Questions tagged [correctness-proof]
Questions that ask for or about correctness proofs of algorithms.
356
questions
1
vote
4
answers
109
views
Prove optimality of greedy strategy for fewest number of stops
Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since ...
- 17
1
vote
0
answers
76
views
Successive shortest paths with fixed costs and costs per unit
I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
- 111
1
vote
0
answers
31
views
Proving a maximal bottleneck for all pairs of vertices in maximal spanning tree
Suppose we have an undirected graph $G=(V,E)$ and and it's Maximal spanning tree $T=(V,F)$ such that the edges in $F$ is the heaviest subset of edges $E$ from which you can create a spanning tree.
We'...
- 295
7
votes
1
answer
577
views
Correctness of FIPS 186-4 square test algorithm
Federal Information Processing Standard 186-4 appendix C.4 gives (without reference) an algorithm intended to test if a positive integer $C$ (which can be thousands bits) is a square:
Set $n$, such ...
- 489
0
votes
0
answers
15
views
Changing the order of assignment in a state machine algorithm for Best Time to Buy and Sell Stock problem
Here's a smaple solution to Best Time to Buy and Sell Stock III problem:
...
- 101
2
votes
2
answers
65
views
Greedy algorithm-maximal minimum average of n pairs
Lets assume $2n $ gifts such that each gift $i$ has price $a_i$
The goal is to find a partition of the gifts into $n$ pairs such that each pair $P_i=\left(a_{i_{0}},a_{i_{1}}\right)$ has maximal ...
- 212
-3
votes
1
answer
58
views
How to prove that this is NP complete
I have the following problem: Given an undirected graph with n vertices v1,…,vn, a positive integer weight on each edge, and a n×n symmetric matrix Rij. The objective is to find a subset S of the ...
0
votes
1
answer
61
views
How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?
I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero.
What ...
- 225
0
votes
0
answers
55
views
Proving that a greedy algorithm is correct using an exchange argument
I am trying to make a greedy algorithm for filling boxes. The rules are as follows:
1. Each box and item has an associated weight/capacity.
2. An item only fits into a box if its weight is less than ...
0
votes
1
answer
59
views
Struggling to find loop invariant in power function
I am struggling to find a good loop invariant for the following function, which returns a^b where a is a real number and b is a natural number:
...
- 3
0
votes
3
answers
96
views
Minimising maximum sum algorithm
Given a list of integers NUMS and an integer k (buckets), we must allocate every integer from NUMS to some bucket such that maximum of sum of integers across all buckets is minimised.
A simple ...
- 135
0
votes
1
answer
61
views
Correctness vs Proof of Correctness
Assuming we are observing an algorithm.I am confused as to how one needs to proof correctness.
What exactly the correctness represent for a given algorithm?
And why do we have to proof correctness, in ...
- 185
1
vote
1
answer
45
views
shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true
I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/).
Everything in the first part of the proof (The section ...
1
vote
1
answer
55
views
Is this a good proof of correctness?
I am currently being introduced to algorithms and I am trying to learn about showing the correctness. For training I chose the very basic linear-search algorithm and I would like to know if this is a ...
- 13
1
vote
1
answer
47
views
Correctness of bft resulting in shortest path
I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path:
source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf
The ...
- 55
0
votes
1
answer
209
views
Finding the loop invariant for Array Reversal
I've been assigned to find the loop invariant for the following code:
...
- 103
0
votes
0
answers
30
views
Correctness implication graph for 2-sat
i want to proof some stuff for the 2-sat problem.
So we have something like this:
$\varphi$ = (x$_{1}$ $\lor$ y$_{1}$) $\land$ (x$_{2}$ $\lor$ y$_{2}$) $\land$ ... $\land$ (x$_{n}$ $\lor$ y$_{n}$). We ...
- 11
1
vote
1
answer
281
views
Formal Proof on why Greedy isn't working on one Particular Problem
Problem
You are given two integer arrays nums and multipliers of size n and ...
- 251
2
votes
0
answers
53
views
How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?
I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it.
So a k-core of a ...
2
votes
1
answer
40
views
Check if a string can be obtained by a sequences of insertion of "abc"
Let $a$ initially be an empty string. One can transform $a$ into $b$ in the following way: $a$ becomes $a_{left}+$"$abc$"$+a_{right}$, where $a=a_{left}+a_{right}$ in a prior state. $a_{left}...
user137116
2
votes
1
answer
129
views
Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct
This problem is from LeetCode.
You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k ...
- 1
0
votes
0
answers
73
views
Is this greedy algorithm optimal?
Let $T=(V,E)$ be a tree and let $k$ be a natural number. The problem is to find the largest set of vertices $S \subseteq V$ such that $(*)$ every path in $T$ consists of at most $k$ vertices from $S$.
...
- 13
1
vote
0
answers
57
views
Proof for Queue in BFS consists of vertices of distance k and k+1
For any vertex v reachable from s, BFS computes a shortest path
from s to v (no path from s to v has fewer edges).
In order to prove the above proposition, The author of the book has stated that we ...
- 11
0
votes
1
answer
71
views
2
votes
1
answer
52
views
How did the following derivation of the final weight of a weight-balanced search tree node after rotation to make it balanced occur?
I was reading section 3.2 of Advanced Data Structures by Peter Brass (which is about weight-balanced search trees) for self-study. I got stuck on a proof about rebalancing properties.
$\alpha$ and $\...
1
vote
0
answers
37
views
What is known about the possibility of making a program to validate another program for correctness?
I'm having a question inspired by exercise 14 from section 1.2.1 of Donald Knuth's The Art of Computer Programming. It's phrased in the following way:
(R. W. Floyd) Prepare a computer program that ...
- 13
1
vote
2
answers
339
views
finding a greedy algorithm that maximizes total energy of fruits subject to expiry dates
This problem is based off of the following problem on stack overflow: https://stackoverflow.com/questions/64797299/greedy-algorithm-to-maximize-score. The second answer is incorrect because the ...
- 279
0
votes
2
answers
337
views
Proving the correctness of an algorithm
What is the logic behind using a loop invariant proof for proving the correctness of an algorithm? How is it proved that using the loop invariant proof indeed proves the correctness of a loop?
- 3
0
votes
2
answers
88
views
Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?
Question:
Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers.
We use an algorithm that loops through all the ...
- 37
1
vote
0
answers
33
views
How can I prove the correctness of the Hoshen–Kopelman algorithm?
I'd like to formally prove the correctness of Hoshen–Kopelman algorithm (link here https://en.wikipedia.org/wiki/Hoshen%E2%80%93Kopelman_algorithm). Anyway I don't know what is the right approach. At ...
0
votes
1
answer
56
views
Factorial Formulae proof (from Algorithm Design Manual)
I'm going through Algorithm Design Manual and it didn't take long before I hit a proof I don't understand. Can anyone point me in the right direction?
From the book:
Problem: Prove that $\sum_{i=1}^n ...
- 103
2
votes
1
answer
64
views
Another proof of a codeforces problem
Link to the problem: https://codeforces.com/problemset/problem/1221/A.
The problem:
You are playing a variation of game 2048. Initially you have a
multiset $S$ of $n$ integers. Every integer in this ...
2
votes
1
answer
99
views
Looking for a proof on why my algorithm in codeforces works
I'm trying prove the correctness of my algorithm.
This is the problem in codeforces: https://codeforces.com/contest/1428/problem/C
Here's my code in C++ which was accepted:
...
2
votes
2
answers
459
views
Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations
Problem Description: We have an array of $n$ positive integers and in one operation we have to choose two elements in the array and decrease them by $1$. (Elements on which we are performing this ...
- 21
2
votes
1
answer
60
views
Intuitive proof that all planar graphs are disk contact graphs
Planar graphs are graphs which can be drawn on the plane without edges crossing.
Disk contact graphs are graphs obtained as follows. Place some disks in the plane without overlaps, allowing touching. ...
- 665
1
vote
1
answer
149
views
Prove that the following algorithm for division and remainders of natural numbers is correct
I am currently brand new to the correctness proof method, and have stumbled upon this algorithm which I find very tricky.
Prove that the following algorithm for division and remainders of natural ...
- 11
0
votes
1
answer
88
views
Mechanically proving element non-membership
I'm facing a (possibly simple) problem while proving a theorem.
I need to show that under several (true) assumptions, some element is not in a set. Such assumptions are all met and there is are ...
- 169
-1
votes
1
answer
142
views
Proving correctness for greedy algorithm in string removal problem
Problem Statement:
You are given a string s and two integers x and y. You can perform two types of operations any number of times.
Remove substring "ab" and gain x points.
For example, when ...
- 39
0
votes
0
answers
39
views
Deletion in B Trees
Given a B-Tree that contains the keys $k$ and $2k$, we know the height
of the tree will be reduced if we delete the key $k$.
Prove or disprove: The height of the tree will also reduce if we
remove $2k$...
- 221
0
votes
1
answer
51
views
Proving upper/lower bound
$f (n) = Θ(f (n/2))$
The counter example in the solutions was $f(n)=\sqrt{n}$.
But then we get for every $n\ge n_{0}$
$\sqrt{n}\le c_{0}\sqrt{\frac{n}{2}}\ \ ->\ \ n\le c_{0}^{2}\cdot\frac{n}{2}\ \...
- 221
3
votes
1
answer
77
views
PetersonNP, mechanical mutual exclusion proof
Good day everyone,
I'm currently trying to carry out the PetersonNP (a.k.a. FilterLock) correctness proof (mutual exclusion).
I've found several proof sketches on concurrency books but I'm interested ...
- 169
1
vote
1
answer
123
views
Proof of approximation ratio for approximate triangle inequality version of k-center
Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
- 190
0
votes
1
answer
147
views
Prove Edited Algorithm of Bellman–Ford?
Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.
I am stuck on this question for a week and hope to get some ...
- 13
0
votes
0
answers
88
views
Is correctness implied by an optimality proof?
New to proofs (in the context of analysis of algorithms).
I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
- 101
0
votes
0
answers
145
views
Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem
Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem.
I understand how the solution is implemented but,...
- 101
-1
votes
1
answer
248
views
Proof of Correctness : Arranging the sheep
I've come across a question in Codeforces contest 719(Div - 3).
The problem goes like this :
I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
-1
votes
1
answer
52
views
Is clause learning in SAT parsimonius?
I have a model counting program bob. On some graph coloring formulas, bob got the right answer only after removing clause learning. That is to say, with clause learning, bob sometimes counts ...
6
votes
1
answer
962
views
Why does the Huffman coding algorithm produce a valid tree?
I am not asking about the Huffman Code, but the most widely described algorithm for generating one, also described on the english wikipedia: https://en.wikipedia.org/wiki/Huffman_coding#Compression
...
1
vote
1
answer
198
views
Loop invariance insertion sort algorithm
I have the following pseudo code for a insertion sort algorithm
...
- 111
1
vote
1
answer
26
views
Explain the proof of allocation problem
The problem:
There are $N$ houses for sale. The $i$-th house costs $A_i$ dollars to buy.
You have a budget of $B$ dollars to spend.
What is the maximum number of houses you can buy?
There is an ...
- 137