Spring 2016 - 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.

Administration

Instructor
Debmalya Panigrahi
LSRC D203
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.

Announcements

5/5: The review sessions will be held tonight and tomorrow at 8-10 pm in North 311.
4/25: The deadline for HW6 is extended to the end of Wednesday 4/27.
4/13: The review session will be held tonight at 8-10 pm in LSRC B101.
4/12: Homework 6 is out.
4/12: Professor's office hour is cancelled today, instead Reza has an extra office hour at the same time in N002.
4/10: Homework 4 grades and solutions on Sakai.
4/7: Problem 2 in HW 5 has been changed.
4/6: The due date for Homework 5 changed to 4/19.
4/4: Mikes's office hour (April 5) canceled.
4/4: Jeremy's office hour rescheduled for 12-1 pm tomorrow (Tuesday, April 5) in the Link.
3/29: Homework 5 is out.
3/24: MST scribe note is updated.
3/22: Billy's office hours this Thursday will be 1:30-2:30pm
3/22: Problem 1 of HW4 is updated.
3/20: The deadline for Homework 4 exended to 3/29.
3/11: Homework 4 is out.
2/7: Homework 2 grades and solutions on Sakai.
3/6 Reza's office hour rescheduled for 9-10 am tomorrow (Monday, March 7) in North 002
2/24 Tianqi's office hour rescheduled for 7-8 pm at LSRC B101
2/24 Tianqi's office hour is cancelled due to tornado issue
2/23: Professor's office hour today at 4:30 - 5:30 will be in LSRC D344 instead of his office
2/21: Tianqi's office hour moved to 5:15-6:15 pm tomorrow (Monday, Feb 22).
2/18: Homework 3 is out.
2/18: Homework 1 grades and solutions on Sakai.
2/4: Homework 2 is out.
1/21: Homework 1 is out.
1/13: The recitation moved from Gross 103 to Gross 107.

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 (six): 35%
Midterm exams (two): 35%
Final exam: 30%
Both the midterms and the final exam will be in-class closed-book exams.

Homework

Review the detailed guidelines on collaboration. Any violation of these guidelines will be reported without exception to the relevant authorities.
You will get 50% credit if you submit your homework within one week of the submission deadline, and no credit therefeafter. In exceptional circumstances, you can contact the instructor before the submission deadline to get an extension. Requests for extension are at the discretion of the instructor and can be refused.
We will use Sakai for homework submission.
The homework solutions have to be typed. It is strongly encouraged that you prepare your homework submissions in LaTeX.
Homework solutions must be submitted by 11:59 pm Durham (Eastern) time on the due date.

Schedule

Homework 1 (Lectures 1-5)	released on 1/21	due on 2/4
Homework 2 (Lectures 6-9)	released on 2/4	due on 2/18
Homework 3 (Lectures 10-13)	released on 2/18	due on ~~3/8~~ 3/10
Homework 4 (Lectures 14-17)	released on ~~3/8~~ 3/10	due on ~~3/24~~ 3/29
Homework 5 (Lectures 18-21)	released on ~~3/24~~3/29	due on ~~4/7~~ ~~4/12~~ 4/19
Homework 6 (Lectures 22-25)	released on ~~4/7~~ 4/12	due on ~~4/26~~ 4/27

Course Plan

Lecture	Date	Topic	Scribe Notes	References
		Introduction
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		Notes	DPV: 2 KT: 5 CLRS: 4, 7, 8, 9, 28
4	Tu 1/26	Greedy Algorithms: Fractional Knapsack, Interval Scheduling, Huffman codes	Notes	DPV: 5 KT: 4 CLRS: 16
5	Th 1/28		Notes	DPV: 5 KT: 4 CLRS: 16
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		Notes	DPV: 6 KT: 6 CLRS: 15
		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		Notes	DPV: 3 KT: 3 CLRS: 22
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		Notes	DPV: 7 KT: 7 CLRS: 26
	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	Notes	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	Notes	DPV: virtual chapter KT: 13 CLRS: 5, 11
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	Notes
		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
		Intractability
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 Time: 2-5pm Location: French Science 2231