# Questions tagged [correctness-proof]

273 questions
Filter by
Sorted by
Tagged with
19 views

### I cannot find an invariant for the following program

I have the following: (|$y=0; x=c$|) while(x > 0){y=y+a; x=x-1;} (|$y= a*c$|) This seems like a fairly simple program and I can intuitively tell that the post ...
24 views

### Proving inequalities related to Dijkstra's algorithm

Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$. Define $IN(v)$ as the set of in-neighbors of $v$. Define $w(u,v)$ as the weight of the edge $(u,v)$. I am asked to ...
180 views

44 views

### Interval partitioning problem different approach - arrange lectures in minimum number of classrooms

The problem of scheduling lectures in minimum number of classrooms is as follows: Find minimum number of classrooms to schedule all lecture so that no two occur at the same time in the same room. The ...
95 views

### How to prove program solves the problem?

I am preparing for the exam on Theory of Programming class. Now I am trying to solve the task from the sample paper: Task description starts here Given the following problem: A problem is given by ...
22 views

55 views

### Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths

The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below. The notation ...
70 views

### Alternative proof of the fact that heapify can be linear-time

As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness. Firstly, I ...
41 views

### Finding invariant when detecting a cycle

Let consider a connected graph $G = (V, E)$ which is not oriented. One way to detect a cycle in such a graph is : Create an array : seen of size $\mid V \mid$ with seen[i] = false for all $i$ ...
73 views

### Hoare triple: Loop invariant and partial correctness

Below there is Hoare triple in which variable $a$ is an array of integers, $len$, $x, i$ are integer-valued variables, and $r$ is a Boolean-valued variable. I have to provide a loop invariant (using ...
3k views

### Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?

First Slide: Find Max(A) // INPUT: A[1..n] - an array of integers // OUTPUT: an element m of A such that m >= A[j], for all 1 <= j <= A.length max = A[j==1] for j = 2 to A.length if max < A[...
44 views

### Can we ignore the postcondition in the Hoare conditional rule when there is a return statement?

I'm proving the correctness of naive string matching using Hoare logic. I have the following pseudocode: ...
115 views

### Proving correctness of the Newton's Method for finding the square root of a number

I'm trying to prove the correctness of this simple square root calculation algorithm using SPARK: ...
619 views

### Prove that the total distance is minimised (when travelling across the longest path)

Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have ...
83 views

### Comparing locally maximal and localy minimal Hamiltonian paths [closed]

Let $K_n$ be a weighted complete graph on $n$ vertices. Two Hamiltonian paths are formed as follows. The first one, $H$, is formed by starting at an arbitrary vertex, and at each stage proceeding from ...
71 views

### Correct invariant of BFS

I am trying to find a correct invariant of BFS. If we represent a queue as $Q = [a_0;...; a_n]$ such that : $Q.pop() = a_n$ then I found the following invariant which I think is correct (we denote ...
36 views

### Correctness of an algorithm difference between recursive and iteraive

I know that the general strategy to do the correction of an algorithm is as follow : if the algorithm is recursive then prove the correctness using induction if the algorithm is iterative (...
56 views

### Find an invariant in the minimum algorithm

I have the following simple algorithm to find the smallest element of an array $A$ of numbers: ...
134 views

### Must the champion of an entire tournament beat the champion of a possible tournament among other players?

I have a list of "players" of a "tournament". Any two adjacent players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given ...
519 views

### Is my proof of my greedy algorithm to find subsequence correct?

Credit to KleinBerg and Taros Book Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
45 views

### Prove that set of operations form a commutative Monoid

this is my first post on this exchange. I am looking for some help with defining a proof that a set of operations I have designed forms a commutative monoid. (Disclaimer: I am not sure that I have ...
221 views

### Proof that G is a Tree After DFS and BFS form the same tree T [closed]

Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth first search ...
57 views

### Prove that the following algorithm has STOP property (number of steps is finite)

Prove that the following algorithm has STOP property. I am not sure if this term is widely know, so the definition of STOP property that I got during classes looks as follows: STOP property (for ...
256 views

### Iterative Fibonacci algorithm correctness proof, finding loop invariants

The algorithm take in an integer $n$ and outputs the $n$th number in the Fibonacci sequence ($F_n$). The sequence starts with $F_0$. I am trying to prove the correctness assuming valid input: ...
129 views

### Why is it true that given a monotonic heuristic function, A* can be seen as Dijkstra's algorithm where no node needs to be processed more than once?

Maybe I am missing something very easy and obvious. But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: ...
307 views

### Proof of QuickSort algorithm correctness

Recently I’ve studied QuickSort and understood its general idea. Basically, we do the following: Pick an element from the array (no matter which one and how in this context) Rearrange elements in ...
385 views

### Confused about the correctness proof of Dijkstra's algorithm

In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow: Let u be v's predecessor on a shortest path P:s->...->u->v from s to v. Then, If d(u) = δ(s,u) and edge (...
372 views

### How this proof of fractional knapsack works?

I don't understand a step in my book proving the fractional knapsack problem: Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by ...
58 views

### Proving correctness of inefficient algorithm - Path between two vertices

Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity ...
57 views

### Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...
33 views

### Prove that a recursive program satisfies a logic predicate with implication and quantifiers by induction [closed]

i have this program to prove: ...
Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH( suppose a root of rank k has at least $2^k$ vertices in ...