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
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
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