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

  1. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
  2. 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.