Algorithm Design and Analysis (Justo)

Introduction

There are compelling reasons to study algorithms. To put it simply, computer programs would not exist without algorithms. And with computer applications becoming indispensable in almost all aspects of our professional and personal lives, studying algorithms becomes a necessity for more and more people.

Another reason for studying algorithms is their usefulness in developing analytical skills. After all, algorithms can be seen as special kinds of solutions to problems, not answers but precisely defined procedures for getting answers. Consequently, specific algorithm design techniques can be interpreted as problem solving strategies that can be useful regardless of whether a computer is involved.

Activity Details

The term algorithm can be defined using any of the following statements:

• An algorithm is a set of rules for carrying out calculation either by hand or on a machine.
• An algorithm is a finite step-by-step procedure to achieve a required result.
• An algorithm is a sequence of computational steps that transform the input into the output.
• An algorithm is a sequence of operations performed on data that have to be organized in data structures.
• An algorithm is an abstraction of a program to be executed on a physical machine (model of Computation).
• The most famous algorithm in history dates well before the time of the ancient Greeks: this is the Euclid’s algorithm for calculating the greatest common divisor of two integers.

The “analysis” deals with performance evaluation (complexity analysis). We start with defining the model of computation, which is usually the Random Access Machine (RAM) model, but other models of computations can be use such as PRAM. Once the model of computation has been defined, an algorithm can be describe using a simple language (or pseudo language) whose syntax is close to programming language such as C or java.

Algorithm’s Performance

Two important ways to characterize the effectiveness of an algorithm are its space complexity and time complexity. Time complexity of an algorithm concerns with determining an expression of the number of steps needed as a function of the problem size. Since the step count measure is somewhat rough, one does not aim at obtaining an exact step count. Instead, one attempts only to get asymptotic bounds on the step count.

Asymptotic analysis makes use of the O (Big Oh) notation. Two other notational constructs used by computer scientists in the analysis of algorithms are Θ (Big Theta) notation and Ω (Big Omega) notation. The performance evaluation of an algorithm is obtained by tallying the number of occurrences of each operation when running the algorithm. The performance of an algorithm is evaluated as a function of the input size n and is to be considered modulo a multiplicative constant.

The following notations are commonly use notations in performance analysis and used to characterize the complexity of an algorithm.