Chapter 2

Problem description • Input • Result (output) Algorithm • Pseudocode is fine Program • Java, C, Python Machine instructions (executable)

It’s created from using components of natural language to express algorithms • Pseudocode = “Not real” Code

• Natural language can be extremely verbose • Lack of structure makes it difficult to locate specific sections of the algorithm • Natural language is too “rich” in interpretation and meaning • Not sufficiently precise to represnt algorithms

• Used to design and represent algorithms • A compromise between the two extremes of natural and formal languages • Will not be unique

Sometimes called a straight-line algorithm; the order is followed in a linear fashion.

• Conditional and iterative • Allow us to alter the normal sequential flow of control in an algorithm

• The “question-asking” operations of an algorithm • If/then/else

• The repetition of a block of instructions • While or For loop statement

Determines if statement is true or false • if/elif statements

Continuation condition is tested at the beginning of each pass through the loop

Continuation condition is tested at the end of the loop body, not the beginning.

Instructions that computing agent understands and is capable of executing without further explanation.

• Process of searching for a special pattern of symbols within a larger collection of information. • Is assisting microbiologist and geneticists studying and mapping the human genome.

• Sort the entire list into ascending order. • Attempt to match the entire pattern against the text. • Find a root of the equation.

Use of high-level instructions during the design process

Viewing an operation at a high level of abstraction

Run Time Analysis • Worst Case • Average Case Big Oh • Constant run time O(1) • Logarithmic run time O(logn) • Linear run time O(n) • Linearithmic run time O(nlogn) • Quadratic run time O(n2)

For a sequence of instructions, the cost of executing the sequence of instructions is, asymptotically speaking, the same as the maximum cost of the individual instructions. For three instructions a, b and c: • O({a, b, c}) = max (O(a), O(b), O(c)) where {a, b, c} represents direct sequencing of the three individual instructions.

For a conditional statement, the cost of execution is the maximum of the cost of evaluating the condition and the cost(s) of the alternate instruction sequences • O(if {condition} then {sequence1} else {sequence2}) = max (O(condition), O(sequence1), O(sequence2))

Applies to an iterative construct ( e.g., loop, for, while) that will cause the execution of a subset of instructions to be repeated a specified number of times. The trick is to understand how many times the instructions will be repeated. For k iterations, the general rule is: • O(loop (k) {sequence}) = O(k*sequence)