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
33 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 ...
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 ...
0 votes
4 answers
232 views

$ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity

My algorithms and data structures' book states that to create a dynamic array the following procedure is followed: Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in ...
1 vote
1 answer
67 views

Q: Defining Markov-Chain Probability Matrix States | Specific Academic Paper

I am working on a uni project, for which i will model synthetic electricity consumption time series using Markov-Chains. I am reading through current academic literature on that topic and came across ...
3 votes
5 answers
5k views

Chess Knight minimum moves to destination on an infinite board

There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm. Here is ...
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 ...
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$ ...
3 votes
1 answer
541 views

Retrieving the cheapest path of a graph with time-dependent edge weights

There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient ...
1 vote
1 answer
228 views

Find a weight threshold for edges for maximum number of connected components in a graph

So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
2 votes
1 answer
71 views

Conditional Maximization of a Binary Matrix

Given an $L \times N$ matrix $A$ with only binary values, $A_{ij} \in \{0, 1\}$, and a vector $b$ with $b_j = 2^{j-1}$, I want to find a matrix $\tilde{A}$ that maximizes $\tilde{c}=\tilde{A}b$, ...
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 ...
1 vote
2 answers
744 views

Indexed Priority Queue change key

So I was just studying about Indexed Priority Queues and I got confused about the increase key operation. So basically we have the option to increase a key for an element in log n time because we can ...
0 votes
2 answers
1k views

Dynamic Programming - Difficult Jumping Frog Problem

Given a set of $n$ stones, arranged in a row at equal distances from each other. The stones are numbered from $0$ to $n-1$. A frog that is on stone number $0$ has to get to stone number $n-1$. A jump ...
-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 ...
1 vote
0 answers
345 views

Clash Royale Algorithm for troops path

I am making a clone of Clash Royale which is basically a Tower Defence game. As you can see from the picture you can deploy different troops only in your side of the court (that blue rectangle), and ...
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 ...
1 vote
1 answer
19 views

Defining multi commodity flows as polytopes

In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka ...
0 votes
1 answer
27 views

Intuition for Using Greedy Approach in Container with Most Water Problem

Link to leetcode problem: https://leetcode.com/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150 if we consider this solution: https://leetcode.com/problems/...
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 : ...
17 votes
3 answers
881 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
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 ...
0 votes
1 answer
267 views

Literature request: Generating all vertex subsets of a graph

I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications ...
0 votes
1 answer
96 views

Area preserving distance optimization

I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find ...
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 ...
21 votes
3 answers
12k views

Sort array of 5 integers with a max of 7 compares

How can I sort a list of 5 integers such that in the worst case it takes 7 compares? I don't care about how many other operations are performed. I don't know anything particular about the integers. ...
0 votes
1 answer
241 views

Efficient Method for Distance Comparison in Euclidean Space

I have a vector of 2D Euclidean coordinates, and I need to find out if two or more points are within a distance threshold. The naive approach is to compare each point with every other point, but I am ...
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 ...
0 votes
1 answer
76 views

Example of a function with specified running time

Can someone help with an example of a function such that $f(m ,n)$: $f(m ,n)$ takes 2 parameters $(m, n); \ m, n \in \mathbb{Z^+}$ The optimal running time to compute is $C(|m|^{|n|})$ in the worst ...
1 vote
2 answers
92 views

Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language. Theorem Let L ⊆ Σ∗. The following conditions are equivalent: L is generated by a ...
2 votes
3 answers
156 views

What are quines (layman friendly)?

I was going through the Wikipedia page on Quines and did not understand this paragraph - A quine is a fixed point of an execution environment, when the execution environment is viewed as a function ...
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 ...
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, ...
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 ...
0 votes
2 answers
92 views

Relation between algorithms and models

I have found this question some time ago. While reading it, I had a problem with understanding the following idea: Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (...
10 votes
2 answers
1k views

Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
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 ...
0 votes
1 answer
44 views

Coding the labyrinth solver

The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473 To summarize, in an unknown strongly ...
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: ...
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 ...
2 votes
2 answers
319 views

Hex Word Search Generator Algorithm

I want to create an algorithm to build a hex matrix with given: - max n rows - max m collumns - min t rown - min q collumns containing the specific words from a list: "example", "test", "algorithm"....
8 votes
2 answers
4k views

What is With High Probability on Probabilistic Algorithms?

I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still didn'...
0 votes
1 answer
1k views

Best algorithm for sequencing reducible control flow graph

I have a reducible control flow graph with only natural loops, produced from a simple DSL. Every node keeps a list of successors and a list of predecessors. I need to make a sequence of nodes out of ...
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 ...
1 vote
1 answer
132 views

Hoare Logic: Identifying Hoare Triple given a simple function

The program is designed to start with values for $x$ and $y$. The variables $u1$​ and $u2$​ are intended to represent $x$ and $y$ in ascending order. Provide suitable preconditions and postconditions ...
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 ...
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 ...
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, ...
1 vote
1 answer
81 views

Data structure for represent the cake in cake dividing problem?

Got inspiration while reading history book. Inspired by: China, the cake of kings and emperors, Le Petit Journal 1898 Background: After the Second Opium War, United Kingdom(UK), France, Russia, ...
5 votes
2 answers
4k views

When to use DFS and when use BFS?

Preparing for an interview. I see two cases where each one is specially suited BFS: When you need to find shortest path between vertices (if one exists). DFS: If you need to find cycles in a ...
0 votes
1 answer
86 views

Enumerate all superincreasing subsequences

A sequence of positive real numbers S1, S2, S3, …, SN is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. E.g: 1,...

1
2 3 4 5
231