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
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
22 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
38 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
17 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
27 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
22 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
63 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
1answer
70 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.
5
votes
1answer
263 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
41 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
46 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
22 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
28 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
57 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
54 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
55 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
27 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
96 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
26 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
46 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 ...
2
votes
0answers
21 views

Assignment problem, minization of the Standard Deviation

I have an assignment problem. So typically I need to find the optimal combination between two sets of parameters P, M. I know that the Hungarian Algorithm is often privileged for this kind of problem ...
0
votes
0answers
19 views

How to figure out whether PCA can be performed on a data set or not?

I do have idea on the way PCA works but I do not know how to figure out whether a high dimensional data set is suited for PCA compression. I googled for some algorithms but could find any. Are there ...
1
vote
0answers
15 views

Is there any general algorithm to solve such a 3D cutting problem?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width ...
3
votes
1answer
40 views

A result of Erdos: the multiplicative persistence of $n$ is at most $c\ln(\ln n)$

Multiply all the digits of a number $n$ by each other, repeating with the product until a single digit is obtained. The number of steps required is known as the multiplicative persistence of $n$. ...
0
votes
0answers
11 views

Spin-off of Scheduling Weighted Interval Problem

I'm trying to solve a problem in which, given a + sign shaped area of land (with no width) and a list of contiguous sections of the land (segments, T-shapes, smaller + shapes, etc), each with an ...
1
vote
1answer
35 views

How is de = 1 (mod ϕ(n)) calculated

I am reading RSA algorithm. So, I was writing a question but I saw this question and still couldn't understand it. If $$e\cdot d \equiv 1 \pmod{\varphi(n)},$$ then $$ed=k\cdot \varphi(n)+1, \qquad ...
3
votes
1answer
29 views

Proving a recursive algorithm on a set is true

If I have an algorithm that returns the entry of a set with the largest value, how do I prove the algorithm is true mathematically? (I know I could just write tests for it.) I understand how to use ...
1
vote
1answer
24 views

How to compare times?

i'm looking for an algorithm to compare 2 different time records. My time format is hour:minute:second:nanosec I tried something like this, but its not working well: if (hour <= anotherHour) { ...
0
votes
2answers
39 views

Find Algorithm, given a list of arcs, that maximizes number that fit on a circle

I'm trying to find an optimal algorithm that, given a list of arcs $(x_i, y_i)$, where $x_i$ and $y_i$ are the starting and ending angle measurements of the arc in radians, maximizes the number of ...
0
votes
1answer
27 views

Elaboration needed on a section of a published paper about dictionary learning

I will be doing my master thesis on dictionary learning, and I am trying to understand basic concepts of the subject reading the following paper: K-SVD: An Algorithm for Designing Overcomplete ...
3
votes
0answers
41 views

Implementing the Risch algorithm to integrate $\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}$

Following the work of Andreas Wurfl i am trying to implement the Risch algorithm on $\int{\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}dx}$ following his method for extensions that are purely logarithmic, we ...
0
votes
1answer
36 views

Fast Fourier Transform Splitting Algorithm

I'm trying to figure out how the FFT splitting algorithm works. I've pretty much understood the general idea, but when I try to compute it, I get something completely different than what I expect $ ...
1
vote
1answer
21 views

What would the expected number of swaps in a merge sort be?

If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would ...
0
votes
1answer
20 views

Logarithmic algorithm performance

If I have an algorithm that on $T$ iterations gets me within $O(\log(T)/T)$ accuracy, what is a (preferably concise, closed form) lower bound on $T$ that gets me within $\epsilon$ accuracy? In other ...
1
vote
1answer
36 views

How many comparisons does it take to find a number in a grid of numbers arranged in an $N \times N$ square

We have an $N \times N$ squares, filled with integer numbers monotonically increasing in "right" and "down" directions. So from any point, if you move left the number will get bigger, or if you go ...
1
vote
1answer
50 views

Dijkstra's Algorithm for Negative Weights.

Now the problem states that their is a graph $ G = (V,E) $ where some of the edges have negative weights while some of the edges have positive edges. Now the question is why won't Dijkstra's algorithm ...
-1
votes
1answer
25 views

Give a procedure using assignment statement to interchange the values of the variables $x$ and $y$. [closed]

Give a procedure using assignment statement to interchange the values of the variables $x$ and $y$. What is the minimum number of assignment statement needed to do this? I have this assignment in ...
2
votes
1answer
24 views

Multiplying two matrices using Strassen vs squaring identical matrices

I have an assignment question such as follows: when using the Strassen algorithm we have 7 subproblems usually, and I suppose this applies to any two $n*n$ matrices and the run time is ...
0
votes
0answers
13 views

Find all groups that meets the condition

I have $n$ elements, each of them have two unsigned int attributes $x$ and $y$. Now I'd like to find out all the groups that fit the following condition: $A.x \geq B.y$ and $B.x \geq A.y$. The ...
0
votes
1answer
14 views

Asymptotic convergence of the total length of a graph

I encoded the following algorithm: suppose we're in (0,1)x(0,1) and I randomly create a "village" one at a time. At each step, I link a newly randomly created village to the closest village already ...
4
votes
1answer
37 views

Algorithm for traversing a conditional maze

Imagine a maze where there are rooms and doors. You can only go one way through a door. Some doors are locked. Certain rooms contain keys to certain doors. In effect, each time you find a key, the ...
0
votes
0answers
12 views

Asymptotic complexities of a conditional function

Let the function $f(n)$ be defined by $$f(n) = \dfrac{n^2}{7}$$, for n even and $$f(n) = 452n$$, for n odd I'm being asked to determine which statements are true and to show validation for those ...
1
vote
1answer
18 views

Counting Operations in the context of an Urn Problem

I was tasked with the following question, regarding the counting of operations in the pseudo code provided that has nested for loops: Let U ={B1,B2,...,Bn} with n >= 3. Interpret the following ...
0
votes
1answer
19 views

Find a shortest way between nodes in graph

I have a next structure : Each node in graph may have more than 2 links. I want to find a shortest way with node 1 and 13. ...
2
votes
1answer
34 views

How to determine number of roots of $a^k + b^k \equiv c^k \pmod{d}$?

Is there a way to determine number of roots of $a^k + b^k \equiv c^k \pmod d$? It is an algorithmic task, not theoretic math. I am not looking for a closed formula.
0
votes
0answers
19 views

adaboost weighting scheme’s equality

As you all know, ada-boost weighting is as follows, $$ \begin{cases} e^{-\alpha} & \quad \text{for right classified}\\ e^\alpha & \quad \text{for miss-classified} \end{cases} $$ ...
0
votes
1answer
20 views

single value computation

I was solving a coding problem where given a bunch of numbers, i need to compute step difference till i'm left with only one number. For example numbers are 3, 5, 2, 6, 7 such that my result is ...
0
votes
0answers
15 views

Decomposing an undirected graph into trails

Any undirected graph, $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, has an even number of odd-degree vertices. If $\mathcal{G}$ has $2k$ odd-degree vertices, where $k > 1$, then $\mathcal{G}$ can be ...
5
votes
2answers
117 views

Algorithm design for enumerating pairs of noncommuting elements up to conjugacy

I am trying to write some Magma code that, given a group $G$, returns a list of pairs $(x,y)$ with $x,y\in G$ such that $[x,y]\neq 1$ and such that every pair $(z,w)$ in the group with $[z,w]\neq 1$ ...