RTMNU SY IT syllabus

RTMNU · Second Year B.Tech Information Technology · NEP 2020

Data Structure and Algorithms

BIT3T09 · Semester III · 3 credits · College 30 + university 70

All notes for this subject
  1. Unit 1: Introduction to Algorithm; Sorting and Searching

    8 hours

    General 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
  2. Unit 2: Stacks and Queues

    7 hours

    The 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
  3. Unit 3: Linked Lists

    7 hours

    Linked-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
  4. Unit 4: Trees

    7 hours

    Tree 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
  5. Unit 5: Graphs and Hashing

    7 hours

    Graph 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).