## HW 2: Analysis, Trees, Dynamic Programming

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

Bart Massey

Due Thursday 1 May 2014 before class

### Problems

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.)

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.]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.