In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
-
Solution
A linked list or one way list is a linear collector of data elements, called nodes, where the linear order is given by means of pointers, so worst case comparison needed to search a singly list of length n is n.
The minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same colour is
-
Solution
we need 3 colors to colors a odd cycle and 2 colors to color an even cycle.
So Ans is
n – 2[n/2] + 2
The solution to the recurrence equation T (2k) = 3T (2k–1) + 1, T (1) is
-
Solution
The trapezoidal rule for integration give exact result when the integrand is a polynomial of degree
-
Solution
The rank of the matrix \(\begin{bmatrix} 1 &1 \\ 0 &0 \end{bmatrix}\) is
-
Solution
It is 2 × 2 matrix \(\begin{bmatrix} 1 &1 \\ 0 &0 \end{bmatrix}\)= 0
So Rank is 1
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}.There is an edge between (a, b) and (c, d) if |a– c| ≤ 1 and|b–d| ≤ 1. The number of edges in this graph is__________.
-
Solution
506 edges
The value of the dot product of the eigen vectors corresponding to any pair of different eigenvalues of a 4-by-4 symmetric positive definite matrix is __________.
-
Solution
We know that for a symmetric positive definite matrix the eigen vectors corresponding to two different eigen values are orthogonal.
So, their dot product is equal to zero.However we must not that the eigen vectors corresponding to the same eigen value (occuring more than once) need not be orthogonal to each other.
Above mentioned result is deduced from spectral theorem of Linear Algebra.
Assume that there are 3 page frames which are initially empty.If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.
-
Solution
The given reference string is:
1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6.
Available no. of frames = 3.
We know that in the optimal replacement policy, when a page fault occurs, the required page is loaded from secondary memory and “that page in main memory will be replaced which will not be used for the longest period of time”. Use of this algorithm guarantees the lowest possible page fault rate for a fixed number of frames.Furthermore, this algorithm also does not suffer with Belady’s Anomaly.
Required page
Frames
Page fault (Y/N)
We can see that “Page 4” replaced “Page 3” as it will not be used for longest period of time (Page 1,2 both will be used before page 3). Similarly,Red marked page-3 replaced page-5 as both page - 2, 4 will be used in future.From the above table:
Total no. of page faults = 7.
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.
Using the shortest remaining time first scheduling algorithm,the average process turnaround time (in msec)is____________________.
-
Solution
7.2 milli seconds
QUESTIONS CARRY 2 MARKS EACH
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.
Using the shortest remaining time first scheduling algorithm,the average process turnaround time (in msec)is____________________.
-
Solution
The graph
Weight of minimum spanning tree.
Use the Kruskal’s algorithm to find the minimum spanning tree .
Step 1 Arrange all the edges in ascending order i.e., (h, g), (i, c), (g,f), (a, b), (f, c), (i, g), (c, d), (h, i), (a, h), (b, c), (d, e), (f, e), (b, h),(d, f).
Step 2 After drawing each edge one by one in ascending order and avoid that edges, which forms loop, we get the following minimum spanning tree.Total weight = 1 + 2 + 2 + 4 + 4 + 7 + 8 + 9 = 37