Analysis and Design of Algorithms

INTRODUCTION TO ALGORITHMS

1. What is analysis?

Analysis: Distinction and separation of the parts of a whole until reaching an understanding of the principles or
elements of this.

Design: Design is defined as the prior process of mental configuration, "pre-figuration", in the
search for a solution in any field. Commonly used in the context of
industry, engineering, architecture, communication, and other creative disciplines.

Algorithm: An algorithm is like an ordered and finite set of operations that allows finding the
solution to a problem.

2. Define Algorithm Analysis and Design.

The analysis and design of algorithms aims to establish properties regarding efficiency.
allowing the comparison between alternative solutions and predicting the resources that will be used by a
algorithm. These estimates turn out to be quite useful in the search for efficient algorithms.

When performing a theoretical analysis of algorithms, it is common to calculate their complexity in

asymptotic non-sense, that is, for a sufficiently large input size. The bound
asymptotic upper bound, and the omega notation (lower bound) and theta notation (average case) are used with that
purpose. For example, we say that binary search executes in a number of steps
proportional to a logarithm, in O(log(n)), colloquially "in logarithmic time". Normally the
asymptotic estimates are used because different implementations of the same algorithm do not
they must have the same efficiency. However, the efficiency of two implementations
"Any reasonable ones" of a given algorithm are related by a multiplicative constant.
hidden constant call.

Exact measures of efficiency are useful for those who truly implement and use them.
algorithms, because they have more precision and thus allow them to know how much time they can assume that
it will take execution. For some people, like video game developers, a
A hidden constant can mean the difference between success and failure.

In software engineering, algorithm design is a specific method to create a

mathematical model adjusted to a specific problem to solve it. The design of algorithms is
a theory of Operations Research.

3. Origin of algorithms

These arose in the mid-9th century by the distinguished mathematician and astronomer Mohammed Ibn
Musa -aljarizm: but we can see that Al_yebr-mugabata is another who developed formulas for
enable that with a limited number of processes it was possible to solve first-degree equations and
second grade.

The history of the algorithm originates from the need to perform mathematical calculations through it.
it underpins the initial step of fully understanding any presented problem.
 Analysis and Design of Algorithms

But let's also keep in mind that algorithms are at the very heart of
computers and that programming languages are just a means of expressing them.

In algorithm theory, we can mention that algorithms began to emerge

approximately throughout history in the 19th century although by this time it was already
certain knowledge of these.

4. Evolution of algorithms

To see the evolution that algorithms have undergone over the years, it is necessary to understand
that these evolved according to the computing needs and the physical architecture of the
computers, various problems require different approaches to solve them
virtually gave rise to the different programming paradigms.

The paradigms of programming are:

Imperative Paradigm

Declarative Paradigm

Structured Paradigm

Object-Oriented Paradigm:

Functional Paradigm

Logical paradigm

Each paradigm has a different approach and is oriented towards a specific group of problems.
the characteristics that these paradigms have are:

Imperative Paradigm: describes programming as a sequence of instructions or commands

that change the state of a program. Machine code is generally based on the
imperative paradigm. Its opposite is the declarative paradigm. This paradigm includes the
procedural paradigm among others.

Declarative Paradigm: It does not rely on how something is done (how a goal is achieved step by step.
step), but rather describes (declares) what something is like. In other words, it focuses on describing the
properties of the sought solution, leaving the algorithm undetermined (set of
instructions) used to find that solution. It is more complicated to implement than the
imperative paradigm has disadvantages in efficiency, but advantages in problem-solving
certain problems.

Structured Paradigm: programming is divided into blocks (procedures and functions) that
they can or cannot communicate with each other. In addition, the programming is controlled with sequence, selection
and iteration. It allows for the reuse of programmed code and provides a better understanding of the
programming. It is contrary to the unstructured paradigm, of little use, which has no
structure, it is simply a 'block', like for example, batch files (.bat).

Object-Oriented Paradigm: it is based on the idea of encapsulating state and operations in

objects. In general, programming is solved by communicating these objects through
 Analysis and Design of Algorithms

messages (message-oriented programming). It can be included (although not formally) within

from this paradigm, the object-based paradigm, which also has inheritance and subtypes between
objects.

Its main advantage is the reuse of codes and its ease of thinking of solutions to
certain problems.

Functional Paradigm: this paradigm conceives computing as the evaluation of functions

mathematics and avoids declaring and changing data. In other words, it emphasizes the application of
the functions and composition between them, more than in the changes of states and execution
sequential commands (as done by the procedural paradigm). It allows solving certain
elegantly solve problems and purely functional languages avoid side effects
common in other types of programming.

Logical paradigm: it is based on the definition of logical rules and then, through an engine of
logical inferences, answer questions posed to the system and thus solve problems.

Example: prologue.

5. Structure of an algorithm

The structure of an algorithm helps to organize the elements that appear in it. All the
algorithms have the same structure, which is defined by three sections:

· Header

· Statements

· Body

Header: The header of an algorithm must indicate the name (identifier) assigned to it.
same. The syntax is: 'Algorithm <algorithm_name>'.

Example:

If one wants to design the algorithm of a program that calculates the area of a circle by
the algorithm must have "algorithm Area_of_a_circle" in the header

Declarations: In this section, the constants, data types, and variables are declared that
they are used in an algorithm. The syntax is as follows:

Constants

<declaration_of_constants>

Data types

data type declaration

Variables

<variable_declaration>
 Analysis and Design of Algorithms

Example:

To solve the problem posed in the previous topic, it is necessary to declare a constant and
two variables

Constants

PI=3.1416

Variables

Real area, radius

Body: In the body, all the instructions of the algorithm are written. The syntax is:

Start

Instruction 1

Instruction n

End

Start and End are reserved words that mark the beginning and the end of the body section.
what is where the main instruction block of the algorithm is.

Example

Start

Write ("enter radius: ")}

Leer (radio)

Area = PI * radius ** 2

Write ("The area of the circle is:", area)

End

Comments. In algorithms, it is advisable to write comments to explain the design and/or

operation of the same.

Example

/* Header */

Algorithm Area_of_a_circle
 Algorithm Analysis and Design

6. Types of algorithms

Qualitative: They are those in which the steps are described using words.

Quantitative: These are the ones in which numerical calculations are used to define the steps of
process.

There are several algorithm design techniques that allow for the development of a solution to the problem.
proposed, some of them are:

Greedy algorithms: they select the most promising elements from the set of
candidates until a solution is found. In most cases, the solution is not optimal.

Parallel algorithms: allow the division of a problem into subproblems in such a way that it
can be executed simultaneously on several processors.

Probabilistic algorithms: some of the steps of this type of algorithms depend on

pseudo-random values

Deterministic algorithms: The behavior of the algorithm is linear: each step of the algorithm
has only one successor and one ancestor.

Non-deterministic algorithms: The behavior of the algorithm takes the form of a tree and at each
the step of the algorithm can branch into any number of immediately subsequent steps,
In addition, all branches are executed simultaneously.

Divide and conquer: they divide the problem into disjoint subsets obtaining a solution of
each of them to later join them, thus achieving the solution to the complete problem.

Metaheuristics: they find approximate (non-optimal) solutions to problems based on

a prior knowledge (sometimes referred to as experience) of them.

Dynamic programming: tries to solve problems by reducing their computational cost

increasing the spatial cost.

Branching and bounding: it is based on constructing solutions to the problem by

an implicit tree that is traversed in a controlled manner finding the best solutions.

Backtracking: the solution space of the problem is built in a tree

that is fully examined, storing the least costly solutions.

7. What is program execution?

It is the execution of the instructions of an exe by the CPU. It is then when the processor
access the machine code of the program and execute its actions sequentially.
 Analysis and Design of Algorithms

8. Cold run of an algorithm (trace of an algorithm).

The trace of an Algorithm can be defined as the manual execution of it sequentially.

statements that compose it. Thus, the trace of the following algorithm is the value that they are taking on.
variables as a program is executed.

The main function of tracing an algorithm is to verify that it

it works correctly or to carry out the debugging stage in which efforts are made to correct errors,
simplify the algorithm to the maximum and increase its efficiency and speed.

In this way, the programmer executes a cold run on the source program by selecting
a set of input data, manually executing each statement of the source program and
checking that the results obtained are as expected according to the dataset
input. As a debugging technique, the programmer must carry out this process using
datasets that allow executing all possible "paths" of the program.

Example: Perform the E-P-S analysis and design an algorithm to calculate the surface area of a
parallelepiped with dimensions l (length), a (width), and h (height).

Encoding:
float Area()
{
float l, h, a, AS;
Length of the parallelepiped =
scanf("%f", &l);
Width of the parallelepiped=
scanf("%f", &a);
Height of the parallelepiped=
scanf("%f", &h);
AS = 2 * (l * a + l * h + a * h);
printf("Surface area of the parallelepiped = %f", AS);
}

Cold running:
l = 3.0
a = 2.5
h = 7.3
AS = 2 x (3.0 x 2.5 + 3.0 x 7.3 +
(2.5 x 7.3) = 95.3
 Analysis and Design of Algorithms

9. Examples of an algorithm.

1- In order for a person to exercise their vote in a government election, they must be of legal age.
age and Costa Rican.

For a person to be able to marry, they must be of legal age and single.

3- Write an algorithm that calculates the hypotenuse of a right triangle, where both legs
they are equal to 5.
 Analysis and Design of Algorithms

4. Determine the discount of an item based on the quantity of units of it. if

If you buy more than 5 items, you get a 5% discount; otherwise, there is no discount.
 Analysis and Design of Algorithms

BIBLIOGRAPHY

Wikipedia (2013). Algorithm Analysis. Available at

http://en.wikipedia.org/wiki/Algorithm_analysis

Wikipedia (2013). Algorithm Design. Available at

http://es.wikipedia.org/wiki/Dise%C3%B1o_de_algoritmos

Müller G. (2008). Class 9. Programming Modular. Available in

http://es.scribd.com/doc/2959783/3/Running-in-cold-of-Main-Algorithm

Acevedo, A. 2010 Algorithmic y Programming. Available in Invalid URL. No text to translate.

algoritmicayprogramacion.blogspot.com/

Rivas A. (2012). Algorithmic and Programming Project. Available at

http://es.scribd.com/doc/33942225/Algorithmic-and-programming-project-1

Gómez, R. (2009). Course on Logic and Algorithms 2009. Available at

The provided text is a URL and does not require translation.

Tadeo, M. (2010). Parts of an Algorithm. Available athttp://am55887.blogspot.com/