CS 584/684 Homework 2: Analysis, Trees, Dynamic Programming

Bart Massey
Due Thursday 1 May 2014 before class

Problems

1. Consider the following algorithm for reversing the elements of an array:

   ALGORITHM REVERSE D&C
   To reverse a 0-based array a:
       n ← |a|
       if n = 1
           return a
       m ← n div 2 - 1
       m′ ← m + 1
       if n is odd
           m′ ← m′ + 1
       reverse a[0..m]
       reverse a[m′..n - 1]
       for i in 0..m
           exchange a[i] with a[m′ + i]

   What is the time complexity of this algorithm? How does it compare with the time complexity of "naive" reverse? (CS 684 students: Implement and benchmark this algorithm.)

2. Consider balanced binary search trees T1 and T2 with integer keys, representing sets of integers. Give an algorithm for finding a balanced binary search tree that is the intersection of T1 and T2 that runs in time O(|T1|+|T2|). Hint: you might want to take the trees apart into ordered lists and put them back together again.

   [Exercise originally from The Structure and Interpretation of Computer Programs, as reported by an anonymous blogger.]

3. Consider the dual of the first problem described in the book. Instead of cutting rods for maximum profit, let's try buying rods at minimum cost. Assume that one can buy connectors of cost 2 that join two rods, and that rods are available for purchase at the prices listed in the following table (from the book).

Length	Cost
1	1
2	5
3	8
4	9
5	10
6	17
7	17
8	20
9	24
10	30

Give an algorithm using memoization or dynamic programming for efficiently finding the cost of a minimum-cost assembly for a rod of length n. Find the big-O worst-case complexity of your algorithm. (CS 684 students: Implement your algorithm, and show the minimum cost for assembling rods of length 1-30 given the above costs.)

Format

Your writeup may be in plain text. It is preferable to produce PDF or HTML. Try to make your writeup clear and readable. Document formats such as Word or OpenOffice are unacceptable. LaTeX is awesome, and you should learn how to use it anyhow, so PDF produced from that is best of all.

Submission

Submission is through http://crossgrade.svcs.cs.pdx.edu.