513 Fall 2021 Course Information


Time: W 11:00pm-2:20pm
Place: Livingston TIL258 PLEASE NOTE: Give yourself extra time to get to Livingston Campus.
Professor: M. Farach-Colton
Office Hours: M 11:00pm-12:00pm
, or by appointment. TA info: TBA
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 three example, each with a third of the final grade. All tests are cummulative. Weekly homework assignments will be used to determine if someone close to the border between two grades should be moved up.

The homework assignments are mathematically oriented and involve derivations of mathematical equations, proofs of combinatorial theorems and running time analysis of combinatorial algorithms. Students can form groups of up to four for the purposes of homework. Homework is to be done independently within each group. Each group should turn in one assignment, clearly marked with group-member names. Once you form a group, it can't be changed. 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. But of course you get partial credit for saying something better than I don't know.

Tentative Exam Schedule:


Other stuff: Suffix Tree Slides