Basic CS-Algorithms [3i Infotech Placement]: Sample Questions 4 - 5 of 12

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 4

Algorithms

Question

MCQ▾

There was a circuit given using three NAND gates with two inputs and one output. Find the output

Choices

Choice (4)

a.

NOT

b.

AND

c.

OR

d.

XOR

Answer

c.

Explanation

Using 3 NAND Gate 2 Input and 1 Output is Or
  • In the question with the 3 NAND gates presumably the outputs of two of them are connected to the inputs of the third.
  • When we are use 3 NAND gate with 2 inputs then output is an OR gate.
    • To get a logic 1 output from a NAND gate, we need a logic 0 on both of its inputs.
    • Logic 1 at both inputs of the first two NAND gates will produce a logic 0 output from both of them.
    • The two logic 0′s are fed to the inputs of the third NAND gate producing a logic 0 output from the third NAND gate.

Question 5

Algorithms
Edit

Describe in Detail

Essay▾

In the context of memory management, what are placement and replacement algorithms?

Explanation

Placement Algorithm

  • Determine where in available real-memory to load a page.
  • Common methods are first-fit, next-fit, best-fit.
    • First-fit:
      • Maintain list of free partitions ordered by addresses.
      • Tendency for small fragments start and large fragments at list end.
    • Next-fit:
      • Tendency to fragment the large free block at the end of memory.
      • Leads to more equal distribution of fragments.
    • Best-fit:
      • Search the entire list and allocate the smallest hole that is big enough.

Replacement Algorithm

  • Determine which page should be be swapped out.
  • Used when memory is full and one process needs to remove page to make room for another page.
    • Page fault forces choice:
      • Which page to remove to make room for incoming page?
    • Modified page is first saved
      • Unmodified overwritten.
    • Better not to choose an often used page
      • Probably need to bring back in soon.

Page Replacement Algorithms

First in first out:

  • Oldest page in main memory is selected for replacement.
  • Easy to implement, replaces pages from the tail and add new pages at the head.

Reference String: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1,2, 1,

Misses: x x x x x x x x x

Page Replacement Algorithms

Optimal Page Algorithm

  • An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms.
  • Replace the page not be used for largest period of time.
  • Ideal but not possible in real life as it depends on accurately predicting future behaviour of the program

Reference String: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1,2, 1,

Misses: x x x x x x

Optimal Page Algorithm

Least Recently Used (LRU) Algorithm

  • Page which has not used for the longest time in main memory is selected for replacement.
  • Easy to implement, keep a list, replace pages by looking back into time.

Reference String: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1,2, 1,

Misses: x x x x xx x x

Least Recently Used (LRU) Algorithm

Developed by: