**CPS 330: Algorithm Design**

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.

### Grading

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

Algorithm Design by J. Kleinberg and E. Tardos. (optional; link is to the SLIDES)

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

7 | Jan. 29 |
Shortest
paths with negative
edge lengths: Bellman Ford Algorithm |
||||

8 |
Feb. 3 |
Bellman-Ford implementation, Shortest paths in DAGs |
||||

9 |
Feb. 5 |
The
Minimum
Spanning Tree Problem: Cuts and cycles |
||||

10 |
Feb. 10 |
Kruskal's and Prim's Algorithms | ||||

11 |
Feb. 12 |
Data Structures for Disjoint Sets, Amortization | ||||

12 |
Feb. 17 |
Greedy Techniques: Scheduling with Deadlines, Smith's Rule | ||||

13 |
Feb. 19 |
REVIEW SESSION/SLACK | ||||

14 |
Feb. 24 |
EXAM 1 (Lectures 1 - 8) |
||||

15 | Feb. 26 | Divide and Conquer: Closest pair of points in 2-D | ||||

16 | Mar. 3 | Convex Hull Algorithms: Graham Scan, Gift Wrapping | ||||

17 |
Mar. 5 |
Integer and Matrix Multiplication | ||||

SPRING BREAK | ||||||

18 |
Mar. 17 |
Polynomial multiplication and Fast Fourier Transform | ||||

19 |
Mar. 19 |
Dynamic Programming: Weighted Interval Scheduling Integer Knapsack and Pseudo-polynomial time |
||||

20 | Mar. 24 | Shortest Paths Revisited: Bellman-Ford and Floyd-Warshall algorithms |
||||

21 | Mar. 26 | Sequence alignment and Small space | ||||

22 |
Mar. 31 | Optimization Problems on Trees | ||||

23 |
Apr. 2 |
Randomization: Linearity
of
Expectation Randomized searching using Hash functions |
||||

24 |
Apr. 7 |
NP-Completeness: Definition of NP 3SAT is NP-complete |
||||

25 | Apr. 9 | Reductions between NP-complete problems | ||||

26 |
Apr. 14 |
EXAM 2 (Lec. 9-22) |
||||

27 |
Apr. 16 |
NP-completeness
of Directed
Hamiltonian Cycle, Hamiltonian Cycle, TSP, 3-Coloring, Subset Sum |
||||

28 | Apr. 21 | Fixed Parameter Tractability Approximation algorithms | ||||

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