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

Lectures

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

Recitations

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.

Announcements

There is an additional instructor office hour on Apr26 2:30pm.
Homework deadline policy is updated again. Please check the corresponding section for details.
Homework deadline policy has changed. Please check the corresponding section for details.
TA and UTA office hours have been updated. Please check the corresponding section for details.
In case any of you cannot access Sakai, please email your homework together with your name and NetID to Abe (abef@cs.duke.edu) or Tianyu (tianyu@cs.duke.edu) before the deadline.
No class on 1/16 because of MLK day (university holiday).
The instructor will be away on 1/18. The lecture will be given by a guest lecturer.

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 + 1 optional): 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/11	due on 1/18
Homework 2	released on 1/18	due on 1/25
Homework 3	released on 1/25	due on 2/1
Homework 4	released on 2/1	due on 2/8
Homework 5	released on 2/8	due on 2/15
Homework 6	released on 2/15	due on 2/27
Homework 7	released on 2/27	due on 3/6
Homework 8	released on 3/6	due on 3/22
Homework 9	released on 3/22	due on 4/3
Homework 10	released on 4/3	due on 4/17
Homework 11	released on 4/17	due on ~~4/24~~ 4/26
Homework 12	released on 4/26	Optional

Course Plan

Lecture	Date	Topic	Scribe Notes	References
		Introduction
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		Notes	DPV: 2 KT: 5 CLRS: 4, 7, 8, 9, 28
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		Notes	DPV: 5 KT: 4 CLRS: 16
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		Notes	DPV: 6 KT: 6 CLRS: 15
		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	DPV: 4 KT: 24, 25
12	Mo 2/27	Shortest Path: Dijkstra's and Bellman-Ford; MST properties	Notes2	DPV: 4 KT: 24, 25
13	We 3/1	MST: Prim's and Kruskal's, The Union-Find Data Structure	Notes1	KT: 23
13	We 3/1	MST: Prim's and Kruskal's, The Union-Find Data Structure	Notes2	KT: 23
14	Mo 3/6	The Union-Find data structure and amortized analysis Network Flows	Notes	KT: 7 CLRS: 26
15	We 3/8		Notes	KT: 7 CLRS: 26
	Tu 3/13, Th 3/15	Spring Break: No Class
16	Mo 3/20	Maxmimum flow and minimum cut	Notes	KT: 7 CLRS: 26
		Randomized Algorithms
17	We 3/22	Monte Carlo algorithms	Notes	DPV: virtual chapter KT: 13 CLRS: 5, 11
18	Mo 3/27	Las Vegas algorithms	Notes	DPV: virtual chapter KT: 13 CLRS: 5, 11
19	Mo 3/29	Hashing (and preliminaries of prime field)	Notes	DPV: virtual chapter KT: 13 CLRS: 5, 11
20	Mo 4/3	Hashing (and preliminaries of prime field)	Notes	DPV: virtual chapter KT: 13 CLRS: 5, 11
		Linear Programming
20	Mo 4/3	LP Formulations, Integer Linear Program	Notes	DPV: 7 CLRS: 29
21	We 4/5	LP Duality	Notes	DPV: 7 CLRS: 29
22	Mo 4/10	LP Algorithms, Simplex Algorithms, Separation Oracles	Notes	DPV: 7 CLRS: 29
	We 4/12	Midterm 2: Lectures 12-22
23	Mo 4/17	Separation Oracles, Ellipsoid algorithms	Notes	DPV: 7 CLRS: 29
24	We 4/19	LP continued: Separation Oracles, Integrality Gap, Interior Point Methods	Notes	DPV: 7 CLRS: 29
		Intractability
25	Mo 4/24	Complexity: P, NP and NP-Hardness, Polynomial time reduction	Notes	DPV: 8, 9 KT: 8, 11 CLRS: 34, 35
26	We 4/26	Approximation algorithms	Notes	DPV: 8, 9 KT: 8, 11 CLRS: 34, 35
	Mo 5/1	Final Exam: All Lectures Time: May 1, 9am-12pm Location: French Science 2231

Recitations

Discussion	Date	Topic	Discussion 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
9	Fr 3/31	Randomized Quicksort and Collision Handling	Notes
10	Fr 4/7	LP Duality	Notes
11	Fr 4/14	LP Separation Oracle example	Notes