₹0 for students · Certificate · Intermediate

Data Structures (Open Data Structures)

14 lessons: lists, hashing, trees, heaps, sorting, graphs and B-trees, with Python code

Start free in the app

14 lessons · ~12 hours · 28-question final exam · pass mark 70%

About the course

What you’ll learn

The data structures every software engineer and interviewer expects you to know, taught from Pat Morin's open textbook Open Data Structures. Learn how array-based and linked lists, skiplists, hash tables, binary search trees, scapegoat and red-black trees, heaps, tries and B-trees work, why their operations take the time they do, and how sorting and graph search are built on them. Each lesson has a study guide, the book chapter, the matching Python implementation and a quiz. Pass every quiz and the final exam to earn a verifiable certificate.

Data structuresBig-O analysisLinked listsHash tablesBinary search treesBalanced treesHeapsSorting algorithmsGraph searchPython

Part of the career track: Computer Science Foundations

How the certificate works

  1. Read each lesson’s study guide, then the full lesson and any notebooks or exercises.
  2. Pass every lesson quiz with 70% or more.
  3. Pass the final exam: 28 questions in 40 minutes.
  4. Get a certificate with a public verification link, and add it to LinkedIn.

Syllabus

14 lessons in 4 parts

Foundations and lists

1
Introduction: Interfaces and Efficiency
45 min · A data structure's interface (what) is separate from its implementation (how).
2
Array-Based Lists
60 min · ArrayStack: O(1) get/set; add/remove at i cost O(n − i).
3
Linked Lists
50 min · SLList: O(1) push/pop at head and add at tail; implements Stack and Queue.
4
Skiplists
50 min · Levels L0…Lh; each element is promoted with probability 1/2.

Hashing and search trees

5
Hash Tables
55 min · Hash tables give O(1) expected add, remove and find (USet).
6
Binary Trees and Binary Search Trees
55 min · Binary trees: nodes with left, right and parent; depth and height.
7
Random Binary Search Trees and Treaps
50 min · Randomly built BSTs have expected depth O(log n), about 2 ln n.
8
Scapegoat Trees
45 min · Partial rebuilding: rebuild an unbalanced subtree into a perfectly balanced one.
9
Red-Black Trees
60 min · Red-black trees give O(log n) worst-case add, remove and find (Java TreeMap, C++ std::map).

Heaps, sorting and graphs

10
Heaps
45 min · Heaps implement priority queues: add and remove the minimum.
11
Sorting Algorithms
60 min · Merge sort: O(n log n) worst case, extra space.
12
Graphs
55 min · A graph has vertices and edges; edges may be directed.

Integers and external memory

13
Data Structures for Integers
50 min · Using the bits of w-bit integer keys can beat comparison bounds.
14
External Memory Searching and B-Trees
50 min · Disk access is far slower than memory; the external memory model counts block transfers of B items.

Course content is based on "Open Data Structures" by Pat Morin (https://opendatastructures.org/, source at https://github.com/patmorin/ods), used under a Creative Commons Attribution licence. Study guides and quiz questions are written by Vikosha. Certificates are issued by Vikosha and are not issued or endorsed by the author. Licence: Creative Commons Attribution (CC BY), Copyright Pat Morin. View the original curriculum