This course provides a rigorous analysis of the design, implementation, and properties of advanced data structures. Topics include time-space analysis and tradeoffs in arrays, vectors, lists, stacks, queues, and heaps; tree and graph algorithms and traversals, hashing, sorting, and data structures on secondary storage. Surveys library implementations of basic data structures in a high-level language. Advanced data structure implementations are studied in detail. Illustrates the importance of choosing appropriate data structures when solving a problem by programming projects in a high-level language.
This course expands on CSE 250 by introducing techniques for data organization that account for the memory hierarchy and the need for concurrent access. Topics include IO Complexity, On-Disk Tree- and Hash- based structures, Write-optimized data structures (e.g., LSM Indexes and Beta-Epsilon Trees), Serialization/Data Layout, Caching, Secondary Indexes, Concurrent Data Structures, and Versioned Data Structures.
Database Systems teaches the inner workings of data management systems. Focus areas include organizational data structures (physical layouts, indexes, materialized views), data processing algorithms (join, sort), query optimization (relational algebra equivalences, query planning, cost modeling), transactional semantics (X-serializability, locking, OCC, MVCC), and recovery (WAL, Undo Logging, ARIES). The course involves a term-long project where students build a query processing system.
Languages & Runtimes for Big Data is a project based course exploring topics at the intersection of Data Management and Programming languages. Focus areas include indexing, databases on new hardware, uncertain data management, and concurrency. In addition to reading papers from ongoing research in these areas, students are expected to complete a term-long project based on one of several seed ideas provided by the instructors.
We run a yearly seminar with invited speakers from the database community each spring.
Seminar topics vary from term to term.
This page last updated 2024-09-19 13:18:43 -0400