Intermediate Data Structures and Algoirthms Assignment 4

CMPT 280– Intermediate Data Structures and Algoirthms
Assignment 4

Total Marks: 52
1 Submission Instructions
• Assignments must be submitted using Moodle.
• Responses to written (non-programming) questions must be submitted in a PDF file, plain text file
(.txt), Rich Text file (.rtf), or MS Word’s .doc or .docx files. Digital images of handwritten pages
are also acceptable, provided that they are clearly legible.
• Programs must be written in Java.
• If you are using Eclipse (or similar development environment), do not submit the workspace (project).
Hand in only those files identified in Section 5. Export your .java source files from the workspace
and submit only the .java files.
• No late assignments will be accepted. See the course syllabus for the full late assignment policy for
this class.
2 Background
2.1 Restrictions of ADTs
We have seen how we can extend the functionality of a data structure that we already have implemented by creating a subclass using the extends keyword in Java. This allows us to take an existing
data structure class and add new functionality or modify existing ADT functionality (e.g. extension of
ArrayedTree280 to ArrayedHeap280), or to create a specialization of a more generic ADT (e.g. extension
of LinkedSimpleTree280<String to ExpressionTree).
Another ADT programming paradigm is restriction. Restriction is used to make an existing ADT
appear to be another ADT that has less functionality. Consider the following example. Suppose we need a
Stack ADT, but our data structure library, whatever it is, doesn’t have one. Further suppose that our data
structure library does have a list ADT which allows insertions and deletions from either end of the list.
Such a list has more than the necessary functionality of a stack. A stack is really just a list where we can
only add (push) and remove (pop) items at one end. We could just use the list itself as a stack, trusting
ourselves to only add and remove at one end. But this does not eliminate the possibility that the “stack”
could be used in ways that a stack should not be used when all we really need is a stack. Perhaps another
programmer comes along and doesn’t realize that you were using a list to get the behaviour of a stack and
does something very un-stack-like to the list without realizing it! What is really needed in this situation
is an ADT that has less functionality than the one we already have. We can’t get that by extending the
existing list ADT, but we can use the idea of restriction to make the list appear to the outside world as
nothing more than a stack!
The solution is to restrict the list class by writing a stack class which includes a list as an instance
variable, and methods that consist of only the interface for a stack. In other words, the list is the internal
data structure for the stack ADT, but the public operations for the ADT consist of only those for a stack.
These methods then “translate” the stack operations into the corresponding list operations, thus resulting
in a new class that looks exactly like a stack to the outside world, but implements the stack using a list.1
If you take a look at the Stack280 class in lib280, you’ll see that this is precisely what Stack280 does. Its
methods translate stack operations into operations on an internal list. Implementing this restriction is far
less work than writing a new linked or array-based stack class from scratch.
You will practice the concept of restriction in Question 1, below.
2.2 Hash Tables
Hash tables are an array-based container that work by using a hash function to convert an item to be stored
in the container into an integer value i (called the item’s hash), then the item is placed into an array at offset
i. A collision results if more than one item hashes to the same i. There are several methods of collision
resolution, one of which, called chaining, is to make each offset i of the array refer to a list, onto which all
elements that hash to offset i are placed.
lib280-asn4 contains an implementation of a hash table called KeyedChainedHashTable280. You will
use this class to solve a problem. KeyedChainedHashTable280 is an example of a type of data structure
called a keyed dictionary where each item is associated with a unique key. A keyed hash table computes
the hash of an item from only the item’s key, even though the item itself might contain other data fields.
Additional background and details about chained hash tables will be a component of this week’s tutorials.
1Some might call this a “wrapper” class because all it does is “wrap” one ADT in a more restrictive interface, and passes all the
work on to the inner ADT.
Page 2
3 Your Tasks
Question 1 ():
Recall from assignment 3 that a priority queue is a queue in which there is a numeric priority associated with every item in the queue. The item at the head of a priority queue is always the item with
highest priority. If we think about it, a heap actually has some the functionality the priority queue
ADT we specified in assignment 3. We can insert items into a heap which are kept organized by their
size (equivalent to enqueue!), and a heap always “dispenses” the largest item (equivalent to getting
the item at the front of the priority queue), and it allows us to delete the largest item (equivalent to
a dequeue!). The problem we would like to solve is to implement the priority queue ADT specification from assignment 3 by re-using as much of our existing code as we can. You can find the
priority queue specification in the appendix of this document.
In Assignment 3 we wrote a class ArrayedHeap280 (the instructor’s ArrayedHeap280 is included in
lib280-asn4), which has some of the functionality we need for a priority queue. But we cannot just
extend it because:
1. it has methods that are priority queue ADT doesn’t have, like itemExists;
2. it has methods that have the right functionality, but the wrong name, like deleteItem, which, for
our priority queue, is called deleteMax; and
3. it doesn’t have an iterator, which we need in order to determine the item with the smallest priority
(we need to be able to inspect all of the items in the heap to find the smallest one without moving
the internal cursor away from the root of the heap).
The solution will be as follows:
(a) (8 points) Write a class ArrayedBinaryTreeIterator280 which extends ArrayedBinaryTreePostion280
and implements the LinearIterator280 interface. This will be an iterator for an ArrayedBinaryTree. This class should be fairly easy to implement since you can pretty much copy all of the methods required by the LinearIterator280 interface from ArrayedBinaryTreeWithCursors280, with
perhaps some small modification. A mostly incomplete ArrayedBinaryTreeIterator280.java
file has been provided in the tree packagelib280-asn4 to start you off.
(b) (4 points) Extend ArrayedHeap280 to a class IterableArrayedHeap280 and write the following
methods in IterableArrayedHeap280:
• Add a deleteAtPosition method to delete a specific item in the heap (which need not
be the root). The item to be deleted should be specified by passing a reference to an
ArrayedBinaryTreeIterator280 object. The algorithm for this is just a slight modification of
the heap deletion algorithm where you swap the item at the end of the array with the item to
be deleted, and then swap it with its larger child until it is larger than both its children. This
method should be very similar to deleteItem from ArrayedHeap280.
• Add a method to IterableArrayedHeap280 called iterator which returns a new
ArrayedBinaryTreeIterator280 object for the tree.
A mostly incomplete IterableArrayedHeap280.java file has been provided in the tree package
lib280-asn4 to start you off.
(c) (14 points) Write a class PriorityQueue280 which is a restriction (as defined in 2.1) of IterableArrayedHeap280
which implements the priority queue ADT specification given in the Appendix of this document.
This means that PriorityQueue280 should have an IterableArrayedHeap280 as an instance variable, and it is in the heap that the queue items are stored.
In this way we can hide the functionality of IterableArrayedHeap280 that we don’t want exposed,
as well as add the functionality that it lacks.
Page 3
Some of the priority queue methods, like isFull and deleteMax, require identical behavior to
existing methods in the IterableArrayedHeap280 and can be written as a single call to a method
in the IterableArrayedHeap280 instance variable.
Other methods, like minItem and deleteAllMax, require functionality that doesn’t exist in
IterableArrayedHeap280 which will be up to you to implement – this will still be done by calling
methods of the internal heap, but a single call won’t be enough, for example, you may need to
iterate over the heap using its iterator.
I have provided you with a mostly incomplete PriorityQueue280.java file in the dispenser
package lib280-asn4 which contains a regression test for your convenience (you do not have to
write your own).
(d) (7 points) Comment all of the methods in all classes that you wrote by adding a javadoc comment
header, and inline comments where appropriate.
Implementation Hints
Since items in the IterableArrayedHeap280 must implement Comparable, your priority queue may
assume that the compareTo method of the items compares items based on their priority.
Page 4
Question 2 ():
Almost every modern video game in the roleplaying genre provides the player with a quest log which
is essentially a list of tasks that the player’s character has to perform to advance the story or to obtain
rewards.2
In this question we are going to create a data structure for a quest log based on a chained
hash table. For our purposes, a quest log entry will consist of the following pieces of information:
• Name of the quest.
• Name of the area of the world in which the quest takes place.
• Recommended minimum character level that should attempt the quest.
• Recommended maximum character level that should attempt the quest.
For the purposes identifying quests, quest log entries are keyed on the name of the quest. A class
called QuestLogEntry that can hold these pieces of information is provided. Notice how the key()
method of the QuestLogEntry class returns the name of the quest.
For this question, you are provided with a complete IntelliJ module (also compatible with Eclipse)
called QuestLog-Template in which you will modify one of the classes. It includes the QuestLogEntry
class and some .csv (comma-separated value) files which will be used as input data. You will need to
import the project into your IDE. The QuestLog-Template project requires access to the lib280-asn4
project, set this up as per the self-guided tutorial on the class website for setting up an IntelliJ module
to use lib280.
The entirety of your work will be to finish implementing methods in the QuestLog class provided in
the QuestLog-Template project, and to write a couple of interesting tests. Note that the QuestLog class
is a specialized extension of KeyedChainedHashTable280, so it is a chained hash table. Here is a list of
what you have to do:
(a) (3 points) Complete the implementation of the QuestLog.keys() method. This method must
return an array of the keys (i.e. the quest names) of each QuestLogEntry instance in the hash
table. The keys may appear in the returned array in any order.
(b) (3 points) Complete the implementation of the QuestLog.toString() method. This method
should return a printable string consisting of the complete contents of all of the QuestLogEntry
objects in the hash table in alphabetical order by the quest names, one per line. Here is an example
string returned by toString() from a quest log containing four entries:
Defeat Goliad : Candy Kingdom , Level Range : 20 -25
Locate the Lich ’ s Lair : Costal Wasteland , Level Range : 35 -40
Make an Amazing Sandwich : Finn ’s Treehouse , Level Range : 1 -5
Win Wizard Battle : Wizard Battle Arena , Level Range : 2 -4
Remember that the hash table makes no promises whatsoever about the ordering of the quest log
entries in the chains of the hash table. Hint: the keys() method from part (a) will be handy for
this method, as will knowing that Arrays.sort() can sort the elements of an array.
(c) (3 points) Complete the implementation of the QuestLog.obtainWithCount() method. This method
takes a quest name as input and returns a Pair280 object (found in lib280.base) which must
contain the QuestLogEntry object from the quest log which matches the given quest name (if
it exists) and the number of QuestLogEntry objects that were examined while searching for the
desired one. The latter number must be present whether the quest name was found in the quest
log or not.
2Back in the day, games didn’t have quest logs. If you wanted to remember what you were supposed to do, or something
that a character in the game said, you wrote it down with an ancient mystical device called a pencil. I recall having pages and
pages of notes from playing Ultima V which was a pretty epic game when it came out in 1988. I remember the incredible sense of
accomplishment I got from completing this game after six months of playing and making meticulous notes of conversations with
characters in the game and the directions I cobbled together for finding Lord British’s crown in the underworld. And in 1988 there
was no Internet to get hints from if you got stuck!
Page 5
Hints: A Pair280 object has two generic type parameters, the first of which specifies the type of
the first element of the pair, and the second of which specifies the type of the second element in
the pair. For example, if I wanted a pair consisting of an Integer and a Float I might write:
Pair280 < Integer , Float p = new Pair280 < Integer , Float ( 5 , 42.0 );
The components of the pair can be accessed using the firstItem() and secondItem() methods:
System . out . println ( p . firstItem ()); // prints the integer 5
System . out . println ( p . secondItem ()); // the floating point number 42.0
(d) (Points for part (d) are awarded in part (e)-1)
Now take a look at the main() program in QuestLog.java. As given, it already does the following
things:
1. Creates a new, empty QuestLog instance called hashQuestLog.
2. Creates a new, empty OrderedSimpleTree280 instance (a binary search tree) called treeQuestLog
that can hold items of type QuestLogEntry.
3. A .csv file containing the data for a number of QuestLogEntry objects is opened, and read
in, creating a QuestLogEntry instance for each quest, and adding each such instance to both
both the hashQuestLog and treeQuestLog data structures.
4. The complete contents of hashQuestLog and treeQuestLog are printed out using their respective toString() methods. You’ll know when your Questlog.toString() method from
part (b) is working when its output matches that of treeQuestLog.toStringInorder().
At the end of main() are two TODO markers. For the first one, you need to write code that calls
hashQuestLog.obtainWithCount() for each quest in the hashed quest log and determines the
average number of QuestLogEntry objects that were examined over all such calls.
Finally, for the second TODO marker, you have to do the same thing for treeQuestLog. You can
do this by calling the searchCount() method of treeQuestLog for each quest stored in the log.
Note that searchCount() requires that you pass in the actual QuestLogEntry object that you are
looking for rather than just the quest name (maybe you can obtain these from the hashed quest
log?). searchCount() returns the number of items that were examined while trying to position
the tree’s cursor at the given QuestLogEntry object.
Once you have computed the average number of QuestLogEntry objects examined for each of the
two data structures, print out the results. Something like this will do:
Avg . # of items examined per query in the hashed quest log with 4 entries : 1.25
Avg . # of items examined per query in the tree quest log with 4 entries : 2.0
(e) (10 points) Run your completed main() program for each of the .csv files provided in the project
(just change the filename in quotes that is passed to FileReader). Each .csv file contains in its
filename the number of quest entries in the file. For each .csv file, record the reported average
number of items examined per query in each data structure. In a text file called a4q2.txt (or
other acceptable file format) answer the following questions:
1. List the reported averages that you recorded for each .csv input file in a table that looks
something like this (filling in the rest of the table of course):
Filename Avg. Queries for hashQuestLog Avg. Queries for treeQuestLog
quests4.csv 1.25 2.0
quests16.csv
quests250.csv
quests1000.csv
quests100000.csv
2. If you had to choose a simple function (i.e. from the list of functions used in big-Oh notation)
to characterize the behaviour of the the average number of items examined per query for the
hashed quest log as the number of quests (n) in the log increases, what would it be?
Page 6
3. If you had to choose a simple function (i.e. from the list of functions used in big-Oh notation)
to characterize the behaviour of the the average number of items examined per query for the
tree quest log as the number of quests (n) in the log increases, what would it be?
4. If your primary use of the quest log was to display all of the quests in the log in alphabetical
order, would you prefer the hashed quest log or the tree quest log? Why?
5. If your primary use of the quest log was to periodically look up the details of specific quests
in no particular order, would you prefer the hashed quest log or the tree quest log? Why?
4 Files Provided
lib280-asn4: A copy of lib280 which includes:
solutions to assignment 3;
ArrayedBinaryTreeIterator280.java A mostly incomplete implementation of a linear iterator for
arrayed binary trees;
IterableArrayedHeap280.java A mostly incomplete implementation of a heap which provides
an iterator and allows any item to be deleted; and
PriorityQueue280.java: A mostly incomplete implementation of our priority queue ADT (in
the lib280 dispenser package).
QuestLog-Template.zip: A complete IntelliJ module (also compatible with Eclipse) containing everything
you need for Question 2.
5 What to Hand In
ArrayedBinaryTreeIterator280.java Your completed implementation of a linear iterator for arrayed binary
trees.
IterableArrayedHeap280.java Your completed implementation of a heap which provides an iterator and
allows any item to be deleted.
PriorityQueue280.java: Your completed implementation of the priority queue ADT.
QuestLog.java: Your completed quest log based on a hash table (parts (a), (b), and (c) of Q2), and completed additions to main() (part (d) of Q2).
a4q2.txt: Your answers to the questions posed in part (e) of Q2.
Page 7
Appendix – Priority Queue ADT
This is the Priority Queue ADT specification from Assignment 3, but with some methods left out. You
need to implement only the operations shown here.
Name: PriorityQueue<G
Sets: Q : set of priority queues containing elements from G.
G : set of items that can be in a priority queue.
B : {true, f alse}
N : set of positive integers.
N0 : set of non-negative integers.
Signatures: newPriorityQueue<G: N → Q
Q.insert(g): G 6→ Q
Q.isFull: → B
Q.isEmpty: → B
Q.count: → N0
Q.maxItem: 6→ G
Q.minItem: 6→ G
Q.deleteMax: 6→ Q
Q.deleteMin: 6→ Q
Q.deleteAllMax: 6→ Q
Preconditions: For all q ∈ Q, g ∈ G,
q.insert(g): queue is not full
q.maxItem: queue is not empty
q.minItem: queue is not empty
q.deleteMax: queue is not empty
q.deleteMin: queue is not empty
q.deleteAllMax: q must not be empty.
(Operations without preconditions are omitted)
Semantics: For all n ∈ N, g ∈ G, n ∈ N
newPriorityQueue<G(n): create a new queue with capacity n.
q.insert(g): insert item g into t in priority order with the highest number being the highest priority.
q.isFull: return true if t is full, f alse otherwise
q.isEmpty: return true if t is empty, f alse otherwise
q.count: obtain number of items in q
q.maxItem: return the largest (highest priority) item in q.
q.minItem: return the smallest (lowest priority) item in q.
q.deleteMax: remove the largest (highest priority) item in q from q.
q.deleteMin: remove the smallest (lowest priority) item in q from q.
q.deleteAllMax: all occurrences of the highest priority item are deleted from q.
Page 8