Kruskal’s algorithm takes these structures as input and returns a minimum spanning tree. For 10 points each:
[10e] Name these structures that consist of nodes and edges. They can be represented using adjacency lists or adjacency matrices. Euler instigated the theory of these things in his solution to the Bridges of Königsberg problem.
ANSWER: graphs [accept network]
[10m] Kruskal’s algorithm works by choosing a safe edge with the minimum cost at every step until a spanning tree is found which makes it an algorithm of this type. Other algorithms of this type include Dijkstra’s algorithm and Huffman coding.
ANSWER: greedy
[10h] Testing if edges are safe can be done using a disjoint set data structure. When implemented with path compression and ranks, checking can be done in [read slowly] “big theta of alpha of n” average time where alpha is the inverse of this simple non-primitive recursive function named for a German mathematician.
ANSWER: Ackermann function