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
7 views

What can $T(n) = 2T(\log n)/2 + \theta(n)$ be reduced to?

What can $T(n) = 2T(\log n)/2 + \theta(n)$ be reduced to?
0
votes
1answer
24 views

Grade School Multiplication Algorithm for Binary Numbers explanation

I under stand the shifting but not why it will always give the right answer? For Example: ...
1
vote
1answer
24 views

Solving the Diophantine equation $ax + by = c$ using Maple [on hold]

I wrote a program in Maple called EEAsolve (I'm not sure how I can show everybody the code), and what it does is takes 3 parameters from $ax + by = c$: $a$, $b$, and $c$. When I run the program with ...
2
votes
0answers
32 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
0
votes
0answers
5 views

Need an algorithm to add a range of results from a function.

There is a formula. G(L*.035+.65) that is common to what I do at work. Occasionaly, I need to not only have the result, but the complete sum of a range of results. In this example, I know that G is ...
0
votes
2answers
28 views

Generating a random binary matrix with fixed number of nonzeros

I want an algorithm (just the idea, not the actual code) to generate a random $n$ by $n$ matrix with binary entries, but with the condition that the number of nonzeros must be a fixed number $c$. Any ...
-3
votes
0answers
40 views

The recurrence $T(n) = 2T(\sqrt{n})+n$

How to solve the recurrence $$T(n) = 2T(\sqrt{n})+n$$ Suppose we have some initial value $T(a)=t_0$ and we want to find its value for all input of the form $a^{2^k}$. From the recurrence we get ...
0
votes
1answer
14 views

Equality Constraints in Quadratic Programming

Now I am new to the world of primal-dual algorithms and I want to understand the SOCP-Code of Lobo/Vandenberghe/Boyd (primal dual interior point method). Currently I am working through Goldfarb and ...
1
vote
1answer
22 views

Why does the feasible set being a matroid ensure a polynomial time algorithm?

Reading up on matroid theory in the context of graph optimization and in particular minimum spanning trees. It turns out that finding a set of acyclic arcs is equivalent to finding an independent ...
1
vote
1answer
24 views

Problem understanding analysis of greedy maximal weighted matching algorithm

Greedy Algorithms for Matching $M = \emptyset$ For all $e \in E$ in decreasing order of $w_e$ add $e$ to $M$ if it forms a matching Theorem The weight of the matching $M$ returned by the ...
0
votes
0answers
5 views

Hastings algorithm

Let $Q=\begin{pmatrix} 0 & 1 & 0 & 0 & 0\\0.5 & 0 & 0.5 & 0 & 0\\ 0 & 0.5 & 0 & 0.5 & 0\\ 0 & 0 & 0.5 & 0 & 0.5\\ 0 & 0 & 0 ...
2
votes
1answer
21 views

Algorithm to partition a set into subsets of max weight

I have a big set $S$ of elements $e_i$, each $e_i$ characterized by an integer weight $w_i$. I would like an algorithm to split set $S$ into subsets $S_j$ such that: The sum of weights in each ...
0
votes
0answers
30 views

$T(n) = T(n/3) + T(2n/3) + cn$ - recursion tree with constance $c$

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac ...
3
votes
1answer
32 views

Every graph can be optimally colored greedily.

I was at a conference today and someone said that if the graph $G$ has chromatic number $n$ then there is a way to order the vertices so that coloring greedily gives us a coloring with $n$ colors. By ...
0
votes
0answers
9 views

Ratio of fpras approximations

If I need to compute the ratio $\frac{A}{B}$ and if there exists an FPRAS that approximates the numerator and the denominator separately, that is, $\exists A_{fpras},B_{fpras}$: $Pr(A(1-\epsilon)\le ...
5
votes
0answers
26 views

Computing N cofactors

I have an $N\times N$ matrix of small size (say $N=20$). Is there a way to evaluate the $N$ cofactors of the elements of the first row, faster than in the obvious way as $N$ independent determinant ...
-1
votes
1answer
23 views

Number of submatrices of sum K

I have an array $A[]$ of N elements ($N<=1000$, $-1000<=A[i]<=1000$). We define a Matrix M such that $M[i,j]= A[i]*A[j]$. In the resulting matrix $M$, we have to count the number of ...
0
votes
1answer
26 views

What can you say about two expressions with same reminder?

I am working on Integer factorization problem and I came to those two interesting expressions: $a,b,c,x$ are non negative integers $a,b < c$ $$\frac{ax + b}{c-x}$$ and $$\frac{ac + b}{c-x}$$ ...
0
votes
0answers
15 views

Function to define how combinations N items can be organized with a certain condition

This is not a factorial only problem If I have 5 items and I wanted to know how many possible ways they could be arranged, the answer is 5! or 120. However my situation is I need to know how many ...
1
vote
1answer
33 views

Nth pemutation of Lexicographic String

Can someone please explain the logic behind the mathematical equation, that for finding the Nth Lexicographic rank of a string the Leading Entry is $a_q$ if $k=q\cdot (n!)+r.$ The link to the problem ...
2
votes
0answers
18 views

Sorting for maximum mean squared successive difference

I have a set of numbers and I have to order them for maximum MSSD (mean squared successive difference). For example, if I have the ordered set {1,2,3,4,5,6} this would give me an MSSD of ...
0
votes
1answer
19 views

Using exchange argument in proving greedy algorithm

Here's a problem solvable by greedy algorithm: You are a company and you have list of tasks that still need to be done (but you're late with them already). For a given task we have information about ...
0
votes
1answer
24 views

Assigning values to players on a team

There are $4$ different teams $(A, B, C, D)$, each with $15$ people. All these teams competed against one and other in a competition. Each person in a team teamed up with another person inside their ...
-1
votes
1answer
35 views

$t(n) = t(n-2) + 2^n$ [closed]

Assume that $t(n) = 1$ for $n\le 1$ and the recurrence given is for $n > 1$ $$t(n) = t(n-2) + 2^n$$ trying to find the recurrence within big theta accuracy, help!
1
vote
1answer
33 views

Show that we can check if $G$ has a circuit in time $O(V)$.

Consider a non-directed graph $G=(V,E)$ at which it is not allowed that we have edges of the form $(v,v)$. Show that we can check if $G$ has a circuit in time $O(V)$. According to my notes, we can ...
0
votes
1answer
19 views

Computing time-complexity of DP recursion

I've written an algorithm which uses 3-dimensional DP table and it goes as follows: $DP[i][j][0]$ can be computed in $O(1)$ for any $i,j$ and $DP[i][j][k]=\max(DP[i][m][0]+DP[m+1][j][k-1]) $ for all ...
0
votes
0answers
16 views

Topological sort of a graph- how can we find a contradiction?

The topological sort of a graph can be considered as an order of its nodes along a horizontal line so that all the directed edges go from the left to the right. How could we show that all the ...
-1
votes
0answers
19 views

Show that the Dijkstra's algorithm computes correctly the shortest paths

Suppose that we are given a weighted, directed graph $G=(V,E)$ at which the edges that begin from the initial node $s$ could also have negative weights, but the weights of all the ther edges are ...
4
votes
1answer
46 views

How could we prove the correctness of the algorithm?

Consider two sets $D=\{ d_1, d_2, \dots, d_n\}$ and $E=\{ e_1, e_2, \dots, e_m \}$ and consider an other variable $K \geq 0$. Show that we can answer in time $O((n+m) \lg (n+m))$ the following ...
4
votes
0answers
17 views

Simple criteria to know if the p-nary notation of an integer can generate a tree by preorder traversing?

I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like: ...
-6
votes
1answer
96 views

Describe the algorithm [closed]

Describe an algorithm in pseudocode that finds all terms of a finite sequence of integers that are greater than the sum of all previous terms of the sequence. procedure find all biggies(a1, a2, . . . ...
1
vote
1answer
32 views

Master Theorem. How is $n\log n$ polynomially larger than $n^{\log_4 3}$

I was reading Master theorem from CLRS, and it said that $n\log n$ is polynomially larger than $n^{\log_4 3}$ while $n\log n$ is not polynomially larger than $n$. What does it mean to be ...
0
votes
0answers
29 views

Polynomial time algorithm for finding the chromatic sum of a tree.

As the title goes, a polynomial time algorithm for finding the chromatic sum of a tree is required. NOTE: Finding the chromatic sum of a graph is also called the sum coloring problem - The sum ...
1
vote
0answers
11 views

Using FFT to compute DFT of a polynomial

i currently studying about FFT and DFT and we were given simple question: Use the recursive FFT to compute the DFT of this polynomial of '3' degree: $$-1\:+\:4x\:+\:3x^2$$. So, i go to this ...
1
vote
1answer
36 views

Determining the coefficient of $x^n$ in $\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$

I looking for an algorithm to efficiently find the value$\mod p$ of the coefficient of $x^n$ in a generating function of this form: $$\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$$ where $p$ is some prime ...
0
votes
0answers
14 views

Blum Micali Algorithm Security By Seed Size

I'm coming from a computer science background, so I'm having some difficulty with these high level mathematics. With reference to the Blum Micali algorithm: (underscore represent subscript) ...
0
votes
0answers
15 views

How to apply Diophantine equation [closed]

How can I use Diophantine equation in the next equation? $AX + BY + CXY = D$
1
vote
1answer
57 views

Integer factorization: Single solution for integer equation

While working on my integer factorization project, I came to this: $(A + CX)(B + CY) = D$ $X,Y,A,B,C,D$ Are integer numbers $A,B,C,D > 0$ $X,Y >= 0$ $A,B,X,Y < C < D$ If $X=Y$ than $Y ...
1
vote
1answer
10 views

some notations in algorithm analysis

Assuming $k$ is a variable, 1.then someone claims that the algorithm complexity is super-linear or sub-linear in $k$, here what is the meaning by using super-linear or sub-linear? 2.also, if ...
4
votes
1answer
80 views
+50

How can one find intermediate digits of a root of an algebraic equation?

I was wondering whether there is a way to find intermediate digits of an algebraic equation. For example, if I have $$234x^{\frac{1}{12345}}-24621x^{\frac{1}{3456}}=1$$ And I want to find the ...
4
votes
0answers
45 views

Algorithm for finding “fact families”

My friend's 3rd grader encountered the following question regarding "fact families" on her math homework: I was in 3rd grade sometime in the 1980s, so I don't believe I ever encountered this term ...
0
votes
3answers
36 views

Decompose a polynomial: find $f(x)$ such that $h(x) = f(g(x))$

I try to make an algorithm that decomposes a polynomial, ie find $f(x)$ such that $h(x) = f(g(x))$ by knowing $h$ and $g$. For example, having : $h(x) = 112x^6 + 1232x^5 + 2772x^4 - 3388x^3 + 847x^2 ...
4
votes
1answer
27 views

Algorithm concerning orthogonal matrices

Say I have a n-dimensional orthogonal matrix, with some of its elements given and these others unknown. Does there exist an effective algorithm to find out the unknown elements and restore the whole ...
0
votes
0answers
14 views

Algorithm to find the minimum of a function over a k-size partition of a set

I wish to compute the minimum value of a non-linear function over all possible size-k subsets of a given set of integers. Does anyone know about a specific algorithm to solve this problem?
0
votes
1answer
33 views

Relation between Genetic Algorithm and Information theory

Can anyone suggest me some references (papers, books, lecture notes) on the relation between GA and Information theory?
-2
votes
1answer
33 views

How to define human-friendly axis marking notches

I have a need to compute values of "tick" marks on an axis that uses various different min/max ranges. Specific example -- Picking Human-Friendly Notch Step Axis Y has function values range between ...
0
votes
0answers
33 views

Memory efficient algorithm to find network diameter

I am trying to implement memory efficient algorithm to find network diameter. So far I have classic bfs but it fills memory for large graphs (I am trying to work with Orkut data set) The ...
-1
votes
0answers
32 views

Formal proof for Euler's Theorem [closed]

I have been looking for a formal proof to the following theorem: A connected graph has an Eulerian path iff it has at most two graph vertices of odd degree. I have not been able to find one ...
1
vote
0answers
27 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
0
votes
0answers
44 views

Hill Cipher issues

I am new to math and have took interest into hill cipher; thus, I have attempted to create my own codes, but have faced several issues. As you may know, hill cipher requires matrix to encrypt and ...