|
CSCI-GA.3520-001Fall 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, Off-416, Ph: 212-998-4859
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: Subset-sum 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, 2-3 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, Max-flow |
CLRS: Chapter 24 |
Oct
27 |
Max-flow: Max-flow = Min-cut, Ford-Fulkerson
algorithm |
|
Oct
29 |
Max-flow: 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 Quick-Sort, MAX-CUT |
|
Nov
12 |
Randomized
algorithms: Hashing |
|
|
|
|
|
|
|
|
|
|