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.
Sorting: 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.
