CSE 202: Syllabus, Textbook, and Prerequisites

Syllabus

  1. Introduction to problems and algorithms
  2. Mathematics for algorithm analysis
  3. Divide and conquer
    • Sorting and order statistics
    • Fast Fourier transform
    • Closest pair
  4. Greedy method
  5. Dynamic programming
  6. Graph algorithms
  7. Network Flow
  8. Linear programming
  9. NP-completeness
  10. PSPACE-complete problems
  11. 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.

  1. Fast Ship - Ebay store
  2. Amazon
    Amazon has fast and free shipping for college students.
  3. Barnes and Noble

Supplementary Reading

  1. Introduction to Algorithms by Cormen, Leiserson, Rives, and Stein
  2. Algorithms by Dasgupta, Papadimitriou, and Vazirani
  3. 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