##
__DATA STRUCTURES AND APPLICATION __

####
Subject Code:18CS32 CIE Marks:40

SEE Marks:60

Number of Contact Hours/Week:3:2:0 Total Number of Contact Hours:50 Exam Hours:3 Hrs

CREDITS –4

####
__Course Learning Objectives: __This course (18CS32) will enable students to:

• Explain fundamentals of data structures and their applications essential for programming/problem solving• Illustrate linear representation of data structures: Stack, Queues, Lists, Trees and Graphs

• Demonstrate sorting and searching algorithms

• Find suitable data structure during application development/Problem Solving.

####

Module 1

Introduction: Data Structures, Classifications (Primitive & Non Primitive), Data structure Operations, Review of Arrays, Structures, Self-Referential Structures, and Unions. Pointers and Dynamic Memory Allocation Functions. Representation of Linear Arrays in Memory, Dynamically allocated arrays.Module 1

Array Operations: Traversing, inserting, deleting, searching, and sorting. Multidimensional Arrays, Polynomials and Sparse Matrices.

Strings: Basic Terminology, Storing, Operations and Pattern Matching algorithms. Programming Examples.

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, Ch apter 4: 4.1 - 4.9, 4.14 Reference 3: Chapter 1: 1.4

__Module 2__

Stacks: Definition, Stack Operations, Array Representation of Stacks, Stacks using Dynamic Arrays, Stack Applications: Polish notation, Infix to postfix conversion, evaluation of postfix expression.Recursion - Factorial, GCD, Fibonacci Sequence, Tower of Hanoi, Ackerman's function. Queues: Definition, Array Representation, Queue Operations, Circular Queues, Circular queues using Dynamic arrays, Dequeues, Priority Queues, A Mazing Problem. Multiple Stacks and Queues. Programming Examples.

Textbook 1: Chapter 3: 3.1 -3.7

Textbook 2: Chapter 6: 6.1 -6.3, 6.5, 6.7-6.10, 6.12, 6.13

__Module 3__

Linked Lists: Definition, Representation of linked lists in Memory, Memory allocation; Garbage Collection. Linked list operations: Traversing, Searching, Insertion, and Deletion. Doubly Linked lists, Circular linked lists, and header linked lists. Linked Stacks and Queues. 10Applications of Linked lists – Polynomials, Sparse matrix representation. Programming Examples

Textbook 1: Ch apter 4: 4.1 – 4.6, 4.8 Textbook 2: Ch apter 5: 5.1 – 5.10

__Module 4__

Trees: Terminology, Binary Trees, Properties of Binary trees, Array and linked Representation of Binary Trees, Binary Tree Traversals - Inorder, postorder, preorder; Additional Binary tree operations. Threaded binary trees, Binary Search Trees – Definition, Insertion, Deletion, Traversal, Searching, Application of Trees-Evaluation of Expression, Programming ExamplesTextbook 1: Chapter 5: 5.1 –5.5, 5.7 Textbook 2: Chapter 7: 7.1 – 7.9

__Module 5__

Graphs: Definitions, Terminologies, Matrix and Adjacency List Representation Of Graphs, Elementary Graph operations, Traversal methods: Breadth First Search and Depth First Search.Sorting and Searching: Insertion Sort, Radix sort, Address Calculation Sort. Hashing: Hash Table organizations, Hashing Functions, Static and Dynamic Hashing.

Files and Their Organization: Data Hierarchy, File Attributes, Text Files and Binary Files, Basic File Operations, File Organizations and Indexing

Textbook 1: Chapter 6 : 6.1 –6.2, Chapter 7:7.2, Chapter 8 : 8.1-8.3 Textbook 2: Chapter 8 : 8.1 – 8.7, Chapter 9 : 9.1-9.3, 9.7, 9.9 Reference 2: Chapter 16 : 16.1 - 16.7

__Course Outcomes: __The student will be able to :

• Use different types of data structures, operations and algorithms• Apply searching and sorting operations on files

• Use stack, Queue, Lists, Trees and Graphs in problem solving

• Implement all data structures in a high-level language for problem solving.

####
__Question Paper Pattern:__

• The question paper will have ten questions.• Each full Question consisting of 20 marks

• There will be 2 full questions (with a maximum of four sub questions) from each module.

• Each full question will have sub questions covering all the topics under a module.

• The students will have to answer 5 full questions, selecting one full question from each module.

__Question Bank-1__

__Question Bank-__2

__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.

__Reference Books:__

1. Gilberg & Forouzan, Data Structures: A Pseudo-code approach with C, 2nd Ed, Cengage Learning,20142. Reema Thareja, Data Structures using C, 3rd Ed, Oxford press, 2012.

3. Jean-Paul Tremblay & Paul G. Sorenson, An Introduction to Data Structures with Applications, 2nd Ed, McGraw Hill, 2013

4. A M Tenenbaum, Data Structures using C, PHI, 1989

5. Robert Kruse, Data Structures and Program Design in C, 2nd Ed, PHI, 1996.