Need help converting machine code I would appreciate some help with this question.

The 32 bit numbers below represent a MIPS instruction. identify the different fields and state which instruction it is. give the assembler source code that can be converted into this instruction.

001000|10001|10010|0000000000001111

I separated the bits and I know the first 6 bits are the opcode and given the opcode it means Addi. The last 16 bits are the immediate value which I have converted to 15. I do need help with the registers and converting the binary into the register number. I have looked everywhere and can not find an explanation. Any help would be appreciated. i know the structure takes this format:

Addi, t,s, 15

You've basically got the answer already: the s register is number 0b10001 = 17, the t register is number 0b10010 = 18.

The instruction is not quite the way you've said it: standard MIPS has the registers in the opposite order, so it's opcode rs rt immediate. The opcode is 0b001000 = 8 = ADDI; rs is 0b10001 = 17 = $s1; rt is 0b10010 = 18 = $s2; the immediate value is 0b0000000000001111 = 15.

(The prefix 0b indicates that the following number is in binary.)


Why is testing if x > y primitive recursive? $f(x,y)= 0$ if $x>y$ and $1$ otherwise.

How can prove formally that this function is primitive recursive?

Hint: One possible approach is to compose the functions $x\dot{-}y = \max(x-y,0)$ and $\delta(z) = \begin{cases} 0 & z=0, \\ 1 & z>0 \end{cases}$.


What are barriers to Genetic Programming with cyclic graphs Genetic programming uses either trees (in case of classical GP) or acyclic graphs (CGP and in a certain sense LGP), to represent evolved programs (phenotypes).

Is there any reason, why cyclic graphs aren't used?

Perhaps one reason is that constraints (perhaps somewhat arbitrary ones) would have to be imposed on what it means to interpret a program represented in this fashion.

However, recent work with CGP has actually explored the addition of cycles:
Recurrent CGP


Compare each array $i$ member to all array $j$ member where $(i > j)$ , in time less than $O(n^2)$ I am new to algorithms so sorry to ask simple question

I am working on a problem which is about array of integers, my solution is right but not good enough, because I have time exceeded exception on codeforces. I think solution where solution's time < O(n^2) would be right.

My solution:

int n;
cin >> n;

int currentScore = n;
int credits[n];
int grades[n];
for (int i = 0; i < n; i++) {
    cin >> credits[i];
    for (int j = 0; j < i; j++) {
        if (credits[i] <= credits[j]) {
            currentScore--;
        }
    }
    grades[i] = currentScore;
    currentScore = n;
}

for (int i = 0; i < n; i++) {
    cout << grades[i] << endl;
}

return 0;

Create a binary tree containing the points, either each node also containing the number of elements in each sub tree . For each candidate, determine the number of candidates arriving earlier, and having same or higher score using the tree, then add the candidates score to the tree.

Should work in O(n log n). I doubt O(n) is possible.

PS chi’s answer is a lot easier, and you probably have a library for the sorting, which is the hard part.


The Absolute Minimum Every Software Developer Absolutely, Positively Must Know about Computer Science (No Excuses!) Yes, I borrowed the title form a famous joelonsoftware post for my question because I didn't exactly know how to ask this.

I'm a professional programmer for a few years now and although I followed informatics courses in school there was a lot of stuff missing from the curriculum, as I now know but wasn't aware then. For example I didn't do any compiler theory, algorithm analysis (the Big-O), have no idea what P-NP meant etc.

So I want to catch up now!

But the field of computer science is big. Really big! So from here my question: What's the absolute minimum every software developer absolutely, positively must know about computer science (no excuses!)?

> What's the absolute minimum every software developer absolutely,
> positively must know about computer science (no excuses!)?

IMO every software developer should absolutely know (no excuses!) the quote attributed to E. W. Dijkstra:

"Computer science is no more about computers than astronomy is about telescopes"

:-D :-D


What is the intuition that 2-phase locking achieves serializability (also known as before-or-after atomicity)? I am learning 2-phase locking and its unclear to me how it achieves/guarantees before-or-after atomicity (i.e. serilizability).

I went to the following notes

http://ocw.mit.edu/resources/res-6-004-principles-of-computer-system-design-an-introduction-spring-2009/online-textbook/atomicity_open_5_0.pdf

on page 9-73 it argues informally:

"Informally, once a transaction has acquired a lock on a data
object, the value of that object is the same as it will be when the transaction reaches its
lock point, so reading that value now must yield the same result as waiting till then to
read it. Furthermore, releasing a lock on an object that it hasn’t modified must be harm
less if this transaction will never look at the object again, even to abort. A formal
argument that two-phase locking leads to correct before-or-after atomicity can be found
in most advanced texts on concurrency control and transactions"

But I didn't really understand the argument and it seems that a formal proof is not trivial or maybe too complicated. So I was seeking an alternate intuitive argument to its correctness. I don't really understand why that is the reason but if someone else has a better way of explaining it or a different perspective, it would be greatly appreciated!

I'll try to phrase it from an intuitive perspective.

Anomalies occur when there are conflicts, i.e. when two different transactions write on the same object (clearly if they only read stuff nothing can go wrong).
For example, here:

r1(x), r2(x), w1(x) // at this point, r2 read garbage

2PL is a way to prevent this kind of stuff from happening by putting a lock on every object a transaction deals with, and removing the locks when it's done.
The lock can be a read lock (when T reads an object) or a write lock (when T writes an object) and the rules are simple:

refuse a read-lock if a write-lock (from a different T) already held
refuse a write-lock if any lock (from a different T) already held.

The idea behind these is that you don't want T2 to read something that T1 is going to overwrite (see the first example), and you don't want T2 to write onto something that was previously read or written by T1.

With 2PL, when T wants to read/write on an object it will ask permissions to put a lock on it, and this permission will be granted (or denied) based on the two rules above.

In the example I gave you, with 2PL T1 would have a write-lock on x so r2(x) would not happen before w1(x) because the read-lock would not be granted (rule 1).


finding separating words (Nerode) i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me how to do so. also, if you can, would appreciate if you could check if i obtained the correct equivalence classes for both languages.

1)$L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts and ends with} \quad aa\bigg\}$

equivalence classes i've obtained:

$S_1 = \epsilon$

$S_2 = a$

$S_3 = (b+c)\sum^*+a(b+c)\sum^*$

$S_4 = aa+aaa+aa\sum^*aa$

$S_5 = aa\sum^*(b+c)a$

$S_6 = aa\sum^*(b+c)$

2)$L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$

equivalence classes i've obtained:

after joining $\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\}=\{\epsilon, a,b,bba^*\}$ and using the complementary, i've obtained:

$S_1 = \epsilon$

$S_2 = a$

$S_3 = b$

$S_4 = bba*$

$S_5 = c\Sigma^*+a\Sigma^++b(a+c)\Sigma^*+bb\Sigma^*(b+c)\Sigma^*$

how can i find the separating words? also, if you can, could you verify that i've obtained the correct results?

thank you very much!

There are systemic approaches to find the separating words (a.k.a. distinguishers).

However, for small instances of regular languages, I prefer to use plain argument in plain English sometimes. Let me use your case 1) as an example, where you have got all the equivalent classes correctly.

$L$ contains words that start and end with $aa$.
$S_1$ is the empty word.
$S_2$ is the word $a$.
$S_3$ are the words that do not start with $aa$.
$S_4$ are the words that start with $aa$ and end with $aa$.
$S_5$ are the words that start with $aa$ but do not end with $a$.
$S_6$ are the words that start with $aa$ and end with $a$ but not $aa$.

What kind of words can be attached to each group of words to make them in $L$?

$S_1$ + $L$
$S_2$ + words that start with $a$ and end with $aa$.
$S_3$ won't work
$S_4$ + $a$ or words that end with $aa$.
$S_5$ + words that end with $aa$.
$S_6$ + words that end with $a$.

Now that we know these completion groups of words, it is easy to find the separating words.

For example, $S_1$ and $S_2$. We need a word that is in $L$ or that starts with $a$ and ends with $aa$, but not both. The word $abaa$ will do.

For example, $S_5$ and $S_6$. We need a word that ends with $aa$ or that ends with $a$ but not both. The word $a$ will do.


FFT-less $O(n\log n)$ algorithm for pairwise sums Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$.

We are interested in finding the counts of all the possible pairwise sums $S_{ij} = a_i + a_j$. ($i = j$ is allowed).

One algorithm is to construct the polynomial $P(x) = \sum_{j=1}^{n} x^{a_j}$ of degree $\le kn$, and compute its square using the Fourier transform method and read off the powers with their coefficients in the resulting polynomial. This is an $O(n \log n)$ time algorithm.

I have two questions:

Is there an $O(n \log n)$ algorithm which does not use FFT?
Are better algorithms known (i.e $o(n \log n)$)? (FFT allowed).

It would seem that this problem is equivalent to integer/polynomial squaring:

1. It is known that polynomial multiplication is equivalent to integer multiplication.

2. Obviously, you already reduced the problem to polynomial/integer squaring; therefore this problem is at most as hard as squaring.

Now I will reduce integer squaring to this problem:

Suppose you had an algorithm:

$$
F(\mathbf{\vec a})\rightarrow P^2(x),\\
\text{where } P(x)=\sum_{a_i \in \mathbf{\vec a}} x^{a_i}
$$

This algorithm is essentially the algorithm you request in your question. Thus, if I had a magic algorithm that can do this, I can make a function, ${\rm S{\small QUARE}}\left(y\right)$ that will square the integer $y$ (oh yes, I do love mathjax :P):

$$
\begin{array}{rlr}\hline
&\mathbf{\text{Algorithm 1}} \text{ Squaring}&\hspace{2em}&\\
\hline
{\tiny 1.:}&\mathbf {\text{procedure }} {\rm S{\small QUARE}}\left(y\right):\\
{\tiny 2.:}&\hspace{2em}\mathbf {\vec a} \leftarrow ()
  &&\triangleright~\mathbf {\vec a}\text{ starts as empty polynomial sequence}\\
{\tiny 3.:}&\hspace{2em}i \leftarrow 0\\
{\tiny 4.:}&\hspace{2em}\mathbf{while}~y\ne0~\mathbf{do}
  &&\triangleright~\text{break }y\text{ down into a polynomial of base }2\\
{\tiny 5.:}&\hspace{4em}\mathbf{if}~y~\&~1~\mathbf{then}
  &&\triangleright~\text{if lsb of }y\text{ is set}\\
{\tiny 6.:}&\hspace{6em}\mathbf{\vec a} \leftarrow \mathbf{\vec a}i
  &&\triangleright~\text{append }i\text{ to }\mathbf{\vec a}~\text{(appending }x^i\text{)}\\
{\tiny 7.:}&\hspace{4em}\mathbf{end~if}\\
{\tiny 8.:}&\hspace{4em}i \leftarrow i + 1\\
{\tiny 9.:}&\hspace{4em}y \leftarrow y \gg 1
  &&\triangleright~\text{shift }y\text{ right by one}\\
{\tiny 10.:}&\hspace{2em}\mathbf{end~while}\\
{\tiny 11.:}&\hspace{2em}P^2(x) \leftarrow F\left(\mathbf{\vec a}\right)
  &&\triangleright~\text{obtain the squared polynomial via } F\left(\mathbf{\vec a}\right)\\
{\tiny 12.:}&\hspace{2em}\mathbf{return}~P^2(2)
  &&\triangleright~\text{simply sum up the polynomial}\\
{\tiny 13.:}&\mathbf {\text{end procedure}}\\
\hline
&\end{array}
$$

Python (test with codepad):

#https://cs.stackexchange.com/q/11418/2755

def F(a):
    n = len(a)
    for i in range(n):
        assert a[i] >= 0

    # (r) => coefficient
    # coefficient \cdot x^{r}
    S = {}
    for ai in a:
        for aj in a:
            r = ai + aj

            if r not in S:
                S[r] = 0

            S[r] += 1

    return list(S.items())

def SQUARE(x):
    x = int(x)

    a = []
    i = 0
    while x != 0:
        if x & 1 == 1:
            a += [i]
        x >>= 1
        i += 1

    print 'a:',a
    P2 = F(a)

    print 'P^2:',P2

    s = 0
    for e,c in P2:
        s += (1 << e)*c
    return s

3. Thus, squaring is at most as hard as this problem.

4. Therefore, integer squaring is equivalent to this problem. (they are each at most as hard as each-other, due to (2,3,1))

Now it is unknown if integer/polynomial multiplication admits bounds better than $\mathcal O(n\log n)$; in fact the best multiplication algorithms currently all use FFT and have run-times like $\mathcal O(n \log n \log \log n)$ (Schönhage-Strassen algorithm) and $\mathcal O\left(n \log n\,2^{\mathcal O(\log^* n)}\right)$ (Fürer's algorithm). Arnold Schönhage and Volker Strassen conjectured a lower bound of $\Omega\left(n \log n\right)$, and so far this seems to be holding.

This doesn't mean your use of FFT is quicker; $\mathcal O\left(n\log n\right)$ for FFT is the number of operations (I think), not the bit complexity; hence it ignores some factors of smaller multiplications; when used recursively, it would become closer to the FFT multiplication algorithms listed above (see Where is the mistake in this apparently-O(n lg n) multiplication algorithm?).

5. Now, your problem is not exactly multiplication, it is squaring. So is squaring easier? Well, it is an open problem (no for now): squaring is not known to have a faster algorithm than multiplication. If you could find a better algorithm for your problem than using multiplication; then this would likely be a breakthrough.

So as of now, the answer to both your questions is: no, as of now, all the ~$\mathcal O(n\log n)$ multiplication algorithms use FFT; and as of now squaring is as hard as multiplication. And no, unless a faster algorithm for squaring is found, or multiplication breaks the $\mathcal O(n\log n)$ barrier, your problem cannot be solved faster than $\mathcal O(n \log n)$; in fact, it cannot currently be solved in $\mathcal O(n\log n)$ either, as the best multiplication algorithm only approaches that complexity.


Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack? I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with two stacks. I also know that you can’t simulate a Turing machine with a PDA, because a professor challenged a student when he suggested the treating a stack as a matrix, that is, as if it were two arrays. What’s the roadblock?

The comment of @Yuval tells the intuition behind the answer (the shortcoming of a PDA is that you can iterate only once over the word and you cannot read the second letter in the stack before popping the first one, note that you can keep only constant amount of data in the state).

However, a very concise formal proof why we can not simulate all Turing machines with PDAs is that you can build to each PDA a corresponding context free grammar such that a given word  is accepted by a given PDA if and only if it can be constructed with the corresponding grammar source.

Now since CFL is a proper subset of CSL which is again a proper subset of recursive languages which all can be decided by Turing machines, Turing machines can simulate all PDAs but not vise versa. To see why, for a given recursive but not context-free language, say the standard example $a^nb^nc^n$, there is no PDA to compute this language since else there would be a context free grammar to compute it which would make it CFL. On the other hand it is not hard to build a Turing machine that decides this language.


Increasing Cache Line and Programs with bad Spatial Locality I'm reading on caches and I'm feeling a bit lost with spatial locality.

From my understanding, increasing the cache line with a program that has high spatial locality reduces the miss rate.

But for a program that has low spatial locality, does an increase in cache line have any effect on the miss rate?

There will be minimal, to no effect on the miss rate of a program with low spatial locality.


Direct Cache Mapping - Addressing I've looked through all the other similar questions, but I don't feel like I understood exactly what I'm supposed to do with my case, so I'm hoping I'm not the only one.

In an exercise I'm doing, I'm told to consider a computational system with a direct mapping cache, that can store 16 blocks of 4 bytes, and 32-bit addresses.

I'm then given 8 addresses in hexadecimal, and I'm supposed to say what will be the content of the 16 blocks.

One of the adresses in question is: 0xC4001234
I've calculated the tag as 21 bits, set being 4 bits, and offset being 5 bits.
Yet, I'm not sure how I'm supposed to know in which block it will be.
My teacher's Powerpoint said that the "set" is used to locate the block in the memory, but I'm not sure how. I thought I'd convert the address into binary and use the 4 bits to calculate where the block will be, but then I have some adresses that match in the same block.

I was wondering if anyone could show me how to do this one address, so I can do this exercise and hopefully pass my exam. Thanks.

Your cache is direct mapped so there are no sets. Those are set associative caches.

In your example the tag is 26 bit, block 4 bit and byte offset is 2 bit.

To get that just break your 32 bits into tag, block and byte fields.
16 blocks means 4 bits to address a block.
4 byte blocks means 2 bits to address bytes within blocks.
Rest of the bits are 26, which is the tag.
When you convert 0xC4001234 to binary and remove first 26 bits and the last 2 bits that gives you the 4 block bits.

In your case it is 1101 or block 13 of 0-15.


Programs for artificial system design? Are there program systems that can discover the need of routines - and then design them, code them and use them as parts of the system?

Any group of humans trying to pursue an activity has to develop in a developed system, to solve their problems by formulating the issues, search for knowledge and methods, to be tested and evaluated - and to be incorporated into the common experience for the activity to be pursued. Are there some software that could be compared with a human process like that?

There has been a lot of work in genetic programing (GP) in this vein. Automatically defined functions are a big deal in GP and figuring out how many and what kinds of ADF's you should have (the "Architecture") has been the subject of a lot of research as well. More generally some people have looked at how to use GP to create libraries that it can then work with to make new more complex functions.

GP can often create perfect solutions like reversing a list or sorting lists. More often how ever it generates approximate solutions. It is really clever what all it can do however. John Koza (a really big name in GP) used genetic programing to find entirely new circuits that had never been created before and were effectively open problems in electrical engineering. To do this he had it design everything from the ground up but it had many recognizable circuits as sub parts. One could imagine that it might have made these things faster if it had already had those designed parts in its library.


How does computer store non-repeating decimal very accurately? Maybe it is not accurate at all, but it looks very accurate for me.
I'm making a scientific calculator for my portfolio, and I found an interesting phenomenon.

Because computers store decimals not accurately but approximately, I thought that asin(sin(30rad)) wouldn't give 30rad, and sqr(sqrt(7)) wouldn't give 7, etc..

However, it seems that every kind of calculations like above gives an accurate result. (I used cmath header of c++, and I checked that python math modules also gives the same)

This consequence seems even arcane to me. Does the computer really store those non-repeating deicmals? or is it just a matter of implementation of math libraries, like substituting a special symbol for them?

It may be that sqr (sqrt (7)) is displayed as 7, but it isn't actually exactly equal to 7. That's something you need to check. What you see is not always what you get. It may be that sqr (sqrt (7)) is exactly 7, by "coincidence" (not really coincidence, more like "unpredictable with my limited knowledge").

Take any floating point number x, 1 ≤ x < 4. When the square root is calculated, you get another floating point number y, 1 ≤ y ≤ 2. There are fewer floating point numbers (about half as many) 1 ≤ y ≤ 2 as floating point numbers 1 ≤ x < 4. If you square two numbers y and y', that calculation doesn't know how y and y' were created. So there are about half as many floating point numbers sqr (sqrt (x)), 1 ≤ x ≤ 4, as original numbers in that interval. So for about half the numbers, sqr (sqrt (x)) ≠ x.

The other way round, calculating sqrt (sqr (x)), you can probably prove that the result must be equal to x if both operations are calculated with high quality. If the squaring operation produces a relative error epsilon, then the square root operation divides that relative error by two.

PS. Yuval checked that for x = 7, sqr (sqrt (x)) is not equal to x. If you checked all integers from 1 to 10,000 except those that are squares, I'd expect that sqr (sqrt (x)) equals x in about half the cases that you check.


Why is $3^{\log_2 n}$ the same as $n^{\log_2 3}$? I am reading about divide and conquer algorithm at following link on page on 57 in this link. The document analyzes the running time of the algorithm. At the very top level, when $k = 0$, this works out to $O(n)$. At the bottom, when $k = \log_2 n$, it is $O(3^{\log_2 n})$, which, the author claims, can be rewritten as $O(n^{\log_2 3})$.

My question is:

  Why can $O(3^{\log_2 n})$ be rewritten as $O(n^{\log_2 3})$?

The two expressions are equal: $3^{\log_2 n} = n^{\log_2 3}$. To see this, you can use the following identities: $\log_a b = \log_c b/\log_c a$, $\log_a b = 1/\log_b a$, and $a^{\log_a b} = b$. Using these identities, we get
$$
3^{\log_2 n} = 3^{\log_3 n / \log_3 2} = 3^{\log_3 n \cdot \log_2 3} = (3^{\log_3 n})^{\log_2 3} = n^{\log_2 3}.
$$


Vertex Cover of size at most $\log n$ Consider the following language:
$$
L = \{ G | G \text{ has a VC of size at most } \log n \}
$$

Does $L\in P$ or $L\in NPC$?

If you solve Vertex Cover with the simple branching algorithm, you achieve an FPT running time of $2^k \text{poly}(n)$, where $k$ is an upper bound for the solution you are looking for.

Substituting $k$ for $\log n$ gives you the answer you are looking for.


Number of ways of making change in Big O notation I have the following algorithm in ML:

fun change(till,0,chg,chgs) = chg::chgs
|   change([],amt,chg,chgs) = chgs
|   change(c::till,amt,chg,chgs) = if amt<0 then chgs else change(c::till, amt-c,c::chg, change(till,amt,chg,chgs));

The algorithm takes a list of currency denominations as till and returns all the combinations of denominations which produce the amount amt specified.

And I am trying to show that the number of ways for making change for some value n regardless of order with two change values is O(n). And then trying to figure out what it is for more change values.

It's clear that for one change value it is O(1) as there is only one possible way to make change but I'm not sure how to progress from there.

Any help would be much appreciated.

Suppose that the two denominations are $a$ and $b$. Every solution to the coin-changing problem is a solution to the equation $\alpha a + \beta b = n$ in non-negative integers $\alpha,\beta$. For every possible value of $\alpha$ there is at most one solution. Since $0 \leq \alpha \leq n/a$, we conclude that there are at most $n/a + 1 = O(n)$ solutions.


Finding pairs $a \in A$, $b \in B$ where $a \ge 3b$ in linear time There are two sorted arrays A and B containing distinct values. How to find all the pairs $(a,b)$ such that $a \ge 3b$ and a is in A and b is in B. This needs to be done in linear time.

I have tried solving it but it is taking me $n \log n$ time, not $n$. I simply use binary search to look for the value of $b$ corresponding to $a$. But in worst case it will come up as $n \log n$ only.

I have tried to read about it online but found nothing and kind of stuck for the past 2 days. I just want some hints to move in the right direction because I feel that maybe I am missing something very fundamental.

If you need to list all output pairs, as you say, then the problem can't be solved in any less than quadratic time, for the reason that the output may be of quadratic size. Imagine that $A$ and $B$ are both half the input (say, both length $n$), and
\begin{align*}
A &= [3n + 1, 3n+2, 3n+3, \ldots, 4n-1, 4n] \\
B &= [1, 2, 3, \ldots, n]
\end{align*}

Then the output to your problem is all pairs of an element in $A$ and an element in $B$, and there are $n^2$ such pairs.

Probably there is an additional fact you haven't mentioned, that you don't have to produce all pairs, but you just have to produce a more compact representation of the output (e.g. for each $a \in A$, you only need to produce the maximal $b \in B$ such that $a \ge 3b$).

A hint for this altered version, where you only need the maximal $(a,b)$ pairs:

Imagine you are iterating through both $A$ and $B$ at once, instead of just iterating through $A$ or $B$ separately. So, you are keeping two pointers, one into $A$ and one into $B$. Suppose you have found the maximal pair for $a$, so you know $(a, b)$, and the next element in $A$ after $a$ is $a'$. What should you do?


Blum's speedup theorem showing unclassifiable complexity languages? Do any of Blum's theorems prove that there exist decidable languages that are unclassifiable anywhere in the time hierarchy? In other words, asserting they (mentioned in the proofs) are computable within any time $O(f(n))$ for some time-constructable function $f(n)$ leads to a contradiction?

If a language is decidable then it is accepted by some Turing machine. The running time of that Turing machine is by definition time-constructible. So any computable function has a time-constructible upper bound by definition.


What's the name of this packing problem? I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping.
For example if I have these intervals:
A: [ [0, 10] ]
B: [ [1, 3], [5, 7] ]
C: [ [8, 10] ]

I want to get the following result:
[0, 1]: [A]
[1, 3]: [A, B]
[3, 5]: [A]
[5, 7]: [A, B]
[7, 8]: [A]
[8, 10]: [A, C]

What's the name of this problem?

The problem can be stated as finding the elementary intervals for a given set of intervals. It is a technique frequently used for problems in computational geometry (as suggested by nir shahar also).


Probabilisitc timed automaton I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP. However, is there anything else? Are they still memoryless? I am not able to find any information about this topic.

The reason that you do not find any results is thta from a scientific point of view, the well-posed questions for PTAs and MDPs are quite different:

MDPs typically have a reward function assigned, while PTAs do not necessarily have to have them.
It is a bit imprecise to state that the "objectives is to solve the non-determinism of a MDP" -- it depends on what you want to do. PTAs are foremost models that you can analyse. Resolving the non-determinism means computing a policy, which makes sense if you have some kind of optimization criterion that you want to follow. This could be a temporal logic formula.
In MDPs, the classical question is to find a policy that maximizes the limsup average payoff or the discounted payoff. In the latter case, there exist optimal memoryless policies (which is the result that you refer to). In PTAs, asking the same question is kind-of odd as the number of states in PTAs is infinite and there is (by default) nothing to optimize. A state consists of a location and a valuation to the clocks. This is already the case for timed automata, from which PTAs inherit many of their properties (and hardness results).
The questions typically asked for PTAs are whether there exist policies that raise the probability of some temporal property holding along a trace over some given limit. A paper my Norman et al. (http://www.prismmodelchecker.org/papers/fmsd-ptas.pdf) contains details. They also define reward structures for PTAs, but the do not need to be concerned with discounted payoff optimization, like it is common in the MDP research case.


Which problems are hard for P^NP? Quantified Boolean formulae are the prime examples of problems that are hard for the polynomial hierarchy, i.e., for the $\Pi$ and $\Sigma$ versions of it. However, there is also the $\Delta$ version, defined as $\Delta_{i+1}^{\rm P} := {\rm P}^{\Sigma_i^{\rm P}}$. In particular, $\Delta_2^{\rm P} = {\rm P}^{\rm NP}$.

What are typical hard problems for this part of the hierarchy?

I failed to search the Web for this; especially, you cannot use Google to find much about "P^NP".

Krentel gave two problems complete for $\Delta_2^P$ (see Theorem 3.4):

Input: Boolean formula $\phi(x_1,\dots,x_n)$.
Question: Is $x_n = 1$ in the lexicographically largest satisfying assignment of $\phi$?
Input: Weighted graph $G$, integer $k$.
Question: Is the length of the shortest TSP tour in $G$ divisible by $k$?

Krentel also states that the only previous example of a $\Delta_2^P$-complete problem up to 1988 was Uniquely Optimal TSP, given by Papadimitriou in 1984.
As sdcvvc pointed out, see also the MO discussion at https://mathoverflow.net/questions/2218/characterize-pnp for a nice discussion by Ryan Williams of a machine model that captures $\Delta_2^P$.

Mark W. Krentel, The Complexity of Optimization Problems, JCSS 36 490–509, 1988. doi:10.1016/0022-0000(88)90039-6


What is the trick of "adding a huge number" for in the reduction from 3-Partition? Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following figure.

In the $\textsf{3-Partition}$ instance, there are $n$ elements $(a_1, \cdots, a_i, \cdots, a_n)$. The target sum $t$ is $t = \frac{\sum a_i}{n/3}$.

In the reduction, $B$ is a huge (constant) number and each $a_i$ is represented by a $(B + a_i) \times (B + a_i)$ square. The blank in the rectangle will be filled by unit ($1 \times 1$) squares.

Questions:
I don't quite understand the trick of "adding a huge number $B$" in the reduction. I guess it is used to force that any packing scheme will give a solution to $\textsf{3-Partition}$. But how?

  Question 1: What is the trick of "adding a huge number" for in the reduction from $\textsf{3-Partition}$? Specifically, why does this reduction work? Why is this trick necessary, i.e., why wouldn't the reduction work if we left out $B$ (set $B=0$)?

I tried to identify the flaw of the proof of "any packing gives a 3-partition" but could not get the key point.

Actually I have also seen other reductions from $\textsf{3-Partition}$ that also use this trick. So,

  Question 2: What is the general purpose of this trick of "adding a huge number" in the reductions from $\textsf{3-Partition}$ (if there is)?

Note: This problem is from the video lecture (from 01:15:15) by Prof. Erik Demaine. I should have first checked the original paper "Packing squares into a square". However, it is not accessible to me on the Internet. If you have a copy and would like to share, you can find my mailbox in my profile. Thanks in advance.

The large $B$ is here to ensure that the squares follow the pattern shown in the figure.

In the part "there exists a packing $\Rightarrow$ there exists a 3-partition". You need to exhibit tripples of integers with sum $=t$. This is easy if the coding squares in the packing are arranged 3-by-3 as in the picture, but how do you know this is the case? For instance, with very slightly smaller blue squares, you could have two small squares side by side in the same column, and then you'd be in trouble.

One way to use the trick of the $B$ constant is to say that it is not possible to have any horizontal line crossing strictly more than $n/3$ squares (such a line has length $(B+t)\frac n3$, a square has size at least $B$, and $B > t\frac n3$). So each horizontal line meets a 1st square, a 2nd square, etc., and then you can show (again using the large $B$), that the $i$th squares of each lines must all meet in the same column. Once you've got this, then you  get a 3-partition.

About Question 2, it is obviously hard to give a formal answer, but the general pattern is the following:with 3-partition, you need to introduce some kind of slackness to allow that any integer in an interval $[min,max]$ can be somehow encoded and embeded in a slot (which must then correspond to the maximum possible size). But then a common issue is having two integers fitting in the same slot, or more generally other overlapping issues (as with the squares here). This is solved by making sure that the $min$ is large enough compared to the slot size (we often need $min > max/2$, or $min > max*(n-1)/(n)$ here): this is easily achieved with an additive constant $B$.

Edit Sample instance where $B$ is necessary:
Let the instance of 3-partition be $(10,7,2,10,9,2)$ with $t=20$. This is a no-instance. However, with $B=0$, you have a valid packing of the $40\times 20$ rectangle: use a first column with four squares $(10,7,2,2)$, the last two being side-by-side, and a second column with only $(10,9)$. This is not possible with, say, $B=100$, and a $240 \times 320$ rectangle.


If $F$ is valid then $F \cup \{res(C_1,C_2,A_i)\}$ is valid I have to prove the following problem in propositional logic:

Let $F$ be a set of clauses and let $F' = F \cup \{res(C_1,C_2,A_i)\}$ be the extension of $F$ by a resolvent of some clauses $C_1,C_2 \in F$ where $A_i$ is a literal occuring positively in $C_1$ and negatively in $C_2$.

Prove that: If $F$ is valid, then $F'$ is valid.

So in other words I have to prove that when I construct the union of the original formula $F$ and the formula resulting by applying resolution on $F$ over a literal $A_i$ in $F$, validity is still preserved.

I think that this should be provable by applying a direct proof.

Recall: Note that resolution is defined as follows: given two clauses:
$C_1 = (A_1 \lor \dots \lor A_i \lor \dots \lor A_n)$ and $C_2 = (B_1 \lor \dots \lor B_j \lor \dots \lor B_m)$ such that for some $i, j$ with $1 \leq i \leq n$, and $1 \leq j \leq m,\; A_i = \neg B_j$,
the resolvent of $C_1$ and $C_2$ on $A_i$ is the clause

$res(C_1,C_2,A_i) = (A_1 \lor \dots \lor A_{i-1} \lor A_{i+1} \lor \dots \lor A_n \lor B_1 \lor \dots B_{j-1} \lor B_{j+1} \lor \dots \lor B_m)$

EDIT: Here is my try:

Let $I$ be an interpratation taken from the set of models $Mod(F)$. Hence, $I(F) = 1$. Because this interpretation satisfies $F$ it must also be the case that it satisfies $C_1$ and $C_2$. If we take a look at the structure of $C_1$ and $C_2$ we have to distinguish between $2$ different cases:

(1) $A_i$ is positive in $C_1$ but negative in $C_2$ and

(2) $A_i$ is negative in $C_1$ but positive in $C_2$.

In case (1) if $A_i$ is set to true in $C_1$ it would be false in $C_2$.
In case (2) if $A_i$ is set to true in $C_2$ it would be false in $C_1$.

$A_i$ cannot be the literal which preserves satisfiability of $F$. Hence $I$ must include some assignment of other literals in $F$ such that $F$ is satisfied. Thus, the resolvant $res(C_1,C_2,A_i)$ is also satisfied.

Since you are only asking for a hint:

You have to prove that, for any interpretation I, if it satisfies all
the clauses in $F$, then it also satisfies the resolvant
$res(C_1,C_2,A_i)$, and hence it satisfies all the clauses in $F'$.

From that you can infer the result to be proved, with some universal quantification.

Note on terminology and notations:

I would rather say that, when $F$ is valid, every interpretation
satisfies it. It is $F$ that is to be satisfied, not the interpretation. Or more generally, it may also be a clause $C$, a literal $A_i$, or a set of clauses $F$ that may (have to) be satisfied.
$F$ is valid iff for any interpretation $I$, $I(F)=1$.
You should not say "for any interpretation $I(F)$", since as you noted yourself, $I(F)$ is a truth value. An interpretation in propositional logic is (usually) an assignment of truth values to the symbols used in the clauses, i.e. a mapping of the set of symbols to the set of truth values. It also implies interpreting logical connectives in the usual way, and sets of clauses as a conjunction of the clauses. Then, truth tables allow you to associate truth values to each construct, up to the whole set of clauses, which is what is meant by $I(F)$. The interpretation is $I$. while $I(F)$ is the truth value it gives to the set $F$ of clauses.

Interpretation may be defined in a more general way, but the above should be enough here.


How can a operating system run on more than one CPU architecture? How can a operating system run on more than one CPU architecture?

Does the OS detect what type of architecture it is currently running on?
If so, does it simply use a different set of code for that architecture?

How does the CPU detect the type of architecture?

Operating systems don't detect the CPU architecture.  Instead, you have to ensure that you install the correct version of the operating system given its CPU architecture.  If you make the wrong decision, then the OS won't boot, as the CPU won't understand (either reject or misinterpret) the machine code that you've provided.

The reason's that an operating system is just a program written as a series of instructions for the CPU to execute.  Since different types of CPU's have different instructions, a procedure (program) written (compiled) for one CPU could be gibberish for another.


How to show that FPATH is in NL? Consider this problem:

$\qquad\displaystyle \mathsf{FPATH} = \{\langle G, a_1,\dots,a_n\rangle \mid G \text{ is a digraph with directed path } (a_1,\dots,a_n)\}$

It's allowed to visit nodes outside the sequence, but a1 must be visited before a2 and so on.

I am having big trouble trying to show that this language is NL-complete. I have tried finding an algorithm for a TM that decides this problem in NSPACE(log n), but I can't seem to find a good solution. I know that PATH is NL-complete, so I guess I can use that fact. My problem is finding an algorithm that somehow has to know that is has been through the sequence $a_1$ to $a_n$, but how can I do this when the worktape only can use $\log n$ space?

Turning my comment into an answer for the question in the title, the Immerman-Szelepcsényi Theorem says that NL = coNL.  This means it's enough to show that FPATH is in coNL.  For that, observe that the path $a_1,a_2,\ldots, a_n$ is not in $G$ if and only if some edge $a_ia_{i+1}$ is not present.  Since you just need to guess $i$, that's all you need to write down.


find number in array divided into k parts I was wondering what is the most efficient way to find the a number in an array with the following conditions:

  Array $A$ of size $n$ divided into even parts in the size of $k$

  every element in each part is bigger than all the elements in the part
  before (Lets say in the left)
  every element in each part is smaller then then every elements in the part after it (lets say on the right)

At this moment after trying couple of ways I am under the impression that the only way is $O(n)$

Is it correct?

Choose an arbitrary representative from each part. Using binary search, you can find the two representatives which bracket the given element. You can then look for your given element in the $2k$ elements comprising the two parts that the representatives belong to. This algorithm takes time $O(\log(n/k) + k) = O(\log n + k)$, interpolating between the cases $k=1$ (sorted array, $O(\log n)$) and $k = n$ (unsorted array, $O(n)$).


Algorithm to find the intersection of non-convex polyhedra Context:

I have two polyhedra, $A = V_1\times F_1$ and $B=V_2\times F_2$ where $V_i$ is set of vertices (which are just coordonate in $\mathbb R^3$) and $F_i$ is a set of faces (tuples of length $\geq 3$ such as $(i_1,...,i_k) \in F_i$ iff there is a face formed by the $i_1$-th,...,$t_k$-th vertices of $A_i$).
Then, if I want to draw a cube, I will have 8 vertices in $V$ and 6 tuples of length $4$ that define the vertices of each square that makes the 6 faces of my cube.

These are not necessarily convex (but at least they are connected).

The problem:

Find an algorithm that takes $A,B$ and return $C$ the intersection of the two polyhedra.

My research:

I found this on the stack network:
https://mathoverflow.net/questions/141703/intersection-of-polyhedra

But the answers focuses on collision detection rather than returning the intersection of the two bodies.

The other articles I found online seem also to be all about collision detection rather than intersection.

My attempts:

I first imagine to approximate polyhedra with voxels, since it is pretty easy to find intersections of 0-1 arrays. But In my case, I would need too many voxels, then it would lead to too much memory use.

I do not have any other idea to solve efficiently my problem.

I propose the following approach.

Decompose each polyhedron into a union of convex polyhedra, say $A = A_1 \cup \cdots \cup A_m$ and $B = B_1 \cup \cdots \cup B_n$.
Convert each convex polyhedron from V-representation (its list of vertices) to H-representation (intersection of half-spaces, given by linear inequalities).
Compute the intersection as $A \cap B = \bigcup_{i,j} A_i \cap B_j$, where you can compute $A_i \cap B_j$ trivially once they are in H-representation: you just concatenate the list of linear inequalities.  (If you want, you can convert $A_i \cap B_j$ back to V-representation.)

There are standard algorithms for doing step 2.  In fact, given a face, it is easy to construct the corresponding linear inequality (form the plane that goes through all of the vertices on the face, then create the corresponding linear equality, then change the equality to an inequality).

I'm not sure how to do step 1; perhaps that is worth asking as a separate question, if you can't figure it out after some research.


Undecidable language and Turing Machines I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about.

  If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine that recognizes the complement of A?

To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine. Also seeing as the Language is undecidable, this Turing Machine will not halt for strings that are not in the language.

Can someone please tell me if my understanding is correct or not, and if not give me some clarification?

To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine.

You presume to know something about how the machine for $\overline{A}$ was built; don't, because you can't.

What's more, this construction (flipping accepting states) does not work for TMs that do not always halt, as any one for $A$ has to be.

Thus, a semi-decider for $\overline{A}$ has to look differently from what you describe.

Regarding the original problem you were given, it is a weird formulation to test your understanding of basic closure properties.

Hint: Assume there was a semi-decider for $\overline{A}$. What follows about $A$?


Human ranked/sorted items I'm trying to derive an algorithm or procedure I would use to have a human interactively rank a series of items based on importance by comparing a random-pairing of items at a time.

So, given an array of let's say 10 "things", I want to present two of the things, and have the user specify which is the more important of the two.  What I don't know is:

What is the proper name for this procedure/concept?
Would I use some form of sorting algorithm?
How could I determine when to stop?  When is the ranking "done"?
And, importantly, I would prefer not to present the same "thing" to the user in a row.  That is, if comparing Item B and Item K, user selects Item K as more important, the next iteration should not present either Item B or Item K.

What I'm after seems similar to this question: Nearest neighbour based on subjective human comparison - is this a thing?

... but I'm not interested in similarity, just relative importance.  Think prioritizing a to-do list or subjectively ranking vacation destinations, etc.

The Elo Rating System may be similar to what I'm after, as well.

There are statistical models for relative ranking.  I'd suggest taking a look at the Bradley–Terry model.  The data is sometimes known as paired comparison data.

See also Analysis and classification based on data points,  Peer grading design - choosing a graph, to get accurate rankings/ratings, https://stats.stackexchange.com/q/83005/2921.


Proof that a relation is in FP How we can prove that the relation: $R= \left\{0,1\right\}^*\times \left\{0,1\right\}^* \in FP$
I understand that we need to find a polytime algorithm to decide whether $(x,y) \in R$ since $(x,y)\in R= \left\{0,1\right\}^*\times \left\{0,1\right\}^*$
How can we find this? And this is enough to prove that $R \in FP$?

To show that $R \in \mathsf{FP}$ you need to show that there is a deterministic poly-time algorithm $A$ that takes $x$ as input and outputs a $y$ such that $(x,y) \in R$.
A possible choice of $A$ is the algorithm that outputs $\varepsilon$ (the empty word) regardless of $x$. Indeed, $(x, \varepsilon) \in R$.


Is this concatenation ({a} · {b})^2 ≠ a^2 · b^2? I presumed they were equal, such that both resulted in aabb. However, I'm told they are false and I don't know why.
Is it because in the second one, we would concatenate a · b before raising to the power of 2, thus resulting in abababab? Or because in the first one you concatenate first, thus resulting in abab?
Thanks in advance.

They are different, because:
$(a \cdot b)^2 = abab$, since you need to concatenate $a$ and $b$ first, them reapeat the concatenation two times.
$a^2 \cdot b^2 = aabb$, since you need to concatenate the repetition of two $a$ with the repetition of two $b$.


Counting the number of minimal covers of a binary matrix Given a binary $n$-times-$n$ matrix $A$, we'd like to cover the regions comprised of $1$'s with non-intersecting rectangles. A collection of disjoint rectangles that covers all $1$'s (and only $1$'s, i.e., it mustn't cover any $0$'s) is called a cover. (Notice that a problem instance may have many different covers.)

A cover is called a minimum cover if it uses the smallest number of rectnagles possible.

The counting problem I'm interested in is: given an $n$-times-$n$ binary matrix $A$, count the number of minimum covers of $A$.

What can you say about this problem? (This post was inspired by this SO question.)

It's easy to show that some inputs can produce an exponential number of minimum covers.  Consider the following 3x3 matrix:

110
100
000

This can be minimally covered in exactly 2 ways: either using a single vertical 2x1 rectangle and a single 1x1 rectangle, or a single horizontal 1x2 rectangle and a single 1x1 rectangle.

Thus placing $k$ non-overlapping copies of this gadget in a grid will produce an instance with $2^k$ distinct minimal covers.  You could, for example, tile an $n$ by $n$ grid with $n^2/9$ of them to produce an instance with $2^{n^2/9}$ minimal covers.

(It's possible that a better gadget exists -- that is, smaller gadgets that would increase the coefficient in the exponent.  More interestingly it's possible that instances with asymptotically more minimal covers exist.)


Can max-flow with mutually exclusive edges be reduced to standard max-flow problem? I'm working with a flow network like the following:

The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, also with capacity 1. X and Y both have edges with capacity 4 to the sink t.

Typically this would have many solutions: all of the ways you could split up A, B, C, and D between X and Y. In the modified version, I have to pick either X or Y. If the flow on (X, t) > 0, the flow on (Y, t) must be 0, and vice versa. So there are only two solutions, sending all 4 units of flow through X or through Y.

I'm wondering if there is a way to reduce this constraint to the standard max-flow so I can just run Ford-Fulkerson on a modified graph. That, or whether this is fundamentally harder and is an isomorphism of a different problem.

In simpler versions like the one I've laid out above you could just reduce the decision to a problem where you have only s, t, and the nodes X and Y and must send 1 unit of flow through the network, but I'm struggling with the general case where we have two edges X and Y, only one of which is allowed to have nonzero flow through it in the solution.

You can reduce SAT to this version. Connect the source to nodes $x_1,\ldots,x_n$, one per variable, with infinite capacity. Connect each $x_i$ to two exclusive nodes $x_i^T,x_i^F$, with infinite capacity. Create one node per clause, and connect a literal to a clause (with infinite capacity) if the clause contains the literal. Finally, connect each clause to the sink with unit capacity. The maximum flow is the number of clauses iff the formula is satisfiable.


How to simulate a die given a fair coin Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate integers $k,m$, such that $2^k = 6m$. So after flipping the coin $k$ times, we map the number encoded by the k-length bitstring to outputs of the die by dividing the range $[0,2^k-1]$ into 6 intervals each of length $m$. However, this is not possible, since $2^k$ has two as its only prime factor but the prime factors of $6m$ include three. There should be some other simple way of doing this, right?

What you can do, is to employ a method called rejection sampling:

Flip the coin 3 times and interpret each flip as a bit (0 or 1).
Concatenate the 3 bits, giving a binary number in $[0,7]$.
If the number is in $[1,6]$, take it as a die roll.
Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.

Since $\frac 68$ of the possible outcomes lead to termination in each set, the probability of needing more than $l$ sets of flips to get a die roll is $(1-\frac 68)^l = \dfrac 1{4^l}$. Hence, this method is efficient in practice.

Improvements:

@Angel's answer points out, that the number of coin flips in each set but the first can be reduced from 3 to 2, by using the distinction between a $0$ and a $7$ as the first bit for the next set.

@Emanuele Paolini explains, how you can reduce the number of rerolls, if you need multiple die rolls.


Prove that $P/poly$ is closed on $^*$. Prove that $P/poly$ is closed on $^*$. Please help me with that because I cannot deal with that.

Note that for $w\in\{0,1\}^n$ it holds that:

$w\in L^*\iff w\in L \lor \left(\exists i\in \{1,...,n-1\} : w_1...w_i\in L^* \land w_{i+1}...w_n\in L\right)$.

You can translate the above into a dynamic programming algorithm for deciding $L^*$. One way to do that is keeping an array $A[i]$, where $A[i]=1\iff w_1,...,w_i\in L^*$, and filling it from $i=0$ upwards. The running time $T(n)$ is bounded by $T(n)\le T(n-1)+T_L(n)$, where $T_L(n)$ is the time required for deciding membership to $L$ on inputs of length $n$. Hence, $T(n)\le nT_L(n)$, which is polynomial if $L\in P$.

This works fine if $L\in P$, however when $L\in P/Poly$, you have a polynomial time machine $M(x,y)$ and a sequence of advice $\{\alpha_n\}_{n\in\mathbb{N}}$, where $\alpha_n\in\{0,1\}^{p(n)}$ for some polynomial $p$, such that $x\in L \iff M\left(x,\alpha_{|x|}\right)=1$. The above procedure requires deciding membership to $L$ on inputs of length at most $n$. Thus, your advice for deciding $L^*$ on length $n$ inputs will be $\beta_n=\alpha_0,\alpha_1...,\alpha_n$ (which is still polynomial), and whenever you need to check membership to $L$ on a word $w$ of length $0\le i\le n$, execute $M(w,\alpha_i)$.


What are the differences between the set of Real Numbers and the Java datatype float? Besides the fact that the real numbers ℝ go on forever whereas the floats only go up to a certain point (Float.MAX_VALUE) in Java, what else could I compare between these two sets of numbers?

The set of double precision floating point numbers in Java has the following elements:
Integers from 1 to $2^{53}-1$, multiplied by $2^e$ for integers e in some fixed range (which I am too lazy to look up right now).
+Infinity and -Infinity
+NaN and -NaN
+0 and -0.
The last six are not real numbers (+0 and -0 are both similar, but not quite the same as the real number 0).
Real numbers which are not Java floating-point numbers are 0, those numbers that are either too large or too small, requiring an integer e outside the allowable range, those that are not integer multiples of a power of two, and those that are integer multiples of a power of two with an integer > $2^{53}$.


How does the memory of a 64bit and 32bit processor work In this article, the author states that a 64bit processor can theoretically reference 2^64 bytes of memory. What does he mean by this statement, or rather the word, reference?

Also, I visualize the entire RAM to be divided into little memory cells, each having an n-bit binary number that represents a given instruction or value that is needed for running any program in the computer. Is this visualization right?

If it is, then
for a 64bit processor, what would be the number of memory cells in the RAM?

No, the author is wrong.

I have used 32 bit processors that could address 64 GB of RAM. Memory is restricted by the number of address lines, multiplied by the number of bytes addressed by each individual value of address lines.

Address space of one application was limited to 4GB, but you could have a dozen applications running at the same time, each using several GB.

The author also seems to be quite ignorant of what processors and operating systems exist.


(When) is hash table lookup O(1)? It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item happens to land in the same bucket and the lookup time becomes linear ($\Theta(n)$).

Are there conditions on the data that can make hash table lookup truly $O(1)$? Is that only on average, or can a hash table have $O(1)$ worst case lookup?

Note: I'm coming from a programmer's perspective here; when I store data in a hash table, it's almost always strings or some composite data structures, and the data changes during the lifetime of the hash table. So while I appreciate answers about perfect hashes, they're cute but anecdotal and not practical from my point of view.

P.S. Follow-up: For what kind of data are hash table operations O(1)?

There are two settings under which you can get $O(1)$ worst-case times.

If your setup is static, then FKS hashing will get you worst-case $O(1)$ guarantees. But as you indicated, your setting isn't static.
If you use Cuckoo hashing, then queries and deletes are $O(1)$ worst-case, but insertion is only $O(1)$ expected. Cuckoo hashing works quite well if you have an upper bound on the total number of inserts, and set the table size to be roughly 25% larger.

There's more information here.


How to prove SPACE-TMSAT is PSPACE-hard? I understand that the language:

$\operatorname{SPACE-TMSAT} = \{⟨M, w, 1^n⟩ : \text{DTM $M$ accepts $w$ in space $n$}\}$

is in PSPACE since it doesn't use more than $n$ space. But to prove that it is PSPACE-complete, we need to do the reduction from any other PSPACE language to it. If we assume the language to run on a DTM using $O(n^k)$ space, how could we reduce it to SPACE-TMSAT?

Suppose $L$ is accepted by some machine $M$ using up to $p(n)$ space, for some polynomial $p(n)$. We map $w$ to $\langle M, w, 1^{p(|w|)} \rangle$.


Examples of Context Free Languages I'm having a hard time thinking of context free languages. The only example I've been able to think of is $0^n1^n$, but I'm having a hard time thinking of any others. Can I get some examples?

Here are some of the examples of context free languages

$\{ w \in \{0,1\}^*\mid \ w$ contains at least three ones }
$\{ w \in \{0,1\}^*\mid \ w = w^{R}$ and $\mid w \mid $ is even  }
$\{ w \in \{0,1\}^*\mid \ $ the length of $w$ is odd and the middle symbol is $0$ }
$\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0 $ and $ i + j = k $ }
$\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0, $ and $ i = k  $ or $i = k$ }
$\phi$

Reference : https://web.njit.edu/~marvin/cs341/hw/hwsoln05.pdf


Approximate Bayesian Computation VS Monte Carlo Simulation I am a little confused about the differences between Approximation Bayesian Computation (ABC) and Monte Carlo Methods (MCM). Citing from wikipedia:

Approximate Bayesian computation (ABC) constitutes a class of computational methods rooted in Bayesian statistics. In all model-based statistical inference, the likelihood function is of central importance, since it expresses the probability of the observed data under a particular statistical model, and thus quantifies the support data lend to particular values of parameters and to choices among different models. For simple models, an analytical formula for the likelihood function can typically be derived. However, for more complex models, an analytical formula might be elusive or the likelihood function might be computationally very costly to evaluate.
Monte Carlo methods (or Monte Carlo experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. [..] Monte Carlo methods are mainly used in three distinct problem classes: optimization, numerical integration, and generating draws from a probability distribution.

In both cases, we run many simulation starting with constant or varying parameters and get the posterior probability (although I am not sure we call that a posterior probability in MCM). I would tend to think that ABC is MCM, where we use the posterior probability to define a confidence interval. Or maybe, by definition MCM are deterministic and therefore the resulting distribution is a function of the parameter values only and therefore it does not make any sense to make any statistical inference (such as calculating an confidence interval). I'd tend to think that ABC is a type of MCM, where we make statistical inference (or whenever the simulation takes a random seed in input). Is that right?

Is ABC a specific case of MCM?
Is ABC just like an MCM except that a random seed is taken in input?

Yes, ABC is a specific application of Monte Carlo method. That application is approximating likelihood functions.

Anything that happens in a computer is actually deterministic. However, ABC, like any other MCM, must have a good pseudo-random generator. There is no difference in the amount of randomness required by the methods.

Examples of Monte Carlo methods which are not ABCs include genetic algorithms and Monte Carlo integration.


Is this language NP Hard? $L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}$ and $n>0$, and $m$ accepts $w$ for a maximum of $n$ moves/steps/operations $\}$

Alphabet is $\Sigma=\{0,1\}$

If this language is NP Hard then what reduction proves it?

My effort to answer this question myself is:

If $L$ is NP Hard then every NP language reduces to $L$ in polynomial time deterministically.

More formally $L\in\Bbb{NPH}\implies\forall L'\in\Bbb{NP}:\;L'\le_PL$

Let $L'$ be any arbitrary NP language.

According to the assumption that $L'\in\Bbb{NP}$ by definition of the complexity class $\Bbb{NP}$ exists non-deterministic Turing machine $m$ that decides $L'$ in polynomial time.

This means that for every word/string $w\in\Sigma^*$:

If $w\in L'$ then $m$ accepts $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

AND

If $w\notin L'$ then $m$ rejects $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

Where $c$ and $k$ are constant non-negative integers and $N$ is the length of $w$.

If $L'\le_PL$ then exists deterministic Turing machine $m'$ that computes function $f:\Sigma^*\rightarrow\Sigma^*$ in polynomial time so that for every word/string $w\in\Sigma^*$:

$w\in L'\iff f(w)\in L$

Let $m'$ be deterministic Turing machine that in the beginning $m'$ inserts the encoding of $m$ before input word/string $w$, which takes constant time $\mathcal{O}(1)$, because the encoding of $m$ is constant word/string and thus the length of the encoding of $m$ is constant non-negative integer, then $m'$ computes the length of the input word/string $w$ by counting all symbols of $w$, which suppose to take linear time $\mathcal{O}(N)$ where $N$ is the length of the input word/string $w$, then compute the power of the computed length by the constant non-negative integer $k$, which takes polynomial time, then multiply the result by the constant non-negative integer $c$, which also takes polynomial time, and at last append the result after $mw$ and the content of the tape of $m'$ will be $(m,w,c\cdot N^k)$ where $n=c\cdot N^k$

After doing all these actions $m'$ halts.

$m'$ is indeed deterministic Turing machine and runs in polynomial time and $w\in L'\iff (m,w,c\cdot N^k)\in L$ followed by the definitions of complexity class $\Bbb{NP}$ and non-deterministic Turing machines.

Hence by definition $L'\le_PL$ because of $m'$

Conclusion: For arbitrary language $L'$ I showed that $L'\le_PL$ holds.

Therefore every NP language reduces to $L$ in polynomial time deterministically and by definition $L$ is NP Hard.

What I wrote above suppose to be a proof that $L$ is NP Hard, but the proof doesn't reduce already proven NP Hard language to $L$, so I think that I did some mistake.

Indeed, this is the prototypical NP-complete language.

Recall what NP-hardness means: For all languages $L'$ in NP, there is a polynomial time reduction from $L'$ to $L$.
Normally, when one wants to prove NP-hardness, one takes a language $L''$ which is itself already known to be NP-hard and establishes a reduction from $L''$ to $L$.

But not so in this case! It is much more natural to directly construct a reduction from $L'$ to our $L$, only using the fact that $L'$ belongs to NP.


Curry-Howard, void, and type checking in Haskell I am trying to understand an example of theorem proving via type checking in Haskell given here. The example is as follows.
Using the Curry-Howard isomorphism, construct an inhabitant of the type and prove that $N= (A\vee (B\rightarrow A))\& (C\&(C\rightarrow B))\rightarrow ((\neg B\& A)\vee ((A\rightarrow B)\&(B\rightarrow A)))$ holds.
The author provides a following code.
data Void
nnot :: Void -> a
nnot = undefined
proposition :: (Either a (b -> a), (c, c -> b)) -> Either (Void -> b, a) (b -> a)
proposition (Left x, (y, f)) = Left (nnot, x)
proposition (Right g, (y,f)) = Left (nnot, (g (f y)))

The implication $(A\vee (B\rightarrow A))\& (C\&(C\rightarrow B))\rightarrow (\neg B \& A)$ does not hold. But the constructed term is claimed to prove it, and the type checker is satisfied by it. Why?
I feel that the transcription of the initial formulae to the type of proposition is incorrect, since the negation of b is represented with Void -> b which is the absurdity (and it is defined as nnot). I.e. from the logical point of view, the pair (Void -> b, a) corresponds to the term $\bot \& A$. But that does not give an answer why the type checker verifies the code above. Thus, I will greatly appreciate any hints on the following two questions.

Why does the Haskell compiler approve the type of proposition?
If that is the case when Curry-Howard is not in place then how I can actually use the type checker to prove formulas with negation via Curry-Howard?

I do not know either this question is more appropriate on cs or stackoverflow, so please sorry if it is off-topic.
EDIT: Given the following corrected proposition:
proposition :: (Either a (b -> a), (c, c -> b)) -> Either (b -> Void, a) (b -> a)

I have written the following "proof" for it, and the type checker was satisfied. I do not know whether I can believe that the proposition can be counted as being proved after the type check.
proposition (Left x, (y, f)) = Right ((\z1 z2 -> z1) x)
proposition (Right g, (y,f)) = Right ((\z1 z2 -> z1) (g (f y)))

And still I have no idea whether it is possible to prove any negation by the type checking procedure.
Edit2: I thought I had got some understanding of the topic, but then I tried the following:
prop1 :: ((Either a b), c) -> b
prop1 (Right x, y) = x

This code is Ok for Haskell (for example, there). But it seems to be ill-typed from the point of view of logic: the corresponding type is $(A\vee B)\& C\rightarrow B$. It is obvious that the case given in prop1(Right x, y) = x has the right (heh) type, but I did not define the case for prop1(Left x, y), thus the proposition is not proved for this case.
Hence, I can have problems with the disjunction as well.

I would find a different tutorial because the author of that one is fundamentally confused. They wrongly claim that $\neg a$ and $\bot\to a$ are equivalent ($a\to\bot$ would be correct), and also wrongly claim that you can't write a function of type $\texttt{Void}\to a$.
$\texttt{Void}\to a$ is vacuously true. In principle a function of that type should require no definition at all because the number of cases for which you need to define it is zero. GHC doesn't accept that, but (with -XEmptyCase) it does accept
f :: Void -> a
f x = case x of {}

which is a perfectly valid, logically sound definition.

Why does the Haskell compiler approve the type of proposition?

The proposition as written in the Haskell code is actually true. The proof is invalid though since it uses $\texttt{undefined}$.
If you replaced the right hand side with $(b\to\texttt{Void},a)$ then it would be false, but you could still "prove" it using $\texttt{undefined}$; in fact you could just write $\texttt{proposition} = \texttt{undefined}$ and the type checker would accept that. It would also accept $\texttt{proposition} = \texttt{proposition}$. If you want to use Haskell as a Curry-Howard sandbox you have to take care that your code doesn't throw an exception or fail to terminate, because the compiler won't catch those errors.

Response to edit: your proof is correct but it can be simplified. In the first case, there's no need to create a function and immediately apply it to one of its arguments. Instead of (\z1 z2 -> z1) x you can write \z2 -> x, or \_ -> x since the argument/premise isn't used. In the second case, you don't need to prove b -> a since you already have g :: b -> a. The simplified proof is
proposition (Left x, _) = Right (\_ -> x)
proposition (Right g, _) = Right g

In addition to the pitfalls that Dan Doel mentioned in a comment, missing cases are another thing to watch out for. GHC by default doesn't even warn about them. With -Werror=incomplete-patterns it will refuse to accept programs with missing cases.
You can prove negations. You need to return a value of type $\texttt{Void}$, which you can't create yourself but you can get from elsewhere. For example here's a proof of $((P\Rightarrow Q) \mathbin{\&} \neg Q)\Rightarrow \neg P$:
f :: (a -> b, b -> Void) -> (a -> Void)
f (x, y) = \z -> y (x z)

You may reasonably wonder where your caller got the value of type $\texttt{Void}$, but that's the caller's problem, not yours. Deriving a contradiction in a subproof doesn't mean the logic is inconsistent, it just means you've shown that you'll never actually reach this point in the real world.


Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity? Kolmogrov complexity is known to be uncomputable.  Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, increment i and iterate? Won't that prove that no program of length < i generates string s?

The problem with your approach is that some programs never halt, and it's difficult (indeed, uncomputable) to tell whether they do. You can tell if a program outputs $s$ and halts, but you don't know how much to wait before declaring that the program never halts. However, your approach shows that it is possible to write a program that prints upper bounds on the Kolmogorov complexity of a give string, eventually printing the correct upper bound. This doesn't give you the Kolmogorov complexity since you don't know when the program will have printed its final upper bound.


Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector? Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables.

If we set the $c^T$ vector of the objective $\text {maximize } c^Tx$ to all one (unweighted, i.e., $c^T=(1,1,\dots,1)$) is the problem still NP-hard?

We can encode satisfiability of a SAT instance as the feasibility of a 0-1 integer linear program. For feasibility, the objective function doesn't matter, so you can impose whatever constraint you wish on it.

For an example of how to express boolean or, boolean and, and boolean negation in a 0-1 integer linear program, see Express boolean logic operations in zero-one integer linear programming (ILP).  This is all that's needed to express a SAT instance as a 0-1 integer linear program.


task scheduling optimization problem I'm interested in such problem. I have a set of $n$ tasks ${T_i}$ and directed acyclic graph, which nodes correspond to tasks and edges correspond to order of execution two tasks. In other words if I have edge $T_i \rightarrow T_j$ it means that task $T_i$ should be executed in day which strictly before day of execution $T_j$. All tasks should be executed within $m$ days, every task should be executed exactly once. Execution of task $T_i$ in day $j$ costs $C_{ij}$ dollars. There is no restriction on number of tasks executed in one day. I should minimize total cost of execution all tasks.

Can one solve this problem in polynomial time?

My idea is only to bruteforce topological sorting and dynamic programming then, but it is too slow.

ADD: I can solve problem, when given DAG is forest. It can be done by simple dynamic programming, where states are $(T_i, j)$, which means that $T_i$ is executed in day $j$ and subtree tasks are executed within constraints.

ADD: I've read this paper, 13.3 Layer Assignment, p. 417.
Also this problem can be formulated in terms of weighted CSP, we need to minimize such value $\sum\limits_{v \in V}C_{v \sigma(v)} + \sum\limits_{(u,v) \in E} D_{\sigma(u)\sigma(v)}$, where $\sigma(v)$ is day when task $T_v$ is executed, $D_{ij} = \begin{cases} 0 &\mbox{if } i < j \\
\infty & \mbox{if } i \ge j \end{cases}$.

These kinds of problems are usually studied under the banner of Operations Research or Operational Research, and this is still an active area after several decades.
See the Graham et al. survey from 1979 (doi:10.1016/S0167-5060(08)70356-X) for the standard terminology and many older references.
It looks like your problem is $P|\text{prec},p_{ij}=1|\sum_j C_{ij}$ which seems too general to have been studied back then.

You don't describe the kinds of task graphs you work with, but in my experience many practical task graphs from computer science lead to an explosion of chains of tasks to consider, making it hard to do dynamic programming, while task graphs from other fields often are more amenable to dynamic programming.
When the structure of the task graph is "nice", then one can do better.
For instance, series-parallel task graphs often lead to polynomial-time algorithms.

Without knowing more about the details of your problem, I'd say it sounds NP-hard on general task graphs due to the costs, but it may well be possible to exploit special features of the task graphs (or perhaps the costs) to design an efficient algorithm.


Are all calculations graphs? I've come to understand that programs are graphs on several layers. Call-graphs are an example that come to mind without a textbook handy, another is mutation flow.

So I  do understand that code is a graph, and that compilers and interpreters usually end up traversing the graph according to the rules of the language. It's magic, really, but here is my question:

Are all calculations graphs? Are there calculations that cannot be expressed as a state machine?

I wouldn't say that code is a graph.  I would say that graphs are a convenient way to represent some aspects of graphs.

There is a sense in which every computation on your computer can be expressed as a state machine: if your computer has 8 billion bits of memory, then there are at most $2^{8,000,000}$ possible states, so it can be considered as a state machine on that state space.  However, that probably isn't a very useful point of view.  Instead, we usually model computers as Turing machines (or in another way), and those cannot be expressed as a finite state machine.

The question of whether all computations are graphs doesn't seem well-defined to me.  Presumably graphs can be used to represent some aspects of computations, but that doesn't mean the calculation is a graph (or that it is nothing more than a graph).


Word ladder problem for words with different length Is there some one who know any algorithm for word ladder problem with words of different length?

Actually we have some strings with same length and some strings with one length longer but not from any size(any size means:  one string with size 10 and one string with size 1000).

any link or advise is acceptable.

my solution is this: build a graph with strings in the nodes and nodes are connected if their strings can be converted to each other just by changing one letter, then using BFS.

word ladder problem

Your algorithm that runs breadth-first search (BFS) on the graph built with words as nodes and pairs of words that differ by one letter as edges is the natural algorithm to solve the problem, whether the words are different lengths or not.

I would just call call your algorithm as a BFS algorithm. It is classic application of BFS to search for the shortest paths between two nodes of a graph where the length of a path is simply the number of its edges.

If we let the BFS algorithm run until all nodes has been visited, then it will be able to find all shortest paths between a source node and all other nodes.

You can find some detailed comparison between BFS and Dijkstra algorithm for shortest path in a graph here.


How to delete an element from a B-tree There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree.

For example, given the following tree, how would we delete 26 and 63?

Is there a general approach?

All of the keys you want to delete in this particular example belong to the case when we are deleting keys from a leaf node, without need to rebalance a tree after deletion.

Algorithm for deleting a key from a leaf node consists of three steps:

1) Search for the value to delete.

2) If the value is in a leaf node, simply delete it from the node, because there are no subtrees to worry about.

3) If underflow happens (i.e., if we break one of the defining rules/properties of a B-tree - every non-root node has to have at least (M-1)/2 keys), rebalance the tree.

Also, if you are interested in implementation of rebalancing algorithm, beyond the scope of the given example, I suggest these sources:

https://www.youtube.com/watch?v=vqIxJaNrPI4

https://webdocs.cs.ualberta.ca/~holte/T26/del-b-tree.html


Difference between spanning tree and a tree? Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem relevant to computer science. My professor in my algorithms class makes the distinction between a spanning tree and a regular tree; but never says what the difference really is. The only thing I notice is that he uses the word spanning tree when he is talking about graphs.

Is a spanning tree simply when a graph takes on a tree structure? In other words, the raw data structure under the hood is a graph, but it takes on some characteristics of a tree? Or is it something else?

Given a graph $G$,
a spanning tree is a subgraph of $G$ that (i) is a tree, and (ii) has all the vertices in $G$.

There can be many spanning trees for $G$. If you put weights on the edges, one of these spanning trees will have a minimal sum of weights. This is the minimal spanning tree.

Regular (sub)tree is just subgraph which is a tree - it doesn't have all the nodes in $G$: it satisfies property (i) above, but not necessarily property (ii).


Index of a language and its reversal The index of a language is the number of Myhill-Nerode classes that it has. It is also equal to the number of states in the minimal DFA for the language. What is an example of a language that has a different index from its reversal?

The $k$th letter equals $a$, for fixed $k$, assuming a two letter alphabet.

This generic answer is made precise in the comment by @AntonTrunov below.


Describe regular expression I am learning about regular expression, and  trying to describe a regular expression for the language L

$\qquad L = \{a^i b^j c^k \mid i+j = k\}$

What is the right approach and how to describe a regular expression like this?

It seems I didn't understand the question.
There is no regular expression for this language because it is not regular. You can prove it using the pumping lemma.


Solving the recurrence $T(n) = n^{3/4}(^{1/4})+ n $ I need to solve the following recurrence relation: $T(n) = n^{3/4}(^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)=T(e^x)$. I was able to get to $F(x)= e^{3x/4} \cdot F(x/4)+ e^x$. However, the master theorem still doesn't apply at this stage. How can I proceed?

You can just expand it:
$$
\begin{align*}
T(n) &= n + n^{3/4} T(n^{1/4}) \\ &=
n + n^{3/4}\cdot [n^{1/4}+ n^{3/16}\cdot T(n^{1/16})]  \\ &=
n + n + n^{3/4} \cdot n^{3/16} T(n^{1/16}) \\ &=
n + n + n + n^{3/4} \cdot n^{3/16} \cdot n^{3/64} T(n^{1/64}) \\ &=
\cdots
\end{align*}
$$
We see that $T(n) = C(n) n$, where $C(n)$ is the number of times we need to apply $n \mapsto n^{1/4}$ until the answer drops below some constant.

I'll let you figure out $C(n)$, and so complete this exercise.


2D convolution: Flipping the kernel? Why do we need to flip the kernel in 2D convolution in the first place?
What's the benefit of this?
So, why can't we leave it unflipped?
http://www.songho.ca/dsp/convolution/convolution2d_example.html

input

kernel

output

"First, flip the kernel, which is the shaded box, in both horizontal and vertical direction"

If you do not flip the kernel, you simply obtain a different operation that is called cross correlation. When the filter is symmetric, like a Gaussian, or a Laplacian, convolution and correlation coincides. But when the filter is not symmetric, like a derivative, you get different results.

The reason why convolution is preferred over correlation is that it has nicer mathematical properties. In particular, convolution is associative, while correlation in general is not.

For a more technical explanation we need to go into the frequency domain.
The main theorem of convolutions states that the Fourier tansform of the convolution $f*g$ of two functions $f$ and $g$ is equal (up to a constant depending on the transformation) to the product of the Fourier transforms of the two functions. In symbols

$$ {\mathcal {F}}\{f*g\}=k\cdot {\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}$$

where $\mathcal {F}$ is the Fourier transform. In the case of correlation, you would get multiplication by the complex conjugate, that is less nice, and in particular not associative.

Another interesting property of convolution is that convolving a kernel with
a unit impulse (e.g. a matrix with a single 1 at its center and 0 otherwise),
you get the kernel itself as a result. Correlation would flip the kernel,
instead.


Is there any mechanism where the kernel portion of an OS in memory may also be swapped? I'm recently learning the part of I/O buffering of operating system and according to the book I use,

  When a user process issues an I/O request, the OS assigns a buffer in the system portion of main memory to the operation.

I understand how this method is able to avoid the swapping problem in non-buffering situation. But is it assumed that the OS buffering created for the process will never be swapped out?

To extend my question, I was wondering if there is any mechanism where  the kernel portion of an OS in memory may also be swapped?

Indeed, it wouldn't make sense to swap out an I/O buffer. The point of that buffer is that it's in RAM. The code to perform the I/O and the code to manage swap must not be swapped out either.

Other kernel code can be swapped out, in principle. However this can be problematic for several reasons. Hardware drivers that aren't involved in swap could be swapped out, but this means the kernel had to be very careful about the whole data party to swap (which may involve a disk over some external communication bus or even the network, as well as filesystem code when swapping to a file). Furthermore a lot of driver vice is very performance-sensitive: the kernel had to read it send data when the hardware is ready and may not be able to afford the time to bring vice and data back out of swap. In addition, RAM is usually assumed to be reliable (it's acceptable for the system to crash if the RAM fails), but swap (on disks or over the network) isn't, and it's difficult to design a kernel that can recover if part of it becomes unavailable. Most kernels take the simple approach and never swap out kernel code and data.


Average codeword length in a Huffman tree is $\Omega(\log n)$ Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters.

My try:

I think that the worst case is when the tree is full and all the characters are in the highest level.

Therefore: $n=2^h \to h=\log n$, and the average codeword length is $\Omega(\log n)$.

Am I missing something?

This answer assumes that by average you mean just that – the sum of all codeword lengths divided by $n$.

Let us show that any prefix code satisfies your property. Consider any prefix code whose codewords have lengths $\ell_1,\ldots,\ell_n$. Kraft's inequality shows that
$$
2^{-\ell_1} + \cdots + 2^{-\ell_n} \leq 1.
$$
The function $x \mapsto 2^{-x}$ is convex, hence
$$
\frac{1}{n} \geq \frac{2^{-\ell_1} + \cdots + 2^{-\ell_n}}{n} \geq 2^{-(\ell_1+\cdots+\ell_n)/n}.
$$
It follows that
$$
\frac{\ell_1 + \cdots + \ell_n}{n} \geq \log_2 n.
$$
Since $x \mapsto 2^{-x}$ is strictly convex, there can be equality only if $\ell_1 = \cdots = \ell_n$, that is, only if all codewords are of length exactly $\log_2 n$. That can only happen if $n$ is a power of 2. This leaves open the following question:

  What is the minimum average codeword length of a prefix code on $n$ symbols?

(We note in passing that every prefix code satisfying Kraft's inequality tightly is a minimum redundancy code for some distribution, namely the one in which the probability of the $i$th symbol is $2^{-\ell_i}$.)

To answer this, let us note that convexity implies that if $a < b$ then
$$
2^{-a} + 2^{-b} \geq 2^{-(a+1)} + 2^{-(b-1)}.
$$
(We can also see this directly: without loss of generality $a=0$, and then we need to prove $1 + 2^{-b} \geq 1/2 + 2 \cdot 2^{-b}$, that is, $1/2 \geq 2^{-b}$, which follows from $b \geq 1$.)

Applying this operation repeatedly starting at some arbitrary integer solution of Kraft's equation, we eventually reach a solution which involves at most two different values $\ell,\ell+1$. If $n = 2^k + m$, where $0 \leq m < 2^k$, then this solution must consist of $2^k - m$ many $k$'s and $2m$ many $k+1$'s. Hence the optimal average codeword length is
$$
\frac{k(2^k-m)+(k+1)2m}{2^k+m} = k + \frac{2m}{2^k+m}.
$$


Does a non deterministic Turing machine which is a decider halt on all branches for all inputs? Does a non deterministic Turing machine which is a decider halt on all branches for all inputs??

I know it must halt on all branches for a string not in language, but for a string in language, NDTM requires only one accepting branch so even if some other branch is infinite, NDTM will still accept the string

You can define it either way.  The simple way to  define it is to say that every branch must halt for every input.  Alternatively, you can say that, if the input is in the language, at least one branch must accept, so you don't care if the others reject or just fail to halt; if the input is not in the language, then every branch must reject.

Both in terms of computability and complexity, you can show that the two definitions are completely equivalent.


How to use the Pumping Lemma to prove that a restricted subset of 0*1*2*3*, where there are as many 3's as 0's and 1's, is not a CFL? Use the pumping lemma for context-free languages to show that the following
  language is not context-free: $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $

So I have started like this:

Let us assume that $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $ is a context-free language. Then $ ∃ p∈N $ such that $∀ w∈L$, $|w|≥p$, then $∃ u,v,x,y,z∈Σ^*$ such that we can write $w=xuyvz$ which is subject to the following conditions:

$
 |uyv|≤p\\
 |uv|>0\\
 ∀ k≥0,xu^k yv^k z∈L
$

Now, let $p$ be the constant in the Pumping lemma and let $w=0^q 1^p 2^q 3^{p+q}$.

Here I have gotten stuck. I am not sure about my choice of $w$ and very unsure about what I can actually say about $w$ since I know nothing about $q$ compared to $p$ except that the number of $3$'s is $p+q$. I am even doubting that it is possible to show that $L$ is not context-free. At the moment there is always the possibility that $uyv$ is in both the $1$'s and $3$'s or the $0$'s and $2$'s (if I swap $p$ and $q$), and then I could possibly pump them just fine.

What am I missing here? Been starring myself blind trying to find it.

Use $|uyv|\le p$ to avoid the cases you mention, e.g., that $u,v$ pump both the $1$'s and the $3$'s. You can choose $p,q$ in $w$ such a way that this way of pumping is not possible. There is no problem in choosing $p=q$!


One-dimensional k-center problem. Finding minimum distance This is a follow-up to this question: Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be
$$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

Which algorithm should i use to get minimal possible value of $d(X,Y)$?

I tried do develop dynamic programming algorithm but didn't succeed. In my previous question i was told that this problem is known as unweighted one-dimensional k-center problem. I've looked through some papers on the net but all of them offered the ways to find some particular $Y$. But my current problem seems to be easier: i need only the optimal value of $d(X,Y)$. So i expect the solution to be rather standard and rather easy.

Thanks in advance.

P.S. The original problem is taken from here:
http://www.e-olymp.com/en/problems/3208

Hint: Turn the problem upside down and ask yourself: can I easily check if the answer is less than or equal to $t$?


Abstract Data Types and their Implementation I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.

I would say Algorithms by Robert Sedgewick and Kevin Wayne is a classic book which explains quite well the basics of these concepts.

However you could also find a lot of resources on the web for free.


Decidability of language of TMs which accept only their Gödel number I am trying to prove that $L = \{\langle M \rangle  \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$.

I think I can't use Rice's theorem, so I tried to find a reduction. The halting problem for example does not help me in this case. Do you have any idea how to prove it?

The recursion theorem states that if $A(x,y)$ is a two-input Turing machine then there is a Turing machine $M$ such that $M(x) = A(x,\langle M \rangle)$. Moreover, $M$ can be constructed from $A$ effectively (i.e., using an algorithm). Using this, we can reduce the halting problem to your problem. Given a Turing machine $B$ and an input $z$, construct a new Turing machine $A(x,y)$ which acts as follows:

If $x = y$ then simulate $B$ on $z$.
Otherwise, enter an infinite loop.

Use the recursion theorem to construct a new machine $M$ that on input $x$ acts as follows:

If $x = \langle M \rangle$ then simulate $B$ on $z$.
Otherwise, enter an infinite loop.

Then $M \in L$ iff $B$ accepts $z$.


Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$ I recently thought of the following problem:

Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$.

For example, if $A = \{ \{ 1, 2 \}, \{ 1, 2, 3 \}, \{3, 4\}, \{4\} \}$ then $B = \{ \{ 1, 2 \}, \{ 3 \}, \{ 4 \} \}$.

I designed the following algorithm:

Let $B = \emptyset$ initially.
Let $S$ be the set of set(s) of lowest of cardinality in $A$.
Let $I$ be the intersection of the sets in $S$.
If $I = \emptyset$: add the sets in $S$ to $B$, remove the elements in the sets in $S$ from the sets in $A$, and remove $\emptyset$ from $A$.

If $I \neq \emptyset$: add $I$ to $B$, remove the elements in $I$ from the sets in $A$, and remove $\emptyset$ from $A$.
Repeat from step 2 until $A = \emptyset$.

My questions are:

Does this problem have a name?
Is this algorithm correct?
What is the complexity of this algorithm?
Is this algorithm optimal, and if not, what would be a better algorithm?

Essentially you are finding all non-empty components of the Venn diagram of the sets in $A$. So here is an algorithm:

B = empty set
for each set S in A:
    for each set T in B:
        remove T from B
        compute (S \cap T), (T \ S) and (S \ T)
        if (S \cap T) is not empty, add (S \cap T) into B
        if (T \ S) is not empty, add (T \ S) into B
        S = S \ T
    if S is not empty, add S into B
return B

This algorithm runs in $O(nm)$ time where $n$ is the number of all elements involved, and $m$ is the number of sets in $A$.

For your example, initially $B$ is empty.

After dealing with $\{1,2\}$, $B=\{\{1,2\}\}$.

After dealing with $\{1,2,3\}$, $B=\{\{1,2\},\{3\}\}$.

After dealing with $\{3,4\}$, $B=\{\{1,2\},\{3\},\{4\}\}$.

After dealing with $\{4\}$, $B=\{\{1,2\},\{3\},\{4\}\}$.


Optimal scalability of a distributed algorithm What's the optimal scalability of some algorithm when I implement it in a distributed manner?

Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes. I.e, if algorithm A takes T units of time with 1 computing node on input I, it can't run faster than T/n units of time  with n computing nodes on the same input I.

Is my intuition correct or are there some weird counter-examples to it?

Yes, your intuition is correct, for all the reasonable models of computation that I'm familiar with.  If it weren't, then we could take a single machine and have it simulate a cluster of n nodes, increasing the cost by only a factor of n.  So, if you had an algorithm that ran on a cluster of n nodes faster than T/n, you'd get an algorithm that runs on a single node faster than T.

Note that the single node might need to have n times as much memory as each node in the cluster.


How to use dynamic programming to solve this? Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies and toonies you have. Assume that you have enough coins to pay x cents. You do not have to pay exactly x cents; you can pay more. The cashier is assumed to be smart enough to give you back the optimal number of coins as change. We want to minimize the number of coins that changes hands, that is the number of coins you give to the cashier plus the number of coins the cashier gives back to you.

For example, if we want to pay 99 cents and we have 99 pennies and 1 loonie, then the optimal solution would be to give the cashier the loonie and take back 1 penny.

A particularly easy solution that occurs to me is to create a six-dimensional array. But in practice this is not feasible. So I am wondering if anyone can give me a small hint as to how to use dynamic programming to solve this (as this question looks intuitively to me like a DP problem). Once I have a hint, I can perhaps work out the remaining details myself. Thanks.

This is the famous change-making problem.

If you want to solve it with dynamic programming, you have to come up with a suitable recursion. The central question is:

  Assuming you know the optimal coin choices for all $k < n$ (cents), how do you derive the optimal choice of coins for $n$ (cents)?


Learning Automated Theorem Proving I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

Note that these topics are not easily digested without a background in (mathematical) logics. If you have problems with basic terms, please read up on those, for instance Logics in Computer Science by M. Huth and M. Ryan (in particular chapters one, two and four) or An Introduction to Mathematical Logic and Type Theory by P. Andrews.
For a short introduction into higher order logic (HOL) see here.

I looked at Coq and read the first chapter of the intoduction to Isabelle amongst others; Types of Automated Theorem Provers

I have known Prolog for a few decades and am now learning F#, so ML, O'Caml and LISP are a bonus. Haskell is a different beast.

I have the following books

"Handbook of Automated Reasoning" edited by Alan Robinson and Andrei Vornkov

"Handbook of Practical Logic and Automated Reasoning" by John Harrison

"Term Rewriting and All That" by Franz Baader and Tobias Nipkow

What are the differences between Coq and Isabelle?
Should I learn either Isabelle or Coq, or both?
Is there an advantage to learning either Isabelle or Coq first?

Find the series' next question here.

My preference is for Coq, but I imagine that others prefer Isabelle. One of the strange things I found about Isabelle is that there is a two-level syntax, where some of your definitions need to be inside double quote. No such nonsense is present in Coq.

Ultimately, the one that is most suitable for you may depend on what you want to prove. Both languages have a lot of library support and active communities doing all sorts of development and example theories. If one language provides  adequate library (or other) support for the kinds of theory you wish to develop, then I'd select that language.

One strategy is to do a simple tutorial in both languages and follow up the one that feels the best. For example,

Coq in a Hurry by Yves Bertot, or
the first part of A Proof Assistant for Higher-Order Logic by Tobias Nipkow, Lawrence C. Paulson and Markus Wenzel.

Here is a blog post briefly comparing the two by someone who ultimately prefers Isabelle.

Make sure you use a proper IDE (such as ProofGeneral), rather than doing things on the command line.

Another way to to get into Coq is to try the online book Software Foundations by Benjamin Pierce et al. It provides an excellent tutorial with loads of details provided. The focus is mostly on programming language semantics, but a lot of the basics (and beyond) of Coq and semi-automated theorem proving are covered along the way.