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
What is known about representing numbers as their modulo of successive prime numbers?
Let's define $P_i$ as the $i$th prime number, and $π(i)$ as the number of primes up to $i$. Then, each positive natural number $n$ can be uniquely represented by $[n \bmod P_i \,\mid\, i \in \Bbb N, i ...
0
votes
1answer
18 views
Algorithm Analysis - runtime
Suppose that you have to choose between three algorithms A1, A2 and A3 for a given problem. The worst-caserunning time for each algorithm is given by:
$W_{1}(n) = 100_{n}$; $W_{2}(n) = {2n}log_{10}...
-1
votes
0answers
16 views
Getting Started with Algorithm Trading [on hold]
I was curious if it is feasible and worth my time/money to build a trading platform using external APIs and libraries or is it easier to use something like TD Ameritrade. In other words, are there any ...
0
votes
0answers
13 views
A good way to update prices dynamically based on purchases [on hold]
I'm selling 3 items and I want a way to let the market determine the prices.
I'd like to start all items at the same price, say $40.00, and then at intervals of 1 day, I'd like to update the prices ...
0
votes
2answers
58 views
How to get a closed form for $\sum_{i=1}^n \frac{3^i}{2^i}$ [duplicate]
How can I get a closed form for:
$$\sum_{i=1}^n \frac{3^i}{2^i}$$
I have just started studying closed forms for summations and I am still lost on this matter so I would appreciate if you guys could ...
0
votes
0answers
12 views
What is the min/max number of leaves/non-leave nodes in B+ tree?
Let $n=100$ be the order of a B+ tree which is represents $10^4$ unique values (e.g. primary keys in a database). What is the minimum and maximum number of leaves and non-leave nodes in the tree?
...
1
vote
1answer
30 views
How to determine the faces of an array of points?
Is there a way of determining the faces of any polyhedron?
I have an array of $3$-dimensional points and no information what polyhedron should come out.
0
votes
0answers
8 views
Sub-quadratic algorithm for finding the intersections between two sets of spherical arcs
Is there an algorithm that can find the intersections between two sets of spherical great-circle arcs (on the same sphere) with an worst-case runtime complexity better than the $O(n × m)$ brute-force ...
0
votes
0answers
31 views
Generalization of Captives Wearing Hats puzzle
I have been playing with the following puzzle on and off for a few years, but I haven't been able to address this particular generalization.
Background
This problem is somewhat involved, so it's ...
2
votes
0answers
39 views
Finding the Dictator in Arrow's Impossibility Theorem
Arrow's Impossibility Theorem states that if we have at least three different social states and a finite number of individuals (voters), any social welfare function that satisfies the conditions of ...
1
vote
2answers
32 views
O(g)O(n) + O(f)O((logn)^5) = O(n^5), is the following statement true or not? [on hold]
Given that $f = O(n^2)$ and $g = O(n^4)$, I'm not able to conclude if the above statement is true or not, that's to say, if we can say that :
$$ O(g)O(n) + O(f)O\left(\log(n)^5\right) = O\left(n^5\...
0
votes
1answer
30 views
Binary matrix with columns sums equal to an array numbers, with unique rows sums
I have this input array:
[5, 3, 2, 4, 1, 3, 4]
and want to build binary matrices where sums of each column equal to the coresponding input array elements.
The ...
0
votes
0answers
27 views
Optimisation Problem: Given some data calculate the correct value
I have a real world problem that I would like to solve. I think this problem is an optimisation one. But I am not sure, and I have never work with optimisation algorithms or formulas.
I have 8 ...
2
votes
1answer
22 views
Restricted query problem
I am considering a problem which seems very classic but have no idea where to find the related results. Any help or comment will be appreciated.
Given a non-empty set $S$, a set $Q$ of the subsets of ...
0
votes
0answers
20 views
Generating an Algorithm
So I want to have some kind of number geenrator for the following idea that I have and it goes:
Problem: For each event $A,$ a single worker $X$ gains some distinct number of points. The points will ...
0
votes
0answers
9 views
Acceptance rejection with Halton sequence as random number generator
I am coding various normal random variable generators, one of them being the acceptance rejection method:
...
-1
votes
1answer
16 views
Algorithm to find a maximum weighted forest [closed]
Given a graph G(V,E), with negative weights.
- How to find a maximum weighted forest on G, and how to prove that if all weights are positive the result is a tree.
2
votes
0answers
21 views
Looking for name of combinatorial problem- Permute rows and columns to minimize distance to target matrix
I am trying to find a solution (or algorithm) for the following combinatorial problem:
Given an input matrix and a target matrix, find a permutation of the rows and permutation of the columns that ...
0
votes
0answers
32 views
Algorithm for cliques in weighted graph
Is there a known algorithm (besides brute force) for the following problem:
We have given an edge-weighted complete graph $G$ and a finite set of natural numbers $A = \lbrace n_1,\ldots,n_k \rbrace$ (...
5
votes
1answer
64 views
Sharing a pie evenly among an unknown number of people. [duplicate]
This is a question inspired by the question "Nine gangsters and a gold bar" on the Puzzling Stack Exchange.
Suppose you're throwing a party, and you know that either 7, 8, or 9 people will arrive. ...
3
votes
1answer
72 views
Fast Evaluation of Multiple Binomial Coefficients
Suppose we have a sequence of binomial coefficients.
$$
S = \left\langle \binom{5}{2}, \binom{5}{3}, \binom{6}{3}, \binom{17}{14}, \binom{19}{15} \right\rangle
$$
How can we efficiently evaluate all ...
0
votes
0answers
12 views
Assignment with pair-wise constraints
Consider the assignment problem where we have two groups $u = {1, \ldots, n}$ and $v = {1, \ldots, n}$. The task is to assign each of the elements of $u$ to one and only element in $v$, such that the ...
5
votes
2answers
67 views
Random graphs with a hamiltonian path
Suppose we randomly choose a graph with $n$ vertices in the following manner: each edge is included with probability $\frac12$. Thus, each graph has the same probability of being chosen, and there are ...
2
votes
0answers
32 views
polynomial representation of binary in computer memory and its efficiency
I have noticed that in some cases 'polynomial representation' of a number is the preferred method to represent numbers in computer programs, especially those involving modular arithmetic and ...
1
vote
0answers
22 views
LLL Reduction Conditions
I'm looking to generalise the LLL algorithm to certain number fields. However, I have a few questions regarding the definition of a set of LLL reduced basis vectors:
I understand that $|\mu_{ij}|$ (...
2
votes
1answer
36 views
How can i distribute the money in the fewest movements? [closed]
I am trying to evenly distribute the total amount to each person involved.
For example I will use money.
Example 1
Person A has $20
Person B has $40
Person C has $60
So to make everything even ...
0
votes
0answers
12 views
expected number of probes for a search miss in a given hash table using linear probing
$m$ is the size of the hash table and $n$ is the number of entries in the hash table.
We assume the hash function uniformly and independently distributes the keys among the values $0$ to $m-1$.
In ...
2
votes
2answers
22 views
Calculate matrix powering given one outer product: $(x\cdot{y}^T)^k$
It is an exercise on the chapter one of a book. Book: "Matrix Computations 4th edition" by Golub and Van Loan.
It reads: Give an $O(n^2)$ algorithm for computing $C=(x\cdot{y}^T)^k$ where $x$ and $...
0
votes
0answers
22 views
Multiply large numbers by dividing them into 3 (Karatsuba with n/3 size)
I was solving some problems related to Karatsuba, when I came across a problem which says, how many multiplications would you need to multiply a large number divided into 3 smaller ones like this:
a =...
3
votes
2answers
52 views
Proving greedy algorithm for largest permutation with at most K swaps
Let's see the following statement:
Given an array with the first N natural numbers in any order perform at most K(non-negative) swaps in order to obtain the largest possible permutation.
For making ...
8
votes
1answer
95 views
Maximize the trace of a matrix by permuting its rows
I have been struggling with a combinatorial problem that eventually translates to the following:
Given an $n \times n$ nonnegative matrix, find a permutation of the rows that maximizes the trace.
...
1
vote
1answer
34 views
Given a hyperbola, determine whether any of its points lie within $\{x\in [0,1]\mid 0\leq y\leq 1\}$
Given
$$
y=\frac{c_1 +c_2x}{c_3+c_4x}
$$
Is there any test using the values of $c$ to see if between $x\in[0,1]$ there is at least one point where $y\in[0,1]$ other than just evaluating the function ...
12
votes
9answers
4k views
Is there a mathematical notation for “repeat $X$ until $Y$”?
The repeat X until Y methodology is a key component of many algorithms. Yet, I haven't come across a good mathematical notation for it. (Perhaps because it is of ...
0
votes
0answers
60 views
Where can I learn mathematical style pseudo code?
Some algorithms represented with the mathematical notations in some research papers, books, documentations. These expressions seem a little bit confusing.
For example :
...
0
votes
0answers
27 views
Boolean circuit
Is it, in the definition of Boolean circuit, allowed that some input gates are not labeled variables but by constants from $\{0,1\}$. I somehow need that this issue is explicitly stated.This may be ...
5
votes
2answers
68 views
Pigeonhole principle based algorithm
I was trying to solve this problem.
http://olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2016/09/inmosol-15.pdf
INMO-2015 P6. From a set of $11$ square integers, show that one can choose ...
0
votes
1answer
24 views
“Reverse Clustering” Algorithm?
The clustering algorithm splits points into disjoint sets in a way that minimizes the intra-set distance.
Is there an efficient algorithm which does the opposite (maximize the intra-set distance)? I....
0
votes
0answers
23 views
How do I determine when an optimal solution is found in an auxiliary linear program?
The linear program to be solved after converting to auxiliary and slack form:
$$z=-x_0$$
$$x_3 = 4 − x_1 − 2x_2 + x_0$$
$$x_4 = −12 + 2x_1 + 6x_2 + x_0$$
$$x_5 = 1 − x_2 + x_0$$
The final slack form ...
2
votes
0answers
43 views
Proof that my greedy algorithm for assigning candidates to jobs works
I was using the answers on this question as a guide for proving that my greedy algorithm is correct. (Unfortunately, CS Stack Exchange does not accept proof verification questions, which is why I ...
2
votes
2answers
58 views
Calculate the last digit of $a^{b^c}$
I'm doing some programming challenges, and I have to find the last digit of the result from evaluating the expression $a^{b^c}$. The unit tests of this challenge feature very big integers, so ...
0
votes
1answer
21 views
Directly proportional realtoinship between power consumed and time taken by computer system.
Suppose there is a computer system that performs some specific event in multiple iterations and requires some amount of power and time for each iteration to be calculated. At every iteration system ...
1
vote
1answer
60 views
For each edge in a tree, counting paths passing through this edge
I have a tree and for its each edge, I want to know the numbers paths passing through this edge.
For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (...
0
votes
1answer
30 views
How to interpret second order Runge-Kutta Method?
I am reading about the Runge-Kutta method in Numerical Recipes, they start with the Second-Order Runge-Kutta Method and give the following equations
$$[1] \;\;\; k_1 = h \; f^{'}(x_n,y_n)$$
$$[2] \; \...
1
vote
3answers
57 views
Formula or Algorithm to Draw curved lines between points
I'm developing a script to connect point with curved lines.
The points are in ascendent order in x-axis like this:
I'm studying Bezier Curves, but I don't think it's the best solution (see https://...
2
votes
1answer
49 views
Algorithm for placing rooks on an $n\times n$ chessboard such that they attack exactly $m$ squares
Suppose there is a chessboard with dimensions $n\times n$ and you put rooks on the chessboard such that they collectively attack $m$ squares on that chessboard (a rook attacks the square it is on, too)...
1
vote
0answers
178 views
Cyclic Partisan Nim Variant
This game is played with a sequence of heaps and a position marker, where each heap is owned by exactly one player. The game ends when a player has removed all objects from their own heaps, and this ...
0
votes
1answer
28 views
After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?
Consider a hash function that distributes keys uniformly. The hash table size is 20.
Here I am getting answer 11 considering the fact that probability will of collision will be 50% more only when we ...
0
votes
0answers
20 views
An algorithm to find a tuple of subsets for which every subtuple of given size has union equal to the entire set
This question involves the setup given here: Counting tuples of subsets for which every subtuple of a given size has union equal to the entire set
. Nonetheless this question is logically independent ...
3
votes
0answers
169 views
Comparing elements of sets
Let $a_1, a_2, a_3, a_4$ be real numbers.
Consider the following sets
$$
\mathcal{U}_1\equiv \{-a_1, a_1, -a_2, a_2, 0, \infty, -\infty\}
$$
$$
\mathcal{U}_2\equiv \{-a_3, a_3, -a_4, a_4, 0, \infty,...
0
votes
1answer
67 views
How do you apply this algorithm to $x^2+5x+6$?
There's a generic algorithm that works for these types of trinomials ($ax^2+bx+c$)
First write $\left(\dfrac{ax\phantom{+4}}{\phantom{5}}\right)
\left(\dfrac{ax\phantom{+4}}{\phantom{5}}\right)...
