[ Silence ]
>> Welcome to almost the end of CS50.
This is week 11.
Week 12, as you know, is the end game.
So last lecture this coming Monday.
Quiz 1 is this coming Wednesday,
so a few announcements about that.
So quiz same place as last time.
See the hand up that's on the website if you haven't already.
I'll be holding those last minute late night panick office
hours Tuesday night in [inaudible name] Cafe
on the ground floor at 8 p.m. till whenever.
If you have questions that you would like to address
at that point in time, and the TF's
and CA's have some as well this week.
Coming up is P set 5's deadline.
So this little guy has yet to have anyone submit photographs
of him, and my God, I walked all over campus for like 2 hours
with that friend taking these photographs, and I know some
of you guys have found some of these photos because Ken and I
and Alex and Jansu have all been photographed;
but no one's actually submitted their little map of photos.
You have till Friday at midnight of this week
for that amazing prize coming up next Monday.
So also this week we have this little blurb,
the Harvard extension school has put together this program here,
very fancy invitation here.
There is a panel discussion with a number of alumni
and fairly famous people led by our own Harry Lewis,
a professor in the computer science department.
It's entitled "No More Teachers No More Books" higher ed
in the networked age.
This is this Wednesday at 4 o'clock if this interests you.
And then they've also invited some of us, 10 or fewer,
to the faculty club afterwards.
So we thought we'd turn this into a faculty club reception
with David and team if you would like to join us.
Go ahead and go to CS50.net/rsvp.
Among other things you'll have chances to chat with faculty,
myself, some of the TF's and CA's, also Craig Silverstein
who is Google employee number 1, and who's actually on this panel
that Harry is moderating.
So take a peek at that if you're interested.
This, I thought, was kind of timely.
So I was literally riding the T this morning, and the Metro,
this free paper in Boston had this ad here, or this article.
New Best Friend for MBTA Busriders,
and it goes on to discuss an API that the MBTA has just released
in hopes, frankly, that other people will now implement the
rest of this tool for them.
So they have opened up a shuttle and API by which you can find
out the next times of buses actually arriving in real time.
So not printed schedules, but actual real time data
for a number of the routes.
So frankly, even if you submitted your proposal already,
do feel free to bite off something that's perhaps a
little different if that appeals.
Also today at 3 p.m., so half an hour after lecture,
Apple Computer itself is going to be offering a seminar
on iPhone development.
So whether you're tackling an iPhone app project,
or even are just curious, or like pizza,
come by at 3 p.m. Maxwell Dworkin 119.
That's 1 floor up on the computer science building.
And what else?
We got anything else here?
OK. So I'm told UC elections are in progress.
And I'm a bit of a packrat when it comes to maintaining archives
of things, so look at what I found.
[ Laughter and applause ]
So I'd like perhaps to take a chance
to re-declare my candidacy some 10 years later.
This is perhaps an example of how not to do web design,
or this is what happens when you try to design a website
around an animated gif that you just really want
to use for some purpose.
If you actually click through this you'll see my very verbose
platform that I had at the time, including a letter to freshmen,
some campaign posters.
And just to give you a little retrospect from 10 years ago,
the undergraduate counsel, so this is 1996 or 1997.
The undergraduate counsel today suffers from 2 problems.
Not only does the counsel lack the attention
of the student body, it lacks respect as well.
As recent voting turnout suggests,
most students neither know
who their representatives are, nor do they care.
Lowell House, our favorite house given the number of you
in this class, for instance is home to some 450 students
yet only 25 of them voted in 1997.
So I do hope that things have come a long way since then.
This platform didn't take me very far, clearly, but good luck
to those in this year's elections,
which I gather are now in progress.
So please, if nothing else,
no animated gif's in your own projects.
Finally, I've been told to wear this today.
Our own Yuki Machita has been designing our CS50 store.
It's store.CS50.net.
And I'm told those of you who celebrate,
they make wonderful Christmas gifts.
So keep that in mind perhaps.
But today is ultimately about life after 50.
This handout that you have here is an excerpt
from the course catalogue, and all of the courses
that you are qualified to take after CS50;
some of them this spring, some of them next fall,
and 1 or 2 of them only being offered the spring thereafter.
So today realize it's not just about advertising some courses
that we think you might want to take, but it's also meant
to be a little more academic than that,
and to give you guys a sense
of what more there is in computer science.
So many of you statistically will consider CS50
to be a terminal course.
You got out of it what you want,
and that's sort of enough for you.
But realize that there's a lot of holes
that you can begin to fill in.
Realize that this course surveys a lot of fields,
a lot of subfields that you can really only begin to appreciate
and master by taking full fledged courses in these fields.
So what we have today is a team of computer science faculty
who will be giving you a taste, yes, of these 5 courses
that you might take this spring or coming fall; but also a taste
of computer science itself.
So realize that there's so much more out there.
You've only begun to scratch the surface,
and it really takes a good amount of time and attention
to really feel like you've honed this stuff.
So with that said, allow me
to introduce Professor Greg Morrisett
who teaches computer science 51, which is historically, sure OK,
which is historically the follow up...
[ Applause ]
... to computer science 50, and this is the course
that I myself took as a second course in computer science.
So it's a little close to my heart as well.
>> Professor Greg Morrisett: Thank you David.
Good morning, afternoon...
sorry. What is CS51?
CS50 is entitled something like programming.
What's it called?
What's the official name?
Programming 1 or something, introduction
to computer science 1.
51 has the wonderful title of introduction
to computer science 2.
So what's the 2 all about?
Well I hope most of you realize at this point
that programming is not that hard.
I teach 5th graders sometimes how to program.
Scratch is kind of fun for doing that.
What I have learned is that you can teach just
about anybody how to program.
But it's very, very hard to program well
and that's what 51 is all about.
It's not just programming, now it's taking it to the next level
and seeing how you can program well.
What do I mean by well?
You need to be able to write code that's reliable, efficient,
that it obeys the contracts that it has with the outside world
in terms of correctness, in terms of efficiency.
It should be testable.
The ideal code you should be able to prove correct.
It should be easy to maintain.
It should be beautiful, something you want
to take home and show to your mom.
Really good code is elegant.
And that's what 51 is about.
The other part of 51 is that it's supposed
to expand your problem solving skills by making it possible
to quickly and easily recognize the right tool for the job.
So the right tool might be a data structure, algorithm.
It may be a conceptual way to think or frame the problem,
or to break it up into more easily solved subproblems.
It may even be a programming language.
And the prime directive of CS51 is that at all costs
to be as lazy as possible.
A really good programmer is so lazy they will go
out of their way to write code to make it possible
to not write code in the future.
So they pull out the right things into libraries,
into reusable data structures and algorithms.
They keep interfaces small and simple,
and they reuse somebody else's code whenever they can.
But 1 other thing that they do, and the thing that I'm going
to highlight just today, is they pick the right programming tool
for the job.
So they may pick the right programming language
for the job, and to give you an idea of this I want you
to think just for a second
as if the Arabs had never invented the numeric notation
that we use today.
And instead we were still stuck with Roman numerals.
Imagine trying to write an algorithm just
to multiply 2 Roman numerals.
It's actually very hard to do.
About the only way I know how to do it, that's even reasonable,
is to translate them first into Arabic numerals,
some form of numbers and do the algorithm at that level,
and then convert them back.
So the way, the language that you have
for conceptualizing your problem can have a strong influence
on whether you can find a solution and how efficient
or how elegant the solution is.
Now it's true that often times we don't have the luxury
of picking the language or the tools that we're using
for a particular programming task, but if you can think
in a different language, at the right level of abstraction
about a problem, and if you understand how those mechanisms
are realized, how they're implemented,
then you could take those ideas and translate them back
into the programming environment that you are forced to use.
And that happens day to day in real programming tasks.
It is not thinking necessarily at the level of C code,
but thinking at a much higher level of abstraction
and then be able to decompose the problem
and translate it back down.
So here's a simple example.
This is 1 of the data structures that we'll look at.
It's the red-black tree.
It's a data structure that goes back to Sedgewick and...
Michael's laughing.
You cover this in 124?
Nope. That's why we do it in 51.
So it's a balanced binary tree.
There are many flavors of these
like B trees, 23 trees, AVL trees.
Very useful for representing sets or finite maps,
or tables when you need to have efficient support for lookup,
insertion, deletion, and so forth.
The key thing about red-black trees is that in order
to maintain good asymptotic balance for lookup or insertion,
you have to keep the tree balanced.
And these 2 invariants up here, these 2 properties,
are properties that ensure that your tree is always bushy enough
that you can guarantee logarithmic access time
for insertion or deletion.
So these 2 invariants say that every node,
red node, has a red child.
No red node has a red child, and every path
from the root has the same number of black nodes.
So it's just a way of laying out the tree in a balanced fashion
so that no chain is too deep.
And if you insert a new node and end
up breaking these invariants, so here we have...
this new number, 25, inserted into the tree.
We've broken that invariant.
Then you have to reorganize the tree on the fly
to restore the invariants.
OK? Now the algorithms for doing this, if you formulate them
in 1 language they can be very tricky to get right.
And if you formulate them
in another they can actually be quite simple.
So here is the code for doing insertion and re-balancing
in a high level language called ML.
It's a functional programming language,
and it's 1 of the languages that we'll be looking at,
and provides certain features such as pattern matching
on algebraic data types
that makes writing this code essentially a 1 pager,
or a 1 slide.
If you look at your favorite algorithms textbook for example,
Sedgewick has an algorithms textbook, you look at the code
for doing this and see it's 4 times the size
of that code up there.
Here is the code for doing insertion, except I ran
out of room and actually have to double the amount of code
down here and repeat it except swap red and black.
And also I didn't show you the subroutines, tree insert,
left rotate and right rotate.
This is what left rotate looks like.
And right rotate is just like it except you sort
of flip things around and make...
so the point is that actually staring at this code
and deciding whether you've got it right,
and whether you're respecting those 2 properties can be very
hard to do.
And if you test the code, you may find out that
in your particular test cases it seems to pass all the tests.
But if you've got a really tricky problem,
you'd like to have more than just testing
as your form of assurance.
You might like to go back and formally prove
that your code respects these properties that I mentioned.
Proving that your algorithm is correct is pretty easy
on 1 page of code.
It's certainly a lot easier than doing it
on 4 pages of low level code.
This code also has other advantages.
It's safe with respect to exceptions, and multi threading,
whereas the C code is not.
And how do you get those properties?
Part of that is because the language is forcing you
into a certain discipline
that gives you those properties for free.
On the other hand this code is doing functional updates
to a data structure, whereas the C code is doing
imperative updates.
And how do you efficiently translate a high level language
like this down into something like C code?
That's something that we're going to be looking at in 51.
The goal in this class is to give you an understanding,
not just of 1 programming language, but of a bunch
of linguistic abstractions that you're going to run into over
and over again; although usually they'll have different names
like Microsoft will give it some name,
and Google will give it a different name.
And you want to be able to recognize these abstractions
and apply them wherever you are.
You may be operating in an OO language
and you need the concept of a closure.
How can you represent closures as objects?
How can you represent objects as closures?
These are some of the ideas that we'll be talking about in some
of the linguistic mechanisms like laziness,
that we'll be using in the class.
We're also going to be seeing some exposure
to software engineering techniques.
I call these software engineering in the small.
So instead of training you how to code 50 million lines
of code, which is basically something nobody knows how
to do well, witness Microsoft.
We're going to be talking about at least little things
that you can do to make your code more readable,
more testable, more maintainable.
So simple things like modular design
and how do you use language mechanisms to get modularity?
How do you do integration and unit tests?
And how do you read somebody's code in a critical way?
How do you do code reviews?
We're also going to be looking at abstract models
of computation beyond simple programming languages.
So we'll be looking at for example, models for space
and time, and this is a good prelude into 124
which Michael will tell you about.
We'll be talking about models for reasoning about code
at a high level abstraction,
like a substitution model of evaluation.
We'll also be talking about how to prove properties of code,
like how do you prove the correctness?
Or how do you prove the asymptotic efficiency
of your code in a very rigorous, informal, mathematical way.
OK, so that's really all I have to say about 51.
I'll be around the whole time though,
in case you have any questions.
Let me now hand the mic over to Matt Welch,
who's another professor in computer science,
and he'll be telling you about CS61.
If there are any questions while he's coming up here,
I'll be happy to yield.
No? Good.
[ Applause ]
>> Matt Welch: I'm assuming there's...
Hi everybody.
I'm going to do the rest of this in Latin because we are standing
with these esteemed gentlemen on the left and on the right.
So what I want to do is talk to you a little bit about CS61.
CS61 and CS51 are like 2 sides of the same coin.
They're both intended to be classes
that are taken right after taking CS50.
In fact a lot of freshmen are also taking CS61 this semester.
CS61 is an introduction to computer systems
and how computers work internally.
So the basics of the class, we meet on Tuesdays
and Thursdays at 2:30.
The pre-requisite is this class,
or just any C programming experience.
You can in fact use CS61 for the CS concentration breadth
requirement that is to satisfy the need to have several classes
with different middle digits.
You can also use it for the CS secondary.
We generally say that most students who have an interest
in CS, whether you're going to be a concentrator
or just do the secondary, should take both CS51 and CS61
because they really compliment each other nicely.
So what's CS61 all about?
Really this class is about understanding the guts
of how computers work, getting under the hood
and really driving down on the things that matter to you
as a programmer in terms of the performance
of the code that you write.
So what we try to do is understand how a processor works
internally, and then how do you write good C code
that can map well onto what the processor knows how to do.
This is extremely important in real world
because in the real world you're going to be expected
to write programs that perform well.
And that are, of course, also correct.
We'll talk a lot about caching and memory management.
That is, how to lay out the data structures in your program
so that they give the best performance on the processor
and the memory architecture of the machine that you're using.
We'll talk a lot about concurrency.
So every computer that you can buy today basically has multiple
processors, multiple cores on the same processor chip.
And in order to make use of those you generally need
to write programs that can do multiple things simultaneously.
Threading and processes are 2 straightforward ways
of accomplishing that, but writing this kind
of code is very complicated because the threads have
to interact with each other.
So this is 1 of these things that you need
to understand how to do.
And just generally how to write rock solid
and fast systems codes.
CS61 is extremely practical if you want
to improve your programming skills.
The reason that I introduced the class is because we saw
that there is a huge gap between many of the concepts presented
in computer science classes in the reality
of how real systems work.
And so as you learn how to program
in higher level languages like Java or ML, that you do need
to have an understanding of how those map
down onto what's happening
at the physical electronics inside the computer.
That's really critical for performance.
So you need to understand operating system...
you need to know these details to understand things
like operating systems, databases,
compilers, and so forth.
Let me tell you a story that I think motivates the need
for a class like CS61.
How many of you have heard of this case of Ken Thompson
who is 1 of the coinventors of Unix and C,
hacking the original Unix system?
Has anybody heard this story before?
This is a fascinating lesson in why not
to trust the code that you're running.
So Ken Thompson, he coinvented the Unix operating system.
He won the Turing Award,
which is the computer science community's equivalent
of the Nobel Prize.
The Turing Award is awarded once a year
to an emminent computer scientist, and it's a really,
really big deal to win the Turing Award.
And as part of winning the Turing Award,
the winner is asked to give a lecture on their work.
And during his Turing Award lecture Thompson made
the submission.
He basically reminded people back in the early days
of the Unix system he wanted to be able to log
in into any Unix computer that was installed,
without having to have an account.
So what he did was he hacked the log
in program, and added a backdoor.
Yeah? So he added a special password that only he knew,
that if he tried to log in with a password then it would let
him in.
Yeah, OK? And that was really great for debugging.
He wasn't trying to do anything malicious with it, but he wanted
to understand what was going on inside.
The problem was that everybody had the source code,
back in those days everything was open source
so if somebody happened to look at the code for log
in they would notice
that there's this backdoor in the code.
He didn't want people to know about this.
He wanted to cover his tracks.
So what he did was he hacked the C compiler,
and the C compiler then understood
when it was compiling log in.C to add the code for the backdoor
to it before compiling.
Anybody see what's going on here?
Yeah? So if you looked at log in.C itself,
you would not see the backdoor code.
Alright, so what's the problem?
This works right?
So if you're looking for login.C you won't see the backdoor,
but there's somewhere else you could look that you'd notice
where the backdoor is.
Where is it?
In the C compiler code itself.
Remember the source code for everything,
including the C compiler,
was just sitting right there on every Unix system.
So you could just look at the source of the C compiler.
So here's what he did.
He hacked the C compiler to recognize
when it was compiling itself...
to add the code to add the code to login.C for the backdoor.
This is a true story.
I'm not making this up.
And so then he deleted that version of the C compiler,
so now we have a C compiler in binary form only
that would always, everytime it compiled itself,
would inject this additional backdoor code
into the new version of the C compiler,
which would then inject the backdoor code into log in.
OK, so this is amazing.
This is just so cool right?
It's just extremely nefarious.
The only way that you would have been able to understand
that this was happening is if you were able to look
at the machine code for either the C compiler or for the log in
and notice that there's this backdoor there.
It was never present in source code form.
So there's no source code that represents the backdoor anymore.
This is an interesting problem.
In CS61 one of the key skills you're going
to gain is being able to read machine code
and understand what the machine code is doing.
So what we're going to do in CS61,
learn how machines really work.
You're going to really be an expert at using things like GDB.
We're going to debug the hardest and the most interesting bugs.
We're going to drive down to the machine code level
in order to do that.
Hacking binaries for fun and profit, 1 of the labs
in the this class, I'm going to give you a broken binary
and you're going to exploit a buffer overrun bug
in that binary and cause that binary
to do things it was not designed to do.
This is basically the jist
of how most viruses and worms propagate.
You're going to measure
and improve the performance of your programs.
We're going to be very focused on getting good performance,
and you're going to write multi threaded concurrent programs
like a professional.
So you're really going to understand how
to exploit all those extra cycles
and cores on your machines.
So this sounds like it's a lot, it's hard,
but I want to emphasize this is an introductory class.
All of you can take CS61 and be successful in it.
So it's challenging but it's a lot of fun.
This is not intended just for hardcore CS concentrators.
We have 5 lab assignments.
The first one I give you a binary and it asks you
for a series of 7 passwords.
You have to get all 7 passwords right.
I don't give you the source code.
So how do you figure out what the passwords are?
You have to disassemble the binary,
read the machine instructions,
and understand what it's trying to ask you for.
This is a lot of fun and it's quite addictive.
You'll do this buffer overrun bug,
you'll implement your own version of malloc.
I promise after doing this you will understand how
pointers work.
Write your own Unix shell and you're going
to build your own concurrent multi threaded internet service.
So there will be 1 midterm exam and 1 final.
So that's basically what the whole course is.
I'm going to skip over this.
You can go look on the website to look at the syllabus.
And I just want to leave you with this.
So this is my favorite way of representing what CS61 is.
How many of you know what this is from?
This is from the Matrix.
So this is how I think of it, which is CS61 is the red pill.
If you take CS61 you're going to understand what's going
on at all these lower levels
of what's really happening inside the system.
So I encourage you to take CS61
and I will show you how deep the rabbit hole goes.
Thanks.
[ Applause ]
>> Well we'll switch the movie real quick.
>> This is my former professor, Professor Michael Mitzenmacher,
who teaches computer science 124.
>> Professor Michael Mitzenmacher: So I'm really
into algorithms and how they can be used in actual reality.
So to start with I thought I'd, before explaining the course,
explain some of the research I do by way of a movie;
try and give evidence that it's not just that we come out here
and say yeah, algorithms are important and useful
and allow you to do cool things.
But actually like to show you
that they allow you to do cool things.
So hopefully this will go.
[ Silence ]
>> In a perfect hash table we can look
up any rhythm in constant time.
We construct perfect hash tables on the GPU using a hybrid
of 2 randomized constructions.
A thread is a sign to each item.
First it leads the randomly chosen top level hash function,
and uses it to choose a bucket to hash to.
The item then commits a counter
for it's bucket using an atomic operation.
We prefix on the array of final counts,
at which point we know a base and an offset for each item.
We allocate memory and then each item writes itself
to the location defined by it's base plus offset.
Within a bucket, we organize the items using Cuckoo hashing.
The table is broken up into 3 subtables,
each with it's own hash function.
Items that cannot fit into the first table proceed
to the 2nd one, and items that cannot fit
into the 2nd table proceed to the 3rd.
An item that fails to fit into the 3rd table, like H,
goes back to the 1st table and evicts the item currently
in the location that it wants.
The eviction process continues
until all items have found a spot.
Each bucket is processed within a block.
We write out the Cuckoo hash tables
with all the 1st tables together, then all the 2nd,
and then all the 3rd tables.
This allows more coalesced access for parallel lookups.
Hash tables are useful
for representing voxel live surface data.
Only the surface voxels are stored in the hash table,
greatly reducing the storage requirements.
This is called spacial hashing.
Here we are using spacial hashing
to find the interception of 2 moving surfaces.
At every frame we read a point cloud for each surface,
and construct a hash table
for the voxels containing the points.
We find the green intersections by looking up the voxels
of 1 surface and the table of the other.
We use the hash tables to flood fill along the surface
to find a blue region inside the other object.
Here we compute a in difference,
subtracting 1 running man from the other.
The user can move the men around interactively.
We achieve a frame rate of about 27 frames per second using a
virtual voxel grid of size 128 cubed with surfaces
of roughly 160,000 points.
[ Silence ]
Matching is another important application of hash tables.
Here we have 2 different images
of a carved relief from Persepolis.
We use a sobel edge detector
to select distinctive feature points in both images.
We encode triples of points from 1 image in a way
that is invariant to translation, rotation,
and scaling, and store the codes into a hash table.
Then we look up triples from the other image in the table.
We find the match, we look for a correspondence.
In this case the top ranked correspondence matches the 2
images almost perfectly.
This technique is called geometric hashing.
In this clip of 2 people fighting,
you look for the following man on the upper left.
The graph shows the number of votes
for the best correspondence in each frame.
The best match usually aligns the query shape to the man
in black, but when he bends
down the algorithm cannot find enough matching triples.
When there is a perfect match we find it.
Here we recognize some of the monuments
that Mac Harding dances in front
of in a semi famous You Tube video.
This image of Saint Basil's Cathedral
at the Kremlin matches Mac's video.
It does not match this Bangkok street scene.
Here we match this image of the Taj Mahal to the video.
We don't get a good match at Progue Castle, as expected.
We match a video frame, including buoying
for all potential correspondences,
in about 2 seconds on average.
The construction of the hash table
for about 3 million items takes 44 milliseconds.
Thank you for your attention.
[ Applause ]
>> Alright.
So I'm not promising that the end of 124 you'll be able to do
that necessarily, but I am promising that you'll get a lot
of the skills that you will need to go forward
into your further classes where you will be able
to take algorithms and data structures,
and find cool things to do with them.
I view CS124 as putting the real science in computer science,
that it's going to give you the tools you need to do a lot
of really interesting things all the way down the line.
[ Silence ]
Alright, so the course goal for this is to provide everyone
with a solid background in algorithms and data structures
in preparation for future work, graduate level work,
in algorithms, further work in your undergraduate classes,
or for jobs in industry.
One of the things that I'm always excited and relieved
to hear afterwards is that when people go
out on their job interviews, they always come back
and tell me that they were asked questions that have...
exactly do with something they learned in CS124.
This is the sort of skills people are looking
for when they're looking for a job, not just that you know how
to program, but that you know how to think about problems,
that you know the ways to attack problems, that you know the sort
of tricks and techniques that can be used to solve problems
to get working code solutions.
And so the key course goal is to actually get you ready,
whether this means you're going on in your studies,
or going on in the work world.
So the class set up, I welcome people from all different areas.
Certainly the bulk of people tend to be computer science
and applied math concentrations,
but we also get people every year from biology, physics,
economics, mathematics, and other areas because more
and more as other fields are doing more and more computing,
the people in those fields are finding that they need
to understand algorithms and how they work.
The assigments in the class, because I do believe
in algorithm practice and not just algorithm theory,
they tend to be a mix.
There are certainly going to be plenty of theoretical
and mathematical work, but we're also going
to have programming assignments.
My joke is I find that this maximizes the feelings
of unhappiness.
The mathematicians are unhappy because they have to program,
and non mathematicians are unhappy because they have
to do math, but really is the best way to get both ends
to understand not just how algorithms...
to think about them abstractly,
but also to implement them and how...
the tangible gains they can actually get you
in real problems.
So this class, CS50, is the minimum prerequisite,
but I should point out certainly 51 and 61,
121 and strong math backgrounds are all helpful
but not at all required.
The sort of topics we're going to cover, a rough list.
We'll go over graph algorithms.
We'll go over a variety of techniques for solving problems,
reading algorithms, divide and conquer,
dynamic programming, linear programming.
We'll look at things like hashing,
something that you just saw a video on,
some advanced hashing techniques.
And randomness, how to use randomness in algorithms,
how to understand how randomness can help you in algorithms.
We'll look at MP complete problems, and how to solve them.
If you've learned anything about incomplete,
MP complete problems, that may seem like an odd statement;
that MP complete problems are supposed to be the problems
that we're not supposed to be able to solve.
But of course in the real world you can't just go to your boss
and say, well this problem's MP complete
so I don't have to do it anymore.
They're going tricks back to solutions, so we'll come
up with ways and techniques in thinking
that we'll let you solve them for practical situations.
Currently scheduled, if I read the book right, Tuesday,
Thurday 11:30 to 1:00.
I hope you'll consider it for this spring.
If not I'll hope you'll consider it for your next spring,
offer it every year, and I hope to see you there.
Thanks.
[ Applause ]
>> So next up is going to be Professor Hanspeter Pfister.
He teaches computer science 171, which is visualization.
This is actually a course like CS61 and CS179
that actually didn't exist in my time.
And to be honest it's sort of with envy that I see what kind
of courses they've added to the undergraduate roster, because
and this isn't just saying this
because my former professors are here,
or because I think I need to say this.
A lot of these, I think, are great fun and the fact
that you can take these courses
after just 50 alone is really quite empowering.
So, Professor Pfister.
>> Professor Pfister: Thanks a lot and thanks for coming.
So I'm teaching visualization,
so you might ask well what is visualization?
Visualization is essential to convey information
through visual representations.
So we're talking about graphs, charts, maps, and all kinds
of fancy ways to visually depict information.
And in particular this class will focus
on interactive applications of visualization
where you can actually interact with any of these
in an interactive way.
So if the previous courses were more about the science
of computer science, this class is much more
about the design and computer science.
So it's a combination of both design and computer science.
And as a matter of fact, only about a third of the students
in this class are CS concentrators.
So this is really a class that should appeal
to pretty much everybody because I believe everybody is dealing
with information.
Now why is this class important?
I think actually visualization is 1 of the big topics
that we currently have to deal with.
It's because we're living in the age of information explosion.
So we have too much information online.
We can't really make sense of it all in just text form,
and so we need some other representations
in order to understand it all.
This is even more so in the sciences
where people have coined the phrase 'industrial revolution
of data'.
So we're now able to collect data at a much faster rate
than what we're able to process or comprehend.
And that's because we have all these great sensors
from the very small to the very large that provide us
with more and more data.
So in order to understand all of this we need some means
to basically look at the data,
and this is probably the worst possible way to do that.
So instead of just looking at numbers, we want to look
at visual representations.
And as Donald Norman, one of the great industrial designers
and ACI expert has said, it is things that make us smart.
So we learned how to write down things
so we can preserve history.
We learned how to make pictures and graphs
so that we can understand information and convey it.
So this class, or I should say visualization
in general, will help us think.
I hope the class will help you think too.
It releases the load on working memory.
It all floats from our cognition
because we can literally represent the information
in a different medium.
And it uses the power of human perception.
So as you may know, our visual system is the biggest sensory
organ and it's represented in our brain with about half
of the neurons in the brain, so we have a huge amount
of perceptual power that we can actually use
to understand information.
So the goals of the class are to teach you the principles of how
to make effective graphs, charts, maps,
and visualizations; and then how to teach you to gather the data,
in particular from online sources.
So we're going to teach you how to use Python,
which is a very nice and simple to learn scripting language,
to scrape information from webpages.
And then using that information that you gathered,
implement interactive visualizations using a Java
framework called processing.
And again, processing is relatively easy to learn.
And finally we have a few programming homeworks
and a final project where you can put all of those skills
that you're learning in the class to use.
So what I'd like to do next is show you a few projects
that students have done last year.
And I'm going to start with Jason Gowell.
So Jason actually in all this, the students start
with a question study of personal interest.
I'm sorry I can't fit it all on the screen right now,
but he started with the question 'what is the energy used
of the different buildings on the Harvard campus?'
And it turns out that
that information is actually available
from the Harvard Office of...
what is it called...
I guess of Public Buildings.
So what he did is he plotted the yearly energy use
of the different buildings
on the map using circles representing the size
of the energy use.
And as you may be able to see here on the right,
he also has a pie chart
that shows you how the different buildings use
that energy depending on the type of energy.
So let me move this over.
So green is electricity, red is steam, blue is chilled water.
And you can see that depending on the building shown up here
with their name, you have very different energy usage patterns.
And as a matter of fact, if I were able to scroll,
you could actually see that this energy usage pattern changes
over the years.
So down here he has a visualization
of how this changes over the course of the year,
and the pie chart up there will automatically update.
Now going back here, let me just show you the last bit
of the visualization, which is you also have a list view
that shows you the biggest and smallest energy consumers
on the Harvard campus over here.
And again, depending on the time of year,
you have different buildings
that use different amounts of energy.
So this was an effective visualization
to show you the energy usage on the Harvard campus.
Next project I'd like to show is by Navin Sinha [phonetic].
Navin was interested in finding good restaurants
in the Cambridge and Boston area.
And instead of just building yet another visualization
of the ratings, he actually went to the different newspapers here
in town, Boston Magazine, Boston Globe, Boston Herald,
and Boston Phoenix, and he computed an average,
or compound score for each of the restaurants
that those newspapers rate.
And then what he's showing here is the deviation
from this average score between the different newspapers.
So let's quickly look at that.
[ Silence ]
So here again is this visualization.
Let's first turn off the filter here.
You can actually see the name of the restaurant here.
So number 1 is Hoya, followed Les [inaudible name],
followed by Number 9, followed by Uni, and so on.
So for those of you who like to eat well,
you probably recognize some of these names.
So the restaurants are ordered from right to left,
the top ranked restaurant on the average rating being
on the right most side.
But then he's showing the deviation.
Bars that go above the line show that this particular newspaper,
for example Boston Magazine, has ranked this restaurant here,
Aura, on average higher than the compound average score
of all of the ratings.
And similarly some of them are ranked lower.
So you might see for example the Boston Herald seems
to be more critical of some of the restaurants
that are typically ranked highly,
and then some others are ranked a little better over here.
Then you can look at the different categories.
So here are the inexpensive restaurants.
You might find out that Garden
at the Cellar is a very good value if you like good food
and don't want to spend so much money.
You can conversely look at the expensive restaurants.
Not surprisingly, most of them are here in the top category.
I'm sorry, you can't really see some of the bars
on this projector, but I'll just show you these are all top
ranked and expensive.
But then this one here, Moo, is actually expensive
but doesn't get such a good compound ranking.
So it might not be such a great value for your money.
You may want to find out which cuisine is ranked highest,
and it turns out Japanese actually is...
Oya and Uni and the Oshi suishi bar.
They're all ranked very highly, and so on.
Let me show you another example from last year.
Karen Hanson, she works in the microcellular
and biology laboratory and she's going to apply to grad school,
and she wanted to find out how are the different MCB labs
around the country deal with admissions.
So she put together this nice visualization...
again I probably cannot move this, I'm sorry.
But she put together a nice visualization
of admissions based on different schools and based
around the country, showing you what are the areas
where admissions are relatively high.
So definitely California is 1 of them,
Massachusetts being another.
And then showing you the sort of statistics
of the typical student that gets into these programs.
And then over here she also has more information
about each school, how many students they admit per year,
and what kind of characteristics that each school is looking for.
And then also the top faculty in the country that admit students
in MCB, and what kind of profile
that they're typically looking for.
So lastly related to this, there was a project
by Shao Hai [phonetic] who also was interested in MCB,
but he looked at the publication records of faculty
at MCB here at Harvard.
What he did, he has a visualization showing you the
different publications that the faculty have.
So you have the list of faculty here on the right,
and then the size of the circle shows you how many papers a year
they published.
You can see the legion, but I happen
to know the big circle is 30 papers a year.
So this professor here had 30 publications a year.
The X axis is numbers of years since PhD,
so this is a senior person,
and here is actually a more junior person.
And the Y axis is if they were a senior author
or a junior author, i.e. first author on the paper.
So you can see some of the more junior faculty tend
to put themselves as first authors, whereas most
of the senior faculty tend to be senior authors.
Again he was interested in this particular question.
He also did a timeline of publications over time
for each of the faculty.
So you can see that the senior faculty tend to peter
out after a certain number of years of being in the business.
So I think these were some really fun examples
from last year.
I invite you to go to the website
and you'll see a lot more.
And I also want to briefly mention the topics we'll cover.
We'll talk about perception, sort of the fundamentals
of interaction, design, and visual design.
And then we'll talk about different visualization types
such as graphs, maps, trees and networks.
We talk about how to visualize high dimensional data.
And finally we have some guest lectures of people coming
in talking about application areas
such as scientific visualization,
or life science visualization,
or even visualization in the arts.
So I hope to see you all during shopping period,
and thanks a lot.
[ Applause ]
>> So we have just 1 more teaser for you.
This one from Professor Krzysztof Gajos who's teaching
computer science 179, which is sensibly about user interfaces.
>> Professor Krzysztof Gajos: Hi my name is Krzysztof Gajos.
How many of you here are first years at Harvard?
Well so am I.
I'm very excited to be here.
I think what makes Harvard computer science incredibly
exciting is not only the computer scientists,
but everybody else at Harvard.
It's the fact that Harvard focuses not only on the bits,
but also on the rest of the world.
We are here to make an impact.
Greg, Matt, and Michael told you a lot
about how you can solve problems, and the skills
that you need for solving problems.
And I think this is actually important for computer science.
In fact let me start with a story
from my own undergraduate experience.
My first research opportunity down at the technical college,
a little bit down the river,
was with an information retrieval group.
David Cargo was incredibly interested in web search.
It was a time of Alta Vista, Web Crawler, Meta Crawler,
and each week he would start the meeting by bringing up 1
of those new search engines because they tended to pop
up roughly once a week.
He would test it always in the same way.
He would type in his name and see what came up.
And inevitably the first thing that would come
up in those engines would be a publications database that...
that said his name more than once, or another website
that mentioned him but it was never his homepage.
And 1 day I knew that things had changed.
He looked different.
There was suspense in the classroom.
He was going to tell us something very special.
He brought up a search engine, a brand new search engine,
typed in his name, and out came his name.
What was the search engine?
No it was not Alta Vista, it was Google.
What was special about Google?
What made Google special?
It was the fact that there was a very important problem,
search problem, that has been around for many years.
There were lots of people working on it,
and Google guys figured out how to solve that problem well.
They used all of the skills and computer science and came
up with the great solution.
They started with a well defined problem and they came
up with a great solution, and that made them great.
But I argue that besides being incredibly smart,
[inaudible name] incredibly lacking.
How many great problems, well specified problems,
can you name off the top of your head?
Probably not that many, right?
I think as computer scientists we need another skill,
and this is the skill that all of these people have.
These people have the skill of going out in the world
and finding the problem.
They go talk to people, figure out that people have the problem
that they themselves might not even know about,
and then they come up with such a compelling solution
that they change how the world operates.
And this actually is the premise of CS179.
CS179, called the usable interactive systems,
will be offered for the first time,
kind of on a permanent basis, this spring.
It was offered once before by a visiting faculty.
And this class is not about solving problems.
It's not about understanding problems.
It's about discovering problems.
So the fundamental question
of this class is what is computer science,
and what it's not.
Unfortunately many people,
not you because you wouldn't be here, think of computer science
as something like this.
But this is not what computer science is.
Computer science is an extremely powerful intellectual tool kit
for discovering and solving problems.
And the successes of computer scientists depends not only
on how well you can solve the problems,
but on what problems you solve.
And in CS170 we'll precisely focus
on this entire lifecycle of innovation.
In CS179 you will learn how to discover
that there exists a problem, a powerful problem,
a problem that if you solved it could change people's lives.
You will learn how to invent solutions.
And when we invent solutions to problems
that we've just discovered, it's not just
about writing codes to specification.
It's figuring out what aspects
of the problem are actually important.
It's figuring out who the stakeholders are
and whose needs you should address first.
It's about figuring out what you need to do in order
for your solution to actually be sustainable and productive.
An extremely important skill that you will learn in CS179 is
that you are not an average person,
which is actually a terrible handicap because it means
that you have no idea what normal people think.
When we design solutions we design for different people.
We design for people who love control.
We design solutions for people who like to tweek.
But this is not what other people like to do,
and we will actually learn about our own biases and what makes...
and how we can overcome them.
We'll also learn how to formally
and informally evaluate our ideas, and actually a big part
of the class is going to be critique sessions.
Once a week we are going to meet in small groups,
present our contributions for the week, and other students
in that small group will actually present formative
critiques of whatever progress you and your group made
to help you improve your system.
One of the greatest assets that we have as innovators,
is other innovators, other people
who understand the innovation process
and who can offer useful feedback
that can help shape your solutions.
And finally this class will be about teamwork.
All of the projects will be done in teams of 3,
and the projects will last most of the semester
with a couple of short breaks.
So on the practical side, the main prerequisite
for this class is CS50 or any kind of programming experience.
We will be using...
the specific programming skills that you will need
to be successful in this class.
We'll let you cover in the class all you need to know,
is how to think like a programmer.
Lectures will be twice a week.
We'll have critique sessions,
and we'll have regular weekday assignments.
There may be final exam.
I haven't decided yet.
An exciting thing is, Apple has offered to lend us iPod Touchs.
Every team of 3 will have their own iPod Touch,
and iPod Touch web development will give the platform
that we'll use for innovating and discuss.
Any questions?
OK. I will see you in the spring of 2010.
[ Applause ]
>> So I thought I'd leave you guys with 1 thought.
So truth be told, I think there's something very
empowering about studying computer science.
And I say this having defected from gov long ago.
I can think of enumerable experiences,
just in the real world with this background I had;
not just in 50, but in networking courses
and in theory courses, where I actually realized very quickly I
understand better what this person I'm talking
to is actually talking about.
So case in point, Comcast is my, was for years,
my cable modem provider.
And every night around like 9 p.m. I would just lose internet
connectivity altogether,
and this happened again and again and again.
And I talked to so many damn representatives on the phone
about this pattern, and of course the irony there being
such a big company, oh sir we can send someone
out between 9 a.m. and 5 p.m. everyday.
But it only happens after 5 p.m. and so I hypothesized for them
on the phone, you know maybe this has to do
with some real world usage patterns.
Right? A lot of my neighbors come home around 7 p.m.,
8 p.m. Perhaps this is putting more
of a load on your equipment.
No, no, no, no.
It looks fine right now sir, at 9 a.m. in the morning.
And long story short, this sort of instinctive understanding
of how routers work and how local hardware
and electronics work, helped me realize maybe there was
something a little more to it then.
Cisco, for instance, is a very popular company
that makes really expensive
and really high powered routers and switches.
And in my consulting life some months ago,
we had just deployed this real world Cisco switch,
a Cisco firewall actually.
And I'd never used these things before.
A lot of the stuff was over my head.
The documentation's like this thick, but I knew from CS143,
networking, you know, how a router is supposed to work,
how a firewall is supposed to work.
And there too this firewall, brand new out of the box,
installed by very expensive consultants, was crashing
on us again and again everyday.
And frankly I whipped out my CS50 skills SSH into this thing,
because it's really just a Unix computer that's running,
and found all of these core files
which I really didn't understand but I knew
from my time 10 years ago weren't necessarily a
good thing.
And sure enough the firmware, the software running
on this Cisco, very expensive switch, was just buggy.
Cisco had screwed up, and the thing was seg faulting once a
night around a particular time.
But it was these instincts,
being able to solve these problems myself and being able
to identify problems,
as Krzysztof has mentioned there, in the real world.
It's like wow, wouldn't it be great
if we had this Twitter agregator.
Why? Not because it's terribly useful, but because we can.
And that's the sense of empowerment that I got from all
of these computer science courses I got.
And whether you're considering majoring or minoring,
or just dabbling in computer science, hopefully you gather
from the faculty who joined us today,
that there's many different directions
in which you guys can go after this.
So I hope you will join us next semester on Wednesday
for quiz 1, and also on Monday for our final class.
See you on Wednesday!
[ Music ]