
CSCIGA.3520001Fall 2014
CS Dept,
New York University
Honors Analysis of Algorithms

Final
exam is scheduled on Fri December 19, 2014, 11AM  3PM, in Room 312.
Please
arrive 10 mins early, i.e. at 10:50. This is a closed book exam. No notes, books, online material etc are allowed.
Solutions
to all homeworks, including the last one, are
available below.
Instructor: Subhash Khot, Off416, Ph: 2129984859
Office hours: TBA.
Grader: TBA.
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)
Towards
the preparation for the final exam, the main thing to do is practice, practice
and practice! In addition to the problems from the past PhD/MS exams and
homework problems, you can also work through problems in the [KT] textbook.
Also, you may not want to wait till the relevant topics are covered in class
(which might be too late, especially for the topics to be covered towards the
end).
Date

Topics covered

Source

Sept
3 
Introduction; Basic data structures: arrays, linked lists, merging sorted lists 
KT: Chapter 1,2 
Sept
8 
Heapsort, Divide and conquer: mergesort, recurrence relations 
KT: Chapter 5 
Sept
10 
Divide and
conquer: finding median, quicksort 
KT: Chapter 5 
Sept
15 
Divide and conquer: counting inversions, sorting lower bound, radix sort 
KT: Chapter 5 
Sept
17 
Divide and conquer: fast Fourier transform, polynomial multiplication 
KT: Chapter 5 
Sept
22 
Greedy algorithms: interval scheduling, interval partitioning 
KT: Chapter 4 
Sept
24 
Greedy
algorithms: minimum spanning tree 
KT: Chapter 4 
Sep
29 
Dynamic
programming: Subsetsum with bounded integers, matrix chain multiplication,
longest common subsequence 
KT: Chapter 6 
Oct
1 
Dynamic
programming: weighted interval scheduling, shortest paths, Maximum
independent sets in trees 
KT: Chapter 6 
Oct
6 
Amortized
analysis: stack, binary counter, binomial heaps 
CLRS: Chapter 17,19,20 
Oct
8 
Amortized
analysis: Fibonacci heaps 
CLRS: Chapter 17,19,20 
Oct
15 
Binary search
trees, 23 Trees, Breadth first search 
KT: Chapter 3 
Oct
20 
Acyclic graphs,
topological sort, strongly connected graphs,
strongly connected components, depth first search 
KT: Chapter 3 
Oct
22 
Dijkstra’s
shortest path, Maxflow 
CLRS: Chapter 24 
Oct
27 
Maxflow: Maxflow = Mincut, FordFulkerson
algorithm 

Oct
29 
Maxflow: Application to Hall’s Theorem Randomized
algorithms: Basics of probability 

Nov
3 
Randomized
algorithms: Union bound, Ramsey Numbers
(application of probabilistic method) 

Nov
5 
Randomized
algorithms: Independence, Contention resolution 

Nov
10 
Randomized
algorithms: Expectation, Randomized QuickSort, MAXCUT 

Nov
12 
Randomized
algorithms: Hashing 









