Course Schedule, CPSC 331, Winter 2017

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  java -  references -  Mike Jacobson

 Tentative Course Schedule

Week #1: Introduction to Correctness of Algorithms

Monday, January 9 Lecture #1 Introduction to CPSC 331
Wednesday, January 11    Lecture #2 Correctness of Algorithms and Programs
Friday, January 13 Lecture #3 Correctness of Algorithms and Programs (continued)
 

Week #2: Introduction to Testing

Monday, January 16 Lecture #4 Correctness of Algorithms and Programs (continued)
Wednesday, January 18 Lecture #5 Principles of Testing
Friday, January 20 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 20 Assignment 1 Set (due Monday, February 6)
 

Week #3: Introduction to the Analysis of Algorithms

Monday, January 23 Lecture #7 Introduction to Algorithm Analysis
Wednesday, January 25 Lecture #8 Introduction to Algorithm Analysis (continued)
Friday, January 27 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, January 30 Lecture #10 Abstract Data Types, Data Structures, and Their Implementations
Wednesday, February 1 Lecture #11 Basic Data Structures
Friday, February 3 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 6 Lecture #13 Stacks
Wednesday, February 8 Lecture #14 Queues
Friday, February 10 Lecture #15 Searching
 
First Tutorial: Tutorial #7 Arrays and Lists
Second Tutorial Tutorial #8 Stacks
 
Monday, February 6 Assignment 1 Due at 11:59 pm
Monday, February 6 Assignment 2 Set (due Friday, March 3)
 

Week #6: Basic Data Structures; Dictionaries

Monday, February 13 Lecture #16 Classical Sorting
Wednesday, February 15 Lecture #17 Classical Sorting (continued)
Friday, February 17 Lecture #18 Binary Search Trees
 
Lecture supplement: Tree Traversals
 
First Tutorial: Tutorial #9 Queues
Second Tutorial: Tutorial #10 Algorithms for Searching
 

February 20-24

Reading Week No lectures
 

Week #7: Red-Black Trees

Monday, February 27 Lecture #19 Binary Search Trees (continued)
Wednesday, March 1 Lecture #20 Introduction to Red-Black Trees
Friday, March 3 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 Discussion of Assignment 2
Second Tutorial: Tutorial #12 Classical Sorting Algorithms
 
Friday, March 3 Assignment 2 Due at 11:59 pm
 

Week #8: Hash Tables

Monday, March 6 Lecture #22 Red-Black Trees: Deletions
Wednesday, March 8 Lecture Time Questions about the Midterm
Friday, March 10 Lecture #23 Hash Tables with Chaining
 
Lecture supplement: Additional Kinds of Search Trees
 
First Tutorial Tutorial #13 Midterm Review (solutions to sample midterm)
Second Tutorial: Tutorial #14 Binary Search Trees
 
Wednesday, March 8 Midterm 5:00–6:30pm in EDC 179
Friday, March 11 Assignment 3 Set (due Monday, March 27)
 

Week #9: Advanced Sorting

Monday, March 13 Lecture #24 Hash Tables with Open Addressing
Wednesday, March 15 Lecture #25 Merge Sort
Friday, March 17 Lecture #26 Binary Heaps
 
Lecture supplement: Hash Functions and Additional Hashing Strategies
 
First Tutorial Tutorial #15 Red-Black Trees
Second Tutorial: Tutorial #16 Hash Tables
 

Week #10: Advanced Sorting, Concluded

Monday, March 20 Lecture #27 Operations on Binary Heaps
Wednesday, March 22 Lecture #28 Applications of Binary Heaps
Friday, March 24 Lecture #28 Applications of Binary Heaps (cont.)
 
First Tutorial Tutorial #17 Discussion of Assignment 3
Second Tutorial: Tutorial #18: Merge Sort
 

Week #11: Graphs and Their Algorithms

Monday, March 27 Lecture #29 Quicksort
Wednesday, March 29 Lecture #30 Graphs and Their Representations
Friday, March 31 Lecture #31 Trees, Spanning Trees, and Subgraphs
 
Lecture supplement: Proof of Tree Propeties
 
First Tutorial: Tutorial #19: Binary Heaps and Their Applications
Second Tutorial: Tutorial #20: Quicksort
 
Monday, March 27 Assignment 3 Due at 11:59 pm
Monday, March 27 Assignment 4 Set (due Wednesday, April 12)
 

Week #12: Graphs and Their Algorithms, Continued

Monday, April 3 Lecture #32 Graph Search: Depth-First Search (Slides from class with example worked out)
Wednesday, April 5 Lecture #33 Graph Search: Breadth-First Search (Slides from class with example worked out)
Friday, April 7 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: Introduction to Graphs
 

Week #13: Graphs and Their Algorithms, Concluded

Monday, April 10 Lecture #36 Computation of Minimum-Cost Spanning Trees: Prim's Algorithm (Slides from class with example worked out)
Wednesday, April 12 Lecture Time Questions about Final exam
 
First Tutorial: Tutorial #23: Graph Search
Second Tutorial: Tutorial #24: Computation of Minimum-Cost Paths and Spanning Trees
 
Wednesday, April 12 Assignment 4 Due at 11:59 pm
 

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/W17/schedule.php