Write short notes on the following :
a) BFS
b) Tail recursion
Breadth-first search:
Breadth-first search is a way to find all the vertices reachable from the a given source vertex, s. Like depth first search, BFS traverse a connected component of a given graph and defines a spanning tree. Intuitively, the basic idea of the breath-first search is this: send a wave out from source s. The wave hits all vertices 1 edge from s. From there, the wave hits all vertices 2 edges from s. Etc. We use FIFO queue Q to maintain the wavefront: v is in Q if and only if wave has hit v but has not come out of v yet.
Algorithm: Breadth-First Search Traversal
BFS(V, E, s)
for each u in V − {s} ▷ for each vertex u in V[G] except s.
do color[u] ← WHITE
d[u] ← infinity
π[u] ← NIL
color[s] ← GRAY ▷ Source vertex discovered
d[s] ← 0 ▷ initialize
π[s] ← NIL ▷ initialize
Q ← {} ▷ Clear queue Q
ENQUEUE(Q, s)
while Q is non-empty
do u ← DEQUEUE(Q) ▷ That is, u = head[Q]
for each v adjacent to u ▷ for loop for every node along with edge.
do if color[v] ← WHITE ▷ if color is white you've never seen it before
then color[v] ← GRAY
d[v] ← d[u] + 1
π[v] ← u
ENQUEUE(Q, v)
DEQUEUE(Q)
color[u] ← BLACK
Analysis
The while-loop in breadth-first search is executed at most |V| times. The reason is that every vertex enqueued at most once. So, we have O(V).
> The for-loop inside the while-loop is executed at most |E| times if G is a directed graph or 2|E| times if G is undirected. The reason is that every vertex dequeued at most once and we examine (u, v) only when u is dequeued. Therefore, every edge examined at most once if directed, at most twice if undirected. So, we have O(E).
Therefore, the total running time for breadth-first search traversal is O(V + E).
Tail recursion
Definition: A special form of recursion where the last operation of a function is a recursive call. The recursion may be optimized away by executing the call in the current stack frame and returning its result rather than creating a new stack frame.
The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use.
// A tail recursive function to calculate factorial
unsigned factTR(unsigned int n, unsigned int a)
{
if (n == 0) return a;
return factTR(n-1, n*a);
}
// A wrapper over factTR
unsigned int fact(unsigned int n)
{
return factTR(n, 1);
}
The idea is to use one more argument and accumulate the factorial value in second argument. When n reaches 0, return the accumulated value.
What is an Abstract Data Type? What do you mean by a Dynamic Data Structure?
Write a C program to check a number is even or odd.
