## Administrative Information

#### Lectures: MW  3:30-4:45 (WWH 102)

Instructor: Subhash KhotOff  416,  Ph:  212-998-4859

Office hours:  M 2:30-3:30

Teaching assistant: Daniel Wichs.   Office Hours:  Thu 12:00-2:00 pm, Off 408.

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.

### Source

Sept 3

Introduction;  Basic data structures:  arrays.

KT: Chapter 1,2

Sept 8

Basic data structures:  linked lists, heaps;  Heapsort;

Divide and conquer: mergesort, quicksort, recurrence relations.

KT: Chapter 2,5

Sept 10

Divide and conquer: finding median, counting inversions.

KT:Chapter 5

Sept 15

Divide and conquer: fast Fourier transform;

Greedy algorithms: interval scheduling.

KT:Chapter 5,4

### Sept 17

Greedy algorithms: interval partitioning, minimum spanning tree.

KT:Chapter 4

Sept 22

Greedy  algorithms:  Huffman codes

KT:Chapter 4

Sept 24

Dynamic programming:  Fibonacci numbers, subset sum, matrix chain

multiplication, longest common subsequence

KT:Chapter 6

Sept 29

Dynamic programming:  weighted interval scheduling, shortest paths (Bellman-

Ford),  max independent sets in trees

KT:Chapter 6

Oct  1

Amortized analysis:  stack,  binary counter;   Binomial heaps

CLRS:Chapter 17,19

Oct  6

Amortized analysis: Fibonacci heaps

CLRS:Chapter 20

Oct  9

Binary search trees, 2-3 trees;  Breadth-first and depth-first search

KT:Chapter 3

Oct  16

Dijkstra’s shortest path algorithm;  Network flows

CLRS:Chapter 24

Oct  20

Max-flow, Ford-Fulkerson algorithm, max-flow  =  min-cut

KT:Chapter 7

Oct  23

Matchings in bipartite graphs, Hall’s Theorem;  Discrete probability, basics

KT:Chapter 7

Oct  27

Randomized algorithms: Ramsey graphs,  contention resolution

KT:Chapter 13

Oct  29

Randomized algorithms:  max-cut, Markov’s inequality, randomized quick-sort

KT:Chapter 13

Nov 3

Randomized algorithms:  pairwise independent hashing

KT:Chapter 13

Nov 5

Languages, deterministic finite automata, regular languages

Sipser:Chapter 1

Nov 10

Non-deterministic finite automata, regular expressions

Sipser:Chapter 1

Nov 12

Context free grammars, push-down automata

Sipser:Chapter 2

Nov 17

Turing machine, decidable languages, Turing-recognizable languages

Sipser:Chapter 3,4

Nov 19

Undecidability,  diagonalization method

Sipser:Chapter 4

Nov 24

P, NP

Sipser:Chapter 7

Nov 26

NP-completeness: 3SAT, vertex cover, independent set, clique, subset-sum

Sipser:Chapter 7

Dec  1

NP-completeness: Circuit-SAT, Cook-Levin theorem (i.e. 3SAT is NP-complete)

Sipser:Chapter 7

Dec  3, 5, 10

Review