Final project (3 parts) Provide 2 algorithms in pseudocode that calculates the m

Question

Final project (3 parts)

Provide 2 algorithms in pseudocode that calculates the median or the mode of a given list. (Choose median or mode)

The mode is the value that is repeated more often in the list.

a.       Compare the attributes of both of them and comment their efficiency. Mention their Order of magnitude in terms of space and time (number of comparisons)

b.       Implement the algorithms in high-level language and run them several times. Increase the number of the list (You can create a loop to fill up an array with random numbers)

c.       Comment the results

2)      Choose one of the algorithms and start writing it in Assembly code (Just the first 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

Algorithm 1:

procedure median()  

   Array A

   Size N

   SORT(A)

   middle = (N + 1) / 2

   DISPLAY A[middle] as median

end procedure

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:

#include <stdio.h>

void swap(int *p,int *q) {

   int t;

   t=*p;

   *p=*q;

   *q=t;

}

void sort(int a[],int n) {

   int i,j,temp;

   for(i=0;i<n-1;i++) {

      for(j=0;j<n-i-1;j++) {

         if(a[j]>a[j+1])

            swap(&a[j],&a[j+1]);

      }

   }

}

int main() {

   int a[] = {6,3,8,5,1};

   int n = 5;

   int sum,i;

   sort(a,n);

   n = (n+1) / 2 - 1; // -1 as array indexing in C starts from 0

   printf("Median = %d ", a[n]);

   return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.