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

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

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 14. 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.
- Final: TBA

Other stuff: Suffix Tree Slides