CSCI 4101/5101 Test No. 1
Friday, February 19, 2016
MINI-ESSAYS. Answer the questions as completely as you can without sacrificing conciseness. The space provided should be a good indication of the length of answer required. If you do need additional space, you can write on the back of the sheets but clearly indicate where the continuation is located.
Justify the choice of time complexity as the primary criterion when comparing alternative algorithms to solve a problem. Why is it usually chosen ahead of space complexity for comparison purposes? What about the development time of software designers? (10 pts.)
Time complexity is the primary criterion used when comparing alternative algorithms to solve a problem because time is irrecoverable. Space can be recycled or can be expanded by adding more memory to the computing device. On the other hand, time cannot be expanded per se – although one can virtually do this by using a faster computer, an enhancement that is probably more costly than just increasing available memory.
Of course, this discussion presupposes that the alternative solutions are both correct. Otherwise, one or both would be useless since they do not really solve the problem.
We do not discuss other criteria that may be relevant to real-world operations that develop software solutions because there is more variability in them. Take for example, development time spent by software designers. Some programmers are simply more efficient at producing code than others so time of development might not be an accurate gauge of which alternative solution should be adopted. On the one hand, a more efficient solution might take forever to program negating any time savings in running time. On the other hand, a less efficient solution might take little time being implemented but if the resulting program has to be run many, many times as in the span of several years, then a more efficient solution might be preferable since the total time savings would still be significant.
Also, different companies may have different pay scales and so if labor is cheap (as in third world countries), it may be advantageous to have a more efficient algorithm implemented even if it took a long time to do this. On the other hand, if labor costs are steep, then a quick and dirty solution that may not be the most efficient may be preferable especially if the resulting program is going to be run only a few number of times.
There may be other reasons pertaining to the relative difficulty of actually proving in a mathematically rigorous way that an algorithm is correct that might make correctness (in the total sense) not the primary criterion.
(with answers)
Name _______________________________________________
Part I.
1.
CSCI 4101/5101 Test No. 1 2. Suppose (as in the textbook) that computers were infinitely fast and computer memory was free.
Would the study of algorithms still be relevant? Defend you answer. (8 pts.)
The study of algorithms would still be relevant even if we had infinitely fast computers and all the memory we can get our hands on (since it is free).
Correctness would still be a desirable and critical characteristic for the algorithms designed. Who wants to implement an algorithm that does not work or solves the wrong problem correctly? Thus, techniques for establishing program correctness would still be a legitimate object of study.
Also, algorithms usually do not “write themselves” and so the different algorithmic schemes and approaches would still be useful “stuff” to learn so that when a new problem presents itself, one can look at how old problems were tackled and solves to gain insight into how the new problem may itself be solved. Solution schemes like “divide-and-conquer”, “recursion”, “incremental approach”, “dynamic programming”, “randomization”, “simulated annealing”, “genetic algorithms”, “heuristics”, etc., would still be interesting and fruitful objects of study in algorithm analysis and design.
3. What does it mean when one says that an algorithm is O(n2)? (7 pts.)
By definition, the O() notation allows us to describe an upper bound on the growth of whatever it is that we wish to estimate. So, O(n2) would mean that whatever it is that we are estimating does not grow any faster than quadratic as the independent variable n grows.
Now, since algorithm analysis has come to mean estimating the resource requirement of an algorithm, and time complexity is of primary importance, to say that an algorithm is O(n2) usually would mean that its time complexity is no worse than quadratic in growth.
Some examples of algorithms we have seen that have O(n2) time complexity are INSERTION-SORT, BUBBLESORT, and MAXSORT, where n is taken to be the number of items to be sorted.
Some examples of algorithms that have O(n2) space complexity are linear programming algorithms that employ nn matrices to arrive at the solution, where n may be the number of unknown variables in the problem instance, or graph algorithms where the graph with n vertices is represented using an adjacency matrix that is nn in size.
Page 2
CSCI 4101/5101 Test No. 1
Part II. MULTIPLE CHOICE. Indicate the best answer from the five choices presented for each of the following questions. Record the answers in the provided scantron sheet. (1 pt. each)
1. A(n) __________ can be defined as a well- defined computational procedure that takes input and produces output.
a. pipeline
b. algorithm
c. roadmap
d. recipe
e. None of these answers are good.
2. An instance of a problem consists of this:
a. input needed to compute a solution
b. output produced as solution
c. algorithm applied to input
d. snapshot of problem solution
e. primitive operation that costs O(1)
3. Sorting is a fundamental operation in computer science that takes a collection of values as input and rearranges them into some specified _______.
a. location b. value
c. definition d. identity e. order
4. An algorithm is said to be ________ if, for every input instance, it halts with the correct output.
a. efficient
b. economical
c. correct
d. tractable
e. understandable
5. An algorithm can be specified in terms of these, except:
a. informal English
b. as a computer program
c. as a hardware design
d. pseudocode
e. as a black box
6.
7.
8.
9.
10.
Interesting algorithms exhibit the following characterics, except:
a. they admit many candidate solutions
b. they have practical applications
c. they solve new problems
d. All of these answers are valid.
e. None of these answers are valid.
A(n) ___________ is a way to store and organize data in order to facilitate access and modifications.
a. algorithm
b. data structure
c. recipe
d. address book
e. hard drive
The usual measure of efficiency is this, which is how long an algorithm takes to produce its result:
a. implementability b. modifiability
c. understandability d. compactness
e. speed
Insertion sort is based on a technique similar to the way many people sort a hand of ________.
a. uncooked cereal
b. playing cards
c. thumb drives
d. paper documents
e. juggling pins
________ sort works by combining two sorted sub-collections into one in linear time.
a. Merge
b. Insertion
c. Stack
d. Quick
e. Heap
Page 3
CSCI 4101/5101
Test No. 1
11. Analyzing an algorithm has come to mean ________ the resources that the algorithm requires.
a. supplying
b. questioning
c. predicting
d. complementing e. preserving
12. The longest running time for any input is what we call the _______ complexity of an algorithm.
a. best-case
b. worst-case
c. average-case d. unfortunate
e. outrageous
13. The running time _______ over all input is what we call the average-case complexity of an algorithm.
a. accumulated b. anticipated c. amortized d. generated e. expended
14. The shortest running time for some input is what we call the _______ complexity of an algorithm.
a. best-case
b. worst-case
c. average-case d. unfortunate
e. outrageous
15. This algorithmic technique known as divide- and-conquer breaks the problem into _______ subproblem(s).
a. a single
b. more complex
c. non-existent
d. already-solved
e. several
16. We write f (n) = (g(n)) when g(n) is an asymptotically ___________ for f(n).
a. lower bound
b. upper bound
c. tight bound
d. approximation
e. None of these answers are valid.
17. We write f(n) = O(g(n)) when g(n) is merely an asymptotic __________ for f(n).
a. lower bound
b. upper bound
c. tight bound
d. approximation
e. None of these answers are valid.
18. We write f(n) = (g(n)) when g(n) is merely an asymptotic __________ for f(n).
a. lower bound
b. upper bound
c. tight bound
d. approximation
e. None of these answers are valid.
19. When we state that for all f(n), f(n) = ( f(n))
we are saying that the () notation is __________.
a. reflexive
b. symmetric
c. transitive
d. anti-symmetric e. idempotent
20. When we state that, for all f(n), g(n), h(n): f(n) = (g(n))
and f(n) = (h(n)) g(n) = (h(n))
we are saying that the () notation is
a. reflexive
b. symmetric
c. transitive
d. anti-symmetric e. idempotent
Page 4
CSCI 4101/5101
Test No. 1
21. To say that for a function f(n) it is true that if m n then f(m) f(n)
is to say that the function f(n) is:
a. monotonically increasing
b. monotonically decreasing
c. constant
d. oscillating
e. undefined
22. To say that for a function f(n) it is true that if m n then f(m) f(n)
is to say that the function f(n) is:
a. monotonically increasing
b. monotonically decreasing
c. monomially constant
d. perenially oscillating
e. non-trivially discontinuous
23. To say that a function f(n) is such that f (n) = O(nk) for some constant k
is to say that the function is:
a. locally bounded
b. logarithmically bounded
c. exponentially bounded
d. polynomially bounded
e. asymptotically bounded
24. The substitution method for solving recurrences makes use of this important proof technique:
a. mathematical induction
b. mathematical analysis
c. convex analysis
d. hyperbolic reasoning
e. philosophical conjecture
25. The ___________ method is best used to generate a good guess which, in turn, can be confirmed with the substitution method.
a. family-tree
b. perenial-tree
c. recursion-tree
d. holiday-tree
e. random-tree
26. The master method may be applied to solve all types of recurrences. Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
27. Merge-sort achieves optimal average-case time complexity (i.e., (nlgn)). Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
28. Merge-sort has a best-case time complexity of O(nlgn). Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
29. Insertion-sort has a best-case time complexity of (n). Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
30. Insertion-sort has a non-optimal worst-case time complexity of O(n2). Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
31. Asymptotic complexity exhibits transpose symmetry. This can be expressed as:
f (n) = O(g(n)) g(n) = (f (n)) Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
32. Asymptotic complexity is not affected by scaling nor the addition of a constant term. This can be expressed as:
f(n) = (g(n)) (c1 f(n) + c2) = (g(n)) Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
Page 5
CSCI 4101/5101
Test No. 1
33. Asymptotic complexity disregards terms in a polynomial that have lower powers of the independent variable (i.e., n). This can be expressed as:
Assess the correctness of this statement.
34. To say that a function f(n) = (g(n)) means that we have found a tight bound on the growth of f(n). This can be expressed as:
f(n) = (g(n))
f(n) = O(g(n)) and f(n) = (g(n))
Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
35. Not all functions are asymptotically comparable. Assess the correctness of this statement.
a. This is a true statement.
b. This is a false statement.
a. b.
This is a true statement. This is a false statement.
Part III.
1.
PROBLEM-SOLVING. Perform the required operation(s) to achieve the desired solution(s). Show that f(n)=10100n + 2016 is (n). (5 pts.)
We can establish the result by showing that f(n) is Θ(n). And then since Θ(n) implies both O(n) and Ω(n), we would have our result.
To show that f(n) is Θ(n), we show that
lim f(n)/n = c > 0 n∞
lim f(n)/n = lim (10100n+2014)/n n∞ n∞
= lim (10100n)/n + lim (2014/n) n∞ n∞
= 10100
Hence, we have the desired result, i.e., f(n) is Ω(n).
And indeed,
which is greater than zero.
Page 6
CSCI 4101/5101 Test No. 1
2. Show that if f(n) is (n2) then f(n) is also (n). (5 pts.)
The result follows from the fact that for n > 1, n2 > n
And so, if f(n) > cn2 for some positive constant c and n large enough, by transitivity, f(n) > cn for those values of n as well. But this is exactly the definition of f(n) being Ω(n).
3. Consider the following recursive method in Java that determines if the characters in a string are alphabetically arranged in increasing order or not:
public boolean isSorted( String str ) {
if ( str.length() <= 1 ) //a string with one or no charactersreturn true;else //check first two characters in orderreturn ( ( str.charAt(0) <= str.charAt(1) )//check last n-1 characters in order&& isSorted( str.substring(1,str.length()) ); } //end of isSorteda. Explain convincingly why the recurrence below for t(n), where n is the number of characters in the string parameter str, is a correct expression for the number of primitive operations required by a call to isSorted. (10 pts.)t(0) = (1)t(1) = (1)t(n) = t(n–1) + (1)The base cases when n, the length of the string str, is either 0 or 1, involves a constant amount of work associated with the test for the string length and returning the true result. This is why we have the cost Θ(1) for these cases, that is:t(0) = Θ(1) t(1) = Θ(1)The general case involves similar tests for string length and a comparison of the first and second characters, something that is not affected by the length of the string argument, thus incurring the cost Θ(1) like in the base cases. But there is one recursive call to the same method albeit with a string that has had its first character removed and hence has a length one less than that of the original string str. Hence, for the general case:t(n) = t(n─1) + Θ(1) Page 7(more next page)CSCI 4101/5101 Test No. 1 b. Using the recursion-tree below for t(n), formulate a guess that solves the recurrence on theprevious page. (10 pts.)n–1cc ccc Taking the sum of the costs at eachlevel of the recursion tree, we get: cnThis gives us t(n) = cn and the “guess” t(n) = Θ(n).Page 8CSCI 4101/5101 Test No. 1 4. We can express binary search as a recursive procedure as follows:In order to determine if a target value x is in sorted array A[1..n], we compare x with the middle element of A[1..n] and then, depending on this comparison, either determine that we have found x (if they are equal) or recursively search for x in one of the halves of the sorted array: either in A[1..n/2–1] or in A[n/2+1..n]. The base case would be when the sorted array has one element or is empty. a.Explain why the following recurrence for the running time t(n) [in terms of the number of comparisons made] of this recursive version of binary search is appropriate. (5 pts.)t(1) = 1 t(n) = t(n/2) + 1When there is only one item in the array, we simply compare the target value with the single item in the array and have a determination of whether the target is in the array or not. That’s a total of one comparison, hence the costt(1)=1In the general case, the target value is compared with the middle element of the array and a recursive search is carried out in the first or the second half of the array depending on the result of the first comparison. That’s one comparison and then the comparisons associated with the recursive call involving just half of the original items in the array, hence the costt(n) = t(n/2) + 1Using the Master Theorem, supply the solution for t(n). Identify the values of a, b, and k asemployed in the Master Theorem. (5 pts.)b.We can express ast(n) = t(n/2) + 1 t(n) = 1t(n/2) + n0And, using the Master Theorem “template” identify the following parameter values: a = 1, b = 2, and k = 0. Hence, Case 2 applies and the solution is:t(n) = Θ(logn) Page 9
Reviews
There are no reviews yet.