1) Provide an algorithm in pseudocode that calculates the mode of a given list.
ID: 3712745 • Letter: 1
Question
1) Provide an algorithm in pseudocode that calculates the mode of a given list.
The mode is the value that is repeated more often in the list.
a. Study the attributes and comment their efficiency. Detect the main work unit and calculate the Order of magnitude in terms of space and time
b. Comment the results
2) Write a piece of the algorithm in Assembly code (Just 20 Assembly instructions)
3) Based on the assembly instructions in 2), describe the flow of signals occurring in the ALU, Memory, IO and control unit.
Explanation / Answer
ANS:-
Algorithm 1:
Algorithm 2:
Triplet Adjust(A, i, Step)
Let j= i+Step and k= i+2Step; this procedure moves the median of a triplet of
terms at locations i; j; kto the middle position.
if (A[i]< A[j])
then
if (A[k]< A[i]) then Swap(A[i]; A[j]);
else if (A[k]< A[j]) then Swap(A[j]; A[k]);
else
if (A[i]< A[k]) then Swap(A[i]; A[j]);
else if (A[k]> A[j]) then Swap(A[j]; A[k]);
Approximate Median(A, r)
This procedure returns the approximate median of the array A[ 0; :::;3
r1].
Step=1; Size=3
r
;
repeat rtimes
i=(Step1)/2;
while i <Size do
Triplet Adjust(A, i, Step);
i=i+(3Step);
end while;
Step = 3Step;
end repeat;
return A[(Size 1)=2];
b. Run time analysis:
In algorithm 1: complexity depends on the sort algorithm , if select sort then worst case time is O(n2) similarly for others
In algorithm 2:
Given an input of size n, the algorithm Approximate Median performs fewer than 4/3n comparisons and 1/3n exchanges on the average.
Implementation of algorithm 1:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.