Theoretical Computer Science (M21276)
Part B/5: Introduction to Computational Complexity
(Jan 4-9, 2022)
Question 1. Simulate the sequential and binary search algorithm for the following array L of integers
Copyright By PowCoder代写 加微信 powcoder
10, 16, 19, 24, 28, 30, 33, 38, 49, 58, 66, 69, 76, 85, 96, 100 and keys (i) x = 10, (ii) x = 38.
How many basic steps (loops) have to be executed in each case?
Give an example of a key for which both algorithms have to do the most steps
(loops) for L. If such a key doesn’t exist give a reason.
Question 2. Consider two possible algorithms to solve a problem, A and B. The time time complexity of the first algorithm is TA(n) = An3 , where n is the size of the input and for the second one TB(n) = Bn2. After programming these, you run it for a small subset (n = 100) and discover that they take TA(100) = 0.1 seconds and TB(100) = 2 seconds. How long does each take for n = 10,000? For what values of n does it make sense to use the algorithm A ?
Question 3. Given the following algorithm:
while i <= n
i := i + 1; x := x + 1; S;
(a) Find the number of times that the statement S is executed during the running of the program for n = 4, as a function of n.
(b) Find the number of times that the assignment statement (:=) is executed during the running of the program for n = 4, as a function of n.
Question 4. Given the following algorithm:
while i < (n + 1)
i := i + 1;
for j := 1 to i do S od od
(a) Find the number of times that the statement S is executed during the running of the program for n = 4, as a function of n.
(b) Find the number of times that the assignment statement (:=) is executed during the running of the program for n = 4, as a function of n (including assignments := as part of for statement itself).
Question 5. Given the following algorithm:
for i := 1 to n do
for j := 1 to i do x := x + f(x) od; x := x + g(x)
(a) Find the number of times that the addition operation (+) is executed during the running of the program for n = 4, as a function of n.
(b) Find the number of times that the assignment statement (:=) is executed during the running of the program for n = 4, as a function of n (including assignments := as part of for statement itself).
Question 6. Given the following algorithm:
while j <= n/2
while i <= j
print j, i; i := i + 1; S;
j := j + 1; od
(a) What is the output when n = 8?
(b) Find the number of times that the statement S is executed during the running of the program as a function of n.
Question 7. Given the following algorithm:
while x <= y
x := x + 2; y := y/2; S;
Find the number of times that the statement S is executed during the running of the program.
Question 8. Suppose you have an old computer that requires 1 minute to solve a problem P using your algorithm A for instances of size n = 10 000. Suppose you buy a new computer that runs 100 times faster than the old one (hence the new computer runs 100 times more operations for the same input). What size of input can be run in 1 minute on the new computer, assuming the following time complexities T(n) for the algorithm A?
(a) T(n)=n, (b) T(n)=n2,
(c) T(n) = 10n.
Question 9. Fill in the following table for different time-complexity functions. For large
values use only approximative values in the terms of powers of 10, e.g. 109, ... n logn n2 2n n!
Consider a problem with exponential/factorial complexity and assume 1 computation per 10−12 seconds.
Computing continuously from 0 A.D. until now, for which n we would still not have solved the problem in exponential/factorial case?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com