Dec 13 - Revised notes for Lecture 12 and 31 have been posted, fixing
mistakes in the add operation (Lecture 12, slide 23) and the BFS algorithm
(Lecture 31, slide 9).
Dec 10 - Answer to 6(a) on the sample final is (3,2,1,6,24,18). Answer to 6(b) is (3,2,1) and (24,18).
Dec 10 - Additional office hours during the exam period will be:
Dec 16: 13:00 - 15:00
Dec 17: 13:00 - 16:00
Dec 10 - Some information about the final exam:
The exam is cummulative (everything covered in class is examinable)
Similar in style and length to the sample exam.
Short answer questions will likely also ask for a brief justification
(one mark for the answer, one for the justification).
You will not be asked for Java code (use pseudocode for algorithms)
You will not be asked for any complete proofs of correctness.
Summary of topics:
Analysis of algorithms:
Correctness: definitions, loop invariants, proof of termination
(no complete proofs of partial correctness)
Testing: definitions and principles, designing test cases
Asymptotic analysis: definitions, proving results based on the
definitions, runtime analysis of iterative algorithms, expressing
running times of recursive algorithms using recurrence relations.
Data structures and algorithms:
Give specification of requirements for an algorithm.
Define ADTs (spec. of requirements for the ADTs methods).
Know examples of applications.
Be able to trace examples for algorithms, give pseudocode, give
key loop invariants, prove termination.
Know running time results (worst and average case, best case where
relevant). Proofs for iterative algorithms, give recurrence
relations for recursive algorithms.
Be able to handle some variations (eg. kMerge question on sample
exam) and different applications (eg. TreeSort question on sample
term test).
You are responsible for all data structures and algorithms covered in class.
One exception: you are not expected to memorize all the cases and
subcases of insertion and deletion for red-black trees.
Nov 29 - Complete versions of the notes on heaps, heap operations,
heap applications, and quicksort are available on the course schedule page.
Nov 29 - The grades for Term Test 2 are now available through Blackboard.
The tests will be handed back during the labs on Wed, Dec. 1; solutions
will be discussed in the lecture that day. The model solutions are available
on the "tests" page. Concerns about the grading
hould be addressed directly to Prof. Jacobson.
For small corrections (such as addition errors), just show
the test to me. For appeals of the grading, please submit your test along with
a written explanation of which question(s) should be remarked and why you
think they deserve more credit.
Nov 29 - Model solutions to Assignment 3 are available on the
"Assigment 3" page.
Nov 19 - Assignment 4 has been posted, available through the
"assigments" page.
Nov 15 - Term Test 2 (Wednesday, Nov 24 from 18:00 - 19:30 in ST 143) will cover all material up to and including the Lecture 23 notes (Merge Sort). Complete notes for Lecture 23, including the inductive proof of the upper bound on T(n), are now available.
Nov 10 - My office hours for the week of Nov 22-26 will be on
Wednesday, Nov 24 from 11:00 - 12:45.
Nov 10 - Model solutions to Assignment 2 are available on the
"Assigment 2" page.
Nov 8 - My office hours for this week and the following week will be
on Wednesday (Nov 10 and 17) from 11:00 - 12:45.
Nov 5 - Due to an unavoidable conflict, my office hours today are
cancelled. If you have any questions, please send them by email, or make
an appointment with me for an alternate time.
Oct 29 - Assignment 3 has been posted, available through the
"assigments" page.
Oct 25 - The grades for Term Test 1 are now available through Blackboard.
The tests will be handed back during the labs on Wed, Oct. 27, and solutions
will also be covered. The model solutions available on the
"tests" page have been updated to indicate some of
the common mistakes. Concerns about the grading should be addressed directly to Prof. Jacobson. For small corrections (such as addition errors), just show
the test to me. For appeals of the grading, please submit your test along with
a written explanation of which question(s) should be remarked and why you
think they deserve more credit.
Oct 20 - The material on Average Case Analysis of Binary Search Trees
will not be covered. The lecture on Friday, Oct 22 will begin by finishing
the discussion of binary search trees and continue with the first lecture
on red-black trees. The tutorial on Wed, Oct 27 will be used to discuss
the solutions of Term Test 1.
Oct 20 - Solutions to Term Test 1 are available on the
"tests" page.
Oct 20 - Grades for Assignment 1 are now available and can be viewed through blackboard. Concerns about the grading (if any) should be addressed to
Isheeta (inagris@ucalgary.ca).
Oct 18 - Extra office hours before Term Test 1 will be
Tuesday, Oct 19, 13:00 - 15:00
Wednesday, Oct 20, 11:00 - 12:45
Oct 18 - Model solutions to Assignment 1 are available on the
"Assigment 1" page.
Oct 15 - Term Test 1 (Wednesday, Oct 20 from 18:00 - 19:30 in ST 143) will cover all material up to and including Slide 11 (binary search tree exmaple) of the Lecture 13-14 notes.
Oct 8 - Assignment 2 has been posted, available through the
"assigments" page.
Sept 24 - As I am currently out of town, my office hours today are cancelled (my apologies for forgetting to mention this on Wednesday!). If you need to see me before my regular office hours next Friday, please send me an email and we can set up an appointment for sometime after I'm back on Tuesday.
Sept 22 - Assignment 1 has been posted, available through the
"assigments" page.
Sept 13 - Please note that the date/location for the two term tests listed on the Lecture 1 notes handout out in class today is incorrect. The correct information is on your course information sheet and on the course web page, namely Oct 20 and Nov 24, both in ST 143. The version of the lecture 1 notes available on the course web page has been corrected.
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F10/news.html