This document outlines a course on data structures and applications. The course aims to explain fundamental data structures, illustrate linear data structures like stacks, queues, lists, trees and graphs, and demonstrate sorting and searching algorithms. The course is divided into 5 modules covering topics such as arrays, strings, linked lists, trees, graphs, sorting, searching and hashing. Students will learn to use different data structures and algorithms to solve problems and will implement various data structures in a programming language. The assessment includes a 3 hour exam with 10 questions, 5 of which students must answer by selecting 1 question from each module.
This document outlines a course on data structures and applications. The course aims to explain fundamental data structures, illustrate linear data structures like stacks, queues, lists, trees and graphs, and demonstrate sorting and searching algorithms. The course is divided into 5 modules covering topics such as arrays, strings, linked lists, trees, graphs, sorting, searching and hashing. Students will learn to use different data structures and algorithms to solve problems and will implement various data structures in a programming language. The assessment includes a 3 hour exam with 10 questions, 5 of which students must answer by selecting 1 question from each module.
This document outlines a course on data structures and applications. The course aims to explain fundamental data structures, illustrate linear data structures like stacks, queues, lists, trees and graphs, and demonstrate sorting and searching algorithms. The course is divided into 5 modules covering topics such as arrays, strings, linked lists, trees, graphs, sorting, searching and hashing. Students will learn to use different data structures and algorithms to solve problems and will implement various data structures in a programming language. The assessment includes a 3 hour exam with 10 questions, 5 of which students must answer by selecting 1 question from each module.
This document outlines a course on data structures and applications. The course aims to explain fundamental data structures, illustrate linear data structures like stacks, queues, lists, trees and graphs, and demonstrate sorting and searching algorithms. The course is divided into 5 modules covering topics such as arrays, strings, linked lists, trees, graphs, sorting, searching and hashing. Students will learn to use different data structures and algorithms to solve problems and will implement various data structures in a programming language. The assessment includes a 3 hour exam with 10 questions, 5 of which students must answer by selecting 1 question from each module.
SEMESTER – III Course Code 18CS32 CIE Marks 40 Number of Contact Hours/Week 3:2:0 SEE Marks 60 Total Number of Contact Hours 50 Exam Hours 03 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 Contact Hours Introduction: Data Structures, Classifications (Primitive & Non Primitive), Data structure 10 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 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 RBT: L1, L2, L3 Module 2 Stacks: Definition, Stack Operations, Array Representation of Stacks, Stacks using Dynamic 10 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 RBT: L1, L2, L3 Module 3 Linked Lists: Definition, Representation of linked lists in Memory, Memory allocation; 10 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: Ch apter 4: 4.1 – 4.6, 4.8, Textbook 2: Ch apter 5: 5.1 – 5.10, RBT: L1, L2, L3 Module 4 Trees: Terminology, Binary Trees, Properties of Binary trees, Array and linked 10 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 RBT: L1, L2, L3 Module 5 Graphs: Definitions, Terminologies, Matrix and Adjacency List Representation Of Graphs, 10 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 RBT: L1, L2, L3 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. 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,2014. 2. 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.