Problem Detail: I have a problem with classifying certain CPUs to the proper classes of Flynn’s Taxonomy. 1. Zilog Z80 According to this article on Sega Retro, Z80 has limited abilities to be classified as SIMD: a limited ability for SIMD Read More …
Blog
Why is the name half-adder used to represent the half-adder?
Problem Detail: I have recently came across half-adders and full adders in my Logic Network lectures. I have somewhat understood the theory, but I am still unable to understand the reason why they called them in that name? I mean, is Read More …
Shortest path in weighted(positive or negative) undirected graph
Problem Detail: I have to find an algorithm that finds the SSSP (single-source shortest path – shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different shortest paths, the algorithm should Read More …
Why are the total functions not enumerable?
Problem Detail: We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) Read More …
What are Markov chains?
Problem Detail: I’m currently reading some papers about Markov chain lumping and I’m failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-space lumping in Markov chains they provide Read More …
How to analyze/test a binary search algorithm?
Problem Detail: I was asked to “Compute the average runtime for a binary search, ordered array, and the key is in the array.” I’m not quite sure how to approach this problem. Isn’t the runtime of binary search O(log n)? And Read More …
How can it be detected that a number generator is not really random?
Problem Detail: I heard that random number generation in computers isn’t really random, but there is no efficient algorithm to detect it. How can it be detected at all ? Asked By : URL87 Answered By : SamM Computers Being Really Random: True Read More …
Represent a real number without loss of precision
Problem Detail: Current floating point (ANSI C float, double) allow to represent an approximation of a real number. Is there any way to represent real numbers without errors? Here’s an idea I had, which is anything but perfect. For example, 1/3 Read More …
What exactly is polynomial time?
Problem Detail: I’m trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn’t find an exact definition anywhere. I assume it is the complexity that is not exponential. Do linear/constant/quadratic complexities count as polynomial? An Read More …
A Question relating to a Turing Machine with a useless state
Problem Detail: OK, so here is a question from a past test in my Theory of Computation class: A useless state in a TM is one that is never entered on any input string. Let $$mathrm{USELESS}_{mathrm{TM}} = {langle M, q rangle Read More …
