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)

3
votes
1answer
468 views

Fast generation of Pareto-distributed randoms.

I'm developing a library of routines for generating random numbers for simulations (it's on GitHub). I've included fast routines for normally distributed and exponentially distributed randoms, using ...
2
votes
4answers
42 views

Non-Piecewise interpolation over 3 points

I am trying to write an algorithm that interpolates between 3 values. The interpolation will be over the interval [0,1]. What I would like to do is: (Hopefully this makes sense) at x = 0, y = ...
2
votes
2answers
406 views

For recurrence T(n) = T(n − a) + T(a) + n, prove that T(n) = O(n^2 ) complexity

I have been looking over this question for hours now, and can't seem to work it out. It's a question regarding the complexity of sorting algorithms Assume that $a$ is constant and so is $T(n)$ for $n ...
2
votes
2answers
6k views

simple example of recursive least squares (RLS)

I'm vaguely familiar with recursive least squares algorithms; all the information about them I can find is in the general form with vector parameters and measurements. Can someone point me towards a ...
0
votes
1answer
361 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
1
vote
0answers
27 views

Find minimum value of $n$ for an integer $A$ such that $A=n^x$,where $n>1$ and $x\geq 1$

How can I calculate sum of a series of function $f(A)$ for $A = 2,3,4,5,6...A$ $f(A)=n$ (such that $n$ is minimum integer such that $A=n^x$ where $n>1$ and $x≥1$ and both n and x are integer) ...
1
vote
0answers
17 views

Factorial and $\Theta$ notation [duplicate]

If $N$ is a $n$-bit number, how many bits longs is $N!$, approximately in $\Theta( )$ form? I know that $$ \log(N!) = \log(N*(N-1)*...*2*1) \leq \log (N)+\log (N-1)+...+\log(2)+\log(1) $$ $$ ...
12
votes
1answer
66 views
+300

Decomposition of an algebraic number into a sum or product of algebraic numbers with smaller degree

An algebraic number can be identified by its minimal polynomial together with isolating intervals with rational bounds for its real and imaginary parts. The degree of an algebraic number is the degree ...
1
vote
2answers
20 views

Algorithm to cover maximal number of points with one circle of given radius

we have a plane with some points on it. We know coordinate of each point apriori. We also have a circle of unit radius. I need an algorithm that determines optimal/sub-optimal position of a circle ...
5
votes
3answers
274 views

An algorithm for making conditionally convergent series take arbitrary values?

This thread reminded me of an old unsettled question I have. Given an arbitrary conditionally convergent series $\beta=\sum\limits_{k=1}^\infty a_k$ and a target value $\alpha$, is there an algorithm ...
0
votes
1answer
41 views

How to prove complexity of algorithms

I have three different algorithms which I want to prove if they are solvable in polynomial/subexponential/exponential time. The algorithms are $f(k) = e^{\sqrt{\log{k}}}$, $f(k) = k^2 + ...
0
votes
0answers
13 views

SQL joins and analysis

Say we have a users table and an events table and what sort of analysis can be done? Also, what is some SQL statements to describe the analysis of these 2 tables?
2
votes
1answer
758 views

How to see that K-means objective is convex?

I'm trying to proof that the objective of the K-means clustering algorithm is non-convex. The objective is given as $J(U,Z) = \|X-UZ\|_F^2$, with $X \in\mathbb{R}^{m\times n}, U\in ...
1
vote
1answer
17 views

Signed angle difference without conditions

I've got two angles in $0 \leqslant a < 360$ and I need to find the signed difference between them which should be $-180 < \Delta < 180$. Is there a way to calculate the difference with ...
0
votes
0answers
13 views

An efficient algorithm to decide if a directed graph is unilaterally connected

I have been doing practise problems in designing algorithms and came across the following in a past test from an American university (see attached): A directed graph is unilaterally connected if, ...
0
votes
0answers
26 views

Searching an Approximation Formula for Two Parameters

I have an algorithm with two parameters ($p_1$ and $p_2$) and one result ($x$). Interesting (for me) parameters and results are: ...
0
votes
1answer
17 views

Find the asymptotic solution $\Theta$ of the recurrence using the master theorem

I just took a quiz for an algorithms class that I didn't do so well on. It was on the master theorem. Unfortunately the professor refuses to supply answers or even tell me what I got wrong, so I was ...
1
vote
1answer
20 views

Reduction to a max flow problem from a sudoku like puzzle

Given an $n$ by $n$ grid of which some of the squares are black and some are white. I'm allowed to mark some of these squares and the question is to prove whether a given grid with given black squares ...
0
votes
2answers
562 views

Greedy Algorithm, Fewest overlaps

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
1
vote
1answer
15 views

Algorithm for computing the inverse limit of a finite inverse system

Let $k$ be a field (finite if you'd like), let $(I,\le)$ be a finite directed poset with $|I|=n$, and let $(A_i,f_{ij})_{i\le j\in I}$ be an inverse system of finitely generated, graded, commutative ...
1
vote
1answer
15 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

Note: I've also asked this question on StackOverflow here I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if ...
0
votes
0answers
10 views

Square root of Bezier curve via deconvolution

I calculate the product of two Bezier curves via convolution as described in Sanchez-Reyes 2003. I would also like to calculate the square root of a Bezier curve (I have not seen this published ...
0
votes
0answers
66 views

maximum frequencies of numbers in a matrix

I have a matrix A of size n*n.Consider a new matric M : M[i][j]=max of frequencies of numbers occuring in ith row and jth column(A[i][j]) counted once. I have a ...
0
votes
0answers
12 views

Derivation of SVM algorithm (Lagrangian)

I have a question about the derivation of the SVM algorithm (for example, page 3 here ). The question is about the math, so that's why I'm asking this here. Suppose I have the following optimization ...
0
votes
1answer
372 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
2
votes
1answer
56 views

Gaussian elimination algorithm performance

I am developing the quadratic sieve algorithm and I reached a new bottle neck: The matrix processing. I been reading quit a lot about this topic and I found many solutions Gaussian elimination: ...
0
votes
0answers
8 views

partitioning a set into subsets while considering preferences

i am looking for an algorithm to partition a set of P (p=~70) people into minimum G (G=~3) subsets/groups so that no group would have more than M (M=~30) maximum people/elements. Each person ...
0
votes
0answers
40 views

How to square a number that got more digits than search results “digits” on Google.

I am implementing the quadratic sieve algorithm. And I got run in unexpected problem. Take a look at those two final steps of the algorithm as described in wiki. Use linear algebra to find a ...
0
votes
0answers
19 views

Solve the recurrence $T(n) = 2T(n/2) + n/\log n$

Hi am trying to solve the recurrence $T(n) = 2T(n/2) + n/\log n$. It almost matches the master theorem except for the $n/\log n$ part?
0
votes
0answers
9 views

Matching of points in two discrete linear sequences with potentially missing points

This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up. Anyway, ...
1
vote
0answers
16 views

Algorithm for computing an inverse image

Let $k$ be a field (finite if you'd like), and let $f:A\to B$ be a map of graded, commutative $k$-algebras. Suppose further that $A$ is finitely generated and choose a presentation ...
0
votes
1answer
30 views

Prove that $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$

Show that if $n$ is a power of $2$, say $n = 2^k$, then we have the equality $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$. The first step is to prove $O(\lg^2n)$: $$ \lg \frac{2^k}{2^0} + \lg ...
0
votes
2answers
47 views

Evaluating Nested Summations

I'm trying to evaluate the following nested summation as a function of $n$: $$\sum_{i=1}^{n-1} \sum_{j=i+1}^n \sum_{k=1}^j 1$$ So far I have: $$\sum_{i=1}^{n-1}\sum_{j=i+1}^n i+1$$ ...
3
votes
1answer
39 views

solve $54 x + 16 y = 2400$ for integer values of x,y

How to get integer values for x and y that satisfy: $$54 x + 16 y = 2400$$ Someone told me that I can do it using Euclid-Wallis algorithm, but I don't understand it so, if there isn't any else ...
1
vote
2answers
129 views

Understanding Sobol sequences

Can someone explain to me in simple terms, how Sobol sequences work? The wikipedia article is fairly technical. They look pretty interesting. So I shall describe (whatever little I know) in short the ...
0
votes
2answers
18 views

Bubble sort complexity calculation, unsure how it went from one step to another.

I'm looking at my textbooks steps for calculating the complexity of bubble sort...and it jumps a step where I don't know what exactly they did. I see everything up to that point using summation ...
13
votes
0answers
88 views

Is there an efficient algorithm for this vertex cycle cover problem? [migrated]

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
1
vote
1answer
35 views

Sum of two elements is $x$

I read the following problem in the book Introduction to Algorithms by Cormen, Leiserson, Rives, Stein and I couldn't make any progress with it. There is a set of $n$ numbers. Give an algorithm that ...
2
votes
1answer
29 views

Complexity of generating a prime larger than $N$

Is it provably difficult to generate a prime larger than a prescribed $N$? For instance, if I want a prime of $1000$ digits, is there a way to do that deterministically, i.e., without resorting to AKS ...
2
votes
5answers
36 views

Prove a function is in Big-Oh and not in Big-Omega

We are told to use the definitions of Big-Oh and Big-Omega to prove that a given function is in $O(f(n))$ or $\Omega(f(n))$. It requires being able to use $c$ and $n_0$. Use the definitions to show ...
1
vote
1answer
23 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
0
votes
0answers
37 views

Algorithm For Honest vs. Dishonest People

Consider a group of people. When two are taken and asked if the other is honest, they may each either reply that the other is honest, dishonest, or they may report that one is honest and the other is ...
0
votes
1answer
22 views

Solve logistic problem with graph - fitting boxes

Suppose you have $n$ boxes, each of which falls into one of the $k$ sizes, and you want to nest smaller ones into larger ones, such that no two boxes $A$ and $B$ are nested inside the same box, if ...
3
votes
1answer
469 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
1
vote
1answer
462 views

Binary Tree and Overhead fraction Caluculation

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes: 2) Only leaf nodes store data; internal nodes store two child ...
1
vote
1answer
43 views

Project allocation optimization with tricky constraint

I have an allocation problem that should be straightforward, except that it has very specific constraints. I want to assign approximately 300 students to 170 projects in pairs - so that each project ...
0
votes
1answer
66 views

Getting $B$ from $A = M^t B M$ without inverting $M$

I have got three matrices: $A$ (dimension $n \times n$), $B$ (dimension $m \times m$) and $M$ (dimension $m \times n$). We have $m > n$. This is the relation between these three matrices: $A = M^t ...
0
votes
2answers
32 views

Newton's method for optimization

I have been reading about Newton's method and know that you can use it for optimization problems. However, does Newton's method only guarantee convergence to a local minimum or maximum, or can it be ...
0
votes
0answers
14 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
0
votes
1answer
43 views

Prove this greedy algorithm is optimal

So the question is: Consider the following different greedy algorithm for the Interval Scheduling algorithm: DifferentGreedySchedule - Initialize R to contain all intervals - While R is not empty - ...