Week #1: Introduction to Correctness of Algorithms
|
|
|
|
Monday, January 11
|
Lecture #1
|
Introduction to CPSC 331
|
|
Wednesday, January 13
|
Lecture #2
|
Correctness of Algorithms and Programs
|
|
Friday, January 15
|
Lecture #3
|
Correctness of Algorithms and Programs (continued)
|
|
|
|
|
Week #2: Introduction to Testing
|
|
|
|
Monday, January 18
|
Lecture #4
|
Correctness of Algorithms and Programs (continued)
|
|
Wednesday, January 20
|
Lecture #5
|
Principles of Testing
|
|
Friday, January 22
|
Lecture #6
|
Principles of Testing (continued)
|
|
First Tutorial:
|
Tutorial #1
|
Java Review
|
|
Second Tutorial:
|
Tutorial #2
|
Proofs of Correctness of Algorithms
|
|
Tutorial #2 supplement:
|
|
Proof of Correctness example
|
|
Friday, January 22
|
Assignment 1
|
Set (due Monday, February 8)
|
|
|
|
|
Week #3: Introduction to the Analysis of Algorithms
|
|
|
|
Monday, January 25
|
Lecture #7
|
Introduction to Algorithm Analysis
|
|
Wednesday, January 27
|
Lecture #8
|
Introduction to Algorithm Analysis (continued)
|
|
Friday, January 29
|
Lecture #9
|
Asymptotic Notation
|
|
Lecture supplement:
|
|
Analyzing the Running Time of an Algorithm
|
|
Lecture supplement:
|
|
Using Asymptotic Notation
|
|
First Tutorial:
|
Tutorial #3
|
Testing of Programs
|
|
Second Tutorial:
|
Tutorial #4
|
Analysis of Running Time of Algorithms
|
|
|
|
|
Week #4: Basic Data Structures
|
|
|
|
Monday, February 1
|
Lecture #10
|
Abstract Data Types, Data Structures, and Their Implementations
|
|
Wednesday, February 3
|
Lecture #11
|
Basic Data Structures
|
|
Friday, February 5
|
Lecture #12
|
Basic Data Structures (continued)
|
|
Lecture supplement:
|
|
Amortized Analysis of Operations on Dynamic Arrays
|
|
First Tutorial:
|
Tutorial #5
|
Asymptotic Notation
|
|
Second Tutorial:
|
Tutorial #6
|
Discussion of Assignment 1
|
|
|
|
|
Week #5: Searching and Sorting
|
|
|
|
Monday, February 8
|
Lecture #13
|
Stacks
|
|
Wednesday, February 10
|
Lecture #14
|
Queues
|
|
Friday, February 12
|
Lecture #15
|
Searching
|
|
First Tutorial:
|
Tutorial #7
|
Arrays and Lists
|
|
Second Tutorial
|
Tutorial #8
|
Stacks
|
|
Monday, February 8
|
Assignment 1
|
Due at 11:59 pm
|
|
Monday, February 8
|
Assignment 2
|
Set (due Monday, February 29)
|
|
|
|
|
February 15-19
|
Reading Week
|
No lectures
|
|
|
|
|
Week #6: Basic Data Structures; Dictionaries
|
|
|
|
Monday, February 22
|
Lecture #16
|
Classical Sorting
|
|
Wednesday, February 24
|
Lecture #17
|
Classical Sorting (continued)
|
|
Friday, February 26
|
Lecture #18
|
Binary Search Trees
|
|
Lecture supplement:
|
|
Tree Traversals
|
|
First Tutorial:
|
Tutorial #9
|
Queues
|
|
Second Tutorial:
|
Tutorial #10
|
Discussion of Assignment 2
|
|
|
|
|
Week #7: Red-Black Trees
|
|
|
|
Monday, February 29
|
Lecture #19
|
Binary Search Trees (continued)
|
|
Wednesday, March 2
|
Lecture #20
|
Introduction to Red-Black Trees
|
|
Friday, March 4
|
Lecture #21
|
Red-Black Trees: Rotations and Insertions
|
|
Lecture supplement:
|
|
Analysis of Operations on Binary Search Trees
|
|
Lecture supplement:
|
|
Average-Case Analysis of Binary Search Trees
|
|
First Tutorial:
|
Tutorial #11
|
Algorithms for Searching
|
|
Second Tutorial:
|
Tutorial #12
|
Classical Sorting Algorithms
|
|
Monday, February 29
|
Assignment 2
|
Due at 11:59 pm
|
|
Monday, February 29
|
Assignment 3
|
Set (due Wednesday, March 23)
|
|
|
|
|
Week #8: Hash Tables
|
|
|
|
Monday, March 7
|
Lecture Time
|
Questions about the Midterm
|
|
Wednesday, March 9
|
Lecture #22
|
Red-Black Trees: Deletions
|
|
Friday, March 11
|
Lecture #23
|
Hash Tables with Chaining
|
|
Lecture supplement:
|
|
Additional Kinds of Search Trees
|
|
First Tutorial
|
Tutorial #13
|
Binary Search Trees
|
|
Second Tutorial:
|
Tutorial #14
|
Red-Black Trees
|
|
Monday, March 7
|
Midterm
|
5:00–6:30pm in ST 135
|
|
|
|
|
Week #9: Advanced Sorting
|
|
|
|
Monday, March 14
|
Lecture #24
|
Hash Tables with Open Addressing
|
|
Wednesday, March 16
|
Lecture #25
|
Merge Sort
|
|
Friday, March 18
|
Lecture #26
|
Binary Heaps
|
|
Lecture supplement:
|
|
Hash Functions and Additional Hashing Strategies
|
|
First Tutorial
|
Tutorial #15
|
Hash Tables
|
|
Second Tutorial:
|
Tutorial #16
|
Merge Sort
|
|
|
|
|
Week #10: Advanced Sorting, Concluded
|
|
|
|
Monday, March 21
|
Lecture #27
|
Operations on Binary Heaps
|
|
Wednesday, March 23
|
Lecture #28
|
Applications of Binary Heaps
|
|
Friday, March 25
|
No Lecture
|
Good Friday
|
|
First Tutorial
|
Tutorial #17
|
Discussion of Assignment 3
|
|
Second Tutorial:
|
Tutorial #18:
|
Binary Heaps and Their Applications
|
|
Wednesday, March 23
|
Assignment 3
|
Due at 11:59 pm
|
|
Wednesday, March 23
|
Assignment 4
|
Set (due Wednesday, April 13)
|
|
|
|
|
Week #11: Graphs and Their Algorithms
|
|
|
|
Monday, March 28
|
Lecture #29
|
Quicksort
|
|
Wednesday, March 30
|
Lecture #30
|
Graphs and Their Representations
|
|
Friday, April 1
|
Lecture #31
|
Trees, Spanning Trees, and Subgraphs
|
|
Lecture supplement:
|
|
Proof of Tree Propeties
|
|
First Tutorial:
|
Tutorial #19:
|
Quicksort
|
|
Second Tutorial:
|
Tutorial #20:
|
Introduction to Graphs
|
|
|
|
|
Week #12: Graphs and Their Algorithms, Continued
|
|
|
|
Monday, April 4
|
Lecture #32
|
Graph Search: Depth-First Search (Slides from class with example worked out)
|
|
Wednesday, April 6
|
Lecture #33
|
Graph Search: Breadth-First Search (Slides from class with example worked out)
|
|
Friday, April 8
|
Lecture #34
|
Computation of Minimum-Cost Paths: Dijkstra's Algorithm (Slides from class with example worked out)
|
|
Lecture supplement:
|
|
Proof of Lemma 5 in the Notes on Breadth-First Search
|
|
First Tutorial:
|
Tutorial #21:
|
Discussion of Assignment 4
|
|
Second Tutorial:
|
Tutorial #22:
|
Graph Search
|
|
|
|
|
Week #13: Graphs and Their Algorithms, Concluded
|
|
|
|
Monday, April 11
|
Lecture #35
|
Computation of Minimum-Cost Spanning Trees: Prim's Algorithm (Slides from class with example worked out)
|
|
Wednesday, April 13
|
Lecture Time
|
Questions about Final exam
|
|
First Tutorial:
|
Tutorial #23:
|
Computation of Minimum-Cost Paths
|
|
Second Tutorial:
|
Tutorial #24:
|
Computation of Minimum-Cost Spanning Trees
|
|
Wednesday, April 13
|
Assignment 4
|
Due at 11:59 pm
|
|
|
|
|