COT3100 // Exam II // Review Exercises Here is a list of review exercises. There are times when an exercise will be open ended, allowing you to pursue multiple aspects of the material. While encompassing some areas we have studied, you should further supplement your studying by reviewing: your notes, your homework assignments, exercise questions given in lecture, exercise questions given in discussion sessions, and problems from the chapters in our textbook. 1 1. [5 pts] Convert the binary 0110 1000 into its octal representation [(0110 1000)2 = ( ? )8; show your work]. (000)2 =0*4 + 0*2 + 0*1 =(0)8 (101)2 =1*4 + 0*2 + 1*1 =(5)8 (001)2 =0*4 + 0*2 + 1*1 =(1)8 (0110 1000)2 = (001 101 000)2 = (150)8 Note, in the second blocking of the binary number, the bits are split into groups of 3 to format to an Octal value. One zero is padded to the left side [not changing the number] to create the left most block of 3. 2. Using pseudo-code, describe an algorithm that will receive an unsorted array [a list of integers where the first index is 0] and find the index location of all integer(s) closest to zero. Prove the time complexity of your algorithm. Consider this example [note, 2 and -2 are both closest to zero in this array]: SAMPLE ARRAY INDECES CLOSEST TO ZERO [ 7, -8, 3, 2, 14, -5, 6, -2, 10, 2 ] 3, 7, 9 procedure closest_to_zero( a[]: integer ) lowest := abs( a[0] ) (1) for index := 1 to length(a) – 1 ∑ 1&'()*+ = () current := abs( a[index] ) (1) if ( current < lowest ) (1) lowest = current (1) indices := empty_list (1) tmp := 0 (1) for index := 0 to length(a) – 1 ∑ 1&'()*+ = () current := abs( a[index] ) (1) if ( current == lowest ) (1) indices[tmp] = index (1) tmp = tmp + 1 (1) return indices (1) Overall Complexity: () + () = () COT3100 // Exam II // Review Exercises Here is a list of review exercises. There are times when an exercise will be open ended, allowing you to pursue multiple aspects of the material. While encompassing some areas we have studied, you should further supplement your studying by reviewing: your notes, your homework assignments, exercise questions given in lecture, exercise questions given in discussion sessions, and problems from the chapters in our textbook. 2 3. Use pseudo-code to describe an algorithm that will receive an integer value and return the sum the individual digits in the number. The number entered will have an arbitrary number of digits. If the number entered was 1234, your algorithm will sum 1 + 2 + 3 + 4 and return 10. digit_sum(int n) int sum = 0 while (n > 0) { sum += n%10 n /= 10 } return sum 4. You know that the power set of A [often denoted as () or ()] is the set of all subsets of A. The cardinality of a set A [denoted ||] is the number of elements that it contains. Deterine the optimal value for and prove using the Mathematical Induction that |()| = 2& if || = , ∀ ≥ . An example of the power set is if = {, , }, then () =F∅, {}, {}, {}, {, }, {, }, {, }, {, , }H. Notice that || = = 3 and () = 2I = 8. Let () be the proposition that |()| = 2 if || = for some set . Basis step: For = ∅: () = {∅} || = 0 |()| = 1 = 20 Therefore, (0) is true. Inductive step: Assume ∀ ≥ 0, () is true. Let || = + 1 () will contain all the subsets previously contained for || = , along with subsets that contain the new element (of which there are 2). So, () = 2 + 2 = 2+1. Therefore ( + 1) is true. 5. Determine the optimal value for and use Mathematical Induction to prove ∀ ≥ , (): L( − 1)&)*+ = N2 − 1O ( + 1) COT3100 // Exam II // Review Exercises Here is a list of review exercises. There are times when an exercise will be open ended, allowing you to pursue multiple aspects of the material. While encompassing some areas we have studied, you should further supplement your studying by reviewing: your notes, your homework assignments, exercise questions given in lecture, exercise questions given in discussion sessions, and problems from the chapters in our textbook. 3 (1) Basis Step Prove () is True for = 1 [note, = 1]. =L( − 1)&)*+ =L( − 1)()*+ = (0 − 1) + (1 − 1) = −1 = N2 − 1O ( + 1) = T12 − 1U (1 + 1) = T−12U ∗ 2 = −1 Thus, the = and (1) is True. (2) a. Inductive Hypothesis Assume () is True for = . That is, L( − 1)W)*+ = T2 − 1U ( + 1) = X2 − 2 − 1 b. Inductive Step Prove () is True for = + 1. =L( − 1)&)*+ = L( − 1)WY()*+ =L( − 1)W)*+ + Z( + 1) − 1[ =L( − 1)W)*+ + Using the Inductive Hypothesis, =L( − 1)W)*+ + = X2 − 2 − 1 + = X2 + 2 − 1 = X2 + 2 − 22 = X2 + 2 − 22 = 12 (X + − 2) COT3100 // Exam II // Review Exercises Here is a list of review exercises. There are times when an exercise will be open ended, allowing you to pursue multiple aspects of the material. While encompassing some areas we have studied, you should further supplement your studying by reviewing: your notes, your homework assignments, exercise questions given in lecture, exercise questions given in discussion sessions, and problems from the chapters in our textbook. 4 = N2 − 1O ( + 1) = T + 12 − 1U Z( + 1) + 1[ = T2 + 12 − 1U ( + 2) = T2 − 12U ( + 2) = X2 − 2 + 22 − 22 = X2 + 2 − 22 = 12 (X + − 2) Thus, the = and ( + 1) is True. Therefore, () is True ∀ ≥ = 1. 6. Given (): ∀ ≥ 1, 2 | (X + ), determine the optimal value for and use Mathematical Induction to prove that () is true. (1) Basis Step Prove () is True for = 1 [note, = 1]. 2 | (1X + 1) ⇔ 2 | 2, note 2 = 2 ∗ 1 + 0. (2) a. Inductive Hypothesis Assume () is True for = . That is, 2 | (X + ) or X + = 2 ∗ (, where ( ∈ . b. Inductive Step Prove () is True for = + 1. 2 | Z( + 1)X + ( + 1)[ or Z( + 1)X + ( + 1)[ = 2 ∗ (where X ∈ ( + 1)X + ( + 1) = X + 2 + 1 + + 1 = X + 3 + 2 Now, we will re-arrange, pairing X with one of the three ‘s in 3 and pairing the remaining 2 with 2: (X + ) + (2 + 2) COT3100 // Exam II // Review Exercises Here is a list of review exercises. There are times when an exercise will be open ended, allowing you to pursue multiple aspects of the material. While encompassing some areas we have studied, you should further supplement your studying by reviewing: your notes, your homework assignments, exercise questions given in lecture, exercise questions given in discussion sessions, and problems from the chapters in our textbook. 5 Using the Inductive Hypothesis, (X + ) + (2 + 2) = 2 ∗ ( + (2 + 2) 2 ∗ ( + (2 + 2) = 2 ∗ ( + 2( + 1) = 2 ∗ (( + + 1) Thus, taking X = (( + + 1) and ( + 1) is True. Therefore, () is True ∀ ≥ = 1.
