1

M269: Algorithms, Data Structures and Computability

Tutor-Marked Assignment (KSA Fall 2020/2021)

Cut-Off Date: To be announced

Total Marks: 100

Contents

Warnings and Declaration…………………………………….……………………………………1

Question 1 ……………….…………………………………. ……………………………………..2

Question 2 ………………………………………………………………………………….…..…..2

Question 3 ………………………………………………………………………………….…..…..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:……………………………………………………

Arab Open University

2

Question 1: (40 marks)

A spy wants to destroy espionage evidence. He doesn’t want that destruction to be discovered, he only wants to mislead the investigation team. The evidence is a message in the form of an array of character, where each character has a numeric value as illustrated in the below lookup table. The spy wants to change the characters in the array it in a way that cannot be observed. He plans to do so by subtracting from each character the first small character after it, and if there’s no such character he will keep that character without any change. [Note: for example, to subtract C from E E=5 while C=3 and hence E–C=5-3=2=B. Therefore, E-C=B]

A

B

C

D

E

F

G

H

I

J

K

L

M

1

2

3

4

5

6

7

8

9

10

11

12

13

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

14

15

16

17

18

19

20

21

22

23

24

25

26

For example, the message is [A, E, F, C, B] the result will be [A, B, C, A, B]. Observe how we subtracted C from E and F. We also subtracted B form C, while keeping A and B without any change.

Given the original message, you must implement the subtractions trick as fast as you can, otherwise, the investigation team will catch you.

Inputs

output

Ex1:

[A, G, D, E, F, B]

[A, C, B, C, D, B]

Ex2:

[A, B, A, F, C]

[A, A, A, A, C]

Ex3:

[A, E, B, B, D]

[A, C, B, B, D]

Ex4:

[A, B, E]

[A, B, E]

a) Using a brute-force approach, design an algorithm to solve this problem (5 marks), and analyze its complexity (5 marks)

b) Implement your algorithm using Python (10 marks)

c) Design a more efficient algorithm to solve this problem (10 marks), and analyze its complexity (5 marks) [Hint: you can use any data-structure]

d) Prepare a brief report (250 words) comparing the two algorithms (5 marks)

Question 2: (40 Marks)

Given a group of boxes carried on a fork lift truck, it is requested to arrange these boxes on top of each other to reach the minimum possible height. To enable the driver to control the stability of the boxes, it is mandatory that a box “X” cannot be placed on top of another box “Y” unless the 2D base area of X is less than or equal to 2D base area of Y. It is allowed to rotated any box to use any two sides as its base.

3

For example, consider below 3 boxes where each box has the following dimensions

Input:

Box 1: (9,3,6),

Box 2: (2,3,7),

Box 3: (6,4,10)

Output:

From bottom to top as follows:

Box 3 on the base (6,10) and height 4,

then Box 1 on the base (6,9) and height 3,

finally, on top Box 2 on the base (3,7) and height 2.

The total height is 9

[Explanation: as we can see that the first box in the bottom is the box 3 with base 6×10 and height 4, then box 1 with base 6×9 and height 3, and so on. This arrangement of boxes fulfils the stability constraint and also satisfies the minimum possible height]

Assume the existence of n boxes, answer the following questions:

a) Describe how a brute-force approach algorithm would solve the above problem (5 marks), and explain its complexity (5 marks).

b) Design a more efficient algorithm to solve this problem. Explanation and pseudo code should be provided (10 marks). Analyze the complexity of your solution. (5 marks) [full explanation of your answer should be provided]

c) Implement Both of the above algorithm using Python (10 marks)

d) Prepare a brief report (250 words max) to describe the difference between the performance of the two algorithm in case of big number of input boxes. (5 Marks)

Question 3: (20 marks)

Find the complexity of the following blocks of code or algorithm’s description. [Note: your answer must show the steps that lead to your final answer] (4 marks each)

1)

int BinDig (int n)

{ if (n == 1) return 1;

else return (Comp(n) + BinDig(n/2) + BinDig(n/2)); }

[Given that Comp(n) is a function with complexity O(n2)]

2)

def F(n):

if n == 0:

return 0

elif n == 1:

return 1

else: return F(n-1) + F(n-2)

3)

The algorithm solves the problem by breaking it into 8 sub-problems of n/2 the scale, recursively solving each sub-maze, and then combining the solutions in linear time O(n)

4)

The algorithm solves the problem of size n by dividing it into 16 sub-problems of size n/2, recursively solving each sub-problem, and then combining the solutions in O(n4) time

4

5)

count = 0

for i = 1 to 100 do

for k = 1 to 100 do

for (j = 2; j < n; j *= 2) count = i + k + j;
end for
end for
end for
Note:
You should submit all your answers for the above mentioned questions in one big word file (one after the other). The file should contain the following items for each question:
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 Assessment

Payment Methods

All online transactions are done using all major Credit Cards or Electronic Check through PayPal. These are safe, secure, and efficient online payment methods.

Our customer support team is here to answer your questions. Ask us anything!

👋 Hi, how can I help?