|
|
CSCI-GA.3520-001Fall 2018
CS Dept, New York University
Honors Analysis of Algorithms
|
Instructor: Subhash Khot, Off-416, Ph: 212-998-4859 Office hours: Tue 1:00-2:30 (it would help if you send email beforehand).
TA: T. Devanathan. Office hours: Monday 2:00-4:00. Off 409
Course Description
This course is intended to
cover the topics needed for the
departmental comprehensive exam in Algorithms. Unlike in the past, the
course and the final exam will *not* include topics from 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:
Text: (Not necessarily required.
The lectures should be self-contained).
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 16. 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).
Homeworks: I highly recommend hand-written solutions.
Homework 5 (numbering of problems and
solutions could be inconsistent).
Homework 6 (numbering of problems and
solutions could be inconsistent).
Homework
6 could have some broken links. These refer to 2008, 2009 exams from here.
Date
|
Topics covered
|
Source
|
|
Introduction; Basic data structures: arrays, linked lists, merging sorted lists |
KT: Chapter 1,2 |
|
|
Heapsort, Divide and conquer: mergesort, recurrence relations |
KT: Chapter 5 |
|
|
Divide and
conquer: finding median, quicksort |
KT: Chapter 5 |
|
|
Divide and conquer: counting inversions, sorting lower bound, radix sort |
KT: Chapter 5 |
|
|
Divide and conquer: fast Fourier transform, polynomial multiplication |
KT: Chapter 5 |
|
|
Greedy algorithms: interval scheduling, interval partitioning |
KT: Chapter 4 |
|
|
Greedy
algorithms: minimum spanning tree |
KT: Chapter 4 |
|
|
Dynamic
programming: Subset-sum with bounded integers, matrix chain multiplication,
longest common subsequence |
KT: Chapter 6 |
|
|
Dynamic programming:
weighted interval scheduling, shortest paths, Maximum
independent sets in trees |
KT: Chapter 6 |
|
|
Amortized
analysis: stack, binary counter, binomial heaps |
CLRS: Chapter 17,19,20 |
|
|
Amortized
analysis: Fibonacci heaps |
CLRS: Chapter 17,19,20 |
|
|
Binary search
trees, 2-3 Trees, Breadth first search |
KT: Chapter 3 |
|
|
Acyclic graphs,
topological sort, strongly connected graphs,
strongly connected components, depth first search |
KT: Chapter 3 |
|
|
Dijkstra:
shortest path, Max-flow |
CLRS: Chapter 24 |
|
|
Max-flow:
Max-flow = Min-cut, Ford-Fulkerson algorithm |
|
|
|
Max-flow:
Application to Hall Theorem Randomized
algorithms: Basics of probability |
|
|
|
Randomized
algorithms: Union bound, Ramsey Numbers
(application of probabilistic method) |
|
|
|
Randomized
algorithms: Independence, Contention resolution |
|
|
|
Randomized
algorithms: Expectation, Randomized Quick-Sort, MAX-CUT |
|
|
|
Randomized
algorithms: Hashing |
|
|
|
|
Turing
machines, running time, P, non-determinism, NP |
|
|
|
NP-completeness:
reductions |
|
|
|
Cook-Levin
Theorem |
|