cs-236:homework-9 [CS Wiki]

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

(2 points) 10.2.2
(2 points) 10.2.8
(3 points) 10.3.2
(3 points) 10.3.4
(2 points) 10.3.12
(2 points) 10.3.26 (8th ed. 10.3.30) - do for Exercise 2 only (not Example 2). Use the following labels for edges: graph
(4 points) 10.4.2
(1 points) 10.4.4
(3 points) 10.4.12
(3 points) 10.4.14
(2 points) 10.4.18
(6 points) 10.6.8 - Extend Dijkstra's algorithm to compute the actual path as well as the mileage. Show your work. Report both the mileage and the path.
(6 points) 10.6.21 - Extend Floyd's algorithm to compute the actual path as well as the cost. Report the cost between a and z and show how the path is reconstructed from your extension.
(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: 2018/08/15 14:34 by pdiddy

Back to top