513 Fall 2011 Course Information


Time: T 1:40pm-4:40pm
Place: RUTCOR 166 PLEASE NOTE CHANGE OF ROOM
Professor: M. Farach-Colton
Office Hours: T 10:30pm-12:00pm
TA: homework">Yongpil Kim

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.)
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.

25% credit will be given for any question for clearly marking the question with "I DON'T KNOW". Answer with a wrong answer will get 0% credit. So it's better for you to admit that you don't know something, rather than trying to fake it.

Exam Schedule: