can you create a study plan with the text from a slideshow video

This is pre lecture one for CSE $430.$ We're going to cover an introduction to algorithm design and complexity analysis.

$0$:$00$

And you should reference chapters one, two and three of the common least recent algorithms book.

$0$:$09$

A quick overview of our algorithms course.

$0$:$17$

We're going to be talking about various design techniques and approaches for algorithms, which are more important than just memorizing algorithms.

$0$:$20$

We're going to spend a lot of time talking about the analysis of algorithms, both the growth in runtime and maybe memory usage.

$0$:$28$

Spend a little time discussing how we can prove an algorithm correct, which is different from, uh$,$

$0$:$35$

in your programing courses where maybe you wrote test tables to test your code proving and algorithms.

$0$:$41$

A little different idea. And we're going to talk a lot about applications of algorithms and understanding,

$0$:$46$

uh$,$ how to apply the theoretical algorithms in real world applications.

$0$:$51$

So for the analysis of algorithms,

$0$:$58$

the basic idea is that if we're going to look at the size of a problem versus how much time it takes to run or the memory usage,

$1$:$00$

we're not concerned with an individual point of this graph.

$1$:$11$

We're concerned with the growth in the runtime or the growth of the memory usage as the size of the problem increases.

$1$:$15$

So what this this graph represents is maybe four different algorithms with various growth growths associated with them.

$1$:$21$

And we'll talk a lot about how we would develop these functions that are the algorithm growth.

$1$:$30$

But again remember the main idea is the individual points on this graph are irrelevant.

$1$:$36$

You know, if I look at for a size problem $18,$ this blue one looks a little bit better than the dark dashed one.

$1$:$41$

But in the long run, the dark one is a better algorithm than the blue one.

$1$:$48$

So the analysis of algorithms concerned when n gets large. It's not a predicted runtime for a certain size problem,

$1$:$52$

it's to compare algorithms to find the one that grows most slowly as the problem size gets larger.

$2$:$00$

So that's just one main thing to kind of remember. Throughout this course, we're going to start out with talking a lot about sorting algorithms.

$2$:$07$

They're they're uh it's a easy problem to to understand what sorting is$.$

$2$:$15$

And there's a lot of interesting algorithms that we can explore, uh$,$ proving algorithms with and explore,

$2$:$20$

uh$,$ the algorithm that analysis both for sequential algorithms and for recursive algorithms.

$2$:$26$

So again, the basic problem definition here is a mathematical form.

$2$:$32$

Uh$,$ you have a sequence of items, uh$,$ and the outlets, the input,

$2$:$35$

the output is some sort of permutation of those items such that in this permutation the first item is less than or equal,

$2$:$39$

the second item is less than the third item. So you're kind of assuming that the items have to have a way to compare them.

$2$:$46$

Uh$,$ if you're just given a bunch of colors, you have to be told, how are you going to compare those colors?

$2$:$51$

Maybe it's by$,$ you know, their intensity or hue or something like that.

$2$:$56$

If you're given people, uh$,$ people's names, it would be alphanumeric, uh$,$ you know, sorting by name or something.

$3$:$00$

So that's the general problem definition. Now, why do we need to understand the general problem definition?

$3$:$06$

Well, usually if you look at the general problem definition,

$3$:$11$

you can start to come up with ways to describe the size of the problem without worrying about how to solve that problem.

$3$:$14$

And so if you think about sorting in this way that it's just a permutation of the input,

$3$:$22$

you can kind of understand that the problem size is the number of possible permutations of the input.

$3$:$26$

So if we have five items, there's actually $120$ different permutations of those five items.

$3$:$33$

And so if there's $120$ permutations there could be more than one that's sorted if

$3$:$40$

there's equal items but there's at least one of those permutations is sorted.

$3$:$44$

If we go to ten items, how much bigger is ten factorial than five factorial?

$3$:$48$

It's a lot bigger. It's exponential growth. So you can see the sorting problem in general just by problem.

$3$:$53$

Definition of the size of the problem exhibits exponential growth.

$3$:$59$

So if you remember from your discrete math class, you probably talked a lot about combinations of permutations.

$4$:$03$

And well, this is why we need to know this. It's to define the size of the problem given a general problem definition.

$4$:$07$

Now we're also, as I mentioned before, we're going to spend some time to prove algorithms correct.

$4$:$16$

And for iterative algorithms there's a approach called loop invariance to use to prove that an algorithm is correct.

$4$:$21$

And what a loop invariant by the name loop invariant. What that implies is an invariant is something that's unchanging.

$4$:$28$

So a