Engr 691-13: Special Topics on Analysis of Algorithms
Jackson Computer Engineering & Telecommunications Program
Spring Semester 1997

Assignment #8
Due Thursday, 17 April

Note the revised due date listed above.

Do the following exercises from chapter 8 of the Brassard and Bratley textbook:

• Problem 8.18 on page 279.

• Problems 8.21 and 8.22 on page 280. Implement and test a program (in a language of your choice) for these algorithms.

• (Optional) Problem 8.32 on page 281.

• (Optional) A certain string-processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks are made can affect the total amount of time used.

  For example, suppose we wish to break a 20-character string after characters 3, 8, and 10 (numbering the characters in ascending order from the left end, starting from 1). If the breaks are made in a left-to-right order, then the first break costs 20 units of time, the second break costs 17 units of time, and the third break costs 12 units of time, a total of 49 units of time. If the breaks are made in a right-to-left order, then the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of 38 units of time.

  Devise a dynamic programming algorithm that, when given the numbers of the characters after which to break, determines the cheapest cost of those breaks in time O(n^3).

UP to ENGR 691 assignments document?