Description
Solve assignment with given instructions
Unformatted Attachment Preview
Python Programming
Homework 4
Instructor: Dr. Ionut Cardei
The following problems are from Chapters 14 (Files and Exceptions II) and 15 (Recursion) .
For full credit:
Make sure you follow exactly all requirements listed in this document,
the program must have all required features and run as expected,
follow the coding style taught in the book. Write docstrings for all function contracts and
comment the tricky parts of the code. Check out the Google Python Style Guide.
Upload on Canvas: the PDF file with all solutions plus the .py source files, in this order.
First, write the solution to a problem i in in a Pyhton file pi.py, for i=1…n.
Then, paste your answers into a new Word document called h4.doc. When done, convert it to PDF and
upload the PDF version (h4.pdf) and the solution .py files on Canvas.
The PDF file is very important: the instructor will write comments on top of the PDF file on Canvas for
you to read and learn from your mistakes.
Write your full name at the top of the file and add a heading before each problem solution.
List the solutions in the PDF file in the given order, 1, 2,.…
Syntax highlighting for the code pasted in the Word file makes it more readable and helps avoid
grading mistakes. Pasting from Spyder (or another IDE) into Word may preserve the Python
colors and styles. If not, consider using http://hilite.me/ or some other online service.
The problems are missing some details (e.g. on design, some method names). Where
unspecified by requirements, feel free to make your own decisions on design and
implementation as long as they comply with the book material, coding style, and don’t
contradict the requirements. If in doubt, ask on the Homework Q&A Forum, or ask the
instructor by email.
You have unlimited attempts to upload this assignment, but only the last one before the deadline
will be graded.
IMPORTANT:
Your solution must be your own original work and it must NOT include code that was shared or
copied from somewhere else. Doing otherwise is against the FAU Code of Academic Integrity.
For this assignment the instructor will use a cheating detector application that finds submissions that
indicate code shared or copied.
Name each required .py file like this: px_Lastname_Firstname.py, Substitute x with the problem
number, and Lastname, Firstname with your own last name and first name.
Example: if the problem number is 2 and your name is Jane Austen, name the problem 2 source file
p2_Austen_Jane.py.
Problem 1. (50 points)
Write the code for this problem in a file named p1_Lastname_Firstname.py, as required above.
A non-interactive text editor executes simple editing commands on a text file using a programming
interface (i.e. functions or object methods) in some programming language, like Python. All commands
take as input, at minimum, the file name as a parameter, then perform their job (reading or modifying
the file), and end returning some results. For this problem we assume the text files have the utf-8
encoding (the default in Python) and they are not too large. Therefore, it’s OK to read the file entirely
to memory, execute the operations required, then overwrite the file with the modified file content, as a
string. This is not the only approach, but it’s the simpler one and it works for smaller files.
Here are the editing commands, with the corresponding function signatures:
1. ed_read(filename, from=0, to=-1): returns as a string the content of the file named filename,
with file positions in the half-open range [from, to). If to == -1, the content between from and
the end of the file will be returned. If parameter to exceeds the file length, then the function
raises exception IndexError with a corresponding error message.
2. ed_find(filename, search_str): finds string search_str in the file named by filename and returns
a list with index positions in the file text where the string search_str is located. E.g. it returns
[4, 100] if the string was found at positions 4 and 100. It returns [] if the string was not found.
3. ed_replace(filename, search_str, replace_with, occurrence=-1): replaces search_str in the file
named by filename with string replace_with. If occurrence==-1, then it replaces ALL
occurrences. If occurrence>=0, then it replaces only the occurrence with index occurrence,
where 0 means the first, 1 means the second, etc. If the occurrence argument exceeds the actual
occurrence index in the file of that string, the function does not do the replacement. The
function returns the number of times the string was replaced.
4. ed_append(filename, string): appends string to the end of the file. If the file does not exist, a
new file is created with the given file name. The function returns the number of characters
written to the file.
For all the functions above, the file should not be changed in case of an error. If an error related to file
I/O (e.g. FileNotFoundError or IOError) occurs in one of these functions, it should be passed to the
caller. This means that these functions should not catch (except:) file IO errors.
Examples:
fn = “file1.txt”
# assume this file does not exist yet.
ed_append(fn, “0123456789”)
# this will create a new file
ed_append(fn, “0123456789”)
# the file content is: 01234567890123456789
print(ed_read(fn, 3, 9))
print(ed_read(fn, 3))
# prints 345678. Notice that the interval excludes index to (9)
# prints from 3 to the end of the file: 34567890123456789
lst = ed_find(fn, “345”)
print(lst)
print(ed_find(fn, “356”))
# prints [3, 13]
# prints []
ed_replace(fn, “345”, “ABCDE”, 1)
# changes the file to 0123456789012ABCDE6789
# assume we reset the file content to 01234567890123456789 (not shown)
ed_replace(fn, “345”, “ABCDE”) # changes the file to 012ABCDE6789012ABCDE6789
Here are your tasks for this problem:
a) Implement in Python all functions listed on the previous page. Write the contracts for each function
in its docstring. Ensure precondition errors are handled properly and exceptions are raised as needed.
All errors related to file I/O (e.g. FileNotFoundError or IOError) should be passed to the caller.
b) Write test functions for functions ed_replace and ed_find using the testif() function we used for
homework 3, listed in Appendix A. These test functions should be named test_x , where x is the name
of the function tested. E.g. test_ed_write() should use testif() to test ed_write(). In general, this type of
test functions are called unit tests as they test just one function (or one method in a class).
c) Write a main() function where you show how to use all ed_…. functions written for part a).
d) EXTRA CREDIT for 5 points
Write a function ed_search(path, search_string) that searches for search_string in all files in directory
path and its immediate subdirectories using the os.walk function.
The ed_search function must use the ed_find() function from part a). ed_search must return the list of
full (absolute) path names where files in which search_string is found or the empty list [] if the string is
not found in any files. The ed_search function should not proceed recursively to all subdirectories.
Problem 2. (50 points)
a) Leaf.
Write a function in file p2_Lastname_Firstname.py with name draw_leaf_straight that draws a leaflike that looks like Figure 1.a) using the turtle module. The figure produced is similar in principle to the
recursive examples from the textbook. The function takes as parameters the recursion level and the
length of the lower part of the “stem” (the petiole). It is really hard and time-consuming to make your
leaf look exactly like in the figure below, so students are encouraged to express their artistic side, to
personalize their leaf with various proportions and angles, as long as the basic leaf structure is similar
to that in Figure 1.b) and their leaf is similar to that in Figure 1.a). Make sure the figure you generate is
turned “left” 90 degrees, so it stands vertically. The turtle starts by default oriented towards “East”.
a)
b)
Figure 1. a) Recursive leaf produced by calling draw_leaf_straight(8, 120). b) The leaf
produced by the call draw_leaf_straight(1, 120).
Include a screenshot of the figure drawn by the call draw_leaf_straight(6, 120). Changing the function
name or using a screenshot for a different set of arguments will be penalized.
Hints:
The simplest leaf figure, drawn by the call draw_leaf_straight(1, 120), is shown in Figure 1 b).
Using helper functions to set up the figure is acceptable.
Use turtle.up(), turtle.down() to stop/start drawing, turtle.goto(x,y) to set the starting point for your
leaf drawing. Explore the other turtle functions, too. turtle.delay(0) eliminates animation delay.
Extra credit: 5 points if you also write a similar function called draw_leaf_curved (in addition to
draw_leaf_straight) that draws a curved leaf that looks like that in Figure 2. Again, it does not have to
be identical, but the it must be curved.
Include a screenshot of your figure obtained from the call draw_leaf_curved(6, 120).
Figure 2. Optional extra credit part for Problem 1: curved leaf
produced by the call draw_leaf_curved(8, 120)
b) Base X Conversion.
Write in file Write a function in file p2_Lastname_Firstname.py a recursive function
strB(n, base=10) that converts a non-negative int value n to a string representation of n in the given
base. The base parameter is an int between 2 and 26.
For digits greater than 9 use letters ‘A’-’Z’.
No credit is given for a solution that is not recursive.
Examples:
>>> strB(0)
‘0’
>>> strB(1234, base=10)
‘1234’
>>> strB(10, base=8)
’12’
>>> strB(100, base=8)
‘144’
>>> strB(100, base=16)
’64’
>>> strB(1024, base=16)
‘400’
>>> strB(15, base=13)
’12’
>>> strB(15, base=25)
‘F’
>>> strB(123, base=16)
‘7B’
>>> strB(1234, base=16)
‘4D2’
>>> strB(8191, base=16)
‘1FFF’
>>> strB(100, base=13)
’79’
>>> strB(102, base=13)
‘7B’
>>> strB(123456789, base=26)
‘AA44A1’
>>> strB(16, base=2)
‘10000’
>>> strB(100, base=2)
‘1100100’
Use the testif module/function attached to the homework’s page to write 4 unit tests for the
strB function. Check out Homework 3 solutions on how to write these unit tests.
Include a screenshot of your function’s output when used from the Python console with a
different set of test values than seen above. (IDLE, Spyder, and Jupyter have a Python console
window where the user can enter Python code directly.)
c) Memoized binomial coefficient (n-choose-k)
Write in file p2_Lastname_Firstname.py a recursive function Cnk_m(n,k) for computing the value of
the binomial coefficient using the memoization technique taught in class. No credit is given for a
solution that is not recursive and that does not use memoization.
Read more about the binomial coefficient here.
The recursive formula for n-choose-k is the following:
n = n =1
(
) (0 ) .
The base cases are: n
The recursive version without memoization has a time complexity of O(2n). With memoization, the
complexity drops to O(k n). Iterative versions are even more efficient.
•
•
Use testif to write 4 unit tests for your function. Use online calculators to find the correct
values.
Run the run_Cnk function inside the Python console for some interesting values and take a
screenshot with the run_Cnk function’s output. Include the screenshot in the PDF file after the
source code.
HINT: write first a recursive version without memoization; make sure that works, then add
memoization.
d) Making Pairs.
Write in file p2_Lastname_Firstname.py a recursive function called make_pairs that takes as
parameters two lists, seq1 and seq2, and that returns a list with all tuples (x, y) where x is in seq1 and y
is the matching element in seq2, at the same index as x.
Function make_pairs stops once it reaches the end of the shorter sequence.
No credit is given for a solution that is not recursive or for one that uses a list comprehension or uses a
loop statement, like for and while. Build the list with an accumulator argument.
Examples:
>>> make_pairs([1,2,3], [4,5,6])
[(1, 4), (2, 5), (3, 6)]
>>> make_pairs([1,2,3], [4,5])
[(1, 4), (2, 5)]
>>> make_pairs([1,2,3], [4,5,6,7,8,9])
[(1, 4), (2, 5), (3, 6)]
>>> make_pairs([], [4,5,6,7,8,9])
[]
>>> make_pairs([1,2,3], [4])
[(1, 4)]
>>> make_pairs([1,2,3], [])
[]
•
Write 5 unit tests for make_pairs with testif. Make sure you check boundary cases, e.g. one of the
sequences is empty, etc.
IMPORTANT NOTES:
A submission that does not follow the instructions 100% (i.e. perfectly) will not get full credit.
Did you write docstrings with contracts for all functions ?
Did you include all the required screenshots (if any)?
Upload the PDF file and .py source files on Canvas, in this order.
Only submissions uploaded before the deadline will be graded.
You have unlimited attempts to upload this assignment, but only the last one uploaded before
the deadline will be graded.
Rubric (100 points maximum):
Points for each problem are assigned as follows:
code correctness and screenshots (if required): 85%
coding style and following standards: 15%
APPENDIX A
The testif function used for writing unit tests:
Purchase answer to see full
attachment
