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

What can $T(n) = 2T\left(\frac{\log n}{2}\right)+ \theta(n)$ be reduced to?

What can $T(n) = 2T\left(\frac{\log n}{2}\right) + \theta(n)$ be reduced to?
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 ...
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: ...
2
votes
1answer
71 views

How to efficiently find the largest perfect square dividing a given large integer?

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
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 ...
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 ...
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 ...
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
28 views

Faster algorithm to test associativity of magma [duplicate]

Is there a faster algorithm to test associativity of a finite magma than just computing the two products of every triple of elements?
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
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?
-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 ...
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 ...
11
votes
3answers
984 views

Quickest way to determine a polynomial with positive integer coefficients

Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are all positive integers. ...
0
votes
1answer
68 views

Zig-Zag traversal of list

Suppose that each node of the list has the following structs: string num next It is given a string $w$. Suppose that $w$ is in the list at a node $p$, of which the struct num has the value n. We ...
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 ...
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
2answers
56 views

Efficiently calculating the 'prime-power sum' of a number.

Let $n$ be a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$. Is there an 'efficient' way to calculate the sum $e_1+e_2+\cdots +e_m$? I could always run a brute ...
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 ...
2
votes
1answer
267 views

Maximum subarray problem

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones ...
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
200 views

What is the difference between the Big O and Big O star (asterisk) operator?

I'm doing some research on algorithms complexity and in different papers I notice both the use of the regular Big-O operator O(...) and a variant ...
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
140 views

Patterson Algorithm

In the proof of Theorem I(c) from this paper (pdf) (original zip), there is a proposition that says: So by our choice of $g$ we get $\theta/p \mid \psi/p$ whence $\theta \mid \psi$. (this is ...
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 ...
-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
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 ...
3
votes
0answers
49 views

$n$ solutions Sudoku

Is there an algorithm which can calculate a $9 \times 9$ Sudoku with non-trivial $n$ possible solutions? So if you play it you can play it for example 4 times? So if you play it there's a choice in ...
0
votes
0answers
146 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
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 ...
4
votes
5answers
694 views

Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
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
2answers
92 views

Problem in game theory related to traffic networks

I have learnt game theory for a short period of time and I am not familiar with multi-player non-zero sum games. Here is a problem from my book which I am stuck: In this road network below each of ...
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 ...
0
votes
4answers
2k views

Sum of digits of a product is equal to product - 9

Say we have a number greater than or equal to 5 and less than 10, like 5. If we multiply it by 2, we get 10, and if we take the sum of the digits of 10, we get 1. If instead of adding up the digits ...
9
votes
3answers
293 views

Finding 1000th 5-smooth number

Smooth numbers are natural numbers that are products of only small prime numbers. They have some applications in cryptography. A number is 5-smooth if its only prime factors are $2,3$ or $5$. ...
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
2answers
130 views

How can I convert camera motion into zoom?

I try to reconstruct a camera of a video sequence via match moving techniques. After the reconstruction process all seemed to work as expected, but then I've realized my camera is moving forward ...
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 ...
3
votes
2answers
585 views

maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...
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 ...
4
votes
4answers
279 views

Relationship between degrees of continued fractions

I'm trying to compute the values of differing degrees of continued fractions like $\sqrt 2$, e and other similar fractions. My theory was to take the reduced fraction at an arbitrary depth and the ...
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
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 ...
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 ...
-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!
-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, . . . ...
2
votes
1answer
279 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
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 ...
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 ...