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

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.

What's inside

Learning objectives

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

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

Syllabus

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

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Develops mature Java programming skills by using recursion in Tree ADTs

Investigates different nonlinear, linked data structures: Trees, Heaps, SkipLists and HashMaps

Designed for efficient storage and retrieval based on the concept of unique keys paired with values

Offers hands-on labs and interactive materials

Requires prior knowledge of Java, object-oriented programming and linear data structures

Taught by Mary Hudachek-Buswell

Reviews summary

Engaging course on data structures ii

Learners say that this course is extremely well received. This well-organized course is praised for its varied content, concise lectures, challenging problem sets, and high-quality instruction. Students who recommend this course say that it is especially beneficial for those looking to learn or brush up on specific data structures and algorithms.

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps with these activities:

Collection of Coding Challenges and Resources

Show steps

Compile a collection of coding challenges, online resources, and tools related to data structures and algorithms in Java.

Browse courses on Data Structures

Show steps

Search for and gather coding challenges from various online platforms.
Identify and list helpful online resources, such as tutorials, articles, and documentation.
Organize and categorize the collected resources based on topic and difficulty.

Data Structures and Algorithms with Java: A Guide to Data Structures, Algorithms, and Object-Oriented Design Patterns in Java

Show steps

Review a comprehensive guide to data structures and algorithms in Java, reinforcing your understanding of concepts covered in the course.

View Data Structures and Algorithms in Java on Amazon

Show steps

Read chapters relevant to the course topics.
Practice the exercises and examples provided in the book.
Summarize key concepts and algorithms in your own words.

Java Basics: Object-Oriented Design

Show steps

Revisit object-oriented design principles in Java to strengthen your foundational understanding of data structures and algorithms.

Show steps

Review the concepts of classes, objects, and inheritance.
Explore the principles of encapsulation, abstraction, and polymorphism.
Practice creating and using custom Java classes and objects.

Four other activities

Expand to see all activities and additional details

Show all seven activities

Walkthrough of Binary Search Tree Implementation

Show steps

Follow along with guided tutorials that demonstrate step-by-step how to implement a Binary Search Tree in Java.

Show steps

Find tutorials that cover BST implementation in Java.
Follow the instructions and code along to create your own BST implementation.
Test your BST implementation with sample data and verify its functionality.

Heap Manipulation Exercises

Show steps

Engage in practice drills that challenge you to manipulate heaps, such as building, inserting, and extracting elements.

Browse courses on Priority Queues

Show steps

Solve coding exercises that involve heap operations.
Implement different heap algorithms, such as heap sort or heapify.
Analyze the time complexity of your heap implementations.

Collaborative HashMap Implementation

Show steps

Participate in peer sessions where you collaborate on designing and implementing a HashMap in Java, exploring collision resolution strategies.

Browse courses on Data Structures

Show steps

Form a study group with peers.
Brainstorm different collision resolution techniques.
Design and implement a custom HashMap with the chosen collision resolution strategy.
Test and evaluate the performance of your HashMap implementation.

SkipList Data Structure Project

Show steps

Undertake a project to design and implement a SkipList data structure in Java, exploring its probabilistic nature and performance characteristics.

Browse courses on Data Structures

Show steps

Research the concept and algorithms behind SkipLists.
Design and implement a SkipList data structure in Java.
Analyze the performance of your SkipList implementation and compare it to other data structures.
Document your findings and insights in a technical report.

Career center

Learners who complete Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps will develop knowledge and skills that may be useful to these careers:

Software Engineer II

As a Software Engineer II, you will have the opportunity to work on a variety of projects that require a solid foundation in data structures and algorithms. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course will provide you with the skills you need to succeed in this role. Specifically, the course will teach you about binary trees, binary search trees, heaps, skiplists, and hashmaps. These concepts are essential for understanding how to design and implement efficient software applications.

See salaries and explore the career path for Software Engineer II

Data Analyst

As a Data Analyst, you will be responsible for collecting, cleaning, and analyzing data to help organizations make informed decisions. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course will provide you with the skills you need to succeed in this role. Specifically, the course will teach you about how to use data structures and algorithms to efficiently store, retrieve, and analyze data.

See salaries and explore the career path for Data Analyst

Software Developer

As a Software Developer, you will be responsible for designing, developing, and testing software applications. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course will provide you with the skills you need to succeed in this role. Specifically, the course will teach you about how to use data structures and algorithms to efficiently design and implement software applications.

See salaries and explore the career path for Software Developer

Database Administrator

As a Database Administrator, you will be responsible for managing and maintaining databases. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course will provide you with the skills you need to succeed in this role. Specifically, the course will teach you about how to use data structures and algorithms to efficiently store and retrieve data from databases.

See salaries and explore the career path for Database Administrator

Systems Analyst

As a Systems Analyst, you will be responsible for analyzing and designing computer systems. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course will provide you with the skills you need to succeed in this role. Specifically, the course will teach you about how to use data structures and algorithms to efficiently design and implement computer systems.

See salaries and explore the career path for Systems Analyst

Web Developer

As a Web Developer, you will be responsible for designing, developing, and maintaining websites and web applications. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently design and implement web applications.

See salaries and explore the career path for Web Developer

Machine Learning Engineer

As a Machine Learning Engineer, you will be responsible for developing and deploying machine learning models. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently design and implement machine learning models.

See salaries and explore the career path for Machine Learning Engineer

Data Scientist

As a Data Scientist, you will be responsible for collecting, cleaning, and analyzing data to help organizations make informed decisions. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently store, retrieve, and analyze data.

See salaries and explore the career path for Data Scientist

Computer Programmer

As a Computer Programmer, you will be responsible for writing and maintaining computer programs. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently design and implement computer programs.

See salaries and explore the career path for Computer Programmer

Computer Systems Analyst

As a Computer Systems Analyst, you will be responsible for analyzing and designing computer systems. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently design and implement computer systems.

See salaries and explore the career path for Computer Systems Analyst

IT Project Manager

As an IT Project Manager, you will be responsible for planning, executing, and managing IT projects. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently manage IT projects.

See salaries and explore the career path for IT Project Manager

Information Systems Manager

As an Information Systems Manager, you will be responsible for managing and maintaining information systems. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently design and implement information systems.

See salaries and explore the career path for Information Systems Manager

Software Test Engineer

As a Software Test Engineer, you will be responsible for testing and validating software applications. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently test and validate software applications.

See salaries and explore the career path for Software Test Engineer

Database Engineer

As a Database Engineer, you will be responsible for designing, developing, and maintaining databases. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently design and implement databases.

See salaries and explore the career path for Database Engineer

Technical Writer

As a Technical Writer, you will be responsible for writing and maintaining technical documentation. The Data Structures & Algorithms II: Binary Trees, Heaps, SkipLists and HashMaps course may be useful for this role, as it will teach you about how to use data structures and algorithms to efficiently organize and present technical information.

See salaries and explore the career path for Technical Writer