CS计算机代考程序代写 algorithm Hashing and Quicksort

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