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:

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

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/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 DPV: 4
KT: 24, 25
Notes2
13 We 3/1 MST: Prim's and Kruskal's, The Union-Find Data Structure Notes1 KT: 23
Notes2
14 Mo 3/6 The Union-Find data structure and amortized analysis
Network Flows
Notes KT: 7
CLRS: 26
15 We 3/8
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
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 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
Mo 5/1 Final Exam: All Lectures
Time: May 1, 9am-12pm

Location: French Science 2231

Recitations

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