Backup

Priority Queues

Abstract Priority Queue

• Create a package cs323.queue.
• Create an abstract class AbstractPriorityQueue under queue.
• Make a generic type T extends Comparable<T>].
• Declare an abstract method add.
• @param key a comparable key to be added.
• Declare an abstract method removeMax.
• @return the key with the highest priority.
• @throws[NoSuchElementException] (http://docs.oracle.com/javase/8/docs/api/java/util/NoSuchElementException.html) if the queue is empty.
• Declare an abstract method size.
• @return the number of keys in this queue.
• Define a method isEmpty.
• @return true if the queue is empty; otherwise, false.

Eager Priority Queue

• Create a class EagerPriorityQueue under queue.
• Extend the AbstractPriorityQueue class.
• Make a generic type T extends[Comparable<T>].
• List<T> l_keys - contains all keys.
• Override the add method.
• Insert the key to l_keys such that l_keys maintains to be in ascending order.
• Override the removeMax method.
• Remove and return the last key in l_keys.
• Override the size method.
• @return the size of l_keys.

Binary Heap

• Create a class BinaryHeap under the queue package.
• Extend the AbstractPriorityQueue class.
• List<T> l_keys - contains all keys, including a dummy key at the front.
• int n_size - counts the number of keys in the heap.
• Override the add method.
• Add the key to the end of l_keys, and increase n_size by 1.
• Perform swim (bottom-up reheapify).
• Override the removeMax method.
• Swap the last and the first keys in l_keys.
• Remove and keep the last key in l_keys; decrease n_size by 1.
• Perform sink (top-down reheapify).
• Override the size method.
• @return n_size.

Evaluation

• Assess EagerPriorityQueue and BinaryHeap using:
• PriorityQueueTest#testAccuracy().
• Compare the speeds of EagerPriorityQueue and BinaryHeap using:
• PriorityQueueTest#testSpeed().

Quiz

• Create a class LastnameHeap under queue (e.g., ChoiHeap).
• Extend the AbstractPriorityQueue class.
• Override the add, removeMax, and size methods such that each node takes 3 children instead of 2 (so it becomes a ternary instead of binary tree). You code should look very similar to BinaryHeap.
• Put TernaryHeap.java under cs323/quiz1.

Sort

Comparison-based Sort

• Create a package sort.
• Put the AbstractSort class under sort.
• Create classes SelectionSort, InsertionSort, HeapSort, ShellSort, MergeSort, QuickSort under sort.
• Extend the AbstractSort class.
• Make a generic type T extends Comparable<T>.
• Override the sort method in each class by implementing selection sort, insertion sort, heap sort, shell sort, merge sort, and quick sort.
• Make sure you use the compareTo, assign and swap methods for all comparisons, array assignments, and swaps, respectively.

Evaluation

• Assess all sorting algorithms using:
• SortTest#testAccuracy().
• Compare the speeds of all sorting algorithms using:
• SortTest#compareSpeeds().
• Compare the assignments of all sorting algorithms using:
• SortTest#countOperations().

Quiz

• Create a class ShellSortHibbard under sort.
• Extend the AbstractSort class.
• Override the sort method.
• Implement the shell sort algorithm.
• Use the Hibbard sequence for the gaps.
• Compare the performance between ShellSort and ShellSortHibbard using lists of 100, 200, ..., 1000 random keys for speeds, comparison counts, and assignment counts.

Abstract Class - Bucket Sort

• Create an abstract class AbstractBucketSort under the sort package.
• Inherit the AbstractSort class.
• Make a generic type T extendsComparable<T>.
• List<T>[] g_buckets: the list of buckets.
• boolean b_sort: if true, sort each bucket.
• Define a constructor.
• @param bucketSize: the total number of buckets.
• @param sort: if true, sort each bucket.
• Initialize g_buckets with empty lists (use DSUtils#createEmptyListArray).
• Initialize the global instance b_sort with sort.
• Declare an abstract method getBucketIndex.
• @param key a comparable key.
• @return the index of the bucket that key should be inserted.
• Override the sort method.
• Add all keys in array to g_buckets using the getBucketIndex method.
• If b_sort is true, sort each bucket in ascending order.
• Put all keys in each bucket back to array.

Integer Bucket Sort

• Create a class IntegerBucketSort under the sort package.
• Inherit the AbstractBucketSort<Integer> class.
• Define a constructor.
• @param min the minimum integer (inclusive).
• @param max the maximum integer (exclusive).
• Call super with an appropriate bucket size given min and max, and sort = false.
• Override the getBucketIndex method.
• @return the index of the bucket that key∈[min,max] should be inserted.

Radix Sort - Least Significant Digit

• Create a class LSDRadixSort under the sort package.
• Inherit the AbstractBucketSort<Integer> class.
• Define a constructor.
• @param maxDigit the maximum number of digits.
• Call super with bucketSize = 10 and sort = false.
• Override the getBucketIndex method.
• @return the index of the bucket, where key ≤ 10^maxDigit.

Quiz

• Create a class ProbabilityBucketSort under the sort package.
• Inherit the AbstractBucketSort<Double> class.
• Define a constructor.
• Call super with an appropriate bucket size given the input range of [0, 1), and sort = true.
• Override the getBucketIndex method.
• @return the index of the bucket that key∈[0, 1) should be inserted.
• Create a class ProbabilityBucketSortTest under the sort package, and define a method test to evaluate the accuracy of your algorithm using 10 different lists of 100 random double values between 0 and 1.
• See SortTest#testAccuracy and Random#nextDouble.

Binary Node

• Create a package cs323.tree.
• Download the AbstractBinaryNode class and put it under the tree package.
• Create a class BinaryNode under the tree package.
• Inherit the AbstractBinaryNode class.
• Make a generic type T extendsComparable<T>.
• Define a constructor.
• @param key the key of this node.

Binary Search Tree

• Download the AbstractBinarySearchTree class and put it under the tree package.
• Create a class BinarySearchTree under the tree package.
• Inherit the AbstractBinarySearchTree class.
• Make a generic type T extendsComparable<T>.
• Override the createNode method.
  • @param key the key of this node.
  • @return a BinaryNode with the specific key.

Balanced Binary Search Tree

• Create a package cs323.tree.balanced.
• Create a class AbstractBalancedBinarySearchTree under the balanced package.
• Declare an abstract method balance.
• @param node the node to be balanced.
• Override the add and remove methods.
• @param key the key of the node to be added and removed.
• Call the balance method to keep the tree in balance.
• Define methods rotateLeft and rotateRight.
• @param node the node to be rotated.
• Rotate the specific node to left and right.

AVL Node

• Create a class AVLNode under the balanced package.
• Inherit the AbstractBinaryNode class and set AVLNode as the node type.
• Make a generic type T extendsComparable<T>.
• int i_height the height of this node.
• Create a constructor.
• @param key the key of this node.
• Intialize i_height to 1.
• Define a method getBalanceFactor.
• @return height(left-subtree) - height(right-subtree).
• Define a method resetHeights.
• Reset the heights of this node and its ancestors, recursively.
• Override the setLeftChild and setRightChild methods.
• @param node the child node.
• Call the resetHeights method to update the heights.

AVL Tree

• Create a class AVLTree under the balanced package.
• Inherit the AbstractBalancedBinarySearchTree class and set AVLNode as the node type.
• Make a generic type T extendsComparable<T>.
• Override the createNode method.
  • @return a AVLNode with the specific key.
• Override the rotateLeft and rotateRight methods.
• @param node the node to be rotated.
• Call the node.resetHeights method to update the heights.
• Override the balance method.
• @param node the node to be balanced.
• Read AVL tree.

Red-Black Node

• Create a class RedBlackNode under the balanced package.
• Inherit AbstractBinaryNode and set RedBlackNode as the node type.
• Make a generic type T extendsComparable<T>.
• boolean b_red true if this node is red; otherwise, false.
• Create a constructor.
• @param key the key of this node.
• Intialize b_red to true.
• Define methods isRed and isBlack.
• @return true if this node is red and black.
• Define methods setToRed and setToBlack.
• Set this node to red and black.

Red-Black Tree

• Create a class RedBlackTree under the balanced package.
• Inherit AbstractBalancedBinarySearchTree and set RedBlackNode as the node type.
• Make a generic type T extendsComparable<T>.
• Override the createNode method.
  • @return a RedBlackNode with the specific key.
• Override the balance method.
• @param node the node to be balanced.
• Read Red-Black tree.

Fibonacci Sequence

• Create a package cs323.dynamic.fibonacci.
• Download the AbstractFibonacci class and put it under fibonacci.
• Create classes RFibonacci, LFibonacci, DFibonacci under fibonacci.
• Extend AbstractFibonacci.
• Override the get2p method under RFibonacci, LFibonacci, DFibonacci using recursion, dynamic programming, and a loop, respectively.
• @param k must be greater than 1.
• @return the k'th Fibonacci number.

Tower of Hanoi

• Create a package cs323.dynamic.hanoi.
• Download the AbstractHanoi class and put it under hanoi.
• Create classes RHanoi and DHanoi under hanoi.
• These classes extend AbstractHanoi.
• Override the solve method under RHanoi and DHanoi using recursion and dynamic programming, respectively.
• @param n the total number of rings.
• @param source the source tower.
• @param intermediate the intermediate tower.
• @param destination the destination tower.
• @return a list of steps to move all rings from source to destination.

Longest Common Subsequence

• Create a package cs323.dynamic.lcs.
• Download the AbstractLCS class and put it under lcs.
• Create classes RLCS and DLCS under lcs.
• These classes extend AbstractLCS.
• Override the solve method under RLCS and DLCS using recursion and dynamic programming, respectively.
• @param c the first array of characters.
• @param d the second array of characters.
• @param i the index of c to be compared.
• @param j the index of d to be compared.
• @return a longest common sequence of the specific strings c and d.

Knapsack Problem

• Create a package cs323.dynamic.knapsack.
• Download the AbstractKnapsack class and put it under lcs.
• Create classes RKnapsack and DKnapsack under knapsack.
• These classes extend AbstractKnapsack.
• Override the solve method under RKnapsack and DKnapsack using recursion and dynamic programming, respectively.
• @param items items to be entered into the knapsack.
• @param maxWeight the maximum weight that the knapsack can hold.
• @return a list of items maximizing the total value given items and maxWeight.

Quiz

• For each k, how many times are the following methods called recursively?
• RHanoi#solve(List<String> int, char, char, char).
• DHanoi#solve(List<String>, int, char, char, char, Map<String,int[]>).
• Is there any clear pattern between k and the number of the method calls in each class? Explain the pattern if there is one.

Spanning Tree

• Create a package cs323.graph.
• Download the Graph and Edge classes and put it under graph.
• Create a package cs323.graph.span.
• Download the SpanningTree class and put it under span.
• Download the MSTAlgorithm interface and put it under span.

Minimum Spanning Tree

• Create classes MSTPrim, MSTKruskal, and MSTEdmonds under span.
• Inherit the MSTAlgorithm interface.
• Override the getMinimumSpanningTree method in each class by implementing Prim's, Kruskal's, and Chu–Liu-Edmonds' algorithms, respectively.
• @param graph a graph containing at least one spanning tree.
• @return a minimum spanning tree.

Prim's Algorithm

1. Pick a vertex.
2. Put the picked vertex to a set and add all its incoming edges to a priority queue using their weights.
3. Remove the minimum edge in the queue and check if the set contains the source of this edge.
4. If the set contains the source, add the edge to a tree.
5. If all edges in the tree form a spanning tree, return the tree.
6. Otherwise, go to #2 by picking the source of the edge.
7. Go to #3 unless the queue is empty.

Kruskal's Algorithm

1. Create a forest in which each set consists of each vertex in the graph.
2. Create a priority queue containing all edges in the graph.
3. Remove the minimum edge in the queue and check if the source and the target belong to the same set in the forest.
4. If the source and the target do not belong to the same set, add the edge to a tree and merge the source and the target sets.
5. If all edges in the tree form a spanning tree, return the tree.
6. Go to #3 unless the queue is empty.

Chu–Liu-Edmonds’ Algorithm

1. Initially, every vertex is considered a tree.
2. For each tree, keep 1 incoming edge with the minimum weight.
3. If there is no cycle, go to #5.
4. If there is a cycle, merge trees with the cycle into one and update scores for all incoming edges to this tree, and goto #2.
5. For each vertex in the tree, add the weight of its outgoing edge to its incoming edges not in the tree. Break all cycles by removing edges that cause multiple parents.

Quiz 6

• Give a graph where Prim's and Kruskal's algorithms generate different kinds of minimum spanning trees. Explain how these trees are generated. If you cannot find an example, explain why these algorithms always generate the same minimum spanning tree given any graph.

Quiz 7

• What is the worst-case complexity of Chu–Liu-Edmonds’ Algorithm when V is the number of vertices and E is the number of edges in a graph? Explain how you come up with this complexity.

Ford-Fulkerson Algorithm

• Create a package graph.flow.
• Download the MaxFlow and MFAlgorithm classes.
• Create a class FordFulkerson under graph.flow.
• Inherit the MFAlgorithm interface.
• Override the getMaximumFlow method under FordFulkerson.
• @param graph a graph.
• @param source the source vertex.
• @param target the target vertex.
• @return the maximum flow from the source to the target vertices.
• Find each augmenting path using depth-first search.
• Ford-Fulkerson.

Links

• Online simplex tool.

Quiz

• Prove the maximum flow is equal to the minimum cut capacity.