Breadth First Search(BFS) Idea: Explore relatives at same level before their children Explore relatives left to right Snas witha, Spring 03 Elements of algorithm design Description stylized pseudo code, sufficient to analyze and implement the algorithm Analysis: · Soundness: is a solution returned by the algorithm guaranteed to be correct is the algorithm guaranteed to find a solution when there is one? T ow long does it take to find a solution Space complexity how much memory does it need to perform search? Bran withams, Spring 03 1313 Brian Williams, Spring 03 26 Breadth First Search (BFS) S D A B C G C G D C G Idea: •Explore relatives at same level before their children •Explore relatives left to right 1 2 4 8 9 5 3 6 10 11 7 S A D C G C B D C G G Brian Williams, Spring 03 27 Elements of Algorithm Design Description: – stylized pseudo code, sufficient to analyze and implement the algorithm. Analysis: • Soundness: – is a solution returned by the algorithm guaranteed to be correct? • Completeness: – is the algorithm guaranteed to find a solution when there is one? • Time complexity: – how long does it take to find a solution? • Space complexity: – how much memory does it need to perform search?