All Questions
33
questions
0
votes
1
answer
35
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
184
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
35
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,740
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,524
0
votes
1
answer
262
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 ...
- 795
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
293
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
385
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