Algo Quizes

1. 1There is no known algorithm to generate the prime numbers less than a given number n.

   1. ATrue
   2. BFalse
2. 2The study of algorithms is a new field of study.

   1. ATrue
   2. BFalse
3. 3The greatest common divisor problem can be solved by exhaustive search.

   1. ATrue
   2. BFalse
4. 4An algorithm may contain one or more ambiguous steps.

   1. ATrue
   2. BFalse
5. 5Empirical analysis is the preferable method to determine the efficiency of an algorithm.

   1. ATrue
   2. BFalse
6. 6Different algorithms can solve the same problem with different efficiency classes.

   1. ATrue
   2. BFalse
7. 7An algorithm should always terminate for each valid input.

   1. ATrue
   2. BFalse
8. 8For any given problem, only one algorithm can solve it.

   1. ATrue
   2. BFalse
9. 9There is a unique representation for any given algorithm.

   1. ATrue
   2. BFalse
10. 10An algorithm may not produce the correct output in some special cases.

    1. ATrue
    2. BFalse

11. 11Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
    
    f1(n) = 2^n
    f2(n) = n^(3/2)
    f3(n) = n Log n
    f4(n) = n^(Logn)

    1. Af3, f2, f4, f1
    2. Bf2, f3, f1, f4
    3. Cf3, f2, f1, f4
    4. Dnone of the choices
    5. Ef2, f3, f4, f1
12. 12In the worst case, sequential search takes n^2 comparisons to find a key in an array of size n^2.

    1. ATrue
    2. BFalse
13. 13n ∈ O(Log(n^3))

    1. ATrue
    2. BFalse
14. 14The efficiency class of an algorithm is always reported in terms of the worst case scenario.

    1. ATrue
    2. BFalse
15. 15Addition is the basic operation when multiplying 2 matrices.

    1. ATrue
    2. BFalse
16. 16The Order of growth of any function is calculated as n→∞.

    1. ATrue
    2. BFalse
17. 17he time complexity of the following function is (assume n > 0)
    
    
    
    int recursive (int n) {
    
    if(n == 1)
    
    return (1);
    
    else
    
    return (recursive (n-1) + 1);
    
    }
    
    

    1. AO(n)
    2. BO(n^2)
    3. Cnone of the choices
    4. DO(2^n)
    5. EO(n log n)
18. 18The time efficiency of an algorithm is measured in nanoseconds.

    1. ATrue
    2. BFalse
19. 19The time efficiency of an algorithm depends on the processor.

    1. ATrue
    2. BFalse
20. 20[log n]^3 ∈ O(n)

    1. ATrue
    2. BFalse
21. 21The average case time efficiency is always easier to calculate than the worst case.

    1. ATrue
    2. BFalse
22. 221000,000 n ∈ O(n^2).

    1. ATrue
    2. BFalse
23. 23The time efficiency of an algorithm in the average case scenario is calculated as the average of the worst and the best cases.
    
    

    1. ATrue
    2. BFalse
24. 24The time complexity of the following function is (assume n > 0)
    
    int recursive (int n) {
    if(n == 1)
    return (1);
    else
    return (recursive (n-1) + recursive (n-1));
    }
    
    

    1. AO(n^2)
    2. BO(2^n)
    3. CO(n)
    4. DO(n log n)
    5. Enone of the choices
25. 25The basic operation is the one that contributes most towards the running time of the algorithm.

    1. ATrue
    2. BFalse
26. 26Θ(n) is the minimum number of multiplications required to compute the value of a polynomial of order n at a given point.

    1. ATrue
    2. BFalse
27. 27Finding the shortest Hamiltonian circuit in a weighted connected graph has an exponential time complexity.

    1. ATrue
    2. BFalse
28. 28The time complexity of the brute-force algorithm for solving the assignment problem is Θ(n!).

    1. ATrue
    2. BFalse
29. 29The time complexity of the brute-force algorithm for solving the Knapsack problem is Θ(n!).

    1. ATrue
    2. BFalse
30. 30Selection sort is a Θ(n^2) algorithm on all inputs.

    1. Atrue
    2. BFalse
31. 31Exhaustive search methods provide good approximation for some problems.

    1. ATrue
    2. BFalse
32. 32In the Brute-force algorithm for solving the Closest-Pair Problem, the basic operation is the SQRT function.

    1. ATrue
    2. BFalse
33. 33On Average, bubble-sort requires no swaps.

    1. ATrue
    2. BFalse
34. 34In the best-case scenario, selection sort performs Θ(n) comparisons to sort an array of size n.

    1. ATrue
    2. BFalse
35. 35The brute-force string matching algorithm has a linear time complexity.

    1. ATrue
    2. BFalse
36. 36Matrix multiplication can be performed with Θ(n^2.8)

    1. ATrue
    2. BFalse
37. 37The recurrence relation for the worst case scenario of Quick sort is C(n) = 2C(n/2) + n-1

    1. ATrue
    2. BFalse
38. 38Given a binary search tree, the recurrence relation representing the worst case scenario for searching for a given key is:
    
    C(n) = C(n/2) + 1

    1. ATrue
    2. BFalse
39. 39The performance of a divide-and-conquer algorithm for solving the Closest-Pair Problem is Θ(n log n)

    1. ATrue
    2. BFalse
40. 40The worst case efficiency of Quickhull is Θ(n^2).

    1. ATrue
    2. BFalse
41. 41The recurrence relation for the best case scenario of merge sort is C(n) = C(n/2) + n-1

    1. ATrue
    2. BFalse
42. 42The recurrence relation for multiplying two n-digit numbers using a divid and conquer algorithm is:
    
    M(n) = 3M(n/2).

    1. ATrue
    2. BFalse
43. 43 Merge sort is a Θ(n log n) algorithm on all inputs.

    1. ATrue
    2. BFalse
44. 44If binary search is used to search for an item into a linked list, the recurrence relation is C(n) = C(n/2) + θ(n)

    1. ATrue
    2. BFalse
45. 45The worst case time complexity of Quicksort sort is Θ(n^2).

    1. ATrue
    2. BFalse
46. 46If anis computed as:
    
    a^n= a^n/2×a^n/2
    The time complexity is θ(n log n)

    1. Atrue
    2. Bfalse
47. 47If a^n is computed as:
    
    a^n=a^n−1×a
    The time complexity is θ(log n)

    1. ATrue
    2. BFalse
48. 48The best case time complexity of insertion sort is θ(n).

    1. ATrue
    2. BFalse
49. 49The worst case time complexity of insertion sort is θ(n log n).

    1. ATrue
    2. BFalse
50. 50The time complexity for the brute force approach for solving the fake coin problem is θ(n^2).

    1. ATrue
    2. Bfalse
51. 51The time complexity for the decrease-and-conquer algorithm for solving the fake coin problem is θ(log n).

    1. ATrue
    2. BFalse
52. 52The time complexity for Euclid's algorithm for finding the greatest common devisor is θ(n logn)

    1. ATrue
    2. BFalse
53. 53The average case for a decrease and conquer algorithm for finding the kth smallest element is Θ(n log n)

    1. ATrue
    2. BFalse
54. 54Interpolation Search is preferable to binary search only for VERY large arrays.

    1. ATrue
    2. BFalse
55. 55The average case time complexity for interpolation search is log(log n).

    1. ATrue
    2. BFalse
56. 56How many searches will be needed to justify the time spent on pre-sorting an array of 103 elements if sorting is done by merge sort and searching is done by binary search?

    1. A19
    2. B23
    3. C10
    4. Done
    5. E71
57. 57How many searches will be needed to justify the time spent on pre-sorting an array of 103 elements if sorting is done by selection sort and searching is done by binary search?

    1. A1913
    2. B716
    3. C2000
    4. D123
    5. E1010
58. 58The time complexity of a pre-sorting algorithm for solving the element uniqueness problem is Θ(n log n).

    1. ATrue
    2. BFalse
59. 59The mode value of a given list of numbers cannot be computed in less than Θ(n^2).

    1. ATrue
    2. BFalse
60. 60Gaussian Elimination algorithm transforms the coefficient matrix to an upper triangular matrix in

    1. Anone of the choices
    2. BΘ(n log n)
    3. CΘ(n^3)
    4. DΘ(n^2)
    5. EΘ(n)
61. 61The inverse of a matrix can be computed in
    
    

    1. AΘ(n^2)
    2. BΘ(n log n)
    3. Cnone of the choices
    4. DΘ(n^3)
62. 62The worst case efficiency of searching using a binary search tree is Θ(n).

    1. ATrue
    2. BFalse
63. 63The time efficiency of searching using an AVL tree is Θ(n log n).

    1. ATrue
    2. BFalse
64. 64The time efficiency of ternary search is Θ(log3 n).

    1. ATrue
    2. BFalse
65. 65Horner's Rule has the same time efficiency as the brute force approach for evaluating a polynomial of degree n.

    1. ATrue
    2. BFalse
66. 66In a weighted graph, the space efficiency of finding the shortest paths between every pair of vertices is Θ(n3)

    1. ATrue
    2. BFalse
67. 67The space efficiency of Warshall's Algorithm for finding the transitive closure is Θ(n).

    1. ATrue
    2. BFalse
68. 68The time complexity for computing the binomial coefficient C(n,k) using dynamic programming is Θ(n)

    1. ATrue
    2. BFalse
69. 69Solving the knapsack problem using dynamic programming has the same time complexity as the brute force approach.

    1. ATrue
    2. BFalse
70. 70All problems can be solved by dynamic programming.

    1. ATrue
    2. BFalse
71. 71In a weighted graph, the time efficiency of finding the shortest paths between every pair of vertices is Θ(n3)

    1. ATrue
    2. BFalse
72. 72The time complexity for computing the nth Fibonacci number using dynamic programming is Θ(n log n)

    1. ATrue
    2. BFalse
73. 73Computing the transitive closure of a graph using Warshall's Algorithm is more efficient than repeated calls of death first search.

    1. ATrue
    2. BFalse
74. 74Union-find data structure can be used to implement Kruskal's algorithm.

    1. ATrue
    2. BFalse
75. 75A greedy technique algorithm for solving the change-making problem provides the optimal solution for all denominations.

    1. ATrue
    2. BFalse
76. 76The length of the codeword generated by Huffman's algorithm for any given symbol is inversely proportional to the symbol's frequency in the encoded message.
    
    

    1. ATrue
    2. BFalse
77. 77Assuming a graph is represented by an adjacency matrix, the time efficiency for Prim's algorithm is Θ(n^2).

    1. ATrue
    2. BFalse
78. 78When building the Huffman's tree for a given message, all symbols should appear in the leaves of the tree.

    1. ATrue
    2. BFalse
79. 79Huffman's codes are uniquely decodable.

    1. ATrue
    2. BFalse
80. 80Assuming a graph is represented by an adjacency matrix, the time efficiency for Dijkstra's algorithm is Θ(nlogn).

    1. ATrue
    2. BFalse
81. 81Kruskal's algorithm is easier to implement compared to Prim's algorithm.

    1. ATrue
    2. BFalse
82. 82Prim's algorithm for finding the minimum spanning tree does not always yield the optimal solution.

    1. ATrue
    2. BFalse
83. 83Huffman's algorithm is used to generate fixed-length codewords.

    1. ATrue
    2. BFalse
84. 84Iterative improvement algorithms always produce the optimum solution.

    1. ATrue
    2. BFalse
85. 85An optimal solution for a linear programming problem can always be found at an extreme point of the problem's feasible region.

    1. ATrue
    2. BFalse
86. 86The worst-case efficiency of Simplex algorithm is exponential.

    1. ATrue
    2. BFalse
87. 87In the maximum flow problem, the network can have more than one sink nodes.

    1. ATrue
    2. BFalse
88. 88In the maximum flow problem, an intermediate vertex can store or consume a small amount of the material.

    1. ATrue
    2. BFalse
89. 89The maximum-flow problem can be solved as an instance of a linear programming problem.

    1. ATrue
    2. BFalse
90. 90A greedy algorithm for solving the maximum-flow problem always produces the optimum solution.

    1. ATrue
    2. BFalse
91. 91The value of the maximum flow in a network is equal to the capacity of its minimum cut.

    1. ATrue
    2. BFalse
92. 92A graph is bipartite if and only if it does not have a cycle of an odd length.

    1. ATrue
    2. BFalse
93. 93The maximum matching problem in a 2-colorable graph can be solved as an instance of the max flow problem.

    1. ATrue
    2. BFalse
94. 94The time complexity for Gale-Shapley Algorithm for solving the stable marriage problem is n^3.

    1. ATrue
    2. BFalse
95. 95Gale-Shapley Algorithm for solving the stable marriage problem produces the optimal solutions for both men and women at the same time.

    1. ATrue
    2. BFalse
96. 96The lower bound is tight if there exists an algorithm with the same efficiency as the lower bound.

    1. ATrue
    2. BFalse
97. 97The trivial lower bound for matrix multiplication is Θ(n^3)

    1. ATrue
    2. BFalse
98. 98The trivial lower bound for solving the travelling salesman problem
    
    is Θ(n).

    1. ATrue
    2. BFalse
99. 99Θ(n logn) is the minimum number of comparisons in the worst case for any comparison-based sorting algorithm.

    1. ATrue
    2. BFalse
100. 100The CNF satisfiability problem belongs to the class of P problems.

     1. ATrue
     2. BFalse
101. 101The travelling salesman problem in NOT an NP-complete.

     1. ATrue
     2. BFalse
102. 102Both backtracking and branch-and-bound techniques can be used to improve the time complexity of NP problems.

     1. ATrue
     2. BFalse
103. 103The nearest-neighbour algorithm for the travelling sales man problem has a bounded accuracy.

     1. ATrue
     2. BFalse
104. 104A greedy approach yields the exact solution for the continuous version of the knapsack problem.

     1. ATrue
     2. BFalse
105. 105If P ≠ NP, there exists no approximation algorithm for TSP with a finite performance ratio.

     1. ATrue
     2. BFalse

Descripción

Computer Science Test sobre Algo Quizes, creado por Nikholas Pcenicni el 21/04/2022.

Autor

Nikholas Pcenicni

Idioma

English

Visitas

15

Etiquetas

computer science

Valoración

Aún sin valoraciones

Valora este test

Valora este test

Más sobre Algorithm Analysis and Complexity