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)

0
votes
0answers
22 views

Minimum number of operations to make all of the strings (objects) the same

Let $A$ be an alphabet, $K$ and $N$ be natural numbers and $X$ be a list of $N$ strings over $A$, each one consisting of $K$ letters. You have one operation ($@f$): convert a string from $X$ to ...
2
votes
1answer
19 views

Algorithm to solve traffic jam

Is there an algorithm for solving a traffic jam? Given a traffic jam situation, this algorithm should tell which moves each car should make, and in which order the cars should move, so that the ...
0
votes
0answers
19 views

How to approximate a trigonometric to make less computation complexity

I having a trigonometric function such as $$ p_2(s) = \begin{cases} \frac {1}{(2 \pi)^2}(1-\cos (2 \pi s)), & \text{if $s \le1$ } \\ \frac {1}{2 }(s-1)^2, & \text{if $s >1$ } ...
0
votes
0answers
6 views

Origin of divergence in a divergent field (2D) [on hold]

I have a field of measured vectors, they generally (besides the noise) point outward from some "central point". Looking for a way to calculate/approximate the position of this "central point". Thanks ...
0
votes
3answers
33 views

Efficient algorithm for taking powers of binary numbers?

Is there any efficient algorithm for taking powers of binary numbers? Or even just squaring one? Thanks ahead of time.
-4
votes
0answers
32 views

does anyone know how to generate those red shape in pictures? [on hold]

I'm trying to make red shape through some kind of algorithm,suppose we know the font consist of Bézier points and lines.any good ideas?
0
votes
1answer
20 views

Problem implementing a QR factorization

I'm trying to write a Fortran subroutine to compute a QR factorization using the Householder method. To test my routine, I compute the factorization of the following matrix: $$ A = \begin{pmatrix} ...
0
votes
2answers
33 views

Writing a GCD of three numbers as a linear combination

i know how to find the $\gcd(5,11,2^{2015}-1)$. but i can't seem to find the linear combination. do you find it the same way we find the linear combination of two integers.
1
vote
1answer
21 views

How to set up this algorithm?

I'm doing a simple budget app, to make some calculations to improve private economy. I've made an option where you can enter the value of the money that are in the bank right now, and how many days ...
-1
votes
0answers
7 views

Get a given string by concatenation of the minimal number of given words [on hold]

Suppose you have an input string, say $s$, and a set of words $W$. The task is to find the minimal $N$ such that: $s = w_1 \cup w_2 \cup ... w_N$, where $w_i \in W$. Could you please name a handy ...
0
votes
0answers
20 views

How to use mobius-inversion to solve this problem?

Currently, I'm trying to solve this problem using mobius-inversion. the function f(d) means the number of (i, j, k) equals d, and function g(d) means the numbers that satisfying: d | (i, j, k). Then ...
0
votes
0answers
24 views

Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete

So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that ...
0
votes
0answers
15 views

Implementing specific SVD algorithms

My goal is to learn to implement the two-sided Jacobi SVD, a method of SVD for bidiagonal matrices, and a method of SVD for tridiagonal matrices. Can anyone recommend a place to learn about these, or ...
1
vote
1answer
23 views

How to efficiently list prime with a very specific property

I noticed that my phone number 06 xx xx xx xx is a prime number. Ok that cool ... But if you had the country code (+33 for france), ...
1
vote
0answers
5 views

Is the mapping achieved by the discrete Frechet Distance the best achievable pair decomposition?

I have the following proble: There are 2 sequences $P$ and $Q$ composed by $M$ and $N$ points respectively. I want to calculate the discrete Frechet distance between them. This operation outputs also ...
0
votes
0answers
14 views

A suitable algorithm to change strings to zero strings

I found a programming exercise I couldn't solve. Namely, I have been given a long binary string and a fixed set of operations. Here, an operation means that it takes a substring and transforms its ...
0
votes
0answers
33 views

How many counts the square number?

For example I have a number is $55$. Can I check this for how many counts number's square create this number. For example I have $55$ So, I know this number total from 5 number, which are $$55 = ...
0
votes
1answer
17 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
0
votes
0answers
18 views

Help understanding Jacobi SVD

I found this link, and I want to complete this implementation of the Jacobi SVD method, but it isn't clear to me how to implement alpha, beta, and gamma. I think it's very clear that ...
0
votes
0answers
9 views

Code that Creates a Monotonic Array

I'm not sure whether this belongs on StackOverflow or here. Suppose I have an infinite (indexed from $-\infty$ to $\infty$) array of random doubles x[]. They are ...
0
votes
0answers
45 views

Squaring a matrix using a linear memory

I have a N x N matrix (let's denote it with A). I want to calculate $A ^ 2$, using $\theta(N)$ memory (speed does not matter as long as it's a polynomial) on one processor. I believe that this can ...
0
votes
1answer
32 views

What algorithm can sort the first sqrt(n) elements of an array in O(n) time?

I want to partially sort an array of $n$ elements to get the first $\sqrt{n}$ elements sorted, and it has to be done in $O(n)$ time. The complexity $O(n)$ seems to imply that it is necessary to go ...
0
votes
1answer
19 views

Finding algorithm to design combinatorics formulae per input data

Problem: calculate how many unique "words" can be made using the letters of your a) name (Kateryna - 8 letters, letter 'a' used twice) b) lastname (Atamanchuk - 10 letters, letter 'a' used 3 times) ...
0
votes
0answers
15 views

Computing efficiently a small base to the power a large number

Is there a fast algorithm to compute an exponential with a small base, (namely , close to 1) For example, computing 1.01 to the power 100?
0
votes
0answers
12 views

Depths of top-level multiplication algorithms

I've seen that the depth of the Cantor/Kaltofen algorithm is in $O(\log n)$. Are the operations for this complexity undifferentiated ? Or this complexity is in terms of multiplications only ?
0
votes
0answers
7 views

BFS Modification For Total Shortest Paths

I was given the following problem as an assignment but it is really confusing me: Consider the BFS algorithm. Given a digraph G = (V, E) and a starting vertex s ∈ V, this algorithm computes for ...
2
votes
1answer
30 views

The output spanning tree of Kruskal's algorithm is a minimum spanning tree

I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction. We suppose that $S$ is not a minimum spanning tree. ...
0
votes
1answer
30 views

Have you seen these integer factorization algorithms before?

I have two algorithms for finding two factors, $p$ & $q$, of a number $N$. The algorithms are (hopefully) obviously related. The pseudo-code for them follows: Algorithm 1 ...
1
vote
1answer
21 views

Summation to Closed Form conversion

I am struggling to understand basics as it related to forming a closed form expression from a summation. I understand the goal at hand, but do not understand the process for which to follow in order ...
0
votes
0answers
34 views

proof that some expected value equal to $\theta (\log n - \log k)$

So here is the problem - Given the following equation: $(c_2\cdot \log n) - (c_1\cdot \log k)\le E(X)\le 1+ (c_1\cdot \log n) - (c_2\cdot \log k)$ When $c_2,c_1\gt0$ and also $c_1\gt c_2$ In ...
0
votes
0answers
16 views

how to create sets which has one common value for intersection

There is a algorithm called Maekawa, to send message to a particular request set (http://courses.cs.vt.edu/cs5204/fall99/Supplemental/ProblemSet8.html) I am interested in the ALgorithm to generate ...
4
votes
0answers
26 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
0
votes
0answers
19 views

expectation approximation

Note: You don't have to understand Approximation Algorithms to answer this Hello. I need to prove an algorithm approximation by using expectation. The algorithm takes $x_i \in {0,1,2}$ such that ...
2
votes
1answer
53 views

The output of Kruskal's algorithm is a spanning tree

I want to show that the output of Kruskal's algorithm is a spanning tree. Let $G$ be a connected, weighted graph and let $S$ be the subgraph of $G$ which is the output of the algorithm. $S$ cannot ...
1
vote
0answers
18 views

Coloring chordal graphs

It is well known that the graph coloring problem --- given a graph $G$ and a number $k\in\mathbb{N}$ decide whether $\chi(X)\le k$ --- is NP-complete. However, certain classes of graphs can be colored ...
1
vote
1answer
62 views

Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed? Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.
1
vote
0answers
66 views

Algorithm for tetration to work with floating point numbers

So far, I've figured out an algorithm for tetration that works. However, although the variable a can be floating or integer, unfortunately, the variable ...
1
vote
0answers
19 views

simple algorithm to go thru all lexicographic permutaions

I'm working thru the euler question 24 (not looking for the answer) and came across this site describing an algorithm to get all the permutaions. Here are the steps they lay out : Steps to ...
1
vote
0answers
37 views

Is there an optimal algorithm to calculate $2^n - 1$ in $\theta(n^n)$

The sequence $(f_{n})_{n \in \mathbb{N}}$ is defined by $f_{0} := 0, f_{1} := 1$ and $f_{n} := 3f_{n-1}-2f_{n-2}$ for $n \in \mathbb{N}_{0} \setminus \{0,1\}$. Is there an algorithm that takes an $n ...
2
votes
4answers
45 views

Two non-negative functions f,g such that $f \not\in O(g)$ and $ g \not\in O(f)$

Show that there exist two non-negative functions $f,g: \mathbb{N} \rightarrow \mathbb{R}$ such that $f \not\in O(g)$ and $ g \not\in O(f)$. It would be easy two find two such functions for which one ...
0
votes
0answers
17 views

Solving Nonconvex Programming using Genetic Algorithm

Consider such a programming problem, \begin{equation} min \| \Psi(\boldsymbol{x}) \|_p \quad s.t. \quad \boldsymbol{Ax} = \boldsymbol{b} \end{equation} Where $\boldsymbol{x} \in \mathcal{R}^{n}$, ...
0
votes
1answer
20 views

Hamilton-like paths in digraph

We are given digraph with two (possibly the same) vertices - let's call them S and F. We are also given some set of vertices W (possibly empty, possibly consisting of all vertices of digraph). We ...
2
votes
1answer
34 views

Given the graph below, use Dijkstra’s algorithm to find the shortest path (More details included)

So I've found out a few things and was wondering if someone could verify if I'm doing this correctly. So here is an example I've been given: Here is the solution to that example: Now here is the ...
0
votes
1answer
46 views

Need help to understand the solution for NP-completness proof (3CNF <= 0-1 integer-programming problem)

I was trying to solve problem from Cormen page 1100 34.5-2 Given an integer $m * n$ matrix A and an integer $m$-vector $b$, the 0-1 integer- programming problem asks whether there exists an integer ...
1
vote
2answers
53 views

Intersection of integer sets

This is probably a trivial question for mathematicians but I am not seeing how to approach the following problem: Imagine two sets defined by: ...
-3
votes
2answers
26 views

How do I write this equation as an algorithm? [closed]

how do I write "from 3 to 6" or > 2 but < 7 in an algorithm?
5
votes
1answer
92 views

Two pawns walking in a complete graph

We have a complete graph $G = \langle V,E\rangle$ with non-negative values on edges. Let $C = \{v_1,v_2,\ldots,v_n\}$ be an ordered collection of $G$'s vertices. At the beginning we have two pawns in ...
0
votes
0answers
36 views

Calculate distance between known intersecting points [closed]

I have been working on this problem for awhile now and I think I just need a few fresh minds to help me out. I have 4 lines that intersect and form a shape. This is part of a much larger problem, ...
0
votes
0answers
25 views

Baby-step Giant-Step algorithm to calculate value in new base

Using the Baby step–giant step algorithm I am trying to determine $log_{2}(7)$ in base $1$3. Let $p = 7$. Set $n$ to the least integer greater than $\sqrt p$: $n = 3$. So for baby step, I started off ...
3
votes
1answer
42 views

Help understanding the complexity of my algorithm (summation)

As an exercise, I wrote an algorithm for summing the all elements in an array that are less than i. Given input array A, it produces output array B, whereby B[i] = sum of all elements in A that are ...