This document describes a course on data structures using C. It outlines the course code, title, credits, contact hours and assessments. It then lists the course outcomes and covers content including arrays, linked lists, stacks, queues and trees. It provides textbook and reference recommendations.
This document describes a course on data structures using C. It outlines the course code, title, credits, contact hours and assessments. It then lists the course outcomes and covers content including arrays, linked lists, stacks, queues and trees. It provides textbook and reference recommendations.
This document describes a course on data structures using C. It outlines the course code, title, credits, contact hours and assessments. It then lists the course outcomes and covers content including arrays, linked lists, stacks, queues and trees. It provides textbook and reference recommendations.
This document describes a course on data structures using C. It outlines the course code, title, credits, contact hours and assessments. It then lists the course outcomes and covers content including arrays, linked lists, stacks, queues and trees. It provides textbook and reference recommendations.
Course Code: CAC04 Course Title: Data Structures using C
Course Credits: 03 Hours/Week: 03
Total Contact Hours: 42 Formative Assessment Marks: 30 Exam Marks: 70 Exam Duration: 03 Hours Course Outcomes (COs): After completing this course satisfactorily, a student will be able to:
• Describe how arrays, records, linked structures, stacks, queues, trees, and graphs are represented in memory and used by algorithms • Describe common applications for arrays, records, linked structures, stacks, queues, trees, and graphs • Write programs that use arrays, records, linked structures, stacks, queues, trees, and graphs • Demonstrate different methods for traversing trees • Compare alternative implementations of data structures with respect to performance • Describe the concept of recursion, give examples of its use • Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing
Course Content Content Hours Unit - 1 Introduction to data structures: Definition; Types of data structures - Primitive & 8 Non-primitive, Linear and Non-linear; Operations on data structures. Dynamic memory allocation: Static & Dynamic memory allocation; Memory allocation and de- allocation functions - malloc, calloc, realloc and free. Algorithm Specification, Performance Analysis, Performance Measurement Recursion: Definition; Types of recursions; Recursion Technique Examples - GCD, Binomial coe0fficient nCr, Towers of Hanoi; Comparison between iterative and recursive functions. 10 hours Unit - 2 Arrays: Basic Concepts – Definition, Declaration, Initialisation, Operations on arrays; Types of 10 arrays; (ADT); Representation of Linear Arrays in memory; Traversing linear arrays; Inserting and deleting elements; Sorting – Selection sort, Bubble sort, Quick sort, Merge sort, Insertion sort; Searching - Sequential Search, Binary search; Iterative and Recursive searching; Multidimensional arrays; Representation of multidimensional arrays; Sparse matrices.
Unit - 3
Linked list: Basic Concepts – Definition and Representation of linked list, Types of linked lists - 8 Singly linked list, Doubly liked list, Header liked list, Circular linked list; Representation of Linked list in Memory; Operations on Singly linked lists – Traversing, Searching, Insertion, Deletion; Memory allocation; Garbage collection, Unit - 4 Stacks: Basic Concepts – Definition and Representation of stacks; Operations on stacks; 8 Applications of stacks; Infix, postfix and prefix notations; Conversion from infix to postfix using stack; Evaluation of postfix expression using stack; Application of stack in function calls. Queues: Basic Concepts – Definition and Representation of queues; Types of queues - Simple queues, Circular queues, Double ended queues, Priority queues; Operations on Simple queues; Unit - 5
Trees: Definition; Tree terminologies –node, root node, parent node, ancestors of a node, 8 siblings, terminal & non-terminal nodes, degree of a node, level, edge, path, depth; Binary tree: Type of binary trees - strict binary tree, complete binary tree, binary search tree and heap tree; Array representation of binary tree. Traversal of binary tree; preorder, inorder and postorder traversal; Graphs - Introduction
Text Books 1. Ellis Horowitz and Sartaj Sahni: Fundamentals of Data Structures References
1. Tanenbaum: Data structures using C (Pearson Education)
2. Kamathane: Introduction to Data structures (Pearson Education) 3. Y. Kanitkar: Data Structures Using C (BPB) 4. Kottur: Data Structure Using C 5. Padma Reddy: Data Structure Using C 6. Sudipa Mukherjee: Data Structures using C – 1000 Problems and Solutions (McGraw Hill Education, 2007)) Course Code: CAC04P Course Title: Data Structures Lab Course Credits: 02 Hours/Week: 04 Total Contact Hours: 52 Formative Assessment Marks: 10 Exam Marks: 40 Exam Duration: 03 Hours Programming Lab Part A: 1. Program to find GCD using recursive function 2. Program to display Pascal Triangle using binomial function 3. Program to generate n Fibonacci numbers using recursive function. 4. Program to implement Towers of Hanoi. 5. Program to implement dynamic array, find smallest and largest element of the array. 6. Program to create two files to store even and odd numbers. 7. Program to create a file to store student records In a file ****** sort the records 8. Program to read the names of cities and arrange them alphabetically. 9. Program to sort the given list using selection sort technique. 10. Program to sort the given list using bubble sort technique. Part B: 1. Program to sort the given list using insertion sort technique. Replace technique with algorithm 2. Program to sort the given list using quick sort technique. 3. Program to sort the given list using merge sort technique. 4. Program to search an element using linear search technique. 5. Program to search an element using recursive binary search technique. 6. Program to implement Stack. 7. Program to convert an infix expression to postfix. 8. Program to implement simple queue. 9. Program to implement linear linked list. 10. Program to display traversal of a tree. 11. Doubly linked list, circular 12. Graphs programs
