Properties of an algorithm

“An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.” (Rosen, p. 120)

Input – An algorithm has input values from a specified set

Output – From each set of input values an algorithm produces output values from a specified set. the output values are the solution to the problem.

Definiteness – The steps of an algorithm must be defined precisely.

Correctness – An algorithm should produce the correct output values for each set of input values.

Finiteness – An algorithm should produce the desired output after a finite (but prehaps large) number of steps for any input in the set.

Effectiveness – It must be possible to perform each step of an algorithm exactly and in a finite amount of time.

Generality – The procedure should be applicable for all problesm of the desired form, not just for a particular set of input values.

An algorithm is an unambiguous set of instructions for determining the solution to a problem in a finite amount of time using a finite amount of space. (Adams)

Well-known computer science algorithms

Searching

linear search

binary seach

ternary search

Sorting

bubble sort

insertion sort

selection sort

shell sort

binary insertion sort

quicksort

topological sort

Graph/Tree Traversals

preorder

inorder

postorder

depth first search

breadth first search

Greedy algorithms

shortest path

Dijkstra’s

Others

MatrixMultiplication

Euler Path

Euclidean

Huffman

Washall

Strategies

divide and conquer

greedy

recursive

A statement or proposition is a sentence that is either true or fals

Binary logical connectives

and - conjunction - conjuncts

or - disjunction - disjuncts

implication – antecedent consequent

equivalence

Unary logical connective

not

Truth tables