1. Why is Insertion sorts runtime O(n) if the list is sorted? Why is Bubble sorts runtime O(n²) regardless of the sorted condition of the list?

2. Specify which operations run best when the list is sorted. Then briefly describe an algorithm to implement each operation using a list organized in the optimal way. (10%)

Task	Algorithm	Sorted/Un-sorted?
Find the minimum value.
Find the maximum value.
Compute the arithmetic mean
Find the median (i.e., the middle value)
Find the mode (i.e., the value that appears the most times)

3. Assume a disk drive from the late 1990s is configured as follows. The total storage is approximately 675MB divided among 15 surfaces. Each surface has 612 tracks; there are 144 sectors/track, 512 bytes/sector, and 8 sectors/cluster. The disk turns at 3600 rpm. The tract-to-track seek time is 20ms, and the average seek time is 80ms. Now assume that there is a 360KB file on the disk. On average, how long does it take to read all of the data in the file? Assume that the first track of the file is randomly placed on the disk, that the entire file lies on adjacent tracks, and that the file completely fills each track on which it is found. A seek must be performed each time the I/O head moves to a new track. Show your calculations. (10%)

4. Assume that a virtual memory is managed using a buffer pool. The buffer pool contains five buffers and each buffer stores one block of data. Memory accesses are by disk block ID. Assume the following series of memory accesses takes place:

5 2 5 12 3 6 5 9 3 2 4 1 5 9 8 15 3 7 2 5 9 10 4 6 8 5

For each of the following buffer pool replacement strategies, show the contents of the buffer pool at the end of the series, and indicate how many times a block was found in the buffer pool (instead of being read into memory). Assume that the buffer pool is initially empty. (20%)

a. First in, first out.

b. Least frequently used (with counts kept only for blocks currently in memory, counts for a page are lost when that page is removed, and the oldest item with smallest count is removed when there is a tie).

c. Least frequently used (with counts kept for all blocks, and the oldest item with the smallest count is removed when there is a tie).

d. Least recently used.

e. Most recently used (replace the block that was most recently accessed).

5. Assume that the values A through H are stored in a self-organizing list, initially in ascending order. Consider the three self-organizing list heuristics: count, move-to-front, and transpose. For count, assume that the record is moved ahead in the list passing over any other record that its count is now greater than. For each, show the resulting list and the total number of comparisons required resulting from the following series of accesses: (20%)

D H H G H E G H G H E C E H G

6. Answer the following:

a. Explain how open hash tables handle collisions? b. Explain how closed hash tables handle collisions?

c. What is the difference between linear probing and improved linear probing (double hashing)?