COP 3530, Discrete Data Structures and Algorithms, Summer 1999, Homework 5 :: UFL Florida Computer Programming Homework

Class Notes: Data Structures and Algorithms Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344 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: Answers are in blue typeface. * 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. Answer: Psudeocode for BFS is given for a graph having n vertices and m edges, as follows: procedure: Breadth-first-search(w) { initialize list L0 to contin vertex w # 2 mem I/O i = 0 # 1 mem I/O while not(isEmpty(Li)) do # n-1 comps { create Li+1 = empty list # 1 mem I/O for each vertex v in Li do # n iterations max. { for each edge e incident on v do # m iter's max.