Questions related to combinatorics and discrete mathematical structures
4
votes
1answer
68 views
Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have ...
3
votes
1answer
23 views
Chazelle's discrepancy book: greedy method
In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem ...
9
votes
0answers
117 views
Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.
Problem statement:
Consider the folowing variation of the well know problem Towers of
Hanoi:
We are given $n$ towers ...
7
votes
1answer
77 views
How to practically construct regular expander graphs?
I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.
What is the easiest method to do this in practice?
Constructing a random d-regular graph, which is ...
16
votes
0answers
136 views
Asymptotics of the number of words in a regular language of given length
For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
5
votes
1answer
68 views
What is a compact way to represent a partition of a set?
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly ...
2
votes
1answer
126 views
Maximum number of augmenting paths in a network flow
Let's say we a have flow network with $m$ edges and integer capacities.
Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.
A good way to start thinking ...
3
votes
1answer
69 views
Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
2
votes
1answer
60 views
How to enumerate combinations in parallel
I have $n\times k$ matrix with $k<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried ...
1
vote
1answer
61 views
How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$?
Suppose we are given $n$ variables $X_i, i=1,\dots,n$, each taking values from $\{0,1\}$, and a constant integer $k$ with $ 0\leq k \leq n$.
What are some efficient ways to enumerate all possible ...
3
votes
1answer
42 views
Counting solutions to system of linear equations modulo prime
I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to ...
2
votes
1answer
84 views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
4
votes
1answer
63 views
What is the maximum number of shortest paths between any pair of vertices in a chordal graph?
A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
4
votes
2answers
100 views
How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$?
I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.
My ...
8
votes
1answer
74 views
Number of Hamiltonian cycles on a Sierpiński graph
I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
2
votes
1answer
89 views
Tiling of squares
Motivation: This question is motivated by my previous question . In that question, my statment of the uniqueness requirement is not interesting since it leads to easily computable function. I am ...
7
votes
2answers
234 views
Why are there more non-computable functions than computable ones?
I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are ...
6
votes
1answer
133 views
Unique tilings of squares
We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile such that every underlying square is covered without overlapping. Let us define a ...
3
votes
0answers
72 views
Dynamic Knapsack Problem - Algorithms and References
I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
1
vote
2answers
81 views
How optimal is Lempel-Ziv at reaching the Shannon limit?
I find this a bit difficult to describe, but I am interested in the following idea :
The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal ...
1
vote
1answer
23 views
On the generalization of two recreational problems: request for references, if there's any
I wonder if two famous (and, IMHO, very nice) recreational problems are been studied in some general form.
Here's the first.
We have 13 balls, all looking absolutely the same, with 12 of them having ...
5
votes
1answer
80 views
Application of Expander Codes
I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon ...
7
votes
2answers
145 views
Simplify complexity of n multichoose k
Edit: In my case, $k$ may be greater than $n$ and they grow independently.
I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was ...
0
votes
1answer
116 views
Data structures and algorithms for bridge game play?
In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There ...
0
votes
1answer
53 views
Multisets of a given set
A multiset is an unordered collection of elements where elements may repeat any
number of times. The size of a multiset is the number of elements in it counting
repetitions.
(a) What is the number of ...
0
votes
3answers
111 views
Recursive function calculating number of ways to sum $a + 2 b + 3 c = x$
Using python need to code a recursive function with one input and no global integers that calculates the number of options to get $x$ using $a*1+b*2+c*3$.
Say $x=3$, there are four options: $\lbrace ...
3
votes
2answers
252 views
Modified paths Counting in a Rectangle
I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:
We are given K Rectangles. The dimensions ...
2
votes
0answers
75 views
A Recursive Formula For Generalized Josephus problem
The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor".
The following recursive formula is given:
...
3
votes
1answer
75 views
Find vectors with elements of finite fields that sum up to given value
Given a universe $U$ consisting of k sets of vectors with each vector $\vec{v} \in {\mathbb{F}_{p^m}}^n $. Given also another vector $\vec{c} \in {\mathbb{F}_{p^m}}^n$.
Now decide if there is a set ...
3
votes
1answer
92 views
Functions between sets?
I recently took a practice exam for the Computer Science GRE and this was one of the questions:
Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set ...
3
votes
2answers
109 views
Algorithm to pack any small boxes into a big box
I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains ...
9
votes
1answer
987 views
When can a greedy algorithm solve the coin change problem?
Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v.
E.g. for the coinset 1,5,10,20 this gives 2 ...
7
votes
1answer
185 views
How many max heaps are there?
How many different max-heaps can I form using a list of $n$ integers.
Example:
list [1,2,3,4]
and max-heap is 4 3 2 1 or
...
3
votes
1answer
68 views
Computing the rank of a multiset after inserting another element
What is the procedure for computing the rank of a multiset after inserting an element?
For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements.
The multiset $M = (1,1)$ ...
5
votes
1answer
60 views
Maximal derangements
When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement
of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like
to know ...
0
votes
1answer
285 views
Average number of full nodes in a binary search tree
Let $f(N)$ be the average number of full nodes (nodes with two children) in an $N$-node binary search tree.
Determine the values of $f(0)$ and $f(1)$.
Given that for $N > 1$,
...
5
votes
1answer
80 views
Reconstructing a data table from cross-tabulation frequencies
Say there is a data table $D$ that we cannot see, with $M$ columns. We are given exact cross-tabulation frequencies for all ${M \choose 2}$ pairs of columns, that is how often each combination of two ...
7
votes
0answers
152 views
On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
4
votes
1answer
86 views
How many possible assignments does a CNF sentence have?
I'm having some trouble understanding the following:
When we look at satisfiability problems in conjunctive normal form, an underconstrained problem is one with relatively few clauses constraining ...
2
votes
1answer
102 views
What is the probability of friendship conditioned on the number of mutual friends
Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?
I am ...
15
votes
1answer
412 views
Pizza commercial claim of 34 million combinations
A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out. ...
6
votes
1answer
126 views
Problem similar to set packing
Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse ...
6
votes
3answers
385 views
Generalised 3SUM (k-SUM) problem?
The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.
It is conjectured that there is not better solution than quadratic, i.e. ...
18
votes
6answers
608 views
Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
7
votes
2answers
466 views
What is the average height of a binary tree?
Is there any formal definition about the average height of a binary tree?
I have a tutorial question about finding the average height of a binary tree using the following two methods:
The natural ...
5
votes
2answers
365 views
Algorithm to find optimal currency denominations
Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The ...
2
votes
0answers
97 views
How to formalise efficient payment with a collection of coins in a wallet?
Context
If you have to pay an amount of money at a store and have a limited collection of payment items (i.e. coins and banknotes) -- let's for simplicity assume there are only coins -- a trivial ...
5
votes
2answers
798 views
Prove that every two longest paths have at least one vertex in common
If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.
I think that that common vertex ...
6
votes
4answers
130 views
What is the number of expressions containing n pairs of matching brackets with nesting limit?
I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching ...
4
votes
2answers
245 views
Is there a formal name for this graph operation?
I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation. The operation takes two distinct edges, injects a new node between the ...
