Instructor 

Jamie Sikora 

Email: sikora@vt.edu (please include "4104" in the subject line)

Office hours: 

• 9am-11am Wednesdays in Torgersen 2160E (starting Feb 18, see important dates below)

• Immediately after lectures (outside Goodwin Hall 125)

• Other times and Zoom options available upon request

Teaching Assistants

Ankith Mohan (GTA), ankithmo@vt.edu 

Office hours: 1pm-3pm Wednesdays in Torgersen 2030 (starting Feb 04)

Aidan Flinton (GTA), aidanflinton@vt.edu 

Office hours: 12pm-2pm Fridays in Torgersen 2030 (starting Jan 30)

Yoongi Baek (UTA) in Torgersen 1070 (starting Jan 22)

Office hours: 

2:30pm - 5pm Mondays 

3:30pm - 5pm Tuesdays 

11:00am - 1pm Wednesdays

3:30pm - 5pm Thursdays

3:30pm - 6:00pm Fridays

🧑‍🏫 Lectures: Mondays and Wednesdays @ 4:00pm - 5:15pm in Goodwin Hall 125

📑 Syllabus: The rest of the course information can be found in syllabus.pdf  syllabus.tex

🥪 A flyer about food insecurity pdf

• Classes begin: Jan 20 (Jan 21 for this course)

• No lecture (or instructor office hours): Jan 28

• Lectures over Zoom: Feb 02, 04, 09, 11 (link here). (Virtual) instructor office hours available upon request.

• Topic 1 (Stable matchings, algorithm analysis)

  • Assignment 1: out Jan 30, due Feb 13 [2 weeks]

  • Solutions posted Feb 16

  • Test 1: Feb 18 (in class)

• Topic 2 (Graphs, greedy algorithms)

  • Assignment 2: out Feb 20, due Mar 06 [2 weeks]  

  • Spring break: Mar 07-15 (no lectures/office hours)

  • Solutions posted Mar 16 (probably earlier)

  • Test 2: Mar 18 (in class) 

• Topic 3 (Divide and conquer, dynamic programming)

  • Assignment 3: out Mar 20, due Apr 03 [2 weeks]

  • Solutions posted Apr 06 

  • Test 3: Apr 08 (in class) 

• Topic 4 (Network flows)

  • Assignment 4: out Apr 10, due Apr 17 [1 week]  

  • Solutions posted Apr 20 

  • Test 4: Apr 22 (in class) 

• Topic 5 (Intractability)

  • Assignment 5: out Apr 24, due May 01 [1 week]

  • Solutions posted May 04 

  • Test 5: May 06 (in class, last class) 

Introduction   slides 📹

Stable matchings   slides

Algorithm analysis   slides

Graphs   (lecture slides) 

Greedy algorithms I - Scheduling   (lecture slides, job scheduling demo, lecture scheduling demo)

Greedy algorithms II - Shortest paths  (lecture slides, Dijkstra's demo)

Greedy algorithms III - Special trees   (lecture slides, Edmond's branching demo, red-blue algorithms)

Divide and conquer   (lecture slides)

Dynamic programming   (lecture slides) 

Network flows I - Introduction   (lecture slides, Ford-Fulkerson demo)

Network flows II - Applications   (lecture slides)

Intractability I - Reductions   (lecture slides)

Intractability II - NP   (lecture slides)