# 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))
4
```

**Part 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}'
```

Run in 61A Code
### 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: >⭐⭐⭐**