CMSI 3630: Homework Assignment #4
Due Date: Thursday of week 15
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, peripherals, and applications, and could make
code that is nicely formatted on *your* computer look
all over the map
on *my* computer or
in my editor. 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.
- On assignments 1, 2, and 3, WORK BY YOURSELF. On assignments
4 and 5, 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 individuals or 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
or individuals. Each person or 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].
- MAKE SURE TO INCLUDE ME IN YOUR REPO AS A CONTRIBUTOR so that I can upload your evaluations.
- 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 #4
Learning Outcomes: 1) implementing a sorting
algorithm and testing it; 2) using a binary tree to implement an encoding scheme; 3) code a game in Java
given a text description; 4) learning to use elements of the Java language to control the display of the
terminal window; 5) using different data structures in concert to solve a problem
This problem set has one problem from chapter 3, one problem from chapter 8, and one that I've found from a
completely different source. You will be working with sorting, binary trees, and representations of data
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:
- Another kind of simple sort is the odd-even sort. The idea is to repeatedly make two passes through an
array. On the first pass you look at all the pairs of items, a[j] and a[j+1], where j is odd (j = 1, 3, 5,
…). If their key values are out of order, you swap them. On the second pass you do the same for
all the even values (j = 2, 4, 6, …). You do these two passes repeatedly until the array is sorted.
Replace the bubbleSort()
method in bubbleSort.java
[Listing 3.1] with an
oddEvenSort()
method. Make sure it works for varying amounts of data. You'll need to figure
out how many times to do the two passes. The odd-even sort is actually useful in a multiprocessing
environment, in which a separate processor can operate on each odd pair simultaneously and then on each
even pair. Because the odd pairs are independent of each other, each pair can be checked – and swapped,
if necessary – by a different processor. This makes for a very fast sort.
- Read the section on Huffman Coding in chapter 8 of the Lafore book [it begins on page 415].
Then write a program to implement Huffman coding and decoding. Use a binary tree to facilitate the decoding
part. Your program should do the following:
- Accept a text message, possibly of more than one line. Handle both upper and lower case, plus
the space, newline, period and comma characters. That's up to 56 individual characters.
- Count the number of occurrences of each each character and save the values to an array.
- Put each of the characters and its count into a
quasi-priority
queue which has the lowest
character count at the left end and the highest count at the right end.
- Create a Huffman tree for this message using the process described on pp. 418 - 420. Following
the diagrams can be a big help to understanding how this works.
- Create the code table using the process described in the paragraph on page 421 under
Creating
the Huffman Code
.
- Encode your message into binary and display it on the screen.
- Using your Huffman Tree, decode the message from binary back to text and display it.
- If want to do so, the program could also display the Huffman tree after creating it. The ideas
in Programming Projects 8.1, 8.2, and 8.3 might prove helpful. You can use
String
variables to store binary numbers as arrangements of the characters 1 and 0. Don't worry about
doing actual bit manipulation unless you really want to.
- In the game
Simon
a four-colored disk can play a random sequence of tones and lights. Each color
on the disk is actually a button that can be pressed, with a light behind it. As the game makes a tone,
it also flashes the light with that tone. The game is for the user to press the buttons in the sequence
that is played by the game's controller. The sequence starts with a single light/tone, then increases
the number of lights/tones by adding one new trial to the sequence each time the player gets the entire
order correct. The game is over when the user makes a mistake in entering the sequence.
Using the letters R
for Red, G
for Green, Y
for Yellow, and B
for Blue,
implement the game. When the player makes a mistake in the sequence, ask if they would like to play
again. Implement the game as follows:
Be sure that the sequence is random. Make your program display the string each time, letter by letter,
with the letters separated by spaces. Try to make a short delay before each letter is displayed. Once
all the letters in the sequence are displayed wait one second and then make your program output backspace
characters to erase the displayed string. Then read the user's input and display each character as it is
entered. When the user makes an error output a mistake
message.