Problem Detail: In various discussions of the merits of functional programming, the phrase referential transparency or equational reasoning is often listed. My question is – are these roughly the same thing? (One being the concept, and the second being the process Read More …
Blog
[Solved]: PDA with N-Stacks comparison with Turing Machines
Problem Detail: Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation? It’s been told that PDA with 2-Stacks is equally powerful to Turning Machine. But what if we add more stacks i.e. Read More …
[Solved]: Analyzing load balancing schemes to minimize overall execution time
Problem Detail: Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given workload will take is given by a Read More …
[Solved]: Why do Bloom filters work?
Problem Detail: Let’s say I am using Bloom filters to create a function to check if a word exists in a document or not. If I pick a hash function to fill out a bit bucket for all words in my Read More …
[Solved]: Show that the Turing Machine domain can be viewed as a classical planning domain
Problem Detail: This is one of my assignments. I am not able to comprehend how to reduce the Turing machine domain to Classical planning domain. My understanding is that we have to essentially perform complexity analysis of classical planning domain. So Read More …
[Solved]: this automata is NFA or DFA?
Problem Detail: That’s my question, since it has two symbols but go to a single state, is DFA or NFA? Asked By : Teo Answered By : Yuval Filmus First of all, every deterministic finite automaton is a fortiori a non-deterministic finite Read More …
[Solved]: Subgraph isomorphism in planar graphs
Problem Detail: I’m a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs. I’m trying to find subgraph matches to map an application graph (the subgraph) to a network-on-chip (the large graph). I have already implemented Read More …
[Solved]: $log^*(n)$ runtime analysis
Problem Detail: So I know that $log^*$ means iterated logarithm, so $log^*(3)$ = $(loglogloglog…)$ until $n leq 1$. I’m trying to solve the following: is $log^*(2^{2^n})$ little $o$, little $omega$, or $Theta$ of ${log^*(n)}^2$ In terms of the interior functions, $log^*(2^{2^n})$ Read More …
[Solved]: CoNP and NPhard intersection
Problem Detail: Can a problem be both NP-Hard and CoNP? Can a problem be both NP and CoNP-Hard? Asked By : Turbo Answered By : Peter Shor There is a problem which is both NP-hard and in coNP if and only if NP Read More …
[Solved]: What would dynamically-typed languages actually do if type enforcement was removed?
Problem Detail: I program in Python, which is a well-known dynamically typed language. I understand dynamic typing to mean mainly that “operations” (in a loose sense) in the language are either allowed or denied (raise an exception) based on the type Read More …
