**This is an old revision of the document!**

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)
PredicateList.evaluate()
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)