# CSE 202: Syllabus 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

Backtracking

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.

Amazon has fast and free shipping for college students.

### 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