Tagged Questions

Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
5 views

Bulk-loading R-tree with data with extent

When bulk-loading R-tree with points one can simply sort the elements by some coordinate and split to equal-sized chunks. But if the elements have some extent, sorting them by their coordinate value ...
2
votes
0answers
21 views

Quick method for approximate integer square roots

I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties: $(\bar{n}+1)^2>n$; $(\bar{n}-1)^2<n$; So we have ...
1
vote
1answer
48 views

Are conditionals necessary in computation? [duplicate]

I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for ...
0
votes
0answers
31 views

Algorithm for rope burning problem [on hold]

Generalized from a technical interview question: Original question: There are two ropes, each rope takes 1 hour to burn. But either rope has different densities at different points, so there’s ...
0
votes
1answer
42 views

Which algorithm to use to find all common substring (LCS case) with really big strings

I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need to find the LCS and other ...
1
vote
1answer
26 views

Find a 3-colouring using the 3-colourability decision problem

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to ...
0
votes
0answers
36 views

Place P particles in a N dimensional space as evenly as possible [on hold]

I get P particles and a "searchspace" of dimensions N and sizes X1...Xn. All variables are known, but I would like to distribute the particles as evenly as feasable across the space. Assuming the ...
0
votes
1answer
28 views

books on algorithms for beginners in Ruby or Python or C. Not too math heavy [on hold]

I am currently at student at Turing and I would like to learn more about algorithmic design while studying programming. Our school mainly deals more with web software, Ruby, and Rails, but I would ...
0
votes
0answers
18 views

Find Different area between two images

My purpose is to compare pixels between two images and find out minimal(optimized) rectangular area that contains all different pixels between images. Simply, I compared all pixels(for example ...
2
votes
2answers
43 views

Leveling array values with the smallest move

I'm not an expert of the theory of algorithm, so please forgive me if this problem is nonsense, but I want to find good algorithm to solve below problem. There is a array of integer each of which has ...
0
votes
0answers
16 views

How can an EE doing a project with large sets of data implement machine learning techniques?

I have a general overview of what machine learning is, but I have no idea how to implement algorithms etc. For ex: If I have a system where I have a sensor system to detect each food item a person ...
0
votes
1answer
31 views

Reference request for coding Knight's Tour

Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly good efficiency)?
10
votes
3answers
2k views

Is there an algorithm that provably exists although we don't know what it is?

In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it. I am looking for similar results in computer ...
-2
votes
1answer
42 views

Count positive subsequences in a sequence of numbers faster than $\Theta(n^{1.5})$

Find the total number of positive subsequences in a sequence of numbers with an algorithm that is faster than $O(n^{1.5})$. For example, {-2 3} is a positive subsequence of {1 -2 3} since -2+3 = 1 is ...
0
votes
1answer
18 views

2-way Graph Partitioning problem

We have a graph $G=(V,E)$ and we need to divide this graph into two clusters $A$ and $B$. Some pairs of vertices $u$, $v$ should not be in the same cluster, and we define an edge $(u,v) \in E$. The ...
-2
votes
1answer
14 views

Strongly connected components in graph

Statement:SCC in G is same as Rev(G) Ex:Consider the following graph g 0->1 1->2 2->4 3->1 4->3 The strong components set would be S={0,1,2,3,4} If I reverse the above graph (i.e) 1->0 1->3 ...
0
votes
1answer
10 views

How to identify statistically distinct features of different sets?

I have two non-overlapping sets of items, with feature counts for each. What standard algorithms can I use to extract the most statistically distinct features of each set? For example: Items served ...
0
votes
1answer
32 views

Need help to derive the Complexity!

Please help me regarding this one! What will be the communication and computation complexity of this code?? ...
1
vote
1answer
26 views

Finding approximately collinear points

my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my ...
2
votes
1answer
40 views

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3) I was told it takes: $$2(n-2) + 1 = 2n-3$$ However, I can't seem to figure out ...
-1
votes
2answers
43 views

Algorithms on Fibonacci Numbers [on hold]

I want to know if there exists algorithms that: Finds if number is Fibonacci number (not using golden mean) in $O(1)$. If we use golden mean, will it be logarithmic or constant, and why? Finds ...
0
votes
0answers
15 views

Domains in Evolutionary Algorithms where solution is a set of individuals

Can someone help me find domains in field of Evolutionary Algorithms where desired solution is a set of individuals(perhaps even whole population) and not single best solution. For example i want to ...
3
votes
1answer
28 views

Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
0
votes
1answer
63 views

k-center algorithm in one-dimensional space

I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution ...
0
votes
0answers
37 views

Optimizing Permutation Algorithm [closed]

I'm looking at Permutations Algorithm, the complexity of this algorithm is pretty high O(N*N!). The algorithm is based on this observations. GeneratePermutations("ABC")= [ABC; ACB; BAC ; BCA ; CBA ...
-1
votes
0answers
48 views

Can we tweak Mergesort to perform better than Quicksort? [closed]

Generally We know Mergesort has complexity $O(n\log n)$ and Quicksort has worst case complexity of $O(n^2)$, which rarely happens if we choose good pivot. I would like to know if there is some way to ...
0
votes
0answers
30 views

Number of all possible sequences [closed]

If I have a list of numbers, say $L = \langle5, 10, 15, 20, 25\rangle$, how could I make a program so that I get the number of sequences for which $a_i -a_{i+1}<10$, where $a_i$ is the $i^{th}$ ...
3
votes
0answers
15 views

Detecting coplanarity by given erroneous pairwise distances

This is the question I asked four months ago and took very satisfactory answers. However, I tackle a new problem now. Here, I summarize the original problem: We have points in 3D space. We do not ...
-1
votes
0answers
23 views

Amortized cost of increment counter problem

Consider the increment-counter problem, where now the counter is represented in base 10, the initial count is 0, and where the cost of an increment is the number of digits that change. (a) Show by ...
0
votes
0answers
26 views

Booth's Algorithm Multiplication

When multiplying signed integers by Booth's algorithm, does the multiplicand always have to be negative? What happens if multiplier and multiplicand are both negative? Does the algorithm still work? ...
-2
votes
1answer
11 views

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm Please help me to understand and complete this. I would very much ...
4
votes
1answer
135 views
+50

Fixed size set to contain the maximum number of given sets

I asked this question in SO here I have about 1000 sets of size <=5 containing numbers 1 to 100. {1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... ...
3
votes
3answers
479 views

Rigorous Proof of Insertion Sort

Currently I self study CLRS book (Outside of any course, so I got no access to an instructor) And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal. Here's the algorithm: ...
0
votes
0answers
18 views

Patent-free algorithm for labeling a MRF/CRF

At the moment I'm implementing a video segmentation algorithm for moved foreground / background. In the literature often a graph-cut algorithm is used, which is patented by US6973212. Are there any ...
0
votes
1answer
45 views

Proving that the average case complexity of binary search is O(log n)

I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations. But how would I go ...
0
votes
0answers
19 views

Efficient Power of Square Symmetric Matrix

It is known that computing the nth power of a matrix can be done in $O(D(n)+n \log(n))$ time, where where $D(n)$ is the time needed for diagonalization. What is known about square symmetric matrices? ...
1
vote
0answers
48 views

Prove that there always exists a fair driving schedule [closed]

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
-1
votes
1answer
30 views

Determine whether there is a valid rounding in a table of numbers

I was told this question would be better suited here: Suppose you have a table such as: $\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 ...
1
vote
1answer
24 views

Can there exist a recurrence relation for “sequential search”?

I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.
-1
votes
0answers
26 views

Deleting and querying the kth element [duplicate]

Given an array A containing N elements. I want to know what is best suitable data structure to handle these 2 queries : Delete Kth element from the array. Report current Kth element of the array. ...
4
votes
1answer
59 views

Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form

As stated in the title: Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form. For example: when $p = 2$ and $q = 3$ Next of $2^2*3=12$ is ...
1
vote
0answers
58 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
1
vote
1answer
28 views

Find the max of a convex function in fewest samples

Suppose there is a convex function, and a certain domain interval. I want to find the max of this function within the interval. The goal is to minimize the number of times the function is evaluated, ...
-1
votes
0answers
53 views

Algorithm to determine number of strings of length n under different constraints

I am looking for an algorithm that can find the number of sequences of length $n$ that can be made from $m$ different characters $\{x_0, x_1, \cdots, x_{m-1}\}$. Several additional constraints are ...
2
votes
2answers
85 views

How do I know if my algorithm is right (without coding)? [closed]

For some background : I think I am quite good at advanced (graduate/research level) mathematics and physics but I have no CS background. Now I am taking a graduate level class on algorithms. I ...
0
votes
0answers
45 views

Is there a poly time algorithm for finding all approximate zeros contained in $[0,1]$ of a continuous poly computable $f(x)$ with at most m zeros?

Specifically we know that for our function $f$ ($f$ takes real values), $\infty>f(0)>0$, while $-\infty<f(1)<0$. So the classical binary search will find an approximate zero within ...
-1
votes
1answer
23 views

Recursion problem to see if string fits in given pattern

If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g*a". A question mark can be replaced with one character and asterisk ...
2
votes
0answers
6 views

Finding maximum information gain subinterval of an array containing points from 2 classes

Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between ...
4
votes
0answers
66 views

Minimal covering circle

There are $n<10^4$ points on the plane. How can one approximately (with a given precision $2^{-20}$ of points' coordinates) find the minimal radius of a circle that covers some $k$ out of $n$ these ...