{\rtf1\ansi\deff0\adeflang1025
{\fonttbl{\f0\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f1\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f2\fnil\fprq2\fcharset0 HG Mincho Light J;}{\f3\froman\fprq2\fcharset0 Times New Roman;}{\f4\fswiss\fprq2\fcharset0 Arial;}{\f5\fnil\fprq2\fcharset0 Arial Unicode MS;}}
{\colortbl;\red0\green0\blue0;\red0\green0\blue128;\red128\green128\blue128;}
{\stylesheet{\s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\snext1 Default;}
{\s2\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext2 Text body;}
{\s3\sb240\sa120\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs28\lang1033\sbasedon1\snext2 Heading;}
{\s4\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs28\lang1033\b\sbasedon1\snext1{\*\soutlvl0} Heading 1;}
{\s5\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs24\lang1033\i\b\sbasedon1\snext1{\*\soutlvl1} Heading 2;}
{\s6\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs24\lang1033\sbasedon1\snext1{\*\soutlvl2} Heading 3;}
{\s7\sb240\sa60\keepn\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs24\lang1033\b\sbasedon1\snext1{\*\soutlvl3} Heading 4;}
{\s8\sb240\sa60\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs22\lang1033\sbasedon1\snext1{\*\soutlvl4} Heading 5;}
{\s9\sb240\sa60\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs22\lang1033\i\sbasedon1\snext1{\*\soutlvl5} Heading 6;}
{\s10\li360\ri0\fi-360\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext10 List;}
{\s11\li720\ri0\fi-360\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext11 List 2;}
{\s12\li1080\ri0\fi-360\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext12 List 3;}
{\s13\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext13 Header;}
{\s14\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext14 Footer;}
{\s15\sb240\sa60\cf1\qc{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs32\lang1033\b\sbasedon1\snext16 Title;}
{\s16\sa60\cf1\qc{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f4\fs24\lang1033\sbasedon1\snext2 Subtitle;}
{\s17\li360\ri0\fi1\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext17 WW-List Continue;}
{\s18\li360\ri0\fi1\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext18 WW-Body Text 2;}
{\s19\li360\ri0\fi1\sa120\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon18\snext19 WW-Body Text 3;}
{\s20\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext20 Normal;}
{\s21\li720\ri0\fi0\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\sbasedon20\snext21 Body Text 2;}
{\*\cs23\cf1{\*\updnprop5801}\up10\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\fs24\lang1033\sbasedon27 Footnote Characters;}
{\*\cs24\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\fs24\lang1033 Page Number;}
{\*\cs25\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\fs24\lang1033 Numbering Symbols;}
{\*\cs26\cf2\ul\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\fs24\lang1033 Internet Link;}
{\*\cs27\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\fs24\lang1033 WW-Absatz-Standardschriftart;}
{\*\cs28\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\lang1033 WW-Absatz-Standardschriftart1;}
{\*\cs29\cf1{\*\updnprop5801}\up10\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\lang1033\sbasedon28 WW-Footnote Symbol;}
{\*\cs30\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\lang1033 WW-Default Paragraph Font;}
{\*\cs31\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\lang1033 WW-Page Number;}
{\*\cs32\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\lang1033\sbasedon30 WW-Page Number1;}
{\*\cs33\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f0\lang1033\b\sbasedon30 WW-Strong;}
}
{\info{\title 132hw11 - s03}{\author Sharon Tuttle}{\creatim\yr2001\mo1\dy23\hr10\min30}{\operator Sharon Tuttle}{\revtim\yr2003\mo5\dy3\hr2\min4}{\printim\yr2003\mo1\dy28\hr11\min42}{\comment StarWriter}{\vern6410}}\deftab720
{\*\pgdsctbl
{\pgdsc0\pgdscuse195\pgwsxn12240\pghsxn15840\marglsxn1440\margrsxn1440\margtsxn720\margbsxn720\headery0{\*\headeryb283\headerxl0\headerxr0\headeryh0}{\header \pard\plain \s13\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\ltrch\loch\fs12 {\ltrch\loch\f3 CIS 132 - HW #11\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 1}}}
\par {\ltrch\loch\f3 Spring 2003}
\par }
\pgdscnxt0 Default;}}
\paperh15840\paperw12240\margl1440\margr1440\margt720\margb720\sectd\sbknone\pgwsxn12240\pghsxn15840\marglsxn1440\margrsxn1440\margtsxn1303\margbsxn720\headery720{\header \pard\plain \s13\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\ltrch\loch\fs12 {\ltrch\loch\f3 CIS 132 - HW #11\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 1}}}
\par {\ltrch\loch\f3 Spring 2003}
\par }
\ftnbj\ftnstart1\ftnrstcont\ftnnar\aenddoc\aftnrstcont\aftnstart1\aftnnrlc
\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\qc{\*\tlswg8236}\tx6300\ltrch\loch\fs22\b {\ltrch\loch\f3 HUMBOLDT STATE UNIVERSITY}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\qc\ltrch\loch\fs22\b {\ltrch\loch\f3 CIS 132 - Introduction to Computer Science II - Spring 2003}
\par {\ltrch\loch\f3 Homework #11 - due Friday, May 9th,  4:30 pm}
\par {\ltrch\loch\f3 Graphs}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033{\*\tlswg8236}\tx1260\ltrch\loch\fs22\b 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af2\afs24\langfe255\loch\f3\fs20\lang1033\li360\ri0\fi-360{\*\tlswg8236}\tx6660\ltrch\loch\f3\fs22 {\ltrch\loch\f3 Along with this handout on the course web page is a buggy adjacency list graph implementation. You do not want to remove vertices or edges --- but adding vertices and edges *seems* to work, based on *limited* testing. Note that the toString() method shows 
each edge twice ((B, A) and (A, B), if there's an edge from A to B).}
\par 
\par {\ltrch\loch\f3 To class {\b Cs132AdjListGraph}, add a method {\b buildDepthFirstKeyList(Cs132Vertex vert)} --- it should return an array of type {\b Comparable}, containing the keys of the graph's vertices reachable from {\b vert }in a {\b depth}-first-search ordering starting at vertex {\b vert}. (Y
ou may use either the recursive or the stack-based algorithm.) (Note that you'd add the vertex's key to the array when you mark that vertex as visited...)}
\par 
\par {\ltrch\loch\f3 (Add a test method for {\b buildDepthFirstKeyList()} to {\b Cs132AdjListGraphTest}, also, of course. But note that some special required tests are needed this time --- see below.)}
\par 
\par {\ltrch\loch\f3 Also to class {\b Cs132AdjListGraph, }add a method {\b buildBreadthFirstKeyList(Cs132Vertex vert)} --- yup, it should return an array of type {\b Comparable}, also, except it contains the keys of the graph's vertices reachable from {\b vert} in a {\b breadth}-first-search ordering
 starting at vertex {\b vert}. }
\par 
\par {\ltrch\loch\f3 (And add a test method for {\b buildBreadthFirstKeyList()} to {\b C132AdjListGraphTest()}, also, again noting the special additional requirements below.)}
\par 
\par {\ltrch\loch\f3 Note that, when you are testing these, you {\b must }{\b0 i}nclude at {\b least} the following tests:}
\par {\ltrch\loch\f3 *\tab create at least one {\b unconnected} graph of at least {\b 6} vertices, with at least{\b  3} vertices in each connected component. Test using this graph at least twice for each of the two new methods, using a vertex from at least two different connected components.}
\par 
\par {\ltrch\loch\f3 *\tab create a graph corresponding to the following:}
\par 
\par {\ltrch\loch\f3 \tab G = \{V = (A, B, C,  D, E, F, G, H, I, J, K),}
\par {\ltrch\loch\f3                E = ((A, B), (A, C), (A, F), (B, D), (B, E), (C, G), (C, H), (D, K), (E, G), (E, I), (F, J))}
\par {\ltrch\loch\f3               \}}
\par 
\par {\ltrch\loch\f3 \tab (you can make the values for the vertices with the above keys whatever you'd like...)}
\par 
\par {\ltrch\loch\f3 \tab Test using this graph and vertex with key {\b A} for both {\b buildDepthFirstKeyList() {\b0 and }buildBreadthFirstKeyList()}.}
\par 
\par {\ltrch\loch\f3 \tab (be sure to include {\b expected()} calls for all of these tests, as usual, of course --- THIS TIME, there's special {\b partial} {\b credit} if you give an accepted depth-first and breadth-first ordering (respectively) for this graph in your expected() calls for these 
methods for this graph, even if your methods do not work, because I want to see if you can do a bf-ordering and df-ordering "by hand". Yup, doing such an activity definitely could show up on the final...)}
\par 
\par {\ltrch\loch\f3{\b0 You are permitted to improve toString() in Cs132AdjListGraph if you like --- you may also correct any bugs you find in the provided files.}}
\par 
\par {\ltrch\loch\f3 Turn in your resulting Cs132AdjListGraph.java and Cs132AdjListGraphTest.java along with copies of the text console contents from running the new test methods within your Cs132AdjListGraph{\*\bkmkstart DDE_LINK1}{\*\bkmkend DDE_LINK1}Test class.}
\par }