辅导案例-FIT2004-Assignment 4
FIT2004 S2/2019: Assignment 4
Nathan Companez
DEADLINE: Friday 25th October 2019 23:55:00 AEST
LATE SUBMISSION PENALTY: 10% penalty per day. Submissions more than 7 days
late are generally not accepted. The number of days late is rounded up, e.g. 5 hours late
means 1 day late, 27 hours late is 2 days late. For special consideration, please complete
and send the in-semester special consideration form with appropriate supporting document
before the deadline to [email protected]
PROGRAMMING CRITERIA: It is required that you implement this exercise strictly
using Python programming language (version should not be earlier than 3.5). This
practical work will be marked on the time complexity, space complexity and functionality
of your program.
Your program will be tested using automated test scripts. It is therefore critically impor-
tant that you name your files and functions as specified in this document. If you do not, it
will make your submission difficult to mark, and you will be penalised.
SUBMISSION REQUIREMENT: You will submit a zipped file (named
studentId_A4.zip, e.g. if your student id is XXXX, the name of zipped file must be
XXXX_A4.zip). It should contain a single python file, assignment4.py, and a single pdf
file, description.pdf
PLAGIARISM: The assignments will be checked for plagiarism using an advanced pla-
giarism detector. All suspected cases will be investigated. The faculty takes academic
integrity seriously and consequences for such misconduct can include receiving zero marks
for the assignment or unit or suspension or exclusion. Please see the University Policy
https://www.monash.edu/students/admin/policies/academic-integrity for more details.
“Helping” others is NOT ACCEPTED. Please do not share your solutions partially or/and
completely to others. If someone asks you for help, ask them to visit us during consultation
hours for help.
1
Learning Outcomes
This assignment achieves the Learning Outcomes of:
• Analyse general problem-solving strategies and algorithmic paradigms, and apply them
to solving new problems
• Prove correctness of programs, analyse their space and time complexities
• Develop and implement algorithms to solve computational problems.
In addition, you will develop the following employability skills:
• Text comprehension
• Designing test cases
• Ability to follow specifications precisely
Warning
For all assignments in this unit, you may not use python dictionaries or sets. For all assignments
in this unit, please ensure that you carefully check the complexity of each python function that
you use. Common examples which cause students to lose marks are list slicing, inserting or
deleting elements in a list, using the in keyword to check for membership of an iterable, or
building a string using repeated concatenation of characters. These are just a few examples, so
be careful. Remember, you are responsible for the complexity of every line of code you write!
Assignment timeline
In order to be successful in this assessment, the following steps are provided as a suggestion.
This is an approach which will be useful to you both in future units, and in industry.
Planning
1. Read the assignment specification as soon as possible and write out a list of questions
you have about it.
2. Clarify these questions; You can go to a consultation, talk to your tutor, discuss the tasks
with friends or ask in the forums.
3. As soon as possible, start thinking about the problems in the assignment.
• It is strongly recommended that you do not write code until you have a solid feeling
for how the problem works and how you will solve it.
4. Writing down small examples and solving them by hand is an excellent tool for coming
to a better understanding of the problem.
• As you are doing this, you will also get a feel for the kinds of edge cases your code
will have to deal with.
2
5. Write down a high level description of the algorithm you will use.
6. Determine the complexity of your algorithm idea, ensuring it meets the requirements.
7. Write your description.pdf.
• You should be able to start working on this before you write your code.
• If you cannot, perhaps your it is worth thinking a little more about how exactly your
code will work.
Implementing
1. Think of test cases that you can use to check if your algorithm works.
• Use the edge cases you found during the previous phase to inspire your test cases.
• It is also a good idea to generate large random test cases.
• Sharing test cases is allowed, as it is not helping solve the assignment.
2. Code up your algorithm, (remember decomposition and comments) and test it on the
tests you have thought of.
3. Try to break your code. Think of what kinds of inputs you could be presented with which
your code might not be able to handle.
• Large inputs
• Small inputs
• Inputs with strange properties
• What if everything is the same?
• What if everything is different?
• etc...
Before submission
• Make sure that the input/output format of your code matches the specification.
• Make sure your filenames match the specification.
• Make sure your functions are named correctly and take the correct inputs.
• Make sure you zip your files correctly
3
Background
A word ladder is a series of words, all the same length, where each word differs with the
previous word by exactly one character. In this assignment we will refer to the first word
as the start_word and the last word as the target_word. A word ladder puzzle is
normally presented by giving the start_word, then some number of empty space, then
the target_word. To solve the puzzle, the player must find the sequence of words that
completes the chain. These words are called the intermediate words. In general the words
must be valid English words. In general, the solution to a word ladder will not involve
repeated words, since this loop could be removed without invalidating the solution. An
example of such a puzzle and its solution are:
To make our own word ladders, we need to use a data structure which allows us to easily
check if two words differ by a single letter. In this assignment, we will represent this
information using a graph, where each vertex corresponds to a word, and there is an edge
between two vertices when those two words differ by a single letter. A solution to a word
ladder would be a path in this graph.
Algorithm Descriptions (2 mark)
For each of the three tasks, you must also write a brief description of your algorithm. The
total length should be no more than 800 words.
These two descriptions will be submitted in the pdf file description.pdf mentioned in the
"Submission Requirement" section. These description should explain the steps your algorithm
takes to solve the problem, and the complexity of each step. Please try to keep these descriptions
at a fairly high level, talk about your data structures and algorithms, not individual variables
or lines of code.
0 Building the graph (6 marks)
For all the tasks in this assignment, we will be working with a graph where each vertex repre-
sents a word, and there is an edge between two vertices if and only if those two words differ by
exactly one character. You do not need to check that this is true, you may assume the input
4
files always correctly encode such a graph.
Before we start, we need to construct the graph. You will be provided with two files. You will
need to read these files into an appropriate graph data structure. To do this, you will create
a Python class, Graph. The other tasks in this assignment will each require you to write a
method for your Graph class.
For this assignment, all the graphs will be simple, undirected graphs.
Important: If you do not create a class, or you implement the later tasks as independent
functions rather than methods of the Graph class, you may receive 0 marks for the assignment.
0.1 Input
The graph is given to you as two files, the first containing information about the vertices,
and the second containing information about the edges. For this task, you need to write the
__init__(self, vertices_filename, edges_filename) function for your Graph class. This
function takes two filenames as inputs, and reads the data from them into an appropriate data
structure.
The first line of vertices_filename has a number, n, which is the number of vertices in the
graph. The next n lines each start with a unique integer between 0 and n − 1 inclusive (the
vertex ID) and then a space, and then a word (the word which that vertex represents). The
words will contain only lowercase English alphabet characters. For this assignment, you
may assume that all words are constant size.
Each line of edges_filename consists of two numbers, separated by a a space. Each of these
pairs of numbers represents an undirected edge connecting the two vertices with those IDs. You
are guaranteed that all the numbers in edges_filename are valid vertex IDs (i.e. are integers
between 0 and n− 1 inclusive). The edges are in no particular order.
Example:
Calling this line of code should correctly populate an instance of your Graph class.
my_graph = Graph("vertices.txt", "edges.txt")
Note that here the two files are called vertices.txt and edges.txt, but they could be called
anything. Similarly, the name my_graph is just used as an example, it could be any name:
0.2 Output
No output is required. The marks for this task are awarded for having the correct complexity,
and having no errors in your graph construction. That said, the choices you make about how
your graph is implemented will affect the complexity of later tasks, so make sure you have read
the whole assignment.
0.3 Complexity
__init__ should run in O(V + E), where
5
• V is the number of lines in vertices_filename
• E is the number of lines in edges_filename
6
1 Solving a ladder (10 marks)
Once we have built the graph, we want to be able to solve word ladders! Given a word ladder
puzzle (i.e. a start_vertex and target_vertex, which each have a word), you need to write
a function which finds the shortest list of intermediate words which solves it (or reports that
no such list exists)
You will write a method for the Graph class, called solve_ladder(self, start_vertex,
target_vertex), which will return a list of the intermediate words.
For a given pair of start_vertex and target_vertex, there may be several equally short lists
of intermediate words. Any of them is acceptable.
1.1 Input
start_vertex and target_vertex. These are integers between 0 and V − 1 inclusive, where
V is the number of vertices in the graph.
1.2 Output
The function should return a list of strings, which correspond to the words in the word ladder
from start_vertex to target_vertex. Note that this list can be empty under certain con-
ditions. In some cases, it may not be possible to find a chain from the start_vertex to the
target_vertex. In these cases, the function should return False.
Example: If vertices_filename contains
7
0 aaa
1 aab
2 abb
3 bbb
4 caa
5 cba
6 bba
Then edges_filename would contain
0 1
0 4
1 2
2 3
3 6
4 5
5 6
Suppose that we had created an instance of Graph, called my_graph to store the above graph.
my_graph.solve_ladder(0, 6) returns ["aaa", "caa", "cba", "bba"]
7
1.3 Complexity
solve_ladder must run in O(V + E) time, where
• V is the number of vertices in the graph
• E is the number of edges in the graph
8
2 Restricted word ladder (12 marks)
Now, rather than the shortest word ladder, you want to find the cheapest word ladder. The
cost of a word ladder is found by summing the the costs of the changes made to characters
during that ladder. The cost of changing a character from given by squaring the difference in
alphabet position of the two characters. For example, the cost of transforming "a" into "c"
would be (3− 1)2 = 4. Transforming "a" into "z" would cost (26− 1)2 = 625. The cost of the
word ladder in the background section, which starts with "cold" and ends with "warm" would
be
(L→ R) + (O → A) + (C → W ) + (D →M)
=(12− 18)2 + (15− 1)2 + (3− 23)2 + (4− 13)2
=36 + 196 + 400 + 81
=713
However, there is an additional requirement. In this task, the word ladder must also
contain at least one word which starts with a given letter. This letter will be one of our input
parameters.
You will write a method for the Graph class, called cheapest_ladder(self, start_vertex,
target_vertex, req_char) to solve this problem.
2.1 Input
start_vertex, target_vertex and req_char. start_vertex and target_vertex are integers
between 0 and V − 1 inclusive, where V is the number of vertices in the graph. req_char is a
lowercase english alphabet character.
2.2 Output
cheapest_ladder should return two things as a tuple (or False). The first is the cost of the
cheapest word ladder. The second is a list of strings, which are the intermediate words in the
cheapest word ladder starting at start_vertex and ending at target_vertex, such that at
least one word in the ladder has req_char as its first character (This can be the the word
associated with start_vertex or target_vertex). Note that this list can be empty under
certain conditions.
In some cases, it may not be possible to find a chain from the start_vertex to the tar-
get_vertex with at least one word in the ladder has req_char as its first character . In these
cases, the function should return False.
Example:
7
0 aaa
1 aab
2 abb
3 bbb
4 caa
9
5 cba
6 bba
Then edges_filename would contain
0 1
0 4
1 2
2 3
3 6
4 5
5 6
Suppose that we had created an instance of Graph, called my_graph to store the above graph.
• my_graph.cheapest_ladder(0, 6, ’z’) returns False, as there is no path from "aaa"
to "bba" where one of the words has z as the first letter.
• my_graph.cheapest_ladder(0, 6, ’a’) returns (4, [’aaa’, ’aab’, ’abb’, ’bbb’,
’bba’]), as there are two paths from "aaa" to "bba", both of which have at least one
word starting with a, but this path has total cost 4 while the other has total cost 6.
• my_graph.cheapest_ladder(0, 6, ’c’) returns (6, [’aaa’, ’caa’, ’cba’, ’bba’]),
as there are two paths from "aaa" to "bba", but only this path has at least one word
starting with c
2.3 Complexity
cheapest_ladder must run in O(E log(V )) time, where
• V is the number of vertices in the graph
• E is the number of edges in the graph
10
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie