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.