All Questions

44,241 questions
Filter by
Sorted by
Tagged with
3 views

Find $k$ shortest paths in linear time

Suppose given number $k$ and undirected unweighted graph $G=(V,E)$, also given two vertices $s$ and $t$. Can we find $k$ shortest paths between $s$ and $t$ in $O(n+m)$ without term $k$? I read this ...
4 views

The Language of All Palindromes - Is it CFL?

Regarding $L=\{ww^R~|~w\in\Sigma^*\}$ - The language of all palindromes. Is it a CFL? I think it is, because if we take any $\Sigma$, for example $\Sigma=\{a,b\}$, then it certainty is. CFL are closed ...
18 views

Formal mathematical resolution for Recurrence Relations

let's suppose we've got a simple Recurrence Relation: $$T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases}$$ At lesson we've resolved it, but I ...
• 200
23 views

Cosine distance in a space, and cheating?

I read an example of using cosine distance in RGB space, and it pointed out that (eg.) dark red and light red have a cosine distance (CD) of zero because CD only gives you the angle between vectors ...
• 198
9 views

Can you safely use the remaining space on a an external hard drive used for a recovery drive? [closed]

I created a recovery drive with the Control Panel's Advanced Recovery Tools, on an external hard drive. Is it safe (for the purposes of retaining a functional recovery drive) to create a new simple ...
27 views

Undirected unweighted sub-graph enumeration with threshold on node value

I have an undirected, unweighted graph $G=(V,E)$, and a function $f:V\to [0,1]$ where $[0,1]$ denotes the interval of real numbers from $0$ to $1$ inclusive. Given an input threshold $t\in [0,1]$, I ...
23 views

• 13
19 views

Entropy of a single Hint

Assume that the probability that a woman is above 80 years old is 3 times that of a man. How much information (in bits) do you get if you are given that a 80 year old person is a male? How should I ...
17 views

Is there an algorithm for mapping two ambiguous and unrelated data sets?

I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets. So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac ...
22 views

What kind of CNF and DNF are in P [closed]

could anyone help me to prove which languages are in P? I will present my thoughts but I do not know how to go from there. Thank for any help l1 = {L | L is on CNF and is satisfiable} l2 = {L | L is ...
• 103
1 vote