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

learn more… | top users | synonyms (1)

1
vote
1answer
33 views

Master Theorem. How is $n\log n$ polynomially larger than $n^{\log_4 3}$

I was reading Master theorem from CLRS, and it said that $n\log n$ is polynomially larger than $n^{\log_4 3}$ while $n\log n$ is not polynomially larger than $n$. What does it mean to be ...
0
votes
0answers
30 views

Polynomial time algorithm for finding the chromatic sum of a tree.

As the title goes, a polynomial time algorithm for finding the chromatic sum of a tree is required. NOTE: Finding the chromatic sum of a graph is also called the sum coloring problem - The sum ...
1
vote
0answers
12 views

Using FFT to compute DFT of a polynomial

i currently studying about FFT and DFT and we were given simple question: Use the recursive FFT to compute the DFT of this polynomial of '3' degree: $$-1\:+\:4x\:+\:3x^2$$. So, i go to this ...
1
vote
1answer
36 views

Determining the coefficient of $x^n$ in $\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$

I looking for an algorithm to efficiently find the value$\mod p$ of the coefficient of $x^n$ in a generating function of this form: $$\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$$ where $p$ is some prime ...
0
votes
0answers
14 views

Blum Micali Algorithm Security By Seed Size

I'm coming from a computer science background, so I'm having some difficulty with these high level mathematics. With reference to the Blum Micali algorithm: (underscore represent subscript) ...
1
vote
1answer
60 views

Integer factorization: Single solution for integer equation

While working on my integer factorization project, I came to this: $(A + CX)(B + CY) = D$ $X,Y,A,B,C,D$ Are integer numbers $A,B,C,D > 0$ $X,Y >= 0$ $A,B,X,Y < C < D$ If $X=Y$ than $Y ...
1
vote
1answer
11 views

some notations in algorithm analysis

Assuming $k$ is a variable, 1.then someone claims that the algorithm complexity is super-linear or sub-linear in $k$, here what is the meaning by using super-linear or sub-linear? 2.also, if ...
5
votes
1answer
116 views

How can one find intermediate digits of a root of an algebraic equation?

I was wondering whether there is a way to find intermediate digits of an algebraic equation. For example, if I have $$234x^{\frac{1}{12345}}-24621x^{\frac{1}{3456}}=1$$ And I want to find the ...
4
votes
0answers
45 views

Algorithm for finding “fact families”

My friend's 3rd grader encountered the following question regarding "fact families" on her math homework: I was in 3rd grade sometime in the 1980s, so I don't believe I ever encountered this term ...
0
votes
3answers
36 views

Decompose a polynomial: find $f(x)$ such that $h(x) = f(g(x))$

I try to make an algorithm that decomposes a polynomial, ie find $f(x)$ such that $h(x) = f(g(x))$ by knowing $h$ and $g$. For example, having : $h(x) = 112x^6 + 1232x^5 + 2772x^4 - 3388x^3 + 847x^2 ...
4
votes
1answer
27 views

Algorithm concerning orthogonal matrices

Say I have a n-dimensional orthogonal matrix, with some of its elements given and these others unknown. Does there exist an effective algorithm to find out the unknown elements and restore the whole ...
0
votes
0answers
15 views

Algorithm to find the minimum of a function over a k-size partition of a set

I wish to compute the minimum value of a non-linear function over all possible size-k subsets of a given set of integers. Does anyone know about a specific algorithm to solve this problem?
0
votes
1answer
34 views

Relation between Genetic Algorithm and Information theory

Can anyone suggest me some references (papers, books, lecture notes) on the relation between GA and Information theory?
-2
votes
1answer
33 views

How to define human-friendly axis marking notches

I have a need to compute values of "tick" marks on an axis that uses various different min/max ranges. Specific example -- Picking Human-Friendly Notch Step Axis Y has function values range between ...
0
votes
0answers
34 views

Memory efficient algorithm to find network diameter

I am trying to implement memory efficient algorithm to find network diameter. So far I have classic bfs but it fills memory for large graphs (I am trying to work with Orkut data set) The ...
1
vote
0answers
27 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
0
votes
0answers
46 views

Hill Cipher issues

I am new to math and have took interest into hill cipher; thus, I have attempted to create my own codes, but have faced several issues. As you may know, hill cipher requires matrix to encrypt and ...
0
votes
0answers
29 views

Reducing places of petri net

I'm looking for algorithms for reducing places of a Petri net. Can I get any keyword or reference for such algorithms? Regards
0
votes
2answers
53 views

Finding big O of a function

How do I find Big O of function which are polynomial fractions $$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$$ The same question is posted here (Finding Big-O with Fractions) but i dont understand the ...
0
votes
0answers
31 views

Efficient and Elegant Subword-Tree Construction - trouble understanding compact representation

I'm reading the paper "Efficient and Elegant Subword-Tree Construction" by M.T. Chen and J.I. Seiferas and I'm having trouble understanding their compact representation to a Subword-tree, especially ...
0
votes
1answer
31 views

Finding the time complexity

Can someone please help me to solve this problem. Find a $\theta$ notation for the number of times $x=x+1$ is executed ...
3
votes
0answers
19 views

Finding lower bounds for solution of linear Diophantine equation in two varuables

I am currently encountering the following arithmetical problem : given four nonzero integers $A,B,C,D$, let $\Omega=\bigg\lbrace (x,y)\in{\mathbb N_{\geq 0}}^2 \ \bigg| \ \frac{Ax+By}{Cx+Dy} \in ...
0
votes
1answer
20 views

Feasible method of grouping relations

This might be a bad question, I hope not so bad. Problem is I have a set of relations(millions), presumably two arrays hold two nodes(starting, and ending), which together forms a relation(edge). I ...
0
votes
1answer
21 views

How do I place two points on two axis-aligned line segments such that they have given Euclidean distance l?

This is my problem: I am given two axis aligned line segments $l_1$ and $l_2$ of finite length and a distance $l$. How do I find points $p_1 \in l_1$ and $p_2 \in l_2$, such that $||p_1-p_2||_2 = l$? ...
2
votes
1answer
38 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
5
votes
0answers
46 views

A summation involving the ceiling function

I'm trying to find a better method of calculating the sum $$\sum_{k=1}^N\lceil ak\rceil^2$$ where $a$ is an irrational number. So far, my only idea is to somehow use a best rational approximation. ...
3
votes
0answers
41 views

Algorithm for Converting Rational Into Surreal Number

I'm writing a library in Haskell that represents the class of surreal numbers, which like many things can be read about here. I've run into a problem in converting between other classes of numbers ...
0
votes
0answers
33 views

Warshall's algorithm in transitive closure

Let $A=\{0,1,2,3\}$ and let $R$ and $S$ be the relations on $A$ described by the matrices $M_R= \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ ...
1
vote
0answers
16 views

Finding other two vertices when one vertex and each point on the triangle is known ?

I am working on some gesture recognition for my game. I am stuck on a problem. I have one vertex i.e the starting point and every point on the triangle, I also have the centroid. So how do I find the ...
0
votes
0answers
27 views

Will the area of all possible shapes created from 5 points always be the same?

I'm doing calculations on the locations of 5 points on a grid, and the locations change every second. I need to calculate how "grouped" or "packed" the points are and I was guessing that calculating ...
0
votes
0answers
42 views

Explanation of the TrueSkill bayesian ranking algorithm in a two-person game, like Tennis?

TrueSkill is mostly used for ranking and matching players on Xbox Online Games, it is a general rating model that could be applied to any game, including Chess, Tennis or Football. It models every ...
3
votes
0answers
101 views

How can I convert a recursive equation to a non-recursion one? [duplicate]

While I am aware of several other similar question which have been asked in the past, my mathematical education only extends through calculus, making them beyond my comprehension, and I believe this ...
0
votes
1answer
16 views

Finding other two vertices of a triangle from centroid and one vertex?

I am working on some gesture recognition for my game and I want to find if a point is inside the triangle created by the user or not. For that I need three vertices. Currently I am using the '$1 ...
0
votes
0answers
62 views

Can $n$ vertices be removed so the directed graph contains no cycles?

Given a directed graph and $n\in \mathbb N$ how can we verify if there exists $A \subseteq V$ so that $\left | A \right | \leq n $ and $G-A$ does not contain cycles?
5
votes
1answer
120 views

Finding the location of an image of the Mandelbrot set

I've got an image of a segment of the Mandelbrot set that I generated with an iPhone app a long time ago (I use it as my background image). I now have no idea where in the set the image came from. ...
0
votes
2answers
78 views

Prim , Kruskal or Dijkstra

I've a lot of doubts on these three algorithm , I can't understand when I've to use one or the other in the exercise , because the problem of minimum spanning tree and shortest path are very similar . ...
3
votes
0answers
49 views

$n$ solutions Sudoku

Is there an algorithm which can calculate a $9 \times 9$ Sudoku with non-trivial $n$ possible solutions? So if you play it you can play it for example 4 times? So if you play it there's a choice in ...
5
votes
1answer
113 views

Moscow puzzle. Number lattice and number rearrangement. Quicker solution?

I have already considered chains of numbers like $4-19, 19-9, 9-22$, to solve the problem and got the answer. However just out of curiosity, can anyone think of a better/quicker solution? (answer ...
0
votes
2answers
94 views

Problem in game theory related to traffic networks

I have learnt game theory for a short period of time and I am not familiar with multi-player non-zero sum games. Here is a problem from my book which I am stuck: In this road network below each of ...
0
votes
0answers
39 views

Conjectured optimal running time for integer factorization

While detecting prime numbers is computationally fast ($O(\log^3 n)$), the fastest known algorithms to split a composite number into its prime factor are very slow (RSA cryptography relies on this ...
1
vote
1answer
60 views

Check for valid statistics

Alice conducted a voting about N of his opinions. A[i] percent of people voted for opinion number i. This statistics is called valid if sum of all A[i] is equal to 100. Now let us define rounding up ...
2
votes
0answers
96 views

Least Impossible Subset Sum

Given a set A which contains natural numbers from 1 to N. Also given another set B which contains p natural numbers between 1 to N. We have to find out the least sum of subset which is not possible in ...
2
votes
0answers
63 views

Fastest way to find modular multiplicative inverse

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in ...
0
votes
1answer
21 views

Average time for a brute force shuffling algorithm to terminate

I was going through the Udacity CS212 class on program design, and the teacher(Peter Norvig) was explaining why a specific shuffling algorithm was inefficient(shown here). The algorithm consists of ...
0
votes
0answers
19 views

Polynomial-time algorithm to decide polytope equality $\{x \mid Ax \leq b\}=\{x \mid Bx \leq d \} $

This is a homework. Given two sets of inequalities $$Ax \leq b ,\,Cx \leq d ,\,x \in \mathbb{R}^n$$ where the coefficients are all rationals. Give a polynomial time algorithm to decide if: $$\{x ...
2
votes
0answers
124 views

Minimum Sum that cannot be obtained from the 1…n with some missing numbers

Given positive integers from $1$ to $N$ where $N$ can go upto $10^9$. Some $K$ integers from these given integers are missing. $K$ can be at max $10^5$ elements. I need to find the minimum sum that ...
0
votes
1answer
373 views

Count permutations with LCM

Given $N,M$ and $D$ we need to count how many permutations of $N$ integers are there with each $i$'th element $1 \le A[i] \le M$ such that least common multiple (LCM) of all its elements is divisible ...
2
votes
2answers
134 views

How can I convert camera motion into zoom?

I try to reconstruct a camera of a video sequence via match moving techniques. After the reconstruction process all seemed to work as expected, but then I've realized my camera is moving forward ...
0
votes
2answers
562 views

Minimum moves to destroy

N one dimensional kingdoms are represented as intervals of the form $[a_i , b_i]$ on the real line. A kingdom of the form $[L, R]$ can be destroyed completely by placing a bomb at a point $x$ on the ...
0
votes
0answers
62 views

Algorithm to calculate powers

Is it possible to write an algorithm that uses only multiplication and addition to calculate $a^b$ where both a and b are real numbers?