Exam 2

You may use 3.5 contiguous hours on this exam. You may use any resources on this exam, except for other people. See also the course policies.

Put all your answers in one CodeSkulptor file. Use Python comments to include any answers that are not Python code. Use Python comments to clearly mark each problem number. Submit your CodeSkulptor URL on OWL-Space, under Exam 2.

To save you time, we have provided a template for you to start from.

Provide documentation strings for all functions.

As a matter of good style and conciseness, wherever reasonable you should use functions that have been defined previously on this assignment, on a previous assignment, or in class. You may use your own code or any code that we have provided as part of this course.

Regular Expressions (8 points total)

1. (8 points)

   Tony the Tiger asks you to write a regular expression that matches all instances of the word “great”, allowing for the “g” to be capitalized or not, and allowing for the “r” to be repeated any number of times.

   For example, it should match "Great" and "grrrrrrrreat".

   You do not need to worry about it matching only at the beginning or end of the string or a word boundary.

Markov Chains (25 points total)

2. (25 points)

   Our text-based Markov chains give us information about word sequences and their possible successors. For example, consider the following Markov chain with a sequence size of 3. For brevity, it uses one-letter words, and only the relevant part of the chain is shown.

   chain = {("a", "x", "y") : {"z" : .5, "f" : .5},
            ("b", "x", "y") : {"e" : .33, "z" : .34, "k" :  .33},
            ("c", "x", "y") : {"m" : 1},
            …}
   

   We can use Markov chains in reverse to get some information about possible precedessors. For example, the possible predecessors of ("x", "y", "z") are "a" and "b", but not "c".

   Write a function Markov_chain_predecessors(chain, word_seq) that takes a Markov chain and a word sequence and returns a set of the possible predecessors in this sense. Thus, Markov_chain_predecessors(chain, ("x", "y", "z")) should return set(["a", "b"]).

   Assume that the keys of the chain dictionary have the same length as word_seq.

Graphs (50 points total)

The graph representation we have been using is a version of an adjacency list — i.e., for each node, we keep a “list” (actually, a set) of its neighbors.

Adjacency list representation of the example graph:

• directed_graph_adjlist = {0: set([1,4]),
                            1: set([3]),
                            2: set([]),
                            3: set([0,1,4]),
                            4: set([0,3])}
  

3. (25 points)

   Write a function count_connections(graph, node) returns the number of nodes in the given graph that have an edge leading out of or into the given node, i.e., are connected to another node. Assume the graph is given as an adjacency list.

   For example, count_connections(directed_graph_adjlist, 0) should return 3, since node 0 is connected to nodes 1, 3, and 4.

   Hint: There are two basic strategies. One is to follow the definition and find which nodes are connected to another node, and then count them. Another is to count the nodes that are not connected to another node, and subtract that from the total number of nodes.

As mentioned previously, another representation is a 2D matrix of Booleans, also known as an adjacency matrix. In Python, we actually would use a list of lists of Booleans. There exists an edge from node i to node j if row i, column j == True, i.e., if graph[i][j] == True

Adjacency matrix representation of the example graph:

• # column             0      1      2      3      4
  directed_graph_adjmat = [[False, True,  False, False, True],  # row 0
                           [False, False, False, True,  False], # row 1
                           [False, False, False, False, False], # row 2
                           [True,  True,  False, False, True],  # row 3
                           [True,  False, False, True,  False]] # row 4
  

4. (10 points)

   Define the function empty_adj_matrix(num_nodes). It returns a list of num_nodes lists, each having num_nodes False's.

   For example, empty_adj_matrix(3) should return

   [[False, False, False],
    [False, False, False],
    [False, False, False]}
   

5. (15 points)

   Define the function directed_adj_matrix(graph_adjlist). Given a graph in adjacency list form, i.e., our usual dictionary-based form, it returns the corresponding adjacency matrix form. An example is shown above.

   Hint: Create an initial empty matrix, then loop over the input's nodes and their edges, changing each appropriate matrix value to True.

Classes and Objects (17 points total)

See the provided template code for the definition of a Marble class. Read the documentation strings for its methods to see what they do.

Correction to template:   Right after the __str__ method, please add the following method, which is needed for proper printing of objects contained within lists:

    def __repr__(self):
        return self.__str__()

6. (10 points)

   Write a function get_marbles(num_marbles) that returns a list of the given number of marbles. The color of each is randomly chosen from the equally likely options, "red", "blue", or "green".

   For example, get_marbles(3) could return ["blue marble", "blue marble", "green marble"].

   This description was erroneous and led to confusion. It should return a list of Marble objects, not strings. Otherwise, the next problem is impossible.

7. (7 points)

   Write a function rub_marbles(marbles) that “rubs” each marble in the provided list.