# 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.

10,004 questions
Filter by
Sorted by
Tagged with
24 views

### Building a game tree from a board game

Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....
38 views

### What are the reasons for solution assumptions behind the longest subsequence problem?

All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...": ...
23 views

24 views

### Lower bound on number of zero columns in matrix

I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...
56 views

### speed up straightforward solution using dynamic programming

i recently got onto the following problem: we consider the following array: A = [2, 3, 6, 1, 6, 4, 12, 24] we need to count the number of times these two ...
24 views

### Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
43 views

### Question about the proof of the undecidability of the Halting Problem

From what I can see, the proof of the undecidability of the Halting Problem relies on a fairly basic self-referential paradox, the simplified version being (from Wikipedia): ...
15 views

### Is ordering achieved by central server algorithm?

ME3 specifies that the first process be granted access before the second Ordering-: Requests are granted in the order they were requested. Colouris Distributed Systems book-: The reader should ...
77 views

### What is the most efficient algorithm for calculating factorials? [duplicate]

Calculating the factorial n! by the algorithm that defines it is of O(n) complexity because it requires n-1 multiplications to find the solution. Is there an algorithm that is any faster than that?
44 views

### How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?

I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
29 views

### Random splitting with fixed size range

I ran into this problem while trying to create a procedural texture algorithm. I ended up using a greedy approximation and shuffling it to hide the bias, but I was wondering if there was a way to find ...
70 views

### What is the fastest classical "period-finding" algorithm that can replace the Quantum Fourier Transform in Shor's algorithm?

Shor's algorithm uses the Quantum Fourier Transform to find the period the function a^x mod N with "a" being a constant integer less than N and N being a ...
26 views

24 views

### Polynomial time function vs polynomial time algorithm

In the book Proof Complexity By Jan Krajicek, the definition of a functional propositional proof system is given as: Definition 1: A functional propositional proof system is any polynomial time ...
28 views

### Recursive Prefix-Sums K times

I have been wondering about the following question for quite some time: You are given an array $x$. Define f(x) as the prefix sums of this array. For example, f([1,0,1]) = [1,1,2] and f(f([1,0,1])) = [...
493 views

### Algorithm notation

I am reading Nancy Lynch's Distributed Algorithms. In page 103, there is the FloodSet algorithm. Can anyone please explain what Uj mean in W := W U Uj xj (line 3 of transition function)?
12 views

### How does Sign-and-Magnitude representation allow for easier tracing of memory dumps?

Hey I've read in Wikipedia the following: Refer here link. "Sign & magnitude allowed for easier tracing of memory dumps (a common process in the 1960s) as small numeric values use fewer 1 ...
3 views

### Rank aggregation algorithm across several criteria when only the top pick in each category is known

Example setup: Assume that in a survey, $n$ users pick their top cell phone (e.g. iPhone 11, Galaxy S9 etc.) in each of $m$ categories (e.g. camera quality, cost, speed etc.). The users don't rank all ...
14 views