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.