# 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

Essay Question▾

### 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.

• 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.

• Kernel page or user page.

## Question number: 293

Essay Question▾

### 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 linear-time algorithm to find minimum spanning trees”, J. ACM, vol. 42,1995, pp. 321 - 328. ]

• Solved in linear worst-case time if the weights are small integers. [Fredman and Willard, “Trans-dichotomous algorithms for minimum spanning trees and shortest paths”, 31st IEEE Symp. Foundations of Comp. Sci. , 1990, pp. 719–725. ]