Data Structures & Algorithms III: AVL and 2-4 Trees, Divide and Conquer Algorithms

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 8: AVL Trees

• Explore the AVL tree subgroup from Binary Search Trees (BST) and their distinguishing properties
• Discover the self-balancing of AVL trees, and which rotations are used to balance
• Implement the entire AVL tree data structure, and examine its performance

Module 9: (2-4) Trees

• Extend understanding of tree structures beyond binary trees to a more complex model
• Study the properties of (2-4) trees, and how operations maintain those properties
• Recognize when overflow and underflow situations arise within the (2-4) tree, and how to resolve those situations with promotion, fusion and transfer

Module 10: Iterative Sorting Algorithms

• Understand and implement four basic iterative, comparison sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort and Cocktail Shaker Sort
• Examine the characteristics of sorting algorithms: Stability, Adaptation and Memory
• Implement optimizations of these algorithms to yield better performance
• Analyze the time complexity of each of the algorithms

Module 11: Divide & Conquer Sorting Algorithms

• Introduction to the Divide & Conquer approach to sorting algorithms
• Implement and comprehend each of the divide & conquer algorithms presented: Merge Sort, In-Place Quick Sort and LSD Radix sort
• Examine the stability and memory usage of these sorting algorithms
• Explore the novel approach that LSD Radix sort uses to solve the sorting dilemma