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.
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.
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.
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.
bubble sort
selection sort
insertion sort
mergesort
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?
bubble sort
selection sort
insertion sort
mergesort
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.
Describe an algorithm that you can use to find your car 100% of the time.
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?
Give an exact upper and lower bound on your algorithm's running time, as a function of D.
Solve Project Euler's problem 5:
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?