data structures and applications

Semester : III

Course Code : 18CS32

CIE Marks : 40 SEE Marks : 60

DATA STRUCTURES AND APPLICATIONS
18CS32

SYLLABUS

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.
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
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 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. Applications of Linked lists – Polynomials, Sparse matrix representation. Programming Examples
Textbook 1: Chapter 4: 4.1 – 4.6, 4.8,
Textbook 2: Chapter 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 Examples
Textbook 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

textbooks recommended by vtu

Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures in C, 2nd Ed, Universities Press,
2014
Seymour Lipschutz, Data Structures Schaum’s Outlines, Revised 1st Ed, McGraw Hill, 2014.

reference recommended by vtu

Gilberg & Forouzan, Data Structures: A Pseudo-code approach with C, 2nd Ed, Cengage
Learning,2014.
Reema Thareja, Data Structures using C, 3rd Ed, Oxford press, 2012.
Jean-Paul Tremblay & Paul G. Sorenson, An Introduction to Data Structures with Applications,2nd Ed, McGraw Hill, 2013
A M Tenenbaum, Data Structures using C, PHI, 1989
Robert Kruse, Data Structures and Program Design in C, 2nd Ed, PHI, 1996