CSC 321 Spring 2002

Assignment 1

Due: Monday, April 8^th

Write up solutions to each of the following problems:

1. Problem 1.2-2 (p. 13 in CLRS) [The point of this problem is that, even though insertion sort may be faster for small values of n, there is a point at which merge sort becomes faster.]
   
2. Problem 2.1-3 (p. 21 in CLRS) [Refer back to the material on p. 18.]
   
3. Problem 2.2-3 (p. 27 in CLRS)
   
4. Prove the following, using the definition of Big-O (which means you need to give a constants c>0 and n₀):
   • n³-7n + 12  =  O(n³ ).
   • 11n²+32n+14  =  O(n² ).
     
5. You are writing a program to provide driving directions.  You start with the simple case of driving along Interstate 55 (otherwise known as the Stevenson Expressway in Chicago).  You have a list of cities along I55: Chicago, Downers Grove, Bolingbrook, Plainfield, Joliet, Channahon, etc.  You know the distance from each city to the next one on the list.  You want to be able to determine the distance between any pair of cities. 
   
   Assuming there is a total of n cities, one way to do this is to have an array D where D[k] is the distance from city k to city k+1.   To find the distance from city i to city j, add up the entries from D[i] to D[j-1].  This approach requires O(n) space and, in the worst case, O(n) additions.  
   
   Another way is to have an n by n table T where T[i,j] is the distance from city i to city j and perform a look-up.  This approach requires O(n²) space and O(1) look-ups.
   
   Your task is to find a method that requires O(n) space and O(1) operations.