GUG SY CSE syllabus

GUG · Second Year B.Tech. Computer Science and Engineering · NEP 2020

Advanced Data Structures

STPCCCSE403 · Semester IV · 4 credits · IE 10 + mid-semester 10 + ESE 80

4 credits: 3 lectures and 1 tutorial a week.

  1. Unit 1: Linked Lists

    10 hours

    Singly linked lists: representation in memory and the algorithms for traversal, search, insertion, deletion, reversal and ordering; doubly and circular linked lists and their analysis; linked representation of stacks and queues.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

  2. Unit 2: Trees and Their Variants

    8 hours

    Tree terminology; binary trees and their operations; binary search trees and the time analysis of their operations; threaded binary trees; tree rotations and AVL trees.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

  3. Unit 3: Graphs

    8 hours

    Graph terminology and representations; DFS and BFS with their complexity; path finding with Dijkstra's single-source and Floyd's all-pairs shortest paths; spanning trees by Prim's and Kruskal's algorithms.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

  4. Unit 4: Heaps and Disjoint Sets

    8 hours

    Binary heaps, min-heap and max-heap operations; heaps in priority queues and sorting; the disjoint-set ADT and union-find operations, with applications in dynamic connectivity and Kruskal's algorithm.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Heaps and balanced trees
    • Disjoint sets and union-find
  5. Unit 5: Advanced Data Structures and Applications

    6 hours

    Tries (prefix trees) for string matching and retrieval; segment trees and binary indexed trees for range queries and updates; amortised analysis with examples such as stack expansion and dynamic arrays.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Tries
    • Segment trees and binary indexed trees
    • Amortised analysis

Unit contents are summarised from the official GUG syllabus . AiCanCode.org is not affiliated with Gondwana University, Gadchiroli.