Placeholder Image

Subtitles section Play video

  • We're going to get started. Handouts are the by the door if

  • 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.