Question

1. What is the role of “levels” within a breadth-first search?

2. Other than flight routes, what is an example of directed graphs in the real world?

3. Other than driving routes, what is an example of shortest paths in the real world?

4. What is the difference between shortest path and minimum spanning trees?

5. What role does “NP” play when developing efficient algorithms?

Answer 1

Ans.1 The levels in BFS basically signify the level of each node in the given tree from source node. In BFS the traversal is always level wise. That is from a node it's neighbours then neighbours of neighbours and so on.

Ans .2 Taking courses/subjects in colleges. Some courses have other courses as pre-requisites.

Ans.3 Shortest path is used in Routing Protocols to determine shortest path for hopping between routes for sending protocol messages.

Ans.4 Shortest path is simply the shortest path between 2 points. For example in a triangle shortest path between 2 vertices will be one edge.

However MST includes all vertices exactly once and gives edges which added up to minimum weight.

For example in a triangle of sides lengths 3,4,5 ..The sides with weights 3 and 4 will form the MST.

Ans.5

In 1965, Jack Edmonds gave the a formal definition of "efficient computation" that is problems that runs in time a fixed polynomial of the input size. These class of problems with efficient solutions are to be known as P . Here P stands for "Polynomial Time."
Now another set of problems with solutions are there. If given a potential solution, some solution can be validated efficiently. These problems collection which have a efficiently verifiable solutions is known as NP.

Now comes P = NP. This means that we can find that solution efficiently as well (for every problem that has an efficiently verifiable solution. ) Which was an early theory. However now the debate is whether P ≠ NP. This is the single most highly regarded as important question in the domain of theoretical computer science and it's interjection with mathematics. And P vs NP is a computational issue for efficiency.