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

Final
exam is scheduled on Wed, Dec 23, 12:304:00pm, Room 202.
Solutions
to all homeworks are now available.
Instructor: Subhash Khot – Off 416, Ph: 2129984859
Office hours: Monday, 2:303:30pm.
Teaching assistant: Kristiyan Haralambiev, Office 714 (Broadway bldg), Wed, Thu 2:303:30pm. (not available the week of Sept 2125).
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.
The course (and assignments) will
be very similar to the same course I taught in Fall 08. Here is the link.
Practice Problems (Problems added to the
top of the list).
Problems
from past PhD Algorithms Exam
Problems
from past MS Algorithms Core Exam (easy but may be good as practice problems)
Problem Set 4+5 Solutions (from past year; there are missing/extra solutions, problem number mismatch etc.)
Problem Set 6+7 Solutions (from past year; there are missing/extra
solutions, problem number mismatch etc.)
Date

Topics covered

Source

Sept
9 
Introduction; Basic data structures: arrays, linked lists, heapsort 
KT:
Chapter 1,2 
Sept
14 
Divide
and conquer: mergesort, quicksort,
recurrence relations, finding median 
KT:Chapter 5 
Sept
16 
Divide
and conquer: counting inversions, fast Fourier transform 
KT:Chapter 5 
Sept
21 
Greedy
algorithms: interval scheduling, interval partitioning 
KT:Chapter 4 
Sept
23 
Greedy
algorithms: minimum spanning tree, Huffman codes 
KT:Chapter 4 
Sept
28 
Dynamic
programming: subset sum, matrix chain multiplication, longest common
subsequence 
KT:
Chapter 6 
Sept
30 
Dynamic
programming: weighted interval scheduling, shortest paths (BellmanFord), max
independent sets in trees 
KT:
Chapter 6 
Oct 5 
Amortized
analysis: Binomial heaps,
Fibonacci heaps 
CLRS:
Chapters 17,19,20 
Oct
7 
Binary
search trees, 23 Tress, Breadth
first search 
KT:Chapter 3 
Oct
12 
Depth
first search, Dijkstra’s
shortest path, maxflow 
CLRS:Chapter 24 
Oct
14 
Maxflow:
FordFulkerson algorithm,
maxflow mincut theorem 
KT:Chapter 7 
Oct
19 
Hall’s
Theorem; Basics of discrete
probability, Probabilistic
method: Ramsey numbers 
KT:Chapter 13 
Oct
21 
Randomized
algorithms: Contention
resolution, MAXCUT 
KT:Chapter 13 
Oct
26 
Randomized
quicksort,
Hashing, 2universal
families of hash functions 
KT:Chapter 13 
Oct
28 
Hashing; Introduction: Automata, Computability and Complexity 
KT:Chapter 13 
Nov
2 
Deterministic
finite automata 
Sipser:Chapter 1 
Nov
4 
Nondeterministic
finite automata, Regular
expressions 
Sipser:Chapter 1 
Nov
9 
Context
free grammars 
Sipser:Chapter 2 
Nov
11 
Pushdown
automata, Turing machine 
Sipser:Chapter 2 
Nov
16,18 
Class
cancelled 

Nov
23 
Decidable
and Turingrecognizable languages 
Sipser:Chapter 3,4 
Nov
25 
Undecidability, diagonalization method 
Sipser:Chapter 4 
Nov
30 
Review
by Kristiyan. 

Dec
2 
Review
by Kristiyan. 

Dec
7 
P,
NP, NPcompleteness: 3SAT,
Hamiltonian Cycle, TSP 
Sipser:Chapter 7 
Dec
9 
NPcompleteness:
vertex cover, independent set, clique 
Sipser:Chapter 7 
Dec
14 
NPcompleteness:
subsetsum, Review 
Sipser:Chapter 7 