CPSC 629-600: Analysis of Algorithms

Fall 2002
Course Information

Class Meeting: TR12:45-2:00pm, Zachry 105b

Instructor: Andreas Klappenecker
Office: 509B Harvey R. Bright Building
Office hours: TR 10:45-11:45am
Email: klappi @ cs.tamu.edu

Teaching Assistant: Yueping Zhang
Office: 414D Harvey R. Bright Building
Office hours: M 1:45pm-2:45pm, R 4:00pm-5:00pm
Email: yueping @ cs.tamu.edu

General Information

Sneak Preview of Grades: Thursday, Dec 19, 3:00pm-4:00pm, HRBB 509B.
Test results of aks implementations.
Syllabus

Homework

Problem Set 1 [ps][pdf]
Problem Set 2 [ps][pdf]
Problem Set 3 [ps][pdf]
Problem Set 4 [ps][pdf]
Problem Set 5 [ps][pdf]
Problem Set 6 [ps][pdf]

Project

The AKS Primality Test

Lecture Notes

The Extended Euclidean Algorithm [ps][pdf]
An Introduction to the AKS Primality Test [ps][pdf]
Groups, Rings, and Finite Fields [ps][pdf]
Congruences for the Perplexed [ps][pdf]

Lectures

T Sep 03: Introduction, Integers, Ideals, Prime Factorization
R Sep 05: Extended Euclidean algorithm
T Sep 10: Groups and Rings
R Sep 12: The AKS primality test, ideals and finite fields
T Sep 17: The AKS primality test - second helping
R Sep 19: RSA
T Sep 24: Factoring: Pollard's p-1 Method and the Quadratic Sieve
R Sep 26: Divide-and-Conquer, Master Theorem, Merge Sort, Burrows-Wheeler transform
T Oct 01: BZIP, Quicksort, Recurrences
R Oct 03: Recurrences, generating functions
T Oct 08: Generating functions
R Oct 10: Huffman codes, greedy algorithms
T Oct 15: Greedy algorithms for matroids
R Oct 17: Largest weight forrests
T Oct 22: Review
R Oct 24: Midterm exam
T Oct 29: Dynamic programming
R Oct 31: Dynamic programming
T Nov 05: Randomized algorithms, Las Vegas algorithms
R Nov 07: Randomized algorithms, Monte Carlo algorithms
T Nov 12: Complexity Theory
R Nov 14: NP-completeness
T Nov 19: NP-completeness
R Nov 21: NP, coNP, etc.
T Nov 26: Approximation Algorithms
R Nov 28: Thanksgiving - no class.

Culture

Reports are due one week after the talk
Format of the Reports

Talks (you should have completed all reports by November 8)

H. Mahmoud, HRBB 302, Nov 08, 3:00pm
C. Lefurgy, HRBB 124, Nov 06, 4:10pm
G. Chen, HRBB 516, Nov 06, 10:50pm
X. Fu, WERC 315, Nov 01, 1:00pm
R. Guttierez, HRBB 124, Oct 30, 4:10pm
J.-M. Lien, B. Bayazit, HRBB 302, Oct 25, 3pm
J. Kim, R. Pearce, HRBB 113, Oct 18, 3:00pm
S. Vellanki, WERC 315, Oct 18, 1:00pm (Part II)
A.L.N. Reddy, HRBB 124, Oct 16, 4:10pm
S. Zubairy, HRBB 516, Oct 16, 10:50am
D. Loguinov, HRBB 124, Oct 09, 4:10pm
P. Hemmer, HRBB 516, Oct 09, 10:50am.
B. Stroustrup, HRBB 124, Oct 2, 4:10pm.
G. Chen, HRBB 516, Sep 25, 10:50pm.
S. Istrail, HRBB 124, Sep 23, 4:10pm.
Y. Chen, HRBB 113, Sep 20, 3pm.
E. Jung, HRBB 113, Sep 20, 3:30pm.