Unit I

Question 1

sequence of unambiguous instructions for solving a problem

Answer 1

Algorithm

Question 2

algorithms that executes instructions one after another, one operation at a time.

Answer 2

Sequential Algorithm

Question 3

expressing algorithm by a collection of connected geometric shapes

Answer 3

Flow Chart

Question 4

Efficiency indicates how fast the algorithm runs.

Answer 4

Time Efficiency

Question 5

Efficiency indicates how much extra memory the algorithm needs.

Answer 5

Space Efficiency

Question 6

preserves the relative order of any two equal elements in its input.

Answer 6

Stable Algorithm

Question 7

Efficiency for which the algorithm runs the longest among all possible inputs of that size.

Answer 7

Worst Case Efficiency

Question 8

Efficiency for which the algorithm runs fastest among all possible inputs of that size.

Answer 8

Best Case Efficiency

Question 9

h ϵ O(g); g ϵ θ(n^2) then h ϵ θ(n^2)

Answer 9

Transitivity

Question 10

t1(n) ϵ Ο(g1(n)) and t2(n) ϵ Ο(g2(n)),

t1.t2 ϵ Ο(g1, g2)

Answer 10

Rule of Product

Question 11

t1(n) ϵ Ο(g1(n)) and t2(n) ϵ Ο(g2(n)),

t1(n) + t2(n) ϵ Ο(max{g1(n), g1(n)})

Answer 11

Rule of sum

Question 12

Class name that characterizes efficiency of an algorithms with two embedded loops

Answer 12

Quadratic

Question 13

Class name that characterizes efficiency of an algorithms with three embedded loops

Answer 13

Cubic

Question 14

Class name that characterizes algorithms that generate all subsets of an n-element set

Answer 14

exponential

Question 15

Class name that characterizes algorithms that generate all permutations of an n-element set

Answer 15

Factorial

Question 16

The principal alternative to the mathematical analysis of an algorithm’s efficiency

Answer 16

Empirical Analysis