Class Notes: COP3530

Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Homework #5 -- Due Wed 30 June 1999 : 09.30am Revised Date

In class, we discussed the breadth-first and depth-first search (BFS and DFS) algorithms for graph traversal. Using your class notes and the text (Chapter 12) as a guide, answer the following questions.

Note: These questions are not meant to be busywork, but are presented to help you develop your thinking and analysis capabilities re: graph traversal. One or more questions like this are likely to appear on Exam #2 or on the Final Exam.

Question 1. Write pseudocode (not Java code) for the BFS algorithm we discussed in class. Beside each step, write the number of external I/O, memory I/O, incrementation, comparison, and other types of operations employed. Then, construct a work budget for each type of operation, together with a Big-Oh estimate of complexity.
Question 2. Repeat Question 1 for the DFS algorithm that we discussed in class.
Question 3. Given the following graph specification (assume directed edges only) for G = (V,E), write out the order in which BFS visits the vertices, starting at vertex a (2 points total):
Analyze the complexity of each case ((a) and (b), above) by constructing a work budget for each step of the traversal (2 points total).
Question 4. Repeat Question 3 with b as the start vertex.
Question 5. Repeat Question 3 for DFS instead of BFS.
Question 6. Repeat Question 4 for DFS instead of BFS.

Note: Ask the TAs if you have questions about the homework. You must complete the homework by yourself, but you can work together on general approaches to solving the homework problems. Show your work to get full credit. Any copying will be construed as cheating.