PAHSU · Second Year B.Tech. Artificial Intelligence and Data Science · NEP 2020
Data Structure
ADPCC-02 · Semester III · 4 credits · ISE 30 + ESE 70
All its practical assignments are implemented in Python; the course also carries 25 marks of internal continuous assessment and a 25-mark practical oral exam.
Unit 1: Introduction to Data Structures, Searching and Sorting
6 hoursTypes of data structures: static and dynamic, primitive and non-primitive, linear and non-linear; arrays in Python; linear and binary search; bubble, selection, insertion, merge, quick, shell, radix and heap sort; time and space complexity.
Examined in the 70-mark end-semester paper
- Data structures and their types
- Sequential and binary search
- Insertion, bubble and selection sort
- Merge sort and quick sort
- Shell sort
- Radix sort
- Heaps
- Time and space complexity
Unit 2: Stack and Queue
6 hoursStacks: representation, operations, implementation and applications such as converting Polish notations and evaluating postfix expressions; queues: representation and operations, linear, circular and priority queues.
Examined in the 70-mark end-semester paper
- Stack ADT and operations
- Expression conversion and evaluation
- Queue ADT and operations
- Circular queues
- Deques and priority queues
Unit 3: Lists
6 hoursSingly, doubly and circular linked lists: representation and operations; stacks and queues using linked lists; adding and subtracting two polynomials.
Examined in the 70-mark end-semester paper
- Singly linked lists
- Doubly linked lists
- Circular linked lists
- Linked stacks and queues
- Polynomial addition with linked lists
Unit 4: Hashing
4 hoursHash functions and choosing one; collision resolution by open addressing (linear probing, quadratic probing, double hashing) and by chaining.
Examined in the 70-mark end-semester paper
- Hash functions and their applications
- Hashing and collision resolution
- Open addressing and perfect hashing
Unit 5: Trees
5 hoursTree terminology; binary trees and binary search trees; inorder, preorder and postorder traversal; operations and linked implementation; threaded binary trees.
Examined in the 70-mark end-semester paper
- Tree terminology and representation
- Binary tree traversals
- Binary search trees
- Threaded binary trees
Unit 6: Advanced Trees
7 hoursMultiway and balanced multiway search trees: traversal and insertion in B-trees and B+ trees; AVL trees: height, insertion, deletion and single and double rotations.
Examined in the 70-mark end-semester paper
- B-trees and B+ trees
- AVL trees
Unit 7: Graph Fundamentals
3 hoursGraph terminology, directed and undirected graphs; adjacency-matrix and adjacency-list representation; BFS and DFS traversal.
Examined in the 70-mark end-semester paper
- Graph representation
- DFS and BFS
Unit 8: Graph Algorithms and Applications
5 hoursDijkstra's shortest-path algorithm; minimum spanning trees by Prim's and Kruskal's algorithms; graphs in social networks, recommendation systems and knowledge graphs.
Examined in the 70-mark end-semester paper
- Dijkstra's algorithm
- Prim's and Kruskal's algorithms
- Collaborative filtering for recommendation
- Knowledge graphs: RDF, RDFS and OWL
Unit contents are summarised from the official PAHSU syllabus . AiCanCode.org is not affiliated with Punyashlok Ahilyadevi Holkar Solapur University (PAHSU).