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
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
51 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
38 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
20 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
119 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
32 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
164 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
22 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 ...
0
votes
1answer
23 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
1answer
18 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 + ...
0
votes
0answers
48 views

Prove that every connected graph whose vertices are all of even degree has no cut-vertices

I am trying to prove that every connected graph whose vertices are all of even degree has no cut-vertices. Now, I am not very good with proofs but I was thinking about proving it by contradiction, ...
0
votes
0answers
18 views

Approach for this Popular Algorithmic Problem

Given a matrix we have to select one value from each row so that the total value cost selected is minimum. Now the problem is we cannot select column "0" to "J" in "I"th row if we have selected ...
5
votes
2answers
142 views

Differentiate polynomials in $\mathbb{Z}_2[x]$

It seems suggested that the differential of a polynomial in $\mathbb{Z}_2$ is as I would expect: $$\begin{align} &f = x^6 + x^3 + x + 1 \\ &f' = 6x^5 + 3x^2 +1 \mod 2 \\ &f'= x^2 + 1 \\ ...
1
vote
1answer
121 views

Algorithm - Circle Overlapping

Say you have a shape you want to fill up with circles, where by the circles overlap just enough to cover the whole surface area of the shape. The circles will remain as a fixed size however the shape ...
2
votes
3answers
33 views

Help formulating a proof showing two lists can be merged with 2n-1 comparisons

I need some help formulating a proof that shows that two lists of size n can be merged in 2n - 1 comparisons. I understand the essence behind it, but have difficulty proving it mathematically. I ...
0
votes
0answers
36 views

Round robin match location algorithm

Although this is a software engineering problem, I feel like this is a mathematical question so wanted to ask it here. I'm trying to figure out an algorithm for setting a matches location for a round ...
1
vote
2answers
59 views

Shortest Path on Specific Graph with one Property !?

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
1
vote
0answers
23 views

Runtime of recursive algorithm - Master's Theorem

I wrote a computer program that solves a question, and I am interested in knowing what is the runtime. My aim is for $O(\log n)$, and I'd like someone more experienced (and smarter?) to review my ...
1
vote
0answers
38 views

Fast algorithm to invert a large sparse matrix

I am interesting in sparse matrix that defined at here. I am looking for a fast algorithm to invert the matrix (better than Gaussian Elimimation). Could you suggest to me some methods that reduce ...
0
votes
1answer
44 views

graph theory δ(G) + δ(complement G) <= n - 1

Hi I am new to graph theory and being terrible with proofs I am looking for some hints to prove this: Prove that if G is a graph of order n, then δ(G) + δ(complement of G) ≤ n − 1. I know that ...
1
vote
2answers
34 views

Proof that all n-length subsets have been generated from a set.

I have a function in a computer program that generates integer subsets within an integer set. The function takes an set of sequential numbers and finds all the possible subsets of a given length. The ...
1
vote
0answers
26 views

Given plaintext and ciphertext of the same length, how could one generate potential symmetric keys if encryption algorithm is unknown?

This question is about both encryption and about how and if one could transform data from one given form to another given form and back. I am given plaintext and ciphertext, both of which are the ...
2
votes
1answer
69 views

Longest Path in undirected unweighted graph

I came across a problem where I have to find out the longest path in a given graph. I have list of edges ( eg.{AB, BC} ) which states there is an edge between vertices/nodes (A,B,C). Now i want to ...
1
vote
3answers
69 views

Are there infinite sequences not reproducible by finite algorithms?

Let me know if this is a repeat question. I was thinking that sequence of integers we deal with (e.g., the digits of $\pi$, the prime numbers, the Fibonacci numbers, pseudorandom numbers) seem to be ...
1
vote
2answers
38 views
2
votes
1answer
28 views

Where can I find an algorithm to compute $\min_{x \in \Delta_n} \langle g , x - y \rangle_1 + c\lvert x - y\rvert_1^2$?

I wish to compute the minimizer of $$ \min_{x \in \Delta_n} \langle g , x - y \rangle + \frac{c}{2}\lvert x - y\rvert_1^2$$ where the subindex $1$ indicates that the norm is the $1$-norm and ...
0
votes
1answer
27 views

Binary Representation of the Collatz Conjecture

What is the benefit of looking at the binary representation of the collatz conjecture. I know that it makes the computation easier because there is really one operation involved which is multiplying ...
0
votes
0answers
55 views

Calculate optimal path through changing network?

Apologies if this question is not suited for this forum. The question extends beyond my knowledge of mathematics and programming, it is quite hard to get my head around it let alone put it in to ...
0
votes
0answers
13 views

Arguing independent set [duplicate]

Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. A subset $I$ of $V$ is called an independent set if for any two distinct vertices $u$ and $v$ in $I$, $(u, v)$ is not an edge in $E$. ...
0
votes
2answers
88 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
0
votes
1answer
46 views

The meaning of 'worst case'

When giving bound on convergence rate, complexity and so on, people sometimes will specify it by 'worst case'. What is the meaning of 'worst case'?
0
votes
1answer
57 views

Learning finite automata from symbol set and given sample

Good day. We have a finite automaton F1, for example, . We need to get automaton F2 that accepts strings like accepted by ...
0
votes
2answers
31 views

Exponential vs Polynomial running time

As per this article: http://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time we know that exponential is worse than polynomial in terms of running time. Is it safe to say that ...
5
votes
3answers
214 views

How do we identify twin primes .

as known , each prime number greater than 3 is of the form $6k-1$ or $6k+1$ . twin primes are all sort of two adjacent primes of difference $= 2$ as: $$(11,13) ,(17,19),\ldots,(6k-1,6k+1)$$ -Is ...
2
votes
0answers
124 views

Minimum number of real multiplications to multiply two quaternions [closed]

Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows: $$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$ We only need the ...
0
votes
0answers
51 views

Savitzky-Golay Coefficients for end points

I've been looking for solution to clean up SG Filter end points and I discovered a shifted set of coefficients in Numerical Recipes that might do the trick. Nr = 0; Nl = 4; 0.086, -0.143, -0.086, ...
0
votes
0answers
13 views

Estimate parameters of a system on realtime defined as follows

I have a motor I need to estimate the parameters on real time. To simplify the problem I will put the general equation in matrix form that governs it in discrete time: $$ u_q(k) = \left[ ...
4
votes
1answer
33 views

How can I compute $\sum_{i=1}^n x_i \log(x_i)$ in a stable manner?

Given a vector in $\mathbb{R}^n$ I have an algorithm to compute $$\sum_{i=1}^n x_i \log(x_i)$$ However for my application the norm of $x$ must be 1, hence for big $n$ the components tend to be too ...