Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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
3 votes
1 answer
31 views

Is there an algorithm for rearranging a set in a specific way while optimizing for minimum amount of moves?

Say I have an array that goes like [ a, c, b, d ] and I want it rearranged as [ d, c, a, b ]. The only type of change I'm allowed to make is plucking an element from one place and inserting it into ...
user81993's user avatar
  • 161
0 votes
1 answer
32 views

Balancing tree by removing nodes instead of perfoming rotations to defined height $h$

I am provided a tree that may be very deep and unbalanced. I want to be able to transform this tree into a more balanced form with maximum height $h$. We can do this by removing internal nodes, but we ...
olivarb's user avatar
  • 101
1 vote
1 answer
18 views

Pseudo-Traveling Salesman on a colored graph

I have a graph with nodes of various colors and weighted edges between them. I would like to find the least cost path that touches exactly one node of each color. Is this a known problem or reducible ...
Jemmy's user avatar
  • 113
-1 votes
0 answers
15 views

Using Binary Search to Calculate the nearest 2d Co-ordinate from a list , Leetcode#2812

I am solving this question Problem Link through a different method , the only difference between the the official solution and my approach is that, The official Solution uses BFS(Multisource) to ...
Shubham Kumar's user avatar
0 votes
0 answers
16 views

Improve performances of Gauss-Jordan (XOR-SAT) Algorithm?

In this question I was looking for an algorithm to solve what seems to be a XOR-SAT problem. Let's consider this equation system : ...
nowox's user avatar
  • 241
4 votes
0 answers
39 views

Algorithm for finding a path factor in a graph

A 1-factor is a perfect matching. A path factor of a graph $G$ is a spanning subgraph, each of whose components is a path with at least two vertices (see the following figure). Since every path with ...
licheng's user avatar
  • 405
1 vote
1 answer
174 views

How to solve a system of XOR equations in a cyclic graph?

I am working on a problem where I need to find values for nodes in a graph of k-nodes. Here an example: The properties are: Each big node (A..H) is connected to at least one blue node Each blue node ...
nowox's user avatar
  • 241
0 votes
0 answers
32 views

Algorithm for all optimal s-t cuts [closed]

Suppose the $s$-$t$ min cut in a directed digraph $G = (V,E)$ is not unique ($s$ is the source and $t$ is the destination). Is there an algorithm to generate all possible $s$-$t$ min cuts, say using ...
tr244's user avatar
  • 1
0 votes
1 answer
42 views

Big O notation of T(n) = T(n/2) + O(log n) using master theorem?

I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time. Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
inkwad's user avatar
  • 1
2 votes
0 answers
44 views

Ensuring that no two subsets have equal sums

Given a list $L$ of $n$ real numbers in $[0,1]$, I would like to ensure that there is no partition of $L$ into two subsets with an equal sum. Deciding whether such a partition exists is a well-known ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
35 views

Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
Bob Marley's user avatar
0 votes
1 answer
15 views

Algorithms for unordered vertices of the convex hull

For the sake of this question a "non-ordering" "set of vertices of convex hull" algorithm produces the collection of all points on the convex hull of its input without producing ...
worldsmithhelper's user avatar
0 votes
0 answers
11 views

Repetition of projection game [closed]

Consider projection name $H$ with projection function $\sigma$ with $val(H)\in [0.1,0.9]$, how to construct a $H$ s.t. $val(H^{\otimes 2})\geq val(H)-\epsilon$ for arbitrary $\epsilon>0$? There is ...
Lagranngekmno4's user avatar
2 votes
1 answer
36 views

Minimize cost for list of words given a list of letters

What is a general algorithm to reorder a list of letters such that it minimizes the cost for a fixed list of words? Algorithm input To be optimized a list of unique letters: ...
wjwrpoyob's user avatar
  • 141
2 votes
1 answer
62 views
+50

The existence of a (nearly) quadratic time algorithm for 2-steps shortest path or smallest triangle

I am interested in two problems, which seem to be related, solving each will advance me in other possible directions. In both problems, $G=(V,E)$ is a positively-weighted undirected graph. Denote its ...
Mařík Savenko's user avatar
0 votes
0 answers
21 views

Integrality gap of Maximum Coverage LP

Consider Maximum-Coverage problem, which means there are set $A$ and $n$ subsets of $A$, we can choose $k$ subsets to cover some elements, and Maximum-Coverage is the assignment that cover most ...
Lagranngekmno4's user avatar
3 votes
0 answers
49 views
+50

Maximum network flow with few non-integral edges

Consider the following network: $s\to a, s\to b$ with capacity $1.5$ each; $a\to 1, a\to 2, a\to 3, b\to 1, b\to 2, b\to 3$ with infinite capacity each; $1\to t, 2\to t, 3\to t$ with capacity $1$ ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
22 views

Calculating nth permutation with repetition efficiently, with variable number of elements

After a long night of Calculating nth permutation without repetition efficiently, with variable number of elements, I realized I actually want permutations with repetition. Given the ordered set ...
wjwrpoyob's user avatar
  • 141
1 vote
3 answers
36 views

worst case scenario for sorting an array using insertion sort given that all elements can only be 0,1,2

were given an array of numbers "A" of size n, any given number in the array can be one of the following: 0,1,2. using insertion sort, what is the worst case scenario, and what is the best ...
אקרמי צאלח's user avatar
0 votes
1 answer
13 views

Calculating nth permutation without repetition efficiently, with variable number of elements

I know I can use the factorial number system to calculate ordered permutations of a set efficiently, given a constant length (for example, ...
wjwrpoyob's user avatar
  • 141
0 votes
0 answers
16 views

Boosting probability of Randomized approximation algorithms

Suppose $A$ is a randomized algorithm with following properties: The expected running time of $A$ is at most $\mathrm{poly}(n)$ When Opt$\geq c$, with probability at least $\mathrm{poly}(n)$ ...
Lagranngekmno4's user avatar
0 votes
1 answer
20 views

Finding middle vertex of tree

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G ...
user438409385's user avatar
0 votes
1 answer
28 views

Robust maximum weight forests with weights on edges

In an undirected weighted graph with edge weights, the task is to find a spanning tree T. An adversary will delete two edges (not necessarily from T), and subsequently, we can add an edge (excluding ...
Toyllo's user avatar
  • 1
2 votes
1 answer
60 views

Minimum number of intervals from a set to cover all intervals of another set

There are two sets of intervals provided to us. target = {{11,13}, {7,10}, {0,3}, {6,6}} space = {{10,12}, {2,6}, {4,8}, {0,4}, {9,10}} I need to find the minimum number of intervals I can pick from ...
Viktor's user avatar
  • 23
-1 votes
0 answers
32 views

Algorithmically determine if another algorithm is brute force?

Is there a way to algorithmically determine if another algorithm is a brute force algorithm? Can a Turing machine be programmed to do this? related: "Precise definition of a brute force algorithm&...
Geremia's user avatar
  • 142
-2 votes
2 answers
50 views

Precise definition of a brute force algorithm

What is the precise definition of a brute force algorithm? Is it one that simply has non-polynomial runtime?
Geremia's user avatar
  • 142
3 votes
0 answers
47 views

Algorithm to find minimum number of cuts in DAG based on a rule

I encountered this problem while doing some “graph”ics programming: Take a directed acyclic graph where every vertex is given a non-unique label 1..N You can ‘trim’ the DAG by making a cut that ...
Matt Tytel's user avatar
3 votes
1 answer
196 views

How to find a binary vector with minimized distance with a vector set?

Given a set of vectors $S = \{v_1, v_n, ..., v_n\}$, $v_i \in \mathbb{R}^m $. Now I want to find a binary vector $ t \in \{0, 1\}^m $ to minimize $ \sum_{i=1}^n \text {distance} (t, v_i)$. ...
Jun Yang's user avatar
0 votes
1 answer
25 views

Is this knapsack variant named / studied? "Online algorithm for farthest-from-previous index"

Problem Statement: Given: an ordered list of N items, which we can refer to by index: [0, N). Goal: Write an algorithm to ...
Erotemic's user avatar
  • 123
0 votes
0 answers
35 views

Given a vector space where every vector has a weight. Find the highest weight subspace

I have the following problem: Given a finite dimensional vector space $V$ over a finite field, and where every vector has a weight given by $w\colon V \rightarrow \mathbb{N}$. Find the subspace $U$ of ...
Sander's user avatar
  • 203
1 vote
1 answer
92 views

Number of unique paths in a grid

Suppose, I have a nxn grid. Now, I want to move from (1,1) to (1,n). How many unique ways are there possible if I can move in left, right, up and down direction. I am trying to solve it using depth ...
Nakib's user avatar
  • 11
3 votes
1 answer
34 views

Best algorithm to evaluate a function that takes the elements of all possible combinations of N numbers

Consider a set $A$ containing $N$ real numbers. Let $f(X_{r,k})$ represent a function, where $X_{r,k}\subseteq A$ denotes the $k$th combination of $r$ elements from $A$, with $1 \leq k \leq \binom{N}{...
GeoArt's user avatar
  • 31
-6 votes
0 answers
41 views

What is the Time Complexity of following code?

What is the Time Complexity of following code? P_P(A[1..n]) { if (n==1) then return; for i=1 to n/2 A[i] = A[i] + A[i+n/2] P_P(A[1..n/2] }
Dattatraya Sakharam Adane's user avatar
0 votes
0 answers
15 views

How to get the iterator of the ancestor nodes during DFS or BFS?

I am able to solve this by myself, but somebody may already know the answer, so saving manpower, instead of me probably trying several variants. What is an easy way during either DFS or BFS of a DAG ...
porton's user avatar
  • 493
1 vote
1 answer
65 views

Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

My question arises out of this competitive programming problem. The idea is to find a unique element $u$ and then divide-and-conquer for the subarray to the left and to the right of $u$. Searching for ...
Elucidase's user avatar
1 vote
1 answer
47 views

How to prove a function is a bijection (name mangling)?

I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed. We'...
user129393192's user avatar
0 votes
1 answer
25 views

How to do different cases of Union Find?

Here is the question: I understand that the absolute parents are 1, 3, 0, and 8, respectively, but I'm not sure how to do union here. Could someone help me understand how to do this?
MotherHorse's user avatar
0 votes
1 answer
37 views

Efficient ordered single-writer multi-reader list with "add" and "bring to front" operations

I'm looking to implement a collection that needs to support only two operations: AddOrUpdate: Insert item into collection if it doesn't exist; otherwise, move it from whatever the current position is ...
Bogey's user avatar
  • 133
1 vote
1 answer
33 views

What kind of problem am I trying to solve?

I have 500 locations that have multiple skus with varying quantities and I have 6000 orders requesting multiple skus with varying quantities. I have to minimize the total number of locations I visit(...
Chong's user avatar
  • 13
0 votes
2 answers
31 views

Search times for hash tables using open addressing for collision resolution

With regards to hash tables using open addressing as collision resolution mechanism, Introduction to Algorithms, Chapter 11, page 294 (4th edition, 2022 printing) states the following Deletion from ...
jam's user avatar
  • 13
-2 votes
2 answers
31 views

Color conversions formulas

I need formulas to convert betwen color spaces, is there official color conversion reference or something of this kind? I can't find it with simple google search. rgb -> hex, rgb -> hsl, rgb -&...
Ilia Borisov's user avatar
1 vote
1 answer
36 views

Knuth–Morris–Pratt algorithm - Determine the next position of the proper prefix of the pattern string

When I learn Knuth–Morris–Pratt algorithm, I got a function f from the book Fundamentals of Data Structures in C. ...
user169664's user avatar
0 votes
0 answers
28 views

Algorithm of min copies needed to make up a string

I encountered a coding interview question. The problem is like this, you are given a source string and a target string, you can make arbitrary copies of source string and also delete an arbitrary ...
P Li's user avatar
  • 101
0 votes
0 answers
26 views

Largest Tetrahedra from a set of points

Problem Given a set of k points in 3D Euclidean space with k ≥ 4, find four points from the set that form a tetrahedra such that the volume of the tetrahedra is maximized. Attempted Solution Find ...
WakkaTrout's user avatar
-1 votes
0 answers
22 views

Swap function in Time Complexity

Find the time complexity of the following using step count method. for (i = 0; i < n; i++) for (j = i+1; j < n; j++) swap(a[i][j], a[j][i]); I need ...
eccentric learner's user avatar
0 votes
0 answers
6 views

Load Balancing with No Overlap

Problem Suppose there are $n$ jobs $J_1, \ldots, J_n$ that need to be completed using $m$ machines $M_1, \ldots, M_m$. Each job $J_i$ consists of a set $S\left(J_i\right)$ of $k_i$ sub-chores $s_1, \...
cuppajoeman's user avatar
1 vote
0 answers
20 views

re-rooting a rooted DAG

A "network" is a DAG with a single source (the "root") and all nodes except the root either have in-degree one or out-degree one. A network is "binary" if all nodes have ...
igel's user avatar
  • 111
-1 votes
0 answers
29 views

Why do different computes take inputs at the same time differently?

I was randomly pressing multiple keys at a time on a school chrome book. When I pressed for example, the q, w, and e keys, it said qwe or whatever order in the search bar. But if it was a different ...
sammyiscuul's user avatar
0 votes
0 answers
34 views

Algorithm to "reverse" search/match pairs from results

Sorry, I don't know how to title it clearly. There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. ...
herhor67's user avatar
0 votes
0 answers
9 views

Shortest path in a graph where edge weights can vary dynamically based on the path taken [duplicate]

I have a directed acyclic graph whith negative edges where edge weights can vary dynamically based on the path taken. ...
user1552545's user avatar

1
2 3 4 5
231