Exam Prep 6: Object-Oriented Programming, Trees, Linked Lists
Students from past semesters wanted more content and structured time to prepare for exams. Exam Prep sections are a way to solidify your understanding of the week's materials. The problems are typically designed to be a bridge between discussion/lab/homework difficulty and exam difficulty.
Reminder: There is nothing to turn in and there is no credit given for attending Exam Prep Sections.
We try to make these problems exam level , so you are not expected to be able to solve them coming straight from lecture without additional practice. To get the most out of Exam Prep, we recommend you try these problems first on your own before coming to the Exam Prep section, where we will explain how to solve these problems while giving tips and advice for the exam. Do not worry if you struggle with these problems, it is okay to struggle while learning.
You can work with anyone you want, including sharing solutions. We just ask you don't spoil the problems for anyone else in the class. Thanks!
You may only put code where there are underscores for the codewriting questions.
You can test your functions on their doctests by clicking the red test tube in the top right corner after clicking Run in 61A Code. Passing the doctests is not necessarily enough to get the problem fully correct. You must fully solve the stated problem.
Q1: Iterator Tree Link Tree Iterator
Difficulty: ⭐⭐
Part A: Fill out the function funcs, which is a generator that takes in a linked list link and yields functions.
The linked list link defines a path from the root of the tree to one of its nodes, with each element of link specifying which branch to take by index. Applying all functions sequentially to a Tree instance will evaluate to the label of the node at the end of the specified path.
For example, using the Tree t defined in the code, funcs(Link(2)) yields 2 functions. The first gets the third branch from t -- the branch at index 2 -- and the second function gets the label of this branch.
>>> func_generator = funcs(Link(2)) # get label of third branch
>>> f1 = next(func_generator)
>>> f2 = next(func_generator)
>>> f2(f1(t))
4Part B: Using funcs from above, fill out the definition for apply, which applies g to the element in t who's position is at the end of the path defined by link.
Q2: Cucumber - Fall 2015 Final Q7
Difficulty: ⭐⭐
Cucumber is a card game. Cards are positive integers (no suits). Players are numbered from 0 up to players
(0, 1, 2, 3 in a 4-player game).
In each Round, the players each play one card, starting with the starter and
in ascending order (player 0 follows player 3 in a 4-player game). If the card played is as high or higher than
the highest card played so far, that player takes control. The winner is the last player who took control
after every player has played once.
Implement Round so that Game behaves as described in the doctests below.
EDIT: The first two lines in the play function should be:
assert _______________________________, f'The round is over, player {who}'
assert ______________________________, f'It is not your turn, player {who}'Q3: Count Coins Tree
IMPORTANT: For this problem, you will be given time during the Exam Prep section to solve on your own before we go over it.
Difficulty: ⭐⭐⭐
You want to help your friend learn tree recursion. They don't quite understand all the recursive calls and how they work, so you decide to make a tree of recursive calls to showcase the tree in tree in tree recursion. You pick the count_coins problem.
Implement count_coins_tree, which takes in a non-negative integer n and returns a tree representing the recursive calls of count change.
Since you don't want your trees to get too big, you decide to only include the recursive calls that eventually lead to a valid way of making change.
See the code for an implementation of count_coins.
For the times when either recursive call returns None, you don't want to include that in your branches when making the tree. If both recursive calls return None, then you want to return None.
Each leaf for the count_coins_tree(15, [1, 5, 10, 25]) tree is one of these groupings.
- 15 1-cent coins
- 10 1-cent, 1 5-cent coins
- 5 1-cent, 2 5-cent coins
- 5 1-cent, 1 10-cent coins
- 3 5-cent coins
- 1 5-cent, 1 10-cent coin
Q4: Extra Practice
Difficulty: >⭐⭐⭐