0 So we'll start out with a very simple problem. It's one of the oldest problems that has been studied in algorithms; it's the problem of sorting. OK, and we're actually going to study this for several lectures. OK, so we're going to think of ... sorting contains many algorithmic techniques.
We start out with a very simple problem, the problem of sorting. This is one of the oldest problems that has been studied in [the field of] algorithm analysis. We are actually going to study it for several lectures. Sorting contains many algorithmic techniques.

start out with X = X is the first thing we will do

has been studied Present Perfect Passive

actually, essentially, you know fillers (words and phrases that frequently don't add anything to meaning)

23.333 So the sorting problem is the following: we have a sequence a1, a2, up to an of numbers as input.
The sorting problem is the following: we have a sequence a1, a2, up to an of numbers as input. (Something funny is happening in the lecture hall - the students are laughing, the professor is smiling - but we don't know what it is.)
a1 Pronounced "a-one" or "a-sub-1" where sub is short for subscript. On the blackboard, he writes them as subscripts.
46.86700000000003 And our output is a permutation of those numbers, (long pause, the sentence continues in the next segment)

This sentence continues in the next segment. It has several digressions. Without digressions, it says: "The output is a permutation of those numbers, ... such that ... they are monotonically increasing in size."

61.00000000000004 OK, a permutation is a rearrangement of the numbers, where every number appears exactly once in the rearrangement, such that -- so I sometimes use the dollar sign to mean "such that" - OK - such that a1 is less than or equal to a2 - oop, prime - such that they are monotonically increasing in size.

As I just said, the output of a sorting algorithm is a permutation of input numbers. A permutation of a sequence of things is another sequence that has all the same things but in a different order. We don't remove or add things, we just rearrange them. A permutation of numbers is a rearrangement of a sequence of numbers. The output of a sorting algorithm is a permutation of input numbers such that, in the new sequence, the numbers increase. They increase from the first number to the last: each next number is bigger than the preceding number. In mathematics we say that the numbers increase monotonically.

Digression 1, a definition of the term permutation: "A permutation is a rearrangement of the numbers, where every number appears once in the rearrangement."

Digression 2: an explanation of what he wrote on the blackboard. The phrase such as is used so often in math and computer science that he uses an abbreviation for it: I sometimes use the dollar sign to mean 'such that'.

Digression 3 (oop, prime) a correction in notation: since the elements of the permutation are in a different order, he must use different symbols for them, so instead of a1 he must use, for instance, a'1 (a-prime-one).

Finally, he completes the sentence that began in the preceding segment (Our output is a permutation of those numbers) such that they are monotonically increasing in size.

rearrangement a new arrangement. rearrange things means "move things around without making significant changes, such as removing or adding new things"

96 OK, so take a bunch of numbers, put them in order. OK?
So here's an algorithm to do it, it's called insertion sort.
So [in summary, the task is:] take a bunch of numbers and put them in order.
Here is an algorithm to do it. It is called insertion sort.

take ... put them in order The long previous sentence is summarized as two instructions. Note the intonation.

a bunch of normally said of flowers. Colloquially, means the same as "several, a few, a number of."

108.667 And we write this algorithm in what we call pseudocode. That's sort of a programming language, except it's got English in there, often. OK and it's just a shorthand for writing ... umm .. for being precise. OK, so this sorts A from 1 to n.

We write this algorithm in a special notation. We call this notation "pseudocode." So we write the algorithm in what we call pseudocode. Pseudocode is similar to a programming language, except it often uses English. It is a shorthand notation that makes it possible to be precise. So, this [algorithm] sorts A from 1 to n.

pseudocode The prefix pseudo can be added to many nouns or adjectives: pseudo-X means "something that looks like X but is not really X." A pseudo-Afghan carpet is a carpet that tries to look like Afghan; a fake. Pseudocode looks like programming code but it isn't.

sort of It's sort of a programming language. In this sentence, sort of means the same as the prefix pseudo: similar to, but not really a programming language.

shorthand A brief way of writing something down.

143.60000000000002 And here's the code for it.

Here is the code for it..

146 (Long pause. Writes code on the blackboard.)

INSERTION-SORT (A, n) Input: A [1 . . n]

for j ← 2 to n do

key ← A [ j]
i ← j – 1
while i > 0 and A [i] > key do
A [i+1] ← A[i]
i ← i – 1
A [i+1] = key
199.667 So this is what we call pseudocode. OK?
And, if you don't understand the pseudocode then, umm, you should ask questions about any of the notations. You'll start to get used to it as we go on.

This is what we call "pseudocode."
If you don't understand pseudocode, you should ask questions about the notations that are used in pseudocode. You will start getting used to it as we go on.

get used to X become used to X, become familiar and comfortable with X
218.86700000000005 One thing is that in the pseudocode we use indentation where in most languages they have some kind of begin-end delimiters, like curly braces or something in Java or C, for example. OK, we just use indentation.
In many programming languages, there are some kind of begin-end delimiters to indicate the beginning and end of a block of statements. Java and C use curly braces as begin-end delimiters. In pseudocode, we just use indentation to show the beginning and end of a block.
X is some kind of Y Y is a general class of things, and X is a subclass or a specific example of Y.
231.86700000000005 The whole idea of pseudocode is to try to get the algorithms as short as possible while still understanding what the individual steps are.
The idea of pseudocode is to make the description of an algorithm very short. We want to get the algorithms as short as possible, but not so short that we cannot understand. their individual steps.

the whole idea the main idea, the main purpose

while still understanding the steps This is a participle phrase.

239.53300000000004 OK? Umm, in practice, there actually have been languages that use indentation as a means of showing umm the nesting of things. It's generally a bad idea because when you page from one ... if things go over from one page to another, for example, ok, you can't tell what level of nesting it is, whereas with umm with explicit braces it's much easier to tell.
There have been [programming] languages that use indentation as a means of showing the nesting of expressions. It is generally a bad idea because if a nested expression goes from one page to another, you cannot tell what level of nesting it is. With explicit braces it's easier to tell.

a means of showing Note that means is both singular and plural.

nesting of things Some speakers, when they cannot find the precise word, simply say "things." See also "if things go from one page to another" in the next sentence.

page from one... The word page, like many English words, can be used both as a verb and a noun. The way he started the sentence, he would have to say: "when you page from one page to another," so he interrupted himself and replaced the verb.

you can't tell Note this use of the verb tell, usually after can or cannot.

263.5330000000001 So there are reasons why this is a bad notation okay if you okay were writing umm if you were doing software engineering, but it's a good one for us because it just keeps things short, makes fewer things to write down.
So there are reasons why pseudocode is a bad notation for programming. If this were a course on software engineering pseudocode would not be a good notation. However, it's a good notation for us because it keeps things short, and so there are fewer things to write down.

if you were writing, if you were doing (but you are not) This is called counter-to-fact condition. Usually would is used in the main clause: If you were writing code, this would be a bad notation. In counter-to-fact conditions, the form were is used with both singular and plural subjects: If this were a course on programming, we wouldn't be using this notation.

software engineering He seems to suggest that software engineers mostly write code. In fact, much of the time they use high-level languages for modeling and design.

277.333 So this is insertion sort. Let's try to figure out a little bit what this does.
This, then, is insertion sort. Let's try to figure out what it does.
figure out understand, solve (a problem)
281.93300000000016 OK so umm so it... it basically takes an array A and at any point -- the thing to understand is --- so we're setting basically -- we're running an outer loop j to the n, and an inner loop that starts umm at j minus 1 and then goes down until it's umm until it's zero.
It takes an array A, and we are running an outer loop j to the n, and an inner loop that starts at j-1 and goes down to 0.

basically a filler word, doesn't add anything to meaning

at any point a false start, abandoned.

we're setting, basically... a false start with a filler word in it. He never says what we are setting and to what value.

set X to Y set the value of variable X to be Y; assign the value Y to the variable X

until it's zero What is it in this clause? Not the loop itself, but the loop counter.

321.333 OK, so basically -- so if we look at any point in the algorithm, we essentially are looking at some element here j -- A of j -- j-th element --
At any point in the algorithm, we are looking at some element here it's j, A[j], j-th element [of the array
we are looking at often means "we are selecting," "we are working with"
332.333 and what we do is essentially is we pull the value out here that we call the key,
We pull out the value of A[j], and we call it the key.
essentially another filler word
340.3999999999999 and at this point, the important thing to understand is - and we'll talk more about this in recitation on Friday - is that there is an invariant that's being maintained by this loop each time through.
At this point, the important thing to understand is that there is an invariant that's being maintained by this loop each time through. We'll talk more about this in recitation on Friday.

invariant something that does not change

that is being maintained Present Passive Progressive

each time through each time we go through the loop

356.40000000000003 The invariant is that this part of the array is sorted.
The invariant is that this part of the array is sorted.
362.333 And the goal each time through the loop is to increase -- is to increase -- is to add one to this length of the things that are sorted.

The goal each time through the loop is to increase by one the length of the part of the array that is sorted OR to add one more element to those elements that are already sorted

this length of the things Two descriptions are mixed here: the sorted part of the array has length that is increased by one, but the "things" (element of the array) do not have length.
372.333 The way we do that is we pull out the key, and we just copy values up like this -- keep copying up -- ok? until we find the place where this key goes, and then we insert it in that place, and that's why it's called insertion sort.
This is how we do this: we pull out the key, and we copy up the values, and we keep copying until we find the place where this key goes, and then we insert it in that place. That's why the algorithm is called "insertion sort".

copy up in this case, copy to the higher indices of the array

keep copying continue copying; (keep working "continue working")

390.933 So we just sort of move the things, copy the things up until we find where it goes, and then we put it into place.
This repeats the preceding sentence so the students have time to understand the idea.
sort of a filler phrase here
399.867 And then we -- now we have that from -- A from 1 to j is sorted, and now we can [to] work on j+1.
Now we have [the result] that A from 1 to j is sorted, and we can work on [element] j+1.
409.333 ok So let's give an example of that.
Let's give an example of [using insertion sort].
413.46700000000004

Grammar topics:

  • Spoken language: (exercise: given a paragraph, remove all spoken language features that do not add anything to meaning)
    • simple connections (so, OK)
    • generic words (things)
    • fillers (umm, actually, essentially; you know; )
  • word-formation: re- (redo, rewrite)
  • Contrary-to-fact conditionals and the use of would

Expressions:

get used to; some kind of; rearranging furniture on the Titanic; sort of (as an adverb); a bunch of; can't tell, the whole idea; figure out

Vocabulary:

arrange, rearrange, arrangement, rearrangement; rearranging furniture on the Titanic; pseudocode; shorthand; means (singular noun); keep (doing)

CS terminology :

algorithm; pseudocode; invariant; set (X to Y); nest, nesting;