Transcript Algorithms

Fundamentals of Algorithmic
Problem Solving
 Algorithms are not answers to problems
 They are specific instructions for getting answers
 This emphasis on defining precise constructive
procedures is what makes computer science
distinct from other many other disciplines
 The design of algorithms typically has several
steps
 Understanding the problem
 Ascertaining the capabilities of a computational
device
 Choosing between exact and approximate problem
solving
 Deciding on appropriate data structures
© Ronaldo Menezes, Florida Tech
Connectivity Problem
 Let's consider the following problem:
 Given a sequence of pairs of integers of the form (pq) write an algorithm that would input a sequence of
pairs and tell whether a pair is redundant.
 (p-q) means that p is connected to q, and vice-versa (the
connection relation is transitive)
 A pair (p-q) is said to be redundant iff p is connected
to q via some N number of other integers, N>=0
 The algorithm must therefore remember the
pairs it has seen (or information related to the
pairs) so that it can answer if a given pair is
redundant.
© Ronaldo Menezes, Florida Tech
Sample Output
© Ronaldo Menezes, Florida Tech
Connectivity Applications
 Networks
 Integers may represent machines and our problem
is to find whether two machines need to be
connected
 Same applies to other kids of networks such as Social
Networks.
 Integers may represent points in a electric network
grid and we want to find out whether the pairs
(wires) are sufficient to connect all points in the
network
 VLSI
 In the design of integrated circuits integers may
represent components and we want to avoid the
use of redundant connection between the
components.
© Ronaldo Menezes, Florida Tech
Connectivity Applications
 Programming Languages
 Some languages have the concept of
aliases. Integers may represent the variable
names and the pairs represent the fact the
two variable names are equivalent.
 Graph Theory
 Pairs represent edges and integers
represent nodes. We might want to find out
the degree of connectivity of the graph.
© Ronaldo Menezes, Florida Tech
Large Connectivity Example
(from Sedgewick’s book)
© Ronaldo Menezes, Florida Tech
Expressing a Algorithm
 Our first task is to think about what is required from
the problem statement.
 That is, we need to know what the algorithm needs to
answer.
 It is normally the case that the complexity of the
problem is directly proportional to the complexity of
the algorithm.
 Although complex problems may have a very simple
algorithm
 In the connectivity case, one needs to answer only a
binary question: given a pair of integers, are they
connected already (yes/no)?
 Note that the problem does not require us to demonstrate
the path in the case of a positive answer.
 In fact the addition of this requirement would make the
problem much more© Ronaldo
complex.
Menezes, Florida Tech
Expressing a Algorithm
 One could also ask for “less” information:
 Are M connections sufficient to fully connect
N objects together?
 Note that we're are not asking anything about
specific pairs.
© Ronaldo Menezes, Florida Tech
Fundamental Operations
 When designing an algorithm it is worth spending
some time thinking about the fundamental operations
that the algorithm needs to perform.
 For the connectivity problem we could have that for every
given pair
 One has to find whether the pair represents a new connection
between the two objects
 If it does, then we need to incorporate the information about the
new connection (in a data structure) so that future searches can
be answered correctly
 The above can be abstractly represented using a set.
 The input represents elements in a set. The problem then is
to:
 Find whether a set contains a given items in the pair.
 Replace the sets containing the two given items with their union
set.
© Ronaldo Menezes, Florida Tech
Self-test Exercise
 Exercise 1
How can we solve the connectivity problem using the
abstract operations described in the previous slide?
Sketch an algorithm based on the following
description:
 We can use a set S to represent the connected elements
 When we read a pair (p-q) we check whether they (both)
are elements of the set
 If they are, we don't print the pair (they are already connected).
 If they are not we then make: S U {p,q}.
© Ronaldo Menezes, Florida Tech
How good is good enough?
 As a rule of thumb we strive for finding efficient
algorithms. But there various are factors you should
consider:
 Very important factors:
 How often are you going to need the algorithm?
 What is the typical problem size you're trying to solve?
 Less important factors that should also be considered:
 What language are you going use to implement your algorithm?
 What is the cost-benefit of an efficient algorithm?
 One of the best quotes I know about design (in
general) is from Antoine de Saint-Exupéry:
 “A designer knows he has arrived at perfection not when
there is no longer anything to add, but when there is no
longer anything to take away”
© Ronaldo Menezes, Florida Tech
Simplicity is Very Desirable
 Independently of how good your algorithm
needs to be, you should always try to fully
understand the problem
 A good understanding exercise is the design of a
very simple algorithm that does the job.
 A simple (and correct) algorithm may also be
useful as the basis for testing a more sophisticated
algorithm.
 A simple approach (that some of you may
have tried for the connectivity problem) could
be:
 Use a data structure to store all (needed) pairs.
 For any new pair (p-q), search the data structure
and try to build a path from p to q.
© Ronaldo Menezes, Florida Tech
Brute Force
 Brute force is a straightforward approach to solving a
problem usually directly based on the problem's
statement and on the definitions of the concepts
involved
[Levitin 2003]
 It is considered a design strategy although the strategy
is simply: just do something that works!
 As an example consider the exponentiation problem


Compute an for a given number a and a nonnegative integer n.
The brute force approach consists of:

Can you calculate an using less then (n-1) multiplications?
© Ronaldo Menezes, Florida Tech
Uses of Brute Force
 The brute force design technique rarely yields
efficient algorithms.
 But it does have a few advantages:
 Brute force algorithms are normally more general.
 In fact it is normally difficult to point out problems that a bruteforce approach cannot tackle.
 Most elementary algorithmic tasks use brute force
solutions.
 e.g. Calculating the sum of a list of numbers; finding the max
element in a list.
 The solutions are normally reasonable for practical instances
sizes.
 A simple (correct) solution may serve as
 the basis for testing more sophisticated solutions.
 as a yardstick with which to judge more efficient alternatives for
solving the problem – a benchmark.
© Ronaldo Menezes, Florida Tech
The Brute-force Approach to The
Connectivity Problem
 Let’s go back to the brute force approach
to the connectivity problem we mentioned
earlier
 It may not be considered an algorithm
because:
 How big does the data structure to save all
pairs need to be?
 No obvious solution for building the path
comes to mind.
© Ronaldo Menezes, Florida Tech
Union-Find Algorithm
 If we want to solve the connectivity problem
based on union-find operations we must:
 Define a data structure to represent the set(s)
 The quick-find solution (as defined by Sedgewick's) uses
an array of size N where N is the number of objects in the
connectivity problem. Let's called it id
 The value of the id[i] object is initialized with the value
i.
 Define the union operation
 Two objects (p and q) are said to belong to the same set
(therefore connected) iff
id[p] == id[q]
 Union is defined by changing all entries in the array with
value equal to id[p] to id[q]
© Ronaldo Menezes, Florida Tech
View of Quick-Find
id
© Ronaldo Menezes, Florida Tech
Quick-find solution to the
connectivity problem
public class QuickF {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
int id[] = new int[N];
for (int i = 0; i < N ; i++)
id[i] = i;
for( In.init(); !In.empty(); ) {
int p = In.getInt(), q = In.getInt();
int t = id[p];
if (t == id[q]) continue;
for (int i = 0; i < N; i++)
if (id[i] == t) id[i] = id[q];
Out.println(" " + p + " " + q);
}
}
}
© Ronaldo Menezes, Florida Tech
How good is Quick-Find?
 Property 1.1
The quick-find algorithm executes at least MN
instructions, where N is the number of objects and M
is the number of unions.
For each union operation the internal for-loop has to
traverse the entire array
 This seems a reasonable algorithm but if M and N
are large, the algorithm does not perform that well.
 Can we do better?
 The algorithm we saw earlier is a union-find algorithm
where the find operation is fast but the union is slower.
 Let's look at a solution that uses the same abstraction but
with a different interpretation for the values stored in the
array.
© Ronaldo Menezes, Florida Tech