Q. What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as f = Σ (0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available. Answer:                                                     . ...

Q. Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is. Solution: You need at least 3 switches of Ethernet are required to connect 15 computers.

Q. Let Σ be the set of all bijections from {1, … , 5} to {1, … , 5}, where 𝑖𝑑 denotes the identity function, i.e. 𝑖𝑑(𝑗) = 𝑗, ∀𝑗.  Let ∘ denote composition on functions.   For a string 𝑥 =𝑥1 𝑥2 ⋯ 𝑥𝑛 ∈ Σ𝑛, 𝑛 ≥ 0 , let 𝜋(𝑥) = 𝑥1 ∘ 𝑥2 ∘ ⋯ ∘ 𝑥𝑛. Consider the language 𝐿 = {𝑥 ∈ Σ∗| 𝜋(𝑥) = 𝑖𝑑 }. The ...

Q. Suppose 𝑌 is distributed uniformly in the open interval (1,6). The probability that the polynomial 3𝑥2 + 6𝑥𝑌 + 3𝑌 + 6 has only real roots is (rounded off to 1 decimal place) Solution: For a quadratic polynomial ax2 + bx + c = 0. There are three condition: b2 - 4ac > 0   ...

Q. Let 𝑇 be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves 𝑎 and 𝑏 of 𝑇 are chosen uniformly and independently at random. The expected value of the distance between 𝑎 and 𝑏 in 𝑇 (i.e., the number of edges in the unique path between 𝑎 and 𝑏) is ...

Q. A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60-MHz clock. To service a cache miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch ...

Q. The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointers. The disk block size is 4 kB, and the disk block address is 32-bits long. The maximum possible file size is (rounded off to 1 decimal place) ____________GB. Solution: No. ...

Q. Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below: ProcessP1P2P3P4Arrival time0134CPU burst time313Z These processes are run on a single processor using preemptive Shortest Remaining Time First ...

Q. Consider the following statements: The smallest element in a max-heap is always at a leaf node The second largest element in a max-heap is always a child of the root node A max-heap can be constructed from a binary search tree in Θ(𝑛) time A binary search tree can be constructed ...

Q. Consider the following snapshot of a system running 𝑛 concurrent processes. Process 𝑖 is holding 𝑋𝑖 instances of a resource R, 1 ≤ 𝑖 ≤ 𝑛. Assume that all instances of R are currently in use. Further, for all 𝑖, process 𝑖 can place a request for at most 𝑌𝑖 additional instances of R while holding ...

Q. Let 𝐺 be any connected, weighted, undirected graph. 𝐺 has a unique minimum spanning tree, if no two edges of 𝐺 have the same weight. 𝐺 has a unique minimum spanning tree, if, for every cut of 𝐺, there is a unique minimum-weight edge crossing the cut. Which of the above two statements ...

Q. There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, …, An is (A) O(n) (B) O(n log n) ...