Yale CPSC365

Quick Links:

[Discussion & OH] [Schedule] [Calendar] [Problem Sets] [Policies] [Resources] [Staff]

Welcome to the course page for CSPC365 in Spring 2022

Instructor: Dr. Andre Wibisono
Times: Tu/Th 2:30-3:45pm
Classroom: David Auditorium

Announcements

Apr 25: In-class exam on Apr 28 Thur at 2:30pm

Apr 25: Review sessions for the midterm - Check the location and time info below

Course Content

Textbook: Algorithm Design written by Jon Kleinberg and Éva Tardos

Class 1, Tue Jan 25: Introduction
- Reading: Textbook Section 1.1 - 1.2
- Problem set: Pset 1 posted; due Feb 1 @ 2:30pm
- Lecture notes:
  - Lecture Slides
  - Scirbe Notes
- Video: Click to view the recorded lecture

Class 2, Thur Jan 27: Review on Asymptotics and Graphs
- Reading: Textbook Section 1, 2.3-2.5
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Review 0, Fri Jan 28 @ 3:00pm: Review on Logic, Proofs, Math
- Notes: Supplemental Slides about Proofs
- Videos: Click to view the recorded review

Class 3, Tue Feb 1: Stable Matching Problem
- Reading: Textbook Section 3.1
- Problem set:
  - Pset 1 due; submit to Gradescope
  - Pset 2 posted; due Feb 8
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Class 4, Thur Feb 3: Graph explorations
- Reading: Textbook Section 3.2 - 3.6
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Discussion 1, Fri Feb 4:
- Time and links vary; click to view the schedule and the links
- Practice Problems:
  - Discussion 1

Class 5, Tue Feb 8: Depth First-search
- Reading: Textbook Section 3.2 – 3.6
- Problem set:
  - Pset 2 due; submit to Gradescope
  - Pset 3 posted; due Feb 22
- Lectute Notes:
  - Scribe Notes
- Videos: Click to view the recorded lecture

Class 6, Thur Feb 10: Breath-First Search, Shortest path in weighted graph: Dijkstra’s algorithm
- Reading: Textbook Section 3.2 – 3.6
- *Lecture:
  - Scribe Notes
- Videos: Click to view the recorded lecture

Discussion 2, Fri Feb 11:
- Time and location vary; click to view the schedule
- Practice Problems:
  - Discussion 2

Class 7, Tue Feb 15: Proof of Correcteness Dijkstra’s algorithm, Implementation
- Reading: Textbook Section 4.4
- Lecture notes:
  - Scribe Notes
- Videos: Click to view the recorded lecture

Class 8, Thur Feb 17: Minimal Spanning Tree
- Reading: Textbook Section 4.4
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Discussion 3, Fri Feb 18:
- Time and location vary; click to view the schedule
  - Romm change of the session @ 11:00: ML104
- Practice Problems:
  - Discussion 3

Class 9, Tue Feb 22: Divide-and-Conquer 1: Integer Multiplication
- Reading: Textbook Section 5
- Problem set:
  - Pset 4 posted; due Mar 8 @ 2:30 pm
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Class 10, Tur Feb 24: Divide-and-Conquer 2: Mergesort, Master Theorem
- Link to Live Session
- Reading: Textbook Section 5
- Lecture notes:
  - Lecture Slides
  - Scribe notes
- Videos: Click to view the recorded lecture

Discussion 4, Fri Feb 25:
- Time and location vary; click to view the schedule and location info
- Practice Problems:
  - Discussion 4

Class 11, Tue Mar 1: Dynamic Programming 1: Fibonacci, Shortest paths
- Reading: Textbook Section 6
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Special Review Session, Tue Mar 1 @ 4:30 -5:30 pm:
- Click to view the recorded session

Class 12, Thur Mar 3: Dynamic Programming 2: Knapsack, longest increasing subsequence
- Reading: Textbook Section 6
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Discussion 5, Fri Mar 4:
- Time and location vary; click to view the schedule and location info
- Practice Problems:
  - Discussion 5

Class 13, Tue Mar 8: DP 3: Floyd-Warshall, longest increasing subsequence
- Reading: Textbook Section 6
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

In-class Midterm Exam1, Thu Mar 10:
- David Auditorium @ 2:30-3:45
- One page (single-sided) of handwritten cheatsheet allowed

Class 15, Tue Mar 15: Network Flow 1: Max Flow, Min Cut, Ford-Fulkerson
- Reading: Textbook Section 7
- Problem set:
  - Pset 5 posted; due Apr 5 @ 2:30 pm
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- Videos: Click to view the recorded lecture

Class 16, Thur Mar 17: Network Flow 2: Ford-Fulkerson Analysis: Running Time, Correctness
- Reading: Textbook Section 7
- Lecture notes:
- Videos: Click to view the recorded lecture

Class 17, Tue Mar 29: Max-flow/min-cut; proof of correctness of FF
- Link to the live session
- Reading: Textbook Section 7
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- video: Click to view the recorded lecture

Class 18, Thur Mar 30: Bipartite matching, applications
- Link to the live session
- Reading: Textbook Section 7
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- video: Click to view the recorded lecture

Discussion 6, Fri Apr 1:
- Time and location vary; click to view the schedule and location info
- Practice Problems:
  - Discussion 6

Class 19, Tue Apr 5: Complexity 1: Reductions, SAT, 3-SAT, NP
- Reading: Textbook Section 8
- Lecture notes:
  - Lecture 19 + 20
  - Scribe Notes
- video: Click to view the recorded lecture
- Pset : Pset 6 posted; Due is Apr 19 (Sunday) @2:30pm

Class 20, Thur Apr 7: Complexity 2: Examples
- Reading: Textbook Section 8
- Lecture notes:
  - Lecture 19 + 20
  - Scribe Notes
- video: Click to view the recorded lecture
- Pset : Pset 5 due

Discussion 7, Fri Apr 8:
- Time and location vary; click to view the schedule and location info
- Practice Problems:
  - Discussion 7

Class 21, Tue Apr 12: Complexity 3: NP, SAT, 3-SAT
- Reading: Textbook Section 8
- Lecture notes:
  - Scribe Notes
- video: Click to view the recorded lecture

Class 22, Thur Apr 14: Complexity 4: 2-SAT, examples
- Link to live session
- Reading: Textbook Section 8
- Lecture notes:
- video: Click to view the recorded lecture

Discussion 8, Fri Apr 15:
- Time and location vary; click to view the schedule and location info
- Practice Problems:
  - Discussion 8

Class 23, Tue Apr 19: Complexity 5:
- Reading: Textbook Section 8
- Lecture notes:
  - Lecture Slides
  - Scribe Notes
- video: Click to view the recorded lecture
- Pset :
  - Pset 6 due @ 2:30 pm
  - Pset 7 posted; due Apr 26

Class 24, Tue Apr 21: Complexity 6:
- Reading: Textbook Section 8
- Lecture notes:
  - Lecture Slides
- video: Click to view the recorded lecture

Discussion 9, Fri Apr 22:
- Time and location vary; click to view the schedule and location info
  - Nevin’s discussion session @ 12:00pm cancelled
- Practice Problems:
  - Discussion 9

Class 25, Tue Apr 26: Review:
- Lecture notes:
  - Lecture sldies
- video: Click to view the recorded lecture
- Pset: Pset 7 Due

Review Session:
- Michal (ULA): Apr 25 Mon @ 6pm in ML104
- John (TF): Apr 26 Tue @ 4:30 pm in HLH17 05
  - Click to view the recorded session
- Michal (ULA): Apr 27 Wed @ 6pm in BCT CO31
- Alden (ULA): Apr 27 Wed @ 7pm in ML221

In-class Midterm Exam2, Thu Apr 28:
- David Auditorium @ 2:30-3:45
- One page (doubled-sided) of handwritten cheatsheet allowed