The document outlines the course structure for 'Advanced Data Structures' at GITAM School of Technology, detailing prerequisites, educational objectives, and course outcomes. It covers various topics including basic data structures, maps, trees, graphs, and pattern matching techniques. The course aims to equip students with the ability to analyze algorithms, implement hashing techniques, and apply data structures in real-world applications.
The document outlines the course structure for 'Advanced Data Structures' at GITAM School of Technology, detailing prerequisites, educational objectives, and course outcomes. It covers various topics including basic data structures, maps, trees, graphs, and pattern matching techniques. The course aims to equip students with the ability to analyze algorithms, implement hashing techniques, and apply data structures in real-world applications.
The document outlines the course structure for 'Advanced Data Structures' at GITAM School of Technology, detailing prerequisites, educational objectives, and course outcomes. It covers various topics including basic data structures, maps, trees, graphs, and pattern matching techniques. The course aims to equip students with the ability to analyze algorithms, implement hashing techniques, and apply data structures in real-world applications.
The document outlines the course structure for 'Advanced Data Structures' at GITAM School of Technology, detailing prerequisites, educational objectives, and course outcomes. It covers various topics including basic data structures, maps, trees, graphs, and pattern matching techniques. The course aims to equip students with the ability to analyze algorithms, implement hashing techniques, and apply data structures in real-world applications.
GITAM (Deemed to be University) GITAM School of Technology
CSEN3151 ADVANCED DATA STRUCTURES L T P S J C
2 1 0 0 0 3
Pre-requisite Data Structures
Co-requisite Data Structures Preferable None exposure
Course Description: After the students have gone through a course on data structures, where they learn the formal and abstract representations of data and its manipulation. Studying course on advanced data structures should teach the students concrete implementations and manipulation of such basic data structures and their use in design and analysis of non-trivial algorithms for a given computational task. On completion of such a course, students should be able to analyse the asymptotic performance of algorithms demonstrate their familiarity with major data structures, rule to manipulate those, and their canonical applications such as graphs and pattern recognition. Course Educational Objectives: ● Analyze algorithms and data structures applying methods for amortized analysis ● Evaluate methods for performance improvement of dictionaries and hashing techniques. ● Analyze and assess various time and space efficient searching tree data structures ● Analyze and assess the applicability of fundamental graph algorithms to applications and external sorting schemes. ● Define and apply data structures for Pattern Matching and tries
UNIT 1 Review of basic Data Structures 9 hours
Recursion: illustrative examples; Array based sequences: low level arrays, Dynamic Arrays, amortized analysis; Stacks, Queues, Double Ended Queues. Priority Queues: Priority Queue as ADT, Implementing Heap using Priority Queue, Sorting with Priority Queue.
UNIT 2 Maps and Hash Tables 9 hours
Maps, and Hash Tables: Maps and Dictionaries, Hash Tables. Hash table representation: Hash functions, collision resolution-separate chaining, open addressing- linear probing, quadratic probing, double hashing, rehashing, extendible hashing, comparison of hashing and skip lists.
B Tech. Computer Science and Engineering w.e.f. 2021-22 admitted batch
GITAM (Deemed to be University) GITAM School of Technology
UNIT 3 Trees 9 hours
General Trees, Binary Trees, Implementing Trees, Binary search trees; Balanced search trees, AVL trees, Splay Trees, Red –Black Trees, Multiway search Trees, B-Trees, B-Tree of order m, height of a B-Tree, insertion, deletion and searching, Comparison of Search Trees. UNIT 4 Graphs 9 hours The graph ADT, Representation in memory; Directed Acyclic Graph; Shortest path using Prim- Jarnik Algorithm and Kruskal's Algorithm; Disjoint Partitions and Union Find Structures. External Sorting: Model for external sorting, Multi-way merge, Polyphase merge.
UNIT 5 Pattern Matching and Tries 9 hours
Pattern Matching: Pattern matching algorithms -Brute force, the Boyer –Moore algorithm, the Knuth-Morris- Pratt algorithm Tries: Standard Tries, Compressed Tries, Suffix Tries, Search Engine Indexing.
Textbooks: 1. Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, 4rd Edition, Pearson,2014 2. Michael T. Goodrich, R.Tamassia and Michael H. Goldwasser, Data structures and Algorithms in Python,Wileystudentedition,JohnWileyandSons,2013. 3. Bradley N Miller, David Ranum, Problem Solving with Algorithms and Data Structures using Python, Franklin, Beedle& Associates publishing, 2013. References: 1. Data structures using java, Langsam, Augenstein and Tanenbaum, PHI, 2003. 2. Peter Brass, Advanced data structures. Vol. 193. Cambridge: Cambridge University Press, 2008 3. https://www.coursera.org/learn/algorithms-graphs-data-structures Course Outcomes: After successful completion of the course the student will be able to: 1. analyze the different algorithms and data structures. 2. implement different hashing techniques 3. assess the time and space efficient searching trees 4.implement graphs to real time applications 5. apply data structures for pattern matching
B Tech. Computer Science and Engineering w.e.f. 2021-22 admitted batch
GITAM (Deemed to be University) GITAM School of Technology
