All Questions
18
questions with no upvoted or accepted answers
8
votes
0
answers
317
views
Efficient algorithms to determine whether vertices form a deadlock
$\textbf{I. Problem Statements}$
Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations:
(1)$[m] := \{1, 2, \dots, m\}$.
(2)$e_i$ is the elementary vector with $...
- 1,008
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
2
votes
0
answers
71
views
Finding whether a sum of numbers in a set generate another number
I have a set of numbers $\{a_1,\dots,a_n\}$ and another number $k$. I need to find whether sum of any combination of numbers in the set produces $k$. It can be $a_1 + a_2$ or $a_1 + a_2 + a_3 + a_7$. ...
- 121
1
vote
0
answers
73
views
How to quickly eyeball maximum sum subarray?
Given an integer array, I want to find the continuous subarray (containing at least one number) which has the largest sum. There are some algorithmic solutions to this here: https://en.wikipedia.org/...
- 1,415
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
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
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
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
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
0
votes
1
answer
27
views
Choosing k elements with multiple weights maximizing the minimum weight
Consider the following optimisation problem.
Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$.
Find an $X\subset S, |X|=k$ ...
- 31
0
votes
0
answers
21
views
Filtering out faulty durations
I have a question that is algorithms and CS related but felt more appropriate to ask on Math Exchange.
I have a list of candidates, each with a given duration. for example {candidate1: 15s, candidate2:...
0
votes
0
answers
32
views
Effectively solve optimization problem in this system?
The system :
Given
$2$ sets $I,J$ such that $I\cap J = \emptyset , \#I = \#J$
a time-dependent function $c : \mathbb{R}_{\ge 0} \times I \times J \to \mathbb{R}_{\ge 0}$ .
Consider a system that ...
- 910
0
votes
0
answers
68
views
Finding the general formula for the last standing soldier
Suppose there are 'n' soldiers standing in a circle who have decided to kill each other (just because they don't want to surrender to the opposition).
Lets say they are denoted from a1 to an in the ...
- 1
0
votes
0
answers
67
views
Greedy algorithm for variation of bin packing
Consider the bin packing problem where an input array of weights have to be packed in the minimum number of bins possible. Consider the two following restrictions. First, for any bin, a heavier weight ...
- 127