(1)	_____	The degree (or valency) of a vertex is:
		Its connected forest Its geographic extent The number of links incident to it Its walk
(2)	_____	A graph which contains no circuits is said to be:
		A walk Directed A giraffe A forest
(3)	_____	Geocoding is:
		The process of creating an electronic/digital representation (usually a vector representation) of a geometric shape An algorithm for performing phonetic searches The process of finding the coordinates of an object on the surface of the Earth None of the above
(4)	_____	A "great circle" is:
		A vertex A norm A map projection A section of a sphere that contains a diameter of the sphere
(5)	_____	A label correcting algorithm for finding shortest paths:
		Visits each node at most once Only works for distances, not for times Can select candidates using the Euclidean distance All of the above

Find the "distance" between the following points (1,0) and (4,4) using each of the following metrics:

The metric generated by the Euclidean norm
(1)
The metric generated by the rectilinear norm
(2)
The metric generated by the supremum norm
(3)
The "Post Office" metric
(4)

Recall that the minimum distance between a point, , and the line through the points and is given by:

Using this, find the minimum distance between each of the following points and the line segment connecting the points (1,1) and (4,4).

(3,1)
(1)
(2,2)
(2)
(5,4)
(3)
(4,1)
(4)

Find the Soundex code for each of the following street names. (Note: You can, and should, check your answers using the Java implementation of the algorithm that we discussed in lecture.)

Eberhard
(1)
Lee
(2)
Pfister
(3)
Heimbach
(4)

calculate the "shortest" path from vertex/node 0 to vertex/node 8 using Dijkstra's label setting algorithm. Show your work in the tables next to each vertex/node (i.e., each time you change the label associated with a vertex/node you must add a row to the associated table that contains the new label and the new predecessor).

1. Change the 62 to a 49 and perform a "sift up".

2. Change the 46 to a 17 and perform a "sift up".

3. Remove the smallest element by swapping the "front" and "back" elements, removing the new "back" element, and performing a sift down.

4. Add a new element (with a value of 27) by making it the "back" element and performing a sift up.

public class Node
{
    public int              label;
    public String           id;    
}
    

complete the following GroupedCollection class:

import java.util.*;

/**
 * A GroupedCollection is a collection of Node objects.
 * Each node is kept in a "bucket" that corresponds to 
 * an intervale of labels.
 *
 * For example, if the maximum label is 100 and the 
 * number of buckets is 2, then the Node objects are
 * kept in two buckets, one containing Node objects with
 * labels in the interval [0, 50] and one containing Node 
 * objects with labels in the interval [51, 100].
 * corresponding to its label.
 */
public class GroupedCollection
{



    

    /**
     * Explicit Value Constructor
     *
     * @param maxLabel    The value of the largest possible label
     * @param numBuckets  The number of buckets
     */
    public GroupedCollection(int maxLabel, int numBuckets)
    {




    }
    


    /**
     * Add a Node to this GroupedCollection (i.e., put
     * it in the appropriate bucket)
     *
     * Note: This method assumes that the Node is not
     *       already in this GroupedCollection
     */
    public void addNode(Node node)
    {












    }
    


    /**
     * Get the Node with the smallest label (and remove it
     * from this GroupedCollection)
     *
     * @retun  The appropriate Node
     */
    public Node getNodeWithSmallestLabel()
    {














    }
    


    /**
     * Modify the label of a Node that is already
     * in this GroupedCollection (and move the Node
     * to the correct bucket)
     *
     * @param node      The Node to modify
     * @param newLabel  The new label for this Node
     */
    public void modifyNode(Node node, int newLabel)
    {














    }
}