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

Please note the location for the exam: 194
Mercer St Room 208. 9:00AM  1:00PM
This is DIFFERENT from the
class location. You might want to check out the location beforehand so that you
don't have trouble finding it at the last minute.
Please arrive at least 20 minutes before the exam
starts. You must carry your NYU ID.
Instructor: Subhash Khot, Off416 WWH, Ph: 2129984859. Office hours: W, 9:3011:30AM.
Grader: Zizhou Huang, 60 5th Ave, Room 550, Office hours: Th 3:004:30PM
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 selfcontained).
This book may be useful: Introduction
to Algorithms (Second Edition), by Cormen, Leiserson, Rivest, and Stein.
Grading: 50% problem sets, 50%
final exam.
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 handwritten solutions.
Deadlines
to be announced as we go along.
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: Subsetsum 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, 23 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, Maxflow 
CLRS: Chapter 24 

Maxflow:
Maxflow = Mincut, FordFulkerson algorithm 


Maxflow: 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 QuickSort, MAXCUT 


Randomized
algorithms: Hashing 



Turing
machines, running time, P, nondeterminism, NP 


NPcompleteness:
reductions 


CookLevin
Theorem 
