Properties of reciprocal Quines I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same programming language.

Thinking of this particular case I have come to the conclusion that these two program must necessarily submit to certain properties. The first thing that came to my mind is the fact that they cannot have different cardinalities, the reason is easily understood: lets take the case that one of the two (lets say $A$) has a $\gt$ cardinality, so  $\mid A \mid\gt\mid B \mid$.

Now we codify this example in a trivial way: $A = 1111$ (|A|=4) and $B = 111$ (|B|=3).
It is evident that $A$ can produce the $B$ code but the reverse cannot happen as $B$ has fewer bits than $A$. The only way for the game to work is that the programs have the exact same length and all the practical examples I have seen online (through high-level programming languages) seem to respect this "supposition" of mine.
A second thing I noticed is the fact that these two codes differ only by a short number of characters.

Am I making any mistakes in these considerations?
Is there a way to calculate the maximum number of difference characters that can exist between the two codes?

I would also appreciate if someone could indicate me some sources for the theoretical study of this particular case of quines, searching online I found only practical examples
accompanied by brief explanations on the syntax of programming languages.

I don't see why they should have the same length, given that one can succinctly output large amounts of whitespace using something like

for i=1 to 1000 do
    print " "

So, given any mutual Quines $A$ and $B$, one could surely add 1000 spaces to $A$ and 2000 spaces to $B$ and adjust the programs to use for loops like the above.


What actually is Blocking flow problem? I am facing a hard time understanding Blocking Flow problem. This is what I have understood till now : We have a graph and in blocking flow problem we find all shortest paths from source to destination and saturate atleast one edge in all of the shortest paths respectively [1] and we delete that path. In examples I am reading online, it is explained with an example of graph with all edges of unit length
[2].  Our professor explained the solution to this using dynamic trees. I am unable to apply the concept of dynamic trees (splay) for the solution of this problem. What will be stored in the nodes of the tree and on what basis will we perform the spaly operation?

[1] There can only be one shortest path, or many shortest paths of same length. What is the concept of all shortest paths?

[2] If a graph has all edges of unit lengths, then all the edges will be deleted (because all will appear in some path from source to sink). Then, source and destination will be disconnected in the end. What would be the use of doing this?

What is the goal for solving this problem? Can someone point in right direction in layman's terms? Also I have read some articles regarding this but unable to understand them and also none of them uses splay trees to solve this problem.

A blocking $s$-$t$ flow is a flow whose residual network (consisting of all edges not saturated by the flow) contains no $s$-$t$ path. Stated differently, a blocking flow is a flow which, for every $s$-$t$ path, saturates at least one edge. Equivalently, a blocking flow is a flow which, for every simple $s$-$t$ path, saturates at least one edge.

The blocking flow problem is to find a blocking flow in a flow network. Such a flow exists since a maximum flow is always a blocking flow (but not vice versa).

The concept of blocking flow is used in Dinitz's maximum flow algorithm.


How to measure "sortedness" I'm wondering if there is a standard way of measuring the "sortedness" of an array?  Would an array which has the median number of possible inversions be considered maximally unsorted?  By that I mean it's basically as far as possible from being either sorted or reverse sorted.

No, it depends on your application. The measures of sortedness are often refered to as measures of disorder, which are functions from $N^{<N}$ to $\mathbb{R}$, where $N^{<N}$ is the collection of all finite sequences of distinct nonnegative integers. The survey by Estivill-Castro and Wood [1] lists and discusses 11 different measures of disorder in the context of adaptive sorting algorithms.

The number of inversions might work for some cases, but is sometimes insufficient. An example given in [1] is the sequence

$$\langle \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n, 1, \ldots, \lfloor n/2 \rfloor \rangle$$

that has a quadratic number of inversions, but only consists of two ascending runs. It is nearly sorted, but this is not captured by inversions.

[1] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.


Why does this particular hashCode function help decrease collisions? I just read in Effective Java about the hashCode method:

  Store some constant nonzero value, say, 17, in an int variable called result.
  For each significant field f in your object (each field taken into account by the equals method, that is), do the following:

  a. Compute an int hash code c for the field.

  b. Combine the hash code c computed in step 2.a into result as
  follows: result = 31 * result + c;

  A nonzero initial value is used in step 1 so the hash value will be
  affected by initial fields whose hash value, as computed in step 2.a,
  is zero.

  If zero were used as the initial value in step 1, the overall
  hash value would be unaffected by any such initial fields, which could
  increase collisions. The value 17 is arbitrary. The multiplication in
  step 2.b makes the result depend on the order of the fields, yielding
  a much better hash function if the class has multiple similar fields.

And that's their implementation of hashCode:

@Override public int hashCode() {
    result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    hashCode = result;
    return result;
}

My questions are below:

How does the initial value 17 help us decrease collisions?
How does multiplying by 31 help us decrease collisions?
Why do we use 17 and 31? I know they are prime numbers. Is that why we use them?

I tried to come up with an example of a collision using a class with two and three integer fields, but didn't succeed. I'd glad, if you gave me a simple example of a collision.

If the hashed codes are $x_1,\ldots,x_n$ (in that order), then the resulting hash value is
$$
x_n + 31 x_{n-1} + 31^2 x_{n-2} + \cdots + 31^{n-1} x_1 + 31^n \cdot 17 \pmod{2^{32}},
$$
assuming int is 32 bits, and ignoring signed/unsigned distinctions. In view of this, the integers 17 and 31 should satisfy the following two properties:

17 should be non-zero. This way, the hash depends on the input length. Otherwise it is completely arbitrary.
31 should be relatively prime to $2^{32}$ (i.e., odd) and have a high order modulo $2^{32}$ (that is, the minimal $m$ such that $31^m \equiv 1 \pmod{2^{32}}$); this way the multiplicands $31,31^2,\ldots$ are all different for the longest time possible. It turns out that the order of $31$ modulo $2^{32}$ is only $2^{27}$, so 31 is not an optimal choice. Its being prime makes no difference – we only care about its oddness and order.

In any case, this hash can be improved on – for example, the python hash function uses XOR instead of addition, thus making the resulting calculation non-algebraic.


Cache efficient matrix multiplication Consider these matrices:

$A=\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$

$B=\begin{bmatrix}-1 & -2\\-3 & -4\end{bmatrix}$

Using standard algorithm:

$C=\begin{bmatrix}1*-1+2*-3 & 1*-2+2*-4\\3*-1+4*-3 & 3*-2+4*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\-15 & -22\end{bmatrix}$

Transpose B and do dot product row wise for A and B

$B^T=\begin{bmatrix}-1 & -3\\-2 & -4\end{bmatrix}$

$C=\begin{bmatrix}1*-1+2*-3 & 1*-2+2*-4\\3*-1+4*-3 & 3*-2+4*-4\end{bmatrix}=\begin{bmatrix}-7 & -10\\-15 & -22\end{bmatrix}$

I'd like to know whether the second version is correct in general?

And whether the second version is more cache efficient than the standard algorithm?

Why has matrix multiplication been defined as row with column?

NOTE: I do know real world implementations such as BLAS use different techniques than the naive implementation.

It is correct.

Mathematically, $A$, $B$ and $C$ are foremostly linear mappings between vector spaces. Say, $A:W\to X$ and $B: V\to W$, then $C = A\circ B$ is a linear mapping $V\to X$. Practically speaking, and that's where the matrix representation stems from, you represent a mapping $V\to W$ as a member of the tensor space
$V^\ast\otimes W$, where $V^\ast$ is the dual space of $V$, that is, any linear mapping $V\to W$ can be written in the form
$$
B(v) = \sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)
$$
where $b_{jk}$ are the coefficients characterising the mapping, and the $w_j$ form a convention-chosen basis of $W$ and the $f_k:V\to \mathbb{R}$ (or whatever field you're working over) basis of $V^\ast$. Then, we can see what the composition comes out as:
$$\begin{align}
C(v) = A(B(v)) =& \sum_l\sum_i x_l\cdot a_{li}\cdot g_i\Bigl(\sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)\Bigr)
  \\ =& \sum_{lijk} x_l\cdot a_{li}\cdot b_{jk}\cdot g_i(w_j)\cdot f_k(v)
\end{align}$$
The basis of $W$'s dual space will be chosen so that $g_i(w_j)=\delta_{ij}$, so
$$\begin{align}
C(v) =& \sum_{ljk} x_l\cdot a_{lj}\cdot b_{jk}\cdot f_k(v)
  \\ =:& \sum_{lk} x_l\cdot c_{lk}\cdot f_k(v)
\end{align}$$
where you have your matrix multiplication
$$
c_{lk} = \sum_j a_{lj}\cdot b_{jk}.
$$
There are two alternative, equivalent ways to look at linear mappings, and one of them you found: you basically group
$$
A(w) = \sum_{li} x_l\cdot a_{li}\cdot g_i(w)
     = \sum_l x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)(w)
$$
...which you can do because the dual space is also a vector space; $\Bigl(\sum_i a_{li}\cdot g_i\Bigr)$ are just the row vectors of $A$ which are not in fact vectors but co-vectors—and now
$$\begin{align}
A(B(v)) =& \sum_l x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)\Bigl(\sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)\Bigr)
  \\ =& \sum_{lk} x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)\Bigl(\sum_jw_j\cdot b_{jk}\Bigr)\cdot f_k(v)
\end{align}$$
..and there in the middle is that scalar product between a row vector of $A$ and a column vector of $B$ (or, if you will, a row vector of $B^T$).

So yeah, this can be done and is often done in algorithms.

Does it help with cache? It can certainly help, if you naturally come by $B$ in transposed form. I think e.g. the Eigen library exploits this a lot, through lazy evaluation and pre-arranging intermediate results to come out transposed in the first place if deemend useful. If all you got is $B$ in un-transposed form though, well, the cost of transposing it (which is also not readily cache-friendly) may outweigh the cache penalty of multiplying in suboptimal order.

There are many approaches to this, it's a well studied field. But there's no silver bullet for the optimal transposition policy. (An interesting approach is to store matrices in Morton order, so that always both rows and columns have some cache coherence.)


Is this in-place merge algorithm efficient or not? I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head elements of the second list, swaps them, and recurses on the four sublists. Code for the algorithm:

// Assuming that the subranges [start, mid) and [mid, end)
// are each sorted, this yields [start, end) being sorted.
void merge(int[] array, int start, int mid, int end) {
    // Check bounds
    assert 0 <= start && start <= mid &&
        mid <= end && end <= array.length;
    if (start == mid || mid == end)
        return;

    // Find tail section of first list
    // and head section of second list
    int left = mid - 1;
    int right = mid;
    while (start <= left && right < end
            && array[left] > array[right]) {
        left--;
        right++;
    }

    // Swap elements
    int n = right - mid;
    for (int i = 0; i < n; i++) {
        int j = mid - n + i;
        int k = mid + i;
        int temp = array[j];
        array[j] = array[k];
        array[k] = temp;
    }

    // Recurse on two pairs of sorted sublists
    merge(array, start, left + 1, mid);
    merge(array, mid, right, end);
}

An actual implementation can be found here.

So far I was able to establish these points:

The recursive algorithm terminates, and correctly merges two lists.
In the worst case when merging two lists that are $n$ elements each, there could be $O(n)$ recursion depth. For example, when merging [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and [0, 10, 11, 12, 13, 14, 15, 16, 17, 18], the 9 swaps with 0 and then recurses. Due to the stack space usage, it is clear that the algorithm is not "in-place" as hoped.
If both initial lists have roughly the same distribution (and are "balanced"), then we can expect the merge recursion depth to be $O(\log n)$ which is good.

My questions are as follows:

Does this merge algorithm have $O(n)$ time complexity or something worse? Because if it's worse, then the overall merge sort can't be in $O(n \log n)$. I want to know if it can degenerate in a way similar to how quicksort can exhibit $O(n^2)$ behavior.
Is there a way to reduce the worst-case stack space usage to $O(\log n)$ using tail recursion? I'm thinking about the trick used in quicksort where recursion is used on the smaller subproblem and tail recursion on the bigger subproblem.

Motivation: I'm interested in learning about in-place stable merge sort algorithms. I have a background of implementing a variety of sort algorithms, including the standard merge sort with auxiliary storage.

This algorithm has been previously published in literature; for a detailed worst-case runtime analysis, see [1], [2], and [3]. It is referred to as "Symmerge" or "merging by decomposition". When the two subarrays to be merged are both of length $n$, the algorithm runs in worst-case $O(n \log n)$-time and uses $O(\log n)$ space (due to recursion).

If we use this algorithm for mergesort, the overall mergesort recurrence becomes $T(n)=2T(n/2)+O(n\log n)$; using the Extended master theorem, we know $T(n)=O(n \log^2 n)$.

[1]: P.-S. Kim and A. Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.4612&rep=rep1&type=pdf

[2]: K. Dudzinski and A. Dydek, "On a stable storage merging algorithm". Information Processing Letters 12 (1981) 5–8.

[3]: S. Dvorak and B. Durian, "Merging by Decomposition Revisited."  The Computer Journal, Volume 31, Issue 6, 1988, Pages 553–556, https://doi.org/10.1093/comjnl/31.6.553


Which data structure to use for accessing min/max in constant-time? I need a data structure which can include millions of elements, minimum and maximum must be accesable in constant time and inserting and erasing element time complexity must be better than linear.

A basic data structure that allows insertion and deletion in time $\Theta(\log n)$ are balanced binary search trees. Their memory overhead is reasonable (in case of AVL trees, two pointers and three bits per entry) so millions of entries are no problem at all on modern machines.

Note that in a search tree, finding the minimum (or maximum) is conceptually easy by descending always left (right) starting in the root. This works in time $\Theta(\log n)$, too, which is too slow for you.

However, we can certainly store pointers to these tree nodes, similar to front and end pointers in double-linked linear lists. But what happens when the elements are deleted? In this case, we have to find the in-order successor (predecessor) and update the pointer to the minimum (maximum). Finding this node works in time $O(\log n)$ so it does not hurt deletion time, asymptotically.

You can, however, enable time $O(1)$ deletion of minimum and maximum by threading the tree, that is maintaining -- in addition to the binary search tree -- a double-linked list in in-order. Then, finding the new minimum/maximum is possible in time $O(1)$. This list requires additional space (two pointers per entry) and has to be maintained during insertions and deletions; this does not make the asymptotics worse but certainly slows down every such operation (I leave the details to you). So you have to trade-off the options given your application, that is which operations occur more often and which you want to be fastest.

Note that trees, as all linked structures, tend to be bad for memory hierarchies since they don't necessarily preserve data locality. If your sets are so large that they don't fit into cache completely, you should check out B-trees which are designed to minimise page loads. The above works with them, too.


Lambda Calculus Argument Delimiter So I've been looking into lambda calculus on and off for months simply trying to understand the numerical system and the successor function.  I understand that it's basically just argument evaluation, but the syntax confused me for the longest time.  Finally, I found this:

S0 = (λ abc.b(abc)) (λ sz.z)
     = λ bc.b((λ sz.z) bc)
     = λ bc.b((λ z.z) c)
     = λ bc.b(c)

from this URL: http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html

and realized that I didn't understand how this worked because there seems to be no delimiter indicating the start of argument space.  My question is: Is there an acceptable delimiter for this in lambda calculus, and, if not, how can I verbalize this when writing or viewing  it?

EDIT: Some people seem to have misunderstood this, so let me explain better.  How do I indicate that a function is being called on a specific set of arguments?  For example, in most programming languages the indicator is just parenthesis

function(arg0,arg1,arg3...)

Is there an equivalent to this in untyped lambda calculus?

ANOTHER EDIT: Okay, it's still misunderstood as to what I mean.  Let's talk about the successor function again.  The wikipedia pages shows something like the following:

Succ=La.Lb.Lc.b (a b c)
               ^

The marked whitespace is annoying since It's not clear that the part in parenthesis is still part of the function itself, and instead looks like an argument is being passed to the function.  Is there a delimiting character that separates the body of the function from the  arguments on which it is to be called?  Example:

Succ=((La.(Lb.(Lc.(b,((a,b),c))))),),,

The problem that I think I'm having is that since functions can be returned as primary values, the syntax doesn't express that very clearly.  However, in the example that I gave, we can see that there are three commas without trailing inputs, indicating that the function takes 3 values (the function to find the successor of and the successor's potential arguments).  Is there a good convention to express the point where a function's body ends and the values that it needs to be evaluated begin?

*A VERY IMPORTANT EDIT: * This is not about currying.

So, I think part of the problem is that the resource you're using is not using standard lambda calculus notation.

In most texts, there is a space between arguments. I would write $\lambda x\ y\ z\ldotp z$ in place of $\lambda x y z\ldotp z$. But, if you assume a convention that variables are always single letters, you can omit the space without ambiguity.

But I can't imagine one would ever write whole programs this way. Rather, this is more likely to show up in examples, code snippets, and small proofs, where there aren't many variables and the names don't matter.

Basically it boils down to this:

A minimal lambda calculus only allows one argument per function, so there's no need for a delimiter. The dot denotes the function body.
There is common syntactic sugar for multiple arguments, which abbreviates $\lambda x \ldotp (\lambda y \ldotp (\lambda z\ldotp z))$ as $\lambda x\ y\ z\ldotp z$.
In a situation where variable names are assumed to be single letters, one could use $\lambda x y z\ldotp z$ in place of $\lambda x\ y\ z\ldotp z$.

There is no delimiter, other than the space, that I know of for arguments. Commas would be frowned upon, since they indicate tuples, rather than curried arguments.

EDIT: to respond to the OPs edit:

There is no such thing as multiple arguments in an untyped lambda calculus, at least not in standard ones. There are two ways to simulate multiple-argument functions.

Tuples: you can use a Church encoding to pass a single argument, which can be decomposed into multiple values. So you would write $f (<x,y>)$, where $<x,y>$ is some special syntax for making a pair, and then decompose it as $HD\ t$ and $TL\ t$ inside your function to get at each argument.
Currying: When, in an imperative language, you would write f(x,y,z), you write $(f\ x\ y\ z)$, which is syntactic sugar for $(((f\ x)\ y)\ z)$. A function accepting multiple arguments is just a function which returns another function.

It turns out that these two are basically isomorphic, so which you do doesn't much matter.

Some languages, like Scheme, have built in syntax for multiple-argument functions, but I haven't seen anything like that in a formal lambda calculus. Usually they're intended to be minimal, and so when you don't need multiple-argument functions, you don't put them in.


I need clarification about DFA's and DFA acceptable languages In class yesterday we went over DFA's and DFA acceptable languages.  An example of a language that is not DFA acceptable was given as $\{ ab, aabb, aaabbb, aaaabbbb, \ldots \}$.  The reason given was that the machine would need an infinite amount of states.

But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?

Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states.  But if you had the language $L = \{ a \}$, over the alphabet $\{ a, b \}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\{ a, b \}^* - \{ a \}$, which includes $\{ ab, aabb, aaabbb, \ldots \}$.

I think I must be misunderstanding something crucial here.

$Doubt-1$:  "But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?"

No, the DFA you are thinking about as below: accepts $(a + b)^*$ that is "all possible string consists of symbols '$a$' and '$b$', including $ε$ string".

     __
     ||  a, b
     ▼|
––►((Q0))

Q0 is both initial and final state

Language accepted by this DFA is superset of language $L = \{ a^nb^n$ | $n > 0  \}$  and hance also accepts all strings in $L$.

The concept you are missing is:
 "An automata $A$ for some language $L$ must accept $\textit{exactly}$  language $L$, neither a subset nor a superset of $L$".

Hance DFA above is not a finite representation of language $L = \{ a^nb^n$ | $n > 0 \}$.

  $Doubt-2$:  "Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states".

Note: To construct new complement DFA $D$, old-DFA $A$ must be a complete, means there should all possible outgoing edge from each state (or in other words δ should be a complete function).
Read "Complement DFA for Regular Expression $(00 + 1)^*$" to learn how to consturct complement DFA.

  $Doubt-3$:   But if you had the language $L = \{ a \}$, over the alphabet $\{ a, b \}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\{ a, b \}^* - \{ a \}$, which includes $\{ ab, aabb, aaabbb, \ldots \}$.

As you already know complement of a regular language is regular (DFA exists for regular language and you know how to make DFA for complement regular language), so new language $L^" $ = $\{ a, b \}^* - \{ a \}$ is a regular language.

And language $L^" $  is a superset of language $\{ a^nb^n$ | $n > 0 \}$.

The concept you are missing is that you don't know:

  $Doubt-4$:   "What is called regular language?" And Why a languages like $(a + b)^*$  is regular? But language $\{ a^nb^n$ | $n > 0 \}$ is not a regular language**

A language (a set) $L$ is called Regular Language, if its require bounded (finite) amount of information at any instance of time while processing a strings in language $L$.

What is bounded information?
For example: Consider a fan switch for on-off. By viewing fan-switch we can say whether fan is in on or off state (this is bounded or limited information).
But we can not know that how many times a fan has been on-off in past! (to memorized, it requires a mechanism to store unbounded amount of information to count how many times  – e.g. some kind of meters, we have in our car/bike).

To understand how states are uses as memory element read this answer, you may also like to read: How to write regular expression for a DFA

Language $\{ a^nb^n$ | $n > 0 \}$ is not a regular because here $n$ is unbounded. To verify string in language $a^nb^n$ we have to remember how many '$a$' has been came and this required a infinite memory to count because number of '$a$' s in string that can be infinity large.
(hence an automata can only capable to process strings of $a^nb^n$ if it has infinite memory e.g PDA).

Whereas $(a + b)^*$ is of-course a regular by its nature, because there is bounded restriction that "string consists of only symbol '$a$' and '$b$'".
 And strings of this language can be easily processed (or recognized) by an automata in which we have finite memory that is finite automata. Yes, in finite automata we have finite memory in terms of states (The word "Finite" significance of the presence of 'finite amount of memory' in the form of finite number of states $Q$).

Summarize:

Memory in finite automata is present in the form of states $Q$ only and according to automata principal: any automata can have only finite set of states. hence finite automata has finite memory, this is the reason automata for regular language is called finite automata. You can think a finite automata like CPU without memory, that has finite  register to remember its internal states.

Finite State  –► Finite Memory  –► Only language can be process for which finite memory need to store at any instance of time while processing the string: –► that language is called Regular Language

Absence of external memory is limitation of finite automate  –► or we can say limitation of class of language defined by finite automata that is called Regular language.

Side note::
*   Also a language { anbn | 10>100 n > 0 } is regular, a large set but regular because $n$ is bounded, hence finite automata and regular expression is possible for this language  – finite set is always regular.
*  There are infinite sets those are regular. Regular language of subset of all possible infinite set. Check this Venn-diagram.

So, if any time you need to proof that a language $L$ not a regular – before the go to use "formal tools" likes pumping lemma, first try to proof using fundamental definition of regular language.


How much does C# gain from its value types C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to make small objects more cache friendly, that is, for efficiency reasons.

my question is;

is there any study on how much efficiency gain does C# make by this design choice, based on evaluating real world projects.
Assuming the answer to the first question is that there is a measurable efficiency gap, will things change when JIT compilers come into play?

Swift does the same thing (having both value types and reference types). I'm sure there are efficiency studies, performed by the people implementing the Swift compiler.

But the difference between reference types and value types goes a lot deeper. What you need to look at is things like mutability, semantics when passing parameters, and so on. I don't choose reference vs. value types for micro efficiencies, but for the semantics.

So your assumption "the design decision is mainly to make small objects more cache friendly", is firstly wrong, and secondly I strongly doubt it makes things more cache friendly.


Is maximum edge-weighted triangle-free graph NP-hard? Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$.

Is this problem NP-hard? I thought I saw some mention or folk-theorems that it was, but I can't find anything. There is a similar problem which is known to be NP-hard:

Given a graph $G$ with weights $w_v$ on the vertices, choose a subset $S$ of the ''vertices'' such that the induced subgraph $G_S$ doesn't contain any 3-cycles, maximizing $\sum_{v\in S} w_v$.

There are many sources online talking about how MAX-IND-SET can be reduced to this. It's not immediately obvious to me if this generalizes to the above, though. The closest thing I did find was https://www.sciencedirect.com/science/article/pii/S0166218X14002182 which mentions that finding maximum-cardinality triangle-free 2-matchings (so that $S$ has max degree 2) is easy, and it seemed to suggest that it would work for the weighted version as well, although I didn't quite follow it all the way through.

Anyone have a reference for this, or want to provide a reduction? :)

The problem is $NP$-complete even in the unweighted case (e.g.: all edge weights are equal to $1$). Instead of looking for a maximum edge-induced, triangle-free subgraph we may equivalently consider the minimum number of edges to delete from the original graph in order to leave a triangle-free graph. This problem (and other, related problems) are demonstrated to be $NP$-complete in [1]:

If $\pi $ is a property on graphs or digraphs, the edge-deletion problem can be stated as follows: find the minimum number of edges whose deletion results in a subgraph (or subdigraph) satisfying property $\pi $. Several well-studied graph problems can be formulated as edge-deletion problems.
In this paper we show that the edge-deletion problem is NP-complete for the following properties: (1) without cycles of specified length l, or of any length $ \leqq l$, (2) connected and degree-constrained, (3) outerplanar, (4) transitive digraph, (5) line-invertible, (6) bipartite, (7) transitively orientable. For problems (5), (6), (7) we determine the best possible bounds on the node-degrees for which the problems remain NP-complete.

Yannakakis, Mihalis. "Edge-deletion problems." SIAM Journal on Computing 10.2 (1981): 297-309.


Mapping categorical data in K-nearest neighbour I have a data set which contains categorical data, for example:

+-----+-----+------+
| age | sex | grade|
+-----+-----+------+
| 18  |  M  |  59  |
+-----+-----+------+
| 19  |  F  |  16  |
+-----+-----+------+

How can i map the sex column to numerical data? generally how can i do map categorical data to numerical data in KNN? Is this a good idea to do this mapping?

You can map M to 0 and F to 1.  In general, if you have N categories, you can map each category to a number in the range 1,2,..,N.  If N=2, this is fine for a k-nearest neighbor classifier.

If N>2, this is not a good idea for a k-nearest neighbor classifier, as it makes some assumptions (e.g., that the first category is more similar to the second category than the third).  If you want to use a k-nearest neighbor classifier and you have no knowledge about the meanings of the categories, the best you can do is to use a one-hot encoding.  If you do have some knowledge about the meanings of the categories, the best you can do is to define a distance function or similarity function between categories, and use that directly (instead of mapping the categories to numbers).


Constructing a context-free grammar I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, the terminals are $a,b,c$, the start symbol is $S$, and the productions are
\begin{align}
&S \to aYS \mid cXc \mid bXS \mid cYc \mid \varepsilon \\
&X \to a \mid bXX \\
&Y \to b \mid aYY \\
\end{align}

Your grammar doesn't seem to generate $caac$. Indeed, in order to generate this work, a simple case analysis shows that the derivation must start
$$ S \to cYc \to caYYc, $$
at which point it is clear that we cannot generate $caac$.
I assume you know how to generate the language $c\Sigma^*c$, as well as the language of all words with an equal number of $a$-s and $b$-s. Instead of combining them in a complicated way, write grammars for both, and then join them together using a rule of the sort $S \to S_1 \cup S_2$.


Tight instance for unweighted maximum coverage problem? The maximum (unweighted) coverage problem is defined as follows:

Instance: A number $k$ and a collection of sets $S = \{S_1, S_2, \ldots, S_m\}$.
Objective: Find a subset $S^{'} \subseteq S$ of sets, such that $\left| S^{'} \right| \leq k$ and the number of covered elements $\left| \bigcup_{S_i \in S^{'}}{S_i} \right|$ is maximized.

This problem is NP-hard. I am trying to find a counterexample when the greedy algorithm fails but I failed. Especially, can you find a family of instances when the greedy algorithm always fails? (Or at least one simple instance?)

The greedy algorithm:
at each stage, choose a set which contains the largest number of uncovered elements.

I found a family of instances here but it was for the weighted case and I cannot transform it to the unweighted case.

Here is one example:
take the universe   $$U=\{u_1,\dots,u_n,v_1,\dots,v_n\}$$
$S_i=\{u_i,v_i\}$ for $i=1,\dots,n$ , and  $S_{n+1}=\{u_1,\dots,u_n\}$, $m=n+1$, $k=n$


Cross Edge and Back Edge when doing BFS I was asking to prove that

  For any directed graph, when we perform BFS, for each cross edge $(u,v)$,
  there is some time when both vertices $u$ and $v$ appear in the queue.
  (In other words, we have a queue like this: $Q = \langle v_1,v_2,..u,..,v,..v_k \rangle$.)

However, when I draw some graph; I've encountered this example

If we perform BFS starts from $a$, then what is the edge of $(f,c)$? clearly, if what I was about to prove is correct, $f$ and $c$ will never appear in the queue at same time during the whole execution of BFS. So $(f,c)$ is not cross edge. Then what edge is this ? It can't be back edge; since $c.parent$ is $a$, and $f.parent$ is $e$. they aren't tree edge, nor forward edge.

So what I am asked to prove is not correct?

So I guess that the statement only holds for undirected graph?

Your statement for directed graphs is not true. Your graph in the OP is a counterexample. However, for undirected graphs it is true since if $(a,b)$ is a cross edge then the depth-difference between the vertices is at most 1, i.e. $depth(a) = depth(b)$ or $depth(a)+1 = depth(b)$. Using this fact, which is proved below, you can prove your statement.

Assume that at some point you have the following queue configuration:
$$v_1, v_2,\dots, v_k,a,\dots, u_1,\dots u_m \text{ (leftmost leaves first)}$$
where $v_i$s and $a$ have the depth $d$ and $u_i$s have the depth greater than $d$. Since $(a,b)$ is a cross edge, $a$ and $b$ belong to different ancestral trees, i.e., one of the $v_i$s is an ancestor of $b$ i.e, $b$ must be discovered before we reach $a$. If their depth values are equal then $b$ has already been reached (discovered) and so they must be at the same time in the queue. Otherwise, their depth values differ by 1 and so $b$'s ancestor (parent) must be one of the $v_i$, say $v'$. This $v'$ is popped and extended before we reach $a$ and since $b$ is a descendant of $v'$, $b$ is pushed into the queue before $a$ is removed.

Thus in both cases $a$ and $b$ appear in the queue for some time during the execution of BFS.

Claim: In a breadth-first search of an undirected graph for each cross edge $(a,b)$ $$0 \leq depth(b)-depth(a) \leq 1$$
Proof: Assume that $depth(b)-depth(a) > 1$. Then $depth(b)$ is at least $depth(a) + 2$. But $(a,b) \in E$ (a cross-edge) and hence $depth(b) = depth(a)+1$, a contradiction (see the following figure).


When is an ATM network connection superior to an IP connection? Currently learning about Networks in Computer Science, and I don't understand why you would ever use an ATM (asynchronous transfer mode)  network instead of IP, as IP doesn't have to be as reliable and can be set up much more quickly, and is what the entire Internet basically uses.

AFAIR ATM was specifically designed to also transfer real time data like voice. This requires guaranteed properties like bandwidth and latency.

IP can't give those guarantees as it looses packets and reorders packets.

Also ATM is connection oriented, whereas IP needs the complexity of TCP to get that.


Is there an algorithm which can compute every algorithm's time complexity? I think of an algorithm which computes the time complexity. It would be great if a code editor could compute the time complexity of the selected lines and even compare two pieces of codes in order to help developer to select one of them. I heard something related with halting problem but couldn't figure out.

It would be great, wouldn't it?
And like most problems regarding Turing Machines (or "algorithms"), there is no such algorithm, and there never will be:

Consider for example the language
$$\{M: M\text{ is a TM that runs in time }O(n^3)\}$$
It is quite easy to reduce the halting problem to this language. Indeed, given input $M,w$ for the halting problem, the reduction outputs a machine $K$ that given input $x$, runs $M$ on $w$, and accepts $x$ iff $M$ halts on $w$, and does not halt otherwise. Since running $M$ on $w$ takes constant time (if it halts at all), then $K$ runs in time $O(n^3)$ iff $M$ halts on $w$.

Thus, it is undecidable (not in $coRE$, to be exact).
There is nothing special about $n^3$, the same reduction works easily for every function greater than $n\log n$ (below $n\log n$ things get a bit more involved).

Also, the Halting problem itself can be regarded as a sort of "run-time problem", in the sense that you don't even ask what the runtime of an algorithm is, but just whether it halts. Even that is undecidable.

It is interesting to note that the language, as formulated in this answer, is also not in $RE$, it is an easy exercise to show it. However, if you replace the $O(n^3)$ with exactly $n^3$, then the problem is in $coRE$. Then, the former reduction needs certain adjustments, but the problem is still undecidable.


What is $R_\min$ in this formulat for optimal buffer size? I read a question from my recitation about optimal buffer size. As solution there is a furmula for calculating the optimal buffer size; I'm not sure about one of its parameters. The formula is

$\quad \operatorname{Buffer}_{\text{optimal}} =  \frac{\operatorname{Buffer}_{\text{current}}}{1-\frac{R_{\text{app}}}{R_{\min}}}$

Where

$\operatorname{Buffer}_{\text{optimal}}$ is the optimal buffer size we want to calculate.
$\operatorname{Buffer}_{\text{current}}$ is the current buffer size.
$R_{\text{app}}$ is the rate the application reads data from the buffer at.
$R_{\min}$ -- this is the one I'm not sure about.

The example problem is this:

  Alice connects to web server and downloads a file of 12KB size from
  the server. There is a router between them. The transmission rate
  between Alice and router is 400,000B/s and the transmission rate between
  router and server is 1MB/s. Buffer size in the router is 4KB, and buffer
  size in Alice is 3KB. The rate the application reads from Alice buffer with
  is 100KBps.

  Calculate the optimal buffer size for Alice as a fuction of router buffer
  size and free space at the buffer.

So as described in the solution, according to the above formula the solution is

$\qquad \operatorname{Buffer}_{\text{optimal}} = \frac{3*10^3}{1-\frac{10^5}{4*10^5}}$

So what $ R_{\min} $ could be  ?

$R_{min}$ is the "Writing Rate in Application Buffer" (from router in your example).

This formula makes sense for different conditions like $R_{app}=R_{min}$. In this case the buffer size should be infinite (very large buffer) and it is intuitively correct. $R_{app} >R_{min}$ makes the size negative which shows that buffering does not help while the reading data is very faster than buffering data in user side.


Precise relation between complexity classes(focus on P, NP and EXPTIME) I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes.

What I know so far:

$P \subseteq EXP$ (from Time Hierarchy Theorem [1])
We don't know an exact relation between $P$ and $NP$, and between $NP$ and $EXPTIME$. What do we know:

2.1 $\forall problem \in P \Rightarrow problem \in NP$ (Any problem in $P$ is in $NP$.)

2.2 $\forall problem \in P \Rightarrow problem \in EXPTIME$ (Any problem in $P$ is in $EXPTIME$.)
In $P$ vs $NP$:

3.1 We haven't found an $ NP $ $complete$  $problem $ that we can solve in polynomial time (this would imply $P = NP$)

3.2 We haven't found a proof that states that we can't find an polynomial (running time) algorithm for an $NP$ $complete$ $problem$ (this would imply $P \neq NP$)

3.3 From 3.1 and 3.2 we can't state anything about the cardinality of $NP-P$. Most of scientists belive that $P \neq NP$ so there are $NP$ problems that we can't solve in polynomial time.

First, if you find and "hole" in what is stated above, please correct me.

Now for my questions:

A. What can we say about $NP$ vs $EXPTIME$? Are there $EXPTIME$ $complete$ problems not in $NP$? For me it sounds like the $P$ vs $NP$ problem just one "level" (in the hierarchy) higher.

B. How does one go about finding a proof like in 3.2? Obviously we haven't found such a proof but I am looking to understand. The first idea that comes to mind is to go with a proof by contradiction. Not finding such a proof doesn't say much (maybe we are not "smart" enough). What else could we try? The problem reduces, in my opinion, to proving that an algorithm in "elegant" (in running time; that means that it is "the fastests")

Kind of bonus question:

C. How does this relate to Godel's incompleteness theorem? Maybe the better question (quite outside of the scope of the original question) is how much of the math we use on answering these questions can be considered a formal system(so we can apply Godel's result)? What parts are not "formal"?

D. I wasn't able (yet) to look very far into [1]. If possible, can someone give me an informal insight on how it handles defining a strict lower (time) bound for a certain problem?

[1]https://en.wikipedia.org/wiki/Time_hierarchy_theorem

The Wikipedia page on EXPTIME summarizes all the known relationships:

$\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}$.
$\mathsf{P} \subsetneq \mathsf{EXPTIME}$ due to the time hierarchy theorem.

You can find more information on the time hierarchy theorem in Wikipedia, in textbooks, and in online lecture notes. It is a very standard topic.

The P vs NP question is about the first two levels of the polynomial hierarchy. It is conjectured that all levels are distinct and different from $\mathsf{PSPACE}$, which is an upper bound on the hierarchy; and that $\mathsf{PSPACE}$ is distinct from $\mathsf{EXPTIME}$ (it is known that $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$).

The proof of the time hierarchy theorem uses diagonalization in a straightforward manner (at least conceptually), and in this regard it is part of a line of results that includes Gödel's (first) incompleteness theorem and Turing's undecidability of the halting problem. In fact, it is a time-bounded version of the latter.

Finally, while some people have some ideas on how to prove $\mathsf{P} \neq \mathsf{NP}$, we mostly know a few general methods which cannot prove $\mathsf{P} = \mathsf{NP}$. These are known as barriers, and include diagonalization (used to prove the time hierarchy theorem), natural proofs (used to prove lower bounds in circuit complexity), and arithmetization (used to prove $\mathsf{IP}=\mathsf{PSPACE}$). The Wikipedia article about the P vs NP problem has a nice summary about these barriers.


Evolutionary algorithm - is there a relation between minimum iterations and size of decision variables I am solving an optimization problem using SPEA2, my problem has three cases with decision variables 25, 50 and 100 in each case. I want to ask if there is some relationship between the number of variables and iterations of evolution process. I mean to say I run algorithm fewer times when decision variables are 25 than once they are 50. Thanks in advance.

As a very general heuristic, it's likely true that bigger problems are harder than smaller ones and benefit from more searching. Bigger populations, longer runs, etc. can be beneficial in that case.

The real question is whether your algorithm is converging or not. If you're converging before you find a good answer, more generations isn't going to help.


Single Cycle Data-path Requirements How does having separate instruction and data memories help in implementing a single cycle datapath for a MIPS instruction set? I want to know why we can only use a datapath element once in a cycle for making the datapath capable of executing any instruction in a single cycle.

Each element in that data path is purely logical, thus in each cycle an element can perform only a single operation.
If you had only one memory element, you would've possibly need to perform two operations in one cycle: (1) read the instruction (2) read/write data. This is impossible with a logic-only (sateless) elements within a single cycle.


Multi objective optimization using genetic algorithm I have an objective function profit = income - expense . I want to solve it using genetic/evolutionary algorithm (strength pareto SPEA2). Since the algorithm is multi-objective so can I consider the income maximization as one objective and expense minimization as second objective?. I am using SPEA2 matlab code from YARPIZ. I am not sure whether this approach of breaking objective function is technically correct. Secondly, please also throw some light on how to do both conflicting objective simultaneously. The code in link is written for minimization of objective functions, but I have to minimize one and maximize other objective.

Just define profit as a variable and maximize porfit as your singular objective. In general the objective will depent on multiple variables indirectly and the variables will usually also depend on each other. If this is not the case there are probably much more effective solutions than genetic algorithms.


Simple cycles of length two in an undirected graph Pedagogical question.

Background

A cycle in a graph can be defined as a sequence of vertices $v_1,\dots,v_n$ with $v_1=v_n$ such that, for each $i \in \{1,\dots,n-1\}$, the graph has an edge $(v_i,v_{i+1})$. (One can define it differently.)

The point

Every definition of simple cycle I have seen is: a cycle with no repeated vertices, except the first and last.

But this definition implies that even in undirected graphs, we can have simple cycles of length two, e.g. $u \to v \to u$. However, we probably do not want to consider this a simple cycle because it re-uses the edge $(u,v)$ and this would break several algorithms and proofs.

Of course for cycles of length $3$ or more, requiring no repeated vertices implies there are no repeated edges.

The question

Which of the following is right? Justify your answer.

(1) The standard definitions are incorrect, they ought to explicitly exclude simple cycles of length 2 in undirected graphs.

(2) The standard definitions are correct, the cycle of length 2 is simple.

(3) This question is wrong in claiming this is the standard definition of simple cycle. There are other better definitions that are standard (references please!).

It turns out that the very popular textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, sneakily avoids this issue by giving a different definition of cycle in undirected vs directed graphs.

In Section B.4, it defines cycle and simple cycle as I do (they also require at least one edge), in directed graphs. In an undirected graph, they define cycle the same way except they require that all of the edges in the cycle be distinct; and they say the cycle is simple if in addition the vertices are distinct, other than $v_1=v_k$.


How to propose a method to construct an automaton? Given $0 \leq m < k$ and $p \geq 2$ it's defined $$A_{k,m,p} = \{ \alpha \in  \{0,1,\dots,p-1\}^* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \}$$

It is needed to give a general method to construct an automaton which accepts this language. I'm trutly lost about the procedure in this. Any hint would be helpful.

Some observations about this: The automaton is not specified (i.e. could be NFA or DFA) and the numbers are static.

Your automaton will have $k$ states, one for each possible value of $m$, i.e., one for each of the congruence $(\text{mod } k)$ classes. Exactly one of these states will be marked as the final state, because that will be the one that accepts ocurrences of $\alpha$ that are compatible with $x ( \text{mod } k) =m$.

The transition function will connect states representing congruence classes for $m=a$ and $m=b$ by an arrow labeled with a symbol denoting $c$, if and only if $(a.p +c)\text{ mod } k = b$.

The initial state will be the one corresponding to $m = 0$, assuming leading zeros are allowed.


Correct application of the CFL Pumping Lemma I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable by the separate pumping lemma for linear languages (as given in Linz's book), but my question is different.
Evidently this is a CFL, and a pushdown automaton can be constructed for it. But if I apply the pumping lemma for CFLs, I find that I'm able to pump strings that don't belong to the language, which would mean that the language is not a CFL. Clearly I'm doing something wrong.
Going by the "game-like" format given in Linz, say you pick $w = a^mb^mc^{2m}$, $|w| \ge m$. The adversary can choose a number of decompositions $w = uvxyz$, they can look like -:

$v = a^k, y = a^l$: The case where $|vxy|$ is contained within the $a$'s of the string. Pump $i = 0$, and then $w_0 = a^{m – (k + l)}b^mc^{2m}$ cannot be in the language since the equality no longer holds.
$v = a^k, y = b^l$: The case where $v$ is in the $a$ section, $x$ spans across the $a$'s and $b$'s, and $y$ is in the $b$ section. Again, pump $i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ cannot be in the language.

There are more cases like these. Where am I going wrong in the application of the CFL PL?

The pumping lemma for CFL states that if $L$ is a CFL, there exists a constant $N \ge 1$ such that for all $\omega \in L$ with $\lvert \omega \rvert \ge N$ there is a division $\sigma = u v w x y$ with $\lvert v w x \rvert \le N$ and $v x \ne \varepsilon$ such that $u v^k w x^k y \in L$ for all $k \ge 0$.
(The pumping lemma for regular languages is similar, the discussion below applies with minor changes).
You want to prove by contradiction that $L$ is not a CFL. So you assume $L$ is a CFL, and get a contradiction to the lemma. This means, in detail:

As $L$ is a CFL, it satisfies the lemma. In particular, there is a constant $N$ such that...
As the lemma states all long strings in $L$ can be divided, you are free to pick one that is easy to work with.
The lemma states there is some division of $\omega$ such that.... for all $k \ge 0$...; to contradict the lemma you have to prove no division works. In practice, you take a given division of your $\omega$ (any division) and for it pick some $k$ for it that doesn't give a string in the language. You might need to divide this into cases.

What happens for strings that don't belong to the language, or are shorter than $N$, is completely irrelevant. It might be that some strings can be pumped, that some values of $k$ work for all strings, ... What is crucial is that for one string $\omega$ (the one you picked) no division works with one value of $k$ (again, the one you picked). As the lemma asserts it works for all long enough strings, with some division for all $k$, one counterexample is enough. Infinite examples prove nothing.


Hashing Probabilities I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a simple uniform hash, what is the expected number of buckets that have exactly 1 item? What is the expected number of buckets with at least 2 items? What is the expected number of buckets with exactly k items?", so will appreciate any help with respect to hashing probabilities.

For sufficiently large $M$, the size distribution of hash slots with good uniform hash functions follows a Poisson distribution.

Let $\lambda = \frac{N}{M}$ be the load factor. Then the expected proportion of buckets with exactly $k$ items in it is:

$$P(\hbox{# of items in the bucket is } k) = \frac{e^{-\lambda} \lambda^k}{k!}$$


Why the negative reward function in linear quadratic regulation encourage to be at original state? I was reading Stanford's CS 229 materials on Linear Quadratic Regulation ( Lecture note 13, youtube Lecture 18, around time 36 min).
And it mentions that:

" the quadratic formulation of the reward is equivalent to saying that we want our state to be close to the origin.For example, if $U_t = I_n $(the identity matrix) and $W_t = I_d$, then
$R_t = -\Vert(s_t)\Vert^2-\Vert(a_t)\Vert^2$, meaning that we want to take smooth actions (small norm of $a_t$) to go back to the origin (small norm of $s_t$)."

but why is that? Why the norm of the origin is smaller? $s_t$ for any time point are just a vector of n dimension which can take any value, right?

Minimizing $s^TUs=s^Ts=\|s\|^2$ minimizes the distance from the origin, because the norm of a vector is its Euclidean distance (https://en.wikipedia.org/wiki/Euclidean_distance) from the origin:

$$\|s\|= \sqrt{s_1^2+s_2^2+\dots+s_n^2} = \sqrt{(s_1-0)^2+(s_2-0)^2+\dots+(s_n-0)^2}$$


Verify the type of a lambda expression I need to verify the type for the lambda expression: $\lambda f.\lambda x.f (f x)$

My method gives me: $(a\rightarrow c)\rightarrow b\rightarrow c$

Im trying to define it in Haskell (on Hugs) like this:

h= \f x -> f (f x)

When i call the :type comamnd it gives me:

(a -> a) -> a -> a

Is mi function correctly defined in Haskell?, or my method gives me a wrong result?

Haskell is right.

I do not know whether your Haskell syntax is correct, though it looks plausible to me, but the Haskell typing is the right one.

Since $f$ is applied to the result of $f(x)$, $f$ must be of type $a\rightarrow a$,
$a$ being the type of $x$.


Why product type is a dependent SUM? It might just be a stupid question but I simply see no obvious reason why dependent sum type is a generalized form of product type. Concretely, the sigma type $\Sigma(x:S)T$ degenerates to a product type if $T$ does not depend on $x$ and is expressed to be $S\times T$ in this case.

Where the SUM part in dependent sum type is coming from? Also, the type of dependent functions is called dependent PRODUCT type. Might I ask why it's called product type as well? I kind of sense that it has something to do with algebraic data type but I can't get through it.

Let's do products first.
The usual cartesian product $A \times B$ is also called a binary product because we are making a product of two sets. We could make a ternary product $A \times B \times C$. What is the most general case? Well, to have an index set $I$ and a family of sets $X_i$, one for each $i \in I$, and then we make the product of all these $X_i$'s. This is written as $\prod_{i \in I} X_i$. When $I$ is infinite, it is called an infinitary product. Other products are a special case, for example if we take $I = \{1, 2\}$, $X_1 = A$ and $X_2 = B$ then $\prod_{i \in \{1,2\}} X_i = A \times B$, so a binary product is a special case of the general product.
We can do the previous paragraph in type theory, as there is nothing specific to sets there. Given a type family $i : I \vdash X(i) \ \mathsf{type}$, we may form the type $\prod (i : I) X(i)$. To get a binary product $A \times B$ as a special case, take $I = \mathsf{Bool}$, set $X(\mathsf{false}) = A$ and $X(\mathsf{true}) = B$.
Now let's try sums. I will assume you understand the sum of two sets or types, $A + B$. We could have a ternary sum, $A + B + C$. Again, there is a general case: take a family of sets $(X_i)_{i \in I}$ and form their sum. In set theory it is written as $\coprod_{i \in I} X_i$ and called coproduct, while in type theory it is written as $\sum (i : I) X(i)$ and called dependent sum. One way to see why people call it a sum is to consider how many elements it has. If $A$ has $a$ elements and $B$ has $b$ elements, then $A + B$ has $a + b$ elements. In general, if $X_i$ has $x_i$ elements, then $\sum (i : I) X_i$ has $\sum_i x_i$ elements.
We saw that the binary product is a special case of a general product. But it is also a special case of a dependent sum. Suppose $A = \{0, 1, 2\}$. Then $A \times B = B + B + B$. In general, if we want $A$-many copies of $B$, then that's
$$A \times B = \underbrace{B + B + \cdots + B}_{A}$$
Of course, such notation is silly, so we prefer to take $I = A$ and $X_i = B$ and then the same thing is written as
$$A \times B = \sum_{i \in I} X_i$$
or to confuse beginners
$$A \times B = \sum_{a \in A} B.$$
This just says that $A$ times $B$ is the same thing as adding $A$-many $B$'s together. It's the first thing we're told about multiplication, except that here it's about sets, not numbers (but that's irrelevant, really).


When are two simulations not a bisimulation? Given a labelled transition system $(S,\Lambda,\to)$, where $S$ is a set of states, $\Lambda$ is a set of labels, and $\to\subseteq S\times\Lambda\times S$ is a ternary relation. As usual, write $p \stackrel\alpha\rightarrow q$ for $(p,\alpha,q)\in\to$. The labelled transition $p\stackrel\alpha\to q$ denotes that the system in state $p$ changes state to $q$ with label $\alpha$, meaning that $\alpha$ is some observable action that causes the state change.

Now a  relation $R \subseteq S \times S$ is a called a simulation iff
$$ \forall (p,q)\in R,
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R.
$$

One LTS is said to simulate another if there exists a simulation relation between them.

Similarly, a relation $R \subseteq S \times S$ is a bisimulation iff $\forall (p,q)\in R,$
$$
\begin{array}{l}
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R
\text{ and } \\
\text{ if } q \stackrel\alpha\rightarrow q'
   \text{ then } \exists p', \;
   p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R.
\end{array}
$$

Two LTSs are said to be bisimilar iff there exists a bisimulation between their state spaces.

Clearly these two notions are quite related, but they are not the same.

  Under what conditions is it the case that an LTS simulates another and vice versa, but that the two LTSs are not bisimilar?

Because a CCS process is worth a thousand pixels – and it is easy to see the underlying LTS – here are two processes that simulates each other but are not bisimilar:

$$P = ab + a$$
$$Q = ab$$

$\mathcal{R_1}=\{(ab+a, ab), (b, b), (0,b), (0, 0)\}$ is a simulation.

$\mathcal{R_2}=\{(ab, ab+a), (b, b), (0,0)\}$ is a simulation.

$P\ \mathcal R_1\ Q$ and $Q\ \mathcal R_2\ P$ but $P$ and $Q$ are not bisimilar. Why not? Because $P\stackrel{a}→0$ and the only $Q'$ such that $Q\stackrel{a}→Q'$ is $b$ ... and $0$ is not bisimilar to $b$.

Why can they simulate each other, then? Because $P$ simulates $Q$ since it can do everything $Q$ does. And $Q$ simulates $P$ because even if $P$ can go in one $a$-step to a program that does nothing, $Q$ can still do that $a$-step, and that's all it takes to simulate something. The key difference with the bisimulation is really that, as Charles said, you have to relate the same processes with both simulations. (i.e. $\mathcal R$ such that both $\mathcal R$ and $\mathcal R^{-1}$ are simulations)


Shortest distance from multiple points to one point I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the end node $v$. I want the shortest $d$ to $v$.

This is quite straightforward

Reverse the direction of each edge.
Apply single source shortest path algorithm with destination as the source.
Reverse the direction again. (Optional, only if you want to preserve the originality of graph)

Time Complexity-
With graph given as adjacency list, it takes $O(E+V)$ to reverse the directions of each edge. With graph given as adjacency matrix, it takes $\theta(V^2)$. Rest you can apply any single source shortest path algorithm like Dijkshtra.

Note that a graph with reverse edges of original one typically called as transpose of the original graph.


Classification problem where one attribute is a vector Hello I am a layman trying to analyze game data from League of Legends, specifically looking at predicting the win rate for a given champion given an item build.
Outline
A player can own up to 6 items at the end of a game. They could have purchased these items in different orders or adjusted their inventory position during the course of the game.
In this fashion the dataset may contain the following rows with:
   champion id   |                 items ids               | win(1)/loss(0)
----------------------------------------------------------------------------
       45        |   [3089, 3135, 3151, 3157, 3165, 3285]  |       1
       45        |   [3151, 3285, 3135, 3089, 3157, 3165]  |       1
       45        |   [3165, 3285, 3089, 3135, 3157, 3151]  |       0

While the items are in a different order the build is the same, my initial thought would be to simply multiply the item ids as this would give me an integer value representing that combination of 6 items.
While there are hundreds of items, in reality a champion draws off a small subset (~20) of those to form the core (3 items) of their build. A game may also finish before players have had time to purchase 6 items:
                items ids
------------------------------------------
   [3089, XXXX, 3151, 3285, 3165, 0000]
   [XXXX, 3285, XXXX, 3165, 3151, 0000]
   [3165, 3285, 3089, XXXX, 0000, 0000]

XXXX item from outside core subset
0000 empty inventory slot

As item 3089 compliments champion 45 core builds that have item 3089 have a higher win rate than core builds which are missing item 3089.
The size of the data set available for each champion varies between 10000 and 100000. The mean is probably around 35000.
Questions

Is this a suitable problem for supervised classification?
How should I approach finding groups of core items and their win rates?

Yes.  If you have a non-trivial data set of this form, this would be a reasonable fit for statistical analysis.

For independent variables, you have one binary feature for each core item (indicating whether that item was purchased or not); the outcome is a binary variable (win or loss).  Accordingly, one reasonable approach would be to try logistic regression.  You'll have one independent variable $X_i$ for each item; $X_i=1$ means that item $i$ is one of the 6 items that the champion purchased in this game, $X_i=0$ means item $i$ was not purchased.  You'll have a dependent variable $Y$; $Y=1$ means that the champion won this game, $Y=0$ means the champion lost.  Then logistic regression will tell you which items tend to be associated with winning games.

There are other methods you could try as well: pretty much any method for supervised classification that works well with binary/categorical variables.

The one thing I don't recommend you do is multiply the item codes.  That's not going to help.  Instead, just have 20 features, where each feature indicates whether a particular item was purchased or wasn't.


Big O order of a function I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function () = ^2 +  log2() + log2(). Show your working.

My answer is O(n^2) because it's the term with the highest degree. However, I'm not really sure how to show it. Am I right by saying that it has to be proven like this -> f(n) is an element of O(n^2). So far, I've only done questions like n^2 + 2n + 1 and I have to find c and k values. I'm not quite sure how to do this one. Can anyone help me out, please?

Thanks

You need to show that there is an index $n_0\geq 0$ and some $c>0$ such that $f(n) \leq c\cdot n^2$, for all $n\geq n_0$. Here you can take $c=2$.

This leaves you with showing that $n \log_2(n) + log_2(n) \leq n^2$, for high enough values of $n$.

This holds because $\lim_{n\to\infty}\frac{log_2(n)}{n} = 0$.


XOR Statement in integer programming How can I convert a XOR statement into linear constraints for integer programming ?
The expression is $(x_1 \geq 1)$ XOR $(x_2 \geq 1)$ where $x_1$ and $x_2$ are integer. It means that if $x_1 \geq 1$ then $x_2 = 0$ and vice versa.
I started to linearize the statement by :
$(x_1 \geq 1)$ XOR $(x_2 \geq 1) = (x_1 \geq 1 \quad and \quad x_2 \leq 0) or (x_1 \leq 0 \quad and \quad x_2 \geq 1)$ but I don't know how to continue, I would like to follow the Big M mothod but I'm going around in circles...
I need it to resolve this kind of linear program where if $x_1\geq 0$ then $x_2=0$ and vice versa :
\begin{equation}
\begin{aligned}
\min \quad & a_1x_1 + a_2x_2 + a_3x_3\\
\textrm{s.t.} \quad & x_1 + x_2 + x_3 = 200\\
  &x_1 \leq 100\\
  &x_2 \leq 100\\
  &x_3 \leq 100\\
  &x_1 \geq 1 \quad xor \quad x_2 \geq 1 \\
  &x_i \in N, \quad i \in \{1, 2, 3 \}   \\
  &a_i \in R, \quad i \in \{1, 2, 3 \}   \\
\end{aligned}
\end{equation}
Thanks a lot ! :)

For binary variables you could just write $x_1 = 1 - x_2$, but I see that in your case $x_1,x_2 \in \{1,2,3\}$. You can still use the same trick once you force a boolean variable $y_i$ to be 1 if and only if $x_i \ge 1$:
$$
\begin{align*}
3 y_1 &\ge x_1 \\
y_1 &\le x_1 \\[6pt]
3 y_2 &\ge x_2 \\
y_2 &\le x_2 \\[6pt]
y_1 &= 1-y_2 \\[6pt]
y_1, y_2 &\in \{0,1\}
\end{align*}
$$


Gödelization in Turing Machine I was looking at Gödelization in Theory of Computation course. I could understand the Gödel numbering concepts, but couldn't understand its importance in Theory of Computation. Could anyone please point to some good materials or point out its importance.

Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the significance of this should be obvious if I can convince you that this really is so.

Before modern computers came into existence, people made single-purpose computing devices (I am telling you a story, not a history), for example someone made a machine for calculating $arctan$, and someone else made a machine for calculating the Bessel function. Turing's original insight was that we only had to build one machine (the universal one), which took as input the description of any machine and simulated it. But what is a "description of a machine"? An engineer might think of circuit designs and assembly instructions. But that is very complicated and not easily presented to a machine. And perhaps ever more complicated machines require ever more complicated descriptions?

We need a way of describing machines that is as simple as possible. Here Gödel's idea was important: he showed some years before Turing that all sorts of things in logic (formulas, proofs) could be encoded with numbers, and then manipulated within arithmetic. We can do a similar trick with Turing machines: encode the program, the current state, and the contents of the tape used so far, with a string of symbols on a tape (for examples $0$'s and $1$'s), and then manipulate the string with a Turing machine.

In practice we do not write down sequences of $0$'s and $1$'s when we program. We use another layer of encoding and write "source code" which is translated to $0$'s and $1$'s (the "machine code") by compilers. But in fact early computer scientists did write down $0$'s and $1$'s directly by flipping switches. That was Gödelization in its pure form.

In practice we represent programs and data in a variety of formats known as .java, .py, .mp3, .jpg, etc. In logic and theory of computing people prefer to stick with the good old numbers because they are more easily manipulated within mathematics.

Nowadays everybody knows that "computers do everything in terms of $0$'s and $1$'s". This fact has become so familiar that it is hard to appreciate its originality. Many years ago, when no modern computers existed, it was far from obvious that machines, text, music, pictures and movies could all be encoded with numbers, or sequences of $0$'s and $1$'s.


Merge sort mxn matrix The question is as follows:

I am new to this, and I do not understand how to apply divide and conquer to a matrix, the algorithm that I have come up with is as follows (I am not sure if I am correct)

I thought I can divide the matrix into a matrices of 3 x 3 and 2 x 3 first. Then I will apply sorting of rows over column individually on both the matrices. Finally I will copy the second matrix sorting result over to the first sorted matrix. However, my problem is how do I sort the matrix first in to some order so that my division will yield a correct partition else what happens is, post copy I have to again sort (Which I thought is probably wrong)

As far as I can see, "sort the rows of the matrix, with respect to their columns" means that you're supposed to sort the rows lexicographically. That is, the row
$$a_1\ a_2\ \ldots\ a_n$$
comes before
$$b_1\ b_2\ \ldots\ b_n$$
if and only if there's some $i$ such that $a_j=b_j$ for $j<i$ and $a_i<b_i$.

As far as the divide and conquer goes, it doesn't matter that it's a two-dimensional matrix. You're trying to sort a collection of "things" according to some ordering on "things". These "things" happen to be the rows of some array but that doesn't make any difference to the algorithm.


How to simulate online matching algorithms (implementation) I was reading about online algorithms and bipartite matching.
I found an implementation that works fine on several websites (like geeksforgeeks).
For the online version, I found this paper
https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf
But there's one part that I don't understand.
In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once
While I can see how such case if frequent in real life, I fail to understand what kind of implementation could be used to demonstrate this...
I thought of the following

Create a graph with girls
add boys and define manually the girls they like via some sort of user input (input py/cin c++)
solve(match) for the newly added boy according to rank(priority) and return to user input till no more girls are left or till user decides to stop?

In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls?
Is my suggestion correct? or did I misunderstand something?
Thanks in advance

Just to clarify your doubt. An online algorithm is an algorithm that does not have the whole input (otherwise it would be offline), but it gets the input in a sequential manner. Looking at your paper, for example, they define an online algorithm as (1 Introduction):

An on-line algorithm receives a sequence of requests and must respond
to each request as soon as it is received

I would use a simpler example than a graph of boys and girls. Think about a list of numbers that you want to sort.
Then an offline algorithm would take the whole input and sort it: quicksort.
An online algorithm sorts after every single number, or better, it ensures that a certain property is maintained over a sequential input. An clear example of it is
Insertion Sort, since it ensures that the output list is always sorted.
Now looking at your questions:

In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once. ~> Exactly. The girls in the example arrive one by one. You might know how many they are in total, (since |V| seems to be given), but you do not know which one is the next one until you "matched" the current one. As in the "insertion sort" example, you do not know the next number until you sorted the current one.
In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls? ~> The paper says "Let G(U,V,E) be a bipartite graph", therefore my take on it is that you know how many boys (|U|) and how many girls you have (|V|).


Does $\{0, 1\}^*\in \text{co-NP}$? There is trivially $\emptyset\in\text{NP}$. From the definition of $\text{co-NP} = \{L : \overline{L} \in \text{NP}\}$ where $\overline{L} = \{0, 1\}^*-L$ follows $\{0, 1\}^*\in \text{co-NP}$. Is this true? If so, it is also true that $\{0,1\}^*\in \text{NP}$?

Both $\emptyset$ and $\{0,1\}^*$ are in $P$, and therefore they are also in $NP \supseteq P$ and $co-NP \supseteq P$.


What is difference between architecture and microarchitecture? I am studying computer architecture.  I would like to know the difference between the terms "computer architecture" and "microarchitecture".

The term architecture was popularized by the paper "Architecture of the IBM System/360", IBM Journal of Research and Development, 8(2):87-101, April 1964 by Gene M Amdahl, Gerrit A Blaauw, and Frederick P Brooks, Jr.  They say,

  The term architecture is used here to describe the attributes of a system as seen by the programmer, i.e., the conceptual structure and functional behavior, as distinct from the organization of the data flow and controls, the logical design, and the physical implementation.

According to the Wikipedia page on computer architecture the terminology was probably introduced inside IBM in 1959.

Today we would use the term instruction set architecture to describe the syntax and semantics of the interface of a computer, including the type and size of the operands, programmer visible register state, the memory model, how interrupts and exceptions are handled, the available instructions and the meaning of each instruction.  The instruction set architecture is the boundary between software and hardware, and is the contract between the programmer and the hardware designer.

The term microarchitecture is used to refer to the organization, or highest level of implementation, of a particular processor.  The study of microarchitecture would include topics like pipelining, instruction-level parallelism, out-of-order execution, speculative execution, branch prediction and caching.

I'm not sure about the etymology of microarchitecture.  I can find it used as early as 1975 (in the title of the EUROMICRO Workshop on the Microarchitecture of Computer Systems), but it could certainly be older than that.

Currently the term computer architecture or just architecture typically encompasses both instruction set architecture and microarchitecture, as well as broader system-level issues like network connectivity on multiprocessors.


Discrepancy between process execution time and CPU speed (lost cycles) I'm not sure if this is on topic, but I've seen some hardware related questions here so I'll post it here anyway. If it's off topic I'll take it off.

Compile this C code:

int main() {
  unsigned long long int i;
  for (i = 0; i < 30000000000ull; ++i){}
  return 0;
}

with gcc cycleTimer.c. Then run /usr/bin/time -f "%E %P" ./a.out.

I get the following output:

1:17.04 99%

Meaning the process takes 77 seconds to complete and uses 99% of a CPUs time. Running cpufreq-info during the process gives

current CPU frequency is 2.30 GHz

for all four cores. Now create the assembly instructions for cycleTimer.c with gcc cycleTimer.c -S, and we get the following assembly code:

        .file   "cycleTimer.c"
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movq    $0, -8(%rbp)
        jmp     .L2
.L3:
        addq    $1, -8(%rbp)
.L2:
        movabsq $29999999999, %rax
        cmpq    %rax, -8(%rbp)
        jbe     .L3
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
        .section        .note.GNU-stack,"",@progbits

From this, we can see that on every iteration of the loop, four assembly instructions are being run. Therefore, to work out the instructions per second, we do (4*30000000000)/77 = 1558441558 which is 1.6 GHz, much less than 0.99*2.3 which gives 2.28 GHz of the processor that we are actually meant to be using.

Why is there such a big discrepancy? The kernel is saying that 99% of the CPU is being used. Are there any other hidden instructions being computed by the CPU we don't see with gcc -S? Have I made a mistake somewhere?

The $2.3\textrm{GHz}$ clock cycle speed of your CPU is something entirely different from the rate at which it executes assembly instructions. Executing a single instruction may take 1, 10 or even more than 100 clock cycles or it might take less than a single cycle (since multiple instructions can sometimes be executed in a single cycle).

An interesting experiment would be to do some work in the loop body, such as an addition or a division. Even though addition and division are both single instructions, the program that does a division will probably take considerably longer than one that does addition since on most architectures division takes many clock cycles.


How do computers keep track of time? How are computers able to tell the correct time and date every time?

Whenever I close the computer (shut it down) all connections and processes inside stop.  How is it that when I open the computer again it tells the exact correct time? Does the computer not shut down completely when I shut it down? Are there some processes still running in it? But then how does my laptop tell the correct time when I take out the battery (and thus forcibly stop all processes) and start it again after a few days?

Computers have a "real-time clock" -- a special hardware device (e.g., containing a quartz crystal) on the motherboard that maintains the time.  It is always powered, even when you shut your computer off.  Also, the motherboard has a small battery that is used to power the clock device even when you disconnect your computer from power.  The battery doesn't last forever, but it will last at least a few weeks.  This helps the computer keep track of the time even when your computer is shut off.  The real-time clock doesn't need much power, so it's not wasting energy. If you take out the clock battery in addition to removing the main battery and disconnecting the power cable then the computer will lose track of time and will ask you to enter the time and date when you restart the computer.

To learn more, see Real-time clock and CMOS battery and Why does my motherboard have a battery.

Also, on many computers, when you connect your computer to an Internet connection, the OS will go find a time server on the network and query the time server for the current time.  The OS can use this to very accurately set your computer's local clock.  This uses the Network Time Protocol, also called NTP.


NP-hardness of problem with indices and subsets Consider the following problem.

  Let $S=\{1,2,\dots,n\}$, and $A_{ij}\subseteq S$ for $i,j\in S$. Does there exist a strict subset $T\subset S$ such that for all $j\not\in T$, there exists $i\in T$ for which $T\subseteq A_{ij}$?

(For $T=S$, this is trivially true, so we disallow it.)

The problem is in NP: given a set $T$, it is easy to verify whether it satisfies the property. Is it also NP-hard, or does there exist a polytime algorithm?

I tried to construct such a set $T$ greedily by starting with some $i\in S$. If $i\in A_{ij}$ for all $j\not\in i$, we can choose $T=\{i\}$ and are done. Otherwise, there is some $j$ for which $i\not\in A_{ij}$, so we can try adding $j$ into the set, and iterate on the new set $T=\{ij\}$ until the process stops. The problem is that there is no guarantee that this will stop before $T$ is the whole set $S$ even if such $T\neq S$ exists.

I also thought about dynamic programming, but it's not clear what the subproblems should be in this setting. On the NP-hardness side, I thought about reducing from some problems related to sets. There are problems like subset-sum or partition, but those concern sums of elements and are not directly relevant.

This question shows that Vašek Chvátal is a hero.

Reduce from graph kernel.

In the GRAPH KERNEL problem, the input data is a digraph and the task is to determine whether it has a kernel.

A kernel of a digraph is a subset $S$ of its vertex set which satisfies (i) no two vertices of $S$ are adjacent, and (ii) for every vertex not in $S$ there exists an arc from some vertex in $S$ pointing to it.

So, we need to transform a digraph to your set matrix problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element by $V$.

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure $T$ is an independent set in this digraph. For each arc-element $a=(u,v)$, set $A[u,a]=V\setminus\{v\}$ and $A[v,a]=V\setminus\{u\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A[w,a]=V\setminus\{u,v\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A[u,v]=V$

All the other entries of $A$ are set to $\emptyset$.


Can sampling remove the limitations in greedy algorithm? Given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or some structured manner reduce or remove the limitations of greedy algorithm?

I understand the answer to this is problem-specific, but given a problem that shows the limitation of greedy algorithm can sampling be used in any way in order to guide the greedy algorithm to generate an optimal solution?

It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as myopic algorithms) being only one of them. That said, I have a positive answer and a negative answer for you.

Positive answer. Consider the problem of maximizing a non-negative submodular function under a cardinality constraint. In this problem, you are given a submodular function $f$ over a domain $U$, and a bound $k$. Your task is to find a subset $S \subset U$ of size at most $k$ such that $f(S)$ is as large as possible. This problem is hard (more on that below), and so we make do with approximation algorithms. The greedy algorithm has no guarantees in this regard, but a simple modification of it gives a (probably non-optimal) $1/e$ guarantee. See Buchbinder–Feldman–Naor–Schwartz.

Negative answer. In what sense is the problem of maximizing a non-negative submodular function under a cardinality constraint hard? One such sense is hardness in the value oracle model. Suppose that an approximation algorithm is given oracle access to the function $f$. Then if $f$ always produces a $1/2+\epsilon$ approximation, there must be some $f$ and $k$ for which it calls the oracle exponentially many times (in $n = |U|$), a result due to Vondrák. This hardness result holds even for randomized algorithms (with any constant success probability). So randomization has its limits as an ingredient.

Does randomness help? Take the closely related problem of unconstrained submodular maximization – the case $k = n$ (recall $n = |U|$) of the problem considered above. The algorithm of Buchbinder–Feldman–Naor–Schwartz yields the optimal 1/2 approximation, but is randomized. They also give a 1/3 approximation algorithm which is deterministic, matching previous guarantees of Feige–Mirrokni–Vondrák. Can deterministic algorithms achieve the randomized guarantee? (Rumour has it that the answer is: Yes.)

Can randomization help? Under the widely held belief that P=BPP, there cannot be any discrepancy between randomized and deterministic polytime algorithms. However, this holds only in the model in which the input is given explicitly. In the value oracle model, the input is given implicitly as an oracle, and so it could be that randomized algorithms outperform deterministic ones. Indeed, it is easy to come up with specific tasks which are much easier for randomized algorithms. The question is whether unconstrained submodular maximization is one of these examples.


on "On the cruelty of really teaching computing science" Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course:

On the one hand, we teach what looks like the predicate calculus, but we do it very differently from the philosophers. In order to train the novice programmer in the manipulation of uninterpreted formulae, we teach it more as boolean algebra, familiarizing the student with all algebraic properties of the logical connectives. To further sever the links to intuition, we rename the values {true, false} of the boolean domain as {black, white}.
On the other hand, we teach a simple, clean, imperative programming language, with a skip and a multiple assignment as basic statements, with a block structure for local variables, the semicolon as operator for statement composition, a nice alternative construct, a nice repetition and, if so desired, a procedure call. To this we add a minimum of data types, say booleans, integers, characters and strings. The essential thing is that, for whatever we introduce, the corresponding semantics is defined by the proof rules that go with it.
Right from the beginning, and all through the course, we stress that the programmer's task is not just to write down a program, but that his main task is to give a formal proof that the program he proposes meets the equally formal functional specification. While designing proofs and programs hand in hand, the student gets ample opportunity to perfect his manipulative agility with the predicate calculus. Finally, in order to drive home the message that this introductory programming course is primarily a course in formal mathematics, we see to it that the programming language in question has not been implemented on campus so that students are protected from the temptation to test their programs.

He emphasises that this is a serious proposal, and outlines various possible objections, including that his idea is "utterly unrealistic" and "far too difficult."

But that kite won't fly either for the postulate has been proven wrong: since the early 80's, such an introductory programming course has successfully been given to hundreds of college freshmen each year. [Because, in my experience, saying this once does not suffice, the previous sentence should be repeated at least another two times.]

Which course is Dijkstra referring to, and is there any other literature available that discusses it?
The essay appeared in 1988 when Dijkstra was at the University of Texas at Austin, which is probably a clue -- they host the Dijkstra archive but it is huge, and I'm particularly interested in hearing from others about this course.
I don't want to discuss whether Dijkstra's idea is good or realistic here. I considered posting this on cstheory.se or cs.se but settled on here because a) a community of educators might be more likely to have someone who can answer easily, and b) Dijkstra himself emphasises that his course is "primarily a course in formal mathematics."  Feel free to flag for migration if you disagree.

This is pretty much what TU Eindhoven's Computing Science education, designed and implemented by Dijkstra and colleagues, was like from the time it started, around 1980, until Dijkstra's influence started to wane, somewhere half way through the 1990s.

I started studying CS at Nijmegen University in 1982; a classmate did the same at TU Eindhoven. Every spring, our old secondary school would have a day on which former students would introduce their chosen field of study to current students, and we were both there to introduce CS, so we compared our experiences. They were vastly different. In Nijmegen, we obtained actual experience with actual programming languages, actually running our assignment programs on an actual computer (a VM/CMS virtual machine, to be precise). Not so in Eindhoven.  My former classmate told me they weren't allowed to touch a computer in the first year. Programming, in Eindhoven, meant learning to mathematically construct provably correct algorithms from mathematically stated problem definitions.  On paper.

This attitude was somewhat relaxed after Dijkstra left, but even in the early 1990s, the courses called Programmeren (Programming), numbered 1 to 9, and spanning several years, still consisted of that same activity, and one in particular presented a major hurdle for the students. I never took any of those courses, but I doubt any use of computers was involved.

In case you're wondering: today's computer science education at TU Eindhoven is very different.


How to find the compression method used on an unknown sequence of bytes? I have a sequence of bytes:
https://drive.google.com/file/d/17sfchPgsySi2ilIxLuBb1q-UUqq5lO87
What the data is, is unknown (see NOTE below).
I'm pretty sure this data is compressed in some way, due to the ent analysis results:
$ ent first-chunk

Entropy = 7.997831 bits per byte.

Optimum compression would reduce the size
of this 949674 byte file by 0 percent.

Chi square distribution for 949674 samples is 2962.74, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.3922 (127.5 = random).
Monte Carlo value for Pi is 3.157487727 (error 0.51 percent).
Serial correlation coefficient is 0.001738 (totally uncorrelated = 0.0).

According to the Chi square distribution the data is definitely not random.
And compression is at an optimum. This leads me to believe the data is compressed and not encrypted. Is this a correct inference?
I've tried to decompress this data assuming the compression method to be zip, gz, xz, lz4, deflate, lzma, bzip, using tools like unlzma, gunzip, unzip, unlz4, zlib-flate etc. and none of them have worked. I always end up with a "file format not recognized" or a "invalid header check" error.
How do I find what compression method was used on the data? Could it be that the compression headers are missing?

NOTE:
This data is part of a slightly larger data file that is (possibly) the firmware and additional memory of a bluetooth speaker Flash memory.
The whole file is:
https://drive.google.com/file/d/1e9yG8xMkZ331C2TOTOzo9Y93L4abxX9F

This file contains some repeated long byte sequences. In particular, the 66(decimal)-byte sequence beginning 49 97 CE... occurs many times, and always at an offset that's a multiple of 66.
If you decrypt the file as a bitwise Vigenère cipher with that as the key, the result has a lot of structure. It appears to be divided into 66-byte records with 64 bytes of payload followed by a 2-byte checksum. (I assume it's a checksum because it's a deterministic function of the first 64 bytes, and the first 64 bytes sometimes have simple patterns like 01 01 01... but the last two bytes always look like garbage.)
Beyond that, I can't figure anything out. Notably, while some records consist entirely of recognizable patterns (except the checksum), and some begin with recognizable patterns and end as garbage, none begin as garbage and end recognizably, which makes me think that there may be more to the encryption than a simple xor.


Proving ambiguity of this Context Free Grammar I ran into this exercise problem from Introduction To The Theory Of Computation by Sipser. Given a context free grammar:

$ S \rightarrow SS \ | \ T \\ T \rightarrow aTb \ | \ ab $

I have to show that the grammar is ambiguous. So I have to find at least two leftmost derivation of a string. I have tried a lot but have failed to come up with a counter-example. I think T describes the following grammar:

$ L = {\{a^nb^n} \ | \ n > 0 \} $

But if I take $SS$, it is equivalent to taking $TT$, then it generates the strings like $ a^n b^n a^nb^n $, which is entirely different from L. So how can I come up with a string that has two leftmost derivation in this grammar. Any sort of help would be appreciated!

Below is the picture from the exercise.

The string $ababab$ has two different parse trees. In one of them the first two $ab$'s are grouped together, and in the other one, the last two $ab$'s are grouped together.

Stated differently, one parse tree corresponds to a derivation $S \Rightarrow SS \Rightarrow^* ababS \Rightarrow^* ababab$, and the other one to a derivation $S \Rightarrow SS \Rightarrow^* Sabab \Rightarrow^* ababab$. If you draw the parse trees for both derivations, you'll see that you get different parse trees.

Finally, here are actual two different leftmost derivations of $ababab$:

$S \Rightarrow SS \Rightarrow SSS \Rightarrow TSS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.
$S \Rightarrow SS \Rightarrow TS \Rightarrow abS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.

As an aside, an equivalent unambiguous grammar replaces the production $S \to SS$ by the production $S \to ST$ (or by the production $S \to TS$).