UNIT I

Introduction and Overview: Definition, Elementary data organization, Data Structures, data
Structures operations, Abstract data types, algorithms complexity, time-space trade-off.
Preliminaries: Mathematical notations and functions, Algorithmic notations, control structures,
Complexity of algorithms, asymptotic notations for complexity of algorithms. Introduction to
Strings, Storing String, Character Data Types, String Operations, word processing, Introduction
to pattern matching algorithms.
[Link]

Introduction and Overview:

Definition

WHAT IS DATA STRUCTURE?

In computer science, a data structure is a way of organizing and storing data in a computer
program so that it can be accessed and used efficiently. Data structures provide a means of
managing large amounts of data, enabling efficient searching, sorting, insertion and deletion
of data.
Elementary data organization

Data structures are the building blocks of any program or the software. Choosing the
appropriate data structure for a program is the most difficult task for a programmer.
Data: Data can be defined as an elementary value or the collection of values.
Ex: student's name and its id are the data about the student.
Group Items: Data items which have subordinate data items are called Group item.
Ex: name of a student can have first name and the last name.
Record: Record can be defined as the collection of various data items.
Ex: if we talk about the student entity, then its name, address, course and marks can be
grouped together to form the record for the student.
File: A File is a collection of various records of one type of entity.
Ex: if there are 60 employees in the class, then there will be 20 records in the related file
where each record contains the data about each employee.
Attribute and Entity: An entity represents the class of certain objects. It contains
various attributes. Each attribute represents the particular property of that entity.
Field: Field is a single elementary unit of information representing the attribute of an

Dell | [SCHOOL]
 entity.
Data Structures:

Introduction to Data Structures

A data structure is a systematic way of organizing and storing data in memory so that it can
be accessed and modified efficiently. In computer science, the choice of data structure
directly affects the performance of algorithms.
A program consists of:
 Data
 Operations on data
Efficient data organization improves:
 Execution time
 Memory utilization
 Maintainability of programs
According to the classical view presented in standard textbooks, data structures are closely
connected with abstract data types and algorithm design.

Classification of Data Structures

Dell | [SCHOOL]
 1. Array:
An array is a collection of data items stored at contiguous memory locations. The idea is to
store multiple items of the same type together. This makes it easier to calculate the position
of each element by simply adding an offset to a base value, i.e., the memory location of the
first element of the array (generally denoted by the name of the array).

2. Linked Lists:
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not
stored at a contiguous location; the elements are linked using pointers.

Linked Data Structure

3. Stack:
Stack is a linear data structure which follows a particular order in which the operations are
performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). In stack,
all insertion and deletion are permitted at only one end of the list.

Dell | [SCHOOL]
 Stack Operations:
 push(): When this operation is performed, an element is inserted into the stack.
 pop(): When this operation is performed, an element is removed from the top of the stack
and is returned.
 top(): This operation will return the last inserted element that is at the top without
removing it.
 size(): This operation will return the size of the stack i.e. the total number of elements
present in the stack.
 isEmpty(): This operation indicates whether the stack is empty or not.
4. Queue:
Like Stack, Queue is a linear structure which follows a particular order in which the
operations are performed. The order is First in First out (FIFO). In the queue, items are
inserted at one end and deleted from the other end. A good example of the queue is any queue
of consumers for a resource where the consumer that came first is served first. The difference
between stacks and queues is in removing. In a stack we remove the item the most recently
added; in a queue, we remove the item the least recently added.

Dell | [SCHOOL]
 Queue Data Structure
Queue Operations:
 Enqueue(): Adds (or stores) an element to the end of the queue..
 Dequeue(): Removal of elements from the queue.
 Peek() or front(): Acquires the data element available at the front node of the queue
without deleting it.
 rear(): This operation returns the element at the rear end without removing it.
 isFull(): Validates if the queue is full.
 isNull(): Checks if the queue is empty.

Data Structures operations

Operations are actions performed on data structures to manipulate stored data.
1. Traversal
Accessing each element exactly once.
2. Insertion
Adding a new element into a data structure.
Example: Insertion in an array at position pos:
Time Complexity:
 Worst case: O(n)
3. Deletion
Removing an element from a structure.
Example: Deletion from array:
4. Searching
Finding the location of an element.
Example: Linear Search
Worst-case complexity: O(n)
5. Sorting

Dell | [SCHOOL]
 Arranging data in ascending or descending order.
Example: Bubble Sort (basic idea)
Time Complexity:
 Worst: O(n²)
6. Merging
Combining two data structures into one.
Used in merge sort and file processing.
Characteristics of Data Structures
A data structure is a way of organizing and storing data so it can be used efficiently. The
main characteristics are explained below:
1. Linear and Non-Linear Data Structures
� Linear Data Structure
In a linear data structure, elements are arranged sequentially (one after another).
Each element (except first and last) has:
 One predecessor
 One successor
Examples:
 Array
 Linked List
 Stack
 Queue
Features:
 Easy to implement
 Easy to traverse
 Memory is arranged in sequence
� Example:
10 → 20 → 30 → 40
� Non-Linear Data Structure
In a non-linear data structure, elements are not arranged sequentially.
One element can be connected to multiple elements.
Examples:
 Tree
 Graph

Dell | [SCHOOL]
 Features:
 Hierarchical structure
 Complex relationships
 Used in advanced applications
� Example (Tree structure):
10
/ \
20 30

Homogeneous and Heterogeneous Data Structures

� Homogeneous Data Structure
All elements are of same data type.
Example:
 Array of integers
 Array of characters
int arr[5] = {10, 20, 30, 40, 50}
Features:
 Simple
 Memory efficient
 Same type of operations performed
� Heterogeneous Data Structure
Elements are of different data types.
Example:
 Structure in C
 Class in C++
struct student {
int roll;
char name[20];
float marks;
};
Features:
 Can store mixed data
 Used to represent real-world entities

Dell | [SCHOOL]
 Static and Dynamic Data Structures
� Static Data Structure
 Memory size is fixed at compile time
 Size cannot be changed during program execution
Example:
 Array
int arr[10];
Features:
 Fast access
 Less flexible
 May waste memory

� Dynamic Data Structure

 Memory is allocated at runtime
 Size can grow or shrink
Example:
 Linked List
 Tree
 Graph
Features:
 Flexible
 Efficient memory usage
 Slightly complex implementation
Abstract Data Types
An abstract data type (ADT) refers to a set of data values and associated operations that are
specified accurately.

Dell | [SCHOOL]
 An Abstract Data Type (ADT) is a logical description of a data type that specifies:
 The set of values
 The operations allowed
 The behaviour of those operations
It does NOT specify how operations are implemented.
What is an Abstract Data Type (ADT)?
An Abstract Data Type (ADT) is a logical or mathematical model of a data structure that
defines:
 What data is stored
 What operations can be performed on the data
 What the operations do
But it does NOT specify how the operations are implemented.
In simple words:
ADT tells what to do, not how to do it.
Example of ADT
Consider a Stack ADT:
It defines operations like:
 push() – Insert element

Dell | [SCHOOL]
  pop() – Remove top element
 peek() – View top element
 isEmpty() – Check if stack is empty
It does not say whether the stack is implemented using:
 Array
 Linked List
That implementation part is hidden.
Why is it called "Abstract" Data Type?
It is called abstract because:
 It hides implementation details.
 It shows only essential features.
 The user does not know how internally it works.
Think of it like using an ATM machine:
 You know how to withdraw money.
 You don’t know how the machine processes internally.
That hidden internal working makes it abstract.
Difference between ADT and Normal Data Type
Feature Normal Data Type Abstract Data Type (ADT)

Definition Built-in data types Logical model of data

Examples int, float, char Stack, Queue, List, Tree

Focus Stores single value Stores collection of data

Implementation Already defined in language Can be implemented in different ways

Abstraction No Yes

Example Comparison
 int → Just stores a number.
 Stack ADT → Stores multiple elements and defines specific operations on them.
How ADT is Different From Other Data Structures?
Data Structure = Implementation
ADT = Definition / Blueprint
Example:

Dell | [SCHOOL]
  Stack (ADT) → Concept
 Stack using array → Implementation
 Stack using linked list → Another implementation
So ADT is like a design, and data structure is the real building.

Example: Stack ADT

Logical Definition
Stack = (S, push, pop, top, isEmpty)
Where:
 S is a collection of elements
 push adds element
 pop removes element
 top returns top element
Stack Property:
LIFO (Last In First Out)

ADT vs Data Structure

ADT Data Structure

Logical view Physical implementation

Specifies what Specifies how

Example: Stack Example: Array stack

Dell | [SCHOOL]
 Algorithms complexity
Algorithm is a step by step procedure for solving a problem or accomplishing a task,
Or
An algorithm is a finite sequence of well defined instructions that can be used to solve a
computational problem.
Or
It provides a step-by-step procedure that convert an input into a desired output.

Algorithms typically follow a logical structure

1. Input: The algorithm receives input data.

2. Processing: The algorithm performs a series of operations on the input data.
3. Output: The algorithm produces the desired output.

Understanding algorithm complexity helps in:

 Performance Analysis: Predicting how an algorithm will scale with larger inputs.
 Optimization: Identifying bottlenecks (slowdown) and improving efficiency.
 Resource Management: Ensuring algorithms run within acceptable time and space
limits. Algorithm complexity measures resource usage.

Two main types of algorithm complexity:

1. Time Complexity

 The time complexity of an algorithm is the amount of time required to complete the
execution.
 The time complexity of an algorithm is denoted by the big O notation.
 Number of primitive operations executed.

Measured as function of input size n.

Example 1: Constant Time (Time does not change, even if input increases.)
int x = a + b;
Time Complexity: O (1)

Dell | [SCHOOL]
 Example 2: Linear Time (Time increases proportionally with input)
for(int i = 0; i < n; i++)
printf("%d", i);
Time Complexity: O(n)

Example 3: Quadratic Time (Time increases very fast (square of input)

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
printf("*");
Time Complexity: O(n²)

2. Space Complexity

 Space complexity measures the amount of memory an algorithm needs to run as a

function of the input size.
 It also includes the space used by the input itself, temporary storage, and function call
stacks.

It depends on:

 Program Space: the space required by the machine program generated by the compiler
or assembler.
 Data Space: The space required to store the constants, variables etc,
 Stack Space: The space required to store the return address along with parameters that
are passed to the function, local variables etc.

The space needed by an algorithm consists of the following components:

 Fixed static space

 Variable dynamic space

Total memory required by algorithm.

Total Space = Fixed part + Variable part
Fixed part includes:
 Program instructions
 Constants
 Simple variables

Dell | [SCHOOL]
 Variable part includes:
 Dynamic memory
 Recursion stack
 Data structures

Time-space trade-off
The time-space trade-off is a fundamental concept in computer science and algorithm design
that involves a balance between the time complexity (execution speed) and the space
complexity (memory usage) of an algorithm.
The general idea is that if you use memory, you might be able to speed up the algorithm, and
vice versa.
Key Points of time Space Trade-off:

1. More time for less Space: If you optimize for space (use less memory), it might take
more time to execute because it needs to recomputed results multiple times, or it
needs to traverse the input multiple times.
2. More Space for Less Time: If you optimize an algorithm for time (use more
memory),
It might run faster because you can store intermediate results (e.g., memorization,
caching and avoid redundant computations.

Example of Time –Space Tradeoff:

Memorization (Dynamic Programming)
Problem: Calculating Fibonacci numbers.
Without memorization, the naïve recursive solution has exponential time complexity due to
repeated recalculations, thus speeding up the computation.
Without Memorization:

 Time complexity: O(2n) (due to computation).

 Space complexity: O(1) (no additional space used).

With memorization

 Time complexity: O(n) (we compute each Fibonacci number once).

 Space complexity: O(n) (storing results in a cache).

Dell | [SCHOOL]
 Trade-off: By using more space to store intermediate results, you reduce the time complexity
dramatically.

Preliminaries: Mathematical notations and functions

Algorithm analysis frequently uses mathematical functions to describe growth rates.

1. Floor and Ceiling Functions
2. Remainder Function (modular arithmetic)
3. Integer and Absolute Value Functions
4. Summation symbol (Sums)
5. Factorial function
6. Permutations
7. Exponents and Logarithms

Floor and Ceiling Functions

Floor Function ⌊x⌋

Gives the greatest integer less than or equal to x

Example:
⌊4.7⌋ = 4
⌊–2.3⌋ = –3
(Go down to nearest integer)

Ceiling Function ⌈x⌉

Gives the smallest integer greater than or equal to x

Example:
⌈4.2⌉ = 5
⌈–2.3⌉ = –2
(Go up to nearest integer)

2. Remainder Function (Modular Arithmetic)

Gives remainder after division

Dell | [SCHOOL]
 Written as:
a mod b
Example:
10 mod 3 = 1
Because:
10 ÷ 3 → remainder = 1
Another example:
15 mod 4 = 3

3. Integer and Absolute Value Functions

Integer Function

Gives only integer part

Example:
int(4.9) = 4

Absolute Value |x|

Gives positive value

Example:
|5| = 5
|–5| = 5
(Sign removed)

4. Summation Symbol (Σ)

Used to represent addition of numbers

Symbol:
Σ

Dell | [SCHOOL]
 Example:

5. Factorial Function (!)

Product of all positive numbers up to n

Written:
n!
Example:
5! = 5 × 4 × 3 × 2 × 1
= 120
Another:
3! = 6

6. Permutations

Arrangement of objects in different ways

Formula:

nPr=n!/(n−r)!

Example:
5P2 = 5! / 3!
=5×4
= 20

Dell | [SCHOOL]
 7. Exponents and Logarithms

Exponent

Power of number
Example:
2³ = 8
2⁴ = 16

Logarithm

Opposite of exponent
Example:
log₂(8) = 3
Because:
2³ = 8

Algorithmic Notations:
Algorithmic notations are methods used to define, design, and represent the step-by-step
procedures of an algorithm before they are implemented in a specific programming language.
The three primary notations are

1. Pseudocode
2. Flowcharts
3. Mathematical Notation.

1. Pseudocode
Pseudocode is a detailed, readable description of an algorithm that uses a mixture of natural
language (e.g., English) and high-level programming syntax, such as loops (for, while) and
conditionals (if-then-else).
 Purpose: To plan program logic without worrying about strict syntax rules.
Characteristics:
o It is language-independent.
o It uses indentation to show hierarchy and control structures.
o Easier to convert to actual programming code compared to flowcharts.

Dell | [SCHOOL]
  Example (Sum of Two Numbers):
START
DECLARE num1, num2, sum
READ num1, num2
sum = num1 + num2
PRINT sum
STOP

2. Flowcharts
A flowchart is a diagrammatic or graphical representation of an algorithm. It uses standard
symbols (rectangles, diamonds, ovals) connected by arrows to show the sequence of
operations.
 Purpose: To visually represent the logic and flow of a system, making it easy to understand.
Standard Symbols:
o Oval (Terminator): Represents the Start/End.
o Parallelogram (Input/Output): Represents data input or output.
o Rectangle (Process): Represents calculations or actions.
o Diamond (Decision): Represents conditional branches.
 Advantages: Excellent for visualizing complex logic.
 Disadvantages: Can become complex and hard to modify for large, detailed programs.

3. Mathematical Notation
Mathematical notation uses symbols, formulas, and symbolic logic (such as set theory or
matrix notation) to define algorithmic steps, commonly used in numerical analysis, scientific
computing, and algorithm complexity analysis.

Dell | [SCHOOL]
 [Precise: exact, specific, and accurate

Concise: brief, without unnecessary details]

Control structures

Control structures determine the flow of execution in algorithms

1.
2. Sequence logic, or sequential flow
3. Selection logic, or conditional flow
4. Iteration logic, or repetitive flow

 Sequence logic (Sequential flow): The default mode of execution where instructions are
performed one after another in the exact order they appear.
#include<stdio.h>
int main()
{
int a = 5, b = 3, sum;
sum = a + b;
printf("%d", sum);
return 0;
}
 Selection logic (Conditional flow): Used for decision-making and branching. It allows the
program to choose between alternative paths based on whether a condition is true or false.
Examples include if, if-else, and switch statements.
#include<stdio.h>
int main()
{
int n = 10;

if(n > 0)
printf("Positive");

return 0;

Dell | [SCHOOL]
 }
 Iteration logic (Repetitive flow): Used to repeat a block of code multiple times as long as a
specific condition is met. Examples include for, while, and do-while loops.
#include<stdio.h>
int main()
{
int i;

for(i=1; i<=3; i++)

printf("%d", i);

return 0;
}

Complexity of algorithms
Why analysis of algorithm is important?
1. To predict the behaviour of an algorithm for large inputs (Scalable Software).
2. It is much more convenient to have simple measures for the efficiency of an algorithm
than to implement the algorithm and test the efficiency every time a certain parameter in
the underlying computer system changes.
3. More importantly, by analysing different algorithms, we can compare them to determine
the best one for our purpose.
 If the problem is having more than one solution or algorithm then the best one is
decided by the analysis based on two factors.
1. CPU Time (Time complexity)
2. Main memory space (Space complexity)
Time complexity of an algorithm can be calculated by using two methods:
1. Posterior Analysis
2. Priori Analysis

Difference between a posterior analysis and A priori analysis

A posterior analysis A priori analysis

Dell | [SCHOOL]
 Posterior analysis is a relative analysis Prior analysis is an absolute analysis

It is dependent on language of compiler and It is independent on language of compiler

type of hardware and type of hardware

It will give exact answer It will give approximate answer

It doesn’t use asymptotic notations to It uses the asymptotic notations to represent

represent the time complexity of an how much time the algorithm will take in
algorithm. order to complete its execution.

The time complexity of an algorithm using a The time complexity of an algorithm using a
posteriori analysis differ from system to priori analysis is same for every system.
system.

If the time taken by the program is less, then If the algorithm running faster, credit goes
the credit will go to compiler and hardware. to the programmer.

It is done after execution of an algorithm. It is done before execution of an algorithm

It is costlier than priori analysis because of It is cheaper than posterior analysis.

requirement of software and hardware for
execution.

Maintenance phase is required to tune the Maintenance phase is not required to tune
algorithm. the algorithm

Parameters to measures complexities

1. Time complexity
 Time complexity is the amount of time taken by an algorithm to execute each
statement of the code till its completion.
 The time taken here is for the function of the length of the input and not the actual
execution time of the machine on which the algorithm is running.
 The time complexity of algorithms is commonly expressed using the Big O notation.
 To calculate the time complexity, total the cost of each fundamental instruction and
the number of times the instruction is executed.
 There are statements with basic operations like comparisons, return statements
assignments, and reading a variable.
2. Space complexity

Dell | [SCHOOL]
 1. The space complexity of an algorithm is the total space taken by the algorithm with
respect to the input size.
2. Space complexity includes both Auxiliary space and space used by unit.

Order growth
 The order of growth of an algorithm is an approximation of the time required to run a
computer program as the input size increases.
 The order of growth ignores the constant factor needed for fixed operations and
focuses instead on the operations that increase proportional to input size.
Ex: a program with a linear order of growth generally requires double the time if the input
doubles.
Types of Order Growth of an Algorithm
Different types of Order of Growth of an Algorithm are shown below:
Order of Growth Description

1 Constant

log n Logarithmic

n Linear

n log n Linear Logarithmic

n^2 Quadratic

n^3 Cubic

2n Exponential

Constant Order of Growth (1)

 The constant order of growth means the number of steps executed by the algorithm is
constant, whatever the input may be.
Ex: If an algorithm input is 10 or 100 or 1000, the number of steps executed by that algorithm
is always constant.
Logarithmic Order of Growth (log n)
 The Order of Growth of these algorithms is logarithmic.

Ex: If the algorithm input is 8, the number of steps executed by this algorithm is log 8(which
means three steps are performed to get the output).

Dell | [SCHOOL]
 Linear Order of Growth (n)
 The Linear Order of Growth means the number of steps executed by an algorithm is
same as the size of the input.
Ex: If the inputs are 10 or 100 or 1000, the algorithm executes those many numbers steps.

Linear Logarithmic (n log n)

The Order of Growth of these algorithms is linear logarithmic.
Ex: If the input 8 means the number of steps executed is 8 * 3 = 24.

Quadratic order of growth (n^2)

The Order of Growth of the Algorithms is quadratic.

Ex: ten example, ten inputs mean the number of steps executed is 100.

Cubic order of growth (n^3)

The Order of growth of the Algorithms is cubic.

Ex: ten inputs mean the number of steps executed is 1000.

Exponential order of Growth (2n)

The Order of Growth of the Algorithms is exponential.

Ex: ten inputs mean the number of steps executed is 2024.

Notation Example Explanation

O(1) Array access Time taken is constant, regardless of input size

O(log n) Binary Search Time taken grows logarithmically with input

size

O(n) Linear Search Time taken grows linearly with input size

O(n log n) Merge Sort Time taken grows linear ithmically with input
size.

Dell | [SCHOOL]
 O(n^2) Bubble Sort Time taken grows quadratically with input size

Worst ,Average and Best-Case Analysis of Algorithms

1. Worst Case Analysis (Mostly used)

 It represents the maximum time an algorithm takes to run.

 In Linear Search, worst case occurs when the search element is not found in
the array.
 It gives the upper bound of the algorithm and helps in analysing performance.

3. Best Case Analysis (Very Rarely used)

 In best case analysis, we calculate the minimum running time of an algorithm

(lower bound).
 In Linear Search, the best case occurs when the search element (x) is found at
the first position of the array.
 The number of operations in the best case is constant (not dependent on n).
 Therefore, the order of growth is constant O(1).

4. Average Case Analysis (Rarely used)

 In average case analysis, we consider all possible inputs and calculate the
running time for each input.
 Then we add all the running times and divide by the total number of inputs to
get the average time.
 In Linear Search, we assume that all cases are uniformly distributed, including
the case when the element is not present in the array.
 So we sum all cases and divide by (n + 1), where n cases are for elements
present and 1 case is for element not present.

Asymptotic notations for complexity of algorithms

1. Big O notations (O)

Dell | [SCHOOL]
 Big-O notation represents the upper bound of the running time of an algorithm.

 It usually describes the worst-case time complexity.

If f(n) is the running time of an algorithm, then

f(n) = O(g(n)) if there exist positive constants c and n₀ such that

0 ≤ f(n) ≤ c · g(n) for all n ≥ n₀

 Big-O gives the upper limit (maximum growth) of an algorithm.

 It shows how the running time increases when the input size increases.

Big Omega notation(Ω-Notation )

 Omega notation (Ω) represents the lower bound of the running time of an algorithm.

 It usually describes the best-case time complexity.

 It shows the minimum time required by an algorithm to complete execution.

If f(n) is the running time of an algorithm, then

f(n) = Ω(g(n))

if there exist positive constants c and n₀ such that:

0 ≤ c · g(n) ≤ f(n) for all n ≥ n₀

Dell | [SCHOOL]
 Big Theta notation (Θ-Notation)

 Theta notation (Θ) represents both the upper bound and lower bound of the running
time of an algorithm.

 It shows the exact or tight bound of the algorithm’s time complexity.

If f(n) is the running time of an algorithm, then

f(n) = Θ(g(n))

if there exist positive constants c₁, c₂ and n₀ such that:

c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for all n ≥ n₀

Differences between Big O, Big Omega, and Big Theta.

Dell | [SCHOOL]
 [Link].
Big O Big Omega (Ω) Theta (Θ)

It is like (<=) It is like (>=) It is like (==)

rate of growth of an rate of growth is greater meaning the rate of growth
algorithm is less than or than or equal to a is equal to a specified
1. equal to a specific value. specified value. value.

The bounding of a function

The upper bound of a
from above and below is
function is represented by The lower bound of a
represented by theta
Big O notation. Only the function is represented
notation. The exact
time taken function is by Omega notation.
asymptotic behaviour is
bounded by above. B
2. done by this theta notation.

Big Omega (Ω) - Lower Big Theta (Θ) - Tight

Big O - Upper Bound
3. Bound Bound

To find Big Omega

To find Big O notation of An algorithm's general
notation of
time/space,we consider time/space cannot be
time/space,we consider
the case when an represented as Theta
the case when an
algorithm takes notation, if its order of
algorithm takes
maximum time/space. growth varies with input.
4. minimum time/space.

Mathematically: Big Oh Mathematically: Big Mathematically - Big Theta

is 0 <= f(n) <= Cg(n) for Omega is 0 <= Cg(n) <= is 0 <= C2g(n) <= f(n) <=
5. all n >= n0 f(n) for all n >= n0 C1g(n) for n >= n0

Introduction to Strings
 Strings are sequences of characters. The differences between a character array and a
string are, a string is terminated with a special character ‘\0’.
Storing String
How Strings are represented in Memory?

 C: Strings are declared as character arrays or pointers and must end with a null
character (\0) to indicate termination.

Dell | [SCHOOL]
 // C program to illustrate strings
#include <stdio.h>

int main()
{
// declare and initialize string
char str[] = "Geeks";

// print string
printf("%s", str);

return 0;
}
Character Data Types
A character data type (char) is used to store a single character, such as a letter, digit, or
symbol.

Characteristics
 It stores only one character at a time.
 It is written inside single quotes (' ').
 It occupies 1 byte of memory.
 The value is stored as an ASCII code internally.

Dell | [SCHOOL]
 Description Character Literal Example
Alphabet character 'A', 'b', 'Z'
Digit character '0', '5', '9'
Special symbol '@', '#', '%'
Space character ' '
Escape character '\n', '\t', '\0'

String Operations
1. Insertion Operation: Adding a new character or string at a specific position in a
string.
Example: strcat(str, "World"); // Inserts "World" at the end of str

2. Access Operation: Adding a new character or string at a specific position in a string.

Example: strcat(str, "World"); // Inserts "World" at the end of
str

3. Deletion Operation: Removing a character or part of a string from a given position.

Example: strcpy(str, "Hello"); // After deleting some characters,

remaining string becomes "Hello"

4. Concatenation Operation: Joining two strings together to form a single string.

Example: strcat(str1, str2); // Combines str2 at the end of str1

Characteristics of String:
 A string stores multiple characters.
 It is written inside double quotes (" ").
 It is stored in a character array.
 The string always ends with a null character \0.

Description String Literal Example

Alphabetic string (only "Hello", "Computer"

letters)
Numeric string (only digits) "12345", "2024"
Alphanumeric string (letters "BCA2025", "C123"
+ numbers)

Dell | [SCHOOL]
 Special character string "@#$%", "!&*"
(symbols)
Mixed string (letters, "C@2025!", "A1#B2"
numbers, symbols)
Hexadecimal string "\x41", "\x42"
String containing backslash "C:\\Program Files"
String containing double "He said \"Hello\""
quote

Complexity Analysis of String in data Structure

String Operation Best Case Average Case Worst Case

Access O(1) O(1) O(1)
Insertion O(1) O(n) O(n)
Deletion O(1) O(n) O(n)
Concatenation O(n) O(n) O(n)

Word processing
 A word processor is a tool used to create, edit, format, and print text documents.
 It processes text into pages and paragraphs.
 Word processors are of three types:
1. Mechanical word processors
2. Electronic word processors
3. Software word processors
 Word processing software helps in editing, formatting, designing, and managing text
in documents.
 Today, word processors are mainly software programs that run on general-purpose
computers.

Examples or Applications of a word processing software

 Wordpad
 Microsoft Word
 Lotus word pro
 Notepad
 WordPerfect (Windows only),
 AppleWorks (Mac only),

Dell | [SCHOOL]
  Work pages
 OpenOffice Writer

Features

1. They are stand-alone devices that are dedicated to the function.

2. Their programs are running on general-purpose computers
3. It is easy to use
4. Helps in changing the shape and style of the characters of the paragraphs
5. Basic editing like headers & footers, bullets, numbering is being performed by it.
6. It has a facility for mail merge and preview.

Functions

 It helps in Correcting grammar and spelling of sentences

 It helps in storing and creating typed documents in a new way.
 It provides the function of Creating the documents with basic editing, saving, and printing
of it or same.
 It helps in Copy the text along with moving deleting and pasting the text within a given
document.
 It helps in Formatting text like bold, underlining, font type, etc.
 It provides the function of creating and editing the formats of tables.
 It helps in Inserting the various elements from some other types of software.

Dell | [SCHOOL]
 Advantages

 It benefits the environment by helping in reducing the amount of paperwork.

 The cost of paper and postage waste is being reduced.
 It is used to manipulate the document text like a report
 It provides various tools like copying, deleting and formatting, etc.
 It helps in recognizing the user interface feature
 It applies the basic design to your pages
 It makes it easier for you to perform repetitive tasks
 It is a fully functioned desktop publishing program
 It is time-saving.
 It is dynamic in nature for exchanging the data.
 It produces error-free documents.
 Provide security to our documents.

Disadvantages

 It does not give you complete control over the look and feel of your document.
 It did not develop out of computer technology.

Introduction to pattern matching algorithms.

 The complexity of pattern searching depends on the algorithm used.

 Pattern searching algorithms are useful for searching data in databases.
 They are used to find a pattern (substring) inside a larger string.

Dell | [SCHOOL]
 Features of Pattern Searching Algorithm

 Pattern searching algorithms should recognize familiar patterns quickly and accurately.
 Recognize and classify unfamiliar patterns.
 Identify patterns even when partly hidden.
 Recognize patterns quickly with ease, and with automaticity.

Naïve Pattern Searching Algorithm

 Naive pattern searching is the simplest pattern searching algorithm.

 It compares the pattern with every position of the main string.
 This algorithm is suitable for small texts.
 It does not require any pre-processing of the pattern or text.
 It does not use extra memory to perform the search.

#include <stdio.h>
#include <string.h>
int main() {
char text[] = "AABAACAADAABAABA";
char pattern[] = "AABA";
int n = strlen(text);
int m = strlen(pattern);

Dell | [SCHOOL]
 int i, j;
for(i = 0; i <= n - m; i++) {
for(j = 0; j < m; j++) {
if(text[i + j] != pattern[j])
break;
}
if(j == m)
printf("Pattern found at index %d\n", i);
}
return 0;
}

Example

Text: AABAACAADAABAABA
Pattern: AABA

Output:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
Recursion:
Definition: The process in which a function calls itself directly or indirectly is called
recursion and the corresponding function is called a recursive function.
Types
Type of Definition Example
Recursion

Direct A function calls itself directly. fact(n) →

fact(n-1)
Recursion

Indirect A function calls another function which again A() → B() → A()
Recursion calls the first function.

Tail Recursion The recursive call is the last statement in the return fact(n-
1);
function.

Head Recursion The recursive call occurs before other operations fun(n-1);

Dell | [SCHOOL]
 in the function. printf("%d", n);

Tree Recursion A function calls itself more than once. fib(n-1) +

fib(n-2)

Nested A function call is inside another recursive call. fun(fun(n-1))

Recursion

Examples: (Factorial)
#include <stdio.h>
int fact(int n) {
// Base Condition
if (n == 0)
return 1;
return n * fact(n - 1);
}
int main() {
printf("Factorial of 5 : %d\n", fact(5));
return 0;
}
Factorial of 5 : 120

Dell | [SCHOOL]
 UNIT II
Arrays: Definition
Arrays are defined as the collection of similar types of data items stored at contiguous memory
location.
Properties of array:

 Each array element has the same data type and size (4 bytes).
 Elements are stored in contiguous memory, starting at the smallest address.
 Elements can be randomly accessed using the base address and element size

Linear arrays
 A linear array is a collection of elements of the same data type stored in consecutive
memory locations and accessed using a single index.
 Elements are stored one after another in memory.
 Accessed using one index (arr[i]).
 All elements are of the same data type.
 Supports random access.

Arrays as ADT
 An abstract data type (ADT) is a data structure that defines a set of operations.
 Arrays can be considered as an ADT because they provide a set of operations that
allow us to manipulate the data contained within them.
Characteristics of array as ADTs

 Fixed Size: The size of the array is defined at creation and cannot be changed.
 Homogeneous Data: All elements in the array are of the same data type.
 Indexed Access: Elements are accessed using an index (position).
 Efficient Memory Allocation: Elements are stored in contiguous memory locations,
enabling fast access.

Common Operations on Array ADT

 Insert: Add an element at a specific index or at the end.

Dell | [SCHOOL]
  Delete: Remove an element from a specific index.
 Access: Get an element using its index.
 Update: Modify the element at a specific index.
 Size/Length: Get the total number of elements.
 Search: Find the position of a specific element.
 Traversal: Iterate through all array elements.

Example:

#include <stdio.h>

#define MAX 100

// Array ADT structure

struct Array {

int data[MAX];

int size;

};

// Insert at end

void insert(struct Array *arr, int value) {

arr->data[arr->size] = value;

arr->size++;

// Access element

int access(struct Array arr, int index) {

return [Link][index];

// Update element

void update(struct Array *arr, int index, int value) {

arr->data[index] = value;

Dell | [SCHOOL]
 }

// Delete element

void delete(struct Array *arr, int index) {

for(int i = index; i < arr->size - 1; i++) {

arr->data[i] = arr->data[i + 1];

arr->size--;

// Traverse array

void traverse(struct Array arr) {

for(int i = 0; i < [Link]; i++) {

printf("%d ", [Link][i]);

printf("\n");

int main() {

struct Array arr;

[Link] = 0;

insert(&arr, 10);

insert(&arr, 20);

insert(&arr, 30);

traverse(arr);

update(&arr, 1, 25);

traverse(arr);

delete(&arr, 0);

Dell | [SCHOOL]
 traverse(arr);

printf("Element at index 1: %d\n", access(arr, 1));

return 0;

Output:

10 20 30

10 25 30

25 30

Element at index 1: 30

Representation of Linear Arrays in Memory

int arr[5]; // This array will store integer type element

char arr[10]; // This array will store char type element
float arr[20]; // This array will store float type element

Declaration is static or compile-time memory allocation, which means that the array
element's memory is allocated when a program is compiled.

In a linear array, memory is allocated continuously like this:

Dell | [SCHOOL]
 Example:
int A[5] = {10, 20, 30, 40, 50};
If each integer takes 4 bytes, then the array is stored in memory as:

Index Element Memory Address (Example)

A[0] 10 1000

A[1] 20 1004

A[2] 30 1008

A[3] 40 1012

A[4] 50 1016

 Base address = address of first element = 1000

 Each next element = previous address + size of data type
Address Calculation Formula (Important)
Formula:
[ LOC(A[i]) = Base(A) + (i \times W)]
Where:
 LOC(A[i]) = address of element at index i
 Base(A) = address of first element A[0]
 i = index position
 W = size of each element in bytes

Basic Operations:
 Traversal: Visiting or accessing each element of the array one by one.
 Insertion: Adding a new element at a specific position in the array.
 Deletion: Removing an element from a specific position in the array.
 Search: Finding the location of a particular element in the array.
 Update: Modifying or changing the value of an existing element in the array.

Traversal

Dell | [SCHOOL]
 #include <stdio.h>
int main() {
int arr[3] = {10, 20, 30};
for(int i=0; i<3; i++)
printf("%d ", arr[i]);
}
Output:
10 20 30

Insertion: Example (insert 25 at position 2)

#include <stdio.h>
int main( ) {
int arr[5] = {10, 20, 30, 40};
int n = 4, pos = 2, value = 25;
for(int i=n; i>pos; i--)
arr[i] = arr[i-1];
arr[pos] = value;
n++;
for(int i=0; i<n; i++)
printf("%d ", arr[i]);
}
Output:
10 20 25 30 40

Deletion: Example (delete element at position 1)

#include <stdio.h>

int main() {

int arr[5] = {10, 20, 30, 40};

int n = 4, pos = 1; // delete 1st position

for(int i = pos-1; i < n-1; i++)

Dell | [SCHOOL]
 arr[i] = arr[i+1];

n--;

for(int i=0; i<n; i++)

printf("%d ", arr[i]);

Output: 20 30 40

Search Example (search 30):

#include <stdio.h>
int main() {
int arr[4] = {10, 20, 30, 40};
int key = 30;
for(int i=0; i<4; i++){
if(arr[i] == key){
printf("Element found at index %d", i);
break;
}
}
}
Output:
Element found at index 2

Update Example (update index 1 to 50):

#include <stdio.h>
int main() {
int arr[3] = {10, 20, 30};
arr[1] = 50;
for(int i=0; i<3; i++)
printf("%d ", arr[i]);
}

Output:

Dell | [SCHOOL]
 10 50 30

Advantages and Disadvantages of Array:

Advantages of Arrays
1. Easy Access: Elements can be accessed directly using an index.
2. Fast Retrieval: Random access makes reading elements very fast.
3. Simple Implementation: Easy to understand and use in programs.
4. Efficient Memory Usage: Elements are stored in contiguous memory locations.
Disadvantages of Arrays
1. Fixed Size: The size must be defined in advance and cannot easily change.
2. Insertion/Deletion Costly: Requires shifting elements, which takes time.
3. Memory Wastage: Extra space may remain unused if the array is not fully utilized.
4. Homogeneous Data: Can store only elements of the same data type.
Types of Arrays

Fixed Size Array:

An array whose size is defined at the time of declaration and cannot be changed during
program execution.
#include <stdio.h>
int main() {
int arr[3] = {10, 20, 30};

Dell | [SCHOOL]
 printf("%d", arr[1]);
}
Output
20
Dynamic Size Array:
An array whose size can be allocated or changed during runtime using dynamic memory
allocation.
#include <stdio.h>
#include <stdlib.h>
int main() {
int *arr;
arr = (int*) malloc(3 * sizeof(int));
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
printf("%d", arr[2]);
}
Output
30
One-Dimensional Array:
An array that stores elements in a single row and is accessed using one index.
#include <stdio.h>
int main() {
int arr[4] = {5, 10, 15, 20};
printf("%d", arr[3]);
}
Output
20

Multi-dimensional arrays
A multi-dimensional array is an array with more than one dimension.

Two-Dimensional Arrays
A 2D array is also known as a matrix (a table of rows and columns).

Dell | [SCHOOL]
 To create a 2D array of integers,
Example:
int matrix [2][3] = { {1, 4, 2}, {3, 6, 8} };
The first dimension represents the number of rows [2], while the second dimension represents
the number of columns [3].

Change Elements in a 2D Array

To change the value of an element, refer to the index number of the element in each of the
dimensions:
The following example will change the value of the element in the first row (0) and first
column (0):
Example
int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };
matrix[0][0] = 9;
printf("%d", matrix[0][0]); // Now outputs 9 instead of 1
Loop Through a 2D Array
To loop through a multi-dimensional array, you need one loop for each of the array's
dimensions.
The following example outputs all elements in the matrix array:
Example
int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };
int i, j;
for (i = 0; i < 2; i++) {
for (j = 0; j < 3; j++) {
printf("%d\n", matrix[i][j]);
}
}

Example:

#include <stdio.h>

int main() {

Dell | [SCHOOL]
 int arr[2][3], i, j;

printf("Enter 6 numbers:\n");

// Input

for(i=0; i<2; i++)

for(j=0; j<3; j++)

scanf("%d", &arr[i][j]);

// Output

printf("The 2D array is:\n");

for(i=0; i<2; i++) {

for(j=0; j<3; j++)

printf("%d ", arr[i][j]);

printf("\n");

return 0;

Example Input
Enter 6 numbers:
1 2 3
4 5 6

Output
The 2D array is:
1 2 3
4 5 6

Matrices
A Matrix is a rectangular arrangement of elements (numbers/data) in the form of rows
and columns.
Types of Matrices
Row Matrix: Matrix having only one row.
Column Matrix: Matrix having only one column.

Dell | [SCHOOL]
 Square Matrix: Matrix having same number of rows and columns.
Diagonal Matrix: All elements except diagonal are 0.
Identity Matrix: Diagonal elements are 1, others are 0.
Zero (Null) Matrix: All elements are 0.

Sparse matrices
A matrix is a two-dimensional data object made of m rows and n columns, therefore having
total m x n values. If most of the elements of the matrix have 0 value, then it is called a
sparse matrix.
Why to use Sparse Matrix instead of simple matrix?
 Storage: There are lesser non-zero elements than zeros and thus lesser memory can be
used to store only those elements.
 Computing time: Computing time can be saved by logically designing a data structure
traversing only non-zero elements.
00304
00570
00000
02600

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in

the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero
elements, we only store non-zero elements. This means storing non-zero elements
with triples- (Row, Column, value).
Sparse Matrix Representations can be done in many ways following are two common
representations:

1. Array representation
2D array is used to represent a sparse matrix in which there are three rows named as

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located
 Value: Value of the non-zero element located at index - (row, column)

Dell | [SCHOOL]
 // C program for Sparse Matrix Representation
#include<stdio.h>
int main()
{
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};
int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;
// number of columns in compactMatrix (size) must be
// equal to number of non - zero elements in
// sparseMatrix
int compactMatrix[3][size];
// Making of new matrix
int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)

Dell | [SCHOOL]
 if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}
for (int i=0; i<3; i++)
{
for (int j=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);
printf("\n");
}
return 0;
}

Output
001133

242312

345726

Searching
Linear Search
Linear search is a searching technique in which each element of a list or array is checked
one by one sequentially until the required element is found or the list ends.

Array:
A = [10, 25, 30, 45, 50]

Element to search: 30

Steps

1. Compare 10 with 30 → Not equal

2. Compare 25 with 30 → Not equal
3. Compare 30 with 30 → Found

Element 30 is found at position 3.

Dell | [SCHOOL]
 Steps:

1. Start from the first element.

2. Compare the search element with each element in the array.
3. If the element matches, return its position.
4. If the end of the array is reached and no match is found, return not found.

#include <stdio.h>
int main() {
int a[5] = {10, 25, 30, 45, 50};
int i, key = 30;
for(i = 0; i < 5; i++) {
if(a[i] == key) {
printf("Element found at position %d", i + 1);
return 0;
}
}
printf("Element not found");
return 0;
}
Output:
Element found at position 3
Advantages
 Simple and easy to implement
 Works on unsorted data
 Suitable for small datasets
 No extra memory required
Disadvantages
 Slow for large datasets
 Requires checking each element one by one
 Time complexity is O(n) (worst case)
Binary Search

Binary search is a searching technique used to find an element in a sorted array by

repeatedly dividing the search interval into two halves.
It compares the middle element of the array with the target value.

Dell | [SCHOOL]
 Array (sorted): A = [10, 20, 30, 40, 50]
Element to search: 40
Steps

1. Find middle element

Middle = (0 + 4) / 2 = 2 → Element = 30
2. Compare 40 with 30
40 > 30 → Search in right half
3. New range = [40, 50]
4. Find new middle
Middle = 3 → Element = 40
5. Element found at position 4

Algorithm

1. Start with the middle element of the sorted array.

2. If the middle element equals the key → element found.
3. If the key is smaller → search the left half.
4. If the key is larger → search the right half.
5. Repeat until the element is found or the list ends.

Example:

#include <stdio.h>
int main() {
int a[5] = {10, 20, 30, 40, 50};
int low = 0, high = 4, mid, key = 40;
while(low <= high) {
mid = (low + high) / 2;
if(a[mid] == key) {
printf("Element found at position %d", mid + 1);
return 0;
}
else if(a[mid] < key)
low = mid + 1;
else

Dell | [SCHOOL]
 high = mid - 1;
}
printf("Element not found");
return 0;
}
Output:
Element found at position 4
Advantages
 Faster than linear search
 Time complexity is O(log n)
 Efficient for large datasets
Disadvantages

 Works only on sorted arrays

 Slightly more complex than linear search
 Not suitable for frequently changing data

Sorting
1. Bubble sort
Bubble sort repeatedly compares adjacent elements and swaps them if they are in the
wrong order.
#include <stdio.h>
int main() {
int a[5] = {5, 1, 4, 2, 8};
int i, j, temp;
for(i = 0; i < 5; i++) {
for(j = 0; j < 5-i-1; j++) {
if(a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}

Dell | [SCHOOL]
 printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}
Output: Sorted array: 1 2 4 5 8

2. Selection sort
Selection sort repeatedly selects the smallest element from the unsorted part and places it
at the beginning.
#include <stdio.h>
int main() {
int a[5] = {64, 25, 12, 22, 11};
int i, j, min, temp;

for(i = 0; i < 4; i++) {

min = i;

for(j = i+1; j < 5; j++) {

if(a[j] < a[min])
min = j;
}
if(min != i) {
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}

Dell | [SCHOOL]
 3. Insertion sort
Insertion sort places each element in its correct position in the sorted part of the array.
#include <stdio.h>
int main() {
int a[5] = {12, 11, 13, 5, 6};
int i, j, key;
for(i = 1; i < 5; i++) {
key = a[i];
j = i - 1;
while(j >= 0 && a[j] > key) {
a[j+1] = a[j];
j = j - 1;
}
a[j+1] = key;
}
printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}
Output: Sorted array: 5 6 11 12 13

Dell | [SCHOOL]
 4. Merge sort
Merge sort divides the array into smaller parts, sorts them, and then merges them together.
#include <stdio.h>
void merge(int a[], int low, int mid, int high) {
int i = low, j = mid + 1, k = low;
int temp[50];
while(i <= mid && j <= high) {
if(a[i] <= a[j]) {
temp[k] = a[i];
i++;
}
else {
temp[k] = a[j];
j++;
}
k++;
}
while(i <= mid) {
temp[k] = a[i];
i++;
k++;
}
while(j <= high) {
temp[k] = a[j];
j++;
k++;
}
for(i = low; i <= high; i++)
a[i] = temp[i];
}
void mergesort(int a[], int low, int high) {
if(low < high) {
int mid = (low + high) / 2;

Dell | [SCHOOL]
 mergesort(a, low, mid);
mergesort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
int main() {
int a[5] = {8, 3, 5, 2, 7};
int i;
mergesort(a, 0, 4);
printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}
Quick sort
#include <stdio.h>
void quicksort(int a[], int low, int high) {
int i = low, j = high, pivot, temp;
pivot = a[(low + high) / 2];
while(i <= j) {
while(a[i] < pivot)
i++;
while(a[j] > pivot)
j--;
if(i <= j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if(low < j)
quicksort(a, low, j);

Dell | [SCHOOL]
 if(i < high)
quicksort(a, i, high);
}
int main() {
int a[5] = {8, 3, 5, 2, 7};
int i;
quicksort(a, 0, 4);
printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}

Dell | [SCHOOL]