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 …
Category: Uncategorized
[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]: Can the isomorphic graph problem be solved in deterministic polynomial time?
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 …
[Solved]: Convergence of Simulated Annealing Based Algorithms
Problem Detail: I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge fast (based on satisfying some properties) to global/local optimal point Read More …
[Solved]: How can SML infer types like this?
Problem Detail: Wikipedia says: fun factorial n = if n = 0 then 1 else n * factorial (n-1) A Standard ML compiler is required to infer the static type int -> int of this function without user-supplied type annotations. I.e., 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 …
[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]: Selling blocks of time slots
Problem Detail: Given $n$ time slots that $k$ people want to buy. Person $i$ has a value $h(i,j)geq 0$ for each time slot $j$. Each person can only buy one consecutive block of time slots, which could be empty. Is there Read More …
[Solved]: How to analyze the lower bound of the horse racing problem using adversary argument?
Problem Detail: Consider the following problem: Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of these horses. Analyze the Read More …
[Solved]: Design a DFA which accepts words with sorted letters
Problem Detail: I have just started learning Theory of Computation and have come across a question which I am not able to solve. The question is as follows: Design a DFA that reads a word (character strings) and decides whether the Read More …
