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

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

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

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

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

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

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

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

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

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

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