# Questions tagged [correctness-proof]

278 questions
Filter by
Sorted by
Tagged with
2k views

### Proof of Correctness of Prim's algorithm [duplicate]

what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case? Is it because of after any number of steps, $S$ might not be in a sub ...
114 views

### What is wrong in this proof? [closed]

I stumbled upon this wikipage that has got this proof : I rechecked sum rule of differentiation. And i can not understand where is this wrong. Any Tips ? I think that the second line x^2 = x + x ...
953 views

### A* optimality of the expanded node

Suppose I have a admissible and consistent heuristic. Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal? Look at this pseudocode from wikipedia: ...
145 views

### trouble with bijection definition [closed]

I have a bijection problem that I cannot get my head around. It goes like this: let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g ...
443 views

### Theory of multi-label classification

Multi-label classification is a machine-learning problem where each sample can have zero or more labels from a closed set of possible labels. This task has applications in several fields. For example, ...
13k views

### Prove correctness of recursive Fibonacci algorithm, using proof by induction

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction. Here is my ...
4k views

### Prove correctness of recursive multiplication algorithm

I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together: ...
11k views