# 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,564 questions
Filter by
Sorted by
Tagged with
28 views

### Decomposing a general polygon into simple ones

This is a question about splitting a very general kind of polygon into a list of simple polygons. Let me introduce some notions: Let an 'edge class' $E$ be a set of homeomorphic images of the unit ...
• 161
1k views

### Is this a potentially more intuitive approach to MergeSort?

I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...
• 131
29 views

### Which course is more beneficial for studying undergraduate computer science: Multivariable Calculus or Number Theory

I want to major in computer science for my undergraduate degree. I want to take one of the mathematics courses offered by Stanford ULO (https://ulo.stanford.edu/mathematics). I am unable to choose ...
15 views

### Sequencing swaps with constraints

I have an array of N numbers, and M swaps. Each swap has an index i and amount it subtracts from the ith number, and an index j and amount it adds to the jth number. It can only be applied if the ...
• 99
52 views

### Sorting Algorithm that accounts for relative difference to reduce comparisons (sorting paint samples)

I have a scenario where I want to sort a list of objects where the process of comparing two a <= b is very slow, and so I wish to minimise comparisons. My ...
• 121
11 views

### Algorithm_A-Res problem

https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Res A-RES calls for the selection of m distinct random items out of a population of size n, each item with weight. but my case is: a huge ...
26 views

### Algorithm for finding the minimum factorization of a tensor product expression

I originally asked a question on the Mathematica stack exchange on a similar topic here. But it seems like my question actually extends beyond Mathematica. The issue is the following. Let $a,b,d$ be ...
• 125
783 views

### In-Place Reordering of Doubly Linked List Nodes to Ensure Memory Contiguity

I am addressing an optimization problem involving a doubly linked list, where nodes are allocated within a contiguous memory block of fixed size $N$. Initially, the spatial locality of nodes in memory ...
704 views

### Classification of efficient and inefficient algorithms and the scientific reasoning behind them

I've been struggling with the commonly accepted notion in computer science that exponential algorithms are inefficient. The standard explanation is that they "grow exponentially in the size of ...
• 119
1 vote
26 views

• 73
42 views

### Finding maximal elements of a partially ordered set

My problem Given a partially-ordered set $(S, <)$, I want to compute the set of maximal elements $$S_{max} =\{a\in S | \nexists b \in S, a < b \}$$ while making as few comparisons as possible ...
• 73
51 views

### O-notation confusion

I'm reading CLRS and I can't understand this part: in n-100<=c why we can't choose 101 for n (and more) and any value of c that's >=1?
31 views

### Clever algorithm for ordered compact sub-grouping

I have a set of 2D points (called "seats"), with each having a scalar numerical value attached to it. I have an ordered sequence of groups, each with an integer attributed to it, such that ...
• 101
1 vote
32 views

### Does modifying input space change space complexity?

The auxiliary space analysis that involves modifying the input array can lead to "unfair" situations. Examples: Consider that an algorithm that uses O(N) memory and does not need to ...
110 views

### Deducing upper bound for Boolean Circuit size from well-known algorithms

Given an algorithm A for computing binary function $f$. Assuming that A runs in time $t(n)$, what could we say about the size of the minimal Boolean circuit C that calculates f? I think that it ...
• 231
1 vote
56 views

### How to create a tree of height $lg(n)$ using Union-Find data structure

I'm wondering given a set $A$ of $n$ numbers, is there any procedure that can create a tree of height $lg(n)$ that contain all the elements of $A$ by applying consecutive Union by rank operation in a ...
• 93
33 views

### Find, in linear time, a line that intersects all the segments and has the largest possible slope, or determine that there is no such line

I'm wondering how to approach this question. Let $e_1, \ldots, e_n$ be $n$ horizontal segments in the plane. Find, in linear time, a line that intersects all the segments and has the largest possible ...
• 31
82 views

### Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $n \times n$ Table

We have an $n \times n$ table, and in each cell of the table, there is a number from $1$ to $2n$. We want to change the numbers in some of the cells and replace them with other numbers from $1$ to ...
144 views

### Approximation algorithm for binary (linear) programs

I am interested in solving the following problem: $$\max c^\top x \qquad\text{s.t.}\\ Ax \le b\\ x \in \{0,1\}^n$$ One can assume that $c$, $A$ and $b$ have integer entries if that simplifies things....
• 555
1 vote
2k views

### Arrays. Find row with most 1's, in O(n)

Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
1 vote
31 views

### Sparse bit string pattern matching

Suppose there are two strings of bits. Let's call them the needle (n) and the haystack (h). We'll say that the needle matches ...
• 111
1 vote
30 views

### Bron-Kerbosch algorithm for finding cliques missing a few edges?

The Bron-Kerbosch algorithm takes a graph and finds its maximal cliques in an efficient manner (as far as I'm aware, it is $O(3^{n/3})$, where $n$ is the number of vertices). Let $t$ be a positive ...
1 vote
52 views

### What does "computer steps" mean in this runtime definition?

My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) ...
• 111
27 views

### How is the prefix function (for KMP) time complexity O(N)?

I'm looking at the algorithm for the prefix function from here https://cp-algorithms.com/string/prefix-function.html : ...
• 324
34 views

### Minimal k-way comparison sorting algorithm?

I've watched 600 TV shows, and I want to sort them in order of how much I liked them. I'm bad at assigning absolute scores, but good at comparing relative enjoyment, so it has to be a comparison sort. ...
• 31
67 views

### Is there a "leader election" algorithm for communication via shared disks?

I've been trying to design such an algo with TLA+ formal prover, that is till I realized that it's a case of "simple-looking problem but with soooo many corner-cases", which screams of "...
• 121
50 views

• 225
40 views

### Relation between ExpTime vs Pspace

Are there any EXPTIME-COMPLETE problems that cannot be proven to be PSPACE-COMPLETE?
76 views

### Is it possible to sort this type of array in O(n) time?

Pseudo-Sorted array is an array that for every 0=<k<n the k smallest cell will be in the first 2k cells. For example the smallest cell will be in indexes 0-1 The second will be in indexes 0-3 ...
68 views

### Given an AVL tree of size n, is it possible to split the tree into 'k' equal sized search-trees in less than O(n) time?

The question first asked to split the AVL tree of size n into k equal sized search trees(k devides n) in O(n) time, and I solved this by moving all the AVL tree values into an array, and from there ...
• 23
100 views

### Minimum cost path connecting exactly K vertices

I came across a situation in real life that maps to this optimization problem: Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
70 views

### Data structure that supports adding to evenly spaced indices

I need an array-like data structure that stores integers and supports fast addition to multiple evenly spaced elements on given interval. Formally, if $n$ is length of the array, it has to support ...
• 51
1 vote