Lecture 5, Part 1 Exercises

Before starting, please run the following cell

In [ ]:
from __future__ import division, print_function 

The answer to every question should use recursion!

Question 1

We want to write a recursive function findMinRec(l) to find the minimum value in list l, where l is a list of integers. We will break this problem into steps as shown below.

1.1

Write down the recursive case.

1.2

Write down the base case.

1.3

Now write the function findMinRec(l) that finds the minimum value in the list l.

For example, findMinRec([-2,2,3]) = -2.

Question 2

We have a list of prices for items you want to purchase. You want to calculate the total bill. Write a recursive function findSumRec(l) that takes a list of integers l and returns the sum of the prices in the list.

2.1

Write down the recursive case.

2.2

Write down the base case.

2.3

Write the recursive function findSumRec(l) that will add all the numbers in the list to return the total sum of the bill needed to be paid.

For example, findSumRec([55, 36, 200, 11]) = 302

Question 3

In this question we are given a string of letters where each letter represents whether a person is a spy or a commoner. So letter "c" in the string represents commoner and letter "s" represents spy. We want to find out how many spies are in the group. Write recursive function countSpiesRec(s) where s is the string of people.

3.1

Write the recursive case.

3.2

Write the base case.

3.3

Now we want to write the function countSpiesRec(s) that given a string of spies and commoners, will return the number of spies (s characters).

For example countSpiesRec("scccscccccc") = 2.

Another example: countSpiesRec("cccc") = 0.

Also: countSpiesRec("") = 0.

Question 4

We want to write a recursive function multiplyRec(x, y) that will multiply two positive integers x and y together without using the multiplication operator ($*$).

4.1

Write the recursive case.

4.2

Write the base case.

4.3

Now we want to write the recursive function multiplyRec(x, y) that takes in two non-negative integers and returns the product. We do not want to use the $*$ operator but rather want to do this recursively.

As you would expect, multiplyRec(4, 5) = 20

Also note, multiplyRec(0, 5) = 0

Question 5

Lets write a function findPowerTwoDivide(n) that takes in an integer n and returns the largest power of $2$ (e.g. $2^4 = 16$) that divides n evenly.

For example, findPowerTwo(8) = $2^3 = 8$

For example, findPowerTwo(9) = $2^0 = 1$

Question 6

Lets write a function findPowerTwoLargest(n) that takes in an integer n and returns the largest power of $2$ (e.g. $2^4 = 16$) that less than or equal to n.

For example, findPowerTwo(8) = $2^3 = 8$

For example, findPowerTwo(9) = $2^3 = 8$

Question 7

We have a list of integers representing how much you like different people. For example you like person with score $10$ more than you like person with $-12$ or $9$. Now you are going to have a party and are trying to decide who to invite. The sum of the scores of the people you invite represents the fun you would have at the party. We want to decide which subset of people to invite in order to have the most fun party.

Write a function bestPartyScore(friendScores), where friendScores is a list of integers, that returns an integer representing the fun you would have at the party.

For example, if you have friendScores = [1, 3, 7, 11], bestPartyScore(friendScores) = 1 + 3 + 7 + 11 = 22.

If you have friendScores = [1, -3, 7, 11], bestPartyScore(friendScores) = 1 + 7 + 11 = 19.

If you have friendScores = [-1, -3, -7, -11], bestPartyScore(friendScores) = 0 = 0.

If you have friendScores = [], bestPartyScore(friendScores) = 0 = 0.

Question 8

Now we will review the concept of binary.

Similar to how you can write numbers in decimal system (base $10$):

e.g. $1042 = 1(10^3) + 0(10^2) + 4(10^1) + 2(10^0)$

we can do this other sytems as well. Here is how we could do this in a different system. This is in base $2$ which we call the binary system:

e.g. $24 = 1(2^4) + 1(2^3) + 0(2^2) + 0(2^1) + 0(2^0)$

You can see each positive integer would have it's own unique such decomposition. As a result we can encode positive integers using just the coefficients from the above powers of $2$. So looking at $24$, if we just take the coefficients from the right hand side equation we get $11000$. This is the base $2$ encoding of $24$.

Here are some more examples:

e.g. $0 = 0(2^0) = 0$ in base $2$

e.g. $1 = 1(2^0) = 1$ in base $2$

e.g. $19 = 1(2^4) + 0(2^3) + 0(2^2) + 1(2^1) + 1(2^0) = 10011$ in base $2$

e.g. $63 = 1(2^5) + 1(2^4) + 1(2^3) + 1(2^2) + 1(2^1) + 1(2^0) = 111111$ in base $2$

e.g. $685 = 1(2^9) + 0(2^8) + 1(2^7) + 0(2^6) + 1(2^5) + 0(2^4) + 1(2^3) + 1(2^2) + 0(2^1) + 1(2^0) = 101010110$ in base $2$

8.1

Try to do the equivalent for $39$. Write the corresponding binary encoding.

8.2

We want to write a recursive function decimalToBinary(x) that takes in a positive integer x and returns a string that represents the binary form of x.

e.g. decimalToBinary(0) = "0"

e.g. decimalToBinary(19) = "10011"

Question 9

Jack the frog wants to hop home from a restaurant. He has to cross the river from the restaurant at rock n to his home at rock $0$. The rocks have equal distance of $1$ between them and he can jump over any number of rocks in the direction of his house and does not go backwards. In how many different ways can he reach home? Two ways are different if they do not use exactly the same rock route. Write a recursive function gettingHome(n) that takes in integer n representing the distance between the restaurant and home, and returns the number of ways for Jack to return home.

For example, when n = 3, gettingHome(n) = 4

frog.png