A priority queue (PQ) is a data structure that supports the following two operations:
add(): adds a comparable key to the PQ.
remove(): removes the key with the highest (or lowest) priority in the PQ.
A PQ that removes the key with the highest priority is called a maximum PQ (max-PQ), and with the lowest priority is called a minimum PQ (min-PQ).
Does a priority queue need to be sorted at all time to support those two operations?
What are the use cases of priority queues?
Abstract Priority Queue
Let us define that is an abstract class to be inherited by all priority queues:
L1: declares the type T that is the type of input keys to be stored in this PQ.
T must be by its priority.
What are comparable data types in Java? Can you define your own comparator?
Let us define three abstract methods, add(), remove(), and size() in AbstractPriorityQueue:
Given the abstract methods, we can define the regular method isEmpty():
Lazy Priority Queue
Let us define whose core methods satisfy the following conditions:
add(): takesto add a key to the PQ.
remove(): takes to remove the key with the highest/lowest priority from the PQ.
In other words, all the hard work is done at the last minute when it needs to remove the key.
L1: declares T and passes it to its super class, AbstractPriorityQueue.
L2: defines a list to store input keys.
Can you add keys to the member field keys when it is declared as final (a constant)?
Why does all constructors in LazyPriorityQueue need to call the super constructor?
We then override the core methods, add() and remove():
L6-8: appends a key to the list in .
L15-20: removes a key to the list in .
Is ArrayList the best implementation of List for LazyPriorityQueue?
Why does remove() in L18 cost ?
Eager Priority Queues
Let us define whose core methods satisfy the following conditions:
add(): takesto add a key to the PQ.
remove(): takes to remove the key with the highest/lowest priority from the PQ.
In other words, all the hard work is done as soon as a key is added.
What are the situations that LazyPQ is preferred over EagerPQ and vice versa?
The implementations of the two constructors and the size() method are identical to the ones in LazyPriorityQueue.
Should we create an abstract class that implements the above code and make it as a super class of LazyPQ and EagerPQ? What level of abstraction is appropriate in object-oriented programming?
We then override the core methods, add() and remove():
L6-12: inserts a key to the list in .
L8: finds the index of the key to be inserted in the list using binary search in .
What are the worst-case complexities of add() and remove() in LazyPQ and EagerPQ in terms of assignments and comparison?
L2: is a comparator that can compare keys of the generic type T.
public abstract class AbstractPriorityQueue<T extends Comparable<T>> {
protected final Comparator<T> priority;
/**
* Initializes this PQ as either a maximum or minimum PQ.
* @param priority if {@link Comparator#naturalOrder()}, this is a max PQ;
* if {@link Comparator#reverseOrder()}, this is a min PQ.
*/
public AbstractPriorityQueue(Comparator<T> priority) {
this.priority = priority;
}
}
/**
* Adds a comparable key to this PQ.
* @param key the key to be added.
*/
abstract public void add(T key);
/**
* Removes the key with the highest/lowest priority if exists.
* @return the key with the highest/lowest priority if exists; otherwise, null.
*/
abstract public T remove();
/** @return the size of this PQ. */
abstract public int size();
/** @return true if this PQ is empty; otherwise, false. */
public boolean isEmpty() {
return size() == 0;
}
public class LazyPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
private final List<T> keys;
/** Initializes this as a maximum PQ. */
public LazyPriorityQueue() {
this(Comparator.naturalOrder());
}
/** @see AbstractPriorityQueue#AbstractPriorityQueue(Comparator). */
public LazyPriorityQueue(Comparator<T> priority) {
super(priority);
keys = new ArrayList<>();
}
@Override
public int size() {
return keys.size();
}
}
/**
* Appends a key to {@link #keys}.
* @param key the key to be added.
*/
@Override
public void add(T key) {
keys.add(key);
}
/**
* Finds the key with the highest/lowest priority, and removes it from {@link #keys}.
* @return the key with the highest/lowest priority if exists; otherwise, null.
*/
@Override
public T remove() {
if (isEmpty()) return null;
T max = Collections.max(keys, priority);
keys.remove(max);
return max;
}
public class EagerPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
private final List<T> keys;
public EagerPriorityQueue() {
this(Comparator.naturalOrder());
}
public EagerPriorityQueue(Comparator<T> priority) {
super(priority);
keys = new ArrayList<>();
}
@Override
public int size() {
return keys.size();
}
}
/**
* Adds a key to {@link #keys} by the priority.
* @param key the key to be added.
*/
@Override
public void add(T key) {
// binary search (if not found, index < 0)
int index = Collections.binarySearch(keys, key, priority);
// if not found, the appropriate index is {@code -(index +1)}
if (index < 0) index = -(index + 1);
keys.add(index, key);
}
/**
* Remove the last key in the list.
* @return the key with the highest priority if exists; otherwise, {@code null}.
*/
@Override
public T remove() {
return isEmpty() ? null : keys.remove(keys.size() - 1);
}
1.2. Implementation
LongInteger: implementation.
We are going to create a class called LongInteger inheriting SignedNumeral that can store an indefinite size of an integer value beyond the primitive types such as int and long.
What is so special about primitive data types in Java?
Java SE provides a similar class called although the implementations of LongIntegerandBigIntegerare completely independent.
Field
Let us declare the member field digits that is an array of bytes holding the values of this integer:
L1: LongInteger is passed to specify the generic type T in SignedNumeral.
The i'th dimension of digits is the i'th least significant digit in the integer such that the integer 12345 would be stored as digits = {5, 4, 3, 2, 1}, which makes it convenient to implement the arithmetic methods, add() and multiply().
Is the array of bytes the most efficient way of storing a long integer?
Constructors
Let us define the following three constructors:
L2: the default constructor that initializes this integer with 0 by calling the constructor in L20.
L10: a copy constructor that initializes this integer with n.
Do the constructors in L10 and L20 call any constructor in the super class?
Arrays.copyOf() is a referenced by the class type Arrays, not an object. Java provides many classes with static methods that are commonly used (e.g., , ).
Can you call non-static methods or fields in the body of a static method?
The static keyword must not be abused to quickly fix compile errors unless it is intended.
Method: set()
Let us define the set() method that takes a string and sets the sign and the value of this integer:
L1-7: javadoc comments.
L4: this method throws if n is null.
When should we use statements over blocks for error handling and vice versa?
This type of method is called a setter. Java encourages making member fields private and creating getters and setters to access the fields for , which is not necessarily encouraged by other languages.
Method: add()
Let us override the add() method that calls two helper methods:
L3-4: adds n to this integer that has the same sign by calling addSameSign().
L5-6: adds n to this integer that has a different sign by calling addDifferentSign().
The following shows an implementation of addSameSign() based on the simple arithmetic:
L7-9: creates the byte array result by copying values in this integer.
L8: the dimension of result can be 1 more than m after the addition.
What are tradeoffs to make the size of result to be m instead of m+1 and vice versa?
The following shows addDifferentSign() that throws :
The implementation of addDifferentSign() is quite similar to addSameSign() although it involves a few more logics. We will leave this as an .
In practice, addSameSign()and addDifferentSign() should be private. We made them protected for exercise purposes.
Method: multiply()
Let us override the multiply() method:
L4: sets the sign after the multiplication.
L7-15: multiplies n to this integer:
What is the worst-case complexity of the multiply() method?
Method: main()
Let us create a runnable class called that contains the main method:
Can we define the main method in LongInteger instead without creating LongIntegerRun?
L2: the parameter args is passed from the command line.
Why does the main method need to be static?
This prints something like the following:
[: one-dimensional array.
L: the element of this array is an object.
java.lang.String
What is the hash code of an object?
Every object implicitly inherits that defines a few member methods including , which gets called automatically by the println() method to retrieve the string representation of this object. We can use the helper method that gives a more readable representation:
How is the Arrays.toString() method implemented?
Since no argument is passed to the main method at the moment, this prints an empty array:
If you set the arguments to 123 -456 using the [Run - Edit Configurations - Program arguments]setting, it prints the following array:
Given those two arguments, we can create two integers:
This prints something like the following, which are returned by a.toString():
How is the toString() method implemented in the Object class?
Method: toString()
To print a more readable representation, we need to override the toString() method in LongInteger:
L5: provides an efficient way of concatenating different data types into one string.
What are the advantages of using StringBuilder instead of concatenating values with the + operator as follows:
Given the overridden method, the above main method now prints the following:
What are the advantages of overriding toString() instead of creating a new method with the same code, and calling the new method to get the string representation of LongInteger?
Method: compareTo()
Java does not allow , so it is not possible to use logical operators to compare the two integers above, a and b:
In fact, any object that is comparable must inherit the interface as follows:
L2: LongInteger is passed to Comparable as a generic type.
Is extends always used to inherit a class whereas implements is used to inherit an interface?
The Comparable interface contains one abstract method called that returns a negative value if this object is smaller than n, a positive value if this object is greater than n, and zero if this object equals to n. The compareTo() method must be overridden by the LongInteger class:
The compareAbs() method compares the absolute values of this and n:
L7: if digits has more dimensions, its absolute value is greater.
L10-13: compares the significant digits iteratively.
Is it safe to use the same variable i to iterate both digits and n.digits?
Once LongInteger properly inherits Comparable by overriding compareTo(), objects instantiated by this class can be compared using many built-in methods.
L2: is a specific implementation of the interface .
All collections in Java inheriting uses generics.
What is the advantage of declaring list as List instead of ArrayList?
What kind of sorting algorithm does Collections.sort() use?
The above code prints the following sorted lists:
What would be the case that needs to distinguish -0 from 0?
super(): calls the corresponding constructor in the super class, SignedNumeral.
Let us define a static nested class Time under PriorityQueueTest that stores runtimes for the add() and remove() methods in any PQ:
What is the advantage of defining static nested class over non-static nested class?
Runtime Estimation
Let us define addRuntime() that estimates the runtime for add() and remove()for a particular PQ:
L5-8: estimates the runtime for add():
L5: gets the snapshot of the starting time using .
Is the approach using currentTimeMillis() a proper way of benchmarking the speed?
We then define benchmark() that estimates the speeds of multiple PQs using the same lists of keys by calling addRuntime():
L1: method declaration:
AbstractPriorityQueue[]: It is unusual to declare an array of objects involving generics in Java (you will see the unique use case of it in the testSpeedAux() method).
Why do we need to benchmark the priority queues multiple times?
Benchmark
Let us define testSpeedAux() that takes multiple PQs and prints out the benchmarking results:
L1: annotates indicating that this method takes vararg parameters.
L2: declares a final method that cannot be overridden by its subclasses.
Why is it recommended to declare the method final if it takes vararg parameters?
Why does JVM need to be warmed-up before the actual benchmarking?
Why should you use StringJoiner instead of concatenating strings with the + operator?
Speed Comparison
The followings show runtime comparisons between LazyPQ, EagerPQ, and BinaryHeap:
public class LongInteger extends SignedNumeral<LongInteger> {
/** The values of this integer (excluding the sign). */
protected byte[] digits;
...
/** Creates a long integer with the default value of "0". */
public LongInteger() {
this("0");
}
/**
* Creates a long integer by copying the specific object.
* @param n the object to be copied.
*/
public LongInteger(LongInteger n) {
super(n.sign);
digits = Arrays.copyOf(n.digits, n.digits.length);
}
/**
* Creates a long integer with the specific sign and values.
* @param n the sign and values to be set.
* @see #set(String)
*/
public LongInteger(String n) {
set(n);
}
/**
* Sets the sign and values of this integer.
* @param n the sign and values to be set.
* @throws NullPointerException when `n` is null.
* @throws InvalidParameterException when `n` contains non-digit character
* except for the first character that can be [+-\d].
*/
public void set(String n) {
// 'n' must not be null
if (n == null)
throw new NullPointerException();
// set this.sign
sign = switch (n.charAt(0)) {
case '-' -> { n = n.substring(1); yield Sign.NEGATIVE; }
case '+' -> { n = n.substring(1); yield Sign.POSITIVE; }
default -> Sign.POSITIVE;
};
// set this.digits
digits = new byte[n.length()];
for (int i = 0, j = n.length() - 1; i < n.length(); i++, j--) {
byte v = (byte)(n.charAt(i) - 48);
if (0 > v || v > 9) {
String s = String.format("%d is not a valid value", v);
throw new InvalidParameterException(s);
}
digits[j] = v;
}
}
@Override
public void add(LongInteger n) {
if (sign == n.sign)
addSameSign(n);
else
addDifferentSign(n);
}
/**
* Adds the specific integer that has the same sign as this integer.
* @param n the integer to be added with the same sign.
*/
protected void addSameSign(LongInteger n) {
// copy this integer to result[]
int m = Math.max(digits.length, n.digits.length);
byte[] result = new byte[m + 1];
System.arraycopy(digits, 0, result, 0, digits.length);
// add n to result
for (int i = 0; i < n.digits.length; i++) {
if (i < n.digits.length)
result[i] += n.digits[i];
if (result[i] >= 10) {
result[i] -= 10;
result[i + 1] += 1;
}
}
// set this.digits
digits = result[m] == 0 ? Arrays.copyOf(result, m) : result;
}
/**
* Adds the specific integer that has a different sign from this integer.
* @param n the integer to be added with a different sign
*/
protected void addDifferentSign(LongInteger n) {
throw new UnsupportedOperationException();
}
@Override
public void multiply(LongInteger n) {
// set this.sign
sign = (sign == n.sign) ? Sign.POSITIVE : Sign.NEGATIVE;
// multiply this and n and save it to result
byte[] result = new byte[digits.length + n.digits.length];
for (int i = 0; i < digits.length; i++) {
for (int j = 0; j < n.digits.length; j++) {
int k = i + j, prod = digits[i] * n.digits[j];
result[k] += prod;
result[k + 1] += result[k] / 10;
result[k] %= 10;
}
}
// set this.digits
int m; for (m = result.length - 1; m > 0; m--)
if (result[m] != 0) break;
digits = ++m < result.length ? Arrays.copyOf(result, m) : result;
}
public class LongIntegerRun {
static public void main(String[] args) {
System.out.println(args);
}
}
[Ljava.lang.String;@d716361
static public void main(String[] args) {
System.out.println(Arrays.toString(args));
}
[]
[123, -456]
static public void main(String[] args) {
LongInteger a = new LongInteger(args[0]);
LongInteger b = new LongInteger(args[1]);
System.out.println(a);
System.out.println(b);
}
public class LongInteger extends SignedNumeral<LongInteger> {
...
@Override
public String toString() {
StringBuilder build = new StringBuilder();
if (sign == Sign.NEGATIVE) build.append("-");
for (int i = digits.length - 1; i >= 0; i--)
build.append(digits[i]);
return build.toString();
}
...
String s = "";
if (sign == Sign.NEGATIVE) s += "-";
for (int i = digits.length - 1; i >= 0; i--)
s += digits[i];
return s;
123
-456
boolean c = a < b; // gives a compile error
public class LongInteger extends SignedNumeral<LongInteger>
implements Comparable<LongInteger> {
...
}
@Override
public int compareTo(LongInteger n) {
if (isPositive())
return n.isNegative() ? 1 : compareAbs(n);
else
return n.isPositive() ? -1 : -compareAbs(n);
}
/**
* @param n the object to be compared.
* @return a negative integer, zero, or a positive integer as the absolute value of this object is
* less than, equal to, or greater than the absolute value of the specified object.
*/
public int compareAbs(LongInteger n) {
int diff = digits.length - n.digits.length;
if (diff == 0) {
for (int i = digits.length - 1; i >= 0; i--) {
diff = digits[i] - n.digits[i];
if (diff != 0) break;
}
}
return diff;
}
static public void main(String[] args) {
List<LongInteger> list = new ArrayList<>();
list.add(new LongInteger("78"));
list.add(new LongInteger("-45"));
list.add(new LongInteger("0"));
list.add(new LongInteger("6"));
list.add(new LongInteger("-0"));
list.add(new LongInteger("-123"));
list.sort(Comparator.naturalOrder());
System.out.println(list);
list.sort(Comparator.reverseOrder());
System.out.println(list);
}
Supplier: passes a function as a parameter that returns a key of the generic type T.
L2: generates an array of Time using several stream operations. The dimension of times[] is the same as the dimension of queues such that times[i] accumulates the speeds taken by the queue[i], respectively.
: creates a stream specified by the supplier.
: creates a stream with a specific size.
: returns an array of the specific type.
L4: benchmarks the PQs multiple times as specified by iter.
L5: generates the list of keys specified by the supplier sup.
L6-7: estimate the runtimes by using the same list of keys for each PQ.
It can take a 0-to-many number of abstract PQs.
The type of queues is AbstractPriorityQueue<Integer>[] such that it can be directly passed to the benchmark() method.
<T extends Comparable<T>> void addRuntime(AbstractPriorityQueue<T> queue, Time time, List<T> keys) {
long st, et;
// runtime for add()
st = System.currentTimeMillis();
keys.forEach(queue::add);
et = System.currentTimeMillis();
time.add += et - st;
// runtime for remove()
st = System.currentTimeMillis();
while (!queue.isEmpty()) queue.remove();
et = System.currentTimeMillis();
time.remove += et - st;
}
<T extends Comparable<T>> Time[] benchmark(AbstractPriorityQueue<T>[] queues, int size, int iter, Supplier<T> sup) {
Time[] times = Stream.generate(Time::new).limit(queues.length).toArray(Time[]::new);
for (int i = 0; i < iter; i++) {
List<T> keys = Stream.generate(sup).limit(size).collect(Collectors.toList());
for (int j = 0; j < queues.length; j++)
addRuntime(queues[j], times[j], keys);
}
return times;
}
@SafeVarargs
final void testRuntime(AbstractPriorityQueue<Integer>... queues) {
final int begin_size = 1000;
final int end_size = 10000;
final int inc = 1000;
final Random rand = new Random();
for (int size = begin_size; size <= end_size; size += inc) {
// JVM warm-up
benchmark(queues, size, 10, rand::nextInt);
// benchmark all priority queues with the same keys
Time[] times = benchmark(queues, size, 1000, rand::nextInt);
StringJoiner joiner = new StringJoiner("\t");
joiner.add(Integer.toString(size));
joiner.add(Arrays.stream(times).map(t -> Long.toString(t.add)).collect(Collectors.joining("\t")));
joiner.add(Arrays.stream(times).map(t -> Long.toString(t.remove)).collect(Collectors.joining("\t")));
System.out.println(joiner.toString());
}
}
Let us create PriorityQueueTest and define testRobustnessAux() that checks the robustness of any PQ inheriting AbstractPriorityQueue:
L6: the generic type T is defined specifically for this method such that the priority queue pq, the list keys, and the comparator comp take the same type T that is comparable.
L7: any collection that inherits the interface has the member method that takes a and applies each key in the collection to the consumer.
L8: any collection has the member method that returns the of the collection.
: creates a stream of the collection whose keys are sorted
: creates a collection specified by the
L9: iterates each of the sorted keys and compares it to the returned value of pq.remove().
What are the advantages of defining a method-level generic type?
Functional Programming
The following code shows a traditional way of iterating over a list (that is equivalent to L7 above):
Java 5 introduced an enhanced for loop that simplified the traditional for loop:
Java 8 introduced that enabled functional programming in Java. The following code takes each key (as a variable) in keys and applies it to pq.add():
The syntax of the above code can be simplified as follows (as shown in L7):
What are the main differences between object-oriented programming and functional programming?
Since Java 8, higher-order methods can be defined by parameterizing types of interfaces in the package.
Test: Robustness
Let us define the testRobustness() method that calls the auxiliary method testRobustnessAux():
L7-9: tests different types of max-PQs. The keys need to be sorted in reverse order for it to test the remove() method.
L11-13: tests different types of min-PQs. The keys need to be sorted in the natural order for it to test the remove() method.
The generic types of the PQs in L4-5 are explicitly coded as <Integer>, whereas they are simplified to <> in L7-13. When do generic types need to be explicitly coded?
The testRobustness() method illustrates the benefit of defining AbstractPriorityQueue such that any type of PQ can be passed to testRobustnessAux() for unit-testing.
/**
* @param pq a priority queue.
* @param keys a list of comparable keys.
* @param comp a comparator used for sorting.
*/
<T extends Comparable<T>> void testRobustness(AbstractPriorityQueue<T> pq, List<T> keys, Comparator<T> comp) {
keys.forEach(pq::add);
keys = keys.stream().sorted(comp).collect(Collectors.toList());
keys.forEach(key -> assertEquals(key, pq.remove()));
}
.
: returns a collector that transforms the stream into a list.
Divide the problem into sub-problems (recursively).
Conquer sub-problems, which effectively solve the super problem.
Why do people ever want to use QuickSort?
Merge Sort
Divide the input array into two sub-arrays.
Sort each of the sub-arrays and merge them into the back.
Let us create the class inheriting AbstractSort:
L2: holds the copy of the input array.
Let us then override the sort() method that calls the helper method:
L4-5: increases the size of the temp array if necessary.
L5: unchecked type Object to T[].
What is the advantage of declaring the member field temp?
The helper method can be defined as follows:
L11: sorts the left sub-array.
L12: sorts the right sub-array.
L13: merges the left and right sub-arrays.
Finally, the merge() method can be defined as follows:
L10-11: copies the input array to the temporary array and counts the assignments.
L14-15: no key left in the 1st half.
L16-17
How many assignments are made for the number of keys by the above version of MergeSort?
Quick Sort
Pick a pivot key in the input array.
Exchange keys between the left and right partitions such that all keys in the left and right partitions are smaller or bigger than the pivot key, respectively.
Repeat this procedure in each partition, recursively.
Let us create the class inheriting AbstractSort:
Let us then override the sort() method:
L3: stops when the pointers are crossed.
L6: sorts the left partition.
L7: sorts the right partition.
The partition() method can be defined as follows:
L5: finds the left pointer where endIndex > fst > pivot.
L6: finds the right pointer where beginIndex < snd
The programming design in L5 and L6 are not ideal since the while loops do not include anybody that can confuse other programmers.
Intro Sort
Although Quick Sort is the fastest on average, the worst-case complexity is .
sorting algorithms that guarantee faster worst-case complexities than Quick Sort:
Quick Sort for random cases and a different algorithm for the worst case.
How can we determine if Quick Sort is meeting the worse-case?
Let us define the IntroSoft class inheriting QuickSort:
L2: declares a sorting algorithm to handle the worst cases.
L14: resets the counters for both the main and auxiliary sorting algorithms.
We then override the sort() method by passing the maximum depth to the auxiliary method:
L9: returns as the maximum depth.
Finally, the auxiliary method sort() can be defined as follows:
L4-5: switches to the other sorting algorithm if the depth of the partitioning exceeds the max depth.
Does the max-depth need to be set to ?
Benchmarks
The following shows runtime speeds, assignment costs, and comparison costs between several sorting algorithms for the random, best, and worst cases.
Average
: no key left in the 2nd half.
L18-19: the 2nd key is greater than the 1st key.
L20-21: the 1st key is greater than or equal to the 2nd key.
<
pivot
.
L7: the left and right pointers are crossed.
L8: swaps between keys in the left and right partitions.
public class MergeSort<T extends Comparable<T>> extends AbstractSort<T> {
private T[] temp;
public MergeSort() {
this(Comparator.naturalOrder());
}
public MergeSort(Comparator<T> comparator) {
super(comparator);
}
}
@Override
@SuppressWarnings("unchecked")
public void sort(T[] array, int beginIndex, int endIndex) {
if (temp == null || temp.length < array.length)
temp = (T[])Array.newInstance(array[0].getClass(), array.length);
sort(array, temp, beginIndex, endIndex);
}
/**
* @param input the input array.
* @param temp the array to hold the copy of the input array.
* @param beginIndex the beginning index of the 1st half (inclusive).
* @param endIndex the ending index of the 2nd half (exclusive).
*/
protected void sort(T[] input, T[] copy, int beginIndex, int endIndex) {
if (beginIndex + 1 >= endIndex) return;
int middleIndex = Utils.getMiddleIndex(beginIndex, endIndex);
sort(input, copy, beginIndex, middleIndex);
sort(input, copy, middleIndex, endIndex);
merge(input, copy, beginIndex, middleIndex, endIndex);
}
/**
* @param input the input array.
* @param temp the array to hold the copy of the input array.
* @param beginIndex the beginning index of the 1st half (inclusive).
* @param middleIndex the ending index of the 1st half (exclusive).
* @param endIndex the ending index of the 2nd half (exclusive).
*/
protected void merge(T[] input, T[] copy, int beginIndex, int middleIndex, int endIndex) {
int fst = beginIndex, snd = middleIndex, n = endIndex - beginIndex;
System.arraycopy(input, beginIndex, copy, beginIndex, n);
assignments += n;
for (int k = beginIndex; k < endIndex; k++) {
if (fst >= middleIndex)
assign(input, k, copy[snd++]);
else if (snd >= endIndex)
assign(input, k, copy[fst++]);
else if (compareTo(copy, fst, snd) < 0)
assign(input, k, copy[fst++]);
else
assign(input, k, copy[snd++]);
}
}
public class QuickSort<T extends Comparable<T>> extends AbstractSort<T> {
public QuickSort() {
this(Comparator.naturalOrder());
}
public QuickSort(Comparator<T> comparator) {
super(comparator);
}
}
@Override
public void sort(T[] array, int beginIndex, int endIndex) {
if (beginIndex >= endIndex) return;
int pivotIndex = partition(array, beginIndex, endIndex);
sort(array, beginIndex, pivotIndex);
sort(array, pivotIndex + 1, endIndex);
}
protected int partition(T[] array, int beginIndex, int endIndex) {
int fst = beginIndex, snd = endIndex;
while (true) {
while (++fst < endIndex && compareTo(array, beginIndex, fst) >= 0);
while (--snd > beginIndex && compareTo(array, beginIndex, snd) <= 0);
if (fst >= snd) break;
swap(array, fst, snd);
}
swap(array, beginIndex, snd);
return snd;
}
public class IntroSort<T extends Comparable<T>> extends QuickSort<T> {
private final AbstractSort<T> engine;
public IntroSort(AbstractSort<T> engine) {
this(engine, Comparator.naturalOrder());
}
public IntroSort(AbstractSort<T> engine, Comparator<T> comparator) {
super(comparator);
this.engine = engine;
}
@Override
public void resetCounts() {
super.resetCounts();
if (engine != null) engine.resetCounts();
}
}
@Override
public void sort(T[] array, int beginIndex, int endIndex) {
final int maxdepth = getMaxDepth(beginIndex, endIndex);
sort(array, beginIndex, endIndex, maxdepth);
comparisons += engine.getComparisonCount();
assignments += engine.getAssignmentCount();
}
protected int getMaxDepth(int beginIndex, int endIndex) {
return 2 * (int)Utils.log2(endIndex - beginIndex);
}
private void sort(T[] array, int beginIndex, int endIndex, int maxdepth) {
if (beginIndex >= endIndex) return;
if (maxdepth == 0) // encounter the worst case
engine.sort(array, beginIndex, endIndex);
else {
int pivotIndex = partition(array, beginIndex, endIndex);
sort(array, beginIndex, pivotIndex, maxdepth - 1);
sort(array, pivotIndex + 1, endIndex, maxdepth - 1);
}
}
O(nlogn)
O(nlogn)
O(nlogn)
O(nlogn)
O(nlogn)
5.1. Concept
This section gives an overview of tries.
Overview
A trie is a tree where each node has:
0-to-many children,
A key whose type is character,
A value that can be any type of object, and
An end-state that indicates if the node and its ancestors together represent the end of a certain word.
Let us consider the following list of strings:
Given the strings as keys, a binary search tree can be constructed as follows using a balancing algorithm:
How many character comparisons does it need to make to search a string in a balanced BST?
With the same list of strings, a trie can be constructed as follows:
1st cell: key (a character).
2nd cell: value (the index of the string that the node represents).
3rd cell: end-state (T for true, F for false).
What is the worst-case complexity of searching a string in a trie?
This section provides exercises for better understanding in tries.
Let L be a list of country names in String where spaces are allowed (e.g., "United States", "South Korea"). Consider a trie where all country names in L and their unique IDs are put as key-value pairs as follows:
Implementation
Create the class under the package that inherits by passing Integer as the generic type.
Update the getEntities() method that takes an input string and returns the list of , where each entity consists of the begin index (inclusive) and end index (exclusive) of the first and the last characters of the corresponding country name respectively as well as the ID of the country name.
Report
Write a report that briefly describe your approach and explains the worst-case complexity of your approach, and save it as quiz5.pdf.
Notes
Substring matching of country names is not required. If your dictionary has "United States" as a country name and the input string contains "United Nation", the "United" should not be matched as a country name.
Substring matching within input words are expected. If your dictionary has "America" as a country name and the input contains "American", the first 7 characters, "America"
See TrieQuizTest for an example of how to unit-test your approach.
should be recognized as a country name.
The worst-case complexity needs to be explained in terms of the number of characters n in the input string.
Assume that the method in the DisjointSet class uses the baseline approach:
A disjoint set can be represented by a tree. Update the method in the DisjointSetQuiz class that would result the following tree:
Report
Write a report quiz6.pdf that includes the followings:
Describe how the values in the array changes after each call in the main() method.
Describe how the values in the array would change after calling find(0) once all keys are added as above, assuming that the find() method in DisjointSet class uses the efficient approach:
6.2. Implementation
This sections discusses the implementation of disjoint sets.
L2: the size of subset (-1 implies 1 ID, -2 implies 2 IDs, and so on).
L5-6: every set is initialized with the size of 1.
L9: a copy constructor.
Let us define the find() method:
L2: returns the ID of the subset where the specific key belongs to.
What is the worst-case complexity of the find() method?
We then define the inSameSet() method:
L2: returns true if the two specific keys are in the same set.
Finally, let us define the union() method:
L2-4: return the subset ID where both key1 and key2 belongs to.
L6-10: merges the set containing key2 to the set containing key1.
7.1. Implementation
This section describes how to implement a graph structure.
Types of Graphs
There are several types of graphs:
Can we represent undirected graphs using an implementation of directed graphs?
Edge
Let us create the class representing a directed edge under the package:
L1: inherits the interface.
L2-3: the source and target vertices are represented by unique IDs in int.
Let us the define the init() method, getters, and setters:
Let us override the compareTo() method that compares this edge to another edge by their weights:
L4: returns 1 if the weight of this edge is greater.
L5: returns -1 if the weight of the other edge is greater.
Graph
Let us create the class under the package:
L2: a list of edge lists where each dimension of the outer list indicates a target vertex and the inner list corresponds to the list of incoming edges to that target vertex.
L5: creates an empty edge list for each target vertex.
L9
For example, a graph with 3 vertices 0, 1, and 2 and 3 edges 0 -> 1, 2 -> 1, and 0 -> 2, the incoming_edges is as follows:
Let us define setters for edges:
L2-4: retrieves the incoming edge list of target, and adds the new edge to the edge list.
L9-10: add edges to both directions.
Let us then define getters:
L6: uses the method that merges the list of edge lists into one list of edges.
L10: uses the and methods to find vertices with no incoming edges.
What is the worst-case complexity of the getVerticesWithNoIncomingEdges() method?
Let us define the getOutgoingEdges() method that returns the list of outgoing edges:
L1: returns a list of edge deque, where each dimension in the outer list represents the deque of outgoing edges for the corresponding source vertex.
L2: generates the list of empty edge deques.
L4-7
What is the worst-case complexity of the getOutgoingEdges() method?
public class DisjointSet {
private final int[] subsets;
public DisjointSet(int size) {
subsets = new int[size];
Arrays.fill(subsets, -1);
}
public DisjointSet(DisjointSet set) {
subsets = Arrays.copyOf(set.subsets, set.subsets.length);
}
}
L11-15: merges the set containing key1 to the set containing key2.
publicintfind(int id){return(subsets[id]<0)? id :find(subsets[id]);}
publicintfind(int id){return(subsets[id]<0)? id :(subsets[id]=}
L10: constructor overwriting.
L14: copy constructor.
L6: returns 0 is the weights of both edges are the same.
: copies the list of edge lists from
g
to this graph.
L13: returns true if all incoming edge lists are empty using the allMatch() method.
L17: the size of the graph is the number of vertices in the graph.
: visits every target vertex to retrieve the incoming edge lists, and assigns edges to appropriate source vertices.
public boolean inSameSet(int key1, int key2) {
return find(key1) == find(key2);
}
public int union(int key1, int key2) {
int r1 = find(key1);
int r2 = find(key2);
if (r1 == r2) return r1;
if (subsets[r1] < subsets[r2]) {
subsets[r1] += subsets[r2];
subsets[r2] = r1;
return r1;
}
else {
subsets[r2] += subsets[r1];
subsets[r1] = r2;
return r2;
}
}
public class Edge implements Comparable<Edge> {
private int source;
private int target;
private double weight;
public Edge(int source, int target, double weight) {
init(source, target, weight);
}
public Edge(int source, int target) {
this(source, target, 0);
}
public Edge(Edge edge) {
this(edge.getSource(), edge.getTarget(), edge.getWeight());
}
}
private void init(int source, int target, double weight) {
setSource(source);
setTarget(target);
setWeight(weight);
}
public int getSource() { return source; }
public int getTarget() { return target; }
public double getWeight() { return weight; }
public void setSource(int vertex) { source = vertex; }
public void setTarget(int vertex) { target = vertex; }
public void setWeight(double weight) { this.weight = weight; }
public void addWeight(double weight) { this.weight += weight; }
@Override
public int compareTo(Edge edge) {
double diff = weight - edge.weight;
if (diff > 0) return 1;
else if (diff < 0) return -1;
else return 0;
}
public class Graph {
private final List<List<Edge>> incoming_edges;
public Graph(int size) {
incoming_edges = Stream.generate(ArrayList<Edge>::new).limit(size).collect(Collectors.toList());
}
public Graph(Graph g) {
incoming_edges = g.incoming_edges.stream().map(ArrayList::new).collect(Collectors.toList());
}
public boolean hasNoEdge() {
return IntStream.range(0, size()).allMatch(i -> getIncomingEdges(i).isEmpty());
}
public int size() {
return incoming_edges.size();
}
}
incoming_edges.set(0, new ArrayList());
incoming_edges.set(1, new ArrayList(new Edge(0, 1), new Edge(2, 1));
incoming_edges.set(2, new ArrayList(new Edge(0, 2)));
public Edge setDirectedEdge(int source, int target, double weight) {
List<Edge> edges = getIncomingEdges(target);
Edge edge = new Edge(source, target, weight);
edges.add(edge);
return edge;
}
public void setUndirectedEdge(int source, int target, double weight) {
setDirectedEdge(source, target, weight);
setDirectedEdge(target, source, weight);
}
public List<Edge> getIncomingEdges(int target) {
return incoming_edges.get(target);
}
public List<Edge> getAllEdges() {
return incoming_edges.stream().flatMap(List::stream).collect(Collectors.toList());
}
public Deque<Integer> getVerticesWithNoIncomingEdges() {
return IntStream.range(0, size()).filter(i -> getIncomingEdges(i).isEmpty()).boxed().collect(Collectors.toCollection(ArrayDeque::new));
}
public List<Deque<Edge>> getOutgoingEdges() {
List<Deque<Edge>> outgoing_edges = Stream.generate(ArrayDeque<Edge>::new).limit(size()).collect(Collectors.toList());
for (int target = 0; target < size(); target++) {
for (Edge incoming_edge : getIncomingEdges(target))
outgoing_edges.get(incoming_edge.getSource()).add(incoming_edge);
}
return outgoing_edges;
}
public int find(int id) {
return (subsets[id] < 0) ? id : find(subsets[id]);
}
public int find(int id) {
return (subsets[id] < 0) ? id : (subsets[id] = find(subsets[id]));
}
find
(
subsets
[
id
]));
7.2. Cycle Detection
This section describes an algorithm to detect a cycle in a graph.
A cycle in a graph can be detected by traversing through the graph:
Let us define the containsCycle() method under the Graph class that returns true if the graph contains any cycle; otherwise, false:
public boolean containsCycle() {
Deque<Integer> notVisited = IntStream.range(0, size()).boxed().collect(Collectors.toCollection(ArrayDeque::new));
while (!notVisited.isEmpty()) {
if (containsCycleAux(notVisited.poll(), notVisited, new HashSet<>()))
return true;
}
return false;
}
L2: initially all vertices are not visited.
L4: iterates until all vertices are visitied:
L5-6: if the recursive call finds a cycle, returns true.
What is the worst-case complexity of the containsCycle() method?
L2-3: marks the target vertex visited.
L5: for each incoming edge of the target vertex:
Why do we need to pass the new HashSet for every call in L5?
L6-7
: returns true if the source vertex of this edge has seen before.
L9-10: returns true if the recursive call finds a cycle.
private boolean containsCycleAux(int target, Deque<Integer> notVisited, Set<Integer> visited) {
notVisited.remove(target);
visited.add(target);
for (Edge edge : getIncomingEdges(target)) {
if (visited.contains(edge.getSource()))
return true;
if (containsCycleAux(edge.getSource(), notVisited, new HashSet<>(visited)))
return true;
}
return false;
}
8.5. Quiz
This section provides exercises for better understanding of minimum spanning trees.
Complexity
Explain the worst-case complexities of the following algorithms in terms of V and E according to our implementations:
Prim's algorithm
Kruskal's algorithm
Chu-Liu-Edmonds' algorithm
Comparison
Provide an example of a graph where Prim's and Kruskal's algorithms find different minimum spanning trees from the same graph and explain how these trees are found. If you cannot find an example, explain why these algorithms always find the same minimum spanning tree given the same graph.
Different MSTs can be found from the same graph only if there are multiple edges with the minimum weight for any of which can be polled from the priority queue. Consider cases where the compareTo() method is overridden differently from the original implementation.
Report
Write a report quiz7.pdf that includes the complexity and comparison analyses.
9.3. Simplex Algorithm
Max-Flow Min-Cut Theorem
Let S - T cut be a set of edges whose removal disconnects any path between S and T:
What is the relationship between max-flow and min-cut?
This section provides exercises for better understanding in dynamic programming.
Tower of Hanoi
Write a report quiz9.pdf that includes answers to the followings.
As n increases from 1 to 10, how many times does the auxiliary solve() method get called recursively in and ?
Is there clear patterns between n and the number of the method calls made by these classes? Explain the patterns if exist.
Longest Common Subsequence
Include answers to the followings in quiz9.pdf:
Explain what the values of the dynamic table mean in the class.
LCSDynamic pre-populates the dynamic table before making any recursive calls. Is it possible to find a LCS with dynamic programming by populating the dynamic table while making recursive class.
You may need a different type of a dynamic table to populate it while making recursive calls.
Extra Credit
Create the class under the package.
Update the solveAll() that returns all longest common subsequences between two strings.
0. Getting Started
This chapter helps you set up the development environment for this course.
Associate Professor of Computer Science
Office Hours → MW 4PM - 5:30PM, MSC W302F
BS in Computer Science; BA in Physics and Astronomy
Office Hours → TuTh 10:30AM - 12PM, MSC E308
BS in Computer Science and Economics
Office Hours -> MW 2:30PM - 4PM, MSC E308
Grading
1 + 10 topical quizzes: 70%
3 homework assignments: 30%
Your work is governed by the . Honor code violations (e.g., copies from any source, including colleagues and internet sites) will be referred to the .
Notes
For every topic, one quiz will be assigned to check if you keep up with the materials.
Homework assignments assess conceptual understanding, programming ability, and analytical writing skills relevant to this course.
All quizzes and assignments must be submitted individually. Discussions are allowed; however, your work must be original.
0.2. Quiz
Quiz 0: Getting Started
Coding
Right-click on the directory under the project and create the package . Right-click on the utils package and create the Java class :
Zinc Zhao
BS in Computer Science; BA in Music
Office Hours → TuTh 1PM - 2:30PM, MSC E308
Excuses for exam absence/rescheduling and other serious personal events (health, family, personal related, etc.) that affect course performance must be accompanied by a letter from the Office of Undergraduate Education.
Late submissions within a week will be accepted with a grading penalty of 15% and will not be accepted once the solutions are discussed in class.
Run the program by clicking [Run -> Run]. If you see 5 on the output pane, your program runs successfully.
Testing
Open build.gradle and add the following configurations (if not already), which would allow you to perform JUnit Testing:
Right-click on the src/test/java directory under the project and create the package edu.emory.cs.utils. Right-click on the utils package and create the Java class UtilsTest:
Add UtilsTest.java to Git.
Add the following method to the UtilsTest class. Make sure to include all imports:
Run the test by clicking [Run -> Run]. If you see the test passed, your unit test runs successfully.
Submission
Add the instructors as collaborators in your GitHub repository:
Jinho Choi: jdchoi77
Peilin Wu: qualidea1217
Jeongrok Yu: jeongrok
Zinc Zhao: ZincZhao
2. Commit and push the following to your GitHub repository:
Although Java 17 is not the most recent version, it is the latest long-term support (LTS) release, which is preferred.
Version Control
Install Git using any of the following instructions:
Run the following commands on a terminal by replacing user.email and user.name with your email address and name:
Integrated Development Environment
Install the latest version of on your local machine:
The recommended version: 2022.3.x (Ultimate Edition)
Apply for the with your school email address to use the ultimate version.
Even if you already have an IDE that you are familiar with for Java programming, we strongly recommend you use IntelliJ because provides IDEs for many popular programming languages with similar interfaces, which makes it easier for you to adapt.
Project Management
Launch IntelliJ and create a project by clicking the [New Project] button at the top:
Name: dsa-java
Location: local_path/dsa-java
Check "Create Git repository"
For JDK, you should be able to see version 17 if it is properly installed. If you cannot find the version, click [Add JDK] and select the following directory.
Windows: C:\Program Files\Java\jdk-17.x.x
Open and make sure distributionUrl indicates the latest version of Gradle:
Click [Settings - Build, Execution, Deployment] on the menu:
Click [Build Tools - Gradle] and set Gradle JVM to 17.
Click [Compiler - Java Compiler] and set Project bytecode version to 17.
Click [File - Project Structure] and select [Project Settings]:
Click [Project Settings - Project] and set SDK to 17 and Project language level to SDK default.
Click [Project Settings - Modules - Dependencies] and set Module SDK to 17.
Open and make sure sourceCompatibility and targetCompatibility are set to java version 17 (add the following configurations if they do not exist already):
Lastly, check mavenCentral() is configured as a repository in your build.gradle:
There is another popular build tool called . However, we will use Gradle for this course because it is faster and simpler to build a Java-based project.
GitHub Integration
To integrate the project with your repository, click [Settings]:
Choose [Version Control - Github] on the left pane.
Click [+] and login with your GitHub ID and password.
If you use two-factor authentication, log in with your .
Create under the project and add the following contents:
Click [Git - GitHub - Share Project on Github] and create a repository:
Make sure to check private.
Repository name: dsa-java
Remote: origin
Add all files and make the initial commit. Check if the repository is created under your GitHub account: https://github.com/your_id/dsa-java.
We recommend you create a GitHub account with your school email address, allowing you to add unlimited collaborators to the repository.
static public int getMiddleIndex(int beginIndex, int endIndex) {
return beginIndex + (endIndex - beginIndex) / 2;
}
static public void main(String[] args) {
System.out.println(getMiddleIndex(0, 10));
}
Please follow every example described in this section. Programming is an act of writing, not reading. By the end of this chapter, you should be able to reproduce the entire codebase yourself from scratch without consulting those examples.
2. Priority Queues
This chapter discusses different types of priority queues and benchmarks their performance in terms of the worst-case complexities.
Contents
1.3. Unit Testing
LongInteger: unit tests.
Test: LongInteger()
Let us create a testing class called and make a for the constructors:
L6: the @Test annotation indicates that this method is used for unit testing.
L7: methods used for unit testing must be public.
L8: tests the default constructor
assertEquals(): compares two parameters where the left parameter is the expected value and the right parameter is the actual value.
L12-15: tests the constructor with a string parameter.
L18-19: tests the copy constructor.
When should we use import static instead of import?
When you run this test, you see a prompt similar to the followings:
Test: multiply()
Let us define another method for testing the multiply() method:
L11-12: a can hold the integer 152415787517146788750190521 (≈287), which is much larger than the maximum value of long that is 263−1.
Test: compareTo()
Let us define a method for testing the compareTo() method:
assertTrue(): passes if the parameter returns true.
Unit testing provides an effective way of ensuring the correctness of your program. Making a unit test for every method is standard practice, although this standard is often dismissed due to time pressure.
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class LongIntegerTest {
@Test
public void testConstructors() {
// default constructor
assertEquals("0", new LongInteger().toString());
// constructor with a string parameter
assertEquals("12", new LongInteger("12").toString());
assertEquals("34", new LongInteger("+34").toString());
assertEquals("-56", new LongInteger("-56").toString());
assertEquals("-0", new LongInteger("-0").toString());
// copy constructor
assertEquals("12", new LongInteger(new LongInteger("12")).toString());
assertEquals("-34", new LongInteger(new LongInteger("-34")).toString());
}
}
@Test
public void testCompareTo() {
assertTrue(0 < new LongInteger("0").compareTo(new LongInteger("-0")));
assertTrue(0 > new LongInteger("-0").compareTo(new LongInteger("0")));
assertTrue(0 < new LongInteger("12").compareTo(new LongInteger("-34")));
assertTrue(0 > new LongInteger("-12").compareTo(new LongInteger("34")));
assertTrue(0 > new LongInteger("-34").compareTo(new LongInteger("12")));
assertTrue(0 < new LongInteger("34").compareTo(new LongInteger("-12")));
}
Preface
Jinho D. Choi
This is an advanced programming course in Computer Science that teaches how to design efficient structures and algorithms to process big data and methods to benchmark their performance for large-scale computing. Topics cover data structures such as priority queues, binary trees, tries, and graphs and their applications in constructing algorithms such as sorting, searching, balancing, traversing, and spanning. Advanced topics such as network flow and dynamic programming are also discussed. Throughout this course, students are expected to
Have a deep conceptual understanding of various data structures and algorithms.
1.1. Abstraction
Different types of objects and inheritances in Java.
Class
A is a template to instantiate an .
What is the relationship between a class and an object?
Let us create a class called
3. Sorting Algorithms
This chapter discusses different types of sorting algorithms and benchmarks their performance in terms of comparisons and assignments.
Contents
3.1. Abstraction
The abstract class for all sorting algorithms.
Abstract Sort
Let us create an abstract class :
L2-4
Implement their conceptual understanding in a programming language.
Explore the most effective structures and algorithms for given tasks.
Properly assess the quality of their implementations.
There are topical quizzes and homework assignments that require sufficient skills in Java programming, Git version control, Gradle software project management, and scientific writing. Intermediate-level Java programming is a prerequisite of this course.
public abstract class AbstractSort<T extends Comparable<T>> {
private final Comparator<T> comparator;
protected long comparisons;
protected long assignments;
/** @param comparator specifies the precedence of comparable keys. */
public AbstractSort(Comparator<T> comparator) {
this.comparator = comparator;
resetCounts();
}
/** @return the total number of comparisons performed during sort. */
public long getComparisonCount() {
return comparisons;
}
/** @return the total number of assignments performed during sort. */
public long getAssignmentCount() {
return assignments;
}
public void resetCounts() {
comparisons = assignments = 0;
}
}
/**
* @param array an array of comparable keys.
* @param i the index of the first key.
* @param j the index of the second key.
* @return array[i].compareTo(array[j]).
*/
protected int compareTo(T[] array, int i, int j) {
comparisons++;
return comparator.compare(array[i], array[j]);
}
/**
* array[index] = value.
* @param array an array of comparable keys.
* @param index the index of the array to assign.
* @param value the value to be assigned.
*/
protected void assign(T[] array, int index, T value) {
assignments++;
array[index] = value;
}
/**
* Swaps array[i] and array[j].
* @param array an array of comparable keys.
* @param i the index of the first key.
* @param j the index of the second key.
*/
protected void swap(T[] array, int i, int j) {
T t = array[i];
assign(array, i, array[j]);
assign(array, j, t);
}
/**
* Sorts the array in ascending order.
* @param array an array of comparable keys.
*/
public void sort(T[] array) {
sort(array, 0, array.length);
}
/**
* Sorts the array[beginIndex:endIndex].
* @param array an array of comparable keys.
* @param beginIndex the index of the first key to be sorted (inclusive).
* @param endIndex the index of the last key to be sorted (exclusive).
*/
abstract public void sort(T[] array, int beginIndex, int endIndex);
that we want to be a super class of all numeral types:
L1: packageindicates the name of the package that this class belongs to in a hierarchy.
What are the acceptable access-level modifiers to declare a top-level class?
Let us declare a method, add() , that is an operation expected by all numeral types:
L4: @param adds a javadoc comment about the parameter.
The issue is that we cannot define the methods unless we know what specific numeral type this class should implement; in other words, it is too abstract to define those methods. Thus, we need to declare Numeral as a type of abstract class.
What are the advantages of havingNumeral as a super class of all numeral types?
There are two types of abstract classes in Java, abstract class and interface.
Can an object be instantiated by an abstract class or an interface?
All methods in an interface are public that does not need to be explicitly coded.
Abstract methods in an interface are declared without their bodies.
Who defines the bodies of the abstract methods?
Let us create a new interface called SignedNumeral that inherits Numeral and adds two methods, flipSign() and subtract():
Can an interface inherit either an abstract class or a regular class?
L1: extends inherits exactly one class or interface.
L9: default allows an interface to define a method with its body (introduced in Java 8).
Can we call add() that is an abstract method without a body in the default method subtract()?
Although the logic of subtract() seems to be correct, n.flipSign() gives a compile error because n is a type of Numeral that does not include flipSign(), which is defined in SignedNumeral that is a subclass of Numeral.
What kind of a compile error does n.flipSign() cause?
The first way is to downcast the type of n to SignedNumeral, which forces the compiler to think that n can invoke the flipSign() method:
This removes the compile error; however, it will likely cause a worse kind, a runtime error.
Why is a runtime error worse than a compile error?
Downcasting, although allowed in Java, is generally not recommended unless there is no other way of accomplishing the job without using it.
How can downcasting cause a runtime error in the above case?
Polymorphism
The second way is to change the type of n to SignedNumeral in the parameter setting:
This seems to solve the issue. Then, what about add() defined in Numeral? Should we change its parameter type to SignedNumeral as well?
It is often the case that you do not have access to change the code in a super class unless you are the author of it. Even if you are the author, changing the code in a super class is not recommended.
Why is it not recommended to change the code in a super class?
How about we override the add() method as follows?
L2: @Override is a predefined annotation type to indicate the method is overridden.
The annotation @Override gives an error in this case because it is not considered an overriding.
What are the criteria to override a method?
When @Override is discarded, the error goes away and everything seems to be fine:
However, this is considered an overloading, which defines two separate methods for add(), one taking n as Numeral and the other taking it as SignedNumeral. Unfortunately, this would decrease the level of abstraction that we originally desired.
What are good use cases of method overriding and overloading?
Generics
The third way is to use generics, introduced in Java 5:
L1: T is a generic type that is a subtype of Numeral.
A generic type can be recursively defined as T extends Numeral<T>.
L2: T is considered a viable type in this interface such that it can be used to declare add().
Can we define more than one generic type per interface or class?
The generic type T can be specified in a subclass of Numeral:
L1: T is specified as SignedNumeral.
This would implicitly assign the parameter type of add() as follows:
The issue is that the implementation of add() may require specific features defined in the subclass that is not available in SignedNumeral. Consider the following subclass inheriting SignedNumeral:
L2-6: LongInteger is a regular class, so all abstract methods declared in the super classes must be defined in this class.
Since the n is typed to SignedNumeral in L6, it cannot call any method defined in LongInteger, which leads to the same issue addressed in the casting section.
Would the type of n being SignedNumeral an issue for the subtract() method as well?
Thus, SignedNumeral needs to define its own generic type and pass it onto Numeral:
L1: T is a generic type inheriting SignedNumeral, that implies all subclasses of SignedNumeral.
T can be safely passed onto Numeral because if it is a subclass of SignedNumeral, it must be a subclass of Numeral, which is how T is defined in the Numeral class.
Generics are used everywhere in Java, so it is important to understand the core concept of generics and be able to adapt it in your code to make it more modular.
Enum
Let us create an enum class called Sign to represent the "sign" of the numeral:
All items in an enum have the scope of static and the access-level of public.
Items must be delimited by , and ends with ;.
The items in the enum can be assigned with specific values to make them more indicative (e.g., +, -):
L5: final makes this field a constant, not a variable, such that the value cannot be updated later.
L8: this points to the object created by this constructor.
L11: @return adds a comment about the return value of this method.
Why should the member field value be private in the above example?
Note that value in L8 indicates the local parameter declared in the constructor whereas value in L13 indicates the member field declared in L5.
Limit of Interface
In SignedNumeral, it would be convenient to have a member field that indicates the sign of the numeral:
L2: All member fields of an interface are static and public.
Can you declare a member field in an interface without assigning a value?
Given the sign field, it may seem intuitive to define flipSign() as a default method:
L3: condition?A:B is a ternary expression that returns A if the condition is true; otherwise, it returns B.
Is there any advantage of using a ternary operator instead of using a regular if statement?
Unfortunately, this gives a compile error because sign is a constant whose value cannot be reassigned. An interface is not meant to define so many default methods, which were not even allowed before Java 8. For such explicit implementations, it is better to declare SignedNumeral as an abstract class instead.
Selection-based sorting algorithms take the following steps:
For each key where and
3.4. Distribution-based Sort
Bucket sort, radix sort.
Unlike comparison-based algorithms in Sections and , distribution-based sorting algorithms do not make comparisons between keys in the input array; instead, they distribute keys into ordered buckets and merge keys in the buckets.
Bucket Sort
Let us create an abstract class, inheriting AbstractSort:
2.5. Quiz
Quiz 2: Priority Queues
Coding
Create a class called under the main package that extends the abstract class .
package edu.emory.cs.algebraic;
public class Numeral {
}
public class Numeral {
/**
* Adds `n` to this numeral.
* @param n the numeral to be added.
*/
public void add(Numeral n) { /* cannot be implemented */ }
}
public interface Numeral {
void add(Numeral n);
}
public interface SignedNumeral extends Numeral {
/** Flips the sign of this numeral. */
void flipSign();
/**
* Subtracts `n` from this numeral.
* @param n the numeral to be subtracted.
*/
default void subtract(Numeral n) {
n.flipSign();
add(n);
n.flipSign();
}
}
public class LongInteger implements SignedNumeral {
@Override
public void flipSign() { /* to be implemented */ }
@Override
public void add(SignedNumeral n) { /* to be implemented */ }
}
public enum Sign {
POSITIVE('+'),
NEGATIVE('-');
private final char value;
Sign(char value) {
this.value = value;
}
/** @return the value of the corresponding item. */
public char value() {
return value;
}
}
/** Flips the sign of this numeral. */
default void flipSign() {
sign = (sign == Sign.POSITIVE) ? Sign.NEGATIVE : Sign.POSITIVE;
}
public abstract class SignedNumeral<T extends SignedNumeral<T>> implements Numeral<T> {
/** The sign of this numeral. */
protected Sign sign;
/**
* Create a signed numeral.
* the default sign is {@link Sign#POSITIVE}.
*/
public SignedNumeral() {
this(Sign.POSITIVE);
}
/**
* Create a signed numeral.
* @param sign the sign of this numeral.
*/
public SignedNumeral(Sign sign) {
this.sign = sign;
}
...
...
/** @return true if this numeral is positive; otherwise, false. */
public boolean isPositive() {
return sign == Sign.POSITIVE;
}
/** @return true if this numeral is negative; otherwise, false. */
public boolean isNegative() {
return sign == Sign.NEGATIVE;
}
/** Flips the sign of this numeral. */
public void flipSign() {
sign = isPositive() ? Sign.NEGATIVE : Sign.POSITIVE;
}
/**
* Subtracts `n` from this numeral.
* @param n the numeral to be subtracted.
*/
public void subtract(T n) {
n.flipSign(); add(n); n.flipSign();
}
/**
* Multiplies `n` to this numeral.
* @param n the numeral to be multiplied.
*/
public abstract void multiply(T n);
}
Test the correctness of your TernaryHeapQuiz using the testRobustness() method.
Add more tests for a more thorough assessment if necessary.
Benchmarking
Compare runtime speeds between BinaryHeap and TernaryHeapQuiz for add() and remove() using the testRuntime() method.
Create a PDF file quiz2.pdf and write a report that includes the following:
A table and a chart to compare speeds between the two priority queues for those two methods, add() and remove(), with respect to different input sizes.
A brief explanation of why a certain PQ is faster than the other PQ with respect to different input sizes.
Submission
1. Commit and push everything under the following packages to your GitHub repository:
The complexities differ by different search algorithms:
Algorithm
Search
Compare
Swap
Selection Sort
Heap Sort
Selection Sort uses linear search to find the minimum (or maximum) key, whereas Heap Sort turns the input array into a heap, so the search complexity becomes O(logn) instead of O(n) .
Can the search be faster than O(logn)?
Selection Sort
Let us create the SelectionSort class inheriting AbstractSort:
Let us then override the sort() method:
L3-12: O(n2)
L3: iterates all keys within the range →O(n).
L4-9: finds the index of the maximum key within the range .
L11: swaps the maximum key with the last key in the range .
How does the sort() method work with Comparator.reverseOrder()?
Heap Sort
Let us create the HeapSort class inheriting AbstractSort:
Before we override the sort() method, let us define the following helper methods:
L1-7: finds the right position of the k'th key by using the sink operation.
L9-11: finds the parent index of the k'th key given the beginning index.
L13-15: finds the left child index of the k'th key given the beginning index.
How is this sink() method different from the one in the BinaryHeap class?
Finally, we override the sort() method:
L4-5: turns the input array into a heap →O(nlogn):
L4: iterates from the parent of the key in the ending index →O(n) .
L5: sinks the key .
L8-11: selection sort :
L8: iterates all keys within the range .
L9
What is the worst-case scenario for Selection Sort and Heap Sort?
Insertion-based Sort
Insertion-based sorting algorithms take the following steps:
For each key Ai where ∣A∣=n and i∈[1,n) :
Keep swapping Aj and Ai until Aj≤Ai.
The complexities differ by different sequences:
Algorithm
Sequence
Compare
Swap
Insertion Sort
Adjacent
Shell Sort
Knuth
Insertion Sort
Let us create the InsertionSort class inheriting AbstractSort:
Let us then define an auxiliary method, sort():
L4: iterates keys in the input array →O(n).
L5: compares keys in the sublist of the input array →O(hn).
L6: swaps the two keys.
Given the auxiliary method, the sort() method can be defined as follows where h = 1:
How many swaps does Insertion Sort make for the following array?
[7, 1, 2, 3, 4, 5, 6, 14, 8, 9, 10, 11, 12, 13, 0]
Shell Sort
Gap Sequence
Shell Sort groups keys whose gap is defined by a particular gap sequence:
Knuth: (3k−1)/2⇒{1,4,13,40,121,…}
Hibbard: 2k−1⇒{1,3,7,15,31,63,…}
Pratt: 2p⋅3q⇒{1,2,3,4,6,8,9,12,…}
Shell: , where
For the above example, by using the Hibbard sequence, it first groups keys whose gap is 7:[7, 14, 0], [1, 8], [2, 9], [3, 10], [4, 11], [5, 12], [6, 13]
It then sorts each group using Insertion Sort, which results in the following array:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
The above procedure is repeated for gaps 3 and 1; however, the array is already sorted, so no more swapping is necessary.
Implementation
Let us create an abstract class, ShellSort, inheriting AbstractSort:
L2: stores a particular gap sequence.
L7: pre-populate the gap sequence that can handle the input size up to 10000.
Then, let us define two abstract methods, populateSequence() and getSequenceStartIndex():
L5: populates a particular sequence for the input size n.
L11: returns the index of the first gap to be used given the input size n.
Let us then override the sort() method:
L4: should not re-populate the sequence unless it has to.
L6: iterates the sequence →O(s) where s is the number of gaps in the sequence.
L7: sorts the gap group by using the auxiliary method.
Knuth Sequence
Let us create the ShellSortKnuth class that populates the Knuth Sequence for ShellSort:
The two abstract methods can be overridden as follows:
L2: populates the Knuth sequence up to the gap ≤3n.
L13: returns the index of the first key ≤3n.
Why should we use 3n as the largest gap in the sequence?
Demonstration
Unit Tests & Benchmarks
The codes for unit testing and benchmarking are available in SortTest:
Ai
∣A∣=n
i∈[n,0)
L2: declares a list of buckets where each bucket is represented by a Deque.
L6: does not pass any comparator to AbstractSort since no comparison is needed.
L7: creates a pre-defined number of buckets.
What kind of input keys can work with distribution-based sorting algorithms?
We then define a helper method sort():
L7: bucketIndex is a function that takes a comparable key and returns the appropriate bucket index of the key.
L9-10: adds the keys within the range in the input array to the buckets.
L13-16: puts all keys in the buckets back to the input array while keeping the order.
How many assignments are made by the sort() method in BucketSort?
Integer Bucket Sort
Let us create the IntegerBucketSort class inheriting BucketSort that sorts integers within a specific range in ascending order:
L2: takes the smallest integer in the range.
L8: passes the number of buckets, max - min, to be initialized to the super constructor.\
We then override the sort() method:
L3: passes a lambda expression that takes key and returns key - MIN indicating the index of the bucket that key should be assigned to.
Is it possible to implement DoubleBucketSort that can handle double instead of integer keys?
Radix Sort
Let us create an abstract class, RadixSort, inheriting BucketSort<Integer>:
L3: creates 10 buckets to sort any range of integers.
L6: returns the order of the most significant digit in the input array.
LSD Radix Sort
Let us create the LSDRadixSort class inheriting RadixSort that sorts the integer keys from the least significant digit (LSD) to the most significant digit (MSD):
L5: iterates from LSD to MSD.
L7: the lambda expression returns the bucket index, the value in the n'th significant digit.
Benchmarks
The followings compare runtime speeds between advanced sorting algorithms where the input arrays consist of random integer keys:
A binary heap is a PQ that takesO(logn)for both add() and remove(), where keys are stored in a balanced binary tree in which every node has a higher priority than its children (when used as a max-PQ).
When should we use a binary heap over a lazy PQ or an eager PQ?
Balanced Binary Tree
A balanced binary tree can be implemented by a list such that given the 'th key in the list:
The index of its parent:
The index of its left child: .
The index of its right child: .
Is the tree represented by the list [1, 2, 3, 4, 5] balanced?
Implementation
Let us create the class inheriting AbstractPriorityQueue:
L11: adding null as the first item makes it easier to calculate the indices of parents and children.
L16: keys has the extra item of null from L11 that is not an input key.
How does adding null make the calculation of the indices easier?
Additionally, let us define the helper method compare() that compares two keys in the list:
L8: calls the compare() method in the member field priority declared in the super class.
Add() with Swim
The add() method in a heap uses the operation called swim as follows:
L3: appends the new key to the list.
L7-10: keeps swimming until the list becomes a heap:
How many keys are compared at most for the `add operation?
Remove() with Sink
The remove() method in a heap uses the operation called sink as follows:
L3: checks if the heap is empty.
L4: swaps the root and the last key in the list.
L3
How many keys are compared at most for the remove operation?
4. Binary Search Trees
This chapter discusses binary search trees using different balancing algorithms.
This section discusses abstraction of binary search trees.
This section assumes that you have already learned core concepts about binary search tress from the prerequisite. Thus, it focuses on the abstraction that can be applied to other types of binary search trees introduced in the following sections.
Abstract Binary Node
3.5. Quiz
Quiz 3: Sorting Algorithms
Coding
Shell Sort: Hibbard
3.6. Homework
This section explains the homework assignment regarding Hybrid Sort.
Hybrid Sort
Your task is to write a program that sorts a 2D-array of comparable keys into an 1D-array where all the keys are sorted in ascending order. Here is a sample input to your program:
Here is the expected output given the sample input:
Each row in the input array has one of the following properties:
4.2. Balanced BST
This section discusses abstraction of binary search trees.
A binary search tree gives the worst-case complexity of for searching a key when it is not balanced, where is the number of nodes in the tree:
4.4. Quiz
This section provides exercises for better understanding in balanced binary search trees.
Interpretation
Explain how the remove() method works in the class:
public class SelectionSort<T extends Comparable<T>> extends AbstractSort<T> {
public SelectionSort() {
this(Comparator.naturalOrder());
}
public SelectionSort(Comparator<T> comparator) {
super(comparator);
}
}
@Override
public void sort(T[] array, final int beginIndex, final int endIndex) {
for (int i = endIndex; i > beginIndex; i--) {
int max = beginIndex;
for (int j = beginIndex + 1; j < i; j++) {
if (compareTo(array, j, max) > 0)
max = j;
}
swap(array, max, i - 1);
}
}
public class HeapSort<T extends Comparable<T>> extends AbstractSort<T> {
public HeapSort() {
this(Comparator.naturalOrder());
}
public HeapSort(Comparator<T> comparator) {
super(comparator);
}
}
private void sink(T[] array, int k, int beginIndex, int endIndex) {
for (int i = getLeftChildIndex(beginIndex, k); i < endIndex; k = i, i = getLeftChildIndex(beginIndex, k)) {
if (i + 1 < endIndex && compareTo(array, i, i + 1) < 0) i++;
if (compareTo(array, k, i) >= 0) break;
swap(array, k, i);
}
}
private int getParentIndex(int beginIndex, int k) {
return beginIndex + (k - beginIndex - 1) / 2;
}
private int getLeftChildIndex(int beginIndex, int k) {
return beginIndex + 2 * (k - beginIndex) + 1;
}
@Override
public void sort(T[] array, int beginIndex, int endIndex) {
// heapify all elements
for (int k = getParentIndex(beginIndex, endIndex - 1); k >= beginIndex; k--)
sink(array, k, beginIndex, endIndex);
// swap the endIndex element with the root element and sink it
while (endIndex > beginIndex + 1) {
swap(array, beginIndex, --endIndex);
sink(array, beginIndex, beginIndex, endIndex);
}
}
public class InsertionSort<T extends Comparable<T>> extends AbstractSort<T> {
public InsertionSort() {
this(Comparator.naturalOrder());
}
public InsertionSort(Comparator<T> comparator) {
super(comparator);
}
}
protected void sort(T[] array, int beginIndex, int endIndex, final int h) {
int begin_h = beginIndex + h;
for (int i = begin_h; i < endIndex; i++)
for (int j = i; begin_h <= j && compareTo(array, j, j - h) < 0; j -= h)
swap(array, j, j - h);
}
@Override
public void sort(T[] array, int beginIndex, int endIndex) {
sort(array, beginIndex, endIndex, 1);
}
public abstract class ShellSort<T extends Comparable<T>> extends InsertionSort<T> {
protected List<Integer> sequence;
public ShellSort(Comparator<T> comparator) {
super(comparator);
sequence = new ArrayList<>();
populateSequence(10000);
}
}
/**
* Populates the gap sequence with respect to the size of the list.
* @param n the size of the list to be sorted.
*/
protected abstract void populateSequence(int n);
/**
* @param n the size of the list to be sorted.
* @return the starting index of the sequence with respect to the size of the list.
*/
protected abstract int getSequenceStartIndex(int n);
@Override
public void sort(T[] array, int beginIndex, int endIndex) {
int n = endIndex - beginIndex;
populateSequence(n);
for (int i = getSequenceStartIndex(n); i >= 0; i--)
sort(array, beginIndex, endIndex, sequence.get(i));
}
public class ShellSortKnuth<T extends Comparable<T>> extends ShellSort<T> {
public ShellSortKnuth() {
this(Comparator.naturalOrder());
}
public ShellSortKnuth(Comparator<T> comparator) {
super(comparator);
}
}
@Override
protected void populateSequence(int n) {
n /= 3;
for (int t = sequence.size() + 1; ; t++) {
int h = (int) ((Math.pow(3, t) - 1) / 2);
if (h <= n) sequence.add(h);
else break;
}
}
@Override
protected int getSequenceStartIndex(int n) {
int index = Collections.binarySearch(sequence, n / 3);
if (index < 0) index = -(index + 1);
if (index == sequence.size()) index--;
return index;
}
public abstract class BucketSort<T extends Comparable<T>> extends AbstractSort<T> {
protected List<Deque<T>> buckets;
/** @param numBuckets the total number of buckets. */
public BucketSort(int numBuckets) {
super(null);
buckets = Stream.generate(ArrayDeque<T>::new).limit(numBuckets).collect(Collectors.toList());
}
}
/**
* @param array the input array.
* @param beginIndex the index of the first key to be sorted (inclusive).
* @param endIndex the index of the last key to be sorted (exclusive).
* @param bucketIndex takes a key and returns the index of the bucket that the key to be added.
*/
protected void sort(T[] array, int beginIndex, int endIndex, Function<T, Integer> bucketIndex) {
// add each element in the input array to the corresponding bucket
for (int i = beginIndex; i < endIndex; i++)
buckets.get(bucketIndex.apply(array[i])).add(array[i]);
// merge elements in all buckets to the input array
for (Deque<T> bucket : buckets) {
while (!bucket.isEmpty())
array[beginIndex++] = bucket.remove();
}
}
public class IntegerBucketSort extends BucketSort<Integer> {
private final int MIN;
/**
* @param min the minimum integer (inclusive).
* @param max the maximum integer (exclusive).
*/
public IntegerBucketSort(int min, int max) {
super(max - min);
MIN = min;
}
}
@Override
public void sort(Integer[] array, int beginIndex, int endIndex) {
sort(array, beginIndex, endIndex, key -> key - MIN);
}
public abstract class RadixSort extends BucketSort<Integer> {
public RadixSort() {
super(10);
}
protected int getMaxBit(Integer[] array, int beginIndex, int endIndex) {
Integer max = Arrays.stream(array, beginIndex, endIndex).reduce(Integer::max).orElse(null);
return (max != null && max > 0) ? (int)Math.log10(max) + 1 : 0;
}
}
public class LSDRadixSort extends RadixSort {
@Override
public void sort(Integer[] array, int beginIndex, int endIndex) {
int maxBit = getMaxBit(array, beginIndex, endIndex);
for (int bit = 0; bit < maxBit; bit++) {
int div = (int)Math.pow(10, bit);
sort(array, beginIndex, endIndex, key -> (key / div) % 10);
}
}
}
: swaps the maximum key with the beginning key in the range
.
L10: sinks to heapify →O(logn).
→O(n)
→O(1)
→O(logn)
→O(nlogn)
→O(n)
n/2k⇒{500,250,125,…}
n=1000
O(n)
O(n2)
O(n)
O(logn)
O(nlogn)
O(nlogn)
O(n2)
O(n2)
O(n1.5)
O(n1.5)
→O(1)
e.g., given the list [1, 2, 3, 4, 5], 1 is the root, 2 and 3 are the left and right children of 1, and 4 and 5 are the left and right children of 2, respectively.
L8: compares the new key to its parent if exists.
L9: if the new key has a higher priority than its parent, Collections.swap() them.
: removes the (swapped) last key with the highest priority in this heap.
L10-16: keeps sinking until the list becomes a heap:
L12: finds the child with a higher priority.
L13: breaks if the parent has a higher priority than the child.
L14: swaps if the child has a higher priority than the parent.
Mostly sorted in ascending order (e.g., the 3rd row).
Mostly sorted in descending order (e.g., the 4th row).
Randomly distributed (e.g., the 5th row).
The easiest way is to merge all rows in the input array into an 1D-array then sort it using IntroSort. The implementation of this strategy is provided to establish the baseline: HybridSortBaseline. Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.
Override the balance() method that first checks the following conditions:
node is the only child &
node’s parent is the right child of node's grand parent &
node’s uncle has only one child.
If all of the above conditions are satisfied, balance() makes multiple rotations such that the left subtree is always full before any node gets added to the right subtree.
For the example below, after adding the keys (in red) to the trees 1, 2, 3, and 4, they all need to be transformed into the tree 5 by the balance() method.
The transform must be performed only by rotations; other setter methods such as setLeftChild() or setRightChild() are not allowed in this assignment.
L1: the generic type T represents the type of value in L6.
L2: is used to store the children.
L4: true if this node represents the last character of a certain word; otherwise, false.
L9: gives the complexity for searching a key.
What other types of maps are implemented in Java?
Let us define getter methods:
L10: returns the map consisting of children's characters as keys and their nodes as values.
Is there any risk of returning this.children in L11?
Let us then define setter methods:
L7: returns the previously assigned value of this node.
L13: returns the child with the specific key if exists; otherwise, a new child with the key.
What does the removeChild() method return if key does not exist in this node?
Finally, let us define checker methods:
L1: returns true if this node represents the last character of a certain word; false.
Trie
Let us create the class, :
L1: defines a generic type T that can be any type.
L5: initializes the root with the null character.
Let us define the find() method that takes a specific key in string and returns the node corresponding the last character of the key:
L5: iterates through every character in the string.
L6: finds the node whose key is the current character.
L7
Given the find() method, let us define the get() method that takes a string key and returns the value of the node corresponding to the key in this trie:
L3: checks if both the key exists and the key is a word.
We then define the put() method that inserts a key-value pair to the trie:
L4-5: iterates through all characters in the key and adds children as necessary.
L7: sets the end state of the node corresponding the last character to true.
What does node.addChild(c) return if the child with the key c already exists?
The following demonstrates how the put() method works:
Finally, let us define the remove() method that removes all appropriate nodes corresponding to the key:
L2: retrieves the node corresponding to the last character in the key.
L4: returns false the key does not exist or the key is not a word.
The following demonstrates how the remove() method works:
5.4. Homework
This section explains the homework assignment regarding Autocomplete.
Auto-Complete
Most virtual keyboards provide the option of auto-complete, which gives a list of candidate words that you wish to type given a prefix you enter. For instance, when you type "sh", it gives a list of candidate words such as "she", "shell", "ship", etc.
If you select a word from the candidates, it should learn your selection as the top candidate for that prefix. For instance, if you select "ship" from the example above, the next time you enter the same prefix "sh", it should give a list of candidates where the first item is "ship" instead of "she".
7. Graphs
This chapter implementations of basic algorithms related to graphs.
Contents
public class BinaryHeap<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
private final List<T> keys;
public BinaryHeap() {
this(Comparator.naturalOrder());
}
public BinaryHeap(Comparator<T> priority) {
super(priority);
keys = new ArrayList<>();
keys.add(null);
}
@Override
public int size() {
return keys.size() - 1;
}
}
/**
* @param i1 the index of the first key in {@link #keys}.
* @param i2 the index of the second key in {@link #keys}.
* @return a negative integer, zero, or a positive integer as the first key is
* less than, equal to, or greater than the second key.
*/
private int compare(int k1, int k2) {
return priority.compare(keys.get(k1), keys.get(k2));
}
@Override
public void add(T key) {
keys.add(key);
swim(size());
}
private void swim(int k) {
for (; 1 < k && compare(k / 2, k) < 0; k /= 2)
Collections.swap(keys, k / 2, k);
}
@Override
public T remove() {
if (isEmpty()) return null;
Collections.swap(keys, 1, size());
T max = keys.remove(size());
sink();
return max;
}
private void sink() {
for (int k = 1, i = 2; i <= size(); k = i, i *= 2) {
if (i < size() && compare(i, i + 1) < 0) i++;
if (compare(k, i) >= 0) break;
Collections.swap(keys, k, i);
}
}
public abstract class AbstractBinaryNode<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> {
protected T key;
protected N parent;
protected N left_child;
protected N right_child;
public AbstractBinaryNode(T key) {
setKey(key);
}
}
public boolean hasParent() { return parent != null; }
public boolean hasLeftChild() { return left_child != null; }
public boolean hasRightChild() { return right_child != null; }
public boolean hasBothChildren() {
return hasLeftChild() && hasRightChild();
}
/** @return true if the specific node is the left child of this node. */
public boolean isLeftChild(N node) {
return left_child == node;
}
/** @return true if the specific node is the right child of this node. */
public boolean isRightChild(N node) {
return right_child == node;
}
public T getKey() { return key; }
public N getParent() { return parent; }
public N getLeftChild() { return left_child; }
public N getRightChild() { return right_child; }
public N getGrandParent() {
return hasParent() ? parent.getParent() : null;
}
@SuppressWarnings("unchecked")
public N getSibling() {
if (hasParent()) {
N parent = getParent();
return parent.isLeftChild((N)this) ? parent.getRightChild() : parent.getLeftChild();
}
return null;
}
public N getUncle() {
return hasParent() ? parent.getSibling() : null;
}
public void setKey(T key) { this.key = key; }
public void setParent(N node) { parent = node; }
public void setLeftChild(N node) {
replaceParent(node);
left_child = node;
}
public void setRightChild(N node) {
replaceParent(node);
right_child = node;
}
/**
* Replaces the parent of the specific node to be this node.
* @param node the node whose parent to be replaced.
*/
@SuppressWarnings("unchecked")
protected void replaceParent(N node) {
if (node != null) {
if (node.hasParent()) node.getParent().replaceChild(node, null);
node.setParent((N)this);
}
}
/**
* Replaces the old child with the new child if exists.
* @param oldChild the old child of this node to be replaced.
* @param newChild the new child to be added to this node.
*/
public void replaceChild(N oldChild, N newChild) {
if (isLeftChild(oldChild)) setLeftChild(newChild);
else if (isRightChild(oldChild)) setRightChild(newChild);
}
public class BinaryNode<T extends Comparable<T>> extends AbstractBinaryNode<T, BinaryNode<T>> {
public BinaryNode(T key) {
super(key);
}
}
public abstract class AbstractBinarySearchTree<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> {
protected N root;
public AbstractBinarySearchTree() {
setRoot(null);
}
/** @return a new node with the specific key. */
abstract public N createNode(T key);
public boolean isRoot(N node) { return root == node; }
public N getRoot() { return root; }
public void setRoot(N node) {
if (node != null) node.setParent(null);
root = node;
}
}
/** @return the node with the specific key if exists; otherwise, {@code null}. */
public N get(T key) {
return findNode(root, key);
}
/** @return the node with the specific key if exists; otherwise, {@code null}. */
protected N findNode(N node, T key) {
if (node == null) return null;
int diff = key.compareTo(node.getKey());
if (diff < 0)
return findNode(node.getLeftChild(), key);
else if (diff > 0)
return findNode(node.getRightChild(), key);
else
return node;
}
/** @return the node with the minimum key under the subtree of {@code node}. */
protected N findMinNode(N node) {
return node.hasLeftChild() ? findMinNode(node.getLeftChild()) : node;
}
/** @return the node with the maximum key under the subtree of {@code node}. */
protected N findMaxNode(N node) {
return node.hasRightChild() ? findMaxNode(node.getRightChild()) : node;
}
public N add(T key) {
N node = null;
if (root == null)
setRoot(node = createNode(key));
else
node = addAux(root, key);
return node;
}
private N addAux(N node, T key) {
int diff = key.compareTo(node.getKey());
N child, newNode = null;
if (diff < 0) {
if ((child = node.getLeftChild()) == null)
node.setLeftChild(newNode = createNode(key));
else
newNode = addAux(child, key);
}
else if (diff > 0) {
if ((child = node.getRightChild()) == null)
node.setRightChild(newNode = createNode(key));
else
newNode = addAux(child, key);
}
return newNode;
}
/** @return the removed node with the specific key if exists; otherwise, {@code null}. */
public N remove(T key) {
N node = findNode(root, key);
if (node != null) {
if (node.hasBothChildren()) removeHibbard(node);
else removeSelf(node);
}
return node;
}
/** @return the lowest node whose subtree has been updatede. */
protected N removeSelf(N node) {
N parent = node.getParent();
N child = null;
if (node.hasLeftChild()) child = node.getLeftChild();
else if (node.hasRightChild()) child = node.getRightChild();
replaceChild(node, child);
return parent;
}
private void replaceChild(N oldNode, N newNode) {
if (isRoot(oldNode))
setRoot(newNode);
else
oldNode.getParent().replaceChild(oldNode, newNode);
}
/** @return the lowest node whose subtree has been updatede. */
protected N removeHibbard(N node) {
N successor = node.getRightChild();
N min = findMinNode(successor);
N parent = min.getParent();
min.setLeftChild(node.getLeftChild());
if (min != successor) {
parent.setLeftChild(min.getRightChild());
min.setRightChild(successor);
}
replaceChild(node, min);
return parent;
}
public class BinarySearchTree<T extends Comparable<T>> extends AbstractBinarySearchTree<T, BinaryNode<T>> {
/**
* @param key the key of this node.
* @return a binary node with the specific key.
*/
@Override
public BinaryNode<T> createNode(T key) {
return new BinaryNode<T>(key);
}
}
public abstract class AbstractBalancedBinarySearchTree<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> extends AbstractBinarySearchTree<T, N> {
/**
* Rotates the specific node to the left.
* @param node the node to be rotated.
*/
protected void rotateLeft(N node) {
N child = node.getRightChild();
node.setRightChild(child.getLeftChild());
if (node.hasParent())
node.getParent().replaceChild(node, child);
else
setRoot(child);
child.setLeftChild(node);
}
/**
* Rotates the specific node to the right.
* @param node the node to be rotated.
*/
protected void rotateRight(N node) {
N child = node.getLeftChild();
node.setLeftChild(child.getRightChild());
if (node.hasParent())
node.getParent().replaceChild(node, child);
else
setRoot(child);
child.setRightChild(node);
}
}
@Override
public N add(T key) {
N node = super.add(key);
balance(node);
return node;
}
@Override
public N remove(T key) {
N node = findNode(root, key);
if (node != null) {
N lowest = node.hasBothChildren() ? removeHibbard(node) : removeSelf(node);
if (lowest != null && lowest != node) balance(lowest);
}
return node;
}
/**
* Preserves the balance of the specific node and its ancestors.
* @param node the node to be balanced.
*/
protected abstract void balance(N node);
public class TrieNode<T> {
private final Map<Character, TrieNode<T>> children;
private TrieNode<T> parent;
private boolean end_state;
private char key;
private T value;
public TrieNode(TrieNode<T> parent, char key) {
children = new HashMap<>();
setEndState(false);
setParent(parent);
setKey(key);
setValue(null);
}
}
This class extends the abstract class Autocomplete, which extends Trie.
The value type of the generic T can be a collection of strings (e.g., List<String>).
You must create a constructor that takes two parameters, dict_file and max, and calls its , which reads all words in the dictionary file (e.g., ).
Override the getCandidates() method that takes a prefix and returns a list of candidate words matching the prefix:
The max-number of candidates in the list must be the return value of the getMax() method.
Override the pickCandidate() method that takes a prefix and a selected candidate, and saves the information:
This is the most recently selected candidate for that particular prefix. It must appear as the first item in the candidate list when the same prefix is entered next time.
Feel free to change the generic type, representing the value type of each TrieNode, to anything other than List<String> (List<something else>).
The getCandidates() method:
Must show the most frequently picked candidate first, the 2nd-most frequently picked candidate next, and so on.
If there are more than one candidate with the same frequency, sort them by recency.
The rest of candidates should be filled as in the original task.
You must submit both AutocompleteHW and AutocompleteHWExtra to earn the extra credit.
Notes
Do not change the dictionary file. If you find anything peculiar about the dictionary file, please let me know so everyone works on the same copy of the dictionary file.
Please test your program yourself. We will evaluate your program using our unit tests and measure the performance (both speed and accuracy).
Take a look at Map if you are not familiar with methods in the standard library.
If you are having trouble with implementing getCandidates(), think about how to traverse the trie given any node.
If you are having trouble with implementing pickCandidate(), take a look at .
You are not allowed to use any type of to store candidates for this homework.
Your program should be able to handle prefixes or candidates that do not exist in the dictionary.
All picked candidates should be introduced as real words to the trie.
Whitespaces are not allowed as input; thus, you should trim all input strings.
⇒
O(logn)
O(logn)+α
O(logn)+β
8.1. Abstraction
This section discusses spanning trees in a graph.
Overview
A spanning tree in a graph is a tree that contains all vertices in the graphs as its nodes. A minimum spanning tree is a spanning tree whose sum of all edge weights is the minimum among all the other spanning trees in the graph.
Can a graph have more than one minimum spanning tree?
Spanning Tree
Let us define the class under the package:
L1: inherits the interface.
L2: contains all edges in this spanning tree.
L3
We then define getters and setters:
L3: the size of the spanning tree is determined by the number of edges.
Finally, we override the compareTo() method that makes the comparison to another spanning tree by the total weight:
MST
Let us create the interface that is inherited by all minimum spanning tree algorithms:
L2: an abstract method that takes a graph and returns a minimum spanning tree.
8.2. Prim's Algorithm
This section discusses Prim's Algorithm that finds a minimum spanning tree in an undirected graph.
Prim's algorithm finds a minimum spanning tree by finding the minimum edge among all incoming edges of visited vertices.
Let us define the MSTPrim class inheriting the MST interface:
L9: adds the vertex 0 to the visited set and its incoming edges to the queue.
L11: iterates through all incoming edges:
L14: if the visited set contains the source vertex, adding the edge would create a cycle.
L16: if the tree contains v-1 number of edges, a spanning tree is found.
The add() method can be defined as follows:
L4-7: adds all incoming edges that have not been visited to the queue.
What is the worst-case complexity of Prim's Algorithm?
8. Minimum Spanning Trees
This chapter discusses algorithms to find minimum spanning trees in undirected and directed graphs.
This section discusses a type of balanced binary search trees called AVL Trees.
AVL (Adelson-Velsky and Landis) trees preserve the balance at all time by keeping track of the height of every node through a balance factor.
AVL Node
Let us create the AVLNode class inheriting AbstractBinaryNode:
L2: keeps track of the height of this node.
L6: a node with no children has the height of 1.
We then override the setLeftChild() and setRigthChild() methods such that the height of this node gets adjusted accordingly with the new child by calling the resetHeights() method:
L15: adjusts the height of this node and its ancestors, recursively.
L20-22: retrieve the height of this node.
L24-27
What are the heights of 3, 5, and 7 in the figure below when the height of 4 changes from 3 to 4?
Finally, we define the getBalanceFactor() method that returns the height difference between the left-subtree and the right-subtree of this node:
How can we tell if the node is unbalanced by using the balance factor?
AVL Tree
Let us create the class that inherits AbstractBalancedBinarySearchTree and override the createNote(), rotateLeft(), and rotateRight() methods:
L10,16: resets the height of node after rotation.
node.resetHeights() does not reset heights of nodes in its subtree. Would this cause an issue?
We then override the balance() method:
L6: the left-subtree is longer.
L9-10: the case of left zig-zag.
L12
The followings demonstrate how the balance() method works in AVL Trees:
What is the worst-case complexity of the balance() method in AVLTree?
4.3. Red-Black Trees
This section discusses a type of balanced binary search trees called Red-Black Trees.
Red-Black trees preserve the balance at most time by satisfying the following conditions:
Every node is either red or black.
The root and all leaves (null) are black.
Every red node must have two black children.
Every path from a given node to any of its leaves goes through the same number of black nodes.
Red-Black Node
Let us create the class inheriting AbstractBinaryNode:
L2: if is_red is true, the color of this node is red; otherwise, it is black.
L6: the color of the node is black by default upon instantiation.
Let us the class inheriting AbstractBalancedBinarySearchTree:
Finally, let us override balance() method that handles 3 cases:
L3: sets the color to black if node is the root.
L5: if the color of node's parent is red:
What about the case when the color of node's parent is black?
The following shows a method that handles when both the parent and the uncle are red:
Are there any structural changes after this method is called?
The following shows a method that handles when the parent is red but the uncle is black:
L7: the case of left zig-zag.
L11: the case of right zig-zag.
L19: the case of left linear.
The followings demonstrate how the balance() method works in Red-Black trees:
How does a Red-Black tree know when it is unbalanced?
7.3. Topological Sorting
This section discusses two algorithms for topological sorting.
The task of topological sorting is to sort vertices in a linear order such that for each vertex, all target vertices associated with its incoming edges must appear prior to it.
By Incoming Scores
The followings demonstrate how to perform a topological sort by incoming scores, where the incoming score of a vertex is define as the sum of all source vertices:
8.4. Edmonds' Algorithm
This section discusses Chu-Liu-Edmonds' Algorithm that finds a MST in a directed graph.
Chu-Liu-Edmonds' Algorithm takes the following steps to find a MST in a directed graph:
Initially, every vertex is considered a subtree.
For each subtree, keep 1 incoming edge with the minimum weight.
7.4. Quiz
This section provides exercises for better understanding in disjoint sets.
Implementation
Create the class under the package.
public TrieNode<T> getParent() { return parent; }
public char getKey() { return key; }
public T getValue() { return value; }
public TrieNode<T> getChild(char key) { return children.get(key); }
/** @return the map whose keys and values are children's characters and nodes. */
public Map<Character, TrieNode<T>> getChildrenMap() {
return children;
}
public void setParent(TrieNode<T> node) { parent = node; }
public void setKey(char key) { this.key = key; }
public void setEndState(boolean endState) { end_state = endState; }
public T setValue(T value) {
T tmp = this.value;
this.value = value;
return tmp;
}
public TrieNode<T> addChild(char key) {
TrieNode<T> child = getChild(key);
if (child == null) {
child = new TrieNode<>(this, key);
children.put(key, child);
}
return child;
}
public TrieNode<T> removeChild(char key) {
return children.remove(key);
}
public boolean isEndState() { return end_state; }
public boolean hasValue() { return value != null; }
public boolean hasChildren() { return !children.isEmpty(); }
public class Trie<T> {
private final TrieNode<T> root;
public Trie() {
root = new TrieNode<>(null, (char)0);
}
public TrieNode<T> getRoot() { return root; }
}
/** @return the node with the specific key if exists; otherwise, {@code null}. */
public TrieNode<T> find(String key) {
TrieNode<T> node = root;
for (char c : key.toCharArray()) {
node = node.getChild(c);
if (node == null) return null;
}
return node;
}
public T get(String key) {
TrieNode<T> node = find(key);
return (node != null && node.isEndState()) ? node.getValue() : null;
}
public boolean contains(String key) {
return get(key) != null;
}
public T put(String key, T value) {
TrieNode<T> node = root;
for (char c : key.toCharArray())
node = node.addChild(c);
node.setEndState(true);
return node.setValue(value);
}
This section describes how to implement a flow network.
A flow network is a directed graph that has the following properties:
Max Flow
Let us define the MaxFlow class that keeps track of the amount of flows in every edge used to find the maximum flow:
L2: consists of (edge, flow) as the key-value pair.
L3: stores the total amount of flows to the target vertices.
L13-14: initializes all flows to 0.
Let us define getter methods:
L5: returns the remaining residual that can be used to push more flows.
L6: the edge weight represents the total capacity.
Finally, let us define setter methods:
L1: takes the path from a source and a target.
L2: updates the flow of every edge in the path with the specific flow.
9.2. Ford-Fulkerson Algorithm
This section describes the implementation of Ford-Fulkerson Algorithm
Subgraph
Let us define the class that consists of a subset of vertices and edges from the original graph:
Let us define helper methods:
8.3. Kruskal’s Algorithm
This section discusses Kruskal's Algorithm that finds a minimum spanning tree in an undirected graph.
Kruskal's algorithm finds a minimum spanning tree by finding the minimum edge among subtrees.
Let us create the class inheriting the MST interface:
L4: adds all edges to the priority queue.
8.6. Homework
This section describes the homework assignment to develop an algorithm to find all minimum spanning tress given an undirected graph.
Finding All Minimum Spanning Trees
Your task is to write a program that finds all minimum spanning trees given an undirected graph.
9. Network Flow
This chapter discusses the optimization problem called Network Flows that finds the maximum flow given a flow network.
Contents
public class SpanningTree implements Comparable<SpanningTree> {
private final List<Edge> edges;
private double total_weight;
public SpanningTree() {
edges = new ArrayList<>();
}
public SpanningTree(SpanningTree tree) {
edges = new ArrayList<>(tree.getEdges());
total_weight = tree.getTotalWeight();
}
}
public List<Edge> getEdges() { return edges; }
public double getTotalWeight() { return total_weight; }
public int size() { return edges.size(); }
public void addEdge(Edge edge) {
edges.add(edge);
total_weight += edge.getWeight();
}
@Override
public int compareTo(SpanningTree tree) {
double diff = total_weight - tree.total_weight;
if (diff > 0) return 1;
else if (diff < 0) return -1;
else return 0;
}
public interface MST {
public SpanningTree getMinimumSpanningTree(Graph graph);
}
private void add(PriorityQueue<Edge> queue, Set<Integer> visited, Graph graph, int target) {
visited.add(target);
for (Edge edge : graph.getIncomingEdges(target)) {
if (!visited.contains(edge.getSource()))
queue.add(edge);
}
}
@Override
public void setLeftChild(AVLNode<T> node) {
super.setLeftChild(node);
resetHeights();
}
@Override
public void setRightChild(AVLNode<T> node) {
super.setRightChild(node);
resetHeights();
}
/** Resets the heights of this node and its ancestor, recursively. */
public void resetHeights() {
resetHeightsAux(this);
}
private void resetHeightsAux(AVLNode<T> node) {
if (node != null) {
int lh = node.hasLeftChild() ? node.getLeftChild().getHeight() : 0;
int rh = node.hasRightChild() ? node.getRightChild().getHeight() : 0;
int height = Math.max(lh, rh) + 1;
if (height != node.getHeight()) {
node.setHeight(height);
resetHeightsAux(node.getParent()); // recursively update parent height
}
}
}
/** @return height(left-subtree) - height(right-subtree). */
public int getBalanceFactor() {
if (hasBothChildren())
return left_child.getHeight() - right_child.getHeight();
else if (hasLeftChild())
return left_child.getHeight();
else if (hasRightChild())
return -right_child.getHeight();
else
return 0;
}
public class AVLTree<T extends Comparable<T>> extends AbstractBalancedBinarySearchTree<T, AVLNode<T>> {
@Override
public AVLNode<T> createNode(T key) {
return new AVLNode<>(key);
}
@Override
protected void rotateLeft(AVLNode<T> node) {
super.rotateLeft(node);
node.resetHeights();
}
@Override
protected void rotateRight(AVLNode<T> node) {
super.rotateRight(node);
node.resetHeights();
}
}
@Override
protected void balance(AVLNode<T> node) {
if (node == null) return;
int bf = node.getBalanceFactor();
if (bf == 2) {
AVLNode<T> child = node.getLeftChild();
if (child.getBalanceFactor() == -1)
rotateLeft(child);
rotateRight(node);
}
else if (bf == -2) {
AVLNode<T> child = node.getRightChild();
if (child.getBalanceFactor() == 1)
rotateRight(child);
rotateLeft(node);
}
else
balance(node.getParent());
}
public class RedBlackNode<T extends Comparable<T>> extends AbstractBinaryNode<T, RedBlackNode<T>> {
private boolean is_red;
public RedBlackNode(T key) {
super(key);
setToRed();
}
public void setToRed() { is_red = true; }
public void setToBlack() { is_red = false; }
public boolean isRed() { return is_red; }
public boolean isBlack() { return !is_red; }
}
public class RedBlackTree<T extends Comparable<T>> extends AbstractBalancedBinarySearchTree<T, RedBlackNode<T>> {
@Override
public RedBlackNode<T> createNode(T key) {
return new RedBlackNode<T>(key);
}
}
@Override
protected void balance(RedBlackNode<T> node) {
if (isRoot(node))
node.setToBlack();
else if (node.getParent().isRed()) {
RedBlackNode<T> uncle = node.getUncle();
if (uncle != null && uncle.isRed())
balanceWithRedUncle(node, uncle);
else
balanceWithBlackUncle(node);
}
}
public List<Integer> topological_sort(boolean depth_first) {
Deque<Integer> global = getVerticesWithNoIncomingEdges();
List<Deque<Edge>> outgoingEdgesAll = getOutgoingEdges();
List<Integer> order = new ArrayList<>();
while (!global.isEmpty()) {
Deque<Integer> local = new ArrayDeque<>();
int vertex = global.poll();
order.add(vertex);
Deque<Edge> outgoingEdges = outgoingEdgesAll.get(vertex);
while (!outgoingEdges.isEmpty()) {
Edge edge = outgoingEdges.poll();
//Remove edge in all incomingEdges of the target vertex
List<Edge> incomingEdges = getIncomingEdges(edge.getTarget());
incomingEdges.remove(edge);
//If the vertex has no incoming edges, add it to the local queue awaited to be added to the global deque
if (incomingEdges.isEmpty())
local.add(edge.getTarget());
}
//Transfer all vertices in local to global
while (!local.isEmpty())
if (depth_first) global.addFirst(local.removeLast());
else global.addLast(local.removeFirst());
}
if (!hasNoEdge()) throw new IllegalArgumentException("Cyclic graph.");
return order;
}
public class MaxFlow {
private Map<Edge, Double> flow_map;
private double maxflow;
public MaxFlow(Graph graph) {
init(graph);
}
public void init(Graph graph) {
flow_map = new HashMap<>();
maxflow = 0;
for (Edge edge : graph.getAllEdges())
flow_map.put(edge, 0d);
}
}
Tasks
Create a class called MSTAllHW that inherits the MSTAll interface.
Override the getMinimumSpanningTrees() method.
Feel free to use any classes in the graph package without modifying.
Write a report that explains the logic and worst-case complexity of your program and save it as hw3.pdf.
You may want to start with the implementation of either Prim's or Kruskal's algorithm and update the code to find all minimum spanning trees.
Extra Credit
Create an interesting graph and submit both the source code (as in MSTAllHWTest) and the diagram representing your graph (up to 1 point).
Notes
Test your code with graphs consisting of zero to many spanning trees.
Your output must include only minimum spanning trees.
Your output should not include redundant trees. For example, if there are three vertices, 0, 1, and 2, {0 -> 1, 0 -> 2} is considered the same as {0 -> 1, 0 <- 2} or {0 <- 1, 0 -> 2} or {0 <-1, 0 <- 2}.
L6: iterates as long as it can find an augmenting path
L7: finds the edge with the minimum capacity in the augmenting path.
L8: updates the edges in the path with the flow.
Let us define the getMin() method:
Finally, let us define the getAugmentingPath() method:
L2: once the source reaches the target, it found an augmenting path.
L6: adding the source vertex would cause a cycle.
L7: cannot push the flow when there is no residual left.
L10: recursively finds the augmenting path by switching the target.
Backward Pushing
Let us consider the following graph:
As shown, our implementation of Ford-Fulkerson Algorithm does not always guarantee to find the maximum flow correctly. To fix this issue, we need to implement backward pushing:
The backward pushing can be performed after the applying the flow to all edges as in the implementation above (see the code in the "With Backward Pushing" tab).
Finally, the updateBackward() method can be implemented as follows:
Update the getAugmentingPaths() method that returns all augmenting paths between the specific source and target vertices using depth-first traverse.
Extra Credit
Create the NetworkFlowQuizExtra class and update the getAugmentingPaths() method such that it uses breadth-first traverse instead of depth-first traverse.
Simplex Algorithm
Given the following graph where there are two source vertices, and , and two target vertices, and , define the objective functions and their constraints to find the (1) max-flow and (2) min-cut using the simplex algorithm:
Report
Write quiz8 that includes:
The worst-case complexity of your getAugmentingPaths() method.
An explanation of when the depth-first traverse is preferred over the breadth-first traverse and vice versa to find augmenting paths.
An objective function and is constraints to find max-flow.
public double getMaxFlow() {
return maxflow;
}
public double getResidual(Edge edge) {
return edge.getWeight() - flow_map.get(edge);
}
public class FordFulkerson implements NetworkFlow {
public MaxFlow getMaximumFlow(Graph graph, int source, int target) {
MaxFlow mf = new MaxFlow(graph);
Subgraph sub;
while ((sub = getAugmentingPath(graph, mf, new Subgraph(), source, target)) != null) {
double min = getMin(mf, sub.getEdges());
mf.updateFlow(sub.getEdges(), min);
}
return mf;
}
}
public class FordFulkerson implements NetworkFlow {
public MaxFlow getMaximumFlow(Graph graph, int source, int target) {
MaxFlow mf = new MaxFlow(graph);
Subgraph sub;
while ((sub = getAugmentingPath(graph, mf, new Subgraph(), source, target)) != null) {
double min = getMin(mf, sub.getEdges());
mf.updateFlow(sub.getEdges(), min);
updateBackward(graph, sub, mf, min);
}
return mf;
}
}
public class Subgraph {
private final List<Edge> edges;
private final Set<Integer> vertices;
public Subgraph() {
edges = new ArrayList<>();
vertices = new HashSet<>();
}
public Subgraph(Subgraph graph) {
edges = new ArrayList<>(graph.getEdges());
vertices = new HashSet<>(graph.getVertices());
}
}
public List<Edge> getEdges() { return edges; }
public Set<Integer> getVertices() { return vertices; }
public void addEdge(Edge edge) {
edges.add(edge);
vertices.add(edge.getSource());
vertices.add(edge.getTarget());
}
public boolean contains(int vertex) {
return vertices.contains(vertex);
}
private double getMin(MaxFlow mf, List<Edge> path) {
double min = mf.getResidual(path.get(0));
for (int i = 1; i < path.size(); i++)
min = Math.min(min, mf.getResidual(path.get(i)));
return min;
}
private Subgraph getAugmentingPath(Graph graph, MaxFlow mf, Subgraph sub, int source, int target) {
if (source == target) return sub;
Subgraph tmp;
for (Edge edge : graph.getIncomingEdges(target)) {
if (sub.contains(edge.getSource())) continue;
if (mf.getResidual(edge) <= 0) continue;
tmp = new Subgraph(sub);
tmp.addEdge(edge);
tmp = getAugmentingPath(graph, mf, tmp, source, edge.getSource());
if (tmp != null) return tmp;
}
return null;
}
protected void updateBackward(Graph graph, Subgraph sub, MaxFlow mf, double min) {
boolean found;
for (Edge edge : sub.getEdges()) {
found = false;
for (Edge rEdge : graph.getIncomingEdges(edge.getSource())) {
if (rEdge.getSource() == edge.getTarget()) {
mf.updateFlow(rEdge, -min);
found = true;
break;
}
}
if (!found) {
Edge rEdge = graph.setDirectedEdge(edge.getTarget(), edge.getSource(), 0);
mf.updateFlow(rEdge, -min);
}
}
}
public class MSTKruskal implements MST {
@Override
public SpanningTree getMinimumSpanningTree(Graph graph) {
PriorityQueue<Edge> queue = new PriorityQueue<>(graph.getAllEdges());
DisjointSet forest = new DisjointSet(graph.size());
SpanningTree tree = new SpanningTree();
while (!queue.isEmpty()) {
Edge edge = queue.poll();
if (!forest.inSameSet(edge.getTarget(), edge.getSource())) {
tree.addEdge(edge);
if (tree.size() + 1 == graph.size()) break;
forest.union(edge.getTarget(), edge.getSource());
}
}
return tree;
}
}
public abstract class Hanoi {
/**
* @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 in the source tower to the destination tower.
*/
public abstract List<String> solve(int n, char source, char intermediate, char destination);
protected String getKey(int n, char source, char destination) {
return n + ":" + source + "->" + destination;
}
}
This section discusses recursive and dynamic programming ways of finding longest common subsequence.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Given a string "ABCDE"
Substring: {"A", "BC", "CDE", ...}
Subsequence: {all substrings, "AC", "ACE", ...}
Not subsequence: {"BA", "DAB", ...}
Longest common subsequence
The longest subsequence commonly shared by multiple strings.
e.g., “baal” is a LCS of “bilabial” and “balaclava”.
Can there be more than one longest common subsequence?
Application
Find the longest common subsequence in DNA (e.g., GAATGTCCTTTCTCTAAGTCCTAAG).
Abstraction
Let us create the abstract class :
Recursion
Let us create the inheriting LCS:
L4: no character is left to compare for either string.
L5: when two characters match, move onto c[:i-1] and d[:j-1].
The followings demonstrate a recursive way of finding a LCS between two strings:
Dynamic Programming
Let us create the class inheriting LCS.
L4: creates a dynamic table and passes it to the solver.
L12: the dynamic table is pre-populated before any recursive calls.
The following show the dynamic table populated by the previous example:
Let us define the solve() method:
L2: no character is left to compare for either string.
L3: when two characters match, move onto c[:i-1] and d[:j-1].
The followings demonstrate how to find a LCS using the dynamic table:
public class HanoiRecursive extends Hanoi {
@Override
public List<String> solve(int n, char source, char intermediate, char destination) {
List<String> list = new ArrayList<>();
solve(list, n, source, intermediate, destination);
return list;
}
private void solve(List<String> list, int n, char source, char intermediate, char destination) {
if (n == 0) return;
solve(list, n - 1, source, destination, intermediate);
list.add(getKey(n, source, destination));
solve(list, n - 1, intermediate, source, destination);
}
}
public class HanoiDynamic extends Hanoi {
@Override
public List<String> solve(int n, char source, char intermediate, char destination) {
List<String> list = new ArrayList<>();
solve(list, n, source, intermediate, destination, new HashMap<>());
return list;
}
private void solve(List<String> list, int n, char source, char intermediate, char destination, Map<String, int[]> map) {
if (n == 0) return;
int fromIndex = list.size();
int[] sub = map.get(getKey(n - 1, source, intermediate));
if (sub != null) addAll(list, sub[0], sub[1]);
else solve(list, n - 1, source, destination, intermediate, map);
String key = getKey(n, source, destination);
list.add(key);
sub = map.get(getKey(n - 1, intermediate, destination));
if (sub != null) addAll(list, sub[0], sub[1]);
else solve(list, n - 1, intermediate, source, destination, map);
if (!map.containsKey(key))
map.put(key, new int[]{fromIndex, list.size()});
}
private void addAll(List<String> list, int fromIndex, int toIndex) {
for (int i = fromIndex; i < toIndex; i++)
list.add(list.get(i));
}
}
public abstract class LCS {
/**
* @param a the first string.
* @param b the second string.
* @return a longest common sequence of the two specific strings.
*/
public String solve(String a, String b) {
return solve(a.toCharArray(), b.toCharArray(), a.length() - 1, b.length() - 1);
}
/**
* @param c the first array of characters.
* @param d the second array of characters.
* @param i the index of the character in {@code c} to be compared.
* @param j the index of the character in {@code d} to be compared.
* @return a longest common sequence of the two specific strings.
*/
protected abstract String solve(char[] c, char[] d, int i, int j);
}
public class LCSRecursive extends LCS {
@Override
protected String solve(char[] c, char[] d, int i, int j) {
if (i < 0 || j < 0) return "";
if (c[i] == d[j]) return solve(c, d, i - 1, j - 1) + c[i];
String c1 = solve(c, d, i - 1, j);
String d1 = solve(c, d, i, j - 1);
return (c1.length() > d1.length()) ? c1 : d1;
}
}
public class LCSDynamic extends LCS {
@Override
protected String solve(char[] c, char[] d, int i, int j) {
return solve(c, d, i, j, createTable(c, d));
}
/**
* @param c the first string.
* @param d the second string.
* @return the dynamic table populated by estimating the # of LCSs in the grid of the two specific strings.
*/
protected int[][] createTable(char[] c, char[] d) {
final int N = c.length, M = d.length;
int[][] table = new int[N][M];
for (int i = 1; i < N; i++)
for (int j = 1; j < M; j++)
table[i][j] = (c[i] == d[j]) ? table[i - 1][j - 1] + 1 : Math.max(table[i - 1][j], table[i][j - 1]);
return table;
}
}
protected String solve(char[] c, char[] d, int i, int j, int[][] table) {
if (i < 0 || j < 0) return "";
if (c[i] == d[j]) return solve(c, d, i - 1, j - 1, table) + c[i];
if (i == 0) return solve(c, d, i, j - 1, table);
if (j == 0) return solve(c, d, i - 1, j, table);
return (table[i - 1][j] > table[i][j - 1]) ? solve(c, d, i - 1, j, table) : solve(c, d, i, j - 1, table);
}
public class FibonacciRecursive implements Fibonacci {
@Override
public int get(int k) {
return switch (k) {
case 0 -> 0;
case 1 -> 1;
default -> get(k - 1) + get(k - 2);
};
}
}
public class FibonacciDynamic implements Fibonacci {
@Override
public int get(int k) {
return getAux(k, createTable(k));
}
private int[] createTable(int k) {
int[] table = new int[k + 1];
table[0] = 0;
table[1] = 1;
Arrays.fill(table, 2, k + 1, -1);
return table;
}
private int getAux(int k, int[] table) {
if (table[k] >= 0) return table[k];
return table[k] = getAux(k - 1, table) + getAux(k - 2, table);
}
}
public class FibonacciIterative implements Fibonacci {
@Override
public int get(int k) {
if (k < 2) return k;
int f0 = 0, f1 = 1, f2;
for (int i = 2; i < k; i++) {
f2 = f0 + f1;
f0 = f1;
f1 = f2;
}
return f0 + f1;
}
}
