Data Structures and Algorithms Assignment 2 Solution

This programming assignment will test your knowledge and your implementation abilities of what you have learned in the Lists, Stacks, and Queues parts of the class.




This homework must be completed individually. Discussion about algorithms and data structures are allowed but group work is not. Coming up with the same algorithm and talking about the ways of implementation leads to very similar code which is treated as plagiarism! Discuss carefully. Any academic dishonesty, which includes taking someone else’s code or having another person doing the assignment for you will not be tolerated. By submitting your assignment, you agree to abide by the Koc University codes of conduct.




Description




This assignment is designed to assess your understanding of Arrays, Linked Lists, Stacks, and Queues and your implementation abilities. This assignment requires you to implement the Double Ended Queue




Deque data structure. Deque, which is pronounced as \deck", is a generalization of the queue data structure that supports inserting and removing elements from either the front or the back of the data structure. The assignment will have two phases; (1) implementation of the data structures and (2) application of the data structures.



Part I




In the rst part of the assignment, you will implement the deque ADT both using Arrays and Doubly Linked Lists. You will be given a deque interface and two starter les. These les have comments for your convenience. You are also given another interface for a simple container. This interface speci es three operations; (1) push, (2) pop and (3) peek. The details are in the comments but you can gure out that these methods resemble stack and queue operations. You are asked develop a stack class and a queue class which implement this interface. However, you are required to use a deque for this; by wrapping the dequeue operations to achieve the desired input-output behavior. The type of deque will be given as a generic. See the relevant les and the main le for how they are used.




The code has comments about the assignment. Majority of what you need to do is actually in these comments so make sure you read them carefully. The descriptions for the provided les are below. Bold ones are the ones you need to modify and they are placed under the code folder, with the rest under given.




iDeque.java: This is the interface that shows you the operations of the Deque ADT. You do not need to modify this le. The ArrayDeque and LLDeque classes implements this interface. Make sure you pay attention to the comments.




ArrayDeque.java: You need to code the ArrayDeque class that implements the iDeque interface using a Dynamic Array in this le. Follow the instructions given in the code. This must be a circular implementation.




LLDeque.java: You need to code the LLDeque class that implements the iDeque interface using a Doubly Linked Lists in this le. Follow the instructions given in the code.




iSimpleContainer.java: This interface has three simple methods of a container that allow manip-ulation from a \single point". You do not need to modify this le but make sure to read its comments.







1



Stack.java: You need to code the Stack class that implements the iSimpleContainer interface using a generic deque in this le. Look at the code to see how this is setup. This must have the last-in rst-out behavior.




Queue.java: You need to code the Queue class that implements the iSimpleContainer interface using a generic deque in this le. Look at the code to see how this is setup. This must have the rst-in rst-out behavior.




Main.java: Runs the autograder on your code and gives printouts to help you.




Util.java: This le includes utility functions. Do not worry about it, you will not need to use anything from this le in this assignment.




Part II




In the second part of the assignment, you are going implement an algorithm, given below, that nds the exit in a maze given a start coordinate. This algorithm uses containers which changes its behavior. If a stack is used the algorithm acts as a depth- rst search and if a queue is used, it acts as a breadth- rst search. The idea is to start from the start state and systematically search the maze. The containers hold the next states to be checked. The mazes are given as txt les where characters de ne the whether a cell is a wall, empty, a start state or an end state. The algorithm is as below:







Algorithm 1: solveMaze(maze,sc,deque)




Input: Maze (maze), initially empty container (sc), initially empty visited node storage (deque)




Output: Wheter a path to an exit cell is found, the lled visited node storage sc.push(maze startState)




while sc is not empty do




currentState = sc.pop()




if currentState is an exit state then

return true




else if currentState is not visited then

mark currentState as visited







deque.addBehind(currentState) foreach empty neighbor of currentState do sc.push(neighbor)




end




end




return false







For this part, you need to edit the following le:




Maze.java: This le holds the maze information. Go over its comments carefully and understand what it does. You are going to ll in the solveMaze method. We de ned additional methods to be helpful but they are not going to be checked.




Grading




Your assignment will be graded through an autograder. Make sure to implement the code as instructed, use the same variable and method names.




A version of the autograder is also released to you. Our version will more or less be similar, potentially including more tests or tests with additional reference implementations of Stack and Queue. Run the main program in the Main.java to get the autograder output and your grade.




In case the autograder fails or gives you 0 when you think you should get more credit, do not panic.




Let us know. We can go over everything even after your submission.




Submission




You are going to submit a compressed archive through the blackboard site. The le should extract to a folder with your student ID without the leading zeros. This folder should only contain les that were










2



in boldface in the previous section. Other les, which you should not have modi ed anyways, will be deleted. Other les will be deleted and/or overwritten.




Important: Make sure to download your submission to make sure it is not corrupted and it has your latest code. You are only going to be graded by your blackboard submission.




Submission Instructions




You are going to submit a compressed archive through the blackboard site. The le can have zip, tar, rar, tar.gz or 7z format.




This compressed le should extract to a folder with your student identi cation number with the two leading zeros removed which should have 5 digits. Multiple folders (apart from operating system ones such as MACOSX or DS Store) greatly slows us down and as such will result in penalties




Code that does not compile will be penalized and may receive no credits.




Do not trust the way that your operating system extracts your le. They will mostly put the contents inside a folder with the same name as the compressed le. We are going to call a program (based on your le extension) from the command line. The safest way is to put everyting inside a folder with your ID, then compress the folder and give it your ID as its name.




One advice is after creating the compressed le, move it to your desktop and extract it. Then check if all the above criteria is met.




Once you are sure about your assignment and the compressed le, submit it through Blackboard. After you submit your code, download it and check if it the one you intended to submit.




DO NOT SUBMIT CODE THAT DOES NOT TERMINATE OR THAT BLOWS UP THE MEMORY.




Let us know if you need any help with setting up your compressed le. This is very important. We will put all of your compressed les into a folder and run multiple scripts to extract, cleanup and grade your codes. If you do not follow the above instructions, then scripts might fail. This will lead you to get a lower grade than what the autograder suggests.




































































































3