COMP 3711H -  Fall 2014
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

Kruskal's Algorithm Slides

• 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

Hashing Slides   Handout

• 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)

Problem Set 2

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

Problem Set 9

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

Problem Set 10

• 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