SchoolofContinuingStudiesEcolededucationpermanente CCCS 315: Data Structures and Algorithms Assignment \#2 Type of Assignment - Individual Work - Evaluated: This assignment is marked out of 100 points and is worth 10% of your final grade - Estimated Time: 120-500 minutes Description In this Assignment, you will study, Analyze (Big-O), and implement stacks and Priority Queues. Learning outcomes being met through this assessment - Recognize the usage of the stacks and Queues - Apply Big-O notation to analysis an algorithm - Identifying general sorting problems Steps to complete the assignment This assignment is designed similarly to a job interview. First, we will introduce a problem. You then need to apply critical thinking, design a solution, evaluate the solution (Big-O), then improve it if needed. Lastly, you will implement your solution. Part 1: Stacks We will implement a program that will use STACK to do the add, and multiplication. (Do not use the build in function or classes of Java or from the textbook). - You need to create Stack ADT, you may use linkedlist or array in the stack ADT. - Create a stack ADT that takes integer (INTGER Class), should include but not limited to these methods: Now we need to test it: - Create a main that ask user to input commands. - You need to use scanner class, - Need to make sure user knows when the program starts - Need to show available commands - Available commands from command line should be - For this part, you do not need to make sure user input the right value and types (no expectation or defensive coding is needed) - This is how your main should look like: McGill SchoolofContinuingStudiesEcolededucationpermanente Welcome to Stacks! List of command - Enter (a) to the above question and enter an integer you wish to add to your stack - Enter (+ or ") as an operator to be applied to the last two items added to your stack Enter (?) if you wish to see everything in your stack printed to the screen - Enter (p) if you wish to remove the last item - Enter (z) if you are done playing with stacks Would you like to command: a 22 Your value has been added to the stack! Would you like to command: a 23 Your value has been added to the stack! Would you like to command: a 19 Your value has been added to the stack! Would you like to command: a 15 Your value has been added to the stack! Would you like to command: A 34 Your value has been added to the stack! Would you like to command: Your stack items are: [34-15-19-23-22-] Would you like to command: You have added the last two items in your stack and pushed the total: 49 Would you like to command: Your stack items are: [49-19-23-22] Would you like to command: You have multiplied the last two items in your stack and pushed the total: 931 Would you like to command: Your stack items are: [931-23-22] Would you like to command: Thanks for playing Part 2: General Tree In this part, you have been asked to create a simple ADT tree. A company asked you to create a tree like the following: As you can see you need the following: - a Worker.java class, that only have name and salary attributes, you should have a constructor for this class. - You need a Binary TREE ADT class to hold the tree. - The Tree elements can have no children or many children (0,1,2,3,) - A binary tree ADT needs the following Here, You should have two workers as an input, worker A \& worker P. You shoud add the value of worker A to the right or left of worker P - You need to also write a method to print the tree (nothing fancy!!) You may do it in-order, preorder,... - Last part, create a main create the workers with their name and salary - Add them to the tree similar to image, remember to use setLeft and setRight - Lastly use your print and print the tree Part 3: Analysis 1. What is the time complexity of adding new element to a binary tree? 2. What if we used general tree ( 0 to many children), what would be the time complexity of adding new element? Would the number of children have any effect on it? 3. What is the worst case for adding a new element to a general tree? 4. Is there a relationship with the height of a tree and time complexity? Evaluation Criteria - Format Requirements ( 5%) - Comments and CamelCase is important - Student ID in each file - Java DocString - Style - Part 1(35%) - Correctness of Stack 25% - Tests 10% (The main method) - Part 2(50\%) Worker class 5% Method of binary tree 30% Method for visiting and printing the tree 10% Main class 5% - Analysis: 10% Each question is 2.5% Submitting your Work - You have to zip all the Java code for part 1 and part 2 (.java codes and if missing you will lose 85%) - PDF for last part (Part3)