(5/5)

Exercise 1 [20 points]

Let T 1 (n) be the total number of times that x = x + 1 executes the routine

FindMyCompexity1 () and T 2 (n) the total number of times the command x = x + 1 is executed by

routine FindMyComplexity2 (). Calculate T 1 (n) and T 2 (n). Study the class (symbolism O)

of T 1 (n) and T 2 (n).

procedure FindMyComplexity1 (integer n)

for i = 1 to n do

for j = 1 to √ n do

for k = 1 to n - j +1 do x = x + 1;

}

procedure FindMyComplexity2 (integer n)

for i = 1 to 2n do

if (i% 2 == 1) then

for j = i to 2n do x = x + 1;

}

Exercise 2 [25 points]

a. Which of the following is true and why?

i. n 5 - 5n 3 - 5n 2 +10 = Θ (n 5 )

ii.

(2 * (2))

1

n

i

i

+

∑

=

= O (n 2 )

iii. min (2 70 , n 3 log n) = Θ (1)

b. Consider the asymptotic complexity (based on the symbolism I) of the function

f (n) = n 2 log n 3 + n 2

n - n 2 log n -3

Page 2

Exercise 3 [25 points]

Resolve the following retroactive replacement relationships.

a.

[7M]

b.

, where c is an integer constant. [8M]

For the retrospective relationship of question a. the following are requested:

i. Design the backdrop

[5M]

ii. Verify, using mathematical induction, that the solution you found with iterative

replacement is correct.

[5M]

Exercise 4 [30 points]

Consider the following retrospective algorithm, which is executed on a non-sorted

table of integers T [s ... u] with n = u-s + 1 = 2 k (k> 0), where s, u, u> s are positive integers which

specify the first and last element of the table.

int RecursiveF (table T: array of int, int s, int u) {

int middle; int val;

if (us == 0) return T [s];

middle = ⌊ (s + u) / 2 ⌋ ;

for j = s to middle do {

if (T [j]> T [j + middle]) then

swap (T [j], T [j + middle]);

}

val = RecursiveF (T, s, middle);

return val;

}

a. What does RecursiveF calculate? Please provide a brief description of how it works. [7M]

b. Track RecursiveF (T, 1.8) for case T = [20,4,40,60,34,16,38,2]. Present

a brief description of how the algorithm works.

[8M]

c. Formulate a retrospective relationship for the RecursiveF runtime ().

[5M]

d. Solve the retroactive relationship you proposed in question c. and study (based on

of symbols O and Z) the order of its complexity.

[5M]

e. What is the spatial complexity of the algorithm (that is, how much memory is needed to execute it

the algorithm);

[5M]

Google Translate

Original text

Παναγιώτα Φατούρου

Contribute a better translation

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of