Register

Recent questions tagged gate1991

31 votes
2 answers
6
GATE CSE 1991 | Question: 14,c
Consider the binary tree in the figure below: Outline a procedure in Pseudo-code to delete an arbitrary node from such a binary tree with $n$ nodes that preserves the structures. What is the worst-case time complexity of your procedure?
Consider the binary tree in the figure below:Outline a procedure in Pseudo-code to delete an arbitrary node from such a binary tree with $n$ nodes that preserves the stru...
User Avatar
20 votes
3 answers
7
GATE CSE 1991 | Question: 14,b
Consider the binary tree in the figure below: Give different steps for deleting the node with key $5$ so that the structure is preserved.
Consider the binary tree in the figure below:Give different steps for deleting the node with key $5$ so that the structure is preserved.
User Avatar
41 votes
4 answers
10
GATE CSE 1991 | Question: 15,b
Consider the following first order formula: ... Does it have finite models? Is it satisfiable? If so, give a countable model for it.
Consider the following first order formula:$\left ( \matrix{ \forall x \exists y : R(x,y) \\[1em] \Large \land \\[1em] \forall x \forall y : \left ( R(x,y) \impl...
User Avatar
21 votes
5 answers
11
GATE CSE 1991 | Question: 17,a
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
User Avatar
48 votes
3 answers
12
GATE CSE 1991 | Question: 16-b
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.
User Avatar
20 votes
2 answers
15
GATE CSE 1991 | Question: 5-b
Find the minimum sum of products form of the logic function $ f(A,B,C,D) = \Sigma_{m}(0,2,8,10,15)+ \Sigma _{d}(3,11,12,14)$ where $m$ and $d$ represent minterm and don't care term respectively.
Find the minimum sum of products form of the logic function $ f(A,B,C,D) = \Sigma_{m}(0,2,8,10,15)+ \Sigma _{d}(3,11,12,14)$ where $m$ and $d$ represent minterm and don't...
User Avatar
52 votes
2 answers
18
GATE CSE 1991 | Question: 16,a
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's.$
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's....
User Avatar
15 votes
5 answers
19
GATE1991-15,a
Show that the product of the least common multiple and the greatest common divisor of two positive integers $a$ and $b$ is $a\times b$.
Show that the product of the least common multiple and the greatest common divisor of two positive integers $a$ and $b$ is $a\times b$.
User Avatar
25 votes
3 answers
20
GATE CSE 1991 | Question: 14,a
Consider the binary tree in the figure below: What structure is represented by the binary tree?
Consider the binary tree in the figure below:What structure is represented by the binary tree?
User Avatar
26 votes
5 answers
21
GATE CSE 1991 | Question: 13
Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for the time-complexity of your algorithm.
Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for ...
User Avatar
27 votes
1 answer
29
GATE CSE 1991 | Question: 5-a
Analyse the circuit in Fig below and complete the following table ${\begin{array}{|c|c|c|}\hline \textbf{a}& \textbf{b}& \bf{ Q_n} \\\hline 0&0\\\ 0&1 \\ 1&0 \\ 1&1 \\ \hline \end{array}}$
Analyse the circuit in Fig below and complete the following table$${\begin{array}{|c|c|c|}\hline\textbf{a}& \textbf{b}& \bf{ Q_n} \\\hline0&0\\\ 0&1 \\ 1&0 \\ 1...
User Avatar
Page: