Problem Detail: I am unable to understand that what the characteristic path length (CPL) of a graph is. In one of its definitions, it is written that it is defined as the median of the means of the shortest path lengths Read More …
Author: ignougroup
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 …
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 …
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 …
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 …
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 …
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 …
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 …
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 …
Halting problem reducing to the blank tape halting problem
Problem Detail: I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this. The blank tape problem takes a machine and an empty tape and tells Read More …
