Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Comparing sorting algorithms.
• O(nlogn) sorting algorithms.
• Lower bounds on sorting algorithms.

Preliminaries

Admin

Upcoming Work

• For Monday: Work on the Exam
• For Wednesday the 16th: Exam 1

Extra Credit

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

Academic

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

Peer

• Women's Soccer, Saturday or Sunday at 11 am
• Men's Soccer, Saturday or Sunday at 2 pm

Exam 1

• My idiocy deleted the exam.
  cd $(CSC301)/assignments pushd $(CSC151)/assignments cp $(CSC207)/assignments/exam.01.sect . EDIT EDIT EDIT DISCONNECT cd $(CSC301)/assignments vi exam.01.sect NO SUCH FILE cp ($CSC151)/assignments/exam01.sect . cd $(CSC151)/svnrepo svn revert exam1.2015F.sect
  • Make the exam in the 151 directory.
  • Realize the exam in the 151 directory is normally a symbolic link to a shared exam.
  • Copy the exam from the 151 directory to the 301 directory
  • svn revert the shared exam
  • Realize that you copied the link not the exam
• Here's a summary. I'll rewrite tomorrow.
• Five problems. Blind grading.
• Problem 1: Find a real algorithm with a triply-nested loop and do the summation analysis.
• Problem 2: For the recurrence relation T(N) <= T(2N/3) + 2T(N/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))
• 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

Comparing sorting algorithms

What kinds of things might you ask about the data set?

• Size:
  • Will the data set fit into memory?
• Arrangement
  • Is it already mostly sorted or completely random?
• Duplicate data
  • Are there duplicate elements or are all elements distinct
• How are the data stored?
  • Array, linked list, etc.
• How will you access it later?

What kinds of things might you ask about the sorting algorithm? (What requirements you might have on the sorting algorithm?)

• Locality of comparisons for large data sets.
• Memory overhead
  • Quicksort: Constant; sort in place
  • Heapsort: Constant; sort in place
  • Mergesort: O(n)
• What's the asymptotic complexity?
  • Worst case
  • For the expected data
  • Average case
• What's the real running time (on your class of machine/for these data)?
• Is it stable?
  • Stable sorting routines keep "equal" values in the same order they were in before.

General algorithm strategy:

• Come up with a solution
• Do asymptotic analysis
• Ask if you can do better
• Repeat the above until you can't do better
• Attempt to prove that you can't do any better

O(nlogn) sorting algorithms

• Merge sort
  • Top-down (recursive)
  • Bottom-up (iterative)
  • Requires overhead
• Quicksort
  • Top-down (recursive)
  • Expect O(nlogn)
  • Requires luck
• Heapsort
  • Top-down (recursive)
  • No extra overhead, no luck, but weird
  • Doesn't seem faster in practice

Lower bounds on sorting algorithms

Theorem: For algorithms based only on comparing values in an array, sorting is Omega(nlogn)

Detour: Sorting tree. Provide a visualization of how a sorting routine determines how to permute the array to sort it.

Any comparison-based sorting routine can be described by a sorting tree.

The best comparison-based sorting routine will require the height of the shortest sorting tree.

How many leaves are there in a sorting tree for an array of N values (what's the minimum number of such leaves)? N!, the number of permutations of N values.

Depth of tree is O(log(N!)) is approximately O(NlogN)

Lemma: 2^(N!) is in Theta(2^(NlogN))

Proof by induction