JNTUK R20 DATA STRUCTURES

 

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:
  1. Data Structures Using C. 2ndEdition.Reema Thareja, Oxford.
  2. Data Structures and algorithm analysis in C, 2nded, Mark Allen Weiss.
ReferenceBooks:
  1. Fundamentals of Data Structures in C, 2nd Edition, Horowitz, Sahni, Universities Press.
  2. Data Structures: A PseudoCode Approach, 2/e, Richard F.Gilberg, Behrouz A.Forouzon, Cengage.
  3. 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

No comments

JavaFX Scene Builder

  This is an article about the JavaFX Scene Builder. You will get a short introduction about the installation and usage of the software. The...