JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Prerequisite:

• 1. A course on “Programming for Problem Solving “

Course Objectives:

• Exploring basic data structures such as stacks and queues.
• Introduces a variety of data structures such as hash tables, search trees, tries, heaps, graphs.
• Introduces sorting and pattern matching algorithms

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.

UNIT - I

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 - II

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 - III

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 - IV

Graphs: Graph Implementation Methods. Graph Traversal Methods. Sortings: Heap Sort, External Sorting- Model for external sorting, Merge Sort.

UNIT - V

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

TEXT BOOKS:

• 1. Fundamentals of data structures in C, 2 nd 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.
• 2. Introduction to data structures in c, 1/e Ashok Kamthane.