cs046 ยป

Contents

## Discovering Algorithms

Here's half of my array. I'll just pick up parts for the second half so I can tell them apart. Here's the other half of my array. Now what could I do? It looks like it would be helpful if I could swap these two elements, cause that way I would get this element in place, and also this one. Let's do it again, that's good. Now these two elements are in place. And so are these. Another swap, and another, and another, and presto! I'm done. I have what used to be the second half now in the first half, what used to be in the first half now in the second half, in exactly the right order. Well that's great, now I can start writing pseudocode. So which elements did I swap? The one in positions zero and five. 1 and 6, 2 and 7, 3 and 8, 4 and 9. So each time I swapped position i with position i plus 5. What's five? That's the length of each sub-array, or one half the length of the original array. So i started at zero. We'll figure out in a minute how far it went, and then I'll swap the element at position i with, well I can't say i plus 5 in the pseudo-code, because the pseudo-code needs to explain the general situation. So, it was length over 2, now, how far does i go? In this case, it went from zero to four. So in general, it'll go to length over 2 minus 1. Now that was the hard part, the easy part is to program that in Java, and I'll leave that to you.

## Swapping Halves

This is how the problem was set up for you. We have an array of elements, and your job was to swap the first and the second half. I then move the j'th position to the i'th position and then take the saved value in here. If [UNKNOWN] has reminded you how to swap two elements in an array, we've actually seen the same thing with array lists before. Let's go through this really quickly so that you understand this. So we want to swap these two positions. And in the second line, it moves the j element into the i element thereby overwriting what was in here. But fortunately in the first line we had moved that into the variable saved. And then in the third line, we move it into j. Now we're ready to apply the pseudo code that you've seen at the end of the previous unit.

## Swapping Halves

That pseudo code asked us to let i go from zero to the length over 2 minus 1. That minus one is always a little inelegant, I prefer to use the less than sign here. Inside the loop, we were supposed to swap the position i and i plus length over 2. Let's copy and paste the swap code. Here it is, but now j, of course, is supposed to be this. Now I fixed up the code. And I'm ready to run. Here you see the result, the array before and after swapping. And you can see these numbers are now where they're supposed to be, as well as for the other half. I want to briefly talk about the code that produced this printout here. When you look over here, we call system.out.println and we can't directly print elements. As I said, arrays are more primitive then array lists, and an array will not print out its value. This method here takes an array and turns it into a string that lists all of the values inside. Though when you want to print out an array list, you can directly pass it out to System.out.printIn. When you have an array, you have to use this helper method. Of course you could also use a direct loop, but the helper method is more convenient. Now remember what the point of all of this was, the point was not how to implement the swapping algorithm in Javam the exciting thing was how we discovered it in the first place, we discovered it by playing around with stuff and not by worrying about exactly how the index values were or whether we needed a For loop or a While loop and I hope that's the lesson that stays with you, if you need to do something that's off the beaten track, that's different from what you've seen before. Get out some Lego bricks, some coins, some candies, whatever, and figure out what the operation would be with those. And that'll give you the intuition that you need in order to be a successful programmer. Programming is all about having the right ideas and the right intuition, not about pushing the symbols of the programming language around.

## 2-D Arrays Part 1

You've seen how arrays can store a sequence of values such as this one. Here we have three prices for three different kinds of gasoline. Well, what if we have two gas stations in this case you'll want to store a two dimensional arrangement with rows and columns, two dimensional arrays can do that. In this example we would have three rows and two columns. In Java we get such a arrangement by saying, give me a new array of doubles, of floating point numbers and I want three rows, two columns. In general, the first number is the number of rows, the second one the number of columns. Note the type, it's a double brackets brackets meaning, it's a two dimensional array, of numbers. If you already know which numbers should go into the two dimensional array, then you can supply them like this. Again, here I have a two dimensional array, of prices. And now, you put a, pair of braces, for the entire array, and then for each row you put another pair of braces with the values. So here we have three rows, each of which is enclosed in a pair of braces. Now you know how to declare a two-dimensional array. Next let's have a look at how we can access its elements.

## 2-D Arrays Part 2

You've just learned how to set up a two-dimensional array, and now let's say we want to know the price of regular gasoline of the second gas station. We supply two index values; the first one is the row, the second one the column. So in this case we're in row zero and in column one. Now you know how to access a particular element. You simply look up the row and the column number and plug them in here. What if you want to look at all elements? For example, to make a print out of every price in the 2D array. Let's look at that next.

## 2-D Arrays Part 3

To visit all elements in a Two-D array, you want to loop over the rows and columns. Let's first loop over the rows. So we have a row index i that assumes to values zero, one, and two in this example. Similarly, we'll have a column index j, then in this example, we'll go from zero to one. If we had more columns, of course it would go further. When you have a row of column index, then we can access the element at the i-th row, and the j-th column. So what you see over here. As the general expression for an element at an arbitrary row and arbitrary column. In this case, we just print it and we use printf. So that the print out lines up nicely. So we would now print this element and print that element, that would finish the innerloop. Then the outer loop would pick the next row, we print these two, and then the outer loop picks the last row. And we print those two. Now, of course, we want the numbers to line up nicely, so after printing each row, we want to print a new line. Notice that this statement is contained in the outer loop, because it happens once per row. But its not in the inner loop because we don't want a new line after every of the element. Now, lets look at the missing balance here. Of course, in this simple example I could just say I should be less than three, J should be less than two, but in general, someone might just hand you a two-dimensional array and you should ask it how big it is. Just like with a one-dimensional array, you just use the length field to find out how big an array is. You can get the number of rows from a two-dimensional array by asking it arrayname.length. And the reason for this is that a two-dimensional array is actually an array of one-dimensional arrays. So prices, which looks like this nice tabular arrangement, really is an array of three arrays, one for each row. And so the number of rows is given by that length. Now, we need to look at how many columns we have. Here you have a row. And the length of that row is the number of columns. So in general, you should remember that, for any two-dimensional array, you get the number of rows with this expression, the number of columns with that expression. Now, let's move on to doing something more interesting with two-dimensional arrays and gas prices.

## Neighbors

When you have a picture, you can think of it as a giant two-dimensional array of colors. It's a little tedious to work with the colors because they have red, blue, and green components. Here, we'll just use grayscale. Each element in the two-dimensional array will represent a gray level. As an integer between zero and 255. Now, here's the problem that we want to solve, we have a photo, which is represented as a two-dimensional array, of lots of grey level. And now we want to make it a little blockier. When I have groups of four neighbors like this, I want to compute the average color or rather the average gray level of these four pixels and color them all in that color. And this is, I'm making every pixel a bit fatter. Let me blow this up a little. So here are the pixel, and I want to know, what are it's three neighbors to the right, to the bottom, and diagonally. So let's assume the one that I'm starting with is pixels ij, that means my row is i, and my column is j. Let's look at the one to the right. The row number is the same, and the column number has increased by one. So here it is in Java. Same row, column increased by one. What about the one to the south? In this case, the column index j is the same. And the row index has increased by one. So here's the java code for that. Finally, the diagonal one has both the row and column index increase by one. And I'll leave it to you in the next lab exercise to figure that out. So go ahead and. Program this exercise. You need to traverse the first pixel here then you jump by two each time and also the columns you go down by two columns each time. In each step you average these four pixels, compute the average value and stick it back into all four pixels. Don't worry the friendly [INAUDIBLE] have given you some code to start with.

## Neighbors

Let me show you how I did this. We have the loop for the rows, and the loop for the columns. Notice that the rows jump in steps of two. We'll do the same thing for the columns. Now I need to compute the average of these four pixels. Let me draw my little picture again. So here's position I J. And I want to compute the average of this one. This one. This one, and this one. I already have the one in I J. This one here has row I, column J plus 1. The one over here has row I plus 1 and column J. And finally the one over here has row I plus 1, column J plus 1. I add those four, divide by 4, and that's my average. And I need to stick it back into. Each of those four pixels. I already have the coordinates, so I can just copy them. I'm almost done, but I still have to put in the bounds here. When we talked about the gas prices, we were told, what the general rule is, so let's just do that. The length of a two dimensional array, is the number of rows, and the length of a row is the number of columns. Let's see what it looks like when we run it. Here was the original picture. Here are the process gray levels. Now, you won't be able to see this on the video, but if you run this at home, if you carefully look at this arc for example, you will see that it is more pixelated. Now, the point of all this was, to work with neighbors. To figure out if you have a pixel position, what other neighboring positions. That many, many image manipulation algorithms where you have to do just that. For example, to blur a photo, to sharpen it or to process it in other ways. Now you will work with Sarah with an entirely different problem. She will show you how to use two dimensional arrays for a grade book with a kind instructor who wants to know which students are doing very well and also which exams are too hard.

## Two Dimensional Arrays

The homework scores class may be useful for storing a single student's grades. And you can get useful information out of a single student's scores. But when my friend Sarel was teaching math, that wasn't enough information for her. She wanted information about her teaching skills, as well as detailed summaries for the students. She wanted to know how well she had taught fractions. And how well she taught equivalent fractions. And for that, she would need to compare the data for all of the students for one topic. This is starting to look like a a student. And also to calculate the total for a topic, which would allow her to compute sums for each topic. And then compare them, to see which topics she needed to spend more time on. Once that was done, she could write very detailed, customized teacher comments for each student, by looking at what they got in each topic, and choosing different sentences based on that grade. We're going to implement this together. I'm going to make a class. The GradeBook class, which will contain a 2-D array, of all of the scores. It'll also contain, the names of the students, and the names of the topics. Since you probably don't want to enter these scores over and over again, I wrote a method that will read the GradeBook scores, from the files, and put them into the array for you.

## Total Score for One Student

Let's code this in Java. I can see that I have the number of students and the number of topics. And the two dimensional array of grades. I can ignore the student names and the topics for now. What I'm really interested in, is implementing the total for student method. To do this, the important thing to recognize is that I want to access all of the grades in one row. The grades in one row all share their first index but their second index varies because that tells which column. So I'll loop over all of the columns, starting at the first one. And since there's a column for each topic, I'll keep going as long as my column is less than the number of topics. I'll need a variable to hold the sum, and for each item I'll add the grade in the studentIndex row, in the column column. And when I'm done, I'll return the sum. Just to be safe, is somebody gives me a bad studentIndex, I want to return minus 1. So if studentIndex is less than 0 or more than the number of students, or greater than or equal to the number of students, I return minus 1. This is always a good idea when somebody else is calling your method. You want to think about the things that they could do wrong, and agree on a good way to handle those cases.

## total score for all students

Returning the total score for one student wasn't too bad. I bet we could return an array with the totals for all of the students. So going back to this example, here we would want to return an array with three elements, one for each student. The first one would be five plus six plus seven. The second would be six plus eight plus seven, and the third would be four plus six plus five. In BlueJ, implement the method totalsForAllStudents.

## total score for all students

I am going to show you two ways to do this, we know that for each student we want to write that student's total into an array and return it, I know exactly how big I want the array to be because I want one total for each student, so I want numStudents items in my array, now for each student I want to increment my new double array by the total for that student. I already have a method that calculates this, so I can just use it again. And when I've done that for all of the students, I can return totals. We could also do this using nested for loops. To do that, I would first think about, solving the problem for one student. Now, for the one student that I'm thinking about, for now let say that's student one, I want to add that student's grade. For that topic. To the student total. And then, in my larger array of all all of the totals, I can fill in the space for that student with the student total. And now for each student, I'll do all of these steps. I don't need to define this one anymore. Now the inner loop is calculating totals, and the outer loop is storing the calculated totals into the array of totals. So now that I've fixed my syntax errors, this way will work just as well as the last one. Just to make sure, I'll test it. I won't make you read through all of this, but they look good. Hopefully the number of values here makes you see why it would be nice as a teacher to have a computer to do this for you.

## how well did i teach

We talked about calculating totals for a student, but there was another important use for this 2D array. We wanted to be able to tell if there was a particular topic that my friend needed to spend more time on. Let's write a method that calculates the sum for each column. So it would return an array whose size matches the number of topics. And those values should be the some of all of the students scores for that topic. So in this case, the array would look like this. If you're ready to go this method, skip ahead. If not, I'll do a short example first. Let's say I want to calculate the total for multiplying fractions. I would want to add this this spot, and this spot, and this spot. This one is the zeroth student, and the second topic. This one is the first student, and the second topic. This one, is the second student, and the second topic.

## how well did i teach

To code this in BlueJ, I'll first imagine just calculating a total for one topic. Let's say it's topic two. Now for each student, I want to look at the grade for that student for the current topic. And add it onto the sum so far. This'll be the sum for this one topic. I'll initialize sum for topic with zero and then once I've calculated it I want to store it in the correct spot for it's topic. I'll need to make this array for all of the totals, it contains doubles. And it should have one for each topic, and then at the end, I'll return all of the totals. But now I need to do this part for all of the topics. So, starting from initializing the sum, to saving it, I want to indent everything, and then add a for loop that goes through all of the topics so now that I am controlling the topic that I am looking at with a for loop we can get rid of that and now I am ready to try it, since there are less topics than students it's easier to tell this time that it is right, but there are a lot of other ways that we could do this, for example I could create my array with one spot for each topic and I then I could go through each student one student at a time, and add their total. And add their grade to the correct total for the correct topics. And then, for the last line, plus 4 plus 6 plus 5. That might work, too. I think that's a little more confusing to read. But there could be advantages to that way as well. I think the way that I showed was the simplest. But trying a few different ways is good practice. You could find the one that you like best. What do you like about it?