CSC 344
Homework 2

Assigned Feb. 17, due Mar. 3

You have eight problems, and 14 days to do them.

As you're doing these, think of which one you'd like to present in class, and let me know as soon as you've decided. Solutions will be presented in class March 3 and 5.

• Shaffer 3.5: How do processor speed and asymptotic complexity affect how large a problem instance you can solve in a given length of time?
• Shaffer 3.11: Which function is asymptotically faster-growing, or are they asymptotically equivalent?

• Here's a silly way to sort a bunch of numbers: generate each of the possible permutations of the numbers, and for each one, test whether it's in order.

  Analyze this algorithm: tell how long it takes, as a function of how many numbers there are, using big-O notation.

• A slightly less-silly way to sort: for each number, count how many of the other numbers are less than it, and use this count to put it into the right location in an array. Then read off the array from beginning to end.

  Analyze this algorithm: tell how long it takes, as a function of how many numbers there are, using big-O notation. Do you see any significant limitations of this algorithm? Can you fix them?

• CLRS problem 4-5 (chip-testing, at the end of the chapter)

• From another textbook: Suppose you have a bunch of numbers stored in two n-element sorted arrays, and you want to find the n-th smallest element (i.e. approximately the median) of the combined collection of numbers. You have random (read) access to the arrays, so you can get the k-th smallest element from either array in constant time.

  Give an algorithm to find the median of the combined collection of numbers in O(log(n)) time.

• From another textbook: Suppose you have a bunch of identical glass jars, and you want to find out (to the nearest foot) how long a drop they can take without breaking. Assume that whether they break is unaffected by wind, temperature, angle, history of previous non-breaking drops, etc.; it's solely determined by the height of the drop.

  1. What are the relevant resources in this problem? Choose appropriate cost measures for evaluating algorithms to solve this problem. What is an appropriate “size” parameter?
  2. Describe an algorithm (in pseudocode), as efficient as you can, to find the answer using only one glass jar. How long does it take, as a function of the size parameter?
  3. Describe an algorithm, as efficient as you can, to find the answer using an unlimited supply of glass jars. How long does it take, and how many jars does your algorithm actually use, as functions of the size parameter?
  4. Describe an algorithm, as efficient as you can, to find the answer using exactly 2 glass jars. How long does it take?
  5. Describe an algorithm, as efficient as you can, to find the answer using exactly 3 glass jars. How long does it take?
  6. Describe an algorithm to find the answer using exactly k glass jars, for an arbitrary positive integer k. How long does it take? Is the answer for larger values of k asymptotically faster than for smaller values of k?

• Implement (in a language of your choice) a data structure for matrices that allows you to extract contiguous sub-matrices (say, rows 3-6 and columns 4-8 of a given matrix) in constant time.

  Next, implement (in the same language) three different algorithms for matrix multiplication:

  • the "obvious" algorithm, in which each cell of the answer is computed as the dot-product of a row of the first matrix with a column of the second matrix;
  • the "simple divide and conquer" algorithm described in section 4.2 of CLRS; and
  • Strassen's modified divide-and-conquer algorithm, also described in section 4.2 of CLRS.
  Be sure to use the same language and data structure for all three algorithms, so we can compare them meaningfully. Design things so that you can easily measure the CPU time taken by each call to your matrix-multiply function. For the two divide-and-conquer algorithms, you may assume for simplicity that the matrix size is a power of 2.

  Run all three algorithms on random matrices of a variety of (power-of-2) sizes.
  Check that all three algorithms produce the same answer (or, if you're using floating-point, very close to the same answer).
  Tabulate the CPU time taken by each algorithm at each input size? What conclusions can you draw?