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

learn more… | top users | synonyms (1)

1
vote
2answers
114 views

GCD and LCM of three numbers

Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L? gcd(x, y, z) means the greatest common divisor ...
1
vote
1answer
45 views

Proof with $\Theta$

I am having a hard time proving the following statement: Suppose that the functions $f_1, f_2, g_1, g_2 : \mathbb{N} \rightarrow \mathbb{R}^{\ge 0}\ are \ such \ that \ f_1 \in \Theta (g_1) \ and ...
1
vote
2answers
208 views

Solving a recurrence by using characteristic equation method

How can I solve $$T(n) = aT(n-1) + bT(n-2)+ cn $$; where $a,b,c$ are constants. I could not figüre it out :( There are T(0) = d and T(1) = e, Thanks in advance.
1
vote
3answers
171 views

Fermats Little Theorem

I need help in the use of Fermat’s Little Theorem, in order to calculate the remainder of $5^{120}$ when divided by 19. Thank you.
1
vote
2answers
69 views

How can we find a new sum of multiplications based on a previous one?

Suppose wehave two sequences: $$(a_0, a_1, a_2, \dots, a_{2^n-1})$$ $$(b_0, b_1, b_2, \dots, b_{2^n-1})$$ We also have the following sum: $$\sum_{k=0}^{2^n-1}{a_k \cdot b_k}$$ I'd like to know the ...
1
vote
3answers
346 views

Big Oh Question

I have the following question: Is the following statement true or false? ** All logs to base 2 log2n is a memeber of O(log(n)) My attempt: log2n - clogn <= 0 log2 + logn - clogn <= 0 1 + ...
1
vote
2answers
236 views

A problem on Number theory

You are given three non-negative integers $A$, $B$ and $C$, find a number $X$ (say) satisfy $X^A \equiv B\pmod{2C + 1}$ and $0 \le X \le 2C$. I am inquisitive about how to approach this one?
0
votes
3answers
209 views

Subtracting two dates

I'm developing a software and I need to subtract two dates and then get a date again. I've been trying to solve this problem for a while and I have found some additional problems. One of these ...
0
votes
2answers
109 views

$T(n) = T (\frac{n}{5}) + \frac {n}{\log (n)}$ Solving

I want to find the bound for $T(n) = T (\frac{n}{5}) + \frac {n}{\log (n)}$. I tried with forward iteration and this is what i 've got $T(1) = c$ $T(5^1) = c + 5^1$ $T(5^2) = c + 5^1 + (5^2)/2$ ...
-2
votes
2answers
129 views

The number of elements of a finite group which is a quotient of a finitely generated free abelian group

Let $G$ be a finitely generated free abelian group. Let $\omega_1,\cdots,\omega_n$ be its basis. Let $\alpha_1,\cdots,\alpha_m$ be a finite sequence of elements of $G$. Suppose $\alpha_i = \sum_j ...
-2
votes
3answers
378 views

Find an algorithm to compute $(1! \cdot 2! \cdot3!\cdots n! ) \,\%\, x$.

You need to find the product of first n factorials $1! \cdot 2! \cdots n!$ modulo $109546051211.$ $1 \le n \le 10^7$. I need a fast algorithm for this.
8
votes
3answers
2k views

Will this procedure generate random points uniformly distributed within a given circle? Proof?

Consider the task of generating random points uniformly distributed within a circle of a given radius $r$ that is centered at the origin. Assume that we are given a random number generator $R$ that ...
7
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 ...
6
votes
6answers
254 views

Elegant way to solve $n\log_2(n) \le 10^6$

I'm studying Tomas Cormen Algorithms book and solve tasks listed after each chapter. I'm curious about task 1-1. that is right after Chapter #1. The question is: what is the best way to solve: ...
6
votes
1answer
274 views

Can a Pratt certificate for a prime be found in polynomial time?

Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
6
votes
3answers
266 views

Efficiently testing if sigma(n) = m

I'm trying to write a function that efficiently solves this problem: Given positive integers m and n, determine whether $\sigma(n)=m$. Of course I'm looking for a faster technique than "factor n, ...
6
votes
1answer
265 views

Algorithmic Analysis Simplified under Big O

Hi I am revising for my exams and I have the following inhomogeneous first order recurrence relation defined as follows: f(0) = 2 f(n) = 6f(n-1) - 5, n > 0 I ...
5
votes
1answer
95 views

Flip all to zero

I have a square grid of size $N$, with rows numbered from $0$ to $N - 1$ starting from the top and columns numbered from $0$ to $N - 1$ starting from the left. A cell $(u, v)$ refers to the cell that ...
5
votes
1answer
207 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
2answers
419 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
329 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
694 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
104 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
178 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
678 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
193 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
4answers
493 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, ...
3
votes
1answer
60 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
1answer
84 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
342 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
489 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
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)
3
votes
1answer
697 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
299 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
303 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
477 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
244 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
379 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
281 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
149 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
1answer
53 views

What's the Lucas version of the Möbius test for Fibonacci numbers?

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to ...
2
votes
2answers
91 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
3answers
3k views

Algorithms for Finding the Prime Factorization of an Integer

As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite. My question is about ...
2
votes
1answer
49 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 ...