CMSI 3630: Homework Assignment #3
Due Date: Thursday of week 10
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 #3
Learning Outcomes: 1) Learning to output string
representations of objects; 2) extending a class; 3) expanding a class; 4) getting used to different
data structures and how they work; 5) getting familiar with the way data structures are used to make
other data structures
This problem set has two problems from chapter 4, and three from chapter 5. You will be working with
stacks, queues, and linked lists 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:
- Write a method for the
Queue
class in the queue.java
program (Listing 4.4)
that displays the contents of the queue. Note that first you will have to translate the program
from Java into Python. This is done often in the industry and is called porting
the code. Instead of a Java array you will use a Python list
data type to implement
the queue. Also note that writing the display method does not mean simply displaying the contents
of the underlying list. Because a queue structure is a FIFO structure, you should
show the queue contents from the first item inserted to the last, without indicating to the user
whether the sequence is broken by wrapping around the end of the list. Be careful that one item
and no items both display properly, no matter where front and rear are.
- EXTRA CREDIT: Create a
Deque
class based on the discussion of
deques (double-ended queues) in this chapter [CH 4]. It should include insertLeft()
,
insertRight()
, removeLeft()
, removeRight()
,
isEmpty()
, and isFull()
methods. It will need to support wraparound at
the end of the list, as queues do. You can use your Queue.py and QueueApp.py classes as a
starting point.
- A circular list is a linked list in which the last link points back to
the first link. There are many ways to design a circular list. Sometimes there is a pointer to
the start of the list. However, this makes the list less like a real circle and more like
an ordinary list that has its end attached to its beginning. Make a class for a singly linked
circular list that has no end and no beginning. The only access to the list is a single reference,
current
, that can point to any link on the list. This reference can move around the
list as needed. [See Programming Project 5.5 for a situation in which such a circular list is
ideal.] Your list should handle insertion
, searching
, and
deletion
. You may find it convenient if these operations take place one link
downstream of the link pointed to by current. [Because the upstream link is singly linked, you
can't get at it without going all the way around the circle.] You should also be able to display
the list [although you'll need to break the circle at some arbitrary point to print it on the
screen]. A step()
method that moves the current
reference along to the
next link might come in handy too.
- Implement a
stack
class based on the circular list of Programming Project 5.3. This
exercise is not too difficult. [However, implementing a queue can be harder, unless you make the
circular list doubly linked.]
- EXTRA CREDIT: The Josephus Problem is a famous mathematical puzzle that goes back
to ancient times. There are many stories to go with the puzzle. One is that Josephus was one of
a group of people who were about to be captured by the Romans. Rather than be enslaved, they
chose to commit suicide. They arranged themselves in a circle and, starting at a certain person,
counted off around the circle. Every nth person had to leave the circle and kill
themselves. Josephus decided he didn't want to die, so he arranged the rules so that he would
be the last person left. If there were [say] 20 people, and he was the seventh person from the
start of the circle, what number should he tell them to use for counting? The problem is made
more complicated because the circle shrinks as the counting continues.
Create an application that uses a circular linked list [like that in Programming Project 5.3] to
model this problem. Inputs are the number of people in the circle, the number used for counting
off, and the number of the person where counting starts [usually 1]. The output is the list of
persons being eliminated. When a person drops out of the circle, counting starts again from the
person who was on his left [assuming you go around clockwise].
There are actually two ways to count this off. One way is to count by the counter value and when
you land on a person at the counter value they are eleminated. Then you continue the count with
the person directly adjacent to the one who was eliminated. Here's an example. There are seven
people numbered 1 through 7, and you start at 1 and count off by threes. People will be eliminated
in the order 4, 7, 3, 1, 6, 2. Number 5 will be left.
The second way of counting is slightly different. You start at 1 and count by the counter value
and when you land on a person at the counter value they are eliminated. However, in this case
instead of continuing the count at the adjacent person, you consider that adjacent person to have
TAKEN THE PLACE of the one who was eliminated, and the count begins at the next person AFTER that
one. For example, in the same situation with seven people counting by threes, people will be
eliminated in the order 4, 1, 6, 5, 7, 3. Number 2 is the remaining person in this case.
If you have trouble understanding the difference, draw it out on a piece of paper or on a
whiteboard and count it off to see how they are different.
One other thing to consider is, the REAL answer to the problem is HOW NOT TO DIE, so given the
number of people AND YOUR LOCATION IN THE LINE, WHAT NUMBER do you
count by to ensure you are the last person left standing, so you can run away from the Romans and
not either die OR be a slave.