Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Background.
• Heaps.
• Inserting into Heaps.
• Removing from Heaps.
• Heap Sort.

Preliminaries

Admin

• How well do you remember heaps and heap sort?
  • Really well
  • Somewhat
  • Barely

Upcoming Work

• For Wednesday: Work on the Exam
• For next Wednesday: The Exam

Extra Credit

• Don't forget that you can send these to me in advance!

Academic

• CS Table Tuesday at noon: NSA Barbie
• CS Table Thursday: Blake

Peer

Exam 1

• Five problems. Blind grading.
• Problem 1: Find an algorithm with a triply-nested loop and do the summation analysis.
• Problem 2: For the recurrence relation T(N) <= 2T(N/3) + T(2N/3) + cN (a) draw the recurrence tree, (b) solve using master theorem or estimate using top-down or bottom-up models; (c) prove.
• Problem 3: Three proofs involving big-O notation
  • I can drop the lower order term: if f(n) is in O(g(n)) and h(n) is in O(f(n) + g(n)) then h(n) is in O(g(n) )
  • I don't care about constant multipliers if f(n) is in O(c*g(n)) then f(n) is in O(g(n))
  • I can combine functions if f(n) is in O(g(n)) and h(n) is in O(g(n)) then (f(n) + h(n)) is in O(g(n))
  • Optional: If f(n,k) is in O((n-1)(k-1)), then f(n,k) is in O(nk).
• Problem 4: Show the correspondence between insertion in 2-3-4 trees and insertion in red-black trees.
• Problem 5: Merge sort with only n/2 scratch space.

Questions

Is this Sam's normal: "Use any reasonable resource, but no posting questions?"

Yes.

Lower Bounds on Comparison-Based Sorting

n! leaves = Theta(2^(nlogn))

Weak proof by induction:

Base cases: n = 1, n = 2

Inductive cases:

• Step 1: n! = n*((n-1)!)
• Inductive hypotheseis: (n-1)! =~ 2^((n-1)log(n-1))
• Step 2: n! =~ n * 2^((n-1)log(n-1))
• n! =~ 2^(logn) * 2^((n-1)log(n-1))
• n! =~ 2^(logn) * 2^((n-1)log(n)*(log(n-1)/log(n)))
• For sufficiently large n, log(n-1)/log(n) is pretty damn close to 1
• n! =~ 2^(logn) * 2^((n-1)log(n))
• n! =~ 2^(logn + (n-1)log(n))
• n! =~ 2^(nlogn)

Proof by Authority: According to famous people like Knuth, n! =~ 2^(nlogn)

The tree has 2^(nlogn) leaves. The minimum height of a tree with k leaves is log(k). So, the tree has minimum height log(2^(nlogn)) = nlogn.

Background

• Merge sort: O(nlogn), but O(n) space
• Quicksort: O(1) space, O(nlogn) expected running time, complex analysis; some bad cases - If you pick pivots badly, it's O(n^2)
  • Pick randomly - really complex analysis
  • Pick the first element in the subarray, but permute the array randomly first. - similarly complex analysis
• Heapsort: O(nlogn) always, O(1) extra space

Heaps

Key ideas:

• Heaps are binary trees with certain properties
  • The value in a node is higher priority than the values of the nodes below it (higher priority might be "larger" or "smaller" or ...)
  • The tree is nearly complete
    • Either complete or ...
    • All but the bottom level are complete and last level is all at the left.
• Heaps implement priority queues
• We can store heaps in arrays
  • Using a simple model of where children go
• If we can implement insert and remove in O(height), we get O(nlogn) sorting by: INSERT EVERYTHING; REMOVE EVERYTHING IN ORDER

Inserting into Heaps

• Two properties to maintain. Which is harder? It turns out that nearly complete is harder.
• So put the new value in where it maintains near completeness
• Now, restore the other property; Repeatedly swap with parent if higher priority than parent

Removing from Heaps

• Two properties to maintain: near completeness and heap property
• Maintain near completeness by putting the rightmost bottom element at the top
• Repeatedly swap with higher priority child until swapping is done

Heap Sort

• Put all the values in an array (or start with all the values in the array) using breadth-first ordering of nodes.

• Turn the array into a heap by calling swap-up from postions 1 to n-1

  for k = n-1 down to 1
    swap(A, 0, k)
    swapDown(A, 0)
  

• This requires us to be able to identify the indices of children and parent

  left child of value at position k: 2k+1
  right child of value at position k: 2k+2
  parent of value at position k: floor((k-1)/2)