algorithms留学生讲解、辅导Python、辅导programming

2019.01.24 - 首页 >> 其他

Due: January 10, 2018, 23:55 pm

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],...

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.

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:

There will always be at least one register in operation (with no fixed maximum) and all register speeds will be

positive integers (whole numbers). Anything else is considered invalid.

What you need to do

You have been provided with some files on Moodle named customers1.txt, customers2.txt, customers3.txt, customers4.txt,

customers5.txt and regSpeed1.txt, regSpeed2.txt, regSpeed3.txt and regSpeed4.txt. These will

help you to complete this assignment.

You are required to complete the following tasks in this assignment:

1. assign customers by round robin

2. display lines with customer details

3. assign customers to registers by user choice

4. menu to control assignment method

5. computing time to process

6. brute force approach

description

7. greedy approach

Task 1: Assigning customers to lines by round robin

Typically, when a customer is ready to pay for the items in their basket, they will look at the lines and pick

the shortest one to join. We can approximate this behaviour by choosing a round robin approach. This means

that we go through each customer one at a time and assign them to the next line. For instance, if we had 7

customers and 3 lines, we would place customer 1 at line 1, customer 2 at line 2, customer 3 at line 3, customer

4 at line 1, customer 5 at line 2, customer 6 at line 3, and customer 7 at line 1. This would leave line 1 with

three customers and all other lines with two.

Prepare python code which allocates each (valid) customer to one of the available (valid) lines according to this

approach. For instance, given the files customers5.txt and regSpeed4.txt we might find that registers 2 and

3 were empty (as they were invalid) but register 1 had customers 1, 3, 5, 8, 10, 13 and register 4 had customers

2, 4, 6, 9, 11 with customers 7 and 12 not included as they were also invalid.

Task 2: Displaying lines with customer details

For this task, you should setup python code which will allow you to determine the current contents of each line

and display them neatly to the screen. For instance, given the files customers5.txt and regSpeed4.txt we

would output

This will help you track whether later tasks are working correctly.

Task 3: Assigning customers to lines by user choice

For this task, we will simulate allowing a staff member to choose the lines (for registers) customers should join.

You should read in from the user an assignment of customers to registers with commas between customer numbers

and | between different registers (lines). For instance, given the files customers5.txt and regSpeed4.txt

we might display:

Please enter your assignment using customer numbers separated by commas and lines separated by ’|’

and if the user gave us 1,2,3|4,5,6|7,8,9|10,11,12,13 we would output

invalid register (2) assigned customers, line reset to empty

invalid register (3) assigned customers, line reset to empty

invalid customer (12) assigned to a line, customer was ignored

As we can see in the above, there are some invalid customers and register which were chosen by the user; where

this occurs, these selections should be ignored and an appropriate message shown to the user.

Task 4: Use of menu to control customer assignment

As there are now multiple ways for customers to be assigned to registers, update your code so that it first asks

the user which method to apply, for instance it may ask:

Assign customers by

1.Round robin

2.User choice

Please select one of the options above...

and if 1 were selected it would display the results of a round robin assignment, while if 2 were selected it would

request the assignment from the user and display the result as per task 3.

Task 5: Compute processing time

Setup python code which can take any register (line) with customers and compute the time it will take to

process customers in that line. For each line you should use the register speed to determine time to process a

light, average or bulky item (which you would have completed in assignment 1) and then multiply through the

number of each type of item (also completed in assignment 1) for all customers in the line.

You should update your display of lines code to include the total time to process each register line and the

maximum time taken by any register. For instance, given the files customers3.txt, regSpeed1.txt and

choosing a round robin assignment, we might display:

With these assignments, the total time to process all customers is 42 seconds

Task 6: Brute force solution

Prepare a brute force approach to assigning customers to lines such that the dollar value of purchases made per

second is maximised. For instance, given the files customers1.txt, regSpeed1.txt we show several possible

assignments yielding different amounts in dollars per second:

With these assignments, the total time to process all customers is 80 seconds

$5.925 per second

With these assignments, the total time to process all customers is 42 seconds

$11.286 per second

The optimal arrangement (as produced by brute force) is:

With these assignments, the total time to process all customers is 40 seconds

$11.85 per second

For this task, you may assume you will receive at most 4 registers and 6 customers.

Task 7: Written descriptions

Description of your bruteforce algorithm

You should provide a PDF file named description.pdf that describes your bruteforce algorithm to find the

best assignment of customers to registers (lines). Your description must consist of: 1) a high level strategy

written in plain English in enough detail that another student in the unit would be able to understand; and 2)

a justification for why your strategy correctly finds the valid assignment with maximum $ per second.

Description of a greedy strategy to find an assignment of customers to registers

(lines)

You need to provide a greedy approach to solve this task and describe it in a PDF file named description.pdf

that describes your greedy algorithm to find the best (greedy) assignment of customers to registers (lines). Note

that you do NOT need to implement the greedy version of the algorithm – a description of your approach is

sufficient. Your description must consist of:

a high level strategy written in plain English in enough detail that another student in the unit would be

able to understand

a justification of why your algorithm is Greedy.

a discussion on whether your algorithm will find the optimal solution.

a discussion on the complexity of the greedy algorithm versus the brute force approach.