Due Date: December 14, 2018 [2018-12-14, Friday of finals week]

The following guidelines are expected for all homework submissions:

Problems for Assignment #5

This problem set has two problems from chapter 13, and two problems that I'll make up or determine from other sources. You will be working with hashes, graphs, and deciding when to use which data structure for this assignment. Your task is to complete the following problems using the programs specified in each one. As always, when you are finished and ready to submit your work, do so in your repo. Here are the problems:

  1. Modify the bfs.java program (Listing 13.2) to find the minimum spanning tree using a breadth-first search, rather than the depth-first search shown in mst.java (Listing 13.3). In main(), create a graph with 9 vertices and 12 edges, and find its minimum spanning tree.
  2. Modify the dfs.java program (Listing 13.1) to display a connectivity table for a directed graph, as described in the section Connectivity in Directed Graphs.
  3. HEARKEN BACK TO THOSE THRILLING DAYS OF YESTERYEAR, when all you had to worry about was implementing your BrobdingnagianInteger class. Let's finish the Dice Set problem by turning it into the full-fledged version of the dice game Yahtzee. Look up the rules and scoring on the Internet. You can implement the scoring any way you want, but you'll need to keep track from roll to roll. For this exercise, you only need to have one player who rolls the dice and gets a score. Since there are several different things to keep track of, you might be able to use one or two of the data structures we've studied: Queue, Deque, Priority Queue, Heap, Trees, &c.
  4. Extra credit: Add a computerized player to the previous problem. Keep track of both scores and declare a winner.