Problem Detail: A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream $012345$, I am trying each of Read More …
Category: Uncategorized
[Solved]: JIT, AOT, Interpretation: What are differences between them?
Problem Detail: I’m a beginner in Compilation. My understanding is that Interpretation means Interpreter takes source program as input and produce the result of this program.(source -> Interpreter -> run on the machine) Compilation means Compiler take source program as input Read More …
[Solved]: Computing maximum-cost subtree that uses at most k edges
Problem Detail: I’m looking for an efficient algorithm for the following problem: Input: a binary, complete tree with a cost on each edge, an integer $k$ Output: the maximum-cost subtree containing $le k$ edges For purposes of this problem, a subtree Read More …
[Solved]: Under what conditions is K-means clustering transformation-invariant?
Problem Detail: Given a set of data points $X = {x_1, x_2, ldots, x_m}$ where $x_i in mathbb{R}^d$ we run K-means on $X$ and obtain the clusters $c_1, c_2, ldots, c_k$. Now, if we create a new dataset $Y = {y_1, Read More …
[Solved]: What are the difference between and consequences of using type parameters and type indexes?
Problem Detail: In type theories, like Coq’s, we can define a type with parameters, like this: Inductive ListP (Element : Type) : Type := NilP : ListP Element | ConsP : Element -> ListP Element -> ListP Element. Alternatively, we can Read More …
[Solved]: Pumping Lemma for $L = left { a^{c}mid text{c is a composite number} right }$
Problem Detail: $L = left { a^{c}mid text{c is a composite number} right }$ I feel that this is not a context-free language as checking this constraint requires divisibility checking, but I am facing a hard time in proving that $L$ Read More …
[Solved]: Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?
Problem Detail: My best attempt at a specific case of the problem where $n =$ 256: For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the Read More …
[Solved]: On the minimum order of a maximal independent set in cycle graphs and path graphs
Problem Detail: I can see from this question that a $K_{r + 1}$-free graph with $n$ vertices and $e$ edges contains an independent set of order at least $$frac{n}{2e/n + 1} tag{1} $$ Since for a $C_{n}$/$P_{n}$ we know how many Read More …
[Solved]: Why does this graph show the tightness of MST heuristic’s 2-approximation bound?
Problem Detail: This is a homework problem I’ve been given and I’ve been raking my brain for hours (so I’m satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a wheel graph, Read More …
[Solved]: How does a regular language satisfies the second condition of the pumping lemma
Problem Detail: I’m a little bit confused about the second condition of the pumping lemma which are: $|y|geq1$ $|xy|leq p$ $forall i geq 0:xyizin L$ I don’t understand why the length of substrings $xy$ has to be less than the pumping Read More …
