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
28 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
54 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
29 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
53 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
185 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
32 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
40 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
39 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
74 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
72 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
32 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
52 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
71 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
71 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
57 views

Accelerated Gradient Descent V.S 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
245 views

multi-game round robin tournament algorithm

Each year I am part of a group that hosts a "Lawn Game Olympics." 6 different lawn games (bocce, ladder golf, washer toss etc...) and every year a different amount of teams shows up. The first year ...
2
votes
0answers
93 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
34 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
117 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
94 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
42 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
81 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
103 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
50 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
413 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
36 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 ...
2
votes
0answers
44 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 ...
2
votes
0answers
30 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 MSSD=$\frac{...
2
votes
0answers
128 views

Least Impossible Subset Sum

Given a set A which contains natural numbers from 1 to N. Also given another set B which contains p natural numbers between 1 to N. We have to find out the least sum of subset which is not possible in ...
2
votes
0answers
415 views

Fastest way to find modular multiplicative inverse

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in $p=...
2
votes
0answers
133 views

Show that matrices multiplication and LUP decompositions have the same difficulty

Let $M(n)$ be the time to multiply two $n\times n$ matrices, and let $L(n)$ be the time to compute the LUP decomposition of an $n\times n$ matrix. How to show that multiplying matrices and ...