Course description
Data Structures & Algorithms III: AVL and 2-4 Trees, Divide and Conquer Algorithms
This Data Structures & Algorithms course completes the data structures portion presented in the sequence of courses with self-balancing AVL and (2-4) trees. It also begins the algorithm portion in the sequence of courses. A short Java review is presented on topics relevant to new data structures covered in this course. The course does require prior knowledge of Java, object-oriented programming, and linear and nonlinear data structures. Time complexity is threaded throughout the course within all the data structures and algorithms.
You will investigate and explore the two more complex data structures: AVL and (2-4) trees. Both of these data structures focus on self-balancing techniques that will ensure all operations are O(log n). AVL trees are a subgroup of BSTs and thus inherit all the properties and constraints from BSTs. Additionally, AVLs incorporate rotations that are triggered when the tree is mutated and becomes out of balance. (2-4) trees are a subgroup of B-Trees and are non-binary trees with more than 2 children. 2-4 defines the range of children that exists in the trees. However, these trees are extremely flexible and allow the nodes to shrink and grow as needed to store more data. With this flexibility comes more issues to handle, like overflow and underflow which require more intense techniques to resolve the issues.
Upcoming start dates
Who should attend?
Prerequisites
Basic knowledge of the Java programming language, object-oriented principles, and the following abstract data types: Binary Search Trees, Heaps, and Hashmaps.
Training content
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
Course delivery details
This course is offered through The Georgia Institute of Technology, a partner institute of EdX.
9-10 hours per week
Costs
- Verified Track -$149
- Audit Track - Free
Certification / Credits
What you'll learn
- Improve Java programming skills by implementing AVLs and sorting algorithms
- Study techniques for restoring balance in AVL and (2-4) trees
- Distinguish when to apply single and double rotations in AVLs
- Investigate complex (2-4) trees that exhibit underflow and overflow problems
- Demonstrate the appropriate use of promotion, transfer and fusion in (2-4) trees
- Implement basic iterative sorting algorithms: Bubble, Insertion and Selection
- Explore optimizations to improve efficiency, including Cocktail Shaker Sort
- Contemplate two Divide & Conquer comparison sorting algorithms: Merge and Quick Sort
- Consider one non-comparison Divide & Conquer algorithm: LSD Radix Sort
- Analyze the stability, memory usage and adaptations of all sorting algorithms presented
- Study the time complexity for the AVLs, (2-4) Trees and sorting algorithms
Contact this provider
edX
edX For Business helps leading companies upskill their labor forces by making the world’s greatest educational resources available to learners across a wide variety of in-demand fields. edX For Business delivers high-quality corporate eLearning to train and engage your employees...