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
9 views
Algorithm: All-pair graph traversal in groups of 4
My question is based on this puzzling SE post.
Let me reword it as best as I possibly can.
There are 32 students that will be taking a test which consists of 32 questions, each question worth 1 ...
2
votes
3answers
34 views
Why is $ \sum_{k = 1}^{n - 1}O\left( \binom{n}{k}k^2 \right) = O(n^22^n)$?
In the analysis of an exact dynamic programming analysis for the Travelling Salesman problem in Exact Exponential Algorithms by Fomin and Kratsch, it is stated on p. 6 that
$$ \sum_{k = 1}^{n - 1}O\...
0
votes
0answers
13 views
given a system of N linear equations, Is there an algorithm that can find a solution that solves the most number of equations in this system
My apologies if this question makes no sense; I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this- for this particular case, this algorithm ...
0
votes
0answers
16 views
Network Optimization [on hold]
Suppose that after solving a shortest path problem, you realize that you underestimated some arc lengths and overestimated some other arc lengths. The actual arc lengths are c'_ij instead of c_ij for ...
1
vote
0answers
20 views
Division on a real quadratic ring of integers.
I've seen that $\mathbb{Z}[\varphi ] = \mathcal{O}_{\mathbb{Q}_{\sqrt{5}}}$, where $\varphi$ is the golden ratio, is a Euclidean domain with norm $N(x + y\varphi ) = x^{2} + xy - y^{2}$.
Given a ...
0
votes
1answer
44 views
Divide and conquer: Why $F(0) = 0$? [on hold]
Reading algorithms. Fibonacci example.
I saw an example where it said $F(1) = 1$ and $F(0) = 0$. (Fibonacci)
Why $F(1) = 1$ and $F(0) = 0$? From where does it originate?
Thanks.
0
votes
0answers
15 views
Calculate row (y) based on given height
I am trying to solve mathematical problem.
I want to find a pattern for getting correct row based on current height of mouse position (height in local system of coordinates). I have written on paper ...
0
votes
0answers
20 views
Pandigital Numbers Exceeding a Ratio
The problem is described in here: Define a number to be pandigital if each digit from $0$ to $9$ appears in its representation at least once. We want to find the least number $n$ such that the ...
0
votes
0answers
21 views
First-Visit vs Every-Visit Monte Carlo
I have recently been looking into reinforcement learning. For this, I have been reading the famous book by Sutton, but there is something I do not fully understand yet.
For Monte-Carlo learning, we ...
0
votes
1answer
22 views
Simple Analytical Function
Why is the following not a SAF? It applies the exponent a finite numer of times.
Which rule is it violating?
2
votes
1answer
30 views
Calculation cube root by hand using division method, not working for $\sqrt[3]{4} $
I have been studying the division method to calculate cube roots by hand (in preparation for an exam in which one is not allowed to use a calculator).
This division method for calculation of cube ...
1
vote
1answer
26 views
How many number of integer coordinates exists between a line segment, including the end points?
There is a line segment say $AB$ with coordinates of end-points as $A=(x_1, y_1)$ and $B=(x_2, y_2)$. $x_1, y_1, x_2, y_2$ are integers. I need to find the number of integer coordinates which lie on ...
0
votes
1answer
35 views
dead simple arbitrage algorithm
When googling for a solution to the currency arbitrage problem, a variant of the Bellman-Ford algorithm comes up as the most efficient solution. See for example this page or this stackexchange post.
...
1
vote
0answers
37 views
Algorithm for Union of Polychora (4D Polytopes)
In the course of my research (radio engineering), I need to solve the following problem, for which I do not feel well equipped.
I would like to calculate the union of polychora (4-polytopes, bounded ...
1
vote
2answers
26 views
Expressing the upper bound to $f(n) = n * log(n)$ as a polynomial
In order to do a recursive algorithm analysis, I'm applying the master theorem. As part of that, I'm looking to find a value for $\epsilon$ so that $n \log{n} = O(n^{2-\epsilon})$.
Now, intuitively, ...
1
vote
0answers
16 views
Given specific of an iterative code prove it with program correctness
(a) Given an appropiate loop invariant
(b) Use your loop invariant from (a) to prove partial correctness (when loop terminates)
(c) Define an appropriate expression for the purpose of proving ...
-1
votes
0answers
20 views
Prove that if $f(n)$ and $g(n)$ are two non-negative functions,then $\max (f(n),g(n)) = \Theta (f(n)+g(n))$ [on hold]
If $f(n)$ and $g(n)$ are two non-negative functions, then $\max (f(n),g(n)) = \Theta (f(n)+g(n))$
0
votes
0answers
9 views
pocs vs conjugate gradient.
I am just wondering in general, how does conjugate gradient vs pocs (projection onto convex sets) in terms of approaching the true solution?
I am doing simulation, but I would really like to have ...
0
votes
0answers
13 views
Describe an algorithm for fastest run time [on hold]
You have a list of n signal measurements from a radio telescope. Each measurement is a single integer (a measure of signal energy). You want to find the k measurements of highest energy in the hope ...
1
vote
0answers
40 views
$L = [1,2,3,4,5,6,7]$ is a list of integers, return the maximum sum of any adjacent pair of integers in L
Given this specification, what gets returned?
Precondition: L is a list of integers, len(L) > 1.
Postcondition: Return $max_{0<k<len(L)} \{L[k-1]+L[k]\}$. I.e., return the maximum sum of any ...
0
votes
0answers
13 views
recursive program correctness proof for $n^2$
let $k \in \mathbb N$, we define the predicate $Q(k)$ as follows
$Q(k)$ let $n \in \mathbb N$ and let $k = n$, then $SQUARE(n)$ terminates and returns $n^2$
Will use pci to prove
Base Case: let $k =...
0
votes
1answer
16 views
Bit flipping algorithm implementation or psuedo-code
I am trying to understand and implement Bit flipping algorithm
Can someone share the psuedocode for the algorithm and explain in detail? I cannot understand the answer.
I also want to understand ...
1
vote
1answer
22 views
Asymptotic Problem Complexity = Infimum of Asymptotic Algorithm Complexities?
When talking about the complexity of algorithms and problems, the complexity of a problem is the infimum of the complexities of the algorithms that solve the problem.
My question is:
Is the ...
1
vote
1answer
104 views
Matrix filled with 0's and 1's
A matrix of size $n \times m$ filled with $0$'s and $1$'s and this matrix is considered lucky if no two adjacent cell are same i.e.,( no adjacent two 0's or 1's together ) so, we can invert some ...
3
votes
1answer
35 views
Maximal disjoint sets in a list
Given $A = [[4, 10, 14], [5, 13, 14], [2, 7, 13], [0, 2, 12], [2, 4, 11], [3, 5, 11], [3, 7, 10], [6, 9, 10], [0, 1, 3]]$ is a list of sets. I want to find the maximum number of sets from the list ...
0
votes
0answers
41 views
Ways to fill n x n matrix with 1 and -1 so that there is only one 1 and one -1 per row and column and the sum of each row and column is 0
I'm looking for a technique to find all possible ways to fill n x n matrix with following rules: There can only be one -1 and one 1 on each row and column. The sum of every row and column has to be 0. ...
0
votes
2answers
58 views
Finding a formula for a sequence or proving it is impossible [on hold]
I tried to search for a formula that produces the following sequence:
35
49
55
65
77
85
91
95
115
Etc, a larger sequence is in the following link:
https://pastebin.com/HDDHe7bz
Or proving that such ...
1
vote
1answer
28 views
Problem that is very compute-intensive but also has a good approximated solution?
For my work I'm looking for good examples of problems that are very compute-intensive and at the same having good and fast approximated solutions. Could you give me some examples?
I'm unsure if this ...
1
vote
1answer
24 views
Recursive program correctness proof of a simple python program that returns (x + y).
For $k \in \mathbb N$ we define $Q(k)$ as follows
$Q(k): $ let $x, y \in \mathbb N$ and $x$ is a multiple of $3$ and $k = x + y$, then $FUN(x, y)$ terminates and returns $x + y$
I will prove $Q(k)$ ...
0
votes
1answer
15 views
Algorithm for modifying graph with negative cycles to be able to conduct Floyd-Warshall
Just putting it out there, this is a homework question but I wanted to get a second opinion on my thoughts to see if my thought process was right.
Say we have an undirected graph G = (V,E). We know ...
0
votes
1answer
30 views
How to create subsequences from a set of ordered integers given the specified constraints.
Given, for example, the following set of integers $\{1,2,3,4\}$, how can you compute the number of all possible sequence scenarios, where a scenario consists of a number of sequences, as following ...
-1
votes
0answers
20 views
Find a line in 3D which has minimum property
Given N lines in the 3D, I need to give algorithm which solves the following:
Find a line L such that:
Let $l_1, l_2, l_3,...,l_N$ be the N lines.
Let $d(l_i, L)$ the distance between $l_i$ to $L$.
...
2
votes
2answers
32 views
Find element of multiplicative group such that its order is $n$
Is there an efficient algorithm that given an integer $n$, it finds any $a$ and $p$ such that $a$ has order $n$ in $(\mathbb Z/p\mathbb Z)^\times$?
$n$ may be moderately large, say ~$10^5$.
If it ...
0
votes
0answers
21 views
Finding position for insertion of an element in Max Heap using binary search
I am struggling with the following question:
Consider the process of inserting a new element into a given max-heap $A$. The new element is firstly placed as the last leaf node (say $x$) in the ...
1
vote
0answers
15 views
Procedure to generate 2-dimensional convex polytopes with a given number of vertices
I need to deal with the following.
Let $[B]$ denote the set of integers $\{0,1,\ldots,B\}$.
Consider an integer $n \geq 3$ and a grid $[B]\times [B]$, and let $P_{n,B}$ denote the set of convex ...
0
votes
0answers
11 views
Are there a formula to give index of each element after ordering permutation if we know permutation number?
Suppose we have 3 unique elements, let give each element its own index 0,1,2
It can be reorder into 3! permutation which is 6 ways to order this list. And each one of permutation can be given a ...
0
votes
0answers
42 views
How to solve a $10$ degree Polynomial? (without using the normal tricks)
The problem specifically is a $x^{10}$ polynomial over $x^9$ polynomial that we have to graph.
To graph, we need to find all the vertical intercepts so both polynomial need to be factored.
Is there ...
0
votes
0answers
16 views
Big O in Rademacher
Theorem 2 of these notes states:
Let $G$ be a family of functions mapping a set $Z$ to the unit interval $[0,1]$. Suppose that a sample $S$ of size $m$ is drawn according to distribution $D$ on $Z$. ...
5
votes
3answers
46 views
Why can't set cover be reduced to min-cost max-flow?
Okay, so I know obviously I'm making some kind of easy mistake here, since set cover is NP-complete and min-cost max-flow is in P, but I can't figure out what the mistake is.
So, given a universe $U$ ...
0
votes
0answers
19 views
How to efficiently find the number of coprime pairs such that none of the pair elements belong to the same group?
I have 'n' number of positive integers. I want to find the number of coprime pairs such that none of the pair elements belong to the same group.
For example, if my number sequence is ...
0
votes
0answers
33 views
About Simplex method in Introduction to Algorithms (CLRS)
I am reading "Introduction to Algorithms 3rd Edition" by CLRS.
I think it is obvious that $28$ is the optimal objective value from the objective function $z = 28 - \frac{1}{6} x_3 - \frac{1}{6} x_5 - \...
1
vote
0answers
25 views
How to rewrite an expression in order to have the result a multiple of X?
I'm a programmer and need to create an algorithm that takes any expression and rewrite it in a way that the final result is a multiple of a specific value X.
For example, let's consider that i need ...
0
votes
1answer
26 views
Program Algorithmic time
Just a simple question to get the total time to do a particular program or calculate Big O of the function
Lets say I have an n x n array
x = 0, y = 0
for i = z to n:
x = i + 1
y = i - 1
C[i][i] ...
1
vote
1answer
64 views
How to maximize the total auction price for a set of bids subject to bidder constraints
I want to auction a set of ASSETS (A) and fetch the maximum total price. The bidding is simultaneous and works as follows.
Say I have a collection of BIDDERS (B) who, individually, bid to purchase a ...
-2
votes
1answer
18 views
Calculate exchange rate including fees
Let's say I exchange 10 USD to EUR. For example 1 USD = 0.78 EUR. So, exchange rate is 0.78.
In this case: 10 USD = 7.8 EUR.
I also take a fixed service fee, e.g. 0.5 EUR. Fee is the same for any ...
2
votes
0answers
80 views
Any process for solving more complex nonlinear Diophantine equations such as $(8+3n)m = 11$?
Is there any known process for solving nonlinear Diophantine equations such as the ones below?
$(8+3n)m = 11\;\;|\;\;n \in \{0,1\},\;m\in \Bbb Z^+$
$(5+(7+3x+2y)a+3z)b = 30\;\;|\;\; x,y,z \in \{0,1\},...
0
votes
0answers
39 views
Simplifying $\sum_{i=0}^{\log n} \frac{n}{\log\left(\frac{n}{2^i}\right)}$
$$\sum_{i=0}^{\log n} \frac{n}{\log\left(\frac{n}{2^i}\right)}$$
I'm having trouble seeing how this summation simplifies.
It seems it would be something like:
$$\frac{n}{\log(n)} + \frac{n}{\log\...
1
vote
1answer
28 views
Heuristic/approximation solutions to Route Inspection/Chinese Postman problem
The Chinese Postman Problem or Route Inspection Problem on a graph $G$, finds a single path that traverses every edge of $G$ with the minimal possible number of edge repetitions.
The trivial ...
0
votes
0answers
30 views
Groebner Basis calculation for degree 2 polynomials
Gröbner Basis calculation on degree 1 polynomials, namely linear combinations of variables, is the same as Gaussian Elimination, which has a straightforward $O(v^3)$ algorithm: each variable is ...
1
vote
1answer
41 views
Algorithm that check if given undirected graph can have Eulerian Cycle by adding edges
Assume that G is a connectable undirected graph, what is the best algorithm in terms of complexity, that check if graph G can have an Eulerian cycle by adding edges?
I thought of their two cases
G ...
