Scribd
Upload
5 views

3-midterm1-algorithms-exams-final-midterms-and-quizzes

midterm

Uploaded by

thandiwegreens
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views

3-midterm1-algorithms-exams-final-midterms-and-quizzes

midterm

Uploaded by

thandiwegreens
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

lOMoARcPSD|48073138

3-Midterm#1 - Algorithms exams final midterms and quizzes

Design And Analysis Of Algorithms (‫)رطق ةعماج‬

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university


Downloaded by Naivete tandiwe ([email protected])
lOMoARcPSD|48073138

Qatar University
College of Engineering
Department of Computer Science and Engineering
CS323- Design and Analysis of Algorithms –2014

Name: ID:

Midterm#1- 7/4/2014
Duration: 60 Minutes
Question#1: (5 pts)
a) Prove that: ( n4 -n + n 1/2 logn ) is O (n4).

b) Prove that n+n3 is not O(n).

c) Prove the following propositions:

logn + n is θ(n).

n5 + n is Ω (n2).

5n is o(7n)

d) Order the following complexity functions in increasing growth order:

9n , 2 n*n, n71 , nlogn , n!, 2n, n+ logn , 7, (logn)2

Downloaded by Naivete tandiwe ([email protected])


lOMoARcPSD|48073138

Question#2: (5 pts)

1- Find the solution of the following recurrence relation:

T(n) – 2T(n-1) + T(n-2) = 2n (1)

T(0) = 3 ; T(1)=5

2- Write a divide and conquer algorithm to calculate T(n) by using the recurrence relation (1).

3- Find, then solve the recurrence relation giving the number of recursive calls of the
algorithm developed in (2) in terms of n.

Downloaded by Naivete tandiwe ([email protected])


lOMoARcPSD|48073138

Question#3: (5 pts)

Let A be an array of size 5 indexed from 1 to 5. Using sequential search, find the expression of the
average number of key comparisons in A, where the probability to find the searched key (x) in the
array at position i is (1/5i ).
Hint: Give first then the expression of the probability to not find the key x in A..

Downloaded by Naivete tandiwe ([email protected])


lOMoARcPSD|48073138

Question#4: (5 pts)

Analyze the exact time complexity of the following algorithms:

a)
//Begin Here
For i=1 to n
For j=1 to n
For k=1 to n*n
Print ('loop');
For j=1 to n
For k=1 to n
Print (“loop”);
//End here

b)
i=n;
While (i>=1)

{ j=1;
while (j<=n) j=j*2;

i=i/2;
}

Where n is a power of 2.

Downloaded by Naivete tandiwe ([email protected])


lOMoARcPSD|48073138

c)
for (i=1; i<=n; i++)
for (j=1;j<=i; j++)
for (l=1;l<=27;l++);
print ("Hello");

d)

for i=1 to n-3


for j=i+1 to n-2
for k=j+1 to n-1
for m=k+1 to n
print (i, j, k,m);

Downloaded by Naivete tandiwe ([email protected])


lOMoARcPSD|48073138

Question#5: ( 5 pts)

a) (4 pts) Assume that you have an array A of sorted integer numbers of size n. By using a divide
and conquer algorithm, write an algorithm to find the total number of items smaller or equal that
some value V.

b) (1 pts) Find a recurrence equation of the time complexity. Solve this equation.

Downloaded by Naivete tandiwe ([email protected])


lOMoARcPSD|48073138

Question#6: (5 pts)

Let A be the following array if size 8 :

8 5 3 6 9 2 1 4

Explain the different levels of recursive calls to sort A by using Mergesort.

Let n be the size an array to sort. Compare the time complexity of Mergesort, Quicksort in the best,
average and worst cases.

Excellent Exam

Downloaded by Naivete tandiwe ([email protected])

You might also like