Data Structures

Course Objectives :

1. To introduce basics of Data structures (Arrays, strings, linked list etc.)
2. To understand the concepts of Stacks, Queues and Trees, related operations and their implementation
3. To understand sets, heaps and graphs
4. To introduce various Sorting and searching Algorithms

Course Outcomes (CO)

• CO 1 To be able to understand difference between structured data and data structure
• CO 2 To be able to create common basic data structures and trees
• CO 3 To have a knowledge of sets, heaps and graphs
• CO 4 To have basic knowledge of sorting and searching algorithms

UNIT – I

Overview of data structure, Basics of Algorithm Analysis including Running Time Calculations,  Abstract Data Types, Arrays, Arrays and Pointers, Multidimensional Array, String processing, General Lists and List ADT, List manipulations, Single, double and circular lists. Stacks and Stack ADT, Stack Manipulation, Prefix, infix and postfix expressions, recursion. Queues and Queue ADT, Queue manipulation.

UNIT – II

Sparse Matrix Representation (Array and Link List representation) and arithmetic (addition, subtraction and multiplication), polynomials and polynomial arithmetic. Trees, Properties of Trees, Binary trees, Binary Tree traversal, Tree manipulation algorithms, Expression trees and their usage, binary search trees, AVL Trees, Heaps and their implementation, Priority Queues, B-Trees, B* Tree, B+ Tree

UNIT – III

Sorting concept, order, stability, Selection sorts (straight, heap), insertion sort (Straight Insertion, Shell sort), Exchange Sort (Bubble, quicksort), Merge sort (External Sorting) (Natural merge, balanced merge and polyphase merge). Searching – List search, sequential search, binary search, hashing methods, collision resolution in hashing.

UNIT – IV

Disjoint sets representation, union find algorithm, Graphs, Graph representation, Graph Traversals and their implementations (BFS and DFS). Minimum Spanning Tree algorithms, Shortest Path Algorithms 

Textbook(s):

1. Richard Gilberg , Behrouz A. Forouzan, “Data Structures: A Pseudocode Approach with C, 2nd Edition, Cengage Learning, Oct 2004
2. E. Horowitz, S. Sahni, S. Anderson-Freed, "Fundamentals of Data Structures in C", 2nd Edition, Silicon Press (US), 2007.

References:

1. Mark Allen Weiss, “Data Structres and Algorithm Analysis in C”, 2nd Edition, Pearson, September, 1996
2. Robert Kruse, “Data Structures and Program Design in C”, 2nd Edition, Pearson, November, 1990
3. Seymour Lipschutz, “Data Structures with C (Schaum's Outline Series)”, McGrawhill, 2017
4. A. M. Tenenbaum, “Data structures using C”. Pearson Education, India, 1st Edition 2003.
5. Weiss M.A., “Data structures and algorithm analysis in C++”, Pearson Education, 2014.