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)

0
votes
3answers
617 views

Number of combinations avoiding k consecutive elements

I had come across this problem. Consider the list of numbers from 1 to 100. How to find the number of combinations, such that no combination has k consecutive elements? (k is any constant, it can be 3 ...
2
votes
1answer
239 views

Maximizing a linear combination of certain integers

Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a ...
2
votes
3answers
800 views

Counting subsets containing three consecutive elements (previously Summation over large values of nCr)

Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$. ...
3
votes
1answer
68 views

Show that we can compute the product $n = \Pi_in_i$ in time $O(len(n)^2)$ for given integers $n_1,…n_k$ with each $n_i> 1$.

Show that we can compute the product $n = \Pi_i\ n_i$ in time $O(len(n)^2)$ for given integers $n_1,...n_k$ with each $n_i> 1$. I know that we can compute $ab$ in time $O(len(a)len(b))$ courtesy ...
8
votes
3answers
2k views

How can I explain this integer partitions function recursion?

How to explain how this algorithm works? I need to write an article about this but I can't explain why this recursion works fine. It defines the number of partitions of a given integer ...
2
votes
1answer
1k views

Induction proof of lower bound for $\sum \sqrt n$

I'm having some trouble proving the following statement using mathematical induction: $$\frac{1}{2}n^{\frac{3}{2}} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} + \sqrt{4} + ... + \sqrt{n} ,\text{ (for ...
1
vote
1answer
44 views

How do I project points such as to extend a curve?

Given a roughly drawn line (i.e. a squiggle) consisting of, say a few dozen points, how do I extend the line in keeping with the last few points of the line, i.e. if the line was curving downwards at ...
1
vote
2answers
120 views

Find $y=\sqrt{x}$ where $x$ and $y$ positive integers in polynomial time?

Let $x$ be a positive integer and let $y$ be a real number such that $$y=\sqrt{x}$$ Objectives: If $y$ is an integer, find it in polynomial time. If $y$ is not an integer, prove that there is no ...
3
votes
2answers
2k views

Algorithm to generate a prime number which is n-digits long

Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?
2
votes
0answers
81 views

Proving that an effective procedure is correct

I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it. Definitions: (1) The ...
1
vote
2answers
107 views

Statistic: calculating error of order of two sequences of objects

I am trying to derive a meaningful statistic from a survey where I have asked the person taking the survey to put objects in a certain order. The order the person puts the objects is compared to a ...
7
votes
6answers
4k views

Calculate $\pi$ to an accuracy of 5 decimal places?

In this message at point 18 I saw following programming question: Given that $\pi$ can be estimated using the function $4(1 – 1/3 + 1/5 – 1/7 + \ldots)$ with more terms giving greater accuracy, ...
1
vote
2answers
164 views

Random Sequence Generator function

I want to find out a function or algorithm, whichever is suitable, which can provide me a random sequence. Like Input: 3 Output: {1,2,3} or {1,3,2} or {2,1,3} or {2,3,1} or {3,1,3} or {3,2,1} Same ...
1
vote
1answer
92 views

Complexity of recurrence equation

what is the complexity of this equation ? $T(n) = 2*T(\sqrt n) + \log n$ and T(2) = 1.
2
votes
2answers
397 views

For graph $G$, vertices $s,t$ find the shortest path between $s$ and $t$ by weight among all the shortest paths by edges

Given directed graph $G=(V,E)$, two vertices and a weights function $w: E \to R$. In addition we know that there aren't negative cycles in $G$. I need to find a linear algorithm that finds among the ...
1
vote
1answer
167 views

Max flow in a flow network such that $e \in E$ has the maximum flow it can have.

Given a flow network $G=(V,E)$, source $s$ , sink $t$ and capacity function $c:E \to \mathbb{R}^+ \cup \{0\}$ ; as well an edge $e=(u,v) \in E$. I need to find an efficient algorithm which finds among ...
2
votes
2answers
943 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 ...
1
vote
1answer
85 views

What type of graph problem is this?

Lets say I have four group A [ 0, 4, 9] B [ 2, 6, 11] C [ 3, 8, 13] D [ 7, 12 ] Now I need a number from each group(i.e a new group) E [num in A,num in B, num in C, num in D], such that the ...
2
votes
1answer
203 views

Geometry of N-dimensional hypercubes and their N-M surfaces.

I'm working on a computer code to mesh a N-dimensional space with N-dimensional hypercubes and do some physics in it. I am wondering if I can produce a generic code (with C++ templates, but that is ...
7
votes
3answers
625 views

Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
4
votes
1answer
211 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 ...
9
votes
1answer
6k views

Pollard-Strassen Algorithm

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
1
vote
1answer
113 views

Hausdorff-like distance between two arrays

Let $(X,d)$ be a metric space and $a,b\in X^n$ be two arrays of elements of $X$. Define $$ \rho(a,b):=\inf\limits_{\sigma\in \Sigma}\sup\limits_{1\leq i\leq n}d(a_i,b_{\sigma(i)}) $$ where the ...
3
votes
1answer
90 views

matrix “flag” clearing

I have a large matrix that is populated with a list of people, and a 1 or 0 as to whether or not they have a particular flag. A person can have one or more flags, or none at all. For example: $$ ...
2
votes
1answer
113 views

Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval: $\{318, 921, 1526, ...
1
vote
1answer
615 views

Modular Multiplicative Inverse & Modular Exponentiation Equation

I was solving a problem containing that equation. $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given: $1 \le a \le 2,000,000,000$ $0 \le n \le 2,000,000,000$ $2 \le m \le 2,000,000,000$ $a$ and $m$ ...
1
vote
1answer
2k views

What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?

So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
9
votes
6answers
218 views

Is there any way to determine the first $3$ digits of $2^m-2^n$ ($n\leq m\leq 10^{100}$)

It's a problem in my ACM training. Since $n,m$ are really huge, I don't think the algo $2^n=10^{n\log2}$ will work. Also, it's not really wise to calculate the value of $2^n$, I think. So I stack. ...
6
votes
1answer
910 views

Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
3
votes
0answers
173 views

Serret's algorithm and Fermat's theorem on sums of two squares

Serret's algorithm(1848) proved Fermat's theorem on sums of two squares as follows: $p\equiv1\pmod4, u^2+1=kp, 1\leqslant u<\frac{p}2$ $r_0=p, r_1=u$, then Euclidean Algorithm $$r_0=q_1r_1+r_2$$ ...
2
votes
1answer
3k views

Why choose a prime number as the number of slots for hashing function that uses divison method?

The division method is one way to create hash functions. The functions take the form: h(k) = k mod m Where k is a key and m is the number of slots Edit: If this is my hash function why should ...
7
votes
1answer
134 views

Put a mouse to the last cell

We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty. At each step, we can do one of two operations: $\mathbf{P}$: Put only in the first cell $C_1$ 2 mice. $\mathbf{M}$: Move ...
0
votes
2answers
1k views

Master theorem solving

I'm starting to study the master theorem, why does something like $$T(n) = aT(n/b)+f(n)$$ solves to $$f(n)^{\log_ba}$$ ? I'm a bit confused on the resolution
0
votes
2answers
106 views

$l_1$ norm projection with regularization term

I recently encountered an optimization problem and looking for some technical paper for the same.The problem is give as below, $\min f(x)+\lambda*r(x) $ $\ s.t \ x \geq 0, ||x||_1 = 1$. where $x$ ...
0
votes
2answers
735 views

How to find the maxium number of edge-disjoint paths using flow network

Given a graph $G=(V,E)$ and $2$ vertices $s,t \in V$, how can I find the maximum number of edge-disjoint paths from $s$ to $t$ using a flow network? $2$ paths are edge disjoint if they don't have any ...
16
votes
1answer
3k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
0
votes
1answer
2k views

how to prove optimality of this greedy algo

I need some suggestions on how to prove the below greedy algorithm is optimal. Problem: There are $n$ fires on a road. Each fire $i$ is given as an interval where it starts and ends $[s(i), f(i)]$. ...
6
votes
3answers
2k 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$, ...
1
vote
1answer
2k views

Inverse of symmetric matrix M = A*At [duplicate]

Possible Duplicate: 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: ...
1
vote
1answer
313 views

Html Tag counting - Rate of Change formula

I've been trying to a find a statistics-esque formula for calculating the rate of change for html tags which are either added or removed from various websites. So, for example, with the scraper I'm ...
0
votes
1answer
92 views

Create a new image from an image set's patterns

So, I'm interested in learning how to detect patterns in a set of images and then use those patterns to create a new image of similar style. For example, say there is a group of 20~ish images ...
1
vote
1answer
164 views

Deterministic algorithm to fit rhombus to set of points

I'm looking for a deterministic algorithm to obtain the best fitting rhombus out of a set of user-drawn points. It need not necessarily be optimal (simple would be better). Thanks.
0
votes
1answer
50 views

Concatenating different “letters” or domains together, so they don't touch

i will try to be short. i need some "formula" or. a described way, how can i concat domains "together" so they dont touch? in a example i will use letters instead of domains, i have: ...
4
votes
0answers
385 views

Smooth numbers algorithm

I am trying to understand quadratic sieve algorithm and now I am thinking of the way to check if number is smooth over a factor base? For example, say I have number $n = 87463$. First,I find bound $B ...
0
votes
1answer
79 views

Estimates of Gaussian Logarithms

I've been implementing logarithmic number system and I came across these functions called Gaussian logarithms: $f(x) = \log(1 + e^x)$. $g(x) = \log(e^x - 1)$ for $x > 0$. $h(x) = \log(1 - e^x)$ ...
5
votes
2answers
249 views

Why does input size matter in NP theory?

When my prof introduced us to the N/NP topics, the first thing he mentioned is input size, which he defines as the number of bytes needed to describe and write a problem's input into a file. Could ...
5
votes
1answer
134 views

Quantum Information: Deutsch-Jozsa Algorithm

There is a step in the construction of this algorithm which I'm not understanding: $\displaystyle \left[\sum_x \frac{| x \rangle}{\sqrt{2^n}}\right]\left[\frac{ | 0 \rangle -| 1 \rangle ...
2
votes
4answers
882 views

Multiplying exponents, solving for n

When solving for n in this equation I get stuck. Question: What is the smallest value of n such that an algorithm with running time of $\ 100n^2 $ runs faster than an algorithm whose running time is ...
1
vote
0answers
745 views

Legendre and Jacobi symbols

I have a problem with Tonelli-Shanks algorithm with numbers $n = 87463$ and $p = 17$. Solutions are supposed to be $x_1 = 7$, $x_2 = 10$, but I get $11$ and $6$. First with sieving I get a list of ...
1
vote
1answer
414 views

Can Horn's algorithm be generalized for all logic expressions?

The following is an algorithm to find truth assignments for Horn Formulas: Input: A Horn Formula Output: A satisfying assignment, if one exists Set all variables to false While ...