Fall 2011 schedule (Previous schedules: 2009, 2010).

Date Topic Blogger ScribeNotes
Mon, Aug 29 Introduction (Slides [17.9 MB]) Atri Rudra (HW 0 out)
Wed, Aug 31 Main steps in Algorithm Design (Slides [22.2MB]) Atri Rudra
Fri, Sep 2 Stable Marriage Problem (Slides [3.8MB]) Atri Rudra [KT, Sec 1.1] (HW 0 in)
Mon, Sep 5 No Class Labor Day
Wed, Sep 7 Gale-Shapley Algorithm (Slides [5.2MB]) Bethany Griswold
Wembley Leach
Patrick Lapinski
Sheldon Ooi
[KT, Sec 1.1]
Fri, Sep 9 Analysis of the GS Algorithm-I (Slides [2MB]) Sheldon Ooi
Patrick Lapinski
Bethany Griswold
Wembley Leach
[KT, Sec 1.1] (HW 1 out)
Mon, Sep 12 Analysis of the GS Algorithm-II (Slides [1MB]) Peter Turner
Sean Zawicki
Dominic Baratta
Alex Vertlieb
[KT, Sec 1.1]
Reading: [KT, Sec 1.2, 2.1, 2.2, 2.4]
Wed, Sep 14 Asymptotic Analysis (Slides [5.1MB]) Dominic Baratta
Brian Feuerstein
Peter Turner
Robert Wesolowski
[KT, Sec 2.1, 2.2]
Fri, Sep 16 Runtime Analysis (Slides [2.8MB]) Brian Rizzo
William Wheeler
Max Bileschi
Joanna Krzywda
[KT, Sec 2.2] (HW 1 in, HW 2 out)
Mon, Sep 19 Runtime analysis of the GS algorithm (Slides [2.7MB]) Joanna Krzywda
Alex Vertlieb
William Wheeler
Sean Zawicki
[KT, Sec 2.3]
Wed, Sep 21 Graph Basics (Slides [6MB]) Max Bileschi
Priyanka Wagh
Rick Dombkiewicz
Brian Rizzo
[KT, Sec 2.3, 3.1]
Reading: [KT, Sec 1.1, Chap. 2]
Fri, Sep 23 Trees (Slides [2.6MB]) Alyssa Buzzard
Robert Wesolowski
Priyanka Wagh
Xicheng Wang
[KT, Sec 3.1] (HW 2 in, HW 3 out)
Mon, Sep 26 Breadth First Search (Slides [3.1MB]) Timothy Hemingway
Xicheng Wang
Sarah Jordan
Alexander Simeonov
[KT, Sec 3.2]
Wed, Sep 28 Correctness of BFS (Slides [1.7MB]) Elvis Castelino
Sarah Jordan
Alyssa Buzzard
Timothy Hemingway
[KT, Sec 3.2]
Fri, Sep 30 DFS and Graph Representation (Slides [5.1MB]) Ryan Brown
Solomon Karchefsky
Elvis Castelino
Jonathan Filipski
[KT, Sec 3.2, 3.3] (HW 3 in, HW 4 out)
Reading: [KT, Sec 3.2]
Mon, Oct 3 Implementation of BFS (Slides [5.8MB]) Chaw Khaing
Alexander Simeonov
Ryan Brown
Solomon Karchefsky
[KT, Sec 3.3]
Reading: [KT, Sec 3.3, 3.4, 3.5]
Wed, Oct 5 Topological Ordering (Slides [5.9MB]) Jonathan Filipski
Sugandha Sharma
Matthew Elling
Alex Maxon
[KT, Sec 3.6]
Fri, Oct 7 Algorithm for Topological Ordering (Slides ([2.3MB]) Alex Maxon
Gagan Singh
John Gerber
Sugandha Sharma
[KT, Sec 3.6](HW 4 in)
Mon, Oct 10 Mid term exam In class
Wed, Oct 12 Greedy Algorithms (Slides [3.2MB]) Matthew Elling
Bryan Johnson
Brian Feuerstein
Chaw Khaing
[KT, Sec 4.1]
Fri, Oct 14 Interval Scheduling (Slides [.7MB]) Joe Battaglia
Rick Dombkiewicz
Bryan Johnson
Carl Nuessle
[KT, Sec 4.1](HW 5 out)
Mon, Oct 17 Scheduling to Minimize Lateness (Slides) Spencer Brigham
Ryan Lombardo
Joe Battaglia
Richard Doell
[KT, Sec 4.2]
Reading: [KT, Sec 4.1]
Wed, Oct 19 Earliest Deadline First Algorithm (Slides [.4MB]) Rohit Godani
Michael LoBocchiaro
Jordan Dawson
Gagan Singh
[KT, Sec 4.2]
Fri, Oct 21 Analyzing the Earliest Deadline First Algorithm (Slides [.4MB]) Kris Feeley
Scott Haseley
Philip Rosebrough
Benjamin Tapio
[KT, Sec 4.2] (HW 5 in, HW 6 out)
Mon, Oct 24 Shortest Path Problem (Slides [4.6 MB]) John Gerber
Carl Nuessle
Scott Haseley
Michael LoBocchiaro
[KT, Sec 4.4]
Reading: [KT, Sec 2.5]
Wed, Oct 26 Dijkstra's Algorithm (Slides [4.4MB]) Xiang Lin
Junfei Wang
Andrew Castaldi
Rohit Godani
[KT, Sec 4.4]
Fri, Oct 28 Minimum Spanning Tree Problem (Slides [1.9MB]) Andrew Castaldi
Michael Kraich
Dan Lai
Xiang Lin
[KT, Sec 4.5] (HW 6 in, HW 7 out)
Mon, Oct 31 Optimality of Kruskal's and Prim's Algorithms (Slides [17.9MB]) Tyler Flemming
Dan Lai
Kris Feeley
Michael Kraich
[KT, Sec 4.5]
Wed, Nov 2 Cut Property Lemma (Slides [2.4MB]) Richard Doell
Sam Pezzino
Spencer Brigham
Travis Stradder
[KT, Sec 4.5]
Reading: [KT, Sec 4.6]
Fri, Nov 4 Divide and Conquer (Slides [.3MB]) Laura Perot
Benjamin Tapio
Tyler Flemming
Sam Pezzino
[KT, Sec 5.1] (HW 7 in, HW 8 out)
Mon, Nov 7 Mergesort Algorithm (Slides [.3mB]) Robert Stewart
Travis Stradder
Gabriel Freiberg
Laura Perot
[KT, Sec 5.1, 5.5]
Wed, Nov 9 Multiplication Algorithm (Slides [2MB]) Xiangyi Dong
Mike Slutsky
Jon Logan
Robert Stewart
[KT, Sec 5.5]
Reading: [KT, Sec 5.2]
Fri, Nov 11 Counting the Number of Inversions (Slides [1MB]) Jim Dobler
Philip Rosebrough
Xiangyi Dong
Mike Slutsky
[KT, Sec 5.3] (HW 8 in, HW 9 out)
Mon, Nov 14 Merge-Count (Slides, Notes) Gabriel Freiberg
Jon Logan
Andrew Becker
Junfei Wang
[KT, Sec 5.3, 5.4]
Tue, Nov 15 Review Session (Notes) Guest lecture by Jesse Hartloff
Wed, Nov 16 Closest Pair of Points (Slides, Notes) Yi Man Chia
Jordan Dawson
Jon Logan
Andrew Westcott
[KT, Sec 5.4]
Fri, Nov 18 Dynamic Programming (Slides, Notes) Evan Dombrowski
Vaibhav Shah
Greg Houston
Sanjiban Kundu
[KT, Sec 6.1] (HW 9 in)
Mon, Nov 21 Weighted Interval Scheduling Greg Houston
Sanjiban Kundu
Vaibhav Shah
Thirusajee Thanasinganathan
Guest lecture by Swapnoneel Roy
[KT, Sec 6.1, 6.2]
Wed, Nov 23 No Class Fall Recess
Fri, Nov 25 No Class Fall Recess
Mon, Nov 28 Weighted Interval Scheduling-II (Slides, Notes) Andrew Becker
Piers Butry
Thirusajee Thanasinganathan
Jimmy Dobler
Ryan Lombardo
[KT, Sec 6.1, 6.2]
Wed, Nov 30 Shortest Path with Negative Weights (Slides, Notes) Cheng Cheng
Andrew Westcott
Piers Butry
Evan Dombrowski
[KT, Sec 6.8]
Fri, Dec 2 Bellman-Ford Algorithm (Slides, Notes) Dylan Grabowski
Raghu Seshadri
Cheng Cheng
Yi Man Chia
Isaac Elbaz
[KT, Sec 6.8] (HW 10 out)
Mon, Dec 5 NP-Completness (Slides, Notes) Derek Falter
Wed, Dec 7 Approximation and Randomized Algorithms (Slides, Notes) Andrew Ring Derek Falter
Raghu Seshadri
Fri, Dec 9 Wrap-up (Slides) Isaac Elbaz Andrew Ring Last lecture (HW 10 in)