Introduction to Computer Science II
Homework 7
Due by 11:50am on Tuesday, March 1
Reading
Read chapters 10 and 11 as well as the week 7 and 8 lecture notes.
Problems
Solve the following by implementing the corresponding functions in homework7.py. When done, submit that file
through D2L.
1. [Lab] Implement recursive
function binary that takes a non-negative integer n
as input and returns the binary representation of n as a
string. Your function cannot make use of the format
built-in function or the format method of the str
class.
Usage:
>>> binary(0)
'0'
>>> binary(1)
'1'
>>> binary(2)
'10'
>>> binary(3)
'11'
>>> binary(7)
'111'
>>> binary(8)
'1000'
2. [Lab] Using function timingAnalysis
discussed in class, perform experiments to compare the running times
of functions dup1, dup2, dup3, and dup4.
Recall that we argued in class that the running times for these
functions on an input list of size n are on the order of n2,
n*log(n), n , and n. You will need to
determine the right inputs for timingAnalysis to confirm
this ranking. You will include your timingAnalysis runs as
a comment in homework7.py.
3-6. Problems 10.25 [Lab],
10.20, 10.31, 10.33
You will need test2.zip for 10.31. The
usage will be:
Usage:
>>> search('fileE.txt', 'test')
'test/folder2/fileE.txt'
>>> search('fileA.txt', 'test')
'test/fileA.txt'
>>> search('fileB.txt', 'test')
'test/folder1/fileB.txt'
>>> search('fileC.txt', 'test')
'test/folder1/fileC.txt'
>>> search('fileD.txt', 'test')
'test/folder2/fileD.txt'
>>> search('fileE.txt', 'test')
'test/folder2/fileE.txt'
>>> search('fileF.txt', 'test')
>>>