MIT 6.851 Advanced Data Structures

Implementation of data structures from MIT’s 6.851 Advanced Data Structures course (Spring 2012) in Guile Scheme.

Course Information

• Course: 6.851 Advanced Data Structures
• Instructor: Prof. Erik Demaine
• Term: Spring 2012
• Implementation Language: Guile Scheme
• Approach: Literate programming with Org-mode

Setup

System Prerequisites

• Emacs (for org-mode support)
• Guile 2.2+ (or Guile 3.0)
• SQLite3
• Python 3 (for downloading tools)
• wget (for mirroring)
• yt-dlp (for video downloads)

Academic Prerequisites

This course requires strong background in algorithms and data structures. See the prerequisites guide for detailed preparation information:

• **Essential**: MIT 6.046 (Design and Analysis of Algorithms) or equivalent
• **Recommended**: MIT 6.854 (Advanced Algorithms) or equivalent
• **Mathematical**: Strong proof-writing skills, probability theory, amortized analysis

Quick self-assessment: Can you implement balanced BSTs, analyze amortized costs, and write mathematical proofs? If not, review the prerequisites first.

Installation

1. Clone the repository:

   git clone https://github.com/aygp-dr/mit-6851-advanced-data-structures.git
   cd mit-6851-advanced-data-structures
       

2. Check dependencies:

   make check-deps
       

3. Setup environment:

   make setup
       

4. Download course materials:

   make download-materials  # PDFs and website mirror
   make download-videos     # Video lectures (optional)
       

5. Setup scribe templates:

   make scribe-template
       

Usage

Working on Sessions

Each lecture session has its own directory with implementation, tests, and notes:

# Work on Session 1
make session-1

# List all sessions
make list-sessions

# Run tests for current session
cd sessions/01-persistent-data-structures
make test

Running Tests

# Run all tests
make test

# Run session-specific tests
cd sessions/01-persistent-data-structures
guile tests/test-persistent-stack.scm

Creating Scribe Notes

1. Copy the template:

   cp templates/lec-template.org scribes/lec01.org
       

2. Edit in Emacs with org-mode
3. Export to LaTeX:

   make export-scribe ORG_FILE=scribes/lec01.org
       

Literate Programming

Session notes use org-mode with embedded Scheme code:

#+BEGIN_SRC scheme :tangle src/implementation.scm
(define (persistent-operation data)
  ;; Implementation here
  ...)
#+END_SRC

Extract code with:

make tangle  # In session directory

Project Structure

.
├── lib/                    # Core library implementations
├── tests/                  # Main test suite
├── sessions/               # Session-specific implementations
│   ├── 01-persistent-data-structures/
│   │   ├── Makefile       # Session build rules
│   │   ├── notes/         # Org-mode literate notes
│   │   ├── src/           # Extracted source code
│   │   └── tests/         # Session tests
│   └── ...
├── materials/              # Downloaded materials (gitignored)
│   ├── pdfs/              # Lecture PDFs
│   ├── videos/            # Video lectures
│   └── mirror/            # Website mirrors
├── scripts/                # Utility scripts
├── templates/              # Document templates
└── Makefile               # Main build system

Implemented Data Structures

Temporal Data Structures

• [X] Persistent Stack (Session 1)
• [X] Versioned Stack (Session 1)
• [ ] Persistent Queue
• [ ] Retroactive Queue
• [ ] Retroactive Priority Queue

Geometric Data Structures

• [ ] Point Location
• [ ] Orthogonal Range Trees
• [ ] Fractional Cascading
• [ ] Kinetic Data Structures

Dynamic Optimality

• [ ] Splay Trees
• [ ] Tango Trees
• [ ] Multi-Splay Trees

Memory Hierarchies

• [ ] B-Trees
• [ ] Cache-Oblivious B-Trees
• [ ] Buffer Trees
• [ ] Cache-Oblivious Priority Queues

Integer Data Structures

• [ ] Van Emde Boas Trees
• [ ] X-fast Tries
• [ ] Y-fast Tries
• [ ] Fusion Trees

String Data Structures

• [ ] Suffix Arrays
• [ ] Suffix Trees
• [ ] Suffix Automata

Succinct Data Structures

• [ ] Rank/Select
• [ ] Succinct Trees
• [ ] Compressed Text Indexes

Dynamic Graphs

• [ ] Link-Cut Trees
• [ ] Euler Tour Trees
• [ ] Dynamic Connectivity

Development

Testing

Tests use SRFI-64 framework:

(use-modules (srfi srfi-64))

(test-begin "data-structure-name")

(test-group "operation-group"
  (test-assert "description" 
    (condition)))

(test-end "data-structure-name")

Contributing

1. Fork the repository
2. Create a feature branch
3. Implement with tests
4. Update documentation
5. Submit pull request

See PROJECT_NOTES.md for detailed guidelines.

Code Style

• Use descriptive names (stack-push not push)
• Predicates end with ? (empty?, stack-node?)
• Include docstrings for public functions
• Add complexity analysis in comments

Resources

Course Materials

• MIT OpenCourseWare
• CSAIL Course Page
• YouTube Playlist

References

• Okasaki, C. (1998). Purely Functional Data Structures
• Driscoll et al. (1989). Making Data Structures Persistent
• Demaine, E. (2012). 6.851 Lecture Notes

Related Projects

• Purely Functional Data Structures
• Okasaki’s Thesis

License

Educational implementation based on MIT OpenCourseWare materials. See LICENSE for details.

Acknowledgments

• Prof. Erik Demaine for the excellent course
• MIT OpenCourseWare for making materials freely available
• The Guile Scheme community for the implementation platform