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?

There are no well-defined standards for writing algorithms. Rather, it is problem and resource
dependent. Algorithms are never written to support a particular programming code.
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.
We write algorithms in a step-by-step manner, but it is not always the case. Algorithm
writing is a process and is executed after the problem domain is well-defined. That is, we
should know the problem domain, for which we are designing a solution.
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
Algorithms tell the programmers how to code the program. Alternatively, the algorithm can
be written as −
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c←a+b
Step 4 − display c
Step 5 − STOP
In design and analysis of algorithms, usually the second method is used to describe an
algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted
definitions. He can observe what operations are being used and how the process is flowing.
Writing step numbers, is optional.
We design an algorithm to get a solution of a given problem. A problem can be solved in
more than one ways.

Hence, many solution algorithms can be derived for a given problem. The next step is to
analyze those proposed solution algorithms and implement the best suitable solution.
Pseudo code is a term which is often used in programming and
algorithm based fields. It is a methodology that allows the
programmer to represent the implementation of an algorithm.
Simply, we can say that it’s the cooked up representation of an
algorithm. Often at times, algorithms are represented with the help
of pseudo codes as they can be interpreted by programmers no
matter what their programming background or knowledge is.
Pseudo code, as the name suggests, is a false code or a
representation of code which can be understood by even a layman
with some school level programming knowledge. Algorithm: It’s
an organized logical sequence of the actions or the approach
towards a particular problem. A programmer implements an
algorithm to solve a problem. Algorithms are expressed using
natural verbal but somewhat technical annotations. Pseudo
code: It’s simply an implementation of an algorithm in the form of
annotations and informative text written in plain English. It has no
syntax like any of the programming language and thus can’t be
compiled or interpreted by the computer.
Advantages of Pseudocode
 Improves the readability of any approach. It’s one of the
best approaches to start implementation of an algorithm.
 Acts as a bridge between the program and the algorithm or
flowchart. Also works as a rough documentation, so the
program of one developer can be understood easily when a
pseudo code is written out. In industries, the approach of
documentation is essential. And that’s where a pseudo-
code proves vital.
 The main goal of a pseudo code is to explain what exactly
each line of a program should do, hence making the code
construction phase easier for the programmer.
How to write a Pseudo-code?
1. Arrange the sequence of tasks and write the pseudocode
accordingly.
2. Start with the statement of a pseudo code which
establishes the main goal or the aim. Example:
This program will allow the user to check
the number whether it's even or odd.
1. The way the if-else, for, while loops are indented in a
program, indent the statements likewise, as it helps to
comprehend the decision control and execution
mechanism. They also improve the readability to a great
extent.

Example:

if "1"
 print response
"I am case 1"

if "2"
print response
"I am case 2"

1. Use appropriate naming conventions. The human tendency

follows the approach to follow what we see. If a
programmer goes through a pseudo code, his approach will
be the same as per it, so the naming must be simple and
distinct.
2. Use appropriate sentence casings, such as CamelCase for
methods, upper case for constants and lower case for
variables.
3. Elaborate everything which is going to happen in the actual
code. Don’t make the pseudo code abstract.
4. Use standard programming structures such as ‘if-then’,
‘for’, ‘while’, ‘cases’ the way we use it in programming.
5. Check whether all the sections of a pseudo code is
complete, finite and clear to understand and comprehend.
6. Don’t write the pseudo code in a complete programmatic
manner. It is necessary to be simple to understand even for
a layman or client, hence don’t incorporate too many
technical terms.
 Dos and Don’ts to Pseudo Code Writing

Example:
Let’s have a look at this code
 C++
 Java
 C#

#include <iostream>

long long gcd(long long numberOne, long long numberTwo) {

if (numberTwo == 0)
return numberOne;

return gcd(numberTwo, numberOne % numberTwo);

}

long long lcmNaive(long long numberOne, long long numberTwo) {

long long lowestCommonMultiple = (numberOne * numberTwo) /
gcd(numberOne, numberTwo);
return lowestCommonMultiple;
}

int main() {
std::cout << "Enter the inputs" << std::endl;
long long numberOne, numberTwo;
std::cin >> numberOne >> numberTwo;

std::cout << lcmNaive(numberOne, numberTwo) << std::endl;

return 0;
}

FLOWCHARTS

Definitions:

A flowchart is a schematic representation of an algorithm or a stepwise process,

showing the steps as boxes of various kinds, and their order by connecting these
with arrows. Flowcharts are used in designing or documenting a process or
program.
A flow chart, or flow diagram, is a graphical representation of a process or
system that details the sequencing of steps required to create output.
A flowchart is a picture of the separate steps of a process in sequential order.

TYPES:

High-Level Flowchart

A high-level (also called first-level or top-down) flowchart shows the major

steps in a process. It illustrates a "birds-eye view" of a process, Such a flowchart
offers a basic picture of the process and identifies the changes taking place
within the process. It is significantly useful for identifying appropriate team
members (those who are involved in the process) and for developing indicators
for monitoring the process because of its focus on intermediate outputs.

Most processes can be adequately portrayed in four or five boxes that represent
the major steps or activities of the process. In fact, it is a good idea to use only a
few boxes, because doing so forces one to consider the most important steps.
Other steps are usually sub-steps of the more important ones.

Detailed Flowchart

The detailed flowchart provides a detailed picture of a process by mapping all

of the steps and activities that occur in the process. This type of flowchart
indicates the steps or activities of a process and includes such things as decision
points, waiting periods, tasks that frequently must be redone (rework), and
feedback loops. This type of flowchart is useful for examining areas of the
process in detail and for looking for problems or areas of inefficiency.
Deployment or Matrix Flowchart

A deployment flowchart maps out the process in terms of who is doing the
steps. It is in the form of a matrix, showing the various participants and the flow
of steps among these participants. It is chiefly useful in identifying who is
providing inputs or services to whom, as well as areas where different people
may be needlessly doing the same task. See the Deployment of Matrix
Flowchart.
ADVANTAGES OF USING FLOWCHARTS

The benefits of flowcharts are as follows:

1. Communication: Flowcharts are better way of communicating the logic of a

system to all concerned.

2. Effective analysis: With the help of flowchart, problem can be analysed in

more effective way.

[Link] documentation: Program flowcharts serve as a good program

documentation, which is needed for various purposes.

4. Efficient Coding: The flowcharts act as a guide or blueprint during the

systems analysis and program development phase.

5. Proper Debugging: The flowchart helps in debugging process.

6. Efficient Program Maintenance: The maintenance of operating program

becomes easy with the help of flowchart. It helps the programmer to put efforts
more efficiently on that part

Advantages:

· Logic Flowcharts are easy to [Link] provide a graphical

representation of actions to be taken.

· Logic Flowcharts are well suited for representing logic where there is
intermingling among many actions.
 Disadvantages:

· Logic Flowcharts may encourage the use of GoTo statements

leadingsoftware design that is unstructured with logic that is difficult to
decipher.

· Without an automated tool, it is time-consuming to maintain Logic

Flowcharts.

· Logic Flowcharts may be used during detailed logic design to specify a

module.

· However, the presence of decision boxes may encourage the use of GoTo
statements, resulting in software that is not structured. For this reason, Logic
Flowcharts may be better used during Structural Design

LIMITATIONS OF USING FLOWCHARTS

1. Complex logic: Sometimes, the program logic is quite complicated. In

that case, flowchart becomes complex and clumsy.

2. Alterations and Modifications: If alterations are required the flowchart

may require re-drawing completely.

3. Reproduction: As the flowchart symbols cannot be typed, reproduction

of flowchart becomes a problem.

4. The essentials of what is done can easily be lost in the technical details of
how it is done.
 GUIDELINES FOR DRAWING A FLOWCHART

Flowcharts are usually drawn using some standard symbols; however, some
special symbols can also be developed when required. Some standard symbols,
which are frequently required for flowcharting many computer programs.
The following are some guidelines in flowcharting:

(a) In drawing a proper flowchart, all necessary requirements should be

listed out in logical order.

(b) The flowchart should be clear, neat and easy to follow. There should
not be any room for ambiguity in understanding the flowchart.
(c) The usual direction of the flow of a procedure or system is from left
to right or top to bottom.

(d) Only one flow line should come out from a process symbol.

(e) Only one flow line should enter a decision symbol, but two or three
flow lines, one for each possible answer, should leave the decision
symbol.

(f) Only one flow line is used in conjunction with terminal symbol.
(g) Write within standard symbols briefly. As necessary, you can use the
annotation symbol to describe data or computational steps more
clearly.

(h) If the flowchart becomes complex, it is better to use connector

symbols to reduce the number of flow lines. Avoid the intersection of
flow lines if you want to make it more effective and better way of
communication.

(i) Ensure that the flowchart has a logical start and finish.

(j) It is useful to test the validity of the flowchart by passing through it

with a simple test data.

Examples

Sample flowchart
A flowchart for computing factorial N (N!) Where N! = 1 * 2 * 3 *...* N. This
flowchart represents a "loop and a half" — a situation discussed in introductory
programming textbooks that requires either a duplication of a component (to be
both inside and outside the loop) or the component to be put inside a branch in
the loop

Sample Pseudocode
ALGORITHM Sample
GET Data
WHILE There Is Data
DO Math Operation
GET Data
END WHILE
END ALGORITHM

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 impleme nted using programming language. This is then
executed on target computer machine. In this analysis, actual statistics like
running time and space required, are collected.
We shall learn about a priori algorithm analysis. Algorithm analysis deals with the execution
or running time of various operations involved. The running time of an operation can be
defined as the number of computer instructions executed per operation.

Algorithm Complexity
 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.

Space Complexity
Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle. The space required by an algorithm is equal to the sum of the
following two components −
 A fixed part that is a space required to store certain data and variables, that are
independent of the size of the problem. For example, simple variables and
constants used, program size, etc.
 A variable part is a space required by variables, whose size depends on the size
of the problem. For example, dynamic memory allocation, recursion stack
space, etc.
Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part and
S(I) is the variable part of the algorithm, which depends on instance characteristic I.
Following is a simple example that tries to explain the concept −
Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop
Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3. Now, space
depends on data types of given variables and constant types and it will be multiplied
accordingly.
Time Complexity
Time complexity of an algorithm represents the amount of time required by the algorithm to
run to completion. Time requirements can be defined as a numerical function T(n), where
T(n) can be measured as the number of steps, provided each step consumes constant time.

computational time is T(n) = c ∗ n, where c is the time taken for the addition of two bits.
For example, addition of two n-bit integers takes n steps. Consequently, the total

Here, we observe that T(n) grows linearly as the input size increases.
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 is input bound i.e., if there's no input to the algorithm,
it is concluded to work in a constant time. Other than the "input" all other
factors are considered constant.
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
Following are the commonly used asymptotic notations to calculate the
running time complexity of an algorithm.
 Ο − Big Oh Notation
 Ω − Big Omega Notation
 Θ − Theta Notation
 o − Little Oh Notation
 ω − Little Omega Notation

Big Oh Notation, Ο
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.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n)(upper
bound) for all n > n0. }
Example
Let us consider a given function, f(n) = 4.n3+10.n2+5.n+1.
Considering g(n) = n3
f(n) ≥ 5.g(n) for all the values of n > 2.
Hence, the complexity of f(n) can be represented
as O (g (n) ) ,i.e. O (n3).

Big Omega Notation, Ω

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. }
Example
Let us consider a given function, f(n) = 4.n3+10.n2+5.n+1
Considering g(n) = n3 , f(n) ≥ 4.g(n) for all the values of n > 0.
Hence, the complexity of f(n) can be represented
as Ω (g (n) ) ,i.e. Ω (n3).

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. 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. It is represented as follows −
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }
Example
Let us consider a given function, f(n) = 4.n3+10.n2+5.n+1
Considering g(n) = n3 , 4.g(n)≤ f(n)≤ 5.g(n) for all the values of n.
Hence, the complexity of f(n) can be represented
as Ɵ (g (n) ) ,i.e. Ɵ (n3).

Little Oh (o) and Little Omega (ω) Notations

The Little Oh and Little Omega notations also represent the best and
worst case complexities but they are not asymptotically tight in contrast
to the Big Oh and Big Omega Notations. Therefore, the most commonly
used notations to represent time complexities are Big Oh and Big Omega
Notations only.

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)

exponential − 2O(n)

Data Structures

What is Data Structure?

The data structure name indicates itself that organizing the data in
memory. There are many ways of organizing the data in the memory as
we have already seen one of the data structures, i.e., array in C language.
Array is a collection of memory elements in which data is stored
sequentially, i.e., one after another. In other words, we can say that array
stores the elements in a continuous manner. This organization of data is
done with the help of an array of data structures. There are also other
ways to organize the data in memory. Let's see the different types of data
structures.

The data structure is not any programming language like C, C++, java,
etc. It is a set of algorithms that we can use in any programming language
to structure the data in the memory.

To structure the data in memory, 'n' number of algorithms were proposed,

and all these algorithms are known as Abstract data types. These abstract
data types are the set of rules.

Types of Data Structures

There are two types of data structures:

o Primitive data structure

o Non-primitive data structure

Primitive Data structure

The primitive data structures are primitive data types. The int, char, float,
double, and pointer are the primitive data structures that can hold a
single value.

Non-Primitive Data structure

The non-primitive data structure is divided into two types:

o Linear data structure

o Non-linear data structure

Linear Data Structure

The arrangement of data in a sequential manner is known as a linear data

structure. The data structures used for this purpose are Arrays, Linked list,
Stacks, and Queues. In these data structures, one element is connected to
only one another element in a linear form.

When one element is connected to the 'n' number of elements

known as a non-linear data structure. The best example is trees
and graphs. In this case, the elements are arranged in a random
manner.

Now, we will see the common operations that we can perform on these
data structures.

Data structures can also be classified as:

o Static data structure: It is a type of data structure where the size

is allocated at the compile time. Therefore, the maximum size is
fixed.
o Dynamic data structure: It is a type of data structure where the
size is allocated at the run time. Therefore, the maximum size is
flexible.
o Data structure where data elements are arranged sequentially
or linearly where each and every element is attached to its
previous and next adjacent is called a linear data structure.
In linear data structure, single level is involved. Therefore, we
 can traverse all the elements in single run only. Linear data
structures are easy to implement because computer memory
is arranged in a linear way. Its examples
are array, stack, queue, linked list, etc.

o 1. Array
o The array is a type of data structure that stores elements of
the same type. These are the most basic and fundamental
data structures. Data stored in each position of an array is
given a positive value called the index of the element. The
index helps in identifying the location of the elements in an
array.
o If supposedly we have to store some data i.e. the price of ten
cars, then we can create a structure of an array and store all
the integers together. This doesn’t need creating ten separate
integer variables. Therefore, the lines in a code are reduced
and memory is saved. The index value starts with 0 for the
first element in the case of an array.
o 2. Stack
o The data structure follows the rule of LIFO (Last In-First Out)
where the data last added element is removed first. Push
operation is used for adding an element of data on a stack
and the pop operation is used for deleting the data from the
stack. This can be explained by the example of books stacked
together. In order to access the last book, all the books placed
on top of the last book have to be safely removed.
o 3. Queue
o This structure is almost similar to the stack as the data is
stored sequentially. The difference is that the queue data
structure follows FIFO which is the rule of First In-First Out
where the first added element is to exit the queue first. Front
and rear are the two terms to be used in a queue.
o Enqueue is the insertion operation and dequeue is the
deletion operation. The former is performed at the end of the
queue and the latter is performed at the start end. The data
structure might be explained with the example of people
queuing up to ride a bus. The first person in the line will get
the chance to exit the queue while the last person will be the
last to exit.
o 4. Linked List
o Linked lists are the types where the data is stored in the form
of nodes which consist of an element of data and a pointer.
The use of the pointer is that it points or directs to the node
which is next to the element in the sequence. The data stored
in a linked list might be of any form, strings, numbers, or
 characters. Both sorted and unsorted data can be stored in a
linked list along with unique or duplicate elements.
o 5. Hash Tables
o These types can be implemented as linear or non-linear data
structures. The data structures consist of key-value pairs.
o Non-linear Data Structure:
Data structures where data elements are not arranged
sequentially or linearly are called non-linear data
structures. In a non-linear data structure, single level is not
involved. Therefore, we can’t traverse all the elements in
single run only. Non-linear data structures are not easy to
implement in comparison to linear data structure. It utilizes
computer memory efficiently in comparison to a linear data
structure. Its examples are trees and graphs.
o 1. Trees
o A tree data structure consists of various nodes linked
together. The structure of a tree is hierarchical that forms a
relationship like that of the parent and a child. The structure
of the tree is formed in a way that there is one connection for
every parent-child node relationship. Only one path should
exist between the root to a node in the tree. Various types of
trees are present based on their structures like AVL tree,
binary tree, binary search tree, etc.
o 2. Graph
o Graphs are those types of non-linear data structures which
consist of a definite quantity of vertices and edges. The
vertices or the nodes are involved in storing data and the
edges show the vertices relationship. The difference between
a graph to a tree is that in a graph there are no specific rules
for the connection of nodes. Real-life problems like social
networks, telephone networks, etc. can be represented
through the graphs.
o

What is a Static Data structure?

In Static data structure the size of the structure is fixed. The
content of the data structure can be modified but without changing
the memory space allocated to it.
Example of Static Data Structures: Array

What is Dynamic Data Structure?

In Dynamic data structure the size of the structure is not fixed and
can be modified during the operations performed on it. Dynamic
data structures are designed to facilitate change of data structures
in the run time.

Example of Dynamic Data Structures: Linked List

Static Data Structure vs Dynamic Data Structure

 Static data structures, such as arrays, have a fixed size and
are allocated at compile-time. This means that their
memory size cannot be changed during program execution.
Index-based access to elements is fast and efficient since
the address of the element is known.
 Dynamic data structures, on the other hand, have a
variable size and are allocated at run-time. This means that
their memory size can be changed during program
execution. Memory can be dynamically allocated or
deallocated during program execution. Due to this dynamic
nature, accessing elements based on index may be slower
as it may require memory allocation and deallocation.

Aspect Static Data Structure Dynamic Data Structure

Memory Memory is allocated at

Memory is allocated at run-time
allocation compile-time

Size is fixed and cannot be Size can be modified during

Size
modified runtime

Memory Memory utilization may be Memory utilization is efficient as

 utilization inefficient memory can be reused

Access time is faster as it is Access time may be slower due to

Access
fixed indexing and pointer usage

Arrays, Stacks, Queues, Lists, Trees (with variable size),

Examples
Trees (with fixed size) Hash tables

Advantage of Static data structure :

 Fast access time: Static data structures offer fast access

time because memory is allocated at compile-time and the
size is fixed, which makes accessing elements a simple
indexing operation.
 Predictable memory usage: Since the memory
allocation is fixed at compile-time, the programmer can
precisely predict how much memory will be used by the
program, which is an important factor in memory-
constrained environments.
 Ease of implementation and optimization: Static data
structures may be easier to implement and optimize since
the structure and size are fixed, and algorithms can be
optimized for the specific data structure, which reduces
cache misses and can increase the overall performance of
the program.
 Efficient memory management: Static data structures
allow for efficient memory allocation and management.
Since the size of the data structure is fixed at compile-time,
memory can be allocated and released efficiently, without
the need for frequent reallocations or memory copies.
 Simplified code: Since static data structures have a fixed
size, they can simplify code by removing the need for
dynamic memory allocation and associated error checking.
 Reduced overhead: Static data structures typically have
lower overhead than dynamic data structures, since they
do not require extra bookkeeping to manage memory
allocation and deallocation.

Advantage Of Dynamic Data Structure :

 Flexibility: Dynamic data structures can grow or shrink at

runtime as needed, allowing them to adapt to changing
 data requirements. This flexibility makes them well-suited
for situations where the size of the data is not known in
advance or is likely to change over time.
 Reduced memory waste: Since dynamic data structures
can resize themselves, they can help reduce memory
waste. For example, if a dynamic array needs to grow, it
can allocate additional memory on the heap rather than
reserving a large fixed amount of memory that might not
be used.
 Improved performance for some operations: Dynamic
data structures can be more efficient than static data
structures for certain operations. For example, inserting or
deleting elements in the middle of a dynamic list can be
faster than with a static array, since the remaining
elements can be shifted over more efficiently.
 Simplified code: Dynamic data structures can simplify
code by removing the need for manual memory
management. Dynamic data structures can also reduce the
complexity of code for data structures that need to be
resized frequently.
 Scalability: Dynamic data structures can be more scalable
than static data structures, as they can adapt to changing
data requirements as the data grows.
o
o

o Difference between Linear and Non-linear Data

Structures:
S.N
O Linear Data Structure Non-linear Data Structure

In a linear data structure, data

elements are arranged in a linear order In a non-linear data structure, data
1. where each and every element is elements are attached in
attached to its previous and next hierarchically manner.
adjacent.

In linear data structure, single level is Whereas in non-linear data structure,

2.
involved. multiple levels are involved.

Its implementation is easy in

While its implementation is complex
3. comparison to non-linear data
in comparison to linear data structure.
structure.

While in non-linear data structure,

In linear data structure, data elements
4. data elements can’t be traversed in a
can be traversed in a single run only.
single run only.

While in a non-linear data structure,

In a linear data structure, memory is memory is utilized in an efficient
5.
not utilized in an efficient way. way.

Its examples are: array, stack, queue, While its examples are: trees and
6.
linked list, etc. graphs.

Applications of linear data structures Applications of non-linear data

7. are mainly in application software structures are in Artificial
development. Intelligence and image processing.

Non-linear data structures are useful

for representing complex
Linear data structures are useful for
8. relationships and data hierarchies,
simple data storage and manipulation.
such as in social networks, file
systems, or computer networks.

9. Performance is usually good for Performance can vary depending on

simple operations like adding or the structure and the operation, but
removing at the ends, but slower for can be optimized for specific
operations like searching or removing operations.
 S.N
O Linear Data Structure Non-linear Data Structure

elements in the middle.

Data Structure and Algorithm

An algorithm is a set of instructions to perform on some

data. Together, an algorithm and data structure make up a
program.

From the data structure point of view, the 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 an 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.

Data Structures are the programmatic way of storing data

so that data can be used efficiently.

Algorithms in most cases need data structures internally to

make them work as intended.

An example of a program with both data structures and

Algorithms:
A program that takes two lists and returns Fizz if the
combined length of the lists is divisible by 3, Buzz if
it is divisible by 5, Fizzbuzz if it is divisible by both 5
and 3 or the combined length of the list.

def fizzbuzz():

x=[1,2,4.5]

y=[6,7,0]

z=len(x)+len(y)

if z%3==0 and z%5==0:

print("FizzBuzz")

elif z%3==0:

print("Fizz")

elif z%5==0:

print("Buzz")

else:

print(z)
fizzbuzz()

Examples of Data Structures

An associative array (also called dictionary or map) is a

more flexible variation on an array, in which name-value
pairs can be added and deleted freely. A hash table is a
common implementation of an associative array.

 A record (also called tuple or struct) is an

aggregate data structure. A record is a value
that contains other values, typically in fixed
number and sequence and typically indexed
by names. The elements of records are
usually called fields or members.

 A union is a data structure that specifies

which of a number of permitted primitive
types may be stored in its instances, e.g. float
or long integer. Contrast with a record, which
could be defined to contain a float and an
integer; whereas in a union, there is only one
value at a time. Enough space is allocated to
contain the widest member datatype.

 A set is an abstract data structure that can

store specific values, in no particular order
and with no duplicate values.
  A graph and a tree are linked abstract data
structures composed of nodes. Each node
contains a value and one or more pointers to
other nodes arranged in a hierarchy. Graphs
can be used to represent networks, while
variants of trees can be used for sorting and
searching, having their nodes arranged in
some relative order based on their values.

 A class is a data structure that contains data

fields, like a record, as well as various
methods which operate on the contents of the
record. In the context of object-oriented
programming, records are known as plain old
data structures to distinguish them from
classes.

Both Algorithms and Data Structures are fundamental in

Computer Programming. Without one, the other could be
useless.

Introduction to Algorithmic strategies

An algorithm is a finite set of instructions to accomplish a particular task. It is a
step-by-step procedure for solving a given problem. An algorithm can be
implemented in any suitable programming language.
Algorithms must have input, output and should satisfy the following
characteristics such as definiteness, correctness and effectiveness. Data are
maintained and manipulated effectively through data structures. Algorithms can
be developed to store, manipulate and retrieve data from such data structures.
Examples for data structures are arrays, structures, list, tuples, dictionary etc.
Divide and Conquer
 Divide and Conquer
To understand the divide and conquer design strategy of algorithms, let
us use a simple real world example. Consider an instance where we need
to brush a type C curly hair and remove all the knots from it. To do that,
the first step is to section the hair in smaller strands to make the combing
easier than combing the hair altogether. The same technique is applied on
algorithms.
Divide and conquer approach breaks down a problem into multiple sub-
problems recursively until it cannot be divided further. These sub-
problems are solved first and the solutions are merged together to form
the final solution.
The com mon procedure for the divide and conquer design technique is as
follows −
 Divide − We divide the original problem into multiple sub-
problems until they cannot be divided further.
 Conquer − Then these subproblems are solved separately
with the help of recursion
 Combine − Once solved, all the subproblems are
merged/combined together to form the final solution of the
original problem.
There are several ways to give input to the divide and conquer algorithm
design pattern. Two major data structures used are − arrays and linked
lists. Their usage is explained as

Arrays as Input
There are various ways in which various algorithms can take input such
that they can be solved using the divide and conquer technique. Arrays
are one of them. In algorithms that require input to be in the form of a list,
like various sorting algorithms, array data structures are most commonly
used.
In the input for a sorting algorithm below, the array input is divided into
subproblems until they cannot be divided further.
Then, the subproblems are sorted (the conquer step) and are merged to
form the solution of the original array back (the combine step).

Since arrays are indexed and linear data structures, sorting algorithms
most popularly use array data structures to receive input.

Linked Lists as Input

Another data structure that can be used to take input for divide and
conquer algorithms is a linked list (for example, merge sort using linked
lists). Like arrays, linked lists are also linear data structures that store
data sequentially.
Consider the merge sort algorithm on linked list; following the very
popular tortoise and hare algorithm, the list is divided until it cannot be
divided further.

Then, the nodes in the list are sorted (conquered). These nodes are then
combined (or merged) in recursively until the final solution is achieved.

Various searching algorithms can also be performed on the linked list data
structures with a slightly different technique as linked lists are not indexed
linear data structures. They must be handled using the pointers available
in the nodes of the list.
Examples
The following computer algorithms are based on divide-and-
conquer programming approach −
 Merge Sort
 Quick Sort
 Binary Search
 Strassen's Matrix Multiplication
 Closest Pair
There are various ways available to solve any computer problem, but the
mentioned are a good example of divide and conquer approach.

Greedy Algorithm

An algorithm is designed to achieve optimum solution for a given problem.

In greedy algorithm approach, decisions are made from the given solution
domain. As being greedy, the closest solution that seems to provide an
optimum solution is chosen.
Greedy algorithms try to find a localized optimum solution, which may
eventually lead to globally optimized solutions. However, generally greedy
algorithms do not provide globally optimized solutions.

Counting Coins
This problem is to count to a desired value by choosing the least possible
coins and the greedy approach forces the algorithm to pick the largest
possible coin. If we are provided coins of € 1, 2, 5 and 10 and we are
asked to count € 18 then the greedy procedure will be −
 1 − Select one € 10 coin, the remaining count is 8
 2 − Then select one € 5 coin, the remaining count is 3
 3 − Then select one € 2 coin, the remaining count is 1
 4 − And finally, the selection of one € 1 coins solves the
problem
Though, it seems to be working fine, for this count we need to pick only 4
coins. But if we slightly change the problem then the same approach may
not be able to produce the same optimum result.
For the currency system, where we have coins of 1, 7, 10 value, counting
coins for value 18 will be absolutely optimum but for count like 15, it may
use more coins than necessary. For example, the greedy approach will
use 10 + 1 + 1 + 1 + 1 + 1, total 6 coins. Whereas the same problem
could be solved by using only 3 coins (7 + 7 + 1)
Hence, we may conclude that the greedy approach picks an immediate
optimized solution and may fail where global optimization is a major
concern.
Examples
Most networking algorithms use the greedy approach. Here is a list of few
of them −
 Travelling Salesman Problem
 Prim's Minimal Spanning Tree Algorithm
 Kruskal's Minimal Spanning Tree Algorithm
 Dijkstra's Minimal Spanning Tree Algorithm
 Graph − Map Coloring
 Graph − Vertex Cover
 Knapsack Problem
 Job Scheduling Problem
There are lots of similar problems that uses the greedy approach to find
an optimum solution.
Travelling Salesman Problem-

The travelling salesman problem is a graph computational problem where

the salesman needs to visit all cities (represented using nodes in a graph)
in a list just once and the distances (represented using edges in the
graph) between all these cities are known. The solution that is needed to
be found for this problem is the shortest possible route in which the
salesman visits all the cities and returns to the origin city.
If you look at the graph below, considering that the salesman starts from
the vertex ‘a’, they need to travel through all the remaining vertices b, c,
d, e, f and get back to ‘a’ while making sure that the cost taken is
minimum.

There are various approaches to find the solution to the travelling

salesman problem: naïve approach, greedy approach, dynamic
programming approach, etc.

Travelling Salesperson Algorithm

As the definition for greedy approach states, we need to find the best
optimal solution locally to figure out the global optimal solution. The
inputs taken by the algorithm are the graph G {V, E}, where V is the set
of vertices and E is the set of edges. The shortest path of graph G starting
from one vertex returning to the same vertex is obtained as the output.

Algorithm
 Travelling salesman problem takes a graph G {V, E} as an
input and declare another graph as the output (say G’) which
will record the path the salesman is going to take from one
node to another.
 The algorithm begins by sorting all the edges in the input
graph G from the least distance to the largest distance.
 The first edge selected is the edge with least distance, and
one of the two vertices (say A and B) being the origin node
(say A).
 Then among the adjacent edges of the node other than the
origin node (B), find the least cost edge and add it onto the
output graph.
 Continue the process with further nodes making sure there are
no cycles in the output graph and the path reaches back to the
origin node A.
 However, if the origin is mentioned in the given problem, then
the solution must always start from that node only. Let us look
at some example problems to understand this better.
Examples
Consider the following graph with six cities and the distances between
them −

From the given graph, since the origin is already mentioned, the solution
must always start from that node. Among the edges leading from A, A → B
has the shortest distance.
Then, B → C has the shortest and only edge between, therefore it is
included in the output graph.

There’s only one edge between C → D, therefore it is added to the output

graph.

There’s two outward edges from D. Even though, D → B has lower

distance than D → E, B is already visited once and it would form a cycle if
added to the output graph. Therefore, D → E is added into the output
graph.
There’s only one edge from e, that is E → F. Therefore, it is added into the
output graph.

Again, even though F → C has lower distance than F → A, F → A is added

into the output graph in order to avoid the cycle that would form and C is
already visited once.
The shortest path that originates and ends at A is A → B → C → D → E → F
→A
The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114.
Even though, the cost of path could be decreased if it originates from
other nodes but the question is not raised with respect to that.

Example
The complete implementation of Travelling Salesman Problem using
Greedy Approach is given below −

#include <stdio.h>

int tsp_g[10][10] = {

{12, 30, 33, 10, 45},

{56, 22, 9, 15, 18},

{29, 13, 8, 5, 12},

{33, 28, 16, 10, 3},

{1, 4, 30, 24, 20}

};

int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */

void travellingsalesman(int c){

int k, adj_vertex = 999;

int min = 999;

 /* marking the vertices visited in an assigned array */

visited[c] = 1;

/* displaying the shortest path */

printf("%d ", c + 1);

/* checking the minimum cost edge in the graph */

for(k = 0; k < n; k++) {

if((tsp_g[c][k] != 0) && (visited[k] == 0)) {

if(tsp_g[c][k] < min) {

min = tsp_g[c][k];

adj_vertex = k;

if(min != 999) {

cost = cost + min;

if(adj_vertex == 999) {

adj_vertex = 0;

printf("%d", adj_vertex + 1);

cost = cost + tsp_g[c][adj_vertex];

return;

travellingsalesman(adj_vertex);

/* main function */

int main(){

int i, j;

n = 5;
 for(i = 0; i < n; i++) {

visited[i] = 0;

printf("\n\nShortest Path:\t");

travellingsalesman(0);

printf("\n\nMinimum Cost: \t");

printf("%d\n", cost);

return 0;

Output
Shortest Path: 1 5 4 3 2 1

Minimum Cost: 99

ADT
Data types such as int, float, double, long, etc. are considered to be
in-built data types and we can perform basic operations with them
such as addition, subtraction, division, multiplication, etc. Now
there might be a situation when we need operations for our user-
defined data type which have to be defined. These operations can
be defined only as and when we require them. So, in order to
simplify the process of solving problems, we can create data
structures along with their operations, and such data structures
that are not in-built are known as Abstract Data Type (ADT).
Abstract Data type (ADT) is a type (or class) for objects whose
behavior is defined by a set of values and a set of operations. The
definition of ADT only mentions what operations are to be
performed but not how these operations will be implemented. It
does not specify how data will be organized in memory and what
algorithms will be used for implementing the operations. It is called
“abstract” because it gives an implementation-independent view.
The process of providing only the essentials and hiding the details
is known as abstraction.
The user of data type does not need to know how that data type is
implemented, for example, we have been using Primitive values
like int, float, char data types only with the knowledge that these
data type can operate and be performed on without any idea of
how they are implemented.
So a user only needs to know what a data type can do, but not how
it will be implemented. Think of ADT as a black box which hides the
inner structure and design of the data type. Now we’ll define three
ADTs namely List ADT, Stack ADT, Queue ADT.
1. List ADT

Vies of list

 The data is generally stored in key sequence in a list which

has a head structure consisting
of count, pointers and address of compare function needed
to compare the data in the list.
 The data node contains the pointer to a data structure and
a self-referential pointer which points to the next node in
the list.
 The List ADT Functions is given below:
  get() – Return an element from the list at any given
position.
 insert() – Insert an element at any position of the list.
 remove() – Remove the first occurrence of any element
from a non-empty list.
 removeAt() – Remove the element at a specified location
from a non-empty list.
 replace() – Replace an element at any position by another
element.
 size() – Return the number of elements in the list.
 isEmpty() – Return true if the list is empty, otherwise return
false.
 isFull() – Return true if the list is full, otherwise return false.

2. Stack ADT

View of stack

 In Stack ADT Implementation instead of data being stored

in each node, the pointer to data is stored.
 The program allocates memory for the data and address is
passed to the stack ADT.
 The head node and the data nodes are encapsulated in the
ADT. The calling function can only see the pointer to the
stack.
 The stack head structure also contains a pointer
to top and count of number of entries currently in stack.
 push() – Insert an element at one end of the stack called
top.
  pop() – Remove and return the element at the top of the
stack, if it is not empty.
 peek() – Return the element at the top of the stack without
removing it, if the stack is not empty.
 size() – Return the number of elements in the stack.
 isEmpty() – Return true if the stack is empty, otherwise
return false.
 isFull() – Return true if the stack is full, otherwise return
false.

3. Queue ADT

View of Queue

 The queue abstract data type (ADT) follows the basic

design of the stack abstract data type.
 Each node contains a void pointer to the data and the link
pointer to the next element in the queue. The program’s
responsibility is to allocate memory for storing the data.
 enqueue() – Insert an element at the end of the queue.
 dequeue() – Remove and return the first element of the
queue, if the queue is not empty.
 peek() – Return the element of the queue without removing
it, if the queue is not empty.
 size() – Return the number of elements in the queue.
 isEmpty() – Return true if the queue is empty, otherwise
return false.
 isFull() – Return true if the queue is full, otherwise return
false.

Features of ADT:

Abstract data types (ADTs) are a way of encapsulating data

and operations on that data into a single unit. Some of the
key features of ADTs include:
  Abstraction: The user does not need to know the
implementation of the data structure only essentials are
provided.
 Better Conceptualization: ADT gives us a better
conceptualization of the real world.
 Robust: The program is robust and has the ability to catch
errors.
 Encapsulation: ADTs hide the internal details of the data
and provide a public interface for users to interact with the
data. This allows for easier maintenance and modification
of the data structure.
 Data Abstraction: ADTs provide a level of abstraction
from the implementation details of the data. Users only
need to know the operations that can be performed on the
data, not how those operations are implemented.
 Data Structure Independence: ADTs can be
implemented using different data structures, such as arrays
or linked lists, without affecting the functionality of the
ADT.
 Information Hiding: ADTs can protect the integrity of the
data by allowing access only to authorized users and
operations. This helps prevent errors and misuse of the
data.
 Modularity: ADTs can be combined with other ADTs to
form larger, more complex data structures. This allows for
greater flexibility and modularity in programming.

Overall, ADTs provide a powerful tool for organizing and

manipulating data in a structured and efficient manner.
Abstract data types (ADTs) have several advantages and
disadvantages that should be considered when deciding to use
them in software development. Here are some of the main
advantages and disadvantages of using ADTs:

Advantages:

 Encapsulation: ADTs provide a way to encapsulate data

and operations into a single unit, making it easier to
manage and modify the data structure.
 Abstraction: ADTs allow users to work with data structures
without having to know the implementation details, which
can simplify programming and reduce errors.
 Data Structure Independence: ADTs can be
implemented using different data structures, which can
 make it easier to adapt to changing needs and
requirements.
 Information Hiding: ADTs can protect the integrity of data
by controlling access and preventing unauthorized
modifications.
 Modularity: ADTs can be combined with other ADTs to
form more complex data structures, which can increase
flexibility and modularity in programming.

Disadvantages:

 Overhead: Implementing ADTs can add overhead in terms

of memory and processing, which can affect performance.
 Complexity: ADTs can be complex to implement,
especially for large and complex data structures.
 Learning Curve: Using ADTs requires knowledge of their
implementation and usage, which can take time and effort
to learn.
 Limited Flexibility: Some ADTs may be limited in their
functionality or may not be suitable for all types of data
structures.
 Cost: Implementing ADTs may require additional resources
and investment, which can increase the cost of
development.

Overall, the advantages of ADTs often outweigh the disadvantages,

and they are widely used in software development to manage and
manipulate data in a structured and efficient way. However, it is
important to consider the specific needs and requirements of a
project when deciding whether to use ADTs.
From these definitions, we can clearly see that the definitions do
not specify how these ADTs will be represented and how the
operations will be carried out. There can be different ways to
implement an ADT, for example, the List ADT can be implemented
using arrays, or singly linked list or doubly linked list. Similarly,
stack ADT and Queue ADT can be implemented using arrays or
linked lists.