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 Trands in Hashing, Trees, and various computational geometry methods for efficiently solving the new evolving problem

R19 M. TECH. CN/CNIS/CYBER SECURITY

References:

• 1. Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, 2nd Edition, Pearson, 2004.
• 2. M T Goodrich, Roberto Tamassia, Algorithm Design, John Wiley, 2002. R19 M. TECH. CN/CNIS/CYBER SECURITY M. Tech. (CNIS/CN/Cyber Security) – I Year – I Semester Common to CNIS, CN and Cyber Security