Questions tagged [algorithms]
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).
0
votes
0answers
11 views
Find all the paths between two nodes in a complete graph, using Dev-C++ .
I wish to find all the possible paths between two nodes in the graph $G$ by using Dev-C++. The graph $G$ is not a complete graph but i mentioned ''complete graph'' in the question above because, once ...
0
votes
0answers
8 views
Unbounded approximation ratio
Suppose that there is a specific instance of a graph for which the approximation ratio of an algorithm polynomially increases with the number of nodes of the graph, say the approximation ratio is $n^2$...
0
votes
1answer
39 views
An algorithmic puzzle(modular arithmatic)
A car moves from point $A$ to point $B$ at speed $v$ meters per second. The action takes place on the $X$-axis. At the distance $d$ meters from $A$ there are traffic lights. Starting from time $0$, ...
0
votes
1answer
37 views
Traffic light problem
A car moves from point A to point B at speed v meters per second. The action takes place on the X-axis. At the distance d meters from A there are traffic lights. Starting from time 0, for the first g ...
0
votes
0answers
18 views
Sampling distribution output does not look like a continuous function
I made a random distribution using 2 dice rolls, the output usually collects most data around mean:
Then I try to do sampling of N sample size. While using sample size of N = 2 it looks more or less ...
0
votes
0answers
12 views
Proof of equivalence of S-TSP solution with TSP solution (metric instances)
I am wondering where could I find proof for following S-TSP to TSP transformation.
S-TSP (Steiner Travelling Salesman Problem) def: Let $G=(V, E)$ be a non-directed weighted graph. Let $V' \subset V$ ...
2
votes
1answer
49 views
Prove that $ \left \lfloor {\log n} \right \rfloor = \left \lfloor {\log \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor + 1$
We have been doing algorithm analysis in university, and after analyzing binary search algorithm, the following equation resulted. What we have to do now is to prove that $ \left \lfloor {\log n} \...
0
votes
1answer
27 views
A specific and interesting recurrence relation
Let f and g be increasing functions such that the sets {f(1),f(2),...} and {g(1),g(2),...} partition the positive integers. Suppose that f and g are related by the condition g(n)=f(f(n))+1 for all $n&...
1
vote
2answers
35 views
Numerical Integration: Three-term Gaussian Quadrature not giving correct answer
I'm using a 3 term Gaussian Quadrature method to integrate
$\int^{1.3}_{0.75} (sin(x)-1)^2$
I have implemented this using Matlab/Octave through the following code:
...
0
votes
0answers
17 views
What is known about optimizing a cost function $C$ over a Markov Chain steady state distribution?
Suppose I have $N$ (very large integer) states $S=\{s_1, ..., s_{N}\}$. Suppose we also have a cost for each state $C:S\rightarrow \mathbb{R}$.
For every pair of states $(s_i, s_j)$, the pair form ...
2
votes
2answers
52 views
Finding the floor of $\sqrt{d^2-1}$
If we are given $d$ an integer, then I've seen it written that the floor of $\sqrt{d^2-1}=d-1$, but how is this found?
It's not immediately obvious, at least not to me.It makes me feel there must be ...
0
votes
1answer
17 views
How can I choose the highest resulting combination out of arbitrary sized chunks, worth an arbitrary amount each
I am given a set of companies that each want to buy my product in different sized chunks. I have a maximum of 28 Million units to sell and each company pays a different amount of money for their order....
0
votes
0answers
27 views
How we can determine the coordinates of rectangle?
Give the center of the rectangle and their sizes h and w respectively and the $\phi$ angle created by h and Oy. How to determine the coordinates of the rectangle.
For example: we have the coordinates ...
1
vote
1answer
53 views
Unexpected values returned by C++ noise generation functions
I'm porting the C++ libnoise library into another language. While doing so, I came across a function which appears to return inappropriate values, at least according to the original documentation from ...
0
votes
0answers
23 views
How we can determine coordinates of robot aftering some operations?
Initially, Robot is placed at $(0,0)$ and towads the positive direction of the axis $Oy$. How we can determine coordinates of Robot after some operations, where operations have form: $r\text{ }\phi(-...
3
votes
1answer
33 views
Labeling nodes in a bipartite graph to satisfy edge constraints
I'm trying to find an algorithm for the following problem. Let $G$ be a bipartite graph. The edges in $G$ have labels $R$; each label $R(u, v)$ is an integer range $[a, b]$ with $a$ and $b$ being ...
0
votes
1answer
89 views
dynamic programming - recursion
We have $n$ requests to plant trees. Each request comes with a position $p_i$ which means we have to plant the tree $p_i$ meters away from a specific constant point. Also, there should not be another ...
2
votes
0answers
44 views
Number of partition of $n$ into sum of three squares, needing fast algorithm
Does anyone know how to find number of partitions of $n$ into sum of three squares with asymtotic time complexity faster than $O(n)$ ?
I found some info on https://oeis.org/A000164, but there are an $...
1
vote
1answer
42 views
Finding the Elements from a list which average to a Known Number
I apologize as I am very new to this so my question may not be written very well/formally.
What I am trying to do is find which numbers out of a known list would average to a given number.
Say the ...
0
votes
1answer
33 views
How many unlucky numbers in segment $[a;b]$
Some numbers are called unlucky if their decimal representation contain number $5$.
For example: $123456,245,1555$ are unlucky numbers and $111,123,147$ are not unlucky numbers.
In how many unlucky ...
0
votes
0answers
18 views
How to find quantity of cyclical sequences of ordered pairs with permutation between adjacent pairs defined
I have manually identified possible combinations for a small set I have been working with and I'm not sure if I have overlooked some valid options. I would like to be able to calculate the quantity of ...
0
votes
1answer
12 views
Uncountable many monomial orders for monomials with 2 variables
Why do we have for monomials with two variables x1, x2 uncountable many monomial orders?
I could prove that the order defined by
$x_1^ax_2^b ≤ x_1^cx_2^d$ is a monomial order if and only if
$a + b\...
-3
votes
0answers
25 views
Algorithm for scoring/grading app
I'm building an application that assesses one's health by asking a series of questions. For example:
On average, how many hours did you sleep each night during the past 4 weeks?
Less than 5 hours
5 ...
0
votes
1answer
11 views
Algorithm Complexity - Summation - Correctly interpreted how to do it.
I wanted to double check my understanding and working out for a 3 nested for loop algorithm, and working out it's complexity. I've got the right answer, but how I've arrived at it I feel isn't exactly ...
0
votes
0answers
16 views
Finding GCD of a subset of a range given GCDs of first element to lower and upper bound
Given a range $a_1, a_2, ...., a_n$ and given values $x = GCD( a_1, a_2, ....., a_i)$ and $y = GCD(a_1, a_2, a_3, ...., a_j)$
where $i < j$
Is it possible to then find the value of $GCD(a_i, ..... ...
3
votes
0answers
33 views
Looking for scientific papers about lotteries
Do you know any paper focusing on the statistical science and math behind lottery and number guessing games? I am creating a new one, where the winning numbers are known in advance, and the gain is ...
0
votes
0answers
17 views
Estimating features on large, unweighted, hypercubic graph
I'm trying to find methods for estimating graph coefficients (ideally coefficients like betweenness and closeness centrality) for a graph which is so large as to be computationally intractable for the ...
1
vote
0answers
20 views
differences between Gale-Shapley stable solutions
I'm looking for the properties of the man-optimal and women-optimal stable solutions of the Gale-Shapley algorithm. I found dozens of references proving that depending on which side proposes, one gets ...
3
votes
2answers
57 views
Compute $ \lceil{log_2(n)}\rceil $ through basic arithmetic operation
first explain me my motivation:
I need to write a RAM program which compute $ \lceil{log_2(n)}\rceil $ for $ n \in \mathbb{N} $.
Idea
If I have $ n = $ "power of two" ( for example $ 8 = 2^3 $). I ...
1
vote
1answer
46 views
Writing the Dijkstra Algorithm in Mathematics
I would like to know about writing the Dijkstra Algorithm properly and efficiently using mathematical notation, which may simplify the process to writing the proof. Assume that the graph is unweighted,...
0
votes
1answer
19 views
page rank algorithm iterative conversion
I am trying to implement a pagerank algorithm using the formula:
p = the probability vector og getting on a page
Pbeginning = matrix(n,1) full with 1/n
S = the matrix with damping factor of the ...
0
votes
1answer
16 views
Heapsort using MaxHeap and MinHeap
As I read in Introduction To Algorithms [3rd edition]:
MaxHeap is used to sort an array into ascending order, while MinHeap is used to sort an array into descending order.
And the tree below can be ...
0
votes
1answer
14 views
Asymptotic Notation - Linear Search
Among, Big-O, Big-Omega and Big-Theta, Indicate the efficiency class of a linear search.
The best case (Big-O) for a linear search would be, 1 (or constant) because the item being looked for, could ...
0
votes
0answers
13 views
Can a function be upper bounded by itself? [closed]
Upper bound for a function , $f(n)$ is another function $g(n)$ such that $f(n) <= cg(n)$ for some positive $c$ and $\forall$ n > $n_0$. Let f(n) be $n^2 - n$, then can g(n) also be $n^2 - n$ , as ...
1
vote
1answer
48 views
Generating all possible Domino tilings on a $4 \times 4$ grid
I have a task to write a program which generates all possible combinations of tiling domino on a $4 \times 4$ grid. I have found many articles about tilings, but it is for me quite difficult and I ...
0
votes
0answers
48 views
Does there exist a foolproof indefinite integration process?
I've been searching for this for sometime now & the best I've found are computer oriented algorithms (typically relying heavily on reference arrays & thousands of stimulus/action rules).
...
-2
votes
5answers
62 views
Square root without a calculator algorithm [duplicate]
Out of curiosity I'm trying to find an effective algorithm to find the value of a square root of a number(a) without a calculator. I'm trying to find a solution without searching it up.
What I have ...
-1
votes
2answers
45 views
How do I solve the for the base of an exponential modular arithmetic equation? [closed]
The question is:
$$10 \equiv M^5 \mod{35}$$
How do I isolate and solve for $M$?
1
vote
1answer
42 views
Intuition for the “Wavy Curve” method for Rational Inequalities
I am studying inequalities and I saw this method by the name of Wavy Curve method. Since it was listed as an algorithm, I wanted to know its mathematical formulation. I could only see two part of this ...
3
votes
1answer
61 views
Relation between sorted weights of spanning tree and minimal spanning tree
Let $ G=(V,E) $ be a graph, $T$ a minimal spanning tree for $G$ and $T'$ some spanning tree of $G$.
Let us denote:
$w_1\leq w_2\leq ... \leq w_{n-1}$ the weights of $T$
$w'_1\leq w'_2\leq ... \leq ...
0
votes
0answers
18 views
Fill a surface with cuttable tiles
I have a problem that I have a surface. The surface can be of random shape. There can be holes at random places at the surface. I need to fill the surface with rectangular tiles of a fixed size (...
0
votes
0answers
13 views
What is an algorithm to determine when two sentences in predicate logic are equivalent?
Are there references for algorithms which can determine whether or not two sentences in predicate logic are equivalent?
For instance, if we have some domain $D$ and predicates $P,Q$ defined on $D$, ...
6
votes
1answer
114 views
Minimal number of questions to identify a subset
This is a curiosity question.
Recently I stumbled across the following problem :
Given three integers $k,m, n$ such that $m+k\leq n$. A friend chooses a subset $S\subseteq\lbrace1,\ldots,N\rbrace$...
0
votes
0answers
15 views
Use of weights in Dijkstra algorithm
In Dijkstra algorithm, what is the use of weights(distance measures) preassigned to edges? Why cant we just update the distances of vertices by using path length data structure? I think it is ...
1
vote
1answer
45 views
Check if an array contains duplicates [closed]
Check if in array contains duplicates in $O(1)$ space complexity and $ O(n)$ time complexity.
Examples:
...
0
votes
1answer
34 views
Generalizing this flashlight puzzle
My friend told me a riddle yesterday: four people want to cross a bridge. They each will take $1$, $2$, $5$, and $10$ minutes respectively to cross the bridge. They can go across the bridge in groups ...
0
votes
1answer
454 views
Dynamic Programming: Largest Number of Dams that can be built
Because of the recent droughts, $N$ proposals have been made to dam the Murray river. The $i$-th proposal asks to place a dam $x_i$ meters from the head of the river (i.e., from the source of the ...
0
votes
2answers
382 views
Network Flow: Algorithm to find a cut of smallest capacity among all cuts
You are given a flow network $G$ with $n > 4$ vertices. Besides the source $s$ and the sink $t$, you are also given two other special vertices $u$ and $v$ belonging to $G$. Describe an algorithm ...
1
vote
1answer
49 views
Find all integer solution of the equations
I have an equation $$xy^2 + (x^2 + 1)y + x^4 + 1 = 0$$ and I need to find a set of solutions for it in integers. I tried to solve it using Maple with the isolve () ...
1
vote
1answer
26 views
Algorithm to isolate a variable in an arithmetic inequality
Simple Question
I'm looking for a algorithm to isolate a single variable in an inequality.
Context:
Consider the following grammar for writing inequalities:
...
