C S610-Computer Network

S OLVED MCQS QUIZ 1

LEACTURE (1 to 10)

Solved by JUNAID MALIK

1. In heap sort algorithm, the total running time for heavily procedure is

· Big-oh(log n)

· O (1) i.e. Constant time

· Theta (log n)

· Omega (log n)

2. Quick sort algorithm is required a lot of comparison in the

condition.

· Worse case

· Best and average case

· Average case

· Best case

3. In heap sort algorithm (using max heap). When every time maximum element is removed from top.

· Divide and conquer strategy helps us

· We are left with a lot

· We call merge sort algorithm

· It becomes order n2 algorithm

4. In average-case time analysis of quick sort algorithm,

The most balanced case for partition is where we divide the list of element into

· Three nearly equal pieces

· Single piece exactly

· Two nearly piece

· Equal no. of piece as of input element

5. Consider three matrices X,Y,Z dimensions 1×2.2×.3×4 respectively. The number of multiplication of (XYZ) is:

· 32

· 30

· 24

· 18

6. Quicksort is a/an and sorting algorithm.

· In-place, not stable one

· Not in-place, stable one

· In-place, stable one

· Not in-place, not stable one

7. items are not allowed in the 0/1 knapack.

· Lighter

· Whole

· Weighty

· Fractional

8. The main purpose of mathematical analysis is measuring the _ required by the algorithm.

· Space

· Execution time and memory

· Input & output

· Execution time

9. Execution time of an algorithm can be measured by _ .

· Divide and conquer approach

· Both brute force and divide and conquer approach

· Mathematical analysis

· Brute force approach

10. Quick sort is based on strategy.

· Graph theory

· Divide-and-conquer

· Dynamic programming

· Greedy approach

11. A sorting algorithm is called as _ _ if duplicate element remain in the same relative position after sorting.

· O(n) algorithm

· Stable

· Parallel

· Complex

12. Which one sorting algorithm is best suited to sort an array of 2 million elements?

· Insert sort

· Quick sort

· Merge sort

· Bubble sort

13. We can use the property to devise a recursive formulation of the edit distance problem.

· Algorithm

· Small substructure

· Optimal substructure

· Real

14. While sorting. The ordered domain means for any two input elements x and y _ satisfies only.

· All of the above

· x > y

· x < y

· x = y

15. 8n2 + 2n -3 will eventually exceed c2*(n) no matter how large we make _ .

· 2n

· n

· this equation

· c2

16. is a method of solving a problem in which we check all possible solution to the problem to find the solution we need.

· Sorting algorithm

· Greedy approach

· Plane-sweep algorithm

· Brute-force algorithm

17. In quick sort algorithm, provost form .

· Graph

· Stack

· Binary search tree

· Queue

18. In asymptotical analysis of n(n -3) and 4n*n, as n becomes large, the dominant (fastest growing) term is some constant time

· n +1

· n*n

· n

· n-1

19. If Matrix-A has dimensions “3×2” and Matrix-B has dimensions “2×3”, then multiplication of Matrix –A and Matrix-B will result a new Matrix-C having dimensions

· 2×3

· 2×2

· 3×2

· 3×3

20. Boolean operation is a _ operation on an idealized RAM model of computation.

· Advance

· Normal

· Basic

· Starting

21. There are entries in the Edit Distance Matrix.

· ʘ (𝑛²)

· ʘ ( n+100)

· ʘ (n)

· ʘ (n+2)

22. Counting sort is suitable for sorting the elements within range 1 to P. where

· P is undetermined

· P is small

· P is very large

· P is large

23. Suppose we have 4 matrices A,B,C,D. what is correct expansion of m[1,2] in chain matrix multiplication?

· m[1,2] = m[1,1] + m[2,2] +p0 . p1. p3

24. Which one is not passed as parameter in Quick Sort algorithm?

· Array (containing input elements)

· Middle of the array

· Start of the array

· End of the array

25. In asymptotical analysis of n*(5+2)-3. As n becomes large, the dominant (fastest growing) term is some constant times

· n+1

· n*n

· n

· n_1

26. For values of n, any algorithm is fast enough.

· Medium

· Small

· Infinity

· Large

27. Dynamic programming algorithms often use some kind of

to store the result of intermediate sub-problems.

· Stack

· Loop

· Table

· Variable

28. In selection problem, the Sieve technique works in

· One complete go

· Constant time

· Non-recursive manner

· Phases

29. In heap Sort algorithm, the maximum levels an element can move upward is _ .

· Theta (log n)

· O (1) i.e. Constant time

· Omega (log n)

· Big-oh (log n)

30. While analysis of the brute-force maxima algorithm, an array storted in the reverse order is the type of case input.

· Worst

· Best

· Somewhat

· Average

31.1

Divide-and-Conquer is as breaking the problem into small number of

· Pivot

· Sieve

32.

Analysis of Selection Sort ends up with

· T(1/1+n)

· T(n/2)

· T((n/2) +n)

33. For a digraph G = (V, E), Sum of in-degree(v) _

· Not equal to Sum of out-degree(v)

· = Sum of out-degree(v)

· < Sum of out-degree(v)

· Sum of out-degree(v)

34. In problem, we want to find the best solution.

· Minimization

Averaging

· DFS

· BFS

· Both DFS & BFS

· None

36. The Huffman codes provide a method of _ data efficiently.

Select correct option

· Reading

· Encoding

· Decoding

· Printing

37. In greedy algorithm, at each phase, you take the you can get right now, without regard for future consequences.

· Worst

· Minimum

· Good

· Best

38. In Activity selection (using Greedy approach), intuitively _ .

· Short activities are not preferable

· There are always short activities as input

· We do not like long activities

· It does not matter about the length of activities

39. Breadth-first search begins at a root node and inspects all the nodes except neighboring ones.

Select correct option

· True

· False

40. The ancient Roman politicians understood an important principle of good algorithm design that is plan-sweep algorithm.

· True

· False (p27) [Divide and Conquer]

41. In 2d-space a point is said to be if it is not dominated by any other point in that space.

· Member

· Minimal

· Maximal

Join

44. In the analysis of Selection algorithm, we make a number of passes, in fact it

could be as many as

· T(n)

· T(n/2)

· Log n

· n/2+n/4

45. The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.

· True

· False

46.f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same for large n.

· Results

· Variables

· Size

· Growth Rates

47.8n2 + 2n - 3 will eventually exceed c2*(n) no matter how large we make c2.

· True

· False

· If we associate (x, y) integers pair 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.Fast

· Slow

· Expensive

· Cheap

48. For the sieve technique we solve the problem

· Recursively

· Mathematically

· Precisely

· Accurately

49. Analysis of Selection algorithm ends with,

· T(n)

· T(n/2)

· Log n

· n/2+n/4

50. The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Hre Upper Bound means the function f(n) grows asymptotically faster than n log n.

· More

Quiet

· At Least

51. The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.

True

52. After sorting in merge sort algorithm, merging process is invoked.

· True

· False

53. Asymptotic growth rate of the function is taken over case running time.

· Best

· Average

· Worst

· Normal

54. In analysis of f(n)=n(n/5)+n-10 log n, f(n) is asymptotically equivalent to _ .

· N

· 2n

· N+1

· N2

55. Algorithm is concerned with...... issues

· Macro

· Micro

· Both Macro & Micro

· Normal

56. We cannot make any significant improvement in the running time which is better than that of brute-force algorithm.

· True

· False

57. In addition to passing in the array itself to Merge Sort algorithm, we will pass in

other arguments which are indices.

· TWO

· THREE

· FOUR

· FIVE

58. Brute-force algorithm uses no intelligence in pruning out decisions.

· True

· False

59. In analysis, the Brute-force algorithm uses no intelligence in pruning out decisions at least as fast as its largest term.

· TRUE

· FALSE

60. Efficient algorithm requires less computational

· Memory

· Running Time

· Memory and Running TIME

· Energy

61. The O-notation is used to state only the asymptotic bounds.

· Two

· Lower

· Upper

· Both Lower & upper

62. Heaps can be stored in arrays without using any pointers; this is due to the

nature of the binary tree.

· Left-complete

· Right-complete

· Tree Nodes

· Tree Levees

63...... of reference is an important fact of current processor technology

· Defining

· Assigning

· Formality

· Locality

64. In the analysis of Selection algorithm, we get the convergent series.

· Harmonic

· Linear

· Arithmetic

· Geometric

65. Brute-force algorithm for 2D-Maxima is operated by comparing pairs of points.

· TWO

· SOME

· MOST

· ALL

66. In we have to find rank of an element from given input.

· Merge Sort Algorithm

· Selection Problem

· Brute Force Technique

· Plane Sweep algorithm

67. The sequence of merge sort algorithm is:

a. Divide Combine-Conquer

b. Conquer-Divide-Combine

c. Divide-Conquer-Combine Page 27

d. Combine-Divide-Conquer

68. In Selection algorithm, we assume pivot selection takes theta running time.

b. n2

c. n3

d. log (n)

69. Result of asymptotical analysis of n(n -3) and 4n*n is that

a. n(n-1) is asymptotically Less

b. n(n-1) is asymptotically Greater

c. Both are asymptotically Not equivalent

d. Both are asymptotically Equivalent page 23 (4n*n= 4n2)

70. Floor and ceiling are to calculate while analyzing algorithms

a. Very easy

b. Usually considered difficult P-31

c. 3rd Option is missing

d. 4th Option is missing

71. of reference is an important fact of current processor technology.

a. Defining

b. Assigning

c. Formality

d. Locality P-8

72. Which of the following is calculated with Big O notation?

a. Medium bounds

c. Lower bounds

d. Both upper and lower bounds

73. Al-Khwarizmi was a/an

a. Artist

b. Mathematician P-7

c. Astronomer

d. Khalifah

74. In average-case time analysis of Quick sort algorithm, the most balanced case for partition is when we divide the list of elements into _.

a. Equal no. of pieces as of input elements

b. Single piece exactly

c. Two nearly equal pieces

d. Three nearly equal pieces

75. Which of the following is calculated with Big O notation?

a. Medium bounds

c. Lower bounds

b. Both upper and lower bounds

76. Pseudo code of algorithms are to be read by .

b. RAM

c. Computer

d. Compiler

77. The definition of theta-notation relies on proving asymptotic bound.

a. One

b. Lower

c. Upper

78. In merge sort algorithm, to merge two lists of size n/2 to a list of size n, takes

time.

b. Theta log(n)

c. Theta log2(n)

d. Theta n log(n)

79. We can make recursive calls in Fibonacci Sequence.

a. Infinite

c. Only one

d. Zero

80. The sieve technique is a special case, where the number of sub- problems is Just

b. 2

c. 3

d. 4

81. When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has _ sub- problems.

b. Over costing

c. Optimized

d. Three

82. Sieve technique is very important special case of Divide-and-Conquer strategy.

a. True P-34

b. False

83. In order to say anything meaningful about our algorithms, it will be important for us to settle on a .

a. Java Program

b. C++ Program

c. Pseudo program

d. Mathematical model of computation P-10

84. Merge sort is based on .

a. Brute-force

b. Plan-sweep

c. Axis-sweep

d. Divide and Conquer P-27

85. What time does Merge Sort algorithm take in order to sort an array of 'n' numbers?

a. (n)

b. (log n)

c. (n^2)

d. (n log n) Google Search 31. In Heap Sort

86. 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.

a. Array

b. Queue

d. Tree

87. time is the maximum running time over all legal inputs.

b. Average-case

c. Best-case

d. Good-case

88. Efficient algorithm requires less computational...

a. Memory

b. Running Time

d. Energy

89. The Iteration method is used for

a. Comparing sorting algorithms only

c. Merging elements in Merge sort

d. Dividing elements in Merge sort

90. Median is not useful measure of central tendency of given input set especially when the distribution of values is highly skewed.

a. True

91. The Omega-notation allows us to state only the asymptotic

bounds.

a. Middle

c. Upper

d. Both lower & upper

92. In the statement “output P[1].x, P[1].y”, the number of times elements of P are accessed is .

a. 1

b. 3

c. 4

93. The main purpose of mathematical analysis is measuring the required by the algorithm.

a. Space

b. Execution time P-13

c. Inputs & outputs

d. Execution time and memory

94. provides us more accurate result when input values are not closer with each other

a. Average

b. Median P-34

c. Mode

d. Mean

95. The process of ends when you are left with such tiny pieces remaining that it is trivial to solve them.

a. Brute-force

b. Plan-sweep

c. Divide and Conquer P-27

d. Axis-sweep

96. Approach of solving geometric problems by sweeping a line across the plane is called sweep.

a. Line

b. Plane Page 18

c. Cube

d. Box

97. In the analysis of Selection algorithm, we get the convergent

a. Harmonic

b. Linear

c. Arithmetic

98. A Random Access Machine (RAM)is an idealized machine withrandom access memory.

b. 512 MB

c. 256 MB

d. 2 GBs

99. While analyzing Selection algorithm, we make a number of passes, in fact it could be as many as

a. n(n+1)

c. n/3

d. n/4

100. In Random Access Machine (RAM), instructions are executed in

a. Parallel

b. Batch

d. Multiple times

101. In selection problem, the rank of an element will be its

position

a. First

c. Second last

d. Last

102. The worst-case running time of Merge sort is in order to sort an array of n elements.

a. O(log n)

b. O(n)

d. O(n)

103. f(n) and g(n) are asymptotically equivalent. This means that they have essentially the same .

a. Results

b. Variables

c. Size

d. Growth rates P:23

104. An algorithm is a mathematical entity. Which is independent of

a. Programming language

b. Machine and Programming language

c. Compiler and Programming language

d. Programming language Compiler and Machine P:07

105. In Selection problem, the Sieve technique works in

a. Non-recursive manner

b. Constant time

c. Phases page 34

d. One complete go

106. Algorithm is a sequence of computational steps that

---- the input into output.

a. Merge

b. Assign

c. Transform page 7

d. Integrate

107. If pj dominates pi and pi dominates ph then pj also dominates ph, it means dominance relation is

a. Transitive page 18

b. Non Transitive

c. Equation

d. Symbolic

108. To find maximal points in brute-force algorithm each point of the space is compared against of that space.

a. One other point

c. Few other points

d. Most of the other points

109. In the following code the statement “cout<<j;”executes --------- times. for (j=1; j<=5; j = j+2)

cout<<j;

a. 5 times

b. 2 times

c. 3 times

d. 0 times

110. In merge sort algorithm, we split the array around the

index q. a. Entring

c. Exiting

d. Summing

111. In Selection problem, the Sieve technique .

a. Add some more input items each time

b. Do not work recursively

c. Do not uses Divide and Conquer approach d. Eliminates undesired data items each time

112. While Sorting, the order domain means for any two input elements x

and y

satisfies only.

b. x > y

c. x = y

d. All of the above

113. For solving Selection problem, we introduced Sieve technique due to

a. Using Decrease and Conquer strategy page 34

b. Avoiding to sort all input data

c. Eliminating Rank of an element

d. Using Brute-force approach

114. is one of the few problems, where provable lower bounds exist on how fast we can sort.

a. Searching

c. Both Searching & sorting

d. Growing

115. In plane sweep approach, a vertical line is swept across the 2d-plane from .

a. Right to Left

b. Left to Right page 18

c. Top to Bottom

d. Bottom to top

116. In generating Fibonacci sequence, we can avoid unnecessary repetitions by

process.

a. Tokenization

b. Memorization page 43

c. Randomization

d. Memorization

117. For values of n, any algorithm is fast enough.

b. Medium

c. Large

d. Infinity

118. Single item from a larger set of .

a. Constant

b. Pointers

c. Phases

119. Brute-force algorithm for 2D-Maxima is operated by comparing

pairs of points.

a. Two

b. Some

c. Most

120. For the Sieve Technique we take time.

b. IT(n / 3)

c. n^2

d. n/3

121. Asymptotic growth rate of the function is taken over

case running time. .

a. Best

c. Average

d. Normal

122.The sieve technique is a special case, where the number of sub problems is just.

a. 5

b. Many c. 1 page 34

d. Few

123. In Quick sort, we don’t have the control over the sizes of recursive calls.

a. True page 49

b. False

c. Less information to decide

d. Ether true or false

124. Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their coordinates. .

b. Y

c. Z

d. X , Y

125.Random access machine or RAM is a/an.

a. Machine build by Al-Khwarizmi

b. Mechanical machine

d. Electronics machine

126.Cubic function will a quadratic function.

a. Prove

b. be equal to

c. find

127.Asymptotic growth of 8n^2 + 2n – 3 is:

a. Θ(n^2 + n)

c. Θ(8n^2)

d. Θ(8n^2 + 2n)

128. In average-case time the probability of seeing input is denoted by

a. p{I}

b. p[I]

c. p<i>

129.While applying the Sieve technique to selection sort, how to choose a pivot element.

a. Through mean

b. Linear

d. Sequentially

130.Number of of the pseudo code are counted to measure the running time.

a. Inputs

b. Outputs c. Steps page 13

d. Pages

131. 8n^2+2n+3 will exceed c28(n), no matter how large we make

b. 2

d. this quadratic equation

132. In 2-d maxima problem a point p is said to be dominated by point q if

a. p.x <= q.x

c. p.y <= q.y

d. p.x >= q.x and p.y >=q.y

133.Sorting can be in .

a. Increasing order only

b. Decreasing order only

c. Both increasing and decreasing order

d. Random order

134. Recurrence can be described in terms of .

a. Array

b. Linear

d. Graph

135. The brute-force algorithm for 2D-Maxima runs in order O( ) time.

b. n(log n)

d. n3

136.In plane sweep approach of solving geometric problems, a is swept across the plane.

b. Plane

c. Cube

d. Box

137.Which of the following is calculated with Big Omega notation?

a. Medium bounds

b. Upper bounds

c. Lower bounds Page - 25

d. Both upper and lower bounds

138. is always based on divide and conquer strategy.

a. Bubble sort

b. Selection sort

c. Pigeon sort d. Quick sort page 46

139.If a matrix has three rows and two columns, then dimensions of matrix will be:

a. 3x2

b. 2x3

c. 3x3

d. 2x2

140. Asymptotic notations are used to describe _ of an algorithm.

a. Length

b. running time google

c. size

d. compile time

141.The time assumed for each basic operation to execute on RAM model of computation is .

a. Infinite

b. Continuous

d. Variable

142.Boolean operation is a operation on an idealized RAM model of computation.

a. Starting b. Basic page 10

c. Advance

d. Normal

143. If we have an equation 8n2+7f*n + 5f + 6 then is large,

term will be muchxxxxxxxthe n term and will dominate the running time.

a. f g (n)

b. g (n) * 2 c. n * 2 page 23

d. f (n)

144.In quick sort algorithm, we choose pivot .

a. Always the smallest element

b. Greater than 5 c. Randomly page 35

d. Less than 5

145.The problem with the brute-force algorithm is that is uses in pruning out de

a. Worst-case time

c. Outside looping

d. Artificial intelligence

cs502 quiz

1. In heap sort algorithm, the total running time for heavily procedure is

Contact Form