Introduction to Computer Science II

Homework 6

Due by 11:50am on Tuesday, February 22

Reading

Read chapter 10 as well as the week 6 (or 7) lecture notes.

Problems

Solve the following by implementing the corresponding functions in homework6.py. When done, submit that file through D2L.

Note: Additional problems were assigned on Thursday, Feb 17!
1.    [Feb 14 Lab] Implement recursive function countEven() that takes a list as input and returns the number of even numbers in the list. Your solution must not use any loop.
Usage:
>>> countEven([])
0
>>> countEven([1,3])
0
>>> countEven([1,3,6,7,8])
2

2.    [Feb 14 Lab] Implement recursive function maximum() that takes a non-empty list as input and returns the largest number in the list Your solution must not use any loop nor can it use the built-in max() function.
Usage:
>>> maximum([3])
3
>>> maximum([3 , 7, 8, 4, 5])
8
>>> maximum([3, 7, -8, 4, 5])
7

3.    [Feb 14 Lab] Implement a recursive function silly() that takes one nonnegative integer n as input and then prints n question marks, followed by n exclamation points. Your solution must not use any loop.
Usage:
>>> silly(0)
>>> silly(1)
*!
>>> silly(3)
***!!!


4.    [Feb 14 Lab] The recursive formula for computing the number of ways of choosing k items out of a set of n items, denoted C(n, k), is:
C(n,k) = 1                        if k = 0
       = 0                        if n < k
       =C(n-1,k-1) + C(n-1,k)     otherwise
The first case says there is one way to choose no item; the second says that there is no way to choose more items than available in the set. The last case separates the counting of sets of k items containing the last set item and the counting of sets of k items not containing the last set item. Write a recursive function combinations() that computes C(n, k) using this recursive formula.
Usage:
>>> combinations(2, 1)
2
>>> combinations(1, 2)
0
>>> combinations(5, 2)
10

5.    [Feb 14 Lab] Modify the function countdown() so it exhibits this behavior:
Usage:
>>> countdown3(10)
10
9
8
7
6
5
4
3
    BOOM!!!
    Scared you...
2
1
Blastoff!!!
(Note: for maximum effect, you may want to use function sleep() so the countdown really corresponds to seconds!)


6.    Implement recursive function numOnes() that takes a nonnegative integer n as input and returns the number of 1s in the binary representation of n. Use the fact that this is equal to the number of 1s in the representation of n//2 (integer division), plus 1 if n is odd.
Usage:
>>> numOnes(0)
0
>>> numOnes(1)
1
>>> numOnes(3)
2
>>> numOnes(4)
1
>>> numOnes(7)
3
>>> numOnes(8)
1

7.    Implement recursive function palindrome() that takes a string s as input and returns True  if s is a palindrome, False otherwise.
Usage:
>>> palindrome('radar')
True
>>> palindrome('racecar')
True
>>> palindrome('kayak')
True
>>> palindrome('natal')
False

8.    Implement recursive function removeDup() that takes a list as input and returns a copy of the list in which consecutive duplicates are replaced by a single copy of the item.
Usage:
>>> removeDup([2,2,3,3,3,2,2,2,2])
[2, 3, 2]
>>> removeDup([1,2,3,2,1,2,3,2,1])
[1, 2, 3, 2, 1, 2, 3, 2, 1]
>>> removeDup([1,1,1,1,1])
[1]
>>> removeDup([])
[]


Note: The below problems are additional problems assigned on Thursday, Feb 17!


9.    Problem 10.35 in the textbook


10.    Problem 10.36 in the textbook


11.    [Feb 21 Lab] Problem 10.28 in the textbook. You will need file files.zip.


12.     [Feb 21 Lab] Problem 10.30 in the textbook. You will need file test.zip.