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