Questions tagged [correctness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers

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 ...
Pablo Messina's user avatar
-5 votes
1 answer

Defining a correct halt decider

Redefining the notion of a halt decider: (a) Returns true when it correctly determines that its input halts (b) false for everything else including: (1) Non-halting (2) Not a TM description (3) ...
polcott's user avatar
  • 61
5 votes
1 answer

Correctness of AKS algorithm for shortest vector problem

Short question In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true? for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise ...
Hilder Vitor Lima Pereira's user avatar
1 vote
0 answers

Proof of Correctness of Bottleneck Dijkstra Algorithm [closed]

I am working on a bottleneck multicast tree for which I am using bottleneck Dijkstra algorithm. My question is 1) bottleneck Dijkstra has the same correctness as that of (simple) Dijkstra or not ? 2)...
Ali's user avatar
  • 11
0 votes
0 answers

Hoare program correctness

Which is the easiest way to find a valid Invariant for a While Program in the Hoare program correctness verification? Is there a "guided" way to do that?
Nk SP's user avatar
  • 131
0 votes
0 answers

Correctness proof of recursive-descent recognizer

Let G be a grammar that contains no left-recursive rules, and we use a recursive-descent recognizer that uses full backtracking, using list of results for example, to recognize strings of G. How ...
Wickoo's user avatar
  • 386
5 votes
2 answers

Is there a mathematical analysis/proof available for correctness of solutions to inter process communication problems?

I've been going over some material related to IPC recently from Tanenbaum's "Modern Operating Systems" and revisited semaphore after many years. There is a lot of code and pseudo code based ...
vin's user avatar
  • 161