Stack Exchange Network

Stack Exchange network consists of 174 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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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