代写MCD4710、代做Programming留学生、代做Python程序、Python设计代写

日期：2019-04-08 10:25

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:

1. 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.

2. 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.

3. 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.

4. 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.

5. 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

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 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

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.

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 - -

- X - X

X X X -

- X - -

Table 1: Read from file

0 1 - -

- 2 - 0

0 1 3 -

- 2 - -

Table 2: Coloured quilt

0 1 - -

- 2 - 0

1 0 1 -

- 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 - -

- X - X

X X X -

- 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?

1. read quilt

2. write quilt

3. check for correctness

4. exit

Please enter a valid filename: example.txt

X X - -

- X - X

X X X -

- X - -

what would you like to do?

1. read quilt

2. write quilt

3. check for correctness

4. 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:

0 1 - -

- 2 - 0

0 1 3 -

- 2 - -

0 1 - -

- 2 - 0

0 1 2 -

- 2 - -

0 - - - - - - - 0

- 1 - - - 0 1 2 -

0 - - 0 1 - - - 0

- 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?

1. read quilt

2. write quilt

3. check for correctness

4. 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?

1. read quilt

2. write quilt

3. check for correctness

4. 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.