# Questions tagged [correctness-proof]

274 questions
Filter by
Sorted by
Tagged with
61 views

### Using the Consequence Rule

I have the following example that I have to prove {a>7 ^ b>=0} n:=a-b {n<a ^ a+b>=0} Using the Consequence Rule I assumed that the P is true ...
98 views

### how to prove correctness of this greedy algorithm? [duplicate]

I did exercise problem from Pittsburgh university cs department. homework. Question 8 is somewhat exciting. Q8 is solved using greedy algorithm but I have no idea how to prove. Below is Question. ...
30 views

336 views

### Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is ...
1k views

### Proof of correctness of algorithms (induction)

I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and ...
174 views

### Cards shuffling. Greedy algorithm

We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck. My idea is to create a priority queue. ...
76 views

### Boys And Girls Problem. How to prove that the algorithm is correct?

Given that, there are 10 children standing in a circle, 8 of them stand next to a boy, and 4 of them stand next to a girl. If 7 boys and 3 girls stand in the following order: GBGBGBBBBB, then 8 ...
439 views

### How to tell if a Heuristic is monotonic

I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,...