Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
cs-236:homework-10 [2015/01/05 13:48]
egm [Problems]
cs-236:homework-10 [2017/12/01 12:03] (current)
kylej13 [Problems]
Line 1: Line 1:
-The objectives are +==Objectives== 
-List properties ​of graphs including incidentadjacent, neighbors, degree, isolated, and pendant +Properties ​of trees and rooted trees 
-Identify ​in-degree ​and out-degree ​on directed ​graphs +* Buildsearch, and traverse binary search trees. 
-Represent graphs with adjacency matrixes +Perform ​in-order, pre-order, ​and post-order traversal ​on trees and graphs 
-* Represent graphs with adjacency lists +Compute the depth-first ​and breadth-first search for a graph 
-* Finds paths, simple paths, ​and circuits in graphs +* Find minimum spanning trees using Kruskals and Prim's algorithms 
-* Determine is a graph is connected +* Compute the strongly connected components in a graph
-* Find strongly connected components in a graph +
-* Apply Dijkstra'​s shortest path algorithm to graphs +
-* Learn Floyd'​s all-pairs shortest path algorithm+
  
-== Problems == +==Problems== 
-# (2 points) 10.2.2 +# (3 points) ​11.1.2 
-# (2 points) 10.2.8 +# (points) ​11.1.4 
-# (3 points) ​10.3.2 +# (2 points) ​11.2.2 
-# (points) ​10.3.4 +# (2 points) ​11.2.4 
-# (2 points) ​10.3.12 +# (4 points) ​11.4.14 
-# (2 points) ​10.3.26 (do for problem 2 only) +# (points) ​Repeat problem 11.4.14 only this time assign post-order traversal numbers to each vertex of the spanning tree. 
-# (4 points) ​10.4.2 +# (points) ​11.4.16 (just the graph from problem 11.4.14) 
-# (points) ​10.4.4 +# (2 points) ​11.5.1 
-# (points) ​10.4.12 +# (points) ​11.5.2 
-(3 points) 10.4.14 +# (6 points) ​11.5.6
-# (2 points) ​10.4.18 +
-# (points) ​10.6.8 extend the algorithm to compute the actual path, and not just the mileage. Report both the mileage and the path+
-# (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. +
-# ('''​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) +
-## What do cycles in a call graph mean? +
-## What does it mean if the graph is disconnected?​ +
-<code java> +
-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) +
-</​code>​+
cs-236/homework-10.1420490912.txt.gz · Last modified: 2015/01/05 13:48 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