UPGMA(D, n) Clusters ← n single-element clusters labeled 1, ... , n
construct a graph T with n isolated nodes labeled by single elements 1, ... , n for every node v in T Age(v) ← 0 while there is more than one cluster
find the two closest clusters C_{i} and C_{j}
merge C_{i} and C_{j} into a new cluster C_{new} with |C_{i}| + |C_{j}| elements
add a new node labeled by cluster C_{new} to T
connect node C_{new} to C_{i} and C_{j} by directed edges
remove the rows and columns of D corresponding to C_{i} and C_{j}
remove C_{i} and C_{j} from Clusters
add a row/column to D for C_{new} by computing D(C_{new}, C) for each C in Clusters
add C_{new} to Clusters root ← the node in T corresponding to the remaining cluster for each edge (v, w) in T
length of (v, w) ← Age(v) - Age(w) returnT

UPGMA Problem

Construct the ultrametric tree resulting from UPGMA.

Given: An integer n followed by a space-delimited n x n distance matrix.

Return: An adjacency list for the ultrametric tree output by UPGMA. Weights should be accurate to three decimal places.

Note on formatting: The adjacency list must have consecutive integer node labels starting from 0. The n leaves must be labeled 0, 1, ..., n-1 in order of their appearance in the distance matrix. Labels for internal nodes may be labeled in any order but must start from n and increase consecutively.