CS8391     DATA STRUCTURES     L T P C 3 0 0 3

OBJECTIVES:

  • To understand the concepts of ADTs
  • To Learn linear data structures –lists, stacks, and queues
  • To understand sorting, searching and hashing algorithms
  • To apply Tree and Graph structures

UNIT I     LINEAR DATA STRUCTURES –LIST     9

Abstract Data Types (ADTs) –List ADT –array-based implementation –linked list implementation ––singly  linked  lists-circularly  linked  lists-doubly-linked  lists –applications  of  lists –Polynomial Manipulation –All operations (Insertion, Deletion, Merge, Traversal).

UNIT II     LINEAR DATA STRUCTURES –STACKS, QUEUES     9

Stack ADT –Operations -Applications -Evaluating arithmetic expressions-Conversion of Infix to postfix  expression -Queue  ADT –Operations -Circular  Queue –Priority  Queue -deQueue –applications of queues.

UNIT III     NON LINEAR DATA STRUCTURES –TREES     9

Tree ADT –tree traversals -Binary Tree ADT –expression trees –applications of trees –binary search tree ADT –Threaded Binary Trees-AVL Trees –B-Tree -B+ Tree -Heap –Applications of heap.

UNIT IV     NON LINEAR DATA STRUCTURES -GRAPHS     9

Definition –Representation  of  Graph –Types  of  graph -Breadth-first  traversal -Depth-first traversal –Topological Sort –Bi-connectivity –Cut vertex –Euler circuits –Applications of graphs.

UNIT V     SEARCHING, SORTING AND HASHING TECHNIQUES     9

Searching-Linear Search -Binary Search. Sorting -Bubble sort -Selection sort -Insertion sort -Shell  sort –Radix  sort.  Hashing-Hash  Functions –Separate  Chaining –Open  Addressing –Rehashing –Extendible Hashing.

TOTAL: 45 PERIODS

OUTCOMES:

At the end of the course, the student should be able to:

  • Implement abstract data types for linear data structures.
  • Apply the different linear and non-linear data structures to problem solutions.
  • Critically analyze the various sorting algorithms.

TEXT BOOKS:

1. Mark  Allen  Weiss,  ―Data  Structures  and  Algorithm  Analysis  in  C‖,  2nd  Edition,  Pearson Education,1997.

2. Reema Thareja, ―Data Structures Using C‖, Second Edition , Oxford University Press, 2011

REFERENCES:

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein, ―Introduction toAlgorithms", Second Edition, Mcgraw Hill, 2002.

2. Aho, Hopcroft and Ullman, ―Data Structures and Algorithms‖, Pearson Education,1983.

3. Stephen G. Kochan, ―Programming in C‖, 3rd edition, Pearson Education.

4. Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed, ―Fundamentals of Data Structures in C‖, Second Edition, University Press, 2008