RTMNU · Second Year B.Tech Computer Science & Engineering (Data Science) · NEP 2020
Data Structures and Algorithms
BCSE3T09 · Semester III · 3 credits · College 30 + university 70
Unit 1: Introduction to Data Structures; Sorting and Searching
Common operations on and types of data structures, program design and complexity, time complexity, order of growth and asymptotic notation; insertion, selection, merge, shell and radix sort; linear and binary search and hashing.
Examined in the 70-mark end-semester paper
- Data structures and their types
- Time and space complexity
- Asymptotic notations
- Insertion, bubble and selection sort
- Merge sort and quick sort
- Shell sort
- Radix sort
- Sequential and binary search
Unit 2: Arrays and Linked Lists
Linear arrays, traversal, insertion and deletion, bubble sort and searching; linked lists in memory, traversal and search, memory allocation and garbage collection, insertion and deletion, header, circular and two-way lists.
Examined in the 70-mark end-semester paper
- Arrays and sparse matrices
- Singly linked lists
- Garbage collection
- Circular linked lists
- Doubly linked lists
Unit 3: Stacks, Recursion and Queues
Array and linked stacks, the stack ADT, Polish notation and stack applications; recursion with the towers of Hanoi; linked queues, the queue ADT, circular queues, deques, priority queues and their applications.
Examined in the 70-mark end-semester paper
- Stack ADT and operations
- Expression conversion and evaluation
- Recursion
- Linked stacks and queues
- Circular queues
- Deques and priority queues
Unit 4: Trees
Binary tree representation, insertion, deletion and traversal (including stack-based traversal), header nodes and threaded binary trees; binary search trees; AVL trees; m-way search trees, B-trees and B+ trees.
Examined in the 70-mark end-semester paper
- Tree terminology and representation
- Binary tree traversals
- Threaded binary trees
- Binary search trees
- AVL trees
- B-trees and B+ trees
Unit 5: Graphs and their Applications
Graph terminology, sequential representation with the adjacency and path matrices, linked representation, operations on graphs, traversal, posets and topological sorting, and spanning trees.
Examined in the 70-mark end-semester paper
- Graph representation
- Warshall's algorithm for transitive closure
- DFS and BFS
- Topological sorting
- Prim's and Kruskal's algorithms
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).