# Questions tagged [correctness-proof]

376 questions
Filter by
Sorted by
Tagged with
27 views

### Finding middle vertex of tree

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G ...
30 views

### breadth first search proof incomplete statement

I'm studying Breadth-First Search (BFS) from the CLRS book and I'm having trouble understanding the proof that each distance from the source node calculated by BFS is the shortest distance from the ...
• 101
1 vote
53 views

### Prove maximum score is achieved by being greedy

I have a list of tokens T, of length n. Initially I have power p and a ...
• 284
1 vote
41 views

46 views

159 views

### Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct

This problem is from LeetCode. You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k ...
• 207
1 vote
88 views

### Proof for Queue in BFS consists of vertices of distance k and k+1

For any vertex v reachable from s, BFS computes a shortest path from s to v (no path from s to v has fewer edges). In order to prove the above proposition, The author of the book has stated that we ...
89 views

...
63 views

### How did the following derivation of the final weight of a weight-balanced search tree node after rotation to make it balanced occur?

I was reading section 3.2 of Advanced Data Structures by Peter Brass (which is about weight-balanced search trees) for self-study. I got stuck on a proof about rebalancing properties. $\alpha$ and \$\...
1 vote
55 views

### What is known about the possibility of making a program to validate another program for correctness?

I'm having a question inspired by exercise 14 from section 1.2.1 of Donald Knuth's The Art of Computer Programming. It's phrased in the following way: (R. W. Floyd) Prepare a computer program that ...
• 23
1 vote
539 views

### finding a greedy algorithm that maximizes total energy of fruits subject to expiry dates

This problem is based off of the following problem on stack overflow: https://stackoverflow.com/questions/64797299/greedy-algorithm-to-maximize-score. The second answer is incorrect because the ...