Jin Hyun Park / Qual Exam Prep / Sample questions

Sample questions

Questions in the style of the exam. Each one comes with the answer and, more importantly, the reason.

Which 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
Answer: (4) Selection sort.
Selection sort finds the smallest remaining element and swaps it into place, so it makes at most n − 1 swaps in total. The other three can swap far more often (insertion sort, for example, shifts elements one position at a time).
A cache has an access time of 30 ns and main memory has an access time of 150 ns. What is the average memory access time, assuming a hit ratio of 80%?
Answer: 60 ns.
On a hit (80% of the time) the cost is 30 ns. On a miss (20%) you pay for the cache lookup and the memory access, 30 + 150 = 180 ns. So the average is 0.8 × 30 + 0.2 × 180 = 24 + 36 = 60 ns.
What is the minimum number of two-input NAND gates needed to implement a two-input OR gate?
Answer: 3.
By De Morgan's law, A + B = ¬(¬A · ¬B). You need one NAND to make ¬A (tie both inputs to A), one to make ¬B, and one NAND of those two results.
At low multiprogramming levels, throughput increases as the multiprogramming level increases. Why?
Answer: because the potential for concurrent activity among system resources increases.
With more processes in memory, while one waits for I/O another can use the CPU, so the hardware sits idle less often.
At intermediate multiprogramming levels, the rate at which throughput increases begins to fall. Why?
Answer: because some system resource begins to saturate, i.e. reaches 100% utilization.
Once the CPU (or the disk, or memory) is already busy all the time, adding more processes cannot add more work per second.
Let A and B be two sets of strings over an alphabet Σ, and suppose B ⊆ A. Which of the following must be true?
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: only I.
A subset of a finite set is finite, so I holds. But II and III fail: Σ* is regular, and every language is a subset of Σ*, including non-regular and non-context-free ones. Being a subset says nothing about the complexity of the language.
Two processors, M-5 and M-7, implement the same instruction set. M-5 uses a 5-stage pipeline with a 10 ns clock cycle. M-7 uses a 7-stage pipeline with a 7.5 ns clock cycle. Which of the following is (are) true?
1. M-7's pipeline has better maximum throughput than M-5's.
2. The latency of a single instruction is shorter on M-7 than on M-5.
3. Programs on M-7 will always run faster than on M-5.
Answer: only I.
I: in a pipeline, one instruction finishes per clock cycle at best, so throughput is set by the clock cycle alone, and 7.5 ns is shorter than 10 ns. II: latency is (number of stages) × (cycle time): 5 × 10 = 50 ns on M-5 versus 7 × 7.5 = 52.5 ns on M-7, so M-7 is actually slower per instruction. III: a deeper pipeline suffers more from hazards and branch mispredictions, so "always" is false.
What tool helps determine whether a deadlock has occurred?
Answer: a resource allocation graph.
Processes and resources are nodes; requests and assignments are edges. A cycle in the graph is a necessary condition for deadlock (and a sufficient one if each resource has a single instance).
Which of the following is (are) true about virtual memory systems that use paging?
1. The virtual address space can be larger than physical memory.
2. Programs must be resident in main memory throughout their execution.
3. Pages correspond to semantic characteristics of the program.
Answer: only I.
The whole point of virtual memory is that a process can address more than what physically fits (I), because pages can live on disk and be brought in on demand (so II is false). Pages are fixed-size chunks that ignore program structure; it is segments that follow the program's logical units (so III is false).
Which of the following is an efficient method of keeping caches up to date?
1. Snoopy writes
2. Write through
3. Write within
4. Buffered write
Answer: (1).
In a snoopy cache, each cache controller watches ("snoops on") the shared bus and reacts when another processor writes to an address it holds a copy of. Done properly, this keeps caches coherent without slowing down the normal operation of the processor.
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: only I.
More buffers let producers and consumers get further out of step with each other, which improves throughput. The buffer count does not change the logic of the program, so neither deadlock behavior nor correctness is affected.
Page tables are not locked in memory and may be swapped to disk. How many page faults can a single load word (lw) instruction cause?
Answer: up to 2 per memory reference, so up to 4 for the whole instruction (with a single-level page table).
To translate any address you first need the page table. In the worst case the page-table page itself is on disk: one page fault. Then the page holding the target may also be on disk: a second page fault. An lw makes two memory references, the instruction fetch and the data load, so it can fault twice in the fetch phase and twice again in the execute phase. Read the question carefully: some versions ask per phase (answer 2), others per instruction (answer 4).
If L1 is a decidable language and L2 is an undecidable language, what can be said about L1 ∪ L2?
Answer: it is infinite, but it may be decidable or undecidable.
Every undecidable language is infinite (a finite language is always decidable, since you can list its members), so the union is infinite. Whether the union is decidable depends on the particular languages: for example, if L1 = Σ*, the union is Σ*, which is decidable.
Let G = (V, E) be a connected, undirected graph, and let a and b be two distinct vertices. P1 is the problem of finding a shortest path between a and b; P2 is the problem of finding a longest simple path between a and b. What is known about them?
Answer: P1 can be solved in polynomial time (BFS or Dijkstra), but P2 is NP-complete and is not known to be solvable in polynomial time.
The one exception worth remembering: on a directed acyclic graph, the longest path can be found in linear time by processing the vertices in topological order.
Which of the following apply to semispace copying garbage collection?
1. Collects dead objects that reference each other.
2. Incurs overhead on every assignment to a reference variable.
3. Avoids fragmentation.
Answer: I and III.
A copying collector starts from the roots and copies every reachable object to the other half of the heap. A cycle of dead objects is unreachable, so it is simply never copied (I). The copied objects end up packed together, so there is no fragmentation (III). Nothing happens on assignment; that is the cost of reference counting, not of copying collection (II is false).
Of the following problems on an undirected graph G, which is 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 proper node coloring of G with the minimum number of colors
Answer: (2).
The shortest cycle (the girth) can be found with a BFS from each vertex. Longest cycle, maximum clique, and minimum coloring are all NP-hard. Listing all spanning trees is not hard per tree, but a graph can have exponentially many of them, so the output alone can be exponential in size.
True or false?
- Finding the shortest cycle in an undirected graph can be done in polynomial time. True.
- The purpose of a compiler is to translate source code into machine code. True.
- Every finite language is decidable. True. A finite list can always be checked.
- The halting problem is undecidable. True.

Overview · Useful materials · Algorithms · Architecture · OS · Networking · Databases · Automata · AI / ML · Things to remember