BE23CS407 - Design and Analysis of Algorithms (Unit-1)

What is the purpose of asymptotic notation in algorithm analysis?

• To measure the speed of computer hardware.

• To determine the exact runtime of an algorithm.

• To provide a graphical representation of algorithms.

• To describe the efficiency and growth rates of algorithms.

Define time complexity and space complexity.

• Time complexity is the measure of time an algorithm takes to run, while space complexity is the measure of memory an algorithm uses.

• Space complexity is the speed at which an algorithm executes.

• Time complexity refers to the amount of data an algorithm can process.

• Time complexity is the total number of lines in an algorithm.

What is the difference between best case, worst case, and average case analysis?

• Best case: average performance; Worst case: minimum performance; Average case: maximum performance.

• Best case: minimum performance; Worst case: maximum performance; Average case: expected performance.

• Best case: expected performance; Worst case: average performance; Average case: minimum performance.

• Best case: maximum performance; Worst case: expected performance; Average case: minimum performance.

Explain the substitution method for solving recurrence relations.

• The substitution method is a technique for solving recurrence relations by guessing a solution and proving it by induction.

• The substitution method requires solving the recurrence relation using matrix algebra.

• The substitution method is a graphical technique for visualizing recurrence relations.

• The substitution method involves using a calculator to solve equations directly.

What is the time complexity of linear search?

• O(n)

• O(log n)

• O(n^2)

• O(1)

How does binary search improve upon linear search?

• Binary search can be applied to unsorted data without any preprocessing.

• Binary search is faster than linear search because it reduces the search space exponentially.

• Binary search requires more comparisons than linear search.

• Linear search is more efficient for large datasets than binary search.

What is the average case time complexity of binary search?

• O(1)

• O(n)

• O(log n)

• O(n log n)

Describe the interpolation search algorithm and its use cases.

• Interpolation search is best used for uniformly distributed sorted arrays, particularly when the dataset is large and the values are evenly distributed.

• Interpolation search is primarily used for searching in linked lists.

• Interpolation search can be used for any type of data distribution.

• Interpolation search is effective for small, unsorted datasets.

What is the naive string matching algorithm?

• A complex algorithm that uses dynamic programming to find substrings.

• The naive string matching algorithm is a straightforward method for finding a substring in a string by checking each position for a match.

• An algorithm that sorts the string before searching for the substring.

• A method that only checks the first character of the string for matches.

How does the Rabin-Karp algorithm work?

• It employs a binary search method to locate patterns.

• The algorithm relies on sorting the text and patterns.

• The Rabin-Karp algorithm works by using hashing to efficiently search for patterns in a text.

• It uses brute force to find patterns in the text.