The objectives are

  • List properties of graphs including incident, adjacent, neighbors, degree, isolated, and pendant
  • Identify in-degree and out-degree on directed graphs
  • Represent graphs with adjacency matrixes
  • Represent graphs with adjacency lists
  • Finds paths, simple paths, and circuits in graphs
  • Determine is a graph is connected
  • Find strongly connected components in a graph
  • Apply Dijkstra's shortest path algorithm to graphs
  • Learn Floyd's all-pairs shortest path algorithm

Problems

  1. (2 points) 10.2.2
  2. (2 points) 10.2.8
  3. (3 points) 10.3.2
  4. (3 points) 10.3.4
  5. (2 points) 10.3.12
  6. (2 points) 10.3.26 (do for problem 2 only)
  7. (4 points) 10.4.2
  8. (1 points) 10.4.4
  9. (3 points) 10.4.12
  10. (3 points) 10.4.14
  11. (2 points) 10.4.18
  12. (6 points) 10.6.8 extend the algorithm to compute the actual path, and not just the mileage. Report both the mileage and the path.
  13. (6 points) 10.6.21 extend the algorithm to compute the actual path, and not just the cost. Report the cost between a and z and show how the path is reconstructed from your extension.
  14. (6 points Extra Credit) Draw the “call graph” of the following program fragment. (The nodes of a call graph are methods and the edges are method calls)
    1. What do cycles in a call graph mean?
    2. What does it mean if the graph is disconnected?
MainProgram
   main(String[])
      DatalogProgram.evaluateQueryList(StringBuffer)
DatalogProgram
   evaluateQueryList(StringBuffer)
      QueryList.evaluate(StringBuffer)
FactList
   canProve(Predicate)
      Fact.equals(Object)
Predicate
   set(int, Constant)
Fact
   equals(Object)
RuleList
   canProve(Predicate)
      Rule.prove(Predicate)
Rule
   prove(Predicate)
      Head.matches(Predicate)
      PredicateList.evaluate()
      Head.unify(Predicate)
Head
   unify(Predicate)
   matches(Predicate)
PredicateList
   PredicateList(PredicateList)
      PredicateList.initializeVariableInformation()
      Query.initializeVariableInformation()
   evaluate()
      PredicateList.recurse(int)
   recurse(int)
      PredicateList.keepOnGoing(Boolean)
      Query.keepOnGoing(Boolean)
      PredicateList.recurse(int)
      PredicateList.checkToSeeIfTrue()
   checkToSeeIfTrue
      FactList.canProve(Predicate)
      RuleList.canProve(Predicate)
      PredicateList.saveResult()
      Query.saveResult()
   saveResult()
   setUpVariableLocationMapping()
   initializeVariableInformation
      PredicateList.setUpVariableLocationMapping()
   keepOnGoing(Boolean)
QueryList
   evaluate(StringBuffer)
      Query.evaluate(StringBuffer)
Query
   initializeVariableInformation()                                   
   evaluate(StringBuffer)
      PredicateList.evaluate()
   saveResult()
   keepOnGoing(Boolean)
cs-236/homework-9.txt · Last modified: 2015/02/17 17:36 by egm
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0