I'm trying to solve problem 50 on Project Euler. Don't give me the answer or solve it for me, just try to answer this specific question. The goal is to find the longest sum of consecutive primes that adds to a prime below one million. I wrote a sieve to find all the primes below n, and I have confirmed that it is correct. Next, I am goi...
Hello everyone, I have to check if the following language is context free: L2={a^n * b^m * c^n * d^(n+m) :m>=0 n>=0 } Please help, I am totally stuck and I have to hand it over on Monday. ...
Hello We have 2 languages which are (informally) semantically equivalent but syntactically different. One is xml and another is script based. How can I go about formally proving that both languages are in fact equivalent. Script approach is just a convenient way to write a same program that would be tedious to write in xml. Thanks Keta...
I'm doing some research, and looking to create a simple on-line business card creator. I need to give users the ability to pick a business card template and then update the text with their own information. Then I need to create a PDF proof for the user to sign off on, as well as create a hi-rez pdf for print. Can anyone point me in the ...
How can I prove that the number of interval nodes in a binary tree with n leaves (where each interval node has two children) is n-1, using induction? ...
I failed at reading RWH; and not one to quit, I ordered Haskell: The Craft of Functional Programming. Now I'm curious about these functional proofs on page 146. Specifically I'm trying to prove 8.5.1 sum (reverse xs) = sum xs. I can do some of the induction proof but then I get stuck.. HYP: sum ( reverse xs ) = sum xs BASE: sum ( r...
Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP. Could someone explain how this proof works for us less mathematically inclined people? ...
From what I've read about cpython it seems like it does reference counting + something extra to detect/free objects pointing to each other.(Correct me if I'm wrong). Could someone explain the something extra? Also does this guarantee* no cycle leaking? If not is there any research into an algorithm proven to add to reference counting to ...
I know that the relation n = Big-O(1) is false. But if we use induction involving Big-O it can be proved. But the fallacy is we cannot induct Big-O. But my question is how we can disprove the relation by using the constants. The false proof is here, please give me the proof of it being false using the constants. I'm getting confused wit...
I am currently reading an Algorithm's book and came across the Stable Matching Problem. And a question came to mind that I'm curious about, but the book doesn't answer. In every SMP is it possible to always have one pair where each prefers the other one the most? Like in the classic marriage example. Is there always a pair that have one ...
I would to prove the following example: n^k = O (c^n) for every k and c>1 It is noticeable that the polynomial function grows faster than exponential function. We try to find k0 > 0 satisfying the condition fn > = k0 * g(n) Than n^k <= k0 * c^n log(n^k) <= log (k0 * c^n) log(n^(k/n)) <= log (k0 * c) k0 >= 1/c*n^(k/n) So, k0 > 0,...
For my algorithm analysis course, I've derived from an algorithm the function f(n) = n^2 - n + 2. Now I need to prove or disprove f(n) ∈ O(n). Obviously it's not, so I've been trying to disprove that for a few hours and can't figure out how to do it. To disprove it, I need to prove the negative: ∀M > 0, ∀N > 0, ∃n > N s.t. n^2 - n + 1 ...
Possible Duplicate: What book to use to learn Algorithms and Data Structures ? I need a good book on algorithms with mathematical proofs of the complexity and the algorithm itself. Can you recommend me one? ...
Is it possible to prove by induction that the two's complement of any string of 0's will always result in 0, for all sequences of length n? I'm trying to do this using the value formula, i.e. value = -a_n-1 x 2^(n-1) + summation{i=0 to n} (a_i x 2^i), where n = number of bits in string ...
I'm trying to prove the following by induction: sum(k*2^(H-k), k = 0 .. H) = N-H-1 it's a problem for an algorithms class. I was thinking I could do what I normally do for summations, which is to assume that it works for some P(m) and then increment the sum for P(m+1) and work backwards by adding to the right side what the additional ...
pseudocode: void recursive('k'){ // 'k' and 'i' vertices sumA = 0; sumB = 0; for each non visited 'i' neighbor do{ recursive('i'); sumA = sumA + b['i']; sumB = sumB + max(a['i'], b['i']); } a['k'] = 1 + sumA; b['k'] = sumB; } void main(){ a = b = 0; //initialize tables with 0 (zeros) recursive('X'); ...