Advanced Data Structures

View Course Materials

Buying via our links supports this free directory · Affiliate disclosure.
Course facts
  • Payment: Free, no certificate
  • Credits: Non Credit
  • Learning style: Self-paced, start anytime
  • Resources: Instructor Insights; Lecture Notes; Lecture Videos; Problem Set Solutions; Problem Sets
MIT OpenCourseWare details
  • As taught in: Spring 2012
  • Department: Electrical Engineering and Computer Science
Created byMIT
Available onMIT OpenCourseWareMIT OpenCourseWare

Course Details
Learning Style

Start Anytime

Level

All Levels

Study Mode

100% Online

Outcomes
Academic Credits

Non Credit

Price & Terms
Pricing Model

Free Content (No Certificate)

Technical
Content Medium

Video Based

Specification
Access

Free Access

Academic Level

Graduate

SKU: advanced-data-structures Category: Tag: Brand:

Graduate data structures: persistence, geometry, dynamic optimality, cache-oblivious and integer structures, succinct structures and dynamic graphs.

At a glance
LevelAll Levels
AccessFree access
FormatVideo Based
As taught inSpring 2012
DepartmentElectrical Engineering and Computer Science
Add your review
Add to wishlistAdded to wishlistRemoved from wishlist 0
Add to compare

Data structures sit underneath search engines, mail servers and network routers, and they are the building blocks of efficient algorithms. This graduate course covers the major results and current research directions in data structures, in recorded lectures with notes, at least half of it on work from the last decade: persistent and retroactive structures, geometric structures, dynamic optimality, memory hierarchy and cache-oblivious structures, integer structures such as fusion trees, strings, succinct structures and dynamic graphs.

What You Will Achieve

  • Explain persistent, retroactive and geometric data structures and their trade-offs
  • Analyze data structures under memory hierarchy and cache-oblivious models
  • Use integer data structures such as fusion trees, and the lower bounds that limit them
  • Describe succinct structures, string structures and dynamic graph connectivity


Program Overview

Time, Space and Geometry

Structures that remember the past or handle geometry.

  • Persistent and retroactive data structures
  • Geometric structures
  • Dynamic optimality

Memory and Integer Models

How the model of computation shapes what is possible.

  • Memory hierarchy models and cache-oblivious structures
  • Dictionaries and integer models
  • Fusion trees and integer lower bounds
  • Sorting in linear time

Trees, Strings, Succinct Structures and Graphs

Specialized structures at the research frontier.

  • Static trees and strings
  • Succinct structures
  • Dynamic graphs and the dynamic connectivity lower bound
  • The history of memory models

Course Completion


Job Outlook

Advanced data structures are used in algorithm research, search and database engines, systems programming, computational geometry and high-performance software.


Before you start: The prerequisite for this course is 6.046, Design and Analysis of Algorithms, or an equivalently thorough undergraduate algorithms class from another school (e.g., covering much of CLRS). I recommend that you take 6.854, Advanced Algorithms, the broad entry-level graduate course in Theory / Algorithms—it normally makes sense to start there before jumping into deeper graduate courses. If you haven’t taken 6.854, you must have a strong understanding of algorithms at the undergraduate level, such as receiving an A in 6.046, having done relevant research, involvement in computer competitions, etc.

Our take

Good for: Learners drawn to theoretical computer science who want to see where data structures research stands.

Keep in mind: It is a research-level course: the final project is a theoretical contribution, an implementation study, a survey or Wikipedia articles, and the problem sets expect short typeset proofs.

Bottom line: A research-oriented tour of modern data structures, taught by Erik Demaine, with problem sets that have published solutions.

Frequently Asked Questions

How much of the course is recent research?

At least half of it covers research done in the decade before the course, alongside older results from the 1970s that remain important and have changed little.

What can the final project be?

A theoretical contribution or open problem, an implementation with experiments, a survey of a few papers, or a substantial improvement to Wikipedia articles on advanced data structures.

How are the problem sets written?

Each is one page typeset in LaTeX, meant to train the concise writing of research papers, and solutions are published for them.

User Reviews

0.0 out of 5
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0

No reviews yet. Be the first to review this course.

There are no reviews yet.

Write your review

Reviews can only be posted by registered learners. Log in, then you will return here to post.

×

    Report this page
    LiveTalent
    Logo
    Compare items
    • Total (0)
    Compare
    0