Data Structures Assignment

Instructions

Below are a set of 10 tasks. University level students are required to complete all 10 tasks. College level students are required to complete tasks 2, 4, 6, 7, 10.

Marks

Communication marks are given for full JavaDoc on all methods/classes. This includes:

• Descriptions
• Parameter definitions
• Return value definitions

Knowledge marks are given for (but not limited to):

• Using the most appropriate data structure for the given task

Thinking marks are given for (but not limited to):

• Full black/whitebox test for 1 of the tasks

Application marks are given for (but not limited to):

• Completing the assigned tasks

Tasks

1. Create a Stack and a Queue using a Linked List as a backing data structure. Call these classes LinkedStack and LinkedQueue. Implement the ISimpleStack and ISimpleQueue interfaces provided in class.
2. Create a "Not-So-Urban Dictionary" by loading a file of mundane words and their definitions. Allow users to display the list of all words and select a word to define. The definition file can be found HERE.
   • After loading, there should be no duplicates in the definitions.
3. Add a method to the SimpleTree created in class that will perform a depth first and another that will perform a breadth first search for an element. Test your methods using Strings.
   • Method Signature 1: public boolean depthFirstSearch(String element)
   • Method Signature 2: public boolean breadthFirstSearch(String element)
4. Create a List class called SortedList that sorts items as they are inserted.
   • This does NOT mean sort them after inserting them, it means insert them in sorted order.
   • Also, do NOT use an ArrayList as your backing data structure.
5. Write a function that converts an integer into its binary value using a Stack.
   • Method Signature: public static String toBoolean(int n)
6. Using a Queue, write a function that calculates the first n terms in the Fibonacci sequence and returns them in a comma separated string.
   • Method Signature: public static String fib(int n)
7. Create a method that checks whether an input string contains balanced brackets. I.e. "[()]{}{[()()]()} " is balanced, "[(])" is not.
   • Method Signature: public static boolean isBalanced(String input)
8. Create a method with signature public static String infixToPostfix(String expression) that converts mathematical expressions in infix notation into postfix notation. The basic algorithm for this conversion is as follows:
   1. Create an empty stack for keeping operators. Create an empty string for output.
   2. Split the input string into tokens.
   3. Scan the token list from left to right.
      • If the token is an operand, append it to the end of the output string, separated by a space.
      • If the token is a left parenthesis, push it on the operator stack.
      • If the token is a right parenthesis, pop the operator stack until the corresponding left parenthesis is removed. Append each operator to the end of the output list.
      • If the token is an operator, *, /, +, or -, push it on the operator stack. However, first remove any operators already on the operator stack that have higher or equal precedence and append them to the output string, separated by spaces.
   4. When the input expression has been completely processed, check the operator stack. Any operators still on the stack can be removed and appended to the end of the output string separated by a space.
9. Create a method with signature private static Double postfixCalculator(String expression) that evaluates a postfix notation expression and returns a double value of the final calculation of that expression.
10. Edit the Linked List implementation created during class to add the following methods/functionality:
    • Turn the linked list into a doubly-linked list where the list can be traversed forward AND backward.
    • SimpleLinkedList<E> deleteRange(int i, int n) - Deletes n items starting at index i, inclusive. Returns the items that have been deleted in a new linked list
    • void insertAll(int i, SimpleLinkedList<E> e) - Inserts all the elements in the e linked list into the current list starting at index i.
    • void reverse() - Reverses the linked list, in place.