The length of the shortest string NOT in the language (over S = {a, b}) of the following regular expression is______________.a*b* (ba)*a*
-
Solution
a * b * (ba) * a *
Length O is present(as it accepts ∈)
Length 1 is present (a, b)
Length 2 is present(aa, ab, ba, bb)
Length 3 is not present (bab not present)
∴it is 3
Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory.It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory.If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is_________.
-
Solution
Tave= H1× (TTLB + TM) + (1– H1) × (TTLB+ 2× TM)
TTLB= 10 ms
TM= 30 ms
H1= 0.6
Tave= 0.6 × ( 10 + 80) + (1 – 0.6) (10 + 2 × 80)
= 0.6 × 90 + 0.4× 170 = 122 ms
An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):
The average waiting time (in milliseconds) of the processes is _________.
-
Solution
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.
-
Solution
From the above data, after allocating 2 units of tape to each process,with 1 available unit any of the 3 process can be satisfied in such a way, that no dead lock will be there.Therefore it is 7 unit tapes.
Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally unique IPv4 address.Design a 50-bit globally unique ID for this purpose. After what period(in seconds) will the identifiers generated by a host wraparound?
-
Solution
An IP router implementing Classless Inter-domain Routing(CIDR)receives a packet with address 131.23.151.76. The router’s routing table has the following entries:
The identifier of the output interface on which this packet will be forwarded is ______.
-
Solution
Soln :1
Address 131.23.151.76
Coming to I field of given routing table.
⇒ 131.16.0.0/12
131.0001 0111.151.76
131.0001 0000.0.0 (mask bit = 12)
131.16.0.0 (matched)
Coming to II field of given routing table.
⇒ 131.28.0.0/14
131.0001 0111.151.76131.0001 0100.0.0(mask bit = 14)
131.20.0.0(not matched)
Coming to III field of given routing table
⇒ 131.19.0.0/16
131.0001 0111.151.76
131.0001 0111.0.0 (mask bit = 16)
131.23.0.0(not matched)
Coming to IV field of given routing table
⇒ 131.22.0.0/15
131.0001 0111.151.76
131.0001 0110.0.0 (mask bit = 15)
131.22.0.0 (matched)
∵I and IV entries are matched, we pickup longest mask bit
∵Output interface identifies is 1.
A text is made up of the characters a, b, c, d, e each occurring with the probability 0.12, 0.4, 0.15, 0.08 and 0.25 respectively.The optimal coding technique will have the average length of __________.
-
Solution
Using Hoffman’s algorithm, code for a is 1111; b is 0; c is 110; d is 1110; e is 10.
Average code length is 4 ×.12 +1 × .4 +3 ×.15 + 4 ×.08 + 2×.25= 2.15
A network on the Internet has a subnet mask of 255.255.240.0. what is the maximum number of hosts it can handle ?
-
Solution
the given subnet mask’s encoded IP address is
11111111111111111111000000000000
12 bits are available for the hostid ⇒ 212 possible hostids. so the maximum number of hosts on this subnet is 212= 4096 hosts.
A digital search tree is implemented as a tree with n nodes each of which can contain m pointers, corresponding to the m possible symbols in each position of the key. The number of nodes that must be accessed to find a particular key is
To evaluate an expression without any embedded function calls
-
Solution
If no any embedded function calls one stack is enough.