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]