Top new questions this week:
|
|
Recently I studied a MIT open course.
In lecture2, it is stated that Rectangle Packing is NP-hard.
I can understand this because the problem can be reduced to 3-partition problem
But I don't know why ...
|
|
Are there other advantages to linked lists over arrays other than constant time removals of the first element?
|
|
Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes.
I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$...
|
|
For a language $\mathcal{L}$ over an alphabet $\Sigma$, define
$$\mathcal{SW(L)} := \{ y ∈ Σ^∗ \mid \exists x \in Σ^* \text{ such that } xyx \in \mathcal{L}\}$$
How can I prove that if $\mathcal{L}$ ...
|
|
Given the algorithm
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2 return 1
3 else
4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)
I defined a recurrence
$ ...
|
|
Let $QBF_k$ be the problem of determining the satisfiability of a formula of the form
$Φ = Q_1x_1Q_2x_2 . . . Q_kx_k φ(x_1, . . . , x_n)$.
where each $Q_i$
is one of the quantifiers $∀$ or $∃$. So, $Φ$...
|
|
The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS
Problem: We are given a dynamic table $T$ that supports INSERT operation, ...
|
Greatest hits from previous weeks:
|
|
I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic ...
|
|
I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of $a$'...
|
|
Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be ...
|
|
I'm in a course about computing and complexity, and am unable to understand what these terms mean.
All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
|
|
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
|
|
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
|
|
Currently I am playing around with time series forecasts (specifically for Forex). I have seen some scientific papers about echo state networks which are applied to Forex forecast. Are there other ...
|
Can you answer these questions?
|
|
I need a layout algorithm and use it in the GUI, but I can't use existing GUI toolkits at the moment, so I would like to find a layout algorithm.
I only need to do a single row layout, and here is the ...
|
|
Background
In the classic formulation of the knapsack problem with both weight and volume constraints, we are given a collection of $n$ items where item $i$ has weight $w_i\in\mathbb{N}$, volume $u_i\...
|
|
Is there a polynomial-time algorithm that computes the sum of two boolean formulas, such that, (#SUM(F,G) = #F + #G), the output satisfying assignments equals the sum of the satisfying assignments of ...
|
