Description
1 Background
1.1 Arrayed Trees
Question 2 is about a bounded binary tree implementation. You should remember binary trees from CMPT 145 (or similar course) – they are trees in which each node has at most two children.
What you probably didn’t know is that binary trees can be stored using an array, rather than a linked structure. In such an array, the contents of the root node are stored in offset 1 of the array (offset 0 is unused). The contents of the children of the node whose contents are stored at offset i are stored at offset 2i and 2i + 1, respectively.
Thus, the left child of the root is at offset 2 × 1 = 2, the right child of the root is at offset 2 × 1 + 1 = 3, the left child of the left child of the root is at offset 2 × 2 = 4, and so on. The parent of the node whose contents are at offset i, is at offset i/2 (integer division). Thus, the parent of node at offset 7 is at offset 3.
Example 1 Here is the array representation of a tree storing the elements 1 through 10, in no particular order. The array – 7 1 4 3 9 10 2 8 5 6 is a representation of the tree: 7 1 3 8 5 9 6 4 10 2 Note that we do not allow any unused entries in the array between used ones. All the data items in the array are stored contiguously.
This means that we can represent only a particular subset of binary trees with this representation. Namely, it is the set of trees where all levels except possibly the last level are complete (full) and the nodes in the bottom level are all as far to the left as possible. You might be thinking that this is too restrictive and not very useful because we can’t represent all binary trees with this data structure.
However, as we will see on future assignments, this array-based tree data structure is highly useful and efficient as a basis for implementing certain other important data structures. Also note that if we read off the items from left to right in each level of the tree, starting from the top level, we get the items in the same order as they appear in the array.
1.2 m-ary Trees
An m-ary tree is one in which a node may have up to m children. Your lib280-asn3 library has a class called BasicMAryTree280 which implements an m-ary tree. It has some similarities with LinkedSimpleTree280 in that, like LinkedSimpleTree280, you have to build up larger trees from smaller trees, rather than inserting individual elements, because since m-ary trees have no defined structure in general and thus there is no obvious algorithm for automatically deciding where a new element should go. You will use this class in Question 3. More details and some examples on how to use this class are/were provided in Tutorial 3.
2 Your Tasks
Question 1 (11 points):
A priority queue is a queue where a numeric priority is associated with each element. Access to elements that have been inserted into the queue is limited to inspection and removal of the elements with smallest and largest priority only. A priority queue may have multiple items that are of equal priority. Give the ADT specification for a bounded priority queue using the specification method described in Topic 7 of the lecture notes. By “bounded”, it is meant that the priority queue has a maximum capacity specified when it is created, and it can never contain more than that number of items.
Your specification must specify the following operations: newPriorityQueue: make a new queue insert: inserts an element with a certain priority isEmpty: test if the queue is empty isFull: test if the queue is full maxItem: obtain the item in the queue with the highest priority minItem: obtain the item in the queue with the lowest priority deleteMax: remove from the queue the item with the highest priority deleteAllMax: remove from the queue all items that are tied for the highest priority deleteMin: remove from the queue the item with the lowest priority frequency: obtain the number of times a certain item occurs in the queue (with any priority)
Question 2 (20 points):
Your task is to write a Java class called ArrayedBinaryTreeWithCursors280 which extends and implements the abstract class ArrayedBinaryTree280 (provided in the lib280-asn3.tree package as part of lib280-asn3). Tutorial 3 also has more about array-based trees. Your Tasks Some of the work of implementing ArrayedBinaryTreeWithCursors280 has already been done, but there is more to do.
Firstly, there are several methods in ArrayedBinaryTreeWithCursors280 which are defined but not implemented. You must implement these methods. These methods can be easily identified by their “TODO” comments. Secondly, since ArrayedBinaryTreeWithCursors280 implements some other interfaces, there are several methods required by these interfaces that also need to be implemented but have not yet been finished. The method headers for these methods have already been generated but the method bodies are empty. The definitions of these methods in their respective interfaces document what these methods are supposed to do.
These methods can be identified by their “TODO” commands as well as the @Override directive above the method headers. Many of these methods are defined by LinearIterator280, which is inherited through Dict280. These are the same linear iterator methods that you wrote for LinkedList280 on assignment 1. The rest of these methods are defined by Cursor280. There is already a regression test included in ArrayedBinaryTreeWithCursors280. Your completed implementation of the arrayed binary tree must pass the given regression test. If all the regression tests are successful, the only output should be: Regression test complete. You may not modify any of the existing code in the provided ArrayedBinaryTreeWithCursors280.java file (including the regression test) but you can add to it. You may also not modify any other files within lib280-asn3. Implementation Notes • You don’t need to declare an array instance variable in ArrayedBinaryTreeWithCursors280 to hold the data items. There is already one inherited from ArrayedBinaryTree280. You should look at the other inherited instance variables too! • One of your first tasks will be to start implementing the insert method and decide where the new element should be inserted. If you think about it, there’s really only one place it can go… • The algorithm for deleting an element is to replace the element to be deleted by the right-most element in the bottom level of the tree, then delete the right-most element in the bottom level of the tree. • Not sure how a linear iterator works on a tree? If you think about it, there is only one reasonable way to define a linear ordering on the elements of an array-based binary tree. • Reminder: the items array (defined in the abstract class ArrayedBinaryTree280 ) represents the nodes of the tree. You are storing the contents of nodes in the array. There is no node class. It is very important that the contents of the root are stored in offset 1 and we don’t use offset 0 of the array, otherwise the given formulae for finding the child or parent of a node at offset i will not work correctly.
Question 3 (17 points):
In video games, especially those in the roleplaying genre, it is common that characters in the game are advanced in power through the use of a skill tree. Generally, a skill tree defines the prerequisite for the various skills that your character in the game might acquire. For example, in a hypothetical game, if the Shield Bash, Defensive Stance, and Shield Ally skills all require that your character first have the skill Shield Proficiency, then this might be represented by the following skill tree: Shield Proficiency, Cost: 1 Shield Bash, Cost: 2 Defensive Stance, Cost: 1 Shield Ally, Cost : 3 More formally, a skill in the skill tree can only be gained if the character first gains all of the skills which are ancestors of that skill in the tree.1
Your Tasks
Your task in this question is to write a class called SkillTree which extends BasicMAryTree280 (an m-ary tree of Skill objects; a complete Skill.java is provided). A template for the SkillTree class is provided. It contains a constructor and a couple of useful methods. You will add additional methods to this class in the following steps, which you should complete in order: (a) Write a main() method in the SkillTree class in which you construct your own skill tree for your own hypothetical video game. Your tree must contain at least 10 skills. However, for the sanity of everyone involved, try to keep it under 15 skills. Be creative! There is no reason why any two students should hand in exactly the same (or even very similar) skill trees, nor should you just duplicate the skill tree shown in the sample output. Print your tree to the console using the toStringByLevel() method inherited from BasicMAryTree280. (b) Write a method in the SkillTree class called skillDependencies which takes a skill name as input and returns an instance of LinkedList280 which contains all the of the skills which are prerequisites for obtaining the input skill (including the input skill itself!). A RuntimeException exception should be thrown if the tree does not contain the given skill. A good implementation approach for this method is to use a recursive traversal of the tree to find the named skill, and then add skills to the output list as the recursion unwinds. Tutorial 3 includes some discussion of recursive traversal of m-ary trees. Add to your main() program a few tests of this method, and print out the lists that is returned (you can use the list’s toString() method for this). Be sure to test the case where the named skill does not exist in the tree. (c) Write a method in the SkillTree class called skillTotalCost which takes a skill name as input and returns the total number of skill points that a player must invest to obtain the given skill. If the named skill is not in the skill tree, then the skillTotalCost method should throw a RuntimeException exception. Hint: this method is quite easy to implement if you make use of the previously implemented skillDependencies method. For example, in the above skill tree, if a character wants the Shield Ally skill they would need to spend 1 skill point to get Shield Proficiency, and then spend 3 skill points to get Shield Ally for an 1 In the video game world, the term “skill tree” sometimes refers to things that actually aren’t trees; a noteworthy example is the skill tree in the ARPG Path Of Exile, which, if you click the link, can see is clearly not a tree, even though they call it that. Here in question 3, we used the term “skill trees” to mean skill trees that are, in fact, actual trees. Page 5 overall investment of 1 + 3 = 4 points, so for the above tree, skillTotalCost(“Shield Ally”) should return 4. Note that the Skill object contains the cost of the skill. Add to your main() program a few tests of skillTotalCost, and print out the total costs returned. Be sure to test the case where the named skill does not exist in the tree. (d) Run your main() program. Cut and paste the console output to a text file and submit it with your assignment. See the sample output below. Sample Output Here is an example of what the output of your program might look like. Remember, you are expected to be creative in designing your skill tree, and your submission should not attempt to duplicate what you see here aside from the general formatting (the formatting can be the same, but the data should be different!). Note that the formatting of output of the skill tree contents is done by the toStringByLevel() method of BasicMAryTree280. ✞ ☎ My Skill Tree : 1: Slash , Cost : 1 2: Mighty Blow , Cost : 2 2: Shield Bash , Cost : 1 3: Shield Charge , Cost : 2 3: Parry , Cost : 2 4: Shield Wall , Cost : 4 4: – 4: – 4: – 3: – 3: – 2: Cleave , Cost : 2 3: Whirlwind , Cost : 3 4: Berzerk , Cost : 5 4: – 4: – 4: – 3: – 3: – 3: – 2: Mobility , Cost : 1 Dependencies for Shield Wall : Slash , Cost : 1 , Shield Bash , Cost : 1 , Parry , Cost : 2 , Shield Wall , Cost : 4 , Dependencies for Mobility : Slash , Cost : 1 , Mobility , Cost : 1 , Dependencies for Slash : Slash , Cost : 1 , Dependencies for FakeSkill : FakeSkill not found . To get Whirlwind you must invest 6 points . To get Mighty Blow you must invest 3 points . To get Slash you must invest 1 points . FakeSkill not found . ✝ ✆ Page 6 3 Files Provided lib280-asn3: A copy of lib280 which includes the ArrayedBinaryTree280 class needed for Question 1, a partially complete ArrayedBinaryTreeWithCursors280 for Question 1, and the BasicMAryTree280 class which is needed for Question 2. Skill.java : A complete implementation of the Skill class needed for Question 2. SkillTree.java : A template for your implementation of the SkillTree class in Question 2.
4 What to Hand
In You must submit a .ZIP file containing following files: Assignment2.doc/docx/rtf/pdf/txt – your answer to Question 1. Acceptable file formats are Word (.doc or .docx), PDF (.pdf), rich text (.rtf), or plain text (.txt). Digital images of handwritten pages are also acceptable, provided that they are clearly legible and that they are in JPEG (.jpg or .jpeg) or PNG (.png) format. Other image formats are not accepted and will receive a grade of zero. ArrayedBinaryTreeWithCursors280.java – Your completed class for Question 2. SkillTree.java – Your completed implementation of the skill tree and associated tests. q3-output.txt – The console output from your SkillTree::main() test program to Question 3.
