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,525 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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
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 ...
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 ...
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 ...
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$ ...
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
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 ...
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
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
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 ...
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 ...
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
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 ...
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
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 ...
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/...
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 : ...
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 ...
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 ...
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 ...
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
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 ...
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. ...
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 ...
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 ...
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
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 ...
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 ...
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
35 views

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, ...
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 ...
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 (...
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 ...
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 ...
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 ...
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: ...
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 ...
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"....
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'...
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
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
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 ...
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 ...
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 ...
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
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, ...
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 ...
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,...