Posts in 2021
-
12-01 Weighted
Wednesday, December 01, 2021 in Daily
WeightedGraph Class Make a WeightedGraph subclass of your Graph class. (Just copy and edit if you’re not interested in subclassing.) self.weights[(a,b)] == wt means the edge from a to b has weight wt. The weights dictionary should be symmetric …
-
11-16 Tree Diam
Tuesday, November 16, 2021 in Daily
What is the definition of a tree? (That is, what conditions on a graph cause it to be considered a tree?) The diameter of a graph is the maximum distance between any two vertices. For a general graph, a quadratic algorithm is needed. When a graph is …
-
10-27 Slow Cut
Wednesday, October 27, 2021 in Daily
A cut vertex or “articulation vertex” is a vertex whose removal disconnects the graph. There is an efficient way of finding cut vertices, but as a warm up we will just focus on a simple algorithm. Remember: you should develop test cases …
-
10-20 Two Coloring
Wednesday, October 20, 2021 in Daily
A graph can be “colored” with N colors if you can paint every vertex with one of the N colors and have no edge between vertices of the same color. We will use integers to represent colors, like 0=red, 1=green, etc. (The actual colors do …
-
10-19 Connected
Tuesday, October 19, 2021 in Daily
Write a function to find the number of connected components in a graph. def connected_components(g: Graph) -> int: return -1 # skeleton Follow the design process to make it go more smoothly. Testing your code You should make some simple examples …
-
Design Process
Friday, October 15, 2021 in Daily
Show you understand the problem. Write using a fast feedback process. Demonstrate your code works. Understand the problem Examples that you have worked out show that you understand the problem. Pick two examples and show: What information is input …
-
10-15 Diameter
Wednesday, October 13, 2021 in Daily
Recall the setup from the previous project: Generate a random graph (“maze”) with 2000 vertices. Add 100 random edges to your graph. Diameter The diameter of a graph is the maximum shortest distance between any two vertices. Draw two …
-
10-13 Stringy
Wednesday, October 13, 2021 in Daily
Stringy Storage of a Graph The (until now fictional) “string method” of storing a graph lists strings of connected vertices on every line. Assignment: Write a function that accepts an already open file (returned from open) and creates an …
-
10-13 Basics
Wednesday, October 13, 2021 in Daily
Python proficiency questions. Suppose x is an object of class CC. What method is run by str(x)? Give an efficient way to remove the trailing newlines from an array of strings read from a file. ['the\n','mouse\n','went\n','up\n','the\n','clock\n'] …
-
10-08 Shortest
Thursday, October 07, 2021 in Daily
Skills base Sorting into a new container: ys = sorted(..., reverse=True) Sorting by mutation, changing the existing container: xs.sort(reverse=True) Field width: f"{x:10}" puts x in a space 10 characters wide. Improvements to graph.py …