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.5-minute tutorial that explains abstract classes and methods.
The first video on this page is a 3.5-minute 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 |
See also polymorphism.
2. 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.
3. Definition of O(...): pdf file. Exercises of proving f(n) in O(g(n)). pdf file.
Some time-complexity classes: pdf file.
Shortcuts in deciding on complexity classes: pdf file.
Why you should never write f(n) = O(g(n)): pdf file.
4. Amortized time, introduced using ArrayList as an example: pdf file.
5. 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 functions and functional interfaces: 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?overview-summary.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 jar-file that contains all the classes of the program and uses it as a stand-alone 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: pdf-file.
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 pdf-file.
To execute it, evaluate the <boolean-expression>; 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.
assertEquals(expected-value, computed-value) is used in a JUnit testing class to test whether
a computed value is correct. Never use an assert statement for this purpose.One can also use methods
assertTrue(computed value) and
assertFalse(computed value). See webpage.
assertThrows(exception.class, anonymous-function) is used to tell
whether a call of the anonymous function throws the exception.
See webpage.
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.5-minute 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 height-balanced 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.
Recursion on binary trees: page 2 of this pdf file.
OO-oriented implementation of binary trees: pdf file.
Proof that a height-balanced 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.
See this pdf file for a longer explanation with more examples of caches.
Here's a use of a cache in software to make a recursive method more efficient: 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.75-minute video on casting with interfaces: webpage.
5. Compile-time 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 non-String operand is changed into its String representation before the catenation is done. If the non-String operand is of some class-type, 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);
C. What a subclass object looks like: pdf file.
D. Subclasses and the "is-a" relation: one-page pdf file.
E. Definition of inheritance: see inheritance.
F. Class Object, the superest class of them all, and the class hierachy: page 2 of pdf file.
G. Overriding a method and the use of "super.": pdf file.
H. 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 new-expression. Syntax: new <constructor-call> . 2-minute 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;
if it doesn't, the call super(); is inserted. pdf file.
D. How to call another constructor using super(...) or this(...). pdf file.
E. If a class C does not have a constructor, this one is inserted: C() {}. 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 class-type 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 compile-time reference rule determines whether a component reference like p.v or p.m(...)
is syntactically correct: pdf file.
D. The bottom-up 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.5-minutes long, explains abstract classes and methods.
5. Interfaces. An interface provides a way to ensure syntactically (at compile-time) 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.4-minute 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.
An explicit conversion, e.g. (float) 5 or (int) 5.3, is called a cast.
An implicit conversion performed by the Java system is often called a coercion rather than a cast. An example is the coercion of int 5 to double value 5.0 in the assignment double d= 5;
the same color. One application is a map, in which the nodes are countries and adjacent countries are connected by an edge.
See this pdf file for the greedy graph coloring algorithm.
More on the four-color theorem later.
// 1. This comment starts with two slashes and ends at the end of the line.
/* 2. This possibly multi-line comment starts with slash star and ends with: */
/** 3. This special possibly multi-line comment, called a javadoc comment, starts
* with slash star star and ends with: */
The term, "javadoc" stands for "java documentation". Place a javadoc comment BEFORE each class, method, and field declaration in order to describe or specify that declaration. These comments can be extracted by an app called javadoc in order to provide a specification of a class. Eclipse also makes use of javadoc comments, e.g. hover the mouse over a method call and the spec of the method will pop up.
In writing javadoc comments, help format them nicely by using the html tag <br> to end a line.
The worst-case time using comparison sorting to sort an array of size n is O(n log n).
Read about comparison sorting in this pdf file.
For more information, read this this two-page 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(n-1) edges. A complete undirected graph of n nodes has half as many: n(n-1)/2.
See this pdf file.
1. Cores and processing units, processes and threads: pdf file 1.
Click here for a definition of thread-safe.
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.
* Example of using the back door: pdf file. Demo code: BackDoor.zip
* 20-sec 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.
Code that illustrates the above using a dropbox (bounded buffer of size 1). boundedBufferDemo.zip.
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 boolean-expression is false
5 > 4 ? 1+6 : 3 evaluates to 7 since the boolean-expression 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 <class-name> 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 new-expression. It has the form <class-name> ( <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 <class-name>() {}
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 non-empty 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.
Code that uses a dropbox to illustrate use of notify() and notifyAll(). boundedBufferDemo.zip.
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 spanning-tree 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.
DrJava's Interactions Pane made it extremely easy to try out different things, because you could type any statement or expression and have it executed or evaluated immediately. For example, you could write: f= new javax.swing.JFrame(); to create a new JFrame object and store (a pointer to) it in f. We used to teach Java in the first programming course at Cornell. Students didn't know they needed a method main until week 10 of the course, because we relied on the Interactions Pane and JUnit testing for all work. You can still download DrJava from www.drjava.org.
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.
Tony Hoare said: "Inside every large program is a small program struggling to get out."
Edsger Dijkstra said: "Beauty is our business.""
if (b) S1 else S2 ,
statement S1 is called the then-part and S2 is called the else-part.The basics: pdf file.
Adding fields and methods to an enum class: pdf file.
Consider the set {4, 7, 2}. A set is unordered, so an enumeration of its values is a list of them, in an arbitrary order. Here's one example: 4, 2, 7.
To enumerate the values in the set is to produce its values one by one. For example, to enumerate the set above, produce 4, then 3, then 7.
This is explained in the first video in the tutorial on Iterator/Iterable
\n —new-line character
\\ —backslash character
\" —double quote character
\' —single quote character (you can use ' in a String, but as a character, write '\''
1 XOR 1 = 0, 0 XOR 0 = 1, 1 XOR 0 = 1, 0 XOR 1 = 1.
In a similar manner, one defines the XOR of two boolean values:
T XOR T = F, F XOR F = F, T XOR F = T, F XOR T = F.
Here, one can see that b XOR c is just b ≠ c, and there's no need to introduce XOR.
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: <class-name> . <function-name> ( <arguments> )
2. for a non-static function: <expression> . <function-name> ( <arguments> )
where the <expression> evaluates to the name of an object that contains the function to be called. Both "<class-name>." 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 upper-bounded types: pdf file.
9. Examples of lower-bounded 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.
ob has a field time, the convention is to have a method ob.getTime().
Note that a static function getTime(ob) could also be called a getter method, but that is not
the convention.Do not use this convention! It reveals the state of the object. Instead, if you need this method, call it
time() and not getTime(), and in
its specification don't mention that time is a field.
This pdf file discusses
an alternative to the getter/setter terminology: pdf filegoto L, which would cause execution to jump to the statement
labeled L. Its use often led to "spaghetti code" --completely unstructured code with jumps all over the place, making
the code difficult to understand and maintain. In 1968, Edsger Dijkstra wrote an article in the Communications of the ACM titled
Go To Statement Considered Harmful, saying that it should not be used. Some people wrote letters to that journal,
raking him over
the coals for trying to hinder programmers in their innovative work. As usual, Dijkstra was right, and you don't see
the goto in current languages. You do see controlled uses
of it, for example, the break and continue statements in Java. Java's use of goto as a keyword means that it cannot
be used as an identifier.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 four-color theorem: pdf file. Sipka's paper on Kempe's flawed proof: pdf file. Gonthier's paper on the Coq proof: pdf file.
7. The Gries-Xue presentation of the Hopcroft-Tarjan planarity algorithm: pdf file.
8. Depth-first search, breadth-first search, and depth-first walk: webpage.
9. Dijkstra's shortest path algorithm: webpage.
10. Spanning tree of an undirected connected graph: pdf file.
11. Minimum-cost 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
14. Greedy graph coloring algorithm pdf file.
See this pdf file for the definition and examples.
See this pdf file for the greedy graph coloring algorithm.
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.
2-page discussion of hash functions: pdf file.
Tutorial on hashing: web page.
2-page discussion of linear probing, quadratic probing, and double hashing: pdf file.
Paper titled How Caching Affects Hashing: pdf file.
2-page intro to cuckoo hashing: pdf file.
2-page intro to Robin Hood hashing: pdf file.
Two important Java collections classes that implement sets and maps using hashing: java.util.HashSet and java.util.HashMap.
2. Java class ArrayHeap, maintaining a bag of ints as a min-heap: 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>.<class-name>; // 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 16-year-old 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.
Encapsulation is Java's way of implementing information hiding.
(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 inside-out 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.4-minute 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.
4. For functional interfaces, see this 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 spanning-tree 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.
e0Eclipse.zip e0jshell.zip.
Once you know a bit about grammars and such, you can read most of this spec yourself, to get details right from the horse's mouth. Here is the spec for version 14: Java 14 spec
Implementing the Jarník/Prim/Dijkstra algorithm: pdf file.
Using the JPD spanning-tree algorithm to construct a maze: pdf file.
Here is a basic introduction to its use: pdf file.
This file show Eclipse and JShell together can be used to explore features of Java: pdf file.
Here is the Java 11 guide to the use of JShell: docs.oracle.com/en/java/javase/11/jshell/index.html.
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 defined using a polynomial; the simplest such probe sequence is: 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 h and H. Then the probed buckets are h, h + H, h + 2*H, h + 3*H, ... (with wraparound).
See this webpage for a tutorial on hashing.
See this pdf file for more detail on linear probing, quadratic probing, and double hashing.
Video that develops a recursive method to reverse a singly linked list in place: webpage.
Using an anonymous function to sort a LinkedList: pdf file.
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.
for-loop, while-loop, do-loop, 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 maintain P: if P and loop condition are true, does execution of the repetend end with 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.
See this pdf file to learn the basics about Java's interface java.util.Map. Also, look at 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.
Mostafa's merge algorithm: A neat, interesting attempt to provide a fast in-place merge, in Java: java code.
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 minimum-cost 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.
If a reference like null.b or a method call like null.m(...) is attempted at runtime, a "null pointer exception" is happens.
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 one-page pdf file.
Static components are not overridden but are hidden. This is explained in this one-page 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.
See also polymorphism.
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 Hopcroft-Tarjan linear-time planar testing algorithm: pdf file.
In Java and other programming languages, polymorphism deals with types. Together, the three kinds of polymorphism listed below help achieve easy reuse of program parts and scalability to large programming systems:
* Ad hoc polymorphism: read this pdf file.
* Parametric polymorphism: read this pdf file
* Subtype polymorphism: read this 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 spanning-tree 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: <class-name> . <function-name> ( <arguments> ) ;
2. for a non-static procedure: <expression> . <function-name> ( <arguments> ) ;
where the <expression> evaluates to the name of an object that contains the procedure to be called. Both "<class-name>." 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. Constant-space quicksort: end of this pdf file. Article: pdf file.
6. Watch Hungarian dancers perform a quicksort: quicksort dance.
Java uses the double quote solely for strings, e.g. "this is a string".
Within a string, you can use \" for a double quote, e.g. string "\"this\"a" prints as "this"a.
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.
A different explanation of how to understand a recursive call: 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. Video that develops a recursive method to reverse a singly linked list in place: webpage.
8. Videos that develop recursive methods for traversing trees: webpage.
9. Development of a function to decide whether a binary tree is a binary search tree (BST): pdf file.
10. 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.
12. Calculating b^n for integer n ≥ 0 in O(log n) time and space recursively: pdf file. Java code
13. Backtracking: An explanation and an example of it, in two videos: webpage.
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.
return;
assert x > 0;
x= x+1;
Look up the syntax of a statement, either in JavaHyperText or the Java language spec, and it will show you whether a semicolon is needed at the end. Watch out for the following two common mistakes:
1. The statement Math.max(3, 4); calls function max and then throws away the value it returns. Execution of this statement does nothing, but it takes time to do that nothing. Never have a statement that consists of a function call followed by a semicolon.
2. A semicolon by itself is a statement, the "empty statement", which does nothing. Sometimes, a ; is inadvertently put at the end of a loop: while (b < c) ; This means that the repetend is the empty statement, and this can often be a hard-to-find infinite loop.
Be extremely careful with this convention. Do not wantonly provide a setter method for each field of a class. Further, if method setTime(value) is needed, do not mention the field at all in its specification. The user of this class should in general not know what its fields are. Here's an example, Java class JFrame has a method setTitle(t), but its spec says nothing about a field and how that is done, it just says to change the title of this JFrame to t. Here's an alternative to the conventional getter/setter terminology: pdf file.
1. How to use "this." to reference a shadowed field: pdf file.
1. Five videos that (1) give history, (2) state the problem, (3) simulate the algorithm to give insight into the invariant, (4) show the invariant of the algorithm, and (5) develop the algorithm from the invariant: webpage.
2. Extend the algorithm to calculate and save not only the shortest-path 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.
E.g. "snippets of testimony played during the trial ..."
Wikipedia says that in programming practice, "snippet" refers narrowly to a portion of source code that is literally included by an editor program into a file; it is a form of copy-and-paste programming.
Some people say that a snippet in email is the first sentence of the email, which gets displayed after the subject line.
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. constant-space quicksort: end of this pdf file. Article: pdf file.
2D. merge sort: Merging two adjacent sorted segments. Merge sort.
Mostafa's merge algorithm: A neat, interesting attempt to provide a fast in-place merge, in Java: java code.
2E. heap sort: pdf file. JavaHeapSort.zip
3. Non-comparison 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. Minimum-cost spanning tree, Kruskal, Prim, and the JPD algorithm: pdf file.
3. Implementing the JPD algorithm: pdf file.
4. Using the JPD spanning-tree 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.
while (b) {}. It is in a thread, and it is waiting
for another thread to change b so that it can continue with its task. This
is spinning, or busy waiting. Don't write such code, because it is eating up
execution time doing nothing whenever it gets a slice of time. There are
situations where spinning is useful, but only those should use it who know precisely
what they are doing and why.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.
See also polymorphism.
(1) super.m(...) calls method m within the object in which it appears. To determine which version of m is called, use the bottom-up (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..
20-sec 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 white-box testing gives complete code coverage: pdf file.
if (b) S1 or an if-else statement
if (b) S1 else S2 , statement S1 is called the then-part.(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.
c= c + 1; is typically not
thread safe because another thread could execute c= c + 2; at the
same time and their interleaved execution could result in a race
condition --possible outcomes are that 1, 2, or 3 are added to c.
In Java, usually, the synchronized feature is used to make
code thread-safe, although there are other mechanisms to achieve thread safety.
Watch a 3.2-minute video on throwable objects here.
0. Suppose the throw-statement is not within a try-block, 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 try-block.
1. 3.2-minute video on throwable objects: webpage.
2. 5-minute video on interpreting the output of an uncaught thrown object: webpage.
3. Videos on the throw-statement 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. Image of a real binary tree
Recursion on binary trees: page 2 of this pdf file.
OO-oriented implementation of 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 height-balanced tree with n nodes is O(log n): pdf file.
5. Binary search trees (BSTs): pdf file.
5A. Takeoffs on BSTs (AVL tree, 2-3 tree, B-tree, red-black tree): pdf file.
6. Representing arithmetic expressions as trees: pdf file. Java implementation: treeExpressions.zip.
7. Heaps, both min-heaps and max-heaps
7A. Definition of a max-heap and min-heap: pdf file.
7B. Java class ArrayHeap, maintaining a bag of ints as a min-heap: 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 (<class-name1 e1>) <catch-statement1>
...
catch <class-namen en>) <catch-statementn>
where each of the <class-names> is a throwable class. There can also be a "finally clause", which we don't discuss. The try-statement 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 (class-name) or (interface-name)
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.75-minute video (webpage).
6. Compile-time 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.
call wait();. They stay on the waitlist until execution of a call
notify(); or notifyAll(); places them back on the locklist.
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.