4 Questions of 5 Marks
1) Write steps of sieve techniques
2) Write Pseudo code of Dijkstra's algorithm
3) Prove the Lemma:
Consider a diagraph G = ( V,E ) and any DFS forest for G. G has a cycle if and only if the DFS forest has a back edges
4) Answer the following
Where the cliquer cover problem is used?
What is decision problem, also explain with examples?
4 Questions of 3 Marks
1) Let the adjacency list representation of an undirected graph is given.
Explain what property of the list indicates that the graph has an isolated vertex
| | a | b | c | d | e | f |
| a | 1 | 0 | 1 | 1 | 0 | 0 |
| b | 0 | 1 | 1 | 0 | 1 | 0 |
| c | 1 | 0 | 0 | 0 | 0 | 1 |
| d | 0 | 1 | 1 | 1 | 0 | 1 |
| e | 1 | 1 | 0 | 1 | 1 | 1 |
| f | 1 | 0 | 1 | 0 | 1 | 0 |
| g | 0 | 0 | 0 | 0 | 0 | 0 |
2) Analyze the brute force maxima algorithm
3) How Kruskal's algorithm works ?
4) Which points should be supposed to prove the correctness of the Dijkstra's Algorithm?
4 Questions of 2 Marks
1) Given a matrix of graph G
| | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 0 | 3 |
| 1 | 2 | 0 | 4 | 0 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 2 | 0 | 0 | 0 |
Is G directed or undirected graph?
2) Give a detailed example of 2 d maxima
3) What is the common problem in communication network and circuit designing?
4) (4th question i forgot)
No comments:
Post a Comment