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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

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

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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