|
|
CSCI-GA.3520-001Fall 2026
CS Dept, New York University
Honors Analysis of Algorithms
|
Final exam: Dec 14, during regular class hour (i.e. Dec 14, at 5:10-7:40PM,
Silver 520).
HW- 4,5,6 due on 11/17, 11/24, 12/08.
Instructor: Subhash Khot, Off-416 WWH, Ph: 212-998-4859. Office hours: M 8:30-10:00AM.
Grader: Alisher Aikyn
Class assistant: Hriday Ranka
Course Description
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: 30% Homeworks,
30% Midterm, 40% Finals.
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, scanned solutions.
Deadlines
to be announced as we go along.
Homework 4 Solutions Due 11/17, 11:59PM
Problem
7 is here.
Homework 5 Solutions Due 11/24, 11:59PM
Homework 6 Solutions Due 12/08, 11:59PM
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 |
|