Algo Strategies and explaination ppt.pdf

Algorithm classification

1. 1



JSPM's Jayawantrao Sawant College of
Engineering,HADAPSAR,PUNE
Subject :Fundamentals of Data
Structures (SE COMP)
Presented by,

Prof. S. A. SHIVARKAR

2. JSPM's Jayawantrao Sawant College of Engineering









UNIT 1 PART 2

Points to be covered-
Algorithmic Strategies-
Introduction to algorithm design strategies-
Divide and Conquer , Greedy strategy.

3. • In a broad sense, many algorithms approach
problems in the same way.
• Thus, it is often convenient to classify them
based on the approach they employ.
• One reason to classify algorithms is to gain an
insight about an algorithm and understand its
general approach.
• This can also give us ideas about how to look
at similar problems for which we do not
know algorithms.
• Of course, some algorithms defy classification,
whereas others are based on a combination of
approaches.

General Approaches in Algorithm Design:

4. Randomized algorithms rely on the statistical
properties of random numbers.

One example of a randomized algorithm is quicksort.
Example:
Imagine an unsorted pile of cancelled checks by hand.
In order to sort this pile we place the checks numbered
less than or equal to what we may think is the median
value in one pile, and in the other pile we place the
checks numbered greater than this. Once we have the
two piles, we divide each of them in the same manner
and repeat the process until we end up with one check
in every pile. At this point the checks are sorted.
Randomized Algorithms:

5. • Divide-and-conquer algorithms revolve around 3
steps: divide, conquer and combine.

• In the divide step, we divide the data into
smaller, more manageable pieces.

• In the conquer step, we process each division
by performing some operations on it.

• In the combine step, we recombine the
processed divisions. An example of the divide-
and conquer algorithm is merge sort.
Divide-and-Conquer Algorithms:

6. As before, imagine an unsorted pile of
cancelled checks by hand. We begin by
dividing the pile in half. Next, we divide each of
the resulting two piles in half and continue this
process until we end up with one check in
every pile. Once all piles contain a single
check, we merge the piles two by two so that
each pile is a sorted combination of the two that
were merged. Merging continues until we end
up with one big pile again, at which point the
checks are sorted.
Example:

7. Dynamic-programming solutions are similar to divide-and
conquer methods.

In that both solve problems by breaking larger problems into
sub-problems whose results are later recombined.

However, the approaches differ in how sub-problems are
related.

In divide-and-conquer algorithms, each sub-problem is
independent of the others. Therefore we solve each sub-
problem using recursion and combine its results with the
results of other sub-problems.
Dynamic-programming solutions:

8. A dynamic-programming solution is better than a divide-and
conquer approach because the latter approach will do more
work than necessary, as shared sub-problems are solved
more than once.

However, if the sub-problems are independent and there is no
repetition, using divide-and-conquer algorithms is much
better than using dynamic-programming.

Example

Finding the shortest path to reach a point from a vertex in a
weighted graph.
In dynamic programming solutions, sub-problems are not
independent of one another.

9. • Greedy algorithms make decisions that look best at the moment.

• In other words, they make decisions that are locally optimal in the
hope that they will lead to globally optimal solutions.

• The greedy method extends the solution with the best possible decision
at an algorithmic stage based on the current local optimum and the best
decision made in a previous stage.

• It is not exhaustive, and does not give accurate answer to many
problems. But when it works, it will be the fastest method.

• Example :

• Huffman coding, which is an algorithm for data compression.
• Prim’s & Kruskal’s Algorithm,
Greedy Algorithms:

10. Approximation algorithms are algorithms that do
not compute optimal solutions; instead, they
compute solutions that are “good enough”.

Often we use approximation algorithms to solve
problems that are computationally expensive but
are too significant to give up altogether.

Example:
The travelling salesman problem using an
approximation algorithm.
Approximation Algorithms: