May 2022

DATA STRUCTURES

Course Objectives:

The objective of the course is to

Introduce the fundamental concept of data structures and abstract data types
Emphasize the importance of data structures in developing and implementing efficient algorithms
Describe how arrays, records, linked structures, stacks, queues, trees, and graphs are represented in memory and used by algorithms

Course Outcomes:

After completing this course a student will be able to:

Summarize the properties, interfaces, and behaviors of basic abstract data types
Discuss the computational efficiency of the principal algorithms for sorting & searching
Use arrays, records, linked structures, stacks, queues, trees, and Graphs in writing programs
Demonstrate different methods for traversing tree.

UNIT I

Data Structures - Definition, Classification of Data Structures, Operations on Data Structures, Abstract Data Type (ADT), Preliminaries of algorithms. Time and Space complexity. Searching - Linear search, Binary search, Fibonacci search. Sorting- Insertion sort, Selection sort, Exchange (Bubble sort, quick sort), distribution (radix sort), merging (Merge sort) algorithms.

UNIT II

Linked List: Introduction, Single linked list, Representation of Linked list in memory, Operations on Single Linked list-Insertion, Deletion, Search and Traversal ,Reversing Single Linked list, Applications on Single Linked list- Polynomial Expression Representation ,Addition and Multiplication, Sparse Matrix Representation using Linked List, Advantages and Disadvantages of Single Linked list, Double Linked list-Insertion, Deletion, Circular Linked list-Insertion, Deletion.

UNIT III

Queues: Introduction to Queues, Representation of Queues-using Arrays and using Linked list, Implementation of Queues-using Arrays and using Linked list, Application of Queues Circular Queues, Deques, Priority Queues, Multiple Queues.

Stacks: Introduction to Stacks, Array Representation of Stacks, Operations on Stacks, Linked list Representation of Stacks, Operations on Linked Stack, Applications-Reversing list, Factorial Calculation, Infix to Postfix Conversion, Evaluating Postfix Expressions.

UNIT IV

Trees: Basic Terminology in Trees, Binary Trees-Properties, Representation of Binary Trees using Arrays and Linked lists. Binary Search Trees-Basic Concepts,

BST Operations:

Insertion, Deletion, Tree Traversals, Applications-Expression Trees, Heap Sort, Balanced Binary Trees-AVL Trees, Insertion, Deletion and Rotations.

UNIT V

Graphs: Basic Concepts, Representations of Graphs-Adjacency Matrix and using Linked list, Graph Traversals (BFT & DFT), Applications-Minimum Spanning Tree Using Prims & Kruskals Algorithm, Dijkstra’s shortest path, Transitive closure, Warshall’s Algorithm.

Text Books:

Data Structures Using C. 2ndEdition.Reema Thareja, Oxford.
Data Structures and algorithm analysis in C, 2nded, Mark Allen Weiss.

ReferenceBooks:
Fundamentals of Data Structures in C, 2nd Edition, Horowitz, Sahni, Universities Press.
Data Structures: A PseudoCode Approach, 2/e, Richard F.Gilberg, Behrouz A.Forouzon, Cengage.
Data Structures with C, Seymour Lipschutz TMH
e-Resources:

http://algs4.cs.princeton.edu/home/
https://faculty.washington.edu/jstraub/dsa/Master_2_7a.pdf