All Questions
33
questions
0
votes
1
answer
36
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
3
votes
2
answers
191
views
Guaranteed graph labyrinth solving sequence
Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
- 53
0
votes
0
answers
36
views
Understanding the optimality bound for Greedy algorithm in maximization of monotone submodular functions
I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the ...
3
votes
1
answer
115
views
From three integers, choose any two and replace one of them with the two numbers' mean. Show that we can obtain equal integers.
Let $a, b, c$ be three distinct positive integer numbers on a whiteboard. At each step, I choose two of them and I replace one of the two numbers with their arithmetic mean.
For example: I choose $a, ...
- 1,768
1
vote
0
answers
30
views
Can we find a proper $\phi$ so that maps each interval to its center?
For a compact interval $[0,1]$, we divide it into $N^{1/3}$ subintervals with length $N^{-1/3}$. Define a map $\phi: [0,1]\mapsto [0,1]$ maps each subintervals to its center.
For example, let $X\sim ...
- 1,514
0
votes
1
answer
267
views
Algorithm verification: Get all the combinations of possible words
I wanted to know if the algorithm that i wrotte just below in python is correct.
My goal is to find an algorithm that print/find all the possible combinaison of words that can be done using the ...
- 805
0
votes
0
answers
28
views
Ordering of points based on their relative positions (limited info incl. errors)
I am currently working on a problem which I assume mathematicians have already solved.
Setup: I have $N$ people standing in a line. Each of them is assigned with a different number between $1$ to $N$. ...
1
vote
2
answers
71
views
Looking for an algorithm
I have a very long "list" of numbers ( maybe thousands ) which may be grouped, by sum into "n" groups. The number of groups and values are given. For example:
List of numbers: [1, ...
1
vote
0
answers
294
views
Algorithm to find maximum sum over weighted overlapping intervals
Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
- 173
7
votes
1
answer
387
views
Robot moves from $(x,y)$ to $(x+y, y)$ or $(x,x+y)$
I was working on some coding related to this topic I found on Stack Overflow. This lead me to a math problem I thought would be interesting. I was wondering if one was given a starting point, what ...
- 71
0
votes
0
answers
35
views
Runtime Complexity of Memoization
I am struggling to analyze the runtime complexity of the following algorithm formally:
Given a string s and a dictionary of words dict(wordDict), add spaces in s to
construct a sentence where each ...
- 201
0
votes
1
answer
32
views
Search a word in a matrix runtime comlexity
Trying to analyze the runtime complexity of the following algorithm:
Problem: We have an $m \cdot n$ array $A$ consisting of lower case letters and a target string $s$. The goal is to examine whether ...
- 201
4
votes
1
answer
252
views
Maximum number of iterations of a simple algorithm
Suppose there is a 0-1 string of length n. We can perform the following operation on the string:
We can choose two zeros and invert the subsequence between them. The inversion includes the two zeros ...
- 65
0
votes
0
answers
34
views
Expected size of a set with iterative probabilistic growth
We exhaustively compare every item in set $A$ to the items in set $B$, where $A\cap B=\emptyset$, to look for matches.
We repeat this across iterations, where at every iteration, $|A|=n\gt 0$. At ...
0
votes
1
answer
162
views
number of combinations by choosing $\frac{n}{2}$ elements out of n elements
Edit: The mistake was in me counting (enumerating by hand) which @JMoravitz kindly taught me to do right in the chat.
Apologies!
I'm trying to code a problem I have, and I would like to use a ...
- 675
0
votes
1
answer
52
views
Find the minimal composition from n sets that satisfies the given condition.
We have N sets of triples, like
1. { (4; 0,1), (5 ; 0.3), (7; 0,6) }
2. { (7; 0.2), (8 ; 0.4), (1 ; 0.4) }
...
N. { (6; 0.3), (1; 0.2), (9 ; 0.5) }
and need to ...
- 319
5
votes
0
answers
121
views
Partition problem where partition are in increasing order.
For given $n$ and $S$, how many possible combinations are there such that:
$x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$
For example, if $n$ = 3 and $S$ = 5, there ...
- 51
2
votes
1
answer
61
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 ...
2
votes
4
answers
266
views
How many numbers are there for a $16*16$ matrix
Consider all matrixes with $1,0$ if all the numbers are $1$ we define $S=1$ and if all the numbers are $0$ then $S=0$ if non of them happened then we divide it into $4$,$2^{n-1}*2^{n-1}$ matrixes and ...
- 3,568
1
vote
2
answers
640
views
Number of combinations of increasing tuples given their sum
A tuple is represented by
$(a_i,a_{i-1},...,a_1)$ where $a_i<a_{i-1}$ and $i \in \{2...N\}$
So, valid tuples are $(1,2,3,4)$ and $(2,5,9,41)$
You are given the sum of these tuples
$a_i + a_{i-1}...
- 33
5
votes
3
answers
5k
views
How many ways to reach $Nth$ number from starting point using any number steps between $1$ to $6$
In a board game, dice can roll either $1, 2, 3, 4, 5$ or $6$. The board has $N$ number of space. Every time of dice roll randomly, pawn moves forward exactly to dice rolled a number. Now the problem ...
- 63
-1
votes
1
answer
93
views
Algorithm to order and partition a set of of (n,m) pairs with constraints.
I ran into this problem while looking at Google API distance matrix service.
Say you have a collection of a few million (origins, destinations) unique pairs/2 column table like (address, zip) for ...
- 11
3
votes
0
answers
461
views
Count number of m-subsets with xor = 0 [closed]
Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let $[k]=\{1,2,\...
- 740
2
votes
1
answer
158
views
Minimally Good Sequences
Let $k$ be a fixed positive integer. Let a sequence of positive integers with odd sum $(a_1,\ldots,a_n)$ be called good if for all integers $1 \leq i \leq n$, we have $\sum_{j \neq i} a_j \geq k$
Now ...
- 605
0
votes
1
answer
1k
views
Complexity of subset-generation algorithm
I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items.
The algorithm works using the recursive formula of the binomial coefficient
$$\...
- 175
0
votes
2
answers
314
views
Sum of roots of binary search trees of height $\le H$ with $N$ nodes
Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees.
For example, for $N$ = 3, $H$ = 3: ...
- 412
3
votes
2
answers
160
views
Most efficient algorithm to distribute n n-bit strings among n people
We are given $n$ people, whom we identify with the elements of $[n]=\{1,\ldots,n\}$. We are also given a finite collection $\mathcal{K}$ of subsets of $[n]$. The problem is to (efficiently) ...
- 69
3
votes
1
answer
58
views
Finding a recursive definition and computing $B(10)$
For $n \geq 1$, let $B(n)$ be the number of ways to express $n$ as the sum of $1$s and $2$s, taking order into account. Thus $B(4) = 5$ because $4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = ...
- 139
3
votes
1
answer
808
views
number of derangements
In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses.
A derangement of n numbers is a ...
- 315
3
votes
2
answers
194
views
Google Question: Number of ways to select sets such that n is pure
Consider a subset $S$ of positive integers.
A number in $S$ is considered pure with respect to $S$ if, starting from it, you can continue taking its rank in $S$, and get a number that is also in $S$, ...
- 315