Computer Science Weekly Newsletter

Computer Science newsletter

Top new questions this week:

Halting problem - one issue that's bothering me

To my knowledge, halting problem asks if there exists a program that decides whether a program being tested, given some input data (no matter what program it is, or what input data we give) will ...

computability halting-problem  
asked by user4205580 8 votes
answered by Ariel 6 votes

Class of the language only containing the empty string?

$L = \left \{ \epsilon \right \}$ Clearly this language is finite so this must be a regular language. Now since every regular language is Context Sensitive, $L$ is a CSL. We can define the grammar ...

formal-languages regular-languages context-sensitive  
asked by Romy 6 votes
answered by phs 8 votes

Bipartite Graph - How to determine largest subsets that are all connected

I have a bipartite graph $G = (U,V,E)$, where $U$ and $V$ are disjoint node sets and $U \cup V$ is the set of all vertices, and $E$ is the set of all edges. I'm looking for subsets $U' \subseteq U$ ...

algorithms graphs optimization  
asked by Thorsten 6 votes
answered by Tom van der Zanden 6 votes

What NP decision problems are not self-reducible?

So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of ...

complexity-theory reductions decision-problem np  
asked by Adam Martin 6 votes
answered by Yuval Filmus 2 votes

How do incompressible strings and random strings share the same properties?

I came across the following theorem in Sipser's about incompressible strings. Let $\;f$ be some computable function which holds for almost all strings. The for any $b > 0 $, the property $\;f$ ...

computability data-compression randomness  
asked by sasha 5 votes
answered by Yuval Filmus 6 votes

How to show all possible implied parenthesis?

Can I use recursion to find out the possible parenthesis we can add to this expression: 2*3-4*5 ? (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = ...

combinatorics recursion  
asked by noman pouigt 5 votes
answered by Anton Trunov 3 votes

Help with proof involving weighted full binary tree

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the ...

graph-theory trees binary-trees induction  
asked by so.very.tired 5 votes
answered by Yuval Filmus 5 votes

Greatest hits from previous weeks:

Normalizing the mantissa in floating point representation

How to represent $0.148 * 2^{14}$ in normalized floating point arithmetic with the format 1 - Sign bit 7 - Exponent in Excess-64 form 8 - Mantissa $(0.148)_{10} = (0.00100101\;111...)_2$ We shift ...

binary-arithmetic floating-point rounding  
asked by Shashwat 3 votes
answered by Vor 1 vote

Complexity of recursive Fibonacci algorithm

Using the following recursive Fibonacci algorithm: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) If I input the number 5 to find fib(5), I know ...

algorithms time-complexity recursion  
asked by joker 5 votes
answered by ees_cu 13 votes

Can you answer these?

Construct matching for half of the vertices, in linear time

Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free. Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching). ...

algorithms graph-theory graphs matching  
asked by penguina 3 votes

Does dijkstra works when I multiply weights of successive nodes

Consider a complete bidirectional weighted graph. Weight of each edge (a,b) is the probability of getting from a to b. So all weights are in range (0,1]. Probability of going from a to b through the ...

graphs shortest-path  
asked by sudomakeinstall2 2 votes

Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$

(At the very bottom of this, I will shortly describe the motivation for this question.) Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ ...

complexity-theory optimization algebra monoids  
asked by G. Bach 4 votes
Subscribe to more Stack Exchange newsletters

Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on

Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all emails.

Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3