CPS 330: Algorithm Design
Instructor: Kamesh Munagala 
Spring Semester, 2015   (also Spring '14, '11, '10, '09, '08, '07,'06)

Lectures: T/Th 3:05-4:20 (Soc Sci 136)
Recitation: F 11:45 - 1:00 (Phy 130)

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.


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

The best 5 out of 7 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 Sakai.  For assignments, you can discuss problems with each other, but you have to write solutions on your own, and you have to mention who you discussed the problems with. Submitting someone else's solution (even from previous years) with minor changes or asking for solutions on online forums will be considered academic dishonesty.

Course discussions will happen on Piazza.

LATE POLICY: There is no credit for late submissions. No exceptions.

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. 

For your reference, the median grade in the previous few years (when I have taught the course) has been a B. 

Course Textbooks 

Algorithms  by S. Dasgupta, C. Papadimitriou, and U. Vazirani. (required)
Algorithm Design  by J. Kleinberg and E. Tardos.   (optional; link is to the SLIDES)

Office Hours

(Kamesh)                By appointment
(Stavros Sintos)       Thu 4:30 - 6pm  (North 007)
(Nate Xu)                Mon 4 - 5:30pm  (North 303)

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
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
7 Jan. 29
Shortest paths with negative edge lengths:
Bellman Ford Algorithm
Feb. 3
Bellman-Ford implementation, Shortest paths in DAGs
Feb. 5
The Minimum Spanning Tree Problem: Cuts and cycles
Feb. 10  
Kruskal's and Prim's Algorithms
Feb. 12
Data Structures for Disjoint Sets, Amortization
Feb. 17
Greedy Techniques: 
Scheduling with Deadlines, Smith's Rule 

Feb. 19
Feb. 24
EXAM 1 (Lectures 1 - 8)
 15Feb. 26
Divide and Conquer: Closest pair of points in 2-D
 16Mar. 3
Convex Hull Algorithms: Graham Scan, Gift Wrapping
Mar. 5
Integer and Matrix Multiplication
Mar. 17
Polynomial multiplication and Fast Fourier Transform

Mar. 19
Dynamic Programming: Weighted Interval Scheduling
Integer Knapsack and Pseudo-polynomial time
20 Mar. 24Shortest Paths Revisited:
Bellman-Ford and Floyd-Warshall algorithms

 21Mar. 26
Sequence alignment and Small space 
Mar. 31 Optimization Problems on Trees
Apr. 2
Randomization: Linearity of Expectation
Randomized searching using Hash functions
Apr. 7
NP-Completeness: Definition of NP
3SAT is NP-complete
 25Apr. 9
Reductions between NP-complete problems
Apr. 14
EXAM 2  (Lec. 9-22)
Apr. 16
NP-completeness of Directed Hamiltonian Cycle,
Hamiltonian Cycle, TSP, 3-Coloring, Subset Sum
28Apr. 21Fixed Parameter Tractability
Approximation algorithms

Apr. 27
2:00 - 5:00 PM:  FINAL EXAM