algo0108

0 OK. So for example, let me just draw that as a picture. So if I have n on this axis and T of n on this axis...then...this may be a, um... this may be for example a theta n cubed algorithm and this may be a theta n squared algorithm.

I will take a specific example, and I will draw it as a picture. I will draw it as a graph with two axes. This horizontal axis will show n, and this vertical axis will show T(n). I will show two functions T(n). One function will be, for example, for a theta(n³) algorithm and the other for a theta(n²) algorithm.

axes plural of axis. Other such plurals are analysis-analyses and crisis-crises.

23.99502487562189 There's always gonna be some point, n naught, where if you go, for everything larger, the theta n squared algorithm is gonna be cheaper than the theta n cubed algorithm. No matter how much advantage you give it at the beginning, in terms of the speed of the computer you're running on.

There will be some point, n₀, such that for all n larger than n₀, the n² algorithm will require less computation than the n³ algorithm. It will be computationally cheaper. In the beginning, the n³ algorithm may take less time, if you run it on a faster computer, for example. But no matter how much advantage it may have in the beginning, at some point the n² algorithm will become faster.

naught an old-fashioned word for zero; often used in mathematics for subscripts. In the next segment, the lecturer says "n zero."

where if you go... Sentence abandoned

No matter ... the computer you're running on. This is really an addition to the preceding sentence, but said with the intonation of a separate sentence.

42.99701492537314 Now, from an engineering point of view, there's some issues we have to deal with, because sometimes, it could be that that n zero is so large...that...you know, the computers aren't big enough to run the problem.

There are some issues that we, as engineers, have to deal with. From an engineering point of view, we may prefer an algorithm that is mathematically less efficient. It could be that n₀ is very large. It may be so large that today's computers aren't big enough to run the problem for such big n.

there's some issues It should be "there are some issues," but in colloquial speech people often use "there's" with a plural noun.

59.239800995024886 So that's why we nevertheless are interested in some of the slower algorithms.

For this reason, we are interested in some of the slower algorithms. Although they are slower, we are nevertheless interested in them,

nevertheless "despite something we just said," but in this case, it has only been implied that we usually prefer faster algorithms but we are, nevertheless, sometimes interested in slower ones.

64.87960199004975 OK, because some of the slower algorithms, even though they may not asymptotically be slower, I mean asymptotically they'll be slower, they may still be faster on reasonable sizes of things. And so we have to both balance our mathematical understanding with our, um, engineering common sense

because some algorithms, even though they are asymptotically slower, may be faster on inputs of reasonable size. We have to use both our mathematical understanding and our engineering common sense. We have to balance our mathematical understanding with our engineering common sense.

they may not asymptotically be slower The lecturer misspoke and corrected himself.

sizes of things The generic word "things" is used instead of a more specific "inputs."

we have to both balance The word "both" should have been later in the sentence (both understanding and common sense), or not at all. See the paraphrase for two possible versions.

83.63283582089554 in order to do good programming. So just having done analysis of algorithms doesn't automatically make you a good programmer.

[We have to use both] in order to do good programming. If you have studied analysis of algorithms, it does not automatically make you a good programmer. Having studied that subject does not automatically make you a good software engineer.

having done analysis A Perfect Gerund as the subject of the sentence.

90.69751243781096 OK, you also need to learn how to program and [unclear] use these tools in practice to understand when they're relevant and when they're not relevant.

You also need to learn how to program. In this course you learn the tools of algorithm analysis. To be a good programmer, you have to use these tools in practice. Then you will understand when they are relevant and when they are not relevant.

[unclear] One word is not clear. It's possible that the sound track is damaged here.

99.08756218905474 OK, so there's a, there's a saying that, um... if you wanna be a good programmer, you just program every day for two years. You'll be an excellent programmer.

There is a saying that if you want to be a good programmer, you just program every day for two years. All you have to do is program for two years. After that, you will be an excellent programmer.

you just program "all you do is program; all you have to do is program."

109.26169154228857 OK, if you wanna be a world-class programmer, you can program every day for ten years. Or you can program every day for two years, and take an algorithms class.

If you want to be a world class programmer, you can program every day for ten years. Or you can program every day for two years, and take an algorithm class.

Or you program for two years, and take an algorithms class. This is a joke that is also a promotion for the course. In American universities, professors and courses compete for students.

121.84676616915425 OK... OK. So...let's get back to what we were doing, which is analyzing insertion sort.

Let's get back to what we were doing. What we were doing was analyzing insertion sort.

which is The question word which stands for the noun phrase "what we were doing."

analyzing insertion sort This is a Gerund phrase.

131.363184079602 So we're gonna look at the worst case... which as we mentioned before is when the input... is reverse sorted. So the biggest element comes first and the smallest last.

We are going to look at the worst case. As we mentioned before, the worst case is when the input is sorted in the reverse order: the biggest element comes first and the smallest last.

the worst case, which is ... when the input is reverse-sorted Relative clause with which.

163.51840796019903 Because now every time you do the insertion, you gotta shuffle everything over. OK. So you can write down the running time by looking at the nesting of loops.

This is the worst case because every time you do the insertion, you have to move all sorted elements. You have to move all of them one place to the right. You have to move them over. So you have two nested loops. You can write down a formula for the running time by analyzing those nested loops.

you gotta Informal pronunciation of "you've got to," which is a colloquial form for "you have to."

shuffle everything over Instead of move, he uses a more colorful shuffle; instead of saying what is moved, he simply says everything; and instead of saying where, he simply says over.

174.19104477611944 So [what] we do is we sum up, so we ... What we assume is that every operation, every elemental operation is gonna take some constant amount of time. But we don't have to worry about what that constant is 'cos we're gonna be doing asymptotic analysis. As I said, the beauty of the method is that it causes all these things that are real distinctions, to sort of vanish. We sorta look at them from, from thirty thousand feet rather than from, um... from, you know, um... you know, three millimeters or something, OK.

The loops consist of simple operations. They are also called elementary or elemental operations. We sum up all those operations, and we assume that every elemental operation takes a constant amount of time. It is not important for us to know what this constant is. We don't worry about the constant because we are doing asymptotic analysis. As I said, the beauty of such analysis is that some distinctions become unimportant. They are real distinctions but in our analysis they vanish. It is like looking at some place from an airplane or a high mountain. From the altitude of thirty thousand feet or ten kilometers.

So [what] we do another noun clause with the question word. For some reason the lecturer skipped that word.

What we assume is Another noun clause with a question word

we're gonna be doing Progressive Infinitive

from thirty thousand feet from the altitude of thirty thousand feet

207.39203980099504 So, each of these operations is gonna sort of be a basic operation. One way to think about this in terms of counting operations is counting memory references. How many times do you actually access some variable?.

Each operation that we count is a basic operation. What is a basic operation? What exactly do we count? One answer is to count memory references. A variable name is a reference to a memory address. So we count how many times we access variables.

One way to think about this in terms of counting operations is counting memory references. The words "this in terms of" are not needed in this sentence. It should be: "One way to think about counting operations is counting memory references."

219.51044776119406 OK, that's another way of sorta thinking about this model.

This is another way of thinking about asymptotic analysis.

sorta A colloquial way of saying "sort of," which is a qualifier that often doesn't mean anything.

222.6497512437811 So, when we do that, well, we're gonna go through this loop... j is going from two to n...OK, and then we're gonna add up the work that we do within the loop.

When we do insertion sort, the outer loop repeats for every value of the variable j. That variable goes from 2 to n. So we need to add up the work that we do inside that loop.

add up Same as "sum up."

235.1756218905473 So we can sorta write that in math as: summation of j equals two to n.

We can write this in math as follows: Sum (the Greek letter Sigma) of j=2 to j=n.

in math in mathematical notation for sums

242.6179104477612 OK. And then, what is the work that's going on in this, in this loop?

The next question is: how much work is done in this loop?

that's going on A relative clause

248.9353233830846 Well the work that's going on in this loop varies, but in the worst case...how much, how many operations are going on here... for each value of j?

How much work is done in the loop depends on the input. However, what is the worst case? In the worst case, how many operations are performed within the loop for each value of j?

how much work? how many operations? Use much with mass nouns, many with countable nouns.

263.8019900497512 So for given value of j, how much work goes on in this loop? Somebody tell me asymptotically.

To repeat the question: for a given value of j, how much work is done in this loop? Somebody tell me. I want an asymptotic answer, an answer in asymptotic terms.

for given value The article "a" should be there: for a given value.

270.68756218905474 (indistinguishable voice) Yeah, asymptotically is...(indistinguishable voice)

Yes, asymptotically.

Yeah colloquial for Yes.

280.6915422885573 So it's j times some constant. So it's theta j. OK. So there's theta j work going on here because this loop, OK, starts out with i being j minus one and then it's doing just a constant amount of stuff for each step of the value of i.

It's j times some constant. So it's Theta(j). The reason it's Theta(j) is because the loop starts with i=j-1, and i goes down to 0, and there is a constant amount of work for each step of the value of i.

it's doing a constant amount of stuff The generic colloquial word stuff is used here.

297.60099502487566 And i is running from, from, um, um, j minus one down to, um, down to zero.

The variable i goes from j-1 down to 0.

i is running from ... down to He used the verb go before.

307.3074626865672 So, we can say that that's theta j work that's going on. People follow that? OK. And now we have a formula we can evaluate.

So we can say that Theta(j) work is going on on each step of the outer loop. Does everybody understand that? Does everybody follow our reasoning? Now we have a formula that we can evaluate.

People follow that? This is a colloquial form of "Do people follow that?" By "people" he means "people here."

follow In phrases like "follow the reasoning," "follow the proof," the verb means "understand."

319.7044776119403 So what is the evaluation if I wanna simplify this formula? What's that equal to?

What is the value of this formula? How can I simplify it? What is this sum equal to?

value, evaluate, evaluation In computer science and math, expressions have values. To find the value of an expression, we evaluate it. This process of evaluating an expression is called evaluation. Often, to evaluate an expression, we simplify it until it is simplified to a single value.

326.8089552238806 (indistinguishable voice) Sorry. In the back there. (indistinguishable voice) Yup. OK. (indistinguishable voice)

I'm sorry, I couldn't hear you. The student in the back there, please, repeat what you said.

Sorry or I beg your pardon. These phrases are used to say: "I couldn't hear, please, repeat."

Yup another colloquial form of "Yes."

347.40497512437815 So that's just theta n squared. Good. OK. Because this... when you're saying is the sum of consecutive numbers, you mean what? What's the mathematical term we have for that? So we can communicate. Gotta know these things so you communicate.

Yes, this is just Theta(n²). You are saying that this sum is the sum of consecutive numbers - what exactly do you mean? What is the mathematical term for such a sum? We have to know those terms so we can communicate.

Gotta know these things. Colloquial for "We (or You) have to know these things."

361.84477611940304 (indistinguishable voice)

Pause

Pause; no comment

362.571144278607 It's called what's type of sequence? (Indistinguishable voice) It's actually a series but that's OK. (indistinguishable voice) What type of series is this called? (Indistinguishable voice) Arithmetic series. Good. Wow. Got some sharp people, who can communicate.

What is this type of sequence called? It's called what type of sequence. Speaking precisely, it's a series, not a sequence. What type of sequence is it? What is this type of series called? Arithmetic series! Good. Wow! I have some sharp people here, who can communicate.

what's type of sequence? Should be "what type of sequence?"

What type of series is this called? This is a mix of two sentences: What type of sequence is it? What is this type of series called?

376.8298507462687 OK. This is the arithmetic theory ... series. You're basically summing one plus two plus three plus four. Some constants in there, but basically it's one plus two plus three plus four plus five plus six up to n. That's theta of n squared. OK. So if you don't know this math, there's a chapter in the book or you could have taken the prerequisite.

This is the arithmetic series. Basically, you are adding up one plus two plus three plus four. There is a constant factor, but basically it's one plus two plus three plus four plus five plus six up to n. This adds up to Theta(n²). If you don't know the mathematical rule, there is a chapter in the book. If you had taken the prerequisite, you would know it.

you have taken the prerequisite. This implies that if you don't know the rule, you have not yet taken the prerequisite course on Discrete Math.

400.9353233830846 OK. Right. Arithmetic series. People have this vague recollection. Oh yeah. OK. Good. Now, you have to learn these manipulations. We'll talk about it a bit next time. OK. But you have to learn your theta manipulations for what works with theta. You have to be very careful cause theta is a weak notation.

Right, arithmetic series. Do people here have this vague recollection when you say (imitates): "Oh, yeah, I remember something like that." You have to learn these manipulations of formulas. We'll talk about them a little bit next time. But you have to learn how to manipulate formulas with Theta. You have to look carefully for what works with Theta. And you have to be careful in simplifying formulas with Theta because Theta is a weak notation.

Oh yeah This is pronounced with the intonation that people use when they remember something.

manipulations, manipulate The lecturer is talking about manipulating formulas in the process of simplification and evaluation. You manipulate formulas in order to simplify and evaluate.

425.5582089552239 OK. So strong notation is something like Leibnitz notation from calculus, where you ... The chain rule is just canceling two things and it's just fabulous that you can cancel in the chain rule. OK. Just, OK. And Leibnitz notation just expresses that so directly, you can manipulate.

An example of strong notation is calculus notation invented by Leibnitz. In that notation, when you use the chain rule, you just cancel the same term in the numerator and denominator. It is amazing that you can cancel in the chain rule and it is mathematically correct. The Leibnitz notation expresses the operation of the chain rule very directly. It makes it easy to manipulate formulas.

The chain rule is

$\frac {df}{dx} = \frac {df} {dg} \frac {dg}{dx}.$

443.4547263681593 Theta notation isn't like that. If you think it's like that, you're in trouble. You really have to think of what's going on under the theta notation and it's more of a descriptive notation than it is a manipulative notation. There are manipulations you can do with it but unless you understand what's really going on under the theta notation, you will find yourself in trouble.

Theta notation is not like that. If you think it's like that, you will be making mistakes. You'll be in trouble. You really have to think about what the notation stands for. Theta is more a descriptive notation than a notation that lets you easily manipulate formulas. There are some manipulations you can do with it, but if you don't understand what's really going on under the theta notation, you will make mistakes. You will find yourself in trouble.

under the theta notation This is probably a reference to the expression "under the hood." If your car is in trouble you have to lift the hood and look under the hood for the reasons. So, "to look under the hood" means to look at something more deeply; to look at the operation of a complex system by opening the system, rather than from the outside. The Theta notation is like a hood over a complex system, and in order to use it you have to look under the notation.

466.16517412935326 OK? And next time we'll talk a little bit more about theta notation. So is in ... insertion sort fast?

Next time we'll talk a little bit more about Theta notation. So, is insertion sort fast?

So, a typical use of So to close one topic and start a new one.

475.7810945273633 Well it turns out, for small n it's moderately fast. OK, but it is not at all ... for large n.

It turns out that it is moderately fast for small n, but it is not at all fast for large n.

it is not at all for large n The adjective fast does not have to be repeated.

506.92736318407964 OK. So, I'm gonna give you an algorithm that's faster. It's called merge sort. I wonder if I should leave insertion sort up? Why not.

I am going to present to you an algorithm that is faster. I am going to give you a faster algorithm. It is called "merge sort." I wonder if I should leave insertion sort on the blackboard. Why not?

give you The verb give is used here in a very general sense of "present to you," "show you, and explain it to you so you have it in your head and can use it."

Grammar topics:

colloquial speech: use of There's for "there is" and "there are"
irregular Plural forms of nouns
Gerunds and gerund phrases as subjects and predicates
relative clauses with which
much vs. many; little vs. few; little vs. a little; few vs. a few

Expressions:

Sorry; (I) beg your pardon; from thirty thousand feet; under the hood

Vocabulary:

follow (a line of reasoning); manipulate, manipulation; axis;

CS terminology :

value (of an expression); evaluate