# Questions tagged [correctness-proof]

278 questions
Filter by
Sorted by
Tagged with
808 views

### Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times

I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content. I recently had an university exam about Parallel Algorithms. One ...
5k views

### Example of an algorithm that lacks a proof of correctness

We have Hoare logic. Why is it still possible that an algorithm is right but there is no proof that it's correct? Suppose the algorithm is expressed in C. Then we can argue step by step that it's ...
289 views

### How can I prove that a cryptography algorithm is a pseudo-random number generator?

I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not? Is there some principles I have ...
448 views

### find if a string is periodic using a suffix tree, and prove it

A string s of length n is periodic if there is a string $u$ of length <= n/2 such that $s = u^ku'$, where $k$ is ...
150 views

### Correctness proof of the algoritm to generate permutations in lexicographic order

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place. Find the largest index k such that a[k] < a[k + 1]. ...
106 views

### What does the algorithm calculate?

We have the following ...
2k views

### What does it mean to “strengthen the precondition and weaken the postcondition” in Hoare logic?

Having learned a rough summary of Hoare logic (i.e. learning just the basic concept of Hoare triples and a few of the rules) I kept seeing a statement along these lines: The rule of consquence ...
3k views

### Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice?

What are the major causes that makes "Proving Programs correct", not a widely attractive subject? though from it's name, and from what we know from other disciplines (like mathematics) it looks like ...
864 views

### What are the flaws in this encryption algorithm?

Let $A$ be a randomly generated matrix. Let $I$ be the identity matrix. $\times$ is the matrix multiplication operation, $/$ is matrix division (multiplying the first matrix by the inverse of the ...
310 views

### Curious about an old algorithm which calculates modular inverse

I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic Background: I was searching through ...
770 views

713 views

### Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...