CSC 244 Discrete Math Midterm 2 Study Guide Fall 2024 PDF

Study guide for midterm 2 CSC 244 – Discrete Math for Computer Science II Logistics Date: Wednesday, November 13th Time: 2 PM Duration: 50 minutes Closed book Closed note Calculator is allowed Topics Applications of Recurrence Relations Mathematical Induction Recursiv...

Study guide for midterm 2 CSC 244 – Discrete Math for Computer Science II Logistics Date: Wednesday, November 13th Time: 2 PM Duration: 50 minutes Closed book Closed note Calculator is allowed Topics Applications of Recurrence Relations Mathematical Induction Recursive definitions and Structural Induction The basics of counting Topics Please go through the slides. Please also go through the homework questions. Homeworks 4-8 Quizzes 4-7 The exam questions will be similar. You can find the contents in D2l. Also, the lectures are recorded in Panopto. 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 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. 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