Comp 285: Design and Analysis of Algorithms

Fall 2018

MWF 11:00 to 11:50 in Graham Hall 210

Home Course Info Resources

Instructor

Schedule

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

Lecture Date Description Course Materials
Lecture 1 8/15 Introduction
Concepts: What is a better algorithm?
  • How to design for efficiency?
  • What makes an algorithm correct?
Lecture 2 8/17 Algorithm Analysis
Concepts: Correctness of the Insertion Sort
  • How does the insertion sort work?
  • Proof by induction
Lecture 3 8/20 Algorithm Analysis
Concepts: Insertion Sort runtime analysis
  • Best-Case, Worst-Case and Average-Case analysis
  • What runtime describes a fast algorithm?
Lecture 4 8/22 Divide and Conquer
Concepts:Correctness of MergeSort
  • How does it work?
  • The smart merge sub-algorithm
  • Proof by induction
Lecture 5 8/24 Divide and Conquer
Concepts:MergeSort runtime analysis
  • Proving runtime with recursion trees
  • Proving runtime with the iteration method
  • Proving runtime with the master method
 [HW1 Out]
Lecture 6 8/27 Randomized
Concepts:Correctness of QuickSort
  • Intro to types of random algorithms
  • How does it work?
Lecture 7 8/29 Randomized
Concepts: QuickSort runtime analysis
  • Proving expected runtime
  • Mergesort vs. Quicksort tradeoffs
Lecture 8 8/31 Sorting Lower Bounds
Concepts: Reach linear-time sorting
  • Proving comparison based sorting lower bounds
  • Counting Sort
 Quiz 1 in class
[HW2 Out]
Lecture 9 9/5 Sorting Lower Bounds
Concepts: Reach linear-time sorting
  • Bucket Sort
  • Radix Sort
 [Program 1 Out]
Lecture 10 9/7 Divide and Conquer
Concepts: Median Finding
  • The subsitution method
  • Linear-time selection
 Quiz 2 in class
[HW3 Out]
Lecture 11 9/10 Divide and Conquer
Concepts:Median Finding
  • Take two: median of medians
  • Proving the runtime to reach linear time select
Lecture 12 9/12 Divide and Conquer
Concepts: Recap
  • Patterns in D/C
  • Clever tricks around the median
Lecture 13 9/14 Fundamental Graph Algorithms
Concepts:Graph Intro
  • Why graphs? How do we use them today?
  • Review terms
  • Storage and memory implications
 Quiz 3 in class
[HW4 Out]
Lecture 14 9/17 Fundamental Graph Algorithms
Concepts: DFS
  • How it works
  • Notable applications; e.g. exact travesal
Lecture 15 9/19 Fundamental Graph Algorithms
Concepts: Topological Sort
  • Review DAGs
  • How it works
  • Notable applications
 Program 1 Due
Lecture 16 9/21 Fundamental Graph Algorithms
Concepts: BFS
  • How it works
  • Notable applications; biparte graphs
 Quiz 4 in class
[HW5 Out]
Lecture 17 9/24 Fundamental Graph Algorithms
Concepts: Strongly Connected Components
  • Why we care about SCC
  • Kosaraju’s Algorithm
Lecture 18 9/26 Fundamental Graph Algorithms
Concepts: Strongly Connected Components
  • Metagraph representation
  • Proof of correctness
Lecture 19 9/28 Fundamental Graph Algorithms
Concepts: Dijkstra's
  • The single-source shortest path problem
  • How it works
 Quiz 5 in class
[Review Assignment 1 Out]
Lecture 20 10/1 Fundamental Graph Algorithms
Concepts: Dijkstra's
  • Proof of correctness
  • Data structure runtime impacts
  • Issue with negative weights
Lecture 21 10/3 Dynamic Programming
Concepts: Intro to Dynamic Programming
  • Fibonacci numbers
  • Top down vs bottom up
Lecture 22 10/5 MIDTERM [HW6 Out]
Lecture 23 10/10 Dynamic Programming
Concepts: Bellman Ford
  • Single source shortest path problem with negative weights
  • How it works: the lookup table
Lecture 24 10/12 Dynamic Programming
Concepts: Bellman Ford
  • Proof of correctness
  • Detecting negative cycles
 Quiz 6 in class
[HW7 Out]
Lecture 25 10/15 Dynamic Programming
Concepts: Longest Common Subsequence
  • What is the LCS?
  • Building the recursive formulation​
Lecture 26 10/17 Dynamic Programming
Concepts: Longest Common Subsequence
  • Building an algorithm around the recursive formula
  • How to backtrack and create the solution
 [Program 2 Out]
Lecture 27 10/19 Dynamic Programming
Concepts: Knapsack
  • The Unbounded Knapsack
  • Recursive formulas with a 1D Lookup Table
 Quiz 7 in class
[HW8 Out]
Lecture 28 10/22 Dynamic Programming
Concepts: Knapsack
  • The 0/1 Knapsack
  • Recursive formulas with a 2D Lookup Table
Lecture 29 10/24 Greedy Algorithms
Concepts: Activity Selection
  • Setting up a greedy choice
  • Establishing an optimal substructure
Lecture 30 10/26 Greedy Algorithms
Concepts: Job Scheduling
  • Setting up a greedy choice
  • Establishing an optimal substructure
 Quiz 8 in class
[HW9 Out]
Lecture 31 10/29 Greedy Algorithms
Concepts: Minimum Spanning Tree
  • Defining cuts
  • Prooving the initial lemma
Lecture 32 10/31 Greedy Algorithms
Concepts: Minimum Spanning Tree
  • Prim's Algorithm: How it works
  • Proof of correctness: analysing part way through Prim's
  • A faster prim's implementation
 Program 2 due
Lecture 33 11/2 Greedy Algorithms
Concepts: Minimum Spanning Tree
  • Kruskal’s Algorithm
  • roof of correctness: analysing part way through Kruskal’s
 Quiz 9 in class
[HW10 Out]
Lecture 34 11/5 Network Flow
Concepts: Minimum Cuts
  • Developing Terminology
  • Karger’s Algorithm: SuperVertex and SuperEdges
Lecture 35 11/7 Network Flow
Concepts: Minimum Cuts, Maximum Flow
  • Random algorithm pitfalls and mitigation
  • Establishing terminology
  • Max-Flow Min-Cut theorem
 [Program 3 Out]
Lecture 36 11/9 Network Flow
Concepts: Maximum Flow
  • Max-Flow Min-Cut theorem cont.
  • Ford-Fulkerson algorithm
 Quiz 10 in class
[HW11 Out]
Lecture 37 11/12 Network Flow
Concepts: Maximum Flow
  • Applying max-flow to graphs
  • Exploring applications of max-flow
Lecture 38 11/14 Intractable Problems
Concepts: P vs. NP
  • Establishing terminology (NP, NP-Hard, NP-Complete)
  • 0/1 knapsack revisited: Fixed Parameter Tractability
Lecture 39 11/16 Intractable Problems
Concepts: Traveling Salesman
  • Hamiltonian cycles
  • Traveling salesman runtime implications
 Quiz 11 in class
[HW12 Out]
Lecture 40 11/19 Intractable Problems
Concepts: Vertex Cover
  • Defining maximum matching for vertex cover
  • How it works
 Program 3 due
Lecture 41 11/26 Intractable Problems
Concepts: Reductions
  • Reductions: Set Cover
  • Reduction: Clique
Lecture 42 11/28 Wrap Up
Concepts: Concluding Remarks
  • Looking forward
  • Final Review
 Quiz 12 in class
[Review Assignment 2 Out]
12/6 FINAL EXAM: 8:00 to 10:00 am