Hashing and Quicksort
Finishing up some hashing odds and ends
Announcements
• PS1 marks to be returned by June 14th
• TA office hours next week to go over Q2 and Q3
• Practice Test will be available by Sunday June 13th
Test 1
• June 19th, 11:30am – 2pm EST
• Everything up to and including the end of hashing from today
• Aid Sheet Required – must be submitted with answers or 10% deduction
• No other aids – not notes, text, people or websites
• 2 hours to write within a 2.5-hour window
• On MarkUs
• You can ask questions during the test through Piazza private messages
• Typed or hand-written
• Submission: type restricted to PDF or photo. Please name your files properly if you can
• Need to start before 11:59 am ETA.
• More details on Quercus (required reading)
Hash Functions
Finding a good hash function appears essential to the
assumption of simple uniform hashing
What do we want in a good hash function?
•
•
•
Step 1: from string or key to natural number k
Chalk Talk
Step 2: from natural number k to m
• Division Method
• Multiplication Method
• Lots of Heuristics (see textbook)
Chalk Talk
Chalk Talk Big Picture: Hashing vs. Balanced Tree
Chalk Talk Quicksort: Worst Case – Upper bound
Chalk Talk Quicksort: Worst Case – Lower Bound
Chalk Talk Quicksort: Average Case
Chalk Talk
Chalk Talk
Chalk Talk
Classic Quicksort Summary
Quicksort performs well on _______________
Quicksort performs poorly on ________________
Big Question: Can we guarantee the “average” performance on
“average”?
Zoom Poll Review
Why is it that quicksort performs so poorly on sorted input?
Which element did we select as the pivot?
Would it be better if we selected the last element of A as pivot?
What about the middle element?
What about a random element?
Zoom Chat
Randomized Quicksort
• Average-case analysis depended on each permutation equally likely
• Instead of relying on distribution of inputs, randomize algorithm by
picking random element as pivot
• Random behavior of algorithm on any fixed input is equivalent to
fixed behavior of algorithm on uniformly random input
Expected worst-case time of randomized algorithm on every
single input is 𝛳 (n log (n))