DATA STRUCTURES AND APPLICATIONS( 17CS33) Syllabus

DATA STRUCTURES AND APPLICATIONS

[As per Choice Based Credit System (CBCS) scheme]

(Effective from the academic year 2017 -2018)

SEMESTER – III

Subject Code 17CS33	IA Marks 40
Number of Lecture Hours/Week 04	Exam Marks 60 Total
Number of Lecture Hours 50	Exam Hours 03
CREDITS – 04
Module 1		Teaching Hours
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. Text 1: Ch 1: 1.2, Ch2: 2.2 -2.7 Text 2: Ch 1: 1.1 -1.4, Ch 3: 3.1-3.3,3.5,3.7, Ch 4: 4.1-4.9,4.14 Ref 3: Ch 1: 1.4		10 Hours
Module 2
Stacks and Queues 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. Text 1: Ch3: 3.1 -3.7 Text 2: Ch6: 6.1 -6.3, 6.5, 6.7-6.10, 6.12, 6.13		10 Hours
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 Text 1: Ch4: 4.1 -4.8 except 4.6 Text 2: Ch5: 5.1 – 5.10		10 Hours
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 Text 1: Ch5: 5.1 –5.5, 5.7 Text 2: Ch7: 7.1 – 7.9			10 Hours
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 Text 1: Ch6: 6.1 –6.2, Ch 7:7.2, Ch 8:8.1-8.3 Text 2: Ch8: 8.1 – 8.7, Ch 9:9.1-9.3,9.7,9.9 Reference 2: Ch 16: 16.1 - 16.7			10 Hours
Course outcomes: After studying this course, students will be able to:
• Explain different types of data structures, operations and algorithms • Apply searching and sorting operations on files • Make use of stack, Queue, Lists, Trees and Graphs in problem solving. • Develop all data structures in a high-level language for problem solving.
Question paper pattern: The question paper will have ten questions. There will be 2 questions from each module. Each question will have questions covering all the topics under a module. The students will have to answer 5 full questions, selecting one full question from each module.
Text Books: 1. Fundamentals of Data Structures in C - Ellis Horowitz and Sartaj Sahni, 2nd edition, Universities Press,2014 2. Data Structures - Seymour Lipschutz, Schaum's Outlines, Revised 1st edition, McGraw Hill, 2014
Reference Books: 1. Data Structures: A Pseudo-code approach with C –Gilberg & Forouzan, 2nd edition, Cengage Learning,2014 2. Data Structures using C, , Reema Thareja, 3rd edition Oxford press, 2012 3. An Introduction to Data Structures with Applications- Jean-Paul Tremblay & Paul G. Sorenson, 2nd Edition, McGraw Hill, 2013 4. Data Structures using C - A M Tenenbaum, PHI, 1989 5. Data Structures and Program Design in C - Robert Kruse, 2nd edition, PHI, 1996