Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

3
votes
2answers
87 views

Algorithm to find the optimal setup

Suppose I have $2n$ numbers, from which I will compute $n$ sums of two-number pairs. For example, I have $6$ numbers $(1, 2, 3, 4, 5, 6)$ and I can generate three sums of $1+3=4$, $2+6=8$, and ...
3
votes
1answer
1k views

Origin of the Breadth-First Search algorithm

I'd like to know about the history of the breadth-first search algorithm. Can anyone point me to its inventor? It appears that the depth-first search algorithm is attributed to a man named Charles ...
1
vote
1answer
84 views

Finding a distribution for random number generation

I am writing a program for solving the shortest path in travelling salesman problem, with a twist that there are multiple salesmen who partition the cities among themselves, thus creating two part ...
0
votes
1answer
157 views

Asymptotic Complexity Problems with Subtraction

I know that when finding the asymptotic complexity of a given function, you must pay attention to the rate of change in a for loop. For example: for (i = 1 to n) { //some action of constant time ...
1
vote
1answer
212 views

Properties of shortest walks and simple paths during optimization

Let $G=(V,E)$ denote a digraph, $s,t\in V$ two different vertices in $G$ and $w:E\to\mathbb R$ the weighting function for all edges. Moreover $\mathcal K$ denotes the set of all walks, $\mathcal E$ ...
4
votes
0answers
170 views

Use of graph theory to determine tensor contraction ordering

I am considering using a computer program to execute tensor contractions like the following: $\displaystyle \sum_{ij}^{o} \sum_{ab}^{v} \sum_{KL}^{X} B_{ia}^{K} B_{ia}^{L} B_{jb}^{K} B_{jb}^{L} $ ...
0
votes
2answers
194 views

How to prove there is no algorithm for a problem e.g. generating next prime?

Say I want to find the next prime directly without a test. AFAIK there is no known formula. Is it possible that since we've failed to find a formula, then we might be able to prove that there is no ...
0
votes
3answers
255 views

Finding an approximate diagonal in a grid

Imagine a 2 dimensional grid, with a variable size of $ x*y $. For this example of figure 1, let $ x=14; y=5 $. Now one may position "pixels" in this gird. They can only be placed on the grid's points ...
0
votes
1answer
51 views

Bounding below the difference of sums

I would like to bound below the following expression: $\lambda(m,n)=\sum\limits_{i = 1}^{m+n}\lg{i} - \sum\limits_{i = 1}^{m}\lg{i} - \sum\limits_{i = 1}^{n}\lg{i}$ by some expression that ideally ...
0
votes
1answer
1k views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
0
votes
0answers
54 views

Algorithm for precedence related job allocation

Suppose we have a set of jobs. Some jobs are related to others for example Job (a) has to finish for Job(b) to begin. Some other jobs are not related, that means can run in parallel. We have a ...
2
votes
1answer
91 views

Minimim steps required based on game logic

I have the following simple game logic. You start with G gold and 0 experience at Time = 0 minutes. There are different types of houses what you can build, each with his own properties. House A ...
2
votes
1answer
281 views

Growth of $ n^{\ln n}$ versus polynomial, exponential, and logarithmic forms

I'm attempting to clarify the proofs of these forms. Starting with $n^{ln\,n}$ I want to compare with polynomial, exponential, and logarithmic forms. I can understand just by looking at them which ...
0
votes
1answer
96 views

Inputs for Binomial Heaps

This is my first question here. I was studying binomial heaps and it time analysis. Can there be any inputs that cause DELETE-MIN, DECREASE-KEY,and DELETE to run in Big-omega(log n) time for a ...
3
votes
2answers
1k views

Graham scan convex hull algorithm - include all points on boundary

I have am implementing the Graham scan algorithm to find the convex hull of a set of (two-dimensional) points. (My implementation is in Haskell in case anyone wants to know.) The problem is that not ...
0
votes
2answers
104 views

Explanation needed on this rather basic recurrence solution

We are studying about recurrences in our analysis of algorithms class. As an example of the substitution method (with induction) we are given the following: $$T(n) = \lbrace 2T\left(\frac{n}{2}\right) ...
6
votes
1answer
7k views

Show that the solution to $T(n) = T(n - 1) + n$ is $O(n^2)$

Hello and thanks for taking the time to answer my question. The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I ...
3
votes
1answer
87 views

Does anyone know the name of the following problem?

At a given day a number of $N$ salesmen (from the same company) are randomly scattered in a landscape with $M$ cities. At the next day as many cities as possible should have a salesman visiting, no ...
5
votes
3answers
7k views

Finding the longest path in an undirected weighted tree

I have a tree where each edge is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the ...
4
votes
7answers
1k 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 ...
2
votes
2answers
512 views

How many times will “statement” be executed?

Suppose we have the following: ...
2
votes
4answers
88 views

Determination quantity of integers, the sum of digits of which is equal to $N$

For a number in the range $1 \le N \le 36$, i want to find a quantity of four- digit numbers, the sum of digits of which is equal $N$. I would be very grateful for the algorithm! Thank you!
1
vote
0answers
104 views

Maximum Independent Set on Path and Ring

I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...
1
vote
0answers
179 views

Find total number of sets of integers which satisfy a given equality and inequality

Compute the total number of different sets of integers a1, a2,..,an which satisfy the following equality and constraints: $$ ...
2
votes
0answers
29 views

Broken disk head

Broken disk head: We would like to read 1 byte = sequence of 8 bits from a disk, starting from bit 0. Our disk head reads 1 bit at a time. Disk head can only move forward, but after reaching bit 7 ...
1
vote
0answers
50 views

proof of convergence of penalty function algorithm in nesterov's 2004 text

Hi: If anyone has yuri nesterov's 2004 "introductory lectures on convex optimization" book, I will write the question down in latex but otherwise, if no one does, then it's too confusing to explain my ...
2
votes
1answer
66 views

Determining the maximum value

I received at my work some meal tickets valued at 8.80 euros a piece, and my wife who works at another firm, receives meal tickets at 7.50 euros a ticket. The neighborhood that we work at accepts ...
1
vote
1answer
141 views

Is there a well known algorithm for scattering points uniformly around a central point?

Is there a well known algorithm for scattering points uniformly around a central point? For example, imagine the pins on Google maps, and imagine you had a data set where two or more points had ...
4
votes
3answers
3k views

Check if line intersects with circles perimeter

Say I have this circle here. What would be an algorithm to check if lines like the green or blue lines intersect the edge of the circle, but not the red line. So lets say ...
3
votes
1answer
151 views

Visiting points, algorithm

I'm learning for the exam from algorithms and data structures (that I have in a month) and I can't manage with finding efficient algorithm for this problem: We are given $1\le n\le 5000$ points on ...
1
vote
0answers
20 views

Existence of solutions to a Specific kind of non-linear system of equations with rational variables

Consider a system of the form $c_{11}a_1b_{1} + c_{12}a_2b_{2} + \cdots c_{1n}a_nb_{n} = q_1$ $c_{21}a_1b_{1} + c_{22}a_2b_{2} + \cdots c_{2n}a_nb_{n} = q_2$ $\vdots$ $c_{m1}a_1b_{1} + ...
4
votes
2answers
1k views

Counting the number of paths through a grid graph traversing all vertices exactly once

So I asked a question on stack overflow and they suggested I migrate over here. I'm writing a program to solve the following problem: Given a grid of x by y dimensions, calculate the number of ...
1
vote
1answer
56 views

Big 0h question how are they similar?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
2
votes
2answers
2k views

The smallest set of unit- length closed intervals that contains all of the given points

Given a set of points like this: $ \{0.7, 1.0, 1.5, 2.0, 2.3, 2.6, 3.1, 3.6, 3.9, 4.2, 4.7, 5.2, 5.5 \} $ i want to creat a set of lists so that each of the lists keeps the numbers between a closed ...
3
votes
1answer
348 views

Algorithm for a group of people meeting each other person in the least amount of iterations

In my specific case, I have a pool of 80 people that I will be splitting into groups of 4. I would like to rotate people through the groups in a way that each person meets every other person in the ...
2
votes
1answer
101 views

Split the set of points, algorithm

I'm learning for the test and I can't manage with this problem: We are given a set of $n < 1000$ points and an integer $d$. The task is to create two disjoint sets of points $A_1$ and $A_2$ ...
1
vote
1answer
134 views

How to calculate temperature on/off constants

Please consider the following as pseudo code for my question ...
2
votes
1answer
146 views

The existing bound on Edmonds-Karp doesn't seem to be tight

(I have posted the following in theoretical CS stackexchange, but realized that it's the wrong place, so I'm reposting it here) I'm reading CLRS's (Cormen et.a al) Introduction to Algorithm, and ...
2
votes
1answer
258 views

Largest idempotent

Given the prime power factors of $N$, is there a non-quadratic algorithm for finding the largest idempotent of ring $\mathbb{Z}/N\mathbb{Z}$? (That is, the largest number $A \lt N$ such that $A^{2} ...
2
votes
2answers
3k views

Table tennis ranking algorithm

I'm trying to create a formula for ranking an in-office ping pong system. Currently I've created a percentage and ordered the ranking by that, but it seems unfair as someone could play a single match, ...
0
votes
3answers
126 views

How can $n \lg n = O(n^{log_3 4 - r})$?

How can I understand this bound, for me it is not true. $$n\lg n = O(n^{\log_3 4 - r})$$ where $\lg n = \log_2 n$ and $r > 0$ I'm trying to solve this recurrence $T(n) = 4T(n/3) + n\lg n$ using ...
4
votes
2answers
3k views

Does Dijkstra's algorithm work when I multiply weights of successive nodes?

The concrete example is: I am given n currencies and pairwise exchange rates, and I have to change say dollars for euros. And I don't have to change money ...
2
votes
0answers
141 views

Revision Tracking Graph

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it, which contains all edges leading into it on all paths from a ...
2
votes
1answer
90 views

Alogrithm to deterime if one set is a subset of another

Given $p$ and $q$ in any format desired, how could I deterime if $\{x \in \mathbb{R}:p(x)\} \subseteq \{x \in \mathbb{R}:q(x)\}$ is true using an algorithm. Obviously checking all elements of ...
0
votes
1answer
72 views

An algorithm to determine expected profit on a game

I 'm searching for an algorithm (and except the naive brute force solution had no luck) that efficiently ($O(n^2)$preferably) does the following: Supposing I’m playing a game and in this game I’ll ...
3
votes
1answer
276 views

A graph coloring problem concerning 3-colorablility

If I take a triangle-free graph, By Grötzsch's theorem, it should be 3-colorable, and I have already had a coloring. If I change the color of one vertex, and I want to check how many vertices (at ...
0
votes
1answer
98 views

Solving this inequality without trial and error

"What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?" I know the answer is $n = ...
1
vote
1answer
136 views

Mathematical formula for permutation

I have been assigned to write mathematical equation for permutation using only 1,3,5,7,9 numbers starting from single digit going up to five digits numbers. For example Single digit 1 3 5 7 9 two ...
0
votes
1answer
72 views

Why is the upper bound of this statement always incremented by 1?

Why is "for j = 1 to n" translate to this? Why is the upper bound always incremented by 1? $$\sum_{j=1}^{n+1}1 $$ Why isn't it $$\sum_{j=1}^n1 $$ "for j = 1 to n" is written in pseudo code btw ...
2
votes
1answer
426 views

Minimum number of transformation required to equalize a list

Given a list of $n$ positive elements (including $0$). We are allowed to perform only one transformation which is to increment each element of the list except one. What are the minimum number of ...