TECHNOCRATS INSTITUTE OF TECHNOLOGY
(An Autonomous Institute Affiliated to RGPV Bhopal)
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
Semester/Year II / I Program B.Tech–CSE
Subject
ESC Subject Code: ES-205 Subject Name Data Structure: Level-2
Category
Maximum Marks Allotted Contact Total
Theory Practical Total Hours Credit
Marks s
ES MS Assignment/Quiz ES LW L T P
- - - 30 20 50 - - 6 3
Course Objective: Descriptions
1. Understand advanced features of the C++ language.
2. Explore advanced language components like templates, exception handling, and STL.
3. Develop efficient, modular, and reusable code using OOP principles.
4. Apply object-oriented concepts such as classes, objects, inheritance, encapsulation, and
polymorphism in data structure implementation.
5. Implement advanced data structures such as trees, heaps, graphs, hash tables, etc.
6. Analyse and apply searching and sorting techniques to real-world problems.
7. Use templates and generic programming to create reusable data structures.
8. Develop robust programs using exception handling for error management.
9. Understand how data structures support system software, databases, and application software
development.
UNITs
Review of C++ programming language. Introduction to Data Structure: Concepts of Data
and Information, Classification of Data structures, Abstract Data Types, Implementation
aspects: Memory representation. Data structures operations and its cost estimation.
I Introduction to linear data structures- Arrays, Linked List: Representation of linked list in
memory, different implementation of linked list. Circular linked list, doubly linked list, etc.
Application of linked list: polynomial manipulation using linked list, etc.
Stacks: Stacks as ADT, Different implementation of stack, multiple stacks. Application of
II Stack: Conversion of infix to postfix notation using stack, evaluation of postfix expression,
Recursion. Queues: Queues as ADT, Different implementation of queue, Circular queue,
Concept of Dqueue and Priority Queue, Queue simulation, Application of queues.
Tree: Definitions - Height, depth, order, degree etc. Binary Search Tree - Operations,
III Traversal, Search. AVL Tree, Heap, Applications and comparison of various types of tree;
Introduction to forest, multi-way Tree, B tree, B+ tree, B* tree and red-black tree.
IV Graphs: Introduction, Classification of graph: Directed and Undirected graphs, etc,
Representation, Graph Traversal: Depth First Search (DFS), Breadth First Search (BFS),
Graph algorithm: Minimum Spanning Tree (MST)- Kruskal, Prim’s algorithms. Dijkstra’s
shortest path algorithm; Comparison between different graph algorithms. Application of
graphs.
V Sorting: Introduction, Sort methods like: Bubble Sort, Quick sort. Selection sort, Heap sort,
Insertion sort, Shell sort, Merge sort and Radix sort; comparison of various sorting
techniques.
Searching: Basic Search Techniques: Sequential search, Binary search, Comparison of
search methods. Hashing & Indexing.
Case Study: Application of various data structures in operating system, DBMS etc.
Course Outcomes:
CO1: Understand and apply advanced C++ features (OOP, templates, exception handling) for data
structure implementation.
CO2: Implement and analyze linear data structures like arrays, linked lists, stacks, and queues.
CO3: Construct and apply tree structures such as BST, AVL, heaps, B-trees, etc., and evaluate their
efficiency.
CO4: Analyze and apply graph algorithms including traversal, shortest paths, and MSTs for real-world
problems.
CO5: Apply and compare sorting, searching, hashing, and indexing techniques in
computing environments.
Reference Books-
1. AM Tanenbaum, Y Langsam& MJ Augustein, “Data structure using C and C++”, Prentice Hall India.
2. Robert Kruse, Bruse Leung, “Data structures & Program Design in C”, Pearson Education.
3. Aho, Hopcroft, Ullman, “Data Structures and Algorithms”, Pearson Education.
4. N. Wirth, “Algorithms + Data Structure = Programs”, Prentice Hall.
5. Jean – Paul Trembly , Paul Sorenson, “An Introduction to Structure with application”, TMH.
6. Richard, GilbergBehrouz, Forouzan ,“Data structure – A Pseudocode Approach
List/Links of e-learning resource
CodeChef – Data Structures & Algorithms Practice
Link: https://www.codechef.com/practice/tags/datastructures
LeetCode https://leetcode.com/explore/
Practice problems grouped by data structures. Great for hands-on coding.
HackerRank – Data Structures Track
https://www.hackerrank.com/domains/tutorials/10-days-of-data-structures
Covers arrays, linked lists, stacks, queues, trees, etc.
Suggestive list of experiments:
1. Implement linear and binary search on arrays.
2. Implement sorting algorithms: Bubble, Insertion, Selection, Merge, and Quick Sort.
3. Perform matrix operations: Addition, multiplication, and transpose.
4. Write a program to check for palindrome strings and perform string reversal.
5. Implement singly linked list with insertion, deletion, and traversal.
6. Implement doubly linked list and circular linked list operations.
7. Reverse a linked list (iterative and recursive approaches).
8. Merge two sorted linked lists into one.
9. Implement stack using arrays and linked lists.
10. Convert infix expression to postfix using stack.
11. Evaluate postfix expression using stack.
12. Implement queue using arrays and linked lists.
13. Implement circular queue and dequeue (double-ended queue).
14. Create a binary tree and perform traversals: Inorder, Preorder, Postorder.
15. Implement binary search tree (BST) with insert, search, and delete operations.
16. Find height of a binary tree and count leaf/non-leaf nodes.
17. Create an expression tree and evaluate it.
18. Implement a graph using adjacency matrix and list.
19. Implement BFS (Breadth-First Search) and DFS (Depth-First Search).
20. Implement Dijkstra’s shortest path algorithm.
21. Detect cycles in an undirected graph using DFS.
22. Implement hash tables with linear probing and chaining.
23. Implement Heap and perform heap sort.
24. Implement disjoint sets using union-find.
25. Implement topological sort using DFS and Kahn’s algorithm.
COs PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO1 PO11 PO12
CO-1 3 2 2 2 2
3 2
CO-2 3 2 2
2
CO-3 3 3 3 2 2
3 2 2
CO-4 3 3 3
3 2 2
CO-5 3 3 2
Value Meaning
Strong correlation: 3
Moderate correlation: 2
Slight correlation: 1
No significant correlation: Blank
