0:01

So in this course, you and

Â when we ask you to do the programming part you will be writing the code in Python.

Â However, you will notice that when I'm describing algorithms or

Â when there are questions about algorithms the mathematical algorithms on

Â the homework, you'll see that I will be using or requiring the use of a,

Â of a certain program or language that we call pseudo code.

Â Okay.

Â So we have this notion of pseudo-code.

Â [SOUND] Okay.

Â So what is pseudo-code and why do we want to use and

Â why not just stick to Python?

Â So pseudo-code is a language that is very powerful for describing algorithms.

Â It is somewhere between a formal programming language that

Â has exact syntax that you have to use, and English or any other natural language,

Â in the sense that it is not as formal as a programming language.

Â It gives you wiggle room for using structures or using English in them, but

Â is not like English that it is ambiguous or not structured.

Â Okay?

Â So pseudo-code is very important,

Â you are going to be seeing it throughout the course.

Â We are going to be using it and

Â it's very important that you feel comfortable with reading pseudo-code.

Â Okay?

Â There are going to be on the website some notes about syntax that

Â we use for pseudo-code.

Â Of course, the syntax is going to be not very formal because you

Â might ask me why don't we formalize pseudo-code?

Â But if we formalize pseudo-code, what did we get ourselves into?

Â We have defined yet another programming language.

Â All right? So

Â we cannot formalize the syntax of pseudo-code perfectly because otherwise,

Â we have again created another programming language.

Â So pseudo-code, you know,

Â when we use a certain notation, doesn't mean that this is universal notation.

Â If you look at different algorithms textbook,

Â you might see differences in the pseudo-code that the authors use.

Â Usually, it reflect the programming language that the author has been using.

Â Right.

Â So for example the sign for assignment, how do I assign the value five to x.

Â You might see some book saying, x equal five.

Â Okay?

Â You might see some book saying, x colon equal five.

Â 2:08

You might see some text books saying, x left arrow five.

Â Okay?

Â And all of them this is assignment, right?

Â Of course, if you are using Python you have to use one specific symbol

Â for assignment.

Â If you are using C Plus Plus, you have to use one specific symbol for assignment.

Â In, in pseudo-code, it's not that this is right and these are wrong.

Â Or this is right and these are wrong.

Â No, you will see these all these ones in different text books.

Â Okay?

Â Now every text book tries to be consistent, so

Â if a text book is using this for

Â assignment, you will see that the textbook is using this throughout the book.

Â Okay?

Â But it's very important to keep in mind that we are not going to be

Â compiling the code, we are not going to be really running the pseudo-code in the so

Â it doesn't matter if it was this or this or this as long as we are consistent.

Â For example, in this course,

Â we are going to be using this notation, x left arrow five.

Â It means, I am assigning the value five to x.

Â Okay?

Â So, you might be asking, why am I, am I using pseudo-code again and not python.

Â Okay? Python is in some sense is

Â a high level language.

Â Right.

Â The one of the major issues of, or the rationale behind using pseudo-code is

Â that pseudo-code tells us what we want to do.

Â It tells us what we want to do in terms of the algorithm,

Â not necessarily how we want to do it.

Â Okay?

Â And when I am describing the algorithm to you,

Â it's very important that I tell you what I want you to do.

Â These are the steps that I want you to follow to, to, to achieve the, the task.

Â Now, how you want to do each one of these steps?

Â Again, it's very important sometimes to leave room for the, for the user or

Â the programmer to implement them the way they feel comfortable or

Â the way they find them to be more efficient.

Â Okay?

Â Let me illustrate.

Â 3:55

Suppose I'm in, I'm writing an algorithm or a piece of program and somewhere there,

Â I want, I have a list, L and I want to find the minimum element in that list.

Â Okay? The smallest element or

Â a smallest element in that list.

Â So here's one way I would write it in pseudo-code.

Â Let say, x is the smallest [SOUND]

Â element [SOUND] of L.

Â Okay.

Â So this is one way that I can describe this in pseudo-code.

Â Notice, I'm using English, I'm using some mathematical symbols.

Â But it is basically telling me that I am assigning to x the smallest element of L.

Â Now, I have told you what I want to be assign,

Â to assign to x, the smallest element in L.

Â Okay? Or

Â a smallest in case there are multiple ones.

Â Now, no, contrast this to the following.

Â 5:26

So this is a part of code that says, initialize x to infinity very

Â large number, then loop throughout all the elements of L.

Â Here I'm assuming that the list is index trans zero to n

Â minus one if it has n elements.

Â And for every element of L, i is smaller is x,

Â if the first one is smaller than x I'm going to replace x by that one.

Â And I repeat, if the second element is smaller than x,

Â I'm going to put an x the second element and so on.

Â What does this code do?

Â 5:55

This code is identical to this.

Â This is going to actually find the smallest element in L and say that,

Â and put it in x.

Â Now, is this telling us anything more than this about what we want to do?

Â The answer is no.

Â I would argue that this is not telling me anything more than this about what

Â I want to do.

Â It's basically telling me, I want to set to x the smallest element in the list.

Â What is this giving me more than this?

Â It's telling me the how, how am I doing it.

Â Right?

Â So this one is saying, to find the minimum element in L,

Â I'm going to be scanning the list all the way from the left to

Â the right to find the smallest element and I will return that.

Â Okay? So

Â [COUGH] this is where pseudo-code allows me, gives me wiggle room to play with how

Â much description or how much detail I need to give and the algorithm description.

Â This is acceptable pseudo-code, this is acceptable pseudo-code,

Â this is not acceptable in Python or in C Plus Plus or in Pascal.

Â This, if it is translated to proper Python, this will be acceptable,

Â this is very detailed and this, you know, in terms of instead of putting left arrow,

Â I would put equal.

Â In terms of mathematical symbol of infinity,

Â I will have to put proper thing in Python.

Â But this is basically would translate one to one, line for line into Python.

Â Right?

Â But again, in terms of what am I trying to achieve,

Â this is not telling my anything more than this.

Â In fact, I would argue that this is more readable than this.

Â But again, if I say how long does it take to find the minimum element in the list?

Â It's not easy to, to answer that question with this, because okay,

Â you are telling me that I find the smallest element.

Â It is easy to answer this,

Â if the list has n elements, this is going to take on the order of n operation.

Â Why it's not easy to find, to say, what is the running time of this?

Â You might say, well, look this is how I would find the minimum element.

Â That's not necessarily always the case.

Â I will give you another way of finding

Â the minimum element which is [SOUND]

Â sort the list L in increasing order, return, L0.

Â Okay.

Â This is another pseudo-code that is doing exactly the same like this in terms of

Â what we want to achieve.

Â It is sorting the list L in increasing order,

Â returning the first element in L after it is sorted.

Â Now notice, this is different than this, different than this.

Â They are, all three of them are finding the minimum element in the list.

Â This is going to differ from that in terms of the details.

Â And also is going to differ in terms of the running time.

Â This one here for example, what is the time it takes to sort the list?

Â 8:49

Returning this is probably one operation.

Â If I can go to that first,

Â first element in the list in one operation, then this is not going to take

Â many operation are going to take a small number of operations.

Â But how long does it take sort?

Â So now you start seeing that pseudo-code gives me this flexibility of,

Â in very simple readable way, describing what I want to do, like this.

Â But also it allows me, the flexibility to specify exactly how I want to do it.

Â Here, I'm saying do it like this, sort the list, return the first element.

Â This is going to be correct, is going to return the smallest element.

Â This one I'm saying,

Â scan the list, in, in, in order from left to right and find the smallest element.

Â This one doesn't tell me anything about how.

Â Okay?

Â Of course, when you write something in a real programming language Python,

Â C Plus Plus or Java for example, you cannot do this,

Â you cannot get away with this.

Â You have to know exactly how it is implemented and how the, all the details.

Â You have to figure out the details, are you going to be doing this, are you going

Â to writing a sorting function, sorting and then returning the first element?

Â 9:56

So, this is the why we use pseudo-code.

Â I describing an algorithm like this, look at this here in one line I said, sort

Â the list, there's nothing ambiguous about it, sort the list in increasing order.

Â Right? There's nothing ambiguous.

Â If I wanted to write this in Python,

Â I have to write a long piece of code that in fact, does actually the sort.

Â Okay.

Â Whereas in, in pseudo-code it was this magic line says, sort in increasing order.

Â I don't need to describe anything more because it's very well defined.

Â Okay?

Â So it allows me again, to abstract things out,

Â while still maintaining readability and understanding of what I want.

Â I want the smallest element, at the same time if I decide to go

Â into more details so that one understands exactly how I want it to be done,

Â