—-
Divide and Conquer:
Sorted array: some form of binary search. Remember not to do something that
take O(n) time then the recurrence becomes T(n) = 2T(n/2) + c – runtime will become O(n).
If the array is not sorted, then think about merge in mergesort – O(nlogn).
In case, the property requires considering the relative position of the array-elements
(e.g., counting inversions), then it might be good to get the array sorted (merge)
as the subproblems are dealt with.
MST:
Cycle property
Cut property
Almost all problem’s proof will deal with adding an edge to some tree. This
will result in a cycle – then based on the type of the problem, either the
edge-wt will be minimum among all edges in the cycle (cut property) or the
edge-wt will be maximum among all edges in the cycle (cycle property).
Shortest path Dijkstra:
d(v) = d(u) + wt(u,v) where u->v. Review the problems from the homework
Remember: MST using Prims does not compute shortest path from a
source. Otherwise, Prims and Dijkstra would be identical.
Greedy:
Problem type: we need to select some subset of given elements to meet
an optimization objective (e.g., interval scheduling, interval coverage),
strategy: look a sequence from greedy, take a opt-sequence that does not
match with the greedy – pick the first mismatch and try to swap.
Problem type: we need to order all the given elements to meet an
optimization objective (e.g., minimize delay, maximize reward)
strategy: assume some opt-strategy has a pair that is inverse of the
greedy strategies order. Swap the inverted pair and argue the
inversion can be removed.
In both cases, you are swapping something
Some problems:
Chapter 4: Q15.
—————
Find the smallest number of intervals that overlaps with all other intervals.
(a variant of point coverage)
Find the interval with the largest endtime and covers the leftmost uncovered
interval. Left-most uncovered interval is the uncovered interval with the
smallest endtime.
Let Ik and I’ do not match. Let a is the left-most uncovered interval
for Ik, then that is also not covered I’ because end(I’) < end(Ik).
Copy-paste I'->Ik
————-
Given n jobs, each job takes unit time but has d_i is difficulty.
Reward for a job ending at time time j is (n-j)di.
Maximize the reward.
Order the jobs in decreasing order of difficulty.
Let there is an optimal schedule which has an inversion. That is the
J_p and J_q are ordered in such a way that J_p has lower difficulty
than J_q. These jobs would appear side-by-side in the order because if
they are not, one can find a pair, that will be.
Make your argument to remove the inversion. Write the reward
for J_p followed by J_q – (n-t)d_p + (n-t-1)d_q = R1
(n-t)(dp+dq) – d_q = R1
(assuming at time t J_p is done)
Write the reward for J_q followed by J_q
(n-t)d_q + (n-t-1)d_p = R2
(n-t)(d_p + d_q) – dp = R2
As d_p <= d_q, R2 >= R1. Inversion can be removed.
Chapter 5: Q1.
————-
Exercise – to do.
Given two sorted arrays A and B. We want to find the median of the overall
array.
Brute force: merge A and B. O(n) and then find the median – nth element.
Divide and conquer:
find the n/2th element in A – a
find the n/2th element in B – b
a < b means, b is larger that first n/2+1 elements in A and first n/2 elements in B. So, it is at least larger than n+1 Conclude: The median cannot be in the last n/2 elements of B. The median cannot be in the first n/2 elements of A. The median must be in the last n/2 elements in A and the first n/2 elements of B. What about b < a - can we just the flip the arrays and do the same reasoning. Yes. Find the n/4th element among the last n/2 elements - i.e., 3n/4 element in A - a Find the n/4 element among the first n/2 elements - i.e., n/4 element in B. - b The other case a > b is symmetric.
If a = b what happens? then they are both larger than n elements.
If there is only two elements – get the smaller of the two.