# Tagged Questions

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).

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 ...
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 ...
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 ...
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 ...
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 ...
24 views

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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 "...
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}\\ ...
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 ...
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 ...
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 ...
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 ...
33 views

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 $... 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 ... 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(... 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 ... 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}) ... 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. ... 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)... 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, ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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$... 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? ... 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 ... 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(...
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 ...