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)
Week 02 (09/12 - 09/16)
Week 03 (09/19 - 09/23)
Week 04 (09/26 - 09/30)
Week 05 (10/03 - 10/07)
Week 06 (10/12 - 10/14)
Week 07 (10/17 - 10/21)
Week 08 (10/24 - 10/28)
Week 09 (10/31 - 11/04)
Week 10 (11/07 - 11/11)
Week 11 (11/14 - 11/18)
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