Questions tagged [mathematical-programming]
Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.
117
questions
0
votes
1answer
475 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
2answers
87 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
0answers
16 views
Automatically detect Object points and Image points from a Single Grid for Camera Calibration?
What is the best generalised algorithm suited for detecting Object points and image points automatically from a single grid image with different line thickness and luminance intensity?
Link defining ...
2
votes
0answers
57 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
51 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
42 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
34 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 ...
1
vote
1answer
67 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 ...
5
votes
2answers
107 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
0answers
18 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 ...
1
vote
2answers
114 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 ...
3
votes
3answers
146 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
1answer
28 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
0answers
32 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
0answers
28 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 ...
1
vote
2answers
52 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.
...
0
votes
0answers
22 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 ...
0
votes
1answer
68 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
0answers
17 views
How to identify a continuous shape and break it into minimum number of rectangles?
The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous ...
1
vote
1answer
26 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.
...
2
votes
1answer
42 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 ...
0
votes
2answers
55 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+...
-1
votes
1answer
87 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 ...
0
votes
0answers
38 views
Need some help implementing backjumping algorithm
I am extending aima csp solver in my project.I have read the AIMA book and the book says Backjumping algorithm can be implemented by with a little modification of Backtracking algorithm.But,I don't ...
2
votes
1answer
35 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=...
0
votes
1answer
63 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 ...
2
votes
0answers
59 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 ...
3
votes
1answer
109 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$ ...
6
votes
2answers
157 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 ...
2
votes
1answer
34 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 !
0
votes
0answers
42 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 (...
1
vote
0answers
54 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
28 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 ...
2
votes
1answer
120 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 ...
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
1answer
62 views
0
votes
0answers
86 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
54 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, ...
1
vote
1answer
33 views
What is the equation for a spiral path in 3D? [closed]
I am developing games in Unity 3D. Currently, I am trying to place 3D objects in 3D space in a spiral pattern that looks like one of 2 the strands in a pair of the DNA (helix) spiral pattern.
Would ...
0
votes
0answers
27 views
Classify manifolds with neural networks
Can a neural network be used to find the genus of a 2-manifold given for instance as a CW complex?
1
vote
1answer
75 views
Balance groups based on average, element constraints and size
It's a complex situation, where I want to balance groups of numbers based on the average of these numbers, while keeping the group size unchanged and not breaking elements constraints.
Let me explain ...
2
votes
2answers
231 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 ...
1
vote
1answer
811 views
Efficient streaming sort
Consider following task: we have an input of N+1 lines, where first line contains N - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id &...
2
votes
1answer
55 views
Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$
Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I ...
1
vote
1answer
19 views
PCA with Bishop's book
I am reading PCA in Bishop's Pattern Recognition and Machine Learning pg. 562, here in Lagrange multiplier but I don't get it in the highlighted: I wonder is it $u_1$ or $u^T_1$?
Your help is ...
0
votes
1answer
74 views
Compute e^x given starting approximation
I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits). The best way I know is to use Taylor polynomials. However, the Taylor polynomial algorithm seems ...
