Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
1
vote
2answers
60 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 ...
1
vote
0answers
33 views
9
votes
0answers
99 views

Can we say McCarthy and Hoare had the same objective in the 60s regarding a mathematical theory of computation?

I don't think there's any way to ask a very precise question here, so this might be considered opinion based. Nevertheless, it seems the question is clear enough because I'm asking whether these two ...
0
votes
1answer
37 views

Is this a valid induction proof example ?

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 ...
0
votes
1answer
76 views

Showing that algorithm has STOP property and finding its computational complexity function

The task is to show that given algorithm has STOP property and to find its computational complexity function. $\alpha:$ $n \ge 0$ ...
1
vote
1answer
195 views

proving correctness of algorithm about graphs with DFS

I need to prove/disprove the correctness of the following algorithm: Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that ...
2
votes
1answer
53 views

Finding loop invariant of Lowest common multiple function

So I have the following function: ...
1
vote
2answers
240 views

Why is this pushdown automaton for some palindromes right?

$B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$ Solution: For example: $111$ should be accepted steps are $q_1 \to q_2$ stack: [$\$$] $q_2 \to q_2$ stack: $[\$, 1, 1]$ (using up $11$...
2
votes
0answers
39 views

Challenging exercises for proof correctness [closed]

I would like to know where I can find challenging exercises that ask to prove the correctness of an algorithm. The invariant of most of the exercises I’ve found on the internet are quite easy (...
1
vote
1answer
745 views

Confirmation of alternative correctness proof for Floyd-Warshall's all-pair shortest-path algorithm

The most common proof for Floyd-Warshall's algorithm is an induction proof on the outer-most loop, which says $\delta^k(i,j)=\begin{cases} \min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\}...
1
vote
1answer
30 views

Define a length function over $A^{*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$

Consider the following definitions LIST: $\overline{nil} \ \ \ \ \ \frac{l}{a \ l}$ $a \in A$ $A^* = \mu \widehat{LIST}, \ A^{\infty} = v \widehat{LIST}$ NAT: $\overline{0} \ \ \ \ \ \frac{x}{s(...
1
vote
1answer
220 views

Proving correctness of search algorithms

I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof. ...
1
vote
1answer
237 views

Correctness proof for greedy algorithm based on ratio

I've an issue stated as follows: We have 10000 jobs to do, each with some length $l_i$ and weight (importance) $w_i$. Our goal is to arrange the schedule of doing these jobs (in other words, ...
3
votes
1answer
44 views

Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?

As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle. My attempt is that: So this graph would be an counter example ...
3
votes
1answer
164 views

Relating a proof to a Haskell program

I am trying to relate the following integer square root theorem $\forall x: \mathbb{N}, \exists y : \mathbb{N}((y^2 \leq x) \land (x < (y+1)^2))$ and its proof to its role as a specification of ...
1
vote
1answer
454 views

Proof of a greedy algorithm concerning “Buy and Resell Problem”

"Buy and Resell Problem" can be described in the following way: There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from ...
1
vote
2answers
77 views

Array contains elements that differ by K correctness proof

I have been puzzling over an algorithm that decides whether a sorted array of numbers contains two numbers that differ by k. I do not intuitively understand why ...
1
vote
1answer
271 views

Is Loop Invariant Proof a form of Induction?

As far as I see, what computer scientists refer to as loop invariant proofs are exact replicas of induction proof. Is it true? Can I state that loop invariant proof implies an induction? Is there a ...
5
votes
2answers
1k views

Find all critical edges for minimum spanning tree

This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne. 4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to ...
0
votes
1answer
803 views

proof of correctness for greedy knapsack algorithm

I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement ...
0
votes
1answer
630 views

Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
2
votes
0answers
37 views

Maximum boundary edges amount of union of rectangles

I've read that the maximum boundary edges amount of union of $n$ rectangles, named $p$, is bounded by $p \leq n^2 + 4n$ I tried to prove this by induction, but it's seems too difficult to me, can ...
0
votes
1answer
87 views

Any proof of correctness of the Toom-Cook algorithm?

I found the toom-cook algorithm here: http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00037/Multiplication_1_print.pdf and have been trying to chase down proof of it being correct, but can't ...
0
votes
2answers
362 views

Question regarding Hoare's partitioning scheme and a slight modification to it

This is the pseudocode on wikipedia for Hoare's partitioning scheme: ...
4
votes
1answer
140 views

Prove correctness of the iterative algorithm

Description: Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying ...
2
votes
1answer
45 views

Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit

I have such a task at university: we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+...
2
votes
1answer
272 views

Correctness of lower bound proof

I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct. Given a sorted array $A$ (of $n$ ...
2
votes
1answer
258 views

How to prove the correctness of the MinDistance algorithm?

My question is about how to prove the correctness of this algorithm, I know it is not a good algorithm, it is not efficient and can be improved. How could I prove it still returns the desired value? ...
2
votes
1answer
151 views

Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?

I am trying to prove the algorithm for Question 5 in this practice exam. I am trying to prove this algorithm with the following three claims: Suppose we have a graph G, a minimum spanning tree T, ...
1
vote
0answers
78 views

Prove an algorithm. Give directed graph edge weights such that weight of every cycle is 0

I need to construct a graph with the following properties: $w(u, v)$ = $-w(v, u)$, for every edge $(u, v) \in E$ Weight of all $u \leadsto v$ paths is equal, for every $u, v \in V$ (this is zero ...
0
votes
0answers
122 views

Proof of correctness recursive reverse digit function

This is an attempt to understand better recursion. The following recursive function returns the integer obtained by reversing the digits of an input integer. I'm trying to prove its correctness: <...
3
votes
2answers
132 views

Proving an algorithm wrong

So I have this algorithm that outputs the largest value of an array: Input: $A[1,\dots,n]$, $n\geq 1$ Output: Largest value of an array ...
2
votes
2answers
53 views

Limit repetitions in randomized list with each unique element occurring n times

I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row. So with elements [0,1,2] n = ...
3
votes
0answers
95 views

Are there are satisfying explanations for why genetic algorithms work?

The following commentator writes: Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. One of the biggest reasons they fell out ...
0
votes
0answers
48 views

Loop invariant for

The programme returns the number of digits of an integer $n>0$. I still have some difficulties to understand the difference between the loop invariant condition and what the loop should actually ...
4
votes
1answer
334 views

Alternative algorithm for minimum spanning tree construction

Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an algorithm which replaces an ...
0
votes
1answer
160 views

Loop invariant condition IsPrime program

I'm new to the concept of loop invariant and I'm trying to figure out the loop invariant for a program that returns if an integer is prime and, if not, one possible factorization. My intuition is that ...
2
votes
1answer
442 views

Proving correctness of an iterative Fibonacci algorithm

One of the questions in the problem sets that I'm struggling in is this specific number that asks me to prove an iterative Fibonacci algorithm. The algorithm is written below: ...
0
votes
0answers
139 views

Counting the number of occurences - loop invariant

I'm trying to come up with loop invariant for the following program. k = a[0] m = 1 p = 1 while p < n: if a[p] == k: m += 1 p += 1 return m I ...
0
votes
0answers
2k views

proof why worst case for bubble sort is array sorted in reverse order

Question 1: Let's say we have bubble sort algorithm which sorts numbers in ascending order. Intuitively one might agree that the worst case input for this algorithm is array already sorted in ...
-2
votes
1answer
62 views

Learning to prove correctness of simple linked-list algorithms

I understand how to use linked lists, and build algorithm using them. But I don't understand how can we prove their correctness, even of simplest algorithm. I haven't even found a good tutorial ...
1
vote
1answer
171 views

True Postcondition, with true Precondition

In my exam preparation I stumbled across the follwoing exercise regarding pre and postconditions: As far as I understood the question, we need to express some condition for p, such that if that ...
0
votes
0answers
22 views

Does there exist a conservative algorithm to determine if a certain property is satisfied at a certain part of a program?

... x = a / b; For the above code, for example, is there a way to determine whether b could be zero at the time of division, ...
1
vote
1answer
146 views

Doubt with the halting problem undecidable proof

The Halting problem proof can be seen as the following programs: Ends(P, I) is a program that detects (returns true or false) if the program P will halt or not with the input I Diag( P ): is a ...
1
vote
0answers
22 views

Accounting value of Splay trees?

In Splay trees, by definition - the required element x - rises to the root of the tree, using the operations: zig, zig-zig, zig-zag. And the formula zig of the step is this: ...
196
votes
29answers
47k views

Why is writing down mathematical proofs more fault-proof than writing computer code?

I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs. It seems that this is something more ...
2
votes
0answers
87 views

How to write a theorem corresponding to an algorithm's proof of correctness? [closed]

Let $X$ be an algorithm whose correctness supposed to be proved. What is the best practice to write the corresponding theorem? For example: Theorem: Algorithm $X$ correctly computes its output.
0
votes
1answer
85 views

Proof of correctness for a triangulation-algorithm

I'm working on the following exercise: Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have ...