Applications of Recurrence Relations PDF

Applications of Recurrence Relations CSC 244 – Discrete Math for Computer Science II Applications of Recurrence Relations Very useful tool for counting Counting arises in many problems in computer science Heavily used in algorithm design Algorithm: a procedure to solve a problem Rec...

Applications of Recurrence Relations CSC 244 – Discrete Math for Computer Science II Applications of Recurrence Relations Very useful tool for counting Counting arises in many problems in computer science Heavily used in algorithm design Algorithm: a procedure to solve a problem Recurrence relation is essential for: ○ Divide and conquer algorithms ○ Dynamic programming In many other advanced computational techniques Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? Consider the bit string: 10101 Does it satisfy the above condition? Yes Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? Consider the bit string: 101001 Does it satisfy the above condition? No Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? Let an = # strings of length n satisfying the condition Let Sn be the set of strings of length n satisfying the condition Then a1 = 2, the strings are 1 and 0 Hence S1 = {1, 0} and S2 = {11, 10, 01} What about a2? a2 = 3, the strings are 11, 10, and 01 Notice that 1 and 0 are in S1; Can you see a constructive relationship between a1 and a2? and 11 and 01 are in S2 Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? That means from any string of S1 we can generate a string of S2 What about strings ending with 0? Just concatenate 1 at the end of string Can we append 0 with strings of Sn-1? Hence an ≥ an-1 No, for example 0 is in S1 Is an = an-1 ? No, because we only considered strings ending with 1 But 00 is not in S2 Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? Take a closer look at the condition “do not have If the last bit is 0, two consecutive 0s.” then the second last bit is 1. Consider a string ending with 0 in Sn , e.g. …abc0 That means we can generate strings of Sn from strings of Sn-2 by What is c equal to? 1 appending 10 at the end. Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? Hence, an ≥ an-2 If the last bit is 0, Also, an ≥ an-1 then the second last bit is 1. We will argue an = an-1 + an-2 That means we can generate strings of Sn from strings of Sn-2 by How can we prove that argument? Proof by cases. appending 10 at the end. Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? Hence, an ≥ an-2 Case 1: the string ends with a 1, in this case # strings = an-1 Also, an ≥ an-1 Case 2: the string ends with a 0, in We will argue an = an-1 + an-2 this case # strings = an-2 How can we prove that argument? Proof by cases. Hence, the total # strings an = an-1 + an-2 Applications of Recurrence Relations Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. How many such bit strings are there of length five? Recurrence: an = an-1 + an-2 , a1 = 2, a2 = 3 a3 = a2 + a1 = 3 + 2 = 5 a4 = a3 + a2 = 5 + 3 = 8 a5 = a4 + a3 = 8 + 5 = 13 Tower of Hanoi A popular puzzle of the late nineteenth century consists of three pegs disks of different sizes Initially disks are placed on the first peg Rules: ○ Can move one disk at a time ○ a disk is never placed on top of a smaller disk Task: move all disks to the third peg with minimum number of moves Play Tower of Hanoi Let n = # disks. It has been conjecture that the following strategy is the best strategy: 1. Move the set of n-1 small disks to peg 2 2. Move the largest disk to peg 3 3. Move the set of n-1 small disks to peg 3 Let Hn = # moves for n disks for this strategy Then Hn = 2Hn-1 + 1 Play Tower of Hanoi Let n = # disks. It has been conjecture that the What is the solution? following strategy is the best strategy: Hn = 2Hn-1 + 1 1. Move the set of n-1 small disks to peg 2 2. Move the largest disk to peg 3 = 2(2Hn-2 + 1) + 1 = 22Hn-2 + 2 + 1 3. Move the set of n-1 small disks to peg 3 = 22(2Hn-3 + 1) + 2 + 1 = 23Hn-3 + 22 + 2 + 1 Let Hn = # moves for n disks for this strategy … Then Hn = 2Hn-1 + 1 = 2n-1H1 + 2n-2 + … + 2 + 1 = 2n-1+2n-2+...+1 = 2n -1 If n=64, then Hn = 18,446,744,073,709,551,615 Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. For example, consider the sorted list 2, 3, 5, 6, 10, 13. Find x=5. For this simple list we can immediately answer that 5 is the 3rd element. What if we have thousands of elements? We need to develop a strategy/algorithm to find x. Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2, 3, 5, 6, 10, 13, 14, 17 2. If the current element is equal to x, then return the location 3. Else move the next element at right position x = 13 4. Go to step 2 Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2, 3, 5, 6, 10, 13, 14, 17 2. If the current element is equal to x, then return the location 3. Else move the next element at right position x = 13 4. Go to step 2 2 is not equal to 13, move right Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2, 3, 5, 6, 10, 13, 14, 17 2. If the current element is equal to x, then return the location 3. Else move the next element at right position x = 13 4. Go to step 2 3 is not equal to 13, move right Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2, 3, 5, 6, 10, 13, 14, 17 2. If the current element is equal to x, then return the location 3. Else move the next element at right position x = 13 4. Go to step 2 5 is not equal to 13, move right Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2, 3, 5, 6, 10, 13, 14, 17 2. If the current element is equal to x, then return the location 3. Else move the next element at right position x = 13 4. Go to step 2 6 is not equal to 13, move right Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2, 3, 5, 6, 10, 13, 14, 17 2. If the current element is equal to x, then return the location 3. Else move the next element at right position x = 13 4. Go to step 2 10 is not equal to 13, move right Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2, 3, 5, 6, 10, 13, 14, 17 2. If the current element is equal to x, then return the location 3. Else move the next element at right position x = 13 4. Go to step 2 Found 13, return the location Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. A simple algorithm: 1. Start from the leftmost element 2. If the current element is equal to x, then return the location 3. Else move the next element at right position 4. Go to step 2 In the worst case we may need to search the whole list. For large number of elements, it will take longer. Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. The binary search algorithm: 1. Find the middle element y 2. If yx, delete half of the right elements, go to step 1 4. Otherwise, return the location of y Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. The binary search algorithm: 1. Find the middle element y 2, 3, 5, 6, 10, 13, 14, 17 2. If yx, delete half of the right elements, go to step 1 x = 13 4. Otherwise, return the location of y Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. The binary search algorithm: 1. Find the middle element y 2, 3, 5, 6, 10, 13, 14, 17 2. If yx, delete half of the right elements, go to step 1 x = 13 4. Otherwise, return the location of y 6 is a middle element Applications of Recurrence Relations Searching problem: Given a sorted list of integers find an element x if it exists. The binary search algorithm: 1. Find the middle element y 2, 3, 5, 6, 10, 13, 14, 17 2. If yx, delete half of the right elements, go to step 1 x = 13 4. Otherwise, return the location of y 6