All Questions
58
questions
1
vote
0
answers
160
views
How would you prove that a dynamic programming problem is solvable by a greedy algorithm?
I have solved a few optimizations problems using dynamic programming, but some of those problems are also solvable by Greedy algorithms which are computationally more efficient to calculate.
For ...
- 1,035
3
votes
0
answers
72
views
Dividing class into groups
Just a question I have been pondering.
Assume you have a class of 100 students, each student chooses 3 friends. The goal is to split them into 4 groups of 25.
We define 'satisfaction level of ...
- 193
0
votes
1
answer
108
views
How to make the subset sums of a given array of numbers, even.
I'm not sure if I've been able to clearly state my problem here, but here's the extensive problem description:
We have an array of $n$ numbers, and another given number $d$, one step at a time, we ...
- 617
1
vote
0
answers
72
views
Learning about Proofs and how to write them? (A programmer's perspective)
I have a B.S. Degree in computer science and have taken more math classes then the average person but not enough to consider myself good at it. I have been briefly introduced to proofs.
I'm currently ...
- 111
0
votes
2
answers
167
views
How many unique sums $x_0+x_1+x_2+\cdots+x_n=S$ where $x_i>x_{i-1}$?
How many unique sums $x_0+x_1+x_2+\cdots+x_n=S$ where $x_i>x_{i-1}$ are there for each $S$?
$x_i$ and $S$ are non-negative integers.
My Computer Science prof also said that this can be solved ...
- 181
1
vote
1
answer
66
views
Find least number of radial-subgraph of a graph
Background:
Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader?
...
- 19
1
vote
0
answers
185
views
Determine Huffman Tree Depth Using any combinactory ways?
I see this link for determining depth (height) of Huffman tree, but not useful for me.
My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
1
vote
1
answer
93
views
Load balance N customers over K servers with different capacities
Let's say we have N customers that supply a stream of requests, but each customer i supplies different number of requests per minute - $R_i$. All requests are identical in terms of the amount of ...
- 111
1
vote
3
answers
509
views
Isomorphism of Non-Symmetric Matrices
$A, B$ are non-symmetric matrices of dimension $m \times n$ where $m=n$ or $m \neq n$.
Example: An example of $6 \times 3$ non-symmetric matrix is
$$
\begin{pmatrix}
1 & 0 & 0 \\
0 & ...
- 499
1
vote
0
answers
25
views
Finding objects from a list with some properties in $O(n)$
Lets say I have $2$ strings each having $4$ characters.
$k$ is a number $\le 4$.
If, $2$ strings have exactly $k$ common characters lets say they are a "happy pair" with $k$ points.
If I have $n$ ...
- 275
0
votes
1
answer
1k
views
Finding number of subarrays not including certain pairs
How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array?
For eg. if array ={11,22,33,45}
and if we do not want to include say position ...
- 133
2
votes
1
answer
40
views
Finding the size of sumsets in limited space
Let $S=\{a+b:\ a\in A,\ b\in B\}$. I have an explicit representation of $A$ and $B$, but $S$ is too large to store in memory. (For the sake of argument, say $A$ and $B$ are 100 MB and $S$ is 1000 TB.) ...
- 32.3k
3
votes
1
answer
2k
views
what' is the number of full subtrees of a full binary tree?
I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are:
Now my question is:
What is $N(h)$ the maximum number of full sub-trees of a full ...
- 13.8k
3
votes
1
answer
205
views
Traveling salesman neighborhood
I am solving some TSP problems and i got this one and i am not pretty sure about my answer.
By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
- 14.7k
2
votes
1
answer
619
views
Counting the number of complete bipartite subgraphs
I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
- 22.5k