List of practice Questions

Which of the following is FALSE?
Let \( P \) be a regular language and \( Q \) be a context free language such that \( Q \) is a subset of \( P \). Then which of the following is ALWAYS regular?
If the production rules are given as:
\( S \to XY | W \)
\( X \to aXb | \epsilon \)
\( Y \to cY | \epsilon \)
\( W \to aWc | bZ | \epsilon \)
\( Z \to bZ | \epsilon \)
Then the language generated by these rules is _______ .
Subset Construction method refers to _______ .
The output of a syntax-directed translation scheme is _______ .
Which of the following is a regular language?
The maximum number of transitions which can be performed over a state in a DFA? \( \Sigma = \{a, b, c\} \)
The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .
Inherited attributes in SDTs are used for _______ .
The language \( L = \{M | M \text{ halts on all inputs}\} \) is _______ .
A problem is NP-complete if it is _______ .
One way to build a heap is to start at the end of the array (the leaves) and push each new value up to the root. Its time complexity is _______ .
The time complexity to compute the 15\(^\text{th}\) Fibonacci number using dynamic programming is _______ .
If the recursive call keeps calculating the same things over and over again, we can use _______ which stores partial results already calculated and to be used again.
The _______ process updates the costs of all the vertices \(V\), connected to a vertex \(U\), if we could improve the best estimate of the shortest path to \(V\) by including \((U,V)\) in the path to \(V\).
A threaded binary tree is a binary tree in which every node that does not have right child has a thread to its _______.
Best case complexity of insertion sorting is _______ .
Which notation represents the tightest upper bound of an algorithm’s running time?
The greedy approach is optimal for _______ .
The minimum possible time complexity to sort \(n\) integers in the range [1, \(n^2\)] is _______ .
If one wants to add and delete elements quickly without reshuffling the rest, then which data structure suits the best?
What is the time complexity to insert an element at the beginning of a dynamic array?
The recurrence T(n) = 2T(n/2) + n has a solution of _______.
The height of a binary tree with 31 nodes (assuming no single-child nodes) is _______.
The inorder traversal of a BST gives elements in _______.