Problem Detail: Is there a sequence of undirected graphs ${C_n}_{nin mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$? is known to be in class Read More …
Author: ignougroup
[Solved]: Decidability of languages
Problem Detail: $L_1$ is a recursively enumerable language over some alphabet $Sigma$. An algorithm effectively enumerates its words as $w_1, w_2, …$. $L_2$ is another language over $Sigma cup {#}$ as ${w_i#w_j : w_i, w_j in L_1, i < j}$ Read More …
[Solved]: Maximal difference of height between two leaves in an AVL tree
Problem Detail: What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference. I am not sure about my answer – I think that it is $O(log n)$, given the fact Read More …
[Solved]: Is it admited to give the complexity of a function regarding the resulting data structure?
Problem Detail: Assume that we have a data structure which uses $O(log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$. The time complexity of $f$ is $O(n_{_{old}})$ Read More …
[Solved]: Conceptual question about entropy and information
Problem Detail: Shannon’s entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that we are more uncertain about what will happen next. What Read More …
[Solved]: Longest cycle in a digraph
Problem Detail: Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem? Do we know its complexity? Read More …
[Solved]: The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?
Problem Detail: I have often read that Hindley-Milner extended to allow polymorphic recursion is undecidable. However is the term used what is actually meant? Or do people actually mean semidecidable when they mention that? I ask this before I’ve recently found Read More …
[Solved]: Algorithm to check the distance between integers
Problem Detail: I have the next problem, and I was wondering whether it exists a way to solve it without having to iterate around all the array in the worst case. I have a sorted array of pairwise distinct integers, say Read More …
[Solved]: Can we do better than $O(nlog n)$ building a balanced binary tree?
Problem Detail: I’m (foolishly it turns out) confident that the answer to this question is no. So why am I asking? Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-structure for which he asserts various properties. Read More …
[Solved]: Does location transparency imply access transparency?
Problem Detail: In distributed systems theory, I have found the definition that a distributed system requires, among others, location and access transparency. I was wondering if location transparency does not already include access transparency. Wikipedia defines the two as follows: Access Read More …
