Course Schedule, CPSC 331, Winter 2008

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

 Tentative Course Schedule

Week #1: Introduction to Correctness of Algorithms

Monday, January 14 Lecture #1 Introduction to CPSC 331
Wednesday, January 16    Lecture #2 Principles of Testing
Friday, January 18 Lecture #3 Proofs of Correctness
 
Tutorial Exercise: Review of Java Programming Fundamentals
 

Week #2: Introduction to the Analysis of Algorithms

Monday, January 21 Lecture #4 Proofs of Correctness (continued)
Wednesday, January 23 Lecture #5 Introduction to Algorithm Analysis
Friday, January 25 Lecture #6 Getting From Pseudocode To a Bound on Running Time
 
Tutorial Exercise: Testing of Programs
 

Week #3: Introduction to Abstract Data Types and the Java Collections Framework

Monday, January 28 Lecture #7 Asymptotic Notation
Assignment 1 Set (due in 2 weeks)
Wednesday, January 30 Lecture #8 ADTs, Interfaces, and the Java Collections Framework
Friday, February 1 Lecture #9 Basic Data Structures
 
First Tutorial Exercise: Proofs of Correctness of Algorithms
Second Tutorial Exercise: Analysis of Running Time of Algorithms
 

Week #4: Basic Data Structures

Monday, February 4 Lecture #10 Stacks
Wednesday, February 6 Lecture #11 Queues
Friday, February 8 Lecture #12 Binary Search Trees: Definition and Searching
 
Tutorial Exercise: Asymptotic Notation and Standard Functions
 

Week #5: Binary Search Trees

Monday, February 11 Lecture #13 Binary Search Trees: Insertion and Deletion
Assignment 1 Due at 4:30 pm
Assignment 2 Set (due in 3 weeks)
Wednesday, February 13 Lecture #14 Introduction to Red-Black Trees
Friday, February 15 Lecture #15 Red-Black Trees: Rotations and Insertions
 
Tutorial Exercise: Stacks and Queues
 

February 18-22

Reading Week No lectures
 

Week #6: Binary Search Trees, Concluded

Monday, February 25 Lecture Time Questions about Term Test 1
Term Test 1 6:00–7:30pm in ENA 103
Wednesday, February 27 Lecture #16 Red-Black Trees: Deletions
Friday, February 29 Lecture #17 Average Case Analysis of Binary Search Trees
 
Tutorial Exercise: Ordered Sets, Mappings, and Binary Search Trees
 
 

Week #7: Hash Tables

Monday, March 3 Lecture #18 Hash Tables with Chaining
Assignment 2 Due at 4:30 pm
Assignment 3 Set (due in 2 weeks)
Wednesday, March 5 Lecture #19 Open Addressing
Friday, March 7 Lecture #20 Hash Functions
 
First Tutorial: Term Test 1 Solutions
Second Tutorial Red-Black Trees
 
 

Week #8: Searching and Sorting

Monday, March 10 Lecture #21 Algorithms for Searching
Wednesday, March 12 Lecture #22 Classical Sorting Algorithms
Friday, March 14 Lecture #23 Merge Sort
 
Tutorial Exercise: Hash Tables
 

Week #9: Searching and Sorting, Continued

Monday, March 17 Lecture #24 Binary Heaps
Assignment 4 Set (due in 2 weeks)
Wednesday, March 19 Lecture #25 Operations on Binary Heaps
Assignment 3 Due at 4:30 pm
Friday, March 21 Good Friday No lecture
 
Tutorial Exercise: Algorithms for Searching
 

Week #10: Searching and Sorting, Concluded

Monday, March 24 Lecture #26 Heap Sort
Wednesday, March 26 Lecture #27 Priority Queues
Friday, March 28 Lecture #28 Quicksort
 
Tutorial Exercise: Algorithms for Sorting
 

Week #11: Graphs and Their Algorithms

Monday, March 31 Lecture Time Questions about Term Test 2
Term Test 2 6:00–7:30pm in ENA 103
Wednesday, April 2 Lecture #29 Graphs and Their Representations
Friday, April 4 Lecture #30 Trees and Spanning Trees
Assignment 4 Due at 4:30 pm
Assignment 5 Set (due in 2 weeks)
 
Tutorial Exercise: Heaps and Heap Sort
 

Week #12: Graphs and Their Algorithms, Continued

Monday, April 7 Lecture #31 Depth-First Search
Wednesday, April 9 Lecture #32 Breadth-First Search
BFS: Proof of a Key Lemma
Friday, April 11 Lecture #33 Minimum-Cost Paths and Spanning Trees
 
First Tutorial: Quicksort
Second Tutorial: Graphs and their Representations
 

Week #13: Graphs and Their Algorithms, Concluded

Monday, April 14 Lecture #34 Prim's Algorithm
Wednesday, April 16 Lecture #35 Analysis of Prim's Algorithm
Prim's Algorithm: Proof of a Key Lemma
Friday, April 18 Lecture #36 Other Graph Problems and Algorithms
Assignment 5 Due at 4:30 pm
 
First Tutorial: Graph Traversals and Minimum Cost Paths
Second Tutorial: Graph Algorithms: Minimum-Cost Spanning Trees
 

This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/W08/schedule.php