CSE 101: Syllabus, Textbook, and Prerequisites
Syllabus
- Recurrence relations
- Divide and conquer
- Searching, sorting and order statistics
- Fast Fourier transform
- Greedy method
- Dynamic programming
- Graph algorithms
- Max flow and min-cut
- Linear programming
- Combinatorial search and heuristic methods
- NP-completeness
Textbook
Algorithms by Dasgupta, Papadimitriou, and Vazirani.
This book can be purchased at Amazon.
Relevant material: Chapters 0 through 8
Draft copy is available online. However, it differs from the print textbook on the set of exercises.
Supplementary Reading
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
- Algorithmic Puzzles, Anany Levitin and Maria Levitin, Oxford University Press
Prerequisites
- Combinatorics and discrete mathematics (as covered in CSE 20 and 21 at UC San Diego)
- Data structures as covered in CSE 100 at UC San Diego
-
Specifically, the course assumes competency in the following topics:
- growth rates of functions,
- formulating and solving recurrence relations,
- combinatorial reasoning,
- basic graph theory,
- proving the correctness of algorithms,
- basic sorting, selection, and searching algorithms,
- standard data structures: arrays, stacks, queues, trees, heaps, binary search trees, and graphs.
|
|