Name of Course: Data Structure and Algorithms

Code: BCECCE3102
 Introduction to course
What are Data Structures?

Definition: Data structures are a way of organizing and storing data to enable
efficient access and modification.

Examples: Arrays, linked lists, stacks, queues, trees, graphs.

What are Algorithms?

Definition: Algorithms are step-by-step procedures for solving problems

computationally.

Examples: Searching algorithms (linear search, binary search), sorting

algorithms (bubble sort, merge sort), graph algorithms (BFS, DFS).

Relationship Between Data Structures and Algorithms

Synergy: How the choice of data structure impacts algorithm design.

Examples: Sorting algorithms with different data structures.

 Introduction to course
Why Data Structure and Algorithms Matter?

• Efficiency: Impact on performance (time and space complexity).

• Scalability: Handling large datasets effectively.

• Flexibility: Choosing the right structure for the problem.

• Critical Thinking: Designing efficient solutions.

• Problem Solving: Addressing real-world challenges.

• Optimization: Improving computational performance.

Real-World Applications

Industry Examples: How companies use DSA for efficiency

(e.g., Google's search algorithms, Facebook's social network structure).

Impact: Enhancing user experience and optimizing resources.

 Introduction to course
Relevance to Branch:-
Data Structures and Algorithms are foundational to computer science and engineering, impacting
everything from software development and system design to emerging technologies like AI and
cyber security. They are essential for problem-solving, performance optimization, and career
advancement in this rapidly evolving field.

Relevance to Society & Industry:-

Data Structures and Algorithms are pivotal in driving technological innovation, optimizing
efficiency, improving societal outcomes, and fostering economic growth across various industries.
They enable industries to harness data-driven insights, enhance decision-making processes, and
develop solutions that address global challenges and improve quality of life.

Relevance to You:-
Data Structures and Algorithms are crucial for CSE students as they provide a solid academic
foundation, practical skills for software development and system design, enhanced career
opportunities, and personal growth in logical thinking and problem-solving abilities. Mastering DSA
prepares students for successful careers in the dynamic and evolving field of computer science and
engineering.

Potential for career:-

Data Structures and Algorithms are integral to career success in technology-driven industries. They
not only open doors to diverse job opportunities but also empower professionals to innovate, lead,
and contribute to advancements in their fields. Mastery of DSA enhances problem-solving skills,
analytical thinking, and adaptability, ensuring that individuals are well-equipped for fulfilling and
impactful careers.
 Outline of Course
Time required for the Unit
Unit No. Title of the Unit
(Hours)
1. Introduction to Data structures 8

2 Searching and Sorting 8

3. Stack and Queue 8

4. Linked List 9

5. Tree Graphs and their Applications 7

 ABC Analysis of the Subject

Time required for the Unit

Unit No. Title of the Unit
(Hours)
1. Introduction to Data structures Low to Medium

2. Searching and Sorting Medium

3. Stack and Queue Medium to High

4. Linked List Medium

5. Tree Graphs and their Applications Medium to High

 Course Outcome
Students will be able to:-

1. Understand overview of data structure, time and space complexity of an

algorithm

2. Analyse time complexities of various searching, sorting

3. Create various applications using stack and queue

4. Understand linked list and its applications

5. Able to select relevant data structure to solve the problem.

 Recommended Study Material

S.
Text Books: Author Edition Publication
No
Data Structures with C (Schaum's Seymour Latest McGraw Hill
1. Education.
Outline Series) Lipschutz
Data Structures and program Robert Kruse Latest Pearson
2. Education
designing using ‘C’
Reference Book
1. Introduction to Data Structures in C by - Kamthane Pearson Education 2005
2. Data Structures Using C by- Bandyopadhyay Pearson Education
Online Resources
1. https://www.gatevidyalay.com/data-structures/
2. https://www.tutorialspoint.com/data_structures_algorithms/index.htm
 Introduction to Data Structures

• Definition: Organized ways to store, manage, and manipulate data.

• Importance: Crucial for efficient data processing and algorithm

implementation.
 Classification of Data Structures

• Primitive Data Structures

• Non-Primitive Data Structures

 Primitive Data Structures

Definition: Basic data structures directly supported by programming

languages.

Types:-
• Integer: Whole numbers.

• Float: Floating-point numbers.

• Character: Single characters.

• Boolean: True/False values.

 Examples of Primitive Data Structures

• Integer Example: int num = 42;

• Float Example: float pi = 3.14;

• Character Example: char letter = 'A';

• Boolean Example: bool isTrue = true;

 Non-Primitive Data Structures

Definition: More complex data structures built from primitive types.

Types:-

• Linear Structures: Arrays, Linked Lists, Stacks, Queues.

• Non-Linear Structures: Trees, Graphs.

• File Structures: Organization of data in files.

 Linear Data Structures

• Arrays: Fixed-size sequence of elements.

• Linked Lists: Sequence of nodes, each pointing to the next.

• Stacks: Last-In-First-Out (LIFO) structure.

• Queues: First-In-First-Out (FIFO) structure.

 Non-Linear Data Structures

Trees: Hierarchical structure with nodes.

• Binary Trees: Each node has up to two children.

• Binary Search Trees (BST): Nodes organized for fast lookup.

Graphs: Set of nodes connected by edges.

• Directed Graphs: Edges have a direction.

• Undirected Graphs: Edges do not have a direction.

 File Structures

Definition: Methods for organizing data in files.

Types:-

• Sequential: Data arranged in a sequence.

• Indexed: Data arranged with an index for fast access.

• Direct: Data accessed directly by a key or address.

 Examples of Non-Primitive Data Structures

• Array Example: int arr[5] = {1, 2, 3, 4, 5};

• Linked List Example: Node* head = NULL;

• Stack Example: stack.push(10);

• Queue Example: queue.enqueue(20);

• Tree Example: TreeNode* root = new TreeNode(5);

• Graph Example: Graph g(V); g.addEdge(0, 1);

 Comparison
Primitive:-
• Simple and directly supported by languages.
• Fixed size.

Non-Primitive:-
• Built using primitive types.
• Can be dynamically sized and more complex.

• Primitive: Used for simple data storage and operations.

• Non-Primitive: Used for complex data management (e.g., databases,

algorithms).
Topic:- Elementary Data Organization
 What is Data Organization?

• Definition: Data organization refers to the way data is structured, managed,

and stored for efficient access and modification.

• Importance: Determines the performance and efficiency of data operations

such as search, insertion, and deletion.
 Goals of Effective Data Organization

• Efficiency: Minimize time complexity for operations.

• Scalability: Handle large volumes of data gracefully.

• Maintainability: Easy to modify and update data structures.

• Memory Usage: Optimal use of memory resources.

 Basic Data Structures
• Arrays:
• Definition: Fixed-size sequential collection of elements of the same
type.
• Operations: Access by index, update, iterate.

• Linked Lists:
• Definition: Collection of elements where each element points to the
next.
• Types: Singly, doubly, and circular linked lists.
• Operations: Insert, delete, traverse.
 Arrays

• Advantages:
• Fast access via index.
• Simple and easy to use.

• Disadvantages:
• Fixed size.
• Costly insertion and deletion operations.
 Linked Lists

• Advantages:
• Dynamic size.
• Efficient insertions / deletions.

• Disadvantages:
• Higher memory usage due to pointers.
• Sequential access only (no random access).
 Stacks

• Definition: Collection of elements with LIFO (Last In, First Out) access.

• Operations: Push, pop, peek.

• Use Cases: Function call management, undo mechanisms.

 Queues

• Definition: Collection of elements with FIFO (First In, First Out) access.

• Operations: Enqueue, dequeue, front.

• Use Cases: Task scheduling, buffering.

 Trees

• Definition: Hierarchical data structure with nodes.

• Types: Binary Trees, Binary Search Trees (BST), AVL Trees.

• Operations: Insert, delete, traverse.

 Hash Tables

• Definition: Stores data in key-value pairs using a hash function.

• Advantages: Fast lookup, insertions.

• Disadvantages: Handling collisions.

• Use Cases: Caching, symbol tables.

 Graphs

• Definition: Collection of nodes (vertices) and edges.

• Types: Directed, undirected, weighted.

• Use Cases: Network routing, social networks.

 Introduction to Algorithm Complexity

What is Algorithm Complexity?

• Time Complexity: Measures the time an algorithm takes to run as a

function of the size of the input.

• Space Complexity: Measures the amount of memory an algorithm uses as

a function of the size of the input.
 Why is Complexity Important?
Significance

• Efficiency: Helps in comparing different algorithms for the same task.

• Scalability: Determines how an algorithm performs as the input size

grows.

• Resource Utilization: Impacts CPU time and memory usage.

 Big O Notation
Understanding Big O

• Big O Notation: Describes the upper limit of an algorithm's running time

or space requirement.

• Examples:
• O(1): Constant time/space
• O(n): Linear time/space
• O(n²): Quadratic time/space
 Time Complexity: Examples

• Constant Time: O(1)

int getFirstElement(int arr[], int size)

{
return arr[0];
}

• Explanation: Always takes the same amount of time regardless of

input size.
 Time Complexity: Examples

• Linear Time: O(n)

void printElements(int arr[], int size)

{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
}

Explanation: Time grows linearly with the input size.

 Time Complexity: Examples
• Quadratic Time: O(n²)

void printPairs(int arr[], int size)

{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
printf("(%d, %d) ", arr[i], arr[j]);
}
}
}

• Explanation: Time grows quadratically with the input size.

 Space Complexity: Examples

Constant Space: O(1)

int add(int a, int b)

{
return a + b;
}

• Explanation: Uses a fixed amount of space regardless of input size.

 Space Complexity: Examples

Linear Space: O(n)

int* copyArray(int arr[], int size)

{
int *copy = malloc(size * sizeof(int));
for (int i = 0; i < size; i++)
{
copy[i] = arr[i];
}
return copy;
}

• Explanation: Space grows linearly with the input size.

 Space Complexity: Examples

• Quadratic Space: O(n²)

int** createMatrix(int n)
{
int **matrix = malloc(n * sizeof(int *));
for (int i = 0; i < n; i++)
{
matrix[i] = malloc(n * sizeof(int));
}
return matrix;
}

• Explanation: Space grows quadratically with the input size.

 Common Time Complexities
Time Complexities You Should Know

• O(1): Accessing an array element

• O(log n): Binary search

• O(n): Linear search

• O(n log n): Efficient sorting algorithms like Merge Sort

• O(n²): Bubble sort, Selection sort

• O(2ⁿ): Exponential growth in algorithms like recursive Fibonacci

 Common Space Complexities

Space Complexities You Should Know

• O(1): Fixed memory allocation

• O(n): Storing an array of size n

• O(n log n): Space complexity for efficient in-place sorts

• O(n²): Space complexity for certain matrix operations

 Analyzing Time Complexity
• Bubble Sort
void bubbleSort(int arr[], int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

• Time Complexity: O(n²)

• Why? Nested loops lead to quadratic growth in execution time.
 Analyzing Space Complexity

Example: Recursive Function

• Recursive Fibonacci
int fibonacci(int n)
{
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}

• Space Complexity: O(n)

• Why? Uses space proportional to the maximum depth of the recursion

stack.
 Summary

• Time Complexity: Evaluates the running time of an algorithm.

• Space Complexity: Evaluates the memory usage of an algorithm.

• Big O Notation: A tool for describing the growth rates.

• Examples: Help in understanding real-world applications and trade-offs.

 Outline

• Introduction to Pointers

• Accessing the Address of a Variable

• Declaring and Initializing Pointers

• Accessing a Variable through Its Pointer

 Introduction to Pointers

• Definition: A pointer is a variable that stores the memory address of

another variable.

• Key Uses:
• Dynamic memory allocation
• Array manipulation
• Function arguments (pass-by-reference)

• Syntax: dataType *pointerName;

 Accessing the Address of a Variable
• Concept: The address of a variable can be accessed using the address-of
operator (&).

• Syntax: &variableName

• Example Code:

• Output:
 Understanding the Address-of Operator (&)

• Operator: The & operator gives the memory address of a variable.

• Usage: Commonly used with pointers to initialize them.

• Example:
int num = 20;
int *ptr = &num;

• Explanation: ptr now holds the address of num.

 Declaring and Initializing Pointers

• Syntax: dataType *pointerName;

• Initialization: Can be initialized with the address of a variable.

• Example Code:
int var = 5;
int *ptr = &var;
printf("Pointer address: %p\n", ptr);
printf("Pointer value: %d\n", *ptr);
printf("Pointer value: %p\n", &var);
 Accessing a Variable through Its Pointer

• Concept: Dereferencing a pointer means accessing the value stored at the

address the pointer holds.

• Syntax: *pointerName

• Example Code:
int num = 100;
int *ptr = &num;
printf("Value of num: %d\n", *ptr);

• Output:100
 Modifying Values via Pointers
• Example Code:-

#include <stdio.h>
int main()
{
int x = 25;
int *p = &x;
printf("Original value of x: %d \n", x);
*p = 50; // Change value through pointer
printf("Modified value of x: %d \n", x);
return 0;
}

• p holds the address of x.

• Changing *p directly affects x.

 Practical Example: Swapping Values Using Pointers
• Function: Swapping values of two variables using pointers.

• Example Code:
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

int main()
{
int x = 10, y = 20;
swap(&x, &y);
printf("x: %d, y: %d \n", x, y);
return 0;
}

• Output: x: 20, y: 10
 Practical Applications of Pointers

• Dynamic Memory Allocation: Using malloc, calloc, realloc, free.

• Data Structures: Linked lists, trees, graphs.

• Function Arguments: Pass-by-reference to modify variables in functions.

 Introduction to Strings

• Definition: A string is a sequence of characters terminated by a null

character ('\0').

• Storage: Stored as an array of characters.

• Declaration: char str[] = "Hello"; or char str[6] = "Hello";

or
char str[] = {‘H', ‘e', ‘l', ‘l', ‘o', '\0'};

• Library: String operations are available in <string.h>.

 Basic String Operations
Example Code:-

• Initialization: char str[] = "Hello";

• Access: str[0], str[1], ...

• Length: Calculated using strlen().

 Common String Functions
• strlen(str): Returns the length of the string.

• strcpy(dest, src): Copies src to dest.

• strcat(dest, src): Appends src to dest.

• strcmp(str1, str2): Compares two strings.

• Example Code:-
 Outline

• Introduction

• Static Memory Allocation

• Dynamic Memory Allocation

• Memory Allocation Functions in C

1. malloc()
2. calloc()
3. free()
4. realloc()
 Introduction

• Memory Allocation: Process of assigning memory to variables and data

structures.

• Types: Static and Dynamic

 Static Memory Allocation
• Definition: Memory allocated at compile time.

• Characteristics:
• Fixed size.
• Efficient in terms of speed.
• Limited flexibility.

• Example:
int array[10];
 Dynamic Memory Allocation

• Definition: Memory allocated during runtime.

• Characteristics:
• Flexible size.
• Can grow or shrink.
• Slightly slower due to runtime overhead.

• Example:
int *array = (int*) malloc(10 * sizeof(int));
 Memory Allocation Functions in C

• Purpose: Allocate and manage memory dynamically.

• Functions: malloc(), calloc(), free(), realloc()

 malloc()

• Function: Allocates a block of memory.

• Syntax:-
ptr = (cast-type*) malloc(byte-size)
• Example:-
int *ptr = (int*) malloc(10 * sizeof(int));

• Does not initialize memory.

 calloc()
• Function: Allocates memory and initializes it to zero.

• Syntax:-
ptr = (cast-type*)calloc(n, element-size);

• Example:-
int *ptr = (int*)calloc(10, sizeof(int));
 free()
• Function: Frees dynamically allocated memory.

• Syntax:-
free(pointer);
• Example:-
free(ptr);
 realloc()

• Function: Reallocates memory to a new size.

• Syntax:-
ptr = (int*) realloc(ptr, newSize);

• Example:-
ptr = (int*) realloc(ptr, 20 * sizeof(int));
 Initializatio
Function Use Case Example
n

malloc Allocate memory No ptr = malloc(10 * sizeof(int));

calloc Allocate and initialize Yes (to zero) ptr = calloc(10, sizeof(int));

free Free allocated memory N/A free(ptr);

Resize allocated
realloc N/A ptr = realloc(ptr, new_size);
memory
 Conclusion
• Static Memory Allocation: Fixed size, compile-time.

• Dynamic Memory Allocation: Flexible size, runtime.

• Functions: Use malloc(), calloc(), free(), and realloc() to manage memory

dynamically in C.
 Outline
• Introduction to Recursion

• Advantages of Recursion

• Writing Recursive Programs

• Fibonacci Sequence
• Greatest Common Divisor (GCD)
 Introduction to Recursion
• Definition: A function calls itself to solve a problem.

• Components:
• Base Case: Condition where recursion stops.
• Recursive Case: Part of the function that calls itself.

• Example:-
Factorial of n (n!) = n * (n-1)!
 How Recursion Works

• Function Call Stack: Each recursive call pushes a new frame onto the
stack.

• Unwinding: Recursion unwinds when the base case is met.

 Advantages of Recursion
• Simplicity: Often more intuitive and easier to implement for problems like
tree traversals and mathematical sequences.

• Reduction of Code: Reduces the need for complex loops and additional
variables.

• Expressiveness: Provides a natural way to express divide-and-conquer

problems.
 Disadvantages of Recursion
• Overhead: Each recursive call uses stack memory, which can lead to
higher memory usage.

• Performance: Recursion may be slower than iterative solutions due to

function call overhead.

• Risk of Stack Overflow: Deep recursion can exhaust stack space.

 Common Examples
Fibonacci Sequence:-

• Definition: Sequence where each number is the sum of the two preceding
ones.

• Series: 0, 1, 1, 2, 3, 5, 8, ...

• Mathematical Formula:
F(n)=F(n−1)+F(n−2)

with base cases F(0)=0 and F(1)=1

 Fibonacci Sequence - Recursive Program
int fibonacci(int n)
{
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

Explanation: Each call computes Fibonacci of n-1 and n−2 until base
cases are met.
 Greatest Common Divisor (GCD)
• Definition: Largest number that divides two numbers without a remainder.

• Example: GCD of 48 and 18 is 6.

• Mathematical Formula (Euclidean Algorithm):-

GCD(a,b)=GCD(b, a % b)

with base case GCD(a,0) = a

GCD - Recursive Program

int gcd(int a, int b)

{
if (b == 0)
return a;
return gcd(b, a % b);
}
 Conclusion
• Recursion: A powerful tool for solving problems.

• Advantages: Simplifies code and improves readability for certain

problems.

• Considerations: Be mindful of memory usage and stack overflow risks.