513 Fall 2005 Course Information

Time: TTh 3:20pm-4:40pm
Place: HLL-120
Professor: M. Farach-Colton
Office Hours: T 1:30pm-3:00pm
TA: Miguel Mosteiro

Recommended Text: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, MIT Press.
Additional Reading: Garey and Johnson, Computers and Intractability: A guide to the theory of NP-Completeness

Prerequisites: Knowledge of basic concepts of programming and data structures is assumed (e.g. lists, stacks, queues, trees) as well as basic mathematics (e.g. proof by induction, permutations, logarithms, the basics of solving recurances, and asymptotic (i.e. "big-oh", "big-omega") notation). A general background in undergraduate algorithms: sorting upper and comparison model lower bounds, MST algorithms, shortest paths, etc.

Course Contents: Fundamental techniques for designing efficient combinatorial algorithms and mathematical methods for analyzing their complexity.

Tenative list of topics: (Note that the list of topics may vary according to the background of the students.)

Query problems: Least Common Ancestors and Range Minimum Queries; Level Ancestors
Integer Sorting. Soring lower bounds -- comparison and other models.
Divide and conquer, recurrences, Strassen's integer multiplication, suffix sorting.
Selection, random and deterministic.
Dictionary problem: Balanced trees, hashing, van Emde Boas trees
String Algorithms: KMP, dynamic programming, Convolutions and FTT -- with applications like less-than matching.
Randomized Algorithms: Karp-Rabin, Zeros testing, randomized routing.

Grading Policy: There will be two midterms and a final exam. Each midterm is worth 25% of the final grade. The final will weigh 45% of the final grade. All tests are cummulative. Weekly homework assignments will constitute the remaining 5% of the final grade.

The homework assignments are mathematically oriented and involve derivations of mathematical equations, proofs of combinatorial theorems and running time analysis of combinatorial algorithms. 80% of the assigned homework will be used to compute the homework grade. Homework is to be done independently. Students are encouraged to disscuss general course material with their classmates, the TA or the instructor, but specific homework problems may not be written collaboratively. NO LATE HOMEWORK WILL BE ACCEPTED.

Homework 1 Due Sept 8th.

Exam 1: October 11. Here is a sample test. It's the actual first midterm from '95. Obviously, we haven't covered exactly the same topics this year as then, and so the test covers some topics you won't recognize, like Fibonacci Heaps. But it should give you a good idea of what an exam will look like.
Exam 2: November 17
Final: December 15