CPSC 311H Analysis of Algorithms (Honors)

Fall 2005 Course Information

Instructor	Dr. Andreas Klappenecker
Where	HRBB 104
When	Monday, Wednesday, sometimes Friday, 10:10am-11:20am
Office	HRBB, Room 509B
Office Hours	MT 2:15-3:15pm or by appointment
e-mail	klappi @ cs.tamu.edu
Course Information	Syllabus

Schedule

M Aug 29 Introduction, Big Oh Notation
W Aug 31 Asymptotics
F Sep 02 Proof Techniques
M Sep 05 Proofs, Sums, Heaps - Quiz
W Sep 07 Heaps, Heapsort
M Sep 12 Quicksort - Quiz
W Sep 14 Randomized Quicksort
M Sep 19 Lower bound for comparison based sorting - Quiz
W Sep 21 Median and Selection
F Sep 23 No lecture due to hurricane Rita
M Sep 26 Hashing
W Sep 28 Hashing
M Oct 03 Hashing, Balanced Trees, Quiz
W Oct 05 Red-Black Trees
M Oct 10 Review
W Oct 12 Exam 1
M Oct 17 Dynamic Programming, Matrix Chain Multiplication
W Oct 19 Exam 1 Solutions, Longest Common Subsequences
F Oct 21 Greedy Algorithms
M Oct 24 Greedy Algorithms, Matroids - Quiz
W Oct 26 Matroids
F Oct 28 Karl Rister, IBM
M Oct 31 Amortized Analysis
W Nov 02 Amortized Analysis
F Nov 04 Burrows-Wheeler transformation
M Nov 07 No class
W Nov 09 Single source shortest path, Bellman-Ford Algorithm
M Nov 14 Dijkstra's single source shortest path algorithm
W Nov 16 Review, Quiz
M Nov 21 Exam 2
W Nov 23 Complexity Theory
M Nov 28 P,NP, polynomial reducibility, NP completeness
W Nov 30 NPC problems

Lecture Notes

Homework

Problem Set 1
Problem Set 2
Problem Set 3
Problem Set 4
Problem Set 5
Problem Set 6
Problem Set 7
Problem Set 8

Culture

R.M. Karp, "Reducibility Among Combinatorial Problems", In: Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., Plenum, p. 85-103, 1972 (I am not aware of an online version)
D. Zuckerman, On Unapproximable Versions of NP-Complete Problems, SIAM J. on Computing, 25(6), pp. 1293-1304
C.A.R. Hoare, An axiomatic basis for computer programming, Comm. ACM, 12(10), pp. 576-580, 1969.
R.M. Karp, Combinatorics, complexity, and randomness, Comm. ACM, 29(2), pp. 98-109, 1986.
R.E. Tarjan, Algorithm design, Comm. ACM, 30(3), pp. 204-212, 1987

Some of these papers are only accessible within TAMU (or use VPN).

Sample Exams

Exam 1 Exam 2 Final
(These sample exams are of limited value since the previous course was organized differently).

M	Aug 29	Introduction, Big Oh Notation
W	Aug 31	Asymptotics
F	Sep 02	Proof Techniques
M	Sep 05	Proofs, Sums, Heaps - Quiz
W	Sep 07	Heaps, Heapsort
M	Sep 12	Quicksort - Quiz
W	Sep 14	Randomized Quicksort
M	Sep 19	Lower bound for comparison based sorting - Quiz
W	Sep 21	Median and Selection
F	Sep 23	No lecture due to hurricane Rita
M	Sep 26	Hashing
W	Sep 28	Hashing
M	Oct 03	Hashing, Balanced Trees, Quiz
W	Oct 05	Red-Black Trees
M	Oct 10	Review
W	Oct 12	Exam 1
M	Oct 17	Dynamic Programming, Matrix Chain Multiplication
W	Oct 19	Exam 1 Solutions, Longest Common Subsequences
F	Oct 21	Greedy Algorithms
M	Oct 24	Greedy Algorithms, Matroids - Quiz
W	Oct 26	Matroids
F	Oct 28	Karl Rister, IBM
M	Oct 31	Amortized Analysis
W	Nov 02	Amortized Analysis
F	Nov 04	Burrows-Wheeler transformation
M	Nov 07	No class
W	Nov 09	Single source shortest path, Bellman-Ford Algorithm
M	Nov 14	Dijkstra's single source shortest path algorithm
W	Nov 16	Review, Quiz
M	Nov 21	Exam 2
W	Nov 23	Complexity Theory
M	Nov 28	P,NP, polynomial reducibility, NP completeness
W	Nov 30	NPC problems