ࡱ> NM$( / 0LDTimes New RomanL2bbv 0b( 0 ` .  @n?" dd@  @@`` LDt`     c $@7 uʚ;2Nʚ;g43d3dv 0b:ppp@ <4!d!d` 0b8 2b<4dddd` 0b8 2b? %O =CSC-141 Lecture 30Review for the Final ExamSections Covered Since MT26.4  A Shortest-Path Algorithm. 6.5  Representations of Graphs. 6.6  Isomorphisms of Graphs. 6.7  Planar Graphs. (7.1  Introduction to Trees.) 7.2  Teminology and Characterizations of Trees. 7.3  Spanning Trees. 7.4  Minimal Spanning Trees. (10.1  Sequential Circuits and Finite State Machines.) 10.2  Finite-State Automata. OZN,G E :6.4  Shortest Path Algorithm@You should be able to perform iterations of Dijkstra s Algorithm graphically, like figures 6.4.1 through 6.4.5. In other words, you should understand how the algorithm works, not the actual algorithm. You should also understand the concept, and issues associated with, a greedy algorithm.*! , <6.5  Representation of GraphsYou should be able to represent a graph as an adjacency matrix or an incidence matrix. You should be able to convert between adjacency matrices and incidence matrices for graphs. You should be able to convert from an adjacency or incidence matrix to a graph.86.6  Isomorphisms of Graphs  You should be able to determine if two graphs are isomorphic. If they are not, you should be able to cite an invariant that proves this.&6.7  Planar GraphsTYou should be able to redraw a simple graph so none of the edges cross. You should understand the Euler s Formula: f = e  v + 2. You should be able to perform series reduction of a graph. You should be able to eliminate edges to attempt to transform a graph into K5 or K3,3 (Kuratowski s Theorem).+Zs  ,b   @7.2  Characterizations of TreesUnderstand the basic terminology, like height, root, terminal, level, parent, child, ancestor, descendent, etc. Given a spanning tree for a graph, you should be able to answer simple questions about that tree: parents of a, children of j, height of the tree, level of vertex c, etc.H& (7.3  Spanning TreesfYou should understand the difference between breadth-first and depth-first search. Given a graph G, you should be able to: Determine a spanning tree using breadth-first search. Determine a spanning tree using depth-first search. It is not so important to know the actual algorithm, but rather how the algorithm works. Process vertex a. Process vertex c. etc.{ZjZYZ)Z-  jY) 87.4  Minimal Spanning TreesGiven a graph G, you should be able to find a minimal spanning tree, step by step, using Prim s Algorithm and Kruskal s Algorithm. In the case of Prim, you will be given a starting vertex, and should show the progression of addition of edges towards the minimal spanning tree. In the case of Kruskal, you should show the progression of addition of edges towards the minimal spanning tree. In other words, you should know how the algorithms work, not necessarily the actual algorithms..ZbZb>Y   810.1  Finite State MachinesYou should understand how to distinguish FSMs from FSAs and convert back and forth. You should know what six elements comprise a FSM (I, O, S, f, g, and s0) and be able to convert between these six elements, the state table, and the state diagram. $^,)  810.2  Finite State AutomataYou should know what five elements comprise a FSA (I, S, f, A, and s0) and be able to convert between these five elements, the state table, and the state diagram. You should be able to tell whether or not a given FSA will accept an input string, what the output string will be, and what the state transition path is. You should also be able to identify whether a given diagram represents a valid FSA or not.*D S  ProbabilityYou should be able to determine the sample space S for something, be it a deck of cards, dice, roulette wheel, or spinners. (Wheel of Fortune comes to mind.) You should be able to determine the probability of an element of the sample space. You should be able to determine the subset that represents an event A (drawing a black card, rolling an even number, etc.). You should be able to determine the probability for an event, and for both independent and dependent events.@1 Probability ExampleA box contains 36 apples. 25% of the apples are rotten or otherwise inedible, and the apples are evenly distributed within the box. If you reach into the box with your eyes closed (or in the dark), what is the probability that the apple you pick will be rotten? By inspection, it is but I want you to work it out a bit more thoroughly, something like: P(Bad) = 0.25 x 36 / 36 = 9/36 = .*b#/l     ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> (    652 "P 2 T Click to edit Master title style! !$  0`PR " 2 RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0SR "`` 2 >*  0WR "`  R @*  0[R "`  R @*H  0޽h ? ̙33 $Blank Presentation0 zr< (  < < 0 R P   R P*   < 08    8 R*  d < c $ ?  8 < 08  @ 8 RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S < 6X8 `P  8 P*   < 6H8 `  8 R*  H < 0޽h ? ̙33 @8(  @ @ 08 P   8 >*  @ 0N7    7 @*  @ 67 `P  7 >*  @ 6!6 `  6 @* H @ 0޽h ? ̙33  $(  r  S nRp R r  S  sR `   R H  0޽h ? ̙33  0 $(   r  S RP  R r  S  R R H  0޽h ? ̙33  @$(  r  S RP  R r  S T^R R H  0޽h ? ̙33  P$(  r  S NP  R r  S X~N N H  0޽h ? ̙33  `$(  r  S hRP  R r  S `7 7 H  0޽h ? ̙33  p$(  r  S (7P  R r  S ,7 7 H  0޽h ? ̙33   $(   r  S 7P  R r  S g7 7 H  0޽h ? ̙33  $$(  $r $ S 37P  R r $ S h6 6 H $ 0޽h ? ̙33  ($(  (r ( S ́NP  R r ( S [7 7 H ( 0޽h ? ̙33   ,$(  ,r , S NP  R r , S Z6 6 H , 0޽h ? ̙33   0$(  0r 0 S {RP  R r 0 S C7 7 H 0 0޽h ? ̙33   4$(  4r 4 S 8NP  R r 4 S <)6 6 H 4 0޽h ? ̙33   8$(  8r 8 S ~7P  R r 8 S m6 6 H 8 0޽h ? ̙330 D(  DX D C <   6 D S hk6< @  6  H D 0޽h ? ̙330  H(  HX H C <   6 H S P 6< @  6  H H 0޽h ? ̙330 0L(  LX L C <   6 L S 6< @  6  H L 0޽h ? ̙330 @P(  PX P C <   6 P S 6< @  6  H P 0޽h ? ̙330 PT(  TX T C <   6 T S 6< @  6  H T 0޽h ? ̙330 `X(  XX X C <   3 X S 3< @  3  H X 0޽h ? ̙330 p\(  \X \ C <   6 \ S u6< @  6  H \ 0޽h ? ̙330 `(  `X ` C <   3 ` S 3< @  3  H ` 0޽h ? ̙330 d(  dX d C <   3 d S 3< @  3  H d 0޽h ? ̙33 0 h(  hX h C <   3 h S ܫ3< @  3  H h 0޽h ? ̙33 0 l(  lX l C <   3 l S (3< @  3  H l 0޽h ? ̙33 0 p(  pX p C <   3 p S (3< @  3  H p 0޽h ? ̙33 0 t(  tX t C <   3 t S d3< @  3  H t 0޽h ? ̙33r|$7 9:<>@BDFkHWJCL/N}-?3PQSUkW?Y[\^`cb7d f  g Oh+'0 hp ( H T `ltCSC-141 Lecture 30Mark S. HutchenreutherGC:\WINDOWS\Application Data\Microsoft\Templates\Blank Presentation.potMark S. HutchenreutherD2rkMicrosoft PowerPointrD@!w@Q @ f G*g  -& &&#TNPP 2OMia & TNPP &&TNPP    - "-- !-- "-&G& - &Gy& --iyH-- @Times New Roman- . 2 ACSC'!'. . 2 A\-. .2 Ao141 Lecture 30".--Q1-- @Times New Roman- .-2 Review for the Final Exam       .--"System-&TNPP &n ՜.+,0,     On-screen ShowWeird Enterprisesxh<   Times New RomanBlank PresentationCSC-141 Lecture 30Sections Covered Since MT26.4 Shortest Path Algorithm6.5 Representation of Graphs6.6 Isomorphisms of Graphs6.7 Planar Graphs!7.2 Characterizations of Trees7.3 Spanning Trees7.4 Minimal Spanning Trees10.1 Finite State Machines10.2 Finite State Automata ProbabilityProbability Example  Fonts UsedDesign Template Slide Titles ._ch2Mark S. HutchenreutherMark S. Hutchenreuther  !"#$%&'()*+,-./012346789:;<>?@ABCDFGHIJKLORoot EntrydO)Current User- "--- ESummaryInformation& (- 5PowerPoint Document(--iyH-h DocumentSummaryInformation-8. 2 A=C'!'. . 2 A .2 Ao141 Lecture 30".--Q1-- @Times New Roman-.-2 Revi