Question Detail: I’m studying CPU’s and I know how it reads a program from the memory and execute its instructions. I also understand that an OS separates programs in processes, and then alternate between each one so fast that you think Read More …
Blog
Is this intersection of DFAs correct?
Question Detail: I’m constructing a deterministic finite automata (DFA) for a language of all strings defined over ${0,1}$ whose length is even and number of $1$s is odd. I constructed each DFA separately and then combined: Is the given procedure for Read More …
What would be the real-world implications of a constructive $P=NP$ proof?
Question Detail: I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely “proven” to be true with a provided solution, it would open the door for solving numerous problems within the realm of computer Read More …
Hierarchical Paging
Question Detail: Suppose I have a system with 32-bit logical and 16-bit physical address spaces, and the page size is 512 bytes. For simplicity, ignore the valid/invalid bits in the page table. How many sections will the logical address be divided Read More …
What determines the “speed” of a programming language?
Question Detail: Suppose a program was written in two distinct languages, let them be language X and language Y, if their compilers generate the same byte code, why I should use language X instead of the language Y? What defines that Read More …
Proving a binary heap has $lceil n/2 rceil$ leaves
Question Detail: I’m trying to prove that a binary heap with $n$ nodes has exactly $leftlceil frac{n}{2} rightrceil$ leaves, given that the heap is built in the following way: Each new node is inserted via percolate up. This means that each Read More …
Examples of context-free languages with a non-context-free complements
Question Detail: Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia. But this only shows that one of the three languages $A$, $B$, and $overline A cup overline B$ Read More …
Formalization of the shortest path algorithm to a linear program
Question Detail: I’m trying to understand a formalization of the shortest path algorithm to a linear programming problem: For a graph $G=(E,V)$, we defined $F(v)={e in E mid t(e)=v }$ and $B(v)={ e in E mid h(e)=v}$ where $t(e)$ is a Read More …
In-place algorithm for interleaving an array
Question Detail: You are given an array of $2n$ elements $$a_1, a_2, dots, a_n, b_1, b_2, dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like $$b_1, a_1, b_2, a_2, dots Read More …
If the speed of electrical charge hasn't changed, how have computers become faster?
Question Detail: Everyone knows computing speed has drastically increased since their invention, and it looks set to continue. But one thing is puzzling me: if you ran an electrical current through a material today, it would travel at the same speed Read More …
