SPPU · Second Year Electronics & Telecommunication Engineering · 2024 Pattern
Data Structures and Algorithms
MDM-221-ETC · Semester III · 3 credits · CCE 40 + end-semester 60
Unit 1: Introduction to Data Structures and Complexity Analysis
9 hoursLinear and non-linear data structures and abstract data types; time and space complexity, Big-O, Omega and Theta, best, worst and average cases; linear and binary search; bubble, selection and insertion sort.
Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)
- Data structures and abstract data types
- Time and space complexity, asymptotic notation
- Linear and binary search
- Bubble, selection and insertion sort
Unit 2: Stack and Queue
9 hoursStack operations, array representation and the stack ADT; reversing data, infix-to-postfix conversion and postfix evaluation; queue operations, array representation, the circular queue, priority queue and applications of queues.
Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)
- Stack and its array implementation
- Infix to postfix conversion
- Postfix expression evaluation
- Queue and its array implementation
- Circular queue
- Priority queue and applications of queues
Unit 3: Linked List
9 hoursPointers and dynamic memory allocation (malloc, calloc, realloc, free); sequential versus linked organisation; singly, doubly and circular linked lists; stacks and queues using linked lists; polynomials as linked lists.
Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)
- Pointers and dynamic memory allocation
- Singly linked list operations
- Doubly and circular linked lists
- Stack and queue using linked lists
- Polynomial representation and addition with linked lists
Unit 4: Trees
8 hoursTree concepts and binary-tree terminology, representation and traversals; binary search tree operations; AVL trees and rotations.
Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)
- Tree terminology and binary trees
- Binary tree representation and traversals
- Binary search tree operations
- AVL trees and rotations
Unit 5: Graphs
8 hoursGraph terminology, adjacency matrix and list; BFS and DFS traversal; minimum spanning trees by Kruskal's and Prim's algorithms; Dijkstra's shortest path.
Marks: 12 in the end-semester exam · CCE: Seminar, open-book test or quiz (10 marks, Unit 5)
- Graph terminology and representation
- BFS and DFS traversal
- Minimum spanning tree: Kruskal's algorithm
- Minimum spanning tree: Prim's algorithm
- Dijkstra's shortest path algorithm
Unit contents are summarised from the official SPPU syllabus . AiCanCode.org is not affiliated with Savitribai Phule Pune University.