Newbie: June 2012

Tuesday, 19 June 2012

smilar question from NET D- 8707

The aging algorithm with a = 1/2 is being used to predict run times. The
       previous for runs, from oldest to most recent, are 40, 20, 40, and 15 
       msec. What is the prediction of the next time? (5 points)

  Ans: If take all four previous run times into consideration, the prediction
       is (((40 + 20) / 2 + 40) / 2 + 15) / 2 = ((30 + 40) / 2 + 15) /2
                                              = (35 + 15) / 2 = 25

       Or if take only two previous run times into consideration, the
       prediction is (40 + 15) /2 = 27.5

cache hit rate

The performance of a file system depends critically on the cache hit rate (fraction of the blocks found in the cache). If it takes 1 msec to satisfy a request from the cache, but 40 msec to satisfy a request if a disk read is needed, give a formula for the mean time required to satisfy a request if the hit rate is h. Plot this function for h:(0,1)

The mean time is calculated as the probability of a hit times the time required to proccess a hit plus the probability of a miss times the time required to proccess a miss or:

1 msec * h + (1 - h) * 40 msec

Monday, 11 June 2012

Important que to improve concept for UGC-NET

Collecting questions to improve my question bank

answers taken from website getgyan.com

Question 1 :

The register or main memory location wahich contains the effective address of the operand is known as:

Option A: Pointer.

Option B: Indexed Register.

Option C: Special Location.

Option D: Scratch Pad.

Correct Answer: A

Question 2 :

Page stealing is:

Option A: A sign of an efficient system.

Option B: Taking page frames from other working sets.

Option C: Should be the tunning goal.

Option D: Taking larger disk spaces for pages paged out.

Correct Answer: B

Question 3 :

Which of the following refers to the associative memory ?

Option A: The adress of data is generated by the CPU.

Option B: The address of data is supplied by the users.

Option C: There is no need for an address i.e. the data is used as an address.

Option D: The data are accessed sequentially.

Correct Answer: C

Question 4 :

Virtual memory -

A) is a method of memory allocation by which the program is subdevided into equal portions, or pages and core is subdevided into equal portions or blocks.
B) consists of those adedresses that may be generated by a processor during execution of a computation.
C) is a method of allocating processor time.
D) allows multiple programs to reside in seperate areas of core at the time.

Option A: A

Option B: B

Option C: C

Option D: D

Correct Answer: B

Question 5 :

The Memory Buffer Register (MBR) -

A) is a hardware memory device which denotes the location of the current instruction being executed.
B) is a group of electrical circuits (hardware) , that performs the intent of instruction fetched from memory.
C) contains the address of the memory location that is to be read from or stored into.
D) contains a copy of the designated memory location specified by the MAR after a "read" or the new contents of the memory prior to a "write".

Option A: A

Option B: B

Option C: C

Option D: D

Correct Answer: D

Question 6 :

The instruction register -

A) is hardware memory device which denotes the location of the current instruction being executed.
B) is a group of electrical circuits (hardware) , that performs the intent of instruction fetched from memory.
C) contains the address of the memory location that is to be read from or stored into.
D) contains a copy of the designated memory location specified by the MAR after a "read" or the new contents of the memory prior to a "write".

Option A: A

Option B: B

Option C: C

Option D: D

Correct Answer: B

Question 7 :

Thrashing -

Option A: is a natural consequence of virtual memory systems.

Option B: can always be avoided by swapping.

Option C: always occurs on large computers.

Option D: can be caused by poor paging algorithms.

Correct Answer: D

Question 8 :

Tharshing can be avoided if -

Option A: the pages , belonging to the working set of the programs, are in main memory.

Option B: the speed of CPU is increased.

Option C: the speed of I/O processor is increased.

Option D: All of the above.

Correct Answer: A

Question 9 :

The memory allocation scheme subject to "external" fragmentation is -

Option A: Segmentaion.

Option B: Swapping.

Option C: Pure Demand Paging.

Option D: Multiple contiguous fixed partitions.

Correct Answer: A

Question 10 :

If the number of bits in a virtual address of a program is 12 and the page size is 0.5K bytes, the number of pages in the virtual address space is -

Option A: 16

Option B: 32

Option C: 64

Option D: 128

Correct Answer: D

Question 11 :

Which of the following is not true about Memory Management ?

Option A: Virtual memory is used only in multi - user systems.

Option B: Segmetation suffers from external fragmentation.

Option C: Paging suffers from internal fragmentation.

Option D: Segmented memory can be paged.

Correct Answer: A

Question 12 :

In Virtual Memory Systems, Dynamic Address Translation -

Option A: is te hardware necessary to implement paging.

Option B: stores pages at a specific location on disk.

Option C: is useless wahen swapping is used.

Option D: is part of the operating system paging algorithm.

Correct Answer: A

Question 13 :

Seeks analysis -

Option A: is used for analyzing paging problems.

Option B: is used for analyzing device busy problems.

Option C: is used for analyzing control - unit busy problems

Option D: is only shown on real - time displays.

Correct Answer: B

Question 14 :

Swapping -

Option A: works best with many small partitions.

Option B: allows many programs to use memory simultaneously.

Option C: allows each program in turn to use the memory.

Option D: does not work with overlaying.

Correct Answer: C

Question 15 :

Which of the following statement is true ?

Option A: The LRU algorithm pages out pages that have been used recently.

Option B: Thrashing is a natural consequences of virtual memory systems.

Option C: Seek analusis is used for analysing control - unit busy problems.

Option D: All of the above.

Correct Answer: C

Question 16 :

The LRU algorithm ?

Option A: Pages out pages that have been used recently.

Option B: Pages out pages that have not been used recently.

Option C: Pages out pages that have been last used recently.

Option D: Pages out the first page in a given area.

Correct Answer: C

Question 17 :

Paging -

A) is a method of memory allocation by which the program is subdevided into equal portions, or pages and core is subdevided into equal portions or blocks.
B) consists of those addresses that may generated by a processor during execution of a computation.
C) is mwthod of allocating processor time.
D) allows multiple programs to reside in seperate areas of core at the time.

Option A: A

Option B: B

Option C: C

Option D: D

Correct Answer: A

Question 18 :

The Memory Address Register ( MAR ) -

A) is a hardware memory device which denotes the location of the current instruction being executed.
B) is a group of electrical circuits (hardware) , that performs the intent of instruction fetched from memory.
C) contains the address of the memory location that is to be read from or stored into.
D) contains a copy of the designated memory location specified by the MAR after a "read" or the new contents of the memory prior to a "write".

Option A: A

Option B: B

Option C: C

Option D: D

Correct Answer: C

Question 19 :

Memory -

A) is device that performs a sequence of operations specified by instructions in memory.
B) is the device where information is stored.
C) is a sequence of instructions.
D) is typically charaterized by intractive processing and time slicing of the CPU's time to allow quick response to each user.

Option A: A

Option B: B

Option C: C

Option D: D

Correct Answer: B

Question 20 :

Information in a memory that is no longer valid or wanted is known as -

Option A: Non - Volatile.

Option B: Volatile.

Option C: Surplus.

Option D: Grabage.

Correct Answer: D

Friday, 8 June 2012

Infix, Prefix, and Postfix Expressions:
For simplicity, we will consider algebraic expressions with binary operators +, –, *,
and / only.

Infix Notation:
Usual notation in constructing algebraic expression such that operator appears
between two operands; it is ambiguous and requires knowledge of operator hierarchy for
its evaluation. Parentheses can also be used to override operator hierarchy.

Prefix Notation:
A special notation in constructing algebraic expression such that operator appears
before its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.

Postfix Notation:
A special notation in constructing algebraic expression such that operator appears
after its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.

Example: The infix expression ((a–b)/c)*((d+e)–f) has the following postfix and prefix
expression.
Postfix: a b – c / d e + f – *
Prefix: * / – a b c – + d e f

Evaluating Postfix Expression:
scan given postfix expression;
for each symbol in postfix
if operand
then push its value onto a stack S;
if operator
then { pop operand2;
pop operand1;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;

Evaluating Prefix Expression:
reverse given prefix expression;
scan the reversed prefix expression;
for each symbol in reversed prefix
if operand
then push its value onto a stack S;
if operator
then { pop operand1;
pop operand2;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;

Infix to Postfix Conversion:
given a legal infix string;
create an initially empty postfix string;
create an initially empty operator stack S;
for each symbol ch in the infix string do
if ch is an operand
then
append it to the output postfix string;
else if ch == ‘(‘
then
push ch onto stack S;
else if S == ‘)’
then
pop and append operators to output string until the matching ‘(‘ is encountered;
// discard the two parentheses
else // ch must be some other operator
{ while operator stack not empty
and precedence(top(S)) ≥ precedence(ch)
and top(S) != ‘(‘ do
pop operator;
append it to the postfix string;
end while;
push S
}
end for;
while operator stack is not empty do
pop operator;
append it to the postfix string;
endwhile;

Infix to Prefix Conversion:
reverse a given legal infix string;
create an initially empty reversed prefix string;
create an initially empty operator stack S;
for each symbol ch in the reversed infix string do
if ch is an operand
then
append it to the output prefix string;
else if ch == ‘)‘
then
push ch onto stack S;
else if S == ‘(’
then
pop and append operators to output string until the matching ‘)‘ is encountered;
// discard the two parentheses
else // ch must be some other operator
{ while operator stack not empty
and precedence(top(S)) > precedence(ch)
and top(S) != ‘)‘ do
pop operator;
append it to the reversed prefix string;
end while;
push S
}
end for;
while operator stack is not empty do
pop operator;
append it to the reversed prefix string;
endwhile;
reverse the reversed output prefix string;

Example:
1. Given infix expression: ((a–b)/c)*((d+e)–f) and its equivalent postfix expression:
a b – c / d e + f – *
Postfix evaluation:
ch action operand stack
a push a
b push a b
– pop operand2 a
pop operand1
compute and push a–b
c push a–b c
/ pop operand2 a–b
pop operand1
compute and push (a–b)/c
d push (a–b)/c d
e push (a–b)/c d e
+ pop operand2 (a–b)/c d
pop operand1 a–b)/c
compute and push (a–b)/c (d+e)
f push (a–b)/c (d+e) f
– pop operand2 (a–b)/c (d+e)
pop operand1 a–b)/c
compute and push (a–b)/c (d+e)–f
* pop operand2 (a–b)/c
pop operand1
compute and push ((a–b)/c) * ((d+e)–f)

2. Given infix expression: ((a–b)/c)*((d+e)–f) and its equivalent prefix expression:
* / – a b c – + d e f
Reverse the given prefix expression to get f e d + – c b a – / *

Prefix evaluation:
ch action operand stack
f push f
e push f e
d push f e d

+ pop operand1 f e
pop operand2 f
compute and push f (d+e)
– pop operand1 f
pop operand2
compute and push (d+e)–f
c push (d+e)–f c
b push (d+e)–f c b
a push (d+e)–f c b a
– pop operand1 (d+e)–f c b
pop operand2 (d+e)–f c
compute and push (d+e)–f c (a–b)
/ pop operand1 (d+e)–f c
pop operand2 (d+e)–f
compute and push (d+e)–f (a–b)/c
* pop operand1 (d+e)–f
pop operand2
compute and push ((a–b)/c)* ((d+e)–f)

3. Given infix expression: (a–b)/c*(d + e – f / g).
Input: (a–b)/c*(d + e – f / g)

Postfix conversion:
ch action operator stack Postfix
( push (
a output ( a
– push ( – a
b output ( – a b
) pop until ( a b –
/ push / a b –

c output / a b – c
* pop a b – c /
push *
( push * ( a b – c /
d output * ( a b – c / d
+ push * ( + a b – c / d
e output * ( + a b – c / d e
– pop * ( a b – c / d e +
push * ( – a b – c / d e +
f output * ( – a b – c / d e + f
/ push * ( – / a b – c / d e + f
g output * ( – / a b – c / d e + f g
) pop until ( * a b – c / d e + f g / –
pop until empty stack a b – c / d e + f g / – *

Postfix: a b – c / d e + f g / – *

4. Given infix expression: (a–b)/c*(d + e – f / g).
Input: ) g / f – e + d ( * c / ) b – a (

Prefix conversion:
ch action operator stack Reversed Prefix
) push )
g output ) g
/ push ) / g
f output ) / g f
– pop ) g f /
push ) – g f /
e output ) – g f / e
+ push ) – + g f / e
d output ) – + g f / e d
( pop until ) g f / e d + –
* push * g f / e d + –
c output * g f / e d + – c
/ push * / g f / e d + – c
) push * / ) g f / e d + – c
b output * / ) g f / e d + – c b
– push * / ) – g f / e d + – c b
a output * / ) – g f / e d + – c b a

( pop until ) * / g f / e d + – c b a –
pop until empty stack g f / e d + – c b a – / *

Prefix: * / – a b c – + d e / f g

Copied from : http://people.eecs.ku.edu/~jvalland/lectures/268-L9a-PrefixPostfixNotes-S09.pdf

Thursday, 7 June 2012

What is meant by Best, worst and average case running times of an algorithm ???

In the simplest terms,

Best case = fastest time to complete, with optimal inputs chosen.
For example, the best case for a sorting algorithm would be data that's already sorted.
Worst case = slowest time to complete, with pessimal inputs chosen.
For example, the worst case for a sorting algorithm might be data that's sorted in reverse order (but it depends on the particular algorithm).
Average case = arithmetic mean. Run the algorithm many times, using many different inputs, compute the total running time (by adding the individual times), and divide by the number of trials. You may also need to normalize the results based on the size of the input sets.

Complexity and running time are often expressed in "Big O notation," which is used to describe the approximate amount of time an algorithm requires to complete, based the size of its input.

The most commonly used Big O descriptions are

O(1) always terminates in about the same amount of time, regardless of the input size.
O(logN) takes a fixed additional amount of time each time the input size doubles.
O(N) takes twice as long to finish if the input size doubles.
O(N²) takes four times as long if the input size doubles.
O(2^N) increases exponentially as the input size increases.

You can see from the table below that the difference is small for small input sizes, but it can become tremendous as the input size increases even a little bit.

Input Size              Time to Complete
               O(1)  O(logN)   O(N)   O(N²)   O(2^N)
     1           1       1      1       1       1
     2           1       2      2       4       4
     4           1       3      4      16      16
     8           1       4      8      64     256
    16           1       5     16     254   65536

answer is copied from stackoverflow.com Read Here