MCD4710 Assignment 2 (10%) MCD4710 Introduction to Algorithms and Programming
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
Put you name and student ID in a comment at the start of each file in your solution.
You single python file should be named as yourStudentID.py
Save your files into a zip file called yourFirstName_yourLastName.zip
Submit your zip file containing your solution to Moodle.
Your assignment will not be accepted unless it is a readable zip file.
Please ensure that you have read and understood the university’s policies on plagiarism and collusion available at
You will be required to agree to these policies when you submit your assignment.
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.
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.
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.
For each task, you need to write a program that properly decomposes the problem. You will learn functions and decomposition in Week 3.
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.
Total: 100 marks
Code readability (Non-trivial comments where necessary and meaningful variable names) - 10 marks
Code decomposition - 10 marks
Round robin assignment - 10 marks
Display and representation of line contents - 5 marks
User choice assignment - 15 marks
Menu to control assignment method used - 5 marks
Computing processing time - 5 marks
Brute force approach - 25 marks
Description of brute force approach - 5 marks
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.
The student cannot answer even the simplest of questions
There is no sign of preparation
They probably haven’t seen the code before
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
The student seems 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 remember something they were told but now can’t remember
However they clearly know something about the code
With prompting they fail to improve on a partial or incorrect answer
The student seems reasonably 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
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.
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).
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)
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:
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
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:
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, cus- tomers4.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:
assign customers by round robin
display lines with customer details
assign customers to registers by user choice
menu to control assignment method
computing time to process
brute force 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
Register 1 includes customers: 1,3,5,8,10,13 Register 2 is invalid
Register 3 is invalid
Register 4 includes customers: 2,4,6,9,11
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 num- bers 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 Register 1 includes customers: 1,2,3
Register 2 is invalid Register 3 is invalid
Register 4 includes customers: 10,11,13
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:
Register 1 includes customers: 1,4,7,10,13 --- this line will take 19 seconds to process Register 2 includes customers: 2,5,8,11 --- this line will take 28 seconds to process Register 3 includes customers: 3,6,9,12 --- this line will take 42 seconds to process
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:
Register 1 includes customers: 1,4 --- this line will take 21 seconds to process Register 2 includes customers: 2,5 --- this line will take 80 seconds to process Register 3 includes customers: 3 --- this line will take 26 seconds to process
With these assignments, the total time to process all customers is 80 seconds
$5.925 per second
Register 1 includes customers: 3,2 --- this line will take 23 seconds to process Register 2 includes customers: 5 --- this line will take 40 seconds to process Register 3 includes customers: 1,4 --- this line will take 42 seconds to process
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:
Register 1 includes customers: 3,4,5 --- this line will take 33 seconds to process Register 2 includes customers: 2 --- this line will take 40 seconds to process Register 3 includes customers: 1 --- this line will take 22 seconds to process
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.