GATE 1987 Computer Science Questions

# Recent questions tagged gate1987

1
A voltage source e(t) $50 \sin 100$ is connected to a resistor R of 3 ohms in series with an inductor L of $0.04$ henries at time $t$ (in seconds) = 0. The expression for the current in the circuit for $1=0$ is of the form. $i(t) = Ae^{kt} + B sing (100t - \emptyset)$ Find the values of $A, K, B$ and $\emptyset$.
2
A Boolean function $f$ is to be realized only by $NOR$ gates. Its $K-map$ is given below: The realization is
3
Fig. below shows the circuit diagram of a wien bridge oscillator using an op-amp. The frequency of oscillation is given by $f= 1/2 \pi CR$. To have the system oscillate the ratio $R_{2}/R_{1}$ should be $0.5$ $29$ $2$ Any value
4
The below figure shows four D-type flip-flops connected as a shift register using a $XOR$ gate. The initial state and three subsequent states for three clock pulses are also given. State $Q_{A}$ $Q_{B}$ $Q_{C}$ $Q_{D}$ Initial $1$ $1$ $1$ $1$ After the first clock $0$ $1$ $1$ ... $Q_{A} Q_{B} Q_{C} Q_{D}$ after the fourth clock pulse is $0000$ $1111$ $1001$ $1000$
5
The Boolean expression $A \oplus B \oplus A$ is equivalent to $AB + \bar {A}\bar B$ $\bar{A}B+A\bar{B}$ $B$ $\bar{A}$
6
The relative costs of assigning jobs $J_{1}, J_{2}$ and $J_{3}$ to machines $M_{1}, M_{2}$ and $M_{3}$ are given below: $\begin{array}{|c|cccc|}\hline\textbf{JOBS} && \textbf{Machines} \\ & \textbf{$M_{1}$} & \textbf{$M_{2}$} & \textbf{$ ... Using the assignment method find the assignment involving minimum cost. Is this an optimal assignment?
7
Use Simpson's rule with $h=0.25$ to evaluate $V= \int_{0}^{1} \frac{1}{1+x} dx$ correct to three decimal places.
8
Given $f(300)=2,4771; f(304) = 2.4829; f(305) = 2.4843$ and $f(307) = 2.4871$ find $f(301)$ using Lagrange's interpolation formula.
9
Show that the conclusion $(r \to q)$ follows from the premises: $p, (p \to q) \vee (p \wedge (r \to q))$
10
Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$.
11
Give a minimal DFA that performs as a $\mod - 3,\;$ $1$'s counter, i.e. outputs a $1$ each time the number of $1$'s in the input sequence is a multiple of $3$.
12
What is the generating function $G(z)$ for the sequence of Fibonacci numbers?
13
Solve the recurrence equations: $T(n) = T(n - 1)+ n$ $T(1) = 1$
14
Give the composition tables (Cayley Tables) of the two non isomorphic groups of order 4 with elements $e, a, b, c$ where $c$ is the identity element. Use the order $e, a, b, c$ for the rows and columns.
15
How many true inclusion relations are there of the from $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?
16
Specify an adjacency-lists representation of the undirected graph given above.
17
Show that the number of odd-degree vertices in a finite graph is even.
18
How many one-to-one functions are there from a set $A$ with $n$ elements onto itself?
19
How many binary relations are there on a set $A$ with $n$ elements?
20
Consider the following proposal to the "readers and writers problem." Shared variables and semaphores: aw, ar, rw, rr : interger; mutex, reading, writing: semaphore: initial values of variables and states of semaphores: ar=rr=aw=rw=0 reading_value = ... Can a group of readers make waiting writers starve? Can writers starve readers? Explain in two sentences why the solution is incorrect.
21
Construct a binary tree whose preorder traversal is K L N M P R Q S T and inorder traversal is N L K P R M S Q T
22
List the invariant assertions at points $A, B, C, D$ and $E$ in program given below: Program division (input, output) Const dividend = 81; divisor = 9; Var remainder, quotient:interger begin (*(dividend >= 0) AND (divisor > 0)*) remainder := dividend; quotient := 9; (*A*) ... 1; remainder := remainder - divisor; (*C*) end; (*D*) quotient := quotient - 1; remainder := remainder + divisor; (*E*) end
23
A list of $n$ elements is commonly written as a sequence of $n$ elements enclosed in a pair of square brackets. For example. $[10, 20, 30]$ is a list of three elements and $[]$ is a nil list. Five functions are defined below: $car (l)$ returns the first element of its argument list $l$; $cdr (l)$ ... $f ([32, 16, 8], [9, 11, 12])$ (b) $g ([5, 1, 8, 9])$
24
Eight 7-segment LED displays and a keyboard consisting of 28 keys are to be interfaced to a microprocessor based system. Give the block diagram of the interface circuit using minimum number of port lines from any programmable I/O chip. Use any other IC chip if necessary.
25
Give the character format for data transmission in asynchronous serial mode.
26
What is cache memory? What is rationale of using cache memory?
27
Find out the width of the control memory of a horizontal microprogrammed control unit, given the following specifications: $16$ control lines for the processor consisting of ALU and $7$ registers. Conditional branching facility by checking $4$ status bits. Provision to hold $128$ words in the control memory.
Design an $8 \times 8$ multiplier using five 4-bits adders and 4 ROM's each programmed to realise $4 \times 4$ multiplier.
State whether the following statements are TRUE or FALSE: A relation $r$ with schema $(X, Y)$ satisfies the function dependency $X \rightarrow Y$, The tuples $\langle 1, 2\rangle$ and $\langle 2, 2 \rangle$ can both be in $r$ simultaneously.
State whether the following statements are TRUE or FALSE: The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.