Problem Detail: I am trying to understand how IDDFS works by reading a wikipedia article on it. (If someone has a better literature on the subject, don’t hesitate to post). Pseudocode is as follows: IDDFS(root, goal) { depth = 0 for(i=1, Read More …
Blog
[Solved]: Calculating Binet’s formula for Fibonacci numbers with arbitrary precision
Problem Detail: Binet’s formula for the nth Fibonacci numbers is remarkable because the equation “converts” via a few arithmetic operations an irrational number $phi$ into an integer sequence. However, using finite precision arithmetic, one would always have some (small) roundoff error. Read More …
[Solved]: Why do we use stacks and not queues on system-level?
Problem Detail: From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations. Why don’t we use queues and FIFO operations? It’s just a matter of moving pointers anyway. Asked By Read More …
[Solved]: Binary tree traversals reversed
Problem Detail: Am I correct in saying that traverse(node): if node is null, return print node traverse(node’s right subtree) traverse(node’s left subtree) would produce output that is the reverse of post-order traversal? post-order(node): if node is null, return post-order(node’s left subtree) Read More …
[Solved]: Why is Oracle Turing Machine important?
Problem Detail: As you know, an Oracle Turing Machine (OTM) is a “black box” which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church’s Thesis it is impossible to design an algorithm which Read More …
[Solved]: Big Oh vs Big Theta
Problem Detail: I mathematically understand $f(n) in O(g(n))$ : $f(n)$ does not grow faster than $g(n)$. More formally, $exists c, n_0$ s.t. $f(n) leq cg(n) forall n geq n_0$. Similarly, $f(n) in Theta(g(n))$ means that $f(n)$ grows approximately as fast as Read More …
[Solved]: Is $L= { a^ib^j mid jneq i and jneq2i } $ context free?
Problem Detail: $L = { a^ib^j mid jneq i and jneq2i } $ Is this language a context free language? If yes give a PDA. If no, give a proof. The pumping lemma for context free languages doesn’t seem to work Read More …
[Solved]: How, in hardware, MIPS can access a word in the middle of an address
Problem Detail: This is am example of a RAM address in the MIPS architecture (32 bits) I can imagine the RAM as having 32 pins just to inform the RAM address I want to access, so I can access each of Read More …
[Solved]: Find the number of topological sorts in a tree
Problem Detail: Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself. I’ve tried thinking what would be the best for m to define it but couldn’t get anything specific. Read More …
[Solved]: Confused by Floating Point Spacing
Problem Detail: I’m currently taking a numerical analysis class in college and we’re covering floating point systems. For the most part, I have a good grasp on it. However, something I can’t seem to visualize, and haven’t seen any totally lucid Read More …
