Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
0
votes
1answer
67 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
53 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
113 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 ...
1
vote
1answer
37 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
10 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 ...
0
votes
0answers
16 views

Proof of Hungarian Algorithm Matrix Formulation

Can someone explain or give a reference as to how the Hungarian Algorithm in its matrix formulation always gives a correct answer? I've seen proofs of correctness of the bipartite matching formulation,...
2
votes
1answer
111 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
53 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
40 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
0answers
13 views

Verification conditions for Hoare

I am reading about Hoare logic but I don't really understand the verification conditions part for proving partial correctness. What's happening between step 1 to 2? Why do we ignore the Q := 0 and ...
0
votes
1answer
38 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
57 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
330 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 ...
1
vote
2answers
90 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 ...
3
votes
1answer
71 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
84 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
104 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 ...
0
votes
0answers
24 views

Is it the right way to find preorder successor in a binary search tree?

I am confused about the case when the given node is a leaf. The code below does seem to work, but if someone asked me to prove the correctness I'd probably fail. Basically, can someone tell me why <...
0
votes
0answers
21 views

How to write the invariants for one version of binary search insertion point (or leftmost entry) algorithm?

If we compare the binary search algorithm (leftmost or insertion point) on Wikipedia: Algorithm 1: ...
1
vote
0answers
75 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
70 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
16 views

Proving a Hoare Triple does not hold

I have this program specification annotated with a Hoare Triple. Trying to prove that is the case. ...
0
votes
0answers
40 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
62 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
637 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
31 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
28 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 ...
4
votes
2answers
254 views

Is asymptotic ordering preserved when taking log of both functions?

In one of my exercise sheets I have the following question; Let $f,g\colon \mathbb{N}\longrightarrow\mathbb{R}$ be positive functions with $f(n) \in O(g(n))$. Prove or disprove; $\ln(f(n)) \in O(\ln(...
0
votes
0answers
57 views

Making change optimally

Consider that a currency system has $k$ denominations $d_0, d_1, ... d_{k-1}$. $d_0, d_1, ... d_{k-1}$ are such that $d_0 < d_1 < ... < d_{k-1}$ and $d_i$ divides $d_j$ for all $0<=i<j&...
2
votes
0answers
66 views

Interval partitioning problem different approach - arrange lectures in minimum number of classrooms

The problem of scheduling lectures in minimum number of classrooms is as follows: Find minimum number of classrooms to schedule all lecture so that no two occur at the same time in the same room. The ...
1
vote
0answers
97 views

How to prove program solves the problem?

I am preparing for the exam on Theory of Programming class. Now I am trying to solve the task from the sample paper: Task description starts here Given the following problem: A problem is given by ...
0
votes
0answers
26 views

Using induction vs invariants to prove correctness of algorithms

In my algorithms class I have generally been proving algorithms by induction. So for example, given some algorithm $A(n)$ that computes $x$, I show that the algorithm works for some base case, say $A(...
0
votes
1answer
486 views

how to prove correctness of this BFS algorithm?

Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that ...
0
votes
1answer
24 views

Loop invariant initialisation confusion

Consider the algorithm LastMatch below, which returns the offset (shift) of the last occurrence of the pattern P in text T, or -1 if P does not occur in T: ...
0
votes
0answers
73 views

Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm: ...
1
vote
1answer
70 views

Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

The problem is in this other question. Why does this always work? It's not clear to me how one would use induction. For $n = 3$, a quick calculation shows it works, however, I don't think it ...
0
votes
0answers
34 views

Using Hoare logic to show an invariant holds or using induction?

I want to know if given a while loop: x = 0 while(x < 5){ x = x + 1 } I want to show that x (at the a ith iteration of the loop), the value of i is ...
1
vote
0answers
33 views

Where to get proofs of open problems checked? [closed]

I have found what I believe is a proof of related to an open problem in computer science. I've written it up in LaTeX, and I am looking for a way to get it evaluated. I know that cs.se/cstheory.se ...
0
votes
0answers
35 views

Linearithmic solution to finding closest pairs in an array of N elements

I am reading Algorithms 4ed by Sedgewick and Wayne. I came across this algorithm design question that asks the following: Write a program that given an array of N integers, finds a closest pair: two ...
0
votes
1answer
80 views

Confusion about assignment axiom in Hoare logic

I wanted to know if we are given the f.f.g. Hoare triple: {x = 43}x := x + 1{x = 44} How do we show that this is a valid Hoare triple? My attempt was: Using the assignment axiom: {x + 1 = 43} x := ...
3
votes
1answer
180 views

Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one. A greedy algorithm for this would keep removing digits ...
1
vote
1answer
87 views

In-place matrix transposition using rotations

Some time ago I invented an algorithm for in-place matrix transposition using rotations. A matrix of size N×M is represented as a one-dimensional array of size N*M, which is also the future storage ...
1
vote
1answer
28 views

Dubins TSP NP-hardness proof detail

In Le Ny et al.'s paper On the Dubins Traveling Salesman Problem (https://tinyurl.com/y59f7d8x) the authors prove, among other works, that the Dubins Traveling Salesman Problem (DTSP) is NP-hard. I ...
3
votes
3answers
60 views

Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
4
votes
1answer
133 views

Mistake in a proof of termination phase of Simplex algorithm in CLRS?

There is a pseudo-code for Simplex algorithm in CLRS: The proof consists from three-part loop invariant: Proof We use the following three-part loop invariant: At the start of each iteration of the ...
3
votes
1answer
278 views

Understanding Correctness of Bidirectional Dijkstra

I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10: https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%...
1
vote
1answer
109 views

Do the minimum spanning trees of a graph have the same number of edges with a given weight?

I'm asking about the answer here: Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight? I didn't understand the best answer here Choose edge $e \in ...
0
votes
1answer
167 views

Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths

The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below. The notation ...
0
votes
0answers
95 views

Alternative proof of the fact that heapify can be linear-time

As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness. Firstly, I ...

1
2 3 4 5 6