CPS 130: Algorithm Design

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 3 in-class exams of 100 marks each (A,B,C), and a final exam of 200 marks (D).

The best 5 homeworks will be worth a total of 100 points (E)
The final grade will be (Best 2 of A,B,C) + D + E for a total of 500 points.

Course Textbooks:

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

Homework Assignments: Solve these problems from Kleinberg-Tardos.

Homework 1: (due Jan 24) Problems 4, 5, 6, 7, and 8 from Chapter 2.
Homework 2: (due Feb 2) Problems 1, 3, 9, 10, and 12 from Chapter 3.
Homework 3: (due Feb 14) Problems 8, 9, 10, 11, 18, 21, and 22 from Chapter 4.
Homework 4: (due Feb 28) Problems 2, 3, 7, 12, 14, and 17 from Chapter 4.
Homework 5: (due Mar. 7) Problems 1, 3, and 6 from Chapter 5.
Homework 6: (due Apr. 6) Problems 1, 8, 11, 12, 15, 16, 19, 21, 22, and 23 from Chapter 6.

Not for grade:
Additional Problem Set 1
Additional Problem Set 2

Writing Solutions: A typical problem will be of the form "Design an efficient algorithm for problem X". I expect you to provide the answer in the following format:

1. CLEAR description of the algorithm (either pseudocode + English comments, or mathematically precise English). You are allowed to use algorithms discussed in class as sub-routines provided the inputs and outputs are clearly specified. The description should be sufficient to allow any computer literate person to unambiguously implement the algorithm. DO NOT WRITE CODE IN A PROGRAMMING LANGUAGE.
2. PROVE that your algorithm is correct. If I feel that you do not understand why your algorithm works (even if I know why it is correct), you will be penalized heavily.
3. POLYNOMIAL running time. You need to give the running time in O-notation, along with relevant proof. Again, if I feel you are hand-waving, you will be penalized heavily.
4. RELATIVE efficiency: Try to make your running time as small as possible. The more cleverness you put in, the more points you get.

I will place sample solutions to the homework problems as the course moves along. You are strongly encouraged to solve and submit the homework problems since that will give you an idea of what to do on the exams. The only way you can learn the material is to solve as many problems from the textbook and other sources as you can.

Office Hours:

(Kamesh) Thu 10:00-12:00 (D205)

(Sharath) Tue 10:00-12:00 (N007)

Lect.	Date	Topics
1	Jan. 10	First example: Euclid's GCD algorithm History of algorithm design Performance Metrics
2	Jan. 12	Asymptotic analysis of running times
3	Jan. 17	Basic Graph Algorithms: Specifying graphs as input Depth and Breadth First Search Basic Data Structures: Stacks and Queues
4	Jan. 19	Properties of the BFS and DFS solutions Directed Graphs: Strong Connectivity, Topological sorting Testing Bipartiteness
5	Jan. 24	First design technique: Greedy Algorithms Example: Fractional Knapsack Sorting using Heaps The Shortest Path Problem
6	Jan. 26	Dijkstra's Algorithm: Implementation using Heaps The Minimum Spanning Tree Problem: Cuts and cycles Kruskal's and Prim's Algorithms
7	Jan. 31	Data Structures for Disjoint Sets: Amortization
8	Feb. 2	Analysis of Union-find with Path Compression
9	Feb. 7	FIRST EXAM (Lec. 1 - 6)
10	Feb. 9	Exchange Argument for Greedy Algorithms Scheduling with Deadlines, Smith's Rule
11	Feb. 14	2-D Convex Hulls Graham Scan, Gift Wrapping
12	Feb. 16	Greedy algorithms for Interval Graphs Interval Coloring, Interval Scheduling
13	Feb. 21	Second Design Technique: Divide and Conquer Example: Merge-Sort Algorithm Recurrence Relation Examples.
14	Feb. 23	Counting Inversions Finding the closest pair of points in 2-D Integer Multiplication
15	Feb. 28	Third Design Technique: Dynamic Programming Memoization: Weighted Interval Scheduling Integer Knapsack and Pseudo-polynomial time
16	Mar. 2	Shortest paths with negative edge lengths: Bellman Ford Algorithm
17	Mar. 7	Sequence Alignment with Penalties Linear Space Alignment using Divide and Conquer
18	Mar. 9	SECOND EXAM (Lec. 7 - 14)
		SPRING BREAK
19	Mar. 21	CLASS CANCELED
20	Mar. 23	Optimization Problems on Trees Basics of Probability Theory: Linearity of Expectation
21	Mar. 28	Coupon Collector Quicksort, Global min-cuts
22	Mar. 30	Randomized searching using Hash functions
23	Apr. 4	Network Flows: Ford-Fulkerson algorithm Integrality and duality
24	Apr. 6	Applications of flows and cuts: Matching and scheduling
25	Apr. 11	THIRD EXAM (Lec. 15 - 20)
26	Apr. 13	Computational Intractability and NP-Completeness Definition of NP 3SAT is NP-complete
27	Apr. 18	Reductions between NP-complete problems 3SAT -> Independent Set -> Vertex Cover -> Set Cover
26	Apr. 20	NP-completeness of Directed Hamiltonian Cycle, Hamiltonian Cycle, TSP, 3-Coloring, Subset Sum
28	Apr. 25	Approximation Algorithms
	May 3	FINAL EXAM (7 - 10 PM)