I am an engineering student(EE) , and I am familiar with high school math as well as the applied mathematics(thats what typically taught in an engineering degree). I am curious how much mathematical knowledge do I need to to prove the solutions/ideas and its correctness. I am familiar with basic proving techniques like, direct proof through the logic, proof by induction, proof by contradiction. But I have only studied them for the class so I cant really say I am well versed with them and may get stuck while proving some good problems.
My aim is to reach to expert or candidate master level. So which type of mathematical concepts frequently occurs in the problems of these rating ranges, and what level of mathematical maturity and proofs do I need for them so that I can efficiently solve these problems to reach to my desired level.
Thanks.
refer pranav A. sriram Combinatorics
Math is not enough. Learn algorithm (especially graph theory)
I'm learning it. But while solving the problems I see that the solution of almost every problem uses some kind of proof that why this idea works, specially problems related to DP, graph theory, constructive algorithms, greedy etc. So I thought I should learn it, how to prove an idea/solution that it will always work given the constraints.
You may not need to be good at math but need to be good at imagination
at a beginner level, you require knowledge about induction(strong/weak) and logic(to some extent). After that it's just practice. The more proofs you do for solutions/algorithms the better you get at proving.
Thanks. This seems to be a good advice. However, as I much I have observed, induction is mainly useful for DP solutions, or where we need to build our solution incrementally. like we introduce some hypothesis for n_th state, and want to see if the same hypothesis is true for n+1_th state. If thats true then it is true for every value of n. But when it comes to graphs or trees or any other kind of problems where the solution may not necessarily be built step by step. Or maybe we just want to prove some characteristic or property for the graph structure and want to see if that can lead us to correct solution i.e. we want to examine the correctness of solution, then they seems to be proven by some another strategy/methods and we may need some mathematical knowledge also. That is what I'm asking about.
Thats wrong , intuition is much more than that.
Formally a good intuition means deep and a solid understanding of a concept. However after 3-4 tries I found out it is really hard to describe what it is , here is my best take :
Intuition is some kind of "brain mapping" you get with experience. It helps you come up with starting paths to solutions , do observations without the need to prove them formally and accept some complicated observations/facts internally. Overall it enhances your problem solving skills greatly, and it definitely isnt something that just helps with dp.
I agree with you. But I think you have mistaken
inductionwithintuitionin my previous reply.oh right lol mb
Just solve problems on this site. You need to solve most of basic math ,combinatorics and probability.They are just checking your math thinking and knowledge and number theory. And watch some Errichto and Collin videos if you not started yet.And induction comes with knowledge.
In first month you will struggle and even writing solution won't help. In Second month you will solve same problems a lot faster because you solved them already. In Third month you will solve them after you just read the problem statement.
Almost all DP problems are just pattern recognition. There are 10-20 of them. But they have their own subtypes that differ.
combinatorics and graph theory is needed for problem solving, but for proving the correctness you need to know number theory — math and geometry for some problems and also you should know how to use "proof by contradiction" which is useful for proving greedy algorithms
https://youkn0wwho.academy/topic-list
In cases where you need to implement something fast and above the naive, you may compare that solution to the naive one locally through unit/auto tests.
Honestly, most of the time you don't need to proof something mathematically. I don't know math, at least /shrug
If you're already familiar with proving techniques but aren't sure how to apply them to algorithms, then you should try looking at proofs of algorithms you already know. I'd also recommend reading through the first few chapters of Algorithm Design by Kleinberg and Tardos. The problems they present aren't particularly hard but they always prove why the solution works.
Okay. But this only the case with standard algorithms, i.e. sure I can look for the proofs of standard algorithms. But what about constructive algorithms, or greedy etc. which are not so standard. How to prove them and how can we be sure that this particular solution is correct, or this idea will lead us to answer?
You'll learn ideas that are applicable more generally.
Kleinberg and Tardos covers those things. Look at the chapter on greedy algorithms.