- May 15, 2020
MCD4710 Assignment 2 (10%) MCD4710 Introduction to Algorithms and ProgrammingThe 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 problemsbrute-force approaches to problemsbacktracking approaches to problemsSubmission ProcedurePut 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.pySave your files into a zip file called yourFirstName_yourLastName.zipSubmit your zip file containing your solution to Moodle.Your assignment will not be accepted unless it is a readable zip file.Important Notes:Please ensure that you have read and understood the university’s policies on plagiarism and collusion available athttps://www.monashcollege.edu.au/ policy.pdfdata/assets/pdf_file/0010/17101/dip-assessment-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.Marking Criteria:Total: 100 marksCode readability (Non-trivial comments where necessary and meaningful variable names) – 10 marksCode decomposition – 10 marksRound robin assignment – 10 marksDisplay and representation of line contents – 5 marksUser choice assignment – 15 marksMenu to control assignment method used – 5 marksComputing processing time – 5 marksBrute force approach – 25 marksDescription of brute force approach – 5 marksDescription of a greedy approach – 10 marksAssignment code interviewEach 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 Rubric0The student cannot answer even the simplest of questionsThere is no sign of preparationThey probably haven’t seen the code before0.25There is some evidence the student has seen the codeThe answer to a least one question contained some correct pointsBut it’s clear they cannot engage in a knowledgeable discussion about the code0.5The student seems underpreparedAnswers are long winded and only partly correctThey seem to be trying to work out the code as they read itThey seem to be trying to remember something they were told but now can’t rememberHowever they clearly know something about the codeWith prompting they fail to improve on a partial or incorrect answer0.75The student seems reasonably well preparedQuestions are answered correctly for the most part but the speed and/or confidence they areanswered with is not 100%With prompting they can add a partially correct answer or correct an incorrect answer1The student is fully preparedAll questions were answered quickly and confidentlyIt’s absolutely clear that the student has performed all of the coding themselves.BackgroundYou 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 TypeLight itemAverage ItemBulky ItemScanning TimeL2 × L5 × LTable 1: relation between item type and scanning timeNot 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 OperatorLight item (seconds)Average item (seconds)Bulky item (seconds)Bill4820Lee2410Tanya3615Sasha125Table 2: scanning times (in seconds) for sample register operatorsBackground: Customer File FormatYou 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 soL5,A2,L1 l2,B20B207,a15,b20,l6,A12This 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 FormatYou 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:3641There 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 doYou 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 robindisplay lines with customer detailsassign customers to registers by user choicemenu to control assignment methodcomputing time to processbrute force approachdescriptiongreedy approachTask 1: Assigning customers to lines by round robinTypically, 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, customer4 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 customers2, 4, 6, 9, 11 with customers 7 and 12 not included as they were also invalid.Task 2: Displaying lines with customer detailsFor 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 outputRegister 1 includes customers: 1,3,5,8,10,13 Register 2 is invalidRegister 3 is invalidRegister 4 includes customers: 2,4,6,9,11This will help you track whether later tasks are working correctly.Task 3: Assigning customers to lines by user choiceFor 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 outputinvalid 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,3Register 2 is invalid Register 3 is invalidRegister 4 includes customers: 10,11,13As 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 assignmentAs 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 choicePlease 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 timeSetup 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 processWith these assignments, the total time to process all customers is 42 secondsTask 6: Brute force solutionPrepare 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 processWith these assignments, the total time to process all customers is 80 seconds$5.925 per secondRegister 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 processWith these assignments, the total time to process all customers is 42 seconds$11.286 per secondThe 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 processWith these assignments, the total time to process all customers is 40 seconds$11.85 per secondFor this task, you may assume you will receive at most 4 registers and 6 customers.Task 7: Written descriptionsDescription of your bruteforce algorithmYou 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 strategywritten 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 understanda 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.