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)

4
votes
1answer
38 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
29 views

Calculate distance between known intersecting points

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
18 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
19 views
0
votes
0answers
38 views

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

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
0answers
35 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 ...
1
vote
0answers
12 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
14 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
32 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
6 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
21 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
24 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
21 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
30 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. [on hold]

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: ...
2
votes
0answers
26 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
0answers
13 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
27 views

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

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
15 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
17 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
32 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
25 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
20 views

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

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
19 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
11 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
12 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
34 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
2answers
33 views

What formula can I use to identify numbers in the pattern 2 7 10 15 18 23 [closed]

I have an algorithm that loops from 1 to n and need to pick out those numbers. E.g. to find multiples of 3: for n in [0..100] if n % 3 == 0 //do something
0
votes
0answers
10 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
16 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
13 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
16 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
0answers
24 views

Solving cycle in undirected graph in log space?

Setting Let: $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ My Solution we show $UCYLE \in L$ by constructing $\mathcal M$ that decides ...
-2
votes
0answers
43 views

Strongly connected components problem help with using lexicographic order to create a graph

The edges of directed graph $G$ on node set $\{0, 1\} ^ 3$ are as follows: There is an edge from $a_1a_2a_3$ to $b_1b_2b_3$ if and only if $b_3 \in \{a_1,a_2\}$; $b_1 \in \{a_2,a_3\}$; $b_2 = ...
-5
votes
0answers
31 views

Approximation algorithm for mine packing problem [closed]

Problem: In the Mine Packing Problem, we are given an undirected graph G = (V, E), and wish to find a set of vertex-disjoint trees of depths 1 (all leaves connected directly to the root). The goal is ...
0
votes
1answer
19 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
14 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
104 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$ ...
0
votes
1answer
28 views

Finding a function f(n) such that T(n) = O(f(n))

I need some help understanding how to prove that n log n in the equation below is the dominating term. i.e. Given the equation below, find function f(n) such that T(n) = $\theta$(f(n)): $T(n) = ...
1
vote
2answers
43 views

Help me understand this algorithm problem.

First, I'm not looking for an answer here, I'm just looking to understand the problem so that I can prove it. I'm trying to analyzing the worst case running time of an algorithm, and it must has ...
2
votes
1answer
130 views

Show that if $P = NP$, then deciding whether a boolean formula is minimal is in $P$.

Recall a boolean formula $\phi$ over $n$ variables is minimal if there does not exist a shorter formula $\phi'$ over the same set of variables so that $\phi(\bar a) = \phi'(\bar a)$ for every $\bar a ...
0
votes
1answer
21 views

Prove that $w/w_0$ (no idle over minimum possible) $\le 2-1/n$ for any set of tasks on an n processor system

$w/w_0 $ $\le 2-1/n$ I've noticed this problem in a couple of discrete math and algorithm analysis textbooks. Many of them prove it for n=2, but I want to prove it for all n. The idea is that we ...
2
votes
0answers
22 views

Oracle for the inverse function

Let $F$ be a 1-1 function from $[0,1]$ onto $[0,1]$, which is continuous and monotonically increasing. Two oracles are given: A direct oracle - given $x\in[0,1]$, it returns $F(x)$. An inverse ...
-2
votes
0answers
51 views

Fastetst method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$

Is there any faster method for calculating $\frac{(a+b)!}{a!b!}\bmod{m}$? Lucas theorem is also turning out to be slow! $a,b\leq10^9$ and $m=10^6+3$.
0
votes
1answer
22 views

Summation simplification explanation

I'm trying to understand summation for my algorithm course and it has been a while since I took discrete math. Could any body please explain how does summation simplification work from the problem ...
0
votes
0answers
19 views

0/1 knapsack problem when weights are equal to values [closed]

Is there a way to simplify below algorithm ...
0
votes
1answer
16 views

Discrete optimization of weighted sum under constraint

Let $\lambda_1, \dots, \lambda_n \geq 0$, $\;\;c_1, \dots, c_n \in \mathbb{R}$ and $\;\;\gamma >0 $. We are looking for the maximum of function $f$ with $$ f(x) = x_1\lambda_1 + \dots + ...