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
1answer
15 views

Expected number of jumps to just exceed $(1-\rho)$ quantile in the line segment $[0, 1]$

Suppose $X$ is random variable from some unknown distribution $f(X)$. I'm given a black-box/algorithm that takes a number $c\;: 0 \leq c < 1$ and outputs a number(randomly generated) using the ...
0
votes
0answers
17 views

EM algorithm for objective HMM M-step

How did step 2 in the derivation below arrive at step 3?
0
votes
1answer
17 views

Jensen's inequality in derivation of EM algorithm

I am going through the derivation of EM algorithm and got stuck on understanding the following steps: Notes showing EM algortithm derivation For the equality to hold, f(x) has to be an affine ...
1
vote
1answer
28 views

Find minimum number of coins with Largest value coins?

There is a greedy algorithm for coin change problem : using most valuable coin as possible. How We can find a quick method to see which of following sets of coin values this algoithms cannot find ...
-2
votes
0answers
13 views

Give the simplest possible Theta ($\Theta(· · ·)$) form for each of the following functions (e.g., $2n + 3$ would be written as $\Theta(n)$?) [on hold]

1) $2n^2 + 5n + 3$ simplified to $(2n+3)(n+1)$ $\Theta(n)(n+1)$. What would $(n+1)$ be? 2) $5n + 3 \log n + 7$ 3) $2n + 3n \log n + 3$
2
votes
0answers
21 views

shrinking a convex hull around a set of polygons

I'm trying to find (Or design) an algorithm that will let me, after I have a convex hull, progressively shrink the hull towards the polygon set via increasing some parameter. I.e., if we use the ...
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) $$ $$ ...
1
vote
0answers
28 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
2answers
21 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 ...
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?
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
15 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
1answer
44 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
27 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
22 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
0answers
11 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
67 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 ...
12
votes
2answers
103 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 ...
2
votes
4answers
46 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 = ...
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
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, ...
2
votes
1answer
57 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: ...
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
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
32 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 ...
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 ...
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 ...
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
37 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 ...
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
0answers
16 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
1answer
23 views

Proof of Mutually Inclusive Tree Properties

I don't know if that's the most accurate title. I'm trying to prove that one property of trees implies another without using any of the other properties. This is for homework. But I'm really just ...
0
votes
0answers
23 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
1
vote
1answer
24 views

How to show the running time of the following algorithm? [closed]

The outer loop runs n times. The inner loop runs Math.floor(n/i) times. So it would be O(n*Math.floor(n/i)). I do not know how to transform that into a proper expression involving Big Oh and n. Maybe ...
0
votes
1answer
34 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
0answers
14 views

Hamioltonian Circuit of Planar Graph of Order $2^n$

$G$ is a planar graph of order(= number of vertices) $2^n$. Questions: When $G$ has a Hamiltonian Circuit? Is there a polynomial or quasi polynomial time algorithm to decide whether $G$ has a ...
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 ...
2
votes
2answers
30 views

Find $ k$ last digits of quotient

Suppose we have two integer numbers $a, b$ such that $b$ divides $a.$ Suppose that the number $a$ is very and very long and we cant to perform a division algorith. How to find last $k$ digits of ...
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 - ...
1
vote
0answers
17 views

Number of global min cuts in undirected graph

I'm looking at a proof of the following theorem "The number of global minimum cut is $\le \binom{n}{2}$". It says $\forall i$ from $1$ to $n-1$ Find min-cut seperating $\{1,2,\cdots,i\}$ from $i+1$. ...
0
votes
1answer
28 views

Geometric Meaning behind the algorithm (slope of the line + ray casting)

I'm trying to dissect the classic algorithm for finding if a point is inside a (simple) polygon. Please see: http://erich.realtimerendering.com/ptinpoly/ and ...
0
votes
1answer
41 views

algorithm to convert integer to 3 variables (rgb)

I try to store integer (real numbers) values into pixel data. The only way my api can store pixel data are RGB Colors. The idea behind it is, to store a large amount of vertices into the vram, rather ...