HW1 Submitted!

Due yesterday @ 11:59pm

Homework Tips!

• Start EARLY!
• If you start TODAY and run into an issue, spend 10 minutes. If you can’t figure it out, post on Piazza!
• Why does waiting until the last minute not work in software engineering??

HW2 Released Today @ 5pm!

Due Next Tuesday @ 11:59pm

1. Welcome to COMP 285

Lecture 6: Substitution Method & Median Selection

COMP - 285

Advanced Algorithms

Lecturer: Luis Perez (laperez@ncat.edu)

Big Topics!

​

• Advanced Methods for Solving Recurrence Relations
• Substitution Method + Practice with Induction
• The k-Select Problem!

From Last Lecture

• We learned the “Master Method” to make our lives easier
• It just codifies (eg, makes easy) a calculation we could do ourselves if we wanted to (eg, we could always draw the tree, add it all up!)

The Substitution Method

• Another way to solve recurrence relations
• More general than master method
• Step 1: Generate a guess!
• Step 2: Try to prove your guess is correct
• Step 3: (Profit!!)

A first example

• Let’s return to our good friend:

A first example

• Let’s return to our good friend:

​

• Master Theorem says:

A first example

• Let’s return to our good friend:

​

• Master Theorem says:

​

• Let’s prove this via substitution

Step 1: Guess the Answer!

Step 2: Prove the guess is correct

Induction!

Step 2: Prove the guess is correct

• Inductive Hypothesis: T(n)=n(log⁡(n)+1)
• Base Case (n=1): T(1)= 1 = 1 * (log(1) + 1)
• Inductive Step:
• Assume Inductive Hyp. for 1 <= n < k
• Suppose that T(n)=n(log⁡(n)+1) for all 1≤n<k.
• Prove Inductive Hyp. for n=k:
• T(k) = 2⋅T(k/2)+k by definition
• T(k) = 2⋅(k/2 (log⁡(k/2)+1))+k by induction.
• T(k) = k(log⁡(k)+1) by simplifying.
• So Inductive Hyp. holds for n=k.
• Conclusion: For all n≥1, T(n)=n(log⁡(n)+1)

​

Step 3: Profit

• Pretend like you never did Step 1, and just write down:
• Theorem: T(n)=O(n log⁡(n))
• Proof: [Whatever you wrote in Step 2]

​

Big Topics!

​

• Advanced Methods for Solving Recurrence Relations
• Substitution Method + Practice with Induction
• The k-Select Problem!

Another example (practice makes perfect!)

Step 1: Make a guess - maybe from diving inspiration!

Step 2: Prove it, working backwards to get the constant C

Inductive Step

Step 2: Prove it, working backwards to get the constant C

Step 3: Profit

Isn’t Master Theorem enough?

No!

Let’s Review What We’ve Learned So Far…

• A recurrence relation expresses 𝑇(𝑛) in terms of 𝑇(less than 𝑛)
• For example, 𝑇(𝑛)=2⋅𝑇(𝑛/2)+11⋅𝑛
• Two methods of solution:
• Master theorem (aka, generalized “tree method”)
• Substitution method (aka, guess and check)

​

​

The Master Theorem

number of subproblems

Factor by which input size shrinks

word needed to combine the solutions

The Substitution Method

• Another way to solve recurrence relations
• More general than master method
• Step 1: Generate a guess!
• Step 2: Try to prove your guess is correct
• Step 3: (Profit!!)

A fun recurrence relation…

• 𝑇(𝑛) ≤ 𝑇(𝑛/5)+𝑇(7𝑛/10)+𝑛 for 𝑛 > 10.
• Base case: 𝑇(𝑛)=1 when 1≤𝑛≤10

Step 1: Guess the Answer!

• Trying to work backwards gets gross fast…
• We can also just try it out.
• Let’s guess O(n) and try to prove it.

​

Step 2: Proof your guess is right!

• Inductive Hypothesis: 𝑇(𝑛)≤𝑪𝑛
• Base case: 1=𝑇(𝑛)≤𝑪𝑛 for all 1≤n≤10
• Inductive step:
• Let k > 10. Assume that the IH holds for all n so that 1≤𝑛<𝑘.
• 𝑇(𝑘) ≤ 𝑘 + 𝑇(𝑘/5) + 𝑇(7𝑘/10)

≤𝑘+𝑪⋅(𝑘/5)+𝑪⋅(7𝑘/10)

=𝑘+𝑪/5 𝑘+7𝑪/10 𝑘

≤𝑪𝑘 ??

(aka, want to show that IH holds for n=k).

Conclusion: There is some 𝑪 so that for all 𝑛≥1, 𝑇(𝑛)≤𝑪𝑛. By the definition of big-Oh, T(n) = O(n).

​

​

​

Step 2: Proof your guess is right!

• Inductive Hypothesis: 𝑇(𝑛)≤𝑪𝑛
• Base case: 1=𝑇(𝑛)≤𝑪𝑛 for all 1≤n≤10
• Inductive step:
• Let k > 10. Assume that the IH holds for all n so that 1≤𝑛<𝑘.
• 𝑇(𝑘) ≤ 𝑘 + 𝑇(𝑘/5) + 𝑇(7𝑘/10)

≤𝑘+𝑪⋅(𝑘/5)+𝑪⋅(7𝑘/10)

=𝑘+𝑪/5 𝑘+7𝑪/10 𝑘

≤𝑪𝑘 ??

(aka, want to show that IH holds for n=k).

Conclusion: There is some 𝑪 so that for all 𝑛≥1, 𝑇(𝑛)≤𝑪𝑛. By the definition of big-Oh, T(n) = O(n).

​

​

​

Step 3: Profit

• Inductive Hypothesis: 𝑇(𝑛)≤10 𝑛
• Base case: 1=𝑇(𝑛)≤ 10 𝑛 for all 1≤n≤10
• Inductive step:
• Let k > 10. Assume that the IH holds for all n so that 1≤𝑛<𝑘.
• 𝑇(𝑘) ≤ 𝑘 + 𝑇(𝑘/5) + 𝑇(7𝑘/10)

≤𝑘+10⋅(𝑘/5)+10⋅(7𝑘/10)

=𝑘+10/5 𝑘+7(10)/10 𝑘

≤10𝑘

Conclusion: For all 𝑛 ≥ 1, 𝑇(𝑛)≤10𝑛. By the definition of big-Oh, T(n) = O(n).

​

​

​

What did we learn?

• The substitution method can work when the master theorem doesn’t.
• For example, with different-sized sub-problems.
• Step 1: generate a guess
• Throw the kitchen sink at it.
• Step 2: try to prove that your guess is correct
• You may have to leave some constants unspecified till the end – then see what they need to be for the proof to work!!
• Step 3: profit
• Pretend you didn’t do Steps 1 and 2 and write down a nice proof.

Is this even useful!?

Yes! Many problems have recursive solutions where problem sizes are not just “take half”

The k-Select Problem

How would you solve?

• SELECT(A, k):
• A = MergeSort(A)
• return A[k-1]
• Running time is O(n log(n)).
• So that’s the benchmark….

​

Can we do better?

Let’s code it!

Goal: An O(n)-time algorithm

• SELECT(A, 1) (AKA, MIN(A)) :
• min = ∞
• for i=0, ..., n-1:
• If A[i] < ret:
• min = A[i]
• return min
• Time O(n) - Yay!

Can we keep going?

• SELECT(A, 2) (AKA, SECOND_MIN(A)) :
• min = ∞
• secondMin = ∞
• for i=0, ..., n-1:
• If A[i] < secondMin and A[i] < min:
• secondMin = min
• min = A[i]
• Else if A[i] < secondMin and A[i] >= min:
• secondMin = A[i]
• return secondMin

Can we keep going?

• SELECT(A, n/2) (AKA, MEDIAN(A)) :
• min = ∞
• secondMin = ∞
• thirdMin = ∞
• fourthMin = ∞
• This is not a good idea for large k (n/2 or n)
• Basically, this is just going to turn into something like INSERTIONSORT…and that was O(n²)

Next time!

​

• A better solution for the k-Select problem!
• The idea: divide & conquer!
• A little bit of randomized algorithms
• How familiar are folks with probability/statistics?
• ​

How was the pace today?

41