Programming Methodology-Lecture28

Instructor (Mehran Sahami): All righty. So welcome back to our last fun-filled, exciting class of CS106A. Itís always a little sad at the end of the quarter, at least for me. For you, it might be a lot more exciting that youíre done with this class. But so we have a bunch of announcements. There are some things to get through today, namely some things also related to your final exam, as well as some unfinished business with the graphics contest.

So thereís two handouts today, the last two handouts except for the final exam which are a practice final and the solutions for the practice final. The problems that are on that are actually taken from Ė most of them. Some of them were written just for that, but most of them were taken from actual final exams in the past. So just like the midterm, it should give you a chance to get a notion of what kind of questions we would ask, what sort of topical coverage there would be, the level of difficulty, and Iíve left the blank pages out of the exam just to save trees, but we would have space in the exam for you to actually take in.

And we give you the solutions so you can check your exams as well. And again, I would strongly encourage you to do this as a way of studying for the final exam, just to get a sense for how comfortable you feel with the material because there is kind of a range of stuff. As I mentioned today, today is the last class lecture. There is no Ė to sort of pay homage to whatís supposed to be dead week, although most classes donít really have a dead week, our attempt at dead week is a dead day, so there is no lecture on Friday, although sections are still happening this week, so go to your section this week. There are section problems, and there is a bit of a review happening as well, so sections are still very useful to go to this week. Assignment No. 7 you know is due next time. You only need electronic submission for that because weíre not gonna do interactive grading, so thereís no interactive grading for Assignment 7, but it is due at what would be class time on Friday. You just need to submit electronically. Donít worry about paper version. Just wondering. Anyone Ė how many more people Ė or I should say how many people are done with Assignment No. 7 already? Just wondering. Wow. A fair number of folks, so hopefully it wasnít too excruciatingly painful.

Course evaluations, thereís actually two sets of evaluations, and I would ask you to please do them. Theyíre actually really important. The two course evaluations there are is one is a university-wide course evaluation. And actually, if you do your course evals for the class that youíre in, you get access to your grades earlier in Axess, so sort of provides a strong incentive to actually do the course evaluations. But I would encourage you to do them, and be honest in the course evaluation for whatever you think because thatís information that we can also use to try to improve the class in the future, so itís useful for us in the long term, and the university actually uses it for a bunch of stuff for it, so itís very important for them. The university, since they have their own eval Ė we have a specialized eval that we also do. Sort of like you took the mid-quarter eval that was online, we have an end of quarter evaluation for 106A that also gives us some very specific feedback about this class: how much time you spent on assignments, what assignments you liked, what assignments you didnít like, stuff like that Ė that we actually Ė Itís totally anonymous, but we use it for some data analysis to kinda figure out how are we pacing the class, is the class actually achieving the objectives that weíre trying to get to, and youíll find out about that second evaluation in your sections this week. And that oneís also very important, so I would encourage you to go to section, find out about that evaluation, and take it. But the other oneís the university-wide one.

A couple other announcements Ė the final exam as I mentioned before, but I will mention it again Ė it is an open book, open note exam. Bring printouts of your other programs if you want to. You can bring the text book for the class. You can bring your Karel reader if you want, although I can tell you right now that Karel will not be on the final exam. And Iíll give you a list of topics as to whatís actually fair game for the final, and what kind of stuff is covered in the book thatís not gonna be on the final just as part of our final review. But you can bring the Karel course reader if it just makes you feel better to look at Karel. Youíre not gonna need to worry Ė or maybe thereís some algorithm in there that just reminds you of how to write Java. Youíre welcome to bring it, but youíre not actually gonna need to know Karel for the final. It is closed computer, though, just like the midterm exam, so if you have a laptop, donít bring it along, or if you bring it along, donít turn it on.

The regular exam is Thursday of finals week, December 13th. Thatís just over a week from today, 12:15 to 3:15 p.m. in Kresge auditorium, and these dates, and times, and places are all given to you on the front of the practice final anyway, so you have them as a reference. And the alternate final is the day before, Wednesday, December 12th, 3:30 to 6:00 p.m. in Kresge auditorium. You are welcome to take either exam. You donít need to e-mail me. You donít need to make prior arrangements. All you need to do actually in terms of making prior arrangements, you need to figure out which exam you wanna show up for, so the only prior arrangements you need to make are with yourself. Pick which exam you wanna go to, and go to it, and itís all good. It just provides you with a little bit of flexibility if you wanna go home a little bit earlier or if you had a conflicting class because I know some people are watching the class on TV. SBD students, Iíll say it one more time, and itís the last time Iíll say it because itís our last class. E-mail me by 5:00 p.m. today if you plan on taking the exam at your site. Hopefully, Iíve already heard from all of you that this applies to, but if not, you have your last chance for like another hour after class today.

And last but not least, anyone find a cell phone in here? Itís not mine, but there are someone whoís in this class who unfortunately has lost their cell phone, so if you do happen to find a cell phone in this class, just come and bring it up to me after class, and I will make arrangements with the student to get it back to them. So any questions about any of the administrative kind of stuff before we sort of delve into some unfinished business? So we have a little bit of unfinished business in this class, and the unfinished business is the graphics contest Ė well, besides our final review. And Iíve gotta say that the graphics contest Ė last time, I told you they were just impressive. I think they were more than just impressive. Some of them were just jaw dropping, so Iím gonna show you actually, and announce the winners of the graphics contest, as well as show you the winning entries. And weíll also do the random drawing to see of all the people who entered who gets the bonus prize.

So our first winner, and if we have a little fanfare, I can kinda slide this to the side. Actually, Iíll slide both these to the side. So we have two categories. We have algorithmic and aesthetic. In the algorithms category Ė algorithms, I canít even spell these days anymore. Is David Tobin here? David, come on down. So good job. As part of winning, thereís a couple things you get. One is you get a bag of candy, a whole bag, well, not the whole thing. You get one of these. You can pick which one you want, though, so rummage through. A Milky Way fan?

Student: [Inaudible] Milky Way.

Instructor (Mehran Sahami): All right, thatís always good. And weíll show you Ė weíll demo your program and show whatís actually going on, so the program that David did was a program to do fractals. And so I will show you that program, and what is particularly cool about the program. So if we do fractal graphics, it kinda starts off, and it shows you a fractal.

And youíre like oh, thatís kinda cool. You need to do some math. You need to figure out some stuff with fractals. But as many of you know, fractals you can kind of zoom into at any range, so we can pick a range over here, and it will automatically zoom in and expand out, and we can just keep zooming into the fractal if we wanna keep going further. Now besides just that, thatís kinda cool in itself, thereís also some built-in fractals. So thereís a few that David has lovingly provided for us that we can kind of look at, and thatís kind of cool in itself. Now the thing that really made me go, ďWow, that is really cool,Ē is not only are there these built-in fractals, thereís a little text box down here. And in that text box, you can type in an equation for a fractal that includes exponents, and you type in the equation, it actually figures out Ė it parses your equation, runs the math on it, and then generates the fractal.

And you can do this Ė itís sort of freeform. I was kinda playing with this other day, minus X raised to the fourth, so this X plus X squared minus X to the fourth down here, and it takes a little while because itís rendering every pixel on the screen how it should look. And so you can get these really cool effects, and then we can always zoom down. So it takes a little while to redraw, but it goes ahead and redraws it for you. So not only is it doing all the graphics, but it also is providing the opportunity for you to just type in an equation for it to understand the equation and render it, so very nice work. Thanks very much. And so as you know, for that effort, you also get 100 percent on anything in the class, which can include the final exam, which means at this point you can take your practice final and be like recycle bin if you choose to take the hundred on the final, which means you just donít show up, and when I see that little glaring gap I know oh yeah, that was 100. That doesnít apply for everyone else, okay. Also, in the aesthetics category, is Sally Hudson here? Come on down. It takes a little while. You also get your choice of the random candy. And you might wonder why thereís random candy because well, I just buy a lot of candy at Safeway. Kit Kat fan? Good times. And what Sally did for her program Ė this is also pretty Ė well, a lot of the programs actually have very good algorithmic and aesthetic qualities, so itís hard to just pick one for the other, but itís a program called the Tessellator.

And Iíll show you what the Tessellator does. It starts with a little square. Anyone a fan of M. C. Escher? A tessellation is just where you put a bunch of little things on the screen, but they all have to fit together. So you can click on any part of this square, and to guarantee that itíll tessellate, the part of it that should allow for the tessellation to happen, basically sort of the corresponding piece on the other side, also kind of expands out. We donít want the tessellation to overwrite itself, so we can just kind of pick random areas, and that creates little places Ė or we can go this way Ė that create the tessellation. You might say, ďThatís kinda cool,Ē but now we click set tile to set what the tile is. Weíve now defined what the tessellation tile is. We can change its size. So letís say I make it a little bit smaller because I like small tessellations, and thatís kinda cool. But now I can pick multiple tiles of multiple colors, so letís say I want three different colors. Letís see. I have little my red, blue, green sliders over here, and notice the color changes as I slide, so I slide over here, so thatís kind of a puce. I donít know. Well, weíll set the color. So it indicates your color over there. Thereís color No. 1. Letís just go Ė as the big Stanford Cardinal fans, weíll just go for red, although cardinal is slightly off from red, and I donít know where itís actually, so maybe itís got a little blue in it? Maybe a little green, too? Letís just say thatís cardinal, although you would look at that and say, ďBut Mehran, thatís really salmon.Ē Thatís cool, too.

And then weíll just pick another color where weíll go, ďWe wonít go white.Ē Thatís where you have all the Ė you could even just teach red, green, and blue with these three sliders by themselves. What happens if we put red and blue together? Oh, thatís too close to the other one. Letís just go for some blue, so we set the color. Now at this point we go tessellate. And youíll notice because of the way the piece is drawn, you can tessellate everything together of the multiple colors. And you might think thatís kind of cool, and thatís kind of cool in itself, but itís kinda even cooler if the tessellating pieces decide to pop out and bounce around, multiple of them at the same time. So very nice piece of work. Thank you very much. And this keeps going until theyíre all done, and you can actually just reset and do the whole thing all over again, and thatís pretty cool. Now both of those programs are pretty cool, and you both get hundreds for your work. There was one program that was entered that when I showed it to the Ė well, first when I saw it, I went, ďOh my god,Ē because it made you weep in a really good way. And then I showed it to the section leaders. Ben and I were demo'ing these because the section leaders all picked the winning entries, and they saw it. And as we went more and more into the different pieces, every time we showed a different piece, everyone just went, ďAh,Ē and it was just unbelievable. So Chris Miel, are you here? Come on down. This is an additional award weíre giving called the peoplesí choice award because the entries were so good that we figured why stop at two. Because when it comes down to it, in this class there is some level of stuff that I want you to know, right? And if you demonstrate that you know that stuff, we can have some more awards. Itís not a problem. So Chris, first of all you get to pick a bag of candy.

And now I will show you Chrisí program which is Zelda. All right? So it begins with this, and youíre like, ďOh, thatís very unassuming.Ē So you start with the beginning graphics screen. If you look at this one thing, you kind of look at this for a while, and then you realize thereís a little flash of light that goes across. Someone had to animate that, and they had to think about it. And so you can load a game, or you can start a new game, so Iíll show you a new game. It has some nice graphics in there where again if you actually read everything Ė anyone in here Zelda fans? Yeah, I was when I was much younger. Itís actually a very funny sort of take on the Zelda concept. Notice, if I turn different ways heís Ė oh, getting a little feedback there. Thereís a shield that I can use in different directions, and there are different screens I can go into, like I can go into this house over here, and here I can buy stuff. Like Iíve Ė Iím a little bit here so my hearts are down here, so I can say, ďHey. I wanna buy a couple more hearts,Ē and Iíll buy a potion, too. And hereís my funds over here. Hereís my magic potions and my emeralds that I buy stuff with. And Iíll exit.

And then I just kinda cruise along, and thereís stuff that goes along in the world including things that like fade. Notice the fade effect there. And as you continue to cruise along in the world, you see various kinds of things that maybe we wanna kill, and just kind of cruise along. And you get to places where thereís just animation going on everywhere, like the waterís animated. Iím getting beat by the octopus. Never let yourself get beat by an octopus. And you canít do things like run into the river. It actually is aware of what Ė aw, I died. That laugh goes on a little too long. Thereís a whole world you can explore. You can save the games and come back. I should be using my shield, but Iím kinda ignoramus with the shield. Oh, yeah. Thatís right, buddy. Sometimes when you kill something, it turns into an object. Sometimes it doesnít. And it was like every time you enter a different screen, it was like this. It was just astounding. So Ė oh man, I havenít even seen this screen Ė [inaudible]. I know what Iím gonna be doing over winter break, so I will save you all the rest of the time.

Weíll just go in here, so you can see some stuff thatís going on. Music changes. We probably canít actually show this on the video because I think are actually sampled from the real game, perhaps? Yeah, thatís live from the city. But thank you. Thatís just an astounding piece of work. So sort of what I refer to as the peoplesí choice award goes to Chris Miel. Am I pronouncing that right? Is that Miel?

Student: Yeah, itís Miel.

Instructor (Mehran Sahami): Miel. All right. Good times. The other thing that came up is these, you get 100 percent on anything which is nontrivial, right? Youíre getting 100 percent on the final, and I looked at this, and I said, ďI could give Chris 100 on the final, but I think heís pretty much demonstrated anything that I could possibly have wanted him to know in this class, so Iíll just give him an A plus.Ē So youíre done. Thatís your grade. [Inaudible]. Thanks. And if any of the contest winners if at any point in your career you should need any recommendations, let me know. Iíll be happy to write it. Now there were all sorts of honorable mentions. So these are all the winners of the contest. There were some honorable mentions, and I wanna recognize a couple of the honorable mentions that really stood out. Unfortunately, we donít have time to demo them all. There were a lot of cool programs, but a couple honorable mentions as well. Jasmine Mann? Yeah, you wanna come on down? And also Paris Georgegoudis? Am I pronouncing that right? Are you here? Oh, just too good to come to class, but weíll sort of give it to him anyway, Paris G. So Jasmine, you are also entitled to candy.

Student: Yay.

Instructor (Mehran Sahami): And so one of the things you also get, as well as Paris whoís not here, just for the very strong effort that you put in, is you know thereís a participation grade in the class. So you automatically get 100 percent on your participation grade. So thanks very much for a nice piece of work. Jasmine did a musical piano that displayed some stars and had music, and Paris actually did a backgammon program with a computer player as well. So now thereís finally a little more unfinished business to do which is that besides all the winners, there is also a random drawing for everyone who put a serious entry into the contest, and both Jasmine and Paris are both eligible for that potential 100 on the final. If you get the 100 on the final, though, you donít get the 100 on the participation because you only get one prize. Itís your choice because if you happen to win, you get that 100 on whatever you want, so you can still use it for participation. But in terms of everyone else whoís in the contest besides the winners, there was 14 total people who were in the contest. So I figured why donít we just pick the winner collectively in a random drawing, and so I wrote a little program, which just pales in comparison to Zelda. Actually, I even took this program from someone and modified it. Thatís how low budget this effort was because it was just a cool program. It was like, ďOh, thatís cool. Let me just use that rather than rewriting it all myself.Ē

So what this does is it takes each of the entrants of the graphics contest and puts their name on a card. And those cards are shuffled and displayed on the screen. So what weíre gonna do is pick one of those cards, and then this will gradually go through and reveal all the other cards who are the non-winners unfortunately. So you can sort of Ė I know itís kind of brutal, but that way youíve got a sense if youíre still kind of in the running as we go along. So now, I need to pick a card. These are all random, so it doesnít really matter which one I pick, although afterwards itíll be like why didnít you pick the one to the left. Oh, letís just pick this one. This one good?

Student: Yeah. [Inaudible].

Instructor (Mehran Sahami): Yeah. All right. See? Hereís everyone else. They get revealed slowly. I donít know if you can hear the sound effect of the cards flipping over. Sorry, Jasmine. You donít win again, but you still got a prize up here. Yeah, some of the cards once theyíre all covered up Ė well, Paris doesnít win again.

And the winning entrant is Ė [inaudible] actually did a very nice painting program. I donít remember all the entrants. And you have your choice of the Three Musketeers or the [inaudible] bar. No one likes the Three Musketeers. I should write that down. Iíll remember it. Send me e-mail Ė also gets 100. Very nice work on the graphics contest. Thanks very much. And now with that bit of business taken care of, we can move on to reviewing for the final exam. So a little bit of final review, what you need to know, what you donít need to know, and maybe a couple examples of the level of difficulty we expect.

So in terms of whatís actually on the final, this is kinda whatís on. And at a highest level, whatís on the final is Chapters 2 through 13 of the book. Okay? So Karel is not on there, and Chapter 1 on history of Java not on there either. Now 2 through 13 covers a bunch of stuff, so in relation to that, let me start off by telling you whatís not on the final so you get a sense of what are some of the things you donít have to spend your time on. Then Iíll spend some time emphasizing some of the things you do wanna worry about studying. So history, the Chapter 1 stuff as I just mentioned, not on the final. Karel the robot not on the final. Heís fun, but weíre sorta done with Karel at this point. Zelda might be on the final. No, just kidding. Something people have been wondering about, stack heap diagrams not on the final. So stack heap, the diagrams are not on the final, but you might still be expected to know what is the difference between a stack and a heap, what gets allocated on the heap versus what gets allocated on the stack, but in terms of actually drawing the diagram with the memory addresses, thatís not something that weíll ask you a question on.

In terms of the chapter that has to do with images and graphics, thereís a whole bunch of stuff if you read the whole chapter about bit operations on images. Bit operations not on the final, so if you sort of skipped that question, we didnít talk about it much in class except where we did a simple example where we took a picture that was color and turned it into black and white. Remember that? On Halloween, no less. I remember the lecture. Bit operations not on the final exam. You donít need to worry about that. Something we sort of stressed the whole time in the class which you didnít need to worry about was polar coordinates, so polar coordinates itís not like hey, weíre gonna whip them out in the final exam, now you need to know them. You didnít to worry about them before. You donít need to worry about polar coordinates with respect to the graphics, right? And thatís the only place they actually get used. Somewhere else in your life if you go exploring the poles or something, you might care about polar coordinates, but not in this class.

So other things you donít need to worry about: layouts. We talked a bit about layouts when we talked about things like the border layout, and the table layout, and all this kind of stuff. And I showed you could lay things out where you have a program that has a text area for the console, and a canvas, and all that. You just donít need to worry about layouts at all. Thatís not something weíll ask about.

Sorting Ė so Ben gave a nice lecture on sorting. Sortingís kinda useful. These days, sorting is mostly a solved problem. Weíre not gonna ask you any sorting questions on the final in the sense of you donít need to know any of the special sorting algorithms. We may ask you to keep something sorted, but if you think about keeping something sorted, thatís different from sorting it from scratch. So we may or may not ask you to do this, but in terms of being able to sort something from scratch, like knowing selection sort or insertion sort, those algorithms you donít actually need to worry about them. The stuff we did on advanced topics where we talked about threads, you donít need to know. It was an advanced topic. It was for your own edification. Some of you used it in graphics projects, which was Ė or graphics contest entries, which was nice to see, but you donít need to know it. Weíre not gonna do any kind of testing on threads. Okay? And after threads, there was also a lecture on standard Java where we talked about the main method, and generating jar files, and all this nuts and bolts sort of stuff. Thatís not something weíre gonna test you on either in the sense of standard Ė weíll still test you on Java. That doesnít mean you donít need to know any of Java, but just that specific stuff we talked about in relation to standard Java versus the ACM libraries, thatís stuff you donít need to know about either. So what do you need to emphasize when you actually do your studying? Here are the topics, so if you pop all these topics out of Chapters 2 through 13, the rest of the chapters are pretty much fair game, and here are some of the topics that generally come up which you wanna make sure youíre good with.

So the most basic thing is you need to be able to write programs, so you need to be able to build a program. That means knowing all the basic syntax that we talked about, what a class is, extending console program, if while loops, for loops, all that kind of stuff, youíre just gonna need to know that. Itís not like the exam will not have while loops in it, like do the exam without while loops. Itís not gonna be like that. You should know also about objects, classes, and interfaces. What does it mean to implement an interface? What does it mean to define an object? Whatís a constructor for an object? What goes in a constructor for an object? Stuff like that. So you should be able to Ė if somewhere on the exam I asked you to define a class that does something, or perhaps define a class that implements a particular interface and show you what that interface is, you should be able to do that. Note on your sample Ė on your practice final, there actually is exactly a question of this form where you write a class that implements an interface so you get a sense for what that actually is.

You should know about the mechanics of method calls. And part of the mechanics of method calls is what kind of things get passed by reference, meaning they get changed once you actually pass them, what kinds of things get passed by value, which means you get a copy and they donít change, and how those interact with whatís actually going on when you make a method call. And so related to that is the notion of primitives versus objects. What are the primitive types? What does it mean for something to be an object? The general generic type object that all things that are objects are a subclass of the type object, so if you wanna write something that is entirely generic, you could write it in terms of being able to keep track of an object for example. And you did this to some extent when you did for example breakout. There instead of an object you had a GObject that you kept track of. What was the thing on the screen for example that you collided with? You wanted to see if that was a brick, or the paddle, or whatever? Hopefully, you did that for breakout but thatís kind of the same idea there.

So objects, classes, all that happy stuff Ė this is now in the what is in the final rather than not on the final, so Iíll erase all the not on the final stuff. Other things that are also on the final, strings and characters. Know your strings and characters. Especially in relation to strings and characters, know your string operations. This is just a good thing either to have some tab say in your book to where the list of string operations is, or to have it on a separate piece of paper, or to print out for example lecture notes that are on the class website that contains a list of the standard string operations. Itís just good to have them as a reference because you will invariably be doing at least one problem perhaps more that involves some kind of string operation manipulation, and unless you have them all memorized, if you have some handy reference, thatís probably a good thing to have. And related to string operations is also Ė and dealing with characters, so the fact that you can pull individual characters out of a string, you can concatenate a series of characters together to build up a string which is a common way of actually building up a resulting string. Thatís also kind of related to that, so you need to know the interplay between characters and strings. Graphics, yeah, thereís probably gonna be at least one question on there that involves graphics, and thatís in terms of the ACM library, so all your happy friends like GRect, and GOval, and GCompound, and all that kind of stuff could potentially show up on the final exam. Again, this is probably somewhere in your book where you have all the different methods listed out for the ACM graphics library, it might be worth putting a little post-it or something in there so you can flip to it quickly if you need to.

And related to graphics is event-driven programs, and by event-driven programs Ė weíve looked at two kinds of event-driven programs. One is event-driven programs having to do with mouse inputs, so what we refer to as a mouse listener, like was the mouse moved, was the mouse clicked, all that happy stuff that you did for example in breakout. And then the stuff that youíve been doing more recently with name surfer and also with face pamphlet which are action listeners which are various kinds of buttons, or text fields, or whatever the case may be. So you might have some program that actually for example uses both of these things that may take some mouse input or whatever and does some modification on graphics as a result. Uh huh?

Student: [Inaudible].

Instructor (Mehran Sahami): Ah, excellent. I was just about to say that, and you raised your hand first. No, you donít need to worry about key listeners. So anything we give you will be in terms of mouse listeners and action listeners. You donít need to worry about key listeners.

So other kinds of stuff Ė then we got into the world of data structures, and we had arrays and array lists. These are also fair game for the final, so some things you should know is the differences for example between arrays and array lists. When is appropriate to use one of them versus the other, so the use of them, or use them. Theyíre your friends. In the sense that if I give you a problem that involves Ė I give you kinda the setup for that problem, you should be able to choose is that appropriate for an array or an array list. I might tell you which one you should use, but if I donít, you should be able to determine whatís appropriate.

In terms of arrays, you also do need to worry about multidimensional arrays. You did some of this presumably already on the Yahtzee program, but multidimensional arrays Ė at least within reason. I wonít give you anything like a 16-dimensional array, but probably two dimensions is fair game. Three is the upper limit. I wouldnít give you anything more than three dimensions. Likely if thereís something with multidimensional arrays, itíll probably be two at most. Maybe itíll just be single dimension arrays. And also with array lists, everything that weíve done in this class, which is also everything you need to worry about for the final, is sort of the Java 5.0 or later version of array lists. So in the book thereís always sort of two versions. Thereís the hereís how you use array lists before Java 5.0 and hereís how you use array lists after Java 5.0, or 5.0 and later. You donít need to worry about the before 5.0 stuff. Just the 5.0 and later is all youíre gonna need because thatís all weíve emphasized in the class, and thatís these days what everyoneís using anyway.

And then after arrays and array lists, which was kind of the introduction to the whole notion of Java collections, was thinking about collections. So besides just array lists you also saw hashmap, which hopefully at this point you are just the master of the hashmap, but you should know the hashmap. And things that come along with hashmaps and collections in general, or the collection interface Ė I should say collection instead of collections Ė is for example an iterator. What is an iterator? How do you get an iterator from a collection? How do you use an iterator? Thatís something that you just wanna be facile with because chances are for some problem to solve the problem, especially if youíre doing something that involved a hashmap, you probably wanna be able to get an iterator. And then hashmap youíve gotta know, ďOh, hashmap, I need to get the set of keys.Ē Right? The keyset to be able to get the iterator on that. So these are also good places to have tabs in your book for quick reference if you need them.

And last but not least, files. So the basics of files. And youíve done a lot of the basics of files already. Know how to open a file and read from a file. Know how to be able to write to a file if you need to write to a file. Chances are we probably wonít have you write to a file since you didnít have to do it on any of the assignments, but at least reading from a file is fair game. So topically, thatís kinda whatís going on there. Now given the topics, let me show you some examples of the kind of questions we might ask besides whatís on the practice final which you already have sort of a whole practice final that you can do, and I would encourage you to do that under a timed condition, so you can figure out what kind of things youíre maybe a little rusty on, and what kinds of things youíre feeling good about.

Hereís an example of the kind of question we might give that involves a bunch of these concepts, which is given a hashmap Ė so youíre given some hashmap whose type is hashmap string to string, and you know that these are keys and values. Find essentially all key values are the same. So what we want you to do is find matching key value pairs. What do I mean by that? What I mean is letís say we have some hashmap where here are the keys over here, and here are the values over here. And I might have some keys like Alice, and Bob, and Cathy. And I might have some values like Alice, Jeff, and Cathy. And so what I wanna find out for example to print on the screen is Iíd wanna print Alice, and Iíd wanna print Cathy. I wanna write out any of the keys whose value is basically as their value in the hashmap. So thatís a very simple sort of set up, but it stresses a bunch of these concepts that you need to know to be able to do it. And thatís kind of hopefully the way a lot of the questions are gonna be on the final is simple concepts but stresses the ideas. So if we wanna think about solving that problem, we might be given some header like public void match keys, and this has some parameter that itís passed like a hashmap from string to string that weíll call map. And all this syntax should hopefully be stuff thatís just second nature to you at this point. You really wanna figure out how to solve the problem.

If you think about this problem, if we wanna find out which keys have the same value as their value, whatís the first thing we wanna do? Run iterate over the keys, right? We wanna have some way of saying, ďOkay, I need to go through all the keys and look at them to see if they have the same value as their value.Ē So Iíd need to have some iterator. The iterator I know would have to be over strings because itís gonna be an iterator over the type of whatever the key is for the hashmap, and Iíll call it it. And how do I get an iterator from the hashmap or over the keyset of the hashmap? So I need to say map dot keyset Ė these are good things to know in the back of your head Ė iterator Ė we sort of string these all together, and so what I now get is an iterator of strings which are all my keys in the hashmap. And now at this point itís just using my iterator but in conjunction with some other functions, like while my iterator has a next Ė and if you wanna use sort of the funky for each notation thatís also in the book where it allows you to do iteration over an iterator in kind of a stylized form, thatís fine, too, but we didnít stress that in class, so Iím not gonna stress it here.

While the iterator has a next element, I just get that next element Ė equals it dot next. And then I wanna see is this key equal to the value. So now itís gonna stress another hashmap concept which is to go look something up in the hashmap, and so I have string value equals map dot get, and what Iím gonna get from the map is whatever matches that key.

So if my key happened to be Alice over here, Iíd go and get the value which is Alice out of the hashmap, and Iíll just keep writing the rest of it over here. Weíre almost done. So over here we just say if the particular value that I got happens to match the key. Now itís gonna stress the concept of strings. So all these kinds of things fit together. If value dot equals key, which means that value equals the key value, then I print out to the screen to the key. I could print out the value, too, because theyíre both the same at this point, but thatís the whole deal. Thatís the end of my while loop. Thatís the end of my method. So thatís kinda the idea, right? This was not particularly earth shattering, but it stresses a bunch of concepts. Unless you remember the little things like, ďOh yeah, I need to get the iterator over the keyset,Ē which is kind of a very standard pattern with hashmaps, it could take you a lot longer than it otherwise needs to take you. Okay, so any questions about that?

Let me show you one other simple example thatís the sort of thing that would be fair game which is a little program called target seeker. Basically the idea here is thereís a little target thatís a red square, and thereís a little target seeker that comes after it which is the black square. And the black squareís trying to get its center to match up directly with the center of the red square, fairly straightforward. And every time I click the mouse, I move the target somewhere else, so Iím just keeping the seeker Ė itís like, ďOh look, Iím so confused.Ē Every time I click the mouse, the center of the target moves to the current mouse location, and the seeker just keeps seeking to wherever that target is. This problem wonít be on the final, 1.) because Iím showing it to you now, and 2.) because itís really difficult to actually put that in a handout. Like take these set of pages and just flip through them really quickly and you can see what the seeker is doing. So how do you turn this into code? And the code for this is actually fairly straightforward. Itís kind of you need to think about what you were doing in breakout, right? So some of the problems that youíre gonna solve leverage concepts that youíve seen in your programs, so youíve had experience with these kinds of things before.

What we do is we initialize the target. Let me just line up these lines so it looks a little nicer. The target is basically just a rectangle whose size is some constant target size thatís defined down here. Iíll just show it to you. Target size happens to be ten, seeker size is twenty, and thereís a pause time of ten, just so you know. So target square is gonna be the target. Target square is gonna be some new GRect that we set up, and thatís a local Ė or a private instance variable that I wanna keep track of. My target square is just a private GRect. My seeker is also gonna be a private GRect, and Iím gonna keep track of the target that I wanna get to in a private X and Y location known as target X and Y.

So when I start off, I just set my target to be a square of this size, its color is red, and itís filled to be true, so it just initializes the target. And now I say, ďHey, the target starts in the middle of the screen.Ē Presumably that would be in the instructions for the assignment, and so I get the middle of the screen. Know your standard ways of computing the centers of something. Thatís always good to know. Then I add my target to essentially the center of the screen, which means if I remember that my target square, the place I add it to a canvas is actually its upper left hand corner, I need to take the target X which is the middle of the screen, and subtract off half the width of the target in both the X direction and the Y direction to get its upper left hand corner. And then I add it to the screen, so this just sets up the target.

Then I set up the seeker, and the seeker is also a square of size seeker size by seeker size, and it just starts at zero, zero. Thatís presumably something that would be given to you in the problem, that the seeker just starts at a different location. And once Iíve set up the target and the seeker, I add my mouse listeners because I need to know where my mouse clicks, and then I just have this loop thatís just always seeking. Itís just always trying to find wherever the target is. And the target starts off at this target X Y location. Thatís where it always Ė how weíre always gonna keep track of it. So what happens is on every step of seek we pause just so the seeker doesnít just jump there. Itís not very exciting if the seeker just jumps there every time. And we say is the midpoint of the seeker Ė letís get that. Thatís just the seekerís current X location, which is upper left plus half the size of the seeker to come in. And we would do the same thing on the Y, which means we would go down half the size of the seeker in the Y direction. If my target X is greater than my current X, then I need to move positively in the X direction. Otherwise, I wanna move negatively in the X direction.

And similarly with the Y coordinate, right? If my Y Ė so I find the seekerís midpoint Y. If my Y is less than the target Y, I need to move toward the target Y, so Iím gonna increase Y. If my target Yís less than the seekerís Y, Iím gonna decrease Y. So I just find these offsets. Are you gonna move in the positive or negative X direction, or are you gonna move in the positive or negative Y direction? And then Iím gonna have the seeker move one step in that direction. Uh huh?

Student: Whyíd you do that instead of just finding the location [inaudible]?

Instructor (Mehran Sahami): Having it move consistently with Ė

Student: [Inaudible].

Instructor (Mehran Sahami): Well, so if you actually wanna do that, if you wanna have it look more nicely so that rather than trying to match up the Xs and then the Ys, if you wanna move toward it, you need to compute angles, and I just didnít wanna deal with polar coordinates, but you actually can do it with polar coordinates. We just donít do it because weíre not Ė thatís another thing that you know. You donít need polar coordinates, which is why you donít need to know that.

And the only time the target gets updated is when the mouse gets clicked. We set the target X and the target Y to be the new location of where we clicked. We removed the old target from wherever its location was, and we add it back to the new location. And thatís the whole program. Thatís kinda the level of difficulty. Now this is a program that when you have the code, I can explain it all in like five minutes or so, but when youíre writing this from scratch, I would probably expect that writing this program would take probably on the order of about 20 to 30 minutes to write it from scratch with some false starts, et cetera, et cetera. But this is kind of the level of difficulty you could expect to see on the final exam, and a notion of about how much time we would actually give you for it. So any questions about this or about our little hashmap example? That kind of gives you a sense of a set of topics or the richness in some of the questions. And you sort of got the explicit list of topics as well for the class. So any questions about the final? Youíre feeling okay. So I wanted to give you a bit of wrap up if thereís no more questions, given that this is our last class. So if you kind of think about where weíve been, we sort of had ten weeks Ė a little less than ten weeks if you count some Ė oh, we had a day off after the midterm, and we had a day off on Friday, and whatever the case may be.

But I would imagine for a lot of people in this class, there wasnít necessarily Ė there was some previous programming experience because I went through all your Assignment No. 1 e-mails. Remember those? That was so long ago. There was some prior programming experience, but there wasnít a lot of programming experience. So the real hope in this class was to get you to a point where basically you could take this journey over here from not necessarily doing any programming to getting to a point over here where now a bunch of the stuff that you actually see, like games that you actually play either online or in an arcade if any arcades even exist anymore, like on your Xbox or whatever, say like Zelda.

For other kinds of things that you interact with like a data management system or social network, when it comes down to it, hopefully this class has helped demystify some of those things, that really underneath the hood, yeah, thereís a bunch of listeners that are looking for things, and there are some graphics that get updated, and thereís little pause loops, and we need to look for mouse events, and keyboard events. Thereís a bunch of big data structures like arrays, and hashmaps, and stuff like that. They keep track of stuff like your list of friends in the social network, or the communities you belong in. When you use a search engine, this is just doing the same thing. Thereís just some really huge repository of data that you now need to go look up. And the interesting problems that come up are things like this huge repository of data doesnít fit on one computer anymore. So what do you do? You break it up onto a bunch of smaller computers, and each of them gets some chunk of the data. And now you go from just simple data management problem to something worrying about breaking up data into bigger pieces.

And this is how computer science progresses in the sense that the problems get bigger in terms of what we actually deal with, and the interactions with the user get more complicated. But hopefully along the way what you learned in this journey was the science of whatís involved in doing this stuff. So itís just a bunch of science as to how you actually figure out how all these pieces of a game interact, or how data is kept track of in some larger system, especially when you have smaller components that need to be kept track of in arrays and hashmaps that build up into larger components. And so those are the scientific parts of it.

But hopefully as you also saw today when we showed some of the graphics contest examples and when you wrote your programs there was obviously a variety of ways of doing the programs. That was the thing that at the beginning of the class isnít always clear is thereís a huge art in computer science, which is why the textbook for the class is called the Art and Science of Computer Science Ė is this class, we taught you a lot of this stuff, and we hopefully taught you along the way some of the skills to be a good artist and to be a good software engineer. And the real key in programming is youíll learn more of this stuff as you go along, as you become a computer scientist because there is computer science after all in computer science, and so youíll learn more of this stuff. But what youíll also develop as you go along the way is really being an artist.

Thereís a famous quote by someone named Don Knuth whoís considered the father of modern computer science, which interestingly enough heís still alive and heís in this department, so itís kind of like youíre in the same department Ė you should go look him up, actually Ė with the father of modern computer science. And one of the things he said is that programmers tend to better if they subconsciously think of themselves as artists. When youíre putting something together, donít think of it like youíre doing a proof in math. Itís important to figure out all the logical steps, but at the end of the day, youíre putting something together that has an inherent beauty to it. And thatís part of the real beauty of computer science. So I hope you enjoyed the journey. I hope you learned some stuff along the way. And I just wanna thank you for taking part in the little journey we had together. So good luck on the final exam.

[End of Audio]

Duration: 47 minutes