Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
2
votes
1answer
23 views
Quadratic Forms and Newton's Method
Consider the function $f(x,y) = 5x^2 + 5y^2 -xy -11x +11y +11$. Consider applying Newton's Method for minimizing $f$. How many iterations are needed to reach the global minimum point? Why should ...
8
votes
2answers
162 views
Who is the oldest? (in a non-revealing way)
How can a group of people figure out who is the oldest, without revealing any other information?
Revealing all the ages to a trusted third party is not allowed. Preferably I'm looking for solutions ...
10
votes
2answers
103 views
Non-revealing maximum
How can a group of people find out their maximum age without revealing any other information to each other?
(Is there a book or web site about such non-revealing algorithms?)
Preferably I'm looking ...
0
votes
1answer
42 views
How do I determine if two of my software's representation of algebraic numbers are equal?
I have software which stores information about algebraic numbers with absolute precision. If you build it up by creating instances of a Python representation of an integer, float, Decimal, or string, ...
2
votes
0answers
29 views
Difference between two sets of data points
I'm making a simple calibration of a z-stage, by measuring a number of points in one direction with a constant $\Delta$Z between each sample. Then I reverse the direction and measure the same number ...
2
votes
1answer
33 views
Can someone offer an intuitive understanding of linear/quadratic probing and double hashing?
I'm reading through Introduction to Algorithms, and I'm having trouble grasping intuitively how linear probing, quadratic probing, and double hashing exactly work. I suspect my confusion lies within ...
2
votes
1answer
34 views
Can the Euclidean algorithm fail by not terminating in non Euclidean domains?
Is it possible for the Euclidean algorithm to fail by not terminating in finite time in non-Euclidean domains? In $\mathbb{Z}[X]$ it can fail by going out of the ring, ie one gets a non integer ...
2
votes
1answer
53 views
Solve the special congreuences equation?
the following congruencies
$\begin{matrix}
x_1\equiv1~(\mod m_1)\\
x_2\equiv1~(\mod m_2)\\
\vdots\\
x_n\equiv1~(\mod m_n)\\
\end{matrix}$
where $m_i, m_j(i\neq j)$ are pairwise coprime.
Now, I known ...
0
votes
0answers
30 views
The Rule of Product Principle has a formal name in combinatorics?
This question was migrated.
INTRO
The following algorithm do basic addition in an abacus, but not only this. Given n finity sets, it enumerates all subsets contaning one member of each set at a ...
1
vote
1answer
86 views
+100
Quicksort analysis problem
This is a problem from a probability textbook, not a CS one, if you are curious. Since I'm too lazy to retype the $\LaTeX$ I will post an ugly stitched screenshot:
This seems ridiculously hard to ...
1
vote
0answers
30 views
Software to Calculate Kernighan-Lin Algorithm on Graph
Is there any (free) software out there that can perform the Kernighan-Lin partitioning algorithm on a small graph?
2
votes
1answer
40 views
All nonisomorphic trees of order $n$
I have two questions regarding spanning trees:
Q$1$. Is there any formula for the number of distinct trees of order $n$? I don't mean labelled trees, just distinct trees. For example: for $n=3$ ...
2
votes
1answer
48 views
Is this algorithm reflective?
My algorithm takes an array of positive non-zero whole numbers and starts summing up the elements from left to right. When the sum goes above $50$, the sum goes back to $0$. The algorithm outputs how ...
1
vote
2answers
76 views
Need some help with this recurrence equation
I'm self studying from a book I bought to learn more about algorithms and I've been trying most of the exercises in that book, so this is not a homework. Anyways, the relation I'm trying to solve is
...
0
votes
0answers
37 views
General term of this sequence
I wanted to know the General term or the function to generate this sequence I found on OEIS.
It is the number of ways to express 2n+1 as p+2q; where p and q can be odd prime number and even semiprime ...
