Anything new and of sufficient consequence (such as cancellations, updates to assignments, etc.)
will be emailed to the class.
Such emails will arrive at the email address that is indicated at your Student Record.
Announcements with lasting significance will also be posted here.
If I change an announcement, I will put the change in bold
| Date | Topic | Links | Announcement |
|---|---|---|---|
| Sept 6: | Big-O, Ω, ω review. |
Big-O notes from CSCI 260 Introduction to Range Minima Queries | |
| Sept 11, 13 |
Lab: In 315/115. Lecture: Range Minima Query, continued. |
Range Minimum Query 2, continued.
Range Minima Query 3, continued. MIT scribe Notes: go to Lecture 15. |
Range Minima Query Lab | (now due Saturday Sept 23 at midnight)
| Sept 18, 20 |
Lecture:: Range Minimum Query, finish; Minimum Contiguous Sum
Tutorial: in 210/255 |
Minimum Contiguous Sum (short topic, bit of Dynamic Programming review).
Jeff Erickson's Chapter on Dynamic Programmig Amortized Analysis Intro |
Assignment 1: RMQ (and Min Contig Sum) and Solutions |
| Sept 25, 27 |
Lecture:: Amoritized Analysis: Binary Counter, Union Find
Tutorial: in 210/255 |
Amortized Analysis
: Binary Counter
Slides on Union-Findby Robert SEdgewick and Kevin Wayne Amortized Analysis Union-Find |
Assignment 2 Amortized Analysis Due Oct 11, and Solutions |
| Oct 4 |
Lecture:: Fibonacci Heaps
Tutorial: in 210/255 |
Fibonacci Heaps
| |
| Oct 9, 11 |
Lecture:: Fibonacci Heaps, cont'd
Tutorial: |
Fibonacci Heaps cont'd Review for Test |
|
| Oct 16, 18 |
Lecture:: Oct 18 TEST
Tutorial: |
| |
| Oct 23, 25 |
Lecture: Cancelled due to illness.
Network Flow Algorithm: Flow Augmenting Path.
Tutorial: |
Independent reading assigned: U. Illinois slides Jeff Erickson's chapter (read to end of Chapter 10.4 by Wednesday, you can skip the part about irrational capacities) Fib Heaps (conclusion) Network Flow Intro | Network Flow Practice Graphs |
| Oct 30, Nov 1 |
Lecture:
Network Flow Algorithm: Shortest Flow Augmenting Path.
Lab: In 315/115. Network Flow Algorithm |
Network Flow - Shortest Augmenting Path (see also Jeff Erickson's chapter on Network Flow) Network Flow - Maximum Matching | Network Flow Lab |
| Nov 6, 8 |
Lecture:
Network Flow Applications: Disjoint Paths, Tuples
Lab: In 315/115. Network Flow Algorithm, continued. |
Network Flow - Applications (see also Jeff Erickson's chapter on Network Flow) Network Flow - Disjoint Path Covers Network Flow - Min Faculty Hire (Airline problem) Greedy - Stable Matching | |
| Nov 20, 22 |
Lecture:
Dynamic Programming: Fibonacci, Longest Increasing Subsequence, Optimal Binary Trees
Tutorial: In 210/255. |
Dynamic Programming (see also Jeff Erickson's chapter 3) | Take Home Test Draft Update:On Nov 27, a take home test like the attached will be made available. It will be due Nov 28. (This is a change: we had talked about making it available on Sunday, due on Monday, but not everyone had availability in that window, so it is moved to being available Monday, due Tuesday at 1:30.) In the meantime, undertake the Draft test, to ensure you understand the material. Here are the Solutions. |
| Nov 27, Nov 29 |
Lecture:
Nov 27: Leetcode Dynamic Programming:
Nov 29 Presentations: EthB, NicH, EthP Tutorial: Nov 27: none; Nov 29: In 210/255, if presentations run overtime. |
Test 2 and < Test 2 (compact edition). You can look at any textbook and published material as long as it is not bespoke solutions to this test or the draft test done by any other person (you can look at the solutions to the draft test that you yourself wrote). | Topics taken: 1. Coin change problem 2. Pascal's Triangle 3. Regular Expression matching. Best Time to Buy and Sell Stock with Transaction Fee |
| Dec 4, 6 |
Lecture:
Presentations: Dec 4: DanA, MegC, MadJ Dec 6: EdN, AdN, WilP, DomS Tutorial: In 210/255, if we run overtime in the lecture presentations. |
Useful Links:
Course Outline
Jeff Erickson's Algorithms (page with multiple links)
Gara Pruesse's Homepage
Computer Science Homepage
Vancouver Island University Homepage