Computer Science 210
Data Structures

Fall 2018, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

You may work alone or with a partner on this assignment. However, in order to make sure you learn the material and are well-prepared for the exams, you should work through non-coding problems on your own before discussing them with your partner, should you choose to work with someone. Also, be sure every programming task is a team effort. In particular, the "you do these and I'll do these" approach is sure to leave you unprepared for the exams.

All GitHub repositories must be created with all group members having write access and all group member names specified in the README.md file by 4:00 PM, Friday, September 14, 2018. This applies to those who choose to work alone as well!

There is a significant amount of work to be done here, and you are sure to have questions. It will be difficult if not impossible to complete the assignment if you wait until the last minute. A slow and steady approach will be much more effective.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository for this problem set (ps1-yourgitname). One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

To have BlueJ recognize a clone of your repository as a BlueJ project, you will need to issue the command

  touch package.bluej

in Git Bash on Windows (or Terminal on a Mac) after you cd to the clone's directory.

Do not add this file, or other things like .class or .ctxt files to your repository.

Please answer the questions later in this assignment in the README.md file in your repository. Use Markdown to format neatly. Extensive formatting is not necessary.

Working with Git and GitHub

Git and GitHub are new to almost everyone in our class, so it will take a while to get used to how to use it correctly and most effectively. One thing you will want to start doing right away is to commit and push your changes frequently. Any time you have added even a small amount of code that bring you closer to a working solution, commit it. Any time you fix a problem, commit it. This allows you to back to see previous versions when something breaks. Further, by pushing your commits to GitHub, you have a backup of not only your latest version, but all of the previous versions you had committed along the way. To make this more effective, you should use meaningful commit messages. This acts as extra documentation of your development process, and allows you to find where and why particular things changed.

To encourage this, 5 points will be awarded on this problem set for frequency of commits and quality of commit messages. For the amount of work here, you should have a few dozen commits. Your messages should all be meaningful and descriptive, but rarely need to be more than a single sentence.

Array Practice Question

private void mystery() {
    int [] report = { 5, 4, 10, 4, 6, 3, 4 };
    int turn = 0;
    int shot = 0;
    int lastTotal = 0;

    while (shot < report.length && turn < 10) {
        int increment = report[shot] + report[shot+1];
        if (increment >= 10) {
            increment = increment + report[shot+2];
        }
        if (report[shot] < 10) {
            shot++;
        }
        lastTotal = lastTotal + increment;
        shot++;
        turn++;
        System.out.println(shot + " : " + lastTotal);
    }
}

Longest Words Practice Program

Here is one possible way to approach this problem incrementally.

1. Read in one word.
2. Read in words inside a loop (forever).
3. Read in words until someone enters the empty string ("") or "done".
4. Add a variable that keeps track of the number of words read in. Initialize it before your main loop, increment it in an appropriate place inside your main loop, and print it out after the loop.
5. Add a variable to keep track of the longest word. Update it in your main loop any time someone enters a word longer than the longest seen previously. Print it out at the end. Don't worry yet about handling ties.
6. Now worry about that case. When you detect a tie for the longest word, you should append the new word to the string containing the longest word(s). Note that we will now need to have a separate variable to remember the length of the longest word, since the string containing the longest word(s) may now contain multiple words.
7. Add a check at the end to make sure you only print the longest word(s) if at least one word was entered before "" or "done" was entered. If not, print a separate message to that effect.

Here is a sample run of my solution code:

Please enter the next word ("done" to end): this
Please enter the next word ("done" to end): one
Please enter the next word ("done" to end): is
Please enter the next word ("done" to end): so
Please enter the next word ("done" to end): much
Please enter the next word ("done" to end): fun
Please enter the next word ("done" to end): done
You entered 6 words.
The longest word(s): this, much

Vertex Closest Pairs

• Please use METAL's HDX to learn how this algorithm should work. Load up a small graph (under about 50 waypoints) and choose "Vertex Closest Pairs" as the algorithm. If you have the "Trace Pseudocode" box checked, you will see the algorithm in action.
• For this program you may (and should) borrow any useful code from our VertexSearch example from class. Only the search, which was looking for extreme points in the example, needs to be replaced.
• You will of course need to be able to compute the distance between two points. The LatLng class provided in the starter repository includes a method to do this. To use it to compute the distance between LatLng objects named w1 and w2, you can use either

    w1.distanceTo(w2);
  

  or

    w2.distanceTo(w1);
  

  You may either use the LatLng object in your Waypoint object, or adapt the distanceTo method to operate in your Waypoint class.

Lottery Simulator

The good folks in charge of the lottery were concerned that people who did well in math, and in particular computer scientists, were not playing their "Numbers Game" nearly often enough compared to the general public. This is the game where bettors pick a 3-digit number (000 to 999 in boring old base 10) to bet on, and if they win, they get a 500:1 payout. In an attempt to combat the dismal play rate among the state's best and brightest, they decided to introduce a variant of the game that would tempt this particular group with the numbers drawn in hexadecimal and payout rates that are powers of 2! What computer scientist will be able to resist that?!

In the new game, a bettor wagers on which random hexadecimal number between 00 and FF (0-255 for the uninitiated) will be selected that day. The payoff in our game is 128:1, i.e., for a $1 bet, a match will result in a $128 payout. A $2 bet will result in a $256 payout, etc..

Unfortunately, just like the standard "Numbers Game", this only sounds great to anyone who never passed elementary school math or to those who are looking for ways to get rid of some of their money. In reality, if you play this game long enough, you should expect to lose half of the money you've wagered.

Simple Simulation

Your first task is to develop a simple Java program, which you should call LotterySimulation.java, that simulates the above lottery game for a given number of lottery drawings, the number to bet on and the amount of a bet. Each of these three are read in from the keyboard. While you are encouraged to accept numbers to bet on in hexadecimal and report winning numbers in hexadecimal, this is optional. You may keep it simple and represent all numbers in decimal if you prefer.

For example, if the number of drawings to simulate is 8, and the number to bet on is 34, betting $2 per drawing, a series of 8 random numbers in the 00-FF (or, in base 10, 0-255) range should be drawn. For each number drawn, we keep track of the fact that another $2 has been bet. If the number came up as 34, we also record that the winnings for that drawing are $256, and that amount is added to the accumulated winnings. In the end, report the total amount that was bet and the total winnings, followed by a statement that reports either the net amount won, the net amount lost, or that the bettor broke even.

Adding File I/O

Once that is working, your next task is to get some of your input (the number to bet on and the amount of each bet) from a file, and to write all of the program's output (other than Terminal prompts) to a file.

Your program should prompt (at the Terminal) for the name of the input file that contains the number to bet and the amount of each bet, for the name of the file that should contain the simulation output, and for the number of drawings to simulate.

You will need to create your plain text input file in the same folder as your BlueJ project. In Windows, you can use Notepad. On a Mac, TextEdit is a good choice. The file should consist of only the 2 numbers: the number to bet on and the amount of the best, on a single line, separated by a space.

Processing Multiple Bets Per Drawing

Finally, extend your program so it reads an arbitrary number of numbers to bet on and amounts of those bets. Specify this in your input file by having the number of bets you wish to place on the first line. Let's call that "numBets". The file should then have numBets additional lines, with the number to bet on and a bet amount on each line. For each drawing, all numBets bets are placed and processed. (Hint: construct and populate either a pair of arrays for the numbers on which the player is betting and the amount being bet on each number, or a single array of objects that contain fields for both of these values.)

For reference, the starter repository includes a sample input file sampleinput.txt that is used by my solution code to generate (for example) the sample output file in sampleoutput.txt. And here is the keyboard/terminal interaction for my code to do this:

Please enter the name of the file with your lottery numbers and bets: sampleinput.txt
How many drawings would you like to simulate? 64
Please enter a file name for simulation results: sampleoutput.txt

Submitting

Your submission requires that your answers to the questions are in README.md and that all required code and other file deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

This assignment is worth 90 points, which are distributed as follows: