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
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
9 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
6 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
25 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
29 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
17 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
27 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
24 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
18 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
51 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
17 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
57 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
40 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
18 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
votes
1answer
26 views

Prove that the given algorithm is correct for various cases. [on hold]

The following algorithm determines whether a word is a palindrome; that is, if the word is the same read left to right as right to left. Palindrome($s = s_1s_2s_3 \ldots s_n$) (a string of length ...
1
vote
0answers
36 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
43 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
16 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
18 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
28 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
38 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
52 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
84 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 [on hold]

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
22 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 ...
0
votes
0answers
23 views
0
votes
0answers
43 views

How does Facebook determine if people are close friends? [closed]

I've thought about something, how does Facebook determine whether people are close friends or not. I guess they're using algorithm but what and how? What do they do?
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 ...
2
votes
0answers
17 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
18 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
36 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
7 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
24 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
25 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
23 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
33 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
25 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 ...
0
votes
0answers
17 views

Algorithm to find value where complex numbers meet on the unit circle. [closed]

I'm trying to find the value at which 4 points are meeting on the unit circle. These points are eigenvalues of the translation operator $T$. By varying $\lambda$ the eigenvalues change. Background: ...
3
votes
0answers
38 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
33 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
votes
0answers
31 views

Explain why a multiplying algorithm cant take less than O(n^2) time? [closed]

Explain how best case analysis is fundamentally different in kind from worst case and average case analyses. Use a best case argument to explain why no algorithm for multiplying pairs of nxn matrices ...
1
vote
1answer
18 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
18 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
33 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
36 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 ...
0
votes
1answer
22 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 ...