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 …
Category: Uncategorized
[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]: 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]: 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]: Software mutexes and consensus number 1
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 …
[Solved]: Maxima of diagonals in a column wise and row wise sorted matrix
Problem Detail: Let ${a_i}$ and ${b_i}$ be non-decreasing sequences of non-negative integers. How fast can one find $$c_j=max_{0 leq i< j}{a_i+b_{j-i-1}}$$ for all $0leq jleq n-1$? Naively, it takes $O(n^2)$ time, but I’m hoping monotonicity can help here. It’s easy to Read More …
[Solved]: Can Euclidean TSP be exactly solved in time better than (sym)metric TSP?
Problem Detail: Symmetric/Metric TSP can be solved via the Held-Karp algorithm in $mathcal O(n^2 2^n)$. See A dynamic programming approach to sequencing problems by Michael Held and Richard M. Karp, 1962. In Exact Algorithms for NP-Hard Problems: A Survey (PDF) Woeginger Read More …
[Solved]: Why are syntax trees used in genetic programming?
Problem Detail: Reading a course on genetic programming, the first chapter describes the syntax tree as the basic representation of programs in genetic programming. What are the reasons leading to the choice of a syntax tree in genetic programming? Are there Read More …
[Solved]: Language with $loglog n$ space complexity?
Problem Detail: We know that every non-regular language can be recognized with $ Omega (loglog n) $ space complexity. I’m looking for an example of a language which is $ Theta (loglog n) $ space complexity (if such exists). Asked By Read More …
[Solved]: randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $frac{2}{3}$
Problem Detail: I’m trying to practice myself with random algorithms. Lets call a CNF formula over n variables s-formula if it is either unsatisable or it has at least $frac{2^n}{n^{10}}$ satisfying assignments. I would like your help with show a randomized Read More …
