Assignment Computer Science 1 Objectives In this assignment you will gain experience in manipulating two essential ADT: stacks and queues either. As part of the learning experience, you will also

implement the basic opera- tions on these ADT as well as several algorithms to use these ADT in various applications. You will need to provide some analysis of the time complexity of these algorithms. 2 Background Stacks and queues are fundamental data structures in computer science that play important roles in various algorithms and applications which provide efficient ways to store and manage data based on specific principles. Stack: LIFO (Last-In-First-Out) A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It can be visualized as a stack of objects, where the last object placed on top is the first one to be removed. Think of a real-life stack of plates, where you can only remove the topmost plate. Queue: FIFO (First-In-First-Out) A queue is another linear data structure that follows the First-In-First-Out (FIFO) prin- ciple. It can be visualized as a line of people waiting for a service, where the person who arrives first is served first. In a queue, elements are added to the rear and removed from the front. 3 Questions You need to solve the following problems. 1 3.1 Exercise 1 Bonus - 1. Given a directed graph and two vertices source and destination, determine if the destination vertex is reachable from the source vertex. The solution should return true if a path exists from the source vertex to the destination vertex, false otherwise. Note: Edge (x, y) represents an edge from x to y. = Follow the specific input-output format: Input: Graph [edges = [(0, 6), (6, 7), (7, 3), (3, 5), (4, 6)], n = 6], src = 4, dest 5 Output: true Explanation: There exists a path [4 6 -7. 3 5] from vertex 4 to vertex 5. = Input: Graph [edges = [(0, 6), (6, 7), (7, 3), (3, 5), (4, 6)], n = 6], src= 5, dest = 0 Output: false Explanation: There is no path from vertex 5 to any other vertex. - 2. Given a directed graph, two vertices source and destination, and a positive number m, find the total number of routes to reach the destination vertex from the source vertex with exactly m edges. Note: Edge (x, y) represents an edge from x to y. Follow the specific input-output format: Input: Graph [edges = [(0, 6), (0, 1), (1, 6), (1, 9), (1, 5), (5, 3), (3, 4), (9, 5), (9, 3), (9, 4), (6, 9), (7, 6), (7, 1)], n=8], src = 0, dest 3, m = 4 Output: 3 = Explanation: The graph has 3 routes from source 0 to destination 3 with 4 edges. 0-1-9 5 3 0 1 6 9-3 0 6 9 3 3.2 Exercise 2 Refer to the figure below to write a Java program to do following¹: 1. Generate a similar queue as the initial queue of the figure above. Your task is to generate an updated queue reversing the initial queue where you should append the last value of the initial queue to the first index of the updated queue, the 2nd last last value of the initial queue to the second index of the updated queue and so on. For example, in the figure, the last value of the initial queue is 25 and the second last value is 5. In the updated queue, 25 comes in the first index of the queue and 5 in the second index. 2. Consider the updated queue. Your task is to divide the value of each index with its following index. If the value of the previous index < then the value of following index, divide the value of the following index with the previous index. Generate a new queue with the resultant values. Consider the whole number if the result is decimal, i.e. ¹Hint: An array-based implementation is recommended here. 2 Initial Queue 3 15 0 18 4 10 2 525 Step - 1 25 5 2 10 4 18 0 15 3 Updated Queue Step - 2 Updated Queue (after division) 5 2 5 2 4 0 0 Step - 3 0 2 3 4 5 10 10 3 Updated Queue (after sorting) Figure 1: Queue = 25, the value of the 2nd index = 5, result = 25/5 = integer division. For example, in the previously updated queue, the value of the 1st index 5. Therefore, in the new updated queue (after division) the value of the first index will be 5. Repeat the same for the value of the 2nd index 5, value of the 3rd index = 2, result = 5/2 2. Therefore, in the new updated queue the value of the 2nd index is 2. Similarly, the value of the 3rd index 2, value of the 4th index And so on. = = == = 10, as 2 < 10, result = 10/2 = 5. 3. Sort the updated queue (after division) in descending order. If any value appears more than once (duplicate), just append once in the queue. 3.3 You must follow the specific output format: Step-1: Initial queue[3,15,0,18,4,10,2,5,25] - Updated queue [25,5,2,10,4,18,0,15,3] Step-2: Updated queue - [25,5,2,10,4,18,0,15,3] Updated queue (after division) - [5,2,5,2,4,0,0,5,3] Step-3: Updated queue (after division) - [5,2,5,2,4,0,0,5,3] Updated queue (after sorting) - [0,2,3,4,5] Exercise 3 Write a Java program to reverse a stack using the queue data structure. From the reversed stack, find the unique elements and generate a new queue with the elements following FIFO 3 order. Hints to reverse a stack using queue data structure: 1. Pop elements one by one from the stack. 2. Enqueue every popped element into the queue. 3. Do it till the stack is empty. 4. Then, Dequeue elements one by one from the queue. 5. Push every dequeued element into the stack. 6. Do it till the queue is empty. 7. The stack is now reversed. You may follow the pseudo-code for reversing the stack: ReverseStack(stack, queue): // Step 1: Pop elements from the stack and enqueue into the queue while stack is not empty: element = Pop(stack) Enqueue(queue, element) // Step 2: Dequeue elements from the queue and push into the stack while queue is not empty: element Dequeue(queue) Push(stack, element) // The stack is now reversed Use the following algorithm to solve the problem. Provide a brief analysis of the com- plexity for it and justify its Big-Oh notation. Generate UniqueQueue(stack) Input: A stack of elements Output: A queue containing the unique elements in FIFO order 1. Initialize an empty set called uniqueSet to track unique elements. 2. Initialize an empty queue called uniqueQueue. 3. Iterate over the elements in the stack, one by one. 4. For each element in the stack, do the following Check if the element is already present in uniqueSet. If the element is not present in uniqueSet, add it to uniqueSet. Enqueue the element into uniqueQueue. 4 5. Return uniqueQueue, which will contain the unique elements in FIFO order. You must follow the specific output format: Input Stack: [2-9-3 1 8 _ - Output Reversed Stack: [3 - 5 Output Queue with unique 3.4 Exercise 4 - - 9-0-7-8-4 - 5 - 3] 4 - 8-7-0-9-8-1-3-9-2] values: [3 - 5 - 4 - 8-7-0-9-1 -2] Suppose you are shopping to buy shoes, and you have a shopping cart. You can add or remove items from your cart using the concept of a stack, based on the following preferences: You have a dictionary containing tuples for each shoe item. Each tuple consists of three elements: -x: The brand name of the shoe. -y: The original price of the shoe. - z: The discount on the original price of the shoe. Here is the dictionary of shoe items: (‘Nike', 450, 25), ('Adidas', 400, 10), ('Puma', 600, 30), ('Sorel', 360, 0), ('Aldo', 680, 15), ('Skechers', 380, 0) In this dictionary, you can find information about various shoe brands, their original prices, and the discounts available. Each entry in the dictionary represents one shoe item. Using a stack, you can add or remove items to your shopping cart. The following algorithm can be used to solve the problem. Provide a brief analysis of the complexity for it and justify its Big-Oh notation. 1. Start by adding the first item from the dictionary to your shopping cart. 2. Calculate the price of the first item after any applicable discount. Let's call this calculated price "prev". 3. For each remaining item in the dictionary, repeat steps 4-7. 4. Move on to the next item in the dictionary. 5. Calculate the price of the new item after any discount and call this calculated price "next". 6. Compare the calculated prices "prev" and "next” to determine which item has a lower price. 7. If "next" is lower than "prev", update the existing item in your shopping cart with the new item that has the lower price. Otherwise, keep the existing item in your shopping cart as it already has the lower price. 5