Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

4
votes
3answers
1k views

1/f “Pink Noise” for the Math-Disabled

I have very little skill when it comes to math beyond all the elementary level operations (addition, subtraction, multiplication, division, mean, mode, etc) and a vague grasp of statistics, what a ...
0
votes
1answer
48 views

Bounding $\Sigma_{v\in V}(d(v)(\Sigma_{v'}d(v'))$ in a graph

Let $G=(V,E)$ be graph, I know that $\Sigma_{v\in V}d(v)=O(|V|+|E|)$. In my algorithm I go over each $v$ and for each $v$ I look at all of his neighbors and their neighbors and I do constant time ...
3
votes
5answers
295 views

Graph Theory Distance Algorithm

My own problem: Let G be a undirected graph with $n$ vertex and $m$ edges. We have a list that $v_{1} \rightarrow v_{2}$ but it's not important now. Every edge has a weight equal to X. Our task is ...
1
vote
0answers
29 views

3D orientations from distance constraints

I want to determine the relative orientations within a set of rigid 3D objects given some pairwise distances between certain points on pairs of objects. There are sufficient constrains to fully ...
2
votes
0answers
533 views

Logistic regression algorithm in Casio and Texas Instruments calculators

When using logistic regression on a Casio or Texas Instruments calculator, the output is of the form $$f(x) = \frac{c}{1+ae^{-bx}} $$ The problem I have (when teaching in a class where both types of ...
0
votes
2answers
528 views

Worst case analysis of a basic algorithm

I'm wondering how to perform a worst case analysis on a such algorithm. The basic operation is function. ...
6
votes
1answer
859 views

any idea what fractal algorithm might generate this shape?

I Found this image around, and i'm curious what algorithm generates this kind of shape In particular, i'm curious how the flow lines are generated, since usually the Mandelbrot iteration just ...
1
vote
1answer
902 views

How can one grab a random node from a binary tree without flattening it?

For practice developing algorithms, I am challenging myself to write an algorithm that picks a random node in a binary tree. I do know the number of nodes in the tree. I can obviously do this by ...
1
vote
2answers
2k views

Big O Notation and finding witnesses

I am trying to figure out some stuff here with Big O Notation. I mean I understand the concept of it and can generally be able to tell what the efficiency of something is, but I do not really ...
0
votes
2answers
96 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 ...
4
votes
1answer
483 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 ...
3
votes
1answer
4k 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) = aT(...
0
votes
3answers
193 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
vote
2answers
495 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 ...
2
votes
1answer
239 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 (A):...
3
votes
1answer
501 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} \bmod{2^n} < 2^n $. (Kubina and Wunderlich have tested this up to $471,600,000$.) This can be ...
6
votes
2answers
834 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ $$\begin{...
-2
votes
1answer
63 views

Can someone explain? [closed]

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
375 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), ... yn&...
4
votes
1answer
640 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
3answers
704 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 someone ...
2
votes
3answers
872 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
161 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 ($\...
1
vote
2answers
1k 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 ...
2
votes
2answers
1k 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. ...
0
votes
3answers
587 views

Algorithm to find all vertices exactly $k$ steps away in an undirected graph

This question may be better served at cs.SE, but I am not very familiar with CS lingo, so I'm hoping the maths community would be able to answer it as well... I have an undirected graph, and I am ...
1
vote
1answer
142 views

Glicko 2 Formula

I'm trying to learn about glicko 2 rating system . In that document, there is a formula in step 5, point 2 that says $$B = a - k\sqrt{\tau^2}$$ Can anyone explain what is the point of squaring the ...
2
votes
0answers
222 views

intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
2
votes
0answers
417 views

Incremental algorithm for variance of geometric mean

For our application, I'm trying to find a memory-efficient, incremental algorithm to maintain variance of geometric mean. This "online algorithm" on Wikipedia seems excellent, http://en.wikipedia....
0
votes
1answer
109 views

Showing a recurrence is $\Theta$(n)

Specifically how do you go about showing that $$ 2T(n/2)+1 =\Theta(n) $$ Not looking for an answer, as much as the process? I'm studying for a test and this is one of the review problems. Thanks in ...
1
vote
1answer
590 views

Sum of series with log in each term

I was solving recurrence relation of Introduction to Algorithms by {Cormen, Leiserson, Rivest, Stein}, 3rd. edition. Problem 4-3 (i) $$ T(n) = T(n-2) + \frac{1}{lg \; n} $$ I tried few ways, like ...
1
vote
1answer
103 views

Is the following algorithm to check if a point is on a line correct?

I need to check if a point is inside a rectangle (which can be not parallel to the axes) but not on its perimeter. In 2 dimensions. I'm checking if the point is inside by finding the intersection ...
5
votes
1answer
233 views

Permute the values in each row in a matrix such that the columns sum to the same amount.

The general problem Given a matrix, I would like to permute the order of values in each row, so that all the columns of the matrix sums to the same value. A simple example For example, given: <...
7
votes
1answer
2k views

What would be a good method for finding the submatrix with the largest sum?

This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge. Given:A Matrix (Not necessarily square) filled with negative and positive integers.What ...
21
votes
3answers
661 views

Finding the Robot

There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory ...
2
votes
0answers
36 views

How many ways are there to place the ball in N different bags under given condition? [duplicate]

Possible Duplicate: In how many ways we can put $r$ distinct objects into $n$ baskets? I have a doubt in following Combinatorics question : There are N bags, and there several balls of 4 ...
1
vote
2answers
391 views

What is the fastest algorithm to check if a number has only 3 divisors?

Which is the fastest way to check if a number has only 3 unique factors ? Any help will be highly appreciated?
0
votes
2answers
487 views

Universal Formula for Expanding Brackets

I know how to expand brackets such as the following in general, using the foil or crab-claw methods, but my tutor mentioned that there is a universal formula/algorithm for an expansion. E.g Bracket: ...
1
vote
1answer
146 views

Big-Oh of $\log (n^x)$

Prove that if $d(n) = \log(n^x)$, where $x$ is a constant greater than zero, then $d(n)$ is $O(\log(n))$. I have attempted this solution but it seems to me that $\log(a) > \log(b$) if $a > b &...
3
votes
0answers
732 views

Checking whether a string is interleaving of two other strings

I am trying to develop an algorithm to check whether a string s3 is interleaving of another strings s1 and s2. Say s1="abc" and s2="abe", then possible interleavings are ababce, ababec or abcabe. I ...
2
votes
0answers
103 views

Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
0
votes
1answer
516 views

matching sets of coordinates

I'm having a tough time describing my problem, so I'll present an example instead. I have a set of Cartesian coordinates [(1,2) (2,2) (3,3) (4,5) (5,5)] I also have an array of sets of Cartesian ...
4
votes
1answer
100 views

Computing binomial symbols modulo m

While procrastinating, I decided to play around with computing binomial symbols modulo $m$, $$\binom{n}{r} \equiv q \pmod{m}, 0 \leq q < m.$$ Using Pascal's formula, I discovered that this may be ...
1
vote
2answers
518 views

Sorting Algorithm analysis on a list of 0 and 1 element.

I'm trying to understand the difference would it make if following sorting algorithms are given a set of binary inputs i.e. collection of 0 and 1's only. a) Heapsort b) Quicksort c) MergeSort d) ...
1
vote
1answer
2k views

How does karp reduction work? [closed]

I understand karp reduction can be used to change a problem and calls an oracle. But what is the oracle? How is it used? What are the details of a karp reduction? What is it that is reduced? I found ...
6
votes
7answers
10k views

How do I compute binomial coefficients efficiently?

I'm trying to reproduce [Excel's COMBIN function][1] in C#. The number of combinations is as follows, where number = n and number_chosen = k: $${n \choose k} = \frac{n!}{k! (n-k)!}.$$ I can't use ...
2
votes
0answers
79 views

A question on algorithm complexity

It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...
4
votes
3answers
180 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]) ...
1
vote
4answers
1k views

Generate unique number, from 2 different numbers [closed]

I have 2 different numbers, from example 7 and 8. I need generate third "unique" number using given numbers, that is, if from 7 and 8 we obtain some X number, this X number not will be obtain from ...
2
votes
2answers
64 views

Find factor of sample elements given the median

I have a sample $S(x)$ containing $n$ elements: $$S(x)=\{ s_1 x, s_2 x, \ldots, s_n x \},\qquad s_i \in \mathbb{R}, x\in \mathbb{R^{+}}$$ Every element in the sample is multiplied by $x$. Now ...