Syllabus (COMPUTER APPLICATION)

Course Type: MAJ-3

Semester: 3

Course Code: BBCAMAJ03C

Course Title: Data Structure

(L-P-Tu): 4-2-0

Credit: 6

Practical/Theory: Combined

Course Objective: Course Objective: Introduce the fundamental concepts and principles of data structures and their implementation using the C programming language. Develop students' ability to analyze, design, and implement efficient data structures to solve complex problems. Familiarize students with various data structures, such as arrays, linked lists, stacks, queues, trees, and graphs, and their associated algorithms. Provide hands-on experience in utilizing data structures to improve program efficiency, memory utilization, and algorithmic performance.

Learning Outcome: Course Outcomes: Demonstrate a thorough understanding of different data structures and their characteristics, including arrays, linked lists, stacks, queues, trees, and graphs. Apply appropriate data structures and algorithms to solve real-world problems efficiently. Implement and manipulate various data structures using programming language. Analyze the time and space complexity of algorithms and evaluate their efficiency in different scenarios, allowing for optimal solution selection and performance optimization.

Syllabus:

Unit I: Theory Credit: 4 (L 60)

Introduction: Introduction to Data Structure, Types, Abstract Datatypes. [L 2]

Arrays and Structure: Single and Multi-Dimensional Arrays, Address translation, Sparse Matrices (Array and Linked Representation), Basics of Structure, Self-Referential Structure. [L 5]

Linked Lists: Singly, Doubly and Circular Linked Lists. [L 10]

Stacks: Implementing Stack (Array and Linked Representation), Application of Stack, Prefix, Infix and Postfix Expressions, Utility and Conversion of these Expressions from one to another, Limitations of Stack. [L 6]

Queues: Implementing Queue (Array and Linked Representation), Circular Queues, Priority Queues, Applications of Queue, Limitations of Queue. [L 5]

Recursion: Developing Recursive Definitions of Simple Problems and their Implementations, Tracing Recursion, Analysing Recursion, Towers of Hanoi. [L 4]

Searching and Sorting: Linear Search, Binary Search, Comparison of Linear Search and Binary Search, Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Shell Sort, Comparison of Sorting Techniques. [L 10]

Graphs and Trees: Introduction to Trees, Binary Trees, Tree Traversals, Binary Search Trees, Various operations on Binary Search Trees, Height-Balanced Trees, Various Operations on Adelson-Velski and Landis (AVL) Trees, Introduction to Graphs and their representation, Graph Terminology, Graph Traversal- Breadth First Search and Depth First Search. [L 15]

Hashing: Limitations of Direct Address, Introduction to Hashing Table, Chaining, Open Addressing (Linear Probing, Quadratic Probing, Double Hashing). [L 3]

Unit II: Data Structure Lab (Using C) Credit: 2 (L 60)

Practical Part of Data Structure will be based upon the modules covered in the theory part.

Reading References:

1. A.M. Tanenbaum, Data Structure using C, PHI.
2. Data Structures and Algorithms using C, Khanna Publishing.
3. Reema Thareja, Data Structures Using C, Oxford.
4. Jean-Paul Tremblay, Paul G. Sorenson, An Introduction to Data Structures with Applications, Tata McGraw Hill.
5. Horowitz, Sahni,Galgotia, Fundamentals of data structure in C, Pub. Universities press.