This is a CS 2 book that presents classical data structures in an object-oriented programming (OOP) context using Java. This book also focuses on the basic principles of OOP and graphical user interface (GUI)-based programming – two paradigms essential for modern programming and problem solving. Our book is aimed principally at CS 2 students but may also be valuable to software development professionals who wish to upgrade their skills in the areas of OOP, GUI programming, and classical data structures.

The software development principles associated with OOP provide a strong framework for presenting and implementing classical data structures. We adhere to and emphasize these principles throughout this book.

Universities have been slow to introduce courses related to OOP into their curricula. Curriculum change has always occurred slowly at universities, but the past dozen years have been particularly disappointing in the area of OOP education. Often a department assumes that because it has switched language from Pascal or C to C++ or Java in CS 1 or CS 2 that it has made a commitment to object-oriented software education. This is simply not true. Object orientation embodies a set of principles often obscured by the intensive preoccupation with language details often evident in early university courses and the books that cater to these courses. The spate of CS 1 and CS 2 books featuring C++ or Java are often nothing more than warmed-over reruns of structured programming texts written originally for Pascal or C.

Sorting involves rearranging information in some container, usually an array, so that the information is stored from smallest to largest (ascending order) or from largest to smallest (descending order). The need to sort is fundamental. We are interested in finding efficient algorithms to accomplish the task.

We shall assume throughout this chapter that the entities to be sorted are Comparable. That is, they may be compared using the query compareTo.

All the sorting methods are presented as static functions with an array of Comparable as the first parameter and the number of elements to be sorted as the second parameter. Although this represents a departure from the normal pattern of object-oriented class construction, we believe it is justified. As long as the array of elements to be sorted are Comparable the user should not be burdened with having to create an instance of a sorting class in order to rearrange the elements in the array that requires sorting.

Simple and Inefficient Sorting Algorithms

We consider two relatively simple sorting algorithms in this section before turning our attention to more efficient sorting.

Selection Sort

The array is scanned from index 1 to index n and the location of the largest value is obtained. This value is interchanged with the nth value. This assures that the largest value is placed in the rightmost position (index n).

The array is again scanned, this time from index 1 to index n – 1. The location of the largest value is obtained.

Object-oriented software development is centered on the construction of classes. Classes represent a model of the application domain. Object-oriented software analysis and design are preoccupied with the discovery of classes and the relationships they have to each other. Through composition – in which one class holds one or more objects from other classes – and inheritance, the architecture of a software system is denned. This architecture is ultimately realized at the implementation phase by the construction and definition of classes.

This chapter closely examines the issues related to class construction using Java. Among the important issues to be discussed are:

1. What responsibilities should be vested within a class?

2. What responsibilities should be vested with the user of a class?

3. How can we bind the user's responsibilities with the class's responsibilities?

4. How can we organize the behavior of a class in a systematic manner?

5. What naming conventions and documentation style should be employed in class construction?

6. How can and should one control the visibility and access to various features of a class?

Responsibilities between a Class and Its Users – Design by Contract

Bertrand Meyer, perhaps more than any other writer, has clarified and influenced our thinking regarding the responsibilities between a class and its users. His ideas are contained in his seminal work Object-Oriented Software Construction, Second Edition (Prentice-Hall, 1997) and manifested in the Eiffel programming language and environment.

We examine two important types of relationships between classes in this chapter – namely, composition and inheritance. We illustrate the concepts by constructing a complete software system in Java that illustrates the use of these two types of relationships.

Inheritance

Inheritance, as the name implies, involves the transmittal of behavioral characteristics from parent class to child class. Through inheritance one can establish behavior in a base class that is available and directly usable in a hierarchy of descendent classes that extend the base class.

As discussed in Chapter 1, inheritance can be centered on factoring and reusing methods (implementation inheritance) or on extending behavior (behavioral inheritance). It is the latter that we shall utilize in this chapter and throughout this book.

With behavioral inheritance, it is essential that any child class logically be of the same type as its parent. As you recall from Chapter 1, the principle of polymorphic substitution allows a descendent class to be used in place of its ancestor. This would make sense only if each child class can logically be considered to be a kind of its parent.

A child class may extend a parent class by introducing one or more fields or methods not found in the parent or by redefining one or more parent class methods.

One of the conceptual pillars supporting object-oriented software development is the abstract data type (ADT). David Parnas and others articulated this concept in the 1960s. For many years this concept has formed the basis for software construction, both object oriented and otherwise. All of the data structures to be presented in this book are formulated as abstract data types.

A data type is a program entity holding information that can be manipulated in a disciplined manner through a set of predefined operations. Predefined operations include commands that may be used to modify the value of the data type and queries that may be used to access the value of the data type. In the Java programming language an abstract data type is implemented using the class construct. The information structure (data structure) of the ADT is represented in the internal (usually private or protected) fields of the class. The commands are represented by methods that return type void. The queries are represented either by public fields or methods that return a nonvoid type representing field information.

Many software developers have found that ADTs aid in formulating clear and clean software architecture and promote greater understandability of the software and easier software maintenance. In structured programming languages such as C and Pascal the programmer must impose strict protocols in order to utilize ADTs. In the early 1980s two pre-object-oriented languages, Ada and Modula-2, were specifically designed to support and encourage the use of ADTs.

Binary trees were introduced in the previous chapter. A binary tree holds the generic Object type that serves as a placeholder for any reference type. This combined with its nonlinear structure makes it suitable for representing a diversity of information.

This chapter focuses on a specialized but extremely important tree type – the search tree. Such a binary tree holds elements of type Comparable. That is, the elements stored in a search tree may be compared to one another by answering to the query compareTo. The goal of a search table is to provide efficient access to information while allowing the information to be output in an ordered sequence. The order of elements in a binary search tree is based on a comparable property of the elements themselves.

In Chapter 13 we examined the OrderedList as a concrete implementation of a SearchTable. Here we shall examine three concrete search tree classes, each providing an implementation of the interface SearchTable. These concrete classes are BinarySearchTree, AVLTree, and SplayTree. In addition, we shall investigate another interesting and recent implementation of SearchTable, given by class SkipList.

Review of Search Table Abstraction

Recall from Chapter 10 that a search table is a compact abstraction that extends Container and provides the commands add and remove in addition to the command makeEmpty in class Container. The queries contains, get, and iterator are provided by SearchTable in addition to the queries isEmpty and size inherited from Container.

The principles and practices of object-oriented software construction have evolved since the 1960s. Object-oriented programming (OOP) is preoccupied with the manipulation of software objects. OOP is a way of thinking about problem solving and a method of software organization and construction.

The concepts and ideas associated with object-oriented programming originated in Norway in the 1960s. A programming language called Simula developed by Christian Nygaard and his associates at the University of Oslo is considered the first object-oriented language. This language inspired significant thinking and development work at Xerox PARC (Palo Alto Research Center) in the 1970s that eventually led to the simple, rich, and powerful Smalltalk-80 programming language and environment (released in 1980). Smalltalk, perhaps more than any programming language before or after it, laid the foundation for object-oriented thinking and software construction. Smalltalk is considered a “pure” object-oriented language. Actions can be invoked only through objects or classes (a class can be considered an object in Smalltalk). The simple idea of sending messages to objects and using this as the basis for software organization is directly attributable to Smalltalk.

Seminal work on object-oriented programming was done in the mid-1980s in connection with the Eiffel language. Bertrand Meyer in his classic book Object-Oriented Software Construction (Prentice-Hall, 1988; Second Edition, 1997) set forth subtle principles associated with OOP that are still viable and alive today.

We are all familiar with the concept of a dictionary as a fairly large book containing words and definitions. The words are always in alphabetical order to help us look up a particular word. Having the words in alphabetical order is a convenient feature but is not required. There may be other ways to find words in the dictionary, especially if our dictionary is in electronic form. Most words in a dictionary have several definitions. We associate each word with its definitions. Thus, we may characterize a dictionary as a container (possibly ordered) of associations between words and their meanings.

To take our reasoning a step further in our attempt to understand the required behavior of a dictionary, we never add definitions to a dictionary unless they are associated with a word. On the other hand, as we are building the dictionary we may add words without definitions on the promise that the definitions will be added later for those words. And finally, as we fine tune our understanding, we may change definitions for words that are already in the dictionary. We may wish to remove entries in the dictionary or access them in various ways. For example, we may wish to access a list of the words only, the meanings only, or the entire list of entries.

In Chapter 10 we defined interface Dictionary as an extension of the Container interface, interface OrderedDictionary as an extension of SearchTable, and supporting class Association.

In a world with perfect users, perfect programs, and perfect hardware we would not have to concern ourselves with exceptions. Users would never enter incorrect data (e.g., enter an alphabetic character when a number is required). Hardware would never fail. Printers would always be on when our software attempts to access them. A hard drive would never be full when a program attempts to write to it. Such a world does not exist.

Brittle programs do indeed crash because of some failure in the input, the program logic, or the physical system supporting the application. Some crashes occur because of hardware interrupts (failures in a hardware component) or synchronization conflict (two or more segments of code attempting to modify the same data simultaneously). Program crashes may be catastrophic. If the rudder computer control system on an aircraft were to go down or the computer guidance system on a rocket were to fail, a catastrophe of major proportions might occur. Often a program crash results in a loss of input data – not a catastrophe but a profound annoyance to the user. One's confidence in using a program often disappears if such loss of data occurs frequently.

Exception handling involves defensive programming tactics that ensure a more benign outcome if your programming application should fail. Exception handling can ensure that input data are saved before a program is terminated, can notify the user that an input or hardware error has occurred and allow program execution to continue, or can bring the system to a stable and safe state before exiting the application.

Two resources coveted by software developers are memory space and execution time. Among the factors that determine the memory footprint of an application or its execution time is the algorithm chosen in the application (there may of course be many algorithms used within an application).

The space taken by an algorithm is related to the information structure used to hold the data and any other information structures required to support the computational process. These are usually defined as fields in the data structure class.

The time required to execute an algorithm is dependent on the structure of the algorithm. We are usually concerned with the worst-case time, the best-case time, and the average time, to be defined in the following paragraphs. Sometimes these are the same. These execution times are usually related to one or more parameters that determine the size of the problem being solved. To be conservative we normally rely on worst-case time when comparing two algorithms.

The worst-case time is the longest time that any problem of specified size takes to execute. The best-case time is the shortest time that any problem of specified size takes to execute. The average-case time is an estimate of the time required for an average problem of specified size.

For worst-case, best-case, and average-case times, we are normally concerned with asymptotic time complexity – in plain English, the time required to complete an algorithm as a function of problem size when the problem size is assumed to be large.

Summary. We prove some results on the degrees. We show that splits in the e-degrees above any incomplete degree; on the other hand, one can find a splitting of into e-degrees b and d, such that for any degree

Introduction

A set A is enumeration reducible (e-reducible) to a set B if there exists a recursively enumerable (r. e.) set (called in this context an enumeration operator, or, simply, an e-operator) such that

The structure De of the e-degrees is the structure of the equivalence classes (called e-degrees) of sets of numbers under the equivalence relation generated by the preordering the e-degree of A is denoted by the symbol. De is in fact an uppersemilattice with least element where any r. e. set W: the partial ordering relation of will be denoted by

Throughout the paper we will refer to some fixed acceptable numbering of the (r. e.) sets; we therefore obtain a corresponding listing of the e-operators. We will consider finite recursive approximations to the r.e. sets (in the sense of [20, p.16]). We get corresponding finite recursive approximations to the e-operators. We will indicate by the approximation to defined by where is some fixed finite recursive approximation to K.

We adopt the usual notational conventions: see for instance Soare [20], and Cooper [9]. Given a set F, let and. Thus, We sometimes identify a given finite set with its canonical index, thus writing for instance to denote the number where u is the canonical index of F. If B and then if then

It is known ([16], [19]) that the e-degrees extend the structure of the Turing degrees: the mapping defined by (where and denote the Turing degree and the characteristic function of A, respectively) defines an order theoretic embedding preserving joins and least element.

The degrees

McEvoy ([15]) defines a jump operation on. Of particular interest is the structure (it is known that. It is shown in [8] that S is dense and S coincides with the structure of the (in fact, if and only if). One can distinguish several substructures of S. In particular, the correspond, under the above mentioned embedding, to the r. e. Turing degrees a is a if and only if for some r. e.

Ladies and Gentlemen,

I am very happy to be able to welcome you to Prague. French historian Ernest Denis once wrote that in Prague every stone tells a story. As you walk across the Charles Bridge, pause to remember Tycho de Brahe and Johannes Kepler who used to stroll there over 400 years ago as well as Bernard Bolzano two centuries later. I am sure that you too will fall in love with this old, inspiring, majestic, but also tragic city.

These were the words with which I had planned to welcome participants of Logic Colloquium '80 which was cancelled by the communist government. The totalitarian regime was afraid that the participating mathematicians would call for the release of their colleague, mathematician Vaclav Benda, who was serving a 5 year prison term. He was imprisoned for publicity drawing attention to politically motivated prosecution of those opposing the regime. For us, Czech mathematicians, the cancellation meant even deeper isolation from our colleagues abroad. But we never doubted that even though mathematics is very beautiful, freedom is even more so.

Logic Colloquium '98 will now commence.

The 1998 European Summer Meeting of the Association for Symbolic Logic, Logic Colloquium '98 was held at the University of Economics in Prague, August 9-15, 1998. It was co-organized by the Academy of Sciences of the Czech Republic and the Charles University—on the occasion of the 650th anniversary of the founding of the university. During the conference, the Bolzano medal of the Academy of Sciences of the Czech Republic was presented to Gaisi Takeuti in recognition of his work in mathematical logic and other areas and for his cooperation with Czech mathematicians.

The last time a Logic Colloquium was scheduled to be held in Prague was August 1980. Unfortunately, the Czechoslovakian government cancelled that meeting about 40 days beforehand, due to fears that participants would organize protests against the imprisonment of the Czech philosopher and mathematician V. Benda (Benda is presently a senator in the Czech parliament). Nonetheless, the volume Logic Colloquium '80, containing papers intended for the cancelled meeting, was published in 1982.

The program of Logic Colloquium '98 included fifteen invited one-hour plenary addresses, three tutorials, and 39 invited half-hour lectures in parallel special sessions on computability theory, proof theory, set theory, model theory, philosophical logic and fuzzy logic. In addition, there were 98 contributed talks plus 26 papers presented by title. The number of registered participants was 241, coming from 30 countries.

The tutorial short courses were given by P. Hájek, Metamathematics of fuzzy logic; J. Krajíček, Propositional logic, arithmetic and complexity; and Z. Sela, The elementary theory of free groups.

Invited plenary addresses were given by: S.B. Cooper, Hartley Rogers’ 1965 agenda; T. Coquand, Formal topology and proof theory; A. Ekert, On some ramifications of quantum computation (joint work with R. Lupacchini); L. Fortnow, Separating classes; B. Hart, The uncountable spectra of countable theories; G. Hjorth, Vaught conjecture on analytic sets; T. Jech, Stationary sets; C. Jockusch, Ramsey's theorem, computability, and second-order number theory; L. Lipshitz,