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)

2
votes
1answer
97 views

Confusion related to dynamic programming

I was going through this dynamic programming problem. However, I have a confusion In the third picture, having the black border, I didn't get how the For each, we try each string of the k ...
5
votes
2answers
306 views

Sum of the series formula

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= \frac{\sum_{i=0}^{n-1}f(...
2
votes
1answer
167 views

microsoft excel Excel alphabetical index

I would like if someone can give me the numerical indices of the Microsoft Excel alphabetical indices. It Is as follows: $A$ is $1$ and $Z$ is $26$ then the indices starts from $AA=27$, $AB=28$ to $...
1
vote
0answers
453 views

Levenberg-Marquardt training

I am trying to do simplified version of Levenberg-Marquardt alg. for NN with one hidden layer. I found this article: Efficient algorithm for training neural networks with one hidden layer I am not ...
5
votes
2answers
386 views

Proof of Prime Maker Conjecture

In my mind the following conjecture is true: Prime Maker Conjecture I call a number $n$ factor-resistant to $q$ if $q\not\mid n$. Considering $n$ as a composite number, the idea is to make $n$ ...
0
votes
2answers
143 views

$T(n) = T (\frac{n}{5}) + \frac {n}{\log (n)}$ Solving

I want to find the bound for $T(n) = T (\frac{n}{5}) + \frac {n}{\log (n)}$. I tried with forward iteration and this is what i 've got $T(1) = c$ $T(5^1) = c + 5^1$ $T(5^2) = c + 5^1 + (5^2)/2$ $...
4
votes
1answer
202 views

Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?

The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all? With the ...
0
votes
2answers
50 views

Algorithm for integral of standard distribution

I need help in producing random data that follows standard distribution. Since it is to be used in a computer application, I would prefer an algorithm before a table. So, this is what I need. The ...
2
votes
1answer
181 views

Bounding the power of expected value of functions of a random variable.

I am interested in a problem and I do not know where to start looking for possible similar setting. If anyone has a direction to suggest, it would be greatly appreciated. Consider a (finite) set $\...
0
votes
1answer
561 views

How can I calculate the exact expected value of merge sort comparison (not O(n))?

First, the question stated that I have one unsorted list and then I have to split it out into two lists by fair coin flips. (Ex. Head goes A-list, tail goes B-list) Second, I'm trying to solve the ...
2
votes
1answer
1k views

How to check if edge is in some MST (Linear Time)

Assume we have non-distinct edge weights and multiple Minimum Spanning Trees may exist. If we are given an edge, from A-B, how can we check (in linear time) if this edge is part of some MST? Right ...
4
votes
1answer
2k views

How to show that Eratosthenes sieve algorithm has a complexity of $O(n\log n)$

I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem?
1
vote
3answers
1k views

Intuitive explanation of Bailey-Borwein-Plouffe $\pi$ extraction formula?

First, I should clarify, I'm not a mathematician. I don't study maths at college, so my knowledge of maths is sketchy at best. I've been looking with interest at the Bailey-Borwein-Plouffe formula ...
2
votes
1answer
78 views

Optimal distribution of weighted votes

I'm working on a project for my university in wich the students can choose their preferred seminars for the next semester. My goal is it to allocate these weighted votes in an optimal way to the ...
2
votes
0answers
300 views

all eigenvalues of a large sparse symmetric matrix

my question is similar to how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors however i wish to be more concrete and ask if one can, on a standard PC (e.g. a ...
1
vote
1answer
23 views

Square terrain recurrence derivation

You have a square terrain with area $A > 0$. You want to add information into the terrain. You want to subdivide the terrain into $4$ quadrants, process them individually, and assemble the results. ...
1
vote
1answer
123 views

Use of “modulo” operation in place of integer division

would someone please help me with this problem. So earlier, I asked this question: Row and column algorithm And got an answer: The row is :$$r = \left\lfloor \frac{n-1}{t} \right\rfloor + 1$$ This ...
1
vote
3answers
172 views

How to solve two recurrences dependent on each other

Let $F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$ $G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$ We are given $ a_1,b_1,c_1,a_2,b_2,c_2$ and $ F_0,F_1,F_2, G_0, G_1,G_2 $. We have to calculate ...
0
votes
1answer
42 views

Identify gaps in N dimensional data set

We have an interesting problem we need to resolve here, we're using C# .NET 4.0 but the language should be irrelevant as it's a mathematical problem. Problem: we need to identify gaps in N ...
1
vote
1answer
61 views

RSA public exponent problem

I'm trying to work out a very simple RSA algorithm with my own numbers, but I seem to be running into problems. I chose prime numbers 13 and 17, giving me a modulus of 221. $\varphi(221) = 12 * 16 = ...
1
vote
1answer
198 views

Algorithm Design for Delaunay Triangulation?

I am very much happy after seeing some very good answers in this site. I am trying to design a algorithm for the construction of Delaunay Triangulation using Randomized Incremental Algorithm.(I wont ...
5
votes
2answers
581 views

Sparse basis for linear subspace

Suppose I have a linear subspace of some vector space, e.g. described as the column space of some big matrix. How would I algorithmically find a basis of that same subspace where the basis matrix is ...
1
vote
1answer
369 views

Row and column algorithm

Looking for help in revising my algorithm. I need to find one that will give me the row and column of a cell on a grid. The grid is $t \times t$. For example, this is a grid for $t=5$. Now given $n$...
0
votes
2answers
95 views

How can we denote the following function in terms of big-O notation?

I have got a function and want to denote it in terms of bigO notation. f(n) = log4n+n*(1/3). Is this function O(n)? (* here is the multiplication) Thanks for your help
1
vote
1answer
46 views

Complexity analysis of logarithms

I have two functions, f(n)=log(base 2)n and g(n)=log(base 10)n. I am trying to decide whether f(n) is O(g(n)), or Ω(g(n)) or Θ(g(n)). I thinks i should take the limit f(n)/g(n) as n goes to infinity, ...
0
votes
1answer
50 views

Decoding used in Algorithms

Using a transposition matrix of size 4 by 6 (4 columns, 6 rows) and key ‘time’ decode the following message: RLAPET HWBUIE EIERSS TELSRT I am just looking for either a starting point or a step by ...
32
votes
2answers
921 views

Can every number be written as a small sum of sums of squares?

In a practice for a programming competition, one problem asked us to find the smallest number of pyramids which can be built using exactly $n$ blocks, where pyramids have either $k\times k, (k-1)\...
1
vote
2answers
79 views

The growth rate of the functions with respect to each other

There are two functions , for example $f(n)=3\sqrt{n}$, and $g(n)=\log n$. Which one dominates, in other words, is $f(n)=O(g(n))$ or $f(n)= \Omega(g(n))$? Thank you.
1
vote
0answers
82 views

Asymptotic notation of the following function

I have two functions, $f(n)$ and $g(n)$, and I am trying to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$. I am not sure about my answers. Help will be appreciated. a) $f(n)=...
3
votes
1answer
40 views

Indicating the complexity of functions

I am not sure about my answer about the following question. Can anyone help? I try to express whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$, where $f(n)=n^{0,1234}$ and $g(n)=n^{0,...
2
votes
0answers
120 views

The Edge Set Grown in Kruskal's Algorithm

Let G = (V, E) be a weighted, connected and undirected graph. Let T be the edge set that is grown in Kruskal's algorithm and stopped after k iterations (so T might contain less than |E|-1 edges). Let ...
0
votes
1answer
422 views

Recurrence relation using the master theorem $ T(n) = 4T(n/2) + n^2 \log n$ [duplicate]

I am trying to solve the following recurrence relation using the master theorem: $ T(n) = 4T(n/2) + n^2 \log n$ So: $a=4 ,b=2, f(n)=n^2\log n$ , then $n^{\log_2 4}=n^2 $ Now i know that $n^2 \log n ...
1
vote
3answers
3k views

Nested Summation

I have the following nested sum : $$\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}x = x+1$$ I don't have a clue how to solve this one, can somebody help me? Thanks in advance. ${}{}$
0
votes
1answer
43 views

How to compare $ n^{\epsilon} $ and $ \log^bn $ ($\epsilon>0 ,b>1)$

How to compare : 1) $ n^{\epsilon} $ and $ \log^bn $ ($\epsilon>0 ,b>1)$ and 2)$n^{\log n\log\log n}$ and $(\log n)!$
6
votes
1answer
371 views

Can we test if a number is a lucky number in polynomial time?

I know primality tests exist in polynomial time. But can we test if a number is a lucky number in polynomial time ?
1
vote
0answers
80 views

Confusion related to time complexity of fast Fourier transform

I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT. It says that lets say I have a polynomial of ...
2
votes
1answer
86 views

Details about “fingerprinting” algorithms for groups?

where can I find details about "Fingerprinting" algorithms (to test whether two groups are non-isomorphic) "‘Fingerprinting’: For every group $G_1,…, G_r$ evaluate various isomorphism-invariant ...
1
vote
1answer
909 views

Rate of growth of exponential functions

I have difficulties about proving the following: Prove that exponential functions $a^n$ have different orders of growth for different values of base $a>0$. It looks obvious that when $a=3$ it ...
1
vote
2answers
416 views

Deciding whether a function is O(n), Ω(n), or Θ(n)

First of all, this is my homework question, i have my answers and i want to be sure whether i am missing something. I have difficulties about deciding whether f(n) is O(g(n)), Ω(g(n)), or Θ(g(n)): ...
0
votes
2answers
60 views

Algorithm for learning combination preferences

I believe I'm looking for some kind of preference algorithm. Imagine we have three lists. List 1 is appetizers, List 2 is main courses, and List 3 is deserts. Lets assume each list has 50 options in ...
2
votes
3answers
102 views

Understanding $O$-notation and the meaning of $\Omega$

I am studying algorithms, and I have problems on the concepts from an exercise. Thank you so much! Which of the following equations lie in $O(n)$, $\Omega(n)$, $\Theta(n)$ and why. a. $3n+2n^...
3
votes
0answers
162 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
2
votes
1answer
353 views

The Two Clique problem is in P or NP? P != NP for hypothesis.

I need to find a solution to the following question: The problem of the "Two Clique" is in P or NP-complete (assuming P != NP)? The "Two Clique" problem is the following: Given a graph G = (V, E), ...
3
votes
2answers
307 views

Large Clique is in P or NP-complete? P != NP for hypothesis

I need to find a solution to the following question: The problem to find a "Large Clique" is in P or NP-complete (assuming P != NP)? The "Large Clique" problem is the following: Given a graph G = (V, ...
1
vote
0answers
49 views

Reversibility of independent exchange rates

A project has two tasks Task A takes 1 hour, Task B task 4 hours. For this project we enter dollars as the cost currency. ...
1
vote
2answers
75 views

Number of zeros in a number

Is there a quick way of figuring out the number of zeros of some number? It's easy for numbers like: $10$, $100$, $1000$, but not so obvious when the number is something like: $...
3
votes
4answers
509 views

Can you simulate any probability with biased coin throws?

What you're given: $p \in (0,1)$, but you don't know the value of $p$. You have an algorithm $\mathcal{A}_p$ that returns $1$ with a probability of $p$ and $0$ with a probability of $(1-p)$. You ...
1
vote
0answers
103 views

Efficiency of Group-Theoretic Algorithms in MAGMA

Given a finite permutation group $G$ and an element $a\in G$ with conjugacy class $X$, I am interested in determining when for a given element $x\in X$ the subgroup $<a,x>$ generated by $a$ and $...
4
votes
1answer
82 views

Solving the recurrence: $h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 $

I want to solve the following recurrence: \begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation} What are some basic "methods" I can use to guess a ...
2
votes
1answer
772 views

Basic Maths question regarding the selection sort formula.

I'm training to be a software developer and use Stack Overflow a lot, but I'm afraid some basic Maths has gotten in my way. I apologise in advance for a question that may be too easy to be posted here ...