Questions that ask for or about correctness proofs of algorithms.
1
vote
0answers
35 views
how to prove this unsolvable problem about halting problem (turing machine) [duplicate]
Show that the problem of deciding, for a given TM M, whether M halts for all inputs within n^2(namely n square ) steps(n is the length of the input) is unsolvable. You can use the fact without proof ...
0
votes
1answer
39 views
Proving correctness of the algorithm for convex polygon minimum cost triangulation
I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
1
vote
1answer
43 views
While proving optimality of the A* algorithm, why can we change graphs?
In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105.
However, I cannot ...
1
vote
3answers
66 views
Loop Invariants as Tautologies
Would it be correct to characterize loop invariants as a type of tautology? I ask since the invariant must basically always be true, before the loop starts, before each iteration and after the loop ...
2
votes
2answers
44 views
A* optimality of the expanded node
Suppose I have a admissible and consistent heuristic.
Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?
Look at this pseudocode from wikipedia:
...
-1
votes
1answer
78 views
Algorithm Design Manual Question 1-7 [closed]
Skeina, The Algorithm Design Manual
Question 1-7.
Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants c ≥ 2.
...
0
votes
1answer
61 views
Can GDB debug itself?
Can GDB be run on itself? How or why not?
I see something about it http://www.math.utah.edu/docs/info/gdbint_3.html
But GDB might not be written in a language that it can debug?
2
votes
1answer
53 views
The use of multiset ordering in proving termination
Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program?
Is not the well-founded order enough?
0
votes
3answers
186 views
DFS - Proof of Correctness
I'm currently studying the book "Introduction to Algorithms - Cormen". Although a proof of correctness for the BFS algorithm is given, there isn't one any for the DFS in the book. So I was courious ...
0
votes
0answers
37 views
loop invariant proof [duplicate]
Possible Duplicate:
Proof of linear search?
I'm reading the MIT Press, Introduction to Algorithms textbook 3rd edition, and I am a bit confused by an exercise.
2.1-3
Consider the ...
1
vote
2answers
130 views
Proof of linear search?
Consider the searching problem:
Input: A sequence of $n$ numbers $A=(a_1, a_2, \ldots , a_n)$ and a value $v$.
Output: An index $i$ such that $v = a_i$ or the special value NIL if $v$ does ...
2
votes
1answer
141 views
Invariant Proof of For Loops?
From CLRS (third edition, page 19), there is a footnote:
When the loop is a for loop, the moment at which we check the loop invariant just prior to the first iteration is immediately after the ...
3
votes
1answer
79 views
5
votes
1answer
219 views
Will this algorithm terminate on any input?
One can compress data with straight-line grammars. An algorithm that employs this technique is called Sequitur. If I understood correctly, Sequitur basically starts with one rule representing the ...
5
votes
1answer
105 views
How to “prove my algorithm correct”
I'm in a first year discrete math course and we started algorithms. I had to create an algorithm to multiply two numbers together recursively, which resulted in this:
...
1
vote
2answers
58 views
Rigorous proof against pseudorandom generator
I am trying to teach myself the principles of cryptograhpy, and want to solve the following question:
Let G be the algorithm that takes an input x = (x1, . . . , xn) from
{0, 1} n (so each xi ∈ ...
3
votes
1answer
159 views
How to prove that BFS directed-graph traversal algorithm terminates?
How to prove that BFS directed-graph traversal algorithm terminates?
(I copy the pseudocode from here) Input: A graph G and a root v of G.
...
3
votes
1answer
131 views
How to prove that the pre-order tree traversal algorithm terminates?
I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that ...
4
votes
1answer
173 views
5
votes
0answers
212 views
A variation in Ford-Fulkerson algorithm
Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.
I was thinking that when we augment a ...
6
votes
1answer
108 views
Micro-optimisation for edit distance computation: is it valid?
On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:
...
7
votes
2answers
302 views
Invariant For Nested Loop in Matrix Multiplication Program
I'm making a graduate thesis about proving correctness of program for multiplying 2 matrices using Hoare logic. For doing this, I need to generate the invariant for nested loop for this program:
...
8
votes
2answers
186 views
How is the loop invariant obtained in this square root bound finding algorithm?
Originally on math.SE but unanswered there.
Consider the following algorithm.
...
