Order from us for quality, customized work in due time of your choice.
Cut-Off Date: Based on the Published Deadline. Total Marks: 60 marks to 15 mar
Cut-Off Date: Based on the Published Deadline. Total Marks: 60 marks to 15 marks
Contents
Warnings and Declaration…………………………………….…………………………………….1
Problem 1 ……………….…………………………………. ………………………………………2
..
Problem 2 ………………………………………………………………………………….…..… …3
Marking Criteria ……………..………………………………………………………….………..… 4
Plagiarism Warning:
As per AOU rules and regulations, all students are required to submit their own TMA work and avoid plagiarism. The AOU has implemented sophisticated techniques for plagiarism detection. You must provide all references in case you use and quote another person’s work in your TMA. You will be penalized for any act of plagiarism as per the AOU’s rules and regulations.
Declaration of No Plagiarism by Student (to be signed and submitted by student with TMA work):
I hereby declare that this submitted TMA work is a result of my own efforts and I have not plagiarized any other person’s work. I have provided all references of information that I have used and quoted in my TMA work.
Name of Student:…………………………….. Signature:…………………………………………… Date:…………………………………………………
M269 / TMA-KSA Page 2 of 3 2023/2024 Summer
Question 1 (30 marks)
Consider is a game with the following rules:
There are n boxes full of identical toys randomly distributed among these boxes. Your game consists of two steps:
1. Chooses an arbitrary box from the existing n boxes, let’s say box i.
2. You have to move all toys from the selected box i and distribute them on the other boxes.
If you can distribute the toys taken from box i on the other remaining n-1 boxes in a way that makes all the remaining boxes having exactly the same number of toys, then you win the game, otherwise you lose it. In order to win this game, you are allowed to get rid of some toys from the existing boxes in such a way that no matter which box i you choose, you will win. What is the minimum number of toys you will need remove before paying this game in order to always win?
Examples:
Input
Output
Explanation
Test case 1:
[ 7, 4, 4]
(i.e., there are three boxes, where the 1st box has 7 toys, 2nd and the 3rd boxes have 4 toys each)
1
In fact, no matter which box you select, you will never be able to win unless you get rid of at least one toy from any of the existing boxes. You can do this by removing one of them [6,4,4] or [7,4,3] or [7,3,4]. This will enable you to play the game and win no matter which box i you may choose. Explanation:
Ending with having exactly the same number of toys over the n-1 boxes.
Test case 2:
[6,4,4,4]
0
In the second test case, you don’t need any extra toy, since no matter which box you choose, you can always make other boxes equal.
Test case 3:
[4,0,0,]
4
In the third test case, you should use least 4 extra toys into the 2nd or 3rd box and make them distributed as [4,0,4] or [4,4,0] or [4,2,2]. In this way, no matter the box you will choose, you can always win.
a) Design an algorithm to solve this problem with the least possible complexity (10 marks),
b) Analyse the complexity of your solution. (4 marks)
c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case]
d) Prepare a brief report (250 words) comparing your algorithm with the brute force approach (6 marks)
M269 / TMA-KSA Page 3 of 3 2023/2024 Summer
Question 2: (30 Marks)
Given an array of different character, replace each character by its corresponding descending order in the array.
Examples:
Input
output
Test case 1:
[K, L, Q, N, F, B, R]
[5, 4, 2, 3, 6, 7, 1]
Test case 2:
[J, L, A, Y, R, W, D, S]
[6, 5, 8, 1, 4, 2, 7, 3]
Answer the following questions:
a) Design an algorithm with the least possible complexity to solve this problem (10 marks)
b) Analyse the complexity of your solution. (4 marks)
c) Develop a python code to implement your algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case]
d) Prepare a brief report (250 words) comparing your algorithm with the brute force approach (6 marks)
Note:
You should submit all your answers in one big word file. The following table provide a guide on how your answers will be evaluated.
Criterion
Unsatisfactory
Average
Good
Algorithm Design
Incomplete.
? Complete but looks like an essay not a professional algorithm.
? 100% Complete and in a professional format ? Explanation of the pseudo-code is provided ? looks efficient in terms of running time and of memory usage ? Comments on the efficiency
Implementation Using Python
? Incomplete ? Poor use of white space (indentation, blank lines, ambiguous naming of variables)
? Organized work, with correct use of space, variables, and naming.
Completed 100% Comments on the code Screen shot of the run and comments. Organized indentation with good use of variables Tested with any simple input case study. ? Documented briefly in terms of (input, output, functions purposes)
Complexity analysis
? No answer
? Incomplete answer or partially correct.
? Completed 100%. Explanation is provided.
Report
? Irrelevant text or no answer.
? some effort but the report is not organized
? Logical representation of the arguments in terms of problem’s categories, solving technique, complexity, memory consumption and ending with a correct conclusion.
End of Document
Order from us for quality, customized work in due time of your choice.