Binary Search efficiently finds an element in a sorted array by repeatedly dividing the search interval in half. This leads to a logarithmic time complexity of O(log n), making it much faster than linear search for large datasets.
Which algorithm is used for string matching?
A Merge Sort
B Binary Search
C Rabin-Karp
D Quick Sort
The Rabin-Karp algorithm is a string matching algorithm that uses hashing to find a pattern within a text. It computes hash values for the pattern and substrings of the text to identify matches efficiently, especially for multiple patterns.
Which of the following is true about Interpolation Search?
A Works on sorted arrays
B Uses recursion
C Uses binary division
D Works on unsorted arrays
Interpolation Search works on sorted arrays by estimating the position of the target value based on a linear interpolation formula. Its performance is better than Binary Search for uniformly distributed data, but it still requires sorted data.
What is the primary disadvantage of Linear Search?
A Requires recursion
B Only works on sorted arrays
C Cannot handle duplicates
D High time complexity
Linear Search has a time complexity of O(n), which makes it inefficient for large datasets. It checks each element in the array sequentially, making it slower compared to more efficient algorithms like Binary Search.
Which algorithm is known for its worst-case time complexity of O(n^2)?
A Binary Search
B Naive String Matching
C Rabin-Karp
D Interpolation Search
The Naive String Matching algorithm checks all possible positions of the pattern within the text. In the worst case, it has a time complexity of O(n^2), which makes it inefficient compared to more advanced string matching algorithms.
What is the time complexity of the KMP (Knuth-Morris-Pratt) string matching algorithm?
A O(n)
B O(n log n)
C O(n^2)
D O(log n)
KMP (Knuth-Morris-Pratt) string matching algorithm improves efficiency by using preprocessing to create a partial match table. This allows it to skip unnecessary comparisons, resulting in a time complexity of O(n), where n is the length of the text.
Which of the following is true about Binary Search?
A It works on unsorted arrays
B It uses a linear scan
C It requires sorted arrays
D It works on linked lists
Binary Search is an efficient algorithm that works only on sorted arrays. It divides the array in half each time, reducing the search space logarithmically. It cannot be applied to unsorted arrays.
What is the space complexity of Binary Search?
A O(n)
B O(1)
C O(log n)
D O(n log n)
Binary Search has a space complexity of O(1) because it only requires a constant amount of extra space for variables like indices. Unlike algorithms like Merge Sort, it does not need additional space for recursion or storing intermediate results.
Which algorithm is used to find the longest prefix-suffix in string matching?
A Rabin-Karp
B Binary Search
C Interpolation Search
D KMP
The KMP (Knuth-Morris-Pratt) algorithm uses a partial match table (also known as the longest prefix-suffix table) to efficiently find the longest prefix that is also a suffix, optimizing string matching by avoiding unnecessary re-checks of characters.
What is the advantage of using Rabin-Karp over other string matching algorithms?
A Better for small datasets
B Handles large alphabet sizes efficiently
C Handles multiple pattern matches efficiently
D Works without hashing
The Rabin-Karp algorithm excels at matching multiple patterns against a text. By using hash functions, it can compare several patterns in parallel, significantly improving efficiency when searching for multiple substrings in a large text.
What type of data does Interpolation Search work best with?
A Uniformly distributed data
B Random data
C Data with fixed patterns
D Unsorted data
Interpolation Search works best with uniformly distributed data. It uses an interpolation formula to estimate the position of the target value, which allows it to outperform Binary Search when the data is evenly distributed.
Which algorithm improves the time complexity of Naive String Matching?
A Quick Sort
B Rabin-Karp
C KMP
D Merge Sort
KMP improves upon the Naive String Matching approach by preprocessing the pattern to avoid unnecessary comparisons, thus offering better performance.
Which algorithm is commonly used for string matching in text?
A Binary Search
B KMP
C Merge Sort
D Quick Sort
The Knuth-Morris-Pratt (KMP) algorithm is an efficient string-matching algorithm that preprocesses the pattern to avoid redundant comparisons, making it faster than brute force methods when searching for patterns in a text.
What is the space complexity of the Floyd-Warshall algorithm?
A O(n)
B O(n^3)
C O(n^2)
D O(log n)
The Floyd-Warshall algorithm requires O(n^2) space because it maintains a 2D array to store the shortest paths between all pairs of vertices. This space complexity is proportional to the square of the number of vertices in the graph.
What is the key advantage of Divide and Conquer algorithms?
A Recursively divides problems into smaller subproblems
B Works only with small problems
C Solves problems sequentially
D Requires large memory
Divide and conquer algorithms work by recursively breaking down a problem into smaller subproblems, solving each subproblem independently, and combining their results. This approach is effective for problems like sorting and searching.