Tagged Questions
Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
1
vote
1answer
43 views
Most efficient algorithm for nth prime, deterministic and probabilistic?
What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically?
Deterministic
Iterate through only odd values, incrementing by $2$.
Divide each ...
0
votes
0answers
8 views
Extending the Miller-Rabin primality test to factor numbers?
I'm currently using a deterministic version of the Miller-Rabin test (using all bases up to a certain limit). What I'd like to know is if the algorithm can be extended to actually aid in factoring ...
2
votes
0answers
18 views
0
votes
0answers
13 views
Shipping algorithm
I have the following scenario that I want to find an algorithm for in order to put into a c# program: Transportation Inc is contracted to ship 2 ton crates from site A to site B and they want to find ...
0
votes
0answers
7 views
Recommend an intro to binary embedding algorithm
I'm working on my final year project which will establish an reasonable upper bound for one of the bandwidth problem in graph theory. I found difficulty on understanding an algorithm that construct an ...
1
vote
0answers
13 views
Prove $T(n) = 2T(\frac{n}{2} - 3) + n$ is $O(n\lg n)$
I just had an exam in my algorithms class and this was a question on it. I was able to craft a solution, but I'm not sure if my proof has errors.
$$\begin{align}
&\frac{n}{2}-3 < n & ...
1
vote
0answers
16 views
How to find a closed form formula for the following recurrence relation?
I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm -
$$T(n) = 7T(n/2) + \frac{18}{16}n^2$$ with the base case $T(1) ...
2
votes
2answers
45 views
a game of coloring edges of graph
I have a clique of size 5 which is partially colored(black or white). I have to color remaining edges so that each of the triangle has either 1 or 3 black edges. How should I go about coloring the ...
1
vote
4answers
48 views
How to find a closed form solution to a recurrence of the following form?
I need to find the closed form solution to the following recurrence -:
$ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a ...
2
votes
2answers
43 views
If I know that a polynomial (of order $k \gt 2$) has at most $1$ positive real root - can I find that easily?
[update 2] Urgghh - the time-consumption really stems only from the construction of the h-order polynomial. The time for finding the roots (only 10 to 20 times Newton-iteration because of my nice ...
0
votes
0answers
27 views
Step wise Step solutions to math problems
Wolframalpha provides step wise step solution to math problems like integration, differentiation, differential equations etc. I am working on similar project which shows step wise step solution to ...
0
votes
1answer
25 views
recurrence relation using induction method
By using the induction I have to the following recurrence solves to $T(n) = \Theta(n)$.
$T(n) = T(\lfloor n/2\rfloor) + T(\lfloor n/7\rfloor) + 2n, T(0) = 1$
0
votes
0answers
4 views
Locality-Sensitive Hashing for Documents with Minhash function
can anyone explain why LSH save computation time?
example:
if i have the following signature matrix:
...
5
votes
2answers
59 views
+250
Generating seating plans- maximal number of orderings with different adjacencies
Background:
So the school I work at has a policy that we try and sit the kids next to as many different other kids as possible throughout the academic year. This means rejigging the seating plan as ...
0
votes
0answers
12 views
In this insertion sort algorithm for example, how would I prove the algorithm's time complexity is O(n^2)?
Take the following insertion sort algorithm:
I know it's O(n^2) fairly easy by examining it. But as far as proving it's O(n^2), how would I go about doing that? I could add up all the operations, ...
