Tag Info

Hot answers tagged

3

Note: "Prove the existence of a maximum matching." That is not to say that every maximum matching saturates $v$ (it is possible that some do not). Consider any maximum matching, $M$ (guaranteed to exist). Either $v$ is saturated in $M$ or it isn't. If it is, then we are done and the matching we are looking at satisfies the claim. Suppose then that $v$ ...


2

Quicksort boils down to: Selecting a pivot Separate big list into a "smaller than pivot" list $S_{1}$ and "larger than pivot" list $S_{2}$ Sort $S_{1}$ and $S_{2}$ separately, call result $S_{1}'$ and $S_{2}'$. Combine $S_{1}'$ and $S_{2}'$ and pivot into final, sorted list $S'$. Selecting a pivot randomly is constant time. Hence, it follows that $T(n) ...


2

The Knapsack problem is NP, and any problem in NP can be reduced to an NP complete problem (Cook's Theorem). So to show that the knapsack problem is NP complete it is sufficient to show that an NP-complete problem is reducible to the Knapsack problem. We want to use the exact cover problem to show this. A lot of such reductions can be found in the paper of ...


2

Actually all kinds of people have tried to develop models of computation that can do more than a Turing Machine can. Just one little problem: you can't build them. If you figure out how to build one, and you're really good with patent litigation, NDAs and building businesses generally, you'll be a rich man. If you figure out how to build one, and you're ...


2

Notice that $o(1) \in O(1)$, and $O(1)$ is a constant. So $\lim_{n \to \infty} (1 + o(1)) = c$, for some finite constant $c$. So doing some algebraic manipulations: $$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} (1 + o(1)) = c$$ This gives us $f(n) \in \Theta(g(n))$.


1

I'm fairly certain it's just pseudocode. If you were to make it pretty, it would look like $$\sum_{n,k}\frac{T(n,k)x^2y^k}{n!}=1+\ln\left(\sum_{n=0}^{\infty}{\frac{(4+y)^{\binom{n}{2}}x^n}{n!}}\right)$$ This is the exponential generating function for the sequence. The formula that is displayed on the site is actually ...


1

The algorithm should be able to sort $n$ integers in the range $0,\ldots, n^2-1$: We can view suchintegers $x$ as pairs $(a,b)\in\{0,\ldots,n-1\}^2$ with $x=na+b$. The algorithm first sorts on $b$ and then on $a$, with a stable sorting method. The sorting itself is count sorting: The number of occurences of each value is counted (first two loops); then the ...


1

I'll show a possible mapping from exact cover to knapsack by example. Consider a particular exact cover problem consisting of $n=4$ elements $\langle x_0, x_1, x_2, x_3 \rangle$. Now suppose we have a set $S_i = \{x_1, x_3\}$. We can alternatively represent $S_i$ with a $0/1$ list $L_i = \langle 0, 1, 0, 1 \rangle$ (the $j$-th element of $L_i$ is $1$ iff ...


1

The maximum number of edges is clearly achieved when all the components are complete. Moreover the maximum number of edges is achieved when all of the components except one have one vertex. The proof is by contradiction. Suppose the maximum is achieved in another case. Then there exist two components with more than one vertex say the number of vertices are ...


1

The relation describes expected runtime. Each stage of recursion creates two subproblems of size $x$ and $n-x$, where $x$ is a random variable uniformly distributed over $\{1, ..., n\}$. What we are modeling is the probability that our pivot element is the $x^{th}$ largest element. Our hypothesis is that there is an equal probability for it to be any of the ...


1

Classics: Introduction to Metamathematics by S.C. Kleene. One of the first books about computation theory. General introduction to the mathematical logic. Includes very basic set theory, first order logic, formal number theory (including Gödel), recursive functions and Turing machines. Centered around the logic. See Teach Yourself Logic, #8. The Big Books — ...


1

I'm partial to Ullman, Hopcroft's text. Jeff Ullman runs a Coursera course on Automata theory, and I have heard very good things from someone I know who is a linguist. The text gives a very comprehensive overview of formal languages and automata, as well as issues of computability and complexity. I think it is very thorough and well done, plus having a ...


1

That depends on the tree, the order and what actually in-order means in your case. In most situations: yes, the sequence produced would be ascending. Usually BSTs are sorted that left child is smaller than the parent and right child is bigger than the parent. And similarly in-order traversal goes to the left child first, then parent and then right child. In ...



Only top voted, non community-wiki answers of a minimum length are eligible