Data Structures: An Active Learning Approach from edX

This interactive text used in this course was written with the intention of teaching Computer Science students about various data structures as well as the applications in which each data structure would be appropriate to use. It is currently beingtaught at the University of California, San Diego (UCSD), the University of San Diego (USD), and the University of Puerto Rico (UPR).

Thiscoursework utilizes the Active Learning approach to instruction, meaning it has various activities embedded throughout to help stimulate your learning and improve your understanding of the materials we will cover. You will encounter "STOP and Think" questions that will help you reflect on the material, "Exercise Breaks" that will test your knowledge and understanding of the concepts discussed, and "Code Challenges" that will allow you to actually implement some of the algorithms we will cover.

Currently, all code challenges are in C++ or Python, but the vast majority of the content is language-agnostic theory of complexity and algorithm analysis. In other words, even without C++ or Python knowledge, the key takeaways can still be obtained.

What you'll learn

The algorithms behind fundamental data structures (dynamic arrays, linked structures, (un)balanced trees/tries, graph algorithms, hash tables/functions)
How to reason about appropriate data structures to solve problems, including their strengths and weaknesses
How to analyze algorithms theoretically (worst-case, average-case, and amortized)
The key distinctions and relations between "Abstract Data Types" and "Data Structures"
Basic information theory and data compression utilizing the data structures covered

What's inside

Learning objectives

The algorithms behind fundamental data structures (dynamic arrays, linked structures, (un)balanced trees/tries, graph algorithms, hash tables/functions)
How to reason about appropriate data structures to solve problems, including their strengths and weaknesses
How to analyze algorithms theoretically (worst-case, average-case, and amortized)

The key distinctions and relations between "abstract data types" and "data structures"
Basic information theory and data compression utilizing the data structures covered

The algorithms behind fundamental data structures (dynamic arrays, linked structures, (un)balanced trees/tries, graph algorithms, hash tables/functions)
How to reason about appropriate data structures to solve problems, including their strengths and weaknesses
How to analyze algorithms theoretically (worst-case, average-case, and amortized)
The key distinctions and relations between "abstract data types" and "data structures"
Basic information theory and data compression utilizing the data structures covered

Syllabus

Module 1: Introduction and Review

1.1 Welcome to Data Structures!

1.2 Tick Tock, Tick Tock

1.3 Classes of Computational Complexity

1.4 The Fuss of C++

1.5 Random Numbers

1.6 Bit-by-Bit

1.7 The Terminal-ator

1.8 Git: the "Undo" Button of Software Development

Module 2: Introductory Data Structures

2.1 Array Lists

2.2 Linked Lists

2.3 Skip Lists

2.4 Circular Arrays

2.5 Abstract Data Types

2.6 Deques

2.7 Queues

2.8 Stacks

2.9And the Iterators Gonna Iterate-ate-ate

Module 3: Tree Structures

3.1Lost in a Forest of Trees

3.2 Heaps

3.3 Binary Search Trees

3.4 BST Average-Case Time Complexity

3.5 Randomized Search Trees

3.6 AVL Trees

3.7 Red-Black Trees

3.8 B- Trees

3.9 B+ Trees

Module 4: Introduction to Graphs

4.1 Introduction to Graphs

4.2 Graph Representations

4.3 Algorithms on Graphs: Breadth-First Search

4.4 Algorithms on Graphs: Depth-First Search

4.5 Dijkstra's Algorithm

4.6 Minimum Spanning Trees: Prim's and Kruskal's Algorithms

4.7 Disjoint Sets

Module 5: Hashing

5.1The Unquenched Need for Speed

5.2 Hash Functions

5.3 Introduction to Hash Tables

5.4 Probability of Collisions

5.5Collision Resolution: Open Addressing

5.6Collision Resolution: Closed Addressing (Separate Chaining)

5.7Collision Resolution: Cuckoo Hashing

5.8 Hash Maps

Module 6:Implementing a Lexicon

6.1 Creating a Lexicon

6.2 Using Linked Lists

6.3 Using Arrays

6.4 Using Binary Search Trees

6.5 Using Hash Tables and Hash Maps

6.6 Using Multiway Tries

6.7 Using Ternary Search Trees

Module 7:Coding and Information Compression

7.1Return of the (Coding) Trees

7.2 Entropy and Information Theory

7.3 Honey, I Shrunk the File

7.4 Bitwise I/O

Module 8: Conclusions

8.1Summaries of Data Structures

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Relevant to academia and industry, this course teaches fundamental data structures and their applications

Utilizes active learning to enhance engagement and understanding

Emphasizes algorithm analysis, providing a solid foundation for theoretical understanding

Covers a wide range of data structures, from introductory to advanced concepts

Taught by reputable instructors, Niema Moshiri and Liz Izhikevich

May require prior programming knowledge, particularly in C++ or Python

Reviews summary

Highly rated data structure course

learners say that this course is widely well received as an introduction to data structures. The materials are well-written and the course focuses on the theory behind data structures, but also has a lot of coding challenges. It is thorough, practical, and uses colorful, engaging diagrams, illustrations to help visualize data structures.

Course focuses on underlying theory of data structures

"Excellent and concise course on Data Structures. The course focuses on the theory behind the data structures, but it includes multiple coding problems throughout."

Course uses diagrams and illustrations to help visualize data structures

"This is the perfect data structures course for beginners. It is thorough, practical, fun, colorful, and it includes amazing diagrams and illustrations to help visualize data structures, their operations, and their elements."

Course materials, assignments, and quizzes are well-written

"Great course on data structures! The learning materials, assignments, and quizzes are well-written."

Students highly recommend this course to other learners

"Very nice and well structured course about data structures. Highly recommended as an introduction to abstract data structures, graphs and hashing."

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: An Active Learning Approach with these activities:

Read Chapters 1-3 of Levitin's Introduction to the Design & Analysis of Algorithms

Show steps

Builds a foundational understanding of the theoretical underpinnings of the course.

Browse courses on Algorithm Efficiency

Show steps

Review Chapter 1: Introduction
Review Chapter 2: Asymptotic Analysis
Review Chapter 3: Fundamental Data Structures

Complete LeetCode Easy Problems on Array and String Manipulation

Show steps

Provides hands-on practice with basic data structure operations.

Browse courses on Arrays

Show steps

Solve 10 LeetCode Easy problems involving arrays
Solve 10 LeetCode Easy problems involving strings

Follow Tutorial on Hashing Functions and Collision Resolution

Show steps

Expands knowledge of hash table implementation and optimization techniques.

Browse courses on Hashing

Show steps

Find a comprehensive tutorial on hashing functions and collision resolution
Follow the tutorial and implement a hash table in your preferred programming language

Four other activities

Expand to see all activities and additional details

Show all seven activities

Develop a Visual Aid for Understanding Linked Lists

Show steps

Enhances comprehension of linked list concepts through visual representation.

Browse courses on Linked Lists

Show steps

Brainstorm and sketch different visualization techniques
Create a visual aid using a tool of your choice (e.g., flowchart, diagram, animation)
Present or share your visualization with others

Compile Resources on B-Trees and B+ Trees

Show steps

Provides a comprehensive reference for understanding and comparing B-Tree variants.

Browse courses on B-Trees

Show steps

Gather articles, tutorials, and videos on B-Trees and B+ Trees
Organize the resources into a structured document or online collection

Read Chapter 4 of Cormen et al.'s Introduction to Algorithms

Show steps

Provides in-depth coverage of graph algorithms and their applications.

View Introduction to Algorithms, fourth edition on Amazon

Show steps

Read and understand the concepts presented in Chapter 4
Solve the practice problems at the end of the chapter

Implement a Custom Data Structure in Python

Show steps

Strengthens understanding of data structure design and implementation.

Browse courses on Python Programming

Show steps

Choose a data structure to implement
Design and develop the implementation in Python
Test and debug your implementation

Career center

Learners who complete Data Structures: An Active Learning Approach will develop knowledge and skills that may be useful to these careers:

Data Scientist

Data Scientists use data to solve business problems. They develop and apply statistical and machine learning techniques to identify trends and patterns in data. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the development and application of statistical and machine learning techniques.

See salaries and explore the career path for Data Scientist

Information Security Analyst

Information Security Analysts are responsible for protecting computer systems and networks from unauthorized access, use, disclosure, disruption, modification, or destruction. They use a variety of security measures, including firewalls, intrusion detection systems, and encryption. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of security measures.

See salaries and explore the career path for Information Security Analyst

Cloud Architect

Cloud Architects design and implement cloud computing solutions. They work with users to identify business needs and develop solutions that meet those needs. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of cloud computing solutions.

See salaries and explore the career path for Cloud Architect

Database Architect

Database Architects design and implement databases. They work with users to identify business needs and develop solutions that meet those needs. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of databases.

See salaries and explore the career path for Database Architect

Data Warehouse Architect

Data Warehouse Architects design and implement data warehouses. They work with users to identify business needs and develop solutions that meet those needs. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of data warehouses.

See salaries and explore the career path for Data Warehouse Architect

Big Data Engineer

Big Data Engineers design and implement big data solutions. They work with users to identify business needs and develop solutions that meet those needs. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of big data solutions.

See salaries and explore the career path for Big Data Engineer

Computer Programmer

Computer Programmers write, test, and maintain computer programs. They use a variety of programming languages and technologies to develop software that meets the needs of users. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the writing, testing, and maintenance of computer programs.

See salaries and explore the career path for Computer Programmer

Information Systems Manager

Information Systems Managers are responsible for the planning, implementation, and maintenance of information systems. They work with users to identify business needs and develop solutions that meet those needs. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the planning, implementation, and maintenance of information systems.

See salaries and explore the career path for Information Systems Manager

Network Engineer

Network Engineers design, implement, and maintain computer networks. They ensure that networks are reliable, efficient, and secure. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of computer networks.

See salaries and explore the career path for Network Engineer

Systems Analyst

Systems Analysts are responsible for the design, implementation, and maintenance of computer systems. They work with users to identify business needs and develop solutions that meet those needs. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of computer systems.

See salaries and explore the career path for Systems Analyst

Software Engineer

Software Engineers design, develop, test, and maintain computer software. They work in a wide range of industries, including computer systems design, software development, and information technology. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and development of software systems.

See salaries and explore the career path for Software Engineer

Data Analyst

Data Analysts collect, clean, and analyze data to help businesses make informed decisions. They use a variety of statistical and programming techniques to identify trends and patterns in data. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the collection, cleaning, and analysis of data.

See salaries and explore the career path for Data Analyst

Database Administrator

Database Administrators are responsible for the design, implementation, and maintenance of databases. They ensure that databases are reliable, efficient, and secure. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and implementation of databases.

See salaries and explore the career path for Database Administrator

Web Developer

Web Developers design and develop websites. They use a variety of programming languages and technologies to create websites that are user-friendly, efficient, and secure. This course can be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and development of websites.

See salaries and explore the career path for Web Developer

Computer Scientist

Computer Scientists help design and develop computer hardware and software. They study the theory, design, development, and application of computer systems and work in a wide range of industries. Taking this course may be useful in preparing for this role, as it teaches the algorithms behind fundamental data structures, including dynamic arrays, linked structures, and trees. This knowledge can be applied to the design and development of computer systems.

See salaries and explore the career path for Computer Scientist