Tag Info

226

Let me offer one reason and one misconception as an answer to your question. The main reason that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high level. Suppose that you could write a program like this: function MaximumWindow(A, n, w): using a sliding window, calculate (in O(n)) the sums of all ...

77

(I am probably risking a few downvotes here, as I have no time/interest to make this a proper answer, but I find the text quoted (and the rest of the article cited) below to be quite insightful, also considering they are written by a well-known mathematician. Perhaps I can improve the answer later.) The idea, which I suppose isn't particularly distinct from ...

70

A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases. Example: Coin denominations, $d_1,\dots,d_k$ and a number $n$, express $n$ as a sum of $d_i$:s with as few coins as possible. A naive approach is to use the largest possible coin first, and greedily produce such a sum. For ...

62

I immediately recalled an example from R. Backhouse (this might have been in one of his books). Apparently, he had assigned a programming assignment where the students had to write a Pascal program to test equality of two strings. One of the programs turned in by a student was the following: issame := (string1.length = string2.length); if issame then for ...

55

Allow me to start by quoting E. W. Dijkstra: "Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians." (from EWD498) Although what Dijkstra meant with `programming' differs quite a bit from the current usage, there is still some merit in this quote. The other answers have ...

50

Here is an algorithm for the identity function: Input: $n$ Check if the $n$th binary string encodes a proof of $0 > 1$ in ZFC, and if so, output $n+1$ Otherwise, output $n$ Most people suspect this algorithm computes the identity function, but we don't know, and we can't prove it in the commonly accepted framework for mathematics, ZFC.

46

Lamport provides some ground for disagreement on prevalence of errors in proofs in How to write a proof (pages 8-9): Some twenty years ago, I decided to write a proof of the Schroeder-Bernstein theorem for an introductory mathematics class. The simplest proof I could find was in Kelley’s classic general topology text. Since Kelley was writing for a ...

39

One big difference is that programs typically are written to operate on inputs, whereas mathematical proofs generally start from a set of axioms and prior-known theorems. Sometimes you have to cover multiple corner cases to get a sufficiently general proof, but the cases and their resolution is explicitly enumerated and the scope of the result is implicitly ...

30

The best example I ever came across is primality testing: input: natural number p, p != 2 output: is p a prime or not? algorithm: compute 2**(p-1) mod p. If result = 1 then p is prime else p is not. This works for (almost) every number, except for a very few counter examples, and one actually needs a machine to find a counterexample in a realistic period ...

25

They say the problem with computers is that they do exactly what you tell them. I think this might be one of the many reasons. Notice that, with a computer program, the writer (you) is smart but the reader (CPU) is dumb. But with a mathematical proof, the writer (you) is smart and the reader (reviewer) is also smart. This means you can never afford to get ...

23

There are indeed programs like this. To prove this, let's suppose to the contrary that for every machine that doesn't halt, there is a proof it doesn't halt. These proofs are strings of finite length, so we can enumerate all proofs of length less than $s$ for some integer $s$. We can then use this to solve the halting problem as follows: Given a Turing ...

23

Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing. Random testing As a first step, I recommend you use random testing to test your algorithm. It's amazing how effective this is: in my ...

23

One issue that I think was not addressed in Yuval's answer, is that it seems you are comparing different animals. Saying "the code is correct" is a semantic statement, you mean to say that the object described by your code satisfies certain properties, e.g. for every input $n$ it computes $n!$. This is indeed a hard task, and to answer it, one has to look ...

22

First, let us make two maybe obvious, but important assumptions: _.random_item can choose the last position. _.random_item chooses every position with probability $\frac{1}{n+1}$. In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here: For the singleton list there is only one possibility, so it is ...

21

Here's one that was thrown at me by google reps at a convention I went to. It was coded in C, but it works in other languages that use references. Sorry for having to code on [cs.se], but it's the only to illustrate it. swap(int& X, int& Y){ X := X ^ Y Y := X ^ Y X := X ^ Y } This algorithm will work for any values given to x and y, ...

18

What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter? I believe that the primary reasons are idempotency (gives the same results for the same inputs) and immutability (doesn't change). What if a mathematical proof could give different ...

16

There is a whole class of algorithms that is inherently hard to test: pseudo-random number generators. You can not test a single output but have to investigate (many) series of outputs with means of statistics. Depending on what and how you test you may well miss non-random characteristics. One famous case where things went horribly wrong is RANDU. It ...

16

This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ciphertext E and knows the corresponding message M can recover the secret key and thus decrypt all other messages that were encrypted with the same key. The ...

14

I will use the following simple sorting algorithm as an example: repeat: if there are adjacent items in the wrong order: pick one such pair and swap else break To prove the correctness I use two steps. First I show that the algorithm always terminates. Then I show that the solution where it terminates is the one I want. For the first point,...

13

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with. The proof you describe is known as the principle of strong mathematical induction and has the form Suppose that $P(n)$ is a predicate defined on $n\in \{1, 2, \dotsc\}$. If we can show that ... 12 I agree with what Yuval has written. But also have a much simpler answer: In practice softwares engineers typically don't even try to check for correctness of their programs, they simply don't, they typically don't even write down the conditions that define when the program is correct. There are various reasons for it. One is that most software engineers ... 11 You need the line C(i:j) = 0 just before the innermost loop; otherwise, the code is incorrect. Assuming that line is in place, here is the (strongest possible) invariant just before the assignment in the innermost loop: \begin{align*} C_{IJ} &= \sum_{k=1}^{n} A_{Ik}B_{kJ} & \text{for allI$and$J$such that$1\le I < i$and$1\le J\le n$} \\ \... 11 No, your algorithm doesn't work. Consider if the array A is A = [1 1 1 1 1 2 2 3 3 3 3 3 3]. Then the array B will be B = [5 5 5 5 5 2 2 6 6 6 6 6 6]. The sum of B will be 65, and the length of B will be 13, so after division, we'll get the number 5. This is equal to the first element of B, so your algorithm will output "Yes". Nonetheless, not all ... 11 There are a lot of good answers already but there are still more reasons math and programming aren't the same. 1 Mathematical proofs tend to be much simpler than computer programs. Consider the first steps of a hypothetical proof: Let a be an integer Let b be an integer Let c = a+b So far the proof is fine. Let's turn that into the first ... 10 There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it. You should do the following: Set up your (candidate) dynamic programming recurrence. Prove it correct by induction. Formulate the (iterative, memoizing) algorithm following the recurrence. 10 Cryptosystems which are algebraic in nature are amenable to algebraic cryptanalysis. If you are trying to design a secure cryptosystem for actual use, there is one important maxim that you should keep in mind: Don't design your own cryptosystem! It is easy to design weak cryptosystems. Off-the-shelf cryptosystems have withstood breaking attempts by the ... 10 I like Yuval's answer, but I wanted to riff off of it for a bit. One reason you might find it easier to write Math proofs might boil down to how platonic Math ontology is. To see what I mean, consider the following: Functions in Math are pure (the entire result of calling a function is completely encapsulated in the return value, which is deterministic and ... 9 Proving that a program is "thread safe" is hard. It is possible, however, to concretely and formally define the term "data race." And it is possible to determine whether an execution trace of a specific run of a program does or does not have a data race in time proportional to the size of the trace. This type of analysis goes back at least to 1988: ... 9 2D local maximum input: 2-dimensional$n \times n$array$A$output: a local maximum -- a pair$(i,j)$such that$A[i,j]$has no neighboring cell in the array that contains a strictly larger value. (The neighboring cells are those among$A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$that are present in the array.) So, for example, if$A$is$\$\begin{...

9

First off to answer your main question: there is no flaw in the proof. The point where you are not following the reasoning of the proof is that: E belongs to a cycle in the graph and to the MST. Not every other edge of the cycle are in the MST. If you look at your drawing, then either one of the edges towards the rest of the MST is redundant. Because ...

Only top voted, non community-wiki answers of a minimum length are eligible