Subject: Algorithm Unit-1: Fundamentals of Algorithms

Algorithm:
Definition: An Algorithm is nothing but a step-by-step process for solving a particular
problem where a set of finite logical instructions carried out in a sequential order to
accomplish some computational operations.
It is simple sequence of some logical steps to a problem represented as an informal
description in form of a flowchart or pseudo code.

It can be understood by taking the example of cooking a new recipe. To cook a new
recipe, one reads the instructions and steps and executes them one by one, in the given
sequence. The result thus obtained that the new dish is cooked perfectly.

Characteristics of Algorithm:
An Algorithm belongs to the following characteristics-
1. Input: An Algorithm requires some input values to execute a particular
computational task. Thus an algorithm can be given one/more well defined
value(s), other than 0 (no value) as input.
2. Output: The algorithm must clearly define what output will be yielded and it
should be well defined as well. It should produce at least one output.
3. Finiteness: An algorithm must be finite in nature. Finiteness in this context means
that the algorithm belongs to a set of finite logical instructions that are countable
step-by-step.
4. Unambiguity: A perfect algorithm is defined as unambiguous which means that all
the algorithmic instructions should be meaningful, transparent and
straightforward.
5. Effectiveness: Algorithm must be simple, generic and practical such that it can be
executed with the available resources to generate the desired result(s).
6. Language Independent: An algorithm must be language independent. It means
that an algorithm can be implemented in any programming language and capable
produce the same result(s) as output.

Example of Designing Algorithm:

An Algorithm designing technique to find out the greatest number among three
integers.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

STEP-1: Start
STEP-2: Declare three integer variables x, y and z;
STEP-3: if x>y and x>z print x is the greatest.
STEP-4: else if y>x and y>z print y is the greatest.
STEP-5: else print z is the greatest.
STEP-6: Stop.

Alternative Approach (Using Flow Chart):

An Algorithm designing technique to find out the greatest number among three integers.

Data Abstraction:
Definition: Data abstraction is a principle of data modeling theory that emphasizes the
method of hiding the details information about the internal implementation strategies
over the data from the user, but it only provides the functionalities of the data.
Properties:
1. Abstraction is the method of hiding the internal details of the unwanted
information from the end user.
2. It can be implemented using abstract classes and interfaces.
3. Data abstraction is useful to solve an issue at the design level.
4. In data abstraction, implementation complexities are hidden using abstract
classes and interfaces.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

5. It only focuses on the external lookout of the data used in a program.

Advantages:
1. Data abstraction allows users to focus on the basic functionalities of the data
without having to understand its complex operations.
2. Data abstraction makes things simpler as well as easier to change, implement and
document.
3. It is very useful for simplify the design, optimization and indexing and ultimately
increase the maintainability of the solution.
Disadvantages:
1. Data abstraction offers complexity at many levels of the database that might
create confusion for developers.
2. The navigation becomes extremely difficult when an extra layer is added to the
code.

Set: Sets are associative containers that store unique elements following a specific
order. Following are the properties of sets:

 Stores the values in sorted order.

 Stores only unique values. It means that in Set duplicate values are not allowed to get
stored.
 Elements can only be inserted or deleted but cannot be modified.
 We can erase more than 1 element by giving the start iterator and end iterator
position.
 Traversal using iterations.
 Sets are implemented as Binary Search Tree.

Multi-set: Multi-sets are associative containers that store multiple elements having
equivalent values following a specific order. Following are the properties of multi-
sets:

 Stores elements in sorted order.

 It allows the storage of multiple elements. It means that in Multi-set duplicate values
are allowed to get stored.
 We can erase more than 1 element by giving the start iterator and end iterator.

Stack: stack can be defined as a container in which data insertion and data deletion
operations can be done from the one end known as the top of the stack.

Properties:

1. Stack is a linear type data structure and abstract data type in nature.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

2. It contains only one pointer called top pointer which is used for pointing to the
topmost element of the stack.

3. Whenever an element is added in the stack, it is added on the top of the stack and
the element can be deleted only from the top of the stack.
4. Stack follows the LIFO (Last In First Out) of FILO (First In Last Out) working
principle to insert and delete the elements.
5. It is called as stack because it behaves like a real-world stack, piles of books, etc.
6. A Stack is an abstract data type with a pre-defined capacity, which means that it
can store the elements of a limited size.

Working Principle of Stack:

Stack works on the LIFO pattern. As we can observe in the below figure there are five
memory blocks in the stack; therefore, the size of the stack is 5.

Suppose we want to store the elements in a stack and let's assume that stack is empty.
We have taken the stack of size 5 as shown below in which we are pushing the elements
one by one until the stack becomes full.

Since our stack is full as the size of the stack is 5. In the above cases, we can observe that
it goes from the top to the bottom when we were entering the new element in the stack.
The stack gets filled up from the bottom to the top.

When we perform the delete operation on the stack, there is only one way for entry and
exit as the other end is closed. It follows the LIFO pattern, which means that the value
entered first will be removed last. In the above case, the value 1 is entered first, so it will
be removed only after the deletion of all the other elements.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

Standard Stack Operations:

The following are some common operations implemented on the stack:

o push(): When we insert an element in a stack then the operation is known as a

push. If the stack is full then the overflow condition occurs.
o pop(): When we delete an element from the stack, the operation is known as a
pop. If the stack is empty means that no element exists in the stack, this state is
known as an underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.

PUSH operation

The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is
empty.
o When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new position
of the top.
o The elements will be inserted until we reach the max size of the stack.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

POP operation:

The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is empty.
o If we try to delete the element from the empty stack, then
the underflow condition occurs.
o If the stack is not empty, we first access the element which is pointed by the top
o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

Queue: A Queue can be defined as a container in which data insertion and data deletion
operations can be done from the rear and front end of the queue respectively.
Properties:
1. Queue is a linear type data structure and abstract data type in nature.

2. It contains two ends, one end is called Rear and another end is called Front.

3. The insertion and deletion operation on an element for the Queue should be
done from the Rear and Front end of the Queue respectively.
4. Queue follows the FIFO (First In First Out) or LILO (Last In Last Out) working
principle to insert and delete the elements.
5. A Queue is an abstract data type with a pre-defined capacity, which means that it
can store the elements of a limited size.

Types of Queue

There are four different types of queue that are listed as follows -

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

o Simple Queue or Linear Queue

o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Simple Queue or Linear Queue:

In Linear Queue, an insertion takes place from one end while the deletion occurs from
another end. The end at which the insertion takes place is known as the rear end, and the
end at which the deletion takes place is known as front end. It strictly follows the FIFO
rule.

The major drawback of using a linear Queue is that insertion is done only from the rear
end. If the first three elements are deleted from the Queue, we cannot insert more
elements even though the space is available in a Linear Queue. In this case, the linear
Queue shows the overflow condition as the rear is pointing to the last element of the
Queue.

Circular Queue:

In Circular Queue, all the nodes are represented as circular. It is similar to the linear
Queue except that the last element of the queue is connected to the first element. It is also
known as Ring Buffer, as all the ends are connected to another end. The representation
of circular queue is shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue. If
the empty space is available in a circular queue, the new element can be added in an
empty space by simply incrementing the value of rear. The main advantage of using the
circular queue is better memory utilization.

Priority Queue

It is a special type of queue in which the elements are arranged based on the priority. It
is a special type of queue data structure in which every element has a priority associated

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

with it. Suppose some elements occur with the same priority, they will be arranged
according to the FIFO principle. The representation of priority queue is shown in the
below image -

Insertion in priority queue takes place based on the arrival, while deletion in the priority
queue occurs based on the priority. Priority queue is mainly used to implement the CPU
scheduling algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be

inserted in arbitrary order, but only smallest can be deleted first. Suppose an array
with elements 7, 5, and 3 in the same order, so, insertion can be done with the
same sequence, but the order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be
inserted in arbitrary order, but only the largest element can be deleted first.
Suppose an array with elements 7, 3, and 5 in the same order, so, insertion can be
done with the same sequence, but the order of deleting the elements is 7, 5, 3.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both ends of
the queue either from the front or rear. It means that we can insert and delete elements
from both front and rear ends of the queue. Deque can be used as a palindrome checker
means that if we read the string from both ends, then the string would be the same.

Deque can be used both as stack and queue as it allows the insertion and deletion
operations on both ends. Deque can be considered as stack because stack follows the LIFO
(Last In First Out) principle in which insertion and deletion both can be performed only
from one end. And in deque, it is possible to perform both insertion and deletion from
one end, and Deque does not follow the FIFO principle.

The representation of the deque is shown in the below image -

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue, insertion
operation can be performed at only one end, while deletion can be performed from
both ends.

o Output restricted deque - As the name implies, in output restricted queue,

deletion operation can be performed at only one end, while insertion can be
performed from both ends.

Now, let's see the operations performed on the queue.

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

o Enqueue: The Enqueue operation is used to insert the element at the rear end of
the queue. It returns void.
o Dequeue: It performs the deletion from the front-end of the queue. It also returns
the element which has been removed from the front-end. It returns an integer
value.
o Peek: This is the third operation that returns the element, which is pointed by the
front pointer in the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is
completely full.
o Queue underflow (isempty): It shows the underflow condition when the Queue
is empty, i.e., no elements are in the Queue.

Asymptotic Notation: Asymptotic analysis of an algorithm refers to defining the

mathematical bound/framing of its run-time performance. Using asymptotic analysis, we
can precisely 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. For example, the running time of one operation is
computed as f (n) and may be for another operation it is computed as g (n2). This means
the first operation running time will increase linearly with the increase in n and the
running time of the second operation will increase exponentially when n increases.
Similarly, the running time of both operations will be nearly the same if n is significantly
small.

Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.

 Big Oh - Ο Notation.
 Big Omega - Ω Notation.
 Theta - θ Notation.

 Big Oh - Ο Notation: The function f (n) = O (g (n)) if and only if there exist positive
constants c, n0 such that f (n) ≤ c * g (n), ∀n ≥ n0. Big-oh can be used to denote all
upper bounds on the time complexity of an algorithm. Big-oh also captures the
worst case analysis of an algorithm.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

Examples:
10n2 + 4n + 2 = O (n2), such that 10n2 + 4n + 2 ≤ 11.n2, where c = 11, ∀n ≥ 5
Note that 10n2 + 4n + 2 is O(n2 ), O(n3 ), O(2n ), O(10n) as per the definition. i.e., it captures
all upper bounds. For the above example, O (n) is a tight upper bound whereas the rest
are loose upper bounds.

The notation Ο (n) is the formal way to express 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.

 Big Omega - Ω Notation: The function f (n) = Ω (g (n)) if and only if there exist
positive constants c, n0 such that f (n) ≥ c * g (n), ∀n ≥ n0. Omega can be used to
denote all lower bounds of an algorithm.

Example:
2n2 + n log n + 1 = Ω (n2) such that 2n2 + n log n + 1 ≥ 2.n2, where c = 2, ∀n ≥ 1

Note that 2n2 + n log n + 1 is Ω (1), Ω (n), Ω (log n), and Ω (n log n) as per the definition.
i.e., it captures all lower bounds. For the above example, Ω (n2) is a tight lower bound
whereas the rest are loose lower bounds.

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

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.

 Theta - θ Notation: The function f (n) = Θ (g (n)) if and only if there exist positive
constants c1, c2, n0 such that c1 * g (n) ≤ f (n) ≤ c2 * g (n), ∀n ≥ n0. Theta can be used
to denote tight bounds of an algorithm. i.e., g (n) is a lower bound as well as an
upper bound for f (n). Note that f (n) = Θ (g (n)) if and only if f (n) = Ω (g (n)) and f
(n) = O (g (n)).

Example:
2n2 + n log n + 1 = Θ (n2) such that 2n2 ≤ 2n2 + n log n + 1 ≤ 5n2, where ∀n ≥ 2, c1 = 2, c2 = 5

Computer Science & Technology Page No 1

Subject: Algorithm Unit-1: Fundamentals of Algorithms

The notation θ (n) is the formal way to express both the lower bound and the upper
bound of an algorithm's running time.

Difference Between Big oh, Big Omega and Big Theta:

Sl Big Oh - Ο Notation Big Omega - Ω Notation Big Theta - θ Notation

No
1 Big Omega (Ω) It is like (==)
It is like (<=) It is like (>=) meaning the rate of
rate of growth of an rate of growth is greater growth is equal to a
algorithm is less than or than or equal to a specified value.
equal to a specific value. specified value.

2 The algorithm’s lower The bounding of

The upper bound of bound is represented by function from above and
algorithm is represented Omega notation. The below is represented by
by Big O notation. Only asymptotic lower bound theta notation. The
the above function is is given by Omega exact asymptotic
bounded by Big O. notation. behaviour is done by
Asymptotic upper bound this theta notation.
is given by Big O
notation

3 Big Omega (Ω) – Lower Big Theta (Θ) – Tight

Big oh (O) – Upper Bound Bound
Bound

4 It is define as upper It is define as lower It is define as tightest

bound and upper bound bound and lower bound bound and tightest
on an algorithm is the on an algorithm is the bound is the best of all
most amount of time least amount of time the worst case times
required ( the worst required (the most that the algorithm can
case performance). efficient way possible, in take.
other words best case).
5 Mathematically: Big Oh Mathematically: Big Mathematically – Big
is 0 <= f(n) <= Cg(n) for Omega is 0 <= Cg(n) <= Theta is 0 <= C2g(n) <=
all n >= n0 f(n) for all n >= n0 f(n) <= C1g(n) for n >=
n0

Computer Science & Technology Page No 1