1 Fixes
Please note some changes in the output format for Trie.
Allowed imports: List, Stack and Queue.
Code download from here - Download code
Brief description:
In this assignment you need to work with Tries, Red-Black trees and Priority queues. There will be four components of the assignment. The first three will check tries, red-black trees and priority queues independently. The last part of the assignment will be a combination of all the previous components.
2 General instructions
The grading will be done automatically. To ensure a smooth process, an interface will be provided to you, which you are NOT suppose to change. Your solution classes will implement these interfaces.
For each of the component, you will be given and input file, which will contain the commands that your code must execute. As per the command, the program will produce the output, which will be compared against an expected output for grading. Please ensure that you follow the proper formatting criteria, failing to do so will results in a penalty or no marks for that particular component.
2.1 Code skeleton
You are provided with the skeleton of the code. This contains the interfaces and other relevant information. Your task is to implement these functions. The code also contains driver code for all the components of assignment. These will be used to check the correctness of the code. Please DO NOT modify the interface and the driver code. You are free to change and implement other parts in any way you like.
Code can be downloaded from here: Download code
2.1.1 Building and Running
In the code, within the src folder, you can use the following commands to check your code.
make
This will check all the components. Components can also be checked independently:
make trie make rbtree make pq make pm
for Trie, Red-Black tree, Priority-Queue and Project-Management (4th component) respectively.
3 Trie [1 Mark]
Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length) [3].
In this part of the assignment, you need to implement a Trie data structure. To make things interesting, you will be implementing a telephone directory using Tries. Name of a person will be the key (assuming all names are unique). Associate with every name will be a Person object.
package Trie; public class Person { public Person(String name, String phone_number) { } public String getName() { return ""; } }
Listing 1: Person class.
3.1 Interface
You version of Trie must implement the TrieInterface as shown in Listing 2 and is also present in the code provided.
Code:
package Trie; /** * DO NOT EDIT THIS FILE. */ public interface TrieInterface<T> { /** * @param word Word to be input in the Trie * @param value Associated value of the word * @return Success or failure */ boolean insert(String word, T value); /** * @param word Search for this word, Case-Sensitive * @return Returns the Trienode associated if the word is found else NULL */ TrieNode<T> search(String word); /** * * @param prefix Search a particular prefix * @return Returns the last Trienode associated with the prefix. Eg: If PARIS and PARROT is in the Tries, searching for PAR, returns the trienode of first R */ TrieNode<T> startsWith(String prefix); /** * * @param trieNode Prints all the possible word possible from this Trienode * Eg: PAR and PARIS, printTrie(startWith("PAR")) should print PARIS and PARROT i.e all the words with suffix PAR */ void printTrie(TrieNode trieNode); /** * * @param word Delete a word from the Trie * @return Success or Failure */ boolean delete(String word); /** * Print the complete Trie */ void print(); /** * Print a specific level of the Trie. * * @param level */ void printLevel(int level); }
Listing 2: Interface specifications for Trie.
3.2 Input specifications
Commands:
1.INSERT: It takes a Person name and phone number (in next line) as input and inserts that into the trie.
2.DELETE: It takes a String as an input and deletes that from the trie.
3.SEARCH: It takes a String as input and returns true or false, based on whether that word is present in trie or now.
4.MATCH: It takes a String as an input, and return all words where the prefix is the entered String. Printing is done in a lexicographical order.
5.PRINTLEVEL: Print the specified level in lexicographical order separated by comma and DO NOT print spaces.
6.PRINT: Print all the LEVELS of the trie. The print format same as that of PRINTLEVEL.
Sample input file:
Output:
4 Red-Black Tree [1 Mark]
In this part you need to implement a Red-Black tree. A tutorial on Red-Black tree can be found here [2]. In this part, the basic operations on a Red-Black tree, insert and search will be tested. Note: you are not required to implement the delete feature. You will be given an input file, whose format is listed in Section 4.2. A sample output for the input command given in Section 4.2 is shown in 7
In this case also you will implement a telephone directory, with an extra feature that a person can have multiple numbers.
4.1 Specifications
You Red-Black tree, must implement the interface as shown in listing 5.
Code:
package RedBlack; public interface RBTreeInterface<T extends Comparable, E> { /** * Insert and element using the "key" as the key and the corresponding value. * Please note that value is a generic type and it can be anything. * * @param key * @param value */ void insert(T key, E value); /** * Search using the key. * * @param key * @return */ RedBlackNode<T, E> search(T key); }
Listing 5: Input for Trie.
Things to keep in mind:
All the items insert into the RB-Tree has a key and the corresponding value with it. In this version of Red-Black tree, a key can have multiple items. If we are trying to insert an element with a key which is already present in the tree, the value will get attached /appended to that key. This can be seen in the Listing 6.
Output:
5 Priority queues [1 Mark]
In this part you will be working with a priority queue. Specifically, you will be implementing a max-heap which is an implementation of priority queue.
You will need to implement a marks scoring system using Max Heap. This will contains, students name and their corresponding marks. The max-heap will use the marks to arrange the students, i.e. the student with the highest marks will be on the top.
5.1 Specifications
Code:
package PriorityQueue; /** * DO NOT EDIT * * @param <T> */ public interface PriorityQueueInterface<T extends Comparable> { /** * @param element Insert and element to the Priority Queue */ void insert(T element); /** * Extract the current maximum element from the Queue (assuming a max heap). * * @return */ T extractMax(); }
Listing 8: Interface for PriorityQueue.
Commands
1.INSERT
name marks: Insert the student in the tree. Student name and marks are give in the next line. Students name will be unique.
2.EXTRACTMAX
Extract the student with highest marks and print it. Extract operations also removes this from the max-heap.
Sample input (ignore the line numbers):
If you like Codersarts blog and looking for Assignment help,Project help, Programming tutors help and suggestion you can send mail at contact@codersarts.com.
Please write your suggestion in comment section below if you find anything incorrect in this blog post
Comentarios