GTx: Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps

• Develop mature Java programming skills by using recursion in Tree ADTs
• Investigate different nonlinear, linked data structures: Trees, Heaps, SkipLists and HashMaps
• Study the significant uses and applications of hierarchical tree structures
• Explore tree properties, and categorizing based on shape and order
• Design and implement the binary trees: BSTs and Heaps
• Examine edge cases and efficiencies in BST and Heap operations
• Understand the up-heap, down-heap and build-heap procedures
• Consider the probabilistic data structure, SkipLists, and randomization
• Implement a HashMap ADT with its key-value pairs
• Analyze the different collision strategies with HashMaps
• Compute amortized analysis for Heaps and HashMaps

Module 0: Introduction and Review

• Review of important Java principles involved in object-oriented design
• The Iterator & Iterable design patterns, and the Comparable & Comparator interfaces
• Basic “Big-Oh” notation and asymptotic analysis

Module 4: Binary Search Tree (BST) Introduction

• Learn about the non-linear, linked data structure, Trees, and the important submodels: Binary Trees and Binary Search Trees (BST)
• Acquire a working knowledge of the tree structure, including principles, properties and numerical concepts
• Examine traversal algorithms for BSTs, the resulting order and the information obtained by each

Module 5: BST Operations & SkipLists

• Extend understanding of tree structures and their impact on search operations
• Study and implement efficient procedures for the search, add and remove operations in BSTs
• Apply the concept of pointer reinforcement restructuring recursion technique to the add and remove operations
• Investigate the probabilistic data structure, SkipLists, and the implications of randomization on data structures

Module 6: Binary Heaps

• Explore the Binary Heap tree data structure and its additional property constraints that differentiate it from BSTs
• Delve into the add and remove operations that require the up-heap and down-heap procedures
• Explore the efficient bottom-up build heap algorithm

Module 7: HashMaps

• Study HashMaps designed for efficient storage and retrieval based on the concept of unique keys paired with values
• Learn about hash functions, hash codes and compression functions while implementing a basic HashMap
• Investigate data collisions and the strategies to resolve data collisions from external chaining to linear and quadratic probing to double hashing