Midterm Flashcards
Analyzing algorithms gives us insight into how to design “good” algorithms, or improve a given algorithm.
True
The time and space required by an algorithm depends on
d) All options
a) Size of the input
c) Input of fixed-sized
b) Good or bad implementation
Answer: D) All options
The implementation of two algorithms to compare them is much faster than analyzing the code.
False
To predict time usage, we will use a good approximation of the number of elementary or basic steps which the algorithm performs.
True
If two inputs are the same size, the algorithm will not perform differently on them.
False
Compute the maximum number of basic operations performed by the algorithm for any input of fixed size is called worst-case analysis.
True
W(n) provides an upper bound on the number of basic steps performed by the algorithm.
True
Whenever you do a worst-case analysis, you must state
d) All Options
b) Basic Operation Counted
a) Input Size
c) Worst-case Input
Answer: D) All Options
In recursive call tree for recursive algorithms, the root node is the base case and leaf nodes are all initial calls.
False
The divide and conquer (recursion) way of coding is always better than iterative programming.
False
The NP-complete problem means:
d) None of above
b) It is considered highly unlikely an efficient algorithm exist
c) Both a and b
a) Don’t know an efficient algorithm
Answer: C) Both a and b
lg(a/b) = lg a - lg b
True
n = 2^k -> k = lg n
True
lg n = (log n) / (log 2)
True
Average case analysis gives information on what happens most of the time.
True
W(n) always predicts the run time exactly.
False
Consider two functions f(n) and g(n) which differ by a constant factor as being in the same complexity class i.e. if g(n) = c*f(n) for some constant c>0 then g(n) and f(n) should be considered to be in the same class.
True
The complexity class of Theta(nlgn) is Logarithmic time.
False
The complexity class of Theta(n^2) is Quadratic time.
True
An inplace sort is a sorting algorithm that needs any extra space beyond that needed for the input.
False
The divide and conquer problem solving is the best strategy for Fibonacci numbers.
False
Use back substitution for smaller values, until you can guess a pattern.
True
For n=2, the Strassen method takes 8 multiplications to solve C=A*B.
False
The complexity of the ordinary matrix multiplication algorithm is Theta(n^3).
True
x^log^(a^y) = y^log(a^x)
True
Draw the recursive call tree for a small value of n, if the same subproblem is calculated numerous times in the call tree then this is probably an exponential time alg. In this case, use Dynamic Programming Strategy.
True
Suppose that n is a power of 2. then we can apply Strassen’s algorithm recursively (i.e. using the divide and conquer strategy) by splitting the matrix into 4 equal pieces, and treating these pieces like the entries of the 2 x 2 matrix.
True
If we count additions, subtractions, and multiplications of the ordinary algorithm then its order is Theta(n^2.81).
False
The exchange sort is inplace sort.
True
