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. The emphasis is on abstraction, design, and analysis and NOT on programming.
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 (C)
The final exam is of 200 points (D)
The final grade will be A + B + C + D for a
total of 500 points.
All Assignments will be posted on Blackboard.
LATE POLICY: There is no credit for late submissions.
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. So I strongly encourage you to form groups of 2-3 students, in order to discuss and solve extra problems from the textbooks. One member of the team should grade the other's solutions. You can submit these solutions. I will consider these to increase your grade if your performance on the exams and homeworks is leading to lower than a B- grade.
Course Textbooks
Algorithm Design by J. Kleinberg and E. Tardos. (optional)
Office Hours
Lecture Schedule
| Lect. | Date | Topics | ||||
|---|---|---|---|---|---|---|
| 1 | Jan. 8 |
First example: Euclid's GCD
algorithm History of algorithm design Performance Metrics |
||||
| 2 | Jan. 13 |
Asymptotic analysis of running
times Writing Solutions |
||||
| 3 |
Jan. 15 |
Basic
Graph
Algorithms: Specifying
graphs as input Depth and Breadth First Search Basic Data Structures: Stacks and Queues |
||||
| 4 | Jan. 20 | Properties of the BFS and DFS solutions Testing Bipartiteness |
||||
| 5 | Jan. 22 | Directed
Graphs: Strong Connectivity, Topological sorting |
||||
| 6 | Jan. 27 | Shortest Paths and Spanning Trees: Dijkstra's Algorithm, Implementation using Heaps |
||||
| Jan. 29 | CLASS CANCELED |
|||||
| 7 | Feb. 3 | Shortest
paths with negative
edge lengths: Bellman Ford Algorithm |
||||
| 8 |
Feb. 5 |
Bellman-Ford implementation, Shortest paths in DAGs |
||||
| 9 |
Feb. 10 | The
Minimum
Spanning Tree Problem: Cuts and cycles Kruskal's and Prim's Algorithms |
||||
| 10 |
Feb. 12 | Data Structures for Disjoint
Sets, Amortization |
||||
| 11 |
Feb. 17 |
Greedy
Techniques: Scheduling with Deadlines, Smith's Rule | ||||
| 12 |
Feb. 19 |
EXAM 1 (Lectures 1-9) | ||||
| 13 |
Feb. 24 |
Divide and Conquer: Closest pair of points in 2-D | ||||
| 14 |
Feb. 26 | Convex Hull Algorithms: Graham Scan, Gift Wrapping | ||||
| 15 |
Mar. 3 |
Integer and Matrix Multiplication |
||||
| 16 |
Mar. 5 |
Polynomial multiplication and Fast Fourier Transform | ||||
| SPRING BREAK | ||||||
| 17 |
Mar. 17 |
Dynamic Programming: Weighted Interval Scheduling | ||||
| 18 |
Mar. 19 |
Integer Knapsack and Pseudo-polynomial time | ||||
| 19 |
Mar. 24 | Shortest Paths Revisited: Bellman-Ford and Floyd-Warshall algorithms |
||||
| 20 |
Mar. 26 |
Sequence alignment and Small space |
||||
| 21 |
Mar. 31 |
Optimization Problems on Trees | ||||
| 22 |
Apr. 2 |
Randomization: Linearity
of
Expectation Randomized searching using Hash functions |
||||
| 23 |
Apr. 7 |
NP-Completeness: Definition of NP 3SAT is NP-complete |
||||
| 24 |
Apr. 9 |
SECOND EXAM (Lec. 11 - 21) | ||||
| 25 |
Apr. 14 |
Reductions between NP-complete problems | ||||
| 26 |
Apr. 16 |
NP-completeness
of Directed
Hamiltonian Cycle, Hamiltonian Cycle, TSP, 3-Coloring, Subset Sum |
||||
| 27 |
Apr. 21 |
CLASS CANCELED |
||||
| 28 |
Apr. 23 |
READING PERIOD |
||||
| May 1 |
7:00 - 10:00 PM: FINAL
EXAM |