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
0answers
29 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
46 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 = ...
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
29 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
150 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 ...
2
votes
0answers
25 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
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 + ...
0
votes
0answers
44 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
16 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
135 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
78 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
24 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
56 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
18 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 ...
0
votes
0answers
28 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
38 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
29 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
13 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
41 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
66 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
25 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
25 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
36 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
87 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
42 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
52 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
29 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
190 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 ...
4
votes
0answers
80 views

Minimum number of real multiplications to multiply two quaternions

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
36 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 ...
0
votes
0answers
15 views

Optimal algorithm for finding maximum number of alternating cycles in edge-colored multigraph

I'm having trouble finding any information on this. Suppose you have an edge-colored multigraph $G$ with its edges being of two colors (for example, a given edge can be either black or grey). An ...
1
vote
0answers
23 views

Complexity of $\gcd$ algorithm

I'm reading a paper in which it's used the fact that a gcd computation of two numbers $(a,n)$, can be done in $O(\log n)$ time, and $[1]$ is referenced for the result. I haven't found that specific ...
0
votes
0answers
46 views

How to Solve this maximization Problem?

You are given two s: N and K. Lun the dog is interested in strings that satisfy the following conditions: The string has exactly N characters, each of which is either 'A' or 'B'. The string s ...
0
votes
0answers
78 views

set cover problem: d-cover

I've the following problem: Let the universe U and a list of subsets (S_1,..., S_k), be the usual input for the (unweighted) SET COVER PROBLEM, Consider the following doubling scheme for producing a ...
0
votes
0answers
12 views

Complexity of recurrence containing geometic series.

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
2answers
30 views

Complexity of recursive algorithm.

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...
0
votes
0answers
22 views

Closest pair points algorithm with Manhattan Distance

According to the solution of closet pair (euclid distance) with divide and conquer algorithm during merge algorithm we prove that for each point at distance d (minimum distance of two different sub ...
0
votes
0answers
16 views

Difference between two solution for Closest pair of points

I'm having a problem with understanding the difference between two solution of of closet pair of point in plane. According to the the Wikipedia when we are merging two planes we need to check at most ...
0
votes
0answers
17 views

Question about Karp reduction

friends. I have a curiosity about Karp reduction. What we need to do for reduction from problem X to problem Y is that 1) Transformation from Instance of problem X to Instance of problem Y can be ...