DATA STRUCTURES AND APPLICATIONS
Course Code: 21CS32
CIE Marks 50
Teaching Hours/Week (L:T:P: S) 3:0:2:0
SEE Marks 50
Total Hours of Pedagogy 40 T + 20 P
Total Marks 100
Credits 04
Exam Hours 03
Module-1
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. Textbook 1: Chapter 1: 1.2, Chapter 2: 2.2 - 2.7, Text Textbook 2: Chapter 1: 1.1 - 1.4, Chapter 3: 3.1 - 3.3, 3.5, 3.7, Chapter 4: 4.1 - 4.9, 4.14 Textbook 3: Chapter 1: 1.3
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.
Module-2
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. Textbook 1: Chapter 3: 3.1 -3.4, 3.6 Textbook 2: Chapter 6: 6.1 -6.4, 6.5, 6.7-6.13
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
Module-3
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.Textbook 1: Chapter 4: 4.1 – 4.4, 4.5.2, 4.7, 4.8, Textbook 2: Chapter 5: 5.1 – 5.9
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.
Module-4
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. Textbook 1: Chapter 5: 5.1 –5.5, 5.7; Textbook 2: Chapter 7: 7.1 – 7.9
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
Module-5
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. Textbook 1: Chapter 10:10.2, 10.3, 10.4, Textbook 2:7.10 – 7.12, 7.15 Chapter 11: 11.2, Textbook 1: Chapter 6 : 6.1–6.2, Chapter 8 : 8.1-8.3, Textbook 2: 8.1 – 8.3, 8.5, 8.7 Textbook 3: Chapter 15:15.1, 15.2,15.3, 15.4,15.5 and 15.7
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.
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.
Weblinks and Video Lectures (e-Resources):
1. http://elearning.vtu.ac.in/econtent/courses/video/CSE/06CS35.html
2. https://nptel.ac.in/courses/106/105/106105171/
3. http://www.nptelvideos.in/2012/11/data-structures-and-algorithms.html
Activity Based Learning (Suggested Activities in Class)/ Practical Based learning
Real world problem solving using group discussion.
Back/Forward stacks on browsers.
Undo/Redo stacks in Excel or Word.
Linked list representation of real-world queues -Music player, image viewer
){kind=link}
0 Comments