Design and Analysis of Algorithms Tutorial

An Algorithm is a sequence of steps to solve a problem. It acts like a set of instructions on how a program
should be executed.

The main aim of designing an algorithm is to provide a optimal solution for a problem. Not all problems
must have similar type of solutions; an optimal solution for one problem may not be optimal for another.
Therefore, we must adopt various strategies to provide feasible solutions for all types of

Why Design and Analysis of Algorithms?

We study Design and Analysis of Algorithms to analyse the complexity of all the versions of a solution to
a computer problem.

Design Strategies

There are various types of strategies in order to design algorithms for various problems. Some of them are
listed as follows −

 Greedy Approach

 Divide & Conquer Approach

 Dynamic Programming Approach

 Randomization Approach

 Approximation Approach

 Recursive Approach

 Branch and Bound Approach

In this tutorial, we will see various algorithms of each approach to solve various problems.

Analysis of Algorithms

To analyse the feasibility of an algorithm designed, we calculate the complexity of it. This is represented
in three notations, called asymptotic notations. Asymptotic notations are as follows −

 Worst-Case Scenario − Big Oh and Little Oh Notations

 Best-Case Scenario − Big Omega and Little Omega Notations

 Average-Case Scenario − Theta Notation

Each solution is analysed in all scenarios of the problem, and the solution having the best worst-case is
said to be optimal. Thus, providing an efficient algorithm.
Applications of DAA

There are applications of Design and Analysis of Algorithms (DAA) in a wide range of fields. Here are
some of the common fields where it is used:

 Computer programming: Used in computer programming to solve problems efficiently. This

includes developing algorithms for sorting, searching, and manipulating data structures.

 Big data processing: Also used to develop and analyses algorithms for operations such as data
mining, machine learning, and natural language processing, in order to handle large sets of data.

 Networking: Network protocols and algorithms are developed for routing, flow control,
congestion control, and network security. DAA is used to design and analyze these algorithms.

 Artificial intelligence: Used to design and analyze algorithms for tasks in Artificial Intelligence
such as computer vision, speech recognition, and natural language understanding.

 Scientific computing: DAA in scientific computing is used to develop algorithms for operations
like numerical integration, optimization, and simulation.

 Game development: In game development, we use design and analysis of algorithms for
pathfinding, collision detection, and physics simulation.

 Cryptography: DAA is also used in the design and analysis of cryptographic algorithms, such as
RSA and AES, which are used to secure data transmission and storage.

Who Should Learn DAA

This tutorial has been designed for students pursuing a degree in any computer science, engineering,
and/or information technology related fields. It attempts to help students to grasp the essential concepts
involved in algorithm design.

Data Structures - Algorithms Basics

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order
to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an
algorithm can be implemented in more than one programming language.

From the data structure point of view, following are some important categories of algorithms −

Search − Algorithm to search an item in a data structure.

Sort − Algorithm to sort items in a certain order.

Insert − Algorithm to insert item in a data structure.

Update − Algorithm to update an existing item in a data structure.

Delete − Algorithm to delete an existing item from a data structure.

Characteristics of an Algorithm

Not all procedures can be called an algorithm. An algorithm should have the following characteristics −

Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their
inputs/outputs should be clear and must lead to only one meaning.

Input − An algorithm should have 0 or more well-defined inputs.

Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output.

Finiteness − Algorithms must terminate after a finite number of steps.

Feasibility − Should be feasible with the available resources.

Independent − An algorithm should have step-by-step directions, which should be independent of any
programming code.

How to Write an Algorithm?

As we know that all programming languages share basic code constructs like loops (do, for, while), flow-
control (if-else), etc. These common constructs can be used to write an algorithm.

Example

Let's try to learn algorithm-writing by using an example.

Problem − Design an algorithm to add two numbers and display the result.

Step 1 − START

Step 2 − declare three integers a, b & c

Step 3 − define values of a & b

Step 4 − add values of a & b

Step 5 − store output of step 4 to c

Step 6 − print c

Step 7 − STOP

Algorithm Analysis

Efficiency of an algorithm can be analyzed at two different stages, before implementation and after
implementation. They are the following −
 A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured
by assuming that all other factors, for example, processor speed, are constant and have no effect on the
implementation.

A Posterior Analysis − This is an empirical analysis of an algorithm. The selected algorithm is

implemented using programming language. This is then executed on target computer machine. In this
analysis, actual statistics like running time and space required, are collected.

Algorithm Complexity

Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are
the two main factors, which decide the efficiency of X.

Time Factor − Time is measured by counting the number of key operations such as comparisons in the
sorting algorithm.

Space Factor − Space is measured by counting the maximum memory space required by the algorithm.

The complexity of an algorithm f(n) gives the running time and/or the storage space required by the
algorithm in terms of n as the size of input data.

Data Structures - Asymptotic Analysis

Asymptotic Analysis

Asymptotic analysis of an algorithm refers to defining the mathematical foundation/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. 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.

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.

Asymptotic Notations
Execution time of an algorithm depends on the instruction set, processor speed, disk I/O speed, etc.
Hence, we estimate the efficiency of an algorithm asymptotically.
 Time function of an algorithm is represented by T(n), where n is the input size.

Different types of asymptotic notations are used to represent the complexity of an algorithm.
Following asymptotic notations are used to calculate the running time complexity of an algorithm.

 O − Big Oh Notation
 Ω − Big omega Notation
 θ − Big theta Notation
 o − Little Oh Notation
 ω − Little omega Notation

Big Oh, O: Asymptotic Upper Bound

The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. is the
most commonly used notation. It measures the worst case time complexity or the longest amount of
time an algorithm can possibly take to complete.

Hence, function g(n) is an upper bound for function f(n), as g(n) grows faster than f(n).

Big Omega, Ω: Asymptotic Lower Bound

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. It means function g is a lower bound for function f ; after a certain value of n, f will never
go below g.
Theta, θ: Asymptotic Tight Bound

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an
algorithm's running time. Some may confuse the theta notation as the average case time complexity;
while big theta notation could be almost accurately used to describe the average case, other notations
could be used as well.

This means function g is a tight bound for function f.

Common Asymptotic Notations

Following is a list of some common asymptotic notations −

constant − O(1)

logarithmic − O(log n)

linear − O(n)

n log n − O(n log n)

quadratic − O(n2)

cubic − O(n3)

polynomial − nO(1)
Data Structure Basics
 Data Definition
Data Definition defines a particular data with the following characteristics.

 Atomic − Definition should define a single concept.

 Traceable − Definition should be able to be mapped to some data element.
 Accurate − Definition should be unambiguous.
 Clear and Concise − Definition should be understandable.

Data Object
Data Object represents an object having a data.

Data Type
Data type is a way to classify various types of data such as integer, string, etc. There are two data
types −

 Built-in Data Type

 Derived Data Type

Built-in Data Type

 Integers
 Boolean (true, false)
 Floating (Decimal numbers)
 Character and Strings

Derived Data Type

Those data types which are implementation independent as they can be implemented in one or the
other way are known as derived data types.

 List
 Array
 Stack
 Queue

Basic Operations
The data in the data structures are processed by certain operations.

 Traversing
 Searching
 Insertion
 Deletion
 Sorting
 Merging
Data Structures and Types
There are usually just two types of data structures −

 Linear
 Non-Linear

Linear Data Structures

Based on the data storage methods, these linear data structures are divided into two sub-types. They
are − static and dynamic data structures.

Non-Linear Data Structures

Few types of non-linear data structures are −

 Graphs
 Trees
 Tries
 Maps

What is an Array?
An array is a type of linear data structure that is defined as a collection of elements with same or
different data types.

Following are the important terms to understand the concept of Array.

 Element − Each item stored in an array is called an element.

 Index − Each location of an element in an array has a numerical index, which is used to identify the
element.

Syntax
Creating an array in C and C++ programming languages −
data_type array_name[array_size]={elements separated by commas}
or,
data_type array_name[array_size];
 Array Representation
Arrays are represented as a collection of buckets where each bucket stores one element. These
buckets are indexed from '0' to 'n-1', where n is the size of that particular array. For example, an array
with size 10 will have buckets indexed from 0 to 9.

 Index starts with 0.

 Array length is 9 which means it can store 9 elements.
 Each element can be accessed via its index. For example, we can fetch an element at index 6 as 23.
Stack Data Structure

What is a Stack?
A stack is a linear data structure where elements are stored in the LIFO (Last In First Out)
principle where the last element inserted would be the first element to be deleted. A stack is an
Abstract Data Type (ADT), that is popularly used in most programming languages. It is named stack
because it has the similar operations as the real-world stacks, for example − a pack of cards or a pile
of plates, etc.

Stack is considered a complex data structure because it uses other data structures for implementation,
such as Arrays, Linked lists, etc.
Stack Representation
A stack allows all data operations at one end only. At any given time, we can only access the top
element of a stack.

The following diagram depicts a stack and its operations −

Basic Operations on Stacks

The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of
the stack.

Stack Insertion: push()

The push() is an operation that inserts elements into the stack. The following is an algorithm that
describes the push() operation in a simpler way.

Frequently Asked Questions about DAA

There are many Frequently Asked Questions (FAQs) on Design and Analysis of Algorithms due to the
complex nature of this concept. In this section, we will try to answer some of them briefly.

What is Design and Analysis of Algorithms?

An algorithm is a set of instructions to solve a problem by performing calculations, data processing, or
automating reasoning tasks. However, there are always multiple solutions to solving a problem. Design
and Analysis of Algorithms provides various ways to design efficient algorithms to solve a problem by
analysing their complexities.

Why Analysis of Algorithms is important?

Algorithm analysis is an important part of computational complexity theory. The complexity theory
provides a theoretical estimation for the required algorithm resources to solve a computational problem.
For instance, most algorithms are designed to work with input data of variable length. Analysis of
algorithms determines the amount of time and space taken to execute such algorithms.

Which language is best for DAA?

As algorithms are not language specific, using any programming language that you are comfortable with
is recommended.

How important is algorithm design in computer systems?

Our basic aim while designing an algorithm is to maintain the efficiency of the solution. Algorithms are
used in almost all areas of computing. Hence, learning how to design an efficient algorithm is important.

How to test algorithms implementation?

To test the implementation of an algorithm, feed it with diverse types of inputs and observe the outputs
generated. If the time taken by the algorithm to be executed and space complexity are efficient even in
worst case inputs, your algorithm is feasible.

What is time complexity in design and analysis of algorithms?

Time complexity of an algorithm, in general, is simply defined as the time taken by an algorithm to
implement each statement in the code. Time complexity can be influenced by various factors like the
input size, the methods used and the procedure. An algorithm is said to be the most efficient when the
output is produced in the minimal time possible.

How do you find space complexity in DAA?

Space complexity is a function describing the amount of memory (space) an algorithm takes in terms of
the amount of input to the algorithm. So, it is usually computed by combining the auxiliary space and the
space used by input values.