Algorithms

Hi guys, this is gkcs. We are going to be talking about problem solving in this video. So it's far more abstract and

Much more fun to look at in a way than thinking of a particular problem, and then you know finding an algorithm and solving it somehow

This is the video that I saw from MIT

It has Patrick Winston

Who's a professor in AI and he speaks about a few things that you can do to solve problems in general

Okay in general meaning outside of the red programming outside of everything bascially. So the first thing that you need to do is

Define the problem and

I know that in our community, There's a lot of people who get very impatient when you are defining a problem. It's more like oh, okay

Why is this even going on? Why don't you just tell me?

How exactly the problem fits into this mathematical equation and then I've solve it for you, but in real life

Defining the problem is extremely difficult

more often than not

You get a set of requirements, and you bring that down to a problem definition

So I'll give you an example

Find me all numbers which have only two factors

including themselves from 1 to 1000 that's one way to define the problem

so from 1 to 1000

number of Factors of any number

Should be equal to 2 where factor is

less than equal to

the number itself

And greater than equal to 1 okay?

pretty simple

Another way to put this is to say

find me all prime numbers

from 1 to 1,000

That's it. A much simpler way to say it. I know 99% of you had guessed this

99 percent of you did, but what if the problem is really more complicated?

What if I started putting more constraints on this. Things start getting complicated and you want to make the problem definition

simple. I don't want to go on this too much because this is a competitive programming channel

You know. It's different to explain or pick up examples from competitive Programming which have this

But this is a very important thing, and you should probably keep it in the back of your head when you're working next

Okay, where is the duster now?

The second thing you must do is

represent

all the constraints. So that is representation

We will get to this in one of the videos for AI that I'm making right now

But just understand that whatever constraints that you have in a problem if one number depends on

its properties then the way that you define that in the problem statement and in

Your you know when you're actually thinking about solution is very important

The third thing is strategy

or approach lets call it

Approach or

strategy

what does this mean? It means that this is the way that you actually approach the problem.

That was obvious. But if you say that I see a recursive solution to this that's not an algorithm yet

It's a way of thinking it's a way of picking up the program and breaking it into smaller sub parts that

is a recursive approach there's another one

Which is an iterative approach in which you come forward and say oh

I am going to be picking up to each element and solving for them, and maybe everything else is still the same

That's one way and so on and so forth so you have different strategies to look at a problem, and then right try to find its solution

Right now we have not thought about the data structure. I've not thought about

Which you know particular algorithm you can use you can use link-cut trees, segment trees

No, nothing. You just think about should we think recursively should we think iteratively

Should we think about how we're going to get the solution, [okay]?

[that's] that's the point that we have and this is very important

It does come up in competitive programming I mean in every question almost

The fourth thing you need to do is actually pick up the algorithm

This is something that is

extremely well known in our field it's

taking a problem

Using this approach you actually break it down to a set of mathematical contraints set up mathematical things that you need to do

Once it is to that point. You can actually define an

Algorithm to solve the solve the problem. Maybe use persistent Data structures. Maybe use segment trees something like that who knows

But if you know the algorithm then you can solve it now because this has become now

pute math

Lets say equations

Right over here. This has become a set of constraints

So ensure this has become a statement. A problem statement basically

After you define it you get a problem statement after you represent it you get a set of constraints

after you apply an approach or strategy you get a set of equations or a set of

Basically mathematical terms which you need to solve

Okay, Algorithm. And once this algorithm exists

Once you solve the problem, so to speak you need to experiment which in our language

Means we need to check the time complexity and correctness of the algorithm

Okay

Correctness is usually predefined if you're using the right algorithm, it will be correct, but experimentation will tell you or

analysis is

Going to be telling you if this algorithm is fast enough

Maybe you need a order N

Algorithm and you get an order N square. So through analysis you can say that is not going to work. So you change your algorithm

And what if you see that your approach is not working?

Your entire strategy is not giving you this. The best algorithms are not good enough

so then you probably need to go here, or

most probably you will be going here

And then we will be again

Following this big fat path down here. If it does not work we go back here. Till you actually solve the problem.

this is how we solve problems and

In fact this is not, how we solve problems in our

community, including me of course, we jump

We take this big leap, happy leap to right here. Oh my God? I need to learn about algorithms and data structures now

Which is how I

solve problems too. I would really like if we have a methodical approach

To pick up the representation. Then go to the approach and then so on and so forth and then you know on that analysis

We decide it's good enough or not

so this is one technique that I

learned from Patrick Winston

And he learned it from somwhere else there he had quoted the book I can't really remember what I will put in the description below

But tell me your comments on this and tell me whether you find this approach a sensible one

or it is completely practical you know can it never work in contests I find this approach very difficult to

Applying in short contests is but in long ones which are ten days or seven days long

This is one of the best things you can do

Right it uses a lot of software engineering principles also, or maybe software engineering use this

so

Yeah feel free to

To try out and tell me what you think about it

until next time, see you!