Scribd
Upload
8 views3 pages

Algorithm QA Set2

The document provides a Q&A format discussing key concepts in algorithms and data structures, including metrics for analyzing algorithms, sorting complexities, search methods, and definitions of important terms like hash functions and dynamic programming. It covers various algorithms, their efficiencies, and classifications such as P and NP problems. Additionally, it highlights specific algorithms suitable for different scenarios and defines concepts like Minimum Spanning Tree (MST).

Uploaded by

ashwinikrishnamurthyudupa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

Algorithm QA Set2

The document provides a Q&A format discussing key concepts in algorithms and data structures, including metrics for analyzing algorithms, sorting complexities, search methods, and definitions of important terms like hash functions and dynamic programming. It covers various algorithms, their efficiencies, and classifications such as P and NP problems. Additionally, it highlights specific algorithms suitable for different scenarios and defines concepts like Minimum Spanning Tree (MST).

Uploaded by

ashwinikrishnamurthyudupa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Algorithm & Data Structures - Q&A

1. What are the two important metrics to analyze an algorithm?

The two important metrics are:

- Time Complexity: Measures the amount of time an algorithm takes based on input size.

- Space Complexity: Measures the amount of memory used by the algorithm.

2. Sort in ascending order n, n*log(n), log(n), 1, n^3, n^2, n!, 2^n

Ascending order: 1 < log(n) < n < n*log(n) < n^2 < n^3 < 2^n < n!

3. In which scenario linear search performs better than binary search?

Linear search performs better:

- On small or unsorted datasets

- When the target element is near the beginning of the array

4. Pick the odd one out: Insertion Sort, Merge Sort, Quick Sort. Justify your answer.

Odd one out: Insertion Sort

Justification: It is an in-place, comparison-based algorithm suitable for small or nearly sorted datasets, while Merge Sort

and Quick Sort use divide-and-conquer strategy.

5. What is a mobile digit?

A mobile digit in algorithms like Johnson-Trotter is a digit that can move (i.e., swap) in its current direction and is greater

than the adjacent digit.

6. What are the time complexities of Matrix multiplication and Strassen's Matrix multiplication?

Standard Matrix Multiplication: O(n^3)


Algorithm & Data Structures - Q&A

Strassen's Matrix Multiplication: O(n^2.81)

7. Define Hash function. What is the need of Hashing?

A hash function maps keys to array indices. Hashing is used for fast data retrieval, insertion, and deletion in constant

time on average.

8. What is the major difference between Divide and Conquer and Decrease and Conquer?

Divide and Conquer divides the problem into multiple subproblems (e.g., Merge Sort).

Decrease and Conquer reduces the problem to a smaller version of itself (e.g., Insertion Sort).

9. While sorting 28,18,32,45,56, which is the best sorting algorithm? Justify.

For small datasets like this, Insertion Sort is best due to its simplicity and efficiency on nearly sorted or small-sized

inputs.

10. Define Dynamic Programming.

Dynamic Programming is a method for solving complex problems by breaking them down into simpler overlapping

subproblems and storing the results to avoid redundant work.

11. What are P and NP problems?

P problems: Can be solved in polynomial time.

NP problems: Solutions can be verified in polynomial time.

NP ' P, but it is unknown if P = NP.

12. Define MST.


Algorithm & Data Structures - Q&A

MST (Minimum Spanning Tree): A subset of edges in a connected, weighted graph that connects all vertices with the

minimum total edge weight and no cycles.

You might also like