DAA Quiz 3/GLBITM

What is the purpose of the Convex Hull algorithm?

• To calculate the area of a polygon.

• To sort a list of points in ascending order.

• To find the nearest neighbor of a point.

• To find the smallest convex boundary enclosing a set of points.

Explain the Greedy Method in the context of the Knapsack problem.

• The Greedy Method selects items randomly without considering their value or weight.

• The Greedy Method requires sorting items by weight before selection.

• The Greedy Method only considers the total weight of items without regard to their value.

• The Greedy Method selects items based on the highest value-to-weight ratio until the knapsack is full.

List the steps involved in Prim's Algorithm for finding a Minimum Spanning Tree.

• Add all edges to the MST at once.

• Start with all vertices included.

• Select the largest edge connecting MST to non-MST.

• 1. Start with an arbitrary vertex. 2. Find the smallest edge connecting MST to non-MST. 3. Add the edge and vertex to MST. 4. Repeat until all vertices are included.

Describe the process of Kruskal's Algorithm.

• Kruskal's Algorithm sorts vertices and connects them directly.

• Kruskal's Algorithm uses a depth-first search to find cycles.

• Kruskal's Algorithm finds the maximum spanning tree by adding all edges.

• Kruskal's Algorithm finds the minimum spanning tree by sorting edges and adding them without forming cycles.

What are some common applications of Dijkstra's Algorithm?

• Weather forecasting models

• Image processing algorithms

• Data compression techniques

• Common applications include network routing protocols (like OSPF), GPS navigation systems, and project planning (like PERT charts).

How does the Bellman-Ford Algorithm differ from Dijkstra's Algorithm?

• Bellman-Ford is faster than Dijkstra's for all graphs.

• Dijkstra's can handle negative weights while Bellman-Ford cannot.

• Both algorithms require the same data structure for implementation.

• Bellman-Ford handles negative weights; Dijkstra's does not.

Define a Minimum Spanning Tree and its significance in graph theory.

• A Minimum Spanning Tree is a subset of edges connecting all vertices in a graph with the minimum total edge weight.

• A Minimum Spanning Tree is a tree that includes all edges of a graph.

• A Minimum Spanning Tree is a cycle that connects all vertices in a graph.

• A Minimum Spanning Tree is a subset of edges that connects only some vertices in a graph.

What is meant by a single source shortest path in graph algorithms?

• The shortest paths from a single vertex to only one other vertex in a graph.

• The shortest paths from a single source vertex to all other vertices in a graph.

• The paths from all vertices to a single source vertex in a graph.

• The longest paths from multiple sources to a single vertex in a graph.

Explain the Dynamic Programming approach in solving the 0/1 Knapsack problem.

• The total weight of all items in the knapsack.

• The minimum value that can be obtained with the knapsack's capacity.

• The average value of items that can fit in the knapsack.

• The maximum value that can be obtained without exceeding the knapsack's capacity.

What is the time complexity of Prim's Algorithm using an adjacency matrix?

• O(V)

• O(E log V)

• O(V^2)

• O(V log V)