anybody didn't pick one up. My name is Charles Leiserson.

I will be lecturing this course this term, Introduction to

Algorithms, with Erik Demaine. In addition,

this is an SMA course, a Singapore MIT Alliance course

which will be run in Singapore by David Hsu.

And so all the lectures will be videotaped and made available on

the Web for the Singapore students, as well as for MIT

students who choose to watch them on the Web.

If you have an issue of not wanting to be on the videotape,

you should sit in the back row. OK?

Otherwise, you will be on it. There is a video recording

policy, but it seems like they ran out.

If anybody wants to see it, people, if they could just sort

of pass them around maybe a little bit, once you're done

reading it, or you can come up. I did secure one copy.

Before we get into the content of the course,

let's briefly go over the course information because there

are some administrative things that we sort of have to do.

As you can see, this term we have a big staff.

Take a look at the handout here.

Including this term six TAs, which is two more TAs than we

normally get for this course. That means recitations will be

particularly small. There is a World Wide Web page,

and you should bookmark that and go there regularly because

that is where everything will be distributed.

Email. You should not be emailing

directly to, even though we give you our email addresses,

to the individual members of the staff.

You should email us generally. And the reason is you will get

much faster response. And also, for any

communications, generally we like to monitor

what the communications are so it's helpful to have emails

coming to everybody on the course staff.

As I mentioned, we will be doing distance

learning this term. And so you can watch lectures

online if you choose to do that. I would recommend,

for people who have the opportunity to watch,

to come live. It's better live.

You get to interact. There's an intangible that

comes with having it live. In fact, in addition to the

videos, I meet weekly with the Singapore students so that they

have a live session as well. Prerequisites.

The prerequisites for this course are 6.042,

which is Math for Computer Science, and 6.001.

You basically need discrete mathematics and probability,

as well as programming experience to take this course

successfully. People do not have that

background should not be in the class.

We will be checking prerequisites.

If you have any questions, please come to talk to us after

class. Let's see.

Lectures are here. For SMA students,

they have the videotapes and they will also have a weekly

meeting. Students must attend a one-hour

recitation session each week. There will be new material

presented in the recitation. Unlike the lectures,

they will not be online. Unlike the lectures,

there will not be lecture notes distributed for the recitations

in general. And, yet, there will be

material there that is directly on the exams.

And so every term we say oh, when did you cover that?

That was in recitation. You missed that one.

So, recitations are mandatory. And, in particular,

also let me just mention your recitation instructor is the one

who assigns your final grade. So we have a grade meeting and

keep everybody normal, but your recitation has the

final say on your grade. Handouts.

Handouts are available on the course Web page.

We will not generally, except for this one,

first handout, be bringing handouts to class.

Textbook is this book, Introduction to Algorithms.

MIT students can get it any of the local bookstores,

including the MIT Coop. There is also a new online

service that provides textbooks. You can also get a discount if

you buy it at the MIT Press Bookstore.

There is a coupon in the MIT Student Telephone Directory for

a discount on MIT Press books. And you can use that to

purchase this book at a discount.

Course website. This is the course website.

It links to the Stellar website, which is where,

actually, everything will be kept.

And SMA students have their own website.

Some students find this course particularly challenges so we

will have extra help. We will post weekly office

hours on the course website for the TAs.

And then as an experiment this term, we are going to offer

homework labs for this class. What a homework lab is,

is it's a place and a time you can go where other people in the

course will go to do homework. And there will be typically two

TAs who staff the lab. And so, as you're working on

your homework, you can get help from the TAs

if you need it. And it's generally a place,

we're going to schedule those, and they will be on the course

calendar for where it is and when it is that they will be

held, but usually Sundays 2:00 to 4:00 pm, or else it will be

some evening. I think the first one is an

evening, right? Near to when the homework is

due. Your best bet is try to do the

homework in advance of the homework lab.

But then, if you want extra help, if you want to talk over

your solutions with people because as we will talk about

problem sets you can solve in collaboration with other people

in the class. In addition,

there are several peer assistance programs.

Also the office of Minority Education has an assistance

program, and those usually get booked up pretty quickly.

If you're interested in those, good idea to make an

appointment to get there and get help soon.

The homework labs, I hope a lot of people will try

that out. We've never done this.

I don't know of any other course.

Do other people know of courses at MIT that have done this?

6.011 did it, OK.

Good. And was it successful in that

class? It never went,

OK. Good.

[LAUGHTER] We will see. If it's not paying off then we

will just return to ordinary office hours for those TAs,

but I think for some students that is a good opportunity.

If you wish to be registered in this course, you must sign up on

the course Web page. So, that is requirement one.

It must be done today. You will find it difficult to

pass the course if you are not in the class.

And you should notify your TA if you decide to drop so that we

can get you off and stop the mailings, stop the spam.

And you should register today before 7:00 PM.

And then we're going to email your recitation assignment to

you before Noon tomorrow. And if you don't receive this

information by Thursday Noon, please send us an email to the

course staff generally, not to me individually,

saying that you didn't receive your recitation assignment.

And so if you haven't received it by Thursday Noon you want to.

I think generally they are going to send them out tonight

or at least by tomorrow morning. Yeah.

OK. SMA students don't have to

worry about this. Problem sets.

We have nine problem sets that we project will be assigned

during the semester. A couple things about problem

sets. Homeworks won't generally be

accepted, if you have extenuating circumstances you

should make prior arrangements with your recitation instructor.

In fact, almost all of the administrative stuff,

you shouldn't come to me to ask and say can I hand in something

late? You should be talking to your

recitation instructor. You can read the other things

about the form, but let me just mention that

there are exercises that should be solved but not handed in as

well to give you drill on the material.

I highly recommend you doing the exercises.

They both test your understanding of the material,

and exercises have this way of finding themselves on quizzes.

You're often asked to describe algorithms.

And here is a little outline of what you can use to describe an

algorithm. The grading policy is something

that somehow I cover. And always every term there are

at least a couple of students who pretend like I never showed

them this. If you skip problems it has a

nonlinear effect on your grade. Nonlinear, OK?

If you don't skip any problems, no effect on your grade.

If you skip one problem, a hundredth of a letter grade,

we can handle that. But two problems it's a tenth.

And, as you see, by the time you have skipped

like five letter grades, it is already five problems.

This is not problem sets, by the way.

This is problems, OK?

You're down a third of a letter grade.

And if you don't do nine or more, so that's typically about

three to four problem sets, you don't pass the class.

I always have some students coming at the end of the year

saying oh, I didn't do any of my problems.

Can you just pass me because I did OK on the exams?

Answer no, a very simple answer because we've said it upfront.

So, the problem sets are an integral part of the course.

Collaboration policy. This is extremely important so

everybody pay attention. If you are asleep now wake up.

Like that's going to wake anybody up, right?

[LAUGHTER] The goal of homework.

Professor Demaine and my philosophy is that the goal of

homework is to help you learn the material.

And one way of helping to learn is not to just be stuck and

unable to solve something because then you're in no better

shape when the exam roles around, which is where we're

actually evaluating you. So, you're encouraged to

collaborate. But there are some commonsense

things about collaboration. If you go and you collaborate

to the extent that all you're doing is getting the information

from somebody else, you're not learning the

material and you're not going to do well on the exams.

In our experience, students who collaborate

generally do better than students who work alone.

But you owe it to yourself, if you're going to work in a

study group, to be prepared for your study group meeting.

And specifically you should spend a half an hour to 45

minutes on each problem before you go to group so you're up to

speed and you've tried out your ideas.

And you may have solutions to some, you may be stuck on some

other ones, but at least you applied yourself to it.

After 30 to 45 minutes, if you cannot get the problem,

just sitting there and banging your head against it makes no

sense. It's not a productive use of

your time. And I know most of you have

issues with having time on your hands, right?

Like it's not there. So, don't go banging your head

against problems that are too hard or where you don't

understand what's going on or whatever.

That's when the study group can help out.

And, as I mentioned, we'll have homework labs which

will give you an opportunity to go and do that and coordinate

with other students rather than necessarily having to form your

own group. And the TAs will be there.

If your group is unable to solve the problem then talk to

other groups or ask your recitation instruction.

And, that's how you go about solving them.

Writing up the problem sets, however, is your individual

responsibility and should be done alone.

You don't write up your problem solutions with other students,

you write them up on your own. And you should on your problem

sets, because this is an academic place,

we understand that the source of academic information is very

important, if you collaborated on solutions you should write a

list of the collaborators. Say I worked with so and so on

this solution. It does not affect your grade.

It's just a question of being scholarly.

It is a violation of this policy to submit a problem