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 …
Author: ignougroup
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 …
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 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 …
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 …
Does an Operating System inject its own machine code when you open a program?
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 …
Why is encrypting with the same one-time-pad not good?
Question Detail: To encrypt a message $m_1$ with a one-time-pad key $k$ you do $Enc(m_1,k) = m_1 oplus k$. If you use the same $k$ to encrypt a different message $m_2$ you get $Enc(m_2,k) = m_2 oplus k$, and if you Read More …
Finding the path of a negative weight cycle using Bellman-Ford
Question Detail: I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I’m actually interested in, is given some starting vertex and a graph, which path do I actually trace to Read More …
“For small values of n, O(n) can be treated as if it’s O(1)”
Question Detail: I’ve heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it’s O(1). Example: The motivation for doing so is based on the incorrect idea that O(1) is always better than O(lg Read More …
What is the difference between halting, accepting, and deciding in the context of Turing machines?
Question Detail: Does accepting mean that the TM will read and recognize a char from the cell it’s currently reading from? And is it the case that a TM halts iff the input is decidable? Asked By : sdfasdgasg Best Answer from Read More …
