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

Por: edX . en: , ,


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