Data Structures: An Active Learning Approach

Brought by: edX

Overview

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 being taught at the University of California, San Diego (UCSD), the University of San Diego (USD), and the University of Puerto Rico (UPR).
 
This coursework 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.

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.9 And the Iterators Gonna Iterate-ate-ate

Module 3: Tree Structures
  • 3.1 Lost 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.1 The Unquenched Need for Speed
  • 5.2 Hash Functions
  • 5.3 Introduction to Hash Tables
  • 5.4 Probability of Collisions
  • 5.5 Collision Resolution: Open Addressing
  • 5.6 Collision Resolution: Closed Addressing (Separate Chaining)
  • 5.7 Collision 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.1 Return 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.1 Summaries of Data Structures

Taught by

Niema Moshiri

Data Structures: An Active Learning Approach
Go to course

Data Structures: An Active Learning Approach

Brought by: edX

  • edX
  • Free
  • English
  • Certificate Not Available
  • Certain days
  • intermediate
  • English
8.1.2PHP Version190msRequest Duration2MBMemory UsageGET en/courses/{slug}Route
    • Booting (113ms)
    • Application (76.15ms)
    • 1 x Booting (59.65%)
      113.26ms
      1 x Application (40.1%)
      76.15ms
      14 templates were rendered
      • public.courses.show (resources/views/public/courses/show.blade.php)3bladefile
        Params
        0
        course
        1
        links
        2
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.courses.partials.details (resources/views/public/courses/partials/details.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.layouts.main (resources/views/public/layouts/main.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.meta (resources/views/public/layouts/partials/meta.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.navbar (resources/views/public/layouts/partials/navbar.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.links (resources/views/public/auth/profile/partials/links.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.layouts.partials.flash-session (resources/views/public/layouts/partials/flash-session.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      uri
      GET en/courses/{slug}
      middleware
      web, localize:en
      controller
      App\Http\Controllers\CourseController@show
      as
      en.courses.show
      namespace
      prefix
      /en
      where
      file
      app/Http/Controllers/CourseController.php:17-35
      7 statements were executed4.03ms
      • select * from `courses` where `slug_en` = 'data-structures:-an-active-learning-approach' limit 1
        2.35ms/app/Http/Controllers/CourseController.php:20corspedia
        Metadata
        Bindings
        • 0. data-structures:-an-active-learning-approach
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:20
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • update `courses` set `visitors` = `visitors` + 1, `courses`.`updated_at` = '2025-02-13 14:06:26' where `id` = 563
        310μs/app/Http/Controllers/CourseController.php:21corspedia
        Metadata
        Bindings
        • 0. 2025-02-13 14:06:26
        • 1. 563
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:21
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `topic_id`, `slug_en`, `slug_ar` from `subjects` where `subjects`.`id` in (6)
        230μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `slug_en`, `slug_ar` from `topics` where `topics`.`id` in (1)
        210μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 25. /app/Http/Controllers/CourseController.php:23
        • 26. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 27. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 28. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 29. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `institutions` where `institutions`.`id` in (19) and `institutions`.`deleted_at` is null
        360μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `providers` where `providers`.`id` in (1) and `providers`.`deleted_at` is null
        320μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `html_files` where `html_files`.`id` = 557 limit 1
        250μs/app/Models/Course.php:84corspedia
        Metadata
        Bindings
        • 0. 557
        Backtrace
        • 21. /app/Models/Course.php:84
        • 28. view::public.courses.show:29
        • 30. /vendor/laravel/framework/src/Illuminate/Filesystem/Filesystem.php:125
        • 31. /vendor/laravel/framework/src/Illuminate/View/Engines/PhpEngine.php:58
        • 32. /vendor/laravel/framework/src/Illuminate/View/Engines/CompilerEngine.php:72
      App\Models\HtmlFile
      1
      App\Models\Provider
      1
      App\Models\Institution
      1
      App\Models\Topic
      1
      App\Models\Subject
      1
      App\Models\Course
      1
        _token
        YsKGGpDhgthYN8QCmBVadQ2Lpo8LCTdqj9h6P839
        locale
        en
        _previous
        array:1 [ "url" => "https://www.corspedia.com/en/courses/data-structures:-an-active-learning-appro...
        _flash
        array:2 [ "old" => [] "new" => [] ]
        PHPDEBUGBAR_STACK_DATA
        []
        path_info
        /en/courses/data-structures:-an-active-learning-approach
        status_code
        200
        
        status_text
        OK
        format
        html
        content_type
        text/html; charset=UTF-8
        request_query
        []
        
        request_request
        []
        
        request_headers
        0 of 0
        array:24 [ "sec-ch-ua-mobile" => array:1 [ 0 => "?0" ] "sec-ch-ua" => array:1 [ 0 => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" ] "cache-control" => array:1 [ 0 => "no-cache" ] "pragma" => array:1 [ 0 => "no-cache" ] "cdn-loop" => array:1 [ 0 => "cloudflare; loops=1" ] "priority" => array:1 [ 0 => "u=0, i" ] "upgrade-insecure-requests" => array:1 [ 0 => "1" ] "user-agent" => array:1 [ 0 => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" ] "cf-connecting-ip" => array:1 [ 0 => "18.218.121.8" ] "accept" => array:1 [ 0 => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" ] "sec-fetch-site" => array:1 [ 0 => "none" ] "cf-visitor" => array:1 [ 0 => "{"scheme":"https"}" ] "sec-fetch-mode" => array:1 [ 0 => "navigate" ] "sec-fetch-user" => array:1 [ 0 => "?1" ] "x-forwarded-proto" => array:1 [ 0 => "https" ] "cf-ipcountry" => array:1 [ 0 => "US" ] "accept-encoding" => array:1 [ 0 => "gzip, br" ] "sec-fetch-dest" => array:1 [ 0 => "document" ] "sec-ch-ua-platform" => array:1 [ 0 => ""Windows"" ] "x-forwarded-for" => array:1 [ 0 => "18.218.121.8" ] "cf-ray" => array:1 [ 0 => "91156106d9bbf608-ORD" ] "host" => array:1 [ 0 => "www.corspedia.com" ] "content-length" => array:1 [ 0 => "" ] "content-type" => array:1 [ 0 => "" ] ]
        request_server
        0 of 0
        array:50 [ "USER" => "www-data" "HOME" => "/var/www" "HTTP_SEC_CH_UA_MOBILE" => "?0" "HTTP_SEC_CH_UA" => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" "HTTP_CACHE_CONTROL" => "no-cache" "HTTP_PRAGMA" => "no-cache" "HTTP_CDN_LOOP" => "cloudflare; loops=1" "HTTP_PRIORITY" => "u=0, i" "HTTP_UPGRADE_INSECURE_REQUESTS" => "1" "HTTP_USER_AGENT" => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" "HTTP_CF_CONNECTING_IP" => "18.218.121.8" "HTTP_ACCEPT" => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" "HTTP_SEC_FETCH_SITE" => "none" "HTTP_CF_VISITOR" => "{"scheme":"https"}" "HTTP_SEC_FETCH_MODE" => "navigate" "HTTP_SEC_FETCH_USER" => "?1" "HTTP_X_FORWARDED_PROTO" => "https" "HTTP_CF_IPCOUNTRY" => "US" "HTTP_ACCEPT_ENCODING" => "gzip, br" "HTTP_SEC_FETCH_DEST" => "document" "HTTP_SEC_CH_UA_PLATFORM" => ""Windows"" "HTTP_X_FORWARDED_FOR" => "18.218.121.8" "HTTP_CF_RAY" => "91156106d9bbf608-ORD" "HTTP_HOST" => "www.corspedia.com" "REDIRECT_STATUS" => "200" "SERVER_NAME" => "corspedia.com" "SERVER_PORT" => "443" "SERVER_ADDR" => "141.95.147.152" "REMOTE_USER" => "" "REMOTE_PORT" => "27750" "REMOTE_ADDR" => "172.70.130.154" "SERVER_SOFTWARE" => "nginx/1.18.0" "GATEWAY_INTERFACE" => "CGI/1.1" "HTTPS" => "on" "REQUEST_SCHEME" => "https" "SERVER_PROTOCOL" => "HTTP/2.0" "DOCUMENT_ROOT" => "/var/www/corspedia/public" "DOCUMENT_URI" => "/index.php" "REQUEST_URI" => "/en/courses/data-structures:-an-active-learning-approach" "SCRIPT_NAME" => "/index.php" "CONTENT_LENGTH" => "" "CONTENT_TYPE" => "" "REQUEST_METHOD" => "GET" "QUERY_STRING" => "" "SCRIPT_FILENAME" => "/var/www/corspedia/public/index.php" "PATH_INFO" => "" "FCGI_ROLE" => "RESPONDER" "PHP_SELF" => "/index.php" "REQUEST_TIME_FLOAT" => 1739455586.6202 "REQUEST_TIME" => 1739455586 ]
        request_cookies
        []
        
        response_headers
        0 of 0
        array:5 [ "content-type" => array:1 [ 0 => "text/html; charset=UTF-8" ] "cache-control" => array:1 [ 0 => "no-cache, private" ] "date" => array:1 [ 0 => "Thu, 13 Feb 2025 14:06:26 GMT" ] "set-cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6IkRwRjZJaUhGby9QZmRXYmw3ZG1OWVE9PSIsInZhbHVlIjoiTEM4K20vWTNpa1dBV2dmT3IzMDJTZ0hlTktsbWFvUW93YTJqaGpla1Q4YkpTcGZ1QWdHZzhzelVWNjJ0SEhQbjdjbEdrMEtHeHNuc1UxbEV5RXpFS082dzJhVWFDWjQyNkY0VjRwV2x4alZ0MnVmK1ZLeGVKcjFxaGhiU29wQUYiLCJtYWMiOiI2NmEwY2YwODQyNzUyNWU0ZjVlNjQyYmQyY2M1NWU2NDQ1MWIwNWQxYTMwODRkNmYyOGM4M2M4OTg5OWU1MzU2IiwidGFnIjoiIn0%3D; expires=Thu, 13 Feb 2025 16:06:26 GMT; Max-Age=7200; path=/; samesite=laxXSRF-TOKEN=eyJpdiI6IkRwRjZJaUhGby9QZmRXYmw3ZG1OWVE9PSIsInZhbHVlIjoiTEM4K20vWTNpa1dBV2dmT3IzMDJTZ0hlTktsbWFvUW93YTJqaGpla1Q4YkpTcGZ1QWdHZzhzelVWNjJ0SEhQbjdjbEdrM" 1 => "laravel_session=eyJpdiI6Iit4dWpDYS9ZL0JPWWhiTndpY2d6cWc9PSIsInZhbHVlIjoiSkVtREZFSllCTUtFdTYrSjZKeEw5UWNFZS80eHBya1ovcU4wVHpuZFF3Y0JWWHpDWWZTUnIxU2pOZjVNaWptTWVEWHNiemdoR3Zmc2c2ZDJHNXhPRThQM3NzaG9oclJ0QmJDaFowS1plQ0pIMXB2UmJIUXpkc1FrS3MzdW1nczkiLCJtYWMiOiI4MWRlMmRkNTk3YTY3NTdlMWM4YTliOTk5OWYxYTNjYzE4NmQxNGU3YTgyNWVlZDViYjk0YjBkZmIxOGRmZjY5IiwidGFnIjoiIn0%3D; expires=Thu, 13 Feb 2025 16:06:26 GMT; Max-Age=7200; path=/; httponly; samesite=laxlaravel_session=eyJpdiI6Iit4dWpDYS9ZL0JPWWhiTndpY2d6cWc9PSIsInZhbHVlIjoiSkVtREZFSllCTUtFdTYrSjZKeEw5UWNFZS80eHBya1ovcU4wVHpuZFF3Y0JWWHpDWWZTUnIxU2pOZjVNaWptTWVE" ] "Set-Cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6IkRwRjZJaUhGby9QZmRXYmw3ZG1OWVE9PSIsInZhbHVlIjoiTEM4K20vWTNpa1dBV2dmT3IzMDJTZ0hlTktsbWFvUW93YTJqaGpla1Q4YkpTcGZ1QWdHZzhzelVWNjJ0SEhQbjdjbEdrMEtHeHNuc1UxbEV5RXpFS082dzJhVWFDWjQyNkY0VjRwV2x4alZ0MnVmK1ZLeGVKcjFxaGhiU29wQUYiLCJtYWMiOiI2NmEwY2YwODQyNzUyNWU0ZjVlNjQyYmQyY2M1NWU2NDQ1MWIwNWQxYTMwODRkNmYyOGM4M2M4OTg5OWU1MzU2IiwidGFnIjoiIn0%3D; expires=Thu, 13-Feb-2025 16:06:26 GMT; path=/XSRF-TOKEN=eyJpdiI6IkRwRjZJaUhGby9QZmRXYmw3ZG1OWVE9PSIsInZhbHVlIjoiTEM4K20vWTNpa1dBV2dmT3IzMDJTZ0hlTktsbWFvUW93YTJqaGpla1Q4YkpTcGZ1QWdHZzhzelVWNjJ0SEhQbjdjbEdrM" 1 => "laravel_session=eyJpdiI6Iit4dWpDYS9ZL0JPWWhiTndpY2d6cWc9PSIsInZhbHVlIjoiSkVtREZFSllCTUtFdTYrSjZKeEw5UWNFZS80eHBya1ovcU4wVHpuZFF3Y0JWWHpDWWZTUnIxU2pOZjVNaWptTWVEWHNiemdoR3Zmc2c2ZDJHNXhPRThQM3NzaG9oclJ0QmJDaFowS1plQ0pIMXB2UmJIUXpkc1FrS3MzdW1nczkiLCJtYWMiOiI4MWRlMmRkNTk3YTY3NTdlMWM4YTliOTk5OWYxYTNjYzE4NmQxNGU3YTgyNWVlZDViYjk0YjBkZmIxOGRmZjY5IiwidGFnIjoiIn0%3D; expires=Thu, 13-Feb-2025 16:06:26 GMT; path=/; httponlylaravel_session=eyJpdiI6Iit4dWpDYS9ZL0JPWWhiTndpY2d6cWc9PSIsInZhbHVlIjoiSkVtREZFSllCTUtFdTYrSjZKeEw5UWNFZS80eHBya1ovcU4wVHpuZFF3Y0JWWHpDWWZTUnIxU2pOZjVNaWptTWVE" ] ]
        session_attributes
        0 of 0
        array:5 [ "_token" => "YsKGGpDhgthYN8QCmBVadQ2Lpo8LCTdqj9h6P839" "locale" => "en" "_previous" => array:1 [ "url" => "https://www.corspedia.com/en/courses/data-structures:-an-active-learning-approach" ] "_flash" => array:2 [ "old" => [] "new" => [] ] "PHPDEBUGBAR_STACK_DATA" => [] ]