SGBAU · Second Year B.E. Information Technology · NEP 2020
Data Structures
4IT209PC · Semester IV · 3 credits · IE 40 + ESE 60
Radix sort, header and two-way linked lists and record structures are in the syllabus but have no separate notes yet.
Unit 1: Introduction to Data Structures
7 hoursData structure operations, algorithmic notation and complexity of algorithms; string processing: storing strings, string operations, word processing and pattern-matching algorithms.
Examined in the 60-mark end-semester paper
- Data structures and abstract data types
- Algorithms and design strategies
- Time and space complexity, asymptotic notation
- Naïve string matching
- Knuth–Morris–Pratt algorithm
Unit 2: Arrays & Record Structure
7 hoursLinear arrays, their memory representation, traversal, insertion and deletion; bubble sort; linear and binary search; multi-dimensional and pointer arrays; record structures.
Examined in the 60-mark end-semester paper
- Classification of data structures
- Bubble, selection and insertion sort
- Linear and binary search
Unit 3: Linked Lists
7 hoursMemory representation, traversal and searching of linked lists; memory allocation and garbage collection; insertion and deletion; header and two-way linked lists.
Examined in the 60-mark end-semester paper
- Singly linked list
- Doubly and circular linked lists
Unit 4: Stacks & Queues
7 hoursSequential representation of stacks; arithmetic expressions and Polish notation; quick sort, recursion and the Tower of Hanoi; queues, deques and priority queues.
Examined in the 60-mark end-semester paper
- Stack implementation with arrays and linked lists
- Stack applications: recursion and expression conversion
- Evaluating postfix and prefix expressions
- Recursion and the Tower of Hanoi
- Queue, circular queue and deque
- Priority queues
Unit 5: Trees
7 hoursBinary trees, their memory representation and traversal; header nodes; binary search trees; heaps and heap sort; path length and Huffman's algorithm.
Examined in the 60-mark end-semester paper
- Binary trees and their representation
- Binary tree traversals
- Binary search trees
- Heaps and heap sort
- Huffman coding
Unit 6: Graphs & Sorting Algorithms
7 hoursMemory representation of graphs, Warshall's algorithm, graph operations, breadth-first and depth-first search; insertion, selection, radix and merge sort.
Examined in the 60-mark end-semester paper
- Graph representation, BFS and DFS
- Closures and Warshall's algorithm
- Bubble, selection and insertion sort
- Divide and conquer: merge sort and quick sort
Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).