Skip to main content

UCSanDiegoX: Data Structures: An Active Learning Approach

Learn about high-performance data structures and supporting algorithms, as well as the fundamentals of theoretical time complexity analysis through an interactive online text.

Data Structures: An Active Learning Approach
10 weeks
6–7 hours per week
Self-paced
Progress at your own speed
Free
Optional upgrade available

There is one session available:

11,384 already enrolled! After a course session ends, it will be archivedOpens in a new tab.
Starts Dec 6
Enroll
Data Structures: An Active Learning Approach

About this course

Skip About this course

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.

At a glance

  • Institution: UCSanDiegoX
  • Subject: Computer Science
  • Level: Intermediate
  • Prerequisites:
    • Reading and understanding pseudocode
    • Performing time-complexity analysis using Big-O notation
    • Working with basic probabilities
    • Following formal mathematical proofs
    • Programming in either C++ or Python
  • Language: English
  • Video Transcript: English
  • Associated skills: Python (Programming Language), C++ (Programming Language), Computer Science, Algorithms, Algorithm Analysis, Data Structures, Time Complexity

What you'll learn

Skip 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

Syllabus

Skip 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

Ways to take this course

Choose your path when you enroll.

Verified Track

Audit Track

Price

$50 USD

Free

Access to course materials

Unlimited

Limited

Expires on Feb 14, 2024

World class institutions and universities

edX support

Shareable certificate upon completion

Graded assignments and exams

Read our FAQsin a new tab about frequently asked questions on these tracks.

Interested in this course for your business or team?

Train your employees in the most in-demand topics, with edX For Business.
Purchase nowRequest information