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

Findung a line maximizing the number of given points in a given distance

Suppose I am given an arbitrary set of n points in a coordinate plane and a fixed constant r. What algorithm will find the line L that maximizes the number of points in the given set that are within a ...
0
votes
1answer
10 views

Using limits to prove a function is in the order of another function

I have to prove the following theorem: I am not asking for the whole problem, but am stuck on the first part (Proving that output of c implies g(n) is in the order of f(n)). I know the following: ...
0
votes
1answer
6 views

Counting Inversion Pair using Merge Sort

An inversion is a pair of places of a sequence where the elements on these places are out of their natural order. I understood the naive approach where we take an element from 1 list and compare with ...
0
votes
0answers
7 views

Just like Box Muller algorithm for random numbers in Gaussian distribution, are there any such algorithms for other distributions?

I want to create random numbers in various distributions like Poisson, Binomial, Gamma, etc. I cam across Box-Muller algorithm for random number generation in Gaussian distribution. Are there similar ...
1
vote
0answers
35 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
1
vote
1answer
15 views

Algorithm to approximate this cos(x) equation by successions

I'm a little embarrassed, but I've get blocked solving this: I have to "make an algorithm to aproximate the equation" above. That's all the details I know.
1
vote
1answer
24 views

Can't figure out $O(n \log n)$ divide-and-conquer algorithm

Let's say you are a manager at a local solar farm. You have a weather forecast for the next $n$ days, and want to know what the most profitable single stretch to run your panels for would be. On some ...
2
votes
2answers
25 views

Matching Algorithm in Graph Theory

Given $n$ people, $k$ out of which own a car. We need to match a car for each person without a car. Conditions: Each car fits $5$ people, including the driver. Each driver will only allow his ...
2
votes
1answer
18 views

Whats the formula to work out the minimum monthly payment of a loan?

I'm a developer, and i'm building a snowball debt calculator. I want a formula to work out what the minimum monthly repayment would be on a debt with a given interest. And I really want to get the ...
0
votes
0answers
9 views

Changements that have to be done in order to delete node of red-black tree

According to my lecture notes: Let $x$ be the child of the node that we delete. Let $w$ be its sibling node and $p$ the father of $x$. There are four cases: At the first case, $w$ is red. We ...
2
votes
0answers
23 views

Red-Black tree - “Insert-Delete” [on hold]

I am looking at red-black trees. Unfortunately in my lecture notes, the operations "Insert" and "Delete" are not well explained. Could you explain to me steps that we have to do for these two ...
1
vote
1answer
24 views

Determine if there is a node in a binary postorder anti-sorted tree with key $k$

A binary postorder anti-sorted tree is a binary tree for which the post-order traversal gives the keys that are saved at the nodes of the tree in descending order. Present a pseudocode for the most ...
2
votes
1answer
32 views

Graphing algorithm

I am not sure if this belongs on Mathematics Stack Exchange, but it is somewhat relavant here. The Problem If you've installed any graphing/plotting apps on your smartphone, you will notice that the ...
2
votes
1answer
45 views

Is there a formalism for a universal mathematical representation of algorithms?

I don't know if my question is correct so excuse me if I'm not 100% clear about what I would want to know. Is there a formalism which can capture all possible algorithms (mathematically speaking) ? ...
0
votes
0answers
12 views

Create a list with elements from an other list with specific display order

Consider a singly-linked list $L$ each element of which is a struct with two fields, an integer num and a pointer next to the ...
0
votes
0answers
31 views

Infinite fractional number conversions of any real number

Given a function $f:\Bbb Z_+\to \Bbb Z_n $ representing the real number $$\displaystyle\Delta^n(f)=\sum_{k=1}^\infty f(k)\cdot n^{-k}$$ Does it exists a formula or algorithm to receive the function ...
0
votes
0answers
26 views

Find range of result for given equation

While working on my algorithm I came to this problem: $$x_{1,2} = \frac{-bc-a +- \sqrt{(bc)^2 + a^2 + 2bca - 4bd}}{-2b}$$ $b,c$ are positive integer constants that I know their values. The problem ...
-3
votes
1answer
28 views

If $f(n)$ is not $\Theta (g(n))$ does it follow that $\log f(n)$ is not $\Theta(\log g(n))$?

If $f(n)$ is not $\Theta (g(n))$ does it follow that $\log f(n)$ is not $\Theta(\log g(n))$? We say that $f(n)= \Theta (g(n))$ if there exist some constants $c_1$ and $c_2>0$ and $n_0$, such ...
0
votes
1answer
29 views

Bounding summations

Show that $\sum k2^k = \Theta( k2^k)$. I tried to use mathematical induction to prove the bound, but it didn't work. There are other ways that can be used to prove this bound, like bounding the ...
2
votes
0answers
32 views

$T(n) = 2T\left(\frac{\log n}{2}\right)+ \theta(n)$ [on hold]

$T(n) = 2T\left(\frac{\log n}{2}\right) + \theta(n)$ can this be further simplified to a single asymptotic form? For starter, can I say that the answer is bounded by O(n) ?
0
votes
1answer
67 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
32 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
38 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
36 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
57 views

The recurrence $T(n) = 2T(\sqrt{n})+n$ [on hold]

How to solve the recurrence $$T(n) = 2T(\sqrt{n})+n$$ I used substitution by $n = 2^k$ but haven't been able to solve it. Please help
0
votes
1answer
17 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
26 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
31 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
22 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
34 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
29 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
26 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
28 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
16 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
35 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
19 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
20 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
26 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
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
23 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
20 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
50 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
97 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, . . . ...