Questions tagged [loop-invariants]
Properties that hold before and after every execution of a loop. Used to prove correctness of algorithms.
89 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
1
answer
73
views
What is the loop invariant for stack-based algorithm for finding largest rectangle enclosed in a histogram?
I would like some help with proving the correctness of the following algorithm that solves LeetCode problem 84 of finding the largest rectangle enclosed by the bars of a histogram. For simplicity, we ...
-1
votes
1
answer
79
views
Loop invariant proof, nth fibonacci number
The code below calculates the nth Fibonacci number. Do you know the mathematical formula used in this algorithm? I couldn't prove the loop invariant here.
...
1
vote
2
answers
143
views
Picking high index for binary search of sorted array
The following pseudocode returns index of the given element x within sorted array A where p ...
4
votes
1
answer
125
views
Invariance Textbook Problem: Clarification Needed
I am currently reading Michael Soltys' Analysis of Algorithms (2nd Edition), and Problem 1.13 of the subsection titled Invariance reads:
Let $n$ be an odd number, and suppose that we have the set $\{...
2
votes
1
answer
122
views
"Consecutive statements" in Static control Part(SCoP)
Context:
I was reading a research paper related to polyhedral representation(citation given in last). Got confused while trying to understand the notation by implementing them with example code.
Paper ...
1
vote
1
answer
177
views
Any hints about loop invariant of weird loop?
I have this tiny program for finding largest prime divisor (taken from Code Review Stackexchange and written by user Altinak: https://codereview.stackexchange.com/a/74792):
Here is my try to write it ...
0
votes
1
answer
5k
views
MergeSort's merge function loop invariant
I am reading a proof of correctness for the MergeSort Algorithm. This is the code for the MergeSort and the Merge function:
The correctness of the MergeSort function is easy to prove since the two <...
0
votes
1
answer
251
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:
...
0
votes
1
answer
928
views
Finding the loop invariant for Array Reversal
I've been assigned to find the loop invariant for the following code:
...
0
votes
1
answer
144
views
Why is there a 'true' statement as precondition in the following loop invariant
Precondition: true
int i = 0;
while (i < a.length && a[i] != x) {
i++;
}
Postcondition: (∀ j : 0 ≤ j < i : a[j] ≠ x) ⋀ (i = a.length ∨ a[i] = x) }
As I read it, the program has no ...
1
vote
1
answer
91
views
Are there invariants in text processing problems?
I have read that when programming it is good to identify relations -- invariants -- that should hold true throughout the program, and it is good to insert assertions throughout the code to check that ...
2
votes
1
answer
241
views
What loop invariant can be used for this loop? (Algorithm to check if a sequence is stack permutable)
I've written a function that gets a permutation and checks if that permutation can be reached using a stack from an input sequence which is <1,2,3,...,n>. (we take elements from left)
For ...
0
votes
1
answer
138
views
Proving loop invariant for a possibly nonterminating while loop
I started studying through Aho, Ullman - Foundations of Computer Science as a free time exercise. In the second chapter about loop invariants and inductive proofs, there is a starred exercise.
...
0
votes
2
answers
1k
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?
0
votes
1
answer
165
views
What could be a good loop invariant for this?
I am currently new and learning about loop invariants. I have come across this pseudocode where the goal is to shift the elements inside an array with N size in a clockwise direction by K steps.
...