Homework 9: Final Review
Due by 11:59pm on Friday, August 14
Instructions
Download hw09.zip.
Submission: When you are done, submit with python3 ok
--submit
. You may submit more than once before the deadline; only the
final submission will be scored. Check that you have successfully submitted
your code on okpy.org. See Lab 0 for more instructions on
submitting assignments.
Using Ok: If you have any questions about using Ok, please refer to this guide.
Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 3 points.
Questions
Trees
Q1: In-order traversal
Write a function that returns a generator that generates an "in-order" traversal, in which we yield the value of every node in order from left to right, assuming that each node has either 0 or 2 branches.
def in_order_traversal(t):
"""
Generator function that generates an "in-order" traversal, in which we
yield the value of every node in order from left to right, assuming that each node has either 0 or 2 branches.
For example, take the following tree t:
1
2 3
4 5
6 7
We have the in-order-traversal 4, 2, 6, 5, 7, 1, 3
>>> t = Tree(1, [Tree(2, [Tree(4), Tree(5, [Tree(6), Tree(7)])]), Tree(3)])
>>> list(in_order_traversal(t))
[4, 2, 6, 5, 7, 1, 3]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q in_order_traversal
Scheme
Q2: Reverse
Write the procedure reverse
, which takes in a list lst
and outputs a reversed list. Hint: you may find the built-in function append
useful (documentation).
(define (reverse lst)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q reverse-simple
Recursion
Q3: Interleaved Sum
Recall that the summation
function computes the sum of a sequence of
terms from 1 to n
:
def summation(n, term):
"""Return the sum of the first n terms of a sequence.
>>> summation(5, lambda x: pow(x, 3))
225
"""
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total
Write a function interleaved_sum
that similarly computes the sum of a
sequence of terms from 1 to n
, but uses different functions to compute
the terms for odd and even numbers. Do so without using any loops or
testing in any way if a number is odd or even.
Note: no-loops rule is just to make sure you get practice writing recursive solutions, but in future you may have to combine both recursion and loops to solve problems.
Hint: You can test if a number is equal to 0, 1, or
n
. If you start summing from the term 1, you'll be able to tell whether the current term is odd or even. How can you keep track of an extra variable for the current term in a recursive function?
def interleaved_sum(n, odd_term, even_term):
"""Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
to n.
>>> # 1 + 2^2 + 3 + 4^2 + 5
... interleaved_sum(5, lambda x: x, lambda x: x*x)
29
>>> from construct_check import check
>>> check(SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q interleaved_sum
Linked Lists
Q4: Mutate Reverse
Implement mutate_reverse
, which takes a linked list instance and mutates it
so that its values appear in reverse order. For an extra challenge, find an
implementation that requires only linear time in the length of the list
(big-Theta n).
def mutate_reverse(link):
"""Mutates the Link so that its elements are reversed.
>>> link = Link(1)
>>> mutate_reverse(link)
>>> link
Link(1)
>>> link = Link(1, Link(2, Link(3)))
>>> mutate_reverse(link)
>>> link
Link(3, Link(2, Link(1)))
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q mutate_reverse
Submit
Make sure to submit this assignment by running:
python3 ok --submit