Unit2 - Subjective Questions

Brute-Force String Matching Algorithm
The Brute-Force (or Naive) string matching algorithm searches for a pattern of length in a text of length by checking all possible shifts.

Algorithm Steps:

1. Align the pattern with the beginning of the text .
2. Compare the characters of with the corresponding characters of from left to right.
3. If a mismatch occurs, shift the pattern one position to the right and repeat the comparison.
4. If all characters match, record the shift index. Continue until the pattern shifts beyond the text.

Time Complexity:

• Best Case: . This occurs when the first character of the pattern doesn't match any character in the text (e.g., Text = "AAAAA", Pattern = "B"). Only one comparison is made per shift.
• Worst Case: or exactly . This occurs when all characters match except the last one (e.g., Text = "AAAAAAAAA", Pattern = "AAAB").

Closest-Pair Problem
The Closest-Pair problem involves finding the two closest points in a set of points in a -dimensional space (usually 2D, where ). The distance is typically measured using the Euclidean distance formula:

Exhaustive Search Approach:

1. Method: The brute-force or exhaustive search method considers every possible pair of points in the set.
2. Calculation: For points, the number of unique pairs is . The algorithm calculates the Euclidean distance for all these pairs.
3. Tracking: It keeps a record of the minimum distance found so far and the pair of points that yielded this distance.
4. Complexity: Since it evaluates pairs, the time complexity of the exhaustive search approach is . This is inefficient for large datasets, which motivates divide-and-conquer approaches.

Convex-Hull Problem
The convex hull of a set of points is the smallest convex polygon that contains all points of . A polygon is convex if a line segment connecting any two points inside the polygon lies entirely entirely within it.

Brute-Force Algorithm:

1. Concept: A line segment connecting two points and is a part of the convex hull boundary if and only if all other points in lie on the same side of the straight line passing through and .
2. Line Equation: The line through and is given by . A point is evaluated in this equation. If the result is consistently positive or consistently negative for all other points, the segment is part of the hull.
3. Process: Test every possible pair of points ( pairs). For each pair, check the remaining points to see if they fall on the same side.
4. Complexity: Testing pairs against points results in an overall time complexity of , making it highly inefficient compared to Graham Scan or Jarvis March.

Exhaustive Search
Exhaustive search (or generate-and-test) is a problem-solving strategy that systematically evaluates all possible solutions from the solution space to find the optimal one or to find all solutions that satisfy a particular property.

Advantages:

• Simplicity: It is easy to understand, design, and implement.
• Guaranteed Accuracy: If a solution exists, exhaustive search is guaranteed to find it. It finds the absolute optimal solution without getting stuck in local optima.
• Broad Applicability: It can be applied to almost any problem where the search space is finite.

Disadvantages:

• Inefficiency: The time complexity is usually exponential (e.g., or ), making it impractical for large input sizes.
• Scalability: It scales very poorly. As the problem size increases even slightly, the computation time can grow astronomically.
• Resource Intensive: It consumes massive computational power and time for combinatorial problems like the Traveling Salesperson Problem (TSP).

Voronoi Diagrams
A Voronoi diagram is a partition of a plane into regions based on the distance to a specific set of points called sites or generators. For each site, there is a corresponding region consisting of all points in the plane closer to that site than to any other.

Key Properties:

• Convex Regions: Every Voronoi region (cell) is a convex polygon (or unbounded convex shape).
• Edges: The edges of a Voronoi diagram are segments of the perpendicular bisectors of the line segments connecting neighboring sites.
• Vertices: A Voronoi vertex is typically the intersection of three edges and is the center of a circle passing through three sites (with no other sites inside the circle).
• Delaunay Triangulation Dual: The Voronoi diagram is the mathematical dual of the Delaunay triangulation of the same point set.

Applications:

• Nearest Neighbor Search: Quickly finding the closest site to a query point.
• Facility Location: Determining the optimal placement of resources (like hospitals or cell towers) to serve a population efficiently.
• Computer Graphics: Used in procedural texture generation and natural pattern simulations.

Naive String-Matching Algorithm
The naive algorithm checks for the presence of a pattern in a text by simply shifting the pattern one position at a time and comparing characters.

Algorithm:
text
for s = 0 to n - m
match = true
for j = 1 to m
if T[s + j] != P[j]
match = false
break
if match == true
print "Pattern occurs with shift" s

Reason for Inefficiency:
The naive algorithm is inefficient because it entirely ignores information gained during a partial match.

• No Memory: If a mismatch occurs after several matching characters, the algorithm discards all the matching information and simply shifts the pattern by exactly one position.
• Worst-Case Scenario: If the text is composed of highly repetitive characters (e.g., ) and the pattern is similar (e.g., ), the algorithm performs comparisons for almost every shift, leading to a worst-case time complexity of .

Rabin-Karp Algorithm Core Concept:
The Rabin-Karp algorithm uses hashing to find an exact match of a pattern string in a text string . Instead of comparing the pattern to the text character by character for every shift, it compares the hash value of the pattern with the hash value of the current substring in the text.

How Hashing Improves the Process:

1. Hash Calculation: The algorithm computes a hash value for the pattern of length and for the first substring of text of length .
2. Fast Comparisons: Comparing two hash values (integers) takes time. If the hash values don't match, the pattern definitely doesn't match the current substring.
3. Rolling Hash: When shifting the pattern by one position, Rabin-Karp calculates the hash of the new substring in time using a rolling hash technique. It subtracts the value of the old first character, multiplies by the base, and adds the new last character.
4. Handling Collisions (Spurious Hits): Two different strings can have the same hash value. If the hash values match, a character-by-character check is performed to verify the match.
5. Efficiency: While the worst-case time complexity is (if there are many hash collisions), the average-case time complexity is , making it very efficient in practice.

Spurious Hit in Rabin-Karp:
A spurious hit occurs when the hash value of the pattern equals the hash value of a substring in the text , but the actual characters of the pattern and the substring do not match.

Why it happens:
The hashing function used in Rabin-Karp typically uses modulo arithmetic (modulo a prime number ) to prevent the integer values from overflowing. Because the set of possible strings is infinitely larger than the set of hash values (bounded by ), multiple distinct strings will inevitably map to the same hash value (a hash collision).

How it is resolved:
To resolve spurious hits, the Rabin-Karp algorithm must perform an explicit character-by-character comparison whenever a hash match occurs.

1. If , the algorithm loops through the characters of and .
2. If all characters match, a valid shift is reported.
3. If a mismatch is found, it is identified as a spurious hit, the hit is ignored, and the algorithm proceeds to calculate the hash for the next text window.

Prefix Function ( array) in KMP:
The Knuth-Morris-Pratt (KMP) algorithm achieves linear time complexity by utilizing the prefix function (also known as the Failure Function or LPS - Longest Proper Prefix which is also Suffix array).

Significance:

1. Avoiding Redundant Comparisons: In the naive algorithm, a mismatch causes the pattern to shift by 1, re-evaluating previously matched characters. The KMP prefix function stores information about the pattern itself to dictate how far the pattern can safely shift without missing a potential match.
2. Definition of LPS: contains the length of the longest proper prefix of that is also a proper suffix of .
3. Smart Shifting: When a mismatch occurs at after matching characters, the algorithm consults . It knows that the first characters of the pattern match the text just before the mismatch point. Thus, it shifts the pattern such that the prefix aligns with the suffix, avoiding backtracking on the text string.
4. Efficiency: Constructing the prefix table takes time, and using it ensures the text pointer never moves backward, resulting in matching time. Overall time complexity becomes .

Prefix Function (LPS) derivation for :
Let be the length of (). The array stores the length of the longest proper prefix that is also a suffix.

• : . (Base case).
• : . No proper prefix matches a suffix. .
• : . Prefix "A" matches suffix "A". .
• : . Prefix "AB" matches suffix "AB". .
• : . Suffix ends in 'C', no prefix matches. .
• : . Prefix "A" matches suffix "A". .
• : . Prefix "AB" matches suffix "AB". .
• : . Prefix "ABA" matches suffix "ABA". .
• : . Prefix "ABAB" matches suffix "ABAB". .

Final LPS array: [0, 0, 1, 2, 0, 1, 2, 3, 4]

Comparison: Naive vs KMP String Matching

Sequential Search vs. Brute-Force String Matching

Sequential Search (Linear Search):

• Goal: To find a single element (e.g., a number or a specific character) within a linear data structure like an array or list.
• Operation: It iterates through the structure one element at a time from start to finish, checking if the current element matches the target.
• Complexity: where is the number of elements in the list.

Brute-Force String Matching:

• Goal: To find a sequence of characters (a pattern of length ) within another sequence of characters (a text of length ).
• Operation: It checks for the pattern starting at every possible position in the text. This involves an outer loop traversing the text, and an inner loop traversing the pattern.
• Complexity: Worst-case is .

Conclusion: Sequential search is a 1D lookup for a single item, whereas brute-force string matching is effectively a 2D lookup checking for a sequence within a sequence, thus having a multiplicative time complexity factor based on the pattern length.

Time Complexity Analysis of KMP Algorithm:

The KMP algorithm consists of two distinct phases: Preprocessing and Matching.

1. Preprocessing Phase (Building LPS Array):

• This phase analyzes the pattern of length to construct the prefix array .
• It involves a loop that iterates over the pattern. The algorithm maintains two pointers. Although there is an inner while loop that decrements a variable, the variable is bounded by the current index and only increments at most times overall.
• Therefore, the amortized cost of the inner loop across all iterations is linear.
• Complexity: .

2. Matching Phase:

• This phase scans the text of length .
• A text pointer moves from $0$ to and never backtracks.
• A pattern pointer keeps track of the number of matched characters. If a mismatch occurs, is updated using the array (). Since can only decrease as many times as it has increased, and it increases at most times, the inner mismatch loop runs in amortized time per character.
• Complexity: .

Overall Time Complexity:
The total time is the sum of both phases: . Since typically, it is linear with respect to the text length, .

Role of Modulo Arithmetic and Prime Number in Rabin-Karp:

1. Preventing Integer Overflow: The Rabin-Karp algorithm calculates the numerical value of a string (rolling hash) treating it as a number in a specific base (often for ASCII). For a pattern of length , this value can be exceptionally large (), which will quickly exceed standard integer limits in programming languages. Modulo arithmetic (mod ) keeps the hash values bounded within standard integer sizes.
2. Why a Prime Number?
   • Minimizing Collisions: The fundamental goal of the hash function is to distribute string values uniformly across the available buckets . Using a prime number minimizes the chance of hash collisions (spurious hits) because primes do not share common factors with the base (unless is a multiple of , which is avoided). If were a composite number sharing factors with , the hash values would clump together, increasing collisions.
   • Maximizing Table Size: Usually, a prime number is chosen such that fits precisely within a standard computer word (like a 32-bit or 64-bit integer). This maximizes the hash space while preventing overflow during the rolling hash calculation.

Closest-Pair: Divide and Conquer vs Exhaustive Search

• Exhaustive Search: Calculates the distance between all pairs time.
• Divide-and-Conquer Approach:
  1. Sort: First, sort the points based on their x-coordinates, taking .
  2. Divide: Recursively divide the set of points into two halves by a vertical line .
  3. Conquer: Recursively find the closest pair in the left half (let distance be ) and the right half (). Let .
  4. Combine: The closest pair could also have one point in the left half and one in the right half. We only need to check points located within a strip of width centered at the dividing line .
  5. Efficiency in Combine: By sorting points in the strip by y-coordinate, it can be proven geometrically that we only need to compare each point in the strip to at most 7 subsequent points. Thus, the combine step takes time.
• Complexity Improvement: The recurrence relation is , which resolves to . This is a massive improvement over the exhaustive search for large datasets.

Definitions:

• Convex Set: A set of points in a plane is convex if, for any two points and within the set, the entire line segment connecting and also lies entirely within the set.
• Convex Hull: For a given set of points , the convex hull is the smallest convex set that contains all points in . It can be visualized as the shape formed by snapping a rubber band around the outermost points of the set.

Real-World Applications:

1. Collision Detection: In robotics and video games, computing the convex hull of objects simplifies the objects into bounding boxes/shapes. Checking for collisions between convex hulls is much faster than checking complex, concave geometric boundaries.
2. Pattern Recognition & Image Processing: Used for shape analysis, determining the boundary of digit outlines, or grouping features together.
3. Geographic Information Systems (GIS): Used to determine the geographic spread or boundary of a specific feature, like an epidemic outbreak or the territorial span of an animal species.

Relationship between Voronoi Diagrams and Delaunay Triangulation:

Voronoi diagrams and Delaunay triangulations are mathematical duals of each other. They represent the same proximity information about a set of points but in different graphical formats.

1. Dual Graph: If you draw a line segment connecting two generator points (sites) if and only if their corresponding Voronoi regions share an edge, the resulting graph is the Delaunay Triangulation.
2. Vertices and Faces:
   • The vertices of the Delaunay triangulation are the generator points (sites) of the Voronoi diagram.
   • The centers of the circumcircles of the Delaunay triangles correspond exactly to the vertices of the Voronoi diagram.
3. Empty Circle Property: In a Delaunay triangulation, no point from the set lies inside the circumcircle of any triangle. The center of this empty circumcircle is a Voronoi vertex, which is equidistant from the three points forming the triangle.

Rolling Hash Formula in Rabin-Karp:

To compute the hash of the next text window from the current window , the algorithm uses the following constant-time operation:

Explanation of Variables:

• : The hash value of the new text window of length .
• : The hash value of the previous text window of length .
• : The size of the alphabet (e.g., 256 for extended ASCII). Acts as the numerical base.
• : The value of the character dropping out of the window from the left.
• : A precomputed multiplier . It represents the positional weight of the most significant character dropping out.
• : The value of the new character entering the window from the right.
• : A prime number used for modulo arithmetic to prevent integer overflow.

Trace of Naive Algorithm:
(Length )
(Length )

• Shift : Compare ("AABA") with . Match found! Print shift 0.
• Shift : Compare ("ABAA") with ("AABA"). Mismatch at index 1 ('B' != 'A').
• Shift : Compare ("BAAC") with ("AABA"). Mismatch at index 0 ('B' != 'A').
• Shift : Compare ("AACA") with ("AABA"). Mismatch at index 2 ('C' != 'B').
• Shift : Compare ("ACAA") with ("AABA"). Mismatch at index 1 ('C' != 'A').
• Shift : Compare ("CAAD") with . Mismatch at index 0.
• Shift : Compare ("AADA") with . Mismatch at index 2 ('D' != 'B').
• Shift : Compare ("ADAA") with . Mismatch at index 1 ('D' != 'A').
• Shift : Compare ("DAAB") with . Mismatch at index 0.
• Shift : Compare ("AABA") with . Match found! Print shift 9.
• Shift : Compare ("ABAA") with . Mismatch at index 1.
• Shift : Compare ("BAAB") with . Mismatch at index 0.
• Shift : Compare ("AABA") with . Match found! Print shift 12.

Output: Pattern occurs with shifts 0, 9, 12.

Practical Applications of String-Matching Algorithms:

1. Text Editors and Word Processors: The "Find" and "Replace" functionalities heavily rely on efficient string-matching algorithms like KMP or Boyer-Moore to locate words or phrases in large documents.
2. Search Engines: Web crawlers and search engines use string matching to find keywords within massive databases of HTML pages to retrieve relevant search results.
3. Bioinformatics and DNA Sequencing: DNA can be represented as a long string of characters (A, C, G, T). String matching is used to locate specific gene sequences, find mutations, and assemble DNA fragments.
4. Network Intrusion Detection Systems (NIDS): Firewalls and security software inspect incoming network packets against a database of known malicious virus signatures or attack patterns (acting as strings) using algorithms like Rabin-Karp or Aho-Corasick.
5. Plagiarism Detection: Software that checks for academic dishonesty uses string matching to find significant overlaps between a submitted document and existing texts on the internet or in databases.