G22.3520-001         Fall 2008

CS Dept    New York University

Honors Analysis of Algorithms

General Information and Announcements

NOTE:  THIS IS AN OLD WEBPAGE FOR THE COURSE IN FALL 2008

 

Administrative Information

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

Instructor: Subhash Khot – Off  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:

 

Texts:

 

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:

 

Practice Problems (Updated Oct 6;  Problems added to the top of the list).

 

Problems from past PhD Algorithms Exam   Problems from 2006 Exam    Problems from 2007 Exam

 

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

 

Problem Set 1      

 

Problem Set 2+3   

 

Problem Set 4+5 

 

Problem Set 6+7  

 

 

Lectures

Date

Topics covered

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