辅导CSCM94编程

日期：2021-05-14 10:54

Objectives

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 each file in your solution.

2. You single python file should be named as yourStudentID.py

3. Save your files into a zip file called yourFirstName_yourLastName.zip

4. Submit your zip file containing your solution to Moodle.

5. 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 focussing 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 poorly documented.

5. For each task, you need to write a program that properly decomposes the problem. You will

learn functions and decomposition in Week 3.

MCD4710 Assignment 2 (10%) MCD4710 Introduction to

Algorithms and Programming

Marks: This assignment has a total of 100 marks and contributes to 10% of your final mark. Late

submission will have 5% (5 marks) 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: 100marks

a) Code readability (Non-trivial comments where necessary and meaningful variable names) -

10 marks

b) Code decomposition - 10 marks

c) Round robin assignment - 10 marks

d) Display and representation of line contents - 5 marks

e) User choice assignment - 15 marks

f) Menu to control assignment method used - 5 marks

g) Computing processing time - 5 marks

h) Brute force approach - 25 marks

? Description of brute force approach - 5 marks

i) Description of a greedy approach - 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’tseen the code before

0.25 There issome 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.

Background

You have been hired by a grocery store to help them increase their sales (in dollars per second) by improving

how they manage how customers check out their goods and pay for them.

Normally, the store has up to 5 different checkouts and a customer can use any of them; typically customers join

the line which looks shortest but lines move at different speeds based on how many items are being purchased

and how bulky they are (e.g. bigger items can be harder to bag and scan). They’re hoping that you will be

able to suggest some ideas for them in deciding which customers use which line so that each line maximises the

purchases (in dollars per second).

There are three sizes of item, Light, Average and Bulky. Average items take twice as long to scan as light items

and bulky items take fives times as long to scan as light items (see table below).

Item Type Light item Average Item Bulky Item

Scanning Time L 2 × L 5 × L

Table 1: relation between item type and scanning time

Not only this but based on the person working at the register at the time, it can take more or less time to

handle the same sized item. The example in the table below shows some sample register operators and how

long it takes them to scan items in seconds.

Example Register Operator Light item (seconds) Average item (seconds) Bulky item (seconds)

Bill 4 8 20

Lee 2 4 10

Tanya 3 6 15

Sasha 1 2 5

Table 2: scanning times (in seconds) for sample register operators

Background: Customer File Format

You will be reading from a customer file to find out the items a customer has in their basket (their price and

how big they are). These files follow the following format:

[type][value],[type][value],...

[type][value],[type][value],...

...

[type][value],[type][value],...

In this each line is a new customer and within that line, the items are separated by commas and show the type

of the item (with l,a, and b representing Light, Average and Bulky items) followed by the value. For instance,

a file holding three customers with 3, 2, and 5 items each may look like so

L5,A2,L1

l2,B20

B207,a15,b20,l6,A12

This tells us that customer 1 has a light item worth $5, an average item worth $2 and another light item worth

$1. Customer 2 has a $2 light item and a $20 bulky item. Finally, customer 3 has a$207 bulky item, a $15

average item, $20 bulky item, $6 light item and $12 average item.

The item type will always be a single character (but can be upper or lower case), the item value will always be

a positive integer (whole number); anything other than this can be considered invalid input. There will always

be at least one customer and any customer will have at least one item in their basket.

3

Background: Register File Format

You will also be reading from a register file to determine the number of registers currently available and the

speeds of the register operators.

The register files follow the following format:

[speed1]

[speed2]

...

[speedn]

So if there were 4 registers currently in operation with speeds of 3, 6, 4, and 1 second each for a light item, the

file might look like so: