Quiz
Algo Quizes
Create a free account to finish this quiz
Save your progress and see your final score.
Already have an account? Sign in
Questions in this quiz (105)
1There is no known algorithm to generate the prime numbers less than a given number n.
- ATrue
- BFalse
2The study of algorithms is a new field of study.
- ATrue
- BFalse
3The greatest common divisor problem can be solved by exhaustive search.
- ATrue
- BFalse
4An algorithm may contain one or more ambiguous steps.
- ATrue
- BFalse
5Empirical analysis is the preferable method to determine the efficiency of an algorithm.
- ATrue
- BFalse
6Different algorithms can solve the same problem with different efficiency classes.
- ATrue
- BFalse
7An algorithm should always terminate for each valid input.
- ATrue
- BFalse
8For any given problem, only one algorithm can solve it.
- ATrue
- BFalse
9There is a unique representation for any given algorithm.
- ATrue
- BFalse
10An algorithm may not produce the correct output in some special cases.
- ATrue
- BFalse
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)- Af3, f2, f4, f1
- Bf2, f3, f1, f4
- Cf3, f2, f1, f4
- Dnone of the choices
- Ef2, f3, f4, f1
12In the worst case, sequential search takes n^2 comparisons to find a key in an array of size n^2.
- ATrue
- BFalse
13n ∈ O(Log(n^3))
- ATrue
- BFalse
14The efficiency class of an algorithm is always reported in terms of the worst case scenario.
- ATrue
- BFalse
15Addition is the basic operation when multiplying 2 matrices.
- ATrue
- BFalse
16The Order of growth of any function is calculated as n→∞.
- ATrue
- BFalse
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);
}- AO(n)
- BO(n^2)
- Cnone of the choices
- DO(2^n)
- EO(n log n)
18The time efficiency of an algorithm is measured in nanoseconds.
- ATrue
- BFalse
19The time efficiency of an algorithm depends on the processor.
- ATrue
- BFalse
20[log n]^3 ∈ O(n)
- ATrue
- BFalse
21The average case time efficiency is always easier to calculate than the worst case.
- ATrue
- BFalse
221000,000 n ∈ O(n^2).
- ATrue
- BFalse
23The time efficiency of an algorithm in the average case scenario is calculated as the average of the worst and the best cases.
- ATrue
- BFalse
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));
}- AO(n^2)
- BO(2^n)
- CO(n)
- DO(n log n)
- Enone of the choices
25The basic operation is the one that contributes most towards the running time of the algorithm.
- ATrue
- BFalse
26Θ(n) is the minimum number of multiplications required to compute the value of a polynomial of order n at a given point.
- ATrue
- BFalse
27Finding the shortest Hamiltonian circuit in a weighted connected graph has an exponential time complexity.
- ATrue
- BFalse
28The time complexity of the brute-force algorithm for solving the assignment problem is Θ(n!).
- ATrue
- BFalse
29The time complexity of the brute-force algorithm for solving the Knapsack problem is Θ(n!).
- ATrue
- BFalse
30Selection sort is a Θ(n^2) algorithm on all inputs.
- Atrue
- BFalse
31Exhaustive search methods provide good approximation for some problems.
- ATrue
- BFalse
32In the Brute-force algorithm for solving the Closest-Pair Problem, the basic operation is the SQRT function.
- ATrue
- BFalse
33On Average, bubble-sort requires no swaps.
- ATrue
- BFalse
34In the best-case scenario, selection sort performs Θ(n) comparisons to sort an array of size n.
- ATrue
- BFalse
35The brute-force string matching algorithm has a linear time complexity.
- ATrue
- BFalse
36Matrix multiplication can be performed with Θ(n^2.8)
- ATrue
- BFalse
37The recurrence relation for the worst case scenario of Quick sort is C(n) = 2C(n/2) + n-1
- ATrue
- BFalse
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- ATrue
- BFalse
39The performance of a divide-and-conquer algorithm for solving the Closest-Pair Problem is Θ(n log n)
- ATrue
- BFalse
40The worst case efficiency of Quickhull is Θ(n^2).
- ATrue
- BFalse
41The recurrence relation for the best case scenario of merge sort is C(n) = C(n/2) + n-1
- ATrue
- BFalse
42The recurrence relation for multiplying two n-digit numbers using a divid and conquer algorithm is:
M(n) = 3M(n/2).- ATrue
- BFalse
43 Merge sort is a Θ(n log n) algorithm on all inputs.
- ATrue
- BFalse
44If binary search is used to search for an item into a linked list, the recurrence relation is C(n) = C(n/2) + θ(n)
- ATrue
- BFalse
45The worst case time complexity of Quicksort sort is Θ(n^2).
- ATrue
- BFalse
46If anis computed as:
a^n= a^n/2×a^n/2
The time complexity is θ(n log n)- Atrue
- Bfalse
47If a^n is computed as:
a^n=a^n−1×a
The time complexity is θ(log n)- ATrue
- BFalse
48The best case time complexity of insertion sort is θ(n).
- ATrue
- BFalse
49The worst case time complexity of insertion sort is θ(n log n).
- ATrue
- BFalse
50The time complexity for the brute force approach for solving the fake coin problem is θ(n^2).
- ATrue
- Bfalse
51The time complexity for the decrease-and-conquer algorithm for solving the fake coin problem is θ(log n).
- ATrue
- BFalse
52The time complexity for Euclid's algorithm for finding the greatest common devisor is θ(n logn)
- ATrue
- BFalse
53The average case for a decrease and conquer algorithm for finding the kth smallest element is Θ(n log n)
- ATrue
- BFalse
54Interpolation Search is preferable to binary search only for VERY large arrays.
- ATrue
- BFalse
55The average case time complexity for interpolation search is log(log n).
- ATrue
- BFalse
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?
- A19
- B23
- C10
- Done
- E71
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?
- A1913
- B716
- C2000
- D123
- E1010
58The time complexity of a pre-sorting algorithm for solving the element uniqueness problem is Θ(n log n).
- ATrue
- BFalse
59The mode value of a given list of numbers cannot be computed in less than Θ(n^2).
- ATrue
- BFalse
60Gaussian Elimination algorithm transforms the coefficient matrix to an upper triangular matrix in
- Anone of the choices
- BΘ(n log n)
- CΘ(n^3)
- DΘ(n^2)
- EΘ(n)
61The inverse of a matrix can be computed in
- AΘ(n^2)
- BΘ(n log n)
- Cnone of the choices
- DΘ(n^3)
62The worst case efficiency of searching using a binary search tree is Θ(n).
- ATrue
- BFalse
63The time efficiency of searching using an AVL tree is Θ(n log n).
- ATrue
- BFalse
64The time efficiency of ternary search is Θ(log3 n).
- ATrue
- BFalse
65Horner's Rule has the same time efficiency as the brute force approach for evaluating a polynomial of degree n.
- ATrue
- BFalse
66In a weighted graph, the space efficiency of finding the shortest paths between every pair of vertices is Θ(n3)
- ATrue
- BFalse
67The space efficiency of Warshall's Algorithm for finding the transitive closure is Θ(n).
- ATrue
- BFalse
68The time complexity for computing the binomial coefficient C(n,k) using dynamic programming is Θ(n)
- ATrue
- BFalse
69Solving the knapsack problem using dynamic programming has the same time complexity as the brute force approach.
- ATrue
- BFalse
70All problems can be solved by dynamic programming.
- ATrue
- BFalse
71In a weighted graph, the time efficiency of finding the shortest paths between every pair of vertices is Θ(n3)
- ATrue
- BFalse
72The time complexity for computing the nth Fibonacci number using dynamic programming is Θ(n log n)
- ATrue
- BFalse
73Computing the transitive closure of a graph using Warshall's Algorithm is more efficient than repeated calls of death first search.
- ATrue
- BFalse
74Union-find data structure can be used to implement Kruskal's algorithm.
- ATrue
- BFalse
75A greedy technique algorithm for solving the change-making problem provides the optimal solution for all denominations.
- ATrue
- BFalse
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.
- ATrue
- BFalse
77Assuming a graph is represented by an adjacency matrix, the time efficiency for Prim's algorithm is Θ(n^2).
- ATrue
- BFalse
78When building the Huffman's tree for a given message, all symbols should appear in the leaves of the tree.
- ATrue
- BFalse
79Huffman's codes are uniquely decodable.
- ATrue
- BFalse
80Assuming a graph is represented by an adjacency matrix, the time efficiency for Dijkstra's algorithm is Θ(nlogn).
- ATrue
- BFalse
81Kruskal's algorithm is easier to implement compared to Prim's algorithm.
- ATrue
- BFalse
82Prim's algorithm for finding the minimum spanning tree does not always yield the optimal solution.
- ATrue
- BFalse
83Huffman's algorithm is used to generate fixed-length codewords.
- ATrue
- BFalse
84Iterative improvement algorithms always produce the optimum solution.
- ATrue
- BFalse
85An optimal solution for a linear programming problem can always be found at an extreme point of the problem's feasible region.
- ATrue
- BFalse
86The worst-case efficiency of Simplex algorithm is exponential.
- ATrue
- BFalse
87In the maximum flow problem, the network can have more than one sink nodes.
- ATrue
- BFalse
88In the maximum flow problem, an intermediate vertex can store or consume a small amount of the material.
- ATrue
- BFalse
89The maximum-flow problem can be solved as an instance of a linear programming problem.
- ATrue
- BFalse
90A greedy algorithm for solving the maximum-flow problem always produces the optimum solution.
- ATrue
- BFalse
91The value of the maximum flow in a network is equal to the capacity of its minimum cut.
- ATrue
- BFalse
92A graph is bipartite if and only if it does not have a cycle of an odd length.
- ATrue
- BFalse
93The maximum matching problem in a 2-colorable graph can be solved as an instance of the max flow problem.
- ATrue
- BFalse
94The time complexity for Gale-Shapley Algorithm for solving the stable marriage problem is n^3.
- ATrue
- BFalse
95Gale-Shapley Algorithm for solving the stable marriage problem produces the optimal solutions for both men and women at the same time.
- ATrue
- BFalse
96The lower bound is tight if there exists an algorithm with the same efficiency as the lower bound.
- ATrue
- BFalse
97The trivial lower bound for matrix multiplication is Θ(n^3)
- ATrue
- BFalse
98The trivial lower bound for solving the travelling salesman problem
is Θ(n).- ATrue
- BFalse
99Θ(n logn) is the minimum number of comparisons in the worst case for any comparison-based sorting algorithm.
- ATrue
- BFalse
100The CNF satisfiability problem belongs to the class of P problems.
- ATrue
- BFalse
101The travelling salesman problem in NOT an NP-complete.
- ATrue
- BFalse
102Both backtracking and branch-and-bound techniques can be used to improve the time complexity of NP problems.
- ATrue
- BFalse
103The nearest-neighbour algorithm for the travelling sales man problem has a bounded accuracy.
- ATrue
- BFalse
104A greedy approach yields the exact solution for the continuous version of the knapsack problem.
- ATrue
- BFalse
105If P ≠ NP, there exists no approximation algorithm for TSP with a finite performance ratio.
- ATrue
- BFalse
Information
- Description
- Computer Science Quiz on Algo Quizes, created by Nikholas Pcenicni on 21/04/2022.
- Author
- Nikholas Pcenicni
- Language
- English
- Views
- 15
- Tags
- Rating
- No ratings yet Rate this quiz