Posts in 2022
-
02-01 Solver
Tuesday, February 01, 2022 in 02-01 Solver
The purpose of this section is to build a general solver that can figure out how to transition from a given starting state to a given target state. Starter code in Replit.
-
Topological Sort
Wednesday, January 19, 2022 in Daily
Dangers and Annoyances: Make sure you have a way of reading in directed graphs. In a directed graph, when you encounter an edge from a to b, you should not automatically create an edge from b to a. Graph data. Example 1, 7 vertices. Example 2, 23 …
-
01-19 Topo Writeup
Wednesday, January 19, 2022 in Daily
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 …
-
01-14 Minimum Distance
Friday, January 14, 2022 in Daily
Implementing Dijkstra’s algorithm to find the minimum cost path from a starting vertex. Test cases: Example 1 (6 vertices) Shortest distance from 0 to 5 is 50. Example 2 (10 vertices) Shortest distance from 0 to 9 is 80. Example 3 (20 vertices) …
Posts in 2021
-
12-06 MST Wrapup
Tuesday, December 07, 2021 in Daily
Key question: how do you know your code produces a minimal spanning tree? Try some of these test cases. total weight Write a new method in the weighted graph class to return the total weight of all of the edges given. def total_weight(self, edges: …
-
12-02 MST Testing
Friday, December 03, 2021 in Daily
Minimal Spanning Tree: Basic Version We discussed in class a method for creating a minimal spanning tree from a weighted graph. If you need to look it up, it is known as Prim’s Algorithm. from typing import List, Dict, Tuple, Set def …