1What is the primary characteristic of the brute-force string matching algorithm?
Sequential Search and Brute-Force String Matching
Easy
A.It requires the text to be sorted.
B.It uses hash functions.
C.It compares the pattern with every possible substring of the text.
D.It skips characters based on prefix-suffix matches.
Correct Answer: It compares the pattern with every possible substring of the text.
Explanation:
Brute-force string matching checks for the pattern starting at every possible position in the text without any preprocessing.
Incorrect! Try again.
2What is the worst-case time complexity of sequential search on an array of elements?
Sequential Search and Brute-Force String Matching
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
In the worst case, sequential search must check every element in the array, resulting in time complexity.
Incorrect! Try again.
3What does the Closest-Pair problem aim to find?
Closest-Pair and Convex-Hull Problem
Easy
A.The two points in a set with the minimum distance between them.
B.The boundary points of a set.
C.The center of the point set.
D.The two points in a set that are furthest apart.
Correct Answer: The two points in a set with the minimum distance between them.
Explanation:
The Closest-Pair problem involves finding two points in a given set that have the smallest Euclidean distance between them.
Incorrect! Try again.
4Which real-world object is often used to describe a Convex Hull?
Closest-Pair and Convex-Hull Problem
Easy
A.A spider web.
B.A labyrinth.
C.A rubber band stretched around a set of pegs.
D.A chess board.
Correct Answer: A rubber band stretched around a set of pegs.
Explanation:
A convex hull of a set of points is often visualized as the shape formed by a rubber band stretched tightly around the outermost points.
Incorrect! Try again.
5What is Exhaustive Search?
Exhaustive Search
Easy
A.An algorithm that divides the problem into smaller subproblems.
B.A technique used only for sorted arrays.
C.A method that uses heuristics to find a quick solution.
D.A problem-solving approach that evaluates all possible solutions.
Correct Answer: A problem-solving approach that evaluates all possible solutions.
Explanation:
Exhaustive search (or brute-force search) systematically generates and evaluates all candidate solutions to find the correct one.
Incorrect! Try again.
6What does a Voronoi diagram partition a plane into?
Voronoi Diagrams
Easy
A.Concentric circles.
B.Regions based on distance to a specific set of points.
C.Triangles.
D.Squares.
Correct Answer: Regions based on distance to a specific set of points.
Explanation:
A Voronoi diagram divides a plane into regions, or cells, where every point in a region is closer to its corresponding 'seed' point than to any other.
Incorrect! Try again.
7The Naive String-Matching Algorithm is equivalent to which of the following?
Naiva String-Matching Algorithm
Easy
A.Boyer-Moore Algorithm
B.Brute-Force String Matching
C.Knuth-Morris-Pratt Algorithm
D.Rabin-Karp Algorithm
Correct Answer: Brute-Force String Matching
Explanation:
The Naive String-Matching Algorithm checks for the pattern at all possible shifts, which is exactly how brute-force string matching operates.
Incorrect! Try again.
8What is the worst-case time complexity of the Naive String-Matching algorithm for a text of length and pattern of length ?
Naiva String-Matching Algorithm
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
In the worst case, the naive algorithm compares all characters of the pattern for each of the positions, yielding .
Incorrect! Try again.
9Which technique is heavily utilized in the Rabin-Karp Algorithm to find string matches?
Rabin-Karp Algorithm
Easy
A.Dynamic Programming
B.Divide and Conquer
C.Hashing
D.Greedy Approach
Correct Answer: Hashing
Explanation:
The Rabin-Karp algorithm uses a rolling hash function to quickly filter out positions where the pattern cannot match.
Incorrect! Try again.
10What is a 'spurious hit' in the context of the Rabin-Karp algorithm?
Rabin-Karp Algorithm
Easy
A.When the pattern is exactly at the beginning of the text.
B.When the hash values match but the actual strings do not.
C.When the algorithm fails to compute the hash.
D.When the hash values do not match but the strings do.
Correct Answer: When the hash values match but the actual strings do not.
Explanation:
A spurious hit occurs when the hash value of a text substring matches the hash of the pattern, but character-by-character comparison reveals they are different.
Incorrect! Try again.
11What is the primary advantage of the Knuth-Morris-Pratt (KMP) algorithm over naive string matching?
Knuth-Morris-Pratt Algorithm
Easy
A.It requires no preprocessing.
B.It avoids re-evaluating characters in the text that have already been matched.
C.It uses less memory.
D.It works on multiple patterns simultaneously.
Correct Answer: It avoids re-evaluating characters in the text that have already been matched.
Explanation:
KMP uses a prefix function (LPS array) to skip unnecessary comparisons, meaning the text pointer never moves backward.
Incorrect! Try again.
12What does the 'LPS' array in the KMP algorithm store?
Knuth-Morris-Pratt Algorithm
Easy
A.The length of the longest palindrome.
B.The ASCII values of the pattern.
C.The hash values of the characters.
D.The length of the longest proper prefix which is also a suffix.
Correct Answer: The length of the longest proper prefix which is also a suffix.
Explanation:
The LPS (Longest Proper Prefix which is also Suffix) array is used in KMP to determine how many characters can be skipped during a mismatch.
Incorrect! Try again.
13Which well-known problem is often solved using Exhaustive Search to evaluate all possible permutations?
Exhaustive Search
Easy
A.Merge Sort
B.Binary Search
C.Shortest Path in a DAG
D.Traveling Salesperson Problem (TSP)
Correct Answer: Traveling Salesperson Problem (TSP)
Explanation:
A brute-force solution to TSP evaluates all possible routes (permutations of cities) to find the shortest one.
Incorrect! Try again.
14In sequential search, if the target element is the very first item in the list, what is this case known as?
Sequential Search and Brute-Force String Matching
Easy
A.Average case
B.Best case
C.Base case
D.Worst case
Correct Answer: Best case
Explanation:
The best case for sequential search occurs when the target is found at the first position, taking time.
Incorrect! Try again.
15Which of the following describes the shape of a Convex Hull?
Closest-Pair and Convex-Hull Problem
Easy
A.A polygon with internal angles less than or equal to 180 degrees.
B.A straight line.
C.A circle.
D.A star-shaped polygon.
Correct Answer: A polygon with internal angles less than or equal to 180 degrees.
Explanation:
A convex hull is a convex polygon, meaning all its interior angles are 180 degrees or less, and it completely encloses the given set of points.
Incorrect! Try again.
16In a Voronoi diagram, the boundaries separating regions are formed by:
Voronoi Diagrams
Easy
A.Randomly drawn straight lines.
B.Perpendicular bisectors of the segments joining neighboring points.
C.Lines connecting all points.
D.Circles drawn around the points.
Correct Answer: Perpendicular bisectors of the segments joining neighboring points.
Explanation:
The edges of Voronoi cells are segments of perpendicular bisectors of the lines connecting adjacent seed points.
Incorrect! Try again.
17Why does the Rabin-Karp algorithm use modulo arithmetic?
Rabin-Karp Algorithm
Easy
A.To count the number of characters.
B.To sort the strings.
C.To prevent integer overflow when calculating large hash values.
D.To reverse the string.
Correct Answer: To prevent integer overflow when calculating large hash values.
Explanation:
Since hash values can become very large, modulo arithmetic with a prime number is used to keep them within the limits of standard integer types.
Incorrect! Try again.
18What is the time complexity of the preprocessing phase in the KMP algorithm for a pattern of length ?
Knuth-Morris-Pratt Algorithm
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The KMP algorithm preprocesses the pattern of length to construct the LPS array, which takes time.
Incorrect! Try again.
19Which of the following is a major drawback of Exhaustive Search?
Exhaustive Search
Easy
A.It is highly inefficient for large problem sizes.
B.It does not guarantee finding a solution.
C.It requires a sorted input.
D.It is difficult to implement.
Correct Answer: It is highly inefficient for large problem sizes.
Explanation:
Because exhaustive search checks every possible solution, its time complexity grows very rapidly (e.g., exponentially or factorially), making it impractical for large inputs.
Incorrect! Try again.
20What is the worst-case time complexity for a brute-force approach to solving the Closest-Pair problem for points?
Closest-Pair and Convex-Hull Problem
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
A brute-force approach calculates the distance between every possible pair of points, of which there are , resulting in time complexity.
Incorrect! Try again.
21In the Brute-Force string matching algorithm, what is the maximum number of character comparisons required to find a pattern of length in a text of length ?
Sequential Search and Brute-Force String Matching
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
In the worst case, the brute-force algorithm compares the pattern of length starting at every possible position up to , leading to comparisons, which is .
Incorrect! Try again.
22Which of the following scenarios represents the worst-case for the brute-force string matching algorithm?
Sequential Search and Brute-Force String Matching
Medium
A.Text = "AAAAAAAA", Pattern = "B"
B.Text = "ABABABAB", Pattern = "B"
C.Text = "AAAAAAAA", Pattern = "AAAB"
D.Text = "ABCDEFGH", Pattern = "FGH"
Correct Answer: Text = "AAAAAAAA", Pattern = "AAAB"
Explanation:
The worst case occurs when all characters of the pattern match the text except for the last one, forcing the algorithm to do maximum character comparisons before shifting.
Incorrect! Try again.
23What is the time complexity of solving the closest-pair problem using the divide-and-conquer approach?
Closest-Pair and Convex-Hull Problem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The divide-and-conquer algorithm recursively halves the point set and merges the results in time (after initial sorting), resulting in an overall time complexity of .
Incorrect! Try again.
24In Quickhull algorithm for finding the convex hull, which approach does it closely resemble?
Closest-Pair and Convex-Hull Problem
Medium
A.Quick Sort
B.Insertion Sort
C.Heap Sort
D.Merge Sort
Correct Answer: Quick Sort
Explanation:
Quickhull is similar to Quick Sort; it selects a pivot (the farthest point from a line) and recursively divides the problem into two subproblems, filtering out interior points.
Incorrect! Try again.
25Which of the following problems is classically solved using an exhaustive search approach by evaluating all permutations?
Exhaustive Search
Medium
A.Minimum Spanning Tree
B.Shortest Path Problem
C.Traveling Salesperson Problem (TSP)
D.Binary Search
Correct Answer: Traveling Salesperson Problem (TSP)
Explanation:
The brute-force or exhaustive search solution to TSP involves checking all possible routes to find the minimum distance.
Incorrect! Try again.
26Why is exhaustive search generally impractical for large inputs?
Exhaustive Search
Medium
A.Its time complexity usually grows exponentially or factorially.
B.It requires complex data structures.
C.It uses too much memory space.
D.It often produces suboptimal results.
Correct Answer: Its time complexity usually grows exponentially or factorially.
Explanation:
Exhaustive search systematically evaluates every possible solution, which often leads to exponential or factorial time complexities, making it impractical for large .
Incorrect! Try again.
27In a Voronoi diagram of a set of points in a 2D plane, what do the edges of the Voronoi polygons represent?
Voronoi Diagrams
Medium
A.The convex hull of the point set
B.The shortest distance between two points
C.The perpendicular bisectors of the segments joining neighboring points
D.The paths connecting all points in minimum distance
Correct Answer: The perpendicular bisectors of the segments joining neighboring points
Explanation:
A Voronoi edge is formed by points equidistant from two site points, meaning it lies on the perpendicular bisector of the line segment connecting those two sites.
Incorrect! Try again.
28What is the relationship between the Delaunay triangulation and the Voronoi diagram for a given set of points?
Voronoi Diagrams
Medium
A.They are dual graphs of each other.
B.There is no relationship.
C.They are identical.
D.Delaunay triangulation is the complement of the Voronoi diagram.
Correct Answer: They are dual graphs of each other.
Explanation:
The Delaunay triangulation is the dual graph of the Voronoi diagram. Drawing a line between any two points whose Voronoi cells share an edge yields the Delaunay triangulation.
Incorrect! Try again.
29If a pattern of length is matched against a text of length using the naive string matching algorithm, how many valid shifts are tested?
Naiva String-Matching Algorithm
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The naive algorithm slides the pattern over the text one position at a time. The possible starting positions range from index $0$ to , which totals shifts.
Incorrect! Try again.
30Which of the following is true regarding the naive string-matching algorithm?
Naiva String-Matching Algorithm
Medium
A.It requires no extra memory and checks every possible shift.
B.It requires preprocessing of the pattern.
C.It skips certain shifts based on previous matches.
D.Its best-case time complexity is .
Correct Answer: It requires no extra memory and checks every possible shift.
Explanation:
The naive algorithm does not preprocess the pattern or text, uses extra memory, and evaluates shifts sequentially without skipping.
Incorrect! Try again.
31The Rabin-Karp algorithm uses hashing. What is the primary purpose of the rolling hash in this algorithm?
Rabin-Karp Algorithm
Medium
A.To compute the hash of the next window in time.
B.To sort the characters of the pattern.
C.To detect duplicate characters in the text.
D.To avoid character comparisons entirely.
Correct Answer: To compute the hash of the next window in time.
Explanation:
A rolling hash allows the algorithm to update the hash value for the next window of text by removing the old character and adding the new character in time.
Incorrect! Try again.
32In the Rabin-Karp algorithm, what happens when a hash collision occurs (the hash of the pattern equals the hash of a text window)?
Rabin-Karp Algorithm
Medium
A.The window is skipped.
B.The algorithm must perform a character-by-character comparison to confirm the match.
C.The pattern is found, and the algorithm terminates.
D.The hash function is recomputed with a new prime modulus.
Correct Answer: The algorithm must perform a character-by-character comparison to confirm the match.
Explanation:
Because two different strings can have the same hash value (spurious hit), a direct character-by-character check is necessary to verify an actual match.
Incorrect! Try again.
33What is the primary optimization that the Knuth-Morris-Pratt (KMP) algorithm provides over the naive string-matching algorithm?
Knuth-Morris-Pratt Algorithm
Medium
A.It avoids re-evaluating characters in the text that have already matched.
B.It compresses the text before searching.
C.It hashes the text to speed up comparisons.
D.It searches from right to left instead of left to right.
Correct Answer: It avoids re-evaluating characters in the text that have already matched.
Explanation:
KMP utilizes a prefix table (LPS array) to skip unnecessary character comparisons, ensuring that the text pointer never moves backward.
Incorrect! Try again.
34In the KMP algorithm, what does the LPS (Longest Proper Prefix which is also Suffix) array store for a pattern?
Knuth-Morris-Pratt Algorithm
Medium
A.The lengths of the longest proper prefix that matches a proper suffix for every sub-pattern.
B.The indices of non-matching characters.
C.The hash values of all prefixes.
D.The distance to the next identical character.
Correct Answer: The lengths of the longest proper prefix that matches a proper suffix for every sub-pattern.
Explanation:
The LPS array stores the length of the longest proper prefix of the pattern up to index that is also a suffix of the pattern up to index .
Incorrect! Try again.
35Compute the LPS (Longest Proper Prefix which is also Suffix) array for the pattern "ABABC".
Knuth-Morris-Pratt Algorithm
Medium
A.[0, 0, 1, 2, 1]
B.[0, 0, 0, 0, 0]
C.[0, 0, 1, 2, 0]
D.[0, 1, 2, 3, 0]
Correct Answer: [0, 0, 1, 2, 0]
Explanation:
For "A": 0. For "AB": 0. For "ABA": prefix "A" matches suffix "A", so 1. For "ABAB": prefix "AB" matches suffix "AB", so 2. For "ABABC": no proper prefix matches suffix, so 0. Result: [0, 0, 1, 2, 0].
Incorrect! Try again.
36Which of the following is true about Brute-Force string matching?
Sequential Search and Brute-Force String Matching
Medium
A.It is the most optimal string matching algorithm in all cases.
B.It performs better than KMP for highly repetitive patterns.
C.It can backtrack the text pointer after a mismatch.
D.It requires a preprocessing phase.
Correct Answer: It can backtrack the text pointer after a mismatch.
Explanation:
In the brute-force algorithm, if a mismatch occurs after partially matching a pattern, the text pointer is moved back to the next starting character, resulting in backtracking.
Incorrect! Try again.
37In the divide-and-conquer algorithm for the Closest-Pair problem, during the combine step, how many points in the strip at most need to be checked for a given point?
Closest-Pair and Convex-Hull Problem
Medium
A.
B.7
C.11
D.2
Correct Answer: 7
Explanation:
Due to geometric constraints within the strip of width , a point can have at most 7 points (or 6 depending on the exact bounds) strictly closer than inside the checking rectangle.
Incorrect! Try again.
38What is the worst-case time complexity of the Rabin-Karp algorithm, and when does it occur?
Rabin-Karp Algorithm
Medium
A., when the text contains special characters.
B., when there are no hash collisions.
C., when the hash function uses large primes.
D., when all window hash values match the pattern hash value.
Correct Answer: , when all window hash values match the pattern hash value.
Explanation:
The worst case occurs if every text window yields a spurious hit (or actual match), requiring time per window to verify, resulting in overall.
Incorrect! Try again.
39What is the time complexity of the preprocessing step to build the LPS array in the KMP algorithm for a pattern of length ?
Knuth-Morris-Pratt Algorithm
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The LPS array is constructed by iterating through the pattern once with a few localized backups, taking time.
Incorrect! Try again.
40Which set of points uniquely defines the convex hull of a planar point set?
Closest-Pair and Convex-Hull Problem
Medium
A.The extreme points that form the boundary of the smallest convex polygon enclosing all points.
B.The points that lie strictly inside the bounding box.
C.The points with the minimum and maximum x and y coordinates.
D.The collinear points in the set.
Correct Answer: The extreme points that form the boundary of the smallest convex polygon enclosing all points.
Explanation:
A convex hull is defined uniquely by its extreme points (vertices), which form the smallest convex polygon that completely encloses all points in the given set.
Incorrect! Try again.
41In the Brute-Force string matching algorithm, what is the exact maximum number of character comparisons required to find all occurrences of a pattern of length in a text of length , assuming overlapping occurrences are counted?
Sequential Search and Brute-Force String Matching
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The algorithm shifts the pattern to possible positions. At each position, it may make up to comparisons in the worst case (e.g., text consists of all 'A's and pattern is all 'A's), resulting in exactly comparisons.
Incorrect! Try again.
42Consider a text of length and a pattern of length where all characters are distinct. How many comparisons does the Brute-Force algorithm make in the worst case if is not in ?
Sequential Search and Brute-Force String Matching
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Since all characters in the pattern are distinct, a mismatch will occur on the first character for any position unless it matches. If is not in , at worst, the first character matches, but the second fails. Because all characters are distinct, the worst-case number of comparisons is bounded tightly to rather than .
Incorrect! Try again.
43In the divide-and-conquer algorithm for the Closest-Pair problem, points in the strip of width are sorted by their -coordinates. What is the maximum number of points in the strip that need to be checked against a given point to guarantee finding a closer pair if it exists?
Closest-Pair and Convex-Hull Problem
Hard
A.7
B.8
C.6
D.5
Correct Answer: 7
Explanation:
Due to the geometric constraints of the problem, any point in the strip needs to be compared with at most 7 following points in the -sorted array. The points are distributed in two squares, each containing at most 4 points, one of which is the point currently being considered.
Incorrect! Try again.
44Which of the following is true regarding Graham's scan algorithm for finding the Convex Hull?
Closest-Pair and Convex-Hull Problem
Hard
A.Its worst-case time complexity is when all points lie on a circle.
B.It computes the upper and lower hulls separately in time after sorting by -coordinate.
C.It requires sorting points by their polar angle, giving a total time complexity of .
D.It uses a divide-and-conquer strategy, merging two convex polygons in time.
Correct Answer: It requires sorting points by their polar angle, giving a total time complexity of .
Explanation:
Graham's scan selects a base point and sorts the remaining points by the polar angle relative to the base point. The sorting step takes time, and the subsequent stack-based scan takes time, resulting in an overall complexity of .
Incorrect! Try again.
45When solving the Traveling Salesperson Problem (TSP) using exhaustive search on a complete graph with vertices, the number of distinct tours evaluated (ignoring starting vertex and direction) is:
Exhaustive Search
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
A complete graph has Hamiltonian circuits if we fix a starting vertex. Since the direction doesn't matter for the total weight in an undirected graph, we divide by 2, resulting in distinct tours.
Incorrect! Try again.
46What is the relationship between the Voronoi Diagram of a set of points and its Delaunay Triangulation?
Voronoi Diagrams
Hard
A.The Voronoi Diagram connects the centroids of the triangles in the Delaunay Triangulation.
B.The Delaunay Triangulation is the straight-line dual graph of the Voronoi Diagram.
C.The Voronoi Diagram is a subgraph of the Delaunay Triangulation.
D.They are geometrically identical but represented differently in data structures.
Correct Answer: The Delaunay Triangulation is the straight-line dual graph of the Voronoi Diagram.
Explanation:
The Delaunay Triangulation is the dual graph of the Voronoi Diagram. Two points in are connected by an edge in the Delaunay Triangulation if and only if their corresponding Voronoi cells share an edge.
Incorrect! Try again.
47In a Voronoi diagram for points in the plane (where and not all points are collinear), what is the maximum number of Voronoi vertices?
Voronoi Diagrams
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
According to Euler's formula applied to planar graphs, for non-collinear points, the maximum number of Voronoi vertices is and the maximum number of edges is .
Incorrect! Try again.
48Consider the Naive String-Matching algorithm searching for pattern of length in text of length . If consists of 'A's followed by a 'B', and consists entirely of 'A's, what is the exact number of character comparisons made?
Naiva String-Matching Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Since is all 'A's, for each of the shifts, the algorithm compares the first characters (all 'A's, which match) and then the -th character ('B', which mismatches). Thus, exactly comparisons are made at each shift, totaling comparisons.
Incorrect! Try again.
49In the Rabin-Karp algorithm, spurious hits occur when the hash value of the pattern matches the hash value of a text substring, but the strings are not identical. If a prime modulus is chosen randomly from a suitable range, what is the expected number of spurious hits for a text of length and pattern of length ?
Rabin-Karp Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Assuming the hash function distributes values uniformly modulo , the probability of a spurious hit at any single position is . Over positions (approximately ), the expected number of spurious hits is .
Incorrect! Try again.
50Which mathematical property allows the Rabin-Karp algorithm to compute the hash value of the next substring from the current substring in time?
Rabin-Karp Algorithm
Hard
A.The Chinese Remainder Theorem
B.Euclidean Algorithm
C.Fermat's Little Theorem
D.Modular arithmetic and Horner's rule
Correct Answer: Modular arithmetic and Horner's rule
Explanation:
Rabin-Karp treats substrings as numbers in a base- system. The rolling hash utilizes Horner's rule and modular arithmetic to update the hash value in constant time by subtracting the leading digit's value, shifting, and adding the new trailing digit's value.
Incorrect! Try again.
51For the pattern , what is the prefix function (or array) computed in the Knuth-Morris-Pratt algorithm?
Knuth-Morris-Pratt Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The prefix array tracks the length of the longest proper prefix that is also a proper suffix. For 'abacabab': 'a'=0, 'ab'=0, 'aba'=1, 'abac'=0, 'abaca'=1, 'abacab'=2, 'abacaba'=3, 'abacabab'=2 (prefix 'ab', suffix 'ab').
Incorrect! Try again.
52In the KMP algorithm, what is the maximum number of times the (prefix) function can backtrack (i.e., ) while processing a single character in the text?
Knuth-Morris-Pratt Algorithm
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
While processing a single character, the matching state can decrease at most times (the length of the pattern). However, the total number of decreases over the entire string of length is bounded by , leading to an amortized cost of per character, but the worst-case single step is .
Incorrect! Try again.
53When solving the subset-sum problem using exhaustive search on a set of elements, the state space tree has how many leaves?
Exhaustive Search
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The exhaustive search for the subset-sum problem considers all possible subsets. For a set of elements, there are exactly subsets, corresponding to the leaves in the binary state space tree where each level represents the inclusion or exclusion of an element.
Incorrect! Try again.
54Which algorithm computes the convex hull of points in time, where is the number of points on the convex hull, making it output-sensitive?
Closest-Pair and Convex-Hull Problem
Hard
A.Quickhull
B.Divide and Conquer
C.Jarvis's March (Gift Wrapping)
D.Graham's Scan
Correct Answer: Jarvis's March (Gift Wrapping)
Explanation:
Jarvis's March finds the convex hull by repeatedly finding the point with the smallest polar angle relative to the current point. It takes time per hull vertex found, leading to an overall time complexity of .
Incorrect! Try again.
55If a Brute-Force string matcher searches for a pattern of length in text of length , what is the average-case time complexity assuming the text and pattern are generated randomly over an alphabet of size ?
Sequential Search and Brute-Force String Matching
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
For random strings over an alphabet of size , the probability of matching the first character is , the first two is , etc. The expected number of comparisons per shift is bounded by a constant . Thus, the expected total time is .
Incorrect! Try again.
56To prevent arithmetic overflow when computing the rolling hash in the Rabin-Karp algorithm, modulo arithmetic is used. What is the consequence if the modulus is NOT chosen to be a prime number?
Rabin-Karp Algorithm
Hard
A.The time complexity for computing the hash increases to .
B.The algorithm will enter an infinite loop.
C.The probability of hash collisions may increase, leading to more spurious hits.
D.The rolling hash update formula will fail to compute the correct hash.
Correct Answer: The probability of hash collisions may increase, leading to more spurious hits.
Explanation:
Using a prime modulus helps ensure a more uniform distribution of hash values, minimizing collisions. A composite modulus can lead to patterns in hash values depending on the base , increasing collisions (spurious hits) and degrading performance toward .
Incorrect! Try again.
57In the KMP algorithm, the prefix array is used to determine the next shift. If , what does this indicate during the matching process?
Knuth-Morris-Pratt Algorithm
Hard
A.The algorithm has found the pattern in the text.
B.The pattern matches the text perfectly up to index .
C.There is no proper prefix of that is also a suffix, so the pattern must shift entirely past the current matched segment.
D.The character at index in the text must be skipped.
Correct Answer: There is no proper prefix of that is also a suffix, so the pattern must shift entirely past the current matched segment.
Explanation:
A value of means the longest proper prefix of the string up to which is also a suffix is of length 0. Therefore, no part of the previously matched pattern can be reused, and the search resumes by comparing the first character of the pattern with the current text character.
Incorrect! Try again.
58What is the computational complexity of constructing a Voronoi diagram of points using Fortune's sweep-line algorithm?
Voronoi Diagrams
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Fortune's algorithm constructs the Voronoi diagram using a sweep-line technique. Maintaining the beach line and processing site/circle events using a priority queue and a balanced binary search tree takes time.
Incorrect! Try again.
59Consider solving the Assignment Problem for an cost matrix using exhaustive search. What is the asymptotic time complexity of evaluating all possible assignments?
Exhaustive Search
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The Assignment Problem asks to assign jobs to agents. Every valid assignment is a permutation of items. Therefore, an exhaustive search must evaluate all possible permutations, making the complexity .
Incorrect! Try again.
60In the 2D Closest-Pair problem divide-and-conquer algorithm, let be the minimum distance found in the left and right halves. Why do we only need to consider points within a horizontal distance of from the dividing line ?
Closest-Pair and Convex-Hull Problem
Hard
A.Because calculating the distance for points further than causes floating-point overflow.
B.Because the Delaunay Triangulation ensures no closer points exist outside the strip.
C.Because points outside this vertical strip cannot form a convex hull.
D.Because any pair of points split across the dividing line with distance less than must have -coordinates differing by at most .
Correct Answer: Because any pair of points split across the dividing line with distance less than must have -coordinates differing by at most .
Explanation:
For two points and (one in the left half, one in the right half) to have a Euclidean distance less than , their horizontal distance (-coordinate difference) must also be strictly less than . Therefore, only points within of the median line can potentially form a closer pair.