3i Infotech Papers: Sample Questions 292  293 of 1245
Examrace Placement Series prepares you for the toughest placement exams to top companies.
Question number: 292
» Operating System » Unix
Describe in Detail
What are the bits that support the demand paging?
Explanation

Note the following parts of the page table entry, which includes physical address of the page and protection bits.

Page address

Age

Copy on write

Modify

Reference

Valid


A modified bit is set if the page has been altered since it was last loaded into main memory an unset bit means page does not have be written to the disk when swapped out.

Other control bits represent protection and permission at the page level.

A readonly/readwrite bit.

Kernel page or user page.

Question number: 293
Describe in Detail
Convert the given graph with weighted edges to minimal spanning tree, the equivalent minimal spanning tree is:
Explanation

Red edges indicate minimal spanning tree.
Kruskal’s algorithm

Kruskal’s algorithm is easiest to understand and best for solving problems by hand.
Kruskal’s algorithm:
sort the edges of G in increasing order by length
keep a subgraph S of G, initially empty
for each edge e in sorted order
if the endpoints of e are disconnected in S
add e to S
return S

An edge (u, v) when added is always the smallest one connecting the part of S reachable from u with the rest of G, so it must be part of the MST.

This algorithm is known as a greedy algorithm, because it chooses at each step the cheapest edge to add to S.
Other research on finding the minimum spanning tree

When edges of the graph have weights or lengths weight of a tree is the sum of weights of its edges. Different spanning trees have different edge length and hence weights. The problem is to find the minimum length spanning tree.

A randomized algorithm can solve it in linear expected time. [Karger, Klein, and Tarjan, “A randomized lineartime algorithm to find minimum spanning trees”, J. ACM, vol. 42,1995, pp. 321  328. ]

Solved in linear worstcase time if the weights are small integers. [Fredman and Willard, “Transdichotomous algorithms for minimum spanning trees and shortest paths”, 31^{st} IEEE Symp. Foundations of Comp. Sci. , 1990, pp. 719–725. ]