Computer Science 477/677: Design and Analysis of Algorithms

Spring 1999

Homework Assignment 7.

Due April 26, 1999

You may discuss this assignment with other students in the class, or other persons. But you must actually write the assignment in your own hand. You must turn in the homework on letter-sized paper, with your name at the top of each page. Use pen or pencil, any color.

Do not write your homework as a computer file and turn in a printout.

• Work exercise 23.1-5 on page 468 of your textbook.
• Work exercise 23.2-1 on page 476 of your textbook.
• On page 478 there is a recursive algorithm for DFS. Write a DFS algorithm in pseudocode that is not explicitly recursive, and uses finite memory except for just one stack.
• Work exercise 23.4-3 on page 488 of your textbook.