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,813 questions
1
vote
0
answers
27
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
65
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
39
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
145
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
35
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
-1
votes
0
answers
27
views
algorithm vs decidable versus recognisable
I was reading sipser’s book and I know by the church turing thesis that during machines are equivalent to informal descriptions of algorithms.
In chapter 4, we are looking at decidability, suppose we ...
- 1
0
votes
0
answers
14
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
43
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 ...
- 163
1
vote
1
answer
73
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
24
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
2
votes
1
answer
45
views
Akra–Bazzi notation detail
In general, why can we take
$$T(n) = T(n/5) + T(4/5 n) + \Theta(n),$$
and then in the Akkra–Bazzi formula, use $n$ instead of $\Theta(n)$?
- 21
0
votes
0
answers
52
views
How to count increasing 4-item-subsequences of a given array by divide and conquer?
Given a positive integer $n$ and numbers $a_1$, $a_2\dots$, $a_n$, devise an algorithm by divide and conquer to count increasing subsequences of length $4$, i.e. quadruples $(x_1,x_2,x_3,x_4)$ such ...
- 101
1
vote
0
answers
25
views
Polynomial time algorithms for double cosets in symmetric group
Let H and K be 2 subgroups of the symmetric group $S_n$. What is the best known algorithm for calculating coset representatives of the double coset of H and K in $S_n$. Is there a polynomial time ...
