Differences

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

 cs-236:homework-10 [2015/01/05 13:48]egm [Problems] cs-236:homework-10 [2017/12/01 12:03] (current)kylej13 [Problems] Both sides previous revision Previous revision 2017/12/01 12:03 kylej13 [Problems] 2017/11/28 10:43 zalger 2017/11/28 10:43 zalger [Problems for Sections 3 and 4] 2015/02/17 10:36 egm 2015/01/05 13:48 egm [Problems] 2014/09/03 11:54 egm created Next revision Previous revision 2017/12/01 12:03 kylej13 [Problems] 2017/11/28 10:43 zalger 2017/11/28 10:43 zalger [Problems for Sections 3 and 4] 2015/02/17 10:36 egm 2015/01/05 13:48 egm [Problems] 2014/09/03 11:54 egm created Line 1: Line 1: - The objectives are + ==Objectives== - * List properties ​of graphs including incident, adjacent, neighbors, degree, isolated, and pendant + * Properties ​of trees and rooted trees - * Identify ​in-degree ​and out-degree ​on directed ​graphs + * Build, search, 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 + # (4 points) ​11.1.4 - # (3 points) ​10.3.2 + # (2 points) ​11.2.2 - # (3 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) + # (4 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 + # (4 points) ​11.4.16 (just the graph from problem 11.4.14) - # (1 points) ​10.4.4 + # (2 points) ​11.5.1 - # (3 points) ​10.4.12 + # (4 points) ​11.5.2 - # (3 points) 10.4.14 + # (6 points) ​11.5.6 - # (2 points) ​10.4.18 + - # (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. + - # (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. + - # ('''​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) + - ## What do cycles in a call graph mean? + - ## 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) + - ​ +