Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
67 views

Finding the loop invariant for Array Reversal

I've been assigned to find the loop invariant for the following code: ...
user avatar
  • 103
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
2 votes
1 answer
26 views

Check if a string can be obtained by a sequences of insertion of "abc"

Let $a$ initially be an empty string. One can transform $a$ into $b$ in the following way: $a$ becomes $a_{left}+$"$abc$"$+a_{right}$, where $a=a_{left}+a_{right}$ in a prior state. $a_{left}...
user avatar
  • 123
2 votes
1 answer
76 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 ...
user avatar
0 votes
0 answers
70 views

Is this greedy algorithm optimal?

Let $T=(V,E)$ be a tree and let $k$ be a natural number. The problem is to find the largest set of vertices $S \subseteq V$ such that $(*)$ every path in $T$ consists of at most $k$ vertices from $S$. ...
user avatar
  • 13
1 vote
0 answers
34 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 ...
user avatar
0 votes
1 answer
49 views

Isabelle (rule disjE) disjunction elimination rule

...
user avatar
2 votes
1 answer
51 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 $\...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
0 votes
2 answers
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?
user avatar
0 votes
2 answers
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 ...
user avatar
  • 37
1 vote
0 answers
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 ...
user avatar
0 votes
1 answer
36 views

Factorial Formulae proof (from Algorithm Design Manual)

I'm going through Algorithm Design Manual and it didn't take long before I hit a proof I don't understand. Can anyone point me in the right direction? From the book: Problem: Prove that $\sum_{i=1}^n ...
user avatar
2 votes
1 answer
57 views

Another proof of a codeforces problem

Link to the problem: https://codeforces.com/problemset/problem/1221/A. The problem: You are playing a variation of game 2048. Initially you have a multiset $S$ of $n$ integers. Every integer in this ...
user avatar
1 vote
1 answer
70 views

Looking for a proof on why my algorithm in codeforces works

I'm trying prove the correctness of my algorithm. This is the problem in codeforces: https://codeforces.com/contest/1428/problem/C Here's my code in C++ which was accepted: ...
user avatar
2 votes
2 answers
163 views

Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations

Problem Description: We have an array of $n$ positive integers and in one operation we have to choose two elements in the array and decrease them by $1$. (Elements on which we are performing this ...
user avatar
  • 21
2 votes
1 answer
47 views

Intuitive proof that all planar graphs are disk contact graphs

Planar graphs are graphs which can be drawn on the plane without edges crossing. Disk contact graphs are graphs obtained as follows. Place some disks in the plane without overlaps, allowing touching. ...
user avatar
0 votes
0 answers
305 views

Bubble sort correctness proof

Given following bubble sort pseudocode, prove it's correctness. I am curious if what I have written so far is correct and I would like a feedback. ...
user avatar
  • 225
1 vote
1 answer
121 views

Prove that the following algorithm for division and remainders of natural numbers is correct

I am currently brand new to the correctness proof method, and have stumbled upon this algorithm which I find very tricky. Prove that the following algorithm for division and remainders of natural ...
user avatar
0 votes
1 answer
88 views

Mechanically proving element non-membership

I'm facing a (possibly simple) problem while proving a theorem. I need to show that under several (true) assumptions, some element is not in a set. Such assumptions are all met and there is are ...
user avatar
  • 169
-1 votes
1 answer
62 views

Proving correctness for greedy algorithm in string removal problem

Problem Statement: You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points. For example, when ...
user avatar
  • 39
0 votes
0 answers
32 views

Deletion in B Trees

Given a B-Tree that contains the keys $k$ and $2k$, we know the height of the tree will be reduced if we delete the key $k$. Prove or disprove: The height of the tree will also reduce if we remove $2k$...
user avatar
0 votes
1 answer
48 views

Proving upper/lower bound

$f (n) = Θ(f (n/2))$ The counter example in the solutions was $f(n)=\sqrt{n}$. But then we get for every $n\ge n_{0}$ $\sqrt{n}\le c_{0}\sqrt{\frac{n}{2}}\ \ ->\ \ n\le c_{0}^{2}\cdot\frac{n}{2}\ \...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 169
1 vote
1 answer
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 (...
user avatar
  • 69
0 votes
1 answer
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 ...
user avatar
  • 13
0 votes
0 answers
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 + ...
user avatar
  • 101
0 votes
0 answers
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,...
user avatar
  • 101
-1 votes
1 answer
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 ...
user avatar
-1 votes
1 answer
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 ...
user avatar
6 votes
1 answer
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 ...
user avatar
1 vote
1 answer
114 views

Loop invariance insertion sort algorithm

I have the following pseudo code for a insertion sort algorithm ...
user avatar
  • 111
1 vote
1 answer
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 ...
user avatar
  • 137
1 vote
1 answer
135 views

Proof of algorithm correctness

I am studying about algorithm correctness and have enctountered this problem. ...
user avatar
  • 225
0 votes
0 answers
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 )...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 141
3 votes
1 answer
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 ...
user avatar
  • 131
4 votes
1 answer
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)....
user avatar
1 vote
0 answers
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: ...
user avatar
  • 241
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
0 votes
1 answer
28 views

How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...
user avatar
  • 1,871
0 votes
1 answer
365 views

3Sum Why this O(nlogn) solution doesn't work?

I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \...
user avatar
0 votes
0 answers
51 views

Potential Example of an algorithm failure

I was looking an algorithm to solve a problem of finding whether and array contains a quadruple with sum = k,(k is input) mentioned at GeeksforGeeks. In one solution the approach mentioned is below,...
user avatar
1 vote
4 answers
268 views

Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less ...
user avatar

1
2 3 4 5
7