# Homework 9: Final Review hw09.zip

Due by 11:59pm on Friday, August 14

## Instructions

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]
"""
``````

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

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
"""
``````

Use Ok to test your code:

``python3 ok -q interleaved_sum``

### 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.

``python3 ok -q mutate_reverse``
``python3 ok --submit``