In a previous lesson, we looked at I/O-efficient priority queue, which is based on buffer trees. In this lesson and actually the next lessons, we're going to use this I/O-efficient priority queue to look at time forward processing, which is a very important technique. Here, we're going to illustrate it for the problem of computing, what is called a local function on a DAG. So, let's first see what is a local function on a DAG. Well, a DAG or Directed Acyclic Graph, is a directed graph as you see here. So, it's a graph where, the arcs, the edges are directed, and it should be acyclic. We're not allowed to have a directed cycle. So, for instance, this edge would not be allowed because then, together with these two edges, there will be a directed cycle. So, we have a DAG. What is nice about a DAG is that you can sort the nodes, or let's say number the nodes in what is called a topological ordering. So, what's the topological ordering? Well, that's an ordering, let's say V0, V1, V2, and so on, of all the vertices such that every edge is directed from a node with a smaller index to a node with a higher index. So, if I have an edge ViVj then i must be smaller than j. There are no edges allowed in the other direction. So, for instance, if you look at this number in here, then this would be a possible topological ordering. Because, well, for instance, if you look at this edge, you will see that it goes from a vertex with a lower number to a vertex with a higher number. You can check that this is the case for all the edges. So, this is a valid topological ordering. Okay. So, this is a DAG. What we want to compute on a DAG was what I call these local functions. So, what is the local function? It's a function that assigns something to each node in the graph. Actually, it works on a labeled graph. So, what's a labeled graph? That's a graph where every internal node has a specific label, which I denote by Lambda V. We'll see an example in a moment. So, a local function on such labeled graph is a function f, where the value that you assigned to a node vi. So, f of vi, that should only depend on two things. One, it can depend on the label of the node itself. Two, it can depend on the f-values of the in-neighbors. So, it's not allowed to depend on f-values of other nodes. So, for instance, if you look at this node here, well the f-value of this node can depend on its own Lambda value, its own label, plus it can depend on the f-values of these in-neighbors. What is also important is that, if you have a node that has no in-neighbors, so there's no incoming edges, then you can easily compute this f-value just by looking at the label of the node. So, let's look at an example of how we can use this, and what we want to do always, is we want to compute this f-value for all the nodes in the tree. Or in some problems maybe, just the f-value of one certain node is the end result that we want. So, for instance, if you look at evaluating expression trees, then the latter is the case. So, here, you see an expression tree for the expression two plus two times four plus five minus three. Often, if I want to put this into the framework that we saw before, then the labels of the nodes are going to be, well, the leaves in this expression tree are going to get as a label, the number in the expression. The internal nodes are going to have a label that corresponds to the arithmetic operation. Now, what's the local function, well that's obvious. So, for a leaf, the value of a leaf is simply the value of the label. So, here, for instance, this node whose label is five gets value five, this node whose label is three gets value three, and so on. So, this you can do for all the leaves. For an internal node, well, what you simply do is you take the values of its two children, its two in-neighbors. While you take those and apply the arithmetic operation, which is specified by the label of the node itself. So, for instance, for this node, you would get five minus three. So, that's pretty simple. Now, the final value of this whole expression is of course, the f value of the root. So, this is just one example of how evaluating a local function on a DAG can be used to model certain problems. Now, let's have a look at an algorithm for evaluating a local function. So, here, you see, the algorithm, and the assumption that we will be making is that the vertices are numbered according to this topological ordering. So, here you see the algorithm, It's actually pretty obvious, we simply go over all the vertices in this topological order. Then, when it gets to a vertex V vi, I simply compute f, the value for vi, based on the Lambda value, the label of vi and the f-values of the in-neighbors. The nice thing is that because we handle the vertices in topological order that, when I get to vi, it can only have incoming edges in-neighbors from vertices vj with j smaller than i. So, vertices that I already handled. So, when I get to vi, I have all the f-values that I need. So, I have the f-values, I know the label of the node itself. So, I can compute my new f-value. So, what we saw in this lesson was, what our local functions on a labeled DAG, and we saw a very simple algorithm for evaluating such functions, based on a topological ordering. In the next lesson, we're going to analyze the I/O-efficiency of this algorithm. What we're going to see is that it's actually not that good, and that we need to be a little bit more clever in how exactly we implement this algorithm.