CPSC 411 Design and Analysis of Algorithms

Spring 2009
Course Information

Instructor: Andreas Klappenecker
Where: HRBB 104
When: MWF 12:40pm-1:30pm
Office: HRBB, Room 509B
Office Hours: M 11:00am-noon, F 1:30pm-2:30pm
e-mail: klappi at cse.tamu.edu
Course information: Syllabus

Teaching Assistant: Yue Li
Office: HRBB 410D
Office Hours: T 3:30pm-5:00pm, F 10:30am-noon.
e-mail: yli at cs.tamu.edu

Announcments

The CWEB literate programming tools are easily installed (and often already available) on most operating systems; see cweb.pdf and wc.w for an example.
If you are more adventurous, then you can try installing noweb.
Feb 22: Please note that my office hours have changed.
Culture Report 1 due Mon, Feb 2. Submit a summary of a talk or of Turing award lecture by Knuth
Culture Report 2 due Mon, Feb 16. Submit a summary of a talk or of Turing award lecture by Tarjan
Culture Report 3 due Mon, Mar 2. Submit a summary of a talk or of Turing award lecture by Dijkstra
Culture Report 4 due Fri, Apr 3. Submit a summary of a talk or of Turing award lecture by Karp
Culture Report 5 due Mon, Apr 20. Submit a summary of a talk or of Turing award lecture by Cook

Homework

Reading assignment: Chapters 1-3
Reading assignment: Chapter 8
Reading assignment: Chapter 4
Reading assignment: Chapter 16
Reading assignment: Chapter 28.2
Reading assignment: Chapter 15
Reading assignment: Chapter 17
Reading assignment: Chapter 21
Reading assignment: Chapter 22
Reading assignment: Chapter 5
Reading assignment: Chapter 34
Problem set 1
Problem set 2
Problem set 3
Problem set 4, Example of Literate Programming, Sources
Problem set 5
Problem set 6
Problem set 7
Problem set 8

Schedule

W Jan 21 Introduction, Finding Primes in the Digits of Euler's Number

F Jan 23 Asymptotic Notations: Big Oh, Big Omega, Big Theta

M Jan 26 Time complexity of Insertion Sort, Lower bounds for sorting

W Jan 28 Lower bounds for sorting, Divide-and-Conquer Algorithms

F Jan 30 Mergesort
M Feb 02 Homework 1 solutions
W Feb 04 Strassen's method for Matrix Multiplication
F Feb 06 Greedy Algorithms, Huffman codes
M Feb 09 Greedy algorithms, Matroids
W Feb 11 Greedy Algorithms for Matroids
F Feb 13 Matroid Embeddings
M Feb 16 Dynamic Programming, Matrix Chain Multiplication
W Feb 18 Dynamic Programming, Longest Common Subsequence
F Feb 20 Amortized Analysis
M Feb 23 Disjoint Sets - Linked List Implementation
W Feb 25 Disjoint Sets - Forest Implementation
F Feb 27 Review
M Mar 02 Midterm Exam
W Mar 04 Breadth First Search
F Mar 06 Depth First Search
M Mar 09 Topological Sorting, Quiz 5
W Mar 11 Strongly Connected Components
F Mar 13 Single Source Shortest Path Algorithms, Dijkstra, Bellman Ford
Spring Break
M Mar 23 Introduction to Probability Theory
W Mar 25 Randomized Algorithms, Minimum Cut Algorithm
F Mar 27 Randomized Algorithms, Quiz 6
M Mar 30 Generating Random Permutations
W Apr 01 Randomized Selection
F Apr 03 NP Completeness - Basic Definitions
M Apr 06 NP Completeness - Reductions
W Apr 08 NP Completeness - SAT and 3SAT
F Apr 10 NP Completeness - Vertex Cover
M Apr 13 NP Completeness - Further Examples
W Apr 15 Approximation Algorithms
F Apr 17 Undecidability
M Apr 20 Undecidability
W Apr 22 Undecidability
F Apr 24 RSA, Fermat's Little Theorem
M Apr 27 Chinese Remainder Theorem, Analysis of RSA
W Apr 29 Analysis of Bogo-Sort (suggested by Kyle)
F May 01 Fair Pizza Cutting

CPSC 411 Design and Analysis of Algorithms

Spring 2009
Course Information

Announcments

Homework

Schedule

Lecture Notes and Slides

Quizzes

W	Jan 21	Introduction, Finding Primes in the Digits of Euler's Number
F	Jan 23	Asymptotic Notations: Big Oh, Big Omega, Big Theta
M	Jan 26	Time complexity of Insertion Sort, Lower bounds for sorting
W	Jan 28	Lower bounds for sorting, Divide-and-Conquer Algorithms
F	Jan 30	Mergesort
M	Feb 02	Homework 1 solutions
W	Feb 04	Strassen's method for Matrix Multiplication
F	Feb 06	Greedy Algorithms, Huffman codes
M	Feb 09	Greedy algorithms, Matroids
W	Feb 11	Greedy Algorithms for Matroids
F	Feb 13	Matroid Embeddings
M	Feb 16	Dynamic Programming, Matrix Chain Multiplication
W	Feb 18	Dynamic Programming, Longest Common Subsequence
F	Feb 20	Amortized Analysis
M	Feb 23	Disjoint Sets - Linked List Implementation
W	Feb 25	Disjoint Sets - Forest Implementation
F	Feb 27	Review
M	Mar 02	Midterm Exam
W	Mar 04	Breadth First Search
F	Mar 06	Depth First Search
M	Mar 09	Topological Sorting, Quiz 5
W	Mar 11	Strongly Connected Components
F	Mar 13	Single Source Shortest Path Algorithms, Dijkstra, Bellman Ford
		Spring Break
M	Mar 23	Introduction to Probability Theory
W	Mar 25	Randomized Algorithms, Minimum Cut Algorithm
F	Mar 27	Randomized Algorithms, Quiz 6
M	Mar 30	Generating Random Permutations
W	Apr 01	Randomized Selection
F	Apr 03	NP Completeness - Basic Definitions
M	Apr 06	NP Completeness - Reductions
W	Apr 08	NP Completeness - SAT and 3SAT
F	Apr 10	NP Completeness - Vertex Cover
M	Apr 13	NP Completeness - Further Examples
W	Apr 15	Approximation Algorithms
F	Apr 17	Undecidability
M	Apr 20	Undecidability
W	Apr 22	Undecidability
F	Apr 24	RSA, Fermat's Little Theorem
M	Apr 27	Chinese Remainder Theorem, Analysis of RSA
W	Apr 29	Analysis of Bogo-Sort (suggested by Kyle)
F	May 01	Fair Pizza Cutting

CPSC 411 Design and Analysis of Algorithms

Spring 2009 Course Information

Announcments

Homework

Schedule

Lecture Notes and Slides

Quizzes

Spring 2009
Course Information