DATA STRUCTURES

and ALGORITHMS
Bachelor's Degree in Computer Science

DESIGN TECHNIQUES OF
ALGORITHMS
 Data Structures and Algorithms

Algorithm Design Techniques

Algorithmics studies the properties of algorithms, and
helps us choose the most suitable solution in each
situation.
A good choice can lead to saving time and
money, and even making the difference between being able or not
to be able to solve a problem.

The 'techniques' or 'schemes'

of algorithm design are
tools that facilitate the
program development.
 Data Structures and Algorithms

Algorithm design techniques

Divide and Conquer

Greedy Algorithms

Dynamic Programming

Backtracking

Branch and Bound

 Data Structures and Algorithms

Divide and Conquer

This technique consists of solving a
problem arising from the solution of
subproblems of the same type, but of
smaller size, until reaching
sufficiently subproblems
small to be solved
directly.
It is a method of progressive refinement.
 Data Structures and Algorithms

Divide and Conquer

General Outline

1. The problem is decomposed into subproblems

smaller size.

All subproblems are solved

regardless, directly if they are

elementary or in a recursive form.

3. The solutions obtained in the step are combined.

previous to building the solution of the problem

original.
 Data Structures and Algorithms

Divide and Conquer

Iterative Scheme

you will overcome (p: problem)

divide(p, p1, p2, ..., pk)

for i = 1, 2, ..., k
si=resolver(pi)

solution = combine(s1, s2, ..., sk)

 Data Structures and Algorithms

Divide and Conquer

Recursive Scheme
divide_will_overcome (p, q: index)
var m: index

small(p, q)
solucion =solucion_directa(p, q)

in another case
m = divide(p, q);
solucion =combinar
(divide_you_will_win (p, m),
divide_venceras (m+1, q);
 Divide and Conquer
MergeSort
MergeSort (i, j: integer)
It is small if the size is less than a base case.
if small(i, j)
DirectOrder(i, j)
in another case
The original array is split into two pieces of equal size (or as close as possible)
possible), that is to say n/2 y n/2 */
s = (i + j) divided by 2

/* Recursively resolve the subproblems */

MergeSort(i, s)
MergeSort(s+1, j)
Merge two sorted lists. In O(n)
Combine (i, s, j)

Youtube: Merge-sort with Transylvanian-saxon (German) folk dance

 Data Structures and Algorithms

Greedy Algorithms, Greedy or

Greedy
They build the solution to a problem in
successive stages, always trying to take
the optimal decision for each stage.

They are commonly used in problems of

optimization, where a solution is
formed by a set of elements among
a set of candidates (with an order
determined or not.
 Data Structures and Algorithms

Greedy Algorithms
Greedy
Estos algoritmos funcionan por pasos:
Be part of an empty solution.
At each step, the next element is chosen.
among the candidates, to add to the solution.
Once this decision is made, it cannot be undone.
undo.
The algorithm will end when the set of
selected elements constitute a
solution.
 Data Structures and Algorithms

Greedy Algorithms
General Outline
VoraciousFunction(C:set):set;
C is the set of candidates
S The solution is built in the set S
while C ≠ y no solution(S) do
x select(C)
C C–{x}
sifactible(SՍ{x})entonces
S SΣ{x}
If S is the solution, then return S
but there is no solution
At each step, there are the following sets:
Selected candidates for solution S.
Selected candidates but rejected later.
Pending candidates for selection C.
 Data Structures and Algorithms

Greedy Algorithms
Components

Set of candidates, problem entries.

Function solution. Check, at each step, if the current subset of

elected candidates form a solution (whether it is optimal or not).

Deselect function. It reports which is the most promising element of

set of pending candidates. This cannot have been chosen with
previousness. Each element is considered only once. Then, it may be
rejected or accepted and will belong to the solution.

Feasibility function. It informs whether a set can lead to

a solution. It applies to the set of selected elements combined with the
most promising element.

Objective function. Indicate if it is possible to do so starting from the set of candidates C.

build a solution (possibly adding other elements). It is that
what is to be maximized or minimized, the core of the problem.
 Data Structures and Algorithms

Greedy Algorithms
Example

Coin change problem

Given a monetary system of length n and a
amount of change, return a solution (if it exists)
that indicates the number of coins equivalent to
change, that is, to show the change P from
coins of the system.

Given a monetary system that contains coins of value 10, 6, 5, and 1 and the
the amount that is desired to change is, for example, P=18 : How is it composed of
solution regarding the quantity of coins and their values?
 Data Structures and Algorithms

Greedy Algorithms
Example
Initial candidates: all types of available currencies. Value coins
10, 6, 5 and 1
Solution: set of coins that total the amount P.
A solution will be of the form (x1, x2, x3, x4) dondexIit is the number of coins
of the type. It is supposed that the currency is worthi.
Functions:
solution. The present value will be a solution if xi·ciP checks if the value of
the selected coins so far are exactly the value that there is
what to pay.
objective. The function to be minimized is xithe resulting number of coins.
Count the set of coins used in the solution.
select. Choose the highest value coin possible at each step, but
less than the value that remains to be returned.
feasible. A set of coins is feasible if its total value does not exceed the
amount to be paid.
Instead of selecting coins one by one, integer division can be used and
Choose all possible coins of higher value.
 Data Structures and Algorithms

Greedy Algorithms
Example

Change return (P: integer; C: array [1..N] of integer;

var X: array [1..N] of integer);
cambio = 0
for i = 1,2,...,N
X[i] = 0
while act P
j = the largest element of C such that C[j] (P - change)
if j=0 then { If that element does not exist }
There is no solution.
X[j] = (P - change) div C[j]
change = change + C[j]*X[j]
 Data Structures and Algorithms

Greedy Algorithms
Applications

Prim's and Kruskal's algorithms:

They find an expansion tree or of
minimum covering in a graph
wired (house wiring)

Dijkstra's algorithm: Finds the

minimum path between pairs of nodes
 Data Structures and Algorithms

Dynamic Programming
Divide and Conquer splits the problem into
independent subproblems, combining
the solutions to solve the problem
original.

It is a somewhat inefficient alternative if the

subproblems are not independent,
Well, the calculation process is repeated.

Dynamic Programming
 Data Structures and Algorithms

Dynamic Programming
Solve subproblems only once.
storing their solutions in a
table for its future use.

It is an ascending technique, although

solutions can be proposed
descendants, recursive.
 Data Structures and Algorithms

Dynamic Programming
General Scheme

1. Cacharacterize the structure of a solution

optim a.

[Link] (recursivamente) el valor de una

optimal solution.

3. Calcular e l valor de u n a solució n óptIma a

pto rise de soluyes ones parcia the s almathis nadas.

4. Build the optimal solution from the

stored information.
 Data Structures and Algorithms

Dynamic Programming
Fibonacci sequence

0,1,1,2,3,5,8,13,21,34,55,89…..

described by Fibonacci as the solution to a problem

from rabbit breeding:

A certain man had a couple of rabbits together in a

closed place and wanted to know how many are created at
from this pair, in a year, when it is its nature
give birth to another pair in a simple month, and in the second month the
born to give birth too
 Data Structures and Algorithms

Dynamic Programming
Fibonacci sequence

By counting the number of distinct letters in each month, one can know the amount
of total couples that exist up to that month.
 Data Structures and Algorithms

Dynamic Programming
Fibonacci - Recursive Solution

Fibonacci (N)
If N = 0
Fibonacci ← 0 // Base Case
else
If N = 1
Fibonacci←1 // Caso Base
else
Fibonacci ← Fibonacci (N-1) +
Fibonacci (N-2)

Complexity O(cte)n )
 Data Structures and Algorithms

Dynamic Programming
Fibonacci - Iterative Solution
#include<stdio.h>
#define MAX 10
main()
{int i; int fib[MAX];
fib[0]=1;
fib[1]=1;
for(i=2;i< MAX; i++)
{
fib[i] = fib[i-1] + fib[i-2];
}
}

Complexity O(n)
 Data Structures and Algorithms

Dynamic Programming
Applications

Warshall's algorithm: finds the

path matrix of a graph G, to
starting from its adjacency matrix

Floyd's algorithm: finds the matrix

of minimum paths of a graph G, to
starting from its weight matrix
 Data Structures and Algorithms

Backtracking
The goal is to find
solutions for some problem, they
achieve by building solutions
partials.
It resembles a journey in
depth within a directed graph.
It especially applies to problems of
optimization.
 Data Structures and Algorithms

Backtrack
General Scheme
1. As the journey progresses, they go

building partial solutions (n-tuple)

If you reach a sheet and the solution is not
complete the route is not successful and return
back
3. Remove the last element from the tuple

4. Try to build the solution by adding another

different element
If a sheet is reached that is a solution
the journey has been successful
6. If only a solution is sought, the algorithm ...

stops
7. Otherwise, a Backtrack is performed
 Data Structures and Algorithms

Backtracking

Partial solutions limit the

regions in which to find a
complete solution.
The journey is successful, proceeding
in this way, it can be defined by
I complete a solution.
 Data Structures and Algorithms

Backtracking
The journey has no success if there is none.
the stage of the partial solution cannot be
complete.
In a situation of success, the journey
go back. If you return to a node that
it has one or more unexplored neighbors,
continue the course of a solution.
 Data Structures and Algorithms

Backtracking
Applications

LabyrinthGiven a maze, the problem consists

in designing an algorithm that finds a path,
if it exists, to go from the entrance to the exit.

Map coloring: Given a map, can you

color their regions or countries in such a way that
there are no adjacent regions or countries of equal
color?

Graph recognition: Given two graphs, the

the problem consists of determining if both are
equal.
 Data Structures and Algorithms

Branching and Pruning

Branch and Bound

Like Backtrack, it carries out a

partial enumeration of the space of
solutions based on generation
from an expansion tree.
It is a variant of the Return method
Back, and it generally applies to
optimization problems.
 Data Structures and Algorithms

Branching and Pruning

General Outline

1. Selection: select the live node that will be

branched (will depend on the strategy)
2. Branching: the children of the node are generated.
selected (only promising tuples)
3. Calculation of quotas: For each node, a quota is calculated.
quota of the possible best value achievable from that
node
[Link]: the nodes generated in the stage are pruned.
previously that will not lead to a better solution
that the best known so far.
 Data Structures and Algorithms

Branching and Pruning

Unlike Backtrack, the
generation of tree nodes
expansion is carried out according to different
strategies:
Breadth-first traversal: FIFO strategy
In-depth walk-through: LIFO strategy
Use a cost function to select the
node that initially seems more promising:
Minimum Cost Strategy
 Data Structures and Algorithms

Branching and Pruning

A pruning strategy is implemented,

in which at each node it is calculated
a note of the possible value of
those solutions that could
meet later in the
tree.
 Data Structures and Algorithms

Branching and Pruning

Application

The Traveling Merchant:

Starting from knowing the distances between
a certain number of cities, a traveler
must start from one of them, visit each
city exactly once, and return to the
starting point, having traveled in
total the shortest possible distance.

Youtube: EST-C7_AxPi - Cap 2 (2) - Posibilidades -

Traveling Salesman [Link]
 Data Structures and Algorithms

Branching and Pruning

Application

The plumber with fines:

Starting from pending tasks, each of
they with a duration (the days it takes to
to be carried out), a deadline, and a penalty in case
that it is not executed within the deadline
established for him. It is requested to determine the date
at the beginning of each of the jobs for
that the total fine is minimal.
 References
Brassard, G.; Bratley, P. Fundamentals of Algorithmics. (2000).
Prentice Hall.

Guerequeta, Rosa; Vallecillo, Antonio. (1998) Techniques of

Algorithm Design. Publications Service of the
University of Málaga.
[Link]

Lee R. C. T., Tseng S. S., Chang R. C., Tsai Y. T. (2007).

Introduction to the design and analysis of algorithms. A
strategic approach. McGraw Hill Iberoamericana.