Problem Detail: As title. When we want to request following page numbers 2,4,4,2,5,2,1,1,3,1, is clock replacement better? What are the advantages and disadvantages of them? Thanks~ Asked By : Echo0831 Answered By : Rick Decker Coincidentally, for your reference string, both LRU and Read More …
Blog
[Solved]: How to partition a set into a given number of disjoint subsets subject to some conditions?
Problem Detail: I am given a set $Atriangleq{1,ldots,k}$, an integer $sleqslant k$, and non-negative integers $a_{ij}$. My problem is to find $s$ disjoint subsets $S_j$ of ${1,ldots,k}$ such that: $bigcup_{j=1}^s S_j=A$; and $|S_j|leqslant a_{ij}$ for all $iin S_j$ and $j=1,ldots,s$. How Read More …
[Solved]: Is DSPACE properly contained in NSPACE?
Problem Detail: It may be a dumb question, but is $mathsf{DSPACE}(f(n)) subset mathsf{NSPACE}(f(n))$ or is $mathsf{DSPACE}(f(n)) subseteq mathsf{NSPACE}(f(n))$? In other words, is the containment relation proper or not? Wikipedia says the first one, while the ComplexityZoo says the other one. Asked Read More …
[Solved]: High maths for game theory
Problem Detail: I am a starting Ph.D. student in computer science, and I am trying to understand some classic game-theory papers, such as those by Nash, Kalai and Smorodinsky. But I find it hard to understand the mathematical parts. It seems Read More …
[Solved]: Longest simple walk in a complete graph
Problem Detail: A simple walk is a path that does not contain the same edge twice. A simple walk can contain circuits and can be a circuit itself. It just shouldn’t have the same edge twice. A simple undirected graph is Read More …
[Solved]: Converting a non-planar graph to planar
Problem Detail: Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness. Besides connectedness, $G$ Read More …
[Solved]: Does this mean $P = NP$
Problem Detail: I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser’s “Theory of Computation” (2013 edition). My question is based Read More …
[Solved]: Which computational model is used to analyse the runtime of matrix multiplication algorithms?
Problem Detail: Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen’s algorithm and similar things), I have never found any explicit and satisfactory reference to a model of computation, which is used to measure this Read More …
[Solved]: Why is determining the size of a maximum independent set or a clique in P?
Problem Detail: I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to finding clique size, Read More …
[Solved]: Does stay put TM recognizes same languages as standard TM
Problem Detail: I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or symbols). I am trying to figure Read More …
