Questions tagged [correctness-proof]

Questions that ask for or about correctness proofs of algorithms.

Filter by
Sorted by
Tagged with
0 votes
0 answers
39 views

Union of non-regular and finite language

So i got this problem where should prove whether the union of a non regular language $L$ and a finite Language $L'$ is regular or not. My Idea was to show that any regular Language $L_r$ cannot be ...
Theorynoob's user avatar
0 votes
0 answers
28 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
29 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
33 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
0 votes
0 answers
40 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
37 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
93 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
39 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
28 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
28 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
33 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
1 vote
4 answers
524 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
  • 117
1 vote
0 answers
88 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
83 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
  • 315
7 votes
1 answer
579 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
0 votes
0 answers
18 views

Changing the order of assignment in a state machine algorithm for Best Time to Buy and Sell Stock problem

Here's a smaple solution to Best Time to Buy and Sell Stock III problem: ...
Sgg8's user avatar
  • 101
2 votes
2 answers
113 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
71 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
128 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
128 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
193 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
  • 155
0 votes
1 answer
91 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
107 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
60 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
108 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
484 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
329 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
145 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
52 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
145 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
76 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
86 views

Isabelle (rule disjE) disjunction elimination rule

...
Ricardo Boza's user avatar
2 votes
1 answer
54 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
41 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
438 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
614 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
0 votes
2 answers
103 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
  • 37
1 vote
0 answers
39 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 ...
Marco Malabarba's user avatar
0 votes
1 answer
66 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 ...
hackerhasid's user avatar
2 votes
1 answer
93 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 ...
MathematicsBeginner's user avatar
2 votes
1 answer
114 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: ...
MathematicsBeginner's user avatar
2 votes
2 answers
637 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 ...
Poojan's user avatar
  • 21
2 votes
1 answer
81 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. ...
J. Schmidt's user avatar
1 vote
1 answer
180 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 ...
Tarik Pašić's user avatar
0 votes
1 answer
91 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 ...
Chaos's user avatar
  • 463
-1 votes
1 answer
213 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 ...
B_math's user avatar
  • 39
1 vote
0 answers
44 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$...
MathCurious's user avatar
0 votes
1 answer
59 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}\ \...
MathCurious's user avatar
3 votes
1 answer
102 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 ...
Chaos's user avatar
  • 463

1
2 3 4 5
8