SonuGupta001's blog

How much mathematical knowledge do I need to prove the correctness of a solution?
By SonuGupta001, history, 3 weeks ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

refer pranav A. sriram Combinatorics

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Math is not enough. Learn algorithm (especially graph theory)

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You may not need to be good at math but need to be good at imagination

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      Example with DP solving

      Almost all DP problems are just pattern recognition. There are 10-20 of them. But they have their own subtypes that differ.

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://youkn0wwho.academy/topic-list

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But this only the case with standard algorithms

      You'll learn ideas that are applicable more generally.

      But what about constructive algorithms, or greedy etc

      Kleinberg and Tardos covers those things. Look at the chapter on greedy algorithms.

      → Reply