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.

Filter by
Sorted by
Tagged with
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(...
Ben's user avatar
  • 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 ...
Jake's user avatar
  • 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): ...
Forelyl's user avatar
  • 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 ...
YoloV4's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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, ...
Gideon Kogan's user avatar
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 ...
Johan's user avatar
  • 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\...
Sooraj S's user avatar
  • 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 ...
ilovewt's user avatar
  • 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 ...
Mike Battaglia's user avatar
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 ...
Gabi G's user avatar
  • 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\\...
Sooraj S's user avatar
  • 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 ...
mismaah's user avatar
  • 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 ...
sleekster's user avatar
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 ...
Eric Coulthard's user avatar
-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 ...
Jorge Luiz's user avatar
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$" ...
qmww987's user avatar
  • 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 : ...
LeoC's user avatar
  • 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 ...
Aderyn Thomas's user avatar
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,...
Stefanie Gauss's user avatar
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 ...
Questions123's user avatar
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 ...
user avatar
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 ...
blademan9999's user avatar
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 ...
Helpme Guest's user avatar
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 ...
aSpagno's user avatar
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 ...
Li Haoyi's user avatar
  • 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 ...
Dixshant s's user avatar
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 (...
Olumide's user avatar
  • 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 $...
chausies's user avatar
  • 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 ...
nico263nico's user avatar
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 ...
QuantumWiz's user avatar
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 ...
Balchandar Reddy's user avatar
-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....
theateist's user avatar
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 ...
Algo's user avatar
  • 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) ...
Algo's user avatar
  • 1
-2 votes
1 answer
57 views

Programs with feedback?

Suppose we have a program like this: ...
Volpina's user avatar
  • 97
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 ...
Senthil's user avatar
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)$$ ...
John He's user avatar
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 ...
Balchandar Reddy's user avatar
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. ...
nepee's user avatar
  • 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 ...
Michel's user avatar
  • 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 ...
Βill97's user avatar
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 ...
Walrfi's user avatar
  • 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 ...
green_32's user avatar
  • 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 ...
Vandiscleisson N.'s user avatar
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 ...
mappo's user avatar
  • 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: ...
user_1234's user avatar
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 ...
Hugh Mann's user avatar
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 ...
Ezrael's user avatar
  • 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 ...
Bob Aiden Scott's user avatar

1
3 4
5
6 7
227