online colleges and universities

the following content isprovided under a creative commons license. your support will help mitopencourseware continue to offer high-quality educationalresources for free. to make a donation, or viewadditional materials from hundreds of mit courses, visitmit opencourseware, at . professor: good morning. try it again.

good morning. students: good morning. professor: thank you. this is 6.00, also known asintroduction to computer science and programming. my name is eric grimson, i havetogether professor john guttag over here, we'regoing to be lecturing the course this term. i want to give you a heads up;you're getting some serious

firepower this term. john was department head forten years, felt like a century, and in course six,i'm the current department head in course six. john's been lecturing forthirty years, roughly. all right, i'm the young guy,i've only been lecturing for twenty-five years. you can tell, i have lessgrey hair than he does. what i'm trying to say toyou is, we take this

course really seriously. we hope you do as well. but we think it's reallyimportant for the department to help everybody learn aboutcomputation, and that's what this course is about. what i want to do today is threethings: i'm going to start-- actually, i shouldn'tsay start, i'm going to do a little bit of administrivia, thekinds of things you need to know about how we're goingto run the course.

i want to talk about the goalof the course, what it is you'll be able to do at the endof this course when you get through it, and then i wantto begin talking about the concepts and tools ofcomputational thinking, which is what we're primarily goingto focus on here. we're going to try and help youlearn how to think like a computer scientist, and we'regoing to begin talking about that towards the end of thislecture and of course throughout the rest of thelectures that carry on.

right, let's startwith the goals. i'm going to give yougoals in two levels. the strategic goals are thefollowing: we want to help prepare freshmen and sophomoreswho are interested in majoring in course six toget an easy entry into the department, especially for thosestudents who don't have a lot of prior programmingexperience. if you're in that category,don't panic, you're going to get it.

we're going to help you rampin and you'll certainly be able to start the course sixcurriculum and do just fine and still finish on target. we don't expect everybody tobe a course six major, contrary to popular opinion,so for those are you not in that category, the second thingwe want to do is we want to help students who don't planto major in course six to feel justifiably confident intheir ability to write and read small pieces of code.

for all students, what we wantto do is we want to give you an understanding of the rolecomputation can and cannot play in tackling technicalproblems. so that you will come away with a sense of whatyou can do, what you can't do, and what kinds of things youshould use to tackle complex problems. and finally, we want to positionall students so that you can easily, if you like,compete for things like your office and summer jobs.

because you'll have anappropriate level of confidence and competencein your ability to do computational problem solving. those are the strategic goals. now, this course is primarilyaimed at students who have little or no prior programmingexperience. as a consequence, we believethat no student here is under-qualified for thiscourse: you're all mit students, you're all qualifiedto be here.

but we also hope that therearen't any students here who are over-qualifiedfor this course. and what do i mean by that? if you've done a lot priorprogramming, this is probably not the best course for you,and if you're in that category, i would pleaseencourage you to talk to john or i after class about what yourgoals are, what kind of experience you have, and howwe might find you a course that better meets your goals.

second reason we don't wantover-qualified students in the class, it sounds a little nasty,but the second reason is, an over-qualified student,somebody who's, i don't know, programmed for google for thelast five years, is going to have an easy time in thiscourse, but we don't want such a student accidentallyintimidating the rest of you. we don't want you to feelinadequate when you're simply inexperienced. and so, it really is a courseaimed at students with little

or no prior programmingexperience. and again, if you're not in thatcategory, talk to john or i after class, and we'll helpyou figure out where you might want to go. ok. those are the top-levelgoals of the course. let's talk sort of at a moretactical level, about what do we want you to knowin this course. what we want you to be ableto do by the time

you leave this course? so here are the skills that wewould like you to acquire. right, the first skill we wantyou to acquire, is we want you to be able to use the basictools of computational thinking to write small scaleprograms. i'm going to keep coming back to that idea,but i'm going to call it computational thinking. and that's so you can writesmall pieces of code. and small is not derogatoryhere, by the way, it just says

the size of things you'regoing to be able to do. second skill we want you to haveat the end of this course is the ability to use avocabulary of computational tools in order to beable to understand programs written by others. so you're going to be ableto write, you're going to be able to read. this latter skill, by the way,is incredibly valuable. because you won't want to doeverything from scratch

yourself, you want to be ableto look at what is being created by somebody else andunderstand what is inside of there, whether it workscorrectly and how you can build on it. this is one of thefew places where plagiarism is an ok thing. it's not bad to, if you like,learn from the skills of others in order to createsomething you want to write. although we'll come backto plagiarism as a

bad thing later on. third thing we want you todo, is to understand the fundamental both capabilitiesand limitations of computations, and the costsassociated with them. and that latter statement soundsfunny, you don't think of computations havinglimits, but they do. there're some things thatcannot be computed. we want you to understandwhere those limits are. so you're going to beable to understand

abilities and limits. and then, finally, the lasttactical skill that you're going to get out of this courseis you're going to have the ability to map scientificproblems into a computational frame. so you're going to be able totake a description of a problem and map it intosomething computational. now if you think aboutit, boy, it sounds like grammar school.

we're going to teach you toread, we're going to teach you to write, we're going to teachyou to understand what you can and cannot do, and mostimportantly, we're going to try and give you the startof an ability to take a description of a problem fromsome other domain, and figure out how to map it into thatdomain of computation so you can do the reading and writingthat you want to do. ok, in a few minutes we're goingto start talking then about what is computation, howare we going to start building

those tools, but that's what youshould take away, that's what you're going to gain outof this course by the time you're done. now, let me take a sidebar forabout five minutes to talk about course administration, theadministrivia, things that we're going to do in the course,just so you know what the rules are. right, so, class is two hoursof lecture a week. you obviously know whereand you know when,

because you're here. tuesdays and thursdaysat 11:00. one hour of recitation a week,on fridays, and we'll come back in a second to how you'regoing to get set up for that. and nine hours a week ofoutside-the-class work. those nine hours are going tobe primarily working on problem sets, and all theproblems sets are going to involve programming in python,which is the language we're going to be using this term.

now, one of the things you'regoing to see is the first problem sets are pretty easy. actually, that's probablywrong, john, right? they're very easy. and we're going to ramp up. by the time you get to the endof the term, you're going to be dealing with some fairlycomplex things, so one of the things you're going to see is,we're going to make heavy use of libraries, or codewritten by others.

it'll allow you to tackleinteresting problems i'll have you to write from scratch, butit does mean that this skill here is going to bereally valuable. you need to be able to read thatcode and understand it, as well as write your own. two quizzes. during the term, the dates havealready been scheduled. john, i forgot to look them up,i think it's october 2nd and november 4th, it'll beon the course website.

my point is, go check the coursewebsite, which by the way is right there. if you have, if you know youhave a conflict with one of those quiz dates now, pleasesee john or i right away. we'll arrange somethingahead of time. but if you-- the reason i'm saying that is,you know, you know that you're getting married that day forexample, we will excuse you from the quiz to get married.

we'll expect you come rightback to do the quiz by the way, but the-- boy, tough crowd. all right. if you have a conflict,please let us know. second thing is, if you have anmit documented special need for taking quizzes, please seejohn or i well in advance. at least two weeksbefore the quiz. again, we'll arrange for this,but you need to give us enough

warning so that we candeal with that. ok, the quizzes are open book. this course is notabout memory. it's not how well you canmemorize facts: in fact, i think both john and i are alittle sensitive to memory tests, given our age,right john? this is not about how youmemorize things, it's about how you think. so they're open note,open book.

it's really going to testyour ability to think. the grades for the course willbe assigned roughly, and i use the word roughly because wereserve the right to move these numbers around a littlebit, but basically in the following percentages: 55% ofyour grade comes from the problem sets, the other 45%come from the quizzes. and i should've said there's twoquizzes and a final exam. i forgot, that final examduring final period. so the quiz percentagesare 10%, 15%, and 20%.

which makes up the other 45%. other administrivia. let me just look throughmy list here. first problem set, problem setzero, has already been posted. this is a really easy one. we intend it to be a reallyeasy problem set. it's basically to get you toload up python on your machine and make sure you understandhow to interact with it. the first problem set will beposted shortly, it's also

pretty boring-- somewhat likemy lectures but not john's-- and that means, you know,we want you just to get going on things. don't worry, we're going to makethem more interesting as you go along. nonetheless, i want to stressthat none of these problems sets are intendedto be lethal. we're not using them to weed youout, we're using them to help you learn.

so if you run into a problemset that just, you don't get, all right? seek help. could be psychiatric help,could be a ta. i recommend the ta. my point being, please comeand talk to somebody. the problems are set up so that,if you start down the right path, it should be prettystraight-forward to work it through.

if you start down a plausiblebut incorrect path, you can sometimes find yourself stuck inthe weeds somewhere, and we want to bring you back in. so part of the goal here is,this should not be a grueling, exhausting kind of task, it'sreally something that should be helping you learnthe material. if you need help, ask john,myself, or the tas. that's what we're here for. we're going to run primarily apaperless subject, that's why

the website is there. please check it, that's whereeverything's going to be posted in terms of thingsyou need to know. in particular, please go to ittoday, you will find a form there that you need to fill outto register for, or sign up for rather, a recitation. recitations are on friday. right now, we have themscheduled at 9:00, 10:00, 11:00, 12:00, 1:00, and 2:00.

we may drop one of therecitations, just depending on course size, all right? so we reserve the right,unfortunately, to have to move you around. my guess is that 9:00 is notgoing to be a tremendously popular time, but maybeyou'll surprise me. nonetheless, pleasego in and sign up. we will let you sign up forwhichever recitation makes sense for you.

again, we reserve the right tomove people around if we have to, just to balance load, but wewant you to find something that fits your schedulerather than ours. other things. there is no required text. if you feel exposed without atext book, you really have to have a textbook, you'll find onerecommended-- actually i'm going to reuse that word, john,at least suggest it, on the course website.

i don't think either of us arethrilled with the text, it's the best we've probably foundfor python, it's ok. if you need it, it's there. but we're going to basically notrely on any specific text. right. related to that: attendancehere is obviously not mandatory. you ain't in highschool anymore. i think both of us would love tosee your smiling faces, or

at least your faces,even if you're not smiling at us every day. point i want to make about this,though, is that we are going to cover a lot of materialthat is not in the assigned readings, and we dohave assigned readings associated with each oneof these lectures. if you choose not to show uptoday-- or sorry, you did choose to show up today, if youchoose not to show up in future days-- we'll understand,but please also

understand that the tas won'thave a lot of patience with you if you're asking a questionabout something that was either covered in thereadings, or covered in the lecture and is prettystraight forward. all right? we expect you to behaveresponsibly and we will as well. i think the last thing i wantto say is, we will not be handing out class notes.

now this sounds like adraconian measure; let me tell you why. every study i know of, and isuspect every one john knows, about learning, stresses thatstudents learn best when they take notes. ironically, even if theynever look at them. the process of writing isexercising both halves of your brain, and it's actually helpingyou learn, and so taking notes is reallyvaluable thing.

therefore we're not goingto distribute notes. what we will distribute formost lectures is a handout that's mostly code examplesthat we're going to do. i don't happen to have one todaybecause we're not going to do a lot of code. we will in future. those notes are going to makeno sense, i'm guessing, outside of the lecture,all right? so it's not just, you can swingby 11:04 and grab a copy

and go off and catchsome more sleep. what we recommend is you usethose notes to take your own annotations to help youunderstand what's going on, but we're not going toprovide class notes. we want you to take your ownnotes to help you, if you like, spur your ownlearning process. and then finally, i want tostress that john, myself, all of the staff, our job isto help you learn. it's what we getexcited about.

if you're stuck, if you'restruggling, if you're not certain about something,please ask. we're not mind readers, wecan't tell when you're struggling, other than sort ofseeing the expression on your face, we need your helpin identifying that. but all of the tas, many of whomare sitting down in the front row over here, are hereto help, so come and ask. at the same time, remember thatthey're students too. and if you come and ask aquestion that you could have

easily answered by doing thereading, coming to lecture, or using google, they're goingto have less patience. but helping you understandthings that really are a conceptual difficulty is whatthey're here for and what we're here for, so pleasecome and talk to us. that takes care of theadministrivia preamble. john, things we add? professor guttag: twomore quick things. this semester, your classis being videotaped for

opencourseware. if any of you don't want yourimage recorded and posted on the web, you're supposed to sitin the back three rows. professor grimson:ah, thank you. i forgot. professor guttag: --becausethe camera may pan. i think you're all verygood-looking and give mit a good image, so please, feelfree to be filmed. professor grimson: i'll turnaround, so if you want to, you

know, move to the back,i won't see who moves. great. thank you, john. professor guttag: so that, theother thing i want to mention is, recitations are alsovery important. we will be covering material inrecitations that're not in the lectures, not in thereading, and we do expect you to attend recitations. professor grimson: great.

thanks, john. any questions aboutthe administrivia? i know it's boring, but we needto do it so you know what the ground rules are. good. let's talk about computation. as i said, our strategic goal,our tactical goals, are to help you think like a computerscientist. another way of saying it is, we want to giveyou the skill so that you can

make the computer do whatyou want it to do. and we hope that at the end ofthe class, every time you're confronted with some technicalproblem, one of your first instincts is going to be, "howdo i write the piece of code that's going to helpme solve that?" so we want to help youthink like a computer scientist. all right. and that, is an interestingstatement. what does it mean, to thinklike a computer scientist?

well, let's see. the primary knowledge you'regoing to take away from this course is this notion ofcomputational problem solving, this ability to think in computational modes of thought. and unlike in a lot ofintroductory courses, as a consequence, having the abilityto memorize is not going to help you. it's really learning thosenotions of the tools that you

want to use. what in the world doesit mean to say computational mode of thought? it sounds like a hifalutinphrase you use when you're trying to persuadea vc to fund you. so to answer this, we reallyhave to ask a different question, a related question;so, what's computation? it's like a strangestatement, right? what is computation?

and part of the reason forputting it up is that i want to, as much as possible,answer that question by separating out the mechanism,which is the computer, from the artifact should not bewhat's driving this. it should be the notion of,"what does it mean to do computation?" now, to answer that, i'm goingto back up one more level. and i'm going to pose whatsounds like a philosophy question, which is, "what isknowledge?" and you'll see in

about two minutes why i'mgoing to do this. but i'm going to suggest that ican divide knowledge into at least two categories. ok, and what is knowledge? and the two categories i'm goingto divide them into are declarative and imperativeknowledge. what in the world is declarativeknowledge? think of it as statementsof fact. it's assertions of truth.

boy, in this political season,that's a really dangerous phrase to use, right? but it's a statement of fact. i'll stay away from thepolitical comments. let me give you anexample of this. here's a declarativestatement. the square root of x is that ysuch that y squared equals x, y's positive. you all know that.

but what i want you tosee here, is that's a statement of fact. it's a definition. it's an axiom. it doesn't help youfind square roots. if i say x is 2, i want to know,what's the square root of 2, well if you're enough ofa geek, you'll say 1.41529 or whatever the heck it is, but ingeneral, this doesn't help you find the square root.

the closest it does is it wouldlet you test. you know, if you're wandering throughharvard square and you see an out-of-work harvard grad,they're handing out examples of square roots, they'll giveyou an example and you can test it to see, is thesquare root of 2, 1.41529 or whatever. i don't even get laughs atharvard jokes, john, i'm going to stop in a secondhere, all right? all right, so what am itrying to say here?

it doesn't -- yeah, exactly. we're staying away from that,really quickly, especially with the cameras rolling. what am i trying to say? it tells you how you might testsomething but it doesn't tell you how to. and that's what imperativeknowledge is. imperative knowledgeis a description of how to deduce something.

so let me give you anexample of a piece of imperative knowledge. all right, this is actually avery old piece of imperative knowledge for computing squareroots, it's attributed to heron of alexandria, although ibelieve that the babylonians are suspected of knowingit beforehand. but here is a piece ofimperative knowledge. i'm going to start with a guess,i'm going to call it g. and then i'm going to say, if gsquared is close to x, stop.

and return g. it's a good enough answer. otherwise, i'm going to get anew guess by taking g, x over g, adding them, anddividing by two. then you take the averageof g and x over g. don't worry about how cameabout, heron found this out. but that gives me a new guess,and i'm going to repeat. that's a recipe. that's a descriptionof a set of steps.

notice what it has, it has abunch of nice things that we want to use, right? it's a sequence of specificinstructions that i do in order. along the way i have some tests,and depending on the value of that test, i may changewhere i am in that sequence of instructions. and it has an end test,something that tells me when i'm done and whatthe answer is.

this tells you how tofind square roots. it's how-to knowledge. it's imperative knowledge. that's what computationbasically is about. we want to have ways ofcapturing this process. ok, and that leads now to aninteresting question, which would be, "how do i build amechanical process to capture that set of computations?" soi'm going to suggest that there's an easy way to do it--

i realized i did the boards inthe wrong order here-- one of the ways i could do it is, youcould imagine building a little circuit to do this. if i had a couple of elements ofstored values in it, i had some wires to move thingsaround, i had a little thing to do addition, little thingto do division, and a something to do the testing, icould build a little circuit that would actually dothis computation. that, strange as it sounds, isactually an example of the

earliest computers, because theearliest computers were what we call fixed-programcomputers, meaning that they had a piece of circuitrydesigned to do a specific computation. and that's what they would do:they would do that specific you've seen thesea lot, right? a good example of this:calculator. it's basically an example ofa fixed-program computer. it does arithmetic.

if you want play video gameson it, good luck. if you want to do wordprocessing on it, good luck. it's designed to doa specific thing. it's a fixed-program computer. in fact, a lot of the otherreally interesting early ones similarly have this flavor, togive an example: i never know how to pronounce this,atanasoff, 1941. one of the earliestcomputational things was a thing designed by a guy namedatanasoff, and it basically

solved linear equations. handy thing to do if you'redoing 1801, all right, or 1806, or whatever you wantto do those things in. all it could do, though, wassolve those equations. one of my favorite examples ofan early computer was done by alan turing, one of the greatcomputer scientists of all time, called the bombe, whichwas designed to break codes. it was actually used duringwwii to break german enigma codes.

and what it was designedto do, was to solve that specific problem. the point i'm trying to make is,fixed-program computers is where we started, but it doesn'treally get us to where we'd like to be. we want to capture this ideaof problem solving. so let's see howwe'd get there. so even within this frameworkof, given a description of a computation as a set of steps,in the idea that i could build

a circuit to do it, let mesuggest for you what would be a wonderful circuit to build. suppose you could build acircuit with the following property: the input to thiscircuit would be any other circuit diagram. give it a circuit diagram forsome computation, you give it to the circuit, and that circuitwould wonderfully reconfigure itself to act likethe circuits diagram. which would mean, it couldact like a calculator.

or, it could act liketuring's bombe. or, it could act like asquare root machine. so what would that circuitlook like? you can imagine these tinylittle robots wandering around, right? pulling wires and pullingout components and stacking them together. how would you build a circuitthat could take a circuit diagram in and make a machineact like that circuit?

sounds like a neat challenge. let me change thegame slightly. suppose instead, i want amachine that can take a recipe, the description of asequence of steps, take that as its input, and then thatmachine will now act like what is described in that recipe. reconfigure itself, emulate it,however you want to use the words, it's going tochange how it does the that would be cool.

and that exists. it's called an interpreter. it is the basic heartof every computer. what it is doing, is saying,change the game. this is now an example of astored-program computer. what that means, in astored-program computer, is that i can provide to thecomputer a sequence of instructions describing theprocess i want it to execute. and inside of the machine, andthings we'll talk about, there

is a process that will allowthat sequence to be executed as described in that recipe,so it can behave like any thing that i can describein one of those recipes. that actually seems like areally nice thing to have, and so let me show you what thatwould basically look like. inside of a stored-programcomputer, we would have the following: we have a memory,it's connected to two things; control unit, in what's calledan alu, an arithmetic logic unit, and this can take ininput, and spit out output,

and inside this stored-programcomputer, excuse me, you have the following: you have asequence of instructions. and these all getstored in there. notice the difference. the recipe, the sequence ofinstructions, is actually getting read in, and it'streated just like data. it's inside the memory of themachine, which means we have access to it, we can change it,we can use it to build new pieces of code, as well aswe can interpret it.

one other piece that goesinto this computer-- i never remember where to putthe pc, john, control? alu? separate? i'll put it separate--you have a thing called a program counter. and here's the basisof the computation. that program counter points tosome location in memory, typically to the firstinstruction in the sequence.

and those instructions, by theway, are very simple: they're things like, take the value outof two places in memory, and run them through themultiplier in here, a little piece of circuitry, andstick them back into someplace in memory. or take this value out ofmemory, run it through some other simple operation, stickit back in memory. having executed thisinstruction, that counter goes up by one and we moveto the next one.

we execute that instruction,we move to the next one. oh yeah, it looks a wholelot like that. some of those instructions willinvolve tests: they'll say, is something true? and if the test is true, it willchange the value of this program counter to point tosome other place in the memory, some other point in thatsequence of instructions, and you'll keep processing. eventually you'll hopefullystop, and a value gets spit

out, and you're done. that's the heartof a computer. now that's a slightmisstatement. the process to control it isintriguing and interesting, but the heart of the computer issimply this notion that we build our descriptions, ourrecipes, on a sequence of primitive instructions. and then we have aflow of control. and that flow of control iswhat i just described.

it's moving through a sequenceof instructions, occasionally changing where we areas we move around. the thing i want you to takeaway from this, then, is to think of this as, this is,if you like, a recipe. and that's really whata program is. it's a sequence ofinstructions. now, one of things i lefthanging is, i said, ok, you build it out of primitives. so one of the questions is,well, what are the right

primitives to use? and one of the things that wasuseful here is, that we actually know that the set ofprimitives that you want to use is very straight-forward. ok, but before i do that, let medrive home this idea of why this is a recipe. assuming i have a set ofprimitive instructions that i can describe everything on, iwant to know what can i build. well, i'm going to do the sameanalogy to a real recipe.

so, real recipe. i don't know. separate six eggs. do something. beat until the-- sorry,beat the whites until they're stiff. do something until anend test is true. take the yolks and mix them inwith the sugar and water-- no.

sugar and flour i guess isprobably what i want, sugar and water is not going to doanything interesting for me here-- mix them intosomething else. do a sequence of things. a traditional recipe actuallyis based on a small set of primitives, and a good chefwith, or good cook, i should say, with that set ofprimitives, can create an unbounded number ofgreat dishes. same thing holds truein programming.

given a fixed set of primitives,all right, a good programmer can programanything. and by that, i mean anythingthat can be described in one of these process, you cancapture in that set of primitives. all right, the question is, asi started to say, is, "what are the right primitives?" sothere's a little bit of, a little piece of historyhere, if you like. in 1936, that same guy, alanturing, showed that with six

simple primitives, anything thatcould be described in a mechanical process, it'sactually algorithmically, could be programmed just usingthose six primitives. think about that for a second. that's an incrediblestatement. it says, with six primitives,i can rule the world. with six primitives, ican program anything. a couple of really interestingconsequences of that, by the way, one of them is, it says,anything you can do in one

programming language,you can do in another programming language. and there is no programminglanguage that is better-- well actually, that's not quite true,there are some better at doing certain kinds of things--but there's nothing that you can do in c thatyou can't do in fortran. it's called turingcompatibility. anything you can do with one,you can do with another, it's based on that fundamentalresult.

now, fortunately we're not goingto start with turing's six primitives, this would bereally painful programming, because they're down at thelevel of, "take this value and write it onto this tape." firstof all, we don't have tapes anymore in computers, andeven if we did, you don't want to be programmingat that level. what we're going to see withprogramming language is that we're going to use higher-levelabstracts. a broader set of primitives,but nonetheless the same

fundamental thing holds. with those six primitives,you can do it. so where are we here? what we're saying is, in orderto do computation, we want to describe recipes, we want todescribe this sequence of steps built on some primitives,and we want to describe the flow of controlthat goes through those sequence of stepsas we carry on. so the last thing we need beforewe can start talking

about real programmingis, we need to describe those recipes. all right, and to describethe recipes, we're going to want a language. we need to know not only whatare the primitives, but how do we make things meaningfulin that language. language. there we go. now, it turns out there are--

i don't know, john, hundreds? thousands? of programming languages? at least hundreds-- ofprogramming languages around. professor john guttag:[unintelligible] professor eric grimson: true. thank you. you know, they allhave, you know, their pluses and minuses.

i have to admit, in my careerhere, i think i've taught in at least three languages, isuspect you've taught more, five or six, john? both of us have probablyprogrammed in more than those number of languages, at leastprogrammed that many, since we taught in those languages. one of the things youwant to realize is, there is no best language. at least i would argue that,i think john would agree.

we might both agree we haveour own nominees for worst language, there aresome of those. there is no best language. they all are describingdifferent things. having said that, some of themare better suited for some things than others. anybody here heard of matlabmaybe programmed in matlab? it's great for doing things withvectors and matrices and things that are easily capturedin that framework.

but there's some thingsthat are a real pain to do in matlab. so matlab's great forthat kind of thing. c is a great language forprogramming things that control data networks,for example. i happen to be, and johnteases me about this regularly, i'm an old-time lispprogrammer, and that's how i was trained. and i happen to like lisp andscheme, it's a great language

when you're trying to deal withproblems where you have arbitrarily structureddata sets. it's particularlygood at that. so the point i want to makehere is that there's no particularly best language. what we're going to do is simplyuse a language that helps us understand. so in this course, thelanguage we're going to use is python.

which is a pretty new language,it's growing in popularity, it has a lot ofthe elements of some other languages because it's morerecent, it inherits things from it's pregenitors,if you like. but one of the things i want tostress is, this course is not about python. strange statement. you do need to know how to useit, but it's not about the details of, where do thesemi-colons go in python.

it's about using it to think. and what you should take awayfrom this course is having learned how to design recipes,how to structure recipes, how to do things in modesin python. those same toolseasily transfer to any other language. you can pick up another languagein a week, couple of weeks at most, once youknow how to do python. in order to talk about pythonand languages, i want to do

one last thing to set the stagefor what we're going to do here, and that's to talkabout the different dimensions of a language. and there're three iwant to deal with. the first one is, whetherthis is a high-level or low-level language. that basically says,how close are you the guts of the machine? a low-level language, we usedto call this assembly

programming, you're down at thelevel of, your primitives are literally moving pieces ofdata from one location of memory to another, througha very simple operation. a high-level language, thedesigner has created a much richer set of primitivethings. in a high-level language, squareroot might simply be a primitive that you can use,rather than you having to go over and code it. and there're trade-offsbetween both.

second dimension is, whetherthis is a general versus a targeted language. and by that i mean, do the setof primitives support a broad range of applications, or isit really aimed at a very specific set of applications? i'd argue that matlab isbasically a targeted language, it's targeted at matrices andvectors and things like that. and the third one i want topoint out is, whether this is an interpreted versusa compiled language.

what that basically saysis the following: in an interpreted language, you takewhat's called the source code, the thing you write, it may gothrough a simple checker but it basically goes to theinterpreter, that thing inside the machine that's going tocontrol the flow of going through each one ofthe instructions, and give you an output. so the interpreter is simplyoperating directly on your code at run time.

in a compiled language, you havean intermediate step, in which you take the source code,it runs through what's called a checker or a compileror both, and it creates what's called object code. and that does two things: one,it helps catch bugs in your code, and secondly it oftenconverts it into a more efficient sequence ofinstructions before you actually go off and run it. and there's trade-offsbetween both.

i mean, an interpreted languageis often easier to debug, because you can still seeyour raw code there, but it's not always as fast. acompiled language is usually much faster in termsof its execution. and it's one of the things youmay want to trade off. in the case of python, it'sa high-level language. i would argue, i think johnwould agree with me, it's basically a general-purposelanguage. it happens to be better suitedfor manipulating strings than

numbers, for example,but it's really a general-purpose language. and it's primarily-- i shouldn't say primarily, itis an interpreted language. ok? as a consequence, it's not asgood as helping debug, but it does let you-- sorry, that's thewrong way of saying-- it's not as good at catching somethings before you run them, it is easier at some timesin debugging as you go

along on the fly. so what does python look like? in order to talk about python--actually, i'm going to do it this way-- we needto talk about how to write things in python. again, you have to let me backup slightly and set the stage. our goal is to build recipes. you're all going to begreat chefs by the time you're done here.

our goal is to take problems andbreak them down into these computational steps, thesesequence of instructions that'll allow us to capturethat process. to do that, we need to describe:not only, what are the primitives, but how do wecapture things legally in that language, and interactwith the computer? and so for that, weneed a language. we're about to start talkingabout the elements of the language, but to do that, wealso need to separate out one

last piece of distinction. just like with a naturallanguage, we're going to separate out syntaxversus semantics. so what's syntax? syntax basically says, what arethe legal expressions in this language? boy, my handwriting isatrocious, isn't it? there's a english sequenceof words. it's not since syntacticallycorrect, right?

it's not a sentence. there's no verb in thereanywhere, it's just a sequence of nouns. same thing in our languages. we have to describe how do youput together legally formed expressions. and as we add constructs to thelanguage, we're going to talk about. second thing we want to talkabout very briefly as we go

along is the semanticsof the language. and here we're going to breakout two pieces; static semantics and full semantics. static semantics basicallysays which programs are meaningful. which expressions make sense. here's an english sentence. it's syntactically correct. right?

noun phrase, verb,noun phrase. i'm not certain it's meaningful,unless you are in the habit of giving yourfurniture personal names. what's the point? again, you can have things thatare syntactically legal but not semantically meaningful,and static semantics is going to be a wayof helping us decide what expressions, what pieces ofcode, actually have real meaning to it.

the last piece of it is, inaddition to having static semantics, we have sortof full semantics. which is, what doesthe program mean? or, said a different way,what's going to happen when i run it? that's the meaning ofthe expression. that's what you want. you want to know, what's themeaning of this piece of code? when i run it, what'sgoing to happen?

that's what i want to build. the reason for pulling this outis, what you're going to see is, that in most languages,and certainly in python-- we got lots of helphere-- all right, python comes built-in with something thatwill check your static, sorry, your syntax for you. and in fact, as a sidebar, ifyou turn in a problem set that is not syntactically correct,there's a simple button that you push that will checkyour syntax.

if you've turned in a programthat's not syntactically correct, the tas giveyou a zero. because it said you didn't eventake the time to make sure the syntax is correct. the system will helpyou find it. in python, it'll find it,i think one bug at a time, right john? it finds one syntax error ata time, so you have to be a little patient to do it,but you can check that

the syntax is right. you're going to see that weget some help here on the static semantics, and i'm goingto do an example in a second, meaning that the system,some languages are better than others on it, but itwill try and help you catch some things that are notsemantically correct statically. in the case of python, it doesthat i think all at run time. i'm looking to you again,john, i think there's no

pre-time checks. its-- sorry? professor eric grimson:there is some. most of them, i think though,are primarily caught at run time, and that's a little bitof a pain because you don't see it until you go and run thecode, and there are some, actually we're going to see anexample i think in a second where you find it, but youdo get some help there. the problem is, things that youcatch here are actually

the least worrisome bugs. they're easy to spot, you can'trun the program with them there, so you're not goingto get weird answers. not everything is goingto get caught in static semantics checking. some things are going toslide through, and that's actually a bother. it's a problem. because it says, your programwill still give you a value,

but it may not be what youintended, and you can't always tell, and that may propagateit's way down through a whole bunch of other computationsbefore it causes some catastrophic failure. so actually, the problem withstatic semantics is you'd like it to catch everything, youdon't always get it. sadly we don't getmuch help here. which is where we'd like it. but that's part of your job.

what happens if you actuallyhave something that's both syntactically correct, andappears to have correct static semantics, and you run it? it could run and give you theright answer, it could crash, it could loop forever, it couldrun and apparently give you the right answer. and you're not always goingto be able to tell. well, you'll know when itcrashes, that doesn't help you very much, but you can'talways tell whether

something's stuck in an infiniteloop or whether it's simply taking a longtime to compute. you'd love to have a system thatspots that for you, but it's not possible. and so to deal withthis last one, you need to develop style. meaning, we're going to try tohelp you with how to develop good programming style, but youneed to write in a way in which it is going to be easyfor you to spot the places

that cause those semanticbugs to occur. if that sounds like a reallylong preamble, it is. let's start with python. but again, my goal here is tolet you see what computation's about, why we need to do it,i'm going to remind you one last time, our goal is tobe able to have a set of primitives that we combineinto complex expressions, which we can then abstract totreat as primitives, and we want to use that sequence ofinstructions in this flow of

control computing, in orderto deduce new information. that imperative knowledge thatwe talked about right there. so i'm going to start today,we have about five or ten minutes left, i think, inorder-- sorry, five minutes left-- in order to do thiswith some beginnings of python, and we're going to pickthis up obviously, next time, so; simple partsof python. in order to create any kinds ofexpressions, we're going to need values.

primitive data elements. and in python, we have two tostart with; we have numbers, and we have strings. numbers is what you'd expect. there's a number. there's another number. strings are captured in pythonwith an open quote and some sequence of characters followedby a closed quote. associated with every datatype in python is a type,

which identifies the kindof thing it is. some of these are obvious. strings are just a typeon their own. but for numbers, for example,we can have a variety of types. so this is something thatwe would call an integer, or an int. and this is somethingwe would call a floating point, or a float.

or if you want to think ofit as a real number. and there's some othersthat we can see. we're going to build up thistaxonomy if you like, but the reason it's relevant is,associated with each one of those types is a set ofoperators that expect certain types of input in orderto do their job. and given those types of input,will get back output. in order to deal with this, letme show you an example, and i hope that comesup, great.

what i have here is a pythonshell, and i'm going to just show you some simple examplesof how we start building and this'll lead into whatyou're going to see next time as well as what you'regoing to do tomorrow. so. starting with the shell, ican type in expressions. actually, let me back upand do this in video. i can type in a number, i getback a number, i can type in a string, i get back the string.

strings, by the way, can havespaces in them, they can have other characters, it's simplya sequence of things, and notice, by the way, that thestring five-- sorry, the string's digit five digittwo is different than the number 52. the quotes are around themto make that distinction. we're going to seewhy in a second. what i'm doing, by the way, hereis i'm simply typing in expressions to thatinterpreter.

it's using its set of rules todeduce the value and print them back out. things i might like to do inhere is, i might like to do combinations of thingswith these. so we have associated withsimple things, a set of operations. so for numbers, we have thethings you'd expect, the arithmetics. and let me show you someexamples of that.

and actually, i'm going to doone other distinction here. what i typed in, things like--well, let me start this way-- there's an expression. and in python the expressionis, operand, operator, operand, when we're doing simpleexpressions like this, and if i give it to theinterpreter, it gives me back exactly what you'd expect,which is that value. the distinction i'm going tomake is, that's an expression. the interpreter is goingto get a value for it.

when we start buildingup code, we're going to use commands. or statements. which are actually things thattake in a value and ask the computer to do somethingwith it. so i can similarly do this,which is going to look strange because it's going to give methe same value back out, but it actually did a slightlydifferent thing. and notice, by the way, when ityped it how print showed up

in a different color? that's the python saying, thatis a command, that is a specific command to get thevalue of the expression and print it back out. when we start writing code,you're going to see that difference, but for now, don'tworry about it, i just want to plant that idea. once we've got that, wecan certainly, though, do things like this.

notice the quotes around it. and it treats it as a string,it's simply getting me back the value of that string,52 times 7, rather than the value of it. now, once we've got that, wecan start doing things. and i'm going to use printhere-- if i could type, in order to just to get into that,i can't type, here we go-- in order to getinto the habit. i can print out a string.

i can print out-- ah!-- here's a first exampleof something that caught one of my things. this is a staticsemantic error. so what went on here? i gave it an expression thathad an operand in there. it expected arithmetic types. but i gave two strings.

and so it's complaining at me,saying, you can't do this. i don't know how to taketwo strings and multiply them together. unfortunately-- now john you maydisagree with me on this one-- unfortunately in pythonyou can, however, what do you figure that'sgoing to do? look legal? the string three timesthe number three? well it happens to give methree threes in a row.

i hate this. i'm sorry, john, i hate this. because this is overloading thatmultiplication operator with two different tasks. it's saying, if you giveme two numbers, i'll do the right thing. if you give me a number anda string, i'm going to concatenate them together,it's really different operations, but nonetheless,it's what it's going to do.

student: [unintelligible] professor eric grimson:there you go. you know, there will be arebuttal phase a little later on, just like with the politicaldebates, and he likes it as a feature, i don'tlike it, you can tell he's not a lisp programmer and i am. i want to do just a couplemore quick examples. here's another one. ah-ha!

give you an exampleof a syntax error. because 52a doesn'tmake sense. and you might say, wait aminute, isn't that a string, and the answer's no, i didn'tsay it's a string by putting quotes around it. and notice how the machineresponds differently to it. in this case it says, this isa syntax error, and it's actually highlighting whereit came from so i can go back and fix it.

let's do a couple of othersimple examples. i can do multiplication. i've already seen that. i can do addition. three plus five. i can take something to a power,double star, just take three to the fifth power. i can do division, right? whoa.

three divided by five is zero? maybe in bush econom-- no, i'mnot going to do any political comments today, i will notsay that, all right? what happened? well, this is one ofthe places where you have to be careful. it's doing integer division. so, three divided by fiveis zero, with a remainder of three.

so this is the correct answer. if i wanted to get full, realdivision, i should make one of them a float. and yes, you can look at thatand say, well is that right? well, up to some level ofaccuracy, yeah, that's .6 is what i'd like to get out. i can do other things. in a particular, i have similaroperations on strings. ok, i can certainly print outstrings, but i can actually

add strings together, and justas you saw, i can multiply strings, you can kind of guesswhat this is going to do. it is going to merge themtogether into one thing. i want-- i know i'm running you slightlyover, i want to do one last example, it's, i alsowant to be able to do, have variables to store things. and to do that, in this it says,if i have a value, i want to keep it around,to do that, i can

what does that statement do? it says, create a name for avariable-- which i just did there, in fact, let me type itin-- mystring, with an equal sign, which is saying, assign orbind to that name the value of the following expression. as a consequence, ican now refer to that just by its name. if i get the value of mystring,there it is, or if i say, take mystring and add to itthe string, mylastname, and

so this is the firststart of this. what have we done? we've got values, numbersand strings. we have operations toassociate with them. i just threw a couple up here. you're going to get a chanceto explore them, and you'll see not only are there thestandard numerics for strings, there are things like lengthor plus or other things you can do with them.

and once i have values, i wantto get a hold of them so i can give them names. and that's what i just didwhen i bound that. i said, use the name mystringto be bound to or have the value of eric, so i can referto it anywhere else that i want to use it. and i apologize for taking youover, we'll come back to this next time, please go to thewebsite to sign up for recitation for tomorrow.

Online Colleges In NC

let's think about thewaves for the electron. so here i've written outa wave, which is just the same form as the wavesi had for the photon. now let's think a little bitabout the negative energy solutions. if i let the energygo to minus energy, so i turn a positive solutioninto a negative solution. then you see that if ialso take the time to minus

the time, then, thisway it doesn't change. this changes sign, this changessign, nothing changes all together. so what this tellsus, straight away, is that these negative energysolutions are the same thing as if you have an electron. normally, electronstravel forward in time, for the positiveenergy solutions. but here, for thenegative energy solution,

t goes to minus t. so a negative energy solutionis an electron travelling backwards in time. that sounds a little bitlike science fiction, but i'll hope to convinceyou by the end of the lecture that actually, it's not. this is actuallywhat really happens. this is real fact. let's put anexclamation mark there,

because it really is kind of asurprising statement to make. now let's try to write down awave equation for the electron, like we did for the photon. so an equation thatwill give those waves, and give the correctrelation between the energy and the momentum. now, for the electron,we want to be clear about which is thepositive energy piece, and which is the negativeenergy piece, because they're

separate. and so to do that,our wave equation can only have singlederivatives in it. because as soon as wehave two derivatives, then we square everythingand we lose the sign. so if we write down a waveequation for the electron, you might think that you candifferentiate with respect to x. you can differentiatewith respect to time.

if we're only going tohave single derivatives, then it should looksomething like that. then, that will then act onthe electron wave function, since this is the electron,this is presumably the positive energy solution,so i'll put a little plus on it. and let's see what happensif that is equal to zero. well, you remember a d by dxgives you a factor of momentum. d by dt gives youa factor of energy. so this equation tells youthat p is equal to e over c.

so this is indeed thepositive energy solution. and we can write down a negativeenergy one, just the same way, by changing thesign in the middle. that changes thesign of the energy. so this is now thenegative energy solution, and this corresponds top equals minus e over c, because i changed the sign here. now that's still not goodenough for our electron, because the electron has a mass.

and so the tricky thing,is how you get the mass into this equation, sothat everything works out. and the answer, is that -which you find by staring at it for a while - is that youhave to couple these two equations togetherusing the mass. so the equation forthe positive solution, when coupled to thenegative solution, is a factor of the mass (timesa factor of c over hbar, as it turns out) - sothat multiplies psi minus.

and then you do the same thing,couple the negative energy solution to the positiveenergy solution. now, why does this work? well, we have to do alittle bit of algebra. so, to solve this, let'stake this derivative that's acting on the negativesolution and act it on the equation withthe positive solution. so to write that out,i'm going to have d by dx plus 1 over c, d bydt, acting on the whole

of the left-hand side. now, if i do that, if thisacts on the left-hand side, then to keep theequation true, i have to also have this acton the right-hand side. but if this acts onthe right-hand side, this, then that's justwhat we have here, in the second equation. so this, acting onthis, is the same thing (and we have this extrafactor of m c over hbar)

- so if i write thism c over hbar here, then this is actuallyjust equal to this. and since i put an extram c over hbar here, i've got to put one here,to keep everything true. now you see, if wecompare this with this, i have a equationjust for psi plus. now if we look atwhat that equation is, then let's just multiply outthese derivatives on the top. you get a d2 by dx squaredhere, a d2 by dt squared here,

and because thesign is different, the cross terms will cancel. so we wind up with d2by dx squared, minus 1 over c squared,d2 by dt squared, acting on psi plusis equal to the thing that we have here, whichis m c over h-bar squared, acting on psi plus. and actually, if you didthis the other way around, so you started withthe minus equation,

and worked throughthe plus equation, then you would get exactly thesame equation for the minus 1. so this actually workswhether you have psi plus, or whether you havepsi minus there. now, this equation we can solve. the solutions arejust waves, just like they were for the photons. and you rememberfor the photons, when you differentiatewith respect to x,

then you get a factor p squared. when you differentiate thewaves with respect to t, you get a factor of e, sotwice you get e squared. so we get p squared minusone on c squared e squared. and then on the right-hand side,we have m squared, c squared. and that's preciselythe relationship between energy andmomentum that we want for a massiverelativistic particle, so that we wantfor our electrons.

so you can see thatthe whole thing works. the equations that istarted from, here, these linearequations, those then, there are equations for ourelectron wave functions, the positive energy one, andthe negative energy ones. and these equations werefirst discovered by dirac, in 1928 in a very famous paper. so these things are calledthe dirac equations. so, what does all thisactually mean, physically?

what it means, isthat if you have massive relativisticparticles, like electrons - so, if the particles have mass,then besides the positive energy solutions, you must also havethe negative energy solutions. you can't get away fromthem, because they're coupled together like this. so, massive particles,e.g., electrons, imply, immediately,that there must be another sort of particlewhich has the same mass,

but is different. it's the negativeenergy particle. so if we haveelectrons, then we have to have what wecall anti-electrons. this is the negativeenergy solution. so what dirac actuallypredicted here is anti-matter. just by looking atthese wave equations, and looking at making themconsistent with relativity, they have to be wavesbecause of quantum mechanics,

then the only way you canfit those two things together if the particles have mass,is if there's antimatter. so the astonishing thing is thatdirac predicted anti-matter. now, i'd like to emphasise thatthis was a genuine prediction. sometimes when people saythat things are predicted, they really mean explained. so they're predicting somethingthat they already know about. but at the time when dirac didthis calculation, essentially the calculation thatwe've just done,

nobody had a clue that therewas anything like anti-matter. it seemed a fantastic thing,science fiction if you like - well it wasn'teven science fiction, no one had even thought of it. and so this was areal prediction. it was a prediction thatsomething strange should happen, that nobody hadever guessed would happen, and of course, at the time,nobody really believed it. now so far, we've onlydiscussed the dirac equation

in one spatial dimension. and that again, wasto make it easier. of course, thereal dirac equation is in three dimensions,spatial dimensions. and then those extrafeatures come in, just like with the photon. so if we do it inthree dimensions, then what we find is that,just like with the photon, there were two polarizations,a left-handed one,

and a right-handedone, and they carry angular momentumplus and minus hbar, you find a similarthing for the electron. so if you do all thisin three dimensions, then you find - and i'm afraidi'm not going to show you in any detail - that there aretwo different polarizations, we call them twospins, because they're intrinsic to the electron. and for the electron,there's something

rather curious, inthat the spins are not plus and minus hbar, likethey are for the photon, but they're plus orminus a half hbar. this is something that comesout of the dirac equation, when you do it in three dimensions. so for an electron, thereare actually four states. there's the positiveenergy state, left-handed. there's positive energystate, right-handed. there's the negative energystate left-handed, and also

the negative energystate right-handed. now let's think abouthow the field looks - or the waves if you like -look for the electron now, because of what theimplications are of the spin. so if you consider electronfields that go around in a circle, like we didfor the photon field, so we look at theangular momentum, then the fieldlooks like, again, a sine, the angletheta times the angular

momentum minus the energy timesthe time, divided by hbar. but now, the angular momentumis in units of h-bar over 2, not in units of hbar. now, you rememberfor the photon, it had to be inunits of h-bar, so that when we go round the circleand get back to the beginning, we get back to where we started. now, electrons dosomething really weird. for electrons, you have togo around the circle twice

to get back towhere you started. so for electrons,if you do theta, i goes to thetaplus 4 pi, then you can see this expressionwill stay unchanged - the half here cancels outthe - takes the 4 down to 2, and then you get backto where you started. if you only do thetagoes to theta plus 2 pi, so you only go aroundthe circle once, then the wave functiondoesn't go back to itself,

it goes to minus itself. so you get an extra minus sign. so if you think it's a littlebit strange that sometimes you have to go around twice in orderto get back where you started, then i have a little partytrick for you, which shows you that sometimes thisis actually necessary. so here we have a perfectlyordinary wine glass, i'll hold on the flatof my hand like that. now i'm going to turnthe wine glass around,

so you should watch carefullywhat happens to the wine glass. so first, i turn itaround once, like this. and you can see i'mnot not back to where i started, because itfeels very awkward. and then i carry on up,and turn it round again, and now i get backto where i started. now, this extra minus signthat we get for electrons is actually very important. you remember inthe last lecture,

when we were talking aboutthe double slit experiment, and we had two differentpossible things that could happen, andin order to work out the probabilityof that happening, we had to add up theamplitudes for those two different processes,and square it, and that gave usthe probability. so for photons,what we found then, was the probability - in thatcase of going through the two

slits, although it couldapply to just about any process where there aretwo ways of doing things - has to be the sum of thetwo amplitudes squared. now for electrons,i told you last time that it worked inexactly the same way. we take the two amplitudes,we put them together and square them. but, that wasn't quite true. you see, the two processeshere, because they're the same,

you get by swappingthe two photons around. now, when we turn - whenwe swap two photons around, it's a bit like takingthem round in the circle. so for the photons,we get a plus sign. but if you take twoelectrons round in a circle to swap them round, thenyou get this minus sign. you have to take themaround twice in order so for the electrons, there'sactually a minus sign here. so to sum up, we have - thisis another difference now,

between photons and electrons. for photons, we havea plus sign here. we have two differentpolarizations, which have angular momentum,plus or minus h-bar. and this is actually a genericsort of class of the way that things can happen. so objects that look likethis, you can call bosons. whereas for the electrons,we have a minus sign here. the minus sign is because thepolarisation states aren't

in units of h-bar, butin units of a half hbar. this puts them in a differentkind of class of object. these objects we call fermions. bosons are named after anindian physicist called bose, and fermions are namedafter an italian phycicist called fermi - that's wheretheir names come from. now, for fermions,like electrons, this has a veryimportant consequence. if you think about - ifyou have two electrons

in the same state, then, ifthey're in the same state, then these two amplitudesare equal to each other. and if the two amplitudes areequal, then they cancel out, so the probability is zero. so what this meansis that for fermions, then they can't bein the same state. there's no probabilityat all for them being in the same state. so they're alwaysin different states.

and this is something calledthe pauli exclusion principle. and it's because of thepauli exclusion principle that you can build up allsorts of different atoms. so that's why all thedifferent atoms exist, and why the worldaround us is so varied. because, if we have a proton,and an electron going around it, that would be hydrogen, say. if we want to addanother electron, it can't just siton top of this one,

it has to be somewhere else. so the atom looks different. because it can't sitin the same state. actually, it's notquite like that, because there's two spins. so actually, we can put twoelectrons in this orbit, one with spin up, onewith the spin down. that would give us helium. and then the nextone, lithium, has

to come in a different orbit. so that makes all the differentatoms look very different. and is one of themain things that explains the reason theworld's the way it is.