Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
1 vote
1 answer
47 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
36 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
56 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
126 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
  • 498
0 votes
0 answers
100 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
37 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
72 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
  • 33
0 votes
2 answers
41 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. ...
Moh's user avatar
  • 49
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
137 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
49 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
0 answers
73 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
  • 33
1 vote
2 answers
164 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
31 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
159 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
34 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
78 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
62 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
48 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
99 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
34 views

Consolidating my proof for the merge step of mergesort

I've been spending time strengthening my ability to conduct inductive proofs and made one for the mergesort algorithm - specifically the merge part, as the entirety of the algorithm is comparatively ...
blu's user avatar
  • 1
0 votes
0 answers
37 views

Trouble understanding inductive proof of Lomuto's partitioning algorithm

I'm doing a review of sorting algorithms and trying to self-learn how to prove them as well. The foundation of the quicksort proof is intuitive enough if I'm assuming that the recursion holds - but ...
blu's user avatar
  • 1
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
37 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
794 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
91 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
114 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
135 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 ...
Danny Blozrov's user avatar
-3 votes
1 answer
76 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
166 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
174 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
270 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
104 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
169 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
1 vote
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
133 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
658 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
346 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
270 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
53 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
156 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
85 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
88 views

Isabelle (rule disjE) disjunction elimination rule

...
Ricardo Boza's user avatar
2 votes
1 answer
60 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
48 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
510 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
765 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
130 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