Previous slide
Next slide
Toggle fullscreen
Open presenter view
CompSci 260P: Week 10
Midterm 2 Review
Ryuto Kitagawa
University of California, Irvine
Before We Begin
As before, I will not discuss specific grades with anyone at this time
Any questions about your grade, the rubric, or detailed analysis of
solutions will be saved for private ed stem posts, office hours, and regrade
requests
I may attempt to answer questions about general strategies that were applied
If it takes more than 30 seconds, I will have to move on
Pizza Shop
No longer minimizing cook time
We favor customer
with weight
= time to bake customer
's pizza
= time customer
gets their pizza
Minimize the total weighted favor
Sort in decreasing order of
Show that this is the optimal greedy solution
Greedy Proof Strategy
Consider the solution OPT
How do we make OPT more like our solution?
Do this without making OPT worse!
The greedy algorithm sorts the values
Sorting hints towards proving this by considering inversions
Example
Proof
Find some
such that
Example:
Show that the swap only ever improves the solution!
Reminiscent of the Pizza Baking Time Problem
Proof
Calculate the contribution to the weighted sum for the
and
pizza
Let
be the time to start working on the
th pizza
Pizza
:
Pizza
:
Total Contribution:
Then consider what happens after the swap
Pizza
:
Pizza
:
Total Contribution:
Proof
Left hand side is the contribution after the swap
If
is negative, then we are improving
Recall that
Common Mistakes
Comparing inversions which are not consecutive
This causes all contributions between
and
to change, which must be addressed
Assuming the inversion is only at the first index
Isolating the variables
and
instead of considering their ratios
Unnecessarily attempting to prove using induction
While technically correct, this bogs us down in details
Not proving it!
Stating that it is worse is not sufficient
Missing Integer Problem
Vector
of
distinct
bit integers
contains all elements in
except
1
Goal:
Find the missing integer in
time
Constraint:
May only access elements using
bit[i, j]
Returns the
-th bit of
Missing Integer Problem
The Usual Suspects for D & C
Split the array directly in half
Sort elements then split in half
Neither of these usual suspects will get us anywhere
We must look deeper at the properties we have
Missing Integer Problem
We are looking at the bit representation of
Let us look at a small example:
Number
Binary
Number
Binary
0
000
4
100
1
001
5
101
2
010
6
110
3
011
7
111
Algorithm
Group all of the numbers with
at the
-th bit
Do the same for
Whichever group is smaller is missing their bit at
Recurse into the smaller group to get the rest of the bits
Analysis
Master theorem!
Common Mistakes
Defaulting to one of the usual suspects
Good instinct to try, but this strategy would ultimately not work out
Binary search is
too
fast!
Assuming the array is sorted
There is a
algorithm if the array is sorted
Problem statement did not specify
Sorting takes
time
Secretly using the
bit
operation
times
If you got the value of an integer, that took
time
If you compared two integers to each other, that took
time