Data Structures and Algorithms

Chapter 1: Part-I
Introduction to Data Structures
 Contents
▪ Introduction to Data Structures
▪ Abstract Data Types
▪ Abstraction
▪ Recap Basic Programming Knowledge
▪ Arrays
▪ Structures
▪ Functions
▪ Pointers
▪ Algorithms: Properties of an Algorithms
▪ Why do we need data structures when we can already
store data using simple variables?

▪ Why is it essential to have a good understanding of

variables, loops, and functions before learning data
structures?

▪ Which do you think is more critical in a data-driven

system: choosing the right data structure or the right
algorithm? Why?

1
 Abstract Data Type
▪ Abstract Data Type (ADT) is a model for data structures that defines a data
type by its behavior and the relationships between those operations.
▪ ADTs are well-defined models for data organization that specify:
• What data or data elements can be stored?
o E.g., integers, characters, objects. {10, 20, 30}, {A, B, C}, …
• What operations can be done on/by the ADT?
o E.g., insert, delete, search, traverse, push, pop, peek, isempty,
enqueue, dequeue, add, remove vertex, etc.
• What behavioral rules governing those operations?
o E.g. FIFO, LIFO, hierarchical, indexed access, ordered, etc.
▪ ADTs not specify how the data is stored & how the operations are
implemented.
2
 Abstract Data Type…

▪ ADTs consists of a standardized data structures and operations.

▪ There are many formalized and standard ADTs used in software development,
such as lists, stacks, queues, trees, graphs, maps, heaps, and others.

▪ ADTs stores relevant attributes and discarding irrelevant attributes.

▪ Data structure is a concrete implementation of an ADT, typically defined using

the constructs provided by a programming language.

▪ Do all characteristics need to be modeled?

▪ Not at all, because it depends on the scope of the model and the reason for
developing the model
3
 Abstraction

• Abstraction is the process of hiding the complex implementation details and showing
only the essential features or operations to the user.

• Abstraction classifies characteristics as relevant and irrelevant for the particular purpose
at hand and ignoring the irrelevant ones.

• Applying abstraction correctly is the essence of successful programming.

• How do data structures model the world or a part of the world?

• The value held by a data structure represents some specific characteristic of the world.

• The characteristic being modeled restricts the possible:

1. Values held by a data structure
2. Operations to be performed on the data structure.
4
 Abstraction…

▪ Example, abstract data type employees of an organization:

▪ This ADT stores employees with their relevant attributes and discarding
irrelevant attributes.
▪ Relevant:- Name, ID, Sex, Age, Salary, Department, Phone-No, Address
▪ Non-Relevant:- weight, color, height.

▪ While ADTs define basic operations like insertion, deletion, and retrieval,
domain-specific, higher-level application or business logic operations such as
hiring, firing, and retiring of employees are typically built on top of an ADT to
serve specific application needs.

5
 Data Structures
• Data structure is a way of organizing, storing, and managing data so that it can
be accessed and modified efficiently.
• It is the representation of the logical/reasonable relationship existing between
individual elements of data.
• Data structure is an arrangement of data in a computer's memory (or some
times on a disk), group of data elements.

• Data Structure is simply a way to organize data

• What is data structure? To answer this, first we have to understand about data:
• Data is a collection of facts from which conclusion may be drawn
• Types of data: textual, numeric, audio, video and more
6
 Data Structures
Why data structures?
▪ Efficiently organize and manage data.
▪ Develop effective algorithms and optimize performance.
▪ Build problem-solving and logical thinking.
▪ The choice of data structure affects the performance of algorithms and the overall
efficiency of a program.
▪ It is important in every computer science curricula.
▪ We interact with data structures when we:
▪ Implement data structures as a developer.
▪ Perform insert, delete, search, sort operations
▪ Use everyday applications(Open a files, look up a contacts, social
networks, web search)
7
 Types of Data Structure
• Primitive data structure: the basic building blocks provided by programming
languages.

• Simple and directly operated upon by machine instructions. E.g. integer,

float/double, character, boolean.

• Non-primitive data structure: More complex and built using primitive data types.

• Linear Data Structures: Elements are arranged sequentially, and traversal is done
in a single level (one by one). E.g. array, linked list, queue, stack

• Non-Linear Data Structures: Elements are not arranged sequentially. It can be

connected in hierarchical or complex ways. E.g. graph, tree, hash table

• Hash-Based Data Structures (efficient key-value storage): Storing data with unique
keys and fast access using hash function.
8
 Type of Data Structures…
• Type of data structures based on how memory is allocated and managed for
storing data: Static and Dynamic Data Structures
1. Static Data Structures
• Data structures with a fixed size and memory allocation are determined at compile time.
• Pros: Fast access to elements and simple and easy to implement.
• Suitable for applications where the data size is known beforehand.
• Predictable memory usage and efficient access time.
• Cons: Memory size cannot be changed/grow or shrink at runtime/program execution.
• If the allocated size is larger than needed, possible memory wastage.
• Overflow issue if data exceeds allocated size.
• Examples: Arrays, array-based static Stacks and static queues

9
 Type of Data Structures…
2. Dynamic Data Structures
• Data structures can grow or shrink at runtime as needed.
• Memory is allocated and deallocated dynamically using pointers or references.
• Pros: Flexible memory size and can adjust to varying amounts of data.
• Efficient memory usage (allocate only what is needed).
• Adaptable for unpredictable data sizes and no overflow.
• Cons: More complex to implement.
• Slower access compared to static structures (due to pointer dereferencing).
• Pointer dereferencing is accessing the actual data value that a pointer is pointing to.
• Possible memory fragmentation if not managed well.
• Examples: linked lists, trees, graphs, linked list-based dynamic stacks& dynamic queues.

10
 Data Structure Operations
Array Operations
▪ Traverse: Access each element of the array
▪ Insertion: Add an element at a specific index
▪ Deletion: Remove an element from a specific index
▪ Search: Find the location of an element
▪ Update: Change the value of an element
Linked List Operations
▪ Insertion: Add a node at the beginning, end, or middle
▪ Traversal: Visit each node in the linked list
▪ Deletion: Remove a node from any position
▪ Search: Find a node with a specific value
▪ Update: Change the data in a specific node
11
 Data Structure Operations…
Stack Operations (LIFO)
▪ Push: Add an element to the top of the stack
▪ Pop: Remove the top element from the stack
▪ Peek/Top: View the top element without removing it
▪ IsEmpty: Check if the stack is empty

Queue Operations (FIFO)

▪ Enqueue: Add an element to the end of the queue
▪ Dequeue: Remove an element from the front of the queue
▪ Peek/Front: View the front element without removing it
▪ IsEmpty: Check if the queue is empty

12
 Data Structure Operations…
Tree Operations
▪ Traversal: Visit all nodes (in-order, pre-order, post-order)
▪ Insertion: Add a new node while maintaining tree properties
▪ Deletion: Remove a node while maintaining tree properties
▪ Search: Find a node with a given value

Graph Operations
▪ Add Vertex: Add a new vertex to the graph
▪ Add Edge: Connect two vertices with an edge
▪ Remove Vertex: Remove a vertex and its associated edges
▪ Remove Edge: Remove a connection between two vertices
▪ Traversal: Visit vertices (BFS, DFS)
13
 Data Structure Operations…
Hash Table Operations

▪ Insert: Add a key-value pair

▪ Delete: Remove a key-value pair

▪ Search: Retrieve value by key

▪ Update: Change the value associated with a key

14
 Arrays
• Array is a data structure that stores collection of a fixed number of elements of
the same type stored sequentially in the memory.
• Elements can be individually referenced by adding an index to a unique
identifier.
• An item in the array is called element.
• It store multiple values under a single variable name and access them using an
index.

15
 Arrays
• Arrays are.
• Fixed Size: In most programming languages, the number of elements in
the array must be defined when the array is created.

• Indexed: Elements in an array are accessed via an index.

• Memory Allocation: Arrays store elements in a contiguous block of
memory, which makes accessing elements faster.

• Example: We can store 5 values of type int in an array without having to

declare 5 different variables, each with a different identifier.

16
 Arrays…
• Instead, by using an array, we can store 5 different values of the same type
int, for example under a single identifier.
#include <iostream>
using namespace std;
int main() {
Int arr[5]; // Declare an array of 5 integers
// Input 5 integer values from the user
cout << "Enter 5 integer values: " << endl;
for (int i = 0; i < 5; i++) {
cout << "Value " << i + 1 << ": ";
cin >> arr[i]; // Store value in the array
} // Display the stored values
cout << "\nThe stored values are: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " "; }
cout << endl;
return 0;}
17
 Declaring, Initializing and Referencing Arrays
• Declaring an Array: defining the array's type and size (without assigning values).
• Initializing an Array: assigning values to the array at the time of declaration.
• Syntax: data-type variable-name [size];
• Declaring and initializing an array with a fixed size (C++)
• int arr[5] = {1, 2, 3, 4, 5};
• Accessing/referencing elements (C++)
• cout << arr[0] << endl; // Display the first element, which is 1
• cout << arr[2] << endl; // Displaythe third element, which is 3
• Declaring an array using a list(Python)
• arr = [1, 2, 3, 4, 5]
• Accessing/referencing elements(Python)
• print(arr[0]) # Print the first element, which is 1
• print(arr[2]) # Print the third element, which is 3
18
 Declaring and Referencing Arrays…

• For example, an array representing 5 height measurements (each being an integer

quantity) may be defined as:
• int heights[5]; // Declare an array named ' heights' that can store 5 integers
• int heights[5] = {10, 20, 30, 40, 50}; // Initialize array with values
• cout << heights[4]; // Referencing/Accessing(Access last element (50))
• The individual elements of the array are accessed by indexing the array.
• The first array element always has the index 0.
• Heights[0] and heights[4] denote, respectively, the first and last element of heights.
• Each of heights elements can be treated as an integer variable.
• So, for example, to set the third element to 30, we may write: heights[2] = 30;

19
 Declaring, Initializing and Referencing Arrays…
Example
#include<iostream> //Include the input-output stream library for standard I/O
using namespace std; //To avoid using 'std::' before cout and cin
void printArray() // Function name to printArray
{
• Note: to access a nonexistent array element
(heights[-1] or heights[10]) leads to a serious
int arr1[] = {1, 2, 3}; runtime.
for(int i = 0; i < 3; i++) • When you create an array in C++, you
{ define its size, and elements are stored in
indexed positions starting from 0 up to size -
cout << "array[" << i << "] = " << arr1[i] << endl;
1.
}
• When you try to access an index that is out
} of bounds, like:
int main() • heights[-1]; // Negative index (invalid)
{ • heights[10]; // Index larger than 4
printArray(); // Call the printArray function (invalid for size 5 array)
return 0;}
20
 Types of Arrays: One-Dimensional Array
▪ A one-dimensional array is a list of elements of the same type, stored in a single row
(linear form).
▪ int numbers[5] = {10, 20, 30, 40, 50}; // One-dimensional array

21
 Type of Arrays: Two-Dimensional Array
• An array of arrays, stored in rows and columns (table format).
• Elements are accessed using two indices (row and column).
• There can be arrays of two dimension which is array of arrays.
• int matrix[2][3] = { {1, 2, 3}, {4, 5, 6} }; // 2 rows, 3 columns

22
 Type of Arrays: Two-Dimensional Array…
Example
#include<iostream>
using namespace std;
main( )
{
int arr[4][2] = {{21, 23}, {24, 26}, {27, 29}, {40, 41}} ;
int i,j;
cout<<"Printing a 2D Array:\n";
for(i=0;i<4;i++)
{
for(j=0;j<2;j++)
{
cout<<"\t"<<arr[i][j];
}
cout<<endl;
}}
23
 Type of Arrays: Multi-Dimensional Array
• An array with more than two dimensions essentially, an array of arrays of arrays,
and so on.
• A 3-dimensional array can be visualized as a cube of data, accessed using three
indices.
• Syntax: data_type array_name[size1][size2][size3]…;
• E.g. int cube[2][2][3] = { { {1, 2, 3}, {4, 5, 6} }, { {7, 8, 9}, {10, 11, 12} }
• 2 blocks(depth)
• 2 rows in each block
• 3 columns in each row.

24
 Type of Arrays: Multi-Dimensional Array…

Example

Output =

25
 Structures

• Structure(structs) is user-defined data type that allows you to combine multiple

variables of different types under one name.

• It is especially useful when you want to group related data.

• Structures are typically used to group several data items together to form a
single entity.

• It is way to group several related variables into one place.

• Each variable in the structure is known as a member of the structure.

• Unlike an array, a structure can contain many different data types (int, string, bool, etc.).

26
 Structures…

• Why Structures?

• To create complex data types (records, nodes for linked lists, trees, etc.).

• To group related data logically (representing a student, employee, or point in 2D).

• Where are Structures Used in Data Structures?

• Linked Lists: Node with data and next pointer.

• Trees and Graphs: Node with data and children/adjacent nodes.

• Stacks/Queues: to store complex data types).

struct StructureName {
// member variables
• To record real-life data.
dataType member1;
dataType member2; ... };

27
 Structures…

Example #include <iostream>

using namespace std;
struct Rectangle
{
int width, height;

};
int main(void) {
struct Rectangle rec;
rec.width=8;
rec.height=5;
cout<<"Area of Rectangle is: "<<(rec.width * rec.height)<<endl;
return 0;
}

28
 Functions

• Function is a block of code that performs a specific task.

• It is a set of statements designed to accomplish a particular task.

• Functions help in breaking a large program into smaller pieces, making it easier
to write, manage, and debug.

• Experience has shown that the best way to develop and maintain a large
program is to construct it from smaller pieces or (modules).

29
 Functions…

• In C++ these smaller problems can be implemented using modules called

functions.

• This sort of independence of program components is called modularity, and is

critical to good software engineering.

• Splitting code up into functions increases the modularity of a program.

• Modularity = the quality of consisting of separate parts that, when combined,
form a complete whole:

31
 Functions…

• Complex program can be decomposed into smaller and easily manageable

problems.

• This simplifies programming in many ways:

• We can independently write, debug/correct, test
• Increase reusability (reuse in later programs),
• Cooperative work (task division): We can split development of the program
among multiple people, with each developing a different set of functions.

• Maintaining a program

30
 Functions…
• Function definition has a name, parentheses, zero or more parameters & a body.
• For each parameter, should have a corresponding declaration that occurs
before the body.
• Any parameter not declared is taken to be an integer by default.
• Function name: a unique identifier, can be called and used in a program(or
other function).
• Function parameters (signature): a set of zero or more typed identifiers used
for passing values to and from the function.
• Functions return type. specifies the type of value the function returns.
• Function which returns nothing should have the return type void.

32
 Functions…

• The body of a function contains the computational steps (statements) that

comprise the function.

34
 Functions: Example
#include <iostream> int main() { // Main function where program
using namespace std; execution starts
int add(int a, int b) { // Define add function with two integer int x = 20, y = 10; // Declare and initialize
parameters integers x and y
return a + b; // Return the sum of a and b cout << "Addition: " << add(x, y) <<
} endl; // Call and display result of addition
int subtract(int a, int b) { // Define subtract function cout << "Subtraction: " << subtract(x, y)
return a - b; // Return the difference of a and b << endl; // Call and display result of
} subtraction
int multiply(int a, int b) { // Define multiply function cout << "Multiplication: " <<
return a * b; // Return the product of a and b multiply(x, y) << endl; // Call and display
} result of multiplication
float divide(int a, int b) { // Define divide function with two integer cout << "Division: " << divide(x, y) <<
parameters, return float endl; // Call and display result of division
if (b == 0) { // Check if denominator is zero to avoid division return 0; // Return 0 to indicate successful
by zero error execution
cout << "Error: Division by zero!" << endl; }
return 0; // Return 0 to indicate error
}
return (float)a / b; // Cast a to float and return division result
}
34
 Functions…

• When are functions used in data structures and algorithms?

• Searching algorithms such as binary search, linear search.
• Sorting algorithms like bubble sort, merge sort.
• Operations on data structures when inserting/deleting nodes in linked
lists, trees.

• Recursive algorithms like backtracking.

35
 Types of Functions
▪ User Defined Functions: Created by the programmer to perform specific tasks.

▪ This allow for code reusability and modular programming.

▪ Built-in Functions: Predefined and provided by the language’s standard library.

▪ These functions are ready to use and perform common tasks.

▪ Java: System.out.println(), Math.random(), String.charAt(), Integer.parseInt(),

Thread.sleep()….

▪ C++: sqrt(), pow().cout, cin, abs(), size(), exit()…

▪ Python: print(), input(), type(), sorted(), sum()…

36
 Pointers
▪ It is a variable that stores the memory address of another variable.
▪ Instead of storing a value directly, it points to a location in memory where the
value is stored.
▪ Pointer access the data by indirect reference as it holds the address of that
variable where it has been stored in the memory.

▪ We can use the pointer to reference this memory cell.

37
 Pointer Operator

• A pointer operator can be represented by a combination of (*) with a variable.

• Example, int *ptr; where ptr is a pointer variable which holds the address of an
integer data type.
• Why Use Pointers?
• Efficient memory management
• Pass large structures or arrays to functions efficiently
• Dynamic memory allocation
• Building complex data structures (linked lists, trees)

38
 Declaration of Pointer Variables
• Syntax: type *pointer_name;
• type: the data type of the variable that the pointer will point to.
• *: denotes that this variable is a pointer.
• &: Address-of operator (gets the address of a variable)
• *: Dereference operator (accesses the value at an address)

▪ Where type is the type of data pointed to int, char, double

▪ C++ has pointer types for each type of object

▪ Pointers to int objects

▪ Pointers to char objects

▪ Pointers to user-defined objects

40
 Declaration of Pointer Variables …
▪ This simple example to show how can create and use pointer of char.
#include <iostream>
using namespace std;
int main()
{
char c='a’; //Declare a character variable c and initialize it with a
char *ptc = &c; //Declare a pointer ptc to char and store the address of c
cout<< *ptc;
}

39
 Algorithms

• Algorithm is a finite set of well-defined instructions or rules designed to solve

a specific problem or perform a computation.
• It takes an input, processes it through a series of well-defined steps, and
produces an output.
• Characteristics:
• Step-by-step procedure to solve a problem.
• Input and output defined.
• Finite execution: It should terminate after a finite number of steps.

41
 Properties of Algorithms
Finiteness:
▪ Algorithm must complete after a finite number of steps (should have a finite number
of steps).
Definiteness (Absence of Ambiguity):
▪ Each step must be clearly defined, having one and only one interpretation.
▪ At each point in computation, one should be able to tell exactly what happens next.
Sequential:
▪ Each step must have a uniquely defined preceding and succeeding step.
▪ The first step (start step) and last step (halt step) must be clearly noted.
Feasibility:
▪ It must be possible to perform each instruction.
▪ Each instruction should have possibility to be executed.
42
 Properties of Algorithms
Correctness:
▪ It must compute correct answer for all possible legal inputs.
▪ The output should be as expected and required and correct.
Completeness:
▪ It must solve the problem completely.
Effectiveness:
▪ Doing the right thing. It should yield the correct result all the time for all of the
possible cases.
Language Independence:
▪ It must not depend on any one programming language.
Efficiency:
▪ It must solve with the least number of computational resources such as time and space.
▪ Producing an output as per the requirement within the given resources (constraints).
43
 Properties of Algorithms
Input/output:
▪ There must be a specified number of input values, and one or more result values.
▪ Zero or more inputs and one or more outputs.
Precision:
▪ The result should always be the same if the algorithm is given identical input.
Simplicity:
▪ A good general rule is that each step should carry out one logical step.
▪ What is simple to one processor may not be simple to another.
Levels of Abstraction:
▪ Used to organize the ideas expressed in algorithms.
▪ Used to hide the details of a given activity and refer to just a name for those details.
▪ The simple (detailed) instructions are hidden inside modules.
▪ Well-designed algorithms are organized in terms of levels of abstraction.
44
 Applications of Algorithms
▪ Computer Science: Sorting, searching, file compression, and so on

▪ Cryptography & Security: Encryption algorithms (RSA, AES), hashing algorithms

▪ Machine Learning & AI: Classification, prediction, clustering, neural networks, …

▪ Networks: Routing algorithms ( Dijkstra’s, Bellman-Ford….)

▪ Databases: Query optimization, indexing algorithms

▪ Operating Systems: Scheduling algorithms, memory management

▪ Robotics and Automation: Pathfinding algorithms (A* Algorithm, Dijkstra's)

▪ Bioinformatics: Genome sequencing algorithms

▪ But not limited to this.

45
Thank You!

46