01-19 Topo Writeup

Requirements

  • Implementations of topological sort: fast, slow
  • Verifier: checks for a valid order
  • Timing: time and produce a graph. For small size graphs you may need a relatively large number of repetitions to get repeatable measurements.
  • Code cleanup
    • Good names for functions and variables
    • Purpose statements for each function
  • Descriptions: a high level description of each method (slow, fast). Include reasoning why the method works.

My slow method takes about 0.2 seconds for one run of a 2000 vertex graph, if you’re trying to figure out whether your method is fast or slow.

Details

  • (Correctness I.) Have a function that automatically runs through the posted test examples and verifies your solutions are correct.

  • (Correctness II.) Have a function that randomly tests your code by generating a random graph of some size, topologically sorting it, then verifying that the output list is valid for your graph.

  • In the end, write random_checker(graph_size, number_of_trials).

  • Once you know your code works then edit to produce CLEAN CODE.