Problem Detail: I’m so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree Read More …
Author: ignougroup
[Solved]: Is this a divide-and-conquer algorithm?
Problem Detail: I’d like to start by stating this isn’t homework! I’m studying for a job interview and would appreciate a second opinion. (Well, I guess it is homework, but not for school!). I’ve written an algorithm (see pseudocode below) to Read More …
[Solved]: What’s the difference between Adaptive Control and a Kalman Filter?
Problem Detail: From my basic understanding of Adaptive Control, I understand that it uses the error and the velocity of the error to approximate the error in the solution space of a problem, thus allowing for guaranteed convergence under certain conditions Read More …
[Solved]: Complexity of 3SAT variants
Problem Detail: This question is motivated by my answer to another question in which I stated the fact that both Betweeness and Non-Betweeness problems are $NP$-complete. In the former problem there is a total order such that the betweeness constraint of Read More …
[Solved]: Is it decidable whether a pushdown automata recognizes a given regular language?
Problem Detail: The problem whether two pushdown automata recognize the same language is undecidable. The problem whether a pushdown automata recognizes the empty language is decidable, hence it is also decidable whether it recognizes a given finite language. It is undecidable Read More …
[Solved]: Prove correctness of DFA ending with ab
Problem Detail: I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts ${wab mid win {a,b}^*}$ I know that I need to prove by induction on the length of the Read More …
[Solved]: How to prove that BFS directed-graph traversal algorithm terminates?
Problem Detail: How to prove that BFS directed-graph traversal algorithm terminates? (I copy the pseudocode from here) Input: A graph G and a root v of G. procedure BFS(G,v): create a queue Q enqueue v onto Q mark v while Q Read More …
[Solved]: Proof of Ramsey’s theorem: the number of cliques or anti cliques in a graph
Problem Detail: Ramsey’s theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $frac{1}{2}log_2 n$ nodes. I tried to look it up at a few places (including Sipser) but I could not Read More …
[Solved]: Pumping lemma for CFG doubt
Problem Detail: I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought of applying it. Read More …
[Solved]: Hoare triple for assignment P{x/E} x:=E {P}
Problem Detail: I am trying to understand Hoare logic presented at Wikipedia, Hoare logic at Wikipedia Apparently, if I understand correctly, a Hoare triple $${P}~ C ~{Q}$$ means if P just before C, then Q holds immediately after C, as long Read More …
