Now, we're going to take a look at the next level up of structuring data where we have two-dimensional arrays, or arrays of arrays. Two-dimensional array is a doubly indexed sequence of values of the same type. These are familiar. If you've done math calculations with matrices or if we have a table, say we have students in grades, then we have a two-dimensional array, two indices to access an element which would be great. Scientific experiments, there might be an index by time and an index by an experiment. Transactions for bank customers, there's the customer and then which transaction it is. We'll look at this one later on. Pixels in a digital image. This image has got an x-coordinate and a y-coordinate which are just indices and then each value of the coordinates specifies the pixel and the thing there is a color. Our geographic data has many, many applications. Again, just as with one-dimensional arrays, we want to facilitate storage and manipulation of this data. With two indices, we have more flexibility for data that calls for it. So, Java also has language support for two-dimensional arrays. Again, basic support that extends the one-dimensional arrays support in a natural way. So, to declare a two-dimensional array, we put a sequence of two open close braces. That's says a is going to be a two-dimensional array of values of type double. To create one of a given size, we put numbers in there and we use the new construct. So, if a has been declared, this says create a new two-dimensional array, a thousand-by-thousand array. Then to refer to the entry by index after the name of the two-dimensional array, we put a row name inside brackets and a column name inside brackets. Refer to the number of rows, that's a.length and the number of columns is i.length. That can be different for each row. That's a little more advanced. So, we need to get right now, but we put it here for completeness. To refer to a row i, that's a of i. There's no good way to refer to column j and that's just the way that the arrays are implemented. In Java, there are arrays of arrays and once you understand that, then you can see these. So, this is a three by 10 array with three rows and 10 columns. We think of it as laid out in this row major order where we put all the elements in each row one after the other and the columns are vertical. Maybe we think of the first thing as being the name a. Again, the real world. It's slightly more complicated than that. What about initializing? Again, if we write code like a equals new double, [1000]e[1000], that's a million different elements and they're all initialized to 0.0. If they're initialized to zero of the booleans, they're initialized to false and we can declare create initialize in a single statement in a similar way and we can also do literal values. So, it's an array of arrays, so we put curly brackets and then we just put the rows within curly brackets separated by colon. Again, to initialize to zero, you don't have to have nested loops like you might expect in which do need in many other languages, but you have to really be sure you take into account that the cost of creating an array is proportional to its size. So, one application is vector and matrix calculations. These are very familiar to most of you and we won't dwell on it for now, but it's certainly a natural application of arrays. So, if we have two arrays a and b that are both of length n, then we can create a new array of C of that same length, and then add those two vectors a and b to get the result for C. So, it's just term by term add. Or if you have a matrix, then you use a two-dimensional array, then you have to follow every i for every j, do the term by term add. So, each entry gets added to create the corresponding entry on the right. So, that's just a very simple vector and matrix calculations. With vectors and matrices we have more complicated computation. Like for vectors, the dot product product, you have one-dimensional array, you multiply the corresponding entries and add them all up. So, this is just a little trace for these two vectors, one-dimensional vectors. First entry zero. Both of them is x[i] is 0.3 is y[i] is 0.5. You multiply them together, you get 0.15. Then do that for one, you get zero 0.06, then you add it to the sum. And then the third one, you add it inside the dot product of those two vectors is 0.25. When you get that for vectors with a single for-loop with matrices that correspond to things maybe matrix multiplication. If you're familiar with matrix multiplication, you immediately see how this code works, and if you're not, you can look in the book for more details, i and j is the dot product of row i and column j in the result. So, those two give us same result from over there, and that fills in one entry of the matrix. In this case, it's a triple for-loop. For every entry in the output, you have to do a dot product of two vectors in the row and the column in the input matrices. So, that's an example of two-dimensional arrays used to implement a familiar matrix computation. Just a quick question, how many multiplies modifications do you need to multiply two and by n matrices? If you look at this code just for a second, you see, well, it's a triple loop, each one executed n times. So, the answer is n times n times n. That's n cubed two multiply two and by n matrices. So, let's look at another simulation example. So, here we imagine a dog that's wandering and it's lost and wander around in a city that's all square city blocks. Being a dog you knows is to waste time to revisit any intersection and it can't know when it's beginning when end going to a place that it's been before and won't go there. So, the question is, does the dog ever get out of the city or not? So, what we're going to do is have a random process and n by n lattice. We're going to start in the middle, and we're going to move to a random neighboring intersection, but never revisiting anywhere. The two possible things that can happen is, one, you get out of the city, but the other is you get stuck in a dead end. Let's look at an example. So, we start in the middle, and in this case move west, move west again, and then north, and then east, then north, and so forth. Randomly choosing a direction. Now at that point, you couldn't go back that way because it's already, it couldn't go back west because it's already been there. Now it goes south, and then it goes east, and in this case, looks good, but now it's not going to go west again because it's already been there. So, there's only two possible things that it could do. It goes up, north, so that means it escapes. On the other hand with this one, after going for awhile, the dog has the chance to escape if it goes out. But in this case, it chooses to go nowhere, and that means a dead end. That dog's stuck. All the neighboring intersections, he's already been through. So the question is, what are the chances of hitting a dead end? Again, with arrays, we can address this question with simulation. We're going to use Monte Carlo simulation. Now, in the q conflict, we had a one-dimensional array. In this, we're going to have a two-dimensional array of the places that we've been. With all the code that we've seen in this setup, this code almost writes itself. You can quickly see what we're going to want to do. This is a bunch of random walks, and you can see in this case, there's eight by 48 of them, and one, two, three, four, five, six, seven, eight of them are deadEnds, and the rest of them, the dog escapes. So, we want to do a lot of random walks and we want to calculate the proportion for which the dog gets stuck. Again, this is the same setup. This is the third third now that we've used this setup. We're going to take our problem size from the command line. We're going to take the number of trials that we want to do from the command line. We're going to initiate a count of the variable that we care about, which is the number of times it reaches deadEnds, and then we're going to go into a for loop to do our experiment trials times and just use the variable t to just keep count of the number of trials that we've done. What do we do for our experiment? We create a Boolean array, an N by N Boolean array, and again, Java automatically initializes that to false, every entry to false. Then we'll keep our coordinates X and Y for our starting point, and that's going to be in the middle at N over 2, N over 2, and then this while loop, the condition on the while loop is that X can't be 0 and X can't be N minus 1, and Y 0 and Y can't be N minus 1, because any one of those conditions means that the dog escaped. Then, what's the condition that the dog is stuck? The condition is that, every neighboring place has been visited. So if I'm at X, Y, X minus 1Y, X plus 1Y are the ones to the east and west, and XY minus 1, XY plus 1 are the ones to the north and south. So, if I've been to all those places before, I know I'm in the dead end and I just increment that and break. Otherwise, I set this position to be true say, "Okay, I'm here. I've been here," I generate a random number, and then I just take four cases of whether that number is less than a quarter, between a quarter and a half, between half and three quarters, between three quarters and one, all of those equally likely. If the neighbor in that direction, if I haven't been there before, then I go there either by incrementing or decrementing X, or by incrementing or decrementing Y. That's my experiment. I either get out of that by incrementing deadEnds or not incrementing deadEnds. Then when I'm done after doing all the trials, I just print out the percentage of deadEnds, which is the number of deadEnds divided by the number of trials. A pretty short program, but for a big value of N and trials, it's a huge amount of computation, and it can help us address this question of, what's the chance that I reach a dead end? If I do it again, this time I'm doing 100,000 trials, if I do a 10 by 10 grid, then I have a five percent chance of reaching deadEnds, good chance of getting out. As the grid gets bigger, I get a much bigger chance of getting stuck in a dead end. It gets to be 30, it gets to be 58 percent, 40, it gets to be 77 percent. After a while, when the grid is really huge, I've really not much chance of getting out. The size of 100, it's more than 99 percent dead ends, and I can go ahead and plot that and you get an idea for what the chances are for various grid sizes. This seems a little bit like a whimsical problem, but this is actually very like many such problems. There's very important applications in science. So, that's our problem. It's been used to model the behavior of polymers and solvents, and actually, a Nobel Prize was won for study of associated phenomenon, and physics of magnetic materials and many other physical phenomena. It's an important problem that scientists want to understand. What's the probability of reaching a dead end? You might be surprised to know that nobody knows. People had been studying this for a long time, and we don't have a mathematical model for telling us the shape of that curve that we just plotted in one of your early programming lectures. We know from our simulations pretty clearly that it's going to be 99 percent plus for big values of N. The point that I want to make is that, not only can computer simulation be pretty easy, you as a beginning programmer can learn to do it, but it's actually often the only effective way to study a scientific phenomenon. That's why we have this heavy emphasis on simulation at the beginning of this course. It's a very well motivated application of simple programming techniques, and it's important because it's often the only way to make an effective study of a scientific phenomena. Let's summarize briefly. Arrays are a very basic building block in programming. They let us store large amounts of data values of all the same type. We can instantly access a given piece of data with index or indices in two-dimensional arrays, and we'll see later how this efficiency derives from the way that a computer hardware is organized. We're going to see several more applications later in this course, from a shift register for cryptography, to digital audio, to processing digital images, to simulating in bodies in physics. All of those things with this one data structure, and we're going to study other data structures as well.
