Algorithms

by Sedgewick Robert

We should not use an algorithm without having an idea of what resources it might consume, so we strive to be aware of how our algorithms might be expected to perform.

A method can call itself (if you are not comfortable with this idea, known as recursion, you are encouraged to work EXERCISES 1.1.16 through 1.1.22).

When using an ADT, we focus on the operations specified in the API and pay no attention to the data representation; when implementing an ADT,

Objects are characterized by three essential properties: state, identity, and

behavior.

The primary purpose of static methods is to implement functions; the primary purpose of non-static (instance) methods is to implement data-type operations.

Bags, queues, and stacks

In particular, a classic data structure known as the linked list enables implementation of bags, queues, and stacks that achieve efficiencies not otherwise possible. Understanding linked lists is a key first step to the study of algorithms and data structures.

FIFO queue (or just a queue) is a collection that is based on the first-in-first-out (FIFO) policy.

Push operands onto the operand stack. • Push operators onto the operator stack. • Ignore left parentheses. • On encountering a right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands.

Dijkstra’s Two-Stack Algorithm for Expression Evaluation

Java uses the type parameter Item to check for type mismatch errors—even though no concrete type is yet known, variables of type Item must be assigned values of type Item, and so forth.

loitering.

We now have two ways to represent collections of objects, arrays and linked lists. Arrays are built into Java; linked lists are easy to build with standard Java records. These two alternatives, often referred to as sequential

In approaching a new applications domain, we identify computational challenges and use data abstraction to address them, proceeding as follows: • Specify an API. • Develop client code with reference to specific applications. • Describe a data structure (representation of the set of values) that can serve as the basis for the instance variables in a class that will implement an ADT that meets the specification in the API. • Describe algorithms (approaches to implementing the set of operations) that can serve as the basis

for implementing the instance methods in the class. • Analyze the performance characteristics of the algorithms.

Observe some feature of the natural world, generally with precise measurements. • Hypothesize a model that is consistent with the observations. • Predict events using the hypothesis. • Verify the predictions by making further observations. • Validate by repeating until the hypothesis and observations agree.

To allow us to ignore insignificant terms and therefore substantially simplify the mathematical formulas that we work with, we often use a mathematical device known as the tilde notation (~).

The quicksort algorithm’s desirable features are that it is in-place (uses only a small auxiliary stack) and that it requires time proportional to N log N on the average to sort an array of length N. None of the algorithms that we have so far considered combine these two properties.

quick sort conditions

• The entry a[j] is in its final place in the array, for some j. • No entry in a[lo] through a[j-1] is greater than a[j]. • No entry in a[j+1] through a[hi] is less than a[j]. We achieve a complete sort by partitioning, then recursively

When the scan indices cross, all that we need to do to complete the partitioning process is to exchange the partitioning item a[lo] with the rightmost entry of the left subarray (a[j]) and return its index j.