## General Information and Announcements

Final exam is scheduled on Fri December 19, 2014, 11AM - 3PM, in Room 312.

Please arrive 10 mins early, i.e. at 10:50.   This is a closed book exam.   No notes, books, online material etc are allowed.

Solutions to all homeworks, including the last one, are available below.

#### Lectures: MW 2:00-3:15 (WWH 317)

Instructor: Subhash Khot, Off-416, Ph: 212-998-4859

Office hours: TBA.

Course Description

This course is intended to cover the topics needed for the departmental comprehensive exam in Algorithms, which also includes elements of 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 (splay trees, Fibonnacci heaps, Union-Find)
• Algorithms on graphs (DFS, path problems, MST; using reductions for algorithm design)
• Dynamic programming
• Randomization
• NP-completeness
• Automata theory
• Halting problem

Texts:

• Algorithm Design, by Kleinberg and Tardos.
• Introduction to the Theory of Computation (Second Edition), by Michael Sipser.

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 08. Here is the link.

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

### Source

Sept 3

Introduction;  Basic data structures:  arrays,  linked lists, merging sorted lists

KT: Chapter 1,2

Sept 8

Heapsort, Divide and conquer: mergesort, recurrence relations

KT: Chapter 5

Sept 10

Divide and conquer: finding median, quicksort

KT: Chapter 5

Sept 15

Divide and conquer: counting inversions, sorting lower bound, radix sort

KT: Chapter 5

Sept 17

Divide and conquer: fast Fourier transform, polynomial multiplication

KT: Chapter 5

Sept 22

Greedy algorithms: interval scheduling, interval partitioning

KT: Chapter 4

Sept 24

Greedy algorithms: minimum spanning tree

KT: Chapter 4

Sep 29

Dynamic programming: Subset-sum with bounded integers, matrix chain

multiplication, longest common subsequence

KT: Chapter 6

Oct 1

Dynamic programming: weighted interval scheduling, shortest paths,

Maximum independent sets in trees

KT: Chapter 6

Oct 6

Amortized analysis: stack, binary counter, binomial heaps

CLRS: Chapter 17,19,20

Oct 8

Amortized analysis: Fibonacci heaps

CLRS: Chapter 17,19,20

Oct 15

Binary search trees, 2-3 Trees, Breadth first search

KT: Chapter 3

Oct 20

Acyclic graphs, topological sort, strongly connected

graphs, strongly connected components, depth first search

KT: Chapter 3

Oct 22

Dijkstra’s shortest path,  Max-flow

CLRS: Chapter 24

Oct 27

Max-flow:  Max-flow = Min-cut, Ford-Fulkerson algorithm

Oct 29

Max-flow:  Application to Hall’s Theorem

Randomized algorithms: Basics of probability

Nov 3

Randomized algorithms: Union bound, Ramsey

Numbers (application of probabilistic method)

Nov 5

Randomized algorithms: Independence, Contention resolution

Nov 10

Randomized algorithms: Expectation, Randomized Quick-Sort, MAX-CUT

Nov 12

Randomized algorithms: Hashing