|Data Structure||Learning Schedule|
|Pre-requisites: C Programming||3||0||0||3|
The purpose of this course is to provide basic concepts of data structures a nd algorithms. The main goal of the course is to teach the students how to select and design data structures for algorithms that are appropriate for problems that they might encounter. This course is also to learn abstracts data types, graphs, tree and its traversal, and different searching and sorting techniques. This also provides knowledge of Hashing techniques and Garbage Collection and Compaction.
The objective of this course is to:
1.Introduce the fundamentals and abstract concepts of Data Structures.
2.Introduce searching, sorting techniques
3.Learn how concepts of data structures are useful in problem solving.
At the end of the course student will be able to
1.Use and implement appropriate data structure for the required problems using a programming language such as C/C++.
2.Analyze step by step and develop algorithms to solve real world problems.
3.Implementing various data structures viz. Stacks, Queues, Linked Lists, Trees and Graphs.
4.Understand various searching & sorting techniques.
Unit I: Introduction: Basic Terminology
Elementary Data Organization, Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big-Oh, Time-Space trade-off. Abstract Data Types (ADT)Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays : Row Major Order, and Column Major Order, Application of arrays, Sparse Matrices and their representations. Linked lists: Array Implementation and Dynamic Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition, Generalized Linked List.
Unit II: Stacks and Queues: Abstract Data Type
Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Recursion, Tower of Hanoi Problem, Simulating Recursion, Principles of recursion, Tail recursion, Removal of recursion Queues, Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Dequeue and Priority Queue.
Unit III: Trees: Basic terminology
Binary Trees, Binary Tree Representation: Array Representation and Dynamic Representation, Complete Binary Tree, Algebraic Expressions, Extended Binary Trees, Array and Linked Representation of Binary trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Threaded Binary trees, Traversing Threaded Binary trees, Huffman algorithm.
Unit IV: Graphs
Terminology, Sequential and linked Representations of Graphs: Adjacency Matrices, Adjacency List, Adjacency Multi list, Graph Traversal : Depth First Search and Breadth First Search, Connected Component, Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm. Transitive Closure and Shortest Path algorithm: Warshal Algorithm and Dijikstra Algorithm, Introduction to Activity Networks.
Unit V: Searching
Sequential search, Binary Search, Comparison and Analysis Internal Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Two Way Merge Sort, Heap Sort, Radix Sort, Practical consideration for Internal Sorting. Search Trees: Binary Search Trees(BST), Insertion and Deletion in BST, Complexity of Search Algorithm, AVL trees, Introduction to m-way Search Trees, B Trees & B+ Trees Hashing: Hash Function, Collision Resolution Strategies Storage Management: Garbage Collection and Compaction.
- Fundamentals of Data Structures – Horowitz and Sahani, Galgotia Publication
- Data Structures Using C and C++ – Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein, PHI Publications
- An Introduction to Data Structures with applications – Jean Paul Trembley and Paul G. Sorenson, McGraw Hill Publications
- Data Structures and Program Design in C – R. Kruse etal, , Pearson Education
- Data Structures – Lipschutz, Schaum’s Outline Series, TMH