Description
1. Write a recursive method in pseudo code that returns the number of 1’s in the binary
representation of N. Use the fact that this equal to the number of 1’s in the representation of N/2,
plus 1, if N is odd. [10 Points]
2. Evaluate the following sums: [10 Points]
a. ∑
1
4
𝑖
∞
𝑖=0
b. ∑
𝑖
4
𝑖
∞
𝑖=0
3. Let Fi be the Fibonacci numbers. Prove the following: [5 Points]
∑ 𝐹𝑖
𝑁−2
𝑖=1 = 𝐹𝑁 − 2
4. Prove by induction [5 Points]
1
3 + 2
3 + 3
3 + … … … … … + 𝑛
3 =
𝑛
2
(𝑛 + 1)
2
4
5. Suppose your calculator only did base 10 logarithms, write an expression to compute log base 2
of 64 using log base 10. [5 Points]
6. An integer subarray is called alternating if any two consecutive numbers in it have opposite signs
(i.e. one of them should be negative, whereas the other should be positive).
Given an array of n integers, write a pseudocode to compute for each index i, the length of the
longest alternating subarray starting at i. [15 Points]
For example:
Input : a[] = {1, -5, 1, -5}
Output : For index 0, {1, -5, 1, -5} = 4
index 1, {-5, 1, -5} = 3
index 2, {1, -5} = 2
index 3, {-5} = 1.
Input :a[] = {-5, -1, -1, 2, -2, -3}
Output : index 0, {-5} = 1
index 1, {-1} = 1
index 2, {-1, 2, -2} = 3
index 3, { 2, -2} = 2
index 4, {-2} = 1
index 5, {-3} = 1
