All Questions
90
questions
4
votes
1
answer
285
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
1
answer
40
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 3,019
1
vote
2
answers
71
views
Marching cubes generates surface triangles. How to adapt it to generate tetrahedra throughout the volume of a 3D model?
Background
There is a source code that generates surface triangles. The isosurface is generated for the iso-value of 0. The source code uses a table for ...
- 271
2
votes
0
answers
52
views
Fastest way to get from one permutation to another (with distances between elements)
Imagine that I have some rows of shelves. Some shelves have items on them. Some may be empty. Imagine also that I have computed the shortest paths between each location (using Dijkstra's algorithm, ...
- 241
0
votes
1
answer
51
views
Convert $k$ numbers into a single number with $\log_2{n_k + k \choose k}$ bits
Suppose we have $k$ natural numbers such as $n_1 \leq n_2 \leq n_3 \leq \ldots \leq n_k$. Is there any encoding algorithm that alllow to encode this numbers to one number with $\log_2{n_k + k \choose ...
- 13
0
votes
1
answer
34
views
Condition for a Hamiltonian cycle existing proof question
Let $G$ be a graph. If there exists $X\subseteq V(G)$, $X\neq \emptyset$ s.t. $G\setminus X$ has more than $|X|$ components, then $G$ has no Hamiltonian cycle.
Proof.
Suppose for a contradiction that $...
- 2,971
1
vote
1
answer
68
views
Combinatorics Question Relating to "At least"
Your help is greatly appreciated, rather simple question but not quite sure how to go about it.
Determine how many different possible combinations of computer science classes numbered 300 or above ...
3
votes
2
answers
145
views
Characterising functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying special equations
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ be a function.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(x+a)}= 0,
$$...
- 25.3k
4
votes
1
answer
183
views
Every boolean function is multiplicative with probability greater than $1/2$
Let $f:\left\{-1,1\right\}^n\to\left\{-1,1\right\}$.
How to show that
$$
P_{{x,y,z}} \{f(xyz)=f(x)f(y)f(z)\} \ge 1/2?
$$
where $x,y,z$ are distributed uniformly and independently on $\left\{-1,1\right\...
- 25.3k
0
votes
1
answer
102
views
Sudoku based problem. Counting with permutations?
I have been playing Sudoku lately, and I've seen a problem with this general form:
Given N items, each of which belongs alone (1-to-1) in one of N boxes, and given a list of statements of the form:
&...
1
vote
1
answer
770
views
Sorting an array using reverse
I ran into an Olympiad question recently, and one challenging question surprised me:
We have an array $A$ with $n$ elements. $\operatorname{Rev}(i, j)$ for $1 \leq i < j \leq n$ reverses subarray $...
6
votes
2
answers
214
views
a semi-hard problem on combinatory
I ran into a nice interview question.
the problem is as follows:
We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of ...
user871754
1
vote
1
answer
5k
views
How many bit strings of length 7 begin with a 10 or end with 01?
A bit string is a finite sequence of the numbers 0 and 1. Suppose we have a bit string of length 7 that starts with 10 or ends with 01, how many total possible bit strings do we have?
I am thinking ...
user826944
0
votes
0
answers
40
views
Catalan Numbers centered String Question
Using Catalan Numbers
One answer to this quesion.
In a given String these 6 conditions need to exists together:
String's length is 100
Only one curly brackets "{" is at index 1
Only one ...
- 109
0
votes
0
answers
40
views
Does this sentence make sense?
I have been reading a research paper called "Extracting human expertise for constructing knowledge spaces an algorithm", and they provided a way on how to choose the best question to provide ...
- 45