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

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

Instructor: Subhash KhotOff  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:

• 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:

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

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