Computer Science Weekly Newsletter - Thursday, July 31, 2014

Computer Science newsletter

Top new questions this week: Is Post's Correspondence Problem decidable with fixed word size? So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$. I'm wondering, can anything similar be said for when there is a fixed word length? To be precise, here's … computability undecidability decision-problem   asked by jmite 6 votes answered by Raphael 8 votes Graph isomorphism problem for graphs with colored directed edges In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is … algorithms graph-theory graph-isomorphism   asked by Max 6 votes Bounded existential polymorphism In Pierce's "Types and Programing Languages" he, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential … reference-request lambda-calculus type-theory functional-programming   asked by Jake 4 votes Can someone clarify landau symbols definition please? I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know … asymptotics landau-notation   asked by user3236702 3 votes answered by lPlant 4 votes Variable Length Encoding of Integers Using a Modulus Algorithm Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me. The constraints are … algorithms encoding-scheme   asked by Guillermo Phillips 3 votes answered by Yuval Filmus 2 votes Complexity of the decision version of determining a min-cut I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most … complexity-theory graph-theory time-complexity polynomial-time network-flow   asked by Oliver Witt 3 votes answered by Oliver Witt 2 votes Conceptual question about entropy and information Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that … terminology information-theory entropy   asked by Ria George 3 votes answered by Wandering Logic 4 votes Greatest hits from previous weeks: Applying Expectation Maximization to coin toss examples I've been self-studying the Expectation Maximization lately, and grabbed myself some simple examples in the process: From here: There are three coins $c_0$, $c_1$ and $c_2$ with $p_0$, $p_1$ and … probability-theory statistics   asked by IcySnow 10 votes answered by Nicholas Mancuso 8 votes Definition of the state of an object in OOP I need a concise definition of the "state of an object" in object-oriented programming (for a paper). For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find … terminology reference-request programming-languages object-oriented   asked by mrsteve 2 votes answered by Vor 5 votes Can you answer these? Stopping condition for goal-directed bidirectional search for shortest path So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ … algorithms graphs search-algorithms shortest-path   asked by Jan Hudec 2 votes Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square? This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula … combinatorics recursion tiling   asked by user2566092 2 votes Matching with dependencies I have a matching problem which I find is rather different from the stable marriage problem. I have four sets $A,B,C,D$. Elements of set $A$ have to be matched with those of $B$ and $C$ is to be … algorithms reference-request matching assignment-problem   asked by user3761729 1 vote

Subscribe to more Stack Exchange newsletters Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on stackexchange.com. Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all stackexchange.com emails. Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3