Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

0
votes
0answers
21 views

Modifying U=mxn SVD Algorithm to U=mxm Algorithm

I have painstakingly ported this Python source "svd.py" to C++. I confirm it works for the example it comes with. While testing another example (this one, from Wikipedia), the assert statement trips ...
2
votes
1answer
26 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
2
votes
0answers
33 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
8
votes
1answer
85 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
2
votes
0answers
50 views

Minimise total cost and count ways [closed]

A country has a + b cities located in a row, which are uniformly placed. There are two large telecommunication operators in this country. The first operator will ...
0
votes
1answer
15 views

algorithm to see if some sign(s) of terms will sum to zero

I was trying to develop an algorithm so see if a given set of terms $a,b,c,d$ can sum to zero given any possible combination of signs $+/-$ on those terms. How does one compute how many distinct ...
0
votes
0answers
23 views

Algorithm of matching points between two point sets

I have two point sets $A=\{a_1,a_2,...,a_m\}$ and $B=\{b_1,b_2,...,b_n\}$ $(m\ge n)$, and want to find a injection map $\phi$ from $B$ to $A$ such that it minimizes $\sum{||b_i-\phi(b_i)||}$. There ...
4
votes
3answers
93 views

2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
0
votes
0answers
11 views

Perlin noise seems to be distributed like on a bell curve

I coded a perlin noise function, (gradient noise, not value noise). Weirdly, (or maybe it's normal?) my values seem to be distributed pretty much like on a bell curve. I guess I should fix my ...
1
vote
1answer
23 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
0
votes
0answers
7 views

Estimate time it takes the minimum mean cycle cancelling algorithm to converge

This particular algorithm solves the circulation problem, equivalent to the minimum-capacitated flow. My question rather than only from this particular algorithm, but for combinatorial solutions in ...
0
votes
1answer
22 views

Maximal-size set of disjoint edges

Inspired by a "real-world" puzzle (actually, an unimportant aspect of a free-to-play game someone I know is playing)... Given an arbitrary (finite) undirected graph, I want to compute a ...
0
votes
2answers
25 views

Fastest way to find the top points in a rectangle

Given a rectangle X1,Y1 and X2,Y2 such that X1,Y1----------------- | | | | ----------------------X2, Y2 And given a ...
3
votes
2answers
39 views

Smallest value taken by a quadratic polynomial in two variables.

Let $p$ be a degree $2$ polynomial with integer coefficients, say $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ I would like to find an algorithm which solves the following: Problem 1: Given ...
1
vote
1answer
35 views

How to generate a point cloud with known symmetry?

So I would like to know if there are any published algorithms to generate point clouds with known symmetry groups, such as $D_{3h}$ or $O_h$ and stuff like that. I know lots and lots of point clouds ...
3
votes
1answer
87 views

Base of logarithm decrease when variable count increase

I run a large online platform where users submit articles and earn points. I am working on an algorithm where the more comments they submit, the higher score they will receive. In its simplest ...
1
vote
1answer
30 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
0
votes
0answers
8 views

what is a non parametric iterative algorithm?

I am trying to uderstand mean shift algorithm.Mean Shift is a non parametric iterative algorith.What does it mean?
1
vote
1answer
27 views

Algorithm to multiply nimbers

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$? The following rule seems like it could be helpful: $$ 2^{2^m} * 2^{2^n} = \begin{cases} ...
1
vote
3answers
45 views

Big-O, Omega, Theta and Orders of common functions

Based on this table, is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? And a function of order ...
1
vote
1answer
35 views

For an alphabet of size $N$, how many strings have all of its substrings of length $\geq 2$ unique?

For an alphabet of $N$ characters, how many strings can be formed (including the empty string) so that no substring of length $\geq 2$ appears more than once in the string? The maximum length of such ...
3
votes
3answers
65 views

How to generate $\log$ function that intersects at $(0,1)$ and $(1,0)$?

I apologize for any incorrect or missing formatting, first time posting in the math stack exchange. It's been a few years since I've done any kind of calculus, so I remember nothing at all, which is ...
0
votes
0answers
35 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
0
votes
0answers
17 views

How to perform parallel cholesky factorisation

I am a student trying to understand and implement a parallel cholesky factorisation algorithm for sparse matrices in software. Can anyone give an example of a parallel cholesky factorisation ...
0
votes
1answer
81 views

Find if permutation is possible

Given a permutation of natural integers from 1 to N, inclusive. Initially, the permutation is 1, 2, 3, ..., N. We are also given M pairs of integers, where the i-th is (Li,Ri). In a single turn we ...
2
votes
0answers
16 views

Plot implicit equation in sub-quadratic time complexity

It is fairly straightforward to plot an explicit equation such as $y=x^3+3x^2+2x+5$ in linear time, because you can just iterate through all $x$ in your graphing space and use the equation to ...
2
votes
1answer
31 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
8
votes
2answers
178 views

Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal

Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same. I tried a bunch of equations but ...
1
vote
1answer
33 views

can dijkstra's algorithm be applied as it is for undirected graph

I am wondering why can't Dijkstra's algorithm be applied as it is for undirected graphs. I mean instead of adding 2 directed edges to make it equivalent to a directed graph , why wouldn't it work if ...
0
votes
1answer
79 views

Subtraction game between alice and bob

Alice and Bob decide to play a number game. Both play alternately, Alice playing the first move. In each of their moves, they can subtract a maximum of k and a minimun of 1 from n ( ie.each of them ...
0
votes
1answer
29 views

Algorithms to increase or decrease the contrast of an image

While tinkering with image editing, I thought I might implement a contrast algorithm; something that would take a range of values and, based on the value that the user provides (from 0 to 255; the ...
0
votes
0answers
31 views

What would be the way to learn algorithms?

I want to know the mathematical theory associated algorithms. Story with a base of calculation, analytical geometry and linear algebra. What would be the previous topics to begin the study of ...
1
vote
2answers
53 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
2
votes
1answer
49 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
1
vote
0answers
18 views

Math Algorithm Help Needed with Aggregated Percentages (Business Metaphor)

I'm trying to figure out a math algorithm, but I'm having a hard time wrapping my head around the best way. Instead of defining a complex industry-specific process, I'll use a crazy metaphor here ...
-2
votes
0answers
10 views

Exchanging numerical data to percentages

I have a large amount of data that are all positive numbers that i am plotting, however, as apposed to using numbers, which lack relative significance, I was looking to find an algorithm that would ...
0
votes
1answer
19 views

Approximate non-Lipschitz (but continuous) functions by Lipschitz functions

Is there any algorithm to approximate non-Lipschitz (but continuous) functions by Lipschitz functions ?
6
votes
1answer
124 views

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
1
vote
0answers
91 views

Find maximum height of smallest flower

Little beaver planted n flowers in a row on his windowsill and started waiting for them to grow. However, after some time the beaver noticed that the flowers stopped growing.So he decided to come up ...
1
vote
1answer
113 views

How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
0
votes
0answers
35 views

finding quadilaterals from given sides

I have a set of Points. I triangulated the Points as delaunay triangles but i only have edges for the triangles means edge array of the whole set of Points. Now i need to find the traingles and ...
0
votes
1answer
26 views

How to check if a 2D mesh is connected

I'm trying to optimize structures by using FEM and genetic algorithms (GA), the FEM solver is a commercial one, and I'm programming the GA. Something like this. My first approach is simple, just ...
0
votes
1answer
29 views

Fast Fourier Transformation: inverse transform of the product of polynomials

I have managed to implement and understand most of the Fast Fourier Transformation. However, I have one last question. If one has two polynomials, say $A(x)$ and $B(x)$, and one computes DFT of ...
0
votes
0answers
15 views

KMP Algorithm-Longest prefix which is also a proper suffix

Im trying to learn KMP Algorithm, im watching this video on KMP algorithm http://youtu.be/SVKe7bvQ4Xk?t=5m4s There is a statement in the video for determining π[K].It says length of longest prefix of ...
0
votes
1answer
44 views

Algorithm for finding contradictions in a directed graph that represents implications

I need an algorithm that does this: For a directed graph where nodes represent boolean values and edges represent implication (implies TRUE and implies FALSE): If (arc exists between any ...
0
votes
1answer
69 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
1
vote
2answers
51 views

Find if a number lies in this pattern

I have a sequence of numbers below... $1, 2, 4, 7, 11, 16 ...$ You get this list by starting at $1$ then add $1, 2, 3, 4, 5 ...$ Given a number $n$, how can I determine if it will show up in this ...
1
vote
1answer
49 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
0
votes
0answers
21 views

Multi-armed bandit optimization

I've got a variation of multi-armed bandit problem, where I need not to minimize the regret, but to find a bandit with a maximum reward. Could you please tell how this problem is called or suggest ...
1
vote
0answers
25 views

Computing rotating pairs

I'm trying to develop an algorithm that my software development team can use to pair off for daily stand-up calls. Each dev should be paired with every other dev before there is a repeat. In other ...