JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Pre-Requisites

UG level course in Data Structures

Course Objectives:

The student should be able to choose appropriate data structures, understand the ADT/libraries, and use it to design algorithms for a specific problem. Students should be able to understand the necessary mathematical abstraction to solve problems. To familiarize students with advanced paradigms and data structure used to solve algorithmic problems. Student should be able to come up with analysis of efficiency and proofs of correctness.

Course Outcomes

After completion of course, students would be able to:

Understand the implementation of symbol table using hashing techniques. Understand the implementation of symbol table using hashing techniques. Develop algorithms for text processing applications. Identify suitable data structures and develop algorithms for computational geometry problems.

UNIT - I

Dictionaries: Definition, Dictionary, Abstract Data Type, Implementation of Dictionaries. Hashing: Review of Hashing, Hash Function, Collision Resolution Techniques in Hashing, Separate Chaining, Open Addressing, Linear Probing, Quadratic Probing, Double Hashing, Rehashing, Extendible Hashing.

UNIT - II

Skip Lists: Need for Randomizing Data Structures and Algorithms, Search and Update Operations on Skip Lists, Probabilistic Analysis of Skip Lists, Deterministic Skip Lists.

UNIT - III

Trees: Binary Search Trees, AVL Trees, Red Black Trees, 2-3 Trees, B-Trees, Splay Trees

UNIT - IV

Text Processing: Sting Operations, Brute-Force Pattern Matching, The Boyer- Moore Algorithm, The Knuth-Morris-Pratt Algorithm, Standard Tries, Compressed Tries, Suffix Tries, The Huffman Coding Algorithm, The Longest Common Subsequence Problem (LCS), Applying Dynamic Programming to the LCS Problem

UNIT - V

Computational Geometry: One Dimensional Range Searching, Two-Dimensional Range Searching, constructing a Priority, Search Tree, Searching a Priority Search Tree, Priority Range Trees, Quadtrees, k-D Trees. Recent Trends in Hashing, Trees, and various computational geometry methods for efficiently solving the new evolving problem

Text/Reference Books: Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, 2nd Edition, Pearson, 2004. M T Goodrich, Roberto Tamassia, Algorithm Design, John Wiley, 2002.

M.Tech. (Data Science) I Year I Semester