Problem Detail: I am looking for an algorithm with time complexity in $mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree. A caterpillar tree is a tree that has a path to which all nodes are connected Read More …
Author: ignougroup
[Solved]: The “CPS” approach has done great harm to performance in SML/NJ; reasoning desired
Problem Detail: In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated: Note that the “CPS” approach has done great harm to performance in SML/NJ. Its physical evaluation Read More …
[Solved]: How to random-generate a graph with Pareto-Lognormal degree nodes?
Problem Detail: I have read that the degree of nodes in a “knowledge” graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution. Where can I find a kind of algorithm that Read More …
[Solved]: Counting the number of N-dimensional coprime integer vectors
Problem Detail: I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors. The vectors in my set are $N$-dimensional integer vectors whose components are bounded on the top Read More …
[Solved]: Showing that tournament sort requrires O(n log n) comparisons
Problem Detail: I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has Read More …
[Solved]: The control in the Turing Machine
Problem Detail: My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on Read More …
[Solved]: Is {ww^r ww^r} a context-free language?
Problem Detail: Is the language $L = {w w^r w w^r mid w in Sigma^*}$ context-free? ($w^r$ is the reversal of $w$.) I heard that by using the pumping lemma, we can only prove that a language is not context-free, but Read More …
[Solved]: Formal notion of a call graph for Turing machines
Problem Detail: To most computer programs one can assign a “call graph“. Is there a formal notion of call graphs of Turing machines? Motivation is, that one could intuitively call a decidable language $L$ “irreducible” if every Turing machine which decides Read More …
[Solved]: Why is automated theorem proving impossible?
Problem Detail: As far I know, in general case there is no Turing machine which could get any theorem on its input and produce its proof on its output. Why is it so? Asked By : peterh Answered By : Jake We have Read More …
[Solved]: Why would you use a monitor instead of a semaphore?
Problem Detail: I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do not understand why I would use a Read More …
