Problem Detail: I already have a solution for this problem but it’s just not making sense to me. Here is the problem (It’s from Introduction to Algorithms by CLRS found in CH.4): Show $T(n) = 2T(lfloor n/2 rfloor +17)+n$ is $O(n Read More …
Blog
Equivalence of regular expressions
Problem Detail: Is it possible, in general, to determine whether two regular expressions admit the same set of strings? Also, in particular, is it possible to determine whether a given regular expression admits the same set of strings as the regular Read More …
What is an intuitive way to explain and understand De Morgan’s Law?
Problem Detail: De Morgan’s Law is often introduced in an introductory mathematics for computer science course, and I often see it as a way to turn statements from AND to OR by negating terms. Is there a more intuitive explanation for Read More …
Least number of comparisons needed to sort (order) 5 elements
Problem Detail: Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible outcomes. Therefore a binary tree for the Read More …
Why is the k-bounded spanning tree problem NP-complete?
Problem Detail: The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$. I realize Read More …
Algorithm to find the mode in a unimodal array
Problem Detail: I am given the following problem in an Algorithms class: Assume that you are given an array A[1 . . . n] of distinct numbers. You are told that the sequence of numbers in the array is unimodal, in Read More …
Solving the recurrence T(n) = 3T(n-2) with iterative method
Problem Detail: It’s been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given: $$T(n) = 3T(n-2)$$ My first step was to iteratively substitute terms to Read More …
Recurrence relation for time complexity $T(n) = T(n-1) + n^2$
Problem Detail: I’m looking for a $Theta$ approximation of $$T(n) = T(n-1) + cn^{2}$$ This is what I have so far: $$ begin{align*} T(n-1)& = T(n-2) + c(n-1)^2 T(n) &= T(n-2) + c(n-1) + cn^2[1ex] T(n-2) &= T(n-3) + c(n-2)^2 T(n) Read More …
How to determine the maximum RAM capacity for an operating system?
Problem Detail: I was curious to know what limits the max RAM capacity for an OS while reading about microprocessors being 32-bit and 64-bit. I know that limit for 32-bit OS is 4GB and for 64-bit OS is 16 Exabytes, but Read More …
Rice Theorem – What is non-trivial property?
Problem Detail: Every nontrivial property of the recursively enumerable languages is undecidable. What exactly is nontrivial property? Asked By : Alvar Answered By : Untitled A property that holds for every machine or holds for none is trivial. Rice’s theorem does not apply Read More …
