COSC 311: Algorithms
course materials for Fall 2022
Welcome to the Fall 2022 edition of COSC 311: Algorithms!. Course materials and assignments will be posted to this website. Please start by reading the course syllabus:
Meetings
- Lecture 01: MWF 11:00–11:50 Mead 115
- Lecture 02: MWF 2:00–2:50 SCCE A131
- Drop-in Office Hours
- Thursday, 11:00–12:00 in King & Wieland Quad, Tent 2
- Thursday, 2:30–3:30 in King & Wieland Quad, Tent 2
- Office Hours by Appointment (sign up here)
- Wednesday, 3:00–4:00 in SCCE C216 and on Zoom
- TBD
- Evening TA Sessions:
- Sunday, 5:00–7:00 pm in SCCE A131
- Wednesday, 7:00–9:00 pm in SCCE A131
Resources
Recommended Texts (choose one):
- Algorithms Illuminated (Volumes 1–4), Roughgarden (AI)
- Algorithm Design, Kleinberg and Tardos (KT)
- Algorithms in Action, Savvich (AA)
Additional notes and readings will be posted to this website.
Lecture Materials and Tickets
Week 01 (09/02 - 09/09)
- Lecture 01 (09/02)
- topics: course introduction, sorting
- readings: course syllabus
- lecture ticket: read the course syllabus
- lecture 01 slides (annotated PDF forthcoming)
- Lecture 02 (09/05)
- topics: sorting and induction
- readings: pseudocode (course notes)
- lecture 02 ticket (pdf format) (.tex source)
- lecture 02 slides (annotated pdf version)
- Lecture 03 (09/07)
- topics: more on induction, asymptotic notation
- readings: induction
- do lecture 02 ticket (if you haven’t already)
- lecture 03 slides (annotated pdf version)
- Lecture 04 (09/09)
- topics: sorting by divide and conquer
- readings: asymptotic analysis
- lecture 04 ticket (pdf format) (.tex source)
Week 02 (09/12 - 09/16)
- Lecture 05 (09/12)
- topics: sorting by divide and conquer
- readings: learn about MergeSort, e.g. in
- AI Sections 1.4–5
- KT Section 5.1
- lecture 05 ticket (pdf format) (.tex source)
- lecture 05 slides (annotated pdf version)
- Lecture 06 (09/14)
- topics: more sorting by divide and conquer
- readings: nothing new!
- lecture 06 ticket (pdf format) (.tex source)
- Lecture 07 (09/16)
- topics: QuickSort
- readings: nothing new!
- Assignment 01 due (no lecture ticket)
- lecture 07 slides (annotated pdf version)
Week 03 (09/19 - 09/23)
- Lecture 08 (09/19)
- topics: lower bound for sorting
- readings: nothing new!
- lecture 08 ticket (pdf format) (.tex source)
- lecture 08 slides (annotated pdf version)
- Lecture 09 (09/21)
- topics: RadixSort
- readings: Binary Representation
- lecture 09 ticket (pdf format) (.tex source)
- lecture 09 slides (annotated pdf version)
- Lecture 10 (09/23)
- topics: Multiplication by Divide and Conquer
- readings (pick one):
- AI 1.2–3 Integer Multipication and Karatsuba Multiplication
- KT 5.5 Integer Multiplication
- AA 5.2 Integer Multiplication
- lecture 10 ticket (pdf format) (.tex source)
- lecture 10 slides (annotated pdf version)
Week 04 (09/26 - 09/30)
- Lecture 11 (09/26)
- topics: Master Method and Maximization
- readings: none required; optional reading: Mathematicians Discover the Perfect Way to Multiply from Quanta Magazine
- no lecture ticket
- lecture 11 slides (annotated pdf version)
- Lecture 12 (09/28)
- topics: More Recursion Relations; Maximization
- readings: pick one
- AI 4.1–2 The Master Method
- The master method for solving recurrences from Introduction to Algorithms by Cormen et al.
- AA 5.1 Solving Divide-and-Conquer Recurrences
- lecture 12 ticket (pdf format) (.tex source)
- lecture 12 slides (annotated pdf version)
- Lecture 13 (09/30)
- topics: Graphs, Bridges of Königsberg problem, Eulerian circuits
- no lecture ticket (Assignment 02 due)
- lecture 13 slides (annotated pdf version)
Week 05 (10/03 - 10/07)
- Lecture 14 (10/03)
- topics: Graphs, Breadth-first Search, Shortest Paths
- readings: none
- no lecture ticket
- lecture 14 slides (annotated pdf version)
- Lecture 15 (10/05)
- topics: Finishing BFS
- readings:
- no lecture ticket
- lecture 15 slides (annotated pdf version)
- Midterm 1 (10/07)
- In class
- Midterm I Guide
Week 06 (10/12 - 10/14)
- Lecture 16 (10/12)
- topics: Dijkstra’s algorithm
- readings:
- AI 9.1–3 Dijkstra’s Shortest-Path Algorithm
- KT 4.4 Shortest Paths in a Graph
- AA 4.5 Shortest Path Problem
- no lecture ticket
- lecture 16 slides (annotated pdf version)
- Lecture 17 (10/14)
- topics: Efficient Dijkstra implementation; minimum spanning trees
- readings:
- AI 10 The Heap Data Structure
- KT 2.5 A More Complex Data Structure: Priority Queues
- AA 3.1 Binary Heaps
- lecture 17 ticket (pdf format) (.tex source)
- lecture 17 slides (annotated pdf version)
Week 07 (10/17 - 10/21)
- Lecture 18 (10/17)
- topics: Minimum Spanning Trees, Prim’s Algorithm
- readings:
- AI 15.1-4 Minimum Spanning Trees
- KT 4.5 The Minimum Spanning Tree Problem
- AA 4.4 Minimum Spanning Trees
- no lecture ticket
- lecture 18 slides (annotated pdf version)
- Lecture 19 (10/19)
- topics: MST, Kruskal’s Algorithm
- readings:
- AI 15.5-7 Minimum Spanning Treees
- KT 4.5 The Minimum Spanning Tree Problem
- AA 4.4 Minimum Spanning Trees
- no lecture ticket
- lecture 19 slides (annotated pdf version)
- Lecture 20 (10/21)
- topics: Interval Scheduling
- readings:
- AI 13 Introduction to Greedy Algorithms
- KT 4.1 Interval Scheduling
- AA 4.2 Scheduling Problem
- Homework 03 due today (no ticket)
- lecture 20 slides (annotated pdf version)
- lecture 20b slides (annotated pdf version)
- analysis of merging in Kurskal’s algorithm
Week 08 (10/24 - 10/28)
- Lecture 21 (10/24)
- topics: Interval Scheduling
- readings:
- AI 13 Introduction to Greedy Algorithms
- KT 4.1 Interval Scheduling
- AA 4.2 Scheduling Problem
- no lecture ticket
- lecture 21 slides (annotated pdf version)
- Lecture 22 (10/26)
- topics: Dynamic Programming Intro, Profit Maximization
- readings: none
- no lecture ticket
- lecture 22 slides (annotated pdf version)
- Lecture 23 (10/28)
- topics: Weighted Interval Scheduling
- readings:
- AI 16.1–4 Introduction ot Dynamic Programming
- KT 6.1 Weighted Interval Scheduling
- AA 6.1 Introduction to Dynamic Programming
- no lecture ticket (Assignment 04 due)
- lecture 23 slides (annotated pdf version)
Week 09 (10/31 - 11/04)
- Lecture 24 (10/31)
- topics: Weighted Knapsack Problem
- readings:
- AI 16.5 The Knapsack Problem
- KT 6.4 Subset Sums and Knapsacks
- AA 6.2 Knapsack Problem
- no lecture ticket
- lecture 24 slides (annotated pdf version)
- Lecture 25 (11/02)
- topics: Sequence Alignment/Longest Common Subsequence
- readings:
- AI 17.1 Sequence Alignment
- KT 6.6 Sequence Alignment
- lecture ticket
- lecture 25 slides (annotated pdf version)
- Lecture 26 (11/04)
- topics: Finishing Sequence Alignment
- no lecture ticket
- lecture 26 slides (annotated pdf version)
Week 10 (11/07 - 11/11)
- Lecture 27 (11/07)
- topics: Shortest Paths & Bellman-Ford
- readings:
- AI 18.1-2 Shortest Paths Revisited
- KT 6.8 Shortest Paths in a Graph
- AA 6.4 The Bellman Ford Algorithm
- lecture ticket (not to be turned in)
- lecture 27 slides (annotated pdf version)
- Lecture 28 (11/09)
- topics: Finishing Bellman-Ford, Starting Maximum Flow
- lecture 28 slides (annotated pdf version)
- Lecture 29 (11/11)
- topics: Maximum Flow
- readings:
- KT 7.1 The Maximum Flow Problem and the Ford-Fulkerson Algorithm
- AA 7.1–2 Network Flow
- lecture 29 slides (annotated pdf version)
Week 11 (11/14 - 11/18)
- Lecture 30 (11/14)
- topics: Ford-Fulkerson Correctness
- readings:
- KT 7.2 Maximum Flows and Minimum Cuts in a Network
- lecture 30 slides (annotated pdf version)
- Midterm 2 (11/16)
- Lecture 31 (11/18)
- topics: Stable Matchings
- readings:
- KT 1.1 Stable Matchings
- College Admissions and the Stability of Marriage by Gale and Shapley
- lecture 31 slides (annotated pdf version)
Week 12 (11/28 - 12/02)
- Lecture 32 (11/28)
- topics: Reductions, Maximum Bipartite Matching
- readings:
- KT 7.5 The Bipartite Matching Problem
- no lecture ticket
- lecture 32 slides
- Lecture 33 (12/02)
- topics: Reductions and Hardness
- readings:
- KT 8.1 Polynomial Time Reductions
- no lecture ticket
- lecture 33 slides
Week 13 (11/05 - 12/09)
- Lecture 34 (12/05)
- topics: NP Completeness
- readings:
- KT 8.3 Efficient Certification and the Definition of NP
- AA 9.1–2 NP Completeness
- AI 19 What is NP Hardness?
- lecture 34 ticket
- lecture 34 slides
- Lecture 35 (12/07)
- topics: NP Complete Problems
- Lecture 36 (12/09)
- topics: Coping with Intractability
Assignments
- Assignment 01 (Due: 09/16)
- Assignment 02 (Due: 09/30)
- Assignment 03 (Due:
10/1410/23) - Assignment 04 (Due: 10/28)
- Assignment 05 (Due: 11/11)
- Assignment 06 (Due: 12/09)