All Assignment Problems for Cohort 1 (Summer after 10th Grade)

Problem 32-1

(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.

Problem 32-2

(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]

Problem 32-3

(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

Problem 31-1

(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,

$$P(X \, | \, Y) = \dfrac{P(X \wedge Y)}{P(Y)} = \dfrac{\text{count}(X \wedge Y)}{\text{count}(Y)},$$

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*}$$

Problem 31-2

(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]

Problem 31-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

Problem 30-1

(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?

Problem 30-2

(Algo; 90 min)

a) In the file graph/src/node.py, create a class Node that

  • is initialized with an index, and

  • has 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), and

  • has 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]

Problem 30-3

(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)

Problem 29-1

(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: ___

Problem 29-2

(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.

Problem 29-3

(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 CombatTestingPlayers proceeds correctly.

  1. 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)

  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

...

Problem 28-1

(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?

#    ___

Problem 28-2

(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

\begin{align*} \mathcal{D}(P \, || \, Q) = \sum\limits_{X} P(X) \ln \left( \dfrac{P(X)}{Q(X)} \right) \end{align*}

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 asserting 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 _______________________________.

Problem 28-3

(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)

Problem 27-1

(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.

$$\vec{\beta} \approx \left( X^T X \right)^{-1} X^T \vec{y}$$

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 __________________________________________________________

Problem 27-2

(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.

Problem 26-1

(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')

Problem 26-2

(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:

  1. 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.

  2. 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

  1. Create a repository graph.

  2. Put your Tree class in graph/src/tree.py.

  3. 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.

  4. 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]

Problem 26-3

(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".

Problem 25-1

(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.

Problem 25-2

(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

Problem 24-1

(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:

$$y = \beta_0 + \beta_1 t + \beta_2 t^2$$

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:

$$y = \beta_0 + \beta_1 x + \beta_2 x^2 + \beta_3 x^3$$

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

Problem 24-2

(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.

Problem 23-1

(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:

    1. a a square matrix, a tall rectangular matrix, and a wide rectangular matrix;
    2. 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).

    1. the case when the matrix is invertible
    2. the case when the matrix is not invertible due to having dependent rows
    3. the case when the matrix is not invertible due to not being square

Problem 23-2

(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]

Problem 23-3

(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 DumbPlayers proceeds correctly.

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

  1. At the end of Turn 1 Movement Phase:

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

  2. 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

  3. At the end of Turn 2 Movement Phase:

    • Player 1 has 6 scouts at (4,0)
    • Player 2 has 6 scouts at (4,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

  5. At the end of Turn 3 Movement Phase:

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

  6. 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

  7. At the end of Turn 4 Movement Phase:

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

  8. 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

Problem 22-1

(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

Problem 22-2

(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.

Problem 22-3

(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 DumbPlayers 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.

Problem 22-4

(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?

Problem 21-0

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...

Problem 21-1

(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.

  1. 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 = [[]].

  2. 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.

  3. 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']]

Problem 21-2

(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]

Problem 21-3

(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.

Problem 20-1

(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

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-5-9bacb3318584> in <module>()
     20         test['args'], actual_output, desired_output
     21     )
---> 22     assert actual_output == desired_output, error_message + details

AssertionError: incorrect output for add_numbers
INPUT: (0, 1)
OUTPUT: -1
DESIRED: 1

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

Problem 20-2

(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.

Problem 19-1

(30 min)

  1. Create a Github account and create a repository machine-learning.
  2. Create a repl.it account and import the repository into a new repl.
  3. Create a folder src and paste your classes into files:
    • Matrix into Matrix.py
    • PolynomialRegressor into PolynomialRegressor.py
    • GradientDescent into GradientDescent.py

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

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

  5. 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...

Problem 19-2

(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)

Problem 19-3

(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.

Problem 18-1

(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)

Problem 18-2

(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)

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

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

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

Problem 18-3

(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.

Problem 17-1

(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?

Problem 17-2

(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

Problem 17-3

(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.

Problem 16-1

(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)

b) Create a function calc_best_linear_approximation_coefficients(data) that evaluates calc_linear_approximation_coefficients(data, initial_guess) using "grid search" on ~100 initial guesses, where beta_0 and beta_1 cover all combinations of even numbers between -10 and 10. Use precision=0.01 so that each linear approximation runs in less than a second. Then, return the coefficients that yielded the lowest error.

c) Suppose that

  • Eli plays Space Empires for 10 hours and reaches a skill level of 4
  • David plays Space Empires for 40 hours and reaches a skill level of 10
  • Colby plays Space Empires for 100 hours and reaches a skill level of 20
  • George plays Space Empires for 50 hours and reaches a skill level of 15
  • Riley plays space empires for 80 hours and reaches a skill level of 25

i) Using calc_best_linear_approximation_coefficients, what is the linear approximation for the data?

Your answer here

ii) Assuming the relationship between playing hours and skill level is linear, if Justin plays Space Empires for 30 hours, approximately what skill level will he reach? Use the linear approximation from part (i).

Your answer here

Problem 16-2

(DS/Algo; 60 min)

Extend your Tree class.

a) Write a method insert(new_tree, parent_node_value) that takes a new_tree instance and appends it onto the chosen parent_node in self.

  • First, use depth-first search to find the node with parent_node_value. Then, set the new tree's root as the parent node's child.
>>> tree_A = Tree()
>>> edges_A = [('a','c'), ('e','g'), ('e','i'), ('e','a')]
>>> tree_A.build_from_edges(edges_A)
Note: at this point, the tree's internal state should look as follows
    e
   /|\
  a i g
 /
c 

>>> edges_B = [('d','b'), ('a','d'), ('d','f'), ('f','h'), ('d','j'), ('d','k')]
>>> tree_B = Tree()
>>> tree_B.build_from_edges(edges_B)
The tree's internal state should look as follows:
  d 
 /|\\
b j fk
    |
    h

>>> tree_A.insert(tree_B, 'a')
The tree's internal state should look as follows:
    e
   /|\
  a i g
 /|
c d 
 /|\\
b j fk
    |
    h

>>> tree_A.print_depth_first()
e a c d b j f h k i g

(other answers are permissible, e.g.
e i g a d f h b j k c)

b) Write a method print_breadth_first() that prints the node values of a tree, breadth-first.

  • Add the root node to a queue (first-in-first-out). Then, repeatedly print the next node in the queue, remove it from the queue, and add its children to the queue. Keep doing this until the queue is empty.
>>> tree = Tree()
>>> edges = [('a','c'), ('e','g'), ('e','i'), ('e','a'), ('d','b'), ('a','d'), ('d','f'), ('f','h'), ('d','j'), ('d','k')]
>>> tree.build_from_edges(edges)
The tree's internal state should look as follows:
    e
   /|\
  a i g
 /|
c d 
 /|\\
b j fk
    |
    h

>>> tree.print_breadth_first()
e a i g c d b j f k h

other answers are permissible, e.g.
e i a g c d b k j f h

Problem 16-3

(SWE; 60 min)

PART A

Make sure that your combat resolution is implemented correctly (per the previous assignment).

  • Example: Suppose Player A's units (A1 and A2) and Player B's units (B1 and B2) all occupy the same space on the grid, and suppose the attack classes of the units mandate the order A1 > B1 > B2 > A2. Then

    • A1 would go first, making a random choice to attack either B1 or B2.
    • B1 (if still alive) would go second, attacking either A1 or A2
    • B2 (if still alive) would go third, attacking either A1 (if still alive) or A2 (if still alive).
    • A2 (if still alive) would go last, attacking either B1 (if still alive) or B2 (if still alive).
    • The above sequence would repeat until only one team's units occupy the grid space.

  • Note: if two units have the same attack class, then just order them randomly in the attacking sequence.

PART B

Incorporate planets, colony ships, and colonies into your game. Players no longer receive an allowance of CPs from the game. Rather, each turn they get CPs from each of their colonies a planet.

  • Some facts about colony ships:

    • Colony ships can only move 1 space per turn, regardless of speed technology. They have attack 0 and defense 0, and are immediately destroyed whenever an enemy is present. They cost 8 CP to build.

    • When a colony ship lands on an uncolonized planet, it can colonize the planet to form a colony. After colonizing the planet, the colony ship can no longer move.

  • Some facts about colonies:

    • Colonies cannot attack, and they have defense strength of 0. They have no maintenance cost.

    • Colonies start out with a CP capacity of 3, meaning that when the colony ship has colonized a planet, it provides its player with 3 CP per turn. Note that players gain CPs only from colony ships that have colonized a planet.

    • Each time a colony is hit during battle, its CP production decreases by 1 (so the player gets 1 fewer CP per turn). When CP production reaches 0, the colony is destroyed.

  • How the game initially starts:

    • At each player's starting position, they have a colony ship that has colonized their home planet (at the middle-top or middle-bottom of the grid). They also are given 20 CPs, 3 scouts, and 3 additional colony ships.

    • 8 additional planets are randomly placed throughout the 7-by-7 grid.

Problem 15-1

(DS/Algo; 60 min)

Rename your BinaryTree class to Tree and remove the append method and the get_next_node_across_layer method. Now that we've implemented children as a list, we're going to stop working under the binary assumption.

a) Ensure that your method build_from_edges works in general -- not just for binary trees.

  • You should write a while loop that loops through the tree layers until finished.
    • The first layer is the root; get the values of its child nodes from edges and then set the root's children accordingly.
    • The second layer is the root's children; get the values of their child nodes from edges and then set the children of the root's children accordingly.
    • The third layer is the children of the root's children; get the values of their child nodes from edges and then set the children of the third layer accordingly.
    • And so on...

b) Create a method print_depth_first(node=self.root) that prints the values of the nodes of the tree, proceeding in the "depth-first" order.

  • The method should be a very slick recursion: it should print the input node's value, and then call itself on each of the node's children.
>>> tree = Tree()
>>> edges = [('a','c'), ('e','g'), ('e','i'), ('e','a'), ('d','b'), ('a','d'), ('d','f'), ('f','h'), ('d','j'), ('d','k')]
>>> tree.build_from_edges(edges)

The tree's internal state should look as follows:
    e
   /|\
  a i g
 /|
c d 
 /|\\
b j fk
    |
    h

>>> tree_A.print_depth_first()
e a c d b j f h k i g

Other answers are permissible, as long as they 
follow a depth-first ordering, e.g.
e i g a d f h b j k c

DON'T FORGET TO DO PART (C) BELOW

c) What is the time complexity of print_depth_first? Provide justification for your answers.

Problem 15-2

(ML; 60 min)

Create a function calc_linear_approximation_coefficients(data) that uses 2-dimensional gradient descent to compute the line of best fit $\hat{y}=\beta_0 + \beta_1 x$ for a dataset $\left\lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) \right\rbrace.$

To do this, you will need to define the following sum_squared_error function that computes how inaccurate the approximation is:

$$\begin{align*} \text{error} &= \sum_{i=1}^n (\text{approximate y}_i - \text{actual y}_i)^2 \\ &= \sum_{i=1}^n (\hat{y}_i - y_i)^2 \\ &= \sum_{i=1}^n (\beta_0 + \beta_1 x_i - y_i)^2 \\ &= (\beta_0 + \beta_1 x_1 - y_1)^2 + (\beta_0 + \beta_1 x_2 - y_2)^2 + \cdots + (\beta_0 + \beta_1 x_n - y_n)^2 \end{align*}$$

The sum_squared_error function is really just a 2-variable function, with variables $\beta_0$ and $\beta_1.$ So, you can use your existing gradient_descent function to find the values of $\beta_0$ and $\beta_1$ that minimize the sum_squared_error.

>>> on_a_line_data = [(0,1), (1,3), (2,5), (3,7)]
>>> calc_linear_approximation_coefficients(on_a_line_data)
[1, 2]
>>> not_on_a_line_data = [(1,4), (2,5), (3,7)]
>>> calc_linear_approximation_coefficients(not_on_a_line_data)
[2.3333333, 1.5]

Problem 15-3

(SWE; 60 min)

Extend your game system.

a) Implement a "maintenance cost" for each unit, that is equal to the unit's armor value plus its defense technology level. On each turn, the player must pay the maintenance cost associated with each unit. If a player is unable to pay the maintenance cost for the unit, then the unit is eliminated.

  • For example, a Cruiser has armor + defense technology = 3, so the player must pay 3 CP per turn in order to keep the Cruiser.

b) Modify your combat resolution. Instead of resolving each pair combat independently, you should repeatedly loop through all of the units (in the order of their attack class), so that every non-eliminated unit gets the chance to attack before any unit attacks twice.

  • Example: Suppose Player A's units (A1 and A2) and Player B's units (B1 and B2) all occupy the same space on the grid, and suppose the attack classes of the units mandate the order A1 > B1 > B2 > A2. Then

    • A1 would go first, making a random choice to attack either B1 or B2.
    • B1 (if still alive) would go second, attacking either A1 or A2
    • B2 (if still alive) would go third, attacking either A1 (if still alive) or A2 (if still alive).
    • A2 (if still alive) would go last, attacking either B1 (if still alive) or B2 (if still alive).
    • The above sequence would repeat until only one team's units occupy the grid space.

  • Note: if two units have the same attack class, then just order them randomly in the attacking sequence.

Problem 14-1

(DS/Algo; 60 min)

Extend your BinaryTree class. Implement a method build_from_edges that builds a binary tree given a list of edges (parent, child).

Hint: identify the root and then recursively add on child nodes.

>>> tree = BinaryTree()
>>> edges = [('a','c'), ('d','b'), ('a','d'), ('d','f'), ('e','g'), ('f','h'), ('e','a')]
>>> tree.build_from_edges(edges)
Note: at this point, the tree's internal state should look as follows
    e
   / \
  a   g
 /|
c d 
 / \
b   f
    |
    h

Problem 14-2

(ML; 60 min)

a) 2-dimensional linear regression involves finding the line of best fit $y=\beta_0 + \beta_1 x$ for a dataset $\left\lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) \right\rbrace.$

In other words, we aim to find the values of $\beta_0$ and $\beta_1$ that most closely approximate

\begin{align*} \begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_n \end{bmatrix} \begin{bmatrix} \beta_0 \\ \beta_1 \end{bmatrix} &\approx \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} \\ \mathbf{X} \vec{\beta} &\approx \vec{y} \end{align*}

Unfortunately, since $\mathbf{X}$ is taller than it is wide, it is not invertible. However, $\mathbf{X}^T \mathbf{X}$ is invertible, so we have

\begin{align*} \mathbf{X} \vec{\beta} &\approx \vec{y} \\ \mathbf{X}^T \mathbf{X} \vec{\beta} &\approx \mathbf{X}^T \vec{y} \\ \vec{\beta} &\approx \left( \mathbf{X}^T \mathbf{X} \right)^{-1} \mathbf{X}^T \vec{y} \end{align*}

Write a function calc_linear_approximation_coefficients(data) where data is a list of points. Use your Matrix class within the computation.

>>> on_a_line_data = [(0,1), (1,3), (2,5), (3,7)]
>>> calc_linear_approximation_coefficients(not_on_a_line_data)
[1, 2]
>>> not_on_a_line_data = [(1,4), (2,5), (3,7)]
>>> calc_linear_approximation_coefficients(not_on_a_line_data)
[2.3333333, 1.5]

b) Extend your recursive function

gradient_descent(f,x0,alpha=0.01,delta=0.001,precision=0.0001)

to a new function

gradient_descent(f,x0,y0,alpha=0.01,delta=0.001,precision=0.0001)

that works on 2-variable functions.

To recursively update your guesses, use the following update:

\begin{align*} x_{n+1} &= x_n - \alpha f_x(x_n, y_n) \\ y_{n+1} &= y_n - \alpha f_y(x_n, y_n) \end{align*}

Note that you will need to write a helper function that computes partial derivatives using an unbiased (centered) difference quotient:

\begin{align*} f_x(x_n, y_n) &\approx \dfrac{f(x_n+\delta, y_n) - f(x_n-\delta, y_n)}{2\delta} \\ f_y(x_n, y_n) &\approx \dfrac{f(x_n, y_n+\delta) - f(x_n, y_n-\delta)}{2\delta} \\ \end{align*}

where $\delta$ (delta) is chosen as a very small constant. (For our cases, $\delta = 0.001$ should be sufficient.)

The function should recurse until successive guesses are within precision amount of each other.

a) Use your gradient descent function to minimize $f(x,y)=1+x^2+y^2$ starting with the initial guess $(1,2).$

b) Use your gradient descent function to minimize $f(x,y) = 3 + (2x-5)^2 + (3y+1)^2.$

Problem 14-3

(SWE; 60 min)

Extend your game system.

  • On each turn, randomly choose to either upgrade technology or build more ships.

  • Implement speed technology. It increases speed in the same way that attack technology increases attack and defense technology increases defense.

Speed Technology Level | Additional CP Cost |
---------------------------------------------
            0          |         -          |
            1          |         90         |
            2          |         120        |

  • Modify your Scout class so that its default speed is 1.

  • Make it so that a unit's technology level is equal to the technology that existed at the time of building the unit.

    • So, if Scout A is built on turn 1, and then the player purchases speed technology on turn 2, and then builds Scout B on turn 3, then Scout B is faster than Scout A.

Problem 13-1

(Algorithms / Data Structures; 60 min)

Extend your BinaryTree class.

Get rid of the Node attributes right and left. Instead, store an attribute children that is a list of 0, 1, or 2 child nodes. Make sure your append method still works.

For example, if you previously had a node with Node.left = A and Node.right = B, you should now have Node.children = [A, B]. Or, if you had Node.left = None and Node.right = B, then you should now have Node.children = [B].

In [ ]:
# This is the code we wrote during class. 
# You can use it as a starting point if you'd like.

class BinaryTree:
    def __init__(self, head_value):
        self.root = Node(head_value)

    def append(self, value):
        current_node = self.root
        
        while current_node.children_are_filled():
            current_node = current_node.get_next_node_across_layer()

        # now we are at a current_node where some child is no longer filled
        if current_node.left == None:
            current_node.left = Node(value)
            current_node.left.parent = current_node

        elif current_node.right == None:
            current_node.right = Node(value)
            current_node.right.parent = current_node

class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None
        self.parent = None

    def children_are_filled(self):
        left_is_filled = (self.left != None)
        right_is_filled = (self.right != None)
        return left_is_filled and right_is_filled

    def get_next_node_across_layer(self):

        if self.parent == None: # node is the root node
            return self.left

        elif self == self.parent.left: # node is a left node
            return self.parent.right

        elif self == self.parent.right: # node is a right node
            return self.parent.get_next_node_across_layer().left

Problem 13-2

(Machine Learning; 60 min)

a) Create the following normalization functions that replace the elements of an input list x with their normalized values.

  • minmax_normalize - linearly "squashes" the range of the data into the interval $[0,1].$

    >>> minmax_normalize([6, 7, 8, 9])
[0.0, 0.333333, 0.666667, 1.0]
>>> minmax_normalize([4, 13, 3, 5, 5])
[0.1, 1.0, 0.0, 0.2, 0.2]

  • percentile_normalize - the percentile of an element is the portion of the data that is less than the element.

    >>> percentile_normalize([6, 7, 8, 9])
[0.0, 0.25, 0.5, 0.75]
>>> percentile_normalize([4, 13, 3, 5, 5])
[0.2, 0.8, 0.0, 0.4, 0.4]

  • zscore_normalize - computes the number of standard deviations that an element is above (or below) the mean. For example, in the dataset [1, 2, 3, 4, 5, 6, 7] the standard deviation is 2, so we have

    >>> zscore_normalize([1, 2, 3, 4, 5, 6, 7])
[-1.5, -1, -0.5, 0.0, 0.5, 1, 1.5]

b) Create a the following distance functions that compute the distance between two input lists x and y (interpreted as vectors).

  • euclidean_distance - the square root of the sum of squared differences of the components: $$\sqrt{ \sum_{i=1}^n (x_i-y_i)^2 }$$

  • hamming_distance - the sum of absolute differences of the components: $$\sum_{i=1}^n |x_i-y_i|$$

  • cosine_distance - the angle between the vectors (using the dot product): $$\vec{x} \cdot \vec{y} = ||x|| \cdot ||y|| \cdot \cos \theta \qquad \Rightarrow \qquad \theta = \arccos \left( \dfrac{\vec{x} \cdot \vec{y}}{||x|| \cdot ||y||} \right)$$

Come up with tests to demonstrate that your function implements each method correctly.

Problem 13-3

(Software Engineering; 60 min)

Update your game per the following specifications:

a) Change attack_technology and defense_technology to be a player attribute which is applied to all of the player's units during combat. (Previously, it was implemented as a unit attribute.)

  • So, if a player has attack_technology=1, then all of its units get an attack boost of +1 during battle.

b) When moving your units randomly, make sure that they are given the option to stay put. Also, create a unit attribute speed that represents the number of spaces that a unit can move per turn. The speed values are listed in the table below.

  • So, for a unit with speed=2, the unit might stay put, or it might move 1 unit left, or it might move 1 unit up and 1 unit right, or it might move 1 unit down and 1 more unit down, and so on.

c) Create a unit attribute armor that represents the number of hits that the unit can withstand before being destroyed. Whenever a unit is hit during battle, its armor decreases by 1. Once armor reaches 0, the unit is destroyed. The initial armor values are listed in the table below.

Ship          | Armor | Speed |
-------------------------------
Scout         |   1   |   2   |
Destroyer     |   1   |   1   |
Cruiser       |   2   |   1   |
Battlecruiser |   2   |   1   |
Battleship    |   3   |   1   |
Dreadnaught   |   3   |   1   |

Problem 12-1

(30 min)

a) Write a function count_compression(string) that takes a string and compresses it into a list of tuples, where each tuple indicates the count of times a particular symbol was repeated.

>>> count_compression('aaabbcaaaa')
[('a',3), ('b',2), ('c',1), ('a',4)]
>>> count_compression('22344444')
[(2,2), (3,1), (4,5)]

b) Write a function count_decompression(compressed_string) that decompresses a compressed string to return the original result.

>>> count_decompression([('a',3), ('b',2), ('c',1), ('a',4)])
'aaabbcaaaa'
>>> count_decompression([(2,2), (3,1), (4,5)])
'22344444'

Problem 12-2

(45 min)

Write a class BinaryTree which is similar to the doubly linked list, but with the following exceptions:

  • the head node is now called the root node
  • every node has two attributes left and right instead of just a single attribute next

The only method you need to implement (as of now) is append.

>>> tree = BinaryTree(0)
>>> tree.append(1)
>>> tree.append(2)
>>> tree.append(3)
Note: at this point, the tree's internal state should look as follows
    0
   / \
  1   2
 /
3
>>> tree.append(4)
>>> tree.append(5)
>>> tree.append(6)
Note: at this point, the tree's internal state should look as follows
    0
   / \
  1   2
 /|   |\
3 4   5 6

Problem 12-3

(60 min)

Update your game system so that on each turn, each player's construction points (CP) are increased by 10, and they purchase "attack technology" or "defense technology" for a ship (chosen at random) whenever possible.

"Attack technology" and "defense technology" are upgrades to a unit's baseline attack and defense stats during battle. For example, if a unit's baseline attack is $2,$ and it has an attack technology of $3,$ then in battle it is treated as having an attack level of $2+3=5.$

The costs for technology upgrades are as follows:

Attack Technology | CP Cost |
-----------------------------
       0          |   n/a   | (all ships start with attack technology 0)
       1          |   20    |
       2          |   30    |
       3          |   40    |
Defense Technology | CP Cost |
------------------------------
       0           |   n/a   | (all ships start with defense technology 0)
       1           |   20    |
       2           |   30    |
       3           |   40    |

Note: the CP Cost tells how many more CPs are needed to get to the next attack technology. So, if a unit was at attack technology 0, then to upgrade it to attack technology 2, you would have pay 50 CPs.

Problem 12-4

(60 min)

a) Write a recursive function gradient_descent(f,x0,alpha=0.01,delta=0.001,precision=0.0001) that uses gradient descent to estimate the minimum of $f(x),$ given the initial guess $x=x_0.$ Here's a visualization of how it works.

The gradient descent algorithm is

$$x_{n+1} = x_n - \alpha f'(x_n),$$

where $\alpha$ (alpha) is a constant called the learning rate.

Note that you will have to write a helper function to estimate $f'(x_n)$ using a difference quotient,

$$f'(x_n) \approx \dfrac{f(x_n+\delta) - f(x_n-\delta)}{2\delta},$$

where $\delta$ (delta) is chosen as a very small constant. (For our cases, $\delta = 0.001$ should be sufficient.)

The function should recurse until successive guesses are within precision amount of each other.

b) Test gradient_descent on a dummy example: estimate the minimum value of

$$f(x)=x^2+2x+1$$

using the initial guess $x_0 = 0.$ (Note: do not work out the derivative by hand! You should estimate it numerically.)

c) Use gradient_descent to estimate the minimum value of

$$f(x)=\frac{x^{2}+\cos\left(x\right)}{e^{\sin\left(x\right)}}$$

using the initial guess $x_0 = 0.$ (Note: do not work out the derivative by hand! You should estimate it numerically.)

Problem 11-1

(30 min)

Observe that we can time how long it takes to run some code by using the time module:

In [ ]:
from time import time
start = time()

# begin code to time
myList = [k**2+k+1 for k in range(10000)]
mySum = sum(myList)
# end code to time

diff = time()-start
print(diff)

0.00748896598815918

a) Create a function measure_time(f,x) that measures the amount of time it takes to apply the function f to a single input x.

Note: you may get a slightly different time than shown in the example below, because the time that the computer takes to run the function is not always exactly the same.

def f(x):
    my_list = [k**2+k+1 for k in range(x)]
    my_sum = sum(my_list)
    return my_sum

measure_time(f,10000)
---
0.003872394561767578

b) Create a function time_statistics(f,x,num_samples=100) that computes num_samples samples of the time it takes to apply the function f to the input x, and returns the resulting mean and standard deviation of the time.

>>> time_statistics(f,10000)
{
  'mean': 0.003220198154449463,
  'stdev': 0.00035378651456685384
}

Problem 11-2

(60 min)

a) Create a function gap_swap_sort(x) that sorts a list x in a way that is similar to swap_sort, except instead of looping through the whole list each time, we loop through "gaps" of the list and cut the gap in half after each iteration.

For example, for the following list of length $8,$ the first gap is ${8/2} = 4.$

$$ [3, 2, 5, 1, 7, 4, 1, 2] \\ [\underline{\mathbf{3}}, 2, 5, 1, \underline{\mathbf{7}}, 4, 1, 2]\\ [3, \underline{\mathbf{2}}, 5, 1, 7, \underline{\mathbf{4}}, 1, 2]\\ [3, 2, \underline{\mathbf{1}}, 1, 7, 4, \underline{\mathbf{5}}, 2]\\ [3, 2, 1, \underline{\mathbf{1}}, 7, 4, 5, \underline{\mathbf{2}}] $$

Now, the gap becomes $4/2 = 2.$

$$ [3, 2, 1, 1, 7, 4, 5, 2] \\ [\underline{\mathbf{1}}, 2, \underline{\mathbf{3}}, 1, 7, 4, 5, 2] \\ [1, \underline{\mathbf{1}}, 3, \underline{\mathbf{2}}, 7, 4, 5, 2] \\ [1, 1, \underline{\mathbf{3}}, 2, \underline{\mathbf{7}}, 4, 5, 2] \\ [1, 1, 3, \underline{\mathbf{2}}, 7, \underline{\mathbf{4}}, 5, 2] \\ [1, 1, 3, 2, \underline{\mathbf{5}}, 4, \underline{\mathbf{7}}, 2] \\ [1, 1, 3, 2, 5, \underline{\mathbf{2}}, 7, \underline{\mathbf{4}}] $$

Now, the gap becomes $2/2 = 1,$ which is just an iteration of swap_sort:

$$ [1, 1, 3, 2, 5, 2, 7, 4] \\ [\underline{\mathbf{1}}, \underline{\mathbf{1}}, 3, 2, 5, 2, 7, 4] \\ [1, \underline{\mathbf{1}}, \underline{\mathbf{3}}, 2, 5, 2, 7, 4] \\ [1, 1, \underline{\mathbf{2}}, \underline{\mathbf{3}}, 5, 2, 7, 4] \\ [1, 1, 2, \underline{\mathbf{3}}, \underline{\mathbf{5}}, 2, 7, 4] \\ [1, 1, 2, 3, \underline{\mathbf{2}}, \underline{\mathbf{5}}, 7, 4] \\ [1, 1, 2, 3, 2, \underline{\mathbf{5}}, \underline{\mathbf{7}}, 4] \\ [1, 1, 2, 3, 2, 5, \underline{\mathbf{4}}, \underline{\mathbf{7}}] $$

We can't make the gap any smaller, so we continue looping through with gap size $1$ (i.e. swap_sort) until the list is sorted.

b) State the time complexity of gap_swap_sort using big-O notation. Provide some justification for your answer.

Your answer here:

Problem 11-3

(90 min)

Observe that the following function can be used to plot the game board:

In [ ]:
import matplotlib.pyplot as plt
from matplotlib.ticker import MultipleLocator

def labeled_scatter_plot(data, gridsize=[5,5], fontsize=12):
    fig, ax = plt.subplots()
    ax.xaxis.set_minor_locator(MultipleLocator(0.5))
    ax.yaxis.set_minor_locator(MultipleLocator(0.5))

    for item in data:
        x = item['x']
        y = item['y']
        color = item['color']
        label = item['label']
        ax.text(x, y, label, fontsize=fontsize, color=color, horizontalalignment='center', verticalalignment='center')

    x_max, y_max = gridsize
    plt.xlim(-0.5 ,x_max-0.5)
    plt.ylim(-0.5, y_max-0.5)

    plt.grid(which='minor')
    plt.show()
In [ ]:
data1 = [
    {'x': 3, 'y': 2, 'color': 'red', 'label': 'S1'},
    {'x': 2, 'y': 1, 'color': 'blue', 'label': 'D2'}
]

data2 = [
    {'x': 3, 'y': 1, 'color': 'red', 'label': 'S1'},
    {'x': 3, 'y': 1, 'color': 'blue', 'label': 'D2'}
]

labeled_scatter_plot(data1)
labeled_scatter_plot(data2)

a) Refactor your code per the following specifications:

  • You need separate classes: Game, Player, Unit, and a class for each type of ship.

  • Your code needs to be readable -- variables need to be named well, and there shouldn't be too much happening on any single line.

  • Each method within a class should be something that the class actually does. For example, a Unit does not build a fleet. A player builds a fleet.

  • Each function should be concise and should do just one thing. (Extreme case: if a function can't be seen on a single screen without scrolling, then that's an issue.)

b) Use the with the function labeled_scatter_plot to display the board after each turn. Don't get rid of your text logging. At this point the board display should be an addition, not a replacement for your logging.

  • Use the naming convention <letter><number> where <letter> represents the type of ship and <number> represents the unit number. So, S1 would correspond to a Scout that is a player's Unit 1.

    • Battlecruiser should have the letter Bc and Battleship should have the label Bs.

  • Player 1 should be blue, and Player 2 should be red.

c) Modify the function labeled_scatter_plot so that when two units occupy the same grid square, they do not overlap visually. You should move the units slightly apart while ensuring that they still lie within the required grid square.

Problem 11-4

(45 min)

a) Refactor your Matrix class so that no method mutates the underlying matrix.

b) Extend your Matrix class to include a method inverse_by_minors() that computes the inverse using the method of minors.

  • Here is an overview of the method of minors.

c) Show that inverse_by_minors and inverse (which leverages rref) give the same result when applied to several different matrices.

d) State the time complexities of inverse_by_minors and inverse using big-O notation. Provide some justification for your answer.

inverse_by_minors: your answer here

inverse: your answer here

Problem 10-1

(30 min)

a) Take your class LinkedList from before and extend it to become a doubly linked list.

This means that each Node in the list should have an additional attribute, prev, which returns the previous node. (It is the opposite of the next attribute.)

b) Create and demonstrate tests to provide evidence that each node's prev attribute is set correctly after modifying the list by pushing, inserting, or deleting elements.

Problem 10-2

(60 min)

a) Write a function tally_sort(x) that sorts the list x from least to greatest using the following process:

  1. Greate an array of indices consisting of the numbers from the minimum to the maximum element.

  2. Go through the list x and tally up the count in each bin.

  3. Transform the tallies into the desired sorted list.

For example, if x = [1, 4, 1, 2, 7, 5, 2], then the histogram would be:

Tally:   | 2 | 2 | 0 | 1 | 1 | 0 | 1 |
Index:   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

And therefore the sorted list would be [1, 1, 2, 2, 4, 5, 7]

State the time complexity of tally_sort using big-O notation. Provide some justification for your answer.

Your answer here:

b) Write a function card_sort(x) that sorts the list x from least to greatest by using the method that a person would use to sort cards by hand.

For example, to sort x = [12, 11, 13, 5, 6], we would go through the list and repeatedly put the next number we encounter in the appropriate place relative to the numbers that we have already gone through.

So, the sequence would be:

[12, 11, 13, 5, 6]
[11, 12, 13, 5, 6]
[11, 12, 13, 5, 6]
[5, 11, 12, 13, 6]
[5, 6, 11, 12, 13]

State the time complexity of card_sort using big-O notation. Provide some justification for your answer.

Your answer here:

Problem 10-3

(90 min)

a) Refactor your game code to the following specifications:

  1. Use (at least) the following classes: Game, Player, Unit. (Do NOT use Ship in place of Unit; e.g. later on there will be a type of unit Colony which is not a ship.)

  2. An object should NOT mutate the underlying structure of a different object. Each object should mutate its own underlying structure.

    • For example, in Player, you should NOT be explicitly increasing or decreasing the coordinates of units. Rather, you should say something like unit.move(), and then the unit will adjust its own coordinates as appropriate.

  3. Clean up any for loops so that you are looping over the elements of the list, rather than the index of the list (unless you actually need the index).

    • Bad: for i in range(len(units)): self.units[i].move()
    • Good: for unit in self.units: unit.move()

b) Introduce the following additional functionality:

  • Each player starts out with $50$ construction points (CPs) and then randomly builds a fleet until no more units can be used.

    • The cost of building a particular type of unit is shown in the table below. Each player should build a random fleet using the 50 construction points.

    • So that might be a Dreadnaught (24 cp), a Destroyer (9 cp), and a Battlecruiser (15cp) for a total cost of 48 cp.

    • Or it might be 3 Scouts (3 x 6cp = 18cp), a Battleship (20cp), and a Cruiser (12cp) for a total of 50cp.

    • Basically just build a fleet by randomly choosing units until there's not enough construction points to purchase any more units. (To be clear, your code should perform the random generation of the fleet -- i.e. you shouldn't just manually pick it randomly.)

  • Combat resolution proceeds as follows:

    1. Units attack each other in the order of their attack class (A first, then B, and so on). If two ships have the same attack class, then you can fall back to random choice.

    2. Let hit_threshold equal the attacker's attack strength subtracted by the defender's defense strength. Then, roll a $6$-sided die.

      • If the die roll is less than or equal to hit_threshold, then a hit is scored.

      • Also, regardless of hit_threshold, a roll of 1 always scores a hit.

      • If a unit is hit, then it is immediately destroyed.

Name          | CP Cost | Attack Class | Attack Strength | Defense Strength |
-----------------------------------------------------------------------------
Scout         |    6    |      E       |        3        |        0         |
Destroyer     |    9    |      D       |        4        |        0         |
Cruiser       |   12    |      C       |        4        |        1         |
Battlecruiser |   15    |      B       |        5        |        1         |
Battleship    |   20    |      A       |        5        |        2         |
Dreadnaught   |   24    |      A       |        6        |        3         |

Problem 10-4

(30 min)

a) Extend your Matrix class to include a method recursive_determinant() that computes the determinant recursively using the cofactor method.

  • Here is an example of using the cofactor method on a $3 \times 3$ matrix

  • Here is an example of using the cofactor method on a $4 \times 4$ matrix

b) Show that recursive_determinant and determinant (which leverages rref) give the same result when applied to several different matrices.

c) State the time complexities of recursive_determinant and determinant using big-O notation. Provide some justification for your answer.

recursive_determinant: your answer here

determinant: your answer here

Problem 9-1

(30 min)

a) Write a function simple_sort(x) that takes an input list x and sorts its elements from least to greatest by repeatedly finding the smallest element and moving it to a new list. Don't use Python's built-in min function.

State the time complexity of simple_sort using big-O notation.

Your answer:

b) Write a recursive function swap_sort(x) that sorts the list from least to greatest by repeatedly going through each pair of adjacent elements and swapping them if they are in the wrong order.

State the time complexity of swap_sort using big-O notation.

Your answer:

Problem 9-2

(45 min)

Extend your class LinkedList to include the following methods:

  • push(new_data) - insert a new node at the head of the linked list, containing the new_data

  • insert_after(prev_node, new_data) - insert a new node after the given prev_node, containing the new_data

  • append(new_data) - append a new node to the end of the linked list, containing the new_data

  • delete(data) - delete the first node in the linked list whose data is the given data

  • search(data) - return True if the given data is in the linked list, and False otherwise

Be sure to test your code AND RUN IT THROUGH THE LINTER.

Problem 9-3

(90 min)

Implement the following game:

  • There are 2 players with 3 units each, on a $5 \times 5$ grid ($0 \leq x, y \leq 4$).

    • Player 1's units start at $(0,2),$ while Player 2's units start at $(4,2)$

  • During each turn, each unit moves randomly to an adjacent space. (Diagonal spaces are not adjacent)

    • For the random selection, you may import the random module and use random.randint(a,b) to return a random integer N such that a <= N <= b

  • After moving, if two units occupy the same space, one unit (chosen randomly) is destroyed.

    • You may again use random.randint(a,b).

  • The game stops when either all of a player's units have been destroyed, or after $100$ turns, whichever happens soonest.

    • If the game is stopped at $100$ turns, then the player with more surviving units wins. (If the players have the same number of surviving units, then it is a tie.)

The purpose of this problem is to give you more experience using classes. Don't just write a bunch of solo functions. You need to organize your code well. We'll be adding a bunch of additional features onto this game in the future.

RUN YOUR CODE THROUGH THE LINTER!

>>> game = Game()
>>> game.state()

Player 1:
    Unit 1: (0,2)
    Unit 2: (0,2)
    Unit 3: (0,2)
Player 2:
    Unit 1: (4,2)
    Unit 2: (4,2)
    Unit 3: (4,2)

>>> game.complete_turn()

Player 1:
    Unit 1: (0,2) -> (0,1)
    Unit 2: (0,2) -> (0,3)
    Unit 3: (0,2) -> (1,2)

>>> game.resolve_combat()
>>> game.complete_turn()

Player 2:
    Unit 1: (4,2) -> (4,1)
    Unit 2: (4,2) -> (3,2)
    Unit 3: (4,2) -> (4,3)

>>> game.resolve_combat()
>>> game.complete_turn()

Player 1:
    Unit 1: (0,1) -> (1,1)
    Unit 2: (0,3) -> (0,4)
    Unit 3: (1,2) -> (2,2)

>>> game.resolve_combat()
>>> game.complete_turn()

Player 2:
    Unit 1: (4,1) -> (3,1)
    Unit 2: (3,2) -> (2,2)
    Unit 3: (4,3) -> (3,3)

>>> game.resolve_combat()

Combat at (2,2)
Player 1 (Unit 3) vs Player 2 (Unit 2)
Survivor: Player 2 (Unit 2)

>>> game.state()

Player 1:
    Unit 1: (1,1)
    Unit 2: (0,4)
Player 2:
    Unit 1: (3,1)
    Unit 2: (2,2)
    Unit 3: (3,3)

>>> game.run_to_completion()
>>> game.state()

Player 1:
    Unit 1: (4,0)
Player 2:
    Unit 2: (3,1)
    Unit 3: (1,1)

>>> game.num_turns
100

>>> game.winner
2

Problem 9-4

(30 min)

Extend your Matrix class to include a method determinant() that computes the determinant.

  • You should do this by using the same code as in your rref() method, but keeping track of the scaling factors by which you divide the rows of the matrix. The determinant is just the product of these scaling factors (assuming the determinant is nonzero).

    • Optional: If you want to avoid duplicating code (at the expense of making rref a bit more complex), you can modify your rref() method to include an optional parameter return_determinant which is by default set to False. Then, your determinant() method can consist of just return self.rref(return_determinant=True).

  • Be sure to address the following edge cases:

    • If the matrix does not row-reduce to the identity matrix, then the determinant is zero.
    • If the matrix is non-square, then the determinant is undefined.

Test your determinant method on 4 different examples. You can use this matrix determinant calculator to check the results.

RUN YOUR CODE THROUGH THE LINTER!

Problem 8-1

(30 min)

a) Write a function median(x) that computes the median of an input list. Make your own tests.

b) Write a function cov(x,y) that computes the covariance of two lists x an y.

Also write a function corr(x,y) that computes the Pearson correlation coefficient between the two lists.

Make your own tests.

Problem 8-2

(30 min)

Figure out what what following function does, and modify it so that it is readable. Be sure to rename the function and variables with more informative names, and expand out the nested list comprehension. Remember to test that your implementation gives the same result as the original function.

def doesSomething(z):
  return [['abcdefghijklmnopqrstuvwxyz'.index(x) for x in y] for y in z.split(' ')]

Problem 8-3

(30 min)

The Collatz function is defined as

$$f(n) = \begin{cases} n \, / \, 2 & \text{if } n \text{ is even} \\ 3n+1 & \text{if } n \text{ is odd} \end{cases}$$

The Collatz conjecture is that by repeatedly applying this function to any positive number, the result will eventually reach the cycle

$$1 \to 4 \to 2 \to 1.$$

For example, repeatedly applying the Collatz function to the number $13,$ we have:

$$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$

a) Without using recursion, create a function collatz_iterations(number) that computes the number of iterations of the Collatz function that it takes for the input number to reach $1.$

>>> collatz_iterations(13)
9

b) Using recursion, create a function collatz_iterations(number, iterations=0) that computes the number of iterations of the Collatz function that it takes for the input number to reach $1.$

>>> collatz_iterations(13)
9

Problem 8-4

(45 min)

Create a class LinkedList and a class Node which together implement a singly linked list.

  • The class LinkedList should have exactly one attribute:

    • head: gives the node at the beginning of the linked list

  • Each node should have exactly two attributes:

    • data: returns the contents of the node
    • next: returns the next node

  • LinkedList should have exactly three methods:

    • print(): prints the contents of the nodes, starting at the head
    • length(): returns the number of nodes in the linked list
    • append(): appends a new node to the tail of the linked list

For this assignment, you only need to implement the functionality above. We will continue this problem on the next assignment (in which you will implement insert, delete, and search). But you don't have to do that yet.

Make sure not to use any python lists in your answer.

>>> x = LinkedList(4)
>>> x.head.data
4
>>> x.append(8)
>>> x.head.next.data
8
>>> x.append(9)
>>> x.print()
4
8
9
>>> x.length()
3

Problem 8-5

(45 min)

a) Extend your Matrix class to include a method inverse() that computes the inverse matrix using Gaussian elimination (i.e. your rref method).

If the matrix is not invertible, print a message that explains why -- is it be cause it's singular, or because it's non-square?

Test your inverse method on 2 different examples. Verify that when you multiply the original matrix by its inverse, you get the identity matrix.

b) Extend your Matrix class to include a method solve(b) that uses reduced row echelon form to solve the equation $Ax=b,$ where $A$ is the matrix itself and $b$ is a column vector.

Use an augmented matrix, and let your rref() method do the brunt of the work.

For example, the system $$ \begin{cases} x_1 + x_2 = 6 \\ x_1 - x_2 = 2 \end{cases} $$

can be represented as the equation $Ax=b$ where

$$ A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad b = \begin{pmatrix} 6 \\ 2 \end{pmatrix} $$

The solution to the system is $x_1 = 4$ and $x_2 = 2,$ so the solution to $Ax=b$ is $x = \begin{pmatrix} 4 \\ 2 \end{pmatrix}.$

>>> A = Matrix(elements = [[1, 1],
                           [1, -1])
>>> b = [6, 2]
>>> A.solve(b)
[4, 2]

Problem 7-1

(30 min)

a) Create a function find_all_numbers_divisible_by_a_and_b(n,a,b) that lists the numbers $1$ through $n$ that are divisible by both $a$ and $b$. Your function should consist of simply returning a list comprehension.

>>> find_all_numbers_divisible_by_a_and_b(100,6,15)
[30, 60, 90]

b) Rewrite the following function to consist of simply returning a list comprehension.

def compute_all_products(M,N):
    product = []
    for m in range(M):
       for n in range(N):
           product = m * n
           result.append(product)
    return product

Problem 7-2

(60 min)

a) WITHOUT using recursion, create a function skip_factorial(n) that computes the product

  • $n(n-2)(n-4)\ldots(2)$ if $n$ is even, or
  • $n(n-2)(n-4)\ldots(1)$ if $n$ is odd.
>>> skip_factorial(6)
48
>>> skip_factorial(7)
105

Now, rewrite the function skip_factorial(n) WITH recursion.

b) WITHOUT using recursion, create a function unlist(x) that removes outer parentheses from a list until either a) the final list consists of multiple elements, or b) no more lists exist.

>>> unlist([[[[1], [2,3], 4]]])
[[1], [2,3], 4]
>>> unlist([[[[1]]]])
1

Now, rewrite the function unlist(x) WITH recursion.

Problem 7-3

(45 min)

Write several classes to implement the following hierarchy. Be sure to use inheritance when appropriate.

School has a name
School has many courses
School has many teachers
School has many students
School has a principal
Principal has a first name
Principal has a last name
Course has a teacher
Teacher has a first name
Teacher has a last name
Course has many students
Student has a first name
Student has a last name
Student has a grade

When writing your hierarchy, use the given information:

  • The principal of AI High is Geoffrey Hinton.

  • The courses, teachers, and students are as follows:

    1. Applied Math (taught by Gilbert Strang)
      • Cierra Vega
      • Alden Cantrell
      • Kierra Gentry
      • Pierre Cox
    2. Machine Learning (taught by Andrej Karpathy)
      • Alden Cantrell
      • Pierre Cox
      • Miranda Shaffer
    3. Software Development (taught by Avie Tevanian)
      • Cierra Vega
      • Alden Cantrell
      • Kierra Gentry
      • Pierre Cox
      • Thomas Crane
      • Miranda Shaffer

  • The students have the following grade levels:

    • 10th grade: Cierra Vega, Kierra Gentry, Pierre Cox
    • 11th grade: Alden Cantrell, Miranda Shaffer
    • 12th grade: Thomas Crane

Problem 7-4

(30 min)

Extend the rref method in your Matrix class to work on matrices that do not reduce to the identity matrix.

>>> A = Matrix(elements = [[0, 1, 2],
                           [3, 6, 9],
                           [2, 6, 8]])
>>> A.rref().show()
[1, 0, 0]
[0, 1, 0]
[0, 0, 0]

Create the following additional examples to test your code:

A) 2 examples of square matrices that reduce to different rref forms

B) 2 examples of tall rectangular matrices (i.e. more rows than columns) that reduce to different rref forms

C) 2 examples of wide rectangular matrices (i.e. more columns than rows) that reduce to different rref forms

Problem 6-1

Estimated time: (20 min)

a) Write a function mean that computes the mean of a list of numbers.

The mean is defined as follows:

$$\text{Mean}(x_1, x_2, \ldots, x_n) = \dfrac{x_1 + x_2 + \ldots + x_n}{n}$$

Test your code on the following example:

>>> mean([1,3,4,9,6,5])
4.666666666666667

b) Write a function var that computes the variance of a list of numbers.

Let $\bar{x}$ denote $\text{Mean}(x_1, x_2, \ldots, x_n).$ The variance is defined as follows:

$$\text{Var}(x_1, x_2, \ldots, x_n) = \dfrac{(x_1-\bar{x})^2 + (x_2-\bar{x})^2 + \ldots + (x_n-\bar{x})^2}{n}$$

Test your code on the following example:

>>> var([1,3,4,9,6,5])
6.222222222222222

c) Write a function stdev that computes the standard deviation of a list of numbers.

Again, let $\bar{x}$ denote $\text{Mean}(x_1, x_2, \ldots, x_n).$ The standard deviation is defined as follows:

$$\text{StDev}(x_1, x_2, \ldots, x_n) = \sqrt{ \dfrac{(x_1-\bar{x})^2 + (x_2-\bar{x})^2 + \ldots + (x_n-\bar{x})^2}{n} }$$

Test your code on the following example:

>>> var([1,3,4,9,6,5])
2.494438257849294

d) In English words, what do the mean, variance, and standard deviation represent?

Problem 6-2

(5 min)

Consider the code below:

class Animal(object):
    pass

class Dog(Animal):
    def __init__(self, name):
        self.name = name

class Cat(Animal):
    def __init__(self, name):
        self.name = name

class Person(object):
    def __init__(self, name, pets):
        self.name = name
        self.pets = pets

Fill in the following blanks with "is a", "has a", or "has many" as appropriate:

  1. An Animal $\_\_\_$ object
  2. A Dog $\_\_\_$ Animal
  3. A Dog $\_\_\_$ name
  4. A Cat $\_\_\_$ Animal
  5. A Cat $\_\_\_$ name
  6. A Person $\_\_\_$ Object
  7. Person $\_\_\_$ name
  8. A Person $\_\_\_$ pets

Problem 6-3

(30 min)

Notice that we can approximate a zero of a function by repeatedly computing the zero of the tangent line:

a) Create a function zero_of_tangent_line(c) that computes the zero of the tangent line to the function $f(x)=x^3+x-1$ at the point $x=c.$

Test your code on the following example:

>>> zero_of_tangent_line(0.5)
0.714286

b) Create a function estimate_solution(precision) that estimates the solution to $f(x) = x^3+x-1$ by repeatedly calling zero_of_tangent_line until the next guess is within precision of the previous guess.

Test your code on the following example:

>>> estimate_solution(0.01)
0.6823284

Problem 6-4

(45 min)

Extend your Matrix class to include a method rref that converts the matrix to reduced row echelon form. You should use the row reduction algorithm shown below:

  • Step 1a: Swap the 1st row with a lower one so a leftmost nonzero entry is in the 1st row (if necessary).
  • Step 1b: Scale the 1st row so that its first nonzero entry is equal to 1.
  • Step 1c: Use row replacement so all entries below this 1 are 0.
  • Step 2a: Swap the 2nd row with a lower one so that the leftmost nonzero entry is in the 2nd row.
  • Step 2b: Scale the 2nd row so that its first nonzero entry is equal to 1.
  • Step 2c: Use row replacement so all entries below this 1 are 0.
  • Step 3a: Swap the 3rd row with a lower one so that the leftmost nonzero entry is in the 3rd row.
  • etc.
  • Last Step: Use row replacement to clear all entries above the pivots, starting with the last pivot.

For this problem, you may assume that the matrix is a square matrix that reduces to the identity matrix. We will deal with other edge-cases (like zero rows and rectangular matrices) in a future assignment.

>>> A = Matrix(elements = [[0, 1, 2],
                           [3, 6, 9],
                           [2, 6, 8]])
>>> A.rref().show()
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]

Also, test your code on 2 more examples of your own choosing.

Problem 5-0

In [ ]:
%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use('bmh')
In [ ]:
plt.plot(
    [0, 1, 2, 0],  # X-values
    [0, 1, 0, 0],   # Y-values
    color='blue'
)
plt.gca().set_aspect("equal")

Problem 5-1

a) Write a class Rectangle.

  • include the attributes base, height, color, perimeter, area, and vertices.

    • only base, height, and color should be used as parameters

  • include a method describe() that prints out the attributes of the rectangle.

  • include a method render() that renders the rectangle on a cartesian plane. (You can use plt.plot() and plt.gca() and plot.gca().set_aspect("equal") as shown above.)

>>> rect = Rectangle(5,2,'red')
>>> rect.describe()
Base: 5
Height: 2
Color: red
Perimeter: 14
Area: 10
Vertices: [(0,0), (5,0), (5,2), (0,2)]
>>> rect.render()

b) Write a class RightTriangle.

  • Include the attributes base, height, color, perimeter, area, and vertices.

  • Include a method describe() that prints out the attributes of the right triangle.

  • include a method render() that draws the triangle on a cartesian plane.

>>> tri = RightTriangle(5,2,'blue')
>>> tri.describe()
Base: 5
Height: 2
Color: blue
Perimeter: 12.3851648071
Area: 5
Vertices: [(0,0), (5,0), (0,2)]
>>> tri.render()

c) Write a class Square that inherits from Rectangle. Here's an example of how to implement inheritance.

Note: You should not be manually writing any methods in the Square class. The whole point of using inheritance is so that you don't have to duplicate code.

>>> sq = Square(5,'green')
>>> sq.describe()
Base: 5
Height: 5
Color: green
Perimeter: 20
Area: 25
Vertices: [(0,0), (5,0), (5,5), (0,5)]
>>> sq.render()

d) Write a class Shape with

  • attributes base, height, and color

  • methods describe() and render()

Then, rewrite your classes Rectangle and RightTriangle so that they are child classes that inherit from the parent class Shape.

The reason why we might do this is that we'd like to avoid duplicating the describe() and render() methods in each subclass. This way, you'll only have to write the these methods once, in the Shape class.

Problem 5-2

The polynomial $f(x)=x^3+x-1$ has a root on the interval $[0,1].$

a) Create a function update_bounds(bounds) that guesses a root halfway between the bounds, determines whether the guess was too high or too low, and updates the bounds accordingly.

  • For example, starting with the bounds $[0,1],$ the guess would be $0.5.$ This guess is too low because $f(0.5) = -0.375 < 0.$ So, the updated bounds would be $[0.5, 1].$

  • Now, using the bounds $[0.5,1]$, the next guess would be $0.75.$ This guess is too high because $f(0.75) = 0.171875 > 0.$ So, the updated bounds would be $[0.5, 0.75].$

Example:

>>> update_bounds([0,1])
[0.5, 1]
>>> update_bounds([0.5,1])
[0.5, 0.75]

b) Create a function estimate_solution(precision) that estimates the solution to $f(x) = x^3+x-1$ by repeatedly calling update_bounds until the estimated solution is guaranteed to be within precision of the actual solution. You can start with the bounds $[0,1]$ again.

The actual solution is $0.68233 \ldots$, but this number should not appear anywhere in your code. Instead, you can find the maximum error of an estimated solution by taking half the length between the bounds.

  • For example if the bounds were $[0.66, 0.7]$ then the guess would be $0.68$ and the maximum error would be $0.02.$ So, $0.68$ would be a valid output of estimate_solution(0.1) but not estimate_solution(0.01).

Problem 5-3

Implement the following helper methods in your matrix class.

  • get_pivot_row(self, column_index): returns the index of the topmost row that has a nonzero entry in the desired column_index and such that all entries left of column_index are zero. Otherwise, if no row exists, return None.

  • swap_rows(self, row_index1, row_index2): swap the row at row_index1 with the row at row_index2.

  • scale_row(self, row_index): divide the entire row at row_index by the row's first nonzero entry.

  • clear_below(self, row_index):

    • Let $j$ be the column index of the first nonzero entry in the row at row_index.
    • Subtract multiples of the row at row_index from the rows below, so that for any row below row_index, the entry at column $j$ is zero.

  • clear_above(self, row_index):

    • Let $j$ be the column index of the first nonzero entry in the row at row_index.
    • Subtract multiples of the row at row_index from the rows above, so that for any row above row_index, the entry at column $j$ is zero.

Watch out!

  • Remember that the first row/column of a matrix has the index 0, not 1.

  • If row1 is "below" row2 in a matrix, then row1 actually has a higher index than row2. This is because the 0 index corresponds to the very top row.

Example:

>>> A = Matrix(elements = [[0, 1, 2],
                           [3, 6, 9],
                           [2, 6, 8]])
>>> A.get_pivot_row(0)          (TEST ID: 1)
1
>>> A.swap_rows(0,1)
>>> A.show()          (TEST ID: 2)
[3, 6, 9]
[0, 1, 2]
[2, 6, 8]
>>> A.scale_row(0)
>>> A.show()          (TEST ID: 3)
[1, 2, 3]
[0, 1, 2]
[2, 6, 8]
>>> A.clear_below(0)
>>> A.show()          (TEST ID: 4)
[1, 2, 3]
[0, 1, 2]
[0, 2, 2]
>>> A.get_pivot_row(1)          (TEST ID: 5)
1
>>> A.scale_row(1)
>>> A.show()          (TEST ID: 6)
[1, 2, 3]
[0, 1, 2]
[0, 2, 2]
>>> A.clear_below(1)
>>> A.show()          (TEST ID: 7)
[1, 2, 3]
[0, 1, 2]
[0, 0, -2]
>>> A.get_pivot_row(2)          (TEST ID: 8)
2
>>> A.scale_row(2)
>>> A.show()          (TEST ID: 9)
[1, 2, 3]
[0, 1, 2]
[0, 0, 1]
>>> A.clear_above(2)
>>> A.show()          (TEST ID: 10)
[1, 2, 0]
[0, 1, 0]
[0, 0, 1]
>>> A.clear_above(1)
>>> A.show()          (TEST ID: 11)
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]

Problem 4-1

a) Implement a function labelEvenOdd that takes a list of numbers and labels each number as even or odd. Return a list comprehension so that the function takes up only two lines, as follows:

def labelEvenOdd(numbers):
   return [<your code here>]

Example:

>>> labelEvenOdd([1,2,3,5,8,11])
[(1,'odd'),(2,'even'),(3,'odd'),(5,'odd'),(8,'even'),(11,'odd')]

b) Rewrite the function below so that it does not use any dictionary comprehensions. Test your function on some input to make sure it gives the same output as the function below. (Note that you may have to scroll sideways to see the full function.)

def doSomething(sentence):
   return {word: sentence.replace(word, 'barnacle') for word in sentence.split(' ')}

Problem 4-2

Watch this video on Big-O notation. Then, provide the Big-O notation for the following computations:

  1. $A+B$ where $A,B \in \mathbb{R}^{n \times n}$
  2. $A-B$ where $A,B \in \mathbb{R}^{n \times n}$
  3. $cA$ where $A \in \mathbb{R}^{n \times n}$ and $c \in \mathbb{R}$
  4. $AB$ where $A,B \in \mathbb{R}^{n \times n}$
  5. $A^n$ where $A \in \mathbb{R}^{n \times n}$ (assume the computation involves repeated matrix multiplication)

Problem 4-3

Consider the sequence defined recursively as

$a_n = a_{n-1} - 2 a_{n-2}, a_0 = 0, a_1 = 1.$

a) Write a function firstNTerms that returns a list of the first $n$ terms of the sequence: $[a_0, a_1, a_2, \ldots, a_{n}]$

>>> firstNTerms(20)
[0, 1, 1, -1, -3, -1, 5, 7, -3, -17, -11, 23, 45, -1, -91, -89, 93, 271, 85, -457]

b) Watch this video on recursion. Then, write a function nthTerm that computes the $n$th term of the sequence, using recursion.

>>> nthTerm(30)
-24475

Problem 4-4

a) Refactor your Matrix class so that the code is super clean.

Be sure to name your variables well. For example, you shouldn't have an attribute A.matrix -- rather, it should be A.elements.

b) In your matrix class, rewrite __init__ to take only the following parameters, all of which are optional:

  • shape: a tuple containing the number of rows and columns of the matrix. By default, set shape equal to None.

  • fill: if a number, then set all the matrix elements equal to the value of fill. However, if fill is set to diag, then set the diagonal elements equal to 1 and all other elements equal to 0. By default, fill equal to 0.

  • elements: set the matrix elements equal to the corresponding values of the given array. By default, set elements equal to None.

Also, include the following attributes:

  • shape: returns the shape of the matrix as a tuple

  • elements: returns the matrix elements as an array

Example:

>>> A = Matrix(shape=(2,3))
>>> A.show()
[0, 0, 0]
[0, 0, 0]
>>> A.shape         (TEST ID: A1)
(2,3)
>>> A.elements         (TEST ID: A2)
[[0,0,0],[0,0,0]]
>>> B = Matrix(shape=(2,3),fill=1)
>>> B.show()         (TEST ID: A3)
[1, 1, 1]
[1, 1, 1]
>>> C = Matrix(shape=(2,3),fill='diag')
>>> C.show()         (TEST ID: A4)
[1, 0, 0]
[0, 1, 0]
>>> D = Matrix(elements=[[1,2,3],
                         [4,5,6]])
>>> D.show()         (TEST ID: A5)
[1, 2, 3]
[4, 5, 6]

c) Extend your Matrix class to overload equality and indexing.

Equality:

  • implement a method isEqual that checks if all the elements in the matrix are equal to their counterparts in another matrix.

  • overload the equality operator (==) using __eq__.

Indexing:

  • implement a method get that gets the matrix element at the desired index.

  • implement a method set that sets the matrix element at the desired index equal to some desired value.

  • overload the indexing operator ([]) using __getitem__ and __setitem__.

    • include row indexing and column indexing via the parameter : as indicated by the example. To check if the parameter param is equal to :, you can use isinstance(param, slice)

Example:

>>> A = Matrix(elements = [[1, 2],
                           [3, 4]])
>>> A[0,1]         (TEST ID: B1)
2
>>> A[0,1] = 5
>>> A[0,1]         (TEST ID: B2)
5
>>> A.show()
[1, 5]
[3, 4]
>>> B = Matrix(elements = [[1, 5]
                           [3, 4]])
>>> A == B         (TEST ID: B3)
True
>>> B[1,:]         (TEST ID: B4)
[3, 4]
>>> B[:,0]         (TEST ID: B5)
[1, 3]
>>> B[1,:] = [8, 9]         (TEST ID: B6)
>>> B.show()
[1, 5]
[8, 9]
>>> A == B         (TEST ID: B7)
False

Problem 3-1

a) Implement a stack. That is, create a class Stack which operates on a list using the following methods:

  • push: add a new item on top of the stack

  • pop: remove the top item from the stack

  • peek: return the top item without modifying the stack

Examples:

>>> s = Stack()
>>> s.push('a')
>>> s.push('b')
>>> s.push('c')
>>> s.show()`
['a', 'b', 'c']
>>> s.pop()
>>> s.show()
['a', 'b']
>>> s.peek()
'b'
>>> s.show()
['a', 'b']

b) Implement a queue. That is, create a class Queue which operates on a list using the methods enqueue and dequeue, and peek.

  • enqueue: add a new item to the back of the queue

  • dequeue: remove the item at the front of the queue

  • peek: return the item at the front without modifying the queue

Example:

>>> q = Queue()
>>> q.enqueue('a')
>>> q.enqueue('b')
>>> q.enqueue('c')
>>> q.show()
['c', 'b', 'a']
>>> q.dequeue()
>>> q.show()
['c', 'b']
>>> q.peek()
['b']
>>> q.show()
['c', 'b']

Problem 3-2

a) Write a function makeNested which takes a "flat" dictionary and converts it into a nested dictionary based on the key names.

Example:

>>> colors = {
  'animal_bumblebee': ['yellow', 'black'],
  'animal_elephant': ['gray'],
  'animal_fox': ['orange', 'white'],
  'food_apple': ['red', 'green', 'yellow'],
  'food_cheese': ['white', 'orange']
  }
>>> makeNested(colors)
{
  'animal': {
    'bumblebee': ['yellow', 'black'],
    'elephant': ['gray'],
    'fox': ['orange', 'white']
  },
  'food': {
    'apple': ['red', 'green', 'yellow'],
    'cheese': ['white', 'orange']
  }
}

b) Write a function flatten which takes a nested dictionary and converts it into a flat dictionary based on the key names.

Example:

>>> colors = {
  'animal': {
    'bumblebee': ['yellow', 'black'],
    'elephant': ['gray'],
    'fox': ['orange', 'white']
  },
  'food': {
    'apple': ['red', 'green', 'yellow'],
    'cheese': ['white', 'orange']
  }
}
>>> flatten(colors)
{
  'animal_bumblebee': ['yellow', 'black'],
  'animal_elephant': ['gray'],
  'animal_fox': ['orange', 'white'],
  'food_apple': ['red', 'green', 'yellow'],
  'food_cheese': ['white', 'orange']
}

Problem 3-3

In Assignment 2, you wrote a matrix class. Clean up your code for your matrix class and generalize it to $m \times n$ matrices.

Additionally,

  • implement the following attribute: shape

  • implement the following methods: max, min, transpose, exponent.

    • Remember that to take the exponent of a matrix, you need to repeatedly multiply the matrix by itself using matrix multiplication. (Don't just exponentiate each element separately.)

  • overload the following operators:

    • + (__add__) for matrix addition,
    • - (__sub__) for matrix subtraction,
    • * (__mul__) for scalar multiplication,
    • @ (__matmul__) for matrix multiplication

Examples:

>>> A = Matrix([[1, 1, 0],
                [2, -1, 0],
                [0, 0, 3]])
>>> A.shape()
(3, 3)
>>> A.max()
3
>>> A.min()
-1
>>> A.transpose().show()
[[1, 2, 0],
 [1, -1, 0],
 [0, 0, 3]]
>>> A.exponent(3).show()
[[3, 3, 0],
 [6, -3, 0],
 [0, 0, 27]]

Problem 3-4

In Assignment 1, we encountered the trivial encoding function which maps

  • ' ' $\rightarrow 0,$

  • 'a' $\rightarrow 1,$

  • 'b' $\rightarrow 2,$

and so on.

Using a linear encoding function $s(x) = 2x+3,$ the message 'a cat' can be encoded as follows:

  1. Original message: 'a cat'

  2. Trivial encoding: [1, 0, 3, 1, 20]

  3. Linear encoding: [5, 3, 9, 5, 43]

a) Create a function linearEncoding(string,a,b) which encodes a string using the scrambling function $s(x) = ax+b,$

Example:

>>> linearEncoding('a cat', 2, 3)
[5, 3, 9, 5, 43]

b) Decode the message

[377,
 717,
 71,
 513,
 105,
 921,
 581,
 547,
 547,
 105,
 377,
 717,
 241,
 71,
 105,
 547,
 71,
 377,
 547,
 717,
 751,
 683,
 785,
 513,
 241,
 547,
 751],

given that it was encoded with a linear encoding function $s(x) = ax+b$ where $a,b \in \{ 0, 1, 2, \ldots, 100 \}.$

Hint: try running through all combinations of $a$ and $b,$ checking if they correspond to some decoded message, and if so, then printing out that decoded message. Then, you can visually inspect the results to find the one that makes sense.

Problem 2-1

a) Write a function intersection that computes the intersection of two tuples.

Example:

  • intersection( (1,2,'a','b'), (2,3,'a') ) $\rightarrow$ (2,'a')

b) Write a function union that computes the union of two tuples.

Example:

  • union( (1,2,'a','b'), (2,3,'a') ) $\rightarrow$ (1,2,3,'a','b')

Problem 2-2

Write a function countCharacters that counts the number of each character in a string and returns the counts in a dictionary. Lowercase and uppercase letters should not be treated differently.

Example:

  • countCharacters('A cat!!!') $\rightarrow$ {'a': 2, 'c': 1, 't': 1, ' ': 1, '!': 3}

Problem 2-3

Create a Matrix class with the methods show, add, subtract, scale, and multiply for $2 \times 2$ matrices.

The input to a Matrix object is a multi-dimensional array (i.e. an array of arrays).

Examples:


A = Matrix([[1,3],[2,4]])

A.show()

[[ 1, 3 ],

  [ 2, 4 ]]


B = Matrix([[1,0],[2,-1]])

C = A.add(B)

C.show()

[[ 2, 3 ],

  [ 4, 3 ]]


D = A.subtract(B)

D.show()

[[ 0, 3 ],

  [ 0, 5 ]]


E = A.scale(2)

E.show()

[[ 2, 6 ],

  [ 4, 8 ]]


F = A.multiply(B)

E.show()

[[ 7, -3 ],

  [ 10, -4 ]]

Problem 1-1

a) Write a function letters2numbers that converts a string to a list of numbers, where space = 0, a = 1, b = 2, and so on.

Example:

  • letters2numbers('a cat') $\rightarrow$ [1,0,3,1,20]

b) Write a function numbers2letters that converts a list of numbers to the corresponding string.

Example:

  • numbers2letters([1,0,3,1,20]) $\rightarrow$ 'a cat'

Problem 1-2

Write a function isSymmetric that checks if a string reads the same forwards and backwards.

Examples:

  • isSymmetric('racecar') $\rightarrow$ True
  • isSymmetric('batman') $\rightarrow$ False

Problem 1-3

a) Write a function convertToBase10 that converts a number from base-2 to base-10.

Example:

  • convertToBase10(10011) $\rightarrow$ 19 because $1 \cdot 2^{4} + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 19$

b) Write a function convertToBase2 that converts a number from base-10 to base-2.

Example:

  • convertToBase2(19) $\rightarrow$ 10011

Problem 1-4

Write a function isPrime that checks if a number is prime.

Examples:

  • isPrime(59) $\rightarrow$ True
  • isPrime(51) $\rightarrow$ False

Hint: Check for divisibility within a for loop.