Questions tagged [co.combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
0
votes
0answers
67 views

Variation on Social Golfers

This is a problem I ran across recently while trying to schedule classes which I thought might be interesting theoretically. Given k golfers who want to play on <...
0
votes
0answers
292 views

Boolean circuits and digraphs

It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the "...
0
votes
0answers
476 views

Identify all of the non-overlapping rectangular regions of a simple concave polygon

I am looking for an algorithm to identify all of the rectangles bounded by two parallel edges of a polygon. The rectangle must remain inside of the polygon at all times. My polygon is simple and will ...
0
votes
0answers
503 views

Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon. In other words, I want to ...
0
votes
0answers
135 views

Tractability of mutual information-augmented ensemble classification algorithms

I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an ...
0
votes
0answers
186 views

Indexing over all possible functions in better than linear time

Given two sets X and Y, the number of functions mapping X to Y is $\vert Y\vert^{\vert X \vert}$. In particular I am interested in binary strings of relatively small length, e.g. 8. There are $2^8$ (...
0
votes
0answers
99 views

How many subsets of size L do not contain the first k arbitrary pairs?

Let there be a large set $X$, and a bijective function $f$ which maps the integer range 1 to $|X| \choose 2$ onto the subsets of $X$ of size 2. Given integers $L$ and $k$, where $2 \leq L \leq |X|$ ...
0
votes
0answers
324 views

On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT

I have 2 questions. Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph ...
0
votes
0answers
57 views

Regrouping a collection of sets based on constraint

(Pardon me for any unrefined usage/terminology for I do not have a math/CS background.) Consider a collection of $N$ balls with subsets of $n_1, n_2, ..., n_L$ balls of different $L$ colors. The ...
0
votes
1answer
129 views

Counting subsets with large sum

Suppose that you have a multiset of positive integers $I$. $I$ is not given, but it is known that the sum over all elements of $I$ = $k$. (e.g. if $I$={2,5,7} then k=14 is given, but I is unknown). ...
-1
votes
2answers
83 views

Arrangements of Objects

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ ...
-1
votes
1answer
66 views

Chomsky-Schutzenberg Hierarchies explained for physicist (general) [closed]

I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems. As someone who is somewhat unfamiliar with the language of ...
-1
votes
1answer
158 views

Application of the inequality with expectations

Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
-1
votes
2answers
417 views

Intersection between sets

Assume that we have $p$ sets, with given sizes: $m_1,m_2,...,m_p$. The (distinct) elements in each set are taken from $N$ elements (where $m_1,m_2,...,m_p \le N$). A combination is defined as an ...
-1
votes
1answer
165 views

Representation suitable for reconstruction of a tree with bounded degree

I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number ...
-1
votes
1answer
3k views

Minimal perfect hash function from sets of integers to integers

I would like to be able to map any subset of $S = \{0,..,m-1\}$ to an integer $k$. $m$ will probably be 32 because $|\mathcal{P}(S)| = 2^m$ and i want to use a variable with 32 bits to store this ...
-2
votes
1answer
251 views

Complexity of counting the number of Good-perfect matching in the bipartite graph

Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$. Definition1: ...
-2
votes
1answer
297 views

Finding research problem for PhD(TCS)? [closed]

I am a theoratical computer science PhD student. I am wanted some suggestion in how to find research problem for PhD research. I have supervisor and he has given me first problem. We had get progress ...
-2
votes
2answers
246 views

Lemma needed for my machine learning research [closed]

Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...
-2
votes
1answer
109 views

Subset sum for lists [closed]

Given a target list a = [2,4,1,4]` and a list of lists ...
-3
votes
1answer
194 views

Proving that a random permutation generator is not fair [closed]

If I'm generating random permutations using the following algorithm: ...
-3
votes
1answer
155 views

Continous work distribution algorithm with failover

Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256. Is there an algorithm that ...
-3
votes
1answer
6k views

unique binary tree from preorder and postorder traversals of a full binary tree [closed]

If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T. If so.. could ...
-4
votes
1answer
53 views

does within the "range a and b" include a and b?

I have not found the answer to this doubt of mine elsewhere, hence posting it here. It may be a silly question but I just want to be sure :P would be great if someone could help me out with this ...
-4
votes
2answers
461 views

Covering Codes with Game Theory Application

Here is a question I came up with and i have been pondering for a while. It relates to covering codes, a subset of coding theory. I could not come up with an adequate solution, so here I am, asking ...
-5
votes
1answer
2k views

Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...
-5
votes
1answer
132 views

A simple challenge

Consider the following problem: given a number $n$, an alphabet $\Sigma$, and a finite language $L$, how many strings of length $n$ in $\Sigma^*$ contain at least one word $w\in L$? E.g. ...
-8
votes
2answers
298 views

A question on the very essence of "theoretical computer science" [closed]

What is the point of the study? Why would anyone want to just make a career, passion, or otherwise interest or hobby in something that purports itself as theories for computational systems in general? ...

1
9 10 11 12
13