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)

1
vote
1answer
23 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
17 views

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

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
18 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
10 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
9 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
32 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 [on hold]

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
33 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
13 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
20 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
42 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
29 views

Approximation algorithm for mine packing problem [on hold]

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
13 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
100 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
25 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
109 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
18 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
50 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
15 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
43 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 ...
0
votes
0answers
27 views

Prove or disprove that there are no finite numbers of algorithms can solve the difference equation? [closed]

Prove or disprove that there are no finite number of algorithms can solve the all the difference equation? Please comment below regarding this problem
3
votes
1answer
88 views
+50

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
53 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
32 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
23 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
53 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
26 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
36 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
11 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
30 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
65 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
35 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
23 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
29 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
84 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
40 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
43 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 ...