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

Essay Question▾

Describe in Detail

What are the bits that support the demand paging?


Understanding of demand paging

Understanding of Demand Paging

Understanding of demand paging

  • 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 read-only/read-write bit.

    • Kernel page or user page.

Question number: 293

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

Convert the given graph with weighted edges to minimal spanning tree, the equivalent minimal spanning tree is:

Graph of the minimal spanning tree

Graph of the Minimal Spanning Tree

Graph of the minimal spanning tree


Minimal spanning tree in graph

Minimal Spanning Tree in Graph

Minimal spanning tree in graph

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

Image of the Kruskal's algorithm

Image of the Kruskal’S Algorithm

Image of the Kruskal’s algorithm

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