M24-CAP-103 Data Structure
| Part A – Introduction | ||||
| Name of the Programme | MCA | |||
| Semester | 1st | |||
| Name of the Course | Data Structures | |||
| Course Code | M24-CAP-103 | |||
| Course Type | CC-3 | |||
| Level of the course (As per Annexure-I | 400-499 | |||
| Pre-requisite for the course (if any) | – | |||
| Course Objectives | This course introduces fundamental concepts of algorithms and data structures, including algorithmic notation, programming principles, and program analysis. Students will explore arrays, searching and sorting techniques, stacks, queues, and linked lists, along with their applications. The course also covers tree structures such as binary trees, AVL trees, B-trees, and tries, as well as graph terminology, representation, and traversal methods. Additionally, students will learn about set operations, file queries, sequential organization, index techniques, and external sorting. | |||
| Course Learning Outcomes (CLO) After completing this course, the learner will be able to: | CLO-1. Master algorithmic notation, programming principles, and implement arrays, searching and sorting techniques.
CLO-2 Apply stack and queue operations, understand linked lists, and their applications including dynamic storage management. CLO-3 Comprehend binary trees, binary search trees, AVL trees, B- trees, B+ tree indexing, Trie tree indexing, and their applications. CLO-4 Utilize graph representations, traversals, applications, sets operations, and file organization techniques. |
|||
| Credits | Theory | Practical | Total | |
| 4 | 0 | 4 | ||
| Teaching Hours per week | 4 | 0 | 4 | |
| Internal Assessment Marks | 30 | 0 | 30 | |
| End Term Exam Marks | 70 | 0 | 70 | |
| Max. Marks | 100 | 0 | 100 | |
| Examination Time | 3 hours | |||
| Part B- Contents of the Course | ||||
| Instructions for Paper- Setter: The examiner will set 9 questions asking two questions from each unit and one compulsory question by taking course learning outcomes (CLOs) into consideration. The compulsory question (Question No. 1) will consist at least 4 parts covering entire syllabus. The examinee will be required to attempt 5 questions, selecting one question from each unit and the compulsory question. All questions will carry equal marks. | ||||
| Unit | Topics | Contact
Hours |
||
| I | Introduction: Algorithmic notation – Programming principles – Creating programs- Analyzing programs. Arrays: One dimensional array, multidimensional array, pointer arrays. Searching: Linear search, Binary Search, Fibonacci search. Sorting techniques: Internal sorting – Insertion Sort, Selection Sort, Shell Sort, Bubble Sort, Quick Sort, Heap Sort, Merge Sort and Radix Sort. | 15 | ||
| II | Stacks: Definition – operations – applications of stack. Queues: Definition – operations – Priority queues – Dequeues – Applications of queue. Linked List: Singly Linked List, Doubly Linked List, Circular Linked List, linked stacks, Linked queues, Applications of Linked List – Dynamic storage management – Generalized list. | 15 | ||
| III | Trees: Binary tree, Terminology, Representation, Traversals, Applications – Binary search tree – AVL tree. B Trees: B Tree indexing, operations on a B Tree, Lower and upper bounds of a B Tree – B + Tree Indexing – Trie Tree Indexing. | 15 | ||
| IV | Graph: Terminology, Representation, Traversals – Applications – spanning trees, shortest path and Transitive closure, Topological sort. Sets: Representation – Operations on sets –
Applications. Files: queries – Sequential organization – Index techniques. External sorting. |
15 | ||
| Total Contact Hours | 60 | |||
| Suggested Evaluation Methods | ||||
| Internal Assessment: 30 | End Term Examination: 70 | |||
| ➢ Theory | 30 | ➢ Theory | 70 | |
| • Class Participation: | 5 | Written Examination | ||
| • Seminar/presentation/assignment/quiz/class test etc.: | 10 | |||
| • Mid-Term Exam: | 15 | |||
| Part C-Learning Resources | ||||
| Reference Books:
1) Horowitz, E., & Sahni, S. (2004). Fundamentals of Data Structures. Galgotia Book Source Pvt. Ltd. 2) Samanta, D. (2012). Classic Data Structures (2nd ed.). Prentice-Hall of India Pvt. Ltd., India. 3) Kruse, R., Tondo, C. L., & Leung, B. (2007). Data Structures and Program Design in C (2nd ed.). Prentice-Hall of India Pvt. Ltd. 4) Weiss, M. A. (2006). Data Structures and Algorithm Analysis in C (2nd ed.). Pearson Education. |
||||
