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

##### Final Exam

The final exam for *Algorithms* will be held in **SCCE E110 on Friday, December 16th from 9:00 am to 12:00 pm**.

Here is a Final Exam Guide including practice problems for the exam.

##### 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 (annotated pdf version)

- Lecture 33 (12/02)
- topics: Reductions and Hardness
- readings:
**KT**8.1*Polynomial Time Reductions*

- no lecture ticket
- lecture 33 slides (annotated pdf version)

**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 (annotated pdf version)

- Lecture 35 (12/07)
- topics: NP Complete Problems
- lecture 35 slides (annotated pdf version)

- Lecture 36 (12/09)
- topics: Coping with Intractability
- lecture 36 slides (annotated pdf version)

##### Assignments

- Assignment 01 (Due: 09/16)
- Assignment 02 (Due: 09/30)
- Assignment 03 (Due:
~~10/14~~10/23) - Assignment 04 (Due: 10/28)
- Assignment 05 (Due: 11/11)
~~Assignment 06 (Due: 12/09)~~See practice exam questions (not to be turned in)