Introduction:
Data Structures, Classifications (Primitive & Non-Primitive), Data structure operations (Traversing, inserting, deleting, searching, and sorting). Review of Arrays. Structures: Array of structures Self-Referential Structures. Dynamic Memory Allocation Functions. Representation of Linear Arrays in Memory, dynamically allocated arrays and Multidimensional Arrays. Demonstration of representation of Polynomials and Sparse Matrices with arrays.
Laboratory Component:
1. Design, Develop and Implement a menu driven Program in C for the following Array Operations
a. Creating an Array of N Integer Elements
b. Display of Array Elements with Suitable Headings
c. Exit.
Support the program with functions for each of the above operations.
2. Design, Develop and Implement a menu driven Program in C for the following Array operations
a. Inserting an Element (ELEM) at a given valid Position (POS)
b. Deleting an Element at a given valid Position POS)
c. Display of Array Elements
d. Exit.
Support the program with functions for each of the above operations.
Stacks:
Definition, Stack Operations, Array Representation of Stacks, Stacks using Dynamic Arrays. Different representation of expression. Stack Applications: Infix to postfix conversion, Infix to prefix conversion, evaluation of postfix expression, recursion.
Queues:
Definition, Array Representation of Queues, Queue Operations, Circular Queues, Queues and Circular queues using Dynamic arrays, Dequeues, Priority Queues.
Laboratory Component:
1. Design, Develop and Implement a menu driven Program in C for the following operations on STACK of Integers (Array Implementation of Stack with maximum size MAX)
a. Push an Element on to Stack
b. Pop an Element from Stack
c. Demonstrate Overflow and Underflow situations on Stack
d. Display the status of Stack
e. Exit
Support the program with appropriate functions for each of the above operations
2. Design, Develop and Implement a Program in C for the following Stack Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^
b. Solving Tower of Hanoi problem with n disks
Linked Lists:
Definition, classification of linked lists. Representation of different types of linked lists in Memory, Traversing, Insertion, Deletion, Searching, Sorting, and Concatenation Operations on Singly linked list, Doubly Linked lists, Circular linked lists, and header linked lists. Linked Stacks and Queues. Applications of Linked lists – Polynomials, Sparse matrix representation. Programming Examples.
Laboratory Component:
1. Singly Linked List (SLL) of Integer Data
a. Create a SLL stack of N integer.
b. Display of SLL
c. Linear search. Create a SLL queue of N Students Data Concatenation of two SLL of integers.
2. Design, Develop and Implement a menu driven Program in C for the following operationson Doubly Linked List (DLL) of Professor Data with the fields: ID, Name, Branch, Area of specialization a. Create a DLL stack of N Professor’s Data.
b. Create a DLL queue of N Professor’s Data
Display the status of DLL and count the number of nodes in it.
Trees 1:
Terminologies, Binary Trees, Properties of Binary trees, Array and linked Representation of Binary Trees, Binary Tree Traversals - Inorder, postorder, preorder; Threaded binary trees, Binary Search Trees – Definition, Insertion, Deletion, Traversal, and Searching operation on Binary search tree. Application of Trees-Evaluation of Expression.
Laboratory Component:
1. Given an array of elements, construct a complete binary tree from this array in level order fashion. That is, elements from left in the array will be filled in the tree level wise starting from level 0. Ex: Input : arr[] = {1, 2, 3, 4, 5, 6} Output : Root of the following tree
1
/ \\
2 3
/ \\ / \\
4 5 6
2. Design, Develop and Implement a menu driven Program in C for the following operations on Binary Search Tree (BST) of Integers
a. Create a BST of N Integers
b. Traverse the BST in Inorder, Preorder and Post Order
Trees 2:
AVL tree, Red-black tree, Splay tree, B-tree.
Graphs:
Definitions, Terminologies, Matrix and Adjacency List Representation of Graphs, Traversal methods: Breadth First Search and Depth FirstSearch.
Hashing:
Hash Table organizations, Hashing Functions, Static and Dynamic Hashing.
Laboratory Component:
1. Design, Develop and implement a program in C for the following operations on Graph (G) of cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a diagraph using DFS/BFS method.
2. Design and develop a program in C that uses Hash Function H:K->L as H(K)=K mod m(reminder method) and implement hashing technique to map a given key K to the address space L. Resolve the collision (if any) using linear probing
Course Outcomes (Course Skill Set)
At the end of the course the student will be able to:
CO 1. Identify different data structures and their applications.
CO 2. Apply stack and queues in solving problems.
CO 3. Demonstrate applications of linked list.
CO 4. Explore the applications of trees and graphs to model and solve the real-world problem.
CO 5. Make use of Hashing techniques and resolve collisions during mapping of key value pairs
Assessment Details (both CIE and SEE)
Continuous Internal Evaluation:
Three Unit Tests each of 20 Marks (duration 01 hour)
1. First test at the end of 5th week of the semester
2. Second test at the end of the 10th week of the semester
3. Third test at the end of the 15th week of the semester
Two assignments each of 10 Marks
4. First assignment at the end of 4th week of the semester
5. Second assignment at the end of 9th week of the semester
Practical Sessions need to be assessed by appropriate rubrics and viva-voce method. This will contribute to 20 marks.
The sum of three tests, two assignments, and practical sessions will be out of 100 marks and will be scaled down to 50 marks (to have a less stressed CIE, the portion of the syllabus should not be common /repeated for any of the methods of the CIE. Each method of CIE should have a different syllabus portion of the course).
CIE methods /question paper has to be designed to attain the different levels of Bloom’s taxonomy as per the outcome defined for the course.
Semester End Examination:
Theory SEE will be conducted by University as per the scheduled timetable, with common question papers for the subject (duration 03 hours)
1. The question paper will have ten questions. Each question is set for 20 marks. Marks scored shall be proportionally reduced to 50 Marks
2. There will be 2 questions from each module. Each of the two questions under a module (with a maximum of 3 sub-questions), should have a mix of topics under that module.
The students have to answer 5 full questions, selecting one full question from each module.
Suggested Learning Resources:
Textbooks:
1. Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures in C, 2nd Ed, Universities Press, 2014.
2. Seymour Lipschutz, Data Structures Schaum's Outlines, Revised 1st Ed, McGraw Hill, 2014.
3. Reema Thareja, Data Structures using C, 3rd Ed, Oxford press, 2012.
Reference Books:
1. Gilberg and Forouzan, Data Structures: A Pseudo-code approach with C, 2nd Ed, Cengage Learning,2014.
2. Jean-Paul Tremblay & Paul G. Sorenson, An Introduction to Data Structures with Applications,2nd Ed, McGraw Hill, 2013
3. A M Tenenbaum, Data Structures using C, PHI, 1989
4. Robert Kruse, Data Structures and Program Design in C, 2nd Ed, PHI, 1996.