CSCE 210 Fall 2016 Dr. Amr Goneid

Assignment #3

Date: Thu Oct 20, Due: Thu Oct 27, 2016

Solve the following problems and report the solutions in soft form on the current document using Microsoft Office Word or a MathType editor.

  1. For the following code segments, find the worst case number of operations T(n) and the complexity of the segment in terms of the Big-O

Code Segment / Operations to count / T(n) / Big-O
i = 1 ;
while (a[i-1] <= a[i] & i < n) i++ ; / Additions
k = 1;
for (i = 1; i <= n; i++)
for ( j = 1; j <= n/2; j += 2) k *= 2 ; / Multiplications
for (i = 1; i <= n; i++)
for ( j = 1; j <= i; j++) k *= 2 ; / Multiplications
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (a[i,j] != a[j,i]) k++; / Array Element Accesses
[ ]
double Power (double x, int n)
{ double y =1;
if ( n > 0)
{ for (int i = 1; i <= n; i++)
y = y * x; }
return y;
} / Multiplications

______

  1. Find the Big-O for the following number of operations:

No. of Operations / O(. . .)

______

  1. Consider the following algorithm:

ALGORITHM Enigma (n)

k  -1

sum  0

for i = 1 to n do

k  k+2

sum  sum + k

return sum

What does this algorithm do? Find the number of additions T(n) done for a given (n) and the complexity of the algorithm in terms of the Big-O.

______

  1. Consider the following two functions:

void Foo (int x[ ], int i , int j)

{

int y = x[i]; x[i] = x[j]; x[j] = y;

}

void process ( int a[ ], int n)

{

for (int i = n-1; i >= 0; i--)

for ( int j = 1; j <= i; j++)

if ( a[j-1] > a[j] ) Foo (a , j-1 , j);

}

Find the number of array accesses T(n) done by a call of process(a,n) as a function of (n). What is the objective of this algorithm and what is its complexity (Big-O)?

______

  1. Suppose (n) football fans have rated a given football team on a scale of 1 to 5 and the ratings are stored in an integer array A of size (n).
  • Write a function to receive the array and its size and return the most frequent rating.
  • Determine T(n) = number of array element comparisons done by your algorithm.
  • What is the Big-O of this algorithm?

______

  1. Consider the following two functions:

int Fun1 (int n)

{

if (n == 1) return 0; else return (1 + Fun1 (n/2));

}

int Fun2 (int n)

{

int L = 0;

while (n > 1) { n = n/2; L++; }

return L;

}

(a) Trace the two functions for n = 1 , 2 , 4 , 8. To do this, build a table containing (n), the returned value from each function for that (n), and the total number of integer arithmetic operations T(n) needed to achieve the result.

n / Fun1(n) / T1(n) / Fun2(n) / T2(n)
1
2
4
8

(b) What is the complexity (Big-O) of each function?

(c) What are the objectives of these two functions and in what way do they differ?

______

  1. For an array of size (n), suppose algorithm (A) takes 4 n ( log n)2 microseconds to process the array and algorithm (B) takes 28 n log n microseconds to do the same job:
  • For what values of (n) does program (A) take less time than (B)?
  • For each of these algorithms, what will be the time spent to process an array of size 210 ?

______