(ML; 60 min)

**Store your answers in machine-learning/analysis/logistic_regression.py**

Suppose that you have a dataset of points $(x,y)$ where $x$ is the number of hours that a player has practiced Space Empires and $y$ is their probability of winning against an average player.

`data = [(10, 0.05), (100, 0.35), (1000, 0.95)]`

Fit a function $y=\dfrac{1}{1+e^{\beta_0 + \beta_1 x}}$ to the following data, using matrix methods involving the pseudoinverse.

a) Write the system of equations:

```
__ = 1/(1 + e^(beta_0 + beta_1 * ___) )
__ = 1/(1 + e^(beta_0 + beta_1 * ___) )
__ = 1/(1 + e^(beta_0 + beta_1 * ___) )
```

b) Convert the system to a system of linear equations:

```
beta_0 + beta_1 * ___ = ___
beta_0 + beta_1 * ___ = ___
beta_0 + beta_1 * ___ = ___
```

c) Solve for `beta_0`

and `beta_1`

using the pseudoinverse.

d) For a player who has practiced 500 hours, compute the probability of winning against an average player.

e) How many hours does an average player practice? Tip: an average player will have 0.5 probability of winning against an average player, so you just need to solve the equation `0.5 = 1/(1 + e^(beta_0 + beta_1 * x) )`

for `x`

.

(Algo; 45 min)

Implement breadth-first search in your `Graph`

class. This will be very similar to the breadth-first search in your `Tree`

class, but now you will have to make sure that you do not revisit any nodes (because now there are multiple paths from one node to another).

- Luckily, this is a simple adjustment: keep a list of the nodes you've visited, and only make the recursive call on unvisited nodes.

**Example:**

```
>>> edges = [(0,1),(1,2),(1,3),(3,4),(1,4),(4,5)]
>>> vertices = ['a','b','c','d','e','f']
>>> graph = Graph(edges, vertices)
>>> graph.breadth_first_search(2) (note: 2 is the index of the starting node)
[2, 1, 0, 3, 4, 5] (note: in class, we printed out the values, but let's instead return a list of the indices)
other answers are valid, e.g. [2, 1, 4, 3, 0, 5]
```

(Space Empires; 90 min)

**Note: this is the same problem as the previous assignment -- that means you've got an extra class to catch up on it, and it also means that you should indeed fully catch up on it.**

Implement the following additional tests in `tests/test_combat_test_player.py`

:

At the end of Turn 1 Economic Phase:

- Player 1 has 1 CP, 3 scouts at (2,2), 1 destroyer at (2,0)
- Player 2 has 4 CP, 1 destroyer at (2,4).

At the end of Turn 2 Movement Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has 1 destroyer at (2,2)

At the end of Turn 2 Combat Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has no ships other than its home colony/shipyards

At the end of Turn 2 Economic Phase:

- Player 1 has 0 CP, 3 scouts at (2,2), 1 destroyer at (2,2).
- Player 2 has 1 CP, 1 scout at (2,4).

At the end of Turn 3 Movement Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has 1 scout at (2,2)

At the end of Turn 3 Combat Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has no ships other than its home colony/shipyards

At the end of Turn 3 Economic Phase:

- Player 1 has 0 CP, 2 scouts and 1 destroyer at (2,0).
- Player 2 has 4 CP, no ships other than its home colony/shipyards

**Note: These tests are based on the following game events file. I've done my best to ensure this is accurate, but if your game doesn't match up and you think there might be an error in the events, please post about it.**

```
STARTING CONDITIONS
Players 1 and 2
are CombatTestingPlayers
start with 20 CPs
have an initial fleet of 3 scouts, 3 colony ships, 4 ship yards
---
TURN 1 - MOVEMENT PHASE
Player 1:
Scouts 1,2,3: (2,0) --> (2,2)
Colony Ships 4,5,6: (2,0) --> (2,2)
Player 2:
Scouts 1,2,3: (2,4) --> (2,2)
Colony Ships 4,5,6: (2,4) --> (2,2)
COMBAT PHASE
Colony Ships are removed
| PLAYER | SHIP | HEALTH |
----------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 1 | 1 |
| 2 | Scout 2 | 1 |
| 2 | Scout 3 | 1 |
Attack 1
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Largest Roll to Hit: 3
Die Roll: 1
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 2 | 1 |
| 2 | Scout 3 | 1 |
Attack 2
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 2
Largest Roll to Hit: 3
Die Roll: 2
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 3 | 1 |
Attack 3
Attacker: Player 1 Scout 3
Defender: Player 2 Scout 3
Largest Roll to Hit: 3
Dice Roll: 3
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
Combat phase complete
------------------------
TURN 1 - ECONOMIC PHASE
Player 1
INCOME/MAINTENANCE (starting CP: 20)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: -1 CP/Scout x 3 Scouts = -3 CP
PURCHASES (starting CP: 20)
ship size technology 2: -10 CP
destroyer: -9 CP
REMAINING CP: 1
Player 2
INCOME/MAINTENANCE (starting CP: 20)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: 0
PURCHASES (starting CP: 23)
ship size technology 2: -10 CP
destroyer: -9 CP
REMAINING CP: 4
------------------------
TURN 2 - MOVEMENT PHASE
Player 1:
Scouts 1,2,3: stay at (2,2)
Destroyer 1 : (2,0) --> (2,2)
Player 2:
Destroyer 1: (2,4) --> (2,2)
------------------------
TURN 2 - COMBAT PHASE
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 2 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
Attack 1
Attacker: Player 1 Destroyer 1
Defender: Player 2 Destroyer 1
Largest Roll to Hit: 4
Dice Roll: 4
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
------------------------
TURN 2 - ECONOMIC PHASE
Player 1
INCOME/MAINTENANCE (starting CP: 1)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP
REMAINING CP: 0
Player 2
INCOME/MAINTENANCE (starting CP: 4)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: 0
PURCHASES (starting CP: 7)
scout: -6 CP
REMAINING CP: 1
------------------------
TURN 3 - MOVEMENT PHASE
Player 1:
Scouts 1,2,3: stay at (2,2)
Destroyer 1 : stay at (2,2)
Player 2:
Scout 1: (2,4) --> (2,2)
------------------------
TURN 3 - COMBAT PHASE
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 1 | 1 |
Attack 1
Attacker: Player 1 Destroyer 1
Defender: Player 2 Scout 1
Largest Roll to Hit: 4
Dice Roll: 5
Hit or Miss: Miss
Attack 2
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Largest Roll to Hit: 3
Dice Roll: 6
Hit or Miss: Miss
Attack 3
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 1
Largest Roll to Hit: 3
Dice Roll: 1
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
------------------------
TURN 3 - ECONOMIC PHASE
Player 1
INCOME/MAINTENANCE (starting CP: 0)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP
REMOVALS
remove scout 3 due to inability to pay maintenance costs
REMAINING CP: 0
Player 2
INCOME/MAINTENANCE (starting CP: 1)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: 0
REMAINING CP: 4
```

(Stats; 45 min)

**For this problem, put your code in assignment-problems/src/conditional_probability.py**

During class, each person created a distribution of coin flips.

```
flips = {
'George': 'THTH HTHT THTH HHTH THTH TTHT THTH TTTH THTH TTHT THHT HTTH THTH THHT THHT THTH THTH THHT THTH THTH',
'David': 'TTHH HHTT HHTT TTHH HTHT THTH THTH THTH HTHT HTHT THTH HTHT THHH THTH HHTT HHTT TTTH HHTH HTHH TTTH',
'Elijah': 'THTT HTHT HTHH HHHT TTHH THHH TTTT HHTT TTTH TTHH HTHT HTHT TTTT HTTT TTTH HTTT TTHH THTH THHH HTHH',
'Colby': 'HTTH HTHH THTT HHTH TTHT HTTT THHH TTHH HHTT THTH HHTT THTH THHH TTHH THTT HHTH HTTH HTHH TTHT HTTT',
'Justin': 'THTT HTHT TTTH THHT HTHH TTTH THTH HHTH TTTT HTTH HHTT THHH HHHH THTH HTTH TTHH HTHT HHHT THHT TTTH'
}
```

For each person, print out the following probabilities:

$P(\text{ next flip was heads | previous flip was heads })$

$P(\text{ next flip was tails | previous flip was heads })$

$P(\text{ next flip was heads | previous flip was tails })$

$P(\text{ next flip was tails | previous flip was tails })$

**Also, print out the probabilities on the simple dataset HHTTHT to double check that your code is correct.**

For the dataset

`HHTTHT`

, the pairs are`HH`

,`HT`

,`TT`

,`TH`

,`HT`

. So,$P(\text{ next flip was heads | previous flip was heads }) = 1/3$

$P(\text{ next flip was tails | previous flip was heads }) = 2/3$

$P(\text{ next flip was heads | previous flip was tails }) = 1/2$

$P(\text{ next flip was tails | previous flip was tails }) = 1/2$

**Note:** Using Bayes' Rule,

we have that

$$\begin{align*} P(\text{ next flip was heads | previous flip was tails }) &= \dfrac{\text{count}(\text{ next flip was heads AND previous flip was tails })}{\text{count}(\text{ previous flip was tails })} \\ &= \dfrac{\text{count}(\text{ consecutive pairs in which tails was followed IMMEDIATELY by heads })}{\text{count}(\text{ consecutive pairs in which previous flip was tails })}. \end{align*}$$(Algo; 45 min)

Implement depth-first search in your `Graph`

class. This will be very similar to the depth-first search in your `Tree`

class, but now you will have to make sure that you do not revisit any nodes (because now there are multiple paths from one node to another).

- Luckily, this is a simple adjustment: keep a list of the nodes you've visited, and only make the recursive call on unvisited nodes.

**Example:**

```
>>> edges = [(0,1),(1,2),(1,3),(3,4),(1,4)]
>>> vertices = ['a','b','c','d','e']
>>> graph = Graph(edges, vertices)
>>> graph.depth_first_search(2) (note: 2 is the index of the starting node)
[2, 1, 3, 4, 0] (note: in class, we printed out the values, but let's instead return a list of the indices)
other answers are valid, e.g. [2, 1, 0, 4, 3]
```

(Space Empires; 90 min)

Implement the following additional tests in `tests/test_combat_test_player.py`

:

At the end of Turn 1 Economic Phase:

- Player 1 has 1 CP, 3 scouts at (2,2), 1 destroyer at (2,0)
- Player 2 has 4 CP, 1 destroyer at (2,4).

At the end of Turn 2 Movement Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has 1 destroyer at (2,2)

At the end of Turn 2 Combat Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has no ships other than its home colony/shipyards

At the end of Turn 2 Economic Phase:

- Player 1 has 0 CP, 3 scouts at (2,2), 1 destroyer at (2,2).
- Player 2 has 1 CP, 1 scout at (2,4).

At the end of Turn 3 Movement Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has 1 scout at (2,2)

At the end of Turn 3 Combat Phase:

- Player 1 has 3 scouts and 1 destroyer at (2,2)
- Player 2 has no ships other than its home colony/shipyards

At the end of Turn 3 Economic Phase:

- Player 1 has 0 CP, 2 scouts and 1 destroyer at (2,0).
- Player 2 has 4 CP, no ships other than its home colony/shipyards

**Note: These tests are based on the following game events file. I've done my best to ensure this is accurate, but if your game doesn't match up and you think there might be an error in the events, please post about it.**

```
STARTING CONDITIONS
Players 1 and 2
are CombatTestingPlayers
start with 20 CPs
have an initial fleet of 3 scouts, 3 colony ships, 4 ship yards
---
TURN 1 - MOVEMENT PHASE
Player 1:
Scouts 1,2,3: (2,0) --> (2,2)
Colony Ships 4,5,6: (2,0) --> (2,2)
Player 2:
Scouts 1,2,3: (2,4) --> (2,2)
Colony Ships 4,5,6: (2,4) --> (2,2)
COMBAT PHASE
Colony Ships are removed
| PLAYER | SHIP | HEALTH |
----------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 1 | 1 |
| 2 | Scout 2 | 1 |
| 2 | Scout 3 | 1 |
Attack 1
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Largest Roll to Hit: 3
Die Roll: 1
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 2 | 1 |
| 2 | Scout 3 | 1 |
Attack 2
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 2
Largest Roll to Hit: 3
Die Roll: 2
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 3 | 1 |
Attack 3
Attacker: Player 1 Scout 3
Defender: Player 2 Scout 3
Largest Roll to Hit: 3
Dice Roll: 3
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
Combat phase complete
------------------------
TURN 1 - ECONOMIC PHASE
Player 1
INCOME/MAINTENANCE (starting CP: 20)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: -1 CP/Scout x 3 Scouts = -3 CP
PURCHASES (starting CP: 20)
ship size technology 2: -10 CP
destroyer: -9 CP
REMAINING CP: 1
Player 2
INCOME/MAINTENANCE (starting CP: 20)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: 0
PURCHASES (starting CP: 23)
ship size technology 2: -10 CP
destroyer: -9 CP
REMAINING CP: 4
------------------------
TURN 2 - MOVEMENT PHASE
Player 1:
Scouts 1,2,3: stay at (2,2)
Destroyer 1 : (2,0) --> (2,2)
Player 2:
Destroyer 1: (2,4) --> (2,2)
------------------------
TURN 2 - COMBAT PHASE
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 2 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
Attack 1
Attacker: Player 1 Destroyer 1
Defender: Player 2 Destroyer 1
Largest Roll to Hit: 4
Dice Roll: 4
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
------------------------
TURN 2 - ECONOMIC PHASE
Player 1
INCOME/MAINTENANCE (starting CP: 1)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP
REMAINING CP: 0
Player 2
INCOME/MAINTENANCE (starting CP: 4)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: 0
PURCHASES (starting CP: 7)
scout: -6 CP
REMAINING CP: 1
------------------------
TURN 3 - MOVEMENT PHASE
Player 1:
Scouts 1,2,3: stay at (2,2)
Destroyer 1 : stay at (2,2)
Player 2:
Scout 1: (2,4) --> (2,2)
------------------------
TURN 3 - COMBAT PHASE
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
| 2 | Scout 1 | 1 |
Attack 1
Attacker: Player 1 Destroyer 1
Defender: Player 2 Scout 1
Largest Roll to Hit: 4
Dice Roll: 5
Hit or Miss: Miss
Attack 2
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Largest Roll to Hit: 3
Dice Roll: 6
Hit or Miss: Miss
Attack 3
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 1
Largest Roll to Hit: 3
Dice Roll: 1
Hit or Miss: Hit
| PLAYER | SHIP | HEALTH |
---------------------------------------------
| 1 | Destroyer 1 | 1 |
| 1 | Scout 1 | 1 |
| 1 | Scout 2 | 1 |
| 1 | Scout 3 | 1 |
------------------------
TURN 3 - ECONOMIC PHASE
Player 1
INCOME/MAINTENANCE (starting CP: 0)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: -1 CP/Scout x 3 Scouts -1 CP/Destroyer x 1 Destroyer = -4 CP
REMOVALS
remove scout 3 due to inability to pay maintenance costs
REMAINING CP: 0
Player 2
INCOME/MAINTENANCE (starting CP: 1)
colony income: +3 CP/Colony x 1 Colony = +3 CP
maintenance costs: 0
REMAINING CP: 4
```

(Stats; 45 min)

**For this problem, put your code in assignment-problems/src/approximations_of_randomness.py**

During class, each person created a distribution of coin flips.

```
flips = {
'George': 'THTH HTHT THTH HHTH THTH TTHT THTH TTTH THTH TTHT THHT HTTH THTH THHT THHT THTH THTH THHT THTH THTH',
'David': 'TTHH HHTT HHTT TTHH HTHT THTH THTH THTH HTHT HTHT THTH HTHT THHH THTH HHTT HHTT TTTH HHTH HTHH TTTH',
'Elijah': 'THTT HTHT HTHH HHHT TTHH THHH TTTT HHTT TTTH TTHH HTHT HTHT TTTT HTTT TTTH HTTT TTHH THTH THHH HTHH',
'Colby': 'HTTH HTHH THTT HHTH TTHT HTTT THHH TTHH HHTT THTH HHTT THTH THHH TTHH THTT HHTH HTTH HTHH TTHT HTTT',
'Justin': 'THTT HTHT TTTH THHT HTHH TTTH THTH HHTH TTTT HTTH HHTT THHH HHHH THTH HTTH TTHH HTHT HHHT THHT TTTH'
}
```

a) Treating these coin flips as simulations of 20 samples of 4 flips, compute the KL divergence between each simulation and the true distribution. Print out your results.

b) Print out the answer to the following question: whose simulation was the best approximation of true random coin flipping?

(Algo; 90 min)

a) In the file `graph/src/node.py`

, create a class `Node`

that

is initialized with an

`index`

, andhas the attributes

`index`

,`value`

, and`neighbors`

.

b) In the file `graph/tests/test_node.py`

, `assert`

that your `Node`

class passes the following tests. (If you want to remove the `>>>`

at the beginning, use this text replacement tool.)

```
>>> string_node = Node(0)
>>> string_node.index
0
>>> string_node.set_value('asdf')
>>> string_node.value
'asdf'
>>> string_node.neighbors
[]
>>> numeric_node = Node(1)
>>> numeric_node.set_value(765)
>>> numeric_node.set_neighbor(string_node)
>>> numeric_node.neighbors[0].value
'asdf'
>>> string_node.neighbors[0].value
765
>>> array_node = Node(2)
>>> array_node.set_value([[1,2],[3,4]])
>>> array_node.set_neighbor(numeric_node)
>>> array_node.neighbors[0].value
765
>>> numeric_node.neighbors[1].value
[[1,2],[3,4]]
```

c) In the file `graph/src/graph.py`

, create a class `Graph`

that

is initialized with list of

`edges`

(an edge is a tuple of indices) and`vertices`

(a vertex is a node value), andhas the attribute

`nodes`

.

d) In the file `graph/tests/test_graph.py`

, `assert`

that your class passes the following tests.

```
>>> edges = [(0,1),(1,2),(1,3),(3,4),(1,4)]
>>> vertices = ['a','b','c','d','e']
>>> graph = Graph(edges, vertices)
>>> [node.index for node in graph.nodes]
[0, 1, 2, 3, 4]
>>> [node.value for node in graph.nodes]
['a','b','c','d','e']
>>> [len(node.neighbors) for node in graph.nodes]
[1, 4, 1, 2, 2]
```

(Space Empires; 60 min)

Continue writing the game events log, up until a combat round occurs in which some player has a destroyer. (You can stop writing the log once you finish that combat round.)

With regards to the die rolls, each combat round should pick up where the previous round left off. So since the first combat ended with a die roll of 3, the second combat will begin with a die roll of 4.

```
STARTING CONDITIONS
Players 1 and 2
are CombatTestingPlayers
start with 20 CPs
have an initial fleet of 3 scouts and 3 colony ships
---
TURN 1
MOVEMENT PHASE
Player 1, Movement 1
Scouts 1,2,3: (2,0) --> (2, 1)
Colony Ships 4,5,6: (2,0) --> (2,1)
Player 2, Movement 1
Scouts 1,2,3: (2,4) --> (2, 3)
Colony Ships 4,5,6: (2,4) --> (2,3)
Player 1, Movement 2
Scout 1,2,3: (2, 1) --> (2, 2)
Player 2, Movement 2
Scouts 1,2,3: (2, 3) --> (2, 2)
Colony Ships 4,5,6: (2,1) --> (2,2)
Players 1/2, Movement 3
No player moved!
Player 1, Final Locations:
Scout 1: (2, 2)
Scout 2: (2, 2)
Scout 3: (2, 2)
Colony Ship 4: (2,2)
Colony Ship 5: (2,2)
Colony Ship 6: (2,2)
Player 2, Final Locations:
Scout 1: (2, 2)
Scout 2: (2, 2)
Scout 3: (2, 2)
Colony Ship 4: (2,2)
Colony Ship 5: (2,2)
Colony Ship 6: (2,2)
COMBAT PHASE
Remaining ships: (list in the table below)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
---------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
4 | 2 | Scout 1 | 1 |
5 | 2 | Scout 2 | 1 |
6 | 2 | Scout 3 | 1 |
Attack 1
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Miss Threshold: 3
Die Roll: 1
Hit or Miss: Hit (since Die Roll <= Miss Threshold)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
-------------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
4 | 2 | Scout 2 | 1 |
5 | 2 | Scout 3 | 1 |
Attack 2
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 2
Hit Threshold: 3
Die Roll: 2
Hit or Miss: Hit (since Die Roll <= Miss Threshold)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
-------------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
5 | 2 | Scout 3 | 1 |
Attack 3
Attacker: Player 1 Scout 3
Defender: Player 2 Scout 3
Hit Threshold: 3
Dice Roll: 3
Hit or Miss: Hit (since Die Roll <= Miss Threshold)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
-------------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
Combat phase complete
ECONOMIC PHASE
... (continue here)
```

(ML; 60 min)

**Create a file machine-learning/analysis/sandwich_ratings_dummy_variables.py to store your code/answers for this problem.**

```
Slices Beef | Tbsp Peanut Butter | Condiments | Rating |
--------------------------------------------------------------
0 | 0 | - | 1 |
0 | 0 | mayo | 1 |
0 | 0 | jelly | 4 |
0 | 0 | mayo, jelly | 0 |
5 | 0 | - | 4 |
5 | 0 | mayo | 8 |
5 | 0 | jelly | 1 |
5 | 0 | mayo, jelly | 0 |
0 | 5 | - | 5 |
0 | 5 | mayo | 0 |
0 | 5 | jelly | 9 |
0 | 5 | mayo, jelly | 0 |
5 | 5 | - | 0 |
5 | 5 | mayo | 0 |
5 | 5 | jelly | 0 |
5 | 5 | mayo, jelly | 0 |
```

a) Replace the `Condiments`

feature with the dummy variables `Mayo (M)`

and `Jelly (J)`

. **Print out the resulting array.**

```
B = slices roast beef
P = tbsp peanut butter
M = mayo
J = jelly
R = rating
B P M J R
[[ 0, 0, 0, 0, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 0, 0, 0, 1, 4 ],
[ 0, 0, 1, 1, 0 ],
[ 5, 0, _, _, 4 ],
[ 5, 0, _, _, 8 ],
[ 5, 0, _, _, 1 ],
[ 5, 0, _, _, 0 ],
[ 0, 5, _, _, 5 ],
[ 0, 5, _, _, 0 ],
[ 0, 5, _, _, 9 ],
[ 0, 5, _, _, 0 ],
[ 5, 5, _, _, 0 ],
[ 5, 5, _, _, 0 ],
[ 5, 5, _, _, 0 ],
[ 5, 5, _, _, 0 ]]
```

b) Include interaction features. **Print out the resulting array.**

```
B P M J BP BM BJ PM PJ MJ R
[[ 0, 0, 0, 0, __, __, __, __, __, __, 1 ],
[ 0, 0, 1, 0, __, __, __, __, __, __, 1 ],
[ 0, 0, 0, 1, __, __, __, __, __, __, 4 ],
[ 0, 0, 1, 1, __, __, __, __, __, __, 0 ],
[ 5, 0, _, _, __, __, __, __, __, __, 4 ],
[ 5, 0, _, _, __, __, __, __, __, __, 8 ],
[ 5, 0, _, _, __, __, __, __, __, __, 1 ],
[ 5, 0, _, _, __, __, __, __, __, __, 0 ],
[ 0, 5, _, _, __, __, __, __, __, __, 5 ],
[ 0, 5, _, _, __, __, __, __, __, __, 0 ],
[ 0, 5, _, _, __, __, __, __, __, __, 9 ],
[ 0, 5, _, _, __, __, __, __, __, __, 0 ],
[ 5, 5, _, _, __, __, __, __, __, __, 0 ],
[ 5, 5, _, _, __, __, __, __, __, __, 0 ],
[ 5, 5, _, _, __, __, __, __, __, __, 0 ],
[ 5, 5, _, _, __, __, __, __, __, __, 0 ]]
```

c) To help you ensure that your transformed dataset is correct, I'll tell you that the **sum of all the numbers in your matrix, INCLUDING the ratings, should be equal to 313.**

`assert`

that the above statement is true.

d) Fit a linear model to the data

```
rating = beta_0
+ beta_1 ( slices beef ) + beta_2 ( tbsp pb ) + beta_3 ( mayo ) + beta_4 ( jelly )
+ beta_5 ( slices beef ) ( tbsp pb ) + beta_6 ( slices beef ) ( jelly ) + beta_7 ( slices beef ) ( jelly )
+ beta_8 ( tbsp pb ) ( mayo ) + beta_9 ( tbsp pb ) ( jelly )
+ beta_10 ( mayo ) ( jelly )
```

print out your coefficients, **labeled with the corresponding variables**:

```
COEFFICIENTS
bias term: ___
beef: ___
peanut butter: ___
mayo: ___
jelly: ___
beef & peanut butter: ___
beef & mayo: ___
beef & jelly: ___
peanut butter & mayo: ___
peanut butter & jelly: ___
mayo & jelly: ___
...
```

e) Print out the following predictions:

```
PREDICTED RATINGS
2 slices beef + mayo: __
2 slices beef + jelly: __
3 tbsp peanut butter + jelly: __
3 tbsp peanut butter + jelly + mayo: ___
2 slices beef + 3 tbsp peanut butter + jelly + mayo: ___
```

(Stats; 30 min)

**Create a file assignment-problems/detecting_biased_coins.py to store your code/answers for this problem.**

Suppose that you run an experiment where you flip a coin 3 times, and repeat that trial 25 times. You run this experiment on 3 different coins, and get the following results:

```
coin_1 = ['TTH', 'HHT', 'HTH', 'TTH', 'HTH', 'TTH', 'TTH', 'TTH', 'THT', 'TTH', 'HTH', 'HTH', 'TTT', 'HTH', 'HTH', 'TTH', 'HTH', 'TTT', 'TTT', 'TTT', 'HTT', 'THT', 'HHT', 'HTH', 'TTH']
coin_2 = ['HTH', 'HTH', 'HTT', 'THH', 'HHH', 'THH', 'HHH', 'HHH', 'HTT', 'TTH', 'TTH', 'HHT', 'TTH', 'HTH', 'HHT', 'THT', 'THH', 'THT', 'TTH', 'TTT', 'HHT', 'THH', 'THT', 'THT', 'TTT']
coin_3 = ['HHH', 'THT', 'HHT', 'HHT', 'HTH', 'HHT', 'HHT', 'HHH', 'TTT', 'THH', 'HHH', 'HHH', 'TTH', 'THH', 'THH', 'TTH', 'HTT', 'TTH', 'HTT', 'HHT', 'TTH', 'HTH', 'THT', 'THT', 'HTH']
```

Let $P_i(x)$ be the probability of getting $x$ heads in a trial of 3 tosses, using the $i$th coin. Plot the distributions $P_1(x),$ $P_2(x),$ and $P_3(x)$ on the same graph. Be sure to label them.

- (This is similar to when you plotted the Monte Carlo distributions, but this time you're given the simulation results.)

Based on the plot of the distributions, what conclusions can you make about the coins? For each coin, does it appear to be fair, biased towards heads, or biased towards tails? Write your answer as a comment.

(Space Empires; 90 min)

Write a testing file `tests/test_combat_testing_player.py`

to ensure that a game on a $5 \times 5$ grid with two `CombatTestingPlayer`

s proceeds correctly.

At the end of Turn 1 Movement Phase:

- Player 1 has 3 scouts and 3 colony ships at (2,2)
- Player 2 has 3 scouts and 3 colony ships at (2,2)

At the end of Turn 1 Combat Phase:

- Player 1 has 3 scouts at (2,2) and no colony ships (though it does have its home colony)
- Player has no scouts and no colony ships (though it does have its home colony)

**Note:** These tests are based on Elijah's game events file, which we verified during class.

```
STARTING CONDITIONS
Players 1 and 2
are CombatTestingPlayers
start with 20 CPs
have an initial fleet of 3 scouts and 3 colony ships
---
TURN 1
MOVEMENT PHASE
Player 1, Movement 1
Scouts 1,2,3: (2,0) --> (2, 1)
Colony Ships 4,5,6: (2,0) --> (2,1)
Player 2, Movement 1
Scouts 1,2,3: (2,4) --> (2, 3)
Colony Ships 4,5,6: (2,4) --> (2,3)
Player 1, Movement 2
Scout 1,2,3: (2, 1) --> (2, 2)
Colony Ships 4,5,6: (2,1) --> (2,2)
Player 2, Movement 2
Scouts 1,2,3: (2, 3) --> (2, 2)
Colony Ships 4,5,6: (2,1) --> (2,2)
Players 1/2, Movement 3
No player moved!
Player 1, Final Locations:
Scout 1: (2, 2)
Scout 2: (2, 2)
Scout 3: (2, 2)
Colony Ship 4: (2,2)
Colony Ship 5: (2,2)
Colony Ship 6: (2,2)
Player 2, Final Locations:
Scout 1: (2, 2)
Scout 2: (2, 2)
Scout 3: (2, 2)
Colony Ship 4: (2,2)
Colony Ship 5: (2,2)
Colony Ship 6: (2,2)
COMBAT PHASE
Remaining ships: (list in the table below)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
---------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
4 | 2 | Scout 1 | 1 |
5 | 2 | Scout 2 | 1 |
6 | 2 | Scout 3 | 1 |
Attack 1
Attacker: Player 1 Scout 1
Defender: Player 2 Scout 1
Miss Threshold: 3
Die Roll: 1
Hit or Miss: Hit (since Die Roll <= Miss Threshold)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
-------------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
4 | 2 | Scout 2 | 1 |
5 | 2 | Scout 3 | 1 |
Attack 2
Attacker: Player 1 Scout 2
Defender: Player 2 Scout 2
Hit Threshold: 3
Die Roll: 2
Hit or Miss: Hit (since Die Roll <= Miss Threshold)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
-------------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
5 | 2 | Scout 3 | 1 |
Attack 3
Attacker: Player 1 Scout 3
Defender: Player 2 Scout 3
Hit Threshold: 3
Dice Roll: 3
Hit or Miss: Hit (since Die Roll <= Miss Threshold)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
-------------------------------------------------------------
1 | 1 | Scout 1 | 1 |
2 | 1 | Scout 2 | 1 |
3 | 1 | Scout 3 | 1 |
Combat phase complete
ECONOMIC PHASE
...
```

(ML; 60 min)

**Create a file machine-learning/analysis/sandwich_ratings_interaction_terms.py to store your code/answers for this problem.**

The food manufacturing company (from the previous assignment) decided to gather some more data on roast beef and peanut butter sandwiches. (The new dataset has two additional rows at the bottom.)

```
Slices of Roast Beef | Tablespoons of Peanut Butter | Rating |
--------------------------------------------------------------
0 | 0 | 1 |
1 | 0 | 2 |
2 | 0 | 4 |
4 | 0 | 8 |
6 | 0 | 9 |
0 | 2 | 2 |
0 | 4 | 5 |
0 | 6 | 7 |
0 | 8 | 6 |
2 | 2 | 0 | (new data)
3 | 4 | 0 | (new data)
```

a) Using the pseudoinverse, fit another model

$$ \text{rating} = \beta_0 + \beta_1 (\text{slices beef}) + \beta_2 (\text{tbsp peanut butter}).$$Include your answers to the following questions as comments in your code.

```
# QUESTION 1
# What is the model?
# rating = ___ + ___ * (slices beef) + ___ * (tbsp peanut butter)
# QUESTION 2
# What is the predicted rating of a sandwich with 5 slices of roast beef AND
# 5 tablespoons of peanut butter (on the same sandwich)?
# ___
# QUESTION 3
# How does this prediction compare to that from the previous assignment? Did
# including the additional data make the prediction trustworthy? Why or why not?
# ___
```

b) Again using the pseudoinverse, fit a model that has an "interaction term" corresponding to $\beta_3.$

$$ \text{rating} = \beta_0 + \beta_1 (\text{slices beef}) + \beta_2 (\text{tbsp peanut butter}) + \beta_3 (\text{slices beef})(\text{tbsp peanut butter}), $$Include your answers to the following questions as comments in your code.

```
# QUESTION 4
# Fill out the table with the additional interaction term:
# (slices beef) | (tbsp peanut butter) | (slices beef)(tbsp peanut butter) | Rating |
# -----------------------------------------------------------------------------------
# 0 | 0 | _ | 1 |
# 1 | 0 | _ | 2 |
# 2 | 0 | _ | 4 |
# 4 | 0 | _ | 8 |
# 6 | 0 | _ | 9 |
# 0 | 2 | _ | 2 |
# 0 | 4 | _ | 5 |
# 0 | 6 | _ | 7 |
# 0 | 8 | _ | 6 |
# 2 | 2 | _ | 0 | (new data)
# 3 | 4 | _ | 0 | (new data)
# QUESTION 5
# What is the system of equations?
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# _ * beta_0 + _ * beta_1 + _ * beta_2 + _ * beta_3 = _
# QUESTION 6
# What is the matrix equation?
# [[_, _, _, _], [[_],
# [_, _, _, _], [_],
# [_, _, _, _], [_],
# [_, _, _, _], [[beta_0], [_],
# [_, _, _, _], [beta_1], = [_],
# [_, _, _, _], [beta_2], [_],
# [_, _, _, _], [beta_3]] [_],
# [_, _, _, _], [_],
# [_, _, _, _], [_],
# [_, _, _, _], [_],
# [_, _, _, _], [_],
# [_, _, _, _]] [_]]
# QUESTION 7
# What is the model?
# rating = ___ + ___ * (slices beef) + ___ * (tbsp peanut butter) + ___ * (slices beef)(tbsp peanut butter)
# QUESTION 8
# What is the predicted rating of a sandwich with 5 slices of roast beef AND
# 5 tablespoons of peanut butter (on the same sandwich)?
# ___
# QUESTION 9
# How does this prediction compare to that from the previous assignment? Did
# including interaction term make the prediction trustworthy? Why or why not?
# ___
```

(Stats; 60 min)

**Create a file assignment-problems/kl_divergence_for_monte_carlo_simulations.py to store your code/answers for this problem.**

The **Kullbackâ€“Leibler divergence** (or **relative entropy**) between two probability distributions $P(X)$ and $Q(X)$ is defined as

Intuitively, the divergence measures how "different" the two distributions are.

a) Write a function `kl_divergence(p, q)`

that computes the KL divergence between two probability distributions `p`

and `q`

, represented as arrays. Test your function by `assert`

ing that it passes the following test:

```
>>> p = [0.2, 0.7, 0.1]
>>> q = [0.1, 0.8, 0.1]
>>> kl_divergence(p,q)
0.04515746127
[ ^ computation for the above is 0.2*ln(0.2/0.1) + 0.7*ln(0.7/0.8) + 0.1*ln(0.1/0.1) ]
```

b) Compute the KL divergence where `p`

is the Monte Carlo distribution and `q`

is the true distribution for the number of heads in 5 coin tosses, using 1,000 samples in your Monte Carlo simulation (that's the default number from the previous assignment).

Then do the same computation with 100 samples, and then with 10,000 samples. Print out the results for all 3 computations:

```
>>> python assignment-problems/kl_divergence_for_monte_carlo_simulations.py
Testing KL Divergence... Passed!
Computing KL Divergence for MC Simulations...
100 samples --> KL Divergence = ___
1,000 samples --> KL Divergence = ___
10,000 samples --> KL Divergence = ___
```

In a comment in your code, write down what the general trend is and why:

`# As the number of samples increases, the KL divergence __________ because _______________________________.`

(Space Empires; 60 min)

Create a file `notes/game_events_using_combat_testing_players.txt`

and fill out the following template for what will happen during the movement and combat phases in the first turn when two `CombatTestingPlayers`

play each other on a 5-by-5 grid.

**Assume the dice rolls come out in perfect order: 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3...**

Note the following rules regarding attack order:

Fire combat is never simultaneous. Ships with an A Class fire before ships with a B Class, ships with a B Class fire before ships with a C, etc. If both players have groups with the same Class (for example, if both are Bâ€™s), the group belonging to the player with the higher Tactics Technology fires first.

If the Class and the Tactics Technology of both groups are the same, then the defender's group fires first.

(The defender is the group that was the first to occupy the space.)

**Note:** You don't have to implement your tests yet. We should first make sure we're all in agreement on what the outcome of the situation should be.

```
STARTING CONDITIONS
Players 1 and 2
are CombatTestingPlayers
start with 20 CPs
have an initial fleet of 3 scouts and 3 colony ships
---
TURN 1
MOVEMENT PHASE
Player 1, Movement 1
Scouts 1,2,3: (2,0) --> ___
Player 2, Movement 1
Scouts 1,2,3: (2,4) --> ___
Player 1, Movement 2
Scout 1,2,3: ___ --> ___
Player 2, Movement 2
Scouts 1,2,3: ___ --> ___
Players 1/2, Movement 3
___
Player 1, Final Locations:
Scout 1: ___
Scout 2: ___
Scout 3: ___
Player 2, Final Locations:
Scout 1: ___
Scout 2: ___
Scout 3: ___
COMBAT PHASE
Remaining ships: (list in the table below)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
---------------------------------------------------------
1 | _ | _ | _ |
2 | _ | _ | _ |
3 | _ | _ | _ |
...
Attack 1
Attacker: ___
Defender: ___
Hit Threshold: ___
Dice Roll: ___
Hit or Miss: ___ <-- label as "Hit" or "Miss"
Remaining ships: (in the table, only list the ships which remain alive)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
---------------------------------------------------------
1 | _ | _ | _ |
2 | _ | _ | _ |
3 | _ | _ | _ |
...
Attack 2
Attacker: ___
Defender: ___
Hit Threshold: ___
Dice Roll: ___
Hit or Miss: ___ <-- label as "Hit" or "Miss"
Remaining ships: (in the table, only list the ships which remain alive)
ATTACKING ORDER | PLAYER | SHIP | HEALTH |
---------------------------------------------------------
1 | _ | _ | _ |
2 | _ | _ | _ |
3 | _ | _ | _ |
...
... (continue until combat is complete)
```

(ML; 75 min)

**Create a file machine-learning/analysis/sandwich_ratings.py to store your code/answers for this problem.**

A food manufacturing company is testing out some recipes for roast beef sandwiches and peanut butter sandwiches. They fed sandwiches to several subjects, and the subjects rated the sandwiches.

```
Slices of Roast Beef | Tablespoons of Peanut Butter | Rating |
--------------------------------------------------------------
0 | 0 | 1 |
1 | 0 | 2 |
2 | 0 | 4 |
4 | 0 | 8 |
6 | 0 | 9 |
0 | 2 | 2 |
0 | 4 | 5 |
0 | 6 | 7 |
0 | 8 | 6 |
```

In this question, you will fit a plane (i.e. a linear model on 2 input variables) to the data using the following model:

$$ \text{rating} = \beta_0 + \beta_1 \times (\text{slices beef}) + \beta_2 \times (\text{tbsp peanut butter})$$a) As a comment in your code, fill in the system of $9$ linear equations that we seek to satisfy. (Each data point corresponds to a linear equation.)

```
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
# ___ * beta_0 + ___ * beta_1 + ___ * beta_2 = ___
```

b) As a comment in your code, fill in the corresponding matrix equation:

```
# [[___, ___, ___], [[___],
# [___, ___, ___], [___],
# [___, ___, ___], [___],
# [___, ___, ___], [[beta_0], [___],
# [___, ___, ___], [beta_1], = [___],
# [___, ___, ___], [beta_2]] [___],
# [___, ___, ___], [___],
# [___, ___, ___], [___],
# [___, ___, ___]] [___]]
```

Note: the comment above is meant to illustrate the following format:

\begin{align} \underbrace{\begin{bmatrix} \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \\ \_\_ & \_\_ & \_\_ \end{bmatrix}}_{X} \underbrace{\begin{bmatrix} \_\_ \\ \_\_ \\ \_\_ \end{bmatrix}}_{\vec{\beta}} &= \underbrace{\begin{bmatrix} \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \\ \_\_ \end{bmatrix}}_{\vec{y}} \end{align}

c) Use your `Matrix`

class to compute the least-squares approximation. **Do this computation in the file machine-learning/analysis/sandwich-ratings.py.**

As a comment in your code, fill in the blanks in the resulting model:

`# rating = ___ + ___ * (slices of beef) + ___ * (tbsp peanut butter)`

d) Use your model to predict the rating of a sandwich with $5$ slices of roast beef and no peanut butter. Your code should print out this value, and label that it corresponds to $5$ slices of roast beef and no peanut butter.

e) Predict the rating of a sandwich with $5$ slices of roast beef AND $5$ tablespoons of peanut butter (both ingredients on the same sandwich). Your code should print out this value, and label that it corresponds to $5$ slices of roast beef and $5$ tbsp peanut butter.

Should the company trust this prediction? Why or why not? Write your answer as a comment in your code.

`# ____, because __________________________________________________________`

(Space Empires; 90 min)

Create the following classes:

Create a class

`CombatTestingPlayer`

that uses the following strategy:- before buying any ships, buy ship size technology 2
- alternate between buying
`Destroyers`

and`Scouts`

, starting off buying a`Destroyer`

. If it can't pay for the next ship, then just wait until the next turn to buy it. - always move ships towards the center of the board, and have the ships stop there
- during combat, don't screen any ships, and always attack the opposing ship that is highest in the attacking order.

Create a class

`CombatEngine`

that handles all of the combat functionality, and refactor your`Game`

so that whenever it enters combat phase, it gathers the units that occupy the same grid space and passes them into`CombatEngine`

for processing:

```
Game asks Board what ships are on the same grid space
Game passes ships into CombatEngine
CombatEngine asks Players what ships they want to screen
CombatEngine figures out the attacking order
while combat is occurring:
for each Unit in the attacking order:
CombatEngine asks the unit's Player what other unit they want to attack
CombatEngine executes the attack by rolling the dice and logging any hit as appropriate
Game proceeds onwards to economic phase
```

**Make sure that when two CombatPlayers play against each other, there are many battles taking place at the center of the board.**

**Also, make sure that your CombatEngine is implemented well. I DON'T want to see anything ridiculous like CombatEngine inheriting from Game or Board, or implementing any sort of strategy on its own. The Player is the only thing that should be implementing strategy.**

Next time, we'll figure out how to test `CombatEngine`

to ensure that the combat is progressing correctly. But this time, just focus on pulling out the `Game`

's combat methods and moving it into `CombatEngine`

.

(Stats; 30 min)

a) Using your function `probability(num_heads, num_flips)`

, plot the distribution for the number of heads in `10`

coin flips. In other words, plot the curve $y=p(x),$ where $p(x)$ is the probability of getting $x$ heads in $10$ coin flips.

b) Make **5** more plots, each using your function `monte_carlo_probability(num_heads, num_flips)`

.

c) Put all your plots on the same graph, label them with a legend to indicate whether each plot is the true distribution or a monte carlo simulation, and save the figure as `plot.png`

.

Legend: True, MC 1, MC 2, MC 3, MC 4, MC 5.

Make the true distribution thick (`linewidth=2.5`

) and the monte carlo distributions thin (`linewidth=0.75`

). A plotting example is shown below to assist you.

In [ ]:

```
import matplotlib.pyplot as plt
plt.style.use('bmh')
plt.plot([0,1,2,3,4],[0.1, 0.3, 0.5, 0.1, 0.1],linewidth=2.5)
plt.plot([0,1,2,3,4],[0.3, 0.1, 0.4, 0.2, 0.1],linewidth=0.75)
plt.plot([0,1,2,3,4],[0.2, 0.2, 0.3, 0.3, 0.2],linewidth=0.75)
plt.legend(['True','MC 1','MC 2'])
plt.xlabel('Number of Heads')
plt.ylabel('Probability')
plt.title('True Distribution vs Monte Carlo Simulations for 10 Coin Flips')
plt.savefig('plot.png')
```

(Algo; 90 min)

**Problem Context**

Suppose that a railroad network has a list of all of its segments between two towns. For example, if

`railroad_segments = [('B','C'), ('B','A'), ('A','D'), ('E','D'), ('C','F'), ('G','C')]`

then the towns could be arranged as

```
A -- B -- C -- F
\ \
D -- E G
```

Assume that

- segments can be traveled either way, i.e. ('B','C') means you can go from 'B' to 'C' or you can go from 'C' to 'B',
- each railroad segment corresponds to the same travel time, and that
- the railroad segments never form a loop (in other words, to get from any town to another, there is only one possible path that does not backtrack on itself).

**Problem Statement**

Write a function `order_towns_by_travel_time(starting_town, railroad_segments)`

that lists the towns in order of travel time from the `starting_town`

. Implement this function using two different techniques, both of which we went over during class:

`order_towns_by_travel_time_using_tree_class(starting_town, railroad_segments)`

: modify the`railroad_segments`

edge list so that you can pass it into your`Tree`

class and call the`breadth_first_traversal()`

method.`order_towns_by_travel_time_from_scratch(starting_town, railroad_segments)`

: implement breadth first search from scratch, so that it uses the`railroad_segments`

edge list as-is.

**Where to Store / Test the Code**

Create a repository

`graph`

.Put your

`Tree`

class in`graph/src/tree.py`

.Implement the functions

`order_towns_by_travel_time_using_tree_class`

and`order_towns_by_travel_time_from_scratch`

in a file`graph/analysis/railroad_travel_time.py`

.Create a testing file

`graph/analysis/test_railroad_travel_time.py`

, and**ASSERT THAT BOTH OF YOUR FUNCTIONS PASS THE FOLLOWING TESTS:**

```
>>> railroad_segments = [('B','C'), ('B','A'), ('A','D'), ('E','D'), ('C','F'), ('G','C')]
>>> order_towns_by_travel_time('D', railroad_segments)
can return either of two possible answers:
[D, E, A, B, C, F, G]
[D, A, E, B, C, F, G]
[D, E, A, B, C, G, F]
[D, A, E, B, C, G, F]
>>> order_towns_by_travel_time('A', railroad_segments)
can return either of eight possible answers:
[A, D, B, C, E, F, G]
[A, B, D, C, E, F, G]
[A, D, B, E, C, F, G]
[A, B, D, E, C, F, G]
[A, D, B, C, E, G, F]
[A, B, D, C, E, G, F]
[A, D, B, E, C, G, F]
[A, B, D, E, C, G, F]
```

(SWE; 0-90 min)

Resolve **ALL the remaning issues** on your refactoring list. This is the third assignment on which significant time was devoted to refactoring, so I'm expecting you to have **100% of the issues resolved** before the next class. Next to your name, it should say "0 issues remaining".

(Stats; 60 min)

In this problem, you will compute the probability of getting `num_heads`

heads in `num_flips`

flips of a fair coin. You will do this using two different methods. You should write your functions in a file `assignment-problems/coin_flipping.py`

a) Write a function `probability(num_heads, num_flips)`

that uses mathematics to compute the probability.

First, compute the total number of possible outcomes for

`num_flips`

flips. (Hint: it's an exponent.)Then, compute the number of outcomes in which

`num_heads`

heads arise in`num_flips`

flips. (Hint: it's a combination.)Then, divide the results.

b) Write a function `monte_carlo_probability(num_heads, num_flips)`

that uses simulation to compute the probability.

First, simulate 1000 trials of

`num_flips`

coin flips, keeping track of how many heads there were.Then, divide the number of outcomes in which there were

`num_heads`

heads, by the total number of trials (1000).

c) When you run `assignment-problems/coin_flipping.py`

, you should print out the result of `probability(5,8)`

. Also, print out 3 instances of `monte_carlo_probability(5,8)`

.

- The 3 instances will be slightly different because it's a random simulation, but they should be fairly close to each other and to the true result.

(SWE; 120 min)

a) Resolve the remaining issues on your refactoring list.

b) In `tests/test_matrix.py`

, test that the inverse is correctly computed for the following matrices. To do this, you should compute the inverse, multiply the matrix by its inverse, and then check that the result (when rounded to 6 decimal places) is equal to the identity matrix.

```
A = [[1, 2, 3, 4],
[5, 0, 6, 0],
[0, 7, 0, 8],
[9, 0, 0, 10]]
assert round_down(A @ A.inverse()) == identity_matrix
B = [[1.2, 5.3, 8.9, -10.3, -15],
[3.14, 0, -6.28, 0, 2.71],
[0, 1, 1, 2, 3],
[5, 8, 13, 21, 34],
[1, 0, 0.5, 0, 0.1]]
assert round_down(B @ B.inverse()) == identity_matrix
```

(ML; 30 min)

**For this problem, make a file machine-learning/analysis/rocket_takeoff_regression.py and put your code there.**

Recall the following dataset, which represents the distance between a rocket and Earth's surface, as the rocket takes off. The data points are given in the form `(time, distance)`

.

`data = [(1, 3.1), (2, 10.17), (3, 20.93), (4, 38.71), (5, 60.91), (6, 98.87), (7, 113.92), (8, 146.95), (9, 190.09), (10, 232.65)]`

a) Using your `PolynomialRegression`

class, fit a quadratic to the data:

According to the quadratic, what is the predicted position of the rocket after 200 seconds? **Make rocket_takeoff_regression.py print out your answer.**

b) Your friend claims that a cubic model will better fit the data. So, using your `PolynomialRegression`

class, fit a cubic to the data:

According to the cubic, what is the predicted position of the rocket after 200 seconds? **Make rocket_takeoff_regression.py print out your answer.**

c) Which model is better, the quadratic or the cubic? Justify your answer. **Write your answer as a comment in rocket_takeoff_regression.py**

(SWE; 180 min)

**Catch up:** Make sure your tests for `machine-learning/test/test_matrix.py`

and `space-empires/src/test_dumb_player.py`

are working and complete.

- Make sure that your
`DumbPlayer`

test is using assert statements to check the relevant aspects of the game. You should NOT just print out the logging data and compare it visually. Rather, for each test, you should print out what you're testing for and whether the test passed.

**Naming conventions:**

Make sure all your files are named properly, using snake_case and correct grammar.

Make sure all your classes are named as nouns and all your methods/functions are named as verbs. This includes past files as well.

**Refactoring:** Resolve all the high-priority issues on your refactoring list.

**NOTE: There's really not much else on this assignment, so I'm expecting you to get all of the above done over the weekend. If you run into any prolonged trouble, please make a post on Discord! If you find yourself not making progress on an issue for 30 min or more, just make a post for help and move onto another thing.**

(DS/Algo; 60 min)

Create a testing file `tests/test_matrix.py`

that tests your matrix methods

1 test for each arithmetic operation: addition, subtraction, scalar multiplication, matrix multiplication, transpose.

6 tests for reduced row echelon form. You should test all combinations of the following cases:

- a a square matrix, a tall rectangular matrix, and a wide rectangular matrix;
- has the maximum number of possible pivots (i.e. no pivot disappears); has fewer than the maximum number of pivots (i.e. some pivot disappears)

3 tests for each of inverse, inverse by minors, determinant, and recursive determinant (so, 12 tests in all).

- the case when the matrix is invertible
- the case when the matrix is not invertible due to having dependent rows
- the case when the matrix is not invertible due to not being square

(DS/Algo; 45 min)

Write a recursive function `divide_and_conquer_sort(x)`

that sorts an input list `x`

according to the following technique:

If the input list consist of more than one element, then split the list into the first half and the second half, recursively use

`divide_and_conquer_sort`

to sort each half, combine the two sorted halves, and return the result. Otherwise, if the input list consists of only one element, then the input list is already sorted and you can return it.

**Put your function in assignment-problems and create a testing file that implements 4 tests, each of which are significantly different in some way.**

**HERE IS SOME PSEUDOCODE TO HELP YOU STRUCTURE YOUR FUNCTION:**

```
divide_and_conquer_sort(input list):
if the input list consists of more than one element:
break up the input list into its left and right halves
sort the left and right halves by recursively calling divide_and_conquer_sort
combine the two sorted halves
return the result
otherwise, if the input list consists of only one element, then it is already sorted,
and you can just return it.
```

**And here is an example of what's going on under the hood:**

```
input list:[6,9,7,4,2,1,8,5]
break it in half: [6,9,7,4] [2,1,8,5]
use divide_and_conquer_sort recursively to sort the two halves
input list: [6,9,7,4]
break it in half: [6,9] [7,4]
use divide_and_conquer_sort recursively to sort the two halves
input list: [6,9]
break it in half: [6] [9]
the two halves have only one element each, so they are already sorted
so we can combine them to get [6,9]
input list: [7,4]
break it in half: [7] [4]
the two halves have only one element each, so they are already sorted
so we can combine them to get [4,7]
now we have two sorted lists [6,9] and [4,7]
so we can combine them to get [4,6,7,9]
input list: [2,1,8,5]
break it in half: [2,1] [8,5]
use divide_and_conquer_sort recursively to sort the two halves
input list: [2,1]
break it in half: [2] [1]
the two halves have only one element each, so they are already sorted
so we can combine them to get [1,2]
input list: [8,5]
break it in half: [8] [5]
the two halves have only one element each, so they are already sorted
so we can combine them to get [5,8]
now we have two sorted lists [1,2] and [5,8]
so we can combine them to get [1,2,5,8]
now we have two sorted lists [4,6,7,9] and [1,2,5,8]
so we can combine them to get [1,2,4,5,6,7,8,9]
```

(SWE; 90 min)

Write a testing file `tests/test_dumb_player.py`

to ensure that a game on a $5 \times 5$ grid with two `DumbPlayer`

s proceeds correctly.

**Over the course of 4 turns, you should check the board for the following 8 tests:**

At the end of Turn 1 Movement Phase:

- Player 1 has 3 scouts at (4,0)
- Player 2 has 3 scouts at (4,4)

At the end of Turn 1 Economic Phase:

- Player 1 has 3 scouts at (4,0) and 3 scouts at (2,0)
- Player 2 has 3 scouts at (4,4) and 3 scouts at (2,4)
- Players 1/2 have 2 CPs each

At the end of Turn 2 Movement Phase:

- Player 1 has 6 scouts at (4,0)
- Player 2 has 6 scouts at (4,4)

At the end of Turn 2 Economic Phase:

- Player 1 has 5 scouts at (4,0)
- Player 2 has 5 scouts at (4,4)
- Players 1/2 have 0 CPs each

At the end of Turn 3 Movement Phase:

- Player 1 has 5 scouts at (4,0)
- Player 2 has 5 scouts at (4,4)

At the end of Turn 3 Economic Phase:

- Player 1 has 3 scouts at (4,0)
- Player 2 has 3 scouts at (4,4)
- Players 1/2 have 0 CPs each

At the end of Turn 4 Movement Phase:

- Player 1 has 3 scouts at (4,0)
- Player 2 has 3 scouts at (4,4)

At the end of Turn 4 Economic Phase:

- Player 1 has 3 scouts at (4,0)
- Player 2 has 3 scouts at (4,4)
- Players 1/2 have 0 CPs each

For your reference, here's my scratch work when figuring out the conditions above.

```
STARTING CONDITIONS
Players 1 and 2
are DumbPlayers
start with 20 CPs
have an initial fleet of 3 scouts and 3 colony ships
---
TURN 1
MOVEMENT PHASE
Player 1, Movement 1
Scouts 1,2,3: (2,0) --> (3,0)
Player 2, Movement 1
Scouts 1,2,3: (2,4) --> (3,4)
Player 1, Movement 2
Scout 1,2,3: (3,0) --> (4,0)
Player 2, Movement 2
Scouts 1,2,3: (3,4) --> (4,4)
Players 1/2, Movement 3
no movements occur
Player 1, Final Locations:
Scout 1: (4,0)
Scout 2: (4,0)
Scout 3: (4,0)
Player 2, Final Locations:
Scout 1: (4,4)
Scout 2: (4,4)
Scout 3: (4,4)
COMBAT PHASE
no combats occur
ECONOMIC PHASE
Players 1/2
starting CP: 20
colony income: 3 CP/Colony x 1 Colony = 3 CP
maintenance costs: 1 CP/Scout x 3 Scouts = 3 CP
remaining CP: 20
buy scouts: 6 CP/Scout x 3 Scouts = 18 CP
remaining CP: 2
---
TURN 2
MOVEMENT PHASE
Player 1, Movement 1
Scouts 4,5,6: (2,0) --> (3,0)
Player 2, Movement 1
Scouts 4,5,6: (2,4) --> (3,4)
Player 1, Movement 2
Scout 4,5,6: (3,0) --> (4,0)
Player 2, Movement 2
Scouts 4,5,6: (3,4) --> (4,4)
Players 1/2, Movement 3
no movements occur
Player 1, Final Locations:
Scout 1: (4,0)
Scout 2: (4,0)
Scout 3: (4,0)
Scout 4: (4,0)
Scout 5: (4,0)
Scout 6: (4,0)
Player 2, Final Locations:
Scout 1: (4,4)
Scout 2: (4,4)
Scout 3: (4,4)
Scout 4: (4,4)
Scout 5: (4,4)
Scout 6: (4,4)
COMBAT PHASE
no combats occur
ECONOMIC PHASE
Players 1/2
starting CP: 2
colony income: 3 CP/Colony x 1 Colony = 3 CP
maintenance costs: 1 CP/Scout x 6 Scouts = 6 CP
unable to maintain Scout 6; Scout 6 is removed
remaining CP: 0
---
TURN 3
MOVEMENT PHASE
Players 1/2, Movements 1/2/3
no movements occur
Player 1, Final Locations:
Scout 1: (4,0)
Scout 2: (4,0)
Scout 3: (4,0)
Scout 4: (4,0)
Scout 5: (4,0)
Player 2, Final Locations:
Scout 1: (4,4)
Scout 2: (4,4)
Scout 3: (4,4)
Scout 4: (4,4)
Scout 5: (4,4)
COMBAT PHASE
no combats occur
ECONOMIC PHASE
Players 1/2
starting CP: 0
colony income: 3 CP/Colony x 1 Colony = 3 CP
maintenance costs: 1 CP/Scout x 5 Scouts = 5 CP
unable to maintain Scouts 4/5; Scouts 4/5 are removed
remaining CP: 0
---
TURN 3
MOVEMENT PHASE
Players 1/2, Movements 1/2/3
no movements occur
Player 1, Final Locations:
Scout 1: (4,0)
Scout 2: (4,0)
Scout 3: (4,0)
Player 2, Final Locations:
Scout 1: (4,4)
Scout 2: (4,4)
Scout 3: (4,4)
COMBAT PHASE
no combats occur
ECONOMIC PHASE
Players 1/2
starting CP: 0
colony income: 3 CP/Colony x 1 Colony = 3 CP
maintenance costs: 3 CP/Scout x 3 Scouts = 3 CP
remaining CP: 0
---
all future turns continue the same way as TURN 3
```

(ML; 30 min)

Create a file `tests/test_polynomial_regressor.py`

to test your `PolynomialRegressor`

on the following tests. **(Round the comparisons to 6 decimal places.)**

```
from polynomial_regressor import PolynomialRegressor
data = [(0,1), (1,2), (2,5), (3,10), (4,20), (5,30)]
constant_regressor = PolynomialRegressor(degree=0)
constant_regressor.ingest_data(data)
constant_regressor.solve_coefficients()
constant_regressor.coefficients
[11.333333333333332]
constant_regressor.evaluate(2)
11.333333333333332
linear_regressor = PolynomialRegressor(degree=1)
linear_regressor.ingest_data(data)
linear_regressor.solve_coefficients()
linear_regressor.coefficients
[-3.2380952380952412, 5.828571428571428]
linear_regressor.evaluate(2)
8.419047619047616
quadratic_regressor = PolynomialRegressor(degree=2)
quadratic_regressor.ingest_data(data)
quadratic_regressor.solve_coefficients()
quadratic_regressor.coefficients
[1.107142857142763, -0.6892857142856474, 1.3035714285714226]
quadratic_regressor.evaluate(2)
4.942857142857159
cubic_regressor = PolynomialRegressor(degree=3)
cubic_regressor.ingest_data(data)
cubic_regressor.solve_coefficients()
cubic_regressor.coefficients
[1.1349206349217873, -0.8161375661377197, 1.3730158730155861, -0.009259259259233155]
cubic_regressor.evaluate(2)
4.920634920634827
fifth_degree_regressor = PolynomialRegressor(degree=5)
fifth_degree_regressor.ingest_data(data)
fifth_degree_regressor.solve_coefficients()
fifth_degree_regressor.coefficients
[0.9999999917480108, -2.950000002085698, 6.9583333345161265, -3.9583333337779045, 1.0416666667658463, -0.09166666667401097]
fifth_degree_regressor.evaluate(2)
4.999999990103076
```

(DS/Algo; 30 min)

a) Make a new repository `assignment-problems`

. Going forward, this repository will hold any miscellaneous functions you write in assignments.

b) Write a function `combine_sorted_lists(x,y)`

that combines two sorted lists `x`

and `y`

so that the result itself is also sorted. You should build up the output list by going through `x`

and `y`

in parallel, and repeatedly taking the smallest value.

**IMPORTANT CLARIFICATION: You should not be mutating the underlying lists.**During the example in class, we removed items from`x`

and`y`

and put them in a new list, but you shouldn't actually remove anything from`x`

and`y`

. Rather, you should just loop through each list in parallel, keeping track of your indices in`x`

and`y`

, and repeatedly bring a copy of the smallest element into the output list.

```
>>> combine_sorted_lists([1,3,4,5,7],[2,6])
[1,2,3,4,5,6,7]
```

c) Put your function in a file `combine_sorted_lists.py`

. **Then, create a file test_combine_sorted_lists.py that runs $4$ tests on the function you wrote.**

- Be sure to consider a variety of test cases. In particular, make sure your code works on edge-cases, such as when list items are repeated.

(SWE; 90 min)

a) Create a new class `RandomPlayer`

that inherits from `Player`

. Then, take any methods in `Player`

for which random strategy is currently used, and move them to `RandomPlayer`

.

- Such methods include
`move`

,`build_fleet`

, etc.

b) Create another class `DumbPlayer`

that has the same format as `RandomPlayer`

, but that uses the following strategy:

Only spend money on scouts. Always build as many scouts as possible, and don't ever buy anything else (not even technology).

Always move ships to the right.

c) Put the player class files in a folder `player/`

that is analogous to the `unit/`

folder. So, you should have

```
src/
|- player/
. |- player.py
. |- random_player.py
. |- dumb_player.py
```

d) Check to see what happens when two `DumbPlayer`

s play the game. You should have a bunch of scouts collect on the right.

e) Check to see what happens when a `RandomPlayer`

plays against a `DumbPlayer`

.

(Journal Club; 30 min)

Watch this video on AlphaStar, and think about the following questions. We'll discuss them in class next time, and I'm going to expect everyone to have a thought-out response to each of these questions! (Feel free to watch at higher speed, if you're able to process the information to answer the questions below.)

What is deep learning, what is reinforcement learning, and how does AlphaStar integrate them?

What are main agents and exploiter agents? How are they different, and why are exploiter agents used?

How did AlphaStar perform? Was it better than half of the human players? Better than 9 out of 10 human players? Better than that?

Update your file names to be snake case (here's an explanation of why). Also, don't use abbreviations. Write the whole name.

So, you should have:

```
machine-learning/
|- src/
. |- matrix.py
. |- polynomial_regressor.py
. |- gradient_descent.py
|- tests/
. |- test_gradient_descent.py
```

```
space-empires/
|- src/
. |- game.py
. |- player.py
. |- unit/
. |- unit.py
. |- scout.py
. |- battleship.py
. |- and so on...
```

(DS/Algo; 60 min)

Write a function `cartesian_product(arrays)`

that computes the Cartesian product of all the lists in `arrays`

.

```
>>> cartesian_product([['a'], [1,2,3], ['Y','Z']])
[['a',1,'Y'], ['a',1,'Z'], ['a',2,'Y'], ['a',2,'Z'], ['a',3,'Y'], ['a',3,'Z']]
```

**NOTE: This is a reasonably short function if you use the following procedure. You'll probably have to think a bit in order to get the implementation correct, though.**

Create a variable

`points`

that will be a list of all the points in the cartesian product. Initially, set`points`

to consist of a single empty point:`points = [[]]`

.For each array in the input, create a new list of points.

The new set of points can be constructed by looping through each existing point and, for each existing point, adding several new points.

- For a given point, the new points can be constructed by appending each element of the array onto a copy of the given point.

Return the list of points.

**Worked Example:**

```
arrays = [['a'], [1,2,3], ['Y','Z']]
points: [[]]
considering array ['a']
considering element 'a'
new point ['a']
points: [['a']]
considering array [1,2,3]
considering element 1
new point ['a',1]
considering element 2
new point ['a',2]
considering element 3
new point ['a',3]
points: [['a',1], ['a',2], ['a',3]]
considering array ['Y','Z']
considering element 'Y'
new points ['a',1,'Y'], ['a',2,'Y'], ['a',3,'Y']
considering element 'Z'
new points ['a',1,'Z'], ['a',2,'Z'], ['a',3,'Z']
points: [[1,'a','Y'], [1,'a','Z'], [1,'b','Y'], [1,'b','Z'], [1,'c','Y'], [1,'c','Z']]
```

(ML; 60 min)

a) In `GradientDescent`

, clean up `tests/test_gradient_descent.py`

.

For each comparison of floating-point decimals,

**round to 10 decimal places**before you check for equality.The only things you should print are the name of each test, and if the test fails, then your custom error message. You can use the format below, or come up with your own format provided that it meets the specifications in the previous sentence.

```
>>> python tests/test_gradient_descent.py
Testing...
compute_gradient
single_variable_function
two_variable_function
three_variable_function
six_variable_function
descend
single_variable_function
two_variable_function
AssertionError: incorrect output for descend on three_variable_function
OUTPUT: [3.0020000000000000018, 2.0030001000000000055, 1.004000400000000004]
DESIRED: [0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004]
```

b) In `GradientDescent`

, generalize your `grid_search`

to work on objective functions of any number of variables.

**HINT: You wrote a**`cartesian_product`

function in Problem 1, so use it here as a helper function! Just loop over the cartesian product of the input arrays.*Note: For now, don't worry about applying gradient descent within the grid search. Just find the grid point with the lowest value of the function.*

**Lastly, use assert statements to write the following additional tests for your GradientDescent class, and make sure all your tests pass.** Put these additional tests in

`tests/test_gradient_descent.py`

.```
>>> def single_variable_function(x):
return (x-1)**2
>>> def two_variable_function(x, y):
return (x-1)**2 + (y-1)**3
>>> def three_variable_function(x, y, z):
return (x-1)**2 + (y-1)**3 + (z-1)**4
>>> def six_variable_function(x1, x2, x3, x4, x5, x6):
return (x1-1)**2 + (x2-1)**3 + (x3-1)**4 + x4 + 2*x5 + 3*x6
>>> minimizer = GradientDescent(single_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75]])
>>> minimizer.minimum
[0.75]
>>> minimizer = GradientDescent(two_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75], [0.9, 1, 1.1]])
>>> minimizer.minimum
[0.75, 0.9]
>>> minimizer = GradientDescent(three_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75], [0.9, 1, 1.1], [0, 1, 2, 3]])
>>> minimizer.minimum
[0.75, 0.9, 1]
>>> minimizer = GradientDescent(six_variable_function)
>>> minimizer.grid_search([[0, 0.25, 0.75], [0.9, 1, 1.1], [0, 1, 2, 3],
[-2, -1, 0, 1, 2], [-2, -1, 0, 1, 2], [-2, -1, 0, 1, 2]])
>>> minimizer.minimum
[0.75, 0.9, 1, -2, -2, -2]
```

(SWE; 30 min)

If you haven't already, create a class `Board`

that stores the coordinates of all the units.

During combat, the

`Game`

should check the`Board`

to identify which units occupy the same spot.The

`Game`

should not store its dimensions as an attribute. Rather, it should store a reference to the`Board`

, and the`Board`

should store its dimensions as an attribute.- For example, you should never have
`Game.dimensions`

. Rather, you would have`Game.board.dimensions`

.

- For example, you should never have

(ML; 30-90 min)

Notice that we can test code and print out custom error messages using `assert`

statements:

In [ ]:

```
should_be_zero = 42
assert should_be_zero == 0, 'should_be_zero is NOT zero'
```

In [ ]:

```
should_be_one = 1
assert should_be_one == 1, 'should_be_one is NOT one'
```

In [ ]:

```
def add_numbers(x,y):
return x - y
# let's test the function above to see if it works right
test_function = add_numbers
tests = [
{'args':(0, 0), 'output': 0}, # will pass
{'args':(1, 0), 'output': 1}, # will pass
{'args':(0, 1), 'output': 1}, # will not pass; output will be -1
{'args':(1, 1), 'output': 2}
]
for test in tests:
actual_output = test_function(*test['args'])
desired_output = test['output']
error_message = 'incorrect output for {}'.format(
test_function.__name__
)
details = '\nINPUT: {}\nOUTPUT: {}\nDESIRED: {}'.format(
test['args'], actual_output, desired_output
)
assert actual_output == desired_output, error_message + details
```

**Extend your machine-learning library to include the following 8 tests for GradientDescent.py.** For each function, test that

`GradientDescent`

computes the correct gradient, and that the minimum is correct after descending once along the gradient.```
>>> def single_variable_function(x):
return (x-1)**2
>>> def two_variable_function(x, y):
return (x-1)**2 + (y-1)**3
>>> def three_variable_function(x, y, z):
return (x-1)**2 + (y-1)**3 + (z-1)**4
>>> def six_variable_function(x1, x2, x3, x4, x5, x6):
return (x1-1)**2 + (x2-1)**3 + (x3-1)**4 + x4 + 2*x5 + 3*x6
>>> minimizer = GradientDescent(single_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
[0.0020000000000000018]
>>> minimizer = GradientDescent(two_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
[0.0020000000000000018, -0.0030001000000000055]
>>> minimizer = GradientDescent(three_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
[0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004]
>>> minimizer = GradientDescent(six_variable_function)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035, 1.0000000000000009, 2.0000000000000018, 3.0000000000000027]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1)
>>> minimizer.minimum
(0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004, -0.0010000000000000009, -0.0020000000000000018, -0.0030000000000000027)
```

You should be able to execute the tests by running `tests/test_GradientDescent.py`

. **MAKE SURE THAT ALL YOUR TESTS PASS, and make sure to push your finished code to Github for safekeeping.**

```
machine-learning/
|- src/
. |- Matrix.py
. |- PolynomialRegressor.py
. |- GradientDescent.py
|- tests/
. |- test_GradientDescent.py
```

(SWE; 60 min)

Refactor your `space-empires`

library so that each movement phase consists of three movements. (No combat occurs during movement phase.)

- Replace
`Speed Technology`

with`Movement Technology`

, under the following settings:

```
Movement Technology Level | Additional CP Cost | Benefit
---------------------------------------------------------
1 | at start | Can move one space per movement
2 | 20 | Can move 1 space in each of the first 2 movements and 2 spaces in the third movement
3 | 30 | Can move 1 space in the first movement and 2 spaces in each of the second and third movements
4 | 40 | Can move 2 spaces per movement
5 | 40 | Can move 2 spaces in each of the first 2 movements and 3 spaces in the third movement
6 | 40 | Can move 2 spaces in the first movement and 3 spaces in each of the second and third movements
```

- Note: if you had previously "normalized" the maintenance costs by dividing by 3, then remove that.

Note the following answers to some Space Empires questions that were asked recently:

There are no maintenance costs for Colony Ships, Bases

If the colony is destroyed are the shipyards on it destroyed too? Yes.

You cannot place multiple colonies on the same planet.

**If you haven't already, put indents and blank lines in your game logging so that it's easier to read.** Example:

```
-------------------------------------------------
TURN 12 - MOVEMENT PHASE
Player 1 - Move 1
Unit 1 (Scout) moves from (1,2) to (2,2)
Unit 1 (Battleship) moves from (3,2) to (4,2)
Player 2 - Move 1
Unit 1 (Scout) moves from (3,4) to (2,4)
Player 1 - Move 2
Unit 1 (Scout) moves from (2,2) to (3,2)
Unit 1 (Battleship) moves from (4,2) to (4,1)
Player 2 - Move 2
Unit 1 (Scout) moves from (2,4) to (1,4)
...
-------------------------------------------------
```

**Make sure to push your finished code to Github for safekeeping.**

(30 min)

- Create a Github account and create a repository
`machine-learning`

. - Create a repl.it account and import the repository into a new repl.
- Create a folder
`src`

and paste your classes into files:`Matrix`

into`Matrix.py`

`PolynomialRegressor`

into`PolynomialRegressor.py`

`GradientDescent`

into`GradientDescent.py`

Commit and push the repository to your Github. The repository should have the following structure:

`machine-learning/ |- src/ . |- Matrix.py . |- PolynomialRegressor.py . |- GradientDescent.py`

Create another Github repository

`space-empires`

and paste each class into its own file within a folder`src`

. This repository should have the following structure:`space-empires/ |- src/ . |- Game.py . |- Player.py . |- Unit/ . |- Unit.py . |- Scout.py . |- Battleship.py . |- and so on...`

(ML; 60 min)

Make sure that your `GradientDescent`

class works with functions of any number of arguments.

Tip: if you have a function`f(x,y,z)`

and a list`args = [0,5,3]`

, then you can pass`f(*args)`

to evaluate`f(0,5,3)`

.Here's Riley's method for detecting the number of arguments to a function

`f`

:`self.num_vars = len(inspect.getfullargspec(f).args)`

Likewise, here's Elijah's method:

`self.num_vars = f.__code__.co_argcount`

Here is how to clone your `machine-learning`

repository and import your `GradientDescent`

:

```
>>> !git clone https://github.com/yourUserName/machine-learning.git
>>> import sys
>>> sys.path.append("/content/machine-learning/src/")
>>> from GradientDescent import GradientDescent
```

Here are some tests:

```
>>> def single_variable_function(x):
return (x-1)**2
>>> def two_variable_function(x, y):
return (x-1)**2 + (y-1)**3
>>> def three_variable_function(x, y, z):
return (x-1)**2 + (y-1)**3 + (z-1)**4
>>> def six_variable_function(x1, x2, x3, x4, x5, x6):
return (x1-1)**2 + (x2-1)**3 + (x3-1)**4 + x4 + 2*x5 + 3*x6
>>> minimizer = GradientDescent(single_variable_function)
>>> minimizer.minimum
(0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018)
>>> minimizer = GradientDescent(two_variable_function)
>>> minimizer.minimum
(0, 0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018, -0.0030001000000000055)
>>> minimizer = GradientDescent(three_variable_function)
>>> minimizer.minimum
(0, 0, 0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004)
>>> minimizer = GradientDescent(six_variable_function)
>>> minimizer.minimum
(0, 0, 0, 0, 0, 0)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 3.0001000000000055, -4.0004000000000035, 1.0000000000000009, 2.0000000000000018, 3.0000000000000027]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=1, logging=True)
(0.0020000000000000018, -0.0030001000000000055, 0.004000400000000004, -0.0010000000000000009, -0.0020000000000000018, -0.0030000000000000027)
```

(SWE; 60 min)

On repl.it, refactor your game so that each turn consists of three phases: movement, combat, economic.

- During the "movement" phase, all players move their ships.
- During the "combat" phase, all ships that occupy the same grid space engage in combat.
- During the "economic" phase, all players receive income and buy ships / technologies.

You should have a separate method for each of these phases:

`Game.complete_movement_phase`

`Game.complete_combat_phase`

`Game.complete_economic_phase`

Then, push your new changes to your `space-empires`

repository, clone it here, and run your game to show the output below.

(ML; 90 min)

a) Write a class `GradientDescent`

which organizes your gradient descent and grid search functionality. Your output should match the tests below **exactly.**

```
>>> def f(x,y):
return 1 + (x-1)**2 + (y+5)**2
>>> minimizer = GradientDescent(f)
>>> minimizer.minimum
(0, 0) # this is the default guess
>>> minimizer.grid_search([-4,-2,0,-2,4],[-4,-2,0,-2,4])
# evaluates the function on all parameter combinations and updates the minimum accordingly
>>> minimizer.minimum
(0, -4)
>>> minimizer.compute_gradient(delta=0.01)
[-2.0000000000000018, 1.9999999999999574]
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=4, logging=True)
(0.0020000000000000018, -4.002)
(0.0039959999999999996, -4.003996)
(0.005988007999999989, -4.005988008)
(0.007976031983999987, -4.007976031984)
>>> minimizer.minimum
(0.007976031983999987, -4.007976031984)
```

b) Make sure the test below works, using your `GradientDescent`

class above. Your output should match the tests below **exactly.**

```
>>> data = [(0,1), (1,2), (2,4), (3,10)]
>>> def sum_squared_error(beta_0, beta_1, beta_2):
squared_errors = []
for (x,y) in data:
estimation = beta_0 + beta_1*x + beta_2*(x**2)
error = estimation - y
squared_errors.append(error**2)
return sum(squared_errors)
>>> minimizer = GradientDescent(sum_squared_error)
>>> minimizer.descend(scaling_factor=0.001, delta=0.01, num_steps=100, logging=True)
(0.03399999999999892, 0.0799999999999983, 0.21599999999999966)
(0.06071999999999847, 0.1417999999999985, 0.3829519999999995)
(0.08180998399999845, 0.18952841599999815, 0.5119836479999996)
(0.09854562099199829, 0.22637707788799802, 0.6116981274880002)
(0.11191318351974236, 0.2548137070760939, 0.6887468675046403)
...
(0.3047314235908722, 0.32259730399636893, 0.9402940523204946)
>>> mimimizer.minimum
(0.3047314235908722, 0.32259730399636893, 0.9402940523204946)
>>> sum_squared_error(minimizer.minimum)
1.246149882168838
```

c) Write a class `PolynomialRegressor`

which organizes your polynomial regression functionality. Your output should match the tests below **exactly.**

```
>>> quadratic_regressor = PolynomialRegressor(degree=2)
>>> quadratic_regressor.coefficients
[0, 0, 0] # default coefficients --> model is 0 + 0x + 0x^2
>>> quadratic_regressor.evaluate(5)
0 # because it's 0 + 0*5 + 0*5^2
>>> data = [(0,1), (1,2), (2,4), (3,10)]
>>> quadratic_regressor.ingest_data(data)
>>> quadratic_regressor.data
[(0,1), (1,2), (2,4), (3,10)]
>>> quadratic_regressor.sum_squared_error()
121 # the predictions are all 0, so the error is 1^2 + 2^2 + 4^2 + 10^2
>>> quadratic_regressor.solve_coefficients()
>>> quadratic_regressor.coefficients
[1.1499999999999986, -0.8499999999999943, 1.249999999999993] # the coefficients calculated USING THE PSEUDOINVERSE
>>> quadratic_regressor.sum_squared_error()
0.45
>>> quadratic_regressor.plot()
(should show a plot of the regression
function along with the data)
```

(DS/Algo; 30 min)

Write a function `heap_sort(arr)`

that sorts the array by first heapifying the array, and then repeatedly popping off the root and then *efficiently* restoring the heap.

To efficiently restore the heap, you should **NOT** make another call to `heapify`

, because at least half of the heap is perfectly intact. Rather, you should **create a helper function** that implements the procedure below. (read more here)

Replace the root of the heap with last element of the heap.

Compare the element with its new children. If the element is indeed greater than or equal to its children, stop.

If not, swap the element with the appropriate child and repeat step 2.

(SWE; 60 min)

Extend your game.

**Hull Size.** Ships have the following hull sizes:

- Scouts, Destroyers, and Ship Yards each have
`hull_size = 1`

- Cruisers and Battlecruisers each have
`hull_size = 2`

- Battleships and Dreadnaughts each have
`hull_size = 3`

Change your "maintenance cost" logic so that maintenance cost is equal to hull size. Also, change your ship yard technology logic to refer to hull size, rather than armor.

```
Level | CP Cost | Hull Size Building Capacity of Each Ship Yard
------------------------------------------------------------
1 | - | 1
2 | 20 | 1.5
3 | 30 | 2
```

**Ship Size Technology.** In order to build particular ships, a player must have particular ship size technology.

```
Technology | Cost | Benefit
----------------------------------------------------------------------------
Ship Size 1 | at start | Can build Scout, Colony Ship, Ship Yard, Decoy
Ship Size 2 | 10 CPs | Can build Destroyer, Base
Ship Size 3 | 15 more CPs | Can build Cruiser
Ship Size 4 | 20 more CPs | Can build Battlecruiser
Ship Size 5 | 25 more CPs | Can build Battleship
Ship Size 6 | 30 more CPs | Can build Dreadnaught
```

**Bases.** Bases are a type of unit that can only be built on colonies (and cannot move). Bases have

- attack class A,
- attack strength 7,
- defense strength 2,
- armor 3.

Bases do not incur maintenance costs. Players must have ship size technology of 2 or more to build a base, and bases are automatically upgraded to the highest technology for free.

**Decoys.** Decoys are units that are inexpensive and can be used to "trick" the opponent into thinking there is an enemy ship. Decoys cost 1 CP, have zero armor, and do not incur maintenance costs. However, they are removed immediately whenever they are involved in combat (i.e. they are immediately destroyed without even being considered in the attacking order).

**Combat screening.** During combat, the player with the greater number of ships has the option to "screen" some of those ships, i.e. leave them out of combat. Screened ships do not participate during combat (they cannot attack or be attacked) but they remain alive after combat.

During combat a player has N ships and another player has K ships, where N > K, then the player with N ships can screen up to N-K of their ships. In other words, the player with more ships in combat can screen as many ships as they want, provided that they still have at least as many ships as their opponent participating in combat.

(ML; 90 min)

a) The following dataset represents the distance between a rocket and Earth's surface, as the rocket takes off. The data points are given in the form `(time, distance)`

.

`[(1, 3.1), (2, 10.17), (3, 20.93), (4, 38.71), (5, 60.91), (6, 98.87), (7, 113.92), (8, 146.95), (9, 190.09), (10, 232.65)]`

Use gradient descent and grid search to find the best parameters $\beta_0,$ $\beta_1,$ and $\beta_2$ that fit a quadratic function $d=\beta_0 + \beta_1 t + \beta_2 t^2$ to the data.

For the grid search, search over all odd integer combinations $(\beta_0, \beta_1, \beta_2)$ in the space $[-5,5] \times [-5,5] \times [-5,5],$ cutting off the gradient descent after a set number of iterations (

`max_num_iterations=50`

) and returning the initial guess that had the lowest error.**If you find that the grid search is taking too long to run, you can lower**`max_num_iterations`

.Once you finish the grid search, continue running gradient descent on the best initial guess, to a precision of

`precision=0.0001`

b) Using the initial guess that yielded the best-fit parameters, plot the quadratic approximation at each iteration. You can use the following function to assist with plotting.

In [ ]:

```
import matplotlib.pyplot as plt
plt.style.use('bmh')
def plot_approximation(approximation_function, data, title=None, padding=5, num_subintervals=20):
x_coords_data = [point[0] for point in data]
y_coords_data = [point[1] for point in data]
x_min_data, x_max_data = min(x_coords_data), max(x_coords_data)
y_min_data, y_max_data = min(y_coords_data), max(y_coords_data)
a, b = x_min_data-padding, x_max_data+padding
approximation_x_coords = [a + (b-a)*(i/num_subintervals) for i in range(num_subintervals+1)]
approximation_y_coords = [approximation_function(x) for x in approximation_x_coords]
plt.scatter(x_coords_data, y_coords_data, color='black')
plt.plot(approximation_x_coords, approximation_y_coords, color='blue')
plt.xlim(x_min_data-padding, x_max_data+padding)
plt.ylim(y_min_data-padding, y_max_data+padding)
plt.title(title)
plt.show()
data = [(1,4), (2,5), (3,7)]
beta_0_sequence = [4 * (1-1/n+1/20)**5 for n in range(1,21)]
beta_1_sequence = [-0.5 * (1-1/n+1/20)**5 for n in range(1,21)]
beta_2_sequence = [0.5 * (1-1/n+1/20)**5 for n in range(1,21)]
for beta_0, beta_1, beta_2 in zip(beta_0_sequence, beta_1_sequence, beta_2_sequence):
title = 'y = {} + {}x + {}x^2'.format(round(beta_0,2), round(beta_1,2), round(beta_2,2))
def f(x):
return beta_0 + beta_1 * x + beta_2 * x**2
plot_approximation(f, data, title=title)
```

c) Verify your best-fit quadratic coefficients using the linear approximation solver you implemented with your matrix class.

- To jog your memory: $$\vec{\beta} \approx (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \vec{y},$$ where, for the cubic approximation, $$\mathbf{X} = \begin{pmatrix} 1 & t_1 & t_1^2 \\ 1 & t_2 & t_2^2 \\ \vdots & \vdots & \vdots \\ 1 & t_n & t_n^2 \end{pmatrix} \qquad \text{and} \qquad \vec{y} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}$$

d) After 200 seconds, what will be the position of the rocket according to the quadratic approximation?

(DS/Algo; 30 min)

a) Write the following functions:

`get_parent_index(i)`

- given the index of a node in a binary tree, returns the index of the*parent*of the node.`get_child_indices(i)`

- given the index of a node in a binary tree, returns the indices of the*children*of the node.

```
A binary tree is indexed as follows:
0
/ \
1 2
/ \ / \
3 4 5 6
/| /|
7 8 9 10
i | get_parent_index(i) | get_child_indices(i) |
------------------------------------------------
0 | - | 1, 2 |
1 | 0 | 3, 4 |
2 | 0 | 5, 6 |
3 | 1 | 7, 8 |
4 | 1 | 9, 10 |
5 | 2 | - |
6 | 2 | - |
7 | 3 | - |
8 | 3 | - |
9 | 4 | - |
10| 4 | - |
```

b) Write a function `heapify(arr)`

that rearranges an input list so that the list satisfies the following condition:

- When a binary tree is built from the list, every parent node has value greater than or equal to each of its children.

(A binary tree satisfying the above criterion is called a max-heap.)

**HINT: loop through the list, starting at the end. For each value, if the value is greater then the value of its parent in the corresponding binary tree, then swap the two values.**

```
>>> arr = [2, 3, 7, 1, 8, 5, 6]
>>> heapified_arr = heapify(arr)
>>> print(heapified_arr)
[8, 3, 7, 1, 2, 5, 6]
The above array can be interpreted as the following tree:
8
/ \
3 7
/| |\
1 2 5 6
```

(SWE; 60 min)

Implement a unit `ShipYard`

which has

- attack class C,
- attack strength 3,
- defense strength 0,
- armor 1,
- CP cost 6, and
- zero maintenance cost.

Players can only build ships at ship yards that have landed on planets that they have colonized. Initially, a player starts with 4 ship yards on their home planet.

There are some constraints on the types of ships that players can build at a shipyard. A ship with a particular level of armor can only be built at a shipyard if the number of shipyards on the planet is greater than or equal to that armor level.

A player starts with Ship Yard Technology 1 and may purchase additional ship yard technology to increase the armor building capacity of each ship yard:

```
Level | CP Cost | Armor Building Capacity of Each Ship Yard
------------------------------------------------------------
1 | - | 1
2 | 20 | 1.5
3 | 30 | 2
```

For example, if a player has a single ship yard on a planet (with ship yard technology 1), then then can only build a scout or destroyer there (both armor=1). To build a cruiser (armor=2), the player would have to either put another ship yard on the planet, or upgrade the ship yard technology to level 3.

(ML; 60 min)

a) In your function `calc_linear_approximation_coefficients(data, initial_guess)`

, include an optional argument `plotting=False`

. If set to `True`

, then show a plot of the data along with the linear approximation at each iteration of the gradient descent. A plotting function is provided for you, below.

Try it on each of the following datasets:

```
data1 = [(0, -2.7), (1, -0.01), (2, 3.28), (3, 7.07), (4, 10.99), (5, 13.51), (6, 14.75), (7, 17.93), (8, 21.65), (9, 25.48)]
data2 = [(0, 0.41), (1, 1.37), (2, 6.41), (3, 14.49), (4, 18.24), (5, 35.24), (6, 38.84), (7, 63.0), (8, 73.97), (9, 96.11)]
data3 = [(0, 0.12), (1, 4.32), (2, 5.41), (3, 0.74), (4, -3.29), (5, -4.16), (6, -1.38), (7, 3.77), (8, 5.65), (9, 2.7)]
```

In [ ]:

```
import matplotlib.pyplot as plt
plt.style.use('bmh')
def plot_linear_approximation(beta_0, beta_1, data, title=None, padding=5):
x_coords_data = [point[0] for point in data]
y_coords_data = [point[1] for point in data]
x_min_data, x_max_data = min(x_coords_data), max(x_coords_data)
y_min_data, y_max_data = min(y_coords_data), max(y_coords_data)
line_endpoints_x_coords = [x_min_data-padding, x_max_data+padding]
line_endpoints_y_coords = [beta_0 + beta_1 * x for x in line_endpoints_x_coords]
plt.scatter(x_coords_data, y_coords_data, color='black')
plt.plot(line_endpoints_x_coords, line_endpoints_y_coords, color='blue')
plt.xlim(x_min_data-padding, x_max_data+padding)
plt.ylim(y_min_data-padding, y_max_data+padding)
plt.title(title)
plt.show()
data = [(1,4), (2,5), (3,7)]
beta_0_sequence = [2.33 * (1-1/n+1/20)**5 for n in range(1,21)]
beta_1_sequence = [1.5 * (1-1/n+1/20)**5 for n in range(1,21)]
for beta_0, beta_1 in zip(beta_0_sequence, beta_1_sequence):
title = 'y = {} + {}x'.format(round(beta_0,2), round(beta_1,2))
plot_linear_approximation(beta_0, beta_1, data, title=title)
```