Detailed Schedule

Notes:

  • The following schedule is tentative. As we progress through the class, I will update it so that dates correspond to what actually happened.

  • As they become available, assignments will be posted here. The "H" part of a "HW" link is postscript, and the "W" part is the corresponding LaTeX file. For information on how to use LaTeX to write up your homework solutions, click here.

  • Although it is tentative, use this schedule to help you plan ahead. For example, tentative exam dates are displayed in this font. Homework assignments that require you to write code are displayed in this font. As grading of the code portions of a homework will assume working code, unless you are magically endowed with special powers for predicting how long debugging might take, start these problems ASAP.

    Week Lec Tuesday Homework Lec Thursday Homework
    1/19 1 Introduction,
    Insertion Sort    		 HW 1a: Logs, Induction 2 Asymptotics,
    Merge Sort    		 HW 1b: Geo Series, Growth,
    Rank, Stock Market
    1/26 3 Recurrence Relations:
    Sorting, Strassen    		 HW 2a: Divide-n-Conquer
    Multiplication    		 4 More Sorting,
    General Lower Bounds    		 HW 2b: Heaps,
    Stooge Sort, Lower Bounds
    2/2 5 Priority Queues,
    Amortization    		 HW 3a: Buildheap,
    Diminishing Returns    		 6 More Amortization,
    Order Stats    		 HW 3b: IncrKey,
    Amortized: Stacks,
    Trees, Arrays
    2/9 7 Linear Sorting,
    Red-Black Trees    		 HW 4a: Oil-of-Olay,
    Radix Sort Proof    		 8 B-Trees HW 4b: B-Trees
    2/16 9 Dynamic Programming (DP):
    Matrix Mult, LCS    		 HW 5a: Mono, LCS Example 10 More DP: Knap-sack,
    Opt. Search Trees    		 HW 5b: Change,
    Skiing, Load Balance
    2/23 11 Variable-length Linear Sort,
    Div-n-Conquer/DP Summary.    		 Study Guide 12 Graph Algs: Intro,
    Midterm Review    		 MT #1
    3/1 13 Greed HW 7a: Greed Means Caution! 14 Basic Graph Algs:
    BFS, DFS, Top Sort    		 HW 7b: Diameters,
    Cycle Detection,
    Party Fun
    3/8 19 Min Span Trees (MST):
    Prim    		 HW 8a: Greed is G-R-E-A-T! 20 More MST: Kruskall,
    Union-Find    		 HW In class worksheet:
    Integer Weights
    3/15 no class: spring break
    3/22 15 Shortest Paths (SP):
    Floyd-Warshall (FW),
    Bellman-Ford (BF)    		 HW 9a: Baruvka! Neg. Cost Cycles 16
    Floyd-Warshall, DAG-SP    		 HW 9b: Arbitrage,
    NW Reliability,
    FW
    3/29 17 Dijkstra's Algorithm HW 10a: Dijkstra's Boringness 18 Johnson's Algorithm HW 10b: Johnson Problems,
    Hurts Navigation,
    MST/SPs
    4/5 21 Network Flow (NWF) HW 11a: NWF Proofs 22 More NWF HW 11b: Cuts, NASA
    Unicycles, Disjoint Paths
    4/12 22 Linear Programming Study Guide 23 Midterm Review MT #2
    4/19 24 NP-Completeness (NPC) HW 12a: Hit Set 25 More NPC HW 12b: Kernel, Snow Plows
    ILP, Lai, 2-SAT
    4/26 26 And more NPC HW 13a: Network Reliability 27 Approx. Algs HW 13b: Approx. Problem
    5/3 no class: finals week
    Final Study Guide
    Available: around 5/4. Due back: around 5/7