# Final Review A: Questions

RFa.1.

In your own words, describe how insertion sort works.

RFa.2.

Complete the following partial implementation of insertion sort so that it reorders its parameter list into increasing order.

```def insertion_sort(data):     for i in range(1, len(data)):         t = data[i]         j = i - 1         # Your answer goes here         data[j + 1] = t ```
RFa.3.

In your own words, describe how merge sort works. What is the base case?

RFa.4.

Complete the `Citizen` class below so that the `get_id` method returns the `id` parameter provided when the `Citizen` is constructed. The `run` function at right illustrates how another function might interact with the `Citizen` class.

 ```class Citizen:     def __init__(self, id):     def get_id(self): ``` ```def run():     b = Citizen(2)     d = Citizen(4)     print(b.get_id())  # displays 2     print(d.get_id())  # displays 4 ```
RFa.5.

Write a `Student` class for tracking a student's grades in CSCI 150. The class includes two data attributes, both integers: one named `total` tracks how many points the student has earned thus far, and another named `possible` tracks how many possible points the student could have earned thus far. The class includes one constructor and two methods.

`Student()`

(Constructor) Constructs a student who has had completed no graded work for the class.

`register(value, poss)`

Registers that this student has completed work with a grade of `value` out of a possible `poss`.

`get_percent()`

Returns the percent of possible points thus far earned. (The method returns 100.0 when no graded work has been completed.)

The following fragment illustrates how a program might use the `Student` class.

```robin = Student() print(robin.get_percent())  # displays 100.0 robin.register(20, 30) robin.register(10, 20) print(robin.get_percent())  # displays 60.0 ```
RFa.6.

Complete the `Scorecard` class below so that the `get_sum` method returns the total of all the scores given into the `tally` method. Thus, a program might use the `Scorecard` class as follows.

```game = ScoreCard() print(game.get_sum())  # displays 0 game.tally(4) game.tally(6) print(game.get_sum())  # displays 10 game.tally(5) print(game.get_sum())  # displays 15 ```
```class Scorecard:     def __init__(self):     def tally(self, score):     def get_sum(self): ```
RFa.7.

Write a class `GolfScore` providing the following constructor and methods.

`GolfScore(par)`

(Constructor) Constructs a score card for tallying scores, where `par` is the goal for each score.

`add(score)`

Adds a score onto this score card. (The easiest way to solve this problem is not to remember each individual score added into the card; however, you may approach the problem that way if you wish.)

`get_birdie_count()`

Returns the number of values added into this score card that are below `par`.

`get_par_difference()`

Returns the sum over all scores of the difference between the score and the goal. For example, if the goal is 3, and the scores added are 2 and 5, then the method returns 1, since that is the sum of 2 − 3 and 5 − 3.

The following fragment illustrates how a program might use the `GolfScore` class.

```card = GolfScore(3) card.add(2) card.add(3) card.add(2) card.add(4) print(card.get_birdie_count())   # displays 2, since two scores were below 3 print(card.get_par_difference()) # displays -1 (= (2-3) + (3-3) + (2-3) + (4-3)) ```
RFa.8.

Write an `Interval` class for tracking a range of numbers on the number line. It should have the following constructor and methods.

`Interval(first)`

(Constructor) Constructs an interval consisting of just one number, `first`.

`extend(next)`

If this interval doesn't already contain `next`, it is extended just enough to include `next`.

`contains(query)`

Returns `True` if this interval contains `query`.

The below fragment illustrates how this might be used.

```Interval i = Interval(5) print(i.contains(4))   # False i.extend(2) i.extend(6) print(i.contains(4))   # True print(i.contains(6))   # True print(i.contains(6.1)) # False ```
RFa.9.

The game of Nim proceeds by players taking turns selecting a pile and removing 1 or more stones from that pile. The player removing the last stone wins.

Draw a complete game tree for the game of Nim beginning with two piles, both containing two stones. To draw a node, list the number of stones in each pile; for example, the top node will be “2,2”.

Do not include the minimax values assigned to each node in your tree.

RFa.10.

Label all internal nodes of the following tic-tac-toe game tree with the value that minimax search would compute. I've already labeled the leaves.

RFa.11.

Suppose a game player has constructed a game tree as given below. In this tree, high numbers represent good boards for X, and it is currently X's move.

Fill in all empty circles with the values assigned them according to the minimax evaluation algorithm.

RFa.12.

Suppose a game player has constructed the following game tree.

In this tree, high numbers represent good boards for X, and it is currently X's move. (As you can see, X has three possible moves from which to choose, labeled A, B, and C.)

1. Fill in all empty circles with the values assigned them according to the minimax evaluation algorithm.
2. Which move will X choose?
RFa.13.

Suppose we have developed the below game tree through recursive evaluation, in an attempt to find the value of node A. According to alpha-beta search, node C need not be evaluated. Explain why. (In this example, we are imagining that at A, it is X's turn, and larger numbers denote a more positive situation for X.)

# Final Review A: Solutions

RFa.1.

We observe that the first element, considered alone, is already in sorted order. We then insert successive elements in the list into this already-sorted segment of the list, each time shifting values back to make room for the element we are inserting. Once the already-sorted segment includes all list elements, we are done.

RFa.2.
```def insertion_sort(data):     for i in range(1, len(data)):         t = data[i]         j = i - 1         while j >= 0 and data[j] > t:             data[j + 1] = data[j]             j = j - 1         data[j + 1] = t ```
RFa.3.

The base case is when the array has one element; in this case, nothing happens.

When there is more than one element, merge sort consists of three major steps. First, we split the array into two halves. Then we sort each half through recursively applying the merge sort algorithm to each. And finally, we merge the two halves together by successively “removing” the lesser of the two halves' first elements and placing the removed item into the array holding our result.

RFa.4.
```class Citizen:     def __init__(self, id):         self.ident = id     def get_id(self):         return self.ident ```
RFa.5.
```class Student:     def __init__(self):         self.total = 0.0         self.possible = 0.0     def register(self, value, poss):         self.total += value         self.possible += poss     def get_percent(self):         if self.possible == 0.0:             return 100.0         else:             return 100.0 * self.total / self.possible ```
RFa.6.
```class Scorecard:     def __init__(self):         self.total = 0     def tally(self, score):         self.total += score     def get_sum(self):         return self.total ```
RFa.7.
```class GolfScore:     def __init__(self, par):         self.goal = par         self.birdies = 0         self.par_diff = 0     def add(self, score):         if score < self.goal:             self.birdies += 1         self.par_diff += score - goal     def get_birdie_count(self):         return self.birdies     def get_par_difference(self):         return self.par_diff ```
RFa.8.
```class Interval:     def __init__(self, start):         self.start = start         self.stop = stop     def extend(self, next):         self.start = min(self.start, next)         self.stop = max(self.stop, next)     def contains(self, query):         return self.start <= query <= self.stop ```
RFa.9.
RFa.10.
RFa.11.
RFa.12.
 a. b. B
RFa.13.

Let's start by considering B. At B it is O's turn, and O will choose the smaller of 0 and C's value. Thus, the value of B will be 0 or less. At A it is X's turn, and X choose the larger of 3 and whatever B's value will turn out to be. But since we know B will be 0 or less, so it will inevitably choose 3, regardless of whatever C might turn out to be. So if we simply want to know A's value, we need not bother with determining C's value.