Questions tagged [algorithms]
An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.
11,815 questions
1
vote
1
answer
88
views
Can the maximum flow returned by Dinic's algorithm contain a positive flow cycle?
Prove or disprove: Given a maximum flow f returned by Dinic's algorithm, there does not exist a cycle in the network such that every edge on the cycle has a strictly positive flow (f(e) > 0).
My ...
- 11
-2
votes
0
answers
21
views
What the meaning of synchronization in the context of computing [closed]
What the meaning of synchronization and under it explain solution strategies
And additionally what are the models and mechanisms(semaphore,monitors,conditonal variable,rendezvous
1
vote
1
answer
43
views
Generalizing stack approach for finding lexicographically smallest subsequence with constraints
Consider the original problem: finding the lexicographically smallest subsequence of size $k$ from an array / string. I managed to write a proof that shows the monotonic stack algorithm is correct for ...
- 11
2
votes
1
answer
94
views
Lack of common patterns and algorithms in DSA
I was reading some Data structures and algorithms resources and I'm wondering why they don't mention great algorithms we use in everyday programming like filter, map and reduce instead of those ...
- 23
1
vote
0
answers
46
views
From Existence Based Conjectures to Algorithmic Construction
Many graph-theoretic (and math in general) conjectures are non-constructive. They propose the existince of a structure, without a need to find said structure. As a result, the Probabilistic Method can ...
- 11
2
votes
0
answers
108
views
Is this “ordered sibling” heap variant known? A heap-like sort maintaining parent ≥ left ≥ right
Disclosure: this question was drafted with help from ChatGPT based on my notes, implementation, and experimental results. The algorithmic idea and experiments are mine, but some of the English wording ...
- 21
0
votes
0
answers
42
views
Odd periodicity in thermodynamic noise of liquid water? (Digital signal or physical artifact?)
I’ve been performing a high-fidelity spectral analysis on (dCp/dT) (derivative of specific heat capacity) residuals for liquid water using several public datasets.I’ve noticed a subtle but persistent ...
- 1
2
votes
1
answer
149
views
Is this NP-completeness reduction from 3-set packing to a constrained equilibrium selection problem correct?
I am working on a reduction to show NP-completeness of a decision problem arising from a simple economic model.
The problem (NETWORK-EQUILIBRIUM-WELFARE) is:
Given:
a finite set of agents, each with a ...
0
votes
0
answers
36
views
Why doesn’t Lamport’s Byzantine Generals algorithm break under conflicting messages? (m=2, n=7)
I’m trying to understand the correctness of the OM(2) algorithm in the Byzantine Generals problem (with 7 generals, up to 2 traitors).
Assume the commander is loyal, and two lieutenants are traitors: ...
- 1
0
votes
0
answers
15
views
Finding if a chunked grid has split
I'm making a game that needs to have grids. These grids are dynamic and can be split into multiple grids.
How would I find if a grid has split?
I was thinking maybe I keep a list of local components (...
1
vote
1
answer
47
views
What is the optimal algorithm to recover format strings from sampled data?
I'm adding a feature to a logging library that requires me to uniquely tag certain repeated log strings, so long as they came from the same base format string.
The naive algorithm (searching for ...
- 165
1
vote
1
answer
75
views
Constructing a bitwise operation that undoes another one
Assume I have some integer $a$, and perform some kind of bitwise operation on it with $b$ to get
$$
c = a\ \operatorname{op_1} b
$$
where op could be any of AND, <...
- 119
1
vote
1
answer
38
views
Optimization problem for cutting tape into segments as evenly as possible
The Problem
There is a tape with $n$ perforations. The length between perforations is $x_i$, where $x_0$ is the length from the start to the $1$st perforation, $x_1$ is the length from $1$st ...
- 113
0
votes
1
answer
47
views
Proving the Optimality of Greedy Color Assignment to a Sequence
Recently, I participated in a coding competition. The problem that I am proposing is named "Ghostfires", which I will reformulate as follow:
Let $\Sigma = \{R, G, B\}$ be an alphabet of ...
- 103
1
vote
0
answers
28
views
What is the theoretical role of normalization layers (e.g., BatchNorm, LayerNorm) in stabilizing neural network training dynamics?
I am trying to understand the theoretical foundations behind normalization techniques such as Batch Normalization and Layer Normalization in deep neural networks.
It is often stated that these methods ...
- 11