This Blog contains a huge collection of various lectures notes, slides, ebooks in ppt, pdf and html format in all subjects. 
My aim is to help students and faculty to download study materials at one place.

Adobe Photoshop

Hi friends i want to sell my own PSD (Photoshop document) which was complied in Adobe Photoshop5. Contact me on gistservicesz@gmail.com for payment information. And I will send it in form of CD of        250 MB.

Intrusion Detection System In BLACK Hole

Intrusion Detection System: IDS system which generates first aodv scenario and then it can implement the black hole attack after that it is also detecting the attacker node and preventing the packets routing through them 

[blackhole20-1-vbr.rar]

Important NET Questions

K-MAP SOLUTION TO 5 VARIABLES

Simplify the Boolean function
F(A,B,C,D,E)  = Σ (0,2,4,6,9,11,13,15,17,21,25,27,29,31)

Writing decimals in binary,

 Decimal    A    B    C    D    E
     0           0    0     0    0    0
     2           0    0     0    1    0
     4           0    0     1    0    0
     6           0    0     1    1    0
     9           0    1     0    0    1
     11         0    1     0    1    1  
     13         0    1     1    0    1
     15         0    1     1    1    1
     17         1    0     0    0    1
     21         1    0     1    0    1
     25         1    1     0    0    1
     27         1    1     0    1    1
     29         1    1     1    0    1
     31         1    1     1    1    1

Construct two Karnaugh maps for variables A,B,C and D when  E=0 and E=1

From Karnaugh map E=0,  F0 = A'B'E'

From Karnaugh map E=1,  F1 = BE+ AD'E

F  =   F0+  F1

F   =    A'B'E'   +  BE  +   AD'E

 

Solving Recurrence Relations

Solve the recurrence relation T(n) = T(n/2) + lg(n) where T(1) = 1 and n = 2k for a nonnegative integer k. Your answer should be a precise function of n in closed form. Note that lg represents the log function base 2.

T(n) = T(n/2) + lg(n)

T(n/2) = T(n/4) + lg(n/2)

T(n/4) = T(n/8) + lg(n/4)

T(n/8) = T(n/16) + lg(n/8)


Substituting for T(n)

T(n) = T(n/2) + lg(n)

= T(n/4) + lg(n/2)+lg(n)

= T(n/8)+ lg(n/4)+ lg(n/2)+lg(n)

= T(n/16)+lg(n/8)+ lg(n/4)+ lg(n/2)+lg(n)


----------------------------------------------------------

----------------------------------------------------------

Suppose n= 2**k

T(n) = 1 + lg (n. n/2 . n/4. . . . . n/2**k-1)

= 1+ lg(2**k  . 2**k-1 .   2**k-2 .  …… . 2)

= 1+ lg( 2 **(1+2+3+ - - - +k))

= 1 + (1+2+3+ ----+k)

= 1+ k(k+1)/2

______________________________________________________________________________

Solve the recurrence T(n) = T(n-1) + n

T(n)    = T(n-1) + n
T(n-1) = T(n-2) + n-1
T(n-2) = T(n-3) + n-2
T(n-3) = T(n-4) + n -3

 T(n)  =  T(n-1) + n
         =   T(n-2) + n-1+n
         =   T(n-3) + n-2+n-1+n
         =   T(n-4) + n-3+n-2+n-1+n
-----------------------------------------------

        Consider n= 2**k
 T(n)  =  T(n-k) + n+n-1+n-2+n-3+ -------------+n-(k-1)
         =  T(n-k) +  n(n-1) - k(k-1)/2
         = T(n-k) +  n**2 - n -lgn(lgn-1)/2
     
Therefore, asymptotic complexity is n**2

 

NP Completeness

Consider a reduction of problem A to problem B. What is the most precise claim you
can make about problem B for each of the following situations?

a) A is NP-complete and the reduction is in polynomial time.
 NP-hard. (At least as hard as NP-complete problem.)

b) A is in polynomial time and the reduction is also in polynomial time.
B could be anything.

c) A is NP-complete and the reduction is in Pspace.
B could be anything.

d) A is in nondeterministic polynomial time and the reduction is in polynomial time.
B is at least as hard as A, but nothing more can be said.

e) A requires exponential time and the reduction is in polynomial time.
B must requires polynomial time for deciding.

f) A is Pspace complete and the reduction is in Pspace.
B could be anything.
_______________________________________________________________________
Suppose you could reduce an NP complete problem to a polynomial time problem in
polynomial time. What would be the consequence?
What if the reduction required exponential time?

If we could reduce an NP-complete problem to a problem in P, then NP will
be equal to P. If the reduction required exponential time, then there is not
special consequence. (In fact any NP-complete problem can be reduced to
a polynomial time solvable problem using exponential time reduction.)

 

MEMORY MANAGEMENT

Assume you have a small virtual address space of size 64 KB. Further assume that this is a system
that uses paging and that each page is of size 8 KB.
(a) How many bits are in a virtual address in this system?

16 (1-KB of address space needs 10 bits, and 64 needs 6; thus 16).

(b) Recall that with paging, a virtual address is usually split into two components: a virtual page number (VPN) and an offset. How many bits are in the VPN?

3. Only eight 8-KB pages in a 64-KB address space.

(c) How many bits are in the offset?

16 (VA) - 3 (VPN) = 13.
Alternately: an 8KB page of course requires 13 bits to address each byte (213 = 8192).

(d) Now assume that the OS is using a linear page table, as discussed in class. How many entries does this linear page table contain?

One entry per virtual page. Thus, 8.

Now assume you again have a small virtual address space of size 64 KB, that the system again uses paging, but
that each page is of size 4 bytes (note: not KB!).


(a) How many bits are in a virtual address in this system?

Still 16. The address space is the same size.

(b) How many bits are in the VPN?

14.

(c) How many bits are in the offset?

Just 2 (4 bytes).

(d) Again assume that the OS is using a linear page table. How many entries does this linear page table
contain?
2**14, or 16,384.
____________________________________________________________________________________

 Consider the following segment table:

Segment  Base  Length
    0   219    600
    1  2300     14
    2    90    100
    3  1327    580
    4  1952     96

What are the physical addressed for the following logical addresses?

(a) 0,430

(b) 1,10

(c) 2,500

(d) 3,400

(e) 4,112

• (a) 219 + 430 = 649
• (b) 2300 + 10 = 2310
• (c) illegal reference; traps to operating system
• (d) 1327 + 400 = 1727
• (e) illegal reference; traps to operating system 

___________________________________________________________________________


Consider a paging system with the page table stored in memory.

(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?

(b) If we add associative registers, and 75% of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)

• 400 nanoseconds. 200 ns to access the page table plus 200 ns to access the word in memory.
• 250 nanoseconds. 75% of the time it's 200 ns, and the other 25% of the time it's 400ns, so the equation is:

  e.a. = (.75*200)+(.25*400)

  ________________________________________________________________________
  
  A certain computer provides its users with a virtual memory space of 2**32 bytes. The computer has 2**18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4K bytes. A user process generated the virtual address 11123456. Explain how the system establishes the corresponding physical location.
  
  * The virtual address in binary form is
  
  0001 0001 0001 0010 0011  0100 0101 0110 
  
  Since the page size is 2**12, the page table size is 2**20. Therefore, the low-order 12 bits (0100 0101 0110) are used as the displacement into the page, while the remaining 20 bits (0001 0001 0001 0010 0011) are used as the displacement in the page table.

ANALYSIS BIG-O NOTATION

Important Topics for NET DAA

ANALYSIS BIG-O NOTATION

For each of the following pairs of functions f(n) and g(n), state whether f(n) =
O(g(n)), f(n) = ­Ω(g(n)), or f(n) = Θ(g(n)), or none of the above:


(a) f(n) = n2 + 3n + 4, g(n) = 6n + 7
Sol: f(n) = ­Ω(g(n).


(b) f(n) = n √n , g(n) = n2 - n
Sol: f(n) = O(g(n)).


(c) f(n) = 2**n - n**2, g(n) = n**4 + n**2
Sol: f(n) = ­­Ω(g(n).


(d) Assume you have five algorithms with the running times
listed below (these are the exact running times). How much slower do each of these
algorithms get when you double the input size
i) n²
Sol: 4T(n)

ii) n³
Sol: 8T(n)

iii) 100n²
Sol: 4T(n)

iv) nlgn
Sol: 2n(lg2n) = 2n(1+lgn) ~ 2n lgn
T(n) = 2T(n)

v) 2ⁿ
Sol:  [T(n)]² 


(e)  Write a big-O expression for 1+2+3+...+n?
Sol:  O(n²)


True or false:
(f) An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.
Sol : False


(g)  n! = O(nⁿ)
Sol: True


(h) n^O(1) = O(n²)
Sol: False.  O(1) can be any large constant .


(i) All of the following are true.

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), if c is constant
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))
  

   

  MINIMUM SPANNING TREE

  1. In an undirected graph, the shortest path between two nodes lies on some minimum spanning
  tree.
  A: False.
  
  2. If the edges in a graph have different weights, then the minimum spanning tree is unique.
  A: True.
  
  3. If the edge with maximum weight belongs to a cycle, then there exists some MST that
  does not contain this edge.
  A: True
  
  4. Adding a constant to every edge weight does not change the minimum spanning tree.
  A: True
  
  5. There can be more than one minimum spanning trees if the weight of the edges are all distinct
  A.False
  
  6. If all weights are the same, every spanning tree is minimum.
  A. True
  
  7. Greedy algorithm runs in exponential time
  A. False
  
  8. A minimum spanning tree should contain all edges of the graph
  A. False
  
  9. A minimum spanning tree should contain all vertices of the graph
  A.True
  
  10.Adding an edge to a spanning tree of a graph G always creates a cycle.
  A.False
  
  11. Adding an edge to a spanning tree connecting two existing vertices of a graph G always creates a cycle.
  A. True
  
  12. For any cycle in a graph, the cheapest edge in the cycle is in a minimum spanning tree.
  A. False

Theroy of Computation

TURING MACHINE

1. A Universal Turing Machine can compute anything that any other Turing Machine could possibly compute.
True

2.The Turing Test is a test of whether a problem can be solved by a Turing Machine.
True

3. Every acceptable language is also decidable.
False

4. Decidability is a special case of decidability
True

5. Regular languages are decidable
True

6. Context free languages are not decidable
False

DFA MINIMIZATION

DFA MINIMIZATION EXAMPLES

1. Example 1
2. Example2

 

Chomsky Hierarchy

The diagram shows how different classes of languages such as regular, context free, context sensitive, P, NP, PSAPACE, NPSPACE, EXPTIME, NEXPTIME, EXPSPACE, ACCEPTABLE, DECIDABLE, CO-ACCEPTABLE etc are related to each other.

PUMPPING LEMMA

Steps to solve Pumping Lemma problems:
1. If the language is finite, it is regular , otherwise it might be non-regular.
2. Consider the given language to be regular
3. State pumping lemma
4. Choose a string w from language, choose smartly .
5. Partition it according to constraints of pumping lemma in a generic way
6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language
given.
7. State the contradiction and end the proof.

How to remember what pumping Lemma says:

Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or
“there exists”. Notice:
For every regular language L
There exists a constant n
For every string w in L such that |w| >= n,
There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and For every k>=0 , the string xykz is also in L.

courtesey: http://suraj.lums.edu.pk/~cs311w05/pumping_lemma_writeup.pdf
1. Show that L2 = {0^m1^m | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L1. Consider any pumping number p; p≥ 1. Choose w = 0^p1^p.
Consider any pumping decomposition w = xyz;
|y| > 0 and |xy| ≤ p. It follows that x = 0^a and y = 0^b and z = 0^p-a-b1^p, for b ≥ 1. Choose i = 2. We need to show that xy²z = 0^p+b1^p is not in L1.

b ≥ 1.
So p+b > p
Hence 0^p+b1^p is not in L.

2. L2 = {xx | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L2. Consider any pumping number
p ≥ 1. Choose w = 10^p10^p. Consider any pumping decomposition w = xyz; all we know about xyz is that
|y| > 0 and |xy| ≤ p. There are two possibilities:

(a) x = 10^aand y = 0^b and z = 0^p-a-b10^p, for b ≥ 1.
(a) x = " and y = 10b and z = 0^p-b10^p1.
Choose i = 2. We need to show that xy²z is not in L2.
In case (a), xy2z = 10^p+b10^p, which is not in L2 because b ≥ 1.
In case (b), xy2z = 10^b10^p10^p, which is not in L2 because it contains three 1’s.

3. We prove that L3 = {1ⁿ² | n ≥ 0} is not regular.

We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.
Choose w = 1^p2.
Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows
that x = 1^a and y = 1^b and z = 1^p2
−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that
xy²z = 1^n2+b is not in L3; that is, we need to show that p2 + b is not a square. Since b ≥ 1, we have
p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 4.Prove that Language L = {0n: n is a perfect square} is irregular.

Solution: L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such that:
|y| > 0 , |xy| <= n and for all k>=0 , the string xy^kz is also in L.
Choose w to be w = 0s where s = n² that is it is a perfect square.
Let w= 00000000000000000………00000 = xyz . (The length of w = s = n² in this case.)
Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n²- k ) + (k) From pumping lemma, I can pump y any number of times and the new string should also belong to the language. Suppose I pump y twice then, the new string should belong to the language that is it should have length that is a perfect square but, |xy2z| = |xz| + 2|y| = (n²- k ) + 2k = n² + k where n² + k < 1 =" (n+1)(n+1)"> n² (As k > 0)
=> n² <>2 + k < (n+1)2 => n² + k is not a perfect square
=> xy²z is not in L
=> This is a contradiction to the pumping lemma
So, our initial assumption must have been wrong that is L is not regular.

OPERATING SYSTEM Important

OPERATING SYSTEM Important

What are two types of low-level operations that higher-level synchronization operations(e.g., semaphores and monitors) can be built upon?
Test-and-set. compare-and-swap. atomic reads and writes. Other atomic operations. enabling
and disabling interrupts.
_______________________________________________________________
What is the difference between a process and a thread?
Every process has its own address space, but multiple threads inside a process share part of
the memory with their parent process. There is less context switching overhead to switch
among threads when compared to switching among threads.
_______________________________________________________________
What is the difference between deadlock and starvation?
In a deadlock situation, none of the involved processes can possibly make progress. In a
starvation situation, a process is ready to execute, but it is not being allowed to execute.
_______________________________________________________________
Suppose our computer system is running five processes (P1,P2,P3,--,P5 ) and has four
separate types of resources (A,B,C,D). We want to see if the system is in a safe state
using the Banker's algorithm. Using the following information about the state of the
system, determine if the state is safe: (11 points)
Total
AB C D
4 5 4 3

Available
AB C D
0 1 0 0

Maximum
A B C D
P1 1 3 3 0
P2 2 2 1 3
P3 1 1 0 1
P4 1 4 1 0
P5 3 1 2 1

Used
A B C D
P1 0 1 2 0
P2 2 0 1 1
P3 1 0 0 1
P4 0 3 1 0
P5 1 0 0 1

A B C D
Total 4 5 4 3

A B C D
Available 0 1 0 0

Total gives the number of instances of each resource in the system; Available gives the
number of unallocated instances of each resource; Maximum refers to the maximum
number of instances of each resource required by each process; Used refers to how many instances of each resource each process currently holds.

Answer:
The Need matrix is as follows:
Need
A B C D
P1 1 2 1 0
P2 0 2 0 2
P3 0 1 0 0
P4 1 1 0 0
P5 2 1 2 0

The state of the system is unsafe. Executing the Banker's algorithm terminates with P2
and P5 unable to complete. We give a possible sequence of execution with "Work" P3 runs (1, 1, 0, 1), P4 runs (1, 4, 1, 1),P1 runs (1, 5, 3, 1). Now neither P2
nor P5 can release its resources because each holds resources the other needs.
------------------------------------------------------------------------------------------------
2. A computer system has m resources of the same type and n processes share these
resources. Prove or disprove the following statement for the system:
This system is deadlock free if sum of all maximum needs of processes is less than m+n.

3. There are four processes which are going to share nine tape drives. Their current and
maximum number of allocation numbers are as follows :
process current maximum
p1 3 6
p2 1 2
p3 4 9
p4 0 2
a. Is the system in a safe state? Why or why not?
b. Is the system deadlocked? Why or why not?


A Process Using Mutual Exclusion:

int me;
while (1) {
/* non critical section code */
enter(me); /* also called entry code */
/* critical section code */
leave(me); /* also called exit code */
}

We assume each process has access to its process ID, which we're calling me in this example. The process can pass its ID into the enter() and leave() functions.
First try: use a lock.

shared int lock = 0;

void enter(int me)
{
while (lock == 1) /* do nothing */;
lock = 1;
}

void leave(int me)
{
lock = 0;
}


Problem: Process 0 can check that the lock is available, and then get preempted. Process 1 can now check the the lock is available, and enter the critical section. While in the critical section, it can be swapped out, and Process 0 restarted. Since Process 0 has already checked the availability of the lock, it can also enter the critical section. This "solution" fails to provide mutual exclusion.
Second try: take turns

shared int turn = 0;

void enter(int me)
{
while (turn != me);
}

void leave(int me)
{
turn = 1 - me;
}

Problem: If process 0 never attempts to enter the critical section, process 1 is never allowed to enter it (and, if 0 has entered once, it can never enter again until 1 endters). This "solution" fails to guarantee progress. Can you convince yourself it does in fact provide mutual exclusion (so it does meet some of the criteria, but not all)?
Third try: Keep track of whether the other guy wants in

shared int flag[2];

void enter(int me)
{
flag[me] = 1;
while (flag[1-me]);
}

void leave(int me)
flag[me] = 0;
}

Problem: Doesn't satisfy the progress condition. Both processes can get stuck in the entry code and wait there forever, in other words "deadlocked".

Fourth and last try: (Peterson's Algorithm): combine second and third

The basic approach here is that we're going to keep track of both whether the other process wants in, and also whose turn it is. If the other process wants to get in, we'll let it in if it's its turn. But if it doesn't want in, we'll take its place.

shared int flag[2];
shared int turn;

void enter(int me)
{
flag[me] = 1;
turn = 1-me;
while (flag[1-me] && (turn == (1-me)));
}

void leave(int me)
{
flag[me] = 0;
}

CRITICAL SECTION

1.

// functions to enter/leave the // critical section void critical_section_enter_t0() { while (turn != T0) continue; } void critical_section_leave_t0() { turn = T1; }

// functions void critical_section_enter_t1() { while (turn != T1) continue; } void critical_section_leave_t1() { turn = T0; }

i. Does this proposal provide mutual exclusion for the critical
section? Justify your answer!
Yes, it does. The variable ‘turn’ is either T0 or T1, and if it is T0, then
only thread T0 can progress past ‘critical_section_enter_t0’, and vice
versa.

ii. Is this proposal a satisfactory solution to the critical section
problem? Justify your answer!

No, it is not. It does not guarantee progress. In particular, thread T0
cannot reenter the critical section after it has left it unless thread T1
entered and left the critical section in the interim since critical_section_leave_t0() sets turn = T1. Only critical_section_leave_t1() can change it back to T0 again.

Consider:
critical_section_enter_t0();
critical_section_leave_t0();
// may block even though t1 is not in the critical section
critical_section_enter_t0();
critical_section_leave_t0();

NET Questions TOC QUESTIONS

True or False

1. In a finite language no string is pumpable. True
2. A DFA has infinite number of states. False
3. A DFA can have more than one accepting state. True
4. In DFA all states have same number of transitions. True
5. Every subset of a regular language is regular. False
6. Let L4 = L1L2L3. If L1 and L2 are regular and L3 is not regular, it is possible that L4 is regular. True
7. In a finite language no string is pumpable. True
8. If A is a nonregular language, then A must be infinite. True
9. Every context-free language has a context-free grammarin Chomsky normal form. True
10. If A is a context-free language, then A must be nonregular. False
11. The class of regular languages is closed under intersection. True
12. If a language A is regular, then it A must be finite. False
13. Every language is Turing-recognizable. False
14. If a language is context-free, then it must be Turing-decidable. True
15. The problem of determining if a context-free grammar generates
    the empty language is undecidable. False
16. The problem of determining if a Turing machine recognizes the
    empty language is undecidable. True
17. The set of all languages over an alphabet is countable.False
18. There are some languages recognized by a 5-tape, nondetermin-
    istic Turing machine that cannot be recognized by a 1-tape,
    deterministic Turing machine.False
    
19. The language { 0n1n | 0 ≤ n ≤ 1000 } is regular. True
20. Nonregular languages are recognized by NFAs. False
21. The class of context-free languages is closed under intersection. False
22. A language has a regular expression if and only if it
    has an NFA. True
23. The regular expression (01*0 ∪ 1)*0 generates the language
    consisting of all strings over {0, 1} having
    an odd number of 0’s. False
24. If a language A has a PDA, then A is generated by a
    context-free grammar in Chomsky normal form. True
25. If A is a context-free language and B is a language such that B is a subset of A, then B must be a context-free language. False
26. If a language A has an NFA, then A is nonregular. False
27. The regular expressions (a ∪ b)* and (b*a*)* generate the same language. True
28. If a language A has a regular expression, then it also has a context-free grammar. True

REGULAR EXPRESSIONS

Important Questions for NET

REGULAR EXPRESSIONS

SOME REGULAR EXPRESSIONS QUESTIONS FROM TOC

Describe the language denoted by the following regular expressions:

a) a(a|b)*a

The expression denotes the set of all strings of length two or more that start and end with an ‘a’.

b) ((e|a)b*)*

The expression denotes the set of all strings over the alphabet {a,b}.

c) (a|b)*a(a|b)(a|b)

The expression denotes the set of all strings of length 3 or more with an ‘a’ in the third position from the right. Ie of form yaxz where y is an arbitrary string , and x and z are single characters.

d) a*ba*ba*ba*

The expression denotes the set of all strings that contain precisely 3 b’s.

e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*

The expression denotes the set of all strings of even length.