0:01

Okay. Those are some basic data structures and implementations and it seem quite

elementary and simple but actually right away we can get to some very sophisticated

applications of these basic concepts and that's what we're going to consider next.

Now, first thing to mention is that often the kinds of data types and data

structures that we implement or found in a Java library. So, that's true in many

programming environments. So, for example stacks and queues you can find those words

mentioned in the Java library so there's a Java collection library and the so-called

List interface which is displayed here. So Java has general API for sequences of

items and its got things like a, append at the end, remove from the beginning, and

so forth. Any uses of the resizing array, so many of the principles that we consider

does also a, a link list interface. So, why not just use those? Why use our own

implementations? Well, the problem is often in such library code is kind of

designed by committee phenomenon that more and more operations get added and the API

becomes too broad or bloated. It's not a good idea to have lots and lots of, you

know, operations in the same API. And we'll see example in a second. The

problem, the real problem is that when you do that you can't know much about the

performance or you can't assume much about the performance. And so you can kind of

immediately arrive at that performance even for simple clients. So our best

practice that we recommend is so few that these basic data structures that we use

and there's so simple is to go ahead and use the implementations that we've just

discussed for these fundamental data structures. Maybe later, later on, after

2:24

an experienced programmer who knows what he or she is doing could use some of these

library collections effectively. But inexperienced programmers often have

trouble with it. Here's a war story from students Programming assignments not that

long ago. So, we have an assignment where you need to generate a random open sites

in a percolation system. We have one student who was paying attention to what

we're saying and uses an array and can pick the indices into that array at random

check whether they're open and, and repeat. And so the array is N by N, it's

N^2 things and it takes about N^2 time, which is actually a linear time for this

application. But then we have another student who had some Java before coming to

us and considered himself an expert and said, well, I'm going to use linked list

because I could use Java's library and I don't have to worry about downloading your

stupid code. And so, I'll just use that one and pick an index at random and delete

and that program took quadratic time and poor Kenny, when trying to run his program

for the huge instance that we asked found out that it wasn't finishing. And the

reason is that the Java linked list implementation takes a linear time to find

an item with a given index. Not constant time like an array. And that's difficult

for Kenny to think about and difficult to drive that information from the

implementation so program is just too slow. And with the Swiss knife

implementation with so many operations it's hard to know whether or not the

particular set of operations that your client needs is efficiently implemented. So

our insistence in this course is that students should not use the library until

we've implemented it in class. At least that some indication that you understand

the performance characteristics. So now, let's look at some applications then of,

of stacks. There's the stacks are really actually fundamental underlying

computation because they implement , recursion and so, you use stacks often

everyday when you wrote, use the Back button in the Web browser, the places that

you've been are saved on a stack. Right now we will look at two examples. One,

having to deal with compiling from a programming language or interpreting into

an actual computation and then the other one is the PostScript language which is

widely used for, for printing and publishing. So, so the way the compilers

implement functions is using stacks. When there's a function call the whole local

environment is pushed and then along with the return address and then the function

returned is pop the return address in the local environment. So there is the stack

there that contains all that information and whether the function calls itself or

not is not relevant. The stack contains the recursion. In fact, you can always use

an explicit stack to make a recursive program non-recursive. So, this is so when

we have the GCD function, computing the greatest common denominator, greatest

common denominator p and q is greatest common denominator of q and p mod q and it

just calls itself until q gets to be zero. And as this graphic integrates, it just

does it by saving the information on a stack. Now a specific example that really

shows this off and also will illustrate the utility of being able to process

multiple types of data with the same code is this example is Dijkstra's two-stack

algorithm for arithmetic expression evaluation. So the goal is, you got an

arithmetic expression this is just actually like a simple stand in for a

program and we'll talk about that in a second but let's say, arithmetic

expressions. We have operands and operators and you want to evaluate it. And

Dijkstra's algorithm is very simple to express. You processes through the

expression from left to right. If you see a value, you put it, you maintain two

stacks and if you see a value, you put it on the value stack and if you see an

operator, you put on the operator stack. Left parenthesis you ignore. Right

parenthesis, you pop the operator and two values and push the result. Now that's a

lot of words let's look at a demo. So we start out with the empty value stack and

operator stack and we're going to move from left to right. So, and those are the

a top is summarize the four type of things that we could wind up with and what to do

so the left parenthesis we've ignored, a value we put on to the value stack. So,

that one goes right in to the value stack. Operator, we put on to the operator stack.

And plus it goes on the operator stack. Left parenthesis you ignore. It seems strange

to be ignoring parenthesis and we'll get back to that in a second. Value, put in

the value stack. Operator, put on the operating stack. Doesn't seem like we're

doing much except putting stuff on stacks and now, when we come to our right

parenthesis and that's when it gets interesting. What it says is to you have

the top operator and the top two values and that's what you want to do. Supply

that operator to those values and put the resulting value that you get back on to the

operation stack. So, we take off the top two things, we do the operation and then we

put the thing that we get onto the value stack. And that's right parenthesis. So

now continuing along we put a star on. Left parenthesis, we ignore. Four on, star.

The right goes to the value stack and now we got a lot of stuff on the stacks and we

got through right parenthesis and that's going to finish up the computation, take

the top two items off the stack and the top operator off the operator stack,

perform the operation, put the result back on the value stack. Another right

parenthesis, take the top two values off. Perform the operation. Put the value on to

the value stack and finally, the last right parenthesis, take the two operators

of the value stack, operators of the value stack, and operator of the operator stack,

perform the operation, put the result back on the value stack. And we're at the end

of the computation and that's the result. The value that arithmetic expression is

101. Okay? Yup. Here's the code that implements Dijkstra's two-stack algorithm.

We have two different stacks. The operand stack the operator stack is string, it

could be characters which is just our operator. Then our value stack is doubled

so that's the same stack code but with generics, we're using, using two different

types of data. And then simply perform Dijkstra's algorithm. If we have a left

parenthesis... Read a new string. If we have a left parenthesis, do nothing. If we have

plus or times, push it. If we have a right parenthesis, then go ahead and pop the

operator. And if it's plus, add the result of the two values at the top of the value

stack and if it's a star, multiply the two values on the top of the stack and, and

then push the result. So and then when you're done then simply print out the

value on the stack and that's a fine and elegant implementation using stacks for

any arithmetic expression. And it's easy to extend that to handle other types of

things and so, why does this work? Well, when the algorithm encounters an operator,

say, in the inside, we got the parenthesis, operand, operator, operand, parenthesis

its easy to see that what its going to do inside there is put the at the top of the

stack whatever it is, is to put the two and three on the top of the value stack

and plus on the top of the operating stack and when it hits that right parenthesis,

it's going to perform the operation and it's going to proceed then exactly as if

the original input where that, where the value replaced. So, just go in from the

inside out for every operation enclosed within parenthesis like that it's just

repeat the argument that's exactly as if the original expression were (one + five)

twenty and then again, replacing that one, one + 100, 101. That's, that's why

Dijkstra's algorithm works. Actually fairly easy to understand why it works.

And you can go ahead and extend this algorithm to add functions like logs and

sines or other operators and have precedence among operators, have them

associate and multiple operations, and so forth. And actually that's on the road to

developing a compiler or a way to translate a, a program from a programming

language to a computation, so Dijkstra's algorithm that uses stack is

one way for entering and understanding of the basis of computation.