Skip to main content

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
2 votes
0 answers
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 ...
Jürgen Böhm's user avatar
3 votes
3 answers
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 (...
releseabe's user avatar
  • 131
0 votes
1 answer
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 ...
littlesniper23's user avatar
-1 votes
0 answers
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 ...
sprw121's user avatar
  • 99
2 votes
2 answers
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 ...
Greedo's user avatar
  • 121
-1 votes
0 answers
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 ...
user26002931's user avatar
2 votes
1 answer
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 ...
Jack's user avatar
  • 125
2 votes
5 answers
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 ...
Ayush Gundawar's user avatar
0 votes
5 answers
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 ...
Josh's user avatar
  • 119
1 vote
1 answer
26 views

Given arrays A & B and an element-wise distance function f between them, minimize the sum of f over A & B by reordering B?

I have a problem I think I've managed to distill down to the following problem: Given two arrays $A$ and $B$ of length $n$ and a pair-wise distance function $f(a_i, b_i)$, where $a_i \in A$ and $b_i \...
tibbe's user avatar
  • 245
0 votes
0 answers
22 views

SSA Construction: DFS of CFG vs Traversal of Dominator Tree

According to Engineering a Compiler Cooper, K. and Torczon, L. the SSA transformation algorithm is divided into two parts Inserting $\phi$ functions. For each existing definition of a variable ...
David Yue's user avatar
  • 133
0 votes
0 answers
21 views

What is the fastest algorithm for generating all non-isomorphic unlabeled free trees for n-vertices, and also for caterpillar trees of n-vertices?

I'm aware of some algorithms for each problem such as the WROM algorithm for unlabeled free trees and the algorithm from this page for all caterpillar trees of n-vertices. However, I haven't been able ...
Ryan Gillies's user avatar
0 votes
0 answers
23 views

Kronecker Decomposition Algorithm

I am looking for an algorithm that decomposes a $2^n$ square matrix into a Kronecker product $\otimes$ of $n$ number of $2 \times 2$ matrices. Does anyone know if there is an implementation out there ...
3299792458777's user avatar
1 vote
0 answers
21 views

Linear time algorithm for computing radius of membership hyper-sphere

We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E. Alongside the ...
moe asal's user avatar
  • 111
2 votes
1 answer
35 views

Finding the maximum number of courses one can taking fewer than $k$ courses at a time

I bumped into this problem (in Spanish), bu Jon Ander Gómez y Alberto Verdejo. It boils down to: You are given a list of $n$ online courses ($1 \leq n \leq 10^3)$, each course $i$ defined by the ...
user2891462's user avatar
1 vote
2 answers
38 views

Random directed acyclic graph (Barak-Erdös): find "upstream" vertices

The problem Consider a set of $N$ vertices $V=\{v_1,v_2,...,v_N\}$. We define a random directed acyclic graph by the set of edges $E$ as follows: for every $i<j$, $e_{ij}:=(v_i\rightarrow v_j) \in ...
UJM's user avatar
  • 73
3 votes
1 answer
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 ...
UJM's user avatar
  • 73
-1 votes
3 answers
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?
pkrzysiek's user avatar
0 votes
1 answer
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 ...
Gouvernathor's user avatar
1 vote
2 answers
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 ...
Simon Walker's user avatar
2 votes
1 answer
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 ...
Dudi Frid's user avatar
  • 231
1 vote
1 answer
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 ...
Daniel's user avatar
  • 93
0 votes
0 answers
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 ...
K. Stuhl's user avatar
2 votes
1 answer
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 ...
Ferran Gonzalez's user avatar
2 votes
2 answers
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....
Lisa E.'s user avatar
  • 555
1 vote
2 answers
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 ...
Science Guy's user avatar
1 vote
0 answers
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 ...
Yan B.'s user avatar
  • 111
1 vote
0 answers
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 ...
Alvaro Martinez's user avatar
1 vote
2 answers
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) ...
Princess Mia's user avatar
0 votes
1 answer
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 : ...
JobHunter69's user avatar
3 votes
2 answers
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. ...
JentGent's user avatar
0 votes
1 answer
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 "...
Hi-Angel's user avatar
  • 121
2 votes
3 answers
50 views

Prove that the L1 distance between two arrays is minimized when both are sorted

Suppose you are given two arrays of the same length $n$, say $a$ and $b$ containing unique positive integers. The L1 distance between $a$ and $b$ is defined as: $$d_1(a, b) = \sum_{i = 1}^n \lvert a_i ...
kaddy's user avatar
  • 83
2 votes
1 answer
55 views

1-in-k-SAT problem restricted to only positive literals and at most two occurrences of a variable

1-in-k-SAT problem is to determine if there’s an assignment to variables such that every clause has exactly one true literal. Is this problem known to be in P when restricted to positive literals, and ...
Ajay's user avatar
  • 23
1 vote
1 answer
30 views

Recurrence Upper Bound Estimation

I'm going through CLRS and was trying to solve for the asymptotic bound of the following recurrence (exercise 4-5.4) $$T(n) = 4T(n/2) + n^2\text{lg }n$$ According to CLRS definition of Master Theorem, ...
Jackson Schuetzle's user avatar
-1 votes
1 answer
33 views

Top K Most Frequent Elements and Bucket Sorting Intuition

Link to Problem: https://leetcode.com/problems/top-k-frequent-elements/description/ Bucket Sort Solution: https://leetcode.com/problems/top-k-frequent-elements/solutions/5032156/beats-96-39-of-users-...
penguin365's user avatar
1 vote
1 answer
79 views

MSOL for a vertex-cover enlargement problem

Consider the following problem. Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|\le k$, and any subset $V'\...
Lisa E.'s user avatar
  • 555
1 vote
1 answer
44 views

BFS on directed graph with disjointed edges?

There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to ...
Caroline's user avatar
2 votes
1 answer
65 views

Find hierarchical clustering of documents

Given some large set of documents, how would one find a human usable hierarchical clustering to them (ie. place them into a file system such that one can find a document in the minimal time)? My ...
olivarb's user avatar
  • 121
3 votes
1 answer
61 views

Cover a set of points using subintervals of a list of intervals

Given a set of points $\{p_1, p_2, \dots p_n\}$ and a set of intervals $I =\{[a_1, b_1], \dots [a_m, b_m]\}$, you are asked to find a set of subintervals $S = \{[c_1, d_1], \dots [c_m, d_m]\}$ where $[...
SimonNW's user avatar
  • 161
2 votes
1 answer
50 views

Is there a formal methodology for determining time complexity of an implementation of an algorithm?

Basically what the title says. take for example a simple function: def swap(a,b) temp = a a = b b = temp This one is pretty easy to solve intuitively. if we ...
UNRESTR1CTED's user avatar
1 vote
1 answer
59 views

Why does ISA includes instruction for logical operation?

I'm a junior student in Electronic Engineering. Recently, I learned about Gödel's incompleteness theorem. One of the concepts related to this theorem is Gödel numbering, which shows that every logical ...
MS Keane's user avatar
4 votes
0 answers
59 views

Deterministic solution of "nuts and bolts" problem

How are the samples in "Matching nuts and bolts" paper in chapter two chosen deterministically to achieve $O(n^{1.5})$ complexity? I don't see how projective planes can help here.
Gh0st's user avatar
  • 41
2 votes
1 answer
30 views

Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank

Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M $ such that the rank of the matrix $$A = \sum_{m \in N}m $$ is minimal. I am wondering if anyone have seen ...
Sander's user avatar
  • 225
2 votes
1 answer
40 views

Relation between ExpTime vs Pspace

Are there any EXPTIME-COMPLETE problems that cannot be proven to be PSPACE-COMPLETE?
jaime bonilla's user avatar
0 votes
2 answers
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 ...
Itamar Adar's user avatar
2 votes
2 answers
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 ...
Thomas's user avatar
  • 23
5 votes
0 answers
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$ ...
InfiniteSnow's user avatar
5 votes
0 answers
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 ...
Risodu's user avatar
  • 51
1 vote
0 answers
22 views

Global minimum weighted vertext cut for undirected graphs

Given an undirected graph with vertex weights, there any algorithm for finding the global minimum vertex cut that partitions the graph into two components? I can transform the graph to directed one ...
tr244's user avatar
  • 11

1
2 3 4 5
232