Computer Science Stack Exchange Community Digest

Top new questions this week:

Why rectangle packing is NP-hard but maybe not in NP?

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 ...

np-hard np decision-problem  
asked by Jxb Score of 8
answered by Yuval Filmus Score of 16

Advantages of linked lists over arrays?

Are there other advantages to linked lists over arrays other than constant time removals of the first element?

asked by Austin Conlon Score of 5
answered by Surprised Seagull Score of 17

Name and complexity of this problem on bipartite graphs

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$...

graphs np-hard bipartite-graph  
asked by Luigi Procopio Score of 4
answered by Narek Bojikian Score of 2

If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$

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}$ ...

regular-languages automata finite-automata  
asked by Shubhang Gupta Score of 4
answered by Yuval Filmus Score of 4

Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

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 $ ...

complexity-theory asymptotics runtime-analysis recurrence-relation  
asked by Mampac Score of 3
answered by John L. Score of 4

Why can't $QBF$ be reduced to $SAT$

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, $Φ$...

reductions satisfiability  
asked by SVMteamsTool Score of 3
answered by Steven Score of 6

Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $

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, ...

algorithms algorithm-analysis amortized-analysis dynamic-array  
asked by hazelnut_116 Score of 3
answered by John L. Score of 2

Greatest hits from previous weeks:

What is the difference between object detection, semantic segmentation and localization?

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 ...

terminology computer-vision  
asked by Martin Thoma Score of 31
answered by e3oroush Score of 19

Regular Expression for even-odd language of string

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$'...

automata regular-expressions  
asked by Khurram Ali Score of 4
answered by Ran G. Score of 8

What is a safe programming language?

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 ...

asked by beroal Score of 61
answered by Davislor Score of 25

What is the definition of P, NP, NP-complete and NP-hard?

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 ...

complexity-theory terminology complexity-classes p-vs-np reference-question  
asked by Mirrana Score of 314
answered by Kaveh Score of 444

How to prove that a language is not regular?

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 ...

formal-languages regular-languages proof-techniques reference-question  
asked by Raphael Score of 92
answered by Romuald Score of 71

How to prove that a language is not context-free?

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....

formal-languages context-free proof-techniques reference-question  
asked by Raphael Score of 96
answered by jmad Score of 73

Which machine learning algorithms can be used for time series forecasts?

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 ...

reference-request machine-learning artificial-intelligence  
asked by Maecky Score of 28
answered by rphv Score of 28

Can you answer these questions?

A Single Row GUI Layout Algorithm

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 ...

algorithms graphics user-interface  
asked by skiars Score of 1

Running time of 01-Knapsack-like with negative weight/values, absolute value weight constraint, and volume constraint?

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\...

complexity-theory dynamic-programming knapsack-problems  
asked by Rando5 Score of 1

Sum in counting satisfying assignments

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 ...

algorithms complexity-theory satisfiability counting  
asked by Arnau M. Score of 1
answered by Yuval Filmus Score of 0
You're receiving this message because you subscribed to the Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038