Prerequisites:
- Inductive proofs, recursion, basic ability to prove things.
- Solving recurrences.
- Boolean logic. 
- Asymptotics.
- representation of input and input size.
- Finite automatas, Turing machines, regular languages, context free.
- etc.

Basic numeric algorithms
- addition, subtraction, multiplication of n-bit numbers

Graphs
- basics, adjacency lists vs matrix,
- undirected vs directed, paths, cycles, walks
- basic search for reachability
- DFS, BFS, properties
- DAGs, properties (sinks, sources), topological sort
- linear time algorithms to check various reachability properties etc.
- strong connected components, meta graph, knowledge that meta graph
  can be constructed via a linear time algorithm

Single-source shortest path algorithms
- definitions
- BFS and Dijkstra's algorithm for non-negative lengths
- shortest path trees
- Negative length edges and generic algorithm
- Bellman-Ford algorithm for negative cycle detection and
  shortest paths with negative length edges
- Linear time algorithm for shortest paths in DAGs with negative lengths

Recursion
- recursive algorithms
- recurrences and ability to solve them asymptotically via
  unfolding, recursion trees, guess and verify
- Divide and conquer technique
- Binary search

Sorting and selection
- Algorithms for sorting
- Linear time algorithm for selection and medians


Dynamic Programming
 - Recursion + memoization = dyanamic programming
 - Ability to convert recursive algorithm into iterative algorithm
   to avoid recomputing solutions
 - Run time and space analysis
 - Reducing space if only value needed

Greedy Algorithms
 - exchange argument based proofs for greedy algorithm

Minimum Spanning Trees
 - definition of problem
 - cut and cycle properties, safe and unsafe edges
 - correctness of MST algorithms via safe/unsafe characterization
 - Kruskal, Prim, and their implementation and running time
 - Union Find data structure and knowledge of implementations discussed
   in lecture notes.
 - Basics of amortized analysis

Basics of randomized algorithms
 - definition of a randomized algorithm
 - basics of discrete probability, especially expectation
 - randomized quick sort and selection
 - basic knowledge of hashing but no need to know analysis of
   universal hashing.
 

Basics of network flow
 - definitions of flows/cuts
 - Ford-Fulkerson algorithm for finding a maximum flow
   via augmenting paths in residual graph
 - Proof of maxflow-mincut theorem via FF algorithm
 - Integrality of flow when capacities are integer
 - Knowledge of polynomial time variants of FF and their running time.
 - Finding a mincut through a max flow

Applications of network flow:
 - Bipartite matching
 - Hall's condition
 - Baseball elimination
 - Project selection
 - Circulations.

Reductions
 - Polynomial time reductions.
 - Search, decision and optimization problems.
 - Indepdent set <-> Vertex cover
 - Indepdent set <-> Clique.
 - Vertex cover -> set cover.
 - Turing reduction
 - Karp reduction

NP Completeness:
 - SAT
 - CSAT
 - SAT <= CSAT
 - SAT <= 3SAT
 - 3SAT <= Indepdent set
 - Certificates, and verifiers.
 - Definition of P, NP, coNP.
 - Cook-Levin theorem (CSAT is NPComplete).
 - CSAT <= 3SAT
 - 3SAT <= Hamiltonian cycle in directed graph.
 - Hamiltonian cycle undirected <= Hamiltonai cycle directed.
 - 3SAT <= 3COLOR.
 - 3SAT <= Vec Subset sum.
 - Vec subset sum <= Subset sum.
 - Subset sum <= Partition. 

  Note: We do not expect you to be able to reproduce the proofs of the
  harder reductions (Hamiltonian cycle comes to mind). You need to
  understand the basic mechanism, and be able to prove NP Completeness
  for "reasonable" problems.

Complexity
 - complement language.
 - coNP
 - coP
 - P is contained in NP and in coNP.
 - NP intersection co-NP.
 - various relations between these complexity classes.
 - Self reduction.
 - Self reducibility for all NP Complete problems encountered in
    class/homeworks/discussion sections.

   (For the complexity topics, we expect a reasonable understanding of
    the basic concepts - not a mastery of this rather involved topic.)

-------------------------------------------------------------------------
Summary: All topics covered in lectures that are in slides for
lectures 1-24.