How to prove correctness of a shuffle algorithm? I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased).

The first method I use is to construct the entire list of elements and then do a shuffle on it (say a Fisher-Yates shuffle). The second method is more of an iterative method which keeps the list shuffled at every insertion. In pseudo-code the insertion function is:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

I'm interested in how one goes about showing the fairness of this particular shuffling. The advantages of this algorithm, where it is used, are enough that even if slightly unfair it'd be okay. To decide I need a way to evaluate its fairness.

My first idea is that I need to calculate the total permutations possible this way versus the total permutations possible for a set of the final length. I'm a bit at a loss however on how to calculate the permutations resulting from this algorithm. I also can't be certain this is the best, or easiest approach.

First, let us make two maybe obvious, but important assumptions:

_.random_item can choose the last position.
_.random_item chooses every position with probability $\frac{1}{n+1}$.

In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here:

For the singleton list there is only one possibility, so it is uniformly chosen.
Assuming that the list with $n$ elements was uniformly chosen (from all permutations), show that the one with $n+1$ elements obtained by your technique is uniformly chosen.

From here on, the proof is wrong. Please see below for a correct proof; I leave this here because both the mistake and the following steps (which are sound) might be educational.

It is useful to derive a local (i.e. element-wise) property that has to hold, because arguing about the whole permutation is painful. Observe that a permutation is uniformly chosen if every element has equal probability of being at each position, i.e.

$\qquad \displaystyle \mathop{\forall}\limits_{\pi \in \mathrm{Perm}_n} \operatorname{Pr}(L = \pi) = \frac{1}{n!} \quad \Longleftrightarrow \quad \mathop{\forall}\limits_{i=1}^n\ \mathop{\forall}\limits_{j=1}^n \operatorname{Pr}(L_i = j) = \frac{1}{n} \qquad (1)$

where $n = |L|$ and we assume for the sake of notational simplicity that we insert $\{1,\dots,n\}$ into the list.

Now, let us see what your technique does when inserting the $n+1$st element. We have to consider three cases (after the swap):

One of the elements in the list, not swapped, i.e. $i \in \{1,\dots,n\}$ and $j \in \{1,\dots,n\}$
One of the elements in the list, swapped, i.e. $i = n+1$ and $j \in \{1,\dots,n\}$
The new element, i.e. $i \in \{1,\dots,n+1\}$ and $j = n+1$

For each case, we compute the probability of element $j$ being at position $i$; all have to turn out to be $\frac{1}{n+1}$ (which is sufficient because of $(1)$). Let $p_n = \frac{1}{n}$ be the probability of one of the first $n$ elements being at any position in the old list (induction hypothesis), and $p_s = \frac{1}{n+1}$ the probability of any position being chosen by random_item (assumptions 1, 2). Note that the coice of the list with $n$ elements and picking the swap position are independent events, so the probabilities of joint events factor, e.g.

$\qquad \displaystyle \operatorname{Pr}(L_i=j, i \text{ swapped}) = \operatorname{Pr}(L_i=j)\cdot \operatorname{Pr}(i \text{ swapped}) = p_np_s$

for $i,j \in \{1,\dots,n\}$. Now for the calculations.

We only consider the old $n$ elements. Such an element $j$ is at position $i$ if and only if it was there before the last insertion and $i$ is not selected as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_n(1-p_s) = \frac{1}{n}\cdot\frac{n}{n+1} = \frac{1}{n+1}$.
Here we consider that one of the old elements is swapped to the last position. Element $j$ could have been at any of the old positions, so we sum over all probabilities that $j$ was at position $i$ and $i$ is chosen as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L_{n+1} = j) = \sum_{i=1}^n p_np_s = \sum_{i=1}^n \frac{1}{n}\cdot\frac{1}{n+1} = \frac{1}{n+1}$.
The new element ends up at position $i$ if and only if $i$ is chosen as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_s = \frac{1}{n+1}$.

All turned out well, your insertion strategy does indeed preserve uniformity. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

A word of warning: this proof breaks down if the inserted elements are not pairwise different resp. distinguishable, because then the very first equation is no longer valid. But your algorithm is still valid; every permutation with duplicates is generated by the same number of random executions. You can proof this by marking duplicates (i.e. making them distinguishable), perform above proof and remove the markings (virtually); the last step collapses equal sized sets of permutations to the same.

As Steven has remarked correctly in the comments, above proof is fundamentally flawed as $(1)$ does not hold; you can construct distributions on the set of permutations that fulfill the right-hand, but not the left-hand side¹.

Therefore, we will have to work with probabilities of permutations, which turns out to be not that bad after all. The assumptions on random_item and the inductive structure outlined in the very beginning of the post remain in place, we continue from there. Let $L^{(k)}$ denote the list after $\{1,\dots,k\}$ have been inserted.

Let $\pi' \in \mathrm{Perm}_{n+1}$ an arbitrary permutation of $\{1,\dots,n+1\}$. It can be written uniquely as

$\qquad \displaystyle \pi' = (\pi(1), \pi(2), \dots, \pi(i-1), n+1, \pi(i+1), \dots, \pi(n), \pi(i))$

for some $\pi \in \mathrm{Perm}_n$ and $i \in \{1,\dots,n+1\}$. By induction hypothesis, $\operatorname{Pr}(L^{(n)} = \pi) = \frac{1}{n!}$. Furthermore, random_item picks position $i$ with probability $\frac{1}{n+1}$ by assumption. As the random choices of $\pi$ and $i$ are (stochastically) independent, we get

$\qquad \displaystyle \operatorname{Pr}(L^{(n+1)} = \pi') = \operatorname{Pr}(L^{(n)} = \pi) \cdot \operatorname{Pr}(i \text{ swapped}) = \frac{1}{(n+1)!}$

which we had to show. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

For example, assign every permutation in $\{(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)\}$ probability $\frac{1}{4}$ and all others $0$. There are also examples that assign every permutation a non-zero probability.


Average access time in two level cache system In a two-level cache system, the level one cache has a hit time of 1 ns (inside the CPU), hit rate of 90%, and a miss penalty of 20 ns. The level two cache has a hit rate of 95% and a miss penalty of 220 ns. What is the average memory access time?

What is a two-level cache system and how to calculate the time required? Since the hit time of level two cache is missing...

First Let's define all given things

L1 Cache hit: 90% & Time: 1ns

L2 and RAM has hit rate 10% out of which 95% which is 9.5% in total

L2 Cache hit: 9.5% & Time 20ns

RAM has hit rate 5% of 10% = 0.5%

RAM hit: 0.5% & Time 220ns

Formula Avg Memory Access Time

AMAT = L1_hit * L1_T + L2_hit * L2_T + RAM_hit * RAM_T

AMAT = 0.9*1 + 9.5*20 + 0.5*220

AMAT = 300.9ns

What is 2 level cache system:

First cache called L1 is reside on CPU is too fast. When CPU needs data, it checks in L1 cache but if it is not there it will go to L2. L2 cache is sometimes on CPU or outside CPU it depends on architecture of CPU. It does similarly and here also it missed then it fetch data from RAM which is expensive process.


Why can System F1 a.k.a. λ → have kind `*`, but no quantification `∀`? In Types and Programming Languages by Pierce, on p461 in Section 30.4 Fragments of Fω

  30.4.1 Deﬁnition: In System F1 , the only kind is * and no quantiﬁcation (∀) or abstraction (λ) over types is permitted.

  F1 is just our simply typed lambda-calculus, λ → . Its deﬁnition is super-
  ﬁcially more complicated than Figure 9-1 because it includes kinding and
  type equivalence relations, but these are both trivial: every syntactically well formed type is also well kinded, with kind *, and the only type equivalent to a type T is T itself

Is it correct that  quantification ∀ means universal types?

* is the kind of proper types, which are introduced on p442:

  The level of types contains two sorts of expressions. First, there are proper
  types like Nat, Nat→Nat, Pair Nat Bool, and ∀X.X→X, which are inhabited
  by terms. (Of course, not all terms have a type; for example (λx:Nat.x) true
  does not.)

So universal types such as ∀X.X→X are proper types, and thus belong to kind *.
Why can System F1 have kind *, but no universal types, i.e. quantification ∀?

But if System F1 could have kind * and quantification ∀, then wouldn't it become the same as System F2 a.k.a. System F? Quoted from on p461:

  In System F2 , we still have only kind * and no lambda-abstraction at the level of types, but we allow quantiﬁcation over proper types (of kind *).

  F2 is our System F;

Thanks.

Why can System F1 have kind *, but no universal types, i.e. quantification ∀?

Because "System F1 has types of kind *" does not mean "any types which have kind * in some other system (e.g. universal types) are allowed in F1".


What does $|w|$ mean in the statement " $|w|$ where $w \in L \subset \Sigma^*$"? In my assignment I find these symbols:

$|w|$ where $w \in L \subset \Sigma^*$

I believe it means the lexikografic value of a word, but I am not 100% certain.

Let me phrase my question this way: could this notation have any other meaning ?

Usually, $\Sigma^*$ denotes the set of all strings obtainable from an alphabet $\Sigma$.

Most probably, $L$ is a language and $w$ is a word. A language is a subset of the alphabet $\Sigma^*$, thus $L \subset \Sigma^*$.

A word, on the other hand, is a single string obtained from the language $L$.

As an example:

$\Sigma = \{0,1\}$
$\Sigma^* = \{0, 01, 10, 11, 100, 101, \dots, 1011001001, \dots\}$
$L \gets$ all strings containing an even number of zeroes
$w \gets 100010$

And $|w|$ is probably the length of $w$.


Notation Conventions for Tree Data Structures I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to set notation conventions that will not drive other people insane. The primary difference is that this algorithm makes use (logically) of tree data structures while the traditional algorithms in the field have used linear arrays.

The old algorithms therefore could denote specific data as $data_i$ (that is, using LaTex subscripts. Similarly, one could refer to $data_{i-1}$, and it would be clear that that is the "parent" data to $data_i$. Unfortunately, trees do not support this sort of indexing.

Are there any notation conventions for trees that allow clear, concise descriptions of that sort? I want to be able to give talk about an arbitrary bit of data (i.e. $data_i$) and readily discuss parent and child data. The community is mathematician heavy and as such mathematical notation of the sub/superscript y operator sort is favored over the class.property CS style. Note also that these are arbitrary trees; they need not be binary or any other such structure.

Does anyone know of a notation convention that would fit the bill? Alternatively, is there a better place to ask this? Thanks for the help.

You can use functions.

Let $node$ be an arbitrary node of the tree.

Then $data(node)$ is data associated with $node$, $children(node)$ is set of child nodes of $node$ and $parent(node)$ is parent of $node$.

For data associated with $i^{th}$ child of $node$ you can use $data(children(node)_i)$ etc.


Dana Angluin's L* algorithm - Hypothesis inconsistent is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent?

So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will get a counterexample w.

The Question is: Can the counterexample w be chosen in the hypothesis, so that I have two times the same counterexample?

Unfortunetaly I could not find any language and counterexample where it will work.

I have no idea what it would mean for a hypothesis to be inconsistent in this context, but the answer to your second question is: No.  You won't receive the same counterexample twice.

The teacher returns a counterexample $w$.  Here a hypothesis is a DFA (a regular language) and $w$ is a word that the DFA gets wrong (either the DFA accepts, but $w$ is actually not in the language to be learned; or the DFA rejects, but $w$ is actually in the language to be learned).  Angluin's L* algorithm constructs a new DFA that is correct on all of the counterexamples that have been returned so far.  Since this DFA is correct on all past counterexamples received from the teacher, we will definitely never get the same counterexample a second time.


Why do some filesystems have fragmentation and others don't? I try to understand why fragmentation is a problem for NTFS and FAT but not when using inodes.
In all cases, files are not necessarily stored in a contiguous fashion so I don't see the problem for the former two.

So where is the crucial difference?

I think the term inode is misplaced here.  I am unaware of any way in which Inodes have anything to do with optimizations to reduce disk fragmentation.  The term inode goes back to Unix Version 1 from 1971.  It was not until the Berkeley Fast File System in BSD 4.2 in 1983 that anything significant was done to combat disk fragmentation.  In Unix systems the term inode refers to the data structure that holds all the metadata for a file (its length,  permissions, owner, and the pointers to the data blocks for the file (arranged as a tree in most Unix file systems since 1983.)  The file name is not stored in the inode.  Rather directory entries contain the name and an inode number.

NTFS has a data structure analogous to the inode, that contains similar information, and similarly does not contain the file name.  In NTFS this structure is called a master file table entry.   Given the similarities between an inode and NTFS's master file table entries, I can't see any impact on any kind of fragmentation.  FAT also has a similar data structure, the directory entry.  Unlike NTFS and Unix inodes, the FAT directory entry contains the file name along with all the other file information.  Putting the file name with the rest of the file metadata has both positive and negative consequences, but I can't figure out how this difference would have any bearing whatsoever on disk fragmentation.

In fact FAT has a subtle (and not very important) advantage over NTFS and most Unix file systems with inodes.  In systems with inodes (or NTFS's master file table), the inodes are allocated in inode tables, and in some systems (like Linux's ext2) you had to choose the ratio of inode tables to data blocks.  This meant that if you had more small files than you expected you might run out of inode entries even though more data space was still available, and if you have larger files than expected you might run out of data space even though there is empty space allocated for unused inode tables.

Every filesystem has disk fragmentation.  Your perception of which actually suffer from real problems may not be completely accurate.  For example: NTFS has an interface specifically designed to make it easier to write user-level defragmentation utilities that can keep serving file requests while defragmentation is going on, while ext4 (the most commonly used file system on recent Linux systems) does not.  That doesn't necessarily mean that ext4 has less disk fragmentation than NTFS, it just means that if an ext4 file system gets fragmented there is nothing you can do about it.  Both ext4 and NTFS have a number of optimizations to reduce the probability of serious disk fragmentation problems.

You should think of a filesystem as a data structure with a set of algorithms for modifying the data structure.  As with any other data structure the designer needs to trade off a variety of different desirable and undesirable traits.

One of the decisions a filesystem implementation needs to make is block size.  With larger blocks larger chunks of data are guaranteed to be adjacent.  On the other hand, it is rarely the case that a filesystem allows a block to be used by more than a single file at a time (the FreeBSD UFS2 system (c. 2003) being an exception), so if you choose larger blocks but then have many small files those files are going to be spread further apart on the disk (this is so called internal fragmentation.)

Almost every modern file system (including NTFS, HFS+ (Mac), UFS2 (FreeBSD), ZFS (Solaris) and ext4 (Linux)) has a variety of heuristics included to help reduce the number of disk-head movements required during a complete file access.  These include allocating a file's data near its inode, locating the inode near the directory that contains it, and allocating adjacent blocks for data writes that are known to be longer than a block.  Journaling file systems try to combine together many small writes into larger chunks that can be written to adjacent blocks.

Some file systems implement delayed allocation, which permits them to decrement the free-space counter for the disk when the space is requested, but delay choosing which block to write the data to until the time at which the data needs to be flushed from data to memory.  This requires coordination between the file system and other parts of the operating system.  The wikipedia article does not list NTFS as performing this optimization (and FAT system almost certainly don't bother with anything that sophisticated.)

Another thing you should take into account is whether the file system is going to be used on a hard disk or on a solid-state drive (or flash drive).  Disk fragmentation does not matter for solid state drives (because there are no mechanical delays, so every block is equally fast to access).  On the other hand for solid-state/flash drives wear leveling matters a lot.


How to model equality in Integer Linear Programming How to implement v=(a==b) using Linear Programming?
$$
v=
\begin{cases}
True, a=b\\
False, a≠b\\
\end{cases}
$$

Until now I tried the big M-Method.

To show a≤b:
$$a-b+Mv≤M$$
$$-a+b-Mv≤-1$$

To show b≤a:
$$-a+b+Mv≤M$$
$$a-b-Mv≤-1$$

When they are equal everything is okay, but when a≠b it doesn't work.

Use Cast to boolean, for integer linear programming, setting $x=a-b$ and $y=v$.  This only works if you have a constant upper bound on $|a-b|$.  Otherwise, I don't know how to express it in an ILP.

See also Express boolean logic operations in zero-one integer linear programming (ILP), Boolean variable true iff equation is satisfied in ILP, Boolean variable that captures whether an inequality holds.


What is the set of all minimal 3CNF formulas? Definition: A minimal 3CNF formula is an unsatisfiable 3CNF formula with minimum clauses connected by conjunctions, where each clause is disjunction of 3 literals, that is if any of it's clauses is removed from the formula, then the 3CNF formula becomes satisfiable.

For some natural number n, where n is the number of atomic variables, what is the set of all minimal 3CNF formulas? Is it finite? If it is finite then what is it's cardinality, i.e. how many different minimal 3CNF formulas is possible?

In a minimal k-cnf formula, there should be 2k different
k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

That's what I think anyway, but correct me if I am wrong.

Note that for k-cnf formula n≥k, so in 3CNF formula n≥3.

The number of minimal formula is finite.  Indeed, if a formula is minimal, then no clause can be repeated.  Now there are $(2n)^3=8n^3$ possible clauses, so there are at most $2^{8n^3}$ different formulas with no repeated clauses.  Thus there are at most $2^{8n^3}$ minimal formula, which is finite.

I don't know of any clean way to count the number of minimal formula; probably there is no simple formula for it.  You could try computing the number for $n=1,2,3$ by brute-force, then looking up the resulting sequence in OEIS, but I don't expect you to find any simple expression for this number.

What you are thinking is wrong.  A minimal, unsatisfiable formula can have more than 8 clauses.


What fraction of all combinations is guaranteed to be deadlock free? I found this question in the exercise of Tanenbaum (operating systems):

  Two processes, $A$ and $B$,each need three records $1, 2, \text{ and } 3$ in a database. If $A$ asks for them in the
  order $(1, 2, 3)$ and $B$ asks for them in the same order, deadlock is not possible. However, if B asks for them in the order $(3, 2, 1)$ then deadlock is possible. With three resources, there are $3!=6$ possible
  combinations each process can request resources. What fraction of all combinations is guaranteed to be deadlock free?

I haven't gotten any farther than that there are $6$ possible ways that $B$ can request:
$(1,2,3), (1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$

Please help me out.

Let's assume for simplicity that A and B take 5 seconds to request for the next resource and B starts requesting for resources 1 second after A's request.

If A requests for 1 first and B requests for either 2/3 first, it will create a deadlock. This happens because when A requests for either 2/3 it will be blocked and B will be blocked when it requests for 1. So both processes will block each other and in turn will be blocked by each other.
If A and B both request for 1, then A wins out and B will be blocked. So there will be no deadlock.

So the entire problems rests on B's choices. Therefore $\frac{1}{3}$rd of the cases will be deadlock free.


Why is the following language undecidable? I'm currently learning for my exams this semester and tried to solve some old exams from the last years.
The question is to show, that L ist undecidable.
$L=\{w|T(M_w)\neq\emptyset \land \forall x \in T(M_w): xx\in T(M_w)\land xxx\notin T(M_w)\}$
I showed that the language $L'=\{w | T(M_w)\neq \emptyset\}$ is undecidable due to the Rice Theorem. I created to Turing Machines $M_1$ with $T(M_1)=\emptyset$ and $M_2$ with $T(M_2)=\Sigma^*$ to show that the language L' is not trivial. (since $1\in L$ and $2\notin A$. With out loss of generality i assume those machines have the Gödelindexes 1 and 2)
My problem now is, that I know no way to show, that this result transfers to the language L. I know that the language L must only contain such Gödel Indexes, that for those indexes the following TM must accept infinite words (because in case of $x\in T(M_w)$ there must be $xx\in T(M_w)$... and therefore must be $xxxx\in T(M_w)$ etc.)
I would love to hear suggestions / answers!
Thanks in advance

This is a direct consequence of Rice's theorem. A word $w$ is in $L$ if $T(M_w)$ satisfies the following semantic property:

$T(M_w)$ is non-empty, and for any $x \in T(M_w)$, we have $x^2 \in T(M_w)$ and $x^3 \notin T(M_w)$.

In order to show that this language is undecidable according to Rice's theorem, we need to exhibit two Turing machines $w_1$ and $w_2$: one which doesn't satisfy the property, and another one which does satisfy it. We can take $w_1$ to be some machine such that $T(M_{w_1}) = \emptyset$, and $w_2$ to be some machine such that $T(M_{w_2}) = \{ a^{2^n} : n \geq 0 \}$.


How do the non-∪ variants of NFAs work? I've only recently learned anything substantial about finite automata, and I've just come across some things I hadn't seen before. Specifically, that classic NFAs are ∪-NFA, and there are also these things ⊕-NFA , ∩-NFA and ⋆-NFA (I love unicode). These can all be seen in http://fastar.org/publications/PresentationFEW2006Geldenhuys.pdf or http://www.cs.sun.ac.za/~lvzijl/publications/fsmnlp2009.pdf

How are these different from the NFAs I'm familiar with?

Alright, I think I've figured it out. It can be seen in working with the transition function Δ : Q × Σ → P(Q), where Q is the set of states and Σ is the alphabet.

First, lets define some unary functions (P is powerset, of course):

∪ : P(S) -> S, ∪(X) = X1 ∪ X2 ∪ ... Xk where k = |X| (classic NFA)
∩ : P(S) -> S, ∩(X) = X1 ∩ X2 ∩ ... Xk where k = |X|
⊕ : P(S) -> S, ⊕(X) = X1 ⊕ X2 ⊕ ... Xk where k = |X| (symmetric difference NFA)

So basically, take a set of sets, and either and, or, or xor them all together.

Now, we extend the domain of our transition function to Δ : Q × Σ* → P(Q), where Σ* is a string of Σ, via the following recursive definition:

Δ(s, e) = s, where e is the empty string
Δ(s, xa) = ⋆({ s' ∈ Δ(s, x) | Δ(s', a) })

Where ⋆ can be any one of the three unary operators we defined above (and as specified in the second link in the original question, can be any associative and commutative operator on sets, converted into a combining unary function like above). The ⋆-NFA is the generalized NFA, so ⋆ is basically a wild card.

This is most intuitively understood in how an NFA is converted to a DFA by the subset construct. With a ∪-NFA, when you're creating your DFA states, you are taking the union of each result of the transition function from all the previous NFA states. With the other operators, its the intersection or symmetric difference of those states, respectively. If you take another look at that first link that I put in the original question, with this information in mind, it makes a pretty good example that should be relatively easy to understand. It seems this was the original intent of the slides, but without accompanying lecture it was a bit difficult to follow. I guess that about covers it.


Cards shuffling. Greedy algorithm We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck.

My idea is to create a priority queue. At top of the queue we have a minimum value of a(i). And then shuffle Q.top() with the next Q.top() while Q.size() > 1.

Could you help my proving, if it works, or not?

Just like Wojciech said, there is a bijection between calculating Huffman Code and your problem. As you can see, we can treat your problem as:

  Find binary rooted tree with $n$ weighted (weights $a_1,...,a_n$) leafs, such that sum of
  distances from leafs to root multiplied by their weight would be
  minimal.

This problem can be solved by calculating Huffman Code. Now let's see why we can use that algorithm to solve our problem. We will treat each deck as a leaf and each shuffling as an inner verticle. If all inner vertices have exactly 2 kids then such tree is a result of some shuffling procedures. We can easily prove that every Huffman Code Tree don't have inner verticles with only one child (because we could reduce that tree otherwise).

For further reading:

In this lecture note you can read prove that you can use your algorithm to build Huffman Code.


What is branch factor for beam search in RNNs like TensorFlow's Magenta? TensorFlow's Magenta melody generation module has a parameter for branch_factor1. What is it?

Branch factor in beam search refers to average number of branches at each level of a search tree. When predicting a sequence in an LSTM model, such as note selection in melody generation, $b$ branches will be decoded. Increasing the branch factor from 1 to 4 in the call to melody_rnn_generate will maintain the average number of branches to be at $b$.

Specifically for Magenta, it generates 4 branches for each event sequence. It will increase the accuracy of the prediction at the expense of time, and in melody creation at the risk of getting stuck in a local optimum. For example, increasing the branch factor from 1 to 2 decreased the average negative log-likelihood of a melody generation implementation from 36 to 8, but also made the sequence prediction more dependent on the primer sequence (repeating the primer note).


Karp hardness of a diameter-decreasing planted clique A diameter-decreasing planted clique in an undirected graph $G(V,E)$ is a set of vertices $\mathcal{C}\subseteq V$ such that if we add all the missing edges between any pair of vertices in $\mathcal{C}$ to turn it into a clique, then the diameter of the obtained graph $G'$ is at most $2$.

Diameter-decreasing Planted Clique Problem:

  Input: An undirected graph $G(V,E)$ and a natural number $k$

  Output: YES if there exists a diameter-decreasing planted clique
  of size $k$ in $G$, otherwise NO

What is the complexity of this problem?

This problem is $NP$-complete. Reduce from Exact Cover by $3$-Sets (X3C).

Given an X3C instance, its ground set is $\mathcal{U}=\{e_1,e_2,\cdots,e_n\}$. Its collecion of $3$-subsets is $\mathcal{C}=\{s_1,s_2,\cdots,s_m\}$.

  For each element in the ground set and each subset in the collection,
  we create a new vertex (which will be referred to by the same name,
  henceforth).

  For each pair of element $e_i$ and subset $s_j$ such that $e_i\in s_j$, connect the two
  vertices.

  For $s_j$'s vertices:
  Connect all pair of $s_j$'s vertices to make these a clique.

  Then, create a new vertex $s$ and connect it to all $s_j$'s vertices.

  For $e_i$'s vertices: For each pair of elements $e_{i_1}, e_{i_2}$ that share no
  common subset, we create a new vertex $e_{i_1i_2}$ and connect it to both of
  $e_{i_1}$ and $e_{i_2}$.

  Then, create a new vertex $e$ and connect it to all $e_{i_ai_b}$'s vertices.

  Connect $s$ and $e$ by an edge. Create a new vertex $t$ and connect it
  to both of $s$ and $e$.

  Call the newly constructed graph $G$. Set $k=\frac n3+1$.

Clearly, we only need to decrease the distance from $t$ to each of $e_i$'s vertex.

If in the planted clique, we do not choose $t$, then for each $e_i$, we need to connect it to either $s$ or $e$. Because $s$ and $e$ are all the neighbors of $t$. That is going to exceed the bound of $\frac n3+1$ on the cardinality of the clique.

So, $t$ must be included in the planted clique. Denote by $x$, $y$ and $z$ (in this order) the number of vertices included in the planted clique among the $s_j$'s vertices, $e_i$'s vertices and $e_{i_ai_b}$'s vertices (resp.)

We can see that each one in $x$ vertices of $s_j$'s vertices will decrease the distance from $t$ to $3$ $e_i$'s vertices.

Similarly, each one in $y$ vertices of $e_i$'s vertices will decrease the distance from $t$ to $1$ $e_i$'s vertices.

And, each one in $z$ vertices of $e_{i_ai_b}$'s vertices will decrease the distance from $t$ to $2$ $e_i$'s vertices.

So, we must have $3x+y+2z\geq n$. But also, $x+y+z=\frac n3$.

We deduce that $x=\frac n3$ and $y=z=0$


How to prove NP-completeness of this variant of the set cover problem? The problem exactly:

Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least two counselors who are skilled at this sport. They have received job applications from m potential counselors. For each of the n sports, there is some subset of m applicants qualified in that sport. The question is: For a given k < m, is it possible to hire at most k of the counselors and have have at least two qualified in each of the n sports?

So, you are given a set U of elements, a collection of S1, S2...SM subsets of U, and an integer k. The original vertex-cover problem asks if there exists a collection of <= k of these sets whose union is equal to U. This question seems to ask how would we prove this is NP-Complete if we instead had to find a collection of <=k of these sets whose union covered the elements in U at least twice.

My first thought was to try to reduce the set cover problem. I was going to try to extend it to make it have to cover the union twice, but have no idea how to do that.

My next thought was to use 3-SAT since everything comes from that it seems, but I will die of old age before I figure that out.

My question is, what problem should I try to reduce from? Any could I get a hint for a first step to take? I've never proved one of these before so I'm really lost. I've been staring at this problem for 3 hours now.

Your first guess is correct. You misinterpreted however the meaning of reductions. When we prove the hardness of a problem $A$ by a reduction from $B$, we aim to reduce $B$ to $A$ and hence, given an instance $I$ of $B$, we want to build an instance $I'$ of $A$ such that $I$ is a yes-instance if and only if $I'$ is.

Now by reducing set cover to your problem, given an instance $(U, \mathcal{F}, k)$ of set cover, where $U$ is the universe, $\mathcal{F} := \{F_1, \dots, F_m\}$ the collection of sets and $k$ the maximum number of sets in the answer. We build the instance $(U, \mathcal{F}', k')$ as follows. If $k$ equals 0, then we output No. Otherwise, if $U \in \mathcal{F}$, we output yes. Else, Let $\mathcal{F}' := \mathcal{F} \cup \{U\}$, which means we add a new set  to the collection, namely the set consisting of the whole universe. We also set $k' = k + 1$. We claim the original insatnce has a solution of size $k$ for the set cover problem if and only if the new instance has a solution of size $k+1$ of your problem.

For the first direction,  given a solution of size $k$ for thr set cover problem, add the new universal set to the solution to build a solution for your problem of size $k+1$. (Why does this work?)

Now the harder direction, given a solution for the built instance of your problem of size at most $k+1$, if the universal set is a part of thr solution, the  we can remove it to get a solution for the original insatnce of set cover with size at most $k$. If the universal set is not present, then remove any set from the solution (since you can switch this set with the universal set getting back to the previous case).

By this far we proved the hardness of the problem. For the completeness proof, note that given a solution of size $k+1$, we can count for each element in the universe how many times it was covered in the solution in polynomial time. Hence we can proof a positive witness in polynomial time and the problem is NP-complete.


What is the correct definition of coNP/poly? Complexity Zoo defines coNP/poly as
Complement of NP/poly
Thanks to Emil, I understand it as
"the class of decision problems whose complement can be solved in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function."
(A polynomial-bounded advice function is a function $f$ that maps each positive integer $n$ to an advice string $f(n)$ of length polynomial in $n$. To be clear, the advice string depends only on $n$; it is independent of the input to the Turing machine.)
I don't clearly understand this definition. A decision problem is basically a yes/no question, and I suppose "solving a decision problem" means answering the yes/no question correctly. But, if that is the case, then solving a decision problem is same as solving the complement of the problem. So, I wonder
What is the meaning of the word 'solve' in the definition of coNP/poly (or NP/poly)?
I am also interested in whether we can define coNP/poly (or NP/poly) in terms of deterministic polynomial time verifiers (as in the definition of NP). The best I could come up with are the following.
NP/poly is the class of decision problems whose yes certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.
coNP/poly is the class of decision problems whose no certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.
Are these definitions correct?
Disclaimer: I have asked a related question in cstheory.stackexchange. At the time of asking that question, I did not know that the problem is in my understanding of the definition. They recommended that I ask the question here. (I shall delete my other question if the only problem is my understanding of the definition).
Thank you

Recall that a decision problem is a language $L \subseteq \{0,1\}^*$.  (This is the language of all words $w$ such that the answer to the yes/no question is "yes".)
In this context, a Turing machine solves a decision problem $L$ if $L$ is the language accepted by that Turing machine.  In other words, when run on input $w$, the Turing machine halts and accepts if $w \in L$, and halts and rejects if $w \notin L$.


Is it possible to use "and", "or" "not" as relation/predicate in an ontology? In order to represent causality? If we use an ontology we can represent knowledge, using notably semantic triple <s,p,o>.

I was wondering how can I represent this:

A and B cause C

or

A or B cause C

?

I don't want to do reasoning, I only want to represent.

Is it possible to use and, or, negation as predicate/relation in an ontology?

I only see that researchers use causal networks to represent causality, but I was wondering why it is not possible in an ontology.

Thanks in advance,

The ontologies that are used today are mostly based on Description Logics (DLs). The basic building blocks of DLs consists of concepts and relationships between concepts where a concept represents a set of individuals (elements) and a relationship states that an individual of one set is related to an individual of another set.

A good book in this regards is An Introduction to Description Logics. There are different DLs with different expressivities and indeed many DLs exist that allow for negation and relations. A freely available tool for creating ontologies is Protege.

The <s,p,o> you refer to is related to RDF data and RDFS which do not support negation. Roughly RDFS (similar to relational DB schemas) can be seen as defining the schema and RDF as defining the data (similar to the data of a relational database).

How to design what you require depends on the inferences you want to make from your ontology. Since you don't want to reason over the ontology, you can really model this however you want. Though I am wondering whether using an ontology is the most appropriate if you do not intent do any reasoning.

Option 1: Using concepts

Class: D
  EquivalentTo: A or B
  SubClassOf: C

This will result in any individual belonging to A or B to be inferred to belong to C as well. Concept D is introduced to provide a name for the concept A or B.

Option 2: Using Relations

Class: D
  EquivalentTo: A or B

ObjectProperty causes:
  Domain: D
  Range: C

This will result in the inference that whenever two individuals a and b are related via causes (written as causes(a, b)), it will infer that a belongs to D and b belongs to C.

On my blog I have a few posts that give some explanations wrt ontologies as well as some examples.


Reducing infinite paths of a transition system to its set of sets of states Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is at least one outgoing transitions $(s,s') \in T$.
Each path corresponds to a set of states, namely, the states visited along that path.  Given a transition system $\langle S,T \rangle$ and an initial state $s_0 \in S$, I would like an algorithm that outputs the list of all sets of states that can arise from all infinite paths in $\langle S,T \rangle$ that start at $s_0$.
As a trivial example consider $S = \{s_0, s_1, s_2 \}$, $T = \{(s_0,s_1),(s_0,s_2),(s_1,s_1),(s_2,s_2)\}$, with initial state $s_0$; I would like the algorithm to output $\{s_0,s_1\}, \{s_0,s_2\}$.
Is there an algorithm for this problem?
I believe this can be accomplished with strongly connected components, but I don't know what to search for in the literature.

Since the set you want to output can be exponential in the size of the transition system, there is clearly no polynomial algorithm to enumerate it.
Thus, let's focus on an exponential time solution. To this end, it is actually quite easy to find a naive algorithm:
For every subset $Q\subseteq S$ (that contains $s_0$), in order to check whether $Q$ should be outputted by the algorithm, look at the subgraph induced by $Q$, and check whether there is a path from $s_0$ that goes through all the vertices in the induced subgraph.
One way to do the latter, is to indeed decompose the subgraph to its strongly connected components (SCCs), then look at the tree of SCCs, and make sure it's simply a directed path from $s_0$. If it is not a path, then you cannot traverse the entire set $Q$, as you would need to select a branching in the tree from which you cannot go back.
Thus, the test of whether $Q$ should be outputted can be done in polynomial time.


Reducing Exact Cover to Subset Sum in practise! The reduction of Exact Cover to Subset Sum has previously been discussed at this forum. What I'm interested in is the practicality of this reduction, which I will discuss in section 2 of this post. For you who are not familiar with these problems I will define them and show the reduction Exact Cover $\leq_p$ Subset Sum in section 1. For the readers who are already familiar with these problems and the reduction can move ahead to section 2.

section 1

The Exact Cover defined as follows:

Given a family $\{S_j\}$ of subsets of a set $\{u_i, i=1,2,\ldots,t\}$ (often called the Universe), find a subfamily $\{T_h\}\subseteq\{S_j\}$ such that the sets $T_h$ are disjoint and $\cup T_h=\cup S_j=\{u_i, i=1,2,\ldots,t\}$.

The Subset Sum is defined as follows:

Given a set of positive integers $A=\{a_1,a_2,\ldots,a_r\}$ and another positive integer $b$ find a subset $A'\subseteq A$ such that $\sum_{i\in A'}a_i=b$.

For the reduction Exact Cover $\leq_p$ Subset Sum I have followed the one given by Karp R.M. (1972) Reducibility among Combinatorial Problems

Let $d=|\{S_j\}|+1$, and let
$$
\epsilon_{ji}=\begin{cases}1 & \text{if} & u_i\in S_j, \\ 0 & \text{if} & u_i \notin S_j,\end{cases}
$$
then
$$
a_j=\sum_{i=1}^{t}\epsilon_{ji}d^{i-1}, \tag{1}
$$
and
$$
b = \frac{d^t-1}{d-1}. \tag{2}
$$

section 2

In practise (meaning for real world problems) the size of the Universe for the Exact Cover problem can be very large, e.g. $t=100$. This would mean that if you would reduce the Exact Cover problem to the Subsets sum problem the numbers $a_j$ contained in the set $A$ for the Subset Sum could be extremely large, and gap between the $\min\{A\}$ and $\max\{A\}$ can therefore be huge.

For example, say $t=100$ and $d=10$, then its possible to have an $a_j\propto 10^{100}$ and another $a_i\propto 10$. Implementing this on a computer can be very difficult since adding large numbers with small numbers basically ignores the small number, $10^{16} + 1 - 10^{16} = 0$. You can probably see why this could be a problem.

  Is it therefore possible to reduce the Exact Cover to Subset Sum in a more practical way, that avoids the large numbers, and have that the integers in $A$ are of a more reasonable size?

I know that it is possible to multiply both $A$ and $b$ by an arbitrary factor $c$ to rescale the problem, but the fact still remains that gap between possible smallest and largest integer in $A$ is astronomical.

Thanks in advance!

The short answer is no :-)

Why? ... Because SUBSET SUM is weakly NP-complete; you cannot avoid the exponential blowup of the numerical value of the arguments with respect to the input size of the original problem
(in other words the length of the binary representation of the $a_j$  is kept polynomial by the reduction but the values obviously are exponential)

If this was not the case you could use Dynamic Programming to solve an NP-complete problem in polynomial time.


Property of two ANEAs is in NP I have two arbitrary acyclic nondeterministic finite automata $\mathcal{A_1}$ and $\mathcal{A_2}$ and want to show that the problem $L(\mathcal{A_1}) \not \subseteq L(\mathcal{A_2})$ is in NP by specifying a polynomial proof system.

We defined a polynomial proof system in the following way:

For $L \subseteq \Sigma^*$ the relation $R \subseteq \Sigma^* \times \Gamma^*$ is a proof system for $L$ if $(w,b) \in R \Rightarrow w \in L$ and $w \in L \Rightarrow \exists b \in \Gamma^*: (w,b) \in R$. $R$ is polynomial if there is a polynomial $p$ with $|b| \le p(|w|)$ for all $(w,b) \in R$ and $R \in P$.

Unfortunately I have no idea how to get the relation and any help would be appreciated.

Hint: Suppose that $\mathcal{A}_1$ has $n$ states. Since it is acyclic, all the words it accepts have length at most $n-1$ (why?). Therefore if $L(\mathcal{A}_1) \nsubseteq L(\mathcal{A}_2)$ there must exist a word $w$ of length at most $n-1$ that $\mathcal{A}_1$ accepts but $\mathcal{A}_2$ rejects.


Abstract Syntax Tree of Pure Lambda Calculus I was wondering if anyone had any good references or book recommendations that cover abstract syntax trees (ASTs). Specifically, I am interested in the abstract syntax trees of different evaluation strategies (call by value vs. call by name) of the pure lambda calculus. I would like to be able to draw the AST of some pure lambda calculus expression such as
$$and \, true \, false = (\lambda a. \lambda b. a \, b \, (\lambda t. \lambda f. f))(\lambda t. \lambda f. t)(\lambda t. \lambda f. f).$$

I would like to know if/how evaluation strategies affect the structure of ASTs, or how order of operation is reflected in the AST of an expression. This seems trivial for any pure lambda calculus interpreter; so perhaps there is some AST generator out there somewhere? I did some searching on Google but found nothing.

I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.

I would like to know if/how evaluation strategies affect the structure of ASTs, how order of operation is reflected in the AST of an expression

They don't, and it isn't. Evaluation strategies are functions which take ASTs as arguments, and return ASTs (or possibly only normal forms), so you can have different evaluation strategies working on the same AST.

  I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.

See e.g. this Stack Overflow question:

data Exp = Var String
             | App Exp Exp
             | Lam String Exp

In the case of pure lambda-calculus, there is no Constant Int, and and would look like

Lam "a"
  (Lam "b"
     (App
        (App
           (Var "a")
           (Var "b"))
        (Lam "t"
           (Lam "f"
              (Var "f")))))


How does virtual memory work when it need to save data in physical memory into disk? I'm reading a textbook which desribe VM as:

a data structure stored in physical memory known as a page table that maps virtual pages to physical pages. The address translation hardware reads the page table
each time it converts a virtual address to a physical address. The operating system
is responsible for maintaining the contents of the page table and transferring pages
back and forth between disk and DRAM.

A page table is an array of page table entries (PTEs). M. If the valid bit is set, the address field indicates the start of the corresponding physical page in DRAM where the virtual page is cached. If the valid bit is not set, then a null address indicates that the virtual page has not yet been allocated. Otherwise, the address points to the start of the virtual page on disk.
So my question is, let's the PP0(VP1) has been modified and need to be written back to disk to make the change permanent. But the the PTE1 only has address(PP0) pointed to main memory, it has lost disk address VP1, so how can the changes be made to disk in this scenario?

There are a few options:

if a page is in memory then it cannot be on disk as well, As such there is no duplication and the issue doesn't exist.

there is more than just the MMU's pagetable to hold paging information. This mean that the kernel has an auxiliary data structure that says where the page is on disk and the MMU page table only tracks what is in memory. This solution allows memory mapping of files whether they are on disk or over the network.


Inferring Social Ties In some papers, they proposed a model in which the joint posterior probability was modeled as[1]:
$$ P(Y|\textbf{X},G) = \frac{P(\textbf{X},G|Y)P(Y)}{P(X,G)} \propto P(\textbf{X}|Y) \cdot P(Y|G)$$
where $\textbf{X}$ is attribute vectors set and $Y$ is the labels of all the edges in the network.

I know the meaning of the first equal sign which can be applied with Bayesian Theorem. But I feel confused about the third term, $P(\textbf{X}|Y) \cdot P(Y|G)$. How this term comes out?

[1]: J. Tang, T. Lou, and J. Kleinberg, “Inferring social ties across heterogenous networks,” in Proceedings of the fifth ACM international conference on Web search and data mining - WSDM ’12, 2012, p. 743.

This model seems a little confusing due to the role of $G$ and I didn't find their definition of $P(Y|G)$ very sound.

You can consider it the following way:

$$P(Y|\textbf{X},G) \propto P(\textbf{X}|Y) \cdot P(G|Y) \cdot P(Y) = P(\textbf{X}|Y) \cdot [P(G|Y) \cdot P(Y)] \propto P(\textbf{X}|Y) \cdot P(Y|G)$$


What is the complexity of a bracketed search using mediants? I'm trying to estimate the complexity of an algorithm I've written for the Reko decompiler, where I'm trying to "undo" the tranformation done by a compiler to an integer division by a constant $x / n$. The compiler has converted the division into an integer multiplication and a shift: $(x * \lfloor 2^\beta / n \rfloor) >> \beta$, where $\beta$ is the number of bits of the computer's machine word. The resulting constant multiplication is a lot faster than a division in most contemporary architectures, but no longer resembles the original code.

To illustrate: the C statement

y = x / 10;

will be compiled by the Microsoft Visual C++ compiler to  following assembly language

mov edx,1999999Ah  ; load 1/10 * 2^32
imul eax           ; edx:eax = dividend / 10 * 2 ^32
mov eax,edx        ; eax = dividend / 10

The net result is that the register eax will now have the expected value of y from the source code.

A naive decompiler will decompile the above to

eax = ((long)eax * 0x1999999A) >> 32;

but Reko aims to make the resulting output more legible than that by recovering the constant that was used in the original division.

The algorithm hinted at above is based on the description on this article in Wikipedia. First, the algorithm treats the constant multiplier as the scaled reciprocal $2^\beta / n$. It converts that to a floating point number $2^\beta r_f$ and then scales it down by $2^\beta$ to $r_f$, where $0.0 < r_f <1.0$. The final, expensive step is to bracket the floating point value $r_f$ between two rational numbers $a/b$, $c/d$ (starting with 0/1 and 1/1) and repeatedly compute the mediant $(a + c)/(b + d)$ until some convergence criterion is reached. The result should be the "best" rational approximation $r$ to the reciprocal $r_f$.

Now, if the bracketing was being done with a typical binary search starting between the rationals $0/2^\beta$ and $2^\beta/2^\beta$, and computing the midpoint $(a/b + c/d)/2$, I expect the algorithm to converge in $O(\beta)$ steps. But what is the complexity of the algorithm if the mediant is used instead?

The relation between the Stern–Brocot tree and Farey sequences shows that if $0 < p/q < 1$ and $(p,q) = 1$ (i.e., $p/q$ is a reduced fraction) then $p/q$ is at the $q$th level of the tree. Since the running term of your algorithm is linear at the level in which you terminate, your algorithm takes time $O(q)$, where $p/q$ is the answer; but this is not so helpful.

You haven't specified what your stopping criterion is, but presumably you have some error threshold $\epsilon$. The question therefore is for which Farey sequence is it the case that adjacent terms are at distance at most $2\epsilon$ (and so every point is at distance $\epsilon$ from some point). Using the fact that the distance between adjacent fractions $p_1/q_1,p_2/q_2$ in a Farey sequence is $1/(q_1q_2)$, it is not hard to show that the maximal distance at the $q$th Farey sequence is $1/q$. Therefore if you are aiming at a distance of $\epsilon$, then your algorithm will run in time $O(1/\epsilon)$ in the worst case.

However, "most" adjacent fractions at the $q$th Farey sequence are at distance $O(1/q^2)$, and so on average you would probably expect a running time of $O(\sqrt{1/\epsilon})$ (unfortunately, this average is with respect to the input rather than the algorithm).


What is the connection between the logic and the logic programming? As I understand, then logic (i.e. particular theory of logic with some theory's axioms and some possible assignments of the variables) describes some specific world (in the non-modal case) or some set of related worlds (in the modal case) and deduction just explores this one world (this set of related worlds) and discovers/constrains the possible values of the variables (SAT problem).

But logic programming with its quite confusing implication relation (I still don't understand how the implication of the logic programming is related to the implication connective in the logic - those seem to be two completely different notions and different signs - am I right?) allows traveling among worlds (in modal case - among sets of related worlds): if variables {x} has some values in the one worlds, then those variables {x} has some different values in the other world. And it is the (one) semantics of the logic programming, that set of clauses that allow such traveling among worlds, at the end lands the traveller in one world that is fix-point for this set of clauses (of logic programming statements).

Computation is state transition: from one state to the other, from one world-state/world to the other world-state/world. But logical inference is just exploration of one world - be it discovery of the new relations among variables or statements (discovery of theorems) of be it discovery of the consistent set of assignments to the variables (discovery of the solution to SAT problem).

Am I right? What else can be added to this understanding between logic and logic programming?

Maybe there is some logic which allows to deduce the logic programs? To do the reasoning about the logic programs?

First, all this "worlds" stuff is unnecessary. It's a notion used in some semantics of modal logic. You don't need it to understand modal logic, let alone non-modal logics. This isn't to say it can't be useful, it's just that "worlds" is not some fundamental constituent of logic or their semantics, and, regardless, is not typically used outside of modal logics. As common logic programming languages (i.e. Prolog) are not based on modal logic, there's not much reason to bring it up nor concepts sometimes used in its semantics. You can have modalities in a logic programming language, e.g. LolliMon does. The notion of worlds doesn't really map well onto variable assignments. The problem, among other things, is that you can want multiple different assignments to the same variable at the same time.

Sticking to (pure1) Prolog, due to the restrictions on where you can place connectives, it turns out that it can be understood as operating in a logic with no connectives. Let's consider a fairly general example of a Prolog rule:

p(X,Y) :- q(X,Z), r(W); t(Y).

This corresponds to the logical formula: $$\forall X,Y.(t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\to p(X,Y)$$

First, we can eliminate the universal quantifiers and simplify things by considering entailments between open terms where the free variables will behave like constants. This more or less corresponds to $\forall$ introduction. So $\vdash \forall x.\varphi(x)$ becomes just $\vdash\varphi(x)$. Our example becomes:
$$\vdash (t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\to p(X,Y)$$
We can use the $\to$ introduction (aka the deduction theorem) to eliminate the sole occurrence of $\to$ in any particular rule producing for our example:
$$(t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\vdash p(X,Y)$$
We can use the $\lor$ left rule of the sequent calculus LK/LJ to handle the disjunction. Alternatively we could have used the equivalence $(P\lor Q)\to R\equiv (P\to R)\land(Q\to R)$ before eliminating $\to$ and then used $\land$ introduction, then eliminate $\to$ to produce the same result. We could also eliminate disjunctions (';') via a standard source-to-source transformation of the Prolog that is based on these rules. Our example becomes a pair of entailments:
$$t(Y)\vdash p(X,Y)\qquad \exists Z.q(X,Z)\land r(W)\vdash p(X,Y)$$
We can eliminate the existential with a $\exists$ left rule a la LK/LJ which is basically the dual of $\forall$ introduction and works the same way. That is, we just drop the existentials and the bound variables become free and are treated as constants. Alternatively, this could be understood in terms of the equivalence $(\exists x.\varphi(x))\to\psi\equiv\forall x.\varphi(x)\to\psi$. The relevant entailment of our example becomes:
$$q(X,Z)\land r(W)\vdash p(X,Y)$$
Finally, we can use the $\land$ left rule to eliminate conjunctions, producing:
$$q(X,Z),r(W)\vdash p(X,Y)$$
For an arbitrary (pure) Prolog program, the end result is that we have a collection of rules with a list of premises which consist of atomic formulas entailing a single atomic formula. All connectives can be eliminated. If you don't like this, you can easily go from here to the program corresponding to a series of axioms of the form $\forall\vec{X}.(p_1(\vec{X})\land\cdots\land p_n(\vec{X}))\to q(\vec{X})$, which are Horn clauses, or curry this to get rid of $\land$ producing $\forall\vec{X}.p_1(\vec{X})\to(\cdots(p_n(\vec{X})\to q(\vec{X})\cdots)$. This would mean you only need to understand universal quantification and implication, but even then neither ever occurs in a negative position, so you don't need their full generality which is part of why they can be eliminated. If you want to inject classical logic unnecessarily, you can use material implication and write $\forall\vec{X}.\neg p_1(\vec{X})\lor\cdots\lor\neg p_n(\vec X)\lor q(\vec X)$, and, instead of Cut below, we'd talk about Resolution.

Sticking to the connective-free version, how do we actually prove things? Well, we still have the structural rules. In particular, we have Cut which states (for our purposes):
$$\dfrac{\Gamma\vdash P\qquad\Delta,P\vdash Q}{\Gamma,\Delta\vdash Q}$$
where $P$ and $Q$ are atomic formulas and $\Gamma$ and $\Delta$ are lists of atomic formulas. Cut corresponds to calling a subgoal.

For the top-level call that kicks off the execution of a Prolog program, we aren't trying to show whether the universal closure of the top-level goal is true, but rather listing all the bindings to free variables that makes the goal derivable. This can be seen as enumerating the derivations of $\vdash\exists\vec X.q(\vec X)$ if $q(\vec X)$ is the top-level goal.

For the connection to execution, I recommend getting familiar with the concept of an abstract logic programming language as defined in Uniform Proofs as a Foundation for Logic Programming. This shows how we can interpret connectives as instructions to proof search. By constraining the logic, we can make it so this operational interpretation of the connectives (and atomic formulas), can give a complete proof search procedure (for our highly restricted logic). The elimination of connectives that I've done shows that for Prolog (but not $\lambda$Prolog), the only operational interpretation we need is that of atomic formulas. Non-determinism arises from choosing which rule to use to derive the atomic formula and how to instantiate its free variables. Implementation-wise, the former is usually handled by backtracking and the latter by unification.

If you recorded the steps of the execution of a (pure) Prolog program, the result would be a derivation, i.e. a formal proof. There is no "satisfaction" involved. A Prolog program like p :- q, r does not try assigning different truth values to q and r. There's no way to express a contradiction in (pure) Prolog, so every (pure) Prolog program corresponds to a satisfiable formula.

Datalog is usually analyzed with a more semantic approach, but it has additional restrictions over (pure) Prolog to make this well behaved. Datalog is often implemented in a bottom-up manner where we generate a series of single-step deductions and grow the set of derived facts until we reach a fixed point. Prolog, however, is almost always implemented in a top-down manner where we backchain so that we only derive the facts that are relevant for our goal.

1 This excludes this like assert/retract, cut (!), and the negation-as-failure thing.


How to choose the right input(s) to test my algorithm? Suppose i want to trace an algorithm (think of it as a flowchart) to understand how it works, i need an input(s) for this algorithm, the question is: how can i determine the right input(s) that goes through all the cases ? Is there any "scientific" method to determine this input?

If you want to automatically explore the state space of a program, you could try a fuzzer like AFL. But usually programmers do this by running the program under a debugger and thinking a bit about how the input needs to look to take a particular path through the code.


Pick a random number in a pool with duplicates in O(1) time and less than O(n) space? Imagine trying to pick a random number from a pool of numbers that contains:

i1 times the number 1
i2 times the number 2
i3 times the number 3
... etc

For example picking a random number in a pool of
30 times the number 1
90 times the number 2
would yield 1 with 25% probability and 2 with 75% probability.

let NU be the number of unique numbers
let NT be the total number of numbers
In our example NU=2, NT=120.

Is there a way to achieve this in O(1) time and less than O(NT) space?

Edit: corrected probabilities in example.

Why is $1$ returned with probability $33\% < \frac{1}{3}$ and not with probability $\frac{30}{30+90} = \frac{1}{4}$?

Anyway, this can be done in $O(NU)$ space (assuming $i_1, \dots, i_{NU}$ each fit in $O(1)$ memory words) and $O(1)$ time (assuming you can sample an integer between $1$ and $\sum_{j=1}^{NU} i_j$ uniformly at random in $O(1)$ time) using the alias method.

The Wikipedia page includes a pseudocode that uses rational numbers (which might lead to a loss of precision, depending on their representation). If you are interested in a C++ implementation that uses integers, like in your description, see here.


How to prove that a polynomial of degree n is θ(x^n) How can I prove that if $T(x)$ is a polynomial of degree $n$ then $T(x) = \Theta(x^n)$.

Say $T(x) = a_n x^n + \dotsm + a_0$, then by the triangle inequality for $x \ge 1$:

$\begin{align}
   \lvert T(x) \rvert
     &\le \lvert a_n \rvert x^n + \lvert a_{n - 1} \rvert x^{n - 1}
            + \dotsm + \lvert a_0 \rvert \\
     &\le \lvert a_n \rvert x^n + \lvert a_{n - 1} \rvert x^n
            + \dotsm + \lvert a_0 \rvert x^n \\
     &= (\lvert a_n \rvert + \lvert a_{n - 1} \rvert + \dotsm + \lvert a_0 \rvert)
           x^n
\end{align}$

I'm sure you can take it from here. You'll have to figure out an appropriate lower bound to match.


Why do floating point additions sometimes produce equal results? I have tried two sentences on my computer :

2 + 10^(-18) == 2
2^(-55) + 2^(-57) == 2^(-55)

My computer gives TRUE and FALSE respectively. Why does the computer give two different results? Shouldn't the computer give the same output?

Floating point numbers have limited accuracy. They are stored in the following way: $\pm 1.x_0\ldots x_{n-1} \times 2^y$ (here $x_0,\ldots,x_{n-1}$ are binary digits) for an appropriate $n$; the value of the exponent $y$ is also bounded. The value of $n$ and the bounds on $y$ depend on the exact type of the floating point number.

When you add $2$ and $10^{-18}$, the answer is rounded to $2$ since the contribution of $10^{-18}$ is too small to store in the number (i.e., $n$ is too small). When you add $2^{-55}$ and $2^{-57}$ there is no such problem: this is stored as $1.01 \times 2^{-55}$.

For more, check out one of the multitudinous resources on floating point numbers.


How can I mathematically show the largest possible value of a 64-bit double? I'm a physics student wondering how I can mathematically show the largest possible value of a 64-bit double. I don't want to know just the answer, since that is freely available. The equation I was shown by a professor says a machine number is represented as $s\times m \times 2^{E-e}$ with $m$ the mantissa and $e$ the bias of the exponent, but I'm not sure how to use this to show the largest possible 64-bit double. The mantissa is 52 bits long and the largest exponent is 2047. The bias is 1023. The largest exponent is reserved for infinity. The leading 1 is not stored.

Assuming IEEE754 64 bit format:
You have an 11 bit exponent field, a 1 bit sign field, and a 52 bit mantissa field.
The exponent field can have values from 0 to 2047. An exponent field of 0 is reserved for denormalized numbers, and an exponent field of 2047 is reserved for infinity and Not-a-number. You could say that +Infinity is the largest value, but I assume you are looking for the largest finite value. The largest exponent field for a finite value is 2046.
This format has an "exponent bias" of 1023, that is the numbers 1.0 ≤ x < 2.0 have an exponent field of 1023. So the largest value has an unbiased exponent of 2046 - 1023 = 1023, and numbers with an exponent field of 2046 are in the range $2^{1023} ≤ x < 2 \cdot 2^{1023}$.
The mantissa field is 52 bit, with an implicit leading 1 bit. So a mantissa field with a value m, 0 ≤ m ≤ $2^{52}$, means the actual mantissa is 1 + $m \cdot 2^{-52}$. The largest possible mantissa field is all bits 1 or $2^{52}-1$, this makes the largest possible mantissa $2-2^{-52}$.
Multiply with the exponent, and the largest possible number is $2^{1023} \cdot (2-2^{-52})$ or $2^{1024} \cdot (1-2^{-53})$ or $2^{1024} - 2^{971}$


Motion Prediction Problem Setup: Suppose you have a dog running around in a fenced yard (2D). Every x seconds, you mark down the coordinates of the dog. This dog is a puppy - easily distracted, full of energy, and very speedy :) Expect quick, jagged motions, running in circles, and periods where he needs to catch his breath :)

Problem: At any point, you would like to predict where the dog is going to be kx seconds into the future (k being an integer).

I would like to know what types of techniques may be most suitable for solving this? My knowledge breadth in this subject matter is very limited. I'd like to identify a few candidates that I could then deep-dive into

My original thought was to use Langrange-form polynomials to interpolate the latest n points, then extrapolate. The dog's path is continuous, and smooth, so a polynomial approximation seems reasonable; however, the danger lies in forcing the polynomial through the available data. It seems like we want the polynomial that best approximates the data, rather then the lowest degree polynomial that exactly fits the available data - especially if x is substantial.
Ideally, since every prediction can be measured against what actually occurred, there  should be some method of learning on-the-fly. However, since the data isn't static, I don't know how I would apply techniques of somewhat aware of like SVMs or linear regression.

I apologize if I didn't use terms correctly, this is not my area of expertise.

I would try to train a Recurrent Neural Network for this problem, the LSTM architecture is particularly interesting for time series prediction.

Sources:

karpathy.github.io/2015/05/21/rnn-effectiveness/
colah.github.io/posts/2015-08-Understanding-LSTMs/

You would of course need a training dataset consisting of a sequence of events. Let's say $x$ and $y$ coordinates for every timestamp $t$, (possibly $z$ as well to predict a jumping puppy).

Both the network input layer and the output layer would consist of 2 units.
Then you would train your model to predict $(x_{t+1}, y_{t+1})$ given $(x_{t}, y_{t})$. Once the network is trained, you can predict the position of the dog at any point in the future.

Let $M$ be our trained model and let's say you want to predict the position of the dog at time $k$ and you know the current position of the dog at time $t$.

$M(x_{t}, y_{t}) = (x_{t+1}, y_{t+1})$

$t = t+1$

$M(x_{t}, y_{t}) = (x_{t+1}, y_{t+1})$

$...$ increment $t$ and keep predicting until $t+1 = k-1$

$M(x_{t+1}, y_{t+1}) = (x_{k}, y_{k})$

Put in pictures this corresponds to:
 (picture from Udacity lecture about Deep Learning)


Equivalent regular expressions - Proof I came across the following two regular expressions $r_1 = 0^+(10^+0)^∗0^*$ and $r_2 = 0^+(10^+0)^∗$.
I know, in general, proving if two regular expressions are equivalent is hard in terms of time complexity, and that there are several algorithms to determine this. (e.g, convert regex to DFAs.) However, I wanted to know if there is a simpler method for this particular example.
Firstly, they seem to be equivalent.
Intuitively, $r_1$ describes all the words that $r_2$ does since both expressions are the same except for the $0^*$ at the end of $r_1$.
Next, let us rearrange $r_1$ and $r_2$ like so:
$r_1 = 0^+(100^+)^∗0^*$
$r_2 = 0^+(100^+)^∗$
Note that although we changed the order of the expression in the parentheses, it still expresses the same idea, which is zero or more repetitions of one 1 followed by at least two zeroes.
This english description seems to apply even when we append the $0^*$ at the end of $r_1$. Because if we had $m$ zeroes at the end of a word (e.g, 00000100100000), all we would have to do is to use $m$ zeroes for the last repetition of the expression in the parentheses, and just ignore the $0^*$.
This is kind of like my intuition, but I wanted to know if there is any formal proof for this? Or even, I might be wrong, and these regex are not equivalent and there is a counterexample.

Using $s^* = \epsilon + s^*s$, we have
$$
0^+(10^+0)^*0^* = \\
0^+ (\epsilon + (10^+0)^*10^+0)0^* = \\
0^+0^* + 0^+(10^+0)^*10^+00^*
$$
Similarly,
$$
0^+(10^+0)^* =
0^+ (\epsilon + (10^+0)^*10^+0) = \\
0^+ + 0^+(10^+0)10^+0
$$
Therefore it suffices to convince oneself that $0^+0^* = 0^+$ and $0^+00^* = 0^+0$.
If you want to turn it into a completely formal proof, you'll need to satisfy a list of axioms and derivation rules, but the proof will likely follow similar steps.


What does all uppercase letters mean? I am reading https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and would like to know, what the following statement means:

Lambda terms: M,N ::= x | (M N) | (λx.M).

It is from page 11.

What does for example mean? Is x a type of M and N?

As it's explained in the comments, $M$ and $N$ are know as metavariables. More importantly, this kind of definition is known as an inductive definition, that is, you start with very basic elements (symbols belonging to the set $\mathcal{V}$) and build up more complex things from there.

For instance, let $\mathcal{V} = \{v_0, v_1, \ldots, v_{1001}, \ldots\}$. In the BNF definition:

$$ M,N ::= x \mid (M N) \mid (\lambda x.M) $$

$x$ can be any of the $\{v_0, v_1, v_2, \ldots \}$. That means any symbol from $\mathcal{V}$ can be considered a $\lambda$-term, a most basic of rules.
$M$, $N$ are structures already known to be $\lambda$-terms, so from the previous example we can build expressions like $(v_0 ~ v_1)$, $(v_{100} ~ (v_{0} ~ v_{1}))$, $((v_{100} ~ (v_{0} ~ v_{1})) ~ v_2) $ and so on.
With the previous two rules you can now build more complex expressions like $(\lambda v_{100}. (v_0 ~ v_1))$, since all previous terms made by combining the two previous rules are known to be $\lambda$-terms.
Now you can mix all three rules, like in $(v_0 ~ (\lambda v_9.(v_9 ~ v_{999})))$


Why strokes are treated differently than fills in modern graphics pipelines This article shows some of the issues. But basically, on the web, you have fillStyle and strokeStyle, and in WebGL you have those different ways of rendering primitive lines, but you end up needing workarounds to draw more complex lines. In CSS borders don't have patternable backgrounds, etc.

Wondering why this limitation is placed on strokes/borders, if it has some history or background on why. It seems like in many cases you want a line to have as much freedom as a "fill", such as gradients, patterns, animations, text, etc. For example, pen strokes vary in thickness all over the place, but strokes typically only support 1 width.

Modern graphics hardware draws triangles. 99% of the hardware is dedicated to drawing triangles. One percent is support for line drawing, and it's mostly for historical reasons. If at all possible, line drawing will be done using the triangle drawing hardware.


Is this language Context-Free? Possible Duplicate:
  Is this language Context-Free?

The language is defined by
$$(a+b)^*-\{(a^nb^n)^n\mid n \geq1 \}$$

is Context-Free Language? I believe that the answer is that it is not a CFL's, but I can't prove it by Ogden lemma or pumping lemma.

chazisop, (a+b)* means {a,b}*. That's all strings that you can form with the symbols a or b or both.

If I understand the notation correctly, only $ab$ can fit both $(a+b)^{*}$ and $(a^{n}b^{n})^{n}$. I see no other way of stacking more $b$'s after the a's, since $a+$ suggest you should have at least one $a$ in every repetition of the expression in parentheses.

$(a+b)^{*}-ab$ seems like a regular language to me, since $ab$ rejects, $a+b$ just consumes one or more $a$'s before a $b$. If we can construct a DFA for $a+b$, we can construct one for $(a+b)^{*}$ as well.


Differences between programming model and programming paradigm? What is the relation and difference between a programming model and
a programming paradigm? (especially when talking about the
programming model and the programming paradigm for a programming
language.)
Wikipedia
tries to answer my question in 1:

  Programming paradigms can also be compared with programming models that are abstractions of computer systems. For example, the
  "von Neumann model" is a programming model used in traditional
  sequential computers. For parallel computing, there are many
  possible models typically reflecting different ways processors can
  be interconnected. The most common are based on shared memory,
  distributed memory with message passing, or a hybrid of the two.

But I don't understand it:

Is it incorrect that the quote in Wikipedia says "the 'von Neumann model' is a programming model", because I understand
that the Von Neumann model is an architectural model from
https://en.wikipedia.org/wiki/Von_Neumann_architecture?
Are the parallel programming models "typically reflecting different ways processors can be interconnected"? Or are parallel
architectural models "reflecting different ways processors can be
interconnected" instead?

In order to answer the question in 1, could you clarify  what a programming model is?

Is it correct that a programming model provided/implemented by a
programming language or API library, and such implementation isn't
unique?

From Rauber's Parallel Programming book, "programming model" is
an abstraction above "model of computation (i.e. computational
model)" which is in turn above "architectural model". I guess that a
programming model isn't just used in parallel computing, but for a
programming language, or API library.

A programming model is implied by the system architecture. If your system architecture is a register machine, your programming model will consist of machine code operations on registers. If your architecture is a stack machine, your programming model will consist of stack operations. A Von Neumann architecture and a Harvard architecture will have other programming models. Self modifying code p.e. wil be possible in a Von Neumann architecture but not in a Harvard architecture.

A programming paradigm is more highlevel: it is the way a problem is modelled (imperative or declarative, Object oriented, functional, logic,...). A single paradigm language supports one of these. Multiparadigm languages are more a sort of Swiss armyknive which take elements out of more paradigms.

Every architecture (and corresponding model) will have his own set of machine code instructions. This machine code language itself will follow the imperative paradigm (do this , do that, read register A, add the value to register B,... or put a value on top af the stack, put another value on top of the stack, add the two values on top..., etc...)

(At least I never saw a non-imperative hardware processor)

A high level language (of whatever paradigm) will be compiled or interpreted to this machine code.

About parallelism: If we consider interconnected processors it will be clear that the way they interconnect will be part of the programming model. An old INMOS transputer p.e. connects with four other transputers. The machine code wil have instructions to communicate with the naburing transputers.

But also on recent systems the way to provide mutual exclusion will have to be resolved on low level. On a one processor system we will have to put the interrupts on and off when leaving or entering the critical section. On a multiprocessor system we will need a monoatomic 'test and set' instruction. This is part of the programming model.

Parallel computing paradigms are high level models to use parallelism. Think on languages who have threaded objects, or use semaphores and monitors as language elements.

When we program on different operating systems, different API's will be used. (or even if we program on the same system but we use an other library - a graphics library p.e.). This will change our programming model. the low level code will be different, but if there is a good abstraction (sort of code once, compile anywhere) this will be invisible in the high level language. If not, you will have to make small changes in your code. But since you will use the same high level language, there will be no change of paradigm.


Fastest search algorithm in a sorted list with certain error rate-limiting constraints This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle.

Problem description:

A random number N between 0 and 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815 (~3.9*10^115 or 64^64) is selected
You have to find the correct number N
You can take a guess X, and get a response whether the number X is greater or lower than N
The twist:

you can only perform 13 guesses in 30s without hitting a 90s timeout - 13/30
if your guess was lower, then you get an error and you can only have 2 errors in 30s without a 90s timeout - 2/30
you have only 2240s time to find the correct value

I had a short discussion with the challenge creator about the solution and he solved it like the broken egg problem. His algorithm basically runs in constant time. As max number is 64^64, he divides the problem in 64 buildings with 64 floors. And a broken egg is an error. This means it takes overall pretty constant 1920s. I think the problem is not equivalent to the egg problem, but somehow the algorithm performs here really really well.

I chose a skewed binary search. Instead of splitting the search field into 50:50, I skew to one side 2/13=0.15 15:85. This way the probability of hitting the punishing error condition is pretty unlikely. My intuition tells me, that this should be the most efficient algorithm, but apparently it's not.

I thought the 0.15 skew would be the best ratio, but after analysing the time it takes with different ratios, the most efficient value seems to be around ~0.22. My calculation is obviously wrong, but what would have been the correct calculation to find ~0.22?

Why does the egg problem algorithm perform better (as in faster on average)?
What is the on average fastest algorithm here? And why is it not based on a skewed binary search?

Any thoughts and comments are welcome.

For simplicity of analysis I will say that 'too high' is the error condition, which is just the problem inverted, $64^{64}-n$. I also assume that requests are instant.

It takes some thinking, but waiting is never an optimal strategy. So we view the problem as just a series of guesses, done in blocks of 13 (unless we hit the 90 second timeout). Instead of timeouts our penalty will be losing guesses, and instead of minimizing time we will minimize guesses used. I write $V_2$ for the value of a guess (in bits) when we are in the state where we guessed too high twice in this block. Similarly I will write $V_1, V_0$. I write $g \in \{0\dots13\}$ for the number of guesses left in the block, including the current one.

I will evaluate a strategy where we pick three numbers $p_0$, $p_1$, $p_2$, where each $p$ encodes how skewed the binary search is for when we've guessed $0$, $1$ or $2$ wrong times in this block.

The expected value (in bits) of a guess $p \in [0, 1]$ (where $0$ is the lowest guess and $1$ is the highest) is the binary entropy function $H(p) = -p \log_2 p - (1 - p)\log_2(1-p)$.

However, for $V_2(g)$, if we guess wrong we lose the rest of this block and the next two blocks, $B$ is the value of a block in bits.

$$V_2(g) = H(p_2) - 2p_2B - p_2\sum_{k=1}^{g-1}V_2(k)$$

If we write $E_2(g)$ as the value in bits of being in state $2$ with $g$ guesses left:

$$E_2(g) = \sum_{k=1}^{g} V_2(k) = \sum_{k=1}^g \big( H(p_2) - 2p_2B - p_2E_2(k-1)\big ) $$
$$E_2(g) = g(H(p_2) - 2p_2B) - p_2 \sum_{k=1}^g E_2(k-1)$$

This recurrence can be solved:

$$E_2(g) = (H(p_2)/p_2 - 2B)(1-(1 - p_2)^g)$$

Similarly, if we guess wrong for $V_1$, we lose our advantage from state $1$:

$$V_1(g) = H(p_1) - p_1(E_1(g-1) - E_2(g-1))$$
$$E_1(g) = \sum_{k=1}^{g} V_1(k) = \sum_{k=1}^{g} \big( H(p_1) - p_1(E_1(k-1) - E_2(k-1))\big )$$

$$E_1(g) = g(H(p_1) - p_1E_2(g-1)) - p_1\sum_{k=1}^{g}E_1(k-1)$$

$$E_1(g) = (H(p_1)/p_1 - E_2(g-1))(1-(1 - p_1)^g)$$

And $E_0$ is directly analogous. Now, since $B = E_0(13)$ we have:

$$E_0(g) = (H(p_0)/p_0 - E_1(g-1))(1-(1 - p_0)^g)$$
$$E_1(g) = (H(p_1)/p_1 - E_2(g-1))(1-(1 - p_1)^g)$$
$$E_2(g) = (H(p_2)/p_2 - 2E_0(13))(1-(1 - p_2)^g)$$

Oh boy... With a CAS I found:

$$E_0(13) =\frac{1}{2P_0P_1P_2 + 1} \left(\frac{P_0H(p_0)}{p_0} - \frac{P_0P_1H(p_1)}{p1} +\frac{P_0P_1P_2H(p_2)}{p_2}\right)$$

where $P_0 = 1-(1-p_0)^{13}$, $P_1 = 1-(1-p_1)^{12}$ and $P_2 = 1-(1-p_2)^{11}$. This is the expression we want to maximize.

Numerically  maximizing this expression gives $E_0(13) \approx 6.72$ bits with:

$$p_0 \approx 0.1854365,\quad p_1 \approx 0.1422816,\quad p_2 \approx 0.0000899$$

This means that in order to get $\log_2(64^{64}) = 384$ bits we expect to need 57.1 blocks, or 1714.3 seconds.

This isn't even optimal yet, though. $p_0, p_1, p_2$ should actually be functions of $g$ (consider that if you are on your last guess in state $0$, then you can be really greedy and not get punished). I will see if I can improve my answer.


Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements? I had a question about random shuffling. Given a sorted list, is it possible to design an algorithm to return a uniformly random arrangement of the items in a deque with the following operations:

read from list and add to front of deque
read from list and add to back of deque
remove from front of deque and add to back
remove from back of deque and add to front

I am trying to figure out an algorithm to do this without the aid of any other arrays or memory (i.e. outside of the original list of size N and the deque, there is no additional memory). After experimenting with it, I'm doubting it's possible to obtain a truly uniformly random arrangement of the items, but I'd love to be proven wrong. Any guidance would be appreciated.

The final algorithm:
for each new element k:
    perform a random cyclic shift of the sequence on the deque
    insert k to the end of the deque
    perform an inverse cyclic shift

Now, why does it work? (There is probably a simpler way to put it; this is how I understand this)
We generate a random permutation $p$ (we would need additional memory for that, but I'll explain how to avoid it). We replace each input number $a_i$ with pair $(a_i, p_i)$. Now it suffices to sort the pairs based on the second element. It works because different permutations correspond to different orders of elements after sorting.
To perform the sorting, we simply emulate insertion sort:

Let $[p_1, \ldots, p_m]$ be the current numbers in deque, and they are in sorted order.
Then another number $k$ arrives, such that $p_1 < \cdots < p_i < k < p_{i+1} < \cdots < p_m$.
We perform the cyclic shift: $[p_{i+1}, \ldots, p_m, p_1, \ldots, p_i]$.
We insert $k$ in the back: $[p_{i+1}, \ldots, p_m, p_1, \ldots, p_i, k]$
We perform an inverse cyclic shift: $[p_1, \ldots, p_i, k, p_{i+1}, \ldots, p_m]$

To avoid storing the permutation, notice that it suffices to decide the relevant order of elements at the moment of insertion. I.e. for each element, you randomly determine its position among existing elements in the deque and perform the shifts as described.


Boolean expression to a truth table How do I fill a truth table from the following expression? I can't decide whether it is SOP or POS.

Y=(A+B)C+AB`+(A+C)C`+(`AB)

SoP or PoS doesn't matter when building a truth table, you just list out the 8 possible inputs and then derive the possible outputs.

If A B and C are all false what is the value of Y?

If only C is true what is the value of Y?

And so on.


What is a fast algorithm for partitioning an array into $k$ subsets $A_1<\dots<A_n$? Let $A$ be an array (equipped with a total ordering $\leq$) of size $n = km$ with $k\in \mathbb{N}$, such such that $A[1],\dots,A[n]$ are all distinct. What is a fast way to find a partition $A_1,\dots,A_k$ of $A$ with $|A_i| = m$ for all $i$, such that $x<y$, if $x\in A_i$ and $y\in A_j$ with $1\leq i<j$?

I have the following rough idea:

find the $i\cdot m$-th order statistic for $i = 1,\dots, k$ and put them into an (automatically) ordered list $\operatorname{pvt}$
iterate through the elements of $A$ and find for every such element (via binary search) the corresponding interval in $\operatorname{pvt}$ and insert it into the corresponding $A_i$

The first step can be done in $O(nk)$ (finding the $l$-th order statistic can be done in $O(n)$) and the second step in $O(n\log k)$, giving us $O(nk)$ in total.

Is there an obvious faster algorithm? (provided this idea works at all)

You can do $O(n \log k)$ by finding $mk/2$-order statistic, partitioning the array into two parts of size $mk/2$ and recursing on each side until $k = 1$. You get the recurrence on running time $T(m, k) = 2 T(m,k/2) + \Theta(m k)$ and $T(m, 1) = \Theta(1)$, which solves to $T(m,k) = O(m k \log k) = O(n \log k)$.


Finding a tight bound for a recurrence relation Problem:
Give tight asymptotic bounds $( \Theta )$ for the following function:
$$ T(n) = T(n-2) + n $$
Answer:
We are not given the base case. I am going to assume that $T(0) = 0$ and $T(1) = 1$. Here are some
values for the function.
$$T(2) = T(0) + 2 = 2$$
$$T(3) = T(1) + 3 = 4 $$
$$T(4) = T(2) + 4  = 6 $$
$$T(5) = T(3) + 5 = 9 $$
$$T(6) = T(4) + 6  = 12 $$
$$T(7) = T(5) + 7 = 16 $$
$$T(8) = T(6) + 8 = 20 $$
$$T(9) = T(7) + 9 = 25 $$
$$T(10) = T(8) + 10 = 30 $$
It is growing faster than $O(n)$ time. I am fairly sure that $T(n) \in O(n^2)$. That is, $O(n^2)$ is an
upper bound. If $T(n)$ is $\theta(n^2)$ then going from $n = 5$ to $n = 10$ we would expect, about, a
factor of $4$ increase. We got an increased by a factor of $\frac{ 10}{3}$. I am thinking that the correct answer is:
$$T(n) = \Theta(n^2)$$.
However, I do not know how to prove that it is correct? or disprove it?

You just need to expant it (suppose $n$ is even) and using mathematical induction:
$$T(n) = n + (n-2) + T(n-4) = n + (n-2) + (n-4) + \cdots + 4 + 2 = $$
$$2 ( 1 + 2 + \cdots + \frac{n}{2}) = 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \frac{n(n+2)}{4} = \Theta(n^2)$$


Is a LBA with stack more powerful than a LBA without? Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful.

A LBA with stack should not be Turing complete, because its halting problem should be decidable. (It seems to be equivalent to the halting problem for a PDA).

Can a deterministic LBA with stack decide all problems decided by a nondeterministic LBA?

Or on the other hand, maybe a LBA with stack is (provably) not more powerful than a LBA?

Edit I think I found out how a deterministic LBA with stack can simulate a nondeterministic LBA. The stack can be used to store and recall the current state of the external memory (the linear bounded memory) as often as needed. The internal state is finite, so there is a global bound for the maximal number of nondeterministic moves available in a single step. So backtracking can be used to recursively simulate the result of each nondeterministic move.

I will have to think about how to make these two observations (halting problem is decidable, nondeterministic LBA can be simulated deterministically) more rigorous, before self-answering. I'm away next week, so don't hold your breath.

Theorem The following are equivalent.

$L$ is accepted by a deterministic LBA with stack
$L$ is accepted by a nondeterministic LBA with stack
$L$ is in $\operatorname{DTIME}(c^n)$ for some constant $c$.

So the computational power of a LBA with stack for decision problems is well understood. The exponential runtime limits the usefulness of this knowledge in practice. But the notion of an LBA with stack can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of

a read-only input tape, surrounded by endmarkers,
a finite state control,
a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
a stack

In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, and Computation (1st ed.) we find:

Theorem 14.1 The following are equivalent for $S(n)\geq\log n$.

$L$ is accepted by a deterministic $S(n)$-AuxPDA
$L$ is accepted by a nondeterministic $S(n)$-AuxPDA
$L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.

with the surprising:

Corollary $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.

Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking. (So this proof also contains the two observations which I wanted to make more rigorous. This answer is already long enough anyway, so I won't go into more detail here.)

This leads to the following answer for the initial question Is a LBA with stack more powerful than a LBA without?: The question is equivalent to a well know open problem, and the expectation is that it is indeed more powerful.


What problems of procedural programming does OOP solve in practice? I have studied the book "C++ Demystified". Now I have started to read "Object-Oriented Programming in Turbo C++ first edition (1st edition)" by Robert Lafore. I do not have any knowledge of programming which is beyond these books. This book might be outdated because it's 20 years old. I do have the latest edition, I am using the old because I like it, mainly I am just studying the basic concepts of OOP used in C++ through the first edition of Lafore's book.

Lafore's book emphasizes that "OOP" is only useful for larger and complex programs. It is said in every OOP book (also in Lafore's book) that procedural paradigm is prone to errors e.g. the global data as easily vulnerable by the functions. It is said that programmer can make honest errors in procedural languages e.g. by making a function that accidentally corrupts the data.

Honestly speaking I am posting my question because I am not grasping the explaination given in this book: Object-Oriented Programming in C++ (4th Edition) I am not grasping these statements written in Lafore's book:

  Object-oriented programming was developed because limitations were discovered in
  earlier approaches to programming....
  As programs grow ever larger and more complex, even the structured programming approach begins to show signs of strain...
  ....Analyzing the reasons for these failures reveals that there are weaknesses in the procedural paradigm itself. No matter how well the structured programming approach is implemented, large programs become excessively complex....
  ...There are two related problems. First, functions have unrestricted access to global data. Second, unrelated functions
  and data, the basis of the procedural paradigm, provide a poor model of the real world...

I have studied the book "dysmystified C++" by Jeff Kent, I like this book very much, in this book mostly procedural programming is explained. I do not understand why procedural(structured) programming is weak!

Lafore's book explains the concept very nicely with some good examples. Also I have grasped an intuition by reading Lafore's book that OOP is better than procedural programming but I am curious to know how exactly in practice procedural programming is weaker than OOP.

I want to see myself what are the practical problems that one would face in procedural programming, how the OOP will make the programming easier. I think I will got my answer just by reading Lafore's book contemplatively but I want to see with my own eyes the problems in the procedural code, I want to see how the OOP style code of a program removes the foregoing errors that would happen if the same program were to be written using procedural paradigm.

There are many features of OOP and I understand it is not possible for someone to explain me how all these features removes the foregoing errors that would generate by writing the code in procedural style.

So, here is my question:

  Which limitations of procedural programming does OOP address and how does it effectively remove these limitations in practice?

In particular, are there examples for programs which are hard to design using the procedural paradigm but are easily designed using OOP?

P.S: Cross posted from: https://stackoverflow.com/q/22510004/3429430

In a procedural language you can't necessarily express restrictions that are required to prove that the caller is using a module in a supported fashion.  In the absence of a compiler checkable restriction, you have to write documentation and hope that it is followed, and use unit tests to demonstrate intended uses.

Declaring Types is the most obvious declarative restriction (ie: "prove that x is a float").  Forcing data mutations to pass through a function known to be designed for that data is another.  Protocol enforcement (method invoke ordering) is another partially supported restriction ie: "constructor -> othermethods* -> destructor".

There are also a real benefits (and a few drawbacks) when the compiler knows about the pattern.  Static typing with polymorphic types are a bit of a problem when you emulate data encapsulation from a procedural language.  For example:

the type x1 is a subtype of x, t1 is a subtype of t

This is one way to encapsulate data in a procedural language to have a type t with methods f and g, and a subclass t1 that does likewise:

t_f(t, x, y, z, ...), t_g(t, x, y, ...)
t1_f(t1, x, y, z, ...)

In order to use this code as it is, you have to do a type check and switch on type of t before deciding the kind of f you will invoke.  You could work around it like this:

type t {
  d : data
  f : function
  g : function
}

So that you invoke t.f(x,y,z) instead, where a typecheck and switch to find the method is now replaced with just having each instance store method pointers explicitly.  Now if you have a huge number of functions per type, this is a wasteful representation.  You could then would use another strategy like having t point to a variable m which contains all of the member functions.  If this feature is part of the language, then you can let the compiler figure out how to deal with making an efficient representation of this pattern.

But data encapsulation is recognition that mutable state is bad.  The object oriented solution is to hide it behind methods.  Ideally, all of the methods in an object would have a well defined calling order (ie: constructor -> open -> [read | write] -> close -> destruct); which is sometimes called a 'protocol' (research: "Microsoft Singularity").  But beyond construct and destruct, these requirements are generally not part of the type system - or well documented.  In this sense, objects are concurrent instances of state machines that are transitioned by method calls; such that you might have multiple instances and use them in an arbitrarily interleaved fashion.

But in recognizing that mutable shared state is bad, it can be noted that object orientation can create a concurrency problem because the object data structure is a mutable state that many objects have a reference to.  Most object oriented languages execute on the thread of the caller, which means that there are race conditions in the method invocations; let alone in non-atomic sequences of function calls.  As an alternative, every object could get async messages in a queue and service them all on the object's thread (with its private methods), and respond to the caller by sending it messages.

Compare Java method calls in a multi-threaded context with Erlang processes sending messages (that only reference immutable values) to each other.

Unrestricted Object Orientation in combination with parallelism is a problem due to locking.  There are techniques ranging from Software Transactional Memory (ie: ACID transactions on in memory object similar to databases) to using a "share memory by communicating (immutable data)" (functional programming hybrid) approach.

In my opinion, Object Orientation literature focuses FAR too much on inheritance and not enough on protocol (checkable method invocation ordering, preconditions, postconditions, etc.).  The input that an object consumes should usually have a well defined grammar, expressible as a type.