SUNY Geneseo Department of Computer Science

Problem Set 3—Depth First Search

CSci 242, Spring 2013

Prof. Doug Baldwin

Due Wednesday, February 6

Purpose

This exercise reinforces your understanding of depth first search.

Background

For background on depth first search, see section 22.3 of our textbook, or the January 31 lecture notes.

Exercise

Solve each of the following problems.

Problem 1

Carry out a depth first search on the following graph by hand, starting at vertex A. Show the timestamps computed for every vertex and the classification assigned to each edge.

Directed graph on 8 vertices

Problem 2

Exercise 22-3.12 in the textbook. Explain why the algorithm you devise is correct (the explanation should be convincing, but needn’t be a completely rigorous proof).

Problem 3

Exercise 22.3-1 in the textbook, for directed graphs only.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look over your solutions, ask any questions I have about them, answer any questions you have, etc. Even though we will have a chance to talk about your solutions, please bring them in writing to the meeting—that will speed things along.

Each meeting should take about 15 minutes. Please schedule your meeting by signing up on the schedule sheet outside my office or electronically via Google calendar. If you work in a group on this exercise, the whole group can have a single meeting with me. Make sure that your meeting ends by the end of the day on the due date above.