|
|
|
Week #1: Introduction to Correctness of Algorithms
|
|
|
|
Monday, January 8
|
Lecture #1
|
Introduction to CPSC 331
|
|
Wednesday, January 10
|
Lecture #2
|
Proofs of Correctness
|
|
Friday, January 12
|
Lecture #3
|
Principles of Testing
|
|
Tutorial Exercise:
|
|
Getting Started in Computer Science 331
|
|
|
|
|
|
|
|
Week #2: Introduction to the Analysis of Algorithms
|
|
|
|
Monday, January 15
|
Lecture #4
|
Introduction to Algorithm Analysis
|
|
Wednesday, January 17
|
Lecture #5
|
Getting From Pseudocode To a Bound on Running Time
|
|
Friday, January 19
|
Lecture #6
|
Asymptotic Notation
|
|
First Tutorial Exercise:
|
|
Correctness of Algorithms
|
|
Second Tutorial Exercise:
|
|
Testing of Programs
|
|
|
|
|
|
|
|
Week #3: Introduction to Abstract Data Types; Stacks and Queues
|
|
|
|
Monday, January 22
|
Lecture #7
|
Introduction to Abstract Data Types
|
|
|
Assignment 1
|
Set (due in 2 weeks)
|
|
Wednesday, January 24
|
Lecture #8
|
Stacks
|
|
Friday, January 26
|
Lecture #9
|
Queues
|
|
First Tutorial Exercise:
|
|
Analysis of Running Time of Algorithms
|
|
Second Tutorial Exercise:
|
|
Asymptotic Notation and Standard Functions
|
|
|
|
|
|
|
|
Week #4: Introduction to Dictionaries
|
|
|
|
Monday, January 29
|
Lecture #10
|
Dictionaries: Implementations Using Arrays and Lists
|
|
Wednesday, January 31
|
Lecture #11
|
Binary Search Trees: Definition and Searching
|
|
Friday, February 2
|
Lecture #12
|
Binary Search Trees: Insertion and Deletion
|
|
First Tutorial Exercise:
|
|
Stacks
|
|
Second Tutorial Exercise:
|
|
Queues
|
|
|
|
|
|
|
|
Week #5: Red-Black Trees
|
|
|
|
Monday, February 5
|
Lecture #13
|
Introduction to Red-Black Trees
|
|
|
Assignment 1
|
Assignment 1
|
|
|
Assignment 2
|
Set (due in 3 weeks)
|
|
Wednesday, February 7
|
Lecture #14
|
Red-Black Trees: Rotations and Insertions
|
|
Friday, February 9
|
Lecture #15
|
Red-Black Trees: Deletions
|
|
Tutorial Exercise:
|
|
Dictionaries and Binary Search Trees
|
|
|
|
|
|
|
|
Week #6: Binary Search Trees, Concluded
|
|
|
|
Monday, February 12
|
Lecture Time
|
Questions about Tutorial Exercises and Review Questions
|
|
|
Term Test 1
|
6:00–7:30pm in ICT 102
|
|
Wednesday, February 14
|
Lecture #16
|
Average Case Analysis of Binary Search Trees
|
|
Friday, February 16
|
Lecture #17
|
Binary Tree Traversals
|
|
Tutorial Exercise:
|
|
Red-Black Trees
|
|
|
|
|
February 19-23
|
Reading Week
|
No lectures
|
|
|
|
|
|
|
|
Week #7: Hash Tables
|
|
|
|
Monday, February 26
|
Lecture #18
|
Hash Tables with Chaining
|
|
|
Assignment 2
|
Due at 4:30 pm
|
|
|
Assignment 3
|
Set (due in 2 weeks)
|
|
Wednesday, February 28
|
Lecture #19
|
Hash Functions
|
|
Friday, March 2
|
Lecture #20
|
Open Addressing
|
|
First Tutorial:
|
|
Term Test 1 Solutions
|
|
Second Tutorial
|
|
Leftover Questions from Previous Exercises
|
|
|
|
|
|
|
|
Week #8: Searching and Sorting
|
|
|
|
Monday, March 5
|
Lecture #21
|
Algorithms for Searching
|
|
Wednesday, March 7
|
Lecture #22
|
Classical Sorting Algorithms
|
|
Friday, March 9
|
Lecture #23
|
Merge Sort
|
|
Tutorial Exercise:
|
|
Hash Tables
|
|
|
|
|
|
|
|
Week #9: Searching and Sorting, Continued
|
|
|
|
Monday, March 12
|
Lecture #24
|
Binary Heaps
|
|
|
Assignment 3
|
Due at 4:30 pm
|
|
|
Assignment 4
|
Set (due in 2 weeks)
|
|
Wednesday, March 14
|
Lecture #25
|
Heap Sort
|
|
Friday, March 16
|
Lecture #26
|
Heap Sort, Continued
|
|
First Tutorial Exercise:
|
|
Algorithms for Searching
|
|
Second Tutorial Exercise:
|
|
Algorithms for Sorting
|
|
|
|
|
|
|
|
Week #10: Searching and Sorting, Concluded
|
|
|
|
Monday, March 19
|
Lecture #27
|
Priority Queues
|
|
Wednesday, March 21
|
Lecture #28
|
Quicksort
|
|
Friday, March 23
|
Lecture Time
|
Questions about Term Test #2
|
|
Tutorial Exercise:
|
|
Heaps and Heap Sort
|
|
|
|
|
|
|
|
Week #11: Graphs and Their Algorithms
|
|
|
|
Monday, March 26
|
Lecture #29
|
Graphs and Their Representations
|
|
|
Term Test 2
|
6:00–7:30pm in ICT 102
|
|
Wednesday, March 28
|
Lecture #30
|
Breadth-First Search
|
|
Friday, March 30
|
Lecture #31
|
Depth-First Search
|
|
|
Assignment 4
|
Due at 4:30 pm
|
|
|
Assignment 5
|
Set (due in 2 weeks)
|
|
First Tutorial:
|
|
Preparing for Term Test #2
|
|
Second Tutorial:
|
|
Quicksort
|
|
|
|
|
|
|
|
Week #12: Graphs and Their Algorithms, Continued
|
|
|
|
Monday, April 2
|
Lecture #32
|
Depth-First Search, Concluded
|
|
Wednesday, April 4
|
Lecture #33
|
Trees and Spanning Trees
|
|
Friday, April 6
|
Good Friday
|
No lecture
|
|
Tutorials:
|
|
Introduction to Graphs
|
|
|
|
|
|
|
|
Week #13: Graphs and Their Algorithms, Concluded
|
|
|
|
Monday, April 9
|
Lecture #34
|
Minimum-Cost Spanning Trees
|
|
Wednesday, April 11
|
Lecture #35
|
Prim's Algorithm
|
|
Friday, April 13
|
Lecture #36
|
Other Graph Problems and Algorithms
|
|
|
Assignment 5
|
Due at 4:30 pm
|
|
First Tutorial:
|
|
Graph Traversals
|
|
Second Tutorial:
|
|
Course Review
|
|
|
|
|