CPSC 311 Analysis of Algorithms
Spring 2002
Course Information
Instructor: Andreas Klappenecker
Where: Zachry 105B
When: TR 11:10am-12:25pm
Office: HRBB, Room 509B
Office Hours: TR 10:00am-11:00am or by appointment
e-mail: klappi @ cs.tamu.edu
Teaching Assistant: Yueping Zhang
Office: HRBB, Room 414D
Office Hours: T 2:40pm-3:40pm, F 13:40pm-14:30pm or by appointment
e-mail: yueping @ cs.tamu.edu
General Information
- Sneak preview of grades: Thursday, May 9, 11:00am-noon. I cannot e-mail or post grades.
- Syllabus
- Exam 1, Tuesday February 26
- Exam 2, Thursday April 18
- Final Exam, Friday May 03, 3pm-5pm
I have succeeded in this course, what next?
- Have fun with ACM programming problems
[acm]
[acm-eu]
- Read about
complexity theory
- Learn about Quantum Computing in my course in Spring 2003.
- Solve one of the Challenge Problems to be posted on my door.
Homework
Culture
You have to type 1-2 pages summarizing the gist of the talk.
- Bjarne Stroustrup, F Feb 15 2pm, ZACH 102
-
Carl Pomerance, T Mar 5 4pm, Chemistry Building
- Cynthia Dwork, M Mar 25, 4:10pm, HRBB 124
- George Varghese, W Mar 27, 4:10pm, HRBB 124
- Chee K. Yap, F Mar 29, 3:00pm, HRBB 302
- Gabriel Silberman: G-Riddle, R Apr 04, 9:30am, HRBB 124.
- Patrick Langley: Knowledge and data in computational biological discovery, R Apr 11, 9:30am HRBB 124
No time for talks? Review papers by Cynthia Dwork [pdf],
Don Knuth [pdf],
Jon Bentley and Robert Sedgewick [pdf], Chee Yap [gzipped ps]
Lectures
- T Jan 15: Sets, Relations, Induction, the Godzilla Algorithm
- R Jan 17: Analysis of the Godzilla Algorithm
- Texas-Sized Numbers [ps][pdf], Analysis [ps][pdf]
- T Jan 22: Big Oh, Omega, Theta Notation. Proofs by Induction.
- R Jan 24: Euclidean algorithm, correctness, and complexity.
- T Jan 29: Extended Euclidean algorithm, Modular Arithmetic, RSA.
- R Jan 31: RSA, Chinese Remainder Theorem
- T Feb 05: Divide-and-Conquer Methods, Integer Multiplication [ps][pdf]
- R Feb 07: Substitution Method, Master Theorem
- T Feb 12: Master Theorem, Strassen's matrix multiplication
- R Feb 14: Fast Fourier Transform
- T Feb 19: FFT, Dynamic Programming, Longest Common Subsequence
- R Feb 21: Dynamic Programming, Matrix Chain Multiplication
- T Feb 26: EXAM 1
- R Feb 28: Discussion of Exam 1
- T Mar 05: Hashing
- R Mar 07: Hashing
- T Mar 12: Spring Break
- R Mar 14: Spring Break
- T Mar 19: Introduction to Graphs
- R Mar 21: Basic Graph Algorithms, Breadth First Search
- T Mar 26: Depth First Search, Topological Sorting
- R Mar 28: Minimum Spanning Trees
- T Apr 02: Single-Source Shortest Path, Dijkstra's algorithm
- R Apr 04: Single-Source Shortest Path
- T Apr 09: Flow Network Algorithms
- R Apr 11: Ford-Fulkerson Algorithm, Programming Exercise 2
- T Apr 16: Marriage Theorem, Introduction to Complexity Theory
- R Apr 18: Exam 2
- T Apr 23: Complexity Theory, P, PSPACE, NP, NPSPACE
- R Apr 25: NP-completeness
Kruskal's algorithm,
Prim's algorithm,
Dijkstra's algorithm,
Ford-Fulkerson Algorithm