Chapter 1: Introduction
Algorithms and Conventions

Read the Preface of the text.

What is an algorithm?

An algorithm is an outline or idea behind a program. Generating an algorithm, itself, is a step-by-step process, getting more specific with each version. It usually starts with a precise statement to solve a problem on a computer but ultimately consists of a sequence of definite instructions to do a certain job. We express algorithms in pseudo-code: something resembling C or Pascal, but with some statements in English rather than within the programming language. It is expected that one could translate each pseudo-code statement to a small number of lines of actual code, easily and mechanically.

From the text we see:

Definition 1.1 [Algorithm]: An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria:

  1. Input. Zero or more quantities are externally supplied.

  2. Output. At least one quantity is produced. (function vs procedure)

  3. Definiteness. Each instruction is clear and unambiguous.

  4. Finiteness. If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.

  5. Effectiveness. Each instruction must be basic so that it can be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in criterion 3; it also must be feasible.

Design of Algorithms

Analysis of Algorithms

Implementation and Program Testing

Pseudocode Conventions

See text for these conventions. They should not be all too surprising as they are similar to most high-level programming syntax rules.

  1. Comments: //
  2. Blocks: {}
  3. Identifiers and Records: Since pseudocode, code is not object-oriented. The use of records is how pre-OO languages grouped information into compound datatypes or structures. Note the use of * to indicate links to other records.
  4. Assignment: <variable> := <expression>
  5. Booleans: true and false
  6. Arrays: A[i,j]
  7. Loops: Use of for,while,repeat-until
  8. Conditionals:
  9. I/O: since pseudocode use read and write rather than specific call
  10. Procedures: Algorithm Name (<paramenter list>)
    Use of return

Algorithm could mean a Function (returned value) or Procedure (no returned value but "side effects" that achieve some purpose).

The book is written with the pseudocode. Note that my notes may contain the Pseudocode conventions or I might accidently fall into Java code. For example, most likely there will be times where I will write code and in assignments not have the colon (:=), or sometimes use an arrow. You are graduate students. Please use your own expertise to comprehend simple slips concerning pseudocode .

Example of Algorithms

Suppose you had the SelectionSort identified in the text (Example1.1). Check out how the text will "walk-through" the conceptualization (Algorithm 1.1 and 1.2)through proof of the algorithm (Thm. 1.1). In addition, the OO code would look something like this:

Recursive Algorithms