New answers tagged

0 votes

Correctness proof of bubble sort(bogus proof)

BubbleSort can be expressed in a few different ways, I'm assuming you're referring to something similar to wikipedias formulation. The mistake in your proof is that you assume that sorting an $n + 1$ ...
Knogger's user avatar
  • 685
2 votes
Accepted

Resolution on weakening rule by derived clause

What proof of the completeness of resolution do you know? Chances are it can be easily adapted to this more general setting. Alternatively, you can reduce it to plain completeness. One way is as ...
Emil Jeřábek's user avatar
2 votes

Disconnection of a directed and weighted graph

The algorithm is not correct. Imagine the following graph: ...
Pål GD's user avatar
  • 15.8k
1 vote

Proving the correctness of a sorting algorithm that contains a whole loop

Assuming the input has at least length 3, you can do it in two steps: Prove the outer loop terminates. You can do this by an argument that the total number of inversions is always non-negative, and ...
orlp's user avatar
  • 12.9k
0 votes

Proving the correctness of a sorting algorithm that contains a whole loop

You can not prove this sorting algorithm as correct because it is not correct. Hint: what happens if the input contains two elements?
orlp's user avatar
  • 12.9k
3 votes
Accepted

Closures break induction in correctness proof of interpreter

You must strengthen the theorem to be proved by induction. In the $e_1e_2$ case, the current induction hypothesis just tells you that $e_1$ reduces to a closure, but not anything more about how the ...
Li-yao Xia's user avatar
2 votes
Accepted

Proof of correctness for Binary Search algorithm to find length of array for unknown length

The length of the array is $n_{min} \le n \le n_{max}$. Initially all you know is that $n_{min} = 0$ and $n_{max} = \inf$. Every step of the algorithm gives you more information. If $n_{min} = n_{max}$...
gnasher729's user avatar
  • 29.4k

Top 50 recent answers are included