CS 8002, PCPs and Hardness of Approximation : Home Page (original) (raw)
General Information and Announcements
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.
Administrative Information
Lectures: MW 2:00-3:15 (WWH 317)
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:
- Recurrence equations and divide & conquer
- Linear time algorithms (radix sort, lexicographic sort, selection)
- Hashing
- Balanced trees and their augmentation
- Amortized analysis (splay trees, Fibonnacci heaps, Union-Find)
- Algorithms on graphs (DFS, path problems, MST; using reductions for algorithm design)
- Dynamic programming
- Randomization
- NP-completeness
- Automata theory
- Halting problem
Texts:
- Algorithm Design, by Kleinberg and Tardos.
- Introduction to the Theory of Computation (Second Edition), by Michael Sipser.
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.
Problems Sets:
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).
Lectures
| 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 | |