MCD4710 Assignment 1 (8%)MCD4710 Introduction to Algorithms and ProgrammingObjectivesDue: Thursday, April 4, 2019, 5:00 pm - Week 6The 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 problemsSubmission Procedure1. Put you name and student ID in a comment at the start of your file in your solution.2. Save your file into a zip file called YourStudentID.zip3. Submit your zip file containing your solution to Moodle.4. 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-assessment- policy.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 focusing 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.Marks: This assignment has a total of 50 marks and contributes to 8% of your final mark. Late submission will have 5% 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?2Marking Criteria:Total: 50 marksA. representation and display (20 marks)B. checking correctness (10 marks)C. generating a quilt of size N x M with random placement of X’s (10 marks)D. decomposition, variable names and documentation (10 marks)Assignment 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 questions There 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 remember However 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 are answered 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.3Background:This assignment has you working on representing a coloured quilt as a table and deciding which colour should occupy each square. In this problem, you have a rectangular quilt. Some of the squares in the quilt will need to be coloured. These are marked with “X”. No square can be the same colour as any of the surrounding eight squares. Note that wrap around is not considered in this problem so a square on the right end does not need to be different to one on the left end (unless they Note: The size of the quilt will never be greater than 10 x 10 and the number of coloured squares to be filled in will never exceed 15 squares i.e. there will never be more than 15 X’s in a file. We will only use four colours. Any more than 4 will take too long to run if you use brute-force.4Task 1: Representation and display (20 marks)The simplest representation of this problem would be to represent the quilt as a table, where ‘X’ marks the squares to be coloured and ‘ - ‘ marks the squares that don’t need to be coloured. Integers can be used to represent the colours with each integer representing a different colour (see table 1, 2, and 3).Part A: Initial setup (5 marks)Write a python function which takes as input the name of a file in which the quilt is stored and produces a two dimensional table (list of lists) to represent this quilt.Part B: Display (5 marks)Extend your program such that the colours of any given quilt can be displayed on the screen. Combining this with the initial setup might yield the following output:Enter the name of the file? Quilt.txtThe quilt is currently as below:X X - -- X - XX X X -- X - -Part C: File input/output (5 marks)Extend your program so that you are able to do the following:? write to a new file the current quilt state (which is saved in your list of lists created in Part A). The user should be asked for the name of the file.? read from a user entered file and update the current quilt state i.e. your list of lists.Hint: if you read from the file you just wrote to, your quilt state will be unchanged.Part D: Menu (5 marks)Write a menu which allows the user to choose from a set of options to perform; e.g.:What would you like to do?1. read quilt2. write quilt3. check for correctness4. exit?1Please enter a valid filename: example.txtX X - -- X - XX X X -- X - -what would you like to do?1. read quilt2. write quilt3. check for correctness4. exit?5Task 2: Correctness: (10 marks)This part is about how to ensure the representation is in fact a valid quilt colouring.Extend your python program (and menu) so that it can take a representation of the quilt state and determine whether any two adjacent squares have the same colour.Where any two adjacent squares are the same colour it prints invalid quilt to the screen, otherwise it prints valid quilt to the screen.For example, consider the three quilts below:0 1 - -- 2 - 00 1 3 -- 2 - -0 1 - -- 2 - 00 1 2 -- 2 - -0 - - - - - - - 0- 1 - - - 0 1 2 -0 - - 0 1 - - - 0- 1 2 - - 0 1 2 -? The first colouring here is valid.? The second colouring is invalid as the 2 in the second row and second column has a 2 around it in the third row and third column.? The third colouring is also valid but shows an example of a 9 × 4 instead.Extend your program so that it uses your file reading code to determine the correctness of a file holding a representation of the quilt. If the examples above were stored in quilt1.txt, quilt2.txt and quilt3.txt respectively then the expected behaviour is as below:what would you like to do?1. read quilt2. write quilt3. check for correctness4. exit?3Please enter a file to check: quilt1.txtvalid quiltWould you like to check another file? YPlease enter a file to check: quilt2.txtinvalid quiltWould you like to check another file? YPlease enter a file to check: quilt3.txtvalid quiltWould you like to check another file? Nwhat would you like to do?1. read quilt2. write quilt3. check for correctness4. exitTask 3: Generating random quilts (10 marks)In this task you will need to ask the user the dimensions of the quilt, N and M. You will also ask the user to enter the number of X’s they want in the quilt. You will use these values to generate a new quilt of size N x M in which the X’s are randomly place in the quilt. You will need to check that the user has entered values that makes sense e.g. if the user enters 5 x 4 for the quilt size, they should not be able to enter a value of 21 for the number of X’s. The minimum number of X’s allowed should be greater than 20% of N x M.Task 4: Decomposition, Variable names and code Documentation (10 marks)Marks will be allocated for good use of variable names, code documentations and proper decomposition.本团队核心人员组成主要包括BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论