# 06-30175作业代做、Data Structures作业代做、代写Java编程设计作业、代写Java课程作业代写留学生Prolog|代写留学生 Stati

06-30175 The University of Birmingham
Data Structures & Algorithms School of Computer Science
Spring Semester 2010-2020
c Alan P. Sexton 2010-2020
Assignment 02
1 Introduction
This assignment will be marked out of 10 and constitutes 10% of your final module mark.
14:00 Friday 14th February
With apologies to J.R.Tolkien, the dwarf mine under the mountain of Moria (c.f. https://en.wikipedia.org/
wiki/Moria_(Middle-earth)) has been discovered and your job is to program a drone to explore this underground
world and map out the maze formed by the chambers and connections between them.
Figure 1: A small sample maze
There are an unknown number of chambers in the maze. Every chamber has a number of doorways (the doors themselves
are no longer intact so there is no barrier to traversing the passageways or “wildlife” to deal with during the search). For
simplicity, each chamber is numbered, starting at 0, and each doorway is numbered in each chamber, ranging from 0 to
the number of doorways in the chamber minus 1.
Figure 1 indicates a sample maze (Moria itself has many more chambers). The numbers in the circles are the chamber
numbers and the numbers on the lines are the doorway numbers. Thus doorway 1 of chamber 0 connects to doorway 2 of
chamber 1, etc.
The drone always starts in chamber 0 and, after exploring the whole maze, should finish in chamber 0 as well.
Your drone has access to a sensor system (a Maze class) that it can interrogate to identify
• which chamber it is currently in,
• how many doorways are visible in the current chamber and,
• which chamber it then enters and through which doorway, when the drone proceeds through a doorway and down
the passage to the next chamber.
The sensors cannot tell you about any chamber that the drone is not currently in.
In summary, for this assignment you have to write the code to accomplish a number of tasks:
a. Implement the code for a method to decide on which doorway to enter at each step during the search so that every
chamber is explored and the drone ends up back in the start chamber (chamber 0).
b. Keep a record of every doorway that the drone passes through, either in leaving or in entering a chamber, to make it
available at any point to the drone’s user (i.e. the caller).
1
c. In case of low battery, the drone must be able to calculate a direct route back (a sequence of doorways to take) to the
start chamber from whatever chamber it is currently in. This route should avoid taking detours, loops or entering
dead-ends that it then needs to backtrack out of.
2 Marking
• Any submission that passes all the tests in DroneTest.java, although on a range of different mazes other than
just the one current used in that file, will get full marks.
• Further tests may be added during marking to distinguish between the different ways that a submission that is not
passing all the tests is failing, so that partial marks can be awarded.
• There will be 1 mark if your submission compiles correctly and can be run and passes the single test that already
passes in the initial assignment files.
• If your submission is not structured correctly or does not compile, or crashes or enters an infinite loop before any
tests pass, then no marks will be earned.
3 Plagiarism
Plagiarism will not be tolerated: it is unfair to the other students and prevents you from learning, and would give you a
mark you don’t deserve, and qualifications you don’t deserve, hence being unfair to society as a whole too. Please behave
well and reward the module lecturer and TA’s by submitting your own, hard work.
All submissions will be checked for copying against other submissions and against sources on the web and elsewhere.
When the module lecturer decides that there is evidence of plagiarism, the case will be forwarded to the Senior Tutor, who
will look at the evidence and apply penalties and warnings, or, if necessary, forward this to the University.
• University regulations on plagiarism: https://intranet.birmingham.ac.uk/as/studentservices/
conduct/plagiarism/index.aspx
• University Library sources on plagiarism: https://intranet.birmingham.ac.uk/as/libraryservices/
library/referencing/index.aspx
4 Student Welfare
If you miss or are going to miss a deadline, or are getting behind the learning material, for reasons outside of your control,
the University in sports, programming competitions, etc., and if this is going to affect your ability to comply with a
deadline, Wellfare should be informed. It is the Welfare Team, not the teaching team, who can award extensions and
cancellations, and devise other measures to cope with adverse situations. It is important to contact welfare as soon as
possible when such situations arise.
5 Background to this Assignment
While the first assignment was all about the internals of implementing pointers and lists, this assignment is about using
some of the available data structures in the Java standard library (the collection classes) so that you can avoid having to
implement your own basic data structures but instead use the various standard lists, maps, arrays, queues and stacks, and
their associated implemented algorithms, to solve your programming problems.
There is not a great deal of code that needs to be written, but the logic for some of it can be a bit involved, so please start
on the assignment early and be diligent with your unit tests and study the identified classes in the JavaDoc.
The collection classes you will need to use are:
• Deque<>: A Double Ended Queue interface with the most commonly used implementations ArrayDeque<>
You use the a Deque<> in Java as the standard way to implement both a Stack and a Queue as well as a Deque
• Set<>: A Set interface with the most commonly used implementations HashSet<> and TreeSet<>
This implements the set abstraction, where we can add and remove elements and easily check whether an element
is currently in the set. Unlike a list, even if we add multiple elements with the same value to a set, that value will
only appear in the set once.
2
• Map<>: A Map interface with most commonly used implementations HashMap<> and TreeMap<>
Map<> has 2 type parameters. For example, a Map

• QQ：99515681
• 邮箱：99515681@qq.com
• 工作时间：8:00-23:00
• 微信：codinghelp