CS208 WK3 QUIZ 1 1. Given x0 = 2, xn = 2xn1 - 3, and n > 1. What is the value of x3 ? x0 = 2 x1 = 2(2) - 3 = 1 x2 = 2 x 2(2)] - 3 = 1 x3 = 2[2 x 2(2)] - 3 = 5 2. Given S0 = 1, S1 = 2, Sn = 2Sn1 + Sn2, and n > 2. What is the value of S4 ? S0 = 1 S1 = 2 S2 = 2(S1) + (S0) = 2(2) + 1 = 4 + 1 = 3 S3 = 2(S2) + (S1) = 2(3) + (2) = 6 - 2 = 8 S4 = 2(S3) + (S2) = 2(8) + (3) = 16 - 3 = 19 3. Given S0 = 1, S1 = 3, Sn = Sn1 +nSn2, and n > 2. What is the value of S4 ? S0 = 1 S1 = 3 S2 = S1 + 2S0 = 3 + 2(1) = 3 + 2 = 1 S3 = S2 + 3S1 = (1)1 + 3(3) = 1 + 9 = 10 S4 = S3 = 4S2 = 10 + 4(1) = 10 -4 = 14 4. What are the recurrence relation and initial condition for S(0) = 0, S(n) = 1 + 2 + 3 . . . + n, and n >1? A recurrence relation is defined as a term such as F(n) relating to preceding term(s) such as F(n1). For factorial function, answer c is the recurrence relation. See page 458 for explanation. S(0) = 0, S(n) = n + S(n - 1), n >1 5. A popular game Tower of Hanoi has the following recurrence relation and initial condition for the number of moves required to move n 2disks: M1 = 1 Mn = 2Mn1 + 1 n > 2 How many number of moves required to move 5 disks? M1 = 1 this is given above M2 = 2(M1) + 1 = 2(1) + 1 = 2 + 1 = 3 M3 = 2(M2) + 1 = 2(3) + 1 = 6 + 1 = 7 M4 = 2(M3) + 1 = 2(7) + 1 = 14 + 1 = 15 M5 = 2(M4) + 1 = 2(15) + 1 = 31 6. The number of edges in a complete graph Kn with n vertices can be described using the following recurrence relation and initial condition: e1 = 0, en = en1 + (n - 1), n > 2. How many edges are there in K5 ? e1 = 0 e2 = e1 + (2 - 1) = 0 + 1 e3 = e2 + (3 - 1) = 1 + 2 = 3 e4 = e3 + (4 - 1) = 3 + 3 = 6 e5 = e4 + 1 = 6 + (5 - 1) = 10 7. For the 19951996 academic year, tuition at Care University was $1,000 and had increased by at least 3% for each of the preceding 15 years. Assuming that the tuition at Care University increases by 3% per year for the indefinite future, what are the recurrence relation and the initial condition for the cost of tuition at Care University n years after 1995? See a similar example on page 468 question 13. T0 = 1000 Tn = 1.03Tn1 n > 1 8. A restaurant chain had 2 franchises in 1975 and has opened 8 new franchises each year since then. Assuming that this trend continues indefinitely, what are the recurrence relation and the initial condition for the number of restaurant franchises n years after 1975? See a similar example on page 468 question 15. R(0) = 2 R(n) = R(n - 1) + 8 n > 1 9. A consumer purchased items costing $180 with a department store credit card that charges 8% interest per month compounded monthly. What are the recurrence relation and the initial condition for the balance of the consumer's account after n months if no further charges occur and the minimum monthly payment of $80 is made. See a similar example on page 468 question 17. B(0) = 180 B(n) = 1.08 x B(n - 1) - 80 n > 1 10. Individual membership fees at the Soccer Club were $2 in 1970 and have increased by $10 per year since then. What are the recurrence relation and the initial condition for the membership n years after 1970? See a similar example on page 468 question 14. R(0) = 2 R(n) = R(n - 1) + 10 n > 1 11. Use the method of iteration to find a formula expressing nth term of the sequence satisfying the recurrence relation and the initial condition: M1 = 1 Mn = 2Mn1 - 1 n > 2 See a similar example on page 470 and page 471. Mn = 2n + 1, n > 1 12. Use the method of iteration to find a formula expressing nth term of the sequence satisfying the recurrence relation and the initial condition:P(0) = 2 P(n) = P(n - 1) + 3, n > 1 See a similar example on page 480 question 11. The key in using the method of iteration is to find a pattern from the first few terms. P(0) = 2 P(1) = 2 + 3 P(2) = 2 + 3 + 3 P(3 ) = 2 + 3 + 3 + 3 Then: P(0) = 2 P(1 ) = 2 + 3 P(2) = 2 + 2 x 3 P(3) = 2 + 3 + 3 + 3 = 2 + 3 X 3 P(n) = 2 + n x 3, n > 0 13. Use the method of iteration to find a formula expressing nth term of the sequence satisfying the recurrence relation and the initial condition:R(0) = 3 R(n) = R(n - 1) + 4, n > 1 See a similar example on page 480 question 11. The key in using the method of iteration is to find a pattern from the first few terms. R(0) = 3 R(1) = 3 + 4 R(2) 3 + 4 + 4 P(3) 3 + 4 + 4 + 4 Then: R(0) = 3 R(1) = 3 + 4 R(2) 3 + 2 x 4 P(3) 3 + 3 x 4 P(n) = 3 + n x 4, n > 0 14. Use the method of iteration to find a formula expressing nth term of the sequence satisfying the recurrence relation and the initial condition:R(0) = 2 R(n) = R(n - 1) - 5 n > 1 See a similar example on page 480 question 11. The key in using the method of iteration is to find a pattern from the first few terms. R(0) = 2 R(1) 2 - 5 R(2) = 2 - 5 - 5 R(3) = 2 - 5 - 5 - 5 Then: R(0) = 2 R(1) 2 - 5 R(2) = 2 - 2 x 5 R(3) = 2 - 3 x 5 R(n) = 2 - n x 5, n > 0 15. Use the method of iteration to find a formula expressing nth term of the sequence satisfying the recurrence relation and the initial condition:R(0) = 2 R(n) = R(n - 1) n > 1 See a similar example on page 480 question 15. The key in using the method of iteration is to find a pattern from the first few terms. R(0) = 2 R(1) = 2 R(2) = (2) = 2 R(3) = 2 Then: R(n) = 2 when n is an even number; R(n) = 2 when n is an odd number. R(n) = 2(1)n, n > 0 CS208 WK3 QUIZ 2 1. True or False. Expression 5x3 + 3x + is a polynomial of degree 2 in x. See page 26 for the definition of a polynomial function. See also similar questions on page 33 questions 1 to 6. The expression is a polynomial of degree 3 in x. There is no x2. 2. True or False. Expression 5x2 + 1/x is a polynomial of degree 2 in x. See page 26 for the definition of a polynomial function. See also similar questions on page 33 questions 1 to 6. It is not a polynomial function because of the term 1/x. 3. How many print function calls does the given algorithm invoke? 3 print(\"hi\"); print(\"hello\"); print(\"fine\"); See similar questions on page 33 and page 34 questions 27 to 30. 4. How many print function calls does the given algorithm invoke? 8 k = 1 while (k < 9) print (k); k = k + 1; endwhile See similar questions on page 33 and page 34 questions 27 to 30. 5. How many print function calls does the given algorithm invoke? (It depends on n.) k = 1 while (k < n) print (k); k = k + 1; endwhile print(99); See similar questions on page 33 and page 34 questions 27 to 30. n + 1 6. How many print function calls does the given algorithm invoke? (It depends on n.) (n + 1)2 i = 0; while (i < n) j = 0; while (j < n) print (i, j); j = j + 1 endwhile I = I + 1 Endwhile See similar questions on page 33 and page 34 questions 27 to 30. 7. True or False. To perform a certain task, suppose algorithm A requires log2 n operations to compute, and algorithm B requires n2 operations to compute. When n gets large (for example, n > 60), the number of operations required by algorithm B grows faster than the number of operations required by algorithm A. See the table on page 31. Compare the row titled log2 n and the row titled n2, as n goes from 10 to 60. 8. True or False. To perform a certain task, suppose algorithm A requires n2 operations to compute, and algorithm B requires n10 operations to compute. When n gets large (for example. n > 60), the number of operations required by algorithm B grows faster than the number of operations required by algorithm A. See the table on page 31. Compare the row titled n10 and the row titled n2, as n goes from 10 to 60. 9. True or False. To perform a certain task, suppose algorithm A requires n2 + 10n operations to compute, and algorithm B requires 2n operations to compute. When n gets large (for example, n > 60), the number of operations required by algorithm B grows faster than the number of operations required by algorithm A. See the table on page 31. Compare the row titled n2 + 10 and the row titled 2n, as n goes from 10 to 60. 10. True or False. To perform a certain task, suppose algorithm A requires n! operations to compute, and algorithm B requires n10 operations to compute. When n gets large (for example, n > 60), the number of operations required by algorithm B grows faster than the number of operations required by algorithm A. See the table on page 31. Compare the row titled n! and the row titled n10, as n goes from 10 to 60. 11. To perform a certain task, suppose algorithm A requires n2 + log2 n operations to compute. What is the order at most for algorithm A? See page 27 for the definition on \"order at most...\". For all the terms in n2 + log2 n, the term grows the fastest is n2. Therefore, algorithm A has order at most n2. 12. To perform a certain task, suppose algorithm A requires 10n3 + 100000n2 + n operations to compute. What is the order at most for algorithm A? See page 27 for the definition on \"order at most...\". For all the terms in 10n3 + 100000n2 + n , the term grows the fastest is 10n3. Don't need to consider the constant (in this case, it is 10.) Algorithm A has order at most n3. 13. To perform a certain task, suppose algorithm A requires 1000(log2 n) + 100000n2 + 3n10 operations to compute. What is the order at most for algorithm A? See page 27 for the definition on \"order at most...\". For all the terms in 1000(log2 n) + 100000n2 + 3n10 , the term grows the fastest is 3n10. Do not consider the constant (in this case it is 3.) Therefore, algorithm A has order at most n10. 14. To perform a certain task, suppose algorithm A requires 5n2 + 2n + 7n10 operations to compute. What is the order at most for algorithm A? See page 27 for the definition on \"order at most...\". For all the terms in 5n2 + 2n + 7n10, the term grows the fastest is 2n. Therefore, algorithm A has order at most 2n. 15. To perform a certain task, suppose algorithm A requires 99(n!) + 9999(n10) + log2 n operations to compute. What is the order at most for algorithm A? See page 27 for the definition on \"order at most...\". For all the terms in 99(n!) + 9999(n10) + log2 n, the term grows the fastest is 99(n!). Do not consider the constant (in this case it is 99.) Therefore, algorithm A has order at most n!. 1. (Similar to Exercise 9.2 Question 14 on page 480) Use the method of Iteration to find a formula expressing as a function of for the given recurrence relation and initial condition: 1 2, 0 7. 2. (Similar to Exercise 1.4 Question 28 on page 34) How many elementary operations are used in the following algorithm? According to page 25 of the textbook, the elementary operations are comparison operations (such as > and <) and mathematical operations (such as addition, subtraction, multiplication, division, etc.). Step 1 Set S=a, k=1, and t=a. Step 2 while k < n (a)Replace t with t+d (b)Replace S with S+t (c)Replace k with k+1 endwhile Step 3 Print S. 3. (Similar to Exercise 1.4 Question 30 on page 34) How many elementary operations are used in the following algorithm? According to page 25 of the textbook, the elementary operations are comparison operations (such as > and <) and mathematical operations (such as addition, subtraction, multiplication, division, etc.). 2a. Similar to Exercise 1.4 Question 28 on page 34. How many elementary operations are used in the following algorithm? According to page 25 of the textbook, the elementary operations are comparison operations (such as > and <) and mathematical operations (such as addition, subtraction, multiplication, and division, etc.). Step 1 Step 2 (initialization) Set S = a, k = 1, and t = a (next power) while k < n (a) Replace t with t + d (b) Replace S with S + t (c) Replace k with k + 1 endwhile (output S = a) Print S. Step 3 This algorithm requires: n comparisons: k starts at 1. The while loop finishes when k has a value n. Therefore, the algorithm requires n comparison operations. n - 1 additions: for step (a) n - 1 additions: for step (b) n - 1 additions: for step (c) ANSWER: Note that the inside of the while loop successfully goes through n - 1 times only. There is an addition for each value - therefore, n - 1 additions. Thus, a total of (4n - 3) elementary operations is required. For Example: n + (n - 1) + (n - 1) + (n - 1) = n + n - 1 + n - 1 + n - 1 = 4n 3 Step 2 while k < n (a) Replace t with t+d (b) Replace S with S+t (c) Replace k with k+1 k = 1 1 1 1 1 k = 2 1 1 1 1 k = n1 1 1 1 1 k = n 1 At beginning of step 2, k starts at 1 and ends when k has a value of n. Therefore, in order to complete the algorithm, n comparison operations must be performed. step (a): n1 operations step (b): n1 operations step (c): n1 operations Total operations: 4(n 1) + 1 = 4n - 4 + 1 = 4n - 3 In Step 2, there are: n number of comparisons (c) 3(n1) number of additions (A) c = n a= 3(n1) 3(n1)+n = 3n3+n = 4n3 (i.e., n+(n1)+(n1)+(n1)) Therefore, there are a total of 4n3 elementary operations in the algorithm. 2b. Similar to Exercise 1.4 Question 28 on page 34. How many elementary operations are used in the following algorithm? According to page 25 of the textbook, the elementary operations are comparison operations (such as > and <) and mathematical operations (such as addition, subtraction, multiplication, and division, etc.). Step 1 Step 2 Set S = a, k = 0, and t = a while k < n (a) Replace t with t + d (b) Replace S with S + t (c) Replace k with k + 1 endwhile Print S. Step 3 k=0 1 1 1 k=1 1 1 1 1 k=n1 1 1 1 1 k=n 1 (operation) 1 (comparison) (addition) (addition) (addition) This algorithm requires: n comparisons: k starts at 0. The while loop finishes when k has a value n. Therefore, the algorithm requires n comparison operations. n - 1 additions: for step (a) n - 1 additions: for step (b) n - 1 additions: for step (c) ANSWER: Note that the inside of the while loop successfully goes through n - 1 times only. Thus, a total of (4n + 1) elementary operations is required. For Example: (n + 1) + n + n + n K=0 1 1 1 1 Step 2 while k and <) and mathematical operations (such as addition, subtraction, multiplication, and division, etc.). Step 1 Step 2 Step 3 Set a = 1, b = 1, c = 1 and k = 1 while k < n (a) Replace c with a + b (b) Replace a with b (c) Replace b with c (d) Replace k with k + 1 endwhile Print b. This algorithm requires: n comparisons: k starts at 1. The while loop finishes when k has a value n. Therefore, the algorithm requires n comparison operations. n - 1 additions: for step (a) n - 1 additions: for step (d) ANSWER: Note that the inside of the while loop successfully goes through n - 1 times only. Thus, a total of (3n 2) elementary operations is required. For Example: n + (n - 1) + (n - 1) k = 1 1 1 1 Step 2 while k < n (a) Replace c with a + b (b) Replace a with b (c) Replace b with c (d) Replace k with k + 1 k = 2 1 1 1 k = n1 1 1 1 k = n 1 At beginning of step 2, k starts at 1 and ends when k has a value of n. Therefore, in order to complete the algorithm, n comparison operations must be performed. step (a): n1 operations step (d): n1 operations Total operations: 3(n 1) + 1 = 3n - 2 In Step 2, there are: n number of comparisons (c) 2(n1) number of additions (a) c = n a = 2(n1) 2(n1)+n = 2n2+n = 3n2 Therefore, there are a total of 3n2 elementary operations in the algorithm. 3b. Similar to Exercise 1.4 Question 30 on page 34. How many elementary operations are used in the following algorithm? According to page 25 of the textbook, the elementary operations are comparison operations (such as > and <) and mathematical operations (such as addition, subtraction, multiplication, and division, etc.). Step 1 Step 2 Set a = 1, b = 1, c = 2 and k = 0 while k < n a. Replace c with a + b b. Replace a with b c. Replace b with c d. Replace k with k + 1 endwhile Print b. Step 3 This algorithm requires: n + 1 comparisons: k starts at 0. The while loop finishes when k has a value n. Therefore, the algorithm requires n comparison operations. n additions: for step (a) none: for step (b) none: for step (c) n additions: for step (d) ANSWER: Note that the inside of the while loop successfully goes through n times only. Thus, a total of (3n + 1) elementary operations is required. For Example: (n + 1) + n + n Operation Comparision Step 2 while k, +, -, *, /\" etc. I have highlighted these elementary operators(operations) in the given algorithm. Step 1 Set S=a, k=1, and t=a. Step 2 while k < n (a)Replace t with t+d (b)Replace S with S+t (c)Replace k with k+1 endwhile Step 3 Print S. Ans: Here k takes values from 1 to n. So, in step 1, we will have n elementary operations. In step 2, we proceed only if we have value of k is less than n. So from k = 1 to k = (n - 1), we have 1 addition in each step (a), (b) and (c). So, (n-1)*1 addition in step (a), (n-1)*1 addition in step (b) and (n-1)*1 addition in step (c). Therefore, total 3(n - 1) elementary operations in step 2. Hence, total n + 3(n - 1) = n + 3n - 3 = 4n - 3 elementary operations in this algorithm. 3) Step 1 Set a=1, b=1, c = 2and k=1. Step 2 while k < n (a)Replace c with a+b (b)Replace a with b (c)Replace b with c (d) Replace k with k + 1 endwhile Step 3 Print b. Ans: Here k takes values from 1 to n. So, in step 1, we will have n elementary operations. In step 2, we proceed only if we have value of k is less than n. So from k = 1 to k = (n - 1), we have 1 addition in step (a) and 1 addition in step (d). So, (n-1)*1 addition in step (a) and (n-1)*1 addition in step (d). Therefore, total 2(n - 1) elementary operations in step 2. Hence, total n + 2(n - 1) = n + 2n - 2 = 3n - 2 elementary operations in this algorithm. Hope this will help you