Explain Decidable and Undecidable Problems. Give example for each.
See Answer →If L1 and L2 are context free languages then, prove that L1 U L2 is a context free language.
See Answer →Write the finite automata corresponding to the regular expression (a + b)*ab
See Answer →Explain whether function: f(x) = x² posses an inverse function or not.
See Answer →Write the following statements in the symbolic form.
i) Some students can not appear in exam.
ii) Everyone can not sing.
See Answer →Verify whether √11 is rational or irrational.
See Answer →Prove by mathematical induction that
Subset Sum Problem
See Answer →Hamiltonian Cycle Problem
See Answer →Clique problem
See Answer →SAT Problem
See Answer →Define the NP-Hard and NP-Complete problem. How are they different from each other. Explain the use of polynomial time reduction with the help of an example
See Answer →What are P and NP class of Problems? Explain each class with the help of at least two examples.
See Answer →Explain the term Decision problem with the help of an example. Define the following problems and identify if they are decision problem or optimisation problem? Give reasons in support of your answer.
(i) Travelling Salesman Problem
(ii) Graph Colouring Problem
(iii) 0-1 Knapsack Problem
See Answer →Explain the Rabin Karp algorithm for string matching with the help of an example. Find the time complexity of this algorithm.
See Answer →Given the following sequence of chain multiplication of the matrices. Find the optimal way of multiplying these matrices:
| Matrix | Dimension |
| A1 | 10 × 15 |
| A2 | 15 × 5 |
| A3 | 5 × 20 |
| A4 | 20 × 10 |
Explain the algorithm to find the optimal Binary Search Tree. Demonstrate this algorithm to find the Optimal Binary Search Tree for the following probability data (where pi represents the probability that the search will be for the key node ki, whereas qi represents that the search is for dummy node di. Make suitable assumptions, if any)
| i | 0 | 1 | 2 | 3 | 4 |
| pi | 0.10 | 0.15 | 0.20 | 0.10 | |
| qi | 0.05 | 0.10 | 0.10 | 0.10 | 0.10 |
Write the Dijkstra’s shortest path algorithm. Also, find the time complexity of this shortest path algorithm. Find the shortest paths from the vertex ‘A’ using Dijkstra’s shortest path algorithm for the graph given in Figure 1. Show all the steps of computation.
See Answer →Write the Prim’s algorithm to find the minimum cost spanning tree of a graph. Also, find the time complexity of Prim’s algorithm. Demonstrate the use of Kruskal’s algorithm and Prim’s algorithm to find the minimum cost spanning tree for the Graph given in Figure 1. Show all the steps.
See Answer →