Problem Detail: We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers. The algorithm was: Given an array A of length n: Make a flag array B Read More …
Author: ignougroup
Why is the halting problem unsolvable by a turing machine?
Problem Detail: So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable. So any human can determine if a problem halts with rigorous inspection, so why can’t a very advanced, Read More …
Bellman-Ford algorithm – Why can edges be updated out of order?
Problem Detail: The Bellman-Ford algorithm determines the shortest path from a source $s$ to all other vertices. Initially the distance between $s$ and all other vertices is set to $infty$. Then the shortest path from $s$ to each vertex is computed; Read More …
Constructing PDA for $a^{2n} b^{3n}$
Problem Detail: So I have been given the task of creating an PDA that recognises the language ${a^{2n} b^{3n} mid n = 0,1,2,dots}$. Am I right in thinking that it needs to have at least 3 times number of $b$’s than Read More …
“NP-complete” optimization problems
Problem Detail: I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. However, I am not exactly sure what the term NP-complete Read More …
Counting and finding all perfect/maximum matchings in general graphs
Problem Detail: Recently i’ve been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm for finding all maximum/perfect matchings in Read More …
How to prove a problem is NOT NP-Complete?
Problem Detail: Is there any general technique for proving a problem NOT being NP-Complete? I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of any real solution, Read More …
How does this Turing machine accept $a^n b^n$?
Problem Detail: I’m reading this tutorial from the University of Illinois about Turing Machines, and I don’t understand something. They give a pseudocode algorithm for an machine that accepts strings from the language $L = {0^n1^n}$ and a diagram of the Read More …
Using induction to prove a big O notation
Problem Detail: I’m trying to prove that the following recurrence relation has a runtime of O(n): fac(0) = 1 fac(n+1) = (n + 1) * fac(n) I think that I can use induction in the following manner: Base case If n=0 Read More …
Using Amdahl’s law how do you determine execution time after an improvement?
Problem Detail: Speeding up a new floating-point unit by 2 slows down data cache accesses by a factor of 2/3 (or a 1.5 slowdown for data caches). If old FP unit took 20% of program’s execution time and data cache accesses Read More …
