Log In

Answers by Arjun

17 votes
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)$
answered Feb 18 in DS 5.1k views
16 votes
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 ___________
answered Feb 13 in Operating System 5.8k views
1 vote
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?
answered Jan 3 in CO and Architecture 11.7k views
4 votes
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
answered Nov 8, 2019 in Numerical Ability 3.4k views
7 votes
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$
answered Oct 19, 2019 in DS 5.4k views
3 votes
answered Sep 10, 2019 in Set Theory & Algebra 248 views
6 votes
2 votes
Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.
answered Aug 7, 2019 in Theory of Computation 765 views
3 votes
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.
answered Jul 15, 2019 in Operating System 619 views
1 vote
In the program scheme given below indicate the instructions containing any operand needing relocation for position independent behaviour. Justify your answer. ...
answered Jul 15, 2019 in CO and Architecture 642 views
7 votes
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$
answered Jul 14, 2019 in Digital Logic 2.3k views
5 votes
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__________.
answered Jul 14, 2019 in Operating System 2.3k views
3 votes
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.
answered Jul 14, 2019 in Operating System 798 views
4 votes
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)?
answered Jul 13, 2019 in Digital Logic 789 views
7 votes
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$
answered Jul 13, 2019 in Digital Logic 3.9k views
6 votes
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.
answered Jul 13, 2019 in Digital Logic 366 views
33 votes
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]\)
answered Jul 6, 2019 in Algorithms 6.8k views
3 votes
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
answered Jul 6, 2019 in Compiler Design 503 views
0 votes
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;
answered Jul 6, 2019 in Compiler Design 472 views
1 vote
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
answered Jul 6, 2019 in Algorithms 318 views
6 votes
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
answered Jul 6, 2019 in Programming 451 views
2 votes
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
answered Jul 4, 2019 in Programming 684 views
2 votes
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.
answered Jul 3, 2019 in Algorithms 318 views
17 votes
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)$
answered Jul 2, 2019 in Algorithms 5.5k views
2 votes
Consider the procedure declaration: Procedure P (k: integer) where the parameter passing mechanism is call-by-value-result. Is it correct if the call, P (A[i]), where A is an array and i an integer, is implemented as below. create a new local variable, say z; assign to ... the body of P using z for k; set A [i] to z; Explain your answer. If this is incorrect implementation, suggest a correct one.
answered Jun 30, 2019 in Compiler Design 460 views
1 vote
Write short answers to the following: (i). Which of the following macros can put a macro assembler into an infinite loop? .MACRO MI,X .IF EQ,X M1 X+1 .ENDC .IF NE,X .WORD X .ENDC .ENDM .MACRO M2,X .IF EQ,X M2 X .ENDC .IF NE,X .WORD X+1 .ENDC .ENDM Give an example call that does so.
answered Jun 30, 2019 in Compiler Design 517 views
4 votes
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)$
answered Jun 27, 2019 in Algorithms 807 views