Due Date: December 14, 2018 [2018-12-14, Friday 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 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.
- 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
- 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.
- 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.
- HEARKEN BACK TO THOSE THRILLING DAYS OF YESTERYEAR, when all you had to worry about was implementing
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.
- Extra credit: Add a computerized player to the previous problem. Keep track of
both scores and declare a winner.