CSE 202: Syllabus, Textbook, and Prerequisites
Syllabus
- Introduction to problems and algorithms
- Mathematics for algorithm analysis
- Divide and conquer
- Sorting and order statistics
- Fast Fourier transform
- Closest pair
- Greedy method
- Dynamic programming
- Graph algorithms
- Network Flow
- Linear programming
- NP-completeness
- PSPACE-complete problems
- Dealing with NP-hardness
- Exploiting input structure
- Approximation algorithms
Textbook
Algorithm Design by Kleinberg and Tardos, 1st edition
Chapters 1 through 12
UCSD Bookstore does not necessarily carry the book.
You can obtain the book from one of the online vendors
or from any other source.
- Fast Ship - Ebay store
- Amazon
Amazon has fast and free shipping for college students.
- Barnes and Noble
Supplementary Reading
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
- Algorithms by Dasgupta, Papadimitriou, and Vazirani
- 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
- Algorithms as covered in CSE 101 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,
- sorting, selection, and searching algorithms,
- standard data structures: arrays, stacks, queues, trees, heaps, binary search trees, and graphs,
- divide-and-conquer, greedy and dynamic programming techniques,
- graph exploration techniques: breadth-first search and depth-first search, and
- standard graph algorithms: minimum spanning trees and shortest paths
|
|