Problem Detail: There are numerous possibilities to implement a software mutex using only shared memory (e.g. Dekker’s algorithm). Recently I’ve read the following from a paper “Wait-free Synchronization” by M. Herlihy: there exists no two-process consensus protocol using multireader/multiwriter atomic registers. And Read More …
Blog
[Solved]: Hash table versus binary search lookup for unchanging data
Problem Detail: Let’s say I have some static, unchanging data (no adds, modifies or deletes) which is looked up by a string value, and that I’m looking to minimize size in memory while also trying to minimize lookup time. It seems Read More …
[Solved]: Minimize Deterministic Finite Automata with no accepting states
Problem Detail: I have a finite automaton with no final/accepting states, so F is empty. How do I minimize it? I got this on a test and I didn’t know how to approach the problem because the automaton had no accepting Read More …
[Solved]: Practical applications of Weighted Independent Set in path graph?
Problem Detail: Consider Weighted Independent Set in a path graph, i.e., a graph where all the vertices are in a single path. Does this problem have practical applications? What are some? This problem is used in many CS courses as an Read More …
[Solved]: How to build/recognise a deadlock-free order of resources
Problem Detail: I have been faced with a problem where three concurrent processes X, Y ,Z execute three different code segments that access and update certain shared variables. Before entering the respective code segments : Process X executes the P operation Read More …
[Solved]: Maximum independent nodes subset algorithm with strong constraint
Problem Detail: I’ve a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints: The selected nodes must be the optimal solution (maximal sum of weight). If one node is flagged no adjacent nodes Read More …
[Solved]: How do I classify my emulator input optimization problem, and with which algorithm should I approach it?
Problem Detail: Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) as: What Read More …
[Solved]: MGU and Variable Standardization – CNF
Problem Detail: I have been reading on converting first order logic sentences to conjunctive normal form, and then performing resolution. One of the steps of converting to CNF, is to Standardize variables: rename all variables so that each quantifier has its Read More …
[Solved]: Removing arbitrary element from Max Heap
Problem Detail: Which of the following strategies is more feasible? Strategy 1: Remove the element from the array, compress the array and reheapify. Strategy 2: Update the value of this node to the current maximum value in the heap + 1, Read More …
[Solved]: Does a regular expression model the empty language if it contains symbols not in the alphabet?
Problem Detail: Suppose $Sigma = { a,b }$ and the regular expression $(a^*b+dc)^*(b^*d + ad)^*$. Is it equal to $varnothing$? So I have a regular expression like this: $(a^*b+dc)^*$. As only $(a,b) in Sigma$, I see that: $dc=varnothing$ So $(a^*b+dc)^*=(a^*b)^*$. Then: Read More …
