Multithread algorithms are notably hard to design/debug/prove. Dekker's algorithm is a prime example of how hard it can be to design a correct synchronized algorithm. Tanenbaum's Modern operating systems is filled with examples in its IPC section. Does anyone have a good reference (books, articles) for this? Thanks! ...
So I saw this question and was curious as to what the Pumping Lemma was (Wikipedia wasn't much help). I understand that its basically a theoretical proof that must be true in order for a language to be in a certain class, but beyond that I don't really get it. Anyone care to try to explain it at a fairly granular level in a way underst...
Why can't a computer program be proven just as a mathematical statement can? A mathematical proof is built up on other proofs, which are built up from yet more proofs and on down to axioms - those truths truths we hold as self evident. Computer programs don't seem to have such a structure. If you write a computer program, how is it th...
I'm trying out Coq, but I'm not completely sure what I'm doing. Is: Theorem new_theorem : forall x, P:Prop /\ Q:Prop Equivalent to: Ax ( P(x) and Q(x) ) (where A is supposed to be the universal quantifier). Edit: I think they are. ...
How does one prove (forall x, P x /\ Q x) -> (forall x, P x) in Coq? Been trying for hours and can't figure out how to break down the antecedent to something that Coq can digest. (I'm a newb, obviously :) ...
Does anyone know any examples of the following? Proof developments about regular expressions (possibly extended with backreferences) in proof assistants (such as Coq). Programs in dependently-typed languages (such as Agda) about regular expressions. ...
When writing a mathematical proof, one goal is to continue compressing the proof. The proof gets more elegant but not necessarily more readable. Compression translates to better understanding, as you weed out unnecessary characters and verbosity. I often hear developers say you should make your code foot print as small as possible. Th...
Does a general proof exist for the equivalence of two (deterministic) finite state machines that always takes finite time? That is, given two FSMs, can you prove that given the same inputs they will always produce the same outputs without actually needing to execute the FSMs (which could be non-terminating?). If such a proof does exist, ...
When we start getting into algorithm design and more discrete computer science topics, we end up having to prove things all of the time. Every time I've seen somebody ask how to become really good at proofs, the common (and possibly lazy) answer is "practice". Practicing is all fine if you have the basics down, but how do you get into ...
How does one go about determining the height of a recursion tree, built when dealing with recurrence run-times? How does it differ from determining the height of a regular tree? edit: sorry, i meant to add how to get the height of the recursion tree from the recurrence relation. ...
I have a computer program that reads in an array of chars that operands and operators written in postfix notation. The program then scans through the array works out the result by using a stack as shown : get next char in array until there are no more if char is operand push operand into stack if char is operator a = pop from stack ...
Does anybody know how to prove that if two binary trees have the same inorder and preorder traversals, then they are identical? (perhaps by showing that you can't have two different binary trees with identical inorder and preorder traversals) Alternatively, show a case that would disprove this, or show why can't it be done? (I'll admit...
Martin Fowler has a Money class that has a money allocation routine. This routine allocates money according to a given list of ratios without losing any value through rounding. It spreads any remainder value over the results. For example, $100 allocated by the "ratios" (1, 1, 1) would yield ($34, $33, $33). Here is the allocate functio...
If T is a balanced BST with n elements, L its left subtree and R its right one, how can I prove that its depth is less than or equal to 2log(n) + 1? There is a proof by induction which I have but I don't get it. (I understand that stackoverflow is mainly programming oriented but I found some questions about binary search trees and dec...
Hi guys i am trying to compare 2 algorithms and thought i may try and write a proof for them !!! (my maths sucks so hence the question) Normally in our math lesson last year we would be given a question like prove: (2r + 3) = n (n + 4) then i would do the needed 4 stages and get the answer at the end Where i am stuck is proving prim...
First of all, is this only possible on algorithms which have no side effects? Secondly, where could I learn about this process, any good books, articles, etc? ...
I want to know the logic behind this statement, the proof. The C expression -x, ~x+1, and ~(x-1) all yield the same results for any x. I can show this is true for specific examples. I think the way to prove this has something to do with the properties of two's complement. Any ideas? ...
Hello, I got this formula from a data structure book in the bubble sort algorithm. I know that we are (n-1) * (n times), but why the division by 2? Can anyone please explain this to me or give the detailed proof for it. Thank you ...
I know this isn't directly related to programming, but I was wondering if anyone know how to apply the pumping lemma to the following proof: Show that L={(a^n)(b^n)(c^m) : n!=m} is not a context free language I'm pretty confident with applying pumping lemmas, but this one is really irking me. What do you think? ...
I'm reviewing my old algorithms notes and have come across this proof. It was from an assignment I had and I got it correct, but I feel that the proof certainly lacks. The question is to prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence. My proof goes as follows: Pr...