Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
4
votes
1answer
272 views
Is there any mathematical trick?
Given two natural numbers I am supposed to reverse each of them and then sum them up and reverse the sum to get the final answer.
For example if the numbers are $4358$ and $754$ then the answer ...
4
votes
3answers
566 views
knapsack algorithm that looks too good to be true
I have an idea for solving the knapsack problem, but it looks too good to be true. I would like someone to explain potential problems with this approach. I'll give an example: I want to find a subset ...
4
votes
6answers
1k views
Finding the Heavy Coin by weighing twice
Suppose you have 100 coins. 96 of them are heavy and 4 of them are light. Nothing is known regarding the proportion of their weights. You want to find at least one genuine (heavy) coin. You are ...
4
votes
3answers
176 views
Can this algorithm on removing 1's from a (0,1)-matrix fail?
Let us be given a $n\times n$ matrix containing only zeros and ones.Now, the goal is to remove some 'ones' from the matrix (i.e. replace them with zeros) so that in each row and each column there is ...
4
votes
4answers
146 views
Determining the next Twin Prime?
A really simple I question I guess. Is there an algorithm or method such that given an integer N there is a way to determine the next twin prime pair greater than N?
If yes then could you please ...
4
votes
1answer
245 views
Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?
I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this:
Strassen’s algorithm is not at all obvious. (This might be the biggest ...
4
votes
3answers
424 views
Counting primes
Let $\pi(x)$ be the number of primes not greater than $x$.
Wikipedia article says that $\pi(10^{23}) = 1,925,320,391,606,803,968,923$.
The question is how to calculate $\pi(x)$ for large $x$ in a ...
4
votes
2answers
89 views
proving algorithm to check if two strings are anagrams-
I have this idea (using C language) for checking for two string if they are anagrams-
if the length of the strings is the same (its only a-z and A-Z).
sum of ASCII value of all chars in a string is ...
4
votes
2answers
292 views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
4
votes
3answers
582 views
Composition of permutation to generate all permutations
Looking at permutations I came up with the following question:
Can you find a permutation S of a set of n elements such that by composing this permutation n! times you will describe all the possible ...
4
votes
2answers
71 views
Minimum distance of a binary linear code
I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.
How can I find parameter $d$ efficiently?
I know the method that compute all the codewords and take ...
4
votes
2answers
388 views
Tranforming 2D outline into 3D plane
I am writing a program where I would like to allow the user to draw 4 connecting lines, such as:
And convert this shape into a 3D plane. Is this possible? Is there an existing algorithm to do so? ...
4
votes
2answers
1k views
Which is asymptotically larger: $\lg(\lg^* n)$ or $ \lg^*(\lg n)$?
This definition is extracted from "Introduction to Algorithm, 2nd Edition".
The iterated logarithm function
We use the notation $\lg^* n$ (read "log star of $n$") to denote the iterated ...
4
votes
5answers
146 views
Find a convex combination of scalars given a point within them.
I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me.
Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...
4
votes
2answers
209 views
Determining the equality of two real numbers
Can the equality of two real numbers always be determined?
Let us say that we have derived an expression for a real number X.
We also have obtained an (entirely different) expression for a real ...
4
votes
4answers
159 views
How to prove this approximation of logarithm of factorial
In other words, how to prove this equation
$$\lg{n!} = \Theta(n\lg{n})$$
4
votes
3answers
96 views
Congruence of terms
There is concept of Term Rewriting. If one have rules for rewriting terms, one can obtain some term from another. For example, rule1: a -> f(b); rule2: b->t. Term A(f(t)) can be obtained from term ...
4
votes
4answers
536 views
How can I change the Conway's Game of Life so that, eventually, all cells die?
Darwinia features an intro which represents a modified version of Conway's Game of Life.
You can see it in action here.
The game developers added one more rule about the game: no cell may live ...
4
votes
1answer
69 views
Do irrational number contain infinate/every patterns of sequences?
I guess the question is
"does an 'infinite' number of patterns imply 'every' number of
patterns?"
For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
4
votes
3answers
69 views
Need help about solving a recurrence relation
I have a recurrence relation which is like the following:
$$
T(n) = 2T(n/2) + \log_2 n.
$$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
$$
...
4
votes
1answer
85 views
Are there any secure ciphers you can use without a computer?
I have some kids that like encryption schemes such as the Caesar cipher and the Vigenère cipher. I would like to teach them something that's not easily breakable by todays maths and computers, but I ...
4
votes
4answers
227 views
Relationship between degrees of continued fractions
I'm trying to compute the values of differing degrees of continued fractions like $\sqrt 2$, e and other similar fractions. My theory was to take the reduced fraction at an arbitrary depth and the ...
4
votes
1answer
469 views
Genetic Algorithms
There is a lot of talk about methods that evolve to change(and improve), however, how does one go about building such a model.
For example, if there is a zero sum game, then, one would hope that ...
4
votes
1answer
632 views
Finding all n×n permutation matrices
If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions?
Here's Wikipedia on doubly stochastic matrices.
4
votes
3answers
411 views
Formally proving that a function is $O(x^n)$
Say I have a function $f(x) = ax^3 + bx^2 + cx + d$ where $a > 0$.
It's clear that for a high enough value of $x$, the $x^3$ term will dominate and I can say $f(x) \in O(x^3)$, but this doesn't seem ...
4
votes
2answers
169 views
Who proved the Master Theorem?
In all of the classes I've had on algorithms, and the books I've seen that talk about the master theorem, none of them mention where it came from, which is pretty odd. Certainly, it didn't just kind ...
4
votes
3answers
76 views
Measuring orderedness
I've found this a frustrating topic to Google, and might have an entire field dedicated to it that I'm unaware of.
Given an permutation of consecutive integers, I would like a "score" (real [0:1]) ...
4
votes
1answer
204 views
Is there a simple algorithm to generate unlabeled graphs?
While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
4
votes
3answers
487 views
How to approach number guessing game(with a twist) algorithm?
I posted this on stackoverflow, but was advised to also post here. It's kind of a math/algo question so I think it's kind of stuck between both worlds of math and computer science. I believe this to ...
4
votes
2answers
621 views
Subset sum problem is NP-complete?
If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
4
votes
1answer
308 views
Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$
I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.
I'm now searching for an intuitive, or geometric, or visual proof of ...
4
votes
2answers
59 views
Numerical search for periodic orbits
Suppose that $\phi$ is a map defined in all of $R^n$, with image also in $R^n$. Is there a known good algorithm to find the periodic points of $\phi$ of order $m$, (or fixed points of $\phi^m$) ...
4
votes
2answers
277 views
Inverse of symmetric matrix $M = A A^\top$
I have a matrix, generated by the product of a non-square matrix with its own transpose:
$$M = A A^\top.$$
I need the inverse of $M$, assuming $\det(M) \neq 0$.
Given the nature of the matrix $M$, ...
4
votes
1answer
199 views
algorithm related to XOR
I have $N$ values, $a_1,a_2,a_3\ldots a_N$.
Now let us say i could increase any of these values by any amount such that the XOR sum becomes zero.
$$(a_1+d_1) \oplus (a_2+d_2) \oplus \cdots \oplus ...
4
votes
2answers
182 views
Russian Peasant Method for multiplication
What exactly happens with the remainder in this algorithm? I don't understand why it is "dropped".
Example:
$$\begin{array}{c}
\text{Half}&&\text{Double}&\text{Remainder}\\ \hline
...
4
votes
1answer
197 views
Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?
This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi.
Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
4
votes
1answer
2k views
How to compute the Pareto Frontier, intuitively speaking?
I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost.
Now the question is 'how does one compute a pareto frontier'? ...
4
votes
2answers
117 views
Ordering vertices of a graph to so that adjacent pairs are connected
I am terrible at these kinds of discrete math problems, so I am asking here the following problem: Given a connected graph $G$ with vertices V[i], find an ordering P[] of its vertices such that there ...
4
votes
3answers
137 views
4
votes
1answer
849 views
How does Knuth's algorithm for calculating logarithm work?
I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm:
given $x\in[1,2)$, do the ...
4
votes
1answer
962 views
Understanding the Sieve of Atkin
I'm attempting to construct a program (in C++) that will count the prime factors of a given number for a Project Euler problem using the Sieve of Atkin, but I'm having trouble understanding a few ...
4
votes
2answers
152 views
Optimization without knowing function's form or derivative
I understand that this question may not have a corresponding answer.
We are developing a control algorithm using dynamic programming. Effectively we are change one input variable and then plot the ...
4
votes
1answer
486 views
Algorithm for computing square root of a perfect square integer?
My question is the following:
Is there a polytime non-numerical
algorithm for computing square root of
perfect square integers?
The more elementary the algorithm is, the better!
EDIT:
...
4
votes
1answer
364 views
Generating a Eulerian circuit of a complete graph with constant memory
(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices.
I would like to generate a Eulerian ...
4
votes
2answers
65 views
Accounting for changing radius of a paper roll to always unroll the same amount of paper
So I'm building a Post-Turing Machine that's running a 5-state busy beaver. It has a 300ft roll of receipt paper at each end simulating an infinite tape.
Hypothetically the tape is divided into ...
4
votes
3answers
176 views
4
votes
1answer
148 views
Is there an algorithm to find a basis for the lattice $V \cap \Bbb{Z}^n$ given a basis for $V \subseteq \Bbb{Q}^n$?
This might be a stupid/very simple question, but since I can't quite seem to come up with a nice trick I will ask it anyway.
Assume that we have a vectorspace $V \subseteq \mathbb{Q}^n$ given in the ...
4
votes
2answers
171 views
Why does the $2$'s and $1$'s complement subtraction works?
The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple:
$1.$ Find the $1$'s or $2$'s complement of the subtrahend.
$2.$ Add it with minuend.
$3.$ If there is ...
4
votes
1answer
111 views
4
votes
4answers
316 views
Calculation of Bessel Functions
I want to calculate the Bessel function, given by
$$J_\alpha (\beta) = \sum_{m=0}^{\infty}\frac{(-1)^m}{m!\Gamma(m+\alpha +1)} \left(\frac{\beta}{2}\right)^{2m}$$
I know there are some tables that ...
