# 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
Filter by
Sorted by
Tagged with
88 views

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 ...
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 ...
1 vote
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-hard parameterized by the solution size on split graphs. As split ...
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....
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 ...
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) ...
57 views

### Programs with feedback?

Suppose we have a program like this: ...
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 ...
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)$$ ...
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 ...
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. ...
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 ...
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 ...
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 vote
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 ...
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 ...
23 views

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 ...
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: ...
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 ...
1 vote
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 ...
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 ...