Introduction to Algorithms, 2021-2
Week 6: Exercises

1. Ascending and Descending

Write a function that takes a list of integers 'a' that is guaranteed to contain a strictly increasing sequence of values followed by a strictly decreasing sequence. For example, the integers might be

   4, 8, 10, 20, 37, 50, 52, 48, 7

It's guaranteed that the values will increase at least once and decrease at least once.

Your function should find and return the largest value in the list. It must run in sub-linear time.

2. Bubble Sort Performance

Write a program that, for every N in the set { 1000, 2000, …, 10000 } generates an array with N random numbers in the range from 1 to N, then sorts the array using a bubble sort. For each N, write an output line with the number N and the number of milliseconds that the sort took to run.

3. Bubble Sort Graph

Using a graphing utility such as Gnuplot, graph the data from the previous exercise, with N on the X axis and the number of milliseconds on the Y axis.

4. Sort Performance

Extend the graph from the previous exercise to include the running time of selection sort, insertion sort and merge sort on arrays of random numbers of the same size.

5. Array Writes

Suppose that we run a sorting algorithm on an array that is already sorted. How many array writes will it perform if we use each of the following algorithms? An answer in big-O notation is acceptable.

  1. bubble sort

  2. selection sort

  3. insertion sort

6. Number of Moves

Suppose that we sort an array of distinct integers of length N, and that initially the largest integer is at the beginning of the array. How many times will this integer move to a new array position if we use each of the following algorithms?

  1. bubble sort

  2. selection sort

  3. insertion sort

7. Lost Car

You are standing on a straight road that goes infinitely far in both directions. You remember that you parked your car somewhere on this road, but you don't know how far away it is or in which direction it is.

  1. Describe an algorithm that you can use to find your car 100% of the time.

  2. Let D be the distance from the start point to your car. What is your algorithm's best-case and worst-case asymptotic running time, as a function of D?

  3. Give an exact upper and lower bound on your algorithm's running time, as a function of D.