Compsci 330: Design & Analysis of Algorithms

Fall 2013

Course Info

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.

Please use Piazza for Dicussion.

[DPV] Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani (Please click the link for a free draft).
[KT] Algorithm Design by J. Kleinberg and E. Tardos (Optional).
[CLRS] Introduction to Algorithm Design by T. Cormen, C. Leiserson, R. Rivest and C. Stein (Optional).


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

The best 4 out of 5 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.

Submission: Homeworks should be turned in at the beginning of the class on the day it is due.

LATE PENALTY: Seven points per day.

Collaboration: You may *NOT* share written work. To know more about What's OK and What's not OK in this class, please check the Honesty Matrix modified from the original one created by Prof. Ron Parr in our department.

Practice: 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.


Note: The schedule might change frequently. Please always check the web page for the newest schedule.

Lecture # Date Topics Reference
1 Aug. 27
First example: Fibonacci numbers
Time and Space
Divide and Conquer, Memoization, and Dynamic Programming
[DPV: 0.2, 2, 6]
2 Aug. 29
Asymptotic analysis of running times
Dynamic Programming: Knapsack
[DPV: 0.3, 6.4]
3 Sep. 3 Divide and Conquer: Mergesort
Solving recurrence relations (master theorem)
[DPV: 2.2, 2.3]
4 Sep. 5
Non-comparative Sorting Algorithms:
Counting sort and Radix sort (LSD and MSD)
[CLRS: 8.2, 8.3]
5 Sep. 10 Quicksort, Randomized Linear Selection,
Deterministic Linear Selection
[DPV: 2.4,
KT: 13.5,
CLRS: 7, 9.2, 9.3]
6 Sep. 12
Binary Search
Binary Search Trees
[DPV: 2.2, 6,
KT: 2.3, 4.8,
CLRS: 12, 13]
7 Sep. 17 Balanced Search Trees:
Top-Down 2-3-4 Search Trees
Splay Trees
[CLRS: 18.1]
Sep. 19
Amortized Analysis of Splay Trees
[ Lecture Note
and Recitation Note
from Cornell]
Sep. 24 Amortized Analysis with the Potential Method
Stacks and Heaps
[DPV: 4.4.3, 4.5
CLRS: 17.3]
Sep. 26 Heaps: Continued
Graph Representations:
Adjacency Matrix and Adjacency List
Breadth-First Search
[DPV: 3.1, 4.2, 4.5]
Oct. 1
Breadth-First Search: Continued
Depth-First Search
[DPV:4.2, 3.2, 3.3]
Oct. 3
Guest Lecture: Prof. Debmalya Panigrahi
Depth-First Search: Continued
Properties of the BFS and DFS solutions
Dijkstra's Algorithm, Implementation using Heaps
The Minimum Spanning Tree (MST) Problem:
Cut and Cycle Properties
Kruskal's and Prim's Algorithms
[DPV:3.2, 3.3, 4.4, 4.5, 5.1]
Oct. 8 Disjoint Sets
An Application of Disjoint Sets: Connected Components
Data Structures for Disjoint Sets:
Linked List, Union by Rank, Path Compression
Kruskal's Algorithm for MST: Continued
[DPV:3.4, 5.1]
14 Oct. 10 EXAM 1 (Lectures 1 - 10)

Oct. 17
Guest Lecture: Prof. Kamesh Munagala
Divide and Conquer: Closest pair of points in 2-D
[DPV:2, KT:5.4, CLRS:33.4]
16 Oct. 22
Guest Lecture: Prof. Pankaj K. Agarwal
Convex Hull Algorithms:
Graham Scan, Gift Wrapping
Oct. 24
Integer and Matrix Multiplication
[DPV:2.1, 2.5]
Oct. 29
Polynomial Multiplication and Fast Fourier Transform [CLRS:30, DPV:2.6,
Lecture Note from Iowa State University]
19 Oct. 31 Lower bounds on Sorting Algorithms and Convex Hull Algorithms [DPV:2.3 (page 62)
CLRS:8.1, 33.3]
20 Nov. 5 Randomization: Linearity of Expectation
Randomized Algorithms:
Quicksort with random pivot
Quickselect with random pivot
[CLRS:7.3, 9.2,
Lecture Notes from Yale
(Sections 1.3, 3.4.1, 3.6.3, 3.6.4)]
Nov. 7 Quickselect with random pivot: Continued
A Monte Carlo algorithm:
Karger's algorithm for minimum cut of undirected graph
[DPV:6 (page 150),
Lecture Notes from Yale
(Sections 1.4,]
Nov. 12 EXAM 2 (Lectures 10-13)
Nov. 14
Parallel Algorithms [ Prof. Bruce Maggs' paper]
Nov. 19
Parallel Algorithms: Continued [ Prof. Bruce Maggs' paper]
Nov. 21
Two ways to use reductions
Defnitions of P and NP based on search problems
NP-Completeness and NP-Hardness
SAT and 3SAT
Nov. 26
Approximation algorithms:
Greedy Algorithm for Set Cover
Christofides' Algorithm for TSP
[DPV:9.2, 5.4,
Leture Note from Sapienza University of Rome]

27 Dec. 3 Competitive Analysis for Online Algorithms:
2-Competitive Algorithm for Ski-rental Problem
k-Competitive LRU Algorithm for Paging Problem
28 Dec. 5 TBD
Friday, Dec. 13
2:00PM - 5:00 PM: FINAL EXAM