Homework 8

Due Date: Tuesday, October 31st at 11:59 PM

Problem 1: BST Traversal

This problem builds on Problem 1 of Homework 7 in which you wrote a binary search tree.

Part 1

As discussed in lecture, three different types to do a depth-first traversal are: preorder, inorder, and postorder. Here is a reference: Tree Traversal.

Write an iterator class called DFSTraversal with the following specifications:

• __init__(self, tree, traversalType): Constructor takes a BinaryTree object and one of the enums from DFSTraversalTypes

from enum import Enum

class DFSTraversalTypes(Enum):
    PREORDER = 1
    INORDER = 2
    POSTORDER = 3

• changeTraversalType(self, traversalType): Change the traversal type
• __iter__(self): This is the initialization of an iterator
• __next__(self): This is called in the iterator for getting the next value

Here's how you might use your DFSTraversal class:

input_array = [3, 9, 2, 11]
bt = BinaryTree()
for val in input_array:
    bt.insert(val)
traversal = DFSTraversal(bt, DFSTraversalTypes.INORDER)
for val in traversal:
    print(val)
2
3
9
11

Part 2

Put your BinaryTree class (from homework 7) and your DFSTraversal class (from Part 1 of this homework) in a file titled TreeTraversal.py.

Problem 2: Markov Chains

Markov Chains are widely used to model and predict discrete events. Underlying Markov chains are Markov processes which make the assumption that the outcome of a future event only depends on the event immediately preceeding it. In this exercise, we will be assuming that weather has Markov properties (e.g. today's weather is dependent only on yesterday's weather). We will use the Markov assumption to create a basic model for predicting weather.

To begin, let's categorize weather into 7 types: ['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing'].

In the weather.csv file accompanying this homework, each row corresponds to one type of weather (in the order given above) and each column is the probability of one type of weather occurring the following day (also in the order given above).

The $ij$th element is the probability that the $j$th weather type occurs after the $i$th weather type. So for example, (1,2) is the probability a cloudy day occurs after a sunny day.

Take a look at the data. Make sure you see how if the previous day was sunny, the following day will have a 0.4 probability of being sunny as well. If the previous day was raining (index $i = 3$), then the following day (index $j$) has a 0.05 probability of being windy ($j = 5$).

Part 1: Parse the .csv file into a Numpy array

Part 2: Create a class called Markov that has the following methods:

• load_data(array): loads the Numpy 2D array and stores it as a class variable.
• get_prob(previous_day, following_day): returns the probability of following_day weather given previous_day weather.

Note: previous_day and following_day should be passed in string form (e.g. "sunny"), as opposed to an index (e.g. 0).

Problem 3: Iterators

Iterators are a convenient way to walk along your Markov chain.

Part 1: Using your Markov class from Problem 3, write Markov as an iterator by implementing the __iter__() and __next__() methods.

Remember:

• __iter__() should return the iterator object and should be implicitly called when the loop begins
• The __next()__ method should return the next value.

Each 'next' step should be stochastic (i.e. randomly selected based on the relative probabilities of the following day weather types) and should return the next day's weather as a string (e.g. "sunny") rather than an index (e.g. 0).

Part 2: We want to predict what weather will be like in a week for 5 different cities.

Now that we have our Markov iterator, we can try to predict what the weather will be like in seven days from now.

Given each city's current weather in the dictionary city_weather (see below), simulate what the weather will be like in 7 days from now. Rather than just producing one prediction per city, simulate 100 such predictions per city and store the most commonly occuring prediction.

In your submission, print a dictionary city_weather_predictions that has each city as a key and the most commonly predicted weather as the corresponding value.

Note: Don't worry if your values don't seem to make intuitive sense. We made up the weather probabilities.