## The final exam is scheduled on Monday, 12/18, 9AM-1PM.

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.

## 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).

#### Lectures: T Th 9:30-10:45 (19 W4, Room 102)

Instructor: Subhash Khot, Off-416 WWH, Ph: 212-998-4859. Office hours: W, 9:30-11:30AM.

Grader: Zizhou Huang, 60 5th Ave, Room 550, Office hours: Th 3:00-4: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:

• 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: 50% problem sets, 50% final exam.

### Problems Sets:

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.

Deadlines to be announced as we go along.

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

### 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