程序代写代做代考 algorithm COMP 250

COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 10-2 : Recurrences
Giulia Alberini, Fall 2020

WHAT ARE WE GOING TO DO IN THIS VIDEO?
 Recurrences

ALGORITHM ANALYSIS
 We would like to find a function 𝑇(𝑛) that describes the running time of an algorithm given an input size 𝑛.
It is relatively easy to determine 𝑇(𝑛) when our algorithms only have loops. (e.g. insertion sort from week 6)
But how do we determine 𝑇(𝑛) for a recursive algorithm?

ALGORITHM ANALYSIS
Example: Suppose a list has 𝑛 elements, what is 𝑇(𝑛) for the following algorithm?
reverse(list) {
if(list.size()==1) {
return; }
firstElement = list.removeFirst();
reverse(list); // now the list has n-1 elements
list.addLast(firstElement);
}

RECURRENCES
“A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs”
e.g.Fibonacci 𝐹 𝑛 =𝐹 𝑛−1 +𝐹 𝑛−2
We use recurrences to express the overall running time 𝑇(𝑛) of an algorithm with input size 𝑛 in terms of the running time on smaller inputs.
Note that for Fibonacci number 𝑛 is an input value. It is NOT the input size!

EXAMPLE1: REVERSINGALIST
reverse(list) {
if(list.size()==1) { return;
}
firstElement = list.removeFirst(); reverse(list); list.addLast(firstElement);
}
Base case
Recursive step
𝑇 1 =𝑏, 𝑇 𝑛 =𝑐+𝑇(𝑛−1)

OBSERVATIONS
Q: What assumptions are we making about removeFirst() and addLast() ?
A: They can be executed in constant time!
(Note that this is not true if we use an ArrayList.)

HOW TO SOLVE A RECURRENCE
There are different methods used to try to solve a recurrence:
Forward substitution Back substitution Recursion-tree method Master Theorem
:

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
𝑇𝑛=𝑐+𝑇𝑛−1
= 𝑐 + 𝑐 + 𝑇(𝑛 − 2)

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
𝑇𝑛=𝑐+𝑇𝑛−1
= 𝑐 + 𝑐 + 𝑇(𝑛 − 2)
= 𝑐 + 𝑐 + 𝑐 + 𝑇(𝑛 − 3)

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
𝑇𝑛=𝑐+𝑇𝑛−1
= 𝑐 + 𝑐 + 𝑇(𝑛 − 2)
= 𝑐 + 𝑐 + 𝑐 + 𝑇(𝑛 − 3) =3𝑐+𝑇𝑛−3 =⋯
=𝑘𝑐+𝑇𝑛−𝑘 =⋯ =(𝑛−1)𝑐+𝑇 1
= 𝑛−1 𝑐+𝑏=𝑐⋅𝑛+(𝑏−𝑐) whichis Θ 𝑛 .

EXAMPLE 2: SORTING A LIST
sort(list) {
if(list.size()==1) {
return;
}
minElement = list.removeMin(); sort(list); list.addFirst(minElement);
}
Base case
Recursive step
𝑇 1 =𝑎, 𝑇 𝑛 =𝑏+𝑐⋅𝑛+𝑇(𝑛−1)

OBSERVATIONS
Q: What assumptions are we making about addFirst() ? A: That can be executed in constant time.
Q: It would be ok if this step uses time proportional to 𝑛. Why?? A: Because removeMin() already takes time proportional to 𝑛.

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
Let’s solve the following slightly simpler recurrence:
𝑇𝑛 =𝑐𝑛+𝑇𝑛−1
= 𝑐𝑛 + 𝑐(𝑛 − 1) + 𝑇(𝑛 − 2)

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
Let’s solve the following slightly simpler recurrence:
𝑇𝑛 =𝑐𝑛+𝑇𝑛−1
= 𝑐𝑛 + 𝑐(𝑛 − 1) + 𝑇(𝑛 − 2)
= 𝑐𝑛 + 𝑐(𝑛 − 1) + 𝑐(𝑛 − 2) + 𝑇(𝑛 − 3)

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
Let’s solve the following slightly simpler recurrence:
𝑇𝑛 =𝑐𝑛+𝑇𝑛−1
= 𝑐𝑛 + 𝑐(𝑛 − 1) + 𝑇(𝑛 − 2)
= 𝑐𝑛 + 𝑐(𝑛 − 1) + 𝑐(𝑛 − 2) + 𝑇(𝑛 − 3)
…
=𝑐 𝑛+ 𝑛−1 + 𝑛−2 +⋯+ 𝑛−𝑘 +𝑇(𝑛−𝑘−1)
= 𝑐 𝑛 + 𝑛 − 1 + 𝑛 − 2 + ⋯ + 2 + 𝑇 1 , 𝑤h𝑒𝑛 𝑘 = 𝑛 − 2

EXAMPLE 3: TOWER OF HANOI
tower(n, start, finish, other) {
Base case is n=0
Recursive step
if(n>0) {
tower(n-1, start, other, finish) move from start to finish tower(n-1, other, finish, start)
}
}
𝑇 0 =𝑏, 𝑇 𝑛 =𝑐+2𝑇(𝑛−1)

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
𝑇𝑛 =𝑐+2𝑇𝑛−1 =𝑐+2 𝑐+2𝑇 𝑛−2
=𝑐 1+2 +4𝑇(𝑛−2)

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
𝑇𝑛 =𝑐+2𝑇𝑛−1
=𝑐+2 𝑐+2𝑇 𝑛−2 =𝑐 1+2 +4𝑇(𝑛−2)
=𝑐1+2 +4𝑐+2𝑇𝑛−3 =𝑐 1+2+4 +8𝑇(𝑛−3)

SOLVING THE RECURRENCE USING BACK SUBSTITUTION
𝑇𝑛 =𝑐+2𝑇𝑛−1
=𝑐+2 𝑐+2𝑇 𝑛−2
=𝑐 1+2 +4𝑇(𝑛−2)
=𝑐1+2 +4𝑐+2𝑇𝑛−3
=𝑐 1+2+4 +8𝑇(𝑛−3)
…
=𝑐1+2+4+⋯+2𝑘−1 +2𝑘𝑇(𝑛−𝑘) =𝑐1+2+4+⋯+2𝑛−1 +2𝑛𝑇0, 𝑤h𝑒𝑛𝑘=𝑛

YOU SHOULD KNOW…
1+2+3+…+𝑘=? 1+2+4+8+…+ 2𝑘 = ?
1+𝑥+𝑥2+𝑥3+…+𝑥𝑘= ?

EXAMPLE 4: BINARY SEARCH
binarySearch(list, key, left, right){ if(left <= right){ mid = (left + right)/2 if(list[mid]==key) return mid else { if(key

Related Posts