• Duración:
    10 semanas
  • Dedicación:
    6–7 horas por semana
  • Precio:

    GRATIS
    Agregar un Certificado Verificado por $50 USD

  • Institución
  • Tema:
  • Nivel:
    Intermediate
  • Idioma:
    English
  • Transcripción de video:
    English
  • Tipo de curso:
    A tu ritmo

Prerrequisitos

  • 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

Sobre este curso

Omitir Sobre este curso
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.

Lo que aprenderás

Omitir Lo que aprenderás
  • 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

Plan de estudios

Omitir Plan de estudios
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

Conoce a tus instructores

Niema Moshiri
Ph. D. Student
The University of California, San Diego
Christine Alvarado
Associate Teaching Professor, Computer Science and Engineering
The University of California, San Diego
Liz Izhikevich
M.S. Student, Computer Science and Engineering
The University of California, San Diego

Obtén un Certificado Verificado para destacar los conocimientos y las habilidades que adquieras
$50 USD

Ver un modelo de certificado de edX en PDF
  • Oficial y verificado

    Obtén un certificado con la firma del instructor y el logotipo de la institución para demostrar tus logros y aumentar las posibilidades de conseguir trabajo

  • Fácil de compartir

    Agrega el certificado a tu currículum o publícalo directamente en LinkedIn

  • Incentivo comprobado

    El certificado te da un motivo más para completar el curso

  • Apoya nuestra labor

    edX, una organización sin fines de lucro, se sustenta con los certificados verificados para financiar la educación gratuita para todo el mundo