CS 1110 Spring 2020, Assignment 4: Tre1110 redux
Updates:
The assignment itself, with updates marked in orange, begins on the next page. On this “page 0”, we also
document the time, location, and nature of the updates, in reverse chronological order,
• Sat Apr 25, 5pm: Typo in a4.py specification of indentlines(): Remove stray ’d’ in ’...abdc...’ in the 3rd
example. The zip file posted to the course website has been updated with this change:
'\tabc\n\tdef\n\tghi' -->
'\t\tabdc\n\t\tdef\n\t\tghi'
should be
'\tabc\n\tdef\n\tghi' -->
'\t\tabc\n\t\tdef\n\t\tghi'
• Wed Apr 22, 9:30am: a4.py: The example given in the specification for todo list to string() had copy-paste
errors. It has now been fixed in the zip file posted to the course website.
CS 1110 Spring 2020, Assignment 4: Tre1110 redux∗
1
Motivation: Get all the things done!
To-do lists, which we saw in A3, need not be just flat lists, but can be hierarchical or nested. One of your instructors
has a to-do list that includes items related to research and items related to the course:
• Her research items are broken up into a grant-proposal document she needs to write and, for each of her PhD
students,
- a separate list of what she needs to get back to each student with.
• Her course responsibilities include creating some labs and creating A4 and A5.
- A4 consists of:
∗ writing the skeleton, solution, and testing code for the programming problems
∗ writing up the assignment handout
∗ (etc.)
How much time does she need to get all this done? Can she get an organized printout of all the things she needs to
do? Help her, Obi-Wan, by completing this assignment!
More seriously, the idea behind this assignment is that nested lists are a natural and practical data structure
where recursion can really shine.
Contents
1
Motivation: Get all the things done!
2
2
Rules
3
2.1
New: resubmission after grading feedback is (conditionally) allowed!
3
2.2
(Same as before) You need to re-group (so to speak) on CMS, regardless of prior groupings
3
2.3
(Same as before) (Dis-)allowed collaborations and documentation requirements
3
3
Due dates
3
4
Task
3
4.1
Overview
3
4.2
Test Cases
4
4.3
The Functions To Write
4
4.3.1
sum hours
5
4.3.2
todo list to string
6
4.3.3
indentlines
7
4.4
Testing Output: read it carefully, even when there’s no “Quitting with Error” message at the bottom!
7
5
Pre-Submission Checklist and What to Submit
8
6
Advice on debugging recursive implementations (text also posted to Piazza)
9
∗Authors: Lillian Lee.
2
2
Rules
2.1
New: resubmission after grading feedback is (conditionally) allowed!
You are welcome to resubmit one of A4 or A5 after receiving grading feedback; further details to be arranged.
We are arranging for resubmission because we are concerned that there may currently be huge variation in
learning situations of students across the course, and we want to reduce the stress of having the deadlines for two
heavily-weighted assignments coming at you. We hope that resubmission will allow you to focus on improvement
and mastery of the material over a more gradual period of time.
However, many of the course staff are themselves carrying heavy burdens, and so we aren’t in a position to be
able to offer regrading of resubmissions for both assignments; hence the limit to one of A4 or A5.
2.2
(Same as before) You need to re-group (so to speak) on CMS, regardless of prior
groupings
You may work alone or with just one other person, who can be someone you’ve grouped with before in CS1110, or a different
person.
If you are partnering, regardless of whether you were grouped in a previous assignment, the two of you must still form a
new group specifically for this assignment on CMS before submitting.1
2.3
(Same as before) (Dis-)allowed collaborations and documentation requirements
means you and, if there is one, your one CMS-registered group partner,
1. Never look at, access or possess any portion of another group’s work in any form.
2. Never show or share any portion of your work in any form to anyone except a member of the course staff.
3. Never request solutions from outside sources; for example, on online services like StackOverflow.
4. DO specifically acknowledge by name all help you received, whether or not it was “legal” according to (1)-(3).
3
Due dates
CMS Usage Guide . Both parties need to act on CMS in order for the grouping to take effect.
(b) By 2pm on Thu Apr 30, submit whatever you have done at that point CMS for Assignment A4, following steps
page . It is OK if you haven’t finished working on it yet.2
(c) By 11:59pm3 on Thu Apr 30, make your final submission of file a4.py to Assignment A4, again following
the aforementioned steps 1-3.
4
Task
4.1
Overview
A major goal of this assignment is practice with recursion, since recursion is a great way to get things done. This goal
implies that, for each of the functions we have you implement, we reserve the right to assign no credit for code that
isn’t fundamentally based on recursion, or does not use recursion in the way we ask for, when we request a recursive
implementation, even if the code fulfills the specification.
The files needed for the assignment can be found in this zip file . It includes a3 classes.py from A3, since we’ll
be using the Task class again.
1This links your submission “portals”.
2The 2pm checkpoints provide you a chance to alert us if any problems arise. Since you’ve been warned to submit early, do not expect
that we will accept work that doesn’t make it onto CMS on time, for whatever reason. There are no so-called “slipdays” and there is no
“you get to submit late at the price of a late penalty” policy. Of course, if some special circumstances arise, contact the instructor(s)
immediately.
3PLUS a 9-hour grace period (anyone can take advantage of it, but the intent is to account for students in “distant” time zones
relative to Ithaca or for connection issues).
3
4.2
Test Cases
We’ve provided test cases in a4 test.py. You should make sure you understand the overall testing scenario we’ve
set up, where there’s One Todo List to rule them all, my todo list, made up of Tasks and (lists of ...) lists of
sub-Tasks. The code4 is shown below left. On the right is the kind of output your code should be able to produce:
a nicely formatted version of my todo list (comments have been added, for expository purposes).
1
BEGIN # start of my_todo_list
1
import a3_classes as a3
2
BEGIN # start of research_todos
2
3
NSF pr: 2
3
# Create some to-do lists
4
BEGIN # start of owe_students
4
5
BEGIN
# start of owe_s1
5
# Todo items I owe to each of my PhD students
6
camera: 8
6
owe_s1 = [a3.Task('camera-ready revisions', 8),
7
revise: 1
7
a3.Task('revise slides', 1)]
8
END
8
owe_s2 = [a3.Task('review proof', 3)]
9
BEGIN # start of owe_s2
9
owe_s3 = []
10
review: 3
10
owe_students = [owe_s1, owe_s2, owe_s3]
11
END
11
12
BEGIN # start of owe_s3 (yes,
it's
empty)
12
research_todos = [a3.Task("NSF proposal response", 213
END
13
owe_students,
14
END
14
a3.Task("Friday talk feedback", 1)1
5
Friday: 1
15
16
END # end of research_todos
16
solncode = [a3.Task("printing", 1),
17
BEGIN # start of course
17
a3.Task("counting", 1),
18
BEGIN # start of asst4
18
a3.Task("nesting depth", 1)]
19
BEGIN start of solncode
19
20
printi: 1
20
asst4 = [solncode,
21
counti: 1
21
a3.Task("writeup", 6),
22
nestin: 1
22
a3.Task("pkg and post", 1),
23
END
23
a3.Task("grading code and guide", 8)]
24
writeu: 6
24
25
pkg an: 1
25
course = [asst4,
26
gradin: 8
26
a3.Task("lab 9", 10),
27
END
27
a3.Task("A5", 20),
28
lab 9 : 10
28
a3.Task("lab 10", 11)]
29
A5
: 20
29
30
lab 10: 11
30
my_todo_list = [research_todos, course]
31
END
32
END
Note that course, asst4, . . ., owe s1 are all also valid todo lists that could be processed in their own right.
You are free to create more test cases, and encouraged to do so if you have the time, but we are not asking you
to submit your testcases.
Nonetheless, we reserve the right to grade your code in part on its output on different test cases than what we
gave you in a4 test.py.
4.3
The Functions To Write
Here are the specifications for the functions whose bodies you are to write in a4.py. Follow the directions given as
comments in a4.py.
4with some reformatting and some shortening of strings for space reasons.
4
4.3.1
sum hours
1
def sum_hours(tlist):
2
"""Returns the number of hours it would take to finish all the tasks contained
3
in the (possibly empty, possibly nested) Task list tlist.
4
If tlist is empty, returns 0.
5
6
Precondition: tlist is a list, possibly empty and possibly nested, of Tasks,
7
and the same is true of any of its sublists, or subsublists, or ...
8
9
Examples:
10
owe_s1 = [a3_classes.Task('camera-ready revisions', 8),
11
a3_classes.Task('revise slides', 1)]
12
owe_s2 = [a3_classes.Task('review proof', 3)]
13
owe_s3 = []
14
owe_students = [owe_s1, owe_s2, owe_s3]
15
research_todos = [a3_classes.Task("NSF proposal response", 2),
16
owe_students,
17
a3_classes.Task("Friday practice-talk feedback", 1)]
18
19
Then,
20
owe_students --> 12
21
research_todos --> 15
22
"""
5
4.3.2
todo list to string
1
def todo_list_to_string(tlist):
2
"""Returns a string version of a (possibly nested, possibly empty) list of
3
todo items tlist,
4
each task on a separate line printed via task_to_string,
5
each list, including the input `tlist` itself, delimited with a starting string
6
'BEGIN\n' and ending string 'END'
7
and each (sub)list's contents indented by one tab ('\t') per embedding level.
8
When printed, this string shows the indent levels visually.
9
10
Precondition: tlist is a list, possibly empty and possibly nested, of Tasks,
11
and the same is true of any of its sublists, or subsublists, or ...
12
13
14
Example:
15
Suppose we set up `owe_students` as follows:
16
owe_s1 = [a3_classes.Task('camera-ready revisions', 8),
17
a3_classes.Task('revise slides', 1)]
18
owe_s2 = [a3_classes.Task('review proof', 3)]
19
owe_s3 = []
20
owe_students = [owe_s1, owe_s2, owe_s3]
21
22
Then, the following very long string (broken up by "+"
for readability) is
23
the result of todo_list_to_string(owe_students):
24
'BEGIN\n'
25
+'\tBEGIN\n'
26
+'\t\tcamera: 8\n'
27
+'\t\trevise: 1\n'
28
+'\tEND\n'
29
+'\tBEGIN\n'
30
+'\t\treview: 3\n'
31
+'\tEND\n'
32
+'\tBEGIN\n'
33
+'\tEND\n'
34
+'END'
35
which, if printed via print(...), looks like this (yes,
there's an empty list):
36
BEGIN
37
BEGIN
38
camera: 8
39
revise: 1
40
END
41
BEGIN
42
review: 3
43
END
44
BEGIN
45
END
46
END
6
4.3.3
indentlines
The following function, which we recommend you implement in a non-recursive manner, is a helper for the function
above. The line numbered ’8’ below has been altered.
1
def
indentlines(line_str):
2
"""Returns a new string where each line in line_str has been indented by a
tab
3
character ('\t').
4
5
Examples:
6
'abc'
--> '\tabc'
7
'abc\ndef\nghi'
--> '\tabc\n\tdef\n\tghi'
8
'\tabc\n\tdef\n\tghi' -->
'\t\tabc\n\t\tdef\n\t\tghi'
9
10
This function has the following nice effect, useful for other functions in
A4.
11
>>> from a4 import indentlines
12
>>> s = 'abc\ndef\nghi'
13
>>> print(s)
14
abc
15
def
16
ghi
17
>>> print(indentlines(s))
18
abc
19
def
20
ghi
21
>>> print(indentlines(indentlines(s)))
22
abc
23
def
24
ghi
25
26
Precondition: line_str is a non-empty string with no trailing whitespace
27
(no tabs, newlines, or spaces at the end).
28
Lines within line_str are delimited by the newline character '\n'.
29
None of the lines in line_str are empty or contain only whitespace
30
"""
4.4
Testing Output: read it carefully, even when there’s no “Quitting with Error”
message at the bottom!
We know that getting the indentation and spacing right in todo list to string may prove challenging. Therefore,
our testing code not only checks if your output is right, but also, in the case of errors, checks whether your output
would be right if we ignored whitespace.
So, below is an excerpt of the output when a test case fails, with line numbers added, where the following should
be noted:
Importantly, Lines 27-28 indicate that the function is not quite correct!, but the only problem is due to
whitespacing.
• Thus, if you follow our recommendation in the implementation instructions to first implement
todo list to string without worrying about getting the tabbing or newlines right and without
employing helper indentlines, you can check for lines like 27-28 to see that you’re on the right
track, and can then proceed to deal with the whitespace.
Lines 4-6 are the output you are used to seeing from an assert equals failure.
Line 10 shows the exact string that should have been the output (surrounded by quotation marks).
Lines 12-15 gives a human-friendly version of the expected string.
Line 17 shows the exact string that the code returned, surrounded by quotation marks.
Lines 19-24 gives a human-friendly version of the function’s output. You can easily see that, in comparison
to lines 12-15, there’s extra blank lines at line 21 and 23.
7
1
Running test_print_todo_list
2
Testing input empty list
3
Testing input owes_s1
4
assert_equals: expected 'BEGIN\n\tcamera: 8\n\trevise: 1\nEND' but instead got
'BEGIN\n\tcamera:
8\n\n\trevise:
1\n\nEN
5
Line 145 of scratch/a4_test.py: testcase.assert_equals(expected, output)
6
Quitting with Error
7
8
************** Error on owes_s1 **************
9
What SHOULD have been the output:
10
'BEGIN\n\tcamera: 8\n\trevise: 1\nEND'
11
Human-readable version:
12
BEGIN
13
camera: 8
14
revise: 1
15
END
16
But the code's output is this:
17
'BEGIN\n\tcamera: 8\n\n\trevise: 1\n\nEND'
18
Human-readable version:
19
BEGIN
20
camera: 8
21
22
revise: 1
23
24
END
25
<output stopped here>
26
27
What if we ignore whitespace in the output?
28
Then your implementation is CORRECT ignoring spacing ... getting close!
In contrast, here’s an example excerpt from the testing code you get if your code is producing incomplete output.
In particular, note line 18.
1
************** Error on owes_s1 **************
2
What SHOULD have been the output:
3
'BEGIN\n\tcamera: 8\n\trevise: 1\nEND'
4
Human-readable version:
5
BEGIN
6
camera: 8
7
revise: 1
8
END
9
But the code's output is this:
10
'BEGIN\n\tcamera: 8\nEND'
11
Human-readable version:
12
BEGIN
13
camera: 8
14
END
15
<output stopped here>
16
17
What if we ignore whitespace in the output?
18
Then your implementation is UNFORTUNATELY NOT CORRECT even ignoring spacing.
5
Pre-Submission Checklist and What to Submit
Files to submit: just a4.py.
Before submitting, ensure your code obeys the following.5
1. Lines are short enough (˜80 characters) that horizontal scrolling is not necessary.
2. Functions are separated from each other by at least two blank lines.
5These requirements up speed up the process of reading/grading hundreds of files.
8
3. You have removed any debugging print statements.
4. You have removed all pass statements.
5. You have removed “instruction” comments, such as “# IMPLEMENT THIS FUNCTION”.
6. If you added any helper functions, these have good docstring specifications.
Make sure the following are all true before you submit.
8. You’ve changed the header comments in all files to list the entire set of people and sources that contributed to
the code.
9. You (and your partner) have included your NetIDs in the header of all files.
10. The date in the header comments has been changed to when the files were last edited.
invitations.
12. (reminder) If working with a partner, you have grouped on CMS. (One has invited on CMS, and one has
accepted on CMS.)
6
Advice on debugging recursive implementations (text also posted to
Piazza)
Something that makes debugging hard: one’s code always looks right.
And recursion is an especially tricky topic, in that beginning students are trying to adjust their mental models
as to how recursive functions actually work.
So how can you view your code through new eyes? Here are some suggestions (stemming from hard-won experi-
ence), when you find that you’ve been making lots of little changes and nothing seems to be helping.
1. Save backup copies of your code before making lots of changes, so you can restore things to the last “mostly
working” version.
2. As always: add print statements to try to get information as to what the values of your variables are. Lots of
issues come down to variables (including parameters) not having the values you expect.
3. Try using Python Tutor to really “see” what your code is doing on particular test cases.
4. Walk away from the computer, and try to write a solution from scratch.
It really will be worth it: once you get the hang of recursion, it leads to such elegant, concise code. The usual
progression is: “I just don’t see how to do this” . . . to . . . ”How could I ever have done this any other way?!”
9
