AOS 2

Question 1

What ADTs does BFS and DFS use?

Answer 1

BFS (Breadth-First Search):

BFS uses a Queue ADT to store the vertices to be visited.
The queue follows the First-In-First-Out (FIFO) principle, meaning that the vertices are visited in the order they are added to the queue.
In BFS, the vertices at the current level are visited first before moving on to the next level.
The queue ensures that the vertices are explored in breadth-first order, visiting all the neighbors of a vertex before moving to the next level.

DFS (Depth-First Search):

DFS uses a Stack ADT to store the vertices to be visited.
The stack follows the Last-In-First-Out (LIFO) principle, meaning that the most recently added vertex is visited first.
In DFS, the algorithm explores as far as possible along each branch before backtracking.
The stack allows the algorithm to go deeper into the graph before exploring the neighboring vertices.

Question 2

Define Prims algorithm, what it does and how it is used

Answer 2

Prim’s Algorithm finds the minimum spanning tree of a weighted and undirected graph.

Prim’s algorithm is considered a greedy algorithm. That means that it will always take the best option that is immediately available, even if there is a better option that appears later on.

Choose a starting node (it doesn’t matter which one you go with).

Look at the edges coming out of that node and choose the one with the lowest weight (if there are multiple with the same weight, it doesn’t matter which one you pick). These nodes and the edge that connects them will form the start of the MST.

Now look at all the edges coming of from the nodes currently in your tree and select once again the edge with the smallest weight. But do not pick an edge that would connect the graph to itself.

Repeat this process until all the nodes are connected.

Question 3

What are the pros and cons of Dijkstra and Bellman Fjord

Answer 3

Both give you the same result, shortest path from one node to all other nodes, the only difference is that Bellman Fjord works on graphs with negative edge weights, but both fail on negative cycles.

Bellman Fjord is not a greedy algorithm.

Question 4

How does the Dijkstra algorithm work?

Answer 4

It’s the one where you pick a node, store a list of every node that you have currently seen, and then keep on picking the lowest edge while filling out your node list for what you have seen. Stop once you have visited all nodes.

Question 5

Name the 4 big algorithms and what they do

Answer 5

1. Dijkstra’s Algorithm:
   
   • Used for finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
   • Commonly used in network routing protocols and GPS navigation systems.
2. Floyd-Warshall Algorithm:
   
   • Used for finding the shortest paths between all pairs of vertices in a weighted graph.
   • Useful in problems involving transitive closure and finding the diameter of a graph.
3. Bellman-Ford Algorithm:
   
   • Used for finding the shortest path from a single source vertex to all other vertices in a weighted graph, even with negative edge weights.
   • Can detect negative-weight cycles in the graph.
4. PageRank Algorithm:
   
   • Used by search engines to rank web pages based on their importance and relevance.
   • Assigns a numerical score to each web page based on the number and quality of incoming links, considering the idea that more important pages are likely to receive more links from other important pages.

Question 6

How does the Bellman Fjord algorithm work?

Answer 6

Works on weighted directed graphs

This is the v-1 times, where you fill in a table with all the nodes, move from left to right filling it in as you go across, keep going until it stops

Question 7

What does Floyd Warshall do?

Answer 7

Keeps 3 values,
k, i, j

create a matrix with the amount of rows and columns for the amount of edges, initialize each nodes path to itself for 0, and then loop through the edges and fill the table in

if dist[i, j] > dist[i][k] + dist[k][j]

and increment
for k from 1 to V
for i from 1 to V
for j from 1 to V

k is the intermediate vertex, i is the source vertex, j is the destination vertex

Question 8

How does Floyd Warshall work for transitive closure and all pair shortest paths?

Answer 8

For all pair shortest paths it takes in a directed weighted graph, and outputs a matrix containing the distances between every node

For transitive closure, the input is just a directed graph, and then the matrix will have 0s and 1s, 0s if there is no route, and 1s if there is a route