Fundamentals of OOP and Data Structures in Java - Part3

Couple of Days back i started reading Fundamentals of OOP and Data Structures in Java By Richard Wiener and Lewis J. Pinson

Below are few quotations i found from this book from the next 3 chapters (8-10).

1) An essential and important part of computer problem solving is the development of algorithms –the detailed logic and steps required to solve a problem. All programmers are introduced very early to a number of useful programming constructs for building algorithms. These include assignment, branching, and iteration. Branching provides a means for conditional or alternative execution of steps in an algorithm. Iteration provides a convenient way to perform repetitive steps. Without branching and iteration the algorithms for even simple problem solutions would be either impossible or verbose and cumbersome. Another useful concept for construction of algorithms is recursion. Recursion is a construct that provides an alternative to iteration for repetitive steps. In many problems requiring repetitive steps we may find
equivalent iterative and recursive algorithms as solutions.

2) Recursive algorithms provide an alternative way to represent repetitive steps in a problem solution instead of iteration. A well-behaved recursive function, algorithm, or implementation satisfies the following three essential properties

a) Recursion essential property #1 –A recursive function, algorithm, or implementation is defined in terms of itself.

b) Recursion essential property #2 –A recursive function, algorithm, or implementation must have a sentinel
parameter. The recursion continues or stops conditional on the value of this sentinel parameter.

c) Recursion essential property #3 –A recursive function, algorithm, or implementation must drive the value of its sentinel parameter in a way to eventually stop the recursion.

3) The complexity of a recursion depends on the degree (number of recursive calls in its implementation) and, to a lesser extent, on the relative location of the recursive call(s). Single recursions may be tracked using a simple graphical technique. Double recursions may be tracked using a graphical binary tree structure.

4) Many algorithms have both iterative and recursive solutions.

5) • In object-oriented languages, the class provides an excellent logical unit for encapsulating an abstract data type (ADT) and its operations.

6) ADTs provide a convenient conceptual framework for data structures that are presented in following chapters.

7) A stack is a container with the following properties:

a) A stack has order that is a property of the stack itself, independent of the objects it contains. Order of the objects in a stack depends on the sequence in which they are inserted or removed. The ordering relationship is characterized as first in, last out or last in, first out.

b) Access to the stack is restricted to one location called the top. We may push (add) a new object onto the top, pop (remove) the object on the top, or query the top object without removing it.

8) A queue is a container with the following properties:

a. A queue has order that is a property of the queue itself, independent of the objects it contains. Order of the objects in a queue depends on the sequence in which they are inserted or removed. The ordering relationship is characterized as first in, first out or last in, last out.

b. Access to the queue is restricted to two locations called the front and rear. We may add a new object at the rear,remove the object at the front, or query the front object without removing it.

9) Container is the top-level container interface. It provides only those commands and queries that may be used without modification by all container types.

10) Stack is a simple linear container of objects. It exhibits first-in, last-out behavior.

11) Queue is a simple linear container of objects. It models a waiting line with first-in, first-out
behavior.

12) A List is a linear container that allows access, addition, and removal of objects at both ends. An IndexableList is a List that also allows access, addition, and removal of objects at a specified index location. A PositionableList is a List that allows access, addition, and removal of objects before or after a specified object in the list.

13) A BinaryTree is a nonlinear container of objects. Its structure consists of binary nodes that may have, at most, two descendants that are also binary trees.

14) A Heap is a special binary tree that shares none of the specific behavior that applies to general Binary Tree containers.It is a ''complete" binary tree that also satisfies the heap property (the object contained in a node is less than or equal to the contents of nodes in its descendants).

15) A PriorityQueue is a container of Comparable objects. It has the property that the highest priority object is always removed next.

16) A SearchTable is a container whose contained objects must be Comparable . The ability to test for containership and to get a contained object is part of the behavior of a SearchTable. Duplicates are optionally disallowed in our SearchTable.

17) A Dictionary is a container of pairs, that is, instances of Association. Its behavior is characterized by accessing, adding, and removing elements based on the keys. An OrderedDictionary is a dictionary whose elements are ordered by keys. Its contained objects must be Comparable , making an OrderedDictionary a kind of SearchTable.Duplicates are optionally disallowed in our Dictionary and OrderedDictionary.

18) A Set is a container of objects with the strict behavior that duplicates are not allowed. The behavior of a Set is consistent with mathematical sets.


About the Author

Richard Wiener is Associate Professor of Computer Science at the University of Colorado at Colorado Springs and Editor-in-Chief of The Journal of Object-Oriented Programming. He is the author or co-author of twenty-one textbooks and professional books. In 1983 Richard Wiener received the Outstanding Teacher of the Year Award from the University of Colorado at Colorado Springs. His areas of research include object-oriented software development,simulated annealing and genetic algorithms, time series, and applied statistics.

Lewis J. Pinson is President of CIC and Associate Professor of Computer Science at the University of Colorado at Colorado Springs. His areas of expertise include computer software development, object-oriented problem solving,genetic algorithms, and complexity studies. He develops and presents training courses and intensive short courses and workshops on object-oriented problem solving and object-oriented languages. Dr. Pinson has authored or co-authored eight books.