JavaHyperText
The links in the navigation bars above take you to webpages with videos / tutorials on many aspects of Java and data structures. Type a word into the Filter field below and only entries whose titles contain that word will be displayed. Filter: 
Type one of these words into the Filter field to see a table of contents for that topic:

The first video on this page is a 3.5minute tutorial that explains abstract classes and methods.
The first video on this page is a 3.5minute tutorial that explains abstract classes and methods.
modifier  class  package  subclass  world 

public  Y  Y  Y  Y 
protected  Y  Y  Y  N 
no modifier  Y  Y  N  N 
private  Y  N  N  N 
Basic step, including the notion of constant time: pdf file. See also pdf file.
Exercises on calculating the number of basic steps. To come
String catenation is not a basic step: pdf file.
get(k) in a LinkedList is not a basic step: pdf file.
Basic steps in executing insertion sort: pdf file.
Definition of O(...): pdf file. Exercises of proving f(n) in O(g(n)). pdf file.
Some timecomplexity classes: pdf file.
Shortcuts in deciding on complexity classes: pdf file.
Why you should never write f(n) = O(g(n)): pdf file.
Amortized time, introduced using ArrayList as an example: pdf file.
Sorting provides a lot of examples of calculating time and space requirements.
This table gives the basic sorting algorithms and links to pdf files for them:
Algorithm  Worst time  Expected time  Space 

insertion sort selection sort 
O(n^2)  O(n^2)  O(1) 
heap sort  O(n log n)  O(n log n)  O(1) 
merge sort  O(n log n)  O(n log n)  O(n) 
quick sort  O(n^2)  O(n log n)  O(n) 
quick sort improved 
O(n^2)  O(n log n)  O(log n) 
comparison sorts  no better than O(n log n) 
Annotations in a JUnit 4 testing class: See this pdf file.
1. Short definition and explanation: pdf file.
2. Use an anonymous function to check that an assertion is thrown: pdf file.
3. Use an anonymous function to sort an array or an array segment: pdf file.
4. Use an anonymous function to sort an ArrayList or LinkedList any List: pdf file.
5. Use an anonymous function to listen to button click in a GUI: pdf file.
6. Anonymous classes and interfaces with one abstract type: pdf file. DemoClassD.zip. DemoClassE.zip.
The specification of the API for Java version 1.9 appears here: docs.oracle.com/javase/9/docs/api/index.html?overviewsummary.html. Visit this site often to learn about some class (like String, or JFrame) and its methods.
public static void main(String[] pars) {...}
An application can be executed without using an IDE. One creates a jarfile that contains all the classes of the program and uses it as a standalone program.
min(x+y, y+w)
The number of arguments must equal the number of parameters of the method that is being called, and the type of each argument must be the same as or narrower than the type of the corresponding parameter.
Creating ragged/jagged multidimensional arrays, in which each row can have a different number of elements: pdffile.
Sort using an anonymous function: array pdf file, List or ArrayList or LinkedList pdf file
The notation {3, 5, 4} is called an array initializer. For more info, see this pdffile.
To execute it, evaluate the <booleanexpression>; if false, throw an AssertionError, which will generally cause the program to abort. Read this to learn about its use and how to turn on its execution.
The assignment statement has the form <variable> = <expression> ;
To be syntactically correct, the
type of the expression must be the same as or narrower than the type of the variable. To execute the assignment statement, evaluate the <expression> and store its value in the <variable>. For more information see the 2.5minute video on this webpage.
See this pdf file for a history of = for equality and why the change to the assignment operator caused confusion.
See this pdf file for the compound assignment operators += = *= /= %=.
A set is a bunch of elements with no duplicates allowed. The set {25, 5, 10} has size 3.
Some people call a bag a multi set or multiset, since an element can occur multiple times in a bag.
That goes against the usual use of an adjective to restrict, e.g. we can restrict the dogs we are considering by talking about old dogs or brown dogs.
Instead of set and multiset, we should use bag and unibag.
Proof that the height of a heightbalanced binary tree with n nodes is O(lg n). pdf file.
You might find this banquet speech, which pokes fun while giving a message, interesting: Eliminating the chaff.
Proof that a heightbalanced binary tree with n nodes has height O(log n). pdf file.
This pdf file also describes the marks of a boolean tyro, a novice, beginner.
For loops: still to come.
For recursive functions: pdf file.
Place this local declaration just before the code to be timed:
long startTime= System.currentTimeMillis();
Then, place this code just after the code to be timed:
long time= System.currentTimeMillis()  startTime;
That gives you the elapsed time in milliseconds.
1. Casting between types char and int: pdf file.
2. Casting among the number types byte, short, int, long, float, and double: pdf file.
3. Casting with classes, called class casts: pdf file.
4. 3.75minute video on casting with interfaces: webpage.
5. Compiletime casting rule (defines when a cast is syntactically OK): pdf file.
If only one of b and c are of type String, then b + c still denotes catenation, and the nonString operand is changed into its String representation before the catenation is done. If the nonString operand is of some classtype, its toString method is called to obtain its String representation.
The simplest way to get a String representation of any expression is to catenate it with the empty String. For example, "" + (68 + 2) evaluates to a String that contains "70".
The class definition also defines the static variables (class variables) and static methods (class methods).
A class can be used as a type. If C is (the name of) a class, then C v; declares a variable v that contains either null or the name of (or pointer to) an object of class C.
A. Format of the class definition and what an object of the class looks like: pdf file.
B. Using keyword extends to define subclasses (and superclasses);
what a subclass object looks like: pdf file.
C. Definition of inheritance: see inheritance.
D. Class Object, the superest class of them all, and the class hierachy: page 2 of pdf file.
E. Overriding a method and the use of "super.": pdf file.
F. Keyword this eveluates to a pointer to the object in which it occurs; the user of "this.": pdf file.
2. Constructor. Purpose: To initialize fields of an object when it is created in order to
make the class invariant true.
A. The newexpression. Syntax: new <constructorcall> . 2minute video on this webpage.
B. Rule: initialize superclass fields before subclass fields. pdf file.
C. Syntactic rule: a constructor that you write must start with a call on another constructor;
what call is inserted if it is not present. pdf file.
D. How to call another constructor using super(...) or this(...). pdf file.
E. What constructor is inserted if a class does not have a constructor. pdf file.
3. The class/interface as a type.
A. A class name can be used as a type. Its values are pointers to objects of that class (and also null).
A variable of some classtype C contains a pointer or reference to an object of type C.
B. An interface name can also be used as a type. Its values are pointers to objects of any class C
(and also null) that implements the interface.
C. The compiletime reference rule determines whether a component reference like p.v or p.m(...)
is syntactically correct: pdf file.
D. The bottomup or overriding rule determines which method will be called at runtime: pdf file.
4. Abstract class. Make a class abstract so that it cannot be instantiated —objects of the class cannot
created. Make a method in an abstract class abstract so that subclasses must override it.
The first video on this page, 3.5minutes long, explains abstract classes and methods.
5. Interfaces. An interface provides a way to ensure syntactically (at compiletime) that a class implements
certain methods. The interface defines the methods abstractly (without bodies), and the class definition
then includes an implements clause to indicate that it will define the methods.
A. 2.4minute tutorial that explains interfaces: second video on this page.
B. How an interface defines an abstract data type (ADT): pdf file.
C. Multiple inheritance and the diamond problem: pdf file
A constructor should truthify the class invariant. Each method body can assume that the class invariant is true and should terminate with the class invariant true.
Also called reference type because a value of the type is a pointer or reference to an object.
Later pdf files will explain how to clone in Java.
the same color. One application is a map, in which the nodes are countries and adjacent countries are connected by an edge.
More on the fourcolor theorem later.
The worstcase time using comparison sorting to sort an array of size n is O(n log n).
Read about comparison sorting in this pdf file.
In a full binary tree, each node has 0 or 2 children.
A perfect binary tree is a full binary tree in which all leaves are at the same level.
Thus, a perfect binary tree is a complete binary tree in which every level is completely filled.
Still to come: a pdf file with examples of such trees.
A complete directed graph with n nodes has n(n1) edges. A complete undirected graph of n nodes has half as many: n(n1)/2.
See this pdf file.
1. Cores and processing units, processes and threads: pdf file 1.
2. Learn about race conditions (pdf file 2) and deadlock (pdf file 3).
3. Class Thread and interface Runnable. pdf file 4.
4. Some methods of class Thread. pdf file 5.
5. Intro to synchronized statements and methods. pdf file 6.
20sec video of Christopher Caspersen's new outhouse (2018): video.mov.
Warning: Don't know what you're doing?
Synchronize all accesses to an object: bottom of page 2 of pdf file 6.
6. Intro to wait(), notify(), and notifyAll(). pdf file 7.
Warning: Don't know what you're doing? Don't use notify(). pdf file 8.
7. Implementing a bounded queue in an array and a bounded buffer. pdf file 9.
8. Java classes that provide for concurrency. pdf file 10.
9. What's a daemon thread? pdf file 11.
5 < 4 ? 1+6 : 3 evaluates to 3 since the booleanexpression is false
5 > 4 ? 1+6 : 3 evaluates to 7 since the booleanexpression is true
Here's a simple example. Consider a graph with 3 nodes and no edges. Then each node is a connected component, and the graph has 3 connected components.
public static final double PI= 3.1415926535897932384626433832795;
The purpose of a constructor is to initialize the fields of a new object of class <classname> so that the class invariant is true when the object is created. See this pdf file for:
(1) Rule: initialize superclass fields before subclass fields.
(2) Syntactic rule: a constructor that you write must start with a call on another constructor; what call is inserted if it is not present.
(3) How to call another constructor using super or this.
(4) What constructor is inserted if a class does not have a constructor.
HERE is a summary of all important points concerning constructors: pdf file.
1. In a newexpression. It has the form <classname> ( <arguments> )
2. As a call of another constructor in the same class: this(<arguments>);.
3. As a call of a constructor of the superclass: super(<arguments>);.
public <classname>() {}
David Gries's PhD genealogy —it's a DAG and not a tree: pdf file.
Topological sort, an algorithm to produce an ordering of a DAG in which the source of each edge precedes its sink: pdf file. Proof that a directed graph in which each node has indegree > 0 contains a cycle: pdf file.
Here is an example. Consider type list: the collection of lists of values like (3, 5, 2) together with operations to add and delete elements, to search for them, etc.
Java class ArrayList is an example of a data structure that implements type list. The singly linked list, as described in this pdf file, is another example of a data structure that implements type list.
The degree of a node in a tree is the number of children it has. Thus, a leaf has degree 0. See this pdf file.
These terms are not well defined in the literature. So we use these definitions:
A graph with n nodes is dense if the number of edges is proportional to n*n; it is sparse if the number of edges is O(n).
A map of a city is generally a sparse graph because the number of edges leaving each intersection is generally 4 or less.
The level of a node is 1 + (its depth).
The height of a node is the length of a longest path from that node to a leaf.
The height of an empty tree is 1.
The height of a nonempty tree is the height of its root.
The width of a tree at depth d is the number of nodes with depth d.
The width of a tree is the maximum of its widths at all depths.
See this pdf file.
2. Shortest path algorithm: webpage.
3. Dijkstra's paper containing the shortest path and minimum spanning tree algorithms: pdf file.
4. Implementing the JPD algorithm: pdf file.
5. Using the JPD spanningtree algorithm to construct a maze: pdf file. Java: mazeGeneration.zip
6. Dining philospher's problem: pdf file.
A narrowing cast is a cast of an expression to a narrower type, e.g. double to int. Narrowing casts must be called for explicitly.
An upcast, or upward cast, is a cast of that object to one of the superclasses or superinterfaces of C. Upcasts will be done automatically when necessary.
A downcast, or downward cast, is a cast of that object to one of the subclasses or subinterfaces of C. Downcasts casts must be called for explicitly.
Use the Eclipse menu in the navigation bar at the top of the page to learn more.
To learn more about IDEs in general, read this Wiki page.
The basics: pdf file.
Adding fields and methods to an enum class: pdf file.
\n —newline character
\\ —backslash character
\" —double quote character
\' —single quote character (you can use ' in a String, but as a character, write '\''
For information on increment/decrement expressions ++ and , see this pdf file.
Look here for constant expressions.
Calculating Fibonacci numbers: pdf file.
A paper by Parmanand Singh on the ancient history of Fibonacci numbers: pdf file.
Fibonacci numbers in architecture and nature: pdf file (to come).
Uses of Fibonacci numbers in computer science: pdf file (to come).
public static final double PI= 3.141592653589793;
A class that is declared with keyword final cannot be extended cannot have a subclass.
You can enable the use of the foreach statement on your own collection class by implementing interfaces Iterator and Iterable. This tutorial shows you how in less than 15 minutes of video: webpage.
An undirected graph is a forest if each of its connected components is a tree. See this pdf file on spanning trees.
(1) the name of the method,
(2) a program counter, which indicates which statement to execute next,
(3) a scope box, which contains the name of the class or object in which the method resides,
(4) the parameters of the method, and
(5) the local variables of the method.
This webpage discusses the frame for a call.
1. for a static function: <classname> . <functionname> ( <arguments> )
2. for a nonstatic function: <expression> . <functionname> ( <arguments> )
where the <expression> evaluates to the name of an object that contains the function to be called. Both "<classname>." and "<expression>." can be omitted if the call appears in a place in which the function can be called without them.
2. Introduction to generic classes: pdf file.
3. Introduction to generic methods: pdf file.
4. Creating a generic array: pdf file.
5. Why ArrayList<Integer> is not a subclass of ArrayList<Object>: pdf file.
6. Introduction to wildcards: pdf file.
7. Introduction to bounded wildcards: pdf file.
8. Examples of upperbounded types: pdf file.
9. Examples of lowerbounded types: pdf file.
10. Multiple upper bounds: pdf file.
11. Restrictions on the use of generic types: pdf file.
12. Discussion of raw types: pdf file.
1. Full explanation: pdf file.
2. An example where instanceof and not getClass() should be used: pdf file.
2. Basic graph terminology and kinds of graphs: pdf file.
3. Adjacency list and adjacency matrix representations of a graph: pdf file.
4. DAGs and topological sort: pdf file. Proof that a directed graph in which each node has indegree > 0 contains a cycle: pdf file.
5. Planarity: pdf file.
6. The fourcolor theorem: pdf file. Sipka's paper on Kempe's flawed proof: pdf file. Gonthier's paper on the Coq proof: pdf file.
7. The GriesXue presentation of the HopcroftTarjan planarity algorithm: pdf file.
8. Depthfirst search, breadthfirst search, and depthfirst walk: webpage.
9. Dijkstra's shortest path algorithm: webpage.
10. Spanning tree of an undirected connected graph: pdf file.
11. Minimumcost spanning tree, Kruskal, Prim, and the JPD algorithm: pdf file.
12. Implementing the JPD algorithm: pdf file.
13. Using the JPD algorithm to construct random mazes: pdf file. Java: spanningMaze.zip
See this pdf file for the definition and examples.
Here's his website.
Here's his PhD genealogy from the Math Genealogy Website. He wrote a Java program to comb that website and produce the pdf file.
If a class overrides function equals and if that class may be used in any Collections class that deals with hashing (e.g. class HashSet and HashMap), then the class must also override function hashCode so that: if b.equals(c), then b.hashCode() == c.hashCode(). This pdf file explains why. Here is a tutorial on hashing.
Given a value, a hash function is used to obtain an index into the hash table where the value might be stored.
Here is a tutorial on hashing.
Two important Java collections classes that implement sets and maps using hashing are java.util.HashSet and java.util.HashMap.
2. Java class ArrayHeap, maintaining a bag of ints as a minheap: heapArray.zip
3. Implementing a heap in which the values are different from the priorities: pdf file.
4. HeapSort, an insitu O(n log n) sorting algorithm: pdf file. JavaHeapSort.zip
Static components are not overridden but are hidden. This is explained in this pdf file.
import <path>.<classname>; // import a particular class
import <path>.*; // import all classes in the package
where the <path> is a path of the API package (e.g. javax.swing) or a path to a directory on your hard drive that represents a package of classes.
See the second page of this pdf file for more information.
See menu item Eclipse > Remove unused imports to see how to easily remove unused import statements from a class.
The Java spec uses "inheritance" slightly differently: private fields are not inherited. However, the private fields DO appear in each object of the subclass, so we think the Java use of "inherited" is wrong and will continue to say that ALL components are inherited.
Here's an analogy. Suppose a 16yearold son's parent's die. He inherits their money. But the money is put in a Trust, and, he cannot touch the money until he is 18. That's like saying the private field appears in each object of the subclass but cannot be directly referenced from the subclass.
(0) Why nested classes are useful: pdf file.
(1) Study this example of the use of a static nested class before reading the next example: pdf file.
(2) A simple but realistic example of the use of an inner class: pdf file.
2. A bit about the Java IO packages; intro to paths of files and directories: pdf file.
3. Interface Path and classes Files and Paths: pdf file.
4. Read a text file using a BufferedReader: pdf file.
5. Write a text file using a BufferedWriter and a PrintWriter: pdf file.
6. Read a webpage —class URL: pdf file.
7. Reading the keyboard: pdf file. KeyBoardDemo.java.
8. Use a JFileChooser to obtain a Path: pdf file.
Explanation: pdf file.
Referencing a field that has been shadowed because of the insideout rule: pdf file.
Selection sort is an in situ sorting algorithm.
Quicksort is an in situ sorting algorithm; it works by modifying the array itself. But it needs extra space for recursive calls. It can be written to require only O(n log n) space on the call stack.
Mergesort is not an in situ sort algorithm because it generally copies 1/2 of the array into another array in order to be able to merge two sorted adjacent array segments efficiently. It also requires O(n log n) space on the call stack.
1. Full explanation: pdf file.
2. An example where instanceof is needed: pdf file.
See this pdf file for an explanation.
1. Explanation of char: pdf file.
2. Explanation of byte, short, int, and long: pdf file.
1. 2.4minute tutorial that explains interfaces: second video on this page.
2. How an interface defines an abstract data type (ADT): pdf file.
3. Multiple inheritance and the diamond problem: pdf file.
By use iteration we mean: use a loop of some sort.
Shakespeare didn't like iteration. In Henry IV, Pt I, 1 ii, one person says, "Thou hast damnable iteration and art, indeed, able to corrupt a saint." I guess he liked recursion better.
Implementing the Jarník/Prim/Dijkstra algorithm: pdf file.
Using the JPD spanningtree algorithm to construct a maze: pdf file.
1. Why javadoc specs are useful to you as you program: pdf file.
2. Eclipse will format your javadoc comments whenever a file is saved.
Put the html tag <br> at the end of each line of a javadoc comment where you want it to start a new line.
3. Generating a javadoc webpage; how to fix Eclipse if the javadoc command is not found: pdf file.
Implementing the Jarník/Prim/Dijkstra algorithm: pdf file.
Using the JPD spanningtree algorithm to construct a maze: pdf file.
It's kind of like DrJava's interactions pane, though it may be a bit harder to use for some things.
But you can even type in a method without having to have a complete class and then call it.
I requires Java 9.
If you don't have Java 9, you can use this website: https://tryjshell.org.
1. Writing a JUnit testing class in Eclipse, for example, to test the methods in a class: webpage.
2. Testing whether an assert statement is correct: pdf file.
3. Testing whether a method call throws a particular exception: pdf file.
4. Eclipse JUnit testing to show code coverage: pdf file.
5. JUnit 5 annotations: pdf file.
In hashing using open addressing, the elements in the set are stored in buckets of the hash table. Collisions may occur in that several values may hash to the same bucket.
Suppose element e hashes to bucket number h.
In linear probing, to see whether e is in the set, buckets h, h+1, h+2, h+3, ... (with wraparound) are probed until e is found or null is found, in which case e is not in the set.
In quadratic probing, the probed buckets are h, h+1*1, h+2*2, h+3*3, ... (with wraparound).
In double hashing, two hash functions are used. Suppose hashing e with the two hash functions gives two integers h1 and h2. Then the probed buckets are h1, h1 + h2, h1 + 2*h2, h1 + 3*h2, ... (with wraparound).
See this webpage for a tutorial on hashing. Look in Wikipedia under double hashing for more information on that topic.
SLiterals of the number types (like int and float): pdf file.
Literals of type char: pdf file.
Principle: Place a local variable as close to its first use as possible. Do not simply declare all local variables at the beginning of a method. FOLLOW THIS PRINCIPLE.
forloop, whileloop, doloop, foreach loop.
2. You can enable the use of the foreach statement on your own collection class by implementing interfaces Iterator and Iterable. This tutorial shows you how in less than 15 minutes of video: webpage.
Loop invariants are used to prove loops correct and, more importantly, to help in the development of loops.
1. Thorough discussion of loop invariants: webpage.
2. Brief intro to loop invariants: pdf file.
Here, in brief, are the 4 loopy questions, using the name P for the invariant:
1. Does it start right: does the initialization truthify P?
2. Does it end right: Does the falsity of the loop condition together with P imply that the postcondition is true?
3. Does the repetend make progress toward termination?
4. Does the repetend main P: if P and loop condition are true, does execution of the repetend end with the P true?
The difference between a map as a data structure and a function is that one can add (and delete) key/value pairs to a map, while one cannot do that for the usual function.
Think of a map as a dictionary: a key is a word and the corresponding value is the meaning of the word. Thus, a dictionary is a set of word/meaning pairs. In fact, the programming language Python uses the word dictionary instead of map.
Maps are often implemented using hash tables or some kind of search tree. In Java, take a look at interface java.util.Map and class java.util.HashMap.
The mean of {5, 3, 5, 9} is 5.5.
For a bag of numbers of odd size, the median is the middle value. For a nonempty bag of even size, it is the mean of the two middle values.
The median of the bag {1, 1, 3, 4, 5} is 3. The median of the bag {2, 3, 4, 5, 6, 7} is 4.5.
1. Push a frame for the call onto the call stack;
2. Assign argument values to the parameters;
3. Execute the method body;
4. Pop the frame for the call from the call stack (and, if a function, put the function value onto the call stack).
the signature of method <T, E> m1(T p, E q) {...} would be <T1, T2> m1(T1, T2)
the signature of method <E1, E2> m2(E1 x, E2) {...} would be <T1, T2> m2(T1, T2)
so they are the same except for the name of the method.
A minimumcost spanning tree of G is a spanning tree of G whose sum of the weights on its edges is a minimum.
See this pdf file.
byte > short > int > long > float > double
char > int > long > float > double
subclass > superclass
See cast to find complete information on casting.
1. Why nested classes are useful: pdf file.
2. A simple but realistic example of the use of a static nested class: pdf file.
3. A simple but realistic example of the use of an inner class: pdf file.
Explanation of char: pdf file.
Explanation of byte, short, int, long, float, and double: pdf file.
For example, if the children are implemented as a Java List, the tree is ordered; if implemented as a Java Set, the tree is unordered.
Binary trees are naturally ordered, with the left child first and then the right child.
Fields are not overridden but are hidden. This is explained in this onepage pdf file.
Static components are not overridden but are hidden. This is explained in this onepage pdf file.
See this pdf file for an explanation.
The default access modifier used when no access modifier is present in a declaration. A variable or method that is declared without a modifier can be referenced in any class declared within this package.
If the graph is undirected, {vk, v(k+1)} is an edge,
If the graph is directed (vk, v(k+1)) is an edge.
The length of the path is the number of edges, i.e. p. See this pdf file.
Often, we speak only of downward paths, meaning that each edge goes from a node to one of its children.
The length of the path is the number of edges, i.e. p. See this pdf file.
Presentation by Gries and Xue of the HopcroftTarjan lineartime planar testing algorithm: pdf file.
As a convention, we write a precondition in a specification as "Precondition: ..." to make it as clear as possible. We generally can use the assert statement to check a precondition. Read about it here.
(2) An assertion placed (as a comment) before a statement in a program to indicate what is true at that place during execution.
Implementing the Jarník/Prim/Dijkstra algorithm. pdf file.
Using the JPD spanningtree algorithm to construct a maze: pdf file. mazeGeneration.zip
1. Explanation of primitive type char: pdf file. This pdf file explains what to watch out for when characters not in type char are used in Strings.
2. Explanation of the other primitive number types: byte, short, int, long, float, and double: pdf file.
3. Explanation of type boolean: pdf file.
1. for a static procedure: <classname> . <functionname> ( <arguments> ) ;
2. for a nonstatic procedure: <expression> . <functionname> ( <arguments> ) ;
where the <expression> evaluates to the name of an object that contains the procedure to be called. Both "<classname>." and "<expression>." can be omitted if the call appears in a place in which the procedure can be called without them.
We jokingly say it means Quit End Done.
2. A priority queue is a queue in which each item in it has a priority, and method remove
removes and returns the item with lowest priority. pdf file.
3. The first page of this pdf file shows how to efficiently implement a bounded queue in an array.
2. The partition algorithm of quicksort: pdf file.
3. The basic quicksort algoriithm: pdf file.
4. Quicksort improved in three essential ways: pdf file.
5. Constantspace quicksort: end of this pdf file. Article: pdf file.
results in unexpected (and wrong) results. See this pdf file.
For radix sorting, see this pdf file.
But if you are not familiar with arrays in Java, read this first: pdf file.
1. Introduction to recursion: pdf file.
2. How a method call is executed, including a recursive call (so you see that recursive calls work): webpage.
3. Understanding a recursive method, about base cases and recursive cases: pdf file.
4. Developing a recursive function: pdf file.
5. Using a bound function to prove termination: pdf file.
6. Recursion may require extra parameters: pdf file.
7. Videos that develop recursive methods for traversing trees: webpage.
8. Development of a function to decide whether a binary tree is a binary search tree (BST): pdf file.
9. A recursive function to adds up the integers in an Integer array of any number of dimensions: pdf file.
10. Definition of tail call and a discussion of how to optimize them: pdf file.
11. Calculating b^n for integer n ≥ 0 in O(log n) time and space recursively: pdf file. Java code
1. The Eclipse refactor tool; using it to change a name (i.e. an identifier): pdf file.
2. Extract a local variable: highlight an expression whose value is to be assigned to the new local variable: pdf file.
3. Extract a method and inline a method call: pdf file.
4. Refactoring a version of selectionSort, using both extracting a method and inlining a method call: pdf file.
public JFrame jf;
contains either null or a pointer to, i.e. a reference to, an object of class JFrame.
Refactoring a version of selectionSort, using both extracting a method and inlining a method call: pdf file.
1. How to use "this." to reference a shadowed field: pdf file.
1. Four videos that (1) give history, (2) state the problem, (3) show the invariant of the algorithm, and (4) develop the algorithm from the invariant: webpage.
2. Extend the algorithm to calculate and save not only the shortestpath distances but the shortest paths themselves, using backpointers: pdf file.
3. Analyze the runtime of the algorithm: pdf file.
4. Discuss implementing the algorithm in a realistic way. It can be used as the basis of a programming project: pdf file.
1. Stable sorting: A sort is stable if equal values stay in their same relative position. For example, if an array contains (..., 5, 3, 5, ...) and sorting changes the two 5's to this: (... 5, 5, ...), the sorting is not stable.
2. Comparison sorts, which sort using comparisons like b[i] < b[j] or b[i].compareTo(b[j]): pdf file.
2A. insertion sort and selection sort: pdf file.
2B. quick sort: The partition algorithm. Basic quicksort. Essential improvements to quicksort.
2C. constantspace quicksort: end of this pdf file. Article: pdf file.
2D. merge sort: Merging two adjacent sorted segments. Merge sort.
2E. heap sort: pdf file. JavaHeapSort.zip
3. Noncomparison sorts. Some history, starting with mechanical/electrical tabulators/sorters. pdf file.
3A. pigeonhole sort: pdf file.
3B. counting sort, a variation of pigeonhole sort: pdf file.
3D. radix sort: pdf file.
4. Using an anonymous function: sorting an array pdf file, sorting a List, ArrayList, or LinkedList pdf file.
5. For a broad overview of sorting, summarizing over 40 sort algorithms, see: en.wikipedia.org/wiki/Sorting_algorithm
6. Java classes that contain all the sorting algorithms discussed above, with JUnit tests: sortSearch.zip
2. Minimumcost spanning tree, Kruskal, Prim, and the JPD algorithm: pdf file.
3. Implementing the JPD algorithm: pdf file.
4. Using the JPD spanningtree algorithm to construct a maze: pdf file. mazeGeneration.zip
These terms are not well defined in the literature. So we use these definitions:
A graph with n nodes is dense if the number of edges is proportional to n*n; it is sparse if the number of edges is O(n).
A map of a city is generally a sparse graph because the number of edges leaving each intersection is generally 4 or less.
2. Merge sort is usually implemented so that it is stable.
3. Quicksort is inherently unstable because the partition algorithm is inherently unstable.
Why nested classes are useful: pdf file.
A simple but realistic example of the use of a static nested class: pdf file.
1. How to study in this course take this seriously: pdf file.
2. The process of completing a programming assignment seriously: pdf file.
3. Summary of how to study and a list of items to be mastered: pdf file.
Thus, we use C for two things: either a node or the subtree with C as its root. See this pdf file.
(1) super.m(...) calls method m within the object in which it appears. To determine which version of m is called, use the bottomup (overriding) rule, but start looking in the partition above the one in which the method call appears.
(2) super(...); can appear as the first statement in a constructor; it calls a constructor of the superclass which one is called depends on the types of the arguments within the parentheses..
20sec video of Christopher Caspersen's new outhouse (2018): video.mov.
<variable> = <expression> ;
See JUnit testing to find out how to write and run repeatable testing procedures.
Eclipse JUnit testing to determine whether whitebox testing gives complete code coverage: pdf file.
(1) this is an expression; it evaluates to the name of (pointer to) the object in which it appears. For example, this.x is a reference to a field x of the object. Generally, we refrain from using "this." indiscriminately to avoid useless clutter. This pdf file shows how to use it to reference a shadowed field.
(2) "this(...);" can appear as the first statement in a constructor; it calls another constructor in this class which one is called depends on the types of the arguments within the parentheses.
Watch a 3.2minute video on throwable objects here.
0. Suppose the throwstatement is not within a tryblock, and it is in some method m. Suppose m was called in a call m(...). Throw object a0 to that call m(...) and act as if that call threw the object. Point 3 says what happens if it is within a tryblock.
1. 3.2minute video on throwable objects: webpage.
2. 5minute video on interpreting the output of an uncaught thrown object: webpage.
3. Videos on the throwstatement and on catching and throwing the exception further: webpage.
1. Intro to trees, tree terminology: pdf file.
2. Examples of trees: pdf file.
3. Binary trees: pdf file.
Preorder, inorder, and postorder traversals of a binary tree. pdf file.
4. Balanced trees: A tree with n nodes is balanced if its height is O(lg n).
This pdf file discusses balanced trees in terms of BSTS (item 5): pdf file.
Proof that the height of a heightbalanced tree with n nodes is O(log n): pdf file.
5. Binary search trees (BSTs): pdf file.
5A. Takeoffs on BSTs (AVL tree, 23 tree, Btree, redblack tree): pdf file.
6. Representing arithmetic expressions as trees: pdf file. Java implementation: treeExpressions.zip.
7. Heaps, both minheaps and maxheaps
7A. Definition of a maxheap and minheap: pdf file.
7B. Java class ArrayHeap, maintaining a bag of ints as a minheap: heapArray.zip
7C. Implementing a heap in which the values are different from the priorities: pdf file.
7D. Heap sort, an insitu O(n log n) sorting algorithm: pdf file. JavaHeapSort.zip.
8. Spanning tree of a graph: pdf file. See also spanning tree.
try <statement>
catch (<classname1 e1>) <catchstatement1>
...
catch <classnamen en>) <catchstatementn>
where each of the <classnames> is a throwable class. There can also be a "finally clause", which we don't discuss. The trystatement is explained, with videos, here and also in this pdf flle.
Java has primitive types and class types.
0. Strong vs weak typing in a programming language: pdf file.
1. Type integer: the integers ..., 2, 1, 0, 1, 2, ... with operators +, , *, +, etc.
2. Primitive types: byte, short, int, long, float, long, char, boolean: pdf file.
For primitive type char: pdf file.
For primitive type boolean: pdf file.
Integral type: byte, short, int, long, char.
Number type: byte, short, int, long, float, long, char: pdf file.
3. Class name or interface name can be used as a type: Its values are names of
(pointers to) objects that contain a partition with that name (and also null).
E.g. the declaration JFrame j; indicates that variable j can contain a pointer
to any object that has a JFrame partition.
4. Wider/narrower types. Each line below gives a series of types; left is narrowest, right is widest:
byte > short > int > long > float > double
char > int > long > float > double
subclass > superclass or class > interface or subinterface > superinterface
5. Unary prefix Cast operator: (type) or (classname) or (interfacename)
e.g. (int) 5.3 casts float value 5.3 to type int, truncating to 5.
Widening casts may be inserted automatically. Narrowing casts must be
done explicitly because they may lose information.
Casting among number types: pdf file.
Casting between char and int: pdf file.
Casting among classes, called class casts: pdf file.
Casting with interfaces: 3.75minute video (webpage).
6. Compiletime reference rule: This rule determines whether a component reference like
p.v or p.m(...) is syntactically correct. It has to do with the type of p. See this pdf file.
Java primitive types:
 (6+2), 6! . Unary prefix operators have highest precedence and are evaluated from right to left. E.g.  +  8 + 5 is evaluated as ((+( 8))) + 5. See also ternary operator and binary operator.
An underdetermined specification of an algorithm allows for implementations that could give different results.
A simple example. Suppose the spec says to put the 0's in an array first.
So the array containing (5, 0, 0, 3) could be changed to (0, 0, 3, 5) or (0, 0, 5, 3).
Underdetermined specs can be a good thing, giving the implementor more freedom in finding an efficient solution.
This pdf file explains what to watch out for when characters not in type char are used in Strings.
1. parameter: a variable declared within the parentheses of a method (i.e. procedure, function, or constructor) header.
2. local variable: a variable declared in a method body. See pdf file.
3. field (or instance variable). See pdf file.
4. class variable (or static variable). See pdf file.
Use this function call to test whether a character c is whitespace: Character.isWhitespace(c).
The old Java function s.trim() returns a copy of s with leading and trailing characters removed if they are ≤ '\u0020'. This includes '\t', '\n', and '\r' but neglects some newer Unicode characters.
Function s.strip(), introduced in Java version 11, is similar but removes exactly white space.