Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
0
votes
2answers
61 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
98 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
30 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
1k 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
1k 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
328 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 ...
2
votes
1answer
192 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
60 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
630 views

Proof of correctness of algorithm

Can someone help me prove the correctness of this algorithm: ...
1
vote
0answers
48 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. ...
3
votes
0answers
757 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
84 views

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

This is the pseudo-code from the problem: ...
2
votes
0answers
29 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
218 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
47 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 ...
1
vote
1answer
315 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
383 views
2
votes
0answers
100 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
321 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
481 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
202 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
2answers
179 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
150 views

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

Given the following algorithm (pseudocode): ...
1
vote
0answers
68 views

Proving correctness of connected algorithm

Okay, so a graph $G = (V, E)$ is (fully) connected if and only if for every pair of vertices $u, v ∈V,$ $u$ and $v$ are connected in $G$. And that if the vertex set is $V = \{0, 1, . . . , n−1\}$, ...
2
votes
1answer
87 views

Little-O: $\forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)$

So I'm assuming everyone's familiar with the definition of Big-O: \begin{align} ∃c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in N, n \geq n_0 ⇒ g(n) ≤ cf(n) \end{align} Here is ...
0
votes
1answer
1k views

Divide and Conquer majority element algorithm

The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array) I came up with this linear divide and conquer algorithm, but I'm ...
1
vote
0answers
110 views

Proof of correctness of Bottleneck Dijkstra Algorithm

I am working on a bottleneck multicast tree for which I am using bottleneck Dijkstra algorithm. My question is 1) bottleneck Dijkstra has the same correctness as that of (simple) Dijkstra or not ? ...
7
votes
2answers
807 views

Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times

I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content. I recently had an university exam about Parallel Algorithms. One ...
19
votes
5answers
5k views

Example of an algorithm that lacks a proof of correctness

We have Hoare logic. Why is it still possible that an algorithm is right but there is no proof that it's correct? Suppose the algorithm is expressed in C. Then we can argue step by step that it's ...
2
votes
2answers
282 views

How can I prove that a cryptography algorithm is a pseudo-random number generator?

I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not? Is there some principles I have ...
3
votes
1answer
81 views

Finding minimum spanning tree of a special form graph

I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form: My idea was a recursive solution: Suppose the algorithm ...
0
votes
1answer
428 views

find if a string is periodic using a suffix tree, and prove it

A string s of length n is periodic if there is a string $u$ of length <= n/2 such that $s = u^ku'$, where $k$ is ...
2
votes
0answers
143 views

Correctness proof of the algoritm to generate permutations in lexicographic order

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place. Find the largest index k such that a[k] < a[k + 1]. ...
3
votes
1answer
793 views

How to prove a greedy algorithm that uses the longest increasing subsequence?

Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...
0
votes
1answer
105 views

What does the algorithm calculate?

We have the following ...
6
votes
1answer
3k views

Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice?

What are the major causes that makes "Proving Programs correct", not a widely attractive subject? though from it's name, and from what we know from other disciplines (like mathematics) it looks like ...
3
votes
0answers
225 views

Sequence Alignment with general gap penalties: proof of optimal substructure

I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works. However, I have merely seen hand-waving explanations for the ...
0
votes
2answers
860 views

What are the flaws in this encryption algorithm?

Let $A$ be a randomly generated matrix. Let $I$ be the identity matrix. $\times$ is the matrix multiplication operation, $/$ is matrix division (multiplying the first matrix by the inverse of the ...
5
votes
2answers
309 views

Curious about an old algorithm which calculates modular inverse

I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic Background: I was searching through ...
2
votes
1answer
2k views

Correctness of algorithm to find maximum in array

I want to show correctness of "Algorithm to find maximum element in array" using induction and contradiction. ...
1
vote
0answers
757 views

Correctness of Dijkstra's algorithm

This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661). The proof makes a case that considering path $...
1
vote
0answers
336 views

Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is ...
2
votes
2answers
1k views

Proof of correctness of algorithms (induction)

I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and ...
0
votes
1answer
174 views

Cards shuffling. Greedy algorithm

We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck. My idea is to create a priority queue. ...
0
votes
0answers
76 views

Boys And Girls Problem. How to prove that the algorithm is correct?

Given that, there are 10 children standing in a circle, 8 of them stand next to a boy, and 4 of them stand next to a girl. If 7 boys and 3 girls stand in the following order: GBGBGBBBBB, then 8 ...
3
votes
1answer
439 views

How to tell if a Heuristic is monotonic

I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,...
1
vote
2answers
304 views

Prove correctness of iterative LCM algorithm

I have been trying to prove the following algorithm, without success. Here is the C-Style pseudocode: ...
2
votes
1answer
176 views

Graph splitting via an algorithm and proof of properties

Given the following function: ...