G22.3520-001         Fall 2009

CS Dept    New York University

Honors Analysis of Algorithms

General Information and Announcements

Final exam is scheduled on Wed, Dec 23, 12:30-4:00pm, Room 202.   

 

Solutions to all homeworks are now available.

 

 

Administrative Information

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

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

Office hours:   Monday,  2:30-3:30pm.

Teaching assistant:  Kristiyan Haralambiev,  Office 714 (Broadway bldg),  Wed, Thu  2:30-3:30pm.   (not available the week of Sept 21-25).  

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.

 

The course (and assignments) will be very similar to the same course I taught in Fall 08.  Here is the link.

 

 

Problems Sets:

 

Practice Problems (Problems added to the top of the list).

 

Problems from past PhD Algorithms Exam  

 

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

 

 

 

Problem Set 1    Solutions

Problem Set 2+3    Solutions

Problem Set 4+5    Solutions  (from past year;  there are missing/extra solutions, problem number mismatch etc.)

Problem Set 6+7    Solutions  (from past year;  there are missing/extra solutions, problem number mismatch etc.)

Lectures

Date

Topics covered

Source

Sept 9

Introduction;  Basic data structures:  arrays,  linked lists, heapsort  

KT: Chapter 1,2

Sept 14

Divide and conquer: mergesort, quicksort, recurrence relations, finding median

KT:Chapter 5

Sept 16

Divide and conquer: counting inversions,  fast Fourier transform

KT:Chapter 5

Sept 21

Greedy algorithms: interval scheduling, interval partitioning

KT:Chapter 4

Sept 23

Greedy algorithms: minimum spanning tree, Huffman codes

KT:Chapter 4

Sept 28

Dynamic programming: subset sum, matrix chain multiplication, longest common subsequence 

KT: Chapter 6

Sept 30

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

max independent sets in trees 

KT: Chapter 6

Oct  5

Amortized analysis:  Binomial heaps, Fibonacci heaps

CLRS: Chapters 17,19,20

Oct 7

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

KT:Chapter 3

Oct 12

Depth first search,  Dijkstra’s shortest path,  max-flow

CLRS:Chapter 24

Oct 14

Max-flow: Ford-Fulkerson algorithm,  max-flow min-cut theorem

KT:Chapter 7

Oct 19

Hall’s Theorem;  Basics of discrete probability,   Probabilistic method: Ramsey numbers

KT:Chapter 13

Oct 21

Randomized algorithms:  Contention resolution, MAX-CUT

KT:Chapter 13

Oct 26

Randomized quicksort,  Hashing,  2-universal families of hash functions

KT:Chapter 13

Oct 28

Hashing;   Introduction:  Automata, Computability and Complexity

KT:Chapter 13

Nov 2

Deterministic finite automata

Sipser:Chapter 1

Nov 4

Non-deterministic finite automata,  Regular expressions

Sipser:Chapter 1

Nov 9

Context free grammars

Sipser:Chapter 2

Nov 11

Push-down automata, Turing machine  

Sipser:Chapter 2

Nov 16,18

Class cancelled

 

Nov 23

Decidable and Turing-recognizable languages

Sipser:Chapter 3,4

Nov 25

Undecidability, diagonalization method

Sipser:Chapter 4

Nov 30

Review by Kristiyan.

 

Dec 2

Review by Kristiyan.

 

Dec 7

P, NP, NP-completeness:  3SAT, Hamiltonian Cycle, TSP

Sipser:Chapter 7

Dec 9

NP-completeness: vertex cover, independent set, clique

Sipser:Chapter 7

Dec 14

NP-completeness: subset-sum,   Review

Sipser:Chapter 7