Sample Questions

<Sample questions>

• Which one of the following in-place sorting algorithms needs the minimum number of swaps?

1. Insertion sort 

2. Quick sort 

3. Heap sort 

4. Selection sort 

Ans: (4) Selection sort. Selection sort is an in-place algorithm having the minimum number of swaps.

• A cache memory needs an access time of 30ns and main memory of 150ns, what is the average access time of the CPU (assume hit ratio = 80%)?

Ans: 60. (30 * 0.8) + ((30 + 150) * 0.2) = 60

• What is the minimum number of two-input NAND gates used to perform the function of two-input OR gate?

Ans: 3 NAND gates are required in minimum to implement OR gate.

• At lower multiprogramming levels, throughput increases as the multi-programming level increases. This phenomenon is best explained by the fact that as the multi-programming level increases: 'the potential for concurrent activity among system resources increases.

• At intermediate multiprogramming levels, the rate of increase of throughput with multiprogramming levels decreases. This phenomenon is best explained by the fact that as the multiprogramming level increases: 'some system resource begins to saturate (to be utilized 100%).

• Let A and B be two sets of words (strings) from Σ*, for some alphabet of symbol Σ. Suppose B is a subset of A. Which of the following statements must always be true of A and B?

1. If A is finite, then B is finite 

2. If A is regular, then B is regular 

3. If A is context-free, then B is context-free.

Answer: 1 is True and 2 and 3 are False.

• Two processors, M-5 and M-7, implement the same instruction set. Processor  M-5 uses a 5-stage pipeline and a clock cycle of 10 nanoseconds. Processor M-7 uses a 7-stage pipeline and a clock cycle of 7.5 nanoseconds. Which of the following is (are) true?

1. M'7's pipeline has better maximum throughput than M-5's pipeline.

2. The latency of a single instruction is shorter on M-7's pipeline than on M-5's pipeline.

3. Programs executing on M-7 will always run faster than programs executing on M-5.

Answer: 1 is True and 2 and 3 are False.

Solution: 1. Throughput is only affected by a clock cycle, 2. Latency is defined by (# stages) * (longest stage time). For example, M-5's latency is 5 * (longest stage time) and M-7's latency is 7 * (longest stage time). 3. This is obviously false.

• An aid to determine the deadlock occurrence is: Resource allocation graph.

• Which of the following is (are) true about virtual memory systems that use pages?

1. The virtual address space can be larger than the amount of physical memory.

2. Programs must be resident in main memory throughout their execution.

3. Pages correspond to semantic characteristics of the program.

Answer: 1 is True and 2 and 3 are False.

• Which of the following is an efficient method of cache updating?

1. Snoopy writes 

2. Write through 

3. Write within 

4. Buffered write 

Answer: 1

Solution: the ability of cache controllers to observe the activity on the bus and take appropriate actions are called snoopy-cache technique. For performance reasons, it is important that the snooping function does not interfere with the normal operation of a processor and its cache.

• Increasing the number of buffers is likely to do which of the following?

1. Increase the rate at which requests are satisfied (throughput)

2. Change the likelihood of deadlock

3. Change the ease of achieving a correct implementation.

Answer: 1 is True and 2 and 3 are False.

• For the instruction load word (lw), we can get at most 2 page faults. We'll look into the page table, in the worst case, the page table may not be present in the memory as it is given in the question that "Page tables are not locked in memory and maybe swapped to disk". Therefore, we bring the page table which generates one page fault. Now, it could happen that the page containing lw word is not in memory so we bring it from the secondary memory which generates another page fault. Therefore, total 2 page faults. The above could be happened for Fetch and Execute phase.

• If L1 is a decidable language and L2 is an undecidable language, then L1 V L2, the union of L1 and L2, is 

Answer: Infinite, but possibly decidable and possibly undecidable

Solution: Decidable language can be finite or infinite. Undecidable language is always infinite. 

• Let G = (V, E) be a connected, undirected graph, and let a and b be two distinct vertices in V. Let P1 be the problem of finding the shortest path between a and b, and let P2 be the problem of finding a longest simple path between a and b. 

Answer: P1 can be solved in polynomial time but P2 is not known to be solvable in polynomial time (NP-complete problem이라고 알려짐. However, an exception is made for DAG. The longest path in a DAG can be solved in linear time.)

• One garbage collection algorithm is semispace copying collection. Which of the following characteristics of garbage collection apply to semispace copying collection?

1. Collects dead objects that reference each other

2. Incurs overhead on every assignment operation to a reference variable 

3. Avoids fragmentation

Answer: 1 and 3 are True and 2 is False.

• Of the following problems concerning a given undirected graph G, which is currently known to be solvable in polynomial time?

1. Finding the longest simple cycle in G 

2. Finding the shortest cycle in G 

3. Finding ALL spanning trees of G 

4. Finding the largest clique in G 

5. Finding a node coloring of G (where adjacent nodes receive distinct colors ) with the minimum number of colors.

Answer: 2

• TRUE or FALSE

1. Finding the shortest cycle in graph G (undirected graph) can be solvable polynomial time? ----> TRUE

2. The purpose of a compiler is to translate source code into machine code --> TRUE

3. Every finite language is decidable --> TRUE

4. Halting problem is undecidable --> TRUE