Questions that ask for or about correctness proofs of algorithms.

learn more… | top users | synonyms

4
votes
1answer
228 views

Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows: Cycle Property: For any cycle C in the graph, if the weight of an edge e of C is larger than the ...
1
vote
0answers
17 views

Proof of Randomized Self-Adjusting Binary Search Tree

I developed a randomized self-adjusting binary search tree years ago, which I called a shuffle tree, but was unable to ever have it published because my proofs were rejected (with little explanation). ...
2
votes
2answers
72 views

How to go about proving an algorithm correct?

The algorithm (called as rmax(1,n)) finds the maximum of a list of numbers contained in an array S[1..n]. ...
3
votes
1answer
240 views

Binary Indexed Trees: Why does i & -i work?

I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to ...
0
votes
1answer
39 views

Understanding a proof in the sweep line algorithm when finding all line segment intersections

You have a set of line segments and you want to find all intersections. First sweep line approach: Use a priority queue Q for the events as they come, where each ...
3
votes
3answers
490 views

Rigorous Proof of Insertion Sort

Currently I self study CLRS book (Outside of any course, so I got no access to an instructor) And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal. Here's the algorithm: ...
0
votes
0answers
76 views

stuck on proving the optimality of a greedy algorithm [closed]

I'm Ph.D. student doing research in wireless networks. My past projects are more oriented to systems than theory. For my current project, I devised a greedy algorithm for an optimization problem. ...
1
vote
1answer
49 views

Proving correctness of an AVL-Tree colouring algorithm

I came up with the following recursive algorithm to colour the nodes of an AVL tree so that the resulting tree is red-black. The logic is that the algorithm first colours the root and, recursively, ...
5
votes
1answer
105 views

Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
0
votes
2answers
85 views

How to show that this algorithm for evaluating polynomials works?

I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..." How do I exactly show ...
0
votes
2answers
45 views

Hoare Calculus Incorrect Assignment Axiom

I'm currently preparing for an exam and recently came across the following exercise and would like to know whether my solution would be correct. Exercise: Prove that the following axiom is not ...
43
votes
11answers
5k views

How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
1
vote
2answers
292 views

Proof of an Optimal substructure in Dynammic Programming?

Could someone please explain how exactly the proof of optimal substructure property in dynamic programing problems works?, they usually say that " let's say the global optimal solution is A, and B is ...
-2
votes
1answer
27 views

why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm

We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists. ...
0
votes
1answer
112 views

Concept used in the proof [closed]

In the paper "Resolution for Quantified Boolean Formulas", I am unable to understand the proof of theorem 3.4. Please help me with the basic concept used on page 4: The concept that I am referring ...
1
vote
0answers
28 views

Conjecture about a matrix column swapping challenge problem

So here is the challenge problem statement: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1512 Basically, given a 0/1 matrix, you ...
8
votes
6answers
213 views

Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?

On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April: '"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a ...
1
vote
2answers
304 views

Correctness proof of greedy algorithm for 0-1 knapsack problem

We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an ...
3
votes
0answers
71 views

Maximum Weight Independent Set in Circular-Arc Graphs (Proof of A Lemma)

I am reading the paper: "Maximum Weight Independent Set Of Circular-Arc Graphs and It's Applications" (http://link.springer.com/article/10.1007%2FBF02832044). And I had a question regarding the proof ...
1
vote
1answer
49 views

Proving the correctness of an algorithm, which computes the connectivity of a directed graph

Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not ...
2
votes
1answer
169 views

How can we minimize the total distance of cross pairs in an array

Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized. The first thought ...
-1
votes
2answers
253 views

Proof of Correctness of Prim's algorithm [duplicate]

what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case? Is it because of after any number of steps, $S$ might not be in a sub ...
3
votes
1answer
150 views

Viterbi algorithm recursive justification

I have a question regarding recursion in Viterbi algorithm. Define $\pi(k; u; v)$ which is the maximum probability for any sequence of length $k$, ending in the tag bigram $(u; v)$. The base case ...
3
votes
2answers
95 views

Is there a proof of the recursive algorithm for generating all permutations of a sequence?

For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible ...
0
votes
1answer
75 views

What is wrong in this proof? [closed]

I stumbled upon this wikipage that has got this proof : I rechecked sum rule of differentiation. And i can not understand where is this wrong. Any Tips ? I think that the second line x^2 = x + ...
0
votes
1answer
82 views

trouble with bijection definition [closed]

I have a bijection problem that I cannot get my head around. It goes like this: let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g ...
5
votes
3answers
167 views

Is it possible to prove thread safety?

Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove ...
4
votes
1answer
127 views

Theory of multi-label classification

Multi-label classification is a machine-learning problem where each sample can have zero or more labels from a closed set of possible labels. This task has applications in several fields. For example, ...
0
votes
2answers
2k views

Prove correctness of recursive Fibonacci algorithm, using proof by induction

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction. Here is my ...
0
votes
1answer
2k views

Proving greedy choice property of fractional knapsack

A typical way of proving the greedy choice property of the fractional knapsack problem is as follows: From Slide 5 of this link: Given: A set of items $I = \{I_1,I_2..I_n\}$ with weights ...
5
votes
1answer
154 views

Question about the formal proof of the inorder traversing

In Don Knuth's famous series of books, The Art of Computer Programming, section 2.3.1, he describes an algorithm to traverse binary tree in inorder, making use of an auxiliary stack: T1 ...
0
votes
0answers
61 views

Prove a bisimulation relation

I need to prove a bisimulation relation on $CA_{\tau}(N)$ (communication algebra with tau-steps) and names $N$. It need to prove that $p!d.x||p?d.y$ is bisimular with $p!d.(x||p?d.y)+p?d.(p!d.x||y)$ ...
1
vote
1answer
70 views

For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?

Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of ...
1
vote
0answers
569 views

Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
0
votes
1answer
270 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
136 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 ...
7
votes
1answer
609 views

A procedure for Topological sort, proof for its correctness

Definition: A preserved invariant of a state machine is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$, then $P(r)$ holds. ...
1
vote
3answers
96 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
3answers
149 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: ...
0
votes
1answer
154 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?
3
votes
1answer
184 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
1k 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
40 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
592 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
168 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
228 views
5
votes
1answer
261 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
1k views

Prove correctness of recursive multiplication algorithm

I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together: ...
2
votes
2answers
89 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 ∈ ...
4
votes
1answer
431 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. ...