Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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