Introduction to Algorithms & Data

Structure
Module 1 – Part 1
Gajendra Shrimal
Content
1. Introduction

2. Problem Solving

3. Data

4. Basic Terminology – Elementary Data Organization

5. Abstract Data Types

6. Data structures

7. Data Structure Operations

8. Static and Dynamic Data Structures

9. Static and Dynamic implementations

10. Algorithms
Introduction
In this part we will cover
 Data structures, Advantages and disadvantages, and use cases of different
data structures.
 Enhanced the knowledge about abstract data types (ADTs) and their
implementations.
 Data structures are the way data is organized and stored in a computer's
memory.
 Abstract Data Types (ADTs) define a set of operations on the data
structure without specifying its implementation.
 Static implementations have fixed sizes, while dynamic implementations
can resize and adapt as needed.
Problem Solving

 Programming is a process of problem solving

 Problem solving techniques
› Analyze the problem
› Outline the problem requirements
› Design steps (algorithm) to solve the problem
 Algorithm:
› Step-by-step problem-solving process
› Solution achieved in finite amount of time
Problem Solving Process

 Step 1 - Analyze the problem

› Outline the problem and its requirements
› Design steps (algorithm) to solve the problem
 Step 2 - Implement the algorithm
› Implement the algorithm in code
› Verify that the algorithm works
 Step 3 - Maintenance
› Use and modify the program if the problem domain
changes
Analyze the Problem

 Thoroughly understand the problem

 Understand problem requirements
› Does program require user interaction?
› Does program manipulate data?
› What is the output?
 If the problem is complex, divide it into
subproblems
› Analyze each subproblem as above
What is an algorithm?

 The idea behind the computer program

 Stays the same independent of
› Which kind of hardware it is running on
› Which programming language it is written in
 Solves a well-specified problem in a general way
 Is specified by
› Describing the set of instances (input) it must work on
› Describing the desired properties of the output
Important Properties of Algorithms

 Correct
› always returns the desired output for all legal instances of
the problem.
 Unambiguous
 Precise
 Efficient
› Can be measured in terms of
 Time
 Space
› Time tends to be more important
Importance of Data Structures and Algorithms:
Understanding data structures and algorithms is crucial for several
reasons:
 Efficient Data Management: Proper data structures enable efficient data
storage, retrieval, and manipulation, leading to better performance of
programs and systems.
 Optimized Operations: Efficient algorithms help in achieving faster and
more accurate results, reducing time and resource consumption.
 Problem-Solving Skills: Learning algorithms improves problem-solving
skills, allowing developers to devise effective solutions to various real-
world challenges.
 Code Optimization: Knowledge of data structures and algorithms
enables developers to write optimized and maintainable code.
 Interview and Career Advancement: Data structure and algorithm
knowledge is often a key factor in technical interviews and career
growth in the field of software development.
Data:
 Data refers to a collection of organized and interpretable information.
 It can encompass facts, statistics, measurements, observations, or any
other form of knowledge that can be recorded or represented.
 Data can exist in various formats such as text, numbers, images,
audio, or video.
 The collection of data is frequently organized into hierarchy of
fields, records and files. The data serves as the raw material for
analysis, decision-making, and understanding patterns or trends.

Attributes: Name Age Gender

Value: Peter 25 Male
Basic Terminology – Elementary Data Organization
Data organization involves how data is structured, stored, and accessed in a
computer system. The fundamental terminology includes:

 Value: The actual content or representation of the information. For example,

the value "42" represents a numeric data item, and "Hello, World!"
represents a string data item.

 Entity: An entity is an object or concept that is distinguishable from other

objects. In data organization, entities are used to represent real-world items
and are described by their attributes.

Example: Consider a "Student" entity. It can have attributes such as "Name,"

"Age," "Roll Number," and "Grade." Each student in the system represents a
distinct entity with its unique set of attributes.
Data Type
The data type defines the category of the data and specifies the
operations that can be performed on it. Common data types include:
Integer (int): Represents whole numbers (positive, negative, or
zero) without any fractional parts. Examples: 1, -5, 1000.
Floating-Point (float/double): Represents real numbers with
fractional parts. Examples: 3.14, -0.5, 2.71828.
Character (char): Represents individual characters, such as letters,
digits, or symbols. Examples: 'A', 'b', '7', '$'.
String: Represents a sequence of characters. Examples: "Hello",
"Data Structure", "12345".
Boolean (bool): Represents true or false values, used for logical
operations. Examples: true, false.
Array: Represents a collection of elements of the same data type,
organized in a linear or multidimensional structure.
Pointer: Represents the memory address of another data item.
ADT (Abstract Data Types)
Before going into ADT (Abstract Data Types) Lets understand Buit-in
Data Types

 Built-in data types in programming languages serve as the

foundation for implementing various data structures.

 While they are not themselves data structures, they are the basic
types that can be used to construct more complex data
structures. Here are some common built-in data types often used
in any programming language: Int, Float, Double, Long etc.

 The use of these built-in data types is to perform basic

mathematical operations like Addition, Subtraction, Multiplication,
Division etc. We might come into a situation where we need to
ADT (Abstract Data Types) Definition and types
 An abstract data type (ADT) is a high-level concept in
computer science that defines a set of operations on a
data structure, without specifying the implementation
details.
 It focuses on what the data structure can do rather than
how it is implemented.
 ADTs provide an abstraction or a logical description of data
that only provides interface to which data structure has to
be taken.
 ADTs abstract away the underlying implementation,
allowing programmers to work with data structures at a
higher level of abstraction.
 This interface does not provide any details of
implementation or which programming language is chosen.
 For example, the ADT of a stack defines operations like
push (adding an element), pop (removing and returning
the top element), and peek (accessing the top element
ADT (Abstract Data Types)
Data Structures
Data structures are fundamental tools used in
computer science to organize and store data
efficiently.
They can be classified into four main categories:
 Primitive data structures include basic types like
integers and floating-point numbers.
 Linear structures, such as arrays and linked
lists, organize data sequentially.
 Nonlinear structures, like trees and graphs,
establish hierarchical or interconnected
relationships between elements.
 File structures manage data on storage devices,
enabling efficient access and retrieval.
Data Structures classification
Data Structure Operations
Common Data Structure Operations

1. Traverse / Access: Visiting and accessing each element

only once in a specific order and Used for processing or
displaying data.
2. Insertion: Adding a new element to the data structure at a
specific position or based on rules.
3. Deletion: Removing an element from the data structure,
either from a specific position or based on conditions.
4. Search: Finding the presence of a specific element within
the data structure and returning its location or indicating
existence.
5. Sorting: Rearranging elements in a specific order
(ascending or descending) based on comparison rules.
Additional Data Structure Operations
1. Merging/Combining: Combining two or more data
structures into a single data structure. Typically used
for merging sorted lists or trees.
2. Splitting/Partitioning: Dividing a data structure into
multiple smaller data structures based on criteria or
conditions.
3. Concatenation: Joining or combining two or more
data structures of the same type into a single data
structure.
4. Copying/Cloning: Creating a duplicate or exact
replica of a data structure.
5. Resizing: Adjusting the size or capacity of a data
structure to accommodate more or fewer elements.
Arrays
Arrays: An array is a linear data structure that stores a
collection of elements of the same data type in contiguous
memory locations. Each element in the array is identified by an
index or a position, starting from 0 for the first element, 1 for
the second element, and so on.
Common Array Operations:
Insertion: Elements can be inserted at the end or at a specific
index in the array.
Deletion: Elements can be removed from the array, either by
shifting elements or marking them as deleted.
Traversal: Iterating through the array to access and process
each element.
Advantages of Arrays:
Random Access: Arrays allow direct access to elements using
their index, enabling quick retrieval.
Memory Efficiency: Arrays use contiguous memory, making
efficient use of memory.
Ease of Implementation: Arrays are simple to declare and use,
making them widely used in programming.
Limitations of Arrays:
Fixed Size: The size of an array is fixed during declaration, which
can lead to memory wastage or insufficient memory if not
estimated correctly.
Insertion and Deletion Overhead: Inserting or deleting
elements in the middle of an array requires shifting other
elements, leading to overhead.
Linked List
Linked List: A linked list is a linear data structure consisting
of a sequence of elements called "nodes," where each node
points to the next node in the list. Unlike arrays, linked lists do
not require contiguous memory allocation, making them more
flexible in size and easier to insert or delete elements.

Nodes in Linked List: Each node in a linked list contains two

components:
Data: The actual value or information stored in the node.
Pointer: A reference to the next node in the list. In a singly
linked list, this pointer points to the next node, whereas in a
doubly linked list, each node has a pointer to both the next
and the previous node.
Advantages of Linked Lists:
1. Dynamic Size: Linked lists can dynamically grow or shrink,
making them ideal for situations where the number of
elements changes frequently.
2. Insertion and Deletion Efficiency: Inserting or deleting
elements in a linked list is efficient as it involves updating
pointers, without the need for shifting elements.
3. Memory Efficiency: Linked lists use memory more efficiently
than arrays since they do not require contiguous memory
allocation.
Limitations of Linked Lists:
4. Random Access Overhead: Unlike arrays, accessing
elements in a linked list requires traversing the list, resulting
in slower random access.
5. Extra Memory Overhead: Each node in a linked list requires
additional memory to store the pointer, leading to extra
memory consumption.
Stack
The Stack Abstract Data Type (ADT) is a collection of elements that
follows the Last-In-First-Out (LIFO) principle. It can be visualized as
a stack of objects, where the last item added is the first one to be
removed
The Stack ADT supports the following operations:
 Push: Adds an element to the top of the stack.
 Pop: Removes and returns the element from the top of the
stack.
 Top: Returns the element at the top of the stack without
removing it.
 IsEmpty: Checks if the stack is empty or not.
 Size: Returns the number of elements currently in the stack.

These operations allow for efficient insertion and removal of

elements in constant time (O(1)).
Implementation of the Stack ADT
The implementation of the Stack ADT can be done using
various data structures. Two common approaches are:
 Array-based implementation: A fixed-size or dynamically
resizable array can be used to store the elements of the
stack. The top of the stack is tracked using an index, and
push and pop operations modify this index accordingly.
 Linked list-based implementation: A linked list can be
used, where each node contains the element and a
reference to the next node. The top of the stack is
represented by the head of the linked list. Push and pop
operations involve adding or removing nodes at the head of
the linked list.
Queue
Queue Abstract Data Type (ADT) is a collection of elements that
follows the First-In-First-Out (FIFO) principle. It can be visualized
as a queue of objects, where the first item added is the first one
to be removed.
The Queue ADT supports the following operations:
Enqueue: Adds an element to the back of the queue.
Dequeue: Removes and returns the element from the front of
the queue.
Peek (or Front): Returns the element at the front of the queue
without removing it.
IsEmpty: Checks if the queue is empty or not.
Size: Returns the number of elements currently in the queue.

These operations allow for efficient insertion and removal of

elements in constant time (O(1)).
TheImplementation
implementation of the of theADT
Queue Queuecan beADT
done using
various data structures. Two common approaches are:
Array-based implementation: A fixed-size or dynamically
resizable array can be used to store the elements of the queue.
Two indices, one for the front and one for the rear, track the
positions of the elements. Enqueue and dequeue operations
involve modifying these indices accordingly.
Linked list-based implementation: A linked list can be used,
where each node contains the element and a reference to the
next node. The front and rear of the queue are represented by
the head and tail of the linked list, respectively. Enqueue and
dequeue operations involve adding or removing nodes at the
appropriate ends of the linked list.
Queue
A queue is a linear data structure that follows the First-In-
First-Out (FIFO) principle. It resembles a real-life queue or
line, where the first person to join is the first one to be
served. Similarly, in a queue, the first element added is the
first one to be removed.
Basic Operations:
Enqueue (Insert): Adding an element to the rear (end) of
the queue.
Dequeue (Remove): Removing the front (first) element
from the queue.
Front (Peek): Viewing the front element without removing
it.
IsEmpty: Checking if the queue is empty.
Size: Determining the number of elements in the queue.
Applications of Queue:
1. Task Scheduling: Managing tasks or processes in the order
of their arrival.
2. Print Spooling: Printing documents in the order they were
sent to the printer.
3. Breadth-First Search (BFS): Traversing graphs level by level.
4. Simulations: Modeling real-world scenarios that follow a
queue-like behavior.
Static and Dynamic Data Structures
Static Data Structures:
In static data structures, the memory is allocated at
compile-time or initialization, and the size remains fixed
throughout the lifetime of the data structure. The
memory for a static data structure is typically allocated
on the stack or as a global variable.
Static data structures are suitable when the maximum
size is known in advance and does not change during
runtime. Examples of static data structures include static
arrays and fixed-size matrices.
Static data structures have the advantage of simplicity,
efficiency, and predictable memory usage. However,
they may be limited in flexibility when dealing with
varying amounts of data.
Dynamic Data Structures:
In dynamic data structures, memory is allocated at runtime as
needed, and the size can grow or shrink dynamically. Dynamic
data structures use heap memory allocation, which allows for
dynamic memory management.
The memory allocation and deallocation are performed
explicitly using functions such as malloc, free, new, and delete.
Dynamic data structures are suitable when the size of the data
structure is not known in advance or may change during
runtime. Examples of dynamic data structures include linked
lists, dynamic arrays, trees, and hash tables.
Dynamic data structures offer flexibility, adaptability, and the
ability to handle varying amounts of data. However, they
require more complex memory management and can incur
overhead due to memory allocation and deallocation
operations.
Dynamic Data Structures:
Static and Dynamic implementations
It refers to different approaches for implementing data
structures.

Static Implementation
In a static implementation, the data structure is allocated a fixed
amount of memory at compile-time or initialization.
The size of the data structure is determined in advance and
cannot be changed during runtime.
Static implementations are often used when the maximum size
of the data structure is known and remains constant.
Examples of static implementations include arrays, fixed-size
matrices, and statically allocated linked lists.
Dynamic Implementation
In a dynamic implementation, the data structure is allocated
memory at runtime as needed.
The size of the data structure can grow or shrink dynamically
as elements are added or removed.
Dynamic implementations are used when the size of the data
structure is not known in advance or can change during
runtime.
Examples of dynamic implementations include dynamically
allocated arrays, linked lists, trees, and hash tables.
Static vs Dynamic Implementation
Algorithms
Algorithms are used in various applications: Algorithms are a
fundamental concept in computer science and find applications in
sorting and searching data, pathfinding, optimization problems,
encryption and decryption, artificial intelligence, and more. They are
essential for solving complex computational problems and designing
efficient software solutions.
Time-space tradeoff in choosing algorithms: When selecting an
algorithm involving any data structure, the objective is to find a
balance between increasing the space for storing data and reducing
the time to process the data, or vice versa. This tradeoff between
space and time is crucial for optimizing the performance of algorithms
in various scenarios, as demonstrated in the example of searching
algorithms.
Example Problem: Searching a given number in the record of the file.
Statement - Given a series of integers and a target value, implement a
search algorithm to determine If the target value exists in the series or
not. If found return the index of the target value; otherwise, return -1.
Implementation of Algorithm
First, Start from the beginning of the list;
Compare 10 with target value (60)
If they matches; search is successful and position 1
(position of 10 i.e. 1) is returned; but here they are not
matching means go to step 4
Go to the Next element (i.e. 20)
Repeat steps 2 to 4 until the target find or end of the list is
reached.
(Check items 20, 30, 40, 50, at 60; here target is matched,
will move to successful case and result is position 6 will be
returned)
If the target value is not found after checking all elements,
the search is unsuccessful, and a special value (e.g., -1)
may be returned to indicate this.
Implementation of Algorithm
Linear search is straightforward to implement but may not be
efficient for large lists or arrays.
Its time complexity is O(n), where n is the number of
elements in the list.
In the worst case, the algorithm may need to check every
element in the list, resulting in a linear time complexity.
Here worst case leads us to 7 searches (means maximum no.
of loop executes.)
Summary…Topic Covered

1. Introduction

2. Data

3. Basic Terminology – Elementary Data Organization

4. Abstract Data Types

5. Data structures

6. Data Structure Operations

7. Static and Dynamic Data Structures

8. Static and Dynamic implementations

9. Algorithms