I'm assuming you can hear me via the speaker.

We were talking Tuesday about the kind of math or computer science prerequisites that

I'm going to assume and some of the prerequisites are more important than others so I'll go

over them again.

Tuesday we went over complexity theory.

The things I expect you to remember from complexity theory is that we have these classes which

are just essentially sets of functions that have a similar growth behavior meaning we

don't care about the beginning to counter set up effects and we don't care about constant

factors and I've shown you the math of how it actually goes and the important thing is

that these things are ordered.

Constant complexity grows less fast than n log n, grows less fast than linear, grows

less fast than any of the polynomial complexities and then we have exponential and the list

goes on.

There's doubly exponential, k-fold exponential and in the end there's something called non-elementary

which is basically towers of exponentials of 2 and the k is k-high and it's of course

bracketed in the way so that it really makes it big.

And of course it goes on after that and at some point we reach undecidability meaning

we can't even guarantee that it stops.

That's kind of the big landscape of complexity theory and the big practical thing I'm assuming

is that from an algorithm you can tell what the complexity is because in AI we're not

just talking about small problems but of problems like the size of the internet or the size

of all concepts that an average adult has and those are in the millions and so size

matters.

And we've talked about prologue which I maintain is good for you.

Learn to love it.

You can kind of break up with that love in April because there's the exam first.

The next topic we are starting on is formal languages and grammars.

In principle again it's very simple.

We're talking about strings which are sequences of characters which we can think of mathematically

as being vectors, topples we say, and we have the zero topple, we have longer and longer

and longer topples and formal languages are just sets of strings.

Very easy.

And anything we do on the language front really here in computer science, our formal languages,

the important thing is that this being, formal language being a set of strings, we have specified

exactly what's in the set.

Those are the good ones and what's not in the set.

Those are the bad ones.

Think about all Python programs.

A set of strings and actually the interpreter tells you whether your program is in the set

or not.

If not, then you get a syntax error.

So that's essentially the theory, has a simple mathematical structure, we have concatenation

as some kind of an addition, only that addition is not commutative like the addition on natural

numbers or reals.

If you turn around the arguments of the concatenation, something different comes out.

So if you concatenate text and book in that order, it becomes textbook.

If you concatenate it in the other order, it becomes book text.

So that's concatenation.

And then we can do kind of things on top of concatenation.

We can do repetition, which just basically says, oh, repeat something, which is concatenated