Unit 2 - Previous Questions

Brute Force

General Concepts of Brute Force

1. Define the "Brute Force" approach to problem-solving.

2. What are the general advantages and limitations of the Brute Force method in algorithm design?

3. Write two key differences between the Brute Force and Divide-and-Conquer techniques.

4. When might a Brute Force approach be considered a practical or reasonable choice for solving a problem?

Example 1: Selection Sort

1. Describe the Selection Sort algorithm.

2. Write a clear algorithm or pseudocode for Selection Sort.

3. Analyze the time complexity of the Selection Sort algorithm.

4. Is Selection Sort a stable sorting algorithm? Explain.

5. Trace the execution of Selection Sort on various lists.

   • [81, 43, 66, 87, 21, 34, 15]
   • [89, 45, 68, 90, 29, 34, 17]
   • [234, 155, 409, 119, 789, 721, 345, 678]
   • [S, E, Q, U, E, N, T, I, A, L] (in alphabetical order)
   • [C, O, M, P, U, T, E, R] (in alphabetical order)
   • [45, 90, 20, 100, 75, 30]
   • [S, E, L, E, C, T, I, O, N, S, O, R, T] (in alphabetical order)

Example 2: Brute-Force String Matching

1. Explain the Brute-Force String Matching algorithm.

2. Write an algorithm or pseudocode for the Brute-Force String Matching technique.

3. Analyze its time complexity of the Brute-Force String Matching algorithm..

4. Trace the algorithm for various patterns and texts.

   • Pattern: "COMPUTER", Text: "MASTER OF COMPUTER APPLICATIONS"
   • Pattern: "EE", Text: "ENGINEERING COLLEGE" (also write the steps)
   • Pattern: "NOT", Text: "NOBODY_NOTICED_HIM" (also determine the number of character comparisons)
   • Pattern P. (e.g., T = ABABDABACDABABCABAB, P = ABABCABAB)

Example 3: Exhaustive Search

1. Define "Exhaustive Search" as an approach to problem solving and explain its relation to the Brute Force strategy.

2. Discuss the primary limitations of Exhaustive Search for complex combinatorial problems.

3. Demonstrate use of Exhaustive Search for the Traveling Salesperson Problem (TSP) with an example.

4. Solve the 0/1 Knapsack problem using Exhaustive Search. given a capacity W=10

Item	Weight	Value
1	7	$42
2	3	$12
3	4	$40
4	5	$25

Divide-and-Conquer

General Concepts of Divide-and-Conquer

1. Explain the "Divide-and-Conquer" paradigm and its three fundamental steps.

2. What characteristics make a problem well-suited for a Divide-and-Conquer approach?

3. Write the general form of a recurrence relation for a Divide-and-Conquer algorithm and explain the role of the Master Theorem.

4. Briefly explain and analyze the algorithm for multiplying two large integers based on Divide and Conquer strategy. Analyze its time efficiency using backward substitution (or recurrence relation).

Example 1: Merge Sort

1. Describe the Merge Sort algorithm. Clearly explain the divide, conquer and combine steps.

2. Write an algorithm or pseudocode for Merge Sort.

3. Analyze time complexity of Merge sort.

4. Is Merge Sort an in-place sorting algorithm? Is it a stable sorting algorithm? Explain.

5. Trace the Merge Sort algorithm on the following lists of numbers:

   • [8, 3, 2, 9, 7, 1, 5, 4]
   • [67, 23, 45, 89, 59, 34, 70, 55]
   • [10, 40, 60, 90, 20, 45] (show steps in detail and evaluate using a recursive tree)

Example 2: Quick Sort

1. Describe the Quick Sort algorithm, focusing on partitioning steps.

2. Write an algorithm or pseudocode for Quick Sort.

3. Analyze the time complexity of Quick Sort for its best-case, worst-case, and average-case scenarios (especially when the input is a set of random numbers for the average case).

4. Explain conditions leading to the worst-case and how to mitigate them. (e.g., randomized pivot selection, median-of-three pivot).

5. Is Quick Sort an in-place sorting algorithm? Is it a stable sorting algorithm? Explain.

6. Trace the Quick Sort algorithm on the following lists of numbers/characters:

   • [5, 3, 1, 9, 8, 2, 4, 7]
   • {Q, U, I, C, K, S, O, R, T}
   • [55, 26, 93, 17, 77, 31, 44, 55, 20]

Example 3: Binary Search

1. Explain the recursive Binary Search algorithm.

2. Write the algorithm or pseudocode for Binary Search.

3. Prove that the worst-case time complexity of the Binary Search algorithm is O(log₂n) by deriving its recurrence relation.

4. Illustrate Binary Search with a suitable example.

Principles of Parallel Algorithm Design

Part A: The Core Concept - Decomposition

1. Explain the main types of decomposition: task decomposition and data decomposition. What is the primary focus of each?

2. Describe specific decomposition techniques in detail, with examples for each:

   • Data Decomposition (including input/output partitioning)

   • Recursive Decomposition

   • Exploratory Decomposition

   • Speculative Decomposition

Part B: Modeling the Parallel Structure

1. Explain "Tasks" and "Dependency Graphs" (also known as Task Interaction Graphs) in parallel algorithm design. with examples.

2. What is the "Critical Path Length" in a dependency graph and why is it important?

Part C: Characterizing Parallelism

1. Define and explain "Granularity" in the context of task size.

2. Define and explain the "Degree of Concurrency" and its relation to the dependency graph.