1131301 DATA STRUCTURES AND ALGORITHMS L T P
C
3 0 0 3
COURSE OBJECTIVES:
To understand algorithms and analyze their efficiency using asymptotic notations.
To study and apply linear data structures for problem solving.
To implement searching and sorting algorithms.
To understand and apply tree data structures.
To study graph structures and algorithm design techniques such as Greedy, Dynamic
Programming, and Backtracking.
UNIT I – ALGORITHM ANALYSIS AND FUNDAMENTALS 9
Introduction of Data Structure – Characteristics of an Algorithm – Problem Solving Techniques –
Algorithm Specification – Pseudocode – Abstract Data Types (ADT)-Analysis of Algorithms –
Time and Space Complexity – Asymptotic Notations (Big-O, Big-Ω, Big-Θ) – Best, Worst and
Average Case Analysis – Recurrence Relations – Master Theorem – Amortized Analysis.
UNIT II – LINEAR DATA STRUCTURES 9
Arrays – 1D and 2D Arrays – Sparse Matrices-Linked Lists – Singly Linked List – Doubly Linked
List – Circular Linked List – Applications-Stacks – Stack ADT – Implementation using Arrays and
Linked Lists – Applications (Expression Evaluation, Infix to Postfix)-Queues – Linear Queue –
Circular Queue – Dequeue – Priority Queue.
UNIT III –SORTING, SEARCHING AND DIVIDE & CONQUER 9
Sorting – Bubble Sort – Selection Sort – Insertion Sort – Merge Sort – Quick Sort – Heap Sort –
Comparison of Sorting Techniques- Searching – Linear Search – Binary Search-Divide and
Conquer – Concept – Binary Search – Merge Sort – Quick Sort – Strassen’s Matrix Multiplication.
UNIT IV – TREES, HASHING AND GREEDY METHOD 9
Trees – Binary Trees – Tree Traversals – Binary Search Trees – AVL Trees – Heap – B-Tree-
Hashing – Hash Functions – Collision Resolution Techniques – Chaining – Open Addressing-
Greedy Algorithms – Activity Selection – Huffman Coding – Minimum Spanning Tree (Kruskal’s
and Prim’s Algorithms) – Dijkstra’s Algorithm.
UNIT V – GRAPH AND ADVANCED ALGORITHMS 9
Graph Representation – BFS – DFS – Topological Sorting – Strongly Connected Components-
Dynamic Programming – Matrix Chain Multiplication – Longest Common Subsequence – 0/1
Knapsack – Bellman-Ford Algorithm-Backtracking – N-Queens – Graph Coloring – Sum of
Subsets-Branch and Bound – Travelling Salesman Problem.
Course Outcomes
Upon completion of the course, students will be able to:
CO1 – Analyze the efficiency of algorithms using asymptotic techniques.
CO2 – Apply linear data structures for problem solving.
CO3 – Implement searching and sorting algorithms effectively.
CO4 – Use tree data structures for real-time applications.
CO5 – Use graph and apply algorithm design techniques such as Greedy, Dynamic Programming
and Backtracking.
TOTAL:45 PERIODS
TEXT BOOKS
1. Mark Allen Weiss, Data Structures and Algorithm Analysis in C, 2nd Edition, Pearson
Education, 2005.
2. Kamthane, Introduction to Data Structures in C, 1st Edition, Pearson Education, 2007
REFERENCES
1. Langsam, Augenstein and Tanenbaum, Data Structures Using C and C++, 2nd Edition,
Pearson Education, 2015.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald [Link], Clifford Stein, Introduction to
Algorithms", Fourth Edition, Mcgraw Hill/ MIT Press, 2022.
3. Alfred V. Aho, Jeffrey D. Ullman,John E. Hopcroft ,Data Structures and Algorithms,
1st edition, Pearson, 2002.
4. Kruse, Data Structures and Program Design in C, 2nd Edition, Pearson Education, 2006.
CO’s-PO’s & PSO’s MAPPING
CO’s PO’s PSO’s
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
1 1 2 2 1 0 0 0 0 2 1 2 2 2 2 3
2 3 3 1 1 0 0 0 0 1 1 1 3 1 2 2
3 2 1 3 1 0 0 0 0 1 1 2 3 3 3 3
4 3 1 3 3 0 0 0 0 1 2 3 3 2 1 2
5 3 2 1 1 2 0 0 0 3 3 3 1 3 1 3
AVg. 2 2 2 1 2 0 0 0 2 2 2 2 2 2 3
1 - low, 2 - medium, 3 - high, 0 - no correlation
1131321 DATA STRUCTURES AND ALGORITHMS LABORATORY L T P C
0 0 3 2
COURSE OBJECTIVES:
To understand algorithms and analyze their efficiency using asymptotic notations.
To study and apply linear data structures for problem solving.
To implement searching and sorting algorithms.
To understand and apply tree data structures.
To study graph structures and algorithm design techniques such as Greedy, Dynamic
Programming, and Backtracking.
LIST OF EXERCISES:
1. Array operations (Insertion, Deletion, Searching)
2. Sparse Matrix Representation
3. Linked List (Singly, Doubly, Circular)
4. Stack implementation and Expression Evaluation
5. Queue implementation (Linear, Circular, Priority Queue)
6. Searching Algorithms – Linear and Binary Search
7. Sorting Algorithms – Bubble, Selection, Insertion
8. Advanced Sorting – Merge Sort, Quick Sort, Heap Sort
9. Binary Tree Traversals
10. Binary Search Tree operations
11. Heap implementation.
12. Graph Traversals – BFS and DFS
13. Minimum Spanning Tree – Kruskal’s and Prim’s Algorithms
14. Shortest Path – Dijkstra’s and Bellman-Ford Algorithms
15. Dynamic Programming – LCS / 0-1 Knapsack
16. Backtracking – N-Queens Problem
TOTAL:60 PERIODS
COURSE OUTCOMES:
At the end of this course, the students will be able to:
CO1 – Analyze the efficiency of algorithms using asymptotic techniques.
CO2 – Apply linear data structures for problem solving.
CO3 – Implement searching and sorting algorithms effectively.
CO4 – Use tree data structures for real-time applications.
CO5 – Use graph and apply algorithm design techniques such as Greedy, Dynamic Programming
and Backtracking.
CO’s-PO’s & PSO’s MAPPING
CO’s PO’s PSO’s
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
1 1 2 2 1 0 0 0 0 2 1 2 2 2 2 3
2 3 3 1 1 0 0 0 0 1 1 1 3 1 2 2
3 2 1 3 1 0 0 0 0 1 1 2 3 3 3 3
4 3 1 3 3 0 0 0 0 1 2 3 3 2 1 2
5 3 2 1 1 2 0 0 0 3 3 3 1 3 1 3
AVg. 2 2 2 1 2 0 0 0 2 2 2 2 2 2 3
1 - low, 2 - medium, 3 - high, 0 - no correlation