Description
Algorithms, Data Structures and
Computability HM
Unformatted Attachment Preview
M269: Algorithms, Data Structures and
Computability
KSA – TMA Spring 23/24
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 / KSA – TMA
Page 1 of 3
2023/2024 Spring
Question 1 (30 marks)
Assume the existence of an even number of positive integers 2n written on a piece of
paper. You decided to play with the numbers, where you start with a score of 0. You will
increase your score by performing the following move exactly n times:
1) Choose two integers A and B from the numbers written on the paper.
2) Add min (A, B) to your score.
3) Erase A and B from the paper.
Note that after performing the move n times, there will be no more integers written on the
paper. Find the maximum final score you can achieve if you optimally play this game:
Examples:
Input
output
Test case 1:
[ 7, 4, 5, 10, 2, 1, 7, 8, 2, 1]
22
Test case 2:
[10, 2, 5, 8, 4, 6, 1, 6]
19
Test case 3:
[1,2,1,1,1,1,]
3
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)
Question 2: (30 Marks)
Assume the existence of n different integers in a list. You have to perform exactly k
operations with it. During each operation, you can do exactly one of the following two
actions (you choose which to do yourself):
find the two minimum elements in the list, and delete them
find the maximum element in the array, and delete it.
Remember that you have to do so for k times to get the minimum possible sum of
elements in the resulting list.
Examples:
Test case 1:
Test case 2:
Test case 3:
Input
output
K=2
List = [ 9, 5, 6, 8, 9, 7, 10, 8, 12, 7, 10]
K=3
[10, 4, 6, 1, 3, 5, 8, 6, 4]
K=1
[5, 8, 6, 4, 10, 9, 6, 7, 2, 5, 8]
68
M269 / KSA – TMA
Page 2 of 3
23
60
2023/2024 Spring
Answer the following questions:
a) Design an algorithm with the least possible complexity to play this game (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
M269 / KSA – TMA
Page 3 of 3
2023/2024 Spring
Purchase answer to see full
attachment
