Introduction to Algorithms, 2022-3
Week 5: Exercises

1. Array Writes

Suppose that we run a sorting algorithm on an array with N elements that is already sorted. How many array writes will it perform if we use each of the following algorithms?

1. bubble sort

2. selection sort

3. insertion sort

2. Insertion Sort With Sentinel

a) Modify our implementation of insertion sort to eliminate the test 'j >= 0' in the inner loop, by first finding the smallest element in the array and moving it into the first position.

b) Perform an experiment to determine whether this change has a signficant effect on the algorithm's worst-case performance.

3. Binary Insertion

Suppose that we run an insertion sort on an input array whose values are all 0 or 1. The array contains N values.

a) What array of input values will be the worst case? What will be the worst-case running time?

b) What will be the expected (i.e. average) running time, if the values in the input array are all randomly either 0 or 1?

4. Merge Sort Visualization

Modify our merge sort implementation from the lecture so that it prints out each subarray as it sorts it recursively. Use indentation to show the hierarchical structure of the recursive calls. For example:

>>> a = [5, 2, 6, 8, 10, 1, 3, 17, 14, 4, 9]
>>> mergesort(a)
[5, 2, 6, 8, 10, 1, 3, 17, 14, 4, 9]
  [5, 2, 6, 8, 10]
    [5, 2]
      [5]
      [2]
    [6, 8, 10]
      [6]
      [8, 10]
        [8]
        [10]
  [1, 3, 17, 14, 4, 9]
    [1, 3, 17]
      [1]
      [3, 17]
        [3]
        [17]
    [14, 4, 9]
      [14]
      [4, 9]
        [4]
        [9]

5. Merge Sort Writes

Suppose that we run merge sort on an array that contains N elements. (If you like, you may assume that N is a power of 2.)

a) How many times will each array element be copied to a different memory location during the course of the sort?

b) How many array writes will the sort perform in all?

c) Does the running time of merge sort depend on the initial arrangement of the values that are being sorted? In particular, is it more efficient when run on an input array that is already sorted?

6. Merge Sort Memory

Consider the merge sort implementation that we saw in the lecture.

a) If we use it to sort an array that occupies N bytes of memory, what is the largest amount of additional memory that will be required at any moment during the sorting process? (Assume that any temporary arrays are freed as soon as there are no more references to them.)

b) Is it possible to modify our implementation to reduce this memory requirement?

7. Running Time

Consider this function:

def foo(n):
    if n == 0:
        return 0
    
    return foo(n // 2) + foo(n // 2)

a) For a given n, what value will the function compute?

b) Write down a recurrence for T(N), the time to run the function foo(N).

c) Solve the recurrence. Hint: Expand it into a tree as we did when we solved the recurrence for mergesort.

d) Suppose that we change the last line to

return 2 * foo(n // 2)

Clearly this will not change the value that the function computes. Will this modification change its big-O running time?