Consider the following question: what is the most effective way of explaining how an algorithm work to somebody?
One way of doing this might be to write Java code implementing the algorithm. However, Java code can often be long and challenging to read.
Making your code fully functional can also introduce a lot of unnecessary noise to your code: you need to deal with minor details irrelevant to the problem, you need to deal with programming-language specific issues...
This means that code, unfortunately, is not an effective way of communicating between programmers. (Code is meant to be a way for you to communicate with the machine!)
Instead, what if we wrote English paragraphs? English is designed to be a way of communicating between two people, and so is an excellent way of explaining how an algorithm works.
That said, it can still be useful to include brief snippets of code in your explanation, or to mix code and English together. If you need to do explain how a particularly tricky loop works, it might just be cleanest to write a for-loop, some if statements, and sprinkle in some English here and there.
We call explanations written in this style pseudocode. Writing pseudocode is another excellent way of communicating algorithms to other programmers.
On your homework and exams, we may ask you to describe how an algorithm works on a high level by either using English or psuedocode.
For example, suppose somebody asks you how you would implement
put(key, value) inside of a SortedArrayDictionary
using binary search. Here are several different examples of response we could give:
Here is an example of an UNACCEPTABLE response. This is full-fledged, compilable Java code: literal code is too noisy and not a good way of explaining how something works.
For example, the below piece of code contains lots of (irrelevant) details relating to how Java handles comparing two objects, which has no bearing on the algorithm itself.
It also contains a lot of boilerplate related to shifting array elements which are tedious to read and dissect but are frankly unimportant to the core essence of the algorithm. You force the reader to waste their time trying to reverse-engineer what exactly your intent is.
If we ever ask you to explain how some algorithm works using English or pseudocode, you should NEVER provide Java code instead. We want to see how effective you are at communicating high-level ideas, and writing code is not an effective way of demonstrating that skill.
public class SortedArrayDictionary<T implements Comparable<T>> {
// ...snip...
public void put(K key, V value) {
containsHelper(key, value, 0, this.size);
}
private void containsHelper(K key, V value, int low, int high) {
if (high < low) {
if (array.length == this.size) {
Pair<K, V>[] newArray = this.makeNewArray(this.size * 2);
for (int i = 0; i < this.size; i++) {
newArray[i] = this.array[i];
}
this.array = new Pair<>(key, value);
}
for (int i = this.size; i > low; i -= 1) {
this.array[i] = this.array[i - 1];
}
this.array[low].setValue(value);
} else {
int middle = low + (high - low) / 2;
Pair<K, V> current = this.array[middle];
if (current.getKey().equals(key)) {
current.setValue(value);
} else if (current.getKey().compareTo(key) < 1) {
containsHelper(key, value, middle + 1, high);
} else {
containsHelper(key, value, low, middle);
}
}
}
}
Here is a better way we can answer the question. This time, we'll use pseudocode.
Notice that here, we're mixing in English and code. We use code in places where the exact nuances of the algorithm matter, or when expressing the logic in English would be too cumbersome.
We also didn't really write Java and sort of invented our own rules. After all, we're not trying to get our pseudocode to "compile". This means we're free to really do anything we want, so long as it's understandable by other people.
public put(K key, V value):
containsHelper(key, value, 0, this.size);
private containsHelper(K key, V value, int low, int high):
if high < low:
If the array is full and needs to be resized, resize it
Shift all elements starting at low up by one
this.array[low] = (key, value)
else:
mid = low + (high - low) / 2
currentPair = this.array[mid]
if currentPair.key == key:
set currentPair's value to value
else if currentPair.key < key:
containsHelper(key, value, mid + 1, high)
else:
containsHelper(key, value, low, mid)
Another good way of explaining how the algorithm works is by just explaining in English.
After all, the reader (who we assume has also taken CSE 373 or equivalent) ought to understand what binary search is, how we do resizing in arraylist-style datastructures... In that case, why not just refer to these standard algorithms by name and focus instead on describing how we combine everything together?
Implementing SortedArrayDictionary's
put:When we want to insert a key-value pair, we start by performing binary search on the internal (sorted) array.
If the key already exists in the array, replace that pair's value with the new one.
If the key doesn't already exist in the array, the binary search algorithm will eventually find the index the new pair should exist at. In order to make room for the new pair, shift over all elements to the right of that index by one, resizing the array if necessary. Add the new key-value pair to the newly open slot.
Be careful, though; in prior quarters, the pseudocode that we saw that was primarily written in English tended to be a bit too general. The approach that mixes code with English tended to produce clearer pseudocode, as small things that matter - notes on how you are planning on keeping track of the current state, or variables that are being kept track of - came across more clearly and were generally more successful.