Hi, i would like help understanding the assignmentFIT1045 Algorithms and programming in Python,...

Question

Hi, i would like help understanding the assignmentFIT1045 Algorithms and programming in Python, S2-2019 Assignment 3 (value 20%) Due: Sunday 20th October 2019, 11:55 pm. Objectives The objectives of this assignment are: • To demonstrate the ability to implement algorithms using basic data structures and operations on them. • To gain experience in designing an algorithm for a given problem description and implementing that algorithm in Python. • To demonstrate an understanding of complexity, and to the ability to implement algorithms of a given complexity. Submission Procedure 1. Save your files into a zip file called yourStudentID yourFirstName yourLastName.zip 2. Submit your zip file containing your solution to Moodle. 3. Your assignment will not be accepted unless it is a readable zip file. Important Note: Please ensure that you have read and understood the university’s policies on plagiarism and collusion available at http://www.monash.edu.au/students/policies/academic-integrity.html. You will be required to agree to these policies when you submit your assignment. A common mistake students make is to use Google to find solutions to the questions. Once you have seen a solution it is often difficult to come up with your own version. The best way to avoid making this mistake is to avoid using Google. You have been given all the tools you need in workshops. If you find you are stuck, feel free to ask for assistance on Moodle, ensuring that you do not post your code. Marks: This assignment will be marked both by the correctness of your code and by an interview with your lab demonstrator, to assess your understanding. This means that although the quality of your code (commenting, decomposition, good variable names etc.) will not be marked directly, it will help to write clean code so that it is easier for you to understand and explain. This assignment has a total of 20 marks and contributes to 20% of your final mark. For each day an assignment is late, the maximum achievable mark is reduced by 20% of the total. For example, if the assignment is late by 3 days (including weekends), the highest achievable mark is 70% of 20, which is 14. Assignments submitted 7 days after the due date will normally not be accepted. Detailed marking guides can be found at the end of each task. Marks are subtracted when you are unable to explain your code via a code walk-through in the assessment interview. Readable code is the basis of a convincing code walk-through. 1 http://www.monash.edu.au/students/policies/academic-integrity.html Task 1: Ternary Sorts (4 Marks) Create a Python module called ternary.py. Within this module implement the following task. You may not import any other libraries or modules. Task: Ternary Partition (4 Marks) Write a function ternary partition(lst) that partitions an unsorted list into three sections: smaller than pivot, equal to pivot, larger than pivot. Input: an unsorted list containing one or more integers. Output: a pair of integers, where the first integer is the index of the final position of the pivot, and the second integer is the index of the first element that is larger than the pivot. The pivot should be the element in the 0th position in the original list. To receive full marks the original list must be partitioned; however, the list is not returned. Examples a) Let lst1=[3]. Calling ternary partition(lst1) returns (0,1), as after calling function lst1=[3], thus the pivot section starts at 0 and ends at 1 (exclusive). b) Let lst2=[3,2,2,5,6,3,1,3]. Calling ternary partition(lst2) returns (3,6), as after calling function lst2==[2,2,1,3,3,3,5,6] (or an approximation of this depending on the specifics of the implementation), thus the pivot section starts at 3 and ends at 6 (exclusive). c) Let lst3=[1,2,3]. Calling ternary partition(lst3) returns (0,1), as after calling function lst3==[1,2,3] (or an approximation of this depending on the specifics of the implementation), thus the pivot section starts at 0 and ends at 1 (exclusive). To receive full marks, this function must have a complexity of O(N), where N=len(lst). This means sorting the list then finding the pivot’s location in the list is not a viable solution. Marking Guide (total 4 marks) Marks are given for the correct behavior of ternary partition: (a) 1 mark for an implementation that does not change the original list and without a complexity of O(N); (b) 3 marks for an implementation that does not change the original list and has a best and worst-case complexity of O(N); (c) 4 marks for an implementation that changes the given list to reflect the partitioning (the list is changed ’in place’) and that has a best and worst-case complexity of O(N). Note: marks will be deducted for including print statements or for including function calls outside of function definitions. 2 Task 2: Sudoku (10 Marks) Sudoku is a logic-based combinatorial number-placement puzzle. The objective is to fill a x2 ∗ x2 grid with digits so that each column, each row, and each of the x × x subgrids that compose the grid contain all of the digits from 1 to x2. (For instance, a 9 ∗ 9 grid would contain nine 3 ∗ 3 subgrids.) The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.1 (a) An exemplary Sudoku puzzle ... (b) ... and its solution Create a Python module called sudoku.py. Within this module implement the following five tasks. You are encouraged to decompose the given tasks into additional functions. You may import deepcopy from copy. You may not import any other libraries or modules. To assist with your implementation of the following tasks, you may use the following function subgrid values. This function takes a n×n sudoku grid, a row coordinate, and a column coordinate, and returns a list containing the n values of the subgrid that the item at the coordinates belongs to. def subgrid_values(grid, row, col): val = [] #get dimension of inner box n = int(len(grid)**(0.5)) #get starting row and starting col r = (row//n)*n c = (col//n)*n for i in range(r, r+n): for j in range(c, c+n): val.append(grid[i][j]) return val Part A: Get Grid (1 Mark) Write a function grid from file(file name) that reads in a file containing a sudoku grid and returns the contents of the file as a Python-readable table. Input: a file name file name, where the file contains n lines, and each line contains n entries separated by commas. Each entry will either be a positive integer, or the letter ‘x’. Output: a table represented as a nested list, where each entry in the orignal file is an element in the table, and all numbers have been converted to integers. Examples a) Calling grid from file(‘gridA.txt’) returns: [ [‘x’,‘x’,1,‘x’], [4,‘x’,‘x’,‘x’], [‘x’,‘x’,‘x’,2], [‘x’,3,‘x’,‘x’] ] b) Calling grid from file(‘gridB.txt’) returns: 1Description adapted from Wikipedia. Read more here: https://en.wikipedia.org/wiki/Sudoku. 3 https://en.wikipedia.org/wiki/Sudoku [ [1,‘x’,9,‘x’,‘x’,‘x’,‘x’,6,‘x’], [8,4,‘x’,‘x’,1,‘x’,‘x’,7,5], [‘x’,‘x’,2,‘x’,‘x’,3,‘x’,‘x’,4], [‘x’,‘x’,8,3,2,1,‘x’,4,7], [‘x’,‘x’,5,‘x’,‘x’,‘x’,6,‘x’,‘x’], [4,2,‘x’,6,9,5,8,‘x’,‘x’], [7,‘x’,‘x’,1,‘x’,‘x’,4,‘x’,‘x’], [6,9,‘x’,‘x’,8,‘x’,‘x’,5,3], [‘x’,5,‘x’,‘x’,‘x’,‘x’,7,‘x’,9] ] Part B: Valid Entry (1 Mark) Write a function valid entry(grid, num, r, c) that determines whether a particular value can be entered at a particular location in a valid grid, while maintaining validity. Input: a nested list grid, that represents an n×n sudoku grid; each item in the inner list is either an integer (example 13), or the string ‘x’; a positive integer num, where 0

FIT1045 Algorithms and programming in Python, S2-2019 Assignment 3 (value 20%) Due: Sunday 20th October 2019, 11:55 pm. Objectives The objectives of this assignment are: • To demonstrate the ability...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment