Algotithms
3rd Year
Lecture 1
Introductio Dr. Ahmed Salama
n to
Algorithms
Course’s Rules
1- Lateness not allowed
2- Tasks every week
3- Mobiles are silent
4- materials and announcement will be through
classroom not Facebook
Algorithms
An algorithm is a complete, sequence of steps of operation for solving a specific
problem.
An algorithm is the best way to represent the solution of a particular problem in a
very simple and efficient way
Well-defined
Finiteness Input
steps
Characteristics of an Algorithm
Output Effectiveness
Algorithms
An algorithm is a complete, sequence of steps of operation for solving a specific
problem.
An algorithm is the best way to represent the solution of a particular problem in a
very simple and efficient way
Algorithm components?
• Problem
• Solution
• Algorithm
• Program
Algorithms
Process the
Read the input Return the
Start data through End
data output
logical steps
Algorithms Types
Sorting Numerical Graph
Algorithms Algorithms Algorithms
Searching Patterns
Algorithms Algorithms
Algorithms
Analysis Design
Algorithms
Analysis
• Analysis of algorithms is the determination of the amount of time and
space resources required to execute them by choosing a better
algorithm for a particular problem as one computational problem can
be solved by different algorithms.
Design
• Implementing an efficient algorithm to solve problem in an efficient
method considering the minimum time and space
Algorithm Design Techniques
1. Divide and Conquer Approach: It is a top-down approach. The algorithms which follow
the divide & conquer techniques involve three steps:
• Divide the original problem into a set of subproblems.
• Solve every subproblem individually, recursively.
• Combine the solution of the subproblems (top level) into a solution of the whole
original problem.
2. Greedy Technique: Greedy method is used to solve the optimization problem. An
optimization problem is one in which we are given a set of input values, which are required
either to be maximized or minimized (known as objective), i.e. some constraints or
conditions.
3. Dynamic Programming: Dynamic Programming is a bottom-up approach we solve all
possible small problems and then combine them to obtain solutions for bigger problems
Algorithms
Analysis
• Predict the value of algorithm in term of resources and performance
How much memory is
What make algorithm Analysis used ?
fast ?
Time Space
Pseudocode Technique
• The pseudocode is an informal and human readable description of an
algorithm leaving many details of it.
• The pseudocode is similar, but not identical, to C++. (Language-agnostic)
• Not discuss the implementation of algorithms in any particular
programming language.
• It aims to present algorithms clearly so they can be readily
understood and analyzed.
Pseudocode Technique
Best Practices and guidance for writing an efficient Pseudocode:
Clarity and
Consistency Abstraction
Simplicity
Use Plain
Indentation Modularity
Language
Algorithms
Phases of Algorithm Development
Linear Search Algorithm
Problem: Determine whether x is in the array S of n keys.
Inputs: positive integer n, array of keys S indexed from 1 to n, and a key x.
Outputs: location, the location of x in S (-1 if x is not in S.)
Int seq_search ( int n, const keytype S [ ], keytype x)
{
step1: set location to 0 (as the first element );
step2: repeat (location <= n-1 and S[location] != x )
step3: move location to the next one
step4: check if (location > n-1)
Then set location = -1 (as not found location)
step5: return location
}
Binary Search Algorithm
Problem: Determine whether x is in the sorted array S of n keys.
Inputs: positive int n, sorted array of keys S indexed from 1 to n, a key x.
Outputs: location, the location of x in S (0 if x is not in S).
void bin_search (int n, const keytype S[], keytype x)
{index& location;
Define indices low, high, mid;
Set low = 0; high = n-1; location = 0;
repeat (low < = high and location = = 0)
{ set mid = ∟(low + high)/2 ⌋;
check if (x = = S[mid])
then location = mid;
else check if (x < S[ mid ])
then high = mid - 1;
else then low = mid + 1;
}}
Exchange Sort Algorithm
Problem: Sort n keys in no decreasing order.
Inputs: positive integer n, array of keys S indexed from 1 to n.
Outputs: the array S containing the keys in non-decreasing order.
void exchangesort (int n, keytype S[])
{ define indices i, j;
for i=0 to n-1
for j=i+1 to n
check if (S[j] < S[i])
then exchange S[i] and S[j];
end for
end for
}
Selection Sort Algorithm
Problem: Sort n keys in nondecreasing order.
Inputs: positive integer n, array of keys S indexed from 1 to n.
Outputs: the array S containing the keys in nondecreasing order.
void Selection_sort ( keytype array[ ] , int N)
{
for i = 0 to i < n-1
{ min_loc = i;
for j = i+1 to j < N
{
If ( Array[j] < Array[ min_loc] )
{
min_loc = j;
}
}
Exchange Array[ min_loc] with Array[i];
end for
}
Bubble Sort Algorithm
Problem: Sort n keys in nondecreasing order.
Inputs: positive integer n array of keys S indexed from 1 to n.
Outputs: the array S containing the keys in nondecreasing order.
void Bubblesort ( keytype array[ ] , int N)
{
Define Indices i, j;
Loop from i = 0 to N-1
loop from j = 0 to N-1 - i
if array[j] > array [j+1]
then exchange array [j] with array [j+1];
End loop
End loop
}
Note
Selection sort is faster and more efficient than Bubble sort
because
Selection sort swaps elements "n" times in worst case,
Where
Bubble sort swaps almost n*(n-1) times.
Sorting Algorithms Visualization
[Link]
Thank You