Skip to main content

Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
user438409385's user avatar
0 votes
1 answer
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 ...
H.Okan's user avatar
  • 101
1 vote
1 answer
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 ...
rranjik's user avatar
  • 284
1 vote
0 answers
41 views

Subset sum backtracking algorithm correctness proof

I'm trying to prove that the algorithm for subset sum, that is the algorithm that given a set of numbers $\\{x_1, \dots, x_n\\}$ and a number $K$ find if there is a subset $\\{x_{1_k}, \dots, x_{n_k}\\...
aram's user avatar
  • 111
0 votes
2 answers
68 views

Correctness proof of bubble sort(bogus proof)

I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction. Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for ...
user146551's user avatar
1 vote
1 answer
132 views

Resolution on weakening rule by derived clause

How to prove that every clause that is implied by the input formula (learned or not) can be derived using resolution with weakening rule: $\frac{C} {C \vee D}$ (A clause $C$ is implied by $F$ if for ...
A. H.'s user avatar
  • 510
0 votes
0 answers
126 views

Interval scheduling; sort by ending times

You have $n$ events on your calendar, defined as intervals with a start time $s_i$ and a finish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$...
Lipid's user avatar
  • 9
1 vote
0 answers
46 views

Is there a proof for camerinis algorithm for finding a minimum bottleneck spanning tree?

Does someone know a proof for Camerinis Algorithm for finding a minimum bottleneck spanning tree? To my knowledge its the only algorithm that performs in linear time to solve this task but I cant find ...
identicon's user avatar
1 vote
1 answer
87 views

Disconnection of a directed and weighted graph

Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive. In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$. The question asks to find a ...
Daniel's user avatar
  • 93
0 votes
2 answers
58 views

Proving the correctness of a sorting algorithm that contains a whole loop

I am preparing for my algorithm and data structures exam. In the code below, I need to prove the correctness of tripSort for arrays of a size >=3. I am trying to do that by using loop invariants. ...
Arugo's user avatar
  • 59
0 votes
0 answers
19 views

Proving Optimal Greedy Algorithms [duplicate]

How is the best way to go about proving that a greedy algorithm is optimal, inductive vs contradiction, are there parts in the proof that are key to include. I did not feel that the lesson I was ...
James's user avatar
  • 1
5 votes
1 answer
141 views

Closures break induction in correctness proof of interpreter

I'm trying to prove the correctness of an interpreter for a simple extension of untyped lambda-calculus with De Bruijn indices. The interpreter is bounded, i.e. in order to ensure its finiteness it ...
mell_o_tron's user avatar
1 vote
1 answer
54 views

Proof of correctness for Binary Search algorithm to find length of array for unknown length

For the algorithm provided in answer to this question, how would I go about proving the correctness of the algorithm? The referenced question is: “You are given an array $A$ of length $n$. Each value ...
Hugh Mann's user avatar
0 votes
1 answer
86 views

Minimum flow in a flow network

Let $G = (V, E)$ be a flow network with a source $s$ and sink $t$. However, the constraints are a bit different: Conservation constraint is as usual. For each edge $e \in E$, we have that the flow $f$ ...
Daniel's user avatar
  • 93
1 vote
2 answers
261 views

Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by ...
Gary Drocella's user avatar
0 votes
0 answers
33 views

What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?

I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
Sanjay  Biswas's user avatar
0 votes
0 answers
237 views

Proof of The Optimality Of Greedy Algorithm for The Interval Scheduling Problem

I have this proof for the optimality of the greedy algorithm for the interval scheduling problem in my algorithms class, but I'm struggling to understand it fully, especially starting from the second ...
Mohamed Hendy's user avatar
0 votes
0 answers
35 views

How to understand this graph problem related to bracket sequence?

This problem comes from a competitive programming problem. I'll restate it(feel free to see it here): A balanced bracket sequence is a bracket sequence(including open and close only) of even length ...
MathematicsBeginner's user avatar
2 votes
2 answers
84 views

What does it mean to prove that software is bugless?

A computer science lecturer said that one should use test as programs can't be proved to be bugless. Is this true? What does it mean to prove that program is bugless? Is there a proof that it is ...
user avatar
1 vote
0 answers
65 views

Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights

I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
Pablo Messina's user avatar
0 votes
0 answers
56 views

Proof that 2 phase locking produces order preserving Conflict serializable schedules

In the book Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery there is a theorem stating that Gen(2PL) ⊂ OCSR. Can some one help to guide on ...
Abishek0398's user avatar
1 vote
1 answer
105 views

Proof of correctness of some optimization of Heap's algorithm for producing permutations

Good day. Some time ago I found a page on (en.) wikipedia about Heap's algorithm for permutations. Here it is. Original algorithm can be written as next (copy from (en.) wikipedia): ...
Forelyl's user avatar
  • 11
1 vote
1 answer
40 views

Reformulating the Given Conditions in Decidability Problems

I came across the following question: Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ? The problem $ALL_{\text{CFG}}$ that states: Given a CFG $G$ ...
RookieCookie's user avatar
0 votes
0 answers
16 views

Need help verifying the complexity of an algorithm [duplicate]

I have the following algorithm which takes as an input a non negative integer n : i = n while i > 0 do : $\,$ $\,$ $\,$ $\,$i = i - 1 $\,$ $\,$ $\,$ $\,$j = 1 $\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
pierrovoltela's user avatar
0 votes
1 answer
46 views

if f(n),g(n) =! 0 , for every n > 0 , and f(n) = Ω(g(n)) , then does this mean that 1/f(n) = O(1/g(n))

Basically what i am trying to prove is this : $f(n),g(n) \neq 0\quad , n>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $ I guess that if we take the definition of $f(...
pierrovoltela's user avatar
2 votes
4 answers
878 views

Prove optimality of greedy strategy for fewest number of stops

Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since ...
prcssngnr's user avatar
  • 127
1 vote
0 answers
93 views

Successive shortest paths with fixed costs and costs per unit

I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
Gabriel Rebello's user avatar
2 votes
0 answers
121 views

Proving a maximal bottleneck for all pairs of vertices in maximal spanning tree

Suppose we have an undirected graph $G=(V,E)$ and and it's Maximal spanning tree $T=(V,F)$ such that the edges in $F$ is the heaviest subset of edges $E$ from which you can create a spanning tree. We'...
Aishgadol's user avatar
  • 355
7 votes
1 answer
581 views

Correctness of FIPS 186-4 square test algorithm

Federal Information Processing Standard 186-4 appendix C.4 gives (without reference) an algorithm intended to test if a positive integer $C$ (which can be thousands bits) is a square: Set $n$, such ...
fgrieu's user avatar
  • 519
2 votes
2 answers
141 views

Greedy algorithm-maximal minimum average of n pairs

Lets assume $2n $ gifts such that each gift $i$ has price $a_i$ The goal is to find a partition of the gifts into $n$ pairs such that each pair $P_i=\left(a_{i_{0}},a_{i_{1}}\right)$ has maximal ...
user avatar
-3 votes
1 answer
78 views

How to prove that this is NP complete

I have the following problem: Given an undirected graph with n vertices v1,…,vn, a positive integer weight on each edge, and a n×n symmetric matrix Rij. The objective is to find a subset S of the ...
Anonymous Molecule's user avatar
0 votes
1 answer
193 views

How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?

I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero. What ...
Tita's user avatar
  • 225
0 votes
1 answer
186 views

Struggling to find loop invariant in power function

I am struggling to find a good loop invariant for the following function, which returns a^b where a is a real number and b is a natural number: ...
Jeremy's user avatar
  • 3
0 votes
3 answers
296 views

Minimising maximum sum algorithm

Given a list of integers NUMS and an integer k (buckets), we must allocate every integer from NUMS to some bucket such that maximum of sum of integers across all buckets is minimised. A simple ...
Ajax's user avatar
  • 163
0 votes
1 answer
109 views

Correctness vs Proof of Correctness

Assuming we are observing an algorithm.I am confused as to how one needs to proof correctness. What exactly the correctness represent for a given algorithm? And why do we have to proof correctness, in ...
imbAF's user avatar
  • 185
1 vote
1 answer
184 views

shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/). Everything in the first part of the proof (The section ...
Sebastian Nielsen's user avatar
0 votes
1 answer
63 views

Is this a good proof of correctness?

I am currently being introduced to algorithms and I am trying to learn about showing the correctness. For training I chose the very basic linear-search algorithm and I would like to know if this is a ...
Niklas Klein's user avatar
1 vote
1 answer
150 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 ...
Tryer outer's user avatar
0 votes
1 answer
716 views

Finding the loop invariant for Array Reversal

I've been assigned to find the loop invariant for the following code: ...
ifiht's user avatar
  • 103
1 vote
1 answer
353 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 ...
Rohit Singh's user avatar
2 votes
0 answers
310 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 ...
universityofwashingtoncoder's user avatar
2 votes
1 answer
57 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
2 votes
1 answer
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 ...
user3472's user avatar
  • 207
1 vote
0 answers
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 ...
Krishna M.V.'s user avatar
0 votes
1 answer
89 views

Isabelle (rule disjE) disjunction elimination rule

...
Ricardo Boza's user avatar
2 votes
1 answer
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 $\...
EJoshuaS - Stand with Ukraine's user avatar
1 vote
0 answers
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 ...
Rusurano's user avatar
1 vote
2 answers
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 ...
Fred Jefferson's user avatar
0 votes
2 answers
842 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?
Kashish's user avatar
1 vote
2 answers
156 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 ...
user624's user avatar
  • 57

1
2 3 4 5
8