SPPU · Second Year Artificial Intelligence and Data Science · 2024 Pattern (Revised)
Data Structures
PCC-201-AID · Semester III · 3 credits · CCE 40 + end-semester 60
Unit 1: Searching, Sorting and Hashing
9 hoursTypes of data structures; space and time complexity, Big-O, Theta and Omega, the step-count method; sequential and binary search; insertion, bubble, selection, merge, quick and radix sort; hash tables and functions, chaining, linear and quadratic probing, double hashing and overflow.
Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)
- Data structures and their types
- Time and space complexity
- Asymptotic notations
- Sequential and binary search
- Insertion, bubble and selection sort
- Merge sort and quick sort
- Radix sort
- Hashing and collision resolution
Unit 2: Memory Allocation and Linked Lists
9 hoursStatic and dynamic allocation; linked lists through dynamic memory; the list ADT; singly, circular, doubly and doubly circular lists; create, traverse, search, insert, delete, sort and concatenate; polynomial addition; generalised linked lists.
Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)
- Static and dynamic memory allocation
- Singly linked lists
- Circular linked lists
- Doubly linked lists
- Polynomial addition with linked lists
- Generalised linked lists
Unit 3: Stacks and Queues
9 hoursThe stack ADT and its array representation; expression conversion and evaluation; recursion; the queue ADT and its array representation; circular queues, deques and priority queues.
Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)
- Stack ADT and operations
- Expression conversion and evaluation
- Recursion
- Queue ADT and operations
- Circular queues
- Deques and priority queues
Unit 4: Trees
9 hoursTree terms, representations and traversals; binary trees and binary search trees; threaded BSTs; optimal BSTs; AVL trees; heaps.
Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)
- Tree terminology and representation
- Binary tree traversals
- Binary search trees
- Threaded binary trees
- Optimal binary search trees
- AVL trees
- Heaps
Unit 5: Graphs
9 hoursAdjacency matrix and list; DFS and BFS; Prim's and Kruskal's minimum spanning trees; Dijkstra's shortest paths; Floyd–Warshall; topological ordering.
Marks: 12 in the end-semester exam · CCE: Seminar, open-book test or quiz (10 marks, Unit 5)
- Graph representation
- DFS and BFS
- Prim's and Kruskal's algorithms
- Dijkstra's algorithm
- Floyd-Warshall algorithm
- Topological sorting
Unit contents are summarised from the official SPPU syllabus . AiCanCode.org is not affiliated with Savitribai Phule Pune University.