Fall 2010 schedule (Click here for last fall's schedule).
Date | Topic | Blogger | Group Leader | Notes |
Mon, Aug 30 | Introduction (Slides [30MB]) | Atri Rudra | (HW 0 out) | |
Wed, Sep 1 | More Introduction (Slides [26.4 MB]) | Atri Rudra | ||
Fri, Sep 3 | Why Algorithms? (Slides [7.82 MB]) | Atri Rudra | ||
Mon, Sep 6 | No class | Labor Day | ||
Wed, Sep 8 | Stable Marriage Problem (Slides [3.81 MB]) | Jesse Hartloff Eric Mikida |
Denise Blady Jae Hyun Park |
[KT, Sec 1.1] |
Fri, Sep 10 | Stable Marriage Problem-II (Slides [2.26MB]) | Kyle Marcus Jae Hyun Park |
Eric Mikida Brian Rosenberg |
[KT, Sec 1.1] (HW 1 out) |
Mon, Sep 13 | Gale-Shapley Algorithm (Slides [3.5MB]) | Andrew Glowacki Adam Soom |
Jesse Hartloff Daniel McNeil |
[KT, Sec 1.1] |
Wed, Sep 15 | GS Algorithm terminates (Slides [1.55 MB]) | Michael Gerritsen Roy Okoroji |
Alex Reiner Justin Rodriguez |
[KT, Sec 1.1] |
Fri, Sep 17 | GS Algorithm Outputs a Perfect Matching (Slides [1.2MB]) | Laurie Dening Daniel Knopp |
JP Endaya Lisa Slish |
[KT, Sec 1.1] (HW 1 in, HW 2 out) |
Mon, Sep 20 | GS Algorithms Outputs a Stable Matching (Slides [5.2 MB]) | Ankit Agarwal Patrick Lapinski |
Michael Krzeminski Robin Sachdev |
[KT, Sec 1.1] |
Wed, Sep 22 | Asymptotic Notation (Slides [2.6MB]) | Steven J Hsieh Jeffrey Meyers |
Ankit Agarwal Patrick Lapinski |
[KT, Sec 2.1, 2.2] |
Fri, Sep 24 | Run Time Analysis of GS Algorithm (Slides [1.87 MB]) | Jeff Plewak Robin Sachdev |
Jeffrey Chu Laurie Dening |
[KT, Sec 2.3] (HW 2 in, HW 3 out) |
Mon, Sep 27 | Runtime Analysis of GS algorithm-II (Slides [5.95MB]) | Brian Rosenberg Brady Whitten |
Chris Lussier Jeff Plewak |
[KT, Sec 2.3, 3.1] |
Wed, Sep 29 | Graph Basics (Slides [4.52 MB]) | Tushar Agrawal Thomas Klonowski |
Solmon Song Adam Soom |
[KT, Sec 3.1] |
Fri, Oct 1 | Trees (Slides [3.24 MB]) | Denise Blady JP Endaya |
Chris Fabiano Jeff Meyers |
[KT, Sec 3.1] (HW 3 in, HW 4 out) |
Mon, Oct 4 | Breadth First Search (Slides [3.3 MB]) | Yogesh Patel Colin Wilbert |
Matt Degen Xiaoyu Ge |
[KT, Sec 3.2] |
Wed, Oct 6 | Computing Connected Component (Slides [2.78 MB]) | Daniel McNeil Sejal Patel |
Hasan Hasanov Daniel Knopp |
[KT, Sec 3.2] |
Fri, Oct 8 | Representing Graphs (Slides [4.88 MB]) | Matt Dyson David Ragsdale |
Andrew Glowacki Kyle Marcus |
[KT, Sec 3.3] (HW 4 in, HW 5 out)) |
Mon, Oct 11 | Analyzing BFS (Slides [2.57 MB]) | Alex Reiner Justin Rodriguez |
David Ragsdale Andrew Wantuch |
[KT, Sec 3.3] |
Wed, Oct 13 | Topological Sorting (Slides [3.29 MB]) | Michael Krzeminski
Mike Vedete |
Tim Eaton Lin Li |
[KT, Sec 3.6] |
Fri, Oct 15 | Computing Topological Sorting (Slides [2.21 MB]) | Jeffrey Chu
Lisa Slish |
Matthew Davison Mike Vedete |
[KT, Sec 3.6] (HW 5 in) |
Mon, Oct 18 | Mid term exam | In class | ||
Wed, Oct 20 | Interval Scheduling Problem ( Slides [3.37 MB]) | Xiaoyu Ge Matthew C Harkins Chris Lussier |
Nicholas McClure Sugandha Sharma Chenqi Tan |
[KT, Sec 4.1] |
Fri, Oct 22 | Optimal Algorithm for Interval Scheduling (Slides [1.37 MB]) | Alex Janikowski Lynn Jensen Nicholas McClure |
Brian Burt Katie Fye Sejal Patel |
[KT, Sec 4.1] (HW 6 out) |
Mon, Oct 25 | Scheduling to minimize lateness (Slides [1.7MB]) | Tim Eaton Bojan Percevic Solmon Song |
Matt Dyson Steven J Hsieh Al Fineberg |
[KT, Sec 4.2] |
Wed, Oct 27 | Analyzing the Greedy Algorithm-I ( Slides [.4 MB]) | Matt Degen Al Fineberg Lin Li |
Thomas Klonowski Bojan Percevic Brady Whitten |
[KT, Sec 4.2] |
Fri, Oct 29 | Analyzing the Greedy Algorithm-II (Slides [.18 MB]) | Brian K Burt Jr. Katie Fye Chenqi Tan |
Tushar Agrawal Stephen Christner John Ferreira |
[KT, Sec 4.2] (HW 6 in, HW 7 out) |
Mon, Nov 1 | Shortest Path Problem (Slides [3.29 MB]) | Stephen Christner Rohit Deshmukh Sugandha Sharma |
Puneet Chawla Alex Janikowski Robert Lathrop |
[KT, Sec 4.4] |
Wed, Nov 3 | Minimum Spanning Tree Problem (Slides [1.29 MB]) | Brian Askew Hasan Hasanov Santosh Thapa |
Lynn Jensen Yogesh Patel Corey J Sleve |
[KT, Sec 4.5] |
Fri, Nov 5 | Correctness of Kruskal's Algorithm (Slides [.94 MB]) | Matthew Davison Chaw K Khaing Robert Lathrop |
Rohit Deshmukh Shesh Patel Santosh Thapa |
[KT, Sec 4.5] (HW 7 in, HW 8 out) |
Mon, Nov 8 | Cut Property Lemma (Slides [17.46 MB]) | James Eckert Nathan Long Brian Wetter |
Roy Okoroji Kurt Ringwall Kyle Schmidt |
[KT, Sec 4.5] |
Wed, Nov 10 | Divide and Conquer (Slides [2.17 MB]) | John Ferreira Brian MacLeod Corey J Sleve |
James Eckert Chaw K Khaing Colin Wilbert |
[KT, Sec 5.1] |
Fri, Nov 12 | Mergesort Algorithms (Slides [.12 MB]) | Nikkita Agarwal Kris Feeley Shesh Patel |
Mike Garricks Brian MacLeod |
[KT, Sec 5.1] (HW 8 in, HW 9 out) |
Mon, Nov 15 | Multiplying two integers (Slides [.12 MB]) | Justin Boyd Rahumathullah Rumaiz Kyle Schmidt |
Juhwan Song Brian Wetter |
[KT, Sec 5.5] |
Wed, Nov 17 | Counting Inversions (Slides [1.79 MB]) | James Cockcroft Kurt Ringwall Juhwan Song |
Matthew C Harkins Nathan Long |
[KT, Sec 5.3] |
Fri, Nov 19 | Closest Pair of Points (Slides [.75 MB]) | Nick Davidson Mike Garricks |
Nikkita Agarwal Andrew Carland Rahumathullah Rumaiz |
[KT, Sec 5.4] (HW 9 in) |
Mon, Nov 22 | Divide and Conquer Algorithm for Closest Pair of Points (Slides [.79 MB]) | Andrew Carland Chris Fabiano Andrew C. Wantuch |
James Cockcroft Anthony Rocco |
[KT, Sec 5.4] |
Wed, Nov 24 | No class | Fall recess | ||
Fri, Nov 26 | No class | Fall recess | ||
Mon, Nov 29 | Dynamic Programming (Slides [2.3 MB]) | Sean Homan Anthony Rocco |
Nick Davidson | [KT, Sec 6.1] |
Wed, Dec 1 | Weighted Interval Scheduling (Slides [.23 MB]) | Brian Askew | [KT, Sec 6.1] | |
Fri, Dec 3 | Shortest Path Problem with Negative Weights (Slides [1.19 MB]) | Seon McDonald | John Montemorano | [KT, Sec 6.8] (HW 10 out) |
Mon, Dec 6 | Bellman-Ford Algorithm (Slides [.6 MB]) | John Montemorano | Sarah Burns Sean Homan Seon McDonald |
[KT, Sec 6.8] |
Wed, Dec 8 | NP-Completeness (Slides [2.69 MB]) | Thirusajee Thanasinganathan | Michael Gerritsen | |
Fri, Dec 10 | Wrap-up (Slides [6.31 MB]) | Sarah Burns Puneet Chawla |
Last lecture (HW 10 in) |