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:

provide basic training in algorithm design for a future computer scientist and/or programmer, and
expose future professionals in other disciplines to fundamental algorithmic paradigms.

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

Nat will hold extra office hours on 4/26 at 5 - 8 pm, and Kevin will hold extra office hours on 4/27 at 3 - 6 pm, both in North 306.
There will be no office hours on 4/25, due to LDOC. Instead, Kevin, Aninda, and Erin will have office hours on 4/24 at 4:30 - 6:30 pm in North 306 (the usual room).
Kevin and Nat will be holding extra office hours on Tuesday 3/20 at 6 - 9 pm, in North 306.
In addition to his usual office hour (on 3/19), Prof. Panigrahi will have an office hour on Wednesday 3/21 at 3 - 4 pm.
Prof. Panigrahi will not have office hours on 3/5.
Prof. Panigrahi will not have office hours on 2/26. Instead, Kevin's office hours on 2/26 will start at 3:30 pm, in North 306.
Kevin's 1/29 office hour (4 - 5 pm) will be moved to 25 minutes before and after his recitation on 1/26, in Social Sciences 136.
Due to the school closings, the due date for Homework 1 has been changed from 1/22 to 1/24.
In case any of you cannot access Sakai or Piazza, please email Kevin (ksun@cs.duke.edu) or Nat (kell@cs.duke.edu) immediately.
No class on Monday 1/15 because of MLK day (university holiday).

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:

Introduction: History of Algorithms, Asymptotic and Worst-case Analysis
Algorithm Design Techniques: Divide and Conquer (Recurrences), Dynamic Programming and Memoization, Greedy Algorithms
Graph Algorithms: Graph Representations, Graph Traversal and Applications, Shortest Path, Minimum Spanning Tree, Network Flows
Data Structures: Amortization and Potential Functions, Union-Find
Computational Geometry: Convex hull
Randomized Algorithms: Monte Carlo and Las Vegas Algorithms, Hashing
Linear Programming: Simplex Algorithms, LP Duality
Intractability: P and NP, NP-completeness, Polynomial-time Reductions, Approximation Algorithms

Prerequisites

There are two hard prerequisites (equivalent courses are also acceptable):

COMPSCI 201 Data Structures and Algorithms
COMPSCI 230 Discrete Math for Computer Science

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:

[DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw Hill, 2006.
[KT] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.

Additional References

[AHU] A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley 1974.
[Ed] H. Edelsbrunner. CPS230 Lecture Notes. Duke University, 2008.
[Er] J. Erickson. CPS473G: Algorithms Lecture Notes. UIUC.
[Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.

Grading

Homework Assignments (11 required (need to be submitted) + 1 for practice (should not be submitted)): 35%
Midterm exams (two): 35%
Final exam: 30%
Both the midterms and the final exam will be in-class closed-book exams.

Homework

Collaborations and Honesty: Review the detailed guidelines on collaboration. Any violation of these guidelines will be reported without exception to the relevant authorities. This has led to disciplinary action in the past, so better be safe than sorry.
Late Submissions: Homework solutions must be submitted by 11:59 pm Durham (Eastern) time on the due date. You will get no credit if you submit your homework after the submission deadline. A submission will be considered late if the submission website (Sakai) marks it as late. This means that it is in your best interest to submit sufficiently early so that there is no possibility of the Sakai server receiving it after 11:59 pm.
Extensions: In exceptional circumstances, you can contact the instructor before the submission deadline to request an extension. You should send an email to the instructor if you are requesting an extension, with a clearly stated reason for your request. Requests for extension are at the discretion of the instructor and may be refused. This implies that last-minute requests for extension are at your own peril, since the original deadline will stand if the request is denied. Only the written consent of the instructor granting an extension will be considered valid. Nobody other than the instructor (TA, UTA, etc.) is authorized to grant an extension.
Submission Website: We will use Sakai for homework submission.
Submission Format: The homework solutions have to be typed. It is strongly encouraged that you prepare your homework submissions in LaTeX.

Schedule

Homework 1	released on 1/15	due on ~~1/22~~ 1/24
Homework 2	released on 1/22	due on 1/29
Homework 3	released on 1/29	due on 2/5
Homework 4	released on 2/5	due on 2/12
Homework 5	released on 2/12	due on 2/26
Homework 6	released on 2/26	due on 3/5
Homework 7	released on ~~3/5~~ 3/6	due on ~~3/19~~ 3/21
Homework 8	released on 3/19	due on 3/26
Homework 9	released on 3/26	due on 4/2
Homework 10	released on 4/2	due on ~~4/16~~ 4/18
Homework 11	released on ~~4/16~~ 4/17	due on 4/25
Homework 12	released on ~~4/25~~ 4/24	Optional

Course Plan

Lecture	Date	Topic	Scribe Notes	References
		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		Notes	DPV: 2 KT: 5 CLRS: 4, 7, 8, 9, 28
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		Notes	DPV: 5 KT: 4 CLRS: 16
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		Notes	DPV: 6 KT: 6 CLRS: 15
		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		Notes	DPV: 3 KT: 3 CLRS: 22
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		Notes	DPV: 5 KT: 4 CLRS: 16, 23
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		Notes	DPV: virtual chapter KT: 13 CLRS: 5, 11
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	LP Duality	Notes	CLRS: 29
	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	Approximation Algorithms: Vertex Cover, Set Cover, TSP	Notes	DPV: 8, 9 KT: 8, 11 CLRS: 34, 35
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

Discussion	Date	Topic	Discussion Notes
1	Fr 1/12	Induction, big-Oh notation	Notes
2	Fr 1/19	Induction, big-Oh notation	Notes
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