1. Why is Insertion sort’s runtime O(n) if the list is sorted? Why is Bubble sor
ID: 3719346 • Letter: 1
Question
1. Why is Insertion sort’s runtime O(n) if the list is sorted? Why is Bubble sort’s runtime O(n2) 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)?
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)
Explanation / Answer
1.
If list is sorted then number of inversions will be decreased. No swaps required.
Only one comparison is required to test whether element at correct position in the list.
So, total elements present in the list are n, then required comparisons are n-1.
Using asymptotic complexity this O(n)
Bubble sort blindly go through the comparisons and swaps. Yes, there is no swaps if list is sorted.
Number of comparisons are n*(n-1)/2.
Using asymptotic complexity, it is O(n^2)
2)
Task
Algorithm
Sorted/Un-sorted?
Find the minimum value.
Selection sort
Yes
Find the maximum value.
Selection sort
Yes
Compute the arithmetic mean
Take each element and calculate sum of all elements and divide it by total number of elements
Doesn’t depends on order of elements
Find the median (i.e., the middle value)
Quick sort or merge sort is if list is unsorted.
If sorted go for binary search
Binary search is better if list is sorted
Find the mode (i.e., the value that appears the most times)
Counting sort
Doesn’t depends on order of elements
3)
The total storage is approximately 675MB
15 surfaces.
Each surface has 612 tracks;
144 sectors/track
512 bytes/sector
8 sectors/cluster.
The disk turns at 3600 rpm.
The tract-to-track seek time is 20ms,
the average seek time is 80ms.
there is a 360KB file on the disk.
Number of Sectors need to be accessed for the file = 360KB/512B
= 720
Time required to access the sector= seektime+rotational delay+ transfer time
Rotational delay:R/2
60sec -> 3600 rotations
? -> 1 rotation
R/2 =>1/120 sec
Transfer time is considered negligible as doesn’t mention anything in the question.
Time required to access the sector= ( 80 ) + ( 1/120 ) => 80.008 sec
Time needed to access the file= 720*(80.008)
= 57606 sec
Assume that the first track of the file is randomly placed on the disk, that the entire file lies on adjacent tracks:
Number of tracks required to access the file= 360KB/(15*612*144*512)B => 1
So, time required to access the file= 80 + (1/120)*720 = 86 sec
4)
a)
5
10
4
6
8
d)
10
4
6
8
5
e)
7
4
12
2
5
Task
Algorithm
Sorted/Un-sorted?
Find the minimum value.
Selection sort
Yes
Find the maximum value.
Selection sort
Yes
Compute the arithmetic mean
Take each element and calculate sum of all elements and divide it by total number of elements
Doesn’t depends on order of elements
Find the median (i.e., the middle value)
Quick sort or merge sort is if list is unsorted.
If sorted go for binary search
Binary search is better if list is sorted
Find the mode (i.e., the value that appears the most times)
Counting sort
Doesn’t depends on order of elements
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.