CSC 344
Homework 1

Assigned Feb. 8, due Feb. 18

There are eleven problems, and ten days to do them. Try to do at least two problems a day, so you have some leeway.

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.

• Shaffer 1.15: algorithms for parenthesis nesting
• Shaffer 1.19: algorithms for max, second-max, third-max, median
• Shaffer 2.47: how long does it take to visit your in-laws?
• CLRS 1.2-2 and 1.2-3: when is an asymptotically "slower" algorithm actually faster?
• Shaffer 2.28: induction proof
• CLRS 2.3-3: prove by induction the exact solution to a recurrence
• Shaffer 2.34: solve a recurrence exactly, and prove by induction that your solution is correct
• Shaffer 3.4: 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?

• 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?