Which of the following problems is not NP-hard?

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is _______.

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an input for which Quicksort takes maximum time.

Following algorithm(s) can be used to sort n integers in the range [1....... n³] in O(n) time

Consider the SLR(1) and LALR (1) parsing tables for a context-free grammar. Which of the following statements is/are true?

Start and stop bits do not contain 'information' but these are used in serial communication for

Which of the following predicate calculus statements is/are valid?

Maximum number of edges in a planar graph with $$n$$ vertices is _______ .

(a) If G is a group of even order, then
show that there exists an element $$a \ne e$$,
the identifier $$g$$, such that
$${a^2} = e$$

(b) Consider the set of integers $$\left\{ {1,2,3,4,6,8,12,24} \right\}$$ together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?
i) Group ii) ring
iii) field iv) lattice
Justify your answer

Which of the following is/are tautology?

A non-planar graph with minimum number of vertices has

Uses Modus ponens $$\left( {A,\,\,A \to B\,|\,\, = B} \right)$$ or resolution to show that the following set is inconsistent:

(1) $$Q\left( x \right) \to P\left( x \right)V \sim R\left( a \right)$$
(2) $$R\left( a \right) \vee \sim Q\left( a \right)$$
(3) $$Q\left( a \right)$$
(4) $$ \sim P\left( y \right)$$
where $$x$$ and $$y$$ are universally quantifies variables, $$a$$ is a constant and $$P, Q, R$$ are monadic predicates.

A computer system has 6 tape drives, with n process completing for them. Each process may need 3 tape drives. The maximum value of n for which the system is guaranteed to be deadlock free is:

Let the page reference and the working set window be c c d b c e c e a d and 4, respectively. The initial working set at time $$t = 0$$ contains the pages {a, d, e}, where a was referenced at time $$t = 0, d$$ was referenced at time $$t = -1,$$ and $$e$$ was referenced at time $$t = -2.$$ Determine the total number of page faults and the average number of page frames used by computing the working set at each reference.

Which page replacement policy sometimes leads to more page faults when size of memory is increased?

At a particular time of computation the value of a counting semaphore is 7. Then 20 P operations and 15 V operations were completed on this semaphore. The resulting value of the semaphore is:

Which of the following is an example of a spooled device?

Which of the following statements is / are true / false?

The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$ is prime$$\left. \, \right\}$$ is not regular

Which of the following statements is / are true / false?

Regular languages are closed under infinite union.

Which of the following statements is / are true / false?

Union of two recursive languages is recursive

In which of the cases stated below is the following statement true?
“For every non-deterministic machine $${M_1}$$ there exists an equivalent deterministic machine $${M_2}$$ recognizing the same language“.

Context-free languages are

If $$G$$ is a context-free grammar and $$w$$ is a string of length $$n$$ in $$L(G),$$ how long is a derivation of $$w$$ in $$G,$$ if $$G$$ is Chomsky normal form?

Which of the following regular expression identities are true?