| Week | Topics covered | Notes from Class | Material, 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 |
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 Sept 14: MergeSort and Master Theorem 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 |
Mon:
Divide and Conquer Analysis: The Master Theorem.
Wed: Algorithmic Approach: Data Structuring (Union-Find structures). Find. Thu: Problem-solving (problems such as on the assignment) |
analyzing MergeSort, Master Thm HW Wyss-Gallifent notes on the Master Theorem |
Sept 21: Disjoint Sets
|||
| 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 |
|||
| Week Oct 3 |
Mon: Graphs, cont'd: BFS DFS
Wed: Thu:Test |
Eppstein: BFS and DFS | |||
| Week Oct 10 |