Computer Science 61A - Lecture 1

Uploaded by UCBerkeley on 25.08.2012

PROFESSOR DENERO: Welcome to Berkeley computer science.
I'm very glad you could all drop by. Okay so I'm John. Some people try to call
me professor that's too formal call me John also I don't work here, so it would be awkward
to call me professor. I work at Google actually. STUDENT: Ooh.
PROFESSOR DENERO: I'm glad you like Google, so do I. But I was here at Cal as graduate
student for many years in fact my years at Cal strongly out number my numbers at Google
so that means you can trust me. I'm the instructor but who will teach you
are TAs running section and is lab and is pretty much everything else. Write tests grade
them make sure you make it through. They are wonderful here they are smiling faces. If
any of you are here stand up and wave. The TAs [APPLAUSE].
That's not all. There are also readers for the course. They are your personal mentor
for learning how the program effectively so. They will give feedback on projects so you
have a chance to develop your skills. And lab assistants volts who come to the lab just
because they want to help you learn. They are there to ensure you respect stuck and
you have someone to asks questions. Come to lab ask homework or project questions. They
will be there to help you out. Okay that's our staff.
What is computer science? So this is a course about computer science
it's called the structure and interpretation of computer programs and computer science
is very broad discipline. Here is what it is. If you ask a bunch of different people.
It's about building big systems, like, you know, they will tell you. There are now global
systems for instance the Google search engine that connect many computers. Artificial intelligence
selfdriving cars and many other things and graphics they create Pixar movie and is video
games security people making sure your privacy is ensured helping you connected world. Network
people make sure programming language people write programming language theory people what's
possible; scientific people learn about computers and list goes on and on. That's computer science
that's what we will cover. That's a lot of material.
And even gets worse. So within each branch of computer science there are sub branches
within artificial intelligence with computer vision with photographic who are the people
in it. So selfdriving car should be able to find the pedestrian. So not to run over with
a plan not to run over a planning with artificial intelligence robotics. That's me. English
is a natural language I spend most of my time on Google translate human language into another.
To do that we need computer systems that understand how language world. Computer science is very
broad but it's connected. Applications and understanding of the most general machines
ever built the computer machine or the computer. That's what connects us all in terms of underlining
ideas but the binding thing and makes us work as single community is we have a common enemy.
And that is complexity. Okay so basically everything that happens
in every branch involves building computer systems. Those are complex they have to do
interesting things and with lots of interacting parts it's complex and hard to understand.
What is 61 A a course about computer science and managing complexity. So we will look at
series of different techniques about complexity and making them understandable.
We have 1 master tool. And that's called abstraction. Most of this
course will be abstraction. Now it's a kind of a subtle concept when you
have a complex thing, with lots of interacting parts. Instead of thinking about complexities
you give it a name and treat it as a whole without worrying about all the details. That's
what abstraction is. So it turns out as humans are you extremely
good at this. You look at me you see John and you call me a person.
You don't call me some complicated really involved mixture of cotton and skin and bone
and blood and bunch of water and carbon atoms with hydrogen and others bounces know you
call me a person even though underneath I am complex. You can where I am right now.
Teaching this class without having to worry about exactly how many oxygen atoms my body
contains now. That's abstraction take something complex and give a name and operate there.
Using abstractions in computer science. It's said it is it's about understanding ones and
zeros and how to compute things with ones and zeros that's not it at all much of it's
at higher level so computer science iS don't stare at screens like this and understand
the inner workings but instead conceptual ideas and abstractions.
It's also introduction to Python language. That's the primary 1 in this course although
there will be others. How many people have written a line of Python
before? Lots. That's great.
For those who haven't, it's okay. We won't be assuming you've seen before although it's
great if you have. We are introducing Python piece by piece and actually very slow space
so we can understand how all the pieces work together. So idea is not to master the programming
language but understand big ideas in computer science and we will happen to use Python which
is convenient. It turns out the features we need we will
introduce today to catch everybody up. Python or not you will have seen it before when you
leave the lecture. What's happening in the class introducing
some features of language how things work. But then we will actually go in and create
the features ourselves. And understand big ideas in computer science.
By building them. Because that's the best way to see inside
a complex system is to build it yourself and then after you can consider it abstraction
give a name and treat it as a whole without looking at the details.
So we are going to study for instance objective orienting programming which is important but
we'll learn how the build object system ourselves. And we will understand how on interpreter
a program that understands how other program programs and bid it ourselves meta is a word
means selfreferential and it's really important in computer science and it sounds cool to
feel free to use in your daily lives. So last thing about this class this is a challenging
course most people in this room as you have seen programmed before and it is designed
for those people or if you are fresh you are willing to put a lot of time up front in order
to catch up with the class. It's moving quickly we solve a lot of puzzles and work with really
challenging ideas. I am not shy about trying to bend your mind. That is the reality of
this course and something you should be prepared for if you choose the stay.
Okay I just told you what the class is about any questions?
STUDENT: What's. PROFESSOR DENERO: Is there a book is the question
no. There are lecture notes online I'll show you some on Monday. They are taken from a
book opensourced licensed under the creative commons it's classic textbook revised to include
new material that's relevant to computer science today but keeps the ideas back in the 80s
were great ideas then and now too. So it's based on a book on the course Web
site. Course Web site is: Looks like this. And it has some announcements
and down here you'll see a column for each lecture I list the readings and those link
to the textbook which is online lecture notes. Okay.
On we go. 61 A is something else. Computer science is
about ideas, it's about managing complexity abstraction it's also about joining a developer
community. Who are these people not all of of them have 61 A too bad for them. They went
to a conference on 1 aspect of Python and got to and took a photo. Computer science
is no longer about a person sitting in front of a computer working by themselves building
something important over 10Êyears that doesn't happen anymore it's interactive discipline
and and working together they don't write programs for computer to understand often
but for other people. You are building program as part of a community. If person A can't
read what person B generated then they can't really work together well.
We'll talk about what it means to be in developer community get connect and had leverage the
people out there who already understanding and ideas and learn from them that's a big
part of computer science of the that's exactly what starts here in 61 A.
There are some alternative to see 61 A T. class is full there's a long wait list. I
can't make class bigger I added computer l extra lecture. But it filled. Now a lot of
people. If you are on wait list, pursue some alternatives. 1 of which is called 61 AS.
Is a selfpaced course. Which means instead of having big lectures
like this where everybody learns at the same time you work through exercises at your own
pace. That means if you want to go faster or slower, you can.
It's it's taught by Brian Harvey and it's currently full but in principle it could be
expanded if you are interested go look for link on course Web site and check that out.
Any questions about that course?
STUDENT: Can you explain why it's taught in different language.
PROFESSOR DENERO: 1 thing that about 61 AS that's different it's not Python but scheme.
It's a language that was developed for original textbook for this course. It's a wonderful
language. And a lot of the good ideas from scheme are used in Python they are close in
that sense but selfpace course is built ton curriculum before updated to include new programming
language and few new topics it's a slight mismatch, but all big ideas are the same.
You type slightly different things when you actually do your projects.
Slight. So this course has only been taught in Python 4 times now.
Which means that there are less bugs than when it was taught only 0 times. But we are
still in development. So if you see things to make better point out to staff. And then
CS 10 the beauty and joy of computing I'm told that is full too. It's a wonderful course
but it's intended for nonmajors or people who want more graceful or slower path in the
programming. And so it uses different programming language as well a visual programming language.
But also addresses some of the ideas how computer science interacts with society as opposed
what we focus on abstraction and complexity. It's a good precursor and also if you want
to learn about computer science learn how to program but you are not particularly interested
in being a computer science major or it's meant to get people in computer science major.
Approximate. Questions about CS 10? How many people took
that course. How many people loved it. STUDENT: Some Woo!s.
Notice more people loved it than took it. That is the really good course I love it but
never took it. I should I could have. If you are interested the gnat check it out. It's
hard to transfer later but attend as soon as possible.
CS 10 doesn't cover the same requirements as 61 A. 61 AS does cover the same requirements.
Okay first class course policies. 1) the purpose of this course is to help you
learn not to make you suffer not to weed you out or confuse you.
2) the staff is here to make you successful in that endeavor. At any time you feel frustrated
confused stuck come to the staff. That's what we are here for and want to make you successful.
And also there is 12 pages of other course policies I wrote on the Web page that I won't
spend the first day discussing the details of grading and stuff but if you have questions
we have online forum and feel free to ask questions course policy readings in addition
to the homework or projects you should use that course forum which is calledÊ"pee at
is a". So not all the details. If you have questions
feel free to come to me afterwards or in office hours um yeah.
There is 1 aspect of course policies that I want to discuss but I think it's very important.
And that's collaboration you should discuss everything with each other. The whole point
of computer science is to understand what you are doing not prove that you know it already
it's okay not to understand the first time you read or hear about it. The way you understand
is go to section talk to the other people go online and ask questions talking to people
in office hours and get involved that's how you learn.
Discuss everything with each other. We even give points for this kind of thing
it's could EPA standing for effort participation and altruism. Every did you show up?
Participates did you say anything? Altruism is actually the most important part
once you understood something did you take the time to help your peers understand as
well. Did you go back to forum and answer questions for people who haven't quite solved
it yet and help them understand as well sometimes you are the best teachers. Because you went
through the phase from not quite understanding something to fully understanding and you know
exactly the bridge in between. So you can be wonderful teachers for each other and it's
the best way to master the subject and telling someone how you think something works you
have a chance to understand and you can explain. There's weekly homeworks that can be completed
with a partner although most people work alone it's important you work through the homeworks
by yourself for little bit to make sure you understand what you understand and what you
don't understand. There are 4 course projects these are 2week
long assignments to big projects. You start with some infrastructure and build
the rest out yourself. They are supposed to be fun and engaging and teach you how to layer
the different ideas of the course into 1 coherent whole. They heard be done in pairs so find
a partner. They need to be someone in section because that's how we organizes the course
around sections and projects are more fun and rewarding and less work with partner so
finding a partner should be a priority. Then you can work throughout the term or switch
that's fine. It's possible to work alone that's fine but I don't recommend it. Find a project
partner in your section. Questions?
STUDENT: Would you recommend a project partner to be a roommate if they are not in your section.
PROFESSOR DENERO: That would be fine but it's important but it's also fine to have someone
who's not. It doesn't have to be the best friend but someone to collaborate with and
learn from and not something you spend the rest of your life building stuff. So that's
fine [LAUGHTER] your partner can be the person that you program everything else in your entire
life with that would make me very proud. I didn't answer that question it could go
on. Unfortunately there are limits 1 rule don't share code with anyone but your partner
talk about ideas but don't post the solution to the homework or projects on online forum
nor should you showing your implementation to anybody else in the class instead ask high
level questions and copying solutions is serious offense and it's easy to detect because programs
are well structured things so it's really not a good idea. So talk about everything
but don't share code. Happen to understand when they do that it's
act of desperation not because they are evil and that happens because they are out of time
confused don't know how to do it themselves the right thing then is ask for help and there's
ways we can help you and make sure you get through and instead of resorting the copying
the solution. STUDENT: How about 2 partners.
PROFESSOR DENERO: What about with partner can you share code absolutely you can share
everything with them and you even hand in 1 assignment for the 2 of you.
Okay. Question. STUDENT:
PROFESSOR DENERO: No some questions just vanish a word about questions it's a great idea.
Occasionally if you ask something off topic and not relevant to everything else I will
say let's talk about that in office hours that doesn't mean I don't like your question
but I have other stuff I'm supposed to talk about in lecture. So feel free but I might
not answer them all I think it's a good idea. It's worse if you don't ask your question
and then you stay confused for entire semester and then you have to take the class again
that's no go. STUDENT: Office hours?
PROFESSOR DENERO: With high probability Monday and Wednesday at 330, but check the course
Web site that might change. Next week, both section and lab meet in lab
room it's a bunch good idea to understand. Homework 1 is posted they come every week.
The nice thing about them is they are not graded o correctness but effort why? It's
there not to for you to prove you know the answer but for you to start understanding
the material well. So homework is meant to be not trivial but challenging enough to get
you to think and apply it in new ways it's okay if you don't get the answer but work
through them because homework problems. Bear a lot of resemblance to what shows up in the
project and even exams. It's a good idea to do it's certainly graded but graded on effort
as opposed to incorrectness. If you are on the wait list you should still
do the assignments and homework if you hope to get in PV some people always drop so some
of you will get enrolled I don't know how many. It's frustrating to be on wait list.
But I will try to accommodate you as much as I can. So for instance if you were denied
course account form earlier I will give you 1 today how many people still need 1?
We now have enough for all. We want you involved in the course. If you think this course is
not right for you drop and do something else. And hopefully people from the wait list will
be able to enroll. Questions?
STUDENT: Homework question. Is it due the next week.
PROFESSOR DENERO: What's that. STUDENT: Is there a due date for every homework.
PROFESSOR DENERO: They will be released op Friday and due the next Friday at 5:00Êp.m.
STUDENT: Where turn it in. PROFESSOR DENERO: Turn them in online. Submission
instructions with handy videos will be posted as soon as possible this weekend by the TAs
it should work pretty well. Okay no more questions? If you want a question
and I don't see you that's because there are lights so feel free to wave. Nobody's wavings
why not? There are midterms on September 19th and October
24th a final exam on December 13th. This is on the Web site if you can't make these let's
know. Not the day before the exam. If you don't show up that's bad. It's a good idea
to read lectures notes before lecture. If you haven't read the lecture notes that might
not be the most productive time they are there to be prereading for the lectures themselves.
STUDENT: Midterm question: do we have to write code on them or type them up.
PROFESSOR DENERO: So what about the midterms do we write down code by hand and answer is
yes you occasionally do that. Midterms do not involve a computer in any way just your
brain and paper and pen no computers inside the pen please.
STUDENT: Where are the office hours? PROFESSOR DENERO: Check the office Web site
to see but my office 329 soda. Never trust anything I say in lecture just go on the Web
site and look it up. It's much safer. Okay next announcement. : let's look at what
the Python language is. Python is programming language. When 3>>>
that means you are talking to the Python interpreter. 1 thing it can do. Is tell you what number
you just typed in. [LAUGHTER].
But there's many. It can add. And even do complex arithmetic.
PROFESSOR DENERO: Okay. So what we've been typing in and evaluated for us are are expressions.
An expression describes some kind of computation sometimes it's simple just understanding a
number is number but some involves combining different values together. Expression describes
computation and evaluates to a value. It's kind of math or arithmetic.
And in math, there are lots of different way to see express different kinds of combining
operator or different expressions so addition looks like 2 things next to each other with
a cross. Division puts 1 above the other there's a line with a funny little groove that we
use to mean square root. Sometimes theres a word sin which apparently is sign. What
else there's bars for absolute value a big Sigma sum up the number from 1 to hundred
so math ticks has hot a lot of ways to say things this means 18 items out of 69. With
a parentheses in order to learn math ticks learn the different notation sometimes F(X).
It turns out all of this can be expressed with function notation like f(X). So that's
what we are focusing for the first couple of weeks is functions knot just mathematical
function functions. That's where we are starting today. Let's
look. So Max of 7.5, 9.5 it's not 2012. It's 9.5. So the notation. It's easy to type. I
didn't create any kind of square root. It's nice because the relationship between different
arguments can be expressed just by the order. So the function pow raises 1 number to the
power of the other. If I raise 100 to the power of 2 I get 10000. But if I change the
order of arguments then I get a different number. Something larger that's 2 to the power
of 100. Okay.
That's 1 nice thing about function notation is by choosing the order of things I can express
different relationships. Another nice thing is: if I have multiple arguments to combine
I can list them all in a row. Oh no 2012 again.
Another interesting thing is I can list 5 values together I only have 1 operation I
apply to all: the Max. If I used for instance the infix notation
of plus over and over I would have to have a bunch but here I only need 1. Most important
thing is that it nests. What is that I cooked up an example.
I don't know if it's interesting but we'll see.
(Whispering). So what I'm saying I want the Max of minute
of 1 and 2 and the minute 3 raised to the 5 and 4.
Talk to the person next to you and figure out if you can guess what that comes up with.
Minus 2.
Minus 2? Let's see if we can understand what's going
on. So here's our expression how it works. It
has operator the thing before the parentheses and it has any number of operands. Start number
from 0 when we count from 0 to the first and then operand 0 and 1 which is 2 and 3 those
themselves are also expressions that's what allows us to next. They tend to be expressions
themselves evaluate to values. Expression 2 evaluates to 2. Expression 3 evaluates to
3. And add evaluates to addition. So then we have a decision we have 2 and we have 3.
Well isn't obvious we add 2 and 3 together. It's obvious but it's worth stating precisely
that's the important thing you can do in computer science is say exactly how something works.
So here we say exactly what it is the procedure by which we evaluate a call expression in
Python. The procedure looks like this. We evaluate
the operator and operand sub expressions first. And then we apply the function, this is additionÊ
which is the value of operator to the sub expressions.
Oh sorry to the arguments which is the values of operand sub expressions what did I just
say. We have operator sub expression as the thing labeled as operator we evaluate that
gives us addition and operands. 2 and 3 and apply the function called addition, to these
2 arguments 2 and 3. Which are both values, and then we get what
the whole thing evaluates to is return value of the function.
That helps us explain what happens when we have 1 of these nested expressions. We will
apply the procedure over and over and over again.
First we find the values of the sub expressions the operator and operands.
So here's the operator it's mul it's value is multiplication function.
How about the first operand is itself an expression. It's a call expression it's not simple. We
need the apply the same rule we are in the middle of applying again to the sub expression
the add is operand there oh sorry. I'm fog o too fast. Add is operator there and operands
is it are 2, the number 2, and another sub expression which is a call expression we have
to evaluate as well as. How do we do that? We evaluate is operator and operands and then
we apply multiplication to the values 4 and 6 and we get 24. New we finally know what
argument to add 2 to. We will add 2 to whatever is value of the sub expression mul 4, 6 which
is 24 and then add to 24 and get 26. We then need to evaluate in last sub expression.
Which gives us adding 3, and fife is 8. We then multiply to get 208. Trees structure.
Trees grow from top down and what's happening is over and over again applying the procedure
for evaluating call expressions. In order to eventually get the value of the whole call
expression by first getting the values of its sub expressions question.
STUDENT: PROFESSOR DENERO: The question is is the common
to all programming languages the answer there's always an exception to the rule but yes. So
functions appear in almost all programming languages because it's a good idea it's extremely
typical that evaluation is sub expressions first and then combine by applying functions
to the arguments. STUDENT: Operations are expressions too are
there sub expressions. PROFESSOR DENERO: Question is account operate
be a sub expression that's complicated or is it always the name mul or add. It can be
sub expression too. We'll look at that next week.
Okay so we actually covered a topic on the first day [APPLAUSE].
Let's do some more demos. The print function is special. Actually, I
will tell you about print on months Monday we are running out of time and I want to tell
you about something else. STUDENT: Can you show. .
PROFESSOR DENERO: Someone asked the question can you show us something cool [LAUGHTER]
the answer is: sure. Let's move on the something cool.
Let's go back and say what's the course about. Well it's about abstraction managing complexity
but it falls into 3 areas: data functions and interpreters. First 2Êweeks on functions
then talk a lot about data and then time on interpreters. What are these things. Data
in general are things a program fired LS with: numbers then add together whatever.
Sometimes we have strings of texts the art of computer programming is a very famous computer
science textbook we don't use in this course it was by a famous computer scientists a data
can be a representation of a person just like you have a abstraction in your mind about
a person is. A computer can have 1 as well and manipulate that. Even large things like
Shakespeare's entire 37 plays. What's a function they are rules for manipulating data telling
us how the combine things in various ways. Which we've looked at by having a function
and writing a call expression which says what should the function apply to.
Add up numbers or perhaps count the number of words in a line of texts. How many words
in the art of computer programming. Fiver. Or pronounce someone's name. How do you say
that? Turns out it's KANUTH the K is not silent. It's an interpreter implementation of procedure
for evaluation. I told you how to evaluate a call expression.
Computers need to know how to do that too so they can actually execute the programs.
So interpreter is the program that knows the rules for the language and therefore take
functions and apply them. Okay I will go off book a little bit. And
show you some things I won't entirely explain but it's flavor of the topics in this course
so you know what you are getting into and know it's not all adding and multiplying but
there are other interesting things can do as well. So what can we do?
I told you that 1Êpiece of data would be the entire 37 plays that Shakespeare ever
wrote. There they are.
I took them all and split them up into words. How many words if.
980,000Êwords. That happened pretty fast. Turns out that not all those words were the
same. In fact Shakespeare was so lazy he wrote down the word the 23,000 times there's other
stuff in there. Some Val. Thou thee.
You add them up we are close to 980,000. [LAUGHTER].
Forsooth, 40 times. STUDENT: When you do that does it take when
it counts those it's also counting the's. So.
PROFESSOR DENERO: So question is every time a the and the's as well the answer is no.
The thing I'm counting the first 10: I broke the text in words midsummer's night is next
thing dream next, now, common, fair hip lie at a, et cetera.
Midsummer night's dream is a good read so I only count the the's in this case anything
you want me to count. Let me get your question in a second I have
a lot of demand for counting commas. My goodness.
STUDENT: Is there a particular reason why it counts commas even though it's not words.
PROFESSOR DENERO: Good question why do we count commas even though they are not words?
Well, computers are very fast but very dumb. Is kind of the fundamental property of that.
We've taken the entire text of Shakespeare not how it was pronounced or conceived but
exactly how it was written. And split it into each segment or each word so breaking space
in that way. And right now we haven't distinguished between what's English word versus just punctuation.
Can we count all words minus punctuation. We could but I won't because I want to do
something else. What if we throw the words in set what's the
property of set it can only have at most 1 of each elements. Therefore these words are
unique. There are only 33,000 unique words without commas. So commoning them. Let's see
what's in there. What's the biggest word the Max of all the words.
[LAUGHTER] zwaggered.
STUDENT: That's not the longest that's the ZW.
PROFESSOR DENERO: That's the last 1 in alphabetical order. You want to figure out anything you
want arbitrary computations. So let's invent 1. There's a trick in Python where you take
a word and write it backwards. Now I'm sorry that it has this weird notation
I won't make you learn that but it's quickest way for you to print something backwards.
Here's something backwards and combine this idea with other ideas. For instance I can
take tall words such that
there are exactly 4 letters long and the reverse of the word is also a word.
You think there's 1 of those actually there's a lot them: Pool, pots, stop backwards. Rail
is liar backwards, et cetera. Think we can go bigger?
Can you think of a 5letter word that's another word spelled backwards?
Oh a bunch someone said madame there is it is.
Bigger? If you can think of 1 shout it out.
Diaper just repaid backwards [LAUGHTER]. Of course.
I'm actually out of time. I'm stopping there are more things you can do with this we'll
do so many next time. Talk to you soon.