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
0
votes
0answers
9 views

Finding a greedy algorithm to maximize the total energy subject to constraints

This problem is based off of the following problem on stack overflow: https://stackoverflow.com/questions/64797299/greedy-algorithm-to-maximize-score. The second answer is incorrect because the ...
0
votes
1answer
15 views

Solve the recurrence equation $T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$

I am trying to find the runtime of: $T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$ $T(1)= 1$ What is the way to solve this kind of problems?
4
votes
1answer
72 views

Find all n bit numbers with k ones and unique under circular shift

I am trying to traverse through all uint64_t with k 1s. Then I find that if x and y are circular shifts of each other, they will output the same result. So I'm trying to optimize my code. The problem ...
0
votes
1answer
32 views

Find a maximum matching in linear time - How to prove it?

Let B be an undirected tree with |V| nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime O(|V|). I understand that the solution ...
0
votes
0answers
13 views

Algorithm to compare two live changing sets

I have two databases that are updated from asynchronous events, those updates should perform the same changes on both. both database have different structures a common id exists between "...
0
votes
2answers
22 views

How to detect if a CFG can cause the parser ends up looping forever?

For example, the following grammar will never stop deriving a complete sentence: S -> A b A -> a A Some other CFGs can derive a complete sentence, but it ...
0
votes
0answers
12 views

Optimal text/code formatting with alignment constraints

Formatting code or things like TeX have some interesting problems. For instance in auto-formatting code you want to use up as much line space as possible but not go over a certain limit if possible. ...
0
votes
0answers
20 views

Finding all integer solutions of an equality

I want to generate all solutions of $x_1+x_2+\ldots+x_{100}=6$ where $x_i$s are non-negative integers. Finding the number of such solutions is not difficult. But is there any easy way to get all ...
0
votes
0answers
25 views

Dynamic programming: weighted interval scheduling with two types of intervals

I am trying to come up with a dynamic programming approach to solve the following problem, but I am stuck as to how to go about an additional added constraint. Input: a set of intervals on a number ...
-1
votes
0answers
21 views

an introduction to bioinformatics algorithms solution manual pdf [closed]

I'm looking for exercise solutions for "An Introduction to Bioinformatics Algorithms" book. Can anyone help me and send it to me if they have it? The above book is written by the following ...
0
votes
0answers
30 views

greedy algorithm proof involving maximizing total energy subject to constraints [closed]

This problem is based off of the following problem on stack overflow: https://stackoverflow.com/questions/64797299/greedy-algorithm-to-maximize-score. The second answer is incorrect because the ...
1
vote
0answers
21 views

Why is the input of the algorithm in "Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation" a matrix?

My question is about the algorithm in the article Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation, as described in the picture below. It is written at beginning ...
0
votes
0answers
15 views

Misunderstanding Readjustment of CPI calculation

I have a practice problem I have been working through in an effort to understand processor time calculation and CPI calculation. The problem is given as such: Two machines are given: In machine A the ...
0
votes
0answers
17 views

Is there an algorithm to efficiently generate all partitions of a set such that no cell contains fewer than k elements of the set?

I am trying to generate partitions of networks to evaluate clustering algorithms. I know that generating all partitions is infeasible (since they grow with Stirling number of the second kind which get ...
1
vote
0answers
45 views
+50

Limited number of calling for a decision blackbox to compute all the solutions

I am trying to reduce between a solution problem and a decision version of the same problem. The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
1
vote
1answer
61 views

How do COVID-19 Vaccination ID verifications work? How do they ensure that the ID is not faked?

How do COVID-19 Vaccination ID verifications work? How do they automatically verify that the COVID-19 Vaccination ID is not faked?
0
votes
0answers
21 views

Is there a standard data structure for sparse block matrices where each block has the same value?

I'm looking for a data structure that could represent a (sparse) matrix of submatrices with equal-valued elements by the individual blocks' coordinates and value; for example, it would encode: \begin{...
1
vote
0answers
10 views

How do distributed joins work in a distributed relational database system?

I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
0
votes
0answers
7 views

Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?

In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
1
vote
1answer
25 views

Minimum number of intervals to cover all possible colors

Given $n$ points in $\mathbb{R}$ each colored with one of following three colors $$C=\{c_1, c_2, c_3\}.$$ In polynomial time, Choose the minimum number of intervals of length $1$ each containing some ...
1
vote
1answer
15 views

update distance matrix between n points

I am looking for an efficient algorithm to update a $N*N$ matrix, in which the coefficients represents the distance between $N$ number of points, every time that the coordinates of a point change in a ...
0
votes
1answer
39 views

Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?

Question: Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers. We use an algorithm that loops through all the ...
0
votes
0answers
12 views

How do relational algebra query analyzers generate query alternatives?

tl;dr: How does a query analyzer know how to modify a query to find a better one? I would like to implement a distributed database. I have figured out ways of storing data in a normalized form, and ...
4
votes
0answers
45 views

Algorithm to find equivalent classes of homotopic pathes on a grid with obstacles

Given a $n \times n$ grid with some walls and two cells $a$ and $b$, I want to compute the non-homotopics paths from $a$ to $b$ on this grid. A path is a sequence of adjacent cells (diagonal does not ...
2
votes
1answer
40 views

Computable Numbers and Cantor's Diagonal Method

We were given the following problem in our university: We will call $x \in (0; 1)$ computable iff there exists an algorithm (e.g. a programme in Python) which would compute the $n^{th}$ digit of $x$ (...
0
votes
0answers
20 views

Understanding Theory of DPLL [closed]

I have several questions regarding DPLL Algorithm : Does by doing BCP could expose a new pure literal? Does by doing PLP could expose a new unit propagation? Can the output of DPLL is correct if we ...
0
votes
0answers
23 views

Algorithm for scheduling tasks and resources [closed]

I want to design an algorithm to distribute $n$ tasks into $k$ resources. Tasks have a length and they can be partitioned. And the aim of the algorithm must be that a task must end at the same time (...
2
votes
1answer
74 views

D* Lite - can edge costs be asymmetric?

I'm trying to modify the original D* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between ...
2
votes
1answer
107 views
+50

Skyline problem with triangular buildings

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites. The following are two variations from the usual Skyline problem: Report ...
0
votes
1answer
29 views

strange and different conclusions about Bellman Ford

Recently I asked a question Here about following topics: after finishing bellman ford algorithm, if BF continue to update distances and distance value related to one vertex v being updated,then v is ...
1
vote
1answer
21 views

Finding a minimum spanning tree that shares the minimum number of edges with the given one

Given some undirected weighted graph $\ G(V,E, w) $ and its minimum spanning tree $\ T$, I need to find another spanning tree $\ T' $ with minimal amount of common edges of both trees. If there are no ...
1
vote
0answers
28 views

How can I prove the correctness of the Hoshen–Kopelman algorithm?

I'd like to formally prove the correctness of Hoshen–Kopelman algorithm (link here https://en.wikipedia.org/wiki/Hoshen%E2%80%93Kopelman_algorithm). Anyway I don't know what is the right approach. At ...
1
vote
1answer
79 views

bellman ford and one surprizing fact

I ran into a very surprising local contest problem. after finishing bellman ford algorithm, if we continue to updating distance and distance of one vertex v being updated, then v is on negative cycle....
4
votes
1answer
120 views

Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?

Given a multiset $S$ of numbers, partition it into two subsets $S_1 $ and $S_2$. How to maximize the sum of their medians? For example, the median of {1,2} is ...
1
vote
1answer
41 views

find 3 points among some given 2D points such that the triangle includes another given point

Ideally, these would be the points that form the smallest (nondegenerate or degenerate) triangle. However, I can admit a large amount of approximation to get it to a lower order of complexity. I can ...
1
vote
0answers
27 views

combination of traveling salesman with knapsack

I am trying to create an optimisation process for a variant of the travelling salesman problem which is combined with a knapsack problem in the following way: Let there be a set of points $P$ on a two-...
3
votes
2answers
67 views

Given a vector of points, what is the fastest algorithm to find all pairs of points at a distance of 1?

Given a vector of points (on the 2D plane), what is the fastest algorithm to find all pairs of points at a distance of 1? Of course, I could use the $O(N^2)$ algorithm to check all pairs of points. ...
0
votes
0answers
37 views

How to build a data-structure for a moving points

Problem:- I have moving points in a 2d space with a fixed obstacle(A polygon) and a fixed destination. I want to find at what time Source(which is moving) can get a path to destination and what is ...
0
votes
0answers
9 views

A DFS update without re-running DFS after adding and removing an edge

Given an undirected graph $G=(V,E)$ I perform a DFS run on it, and among other information I get the visit time $s(\cdot )$ and the exit time $f(\cdot )$ per each node and the parent of each node. ...
0
votes
1answer
17 views

Beginning Algorithm Design and Proving

I know this is a general question, so you can address this by giving some examples that are specific to your field. I want to start learning algorithm design and consequently prove its convergence. ...
2
votes
0answers
53 views

Bowyer-Watson Delaunay Triangulation neighbour walk in $O(n^{1/d})$

The Bowyer-Watson Algorithm for creating Delaunay Triangulations works iteratively. Let's say that we have a Delaunay triangulation of $n-1$ points. Now we add the $n$-th point. In order to update the ...
3
votes
1answer
152 views

Efficient intersection of equivalence classes

Having two equivalence relations, both as a union find data structure with the same number of elements, what is the most efficient way to find the equivalence relation that is the intersection of both ...
0
votes
1answer
14 views

Can't figure out decision variable

Good Evening, I am trying to solve an exercise related to my algorithm designing course. I have understood the question and what it asks. I am required to formulate an ILP and then relax it to ...
2
votes
1answer
32 views

Range queries with O(N log N) build and O(1) query

I read somewhere that you can compute range queries in O(1) with O(N log N) preprocessing for any associative operation (but not necessarily invertible or idempotent). How do you do this? I know this ...
1
vote
1answer
19 views

Reducing a seating problem to maximum flow

Problem: We have p different families with $1 \leq i \leq p$ members for the $i$-th family. We also have q tables where table $t_j$ has a capacity of $1 \leq j \leq q$. We want no two members of a ...
2
votes
1answer
36 views

Minimum number of edges to remove from a graph, so that MST contains a certain edge

Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For ...
0
votes
0answers
12 views

Detect the actual edges of circle in directed graph [duplicate]

Okay so , I know how bellman -ford can detect a negative circle. My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the ...
1
vote
1answer
25 views

Finding a 'short' binary sequence not contained in a given binary sequence

Let $k>1$ be an integer, let $n = 2^k$. Let $s: \{0, \ldots, n-1\} \to \{0,1\}$ be any binary sequence of length $n = 2^k$. There are $n - k$ coherent subsequences of $s$ having length $k$, and the ...
0
votes
1answer
29 views

reduction from 3SUM to 3ARR-ARITH

The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist $i,j,k\in \{1,\cdots, n\}$ so that $A[i] + A[j]+A[k] = 0$. The 3ARR-ARITH problem is defined ...
-1
votes
0answers
52 views

Maximum flow: Dining problem

I have a network flow problem: There are $n$ people invited to a party, the age of person $i$ is $a_i$ years, the waiter must position them in a way such that: Everyone sits around a table There are ...

1
2 3 4 5
205