Spring 2016 - COMPSCI 330 - Design and Analysis of Algorithms


Algorithms are a cornerstone of computational sciences and the need for efficient algorithms is ubiquitous in modern technology. However, the primary goals of algorithm design, the resources that need to be optimized, and even the model of computation varies widely between application areas. In this course, we will study some of the fundamental principles of algorithm design that appear in multiple areas and have had broad impact. In addition, we will focus on the mathematical tools that are frequently used in the theoretical analysis of algorithms, and study how such analysis, in turn, influences algorithm design. The course will be at an undergraduate level and will aim to serve the following objectives:


Debmalya Panigrahi
Email: debmalya@cs.duke.edu
Office Hours on Tuesdays and Thursdays at 4:30 - 5:30 pm in LSRC D203

Teaching Assistants (TAs)
Reza Alijani
North 002
Email: alijani@cs.duke.edu
Office Hours on Mondays at 10:30 - 11:30 am and on Fridays at 4:30 - 5:30 pm in North 306

Tianqi Song
North 208
Email: stq@cs.duke.edu
Office Hours on Mondays and Wednesdays at 4 - 5 pm in North 306

Undergraduate Teaching Assistants (UTAs)
Jeremy Fox
Email: jeremy.daniel.fox@gmail.com
Office Hour on Mondays at 3 - 4 pm in the Link

Arun Ganesh
Email: ag310@duke.edu
Office Hour on Mondays at 5 - 6 pm in the Link

Billy Wan
Email: xw58@duke.edu
Office Hour on Thursdays at 6 - 7 pm in the Link

Rex Ying
Email: zy26@duke.edu
Office Hour on Wednesdays at 5 - 6 pm in the Link

Haofeng Zhang
Email: h.z@duke.edu
Office Hour on Fridays at 7 - 8 pm in the Link

Mike Zhu
Email: mzhu22@gmail.com
Office Hour on Tuesdays at 7 - 8 pm in the Link

Lectures in French Science 2231 on Tuesdays and Thursdays at 3:05 - 4:20 pm
Recitations in Gross 107 on Fridays at 3:05 - 4:20 pm

We will use Piazza for all correspondence and discussions related to the course. If you have a question about the course material or want to initiate a discussion, post it on Piazza allowing the entire class to view and participate in it. If you want to contact the course staff only, send a message via Piazza that is visible only to the relevant course staff.



This course covers the design and analysis of algorithms at an undergraduate level. The following is a tentative list of topics to be covered:


There are two hard prerequisites (equivalent courses are also acceptable): If you do not satisfy these prerequisites, please contact the instructor.


Lecture notes will be uploaded on the course website after every lecture. In addition, the following books cover most of the syllabus:

Additional References



Course Plan

LectureDateTopicScribe NotesReferences
1 Th 1/14 History of Algorithms; Asymptotic Notation; Worst-case Analysis Notes DPV: 0, 2
KT: 2
CLRS: 1, 2, 3, 4
Algorithm Design Techniques
2 Tu 1/19 Divide and Conquer: Binary Search, Quick Sort, Merge Sort, Selection, Strassen's Matrix Multiplication Notes DPV: 2
KT: 5
CLRS: 4, 7, 8, 9, 28
3 Th 1/21
4 Tu 1/26 Greedy Algorithms: Fractional Knapsack, Interval Scheduling, Huffman codes Notes DPV: 5
KT: 4
CLRS: 16
5 Th 1/28
6 Tu 2/2 Dynamic Programming: Shortest Path in a DAG, Longest Increasing Subsequence, 0-1 Knapsack
Notes DPV: 6
KT: 6
CLRS: 15
7 Th 2/4
Graph Algorithms
8 Tu 2/9 Graph Representations and Traversal: Depth First Search, Breadth First Search, Applications Notes DPV: 3
KT: 3
CLRS: 22
9 Th 2/11
10 Tu 2/16 Shortest Path: Bellman-Ford, Dijkstra, All-Pairs Shortest Paths
Notes DPV: 4.6, 6.6
KT: 6.8
CLRS: 24.1, 25
11 Th 2/18 Network Flows: Maxflow Mincut Theorem, Augmenting Paths, Applications Notes DPV: 7
KT: 7
CLRS: 26
12 Tu 2/23
Th 2/25 Midterm 1: Lectures 1-12
13 Tu 3/1 Minimum Spanning Tree: Kruskal, Prim Notes DPV: 5
KT: 4
CLRS: 16, 23
14 Th 3/3 Disjoint sets: Union by rank, amortized analysis: binary counters, the potential method Notes CLRS: 21
15 Tu 3/8 Disjoint sets: Path compression CLRS: 17
Randomized Algorithms
16 Th 3/10 Random processes: Birthday Paradox, Coupon Collector, Balls in Bins Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
Tu 3/15, Th 3/17 Spring Break: No Class
17 Tu 3/22 Las Vegas Algorithms Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
18 Th 3/24 Monte Carlo Algorithms
19 Tu 3/29 Hashing Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
Linear Programming
20 Th 3/31 LP Formulations, Integer Linear Program Notes CLRS: 29
21 Tu 4/5 LP Duality Notes CLRS: 29
22 Th 4/7 LP Algorithms, Simplex Algorithms, Separation Oracles
Computational Geometry
23 Tu 4/12 Convex Hull Algorithms
Guest Lecturer: Dr. Kyle Fox
Notes CLRS: 33
Th 4/14 Midterm 2: Lectures 13-23
24 Tu 4/19 Complexity Classes P and NP, Polynomial-time Reductions Notes DPV: 8
KT: 8
CLRS: 34
25 Th 4/21 Approximation Algorithms: Vertex Cover, Set Cover, TSP Notes DPV: 8, 9
KT: 8, 11
CLRS: 34, 35
26 Tu 4/26 LP Rounding Notes
Sa 5/7 Final Exam: All Lectures
Location: French Science 2231