Spring 2018 - COMPSCI 330 - Design and Analysis of Algorithms

Overview

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

Instructor

Debmalya Panigrahi
LSRC D203
Email: debmalya@cs.duke.edu
Office Hours on Mondays at 3 - 4 pm in LSRC D203

Graduate Teaching Assistants (TAs)

Sam Haney
LSRC D122
Email: shaney@cs.duke.edu
Office Hours on Fridays at 12 - 1 pm in North 306

Nat Kell
LSRC D122
Email: kell@cs.duke.edu
Office Hours on Sundays at 5 - 6 pm and Thursdays at 7 - 8 pm in North 306

Kevin Sun
North 003
Email: ksun@cs.duke.edu
Office Hours on Mondays at 4 - 5 pm and Wednesdays at 4 - 5 pm in North 306

Undergraduate Teaching Assistants (UTAs)

Xingyu Chen
Email: xingyu.chen@duke.edu
Office Hours on Thursdays at 6 - 7 pm in North 306

Feng Gui
Email: feng.gui@duke.edu
Office Hours on Thursdays at 4 - 5 pm in North 306

Katherine Guo
Email: katherine.guo@duke.edu
Office Hours on Thursdays at 5 - 6 pm in North 306

Aninda Manocha
Email: aninda.manocha@duke.edu
Office Hours on Wednesdays at 5 - 6 pm in North 306

Vinit Ranjan
Email: vinit.ranjan@duke.edu
Office Hours on Mondays at 6 - 7 pm in North 306

Erin Taylor
Email: erin.c.taylor@duke.edu
Office Hours on Wednesdays at 6 - 7 pm in North 306

Haofeng (Fred) Zhang
Email: h.z@duke.edu
Office Hours on Mondays at 5 - 6 pm in North 306

Yumin Zhang
Email: yumin.zhang@duke.edu
Office Hours on Sundays at 6 - 7 pm in North 306

Lectures

French Science 2231 on Mondays and Wednesdays at 1:25 - 2:40 pm

Recitations

Section 01D: Social Sciences 136 on Fridays at 1:25 - 2:40 pm (Kevin)
Section 02D: Sociology Psychology 130 on Fridays at 10:05 - 11:20 am (Nat)
Section 03D: French Science 2231 on Fridays at 1:25 - 2:40 pm (Sam)
Section 04D: Physics 130 on Fridays at 10:05 - 11:20 am (Sam)

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.

Announcements

Synopsis

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

Prerequisites

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

Textbooks

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

Additional References

Grading

Homework

Course Plan

LectureDateTopicScribe NotesReferences
Introduction
1 We 1/10 History of Algorithms; Asymptotic Notation; Worst-case Analysis Notes DPV: 0, 2
KT: 2
CLRS: 1, 2, 3, 4
Algorithm Design Techniques
Mo 1/15 Martin Luther King, Jr. Holiday: No class
We 1/17 School closed due to snow
2 Mo 1/22 Divide and Conquer: Binary Search, Quick Sort, Merge Sort, Integer Multiplication, Linear-time Selection. Notes DPV: 2
KT: 5
CLRS: 4, 7, 8, 9, 28
3 We 1/24
4 Mo 1/29 Greedy Algorithms: Interval Scheduling, Interval Coloring, Fractional Knapsack, Huffman codes Notes DPV: 5
KT: 4
CLRS: 16
5 We 1/31
6 Mo 2/5 Dynamic Programming: Longest Increasing Subsequence, 0-1 Knapsack, Maximal Independent Set on Trees
Notes DPV: 6
KT: 6
CLRS: 15
7 We 2/7
Graph Algorithms
8 Mo 2/12 Graph Representations and Traversal: Depth First Search, Breadth First Search, Applications Notes DPV: 3
KT: 3
CLRS: 22
9 We 2/14
10 Mo 2/19 Shortest Path: Bellman-Ford, Dijkstra, All-Pairs Shortest Paths
Notes DPV: 4.6, 6.6
KT: 6.8
CLRS: 24.1, 25
We 2/21 Midterm 1: Lectures 1-10
11 Mo 2/26 Minimum Spanning Tree: Kruskal, Prim, Union-Find Data Structure Notes DPV: 5
KT: 4
CLRS: 16, 23
12 We 2/28
13 Mo 3/5 Amortization and Potential Method Notes DPV: 5
CLRS: 17
14 We 3/7 Network Flows: Augmenting Paths Algorithm, Max-Flow Min-Cut Theorem Notes DPV: 7
KT: 7
CLRS: 26
Mo 3/12, We 3/14 Spring Break: No Class
15 Mo 3/19 Max Flows (continued from 3/7)
Random Processes: Geometric Random Variables, Coupon Collector
Notes
Randomized Algorithms
16 We 3/21 Random Processes: Birthday Paradox, Monte Carlo and Las Vegas Algorithms Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
17 Mo 3/26
18 We 3/28 Hashing Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
Linear Programming
19 Mo 4/2 LP Formulations, Integer Linear Program Notes CLRS: 29
20 We 4/4 LP Duality Notes CLRS: 29
21 Mo 4/9
We 4/11 Midterm 2: Lectures 11-21
22 Mo 4/16 LP Algorithms, Simplex Algorithms, Separation Oracles
Intractability
23 We 4/18 Complexity Classes P and NP, Polynomial-time Reductions Notes DPV: 8
KT: 8
CLRS: 34
24 Mo 4/23 Approximation Algorithms: Vertex Cover, Set Cover, TSP Notes DPV: 8, 9
KT: 8, 11
CLRS: 34, 35
25 We 4/25
26 TBD Makeup lecture for 1/17 cancelled
Mo 4/30 Final Exam: All Lectures
Time: Monday April 30, 2 - 5 pm

Location: French Science 2231

Recitations

DiscussionDateTopicDiscussion Notes
1 Fr 1/12 Induction, big-Oh notation Notes
2 Fr 1/19
3 Fr 1/26 Divide and Conquer Notes
4 Fr 2/2 Greedy Algorithms Notes
5 Fr 2/9 Dynamic Programming Notes
6 Fr 2/16 All Pairs Shortest Path
7 Fr 2/23 Strongly Connected Components
8 Fr 3/2 MST Algorithms
9 Fr 3/9 Ford-Fulkerson Review; Bipartite Matching
10 Fr 3/23 Resource Contention; Balls and Bins
11 Fr 3/30 Randomized Quicksort Revisited Notes
12 Fr 4/6 LP Duality. Dual Fitting
13 Fr 4/13 Bipartite Matching LP Rounding
14 Fr 4/20 NP-hardness: Longest Path, Dominating Set