CS 8002, PCPs and Hardness of Approximation : Home Page

CSCI-GA.3520-001

Fall 2026

CS Dept, New York University

Honors Analysis of Algorithms

General Information and Announcements.

The class will meet in person and will be taught on the whiteboard. It will not be recorded, but the video recordings of the class from Fall 2020 will be made available. All course notes are available (see below). All homeworks are available too (see below, there could be some changes, deadlines TBA).

Administrative Information

Lectures: M 5:10-7:40, Silver 520

Instructor: Subhash Khot, Off-416 WWH, Ph: 212-998-4859. Office hours: TBA

Grader: TBA

Class assistant: TBA

Course Description

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 (Fibonnacci heaps, Union-Find)
Algorithms on graphs (DFS, path problems, MST; using reductions for algorithm design)
Dynamic programming
Randomization
NP-completeness

Text: (Not necessarily required. The lectures should be self-contained).

Algorithm Design, by Kleinberg and Tardos.

This book may be useful: Introduction to Algorithms (Second Edition), by Cormen, Leiserson, Rivest, and Stein.

Grading: TBA.

Problems Sets:

Practice Problems (Problems added to the top of the list).

Practice Problems from past PhD Algorithms Exam

Practice Problems from past MS Algorithms Core Exam (easy but may be good as practice problems)

Homeworks: You should submit hand-written solutions.

Deadlines to be announced as we go along.

Problem 7 is here.

Homework 6 could have some broken links. These refer to 2008, 2009 exams from here.

Lectures (Rough plan)

Class Notes: 1 2 DC DC+1 G G+1 D D+1 B B+1 B+2 B+3 B+4 MF R R+1 R+2 NP NP+1 NP+2 NP+3 SC

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