Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
0
votes
1answer
35 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}\ \...
2
votes
0answers
26 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
1answer
35 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 (...
0
votes
1answer
72 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 ...
0
votes
0answers
24 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 + ...
0
votes
0answers
27 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,...
-1
votes
1answer
98 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 ...
0
votes
1answer
31 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 ...
6
votes
1answer
865 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
1answer
47 views

Loop invariance insertion sort algorithm

I have the following pseudo code for a insertion sort algorithm ...
1
vote
0answers
86 views

Prove the correctness of divide algorithm

This is the pseudocode for the algorithm: function divide($y,z$) comment Return $q,r \in \mathbf{N}$ such that $y=qz+r$ and $r<z$ where $y,z \in \mathbf{N} $ $r:=y$, $q:=0$, $w:=z$; while $w \...
1
vote
1answer
20 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
1answer
82 views

Proof of algorithm correctness

I am studying about algorithm correctness and have enctountered this problem. ...
0
votes
0answers
31 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
1answer
96 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 ...
2
votes
1answer
70 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 ...
4
votes
1answer
55 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
0answers
64 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: ...
0
votes
1answer
28 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 ...
0
votes
1answer
267 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 ...
3
votes
1answer
772 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 ...
0
votes
1answer
26 views

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

A while back I learned of these great algorithms: ...
0
votes
0answers
17 views

How do you prove that this tree path calculation function works, from first principles mathematically?

I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
0
votes
1answer
207 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 \...
0
votes
0answers
48 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,...
1
vote
4answers
174 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 ...
1
vote
1answer
72 views

Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language: $$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$ I ...
0
votes
1answer
145 views

Clarification in the proof for the Bellamn-Ford algorithm

While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma: After k (k >= 0) iterations of relaxations, for any node u that has at least one path from s (the start ...
3
votes
1answer
55 views

Beginner Question Concerning the Logic of a Very Simple Correctness Proof

I'm trying to familiarize myself with correctness proofs and need some help. In the proof for SimpleSelect (P.25), why do we assume both $A'[i] < A'[k]$ and $1 \leq i \leq k$? I'm not quite sure ...
1
vote
1answer
118 views

Approximation algorithm question, clustering on n points

So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the ...
2
votes
1answer
43 views

Sums of $2^{-l}$ that add to 1

Consider the following problem: You are given a finite set of numbers $(l_k)_{k\in \{ 1, ..., n \}}$ such that $\sum_{k=1}^n2^{-l_k}<1$. Describe an algorithm to find a set $(l'_k)_{k\in \{ 1, .....
1
vote
1answer
23 views

How proof of Hoffman algorithm greedy property starts with optimal tree T?

In this paper Claim 1 states that x and y are smallest probability and there is optimal code tree in which this two characters are siblings at the maximum depth. In proof to that claim, author starts ...
2
votes
1answer
452 views

N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its ...
1
vote
1answer
84 views

Proof for an algorithm to minimize $\max(a, b, c) - \min(a, b, c), a \in A, b \in B, c\in C$, A, B, C are arrays in ascending order

Problem Statement I came across this problem here. For given arrays $A$, $B$ and $C$ arranged in ascending order, we need to minimize the objective function $f(a, b, c) = \max(a, b, c) - \min(a, b, c)...
2
votes
1answer
61 views

In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?

In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following ...
0
votes
1answer
58 views

When does this algorithm fail?

The problem Given $n$ stacks of $k$ integers each. What is the maximum sum that can be achieved by removing exactly $p$ integers? The following example illustrates the problem. $n$ = 3, $k$ = 4, $...
-1
votes
1answer
281 views

Variations of Activity Scheduling Algorithm

I've been following Greedy algorithms in the textbook Jeff Erickson. Here is the following Question I was stuck in proving Proof of Correctness for the following variant of the standard Activity ...
2
votes
2answers
629 views

Proving correctness and optimality of a greedy algorithm

Here is a (slightly abridged) problem from Kleinberg and Tardos: Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated ...
3
votes
2answers
300 views

Proof for LeetCode: 11. Container With Most Water problem

UPDATE: I abandoned this initial approach in favor of a more powerful invariant I worked out after posting. I've detailed that one in an answer below. I'm new to algorithm correctness proof-writing ...
4
votes
2answers
555 views

Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)?

Hello I solved this leetcode https://leetcode.com/problems/tree-diameter/ question reserved for people who pay the subscription. The question: Given an undirected tree (tree is not disjoint), ...
5
votes
1answer
88 views

How come correctness proofs aren't tautological?

Consider the following function on binary trees, which is supposed to tell whether a given int is a member of a binary tree t: <...
17
votes
3answers
3k views

Can I use the following method to prove an algorithm is correct?

I'm trying to show that a solution I have obtained via an algorithm is correct. The way I plan on doing this is first by showing that an optimal solution does indeed exist. Then, I plan on showing ...
0
votes
3answers
384 views

Optimality of a Greedy Algorithm

If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you ...
1
vote
0answers
135 views

Loop invariant of a search algorithm

I have to come up with a proof of correctness of the following algorithm: GuardedSearch(A; v) Input: an array A of n numbers and a number v Output: an index i such that A[i] = v, or NotFound if no ...
0
votes
1answer
82 views

Show that a problem is NP-Complete

The problem is, K_longestPath: We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each ...
0
votes
0answers
55 views

Prove grade-school multiplication algorithm applied to binary numbers

I want to prove that the basic multiplication algorithm is correct when applied to binary numbers. I try to follow the steps described here and here but didn't succeed. The basic implementation ...
-1
votes
1answer
126 views

Semantic, total and partial correctness

I encountered the following question: Provide a definition of the semantic correctness of algorithm $A$ with respect to pre-condition $\alpha$ and post-condition $\beta$. A well-presented precise and ...
0
votes
1answer
2k views

Reduction from Vertex Cover to Dominating Set

I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles ...
0
votes
1answer
36 views

I cannot find an invariant for the following program

I have the following: (|$y=0; x=c$|) while(x > 0){y=y+a; x=x-1;} (|$y= a*c$|) This seems like a fairly simple program and I can intuitively tell that the post ...
2
votes
1answer
44 views

Proving inequalities related to Dijkstra's algorithm

Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$. Define $IN(v)$ as the set of in-neighbors of $v$. Define $w(u,v)$ as the weight of the edge $(u,v)$. I am asked to ...

1
2 3 4 5
7