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 - 8pm in North 306

Kevin Sun
North 003
Email: ksun@cs.duke.edu
Office Hours on Mondays at 4 - 5 pm and Wednesdays at 4 - 5pm 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 Notes DPV: 5
KT: 4
CLRS: 16, 23
12 We 2/28 Amortization, Potential Method: The Union-Find Data Structure Notes
13 Mo 3/5
14 We 3/7 Network Flows and Matchings: Maxflow Mincut Theorem, Augmenting Paths Notes DPV: 7
KT: 7
CLRS: 26
Mo 3/12, We 3/14 Spring Break: No Class
15 Mo 3/19 Continued from 3/7
Randomized Algorithms
16 We 3/21 Random processes: Birthday Paradox, Coupon Collector, Balls in Bins Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
17 Mo 3/26 Hashing Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
18 We 3/28 Las Vegas and Monte Carlo Algorithms Notes DPV: virtual chapter
KT: 13
CLRS: 5, 11
19 Mo 4/2
Linear Programming
20 We 4/4 LP Formulations, Integer Linear Program 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
Other Topics
25 We 4/25 Computational Geometry: Convex Hull Algorithms
Notes CLRS: 33
26 TBD Makeup lecture for 1/17
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
7 Fr 2/23 DFS and BFS Notes
8 Fr 3/2 Shortest Path Notes
9 Fr 3/9
10 Fr 3/23
11 Fr 3/30 Probability Notes
12 Fr 4/6 Randomized Quicksort and Collision Handling Notes
13 Fr 4/13 LP Duality Notes
14 Fr 4/20 LP Separation Oracle example Notes