Due Date: Wednesday of finals week]

The following guidelines are expected for all homework submissions:

• All homework must be typed. Homework which is not typed will be returned ungraded and will be subject to the late homework guidelines as set out on the syllabus page. PLEASE DO NOT scribble something on lined paper and rip it out of your spiral notebook — hanging chads went out with the presidential election in 2000.
• I don't care too much about what font you use or how large your margins are; however, you might want to check out a monospaced font for typing code, as it will be easy to see the indentations.
• Speaking of indenting, PLEASE DON'T USE TABS TO INDENT YOUR CODE. Tabs can often get interpreted differently by different computers and applications, and could make code that is nicely formatted on your computer look all over the map on my computer or printer. USE SPACES INSTEAD. You can set up almost every modern text editor to insert spaces whenever you press the TAB key, or you can simply pound the spacebar.
• WORK WITH A PARTNER. I can't stress this enough; part of this policy is don't split up the work – WORK TOGETHER on the assignment. This activity mimics an industry code development model called pair programming which is part of the Extreme Programming software development method. Feel free to collaborate in your pairs as much as you want, doing the entire assignment together.
• DO NOT share your work between groups. Doing so will count as plagiarism. If you wish to discuss solutions with another group over coffee in the Lair, that's fine as long as it is kept at the conceptual level and you don't share your code between groups. Each group needs to turn in its own version of the solutions.
• You only need to turn in ONE COPY per group.
• MAKE SURE YOUR GITHUB REPO IS PRIVATE [for reasons explained on the syllabus page and in class].
• Submit your homework through GitHub, in your repository, to which I must be a contributor or have otherwise been allowed access. I cannot evaluate what I cannot see!

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.