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)

2
votes
0answers
34 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
2
votes
0answers
41 views

Explaining this solution regarding finding the transitive closure.

Graph Theory: The question is to find the transitive closure. Let $G$ be a graph. A directed path $v_1 \rightarrow v_3 \rightarrow v_4$ connects the vertex $v_1$ to $v_4$. $G$ has these additional ...
2
votes
0answers
40 views

shrinking a convex hull around a set of polygons

I'm trying to find (Or design) an algorithm that will let me, after I have a convex hull, progressively shrink the hull towards the polygon set via increasing some parameter. I.e., if we use the ...
2
votes
0answers
40 views

Number of valid sequences!

A sequence consists of 1,-1,2,-2,3,-3. The sequence is considered valid if It's empty If S is a valid sequence the so is "1 S-1","2S-2","3S-3" If S1 and S2 are valid, then so is the sequence formed ...
2
votes
0answers
58 views

Integrating sine with Monte Carlo / Metropolis algorithm

I'm learning Monte Carlo / Metropolis algorithm, so I made up a simple question and write some code to see if I really understand it. The question is simple: integrating sine over 0 to PI. The ...
2
votes
0answers
24 views

Is there a faster algorithm than $O(n^2)$ for calculating “cofactors” $C_k = \prod\limits_{j\neq k}(c_k - c_j)$?

Is there a faster algorithm than $O(n^2)$ for calculating "cofactors" $C_k = \prod\limits_{j\neq k}(c_k - c_j)$ ? (presumably $O(n \log_2 n)$ if one exists) In other words, if I have factors $\...
2
votes
0answers
29 views

Completely autonomous traversal of a planar graph

I have to program an autonomous robot to traverse through a grid given in the following figure. But the main problem is that the nodes to visit is not known beforehand, it will be received by the bot ...
2
votes
0answers
33 views

Why does this algorithm converge?

Consider the following problem. Let $p_1, \dots, p_n \in (0,1)$ such that $\sum p_i = 1$. Let $m > 0$ such that $$ q_i := p_i + m \frac{p_i \log(p_i)}{\sum p_k \log(p_k)} < 1 $$ Suppose ...
2
votes
0answers
26 views

An implement of Constructing elliptic curves of prescribed order

In the Reinier Bröker's Phd thesis——Constructing elliptic curves of prescribed order(2006), he present a effective way to generate a elliptic curve with a given order N. And the heuristic run time of ...
2
votes
0answers
31 views

Probabilistic methods and equations over $m$-dimensional space

Given a set $A$ of $n$ different points in the space $(\mathbb{Z}_p)^m$ (assume $p$ is prime), and given $\delta>0$. show the following property holds for a big enough $n$ and $p$ (you can demand ...
2
votes
0answers
39 views

Using $\pi$ to number by X-mas presents

Context: For this X-max, I will make $50$ presents by myself for my family. I would like to label them so that the labels are totally ordered and all different. However, I think that the traditional $...
2
votes
0answers
59 views

Convex shape in ellipsoid containment test

Supposed you to want find out if an ellipsoid fully contains a convex shape. In the picture below I have drawn two situations. The left shape is overlapping with the ellipsoid, and the right shape is ...
2
votes
0answers
28 views

Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$. I want to show that $W(n)\in \Theta(n)$. Attempt 1 I understand the technique used in this question that solves ...
2
votes
0answers
30 views

Calculate the shortest continuous path between shapes without passing thru other shapes in a specific order?

I have the following points, shapes and paths I would like to calculate how to go thru: We do not have to move in a diagonal direction if that poses a problem. Here would be the movement with just ...
2
votes
0answers
18 views

Given a set of integers $S$, what is the maximum integer that is a product of one or more integers from $S$ not exceeding $X$?

Given a set of integers $S$, which will contain no more than $100$ integers. Now, what would be the fastest approach to find $M$ which is a product of one or more integers from $S$ (and multiple usage ...
2
votes
0answers
40 views

Famous Burning Ropes: Optimal Measuring in General Case

well known riddle: given two ropes that each take an hour to burn (they do not burn uniformly or identically, necessarily) measure 45 minutes. solution: light 3 out of the 4 ends, and then light the ...
2
votes
0answers
14 views

Counterexample for applying directed graph's max-flow algorithm on undirected graphs

I'm looking for examples of very simple graphs (preferably less than 10 nodes) that would serve as counterexamples to the claim that the Edmonds-Karp's algorithm would work on undirected graphs out-of-...
2
votes
0answers
54 views

Validity of Monte Carlo

My question regards the fundamental validity of the concept of Monte Carlo. In the text where I learned about Monte Carlo some time ago and also on all resources I found on the internet, all authors ...
2
votes
0answers
27 views

How does one decide if $N = pq$ is prime or not in the special case when $N \equiv 3 \pmod 4$?

I know that there are primality testings that are deterministic but I wanted to know the answer of this question anyways, just for fun. I was trying to design a randomized algorithm that decides ...
2
votes
0answers
190 views

Why use Backtracking line search method to implement an algorithm

I am new to MATLAB and I am asked to implement on matlab the following algorithm: Steepest descent Newtont Quasi-Newton (bfgs) Gauss-Newton using a line search method and the justify my decision. I ...
2
votes
0answers
33 views

Ideal Card Game

I have invented a very interesting card game. All the cards from 2 to 10 (in four colours) are divided evenly between the two players (the deck is shuffled before dealing the cards, of course). Now ...
2
votes
0answers
50 views

A recursive problem with GAP concerning lists and an iterator loop

I have the following question concerning a list algorithm in GAP: Let $L_1$ be a non-empty list with certain objects as entries. I wrote a program and called it helping_program_1. The Input for ...
2
votes
0answers
43 views

How many number of multiplication/addition operations are there in a multiplication of two numbers of equal length?

BACKGROUND: Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will). Assumption: Just for the sake of this question, let's assume that the term "...
2
votes
0answers
40 views

Border rank of tensors

Can anyone help me find the rank and border rank of the following tensor: \begin{align} T=a_{11}\otimes b_{11}\otimes c_{11}+a_{12}\otimes b_{21}\otimes c_{11}+a_{11}\otimes b_{12}\otimes c_{12}\\ ...
2
votes
0answers
77 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
2
votes
0answers
77 views

packing problem of semicircles into rectangle

I have problem. How can I get the maximum amount of semicircles (for example radius $35\;mm$) into rectangle $(485\times 185\:mm)$. I found many articles about packing of circles but nothing about ...
2
votes
0answers
78 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
2
votes
0answers
41 views

Riemann Zeta continued fraction approximants

In the paper Continued-Fraction Expansions for the Riemann Zeta Function and Polylogarithms by Djurdje Cvijovic and Jacek Klinowski, there is a claim that I cannot reproduce. In the abstract they ...
2
votes
0answers
33 views

Minimizing a floor expression

Consider the expression $$ax - b\left\lfloor\frac{cx}{m}\right\rfloor$$ Variables $a, b, c, m$ are positive integers (all of which are known), and $x$ is an unknown integer. The bounds on $x$ are $...
2
votes
0answers
57 views

Stable Marriage algorithms other than Gale-Shapely?

I've looked around lot and I haven't been able to find any algorithms for to the traditional stable marriage problem (I'm not talking about any of its variants like the roommate problem) besides the ...
2
votes
0answers
65 views

Newton's method on a surface

I am trying to use Newton's method to find the stationary solutions of the integro-differential equation of the form $$\frac{\partial u(r,t)}{\partial t} = -u(r,t) + \int_{\mathbb{R}^{2}}w(r - r')f(u(...
2
votes
0answers
75 views

Tweaking Reddit's Ranking Algorithm

This image explains how Reddit's Ranking algorithm works. As you know, Reddit is a very high traffic site. Therefore, the post rank decreases quite fast. This algorithm puts emphasis on bringing ...
2
votes
0answers
30 views

Fast multiplication times a fixed constant $A$?

Is there a way to speed up integer multiplication of billions of $B_{i}$'s times a fixed $A$? We can configure $A$ to be either small compared to the $B_{i}$'s (e.g. $10^{10}$ compared to $10^{200}$) ...
2
votes
0answers
72 views

Dishwasher Unloading: Optimal Algorithm

Suppose you are unloading cutlery from a dishwasher containing $4$ types of cutlery: teaspoons, tablespoons, knives and forks. Each type has 8 pieces. You hang the cutlery on a rack with two sides. ...
2
votes
0answers
64 views

Accelerated gradient descent versus nonlinear conjugate gradient descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has $O(1/T^2)...
2
votes
0answers
94 views

Efficient elevator strategy

Suppose an institution building has 12 floors and there are a total of 8 lifts. Now lets say a situation arises at peak times where almost all the lifts are crowded and people randomly enter any lift, ...
2
votes
0answers
37 views

Factorization by multiplying and representation as difference of two squares

Definition 1.$$R: \mathbb N \to \mathbb N: \ R(n) = \lceil\sqrt{n}\rceil^2-n.$$ This is the distance from $n$ to the smallest square greater or equal to $n$. Definition 2. Let $a$ be as positive ...
2
votes
0answers
41 views

${n \choose m}$ on periodic lattice (Bravais)

How can I generate all symmetry-inequivalent selections of m sites on a periodic 2d (Bravais) lattice with n sites? Are there some general results or theorems which may be useful in this type of ...
2
votes
0answers
139 views

How do I solve the Frenet-Serret equations for the curve, instead the curvature/torsion?

So I happen to be working in a hobby side project which happens to be increasingly convoluted so now, naturally, I have come to the aid of the gurus. It turns out that I am trying to solve the ...
2
votes
0answers
95 views

Efficient computation of matrix determinant in finite ring

I am trying to implement generalization of Hill cipher. My idea is very simple: the size of key matrix should be arbitrary number not only three. All steps of this cipher is trivial except computation ...
2
votes
0answers
43 views

Assignment problem, minization of the Standard Deviation

I have an assignment problem. So typically I need to find the optimal combination between two sets of parameters P, M. I know that the Hungarian Algorithm is often privileged for this kind of problem ...
2
votes
0answers
82 views

Fast algorithm to invert a large sparse matrix

I am interesting in sparse matrix that defined at here. I am looking for a fast algorithm to invert the matrix (better than Gaussian Elimimation). Could you suggest to me some methods that reduce ...
2
votes
0answers
28 views

Binary search where the computer may lie upto $k$ times

We are performing a binary search on $n$ elements where the answer to a comparison may be wrong upto $k$ times. What is the time complexity of finding the right element in terms of $n$ and $k$? The ...
2
votes
0answers
104 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
0answers
52 views

Explanation of the algorithmic form

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation.The core of the algorithm is the replacement of a string of $1's$ ...
2
votes
0answers
97 views

The amazing lift.

I would like to ask for a program to efficiently calculate how a lift should fetch the people who need it. Most of us use lifts (or elevators) but maybe it could be programmed to be faster! Or can it? ...
2
votes
0answers
417 views

How to solve instant insanity puzzle with graphs.

So I have a 10 cube insanity puzzle, I constructed the graph (I'll post pc later) based on the colors the problem is that there is just way to many lines and nodes to see the solution. Is there any ...
2
votes
0answers
92 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not $O(...
2
votes
0answers
37 views

Good method for finding roots that *usually* fall within an interval?

I've been using Brent's method to find the roots of a monotonic, nonlinear, non-differentiable function. The roots often fall within a known interval, but Brent's method fails if they occasionally ...
2
votes
0answers
33 views

Efficient algorithm for calculating hypervolume

Given a $d$-dimensional hyperrectangle that spans from the origin to the integer coordinates $l_1,l_2,l_3,\cdots,l_d$. If $V$ is the hypervolume of the solid formed by all points in the ...