Fall 2011 schedule (Previous schedules: 2009, 2010).
Date | Topic | Blogger | Scribe | Notes |
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) |