Problem Detail: There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters). One of the nodes, say $s$, wants to know $n$. How can it do Read More …
Category: Uncategorized
[Solved]: Getting started with Program Analysis
Problem Detail: I’m looking for resources on getting started with program analysis. The only book I’ve found on the topic is the Nielson & Nielson book. Other than that, it seems like there are only “compiler” books where “program analysis” would Read More …
[Solved]: Approximation of minimum bandwidth on binary trees
Problem Detail: Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. The decision problem is NP-complete even for binary trees. Complexity Results for Bandwidth Minimization. Read More …
[Solved]: Non-erasing Turing machines and loss of generality
Problem Detail: A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank. I’m trying to understand whether there is loss of generality because of this restriction. My Read More …
[Solved]: Generate random weighted graphs representing a road network
Problem Detail: in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge. My current solution for connecting Read More …
[Solved]: Number of processes needed to maximize CPU utilization under I/O wait conditions
Problem Detail: A computer has 2 GB of RAM of which the operating system occupies 256 MB. The processes are all 128 MB (for simplicity) and have the same characteristics. If the goal is 99% CPU utilization, what is the maximum Read More …
[Solved]: Determining whether a CFG is $LL(k)$ for any $k$?
Problem Detail: In Knuth’s original paper on $LR(k)$ grammars, he proved that the decision problem “Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?” is undecidable. Is there a similar result showing that it is Read More …
[Solved]: Assign undirected edges in a mixed graph to make graph cyclic/acyclic
Problem Detail: What is the complexity of the following problem? Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle. It doesn’t “feel” like an NP-hard problem, Read More …
[Solved]: Most common subset of size $k$
Problem Detail: I’m trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size Read More …
[Solved]: Which measure of sortedness explains the phase transition in Quicksort’s runtime?
Problem Detail: I’m currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n log n)$ as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of Read More …
