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

Class Notes Data Structures and AlgorithmsSummer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344Homework 5 -- Due Wed 30 June 1999 09.30am Revised DateIn 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 spot 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 iters max.