Advanced Data Structures
Dive into advanced data structures and algorithms including hashing, red-black trees, B-trees, splay trees, text processing, computational geometry, and randomized algorithms. Explore key concepts, operations, and applications with practical examples and in-depth analysis.
Uploaded on Feb 20, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Advanced Data Structures M.B.Chandak hodcs@rknec.edu www.mbchandak.com
Course-Curriculum Unit-I Hashing: Review of Hashing, Hash Function, Collision Resolution Techniques in Hashing, Separate Chaining, Open Addressing, Analysis of Open and Closed Hashing, Rehashing, Hash Tables with Worst-Case O(1) Access: Perfect Hashing, Cuckoo Hashing, Hopscotch Hashing. Extendible Hashing. Unit-II Red Black Trees: Height of a Red Black Tree, Red Black Trees Bottom-Up Insertion, Top-Down Red Black Trees, Top-Down Deletion in Red Black Trees, Analysis of Operations. Splay Trees: Splaying, Search and Update Operations on Splay Trees, Amortized Analysis of Splaying.
Course-Curriculum Unit-III B-Trees: Advantage of B- trees over BSTs, Height of B-Tree, Search and Update Operations on B-Trees, Analysis of Operations, Introduction to B+ Trees Garbage Collection: Review, Challenges, Management Interface, Mark-and-Sweep: Garbage Collection Algorithm, Garbage Collection in Java Unit-IV Text Processing: Sting Operations, Brute-Force Pattern Matching, Boyer- Moore Algorithm, Rabin-Karp Algorithm, String Matching with Finite Automata, The Knuth-Morris-Pratt Algorithm, Multiple Longest Common Subsequence Problem (MLCS) Recent Trends, Memory
Course-Curriculum 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, Quad-trees, k-D Trees, Applications. Unit-VI Randomized Algorithms: Need Approaches, Randomized Quicksort, Approximation Algorithm, Sum of Subset Problem. for Randomized Primality Algorithms, Testing,
Course Outcomes On successful completion of the course, students will be able to: 1. Understand implementation of symbol table using hashing techniques. 2. Develop and analyze algorithms for red-black trees, B-trees and Splay trees. 3. Develop algorithms for text processing applications. 4. Identity suitable data structures and develop algorithms for computational geometry problems. randomized algorithms Understand and design
Teachers Assessment modes [40 marks] Course passing cut off: 40-42 [AA = 85 and above] Test 1 = 15 marks [Compulsory] Test 2 = 15 marks [Compulsory] For 10 marks: Method-1 Project based on JAVA / Python Technologies. Interested students can register: Individual projects preferred. Method-2 Class assignments/Quiz/Case studies
Text books: PDF available online Textbooks 1. Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Fourth Edition, PearsonEducation, 2002. 2. Horowitz, Sahni and Rajasekaran, Computer Algorithms, Universities Press, 2000. 3. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithm, Third edition, PHI, 2009. References 1. Aho,Hopcroft and Ullman, Data Structures and Algorithms, Pearson Education, 2002. 2. M T Goodrich, Roberto Tamassia, Algorithm Design, John Wiley, 2002. 3. Tanenbaum, Langram and Augestien, Data Structures using C and C++, Prentice Hall of India, 2002.
