Questions tagged [correctness-proof]
Questions that ask for or about correctness proofs of algorithms.
365
questions
0
votes
0
answers
39
views
Union of non-regular and finite language
So i got this problem where should prove whether the union of a non regular language $L$ and a finite Language $L'$ is regular or not.
My Idea was to show that any regular Language $L_r$ cannot be ...
- 11
0
votes
0
answers
28
views
What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?
I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
0
votes
0
answers
29
views
Proof of The Optimality Of Greedy Algorithm for The Interval Scheduling Problem
I have this proof for the optimality of the greedy algorithm for the interval scheduling problem in my algorithms class, but I'm struggling to understand it fully, especially starting from the second ...
0
votes
0
answers
33
views
How to understand this graph problem related to bracket sequence?
This problem comes from a competitive programming problem. I'll restate it(feel free to see it here):
A balanced bracket sequence is a bracket sequence(including open and
close only) of even length ...
0
votes
0
answers
40
views
Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights
I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
- 159
0
votes
0
answers
37
views
Proof that 2 phase locking produces order preserving Conflict serializable schedules
In the book Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery there is a theorem stating that Gen(2PL) ⊂ OCSR. Can some one help to guide on ...
- 25
1
vote
1
answer
93
views
Proof of correctness of some optimization of Heap's algorithm for producing permutations
Good day. Some time ago I found a page on (en.) wikipedia about Heap's algorithm for permutations. Here it is.
Original algorithm can be written as next (copy from (en.) wikipedia):
...
- 11
1
vote
1
answer
39
views
Reformulating the Given Conditions in Decidability Problems
I came across the following question:
Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ?
The problem $ALL_{\text{CFG}}$ that states:
Given a CFG $G$ ...
- 165
0
votes
0
answers
28
views
Consolidating my proof for the merge step of mergesort
I've been spending time strengthening my ability to conduct inductive proofs and made one for the mergesort algorithm - specifically the merge part, as the entirety of the algorithm is comparatively ...
- 1
0
votes
0
answers
28
views
Trouble understanding inductive proof of Lomuto's partitioning algorithm
I'm doing a review of sorting algorithms and trying to self-learn how to prove them as well. The foundation of the quicksort proof is intuitive enough if I'm assuming that the recursion holds - but ...
- 1
0
votes
0
answers
16
views
Need help verifying the complexity of an algorithm [duplicate]
I have the following algorithm which takes as an input a non negative integer n :
i = n
while i > 0 do :
$\,$ $\,$ $\,$ $\,$i = i - 1
$\,$ $\,$ $\,$ $\,$j = 1
$\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
0
votes
1
answer
33
views
if f(n),g(n) =! 0 , for every n > 0 , and f(n) = Ω(g(n)) , then does this mean that 1/f(n) = O(1/g(n))
Basically what i am trying to prove is this :
$f(n),g(n) \neq 0\quad , n>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $
I guess that if we take the definition of $f(...
1
vote
4
answers
524
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 ...
- 117
1
vote
0
answers
88
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
2
votes
0
answers
83
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'...
- 315
7
votes
1
answer
579
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 ...
- 519
0
votes
0
answers
18
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
113
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 ...
- 232
-3
votes
1
answer
71
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
128
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
1
answer
128
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
193
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 ...
- 155
0
votes
1
answer
91
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
107
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
60
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
108
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 ...
- 47
0
votes
1
answer
484
views
Finding the loop invariant for Array Reversal
I've been assigned to find the loop invariant for the following code:
...
- 103
1
vote
1
answer
329
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 ...
- 261
2
votes
0
answers
145
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
52
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
145
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 ...
- 207
1
vote
0
answers
76
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
86
views
2
votes
1
answer
54
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
41
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
438
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 ...
- 289
0
votes
2
answers
614
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?
- 1
0
votes
2
answers
103
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
39
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
66
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
93
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
114
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
637
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
81
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. ...
- 737
1
vote
1
answer
180
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
91
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 ...
- 463
-1
votes
1
answer
213
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
1
vote
0
answers
44
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$...
- 231
0
votes
1
answer
59
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}\ \...
- 231
3
votes
1
answer
102
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 ...
- 463