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.)
- Query problems: Least Common
Ancestors and Range Minimum Queries; Level
Ancestors
-
Integer Sorting. Sorting 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 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:
- Exam 1: Oct 13. 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. But it should give
you a good idea of what an exam will look like. Here is another midterm. And another.
- Exam 2: TBA
- Final: TBA
Other stuff: Suffix Tree Slides