CS502 QUIZ SOLUTION FILE
If matrix A of dimension 2 x 4 is multiply with matrix B of dimension 4 x 3, then the dimension of resultant matrix is:
2 x 3
Fibonacci Sequence was named on _______, a famous mathematician in 12th Century.
Leonardo Pisano
Chain matrix multiplication problem can be solved through --------------------- strategy.
Dynamic programming
Counting sort is suitable for sorting the elements within range 1 to P, where ________
P is small
The only way to convert a string of i characters into the empty string is with i deletions, represented as _____________.
E(i, 0) = i
In Dynamic Programming approach, we do not store the solution to each sub-problem in case if it reappears.
True
If Matrix-A has dimensions "3x2" and Matrix-B has dimensions "2x3", then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions
3x3
Quicksort is a/an _______ and ________ sorting algorithm.
In-place, stable one
When matrix A of 5 x 3 is multiply with matrix B of 3 x 4 then the number of multiplication required is:
60
Memoization is a part of Dynamic Programming strategy.
True
If matrix A of dimension 2 x 4 is multiply with matrix B of dimension 4 x 3, then the dimension of resultant matrix is:
2 x 3
Counting sort assumes that the numbers to be sorted are in the range ______________.
1 to k where k is small
When matrix A of 5 x 3 is multiply with matrix B of 3 x 4 then the number of multiplication required is:
60
If matrix A of dimension p x q is multiply with matrix B of dimension q x r, then each entry in resultant matrix takes -------------------- time.
O (q)
Memoization is a part of Dynamic Programming strategy.
True
An in-place sorting algorithm is one that ___________ uses additional array for storage.
Does not
When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has _______________ sub-problems.
Overlapping
If a matrix has three rows and two columns, then dimensions of matrix will be:
3 x 2
Multiplication is ________.
n^3 (n cube)
Heap sort is a/an _______ and ________ sorting algorithm.
In-place, not stable one
In generating Fibonacci Sequence, we can avoid unnecessary repetitions by __________ process.
Memoization Not memorization
In Dynamic Programming approach, solution is modified/changed _________.
At each stage
Counting sort is suitable for sorting the elements within range 1 to P, where ________
P is small
_______ overcomes the limitations of ________ by working as per positional notations of numbers.
Radix sort, Counting sort
In Dynamic Programming, our approach is to ____________.
Build the solution in a bottom-up fashion
If matrix A of dimension 2 x 4 is multiply with matrix B of dimension 4 x 3, then the dimension of resultant matrix is:
2 x 3
Insertion sort is an in-place sorting algorithm.
True
If Matrix-A has dimensions "3x2" and Matrix-B has dimensions "2x3", then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions
3x3
Matrix multiplication is a(n) ----------------- operation.
Associative
Identify the TRUE statement.
The Knapsack problem belongs to the domain of optimization problems.
If there are Θ (n²)entries in edit distance matrix then the total running time is:
Θ (n²)
Consider three matrices X, Y, Z of dimensions 1 x 2 , 2 x 3 , 3 x 4 respectively. The number of multiplications of (XY)Z is:
18
In Knapsack Problem, the goal is to put items in the knapsack such that the value of the items is _________ subject to weight limit of knapsack.
Maximized
Radix sort is not a non-comparative integer sorting algorithm.
True
We can multiply two matrices A and B only when they are compatible which means:
Number of columns in A must be equal to number of rows in B
Dynamic Programming comprises of ___________
No Repetition but Recursion
Following is not the application of Edit Distance problem.
Ascending Sort
Consider three matrices X, Y, Z of dimensions 1 x 2 , 2 x 3 , 3 x 4 respectively. The number of multiplications of X(YZ) is:
32
In Bucket sort, if there are duplicates then each bin can be replaced by a
Linked list
There are __________ entries in the Edit Distance Matrix.
Θ (n²)
Heap sort is a/an _______ and ________ sorting algorithm.
In-place, not stable one
In Brute Force solution of Knapsack Problem, there are _______ possible combinations for n items.
2^n (2 raise to the power n)
We can make _________ recursive calls in Fibonacci Sequence.
Infinite
In Fibonacci Sequence, each term is calculated by_______ previous ______ terms.
Adding, Two
A sorting algorithm is called as ________ if duplicate elements remain in the same relative position after sorting.
Stable
As per algorithm of Dynamic Programing, we need to store the result(s) of __________
Intermediate sub-problems
Dynamic Programming is a problem-solving approach in which __________
Both are incorrect
The only way to convert an empty string into a string of j characters is by doing j insertions, represented as _____________.
E(0, j) = j
Dynamic Programming approach is usually useful in solving optimization problems.
True
It is not a Fibonacci Sequence.
1,1,1,2,3,5,8,13,21,34,55,……
TRUE
Dynamic programming formulation of the matrix chain multiplication problem will store the solutions of each sub problem in a(n):
Table
We can use the optimal substructure property to devise a ____________ formulation of the edit distance problem.
Recursive
. If we associate (x.y) integer pare to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a----------car.
Cheep
2. We can use the optimal substructure property to devise a ____formulation of the edit distance problem. recursive
3. In average- case time analysis of quick sort algorithm. The most balanced case for partition is when we divide the list of element into -----------.
Three nearly equal pieces
4. Counting sort assumes that the number to be sorted are in the range ------
1 to k where k is small
5. In random access machine(RAM) instructions are executed in ______
One by one
6. Brute-force algorithm for 2D-maxima is operated by comparing _______pairs of point All
7. A sorting algorithm is called as ______ if duplicate elements remain in the same relative position after sorting.
Stable
8. An algorithm is said to be correct if for every _______ instance , it halts with the correct Input, output
9. The O- notation is used to state only the asymptotic______ bounds.
Upper
10. Insertion sort is an efficient algorithm for sorting a _____number of elements.
Large
11. Dynamic programming formulation of the matrix chain multiplication problem will store the solution of each sub problem in a(n).
Table
12. Dynamic programming strategy is useful when sub problems are independent.
True
13. In 3- dimensional space ,a point P has____ coordinate(s).
X,Y,Z
14. In plane sweep approach, a vertical line is swept across the 2D-plane from____.
Left to right
15. If there are Θ(n2) entries in edit distance matrix then each entry E(i, j) takes_____ time to complete.
Θ(1)
16. The only way to convert an empty string into a string of J characters is by doing insertions , represented as____
E(0 ,j)= j
17. Merge sort have running time_____ running time of heap sort.
Less than
18. Fibonacci sequence was named on ___ a famous mathematician in 12th century.
Leonardo Pisano
19. In Fibonacci sequence, each term is calculated by____ previous ____term.
Adding, two
20. Selection sort is not an place sorting algorithm.
False
In plane sweep approach, a vertical line is swept across the 2d-plane and _____ structure is used for holding the maximal points lying to the left of the sweep line.
STACK
1. In _____ we have to find rank of an element from giving input.
Selection problem
2. AL khawarzmi wa s a/an
Mathematician
3. While sorting the ordered domain means for any two input elements x and y _____ satisfies only.
All of the above
4. When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has _______ sub-problems.
Overlapping
5. In sieve technique, we solve the problem _________
In recursive manner
6. The time assumed for each basic operation to execute on RAM Model of computation is
_____
Constant
7. Heap sort is a/an ____ and _____ sorting algorithm.
In-place, not stable one
8. Algorithm is a sequence of computational steps that _____input into output. Transform
9. If matrix-A has dimension 3x2 and matrix-B has 2x3, then resultant matrix will be 3x3
10. ____ provides more accurate result when input values are not closer to each other Median
11. Boolean operation is a _____ operation on an idealized RAM model of computation. Basic
12. In order to say anything meaningful about our algorithms, it will be important for us to settle on a _________
Mathematical model of computation
13. In average-case time analysis of quick sort algorithm, the most balanced case for partition is when we divide the list of elements into _____
Three nearly equal pieces
14. An algorithm is a mathematical entity, which is independent of ________
Programming language, compiler and machine
15. In dynamic programming based solution of knapsack problem, to compute entries of “V”, we will imply a(n) ______ approach.
Inductive
16. In selection algorithm, we assume pivot selection takes theta _____ running time n
17. If input “n” is odd, the median will be ______
(N+1)/2
18. The asymptotic growth of (N+1)/2 is
O(n^2)
19. In generating Fibonacci sequence, we can avoid unnecessary repititions by _____ process.
Memoization
1) In selection problem, the sieve technique works in--------------
Ans: Phases (pg#34)
2) If a matrix has three rows and two columns, then dimensions of matrix will be:
Ans: 3×2 ( Dimensions of matrix = row×column)
3) When a heapify procedure is applied to the root node to restore the heap, then at each level, the comparison performed takes time:
Ans: it will take Θ(1) (pg#43)
4) If there are Θ(n2) entries in edit distance matrix then the total running time is: Ans: Θ(n2) (pg#84)
5) The O-notation is used to state only the asymptotic---------- Bounds.
Ans: upper (pg#25)
6) The worst-case running time of Quick sort is------------- in order to sort an array of n element.
Ans: Θ(n) (pg#49)
7) The omega-notation allows us to state only the asymptotic-------- bounds. Ans: Lower (pg#25)
8) Dynamic programming formulation of the matrix chain multiplication problem will store the solution of each sub problem in a(n): Ans: (Table) (pg#86)
9) If the time complexity of an algorithm is given by O(1), then time complexity would be:
Ans: Constant (pg#26)
10) Which of the following is calculated with big O notation? Ans : Upper Bounds (pg#25)
11) Insertion sort is an efficient algorithm for sorting a----------------- number of elements.
Ans: Large (pg#39)
12) Chain matrix multiplication problem can be solved through----------- strategy. Ans: Dynamic programming (pg#85) 13) In recursive formulation of Knapsack Problem:
V[0.j] = ------------- for j>=0
Ans: 0 (pg#93)
14) For -------- values of n, any algorithm is fast enough. Ans: small (pg#14)
15)
 |
Counting sort is suitable to sort the elements in range 1 to k: Ans: k is small (pg#57)
16) Quick sort ------------- based on Divide and conquer strategy.
Ans always (pg#46)
17) In the statement “if (P[i].x<P[j].x)& (P[i].y<P[j].y)” the number of times elements of P are accessed is-------------
Ans: 4 (pg#14)
18) ---------------overcome the limitation of -------------- by working as per positional notations of numbers.
Radix sort, Counting sort (pg#71)
19) While sorting, the ordered domain means for any two input elements x and y ------------ satisfy only.
Ans: All given (x<y, x>y, x=y) (pg#39)
20) We can improve the performance of Quick sort if we can be able to--------------- Ans: Skip any sub-array completely (google search.not found in book)
21) Pseudo code of algorithms to be read by------------- Ans : People (pg#12)
22) In Heap Sort algorithm, the maximum levels an element can move up word
Ans Θ(log n) (pg#43)
1) The time assumed for each basic operation to execute on RAM model of computation is : ----------------
Ans : Constant (pg#10)
2) The definition of Theta-notation relies on proving ------------------ asymptotic bounds.
Ans: Both lower and upper (pg#25)
 |
3) In asymptotical analysis of n(n-3) and 4n*n, as n becomes large, the dominant(fastest growing) term is some constant times-----------
Ans : n*n (pg#23)
4) ------------- items are not allowed in the 0/1 knapscak.
Ans : fractional (pg#91)
5) We can improve the performance of Quick Sort if we can be able to-------
Ans : Skip any sub-array completely ( Reapeat)
6) In Quick Sort algorithm, Pivots form-------------
Ans: Binary Search Tree (pg#49)
7) An in-place sorting algorithm is one that -------------- uses additional array for storage.
Ans: Does not (pg#54)
8) The running time of Quick sort algorithm ---------------
2 Comments