Java程序辅导

C C++ Java Python Processing编程在线培训 程序编写 软件开发 视频讲解

客服在线QQ：2653320439 微信：ittutor Email：itutor@qq.com
wx: cjtutor
QQ: 2653320439
JavaHyperText Skip to main content JavaHyperText and Data Structures David Gries, with help from many Home Java HyperText Style Guide Eclipse 0. Create project 1. Show line numbers 2. Import preferences for automatic formatting 3. Reset layout 4. Syntax help 5. Open 2 files 6. ToDO comments 7. JUnit testing 8. Assert statement 9. Generating javadoc 10. Red square: terminating programs 11. Remove/add imports 12. Use UTF-8 character encoding API and strings 1. API documentation 3. Using Strings Explain constructs Introduction 1. Assignment statement 2. New-expression 3. Method calls 2. Try-statement Exceptions 1. Output of thrown exceptions 2. Throwable objects 3. Try-stmt/propagation 4. Throw-statement 5. Throws-clause 6. Hints Abstract classes interfaces Iterator & Iterable Program correctness Loop invariants 1. Introduction 2. Developing loops 3. Finding an invariant Stepwise refinement Recursion Intro to recursion Recursion on linked lists Recursion on trees Backtracking Hashing DFS BFS Shortest path 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: Java Data structures Other anonymous function casts classes constructors generics interfaces I/O JUnit testing types variables graphs hashing linked list sorting trees complexity concurrency polymorphism recursion study habits testing % remainder operation \ escape character +=  -=  *=  /=  %=  (compound assignment operators) See this one-page pdf file. ++   -- (increment and decrement operators)e See this one-page pdf file. <> See diamond <>. = versus == See this pdf file. @Override An annotation that is placed on a method that is supposed to override a method in a superclass or interface. It's a good idea to use it, for it tells you there is an error if the method doesn't actually override another method, perhaps because of a typo. But you are not required to put it on a method that overrides another. 2-3 tree See pdf file. absolute path, a in file system See I/O (first entry). abstract class A class that is declared with modifier abstract. The main feature is that the class cannot be instantiated ---if class C is abstract, the expression new C(...) is syntactically illegal. The first video on this page is a 3.5-minute tutorial that explains abstract classes and methods. abstract data type (ADT) A type whose methods are declared in an abstract way, without regard to implementation. See this pdf file. abstract method A method declared with modifier abstract in an abstract class. Its body is replaced by a ";". Its main feature is that any non-abstract subclass must overridde. The first video on this page is a 3.5-minute tutorial that explains abstract classes and methods. access modifier Java has four levels of access to components. In order of accessibility, they are: public, protected, package (no modifier), and private. The table below shows the access to components of a class depending on the access modifier on that component. For example, a component that is protected can be referenced from within the class, from other classes in the same package, and from a subclass. 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 acyclic A graph is acyclic if it does not contain a cycle. See this pdf file. ad-hoc polymorphism ad hoc Read this pdf file. See also polymorphism. adjacency list, adjacency matrix These are two ways to represent a graph. See this pdf file. adjacent Two nodes of a graph are said to be adjacent if there is an edge connecting them. See this pdf file. actual parameter A term used for argument (of a method call). The term should never be used because it is confusing, especially because the adjective "actual" tends to be omitted and then it is just parameter, which is even more confusing. algorithmic complexity 1. Introduction: pdf file. 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) annotation Something like @Override. See this one-page pdf file. Annotations in a JUnit 4 testing class: See this pdf file. amortize Merriam-Webster's online dictionary tells you that amortize means to write down gradually to extinguishment the cost of (as asset) by periodic charges to expense or profit and loss. That is too abstract for us. This pdf file explains amortization, using class ArrayList as an example. This pdf file uses amortization in estimating the time complexity of a hashing algorithm. anonymous class This two-page pdf file explains what an anonymous class is and how to instantiate it. anonymous function - lambda Anonymous functions were introduced in Java version 8. An anonymous function is a function declared without a name —it has just parameters, a return type, and a body. These first items are for those who don't know about interfaces:    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. API Application Programmer Interface. A set of tools (in Java, packages of classes and interfaces) for building "application software". You are building application software when you write a Java program. 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. apparent class We don't use this terminology. When you see it, ignore it. It is not needed. applet An applet is a Java program that contains a subclass of java.awt.Applet or javax.swing.JApplet. It can appear on web pages. application A Java application is a program that has a class that contains a static procedure defined like this:     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. application programmer interface See API argument An expression that occurs within the parentheses of a method call. The following call has two arguments: x+y and y+w:     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. argument, type argument See type argument argument, variable number of, in a call See this pdf file to see how to allow a variable number of arguments in a call array Explanation of how arrays are used and implemented in Java: pdf-file. 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 array, creating a generic array See this: pdf-file array initializer The expression   new int[]{3, 5, 4}   creates an int array of size 3, with elements 3, 5, and 4. The notation  {3, 5, 4}   is called an array initializer. For more info, see this pdf-file. assert statement The assert statement has the form     assert ; To execute it, evaluate the ; 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 assertFalse assertTrue Method 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 Method assertThrows(exception.class, anonymous-function) is used to tell whether a call of the anonymous function throws the exception. See webpage. assertion A true-false statement about the variables in a program that is placed as a comment at a particular place in the program to indicate that the true-false statement is true at that place. See also precondition and postcondition. assignment statement The assignment statement has the form    =     ; 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 and store its value in the . 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 +=  -=  *=  /=  %=. atomic action A section of a program that must be executed as an indivisible sequence of operations; no other process, or thread, can interrupt or interfere with its execution. autoboxing, auto-unboxing, autowrapping In certain situations, like the declaration-assignment  Integer d= 5;  the integer 5 will automatically be wrapped in a new object of type Integer. This is called autoboxing, although autowrapping would have been more appropriate. Similarly, in the declaration-statement  int k= d;  the integer in d will be auto-unboxed so that it can be stored in k. Autoboxing and auto-unboxing can take place between each primitive type and its wrapper class. Read the pdf file at entry wrapper class. B-tree See pdf file. back door Refers to referencing a synchronized object without synchronizing. Can lead to efficiencies, but should be used with care and only by someone knowledgeable with concurrency. pdf file. Demo code: BackDoor.zip backpointer Consider a path (p, p1, p2, ...) in a graph. A backpointer for a node in the path is the previous node. Thus, p1's backpointer is p and p2's backpointer is p1. Backpointers are used in Dijkstra's shortest path algorithm. backtracking Backtracking is a technique for recursively solving a problem by choosing one possible solution but then removing that choice (this is the backtracking) and trying another if it doesn't work. This webpage contains two videos that give a good example of backtracking. bag, set, unibag A bag is a bunch of elements with duplicates allowed. The bag {25, 5, 25, 10} has size 4 because it contains 5, 10, and 25 twice. Think of it as a representation of a bag containing 2 quarters, a dime, and a nickel. 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. balanced tree A tree of size n is balanced if its height is O(log n). Different properties of a tree can ensure that it is balanced. pdf file. Proof that the height of a height-balanced binary tree with n nodes is O(lg n). pdf file. base 2, 8, 10, and 16 The natural numbers 0, 1, 2, ... can be represented in different bases or radixes. See this pdf file. base case In a recursive method, a base case is case (i.e. values for the method's parameters) in which a recursive call is not needed. See this pdf file. basic step An expression or statement whose evaluation or execution takes roughly the same amount of time no matter what the values being manipulated. Adding two int values is a basic step. Summing the values in an array is not —the time required depends on the size of the array. See this pdf file. binary number system The system for writing natural numbers 0, 1, 2, ... using bits 0 and 1. See this pdf file. binary operator An operator with two operands. Examples are addition and multiplication, 5 + 2 and 6 * 8. See also ternary operator and unary operator. binary search See this pdf file. You might find this banquet speech, which pokes fun while giving a message, interesting: Eliminating the chaff. binary search tree (BST) See this pdf file. binary tree A tree in which each node has at most two children. pdf file. Proof that a height-balanced binary tree with n nodes has height O(log n). pdf file. bipartite graph A graph is bipartite if its nodes can be partitioned into two sets such that no edge connects two nodes in the same set. See this pdf file. block A sequence of statements, local variable declarations, and local class declarations enclosed in braces { }. boolean A primitive type whose values are true and false. See this pdf file for an explanation. This pdf file also describes the marks of a boolean tyro, a novice, beginner. Boolean, class A wrapper class for type boolean. bottom-up rule This is also called the overriding rule. When looking for a method in an object that is appropriate for a method call, start from the bottom of the object and look upward. This rule ensures that an overriding method will be called (if present) rather than an inherited one. bounded buffer A place to store items that may be put in and taken out at different rates by different threads. See Concurrency. bounded wildcard See generics. bound function A function that is used in proving that a loop terminates or that a recursive function terminates. For loops: still to come. For recursive functions: pdf file. break statement See this pdf file. The break statement is used most often to terminate execution of a switch statement. breadth first search (bfs) An algorithm to traverse all nodes of a graph. See the tutorial on DFS BFS. bucket In hashing, an element of the hash table is sometimes called a bucket. See this webpage for a tutorial on hashing. byte A primitive type whose values are integers in the range –2^7 .. 2^7 – 1, or -128..127. See this pdf file for an explanation. Byte, class A wrapper class for type byte. bytecode Java bytecode is the virtual machine language into which Java programs are compiled. See this pdf file. cache A memory cache for a CPU (Central Processing Unit) is a small hardware component that contains copies of some main memory locations so that future requests for them can be served faster than retrieving them from main memory. The terms spacial locality and data locality refer to the use of data elements within relatively close storage locations. An algorithm with high spacial locality will have higher cache performance than one with low spacial locality. 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. calculate elapsed time To calculate the time that any method or operation takes do two things: 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. call stack At runtime (during execution of a Java program), the call stack contains a list of frames for method calls that have been started but have not yet completed. The list is actually a stack because it follows the LIFO principle. This webpage discusses the call stack. casts A cast converts a value from one type to another. Example: the cast (double)(5+6) converts the value of the expression 5+6 to double format. 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. catenate, catenation To link together, to place side by side. Suppose b and c are of type String. Then operation b + c denotes catenation. Its resulting value is a new String that contains the characters of b followed by the characters of c. 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". chaff, eliminating You might find this banquet speech on eliminating the chaff entertaining as well as educational: pdf file. chaining In hashing, there are essentially two ways to maintain the elements of the set being implemented using hashing. In chaining, each bucket of the hash table is a linked list containing the values that hashed to that bucket. In open addressing, each bucket is either null or an element of the set begin maintained. See this webpage for a tutorial on hashing. char A primitive type whose values are single characters, like 'h'. This pdf file explains type char and the unicode representation of characters. This pdf file explains more about code points and what to watch out for when characters not in type char are used in Strings. Character, class A wrapper class for type char. Christmas Halloween Why did I receive a Christmas card on Hallowen? pdf file checked exception Java "checks" all throwable objects except those of class Error and RuntimException. A checked exception has to be handled in one of two ways: (1) catch it in a catch-block or (2) put a throws-clause   throws   on the method header in which the exception is thrown. The video on this webpage explains it. circular linked list See this pdf file. class definition, class declaration A class definition (or declaration) defines the format of objects (or instances or folders) of the class —it defines the methods and fields that go in each object of the class. It is a blueprint for objects of the class. This pdf file explains describes the basic class definition and explains how we draw objects. 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. classes, subclasses, and objects 1. Class definition or declaration: a blueprint for objects, describing what is in them.     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 . 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 class, apparent We don't use this terminology. If you see it being used, ignore it. class as a type A class name can be used as a type. Its values are the names of (pointers to) objects of that class (and also null). For example, the declaration JFrame j indicates that variable j can contain values that are the names of (pointers to) objects of class JFrame. class container See container, for a class. class, generic See generics. class invariant The collection of meanings and constraints on the fields of a class that describe the valid states of all instances of the class before and after each method is called. The class invariant should appear as Javadoc comments on the declarations of the fields. 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. class method See static method. class, nested See nested class. class, real See real class. class, static See nested class. class type A type that is the name of a class or interface. Its values are the names of (pointers to) objects of that class, and null. Also called reference type because a value of the type is a pointer or reference to an object. class variable Same as a static variable. clone, cloning To clone means to make an exact duplicate of. This pdf file introduces the topic. Later pdf files will explain how to clone in Java. code coverage Eclipse JUnit testing to show code coverage: pdf file. code point An integer that represents a character in the Unicode system. For characters in Java type char, it is the integer that is returned when a character is cast to int. This pdf file explains type char and the unicode representation of characters. This pdf file explains more about code points and what to watch out for when characters not in type char are used in Strings. coercion A type conversion is the conversion of a value from one type to another, e.g. from type int to type double. 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; collision In hashing with open addressing, if an element e to be put into the set hashes to a bucket h and an element is already in bucket h, a collision is said to have occurred. The collision is solved using some form of probing, usually linear or quadratic probing. See this webpage for a tutorial on hashing. coloring A coloring of an undirected graph is an assignment of a color to each node such that no two adjacent nodes get 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. comment, javadoc comment Java has 3 kinds of comment, shown below. // 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  
  to end a line. Comparable, compareTo Interface java.lang.Comparable, or java.lang.Comparable, has one abstract method: CompareTo(ob). It is supposed to return a negative int, 0, or a positive int depending on whether this object "comes before", equals, or "comes after" its parameter ob. See this pdf file. comparison sort A comparison-sorting algorithm is a sorting algorithm that uses only comparisons (like b < c) to sort. 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. compiler A (Java) compiler is a program that checks the syntax of a program, and, if the program is syntactically correct, translates it into (the Java virtual) machine language, so that it can be run, or executed. This is called compiling the program, and it happens at compiletime. The Eclipse IDE calls the compiler often as you are editing a program, and it happens so fast that you don't notice it. For more information, read this this two-page pdf file. compile-time, compiletime The time at which the compiler checks the syntax of a program and, if there are no errors, translates the program into an equivalent machine language program, ready to be executed (or run). compile-time casting rule This rule determines whether a cast (class-name) object is syntactically correct and can be compiled. See this pdf file. compile-time reference rule This rule determines whether a component reference like p.v or p.m(...) is syntactically correct. See this pdf file. complete, full, perfect binary tree A complete binary tree has no holes: Every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. 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. complete graph A complete graph has as many edges as possible. 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. component A component of a class is a variable, method, or inner class that is declared in the class or is inherited from the superclass. compound assignment operator See pdf file. concatenate, concatenation Same as catenate. concurrency Concurrency refers to having more than one thread of execution in a program, allowing different parts of a program to execute in parallel. 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. conditional expression. Uses ? and : An expression of the form ? : . It is a ternary operator: it has three operands. To evaluate it, evaluate the ; if it is true, use the value of as the value of the conditional expression; otherwise, use the value of as the value of the conditional expression. Here are examples: 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 connected Two nodes of a graph G are connected if there is a path in G whose endpoints are the two nodes. Graph G is connected if each pair of nodes in it is connected; otherwise, G is disconnected. A graph of 1 node and no edges is connected. A graph with two nodes and no edges is disconnected. See this pdf file. conjunction The proper word for and, the boolean operator &&. See this pdf file. connected component A connected component of graph is a subgraph that is connected and that has no node or edge in common with the rest of the graph. A graph, then, consists of the collection of its connected components. 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. constant In Java, a variable whose value cannot be changed is called a constant. To declare such a variable, use keyword final, as in this example: public static final double PI= 3.1415926535897932384626433832795; constant expression An expression of a primitive type or type String that can be evaluated at compile-time and replaced by its value. If two or more such String expressions have the same value, only one String object is created for all of them. See this pdf file. constant time An operation or method takes constant time if the time it takes to carry it out does not depend on the size of its operands. For a more detailed explanation, with examples, see this pdf file. constructors A method that is declared with the basic form:      ( ) { ... } The purpose of a constructor is to initialize the fields of a new object of class 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. constructor call A call of a constructor. The purpose of a constructor call is to initialize fields of a newly created object so that the class invariant is true. There are three ways to call a constructor —the last two ways may appear only as the first statement of a constructor body: 1. In a new-expression. It has the form ( ) 2. As a call of another constructor in the same class: this();. 3. As a call of a constructor of the superclass: super();. constructor call, default If (and only if) the first statement of the body of a constructor is not a constructor call, this one is inserted: super(); constructor, default If (and only if) a class definition does not contain a constructor, this one is inserted:     public () {} container, for a class Conceptually, we think of all the objects of a class together with its static components being housed in a container, a box. This conceptual view, along with the inside-out rule, helps explain the concept of "static" and how the declaration corresponding to a variable reference is found. This view may give the feeling that all objects and static components reside in contiguous places in memory, but that is not the case. Just think of the container as a conceptual aid, not an implementation device. See this pdf file for an example. continue statement Execution of the statement "continue;" terminates execution of the loop body in which it occurs. See pdf file. core A component on a chip that contains a "processing unit", which can execute sequences of instructions. See pdf file. counting sort A linear-time sorting algorithm that is not a comparison sort. It works by counting (and then using) the number of times each value occurs in the array being sorted. See pdf file. creators, observers, mutators An alternative to the conventional getter/setter terminology: pdf file. CPU Central Processing Unit. See pdf file. critical section Part of a program that accesses resources shared by two or more threads. To avoid a race condition, have it executed as an atomic action —with no other processing accessing or changing the resources while the critical section is being executed. In Java, this is usually done using a synchronized statement or method. See this pdf file. cuckoo hashing A form of hashing with open addressing in which methods contains and remove take constant time in the worst case. Its name is inspired by the actions of the European cuckoo bird. pdf file. cycle A path in a graph is a cycle if it contains at least one edge and its first and last nodes are the same. The cycle is simple if the first node appears exactly twice. See this pdf file. DAG A directed acyclic graph is called a DAG. Summary: pdf file. More detail: pdf file. 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. daemon thread See pdf file. data structure An organization or format for storing and managing data, usually to make some operations efficient. 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. data type Another word for type. See this pdf file. deadlock Deadlock occurs when a group of processes (or threads) can't make progress because they need a resource that another process in the group has locked. See pdf file. debugging The process of looking for and fixing an error once it has been determined that there is an error. decimal number system The system for writing natural numbers 0, 1, 2, ... using digits 0, 1, ..., 9. See this pdf file. default package The package that is used for a class file that is not placed in an explicitly named package. See this pdf file for an explanation. default values Fields (both static and non-static) have default values (if they are not initialized), as follows: numeric-type fields: 0; boolean fields: false; char fields: '\u0000'; and class-type fields: null. Local variables do not have initial default values and must be assigned before referenced. degree The degree of a node u in an undirected graph is the number of edges for which u is an endpoint. See this pdf file. 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. dense A graph is dense if the number of edges is close to the maximum. A graph is sparse if the number of edges is close to the minimum. 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. deprecate To deprecate means to lessen in value. Some classes and methods within classes in the Java API package have been deprecated because they have been superceded by newer ones that do a better job. You can still use the deprecated entities, but it is better if you don't. depth first search (dfs) An algorithm to traverse all nodes of a graph. See the tutorial on DFS BFS. depth first search walk (dfs walk) An extension of dfs to simulate walking around a graph. See the tutorial on DFS BFS. depth, level, width, and height in a tree The depth of a node is the length of the path from the root to the node. Thus, the root is at depth 0 and its children are at depth 1. 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. deque A deque (double-ended queue, pronounced "deck") is a list that supports insertion and deletion at both ends. See this pdf file. descriptor, of a method The method signature plus the return type. diamond <> An abbreviation in a new-expression like new ArrayList<>(). See this pdf file. digraph A directed graph is sometimes called a digraph. diamond problem A problem that occurs when there is multiple inheritance: a method is inherited from two or more classes or interfaces, and a decision must be made on which inherited method is used. See this pdf file. dropbox A bounded buffer of size 1, used to illustrate synchronization among threads. See Concurrency. Code that uses a dropbox to illustrate use of notify() and notifyAll(). boundedBufferDemo.zip. Edsger W. Dijkstra 1. The Jarník/Prim/Dijkstra algorithm for constructing a minimum spanning tree: 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 spanning-tree algorithm to construct a maze: pdf file. Java: mazeGeneration.zip         6. Dining philospher's problem: pdf file. dining philosophers A problem invented by Edsger W. Dijkstra to illustrate deadlock. See this pdf file. directed graph A graph whose edges are directed from one node to another. See this pdf file. disconnected unconnected A graph is connected if there is a path between any pair of nodes. Otherwise, it is disconnected. One sometimes sees the word unconnected used for disconnected, but the proper word is disconnected. See this pdf file. disjunction The proper word for or, the boolean operator ||. See this pdf file. do-loop (do-statement) See this pdf file for an explanation of the do-loop. double A primitive type whose values are written in scientific notation, e.g. 3.46E–4. Each value occupies 64 bits. See this pdf file for an explanation. Double, class A wrapper class for type double. doubly linked list See this pdf file. downcast, upcast; narrowing, downward, widening, upward cast A widening cast is a cast of an expression to a wider type, e.g. int to double. Widening casts will be done automatically when necessary. 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. Suppose an object is looked at from the perspective of some class or interface C. 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 A simple IDE for Java. WE NO LONGER USE IT BECAUSE IT HAS NOT BEEN UPDATED TO USE JAVA 11. Instead, we use the command-line application JShell. 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. Dutch National Flag An algorithm to sort an array that has at most three different values: pdf file. -ea -da ea stands for enable the assert statement; da for disable the assert statement. It is a VM (Virtual Machine) argument that can be used to turn on execution of the assert statement. To disable the assert statement, remove   -ea   or replace it with   -da   --the default is   -da  . Read about it here. Eclipse: an Integrated Development Environment (IDE) We use the IDE Eclipse for developing, testing, and running Java programs. 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. elegance As one definition of elegance, the online Unabridged Merriam-Webster Dictionary give this: scientific precision, neatness, and simplicity. We strive for elegance when developing programs, for only with elegance can we hope to achieve programs that are understandable and correct. Tony Hoare said: "Inside every large program is a small program struggling to get out." Edsger Dijkstra said: "Beauty is our business."" else-part, then-part In an if-else statement  if (b) S1 else S2 , statement S1 is called the then-part and S2 is called the else-part. endpoint For an edge {u, v} of an undirected graph, u and v are the endpoints of the edge. See this pdf file. enhanced for statement Java's formal terminology for a foreach loop. See foreach loop. enum, or enumeration type An enum class provides constants (static final variables), like Coin.PENNY and Coin.NICKEL. The basics: pdf file. Adding fields and methods to an enum class: pdf file. enumeration, enumerate An enumeration of a collection of values (set, bag, list, etc) is simply a list of them. To enumerate the values is to produce them one by one. 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 equals The call b.equals(c) on function equals in class Object returns true iff b == c is true, i.e. b and c evaluate to null or to the same pointer ---they point to the same object. Equals should sometimes be overridden in a class to define what equality means for that class. This pdf file tells you how to do it, and here are some .java files to demo with: equalsDemo.zip Error, class A subclass of class Throwable; its objects and those of its subclasses should not be caught and processed, as opposed to those of class Exception, which may be caught and processed. See the 3.2-minute video on throwable objects here. escape character The escape character \ is used to write characters that cannot appear directly in a String. Here are examples; there are others: \n —new-line character \\ —backslash character \" —double quote character \' —single quote character (you can use ' in a String, but as a character, write '\'' Exception, checked See checked exception. Exception, class A subclass of class Throwable; its objects and those of its subclasses may be caught and processed, as opposed to those of class Error, which shouldn't be caught. See the 3.2-minute video on throwable objects here. exception handling When something like a division by 0 happens, or any exception is "thrown", the flow of control of a program is altered. This important topic of exception handling is covered in tutorials here. exponentiation Calculating b^n for integer n ≥ 0 in O(log n) time recursively and iteratively: pdf file.  Java code exclusive OR, XOR The exclusive OR of two bits b and c yields 1 if the bits are different and 0 if they are the same: 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. expression In Java, each expression has a type, which depends on the type of its operations and operands. Evaluation of the expression yields a value of that type. For information on increment/decrement expressions ++ and --, see this pdf file. Look here for constant expressions. extends clause A clause, extends C, put on a class definition to indicate that the defined class is a subclass of class C and that C is a superclass of the defined class. The subclass inherits all components defined in and inherited by the superclass. factory A factory builds things. In OO parlance a factory method returns an object of a class, building a new one if necessary (using a new-expression). This pdf file pdf file explains. Fibonacci numbers The sequence 0, 1, 2, 3, 5, 8, 13, ... in which each one (except the first two) is the sum of the previous two. 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). field A variable belonging to a class (static field) or instance (non-static field). final A variable declared with keyword final cannot be assigned after its initial assignment. For example, the following declaration of PI in class Math includes keyword final so that PI cannot be changed: public static final double PI= 3.141592653589793; A class that is declared with keyword final cannot be extended ---cannot have a subclass. float A primitive type whose values are written in scientific notation, e.g. 3.46E–4. Each value occupies 32 bits. See this pdf file for an explanation. Float, class A wrapper class for type float. folder Same as object or instance. foreach loop See this pdf file for an explanation of the foreach loop. 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. Follower minus First Formula for calculating how many values are in a range like m..n. The first element of the range is m. The last one is n and its follower is n+1. So the number of integers in the range m..n is the Follower (n+1) minus the First (m), for n+1-m. See the first video on ranges on this page. forest A set of zero or more trees. An undirected graph is a forest if each of its connected components is a tree. See this pdf file on spanning trees. for-loop See this pdf file for an explanation of the for-loop. formal parameter We use the term parameter (of a method) instead of formal parameter and argument (of a method call) instead of actual parameter. The terms formal parameter and actual parameter should never be used because they are confusing, especially because the adjectives tend to be forgotten and then there is no difference in the terms. four color theorem The four-color theorem: this pdf file. Sipka's paper on Kempe's flawed proof: this pdf file. Gonthier's paper on the Coq proof: this pdf file. frame for a call When a method is called, a frame is created for the call. This frame contains    (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. function A method that is declared with the basic form:      ( ) { ... } Execution of the body of the function must terminate by executing a return statement, giving an expression whose value is to be returned. A call on a function is an expression (and thus yields a value). function call A function call is an expression, so it can be placed wherever an expression (of the appropriate type) can be placed. Its form is one of: 1. for a static function: . ( ) 2. for a non-static function: . ( ) where the evaluates to the name of an object that contains the function to be called. Both "." and "." can be omitted if the call appears in a place in which the function can be called without them. functional interface An interface that has exactly one abstract method. Default methods have an implementation and are not abstract. If an interface declares an abstract method overriding one of the public methods of class Object, that method also doesn't count toward the interface's abstract method count since any implementation of the interface will have an implementation from Object or elsewhere. Use the annotation @FunctionalInterface on a functional interface you write to ensure that it indeed one. See this pdf file. generalize Math and computer science often involve the process of generalizing statements. By generalizing a statement, we mean including new situations, or states. For example, one can generalize the statement "2^4 is even" to "2^k is even, for all positive integers k". A video on generalization appears here on this JavaHyperText webpage. generic class See generics. generic method See pdf file. generics 1. History of generics in Java and what generics means: pdf file. 2. Introduction to generic classes: pdf file. 3. Introduction to generic methods: pdf file. 4. Creating a generic array: pdf file. 5. Why ArrayList is not a subclass of ArrayList: 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. getClass ob.getClass() == C.class is true iff ob was created using a new-expression new C(...). 1. Full explanation: pdf file. 2. An example where instanceof and not getClass() should be used: pdf file. getter method A non-static function whose purpose is to retrieve a value from the object in which the method appears. If object 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 file golden ratio The irrational number (1 + sqrt(5))/2 = 1.6180339887... It is a root of the polynomial x^2 - x -1. It is intimately connected with the Fibonacci numbers. See this pdf file and this pdf file(still to come). goto A keyword in Java that is unused. In the early days of computing, high-level programming languages like Fortran, PL/I, and C had a statement like goto 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. grammar One definition of grammar is the system of rules that defines the grammatical structure of a language. That doesn't help much, because grammatical is defined as: of or relating to grammar. Kind of a recursive, non-ending definition. We can instead say that a grammar defines the syntax of a language but not its semantics (meaning). Here's an example of a grammatical definition: in English, a noun phrase can be a list of adjectives followed by a noun. And, in Java, the simple assignment statement has the form " =   ;". graphs 1. Definition of graph and examples of graphs: 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 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. greedy algorithm An algorithm that follows the heuristic of making a locally optimum choice at each stage with the hope of reaching a global optimum. It doesn't always work. See this pdf file for the definition and examples. See this pdf file for the greedy graph coloring algorithm. David Gries The main author of JavaHyperText and the video/tutorials. 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. grok To grok something means 'to understand intuitively or by empathy, to establish rapport with' and 'to empathize or communicate sympathetically with' (see the Wikipedia entry for 'grok'). The term was first used by Robert Heinlein in his science fiction novel Stranger in a Strange Land (1961). If you grok something, you really get it and feel at ease with it. Grundy numbering The maximum number of colors needed to color the nodes of a graph using the greedy coloring algorithm. (The number of colors needed may depend on the order in which the nodes of the graph are colored.) pdf file hashCode and equals Function hashCode in class Object, the superest class of them all, returns the address in memory of the object. 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. hashing, hash table, hash function A hash table is a data structure for maintaining sets or maps that typically offers expected time O(1) for adding and removing elements and for testing whether a value is in the set or map. That's neat! 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. header, of a method The part of a declaration of a method that gives the access modifiers, prefixes like static, the return type or void, the method name, and the parameter declarations delimited by parentheses. Thus, it is the complete method declaration except for the method body. Heaps 1. Definition of a max-heap and min-heap: pdf file. 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 HeapSort An insitu O(n log n) sorting algorithm: pdf file. JavaHeapSort.zip Herman Hollerith Herman Hollerith was the first to develop mechanical-electrical punched card tabulators and sorters in order to improve the process of tabulating census data in the U.S. His firm later becamse part of IBM. See this pdf file. hexadecimal number system The system for writing natural numbers 0, 1, 2, ... using 16 digits 0, 1, ..., 9, A, B, ..., F. See this pdf file. hiding fields and static components Fields are not overridden but are hidden. This is explained in this pdf file. Static components are not overridden but are hidden. This is explained in this pdf file. hypertext Text with links in it to other parts of the text, graphics, tables, images, etc. See this pdf file. Hoare triple Something of the form {Q} S {R} where Q and R are assertions and S is a statement It has the meaning: Execution of S in a state in which Q is true is guaranteed to terminate, and when it does, R is true. IDE --- Integrated Development Environment A software application that includes many facilities for writing, developing, testing, and running programs. For Java, we have been using Eclipse and the very simple IDE, DrJava. Identity The identity of a binary operator o is the value such that x = o + x for all x. See this pdf file. iff iff stands for if and only if. When we write b iff c, we mean (1) if b is true then c is true AND (2) if c is true then b is true. if-statement, if-else statement See this pdf file. immutable Unchangeable. Objects of class String and the wrapper classes are immutable; the values that they wrap cannot be changed. implements clause The implements clause, implements , on a class indicates that the class overrides all abstract methods declared in the interface. As of the latest Java version, the class need not override methods that have defaults. import statement The import statement has one of the forms:     import .; // import a particular class     import .*;         // import all classes in the package where the 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. indegree The indegree of a node u in a directed graph is the number of edges for which u is the sink. See this pdf file. infix operator An operator that is written between its two operands. E.g. +, as in 5 + 6. See also prefix operator and postfix operator. inheritance A subclass inherits all the instance fields and methods available in its superclass. This means that each instance of the subclass contains not only the instance fields and methods defined in it but also the instance fields and methods defined in and inherited by the superclass. 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. information hiding, encapsulation The principle of information hiding requires hiding the implementation of data. This pdf file discusses it. Encapsulation is Java's way of implementing information hiding. inlining a method call The process of replacing a call on a method by the body of the method, with suitable replacement of parameters by arguments. This pdf file explains how to use Eclipse's refactoring tool to inline a method call. inner class A non-static class that is declared within another class. (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. inner or internal node An inner node or internal node of a tree is a node that is not a leaf ---i.e. a node that has a child. IO Input-output I/O 1. Java files and data to demo most of what appears here: iodemo.zip 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. insertion sort A quadratic-time sorting algorithm. See this pdf file. inside-out rule A rule, used in most programming languages, that indicates how to determine what a reference to a variable or a method means (which declaration it refers to). Explanation: pdf file. Referencing a field that has been shadowed because of the inside-out rule: pdf file. instance An instance of a class is an object or manila folder of a class; instance, object, and manila folder are synonyms. in situ algorithm An algorithm is an in situ, or in-place algorithm if it processes its data using only a constant amount of extra space (except perhaps for recursive calls on the call stack). 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. instance method A method that is defined without modifier static in a class. A copy of the method resides in each instance of the class. instanceof Operation instanceof yields true iff the object has a partition named . 1. Full explanation: pdf file. 2. An example where instanceof is needed: pdf file. instance variable A variable that is defined without modifier static in a class. Also called a field. A copy of the variable resides in each object of the class. instantiate To create an instance of. So, evaluation of a new-expression new C(...) instantiates class C, producing a new instance, or object, of the class. int A primitive type whose values are integers in the range –2^31 .. 2^31 – 1, together with its operations +, -, *, *, and % (remainder). See this pdf file for an explanation. Integer, class A wrapper class for type int. integral type The Java primitive types whose values are integers: byte, short, int, long, and char. 1. Explanation of char: pdf file. 2. Explanation of byte, short, int, and long: pdf file. 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. 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. interpreter A compiler for a programming language translates a program into a machine language for execution on the computer. An interpreter is a computer program that executes the program directly, without compiling it first. The language Python is interpreted. Java is compiled into the Java bytecode (which is a virtual machine language), which is then executed by an interpreter. See this pdf file for more infomation. invocation, invoke If you want to be stuffy about it, you refer to a function call, like Math.min(b, c), as a function invocation. Evaluating the function call is then called invoking the function. Note how strange that is. You have an invoCation but then you turn the C into a K and write invoKing. That's as bad as having a picnic but then picnicKing. English is a weird language. is-a relation A class A should extend a class B only if an A "is a" B. See this one-page pdf file. iterate, iteration To iterate means to repeat. An iteration of a loop, be it a while-loop, for-loop, do-loop, or foreach loop, is one execution of its repetend. The first iteration is number 0, the second number 1, etc. 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. jagged array See ragged array. Vojtěch Jarník (Jarník) The Jarník/Prim/Dijkstra algorithm for constructing a minimum spanning tree: pdf file. Implementing the Jarník/Prim/Dijkstra algorithm: pdf file. Using the JPD spanning-tree algorithm to construct a maze: pdf file. javadoc An application that extracts appropriately written specifications from a Java project. 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  
 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. Java exercises We provide exercises to help you learn about methods, return statements, if- and if-else statements, local variables, the for-loop, and the while-loop, using either Eclipse or JShell. It's your choice. The zip files contains answers so you can check your work. e0Eclipse.zip   e0jshell.zip. Java language specification Here is the earliest Java language specification we could find: Java 7 spec. It is for Java 7, in 2013. It's an html version, there is also a pdf version. The authors are James Gosling, Bill Joy, Guy Steele, Gilad Brach, and Alex Buxley. Read the Preface to the First Edition to get a sense of history —how it was created and why. 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 Java Virtual Machine (JVM) The "fake" machine language into which Java is compiled, or the software that actually executes a Java program that has been translated into this machine language. See this pdf file. JDK Java Development Kit. The software package that contains a compiler as well as a Java Runtime Environment so that Java programs can be compiled an executed. See this pdf file. JFrame, class A class in package javax.swing. An instance of it is associated with a window on your monitor. See docs.oracle.com/javase/8/docs/api/javax/swing/JFrame.html. JPD algorithm The Jarník/Prim/Dijkstra algorithm for constructing a minimum spanning tree: pdf file. Implementing the Jarník/Prim/Dijkstra algorithm: pdf file. Using the JPD spanning-tree algorithm to construct a maze: pdf file. JRE Java Runtime Environment. The software package that contains an interpreter for Java bytecode and everything else that is needed to run (execute) programs that are in Java Virtual Machine (JVM) language form. See this pdf file. JShell JShell is a tool you can use from a command-line window (terminal window) to execute Java Snippets. To use it, open up a command-line window and type: jshell 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. JUnit testing JUnit is a framework for writing repeatable tests ---so you can repeat them whenever you want. See the website junit.org/. We use version JUnit5. 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. keyboard Reading the keyboard: pdf file. KeyBoardDemo.java. Kruskal algorithm Kruskal's algorithm for constructing a minimum spanning tree. See this pdf file. label, labeled statement See this pdf file. linear probing, quadratic probing, probe, double hashing In hashing using open addressing, a probe is a test of an element of the linked list in a bucket to see whether it is a particular element. 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. linear search Linear search in an array or array segment: pdf file. linked list See this pdf file. 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. list List is used in its general sense as a list of items, like (dime, penny, dime, quarter). The word is also used in data structures and programming languages with several related meanings. This pdf file explains the uses of the word list. literal A Java denotation of a value. Here are examples of literals: 354, 3.56F, true, 'c', and "peace". SLiterals of the number types (like int and float): pdf file. Literals of type char: pdf file. load factor In hashing, the load factor is the number of elements in the set implemented using a hash table divided by the size of the hash table. See this webpage for a tutorial on hashing. locklist The locklist of an object is the set of threads that are waiting to synchronize on the object because another thread has synchronized on it and has not released the lock. See pdf file. local variable A variable that is declared within the body of a method. For a one-page discussion of local variables, including their declaration, scope, when they are allocated space, and the fact that they are uninitialized, see this 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. logarithm The log operator is the inverse of exponentiation. It is needed in discussing space and time complexities of some algorithms. See this pdf file. long A primitive type whose values are integers in the range –2^63 .. 2^63 – 1. See this pdf file for an explanation. Long, class A wrapper class for type long. loops in Java 1. Java has four different kinds of loop. Here are one-page pdf files that explain each of them: 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 In a graph, a loop is an edge that begins and ends at the same node. All our discussions of graphs assume that loops are not allowed. loop invariant Invariant means non-changing. A mathematical expression is an invariant if its value doesn't change. Thus, a loop invariant is a boolean expression that is true before and after each iteration of the loop. 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. loopy questions The four loopy questions are used to prove that a loop is correct. For a brief intro, read this 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? lower-bounded type or wildcard See generics. magic numbers See pdf file. Mañana Principle ---manana The principle that says to introduce helper methods in certain situations and put off completing them later. Read about it here. Manhattan distance See this short pdf file. manila folder Same as object or instance. map In computer science, a map is simply a function: given a key, it returns a value. 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. Map, interface Read this pdf file to learn the basics about Java's interface java.util.Map. mark of a boolean tyro See this pdf file for the mark of a boolean tyro. Math, class Class Math, in package java.lang, contains a bunch of mathematical functions —e.g. sin(...), tan(...), ceil(...)— as well as the constants PI and E. maze Using the JPD spanning-tree algorithm to construct a maze: pdf file. Java: mazeGeneration.zip mean, median The (arithmetic) mean of a nonempty bag of numbers is their sum divided by the size of the bag. 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. method A set of instructions to be carried out. A method is analogous to a recipe in a cookbook. Java has three kinds of method: function, procedure, and constructor. merge sort Subroutine used to merge to adjacent sorted segments of an array: pdf file. Recursive merge sort: pdf file. Mostafa's merge algorithm: A neat, interesting attempt to provide a fast in-place merge, in Java: java code. method body A method consists of a method header followed by the method body, which has the form: { }. When the method is called, its body is executed. method call An expression or statement that ends up executing the method body. See function call, procedure call, and constructor call. It is important to understand how a method call is executed. Its execution is performed in the four steps shown below. For a more detailed explanation, see this tutorial. 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). method descriptor The method signature plus the return type. method, generic See generic method. method header See header, of a method. method name The name of the method, defined in the method header. method main A Java program becomes an application when a static procedure main is defined that has one parameter, of type String[]. The application can be started without having to have an IDE around. To start execution, this method main is called. method signature The method name together with the types of its parameters. For example, one method in class Math has signature min(int, int). For a generic method, the signature includes the type parameter, with names in the type parameter replaced by some canonical names. For example,      the signature of method m1(T p, E q) {...}    would be m1(T1, T2)      the signature of method m2(E1 x, E2) {...} would be m2(T1, T2) so they are the same except for the name of the method. method specification The specification of a method defines what the method does. It is used to understand how to write calls on the method. It must be clear, precise, and thorough, and it should mention all parameters, saying what they are used for. It is a contract between the programmer who wrote the method and users of the method. It may be given in terms of a precondition and postcondition. This link into our style guide gives details on specs for the different kinds of methods. methods allowing a variable number of arguments in a call See this pdf file to see how to allow a variable number of arguments in a call. minimum (or minimum-cost) spanning tree Suppose an undirected connected graph G has positive weights on its edges. 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. module In Java 9, a module system was introduced in order to be able to split the Java API packages into manageable pieces and to allow only those that are actually used to be included in an application. However, for most people using Java and Eclipse, this is not necessary, and one can continue as before using a default module. Here's a short explanation: pdf file. multiple inheritance Multiple inheritance occurs when a method is inherited from two or more classes or interfaces, with possibly difference implementations. There must be rules to determine which inherited method is used. This is also known as the diamond problem. See this pdf file. mutable An object is mutable if (some of) its fields can be changed. See immutable. mutual recursion Two (or more) methods are mutually recursive if they do something like this: Method A calls method B, B calls method C, and C calls A. narrower type Below, each line gives a series of types, beginning with the narrowest type and proceeding to the widest type:    byte --> short --> int --> long --> float --> double    char --> int --> long --> float --> double    subclass --> superclass      See cast to find complete information on casting. natural number The natural numbers are the nonnegative integers 0, 1, 2, 3, .... negation, complement The proper words for not, the boolean operator !. See this pdf file. nested class A class that is declared within another class. 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. new-expression The new expression has the form  new . Evaluation of the new-expression creates a new object and has as its value the name of (pointer to) the created object. See a full, detailed explanation of it in a 2-minute video on this webpage. nondeterministic algorithm An algorithm that may behave differently and give different results when run twice on the same input. See the second page of this pdf file. node and edge of a tree For the definition of a node and an edge of a tree, see this pdf file. non-static nested class See inner class. non-static method Same as instance method. non-static variable See instance variable. null A value that means "the absence of a pointer to an object". null may be stored in any variable of a class type (sometimes called a reference type) to indicate that the variable does not contain a pointer to an object. It may not be stored in a variable of a primitive type, e.g. int. If a reference like null.b or a method call like null.m(...) is attempted at runtime, a "null pointer exception" is happens. number type The Java primitive types byte, short, int, long, char, float, and double. Explanation of char: pdf file. Explanation of byte, short, int, long, float, and double: pdf file. object An instance of a class, also called a folder. Each object of a class contains the non-static fields and methods defined in and inherited by the class. See class. This pdf file explains how we draw objects. object-casting rule An object (i.e. a pointer to an object) can be cast to any class (or interface) for which it has a partition. See this pdf file for an explanation. Object, class The superest class of them all: any class that does not explicitly extend another class automatically extends class Object. This pdf file explains how we draw objects with a partition for superclass Object. object type Same as class type. octal number system The system for writing natural numbers 0, 1, 2, ... using digits 0, 1, ..., 7. See this pdf file. open addressing In hashing, there are essentially two ways to maintain the elements of the set being implemented using hashing. In open addressing, each bucket is either null or an element of the set begin maintained. In chaining, each bucket of the hash table is a linked list containing the values that hashed to that bucket. See this webpage for a tutorial on hashing. operator precedences See precedence of operators ordered, unordered tree A tree is ordered if the children of each node are ordered; otherwise the tree is unordered. 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. overload A method name is overloaded if there are two methods with the same name but different signatures. For example, class Math contains static functions with signatures min(int, int) and min(double, double). outdegree The outdegree of a node u in a directed graph is the number of edges for which u is the source. See this pdf file. override A method that is inherited from the superclass can be overridden by redeclaring it in the subclass. The inherited method and overriding method must have the same signature (method name, number of parameters, and their types) and return type. At runtime, the bottom-up rule (or overriding rule) ensures that the overriding method will be called, rather than the inherited one. 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. package A package consists of the classes that are contained in a specific directory on your hard drive (or the API packages, like javax.swing and java.lang). 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. package statement A statement that must be put at the head of each class that appears in a package. See this pdf file for an explanation. parameter A variable that is declared within the parentheses of the header of a method. parameter declaration A parameter declaration occurs within the parentheses of the header of a method. It has the form . parameter, type parameter See type parameter. parametric polymorphism Read this pdf file. See also polymorphism. parent, child, sibling, ancestor, and descendent (descendant) of a node in a tree For definitions of these terms, see this pdf file. partition, of an object A place within an object for the components declared in a particular class. See this pdf file for an explanation. partition algorithm The partition algorithm is used in quicksort. See this pdf file. path, in a graph A sequence (v0, v1, …, vp) of nodes such that for k, 0 ≤ k < p:      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. path, in a tree A sequence (v0, v1, …, vp) of nodes such that for k, 0 ≤ k < p: (vk, v(k+1)) is an edge. 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. path, in file system See I/O. pigeonhole sort A non-comparison sort, inspired by early electrical/mechanical sorting/tabulating machines: pdf file. planar graph A graph that can be drawn in the plane with no edges crossing: pdf file. Presentation by Gries and Xue of the Hopcroft-Tarjan linear-time planar testing algorithm: pdf file. polymorphism Polymorphism means "capable of assuming many forms". Here is a basic intro to it: 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 postcondition An assertion placed (as a comment) after a statement in a program to indicate what is to true at that place during execution. postfix operator An operator that is written after its operand. E.g .factorial is a postfix operator: 7 ! . Also, ++ and -- can be used as postfix operators (see this pdf file) See also infix operator and prefix operator. power Calculating b^n for integer n ≥ 0 in O(log n) time recursively and iteratively: pdf file.  Java code precedence of operators Standard mathematics gives precedence to multiplication * over addition +, so that the expression 2 + 3 * 5 is evaluated as if it were parenthesized like this: 2 + (3 * 5). Here is the Java precedence table: pdf file. precondition (1) A constraint on the parameters of a method. It is up to the user to ensure that method calls satisfy the precondition. If a call does not, the method can do whatever it wants. 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. prefix operator An operator that is written before its operand. E.g. unary minus is a prefix operator: - (4 + 2). Also, ++ and -- can be used a prefix operators (see this pdf file). See also infix operator and postfix operator. preorder, inorder, postorder Explanation of preorder, inorder, and postorder traversals of a binary tree: pdf file. prepend To append means to add at the end (of a list). Many moons ago, we coined the word prepend to mean to add at the beginning. Robert Prim The Jarník/Prim/Dijkstra algorithm for constructing a minimum spanning tree: pdf file. Implementing the Jarník/Prim/Dijkstra algorithm. pdf file. Using the JPD spanning-tree algorithm to construct a maze: pdf file.  mazeGeneration.zip primitive type A type that is fully integrated into Java, i.e. one that is not defined by a class definition. 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. priority queue A queue in which each item in it has a priority, and method remove removes and returns the item with lowest priority. pdf file. private An access modifier. A variable or method that is declared with this modifier can be referenced only within the class in which the declaration occurs. procedure A method that is declared with the basic form:      void ( ) { ... } A call of a procedure is a statement. procedure call A procedure call is a statement. Its form is one of: 1. for a static procedure: . ( ) ; 2. for a non-static procedure: . ( ) ; where the evaluates to the name of an object that contains the procedure to be called. Both "." and "." can be omitted if the call appears in a place in which the procedure can be called without them. processing unit A component on a chip in your computer that can execute a sequence of instructions. See pdf file. product of an empty bag The sum of an empty bag of numbers is 0. The product of an empty bag of numbers is 1. See pdf file. programming assignments This pdf file talks about the process of doing a programming assignment. Please take it seriously. promoting a value Same as casting it to a wider type, done automatically in Java when necessary. See narrower type. protected An access modifier; the variable or method that is declared protected can be referenced from within the class, from other classes in the same package, and from a subclass. public An access modifier: the variable or method that is declared with this modifier can be referenced everywhere. QED Q.E.D. This means Quod Erat Demonstrandum, meaning What was to be shown. It is often put at the end of proofs. We jokingly say it means Quit End Done. queue --FIFO list 1. A queue is a list that supports removal from the beginning and insertion at the end. See this pdf file. 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. quicksort 1. An expected-case n log n in-place sorting algorithm. 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. quotes Java uses the single quote for characters, e.g. 'a', '$', '\n'. 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. race condition A race condition occurs when two or more processes executing in parallel access shared data in a way that results in unexpected (and wrong) results. See this pdf file. radix Radix is a stuffy synonym of the base of a number system. For example, base 10 and radix 10 denote the decimal number system. See this pdf file. For radix sorting, see this pdf file. ragged array This pdf-file explains how to create ragged/jagged multidimensional arrays, in which each row can have a different number of element . But if you are not familiar with arrays in Java, read this first: pdf file. raw type For a generic class like ArrayList, the raw type is simply ArrayList while ArrayList is a generic type. This pdf file defines and discusses raw types. real class We don't use this terminology. If you see it anywhere, just ignore what you are reading (e.g. an old prelim question). read a file See I/O. Recursion See Recursion. recursion A method is recursive if its body contains a call on itself. 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. recursive case In a recursive method, a recursive case is case (i.e. values for the method's parameters) in which a recursive call is needed to compute the answer. In a base case, recursion is not needed. See this pdf file. refactoring To refactor a program means to modify it without changing its behavior/correctness with an eye to improving it in some way. 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. reference Reference is another word for pointer. A class variable, like jf defined as     public JFrame jf; contains either null or a pointer to, i.e. a reference to, an object of class JFrame. reference rule The compile-time reference rule determines whether a component reference like p.v or p.m(...) is syntactically correct. See this pdf file. reference type See class type. reflection Reflection is the ability of a computer program to examine, introspect, and modify its own structure and behavior at runtime. Here is an intro to the topic: pdf file    demoCode.zip relative path, a in file system See I/O (first entry). remainder % For c and d of type int, the expression c % d gives the remainder when c is divided by d. repetend repetend means "the thing to be repeated", so it is the body of a loop. In the 1990s, an 11-year old was reading Gries's Science of Programming and emailed Gries some questions, using that word, which Gries didn't know at the time. return statement In a procedure, a return statement has the form return; In a function, a return statement has the form return ; Execution of the return statement terminates execution of the method body in which it occurs and, in the case of a function, returns the value of the as the value of the function call. Robin Hood hashing A substantial modification of hashing using open addressing with linear probing. Has lost of good properties. pdf file. root, leaf, and internal node of a tree For root, leaf, and internal node of a tree see this pdf file. Runnable The interface that declares method run(), which is called to start a thread of execuion. See pdf file. runtime The time when a program (that is, its machine-language version) is being executed, or run, as opposed to compiletime, when the program is checked for syntax errors and is compiled into an equivalent program in the machine language. scientific notation The notation used to write numbers when the exponent is too small or large for the number to be written in decimal form. In Java, one used 'e' or 'E' to indicate the exponent. For example, 500 and 0.5 can be written in scientific notation as 5E2 and 5E-1, respecitively. See float and double. See en.wikipedia.org/wiki/Scientific_notation for a full explanation. scope The scope of a variable is the set of statements in which it can be referenced. For a parameter, it is the body of the method in which the parameter is declared. For a local variable, it is from its declaration to the end of the block in which it is declared. scope box A box within the frame for a method call that contains the name of the class (for a static method) or object (for an instance method) in which the method resides. selection sort A quadratic-time sorting algorithm: pdf file. Refactoring a version of selectionSort, using both extracting a method and inlining a method call: pdf file. semantics Syntax has to do with grammatical correctness, semantics with meaning. We cannot talk about the semantics of a part of a sentence of a language that is not syntactically correct. The semantics of a Java expression or statement defines how it is evaluated or executed. For example, the semantics of the if-statement statement if ( ) is: first, evaluate the ; then, if it is true, execute the . semicolon ; In Java, a semicolon must appear at the end of a "basic" statement, as in    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. setter method A non-static procedure whose purpose is to store a value in a field of the object in which the method resides. By convention, if the field is named time the name of the setter procedure is setTime(value). 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. shadowing a variable Shadowing refers to declaring two variables with the same name with overlapping scopes. Given a reference to such a variable, the inside-out rule indicates to which of the declarations the reference refers. For example, suppose a class has a field x and a method m within the class has a parameter x. That parameter, shadows field x ---every reference to x within the method refers to the parameter. 1. How to use "this." to reference a shadowed field: pdf file. short A primitive type whose values are integers in the range –2^15 .. 2^15 – 1, or -32,768..32,767. See this pdf file for an explanation. short-circuit evaluation This refers to the evaluation of boolean operators && and ||. As soon as the value of a boolean expression is known, evaluation stops. See this pdf file for an explanation. Short, class A wrapper class for type short. shortest path algorithm An algorithm developed by Edsger W. Dijkstra in 1956 for finding the distance of the shortest path from a start node to each node (or to one particular node) in a graph in which the edges have positive weights. 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. side effect, benevolent side effect A side effect occurs when evaluation of an expression changes a variable. We avoid them: pdf file. signature See method signature. silver ratio The irrational number (1 - sqrt(5))/2 = –.6180339887… It is a root of the polynomial x^2 - x - 1. It and its conjugate, the golden ratio, are intimately connected with the Fibonacci numbers. See this pdf file and this pdf file (still to come). simple path, simple cycle A path is simple if all nodes in it are different ---no node is repeated. A cycle is simple if its first node appears exactly twice in it. See this pdf file. sink For an edge (u, v) of a directed graph, u is the source and v is the sink of the edge. See this pdf file. size Size of a tree: the number of nodes in the tree. snippet a small part, piece, or thing (taken from Merriam-Webster Unabridged online dictionary). 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. sorting 0. Interested in the history of sorting? Read this paper by Howard Seward in 1954 on Information sorting: 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. 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 source For an edge (u, v) of a directed graph, u is the source and v is the sink of the edge. See this pdf file. spanning tree 1. A subset of an undirected graph that contains all nodes of the graph and is a tree. See pdf file. 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 sparse A graph is dense if the number of edges is close to the maximum. A graph is sparse if the number of edges is close to the minimum. 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. specification, of a class A description of what a class is for. Generally speaking, it indicates what an instance of the class represents. specification, of a method See method specification. stable sort A sorting algorithm is stable if the relative position of two equal values is unchanged. 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. 1. A stable implementation of insertion sort; why selection sort is inherently unstable: pdf file. 2. Merge sort is usually implemented so that it is stable. 3. Quicksort is inherently unstable because the partition algorithm is inherently unstable. spinning, busy waiting Look at this loop: 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. stack ---LIFO list A stack is a list that supports removal from the end and insertion at the end: pdf file. statement-comment A comment that is a specification of the following lines of code: pdf file. static See static method and static variable. See this pdf file for an explanation. static field Same as static variable. See this pdf file for an explanation. static method A method that is declared with attribute static. There is only one copy of the method. See this pdf file for an explanation of static. static nested class A static class that is declared within another class. Why nested classes are useful: pdf file. A simple but realistic example of the use of a static nested class: pdf file. static type, dynamic type In Java, static type is synonymous with type. Dynamic type has to do with the type of value in a variable at runtime. Read this one-pdf file. StringBuilder, class A class in package java.lang that may be used to build strings more efficiently that class String. This pdf file explains. static variable A variable declared in a class definition with attribute static. There is only one copy of the variable. It is created when execution of the program starts. See this pdf file for an explanation of static. stepwise refinement The systemetic refinement of a specification into an implementation, using small steps. See the tutorial on stepwise refinement. String, class The values of class String are immutable objects that contain sequences of characters. strong vs weak typing Strong vs weak typing in a programming language: pdf file. study habits / work habits Learning to program as well as a programmng language is much like learning a musical instrument. It requires frequent pratice to gain a skill. 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. style guidelines (Java code) Extensive code-style guidelines. subclass Class SC is a subclass of class C, and C is the superclass of SC, if the definition of class SC has an extends clause extends C. This means that every instance of class SC inherits all the components of class C. subtree Choose any node in a tree, say node C. Then subtree C consists of C, all its children, all their children, etc. Thus, we use C for two things: either a node or the subtree with C as its root. See this pdf file. subtype polymorphism Read this pdf file. See also polymorphism. super A keyword that is used in two ways. (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.. superclass See subclass. superest Class Object, defined in package java.lang, is the superclass of all classes that do not explicitly extend another. It is the only class with no superclass, so we call it the superest class of them all. This pdf file shows how to draw objects with a partition for class Object. switch statement See this pdf file. synchronized statements and methods See this pdf file. See also Concurrency. 20-sec video of Christopher Caspersen's new outhouse (2018): video.mov. syntactic rule A rule that applies to the syntax of a program. See syntax. syntactic sugar (In a programming language) syntax that is designed to make something easier to read or write. For example, a foreach loop like "for (C c : list) {...}" is syntactic sugar for a more complicated loop; this syntactic sugar is converted to the more complicated loop before the program is compiled. Another example is an enum class, which is an abbreviation for a more complicated-looking class. syntax The arrangement of words and phrases to create well-formed sentences in a language, or the set of rules that describe well-formed sentences. In Java, the syntax of the assignment statement is =    ; where (1) the must be declared beforehand and (2) the type of the must be the same as or narrower than the type of the . That's all part of the syntax, and a program will not be compiled if the rules are not followed. tail call, tail recursion A recursive call is a tail call if no further action is performed in the method after that tail call has been executed. A method with a tail call is termed tail recursive. This pdf file shows how tail calls can be optimized. ternary operator An operator with three operands. One example in Java is the conditional expression. See also unary operator and binary operator. testing (whitebox, blackbox, structural) Testing is the process of running a program to find errors in it. See this pdf file. 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. then-part In an if-statement  if (b) S1  or an if-else statement  if (b) S1 else S2 , statement S1 is called the then-part. this A keyword that is used in two ways. (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. Threads See concurrency. thread-safe, thread safety These terms refer to code that can be used in an environment in which two or more threads are executing at the same time but the code still performs as expected. For example, the assignment 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. throws-clause A clause of the form  throws  that may have to be included in a method header if the method may throw a checked exception. This webpage contains a video that explains. Throwable, class The superclass of all classes whose objects can be thrown in a throw-statement. Watch a 3.2-minute video on throwable objects here. topological sort An algorithm that orders the nodes of a DAG so that the source of each edge precedes the sink. This pdf file develops the algorithm. Proof that a directed graph in which each node has indegree > 0 contains a cycle: pdf file. throw-statement The throw-statement has the form  throw ; 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. toString function A Java convention is to write an instance function toString() that yields a description of the object in which it resides. Function toString() is defined in Object, the superest class of them all. That function returns the name of the object (e.g. C@fdee). Example. In a class Point with two fields contain the x- and y-coordinates of a point in the plane, calling p.tostring() where object p contains x-value 5 and y-value 4 could return "(5, 4)". trees 0. Poems about trees, including Joyce Kilmers famous poem: pdf file. 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 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 Here is the syntax of the try-statement: try catch () ... catch ) where each of the 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. two's complement notation A way of representing an integer as a sequence of bits. Used in most computers today: pdf file. type A set of values together with operations on them. E.g.the integers, together with operations +, -, *, /. Java has primitive types and class types. type argument The type given within <> of a generic variable declaration or new-expression, e.g. new ArrayList(): pdf file. type parameter The name given within <> of a generic class or method declaration, e.g. public class Wrapper {...}: pdf file. type, raw See raw type. types A type is a set of values together with operations on them. 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. type safety See this pdf file. type Strong versus weak typing: pdf file. Java primitive types: tyro A tyro is a beginner, a novice. Tyro is pronounced tīrō, like gyro in the word gyroscope. It has nothing to do with gyro, that Greek fast food delicacy, wrapped in pita bread. Tyro was Merriam-Webster's Word of the Day on 24 April 2015. Click here to visit Merriam-Webster's website and listen to their podcast about the word. unary operator An operator with one operand. In the following examples, unary minus and factorial each have one operand: - (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. underdetermined specification The word underdetermined means not having enough constraints to specify a unique solution. 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. undirected graph A graph whose edges are undirected: pdf file. unicode ascii This pdf file explains type char and the unicode representation of characters. It discusses ascii, a 7-bit representation of characters developed in the 1960s. This pdf file explains what to watch out for when characters not in type char are used in Strings. upper-bounded type or wildcard See generics. UTF-8 UTF-8 is a variable-width encoding of all Unicode characters. It uses 1-4 bytes per character. Just about all characters of all languages are included, and also musical symbols and much more. It's the preferred encoding for email and web browsers, and it should also be used in Eclipse. To check that it is used in Eclipse, use menu item Preferences -> General -> Workspace and select UTF-8 as the Text File Encoding. See en.wikipedia.org/wiki/UTF-8 for more information. var Introduced in version 10 of Java to make declarations of local variables less cumbersome. For example, instead of    ArrayList st= new ArrayList();    one can now write    var st=  new ArrayList();  and the type of st will be inferred from the initializing expression. "var" can still be used as a variable name. See this pdf file. variables A variable is a name with an associated value. Sometimes viewed as a named box with the value in the box. In Java, a variable has a type, which defines the set of values that the box can contain. In Java, there are four kinds of variable: 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. VM virtual machine. See JVM. VM argument An argument for the virtual machine, such as "-ea". In Eclipse, chooise menu item Run -> Run Configurations. In the window that opens, click the Arguments pane. There you will see a field to enter Program Arguments for a call and VM arguments for a call. variable declaration The basic form of a variable declaration is . Depending on the kind of variable being declared, there may be modifiers. See parameter, local variable, instance variable, and static variable. void A java keyword used to indicate that a method is a procedure and does not return a result. See procedure. waitlist The waitlist of an object is the set of threads that, while synchronized on the object, had executed a call wait();. They stay on the waitlist until execution of a call notify(); or notifyAll(); places them back on the locklist. See pdf file. while-loop (while-statement) See this pdf file for an explanation of the while-loop. white space The exact meaning of a Java white space character is given at this URL. The space character ' ', or '\u0020', is white space, and so are the tab '\t', line feed '\n', and carriage return '\r'. 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. wider type See narrower type. work habits. See study/work habits. workspace The directory where Eclipse maintains information about your Java projects. Read a little bit about workspaces in the first few paragraphs here. worms Read about the first computer worm and how it brought down the internet: pdf file. wraparound This refers to the following. The largest value of type int is 2147483647. If you add 1 to it by evaluating 2147483647+1, the number overflows and you get the smallest value of type int: -2147483648. To see the reason for this, study two's complement notation. wrapper class Each of the primitive types of Java has an associated wrapper class. For example, the wrapper class for type int is Integer. Each object of the wrapper class contains, or wraps, one value of the primitive type, thus allowing a primitive type value to be viewed as an object. Wrapper class objects are immutable, unchangeable. In addition, the wrapper class provides functions for manipulating values of the primitive type and may also include a few constants. Read wrappers.pdf write a file See I/O. zero The number 0, sometimes called nil, nada, zilch, and many other terms. See en.wikipedia.org/wiki/0 for its history and more. ©2017 David Gries

本站部分内容来自互联网,仅供学习和参考