SUDHARSAN ENGINEERING COLLEGE

(Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )

(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INELLIGENCE AND MACHINE LEARNING

PREFACE OF THE COURSE FILE

FACULTY IN-CHARGE : [Link]

DESIGNATION & DEPT : ASSISTANT PROFESSOR & AI&ML

COURSE CODE : CD3291

NAME OF THE COURSE : DATA STRUCTURES AND ALGORITHMS

ACADEMIC YEAR : 2025-2026

DEPT. FOR WHICH

THE SUBJECT
TO BE HANDLED : AI&ML

PROGRAMME NAME : B.E

STUDENTS’ BATCH : 2024-2028

SEMESTER :III

FACULTY INCHARGE HoD / AI&ML

SUDHARSAN ENGINEERING COLLEGE

 (Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )
(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INELLIGENCE AND MACHINE LEARNING

CD3291 –DATA STRUCTURES AND ALGORITHMS
CO-PO-PSO Mapping

Sem 06

Sub Code CD3291

Sub Name
DATA STRUCTURES AND ALGORITHMS

CO1 : Explain abstract data types.

Course Outcomes CO2 : Design, implement, and analyze linear data structures,
such as lists, queues, and stacks, according to the needs of
different applications.

CO3 : Design, implement, and analyze efficient tree

structures to meet requirements such as searching, indexing,
and sorting.

CO4 : Model problems as graph problems and implement

efficient graph algorithms to solve them.

SUDHARSAN ENGINEERING COLLEGE

(Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )
(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
 Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INELLIGENCE AND MACHINE LEARNING

CD3291 –DATA STRUCTURES AND ALGORITHMS
COURSE OBJECTIVES

 To understand Object Oriented Programming concepts and basics of Java programming

language .
 To know the principles of packages, inheritance and interfaces .
 To develop a java application with threads and generics classes .
 To define exceptions and use I/O streams.
 To design and build Graphical User Interface Application using JAVAFX.
 SUDHARSAN ENGINEERING COLLEGE
(Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )
(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INELLIGENCE AND MACHINE LEARNING

CD3291 –DATA STRUCTURES AND ALGORITHMS
CONTENT BEYOND SYLLABUS

⭐ UNIT I – ABSTRACT DATA TYPES

1. ABSTRACT DATA TYPES (ADTs)

1.1 Definition
An Abstract Data Type (ADT) is a mathematical model for data types where:
 The data and
 The operations allowed on that data
are defined independently from implementation.
1.2 Features of ADTs
 Encapsulation
 Implementation independence
 Clearly defined operations
 Supports modularity
1.3 Examples
 Stack ADT
 Queue ADT
 List ADT
 Priority Queue ADT
 Graph ADT
 Dictionary ADT

2. ADTs and Classes

2.1 Connection Between ADTs and Classes
 ADTs specify what operations exist.
 Classes specify how they are implemented.
2.2 Implementing ADTs using Classes
Example:
Stack ADT → Stack class using list/array.

3. Introduction to Object-Oriented Programming (OOP)

3.1 Core Principles
 Encapsulation – binding data + methods
 Abstraction – hide complexity
 Inheritance – code reuse
 Polymorphism – same function, different behavior
 Modularity – structured programming
3.2 Benefits
 Reusability
 Maintainability
 Extensibility
 Real-world modeling

4. Classes in Python
4.1 Defining Classes
class Student:
def __init__(self, name, dept):
[Link] = name
[Link] = dept
4.2 Special Methods
 __init__() → constructor
 __str__() → string representation
 __len__() → length behavior
 __add__() → operator overloading
4.3 Object Creation & Instance Methods
s = Student("Arun", "CSE")

5. Inheritance
5.1 Types
  Single inheritance
 Multilevel
 Multiple
 Hierarchical
 Hybrid
5.2 Example
class Animal:
def sound(self):
print("Some sound")

class Dog(Animal):
def sound(self):
print("Bark")
Supports polymorphism and code reuse.

6. Namespaces in Python
6.1 Types
 Local namespace (inside functions)
 Global namespace (module-level)
 Built-in namespace (Python defaults)
6.2 Scope Resolution
 LEGB Rule (Local → Enclosing → Global → Built-in)

7. Shallow Copy vs Deep Copy

7.1 Shallow Copy
Copies only references, not nested objects.
import copy
a = [1, [2,3]]
b = [Link](a)
7.2 Deep Copy
Copies entire structure recursively.
c = [Link](a)
⭐ 8. Analysis of Algorithms (Beyond Basic Syllabus)
8.1 Why Analyze Algorithms?
 Predict performance
 Compare algorithms
 Identify bottlenecks
 Ensure scalability

9. Asymptotic Notations
Primary Notations
 Big-O → upper bound
 Ω (Omega) → lower bound
 Θ (Theta) → tight bound
Additional Notations (Beyond syllabus)
 Little-o → non-tight upper
 Little-ω → non-tight lower
 Amortized Time Analysis → aggregated cost for repeated operations
Examples:
o Dynamic array resizing
o Hash table insertion

10. Divide & Conquer (Extended)

Basic Steps
1. Divide
2. Conquer
3. Combine
Common Examples
 Merge Sort
 Quick Sort
 Binary Search
 Strassen’s Matrix Multiplication
 Closest Pair of Points (Advanced topic)
Master Theorem (Beyond Syllabus Level)
Used to find T(n) of D&C algorithms:
T(n) = aT(n/b) + f(n)
3 cases used for complexity determination.

11. Recursion (Basic + Advanced Concepts)

11.1 Types of Recursion
 Direct recursion
 Indirect recursion
 Tail recursion
 Non-tail recursion
 Mutual recursion
11.2 Recurrence Relations (Beyond)
Common forms:
 T(n) = T(n – 1) + c
 T(n) = 2T(n/2) + n
 T(n) = T(n/2) + log n
11.3 Solving Recurrences
 Recursion tree method
 Iteration method
 Master theorem
 Substitution method

⭐ 12. Analyzing Recursive Algorithms (Extended Coverage)

Methodologies
1. Counting operations
2. Recursion tree expansion
3. Master theorem
4. Worst, Best, Average case analysis
Examples Beyond Syllabus
 Tower of Hanoi complexity
 Fibonacci (Recursive vs DP)
 Permutation generation
 Backtracking algorithms (N-Queens)
⭐ UNIT II – LINEAR STRUCTURES (Detailed Content)

1. LIST ADT
1.1 Definition
A List ADT is an ordered collection of elements with operations:
 Insert
 Delete
 Access (get)
 Update
 Search
 Traverse
1.2 Properties
 Dynamic size
 Elements can be repeated
 Allows indexing

2. Array-Based Implementations of List ADT

2.1 Features
 Elements stored contiguously
 Fast random access (O(1))
 Insert/delete expensive (O(n)) due to shifting
2.2 Operations
 Insert at end → O(1)
 Insert at middle → O(n)
 Delete at position → O(n)
 Access → O(1)
2.3 Advantages
 Memory locality → faster in practice
 Easy implementation
2.4 Limitations
 Fixed capacity
 Costly resizing
3. Linked List Implementations of List ADT
Linked lists store nodes with:
 Data
 Reference (pointer) to next node
3.1 Advantages
 Dynamic size
 Efficient insertion/deletion
3.2 Disadvantages
 No random access
 Extra memory for pointers

4. Singly Linked Lists

Structure
Each node contains:
[ data | next ]
Operations
 Insert at beginning → O(1)
 Insert at end → O(n)
 Delete node → O(n)
 Search → O(n)
Use Cases
 Stack implementation
 Simple dynamic lists

5. Circular Linked Lists

Structure
Last node points to first node.
Advantages
 Efficient traversal of cyclic data
 No NULL at end
Applications
 Round-robin scheduling
 Music playlist cycling
6. Doubly Linked Lists
Structure
Each node has:
[ prev | data | next ]
Advantages
 Bidirectional traversal
 Delete node in O(1) if pointer given
 Insert before/after easier
Disadvantages
 Extra memory for prev pointer
 More complex operations
Applications
 Browser history
 Navigation menus
 MRU/LRU cache (OS)

7. STACK ADT
Definition
A LIFO (Last In First Out) structure.
Operations
 push(x)
 pop()
 peek()
Applications
 Function call stack
 Expression evaluation
 Backtracking algorithms
 Undo/redo in editors
Implementations
 Array-based stack
 Linked list stack
8. QUEUE ADT
Definition
A FIFO (First In First Out) structure.
Operations
 enqueue(x)
 dequeue()
 front()
 isEmpty()
Applications
 Scheduling
 Buffering (keyboard/mouse input)
 Tree traversal (BFS)
Implementation Types
 Circular array queue
 Linked list queue

9. Double Ended Queues (Deque)

Definition
A structure where insertion and deletion are allowed at both ends.
Types
 Input-restricted deque
 Output-restricted deque
Operations
 Insert front
 Insert rear
 Delete front
 Delete rear
Applications
 Sliding window algorithms
 Palindrome checking
 LRU Cache implementation

⭐ 10. APPLICATIONS OF LINEAR STRUCTURES (Beyond Syllabus)

10.1 Stacks
 Balancing parentheses
 Postfix/Prefix evaluation
 DFS (Depth-first search)
 Reversing strings
10.2 Queues
 Task scheduling
 Print queue management
 CPU Round-robin
 Online ticketing systems
10.3 Linked Lists
 Polynomial representation
 Sparse matrix representation
 Hash table chaining
10.4 Deques
 Implementing undo/redo
 Minimizing or maximizing elements in sliding window
 OS task manager
.

⭐ UNIT III – SORTING AND SEARCHING (Detailed Content)

1. Bubble Sort
 Repeatedly compares adjacent elements
 Swaps if out of order
 Time:
o Best: O(n) (optimized)
o Worst/Average: O(n²)
 Space: O(1)

2. Selection Sort
 Select minimum element and place in correct position
 Time: O(n²) in all cases
  Space: O(1)
 No. of swaps minimal

3. Insertion Sort
 Inserts each element into the sorted portion
 Time:
o Best: O(n)
o Worst: O(n²)
 Space: O(1)
 Good for small or almost-sorted data

4. Merge Sort
 Divide → Recursively sort → Merge
 Time: O(n log n)
 Space: O(n)
 Stable sort
 Suitable for linked lists

5. Quick Sort
 Partition array around pivot
 Time:
o Best/Average: O(n log n)
o Worst: O(n²) (unbalanced partitions)
 Space: O(log n) recursive stack
 Very fast in practice

6. Analysis of Sorting Algorithms

Compare based on:
 Time complexity
 Space complexity
 Stability
 In-place or not
 Adaptive behavior
  Best use-case

Algorithm Time Space Stable In-place

Bubble O(n²) O(1) Yes Yes

Selection O(n²) O(1) No Yes

Insertion O(n²) O(1) Yes Yes

Merge O(n log n) O(n) Yes No

Quick O(n log n) O(log n) No Yes

⭐ 7. Linear Search
Sequential search
 Time: O(n)
 Works with unsorted data

⭐ 8. Binary Search
Requires sorted data
 Time: O(log n)
 Space: O(1)

⭐ 9. Hashing
Technique to store elements using a hash index.
Hash Functions
 Division method
 Multiplication method
 Mid-square
 Folding
 Universal hashing

⭐ 10. Collision Handling

Collisions occur when two keys map to same index.
Techniques
 Chaining
 Open Addressing
 o Linear probing
o Quadratic probing
o Double hashing

⭐ 11. Load Factor

λ=n/m
(n = elements, m = table size)
 Higher λ → more collisions
 Ideal λ ≈ 0.7

⭐ 12. Rehashing
Create bigger table and reinsert all elements.

⭐ 13. Hashing Efficiency

Measured by:
 Collision frequency
 Load factor
 Average search time
 Clustering

⭐ UNIT IV – TREE STRUCTURES (Detailed Content)

1. Tree ADT
 Hierarchical structure
 Root + children
 Height, depth, level
 Recursive definition

2. Binary Tree ADT

Every node has at most 2 children.
Types
 Full binary tree
  Complete binary tree
 Skewed tree
 Perfect binary tree

3. Tree Traversals
Depth-First Traversals
 Pre-order (Root, Left, Right)
 In-order (Left, Root, Right)
 Post-order (Left, Right, Root)
Breadth-First Traversal
 Level order traversal (using queue)

4. Binary Search Trees (BST)

 Left subtree < root < right subtree
 Supports operations in O(log n) (balanced)
 Worst case: O(n) (skewed tree)

5. AVL Trees
Height-balanced BST
 Balance factor = (height(left) – height(right))
 BF = -1, 0, +1 allowed
 Rotations used:
o LL, RR, LR, RL
 All operations O(log n)

6. Heaps
Complete binary tree
 Max heap – parent ≥ children
 Min heap – parent ≤ children
 Used in priority queues
 Heap operations:
o Insert → O(log n)
o Delete → O(log n)
 o Heapify → O(n)

7. Multiway Search Trees

Nodes have more than 2 children
Types:
 B-trees
 B+ trees
 2-3 trees
 2-3-4 trees
Used in databases, file systems.

⭐ UNIT V – GRAPH STRUCTURES (Detailed Content)

1. Graph ADT
Graph G = (V, E)
 Directed/Undirected
 Weighted/Unweighted

2. Representations of Graphs
 Adjacency matrix – O(n²)
 Adjacency list – O(V + E)
 Edge list

3. Graph Traversals
DFS (Depth First Search)
 Uses stack / recursion
 Time: O(V + E)
BFS (Breadth First Search)
 Uses queue
 Time: O(V + E)

4. DAG (Directed Acyclic Graph)

  No cycles
 Used in:
o Scheduling
o Compiler dependency graphs
o DP graphs

5. Topological Ordering
Linear ordering of DAG nodes
 Kahn’s algorithm
 DFS-based algorithm

6. Greedy Algorithms
Technique for optimization problems.
Examples:
 Kruskal
 Prim
 Dijkstra
 Fractional knapsack
 Huffman coding

7. Dynamic Programming
Overlapping subproblems + optimal substructure.
Examples:
 Bellman-Ford
 Floyd–Warshall
 Knapsack
 Matrix chain multiplication
 Longest common subsequence

8. Shortest Paths
Single Source
 Dijkstra (no negative weights)
 Bellman-Ford (negative weights allowed)
All Pairs
 Floyd–Warshall

9. Minimum Spanning Trees (MST)

Spanning tree with minimum cost.
Algorithms
 Kruskal’s (greedy, union–find)
 Prim’s (greedy, priority queue)

10. Complexity Classes and Intractability (Intro)

P Class
 Solvable in polynomial time
NP Class
 Verifiable in polynomial time
NP-complete
 Hardest problems in NP
NP-hard
 At least as hard as NP-complete problems
Examples:
 TSP
 Vertex cover
 SAT
 SUDHARSAN ENGINEERING COLLEGE
(Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )
(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING

COURSE OUTCOMES
CO1 : Explain abstract data types.

CO2 : Design, implement, and analyze linear data structures, such as lists, queues, and
stacks, according to the needs of different applications.

CO3 : Design, implement, and analyze efficient tree structures to meet requirements
such as searching, indexing, and sorting.

CO4 : Model problems as graph problems and implement efficient graph algorithms to solve
them.
 SUDHARSAN ENGINEERING COLLEGE
(Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )
(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING

Unit wise Question Bank

⭐ UNIT I – ABSTRACT DATA TYPES

PART-A
1. Define Abstract Data Type (ADT).
2. What is the relationship between ADTs and classes?
3. What is OOP? Mention two principles.
4. What is a namespace in Python?
5. Differentiate shallow copy and deep copy.
6. What is asymptotic notation?
7. Define recursion.
8. What is Divide and Conquer?
9. Give an example of a recursive algorithm.
10. What is algorithm analysis?
PART-B
1. Explain ADTs, their importance, and how they relate to classes and OOP with
examples in Python.
2. Discuss namespaces, inheritance, shallow and deep copying in Python with suitable
examples.
3. Explain asymptotic notations and analyze algorithms using Big-O, Omega, Theta.
4. Describe Divide & Conquer strategy and explain merge sort / quick sort using this
strategy.
5. Analyze recursive algorithms using recurrence relations and recursive tree method.

⭐ UNIT II – LINEAR STRUCTURES

 PART-A
1. Define List ADT.
2. What is an array-based list implementation?
3. Define singly linked list.
4. What is a circular linked list?
5. Write two applications of doubly linked list.
6. Define Stack ADT.
7. What is a Queue?
8. What is a deque?
9. Write any two applications of stacks.
10. What is meant by linked list node?
PART-B
1. Explain array-based and linked list implementations of the List ADT with advantages
and disadvantages.
2. Describe singly, circular, and doubly linked lists with diagrams and operations.
3. Explain Stack ADT and Queue ADT with operations and applications.
4. Explain double-ended queue (deque) with types and use cases.
5. Compare stacks, queues, and deques in terms of implementation, performance, and
applications.

⭐ UNIT III – SORTING AND SEARCHING

PART-A
1. Define bubble sort.
2. What is selection sort?
3. Write the best case for insertion sort.
4. What is merge sort?
5. Define pivot in quick sort.
6. What is linear search?
7. What is binary search?
8. Define hash function.
9. What is collision in hashing?
10. Define load factor.
PART-B
1. Explain bubble sort, selection sort, insertion sort, merge sort, and quick sort with
examples and analysis.
2. Compare linear search and binary search with time complexities and use cases.
3. Explain hashing, hash functions, collision handling techniques, rehashing, and
efficiency.
4. Discuss the analysis of sorting algorithms in detail with comparison table.
5. Describe quick sort algorithm and derive its best, average, and worst-case time
complexities.

⭐ UNIT IV – TREE STRUCTURES

✅ 2-MARK QUESTIONS
1. Define tree ADT.
2. What is a binary tree?
3. List tree traversal techniques.
4. Define Binary Search Tree (BST).
5. What is AVL tree?
6. Define balance factor.
7. What is a heap?
8. Define min-heap and max-heap.
9. What is a multiway search tree?
10. Write two applications of AVL trees.

PART-B
1. Explain tree ADT, binary tree ADT, and tree traversal methods with examples.
2. Explain binary search trees with insertion, deletion, searching algorithms and
examples.
3. Describe AVL trees and explain all types of rotations (LL, RR, LR, RL).
4. Explain heaps, heap operations, and applications in priority queues.
5. Explain multiway search trees with examples (B-tree/B+ tree concept).

⭐ UNIT V – GRAPH STRUCTURES

PART-A
1. Define Graph ADT.
2. What is adjacency list?
3. Define DFS.
4. Define BFS.
5. What is DAG?
6. What is topological ordering?
7. Define greedy algorithm.
8. What is dynamic programming?
9. Define shortest path.
10. What is MST?
PART-B
1. Explain graph ADT, graph representations, and graph traversal techniques
(BFS/DFS).
2. Describe DAG and explain the algorithm for topological sorting.
3. Explain greedy algorithms and dynamic programming with examples (Kruskal /
Dijkstra / Knapsack).
4. Explain shortest path algorithms (Dijkstra, Bellman–Ford, Floyd–Warshall).
5. Discuss minimum spanning tree algorithms — Kruskal’s and Prim’s — with
examples.

SUDHARSAN ENGINEERING COLLEGE

 (Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )
(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING

CONTINUOUS INTERNAL ASSESSMENT – I & II MARK STATEMENT

SUBJECT CODE AND NAME : AD3291& DATA STRUCTURES AND ALGORITHMS

YEAR/SEM : II/V III ACADEMIC YEAR : 2025-2026

[Link] REG NO STUDENT NAME Internal Assessment marks

(out of 100)
IAT - I IAT - II
1
814424148001 DEEPAK K 78 80
2
814424148002 DHANABALAN P 71 81
3
814424148003 DHARSHINI N 87 93
4
814424148004 DHEERAJ S 71 80
5
814424148005 GURUBALAN M 80 86
6 ILANTHAMIZH
814424148006 BHARATHI M 86 92
7
814424148007 PRABAKARAN B 71 93
8
814424148008 PRABHAKARAN S 85 92
9
814424148009 PRIYA B 87 95
10 SATHIYA
814424148010 ROOPHAN S 73 80
11 814424148011 SINEKAN R 74 80
12
814424148401 ABARNATH A 71 80
13
814424148301 NIKITHAN T 72 80
14
814424148302 SUTHARSAN K 71 80

FACUITY INCHARGE HOD/AI&ML

 SUDHARSAN ENGINEERING COLLEGE
(Approved by AICTE, New Delhi | Affiliated to Anna University, Chennai )
(Accredited by NAAC with ‘A’ Grade)
Sathiyamangalam, Kulathur (TK), Pudukkottai District – 622 501
Mobile No: 98434 90901
Website: [Link] Email: principal@[Link]

DEPARTMENT OF ARTIFICIAL INTELLIGECE AND MACHINE LEARNING

CONTINUOUS INTERNAL ASSESSMENT – I & II MARK STATEMENT

SUBJECT CODE AND NAME : AD3291& DATA STRUCTURES AND ALGORITHMS

YEAR/SEM : II/V III ACADEMIC YEAR : 2025-2026

[Link] REG NO STUDENT NAME 10-11-2025 13-11-2025

1
814424148001 DEEPAK K / /
2
814424148002 DHANABALAN P / /
3
814424148003 DHARSHINI N / /
4
814424148004 DHEERAJ S / /
5
814424148005 GURUBALAN M / /
6 ILANTHAMIZH
814424148006 BHARATHI M / /
7
814424148007 PRABAKARAN B / /
8
814424148008 PRABHAKARAN S / /
9
814424148009 PRIYA B / /
10 SATHIYA
814424148010 ROOPHAN S / /

11 814424148011 SINEKAN R / /
12
814424148401 ABARNATH A / /
13
814424148301 NIKITHAN T / /
14
814424148302 SUTHARSAN K / /

FACUITY INCHARGE HOD/AI&ML