//**********************************************************************//
/***********Exam 3 Review / Graphs Vocab - April 7th, 2017*************//
//********************************************************************//
-REALITY CHECK!
1) Given the following code which starts the Radix Sort algorithm, complete the code for Radix Sort (LSD):
"public static int[] radixSort(int[] arr) {
if (arr == null) {
throw new IllegalArgumentException("Null args illegal");
}
LinkedList<Integer>[] counter;
counter = (LinkedList<Integer>[]) new LinkedList[19];
for (int i = 0; i < 19; i++) {
counter[i] = new LinkedList<>();
}
int mod = 10; //base of our sort
int dev = 1; //divisor
boolean cont = true;
while (cont) {
//(...your code below here...)
}"
//TA SOLUTION:
(...)
while (cont) {
for (int i = 0; i < arr.length; i++) {
int digit = (arr[i] / dev) % mod + (mod - 1) //last part, "mod - 1", handles negatives (e.g. 1 goes in the 10th bucket)
counter[digit].add(arr[i]);
}
int nextIndex = 0;
for (LinkedList<Integer> bucket : counter) {
while (!bucket.isEmpty) {
arr[nextIndex++] = bucket.remove();
}
}
dev *= 10;
if (Integer.MAX_VALUE / mod = dev) { //MISSED THIS PART, but says when to stop the sort
cont = false;
}
}
2) Write the code for the merge sort "Merge" method given the description below:
"/**
/* This is a private helper message that will merge the elements
/* into a sorted list
/*
/* @param <T> data type to sort
/* @param arr the original array
/* @param a the left half of the array to be merged
/* @param b the right half of the array to be merged
/* @ param comparator the comparator that will compare the elements"
private static <T> void merge(T[] arr, T[] a, T[] b, Comparator<T>
comparator) {
int i = 0;
int j = 0;
while (i < a.length && j < b.length) {
arr[i + j] = (comparator.Compare(a[i], b[j]) <= 0)
? a[i++] : b[j++];
}
while (i < a.length) {
arr[i + j] = a[i++];
}
while (j < b.length) {
arr[i + j] = b[j++];
}
}
//TAs way (TAs EXPLICITLY said there were multiple ways)
int i = 0;
while (i < arr.length) {
if (i >= arr.length) {
//...basically, they did everything inside a single while loop; way that I did it (above) was perfectly fine as well
}
}
3) Write the following methods for an AVL tree in Java:
private AVLNode<T> leftRotation(AVLNode<T> node) {
}
private AVLNode<T> rightRotation(AVLNode<T> node) {
}
MY ATTEMPT:
private AVLNode<T> leftRotation(AVLNode<T> node) {
AVLNode<T> newRoot = node.getRight();
node.setRight(newRoot.getLeft());
newRoot.setLeft(node);
updateHeightBF(node);
updateHeightBF(newRoot);
return newRoot;
}
-Was mostly good, but I forgot to include the "updateHeight" portion until after the TA example; currently, this code matches the TAs example
private AVLNode<T> rightRotation(AVLNode<T> node) {
AVLNode<T> newRoot = node.getLeft();
node.setLeft(newRoot.getRight());
newRoot.setRight(node);
updateHeightBF(node);
updateHeightBF(newRoot);
return newRoot;
}
-Here's the updateHeight method:
"private void updateHeightBF(AVLNode<T> mode) {
node.balanceFactor = getHeight(node.left) -
getHeight(node.right);
node.height = Math.max(getHeight(node.left),
getHeight(node.right)) + 1;
}
private int getHeight(AVLNode<T> node) {
if (node == null) {
return - 1;
}
return node.height;
}"
-On Monday, we'll start talking about Graphs: some common terminology, graph modeling, searching algorithms for graphs,
-A few quick things for right now (NOT on the exam):
-A GRAPH is a set of "nodes" (or VERTICES) and a collection of EDGES (or "arcs") that connect pairs of vertices
-The ORDER of a graph is the # of vertices; the SIZE is the # of edges
-The DEGREE of a vertex is the # of edges connected (or "incident") to that vertex
-If all the vertices have the same degree, then we say that the whole graph has that degree
-A PATH is a set of edges that can be followed to connect 2 nodes
-Graphs CAN have vertices that aren't connected to any edges
-Graphs can be DIRECTED, where their edges only go in one direction
-One vertex is the origin, another is the destination; can ONLY go from the origin to the destination
-Usually written as an ordered pair (u, v), where "u" is the origin and "v" is the other
-Graphs can also be UNDIRECTED, where edges can go in both directions
-Graphs can be WEIGHTED, where there are "weights" or "costs" associated with each edge
-A SELF-LOOP is an edge connecting a vertex to itself
-Two edges are "parallel" if they connect the same pair of vertices
-i.e. you can have MULTIPLE edges between 2 vertices
-We say vertices are ADJACENT if an edge connects two vertices to each other
-As we said, a PATH is a sequence of vertices connected by edges to get from one vertex to another
-A SIMPLE PATH is one with no repeated vertices (we only visit each vertex in the path once)
-The 2 most common graph implementations:
-ADJACENCY MATRIX
-ADJACENCY LIST
-We'll go over these on Monday