MCD4710 Introduction to Algorithms and Programming
Python3代写 The objectives of this assignment are:To gain experience in designing algorithms for a given problem description and implementing
MCD4710 Assignment 1 (8%)
Due: July 26, 2018, 5:00 pm
The objectives of this assignment are:
To gain experience in designing algorithms for a given problem description and implementing those algo- rithms in Python 3.Python3代写
- To demonstrate your understandingof:
–how to implement algorithms for sorting in
–how to decompose code into functions in
–how to read from text files using
–how to manipulate lists using basic
–greedy approaches toproblems
– brute-force approaches to problems
– backtracking approaches to problems
- Putyou name and student ID in a comment at the start of each file in your
- Save your files into a zip file called yourFirstNamezip
- Submityour zip file containing your solution to
- Yourassignment will not be accepted unless it is a readable zip
- Please ensure that you have read and understood the university’s policies on plagiarism and collusion available at https://www.monashcollege.edu.au/__data/assets/pdf_file/0010/17101/dip-assessment-policy.pdf.
You will be required to agree to these policies when you submit your assignment.
- Yourcode will be checked against other students’ work and code available online by advanced plagiarism detection systems. Do not take the risk, make sure your work is your
- Where it would simplify the problem you may not use built-in Python functions or libraries (eg. using sort() or sorted()). Remember that this is an assignment focussing on algorithms and program- ming.Python3代写
- Your program will be checked against a number of test cases. Do not forget to include comments in your code explaining your algorithm. If your implementations have bugs, you may still get somemarks based on how close your algorithm is to the correct algorithm. This is made difficult if code is poorly documented.
- Foreach task, you need to write a program that properly decomposes the You will learn functions and decomposition in Week 3.
Marks: This assignment has a t otal of 100 marks and contributes t o 8% of your final mark. Late s ubmission will have 5% off t he t otal assignment marks per day ( including weekends) deducted f rom your assignment mark. Python3代写Assignments submitted 7 days after the due date will normally not be accepted.
Marking Criteria:Total: 100 marks
(a)Codereadability (Non-trivial comments where necessary and meaningful variable names) 10 marks
(b)Code decomposition 10marks
(c)Inputtingand displaying battery and device information 10 marks
(d)Finding the Euclidean distance between devices 10marks Python3代写
(e)nding the closest paid of devices 10marks
(f)inputtingand displaying connections and their distance 10 marks
(g)ndingthe total path cost of connections given 40 marks
Assignment code interview Python3代写
Each student will be interviewed during a lab session regarding their submission to gauge your personal understanding of your Assignment code. The purpose of this is to ensure that you have completed the code yourself and that you understand the code submitted. Your assignment mark will be scaled according to the responses provided.
|0||The student cannot answer even the simplest of questions There is no sign of preparation
They probably haven’t seen the code before
|0.25||There is some evidence the student has seen the code
The answer to a least one question contained some correct points
But it’s clear they cannot engage in a knowledgeable discussion about the code
|0.5||The student seems underprepared Python3代写
Answers are long winded and only partly correct
They seem to be trying to work out the code as they read it
They seem to be trying to remember something they were told but now can’t remember However they clearly know something about the code
With prompting they fail to improve on a partial or incorrect answer
|0.75||The student seems reasonably well prepared
Questions are answered correctly for the most part but the speed and/or confidence they are answered with is not 100% Python3代写
With prompting they can add a partially correct answer or correct an incorrect answer
|1||The student is fully prepared
All questions were answered quickly and confidently
It’s absolutely clear that the student has performed all of the coding themselves.
You will be creating a program which can nd the best way to connect a sequence of LEDs or other small devices on a circuit together with a battery. See gures below.
We can use a le to represent these devices and connections.
Device (and battery) le format Python3代写
A device le will be in the following format: x,y-x,y
For instance, the devices shown above would correspond to exampleDevices.txt as below: 6,8-7,8
The top line will always be the x,y coordinates of the two ends of the battery, every other line will be the x,y coordinates of each device in order.Python3代写
Connections le format
A connections le will be in the following format: x1,y1 x2,y2
x1,y1 x2,y2 x1,y1 x2,y2
For instance, the connections shown above would correspond to exampleConnections.txt as below: 6,8 2,6
Each line in the above is a di erent connection and lists the coordinates where the connection starts and ends. These could easily be reversed and mean the same thing (e.g. 6,8 2,6 is the same as 2,6 6,8) and the connections could be given in any order (e.g. 3,0 4,3 could equally have been the second in the list without changing anything)Python3代写
What you need to doPython3代写
You have been provided with some les on Moodle named exampleConnections.txt and exampleDevices.txt. These will help you to complete this assignment.
You are required to complete the following tasks in this assignment:
- Readin and display a sequence of device and battery locations from a file 10 marks
- Findthe euclidean (‘straight line’) distance between any two devices 10 marks
- Findingthe closest pair of devices 10 marks
- Readin and display a sequence of connections 10 marks
- Findthe total path cost using these connections starting and ending at the battery 40 marks
Task 1: Read in and display a sequence of device and battery locations
For this task you will need to ask the user for a lename to read from and get the battery and devices from this le into some representation in your program.
Once this is done, you should print o all of the devices and the battery locations (using their coordinates) onto the screen [you should clarify which are devices and which the battery] – This should match those provided in the file.Python3代写
Check the background section for how to interpret the devices and battery le For instance, for the devices listed in the background you might display:
the battery is from [6, 8] to [7, 8] the devices are at positions…[2, 6] [3, 0] [4, 3] [6, 4]
Task 2: Find the Euclidean distance between any two devices
For this task, you will need to setup code which is capable of determining the length of a straight line from one device to another. You may assume distance is measured in millimetres Python3代写
Hint: for a pair of points in two dimensions, the formula is as below: distance = (x2 x1)2 + (y2 y1)2
Note: you must write this yourself, you may not use a python package which can compute this
Task 3: Finding the closest pair of devices
Use your code from the previous task and nd which two devices are the closest to one another. You should be able to consider ends of the battery as well, however you should not consider the di erence between one end of the battery and the other – as these are two parts of the same item.Python3代写
You should print this o to the screen; for instance for the devices in the background you might get:
the closest two devices (including battery) are [6, 3] and [4, 3] with a distance of 2.0 (mm)
Task 4: Read in and display a sequence of connections
For this task you will need to ask the user for a lename to read from and get the connections from this le into some representation in your program.
Once this is done, you should print o each connection and display their length on the screen (rounded to two decimal places).Python3代写
Check the background section for how to interpret the connections le
For instance, for the connections listed in the background you might display: of all connections…
Task 5: Find the total path cost using these connections
For the nal task, you should use the battery and set of devices and connections to trace out a path from the battery, through each device and back to the battery (but the other end). You may assume that each device has two connections and that each end of the battery only has one connection.Python3代写
Beginning at one end of the battery, follow the connections through each device (adding up the total distance as you go) until you reach the other end of the battery.
You should display this total distance on the screen (rounded to 2 decimal places). If it is not possibly to get from one end of the battery and back to the other end, you should print something out to this e ect; if not all devices are included in the path, you should print this out.Python3代写
For instance, for the devices and connections in the background, we expect the following to be printed:
These connections connect from battery back to battery and include all devices in the path distance for the full path is 20.08 (mm)Python3代写
If the connection [4,3]-[6,4] was removed in the example in the background, we would instead see this. not possible to traverse this set of connections back to the battery
Finally, if the connections [2,6]-[3,0] and [3,0]-[4,3] are removed and replaced with [2,6]-[4,3] in the example in the background, we would instead see this.
not all devices included in these connections