Problem Detail: Just a quick question, If i were to alter the general DFS algorithm to do this: minDFS(Vertex v) { if (!v.getVisted()) { v.setVisited(); Vertex temp = findClosestVertex(); graph.addEdge(v, temp); minDFS(temp); } } Would I eventually (at the end of Read More …
Author: ignougroup
[Solved]: What is a compact way to represent a partition of a set?
Problem Detail: There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly space-efficient. What is a space-efficient way to represent a partition of a Read More …
[Solved]: Why can PDAs only write one symbol to the stack according to this definition?
Problem Detail: This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser. The transition is defined as $$ delta: Qtimes Sigma_varepsilon times Gamma_varepsilon to P(Qtimes Gamma_varepsilon) $$ where $Q$ is Read More …
[Solved]: Show that the following algorithm doesn’t always find the optimal matching
Problem Detail: Consider the following algorithm for the maximum matching problem: Sort all nodes by their $deg(v)$ Take the node with minimal $deg(v)$ Take a random edge $(u,v)$ $in$ $E$ Add $(u,v)$ to $M$ Delete all edges of $u$ and $v$ Read More …
[Solved]: What is the type theory judgement symbol?
Problem Detail: In type theory judgements are often presented with the following syntax: My question is what is that symbol in the middle called? All the papers I’ve found seem to use an image rather than a unicode character so I Read More …
[Solved]: What complexity class would this version of generalized chess fall?
Problem Detail: By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem “Given an nxn board with a given position, can white force a win?” because the proof would require an exponential amount Read More …
[Solved]: Are all known algorithms for solving NP-complete problems constructive?
Problem Detail: Are there any known algorithms that correctly output “yes” to an NP-complete problem without implicitly generating a certificate? I understand that it is straightforward to turn a satisfiability oracle into a satisfying-assignment finder: just iterate over the variables, each Read More …
[Solved]: Organisation and Architecture of Quantum Computers
Problem Detail: What are devices and their interconnections used alongwith Quantum Processors? Are they compatible with hardware devices like Cache, RAM, Disks of current computers? Asked By : check123 Answered By : Artem Kaznatcheev What you describe as current computers is known as Read More …
[Solved]: What exactly is a clique cover problem?
Problem Detail: I am really confused about clique problem and clique cover problem. I tried googling it,but I don’t see to be able to visualise the clique cover problem. Asked By : user1675999 Answered By : William Macrae A clique is a simple Read More …
[Solved]: (Possibly Easy) Formal Language Question
Problem Detail: I am looking at a “practice test” for a Theory of Computation class. It was a test in a previous year. I am asked to prove that, given L1 and L2 are regular, the union and difference are both Read More …
