LESSON 2

PRELIMINARIES OF ALGORITHM

step-by-step procedure, which defines a set of instructions to be executed

in a certain order

Algorithm

Algorithm to ____an item in a data structure.

Search

Algorithm to ____ items in a certain order.

Sort

Algorithm to _____ item in a data structure.

Insert

Algorithm to _______ an existing item in a data structure.

Update

Algorithm to _______ an existing item from a data structure.

Delete

Algorithm should be clear and ___________. Each of its steps (or

phases), and their inputs / outputs should be clear and must lead to only one meaning.

Unambiguous

An Algorithm should have 0 or more well-defined _______.

Input

An Algorithm should have 1 or more well-defined outputs, and should match

the desired

Output

Algorithms must terminate after a finite number of steps.

Finiteness

Should be feasible with the available resources.

Feasibility

An Algorithm should have step-by-step directions, which should be

independent of any programming code.

Independent

This is a theoretical analysis of an Algorithm. Efficiency of an

Algorithm is measured by assuming that all other factors,

Priori Analysis

This is an empirical analysis of an Algorithm. The selected

Algorithm is implemented using programming language.

Posteriori Analysis

_______ is measured by counting the number of key operations such as

comparisons in the sorting and searching Algorithm.

Time Factor

________ is measured by counting the maximum memory space required

by the Algorithm.

Space Factor

___________ of an Algorithm represents the amount of time required by the Algorithm to run to completion.

Time Complexity

_________ Complexity of an Algorithm represents the amount of memory space required

by the Algorithm in its life cycle.

Space Complexity

Asymptotic Analysis

Refers to defining the mathematical bound of run-time performance.

upper bound; measures Worst Case time complexity.

Big Oh (Ο

Lower bound; measures Best Case time complexity.

Omega (Ω)

Both lower and upper bounds.

Theta (θ)

Recursion

The process in which a function calls itself directly or indirectly.

Example of Recursion

• TOH (Tower of Hanoi)

• Tree Traversals (In-Order / Pre-Order / Post-Order)

• DFS (Depth-First Search)

Informal combination of programming constructs and narrative text.

Pseudocode

Pictorial representation of a procedure using standard symbols.
“Blueprint” of a program.

Flowchart

Flowchart History —— WHO is introduced FLOWCART

Frank Gilbert (1921)

Shows logical steps within a program.

Program Flowchart

shows data procedures and connections.

System Flowchart

Produce ordered sequence of steps (Algorithm).

Problem Solving Phase

Implement the Algorithm in a programming language.

Implementation Phase

• (Addition)
  – (Subtraction)

• (Multiplication)
  / (Division)
  % (Modulus)

Arithmetic Operators

(Equal)

(Greater Than)
< (Less Than)
<> (Not Equal)
= (Greater Than or Equal To)
<= (Less Than or Equal To)

Relational Operators

&& (Logical AND)
|| (Logical OR)
! (Logical NOT)

Logical Operators