Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

6
votes
2answers
6k views

How to calculate the number of decimal digits for a binary number?

I was going to ask this on Stack Overflow, but finally decided this was more math than programming. I may still turn out to be wrong about that, but... Given a number represented in binary, it's ...
5
votes
1answer
201 views

solve $\ln(n!) = \Theta(n\ln(n))$ without stirling approximation

My homework was proving this equation which is simple using Stirling approximation. I was wondering if there is any other method to prove it - whithout Stirling - I can prove $\ln(n!) = O(n\ln(n))$ ...
5
votes
7answers
3k views

Prime number generator, how to make

Can anybody point me an algorithm to generate prime numbers, I know of a few ones (Mersenne, Euclides, etc.) but they fail to generate much primes... The objective is: given a first prime, ...
5
votes
2answers
394 views

Clustering algorithm to cluster objects based on their relation weight

I have $n$ words and their relatedness weight that gives me an $n\times n$ matrix. I'm going to use this for a search algorithm but the problem is I need to cluster the entered keywords based on their ...
5
votes
2answers
327 views

Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
5
votes
1answer
1k 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 ...
5
votes
5answers
687 views

Least wasteful use of stamps to achieve a given postage

You have sheets of 42-cent stamps and 29-cent stamps, but you need at least $3.20 to mail a package. What is the least amount you can make with the 42- and 29-cent stamps that is ...
4
votes
2answers
102 views

Longest increasing subsequence part II

Using the answer provided here, I am now trying to find the longest increasing subset in two different sequences of numbers defined by location1 and location2. For each location there are 16 ...
4
votes
2answers
173 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
2answers
672 views

Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ...
4
votes
1answer
68 views

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
4
votes
1answer
186 views

Reasoning the calculation of the Hilbert's distance

I'm not a mathematician, I'm a computer science student, and I'm attending to a course called Advanced Functional Programming. There's this homework where I need to implement the Hilbert R-tree data ...
3
votes
1answer
55 views

filling an occluded plane with the smallest number of rectangles

I've got a specific problem which I'll try to describe as clearly as possible. I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular ...
3
votes
2answers
373 views

Algorithm of cutting a polygon into equal parts

I have a convex polygon. I need to divide it into 4 equal parts using the two slit. For example, if I have a square, I have to cut it along the diagonals. Are there some common algorithm for this ...
3
votes
1answer
77 views

Effecient way to find optimal solution in a 2 player game

I have a function: \begin{equation*} f(a_1,\ldots,a_7,b_1,\ldots,b_4)=-14-7 a_1+30 a_1 a_2-7 a_4-2 a_4 a_5+21 a_6+21 a_7+16 a_1 b_1-24 a_1 a_2 b_1+6 a_4 b_1-6 a_4 a_5 b_1+6 a_1 b_2-6 a_1 a_2 b_2+8 a_4 ...
3
votes
1answer
89 views

Algorithm/Procedure for finding $\sigma$ such that $\omega=d\sigma$

I know that the Poincare's lemma asserts that under certain conditions a differential form $\omega$ is exact, i.e. it possesses an antiderivative $\sigma$, such that $\omega=d\sigma$. But as ...
3
votes
1answer
56 views

Parametric Weighted Graph problem

Let $G=(V,E)$ be a weighted directed graph with edge-weights given by linear functions $f_i(x) = ax-b$, $0 < a < 1$, $b > 0$. For a given starting parameter $x_0$, a path from $v_i$ to $v_j$ ...
3
votes
2answers
336 views

Linear equation system in modular aritmetic

Can someone explain me how to solve linear equation system in modular aritmetic when i have less equations than variables. I need algorithm for this, something with gaussian matrix maybe. $$4x_1 - ...
3
votes
1answer
468 views

Searching a Young tableau

An $n \times n$ Young tableau is an $n \times n$ matrix of distinct integers, with each row and each column sorted in increasing order. Now, we are given an $n \times n$ Young tableau $T$ and an ...
3
votes
1answer
678 views

Shortest distance between two shapes

This is the scenario of my problem. I have an image of two objects ( of arbitrary shape, not convex, not touching or crossing each other, kept a few space apart). And I am supposed to find the ...
3
votes
1answer
292 views

How many non-isomorphic permutation selections are on an arbitrary N x N square matrix with rotations applied?

My question is an extension to a classic one: On a square $N \times N$ grid, select exact $N$ cells that satisfy condition: only one cell selected in same row and column. How many solutions will ...
3
votes
0answers
297 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
3
votes
2answers
466 views

$3 \times 3 $ Magic Square of Squares

On picture below is three-by-three magic square in which seven of the entries are squared integers, found by Andrew Bremner of Arizona State University (and independently by Lee Sallows of the ...
3
votes
1answer
239 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
3
votes
2answers
372 views

Asymptotically optimal algorithms

Suppose one has an algorithm to solve a problem using at most f(n) computations with size of input n. How to prove, if such is the case, that this algorithm is the fastest possible for solving this ...
3
votes
2answers
141 views

The fundamental group of $K_{3,3}$ — relationship between its generators and embedding into manifolds

So I've been reading this wonderful PDF textbook on algebraic topology: http://www.math.uchicago.edu/~may/CONCISE/ConciseRevised.pdf In particular, I'm very interested in the chapter on graphs. This ...
3
votes
5answers
270 views

good resources for getting started with algorithms

I am reasonably mathematically competent and use algorithms regularly in computing, however I have started reading through 'introduction to algorithms' but find I need to understand a few more basics ...
3
votes
0answers
146 views

Algorithm/Formula to compute adding and/or removing compound and/or non-compound percentages from a value?

I will first start with a scenario, I have to apply some adjustments to a particular value. These adjustments are either compound or non-compounded and they can either be added or subtracted to the ...
2
votes
4answers
463 views

Numbers whose digits sum to 7

Let $S$ be the sequence of all positive integers whose decimal digits add to exactly 7, in increasing order: $$S = \langle7, 16, 25, \ldots, 70, 106, 115, 124, \ldots 160, 205, \ldots, 10230010, ...
2
votes
2answers
87 views

How do I apply the $\pm4$ part of the equation $5F_n^2\pm~4=L_n^2$ without knowing $n$?

I'm trying to test a great many numbers $a^3+b^3$ to see if any of them are Fibonacci using the formula $$a^3+b^3=F_n \iff 5(a^3+b^3)^2\pm~4=L_n^2$$ I want to make my search more efficient by having ...
2
votes
1answer
47 views

Counting permutations, with additional restrictions

There are 10 slots and some marbles: 5 red, 3 blue, 2 green, how many ways can you fit those marbles into those slots? Those marbles fit in 10!/(5! 3! 2!) ways ...
2
votes
1answer
151 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) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
2
votes
1answer
69 views

Modulo in e-voting paper is wrong?

I am trying to run in my mind the registration phase that exists in the paper: Internet Voting Protocol Based on Improved Implicit Security (pdf). I have chosen as parameters the following: the ...
2
votes
1answer
45 views

Efficient modular exponentation of powers

Is there any way to efficiently compute $(((\mathrm{base}^{M_1})^{M_2})^{M_3} \dots )^{M_n}$ modulo $P$, where $P$ is prime? One way is to repeatedly do modular exponentiation for each of the powers. ...
2
votes
2answers
125 views

How to effectively distribute points on plane

I have a plane (screen) with its width and height (monitor resolution, not square). And I'd like to distribute points on that plane with the (approximately) same distance from each other. For ...
2
votes
1answer
78 views

Details about “fingerprinting” algorithms for groups?

where can I find details about "Fingerprinting" algorithms (to test whether two groups are non-isomorphic) "‘Fingerprinting’: For every group $G_1,…, G_r$ evaluate various isomorphism-invariant ...
2
votes
3answers
81 views

Understanding $O$-notation and the meaning of $\Omega$

I am studying algorithms, and I have problems on the concepts from an exercise. Thank you so much! Which of the following equations lie in $O(n)$, $\Omega(n)$, $\Theta(n)$ and why. a. ...
2
votes
2answers
111 views

Combination/Permutation Question

I'm trying to solve a programming challenge, and I have narrowed down all the challenge to a combination/permutation problem. I ended up with 5 possible scenarios, and I need to find all possible ...
2
votes
2answers
3k views

Explanation on arg min

would someone be so kind to explain this to me: Especially the arg min part. (it's from the k-means algorithm)
2
votes
4answers
286 views

why $m$ power by $n$ equals sum of $n$ numbrs

$$m^n=\sum_{i=0}^n(m-1)^i\binom{n}i$$ (a) I want to find a formula for the above and then prove it by induction. But there is two variable right those are $m$ and $n$. I know that this is true, ...
2
votes
2answers
770 views

Expressing a Non Negative Integer as Sums of Two Squares

I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers. ...
2
votes
2answers
228 views

Shortest paths from $s$ by weight which contain even number of edges

Given a directed graph $G=(V,E)$, and a vertex $s\in V$, for every edge there's an integer weight $w(e)$ (positive or negative), I need to find an algorithm such that for every vertex $v \in V$ it ...
2
votes
2answers
2k views

how to distribute n red and m blue balls in some containers to maximize probability of random picking a red one from them?

This is an interview question. Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is ...
2
votes
1answer
351 views

Computing Hermite Normal Form using Extended Euclidean Algorithm

I am trying to calculate the Hermite Normal Form of a square $n \times n$ matrix using the Extended Euclidean Algorithm to compute the columns of the HNF matrix, rather than the standard (column) ...
2
votes
3answers
624 views

calculating unique value from given numbers

let's say I have some (n) random numbers 12, 13, and 18. I want to calculate some unique value from these three such that if I change their order 13, 12, 18 or 18, 12, 13..whatever order they are in, ...
2
votes
2answers
207 views

Mixed strategy nash equilibria in from $2\times N$ bimatrix form

I'm looking for a way of finding (manually!) mixed strategy Nash equilibria in a $2\times N$ game. Calling player 1 the player with two strategies and player 2 the one with $N$ strategies, I've ...
2
votes
1answer
197 views

Asymptotic upper bound of Bisecting trees

The question is : B-3 Bisecting trees Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced ...
2
votes
2answers
155 views

Deciding whether a given number is a totient or nontotient

The following algorithm decides if a number $n>0$ is a totient or a nontotient: ...
2
votes
1answer
790 views

Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull