Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
2
votes
1answer
296 views

How to prove the correctness of the MinDistance algorithm?

My question is about how to prove the correctness of this algorithm, I know it is not a good algorithm, it is not efficient and can be improved. How could I prove it still returns the desired value? ...
2
votes
1answer
200 views

Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?

I am trying to prove the algorithm for Question 5 in this practice exam. I am trying to prove this algorithm with the following three claims: Suppose we have a graph G, a minimum spanning tree T, ...
1
vote
0answers
93 views

Prove an algorithm. Give directed graph edge weights such that weight of every cycle is 0

I need to construct a graph with the following properties: $w(u, v)$ = $-w(v, u)$, for every edge $(u, v) \in E$ Weight of all $u \leadsto v$ paths is equal, for every $u, v \in V$ (this is zero ...
0
votes
0answers
137 views

Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
3
votes
2answers
149 views

Proving an algorithm wrong

So I have this algorithm that outputs the largest value of an array: Input: $A[1,\dots,n]$, $n\geq 1$ Output: Largest value of an array ...
2
votes
2answers
53 views

Limit repetitions in randomized list with each unique element occurring n times

I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row. So with elements [0,1,2] n = ...
3
votes
0answers
95 views

Are there are satisfying explanations for why genetic algorithms work?

The following commentator writes: Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. One of the biggest reasons they fell out ...
0
votes
0answers
52 views

Loop invariant for

The programme returns the number of digits of an integer $n>0$. I still have some difficulties to understand the difference between the loop invariant condition and what the loop should actually ...
4
votes
1answer
401 views

Alternative algorithm for minimum spanning tree construction

Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an algorithm which replaces an ...
0
votes
1answer
305 views

Loop invariant condition IsPrime program

I'm new to the concept of loop invariant and I'm trying to figure out the loop invariant for a program that returns if an integer is prime and, if not, one possible factorization. My intuition is that ...
2
votes
1answer
579 views

Proving correctness of an iterative Fibonacci algorithm

One of the questions in the problem sets that I'm struggling in is this specific number that asks me to prove an iterative Fibonacci algorithm. The algorithm is written below: ...
0
votes
0answers
193 views

Counting the number of occurences - loop invariant

I'm trying to come up with loop invariant for the following program. k = a[0] m = 1 p = 1 while p < n: if a[p] == k: m += 1 p += 1 return m I ...
0
votes
0answers
2k views

proof why worst case for bubble sort is array sorted in reverse order

Question 1: Let's say we have bubble sort algorithm which sorts numbers in ascending order. Intuitively one might agree that the worst case input for this algorithm is array already sorted in ...
-2
votes
1answer
74 views

Learning to prove correctness of simple linked-list algorithms

I understand how to use linked lists, and build algorithm using them. But I don't understand how can we prove their correctness, even of simplest algorithm. I haven't even found a good tutorial ...
1
vote
1answer
198 views

True Postcondition, with true Precondition

In my exam preparation I stumbled across the follwoing exercise regarding pre and postconditions: As far as I understood the question, we need to express some condition for p, such that if that ...
0
votes
0answers
22 views

Does there exist a conservative algorithm to determine if a certain property is satisfied at a certain part of a program?

... x = a / b; For the above code, for example, is there a way to determine whether b could be zero at the time of division, ...
1
vote
1answer
154 views

Doubt with the halting problem undecidable proof

The Halting problem proof can be seen as the following programs: Ends(P, I) is a program that detects (returns true or false) if the program P will halt or not with the input I Diag( P ): is a ...
1
vote
0answers
23 views

Accounting value of Splay trees?

In Splay trees, by definition - the required element x - rises to the root of the tree, using the operations: zig, zig-zig, zig-zag. And the formula zig of the step is this: ...
202
votes
29answers
48k views

Why is writing down mathematical proofs more fault-proof than writing computer code?

I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs. It seems that this is something more ...
2
votes
0answers
100 views

How to write a theorem corresponding to an algorithm's proof of correctness? [closed]

Let $X$ be an algorithm whose correctness supposed to be proved. What is the best practice to write the corresponding theorem? For example: Theorem: Algorithm $X$ correctly computes its output.
0
votes
1answer
100 views

Proof of correctness for a triangulation-algorithm

I'm working on the following exercise: Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have ...
1
vote
2answers
95 views

Element wise product sum of two arrays

I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving ...
0
votes
0answers
54 views

Proof problem in Haskell with take and drop

Im learning Haskell and i want to prove take m (drop n xs) = drop n (take (m+n) xs) and drop m (drop n xs) = drop (m+n) xs Somebody can help me please? :)
3
votes
0answers
375 views

Expression of the weakest precondition of a while loop

I am interested in computing weakest preconditions (WP) of loops. If I refer to Wikipedia "Predicate Transformer semantics", the WP for e.g. total correction of a loop annotated with an invariant I ...
1
vote
0answers
79 views

Hoare correctness proof for a recursive definition of multiplication

Given the program: {y=y0 ^ y>=0} z=0; while (y>0){ z=z+x; (1) y=y-1; } {z=x*y0} I am having trouble finding the ...
0
votes
2answers
83 views

Using the Consequence Rule

I have the following example that I have to prove {a>7 ^ b>=0} n:=a-b {n<a ^ a+b>=0} Using the Consequence Rule I assumed that the P is true ...
1
vote
0answers
119 views

how to prove correctness of this greedy algorithm? [duplicate]

I did exercise problem from Pittsburgh university cs department. homework. Question 8 is somewhat exciting. Q8 is solved using greedy algorithm but I have no idea how to prove. Below is Question. ...
1
vote
0answers
32 views

Minimize number of comparisons to discover a strict total order

$S$ is a set of $n$ elements with some unknown strict total order. The goal is to discover the greatest $k$ elements, where each step consists of comparing $m\ge 2$ elements at once (so if we compare $...
4
votes
2answers
2k views

Intuitive proof for Floyd's cycle detection algorithm

I am trying to understand Floyd's cycle detection algorithm. I can see why the algorithm works. When the Hare moves twice as fast as Tortoise, if there is cycle, they will meet definitely at some ...
5
votes
3answers
2k views

How to select a binary tree node uniformly at random

The exercise I'm trying to solve is You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method ...
1
vote
1answer
394 views

Algorithm for finding 2 missing items in a stream of integers

I saw this post and wondered why the approach described in the accepted answer works. The same problem and solution is described a bit nicer here. So let's say we receive a stream of $n-2$ pairwise ...
3
votes
2answers
229 views

Prove that this solution to the Closest 3-Sum problem always works

I was working on a Leetcode problem, 3Sum Closest. I came up with a solution but struck it down because I didn't think it could be correct. But, turns out it was. I want to know why. Here's the ...
0
votes
1answer
73 views

Proof of correctness of this algorithm

Assume $A$ is an array that contains sorted integers , ie $\forall\ i,j$ where $1 \le i \le j \le |A|$, $A_i \le A_j$. The numbers do not have to be unique, and the task is to check if there is at ...
0
votes
1answer
822 views

Proof of correctness of algorithm

Can someone help me prove the correctness of this algorithm: ...
1
vote
0answers
52 views

Provably correct algorithm/CAS for checking term equalities

Within my research of term rewriting systems (TRS) I stumbled upon a paper (Siekmann, J., and P. Szabó. “The Undecidability of the DA-Unification Problem.” The Journal of Symbolic Logic, vol. 54, no. ...
4
votes
0answers
908 views

How to prove stability of sorting algorithms?

I know to prove instability, we can simply provide a counter-example. But is there a general way to prove that a sorting algorithm is stable? Could you please tell a general method and then show an ...
1
vote
1answer
87 views

Proving by induction that a function gets called n-1 times

This is the pseudo-code from the problem: ...
2
votes
0answers
31 views

Why can optimality be preserved when inserting a new conjunct into an optimally ordered conjunction of conditions? [duplicate]

In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost: where: ...
6
votes
1answer
272 views

Proof: “If the list is then k-sorted for some smaller integer k, then the list remains h-sorted”

Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, considering every hth ...
4
votes
1answer
1k views

Greedy algorithms: Minimum sum number pairing

Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair. I think the optimal pairing is obtained by sorting the original set, pairing the first element ...
1
vote
1answer
52 views

Proof that locality is sufficient in showing two graphs are isomorphic

Using the graph representation with (node, [list of neighbours]), to show that two graphs are isomorphic it is sufficient to: show that the vertices have the same degree and for every pair of ...
2
votes
1answer
406 views

How do we know INVERSIONS-COUNT algorithm implemented in balanced tree really works?

How do we know INVERSIONS-COUNT algorithm (exercise 14.1-7 from here), implemented in balanced tree really works? We assume that the tree data structure we're using is an order statistic tree which ...
0
votes
1answer
117 views

How to prove the outcome of both segment of code are equal

Is it possible to prove using induction? If possible what would be the steps to proof A=B? Main thing i want to proof is outcome of two segments of code are same. Below is the code: Segment A: <...
1
vote
0answers
485 views
2
votes
0answers
101 views

Missing assumptions in selection algorithm proof of correctness by contradiction? [duplicate]

Yes, this is homework. I need help knowing how to begin this problem: Let A be an algorithm that finds the kth largest of n elements by a sequence of comparisons. Prove by contradiction that A ...
1
vote
3answers
354 views

Prove correctness for computing the nth Fibonacci number for the pseudo code

How do we prove the correctness of this pseudo code by induction? ...
-1
votes
1answer
558 views

Why do we need optimal substructure for dynamic programming?

Cormen and others in their book on algorithms in chapter "15 Dynamic Programming" repeat again and again that we need to prove that "a problem exhibits optimal substructure". A problem exhibits ...
1
vote
1answer
231 views

Shunting-yard algorithm - proof

How can one prove that a shunting-yard algorithm always returns a correct expression in RPN? I cannot find any proof in the internet.
1
vote
3answers
199 views

Can algorithm discovery be brute forced?

Ultimately, when you compile them to machine code, algorithms are just 1's and 0's. So then - could you brute force the genesis, and thus the discovery of new, useful algorithms? Say, in pursuit of ...
1
vote
4answers
163 views

How to prove that algorithm returns the value which appears more than $n/2$ times in the array?

Given the following algorithm (pseudocode): ...