All Questions
Tagged with recursive-algorithms combinatorics
68
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
1
vote
1
answer
29
views
Lemma 6.2. in Scaling Algorithms for the Shortest Path Problem
I have a question regarding the proof of Lemma 6.2. in this paper: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/scaling%20algorithm%20for%20the%20shortest.pdf.
The simplified ...
- 102
3
votes
2
answers
190
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,740
0
votes
1
answer
37
views
Complexity of enumeration of a recursive formula ? Given the recurrence on time cost?
Let $a_n$ represent the number of directed acyclic graphs on $n$ vertices. Then the wikipedia, gives me the following recurrence:
$$a_n = \sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}2^{k(n-k)}a_{n-k}$$
I want ...
- 1,799
0
votes
1
answer
64
views
Minimum number of links needed to connect every vertex of a $4$-dimensional hypercube
Let $G_2^4 :=\{0,1\} \times \{0,1\} \times \{0,1\} \times \{0,1\}$ be a set of $2^4$ points in $\mathbb{R}^4$.
Which is the minimum number of straight lines connected at their endpoints (i.e., the ...
- 1,160
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,520
0
votes
1
answer
266
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$. ...
0
votes
1
answer
233
views
In how many ways can they be coloured so that two successive strips have different colours?
$n$ strips are to be coloured using three colours viz. red, blue and green. In how many ways can they be coloured so that no two consecutive strips are of same colour?
My Attempt:
Let $a_n$ be the ...
- 9,599
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
0
votes
1
answer
57
views
Can anybody supply a list of the 1560 possible contiguous, orthogonally connected configurations of three identical 2 x 4 lego bricks?
I have written a program to solve the lego counting problem - to count the number of different contiguous geometric structures that can be made from n identical 4 x 2 lego bricks, all connected ...
- 283
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