NEW
Font size
WorksheetsDAA quiz
Total questions: 50
Worksheet time: 25mins
What is the primary goal of algorithm analysis?
To optimize code length
To improve code readability
To determine algorithm efficiency
To reduce memory usage
Which of the following is a characteristic of an algorithm?
Finite input size
Infinite loop
Well-defined output
No clear termination
What does Big O notation represent?
Best-case scenario
Average-case scenario
Worst-case scenario
Exact running time
Which notation is used to describe the lower bound of an algorithm's running time?
Big O
Big Ω
Big Θ
Big σ
What does Big Θ notation represent?
Upper and lower bounds
Only upper bound
Only lower bound
Average-case scenario
What is the time complexity of a simple for loop?
O(n)
O(n^2)
O(log n)
O(1)
How do you analyze the time complexity of a non-recursive algorithm?
Using recursion tree method
Using master theorem
Counting basic operations
Using substitution method
What is the time complexity of a recursive algorithm with two recursive calls?
O(n)
O(n^2)
O(2^n)
O(log n)
Which method is used to analyze recursive algorithms?
Substitution method
Recursion tree method
Iteration method
All of the above
What is the time complexity of the Floyd-Warshall algorithm for finding shortest paths in a weighted graph?
O(n^2)
O(n^3)
O(n^4)
O(2^n)
Which of the following algorithms has a time complexity of O(n log n) in the average case?
Quicksort
Mergesort
Heapsort
Radix sort
What does the notation Ω(g(n)) represent in terms of the function f(n)?
f(n) grows faster than g(n)
f(n) grows slower than g(n)
f(n) grows at the same rate as g(n)
f(n) is bounded above by g(n)
Which of the following is true about the relationship between Big O and Big Ω?
If f(n) = O(g(n)), then f(n) = Ω(g(n))
If f(n) = Ω(g(n)), then f(n) = O(g(n))
If f(n) = O(g(n)), then f(n) ≠ Ω(g(n))
If f(n) = Ω(g(n)), then f(n) ≠ O(g(n))
What is the time complexity of the recursive algorithm with the recurrence relation T(n) = 3T(n/3) + n^2?
O(n^2)
O(n^2 log n)
O(n^3)
O(3^n)
Which method is used to solve the recurrence relation T(n) = T(n-1) + n?
Substitution method
Iteration method
Recursion tree method
Master theorem
What is the purpose of amortized analysis in algorithm design?
To determine the worst-case scenario
To determine the average-case scenario
To reduce memory usage
To improve code readability
Which of the following is a trade-off in algorithm design, especially in the context of dynamic programming?
Time vs. memory
Code length vs. readability
Efficiency vs. simplicity
All of the above
What is the time complexity of the closest pair algorithm using the divide-and-conquer approach?
O(n log n)
O(n^2)
O(n^3)
O(2^n)
Which of the following algorithms has a time complexity of O(n^2.81)?
Strassen's matrix multiplication
Coppersmith-Winograd algorithm
Karatsuba multiplication
Schönhage-Strassen algorithm
What is the purpose of the AKS primality test?
To determine whether a number is prime or composite
To factor large numbers
To determine the primality of a number in polynomial time
To improve code readability
Which of the following is a consequence of the P vs. NP problem?
If P=NP, then all NP-complete problems can be solved in polynomial time
If P≠NP, then all NP-complete problems cannot be solved in polynomial time
If P=NP, then all NP-complete problems cannot be solved in polynomial time
If P≠NP, then all NP-complete problems can be solved in polynomial time
What is the time complexity of the Bellman-Ford algorithm for finding shortest paths in a weighted graph?
O(n^2)
O(n^3)
O(n^4)
O(n*m)
What is the time complexity of a sequential search algorithm in the worst-case scenario?
O(n)
O(n^2)
O(log n)
O(n log n)
Which of the following is a characteristic of a sequential search algorithm?
It uses a sorted array
It uses a hash table
It compares each element in the array
It uses a binary search tree
What is the time complexity of a brute force algorithm for finding the closest pair of points in a set of n points?
O(n)
O(n^2)
O(n^3)
O(2^n)
Which of the following is a limitation of the brute force technique?
It is efficient for large datasets
It is easy to implement
It has a high time complexity
It is suitable for all problem types
What is the time complexity of the divide-and-conquer algorithm for finding the closest pair of points?
O(n log n)
O(n^2)
O(n^3)
O(2^n)
Which of the following is a key step in the closest pair algorithm?
Divide the points into two halves
Find the closest pair in each half
Combine the results from each half
All of the above
What is the space complexity of the brute force algorithm for finding the closest pair?
O(1)
O(n)
O(n^2)
O(2^n)
Which of the following is a variant of the closest pair problem?
Farthest pair
k-closest pairs
Closest pair in a graph
All of the above
What is the time complexity of the closest pair algorithm using a k-d tree?
O(n log n)
O(n^2)
c) O(n^3)
O(2^n)
Which of the following is a challenge in solving the closest pair problem?
Handling large datasets
Finding an efficient algorithm
Dealing with high-dimensional data
All of the above
What is the Convex Hull problem?
Finding the smallest polygon that encloses a set of points
Finding the largest polygon that encloses a set of points
Finding the closest pair of points in a set
Finding the farthest pair of points in a set
Which algorithm is used to solve the Convex Hull problem?
Graham's Scan
Jarvis' March
QuickHull
All of the above
What is the time complexity of Graham's Scan algorithm?
O(n)
O(n log n)
O(n^2)
O(2^n)
What is the Snake/Snap problem?
Finding the shortest path between two points in a grid
Finding the longest path between two points in a grid
Finding the closest pair of points in a grid
Finding the farthest pair of points in a grid
Which algorithm is used to solve the Snake/Snap problem?
A* algorithm
Dijkstra's algorithm
Bellman-Ford algorithm
Floyd-Warshall algorithm
What is the time complexity of the A* algorithm?
O(n)
O(n log n)
O(n^2)
O(2^n)
What is the purpose of the Convex Hull problem?
To find the smallest polygon that encloses a set of points
To find the largest polygon that encloses a set of points
To find the closest pair of points in a set
To find the farthest pair of points in a set
Which of the following is a variant of the Convex Hull problem?
Concave Hull
Convex Hull with holes
Convex Hull with obstacle
All of the above
What is the application of the Snake/Snap problem?
Robotics
Computer vision
Video games
All of the above
Which of the following is a requirement for Binary Search?
Sorted array
Unsorted array
Array with duplicates
Array with no duplicates
What is the time complexity of finding the minimum and maximum elements in an unsorted array?
O(n)
O(log n)
O(n log n)
O(n^2)
Which of the following algorithms can be used to find the minimum and maximum elements in an array?
Merge Sort
Quick Sort
Binary Search
Linear Search
What is the time complexity of Merge Sort?
O(n)
O(log n)
O(n log n)
O(n^2)
Which of the following is a characteristic of Merge Sort?
In-place sorting
Stable sorting
Adaptive sorting
All of the above
What is the average-case time complexity of Quick Sort?
O(n)
O(log n)
O(n log n)
O(n^2)
Which of the following is a disadvantage of Quick Sort?
Slow for small arrays
Slow for large arrays
Not stable
Not adaptive
What is the time complexity of Exhaustive Search?
O(n!)
Which of the following is an application of Exhaustive Search?
