What is an Algorithm?

• The word algorithm comes from the name of a

Persian author, Abu Ja'far Mohammed ibn Musa al
Khowarizmi(c.825A.D.), who wrote a textbook on
mathematics.
• This word has taken on a special significance in
computer science, where "algorithm" has come to
refer to a method that can be used by a computer for
the solution of a problem.
• This is what makes algorithm different from words
such as process, technique, or method.
Definition:
• An algorithm is a finite set of instructions that, if followed,
accomplishes a particular task. In addition, all algorithms must
satisfy the following criteria:
1. Input: Zero or more quantities are externally supplied.
2. Output: At least one quantity is produced.
3. Definiteness: Each instruction is clear and unambiguous.
4. Finiteness: If we trace out the instructions of an algorithm, then
for all cases, the algorithm terminates after a finite number of steps.
5. Effectiveness: Every instruction must be very basic so that it can
be carried out, in principle, by a person using only pencil and paper.
It is not enough that each operation be definite as in criterion3; it
also must be feasible.
 What is Pseudocode?
• One of the popular representation of
Algorithm
• Widely choosen because:
– easy to read and write
– allow the programmer to concentrate on the logic
of the problem
– Structured in English language
 Pseudocode Convention
• Statement are written in simple English
• Each instruction is written on a separate line
• Keywords and indentation are used to signify
particular control structures.
• Each set of instructions is written from top to
bottom, with only one entry and one exit.
• Groups of statements may be formed into modules,
and that group given a name.
 Six Basic Computer Operations
1. A computer can receive information
Verb used:
•Read  used when the algorithm is to receive the input from a record on a file
•Get  used when the algorithm is to receive input from the keyboard.

Read student name

Get system date
Read number_1, number_2
Get tax_code
2. A computer can put out information
Verb used:
•Print  used when the output is to be sent to the printer
•Write  used when the output is to be written to a file
•Put, Output, Display  used when the output is to be written to the screen
•Prompt  required before an input instruction Get, causes the message to be sent to
the screen which requires the user responds, usually by providing input.

Print `Program Completed´

Write customer record to master file
Put out name, address and postcode
Output total_tax
Display ´End of data´

Prompt for student_mark

Get student_mark
 3. A computer can perform arithmetic
Verb used:
• Compute
• Calculate

•Symbols used:
+, -, *, /, ()

Add number to total

Total = total + number

Divide total_marks by student_count

Sales_tax = cost_price * 0.10
Compute C = (F – 32) * 5/9
4. A computer can assign a value to a variable or
memory location
• Three cases :
1. To give data an initial value in pseudocode, the verbs
Initialise or Set are used
2. To assign a value as a result of some processing, the
symbols ´=´or ´´ are written
3. To keep a variable for later use, the verbs Save or
Store are used.

Initialize total_price to zero

Set student_count to 0
Total_price = cost_price + sales_tax
Total_price  cost_price + sales_tax
Store customer_num in last_customer_num
5. A computer can compare two variables and select one of two
alternate actions

Keyword used:
IF, THEN, ELSE

IF student_attendance_status is part_time THEN

add 1 to part_time_count
ELSE
Add 1 to full_time_count
ENDIF
 6. A computer can repeat a group of actions

Keyword used:
DOWHILE, ENDDO

DOWHILE student_total < 50

Read student record
Print student name, address to report
Add 1 to student_total
ENDDO
 Meaningful names
• When designing a solution algorithm, a programmer
should introduce unique names, which are:
– Represent the variables or objects in the problem
– Meaningful
example: number1, number2, number3  more
meaningful than A, B, C
- Used word separator if more than one word
example: sales_tax, word_count
- Or Capital letter as separator
example: salesTax, wordCount
 The Structure Theorem
• It is possible to write any computer program
by using only three basic control structures
that are easily represented in pseudocode:
» Sequence
» Selection
» Repetition
 Sequence
Is the straightforward execution of one processing step after another.

Statement a
Statement b
Statement c

• Add 1 to pageCount
• Print heading line 1
• Print heading line 2
• Set lineCount to zero
• Read customer record
 Selection
Presentation of condition and the choice between two actions

IF condition p is true THEN

statement(s) in true case
ELSE
statement(s) in false case
ENDIF
Example:
IF student_attendance_status is part_time THEN
add 1 to part_time_count
ELSE
add 1 to full_time_count
ENDI>f
 Repetition
The presentation of a set of instructions to be performed repeatedly,
as long as a condition is true

DOWHILE condition p is true

statement block
ENDDO

Example:
Set student_total to zero
DOWHILE student_total < 50
Read student record
Print student name, address to report
Add 1 to student_total
ENDDO
 DESIGNING A SOLUTION ALGORITHM

• The most challengin task in the life cycle of a

program
• First attempt usually doesnt result in a finished
product
• Keep altering the step and algorithms till
satesfied result achieved.
 Point to be considered in Solution Algorithm

1. A name should be given to the algorithm, which is

describe the function of algorithm
2. An END statement used to indicate the algorithm is
complete
3. All processing steps between the algorithm name
and END statement should be indented for
readability.
4. Each processing step in the defining diagram
relates directly to one or more statements in the
algorithm.
Example 3.1. Solution Algorithm for example 2.1

 A program is required to read three numbers,

add them together and print their total.
• Defining diagram

Input Processing Output

Number1 total
Number2
Number3
 Solution Algorithm
• Add_three_numbers
Read number1, number2, number3
Total = number1 + number2 + number3
Print total
END
• Comments : //
• Blocks :{and }.
• Statements are delimited by ;.
• An identifier begins with a letter.
• The data types of variables are not explicitly
declared.
• Assignment of values to variables
(variable):=(expression);
• Elements of multidimensional arrays are
accessed using[ and ].
• Looping statements :for,while,and repeat-until.
• The while loop takes the following form:
while(condition) do
{ (statement 1)
(statement n)
}
• The general form of a for loop is
for variable:=value l to value 2 step do
{ (statement 1)
(statement n)
}
• A repeat-until statement is constructed as follows:
repeat
(statement 1)
(statement n)
Until(condition)
• A conditional statement has the following
forms:
– if (condition) then (statement)
– if (condition) then (statement1) else (statement2)
– case
{
: (condition 1): (statement1)
: (condition n): (statement n)
:else:(statement n + 1) }
 Recursive Algorithms
• 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.
 Recursion
• In some problems, it may be natural to define the
problem in terms of the problem itself.
• Recursion is useful for problems that can be
represented by a simpler version of the same
problem.
• Example: the factorial function
6! = 6 * 5 * 4 * 3 * 2 * 1

We could write:
6! = 6 * 5!
 Tower of Hanoi
• The disks must be moved within one week.
Assume one disk can be moved in 1 second. Is
this possible?

• To create an algorithm to solve this problem, it

is convenient to generalize the problem to the
“N-disk” problem, where in our case N = 64.
Recursive Solution
Recursive Solution
Recursive Solution
Recursive Solution
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
Tower of Hanoi
 Recursive Algorithm
void Hanoi(int n, string a, string b, string c)
{
if (n == 1) /* base case */
Move(a,b);
else { /* recursion */
Hanoi(n-1,a,c,b);
Move(a,b);
Hanoi(n-1,c,b,a);
}
}
 Performance Analysis
Any given problem may be solved by a number of algorithms. To
judge an algorithm there are many criteria. Some of them
are:
1. It must work correctly under all possible condition
2. It must solve the problem according to the given specification
3. It must be clearly written following the top down strategy
4. It must make efficient use of time and resources
5. It must be sufficiently documented so that anybody can
understand it
6. It must be easy to modify, if required.
7. It should not be dependent on being run on a particular
computer.
• Performance analysis of an algorithm depends
upon two factors
• amount of memory used
• amount of compute time consumed on any CPU.
• Formally they are notified as complexities in
terms of:
– Space Complexity.
– Time Complexity.
• Space Complexity of an algorithm is the amount of memory it needs to
run to completion i.e. from start of execution to its termination. Space
need by any algorithm is the sum of following components:
• Fixed Component: This is independent of the characteristics of the
inputs and outputs. This part includes: Instruction Space, Space of
simple variables, fixed size component variables, and constants
variables.
• Variable Component: This consist of the space needed by component
variables whose size is dependent on the particular problems
instances(Inputs/Outputs) being solved, the space needed by
referenced variables and the recursion stack space is one of the most
prominent components. Also this included the data structure
components like Linked list, heap, trees, graphs etc.
• Therefore the total space requirement of any algorithm 'A' can be
provided as
• Space(A) = Fixed Components(A) + Variable Components(A)
{
int z = a + b + c;
return(z);
}
Space(A) = Fixed Components(A) + Variable Components(A)

Space = 3
int sum(int a[], int n)
{
int x = 0; // 4 bytes for x
for(int i = 0; i < n; i++) // 4 bytes for i
{
x = x + a[i];
}
return(x);
}
Space(A) = Fixed Components(A) + Variable Components(A)

Space = 3 + n
AlgorithmRSum(a,n)
{
if (n <0) thenreturn0.0;
Else return RSum (a,n-1)+ a[n];
}
Space(A) = Fixed Components(A) + Variable Components(A)

Space > = 3(n+1)

• Time Complexity of an algorithm(basically when converted
to program) is the amount of computer time it needs to run
to completion.
• The time taken by a program is the sum of the compile time
and the run/execution time .
• The compile time is independent of the instance(problem
specific) characteristics.
• following factors effect the time complexity:
– Characteristics of compiler used to compile the program.
– Computer Machine on which the program is executed and
physically clocked.
– Multiuser execution system.
– Number of program steps.
• Time(A) = Fixed Time(A) + Instance Time(A)
• Sum(a,b)
{
return a+b
}
Time(A) = Fixed Time(A) + Instance Time(A)
Time (A) = C+2
Statement Steps per Frequency Total Steps
execution

Algorithm Sum(number,size) 0
0 -

{ 0 - 0
result=0.0;
1 1 1

for count = 1 to size do

1 size+1 size + 1

result= result + number[count];

1 size size

return result;
1 1 1

} 0 - 0
Total 2size + 3
 Asymptotic Analysis
• Asymptotic analysis of an algorithm refers to
defining the mathematical boundation
/framing of its run-time performance.
• Using asymptotic analysis, we can very well
conclude the best case, average case, and worst
case scenario of an algorithm.
• Asymptotic analysis refers to computing the
running time of any operation in mathematical
units of computation.
 Why is Asymptotic Notation Important?

1. They give simple characteristics of an

algorithm's efficiency.
2. They allow the comparisons of the
performances of various algorithms.
• Asymptotic Notation is a way of comparing function that ignores
constant factors and small input sizes. Three notations are used
to calculate the running time complexity of an algorithm:
• O (Big-oh)
• Ω (omega)
• ϴ (Theta)
• Usually, the time required by an algorithm falls under three
types −
• Best Case − Minimum time required for program execution.
• Average Case − Average time required for program execution.
• Worst Case − Maximum time required for program execution.
 O (Big-oh)

• Big-oh is the formal method of expressing the

upper bound of an algorithm's running time.
• It measures the worst case time complexity or
the longest amount of time an algorithm can
possibly take to complete.
For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
 Ω (omega)

• The notation Ω(n) is the formal way to express

the lower bound of an algorithm's running
time.
• It measures the best case time complexity or
the best amount of time an algorithm can
possibly take to complete.
For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
 Theta Notation, θ
• The notation θ(n) is the formal way to express
both the lower bound and the upper bound of
an algorithm's running time.
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }
 Amortize Analysis

• Amortized analysis is used for algo­rithms that

have expensive opera­tions that happen
only rarely.
• Amortized complexity analysis is most commonly
used with data structures that have state that
persists between operations.
• The basic idea is that an expensive operation can
alter the state so that the worst case cannot occur
again for a long time, thus amortizing its cost.
• The aggregate method, where the total running time
for a sequence of operations is analyzed.
• The accounting (or banker's) method, where we
impose an extra charge on inexpensive operations and
use it to pay for expensive operations later on.
• The potential (or physicist's) method, in which we
derive a potential function characterizing the amount
of extra work we can do in each step. This potential
either increases or decreases with each successive
operation, but cannot be negative.
Dynamic Table
 Accounting Method
• Increase cost of some operations to bet credit
for others.
• For example consider a stack operations
Cost Amortized
cost
Push 1 2
Pop 1 0
Multi pop Min(k,n) 0
Potential Method
Divide and Conquer – General Method
 Suggest splitting the inputs into k distinct sub
problems ( 1≤ k ≤ n).
 These sub problems must be solved.
 A method must be found to combine the sub
solutions into a solution of the whole problem.
• If the sub problems are still relatively large
then the divide and conquer strategy can
possibly be reapplied.
 Detecting a Counterfeit Coin
• Given a set of coins
• Exactly one coin is defective: it has lesser weight
• Which one is it?
Detecting a Counterfeit Coin Example: n= 16
After one comparison
After Two comparisons
After Three comparisons
After Four comparisons
• Time Complexity of many divide-and-conquer
algorithms is given by recurrences of the form

• where a,b are constants

• split the problem into a ≥ 1 sub problems of
size n/b where b >1.
 Defective Chessboard
• Given a chess board of size n × n where n = 2k
• With exactly one defective square
• How do we cover it completely with L-shaped
tiles?
• L-shaped tiles : trominoes or triominoes
 Defective Chessboard

K=0 k=1

K=2
 A Divide Conquer Solution
• Size k=1 (i.e. 2×2) problem has a simple
solution.
• Divide larger boards into smaller ones.
• Combine solutions to smaller problems.
Ex: Tiling a 8×8 Defective Chessboard
Ex: Tiling a 8×8 Defective Chessboard
Ex: Tiling a 8×8 Defective Chessboard
Ex: Tiling a 8×8 Defective Chessboard
 Binary Search
• ai 1≤ i ≤ n is a list of elements that are sorted
in nondecreasing order.
• Determine whether a given element x is
present in the list.
• MID = low + high
2
• If x < mid, then high = mid-1
• If x > mid, then low = mid+1
 Example
Number to Search

85 > 68 85 < 92
index 0 1 2 3 4 5 6 7 8

1 10 55 66 68 85 92 101 110

Mid = low + high =0+8

=4
2 2
 Example
Number to Search

85 > 68 85 < 92
index 0 1 2 3 4 5 6 7 8

1 10 55 66 68 85 92 101 110

Mid = low + high =5+8

= 6. 5
2 2
 Example
Number to Search

85 < 92
index 0 1 2 3 4 5 6 7 8

1 10 55 66 68 85 92 101 110

Mid = low + high =5+7

= 6
2 2
 Example
Number to Search

85 = 85
index 0 1 2 3 4 5 6 7 8

1 10 55 66 68 85 92 101 110

Mid = low + high =5+6

= 5.5
2 2
Pseudo Code for Binary Search
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched

Set lowerBound = 1
Set upperBound = n

while x not found

if upperBound < lowerBound
EXIT: x does not exists.

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1

if A[midPoint] = x
EXIT: x found at location midPoint
end while

end procedure
6 3 17 25 31 55 62 53 36 42 47 29 8 4 12
Finding the Maximum and Minimum
• Find the maximum and minimum items in a
set of n elements.
• Divide and Conquer Approach
 the array is divided into two halves.
 maximum and minimum numbers in each halves
are found.
 return the maximum of two maxima of each half
and the minimum of two minima of each half.
 82 36 49 91 12 14 6 76 92 55

82 36 49 91 12 14 6 76 92 55

82 36 49 91 12 14 6 76 92 55

82 36 49 14 6 76
 Max Min
92 6

Max Min Max Min Max Min

82 36 91 6 92 55

82 36 49 49 91 12 14 6 76 76 92 55
Time Complexity
 Merge Sort
• Merge Sort is a Divide and Conquer algorithm.
• It divides input array in two halves, calls itself
for the two halves and then merges the two
sorted halves.
 2 8 5 3 9 4 1 7

2 8 5 3 9 4 1 7

2 8 5 3 9 4 1 7

2 8 5 3 9 4 1 7
2 8 5 3 9 4 1 7

2 8 3 5 4 9 1 7

2 3 5 8 1 4 7 9

1 2 3 4 5 7 8 9
Time Complexity
 Quick Sort
• Sorting Algorithm
• It finds the element called pivot which divides
the array into two halves.
• Elements in the first half are smaller than the
pivot.
• Elements in the second half are greater than
the pivot.
 Divide and Conquer Solution
• Find the pivot that divides the array into two
halves.
• Quick sort the left half.
• Quick sort the right half.
 Is Pivot < right? Pivot = 5
Pivot Right = 4
No

Array Index 0 1 2 3 4 5
Array Elements 5 2 6 1 3 4

Left Right
 Is Pivot > left? Pivot = 5
Pivot Left = 4
Yes

Array Index 0 1 2 3 4 5
Array Elements 4 2 6 1 3 5

Left Right
 Is Pivot > left? Pivot = 5
Left =2
Yes Pivot

Array Index 0 1 2 3 4 5
Array Elements 4 2 6 1 3 5

Left Right
 Is Pivot > left? Pivot = 5
Left =6
No Pivot

Array Index 0 1 2 3 4 5
Array Elements 4 2 6 1 3 5

Left Right
 Is Pivot < Right? Pivot = 5
Yes Right =6
Pivot

Array Index 0 1 2 3 4 5
Array Elements 4 2 5 1 3 6

Left Right
 Is Pivot < Right? Pivot = 5
No Right =3
Pivot

Array Index 0 1 2 3 4 5
Array Elements 4 2 5 1 3 6

Left Right
 Is Pivot > Left? Pivot = 5
Left =3
Pivot Yes

Array Index 0 1 2 3 4 5
Array Elements 4 2 3 1 5 6

Left Right
 Is Pivot > Left? Pivot = 5
Left =1
Yes Pivot

Array Index 0 1 2 3 4 5
Array Elements 4 2 3 1 5 6

Left Right
 Pivot

Array Index 0 1 2 3 4 5
Array Elements 4 2 3 1 5 6

Left Right
 Is Pivot < Right? Pivot = 4
Right =1
Pivot No

Array Index 0 1 2 3 4 5
Array Elements 4 2 3 1 5 6

Left Right
 Is Pivot > Left Pivot = 4
Left =1
Pivot Yes

Array Index 0 1 2 3 4 5
Array Elements 1 2 3 4 5 6

Left Right
 Is Pivot > Left Pivot = 4
Yes Left =2
Pivot

Array Index 0 1 2 3 4 5
Array Elements 1 2 3 4 5 6

Left Right
 Is Pivot > Left Pivot = 4
Yes Left =3
Pivot

Array Index 0 1 2 3 4 5
Array Elements 1 2 3 4 5 6

Left Right
 Is Pivot < right Pivot = 1
Yes Right =3
Pivot

Array Index 0 1 2 3 4 5
Array Elements 1 2 3 4 5 6

Left Right
 Selection Sort
• Sorting Algorithm
• Initially whole array is unsorted.
• Considered into two parts
 Unsorted
 Sorted
• Selection : select the lowest element in the
remaining array.
• Swapping : Bring it to the starting position.
• Counter shift: Change the counter for
unsorted array be one.
Sorted Array Unsorted Array

64 25 12 22 11

64 25 12 12 11
Sorted Array Unsorted Array

11 25 12 22 64

25 12
Sorted Array Unsorted Array

11 12 25 22 64

25 22
Sorted Array Unsorted Array

11 12 22 25 64
Strassen’s Matrix Multiplication