Handout Revisions Log

Handouts (Lecures, Tutorials, Assignments, etc.) will sometimes need to be revised to correct errors or to add material. This page will provide a log of major changes made to handouts. If a handout is not listed in this revision log no major changes were made to it (This log will not usually note minor corrections of mis-spellings and grammatical errors)

Lecture Sketches

Quicksort Slides Handout

- September 10, 2014
- p 15, 16 : change of partition cost from N to N-1 adn associated modifications
- September 11, 2014
- p 16: Change of C_{N+1} in middle of page to C_{N-1}

Sorting Lower Bound & Radix Sort Slides Handout

- September 11, 2014
- p 11: \Omega(log n) changed to \Omega(n \log n)

AVL Trees Slides Handout

- October 2, 2014
- Page 17 fixed ordering in “h” row

B-Trees Slides Handout

- October 2, 2014
- Page 4 m-1 Children -> m-1 keys

Randomized Quicksort & Selection Slides Handout

- October 2, 2014
- P25, line 6 “Then E(X_i) \le 1 ½” -> “Then E(X_i) \le 2”

Divide & Conquer Intro and Polynomial Multiplication Slides Handout

- October 2, 2014
- P6 Added another example to first case
- P7 Fixed typos and reformatted page
- P20. Fixed small typos
- P24 Corrected Katsuba to Karastuba
- October 7, 2014
- P 5 Fixed Typo in Divide Section
- Last Page Corrected running time of Karatsuba multiplication

Deterministic Selection Notes

- October 7, 2014
- Cleaned up derivation of c at the end of handout

FFTs and Polynomial Multiplication Slides

- October 7, 2014
- Added pages at the end describing matrix formulation of FFTs
- October 9, 2014
- P. 37 of PDF Fixed typos and added color emphasis
- November 5, 2014
- P 2. Fixed typo

Greedy Algorithms and Fractional Knapsack Slides Handout

- November 5, 2014
- p 13, fixed typos

Huffman Coding Slides Handout

- October 13, 2014
- p 26, changed B(H) to B(H')

Dijkstra's Shortest Path Algorithm Slides

- October 23, 2014
- p 15, 27 modified descriptions
- Added new pages 28, 29

- October 29, 2014
- P 13, fixed some typos

Introduction to Dynamic Programming Slides Handout

- November 5, 2014
- Major Changes all through the slides

Chain Matrix Multiplication Slides Handout

- November 5, 2014
- Major Changes all through the slides

Network Flow Slides Handout

- November 20, 2014
- P 34, added more explanation to Edmonds-Karps analysis

- November 20, 2014
- Various small typo fixes
- November 24, 2014
- p.18, changed x mod to k mod
- p 25, 26, inserted missing mod p
- November 25, 2014
- p 17,19, For Quadratic Hashing changed "c_1 + c_2 i^2" to "c_1 i + c_2 i^2"
- p. 20, removed repeated words
- p. 25,26, corrected typo in definition of r,s
- p 25, added some clarification to explanation

Closest Pairs Slides Handout

- November 24, 2014
- Fixed many typos
- November 25, 2014
- pp 21,23 Added clarifications in middle of pages
- November 26, 2014
- p 9, fixed typo on 2nd line
- p 12, fixed typo on 5th line
- November 27, 2014
- p 10, middle page, changed x coordinate to y coordinate

Linearity of Expectation Slides Handout

- November 24, 2014
- P 4, fixed typo in middle of page (missing summation)

Tutorials

Problem Set 1

- September 11, 2014
- Problem 5: 2nd bullet point. Fixed typo and changed interval from half-open half-closed to half-cloded half-opn (this made the proof sketch shorter)

- September 18, 2014
- Problem 4. Fixed the definition of skyline vectors to correct error found in tutorial

- November 20, 2014
- Added Missing Capacity in Problem 1 figure

- November 28, 2014
- Clarified the notation in Problem 3 (b) in the way discussed in the turtorial

Assignments

Assignment 1

- October 6, 2014
- in 1b, logn changed to h
- October 19, 2014
- In problem 5, added two more termination conditions, for 1X2 and 2X1 matrices
- October 26, 2014
- Missing part added to solution of Problem 3(a)

Assignment 2

- October 25, 2014
- Typo in solution to problem 3(b) corrected. Equation should be ...-n-4, not ..-n-3.
- October 27, 2014
- Fixed other typos in solution of problem 3(b). Also added alternate proof of cost of 3(b).

Assignment 4

- November 24, 2014
- flow/capacity values added for E->D edge in problem 4 diagram

Math Background

- October 27, 2014
- Added some more description to the Master Theorem part

Return to COMP3711H Fall 2014 Home Page