Home | Learning Goals | Schedule | Administration | Readings | Lab/Lecture Notes | Assignments | Computing |
NOTE: Labs begin Thu May 15 or Fri May 16.
Lectures:
Section | Days | Time | Place | Instructor |
201 | MWF | 2.30–5.00 | DMP 110 | Nick Harvey |
Labs:
Section | Day | Time | Place | TAs |
L0A | Wed Fri | 10.00-12.00 | ICCS X251 | Jimmy, Anupam |
L0B | Wed Fri | 12.00-14.00 | ICCS X251 | Adrian, Alex |
L0C | Wed Fri | 17.00-19.00 | ICCS X251 | Kevin, Thomas, Sisi |
L0D | Tue Thu | 10.00-12.00 | ICCS X251 | Alireza, Marjan, Alec |
Feel free to attend other—or multiple!—lectures or labs, subject to available space. (Students registered in a particular session have precedence.) You may need to attend your registered lab section to receive a mark.
Approximate Topic Schedule:
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 |