Questions tagged [mathematical-programming]

Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.

Filter by
Sorted by
Tagged with
-2
votes
0answers
31 views

P=np resolution du problème [closed]

Bonjour j ai essayé de répondre au problème P=NP. Pourriez-vous y jeter un coup d'œil est me dire ce que vous en pansez. https://docs.google.com/document/d/1pchCpN6PKuprPu2qRjzUShwMrPZZYGVTUsVnzvoBvuo/...
0
votes
1answer
49 views

Do all the numbers belong to same slot in the Hashtable?

I was reading the CLRS. In the Hashing Chapter on page 262 a statement says: "For example, if we know that the keys are random real numbers $k$ independently and uniformly distributed in the range $0 \...
0
votes
1answer
99 views

Computer Vision Techniques to find Slope of beach in the 2D Images?

What I am planning to do is to calculate the height and estimate the slope of the segmented Object. The camera will be static and the Object of Interest is the slope of the beach. I am finding harder ...
0
votes
1answer
22 views

Convert ((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4) to MathJax? [closed]

I need help coverting these two question to Math Jax ((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4) and (((50^A)(50^B)(50^C))/(4^2)) + (((50^A)(50^B))/(4^2))+((50^A)/(4))+(1/4) I don't know how to ...
0
votes
0answers
22 views

Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
1
vote
0answers
28 views

Accessible CS Math Job [closed]

I am a CS undergrad and a huge enthusiast of pure math. I have been doing competitive programming and proofs for a while. My ambition is to become an academic in theoretical computer science. The ...
0
votes
1answer
17 views

If there is any research on Goal Based Programming (GBP)?

The more I think about programming and optimization, the more I think "why not just specify a goal and have the program figure out the optimal solution to it". I am familiar with basic "optimization ...
-1
votes
1answer
27 views

Intersection algorithim for finding the intersection points of two arbitrary mathematical curves

I'm looking for an intersection algorithm for finding the intersection points of two arbitrary mathematical curves. Websites like Desmos, GeoGebra, and WolframAlpha allow you to graph and/or input two(...
23
votes
3answers
13k views

What is the fastest algorithm for multiplication of two n-digit numbers?

I want to know which algorithm is fastest for multiplication of two n-digit numbers? Space complexity can be relaxed here!
2
votes
2answers
99 views

Being stuck and frustrated with my masters project

I'm doing a masters in CS that requires me to implement from scratch most of the neural network models and because python libraries aren't applicable to what i want. The problem is that i don't feel ...
0
votes
1answer
567 views

Given a set of points in the plane all laying on the axis, find the number of right angled triangles

My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa)...
2
votes
0answers
62 views

Counting triplets from three arrays satisfying the equation x^2 = yz

Let's say I have three arrays of positive integers X, Y and Z. You can assume that each of ...
0
votes
0answers
53 views

Algorithm Analysis - Binary Search Algorithm

The problem is from Data Structures and Algorithm Analysis Edition 3.2 (Java Version) Book from Clifford A. Shaffer. It is from the third chapter exercises, problem number 3.13.20. Below is how it is ...
0
votes
1answer
52 views

Why do we need/use operator precedence for Arithmetic operators?

Why do we use operator precedence rule for Arithmatic operators? Can't we simply just do the operation in a linear manner from left to right or vice-versa and deal with the operator that comes first. ...
1
vote
0answers
39 views

Proof of Fundamental Lower Bound on Regret

Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. Every iteration consists of the player making a ...
5
votes
2answers
108 views

Fermat's last theorem: How to (partially) solve by programs

No three distinct positive integers $a, b, c$ can satisfy the equation : $a^n + b^n=c^n$, if $n$ is an integer greater than two. The above statement, known as the Fermat's last theorem is proven ...
1
vote
2answers
115 views

Find lines segment portions close together

I have two lines segment in 3D space. Lines segment are defined by 2 points each: $A_1$, $B_1$ and $A_2$, $B_2$ (see left part in the below schema). I would a like to find an algorithm to detect ...
1
vote
1answer
152 views

Min-plus matrix multiplication implementation

I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication: One method for doing this is to ...
1
vote
0answers
19 views

Numerical integration of a function

For a particular physical system, the force is given by $$F(r)=-\frac{d\Phi(r)}{dr}=\frac{r^5+2ar^3+a^2r-4a}{r^4(r^3+ar+2a)}$$ where $\Phi(r)$ is the potential energy which can be obtained as the ...
3
votes
3answers
150 views

Are regular languages and their regular expressions part of computer science?

I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular....
0
votes
0answers
33 views

Number of multiplications and additions in the given code

$N:=2^p$ Input: $f \in \mathbb C^N$ 1: $n=N/2$ 2: initialize vectors $f^{(1)}, f^{(2)} \in \mathbb C^n$ 3: $w_N^0=1$ 4: for $j=0,\ldots,n-1$ do 5: $\ \ \ \ \ f_j^{(1)}=f_j+f_{j+n}$ 6: $\ \ \ \ ...
1
vote
2answers
62 views

Dividing 2 integers with some constraints

This a problem i came across while practicing binary search. Here is the problem: Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. ...
1
vote
0answers
31 views

How can I calculate the exponential integral?

(I'm not sure this is the right forum.) I'm writing a program that uses the prime-counting function. Right now, I'm using x/log(x), but I want to switch to ...
0
votes
1answer
78 views

How to model equality in Integer Linear Programming

How to implement v=(a==b) using Linear Programming? $$ v= \begin{cases} True, a=b\\ False, a≠b\\ \end{cases} $$ Until now I tried the big M-Method. To show a≤b: $$a-b+Mv≤M$$ $$-a+b-Mv≤-1$$ To show ...
0
votes
0answers
23 views

Calculating the maxima of a function subject to a constraint

The first figure below shows the plots of a function $f(x)$ plotted for different values of a parameter $\lambda$, i.e., $f(x)=f(x,\lambda=\lambda_i);i=1,2,3,..;\lambda$ is maximum for the topmost ...
1
vote
1answer
29 views

What easy algorithms are there for calculating products of cycle decompositions?

Here is the easy algorithm we are taught for adding two numbers in base-10 notation. We are taught this algorithm in first or second grade. ...
0
votes
2answers
57 views

How many combinations will be generated if below conditions are put?

I need a generalized formula for a set having size(s) having below restrictions, for ex. X = 2,7,11,17,26 I want only the first combination 2+7 & ignore all of the combinations that start from 2+...
2
votes
1answer
44 views

Estimation of the number of solutions by Counting

This is a question from a quantum computation textbook. Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
5
votes
1answer
571 views

How did the Logic Theorist prove the Pons Asinorum?

I was reading about the Logic Theorist proving many of the Whitehead and Russell's Principia's theorems. However, I cannot find any technical explanation on how the program proved those theorems and ...
12
votes
4answers
5k views

Are there any compression algorithms based on PI?

What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence). I've seen recently some prototype of πfs which assume that every file ...
-1
votes
1answer
101 views

Can we find every 216 digit number combination? [closed]

This question popped to my head when I watched Pi where the mathematican told the Jews "Didnt you calculate every 216 digit number allready?" So I want to find every possible 216 digit number ...
2
votes
1answer
40 views

Linear programming IFF with equality constrain

Is it possible to write the following logical constrain in linear programming? Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is $y=...
2
votes
2answers
263 views

Implications of Integral linear program

Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$ Let $(P^*)$ be ...
2
votes
1answer
130 views

Mathematically calculating time complexity

This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject. Also I ...
2
votes
0answers
65 views

Maximizing the product of a set of dot products

So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following: $\prod_{x \in X} b \cdot x$ where the components of $b$ sum to $1$ If it matters the components of ...
3
votes
2answers
1k views

How does a computer interpret real numbers?

I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers. But I want to know how does ...
2
votes
1answer
151 views

Can this equation be solved in polynomial time?

I came across a more general form of this question. Can we find the value of variables in polynomial time ? Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
5
votes
2answers
165 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
0
votes
0answers
54 views

Optimize an underdetermined system with quartic constraints

I encountered an optimization problem which does not belong to any well-known category of optimization. The system has $M$ (typically $M=120$) real variables and $N$ (typically $N=100$) constraints (...
2
votes
1answer
44 views

Interpolate on a cylic x axes

Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y ...
1
vote
0answers
22 views

How can I code an algorithm (concerning networks) [closed]

my question is basic but I want to know how to code algorithms containing maths like this https://web.stanford.edu/~skatti/pubs/sigcomm15-spotfi.pdf , TY for your help !
1
vote
0answers
59 views

Sum of long geometric progression [closed]

Finding sum of a geometric progression is simple when we just need to report the sum, but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me. I have a ...
1
vote
0answers
38 views

How much of the x86 instruction set does blender use? [closed]

I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
0
votes
0answers
41 views

Algorithm for placing objects inside a square from outside to inside

I have a map that is 300x300 units. I have to place squares of 20x20 units inside that map from outside to inside. There are 3 different types of square, the space available inside the map needs to be ...
0
votes
1answer
50 views

Counting the number of multiples of number A that perfectly divides the number B

What is the best way of counting the number of multiples of number A that perfectly divides the number B. This is the sub problem for one of the questions I am solving on codechef. This is the best I ...
0
votes
1answer
250 views

Is there a poly-time algorithm for expanding out polynomials

so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of $$ z = (x+y)(x-y) \implies x^2+xy-xy+y^2 $$ ...
4
votes
0answers
108 views

Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$

We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$. The obvious naive way ...
0
votes
0answers
103 views

What is the time complexity of MATLAB's ode solvers?

Say I have a system that is $n$ differential equations that are all coupled together, over a time interval $[a,b]$ with timestep $t$. Is there a straightforward time complexity for MATLAB's built in ...
2
votes
1answer
69 views

Implementing Gauss–Legendre algorithm using arbitrary-length rationals

I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate. SuperPI computes pi using the Gauss-Legendre algorithm. The Gauss–Legendre algorithm is quite simple, ...