CSE 202: Syllabus

Syllabus

• Introduction to problems and algorithms
• Mathematics for algorithm analysis
• Graph algorithms
• Greedy method
• Divide and conquer
• Dynamic programming
• Network Flow
• NP-completeness
• PSPACE-complete problems
• Dealing with NP-hardness
• Approximation algorithms

Textbook

Algorithm Design by Kleinberg and Tardos, 1st edition

Supplementary Reading

• Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
• Algorithms by Dasgupta, Papadimitriou, and Vazirani
• Algorithmic Puzzles by Anany Levitin and Maria Levitin, Oxford University Press

Evaluation

There will be one midterm exam (during regular class time, on Monday February 11) one final exam (during final week, as scheduled by the university), and 5 problem sets given as homework assignments. Each will contribute to your final grade as follows: Homework (30%), Midterm (30%), Final (40%).

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