| Week | Topics Covered | Notes from Class | Other material,Notes from previous years, homework | Announcements | Labs and Assignments |
|---|---|---|---|---|---|
|
Week 1 Sep 8-11 |
Wed: Course Administrivia; Definition of Algorithm;
Thu: Random Access Machine model; Big-O. Proving f(n) ∈ O(g(n) using the definition. Some Rules of Big-O. |
Administration and motivation; Introduction to Data Structures and Algorithms; RAM, Big-O intro Big-O cont'd |
My conversation with Co-Pilot on algorithms HW1, Self-test 1 |
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. |
Assignment 1 is due Monday Sept 21 : ADT Array (no hint) ATD Array (with hint) |
|
Week 2
Sep 14-18 |
Mon: Big-O: The Rules. Define Ω and Θ.
Wed Algorithmic Approach: More of the Input, More of the Output, Divide and Conquer (Mergesort). Thu: ADT Array (the assignment question); UnionFind ADT and its various implementations. |
More Rules of Big-O; Defn Ω(f(n)) and Θ(f(n)). Algorithm defn; Algorithmic approaches Union-Find (Disjoint Sets) ADT and algorithms |
Labs begin this week. Before you come to tutorial,
ensure that you have access to the lab (try your card) and have access to your account (follow your login instructions).
|
Lab 1: Union-Find Git - verbose and succinct. |
|
|
Week 3 Sep 21-25 |
Mon:
Divide and Conquer Analysis: The Master Theorem.
Wed: Algorithmic Approach: Data Structuring (Union-Find structures). Find. Thu: Union-find using union-by-rank and path-compression; practice Big-O and Master Theorem |
analyzing MergeSort, MergeSort and Master Theorem When the Master Theorem is silent. More Div & Conq: Karatsuma's Algorithm Sept 23 Union-Find notes from Sep 17 with more stuff added Sept 24 Union-Find using union-by-rank and path compression |
Master Thm HW
Wyss-Gallifent notes on
the Master Theorem Master Theorem Tutorial Sept 26: UnionFind with Path Compression |
Assignment 2, due Oct 1 at midnight Updated Lab 2, due at midnight Tue Sept 29. The Lab 2 specifications originally published had union-by-size and is give here: old instructions. That is the version seen by the 9:00 lab. Students should, after the Thursday lecture, change their code to do union-by-rank and meet all the requirements of the updated Lab 2. |
Assignment 2 Assignment 2 Solutions Lab 2 |
| Week 4 |
Mon: Stacks and Queues review; Graph Theory intro
Wed: Graph Theory, graph representation, BFS, DFS Thu: Review for test Oct 8 -- Video |
Graphs1
Graphs2 Review for Test: Open two browser tabs to simultaneously see slides and listen. Big-O practice slides, recording). Master Theorem practice slides, recording). The zip files are here: Big-O and here: Master Theorem . Once unzipped, I had to click on the audio file and then the pdf separately to listen while reading. On linux, you can use the ``unzip" command. Other operating systems also likely have an unzipper installed, or you can search the web. |
Sept 28: Graphs1 Sept 29: Graphs2 Eppstein: BFS and DFS A Sample Test 1 |
The Lab this week will be self-directed during the scheduled lab time, and lab time with the instructor will be in 315/115 Monday Oct 5 from 11:30 to 1:30. | Lab3 |
| Week 5 Oct 5 |
Mon: Greedy Algorithms. BFS, DFS
Wed: Prim's and Kruskal's algorithms for Spanning Tree Thu:Test |
Greed: Prim's and Kruskal's algorithms DFS iterative and recursive |
Handout of handy facts DFS, BFS |
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. | Lab4, Due Oct 14. |
| Week 6 Oct 12 |
Tue: Thanksgiving holiday on Monday:
the schedule for Monday is moved to Tuesday.
Induction Review. Proving claims about graphs using strong induction.
Greedy change-making algorithm.
Wed: Thu: |
Induction Review Greedy change-making Greedy task-scheduling D1 D2 |
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
Dijkstra's shortest paths (weighted edges) Dijkstra's Algorithm |
Lab5, Due Oct 21. | |
| Week Oct 19 |
Mon: ADT Priority Queue; Heaps
Wed: ADT Dictionary: Open hashing Thu: Hashing: Closed hashing |
Priority Queue ADT Priority Queue: Heaps ADT Dictionary: Hashtables Hashtables: closed hashing |
Sample Test 2 and some sample graphs Heaps Dictionary ADT: Hashtable Hash: linear probing |
Lab6, Due Nov 4. | |
| Week 7 Oct 26 |
Mon:
Intro to Balanced Binary Search Trees
Wed: Intro to AVL trees Thu: Test. No "cheat sheet". |
BST AVL |
BST |
AVL Neel Mishra on AVL trees See Algorithms AVL animation Topics for the test: Graphs and their representations; heaps,BFS, DFS, Prim's, Kruskal's and Dijkstra's algorithms; Greedy algorithms (change-making, unit-length task scheduling with penalties and deadlines); loop invariants. |
|
| Week 8 Nov 2 |
Mon: B-trees
Wed: Count inversions, Herringbone Tile Thu: |
B-trees |
See Algorithms B-tree animation |
||
| Week Nov 9 |
Mon: Reading Week
Wed: Reading Week Thu: Reading Week |
||||
| Week Nov 16 |
Mon: Divide & Conquer: Strassen's Matrix Multiplication, Closest Pair Wed: 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 23 |
Mon: Dynamic Programming:
Wed: Dynamic Programming: Thu: practice test |
Dynamic Programming 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 30 |
Mon: B-Trees
Wed: Thu: Test |
Practice Midterm Nov 28: BTrees | |||
| Week Dec 5 |
Mon: Take up Midterm 3
(AVL trees, Divide and Conquer, Dynamic Programming
Wed: Thu: Review for Final Exam |
Material to help prepare for the exam:
|