CPSC 629: Analysis of Algorithms
Spring 2001
Course Information
Class Meeting: MWF 9:10-10:00am, Harvey R. Bright Building 113
Instructor: Andreas Klappenecker
Office: 509B Harvey R. Bright Building
Office hours: MW 10:10-11:10am
Email: klappi@cs.tamu.edu
Literature
- Introduction to quantum computing by A. Bertiaume
(
[gzipped postscript]
[dvi])
- The standard reference on quantum gates (goes beyond the scope of this course).
- Some slides [ps][pdf] slide 3 contains an obvious typo in the normalization factor.
Lectures
- W Jan 17: Introduction, Matrix Multiplication
- F Jan 19: Strassen's Matrix Multiplication
([strassen.ps]
[strassen.pdf])
- M Jan 22: Matrix Chain Multiplication,
Catalan Numbers, Generating Functions
([catalan.ps]
[catalan.pdf])
- W Jan 24: Dynamic Programming, Matrix Chain Multiplication
- F Jan 26: Knapsack Problem, Floyd's Algorithm
- M Jan 29: Greedy Algorithms, Dijkstra's Algorithm
- W Jan 31: Dijkstra's Algorithm (correctness proof)
- F Feb 2: Kruskal's algorithm
- M Feb 5: Matroids, Bases, Cycles
- W Feb 7: The GREEDY algorithm for matroids, characterization of matroids
- F Feb 9: Generating Functions, Introduction
- M Feb 12: Generating Functions, Basic Techniques
- W Feb 14: Generating Functions ([gf.ps][gf.pdf])
- F Feb 16: Amortized Analysis, Aggregate Method
- M Feb 19: Amortized Analysis, Accounting Method, Potential Method
- M Mar 19: Flows in Networks
- W Mar 21: Ford-Fulkerson algorithm
- F Mar 23: Hamiltonian circuits, traveling salesman problem
- M Mar 26: Introduction to Complexity Theory
- W Mar 28: P versus NP
- F Mar 30: NP-complete problems
- M Apr 2: NP-completeness
- W Apr 4: SAT is NP-complete
- F Apr 6: CLIQUE is NP-complete
- M Apr 9: 3SAT, COLORABILITY
- W Apr 11: COLORABILITY
- F Apr 13: Good Friday - no lecture.
- M Apr 16: Minesweeper is NP-complete
- W Apr 18: RSA
- F Apr 20: Integer factorization
- M Apr 23: Quantum computing
- W Apr 25: Quantum circuits
- F Apr 27: Shor's factorization algorithm
Culture
Remarks