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.
Unit 1: Linked Lists
10 hoursSingly 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
Unit 2: Trees and Their Variants
8 hoursTree 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
- Trees and binary trees
- Binary tree traversals: recursive and non-recursive
- Binary search trees
- Threaded binary trees
- AVL trees and rotations
Unit 3: Graphs
8 hoursGraph 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
- Graph representation
- Graph traversal: DFS and BFS
- Dijkstra's shortest path and topological sorting
- Floyd-Warshall all-pairs shortest paths
- Minimum spanning trees: Prim's and Kruskal's algorithms
Unit 4: Heaps and Disjoint Sets
8 hoursBinary 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
Unit 5: Advanced Data Structures and Applications
6 hoursTries (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.