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

Assignment #9
Due Thursday, 24 April

Note the revised due date listed above.

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

• Problem 9.15 on page 321.

• Problem 9.23 on page 322.

• Problem 9.27 on page 322.

• Choose one of problem 9.16 on page 321, 9.29 on page 323, 9.42 on page 324, or the following problem.

  Suppose that an arithmetic expression is given by a directed acyclic graph similar to that shown in Figure 9.7 on page 300. Assume that the internal nodes of the graph hold addition, subtraction, multiplication, and division operations and that the leaves (i.e., those with no successors) hold integer constants. Devise an efficient (i.e., O(n)) algorithm for evaluating the expression graph.

UP to ENGR 691 assignments document?