Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps
- 0.0
-
![]()
![]()
![]()
![]()
![]()
Brief Introduction
Become familiar with nonlinear and hierarchical data structures. Study various tree structures: Binary Trees, BSTs and Heaps. Understand tree operations and algorithms. Learn and implement HashMaps that utilize key-value pairs to store data. Explore probabilistic data structures like SkipLists. Course tools help visualize the structures and performance.
Description
This Data Structures & Algorithms course extends beyond linear data structures in CS1332xI to the nonlinear and hierarchical data structures here in CS1332xII. 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 data structures. Time complexity is threaded throughout the course within all the nonlinear data structures and algorithms.
You will explore the hierarchical data structure of trees. Trees have important properties such as shape and order which are used to categorize trees into different groups and define their functionality. The course begins by explaining Binary Trees and two subgroups: Binary Search Trees (BSTs) and Binary Heaps. You will program BSTs, their operations and traversal algorithms. BSTs are an important structure when wanting to access information quickly. Heaps approach access differently and prioritize what data is accessed. Heaps also employ the concept of up-heap and down-heap operations not found in other structures.
HashMaps and SkipLists are the last data structures discussed in the course. The HashMap ADT is a collection of key-value pairs. The key-value pairs are stored in an unordered manner based on hash codes and compression functions that translate keys into integers. You will investigate different collision strategies and implement one. SkipLists are a probabilistic data structures where data is placed in the structure based on a randomization procedure.
The course design has several components and is built around modules. A module consists of a series of short (3-5 minute) instructional videos. In between the videos, there are textual frames with additional content information for clarification, as well as video errata dropdown boxes. All modules include an Exploratory Lab that incorporates a Visualization Tool specifically designed for this course. The lab includes discovery questions that lead you towards delving deeper into the efficiency of the data structures and examining the edge cases. This is followed by a set of comprehension questions on topics covered in the module that count for 10% of your grade. The modules end with Java coding assignments which are 60% of your grade. Lastly, you'll complete a course exam, which counts for the remaining 30% of your grade.
Knowledge
- 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
Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps
- 0.0
-
![]()
![]()
![]()
![]()
![]()
Become familiar with nonlinear and hierarchical data structures. Study various tree structures: Binary Trees, BSTs and Heaps. Understand tree operations and algorithms....
