RTMNU · Second Year B.Tech Information Technology · NEP 2020
Data Structure and Algorithms
BIT3T09 · Semester III · 3 credits · College 30 + university 70
Unit 1: Introduction to Algorithm; Sorting and Searching
8 hoursGeneral concepts and types of data structures with their properties and operations; time and space analysis with big-O, theta and omega notation and average-, best- and worst-case analysis; selection, insertion, heap and shell sort; linear and binary search.
Examined in the 70-mark end-semester paper
- Data structures and abstract data types
- Classification of data structures
- Time and space complexity, asymptotic notation
- Bubble, selection and insertion sort
- Heaps and heap sort
- Linear and binary search
Unit 2: Stacks and Queues
7 hoursThe stack ADT, its operations and implementation, multiple stacks and stack applications; prefix and postfix expressions, infix-to-prefix and infix-to-postfix conversion and their evaluation; the queue ADT: simple, circular, double-ended and priority queues and their applications.
Examined in the 70-mark end-semester paper
- Stack implementation with arrays and linked lists
- Stack applications: recursion and expression conversion
- Evaluating postfix and prefix expressions
- Queue, circular queue and deque
- Priority queues
Unit 3: Linked Lists
7 hoursLinked-list operations and representation; singly, circular and doubly linked lists; polynomial addition and multiplication with linked lists.
Examined in the 70-mark end-semester paper
- Singly linked list
- Doubly and circular linked lists
Unit 4: Trees
7 hoursTree terminology and properties; binary trees and binary search trees and their operations; threaded binary trees; AVL trees and rotations, red–black trees, B-trees and B+ trees; tree traversals and their applications.
Examined in the 70-mark end-semester paper
- Binary trees and their representation
- Binary tree traversals
- Binary search trees
- Threaded binary trees
- AVL and 2-3 trees
- Red-black trees
- B-trees and B+ trees
Unit 5: Graphs and Hashing
7 hoursGraph representation and applications, DFS and BFS traversal; hash functions and hash tables, simple hash functions and collision handling.
Examined in the 70-mark end-semester paper
- Graph representation, BFS and DFS
- Hash functions
- Collision handling: chaining and open addressing
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).