Comp 285: Design and Analysis of Algorithms

Fall 2019

MW 11:00 to 12:15 pm in McNair 239

Home Course Info Resources

Instructor

Schedule

Navigate to a topic: Algorithm Analysis | Divide and Conquer | Sorting Lower Bounds | Fundamental Graph Algorithms | Greedy Algorithms | Dynamic Programming | Network Flow | Intractable Problems

Lecture Date Description Course Materials
Lecture 1 8/21 Introduction
Concepts: What is a better algorithm?
  • How to design for efficiency?
  • What makes an algorithm correct?
  • Preliminary Assessment
Lecture 2 8/26 Algorithm Analysis
Concepts: Explore core concepts via the InsertionSort
  • Proofs by induction
  • Big-O Analysis: worst-case and best-case analysis
  • Practice: Explore runtimes of various looping structures
Lecture 3 8/28 Divide and Conquer
Concepts: Introduction to Divide and Conquer
  • Why is BinarySearch O(log(n))?
  • Recurrence relations and the Master Method
  • Together: Find the only non-duplicate
  • Whiteboarding: Find the only duplicate
 [HW1 Out] Due: 9/3
- 9/2 No Class: Labor Day
Lecture 4 9/4 Divide and Conquer
Concepts: MergeSort and Its Applications
  • Proving MergeSort by Induction
  • Together: Counting Inversions
  • Whiteboarding: A more significant inversion
 Quiz 1 in class
[HW2 Out] Due: 9/10
Lecture 5 9/9 Divide and Conquer
Concepts: Whiteboarding Problem Session
  • Find the peak element
  • Count number of occurrences
  • Find the majority element
  • Find the median of two arrays
 [Program 1 Out]
Lecture 6 9/11 Sorting Lower Bounds
Concepts: Reaching linear-time sorting
  • Comparison-based sorting lower bounds
  • Counting Sort, Bucket Sort, and Radix Sort
  • Whiteboarding: Sorting variable lengths efficiently
 Quiz 2 in class
[HW3 Out] Due: 9/17
Lecture 7 9/16 Fundamental Graph Algorithms
Concepts: DFS Applications
  • Review: DFS and DFS Trees
  • Directed Acyclic Graphs
  • Topological Order
  • Whiteboarding: Finding articulation points
 [Program 1 Design Document Due]
Lecture 8 9/18 Fundamental Graph Algorithms
Concepts: BFS Applications
  • Review: BFS and BFS Trees
  • Shortest Paths in Unweighted Graphs
  • Bipartite Graphs
  • Whiteboarding: Six degrees of Kevin Bacon, Fishy peace
 Quiz 3 in class
[HW4 Out] Due: 9/24
[Program 1 Test Cases Due]
Lecture 9 9/23 Fundamental Graph Algorithms
Concepts: Whiteboarding Problem Session
  • Exam 1 Review
  • Weighted Shortest Paths Using BFS
  • Forming Teams
  • Arranging Children in Rows
 [Review Assignment 1 Out]
Lecture 10 9/25 Greedy Algorithms
Concepts: Dijkstra's
  • What is a greedy algorithm?
  • Understanding Dijkstra's Algorithm
  • Proving Dijkstra's
  • Whiteboarding: Paths through a Garden
 Quiz 4 in class
[Program 1 Code Due]
[Program 1 Reflection Due]
Lecture 11 9/30 Greedy Algorithms
Concepts: Minimum Spanning Trees
  • Prim's Algorithm
  • Slow vs Fast Prim's
  • Kruskal’s Algorithm
- 10/2 Exam 1 [HW5 Out] Due: 10/8
Lecture 12 10/7 Greedy Algorithms
Concepts: Further exploring greedy algorithms
  • Activity Selection
  • Job Scheduling
  • Whiteboarding: Filling Minimal CDs
Lecture 13 10/9 Greedy Algorithms
Concepts: Whiteboarding Problem Session
  • Making Change
  • Scheduling a Triathlon
  • Program 2 Discussion
 Quiz 5 in class
[HW6 Out] Due: 10/15
[Program 2 Out]
- 10/14 Fall Break
Lecture 14 10/16 Dynamic Programming
Concepts: Top Down vs. Bottom Up
  • Fibonacci Numbers 3 Ways
  • Building Recursive Formulations
  • Whiteboarding: Climbing Stairs
 Quiz 6 in class
[HW7 Out] Due: 10/22
Lecture 15 10/21 Dynamic Programming
Concepts: Unbounded Knapsack
  • 1D Dynamic Programming
  • Translating recursive formulas to code
  • Whiteboarding: Making Change, DP Approach
 [Program 2 Test Cases Due]
Lecture 16 10/23 Dynamic Programming
Concepts: 0/1 Knapsack
  • 2D Dynamic Programming
  • Tracking additional information
 Quiz 7 in class
[HW8 Out] Due: 10/29
[Program 2 Design Document Due]
- 10/28 Googley Day
Concepts: What do CS majors do in the real world?
  • Guest 1: Riley Porter, SWE at Google
  • Guest 2: Adrienne Posner, PM at Google
 [Program 2 Code Due]
[Program 2 Reflection Due]
Lecture 17 10/30 Dynamic Programming
Concepts: Bellman Ford
  • Last SSSP Algorithm
  • Detecting Negative Cycles
  • Optimizing the Implementation
 Quiz 8 in class
Lecture 18 11/04 Dynamic Programming
Concepts: Whiteboarding Problem Session
  • Program 3 Breakdown
  • Planning a Company Party
  • End of the Semester Planning
 [Program 3 Out]
- 11/06 Exam 2 [HW9 Out] Due: 11/12
Lecture 19 11/11 Network Flow
Concepts: Min-Cut
  • Monte Carlo randomized algorithm
  • Karger’s Algorithm
  • Dealing with incorrect outputs
Lecture 20 11/13 Network Flow
Concepts: Max-Flow, Min-Cut
  • What is a flow?
  • Ford-Fulkerson Algorithm
  • Augmenting path
 Quiz 9 in class
[HW10 Out] Due: 11/19
[Program 3 Test Cases Due]
Lecture 21 11/18 Network Flow
Concepts: Deeper look at augmenting path
  • Updating forward edges
  • Updating backward edges
  • Stepping over example graphs
 [Program 3 Design Document Due]
Lecture 22 11/20 Network Flow
Concepts: Whiteboarding Problem Session
  • Applications of Max-Flow, Min-Cut
  • Sending supplies
  • Load balancing hospitals
  • Deleting edge and updating Max-Flow
 Quiz 10 in class
[HW11 Out] Due: 12/1
Lecture 23 11/25 Intractable Problems
Concepts: NP, NP-Complete
  • Terminology
  • Traveling Salesman Problem
  • 0/1 Knapsack, revisited
  • Vertex Cover
 [Program 3 Code Due]
[Program 3 Reflection Due]
- 11/27 Thanksgiving Break!
Lecture 24 12/2 Intractable Problems
Concepts: NP-Complete Reductions
  • Set-Cover
  • Set Partition
 Quiz 11 in class
[Review Assignment 3 Out] Due: 12/12
Lecture 25 12/4 Intractable Problems
Concepts: Whiteboarding Session
  • Collecting Baseball Cards
  • 2019-colorability
  • A Potentially Intractable Problem
  • End of semester wrap-up
- 12/12 Exam 3