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

When change making problem has an optimal greedy solution?

A well-known Change-making problem, which asks how can a given amount of money be made with the least number of coins of given denominations for some sets of coins (50c, 25c, 10c, 5c, 1c) will ...
0
votes
0answers
7 views

Number of checks to find the median of a set of random 16 numbers

Our teacher gave us a problem to program a way to figure the number of checks needed to find the median of a set of 16 random numbers using a decision tree. he also told us that the least possible ...
1
vote
1answer
14 views

Algorithm to minimize number of trips?

Tom the shepherd and his herd of $n$ sheep have decided that it’s time they leave their home and head to a new home across the state as food is low. However, there are two issues. First off, Tom only ...
1
vote
1answer
32 views

Polygon Matching [on hold]

Given a set of polygons vertices and a template polygon vertices, find all that match polygons from the given set of polygons with a template polygon.
0
votes
1answer
18 views

Maximizing the number of zero entries in a linear combination of matrices

I was wondering if there exists an algorithmic way of solving the following problem. Let's say you have a bunch of square $N\times N$ matrices (call them $M_i$), and you want to form a linear ...
0
votes
0answers
19 views

What is the meaning of sub-constant error?

The error is defined as $E \geq \frac{1}{2ab(1+ab)}$, where $a$ and $b$ are both positive . The claim is: if we fix the value $a$, then to get a sub-constant error $E$, we must ensure that ...
0
votes
1answer
22 views

Randomized Algorithm for finding perfect matchings

I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings. Here is a link to the ...
0
votes
2answers
15 views

Finding $2m+1=2\alpha k+\alpha^2$ quickly

Given some positive integer $m$ I'm looking for all solutions $\alpha,k>0$ to $2m+1=2\alpha k+\alpha^2$ with $0<k^2<2m.$ Right now I'm finding these by looping over each of these possible $k$ ...
1
vote
0answers
14 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
13 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
7 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
9 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
41 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
19 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
27 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
28 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
20 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 ...
0
votes
1answer
21 views

Need help figuring out $O(log$ $n)$ algorithm

Let's consider a strictly decreasing function $f : \mathbb{N} \rightarrow \mathbb{Z}$. That is, $f$ takes as input any natural number $(i ∈ N)$ and returns an integer such that for any $i$, $f(i) > ...
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
34 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
48 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
13 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
32 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
29 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
31 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
34 views

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

$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
69 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
33 views

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

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
39 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$ [closed]

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
27 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
10 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
30 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
29 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
29 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
18 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
36 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 ...