Analysis and Design of Algorithms

What is the main principle behind Greedy Algorithms?

• Prioritizing efficiency over correctness

• Choosing the best possible solution at each step

• Locally optimal choices lead to a globally optimal solution.

• Randomly selecting the next step

Explain the concept of memoization in Dynamic Programming.

• Memoization is only applicable to recursive algorithms

• Memoization involves discarding the results of function calls to save memory

• Memoization always leads to improved time complexity

• Memoization involves storing the results of expensive function calls and reusing them when the same inputs occur again, thus avoiding redundant calculations.

How does the Divide and Conquer algorithm work?

• By ignoring the problem and moving on to a different task

• By breaking down a problem into smaller subproblems, solving each subproblem recursively, and then combining the solutions of the subproblems to form the solution of the original problem.

• By solving the problem directly without breaking it down into smaller parts

• By randomly selecting a solution and iterating through all possible combinations

What are some common applications of Graph Algorithms?

• Sorting algorithms, Database management, Image processing

• Shortest path finding, Minimum spanning tree, Network flow optimization, Topological sorting, Detecting cycles

Compare the time complexity of Bubble Sort and Merge Sort.

• Merge Sort has a worse time complexity than Bubble Sort

• Bubble Sort and Merge Sort have the same time complexity

• Merge Sort has a better time complexity compared to Bubble Sort.

• Bubble Sort is more efficient than Merge Sort

What is the difference between Depth First Search (DFS) and Breadth First Search (BFS)?

• DFS explores as far as possible along each branch before backtracking, while BFS explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth.

• DFS and BFS are essentially the same algorithm with different names

• DFS explores nodes randomly, while BFS follows a specific order

• DFS always finds the shortest path, while BFS may not

In what scenario would you choose to use Greedy Algorithms over Dynamic Programming?

• When the problem has neither overlapping subproblems nor optimal substructure.

• When the problem has neither optimal substructure nor greedy choice property.

• When the problem has optimal substructure and greedy choice property.

• When the problem has overlapping subproblems but not optimal substructure.

How does the Quick Sort algorithm work?

• Quick Sort algorithm works by always selecting the smallest element as the pivot

• Quick Sort algorithm works by selecting a pivot element, partitioning the array based on the pivot, and recursively sorting the sub-arrays.

• Quick Sort algorithm works by sorting the array in reverse order

• Quick Sort algorithm works by randomly shuffling the array elements

Explain the concept of Topological Sorting in Graph Algorithms.

• Topological Sorting is used in tasks scheduling, build systems, and resolving dependencies.

• Topological Sorting is used in machine learning models.

• Topological Sorting is used in sorting algorithms only.

• Topological Sorting is used in image processing.

What is the main idea behind the Knapsack Problem in Dynamic Programming?

• To minimize the number of items in the knapsack

• To find the smallest combination of items within the knapsack's capacity

• To find the most valuable combination of items within the knapsack's capacity

• To maximize the weight of items in the knapsack