search
Log In

Recent questions tagged gate1998

4 votes
2 answers
1
Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m < n$ and $R^m = R^n$.
asked Aug 12, 2018 in Set Theory & Algebra Arjun 667 views
19 votes
3 answers
2
Solve the following recurrence relation $x_n = 2x_{n-1}-1, n>1$ $x_1=2$
asked May 4, 2016 in Algorithms Arjun 1.9k views
3 votes
4 answers
3
Consider a disk with $c$ cylinders, $t$ tracks per cylinder, $s$ sectors per track and a sector length $s_l$. A logical file $d_l$ with fixed record length $r_l$ is stored continuously on this disk starting at location $(c_L, t_L, s_L)$ ... . Derive the formula to calculate the disk address (i.e. cylinder, track and sector) of a logical record n assuming that $r_l=s_l$.
asked Mar 6, 2016 in Operating System Arjun 840 views
27 votes
9 answers
4
Compute the post fix equivalent of the following expression $3^*\log(x+1)-\frac{a}{2}$
asked Aug 29, 2015 in DS Arjun 4.6k views
36 votes
5 answers
5
In a computer system where the best-fit' algorithm is used for allocating jobs' to memory partitions', the following situation was encountered:$\begin{array}{|l|l|} \hline \textbf{Partitions size in $KB$} & \textbf{$4K \ 8K \ 20K \ 2K$} \\\hline \textbf{Job sizes in $KB$} & \text{$2K ... $} \\\hline \end{array}$When will the $20K$ job complete?
asked Jul 10, 2015 in Operating System Arjun 4.3k views
15 votes
5 answers
6
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed integer)
asked Oct 17, 2014 in Theory of Computation Arjun 2.4k views
26 votes
10 answers
7
Consider the following relational database schemes: COURSES (Cno, Name) PRE_REQ(Cno, Pre_Cno) COMPLETED (Student_no, Cno) COURSES gives the number and name of all the available courses. PRE_REQ gives the information about which courses are pre-requisites for a ... following using relational algebra: List all the courses for which a student with Student_no 2310 has completed all the pre-requisites.
asked Sep 26, 2014 in Databases Kathleen 2.9k views
36 votes
5 answers
8
Consider the following database relations containing the attributes Book_id Subject_Category_of_book Name_of_Author Nationality_of_Author With Book_id as the primary key. What is the highest normal form satisfied by this relation? Suppose the attributes Book_title and Author_address are ... is changed to {Name_of_Author, Book_title}, what will be the highest normal form satisfied by the relation?
asked Sep 26, 2014 in Databases Kathleen 7.6k views
21 votes
3 answers
9
Free disk space can be used to keep track of using a free list or a bit map. Disk addresses require $d$ bits. For a disk with $B$ blocks, $F$ of which are free, state the condition under which the free list uses less space than the bit map.
asked Sep 26, 2014 in Operating System Kathleen 2k views
32 votes
4 answers
10
Four jobs are waiting to be run. Their expected run times are $6, 3, 5$ and $x.$ In what order should they be run to minimize the average response time? Write a concurrent program using $\text{par begin-par end}$ to represent the precedence graph shown below.
asked Sep 26, 2014 in Operating System Kathleen 4.5k views
15 votes
1 answer
11
Let the attribute ‘$val$’ give the value of a binary number generated by $S$ in the following grammar: $S \rightarrow L.L \mid L$ $L \rightarrow LB \mid B$ $B \rightarrow 0 \mid 1$ For example, an input $101.101$ gives $S.val = 5.625$ Construct a syntax directed translation scheme using only synthesized attributes, to determine $S.val$.
asked Sep 26, 2014 in Compiler Design Kathleen 4.1k views
17 votes
2 answers
12
An identifier in a programming language consists of up to six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier. Build an $LL(1)$ parsing table for the language defined by the $LL(1)$ ... $X \rightarrow d \text{ semi } X \mid sY$ $Y \rightarrow \text{ semi } s Y \mid \epsilon$
asked Sep 26, 2014 in Compiler Design Kathleen 1.4k views
17 votes
1 answer
13
Derive a recurrence relation for the size of the smallest AVL tree with height $h$. What is the size of the smallest AVL tree with height $8$?
asked Sep 26, 2014 in DS Kathleen 1.7k views
15 votes
1 answer
14
Draw the binary tree with node labels $\text{a, b, c, d, e, f and g}$ for which the inorder and postorder traversals result in the following sequences: Inorder: $\text{a f b c d g e}$ Postorder: $\text{a f c g e d b}$
asked Sep 26, 2014 in DS Kathleen 1.1k views
17 votes
5 answers
15
Let $p$ be a pointer as shown in the figure in a single linked list. What do the following assignment statements achieve? q: = p -> next p -> next:= q -> next q -> next:=(q -> next) -> next (p -> next) -> next:= q
asked Sep 26, 2014 in DS Kathleen 2.3k views
24 votes
4 answers
16
For a set-associative Cache organization, the parameters are as follows: $\begin{array}{|c|l|} \hline \text {$t _c$} & \text{Cache Access Time }\\\hline \text{$ ... $n = k\times m$ is a non-zero integer and $1 < m \leq l$. Give the value of the hit ratio for $l = 1$.
asked Sep 26, 2014 in CO and Architecture Kathleen 3k views
1 vote
2 answers
17
Calculate the total time required to read 35 sectors on a 2-sided floppy disk. Assume that each track has 8 sectors and the track-to-track step time is 8 milliseconds. The first sector to be read is sector 3 on track 10. Assume that the diskette is soft sectored and the controller has a 1-sector buffer. The diskette spins at 300 RPM and initially, the head is on track 10.
asked Sep 26, 2014 in Operating System Kathleen 1.2k views
18 votes
2 answers
18
Design a synchronous counter to go through the following states:$1, 4, 2, 3, 1, 4, 2, 3, 1, 4 \dots $
asked Sep 26, 2014 in Digital Logic Kathleen 1.5k views
8 votes
3 answers
20
Let $G_1 = (N, T, P, S_1)$ be a CFG where, $N=\{S_1, A, B\},T=\{a, b\}$ and $P$ ... $5$ production rules. Is $L_2$ inherently ambiguous?
asked Sep 26, 2014 in Compiler Design Kathleen 1.2k views
23 votes
1 answer
21
Let $M=(\{q_0, q_1\}, \{0, 1\}, \{z_0, X\}, \delta, q_0, z_0, \phi)$ be a Pushdown automation where $\delta$ is given by $\delta(q_0, 1, z_0) = \{(q_0, Xz_0)\}$ $\delta(q_0, \epsilon, z_0) = \{(q_0, \epsilon)\}$ ... $\delta(q_0, 0, z_0) = \{(q_0, z_0)\}$ What is the language accepted by this PDA by empty stack? Describe informally the working of the PDA
asked Sep 26, 2014 in Theory of Computation Kathleen 1.6k views
16 votes
2 answers
22
Let $(A, *)$ be a semigroup, Furthermore, for every $a$ and $b$ in $A$, if $a \neq b$, then $a*b \neq b*a$. Show that for every $a$ in $A$, $a*a=a$ Show that for every $a$, $b$ in $A$, $a*b*a=a$ Show that for every $a,b,c$ in $A$, $a*b*c=a*c$
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 1.9k views
22 votes
4 answers
23
Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A $\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$ List the ordered pairs of the equivalence relations induced by $\Pi_1$. Draw the graph of the above equivalence relation. Let ... $\left\langle\left\{\Pi_1, \Pi_2, \Pi_3, \Pi_4\right\}, \text{ refines } \right\rangle$.
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 2.7k views
17 votes
6 answers
24
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 1.5k views
2 votes
1 answer
25
Derive the expressions for the number of operations required to solve a system of linear equations in $n$ unknowns using the Gaussian Elimination Method. Assume that one operation refers to a multiplication followed by an addition.
asked Sep 26, 2014 in Linear Algebra Kathleen 454 views
8 votes
1 answer
26
Find the points of local maxima and minima, if any, of the following function defined in $0\leq x\leq 6$. $x^3-6x^2+9x+15$ Integrate $\int_{-\pi}^{\pi} x \cos x dx$
asked Sep 26, 2014 in Calculus Kathleen 1.3k views
17 votes
2 answers
27
Suppose we have a database consisting of the following three relations. $\text{FREQUENTS (student, parlor)}$ giving the parlors each student visits. $\text{SERVES (parlor, ice-cream)}$ ... parlor) Express the following in SQL: Print the students that frequent at least one parlor that serves some ice-cream that they like.
asked Sep 26, 2014 in Databases Kathleen 2.1k views
20 votes
2 answers
28
Consider the grammar S $\rightarrow Aa \mid b$ A $\rightarrow Ac \mid Sd \mid \epsilon$ Construct an equivalent grammar with no left recursion and with minimum number of production rules.
asked Sep 26, 2014 in Compiler Design Kathleen 2.7k views
18 votes
2 answers
29
The implication gate, shown below has two inputs ($x \text{ and }y)$; the output is 1 except when $x =1 \text{ and } y=0\text{, realize }f=\bar{x}y+x\bar{y}$ using only four implication gates. Show that the implication gate is functionally complete.
asked Sep 26, 2014 in Digital Logic Kathleen 1.4k views
24 votes
2 answers
30
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language: $L=\{w \in \{0, 1\}^* \mid w$ interpreted as binary number (ignoring the leading zeros) is divisible by five $\}.$
asked Sep 26, 2014 in Theory of Computation Kathleen 3k views
...