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,341
questions
4
votes
2
answers
88
views
Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$
Let $W$ be a linear subspace of the vector space $V = (\mathbb{Z}/2\mathbb{Z})^n$. Let $k = \dim(W)$. For $v \in V$, define the distance from $v$ to $W$ to be $d(v,W):=\min_{w\in W} d(v,w)$ where $d(...
- 141
1
vote
0
answers
21
views
Algorithm for checking whether a set of hyperplanes covers $\mathbb{Z}_r^n$
In what follows, $r \in \mathbb{N}$ is not necessarily prime. $\mathbb{Z}_r$ is shorthand for $\mathbb{Z}/r\mathbb{Z}$.
Given a set of $h$ hyperplanes $A \vec x = b \mod r$, we can check whether the ...
- 378
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):
...
- 11
3
votes
1
answer
132
views
Number of "one neighbourhood" search trees in a graph
Consider the following algorithm: We are given a planar graph $G$. We initialise a set of vertices $S$ to an empty set. We randomly pick a vertex $v$ in $G$ and insert it in $S$. Now we keep including ...
- 73
1
vote
1
answer
100
views
High-multiplicity maximum-weight matching
There are $n$ people and $m$ jobs. We would like to assign at most one job to each person.
For each person,job pair, there is a positive value determining the fitness of this person to that job. The ...
- 5,730
1
vote
0
answers
13
views
Correlation between branchless algorithm length (Assembly) and its latency
I have recently reviewed the new article by DeepMind (Google) in Nature named "Faster sorting algorithms discovered using deep reinforcement learning". They claim that branchless algorithms, ...
- 111
1
vote
1
answer
74
views
How can this problem be solved in $O(n^{3/2}log(n))$ time?
I can solve the following problem by Jeff Erickson in $O(n^3)$(and maybe in $O(n^2logn)$) time but how is the $O(n^{3/2} log(n))$ time solution possible?
Let $D[1 .. n]$ be an array of digits, each ...
- 13
-1
votes
1
answer
71
views
Verify $n\log n=\Theta(10n\log10n)$
How do I Verify that $n\log n=\Theta(10n\log10n)$
I think I need to prove that there exists $c_1,c_2>0$ such that $c_1.g(n)\le f(n)\le c_2.g(n)$
Step 1
$$
\log n\le \log 10n\implies f(n)=n\log n\...
- 139
1
vote
1
answer
54
views
Understanding the Internal Stack Frames in a Recursive Function Call
I'm trying to understand how the system's call stack works internally when a
recursive function is called. Specifically, I'm looking at a function that
computes the maximum depth of a binary tree ...
- 113
2
votes
1
answer
43
views
Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"
I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is ...
- 837
1
vote
1
answer
45
views
Showing that nearly regular graphs have a specific $(2,O(\log n))$ ruling set with high probability
An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that ...
- 315
1
vote
1
answer
141
views
Time Complexity of Matrix Fibonacci Algorithm
In my reference, Exercise 0.4(e), Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, it is given that
$$
\begin{bmatrix}F_n\\F_{n+1}\end{bmatrix}=\begin{bmatrix}0&1\\...
- 139
-1
votes
1
answer
100
views
Algorithm to find the seating capacity on each trip within a multi stop journey
Imagine there's a boat with a fixed number of seats. The boat goes on a journey with n number of stops.
Here is a diagram of the journey where n = 4
The squares represent a stop. The lines represent ...
- 57
0
votes
1
answer
45
views
Is this Patricia tree implementation wrong?
I'm reading the chapter Radix Search of the book Algorithms (Robert Sedgwick).
I've made a simple implementation and something isn't behaving as expected.
In program ...
1
vote
2
answers
124
views
Is there an upper bound on the number of different sorting algorithms
Is there a proven upper bound on the number of possible sorting algorithms that cannot be reduced to another sorting algorithm?
Sorting algorithms with "useless steps" wouldn't count because ...
- 111
-1
votes
1
answer
71
views
With regards to algorithms what's exactly a free-primitive?
With regards to algorithms does anyone could explain what's exactly a free-primitive?
By chance is a free-primitive any kinda sorting?
I've read about that from book Algorithms Illuminated Part 1: The ...
- 107
2
votes
1
answer
76
views
How to reduce $k$-oriented problem to max flow problem?
Given an undirected graph $G$, how to reduce this problem :"Judge whether every edge of $G$ can be given a orientation such that for every vertex $v$ in $G$ has input-degree of at most $k$" ...
- 123
0
votes
1
answer
32
views
Binary search calculating complexity big o
I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book :
...
- 1
2
votes
1
answer
61
views
Minimal set of elements needed to satisfy property counts
I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain ...
0
votes
1
answer
119
views
Isn't allocating a same size array for result considered to be space complexity O(n)?
It is related to this question: https://leetcode.com/problems/product-of-array-except-self/
And assuming we cannot alter the original array, but have to allocate a same size array to store the results,...
- 101
0
votes
0
answers
35
views
Compression Gzip/7Zip
When I calculate the entropy values of files compressed with Gzip, PKZIP, 7ZIP and Winrar, I find that the compression rate of Gzip is higher than the others. The entropy value is higher (indicating ...
0
votes
1
answer
35
views
Finding the mode of a continuous distribution
I need to find the empirical mode of a sample of numbers taken from a continuous distribution (i.e. floating-point data).
I can think of using an histogram, but choosing an appropriate bin size does ...
user16034
3
votes
0
answers
67
views
What's the fastest known non-galactic algorithm for matrix multiplication of large matrices
"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
- 336
0
votes
0
answers
20
views
Bundle diameter calculation algorithm with different wire sizes accounting for twisted pairs?
Based on the same question asked here: Bundle diameter calculation algorithm with different wire sizes?
Best answer was this: https://scipython.com/blog/packing-circles-in-a-circle/
However, there are ...
0
votes
1
answer
29
views
Order list of lines to make them form a closed contour
I need to solve the following type of problem. I have a list of many connected lines forming a closed contour. These lines come as the output of a MarchingSquare algorithm. Consequently they are lines ...
- 5
1
vote
1
answer
30
views
Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?
Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?
I am trying to write a program to analyze Java programs and figure out the
transitive closure of the ...
- 125
0
votes
0
answers
27
views
Solving constrained optimization problem using PyTorch: Minimizing L1 norm of $\vec{x}$ subject to $\vec{x} = \mathbb{A^{-1}}\vec{y}$
My goal is to solve the above-constrained minimization problem where my vector to be optimized is x. The matrix A and the vector ...
1
vote
1
answer
101
views
Orthogonal connectors with non-overlapping horizontal or vertical line segments
I have an upper row of $N$ equally spaced 'units' and a lower row of $N$ equally spaced 'units'. I would like to connect any of the upper row of units to the lower units via orthogonal connectors (...
- 153
1
vote
1
answer
83
views
Finding shortest path between two points in a polygon whose vertices are given?
A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
- 532
7
votes
6
answers
3k
views
How AlphaDev improved sorting algorithms?
On the 7th of June 2023, Google DeepMind released an article about AlphaDev. AlphaDev is an evolution of AlphaZero (used to beat world champions at Go, Chess and Shogi), and it can produce assembly ...
- 81
2
votes
1
answer
71
views
A version of Bareiss algorithm or similar for symmetric matrices
A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use ...
- 86
1
vote
1
answer
75
views
Parameterized intractability relation between split and chordal graphs
I am a research scholar currently working in computational complexity. I am working on a decision problem $P$ that is known to be W[2]-hard parameterized by the solution size on split graphs. As split ...
- 162
-1
votes
1
answer
52
views
Detecting if an object reached target points
I have an object that is moving towards target points and I want to determine when it will reach or pass through them. I receive points in real time, which represent the current position of the object....
- 99
0
votes
0
answers
9
views
Expectimax Pruning
I found the following question in my book:
For probabilistic games like backgammon, where there is a resource
limit, the RB-Expectimax algorithm is used.
Assume that it is known that the heuristic ...
- 1
0
votes
1
answer
23
views
How branching factor affects complexity of Monte Carlo Tree Search?
I was reading: https://stackoverflow.com/questions/34724201/whats-the-time-complexity-of-monte-carlo-tree-search
Where it says:
The runtime of the algorithm can be simply be computed as O(mkI/C)
...
- 1
-2
votes
1
answer
57
views
0
votes
1
answer
32
views
How to generate all the possible nodes inside a polygon, if the polygon is represented by its vertices
If a polygon is represented by its vertices(latitudes, longitudes), is it possible to find all the possible points or nodes(latitudes, longitudes). If so, what kind of algorithm is used. The polygon ...
- 3
0
votes
0
answers
27
views
NURB Sphere surface degree elevation and knot insertion
The code for degree elevation of curves in The NURBS Book by Les Piegl and Wayne Tiller pages 206--209(The_NURBS_Book) assumes the knot vector for the curve is given as:
$$(0,...,0,...,1,...,1)$$
...
- 1
0
votes
1
answer
46
views
Bounded clique width graphs vs parameter clique width
I am Balchandar Reddy, a research scholar. I am currently working on the parameterized complexity of a problem for the parameter clique width. The problem is known to be polynomial-time solvable on ...
- 162
2
votes
1
answer
74
views
Algorithm to find intersection between collection of sets
I have two dataframes representing products two distributors sell. They look like this:
df1 for distributor 1.
...
- 280
4
votes
0
answers
137
views
Comparison-based computation: percentage of current software development?
Vol. III of The Art of Computer Programming, chapter 5 (Sorting, intro) mentions:
Computer manufacturers of the 1960s estimated that more than 25
percent of the running time on their computers was ...
- 592
0
votes
0
answers
36
views
how to find the right path for A* algorithm (not the real time algorithm)
Hey to everyone I am trying to understand A* algorithm not the real time A* algorithm
To understand this I created the following problem
Node s is connected with Α and the heuristic value of Α is 4 ...
- 1
0
votes
0
answers
50
views
3d algorithm - Sort multiple of 4 grid, into subsequently smaller quads
I’m working on a custom exporter for a 3d project.
I have groups of faces (quads) that are always multiples of 4, each quad could be further subdivided into another group of 4, but in the editor they ...
- 1
1
vote
1
answer
49
views
Greedy algorithms criterion/ intution
Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
- 113
2
votes
2
answers
226
views
Turing machine that splits a string into 3 equal parts in $O(n\log n)$
I have the following question: given a string $X^n$, where $n$ is divisible by $3$, how to build a one-tape Turing machine with complexity $O(n\log n)$ that splits this string into $3$ equal parts?
I ...
0
votes
0
answers
23
views
Please help me decipher the symbols in this closed-form
I want to implement the algorithm provided in this answer:
(Please see original post for details.)
It calculates every combination of making a provided amount by using coins from a provided list of ...
- 123
-1
votes
1
answer
46
views
How to calculate average hours worked from bar graph
I want to calculate average hours worked from below bar graph and following this method but I feel this method is not correct to find average working hours
Procedure A:
...
- 99
2
votes
0
answers
117
views
Difficulty in last sentence in proof of "Amortized cost of $\text{Find-Set}$ operation is $O(\alpha(n))$" from CLRS
I was reading the section of Data Structures for Disjoint Sets from the text Introduction to Algorithms by Cormen et. al. I made it through the proof, but I'm not sure I understand the very last ...
- 67
1
vote
0
answers
36
views
Algorithm for the inversion of a striped matrix with tridiagonal stripes
I'd like to compute the inverse of a matrix of size $S^2N \times S^2N$ over complex numbers that is composed of tri-diagonal $S\times S$ size blocks of tri-diagonal $S\times S$ block matrices. This ...
- 11
1
vote
0
answers
348
views
Find the number of all possibilities to visit all vertices once in a connected graph
Let $G$ be a connected undirected graph, e.g.:
u -- v -- w
\ /
x
I would like to determine the number of sequences in which every vertex of the graph is ...
- 151