Xem mẫu
Faculty of Computer Science and Engineering Department of Computer Science
DATA STRUCTURES & ALGORITHMS Tutorial 1 Questions COMPUTATIONAL COMPLEXITY
Required Questions
Question 1.
Reorder the following efficiencies from the smallest to the largest: a. 2n3 + n5
b. 2000 c. 4n+1 d. n4
e. (n-1)! f. nlog2(n)
g. 2klogk(n) (k is a predefined constant)
Question 2.
Determine the big-O notation for the following: a. 2n6
b. 100n + 10.5n2/3 + 5.2n5/7 c. 9log2(n)
d. 5n10 + 2logn
e. n! + k! (k is a predefined constant) f. 100log2(n) + 5(n+2n)
Question 3.
Calculate the run-time efficiency of the following program segment: 1 i = n-1
2 loop (i >= n/2) 1 j = 1
2 loop (j < n/2)
1 print(i, j) 2 j = j + 2
3 end loop 4 i = i - 2
3 end loop
Question 4.
Calculate the run-time efficiency of the following program segment: 1 i = n3
2 loop (i >= n/2) 1 j = 1
2 loop (j < n/2)
1 print(i, j) 2 j = j + 2
3 end loop 4 i = i / 2
3 end loop
Released on 24/08/2012 20:06:39 1/4
Faculty of Computer Science and Engineering Department of Computer Science
Question 5.
If the algorithm doIt has an efficiency factor of 2n, calculate the run time efficiency of the following program segment:
1 i = 1
2 loop (i <= n) 1 j = 1
2 loop (j < n) 1 k = 1
2 loop (k <= n) 1 doIt(…) 2 k = k *2
3 end loop 4 j = j + 1
3 end loop 4 i = i + 1
3 end loop
Question 6.
Given that the efficiency of an algorithm is 2nlog (n4), if a step in this algorithm takes 1 nanosecond (10−9), how long does it take the algorithm to process an input of size 1024?
Question 7.
Write a recurrence equation for the running time T(n) of g(n), and solve that recurrence. Algorithm g (val n )
Pre n must be greater than 0
Return integer value of g corresponding to n 1 if (n = 1)
1 return 1 2 else
1 return g(n – 1)+ 1 End g
Released on 24/08/2012 20:06:39 2/4
Faculty of Computer Science and Engineering Department of Computer Science
Advanced Questions
Question 8.
Prove that for any positive functions f and g, f(n) + g(n) and max(f(n), g(n)) are asymptotically equivalent (i.e. they yield the same big-O notations).
Question 9.
Estimating the time complexity of the following program segment: 1 i = 0
2 loop (i < N) 1 j = i
2 loop (j < N) 1 k = 0
2 loop (k < M) 1 x = 0
2 loop (x < K)
1 print(i, j, k) 2 x = x + 3
3 end loop 4 k = k + 1
3 end loop 4 k = 0
5 loop (k < 2*K) 1 print(k) 2 k = k + 1
6 end loop 7 j = j + 1
3 end loop 4 i = i + 1
3 end loop
Question 10.
Calculate the run-time efficiency of the following program segment: 1 i = n
2 k = n/3
2 loop (i >= k)
1 j = n – 2*k 2 loop (j < i)
1 print(i, j) 2 j = j + 2
3 end loop 4 i = i - 1
3 end loop
Question 11.
Write a recurrence equation for the running time T(n) of f(n), and solve that recurrence. Algorithm f (val n )
Pre n must be greater than 0
Return integer value of f corresponding to n 1 if (n <= 1)
1 return 1 2 else
Released on 24/08/2012 20:06:39 3/4
Faculty of Computer Science and Engineering Department of Computer Science
1 return f(n – 1) + f(n – 2) End
Question 12.
Solve recurrence f(n) = 2f(√n) + log2n. (Hint : change variables, with m = 2n)
-- End --
Released on 24/08/2012 20:06:39 4/4
...
- tailieumienphi.vn
nguon tai.lieu . vn