Question

Question 1: (a) Give the formal definitions of the following: 1. A graph 2. A tree 3. B+ tree 4. An NP-complete problem up-complete problem 5. An undecidable problem

Answer 1

1. A graph is nothing but a connection of nodes. These connections can be in a loop or not. It is a non linear data structure. It consists of edges and nodes

2. A tree is a data structure in which a root have at most two children. It is non linear data structure.

3. B+ tree is extension of B tree. In this data can only be stored on the leaf nodes while internal nodes can only store the key values. The leaf nodes of a B+ tree are linked together in the form of a singly linked lists to make the search queries more efficient.

4. A problem is called if it is both NP and NP hard, where NP is the set of decision problems that can be verified in polynomial time.

5. A language which is not accepted by any turing machine. decision problem P is called “undecidable” if the language L of all yes instances to P is not decidable. Undecidable languages are not recursive languages, but sometimes, they may be recursively enumerable languages.