Data Structure And Algorithm : Practice Questions and Answers

The for loop in the pre-processing step runs m times (length of the pattern). Hence the pre-processing time is Theta(m).

Rabin-Karp is a string matching algorithm proposed by Rabin and Karp. It generalizes to other algorithms and also applies to two-dimensional pattern matching problems.

Using Quick search algorithm, searching starts from the leftmost character and finds the first occurrence of the pattern "CAT" at index 6.

During the searching phase, comparisons can be done in any order. It has quadratic worst-case behaviour but good practical behaviour.

If the pattern occurs in the text, the worst case running time of Boyer-Moore's algorithm is O(mn).

Boyer-Moore's algorithm uses both good-character and bad-character shift tables, whereas Quick search uses only bad-character shift tables.

Quick search algorithm starts searching from the leftmost character to the right, and uses only bad-character shift tables.

The space complexity of the Quick search algorithm is O(n), where n represents the input size.

Quick search algorithm uses only bad-character shift tables, which is one of the reasons for its increased speed over Boyer-Moore's algorithm.

The time complexity of the Quick search algorithm is O(m+n), which is proven to be faster than Boyer-Moore's algorithm.

Quick search algorithm was developed to overcome the drawbacks of Boyer-Moore's algorithm, improving speed and efficiency.

Quick search algorithm is the fastest algorithm in the string matching field, whereas linear search searches for an element in an array sequentially.

Computational complexity theory seeks to classify problems according to their inherent difficulty based on the resources required to solve them.

Hamiltonian circuit, bin packing, and partition problems are NP-complete. The Halting problem is undecidable — it cannot be solved by any algorithm at all.

Two steps: first, show the problem is in NP; second, prove that every NP problem is polynomially reducible to it.

The CNF satisfiability problem belongs to the NP-complete class. It deals with Boolean expressions in conjunctive normal form.

Two conditions must be met: a function t that maps all yes-instances of decision problems D1 to D2, and t must be computable in polynomial time.

A non-deterministic algorithm is classified as NP if its verification stage runs in polynomial time.

A non-deterministic algorithm is a two-stage procedure: a guessing stage and a verification stage.

The Halting problem, proved by Alan Turing, cannot be solved by any algorithm and is therefore undecidable.