Lecture 2: Study of

Algorithms.

Dr. Khaled Alburaihi

Assistant Prof & Head of the
Circle of Academic Quality and
Accreditation in SCC.
Head of the Dept. of MIS In QAU.
 Name
 Scientific Background
 Practical Background
General Rules
Syllabus
 Course Texts
 Design and Analysis Algorithms Texts Books :
 Introduction to Algorithms, 2nd edition by Corman, Rivest, Leiserson,
and Stein.
 Computer Algorithms: Introduction to Design and Analysis By Sara
Baase, 3rd Edition, Addison-Wesley Publishing Company
 Using internet Research.
Study of Algorithms
Study of Algorithms
 The study of algorithms includes many important and
active areas of research.
 Given a problem:
 How do we find an efficient algorithm for its solution?
 Once we have found an algorithm:
 How can we compare this algorithm with other algorithms
that solve the same problem?
 How should we judge the goodness of an algorithm?
Study of Algorithms
 About the study of algorithms, most researchers agree
that there are four distinct areas of study one can identify.
 How to devise algorithms?
 How to validate algorithms?
 How to test a program?
 How to analyze algorithms?
Study of Algorithms (Cont.)
 How to devise algorithms?
 Creating an algorithm is an art which may never be
fully automated.
 How to validate algorithms?
 Once an algorithm is devised, it is necessary to
show that it computes the correct answer for all
possible legal inputs.
 A program can be written and then be verified.
Study of Algorithms (Cont.)
 How to test a program?
 Debugging is the process of executing programs
on sample data sets to determine whether the
faulty results occur and, if so, to correct them.
 Profiling is the process of executing a correct

program on data sets and measuring the time and

space it takes to compute the results.
Study of Algorithms (Cont.)
 How to analyze algorithms?
 Analysis of algorithms refers to the task of
determining how much computing time and
storage an algorithm requires.
 It allows you to make quantitative judgments

about the value of one algorithm over another.

 It allows you to predict whether the software will
meet any efficiency constraints that exist.
 Questions such as how well does an algorithm

perform in the best, worst and average cases.

Study of Algorithms (Cont.)
 Theoretical analysis:
All possible inputs.
 Independent of hardware/ software implementation

 Experimental Study:
Some typical inputs.


 Depends on hardware/ software implementation.

 A real program.
Pseudocode Conventions
What is the Pseudocode?
 Pseudocode is a high-level description of an algorithm that
uses natural language mixed with some programming
language-like constructs.
 It provides a step-by-step outline of the algorithm’s logic
without being tied to any specific programming language
syntax.
 Pseudocode allows algorithm designers to express their ideas
in a concise and understandable manner before actual coding
takes place
Benefits of using Pseudocode

 Simplify logic of the program

 Easier to communicate with non-programmers
 Save time & prevent mistakes
How to Write Pseudocode Algorithm
 Understand the problem
 Example : Write a program that adds together two numbers
 Break down the problem into smaller Steps
 Ask the user to input the first number
 Ask user to input the second number
 Ask the two numbers together

 Display the sum to the user

 Write out the pseudocode

 Test the pseudocode

 Translate the pseudocode into actual code

How to Write Pseudocode Algorithm
 Example in Python
Homework
 Example: Write the program and Pseudocode Algorithm in C++ language that
adds together two numbers
Pseudocode Conventions
 Comments begin with // and continue until the
end of line.
 Blocks are indicated with matching braces:

{and}.
 An Identifier begins with a letter: max.
 Assignment of values to variables is done using

assignment statement : Variable:=expression.

 Logical operators: and, or and not are provided.
 Relational operators: <, ≤, =, ≠, ≥ and >
provided.
Pseudocode Conventions (Cont.)
 Elements of arrays are accessed using: [ and ].
 While loop:

while (condition) do
{
(statement 1)
………………
(statement n)
}
 For loop:
for variable:=value1 to value2 step step do
{
(statement 1)
………………
(statement n)
}
Pseudocode Conventions (Cont.)
 Repeat-until loop:
repeat
{
(statement 1)
…………
(statement n)
} until (condition)

 Conditional statement:
if (condition) then (statement)
if (condition) then (statement 1)
else (statement 2)
Pseudocode Conventions (Cont.)
 Case statement:
case
{
: (condition 1): (statement 1)
………………….
: (condition n): (statement n)
: else: (statement n+1)
}
 Input and output are done using: read and write.
 There is only one type of procedure: Algorithm.
 An algorithm consists of a heading and a body.
 The heading of an algorithm takes the form

Algorithm Name ((parameter list))

Recursive Algorithms
Recursive Algorithms
 A Recursive Algorithm is a problem-solving approach
that solves a problem by solving smaller instances of
the same problem.
 These algorithms make the process of coding certain
tasks simpler and cleaner, improving the readability
and understanding of the code.
Recursive Algorithms (Cont.)
 A Recursive function is a function that is defined in
terms of itself.
 Similarly, an algorithm is said to be recursive if the
same algorithm is invoked in the body.
 An algorithm that calls itself is direct recursive.

 Algorithm A is said to be indirect recursive if it calls

another algorithm which in turn calls A.
Recursive Algorithms (Cont.)
 Base Condition
The base condition is the condition that is used to
terminate the recursion. The recursive function will keep
calling itself till the base condition is satisfied.
 Recursive Case
 Recursive case is the way in which the recursive call is
present in the function. Recursive case can contain
multiple recursive calls, or different parameters such
that at the end, the base condition is satisfied and the
recursion is terminated.
Syntax Structure of Recursion Algorithms
Example 1 in C++ Program to
Using Recursion algorithm
Write the program to Calculate the Factorial 5! In c+
int main()
+ Language Using Recursion algorithm ?
{
// C++ Program to calculate the sum of first N int n = 5;
natural
// numbers using recursion // calling the function
#include <iostream> int sum = nSum(n);
using namespace std;
int nSum(int n) cout << "Sum = " << sum;
{ return 0;
// base condition to terminate the recursion }
when N = 0
if (n == 0) {
return 0;
}
// recursive case / recursive call
int res = n + nSum(n - 1);
return res;
}
Example (cont.)
 Output: Sum = 15
 In the above example,
 Recursive Function: nSum() is the Recursive
Function
 Recursive Case: The expression, int res = n +
nSum(n – 1) is the Recursive Case.
 Base Condition: The base condition is if (n == 0)
{ return 0;}
Example (cont.)
Example 2: Program for Tower of
Hanoi
 Tower of Hanoi is a mathematical puzzle where we
have three rods and n disks. The objective of the
puzzle is to move the entire stack to another rod,
obeying the following simple rules:
 Only one disk can be moved at a time.
 Each move consists of taking the upper disk from one

of the stacks and placing it on top of another stack i.e.

a disk can only be moved if it is the uppermost disk on
a stack.
 No disk may be placed on top of a smaller disk.
Program for Tower of Hanoi
(Cont.)
Example 2: The solution of the
problem
 The solution of the problem for N number of
disks is as follows:
 Move the top N-1 disks from peg A to peg B
(using C as an auxiliarypeg)
 Move the bottom disk from peg A to peg C
 Move N-1 disks from Peg B to Peg C (using Peg
A as an auxiliary peg)
Example for Tower of Hanoi
Tower of Hanoi Algorithm

TOH( n, Sour, Aux , Des)

If(n=1)
Write ("Move Disk “, n ," from ", Sour ," to ",Des)
Else
TOH(n-1,Sour,Des,Aux);
Write ("Move Disk “, n ," from ", Sour ," to ",Des)
TOH(n-1,Aux,Sour,Des);
END
Implementation of Tower of
HANOI in using C++ program
#include <iostream>
using namespace std;
//main program
//tower of HANOI function implementation
int main()
void TOH(int n, char Sour, char Aux, char
{
Des)
int n;
{
if (n == 1) {
cout << "Enter no. of disks:";
cout << "Move Disk " << n << " from "
cin >> n;
<< Sour << " to " << Des << endl;
//calling the TOH
return;
TOH(n, 'A', 'B', 'C');
}
return 0;
TOH(n - 1, Sour, Des, Aux);
}
cout << "Move Disk " << n << " from " <<
Sour << " to " << Des << endl;
TOH(n - 1, Aux, Sour, Des);
}
Sorting Problem
Sorting Problem
 Input: A sequence of n numbers (a1, a2,…, an).
 Output: A permutation of n numbers (reordering)

(a'1, a'2,…, a'n) of the input sequence such that a'1≤

a'2 ≤… ≤ a'n.
 Solve the problem using Insertion sort.

 Insert an element to a sorted array such that the

order of the resultant array be not changed.

Sorting Problem
Algorithm InsertionSort (A, n)
{
for i:=2 to n do
{
key:=A[i];
// Insert A[i] into the sorted sequence A[1…i-1].
j:=i-1;
while ( ( j>0) and (A[j]>key) ) do
{
A [j+1]:=A[j];
j:=j-1;
}
A[j+1]:=key;
}
}
 Illustrate the above algorithm with an example.
Sorting Problem
Sorting Problem
References
 Introduction to Algorithms, 2nd edition by Corman, Rivest,
Leiserson, and Stein.

 Computer Algorithms: Introduction to Design and Analysis

By Sara Baase, 3rd Edition, Addison-Wesley Publishing
Company

 Using internet Research.

‫خالد البريهي‪/‬‬
‫د‬