KTU 2024 Scheme · Semester 3 · Program Core — Information Technology
Data Structures (PCITT303) Syllabus
Official KTU 2024 Scheme syllabus for Data Structures, Semester 3, Program Core — Information Technology (Information Technology).
Course Code
PCITT303
Credits
4
Teaching Hours
3:1:0:0 (L:T:P:R)
CIE Marks
40
ESE Marks
60
Exam Duration
2 Hrs 30 Min
Prerequisites
UCEST105: Algorithmic Thinking with Python; GXEST204: Programming in C
Semester
Semester 3
Course Objective
To understand and classify various data structures and their complexities, analyze algorithms for space and time efficiency, and perform basic operations on arrays, stacks and queues; to implement basic searching, sorting and hash table operations; to master operations on linked lists; and to achieve a solid grasp of tree and graph structures, their traversal methods and applications, including binary search trees, heaps and graph algorithms such as Dijkstra's shortest path.
Module-wise Syllabus
Module 1
11 contact hoursIntroduction to data structures: definitions, classifications - ADT and CDT, linear and non-linear, static and dynamic. Algorithm/program development: analysis of algorithms - space complexity, the notion of time complexity using graphical and tabular representation for linear, quadratic, cubic, logarithmic and exponential functions; asymptotic notations - best case, worst case, average case. Arrays: definition, properties, representation of single and two-dimensional arrays, sparse matrix, polynomial representation and manipulation using arrays (addition only). Stack - operations on a stack using an array. Queues - definition, operations on a queue using an array, circular queue implementation using an array, other types of queues: deque, priority queue (concept only). Applications of stack: infix to postfix conversion and postfix evaluation.
Module 2
11 contact hoursSearching: linear search and binary search. Sorting: bubble sort, selection sort, insertion sort, quicksort and merge sort (recursive algorithms only), complexity analysis of sorting algorithms (detailed analysis not required), and heap sort. Hash tables: different hash functions - division method, multiplication method, mid-square method, folding method; collision resolution techniques - closed hashing (linear probing) and its drawbacks, open hashing (separate chaining), remedies - random probing, quadratic probing, double hashing; load factor and rehashing.
Module 3
11 contact hoursLinked list: definition, array vs linked list, dynamic memory management, representation of a linked list, classification (singly linked list, doubly linked list, circular singly linked list), operations on a singly linked list - traversal, insertion, deletion and searching. Applications of linked lists: polynomial representation and manipulation (addition only). Operations on a doubly linked list - traversal, insertion, deletion and searching. Circular linked list (concept only). Linked list representation of stack and queue, stack and queue implementation and operations using linked lists.
Module 4
11 contact hoursTrees: definition, height, depth, degree, level. Binary trees: properties of binary trees, complete, perfect and full binary trees, linear and linked list representations of binary trees, binary tree traversals - preorder, inorder and postorder (recursive algorithms only), binary tree applications - expression tree creation. Binary search tree: creation, insertion, deletion and search operations. Heap: creation. Graph: definition, set representations, directed and undirected graphs, adjacency matrix and adjacency list representation. Graph traversal: Breadth First Search (BFS), Depth First Search (DFS). Graph applications: shortest path problem - Dijkstra's algorithm.
Course Outcomes
- CO1Apply the concept of data structures and analyze algorithm complexity using graphical and tabular methods in implementing stack and queue operations.
- CO2Implement and evaluate searching, sorting and hash table operations with various collision resolution techniques.
- CO3Implement and manipulate linked lists and utilize them for stack and queue operations, including polynomial manipulation.
- CO4Apply tree and graph algorithms to traverse, search and solve problems, including shortest path computations in graph structures.
Assessment Pattern (CIE: 40 marks, ESE: 60 marks)
Continuous Internal Evaluation (CIE)
| Attendance | 5 |
| Assignment / Microproject | 15 |
| Internal Examination 1 (Written) | 10 |
| Internal Examination 2 (Written) | 10 |
End Semester Examination (ESE)
Total 60 marks, 2 Hrs 30 Min. See the official KTU syllabus document for the exact Part A / Part B question pattern for this course.
Textbooks & Reference Books
Textbooks
- Classic Data Structures — Debasis Samanta (Prentice Hall, 2nd edition, 2008)
- Data Structures Through C — Yashavant Kanetkar (BPB Publications, 3rd edition, 2019)
Reference Books
- Data Structures and Algorithms — Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman (Pearson Education, 2nd edition, 2008)
- Introduction to Algorithms — T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (MIT Press, 4th edition, 2022)
- Introduction to Data Structures with Applications — J. P. Tremblay, P. G. Sorenson (Tata McGraw Hill, 2nd edition, 2001)
- Fundamentals of Data Structures in C — E. Horowitz, S. Sahni, D. Mehta (University Press, 2nd edition, 2008)
Frequently Asked Questions
How many credits is KTU Data Structures (PCITT303)?
4 credits, with 3:1:0:0 (L:T:P:R) teaching hours per week, under the KTU 2024 Scheme.
How many modules are in the PCITT303 syllabus?
4 modules, 44 total contact hours.
What is the CIE and ESE mark split for this course?
CIE (Continuous Internal Evaluation): 40 marks. ESE (End Semester Examination): 60 marks, 2 Hrs 30 Min. Total: 100 marks.
What are the recommended textbooks for PCITT303?
Classic Data Structures (Debasis Samanta); Data Structures Through C (Yashavant Kanetkar).
Is this syllabus specific to one branch, or common to others too?
This Semester 3 course is listed under Program Core — Information Technology at KTU under the 2024 Scheme — check the course header above for which branches it's common to.
Need help with KTU Data Structures?
Learnizo offers live, 1-on-1 online tuition for KTU IT subjects — matched to your exact module and semester.