Exercises Project and Analysis of Algorithms
Uploaded by
ScribdTranslationsExercises Project and Analysis of Algorithms
Uploaded by
ScribdTranslationsBCC241 - PROJECT AND ANALYSIS OF ALGORITHMS
EXERCISE LIST E1
1. In each item indicate and explain if f=O(g), f = (g), f=o(g), f= (g) or f= (g)
f g
a. n -100 n-200
b. n1/2 n2/3
c. log n log2n
d. 10 log n log n2
e. n2 n log n
1/2
f. n 5log2n
n
g. 2 2n plus one
h. n! 2n
2. Exercise 0.4 a and b of DPV.
3. Fill in the table below, providing the time spent by a program, to
resolve a problem with instances of size n. Consider the time for each
instruction/step of 10-6seconds and the complexity function specified in each
line.
Instance size (N)
Function of
70
Complexity 10 30 40 50 60
N + 10
2N2+N + 5
2N+ N2
4. For each function f(n) and each time t in the table below, determine the largest size.
in a problem that can be solved in time t, assuming that the algorithm
to solve the problem takes f(n) microseconds.
f(n) t 1 second 1 minute 1 hour 1 day
lg n
n
n2
n3
2n
n!
5. The table below shows the size of the largest instance of a problem that a
the current computer can solve in 1 hour, given the complexity function of
algorithm. Fill in the table showing the largest instance size that is
can solve in one hour on a computer 100 times and 1000 times more
faster than the current one
Largest instance that a computer solves in 1 hour
Function of Current Computer Computer 100x Computer 1000x
complexity faster faster
N N
n2 M
4
n P
n
4 R
6. You have two algorithms A1 and A2 to solve the same problem. The function
the complexity of the same is respectively. Which
Which algorithm would you choose? Discuss all the possibilities.
7. Using divide and conquer, multiply 10011011 and 10111010.
8. Exercise 2.3 of the DPV.
Exercise 2.4 of the DPV.
10. Exercise 2.5 of the DPV. Up to e)
11. Exercise 2.12 of the DPV.
12. Provide the algorithm that informs the median of a vector in O(n).
13. Let the following piece of pseudocode be:
a = 0;
for i=0..n:
for j=1..i:
for k=j+1..j+i:
a = a + 1;
Define the value of the function den.
14. Prove by induction:
n
1 n
a)
i 1
i(i 1n) 1
n
i a n1 a
b) a
i 1 a 1
( ( ) )
c) ∑
15. Prove that ( () ) ( ).
16. Responda com V ou F. Justifique sua resposta por item.
A polynomial-time complexity algorithm is always preferred to an algorithm of
exponential complexity order.
The worst-case time complexity T of an algorithm A is Ω(n)2), so it is possible that T
it can be O(n) for some inputs of A.
logn2 long 5
3n 2
n
n 2logn (n n)
T(n) n2
64Tn/8 (n2)
Whenever f=O(h) and g=O(h), f=O(g)
If f if g e f=O(g) then g=O(f)
The functions n.log(n) and n.log(n.n) have the same order of complexity.
log(ncθ(log(n)) for any constant c>0
2100is O(1)
2n-1 = O(2n)
2n= (2n-1)
17. Find the complexity of each of the following program snippets:
a) Two loops in sequence:
for (i = 0; i < N; i++) {
sequence of commands
}
for (j = 0; j < M; j++) {
sequence of commands
}
What happens if we replace the complexity of the second loop with N instead of M?
b) A nested loop followed by a non-nested loop:
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
sequence of commands;
}
}
for (k = 0; k < N; k++) {
sequence of commands
}
c) A nested loop where the number of times the innermost loop runs depends on the value
of the index in the outermost loop:
for (i = 0; i < N; i++) {
for (j = i; j < N; j++) {
sequence of commands
}
}
18. Find the best-case and worst-case complexity of the following excerpt from
program:
if (x == y) {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
sequence of commands;
}
}
for (i = 0; i < N; i++) {
sequence of commands
}
}
else {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
sequence of commands;
}
}
}
}
