This course will cover the basic techniques in algorithm design, including greedy algorithms, divide-and-conquer, amortization, dynamic programming, hashing, randomization, and NP-Completeness. The techniques will be covered in-depth, and the focus will be on modeling and solving problems using these techniques.  I will assume prior knowledge of discrete mathematics, probability, and programming. You should meet me if you  do not have this background.

Grading

There will be 2 in-class exams of 100 points each (A,B) 

The best 5 out of 6 homeworks will be worth a total of 100 points (E)

There are four programing assignments for a total of 100 points (C) 

The final exam is of 200 points (D)

The final grade will be (Better of A,B) + C + D + E for a total of 500 points. 


All Assignments will be posted on Blackboard

In general, solve as many extra problems as you can. This course is all about developing problem solving skills, so the more you practice on your own, the better.

Course Textbooks 

Algorithms  by S. Dasgupta, C. Papadimitriou, and U. Vazirani. (required)
Algorithm Design  by J. Kleinberg and E. Tardos.   (optional)

Office Hours

(Kamesh)       Tue  1-2 pm  (D205)
(Nikhil)          Mon 11-12 and Thu 3:15-4:15 pm   (D330)
(Kshipra)       Tue 2:30-4:15pm  (North 311)
 

Lecture Schedule 

 
 
Lect.  Date  Topics 
1 Jan. 9
 First example: Euclid's GCD algorithm
History of algorithm design
Performance Metrics
2 Jan. 14
 Asymptotic analysis of running times
Writing Solutions
3
 Jan. 16
 Basic Graph Algorithms:  Specifying graphs as  input
Depth and Breadth First Search
Basic Data Structures: Stacks and Queues

Jan. 21
 MLK HOLIDAY
4
 Jan. 23
 Properties of the BFS and DFS solutions
Testing Bipartiteness
5
 Jan. 28
 Directed Graphs:
Strong Connectivity, Topological sorting
6
 Jan. 30
 Shortest Paths and Spanning Trees:
Dijkstra's Algorithm, Implementation using Heaps
7
 Feb. 4
 Shortest paths with negative edge lengths:
Bellman Ford Algorithm
8
 Feb. 6
 Bellman-Ford implementation, Shortest paths in DAGs
9
 Feb. 11
 The Minimum Spanning Tree Problem: Cuts and cycles
Kruskal's and Prim's Algorithms
10
 Feb. 13
 Data Structures for Disjoint Sets, Amortization
11
 Feb. 18
 Greedy Techniques:
Scheduling with Deadlines, Smith's Rule
12
 Feb. 20
 FIRST EXAM   (Lec. 1 - 8)
13
 Feb. 25
 Huffman Coding and Entropy
14
 Feb. 27
 Divide and Conquer: Merge-Sort,
Recurrence Relations, Counting Inversions
15
 Mar. 3
 Closest pair of points in 2-D
16
 Mar. 5
 Convex Hull Algorithms: Graham Scan, Gift Wrapping


SPRING BREAK
17
 Mar. 17
 Polynomial multiplication and Fast Fourier Transform
18
 Mar. 19
 Parallel Implementation and Butterfly networks
19
 Mar. 24
 Dynamic Programming: Weighted Interval Scheduling
20
 Mar. 26
 Integer Knapsack and Pseudo-polynomial time
21
 Mar. 31
 Shortest Paths Revisited:
Bellman-Ford and Floyd-Warshall algorithms
Sequence alignment
22
 Apr. 2
 Optimization Problems on Trees
23
 Apr. 7
 Randomization: Linearity of Expectation
Randomized searching using Hash functions
24
 Apr. 9
 SECOND EXAM  (Lec. 11 - 18)
25
 Apr. 14
 NP-Completeness: Definition of NP
3SAT is NP-complete
26
 Apr. 16
 Reductions between NP-complete problems
27
 Apr. 21
 NP-completeness of Directed Hamiltonian Cycle,
Hamiltonian Cycle, TSP, 3-Coloring, Subset Sum
28
 Apr. 23
 <slack>

Apr. 30
 FINAL EXAM  (2 - 5 PM)