Object Oriented Datastructures using Java

By Nell Dale, Daniel T. Joyce and Chip Weems

Welcome to the first edition of Object-Oriented Data Structures using Java. This book has been written to present the algorithmic, programming, and structuring techniques of a traditional data structures course in an objectoriented context. You’ll find that all of the familiar topics of lists, stacks, queues, trees, graphs, sorting, searching, Big-O complexity analysis, and recursion are still here, but covered from an object-oriented point of view using Java. Thus, our structures
are defined with Java interfaces and encapsulated as Java classes. We use abstract classes and inheritance, as appropriate, to take advantage of the relationships among various versions of the data structures. We use design aids, such as Class-Responsibility-Collaborator (CRC) Cards and Universal Modeling Language (UML) diagrams, to help us model and visualize our classes and their interrelationships. We hope that you enjoy this modern and up-to-date approach to the traditional data structures course.

Abstract Data Types

Over the last 16 years, the focus of the data structures course has broadened considerably. The topic of data structures now has been subsumed under the broader topic of abstract data types (ADTs)—the study of classes of objects whose logical behavior is defined by a set of values and a set of operations.

The term abstract data type describes a domain of values and set of operations that are specified independently of any particular implementation. The shift in emphasis is representative of the move towards more abstraction in computer science education. We now are interested in the study of the abstract properties of classes of data objects in addition to how the objects might be represented in a program.

The data abstraction approach leads us, throughout the book, to view our data structures from three different perspectives: their specification, their application, and their implementation. The specification describes the logical or abstract level. This level is concerned with what the operations are and what they do. The application level, sometimes called the user level, is concerned with how the data type might be used to solve a problem. This level is concerned with why the operations do what they do. The implementation level is where the operations are actually coded. This level is concerned with the how questions.

Using this approach, we stress computer science theory and software engineering principles, including modularization, data encapsulation, information hiding, data abstraction, stepwise refinement, visual aids, the analysis of algorithms, and software verification methods. We feel strongly that these principles should be introduced to computer science students early in their education so that they learn to practice good software techniques from the beginning.

An understanding of theoretical concepts helps students put the new ideas they encounter into place, and practical advice allows them to apply what they have learned. To teach these concepts we consistently use intuitive explanations, even for topics that have a basis in mathematics, like the analysis of algorithms. In all cases, our highest goal has been to make our explanations as readable and as easily understandable as possible.

Click to Download

Object-oriented Data Structures Using Java

Data Structures in Java - A Laboratory Course

By Sandra Andersen

To learn a subject such as computer science, you need to immerse yourself in it --learning by doing rather than by simply observing. Through the study of several classic data structures and algorithms, you will become a better informed and more knowledgeable computer science student and programmer. To be able to professionally choose the best algorithm and data structure for a particular set of resource constraints takes practice.

An emphasis on learning by doing is used throughout Data Structures in Java: A Laboratory Course. In each laboratory, you explore a particular data structure by implementing it. As you create an implementation, you learn how the data structure works and how it can be applied. The resulting implementation is a working piece of software that you can use in later laboratories and programming projects.

Click to Download

Data Structures in Java: A Laboratory Course

Algorithms and Data Structures in VLSI Design

By Christoph Meinel and Thorsten Theobald

One of the main problems in chip design is the huge number of possible combinations of individual chip elements, leading to a combinatorial explosion as chips become more complex. New key results in theoretical computer science and in the design of data structures and efficient algorithms can be applied fruitfully here. The application of ordered binary decision diagrams (OBDDs) has led to dramatic performance improvements in many computer-aided design projects. This textbook provides an introduction to the foundations of this interdisciplinary research area, with an emphasis on applications in computer-aided circuit design and formal verification.

Contents
1. Introduction

2. Basics

2.1 Propositions and Predicates - 2.2 Sets, Relations, and Functions - 2.3 Graphs - 2.4 Algorithms and Data Structures - 2.5 Complexity of Algorithms - 2.6 Hashing - 2.7 Finite Automata and Finite State Machines - 2.8 References

Part I: Data Structures for Switching Functions
3. Boolean Functions

3.1 Boolean Algebras - 3.2 Boolean Formulas and Boolean Functions - 3.3 Switching Functions - 3.3.1 Switching Functions with at most Two Variables - 3.3.2 Subfunctions and Shannon's Expansion - 3.3.3 Visual Representation - 3.3.4 Monotone Switching Functions - 3.3.5 Symmetric Functions - 3.3.6 Threshold Functions - 3.3.7 Partial Switching Functions - 3.4 References

4. Classical Representations

4.1 Truth Tables - 4.2 Two-Level Normal Forms - 4.3 Circuits and Formulas - 4.3.1 Circuits - 4.3.2 - Formulas - 4.4 Binary Decision Trees and Diagrams - 4.4.1 Binary Decision Trees - 4.4.2 Branching Programs - 4.4.3 Read-Once Branching Programs - 4.4.4 Complexity of Basic Operations - 4.5 References

5. Requirements on Data Structures in Formal Circuit Verification

5.1 Circuit Verification - 5.2 Formal Verification of Combinational Circuits - 5.3 Formal Verification of Sequential Circuits - 5.4 References

Part II: OBDDs: An Efficient Data Structure
6. OBDDs - Ordered Binary Decision Diagrams

6.1 Notation and Examples - 6.2 Reduced OBDDs: A Canonical Representation of Switching Functions - 6.3 The Reduction Algorithm - 6.4 Basic Constructions - 6.5 Performing Binary Operations and the Equivalence Test - 6.6 References

7. Efficient Implementation of OBDDs

7.1 Key Ideas - 7.1.1 Shared OBDDs - 7.1.2 Unique Table and Strong Canonicity - 7.1.3 ITE Algorithm and Computed Table - 7.1.4 Complemented Edges - 7.1.5 Standard Triples - 7.1.6 Memory Management - 7.2 Some Popular OBDD Packages - 7.2.1 The OBDD Package of Brace, Rudell, and Bryant - 7.2.2 The OBDD Package of Long - 7.2.3 The CUDD Package: Colorado University Decision Diagrams - 7.3 References

8. Influence of the Variable Order on the Complexity of OBDDs

8.1 Connection Between Variable Order and OBDD Size - 8.2 Exponential Lower Bounds - 8.3 OBDDs with Different Variable Orders - 8.4 Complexity of Minimization - 8.5 References

9. Optimizing the Variable Order

9.1 Heuristics for Constructing Good Variable Orders - 9.1.1 The Fan-In Heuristic - 9.1.2 Die Weight Heurisitic - 9.2 Dynamic Reordering - 9.2.1 The Variable Swap - 9.2.2 Exact Minimization - 9.2.3 Window Permutation - 9.2.4 The Sifting Algorithm - 9.2.5 Block Sifting and Symmetric Sifting - 9.3 Quantitative Statements - 9.4 Outlook - 9.5 References

Part III: Applications and Extensions
10. Analysis of Sequential Systems

10.1 Formal Verification - 10.2 Basic Operators - 10.2.1 Generalized Cofactors - 10.2.2 The Constrain Operator - 10.2.3 Quantification - 10.2.4 The Restrict Operator - 10.3 Reachability Analysis - 10.4 Efficient Image Computation - 10.4.1 Input Splitting - 10.4.2 Output Splitting - 10.4.3 The Transition Relation - 10.4.4 Partitioning the Transition Relation - 10.5 References

11. Symbolic Model Checking11.1 Computation Tree Logic - 11.2 CTL Model Checking - 11.3 Implementations - 11.3.1 The SMV System - 11.3.2 The VIS System - 11.4 References

12. Variants and Extensions of OBDDs12.1 Relaxing the Ordering Restriction - 12.2 Alternative Decomposition Types - 12.3 Zero-Suppressed BDDs - 12.4 Multiple-Valued Functions - 12.4.1 Additional Sinks - 12.4.2 Edge Values - 12.4.3 Moment Decompositions - 12.5 References

13. Transformation Techniques for Optimization13.1 Transformed OBDDs - 13.2 Type-Based Transformations - 13.2.1 Definition - 13.2.2 Circuit Verification - 13.3 Linear Transformations - 13.3.1 Definition - 13.3.2 Efficient Implementation - 13.3.3 Linear Sifting - 13.4 Encoding Transformations - 13.5 References

Bibliography

Index

Click to ReadMore/Download

Data Structures:All Chapters

From Wikibooks, the open-content textbooks collection

Computers can and usually store and process vast amounts of data. Some of this data is of use in limited ways (such as the company's name, the date, etc) while most application data follows some pattern. For example, student records at a university would typically contain an id-number, names, addresses, contact details, course information, etc. For conceptual and data processing efficiency reasons this vast amount of data should be structured. That is, the same sort of data, in our student records example, would be provided for each student. Within the one application there would typically be many of such data structures created. Also typically there would be some conceptual relationships which link data structures.

There are no hard and fast rules as to how data must be structured. The structures which are adopted will be determined by the purpose to be achieved. Sometimes the structure of the software may be a relevant consideration, as well as the amount of data involved.

The objective is, ultimately, to process the data captured or stored on the computer in the most efficient manner.

Formal data structures enable a programmer to mentally structure the large amounts of data into conceptually manageable relationships.

Sometimes we use data structures to allow us to do more: for example, to accomplish fast searching or sorting of data. Other times, we use data structures so that we can do less: for example, the concept of the stack is a limited form of a more general data structure. These limitations provide us with guarantees that allow us to reason about our programs more easily. Data structures also provide guarantees about algorithmic complexity — choosing an appropriate data structure for a job is crucial for writing good software.

Because data structures are higher-level abstractions, they present to us operations on groups of data, such as adding an item to a list, or looking up the highest-priority item in a queue. When a data structure provides operations, we can call the data structure an abstract data type (sometimes abbreviated as ADT). Abstract data types can minimize dependencies in your code, which is important when your code needs to be changed. Because you are abstracted away from lower-level details, some of the higher-level commonalities one data structure shares with a different data structure can be used to replace one with the other.

Our programming languages come equipped with a set of built-in types, such as integers and floating-point numbers, that allow us to work with data objects for which the machine's processor has native support. These built-in types are abstractions of what the processor actually provides because built-in types hide details both about their execution and limitations.

Click to Read More

Data Structures and Algorithms in C++

By Michael T. Goodrich, Roberto Tamassia and David M. Mount

This book provides a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation. In terms of the computer science and computer engineering curricula, we have written this book to be primarily focused on the Freshman-Sophomore level Data Structures (CS2) course.

This is a "sister"' book to Goodrich-Tamassia, Data Structures and Algorithms in Java (DSAJ), but uses C++ as the basis language instead of Java. This present book maintains the same general structure as DSAJ, so that CS/CE programs that teach data structures in both C++ and Java can share the same core syllabus, with one course using DSAJ and the other using this book.

While this book retains the same pedagogical approach and general structure as DSAJ, the code fragments have been completely redesigned. Because the C++ language supports almost all of Java's basic constructs, it would be tempting to simply translate the code fragments from Java to the corresponding C++ counterparts. We have been careful, however, to make full use of C++'s capabilities and design code in a manner that is consistent with modern C++ usage. In particular, whenever appropriate, we use elements of C++ that are not part of Java, including templated functions and classes, the C++ Standard Template Library (STL), C++ memory allocation and deallocation (and we discuss the associated tricky issues of writing destructors, copy constructors, and assignment operators), virtual functions and virtual class destructors, stream input and output, and C++'s safe run-time casting. However, we have avoided some of C++'s more arcane or easily misused elements, such as pointer arithmetic.

Highlights of this book include:

• Review of basic features of the C++ programming language
• Introduction to object-oriented design with C++ and design patterns
• Consistent object-oriented viewpoint throughout the book
• Comprehensive coverage of all the data structures taught in a typical CS2 course, including vectors, lists, heaps, hash tables, and search trees
• Detailed explanation and visualization of sorting algorithms
• Coverage of graph algorithms and pattern-matching algorithms for more advanced CS2 courses
• Visual justifications (that is, picture proofs), which make mathematical arguments more understandable for students, appealing to visual learners
• Motivation of algorithmic concepts with Internet-related applications, such as Web browsers and search engines
• Accompanying Web site http://datastructures.net with a special password-protected area for instructors.

Click to Read More

Algorithmic Information Theory

By G J Chaitin

The aim of this book is to present the strongest possible version of G¨odel's incompleteness theorem, using an information-theoretic approach based on the size of computer programs.

One half of the book is concerned with studying , the halting probability of a universal computer if its program is chosen by tossing a coin. The other half of the book is concerned with encoding as an algebraic equation in integers, a so-called exponential diophantine equation.

G¨odel's original proof of his incompleteness theorem is essentially the assertion that one cannot always prove that a program will fail to halt. This is equivalent to asking whether it ever produces any output. He then converts this into an arithmetical assertion. Over the years this has been improved; it follows from the work on Hilbert's 10th problem that G¨odel's theorem is equivalent to the assertion that one cannot always prove that a diophantine equation has no solutions if this is the case.

In our approach to incompleteness, we shall ask whether or not a program produces an in nite amount of output rather than asking whether it produces any; this is equivalent to asking whether or not a diophantine equation has in nitely many solutions instead of asking whether or not it is solvable.

If one asks whether or not a diophantine equation has a solution for N dierent values of a parameter, the N dierent answers to this question are not independent; in fact, they are only log2 N bits of information. But if one asks whether or not there are in nitely many solutions for N dierent values of a parameter, then there are indeed cases in which the N dierent answers to these questions are independent mathematical facts, so that knowing one answer is no help in knowing any of the others. The equation encoding has this property.

When mathematicians can't understand something they usually assume that it is their fault, but it may just be that there is no pattern or law to be discovered!

How to read this book: This entire monograph is essentially a proof of one theorem, Theorem D in Chapter 8. The exposition is completely self-contained, but the collection Chaitin (1987c) is a useful source of background material. While the reader is assumed to be familiar with the basic concepts of recursive function or computability theory and probability theory, at a level easily acquired from Davis (1965) and Feller (1970), we make no use of individual results from these elds that we do not reformulate and prove here. Familiarity with LISP programming is helpful but not necessary, because we give a selfcontained exposition of the unusual version of pure LISP that we use, including a listing of an interpreter. For discussions of the history and signi cance of metamathematics, see Davis (1978), Webb (1980), Tymoczko (1986), and Rucker (1987).

Although the ideas in this book are not easy, we have tried to present the material in the most concrete and direct fashion possible. We give many examples, and computer programs for key algorithms. In particular, the theory of program-size in LISP presented in Chapter 5 and Appendix B, which has not appeared elsewhere, is intended as an illustration of the more abstract ideas in the following chapters.

Click to Download

Algorithms and Complexity

by Herbert S. Wilf

For the past several years mathematics majors in the computing track at the University of Pennsylvania have taken a course in continuous algorithms (numerical analysis) in the junior year, and in discrete algorithms in the senior year. This book has grown out of the senior course as I have been teaching it recently. It has also been tried out on a large class of computer science and mathematics majors, including seniors and graduate students, with good results.

Selection by the instructor of topics of interest will be very important, because normally I’ve found that I can’t cover anywhere near all of this material in a semester. A reasonable choice for a first try might be to begin with Chapter 2 (recursive algorithms) which contains lots of motivation. Then, as new ideas are needed in Chapter 2, one might delve into the appropriate sections of Chapter 1 to get the concepts and techniques well in hand. After Chapter 2, Chapter 4, on number theory, discusses material that is extremely attractive, and surprisingly pure and applicable at the same time. Chapter 5 would be next, since the foundations would then all be in place. Finally, material from Chapter 3, which is rather independent of the rest of the book, but is strongly connected to combinatorial algorithms in general, might be studied as time permits.

Throughout the book there are opportunities to ask students to write programs and get them running. These are not mentioned explicitly, with a few exceptions, but will be obvious when encountered. Students should all have the experience of writing, debugging, and using a program that is nontrivially recursive, for example. The concept of recursion is subtle and powerful, and is helped a lot by hands-on practice. Any of the algorithms of Chapter 2 would be suitable for this purpose. The recursive graph algorithms are particularly recommended since they are usually quite foreign to students’ previous experience and therefore have great learning value.

In addition to the exercises that appear in this book, then, student assignments might consist of writing occasional programs, as well as delivering reports in class on assigned readings. The latter might be found among the references cited in the bibliographies in each chapter.

I am indebted first of all to the students on whom I worked out these ideas, and second to a number of colleagues for their helpful advice and friendly criticism. Among the latter I will mention Richard Brualdi, Daniel Kleitman, Albert Nijenhuis, Robert Tarjan and Alan Tucker. For the no-doubt-numerous shortcomings that remain, I accept full responsibility.

This book was typeset in TEX. To the extent that it’s a delight to look at, thank TEX. For the deficiencies in its appearance, thank my limitations as a typesetter. It was, however, a pleasure for me to have had the chance to typeset my own book. My thanks to the Computer Science department of the University of Pennsylvania, and particularly to Aravind Joshi, for generously allowing me the use of TEX facilities.

Click to Download