# 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

Choice (4)

a.

NOT

b.

AND

c.

OR

d.

XOR

c.

### Explanation

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

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

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

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

Developed by: