| Week | Topics covered | Notes from Class | Material, Homework | Announcements |
|---|---|---|---|---|
| Week 1 |
Wed: Course Administrivia; Definition of Algorithm;
Why we use Big-Oh.
Code Structures and their analysis: Straight-line code;
loops.
Thu: Big-Oh review; More Big-Oh: The Rules; proving claims using the Rules (part 1: proving f(n) ∈ O(g(n) using the definition) |
Sept 7: Intro; Sept 8: Big-O 1 | BigOh;
HW1, Self-test 1 Self-test 1 Solutions |
No labs this week, but we meet Thursday for class/tutorial. However, you should ensure that you have access to the lab (Room 115 in Building 315) after hours -- that your access card works. Information on card key access, as well as other topics such as accessing course pages for VIU CSCI courses, CSCI machines and accounts, lab usage rules, etc. is here. |
| Week 2 |
Mon: Big-O: The Rules. Define Ω and Θ.
Wed Algorithmic Approach: Divide and Conquer (Mergesort). Divide and Conquer Analysis: The Master Theorem. Thu: No labs or class (4-5). |
Sept 12: Rules of Big-O; Defn Ω(f(n)) and Θ(f(n)).
Sept 14: MergeSort and Master Theorem |
analyzing MergeSort, Babcock notes on Master Theorem Master Thm HW | No labs this week, and Thursday's tutorial/lecture is cancelled. Another tutorial time will be set up instead, after consultation with the class to select a time that works for most. |
| Week 3 |
Mon: Holiday
Wed: Algorithmic Approach: Data Structuring (Union-Find structures). Find. Thu: Problem-solving (problems such as on the assignment) |
Sept 21: Disjoint Sets Sept 22: Master Theorem Tutorial Sept 22: Note on Master Theorem |
||
| Week 4 |
Mon: Union-Find data structures
Path Compression heuristic for Union-Find; Analysis of Union
using Quick-Find); and Quick-Union with union-by-rank,
path-compression.
Wed: Graph representation. Thu: Reminder, Assignment 1 due on Saturday. Graph searching; generic search. |
Sept 26: UnionFind with Path Compression Sept 28: Graphs1 Sept 29: Graphs2 Sept 28: Union Find pseudocode Sept 28: Note on Assignment 1 Sept 29: Note on Assignment 1 |
||
| Week Oct 3 |
Mon: Graphs, cont'd: BFS DFS
Wed: Thu:Test |
Oct 3: DFS, BFS Oct 4: Greed: Prim's and Kruskal's algorithms Solution to Assignment 1 |
Eppstein: BFS and DFS | The following will be covered on the test. Big-O, Ω, Θ. Prove that a given function is in the Big-O of another using the definition; and/or using the Rules. Given a Divide-and-Conquer code fragment, analyze it to the point of finding the recurrence relation for the running time. Give Θ running times for Divide and Conquer recurrences using the Master Theorem. Example questions relating to Union-Find might be: given two trees, what is the result of a "Find(x)" operation, using path compression? What is the result of a union(x,y) when using union by rank? How many pointers will need to be redirected if using Quick-Find on a pair of trees that will be provided? Etc. |
| Week Oct 10 |
Mon: Thanksgiving holiday
Wed: Induction review Thu: Minimum Spanning Trees |
Oct 12: Induction Review |
A question that some students may be struggling with is echoed in this Proof by induction question on Stack Exchange. Paddling Ghost makes the correct point in response. These notes from M. Devos at SFU give an example of an induction proof on graphs that works, and one that does not. Other resources on Spanning Trees: Prims Kruskals | UToronto Proof of Correctness of Prim's |
| Week Oct 17 |
Mon: Greed: Unit task scheduling with deadlines and penalties.
DP: Dijkstra's algorithm
Wed: ATD Priority Queue; Heaps Thu: |
Oct 17: Greed: Unit Task Scheduling Oct 17: DP: Dijkstra's Algorithm Oct 19: Priority Queue ADT |
An old test that covers similar material |
|
| Week Oct 24 |
Mon:
Hashing: Hashing with Chaining
Wed: Thu: Test |
Oct 20: Heap Oct 24: Dictionary ADT: Hashtable Oct 24: Hash: linear probing |
||
| Week Oct 31 |
Mon: Binary Search Trees
Wed: AVL trees |
Oct 31: BST Nov 2: AVL |
Week Nov 7: Reading Week | |
| Week Nov 14 |
Mon: Divide & Conquer: Count Inversions, Herringbone Tile
Wed: Divide & Conquer: Strassen's Matrix Multiplication, Closest Pair Thu: Finish Closest Pair. Introduce Dynamic Programming. |
Nov14: Divide and Conquer: Count Inversions and Strassen's Matrix Multiplication Nov14: Divide and Conquer: Herringbone Tile Nov 16: Closest Pair Nov 17: Divide and Conqure Questions |
||
| Week Nov 21 |
Mon: Dynamic Programming:
Wed: Dynamic Programming: Thu: practice test |
Nov 21: Dynamic Programming Nov 23: Dynamic Programming: Change-making, Optimal Dancing |
Dynamic Programming (CMU)
Lab: Brad's AVL output for input.200. The other output.200 is the output from the original BST only. |
|
| Week Nov 28 |
Mon: B-Trees
Wed: Snow Day - no class Thu: Test |
Practice Midterm Nov 28: BTrees | ||
| Week Dec 5 |
Mon: Take up Midterm 3
(AVL trees, Divide and Conquer, Dynamic Programming, Hashing)
Wed: Thu: Review for Final Exam |
Material to help prepare for the exam:
|