1 vote
1
The output of lexical analyzer is: A set of regular expressions Strings of character Syntax tree Set of tokens
2
What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order? $\Theta(n)$ $\Theta(n \log n)$ $\Theta ( n)^{2}$ $\Theta(1)$
3
Consider a paging system that uses $1$-level page table residing in main memory and a TLB for address translation. Each main memory access takes $100$ ns and TLB lookup takes $20$ ns. Each page transfer to/from the disk takes $5000$ ns. Assume that the TLB hit ... is read from disk. TLB update time is negligible. The average memory access time in ns (round off to $1$ decimal places) is ___________
1 vote
4
I want to clearly understand the difference between compulsory miss, conflict miss and capacity miss what I understood is compulsory miss: when a block of main memory is trying to occupy fresh empty line of cache, it is called compulsory miss conflict miss: when ... set-associative cache. Because in associative mapping, no block of main memory tries to occupy already filled line. is this correct?
5
The population of a new city is $5$ million and is growing at $20\%$ annually. How many years would it take to double at this growth rate? $3-4$ years $4-5$ years $5-6$ years $6-7$ years
6
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h > 0$, then the minimum number of nodes in the tree is $2^{h-1}$ $2^{h-1} + 1$ $2^h - 1$ $2^h$
7
FIELD AND RING ARE IN SYLLABUS???
8
9
Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.
10
A concurrent system consists of $3$ processes using a shared resource $R$ in a non-preemptible and mutually exclusive manner. The processes have unique priorities in the range $1 \dots 3$, $3$ being the highest priority. It is required to synchronize the processes such ... priority]:=true; else begin V(proceed [priority]); busy:=true; end V(mutex) Give the pseudo code for the procedure release_R.
1 vote
11
In the program scheme given below indicate the instructions containing any operand needing relocation for position independent behaviour. Justify your answer. ...
12
If the state machine described in figure should have a stable state, the restriction on the inputs is given by $a.b=1$ $a+b=1$ $\bar{a} + \bar{b} =0$ $\overline{a.b}=1$ $\overline{a+b} =1$
13
Assume that there are $3$ page frames which are initially empty. If the page reference string is $\text{1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6}$ the number of page faults using the optimal replacement policy is__________.
14
A number of processes could be in a deadlock state if none of them can execute due to non-availability of sufficient resources. Let $P_i, 0 \leq i \leq 4$ represent five processes and let there be four resources types $r_j, 0 \leq j \leq 3$. Suppose the following data structures have been used ... Is the system currently in a safe state? If yes, explain why.
15
Following floating point number format is given $f$ is a fraction represented by a $6-bit$ mantissa (includes sign bit) in sign magnitude form, $e$ is a $4-bit$ exponent (includes sign hit) in sign magnitude form and $n=(f, e) = f. 2^e$ is a floating point ... point addition of $A$ and $B.$ What is the percentage error (up to one position beyond decimal point) in the addition operation in (b)?
16
The value of a $\text{float}$ type variable is represented using the single-precision $\text{32-bit}$ floating point format of $IEEE-754$ standard that uses $1$ $\text{bit}$ for sign, $\text{8 bits}$ for biased exponent and $\text{23 bits}$ for the ... $−14.25$. The representation of $X$ in hexadecimal notation is $C1640000H$ $416C0000H$ $41640000H$ $C16C0000H$
17
The Karnaugh map of a function of (A, B, C) is shown on the left hand side of the above figure. The reduced form of the same map is shown on the right hand side, in which the variable C is entered in the map itself. Discuss, The methodology by which the reduced map has been derived and the rules (or steps) by which the boolean function can be derived from the entries in the reduced map.
18
In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j$. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of $1. . . n$? $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{4}$ $\frac{n(n+1)}{4}$ $2n[\log_2n]$
19
A simple Pascal like language has only three statements. assignment statement e.g. x:=expression loop construct e.g. for i:=expression to expression do statement sequencing e.g. begin statement ;&hellip;; statement end Write a context-free grammar (CFG) for statements in the above ... in CFG. Show the parse tree for the following statements: for j:=2 to 10 do begin x:=expr1; y:=expr2; end
20
What does the following program output? program module (input, output); var a:array [1...5] of integer; i, j: integer; procedure unknown (var b: integer, var c: integer); var i:integer; begin for i := 1 to 5 do a[i] := i; b:= 0; c := 0 for i := 1 to 5 do write (a[i]); writeln(); a[3]:=11; ... (c,b); b := 5; c := 6; end; begin i:=1; j:=3; unknown (a[i], a[j]); for i:=1 to 5 do write (a[i]); end;
1 vote
21
This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question. Let $L$ be a set. We say that $L$ is in $P$ if there is some algorithm which given input $x$ decides if $x$ is in $L$ or not ... $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above
22
Consider the following program fragment: var a,b : integer; procedure G(c,d: integer); begin c:=c-d; d:=c+d; c:=d-c end; a:=2; b:=3; G(a,b); If both parameters to $G$ are passed by reference, what are the values of $a$ and $b$ at the end of the above program fragment ? $a=0$ and $b=2$ $a=3$ and $b=2$ $a=2$ and $b=3$ $a=1$ and $b=5$ None of the above
23
State the halting problem of the Turing machine.
24
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
25
Given below is the sketch of a program that represents the path in a two-person game tree by the sequence of active procedure calls at any time. The program assumes that the payoffs are real number in a limited range; that the constant INF is larger than any ... end end; (search) Comment on the working principle of the above program. Suggest a possible mechanism for reducing the amount of search.
Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of $a[\:]$ as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and ... $(a,$ left_end$, k)$ $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a,$left_end$, k)$
Choose the correct alternatives (More than one may be correct). The complexity of comparision based sorting algorithms is: $\Theta (n \log n)$ $\Theta (n)$ $\Theta \left(n^2\right)$ $\Theta (n\sqrt n)$