QUESTIONS CARRY 2 MARKS EACH
A piece wise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale).
If we use the Newton-Raphson method to find the roots of f(x) = 0 using x0, x1 and x2 respectively as initial guesses, the roots obtained would be
QUESTIONS CARRY 2 MARKS EACH
Consider the following system of linear equations
\(\begin{bmatrix} 2 & 1 &-4 \\ 4 &3 &-12 \\ 1 & 2 & -8 \end{bmatrix}\begin{bmatrix} x\\ y\\ z \end{bmatrix}=\begin{bmatrix} \alpha \\ 5\\ 7 \end{bmatrix}\)Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of a, does this system of equations have infinitely many solutions?
QUESTIONS CARRY 2 MARKS EACH
The graph G = (V, E) satisfies | E | ≤3 | V | – 6. The min-degree of G is defined as \(\overset{min}{v\in V}\){degree (v)}. Therefore,min-degree of G cannot be
-
Solution
Let the min-degree of G is x. then G has at least |v| *x/2 edges.|v|*x/2 < = 3* |v| -6 for x = 6, we get 0 < = -6, Therefore, min degree of G cannot be 6.Correct answer is (d).
QUESTIONS CARRY 2 MARKS EACH
m identical balls are to be placed in n distinct bags. You are given that m ≥ kn, where k is a natural number ≥ 1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?
-
Solution
QUESTIONS CARRY 2 MARKS EACH
Consider the following SQL query :
select distinct a1, a2,……, an
from r1, r2, ……, rm
where P
For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expression?
-
Solution
SQL form the cartesi an product of the relation named in the form of clause, perform a relational algebra selection using the where clause predicate and then projects the result onto the attributes of the select clause.
A computer sytem has a page size of 1024 bytes and maintain the page table for each process in main memory. The overhead required for doing a look up in the page table is 500 ns. To reduce this overhead, the computer has a TLB that caches 32 virtual page to physical frame mappings. ATLB look up requires 100 ns. The TLB hit rate required to ensure an average virtual address translation time of 200 ns is _________.
-
Solution
Given Page size = 1024 bytes Over
head required = 500 ns
TLB caches 32 virtual pages
TLB lookup = 100 ns
To find TLB hit rate
Solution Let the TLB hit rate to be x,we have 200 = x ×100 + (1 – x)× 500
⇒ x = 3/4 = 0.750
Hence, the TLB hit rate is 0.750.
If one uses straight two-way merge sort algorithm to sort following elements in ascending order 20, 47, 15, 8, 9, 4, 40,30, 12, 17 then order of these elements after the second pair of the algorithm is
-
Solution
In a system with 32 bit virtual addresses and 1 KB page size,use of one-level page tables for virtual to physical address translation is not practical because of
-
Solution
Since page size is too small it will make size of page tables huge.Size of page table= (total number of page table entries)*(size of a page table entry)
Let us see how many entries are there in page table
Number of entries in page table = (virtual address space size)/(page size)
=(2^32)/(2^10)
=2^22
Now, let us see how big each entry is.
If size of physical memory is 512 MB then number of bits required to address a byte in 512 MB is 29. So, there will be(512MB)/(1KB) = (2^29)/(2^10) page frames in physical memory. To address a page frame 19 bits are required.Therefore, each entry in page table is required to have 19 bits.
Note that page table entry also holds auxiliary information about the page such as a present bit, a dirty or modified bit,address space or process ID information, amongst others.So size of page table > (total number of page table entries)*(size of a page table entry)> (2^22 *19) bytes >9.5 MB And this much memory is required for each process because each process maintains its own page table. Also, size of page table will be more for physical memory more than 512 MB.There fore, it is advised to use multilevel page table for such scenarios.
An m-ary tree has n leaf nodes. What is the expression for total number of nodes in the tree?
-
Solution
In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
-
Solution
The 7th smallest element must be in first 7 levels. Total number of nodes in any Binary Heap in first 7 levels is at most 1 + 2 + 4 + 8 + 16 + 32 + 64 = 128 which is a constant.Therefore we can always find 7th smallest element in Θ(1)time.