Data Structures Fundamentals from edX

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, part of the Algorithms and Data Structures MicroMasters program, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures.

A few examples of questions that we are going to cover in this course are:

What is a good strategy of resizing a dynamic array?
How priority queues are implemented in C++, Java, and Python?
How to implement a hash table so that the amortized running time of all operations is O(1) on average?
What are good strategies to keep a binary tree balanced?

We look forward to seeing you in this course! We know it will make you a better programmer.

What you'll learn

Basics of data structures including their fundamental building blocks: arrays and linked lists
How to use Dynamic arrays
A very powerful and widely used technique called hashing and its applications
How to use priority queues to efficiently schedule jobs, in the context of a computer operating system or real life
Basic structure of binary search trees - AVL trees and Splay trees
Applications of data structures

What's inside

Learning objectives

Basics of data structures including their fundamental building blocks: arrays and linked lists
How to use dynamic arrays
A very powerful and widely used technique called hashing and its applications

How to use priority queues to efficiently schedule jobs, in the context of a computer operating system or real life
Basic structure of binary search trees - avl trees and splay trees
Applications of data structures

Basics of data structures including their fundamental building blocks: arrays and linked lists
How to use dynamic arrays
A very powerful and widely used technique called hashing and its applications
How to use priority queues to efficiently schedule jobs, in the context of a computer operating system or real life
Basic structure of binary search trees - avl trees and splay trees
Applications of data structures

Syllabus

Module 1: Basic Data Structures In this module, you will learn about the basic data structures used throughout the rest of this course. We start this module by looking in detail at the fundamental building blocks: arrays and linked lists. From there, we build up two important data structures: stacks and queues. Next, we look at trees: examples of how they’re used in Computer Science, how they’re implemented, and the various ways they can be traversed. Once you’ve completed this module, you will be able to implement any of these data structures, as well as have a solid understanding of the costs of the operations, as well as the tradeoffs involved in using each data structure.

Module 2: Dynamic Arrays and Amortized Analysis In this module, we discuss Dynamic Arrays: a way of using arrays when it is unknown ahead-of-time how many elements will be needed. Here, we also discuss amortized analysis: a method of determining the amortized cost of an operation over a sequence of operations. Amortized analysis is very often used to analyse performance of algorithms when the straightforward analysis produces unsatisfactory results, but amortized analysis helps to show that the algorithm is actually efficient. It is used both for Dynamic Arrays analysis and will also be used in the end of this course to analyze Splay trees.

Module 3: Priority Queues and Disjoint Set Union We start this module by considering priority queues which are used to efficiently schedule jobs, either in the context of a computer operating system or in real life, to sort huge files, which is the most important building block for any Big Data processing algorithm, and to efficiently compute shortest paths in graphs, which is a topic we will cover in our next course. For this reason, priority queues have built-in implementations in many programming languages, including C++, Java, and Python. We will see that these implementations are based on a beautiful idea of storing a complete binary tree in an array that allows to implement all priority queue methods in just few lines of code. We will then switch to disjoint sets data structure that is used, for example, in dynamic graph connectivity and image processing. We will see again how simple and natural ideas lead to an implementation that is both easy to code and very efficient. By completing this module, you will be able to implement both these data structures efficiently from scratch.

Modules 4 and 5: Hash Tables In this module you will learn about very powerful and widely used technique called hashing. Its applications include implementation of programming languages, file systems, pattern search, distributed key-value storage and many more. You will learn how to implement data structures to store and modify sets of objects and mappings from one type of objects to another one. You will see that naive implementations either consume huge amount of memory or are slow, and then you will learn to implement hash tables that use linear memory and work in O(1) on average!

Module 6: Binary Search Trees In this module we study binary search trees, which are a data structure for doing searches on dynamically changing ordered sets. You will learn about many of the difficulties in accomplishing this task and the ways in which we can overcome them. In order to do this you will need to learn the basic structure of binary search trees, how to insert and delete without destroying this structure, and how to ensure that the tree remains balanced.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Suitable for students with little to no background or experience in programming or computer science

Compelling programming assignments allow students to apply the course concepts in practice

Taught by recognized experts Alexander S. Kulikov, Neil Rhodes, Michael Levin, and Daniel Kane

Emphasizes theoretical understanding and real-world applications of data structures and algorithms

Covers a comprehensive range of topics including priority queues, hashing, binary search trees, and amortized analysis

May require some foundational knowledge and understanding of programming languages like C++, Java, and Python

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 Fundamentals with these activities:

Connect with experts in data structures and algorithms

Show steps

Seeking guidance from experienced professionals can accelerate your learning and provide valuable insights into real-world applications of data structures.

Browse courses on Mentorship

Show steps

Attend industry events, meetups, or conferences where you can connect with experts in the field.
Reach out to professors, researchers, or professionals on LinkedIn or other social media platforms.
Request informational interviews or mentorship opportunities to learn from their experiences and perspectives.

Review array indexing

Show steps

Arrays are used throughout the course. Sharpening skills in array indexing will lay a solid foundation for success in this course.

Show steps

Revisit fundamental array concepts like declaration, initialization, and accessing elements.
Practice traversing arrays using different loop structures (for, while, do-while).
Explore techniques for manipulating arrays, such as inserting, deleting, and searching elements.

Join a study group or online forum

Show steps

Engaging with peers in discussions and problem-solving can reinforce your understanding of data structures and provide diverse perspectives.

Show steps

Find online forums or discussion groups dedicated to data structures and algorithms.
Participate in discussions, ask questions, and share your knowledge to foster a collaborative learning environment.
Consider joining a local study group or organizing one with fellow students.

Two other activities

Expand to see all activities and additional details

Show all five activities

Explore Python implementation of data structures

Show steps

The course uses Python. This activity will familiarize you with Python implementations of key data structures, aiding comprehension of the course material.

Browse courses on Python Programming

Show steps

Find tutorials or online resources that demonstrate how to implement data structures like stacks, queues, trees, and hash tables in Python.
Follow the tutorials and try implementing these data structures on your own, using Python code.
Test your implementations with sample inputs and analyze their performance.

Read 'Data Structures and Algorithms Made Easy'

Show steps

This book provides a comprehensive overview of data structures and algorithms, with a focus on practical applications. Reading it will strengthen your understanding of the concepts covered in this course.

View Data Structures and Algorithms Made Easy: Data... on Amazon

Show steps

Go through chapters covering fundamental data structures like arrays, linked lists, and stacks.
Explore sections explaining searching and sorting algorithms, such as binary search and quicksort.
Review chapters on advanced data structures like trees and graphs, along with their applications.

Career center

Learners who complete Data Structures Fundamentals will develop knowledge and skills that may be useful to these careers:

Data Scientist

Data Scientists use their knowledge of math, statistics, and computer science to gather, analyze, and interpret large amounts of data, drawing conclusions and making predictions. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Data Scientist.

See salaries and explore the career path for Data Scientist

Software Engineer

Software Engineers design, develop, test, and maintain software applications. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Software Engineer.

See salaries and explore the career path for Software Engineer

Systems Analyst

Systems Analysts design, develop, and implement computer systems. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Systems Analyst.

See salaries and explore the career path for Systems Analyst

Data Analyst

Data Analysts collect, clean, and analyze data to identify trends and patterns. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Data Analyst.

See salaries and explore the career path for Data Analyst

Database Administrator

Database Administrators design, implement, and maintain databases. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Database Administrator.

See salaries and explore the career path for Database Administrator

Business Analyst

Business Analysts analyze business processes and systems to identify opportunities for improvement. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Business Analyst.

See salaries and explore the career path for Business Analyst

Statistician

Statisticians collect, analyze, and interpret data to draw conclusions. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Statistician.

See salaries and explore the career path for Statistician

Operations Research Analyst

Operations Research Analysts use mathematical models to solve business problems. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as an Operations Research Analyst.

See salaries and explore the career path for Operations Research Analyst

Actuary

Actuaries use mathematical models to assess risk. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as an Actuary.

See salaries and explore the career path for Actuary

Market Researcher

Market Researchers conduct surveys and analyze data to understand consumer behavior. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Market Researcher.

See salaries and explore the career path for Market Researcher

Financial Analyst

Financial Analysts analyze financial data to make investment recommendations. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Financial Analyst.

See salaries and explore the career path for Financial Analyst

Software Tester

Software Testers test software to identify bugs. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Software Tester.

See salaries and explore the career path for Software Tester

Computer Programmer

Computer Programmers write code to implement software applications. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Computer Programmer.

See salaries and explore the career path for Computer Programmer

Information Security Analyst

Information Security Analysts protect computer systems from unauthorized access. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as an Information Security Analyst.

See salaries and explore the career path for Information Security Analyst

Technical Writer

Technical Writers write documentation for software applications. This course will help you understand the fundamental building blocks of data structures, such as arrays and linked lists, and how to use them to build more complex data structures, such as stacks and queues. You will also learn about dynamic arrays, amortized analysis, priority queues, disjoint set union, hash tables, and binary search trees. This knowledge will give you a solid foundation for a career as a Technical Writer.

See salaries and explore the career path for Technical Writer