Also all algorithms need a proof of runtime and a proof of correctness

Question 2. (10 points) Very sparse numbers A positive integer is called sparse if its binary representation does not contain any consecutive 1's, e.g. n-69 ? 1000101 In this problem, we want to calculate the number of sparse integers with bit length exactly k denoted by Sk. E.g. for k-3, the only sparse numbers of bit length 3 are 4100,5101, which gives us that s-2. Note 2.1. 0 is not a sparse number. 1. (3 points) Find a recurrence relation for sk and give a O(k) method to calculate sk Hint 2.1. Observe that the leading digit of any number has to be 1. Now try to find the position of the next 1. 2. (2 points) Let rk be the number of sparse binary strings with length less than or equal to k. Write sk in tms of 1 Hint 2.2. Observe that the leading digit of a string does not need to be 1 3. (3 points) Find a closed form solution for rk (which means to first get a recurrence relation and then solve the recurrence) Hint 2.3. Write down the first 5 to 10 values of rk 4. (2 points) Give an algorithm to calculate sk in O(log k) Question 2. (10 points) Very sparse numbers A positive integer is called sparse if its binary representation does not contain any consecutive 1's, e.g. n-69 ? 1000101 In this problem, we want to calculate the number of sparse integers with bit length exactly k denoted by Sk. E.g. for k-3, the only sparse numbers of bit length 3 are 4100,5101, which gives us that s-2. Note 2.1. 0 is not a sparse number. 1. (3 points) Find a recurrence relation for sk and give a O(k) method to calculate sk Hint 2.1. Observe that the leading digit of any number has to be 1. Now try to find the position of the next 1. 2. (2 points) Let rk be the number of sparse binary strings with length less than or equal to k. Write sk in tms of 1 Hint 2.2. Observe that the leading digit of a string does not need to be 1 3. (3 points) Find a closed form solution for rk (which means to first get a recurrence relation and then solve the recurrence) Hint 2.3. Write down the first 5 to 10 values of rk 4. (2 points) Give an algorithm to calculate sk in O(log k)