Problem Detail: Suppose a system in which addresses (physical and logical) occupy 32 bits, page size is 1024 bytes (210), and physical memory is of size 32MB. How many frames are in physical memory? Is the logical address space larger than Read More …
Author: ignougroup
Undecidable among these for turing machine
Problem Detail: Below are two questions I found in Theory of Computation book but couldn’t find its correct answers, can anyone please give correct answers with explanation? It is undecidable, whether an arbitrary Turing machine(TM) has 15 states an arbitrary TM Read More …
Understand the time complexity for this LCS (longest common subsequence) solution
Problem Detail: I would appreciate an intuitive way to find the time complexity of dynamic programming problems. Can anyone explain me “#subproblems * time/subproblem”? I am not able to grok it. Code for LCS – public static String findLCS(String str1, String Read More …
Why do low fitness individuals have a chance to survive to the next generation?
Problem Detail: I am currently reading and watching about genetic algorithm and I find it very interesting (I haven’t had the chance to study it while I was at the university). I understand that mutations are based on probability (randomness is Read More …
Relation between simple and regular grammars
Problem Detail: I am reading “An Introduction to Formal Languages and Automata” written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) grammars which are very similar to each Read More …
Range update + range query with binary indexed trees
Problem Detail: I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates. I found the following sources: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/ http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree http://apps.topcoder.com/forums/?module=Thread&threadID=756271&start=0&mc=4#1579597 But even after reading through all of them I Read More …
Finite state automata, multiple completion states?
Problem Detail: I’m currently studying for an exam for a course where some of the material covered included finite state automata, I’ve completed a question and I’m not sure about my answer. Question http://i.stack.imgur.com/vDFax.png My Answer http://i.stack.imgur.com/rSnEv.png Are multiple completion states Read More …
Sorting functions by asymptotic growth
Problem Detail: Assume I have a list of functions, for example $qquad n^{log log(n)}, 2^n, n!, n^3, n ln n, dots$ How do I sort them asymptotically, i.e. after the relation defined by $qquad f leq_O g iff f in O(g)$, Read More …
Destination-based vs source-based routing
Problem Detail: I understand that destination-based routing builds the “route” from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-based routing the opposite is true: the route is Read More …
What can Idris not do by giving up Turing completeness?
Problem Detail: I know that Idris has dependent types but isn’t turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types? I guess this is quite a specific question, but I Read More …
