Spring 2017 - 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:

Course Staff


Debmalya Panigrahi
Email: debmalya@cs.duke.edu
Office Hours on Mondays at 11:30 am - 12:30 pm in LSRC D203

Graduate Teaching Assistants (TAs)

Abraham (Abe) Frandsen
North 001
Email: abef@cs.duke.edu
Office Hours on Sundays at 8 - 9 pm in LSRC A155 and Tuesdays at 1:30 - 2:30 pm in North D306

Tianyu Wang
North 003
Email: tianyu@cs.duke.edu
Office Hours on Wednesdays at 4:30 - 5:30 pm in LSRC D301 and Thursdays at 5 - 6 pm in LSRC D301

Undergraduate Teaching Assistants (UTAs)

Paul Cruz
Email: pbc8@duke.edu
Office Hours on Sundays at 9:30 - 10:30 pm in LSRC A155

Arun Ganesh
Email: ag310@duke.edu
Office Hours on Wednesdays at 7:30 - 8:30 pm in LSRC A155

Erin Taylor
Email: ect15@duke.edu
Office Hours on Mondays at 8 - 9 pm in LSCR A155

Patrick Terry
Email: patrick.terry@duke.edu
Office Hours on Thursdays at 8:30 - 9:30 pm in LSRC A155

Narongsak (Army) Tunjaicon
Email: narongsak.tunjaicon@duke.edu
Office Hours on Sundays at 4 - 5 pm in LSRC A247

Weiyao Wang
Email: weiyao.wang@duke.edu
Office Hours on Tuesday at 8 - 9 pm in LSRC A155

Haofeng (Fred) Zhang
Email: h.z@duke.edu
Office Hours on Thursdays at 7:30 - 8:30 pm in LSRC A155


French Science 2231 on Mondays and Wednesdays at 10:05 - 11:20 am


French Science 2231 on Fridays at 10:05 - 11:20 am
SocSci 136 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 We 1/11 History of Algorithms; Asymptotic Notation; Worst-case Analysis Notes DPV: 0, 2
KT: 2
CLRS: 1, 2, 3, 4
Algorithm Design Techniques
Mo 1/16 Martin Luther King, Jr. Holiday: No class
2 We 1/18 Divide and Conquer: Binary Search, Quick Sort, Merge Sort, Integer Multiplication, Linear-time Selection.
Guest lecturer on 1/18: Prof. Pankaj Agarwal
Notes DPV: 2
KT: 5
CLRS: 4, 7, 8, 9, 28
3 Mo 1/23
4 We 1/25 Greedy Algorithms: Interval Scheduling, Interval Coloring, Fractional Knapsack, Huffman codes Notes DPV: 5
KT: 4
CLRS: 16
5 Mo 1/30
6 We 2/1 Dynamic Programming: Longest Increasing Subsequence, 0-1 Knapsack, Maximal Matching on Trees,
Maximal Independent Set on Trees
Notes DPV: 6
KT: 6
CLRS: 15
7 Mo 2/6
Graph Algorithms
8 We 2/8 Graph Representations and Traversal
DFS, BFS and their applications
From BFS to shortest path
Notes DPV: 3, 4.6, 6.6
KT: 3
CLRS: 22
9 Mo 2/13
10 We 2/15
11 Mo 2/20
We 2/22 Midterm 1: Lectures 1-11
12 Mo 2/27 Shortest Path: Dijkstra's and Bellman-Ford; MST properties Notes1
13 We 3/1 MST: Prim's and Kruskal's, The Union-Find Data Structure Notes1
14 Mo 3/6 The Union-Find data structure and amortized analysis
Network Flows
Notes DPV: 7
KT: 7
CLRS: 26
15 We 3/8
Tu 3/13, Th 3/15 Spring Break: No Class
Randomized Algorithms
16 Mo 3/20 Maxmimal flow and minimal cut Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
17 We 3/22 Monte Carlo algorithm Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
18 Mo 3/27 Las Vegas and Monte Carlo Algorithms Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
19 We 3/29
Linear Programming
20 Mo 4/3 LP Formulations, Integer Linear Program Notes CLRS: 29
21 We 4/5 LP Duality Notes CLRS: 29
22 Mo 4/10 LP Algorithms, Simplex Algorithms, Separation Oracles
We 4/12 Midterm 2: Lectures 12-22
23 Mo 4/17 Complexity Classes P and NP, Polynomial-time Reductions Notes DPV: 8
KT: 8
CLRS: 34
24 We 4/19 Approximation Algorithms: Vertex Cover, Set Cover, TSP Notes DPV: 8, 9
KT: 8, 11
CLRS: 34, 35
Other Topics
23 Mo 4/24 Computational Geometry: Convex Hull Algorithms
Notes CLRS: 33
24 We 4/26 Online Algorithms: Rent-or-buy, paging Notes
Mo 5/1 Final Exam: All Lectures
Time: May 1, 9am-12pm

Location: French Science 2231


DiscussionDateTopicDiscussion Notes
1 Fr 1/13 Induction, big-Oh notation Notes
2 Fr 1/20 Divide and Conquer Notes
3 Fr 1/27 Greedy Algorithms Notes
4, 5 Fr 2/3, Fr 2/10 Dynamic Programming Notes
6 Fr 2/17 DFS and BFS Notes
7 Fr 2/24 Shortest Path Notes
8 Fr 3/24 Probability Notes