Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

1
vote
2answers
130 views

GCD and LCM of three numbers

Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L? gcd(x, y, z) means the greatest common divisor ...
30
votes
6answers
2k views

The milk sharing problem

I found a book with math quizzes. It was my father's when he was young. I encountered a problem with the following quiz. I solved it, but I wonder, is there a faster way to do it? If so, how can I ...
1
vote
1answer
53 views

Proof with $\Theta$

I am having a hard time proving the following statement: Suppose that the functions $f_1, f_2, g_1, g_2 : \mathbb{N} \rightarrow \mathbb{R}^{\ge 0}\ are \ such \ that \ f_1 \in \Theta (g_1) \ and ...
1
vote
0answers
106 views

A question on the computational complexity of Boruvka's algorithm

One algorithm that finds a minimum spanning tree in a graph in which all weights are distinct is Boruvka's Algorithm (also known as Sollin's Algorithm). On the page you would see once you clicked ...
2
votes
2answers
2k views

Calculating the shortest distance between n number of points on a scatter graph

This has been bugging me for about two weeks now.. I have a cartesian plane with n number of points randomly placed on it. You can get the coordinates of each point. Now, how do you calculate the ...
3
votes
2answers
58 views

Non-iterative solution for $(a + nb)\mod c < d$

With the given parameters $a$, $b$, $c$, and $d$ I'm looking for a solution of the formula $(a + nb)\mod c < d$. The smallest positive $n$ is the value I want to determine. I can easily solve ...
0
votes
1answer
144 views

Time complexity in terms of theta notation [duplicate]

sum= 0; for (i = n; i > o; i = i/3) for (j = 0; j < n^3; j++) sum++; what is the time complexity (in Θ- notation) in terms of n? so far, i've gotten to this point: The ...
-1
votes
1answer
296 views

Time complexity function in terms of theta notation

sum = 0; for (i = 0; i < n; i++) for (j = 1; j < n^3; j = 3*j) sum++; what is the time complexity (in $\Theta$-notation) in terms of ...
0
votes
1answer
84 views

Finding minimal number of vertices which connect a graph

I'm doing some graph theory studying on my own and I encountered a problem. I have a connected graph $G$ of $11440$ edges and an unknown number of vertices. What would be the best algorithm to find ...
0
votes
0answers
34 views

Levenberg-Marquardt algorithm

Does anyone know if the Levenberg-Marquardt algorithm used to solve non-linear least squares problems has any regularization process?
2
votes
1answer
159 views

Maximizing an algebraic expression using brackets

It's a riddle of sorts: given a list of numbers $\alpha_1 \dots \alpha_n$ and operators $o_1 \dots o_{n-1}$ which can be only $\times\, \mbox{or}\, + $ if the above is a specific algebraic expression ...
0
votes
1answer
61 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
0
votes
0answers
30 views

Algorithm Request, choosing rows from a sparse table of integers to sum to a minimum row value

I'm writing some software, and one part of the software needs to be able to solve this problem as well as possible. Consider a table of integers and goal, for example: $$T = \begin{array} ...
1
vote
1answer
52 views

How to find the best algorithm

I'm dealing with a problem here. It says:Build an algorithm which takes two lists(the elements of the lists are natural numbers) and finds if every element of the first list is displayed at least ...
5
votes
1answer
102 views

Flip all to zero

I have a square grid of size $N$, with rows numbered from $0$ to $N - 1$ starting from the top and columns numbered from $0$ to $N - 1$ starting from the left. A cell $(u, v)$ refers to the cell that ...
0
votes
0answers
94 views

Minimum cost problem

I have been given $n$ points on a $2d$ plane. In terms of their $(x,y)$ coordinates. Now suppose I have to set, say firms, at these positions and the cost for building the first one is zero. For every ...
0
votes
1answer
21 views

Diffie hellman and the discrete algorithm problem

Suppose Alice and Bob are exchanging keys using Diffie-Hellman Key-Exchange Algorithm. a - Alice secret key g - generator p - prime x - the public key passed from Alice to Bob. Eve is listening to ...
1
vote
0answers
32 views

Efficient Cartesian product which ignores classes of elements

Given $n$ sets $X_1,X_2,..,X_n$, and what I am calling an ignore set $I = \{I_1, I_2,..,I_m : \forall i \in I_i, i \in \bigcup X_i\}$. I would like to find the cartesian product $X_1 \times X_2 ...
3
votes
0answers
42 views

Minimal graph such that the greedy pathing algorithm always terminates

Saw this question languishing on Reddit and decided it could stand a signal boost. Since I'm not familiar with the area, it might be quite elementary, but it's at least interesting from a layman's ...
1
vote
0answers
62 views

Gauss-seidel and implicit method

I have a matrix $\mathbf{X}$ and I want to apply a function $f_{ij}$ to each entry of it, until convergence is satisfied. If a value is known in this matrix, then the $f_{ij}$ at this point may be the ...
0
votes
1answer
94 views

Jacobian in Levenberg-Marquardt for 4-Parameter equation

I am trying to fully understand how I can use Levenberg-Marquardt to minimise a 4 parameter equation. There are lots of fancy programs to do this but the documentation about the mathematics is ...
1
vote
0answers
30 views

Adjacency matrix of a graph

How can I prove that an adjacency matrix of a graph and an adjacency list representation are polynomially related? Thanks
1
vote
2answers
47 views

$( x \cdot y ) \mod 37 = 1$

I am doing a paper for my security class. I have this equation which I'm trying to understand $$( x \cdot y ) \mod 37 = 1 $$ e.g. if $x = 8$ and $y = ?$ ; which ...
3
votes
0answers
1k views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
4
votes
2answers
119 views

Longest increasing subsequence part II

Using the answer provided here, I am now trying to find the longest increasing subset in two different sequences of numbers defined by location1 and location2. For each location there are 16 ...
2
votes
1answer
77 views

Fair Division: Making the Differences in Players' Valuations Believable

When teaching basic fair division algorithms, the students always propose some simple and (at the first glance) correct solutions for $n$ players, which unfortunately are not correct! The only way I ...
2
votes
0answers
43 views

LLL and factoring polynomials in $\Bbb Z[x]$

Given a degree $2k$ reducible polynomial $f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$ with $gcd(a_{2k},\dots,a_0)=1$ that is known to be of the form $f_1(x)f_2(x)$ with $deg(f_i(x))=\frac{deg(f(x)}{2}=k$ ...
1
vote
1answer
58 views

Do this algorithm terminates?

Let $x \in \mathbb{R}^p$ denote a $p$ dimensional data point (a vector). I have two sets $A = \{x_1, .., x_n\}$ and $B = \{x_{n+1}, .., x_{n+m}\}$. So $|A| = n$, and $|B| = m$. Given $k \in ...
3
votes
1answer
39 views

Finding a recursive definition and computing $B(10)$

For $n \geq 1$, let $B(n)$ be the number of ways to express $n$ as the sum of $1$s and $2$s, taking order into account. Thus $B(4) = 5$ because $4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = ...
3
votes
0answers
253 views

Convert CRC to result of reversed polynomial?

Looking at the Wikipedia page for CRCs I see that they list a bunch of standard CRC polynomials along with the Reversed Polynomials of each. If I have a value that was calculated with a certain ...
2
votes
1answer
121 views

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a ...
1
vote
2answers
127 views

Longest increasing subsequence

How can I find the longest increasing subsequence of numbers in the sequence {3,2,6,4,5,1}? Same question for ABCBDAB Why would being able to solve these types of problems be important in Relational ...
7
votes
3answers
263 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
8
votes
0answers
161 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
0
votes
1answer
90 views

Trapezoid rule error seems to be 1/N instead of 1/N^2

I'm not sure this should go to Math or Programming sections, but I think mathematicians know programming more often then programmers know mathematics I decided to post here. I was playing ...
0
votes
1answer
84 views

Showing that an algorithm is a gradient descent method

I am stuck on a question about gradient descent, it asks to "show that that the perceptron learning algorithm is a gradient descent method for the squared error target function $(y - \sum w_ix_i)^2$". ...
0
votes
1answer
40 views

Dynamic problems

A natural number n represents the initial position in the game. When it is a players turn he/she is allowed to ...
0
votes
1answer
84 views

Prize distribution system based on quantity/priority per day

I'm trying to figure out a way to "fairly" distribute a pool of prizes on a daily basis depending on the time the contest will run, the priority and max items per day/week. For a better explanation, ...
2
votes
1answer
79 views

Combinatorics/Task Dependency

Here is a competitive programming question: You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
1
vote
0answers
84 views

Is there a proof that Encrypting and then Decrypting any data using AES 256 will result in the same data?

I use AES quite often at work (I'm a software programmer) and I trust that it "works" without understanding the maths behind it. It's a black box to me. Does a mathematical proof exist that AES 256 ...
1
vote
0answers
79 views

Distributed calculation of $\pi$

I want to write a simple distributed software for the calculation of $\pi$. I want to use a formula which is as easy to distribute as possible. I'm thinking of the BBP formula, or something similar (a ...
1
vote
1answer
216 views

Tracing a most-general unifier algorithm

I'm trying to trace the algorithm for getting the most general unifier, and I'm a bit confused. Can there be more than one solution? (although the adjective 'most' suggests otherwise) found online: ...
1
vote
1answer
135 views

Efficient Algorithm for Generalized Sylvester's Equation

Is there an efficient computational algorithm for solving the generalized Sylvester's equation: $\displaystyle \sum_{i=1}^{n}A_{i}XB_{i}=C$ The conventional Kronecker product approach to solve this ...
3
votes
2answers
131 views

The number 3211000 is 7-special

Define a positive integer $k$ to be $n$-special if it satisfies the following properties: It has $n$ digits (0, 1, ..., 9) The 1st digit is equal to the number of 0's in the decimal representation ...
1
vote
1answer
49 views

Combinatorics Question: Graph Algorithms

If a weighted graph is disconnected, it has no spanning trees. (obviously) However, is there a way to find a spanning forest of minimum weight in the disconnected graphs??? If anyone could, I am ...
1
vote
1answer
65 views

Determining box-box intersection without cross product

Does anyone know a way to correctly determine if an axis-aligned box intersects with an oriented (using any invertible square matrix) box in a space with three or more dimensions, without using cross ...
2
votes
1answer
50 views

Find a matching that is stable, but neither optimal or pessimal.

How can I setup a preference table to find a matching that is stable, but neither optimal or pessimal. It can be for any number of women and men where n>2, but I'm not having any luck coming up with ...
1
vote
1answer
77 views

Proof for existence of exactly one solution for the number of marbles in each box

There are four boxes A, B, C and D containing marbles. Two boxes are randomly selected and the number of marbles in each box is summarized. This procedure is repeated five times with the ...
0
votes
0answers
39 views

Need an algorithm to choose the most appropriate numbers from a set to satisfy an increasing value

Given a set of relatively random numbers (example): {125, 375, 100, 280, 900, 670, ...} I want to identify the numbers that most closely sum up to a set such as: ...
0
votes
1answer
28 views

Compute all the directional derivatives of a trivariate polynomial function quickly

Given a trivariate polynomial $A\in\mathbb{R}[x,y,z]$, a direction $\vec v\in\mathbb{R}^3$ and a point $p\in \mathbb{R}^3$, what is the fastest way to compute the directional deriviatives ...