Reference no: EM132699926

Question 1) Consider the following pseudocode:

Input: An array A = (a1, a2, ..., an) of n numbers.
1. For i = 1 to n
2. For j = 2 to A[i] / 2
3. If A[i] % j = 0
4. Then Print false.
5. Go to step 1.
6. Print true.

a. Show the iterations step-by-step of the pseudocode for the in- stance A = (4, 5, 6, 7).
b. Describe the inputs, outputs and the computational problem that the pseudocode solves.
c. What is the computational complexity of the pseudocode? Is it an efficient algorithm or not? Discuss in detail.

Question 2) Assume we have n sensors and a master sensor S0 located in 2- dimensional space. The master sensor S0 knows the (x, y)-coordinates of the other sensors and can calculate the distance of the sensor Si from itself with the following formula:

d(S0, Si) = |x0 - xi| + |y0 - yi| (1)
Given a radius R, the master sensor S0 categorizes the sensor Si according to the distance as following:
• Si is category 1 if d(S0, Si) < R
• Si is category 2 if R ≤ d(S0, Si) < 2R
• Si is category 3 if 2R ≤ d(S0, Si)
As an example, the master sensor S0 is at location (5, 4) and the sensor S1 is at location (2, 2) in Figure 1. Assuming R = 2, the sensor S1 is category 3 since d(S0, S1) = |5 - 2| + |4 - 2| = 5 ≥ 2R = 4.

Figure 1: The master sensor S0 and the other sensors Consider the Category Detection Problem:
Input: The (x, y) coordinates of the sensors S0, S1, ..., Sn, a radius R, and a category value v.
Output: The sensors having category v.
a. Design an algorithm, say Categorization algorithm, that solves
Category Detection Problem. Give the pseudocode of your algorithm.
b. Show the iterations step-by-step of your algorithm for v = 3 on the instance in Figure 1.
c. What is the computational complexity of your algorithm? Is it an efficient algorithm or not? Discuss in detail.

Question 3) Consider the Deviation Sorting Problem:

Input: An array A = a1, a2, ..., an of n numbers.
Output: The sorted absolute deviations (in nondecreasing order) of the numbers from the array average.
Ex: Let A = 3, 5, 8, 10, 9 , then the array average A¯ = 3+5+8+10+9 = 7.
The absolute deviation di of ai from the array average A¯ can be calculated as di = ai A¯ .
Then, the unsorted absolute deviations array can be given as D = 4, 2, 1, 3, 2 .
We obtain the output as 1, 2, 2, 3, 4 after sorting the array D in nondecreas- ing order.

a. Design an algorithm, say Deviation Sorting algorithm, that solves Deviation Sorting Problem. Give the pseudocode of your algo- rithm. (Hint: You may use a sorting algorithm from the lecture.)
b. Show the iterations step-by-step of your algorithm on the in- stance in the example.
c. What is the computational complexity of your algorithm? Is it an efficient algorithm or not? Discuss in detail.

Question 4) Consider the Even Number Problem:

Input: A positive integer k.
Output: kth even natural number (the first even number is 0).

a. Design a recursive algorithm, say Recursive Even algorithm, that solves Even Number Problem. Give the pseudocode of your algo- rithm. Show the iterations step-by-step of your algorithm for k = 4.

b. Alternatively, design an iterative algorithm, say Iterative Even algorithm, that solves Even Number Problem. Give the pseudocode of your algorithm.

c. What are the computational complexities of the recursive and the iterative algorithms? Are they efficient algorithms or not? Discuss in detail.

Attachment:- iterative algorithms.rar