sort by: Relevancy | Title try advanced search for more options
Today's websites are increasingly dynamic. Pages are no longer static HTML files but instead generated by scripts and database calls. User interfaces are more seamless, with technologies like Ajax replacing traditional page reloads. This course teaches students how to build dynamic websites with Ajax and with Linux, Apache, MySQL, and PHP (LAMP), one of today's most popular frameworks. Students learn how to set up domain names with DNS, ho...more
This lecture describes a tour-de-force in integer data structures, called fusion trees (so named because they were published a year after the 1989 cold-fusion "scandal", and were perhaps just as surprising--though more correct). Fusion trees solve predecessor and successor among n w-bit integers in O(logw n) time per operation on the word RAM. The basic idea is to build a B-tree with branching factor wε. The tricky part is to build a wε-si...more
This lecture is our first (of two) about integer data structure lower bounds. In particular, we'll prove that the min of van Emde Boas and fusion trees is an optimal (static) predecessor data structure up to a log log factor, assuming polynomial space. The exact trade-off (up to constant factors) is known, but messier; we'll see the bound but not prove it. In particular, it is known that the log log factor improvements are actually impossi...more
This lecture continues our theme of dynamic graphs. Beyond surveying results for several such problems, we'll focus on dynamic connectivity, where you can insert and/or delete edges, and the query is to determine whether two vertices are in the same connected component (i.e., have a path between them). We'll cover a few different results for this problem: Link-cut trees (from last lecture) already solve trees in O(lg n). Euler-tour trees ...more
This lecture continues our theme of succinct data structures. Building on our expertise with succinct tries, we'll continue on to the practical problem of indexing text with suffix arrays/trees, where several compact and some succinct results are known, with reasonably small (though suboptimal) slowdowns in query time. We'll cover a simple version (not the best) of the historically first such result, which is a compact suffix array that in...more
Professor McBride uses this lecture to show that covalent bonding depends primarily on two factors: orbital overlap and energy-match. First he discusses how overlap depends on hybridization; then how bond strength depends on the number of shared electrons. In this way quantum mechanics shows that Coulomb's law answers Newton's query about what "makes the Particles of Bodies stick together by very strong Attractions." Energy mismatch betwee...more
In this lecture, the first of two about geometric data structures, we'll talk about two major problems-point location and range searching-and tie them to several major data structural techniques: persistence, retroactivity, dynamization of augmentation through weight balance, and fractional cascading.In (planar) point location, we need to preprocess a planar map to support queries of the form "which face contains this point?" This problem ...more
Today's lecture is our second and final lecture on time travel, or more precisely, temporal data structures. Here we will study retroactive data structures, which mimic the "plastic timeline" model of time travel. For example, in Back to the Future, Marty goes back in time, makes changes, and returns to the present that resulted from those changes and all the intervening years. In a partially retroactive data structures, the user can go ba...more
