| Home | Learning Goals | Schedule | Administration | Readings | Lab/Lecture Notes | Assignments | Computing |
Additional References on C++ and Unix that might be helpful (and often available at the CS Reading Room) include:
And many other books on discrete math, data structures, C++, Unix, etc. in the Reading Room and in the UBC Library.
| Topics | Readings from the Koffman text | Readings from the Epp text (4th edition) | |
|---|---|---|---|
| Background that you're supposed to already know |
Basics: Ch 1 Functions: 7.1, 7.2, 7.3, 11.1 Induction: 5.2, 5.3, 5.4 Logic: Ch 2 Proofs: Ch 4 Quantifiers: Ch 3 Sets: 1.2, 6.1, 6.2, 6.3 |
||
| Week 1 May 12-16 |
Overview; Linked lists, stacks, and queues; Introduction to algorithm analysis |
Lists: 4.5
Stacks: 5 Queues: 6.1-6.3 Big-O: Ch 2.6 Optional: Iterators 4.6-4.7 |
Analysis of algorithms: 4.8, 11.3
Big-O Notation: 11.2 Summations: 5.2 |
| Week 2 May 19-23 |
Big O, Big Omega, Big Theta; Summations; Induction; Recursion; Recurrence Relations | Big-O: Ch 2.6
Recursion: 7 |
Analysis of Binary Search: 11.4, 11.5
Big-O Notation: 11.2 Recurrence Relations: 5.7 Recursion: 5.6 Summations: 5.2 |
| Week 3 May 26-30 |
Runtime Analysis; Recursion; Correctness of Recursive Algorithms; Loop invariants
Trees, tree traversal, and binary search trees |
Recursion: 7
Insertion Sort: 10.4 Trees: 8.1-8.4 AVL Trees: 11.1-11.2 |
Correctness of Algorithms: 5.5
InsertionSort: 11.3 Logs: 7.1, 7.2, 11.4 Trees: 10.5, 10.6 |
| Week 4 June 2-6 Note: midterm in class June 4 |
Review
Dictionaries: Successor, FindClosest, RangeQuery Priority Queues: Implemented with arrays or AVL trees PQSort |
Priority Queues: pp. 489-490
Dictionaries (=Maps): 9.2, 9.6 |
|
| Week 5 June 9-14 |
B-Trees
Sorting: Select, Insert, Merge, Quick Hashing |
B-Trees: 11.4-11.5
Sorting: 10.2, 10.4, 10.7, 10.9 Hashing: 9.3-9.5 |
|
| Week 6 June 16-20 |
Graphs Counting Review |
Graphs: Ch 12 | Graphs: Ch 10
Counting: 9.1-9.6 |
| Week 7 June 23-27 |
Exam, Thursday June 26 |