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

What is the algorithm where you rotate around a board in a clockwise pattern?

I'm sure this question has been asked before, but I have no clue what I'm trying to achieve is called and couldn't find anything helpful. I'm trying to find the name of an algorithm that starts at a ...
0 votes
1 answer
43 views

Proving why decreasing an edge weight in a graph may change it's MST by one edge

I'm working on understanding graphs and graph algorithms. The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf (Q 1.D) Describe an efficient algorithm to ...
2 votes
3 answers
98 views

Algorithm: Optimal selection of subset of nodes in undirected graph to minimize score

Apologies if this question exists somewhere. I'm sure it's been asked, but I don't know how to search for it. This is not a homework question but rather a scientific problem I ran into. If this is a ...
0 votes
1 answer
24 views

LP Approximation for Vertex Cover Problem

In Cormen's Introduction to Algorithms, he states the the LP relaxation for the minimum vertex cover approximation problem is $ \begin{align*} &\sum\limits_{v \in V}w(v)x(v) \...
0 votes
2 answers
46 views

Sort doubly linked list with just manipulating pointers

Given doubly linked list $L$ that contains $n$ elements of numbers. Between QuickSort, and MergeSort and InsertionSort, which algorithm preferred to sorting $L$ by just swapping links of $L$? I think ...
  • 1,418
0 votes
0 answers
22 views

Prove that Fibonacci code for data compression is a complete code using Kraft-McMillan inequality

I am Facing a problem when learning about data compression. I learned that the Fibonacci code for data compression is complete. I am trying to prove it using a hint from my professor to use Kraft-...
1 vote
1 answer
32 views

Are there arbitraraly hard worst case problems with polynomial time average case complexity?

For example, are there worst case Decidable(but non primitive recursive or other insane time complexity)problems that have a polynomial average case complexity? If so Are there undecidable worst case ...
2 votes
1 answer
34 views

Finding optimal paths for multiple agents

This is a real world problem, which due to some specific aspects of it I am having a hard time finding relevant literature for it. I am looking for either an algorithm, or a pointer to relevant paper(...
  • 121
0 votes
2 answers
40 views

if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$?

if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$? what if we also have $f(1)=2$?
0 votes
1 answer
29 views

How to select a subset from the array $A=\{\frac{S_1}{K_1},\frac{S_2}{K_2},...,\frac{S_n}{K_n}\}$ such taht the subset can meet this requirement?

Given an array $A=\{\frac{S_1}{K_1},\frac{S_2}{K_2},...,\frac{S_n}{K_n}\}$ whose any $S_i$ and $K_i$ are positive floating-point, and an positive floating-point $R$, how to select a set of element $C=\...
  • 5
1 vote
0 answers
23 views

Longest (weight-wise) walk In a directed graph with weights becoming negative after traversing once

Problem definition I have a directed graph $G = (V,E)$, with positive weights $w(e)>0\:s.t\:\forall e \in E$ I would like to find the longest walk (i.e. edges and nodes may be repeated) in terms ...
  • 11
1 vote
1 answer
27 views

Is there an existing similarity measure for comparing sequences similar to this one?

I work with elements that have a representation in two different vector spaces and I would like to compute an indicator of how similar the neighbors of the elements are in these two spaces. To do so, ...
  • 113
0 votes
0 answers
19 views

How would a patricia tree look like after adding a word that starts as the substring of another but has additional letters?

Take this trie as example: I want to add the word "luan" to this representation, but luan takes 20 bits to represent, while lua takes 15. So, they "differ" from each other on the ...
  • 1
1 vote
0 answers
39 views

Combine Las Vegas and Montecarlo probabilistic algorithms to improve chance of finding correct answer

Let's say that I have a Las Vegas algorithm for a given problem (whose answer is true/false for simplicity) with a chance of ...
  • 239
0 votes
0 answers
15 views

The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?

When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring. Take the string $s = a^6$. Then its ...
0 votes
0 answers
27 views

An ingenious exact smallest grammar algorithm for strings over a single letter, $s \in \{a\}^*$. First enumerate the start rules up to commutation

Take $s = a^{10}$ for our example string. Compute the set of all potential grammar reducing variable-rules: $$ A \to aa \\ B \to aaa \\ C \to aaaa \\ D \to aaaaa $$ There is always exactly $\left\...
-1 votes
1 answer
40 views

how to find the most optimal path for this problem?

There are N islands and there is one pirate. The pirate can start out from any one of the n islands and has the option of either staying on the same island for the next day or moving to a different ...
  • 1
0 votes
1 answer
37 views

Suggest good books for Advanced Data Structure and Algorithms

I don't really need hands on coding help, I need to clear my concepts of some of the more complex topics of DS and Algo like NP-Completeness, Computational Geometry, String Matching, Multithreaded ...
1 vote
1 answer
26 views

Compare and find the best match from multiple lists

Lets say I have n lists from different sources, each contains m possible location of the user. I need to choose the most probable prediction of the user location. My idea was to pick one location from ...
1 vote
0 answers
23 views

Determine whether we can pack $(r_1, \dots, r_k)$ copies of the variables $(A_1, \dots, A_k)$ into a string $s$, in time polynomial in $|s|$?

Let $s \in \Sigma^*$ be a finite string over alphabet $\Sigma$. Find all "compressible" substrings of $s$, that is substrings $t \leqslant s$ (notation) such that $t\alpha t \leqslant s$ ...
0 votes
1 answer
39 views

maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$

Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the subsequence(...
1 vote
1 answer
36 views

Number of ways to make change in o(k), where k is number of coins

Godd afternoon, We have set C of k coins; For example C = (2, 3) We have positive integer n. In how many ways we can represent n using those coins? Example: If n = 12; C = (2, 3) we can represent 12 ...
  • 111
0 votes
0 answers
46 views

Assigning directions to edges in an undirected graph in a way which satifies some condition

I got the following question from my academic instructor and since I am new to graph algorithms I would be happy if someone could review my solution. Given undirected graph $G = (V,E)$, suggest an ...
  • 65
-3 votes
1 answer
91 views

how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000

how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000 for example for n=3, there is 15 solutions 1^1=1^1 1^1=1^2 1^1=1^3 1^2=1^1 1^2=1^2 1^2=1^3 1^3=1^1 1^3=1^2 1^...
1 vote
1 answer
38 views

Possible approaches to the Ship City problem?

About few ago in my freshman year of college I stumbled across an an old blog post on r/programming posing a programming challenge. Here is the short version of it: Hundreds of ships would like to ...
0 votes
1 answer
18 views

Algorithm to find best order for items on pages with a fixed height

I am looking for an algorithm to find the best order of items to fit on pages. Consider the following case, we have a page with the height = 300 We have images with the following heights - [150,200,...
-1 votes
1 answer
25 views

A question about the graph theory or data structure and algorithms

I would like to ask this question as I am not sure about the answer. Let $G=(V,E)$ be a connected, undirected graph, and let $x,y\in V$ be two different vertices. Let $A$ be the problem of finding the ...
0 votes
2 answers
190 views

Closest pair of points in 3D

My professor mentioned that if we already know the divide and conquer algorithm for the closest pair of points in 2 dimensions it's easy to think of a similar algorithm for the 3 dimensions. But I am ...
  • 101
1 vote
1 answer
103 views

Is there an efficient way to solve this problem?

Given a series of n numbers, I need an algorithm that runs in worst case O(n*k) to figure out how many arrangements of those n numbers will give me a score of exactly k. Note that the series does not ...
0 votes
1 answer
37 views

How to prove this variant of set partition problem is NP hard?

The problem is: split the given array with $L$ elements, $A$, into $K$ subsets such that maximum sum of all subsets is minimum. I have known that the problem that partitioning the multiset $S$ into ...
  • 5
0 votes
1 answer
23 views

Algorithm to alternaly order elements in a list

So, I have N sets of objects of various sizes. I want to put them in order, in a way that's as much "alternative" as possible. For example, if I have 5 A, and 6 b, that's easy: B A B A B A B ...
0 votes
1 answer
29 views

Split matrix by groups of columns but *capture all combinations of X columns* for some X

Say I have a big matrix, ~50000 rows, ~80000 columns. I want to split it up and solve subproblems on different machines (horizontal scaling). But I need to make sure every column can be combined with ...
3 votes
1 answer
95 views

Getting all vertices with fixed index in their topological ordering of a DAG

During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve. There are typically more than one order of a topological ordering ...
7 votes
2 answers
204 views

Choose non-adjacent numbers from intervals

Given a list of intervals with integral endpoints, we want to find out if we can choose one integer from each interval so that no two chosen numbers are adjacent. Can we do this in polynomial time? My ...
  • 131
1 vote
1 answer
38 views

Decision tree to check 2 rectangles

Given two disjoint rectangles $(a,b]\times (c,d]$ and $(e,f]\times (g,h]$ in $\mathbb{R}^2$ how can I check with a decision tree of least depth if a given point $(x,y)$ lies within the union of the ...
0 votes
2 answers
113 views

Finding the power of a number without a library pow function

I am solving a problem that involves finding a pow(x, n) without using a pow library function. Following is the algorithm that ...
  • 129
0 votes
0 answers
34 views

Separate recipes into compatible categories

We are running a restaurant. Unfortunately due to mysterious reasons, we cannot tell our chef what recipes to make, we can only prepare him the ingredients for the meals. Fortunately our chef has ...
2 votes
1 answer
44 views

Fpt algorithm for hypergraph basis problem

While working through the book Parameterized Complexity Theory of Flum and Grohe, I encountered exercise 1.42: Let $H = (V, E)$ be a hypergraph. A basis of $H$ is a set $S$ of subsets of $V$ with the ...
  • 31
2 votes
2 answers
88 views

Algorithm for farthest point Voronoi diagram?

I am looking for an algorithm to compute the furthest point Voronoi diagram and I don't seem to be able to find anything decent. The most complete one I have found are these slides and this terribly ...
  • 113
2 votes
1 answer
76 views

Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?

This is probably a computer science history question. Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?
1 vote
2 answers
79 views

Can two different binary trees can have identical post-order sequence

I have found that when drawing two trees having different structures, we can get the same in-order sequence and pre-order sequence. But I haven't found if two different binary trees can have an ...
-2 votes
0 answers
34 views

Odd and even numbers jumps

I have an algorithm where I have to calculate jumps where I see odd or even numbers. There is condition: if number is odd, the next one should be smaller or equal if number is even, the next one ...
2 votes
0 answers
29 views

State of the art implementations of minimum-cost multicommodity flow approximation algorithms

I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
  • 165
0 votes
0 answers
19 views

Signed Decimal Binary to Decimal conversion

I have tried to convert signed binary number, -11.875, to unsigned value. I am not sure about where to add the carry bit taking 2's complement of binary -11.875. The carry bit should be added with the ...
  • 1
1 vote
1 answer
33 views

Is it possible to measure how fast the humans are moving their bodies with different level(slow, normal, fast) from video?

Examples like swinging both of their hands squat walking around jump around etc Is it possible to perform this in real time under crowded scene without depth information? I can find out the "...
0 votes
2 answers
168 views

subtract the weight of the largest edge

I have an oriented and weighted graph, and I need to find the cheapest route from source to destination. Now I have a source node A and a destination node B the cheapest path is given to me by the sum ...
  • 13
0 votes
0 answers
29 views

How to find competitive ratio of any online algorithm?

I am starting to learn online algorithms but am still stuck in determining the competitive ratio. I cannot understand how to find it. All the research papers are so difficult to understand. Please ...
1 vote
0 answers
29 views

How to let the champion sit?

There is a chess tournament planned. It is a single-elimination tournament, and for spectacle purposes, only one match at a time will take place, on a table in the middle of the stage (winners will ...
  • 9,693
1 vote
1 answer
67 views

Removing k-smallest elements in a binary min-heap

Assuming a contiguous array implementation of a binary min heap with n elements, is it possible to remove the k-smallest elements in a faster time than $O(k \log n)$...
  • 123
1 vote
1 answer
75 views

Max-flow problem with additional constraint

Consider the max-flow problem with a set of additional constraints, each in the following form: the flow on edge $e$ must equal the flow on edge $e'$. My question is how to modify existng max-flow ...
  • 71