Here’s a clear, detailed, exam-oriented explanation of all the topics you listed, written in
simple language and suitable for BCA / BSc Computer Science / Data Structures notes or
lab manual.
DATA STRUCTURES & ALGORITHMS –
INTRODUCTION
1. Non-Primitive Data Structures
Non-primitive data structures are complex data types that can store multiple values and
represent relationships among data.
Examples:
Arrays
Structures
Linked lists
Stacks
Queues
Trees
Graphs
👉 They are derived from primitive data types (int, float, char).
2. Classification of Data Structures
A) Linear Data Structures
In linear data structures, elements are arranged sequentially.
Examples:
Array
Linked List
Stack
Queue
Deque
Characteristics:
Single level
Easy traversal
Sequential access
B) Non-Linear Data Structures
In non-linear data structures, elements are arranged hierarchically or graph-like.
Examples:
Tree
Graph
Heap
Set
Characteristics:
Multi-level
Complex relationships
Faster searching in many cases
3. Operations on Data Structures
Common operations performed on data structures:
1. Insertion – adding an element
2. Deletion – removing an element
3. Traversal – accessing all elements
4. Searching – finding an element
5. Sorting – arranging elements
6. Merging – combining data structures
DYNAMIC MEMORY ALLOCATION
4. Static Memory Allocation
Memory allocated at compile time
Size is fixed
Faster access
Less flexible
Example:
int a[10];
5. Dynamic Memory Allocation
Memory allocated at run time
Size is flexible
Efficient memory usage
Managed using pointers
Example:
int *ptr;
6. Memory Allocation Functions (C Language)
1️⃣ malloc() – Memory Allocation
Allocates a single block of memory
Memory is uninitialized
Syntax:
ptr = (int*)malloc(n * sizeof(int));
2️⃣ calloc() – Contiguous Allocation
Allocates multiple blocks
Memory is initialized to zero
Syntax:
ptr = (int*)calloc(n, sizeof(int));
3️⃣ realloc() – Reallocation
Resizes previously allocated memory
Syntax:
ptr = realloc(ptr, new_size);
4️⃣ free() – De-allocation
Releases allocated memory
Syntax:
free(ptr);
ALGORITHMS
7. Algorithm Specification
An algorithm is a finite sequence of steps to solve a problem.
Characteristics:
Input
Output
Definiteness
Finiteness
Effectiveness
Methods of Specification:
Natural language
Pseudocode
Flowchart
8. Performance Analysis
Performance analysis evaluates:
Time complexity
Space complexity
Types of Analysis:
Best case
Average case
Worst case
9. Performance Measurement
Measured using:
Execution time
Memory consumption
Number of operations
Common notations:
O(1)
O(n)
O(log n)
O(n²)
RECURSION
10. Definition of Recursion
Recursion is a technique where a function calls itself until a base condition is met.
11. Types of Recursion
1. Direct Recursion – function calls itself
2. Indirect Recursion – function calls another function
3. Tail Recursion – recursive call is last statement
4. Head Recursion – recursive call before processing
12. Recursion Examples
A) GCD using Recursion
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
B) Binomial Coefficient (nCr)
[
nCr = \frac{n!}{r!(n-r)!}
]
Recursive formula:
[
nCr = (n-1)C(r-1) + (n-1)Cr
]
int nCr(int n, int r) {
if (r == 0 || r == n)
return 1;
return nCr(n-1, r-1) + nCr(n-1, r);
}
C) Towers of Hanoi
Rules:
Move one disk at a time
Never place larger disk on smaller disk
Recursive steps:
1. Move n-1 disks from source to auxiliary
2. Move largest disk to destination
3. Move n-1 disks from auxiliary to destination
void toh(int n, char A, char B, char C) {
if (n > 0) {
toh(n-1, A, C, B);
printf("Move disk %d from %c to %c\n", n, A, C);
toh(n-1, B, A, C);
}
}
13. Iterative vs Recursive Functions
Aspect Iterative Recursive
Approach Loop-based Function calls
Memory Less More (stack)
Speed Faster Slower
Code Longer Shorter
Readability Moderate High
14. Exam-Ready Short Definition ✍️
Recursion:
A programming technique in which a function calls itself repeatedly until a terminating
condition is satisfied.
✅ If you want next:
Convert this into DOC / PDF
Unit-wise notes
MCQs & viva questions
Flowcharts & diagrams
Lab manual format
Just tell me 👍