
G22.3520001
Fall 2008
CS Dept New York University
Honors Analysis of Algorithms

Instructor: Subhash Khot – Off 416, Ph: 2129984859
Office hours: M 2:303:30
Teaching assistant: Daniel Wichs. Office Hours: Thu 12:002:00 pm, Off 408.
Course Description
This course is intended to
cover the topics needed for the
departmental comprehensive exam in Algorithms, which also includes elements
of the theory of computation. The goal of the course, in addition to covering
the topics listed below, is to improve your algorithmic problem solving skills.
Topics:
Texts:
This book may be useful: Introduction to Algorithms (Second
Edition), by Cormen, Leiserson,
Rivest, and Stein.
Grading: 50% problem sets, 50%
final exam.
Practice Problems (Updated Oct 6; Problems added
to the top of the list).
Problems
from past PhD Algorithms Exam
Problems from 2006 Exam Problems
from 2007 Exam
Problems
from past MS Algorithms Core Exam (easy but may be good as practice problems)
Date

Topics covered

Source

Sept
3 
Introduction; Basic data
structures: arrays. 
KT:
Chapter 1,2 
Sept
8 
Basic
data structures: linked lists,
heaps; Heapsort; Divide
and conquer: mergesort, quicksort,
recurrence relations. 
KT:
Chapter 2,5 
Sept
10 
Divide and conquer: finding median, counting inversions. 
KT:Chapter 5 
Sept
15 
Divide
and conquer: fast Fourier transform; Greedy
algorithms: interval scheduling. 
KT:Chapter 5,4 
Sept 17

Greedy
algorithms: interval partitioning, minimum spanning tree. 
KT:Chapter 4 
Sept
22 
Greedy algorithms: Huffman codes 
KT:Chapter 4 
Sept
24 
Dynamic
programming: Fibonacci numbers,
subset sum, matrix chain multiplication,
longest common subsequence 
KT:Chapter 6 
Sept
29 
Dynamic
programming: weighted interval scheduling,
shortest paths (Bellman Ford), max independent sets in trees 
KT:Chapter 6 
Oct 1 
Amortized
analysis: stack, binary counter; Binomial heaps 
CLRS:Chapter 17,19 
Oct 6 
Amortized
analysis: Fibonacci heaps 
CLRS:Chapter 20 
Oct 9 
Binary
search trees, 23 trees;
Breadthfirst and depthfirst search 
KT:Chapter 3 
Oct 16 
Dijkstra’s shortest path algorithm; Network flows 
CLRS:Chapter 24 
Oct 20 
Maxflow,
FordFulkerson algorithm, maxflow
= mincut 
KT:Chapter 7 
Oct 23 
Matchings in bipartite graphs, Hall’s Theorem; Discrete probability, basics 
KT:Chapter 7 
Oct 27 
Randomized
algorithms: Ramsey graphs,
contention resolution 
KT:Chapter 13 
Oct 29 
Randomized
algorithms: maxcut,
Markov’s inequality, randomized quicksort 
KT:Chapter 13 
Nov
3 
Randomized
algorithms: pairwise
independent hashing 
KT:Chapter 13 
Nov
5 
Languages,
deterministic finite automata, regular languages 
Sipser:Chapter 1 
Nov
10 
Nondeterministic
finite automata, regular expressions 
Sipser:Chapter 1 
Nov
12 
Context
free grammars, pushdown automata 
Sipser:Chapter 2 
Nov
17 
Turing
machine, decidable languages, Turingrecognizable languages 
Sipser:Chapter 3,4 
Nov
19 
Undecidability, diagonalization method 
Sipser:Chapter 4 
Nov
24 
P,
NP 
Sipser:Chapter 7 
Nov
26 
NPcompleteness:
3SAT, vertex cover, independent set, clique, subsetsum 
Sipser:Chapter 7 
Dec 1 
NPcompleteness:
CircuitSAT, CookLevin theorem (i.e. 3SAT is NPcomplete) 
Sipser:Chapter 7 
Dec 3, 5, 10 
Review
