U302 SAC Notes

Question 1

What is BFS?

Answer 1

A traversal algorithm that visits all neighbours of the current node at the same time (LEVEL BY LEVEL APPROACH)

Question 2

How does BFS work?

Answer 2

1) It starts from a starting vertex, enqueues it into a queue, and marks it as visited.

2) Then, it dequeues a vertex from the queue, visits it, and enqueues all its unvisited neighbors into the queue.

3) This process continues until the queue is empty.

Question 3

Advantages/Applications of BFS

Answer 3

Applications:
- shortest path
- Maze

Advantages:
- easy to implement
- level by level approach is more efficient
- guarantee that every node in the graph is visited, so sol is def found

Question 4

What is DFS and what ADT does it use?

Answer 4

Depth first search is a traversal algorithm that fully explores a single pathway, going all the way down, then backtracking to the other pathways until the entire graph has been traversed

Question 5

What is Prim’s algorithm used for?

Answer 5

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a WEIGHTED, UNDIRECTED, graph.

Question 6

What ADT does prims use?

Answer 6

Min priority queue, to determine which edge should be connected next (greedy approach- lowest cost edge)

Question 7

What is Dijikstra’s Algorithm

Answer 7

Algorithm that uses a greedy approach to find the shortest paths between one node andALL THE OTHER NODES in a WEIGHTED, DIRECTED graph that are NON-NEGATIVE.

Question 8

Why doesn’t Dijikstra’s work on negative weights?

Answer 8

Since Dijkstra follows a Greedy Approach, once a node is marked as visited it cannot be reconsidered even if there is another path with less cost or distance. This issue arises only if there exists a negative weight or edge in the graph.

Question 9

What is the concept of relaxation?

Answer 9

Updating the path distance values

Question 10

What is Bellman-Ford’s used for?

Answer 10

Single source shortest path problem for weighted, directed graphs, and can work with negative weights.

Question 11

What does WARSHALL’S algorithm find?

Answer 11

Warshall’s Algorithm finds the transitive closure of a graph (whether a path exists between two nodes.)

Question 12

What is Floyd-Warshall’s algorithm used for?

Answer 12

Finds the shortest path for all pairs of nodes in the graph.

The algorithm checks if a path through an intermediate vertex offers a shorter distance between two nodes.

Question 13

What is dynamic programming?

Answer 13

The algorithm is first broken down into sub-problems and then the sub-problems are optimised to find the overall solution

Question 14

What is backtracking

Answer 14

generating possible solutions to a problem and then going back and regenerating a part of the solution when it reaches a dead end

Question 15

What is a greedy algorithm?

Answer 15

One that picks the best/most optimal option or solution at each step/iteration

Question 16

Advantages of BFS

Answer 16

• Simple to implement
• Uses a level by level approach, so is more efficient
• Guarantees that all the nodes in the graph are visited so the solution is found

Question 17

Advantages of DFS

Answer 17

1) Memory efficient
2) time efficient

Question 18

Disadvantages of BFS

Answer 18

2) memory intensive
3) slower for large number of nodes compared to DFS

Question 19

Disadvantages of DFS

Answer 19

1) Not guaranteed to find solution, can potentially keep looping forever
2) may not find the SHORTEST path immediately