CS138a: Computer Algorithms (Winter 2006)

This course serves as an introduction to the design and analysis of algorithms.

Announcements

Instructor: Nevin Kapur
Office: Jorgensen 276
Office hours: Tue 3-4pm in Jrg 276
Class hours: T,Th 1:00-2:25pm in 306 Thomas
Teaching Assistants: Jonathan Lee and Piyush Prakash
TA office hours: Wed 9-10pm and Th, 9-10pm in Jrg 154
Mailing list: http://sympa.cs.caltech.edu/wws/info/cs138a (all students are required to subscribe)
Text: Introduction to Algorithms, Second Edition by Cormen, Leiserson, Rivest, and Stein. (Errata). A copy of the text is on reserve in the library.
Grading, homework policy, and syllabus

Lecture slides and other course material will made available here. (Numbers in parentheses indicate chapters from CLRS.)

Class overview and introduction (1-4)
Divide and conquer, FFT (7, 30)
Dynamic programming (15)
Greedy algorithms (16.1-16.3)
Matroids (no slides) (16.4, 16.5)
Binomial heaps (19)
Amortized analysis (17)
Fibonacci heaps (21)
Hashing (11)
Randomized algorithms (5)
Linear Programming: Farkas' Lemma, Weak Duality, Strong Duality, Complementary Slackness (no slides)
Simplex method (no slides)
Network flow problems and algorithms: Network Simplex, Negative cost cycle algorithm, Max-flow problems (no slides)
LP modeling (no slides)
Approximation algorithms (35)
Set Cover via dual fitting, layering, and randomized rounding (no slides)

Unless otherwise noted, all problem sets are due on Friday by noon in the CS lab in Jorgensen.

Graded problem sets can be found in a box on the table next to the folders.

Last modified on March 9, 2006 by Nevin Kapur.