Algorithm-Paradigms
Question 1 |
Given below are some algorithms, and some algorithm design paradigms
A. Dijkstra’s Shortest Path 1. Divide and Conquer
B. Floyd-Warshall algorithm to 2. Dynamic Programming
compute all pairs shortest path
C. Binary search on a sorted array 3. Greedy design
D. Backtracking search on a graph 4. Depth-first search
5. Breadth-first search
Match the above algorithms on the left to the corresponding design paradigm they follow Codes:
1-i, 2-iii, 3-i, 4-v. | |
1-iii, 2-iii, 3-i, 4-v. | |
1-iii, 2-ii, 3-i, 4-iv. | |
1-iii, 2-ii, 3-i, 4-v. |
Question 1 Explanation:
(1) Dijkstra’s Shortest Path using to find single source shortest path. It is purely based on Greedy technique because it always selects shortest path among all.
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. It takes worst case time complexity is O(|V|3) and worst case space complexity is O(|V|2).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
(3) Binary search on a sorted array:
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
(4) Backtracking search on a graph uses Depth-first search
(2) → All Pair shortest path algorithm is using Dynamic Programming technique. It takes worst case time complexity is O(|V|3) and worst case space complexity is O(|V|2).
→ The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
→ A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
(3) Binary search on a sorted array:
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
(4) Backtracking search on a graph uses Depth-first search
Question 2 |
Match the following typical example problems with suitable algorithm-design paradigms
A: Minimal Spanning Tree
B: Binary Search Algorithm
C: Depth-First Search
D: Optimization
I: Divide and Conquer
II: Greedy Method
III: NLP
IV: Backtracking
A-II, B-I, C-IV, D-III
| |
A-III, B-II, C-IV, D-I
| |
A-III, B-I, C-IV, D-II
| |
A-IV, B-I, C-II, D-III |
Question 2 Explanation:
A. Minimal spanning tree is a greedy algorithm.
B. Binary Search algorithm is a divide and conquer strategy.
C. Depth first search algorithm is a backtracking method.
D. Optimization is a NLP method.
B. Binary Search algorithm is a divide and conquer strategy.
C. Depth first search algorithm is a backtracking method.
D. Optimization is a NLP method.
Question 3 |
Which of the following algorithms doesn’t require Priority queue for its implementation?
Kruskal’s algorithm | |
Prim’s algorithm | |
Huffman code generation algorithm
| |
Warshall’s algorithm |
Question 3 Explanation:
Kruskal’s ,prims , and huffman code generation algorithm require priority queue. But in floyd warshall we use matrix .
Question 4 |
Consider a large disk file containing records each of considerable size and an identification key. Which of the following methods is suitable to organize the file for faster access to a record given its key?
Apply Keysorting and maintain an index to the randomly ordered disk file | |
Sort the records of the disk file using Merge sort | |
Sort the records of the disk file using Quick sort | |
Apply keysorting and accordingly sort the records of the disk file |
Question 4 Explanation:
Using Primary key indexing all records can be accessed faster.Primary key indexing is based on a key attribute where all the elements of key attribute are arranged in sorted manner.
Question 5 |
Which type of algorithm design strategy is used in Quick-hull algorithm to find the smallest convex polygon that contains ‘n’ given points in a plane?
Greedy Approach | |
Divide and Conquer approach | |
Dynamic programming | |
Transform and Conquer approach |
Question 5 Explanation:
The QuickHull algorithm is a Divide and Conquer algorithm similar to QuickSort.
There are 5 questions to complete.