JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Prerequisites

A course on “Data Structures”

Course Objectives

• 1. Introduces the heap data structures such as leftist trees, binomial heaps, Fibonacci and min- max heaps
• 2. Introduces a variety of data structures such as disjoint sets, hash tables, search structures and digital search structures

Course Outcomes

• 1. Ability to select the data structures that efficiently model the information in a problem
• 2. Ability to understand how the choice of data structures impact the performance of programs
• 3. Design programs using a variety of data structures, including hash tables, search structures and digital search structures

UNIT - I

Heap Structures Introduction, Min-Max Heaps, Leftist trees, Binomial Heaps, Fibonacci heaps.

UNIT - II

Hashing and Collisions Introduction, Hash Tables, Hash Functions, different Hash Functions: Division Method, Multiplication Method, Mid-Square Method, Folding Method, Collisions

UNIT - III

Search Structures: OBST, AVL trees, Red-Black trees, Splay trees, Multiway Search Trees: B-trees, 2-3 trees

UNIT - IV

Digital Search Structures Digital Search trees, Binary tries and Patricia, Multiway Tries, Suffix trees, Standard Tries, Compressed Tries

UNIT - V

Pattern matching Introduction, Brute force, the Boyer –Moore algorithm, Knuth-Morris-Pratt algorithm, Naïve String, Harspool, Rabin Karp

TEXT BOOKS:

• 1. Fundamentals of data structures in C++ Sahni, Horowitz, Mehatha, Universities Press.
• 2. Introduction to Algorithms, TH Cormen, PHI

REFERENCES:

• 1. Design methods and analysis of Algorithms, SK Basu, PHI.
• 2. Data Structures & Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education.
• 3. Fundamentals of Computer Algorithms, 2nd Edition, Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Universities Press.