Problem Detail: In class yesterday we went over DFA’s and DFA acceptable languages. An example of a language that is not DFA acceptable was given as ${ ab, aabb, aaabbb, aaaabbbb, ldots }$. The reason given was that the machine would Read More …
Blog
Proof Complexity of a Proof or Disproof of P = NP
Problem Detail: Has there been any research on the proof complexity of a resolution to the P=NP problem? If not, given the lack of progress on the problem, would it be unreasonable to conjecture that any proof that resolves the P=NP Read More …
Measuring one way network latency
Problem Detail: This is a puzzle about measuring network latency that I created. I believe the solution is that it’s impossible, but friends disagree. I’m looking for convincing explanations either way. (Though it is posed as a puzzle I think it Read More …
How do you classify properties as Trivial and Non-trivial?
Problem Detail: I understand what Rice’s theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone help me understand this better, maybe Read More …
Huffman encoding: why is there no need for a separator?
Problem Detail: Char Code ==== ==== E 0000 i 0001 y 0010 l 0011 k 0100 . 0101 space 011 e 10 r 1100 s 1101 n 1110 a 1111 Original text: Eerie eyes seen near lake Encoded: 0000101100000110011100010101101101001111101011111100011001111110100100101 Why Read More …
How is a JIT compiler different from an ordinary compiler?
Problem Detail: There’s been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or Python called JIT compilers, while Read More …
Finding a O(n) solution to: max difference of pairs array question
Problem Detail: I don’t know an O(n) solution to the following: Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in the array than Read More …
Checking Feasibility of Linear Program in Polynomial Time
Problem Detail: Given a linear system of the form: $$begin{array}{c} x_r = a quad x_j = b c_1x_1 + c_2x_2 + ldots + c_nx_n = N x_1+x_2 + x_3 + ldots + x_n = k 0 le a,b,x_1,x_2,x_3…x_n le 1 k Read More …
Generate scale-free networks with power-law degree distributions using Barabasi-Albert
Problem Detail: I’m trying to reproduce the synthetic networks (graphs) described in some papers. It is stated that the Barabasi-Albert model was used to create “scale-free networks with power-law degree distributions, $P_A(k) ∝ k^{-λ}$”. $P_A$ is a probability distribution that returns Read More …
What is the difference between a scripting language and a normal programming language?
Problem Detail: What is the difference between programming language and a scripting language? For example, consider C versus Perl. Is the only difference that scripting languages require only the interpreter and don’t require compile and linking? Asked By : SS Hegde Answered Read More …
