Problem Detail: Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. Read More …
Blog
[Solved]: Compression of Random Data is Impossible?
Problem Detail: A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 – where someone was offering a prize of $5000 for any kind of reduction to the size of randomly generated data (the entrance Read More …
[Solved]: Space bounded Turing Machine – clarification on Computational Complexity (book: Arora-Barak ) question 4.1
Problem Detail: I have the following question from Computational Complexity – A modern Approach by Sanjeev Arora and Boaz Barak: [Q 4.1] Prove the existence of a universal TM for space bounded computation (analogously to the deterministic universal TM of Theorem Read More …
[Solved]: Hash function floating point inputs for genetic algorithm
Problem Detail: I am implementing a genetic algorithm to use as an optimisation algorithm to evolve robots. The robots have certain parameters (represented as floats) which can lie anywhere within a certain range defined for each parameter. My goal is to Read More …
[Solved]: Is there a known method for constructing a grammar given a finite set of finite strings?
Problem Detail: From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible to make a Read More …
[Solved]: Proof by Reduction: From Empty Language to Halting Problem on Empty Input
Problem Detail: Question: Let language $E$ = {$langle M rangle$ | $M$ accepts no inputs whatsoever} Let language $H$ = { $langle M rangle$ | $M$ halts on an empty string input}. Is it possible to show that $H$ is undecidable Read More …
[Solved]: Given $k$ sorted lists, $O(n log k)$ complexity, Mergesort rather than Heapsort
Problem Detail: I was convinced that my idea for a solution to sort $k$ sorted lists into one list would work with a ‘variation’ on MergeSort. I was told this would not work and had to use Heapsort, but didn’t get Read More …
[Solved]: Online Learning Resources for Discrete Mathematics
Problem Detail: Are there any good Discrete mathematics learning web resources with problem sets? Asked By : violet kiwi Answered By : blah I have the perfect place for you, I really enjoyed it myself: Discrete Mathematics lecture series on infocobuild Everything I Read More …
[Solved]: Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2×1 dominoes?
Problem Detail: http://www.algorithmist.com/index.php/UVa_10918 The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the problem. I have coded the solution but the approach is completely Read More …
[Solved]: Simple Task-Assignment Problem
Problem Detail: I have this simple ‘assignment’ problem: We have a set of agents $A = {a_1, a_2, dotso, a_n}$ and set of tasks $T= {t_1, t_2, dotso, t_m}$. Note that $m$ is not necessarily equal to $n$. Unlike the general Read More …
