JNTUH Data Structures syllabus CS 2-1 Sem R18 CS302PC

Unit-1 Introduction to Data Structures

Introduction to Data Structures, abstract data types, Linear list – singly linked list implementation, insertion, deletion and searching operations on linear list, Stacks-Operations, array and linked representations of stacks, stack applications, Queues-operations, array and linked representations.

Unit-2 Dictionaries

Dictionaries:

linear list representation, skip list representation, operations - insertion, deletion and searching.

 

Hash Table Representation:

hash functions, collision resolution-separate chaining, open addressing-linear probing, quadratic probing, double hashing, rehashing, extendible hashing.

Unit-3 Search Trees

Search Trees:

Binary Search Trees, Definition, Implementation, Operations- Searching, Insertion and Deletion, AVL Trees, Definition, Height of an AVL Tree, Operations – Insertion, Deletion and Searching, Red –Black, Splay Trees.

Unit-4 Graphs

Graphs:

Graph Implementation Methods. Graph Traversal Methods.

Sorting:

Heap Sort, External Sorting- Model for external sorting, Merge Sort.

Unit-5 Pattern Matching and Tries

Pattern Matching and Tries:

Pattern matching algorithms-Brute force, the Boyer –Moore algorithm, the Knuth-Morris-Pratt algorithm, Standard Tries, Compressed Tries, Suffix tries.

 

TEXTBOOKS:

1. Fundamentals of Data Structures in C, 2nd Edition, E. Horowitz, S. Sahni and Susan Anderson Freed, Universities Press.

2. Data Structures using C – A. S. Tanenbaum, Y. Langsam, and M.J. Augenstein, PHI/Pearson Education.

 

REFERENCE BOOKS:

1. Data Structures: A Pseudocode Approach with C, 2nd Edition, R. F. Gilberg and B.A. Forouzan, Cengage Learning.

 

Course Outcomes:

  • Ability to select the data structures that efficiently model the information in a problem.
  • Ability to assess efficiency trade-offs among different data structure implementations or combinations.
  • Implement and know the application of algorithms for sorting and pattern matching.
  • Design programs using a variety of data structures, including hash tables, binary and general tree structures, search trees, tries, heaps, graphs, and AVL-trees.