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
1answer
44 views

How to find all paths of length up to k between two nodes in a directed graph?

Let's say I have a directed graph represented as an adjacency matrix, and I'm given two nodes $u,v$ and a parameter $k$. Let's also say that the maximal degree of a node in the graph is $d$. What is ...
0
votes
1answer
41 views

Binary integer programming problem without exponential memory

Consider binary integer programming problem with n variables. I think the branch and cut algorithm takes exponential memory. What are existing algorithms without much memory? Please suggest.
1
vote
1answer
46 views

Method for combining derivative free optimization results of different data inputs

I am working on an algorithm that has multiple fixed parameters. The algorithm analyzes time series data and spits out a number. The fixed parameters need to be such that this number is as small as ...
4
votes
1answer
54 views

Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls

We are given $2n - 1$ boxes with a total of $B$ black and $W$ white balls. In the $i$-th, box there are $w_i$ white and $b_i$ black balls. It is required to choose $n$ boxes so that, the sum of the ...
1
vote
1answer
52 views

Determine whether given f is shortest path function

I have the following question: Let $G = (V,E)$ be a directed graph with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every ...
0
votes
0answers
34 views

Algorithm to calculate shortest path when updating the heaviest edge in a path [duplicate]

For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge. $$w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...
1
vote
0answers
15 views

Is there an heuristic for finding out the smallest height you can get when packing items in a tube?

It's sort of similar to bin packing, but instead of the minimum amount of bins,I was interested in just one infinite bin and finding out what's the smallest height you could get when you start packing ...
4
votes
1answer
43 views

Check if intersection of several 2D half-planes is empty

I have a large set of half-planes $a_ix+b_iy + c_i \geq 0$. What I need is is the fastest way to determine if they have at least one common point. Currently I build a convex polygon by adding half-...
1
vote
1answer
27 views

Average Case Analysis of Insertion Sort as dealt in Kenneth Rosen's “Discrete Mathemathematics and its Application”

I was going through "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the following algorithm of the Insertion Sort and also its analysis. The algorithm is quite ...
2
votes
1answer
30 views

Algorithm to turn gray-scale text into legible binary black and white text

I have an image with gray-scale anti-aliased text produced by Chromium and need to convert this into pure binary black and white text. Applying a simple binary threshold pass over the image causes ...
1
vote
0answers
34 views

How to estimate the number of elements inserted to a Bloom filter

A Bloom filter is a probabilistic data structure that allows encoding sets with false positives. Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
2
votes
1answer
101 views

Modified shortest path problem

For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{...
2
votes
1answer
37 views

Find a list of actions that result in desired state

I have a problem that I need to solve, and I'm looking for which area of computer science (algorithms. etc) would be appropriate to solve this problem. In the system we have a list of actions that a ...
0
votes
1answer
34 views

Efficient way to implement periodic events

I need to implement a system that can schedule and dispatch periodic jobs and needs to support a very high load (millions of jobs per second). Each job in the system has a period that is some multiple ...
2
votes
0answers
63 views

Filling a hole in an image in O(nlogn)

I have a grayscale image (given by a float matrix with values between [0, 1]) with a hole in it (a cluster of pixels/cells with values of -1). Definitions: The ...
2
votes
1answer
41 views

O(m+n) Algorithm for Linear Interpolation

Problem Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the ...
3
votes
2answers
145 views

Solving Exact2IS using IS

i encountered the following problem: Exact2IS ={G has exactly 2 independent sets} Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets. (i ...
4
votes
1answer
52 views

Efficient algorithm to map two differently-sized sets of numbers as closely as possible?

The problem I have two sets of numbers and need to find a mapping between those two sets, so that the total distance between two mapped numbers is as small as possible. Two numbers must not be mapped ...
0
votes
0answers
24 views

Balanced vs Unbalanced KD-tree range search/query complexity

I'm currently reading up on the time complexity of the range search/query for an unbalanced KD-tree. I see all these different articles where the same the complexity is O(sqrt(N)) where N is the ...
2
votes
1answer
85 views

Is X+Y sorting problem still an open problem?

I have found that X + Y sorting is an open computer science problem but that book was too old and then I have google it but didn't find any strong evidence that it ...
2
votes
2answers
75 views

Efficient way to reduce a binomial coefficient as a fraction

Here is the full problem. You need to calculate Euler's totient function of a binomial coefficient $C_n^k$. Input The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$. ...
1
vote
1answer
49 views

Time complexity of code running at most summation(N) times in a loop

Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration: ...
0
votes
0answers
33 views

How to calculate time complexity of KD-tree data structure [duplicate]

I have made a KD-tree data structure for a project I've been working on. But I can't seem to figure out the query complexity for it. What I know: I know that KD-tree is using BST structure, so for a ...
0
votes
1answer
28 views

Joining points of polygon in correct order

I have a point's array of some 2d shape(polygon). The polygon could be either crossed or convex, I don't know it. And I want to join those points in the correct order. My first thought was to take ...
2
votes
1answer
29 views

Responsive input sliders - is there a better way?

I am building an app where a user controls inputs via multiple sliders each with discrete steps. The app then uses the combination of slider values to run some calculations and returns back an output ...
1
vote
0answers
42 views

Convert tree with recursive relationship to parent-child tree

Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good ...
1
vote
1answer
36 views

On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne

I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case. This is the algorithm: ...
1
vote
0answers
33 views

1230C | Codeforces | Find count of numbers that divide all numbers in an array [closed]

Here is the question: Link. In a gist, we need to count the total count of numbers that would divide every number in an array. The approach that I took was that any number that has to divide all the ...
0
votes
0answers
14 views

Some Problem To Understand Petri Nets for detect deadlock in 2PL Locking

hi i read a paper and some section it's not clear for me please help me to understand it.. paper topic: A Deadlock Prevention Algorithm for The TwoPhase Locking Protocol Based on Petri Net basic ...
0
votes
1answer
62 views

Maximum sum path in a matrix

Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable by walking ...
1
vote
2answers
37 views

Analysis of Dijkstra algorithm's (Lazy) running time

I'm trying to figure out the running time for a Dijkstra algorithm. All the sources I have read say that the running time is O(E * log (E)) for a lazy implementation. But when we do the math we get ...
1
vote
1answer
28 views

Running Time Analysis of a Simple Binary Search Algorithm

I'm stuck with the following problem by Skiena (The Algorithm Design Manual, p. 106): Problem: Give an efficient algorithm to determine whether two sets (of size $m$ and $n$, respectively) are ...
0
votes
0answers
22 views

How does a prefix sum with 8 elements can be computed with three processors?

I would like to know if someone can give me an example of how a prefix sum which contains 8 elements can be computed with just three processors. Prefix sum
2
votes
3answers
322 views

Algorithm for ensuring that each element ends up in its specified range when composing a list

I am designing a feature recommendation system and I have encountered an algorithmic problem and I am wondering if any of you know if there are known algorithms to solve this type of issue. In our ...
1
vote
1answer
21 views

Search a number

Given n numbers, design an algorithm to find the smallest $n^{\frac{2}{3}}$numbers, in sorted order. (Assume $n^{\frac{2}{3}}$ is an integer.) I don't understand this question. Can I simply $x = n^{\...
0
votes
0answers
28 views

Algorithm always provide a $2$_$sum$ with at least ONE prime? In polynomial-time?

Function Problem: Given $N$ find a $2$_$sum$ that uses at least $ONE$ prime. Fact: Prime Gaps grow logarithmically on average. And, in worst case if memory serves correct it grows with a bounded ...
0
votes
1answer
28 views

Counting occurrences of word in a text

Let's say I have a long text of 1M words and I would like to create a table of all the words ordered by the number of occurrences in the text. One approach would be populating a dynamic array with ...
1
vote
1answer
30 views

Proving van Emde Boas recurrence

I have tried to solve the following question: van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$. ...
-1
votes
2answers
97 views

Constructing a rectangle of size nx2 with dominos and L-shaped trominos [duplicate]

The Question is from DP tiling a 2xN tile with L shaped tiles and 2x1 tiles? I want an explanation about this question or theory
0
votes
1answer
50 views

MST - algorithm to add an edge to the graph

I have some difficulty proving the correctness of my solution to the following exercise. Let $G = (V,E)$ undirected connected graph, $w \colon E \to \mathbb{R}$ weight function. Let $T$ a MST (minimum ...
1
vote
1answer
33 views

Longest Common subsequence theorem in CLRS

In CLRS in the dynamic programming chapter, there is a theorem about the longest common subsequence prefix that states the following: Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,...
2
votes
1answer
47 views

Algorithm for splitting an array into k sub-arrays

We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized ...
2
votes
1answer
50 views

Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to. In the 2-dimensional case it's fairly ...
0
votes
1answer
32 views

Number of minimum cuts in a graph

Situation : I started watching Algorithm Lectures from Stanford University (Corsera). I stuck on one video lecture(https://www.coursera.org/lecture/algorithms-divide-conquer/counting-minimum-cuts-...
0
votes
1answer
28 views

Maximum Circular Subarray sum

This is a question from the book Algorithms by Jeff Erickson. Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A[i .. j] or a suffix followed by a ...
2
votes
1answer
26 views

What is the fastest algorithm to solve $k$-path problem?

$k$-Path problem The problem: Given a graph $G$ with $n$ vertices and $m$ edges, does there exist a path of length $k$ in the graph? The trivial algorithm to solve is in $O^*(n^k)$ time using ...
0
votes
0answers
24 views

Source code or detailed explanation of “WKS” virtual memory compression algorithm?

I've been trying to find information on various program data virtual memory compression algorithms that are in the "WK" family of algorithms. So far, I've been successful with the "WKdm" compression ...
0
votes
2answers
30 views

Efficient way to concatenate strings to find specific split up values

I'm working with a list of objects ("Section") that contains a string value among other fields. The strings in all of the sections can be concatenated to form the complete text. I am, however, wanting ...
0
votes
0answers
18 views

BFS Tree of a complete graph

Can somebody explain the characteristics for a BFS Tree from a complete graph?. Thanks in advance. I would need the shape of the tree, explain me a little bit how the algorithm would work in this ...
1
vote
0answers
23 views

shortest string containing all binary palindrome of length n as substring

I am trying to compute the shortest binary string that contains all binary palindrome of length n as substring. For example, for n=3, 00010111 is such a shortest string. However, brutal force performs ...

1
3 4
5
6 7
175