Lecture 05

Section 9 Solutions

Programming Methodology-Lecture26 Instructor (Mehran Sahami

Programming Methodology-Lecture26
Instructor (Mehran Sahami): All right. Welcome back to – what kind of day is it going
to be in 106a? Anyone want to – fun-filled and exciting. It always is. Thanks for playing
along. So a couple quick announcements before we start. One announcement is that there
is one handout today, so several people have asked in the past, these programs that I
make in these classes are kind of cool. I would like to be able to share them with my
friends and relatives and whoever else. We're going to talk a little bit about how you do
that today and what that means underneath the hood, but the handout actually explains it
all. It's this notion of a jar file. We'll talk more about a jar file as we go along.
The graphics context, for those of you who are doing it, is due today. Just wondering,
quick show of hands, how many people entered the graphics contest. Wow. Not as many
as I would've thought. There could be a couple people who are at home, even if you don't
win of getting 100 on the final in a random drawing. So that's a good sign.
One thing I do want to check, I just heard a little bit before class that some folks were
having some trouble submitting their graphics contest because there actually might have
been an issue with the server that takes submissions. So if you submitted to the graphics
contest, whether you're in here or you happen to be watching the video, email me, and let
me know what the name of your contest entry was. That way, I know for sure that we
actually got all the contest entries that we think we had, and if we didn't get one, I can
email you back. The thing I would ask you is, if you can't email me any time this
weekend because this weekend is actually, when we're going to make the first pass
looking over all the contest entries, and then we're going to have a small pool that we'll
take to the section leaders. They will vote and give the winner. I'll announce the winner
in class next week.
I might show a demo of the winning two as well. We might do the random drawing in
class as well to see who actually gets the third coveted random drawing spot, even if you
don't win. So please email me if you entered the graphics contest, just to make sure.
One other thing with email for SCPD students, I know it's still a little too early to think
about final exams, but if you're an SCPD student, it's not too early. If you're not an SCPD
student, it's not too early, either. But for SCPD students, if you're taking the final exam, if
you plan of taking it at your sites and you're not going to come on campus to take it,
email me by 5:00 p.m. December 5, letting me know that you're taking it at your site and
the name and email of your site coordinator, just like the midterm. That way, I can get the
information to your site coordinator for the final well before the final.
If you're planning on coming on campus to take the final, you can feel free to send me an
email to say you're coming on campus. If I don't hear from you, I will assume you're
coming on campus. So you only need to email me if you're taking it at your site, so please
do that if you're an SCPD student and you plan on taking it at your site.
Any questions about anything we've done so far before we dive into our next great topic?
All right.
One of the things that we've done the whole time in this class is we use these things
called the ACM libraries. The ACM libraries are a set of libraries that are actually created
by a task force of people. The ACM is the Association of Computing Machinery. We
talked about them at the very beginning of the class when we talked about these libraries.
They put together some nice libraries of stuff that are really useful for teaching, which is
why we use them.
Today, what I'm going to do is lift a little bit underneath the hood and talk about standard
Java, which is what you would get if you didn't use the ACM libraries and you just used
the standard Java libraries. Now, there's no reason why you can't continue to use the
ACM libraries after this class. They're just another set of libraries that were written by a
group of people that you're certainly welcome to use.
So there's no reason why you should stop using them, but there were a couple important
issues related to standard Java. Now it's time for you to know. So the first thing that's
related to thinking about standard Java is when you're running your programs, when you
go into Eclipse and you click on the little running guy to compile your programs. It give
you a list of what classes you actually might want to run.
If you only have one project, you may only get one choice, but one of the things you kind
of think about is in the name surfer program, I actually have four or five different classes.
How come it always knew which class to run? How come it always knew the name surfer
class was the class that I actually should run? Anyone want to venture a guess?
Student: [Inaudible].
Instructor (Mehran Sahami): It's the only class with [inaudible] which is very related to
an underlying issue. It's the only class that actually was extending programs. So one of
the extended programs, what actually was happening in these ACM libraries is you were
getting a method called main. Main is actually the place – you're old enough to see main.
Main is actually the method at which Java classes actually start running.
So one of the things you should think now, you never wrote a method called main. I
never saw a method called main, and you're telling me that's where Java programs
actually start running. Yeah, in fact it is. It's because programs provided this main method
for you. What this main method did in the program was essentially get the rest of you
program running by getting a few things set up and then kicking off your run method. So
you didn't actually need to worry about this.
But now you're sort of old enough to actually see what that main method is all about. So
if we think about what this main method does, the header for the main method is also
kind of weird. This is part of the reason why we never showed you the main method
before. The header for the main method is actually public static void main, but we're not
done yet. Main actually has some arguments. It has an array of strings called args and
arguments, and then something in here happens inside of me.
If we showed this to you on the first day, we would've had to go through and explain
what all these words meant before we explained what main even was, before we
explained how you write your first program. That would've been a pain. Now we can just
tell you. Public mains is a public method. You know that. You probably recall the other
public methods you've written. Static means that this is actually a method that belongs to
the class – it's not something that you would actually call on a particular object.
So you never have some object – like, here's my object X, and I call X .main. Main is just
something that gets called. It's a class method as opposed to being a method that gets
called on an instance. Void means it just returns nothing.
What is getting passed in here is an array of strings. Where is that array of strings coming
from? This actually harks back to when computers weren't all nice and graphical and
everything. When people wrote programs, the wrote program and were typing on what's
called a command line. They wrong the name of the program out. They actually typed it,
and then they typed a bunch of things that they wanted to be passed into the program
such as initial information to start that program. That was the initial thing, so if you had
some program like name surfer, you might actually start off by giving the name of the
program.
Then after name surfer, you might give it the name of the data file, like data dot text. You
might've given it some other things as well that were separated by spaces. This list of
stuff is essentially what gets passed in here as arguments. They're strings, and this is how
the program would actually know what came in on the command line when the program
was kicked off. Java's not that old of a language. It sort of came around and gaining
popularity in 1995. People weren't doing a lot of this in 1995. I already had my mouse
and my folders and all this other stuff, even if you were six years old. You probably did.
You're like, I never typed this stuff, so why do I care about it? The reason why Java's
derived from another language called C, and there's a variation called C++ that was
created when people were writing programs in the days of yore. The whole notion of
main and having some arguments to get passed to main kind of came along with the
baggage of actually having a program language that matches the same style programming
languages when they did do this.
So a lot of the times in real Java programs these days, there aren't really any arguments. If
there are arguments, there's some system parameters or something like that. We don't
usually worry about them. So when you go and look at some other Java program that isn't
using the ACM libraries and you see this main thing, and you're wondering what it's all
about, you can think of main analogously to run. It's just where the whole time you've
been thinking of run as where you're execution starts, main is really where execution
started.
If you think about execution actually started in main, so how did this thing actually kick
off my run method? Now you're sort of old enough to see that, too. So what it actually
did – let's say this was the main method is something like name surfer. So somewhere
inside of a program, inside of the ACM libraries for program, we had this main method
that figured out what the name of your class was. Essentially, it had a one-liner in it that
would've been equivalent to this.
New name surfer dot start cards. So it's a one liner. Now you know what this means.
What was it actually doing? When main started, no objects exist in the world. It's a static
method. So there's no object that you're giving the main message to. Main just wakes up
and says, hey, I'm main. What am I going to do? Why don't I create some object of this
particular type, name surfer, which happens to scan an object, which is your program.
Remember your program, as we kind of talked about, implements the run method, and
actually a program underneath the hood implements the runable interface that we talked
about last time, with threads. We talked about the runable interface.
All programs implement the runable interface. How do you kick off something that's
runable? You say start. So what it basically did was created and object of your class,
which was name surfer, and told it to start. It happened to start pass along these
arguments, but you never needed to see those arguments. As a matter of fact, you never
did see them because when your object was in stand shaded, it didn't expect any
arguments. So the arguments actually got passed to this thing called start, which just
ignored them, basically, and then started your run methods to kick everything off.
Last time when we talked about start, we talked about this in the context of threads. So
we said, oh, you create a new thread, and the object that's you're going to start running,
we put inside a thread. We kick the thread off with start. In this case, we're not actually
creating a new thread. We're just saying we want to start executing this object I just
created. It implements runable, so you'll start running from the method run, but I'm not
creating it in thread. So this thing is going to execute in the same thread of execution as
the entire class.
So I don't suddenly kick off something that's running in parallel with this guy. It's
actually going to sequentially start name surfer, and that's the last thing this guy does.
Run your whole program. Any questions about that? Kind of a funky concept, but that's
basically what's going on. You should see it. We were creating an instance of your
program and then just kicking it off. That's why, this whole time, we had this thing called
the run method that had to be public because it was implementing the runable interface.
But now you've seen main.
We could've just had main in your program to begin with and included all this code. The
only reason we didn't put it in there before is because we didn't want to explain any of
this stuff. In week two of the class, right after [inaudible] all holding hands and singing
Kum Ba Ya. We're like, oh, it's [inaudible] the robot. Let's give Java, public static void
main. Straightening args. You're like, what is going on?
We hadn't done arrays. We hadn't done classes worrying about static. We certainly hadn't
done methods. We hadn't even done parameter passing. So we just waited until the end.
Now you see it.
Now that we have that idea, now we can think about, okay, if this is kind of what the
standard Java world is, let me think about taking this idea and using it to help me take my
existing programs that I've written and pack them up into a form so I can share them with
family and friends. So that's what we're going to do next. The basic concept of doing this
is something that's called a jar file. You've actually seen jar files before because you've
been working with something this whole time in your projects called ACM dot jar. This
was just a jar file that contained all the ACM libraries.
Basically, all a jar file is, where does it get its name. It's not a big mason jar, although you
can think of it like that. It stands for Java archive. That's where the name comes from.
The basic idea behind the jar file is this can contain a whole bunch of different stuff.
Most of the time, what it contains, is a bunch of classes in Java. You can think of this as
the complied version of the classes.
You can actually put source code inside the jar if you want, but most of the time when
you get a jar, it doesn't have the source code associated with it. I just has the actual dot
class files, which are the compiled version of the files. So you could put source files in
here if you wanted. You could put data files in here if you wanted. You could put a bunch
of things in here if you want, but we're really going to focus on the case of putting classes
in here.
So one of these already existed for you. It was ACM dot jar, and we're going to figure out
how to actually create some of these ourselves and use them because you can actually
think of them as something that's executable.
So if we come to the computer, here's name surfer. This is an actual working version of
name surfer, so I'm not going to show you the rest of the files in case you're taking
[inaudible]. All the code's in here, so the first thing I did in the name surfer program is I
thought about, hey, I want to think of this in the standard Java world now, even though
you're still using the ACM libraries. When I want to build this jar, I want to build it in a
way that sort of makes it maximally portable. I can give it to someone who's over here on
this PC and someone who's over here on this Mac. They don't need to have a Eclipse or
anything like that. They can just run it. That's the whole point.
So the first thing I'm going to do is to introduce my friend, the main method. So basically
I put in the code you just saw. I add a method, public static void main has this array of
strings called args that sets the parameters. That's just the way main is always defined to
be. What it's going to do is create a new name surfer object and kick it off. That's the only
thing I need to add to my program. So anywhere you had some class that extended
program, you would add these three lines of code to get it compliant with standard Java.
Once we do that, we need to create the jar file, which is the thing we're actually going to
be able to execute. One thing you might be saying to yourself is that the ACM libraries
already provide this. So why am I putting it explicitly in there? As a matter of fact, it's
not super required that it be in there. The real reason why we put it in there is to try and
maximize portability. Even though Java's supposed to have this property where we write
the Java code once and it can run on PCs and it can run on Macs and it can run on Vista
and Tiger and all this other stuff, in reality, there's some little differences between these
operating systems. So little problems creep up here than there, every once in a while. You
actually saw a few of those in class on occasion. Some of you experienced them in the
Lair.
By putting in this line explicitly rather than kind of relying on the code that's in the ACM
libraries, this is actually doing a bunch more complicated stuff. It needs to infer what the
name of your class was. You never told it explicitly, hey, ACM library, I need a new one
of these guys. Java has a facility called reflection where it can go and say, oh, let me take
a moment to reflect. I'm going to go and look at the names of your classes and then do
something to actually generate some code based on the names of your classes, which is
what it was doing.
But that kind of stuff can get a little bit frosty, so we're just going to say, hey, ACM, don't
worry about it. I'm just giving it to you. I'm a nice guy. So just put it in to make it
explicit. It maximizes portability is the main reason we put it in.
So how do we create the jar file? What we're going to do – these steps are all in
excruciating detail in your handout, so you don't need to worry about scribbling down
notes quickly. What we're going to do is you first click – that's the most difficult part of
the whole thing. You select the project that you want to create the jar file from. So name
surfer. Then we go to the file menu, and we pick export. So this whole time you were
doing imports when you were bringing stuff in, now it's finally time to give something
back in the form of an export.
So what you want to do when you click export is it brings up a little dialogue box.
Sometimes this is closed. Sometimes it's open. It's not a big deal if it's closed. Open it.
Inside Java, you click on jar file. That's what you want to create. It has this nice little jar
icon there to remind you it's a jar file. You click next. I'm just going to take you through
all the steps.
We need to specify a couple things here. First we need to specify what's in the jar file. So
I'm going to open up name surfer, and what I'm going to put inside the jar file – I don't
want to have all of name surfer in the jar file. In terms of if you throw everything in there
including this stuff called dot project and dot class pass, it actually gets a little bit
confused. Some of those things are not germane to what we want to pack up in our jar.
They're just kind of other administrative information.
What we really want to have is everything inside the default package. So I just click on
default package. I can double click on this to make sure that all of my Java files were
checked. That's what I want in my jar. I want basically all of my Java files or the
compiled version of all of my Java files. I make sure that this is clicked. It's clicked by
default. Just make export generated class files and resources. So what it's going to do is
compile those Java files into their corresponding class files. That's what it's going to put
in the jar.
There are other options, like I can export the Java source files if I wanted to. Then I give
someone the actual source code. Most of the time, you don't want to do this if you don't
want peoples sniffing through your source code. You're like, here, take the compiled –
the ACM libraries, we're not going to give you the source code. Just take the ACM
libraries. They're good for you.
So once we have this, we need to specify where we want to save this jar file. So that's
what select export destination. They should've just said, where do you want to save it.
That's the export destination. We can browse around. Basically, I've already created a
folder that has all my name surfer code in it over here. I'm going to save the jar file in that
same folder. So this is just in the same folder for my project called name surfer that has
all of my class files in it. You can put it wherever you want, just don't forget. That's kind
of the key.
I’m going to save it here. You don't need to worry about the options down here. They're
just fine in the defaults that they're at. You click next. Then you come to the screen that
seems like, what's going on. Export files with compile warnings. Yeah, we just want to
export everything. So we just click next.
This is the most interesting part of the whole thing. What we want to do when we actually
create this jar file, and this is something we only need to do when we have other jar files
like the ACM libraries, we need to generate a manifest file. Basically, all a manifest file
is, it's a complicated name. It sort of sounds formal. It sounds like they're on a boat, and
they're like, oh, where's the passenger manifest? Really, all a manifest is – I'll show you
the manifest file. It's two lines long, and then you add one line to it. It's basically just a
little bit of administrative information that's kept around with your jar file so it knows
what kind of stuff you're using with this jar file. That's all it is.
So what we want to do is generate the manifest file. Make sure you save the manifest in
the workspace is checked, which it should be. Then you need to specify where you want
to save the manifest file. The place I want to save it is basically in the same folder for my
name surfer project in the name manifest. You could browse around if you wanted to, but
usually the name you give it is the name of the folder that all your project stuff's in, and
then the name manifest, which is going to be the actual name of the file. Any questions
about that? Manifest file?
The other thing you need to do when you're specifying a jar is a jar's just a bunch of
classes. It needs to know in some sense if someone ends up running this jar – you'll see
that in just a second. You can run a jar – where should it start? Which class should I call
its main method. That's what you specify here. Select the class of the application entry
point. It's kind of a very formal way of saying, where should I start running? So the place
I want to start running, it lists to you all the classes that have a main method. Those are
all the ones that can start running. Name surfer is the only one.
So I click okay. So it says the main class is name surfer. Now there's no more next
buttons. Now all I can do is click finish, and I just created a jar file. You're like, oh,
[inaudible] double click. Double click. We're not there yet.
There's two things that you'll notice if you look over here in the package explorer. You'll
notice now we have something called a manifest file because that's where I saved it. I
also have name surfer dot jar, the jar file I just created. They were both put in the same
folder with my other files. That's were I wanted to save them so they happened to show
up here in the package explorer. Here's the funky thing. Even though we created this
manifest, and we created this jar, they don't have quite the right information that we want.
So what we do is we double click on the manifest file to open it up. Here's the whole
manifest file.
It's got a version, which is 1.0, and it's got the main class, which is name surfer. Why
does it know the main class is name surfer? Because I told it. That's the application entry
point. Just for letting me know that I told it, that's where the application starts.
There's one other thing I need. What I need to do is say, you know what, that's a good
time, but you also need to use the ACM libraries. It says, you didn't tell me about the
ACM libraries. You say, well, now I'm going to add the coveted third line that was talked
about in the manifest file. So I'm actually going to modify the manifest file and add
something called a class path.
All a class path is, it actually looks just like this, C-P. Class path just tells basically the
application what other stuff were you using. Are there other jar files that you're using? So
what you specify here is the name of any jar files that you're going to be using as part of
your program, separated by spaces.
So I'm going to use ACM dot jar. Here's ACM dot jar over here. I'm going to use the
ACM libraries, and those are all in some jar file. I'm also going to use the jar file I just
created, name surfer dot jar. If I had three or more jar files, I'd list them all on the same
line. So if you go and write some application some day where you're like, hey, I got this
jar file for my friend. Here's this jar file I downloaded from the web, which I wouldn't
encourage you to do, and there's this other job file from somewhere else. You just list
them all here with space in between.
Then we save the file. That's probably the most difficult thing that people forget. So you
save the file. You save the manifest file. What do you do after you do all this? Create a
jar all over again. Why? Just trust me.
Here's how it's going to work. I'm going to do it a little bit different this time. Rather than
going to the file menu and picking export, I'm going to take the advanced course. I'm
going to right click on the project name and click export. It brings up exactly the same
window. I'm going to export a jar file. Come over here. What do I want to export? Oh,
yeah. It's all this [inaudible] again. What I want to export is not all this stuff. I just want
to export everything in my default package. Where do I want to save it? I want to save it
in the same place I had before. You might say, but aren't you going to replace the one that
already exists? Yeah, I need to replace the one that already exists because I updated my
manifest.
I need to say it's not just about you anymore. Now it also involved ACM jar. You can
replace the old one. So I'm going to put it in the places before. Then I click next. Here's
the thing about export warnings, export affairs. I don't care. I'm just going to export. Here
is the only place where things are different. The second time I go through this whole
thing, I don't want to generate another manifest file. I generated a manifest file the first
time, and then I modified it. What I want to do is use that modified manifest file. So I say
use existing manifest from workspace, which is again, just a formal way of saying use the
manifest file that's already there.
It asks me, where is the manifest file? Strangely enough, if you look, this is exactly the
same text as here. No coincidence. You just saved it. That's the one you want to use. It's
going to be the same name. Now notice which class of the entry point is grayed out. It's
grayed out because I told it before, your entry point is name surfer. That's in the manifest
file. If that's already in a manifest file, I'm using it, it doesn't need to know it again. So it
doesn't even let me specify it again. Just say that's the difference. Then I click finish.
They give me one last one. Are you sure you want to override that last jar file? He was
your friend. I say yes. We didn't know each other that well. Now I've created this jar file.
What do I do now? Well, I kind of come over here, and I say, here's the jar file I just
made. Now one thing I can do with the jar file is I can double click it. If I double click on
the jar file, it just starts kicking off the name surfer application. So I don't need Eclipse
anymore to go and run and have a little running dude. I have a little application.
I'm like, oh, yeah. How popular was that? Bob's kind of fallen off in the meantime. There
are some other interesting ones. I was looking at these the other night. Verna. After the
'60s, done deal. Thanks for playing. So name your children Verna. Make a comeback.
So name surfer's just kind of running here. It's fun. It's just a little stand-alone application.
If you wanted to pack this up and send it to a friend of yours, you wouldn't just send
name surfer dot jar. What you would do is say, hey, you know what I want to do? I want
to create – I'll just do it in here – some new folder. So I'm going to create some new
folder, and I'll call this my program or whatever you want to call it. I'm just not going to
call it name surfer again because I already have a folder called name surfer. My program.
What I'm going to put in my program, that folder, is the jar of my program. I'm also going
to put in the jar of the ACM library because I also need that jar. That's separate.
I also need in here any data files like names dot data. That's all the data that gets read
when the program starts. It's not like magically that's just going to be there now. It's still
going to go and try to find that file. So I still need to put all that stuff here. Now this
folder is something I can zip up and send it to a friend of mind. When my friend gets it,
they would be like, oh, name surfer dot jar. Then they get going.
So now you can package up any program that you've written in this class. Remember to
put in main. You got to go through this two-part [inaudible] the jar, export it, process,
modify the manifest, create another jar, put it out there again. But you're good to go. Any
questions about that? Now you can package up and share with friends.
What's even cooler than sharing with friends that you can email stuff to is sharing with
friends on the web. You just have millions of friends on the web. Most of them you just
don't know about, but they're probably on in the late hours of the night, looking at your
web pages and things. You can actually take any files that you create here, like jar files,
and make them available in a web browser.
There's one other thing I should mention, and this is kind of a little thing. Before you go
and create all this stuff and send it off to your mom and dad and be like, mom, dad,
breakout. Go play. It's a good time. In order for them to run your jar files, they need to
have the Java run time environment installed. Remember on the second week of class
where we said go to the CS106 web site. You need to download a clip. There's this thing
called the JRE you also need to download.
If you have a make, the JRE in most cases is already installed. If you have Windows, it's
not installed. They need to go down, and you can send them to the CS106 page and say
download the JRE. Here's a copy of handout No. 5. Go ahead and install it, and then they
can run your programs. Your program can't run if the computer doesn't have Java, right?
It's a bunch of stuff that's going to execute Java byte code, and your computer's like,
what's Java byte code? I don't know what to do with it, so it won't run. They need the
Java Runtime Environment.
Now assuming someone has the JRE, they can go to a web page. You might put some
page on the web that allows you to load your applet. Your applet is just a webified
version of your program. So here look. It's running inside a web browser. This isn't the
actual application. This is my web browser. I could go to some search engine from here.
I'm sitting in the web browser. I'm not just running a regular application on my desktop.
This guy's actually running in my web browser.
Here's how I make it happen. I create a web page. If you don't know about HTML and
creating web pages, unfortunately I can't explain that to you in five minutes. What I can
show you is basically what this file's going to look like. So if you know a little bit of
HTML or you just want to essentially copy and paste this idea, this will work for you. So
all you do is say – the entire page that allows your applet to run. You say this page is
HTML. There's these little things called tags.
The name of that page is name surfer. I want to create a little table. I'm going to create a
little border around my application. What's my application? My whole application is right
here. I have an applet. What's the name of the archive, which is a Java archive that
contains my applet? It's name surfer dot jar. Code is what's the entry point. This guy no
long has a manifest file available to us. What's my entry point? Name surfer dot class.
That's where you start running. So it says I'm going to go name surfer dot class, find its
name. That's where I start running.
The space I'm going to give you to run on the screen is 700 by 500. That little snippet of
code is what goes on whatever web server this is serving on. It looks for those jar files,
slaps them into the page and then they're good to go to run more java program inside their
web browser. How many people know HTML? You folks. There's some number of folks
that this might be a reasonable thing to do. If not, you just don't need to worry about it.
It's not a big deal.
The one other thing you should know if you create a web page is that when something's
running in the web page, it doesn't have access to the rest of the file system. What that
means is if I actually happen to be over here – notice I have index dot HTML. I have
name surfer dot jar, and I have ACM dot jar. What happens in my names dash data file?
It doesn't exist. Why doesn't it exist? Because I couldn't read it anyway. Once I'm running
on the web browser, for security reasons, it doesn't let you go in and pull stuff out of your
file system.
If it did, people could do really bad things to your computer. So what you need to do if
you want to find that data, you let us run name surfer on the web. What did you do?
Here's the dirty little secret. I actually created a giant array that had all the data in it and
made it part of the program. So sometimes you can do stuff like that if you don't actually
want to read from a file. The other thing you can do is you can take those files and
include them in the jar file because the jar file cannot only have compiled [inaudible]. It
can also have data files. That's another way of doing it if you want to do it that way.
We don't have time to go into all the details. It's kind of the same process. When you're
exporting stuff to the jar file, you include some data files in there. So what's creating the
executable. Now that we know all this funky stuff about executables put on a web page if
I want. I'm feeling happy. I'm good to go. It's time to come back to our friend, standard
Java.
Standard Java's what allowed us to think about doing this stuff because we learned about
main. I want to show you a couple examples of programs that actually don't use the ACM
libraries at all to show you why we use the ACM libraries. One of the things you might
be wondering is why weren't we just doing the standard Java thing the whole time? Part
of the reason is things are just so much easier and cooler when you have the ACM
libraries.
So if you go back over to Eclipse, we're kind of done with name surfer and all this
manifest stuff. Here's a program that's written in standard Java that writes out hello world
on the screen. This is something you kind of did in the first class by saying public class
hello world extends console program in printlin. Hello world out to the screen, and you
would've gotten it in the console.
So what's different here? What's different is we have public class hello world, and it
doesn't extend anything. It doesn't extend program. It doesn't extend console program.
There are no imports for the ACM libraries. We're not using any of the ACM stuff. So we
don't have a console program. We don't have a nice console that we write stuff out to that
displays in a nice little window. What we do have is something called the system output
console. If we want to put stuff on that, it looks real similar to what you had before. We
used printlin, which is why we made the method that you used called printlin to match
this. But we need to say system dot out dot prinlin and then the text we want to print out.
Again, here I have a main method. My main method can have whatever I want in it. This
is just where execution starts. So if I compile this and run it – let me show you why. This
world is not all that cool. Here's hello world. It just ran. You're like, I don't see anything.
You don't get a cool window that comes up and is like, hello world. You have the system
console. The system console if you happen to be using a development environment like
Eclipse or something else, it's basically just a window in that development environment
that shows messages that you print out. If you happen to be in the bad old days that I
think I erased over here where you have command line text where you actually type stuff
in, the console would just be that same window where the text would appear where you
type stuff.
If you don't get it in a separate window, it's not that cool. A lot of times, this window's
close anyway. If you wanted to kick it up a notch, why use the console? Why not do
something graphical. So here's graphical hello world. What we want to do is create a
window that is going to have some title associated with it. We're going to put the text
hello world in that window. What do we need to do? Again, execution starts at main. We
need to create something called a J frame, which you never had to worry about before.
What's a J frame? It's actually a frame that's going to hold the window.
We're going to start running our application. It's going to create a little window for us that
we're going to display stuff in. What are we going to put in that window? We're going to
put a label. J labels you've seen before. This is just like you've seen. We're going to create
a J label that's called hello world, and we want this label to be center justified as opposed
to left justified or right justified.
So I need to say J label dot center to center justify it. If I don't give it a justification, it'll
by default by left justified and look kind of ugly because we want it center. Then I add
this label to my frame. So similar to the idea of having a canvas and adding stuff to the
canvas, it's exactly analogous. We want to make it just as easy. So when you saw
standard Java, all the same concepts would apply. Here, we're just adding the J label,
which as you know now, is a J component in the big Java hierarchy. J components can be
added to J frames.
So we have a J label that gets added to a J frame. I set the size for that J frame, which is
500 by 300. That tells me how big the window's going to be when it starts. Then there's
this other stuff that I need to do. You would think why do I need to do that? It doesn't
make any sense that I would not otherwise want to have it this way. Here's what I need to
do.
If someone clicks close on the window, I need to say, hey, if someone clicked that, then
you need to close yourself. Otherwise, the window goes away and the application keeps
running. It seems odd, but we need to have that there for this application to stop running.
Then we say window, I know I created you and everything. You need to make yourself
visible. Otherwise, no one will be able to see you.
You're like, why would I create a window that I wasn't going to make visible? Yeah,
that's why we use the ACM libraries. So we need to make sure that this guy's visibility's
true. If we run this, here's graphical hello. So after all this stuff, here's graphical hello.
Yeah, would you want all that explained to you so you can get hello world? You're like,
I'm writing a social network. I don't need to worry about hello world in the middle of my
screen. That's because you have the ACM libraries. So you're like, okay, let's kick it up
even one more notch. You're like, [inaudible] all this mouse stuff and interaction, right?
That should be something I get some benefit from having standard Java. So we'll have an
interactive version of hello.
Center the interactive version of hello. Now some of this stuff should begin to get a little
more repetitive in the sense that you have your main. You have your J frame. The frame
is called interactive hello. That's the title of that window. What we're going to add to this
J frame is a new class that we're going to create called a moving label. I'll show you what
a moving label down in just a second, but we need to set the size of the window, set
default close operation exit on close. Set visibility to true.
Basically all this does is create this window of a particular size. It's going to add this
thing called a moving label to it. Moving label's just another class I create. What's a
moving label? A moving label is a J component. It needs to be a J component because I'm
going to add it to a frame. To display something on a frame, I can only display
components on the frame. This is going to extend component.
It's going to implement our friend, mouse listener. It's going to listen for the mouse.
You're like, oh, I remember mouse listener. That where the mouse got clicked and
dragged. That stuff's exactly the same. So I have my constructor. What my constructor
has, it has some starting text for this label at its starting X and Y location. That should
look kind of familiar to you. Basically I just store off the text. I store it at X and Y. This
guy wants to listen for mouse events.
So it says add a mouse listener, and it needs to say if you get some mouse event, send
them to this. So this is a little bit different than you've written in your programs before
where you just said add mouse listener. You just had an open [inaudible]. That's because
we kind of took care of the rest of this stuff for you.
Here's where things get a little bit funky. The difference between this and thinking about
having some sort of label that you just display on a canvas, some text that just sits there,
is that this guy now has to worry about what's known as painting himself. That means it
needs to draw itself on the screen.
Well, when I had labels before, they just knew how to draw themselves. Yeah, that's
because we gave you a label that was a little bit smarter and knew that it was a label that
should draw itself. This guy needs to be told to draw himself. There's a method called
paint component that gets called whenever this guys gets displayed on the screen. There's
some other thread that's going to call it for you automatically. Here's the graphics context
in which your going to call yourself.
Within that graphics context, I'm going to draw some string. The actual method name and
everything is not important here. It just shows you that there is extra stuff you need to
worry about, which is why we didn't want to do all this stuff to begin with. This stuff
you've seen before. What happens if a mouse is clicked? I get the new XY location. I
repaint. What does repaint mean? It means redraw yourself. I'm going to redraw myself at
this new XY location. When I call repaint, someone comes along and says, hey, to repaint
this area, I'm going to call your paint component method so you can repaint yourself.
Whoa, this is really weird. I'm over here. I get a mouse click, and I know that I want to
redraw myself. But rather than telling myself directly to redraw myself, I go and tell the
system, I need to get repainted. Then the system says, that's the start of Jabba the Hutt
kind of sitting there fat and happy. Some day, if you actually – we won't get into it.
You go and say I need to repaint myself. It says, okay, you need to repaint yourself. Well,
when I'm ready for you to repaint yourself, I'll call your paint component method. Until
then, you don't repaint yourself. So it delays other stuff in the system to worry about, and
then oh, yeah. There was you. You asked to get repainted. I'll call your paint component.
You say, okay, well, now I'm going to draw myself at the new XY location.
So it kind of convoluted the whole notion of you're doing something here, and you're
asking someone else to do something for you. Then they're going to call you back to do
what you originally intended to do. Now it makes a little bit more sense after we talked
about threads and after you've seen all this stuff. Third day of class, not so hot.
So if we run this, this is called interactive below. Basically, what it does is it just brings
up our particular message, CS106A rocks in the middle of the screen. Now every time I
click the mouse button because this is the mouse click event over here. Every time I click
the mouse button, the XY location of the mouse becomes the new base point for the text
that gets drawn. So it just moves around the screen.
Any questions about that? So this is standard Java. You've seen all the concepts using the
ACM libraries. The notion of adding things, having mouse listeners. As a matter of fact,
the whole mouse listeners concept, we just took the standard Java ideas and used them
sort of in conjunction with the ACM libraries. But there's a lot of things in the ACM
libraries that just made it so much easier to, for example, to graphics contest entries or to
write a social network.
So you're welcome to continue to use the ACM libraries after this class. Some people
were wondering why we use these libraries, and this is the reason why. There's a whole
lot of stuff you'd have to worry about otherwise. Questions?
Student: [Inaudible].
Instructor (Mehran Sahami): You'd be using your favorite word processor, like
notepad. There's actually some places which I won't name, but it's actually reasonable
that some schools in your first programming class, what you do is they say, you need to
have notepad, or you need to have some text editor. Then we're going to do command
line stuff. You're going to type in name surfer, names dash data dot text to run your
program. Then everything is going to be [inaudible].
So one thing I want to leave you with now, in our final few moments together, is sort of a
notion – we're still going to meet next week, talk about life after this class, but if you
want to go on in terms of learning more about Java, especially standard Java, we sort of
just started things off by giving you this book, which talks all about the ACM libraries.
This, I think, is a great book to actually learn everything with and use the ACM libraries.
But if you want to go on, what are some other resources you can use?
Student: [Inaudible].
Instructor (Mehran Sahami): It's not pretty. If you go to the Java section of any
bookstore, just be prepared to stay a while. One book that I would recommend, not that I
get any kickbacks from these folks, called Learning Java. It's actually a pretty good time.
Some of the examples you actually saw here were based on this book. It's a little big.
That's why we don't use it as a textbook in this class. Will we break the 1,000-page mark.
It's so close. No, 950. Sorry, close.
There are some other books. Actually, the original specification of the Java programming
language. This is an older version of the book. This was when I was a wee tyke in the
days of yore and got the old version. I forget what version they're up to now. This was
second edition. I think now they're up to three or four. Something like that. The books are
a little bit bigger, but for a book that specifies the language, Java, it's actually very wellwritten
as a reference. So I'd recommend this as well.
If you're into oh, I want it all, Big Java. It's big. I think it might actually cross the 1,000
page – oh, yeah. It's like 1,200. If you really want to get hardcore and you're all about
web-based Java, Java Server Programming. Everything you would want and a lot of
things you don't want to know. Everything you want to know and more. That's just a
small set.
So these are just a few books I'd recommend if you want to go on beyond this class. But
you can go into any bookstore, and you get inundated with that kind of stuff. Now you
have a context for putting all the pieces together because you've seen all the things that
you actually need to know to be able to work with the huge set of tools that Java actually
has. Any questions about any of this stuff?
You're good to go? All right. I'll let you go a couple minutes early because most of the
time, I let you go a couple minutes late. Have a good weekend.
[End of Audio]
Duration: 45 minutes

Programming Methodology-Lecture25 Instructor (Mehran Sahami)

Programming Methodology-Lecture25
Instructor (Mehran Sahami): So welcome back to another fun filled, exciting day of
cs106a. A couple quick announcements before we start. First announcement, there is two
handouts. One of those handouts, which we'll spend some time talking about today, is
your last assignment for the class, which is assignment No. 7. It's worth noting, we sort of
talked about it the very first day of class when we talked about late days. The very first
handout says no late days can be used on assignment No. 7. So that’s important to
remember. No late days can be used for assignment No. 7 because it's due the last day of
the class.
If you're looking at the syllabus, you might say, I didn't think we had class on Friday, the
last day of class. That would still be correct. We don't actually have class, so you only
need to do electronic submission for turning in your program, but it's still due at 3:15 on
that Friday. We just don't actually have lecture on that Friday. We'll talk about the details
of that assignment as we go along.
The other handout that you got is the example of the code that you say last time for the
Fly Tunes music store. So you should have all that code, which shows and example of a
big data structure. In fact, the data structure for that program is perhaps more complicated
than the data structure you're going to need to use for the face pamphlet assignment, No.
7.
So as you know, assignment No. 6 review today. I have a feeling a lot of people may
have been taking late days on it because it was, for example, the last assignment to
actually be able to use late days on. So we'll just do a quick, painful as to how much time
it actually took you. Hopefully it wasn't too painful, but we'll see.
Just wondering, how many people are taking a late day? Wow. So for the six of you who
actually are turning in the assignment on time, anyone in the zero to two hour category? I
would be frightened if you were. I don't think it's actually possible to do in two hours.
Maybe, if you just sat there and wrote all the code. Two to four? Oh, I actually have a
couple for two to four. Wow.
Four to six? Good to see. I think all the [inaudible] is just going to be smaller. Six to
eight? That's a pretty healthy contingent. Eight to ten? Also good-sized contingent. Ten to
12? Couple of folks. 12 to 14? 14 to 16? 16 to 18? 18 plus? Anyone in 18 plus and still
hasn't turned it in, like you're just going for late days. All right. That's good.
So that's good to see. It's a good time. World is still normal, though the normal curve just
happens to be a little smaller because there's more people taking late days, but it's a good
time. If you haven't done it yet, two things. One is that this should give you an idea about
how much time it'll take, perhaps. Two is you don't want to push it. Even if you have late
days, don't push it off too late because you really want to give yourself time to do
assignment No. 7.
So any questions about anything we've done so far before we kind of delve into today's
great topic? All right. So I want to spend the beginning of class actually talking a bit
about your next assignment. So if you're still kind of in the mindset of thinking about
name surfer, and you're like, oh, I'm just so in the mindset of assignment No. 6, take that
little part of your head that's got assignment No. 6. Pop it off the stack. That's my whole
head. Yeah, that might be painful. Pop it off the stack for a second, and we're going to
think about our friend, the face pamphlet.
So just a quick show of hands, how many people are part of a social network or do some
social networking online. That's good to see. So I won't need to spend too much time
telling you about what a social network is, but I'll spend a little bit of time in case you're
not familiar with social networks.
Basically, a social network is just a way of keeping track of some set of people, or
profiles of people, and relationships among people. At the simplest level, that's all it is.
So what you can think about is you have some profile for a person. In some sense, you
can think of the notion of a profile and a person interchangeably most of the time. But as
most of you know, if you've ever read the New Yorker and seen that cartoon that no one
on the internet knows you’re a dog.
So you don't necessarily have to be a person to have a profile. So when we think about a
social network in the abstract sense, we always just talk in terms of profile. But if want to
think about it concretely, you can just think of a profile as being synonymous with a
person, but it need not be, so we generally refer to a profile.
So what a profile has associated with it, it has some attributes or some things that we
keep track of for that profile. For example, it has a name. In the case of your assignment,
it's also going to have some status that we care about, keeping track of the person. It
might have some other things, like the reason why it might be called face pamphlet is
because say you want to keep track of people's faces. You want to actually see what they
look like.
So you might actually have some image in there. Then I mentioned you want to keep
track of some list of friends. So there's some notion of a list of friends that is also
associated with a profile. Real social networks also have other things associated with
them, and the assignment talks about extensions you can do, but we're not going to get
into extensions right now. But these are things we want to think about.
For a person's profile, there's a name. One of the things based on some of the ideas we
talked about in the last lecture, is you can think of name as a unique identifier. What that
means is that you will never have two profiles in your social network that have the same
name. So once you have a name in your profile, in your social network, that name is
yours. That profile will be associated with that name until, at some point we decide,
maybe we want to delete the profile to get rid of it. But the whole time the profile's
actually live, it will have that unique identifier, which is the name of that profile.
So if you ever try to create another profile with the same name, the application will tell
you that you can't. I'll show you some examples of that in a bit. But the name is a unique
identifier, and this thing's just some string that we keep track of the name. So it can be
like your real name or whatever name you want to have, like Code Dog. That can be your
profile name. That's cool, too.
Status is just what you're doing right now. You can think of this as some string which is
what you happen to be up to at the time. Like Maron is teaching. I don't know. Ben is
contemplating life. It's just some particular string of the thing you happen to be doing.
You might want to change this a fair bit.
This image thing is just an image. In our world, that means it's a G image. That means it's
some picture. Originally, when you create a profile, you may not have a status, and you
may not have an image. You may want to add one. You may want to change one as life
goes on. We should be able to allow for that. Then you have a list of friends. When you're
born into the world, your list of friends is empty. Over time, you can gradually build up
friends.
That's the other part of the social network to consider, besides the fact that we have
profiles is that we also have some notion of friendship. The way you can think of
friendship is basically some profile or some person just has a list of friends. So an easy
way to think of a list of friends is a list of names of friends because names are unique
identifiers. So if we keep track of a list of names, we have a list of the unique identifiers
that are our friends.
That's an easy way to be able to look them up, for example. The idea behind friendship
that's key to us – this is not necessarily true in the real world, sadly enough, but for our
intents and purposes, as far as the assignment's concerned, friendship is reciprocal. That
means the if your friendship is reciprocal. Not all the time. That's the way it is.
What the really means is if I have two people, like I have Bob over here and I have Alice
over here, you can think of those as profiles. If they are friends, we draw a line between
their names in our little social network. This is not actually how we keep track of them in
the application that you'll see, but this is often how social networks are drawn.
We put in sort of a circle for each profile in the social network. Here's Don over here, and
here's Chelsea. Notice there's the ABCD phenomenon. Always a good time. So when we
put what we refer to as a link between two people, that means they're friends. Friends are
reciprocal. So if Bob is a friend of Alice, that means that Alice is a friend of Bob. That's
just the way life is all the time in face pamphlet.
It's just a happier place. Everyone's like, oh, I'll be your friend. Okay. Then you're my
friend, too. So that's the way you want to think about it. So if Bob ever adds Alice as a
friend, that automatically means Alice becomes Bob's friend. There's never a
directionality of friendship. Bob clicks, oh, Alice, be my friend. She's like, no. Talk to the
hand. That happens in real life all the time, but not here because it's just a happier place
to be in.
So think of friendships as reciprocal. Again, we don't necessarily have to have anything
explicit to model this link. All we need to do is think about just having a list of names. So
Bob might have Alice in his list of names of friends that he's keeping track of. That's how
I would keep track of the link.
What that also means is that reciprocally, Alice should have Bob in her list of friends
because the links are always reciprocal. When we actually draw this out, if we want to
draw the stylized picture, we could say Alice is friends with Chelsea and Don, and Don
and Chelsea are also friends over here. This is where the name network comes from.
When we draw this thing out, eventually you have millions and millions on these things
in there, all over the place. Everyone's holding hands and singing Kum Ba Ya. You have
a social effect because you have friendship, and what you actually end up drawing is
something referred to as a network.
If you're really the mathematical type, this is really a graph. In this case, it's an undirected
graph. If that kind of talk makes you hot and bothered, like, oh, a graph, yeah. Take
CS103B, which I'll be teaching next quarter. Graphs are just the coolest, most wonderful
thing. But that's a thought that's not important right now.
What is important right now is that this is where the name social network actually comes
from. We create this network that keeps track of social relations. So if we have that base
idea of social networks, how do we actually think about writing an application to keep
track of them. So [inaudible] the computer, I'll show you what, at the end of a week and a
half's effort, you will have your own social network application.
So we're going to call it Face Pamphlet because it's not really big enough to be a book.
It's a tiny book, so it's a pamphlet. So when it starts up, you can see there's interactors
galore all over the place. Over on the north side, we got a name. We got some buttons
over on the west side. We got some status, some pictures, some adding friends. What
does this all mean?
We'll actually go through an example and sort of create a little social network. So what
I'm going to do is create a profile for myself. You're like, oh, that's kind of narcissistic.
That's okay. I didn't want to – oh, we're going to create a profile for you right now.
So we add the profile on here. Here's what we get in the display. There's a bunch of
display elements. We have a name up there with some big font, and it's blue. We don't
have an image right now, so we just have a place holder. That's basically just a rectangle
with some text. It says no image. We don't have a current status, but what we've done is
created an initial profile with the name, Maron Sohami, which is a unique identifier in the
system. So right now, our social network has what we refer to as one [inaudible]. There's
one profile in there, and I don't have a list of friends.
You might say, okay, that's not so exciting. Let's actually add some stuff. So once I
actually have this active profile, I can say, let me change the status. Right now, at this
very moment, I happen to be teaching. So when I click change status, it says Maron
Sohami's teaching. Sometimes I could just be, no, I just really want to be doing this.
So I can keep changing the status. That's fine. It just updates here whenever I type it into
this field and click the button or hit the enter key. I can also add pictures. So I can say, for
example, MaronS.jpeg is a picture of Maron. There's a picture that gets loaded. It gets,
unfortunately, scaled to always take up the space for the image, which is a 200 by 200
region space.
It's constants that are given to you in the handout, but for these purposes, it's 200 by 200.
So this is kind of the bouncer version of Maron in the days of yore, when I was clean
shaven. There was actually a time when I shaved. That doesn't happen very often
anymore. If you were ever wondering what I look like without the beard, not that I care.
But that's what it was like.
So we've created a profile. Not a big deal. You could say, hey, next quarter, I'm planning
on taking 106B, and isn't that taught by Julie Zolanski? Yes, in fact, it is. So let's add a
profile for her. So we type in Julie Zolanski in the name field up here and click add. We
now get a new profile for Julie Zolanski. Julie is just a fiend. She codes like a fiend, so
she's coding like a fiend. That's what she's doing.
So you can see down here, not only is all this stuff getting updated as we typed it in, but
down here, there's something we refer to as the application message. The application
message always tells you what was the last thing you did or tried to do. So your status
was updated to coding like a fiend was the last thing you did. Let's give Julie a little
picture over here. JulieZ.jpeg, and there's Julie, also scaled to 200 by 200. So she's no
longer coding like a fiend. She's kind of feeling stretched.
So now we have her picture. We have her profile. That's all good and well. Let's add a
couple more profiles real quickly. So I'll add some of our section leaders. I'll add Sarah
K. I'm just going to abbreviate. Notice these fields over here don't necessarily get reset
when I create – they just have their old values in them. That's not a big deal. You could
add it as an extension if you wanted to, but they just leave their old values.
Sarah K. Sarah, is it okay if I use your picture? All right. Here we go. There she is, and
she's actually scaled reasonably well. So we'll also add Ben. There's Ben. We'll add a
picture for him. If you're wondering where all these pictures are coming from, in the
starter project that you'll get, you'll get a folder of images that contains the images of all
the section leaders from the class as well as Julie and myself.
I'm scaling until the cows come home. If you have your own pictures, you can add them
into the folder called images, and you, too, can display your image at a 200 by 200
resolution. Ben, where are you? Here's Ben.
Well, Ben's feeling kind of anonymous. So I gave you two anonymous-ish images as
well. There was a Stanford logo, which is just a super low-res version of our logo. Then
there's also Stanford Tree. So you can change the picture to one of those if you want to.
Those just come along for the ride.
If you do the web version, actually, the web version only has these two Stanford logo and
Stanford tree images. I didn't put everyone else's image on the web version because for a
little bit of privacy. Was there a question?
Student: [Inaudible].
Instructor (Mehran Sahami): No. If I empty the field, one of the things it says in your
handout is anytime the field is empty, it just gets ignored when I try to do something. So
any field, whether or not it's name or any other field, just ignore it. But I could have
something like the nonexistent picture.jpeg, and I try to change the picture to that, and it
says unable to open image file.
So in your handout, it actually explains how you can detect if an image exists or not. So
you can actually check the case where the image doesn't exist. If it doesn't exist, we just
don't update the image to the new image. Really, all we're keeping track of here is the
name, which gets created with the initial profile because it never changes, an image that
we display, whatever the current status is. If currently there is no current status, and a list
of friends.
So far, we've add a bunch of profiles. What else can we do? Well, there's a lot of things
we can do. Let's look up Maron again. So if I type in a name I can click look up, and if
that profile exists with that name, it brings it up and says you're displaying the profile
name down here. Then we can add some friends. So Sarah is a friend. Add friends. So it
says Sarah K, added as a friend. Ben is also a friend. So I add Ben.
I can try to add someone who doesn't exist in the system. Like I can try to add – who
should I add? Jenny. 867-5309. I add Jenny. Jenny does not exist. As far as I know in my
social network, Jenny's not there. I get this message down there.
Remember, friendships are supposed to be reciprocal, so I have Sarah and Ben as friends.
I never went to directly update profiles, but if I now look up Ben's profile – Ben N – Ben
has me as a friend. So when I added Ben as my friend, at the same time, I got added to
Ben's friend list. That's something that you're going to need to manage in the application.
Friendship should always be reciprocal. So when you add a friend to a particular profile,
you also make sure to go to that friend and add the current profile to that friend.
Now, another thing we can do, besides just creating profiles and done friends, we can
look up profiles, like when we had Maron's profile over here. We can look up a profile. If
I try to look up a profile that doesn't exist like Maron Sohami Bob doesn't exist. It clears
what profile's in there. It says a profile with the name Maron Sohami Bob does not exist.
When there is no profile in the current application – all this stuff, by the way, is explained
in the handout. This is just to kind of show you to get a feel for how it works. You don't
need to jot this all down in notes. When there is no current profile displayed, I cannot
change any of the things in the profile. It says please select a profile to change status
because I can't change the status of a non-existent profile or change its picture or add
friend to a non-existent profile. But the way I get a new profile displayed in here is I
either add a new profile or I look up an existing profile. Then there's a profile there that I
can change to whatever I want to.
Now, let's say I've looked up this profile. I say, that's great, and Ben decides he's had
enough. Get me out of your social network. So I say, oh, I'm sorry to hear that, Ben.
Here's Ben. I'm going to delete Ben from my social network. Even though I'm displaying
my own profile. I click Ben up here, and I delete him. Whatever profile was there, it
doesn't matter if it was Ben's or whoever else, it cleared, and it says profile of Ben N
deleted.
Now what happens when a profile gets deleted? It gets cleared out of the social network
so it's no longer there. If I try to look it up, it says a profile with the name Ben N does not
exist because, sorry Ben, you've been nuked. You're out of the social network. But Ben
was friends with people. He was friends with me, and now it's a sad day. So I go to look
up Maron. I should've just used the first name.
Ben has been removed from my list of friends. Sad day, but that's life in the city. You
can't be friends with non-existent people. So when someone gets removed from the
network, you go through everyone else in the network and say, did they have them as a
friend. If they did, they get popped out. I guess you're just not a friend anymore. That's
basically the whole social network. That's the whole idea.
So question?
Student: [Inaudible]
Instructor (Mehran Sahami): Okay. Names are not case sensitive, so I can have a
Maron Sohami, and then I can have a screaming Maron Sohami, and he's just different.
He's angry. I don't know if we have an angry image in here. I don't know if any of the
section leaders were actually looking angry, so we'll just make him the Stanford logo.
This is different than Maron Sohami, lower case. So you don't need to worry about it like
you did in the last assignment. You were worrying about case sensitivity. Here, you don't
need to worry about making things insensitive. You can just case – everything is case
sensitive, so you don't need to worry about making strings equal to each other, case
sensitive and stuff like that.
So any questions about this general idea? You got to think about it, right? Any more
questions?
If you kind of think about it, this is the basics of the social network. You have all the
people. You can have as many people as you want from the social network. You can
maintain friendships. You have attributes of the people, which in this case, just happens
to be their name, their image and their status and their list of friends, but you could
imagine – you could extend this in a whole variety of ways.
Really, what this is about is data management. There's a display component. In part of the
assignment, there's a bunch of milestones that are laid out. The actual only milestone that
deals with this display is the very last milestone, which involves a bit of work to get all
this stuff displayed at the right locations. There's a bunch of constants, which is all the
places, you put things at the right locations.
But it's really about managing data. How do you manage profiles, managing the
friendship relationships, being able to remove stuff, add stuff, which is what most
applications in the world are really about. So you're going to get a chance to really
exercise your data structure skills and your larger-scale application skills in this program.
So any questions about this program?
There's also a web demo of it, so if you want to go to the web and play around with it,
you can play around with it. Again, in the web version, there's only these two images, the
Stanford logo and the Stanford tree.
Student: [Inaudible].
Instructor (Mehran Sahami): No. That's the other thing. It's in big font somewhere, like
on page 15 in the assignment. So don't be scared by the fact that the assignment handout
is 28 pages like some people are looking at. Oh, my God, this is so big. The code is much
shorter than the handout, first of all. Second of all, one of the things – all the details are in
there, but one of the important things that comes up in the handout is you don't need to
worry about scaling.
So if I shrink or increase, yeah. No worries about size or resizing. I figured you got
enough practice with that with name surfer. Either you already got practice with it or
you're getting practice with it with name surfer. So we don't need to make you do it again.
So you don't need to worry about component listener and resizing and everything. You
can just lay this stuff out with t respect to the constants that are given to you, and you're
okay. But resizing, you don't need to worry about it.
It can be a cool extension if you want to add it as an extension. That's perfectly fine.
There's a bunch of extension ideas that are listed at the end of the assignment. As you can
kind of imagine, if most of you are on a social network, you probably already have
thousands of ideas for extensions, if you want to add them, but you're not required to add
anything in particular.
So any other questions about this? All right. So with that said, I just want to give you one
last little – before we moved into the advanced topic for today, one last little side note
about social networks. Has anyone ever heard of the phenomenon, six degrees of
separation? A few folks. There was a movie years ago about this phenomenon, and the
movie actually had nothing to do with the phenomenon. It just happened to have the
name, Six Degrees of Separation.
But it's basically this idea that everyone in the world is linked, potentially, to everyone
else by at most, six hops in this graph, which is kind of weird to think about. I won't go
into all the details an mathematics and stuff, but there's some very interesting stuff behind
it. But the biggest idea is that these social networks, you can sort of think of little hops
between people.
You can say Bob is one degree separated from Chelsea or two degrees, depending on
how you count, from Chelsea because you can get to Chelsea by going Bob, Alice
Chelsea or Bob, Don, Chelsea, whatever the case may be. But just in case you're
wondering where the six degree of separation idea came from, Stanley Milgram – anyone
ever hear of Milgram's experiments like obedience to authority, if you're a psychology
kind of person? Same Milgram.
We won't get into that. That's just a whole bunch of other interesting psychological
phenomenon that are discussed on the other side of the quad. But what he did was said –
this was back in the '60s, I think. '67, actually. He sent a whole bunch of packages to
various people in Nebraska. So let's just say that's Nebraska.
He sent a whole bunch of – yeah, my notion of geography – to random people in
Nebraska and said, these packages need to get to someone who's over here in Boston.
Yeah, I have no idea. It's Boston. That's Massachusetts, and here's Boston. These
packages need to get over here, but he didn't give them an address. He just gave them a
name of random people in Boston the packages need to get to.
The only instructions he gave were to say you can't try to figure out who this person is
and send them the package directly. What you need to do is send this package to someone
that you know who you think will be more likely to know this person than you are. Those
were the only instructions. Then when the packages was trackable, how many times it got
mailed.
He measured how many times the package had to be mailed to various people before it
actually got to its destination. What he found was there was an average of about five to
six for the packages to get from a random person in Nebraska to a random person in
Boston. That's where the six degrees idea comes from, but that's – now when people talk
about social networks, they talk about things like degrees of separation and what we refer
to as small world phenomenon. If everyone's linked by only six degrees of separation,
then it really is a small world after all. We can all hold hands and be mechanical animals.
If you've ever been to Disneyland, that makes sense. If you've never been to Disneyland,
you don't need to go on the small world ride now.
So time for something completely different. Are there any questions about social
networks before we delve into our next great topic? If you're really interested, you're like,
Maron, tell me more, take CS103B. It's a good time.
The advanced topic that you're going to get – and I hesitate a little bit to tell you this, but
this is something that you don't need to know for the final exam. As a matter of fact, you
don't need to know it for assignment No. 7. It's just something that's so cool with the way
programs are actually done today, it's something you should actually know. That's a
notion called concurrency.
It's also important for you to know if you want to understand, for example, in next class,
for example, I'll show you how to take the programs that you've written in this class and
turn them into applets or turn them into executables so you can share them with your
friends. You'll need to understand this idea.

Mehran Sahami Handout #41A CS 106A November 28, 2007

Mehran Sahami Handout #41A
CS 106A November 28, 2007
Solution to Section #8
Parts of this handout by Brandon Burr and Patrick Young
/*
* FlightPlanner.java
* ------------------
* Reads in a file of cities and their corresponding flights,
* and allows the user to plan a flight route.
*/
import acm.program.*;
import acm.util.*;
import java.io.*;
import java.util.*;
public class FlightPlanner extends ConsoleProgram {
/** Runs the program. */
public void run() {
println("Welcome to Flight Planner!");
readFlightData("flights.txt");
println("Here's a list of all the cities in our database:");
printCityList(cities);
println("Let's plan a round-trip route!");
String startCity = readLine("Enter the starting city: ");
ArrayList<String> route = new ArrayList<String>();
route.add(startCity);
String currentCity = startCity;
while (true) {
String nextCity = getNextCity(currentCity);
route.add(nextCity);
if (nextCity.equals(startCity)) break;
currentCity = nextCity;
}
printRoute(route);
}
/** Ask user for the name of the next city in the route */
private String getNextCity(String city) {
ArrayList<String> destinations = getDestinations(city);
String nextCity = null;
while (true) {
println("From " + city + " you can fly directly to:");
printCityList(destinations);
String prompt = "Where do you want to go from " + city + "? ";
nextCity = readLine(prompt);
if (destinations.contains(nextCity)) break;
println("You can't get to that city by a direct flight.");
}
return nextCity;
}
– 2 –
/**
* Given a starting city, looks up the destinations from that
* city in the HashMap of flights, and return an array list of
* the destinations that are available.
*/
private ArrayList<String> getDestinations(String fromCity) {
return flights.get(fromCity);
}
/**
* Prints a list of cities from the array list. Each city name is
* indented by a space.
*/
private void printCityList(ArrayList<String> cityList) {
for(int i = 0; i < cityList.size(); i++) {
String city = cityList.get(i);
println(" " + city);
}
}
/**
* Given a list of city names, prints out the flight
* route, with a " -> " between each pair of cities
*/
private void printRoute(ArrayList<String> route) {
println("The route you've chosen is: ");
for (int i = 0; i < route.size(); i++) {
if (i > 0) print(" -> ");
print(route.get(i));
}
println();
}
/**
* Reads in the city information from the given file storing the
* information in both the ArrayList of cities and the HashMap of
* flights.
*/
private void readFlightData(String filename) {
flights = new HashMap<String,ArrayList<String>>();
cities = new ArrayList<String>();
try {
BufferedReader
rd = new BufferedReader(new FileReader(filename));
while (true) {
String line = rd.readLine();
if (line == null) break;
if (line.length() != 0) {
readFlightEntry(line);
}
}
rd.close();
} catch (IOException ex) {
throw new ErrorException(ex);
}
}
– 3 –
/**
* Reads a single flight entry from the line passed as an argument,
* which should be in the form
*
* fromCity -> toCity
*
* Each new city is added to the ArrayList cities, and each new
* flight is recorded by adding a new destination city to the
* ArrayList stored in the HashMap flights under the key for the
* starting city.
*/
private void readFlightEntry(String line) {
int arrow = line.indexOf("->");
if (arrow == -1) {
throw new ErrorException("Illegal flight entry " + line);
}
String fromCity = line.substring(0, arrow).trim();
String toCity = line.substring(arrow + 2).trim();
defineCity(fromCity);
defineCity(toCity);
getDestinations(fromCity).add(toCity);
}
/**
* Defines a city if it has not already been defined. Defining
* a city consists of entering it in the cities array and
* entering an empty ArrayList in the flights table to show
* that it has no destinations yet.
*/
private void defineCity(String cityName) {
if (!cities.contains(cityName)) {
cities.add(cityName);
flights.put(cityName, new ArrayList<String>());
}
}
/* Private instance variables */
private HashMap<String,ArrayList<String>> flights;
private ArrayList<String> cities;
}

Programming Methodology-Lecture23 Instructor (Mehran Sahami)

Programming Methodology-Lecture23
Instructor (Mehran Sahami): So welcome to the 106A lecture just before
Thanksgiving. I thought attendance might not be spectacular today. People are still
filtering in, but it’s good to see so many of you here, though. I’m sure some of you have
already headed home.
You may be wondering who I am. I would have thought before we got back mid-quarter
evaluations that you stood a chance of recognizing me as the TA of your class, but the
comment of more than half of the people who responded to the question of how is Ben
doing was, “I don’t know Ben. I’ve never interacted with Ben. So I assume he’s doing a
great job.”
Most of you jumped to that conclusion. But – so I sort of chased at this, but not much. I
realize, though, that I would enjoy the opportunity to develop a little more exposure. And
so Maron and I decided to switch roles for today. In fact, he’s making copies as we speak,
and there’s going to be one handout that’s sort of pertinent to what you’ll be doing for
[inaudible] the next assignment. And he should be back any time, but I certainly can’t
blame him for being – running a little late since I was supposed to make the copies before
class myself. So anyway, in my capacity as Maron, I don’t hope to be as spontaneous or
as funny as he is, but I do hope to talk about something that is a little bit off of the sort of
charted path of CS106A’s curriculum.
So one way of describing the things that you’re learning in 106A is that you’re learning
how to take the ways that you already know of doing things that may take you some time
and maybe error-prone in the doing of them and tell a computer precisely how to do them
so that you reap the benefits of a machine being able to execute those instructions. And
they’ll be faster. There’ll be fewer errors as long as you get the instructions right in the
first place. And that’s got to be an exhilarating feeling. It’s got to be empowering, or at
least it was when I was sitting in your place as a freshman, to know that, all of a sudden,
if you have a good idea – if you can come up with a procedure for solving a problem that
you’ve always had and tell a computer how to do it, then the computer will be able to do
that over and over and over again. All right? So that’s 106A in a nutshell. So it’s sort of –
it’s not a perfect metaphor. What does it mean to run breakout by hands? I don’t know.
So what I – the distinction I’m trying to make between what you’ve been learning so far
and what you will learn, hopefully, in this lecture – and certainly if you go on to CS106B
– is that there are things that computers can do that you couldn’t possibly have simulated
by hand. Computers can handle so much more data than you could ever manage to sort
through on your own manually that it’s worth you’re learning a bit about how to make
them do that – how to think about instructing a computer to do something that you
couldn’t possibly have done. So today, we’re going to talk about two of the most
important kinds of those problems in computer science, and I’m going to stop just talking
at you and show you some examples in a second. But those two topics are searching and
sorting. How do you find something in a set of things that you have? And how, if you
could impose some structure on that set, would you both find it more quickly, and – I
guess I got ahead of myself – how would you go about imposing the sort of structure that
would help you find it more quickly?
All right. So if I’m seeming to ramble, that stops now.
So searching and sorting – I say they are important, and I hope you believe me, and you
think that for that reason, it’s worth talking about for an entire lecture. But they really are
just a way of getting to talk about something a little deeper, which is this concept of
algorithmic efficiency that we haven’t said much about in the class so far. So that’s the
third part of this two-part lecture. What’s the deal with searching? Well, searching
doesn’t quite fit the mold as something you couldn’t do by hand. You find things all the
time. Chapter 12 of the book looks at two operations of the searching and sorting. This is
pretty generic. All right. So searching is simpler. You can define a search problem – say
you have an array or some other collection of things, and you have something you want
to find. The typical way this is done is that you want to find the index into the array –
where that element was – or, in a more generic case, you want to find out if that element
is even in the array. So you want to have some way of determining that it wasn’t actually
found.
And that may be all you care about. It may be the case that, if the search routine returns
anything other than negative one, you don’t actually care what its value was. But we
adopt – I will adopt the convention for this lecture that if you don’t find what you’re
searching for, then the method that you wrote to do the search should return a negative
value since that’s not a valid index into the array. All right. So if you have a set of things
that you’re trying to search through, the easiest way of doing that is just to look at all of
them and see if each one, in turn, is what you’re looking for. That’s called a linear search
because, to sort of pre-figure what we’re going to talk about at the end of the lecture, the
number of operations you have to do to find the element that you’re looking for is
linearly proportional to the number of elements that you had to begin with. Now it may
not be obvious right now that there’s something better that you can do, and with an
arbitrary set of data, there is not anything better that you can do. But this procedure that
I’ve written up here is an implementation of what you already could have written – a
procedure for finding an element in an array of integers.
So there’s nothing very tricky about this. If it had been a string, you might have even
avoided having to write the function and called it something like, “Index of” with a
character. And inside of “Index of”, though you don’t have to write the code, it would
have had a four loop that iterated over each of the characters of the string, tested each one
for quality with the key that you were looking for and then, presuming it found one that
equaled that character – or in this case, that integer – it would return the index of it. And
if the four loop completes, then you must not have examined any elements that matched,
and so you return negative one. Okay? So here’s a simulation of how that would work,
although the – leaving nothing to the imagination here, this is pretty easy to sort of
envision.
So we have this array of primes, and it has 17 in it. So we are going to expect to find that
this linear search shouldn’t return negative one. But the second one, we’re looking for 27
– which sort of looks prime, but of course, it’s not because it’s nine times three. All right?
Okay. So we called linear search, and here’s our new stat frame, which has the local
variables I and the parameters P and array in it. This is sort of Eric Robert’s – who wrote
the textbooks – way of displaying the execution model of JAVA. All right? So we’re just
looping over it, and we’re testing as I equals zero and then one and then two and then
three and four, five, six – where should we find it? Well, we were looking for seven – no.
Right now, we’re looking for 27. So we’re just gonna go to the – I think there was a
problem with the way that – well, anyway. The console here prints out that, indeed, we
found 17 at position six. There may have been a problem converting PowerPoint slides to
Keynote slides, so I apologize for the sort of shakiness of these animations. But the
content of the slides should be adequate. Cool.
All right. So now we’re in our second called linear search, and the only thing that’s
changed at this point from the beginning of the first called was that the key is different.
So I is still gonna start at zero, and it’s still gonna iterate over all of the positions of the
array. But we’re gonna go through the entire array, which means going all the way up to
ten where I is no longer less than ten. And we didn’t find 27 anywhere. So I hope this is
all fairly clear. But these are the results that you would have expected. So we found the
position of 17, and then we looked for 27 but didn’t find it and returned negative one.
Cool.
How many people think they could have written that in their sleep? That that was too
much time to spend on such a simple idea? All right. Well, it gets more interesting from
here on out, but – so talk to me. What is the problem with linear search?
Student: It takes a lot of time.
Instructor (Mehran Sahami): It takes a lot of time, right? It takes as much time as you
have elements. So if I asked a question, which was – if I knew the SUID number of one
of you in the room, and I asked, “Is this your SUID number?
And you say, “No.”
And I ask you, “Is 05179164 your SUID number?”
Is it yours? Be kind. Tell me it’s yours.
Student: [Inaudible].
Instructor (Mehran Sahami): It’s not. So it actually turns out that it’s mine, so I would
have had to search the entire room before I finally got back to myself if I didn’t make that
shortcut. Okay.
So another illustration of what is really a very simple idea – that if you’re forced to look
at all of the elements that you are searching among, then that’s bad in and of itself if you
could do better. So we’ll see if we can do better, but here is a rather larger data set – 286
area codes – the three-digit numbers that come before the rest of the seven digits in your
phone numbers.
But we’re trying to find 650, which is this county’s area code. So here’s a larger array.
What would happen if we were searching in this? Well, it depends. If we have a fast
computer, it may not matter. These are – there’s only about 300 numbers here, and doing
something 300 times is something that computers are reasonably good at.
But I thought I’d put together this sort of compelling example of why this can become a
bad idea.
All right. So I wrote a program in JAVA, which has this implementation of linear search
that we were just looking at. And the difference that you may notice is that I have an
instance variable, which is sort of behaving as though it were an array, and you’ll see
why that is in a second. But all that I need it for is to get values from it at certain
positions, and I wanna know what its length is so that I can iterate over it.
And I’m also – so why is it called DIS? It’s short for display, and it’s this – an instance of
this number display class that I’ve written. And if there’s time and interest, I’ll talk about
how that was implemented. But it’s intended to sort of mimic the behavior of an array
and, at the same time, show you a linear search in action.
All right. So this is a dialogue program that’s just reading line to ask me for some input.
And here are all of those numbers.
So I slowed it down – even if this looks like it’s going relatively fast – so that you could
see it sequentially considering each of these numbers. All right?
You may notice that you can – you could probably beat this. Right? It’s going slowly
enough that, since these numbers are already in sorted order, you can jump ahead.
So what is it – I want you to think about – while you’re waiting on this to finish, I want
you to think about what it is that you’re doing when you search for the number in this list
of numbers that happens to be sorted, which allows you to go so much more quickly than
the computer. All right.
So why didn’t we find 650 here?
Student: [Inaudible].
Instructor (Mehran Sahami): It wasn’t even there? Yeah. Tricky. Let’s fix that.
Where do we wanna stick it? Probably between 630 – they skipped whole swats of – I
just pulled this off of the Internet, which is notoriously unreliable. All right. They
probably aren’t gonna let this run all the way through the next time. But 650, as you will
notice, is now right here. So it would eventually be found. I’ll let that tell me when it’s
finished.
So now I’m going to switch over to a different kind of search, which I hope has
something to do with the way a human looks at a sorted array and finds the element that
they’re looking for quickly. But – no. Help me out before I just show you that
implementation. What is the insight that lets you find elements more quickly if there’s
some structure – if there’s a sorted order to the elements that you’re looking for?
Go ahead.
Student: [Inaudible].
Instructor (Mehran Sahami): Okay. So if I start with the first number in the array, and I
ask myself, “Is the number I’m looking for higher or lower than the first number in the
array?”
What’s the answer probably going to be?
Student: [Inaudible].
Instructor (Mehran Sahami): It’s probably higher if it’s a sorted array, right?
So I know that’s not quite what you were getting at, but I’m pushing on the definition of
this procedure so that you – would you like to add a clarification to what you were
intending?
Student: [Inaudible].
Instructor (Mehran Sahami): Yeah. The number in the middle. Okay?
So if you look at the number in the middle, and you see that that number is less than the
number you’re looking for, there’s a whole set of numbers that you now don’t have to
worry about. Right? It’s all of those numbers up to and including the number in the
middle of the array. Right?
So now you’re looking at half of the array, and in some sense, your problem is simpler. In
fact, it’s a lot simpler because if you apply the same procedure again, then you can cut
that remaining half in half, and you can cut the remaining half in half. Right?
So this kind of searching is called binary searching because you make a binary choice at
each decision point, and you can then cut the space that you’re searching in half. So what
would that look like if we wrote it out in code?
Well, if you trust me, then it would look something like this. And the insight behind these
admittedly too-short variable names is that we’re keeping track of the LH or left-hand
side of the portion of the array that we’re considering and also the right-hand side. So if
you look at these two initializations, it should make sense that you start with the left-hand
side as far left as it can be at zero and the right-hand side at the index of the very last
element in the array, which is one less than the length of the array. Right?
And so you may already be able to anticipate that we’re going to sort of move these in
closer and closer to each other until they identify an array that has only one element or,
potentially, zero elements, in which case we would decide that we were not able to find
the element that we were looking for. All right?
So we’re going to do this halving procedure until it is the case that LH and RH have
collided with each other in some sense. And the idea of getting the middle element is
captured by this next line here where we take the average of left hand and right hand.
Now searching is such an important operation, and it’s so often needed for very large data
problems that talking to people in industry who have to do a lot of searching – you may
hear someone say that there’s a bug on this line. And it’s the sort of bug that has nothing
to do with computer science in the abstract, but it’s just one of those details that is
unfortunate – the bug being that you don’t really have to add LH to RH before dividing
them. You can divide each one by two and then add their halves to get the average.
This is just sort of a side comment, but why might it be problematic for you to add them
together?
All right. If this rings no bells – why would you say?
Student: [Inaudible].
Instructor (Mehran Sahami): Integer division? That’s – I think if you work with some
small representative cases, you’ll see that that doesn’t prove to be a problem, although
that’s a good insight. But there is a maximum value – yeah?
Student: What if they’re too large?
Instructor (Mehran Sahami): What if they’re too large? So an integer can be as large as
– an [inaudible] integer can be as large as, like, four billion. But what if each one of LH
and RH is, at some point, three billion or greater? Right? And there’s going to be a
problem adding them together.
But we’ve already spent too long talking about that. I would just throw it out as sort of an
interesting detail. But after many, many years of using a binary search that looks exactly
like this, only recently have people begun to realize that little problems like that can sort
of spell disaster with really, really big problems – really, really big sets of data.
Okay. So anyway. That is somewhat an immaterial point.
We now have the index of the middle of the array – or at least the middle of the portion
of the array that we’re considering right now – and we ask our sort of array-like object
what number is at that index. And if it’s equal to our key, then we’re done. We can just
return that we found the index that we – of something that matched the key. So in the
linear search case, if there were multiple copies of the key that we were looking for,
which one would be returned?

The first one, right?
Do you have any insight yet about which one might be returned in this case?
It’s not at all clear to me. And in fact, binary searches generally don’t guarantee anything
about which element they return if there are multiple copies.
Anyway. Assuming that we don’t get lucky, though, and that we don’t find the element
that we were looking for on our first try, then we have to modify the size – the part of the
array that we’re looking at. So how do we do that?
Well, we need to determine, as was suggested, whether the element that we’re looking for
is less than the middle or greater than or equal to the middle. And in the case that it’s less
than the element of the middle of the array, then we want to adjust which side.
So we know that it must be in the first portion of the array, and we’re going to ignore the
second portion of the array. So the right-hand marker that we’re – is what we need to
update this time. So that’s what this does. It updates the right-hand marker to mid minus
one. And why is it minus one?
These sorts of issues can be really frustrating to be off by one errors in otherwise already
complicated algorithms.
Student: [Inaudible].