Important NET Questions
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
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
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.)
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:
___________________________________________________________________________
Consider a paging system with the page table stored in memory.
K-MAP SOLUTION TO 5 VARIABLES
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
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
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
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.
No comments:
Post a Comment