Problem Detail: Given the problem $EQ_{TM} = { langle M_1, M_2rangle mid M_1 text{ and } M_2 text{ are } TM, L_{M_1} = L_{M_2}}$, is it possible to prove that this is undecidable by using (a variant of) Rice theorem? I Read More …
Category: Uncategorized
[Solved]: People crossing a bridge (a proof for a greedy algorithm)
Problem Detail: The problem Some people are crossing a bridge. Each one takes a different time to pass. Assume the people are sorted by their passing time increasingly. These are the conditions of crossing the bridge: only 1 or 2 people Read More …
[Solved]: Approximating the Kolmogorov complexity
Problem Detail: I’ve studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (identify how each author writes some text and group Read More …
[Solved]: Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems?
Problem Detail: I was watching the videos from Skiena’s Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer scientists by biologists were proved to be Read More …
[Solved]: Constructing a random Hamiltonian Cycle (Secret Santa)
Problem Detail: I was programming a little Secret Santa tool for my extended family’s gift exchange. We had a few constraints: No recipients within the immediate family Nobody should get who they got last year The whole thing should be a Read More …
[Solved]: Any very user friendly resources on the Baum-Welch algorithm?
Problem Detail: I’d like to understand the Baum-Welch algorithm. I liked this video on the Forward-Backward algorithm so I’d like a similar one for Baum-Welch. I’m having trouble coming up with good resources for Baum-Welch. Any ideas? Asked By : Walrus the Read More …
[Solved]: Lambda calculus outside functional programming?
Problem Detail: I’m a university student, and we’re currently studying Lambda Calculus. However, I still have a hard time understanding exactly why this is useful for me. I realize if you do loads of functional programming it might be useful, however Read More …
[Solved]: distance between histograms
Problem Detail: I have 2 histograms that represent the height of characters in 2 images. example: 1 ** 2 **** 3 **** . . . 100 ****** For these 2 histograms I compute the peaks. And To check if these 2 Read More …
[Solved]: Automata that recognizes Kleene closure of permutations of three symbols
Problem Detail: This is an automata theory homework question. I need to create DFA that meets the following criteria: Alphabet $Sigma = { a, b, c }$ Machine accepts empty string and strings of length that is a multiple of three, Read More …
[Solved]: Why does merge sort run in $O(n^2)$ time?
Problem Detail: I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O is the Read More …
