# Questions tagged [correctness-proof]

343 questions
Filter by
Sorted by
Tagged with
1 vote
22 views

### Correctness of bft resulting in shortest path

I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path: source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf The ...
67 views

### Finding the loop invariant for Array Reversal

I've been assigned to find the loop invariant for the following code: ...
19 views

### Correctness implication graph for 2-sat

i want to proof some stuff for the 2-sat problem. So we have something like this: $\varphi$ = (x$_{1}$ $\lor$ y$_{1}$) $\land$ (x$_{2}$ $\lor$ y$_{2}$) $\land$ ... $\land$ (x$_{n}$ $\lor$ y$_{n}$). We ...
1 vote
102 views

### Formal Proof on why Greedy isn't working on one Particular Problem

Problem You are given two integer arrays nums and multipliers of size n and ...
34 views

### How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?

I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it. So a k-core of a ...
26 views

1 vote
23 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 ...
1 vote
194 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 ...
76 views

### Proving the correctness of an algorithm

What is the logic behind using a loop invariant proof for proving the correctness of an algorithm? How is it proved that using the loop invariant proof indeed proves the correctness of a loop?
80 views

### Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?

Question: Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers. We use an algorithm that loops through all the ...
1 vote
30 views

### How can I prove the correctness of the Hoshen–Kopelman algorithm?

I'd like to formally prove the correctness of Hoshen–Kopelman algorithm (link here https://en.wikipedia.org/wiki/Hoshen%E2%80%93Kopelman_algorithm). Anyway I don't know what is the right approach. At ...
36 views

69 views

### PetersonNP, mechanical mutual exclusion proof

Good day everyone, I'm currently trying to carry out the PetersonNP (a.k.a. FilterLock) correctness proof (mutual exclusion). I've found several proof sketches on concurrency books but I'm interested ...
1 vote
95 views

### Proof of approximation ratio for approximate triangle inequality version of k-center

Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
100 views

### Prove Edited Algorithm of Bellman–Ford?

Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that. I am stuck on this question for a week and hope to get some ...
51 views

### Is correctness implied by an optimality proof?

New to proofs (in the context of analysis of algorithms). I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
113 views

### Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem. I understand how the solution is implemented but,...
198 views

### Proof of Correctness : Arranging the sheep

I've come across a question in Codeforces contest 719(Div - 3). The problem goes like this : I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
48 views

### Is clause learning in SAT parsimonius?

I have a model counting program bob. On some graph coloring formulas, bob got the right answer only after removing clause learning. That is to say, with clause learning, bob sometimes counts ...
920 views

### Why does the Huffman coding algorithm produce a valid tree?

I am not asking about the Huffman Code, but the most widely described algorithm for generating one, also described on the english wikipedia: https://en.wikipedia.org/wiki/Huffman_coding#Compression ...
1 vote
114 views

### Loop invariance insertion sort algorithm

I have the following pseudo code for a insertion sort algorithm ...
1 vote
26 views

### Explain the proof of allocation problem

The problem: There are $N$ houses for sale. The $i$-th house costs $A_i$ dollars to buy. You have a budget of $B$ dollars to spend. What is the maximum number of houses you can buy? There is an ...
1 vote
135 views

### Proof of algorithm correctness

I am studying about algorithm correctness and have enctountered this problem. ...
65 views

### Linear Search Proof of Correctness (trouble with case where $A[j] = v$ )

There's lots of answers on the proof but I didn't find anything that regarded my difficulty directly. Question ( From " Introduction to Algorithms ( Cormen ) " ): Answer ( Found on the net )...
1 vote
274 views

### How to prove the optimality of the "patience sort" algorithm?

I was trying to understand how we can solve the Longest Increasing Subsequence (LIS) problem in O(N log N) time. I came across a sorting algorithm called the patience sort algorithm. To learn it I was ...
99 views

### Curry–Howard correspondence and functional programming "reliability"

The first time I heard about functional programming, someone told me "it's more reliable to code in a functional style because your type system is like a proof of correctness". I recently ...
75 views

### Is the following Greedy algorithm to generate Gray Codes always correct?

I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites)....
1 vote
76 views

### How to prove that the pseudo-code of thresholded-A* algorithm from my teacher's book is correct?

I have the following DFS2 pseudo-code, which is used in the pseudo-code of IDA*, from my teacher's book, but I cannot understand why it's correct: ...
29 views

### Question regarding the assumptions of the No-Free-Lunch-Theorem for Search

I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf) and have a question regarding the ...
1 vote
445 views

### Floyd's Cycle Detection Algorithm Proof In Laymen

I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1). I have looked through various proofs proving that: If there is a cycle, at ...
2k views

### How to understand the solution to Task Scheduler problem on LeetCode?

LeetCode Task Scheduler problem is the following: Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any ...