Greedy and Dynamic Algorithms

Question 1

Explain the concept of the greedy approach

Answer 1

At each step, the algorithm chooses the best available option without considering the overall future consequences.

Question 2

What are some examples of greedy alogoithms?

Answer 2

Greedy Search Algorithm, Prim’s Algorithm,
Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees.

Question 3

What is the Big O of Dijkstra’s algorithm?

Answer 3

O(ElogV)

Question 4

What is the time complexity of Prim’s algo?

Answer 4

O(E log V)

Question 5

What is the time complexity of Kruskal’s algo?

Answer 5

O(E log E)

Question 6

Which is faster, Prim or Kruskals.

Answer 6

Prim’s algorithm runs faster in dense graphs. Kruskal’s algorithm runs faster in sparse graphs.

Question 7

T/F Prim’s can work using non connected graphs.

Answer 7

False

Question 8

What is the worst case performance of Dijkstra’s using a matrix representation?

Answer 8

O(v^2)

Question 9

Explain Prim’s Algorithm

Answer 9

finding the MST for a graph by randomly selecting any node then the node with the shortest distance from the current node or set of nodes visited so far until all nodes have been connected

Question 10

Explain Kruskal’s Algorithm

Answer 10

finding the MST for a graph by selecting the smallest edge then the next smallest edge and so on until all nodes have been connected

Question 11

Explain the Floyd Warshall’s Algorithm

Answer 11

finding the shortest path between each node and all other nodes in a given graph, by selecting each node and seeing if a shorter path can be found from each source to each destination by going through the currently selected node

Question 12

Explain Dijkstra’s Algorithm

Answer 12

finding the shortest path between a specific starting node and a specific destination node. It picks the unvisited node with the smallest distance, calculates the path through it from the start node, and updates the neighbours distances if smaller.