What is proposition ? Explain with the help of an example. Explain Disjunction and Conjunction with the help of truth table for each.
See Answer →Describe the divide-and-conquer approach to solve recurrences ? Explain how this approach can be used to apply binary search in a sorted list.
See Answer →Moore and Mealy Machine
See Answer →Deterministic and Non-deterministic Turing Machine
See Answer →Deterministic and Non-deterministic finite automata
See Answer →What is a finite automata ? Why is it needed? How is a finite automata represented?. Also explain the term regular expression with the help of an example.
See Answer →What is isomorphism? Find, if the following graphs G1 and G2 are isomorphic or not. Explain how you arrived at your answer.
Draw a hypercube graph Q3 (also called the cubical hypercube). Check whether the hypercube Q3 is Hamiltonian
See Answer →A die is rolled once. What are the probabilities of the following events:
a. Getting an odd number
b. Getting at least a value 2
c. Getting at most a value 2
d. Getting at least 7
How many different permutations arepossible of the letters, taken all at a time, of the word: ASSESSES?
See Answer →Use Mathematical Induction to prove that :
Graph Colouring Problem
See Answer →Vertex cover problem
See Answer →Clique problem
See Answer →3-CNF SAT
See Answer →What are NP-Hard and NP-Complete problem? What is the role of reduction? Explain with the help of an example.
See Answer →Define P and NP class of Problems with the help of examples. How are P class of problem different from NP class of Problems.
See Answer →What are decision problems and Optimisation problems? Differentiate the decision problems and Optimisation problems with the help of at least two problem statements of each
See Answer →Consider the following Graph:
Figure 1: Graph for Problem 3(a) and 3(b)
a) Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum cost
spanning tree of the graph given in Figure 1. Show all the steps of computation.
Also, compute the time complexity of both the algorithms.
b) In the Figure 1, find the shortest path from the vertex ‘a’ using Dijkstra’s shortest
path algorithm. Show all the steps of computation. Also, find the time complexity
of the algorithm.
c) What is dynamic programming? What is the principle of Optimality? Use the
dynamic programming approach to find the optimal sequence of chain
multiplication of the following matrices:
| Matrix | Dimension |
| A1 | 5 x 10 |
| A2 | 10 x 20 |
| A3 | 20 x 15 |
| A4 | 15 x 8 |
| A5 | 8 x 10 |
d) Make all the possible Binary Search Trees for the key values 25, 50, 75.
e) Explain the Knuth Morris Pratt algorithm for string matching. Use this algorithm
to find a pattern “algo” in the Text “From algae to algorithms”. Show all the steps.
What is the time complexity of this algorithm
What is the use of Topological sorting? Write and explain the Topological sorting algorithm. Also, compute the time complexity for the topological sorting algorithm.
See Answer →