关于算法:MCD4710-Algorithms-讲解

MCD4710 Assignment 1 (8%) MCD4710 Introduction to
Algorithms and Programming
Objectives
Due: Thursday, April 4, 2019, 5:00 pm – Week 6
The objectives of this assignment are:
To gain experience in designing algorithms for a given problem description and implementing those
algorithms in Python 3.
To demonstrate your understanding of:
– how to implement algorithms for sorting in Python.
– how to decompose code into functions in Python.
– how to read from text files using Python.
– how to manipulate lists using basic operations.
– greedy approaches to problems
– brute-force approaches to problems
– backtracking approaches to problems
Submission Procedure

1. Put you name and student ID in a comment at the start of your file in yoursolution.
2. Save your file into a zip file called YourStudentID.zip
3. Submit your zip file containing your solution to Moodle.
4. Your assignment will not be accepted unless it is a readable zip file.
   Important Notes:
5. 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-assessmentpolicy.pdf.
   You will be required to agree to these policies when you submit your assignment.
6. Your code 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 own.
7. Where it would simplify the problem you may not use built-in Python functions or libraries (e.g. using
   list.sort() or sorted()). Remember that this is an assignment focusing on algorithms and programming.
8. 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 some marks based on how close
   your algorithm is to the correct algorithm. This is made difficult if code is poorlydocumented.
9. For eachtask, youneed towrite aprogramthatproperly decomposesthe problem. Youwill learn functions and
   decomposition in Week 3.
   Marks: This assignment has a total of 50 marks and contributes to 8% of your final mark. Late submission will
   have 5% off the total assignment marks per day (including weekends) deducted from your assignment mark.
   Assignments submitted 7 days after the due date will normally not be accepted?
   Marking Criteria:
   Total: 50marks
   A. representation and display (20 marks)
   B. checking correctness(10marks)
   C. generating a quilt of size N x M with random placement of X’s (10 marks)
   D. decomposition, variable names and documentation (10 marks)
   Assignment code interview
   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.
   Interview Rubric
10. 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 studentseems underprepared
    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 remembersomething they were told but now can’t remember
    Howeverthey clearly know something about the code
    With prompting they fail to improve on a partial or incorrect answer
    0.75 The studentseemsreasonably well prepared
    Questions are answered correctly for the most part but the speed and/or confidence they are
    answered with is not 100%
    With prompting they can add a partially correct answer or correct an incorrect answer
11. 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.
    3
    Background:
    This assignment has you working on representing a coloured quilt as a table and deciding which colour should
    occupy each square. In this problem, you have a rectangular quilt. Some of the squares in the quilt will need to
    be coloured. These are marked with“X”. No square can be the same colour as any of the surrounding eight
    squares. Note that wrap around is not considered in this problem so a square on the right end does not need
    to be different to one on the left end (unless they are already adjacent).
    X X – –
12. X – X
    X X X –
13. X – –
    Table 1: Read from file
14. 1 – –
15. 2 – 0
16. 1 3 –
17. 2 – –
    Table 2: Coloured quilt
18. 1 – –
19. 2 – 0
20. 0 1 –
21. 2 – –
    Table 3: Another coloured quilt
    Note: The size of the quilt will never be greater than 10 x 10 and the number of coloured squares to be filled
    in will never exceed 15 squares i.e. there will never be more than 15 X’s in a file. We will only use four colours.
    Any more than 4 will take too long to run if you use brute-force.
    4
    Task1: Representation and display (20 marks)
    The simplest representation of this problem would be to represent the quilt as a table, where‘X’marks the
    squares to be coloured and‘–‘marks the squares that don’t need to be coloured. Integers can be used to
    represent the colours with each integer representing a different colour (see table 1, 2, and 3).
    Part A: Initial setup (5 marks)
    Write a python function which takes as input the name of a file in which the quilt is stored and produces a two
    dimensional table (list of lists) to represent this quilt.
    Part B: Display (5 marks)
    Extend your program such that the colours of any given quilt can be displayed on the screen. Combining this
    with the initial setup might yield the following output:
    Enter the name of the file? Quilt.txt
    The quilt is currently as below:
    X X – –
22. X – X
    X X X –
23. X – –
    Part C: File input/output (5 marks)
    Extend your program so that you are able to do the following:
    write to a new file the current quilt state (which is saved in your list of lists created in Part A). The user
    should be asked for the name of the file.
    read from a user entered file and update the current quilt state i.e. your list of lists.
    Hint: if you read from the file you just wrote to, your quilt state will be unchanged.
    Part D: Menu (5 marks)
    Write amenuwhichallowsthe usertochoose froma setofoptionsto perform; e.g.:
    What would you like to do?
24. read quilt
25. write quilt
26. check for correctness
27. exit
    Please enter a valid filename: example.txt
    X X – –
28. X – X
    X X X –
29. X – –
    what would you like to do?
30. read quilt
31. write quilt
32. check for correctness
33. exit
    Task2: Correctness: (10marks)
    This part is about how to ensure the representation is in fact a valid quilt colouring.
    Extend your python program (and menu) so that it can take a representation of the quilt state and determine
    whether any two adjacent squares have the same colour.
    Where any two adjacent squares are the same colour it prints “invalid quilt” to the screen, otherwise it prints
    “valid quilt” to the screen.
    For example, consider the three quilts below:
34. 1 – –
35. 2 – 0
36. 1 3 –
37. 2 – –
38. 1 – –
39. 2 – 0
40. 1 2 –
41. 2 – –
42. • • • • • • • 0
43. 1 – – – 0 1 2 –
44. • • 0 1 – – – 0
45. 1 2 – – 0 1 2 –
    The first colouring here is valid.
    The second colouring is invalid as the 2 in the second row and second column has a 2 around it in the
    third row and third column.
    The third colouring is also valid but shows an example of a 9 × 4 instead.
    Extend your program so that it uses your file reading code to determine the correctness of a file holding a
    representation of the quilt. If the examples above were stored in quilt1.txt, quilt2.txt and quilt3.txt
    respectively then the expected behaviour is as below:
    what would you like to do?
46. read quilt
47. write quilt
48. check for correctness
49. exit
    Please enter a file to check: quilt1.txt
    valid quilt
    Would you like to check another file Y
    Please enter a file to check: quilt2.txt
    invalid quilt
    Would you like to check another file Y
    Please enter a file to check: quilt3.txt
    valid quilt
    Would you like to check another file N
    what would you like to do?
50. read quilt
51. write quilt
52. check for correctness
53. exit
    Task 3: Generating random quilts (10 marks)
    In this task you will need to ask the user the dimensions of the quilt, N and M. You will also ask the user to
    enter the number of X’s they want in the quilt. You will use these values to generate a new quilt of size N x M
    in which the X’s are randomly place in the quilt. You will need to check that the user has entered values that
    makes sense e.g. if the user enters 5 x 4 for the quilt size, they should not be able to enter a value of 21 for
    the number of X’s. The minimum number of X’s allowed should be greater than 20% of N x M.
    Task 4: Decomposition, Variable names and code Documentation(10
    marks)
    Marks will be allocated for good use of variable names, code documentations and proper decomposition.
    WX：codehelp