Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
0
votes
2answers
41 views
Two problems with sorting permutation
We have permutation $p$ of elements $1,\ldots, n$. What is the minimal number of operations required to sort this permutation (in ascending order), where permitted operations are:
a) select some ...
1
vote
1answer
13 views
How to compute the pareto frontier for dimensions higher than 2?
I'm looking for an intuitive way to compute the pareto frontier for dimensions higher than 2, i.e. a generalization of this (very nice) solution: How to compute the Pareto Frontier, intuitively ...
2
votes
1answer
39 views
Recurrences that cannot be solved by the master theorem
I am given this problem as extra credit in my class:
Propose TWO example recurrences that CANNOT be solved by the Master Theorem.
Note that your examples must follow the shape that $T(n) = ...
0
votes
1answer
29 views
Pattern in Fermat Factorization
I have the Fermat Factorizations of $n = pq$ where $p$ and $q$ are primes. I am trying to find a formula/pattern for the number of cycles required to perform the factorization in terms of $n, p, q$. ...
-1
votes
0answers
22 views
proof about Fermat's Algorithm
I need to prove a property about the value of $r$ in Fermat's algorithm: Here is some psuedo-code:
count = 0;
v = 1;
x = ceiling(square_root(n));
u = 2*x + 1;
r = x*x - n;
...
0
votes
1answer
38 views
Running Time for Fermat's Factorization Algorithm
Let $p$ and $q$ be odd primes s.t. $p<q$ and $n= pq$. How many cycles will Fermat's Factorization produce for $n = pq$? Here is some sample data I iterated: (I am having trouble solving for an ...
0
votes
1answer
19 views
Compute index from 2d array to find correspondent index in a flat array
I am a programmer (not a mathematicians), and I am encountering a problem in my software which, if possibly solved mathematically would save a lot of performance issues.
I have an array of arrays ...
2
votes
0answers
82 views
Convert an unsolved number theory problem into a shorter program?
This problem of Waring's is unsolved: For all $n \ge 2 $, $\lfloor (\frac 32 ) ^n \rfloor + {3^n} \, {mod} \; {2^n} < 2^n $. (Kubina and Wunderlich have tested this up to 471,600,000.) This can be ...
0
votes
1answer
41 views
Can someone explain?
How many times is the print statement executed, wehre i,j,k ∈ Z? Explain
For i := 1 to 12 do
For j :=5 to 10 do
For k:=15 downto 8 do
Print (i-j)*k
1
vote
1answer
56 views
is there are specific way to solve coupled first-order differential equations with coefficients varying?
suppose I have "n" coupled differential equation represented by the matrix, Y• = A Y , where Y• is the column matrix containing first derivatives, namely, y1•(t), y2•(t), ... ...
2
votes
1answer
93 views
Characterizing a real symmetric matrix $A$ as $A = XX^T - YY^T$
In my personal research and quest to better understand the subject, I have noticed something concerning the Cholesky factorization of symmetric matrices. Everything I have read states that a symmetric ...
2
votes
1answer
23 views
big O notation with asymptotically nonnegative increasing functions
Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show:
$f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh.
I can't quite figure this out, can ...
2
votes
3answers
70 views
What prime number generating algorithms are used?
You sometimes hear bout these huge prime numbers (RSA prime number challenge comes to mind) and I was curious about what algorithms or formulas prime-number generators use in practice ?
For example in ...
0
votes
2answers
75 views
Resolve this recurrence: $T(2^n) = T(2^{n-1}) + 2^n$
I need to resolve this recurrence:
$T(2^n) = T(2^{n-1}) + 2^n$
The conditions are:
Give a $\theta$ bound.
In case that cannot find a $\theta$ bound, provide tight upper ($O$ or $o$) and lower ...
0
votes
1answer
34 views
Is this a wrong solution to the smallest enclosing circle problem?
I have a set of points in $\mathbb{R}^2$ and I need to find the smallest enclosing circle, i.e. the circle with the smallest radius that contains all of the points belonging to the set.
I have the ...
