Midterm

Question 1

Analyzing algorithms gives us insight into how to design “good” algorithms, or improve a given algorithm.

Answer 1

True

Question 2

The time and space required by an algorithm depends on

Answer 2

d) All options
a) Size of the input
c) Input of fixed-sized
b) Good or bad implementation

Answer: D) All options

Question 3

The implementation of two algorithms to compare them is much faster than analyzing the code.

Answer 3

False

Question 4

To predict time usage, we will use a good approximation of the number of elementary or basic steps which the algorithm performs.

Answer 4

True

Question 5

If two inputs are the same size, the algorithm will not perform differently on them.

Answer 5

False

Question 6

Compute the maximum number of basic operations performed by the algorithm for any input of fixed size is called worst-case analysis.

Answer 6

True

Question 7

W(n) provides an upper bound on the number of basic steps performed by the algorithm.

Answer 7

True

Question 8

Whenever you do a worst-case analysis, you must state

Answer 8

d) All Options
b) Basic Operation Counted
a) Input Size
c) Worst-case Input

Answer: D) All Options

Question 9

In recursive call tree for recursive algorithms, the root node is the base case and leaf nodes are all initial calls.

Answer 9

False

Question 10

The divide and conquer (recursion) way of coding is always better than iterative programming.

Answer 10

False

Question 11

The NP-complete problem means:

Answer 11

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

Question 12

lg(a/b) = lg a - lg b

Answer 12

True

Question 13

n = 2^k -> k = lg n

Answer 13

True

Question 14

lg n = (log n) / (log 2)

Answer 14

True

Question 15

Average case analysis gives information on what happens most of the time.

Answer 15

True

Question 16

W(n) always predicts the run time exactly.

Answer 16

False

Question 17

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.

Answer 17

True

Question 18

The complexity class of Theta(nlgn) is Logarithmic time.

Answer 18

False

Question 19

The complexity class of Theta(n^2) is Quadratic time.

Answer 19

True

Question 20

An inplace sort is a sorting algorithm that needs any extra space beyond that needed for the input.

Answer 20

False

Question 21

The divide and conquer problem solving is the best strategy for Fibonacci numbers.

Answer 21

False

Question 22

Use back substitution for smaller values, until you can guess a pattern.

Answer 22

True

Question 23

For n=2, the Strassen method takes 8 multiplications to solve C=A*B.

Answer 23

False

Question 24

The complexity of the ordinary matrix multiplication algorithm is Theta(n^3).

Answer 24

True

Question 25

x^log^(a^y) = y^log(a^x)

Answer 25

True

Question 26

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.

Answer 26

True

Question 27

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.

Answer 27

True

Question 28

If we count additions, subtractions, and multiplications of the ordinary algorithm then its order is Theta(n^2.81).

Answer 28

False

Question 29

The exchange sort is inplace sort.

Answer 29

True