data/session_01.html

<div class="transcript-body" lang="en">
    <div class="transcript-line" data-begin="0.09">
        <span class="transcript-timestamp">0:00</span>
        <span class="transcript-text">The following content is
            provided under a Creative</span>
        </div>
    <div class="transcript-line" data-begin="2.49"><span class="transcript-timestamp">0:02</span><span
            class="transcript-text">Commons license.</span></div>
    <div class="transcript-line" data-begin="4.03"><span class="transcript-timestamp">0:04</span><span
            class="transcript-text">Your support will help
            MIT OpenCourseWare</span></div>
    <div class="transcript-line" data-begin="6.36"><span class="transcript-timestamp">0:06</span><span
            class="transcript-text">continue to offer high quality
            educational resources for free.</span></div>
    <div class="transcript-line" data-begin="10.72"><span class="transcript-timestamp">0:10</span><span
            class="transcript-text">To make a donation or
            view additional materials</span></div>
    <div class="transcript-line" data-begin="13.32"><span class="transcript-timestamp">0:13</span><span
            class="transcript-text">from hundreds of MIT courses,
            visit MIT OpenCourseWare</span></div>
    <div class="transcript-line" data-begin="17.28"><span class="transcript-timestamp">0:17</span><span
            class="transcript-text">at ocw.mit.edu.</span></div>
    <div class="transcript-line" data-begin="21.056"><span class="transcript-timestamp">0:21</span><span
            class="transcript-text">ERIK DEMAINE: Welcome to 6.851
            Advanced Data Structures.</span></div>
    <div class="transcript-line" data-begin="25.28"><span class="transcript-timestamp">0:25</span><span
            class="transcript-text">I am Erik Demaine.</span></div>
    <div class="transcript-line" data-begin="26.42"><span class="transcript-timestamp">0:26</span><span
            class="transcript-text">You can call me Erik.</span></div>
    <div class="transcript-line" data-begin="28.17"><span class="transcript-timestamp">0:28</span><span
            class="transcript-text">We have two TAs, Tom
            Morgan and Justin Zhang.</span></div>
    <div class="transcript-line" data-begin="31.6"><span class="transcript-timestamp">0:31</span><span
            class="transcript-text">Tom's back there.</span></div>
    <div class="transcript-line" data-begin="32.9"><span class="transcript-timestamp">0:32</span><span
            class="transcript-text">Justin is late.</span></div>
    <div class="transcript-line" data-begin="36.26"><span class="transcript-timestamp">0:36</span><span
            class="transcript-text">And this class is
            about all kinds</span></div>
    <div class="transcript-line" data-begin="38.6"><span class="transcript-timestamp">0:38</span><span
            class="transcript-text">of very cool data structures.</span></div>
    <div class="transcript-line" data-begin="40.567"><span class="transcript-timestamp">0:40</span><span
            class="transcript-text">You should have already
            seen basic data structures</span></div>
    <div class="transcript-line" data-begin="42.65"><span class="transcript-timestamp">0:42</span><span
            class="transcript-text">like balance binary
            search trees and things</span></div>
    <div class="transcript-line" data-begin="45.2"><span class="transcript-timestamp">0:45</span><span
            class="transcript-text">like that, log n
            time to do wherever</span></div>
    <div class="transcript-line" data-begin="48.14"><span class="transcript-timestamp">0:48</span><span
            class="transcript-text">you want in one dimension.</span></div>
    <div class="transcript-line" data-begin="50.06"><span class="transcript-timestamp">0:50</span><span
            class="transcript-text">And here we're going to turn
            all those data structures</span></div>
    <div class="transcript-line" data-begin="52.31"><span class="transcript-timestamp">0:52</span><span
            class="transcript-text">on their head and
            consider them in all sorts</span></div>
    <div class="transcript-line" data-begin="54.143"><span class="transcript-timestamp">0:54</span><span
            class="transcript-text">of different models and
            additional cool problems.</span></div>
    <div class="transcript-line" data-begin="56.93"><span class="transcript-timestamp">0:56</span><span
            class="transcript-text">Today we're going to talk about
            time travel or temporal data</span></div>
    <div class="transcript-line" data-begin="59.63"><span class="transcript-timestamp">0:59</span><span
            class="transcript-text">structures, where
            you're manipulating time</span></div>
    <div class="transcript-line" data-begin="62.77"><span class="transcript-timestamp">1:02</span><span
            class="transcript-text">as any good time
            traveler should.</span></div>
    <div class="transcript-line" data-begin="65.51"><span class="transcript-timestamp">1:05</span><span
            class="transcript-text">Then we'll do geometry where
            we have higher dimensional</span></div>
    <div class="transcript-line" data-begin="67.94"><span class="transcript-timestamp">1:07</span><span
            class="transcript-text">data, more than one dimension.</span></div>
    <div class="transcript-line" data-begin="69.62"><span class="transcript-timestamp">1:09</span><span
            class="transcript-text">Then we'll look at
            a problem called</span></div>
    <div class="transcript-line" data-begin="71.12"><span class="transcript-timestamp">1:11</span><span
            class="transcript-text">dynamic optimality, which is,
            is there one best binary search</span></div>
    <div class="transcript-line" data-begin="74.9"><span class="transcript-timestamp">1:14</span><span
            class="transcript-text">tree that rules them all?</span></div>
    <div class="transcript-line" data-begin="76.642"><span class="transcript-timestamp">1:16</span><span
            class="transcript-text">Then we'll look at something
            called memory hierarchy, which</span></div>
    <div class="transcript-line" data-begin="79.1"><span class="transcript-timestamp">1:19</span><span
            class="transcript-text">is a way to model more realistic
            computers which have cache</span></div>
    <div class="transcript-line" data-begin="82.58"><span class="transcript-timestamp">1:22</span><span
            class="transcript-text">and then more cache
            and then main memory</span></div>
    <div class="transcript-line" data-begin="84.56"><span class="transcript-timestamp">1:24</span><span
            class="transcript-text">and then dish and all
            these different levels.</span></div>
    <div class="transcript-line" data-begin="86.63"><span class="transcript-timestamp">1:26</span><span
            class="transcript-text">How do you optimize for that?</span></div>
    <div class="transcript-line" data-begin="88.58"><span class="transcript-timestamp">1:28</span><span
            class="transcript-text">Hashing is probably the most
            famous, and most popular,</span></div>
    <div class="transcript-line" data-begin="91.77"><span class="transcript-timestamp">1:31</span><span
            class="transcript-text">most used data structure
            in computer science.</span></div>
    <div class="transcript-line" data-begin="93.67"><span class="transcript-timestamp">1:33</span><span
            class="transcript-text">We'll do a little bit on that.</span></div>
    <div class="transcript-line" data-begin="95.96"><span class="transcript-timestamp">1:35</span><span
            class="transcript-text">Integers, when you know that
            your data is integers and not</span></div>
    <div class="transcript-line" data-begin="99.05"><span class="transcript-timestamp">1:39</span><span
            class="transcript-text">just arbitrary black boxes that
            you can compare or do whatever,</span></div>
    <div class="transcript-line" data-begin="102.147"><span class="transcript-timestamp">1:42</span><span
            class="transcript-text">you can do a lot
            better with integers.</span></div>
    <div class="transcript-line" data-begin="103.73"><span class="transcript-timestamp">1:43</span><span
            class="transcript-text">You usually beat log n time.</span></div>
    <div class="transcript-line" data-begin="105.14"><span class="transcript-timestamp">1:45</span><span
            class="transcript-text">Often you can get constant time.</span></div>
    <div class="transcript-line" data-begin="107.1"><span class="transcript-timestamp">1:47</span><span
            class="transcript-text">For example, if you want
            to do priority queues,</span></div>
    <div class="transcript-line" data-begin="109.13"><span class="transcript-timestamp">1:49</span><span
            class="transcript-text">you can do square
            root log log n time.</span></div>
    <div class="transcript-line" data-begin="111.8"><span class="transcript-timestamp">1:51</span><span
            class="transcript-text">That's the best
            known randomized.</span></div>
    <div class="transcript-line" data-begin="115.1"><span class="transcript-timestamp">1:55</span><span
            class="transcript-text">Dynamic graphs, you have
            a graph you want to store,</span></div>
    <div class="transcript-line" data-begin="118.01"><span class="transcript-timestamp">1:58</span><span
            class="transcript-text">and the edges are being added
            and maybe deleted, like you're</span></div>
    <div class="transcript-line" data-begin="121.44"><span class="transcript-timestamp">2:01</span><span
            class="transcript-text">representing a social network.</span></div>
    <div class="transcript-line" data-begin="122.69"><span class="transcript-timestamp">2:02</span><span
            class="transcript-text">And people are friending
            and de-friending.</span></div>
    <div class="transcript-line" data-begin="124.04"><span class="transcript-timestamp">2:04</span><span
            class="transcript-text">You want to maintain some
            interesting information</span></div>
    <div class="transcript-line" data-begin="126.081"><span class="transcript-timestamp">2:06</span><span
            class="transcript-text">about that graph.</span></div>
    <div class="transcript-line" data-begin="127.76"><span class="transcript-timestamp">2:07</span><span
            class="transcript-text">Strings, you have
            a piece of text,</span></div>
    <div class="transcript-line" data-begin="130.669"><span class="transcript-timestamp">2:10</span><span
            class="transcript-text">such as the entire
            worldwide web.</span></div>
    <div class="transcript-line" data-begin="132.555"><span class="transcript-timestamp">2:12</span><span
            class="transcript-text">And you want to search
            for a substring.</span></div>
    <div class="transcript-line" data-begin="134.18"><span class="transcript-timestamp">2:14</span><span
            class="transcript-text">How do you do that efficiently?</span></div>
    <div class="transcript-line" data-begin="135.54"><span class="transcript-timestamp">2:15</span><span
            class="transcript-text">It's sort of the Google problem.</span></div>
    <div class="transcript-line" data-begin="137.42"><span class="transcript-timestamp">2:17</span><span
            class="transcript-text">Or you searching through
            DNA for patterns, whenever.</span></div>
    <div class="transcript-line" data-begin="140.54"><span class="transcript-timestamp">2:20</span><span
            class="transcript-text">And finally succinct
            data structures,</span></div>
    <div class="transcript-line" data-begin="142.35"><span class="transcript-timestamp">2:22</span><span
            class="transcript-text">which is all about
            taking what we normally</span></div>
    <div class="transcript-line" data-begin="144.17"><span class="transcript-timestamp">2:24</span><span
            class="transcript-text">consider optimal
            space or n space</span></div>
    <div class="transcript-line" data-begin="146.66"><span class="transcript-timestamp">2:26</span><span
            class="transcript-text">and reducing it down to the very
            bare minimum of bits of space.</span></div>
    <div class="transcript-line" data-begin="150.44"><span class="transcript-timestamp">2:30</span><span
            class="transcript-text">Usually if you want
            to store something</span></div>
    <div class="transcript-line" data-begin="152.745"><span class="transcript-timestamp">2:32</span><span
            class="transcript-text">where there's 2 to
            the n possibilities,</span></div>
    <div class="transcript-line" data-begin="154.37"><span class="transcript-timestamp">2:34</span><span
            class="transcript-text">you want to get away
            with n bits of space,</span></div>
    <div class="transcript-line" data-begin="156.62"><span class="transcript-timestamp">2:36</span><span
            class="transcript-text">maybe plus square root of
            n or something very tiny.</span></div>
    <div class="transcript-line" data-begin="160.03"><span class="transcript-timestamp">2:40</span><span
            class="transcript-text">So that's the sync
            data structures.</span></div>
    <div class="transcript-line" data-begin="162.74"><span class="transcript-timestamp">2:42</span><span
            class="transcript-text">So that's an overview
            of the entire class.</span></div>
    <div class="transcript-line" data-begin="164.79"><span class="transcript-timestamp">2:44</span><span
            class="transcript-text">And these are sort of the
            sections we'll be following.</span></div>
    <div class="transcript-line" data-begin="167.97"><span class="transcript-timestamp">2:47</span><span
            class="transcript-text">Let me give you a quick
            administrative overview</span></div>
    <div class="transcript-line" data-begin="170.93"><span class="transcript-timestamp">2:50</span><span
            class="transcript-text">of what we're doing.</span></div>
    <div class="transcript-line" data-begin="174.35"><span class="transcript-timestamp">2:54</span><span
            class="transcript-text">Requirements for the class--</span></div>
    <div class="transcript-line" data-begin="175.52"><span class="transcript-timestamp">2:55</span><span
            class="transcript-text">I guess, first,
            attending lecture.</span></div>
    <div class="transcript-line" data-begin="178.317"><span class="transcript-timestamp">2:58</span><span
            class="transcript-text">Obviously if you
            don't attend lecture,</span></div>
    <div class="transcript-line" data-begin="179.9"><span class="transcript-timestamp">2:59</span><span
            class="transcript-text">there'll be videos online.</span></div>
    <div class="transcript-line" data-begin="180.983"><span class="transcript-timestamp">3:00</span><span
            class="transcript-text">So that's resolvable.</span></div>
    <div class="transcript-line" data-begin="182.81"><span class="transcript-timestamp">3:02</span><span
            class="transcript-text">But let me know if you're
            not going to make it.</span></div>
    <div class="transcript-line" data-begin="185"><span class="transcript-timestamp">3:05</span><span
            class="transcript-text">We're going to have problems
            sets roughly every week.</span></div>
    <div class="transcript-line" data-begin="187.41"><span class="transcript-timestamp">3:07</span><span
            class="transcript-text">If you're taking the
            class for credit,</span></div>
    <div class="transcript-line" data-begin="189.39"><span class="transcript-timestamp">3:09</span><span
            class="transcript-text">they have a very simple rule
            of one page in, one page out.</span></div>
    <div class="transcript-line" data-begin="192.5"><span class="transcript-timestamp">3:12</span><span
            class="transcript-text">This is more constraint on
            us to write problems that</span></div>
    <div class="transcript-line" data-begin="195.29"><span class="transcript-timestamp">3:15</span><span
            class="transcript-text">have easy or short answers.</span></div>
    <div class="transcript-line" data-begin="196.719"><span class="transcript-timestamp">3:16</span><span
            class="transcript-text">You probably need
            to think about them</span></div>
    <div class="transcript-line" data-begin="198.26"><span class="transcript-timestamp">3:18</span><span
            class="transcript-text">a little bit before they're
            transparent, but then easy</span></div>
    <div class="transcript-line" data-begin="201.41"><span class="transcript-timestamp">3:21</span><span
            class="transcript-text">to write up.</span></div>
    <div class="transcript-line" data-begin="203.06"><span class="transcript-timestamp">3:23</span><span
            class="transcript-text">And then scribing lectures--
            so we have a scribe for today,</span></div>
    <div class="transcript-line" data-begin="206.43"><span class="transcript-timestamp">3:26</span><span
            class="transcript-text">I hope.</span></div>
    <div class="transcript-line" data-begin="207.58"><span class="transcript-timestamp">3:27</span><span
            class="transcript-text">Here?</span></div>
    <div class="transcript-line" data-begin="208.55"><span class="transcript-timestamp">3:28</span><span
            class="transcript-text">Yes, good.</span></div>
    <div class="transcript-line" data-begin="210.17"><span class="transcript-timestamp">3:30</span><span
            class="transcript-text">So most of the
            lectures have already</span></div>
    <div class="transcript-line" data-begin="212.21"><span class="transcript-timestamp">3:32</span><span
            class="transcript-text">been scribed in some
            version, and your goal</span></div>
    <div class="transcript-line" data-begin="214.58"><span class="transcript-timestamp">3:34</span><span
            class="transcript-text">is to revise that scribe
            notes that if you don't like</span></div>
    <div class="transcript-line" data-begin="218.42"><span class="transcript-timestamp">3:38</span><span
            class="transcript-text">handwritten notes, which
            are also online, then easier</span></div>
    <div class="transcript-line" data-begin="222.11"><span class="transcript-timestamp">3:42</span><span
            class="transcript-text">for people to read.</span></div>
    <div class="transcript-line" data-begin="224.32"><span class="transcript-timestamp">3:44</span><span
            class="transcript-text">Let's see.</span></div>
    <div class="transcript-line" data-begin="225.16"><span class="transcript-timestamp">3:45</span><span
            class="transcript-text">Listeners welcome.</span></div>
    <div class="transcript-line" data-begin="226.187"><span class="transcript-timestamp">3:46</span><span
            class="transcript-text">We're going to have an
            open problem session.</span></div>
    <div class="transcript-line" data-begin="228.02"><span class="transcript-timestamp">3:48</span><span
            class="transcript-text">I really like open problems.</span></div>
    <div class="transcript-line" data-begin="229.23"><span class="transcript-timestamp">3:49</span><span
            class="transcript-text">I really like solving
            open problems.</span></div>
    <div class="transcript-line" data-begin="230.73"><span class="transcript-timestamp">3:50</span><span
            class="transcript-text">So we've done this every time
            this class has been offered.</span></div>
    <div class="transcript-line" data-begin="233.54"><span class="transcript-timestamp">3:53</span><span
            class="transcript-text">So if you're interested in
            also solving open problems,</span></div>
    <div class="transcript-line" data-begin="235.79"><span class="transcript-timestamp">3:55</span><span
            class="transcript-text">it's optional.</span></div>
    <div class="transcript-line" data-begin="236.91"><span class="transcript-timestamp">3:56</span><span
            class="transcript-text">I will organize-- in
            a couple of weeks,</span></div>
    <div class="transcript-line" data-begin="239.48"><span class="transcript-timestamp">3:59</span><span
            class="transcript-text">we'll have a weekly
            open problem session</span></div>
    <div class="transcript-line" data-begin="243.11"><span class="transcript-timestamp">4:03</span><span
            class="transcript-text">and try to solve
            all the things that</span></div>
    <div class="transcript-line" data-begin="246.44"><span class="transcript-timestamp">4:06</span><span
            class="transcript-text">push the frontier of
            advanced data structures.</span></div>
    <div class="transcript-line" data-begin="249.08"><span class="transcript-timestamp">4:09</span><span
            class="transcript-text">So in classes, we'll see
            the state of the art.</span></div>
    <div class="transcript-line" data-begin="251.81"><span class="transcript-timestamp">4:11</span><span
            class="transcript-text">And then we'll change the state
            of the art in those sessions.</span></div>
    <div class="transcript-line" data-begin="255.671"><span class="transcript-timestamp">4:15</span><span
            class="transcript-text">I think that's it.</span></div>
    <div class="transcript-line" data-begin="256.42"><span class="transcript-timestamp">4:16</span><span
            class="transcript-text">Any questions about
            the class before we</span></div>
    <div class="transcript-line" data-begin="258.92"><span class="transcript-timestamp">4:18</span><span
            class="transcript-text">get into the fun stuff?</span></div>
    <div class="transcript-line" data-begin="262.98"><span class="transcript-timestamp">4:22</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="263.9"><span class="transcript-timestamp">4:23</span><span
            class="transcript-text">Let's do some time traveling.</span></div>
    <div class="transcript-line" data-begin="267.142"><span class="transcript-timestamp">4:27</span><span
            class="transcript-text">Before I get to time
            traveling, though, I</span></div>
    <div class="transcript-line" data-begin="268.85"><span class="transcript-timestamp">4:28</span><span
            class="transcript-text">need to define our
            model of computation.</span></div>
    <div class="transcript-line" data-begin="272.42"><span class="transcript-timestamp">4:32</span><span
            class="transcript-text">A theme in this class is that
            the model of computation you're</span></div>
    <div class="transcript-line" data-begin="275.716"><span class="transcript-timestamp">4:35</span><span
            class="transcript-text">working with matters.</span></div>
    <div class="transcript-line" data-begin="276.59"><span class="transcript-timestamp">4:36</span><span
            class="transcript-text">Models matter.</span></div>
    <div class="transcript-line" data-begin="278.06"><span class="transcript-timestamp">4:38</span><span
            class="transcript-text">And there's lots of different
            models of computation.</span></div>
    <div class="transcript-line" data-begin="280.43"><span class="transcript-timestamp">4:40</span><span
            class="transcript-text">We'll see a few of the
            main ones in this class.</span></div>
    <div class="transcript-line" data-begin="285.89"><span class="transcript-timestamp">4:45</span><span
            class="transcript-text">And the starting
            point, and the one</span></div>
    <div class="transcript-line" data-begin="288.58"><span class="transcript-timestamp">4:48</span><span
            class="transcript-text">we'll be using throughout today,
            is called a pointer machine.</span></div>
    <div class="transcript-line" data-begin="293.1"><span class="transcript-timestamp">4:53</span><span
            class="transcript-text">It's an old one from the '80s.</span></div>
    <div class="transcript-line" data-begin="297.24"><span class="transcript-timestamp">4:57</span><span
            class="transcript-text">And it corresponds to
            what you might think about</span></div>
    <div class="transcript-line" data-begin="299.24"><span class="transcript-timestamp">4:59</span><span
            class="transcript-text">if you've done a lot of
            object-oriented programming,</span></div>
    <div class="transcript-line" data-begin="302.09"><span class="transcript-timestamp">5:02</span><span
            class="transcript-text">and before that,
            structure-oriented programming,</span></div>
    <div class="transcript-line" data-begin="304.95"><span class="transcript-timestamp">5:04</span><span
            class="transcript-text">I guess.</span></div>
    <div class="transcript-line" data-begin="305.76"><span class="transcript-timestamp">5:05</span><span
            class="transcript-text">So you have a bunch of nodes.</span></div>
    <div class="transcript-line" data-begin="308.66"><span class="transcript-timestamp">5:08</span><span
            class="transcript-text">They have some fields in them,
            a constant number of fields.</span></div>
    <div class="transcript-line" data-begin="313.97"><span class="transcript-timestamp">5:13</span><span
            class="transcript-text">You can think of these
            as objects or strucs</span></div>
    <div class="transcript-line" data-begin="316.61"><span class="transcript-timestamp">5:16</span><span
            class="transcript-text">in c It used to be records
            back in Pascal days,</span></div>
    <div class="transcript-line" data-begin="320.27"><span class="transcript-timestamp">5:20</span><span
            class="transcript-text">so a lot of the papers
            call them records.</span></div>
    <div class="transcript-line" data-begin="322.17"><span class="transcript-timestamp">5:22</span><span
            class="transcript-text">You could just have a
            constant number of fields.</span></div>
    <div class="transcript-line" data-begin="324.17"><span class="transcript-timestamp">5:24</span><span
            class="transcript-text">You could think of
            those numbered, labeled.</span></div>
    <div class="transcript-line" data-begin="325.3"><span class="transcript-timestamp">5:25</span><span
            class="transcript-text">It doesn't really matter
            because there's only</span></div>
    <div class="transcript-line" data-begin="327.175"><span class="transcript-timestamp">5:27</span><span
            class="transcript-text">a constant number of them.</span></div>
    <div class="transcript-line" data-begin="328.55"><span class="transcript-timestamp">5:28</span><span
            class="transcript-text">Each of the fields could be
            a pointer to another node,</span></div>
    <div class="transcript-line" data-begin="332.24"><span class="transcript-timestamp">5:32</span><span
            class="transcript-text">could be a null pointer, or
            could have some data in it.</span></div>
    <div class="transcript-line" data-begin="335.55"><span class="transcript-timestamp">5:35</span><span
            class="transcript-text">So I'll just assume that
            all my data is integers.</span></div>
    <div class="transcript-line" data-begin="343.13"><span class="transcript-timestamp">5:43</span><span
            class="transcript-text">You can have a
            pointer to yourself.</span></div>
    <div class="transcript-line" data-begin="345.09"><span class="transcript-timestamp">5:45</span><span
            class="transcript-text">You can have a pointer over
            here, whatever you want.</span></div>
    <div class="transcript-line" data-begin="348.44"><span class="transcript-timestamp">5:48</span><span
            class="transcript-text">A pointer machine would
            look something like this.</span></div>
    <div class="transcript-line" data-begin="352.64"><span class="transcript-timestamp">5:52</span><span
            class="transcript-text">In any moment, this is the
            state of the pointer machine.</span></div>
    <div class="transcript-line" data-begin="355.04"><span class="transcript-timestamp">5:55</span><span
            class="transcript-text">So you think this as the memory
            of your computer storing.</span></div>
    <div class="transcript-line" data-begin="359.3"><span class="transcript-timestamp">5:59</span><span
            class="transcript-text">And then you have
            some operations</span></div>
    <div class="transcript-line" data-begin="362.21"><span class="transcript-timestamp">6:02</span><span
            class="transcript-text">that you're allowed to do.</span></div>
    <div class="transcript-line" data-begin="363.66"><span class="transcript-timestamp">6:03</span><span
            class="transcript-text">That's the computation
            part of the model.</span></div>
    <div class="transcript-line" data-begin="367.8"><span class="transcript-timestamp">6:07</span><span
            class="transcript-text">You can think of this
            as the memory model.</span></div>
    <div class="transcript-line" data-begin="370.57"><span class="transcript-timestamp">6:10</span><span
            class="transcript-text">What you're allowed to
            do are create nodes.</span></div>
    <div class="transcript-line" data-begin="373.1"><span class="transcript-timestamp">6:13</span><span
            class="transcript-text">You can say something
            like, x equals new node.</span></div>
    <div class="transcript-line" data-begin="379.91"><span class="transcript-timestamp">6:19</span><span
            class="transcript-text">You can, I don't
            know, look at fields.</span></div>
    <div class="transcript-line" data-begin="384.99"><span class="transcript-timestamp">6:24</span><span
            class="transcript-text">You can do x equals y.field.</span></div>
    <div class="transcript-line" data-begin="388.07"><span class="transcript-timestamp">6:28</span><span
            class="transcript-text">You can set fields,
            x.field equals y.</span></div>
    <div class="transcript-line" data-begin="393.56"><span class="transcript-timestamp">6:33</span><span
            class="transcript-text">You can compute on these
            data, so you can add 5 and 7,</span></div>
    <div class="transcript-line" data-begin="397.4"><span class="transcript-timestamp">6:37</span><span
            class="transcript-text">do things like that.</span></div>
    <div class="transcript-line" data-begin="399.11"><span class="transcript-timestamp">6:39</span><span
            class="transcript-text">I'm not going to worry about--</span></div>
    <div class="transcript-line" data-begin="400.99"><span class="transcript-timestamp">6:40</span><span
            class="transcript-text">I'll just write et cetera.</span></div>
    <div class="transcript-line" data-begin="403.7"><span class="transcript-timestamp">6:43</span><span
            class="transcript-text">This is more a model
            about how everything's</span></div>
    <div class="transcript-line" data-begin="405.68"><span class="transcript-timestamp">6:45</span><span
            class="transcript-text">organized in memory, not so
            much about what you're allowed</span></div>
    <div class="transcript-line" data-begin="408.38"><span class="transcript-timestamp">6:48</span><span
            class="transcript-text">to do to the data items.</span></div>
    <div class="transcript-line" data-begin="409.62"><span class="transcript-timestamp">6:49</span><span
            class="transcript-text">In this lecture, it
            won't matter what</span></div>
    <div class="transcript-line" data-begin="410.87"><span class="transcript-timestamp">6:50</span><span
            class="transcript-text">you're doing to the data items.</span></div>
    <div class="transcript-line" data-begin="412.161"><span class="transcript-timestamp">6:52</span><span
            class="transcript-text">We never touch them.</span></div>
    <div class="transcript-line" data-begin="413.93"><span class="transcript-timestamp">6:53</span><span
            class="transcript-text">We just copy them around.</span></div>
    <div class="transcript-line" data-begin="416.84"><span class="transcript-timestamp">6:56</span><span
            class="transcript-text">So am I missing anything?</span></div>
    <div class="transcript-line" data-begin="419.87"><span class="transcript-timestamp">6:59</span><span
            class="transcript-text">Probably.</span></div>
    <div class="transcript-line" data-begin="421.1"><span class="transcript-timestamp">7:01</span><span
            class="transcript-text">I guess you could destroy
            nodes if you felt like it.</span></div>
    <div class="transcript-line" data-begin="423.95"><span class="transcript-timestamp">7:03</span><span
            class="transcript-text">But we won't have
            to today, because we</span></div>
    <div class="transcript-line" data-begin="426.566"><span class="transcript-timestamp">7:06</span><span
            class="transcript-text">don't want to
            throw anything away</span></div>
    <div class="transcript-line" data-begin="427.94"><span class="transcript-timestamp">7:07</span><span
            class="transcript-text">when you're time traveling.</span></div>
    <div class="transcript-line" data-begin="429.2"><span class="transcript-timestamp">7:09</span><span
            class="transcript-text">It's too dangerous.</span></div>
    <div class="transcript-line" data-begin="432.74"><span class="transcript-timestamp">7:12</span><span
            class="transcript-text">And then the one catch
            here is, what are x and y?</span></div>
    <div class="transcript-line" data-begin="438.57"><span class="transcript-timestamp">7:18</span><span
            class="transcript-text">There's going to be one
            node in this data structure</span></div>
    <div class="transcript-line" data-begin="441.28"><span class="transcript-timestamp">7:21</span><span
            class="transcript-text">or in your memory
            called the root node.</span></div>
    <div class="transcript-line" data-begin="444.184"><span class="transcript-timestamp">7:24</span><span
            class="transcript-text">And you could think of that
            as that's the thing you always</span></div>
    <div class="transcript-line" data-begin="446.6"><span class="transcript-timestamp">7:26</span><span
            class="transcript-text">have in your head.</span></div>
    <div class="transcript-line" data-begin="447.8"><span class="transcript-timestamp">7:27</span><span
            class="transcript-text">This is like your
            cache, if you will.</span></div>
    <div class="transcript-line" data-begin="449.39"><span class="transcript-timestamp">7:29</span><span
            class="transcript-text">It's just got a constant
            number of things, just</span></div>
    <div class="transcript-line" data-begin="451.348"><span class="transcript-timestamp">7:31</span><span
            class="transcript-text">like any other node.</span></div>
    <div class="transcript-line" data-begin="452.47"><span class="transcript-timestamp">7:32</span><span
            class="transcript-text">And x and y are
            fields of the root.</span></div>
    <div class="transcript-line" data-begin="460.52"><span class="transcript-timestamp">7:40</span><span
            class="transcript-text">So that sort of
            ties things down.</span></div>
    <div class="transcript-line" data-begin="462.53"><span class="transcript-timestamp">7:42</span><span
            class="transcript-text">You're always working
            relative to the root.</span></div>
    <div class="transcript-line" data-begin="465.2"><span class="transcript-timestamp">7:45</span><span
            class="transcript-text">But you can look at the data,
            basically follow this pointer,</span></div>
    <div class="transcript-line" data-begin="470.03"><span class="transcript-timestamp">7:50</span><span
            class="transcript-text">by looking at the field.</span></div>
    <div class="transcript-line" data-begin="473.04"><span class="transcript-timestamp">7:53</span><span
            class="transcript-text">You could set one
            of these pointers--</span></div>
    <div class="transcript-line" data-begin="475.85"><span class="transcript-timestamp">7:55</span><span
            class="transcript-text">I think I probably need
            another operation here,</span></div>
    <div class="transcript-line" data-begin="478.16"><span class="transcript-timestamp">7:58</span><span
            class="transcript-text">like x equals y.field1,
            field2, that sort of thing,</span></div>
    <div class="transcript-line" data-begin="483.936"><span class="transcript-timestamp">8:03</span><span
            class="transcript-text">and maybe the reverse.</span></div>
    <div class="transcript-line" data-begin="486.8"><span class="transcript-timestamp">8:06</span><span
            class="transcript-text">But you can manipulate
            all nodes sort</span></div>
    <div class="transcript-line" data-begin="489.2"><span class="transcript-timestamp">8:09</span><span
            class="transcript-text">of via the root is the idea.</span></div>
    <div class="transcript-line" data-begin="490.77"><span class="transcript-timestamp">8:10</span><span
            class="transcript-text">You follow pointers,
            do whatever.</span></div>
    <div class="transcript-line" data-begin="492.71"><span class="transcript-timestamp">8:12</span><span
            class="transcript-text">So pretty obvious,
            slightly annoying</span></div>
    <div class="transcript-line" data-begin="494.78"><span class="transcript-timestamp">8:14</span><span
            class="transcript-text">to write down formally.</span></div>
    <div class="transcript-line" data-begin="496.25"><span class="transcript-timestamp">8:16</span><span
            class="transcript-text">But that is pointer machine.</span></div>
    <div class="transcript-line" data-begin="503.46"><span class="transcript-timestamp">8:23</span><span
            class="transcript-text">And what we're going to
            be talking about today</span></div>
    <div class="transcript-line" data-begin="506.32"><span class="transcript-timestamp">8:26</span><span
            class="transcript-text">in time travel is
            suppose someone</span></div>
    <div class="transcript-line" data-begin="508.829"><span class="transcript-timestamp">8:28</span><span
            class="transcript-text">gives me a pointer machine
            data structure, for example,</span></div>
    <div class="transcript-line" data-begin="511.12"><span class="transcript-timestamp">8:31</span><span
            class="transcript-text">balanced binary search
            tree, linked list.</span></div>
    <div class="transcript-line" data-begin="513.51"><span class="transcript-timestamp">8:33</span><span
            class="transcript-text">A lot of data structures,
            especially classic data</span></div>
    <div class="transcript-line" data-begin="516.03"><span class="transcript-timestamp">8:36</span><span
            class="transcript-text">structures, follow
            pointer machine model.</span></div>
    <div class="transcript-line" data-begin="519.192"><span class="transcript-timestamp">8:39</span><span
            class="transcript-text">What we'd like to do is
            transform that data structure</span></div>
    <div class="transcript-line" data-begin="521.4"><span class="transcript-timestamp">8:41</span><span
            class="transcript-text">or make a new
            pointer machine data</span></div>
    <div class="transcript-line" data-begin="522.816"><span class="transcript-timestamp">8:42</span><span
            class="transcript-text">structure that does
            extra cool things,</span></div>
    <div class="transcript-line" data-begin="525.12"><span class="transcript-timestamp">8:45</span><span
            class="transcript-text">namely travel through time.</span></div>
    <div class="transcript-line" data-begin="527.47"><span class="transcript-timestamp">8:47</span><span
            class="transcript-text">So that's what
            we're going to do.</span></div>
    <div class="transcript-line" data-begin="533.34"><span class="transcript-timestamp">8:53</span><span
            class="transcript-text">There's two senses of time
            travel or temporal data</span></div>
    <div class="transcript-line" data-begin="537.87"><span class="transcript-timestamp">8:57</span><span
            class="transcript-text">structures that we're going
            to cover in this class.</span></div>
    <div class="transcript-line" data-begin="542.2"><span class="transcript-timestamp">9:02</span><span
            class="transcript-text">The one for today is
            called persistence,</span></div>
    <div class="transcript-line" data-begin="545.4"><span class="transcript-timestamp">9:05</span><span
            class="transcript-text">where you don't forget
            anything, like an elephant.</span></div>
    <div class="transcript-line" data-begin="548.31"><span class="transcript-timestamp">9:08</span><span
            class="transcript-text">And the other one
            is retroactivity.</span></div>
    <div class="transcript-line" data-begin="555.24"><span class="transcript-timestamp">9:15</span><span
            class="transcript-text">Persistence will be today.</span></div>
    <div class="transcript-line" data-begin="556.8"><span class="transcript-timestamp">9:16</span><span
            class="transcript-text">Retroactivity is next class.</span></div>
    <div class="transcript-line" data-begin="559.26"><span class="transcript-timestamp">9:19</span><span
            class="transcript-text">Basically, these correspond
            to two models of time travel.</span></div>
    <div class="transcript-line" data-begin="561.67"><span class="transcript-timestamp">9:21</span><span
            class="transcript-text">Persistence is the branching
            universe time travel model,</span></div>
    <div class="transcript-line" data-begin="564.176"><span class="transcript-timestamp">9:24</span><span
            class="transcript-text">where if you make a
            change in the past,</span></div>
    <div class="transcript-line" data-begin="565.8"><span class="transcript-timestamp">9:25</span><span
            class="transcript-text">you get a new universe.</span></div>
    <div class="transcript-line" data-begin="567.35"><span class="transcript-timestamp">9:27</span><span
            class="transcript-text">You never destroy old universes.</span></div>
    <div class="transcript-line" data-begin="569.46"><span class="transcript-timestamp">9:29</span><span
            class="transcript-text">Retroactivity is more
            like Back to the Future,</span></div>
    <div class="transcript-line" data-begin="573.255"><span class="transcript-timestamp">9:33</span><span
            class="transcript-text">when you go back, make
            a change, and then you</span></div>
    <div class="transcript-line" data-begin="575.13"><span class="transcript-timestamp">9:35</span><span
            class="transcript-text">can return to the present
            and see what happened.</span></div>
    <div class="transcript-line" data-begin="577.92"><span class="transcript-timestamp">9:37</span><span
            class="transcript-text">This is a lot harder to do.</span></div>
    <div class="transcript-line" data-begin="579.71"><span class="transcript-timestamp">9:39</span><span
            class="transcript-text">And we'll work on
            that next class.</span></div>
    <div class="transcript-line" data-begin="582.15"><span class="transcript-timestamp">9:42</span><span
            class="transcript-text">Persistence is what
            we will do today.</span></div>
    <div class="transcript-line" data-begin="586.36"><span class="transcript-timestamp">9:46</span><span
            class="transcript-text">So persistence.</span></div>
    <div class="transcript-line" data-begin="597.94"><span class="transcript-timestamp">9:57</span><span
            class="transcript-text">The general idea of persistence
            is to remember everything--</span></div>
    <div class="transcript-line" data-begin="601.81"><span class="transcript-timestamp">10:01</span><span
            class="transcript-text">the general goal, I would say.</span></div>
    <div class="transcript-line" data-begin="605.11"><span class="transcript-timestamp">10:05</span><span
            class="transcript-text">And by everything, I
            mean different versions</span></div>
    <div class="transcript-line" data-begin="607.36"><span class="transcript-timestamp">10:07</span><span
            class="transcript-text">of the data structure.</span></div>
    <div class="transcript-line" data-begin="608.8"><span class="transcript-timestamp">10:08</span><span
            class="transcript-text">So you're doing data
            structures in general.</span></div>
    <div class="transcript-line" data-begin="611.29"><span class="transcript-timestamp">10:11</span><span
            class="transcript-text">We have update operations
            and query operations.</span></div>
    <div class="transcript-line" data-begin="614.55"><span class="transcript-timestamp">10:14</span><span
            class="transcript-text">We're mainly concerned
            about updates here.</span></div>
    <div class="transcript-line" data-begin="616.387"><span class="transcript-timestamp">10:16</span><span
            class="transcript-text">Every time you do an
            update, you think of it</span></div>
    <div class="transcript-line" data-begin="618.22"><span class="transcript-timestamp">10:18</span><span
            class="transcript-text">as taking a version of the data
            structure and making a new one.</span></div>
    <div class="transcript-line" data-begin="621.73"><span class="transcript-timestamp">10:21</span><span
            class="transcript-text">And you never want to
            destroy old versions.</span></div>
    <div class="transcript-line" data-begin="623.8"><span class="transcript-timestamp">10:23</span><span
            class="transcript-text">So even though an update
            like an insert or something</span></div>
    <div class="transcript-line" data-begin="626.23"><span class="transcript-timestamp">10:26</span><span
            class="transcript-text">changes the data structure, we
            want to remember that past data</span></div>
    <div class="transcript-line" data-begin="629.23"><span class="transcript-timestamp">10:29</span><span
            class="transcript-text">as well.</span></div>
    <div class="transcript-line" data-begin="630.77"><span class="transcript-timestamp">10:30</span><span
            class="transcript-text">And then let's make
            this reasonable.</span></div>
    <div class="transcript-line" data-begin="634.03"><span class="transcript-timestamp">10:34</span><span
            class="transcript-text">All data structure operations
            are relative to a specified</span></div>
    <div class="transcript-line" data-begin="637.791"><span class="transcript-timestamp">10:37</span><span
            class="transcript-text">version.</span></div>
    <div class="transcript-line" data-begin="647.2"><span class="transcript-timestamp">10:47</span><span
            class="transcript-text">So an update makes and
            returns a new version.</span></div>
    <div class="transcript-line" data-begin="665.69"><span class="transcript-timestamp">11:05</span><span
            class="transcript-text">So when you do an
            insert, you specify</span></div>
    <div class="transcript-line" data-begin="668.75"><span class="transcript-timestamp">11:08</span><span
            class="transcript-text">a version of your data
            structure and the thing</span></div>
    <div class="transcript-line" data-begin="670.85"><span class="transcript-timestamp">11:10</span><span
            class="transcript-text">you want to insert.</span></div>
    <div class="transcript-line" data-begin="671.96"><span class="transcript-timestamp">11:11</span><span
            class="transcript-text">And the output is a new version.</span></div>
    <div class="transcript-line" data-begin="673.85"><span class="transcript-timestamp">11:13</span><span
            class="transcript-text">So then you could insert into
            that new version, keep going,</span></div>
    <div class="transcript-line" data-begin="676.55"><span class="transcript-timestamp">11:16</span><span
            class="transcript-text">or maybe go back to the
            old version, modify that.</span></div>
    <div class="transcript-line" data-begin="680.21"><span class="transcript-timestamp">11:20</span><span
            class="transcript-text">I haven't said exactly
            what's allowed here,</span></div>
    <div class="transcript-line" data-begin="682.45"><span class="transcript-timestamp">11:22</span><span
            class="transcript-text">but this is sort of
            the general goal.</span></div>
    <div class="transcript-line" data-begin="685.46"><span class="transcript-timestamp">11:25</span><span
            class="transcript-text">And then there are four
            levels of persistence</span></div>
    <div class="transcript-line" data-begin="690.95"><span class="transcript-timestamp">11:30</span><span
            class="transcript-text">that you might want to get.</span></div>
    <div class="transcript-line" data-begin="693.02"><span class="transcript-timestamp">11:33</span><span
            class="transcript-text">First level is called
            partial persistence.</span></div>
    <div class="transcript-line" data-begin="697.44"><span class="transcript-timestamp">11:37</span><span
            class="transcript-text">This is the easiest to obtain.</span></div>
    <div class="transcript-line" data-begin="704.3"><span class="transcript-timestamp">11:44</span><span
            class="transcript-text">And in partial
            persistence, you're</span></div>
    <div class="transcript-line" data-begin="707.63"><span class="transcript-timestamp">11:47</span><span
            class="transcript-text">only allowed to update
            the latest version, which</span></div>
    <div class="transcript-line" data-begin="715.46"><span class="transcript-timestamp">11:55</span><span
            class="transcript-text">means the versions
            are linearly ordered.</span></div>
    <div class="transcript-line" data-begin="721.67"><span class="transcript-timestamp">12:01</span><span
            class="transcript-text">This is the easiest
            to think about.</span></div>
    <div class="transcript-line" data-begin="723.77"><span class="transcript-timestamp">12:03</span><span
            class="transcript-text">And time travel can easily get
            confusing, so start simple.</span></div>
    <div class="transcript-line" data-begin="729.3"><span class="transcript-timestamp">12:09</span><span
            class="transcript-text">We have a timeline of
            various versions on it.</span></div>
    <div class="transcript-line" data-begin="734.78"><span class="transcript-timestamp">12:14</span><span
            class="transcript-text">This is the latest.</span></div>
    <div class="transcript-line" data-begin="737.42"><span class="transcript-timestamp">12:17</span><span
            class="transcript-text">And what we can do is
            update that version.</span></div>
    <div class="transcript-line" data-begin="739.85"><span class="transcript-timestamp">12:19</span><span
            class="transcript-text">We'll get a new version, and
            then our latest is this one.</span></div>
    <div class="transcript-line" data-begin="743.75"><span class="transcript-timestamp">12:23</span><span
            class="transcript-text">What this allows is looking back
            at the past to an old version</span></div>
    <div class="transcript-line" data-begin="747.95"><span class="transcript-timestamp">12:27</span><span
            class="transcript-text">and querying that version.</span></div>
    <div class="transcript-line" data-begin="749.282"><span class="transcript-timestamp">12:29</span><span
            class="transcript-text">So you can still ask questions
            about the old version,</span></div>
    <div class="transcript-line" data-begin="751.49"><span class="transcript-timestamp">12:31</span><span
            class="transcript-text">if you want to be able to do
            a search on any of these data</span></div>
    <div class="transcript-line" data-begin="753.83"><span class="transcript-timestamp">12:33</span><span
            class="transcript-text">structures.</span></div>
    <div class="transcript-line" data-begin="754.329"><span class="transcript-timestamp">12:34</span><span
            class="transcript-text">But you can't change them.</span></div>
    <div class="transcript-line" data-begin="755.6"><span class="transcript-timestamp">12:35</span><span
            class="transcript-text">You can only change the
            most recent version.</span></div>
    <div class="transcript-line" data-begin="758.18"><span class="transcript-timestamp">12:38</span><span
            class="transcript-text">So that's nice.</span></div>
    <div class="transcript-line" data-begin="759.47"><span class="transcript-timestamp">12:39</span><span
            class="transcript-text">It's kind of like time
            machine on Mac, I guess.</span></div>
    <div class="transcript-line" data-begin="764.69"><span class="transcript-timestamp">12:44</span><span
            class="transcript-text">If you've ever seen the
            movie Deja Vu, which is not</span></div>
    <div class="transcript-line" data-begin="766.97"><span class="transcript-timestamp">12:46</span><span
            class="transcript-text">very common, but it's
            a good time travel</span></div>
    <div class="transcript-line" data-begin="768.636"><span class="transcript-timestamp">12:48</span><span
            class="transcript-text">movie, in the first half of
            the movie, all they can do</span></div>
    <div class="transcript-line" data-begin="771.5"><span class="transcript-timestamp">12:51</span><span
            class="transcript-text">is look back at the past.</span></div>
    <div class="transcript-line" data-begin="772.55"><span class="transcript-timestamp">12:52</span><span
            class="transcript-text">Later they discover
            that actually they</span></div>
    <div class="transcript-line" data-begin="774.71"><span class="transcript-timestamp">12:54</span><span
            class="transcript-text">have a full persistence model.</span></div>
    <div class="transcript-line" data-begin="777.85"><span class="transcript-timestamp">12:57</span><span
            class="transcript-text">It takes a while
            for dramatic effect.</span></div>
    <div class="transcript-line" data-begin="784.25"><span class="transcript-timestamp">13:04</span><span
            class="transcript-text">In full persistence, you can
            update anything you want--</span></div>
    <div class="transcript-line" data-begin="788.75"><span class="transcript-timestamp">13:08</span><span
            class="transcript-text">so update any version.</span></div>
    <div class="transcript-line" data-begin="798.07"><span class="transcript-timestamp">13:18</span><span
            class="transcript-text">and so then the
            versions form a tree.</span></div>
    <div class="transcript-line" data-begin="807.96"><span class="transcript-timestamp">13:27</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="808.46"><span class="transcript-timestamp">13:28</span><span
            class="transcript-text">So in this model,
            maybe you initially</span></div>
    <div class="transcript-line" data-begin="810.2"><span class="transcript-timestamp">13:30</span><span
            class="transcript-text">have a nice line of versions.</span></div>
    <div class="transcript-line" data-begin="812.42"><span class="transcript-timestamp">13:32</span><span
            class="transcript-text">But now if I go back to
            this version and update it,</span></div>
    <div class="transcript-line" data-begin="814.86"><span class="transcript-timestamp">13:34</span><span
            class="transcript-text">I branch, get a
            new version here.</span></div>
    <div class="transcript-line" data-begin="817.34"><span class="transcript-timestamp">13:37</span><span
            class="transcript-text">And then I might keep modifying
            that version sometimes.</span></div>
    <div class="transcript-line" data-begin="820.4"><span class="transcript-timestamp">13:40</span><span
            class="transcript-text">Any of these guys can branch.</span></div>
    <div class="transcript-line" data-begin="824.24"><span class="transcript-timestamp">13:44</span><span
            class="transcript-text">So this is why I call it the
            branching universe model, when</span></div>
    <div class="transcript-line" data-begin="827.48"><span class="transcript-timestamp">13:47</span><span
            class="transcript-text">you update your branch.</span></div>
    <div class="transcript-line" data-begin="832.52"><span class="transcript-timestamp">13:52</span><span
            class="transcript-text">So no version ever
            gets destroyed here.</span></div>
    <div class="transcript-line" data-begin="834.38"><span class="transcript-timestamp">13:54</span><span
            class="transcript-text">Again, you can
            query all versions.</span></div>
    <div class="transcript-line" data-begin="836.72"><span class="transcript-timestamp">13:56</span><span
            class="transcript-text">But now you can also
            update any version.</span></div>
    <div class="transcript-line" data-begin="839.36"><span class="transcript-timestamp">13:59</span><span
            class="transcript-text">But you just make a new version.</span></div>
    <div class="transcript-line" data-begin="840.71"><span class="transcript-timestamp">14:00</span><span
            class="transcript-text">It's a totally new world.</span></div>
    <div class="transcript-line" data-begin="842.66"><span class="transcript-timestamp">14:02</span><span
            class="transcript-text">When I update this
            version, this version</span></div>
    <div class="transcript-line" data-begin="844.49"><span class="transcript-timestamp">14:04</span><span
            class="transcript-text">knows nothing about all the--</span></div>
    <div class="transcript-line" data-begin="846.41"><span class="transcript-timestamp">14:06</span><span
            class="transcript-text">this doesn't know
            about this future.</span></div>
    <div class="transcript-line" data-begin="847.94"><span class="transcript-timestamp">14:07</span><span
            class="transcript-text">It's created its own future.</span></div>
    <div class="transcript-line" data-begin="850.89"><span class="transcript-timestamp">14:10</span><span
            class="transcript-text">There's no way to sort of
            merge those universes together.</span></div>
    <div class="transcript-line" data-begin="854.31"><span class="transcript-timestamp">14:14</span><span
            class="transcript-text">It's kind of sad.</span></div>
    <div class="transcript-line" data-begin="856.91"><span class="transcript-timestamp">14:16</span><span
            class="transcript-text">That's why we have the
            third level of persistence,</span></div>
    <div class="transcript-line" data-begin="862.22"><span class="transcript-timestamp">14:22</span><span
            class="transcript-text">which lets us merge timelines.</span></div>
    <div class="transcript-line" data-begin="864.68"><span class="transcript-timestamp">14:24</span><span
            class="transcript-text">It's great for lots
            of fiction out there.</span></div>
    <div class="transcript-line" data-begin="875.88"><span class="transcript-timestamp">14:35</span><span
            class="transcript-text">If you've seen the
            old TV show Sliders,</span></div>
    <div class="transcript-line" data-begin="878.36"><span class="transcript-timestamp">14:38</span><span
            class="transcript-text">that would be
            confluent persistence.</span></div>
    <div class="transcript-line" data-begin="890.83"><span class="transcript-timestamp">14:50</span><span
            class="transcript-text">So confluent persistence,
            you can combine two versions</span></div>
    <div class="transcript-line" data-begin="901.79"><span class="transcript-timestamp">15:01</span><span
            class="transcript-text">to create a new version.</span></div>
    <div class="transcript-line" data-begin="909.22"><span class="transcript-timestamp">15:09</span><span
            class="transcript-text">And in this case, again, you
            can't destroy old versions.</span></div>
    <div class="transcript-line" data-begin="913.72"><span class="transcript-timestamp">15:13</span><span
            class="transcript-text">In persistence, you
            never destroy versions.</span></div>
    <div class="transcript-line" data-begin="916.26"><span class="transcript-timestamp">15:16</span><span
            class="transcript-text">So now the versions form a
            DAG, directed acyclic graph.</span></div>
    <div class="transcript-line" data-begin="922.52"><span class="transcript-timestamp">15:22</span><span
            class="transcript-text">So now we're allowing--</span></div>
    <div class="transcript-line" data-begin="924.01"><span class="transcript-timestamp">15:24</span><span
            class="transcript-text">OK, you make some
            changes, whatever.</span></div>
    <div class="transcript-line" data-begin="925.52"><span class="transcript-timestamp">15:25</span><span
            class="transcript-text">You branch your universe,
            make some changes.</span></div>
    <div class="transcript-line" data-begin="930.274"><span class="transcript-timestamp">15:30</span><span
            class="transcript-text">And now I can say, OK, take
            this version of the data</span></div>
    <div class="transcript-line" data-begin="932.44"><span class="transcript-timestamp">15:32</span><span
            class="transcript-text">structure and this version
            and recombine them.</span></div>
    <div class="transcript-line" data-begin="935.51"><span class="transcript-timestamp">15:35</span><span
            class="transcript-text">Get a new version, and then
            maybe make some more changes.</span></div>
    <div class="transcript-line" data-begin="938.73"><span class="transcript-timestamp">15:38</span><span
            class="transcript-text">OK, what does combine mean?</span></div>
    <div class="transcript-line" data-begin="940.654"><span class="transcript-timestamp">15:40</span><span
            class="transcript-text">Well, it depends on
            your data structure.</span></div>
    <div class="transcript-line" data-begin="942.32"><span class="transcript-timestamp">15:42</span><span
            class="transcript-text">A lot of data structures
            have combine operations</span></div>
    <div class="transcript-line" data-begin="944.42"><span class="transcript-timestamp">15:44</span><span
            class="transcript-text">like if you have linked lists,
            you have two linked lists,</span></div>
    <div class="transcript-line" data-begin="948.029"><span class="transcript-timestamp">15:48</span><span
            class="transcript-text">you can concatenate them.</span></div>
    <div class="transcript-line" data-begin="949.07"><span class="transcript-timestamp">15:49</span><span
            class="transcript-text">That's an easy operation.</span></div>
    <div class="transcript-line" data-begin="950.18"><span class="transcript-timestamp">15:50</span><span
            class="transcript-text">Even if you have
            binary search trees,</span></div>
    <div class="transcript-line" data-begin="951.721"><span class="transcript-timestamp">15:51</span><span
            class="transcript-text">you can concatenate
            them reasonably easy</span></div>
    <div class="transcript-line" data-begin="953.75"><span class="transcript-timestamp">15:53</span><span
            class="transcript-text">and combine it into one
            big binary search tree.</span></div>
    <div class="transcript-line" data-begin="956.67"><span class="transcript-timestamp">15:56</span><span
            class="transcript-text">So if your data structure
            has an operation that</span></div>
    <div class="transcript-line" data-begin="959.06"><span class="transcript-timestamp">15:59</span><span
            class="transcript-text">takes as input two
            data structures,</span></div>
    <div class="transcript-line" data-begin="961.85"><span class="transcript-timestamp">16:01</span><span
            class="transcript-text">then what we're saying is now
            it can take two versions, which</span></div>
    <div class="transcript-line" data-begin="965.15"><span class="transcript-timestamp">16:05</span><span
            class="transcript-text">is more general.</span></div>
    <div class="transcript-line" data-begin="966.43"><span class="transcript-timestamp">16:06</span><span
            class="transcript-text">So I could take the
            same data structure,</span></div>
    <div class="transcript-line" data-begin="968.24"><span class="transcript-timestamp">16:08</span><span
            class="transcript-text">make some changes in
            one way, separately make</span></div>
    <div class="transcript-line" data-begin="970.43"><span class="transcript-timestamp">16:10</span><span
            class="transcript-text">some changes in a
            different way, and then</span></div>
    <div class="transcript-line" data-begin="972.138"><span class="transcript-timestamp">16:12</span><span
            class="transcript-text">try to concatenate them
            or do something crazy.</span></div>
    <div class="transcript-line" data-begin="974.66"><span class="transcript-timestamp">16:14</span><span
            class="transcript-text">This is hard to
            do, and most of it</span></div>
    <div class="transcript-line" data-begin="976.55"><span class="transcript-timestamp">16:16</span><span
            class="transcript-text">is an open problem
            whether it can be done.</span></div>
    <div class="transcript-line" data-begin="979.09"><span class="transcript-timestamp">16:19</span><span
            class="transcript-text">But I'll tell you about it.</span></div>
    <div class="transcript-line" data-begin="981.59"><span class="transcript-timestamp">16:21</span><span
            class="transcript-text">Then there's another level
            even more than confluent</span></div>
    <div class="transcript-line" data-begin="984.86"><span class="transcript-timestamp">16:24</span><span
            class="transcript-text">persistence.</span></div>
    <div class="transcript-line" data-begin="986.55"><span class="transcript-timestamp">16:26</span><span
            class="transcript-text">This is hard to interpret
            in the time travel world,</span></div>
    <div class="transcript-line" data-begin="990.59"><span class="transcript-timestamp">16:30</span><span
            class="transcript-text">but it would be functional
            data structures.</span></div>
    <div class="transcript-line" data-begin="992.43"><span class="transcript-timestamp">16:32</span><span
            class="transcript-text">If you've ever programmed
            in a functional programming</span></div>
    <div class="transcript-line" data-begin="994.13"><span class="transcript-timestamp">16:34</span><span
            class="transcript-text">language, it's a little bit
            annoying from an algorithm's</span></div>
    <div class="transcript-line" data-begin="996.8"><span class="transcript-timestamp">16:36</span><span
            class="transcript-text">perspective, because it
            constrains you to work</span></div>
    <div class="transcript-line" data-begin="999.65"><span class="transcript-timestamp">16:39</span><span
            class="transcript-text">in a purely functional world.</span></div>
    <div class="transcript-line" data-begin="1003.22"><span class="transcript-timestamp">16:43</span><span
            class="transcript-text">You can never modify anything.</span></div>
    <div class="transcript-line" data-begin="1005.9"><span class="transcript-timestamp">16:45</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="1006.4"><span class="transcript-timestamp">16:46</span><span
            class="transcript-text">Now, we don't want
            to modify versions.</span></div>
    <div class="transcript-line" data-begin="1009.22"><span class="transcript-timestamp">16:49</span><span
            class="transcript-text">That's fine.</span></div>
    <div class="transcript-line" data-begin="1009.83"><span class="transcript-timestamp">16:49</span><span
            class="transcript-text">But in a functional
            data structure,</span></div>
    <div class="transcript-line" data-begin="1011.288"><span class="transcript-timestamp">16:51</span><span
            class="transcript-text">you're not allowed to
            modify any nodes ever.</span></div>
    <div class="transcript-line" data-begin="1014.11"><span class="transcript-timestamp">16:54</span><span
            class="transcript-text">All you can do is
            make new notes.</span></div>
    <div class="transcript-line" data-begin="1023.67"><span class="transcript-timestamp">17:03</span><span
            class="transcript-text">This is constraining,
            and you can't always</span></div>
    <div class="transcript-line" data-begin="1027.317"><span class="transcript-timestamp">17:07</span><span
            class="transcript-text">get optimal running times
            in the functional world.</span></div>
    <div class="transcript-line" data-begin="1029.4"><span class="transcript-timestamp">17:09</span><span
            class="transcript-text">But if you can get a
            functional data structure,</span></div>
    <div class="transcript-line" data-begin="1031.358"><span class="transcript-timestamp">17:11</span><span
            class="transcript-text">you have all these
            things, because you</span></div>
    <div class="transcript-line" data-begin="1033.3"><span class="transcript-timestamp">17:13</span><span
            class="transcript-text">can't destroy anything.</span></div>
    <div class="transcript-line" data-begin="1034.259"><span class="transcript-timestamp">17:14</span><span
            class="transcript-text">If you can't destroy
            nodes, then in particular,</span></div>
    <div class="transcript-line" data-begin="1036.216"><span class="transcript-timestamp">17:16</span><span
            class="transcript-text">you can't destroy versions.</span></div>
    <div class="transcript-line" data-begin="1037.43"><span class="transcript-timestamp">17:17</span><span
            class="transcript-text">And all of these things
            just work for free.</span></div>
    <div class="transcript-line" data-begin="1039.93"><span class="transcript-timestamp">17:19</span><span
            class="transcript-text">And so a bunch of
            special cases are known,</span></div>
    <div class="transcript-line" data-begin="1042.957"><span class="transcript-timestamp">17:22</span><span
            class="transcript-text">interesting special
            cases, like search trees</span></div>
    <div class="transcript-line" data-begin="1044.79"><span class="transcript-timestamp">17:24</span><span
            class="transcript-text">you can do in the
            functional world.</span></div>
    <div class="transcript-line" data-begin="1046.47"><span class="transcript-timestamp">17:26</span><span
            class="transcript-text">And that makes all
            of these things easy.</span></div>
    <div class="transcript-line" data-begin="1049.05"><span class="transcript-timestamp">17:29</span><span
            class="transcript-text">So the rest of this
            lecture is going</span></div>
    <div class="transcript-line" data-begin="1050.79"><span class="transcript-timestamp">17:30</span><span
            class="transcript-text">to be general techniques for
            doing partial full persistence,</span></div>
    <div class="transcript-line" data-begin="1054.27"><span class="transcript-timestamp">17:34</span><span
            class="transcript-text">what we know about
            confluent, and what</span></div>
    <div class="transcript-line" data-begin="1056.25"><span class="transcript-timestamp">17:36</span><span
            class="transcript-text">we know about functional,
            brief overview.</span></div>
    <div class="transcript-line" data-begin="1061.06"><span class="transcript-timestamp">17:41</span><span
            class="transcript-text">Any questions about those
            goals, problem definitions?</span></div>
    <div class="transcript-line" data-begin="1067.64"><span class="transcript-timestamp">17:47</span><span
            class="transcript-text">Yeah.</span></div>
    <div class="transcript-line" data-begin="1068.191"><span class="transcript-timestamp">17:48</span><span
            class="transcript-text">AUDIENCE: I'm still confused
            about functional, because--</span></div>
    <div class="transcript-line" data-begin="1070.834"><span class="transcript-timestamp">17:50</span><span
            class="transcript-text">ERIK DEMAINE: What
            does functional mean?</span></div>
    <div class="transcript-line" data-begin="1072.5"><span class="transcript-timestamp">17:52</span><span
            class="transcript-text">AUDIENCE: [INAUDIBLE]</span></div>
    <div class="transcript-line" data-begin="1075.26"><span class="transcript-timestamp">17:55</span><span
            class="transcript-text">ERIK DEMAINE: Yeah, I
            guess you'll see what--</span></div>
    <div class="transcript-line" data-begin="1077.68"><span class="transcript-timestamp">17:57</span><span
            class="transcript-text">functional looks like all
            the other things, I agree.</span></div>
    <div class="transcript-line" data-begin="1080.2"><span class="transcript-timestamp">18:00</span><span
            class="transcript-text">You'll see in a moment
            how we actually implement</span></div>
    <div class="transcript-line" data-begin="1082.36"><span class="transcript-timestamp">18:02</span><span
            class="transcript-text">partial and persistence.</span></div>
    <div class="transcript-line" data-begin="1083.38"><span class="transcript-timestamp">18:03</span><span
            class="transcript-text">We're going to be
            changing nodes a lot.</span></div>
    <div class="transcript-line" data-begin="1087.49"><span class="transcript-timestamp">18:07</span><span
            class="transcript-text">As long as we still
            represent the same data</span></div>
    <div class="transcript-line" data-begin="1090.67"><span class="transcript-timestamp">18:10</span><span
            class="transcript-text">in the old versions, we
            don't have to represent it</span></div>
    <div class="transcript-line" data-begin="1093.04"><span class="transcript-timestamp">18:13</span><span
            class="transcript-text">in the same way.</span></div>
    <div class="transcript-line" data-begin="1094.164"><span class="transcript-timestamp">18:14</span><span
            class="transcript-text">That lets us do things
            more efficiently.</span></div>
    <div class="transcript-line" data-begin="1095.83"><span class="transcript-timestamp">18:15</span><span
            class="transcript-text">Whereas in functional,
            you have to represent</span></div>
    <div class="transcript-line" data-begin="1097.72"><span class="transcript-timestamp">18:17</span><span
            class="transcript-text">all the old versions
            in exactly the way</span></div>
    <div class="transcript-line" data-begin="1099.43"><span class="transcript-timestamp">18:19</span><span
            class="transcript-text">you used to represent them.</span></div>
    <div class="transcript-line" data-begin="1100.794"><span class="transcript-timestamp">18:20</span><span
            class="transcript-text">Here we can kind of
            mangle things around</span></div>
    <div class="transcript-line" data-begin="1102.46"><span class="transcript-timestamp">18:22</span><span
            class="transcript-text">and it makes things faster.</span></div>
    <div class="transcript-line" data-begin="1103.585"><span class="transcript-timestamp">18:23</span><span
            class="transcript-text">Yeah, good question.</span></div>
    <div class="transcript-line" data-begin="1105.49"><span class="transcript-timestamp">18:25</span><span
            class="transcript-text">So it seems almost the same,
            but it's nodes versus versions.</span></div>
    <div class="transcript-line" data-begin="1109.882"><span class="transcript-timestamp">18:29</span><span
            class="transcript-text">I haven't really
            defined a version.</span></div>
    <div class="transcript-line" data-begin="1111.34"><span class="transcript-timestamp">18:31</span><span
            class="transcript-text">But it's just that all the
            queries answer the same way.</span></div>
    <div class="transcript-line" data-begin="1114.58"><span class="transcript-timestamp">18:34</span><span
            class="transcript-text">That's what you need
            for persistence.</span></div>
    <div class="transcript-line" data-begin="1118.58"><span class="transcript-timestamp">18:38</span><span
            class="transcript-text">Other questions?</span></div>
    <div class="transcript-line" data-begin="1120.78"><span class="transcript-timestamp">18:40</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="1123.62"><span class="transcript-timestamp">18:43</span><span
            class="transcript-text">Well, let's do some
            real data structures.</span></div>
    <div class="transcript-line" data-begin="1129.66"><span class="transcript-timestamp">18:49</span><span
            class="transcript-text">We start with
            partial persistence.</span></div>
    <div class="transcript-line" data-begin="1135.907"><span class="transcript-timestamp">18:55</span><span
            class="transcript-text">This is the easiest.</span></div>
    <div class="transcript-line" data-begin="1139.68"><span class="transcript-timestamp">18:59</span><span
            class="transcript-text">For both partial and
            full persistence,</span></div>
    <div class="transcript-line" data-begin="1142.08"><span class="transcript-timestamp">19:02</span><span
            class="transcript-text">there is the following result.
            Any pointer machine data</span></div>
    <div class="transcript-line" data-begin="1146.4"><span class="transcript-timestamp">19:06</span><span
            class="transcript-text">structure, one catch with a
            constant number of pointers</span></div>
    <div class="transcript-line" data-begin="1159.66"><span class="transcript-timestamp">19:19</span><span
            class="transcript-text">to any node--</span></div>
    <div class="transcript-line" data-begin="1162.22"><span class="transcript-timestamp">19:22</span><span
            class="transcript-text">so this is constant n degree.</span></div>
    <div class="transcript-line" data-begin="1167.726"><span class="transcript-timestamp">19:27</span><span
            class="transcript-text">In a pointer machine, you
            always have a constant number</span></div>
    <div class="transcript-line" data-begin="1170.017"><span class="transcript-timestamp">19:30</span><span
            class="transcript-text">of pointers out
            of a node at most.</span></div>
    <div class="transcript-line" data-begin="1172.54"><span class="transcript-timestamp">19:32</span><span
            class="transcript-text">But for this result
            to hold, we also</span></div>
    <div class="transcript-line" data-begin="1174.54"><span class="transcript-timestamp">19:34</span><span
            class="transcript-text">need a constant number of
            pointers into any node.</span></div>
    <div class="transcript-line" data-begin="1177.28"><span class="transcript-timestamp">19:37</span><span
            class="transcript-text">So this is an extra constraint.</span></div>
    <div class="transcript-line" data-begin="1182.91"><span class="transcript-timestamp">19:42</span><span
            class="transcript-text">Can be transformed into
            another data structure that</span></div>
    <div class="transcript-line" data-begin="1187.32"><span class="transcript-timestamp">19:47</span><span
            class="transcript-text">is partially persistent and does
            all the things it used to do--</span></div>
    <div class="transcript-line" data-begin="1193.77"><span class="transcript-timestamp">19:53</span><span
            class="transcript-text">so I'll just say, can be
            made partially persistent.</span></div>
    <div class="transcript-line" data-begin="1200.3"><span class="transcript-timestamp">20:00</span><span
            class="transcript-text">You have to pay something, but
            you have to pay very little--</span></div>
    <div class="transcript-line" data-begin="1203.55"><span class="transcript-timestamp">20:03</span><span
            class="transcript-text">constant amortized
            factor overhead,</span></div>
    <div class="transcript-line" data-begin="1212.55"><span class="transcript-timestamp">20:12</span><span
            class="transcript-text">multiplicative overhead
            and constant amount</span></div>
    <div class="transcript-line" data-begin="1221.86"><span class="transcript-timestamp">20:21</span><span
            class="transcript-text">of additive space per change
            in the data structure.</span></div>
    <div class="transcript-line" data-begin="1230.29"><span class="transcript-timestamp">20:30</span><span
            class="transcript-text">So every time you do a
            modification in your pointer</span></div>
    <div class="transcript-line" data-begin="1233.66"><span class="transcript-timestamp">20:33</span><span
            class="transcript-text">machine-- you set one of
            the fields to something--</span></div>
    <div class="transcript-line" data-begin="1236.26"><span class="transcript-timestamp">20:36</span><span
            class="transcript-text">you have to store that forever.</span></div>
    <div class="transcript-line" data-begin="1237.83"><span class="transcript-timestamp">20:37</span><span
            class="transcript-text">So, I mean, this is the
            best you could hope to do.</span></div>
    <div class="transcript-line" data-begin="1239.98"><span class="transcript-timestamp">20:39</span><span
            class="transcript-text">You've got to store
            everything that happened.</span></div>
    <div class="transcript-line" data-begin="1243.25"><span class="transcript-timestamp">20:43</span><span
            class="transcript-text">You pay a constant
            factor overhead, eh.</span></div>
    <div class="transcript-line" data-begin="1245.76"><span class="transcript-timestamp">20:45</span><span
            class="transcript-text">We're theoreticians.</span></div>
    <div class="transcript-line" data-begin="1246.67"><span class="transcript-timestamp">20:46</span><span
            class="transcript-text">That doesn't matter.</span></div>
    <div class="transcript-line" data-begin="1248.17"><span class="transcript-timestamp">20:48</span><span
            class="transcript-text">Then you get any data
            structure in this world</span></div>
    <div class="transcript-line" data-begin="1250.84"><span class="transcript-timestamp">20:50</span><span
            class="transcript-text">can be made
            partially persistent.</span></div>
    <div class="transcript-line" data-begin="1253.27"><span class="transcript-timestamp">20:53</span><span
            class="transcript-text">That's nice.</span></div>
    <div class="transcript-line" data-begin="1254.026"><span class="transcript-timestamp">20:54</span><span
            class="transcript-text">Let's prove it.</span></div>
    <div class="transcript-line" data-begin="1260.33"><span class="transcript-timestamp">21:00</span><span
            class="transcript-text">OK, the idea is pretty simple.</span></div>
    <div class="transcript-line" data-begin="1264.78"><span class="transcript-timestamp">21:04</span><span
            class="transcript-text">Pointer machines are all
            about nodes and fields.</span></div>
    <div class="transcript-line" data-begin="1266.79"><span class="transcript-timestamp">21:06</span><span
            class="transcript-text">So we just need to simulate
            whatever the data structure is</span></div>
    <div class="transcript-line" data-begin="1269.82"><span class="transcript-timestamp">21:09</span><span
            class="transcript-text">doing to those nodes
            and fields in a way</span></div>
    <div class="transcript-line" data-begin="1271.71"><span class="transcript-timestamp">21:11</span><span
            class="transcript-text">that we don't lose
            all the information</span></div>
    <div class="transcript-line" data-begin="1273.54"><span class="transcript-timestamp">21:13</span><span
            class="transcript-text">and we can still
            search it very quickly.</span></div>
    <div class="transcript-line" data-begin="1277.32"><span class="transcript-timestamp">21:17</span><span
            class="transcript-text">First idea is to
            store back pointers.</span></div>
    <div class="transcript-line" data-begin="1281.19"><span class="transcript-timestamp">21:21</span><span
            class="transcript-text">And this is why we need the
            constant n degree constraint.</span></div>
    <div class="transcript-line" data-begin="1287.53"><span class="transcript-timestamp">21:27</span><span
            class="transcript-text">So if we have a node--</span></div>
    <div class="transcript-line" data-begin="1291.075"><span class="transcript-timestamp">21:31</span><span
            class="transcript-text">how do I want to
            draw a node here?</span></div>
    <div class="transcript-line" data-begin="1295.64"><span class="transcript-timestamp">21:35</span><span
            class="transcript-text">So maybe these are the
            three fields of the node.</span></div>
    <div class="transcript-line" data-begin="1298.7"><span class="transcript-timestamp">21:38</span><span
            class="transcript-text">I want to also store
            some back pointers.</span></div>
    <div class="transcript-line" data-begin="1302.93"><span class="transcript-timestamp">21:42</span><span
            class="transcript-text">Whenever there is a node
            that points to this node,</span></div>
    <div class="transcript-line" data-begin="1308.48"><span class="transcript-timestamp">21:48</span><span
            class="transcript-text">I want to have a
            back pointer that</span></div>
    <div class="transcript-line" data-begin="1310.67"><span class="transcript-timestamp">21:50</span><span
            class="transcript-text">points back so I know where
            all the pointers came from.</span></div>
    <div class="transcript-line" data-begin="1314.21"><span class="transcript-timestamp">21:54</span><span
            class="transcript-text">If there's only p pointers,
            then this is fine.</span></div>
    <div class="transcript-line" data-begin="1317.6"><span class="transcript-timestamp">21:57</span><span
            class="transcript-text">There'll be p fields here.</span></div>
    <div class="transcript-line" data-begin="1320.96"><span class="transcript-timestamp">22:00</span><span
            class="transcript-text">So still constant, still in
            the pointier machine model.</span></div>
    <div class="transcript-line" data-begin="1323.879"><span class="transcript-timestamp">22:03</span><span
            class="transcript-text">OK, I'm going to need
            some other stuff too.</span></div>
    <div class="transcript-line" data-begin="1328.67"><span class="transcript-timestamp">22:08</span><span
            class="transcript-text">So this is a simple thing,
            definitely want this.</span></div>
    <div class="transcript-line" data-begin="1331.31"><span class="transcript-timestamp">22:11</span><span
            class="transcript-text">Because if my nodes
            ever move around,</span></div>
    <div class="transcript-line" data-begin="1333.47"><span class="transcript-timestamp">22:13</span><span
            class="transcript-text">I've got to update
            the pointers to them.</span></div>
    <div class="transcript-line" data-begin="1335.172"><span class="transcript-timestamp">22:15</span><span
            class="transcript-text">And where are those pointers?</span></div>
    <div class="transcript-line" data-begin="1336.38"><span class="transcript-timestamp">22:16</span><span
            class="transcript-text">Well, the back pointers
            tell you where they are.</span></div>
    <div class="transcript-line" data-begin="1340.03"><span class="transcript-timestamp">22:20</span><span
            class="transcript-text">Nodes will still
            be constant size,</span></div>
    <div class="transcript-line" data-begin="1342.41"><span class="transcript-timestamp">22:22</span><span
            class="transcript-text">remain in pointer
            machine data structure.</span></div>
    <div class="transcript-line" data-begin="1345.5"><span class="transcript-timestamp">22:25</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="1346.34"><span class="transcript-timestamp">22:26</span><span
            class="transcript-text">That's idea one.</span></div>
    <div class="transcript-line" data-begin="1348.23"><span class="transcript-timestamp">22:28</span><span
            class="transcript-text">Idea two is this part.</span></div>
    <div class="transcript-line" data-begin="1355.08"><span class="transcript-timestamp">22:35</span><span
            class="transcript-text">This is going to store
            something called mods.</span></div>
    <div class="transcript-line" data-begin="1359.485"><span class="transcript-timestamp">22:39</span><span
            class="transcript-text">It could stand for something,
            but I'll leave it as mods.</span></div>
    <div class="transcript-line" data-begin="1364.02"><span class="transcript-timestamp">22:44</span><span
            class="transcript-text">So these are two of the
            fields of the data structure.</span></div>
    <div class="transcript-line" data-begin="1376.53"><span class="transcript-timestamp">22:56</span><span
            class="transcript-text">Ah, one convenience here
            is for back pointers,</span></div>
    <div class="transcript-line" data-begin="1381.48"><span class="transcript-timestamp">23:01</span><span
            class="transcript-text">I'm only going to store it for
            the latest version of the data</span></div>
    <div class="transcript-line" data-begin="1384.84"><span class="transcript-timestamp">23:04</span><span
            class="transcript-text">structure.</span></div>
    <div class="transcript-line" data-begin="1396.31"><span class="transcript-timestamp">23:16</span><span
            class="transcript-text">Sorry.</span></div>
    <div class="transcript-line" data-begin="1396.81"><span class="transcript-timestamp">23:16</span><span
            class="transcript-text">I forgot about that.</span></div>
    <div class="transcript-line" data-begin="1399.61"><span class="transcript-timestamp">23:19</span><span
            class="transcript-text">We'll come back to that later.</span></div>
    <div class="transcript-line" data-begin="1401.397"><span class="transcript-timestamp">23:21</span><span
            class="transcript-text">And then the idea is to
            store these modifications.</span></div>
    <div class="transcript-line" data-begin="1403.48"><span class="transcript-timestamp">23:23</span><span
            class="transcript-text">How many modifications?</span></div>
    <div class="transcript-line" data-begin="1405.73"><span class="transcript-timestamp">23:25</span><span
            class="transcript-text">Let's say up to p, twice p.</span></div>
    <div class="transcript-line" data-begin="1414.835"><span class="transcript-timestamp">23:34</span><span
            class="transcript-text">p was the bound on the
            n degree of a node.</span></div>
    <div class="transcript-line" data-begin="1418.64"><span class="transcript-timestamp">23:38</span><span
            class="transcript-text">So I'm going to allow 2p
            modifications over here.</span></div>
    <div class="transcript-line" data-begin="1423.87"><span class="transcript-timestamp">23:43</span><span
            class="transcript-text">And what's a
            modification look like?</span></div>
    <div class="transcript-line" data-begin="1428.78"><span class="transcript-timestamp">23:48</span><span
            class="transcript-text">It's going to consist
            of three things--</span></div>
    <div class="transcript-line" data-begin="1430.77"><span class="transcript-timestamp">23:50</span><span
            class="transcript-text">get them in the right order--</span></div>
    <div class="transcript-line" data-begin="1433.7"><span class="transcript-timestamp">23:53</span><span
            class="transcript-text">the version in which
            something was changed,</span></div>
    <div class="transcript-line" data-begin="1436.85"><span class="transcript-timestamp">23:56</span><span
            class="transcript-text">the field that got changed,
            and the value it go changed to.</span></div>
    <div class="transcript-line" data-begin="1442.83"><span class="transcript-timestamp">24:02</span><span
            class="transcript-text">So the idea is that these
            are the fields here.</span></div>
    <div class="transcript-line" data-begin="1447.92"><span class="transcript-timestamp">24:07</span><span
            class="transcript-text">We're not going to touch those.</span></div>
    <div class="transcript-line" data-begin="1449.87"><span class="transcript-timestamp">24:09</span><span
            class="transcript-text">Once they're set to something--</span></div>
    <div class="transcript-line" data-begin="1451.784"><span class="transcript-timestamp">24:11</span><span
            class="transcript-text">or, I mean, whatever
            they are initially,</span></div>
    <div class="transcript-line" data-begin="1453.45"><span class="transcript-timestamp">24:13</span><span
            class="transcript-text">they will stay that way.</span></div>
    <div class="transcript-line" data-begin="1455.37"><span class="transcript-timestamp">24:15</span><span
            class="transcript-text">And so instead of actually
            changing things like the data</span></div>
    <div class="transcript-line" data-begin="1458.42"><span class="transcript-timestamp">24:18</span><span
            class="transcript-text">structure normally
            would, we're just</span></div>
    <div class="transcript-line" data-begin="1459.92"><span class="transcript-timestamp">24:19</span><span
            class="transcript-text">going to add modifications
            here to say, oh,</span></div>
    <div class="transcript-line" data-begin="1461.81"><span class="transcript-timestamp">24:21</span><span
            class="transcript-text">well at this time, this field
            changed to the value of 5.</span></div>
    <div class="transcript-line" data-begin="1465.41"><span class="transcript-timestamp">24:25</span><span
            class="transcript-text">And then later on, it
            changed to the value 7.</span></div>
    <div class="transcript-line" data-begin="1467.72"><span class="transcript-timestamp">24:27</span><span
            class="transcript-text">And then later on, this one
            changed to the value 23,</span></div>
    <div class="transcript-line" data-begin="1471.38"><span class="transcript-timestamp">24:31</span><span
            class="transcript-text">whatever.</span></div>
    <div class="transcript-line" data-begin="1472.32"><span class="transcript-timestamp">24:32</span><span
            class="transcript-text">So that's what
            they'll look like.</span></div>
    <div class="transcript-line" data-begin="1476.292"><span class="transcript-timestamp">24:36</span><span
            class="transcript-text">There's a limit to how many--</span></div>
    <div class="transcript-line" data-begin="1477.5"><span class="transcript-timestamp">24:37</span><span
            class="transcript-text">we can only store a constant
            number of mods to each node.</span></div>
    <div class="transcript-line" data-begin="1480.92"><span class="transcript-timestamp">24:40</span><span
            class="transcript-text">And our constant will be 2p.</span></div>
    <div class="transcript-line" data-begin="1484.58"><span class="transcript-timestamp">24:44</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="1485.08"><span class="transcript-timestamp">24:45</span><span
            class="transcript-text">Those are the
            ideas, and now it's</span></div>
    <div class="transcript-line" data-begin="1486.22"><span class="transcript-timestamp">24:46</span><span
            class="transcript-text">just a matter of
            making this all work</span></div>
    <div class="transcript-line" data-begin="1487.761"><span class="transcript-timestamp">24:47</span><span
            class="transcript-text">and analyzing that it's
            constant amortized overhead.</span></div>
    <div class="transcript-line" data-begin="1493.26"><span class="transcript-timestamp">24:53</span><span
            class="transcript-text">So first thing is if you
            want to read a field,</span></div>
    <div class="transcript-line" data-begin="1506.23"><span class="transcript-timestamp">25:06</span><span
            class="transcript-text">how would I read a field?</span></div>
    <div class="transcript-line" data-begin="1508.09"><span class="transcript-timestamp">25:08</span><span
            class="transcript-text">This is really easy.</span></div>
    <div class="transcript-line" data-begin="1511.72"><span class="transcript-timestamp">25:11</span><span
            class="transcript-text">First you look at what the
            field is in the node itself.</span></div>
    <div class="transcript-line" data-begin="1515.92"><span class="transcript-timestamp">25:15</span><span
            class="transcript-text">But then it might
            have been changed.</span></div>
    <div class="transcript-line" data-begin="1517.831"><span class="transcript-timestamp">25:17</span><span
            class="transcript-text">And so remember when
            I say read the field,</span></div>
    <div class="transcript-line" data-begin="1519.58"><span class="transcript-timestamp">25:19</span><span
            class="transcript-text">I actually mean while
            I'm given some version,</span></div>
    <div class="transcript-line" data-begin="1521.6"><span class="transcript-timestamp">25:21</span><span
            class="transcript-text">v, I want to know what is the
            value of this field at version</span></div>
    <div class="transcript-line" data-begin="1524.655"><span class="transcript-timestamp">25:24</span><span
            class="transcript-text">v, because I want to be able
            to look at any of the old data</span></div>
    <div class="transcript-line" data-begin="1528.28"><span class="transcript-timestamp">25:28</span><span
            class="transcript-text">structures too.</span></div>
    <div class="transcript-line" data-begin="1529.63"><span class="transcript-timestamp">25:29</span><span
            class="transcript-text">So this would be at
            version v. I just</span></div>
    <div class="transcript-line" data-begin="1537.37"><span class="transcript-timestamp">25:37</span><span
            class="transcript-text">look through all
            the modifications.</span></div>
    <div class="transcript-line" data-begin="1538.84"><span class="transcript-timestamp">25:38</span><span
            class="transcript-text">There's constantly many,
            so it takes constant time</span></div>
    <div class="transcript-line" data-begin="1540.923"><span class="transcript-timestamp">25:40</span><span
            class="transcript-text">to just flip through them
            and say, well, what changes</span></div>
    <div class="transcript-line" data-begin="1543.73"><span class="transcript-timestamp">25:43</span><span
            class="transcript-text">have happened up to version v?</span></div>
    <div class="transcript-line" data-begin="1546.16"><span class="transcript-timestamp">25:46</span><span
            class="transcript-text">So I look at mods
            with version less than</span></div>
    <div class="transcript-line" data-begin="1556.75"><span class="transcript-timestamp">25:56</span><span
            class="transcript-text">or equal to v. That will be all
            the changes that happened up</span></div>
    <div class="transcript-line" data-begin="1559.45"><span class="transcript-timestamp">25:59</span><span
            class="transcript-text">to this point.</span></div>
    <div class="transcript-line" data-begin="1560.77"><span class="transcript-timestamp">26:00</span><span
            class="transcript-text">I see, did this field change?</span></div>
    <div class="transcript-line" data-begin="1562.06"><span class="transcript-timestamp">26:02</span><span
            class="transcript-text">I look at the latest one.</span></div>
    <div class="transcript-line" data-begin="1563.71"><span class="transcript-timestamp">26:03</span><span
            class="transcript-text">That will be how I read
            the field of the node, so</span></div>
    <div class="transcript-line" data-begin="1567.25"><span class="transcript-timestamp">26:07</span><span
            class="transcript-text">constant time.</span></div>
    <div class="transcript-line" data-begin="1568.517"><span class="transcript-timestamp">26:08</span><span
            class="transcript-text">There's lots of ways to make
            this efficient in practice.</span></div>
    <div class="transcript-line" data-begin="1570.85"><span class="transcript-timestamp">26:10</span><span
            class="transcript-text">But for our purposes,
            it doesn't matter.</span></div>
    <div class="transcript-line" data-begin="1573.73"><span class="transcript-timestamp">26:13</span><span
            class="transcript-text">It's constant.</span></div>
    <div class="transcript-line" data-begin="1576.01"><span class="transcript-timestamp">26:16</span><span
            class="transcript-text">The hard part is how
            do you change a field?</span></div>
    <div class="transcript-line" data-begin="1578.89"><span class="transcript-timestamp">26:18</span><span
            class="transcript-text">Because there might not be
            any room in the mod structure.</span></div>
    <div class="transcript-line" data-begin="1595.85"><span class="transcript-timestamp">26:35</span><span
            class="transcript-text">So to modify, say we want to
            set node.field equal to x.</span></div>
    <div class="transcript-line" data-begin="1607.24"><span class="transcript-timestamp">26:47</span><span
            class="transcript-text">What we do is first
            we check, is there</span></div>
    <div class="transcript-line" data-begin="1612.74"><span class="transcript-timestamp">26:52</span><span
            class="transcript-text">any space in the mod structure?</span></div>
    <div class="transcript-line" data-begin="1614.27"><span class="transcript-timestamp">26:54</span><span
            class="transcript-text">If there's any blank mods,
            so if the node is not full,</span></div>
    <div class="transcript-line" data-begin="1623.08"><span class="transcript-timestamp">27:03</span><span
            class="transcript-text">we just add a mod.</span></div>
    <div class="transcript-line" data-begin="1626.63"><span class="transcript-timestamp">27:06</span><span
            class="transcript-text">So a mod will look
            like now field x.</span></div>
    <div class="transcript-line" data-begin="1633.106"><span class="transcript-timestamp">27:13</span><span
            class="transcript-text">Just throw that in there.</span></div>
    <div class="transcript-line" data-begin="1635.81"><span class="transcript-timestamp">27:15</span><span
            class="transcript-text">Because right at this moment--</span></div>
    <div class="transcript-line" data-begin="1637.65"><span class="transcript-timestamp">27:17</span><span
            class="transcript-text">so we maintain a time
            counter, just increment</span></div>
    <div class="transcript-line" data-begin="1639.56"><span class="transcript-timestamp">27:19</span><span
            class="transcript-text">it ever time we do a change.</span></div>
    <div class="transcript-line" data-begin="1641.93"><span class="transcript-timestamp">27:21</span><span
            class="transcript-text">This field changed that value.</span></div>
    <div class="transcript-line" data-begin="1643.32"><span class="transcript-timestamp">27:23</span><span
            class="transcript-text">So that's the easy case.</span></div>
    <div class="transcript-line" data-begin="1644.54"><span class="transcript-timestamp">27:24</span><span
            class="transcript-text">The trouble, of course,
            is if the node is full--</span></div>
    <div class="transcript-line" data-begin="1649.34"><span class="transcript-timestamp">27:29</span><span
            class="transcript-text">the moment you've
            all been waiting for.</span></div>
    <div class="transcript-line" data-begin="1651.067"><span class="transcript-timestamp">27:31</span><span
            class="transcript-text">So what we're going to do
            here is make a new node.</span></div>
    <div class="transcript-line" data-begin="1653.15"><span class="transcript-timestamp">27:33</span><span
            class="transcript-text">We've ran out of space.</span></div>
    <div class="transcript-line" data-begin="1654.69"><span class="transcript-timestamp">27:34</span><span
            class="transcript-text">So we need to make a new node.</span></div>
    <div class="transcript-line" data-begin="1656.064"><span class="transcript-timestamp">27:36</span><span
            class="transcript-text">We're not going to touch the old
            node, just going to let it sit.</span></div>
    <div class="transcript-line" data-begin="1658.73"><span class="transcript-timestamp">27:38</span><span
            class="transcript-text">It still maintains all
            those old versions.</span></div>
    <div class="transcript-line" data-begin="1660.53"><span class="transcript-timestamp">27:40</span><span
            class="transcript-text">Now we want a new node
            that represents the latest</span></div>
    <div class="transcript-line" data-begin="1663.23"><span class="transcript-timestamp">27:43</span><span
            class="transcript-text">and greatest of this node.</span></div>
    <div class="transcript-line" data-begin="1664.97"><span class="transcript-timestamp">27:44</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="1665.49"><span class="transcript-timestamp">27:45</span><span
            class="transcript-text">So make a new node.</span></div>
    <div class="transcript-line" data-begin="1671.42"><span class="transcript-timestamp">27:51</span><span
            class="transcript-text">I'll call it node prime to
            distinguish from node, where</span></div>
    <div class="transcript-line" data-begin="1677.06"><span class="transcript-timestamp">27:57</span><span
            class="transcript-text">with all the mods, and this
            modification in particular,</span></div>
    <div class="transcript-line" data-begin="1684.705"><span class="transcript-timestamp">28:04</span><span
            class="transcript-text">applied.</span></div>
    <div class="transcript-line" data-begin="1687.77"><span class="transcript-timestamp">28:07</span><span
            class="transcript-text">OK, so we make a new
            version of this node.</span></div>
    <div class="transcript-line" data-begin="1691.16"><span class="transcript-timestamp">28:11</span><span
            class="transcript-text">It's going to have some
            different fields, whatever</span></div>
    <div class="transcript-line" data-begin="1695.37"><span class="transcript-timestamp">28:15</span><span
            class="transcript-text">was the latest version
            represented by those mods.</span></div>
    <div class="transcript-line" data-begin="1698.73"><span class="transcript-timestamp">28:18</span><span
            class="transcript-text">It's still going to
            have back pointers,</span></div>
    <div class="transcript-line" data-begin="1700.525"><span class="transcript-timestamp">28:20</span><span
            class="transcript-text">so we have to maintain
            all those back pointers.</span></div>
    <div class="transcript-line" data-begin="1704.81"><span class="transcript-timestamp">28:24</span><span
            class="transcript-text">And now the mod,
            initially, is going</span></div>
    <div class="transcript-line" data-begin="1706.4"><span class="transcript-timestamp">28:26</span><span
            class="transcript-text">to be empty, because we
            just applied them all.</span></div>
    <div class="transcript-line" data-begin="1709.34"><span class="transcript-timestamp">28:29</span><span
            class="transcript-text">So this new node doesn't
            have any recent mods.</span></div>
    <div class="transcript-line" data-begin="1712.46"><span class="transcript-timestamp">28:32</span><span
            class="transcript-text">Old node represents
            the old versions.</span></div>
    <div class="transcript-line" data-begin="1714.32"><span class="transcript-timestamp">28:34</span><span
            class="transcript-text">This node is going to
            represent the new versions.</span></div>
    <div class="transcript-line" data-begin="1717.935"><span class="transcript-timestamp">28:37</span><span
            class="transcript-text">What's wrong with this picture?</span></div>
    <div class="transcript-line" data-begin="1719.42"><span class="transcript-timestamp">28:39</span><span
            class="transcript-text">AUDIENCE: Update pointers.</span></div>
    <div class="transcript-line" data-begin="1720.77"><span class="transcript-timestamp">28:40</span><span
            class="transcript-text">ERIK DEMAINE: Update pointers.</span></div>
    <div class="transcript-line" data-begin="1722.12"><span class="transcript-timestamp">28:42</span><span
            class="transcript-text">Yeah, there's pointers
            to the old version</span></div>
    <div class="transcript-line" data-begin="1723.89"><span class="transcript-timestamp">28:43</span><span
            class="transcript-text">of the node, which are fine for
            the old versions of the data</span></div>
    <div class="transcript-line" data-begin="1727.58"><span class="transcript-timestamp">28:47</span><span
            class="transcript-text">structure.</span></div>
    <div class="transcript-line" data-begin="1728.259"><span class="transcript-timestamp">28:48</span><span
            class="transcript-text">But for the latest version
            of the data structure,</span></div>
    <div class="transcript-line" data-begin="1730.3"><span class="transcript-timestamp">28:50</span><span
            class="transcript-text">this node has moved
            to this new location.</span></div>
    <div class="transcript-line" data-begin="1733.56"><span class="transcript-timestamp">28:53</span><span
            class="transcript-text">So if there are any old
            pointers to that node,</span></div>
    <div class="transcript-line" data-begin="1736.07"><span class="transcript-timestamp">28:56</span><span
            class="transcript-text">we've got to update them
            in the current version.</span></div>
    <div class="transcript-line" data-begin="1738.44"><span class="transcript-timestamp">28:58</span><span
            class="transcript-text">We have to update them to
            point to this node instead.</span></div>
    <div class="transcript-line" data-begin="1740.648"><span class="transcript-timestamp">29:00</span><span
            class="transcript-text">The old versions are fine, but
            the new version is in trouble.</span></div>
    <div class="transcript-line" data-begin="1744.06"><span class="transcript-timestamp">29:04</span><span
            class="transcript-text">Other questions or
            all the same answer?</span></div>
    <div class="transcript-line" data-begin="1746.12"><span class="transcript-timestamp">29:06</span><span
            class="transcript-text">Yeah.</span></div>
    <div class="transcript-line" data-begin="1746.791"><span class="transcript-timestamp">29:06</span><span
            class="transcript-text">AUDIENCE: So if you wanted
            to read an old version</span></div>
    <div class="transcript-line" data-begin="1750.719"><span class="transcript-timestamp">29:10</span><span
            class="transcript-text">but you just have the
            new version, [INAUDIBLE]?</span></div>
    <div class="transcript-line" data-begin="1755.63"><span class="transcript-timestamp">29:15</span><span
            class="transcript-text">ERIK DEMAINE: OK--</span></div>
    <div class="transcript-line" data-begin="1756.555"><span class="transcript-timestamp">29:16</span><span
            class="transcript-text">AUDIENCE: [INAUDIBLE]</span></div>
    <div class="transcript-line" data-begin="1757.43"><span class="transcript-timestamp">29:17</span><span
            class="transcript-text">ERIK DEMAINE: The
            question is essentially,</span></div>
    <div class="transcript-line" data-begin="1759.18"><span class="transcript-timestamp">29:19</span><span
            class="transcript-text">how do we hold on to versions?</span></div>
    <div class="transcript-line" data-begin="1762.059"><span class="transcript-timestamp">29:22</span><span
            class="transcript-text">Essentially, you can think of
            a version of the data structure</span></div>
    <div class="transcript-line" data-begin="1764.6"><span class="transcript-timestamp">29:24</span><span
            class="transcript-text">as where the root node is.</span></div>
    <div class="transcript-line" data-begin="1766.404"><span class="transcript-timestamp">29:26</span><span
            class="transcript-text">That's probably the easiest.</span></div>
    <div class="transcript-line" data-begin="1767.57"><span class="transcript-timestamp">29:27</span><span
            class="transcript-text">I mean, in general, we're
            representing versions</span></div>
    <div class="transcript-line" data-begin="1769.528"><span class="transcript-timestamp">29:29</span><span
            class="transcript-text">by a number, v. But we
            always start at the root.</span></div>
    <div class="transcript-line" data-begin="1773.12"><span class="transcript-timestamp">29:33</span><span
            class="transcript-text">And so you've given
            the data structure,</span></div>
    <div class="transcript-line" data-begin="1775.077"><span class="transcript-timestamp">29:35</span><span
            class="transcript-text">which is represented
            by the root node.</span></div>
    <div class="transcript-line" data-begin="1776.66"><span class="transcript-timestamp">29:36</span><span
            class="transcript-text">And you say, search
            for the value 5.</span></div>
    <div class="transcript-line" data-begin="1780.02"><span class="transcript-timestamp">29:40</span><span
            class="transcript-text">Is it in this binary
            search tree or whatever?</span></div>
    <div class="transcript-line" data-begin="1783.289"><span class="transcript-timestamp">29:43</span><span
            class="transcript-text">And then you just start
            navigating from the root,</span></div>
    <div class="transcript-line" data-begin="1785.33"><span class="transcript-timestamp">29:45</span><span
            class="transcript-text">but you know I'm inversion
            a million or whatever.</span></div>
    <div class="transcript-line" data-begin="1789.56"><span class="transcript-timestamp">29:49</span><span
            class="transcript-text">I know what version
            I'm looking for.</span></div>
    <div class="transcript-line" data-begin="1791.34"><span class="transcript-timestamp">29:51</span><span
            class="transcript-text">So you start with the root,
            which never changes, let's say.</span></div>
    <div class="transcript-line" data-begin="1796.04"><span class="transcript-timestamp">29:56</span><span
            class="transcript-text">And then you follow
            pointers that</span></div>
    <div class="transcript-line" data-begin="1798.32"><span class="transcript-timestamp">29:58</span><span
            class="transcript-text">essentially tell
            you for that version</span></div>
    <div class="transcript-line" data-begin="1800.06"><span class="transcript-timestamp">30:00</span><span
            class="transcript-text">where you should be going.</span></div>
    <div class="transcript-line" data-begin="1801.38"><span class="transcript-timestamp">30:01</span><span
            class="transcript-text">I guess at the root version,
            it's a little trickier.</span></div>
    <div class="transcript-line" data-begin="1803.78"><span class="transcript-timestamp">30:03</span><span
            class="transcript-text">You probably want a little array
            that says for this version,</span></div>
    <div class="transcript-line" data-begin="1807.71"><span class="transcript-timestamp">30:07</span><span
            class="transcript-text">here's the root node.</span></div>
    <div class="transcript-line" data-begin="1808.9"><span class="transcript-timestamp">30:08</span><span
            class="transcript-text">But that's a special case.</span></div>
    <div class="transcript-line" data-begin="1811.13"><span class="transcript-timestamp">30:11</span><span
            class="transcript-text">Yeah.</span></div>
    <div class="transcript-line" data-begin="1811.67"><span class="transcript-timestamp">30:11</span><span
            class="transcript-text">Another question?</span></div>
    <div class="transcript-line" data-begin="1813.234"><span class="transcript-timestamp">30:13</span><span
            class="transcript-text">AUDIENCE: So on the
            new node that you</span></div>
    <div class="transcript-line" data-begin="1815.222"><span class="transcript-timestamp">30:15</span><span
            class="transcript-text">created, the fields that you
            copied, you also have to have</span></div>
    <div class="transcript-line" data-begin="1819.606"><span class="transcript-timestamp">30:19</span><span
            class="transcript-text">a version for them, right?</span></div>
    <div class="transcript-line" data-begin="1820.689"><span class="transcript-timestamp">30:20</span><span
            class="transcript-text">Because [INAUDIBLE]?</span></div>
    <div class="transcript-line" data-begin="1826.67"><span class="transcript-timestamp">30:26</span><span
            class="transcript-text">ERIK DEMAINE: These--</span></div>
    <div class="transcript-line" data-begin="1827.731"><span class="transcript-timestamp">30:27</span><span
            class="transcript-text">AUDIENCE: Or do you
            version the whole node?</span></div>
    <div class="transcript-line" data-begin="1830.19"><span class="transcript-timestamp">30:30</span><span
            class="transcript-text">ERIK DEMAINE: Here we're
            versioning the whole node.</span></div>
    <div class="transcript-line" data-begin="1832.65"><span class="transcript-timestamp">30:32</span><span
            class="transcript-text">The original field
            values represent</span></div>
    <div class="transcript-line" data-begin="1834.6"><span class="transcript-timestamp">30:34</span><span
            class="transcript-text">what was originally there,
            whenever this node was created.</span></div>
    <div class="transcript-line" data-begin="1837.94"><span class="transcript-timestamp">30:37</span><span
            class="transcript-text">Then the mods specify what
            time the fields change.</span></div>
    <div class="transcript-line" data-begin="1840.25"><span class="transcript-timestamp">30:40</span><span
            class="transcript-text">So I don't think
            we need times here.</span></div>
    <div class="transcript-line" data-begin="1844.2"><span class="transcript-timestamp">30:44</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="1845.326"><span class="transcript-timestamp">30:45</span><span
            class="transcript-text">So we've got to update
            two kinds of pointers.</span></div>
    <div class="transcript-line" data-begin="1847.2"><span class="transcript-timestamp">30:47</span><span
            class="transcript-text">There's regular
            pointers, which live</span></div>
    <div class="transcript-line" data-begin="1848.81"><span class="transcript-timestamp">30:48</span><span
            class="transcript-text">in the fields, which are
            things pointing to the node.</span></div>
    <div class="transcript-line" data-begin="1852.14"><span class="transcript-timestamp">30:52</span><span
            class="transcript-text">But then there's
            also back pointers.</span></div>
    <div class="transcript-line" data-begin="1853.64"><span class="transcript-timestamp">30:53</span><span
            class="transcript-text">Because if this is
            a pointer to a node,</span></div>
    <div class="transcript-line" data-begin="1855.909"><span class="transcript-timestamp">30:55</span><span
            class="transcript-text">then there'll be a back
            pointer back to the node.</span></div>
    <div class="transcript-line" data-begin="1857.95"><span class="transcript-timestamp">30:57</span><span
            class="transcript-text">And all of those have to change.</span></div>
    <div class="transcript-line" data-begin="1860.62"><span class="transcript-timestamp">31:00</span><span
            class="transcript-text">Conveniently, the back
            pointers are easy.</span></div>
    <div class="transcript-line" data-begin="1871.7"><span class="transcript-timestamp">31:11</span><span
            class="transcript-text">So if they're back
            pointers to the node,</span></div>
    <div class="transcript-line" data-begin="1873.535"><span class="transcript-timestamp">31:13</span><span
            class="transcript-text">we change them to
            the node prime.</span></div>
    <div class="transcript-line" data-begin="1874.91"><span class="transcript-timestamp">31:14</span><span
            class="transcript-text">How do we find
            the back pointers?</span></div>
    <div class="transcript-line" data-begin="1876.08"><span class="transcript-timestamp">31:16</span><span
            class="transcript-text">Well, we just follow
            all the pointers</span></div>
    <div class="transcript-line" data-begin="1877.621"><span class="transcript-timestamp">31:17</span><span
            class="transcript-text">and then there will be
            back pointers there.</span></div>
    <div class="transcript-line" data-begin="1881.33"><span class="transcript-timestamp">31:21</span><span
            class="transcript-text">Because I said we're
            only maintaining</span></div>
    <div class="transcript-line" data-begin="1883.04"><span class="transcript-timestamp">31:23</span><span
            class="transcript-text">backed pointers for
            the latest version,</span></div>
    <div class="transcript-line" data-begin="1885.65"><span class="transcript-timestamp">31:25</span><span
            class="transcript-text">I don't need to preserve
            the old versions</span></div>
    <div class="transcript-line" data-begin="1888.299"><span class="transcript-timestamp">31:28</span><span
            class="transcript-text">of those backed pointers.</span></div>
    <div class="transcript-line" data-begin="1889.34"><span class="transcript-timestamp">31:29</span><span
            class="transcript-text">So I just go in
            and I change them.</span></div>
    <div class="transcript-line" data-begin="1891.025"><span class="transcript-timestamp">31:31</span><span
            class="transcript-text">It takes constant time,
            because the constant number</span></div>
    <div class="transcript-line" data-begin="1893.15"><span class="transcript-timestamp">31:33</span><span
            class="transcript-text">of things I point to, each
            one as a back pointer.</span></div>
    <div class="transcript-line" data-begin="1895.7"><span class="transcript-timestamp">31:35</span><span
            class="transcript-text">So this is cheap.</span></div>
    <div class="transcript-line" data-begin="1897.13"><span class="transcript-timestamp">31:37</span><span
            class="transcript-text">There's no persistence here.</span></div>
    <div class="transcript-line" data-begin="1899.21"><span class="transcript-timestamp">31:39</span><span
            class="transcript-text">That's an advantage of
            partial persistence.</span></div>
    <div class="transcript-line" data-begin="1901.94"><span class="transcript-timestamp">31:41</span><span
            class="transcript-text">The hard part is
            updating the pointers</span></div>
    <div class="transcript-line" data-begin="1904.37"><span class="transcript-timestamp">31:44</span><span
            class="transcript-text">because those live in fields.</span></div>
    <div class="transcript-line" data-begin="1905.684"><span class="transcript-timestamp">31:45</span><span
            class="transcript-text">I need to remember the old
            versions of those fields.</span></div>
    <div class="transcript-line" data-begin="1907.85"><span class="transcript-timestamp">31:47</span><span
            class="transcript-text">And that we do recursively.</span></div>
    <div class="transcript-line" data-begin="1918.746"><span class="transcript-timestamp">31:58</span><span
            class="transcript-text">Because to change
            those pointers,</span></div>
    <div class="transcript-line" data-begin="1920.12"><span class="transcript-timestamp">32:00</span><span
            class="transcript-text">that's a field update.</span></div>
    <div class="transcript-line" data-begin="1921.17"><span class="transcript-timestamp">32:01</span><span
            class="transcript-text">That's something
            exactly of this form.</span></div>
    <div class="transcript-line" data-begin="1922.94"><span class="transcript-timestamp">32:02</span><span
            class="transcript-text">So that's the same operation
            but on a different node.</span></div>
    <div class="transcript-line" data-begin="1925.97"><span class="transcript-timestamp">32:05</span><span
            class="transcript-text">So I just do that.</span></div>
    <div class="transcript-line" data-begin="1927.44"><span class="transcript-timestamp">32:07</span><span
            class="transcript-text">I claim this is good.</span></div>
    <div class="transcript-line" data-begin="1928.76"><span class="transcript-timestamp">32:08</span><span
            class="transcript-text">That's the end of the algorithm.</span></div>
    <div class="transcript-line" data-begin="1931.4"><span class="transcript-timestamp">32:11</span><span
            class="transcript-text">Now we need to analyze it.</span></div>
    <div class="transcript-line" data-begin="1944.886"><span class="transcript-timestamp">32:24</span><span
            class="transcript-text">How do we analyze it?</span></div>
    <div class="transcript-line" data-begin="1945.76"><span class="transcript-timestamp">32:25</span><span
            class="transcript-text">Any guesses?</span></div>
    <div class="transcript-line" data-begin="1949.498"><span class="transcript-timestamp">32:29</span><span
            class="transcript-text">AUDIENCE: Amortize it.</span></div>
    <div class="transcript-line" data-begin="1950.5"><span class="transcript-timestamp">32:30</span><span
            class="transcript-text">ERIK DEMAINE: Amortized
            analysis, exactly</span></div>
    <div class="transcript-line" data-begin="1952.208"><span class="transcript-timestamp">32:32</span><span
            class="transcript-text">the answer I was looking for.</span></div>
    <div class="transcript-line" data-begin="1953.62"><span class="transcript-timestamp">32:33</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="1954.58"><span class="transcript-timestamp">32:34</span><span
            class="transcript-text">[INAUDIBLE] amortization.</span></div>
    <div class="transcript-line" data-begin="1956.29"><span class="transcript-timestamp">32:36</span><span
            class="transcript-text">The most powerful
            technique in amortization</span></div>
    <div class="transcript-line" data-begin="1958.33"><span class="transcript-timestamp">32:38</span><span
            class="transcript-text">is probably the
            potential method.</span></div>
    <div class="transcript-line" data-begin="1960.46"><span class="transcript-timestamp">32:40</span><span
            class="transcript-text">So we're going to use that.</span></div>
    <div class="transcript-line" data-begin="1962.37"><span class="transcript-timestamp">32:42</span><span
            class="transcript-text">There's a sort of more--</span></div>
    <div class="transcript-line" data-begin="1964.36"><span class="transcript-timestamp">32:44</span><span
            class="transcript-text">you'll see a charging
            argument in a moment.</span></div>
    <div class="transcript-line" data-begin="1970.914"><span class="transcript-timestamp">32:50</span><span
            class="transcript-text">We want the potential function
            to represent when this data</span></div>
    <div class="transcript-line" data-begin="1973.33"><span class="transcript-timestamp">32:53</span><span
            class="transcript-text">structure is in a bad state.</span></div>
    <div class="transcript-line" data-begin="1975.3"><span class="transcript-timestamp">32:55</span><span
            class="transcript-text">Intuitively, it's in a bad state
            when a lot of nodes are full.</span></div>
    <div class="transcript-line" data-begin="1978.807"><span class="transcript-timestamp">32:58</span><span
            class="transcript-text">Because then as soon as
            you make a change in them,</span></div>
    <div class="transcript-line" data-begin="1980.89"><span class="transcript-timestamp">33:00</span><span
            class="transcript-text">they will burst, and you have
            to do all this crazy recursion</span></div>
    <div class="transcript-line" data-begin="1983.68"><span class="transcript-timestamp">33:03</span><span
            class="transcript-text">and stuff.</span></div>
    <div class="transcript-line" data-begin="1984.58"><span class="transcript-timestamp">33:04</span><span
            class="transcript-text">This case is nice and cheap.</span></div>
    <div class="transcript-line" data-begin="1985.99"><span class="transcript-timestamp">33:05</span><span
            class="transcript-text">We just add a modification,
            constant time.</span></div>
    <div class="transcript-line" data-begin="1988.68"><span class="transcript-timestamp">33:08</span><span
            class="transcript-text">This case, not so nice
            because we recurse.</span></div>
    <div class="transcript-line" data-begin="1990.43"><span class="transcript-timestamp">33:10</span><span
            class="transcript-text">And then that's going
            to cause more recursions</span></div>
    <div class="transcript-line" data-begin="1992.74"><span class="transcript-timestamp">33:12</span><span
            class="transcript-text">and all sorts of
            chaos could happen.</span></div>
    <div class="transcript-line" data-begin="1996.04"><span class="transcript-timestamp">33:16</span><span
            class="transcript-text">So there's probably a few
            different potential functions</span></div>
    <div class="transcript-line" data-begin="2000.03"><span class="transcript-timestamp">33:20</span><span
            class="transcript-text">that would work here.</span></div>
    <div class="transcript-line" data-begin="2001.08"><span class="transcript-timestamp">33:21</span><span
            class="transcript-text">And an old version
            of these nodes I said</span></div>
    <div class="transcript-line" data-begin="2003.15"><span class="transcript-timestamp">33:23</span><span
            class="transcript-text">should be the number
            of full nodes.</span></div>
    <div class="transcript-line" data-begin="2005.07"><span class="transcript-timestamp">33:25</span><span
            class="transcript-text">But I think we can make
            life a little bit easier</span></div>
    <div class="transcript-line" data-begin="2007.68"><span class="transcript-timestamp">33:27</span><span
            class="transcript-text">by the following.</span></div>
    <div class="transcript-line" data-begin="2012.39"><span class="transcript-timestamp">33:32</span><span
            class="transcript-text">Basically, the total
            number of modifications--</span></div>
    <div class="transcript-line" data-begin="2016.674"><span class="transcript-timestamp">33:36</span><span
            class="transcript-text">not quite the total,
            almost the total.</span></div>
    <div class="transcript-line" data-begin="2019.8"><span class="transcript-timestamp">33:39</span><span
            class="transcript-text">So I'm going to do c times
            the sum of the number of mods</span></div>
    <div class="transcript-line" data-begin="2029.76"><span class="transcript-timestamp">33:49</span><span
            class="transcript-text">in latest version nodes.</span></div>
    <div class="transcript-line" data-begin="2039.16"><span class="transcript-timestamp">33:59</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2040.53"><span class="transcript-timestamp">34:00</span><span
            class="transcript-text">So because we sort
            of really only</span></div>
    <div class="transcript-line" data-begin="2042.984"><span class="transcript-timestamp">34:02</span><span
            class="transcript-text">care about-- we're only
            changing the latest version,</span></div>
    <div class="transcript-line" data-begin="2045.15"><span class="transcript-timestamp">34:05</span><span
            class="transcript-text">so I really only
            care about nodes that</span></div>
    <div class="transcript-line" data-begin="2047.07"><span class="transcript-timestamp">34:07</span><span
            class="transcript-text">live in the latest version.</span></div>
    <div class="transcript-line" data-begin="2048.57"><span class="transcript-timestamp">34:08</span><span
            class="transcript-text">What do I mean by this?</span></div>
    <div class="transcript-line" data-begin="2049.659"><span class="transcript-timestamp">34:09</span><span
            class="transcript-text">Well, when I made
            this new node prime,</span></div>
    <div class="transcript-line" data-begin="2051.909"><span class="transcript-timestamp">34:11</span><span
            class="transcript-text">this becomes the new
            representation of that node.</span></div>
    <div class="transcript-line" data-begin="2054"><span class="transcript-timestamp">34:14</span><span
            class="transcript-text">The old version is dead.</span></div>
    <div class="transcript-line" data-begin="2055.69"><span class="transcript-timestamp">34:15</span><span
            class="transcript-text">We will never change it again.</span></div>
    <div class="transcript-line" data-begin="2058.56"><span class="transcript-timestamp">34:18</span><span
            class="transcript-text">If we're modifying, we will
            never even look at it again.</span></div>
    <div class="transcript-line" data-begin="2061.08"><span class="transcript-timestamp">34:21</span><span
            class="transcript-text">Because now everything
            points to here.</span></div>
    <div class="transcript-line" data-begin="2064.805"><span class="transcript-timestamp">34:24</span><span
            class="transcript-text">So I don't really
            care about that node.</span></div>
    <div class="transcript-line" data-begin="2066.429"><span class="transcript-timestamp">34:26</span><span
            class="transcript-text">It's got a ton of mods.</span></div>
    <div class="transcript-line" data-begin="2067.69"><span class="transcript-timestamp">34:27</span><span
            class="transcript-text">But what's nice is that when
            I create this new node, now</span></div>
    <div class="transcript-line" data-begin="2070.38"><span class="transcript-timestamp">34:30</span><span
            class="transcript-text">the mod list is empty.</span></div>
    <div class="transcript-line" data-begin="2071.882"><span class="transcript-timestamp">34:31</span><span
            class="transcript-text">So I start from scratch,
            just like reinstalling</span></div>
    <div class="transcript-line" data-begin="2073.84"><span class="transcript-timestamp">34:33</span><span
            class="transcript-text">your operating system.</span></div>
    <div class="transcript-line" data-begin="2074.87"><span class="transcript-timestamp">34:34</span><span
            class="transcript-text">It's a good feeling.</span></div>
    <div class="transcript-line" data-begin="2078.01"><span class="transcript-timestamp">34:38</span><span
            class="transcript-text">And so the potential goes down
            by, I guess, c times 2 times p.</span></div>
    <div class="transcript-line" data-begin="2085.09"><span class="transcript-timestamp">34:45</span><span
            class="transcript-text">When I do this change, potential
            goes down by basically p.</span></div>
    <div class="transcript-line" data-begin="2089.764"><span class="transcript-timestamp">34:49</span><span
            class="transcript-text">AUDIENCE: Is c any constant or--</span></div>
    <div class="transcript-line" data-begin="2092.23"><span class="transcript-timestamp">34:52</span><span
            class="transcript-text">ERIK DEMAINE: c will be a
            constant to be determined.</span></div>
    <div class="transcript-line" data-begin="2095.44"><span class="transcript-timestamp">34:55</span><span
            class="transcript-text">I mean, it could be 1.</span></div>
    <div class="transcript-line" data-begin="2097.18"><span class="transcript-timestamp">34:57</span><span
            class="transcript-text">It depends how you
            want to define it.</span></div>
    <div class="transcript-line" data-begin="2098.77"><span class="transcript-timestamp">34:58</span><span
            class="transcript-text">I'm going to use the CLRS
            notion of amortized cost, which</span></div>
    <div class="transcript-line" data-begin="2102.13"><span class="transcript-timestamp">35:02</span><span
            class="transcript-text">is actual cost plus
            change in potential.</span></div>
    <div class="transcript-line" data-begin="2106.777"><span class="transcript-timestamp">35:06</span><span
            class="transcript-text">And then I need a
            constant here, because I'm</span></div>
    <div class="transcript-line" data-begin="2108.61"><span class="transcript-timestamp">35:08</span><span
            class="transcript-text">measuring a running time versus
            some combinatorial quantity.</span></div>
    <div class="transcript-line" data-begin="2112.85"><span class="transcript-timestamp">35:12</span><span
            class="transcript-text">So this will be to match the
            running time that we'll get to.</span></div>
    <div class="transcript-line" data-begin="2117.41"><span class="transcript-timestamp">35:17</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2117.99"><span class="transcript-timestamp">35:17</span><span
            class="transcript-text">So what is amortized cost?</span></div>
    <div class="transcript-line" data-begin="2122.29"><span class="transcript-timestamp">35:22</span><span
            class="transcript-text">There's sort of two
            cases modification.</span></div>
    <div class="transcript-line" data-begin="2124.92"><span class="transcript-timestamp">35:24</span><span
            class="transcript-text">There's the cheap case
            and the not so cheap case.</span></div>
    <div class="transcript-line" data-begin="2128.44"><span class="transcript-timestamp">35:28</span><span
            class="transcript-text">In general, amortized cost--</span></div>
    <div class="transcript-line" data-begin="2134.98"><span class="transcript-timestamp">35:34</span><span
            class="transcript-text">in both cases, it's
            going to be at most--</span></div>
    <div class="transcript-line" data-begin="2137.92"><span class="transcript-timestamp">35:37</span><span
            class="transcript-text">well, first of all, we
            do some constant work</span></div>
    <div class="transcript-line" data-begin="2139.81"><span class="transcript-timestamp">35:39</span><span
            class="transcript-text">just to figure out all this
            stuff, make copies, whatever.</span></div>
    <div class="transcript-line" data-begin="2144.64"><span class="transcript-timestamp">35:44</span><span
            class="transcript-text">So that's some constant time.</span></div>
    <div class="transcript-line" data-begin="2149.68"><span class="transcript-timestamp">35:49</span><span
            class="transcript-text">That's the part that I don't
            want to try to measure.</span></div>
    <div class="transcript-line" data-begin="2152.92"><span class="transcript-timestamp">35:52</span><span
            class="transcript-text">Then potentially,
            we add a new mod.</span></div>
    <div class="transcript-line" data-begin="2155.14"><span class="transcript-timestamp">35:55</span><span
            class="transcript-text">If we add a mod, that
            increases the potential by c.</span></div>
    <div class="transcript-line" data-begin="2159.43"><span class="transcript-timestamp">35:59</span><span
            class="transcript-text">Because we're just counting
            mods, multiplying by c.</span></div>
    <div class="transcript-line" data-begin="2162.07"><span class="transcript-timestamp">36:02</span><span
            class="transcript-text">So we might get plus 1 mod.</span></div>
    <div class="transcript-line" data-begin="2164.702"><span class="transcript-timestamp">36:04</span><span
            class="transcript-text">This is going to
            be an upper bound.</span></div>
    <div class="transcript-line" data-begin="2166.16"><span class="transcript-timestamp">36:06</span><span
            class="transcript-text">We don't always add 1, but
            worst case, we always had 1,</span></div>
    <div class="transcript-line" data-begin="2169.72"><span class="transcript-timestamp">36:09</span><span
            class="transcript-text">let's say.</span></div>
    <div class="transcript-line" data-begin="2171.88"><span class="transcript-timestamp">36:11</span><span
            class="transcript-text">And then there's
            this annoying part.</span></div>
    <div class="transcript-line" data-begin="2174.22"><span class="transcript-timestamp">36:14</span><span
            class="transcript-text">And this might happen,
            might not happen.</span></div>
    <div class="transcript-line" data-begin="2176.5"><span class="transcript-timestamp">36:16</span><span
            class="transcript-text">So then there's a plus maybe.</span></div>
    <div class="transcript-line" data-begin="2180.34"><span class="transcript-timestamp">36:20</span><span
            class="transcript-text">If this happens, we
            decrease the potential</span></div>
    <div class="transcript-line" data-begin="2183.31"><span class="transcript-timestamp">36:23</span><span
            class="transcript-text">because we empty out the
            mods for that node in terms</span></div>
    <div class="transcript-line" data-begin="2186.31"><span class="transcript-timestamp">36:26</span><span
            class="transcript-text">of the latest version.</span></div>
    <div class="transcript-line" data-begin="2187.72"><span class="transcript-timestamp">36:27</span><span
            class="transcript-text">So then we get a negative
            2cp, change in potential.</span></div>
    <div class="transcript-line" data-begin="2194.5"><span class="transcript-timestamp">36:34</span><span
            class="transcript-text">And then we'd have to pay
            I guess up to p recursions.</span></div>
    <div class="transcript-line" data-begin="2209.25"><span class="transcript-timestamp">36:49</span><span
            class="transcript-text">Because we have to--</span></div>
    <div class="transcript-line" data-begin="2211.52"><span class="transcript-timestamp">36:51</span><span
            class="transcript-text">how many pointers
            are there to me?</span></div>
    <div class="transcript-line" data-begin="2213.36"><span class="transcript-timestamp">36:53</span><span
            class="transcript-text">Well, at most p of them, because
            there are at most p pointers</span></div>
    <div class="transcript-line" data-begin="2218.49"><span class="transcript-timestamp">36:58</span><span
            class="transcript-text">to any node.</span></div>
    <div class="transcript-line" data-begin="2222.75"><span class="transcript-timestamp">37:02</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2223.35"><span class="transcript-timestamp">37:03</span><span
            class="transcript-text">This is kind of a weird--</span></div>
    <div class="transcript-line" data-begin="2225.11"><span class="transcript-timestamp">37:05</span><span
            class="transcript-text">it's not exactly algebra here.</span></div>
    <div class="transcript-line" data-begin="2226.51"><span class="transcript-timestamp">37:06</span><span
            class="transcript-text">I have this thing, recursions.</span></div>
    <div class="transcript-line" data-begin="2229.736"><span class="transcript-timestamp">37:09</span><span
            class="transcript-text">But if you think about
            how this would expand,</span></div>
    <div class="transcript-line" data-begin="2231.61"><span class="transcript-timestamp">37:11</span><span
            class="transcript-text">all right, this
            is constant time.</span></div>
    <div class="transcript-line" data-begin="2233.16"><span class="transcript-timestamp">37:13</span><span
            class="transcript-text">That's good.</span></div>
    <div class="transcript-line" data-begin="2234.02"><span class="transcript-timestamp">37:14</span><span
            class="transcript-text">And then if we do this--</span></div>
    <div class="transcript-line" data-begin="2235.02"><span class="transcript-timestamp">37:15</span><span
            class="transcript-text">I'll put a question mark here.</span></div>
    <div class="transcript-line" data-begin="2236.16"><span class="transcript-timestamp">37:16</span><span
            class="transcript-text">It might be here.</span></div>
    <div class="transcript-line" data-begin="2236.868"><span class="transcript-timestamp">37:16</span><span
            class="transcript-text">It might not.</span></div>
    <div class="transcript-line" data-begin="2238.11"><span class="transcript-timestamp">37:18</span><span
            class="transcript-text">If it's not here, find constant.</span></div>
    <div class="transcript-line" data-begin="2239.82"><span class="transcript-timestamp">37:19</span><span
            class="transcript-text">If it is here, then this gets
            expanded into this thing.</span></div>
    <div class="transcript-line" data-begin="2244.28"><span class="transcript-timestamp">37:24</span><span
            class="transcript-text">It's a weird way to
            write a recurrence.</span></div>
    <div class="transcript-line" data-begin="2246.13"><span class="transcript-timestamp">37:26</span><span
            class="transcript-text">But we get p times whatever
            is in this right hand side.</span></div>
    <div class="transcript-line" data-begin="2250.54"><span class="transcript-timestamp">37:30</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2251.04"><span class="transcript-timestamp">37:31</span><span
            class="transcript-text">But then there's this minus 2cp.</span></div>
    <div class="transcript-line" data-begin="2253.44"><span class="transcript-timestamp">37:33</span><span
            class="transcript-text">So we're going to
            get p times 2c here.</span></div>
    <div class="transcript-line" data-begin="2256.56"><span class="transcript-timestamp">37:36</span><span
            class="transcript-text">That's the initial cost.</span></div>
    <div class="transcript-line" data-begin="2257.85"><span class="transcript-timestamp">37:37</span><span
            class="transcript-text">So that will cancel with this.</span></div>
    <div class="transcript-line" data-begin="2260.04"><span class="transcript-timestamp">37:40</span><span
            class="transcript-text">And then we might get
            another recursion.</span></div>
    <div class="transcript-line" data-begin="2261.91"><span class="transcript-timestamp">37:41</span><span
            class="transcript-text">But every time we get a
            recursion, all the terms</span></div>
    <div class="transcript-line" data-begin="2263.91"><span class="transcript-timestamp">37:43</span><span
            class="transcript-text">cancel.</span></div>
    <div class="transcript-line" data-begin="2264.899"><span class="transcript-timestamp">37:44</span><span
            class="transcript-text">So it doesn't matter
            whether this is here or not.</span></div>
    <div class="transcript-line" data-begin="2266.94"><span class="transcript-timestamp">37:46</span><span
            class="transcript-text">You get 0, which is great.</span></div>
    <div class="transcript-line" data-begin="2269.61"><span class="transcript-timestamp">37:49</span><span
            class="transcript-text">And you're left with
            the original 2c.</span></div>
    <div class="transcript-line" data-begin="2273.4"><span class="transcript-timestamp">37:53</span><span
            class="transcript-text">Constant.</span></div>
    <div class="transcript-line" data-begin="2275.41"><span class="transcript-timestamp">37:55</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2276.3"><span class="transcript-timestamp">37:56</span><span
            class="transcript-text">[INAUDIBLE] potential functions
            are always a little crazy.</span></div>
    <div class="transcript-line" data-begin="2279.12"><span class="transcript-timestamp">37:59</span><span
            class="transcript-text">What's happening here is
            that, OK, maybe you add a mod.</span></div>
    <div class="transcript-line" data-begin="2283.53"><span class="transcript-timestamp">38:03</span><span
            class="transcript-text">That's cheap.</span></div>
    <div class="transcript-line" data-begin="2285.15"><span class="transcript-timestamp">38:05</span><span
            class="transcript-text">But when we have to do this
            work and we have to do this</span></div>
    <div class="transcript-line" data-begin="2288.15"><span class="transcript-timestamp">38:08</span><span
            class="transcript-text">recursion-- this is up to
            2p updates or recursions--</span></div>
    <div class="transcript-line" data-begin="2294.39"><span class="transcript-timestamp">38:14</span><span
            class="transcript-text">we are charging it to the
            emptying of this node.</span></div>
    <div class="transcript-line" data-begin="2297.27"><span class="transcript-timestamp">38:17</span><span
            class="transcript-text">The number of mods
            went from 2p down to 0.</span></div>
    <div class="transcript-line" data-begin="2301.11"><span class="transcript-timestamp">38:21</span><span
            class="transcript-text">And so we're just
            charging this update cost</span></div>
    <div class="transcript-line" data-begin="2302.94"><span class="transcript-timestamp">38:22</span><span
            class="transcript-text">to that modification.</span></div>
    <div class="transcript-line" data-begin="2304.059"><span class="transcript-timestamp">38:24</span><span
            class="transcript-text">So if you like charging schemes,
            this is much more intuitive.</span></div>
    <div class="transcript-line" data-begin="2306.6"><span class="transcript-timestamp">38:26</span><span
            class="transcript-text">But with charging schemes,
            it's always a little careful.</span></div>
    <div class="transcript-line" data-begin="2308.5"><span class="transcript-timestamp">38:28</span><span
            class="transcript-text">You have to make sure
            you're not double charging.</span></div>
    <div class="transcript-line" data-begin="2310.86"><span class="transcript-timestamp">38:30</span><span
            class="transcript-text">Here it's obvious that
            you're not double charging.</span></div>
    <div class="transcript-line" data-begin="2314.79"><span class="transcript-timestamp">38:34</span><span
            class="transcript-text">Kind of a cool and magical.</span></div>
    <div class="transcript-line" data-begin="2317.07"><span class="transcript-timestamp">38:37</span><span
            class="transcript-text">This is a paper by
            Driscoll, Sarnak, Sleator,</span></div>
    <div class="transcript-line" data-begin="2322.01"><span class="transcript-timestamp">38:42</span><span
            class="transcript-text">Tarjan from 1989.</span></div>
    <div class="transcript-line" data-begin="2323.82"><span class="transcript-timestamp">38:43</span><span
            class="transcript-text">So it's very early
            days of amortization.</span></div>
    <div class="transcript-line" data-begin="2325.62"><span class="transcript-timestamp">38:45</span><span
            class="transcript-text">But they knew how to do it.</span></div>
    <div class="transcript-line" data-begin="2327.76"><span class="transcript-timestamp">38:47</span><span
            class="transcript-text">Question?</span></div>
    <div class="transcript-line" data-begin="2328.521"><span class="transcript-timestamp">38:48</span><span
            class="transcript-text">AUDIENCE: [INAUDIBLE]</span></div>
    <div class="transcript-line" data-begin="2330.504"><span class="transcript-timestamp">38:50</span><span
            class="transcript-text">ERIK DEMAINE: What happens
            if you overflow the root?</span></div>
    <div class="transcript-line" data-begin="2332.67"><span class="transcript-timestamp">38:52</span><span
            class="transcript-text">Yeah, I never thought about
            the root before today.</span></div>
    <div class="transcript-line" data-begin="2334.753"><span class="transcript-timestamp">38:54</span><span
            class="transcript-text">But I think the way
            to fix the root is</span></div>
    <div class="transcript-line" data-begin="2337.35"><span class="transcript-timestamp">38:57</span><span
            class="transcript-text">just you have one big table
            that says, for a given version--</span></div>
    <div class="transcript-line" data-begin="2342.78"><span class="transcript-timestamp">39:02</span><span
            class="transcript-text">I guess a simple
            way would be to say,</span></div>
    <div class="transcript-line" data-begin="2344.326"><span class="transcript-timestamp">39:04</span><span
            class="transcript-text">not only is a version
            a number, but it's also</span></div>
    <div class="transcript-line" data-begin="2346.2"><span class="transcript-timestamp">39:06</span><span
            class="transcript-text">a pointer to the root.</span></div>
    <div class="transcript-line" data-begin="2347.13"><span class="transcript-timestamp">39:07</span><span
            class="transcript-text">There we go.</span></div>
    <div class="transcript-line" data-begin="2347.629"><span class="transcript-timestamp">39:07</span><span
            class="transcript-text">Pointer machine.</span></div>
    <div class="transcript-line" data-begin="2349.242"><span class="transcript-timestamp">39:09</span><span
            class="transcript-text">So that way you're just
            always explicitly maintaining</span></div>
    <div class="transcript-line" data-begin="2351.45"><span class="transcript-timestamp">39:11</span><span
            class="transcript-text">the root copy or the pointer.</span></div>
    <div class="transcript-line" data-begin="2355.11"><span class="transcript-timestamp">39:15</span><span
            class="transcript-text">Because otherwise,
            you're in trouble.</span></div>
    <div class="transcript-line" data-begin="2358.71"><span class="transcript-timestamp">39:18</span><span
            class="transcript-text">AUDIENCE: Then can you
            go back to [INAUDIBLE].</span></div>
    <div class="transcript-line" data-begin="2361.53"><span class="transcript-timestamp">39:21</span><span
            class="transcript-text">ERIK DEMAINE: So in order
            to refer to an old version,</span></div>
    <div class="transcript-line" data-begin="2364.31"><span class="transcript-timestamp">39:24</span><span
            class="transcript-text">you have to have the
            pointer to that root node.</span></div>
    <div class="transcript-line" data-begin="2366.75"><span class="transcript-timestamp">39:26</span><span
            class="transcript-text">If you want to do it just
            from a version number,</span></div>
    <div class="transcript-line" data-begin="2369.336"><span class="transcript-timestamp">39:29</span><span
            class="transcript-text">look at the data structure.</span></div>
    <div class="transcript-line" data-begin="2370.46"><span class="transcript-timestamp">39:30</span><span
            class="transcript-text">Just from a version
            number, you would</span></div>
    <div class="transcript-line" data-begin="2371.45"><span class="transcript-timestamp">39:31</span><span
            class="transcript-text">need some kind of
            lookup table, which</span></div>
    <div class="transcript-line" data-begin="2373.249"><span class="transcript-timestamp">39:33</span><span
            class="transcript-text">is outside the pointer machine.</span></div>
    <div class="transcript-line" data-begin="2374.54"><span class="transcript-timestamp">39:34</span><span
            class="transcript-text">So you could do it
            in a real computer,</span></div>
    <div class="transcript-line" data-begin="2376.28"><span class="transcript-timestamp">39:36</span><span
            class="transcript-text">but a pointer machine is
            not technically allowed.</span></div>
    <div class="transcript-line" data-begin="2379.21"><span class="transcript-timestamp">39:39</span><span
            class="transcript-text">So it's slightly awkward.</span></div>
    <div class="transcript-line" data-begin="2380.57"><span class="transcript-timestamp">39:40</span><span
            class="transcript-text">No arrays are allowed
            in pointer machines,</span></div>
    <div class="transcript-line" data-begin="2382.4"><span class="transcript-timestamp">39:42</span><span
            class="transcript-text">in case that wasn't clear.</span></div>
    <div class="transcript-line" data-begin="2383.483"><span class="transcript-timestamp">39:43</span><span
            class="transcript-text">Another question?</span></div>
    <div class="transcript-line" data-begin="2384.274"><span class="transcript-timestamp">39:44</span><span
            class="transcript-text">AUDIENCE: [INAUDIBLE] constant
            space to store for [INAUDIBLE].</span></div>
    <div class="transcript-line" data-begin="2388.72"><span class="transcript-timestamp">39:48</span><span
            class="transcript-text">And also, what if we have
            really big numbers [INAUDIBLE]?</span></div>
    <div class="transcript-line" data-begin="2394.294"><span class="transcript-timestamp">39:54</span><span
            class="transcript-text">ERIK DEMAINE: In this model,
            in the pointer machine model,</span></div>
    <div class="transcript-line" data-begin="2396.71"><span class="transcript-timestamp">39:56</span><span
            class="transcript-text">we're assuming that whatever
            the data is in the items</span></div>
    <div class="transcript-line" data-begin="2398.93"><span class="transcript-timestamp">39:58</span><span
            class="transcript-text">take constant space each.</span></div>
    <div class="transcript-line" data-begin="2401.48"><span class="transcript-timestamp">40:01</span><span
            class="transcript-text">If you want to know about
            bigger things in here,</span></div>
    <div class="transcript-line" data-begin="2403.67"><span class="transcript-timestamp">40:03</span><span
            class="transcript-text">then refer to future lectures.</span></div>
    <div class="transcript-line" data-begin="2405.45"><span class="transcript-timestamp">40:05</span><span
            class="transcript-text">This is time travel, after all.</span></div>
    <div class="transcript-line" data-begin="2406.91"><span class="transcript-timestamp">40:06</span><span
            class="transcript-text">Just go to a future
            class and then come back.</span></div>
    <div class="transcript-line" data-begin="2409.2"><span class="transcript-timestamp">40:09</span><span
            class="transcript-text">[LAUGHS] So we'll get
            there, but right now,</span></div>
    <div class="transcript-line" data-begin="2411.92"><span class="transcript-timestamp">40:11</span><span
            class="transcript-text">we're not thinking
            about what's in here.</span></div>
    <div class="transcript-line" data-begin="2415.121"><span class="transcript-timestamp">40:15</span><span
            class="transcript-text">Whatever big thing
            you're trying to store,</span></div>
    <div class="transcript-line" data-begin="2416.87"><span class="transcript-timestamp">40:16</span><span
            class="transcript-text">you reduce it down to
            constant size things.</span></div>
    <div class="transcript-line" data-begin="2419.81"><span class="transcript-timestamp">40:19</span><span
            class="transcript-text">And then you spread them around
            nodes of a pointer machine.</span></div>
    <div class="transcript-line" data-begin="2422.84"><span class="transcript-timestamp">40:22</span><span
            class="transcript-text">How you do that, that's
            up to the data structure.</span></div>
    <div class="transcript-line" data-begin="2425.25"><span class="transcript-timestamp">40:25</span><span
            class="transcript-text">We're just transforming the
            data structure to be persistent.</span></div>
    <div class="transcript-line" data-begin="2428"><span class="transcript-timestamp">40:28</span><span
            class="transcript-text">OK, you could ask about other
            models than pointer machines,</span></div>
    <div class="transcript-line" data-begin="2430.458"><span class="transcript-timestamp">40:30</span><span
            class="transcript-text">but we're going to stick
            to pointer machines here.</span></div>
    <div class="transcript-line" data-begin="2434.53"><span class="transcript-timestamp">40:34</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="2436.22"><span class="transcript-timestamp">40:36</span><span
            class="transcript-text">That was partial persistence.</span></div>
    <div class="transcript-line" data-begin="2438.11"><span class="transcript-timestamp">40:38</span><span
            class="transcript-text">Let's do full persistence.</span></div>
    <div class="transcript-line" data-begin="2441.54"><span class="transcript-timestamp">40:41</span><span
            class="transcript-text">That was too easy.</span></div>
    <div class="transcript-line" data-begin="2446.3"><span class="transcript-timestamp">40:46</span><span
            class="transcript-text">Same paper does
            full persistence.</span></div>
    <div class="transcript-line" data-begin="2448.97"><span class="transcript-timestamp">40:48</span><span
            class="transcript-text">Systems That was just a warm up.</span></div>
    <div class="transcript-line" data-begin="2450.427"><span class="transcript-timestamp">40:50</span><span
            class="transcript-text">Full persistence is actually
            not that much harder.</span></div>
    <div class="transcript-line" data-begin="2455.07"><span class="transcript-timestamp">40:55</span><span
            class="transcript-text">So let me tell you
            basically what changes.</span></div>
    <div class="transcript-line" data-begin="2464.24"><span class="transcript-timestamp">41:04</span><span
            class="transcript-text">There are two issues.</span></div>
    <div class="transcript-line" data-begin="2465.55"><span class="transcript-timestamp">41:05</span><span
            class="transcript-text">One is that everything here
            has to change and not by much.</span></div>
    <div class="transcript-line" data-begin="2469.44"><span class="transcript-timestamp">41:09</span><span
            class="transcript-text">We're still going to
            use back pointers.</span></div>
    <div class="transcript-line" data-begin="2471.37"><span class="transcript-timestamp">41:11</span><span
            class="transcript-text">We're still going
            to have my mods.</span></div>
    <div class="transcript-line" data-begin="2472.86"><span class="transcript-timestamp">41:12</span><span
            class="transcript-text">The number of mods is going
            to be slightly different</span></div>
    <div class="transcript-line" data-begin="2475.026"><span class="transcript-timestamp">41:15</span><span
            class="transcript-text">but basically the same.</span></div>
    <div class="transcript-line" data-begin="2476.91"><span class="transcript-timestamp">41:16</span><span
            class="transcript-text">Back pointers no longer just
            refer to the latest version.</span></div>
    <div class="transcript-line" data-begin="2479.327"><span class="transcript-timestamp">41:19</span><span
            class="transcript-text">We have to maintain back
            pointers in all versions.</span></div>
    <div class="transcript-line" data-begin="2481.41"><span class="transcript-timestamp">41:21</span><span
            class="transcript-text">So that's annoying.</span></div>
    <div class="transcript-line" data-begin="2482.97"><span class="transcript-timestamp">41:22</span><span
            class="transcript-text">But hey, that's life.</span></div>
    <div class="transcript-line" data-begin="2484.274"><span class="transcript-timestamp">41:24</span><span
            class="transcript-text">The amortization, the
            potential function</span></div>
    <div class="transcript-line" data-begin="2485.94"><span class="transcript-timestamp">41:25</span><span
            class="transcript-text">will change slightly
            but basically not much.</span></div>
    <div class="transcript-line" data-begin="2490.85"><span class="transcript-timestamp">41:30</span><span
            class="transcript-text">Sort of the bigger issue you
            might first wonder about,</span></div>
    <div class="transcript-line" data-begin="2493.116"><span class="transcript-timestamp">41:33</span><span
            class="transcript-text">and it's actually the most
            challenging technically,</span></div>
    <div class="transcript-line" data-begin="2495.24"><span class="transcript-timestamp">41:35</span><span
            class="transcript-text">is versions are
            no longer numbers.</span></div>
    <div class="transcript-line" data-begin="2497.49"><span class="transcript-timestamp">41:37</span><span
            class="transcript-text">Because it's not a line.</span></div>
    <div class="transcript-line" data-begin="2499.14"><span class="transcript-timestamp">41:39</span><span
            class="transcript-text">Versions are nodes in a tree.</span></div>
    <div class="transcript-line" data-begin="2501.247"><span class="transcript-timestamp">41:41</span><span
            class="transcript-text">You should probably
            call them vertices</span></div>
    <div class="transcript-line" data-begin="2502.83"><span class="transcript-timestamp">41:42</span><span
            class="transcript-text">in a tree to distinguish them
            from nodes in the pointer</span></div>
    <div class="transcript-line" data-begin="2505.121"><span class="transcript-timestamp">41:45</span><span
            class="transcript-text">machine.</span></div>
    <div class="transcript-line" data-begin="2506.58"><span class="transcript-timestamp">41:46</span><span
            class="transcript-text">OK, so you've got
            this tree of versions.</span></div>
    <div class="transcript-line" data-begin="2508.53"><span class="transcript-timestamp">41:48</span><span
            class="transcript-text">And then versions are just
            some point on that tree.</span></div>
    <div class="transcript-line" data-begin="2513.93"><span class="transcript-timestamp">41:53</span><span
            class="transcript-text">This is annoying
            because we like lines.</span></div>
    <div class="transcript-line" data-begin="2517.02"><span class="transcript-timestamp">41:57</span><span
            class="transcript-text">We don't like trees as much.</span></div>
    <div class="transcript-line" data-begin="2518.77"><span class="transcript-timestamp">41:58</span><span
            class="transcript-text">So what we're going to
            do is linearize the tree.</span></div>
    <div class="transcript-line" data-begin="2524.32"><span class="transcript-timestamp">42:04</span><span
            class="transcript-text">Like, when in doubt, cheat.</span></div>
    <div class="transcript-line" data-begin="2532.2"><span class="transcript-timestamp">42:12</span><span
            class="transcript-text">How do we do this?</span></div>
    <div class="transcript-line" data-begin="2533.88"><span class="transcript-timestamp">42:13</span><span
            class="transcript-text">With tree traversal.</span></div>
    <div class="transcript-line" data-begin="2535.31"><span class="transcript-timestamp">42:15</span><span
            class="transcript-text">Imagine I'm going to draw
            a super complicated tree</span></div>
    <div class="transcript-line" data-begin="2538.24"><span class="transcript-timestamp">42:18</span><span
            class="transcript-text">of versions.</span></div>
    <div class="transcript-line" data-begin="2539.37"><span class="transcript-timestamp">42:19</span><span
            class="transcript-text">Say there are three versions.</span></div>
    <div class="transcript-line" data-begin="2541.66"><span class="transcript-timestamp">42:21</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2542.807"><span class="transcript-timestamp">42:22</span><span
            class="transcript-text">I don't want to number
            them, because that would be</span></div>
    <div class="transcript-line" data-begin="2544.89"><span class="transcript-timestamp">42:24</span><span
            class="transcript-text">kind of begging the question.</span></div>
    <div class="transcript-line" data-begin="2546.33"><span class="transcript-timestamp">42:26</span><span
            class="transcript-text">So let's just call
            them x, y, and z.</span></div>
    <div class="transcript-line" data-begin="2553.08"><span class="transcript-timestamp">42:33</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="2554.384"><span class="transcript-timestamp">42:34</span><span
            class="transcript-text">I mean, it's a directed
            tree, because we</span></div>
    <div class="transcript-line" data-begin="2556.05"><span class="transcript-timestamp">42:36</span><span
            class="transcript-text">have the older versions.</span></div>
    <div class="transcript-line" data-begin="2557.464"><span class="transcript-timestamp">42:37</span><span
            class="transcript-text">This is like the
            original version.</span></div>
    <div class="transcript-line" data-begin="2558.88"><span class="transcript-timestamp">42:38</span><span
            class="transcript-text">And we made a change.</span></div>
    <div class="transcript-line" data-begin="2559.754"><span class="transcript-timestamp">42:39</span><span
            class="transcript-text">We made a different change
            on the same version.</span></div>
    <div class="transcript-line" data-begin="2562.69"><span class="transcript-timestamp">42:42</span><span
            class="transcript-text">What I'd like to do is a
            traversal of that tree,</span></div>
    <div class="transcript-line" data-begin="2565.52"><span class="transcript-timestamp">42:45</span><span
            class="transcript-text">like a regular, as if you're
            going to sort those nodes.</span></div>
    <div class="transcript-line" data-begin="2568.17"><span class="transcript-timestamp">42:48</span><span
            class="transcript-text">Actually, let me use
            color, high def here.</span></div>
    <div class="transcript-line" data-begin="2573.42"><span class="transcript-timestamp">42:53</span><span
            class="transcript-text">So here's our
            traversal of the tree.</span></div>
    <div class="transcript-line" data-begin="2579.03"><span class="transcript-timestamp">42:59</span><span
            class="transcript-text">And I want to look at the
            first and the last time I</span></div>
    <div class="transcript-line" data-begin="2581.79"><span class="transcript-timestamp">43:01</span><span
            class="transcript-text">visit each node.</span></div>
    <div class="transcript-line" data-begin="2582.73"><span class="transcript-timestamp">43:02</span><span
            class="transcript-text">So here's the first
            time I visit x.</span></div>
    <div class="transcript-line" data-begin="2585.36"><span class="transcript-timestamp">43:05</span><span
            class="transcript-text">So I'll write this is
            the beginning of x.</span></div>
    <div class="transcript-line" data-begin="2589.25"><span class="transcript-timestamp">43:09</span><span
            class="transcript-text">Capital X. Then this is
            the first time I visit y,</span></div>
    <div class="transcript-line" data-begin="2593.55"><span class="transcript-timestamp">43:13</span><span
            class="transcript-text">so it's beginning of y.</span></div>
    <div class="transcript-line" data-begin="2595.53"><span class="transcript-timestamp">43:15</span><span
            class="transcript-text">And then this is the last time
            I visit y, so it's the end of y.</span></div>
    <div class="transcript-line" data-begin="2599.07"><span class="transcript-timestamp">43:19</span><span
            class="transcript-text">And then, don't care.</span></div>
    <div class="transcript-line" data-begin="2600.77"><span class="transcript-timestamp">43:20</span><span
            class="transcript-text">Then this is the beginning of z.</span></div>
    <div class="transcript-line" data-begin="2604.8"><span class="transcript-timestamp">43:24</span><span
            class="transcript-text">And this is the end of z.</span></div>
    <div class="transcript-line" data-begin="2607.23"><span class="transcript-timestamp">43:27</span><span
            class="transcript-text">And then this is the end x.</span></div>
    <div class="transcript-line" data-begin="2609.48"><span class="transcript-timestamp">43:29</span><span
            class="transcript-text">If I write those sequentially,
            I get bxbyeybzez,</span></div>
    <div class="transcript-line" data-begin="2618.83"><span class="transcript-timestamp">43:38</span><span
            class="transcript-text">because this is so easy, ex.</span></div>
    <div class="transcript-line" data-begin="2622.4"><span class="transcript-timestamp">43:42</span><span
            class="transcript-text">OK, you can think of these
            as parentheses, right?</span></div>
    <div class="transcript-line" data-begin="2625.53"><span class="transcript-timestamp">43:45</span><span
            class="transcript-text">For whatever reason I chose b
            and e for beginning and ending,</span></div>
    <div class="transcript-line" data-begin="2628.46"><span class="transcript-timestamp">43:48</span><span
            class="transcript-text">but this is like open
            parens, close parens.</span></div>
    <div class="transcript-line" data-begin="2630.36"><span class="transcript-timestamp">43:50</span><span
            class="transcript-text">This is easy to
            do in linear time.</span></div>
    <div class="transcript-line" data-begin="2632.31"><span class="transcript-timestamp">43:52</span><span
            class="transcript-text">I think you all know how.</span></div>
    <div class="transcript-line" data-begin="2633.69"><span class="transcript-timestamp">43:53</span><span
            class="transcript-text">Except it's not
            a static problem.</span></div>
    <div class="transcript-line" data-begin="2635.066"><span class="transcript-timestamp">43:55</span><span
            class="transcript-text">Versions are changing
            all the time.</span></div>
    <div class="transcript-line" data-begin="2636.523"><span class="transcript-timestamp">43:56</span><span
            class="transcript-text">We're adding versions.</span></div>
    <div class="transcript-line" data-begin="2637.5"><span class="transcript-timestamp">43:57</span><span
            class="transcript-text">We're never deleting
            versions, but we're always</span></div>
    <div class="transcript-line" data-begin="2639.458"><span class="transcript-timestamp">43:59</span><span
            class="transcript-text">adding stuff to here.</span></div>
    <div class="transcript-line" data-begin="2640.422"><span class="transcript-timestamp">44:00</span><span
            class="transcript-text">It's a little
            awkward, but the idea</span></div>
    <div class="transcript-line" data-begin="2641.88"><span class="transcript-timestamp">44:01</span><span
            class="transcript-text">is I want to
            maintain this order,</span></div>
    <div class="transcript-line" data-begin="2645.84"><span class="transcript-timestamp">44:05</span><span
            class="transcript-text">maintain the begin and
            the end of each you</span></div>
    <div class="transcript-line" data-begin="2656.01"><span class="transcript-timestamp">44:16</span><span
            class="transcript-text">might say subtree of versions.</span></div>
    <div class="transcript-line" data-begin="2663.52"><span class="transcript-timestamp">44:23</span><span
            class="transcript-text">This string, from
            bx to ex, represents</span></div>
    <div class="transcript-line" data-begin="2665.77"><span class="transcript-timestamp">44:25</span><span
            class="transcript-text">all of the stuff in x's
            subtree, in the rooted tree</span></div>
    <div class="transcript-line" data-begin="2669.82"><span class="transcript-timestamp">44:29</span><span
            class="transcript-text">starting at x.</span></div>
    <div class="transcript-line" data-begin="2673.89"><span class="transcript-timestamp">44:33</span><span
            class="transcript-text">How do I maintain that?</span></div>
    <div class="transcript-line" data-begin="2680.55"><span class="transcript-timestamp">44:40</span><span
            class="transcript-text">Using a data structure.</span></div>
    <div class="transcript-line" data-begin="2696.49"><span class="transcript-timestamp">44:56</span><span
            class="transcript-text">So we're going to use something,
            a data structure we haven't yet</span></div>
    <div class="transcript-line" data-begin="2700.83"><span class="transcript-timestamp">45:00</span><span
            class="transcript-text">seen.</span></div>
    <div class="transcript-line" data-begin="2702.21"><span class="transcript-timestamp">45:02</span><span
            class="transcript-text">It will be in lecture 8.</span></div>
    <div class="transcript-line" data-begin="2704.899"><span class="transcript-timestamp">45:04</span><span
            class="transcript-text">This is a time travel
            data structure,</span></div>
    <div class="transcript-line" data-begin="2706.44"><span class="transcript-timestamp">45:06</span><span
            class="transcript-text">so I'm allowed to do that.</span></div>
    <div class="transcript-line" data-begin="2710.28"><span class="transcript-timestamp">45:10</span><span
            class="transcript-text">So order maintenance
            data structure.</span></div>
    <div class="transcript-line" data-begin="2714.15"><span class="transcript-timestamp">45:14</span><span
            class="transcript-text">You can think of this as
            a magical linked list.</span></div>
    <div class="transcript-line" data-begin="2716.97"><span class="transcript-timestamp">45:16</span><span
            class="transcript-text">Let me tell you what the
            magical linked list can do.</span></div>
    <div class="transcript-line" data-begin="2719.52"><span class="transcript-timestamp">45:19</span><span
            class="transcript-text">You can insert--</span></div>
    <div class="transcript-line" data-begin="2722.871"><span class="transcript-timestamp">45:22</span><span
            class="transcript-text">I'm going to call it
            an item, because node</span></div>
    <div class="transcript-line" data-begin="2724.62"><span class="transcript-timestamp">45:24</span><span
            class="transcript-text">would be kind of confusing
            given where we are right now.</span></div>
    <div class="transcript-line" data-begin="2728.64"><span class="transcript-timestamp">45:28</span><span
            class="transcript-text">You can insert a new item in
            the list immediately before</span></div>
    <div class="transcript-line" data-begin="2732.48"><span class="transcript-timestamp">45:32</span><span
            class="transcript-text">or after a given item.</span></div>
    <div class="transcript-line" data-begin="2737.41"><span class="transcript-timestamp">45:37</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2737.91"><span class="transcript-timestamp">45:37</span><span
            class="transcript-text">This is like a
            regular linked list.</span></div>
    <div class="transcript-line" data-begin="2741.39"><span class="transcript-timestamp">45:41</span><span
            class="transcript-text">Here's a regular linked list.</span></div>
    <div class="transcript-line" data-begin="2744.75"><span class="transcript-timestamp">45:44</span><span
            class="transcript-text">And if I'm given a particular
            item like this one,</span></div>
    <div class="transcript-line" data-begin="2748.29"><span class="transcript-timestamp">45:48</span><span
            class="transcript-text">I can say, well, insert
            a new item right here.</span></div>
    <div class="transcript-line" data-begin="2751.19"><span class="transcript-timestamp">45:51</span><span
            class="transcript-text">You say, OK.</span></div>
    <div class="transcript-line" data-begin="2751.721"><span class="transcript-timestamp">45:51</span><span
            class="transcript-text">Fine.</span></div>
    <div class="transcript-line" data-begin="2752.22"><span class="transcript-timestamp">45:52</span><span
            class="transcript-text">I'll just make a new node and
            relink here, relink there.</span></div>
    <div class="transcript-line" data-begin="2757.06"><span class="transcript-timestamp">45:57</span><span
            class="transcript-text">Constant time, right?</span></div>
    <div class="transcript-line" data-begin="2758.19"><span class="transcript-timestamp">45:58</span><span
            class="transcript-text">So in an order maintenance
            data structure,</span></div>
    <div class="transcript-line" data-begin="2760.05"><span class="transcript-timestamp">46:00</span><span
            class="transcript-text">you can do this
            in constant time.</span></div>
    <div class="transcript-line" data-begin="2761.94"><span class="transcript-timestamp">46:01</span><span
            class="transcript-text">Wow!</span></div>
    <div class="transcript-line" data-begin="2762.9"><span class="transcript-timestamp">46:02</span><span
            class="transcript-text">So amazing.</span></div>
    <div class="transcript-line" data-begin="2765.18"><span class="transcript-timestamp">46:05</span><span
            class="transcript-text">OK, catch is the second
            operation you can do.</span></div>
    <div class="transcript-line" data-begin="2768.41"><span class="transcript-timestamp">46:08</span><span
            class="transcript-text">Maybe I'll number these.</span></div>
    <div class="transcript-line" data-begin="2769.41"><span class="transcript-timestamp">46:09</span><span
            class="transcript-text">This is the update.</span></div>
    <div class="transcript-line" data-begin="2770.97"><span class="transcript-timestamp">46:10</span><span
            class="transcript-text">Then there's the query.</span></div>
    <div class="transcript-line" data-begin="2773.49"><span class="transcript-timestamp">46:13</span><span
            class="transcript-text">The query is, what
            is the relative order</span></div>
    <div class="transcript-line" data-begin="2777.99"><span class="transcript-timestamp">46:17</span><span
            class="transcript-text">of two notes, of two items?</span></div>
    <div class="transcript-line" data-begin="2784.7"><span class="transcript-timestamp">46:24</span><span
            class="transcript-text">x and y.</span></div>
    <div class="transcript-line" data-begin="2787.09"><span class="transcript-timestamp">46:27</span><span
            class="transcript-text">So now I give you this
            node and this node.</span></div>
    <div class="transcript-line" data-begin="2789.98"><span class="transcript-timestamp">46:29</span><span
            class="transcript-text">And I say, which is to the left?</span></div>
    <div class="transcript-line" data-begin="2792.42"><span class="transcript-timestamp">46:32</span><span
            class="transcript-text">Which is earlier in the order?</span></div>
    <div class="transcript-line" data-begin="2794.03"><span class="transcript-timestamp">46:34</span><span
            class="transcript-text">I want to know, is x
            basically less than y</span></div>
    <div class="transcript-line" data-begin="2796.07"><span class="transcript-timestamp">46:36</span><span
            class="transcript-text">in terms of the
            order in the list?</span></div>
    <div class="transcript-line" data-begin="2797.69"><span class="transcript-timestamp">46:37</span><span
            class="transcript-text">Or is y less than x?</span></div>
    <div class="transcript-line" data-begin="2801.136"><span class="transcript-timestamp">46:41</span><span
            class="transcript-text">And an order maintenance
            data structure</span></div>
    <div class="transcript-line" data-begin="2802.76"><span class="transcript-timestamp">46:42</span><span
            class="transcript-text">can do this in constant time.</span></div>
    <div class="transcript-line" data-begin="2805.91"><span class="transcript-timestamp">46:45</span><span
            class="transcript-text">Now it doesn't look like your
            mother's linked list, I guess.</span></div>
    <div class="transcript-line" data-begin="2810.486"><span class="transcript-timestamp">46:50</span><span
            class="transcript-text">It's not the link list
            you learned in school.</span></div>
    <div class="transcript-line" data-begin="2812.36"><span class="transcript-timestamp">46:52</span><span
            class="transcript-text">It's a magical linked
            list that can somehow</span></div>
    <div class="transcript-line" data-begin="2814.7"><span class="transcript-timestamp">46:54</span><span
            class="transcript-text">answer these queries.</span></div>
    <div class="transcript-line" data-begin="2815.81"><span class="transcript-timestamp">46:55</span><span
            class="transcript-text">How?</span></div>
    <div class="transcript-line" data-begin="2816.51"><span class="transcript-timestamp">46:56</span><span
            class="transcript-text">Go to lecture 7.</span></div>
    <div class="transcript-line" data-begin="2818.77"><span class="transcript-timestamp">46:58</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2819.27"><span class="transcript-timestamp">46:59</span><span
            class="transcript-text">Forward reference,
            lecture 8, sorry.</span></div>
    <div class="transcript-line" data-begin="2823.174"><span class="transcript-timestamp">47:03</span><span
            class="transcript-text">For now, we're just going to
            assume that this magical data</span></div>
    <div class="transcript-line" data-begin="2825.59"><span class="transcript-timestamp">47:05</span><span
            class="transcript-text">structure exists.</span></div>
    <div class="transcript-line" data-begin="2826.74"><span class="transcript-timestamp">47:06</span><span
            class="transcript-text">So in constant
            time, this is great.</span></div>
    <div class="transcript-line" data-begin="2829.34"><span class="transcript-timestamp">47:09</span><span
            class="transcript-text">Because if we're maintaining
            these b's and e's, we</span></div>
    <div class="transcript-line" data-begin="2831.68"><span class="transcript-timestamp">47:11</span><span
            class="transcript-text">want to maintain the order
            that these things appear in.</span></div>
    <div class="transcript-line" data-begin="2836.09"><span class="transcript-timestamp">47:16</span><span
            class="transcript-text">If we want to create
            a new version,</span></div>
    <div class="transcript-line" data-begin="2837.62"><span class="transcript-timestamp">47:17</span><span
            class="transcript-text">like suppose we were
            just creating version z,</span></div>
    <div class="transcript-line" data-begin="2840.41"><span class="transcript-timestamp">47:20</span><span
            class="transcript-text">well, it used to be everything
            without this bz, ez.</span></div>
    <div class="transcript-line" data-begin="2843.14"><span class="transcript-timestamp">47:23</span><span
            class="transcript-text">And we'd just insert two
            items in here, bz and ez.</span></div>
    <div class="transcript-line" data-begin="2847.215"><span class="transcript-timestamp">47:27</span><span
            class="transcript-text">They're right next
            to each other.</span></div>
    <div class="transcript-line" data-begin="2848.59"><span class="transcript-timestamp">47:28</span><span
            class="transcript-text">And if we were given version
            x, we could just say,</span></div>
    <div class="transcript-line" data-begin="2850.82"><span class="transcript-timestamp">47:30</span><span
            class="transcript-text">oh, we'll look at ex and insert
            two items right before it.</span></div>
    <div class="transcript-line" data-begin="2854.3"><span class="transcript-timestamp">47:34</span><span
            class="transcript-text">Or you can put them
            right after bx.</span></div>
    <div class="transcript-line" data-begin="2856.069"><span class="transcript-timestamp">47:36</span><span
            class="transcript-text">I mean, there's no
            actual order here.</span></div>
    <div class="transcript-line" data-begin="2857.61"><span class="transcript-timestamp">47:37</span><span
            class="transcript-text">So it could have been y first
            and then z or z first and then</span></div>
    <div class="transcript-line" data-begin="2860.69"><span class="transcript-timestamp">47:40</span><span
            class="transcript-text">y.</span></div>
    <div class="transcript-line" data-begin="2862.07"><span class="transcript-timestamp">47:42</span><span
            class="transcript-text">So it's really easy to add a
            new version in constant time.</span></div>
    <div class="transcript-line" data-begin="2864.61"><span class="transcript-timestamp">47:44</span><span
            class="transcript-text">You just do two of
            these insert operations.</span></div>
    <div class="transcript-line" data-begin="2867.59"><span class="transcript-timestamp">47:47</span><span
            class="transcript-text">And now you have this magical
            order operation, which</span></div>
    <div class="transcript-line" data-begin="2870.68"><span class="transcript-timestamp">47:50</span><span
            class="transcript-text">if I'm given two versions--</span></div>
    <div class="transcript-line" data-begin="2874.5"><span class="transcript-timestamp">47:54</span><span
            class="transcript-text">I don't know, v and w--</span></div>
    <div class="transcript-line" data-begin="2876.8"><span class="transcript-timestamp">47:56</span><span
            class="transcript-text">and I want to know is
            v an ancestor of w,</span></div>
    <div class="transcript-line" data-begin="2880.25"><span class="transcript-timestamp">48:00</span><span
            class="transcript-text">now I can do it
            in constant time.</span></div>
    <div class="transcript-line" data-begin="2882.39"><span class="transcript-timestamp">48:02</span><span
            class="transcript-text">So this lets me do a third
            operation, which is, is version</span></div>
    <div class="transcript-line" data-begin="2889.7"><span class="transcript-timestamp">48:09</span><span
            class="transcript-text">v an ancestor of version w?</span></div>
    <div class="transcript-line" data-begin="2901.85"><span class="transcript-timestamp">48:21</span><span
            class="transcript-text">Because that's going to
            be true if and only if bv</span></div>
    <div class="transcript-line" data-begin="2906.35"><span class="transcript-timestamp">48:26</span><span
            class="transcript-text">is an ev nest around bw and ew.</span></div>
    <div class="transcript-line" data-begin="2919.71"><span class="transcript-timestamp">48:39</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="2920.29"><span class="transcript-timestamp">48:40</span><span
            class="transcript-text">So that's just three tests.</span></div>
    <div class="transcript-line" data-begin="2921.92"><span class="transcript-timestamp">48:41</span><span
            class="transcript-text">They're probably not
            all even necessary.</span></div>
    <div class="transcript-line" data-begin="2923.98"><span class="transcript-timestamp">48:43</span><span
            class="transcript-text">This one always holds.</span></div>
    <div class="transcript-line" data-begin="2925.39"><span class="transcript-timestamp">48:45</span><span
            class="transcript-text">But if these guys fit in between
            these guys, then you know--</span></div>
    <div class="transcript-line" data-begin="2930.67"><span class="transcript-timestamp">48:50</span><span
            class="transcript-text">now, what this tells us,
            what we care about here,</span></div>
    <div class="transcript-line" data-begin="2934.81"><span class="transcript-timestamp">48:54</span><span
            class="transcript-text">is reading fields.</span></div>
    <div class="transcript-line" data-begin="2938.02"><span class="transcript-timestamp">48:58</span><span
            class="transcript-text">When we read a field,
            we said, oh, we'll</span></div>
    <div class="transcript-line" data-begin="2940.3"><span class="transcript-timestamp">49:00</span><span
            class="transcript-text">apply all the modifications
            that apply to version</span></div>
    <div class="transcript-line" data-begin="2942.67"><span class="transcript-timestamp">49:02</span><span
            class="transcript-text">v. Before that, that
            was a linear order.</span></div>
    <div class="transcript-line" data-begin="2944.51"><span class="transcript-timestamp">49:04</span><span
            class="transcript-text">So it's just all versions
            less than or equal to v. Now</span></div>
    <div class="transcript-line" data-begin="2946.9"><span class="transcript-timestamp">49:06</span><span
            class="transcript-text">it's all versions that are
            ancestors of v. Given a mod,</span></div>
    <div class="transcript-line" data-begin="2950.8"><span class="transcript-timestamp">49:10</span><span
            class="transcript-text">we need to know, does this
            mod apply to my version?</span></div>
    <div class="transcript-line" data-begin="2953.83"><span class="transcript-timestamp">49:13</span><span
            class="transcript-text">And now I tell you, I can
            do that in constant time</span></div>
    <div class="transcript-line" data-begin="2956.56"><span class="transcript-timestamp">49:16</span><span
            class="transcript-text">through magic.</span></div>
    <div class="transcript-line" data-begin="2957.61"><span class="transcript-timestamp">49:17</span><span
            class="transcript-text">I just test these
            order relations.</span></div>
    <div class="transcript-line" data-begin="2960.34"><span class="transcript-timestamp">49:20</span><span
            class="transcript-text">If they hold, then that
            mod applies to my version.</span></div>
    <div class="transcript-line" data-begin="2964.36"><span class="transcript-timestamp">49:24</span><span
            class="transcript-text">So w's the version
            we're testing.</span></div>
    <div class="transcript-line" data-begin="2967.36"><span class="transcript-timestamp">49:27</span><span
            class="transcript-text">v is some version in the mod.</span></div>
    <div class="transcript-line" data-begin="2969.43"><span class="transcript-timestamp">49:29</span><span
            class="transcript-text">And I want to know, am
            descendant of that version?</span></div>
    <div class="transcript-line" data-begin="2972.07"><span class="transcript-timestamp">49:32</span><span
            class="transcript-text">If so, the mod applies.</span></div>
    <div class="transcript-line" data-begin="2974.1"><span class="transcript-timestamp">49:34</span><span
            class="transcript-text">And I update what the field is.</span></div>
    <div class="transcript-line" data-begin="2976.63"><span class="transcript-timestamp">49:36</span><span
            class="transcript-text">I can do all pairwise ancestor
            checks and figure out,</span></div>
    <div class="transcript-line" data-begin="2979.03"><span class="transcript-timestamp">49:39</span><span
            class="transcript-text">what is the most recent
            version in my ancestor history</span></div>
    <div class="transcript-line" data-begin="2983.2"><span class="transcript-timestamp">49:43</span><span
            class="transcript-text">that modified a given field?</span></div>
    <div class="transcript-line" data-begin="2984.85"><span class="transcript-timestamp">49:44</span><span
            class="transcript-text">That lets me read a
            field in constant time.</span></div>
    <div class="transcript-line" data-begin="2987.08"><span class="transcript-timestamp">49:47</span><span
            class="transcript-text">Constants are getting
            kind of big at this point,</span></div>
    <div class="transcript-line" data-begin="2989.08"><span class="transcript-timestamp">49:49</span><span
            class="transcript-text">but it can be done.</span></div>
    <div class="transcript-line" data-begin="2993.27"><span class="transcript-timestamp">49:53</span><span
            class="transcript-text">Clear?</span></div>
    <div class="transcript-line" data-begin="2994.55"><span class="transcript-timestamp">49:54</span><span
            class="transcript-text">A little bit of
            a black box here.</span></div>
    <div class="transcript-line" data-begin="2996.85"><span class="transcript-timestamp">49:56</span><span
            class="transcript-text">But now we've gotten
            as far as reading.</span></div>
    <div class="transcript-line" data-begin="3001.92"><span class="transcript-timestamp">50:01</span><span
            class="transcript-text">And we don't need
            to change much else.</span></div>
    <div class="transcript-line" data-begin="3004.75"><span class="transcript-timestamp">50:04</span><span
            class="transcript-text">So this is good news</span></div>
    <div class="transcript-line" data-begin="3011.78"><span class="transcript-timestamp">50:11</span><span
            class="transcript-text">Maybe I'll give you
            a bit of a diff.</span></div>
    <div class="transcript-line" data-begin="3015.28"><span class="transcript-timestamp">50:15</span><span
            class="transcript-text">So full persistence,
            fully persistent theorem--</span></div>
    <div class="transcript-line" data-begin="3026.34"><span class="transcript-timestamp">50:26</span><span
            class="transcript-text">done.</span></div>
    <div class="transcript-line" data-begin="3027.21"><span class="transcript-timestamp">50:27</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3027.71"><span class="transcript-timestamp">50:27</span><span
            class="transcript-text">Same theorem just
            with full persistence.</span></div>
    <div class="transcript-line" data-begin="3030.08"><span class="transcript-timestamp">50:30</span><span
            class="transcript-text">How do we do it?</span></div>
    <div class="transcript-line" data-begin="3031.23"><span class="transcript-timestamp">50:31</span><span
            class="transcript-text">We store back pointers
            now for all versions.</span></div>
    <div class="transcript-line" data-begin="3035.542"><span class="transcript-timestamp">50:35</span><span
            class="transcript-text">It's a little bit annoying.</span></div>
    <div class="transcript-line" data-begin="3036.87"><span class="transcript-timestamp">50:36</span><span
            class="transcript-text">But how many mods do we use?</span></div>
    <div class="transcript-line" data-begin="3040.832"><span class="transcript-timestamp">50:40</span><span
            class="transcript-text">There's lots of ways
            to get this to work,</span></div>
    <div class="transcript-line" data-begin="3042.54"><span class="transcript-timestamp">50:42</span><span
            class="transcript-text">but I'm going to
            change this number</span></div>
    <div class="transcript-line" data-begin="3044.89"><span class="transcript-timestamp">50:44</span><span
            class="transcript-text">to 2 times d plus p plus 1.</span></div>
    <div class="transcript-line" data-begin="3051.702"><span class="transcript-timestamp">50:51</span><span
            class="transcript-text">Wait, what's d? d is the
            number of fields here.</span></div>
    <div class="transcript-line" data-begin="3056.45"><span class="transcript-timestamp">50:56</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3057.14"><span class="transcript-timestamp">50:57</span><span
            class="transcript-text">We said it was
            constant number fields.</span></div>
    <div class="transcript-line" data-begin="3059.15"><span class="transcript-timestamp">50:59</span><span
            class="transcript-text">I never said what that constant
            is. d for out degree, I guess.</span></div>
    <div class="transcript-line" data-begin="3063.68"><span class="transcript-timestamp">51:03</span><span
            class="transcript-text">So p is in degree, max in
            degree. d is max out degree.</span></div>
    <div class="transcript-line" data-begin="3069.289"><span class="transcript-timestamp">51:09</span><span
            class="transcript-text">So just slightly more--
            that main reason for this</span></div>
    <div class="transcript-line" data-begin="3071.33"><span class="transcript-timestamp">51:11</span><span
            class="transcript-text">is because back pointers now
            are treated like everyone else.</span></div>
    <div class="transcript-line" data-begin="3074.45"><span class="transcript-timestamp">51:14</span><span
            class="transcript-text">We have to treat both the out
            pointers and the in pointers</span></div>
    <div class="transcript-line" data-begin="3077.434"><span class="transcript-timestamp">51:17</span><span
            class="transcript-text">as basically the same.</span></div>
    <div class="transcript-line" data-begin="3078.35"><span class="transcript-timestamp">51:18</span><span
            class="transcript-text">So instead of p,
            we have d plus p.</span></div>
    <div class="transcript-line" data-begin="3079.88"><span class="transcript-timestamp">51:19</span><span
            class="transcript-text">And there's a plus
            1 just for safety.</span></div>
    <div class="transcript-line" data-begin="3083.231"><span class="transcript-timestamp">51:23</span><span
            class="transcript-text">It gets my amortization
            to work, hopefully.</span></div>
    <div class="transcript-line" data-begin="3088.33"><span class="transcript-timestamp">51:28</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3089.32"><span class="transcript-timestamp">51:29</span><span
            class="transcript-text">Not much else-- this
            page is all the same.</span></div>
    <div class="transcript-line" data-begin="3092.43"><span class="transcript-timestamp">51:32</span><span
            class="transcript-text">Mods are still, you give
            versions, fields, values,</span></div>
    <div class="transcript-line" data-begin="3095.83"><span class="transcript-timestamp">51:35</span><span
            class="transcript-text">reading.</span></div>
    <div class="transcript-line" data-begin="3096.62"><span class="transcript-timestamp">51:36</span><span
            class="transcript-text">OK, well, this is no longer
            less than or equal to v. But</span></div>
    <div class="transcript-line" data-begin="3101.03"><span class="transcript-timestamp">51:41</span><span
            class="transcript-text">this is now with a version, sort
            of the nearest version, that's</span></div>
    <div class="transcript-line" data-begin="3107.06"><span class="transcript-timestamp">51:47</span><span
            class="transcript-text">an ancestor of v.</span></div>
    <div class="transcript-line" data-begin="3110.66"><span class="transcript-timestamp">51:50</span><span
            class="transcript-text">That's what we were
            just talking about.</span></div>
    <div class="transcript-line" data-begin="3112.719"><span class="transcript-timestamp">51:52</span><span
            class="transcript-text">So that can be done
            in constant time.</span></div>
    <div class="transcript-line" data-begin="3114.26"><span class="transcript-timestamp">51:54</span><span
            class="transcript-text">Check it for all of
            them, constant work.</span></div>
    <div class="transcript-line" data-begin="3117.4"><span class="transcript-timestamp">51:57</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3118.13"><span class="transcript-timestamp">51:58</span><span
            class="transcript-text">That was the first part.</span></div>
    <div class="transcript-line" data-begin="3124.71"><span class="transcript-timestamp">52:04</span><span
            class="transcript-text">Now we get to the hard
            part, which is modification.</span></div>
    <div class="transcript-line" data-begin="3127.16"><span class="transcript-timestamp">52:07</span><span
            class="transcript-text">This is going to be different.</span></div>
    <div class="transcript-line" data-begin="3128.41"><span class="transcript-timestamp">52:08</span><span
            class="transcript-text">Maybe you I should just erase--</span></div>
    <div class="transcript-line" data-begin="3130.81"><span class="transcript-timestamp">52:10</span><span
            class="transcript-text">yeah, I think I'll
            erase everything,</span></div>
    <div class="transcript-line" data-begin="3133.69"><span class="transcript-timestamp">52:13</span><span
            class="transcript-text">except the first clause.</span></div>
    <div class="transcript-line" data-begin="3144.27"><span class="transcript-timestamp">52:24</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3144.89"><span class="transcript-timestamp">52:24</span><span
            class="transcript-text">If a node is not
            full, we'll just</span></div>
    <div class="transcript-line" data-begin="3146.91"><span class="transcript-timestamp">52:26</span><span
            class="transcript-text">add a mod, just like before.</span></div>
    <div class="transcript-line" data-begin="3148.46"><span class="transcript-timestamp">52:28</span><span
            class="transcript-text">What changes is
            when a node is full.</span></div>
    <div class="transcript-line" data-begin="3156"><span class="transcript-timestamp">52:36</span><span
            class="transcript-text">Here we have to do something
            completely different.</span></div>
    <div class="transcript-line" data-begin="3158.22"><span class="transcript-timestamp">52:38</span><span
            class="transcript-text">Why?</span></div>
    <div class="transcript-line" data-begin="3158.91"><span class="transcript-timestamp">52:38</span><span
            class="transcript-text">Because if we just
            make a new version</span></div>
    <div class="transcript-line" data-begin="3161.07"><span class="transcript-timestamp">52:41</span><span
            class="transcript-text">of this node that has empty
            mods, this one's still full.</span></div>
    <div class="transcript-line" data-begin="3165.05"><span class="transcript-timestamp">52:45</span><span
            class="transcript-text">And I can keep modifying
            the same version.</span></div>
    <div class="transcript-line" data-begin="3168.81"><span class="transcript-timestamp">52:48</span><span
            class="transcript-text">This new node that I just erased
            represents some new version.</span></div>
    <div class="transcript-line" data-begin="3172.83"><span class="transcript-timestamp">52:52</span><span
            class="transcript-text">But if I keep modifying
            an old version, which</span></div>
    <div class="transcript-line" data-begin="3174.72"><span class="transcript-timestamp">52:54</span><span
            class="transcript-text">I can do in full persistence,
            this node keeps being full.</span></div>
    <div class="transcript-line" data-begin="3177.76"><span class="transcript-timestamp">52:57</span><span
            class="transcript-text">And I keep paying
            potentially huge cost.</span></div>
    <div class="transcript-line" data-begin="3180.019"><span class="transcript-timestamp">53:00</span><span
            class="transcript-text">If all the nodes were full,
            and when I make this change</span></div>
    <div class="transcript-line" data-begin="3182.31"><span class="transcript-timestamp">53:02</span><span
            class="transcript-text">every node gets
            copied, and then I</span></div>
    <div class="transcript-line" data-begin="3184.764"><span class="transcript-timestamp">53:04</span><span
            class="transcript-text">make a change to
            the same version,</span></div>
    <div class="transcript-line" data-begin="3186.18"><span class="transcript-timestamp">53:06</span><span
            class="transcript-text">every node gets copied again.</span></div>
    <div class="transcript-line" data-begin="3187.388"><span class="transcript-timestamp">53:07</span><span
            class="transcript-text">This is going to take
            linear time per operation.</span></div>
    <div class="transcript-line" data-begin="3189.86"><span class="transcript-timestamp">53:09</span><span
            class="transcript-text">So I can't do the old strategy.</span></div>
    <div class="transcript-line" data-begin="3191.94"><span class="transcript-timestamp">53:11</span><span
            class="transcript-text">I need to somehow make
            this node less full.</span></div>
    <div class="transcript-line" data-begin="3195.304"><span class="transcript-timestamp">53:15</span><span
            class="transcript-text">This is where we're
            definitely not functional.</span></div>
    <div class="transcript-line" data-begin="3197.22"><span class="transcript-timestamp">53:17</span><span
            class="transcript-text">None of this was
            functional, but now I'm</span></div>
    <div class="transcript-line" data-begin="3199.05"><span class="transcript-timestamp">53:19</span><span
            class="transcript-text">going to change an old node, not
            just make a new one in a more</span></div>
    <div class="transcript-line" data-begin="3204.24"><span class="transcript-timestamp">53:24</span><span
            class="transcript-text">drastic way.</span></div>
    <div class="transcript-line" data-begin="3205.86"><span class="transcript-timestamp">53:25</span><span
            class="transcript-text">Before I was adding a mod.</span></div>
    <div class="transcript-line" data-begin="3207.06"><span class="transcript-timestamp">53:27</span><span
            class="transcript-text">That's not a
            functional operation.</span></div>
    <div class="transcript-line" data-begin="3208.56"><span class="transcript-timestamp">53:28</span><span
            class="transcript-text">Now I'm actually going to remove
            mods from a node to rebalance.</span></div>
    <div class="transcript-line" data-begin="3213.87"><span class="transcript-timestamp">53:33</span><span
            class="transcript-text">So what I'd like to do is
            split the node into two halves.</span></div>
    <div class="transcript-line" data-begin="3223.05"><span class="transcript-timestamp">53:43</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3223.55"><span class="transcript-timestamp">53:43</span><span
            class="transcript-text">So I had some big
            node that was--</span></div>
    <div class="transcript-line" data-begin="3226.295"><span class="transcript-timestamp">53:46</span><span
            class="transcript-text">I'll draw it-- completely full.</span></div>
    <div class="transcript-line" data-begin="3230.19"><span class="transcript-timestamp">53:50</span><span
            class="transcript-text">Now I'm going to make two nodes.</span></div>
    <div class="transcript-line" data-begin="3232.89"><span class="transcript-timestamp">53:52</span><span
            class="transcript-text">Here we go.</span></div>
    <div class="transcript-line" data-begin="3239.02"><span class="transcript-timestamp">53:59</span><span
            class="transcript-text">This one is going
            to be half full.</span></div>
    <div class="transcript-line" data-begin="3241.03"><span class="transcript-timestamp">54:01</span><span
            class="transcript-text">This one's going to
            be half full of mods.</span></div>
    <div class="transcript-line" data-begin="3244.93"><span class="transcript-timestamp">54:04</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3245.46"><span class="transcript-timestamp">54:05</span><span
            class="transcript-text">The only question left is, what
            do I do with all these things?</span></div>
    <div class="transcript-line" data-begin="3252.15"><span class="transcript-timestamp">54:12</span><span
            class="transcript-text">Basically what I'd like
            to do is have the--</span></div>
    <div class="transcript-line" data-begin="3254.7"><span class="transcript-timestamp">54:14</span><span
            class="transcript-text">on the one hand, I want
            to have the old node.</span></div>
    <div class="transcript-line" data-begin="3258.72"><span class="transcript-timestamp">54:18</span><span
            class="transcript-text">It's just where it used to be.</span></div>
    <div class="transcript-line" data-begin="3260.55"><span class="transcript-timestamp">54:20</span><span
            class="transcript-text">I've just removed half of
            the mods, the second half,</span></div>
    <div class="transcript-line" data-begin="3263.82"><span class="transcript-timestamp">54:23</span><span
            class="transcript-text">the later half.</span></div>
    <div class="transcript-line" data-begin="3265.71"><span class="transcript-timestamp">54:25</span><span
            class="transcript-text">What does that mean?</span></div>
    <div class="transcript-line" data-begin="3266.74"><span class="transcript-timestamp">54:26</span><span
            class="transcript-text">I don't know.</span></div>
    <div class="transcript-line" data-begin="3267.42"><span class="transcript-timestamp">54:27</span><span
            class="transcript-text">Figure it out.</span></div>
    <div class="transcript-line" data-begin="3269.32"><span class="transcript-timestamp">54:29</span><span
            class="transcript-text">It's linearized.</span></div>
    <div class="transcript-line" data-begin="3271.05"><span class="transcript-timestamp">54:31</span><span
            class="transcript-text">I haven't thought
            deeply about that.</span></div>
    <div class="transcript-line" data-begin="3272.71"><span class="transcript-timestamp">54:32</span><span
            class="transcript-text">Now we're going to make a
            new node with the second half</span></div>
    <div class="transcript-line" data-begin="3276.3"><span class="transcript-timestamp">54:36</span><span
            class="transcript-text">of the mods.</span></div>
    <div class="transcript-line" data-begin="3280.16"><span class="transcript-timestamp">54:40</span><span
            class="transcript-text">It's more painful
            than I thought.</span></div>
    <div class="transcript-line" data-begin="3281.64"><span class="transcript-timestamp">54:41</span><span
            class="transcript-text">In reality, these mods represent
            a tree of modifications.</span></div>
    <div class="transcript-line" data-begin="3285.18"><span class="transcript-timestamp">54:45</span><span
            class="transcript-text">And what you need to do is
            find a partition of that tree</span></div>
    <div class="transcript-line" data-begin="3288.45"><span class="transcript-timestamp">54:48</span><span
            class="transcript-text">into two roughly equal halves.</span></div>
    <div class="transcript-line" data-begin="3291"><span class="transcript-timestamp">54:51</span><span
            class="transcript-text">You can actually do a
            one third, 2/3 split.</span></div>
    <div class="transcript-line" data-begin="3292.87"><span class="transcript-timestamp">54:52</span><span
            class="transcript-text">That's also in a future lecture,
            which whose number I forget.</span></div>
    <div class="transcript-line" data-begin="3297.049"><span class="transcript-timestamp">54:57</span><span
            class="transcript-text">So really, you're
            splitting this tree</span></div>
    <div class="transcript-line" data-begin="3298.59"><span class="transcript-timestamp">54:58</span><span
            class="transcript-text">into two roughly
            balanced halves.</span></div>
    <div class="transcript-line" data-begin="3301.44"><span class="transcript-timestamp">55:01</span><span
            class="transcript-text">And so this 2 might actually
            need to change to a 3,</span></div>
    <div class="transcript-line" data-begin="3303.75"><span class="transcript-timestamp">55:03</span><span
            class="transcript-text">but it's a constant.</span></div>
    <div class="transcript-line" data-begin="3306.33"><span class="transcript-timestamp">55:06</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3307.59"><span class="transcript-timestamp">55:07</span><span
            class="transcript-text">What I want is for
            this to represent</span></div>
    <div class="transcript-line" data-begin="3309.33"><span class="transcript-timestamp">55:09</span><span
            class="transcript-text">a subtree of versions.</span></div>
    <div class="transcript-line" data-begin="3310.35"><span class="transcript-timestamp">55:10</span><span
            class="transcript-text">Let me draw the picture.</span></div>
    <div class="transcript-line" data-begin="3311.86"><span class="transcript-timestamp">55:11</span><span
            class="transcript-text">So here's a tree of versions
            represented by the old mods.</span></div>
    <div class="transcript-line" data-begin="3315.18"><span class="transcript-timestamp">55:15</span><span
            class="transcript-text">I'd like to cut out a
            subtree rooted at some node.</span></div>
    <div class="transcript-line" data-begin="3318.58"><span class="transcript-timestamp">55:18</span><span
            class="transcript-text">So let's just assume
            for now this has exactly</span></div>
    <div class="transcript-line" data-begin="3321.54"><span class="transcript-timestamp">55:21</span><span
            class="transcript-text">half the nodes.</span></div>
    <div class="transcript-line" data-begin="3322.89"><span class="transcript-timestamp">55:22</span><span
            class="transcript-text">And this has half the nodes.</span></div>
    <div class="transcript-line" data-begin="3325.47"><span class="transcript-timestamp">55:25</span><span
            class="transcript-text">In reality, I think it
            can be one third, 2/3.</span></div>
    <div class="transcript-line" data-begin="3329.18"><span class="transcript-timestamp">55:29</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3329.68"><span class="transcript-timestamp">55:29</span><span
            class="transcript-text">But let's keep it convenient.</span></div>
    <div class="transcript-line" data-begin="3332.93"><span class="transcript-timestamp">55:32</span><span
            class="transcript-text">So I want the new
            node to represent</span></div>
    <div class="transcript-line" data-begin="3334.75"><span class="transcript-timestamp">55:34</span><span
            class="transcript-text">this subtree and this node
            to represent everything else.</span></div>
    <div class="transcript-line" data-begin="3337.63"><span class="transcript-timestamp">55:37</span><span
            class="transcript-text">This node is as if this
            stuff hasn't happened yet.</span></div>
    <div class="transcript-line" data-begin="3341.65"><span class="transcript-timestamp">55:41</span><span
            class="transcript-text">I mean, so it represents all
            these old versions that do not,</span></div>
    <div class="transcript-line" data-begin="3344.714"><span class="transcript-timestamp">55:44</span><span
            class="transcript-text">that are not in the subtree.</span></div>
    <div class="transcript-line" data-begin="3345.88"><span class="transcript-timestamp">55:45</span><span
            class="transcript-text">This represents all
            the latest stuff.</span></div>
    <div class="transcript-line" data-begin="3347.8"><span class="transcript-timestamp">55:47</span><span
            class="transcript-text">So what I'm going to
            do is like before, I</span></div>
    <div class="transcript-line" data-begin="3349.75"><span class="transcript-timestamp">55:49</span><span
            class="transcript-text">want to apply some
            mods to these fields.</span></div>
    <div class="transcript-line" data-begin="3354.09"><span class="transcript-timestamp">55:54</span><span
            class="transcript-text">And whatever minds were
            relevant at this point, whatever</span></div>
    <div class="transcript-line" data-begin="3358.32"><span class="transcript-timestamp">55:58</span><span
            class="transcript-text">had been applied, I apply
            those to the fields here.</span></div>
    <div class="transcript-line" data-begin="3362.61"><span class="transcript-timestamp">56:02</span><span
            class="transcript-text">And so that means I can
            remove all of these mods.</span></div>
    <div class="transcript-line" data-begin="3366.9"><span class="transcript-timestamp">56:06</span><span
            class="transcript-text">I only cared about these ones.</span></div>
    <div class="transcript-line" data-begin="3369.36"><span class="transcript-timestamp">56:09</span><span
            class="transcript-text">Update these fields accordingly.</span></div>
    <div class="transcript-line" data-begin="3371.22"><span class="transcript-timestamp">56:11</span><span
            class="transcript-text">I still have the other mods to
            represent all the other changes</span></div>
    <div class="transcript-line" data-begin="3374.04"><span class="transcript-timestamp">56:14</span><span
            class="transcript-text">that could be in that subtree.</span></div>
    <div class="transcript-line" data-begin="3376.03"><span class="transcript-timestamp">56:16</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3376.53"><span class="transcript-timestamp">56:16</span><span
            class="transcript-text">So we actually split the tree,
            and we apply mods to new nodes.</span></div>
    <div class="transcript-line" data-begin="3398.68"><span class="transcript-timestamp">56:38</span><span
            class="transcript-text">Anything else I need to say?</span></div>
    <div class="transcript-line" data-begin="3402.542"><span class="transcript-timestamp">56:42</span><span
            class="transcript-text">Oh, now we need to
            update pointers.</span></div>
    <div class="transcript-line" data-begin="3404"><span class="transcript-timestamp">56:44</span><span
            class="transcript-text">That's always the fun part.</span></div>
    <div class="transcript-line" data-begin="3409.55"><span class="transcript-timestamp">56:49</span><span
            class="transcript-text">Let's go over here.</span></div>
    <div class="transcript-line" data-begin="3425.3"><span class="transcript-timestamp">57:05</span><span
            class="transcript-text">So old node hasn't moved.</span></div>
    <div class="transcript-line" data-begin="3427.49"><span class="transcript-timestamp">57:07</span><span
            class="transcript-text">But this new node has moved.</span></div>
    <div class="transcript-line" data-begin="3429.15"><span class="transcript-timestamp">57:09</span><span
            class="transcript-text">So for all of these
            versions, I want</span></div>
    <div class="transcript-line" data-begin="3433.88"><span class="transcript-timestamp">57:13</span><span
            class="transcript-text">to change the pointer that
            used to point to old node</span></div>
    <div class="transcript-line" data-begin="3438.02"><span class="transcript-timestamp">57:18</span><span
            class="transcript-text">should now point to new node.</span></div>
    <div class="transcript-line" data-begin="3440.806"><span class="transcript-timestamp">57:20</span><span
            class="transcript-text">In this version, it's fine.</span></div>
    <div class="transcript-line" data-begin="3441.93"><span class="transcript-timestamp">57:21</span><span
            class="transcript-text">It should still
            point to old node,</span></div>
    <div class="transcript-line" data-begin="3443.15"><span class="transcript-timestamp">57:23</span><span
            class="transcript-text">because this represents
            all those old versions.</span></div>
    <div class="transcript-line" data-begin="3445.28"><span class="transcript-timestamp">57:25</span><span
            class="transcript-text">But for the new version,
            that version in the subtree,</span></div>
    <div class="transcript-line" data-begin="3448.17"><span class="transcript-timestamp">57:28</span><span
            class="transcript-text">I've got to point here instead.</span></div>
    <div class="transcript-line" data-begin="3450.781"><span class="transcript-timestamp">57:30</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3451.28"><span class="transcript-timestamp">57:31</span><span
            class="transcript-text">So how many pointers could
            there be to this node</span></div>
    <div class="transcript-line" data-begin="3457.33"><span class="transcript-timestamp">57:37</span><span
            class="transcript-text">that need to change.</span></div>
    <div class="transcript-line" data-begin="3458.85"><span class="transcript-timestamp">57:38</span><span
            class="transcript-text">That's a tricky part
            in this analysis.</span></div>
    <div class="transcript-line" data-begin="3461.63"><span class="transcript-timestamp">57:41</span><span
            class="transcript-text">Think about it for a while.</span></div>
    <div class="transcript-line" data-begin="3465.2"><span class="transcript-timestamp">57:45</span><span
            class="transcript-text">I mean, in this
            new node, whatever</span></div>
    <div class="transcript-line" data-begin="3467.2"><span class="transcript-timestamp">57:47</span><span
            class="transcript-text">is pointed to by either here or
            here in the new node also has</span></div>
    <div class="transcript-line" data-begin="3470.222"><span class="transcript-timestamp">57:50</span><span
            class="transcript-text">a return pointer.</span></div>
    <div class="transcript-line" data-begin="3470.93"><span class="transcript-timestamp">57:50</span><span
            class="transcript-text">All pointers are bidirectional.</span></div>
    <div class="transcript-line" data-begin="3472.13"><span class="transcript-timestamp">57:52</span><span
            class="transcript-text">So we don't really care
            about whether they're forward</span></div>
    <div class="transcript-line" data-begin="3474.338"><span class="transcript-timestamp">57:54</span><span
            class="transcript-text">or backward.</span></div>
    <div class="transcript-line" data-begin="3474.926"><span class="transcript-timestamp">57:54</span><span
            class="transcript-text">How many pointers
            are there here?</span></div>
    <div class="transcript-line" data-begin="3476.3"><span class="transcript-timestamp">57:56</span><span
            class="transcript-text">Well, there's d here
            and there's p here.</span></div>
    <div class="transcript-line" data-begin="3479.36"><span class="transcript-timestamp">57:59</span><span
            class="transcript-text">But then there's also
            some additional pointers</span></div>
    <div class="transcript-line" data-begin="3481.28"><span class="transcript-timestamp">58:01</span><span
            class="transcript-text">represented over here.</span></div>
    <div class="transcript-line" data-begin="3482.75"><span class="transcript-timestamp">58:02</span><span
            class="transcript-text">How many?</span></div>
    <div class="transcript-line" data-begin="3484.1"><span class="transcript-timestamp">58:04</span><span
            class="transcript-text">Well, if we assume this
            magical 50/50 split,</span></div>
    <div class="transcript-line" data-begin="3486.89"><span class="transcript-timestamp">58:06</span><span
            class="transcript-text">there's right now d plus p plus
            1 mods over here, half of them.</span></div>
    <div class="transcript-line" data-begin="3492.92"><span class="transcript-timestamp">58:12</span><span
            class="transcript-text">Each of them might be a pointer
            to some other place, which</span></div>
    <div class="transcript-line" data-begin="3496.1"><span class="transcript-timestamp">58:16</span><span
            class="transcript-text">has a return pointer
            in that version.</span></div>
    <div class="transcript-line" data-begin="3498.715"><span class="transcript-timestamp">58:18</span><span
            class="transcript-text">So number of back pointers
            that we need to update</span></div>
    <div class="transcript-line" data-begin="3503.69"><span class="transcript-timestamp">58:23</span><span
            class="transcript-text">is going to be this, 2
            times d 2 times p plus 1.</span></div>
    <div class="transcript-line" data-begin="3510.7"><span class="transcript-timestamp">58:30</span><span
            class="transcript-text">So recursively update at
            most 2 times d plus 2 times p</span></div>
    <div class="transcript-line" data-begin="3521.85"><span class="transcript-timestamp">58:41</span><span
            class="transcript-text">plus 1 pointers to the node.</span></div>
    <div class="transcript-line" data-begin="3530.27"><span class="transcript-timestamp">58:50</span><span
            class="transcript-text">The good news is this is
            really only half of them</span></div>
    <div class="transcript-line" data-begin="3532.55"><span class="transcript-timestamp">58:52</span><span
            class="transcript-text">or some fraction of them.</span></div>
    <div class="transcript-line" data-begin="3534.85"><span class="transcript-timestamp">58:54</span><span
            class="transcript-text">It used to be--</span></div>
    <div class="transcript-line" data-begin="3537.417"><span class="transcript-timestamp">58:57</span><span
            class="transcript-text">well, there were
            more pointers before.</span></div>
    <div class="transcript-line" data-begin="3539"><span class="transcript-timestamp">58:59</span><span
            class="transcript-text">We don't have to
            deal with these ones.</span></div>
    <div class="transcript-line" data-begin="3540.29"><span class="transcript-timestamp">59:00</span><span
            class="transcript-text">That's where we're
            saving, and that's</span></div>
    <div class="transcript-line" data-begin="3541.831"><span class="transcript-timestamp">59:01</span><span
            class="transcript-text">why this amortization works.</span></div>
    <div class="transcript-line" data-begin="3543.622"><span class="transcript-timestamp">59:03</span><span
            class="transcript-text">Let me give you a potential
            function that makes this work--</span></div>
    <div class="transcript-line" data-begin="3552.95"><span class="transcript-timestamp">59:12</span><span
            class="transcript-text">is minus c times sum of the
            number of empty mod slots.</span></div>
    <div class="transcript-line" data-begin="3563.76"><span class="transcript-timestamp">59:23</span><span
            class="transcript-text">It's kind of the same
            potential but before</span></div>
    <div class="transcript-line" data-begin="3566.37"><span class="transcript-timestamp">59:26</span><span
            class="transcript-text">we had this notion of
            dead and alive nodes.</span></div>
    <div class="transcript-line" data-begin="3568.53"><span class="transcript-timestamp">59:28</span><span
            class="transcript-text">Now everything's alive
            because everything</span></div>
    <div class="transcript-line" data-begin="3570.45"><span class="transcript-timestamp">59:30</span><span
            class="transcript-text">could change at any moment.</span></div>
    <div class="transcript-line" data-begin="3571.98"><span class="transcript-timestamp">59:31</span><span
            class="transcript-text">So instead, I'm going to
            measure how much room I have</span></div>
    <div class="transcript-line" data-begin="3576.03"><span class="transcript-timestamp">59:36</span><span
            class="transcript-text">in each node.</span></div>
    <div class="transcript-line" data-begin="3577.134"><span class="transcript-timestamp">59:37</span><span
            class="transcript-text">Before I had no
            room in this node.</span></div>
    <div class="transcript-line" data-begin="3578.55"><span class="transcript-timestamp">59:38</span><span
            class="transcript-text">Now I have half the
            space in both nodes.</span></div>
    <div class="transcript-line" data-begin="3581.76"><span class="transcript-timestamp">59:41</span><span
            class="transcript-text">So that's good news.</span></div>
    <div class="transcript-line" data-begin="3584.07"><span class="transcript-timestamp">59:44</span><span
            class="transcript-text">Whenever we have
            this recursion, we</span></div>
    <div class="transcript-line" data-begin="3588.3"><span class="transcript-timestamp">59:48</span><span
            class="transcript-text">can charge it to a
            potential decrease.</span></div>
    <div class="transcript-line" data-begin="3596.63"><span class="transcript-timestamp">59:56</span><span
            class="transcript-text">Fee goes down by--</span></div>
    <div class="transcript-line" data-begin="3601.16"><span class="transcript-timestamp">1:00:01</span><span
            class="transcript-text">because I have a
            negative sign here--</span></div>
    <div class="transcript-line" data-begin="3603.72"><span class="transcript-timestamp">1:00:03</span><span
            class="transcript-text">c times, oh man, 2 times
            d plus p plus 1, I think.</span></div>
    <div class="transcript-line" data-begin="3613.74"><span class="transcript-timestamp">1:00:13</span><span
            class="transcript-text">Because there's d plus
            p plus 1 space here,</span></div>
    <div class="transcript-line" data-begin="3615.78"><span class="transcript-timestamp">1:00:15</span><span
            class="transcript-text">d plus p plus 1 space here.</span></div>
    <div class="transcript-line" data-begin="3617.23"><span class="transcript-timestamp">1:00:17</span><span
            class="transcript-text">I mean, we added
            one whole new node.</span></div>
    <div class="transcript-line" data-begin="3618.99"><span class="transcript-timestamp">1:00:18</span><span
            class="transcript-text">And total capacity
            of a node in mods</span></div>
    <div class="transcript-line" data-begin="3620.82"><span class="transcript-timestamp">1:00:20</span><span
            class="transcript-text">is 2 times d plus p plus 1.</span></div>
    <div class="transcript-line" data-begin="3623.61"><span class="transcript-timestamp">1:00:23</span><span
            class="transcript-text">So we get that times c.</span></div>
    <div class="transcript-line" data-begin="3626.01"><span class="transcript-timestamp">1:00:26</span><span
            class="transcript-text">And this is basically
            just enough,</span></div>
    <div class="transcript-line" data-begin="3628.53"><span class="transcript-timestamp">1:00:28</span><span
            class="transcript-text">because this is 2 times
            d plus 2 times p plus 2.</span></div>
    <div class="transcript-line" data-begin="3632.01"><span class="transcript-timestamp">1:00:32</span><span
            class="transcript-text">And here we have a plus 1.</span></div>
    <div class="transcript-line" data-begin="3634.14"><span class="transcript-timestamp">1:00:34</span><span
            class="transcript-text">And so the recursion gets
            annihilated by 2 times d plus</span></div>
    <div class="transcript-line" data-begin="3639.69"><span class="transcript-timestamp">1:00:39</span><span
            class="transcript-text">2 times p plus 1.</span></div>
    <div class="transcript-line" data-begin="3641.28"><span class="transcript-timestamp">1:00:41</span><span
            class="transcript-text">And then there's one
            c left over to absorb</span></div>
    <div class="transcript-line" data-begin="3643.44"><span class="transcript-timestamp">1:00:43</span><span
            class="transcript-text">whatever constant cost there
            was to do all this other work.</span></div>
    <div class="transcript-line" data-begin="3647.241"><span class="transcript-timestamp">1:00:47</span><span
            class="transcript-text">So I got the constants
            just to work,</span></div>
    <div class="transcript-line" data-begin="3651.57"><span class="transcript-timestamp">1:00:51</span><span
            class="transcript-text">except that I cheated and it's
            really a one third, 2/3 split.</span></div>
    <div class="transcript-line" data-begin="3654.34"><span class="transcript-timestamp">1:00:54</span><span
            class="transcript-text">So probably all of these
            constants have to change,</span></div>
    <div class="transcript-line" data-begin="3657.09"><span class="transcript-timestamp">1:00:57</span><span
            class="transcript-text">such is life.</span></div>
    <div class="transcript-line" data-begin="3658.102"><span class="transcript-timestamp">1:00:58</span><span
            class="transcript-text">But I think you get the idea.</span></div>
    <div class="transcript-line" data-begin="3661.49"><span class="transcript-timestamp">1:01:01</span><span
            class="transcript-text">Any questions about
            full persistence?</span></div>
    <div class="transcript-line" data-begin="3667.11"><span class="transcript-timestamp">1:01:07</span><span
            class="transcript-text">This is fun stuff, time travel.</span></div>
    <div class="transcript-line" data-begin="3670.2"><span class="transcript-timestamp">1:01:10</span><span
            class="transcript-text">Yeah?</span></div>
    <div class="transcript-line" data-begin="3671.426"><span class="transcript-timestamp">1:01:11</span><span
            class="transcript-text">AUDIENCE: So in the first
            half of the thing where</span></div>
    <div class="transcript-line" data-begin="3674.63"><span class="transcript-timestamp">1:01:14</span><span
            class="transcript-text">the if, there's room
            you can put it in.</span></div>
    <div class="transcript-line" data-begin="3676.583"><span class="transcript-timestamp">1:01:16</span><span
            class="transcript-text">ERIK DEMAINE: Right.</span></div>
    <div class="transcript-line" data-begin="3677.056"><span class="transcript-timestamp">1:01:17</span><span
            class="transcript-text">AUDIENCE: I have a
            question about how</span></div>
    <div class="transcript-line" data-begin="3677.919"><span class="transcript-timestamp">1:01:17</span><span
            class="transcript-text">we represent the version.</span></div>
    <div class="transcript-line" data-begin="3679.421"><span class="transcript-timestamp">1:01:19</span><span
            class="transcript-text">Because before when we said
            restore now [INAUDIBLE].</span></div>
    <div class="transcript-line" data-begin="3683.016"><span class="transcript-timestamp">1:01:23</span><span
            class="transcript-text">It made more sense if now was
            like a timestamp or something.</span></div>
    <div class="transcript-line" data-begin="3685.92"><span class="transcript-timestamp">1:01:25</span><span
            class="transcript-text">ERIK DEMAINE: OK.</span></div>
    <div class="transcript-line" data-begin="3686.67"><span class="transcript-timestamp">1:01:26</span><span
            class="transcript-text">Right, so how do we represent a
            version even here or anywhere?</span></div>
    <div class="transcript-line" data-begin="3691.47"><span class="transcript-timestamp">1:01:31</span><span
            class="transcript-text">When we do a modification, an
            update, in the data structure,</span></div>
    <div class="transcript-line" data-begin="3694.23"><span class="transcript-timestamp">1:01:34</span><span
            class="transcript-text">we want to return
            the new version.</span></div>
    <div class="transcript-line" data-begin="3696.42"><span class="transcript-timestamp">1:01:36</span><span
            class="transcript-text">Basically, we're going
            to actually store</span></div>
    <div class="transcript-line" data-begin="3699.81"><span class="transcript-timestamp">1:01:39</span><span
            class="transcript-text">the DAG of versions.</span></div>
    <div class="transcript-line" data-begin="3701.042"><span class="transcript-timestamp">1:01:41</span><span
            class="transcript-text">And a version is going to
            be represented by a pointer</span></div>
    <div class="transcript-line" data-begin="3703.25"><span class="transcript-timestamp">1:01:43</span><span
            class="transcript-text">into this DAG.</span></div>
    <div class="transcript-line" data-begin="3704.4"><span class="transcript-timestamp">1:01:44</span><span
            class="transcript-text">One of the nodes in this
            DAG becomes a version.</span></div>
    <div class="transcript-line" data-begin="3707.34"><span class="transcript-timestamp">1:01:47</span><span
            class="transcript-text">Every node in this DAG is
            going to store a pointer</span></div>
    <div class="transcript-line" data-begin="3710.4"><span class="transcript-timestamp">1:01:50</span><span
            class="transcript-text">to the corresponding b character
            and a corresponding e character</span></div>
    <div class="transcript-line" data-begin="3713.64"><span class="transcript-timestamp">1:01:53</span><span
            class="transcript-text">in this data
            structure, which then</span></div>
    <div class="transcript-line" data-begin="3716.46"><span class="transcript-timestamp">1:01:56</span><span
            class="transcript-text">lets you do anything you want.</span></div>
    <div class="transcript-line" data-begin="3717.924"><span class="transcript-timestamp">1:01:57</span><span
            class="transcript-text">Then you can query
            against that version,</span></div>
    <div class="transcript-line" data-begin="3719.59"><span class="transcript-timestamp">1:01:59</span><span
            class="transcript-text">whether it's an ancestor
            of another version.</span></div>
    <div class="transcript-line" data-begin="3721.69"><span class="transcript-timestamp">1:02:01</span><span
            class="transcript-text">So yeah, I didn't mention that.</span></div>
    <div class="transcript-line" data-begin="3722.981"><span class="transcript-timestamp">1:02:02</span><span
            class="transcript-text">Versions are nodes in here.</span></div>
    <div class="transcript-line" data-begin="3724.23"><span class="transcript-timestamp">1:02:04</span><span
            class="transcript-text">Nodes in here have pointers
            to the b's and e's.</span></div>
    <div class="transcript-line" data-begin="3726.647"><span class="transcript-timestamp">1:02:06</span><span
            class="transcript-text">And vice versa, the b's
            and e's have pointers back</span></div>
    <div class="transcript-line" data-begin="3728.73"><span class="transcript-timestamp">1:02:08</span><span
            class="transcript-text">to the corresponding
            version node.</span></div>
    <div class="transcript-line" data-begin="3730.731"><span class="transcript-timestamp">1:02:10</span><span
            class="transcript-text">And then you can keep
            track of everything.</span></div>
    <div class="transcript-line" data-begin="3732.48"><span class="transcript-timestamp">1:02:12</span><span
            class="transcript-text">Good question.</span></div>
    <div class="transcript-line" data-begin="3734.79"><span class="transcript-timestamp">1:02:14</span><span
            class="transcript-text">Yeah?</span></div>
    <div class="transcript-line" data-begin="3735.39"><span class="transcript-timestamp">1:02:15</span><span
            class="transcript-text">AUDIENCE: [INAUDIBLE] question.</span></div>
    <div class="transcript-line" data-begin="3736.27"><span class="transcript-timestamp">1:02:16</span><span
            class="transcript-text">Remind me what d is in this.</span></div>
    <div class="transcript-line" data-begin="3737.15"><span class="transcript-timestamp">1:02:17</span><span
            class="transcript-text">ERIK DEMAINE: Oh, d was
            the maximum out degree.</span></div>
    <div class="transcript-line" data-begin="3739.108"><span class="transcript-timestamp">1:02:19</span><span
            class="transcript-text">It's the number of fields in
            a node, as defined right here.</span></div>
    <div class="transcript-line" data-begin="3746.97"><span class="transcript-timestamp">1:02:26</span><span
            class="transcript-text">Other questions?</span></div>
    <div class="transcript-line" data-begin="3749.701"><span class="transcript-timestamp">1:02:29</span><span
            class="transcript-text">Whew.</span></div>
    <div class="transcript-line" data-begin="3750.2"><span class="transcript-timestamp">1:02:30</span><span
            class="transcript-text">OK, a little breather.</span></div>
    <div class="transcript-line" data-begin="3751.305"><span class="transcript-timestamp">1:02:31</span><span
            class="transcript-text">That was partial persistence,
            full persistence.</span></div>
    <div class="transcript-line" data-begin="3753.45"><span class="transcript-timestamp">1:02:33</span><span
            class="transcript-text">This is, unfortunately, the
            end of the really good results.</span></div>
    <div class="transcript-line" data-begin="3756.73"><span class="transcript-timestamp">1:02:36</span><span
            class="transcript-text">As long as we have
            constant degree nodes,</span></div>
    <div class="transcript-line" data-begin="3758.65"><span class="transcript-timestamp">1:02:38</span><span
            class="transcript-text">in and out degree,
            we can do all.</span></div>
    <div class="transcript-line" data-begin="3761.32"><span class="transcript-timestamp">1:02:41</span><span
            class="transcript-text">We can do for
            persistence for free.</span></div>
    <div class="transcript-line" data-begin="3764.83"><span class="transcript-timestamp">1:02:44</span><span
            class="transcript-text">Obviously there are practical
            constants involved here.</span></div>
    <div class="transcript-line" data-begin="3767.08"><span class="transcript-timestamp">1:02:47</span><span
            class="transcript-text">But in theory, you
            can do this perfectly.</span></div>
    <div class="transcript-line" data-begin="3773.17"><span class="transcript-timestamp">1:02:53</span><span
            class="transcript-text">Before we go on to
            confluence, there</span></div>
    <div class="transcript-line" data-begin="3774.83"><span class="transcript-timestamp">1:02:54</span><span
            class="transcript-text">is one positive result,
            which is what if you</span></div>
    <div class="transcript-line" data-begin="3778.21"><span class="transcript-timestamp">1:02:58</span><span
            class="transcript-text">don't like amortize bounds.</span></div>
    <div class="transcript-line" data-begin="3780.615"><span class="transcript-timestamp">1:03:00</span><span
            class="transcript-text">There are various reasons
            amortize bounds might not</span></div>
    <div class="transcript-line" data-begin="3782.74"><span class="transcript-timestamp">1:03:02</span><span
            class="transcript-text">be good.</span></div>
    <div class="transcript-line" data-begin="3783.07"><span class="transcript-timestamp">1:03:03</span><span
            class="transcript-text">Maybe you really care
            about every operation</span></div>
    <div class="transcript-line" data-begin="3784.861"><span class="transcript-timestamp">1:03:04</span><span
            class="transcript-text">being no slower than it was
            except by a constant factor.</span></div>
    <div class="transcript-line" data-begin="3788.74"><span class="transcript-timestamp">1:03:08</span><span
            class="transcript-text">We're amortizing here, so some
            operations get really slow.</span></div>
    <div class="transcript-line" data-begin="3791.5"><span class="transcript-timestamp">1:03:11</span><span
            class="transcript-text">But the others are all
            fast to compensate.</span></div>
    <div class="transcript-line" data-begin="3794.11"><span class="transcript-timestamp">1:03:14</span><span
            class="transcript-text">You can deamortize, it's called.</span></div>
    <div class="transcript-line" data-begin="3802.6"><span class="transcript-timestamp">1:03:22</span><span
            class="transcript-text">You can get constant
            worst case slowdown</span></div>
    <div class="transcript-line" data-begin="3810.28"><span class="transcript-timestamp">1:03:30</span><span
            class="transcript-text">for partial persistence.</span></div>
    <div class="transcript-line" data-begin="3816.77"><span class="transcript-timestamp">1:03:36</span><span
            class="transcript-text">This is a result of Garret
            Brodle from the late '90s, '97.</span></div>
    <div class="transcript-line" data-begin="3824.26"><span class="transcript-timestamp">1:03:44</span><span
            class="transcript-text">For full persistence--
            so it's an open problem.</span></div>
    <div class="transcript-line" data-begin="3827.149"><span class="transcript-timestamp">1:03:47</span><span
            class="transcript-text">I don't know if people
            have worked on that.</span></div>
    <div class="transcript-line" data-begin="3835.801"><span class="transcript-timestamp">1:03:55</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="3836.3"><span class="transcript-timestamp">1:03:56</span><span
            class="transcript-text">So some, mostly good results.</span></div>
    <div class="transcript-line" data-begin="3839.515"><span class="transcript-timestamp">1:03:59</span><span
            class="transcript-text">Let's move on to confluent
            persistence where things</span></div>
    <div class="transcript-line" data-begin="3841.64"><span class="transcript-timestamp">1:04:01</span><span
            class="transcript-text">get a lot more challenging.</span></div>
    <div class="transcript-line" data-begin="3857.511"><span class="transcript-timestamp">1:04:17</span><span
            class="transcript-text">Lots of things go out the window
            with confluent persistence.</span></div>
    <div class="transcript-line" data-begin="3860.01"><span class="transcript-timestamp">1:04:20</span><span
            class="transcript-text">In particular, your
            versions are now a DAG.</span></div>
    <div class="transcript-line" data-begin="3863.52"><span class="transcript-timestamp">1:04:23</span><span
            class="transcript-text">It's a lot harder
            to linearize a DAG.</span></div>
    <div class="transcript-line" data-begin="3865.65"><span class="transcript-timestamp">1:04:25</span><span
            class="transcript-text">Trees are not that
            far from pads.</span></div>
    <div class="transcript-line" data-begin="3868.98"><span class="transcript-timestamp">1:04:28</span><span
            class="transcript-text">But DAGs are quite far
            from pads, unfortunately.</span></div>
    <div class="transcript-line" data-begin="3873.672"><span class="transcript-timestamp">1:04:33</span><span
            class="transcript-text">But that's not all
            that goes wrong.</span></div>
    <div class="transcript-line" data-begin="3884.66"><span class="transcript-timestamp">1:04:44</span><span
            class="transcript-text">Let me first tell you the
            kind of end effect as a user.</span></div>
    <div class="transcript-line" data-begin="3890.06"><span class="transcript-timestamp">1:04:50</span><span
            class="transcript-text">Imagine you have
            a data structure.</span></div>
    <div class="transcript-line" data-begin="3894.83"><span class="transcript-timestamp">1:04:54</span><span
            class="transcript-text">Think of it as a
            list, I guess, which</span></div>
    <div class="transcript-line" data-begin="3897.5"><span class="transcript-timestamp">1:04:57</span><span
            class="transcript-text">is a list of characters
            in your document.</span></div>
    <div class="transcript-line" data-begin="3899.33"><span class="transcript-timestamp">1:04:59</span><span
            class="transcript-text">You're using vi or Word,
            your favorite, whatever.</span></div>
    <div class="transcript-line" data-begin="3903.41"><span class="transcript-timestamp">1:05:03</span><span
            class="transcript-text">It's a text editor.</span></div>
    <div class="transcript-line" data-begin="3905.06"><span class="transcript-timestamp">1:05:05</span><span
            class="transcript-text">You've got a string of words.</span></div>
    <div class="transcript-line" data-begin="3906.68"><span class="transcript-timestamp">1:05:06</span><span
            class="transcript-text">And now you like to do
            things like copy and paste.</span></div>
    <div class="transcript-line" data-begin="3909.785"><span class="transcript-timestamp">1:05:09</span><span
            class="transcript-text">It's a nice operation.</span></div>
    <div class="transcript-line" data-begin="3911.27"><span class="transcript-timestamp">1:05:11</span><span
            class="transcript-text">So you select an interval of
            the string and you copy it.</span></div>
    <div class="transcript-line" data-begin="3916.34"><span class="transcript-timestamp">1:05:16</span><span
            class="transcript-text">And then you paste
            it somewhere else.</span></div>
    <div class="transcript-line" data-begin="3918.34"><span class="transcript-timestamp">1:05:18</span><span
            class="transcript-text">So now you've got two
            copies of that string.</span></div>
    <div class="transcript-line" data-begin="3921.95"><span class="transcript-timestamp">1:05:21</span><span
            class="transcript-text">This is, in some
            sense, what you might</span></div>
    <div class="transcript-line" data-begin="3924.05"><span class="transcript-timestamp">1:05:24</span><span
            class="transcript-text">call a confluent
            operation, because--</span></div>
    <div class="transcript-line" data-begin="3927.96"><span class="transcript-timestamp">1:05:27</span><span
            class="transcript-text">yeah, maybe a cleaner way to
            think of it is the following.</span></div>
    <div class="transcript-line" data-begin="3930.47"><span class="transcript-timestamp">1:05:30</span><span
            class="transcript-text">You have your string.</span></div>
    <div class="transcript-line" data-begin="3931.91"><span class="transcript-timestamp">1:05:31</span><span
            class="transcript-text">Now I have an operation,
            which is split it.</span></div>
    <div class="transcript-line" data-begin="3933.95"><span class="transcript-timestamp">1:05:33</span><span
            class="transcript-text">So now I have two strings.</span></div>
    <div class="transcript-line" data-begin="3935.84"><span class="transcript-timestamp">1:05:35</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3936.34"><span class="transcript-timestamp">1:05:36</span><span
            class="transcript-text">And now I have an operation,
            which is split it.</span></div>
    <div class="transcript-line" data-begin="3938.298"><span class="transcript-timestamp">1:05:38</span><span
            class="transcript-text">Now I have three strings.</span></div>
    <div class="transcript-line" data-begin="3940.77"><span class="transcript-timestamp">1:05:40</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3941.27"><span class="transcript-timestamp">1:05:41</span><span
            class="transcript-text">Now I have an operation
            which is concatenate.</span></div>
    <div class="transcript-line" data-begin="3944.28"><span class="transcript-timestamp">1:05:44</span><span
            class="transcript-text">So I can, for
            example, reconstruct</span></div>
    <div class="transcript-line" data-begin="3947.33"><span class="transcript-timestamp">1:05:47</span><span
            class="transcript-text">the original string-- actually,
            I have the original string.</span></div>
    <div class="transcript-line" data-begin="3949.85"><span class="transcript-timestamp">1:05:49</span><span
            class="transcript-text">No biggie.</span></div>
    <div class="transcript-line" data-begin="3951.94"><span class="transcript-timestamp">1:05:51</span><span
            class="transcript-text">Let's say-- because
            I have all versions.</span></div>
    <div class="transcript-line" data-begin="3954.47"><span class="transcript-timestamp">1:05:54</span><span
            class="transcript-text">I never lose them.</span></div>
    <div class="transcript-line" data-begin="3955.52"><span class="transcript-timestamp">1:05:55</span><span
            class="transcript-text">So now instead, I'm going to
            cut the string here, let's say.</span></div>
    <div class="transcript-line" data-begin="3959.09"><span class="transcript-timestamp">1:05:59</span><span
            class="transcript-text">So now I have this and this.</span></div>
    <div class="transcript-line" data-begin="3963.71"><span class="transcript-timestamp">1:06:03</span><span
            class="transcript-text">And now I can do
            things like concatenate</span></div>
    <div class="transcript-line" data-begin="3966.62"><span class="transcript-timestamp">1:06:06</span><span
            class="transcript-text">from here to here to here.</span></div>
    <div class="transcript-line" data-begin="3970.01"><span class="transcript-timestamp">1:06:10</span><span
            class="transcript-text">And I will get this
            plus this plus this.</span></div>
    <div class="transcript-line" data-begin="3976.801"><span class="transcript-timestamp">1:06:16</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="3977.3"><span class="transcript-timestamp">1:06:17</span><span
            class="transcript-text">This guy moved here.</span></div>
    <div class="transcript-line" data-begin="3978.579"><span class="transcript-timestamp">1:06:18</span><span
            class="transcript-text">So that's a copy/paste
            operation with a constant number</span></div>
    <div class="transcript-line" data-begin="3980.87"><span class="transcript-timestamp">1:06:20</span><span
            class="transcript-text">of splits and concatenates.</span></div>
    <div class="transcript-line" data-begin="3982.1"><span class="transcript-timestamp">1:06:22</span><span
            class="transcript-text">I could also do cut and paste.</span></div>
    <div class="transcript-line" data-begin="3983.81"><span class="transcript-timestamp">1:06:23</span><span
            class="transcript-text">With confluence, I can
            do crazy cuts and pastes</span></div>
    <div class="transcript-line" data-begin="3986.72"><span class="transcript-timestamp">1:06:26</span><span
            class="transcript-text">in all sorts of ways.</span></div>
    <div class="transcript-line" data-begin="3988.95"><span class="transcript-timestamp">1:06:28</span><span
            class="transcript-text">So what?</span></div>
    <div class="transcript-line" data-begin="3989.91"><span class="transcript-timestamp">1:06:29</span><span
            class="transcript-text">Well, the so what
            is I can actually</span></div>
    <div class="transcript-line" data-begin="3992.12"><span class="transcript-timestamp">1:06:32</span><span
            class="transcript-text">double the size of
            my data structure</span></div>
    <div class="transcript-line" data-begin="3993.99"><span class="transcript-timestamp">1:06:33</span><span
            class="transcript-text">in a constant number
            of operations.</span></div>
    <div class="transcript-line" data-begin="3996.05"><span class="transcript-timestamp">1:06:36</span><span
            class="transcript-text">I can take, for example,
            the entire string</span></div>
    <div class="transcript-line" data-begin="3998.27"><span class="transcript-timestamp">1:06:38</span><span
            class="transcript-text">and concatenate it to itself.</span></div>
    <div class="transcript-line" data-begin="4000.031"><span class="transcript-timestamp">1:06:40</span><span
            class="transcript-text">That will double the
            number of characters,</span></div>
    <div class="transcript-line" data-begin="4001.78"><span class="transcript-timestamp">1:06:41</span><span
            class="transcript-text">number of elements in there.</span></div>
    <div class="transcript-line" data-begin="4003.74"><span class="transcript-timestamp">1:06:43</span><span
            class="transcript-text">I can do that again
            and again and again.</span></div>
    <div class="transcript-line" data-begin="4005.9"><span class="transcript-timestamp">1:06:45</span><span
            class="transcript-text">So in u updates,
            I can potentially</span></div>
    <div class="transcript-line" data-begin="4011.38"><span class="transcript-timestamp">1:06:51</span><span
            class="transcript-text">get a data structure
            size 2 to the u.</span></div>
    <div class="transcript-line" data-begin="4017.77"><span class="transcript-timestamp">1:06:57</span><span
            class="transcript-text">Kind of nifty.</span></div>
    <div class="transcript-line" data-begin="4018.61"><span class="transcript-timestamp">1:06:58</span><span
            class="transcript-text">I think this is why
            confluence is cool.</span></div>
    <div class="transcript-line" data-begin="4020.35"><span class="transcript-timestamp">1:07:00</span><span
            class="transcript-text">It's also why it's hard.</span></div>
    <div class="transcript-line" data-begin="4022.7"><span class="transcript-timestamp">1:07:02</span><span
            class="transcript-text">So not a big surprise.</span></div>
    <div class="transcript-line" data-begin="4023.9"><span class="transcript-timestamp">1:07:03</span><span
            class="transcript-text">But, here we go.</span></div>
    <div class="transcript-line" data-begin="4028.13"><span class="transcript-timestamp">1:07:08</span><span
            class="transcript-text">In that case, the version DAG,
            for reference, looks like this.</span></div>
    <div class="transcript-line" data-begin="4033.49"><span class="transcript-timestamp">1:07:13</span><span
            class="transcript-text">You're taking the same
            version, combining it.</span></div>
    <div class="transcript-line" data-begin="4036.18"><span class="transcript-timestamp">1:07:16</span><span
            class="transcript-text">So here I'm assuming I have
            a concatenate operation.</span></div>
    <div class="transcript-line" data-begin="4040.46"><span class="transcript-timestamp">1:07:20</span><span
            class="transcript-text">And so the effect here,
            every time I do this,</span></div>
    <div class="transcript-line" data-begin="4044.24"><span class="transcript-timestamp">1:07:24</span><span
            class="transcript-text">I double the size.</span></div>
    <div class="transcript-line" data-begin="4064.21"><span class="transcript-timestamp">1:07:44</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="4064.817"><span class="transcript-timestamp">1:07:44</span><span
            class="transcript-text">What do I want to say about
            confluent persistence?</span></div>
    <div class="transcript-line" data-begin="4066.9"><span class="transcript-timestamp">1:07:46</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="4067.399"><span class="transcript-timestamp">1:07:47</span><span
            class="transcript-text">Let me start with the
            most general result, which</span></div>
    <div class="transcript-line" data-begin="4073.2"><span class="transcript-timestamp">1:07:53</span><span
            class="transcript-text">is by Fiat and Kaplan in 2003.</span></div>
    <div class="transcript-line" data-begin="4084.34"><span class="transcript-timestamp">1:08:04</span><span
            class="transcript-text">They define a notion called
            effective depth of a version.</span></div>
    <div class="transcript-line" data-begin="4088.817"><span class="transcript-timestamp">1:08:08</span><span
            class="transcript-text">Let me just write it down.</span></div>
    <div class="transcript-line" data-begin="4101.18"><span class="transcript-timestamp">1:08:21</span><span
            class="transcript-text">It's kind of like
            if you took this DAG</span></div>
    <div class="transcript-line" data-begin="4104.87"><span class="transcript-timestamp">1:08:24</span><span
            class="transcript-text">and expanded it out to be a
            tree of all possible paths.</span></div>
    <div class="transcript-line" data-begin="4110.113"><span class="transcript-timestamp">1:08:30</span><span
            class="transcript-text">Instead of point
            to the same node,</span></div>
    <div class="transcript-line" data-begin="4111.529"><span class="transcript-timestamp">1:08:31</span><span
            class="transcript-text">you could just
            duplicate that node</span></div>
    <div class="transcript-line" data-begin="4113.33"><span class="transcript-timestamp">1:08:33</span><span
            class="transcript-text">and then have pointers
            left and right.</span></div>
    <div class="transcript-line" data-begin="4115.26"><span class="transcript-timestamp">1:08:35</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="4115.76"><span class="transcript-timestamp">1:08:35</span><span
            class="transcript-text">So if I did that, of course,
            this size grows exponentially.</span></div>
    <div class="transcript-line" data-begin="4118.218"><span class="transcript-timestamp">1:08:38</span><span
            class="transcript-text">It explicitly represents the
            size of my data structure.</span></div>
    <div class="transcript-line" data-begin="4121.31"><span class="transcript-timestamp">1:08:41</span><span
            class="transcript-text">At the bottom, if
            I have u things,</span></div>
    <div class="transcript-line" data-begin="4122.81"><span class="transcript-timestamp">1:08:42</span><span
            class="transcript-text">I'm going to have 2 to the
            u leaves at the bottom.</span></div>
    <div class="transcript-line" data-begin="4125.96"><span class="transcript-timestamp">1:08:45</span><span
            class="transcript-text">But then I can easily
            measure the number of paths</span></div>
    <div class="transcript-line" data-begin="4129.08"><span class="transcript-timestamp">1:08:49</span><span
            class="transcript-text">from the root to
            the same version.</span></div>
    <div class="transcript-line" data-begin="4130.5"><span class="transcript-timestamp">1:08:50</span><span
            class="transcript-text">At the bottom, I still
            label it, oh, those</span></div>
    <div class="transcript-line" data-begin="4132.25"><span class="transcript-timestamp">1:08:52</span><span
            class="transcript-text">are all v. They're all the
            same version down there.</span></div>
    <div class="transcript-line" data-begin="4134.63"><span class="transcript-timestamp">1:08:54</span><span
            class="transcript-text">So exponential number
            of paths, if I take log,</span></div>
    <div class="transcript-line" data-begin="4136.664"><span class="transcript-timestamp">1:08:56</span><span
            class="transcript-text">I get what I call
            effective depth.</span></div>
    <div class="transcript-line" data-begin="4138.08"><span class="transcript-timestamp">1:08:58</span><span
            class="transcript-text">It's like if you somehow
            could rebalance that tree,</span></div>
    <div class="transcript-line" data-begin="4142.25"><span class="transcript-timestamp">1:09:02</span><span
            class="transcript-text">this is the best you
            could hope to do.</span></div>
    <div class="transcript-line" data-begin="4145.91"><span class="transcript-timestamp">1:09:05</span><span
            class="transcript-text">It's not really a lower bound.</span></div>
    <div class="transcript-line" data-begin="4147.27"><span class="transcript-timestamp">1:09:07</span><span
            class="transcript-text">But it's a number.</span></div>
    <div class="transcript-line" data-begin="4148.04"><span class="transcript-timestamp">1:09:08</span><span
            class="transcript-text">It's a thing.</span></div>
    <div class="transcript-line" data-begin="4149"><span class="transcript-timestamp">1:09:09</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="4150.47"><span class="transcript-timestamp">1:09:10</span><span
            class="transcript-text">Then the result they achieve
            is that the overhead is</span></div>
    <div class="transcript-line" data-begin="4157.37"><span class="transcript-timestamp">1:09:17</span><span
            class="transcript-text">log the number of
            updates plus-- this</span></div>
    <div class="transcript-line" data-begin="4159.79"><span class="transcript-timestamp">1:09:19</span><span
            class="transcript-text">is a multiplicative overhead,
            so you take your running time.</span></div>
    <div class="transcript-line" data-begin="4162.29"><span class="transcript-timestamp">1:09:22</span><span
            class="transcript-text">You multiply it by this.</span></div>
    <div class="transcript-line" data-begin="4165.979"><span class="transcript-timestamp">1:09:25</span><span
            class="transcript-text">And this is a time
            and a space overhead.</span></div>
    <div class="transcript-line" data-begin="4171.529"><span class="transcript-timestamp">1:09:31</span><span
            class="transcript-text">So maximum effective depth
            of all versions, maybe even</span></div>
    <div class="transcript-line" data-begin="4174.26"><span class="transcript-timestamp">1:09:34</span><span
            class="transcript-text">sum of effective depths, but
            we'll just say max to be safe.</span></div>
    <div class="transcript-line" data-begin="4179.1"><span class="transcript-timestamp">1:09:39</span><span
            class="transcript-text">Sorry-- sum over
            all the operations.</span></div>
    <div class="transcript-line" data-begin="4181.8"><span class="transcript-timestamp">1:09:41</span><span
            class="transcript-text">This is per operation.</span></div>
    <div class="transcript-line" data-begin="4183.129"><span class="transcript-timestamp">1:09:43</span><span
            class="transcript-text">You pay basically
            the effective depth</span></div>
    <div class="transcript-line" data-begin="4184.67"><span class="transcript-timestamp">1:09:44</span><span
            class="transcript-text">of that operation as a factor.</span></div>
    <div class="transcript-line" data-begin="4188.779"><span class="transcript-timestamp">1:09:48</span><span
            class="transcript-text">Now, the annoying thing is if
            you have this kind of set up</span></div>
    <div class="transcript-line" data-begin="4191.33"><span class="transcript-timestamp">1:09:51</span><span
            class="transcript-text">where the size
            grew exponentially,</span></div>
    <div class="transcript-line" data-begin="4194.72"><span class="transcript-timestamp">1:09:54</span><span
            class="transcript-text">then number of paths
            is exponential.</span></div>
    <div class="transcript-line" data-begin="4196.49"><span class="transcript-timestamp">1:09:56</span><span
            class="transcript-text">Log of the number of
            paths is linear in u.</span></div>
    <div class="transcript-line" data-begin="4199.22"><span class="transcript-timestamp">1:09:59</span><span
            class="transcript-text">And so this factor could be
            as much as u, linear slowdown.</span></div>
    <div class="transcript-line" data-begin="4206.42"><span class="transcript-timestamp">1:10:06</span><span
            class="transcript-text">Now, Fiat and Kaplan argue
            linear slowdown is not</span></div>
    <div class="transcript-line" data-begin="4208.82"><span class="transcript-timestamp">1:10:08</span><span
            class="transcript-text">that bad, because if you weren't
            even persistent, if you did</span></div>
    <div class="transcript-line" data-begin="4213.44"><span class="transcript-timestamp">1:10:13</span><span
            class="transcript-text">this in the naive way of
            just recopying the data,</span></div>
    <div class="transcript-line" data-begin="4218.41"><span class="transcript-timestamp">1:10:18</span><span
            class="transcript-text">you were actually spending
            exponential time to build</span></div>
    <div class="transcript-line" data-begin="4221.579"><span class="transcript-timestamp">1:10:21</span><span
            class="transcript-text">the final data structure.</span></div>
    <div class="transcript-line" data-begin="4222.62"><span class="transcript-timestamp">1:10:22</span><span
            class="transcript-text">It has exponential size.</span></div>
    <div class="transcript-line" data-begin="4223.619"><span class="transcript-timestamp">1:10:23</span><span
            class="transcript-text">Just to represent it explicitly
            requires exponential time,</span></div>
    <div class="transcript-line" data-begin="4226.8"><span class="transcript-timestamp">1:10:26</span><span
            class="transcript-text">so losing a linear
            factor to do u operations</span></div>
    <div class="transcript-line" data-begin="4229.82"><span class="transcript-timestamp">1:10:29</span><span
            class="transcript-text">and now u squared time
            instead of 2 to the u.</span></div>
    <div class="transcript-line" data-begin="4231.8"><span class="transcript-timestamp">1:10:31</span><span
            class="transcript-text">So it's a big
            improvement to do this.</span></div>
    <div class="transcript-line" data-begin="4235.19"><span class="transcript-timestamp">1:10:35</span><span
            class="transcript-text">The downside of this approach is
            that even if you have a version</span></div>
    <div class="transcript-line" data-begin="4240.44"><span class="transcript-timestamp">1:10:40</span><span
            class="transcript-text">DAG that looks like this,
            even if the size of the data</span></div>
    <div class="transcript-line" data-begin="4243.41"><span class="transcript-timestamp">1:10:43</span><span
            class="transcript-text">structure is staying
            normal, staying linear, so</span></div>
    <div class="transcript-line" data-begin="4246.402"><span class="transcript-timestamp">1:10:46</span><span
            class="transcript-text">this potential, you could
            be doubling the size.</span></div>
    <div class="transcript-line" data-begin="4248.36"><span class="transcript-timestamp">1:10:48</span><span
            class="transcript-text">But we don't know what
            this merge operation is.</span></div>
    <div class="transcript-line" data-begin="4249.92"><span class="transcript-timestamp">1:10:49</span><span
            class="transcript-text">Maybe it just throws
            away one of the versions</span></div>
    <div class="transcript-line" data-begin="4251.794"><span class="transcript-timestamp">1:10:51</span><span
            class="transcript-text">or does something--</span></div>
    <div class="transcript-line" data-begin="4253.22"><span class="transcript-timestamp">1:10:53</span><span
            class="transcript-text">somehow takes half
            the nodes from one</span></div>
    <div class="transcript-line" data-begin="4255.23"><span class="transcript-timestamp">1:10:55</span><span
            class="transcript-text">side, half the nodes from
            the other side maybe.</span></div>
    <div class="transcript-line" data-begin="4257.188"><span class="transcript-timestamp">1:10:57</span><span
            class="transcript-text">These operations
            do preserve size.</span></div>
    <div class="transcript-line" data-begin="4258.83"><span class="transcript-timestamp">1:10:58</span><span
            class="transcript-text">Then there's no great reason why
            it should be a linear slowdown,</span></div>
    <div class="transcript-line" data-begin="4262.52"><span class="transcript-timestamp">1:11:02</span><span
            class="transcript-text">but it is.</span></div>
    <div class="transcript-line" data-begin="4263.671"><span class="transcript-timestamp">1:11:03</span><span
            class="transcript-text">OK?</span></div>
    <div class="transcript-line" data-begin="4264.17"><span class="transcript-timestamp">1:11:04</span><span
            class="transcript-text">So it's all right but not great.</span></div>
    <div class="transcript-line" data-begin="4270.83"><span class="transcript-timestamp">1:11:10</span><span
            class="transcript-text">And it's the best
            general result we know.</span></div>
    <div class="transcript-line" data-begin="4273.56"><span class="transcript-timestamp">1:11:13</span><span
            class="transcript-text">They also prove a lower bound.</span></div>
    <div class="transcript-line" data-begin="4281.42"><span class="transcript-timestamp">1:11:21</span><span
            class="transcript-text">So lower bound is some effect
            of depth, total bits of space.</span></div>
    <div class="transcript-line" data-begin="4297.23"><span class="transcript-timestamp">1:11:37</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="4297.73"><span class="transcript-timestamp">1:11:37</span><span
            class="transcript-text">What does this mean?</span></div>
    <div class="transcript-line" data-begin="4300.02"><span class="transcript-timestamp">1:11:40</span><span
            class="transcript-text">So even if this
            is not happening,</span></div>
    <div class="transcript-line" data-begin="4302.17"><span class="transcript-timestamp">1:11:42</span><span
            class="transcript-text">the number of bits
            of space you need</span></div>
    <div class="transcript-line" data-begin="4304.15"><span class="transcript-timestamp">1:11:44</span><span
            class="transcript-text">in the worst case--
            this does not</span></div>
    <div class="transcript-line" data-begin="4305.8"><span class="transcript-timestamp">1:11:45</span><span
            class="transcript-text">apply to every data structure.</span></div>
    <div class="transcript-line" data-begin="4307.81"><span class="transcript-timestamp">1:11:47</span><span
            class="transcript-text">That's one catch.</span></div>
    <div class="transcript-line" data-begin="4309.79"><span class="transcript-timestamp">1:11:49</span><span
            class="transcript-text">They give a specific
            data structure</span></div>
    <div class="transcript-line" data-begin="4312.07"><span class="transcript-timestamp">1:11:52</span><span
            class="transcript-text">where you need this much space.</span></div>
    <div class="transcript-line" data-begin="4313.63"><span class="transcript-timestamp">1:11:53</span><span
            class="transcript-text">So it's similar to
            this kind of picture.</span></div>
    <div class="transcript-line" data-begin="4317.05"><span class="transcript-timestamp">1:11:57</span><span
            class="transcript-text">We'll go into the details.</span></div>
    <div class="transcript-line" data-begin="4318.94"><span class="transcript-timestamp">1:11:58</span><span
            class="transcript-text">And you need this much space.</span></div>
    <div class="transcript-line" data-begin="4320.86"><span class="transcript-timestamp">1:12:00</span><span
            class="transcript-text">Now, this is kind of
            bad, because if there's</span></div>
    <div class="transcript-line" data-begin="4322.72"><span class="transcript-timestamp">1:12:02</span><span
            class="transcript-text">u operations, and each of these
            is u, that's u squared space.</span></div>
    <div class="transcript-line" data-begin="4326.44"><span class="transcript-timestamp">1:12:06</span><span
            class="transcript-text">So we actually need a
            factor u blow up in space.</span></div>
    <div class="transcript-line" data-begin="4329.395"><span class="transcript-timestamp">1:12:09</span><span
            class="transcript-text">It looks like.</span></div>
    <div class="transcript-line" data-begin="4331.29"><span class="transcript-timestamp">1:12:11</span><span
            class="transcript-text">But to be more precise,
            what this means is</span></div>
    <div class="transcript-line" data-begin="4334.15"><span class="transcript-timestamp">1:12:14</span><span
            class="transcript-text">that you need omega e of
            v space, and therefore</span></div>
    <div class="transcript-line" data-begin="4337.27"><span class="transcript-timestamp">1:12:17</span><span
            class="transcript-text">time overhead per update, if--</span></div>
    <div class="transcript-line" data-begin="4347.83"><span class="transcript-timestamp">1:12:27</span><span
            class="transcript-text">this is not written
            in the paper--</span></div>
    <div class="transcript-line" data-begin="4349.57"><span class="transcript-timestamp">1:12:29</span><span
            class="transcript-text">queries are free.</span></div>
    <div class="transcript-line" data-begin="4355.3"><span class="transcript-timestamp">1:12:35</span><span
            class="transcript-text">Implicit here, they just want
            to slow down and increase space</span></div>
    <div class="transcript-line" data-begin="4360.4"><span class="transcript-timestamp">1:12:40</span><span
            class="transcript-text">for the updates you do,
            which is pretty natural.</span></div>
    <div class="transcript-line" data-begin="4363.31"><span class="transcript-timestamp">1:12:43</span><span
            class="transcript-text">Normally you think of queries
            as not increasing space.</span></div>
    <div class="transcript-line" data-begin="4366.87"><span class="transcript-timestamp">1:12:46</span><span
            class="transcript-text">But in order to construct
            this lower bound,</span></div>
    <div class="transcript-line" data-begin="4369.6"><span class="transcript-timestamp">1:12:49</span><span
            class="transcript-text">they actually do
            this many queries.</span></div>
    <div class="transcript-line" data-begin="4372.36"><span class="transcript-timestamp">1:12:52</span><span
            class="transcript-text">So they do e of v queries
            and then one update.</span></div>
    <div class="transcript-line" data-begin="4375.9"><span class="transcript-timestamp">1:12:55</span><span
            class="transcript-text">And they say, oh well, space
            had to go up by an extra e of v.</span></div>
    <div class="transcript-line" data-begin="4379.41"><span class="transcript-timestamp">1:12:59</span><span
            class="transcript-text">So if you only charge
            updates for the space,</span></div>
    <div class="transcript-line" data-begin="4382.47"><span class="transcript-timestamp">1:13:02</span><span
            class="transcript-text">then yes, you have
            to lose potentially</span></div>
    <div class="transcript-line" data-begin="4384.12"><span class="transcript-timestamp">1:13:04</span><span
            class="transcript-text">a linear factor, this effect
            of death, potentially u.</span></div>
    <div class="transcript-line" data-begin="4387.78"><span class="transcript-timestamp">1:13:07</span><span
            class="transcript-text">But if you also
            charge the queries,</span></div>
    <div class="transcript-line" data-begin="4389.55"><span class="transcript-timestamp">1:13:09</span><span
            class="transcript-text">it's still constant
            in their example.</span></div>
    <div class="transcript-line" data-begin="4393.27"><span class="transcript-timestamp">1:13:13</span><span
            class="transcript-text">So open question, for
            confluent persistence,</span></div>
    <div class="transcript-line" data-begin="4398.1"><span class="transcript-timestamp">1:13:18</span><span
            class="transcript-text">can you achieve
            constant everything?</span></div>
    <div class="transcript-line" data-begin="4401.13"><span class="transcript-timestamp">1:13:21</span><span
            class="transcript-text">Constant time and
            space overheads,</span></div>
    <div class="transcript-line" data-begin="4407.16"><span class="transcript-timestamp">1:13:27</span><span
            class="transcript-text">multiplicative
            factor per operation,</span></div>
    <div class="transcript-line" data-begin="4413.61"><span class="transcript-timestamp">1:13:33</span><span
            class="transcript-text">both updates and queries.</span></div>
    <div class="transcript-line" data-begin="4415.425"><span class="transcript-timestamp">1:13:35</span><span
            class="transcript-text">So if you charge the
            queries, potentially you</span></div>
    <div class="transcript-line" data-begin="4417.3"><span class="transcript-timestamp">1:13:37</span><span
            class="transcript-text">could get constant everything.</span></div>
    <div class="transcript-line" data-begin="4418.98"><span class="transcript-timestamp">1:13:38</span><span
            class="transcript-text">This is a relatively
            new realization.</span></div>
    <div class="transcript-line" data-begin="4423.89"><span class="transcript-timestamp">1:13:43</span><span
            class="transcript-text">And no one knows
            how to do this yet.</span></div>
    <div class="transcript-line" data-begin="4427.325"><span class="transcript-timestamp">1:13:47</span><span
            class="transcript-text">Nice challenge.</span></div>
    <div class="transcript-line" data-begin="4427.95"><span class="transcript-timestamp">1:13:47</span><span
            class="transcript-text">I think maybe we'll work on that
            in our first problem session.</span></div>
    <div class="transcript-line" data-begin="4430.53"><span class="transcript-timestamp">1:13:50</span><span
            class="transcript-text">I would like to.</span></div>
    <div class="transcript-line" data-begin="4433.6"><span class="transcript-timestamp">1:13:53</span><span
            class="transcript-text">Questions about that result?</span></div>
    <div class="transcript-line" data-begin="4434.77"><span class="transcript-timestamp">1:13:54</span><span
            class="transcript-text">I'm not going to
            prove the result.</span></div>
    <div class="transcript-line" data-begin="4436.45"><span class="transcript-timestamp">1:13:56</span><span
            class="transcript-text">But it is a fancy
            rebalancing of those kinds</span></div>
    <div class="transcript-line" data-begin="4439.54"><span class="transcript-timestamp">1:13:59</span><span
            class="transcript-text">of pictures to get this log.</span></div>
    <div class="transcript-line" data-begin="4450.266"><span class="transcript-timestamp">1:14:10</span><span
            class="transcript-text">There are other results
            I'd like to tell you about.</span></div>
    <div class="transcript-line" data-begin="4472.63"><span class="transcript-timestamp">1:14:32</span><span
            class="transcript-text">So brand new result--</span></div>
    <div class="transcript-line" data-begin="4474.71"><span class="transcript-timestamp">1:14:34</span><span
            class="transcript-text">that was from 2003.</span></div>
    <div class="transcript-line" data-begin="4475.98"><span class="transcript-timestamp">1:14:35</span><span
            class="transcript-text">This is from 2012--</span></div>
    <div class="transcript-line" data-begin="4478.3"><span class="transcript-timestamp">1:14:38</span><span
            class="transcript-text">no, '11, '11, sorry.</span></div>
    <div class="transcript-line" data-begin="4482.59"><span class="transcript-timestamp">1:14:42</span><span
            class="transcript-text">It's SOTO, which is in January,
            so it's a little confusing.</span></div>
    <div class="transcript-line" data-begin="4487.48"><span class="transcript-timestamp">1:14:47</span><span
            class="transcript-text">Is it '11?</span></div>
    <div class="transcript-line" data-begin="4489.25"><span class="transcript-timestamp">1:14:49</span><span
            class="transcript-text">Maybe '12.</span></div>
    <div class="transcript-line" data-begin="4490.267"><span class="transcript-timestamp">1:14:50</span><span
            class="transcript-text">Actually now I'm not sure.</span></div>
    <div class="transcript-line" data-begin="4491.35"><span class="transcript-timestamp">1:14:51</span><span
            class="transcript-text">It's February already, right?</span></div>
    <div class="transcript-line" data-begin="4494.75"><span class="transcript-timestamp">1:14:54</span><span
            class="transcript-text">A January, either this
            year or last year.</span></div>
    <div class="transcript-line" data-begin="4500.31"><span class="transcript-timestamp">1:15:00</span><span
            class="transcript-text">It's not as general
            a transformation.</span></div>
    <div class="transcript-line" data-begin="4502.84"><span class="transcript-timestamp">1:15:02</span><span
            class="transcript-text">It's only going to hold in
            what's called a disjoint case.</span></div>
    <div class="transcript-line" data-begin="4505.33"><span class="transcript-timestamp">1:15:05</span><span
            class="transcript-text">But it gets a very good bound--</span></div>
    <div class="transcript-line" data-begin="4507.82"><span class="transcript-timestamp">1:15:07</span><span
            class="transcript-text">not quite constant,
            but logarithmic.</span></div>
    <div class="transcript-line" data-begin="4509.85"><span class="transcript-timestamp">1:15:09</span><span
            class="transcript-text">OK, logarithmic
            would also be nice.</span></div>
    <div class="transcript-line" data-begin="4512.42"><span class="transcript-timestamp">1:15:12</span><span
            class="transcript-text">Or log, log n, whatever n is.</span></div>
    <div class="transcript-line" data-begin="4517.075"><span class="transcript-timestamp">1:15:17</span><span
            class="transcript-text">Pick your favorite n,
            number of operations, say.</span></div>
    <div class="transcript-line" data-begin="4522.45"><span class="transcript-timestamp">1:15:22</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="4525.7"><span class="transcript-timestamp">1:15:25</span><span
            class="transcript-text">If you assume that confluent
            operations are performed only</span></div>
    <div class="transcript-line" data-begin="4539.83"><span class="transcript-timestamp">1:15:39</span><span
            class="transcript-text">on two versions with
            no shared nodes--</span></div>
    <div class="transcript-line" data-begin="4550.36"><span class="transcript-timestamp">1:15:50</span><span
            class="transcript-text">OK, this would be a way to
            forbid this kind of behavior</span></div>
    <div class="transcript-line" data-begin="4553.87"><span class="transcript-timestamp">1:15:53</span><span
            class="transcript-text">where I concatenate the
            data structure with itself.</span></div>
    <div class="transcript-line" data-begin="4556.66"><span class="transcript-timestamp">1:15:56</span><span
            class="transcript-text">All the nodes are common.</span></div>
    <div class="transcript-line" data-begin="4558.52"><span class="transcript-timestamp">1:15:58</span><span
            class="transcript-text">If I guarantee that maybe I, you
            know, slice this up, slice it,</span></div>
    <div class="transcript-line" data-begin="4561.84"><span class="transcript-timestamp">1:16:01</span><span
            class="transcript-text">dice it, wherever, and
            then re-emerge them</span></div>
    <div class="transcript-line" data-begin="4563.59"><span class="transcript-timestamp">1:16:03</span><span
            class="transcript-text">in some other order, but
            I never use two copies</span></div>
    <div class="transcript-line" data-begin="4566.23"><span class="transcript-timestamp">1:16:06</span><span
            class="transcript-text">of the same piece, that
            would be a valid confluent</span></div>
    <div class="transcript-line" data-begin="4570.13"><span class="transcript-timestamp">1:16:10</span><span
            class="transcript-text">operation over here.</span></div>
    <div class="transcript-line" data-begin="4572.26"><span class="transcript-timestamp">1:16:12</span><span
            class="transcript-text">This is quite a
            strong restriction</span></div>
    <div class="transcript-line" data-begin="4573.88"><span class="transcript-timestamp">1:16:13</span><span
            class="transcript-text">that you're not allowed.</span></div>
    <div class="transcript-line" data-begin="4576.58"><span class="transcript-timestamp">1:16:16</span><span
            class="transcript-text">If you try to, who
            knows what happens.</span></div>
    <div class="transcript-line" data-begin="4579.03"><span class="transcript-timestamp">1:16:19</span><span
            class="transcript-text">Behavior's undefined.</span></div>
    <div class="transcript-line" data-begin="4579.98"><span class="transcript-timestamp">1:16:19</span><span
            class="transcript-text">So won't tell you,
            oh, those two versions</span></div>
    <div class="transcript-line" data-begin="4581.83"><span class="transcript-timestamp">1:16:21</span><span
            class="transcript-text">have this node in common.</span></div>
    <div class="transcript-line" data-begin="4582.871"><span class="transcript-timestamp">1:16:22</span><span
            class="transcript-text">You've got to make
            a second copy of it.</span></div>
    <div class="transcript-line" data-begin="4584.6"><span class="transcript-timestamp">1:16:24</span><span
            class="transcript-text">So somehow you have to guarantee
            that control and operations</span></div>
    <div class="transcript-line" data-begin="4587.099"><span class="transcript-timestamp">1:16:27</span><span
            class="transcript-text">never overlap.</span></div>
    <div class="transcript-line" data-begin="4589.27"><span class="transcript-timestamp">1:16:29</span><span
            class="transcript-text">But they can be reordered.</span></div>
    <div class="transcript-line" data-begin="4593.74"><span class="transcript-timestamp">1:16:33</span><span
            class="transcript-text">Then you can get
            order log n overhead.</span></div>
    <div class="transcript-line" data-begin="4599.5"><span class="transcript-timestamp">1:16:39</span><span
            class="transcript-text">n is the number of operations.</span></div>
    <div class="transcript-line" data-begin="4605.39"><span class="transcript-timestamp">1:16:45</span><span
            class="transcript-text">I have a sketch
            of a proof of this</span></div>
    <div class="transcript-line" data-begin="4606.97"><span class="transcript-timestamp">1:16:46</span><span
            class="transcript-text">but not very much
            time to talk about it.</span></div>
    <div class="transcript-line" data-begin="4608.87"><span class="transcript-timestamp">1:16:48</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="4609.37"><span class="transcript-timestamp">1:16:49</span><span
            class="transcript-text">Let me give you a quick picture.</span></div>
    <div class="transcript-line" data-begin="4611.57"><span class="transcript-timestamp">1:16:51</span><span
            class="transcript-text">In general, the
            versions form a DAG.</span></div>
    <div class="transcript-line" data-begin="4615.79"><span class="transcript-timestamp">1:16:55</span><span
            class="transcript-text">But if you make this assumption,
            and you look at a single node,</span></div>
    <div class="transcript-line" data-begin="4620.95"><span class="transcript-timestamp">1:17:00</span><span
            class="transcript-text">and look at all the versions
            where that node appears,</span></div>
    <div class="transcript-line" data-begin="4623.62"><span class="transcript-timestamp">1:17:03</span><span
            class="transcript-text">that is a tree.</span></div>
    <div class="transcript-line" data-begin="4625.21"><span class="transcript-timestamp">1:17:05</span><span
            class="transcript-text">Because you're not allowed
            to remerge versions</span></div>
    <div class="transcript-line" data-begin="4627.37"><span class="transcript-timestamp">1:17:07</span><span
            class="transcript-text">that have the same node.</span></div>
    <div class="transcript-line" data-begin="4628.72"><span class="transcript-timestamp">1:17:08</span><span
            class="transcript-text">So while the big
            picture is a DAG,</span></div>
    <div class="transcript-line" data-begin="4631.48"><span class="transcript-timestamp">1:17:11</span><span
            class="transcript-text">the small picture of a
            single guy is some tree.</span></div>
    <div class="transcript-line" data-begin="4637.504"><span class="transcript-timestamp">1:17:17</span><span
            class="transcript-text">I'm drawing all
            these wiggly lines</span></div>
    <div class="transcript-line" data-begin="4638.92"><span class="transcript-timestamp">1:17:18</span><span
            class="transcript-text">because there are all
            these versions where</span></div>
    <div class="transcript-line" data-begin="4640"><span class="transcript-timestamp">1:17:20</span><span
            class="transcript-text">the node isn't changing.</span></div>
    <div class="transcript-line" data-begin="4641.56"><span class="transcript-timestamp">1:17:21</span><span
            class="transcript-text">This is the entire version DAG.</span></div>
    <div class="transcript-line" data-begin="4643.3"><span class="transcript-timestamp">1:17:23</span><span
            class="transcript-text">And then some of these nodes--</span></div>
    <div class="transcript-line" data-begin="4646.54"><span class="transcript-timestamp">1:17:26</span><span
            class="transcript-text">some of these versions,
            I should say--</span></div>
    <div class="transcript-line" data-begin="4649"><span class="transcript-timestamp">1:17:29</span><span
            class="transcript-text">that node that we're
            thinking about changes.</span></div>
    <div class="transcript-line" data-begin="4651.925"><span class="transcript-timestamp">1:17:31</span><span
            class="transcript-text">OK, whenever it
            branches, it's probably</span></div>
    <div class="transcript-line" data-begin="4653.86"><span class="transcript-timestamp">1:17:33</span><span
            class="transcript-text">because the actual
            node changed, maybe.</span></div>
    <div class="transcript-line" data-begin="4656.41"><span class="transcript-timestamp">1:17:36</span><span
            class="transcript-text">I don't know.</span></div>
    <div class="transcript-line" data-begin="4657.47"><span class="transcript-timestamp">1:17:37</span><span
            class="transcript-text">Anyway there are some dots
            here where the version changed,</span></div>
    <div class="transcript-line" data-begin="4660.17"><span class="transcript-timestamp">1:17:40</span><span
            class="transcript-text">some of the leaves,
            maybe, that changed.</span></div>
    <div class="transcript-line" data-begin="4661.96"><span class="transcript-timestamp">1:17:41</span><span
            class="transcript-text">Maybe some of them haven't yet.</span></div>
    <div class="transcript-line" data-begin="4664.42"><span class="transcript-timestamp">1:17:44</span><span
            class="transcript-text">In fact, let's see.</span></div>
    <div class="transcript-line" data-begin="4668.35"><span class="transcript-timestamp">1:17:48</span><span
            class="transcript-text">Here where it's change, it could
            be that we destroyed the node.</span></div>
    <div class="transcript-line" data-begin="4671.17"><span class="transcript-timestamp">1:17:51</span><span
            class="transcript-text">Maybe it's gone from the
            actual data structure.</span></div>
    <div class="transcript-line" data-begin="4674.56"><span class="transcript-timestamp">1:17:54</span><span
            class="transcript-text">But there still may
            be versions down here.</span></div>
    <div class="transcript-line" data-begin="4676.542"><span class="transcript-timestamp">1:17:56</span><span
            class="transcript-text">It's not really a tree.</span></div>
    <div class="transcript-line" data-begin="4677.5"><span class="transcript-timestamp">1:17:57</span><span
            class="transcript-text">It's a whole DAG of
            stuff down there.</span></div>
    <div class="transcript-line" data-begin="4679.48"><span class="transcript-timestamp">1:17:59</span><span
            class="transcript-text">So that's kind of ugly.</span></div>
    <div class="transcript-line" data-begin="4681.4"><span class="transcript-timestamp">1:18:01</span><span
            class="transcript-text">Where never the
            node still exists,</span></div>
    <div class="transcript-line" data-begin="4683.08"><span class="transcript-timestamp">1:18:03</span><span
            class="transcript-text">I guess that is an
            actual leaf of the DAG.</span></div>
    <div class="transcript-line" data-begin="4685.3"><span class="transcript-timestamp">1:18:05</span><span
            class="transcript-text">So those are OK.</span></div>
    <div class="transcript-line" data-begin="4686.65"><span class="transcript-timestamp">1:18:06</span><span
            class="transcript-text">But as soon as I maybe
            delete that node,</span></div>
    <div class="transcript-line" data-begin="4688.87"><span class="transcript-timestamp">1:18:08</span><span
            class="transcript-text">then there can be a
            whole subtree down there.</span></div>
    <div class="transcript-line" data-begin="4691.61"><span class="transcript-timestamp">1:18:11</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="4692.11"><span class="transcript-timestamp">1:18:12</span><span
            class="transcript-text">So now if you look at
            an arbitrary version,</span></div>
    <div class="transcript-line" data-begin="4695.12"><span class="transcript-timestamp">1:18:15</span><span
            class="transcript-text">so what we're thinking about
            is how to implement reading,</span></div>
    <div class="transcript-line" data-begin="4697.58"><span class="transcript-timestamp">1:18:17</span><span
            class="transcript-text">let's say.</span></div>
    <div class="transcript-line" data-begin="4698.08"><span class="transcript-timestamp">1:18:18</span><span
            class="transcript-text">Reading and writing are
            more or less the same.</span></div>
    <div class="transcript-line" data-begin="4701.11"><span class="transcript-timestamp">1:18:21</span><span
            class="transcript-text">I give you a version.</span></div>
    <div class="transcript-line" data-begin="4702.28"><span class="transcript-timestamp">1:18:22</span><span
            class="transcript-text">I give you a node, and
            I give you a field.</span></div>
    <div class="transcript-line" data-begin="4703.72"><span class="transcript-timestamp">1:18:23</span><span
            class="transcript-text">I want to know, what is the
            value of that field, that node,</span></div>
    <div class="transcript-line" data-begin="4706.18"><span class="transcript-timestamp">1:18:26</span><span
            class="transcript-text">that version?</span></div>
    <div class="transcript-line" data-begin="4707.81"><span class="transcript-timestamp">1:18:27</span><span
            class="transcript-text">So now where could
            a version fall?</span></div>
    <div class="transcript-line" data-begin="4710.014"><span class="transcript-timestamp">1:18:30</span><span
            class="transcript-text">Well it has to be
            in this subtree.</span></div>
    <div class="transcript-line" data-begin="4711.43"><span class="transcript-timestamp">1:18:31</span><span
            class="transcript-text">Because the node has to exist.</span></div>
    <div class="transcript-line" data-begin="4716.95"><span class="transcript-timestamp">1:18:36</span><span
            class="transcript-text">And then it's maybe a pointer.</span></div>
    <div class="transcript-line" data-begin="4718.39"><span class="transcript-timestamp">1:18:38</span><span
            class="transcript-text">A pointer could be to
            another node, which</span></div>
    <div class="transcript-line" data-begin="4722.83"><span class="transcript-timestamp">1:18:42</span><span
            class="transcript-text">also has this kind of picture.</span></div>
    <div class="transcript-line" data-begin="4724.54"><span class="transcript-timestamp">1:18:44</span><span
            class="transcript-text">They could be overlapping trees.</span></div>
    <div class="transcript-line" data-begin="4726.46"><span class="transcript-timestamp">1:18:46</span><span
            class="transcript-text">In general, there
            are three cases.</span></div>
    <div class="transcript-line" data-begin="4728.14"><span class="transcript-timestamp">1:18:48</span><span
            class="transcript-text">Either you're lucky, and the
            version you're talking about</span></div>
    <div class="transcript-line" data-begin="4731.11"><span class="transcript-timestamp">1:18:51</span><span
            class="transcript-text">is a version where
            the node was changed.</span></div>
    <div class="transcript-line" data-begin="4733.96"><span class="transcript-timestamp">1:18:53</span><span
            class="transcript-text">In that case, the data is
            just stored right there.</span></div>
    <div class="transcript-line" data-begin="4738.47"><span class="transcript-timestamp">1:18:58</span><span
            class="transcript-text">That's easy.</span></div>
    <div class="transcript-line" data-begin="4739.125"><span class="transcript-timestamp">1:18:59</span><span
            class="transcript-text">So you could just say, oh,
            how did the node change?</span></div>
    <div class="transcript-line" data-begin="4741.25"><span class="transcript-timestamp">1:19:01</span><span
            class="transcript-text">Oh, that's what the field is.</span></div>
    <div class="transcript-line" data-begin="4742.63"><span class="transcript-timestamp">1:19:02</span><span
            class="transcript-text">OK, follow the pointer.</span></div>
    <div class="transcript-line" data-begin="4745.19"><span class="transcript-timestamp">1:19:05</span><span
            class="transcript-text">A slightly harder
            case it's a version</span></div>
    <div class="transcript-line" data-begin="4748.21"><span class="transcript-timestamp">1:19:08</span><span
            class="transcript-text">in between two such changes.</span></div>
    <div class="transcript-line" data-begin="4749.59"><span class="transcript-timestamp">1:19:09</span><span
            class="transcript-text">And maybe these are not updates.</span></div>
    <div class="transcript-line" data-begin="4751.66"><span class="transcript-timestamp">1:19:11</span><span
            class="transcript-text">So I sort of want to know, what
            was the previous version where</span></div>
    <div class="transcript-line" data-begin="4757.33"><span class="transcript-timestamp">1:19:17</span><span
            class="transcript-text">this node changed
            in constant time?</span></div>
    <div class="transcript-line" data-begin="4761.65"><span class="transcript-timestamp">1:19:21</span><span
            class="transcript-text">It can be done.</span></div>
    <div class="transcript-line" data-begin="4762.62"><span class="transcript-timestamp">1:19:22</span><span
            class="transcript-text">Not constant time,
            actually, logarithmic time,</span></div>
    <div class="transcript-line" data-begin="4765.16"><span class="transcript-timestamp">1:19:25</span><span
            class="transcript-text">using a data structure
            called link-cut trees,</span></div>
    <div class="transcript-line" data-begin="4768.12"><span class="transcript-timestamp">1:19:28</span><span
            class="transcript-text">another fun black
            box for now, which</span></div>
    <div class="transcript-line" data-begin="4771.01"><span class="transcript-timestamp">1:19:31</span><span
            class="transcript-text">we will cover in lecture
            19, far in the future.</span></div>
    <div class="transcript-line" data-begin="4776.171"><span class="transcript-timestamp">1:19:36</span><span
            class="transcript-text">OK.</span></div>
    <div class="transcript-line" data-begin="4779.884"><span class="transcript-timestamp">1:19:39</span><span
            class="transcript-text">Well, that's one case.</span></div>
    <div class="transcript-line" data-begin="4780.8"><span class="transcript-timestamp">1:19:40</span><span
            class="transcript-text">There's also the version
            where maybe a version</span></div>
    <div class="transcript-line" data-begin="4783.19"><span class="transcript-timestamp">1:19:43</span><span
            class="transcript-text">is down here in a subtree.</span></div>
    <div class="transcript-line" data-begin="4785.11"><span class="transcript-timestamp">1:19:45</span><span
            class="transcript-text">I guess then the
            node didn't exist.</span></div>
    <div class="transcript-line" data-begin="4788.34"><span class="transcript-timestamp">1:19:48</span><span
            class="transcript-text">Well, all these
            things can happen.</span></div>
    <div class="transcript-line" data-begin="4790.49"><span class="transcript-timestamp">1:19:50</span><span
            class="transcript-text">And that's even harder.</span></div>
    <div class="transcript-line" data-begin="4791.8"><span class="transcript-timestamp">1:19:51</span><span
            class="transcript-text">It's messy.</span></div>
    <div class="transcript-line" data-begin="4793.36"><span class="transcript-timestamp">1:19:53</span><span
            class="transcript-text">They use another trick, which
            is called fractional cascading,</span></div>
    <div class="transcript-line" data-begin="4799.72"><span class="transcript-timestamp">1:19:59</span><span
            class="transcript-text">which I'm not even going to
            try to describe what it means.</span></div>
    <div class="transcript-line" data-begin="4802.24"><span class="transcript-timestamp">1:20:02</span><span
            class="transcript-text">But it's got a very cool name.</span></div>
    <div class="transcript-line" data-begin="4804.19"><span class="transcript-timestamp">1:20:04</span><span
            class="transcript-text">Because we'll be
            covering it in lecture 3.</span></div>
    <div class="transcript-line" data-begin="4806.08"><span class="transcript-timestamp">1:20:06</span><span
            class="transcript-text">So stay tuned for that.</span></div>
    <div class="transcript-line" data-begin="4807.284"><span class="transcript-timestamp">1:20:07</span><span
            class="transcript-text">I'm not going to say how
            it applies to this setting,</span></div>
    <div class="transcript-line" data-begin="4809.45"><span class="transcript-timestamp">1:20:09</span><span
            class="transcript-text">but it's a necessary
            step in here.</span></div>
    <div class="transcript-line" data-begin="4813.33"><span class="transcript-timestamp">1:20:13</span><span
            class="transcript-text">In the remaining
            zero minutes, let</span></div>
    <div class="transcript-line" data-begin="4815.364"><span class="transcript-timestamp">1:20:15</span><span
            class="transcript-text">me tell you a little bit about
            functional data structures.</span></div>
    <div class="transcript-line" data-begin="4817.78"><span class="transcript-timestamp">1:20:17</span><span
            class="transcript-text">[LAUGHTER]</span></div>
    <div class="transcript-line" data-begin="4820.9"><span class="transcript-timestamp">1:20:20</span><span
            class="transcript-text">Beauty of time travel.</span></div>
    <div class="transcript-line" data-begin="4824.83"><span class="transcript-timestamp">1:20:24</span><span
            class="transcript-text">Functional-- I just
            want to give you</span></div>
    <div class="transcript-line" data-begin="4831.13"><span class="transcript-timestamp">1:20:31</span><span
            class="transcript-text">some examples of things that
            can be done functionally.</span></div>
    <div class="transcript-line" data-begin="4833.59"><span class="transcript-timestamp">1:20:33</span><span
            class="transcript-text">There's a whole book about
            functional data structures</span></div>
    <div class="transcript-line" data-begin="4835.798"><span class="transcript-timestamp">1:20:35</span><span
            class="transcript-text">by Okasaki.</span></div>
    <div class="transcript-line" data-begin="4836.7"><span class="transcript-timestamp">1:20:36</span><span
            class="transcript-text">It's pretty cool.</span></div>
    <div class="transcript-line" data-begin="4838.18"><span class="transcript-timestamp">1:20:38</span><span
            class="transcript-text">A simple example
            is balanced BSTs.</span></div>
    <div class="transcript-line" data-begin="4842.32"><span class="transcript-timestamp">1:20:42</span><span
            class="transcript-text">So if you just want to get
            log n time for everything,</span></div>
    <div class="transcript-line" data-begin="4844.6"><span class="transcript-timestamp">1:20:44</span><span
            class="transcript-text">you can do that functionally.</span></div>
    <div class="transcript-line" data-begin="4845.89"><span class="transcript-timestamp">1:20:45</span><span
            class="transcript-text">It's actually really easy.</span></div>
    <div class="transcript-line" data-begin="4846.89"><span class="transcript-timestamp">1:20:46</span><span
            class="transcript-text">You pick your favorite balance
            BST, like red black trees.</span></div>
    <div class="transcript-line" data-begin="4848.92"><span class="transcript-timestamp">1:20:48</span><span
            class="transcript-text">You implement it top down so you
            never follow parent pointers.</span></div>
    <div class="transcript-line" data-begin="4851.26"><span class="transcript-timestamp">1:20:51</span><span
            class="transcript-text">So you don't need
            parent pointers.</span></div>
    <div class="transcript-line" data-begin="4852.71"><span class="transcript-timestamp">1:20:52</span><span
            class="transcript-text">So then as you make changes
            down the tree, you just copy.</span></div>
    <div class="transcript-line" data-begin="4857.71"><span class="transcript-timestamp">1:20:57</span><span
            class="transcript-text">It's called path copying.</span></div>
    <div class="transcript-line" data-begin="4858.995"><span class="transcript-timestamp">1:20:58</span><span
            class="transcript-text">Whenever you're about
            to make a change,</span></div>
    <div class="transcript-line" data-begin="4860.62"><span class="transcript-timestamp">1:21:00</span><span
            class="transcript-text">make a copy of that node.</span></div>
    <div class="transcript-line" data-begin="4862.07"><span class="transcript-timestamp">1:21:02</span><span
            class="transcript-text">So you end up copying all
            the change nodes and all</span></div>
    <div class="transcript-line" data-begin="4865.45"><span class="transcript-timestamp">1:21:05</span><span
            class="transcript-text">their ancestors.</span></div>
    <div class="transcript-line" data-begin="4866.2"><span class="transcript-timestamp">1:21:06</span><span
            class="transcript-text">There's only log n of them,
            so it takes log n time.</span></div>
    <div class="transcript-line" data-begin="4869.65"><span class="transcript-timestamp">1:21:09</span><span
            class="transcript-text">Clear?</span></div>
    <div class="transcript-line" data-begin="4870.5"><span class="transcript-timestamp">1:21:10</span><span
            class="transcript-text">Easy.</span></div>
    <div class="transcript-line" data-begin="4871.5"><span class="transcript-timestamp">1:21:11</span><span
            class="transcript-text">It's a nice technique.</span></div>
    <div class="transcript-line" data-begin="4872.62"><span class="transcript-timestamp">1:21:12</span><span
            class="transcript-text">Sometimes path copying
            is very useful.</span></div>
    <div class="transcript-line" data-begin="4874.6"><span class="transcript-timestamp">1:21:14</span><span
            class="transcript-text">Like link-cut
            trees, for example,</span></div>
    <div class="transcript-line" data-begin="4876.17"><span class="transcript-timestamp">1:21:16</span><span
            class="transcript-text">can be made functional.</span></div>
    <div class="transcript-line" data-begin="4877.45"><span class="transcript-timestamp">1:21:17</span><span
            class="transcript-text">We don't know what they are,
            but they're basically a BST.</span></div>
    <div class="transcript-line" data-begin="4879.905"><span class="transcript-timestamp">1:21:19</span><span
            class="transcript-text">And you can make
            them functional.</span></div>
    <div class="transcript-line" data-begin="4881.28"><span class="transcript-timestamp">1:21:21</span><span
            class="transcript-text">We use that in a paper.</span></div>
    <div class="transcript-line" data-begin="4883.291"><span class="transcript-timestamp">1:21:23</span><span
            class="transcript-text">All right.</span></div>
    <div class="transcript-line" data-begin="4883.79"><span class="transcript-timestamp">1:21:23</span><span
            class="transcript-text">Deques.</span></div>
    <div class="transcript-line" data-begin="4885.97"><span class="transcript-timestamp">1:21:25</span><span
            class="transcript-text">These are doubly ended queues.</span></div>
    <div class="transcript-line" data-begin="4887.8"><span class="transcript-timestamp">1:21:27</span><span
            class="transcript-text">So it's like a stack and
            a queue and everything.</span></div>
    <div class="transcript-line" data-begin="4889.99"><span class="transcript-timestamp">1:21:29</span><span
            class="transcript-text">You can insert and delete from
            the beginning and the end.</span></div>
    <div class="transcript-line" data-begin="4892.9"><span class="transcript-timestamp">1:21:32</span><span
            class="transcript-text">People start to know
            what these are now,</span></div>
    <div class="transcript-line" data-begin="4894.73"><span class="transcript-timestamp">1:21:34</span><span
            class="transcript-text">because Python calls him that.</span></div>
    <div class="transcript-line" data-begin="4895.98"><span class="transcript-timestamp">1:21:35</span><span
            class="transcript-text">But you can also
            do concatenation</span></div>
    <div class="transcript-line" data-begin="4901.09"><span class="transcript-timestamp">1:21:41</span><span
            class="transcript-text">with deques in constant
            time per operation.</span></div>
    <div class="transcript-line" data-begin="4903.31"><span class="transcript-timestamp">1:21:43</span><span
            class="transcript-text">This is cool.</span></div>
    <div class="transcript-line" data-begin="4904.15"><span class="transcript-timestamp">1:21:44</span><span
            class="transcript-text">Deques are not very
            hard to make functional.</span></div>
    <div class="transcript-line" data-begin="4906.22"><span class="transcript-timestamp">1:21:46</span><span
            class="transcript-text">But you can do deques and
            you can concatenate them</span></div>
    <div class="transcript-line" data-begin="4908.5"><span class="transcript-timestamp">1:21:48</span><span
            class="transcript-text">like we were doing in the figure
            that's right behind this board.</span></div>
    <div class="transcript-line" data-begin="4911.98"><span class="transcript-timestamp">1:21:51</span><span
            class="transcript-text">Constant time split
            is a little harder.</span></div>
    <div class="transcript-line" data-begin="4913.69"><span class="transcript-timestamp">1:21:53</span><span
            class="transcript-text">That's actually one
            of my open problems.</span></div>
    <div class="transcript-line" data-begin="4916.87"><span class="transcript-timestamp">1:21:56</span><span
            class="transcript-text">Can you do lists with split and
            concatenate in constant time--</span></div>
    <div class="transcript-line" data-begin="4921.58"><span class="transcript-timestamp">1:22:01</span><span
            class="transcript-text">functionally or confluently,
            persistently, or whatever?</span></div>
    <div class="transcript-line" data-begin="4925.84"><span class="transcript-timestamp">1:22:05</span><span
            class="transcript-text">Another example-- oh, you
            can do a mix of the two.</span></div>
    <div class="transcript-line" data-begin="4928.58"><span class="transcript-timestamp">1:22:08</span><span
            class="transcript-text">You can get log n search in
            constant time deque operations,</span></div>
    <div class="transcript-line" data-begin="4932.39"><span class="transcript-timestamp">1:22:12</span><span
            class="transcript-text">is you can do tries.</span></div>
    <div class="transcript-line" data-begin="4934.87"><span class="transcript-timestamp">1:22:14</span><span
            class="transcript-text">So a try is a tree
            with a fixed topology.</span></div>
    <div class="transcript-line" data-begin="4937.9"><span class="transcript-timestamp">1:22:17</span><span
            class="transcript-text">Think of it as a directory tree.</span></div>
    <div class="transcript-line" data-begin="4940.01"><span class="transcript-timestamp">1:22:20</span><span
            class="transcript-text">So maybe you're
            using Subversion.</span></div>
    <div class="transcript-line" data-begin="4941.53"><span class="transcript-timestamp">1:22:21</span><span
            class="transcript-text">Subversion has time
            travel operations.</span></div>
    <div class="transcript-line" data-begin="4943.12"><span class="transcript-timestamp">1:22:23</span><span
            class="transcript-text">You can copy an entire
            subtree from one version</span></div>
    <div class="transcript-line" data-begin="4946.24"><span class="transcript-timestamp">1:22:26</span><span
            class="transcript-text">and stick it into a new
            version, another version.</span></div>
    <div class="transcript-line" data-begin="4950.62"><span class="transcript-timestamp">1:22:30</span><span
            class="transcript-text">So you get a version DAG.</span></div>
    <div class="transcript-line" data-begin="4952.685"><span class="transcript-timestamp">1:22:32</span><span
            class="transcript-text">It's a confluently
            persistent data structure--</span></div>
    <div class="transcript-line" data-begin="4954.85"><span class="transcript-timestamp">1:22:34</span><span
            class="transcript-text">not implemented optimally,
            because we don't necessarily</span></div>
    <div class="transcript-line" data-begin="4957.61"><span class="transcript-timestamp">1:22:37</span><span
            class="transcript-text">know how.</span></div>
    <div class="transcript-line" data-begin="4958.24"><span class="transcript-timestamp">1:22:38</span><span
            class="transcript-text">But there is one paper.</span></div>
    <div class="transcript-line" data-begin="4960.2"><span class="transcript-timestamp">1:22:40</span><span
            class="transcript-text">This actually came from the open
            problem section of this class</span></div>
    <div class="transcript-line" data-begin="4963.91"><span class="transcript-timestamp">1:22:43</span><span
            class="transcript-text">four years ago, I think.</span></div>
    <div class="transcript-line" data-begin="4965.59"><span class="transcript-timestamp">1:22:45</span><span
            class="transcript-text">It's with Eric Price
            and Stefan Langerman.</span></div>
    <div class="transcript-line" data-begin="4969.52"><span class="transcript-timestamp">1:22:49</span><span
            class="transcript-text">You can get very good results.</span></div>
    <div class="transcript-line" data-begin="4970.929"><span class="transcript-timestamp">1:22:50</span><span
            class="transcript-text">I won't write them down
            because it takes a while.</span></div>
    <div class="transcript-line" data-begin="4972.97"><span class="transcript-timestamp">1:22:52</span><span
            class="transcript-text">Basically log the degree
            of the nodes factor</span></div>
    <div class="transcript-line" data-begin="4976.45"><span class="transcript-timestamp">1:22:56</span><span
            class="transcript-text">and get functional, and
            you can be even fancier</span></div>
    <div class="transcript-line" data-begin="4979.69"><span class="transcript-timestamp">1:22:59</span><span
            class="transcript-text">and get slightly better
            bounds like log log the degree</span></div>
    <div class="transcript-line" data-begin="4982.48"><span class="transcript-timestamp">1:23:02</span><span
            class="transcript-text">and get confluently persistent
            with various tricks,</span></div>
    <div class="transcript-line" data-begin="4985.37"><span class="transcript-timestamp">1:23:05</span><span
            class="transcript-text">including using all of
            these data structures.</span></div>
    <div class="transcript-line" data-begin="4987.53"><span class="transcript-timestamp">1:23:07</span><span
            class="transcript-text">So if you want to implement
            subversion optimally,</span></div>
    <div class="transcript-line" data-begin="4989.8"><span class="transcript-timestamp">1:23:09</span><span
            class="transcript-text">that is known how to be done but
            hasn't actually been done yet.</span></div>
    <div class="transcript-line" data-begin="4994.39"><span class="transcript-timestamp">1:23:14</span><span
            class="transcript-text">Because there are those
            pesky constant factors.</span></div>
    <div class="transcript-line" data-begin="4998.11"><span class="transcript-timestamp">1:23:18</span><span
            class="transcript-text">I think that's all.</span></div>
    <div class="transcript-line" data-begin="4999.67"><span class="transcript-timestamp">1:23:19</span><span
            class="transcript-text">What is known about functional
            is there's a log n separation.</span></div>
    <div class="transcript-line" data-begin="5003.03"><span class="transcript-timestamp">1:23:23</span><span
            class="transcript-text">You can be log n
            away from the best.</span></div>
    <div class="transcript-line" data-begin="5006.89"><span class="transcript-timestamp">1:23:26</span><span
            class="transcript-text">That's the worst
            separation known,</span></div>
    <div class="transcript-line" data-begin="5010.23"><span class="transcript-timestamp">1:23:30</span><span
            class="transcript-text">between functional and just
            a regular old data structure.</span></div>
    <div class="transcript-line" data-begin="5013.012"><span class="transcript-timestamp">1:23:33</span><span
            class="transcript-text">It'd be nice to improve that.</span></div>
    <div class="transcript-line" data-begin="5014.22"><span class="transcript-timestamp">1:23:34</span><span
            class="transcript-text">Lots of open problems here.</span></div>
    <div class="transcript-line" data-begin="5015.345"><span class="transcript-timestamp">1:23:35</span><span
            class="transcript-text">Maybe we'll work
            on them next time.</span></div>
</div>