Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

0
votes
0answers
36 views

A probabilistic algorithm (something close to Discrete logarithm)

$p$ - is a prime number. $a\in Z_p^*$ is a creator of the group $Z_p ^*$. The definition of the Discrete logarithm of $c\in Z_p^*$ is: $$\log_a c=b\iff a^b=c \mod p $$ Assume we have an algorithm ...
0
votes
0answers
23 views

which algorithm can be used to solve $L_1$-like problem?

I have a problem like this, $$ \min |v|_1+\lambda\sum_{i=1}^{n}v_i'\cdot\log v_i'\\ s.t.~~ ~y=Av\\ \sum_{i=1}^n v_i'=1 \\ v'_i=\frac{|v_i|}{\sum_{i=1}^n|v_i|}~~~(i=1,\cdots,n)\\ $$ where $v,v'\in ...
0
votes
1answer
24 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
2
votes
1answer
41 views

Is there an algorithm to find minimum number of undefinable words in a dictionary?

Here's the problem. Every word in a dictionary is defined by a set of other words. For example "cat" may be defined as "small mammal with fur". Can we choose a set of 'base' or 'prime' words such that ...
1
vote
1answer
21 views

Why Petri Net tokens are not added?

Reading this article it says: A firing of an enabled transition removes one token from each input place and adds one token to each output place. Now if I have the following net, with all ...
0
votes
1answer
24 views

Probabilistic algorithm for $a$ that is not a quadratic residue

We have $Z_n$ ($n\in \mathbb N$). $a\in Z_n$ is a quadratic residue if exists $x\in Z_n$ s.t. $x^2 =a \pmod n$. If there is no such $x$ that make it so $a$ is not a quadratic residue. There is a ...
2
votes
0answers
39 views

multi-game round robin tournament algorithm

Each year I am part of a group that hosts a "Lawn Game Olympics." 6 different lawn games (bocce, ladder golf, washer toss etc...) and every year a different amount of teams shows up. The first year ...
2
votes
2answers
37 views

Sampling from the von-Mises Fisher distribution?

This topic has already been tackled on this website (here). But, unfortunately, no clear cut answers were given. In (Wood,1994), there is apparently a rejection algorithm for sampling from this ...
1
vote
1answer
41 views

How many sets of four points in an MxN grid have one point contained by three other points?

Given a 3x3 grid: 1 2 3 8 9 4 7 6 5 We find 126 distinct sets of 4 points $$\binom{9}{4}$$ There are 8 cases such that when the points are connected with a line in clockwise direction, one point ...
0
votes
1answer
10 views

Invent a polynomial algorithm to find max non-degenerate minor

There is a matrix $A$ with $n$ rows and $m$ columns. The task is to invent a polynomial algorithm to find non-degenerate minor of maximum size. If I got it right, we can reduce this to Gaussian ...
1
vote
1answer
45 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
0
votes
1answer
51 views

finding total number of subset pairs of a set that has equal xor??

I recently came across a problem where i need to find the total number of subset pairs which has equal xor value for a given set. Like for following example: ...
0
votes
0answers
3 views

PageRank metaphor as suspended unlimited capacity pools

What do you think about my metaphor of the centrality measure PageRank? PageRank is an algorithm for evaluating node centrality: it's a function $f:G \to R^n$ where $n$ is the number of nodes in the ...
3
votes
0answers
66 views

Problem using the Fourier transform and convolution to compute an integral

I'm trying to write a subroutine (in Fortran) to compute integrals of the form $$I=\int_{-L}^{L} f(x)g(y-x) \:\mathrm{d}x, $$ using the convolution theorem and fast Fourier transforms. In my routine, ...
1
vote
0answers
8 views

I need help with a complex weighted algorithm

I need help with a formula/algorithm I just cant work out what I am doing or find anything on the internet. I am not very good at mathematics I have not done it high since school so I understand if ...
1
vote
3answers
67 views

Exact concept of Monte Carlo Method [closed]

I am a programmer and just came across the section where in Monte Carlo was discussed. I would like to know the exact concept of Monte Carlo simulation. In net i have read about it that it is the ...
1
vote
2answers
43 views

What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$

What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$, where $S_n$ is a symmetric group and $a$ and $b$ have same cycle type? Question 2: Is there any command in ...
1
vote
1answer
34 views

Courses, books or other resources specifically written to teach and help understand algorithmic language?

The algorithm course/book I'm taking (based on the book Algorithm Design by Jon Kleinberg and Éva Tardos) assumes we understand the language of algorithmic problems and solutions. However, it is not ...
0
votes
0answers
20 views

How to get samples of different paths?

Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed). Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B. I ...
1
vote
0answers
24 views

Algorithm to generate Rhombic sphere tiling

I want to make a function for generate generic Rhombic triacontahedron and any level of detail of rhombic sphere tiling I want to know that can we use rhombic face to tile sphere in more detail than ...
0
votes
1answer
17 views

Set of edges is MST?

Given a Graph $G = (V,E)$ and given a subset $ T \subset E$. I would like to test, whether T is already a MST of G or not in constant time. Note: If $T^{MST}$ is the MST of G, then we know that $T ...
1
vote
1answer
32 views

Find if there is a matrix that her sum of each column and row representing two vectors

We have two vectors: $(a_1,...,a_n),(b_1,...,b_m)$. We want to know if there is a matrix $M_{nm}$ that all its elements are from $\left\{0,1\right\}$ with this condition: The sum of all the elements ...
1
vote
0answers
62 views

Efficient elevator strategy

Suppose an institution building has 12 floors and there are a total of 8 lifts. Now lets say a situation arises at peak times where almost all the lifts are crowded and people randomly enter any lift, ...
18
votes
2answers
738 views

Puzzle: Cracking the safe [duplicate]

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
2
votes
1answer
42 views

What is the worst-case running time of this algorithm?

What's the worst case running time? while flip_coin() == heads: continue; In other words, I flip a fair coin until I get tails. Of course we knows the expected ...
-1
votes
1answer
58 views

Inverse modulo without brute force [closed]

I have this piece of code and I want to know 'x' before the loop without brute force. Is there a way to do an inverse modulo or something? ...
0
votes
0answers
16 views

How to compute the logarithm of a computable number

Let's say you have a computable number $x>0$. $\ln(x)$ is computable as well. Given the computability of $x$, what is a computation for $\ln(x)$. I am using the definition where $a$ is computable ...
3
votes
0answers
22 views

Finding a cycle in a directed graph, however…

Say we have some directed graph, G. Every now and then, I can add either: a single arc from an existing vertex to another existing vertex (but no self-loops), add one new vertex with an arc to an ...
1
vote
2answers
60 views

Divide and Conquer in big O notation

I've got a problem – divide-and-conquer part of my program divided my problem into 2 parts: 1/7 and 5/7 of a problem + merging in a linear time. I need to know it's asymptotic complexity. I know, it ...
0
votes
1answer
49 views

How to finish this proof by contradiction?

The Problem: You were planning to study real hard this quarter so you took out n books on algorithms. However you had better planning than execution and you have not read a single book and they are ...
1
vote
2answers
30 views

Finding the upper bound for a number's factors length

Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be? For example: $X = 10000$ I want $3$ and $3$ ...
0
votes
3answers
55 views

Multiplying array elements

We are given a sorted array containing elements at indices $x_1,x_2,x_3,x_4,....x_n$. We have to find the product $\displaystyle\sum_{i,j,k}x_ix_jx_k$ where $j\geqslant i$ and $k\geqslant j$. For ...
0
votes
0answers
23 views

Determine complexity of algorithm

I have two pieces of code below. a) sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++ ; b) ...
0
votes
1answer
49 views

Fractional Knapsack- explanation

The following algorithm is given: ...
0
votes
1answer
60 views

Complexity of Least Common Multiple

I would like to know the complexity of computing the least common multiple of $n$ natural numbers. Does it depend on Euler's totient function?
2
votes
3answers
85 views

Almost extended Euclidean algorithm - $ax+by=\gcd(a,b)+2$

So I have this equation: $$\eta+2=2g+1n,$$ where $g,n \in \mathbb{N}_{\geq 0}$ and $\eta \in \mathbb{N}_{>0}$. I want to find all possible integer-valued 2-tuples $(g,n)$ that satisfy this ...
0
votes
1answer
32 views

Scheduling: Moore's algorithm

In scheduling we have Moore's algorithm to minimize the the number of late jobs. Because of the EDD-rule (earliest due date first), I guess this algorithm has complexity $\mathcal{O}(n \log n)$. I ...
0
votes
1answer
223 views

Basic idea of proof

I am trying to understand the proof that the expected running time of quicksort is $O(n \log n)$. Could you maybe explain me the basic idea? I am confused right now. EDIT: Suppose that we use the ...
0
votes
3answers
38 views

A lower bound on sorting algorithms

I think I have a proof that $n\ln n$ is optimal in the sense that is it a lower bound for sorting algorithms. See here for a list. It must be greater than $n$ as this is too linear, and the $\ln$ ...
1
vote
0answers
34 views

Factorizing a Polynomial over the Integers

What are the most efficient algorithms to factorize a polynomial over integers, knowing that it has only integer roots? I googled around a lot, but most of the work seems to be around Finite fields. ...
0
votes
0answers
28 views

Optimization Toolbox (fmincon) - How to set logical constraints?

I'm pretty new to Optimization and barely understand it (was about ready to slit my wrist after figuring out how to write Objective Functions without any formal learning on the matter), and need a ...
2
votes
0answers
23 views

Factorization by multiplying and representation as difference of two squares

Definition 1.$$R: \mathbb N \to \mathbb N: \ R(n) = \lceil\sqrt{n}\rceil^2-n.$$ This is the distance from $n$ to the smallest square greater or equal to $n$. Definition 2. Let $a$ be as positive ...
-1
votes
1answer
22 views

How to compute the time complexity for a recurrence relationship?

I have to compute the time complexity for this recurrence relationship: T(n) = \begin{cases} c1, & \mbox{if } n\mbox{ = 1} \\ 8T(n/4) +n +c2, & \mbox{if } n\mbox{ > 1} \end{cases} Can ...
1
vote
1answer
16 views

Computing wavenumbers for discrete Fourier transform

I'm trying to implement a Fortran program to compute the derivative of a function using the FFT. To begin with, just to test my installation of fftpack, I computed the Fourier transform of ...
-1
votes
3answers
52 views

Find Numbers that Start with $3$ and End with $1$ on the given interval [closed]

I am looking for a function / formula that would take in a number and determine whether it starts with 3 and end 1 For example, with 3 digits numbers, I'd like to get $301, 311, 321, 331$ and so on ...
0
votes
1answer
36 views

How does one map a graph into a vector (feature space)?

Assuming there is an undirected weighted graph. How can one convey it's geometrical structure into a feature space? Are there any common practices?
0
votes
0answers
52 views

Solving the recurrence $T(n) = 5T(n/7) +\log n$

I am trying to solve the recurrence $T(n) = 5T(n/7) +\log n$ to find the complexity of an algorithm. Although I solve this immediately with the Master Theorem if I try to solve the recursion I found ...
2
votes
1answer
31 views

Big O notation proof for a divided problem

I have a problem: the algorithm is dividing the given problem into two subproblems - one is 3/5 big and another is 4/5 of the size of the problem - and then merges those two parts together in a linear ...
1
vote
1answer
63 views

Extended Euclidean Algorithm with negative numbers minimum non-negative solution

I came through a problem in programming which needs Extended Euclidean Algorithm, with $a*s + b*t = \gcd(|a|,|b|)$ for $b \leq 0$ and $a \geq 0$ With the help of this post: ...
2
votes
0answers
40 views

${n \choose m}$ on periodic lattice (Bravais)

How can I generate all symmetry-inequivalent selections of m sites on a periodic 2d (Bravais) lattice with n sites? Are there some general results or theorems which may be useful in this type of ...