New answers tagged

0 votes

$(Q\to R)\wedge (R\to Q)$ converting to sentence

IMO both you and the teacher read in a contrived way. I would say "I go to town implies that I have time and I have time implies that I go to town". Note that as this is formal logics, no ...
user avatar
  • 3,912
1 vote

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Induction on the order of G . True for |G| = 1. Assume for |G| = n let prove it for |G| = n +1. Choose a vertex v of minimum degree . Consider H = G - N[v]. Clearly a(G)> = 1 + a(H) > = 1 + sum {...
user avatar
1 vote

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

There are several non-probabilisitc proofs : 1/ using greedy algorithm deleting minimum degree : See : https://www.sciencedirect.com/science/article/pii/S0166218X13001339 https://onlinelibrary.wiley....
user avatar
1 vote

Decomposing large bit mult or exp into smaller bit operations

For product, here is the idea: $$(2^NA + B)(2^NC + D) = 2^{2N}AC + 2^N(AD+BC) + BD.$$ Exponentiation isn't a primitive operation in integer arithmetic.
user avatar
1 vote

Θ, O and Ω, and how they relate to each other as subsets

For two real numbers $a$ and $b$, either $a < b$, $a=b$, or $a>b$. This notation works analogously but orders functions by growth rates. For two functions of $n$, $f(n)$ and $g(n)$, either $f(n)...
user avatar
0 votes

Sum of average of all subarrays

The idea is provided by Yves Daoust. Here is the C++ code I implemented just now. The input format is like n a_1 a_2 ... a_n The modular number is $10^9+7$. ...
user avatar
0 votes

What is the difference between problem solving and theorem proving?Is mathematics problem solving or theorem proving?

Problem solving is the art of finding the solution(s) from a problem statement. Theorem proving is the art of showing that a known solution is indisputably correct. But if the given problem is to ...
user avatar
  • 3,912
4 votes
Accepted

Sum of average of all subarrays

Hint: This sum is a linear combination of the array elements, with varying weights . In the case of four elements, $$a+b+c+d+\frac{a+b}2+\frac{b+c}2+\frac{c+d}2+\frac{a+b+c}3+\frac{b+c+d}3+\frac{a+b+c+...
user avatar
  • 3,912

Top 50 recent answers are included