Held: Friday, 2 October 2015

Back to Outline 15 - 2-3 Trees. On to Outline 17 - Heap Sort.

Summary

We begin our re-exploration of sorting algorithms, considering some of the issues you may have missed in CSC 207.

Related Pages

Overview

• Comparing sorting algorithms.
• O(nlogn) sorting algorithms.
• Lower bounds on sorting algorithms.

Administrivia

Upcoming Work

• For Monday: Work on the Exam
• For Friday the 9th: 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 Table 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.
  
  • 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 an algorithm with a triply-nested loop and do the summation analysis.
• Problem 2: For the recurrence relation .... (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
• 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.

Comparing Sorting Algorithms

Given two sorting algorithms, what are some criteria you might use in deciding which is better for your particular applications.

Here are some I've come up with:

• Running time
  • Asymptotic: Expected
  • Asymptotic: Worst case
  • Actual
  • Based on distribution of data
• Stable or not
• Extra space required
• In place or out of place

O(nlogn) Sorting Algorithms

You should know three (plus or minus)

• Merge sort (top-down and bottom-up)
• Quick sort (well ...)
• Heap sort (we'll revisit this one on Monday)

Lower Bounds on Comparison-Based Sorting Algorithms

• The decision tree model!
  • We show the positions of the two values we compare
  • We have two choices: One is less than the other or one is greater than the other. (We'll assume unique values wlog.)
  • We gather knowledge at each step.
  • At the leaves, we have instructions for permuting the original
• Let's build a decision tree of 3 values (class project)
• Generalize: How many leaves are there in a tree for an array of n values?
• What's the best case height for that tree?