Course Schedule, CPSC 331, Fall 2008

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

 Tentative Course Schedule

Week #1: Introduction to Correctness of Algorithms

Monday, September 8 Lecture #1 Introduction to CPSC 331
Wednesday, September 10    Lecture #2 Principles of Testing
Friday, September 12 Lecture #3 Proofs of Correctness
 
Tutorial Exercise: Review of Java Programming Fundamentals
 

Week #2: Introduction to the Analysis of Algorithms

Monday, September 15 Lecture #4 Proofs of Correctness (continued)
Wednesday, September 17 Lecture #5 Introduction to Algorithm Analysis
Friday, September 19 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, September 22 Lecture #7 Asymptotic Notation
Assignment 1 Set (due in 2 weeks)
Wednesday, September 24 Lecture #8 ADTs, Interfaces, and the Java Collections Framework
Friday, September 26 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, September 29 Lecture #10 Stacks
Wednesday, October 1 Lecture #11 Queues
Friday, October 3 Lecture #12 Binary Search Trees: Definition and Searching
 
Tutorial Exercise: Asymptotic Notation and Standard Functions
 

Week #5: Binary Search Trees

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

Week #6: Binary Search Trees, Concluded

Monday, October 13 Thanksgiving No lecture
Wednesday, October 15 Lecture Time Questions about Term Test 1
Term Test 1 6:00–7:30pm in ICT 121
Friday, October 17 Lecture #16 Red-Black Trees: Deletions
 
Tutorial Exercise: Ordered Sets, Mappings, and Binary Search Trees
 
 

Week #7: Hash Tables

Monday, October 20 Lecture #17 Average Case Analysis of Binary Search Trees
Wednesday, October 22 Lecture #18 Hash Tables with Chaining
Friday, October 24 Lecture #19 Open Addressing
Assignment 2 Due at 4:30 pm
Assignment 3 Set (due in 2 weeks)
 
First Tutorial: Term Test 1 Solutions
Second Tutorial Red-Black Trees
 
 

Week #8: Searching and Sorting

Monday, October 27 Lecture #20 Hash Functions
Wednesday, October 29 Lecture #21 Algorithms for Searching
Friday, October 31 Lecture #22 Classical Sorting Algorithms
 
Tutorial Exercise: Hash Tables
 

Week #9: Searching and Sorting, Continued

Monday, November 3 Lecture #23 Merge Sort
Wednesday, November 5 Lecture #24 Binary Heaps
Friday, November 7 Lecture #25 Operations on Binary Heaps
Assignment 3 Due at 4:30 pm
Assignment 4 Set (due in 2 weeks)
 
Tutorial Exercise: Algorithms for Searching
 

Week #10: Searching and Sorting, Concluded

Monday, November 10 Reading Days No lecture
Wednesday, November 12 Lecture #26 Heap Sort
Friday, November 14 Lecture #27 Priority Queues
 
Tutorial Exercise: Algorithms for Sorting
 

Week #11: Graphs and Their Algorithms

Monday, November 17 Lecture #28 Quicksort
Wednesday, November 19 Lecture Time Questions about Term Test 2
Term Test 2 6:00–7:30pm in ICT 121
Friday, November 21 Lecture #29 Graphs and Their Representations
 
First Tutorial: Heaps and Heap Sort
Second Tutorial: Quicksort
 

Week #12: Graphs and Their Algorithms, Continued

Monday, November 24 Lecture #30 Trees and Spanning Trees
Assignment 4 Due at 4:30 pm
Assignment 5 Set (due in 2 weeks)
Wednesday, November 26 Lecture #31 Depth-First Search
Friday, November 28 Lecture #32 Breadth-First Search
BFS: Proof of a Key Lemma
 
First Tutorial: Term Test 2 Solutions
Second Tutorial: Graphs and their Representations
 

Week #13: Graphs and Their Algorithms, Concluded

Monday, December 1 Lecture #33 Minimum-Cost Paths and Spanning Trees
Wednesday, December 3 Lecture #34 Prim's Algorithm
Friday, December 5 Lecture #35 Analysis of Prim's Algorithm
Prim's Algorithm: Proof of a Key Lemma
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/F08/schedule.php