Fundamental of algorithm problem solving

Objective

⮚What is an Algorithm
⮚Steps in Designing and Implementing an
Algorithm
⮚Important Problem Types
⮚Fundamental Data Structures
 2

ALGORITHM

A sequence of unambiguous instructions for

solving a problem, i.e. for obtaining the
required output for any legitimate input in
a finite amount of time
Recipe for a dish
3

Important points

• Non-ambiguity
 • Range of inputs
• The same algorithm can be represented in
different ways

Several algorithms for solving the same problem

 4
Example : gcd(m,n) m,n : non negative ,not both Zero integers

Consecutive integer checking algorithm for computing gcd(m,

n) Step 1 Assign the value of min{m, n} to t.
Step 2 Divide m by t. If the remainder of this division is 0, go to Step 3; otherwise,
go to Step 4.
Step 3 Divide n by t. If the remainder of this division is 0, return the value of t as
the answer and stop; otherwise, proceed to Step 4.
Step 4 Decrease the value of t by 1. Go to Step 2.
60/12 ==0
Gcd(60,24) t =24 60/24 != 0
t=12
60/23 !=0
..
Try gcd(24,0) :will not work on zero

5
Example : gcd(m,n) m,n : non negative ,not both Zero integers

6
Example : gcd(m,n) m,n : non negative ,not both Zero integers

gcd(m, n) = gcd(n, m mod n)

gcd(60, 24)
= gcd(24, 12)
= gcd(12, 0)
= 12.

7
sieve of Eratosthenes (prime No)
The algorithm starts by initializing a list of prime candidates with consecutive
integers from 2 to n

8
ALGORITHM Sieve(n)
//Implements the sieve of Eratosthenes
//Input: A positive integer n > 1
//Output: Array L of all prime numbers less than or equal to n

if p is a number whose multiples are eliminated on the

current pass, then the first multiple we should consider is p
. p because all its smaller multiples 2p, . . . , (p − 1)p have
been eliminated on earlier passes through the list.

p should not be greater than n, and therefore p cannot

exceed √n using the so-called floor function).

n=11 = 3 P=2 ,A[2] !=0, J=2*2 =4 4<=11, A[4]=0,j=4+2=6

L= ( 2,3,5,7,11)
6<=11 , A[6] =0,j=6+2=8
8<=11,A[8]=0,j=8+2=10
 10<=11,A[10]=0,j=10+2=12
P=3,A[3] !=0 ,j=3*3=9 9<=11,A[9]=0,j=9+3=12 9

Play Time
Locker doors
There are n lockers in a hallway, numbered sequentially from 1 to n. Initially, all
the locker doors are closed. You make n passes by the lockers, each time
starting with locker #1. On the ith pass, i = 1, 2, . . . , n, you toggle the door of
every ith locker: if the door is closed, you open it; if it is open, you close it. After
the last pass, which locker doors are open and which are closed? How many of
them are open?
 10
A locker is toggled once for every divisor it has.
For example, locker #6 is toggled on passes 1, 2, 3, and 6. The only lockers
toggled an odd number of times will end up open.
Now, the number of divisors of a number is odd if and only if the number is a
perfect square (4,16) So, after the n passes, only the lockers with numbers
that are perfect squares will be open.
To determine how many lockers are open, you need to find how many perfect
squares are less than or equal to n. This corresponds to finding the floor of the
square root of n, and since the lockers are numbered from 1 to n, the number
of open lockers is the floor of the square root of n.
In summary, after n passes, the open lockers are those with numbers that are
perfect squares less than or equal to n, and the number of open lockers is the
 floor of the square root of n.

11

Try Out

1. Algorithm to find prime Number

2. Extended Euclid’s algorithm : GCD
3. Find gcd(31415, 14142) by applying Euclid’s algorithm. 4. Estimate
how many times faster it will be to find gcd(31415, 14142) by Euclid’s
algorithm compared with the algorithm based on checking consecutive
integers from min{m, n} down to gcd(m, n).
 12

Algorithm design and analysis process

Understand the problem

Decide on computational means

Exact vs approximate solution
Data structures
Algorithm design technique

Design an algorithm

Prove correctness
 Analyze the algorithm

Code the algorithm

13
Understanding the Problem:

Read the problem’s description carefully and ask questions if you have
any doubts about the problem, do a few small examples by hand, think
about special cases, and ask questions again if needed.

An input to an algorithm specifies an instance of the problem the

algorithm solves. It is very important to specify exactly the set of
instances the algorithm needs to handle

If you fail to do this, your algorithm may work correctly for a majority of
 inputs but crash on some “boundary” value. Remember that a correct
algorithm is not one that works most of the time, but one that works
correctly for all legitimate inputs.

14
Ascertaining the Capabilities of the Computational Device

Algorithms in use today are still destined to be programmed for a computer

closely resembling the von Neumann this architecture is captured by the
so-called random-access machine (RAM).
Its central assumption is that instructions are executed one after another,
one operation at a time. Accordingly, algorithms designed to be executed
on such machines are called sequential algorithms.
The central assumption of the RAM model does not hold for some newer
computers that can execute operations concurrently, i.e., in parallel.
Algorithms that take advantage of this capability are called parallel
algorithms.

15
Choosing between Exact and Approximate Problem Solving Choose
between solving the problem exactly or solving it approximately.

An algorithm design technique (or “strategy” or “paradigm”) is a general

approach to solving problems algorithmically that is applicable to a variety of
problems from different areas of computing

1. provide guidance for designing algorithms for new problems, i.e.,problems

for which there is no known satisfactory algorithm.

2. algorithms are the cornerstone of computer science.

Algorithms + Data Structures = Programs

Methods of Specifying an Algorithm : Natural Language , Pseudo code

Prove correctness
 Correct output for every legitimate input in finite time . Based on mathematical
induction

16

Analyze the algorithm

Efficiency: time and space
Simplicity : easy to understand
Generality: range of inputs, special cases
Optimality: no other algorithm can do better
Coding
How the objects and operations in the
algorithm are represented in the chosen programming
language?
 17

Important problem types

⮚ Sorting
⮚ Searching
⮚ String processing
⮚ Graph problems
⮚ Combinatorial problems Pigeonhole Principle
⮚ Geometric problems Area and Perimeter
Problems
⮚ Numerical problems
 18

Fundamental data structures

Linear data structures

• Array
• Linked list
• Stack
• Queue

Operations: search, delete, insert

Implementation: static, dynamic
 19

Fundamental data structures

Non-linear data structures

• Graphs
• Trees : connected graph without cycles
– Rooted trees
• Ordered trees
– Binary trees
 Graph representation: adjacency lists,
adjacency
matrix
Tree representation: as graphs; binary nodes
20

Fundamental data structures

Sets, Bags, Dictionaries

• Set: unordered collection of distinct elements
Operations: membership, union, intersection
Representation: bit string; linear structure •
Bag: unordered collection,
elements may be repeated
• Dictionary: a bag with operations search, add, delete

21

• Algorithm classification
• By types of problems
• By design technique

• Design techniques
 • a general approach to solving problems

22
gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =
gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43)
= gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1

Consecutive Integer Checking Algorithm:

Total divisions: 14142 iterations (worst case) × 2 divisions per iteration (max) =
28284 divisions.
Euclid's Algorithm:
 Total divisions: 11 divisions

Speedup ≈ Consecutive Integer Checking divisions / Euclid’s Algorithm

divisions ​Speedup≈28284/11≈2571.27

Therefore, Euclid's algorithm is estimated to be between 1300 (lower bound) and 2600
(upper bound) times faster than the consecutive integer checking algorithm.

23