WorksheetsCOCAT - DAA
Total questions: 25
Worksheet time: 23mins
An image processing application begins with two n×n matrices A and B. The first phase of preprocessing the inputs takes O(n2) steps for each of A and B. The second step involves a convolution of A and B to yield a new matrix C in time O(n3). This is followed by an edge detection phase that takes times O(n2) for matrix C. What is the most accurate and concise description of the complexity of the overall algorithm?
O(n2)
O(n3)
O(n2+n3)
O(n5)
We are trying to determine the worst case time complexity of a library function that is provided to us, whose code we cannot read. We test the function by feeding large numbers of random inputs of different sizes. We find that for inputs of size 300 and 3.000, the function always returns well within one second, but for inputs of size 30,000 it sometimes takes about 1 second and for inputs of size 300,000 it sometimes takes 1-2 minutes. What is a reasonable conclusion we can draw about the worst case time complexity of the library function? (You can assume, as usual, that a typical desktop PC performs 109 basic operations per second.)
O(n log n)
O(n2)
O(n3)
O(n3 log n)
Suppose f(n) is 2n3+4n+5 and g(n) is 7n5 + 5n3 + 12. Let h(n) be a third, unknown function. Which of the following is not possible.
h(n) is O(f(n)) and h(n) is also O(g(n))
h(n) is O(g(n)) but h(n) is not O(f(n))
h(n) is O(f(n)) but h(n) is not O(g(n))
h(n) is not O(f(n)) and h(n) is also not O(g(n))
If T(n) is O(n2 √ n) which of the following is false?
T(n) is O(n2 log n)
T(n) is O(n3)
T(n) is O(n3 log n)
A. T(n) is O(n4)
How many times is the comparison i >= n performed in the following program?
int i = 200, n = 80;
main(){
while (i >= n){
i = i-2;
n = n+1;
}
}
40
41
42
43
Which of the following statements is not true?
Quicksort and merge sort are both examples of divide and conquer algorithms.
If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).
For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n2).
If we could find the median in time O(n), quicksort would have worst case complexity O(n log n).
In a min-heap, what is the most accurate description of the worst-case complexity of the operation find_max that reports the value of the largest element in the heap, without removing it?
O(1)
O(log n)
O(n)
O(n log n)
Consider an alternative to binary search called ternary search that divides the input array into three equal parts and recursively searches one of these three segments. What can we say about the asymptotic worst case complexity of ternary search versus binary search?
The complexity of ternary search is the same as that of binary search.
The complexity of binary search is strictly better than that of ternary search.
The complexity of ternary search is strictly better than that of binary search
The relative complexity of ternary and binary search depends on the distribution of values across the array
Suppose we do merge sort with a five-way split: divide the array into 5 equal parts, sort each part and do a 5 way merge. What would the worst-case complexity of this version be?
O(n2)
O(n2 log5n)
O(n log2n)
O(n (log2n)2)
The brute force algorithm for solving the traveling salesman problem is________________
Approximate and Efficient
Optimal and Inefficient
Optimal and Efficient
Approximate and Inefficient
Suppose we build a Huffman code over the four letter alphabet {a,b,c,d}, where f(a), f(b), f(c) and f(d) denote the frequencies (probabilities) of the letters and f(a) > f(b) > f(c) > f(d). Which of the following is a valid conclusion?
The Huffman code will assign two bits to every letter always.
If f(c)+f(d) > f(b), the Huffman code will assign two bits to every letter, otherwise the letters will be encoded with varying numbers of bits.
If f(c)+f(d) > f(a), the Huffman code will assign two bits to every letter, otherwise the letters will be encoded with varying numbers of bits.
If f(b) > f(c)+f(d), the Huffman code will assign two bits to every letter, otherwise the letters will be encoded with varying numbers of bits.
Which of the following is not a greedy algorithm?
Dijkstra's algorithm for single source shortest paths
Bellman-Ford algorithm for single source shortest paths
Prim's algorithm for minimum cost spanning tree
Kruskal's algorithm for minimum cost spanning tree
Your final exams are over and you are catching up on sports on TV. You have a schedule of interesting matches from all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week.
Suppose there are n such matches {M1,M2,…,Mn} available during the coming week. The matches are ordered by starting time, so for each i ∈ {1, 2, …, n−1}, Mistarts before Mi+1. However, match Mi may not end before Mi+1 starts, so for each i ∈ {1,2,…,n−1}, Next[i] is the smallest j > i such that Mj starts after Mi finishes.
Given the sequence {M1,M2,…,Mn} and the values Next[i] for each i ∈ {1, 2, …, n−1}, your aim is to compute the maximum number of complete matches that can be watched.
What is the size of the memo table for this problem?
n2
n+1
n
n-1
Your final exams are over and you are catching up on sports on TV. You have a schedule of interesting matches from all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week.
Suppose there are n such matches {M1,M2,…,Mn} available during the coming week. The matches are ordered by starting time, so for each i ∈ {1, 2, …, n−1}, Mistarts before Mi+1. However, match Mi may not end before Mi+1 starts, so for each i ∈ {1,2,…,n−1}, Next[i] is the smallest j > i such that Mj starts after Mi finishes.
Given the sequence {M1,M2,…,Mn} and the values Next[i] for each i ∈ {1, 2, …, n−1}, your aim is to compute the maximum number of complete matches that can be watched.
How much time will it take to compute Watch[1] using dynamic programming?
O(n3)
O(n2)
O(n log n)
O(n)
Your final exams are over and you are catching up on sports on TV. You have a schedule of interesting matches from all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week.
Suppose there are n such matches {M1,M2,…,Mn} available during the coming week. The matches are ordered by starting time, so for each i ∈ {1, 2, …, n−1}, Mistarts before Mi+1. However, match Mi may not end before Mi+1 starts, so for each i ∈ {1,2,…,n−1}, Next[i] is the smallest j > i such that Mj starts after Mi finishes.
Given the sequence {M1,M2,…,Mn} and the values Next[i] for each i ∈ {1, 2, …, n−1}, your aim is to compute the maximum number of complete matches that can be watched.
What is a good order to compute Watch[i] using dynamic programming?
From Watch[n] to Watch[1]
From Watch[1] to Watch[n]
Either from Watch[1] to Watch[n] or from Watch[n] to Watch[1]
None of these
When we model a graph problem using LP, mapping each path to a variable is not a good strategy because:
We have to be careful to avoid cycles.
A graph has exponentially many paths.
Edges may be directed.
Paths can be hard to compute.
Which of the following is a linear constraint?
17x + 3xz ≤ 4
3x ≥ 14y + 2z + 13
7x ≤ 3xy + 14z - 12
5y + 3x2 ≥ 33
Suppose we compute the maximum s-t flow F in a network. Then, which of the following is true of s-t cuts?
F gives a lower bound for the capacity of the minimum s-t cut but not the exact capacity.
From F, we can identify all minimum s-t cuts in polynomial time.
From F, we can identify a minimum s-t cut in polynomial time.
From F, we know the capacity of the minimum s-t cut, but identifying such a cut can take exponential time.
Which of the following is not a linear constraint?
8x ≤ 3y + 25
5x + 6xy ≤ 5
9x ≥ 7y + 8z
5y + 3x ≥ 33
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference?
If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B.
If we don’t know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.
If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A.
Which of the following is not a backtracking algorithm?
Knight tour problem
N queen problem
Tower of Hanoi
M coloring problem
We have an exponential time algorithm for problem A, and problem A reduces in
polynomial time to problem B. From this we can conclude that:
B has an exponential time algorithm.
B cannot have a polynomial time algorithm.
A cannot have a polynomial time algorithm.
None of the above.
Suppose SAT reduces to a problem C. To claim that C is NP-complete, we additionally need to show that:
There is a checking algorithm for C.
Every instance of C maps to an instance of SAT.
Every instance of SAT maps to an instance of C.
C does not have an efficient algorithm.
While finding optimal solution for a Travelling Salesman problem, sub-tours are to be blocked because:
All sub-tours cannot be found
Some sub-tours are not possible to cover
Travelling Salesman problem considers only some sub-tours, not all
Travelling Salesman problem considers only complete tours, not sub-tours
Nearest Neighbor Heuristic is used to solve a Travelling Salesman Problem. A feasible solution to the problem is obtained. Which one of the following observations will be true?
The solution obtained will be always optimal
The solution obtained will be most likely optimal
The solution obtained may be optimal
The solution obtained will be never optimal
