Stable matching with asymmetric arrays (gale shapley) I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms.

One of the answer suggested to add 5 dummy students to make number of students equal to 10.

Lets suppose before adding the dummy students the preferences are below -:

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

d1 - s1 s5 s3 s4 s2

d2 - s2 s3 s1 s5 s4

d3 - s3 s5 s4 s1 s2

d4 - s3 s5 s4 s2 s1

d5 - s2 s5 s3 s1 s4

d6 - s3 s4 s5 s1 s2

d7 - s2 s4 s5 s1 s3

d8 - s3 s5 s1 s4 s2

d9 - s2 s5 s3 s1 s4

d10 - s5 s2 s1 s3 s4

How should I go about this after adding the dummy students. My approach is below -:
I am putting 5 dummy student in lower preference for dorms and giving random dorms preference to dummy students. Dummy students are denoted by ds.

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

ds1 - d6 d2 d9 d10 d4 d5 d3 d1 d8 d7

ds2 - d4 d2 d6 d3 d10 d9 d5 d7 d1 d8

ds3 - d7 d3 d5 d1 d10 d9 d2 d8 d4 d6

ds4 - d2 d8 d1 d10 d6 d3 d4 d5 d9 d7

ds5 - d10 d2 d6 d3 d4 d5 d1 d7 d9 d8

d1 - s1 s5 s3 s4 s2 ds1 ds2 ds3 ds4 ds5

d2 - s2 s3 s1 s5 s4 ds1 ds2 ds3 ds4 ds5

d3 - s3 s5 s4 s1 s2 ds1 ds2 ds3 ds4 ds5

d4 - s3 s5 s4 s2 s1 ds1 ds2 ds3 ds4 ds5

d5 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d6 - s3 s4 s5 s1 s2 ds1 ds2 ds3 ds4 ds5

d7 - s2 s4 s5 s1 s3 ds1 ds2 ds3 ds4 ds5

d8 - s3 s5 s1 s4 s2 ds1 ds2 ds3 ds4 ds5

d9 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d10 - s5 s2 s1 s3 s4 ds1 ds2 ds3 ds4 ds5

If i solve the above with gale shapley will I get the right results?? In other words, will I get the stable matching?

This will give you a stable matching when you will use the Gale Shapley algorithm. You can use the below code. a and b are dictionaries in the code

def insert_dummies(a,b):
  length_a=len(a.keys())
  length_b=len(b.keys())
  items_a=list(a.keys())
  items_b=list(b.keys())
  dummy_list=[]
  if length_a>length_b:
    dummy_number=length_a-length_b
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_a:
      f=0
      while dummy_number>f:
        a.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0
    while n<(dummy_number):
      for z in dummy_list:
        b[z]=items_a
        n=n+1
  if length_a<length_b:
    dummy_number=length_b-length_a
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_b:
      f=0
      while dummy_number>f:
        b.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0
    while n<(dummy_number):
      for z in dummy_list:
        a[z]=items_b
        n=n+1
    else:
        return

  return a,b

#This function returns the result of the algorithm. Parameter 'a' refers to the preferences of the gender
#that we want to find the optimized solution for, while the parameter 'b' refers to the preferences of the other gender.
def StableMatching(a, b):
    #this function returns a stable matching
    dict_a = a.keys()  #This list contains the names of the group for we are optimizing.
    names1 = list(dict_a)
    dict_b = b.keys() #This list contains the names of the other group.
    names2 = list(dict_b)
    i = 0
    engaged = []
    #This dictionary contains the names of the gender for which we attempt to find the optimized solution.
    times = {}
    t = 0
    position_existing = 0
    position_potential = 0
    counter = 0
    #Can have the values 'free' or 'not free'.
    a_p = {}
    while(counter < len(names1)):
        a_p.update({names1[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Can have the values 'free' or 'not free'.
    b_p = {}
    while(counter < len(names2)):
        b_p.update({names2[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Initialization of times dictionary.
    while(counter < len(names1)):
        times.update({names1[counter]: 0})
        counter = counter + 1

    #The value -1 has the meaning that when all men or women are paired, the loop stops;
    while((i != -1) and (a_p[names1[i]] == 'free') and (times[names1[i]] < len(names2))):
        #The man/woman who is next in the ranking of the proposals.
        w = a[names1[i]][times[names1[i]]]
        if(b_p[w] == 'free'):
            a_p[names1[i]] = 'not free'
            b_p[w] = 'not free'
            t = (names1[i], w)
            engaged.append(t)
            times[names1[i]] = times[names1[i]] + 1
        else:
            q = 0
            while(q < (len(engaged))):
                  if(w in engaged[q]):
                      t1 = engaged[q]
                      l = 0
                      while(l < len(names1)):
                          if(names1[i] == b[w][l]):
                              position_potential = l
                              l = len(names1)
                          l = l + 1
                      l = 0
                      while(l < len(names1)):
                          if(t1[0] == b[w][l]):
                              position_existing = l
                              l = len(names1)
                          l = l + 1
                      if(position_potential < position_existing):
                          t = (names1[i], w)
                          engaged.append(t)
                          del(engaged[q])
                          a_p[names1[i]] = 'not free'
                          a_p[t1[0]] = 'free'
                          q = len(engaged)
                  q = q + 1

            times[names1[i]] = times[names1[i]] + 1
        i = i + 1
        #If the variable i has passed from all the men/women then it starts from the beginning
        #in order to check the ones who remain single.
        if(i == len(names1)):
            i = 0
        if(a_p[names1[i]] == 'not free'):
            k = 0
            z = False
            while((k < len(names1)) and (z == False)):
                if(a_p[names1[k]] == 'free'):
                    i = k
                    z = True
                k = k + 1
            if((k == len(names1)) and (z == False)):
                i = -1
    engaged_dict = dict(engaged)
    return engaged_dict


Would it be possible that the intersection of two non-context-free languages is context-free? Assume two languages $L_1$ and $L_2$, both of which are non-context-free.

Let $L = L_1 \cap L_2$. Could $L$ be context-free?


What is the expressive power of finite-state transducers and pushdown transducers? One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from CFG grammars.

I am, however, unsure about this because we can construct a finite state transducer which translates a string of the form $ab$ to $\{ a^n b^n : n \ge 1 \}$, which is irregular.

Is this the case? If so, can anyone provide the relevant literature?

we can construct a finite state transducer [that maps $\{ab\}$ to $\{a^nb^n n \geq 1\}$].

No, we can't. REG is closed against finite-state transduction.

Wikipedia hints as much without citation; planetmath.org lists some standard references, in particular Hopcroft/Ullman.


Longest Common Subsequence Via Dynamic Programming I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original sequences. For example, the traceback table generated here is correct, since the longest common subsequence of AGCAT and GAC has a length of 2:

   |A  G  C  A  T
---+-------------
  G|0  1  1  1  1
  A|1  1  1  2  2
  C|1  1  2  2  2

From what I understand of how it's supposed to work, the length of the LCS should appear in the bottom right cell.

But using the same method for generating the table, which you can find here, if you rearrange the letters you get an incorrect solution.

   |A  A  G  C  T
---+-------------
  C|0  0  0  1  1
  G|0  0  1  1  1
  A|1  1  1  1  1

Length of the LCS shouldn't have changed, the bottom right value is no longer 2.

Is my question clear enough? Am I simply following the method incorrectly? From what I understand, the order of the original sequences shouldn't matter.

Your question is clear and you are performing the method correctly, as far as see.

But it seems to be a misunderstanding about what the problem solves about strings.
The longest common subsequence problem is about find out a  subsequence of characters in the case of string, not necessary consecutive like substrings.

By example, some subsequences of AAGCT are: AG, AT, ACT, AGT


Compute a max-flow from a min-cut We know that computing a maximum flow resp. a minimum cut of a network with capacities
is equivalent; cf. the max-flow min-cut theorem.

We have (more or less efficient) algorithms for computing maximum flows, and computing a minimum cut given a maximum flow is neither hard nor expensive, either.

But what about the reverse? Given a minimum cut, how can we determine a maximum flow?
Without solving Max-Flow from scratch, of course, and preferably faster than that, too.

Some thoughts:

From the minimum cut, we know the maximum flow value. I don't see how this information helps the standard approaches augmenting-path and push-relabel, although adapting the latter seems slightly more plausible.
We can not use the minimum cut to split the network in two parts and recurse since that won't shrink the problem in the worst case (if one partition is a singleton); also we would not have a minimum cut of the smaller instances.
Does knowing the value of the maximum flow speed up solving the Max-Flow LP, maybe via the complementary slackness conditions?

In the worst case, the minimum cut itself doesn't convey much information about the maximum flow. Consider a graph $G=(V,E)$ in which the minimum $s,t$-cut has value $w$. If I extend $G$ by adding a new vertex $s'$ and an edge $(s',s)$ with weight $w$, a minimum $s',t$-cut in the new graph consists of just the edge $(s', s)$ but that doesn't give any information about how to get $w$ units of flow from $s$ to $t$.

Effectively, the minimum cut tells you the value of the flow, but not how to achieve that flow. This means that knowing the minimum cut can speed up finding the flow by at most a logarithmic factor, since we could do binary search to find the value of the cut.


Delete a consecutive range of leaves from a binary tree Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values).

I want to delete a consecutive interval of leaves.  In other words, suppose we order the leaves from left to right and number them $1,2,\dots,n$.  I am given a pair of indices $i,j$, and I want to delete leaves $i,i+1,\dots,j-1,j$.  This operation should also delete an interior node if all of its descendant-leaves are deleted.

Can this be done efficiently?  Can it be done in $O(d)$ time, regardless of $i,j$?

Yes.  This can be done in $O(d)$ time.  As a nice consequence, if we have a balanced binary tree, then $d = O(\lg n)$, so range-deletion can be done in $O(\lg n)$ time, regardless of how large the range is.

This is hard to explain without a picture, but the key insight is this: it suffices to delete a set $S$ of nodes, where $S$ can be chosen so that $|S| \le 2d$.  (This will of course delete all of the descendants of every node in $S$.)  Since $|S| = O(d)$, the running time to delete the nodes in $S$ will be $O(d)$.  In other words, the interval $[i,j]$ can be expressed as a union of $O(d)$ subtrees.  Roughly speaking, the set $S$ will be chosen by taking a subset of the siblings of the nodes on the path from $i$ or $j$ to the root.

In particular, we will define

$$S = \{n : L(n) \subseteq [i,j] \text{ and } L(\text{parent}(n)) \not\subseteq [i,j]\},$$

where $L(n)$ is the set of leaves that are descendants of $n$.  I will show first that deleting $S$ has the desired effect, and second that that $|S| \le 2d$, from which it will follow that the range-deletion can be done in $O(\lg d)$ time.

Lemma 1. Deleting $S$ will have the effect of deleting leaves $i,i+1,\dots,j-1,j$ but not any of the other leaves.

Proof. Consider any leaf $\ell$ with $i \le \ell \le j$.  Then $\ell$ is a descendant of some $n \in S$: if $\ell \notin S$, then some ancestor of $S$ must be in $S$ (imaging walking up from $\ell$ along the path towards the root; consider the last ancestor $n$ of $S$ such that $L(n) \subseteq [i,j]$; since $L(\ell) =\{\ell\} \subseteq [i,j]$, such an ancestor must exist).  Conversely, a leaf $\ell$ is deleted only if it is a descendant of some $n \in S$; but by construction, $L(n) \subseteq [i,j]$ and $\ell \in L(n)$, so it follows that if leaf $\ell$ is deleted, $\ell \in [i,j]$.

Now let's show that $|S| \le 2d$.  Let $P(\ell)$ denote the set of nodes along the path from $\ell$ to the root.  Let $Q(\ell)$ denote the set of siblings of the nodes in $P(\ell)$ ($\ell$'s sibling, $\ell$'s parent's sibling, $\ell$'s parent's parent's sibling, and so on).  Then I claim:

Lemma 2. $|Q(\ell)| \le d$ for all $\ell$.

Proof. Since the tree has height $d$, $|P(\ell)| \le d$.  Now $|Q(\ell)| \le |P(\ell)| \le d$.

Lemma 3. $S \subseteq Q(i) \cup Q(j)$.

Proof. Suppose $n \in S$, so that $L(n) \subseteq [i,j]$ but $L(\text{parent}(n)) \not\subseteq [i,j]$.  Let $m$ be $n$'s sibling.  Note that $L(\text{parent}(n)) = L(n) \cup L(m)$.  It follows that we must have $L(m) \not\subseteq [i,j]$ (otherwise $L(\text{parent}(n)) \subseteq [i,j]$ and $n$ wouldn't be in $S$).  Also $L(n) \cap L(m) = \emptyset$ and $L(n)$ and $L(m)$ are adjacent intervals ($L(n) \cup L(m)$ is itself an interval; there is no gap in between $L(n)$ and $L(m)$).  It follows that either $i \in L(m)$ or $j \in L(m)$, i.e., $m$ must be an ancestor of either $i$ or $j$, i.e., either $m \in Q(i)$ or $m \in Q(j)$.

Lemma 4. $|S| \le 2d$.

Proof. Follows from Lemma 2, Lemma 3, and the union bound.

Caveat: I haven't checked whether rebalancing can also be done in $O(d)$ time.  For instance, for a balanced binary tree like an AVL tree or a red-black tree, we have $d=O(\lg n)$, and it would be nice if we could delete the entire range in $O(\lg n)$ time.  However, it's not clear whether this is possible.  While we can indeed delete the nodes in $S$ in $O(\lg n)$ time, I haven't checked whether it's possible to do all necessary subsequent rebalancing operations in $O(\lg n)$ time.  Rebalancing is certainly doable in $O((\lg n)^2)$ time, but I don't know whether it can be done in $O(\lg n)$ time.


What structure is used for accessing the most frequent elements top k over a stream of elements? Let's say you want the top k elements. Then given the array, there is an O(n) O(n) space approach. But what if you have a stream of elements, this means that each time you'd append an element to the end of your list, you'd have to do this O(n) time O(n) space approach. Let's say your elements are distinct elements of a set. You can maintain a frequency map, but you'd still have to do the O(n) approach to find the top k elements. Is this is what is done in production? What data structure is used to efficiently keep top k elements with updated frequencies?

This is possible in $\mathcal O(\log n)$ time using self-balancing tree (or heap), using frequencies as keys. This extends the node to keep a list (or once more a tree) of elements of equal frequency.
To access top k elements you can either augment the tree with additional pointers to allow traversal in $k$ steps or use $\mathcal O(\log n)$ recursive one.
Better approach is to keep $k$ elements in that tree-like structure and in another one the rest.

If elements are fixed, you can use hash-table to store them, so keeping a table per frequency would result in expected time $\mathcal O(1)$, here using knowledge of the elements will help to minimize number of collisions.


Difference between Quick sort, Merge sort and Heap sort We know all the above-mentioned sorting algorithms take $\mathcal{O}(\mbox{N log N})$. Merge sort and Heap sort algorithms take $\mathcal{O}(\mbox{N log N})$ time in worst-case where Quicksort takes $\mathcal{O}(\mbox{N}^2)$. So what is the main difference between these algorithms? Which algorithm is preferable for sorting at any time?

Actually, I have been asked this in an interview. I replied Merge sort is not good with space. So we can consider Quicksort. But I couldn't figure out the difference between quick sort and heap sort. I need your help to figure it out.

Well. If you considered only the asymptotic time complexity $\mathcal{O}(\mbox{N log N})$, then there would be practically no difference between Quick and Heap sort. So both algorithms runtime is:

$\mbox{constant} \cdot \mbox{N log N}$

but, the constant may differ significantly and this is what makes a big difference. So, in practice, Quick sort is much more effective and requires much less comparisons than Heap sort (see e.g. here) - so the constant in the above expression for Quick sort is much smaller. That's why Quick sort is the one most used for general purpose..


Is the set of surjective recursive functions in RE/coRE? Let L be a set of recursive funtions with $L = \{i\in \mathbb{N}|f_i\space is\space surjective\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$?

I can't think of a way to show either of the two.

Rice-Shapiro proves that $L$ is not RE nor coRE.

Let $F$ be the set of computable surjective functions. $L$ is the the index set associated to $F$.

Assume by contradiction $L$ is RE. By Rice-Shapiro (compactness), since the identity function belongs to $F$, some finite restriction of the identity must belong to $L$ as well. But a finite-domain function can not be surjective -- contradiction.

Assume by contradiction $\bar L$ is RE. The always undefined function $g$ belongs to $\bar F$, so by Rice-Shapiro (monotonicity), $\bar F$ contains any computable extension of $g$, including the identity function, which is surjective. Contradiction.


Which sort algorithm to choose given two specific arrays? Interview question:

Given array A which contains only odd numbers and array B which contains only even numbers, explain
which sort algorithm would you choose.

I said merge sort. I thought that given two lists both of which are sorted (which I assumed) I can just merge them i.e use the merge part of merge sort.
I was then asked if the numbers were not even or odd would I have chosen merge sort still? Then I was asked if both arrays were not sorted i.e. A contain even numbers (not sorted) and B contain odd numbers (not sorted) which algorithm will I use. I said in practice quicksort typically performs better. I wanted to ask if the length of the arrays is not too big because then bucket sort might do but given his insistence on odd and even integer arrays I did not go for bucket sort (I was afraid I was mentioning all the algorithms).
Does anyone know which algorithm might the interviewer be looking for?

I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime.

Suppose you have an algorithm which works very fast in that case. Then, given any array of integers, you can split it up into an array of even integers and an other of odd integers in linear time. You can then run your super fast algorithm on these arrays to sort your original array super fast as well. Thus, a faster algorithm for this case would lead to a faster algorithm in the general case. So you can safely choose to use whatever sorting algorithm is fastest in the general case (asymptotycally $O(n\log n)$).


What is the difference between complexity theory and computability theory? What is the difference between complexity theory and computability theory? Is there any overlap between the two or are they completely different? Or is one a subset of the other?

Put succinctly, computability theory is concerned with what can be computed versus what cannot; complexity is concerned with the resources required to compute the things that are computable.

As such, the fields are somewhat disjoint. Complexity theory is interested in a fine-grained classification of computable problems, with "it's uncomputable" as a worst-case scenario where we throw up our hands and give up. Computability theory (though one wouldn't realise this from an undergrad course) is interested in a fine-grained classification of uncomputable problems, with "it's computable" as the case at the bottom that's left to others to deal with.

However, there is some overlap of techniques, at least at a high level.  In both cases, one typically uses the existence of an algorithm to demonstrate membership in a class and proofs of hardness are usually by reductions. Diagonalization also plays a role in both, proving things like the time and space hierarchy theorems in complexity, and the undecidability of halting problems in computability.


Name for tree where each node has the aggregate of its children Is there a general name for a tree in which the leaves have some arbitrary values and the value of every other node is some "aggregate" function of its children?

An example where the aggregate function is the sum:

  14
 /  \
4   10
   / | \
  7  1  2

The function could also be the min, max, or any other function of the form $f:S^n\to S$.

Such tree is called Sum Tree or SumTree, where the property is maintained in bottom up fashion. In general if the value is additional value (node property) for some existing one like AVL it is Sum augmented AVL Tree.

If the property is inherent, like maintaining the prefix sum, it would be Fenwick Tree.

As far as I know there is no established name, but for other functions it is partial statistics tree. preferable name would be Tree augmented with $f$, to make it explicit.


Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$ I need help with proving the following language is not regular:
$$
L = \{ a^n b^k \mid n > k \} \cup \{ a^n b^k \mid n \neq k-1 \}
$$
My usual methods using pumping lemma are not getting me anywhere.

If $n > k$ then $n \neq k-1$ (since $k-1 \not> k$), so your language is really $L = \{ a^n b^k \mid n \neq k-1 \}$. If $L$ were regular then so would be the following language $a(a^*b^* \setminus L) \cup \{\epsilon\} = \{ a^n b^n \mid n \geq 0 \}$, which is known not to be regular.


DFA for strings with number of 0's odd only in substring longer than 1 I'm trying to design and DFA that accept string with an odd number of 0`s, but counting only the ones within sub-strings with two or more 0.

So, for example, 011000, will be accepted since it has 4 0`s, but only three or them are inside a sub-string of two or more. But 0001000, wont be accepted.

I believe your language is not regular and if I'm not mistaken, the pumping lemma suffices:
Let us assume by contradiction your language is regular, thus it should hold all 3 conditions of the pumping lemma.

Let $w=0^{2p+1}111$, notice $w\in L$ because $2n$ is always even, thus by adding $1$ we have an odd number of $0$s.

Now let us take a simple example where $p=1$, but this should work for any $p$.

In this case, $p=1$, notice $|w|>p$, since $|w|=5$, essentially $w=000111$. In our case this means $y=0$ and because $|xy|\le 1$ and because $|y|>0$  where 1 is our pumping length this means $x=\epsilon$.

This leaves $z=0011$. However, for $i=2$, we receive: 000011 which is $y^2z \equiv 000011 $.

Then the number of 0s in your substring is now even, meaning $000011 \notin L$.
Again, we can do this for any pumping length $p$ by simply pumping up or pumping down.

Thus there won't be a DFA/NFA for that. You can try using a TM.

For more information: pumping lemma.


A tricky P=NP problem Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under $\pi$ we have $\mathsf{P}=\mathsf{NP}$.

This is a homework question I had. My current sketch is: for a language $L_1 \in \mathsf{NP}$, define another language $L_2\in \mathsf{P}$ based on $L_1$ such that deciding $\pi(L_2)$ helps decide $L_1$. Here $\pi(L_2)$ is decidable as $\mathsf{P}$ is closed under $\pi(\cdot)$; $L_1$ being decidable infers that $L_1\in \mathsf{P}$ and thus $\mathsf{P}=\mathsf{NP}$.

I think my sketch is in the right direction but I'm struggling in defining the appropriate $L_2$ here. Any hint would be appreciated!

You are asked to prove: There is a language X which is in P, such that the language π(X) is NP complete. Because in this case, since P is closed under the operation π, π(X) is also in P, which means P = NP. The idea is: Define a language X, which consists of strings that are YES-instances of an NP-complete problem, followed by an oracle that proves the instance is a YES-instance. The details are a bit tricky.

Define an encoding of instances of the travelling salesman problem: The encoding starts with the number n of cities in decimal notation, a comma, the number K which is the maximum length of a tour, an opening bracket, n * (n-1) / 2 distances in decimal notation, separated by commas if there is more than one distance, and a closing bracket. It is easy to determine that a string is such an encoding of a TSP instance.

We define the language L as follows: Each string in L consists of the encoding of a TSP instance with answer "YES", followed by hyphen characters "-" to exactly double the length of the string so far, followed by a permutation of the numbers 1 to n in decimal notation, separated by commas, such that starting at town 1, then visiting towns in the given order, produces a cyclic tour with length at most K.

The language L is clearly in P. The language π(L) consists of strings that are the encoding of a YES-instance of TSP, followed by some number of hyphens, and if there are enough hyphens, part or whole of an oracle. Because the oracle is much shorter than the encoded instance, π(L) contains some strings that are just encoded TSP instances, followed by hyphens. But for these strings, deciding that they are in π(L) is hard, as hard as deciding that an ordinary instance of TSP is a YES-instance. So π(L) is NP-complete.

And if π(L) is also in P as assumed, then P = NP.


What string operations are basic What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a complete list, and your addition is welcome):

reversal of a string
concatenation of two strings
repetition of a string a finite number of times
search/match a string inside another string
match and replace a string with another string inside a string
split a string, at some specified positions, or according to matching result of another string
taking a substring out of a string, according to specified positions (including taking prefix, or suffix), or according to matching result of another string
...

There are many "complete bases" for operations on strings. One is based on the representation
$$ \Sigma^* = \epsilon + \Sigma \Sigma^*. $$
In words, a string is either empty or is composed of a character and a string. In order to use this representation, we need the following functions:

nil – the empty string
cons(x,s) – the string consisting of the character x followed by the string s
null(s) – true if s is empty
car(s) – returns the first character of a non-empty string
cdr(s) – returns the string resulting from removing the first character of a non-empty string

The terminology is from Lisp; cdr is read could-er or cudder.

Another basis considers strings as arrays. There is a standard basis for reading strings:

len(s) – the length of s
s[i] – the character at position i

For writing strings there are several options. In the immutable case, one choice is:

"" – the empty string
str(x) – the string consisting of the character x
cat(s1,s2) – the string resulting from concatenating s1 and s2

If strings are allowed to be mutable, we can add an operation s[i] = x, changing the character at position i to be x.

One can think of many other bases. Some will be more efficient than others. It all depends on what exactly you are trying to capture, what your goal is.


Turing machine reduction task I am having trouble solving the following task:

  Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$

  Prove that $D$ is not decidable by reducing $$A_{\mathrm{TM}}=\{\langle T, w \rangle \mid \text{$T$ is a Turing machine and $T$ accepts $w$}\}$$ to $D$.

My solution and proof idea

(I am not sure if they are correct.) Assume that $D$ is decidable. Let $R$ be a decider for $D$ and $S$ for $A_{\mathrm{TM}}$. We know that $A_{\mathrm{TM}}$ is not decidable. However, if we manage to show it is decidable using $R$ as subroutine, we derive a contradiction and have therefore shown that $R$ is not decidable either.

Now I have got to a point where I do not know further because I have problems finding ways of showig the contradiction since I cannot see a connection between entering all states and accepting input $w$. If the TM enters all states, it is still unclear if the input is also accepted.

I guess I have to run R on a modification of $T$ so that I can derive a contradiction.

Given a TM $T$, consider the machine $T'$ which, on input $w$, simulates $T$ on $w$ and enters a special state $q$ if and only if has determined that $T$ accepts $w$. Note you can easily guarantee $T'$ never enters $q$ prior to $T$ accepting $w$. Moreover, you can make sure that, once $T'$ enters $q$, it starts to cycle between all its states indefinitely. (For instance, have $T'$ write a special tape symbol so it knows it is supposed to do so.)

For an arbitrary $T$, producing the description of $T'$ is computable. I'll leave it to you to fill in the gaps so this is a full-fledged reduction.

As a rule of thumb, these exercises can usually be solved by producing description of machines (in this case, $T'$) which encode the answer to the original problem ($A_{\mathrm{TM}}$) in their own behavior. In this particular case, the idea is to establish the equivalence between $T'$ entering all its states and $T$ accepting $w$.


Starvation Condition in CPU/Process Scheduling? Let's say OS is using preemptive CPU scheduling. A process P1 gets a chance to run for some time and then next higher priority process comes and preempts P1. After that higher priority processes are coming regularly and P1 never gets chance. Is this condition called starvation or not?

The first line in the wikipedia states
"In computer science, starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to proceeds its work."

https://en.wikipedia.org/wiki/Starvation_%28computer_science%29

so the condition you stated is starvation because P1 is perpetually denied necessary resources to proceeds its work.


Is $\{\varepsilon\}$ a conventional way to mark the empty language? I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer who confirmed. But I keep seeing this and I'm losing my confidence. Is this kind of thing used by anyone? Meaning, does anyone use $\{\varepsilon\}$ as the empty language (even though it would "override" the obvious meaning of the singleton of $\varepsilon$)?

No, that's the language containing one string: the empty string, which is very much distinct from the empty language. The finite state machine on the left accepts language $\{\}$, the finite state machine on the right accepts language $\{\varepsilon\}$. They are not the same.

If a lot of students are confused maybe explicitly show the difference in an exercise/during a lecture.

As an example, we could use the language as a password check. Anyone submitting an accepted word would be let through. Then $\{\}$ means "let no one in" and $\{\varepsilon\}$ means "let anyone that submits a blank password in". Those are quite different indeed!


Functional Dependencies Let relational schema R(A,B,C,D,E,F,G,H,I).

The functional dependencies are: A -> BC, AD -> BE, C ->F , A->F , D-> E

Find the number of non-trivial functional dependencies ? I know that R has only five non-trivial functional dependencies but i do not know how to prove this(How to think)?

$R$ has only five non-trivial functional dependencies (FDs).

No, $R$ has many more non-trivial FDs. For example, Since A-> BC and C -> F, we also  have AC->BF, which is also a non-trivial FD although not a irreducible FD.
What you can say is that all given 5 FDs are non-trivial FDs, since for each given FD, the dependent set is not a subset of the the determinant set.
If you want to see all non-trivial function dependencies of $R$, you have to obtain the dependency closure of the given FDs, following, for example, the procedure given here using Armstrong's axioms.

Step-1 : Add the attributes which are present on Left Hand Side in the original functional dependency.
Step-2 : Now, add the attributes present on the Right Hand Side of the functional dependency.
Step-3 : With the help of attributes present on Right Hand Side, check the other attributes that can be derived from the other given functional dependencies. Repeat this process until all the possible attributes which can be derived are added in the closure.

You can enter R(A,B,C,D,E,F) and A -> B,C; A,D -> B,E; C ->F ; A->F; D-> E into the first two fields on this page. Hit the "Calculate" button and view the result. It will list a lot of related concepts. In particular, it shows the following 43 non-trivial FDs.
A → B,C,F
C → F
D → E
A,B → C,F
A,C → B,F
A,D → B,C,E,F
A,E → B,C,F
A,F → B,C
B,C → F
B,D → E
C,D → E,F
C,E → F
D,F → E
A,B,C → F
A,B,D → C,E,F
A,B,E → C,F
A,B,F → C
A,C,D → B,E,F
A,C,E → B,F
A,C,F → B
A,D,E → B,C,F
A,D,F → B,C,E
A,E,F → B,C
B,C,D → E,F
B,C,E → F
B,D,F → E
C,D,E → F
C,D,F → E
A,B,C,D → E,F
A,B,C,E → F
A,B,D,E → C,F
A,B,D,F → C,E
A,B,E,F → C
A,C,D,E → B,F
A,C,D,F → B,E
A,C,E,F → B
A,D,E,F → B,C
B,C,D,E → F
B,C,D,F → E
A,B,C,D,E → F
A,B,C,D,F → E
A,B,D,E,F → C
A,C,D,E,F → B


What is the implication of the sentence: "if any NP complete problem is p time solvable, then all problems in NP are p time solvable" I find this quote here on page 13

  Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p time solvable?

This is very unbelievable to me since NP complete problems are so different in nature and comes in a variety of form such as longest path, dominating vertex, halting problem, knapsack problem. Can someone show me how this statement is true?

This statement means exactly what you have said: if any NP-complete problem is solvable in polynomial time, then all of them are. This follows from the definitions: a problem X is NP-complete if all problems in NP are polynomial time reducible to it, that is, if for any problem Y in NP there is a polynomial time function $f_Y$ such that for all $w$, $w \in Y$ iff $f_Y(w) \in X$. Now suppose that you could solve X in polynomial time using some algorithm A. For any NP problem Y, you can use $f_Y$ in conjunction with A to solve Y in polynomial time.

This is indeed surprising, and it is one reason why most researchers conjecture that NP is different from P: otherwise all these disparate problems will have polynomial time solutions.


Polynomial time algorithm for finding a maximal monotone subset Input:
Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
Question:
Can this be computed in polynomial time in $n$?
Remarks:

For $k=1$ this is equivalent to the problem of finding a longest increasing subsequence. Indeed, assuming that $x_1<\dots<x_n$, we search for a longest increasing subsequence of $y_1,\dots,y_n$. Such a subsequence can be found in $O(n\log n)$.
The problem is related to the notion of a monotone operator $F:\mathbb R^k\to\mathbb R^k$. Monotonicity of $F$ means that $(x_1-x_2)^T(F(x_1)-F(x_2))\ge 0$ for all $x_1,x_2\in\mathbb R^k$.
The problem can be formulated as a search for a maximum clique in the graph $G=(V,E)$ with vertices $V=\{1,\dots,n\}$ and edges
$E = \{(i,j) \;:\; (x_i-x_j)^T(y_i-y_j)\ge 0 \}$.
The general clique problem is NP-complete.
However, it might be possible to exploit the special structure of $E$ (as shown in the first remark, this is possible when $k=1$).

I would appreciate any hint or comment on this problem.

I stared at this a while now with $k=2$ and got nowhere.

Let's take on $k=2$. To avoid confusion with x and y coordinates, I'll call the vectors $a_i, b_i$ instead.
Lets define $D(i,j)=(a_j-a_i)^T(b_j-b_i) \ge 0$, and $R(i,j)$ to be the boolean relation which holds when $D(i,j)\ge0$.
For $k=1$, R was a total ordering, which is what let us find increasing subsequences. For $k=2$, it's not even a partial ordering, which makes me think any solution will not resemble the $k=1$ case.

Take $x_1,x_2,x_3=(0,0),(0,1),(1,0)$; $y_1, y_2, y_3=(0,0), (-6, 1), (-5,-5)$
$V(1,2)=1$; $V(2,3)=1$; $V(1,3)=-10$

I'd suggest checking if this can be reduced to the longest common subsequence problem (I suspect no, because of the lack of ordering) or to/from some form of linear programming.
To nitpick here, coordinates should really be taken from $\mathbb Z$ bounded by some reasonable (say, polynomial) function for CS problems, not "$\mathbb R$". I suspect you can show it's NP-complete otherwise, say by reduction to the longest common subsequence problem, but in some way that's not really related to whatever your real problem is. That said, I didn't succeed at actually doing so.


Scientific soundness of computer science papers First of all, this question relates to an issue that affects several areas of science, but since StackExchange doesn't have a meta science section I'll make it specific to computer science, which is pertinent because the solution to the bigger problem may actually come from computer science.

In the context of the news that Springer and IEEE published more than 120 nonsense papers my question is as follows:

What rigourous set of methods can we apply to the process of publishing scientific papers so that we can quickly verify the reproducibility of the experiments?

We already have systems like Turnitin that are highly efficient at detecting plagiarism, yet I don't know of any system that can score a piece of work on its scientific soundness.

Is there any ongoing work related to this? I found out about Semantic Publishing whilst composing this question, but I have no idea what other approaches, if any, are being actively worked on.

This is a complex issue that affects all areas of science but has been getting higher visibility as the mainstream media has reported some cases in headlines. An answer seems to be better review systems. However, one might argue that nonsense papers are not necessarily a failure of the peer review system. All peer review systems must be human to some degree and all human systems are fallible/ subject to failure. any peer review system will have both false positives and false negatives in the sense of papers that were accepted but shouldnt be on 2020 hindsight, and papers that were rejected but were of acceptable quality. There is some increasing awareness/ sociological study of peer review systems. Cyberspace can in fact aid the process in some ways by increasing reviewers, increasing visiblity of reviews, adding rating systems, etc. and it can have downsides such as computational ease of creating fake submissions, increased AI capabilities to fool humans, etc.

An example of a CS specific peer review (meta-) analysis can be found in the recent NIPs experiment where peer reviewers were split into two groups, the same papers were given to each, and the overlap in acceptance/ rejection decision was measured. not unsurprisingly to many, results had quite high variance. Researchers overcome "false negatives" by resubmitting papers to other conferences. Unfortunately this NIPs experiment never seemed to be documented except across a lot of CS blogs and there is already some "link rot" of key links. It was announced informally at the conference and many insiders blogged on it including those participating. A full documentation might be considered "airing dirty laundry".

The NIPS Experiment
NIPs peer review experiment / many links


The stable marriage algorithm with asymmetric arrays I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices.

For example if we have 10 students that should be assigned to 10 dorms, then I can build the preference and ranking matrix of this data. The question that I have is what to do in the case that I have, for example, only 5 students to assign and for example 10 dorms. Can I still apply the stable marriage algorithm?

Maybe this question is a little bit foolish, but as I said I only saw this algorithm applied to quadratic arrays.

Yes, the stable marriage problem still makes sense with unequal arrays. Permit me to use men and women as opposed to students and dorms. There are different stable matchings that you can ask for resulting in different cases.

A specific stable matching is desired, either male optimal or female optimal solution
Any valid stable matching is desired
All the stable matchings are required

Let's consider the first case where we want a specific stable matching. Suppose there are $m$ men and $w$ women. Depending on which set is larger we modify the termination condition of the standard algorithm accordingly. Suppose without loss of generality we want the male optimal solution. If $m < w$ we continue until $m$ women have been proposed to. If $m > w$ then we continue until each man is either on the string of some women or has been rejected by all the women.

It's easy to see how the above algorithm can be applied to the second case where any such stable matching is required. Just have the smaller set be the one that proposes.

The third case depends on a theorem that states that if a person is unmarried in one stable matching then they are unmarried in every stable matching. The case then becomes identical to the case with equal sized sets.

More detail on all three cases as well as pseudo-code for each algorithm can be found in McVitie and Wilson's paper titled "Stable marriage assignment for unequal sets".


Better algorithm for determining if a vertex is on any cycle in a graph The problem I'm facing is the following:

  Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$.

The algorithm I can think of is to remove an edge from $u$ to one of its neighbours $v$ at a time and ask if there is still a path from $u$ to $v$ in the resulting graph, placing $(u,v)$ back before the next iteration.

I estimate the time complexity as $O(\Delta\cdot(m+n))$, with $\Delta$ being the greatest degree of the graph and $(m+n)$ for using a BFS on each iterarion.

Is there a better algorithm than this one? Does a simple DFS solve this problem and I'm just losing time with this?

BFS: Breadth-First Search
DFS: Depth-First Seatch

You can remove the vertex $u$ and all its edges, keeping a list of its neighbours.

Then you can check whether one neighbour can reach another.

Properly organized, this will explore every vertex and edge at most once. (same complexity, but without $\Delta$ repetition factor).

I let you work out the details.


Placing items into compatible bucket types to find an optimal total value Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a bucket type iff the item is able to be inserted into a bucket of that type. The goal is to insert the items into the buckets such that the total value of the inserted items is highest.

For example:

Items:
compatible with       | value
A,B,C                 | 17.641
A,B,C                 | 14.821
A,B                   | 14.274
A,B                   | 13.755
A,B                   | 12.240
A,B                   | 12.240
B,C                   | 11.960
A,B                   | 10.270
A,B,C                 | 9.958
A,B,C                 | 8.552

Buckets:
bucket type           | capacity
A                     | 2
B                     | 3
C                     | 4

Solution:
bucket                | values
A                     | 17.641, 12.240
B                     | 14.274, 13.755, 12.240
C                     | 11.960, 9.958, 8.552, 14.821

Is this problem a special case of any existing problems? I am finding it hard to envision an algorithm to solve it, but I feel that a good solution would require passing over the item list multiple times and maintaining a queue of best matches for each bucket type.

What would be the wost-case complexity of the resulting algorithm? Could a situation with 5 bucket types and 30 items explode in computational expense?

You can formalize this problem as a minimum-cost flow problem.

You construct the graph as follows.

First construct a source vertex $s$ and a sink vertex $t$.
For each item $i$, add a vertex $u_i$ and add an edge from $s$ to $u_i$ with capacity 1 and with cost equal to the negation of the value of item $i$.
For each bucket $j$, add a vertex $v_j$ and add an edge from $v_j$ to $t$ with capacity equal to the capacity of bucket $j$ and with cost 0.
If item $i$ is compatible with bucket $j$, add an edge from $u_i$ to $v_j$ with capacity 1 and with cost 0.

Now you can use some polynomial time algorithm (for example, the cycle canceling algorithm) to find an integral solution of the minimum-cost flow problem. This integral solution then shows how you assign the items: if there is a flow 1 on $(u_i, v_j)$, then assign item $i$ to bucket $j$.


Minimize the sum of gaps I have a set of $n$ objects $\{1,2,\ldots,n\}$ where object $i$ has weight $w(i)$ and we have a capacity $W$. I would like to pick a subset $S=\{a_1,\ldots,a_m\}\subseteq \{1,2,\ldots,n\}$ of the objects in order to minimize $$\sum_{j=0}^m(a_{j+1}-a_{j}-1),$$ (assuming that $a_0=0$ and $a_{m+1}=n+1$) while respecting the capacity, i.e., $$\sum_{j=1}^mw(a_j)\leq W.$$

The objective is like the sum of gaps between chosen objects.

Is this problem NP-hard or can we find a polynomial time algorithm?

For every $k$ and $\sigma$, let $A(k,\sigma)$ be the minimum of $\sum_{j=1}^m w(a_j)$ over all subsets $a_1,\ldots,a_m$ of $\{1,\ldots,k\}$ containing $k$ such that $\sum_{j=0}^m (a_{j+1} - a_j - 1) = \sigma$; note that there are $O(n)$ choices for each of $k$ and $\sigma$. You can compute $A(k,\sigma)$ for all $k,\sigma$ using dynamic programming, and use it to solve your problem in polytime.


Back invalidation to maintain inclusion in inclusive cache For an L2 cache that is strictly inclusive of the L1 cache, if a block to be evicted is also present in L1, then back invalidation is required to maintain the inclusion property.

I am interested in some details of how back invalidation is handled.

When an L2 block is evicted, is back invalidation command always sent to the L1 or only sent if the block is in the L1 cache?
If the back invalidation is only sent when the block is in L1, how does the L2 cache maintain the information that a given L2 block is also in L1?
When invalidating L1 block by back invalidation, what happens if the L1 block is dirty? Is it written back to main memory bypassing L2 (assume write-back caches and L2 is the last level cache)?

There are a broad range of design choices about how back invalidation is handled. Whether the L2 knows if a cache block is in L1 (and which L1, instruction or data) is one implementation choice with three basic options: no knowledge, approximate but conservative knowledge, and perfect knowledge.

With the no knowledge, the L2 cache will always probe both L1 caches (assuming a coherent L1 instruction cache as in x86 generally and some other processors, e.g., recent POWER processors). With approximate knowledge back invalidation commands would be filtered so they are sent to the appropriate L1 only if the block is likely to be present. With perfect knowledge only necessary back invalidations are sent to L1.

Obviously the no knowledge option provides the most straightforward implementation since there is no choice but to send the invalidation request. This can waste request bandwidth between L2 and L1 and may interfere with the availability of L1 tags for memory accesses from the core. Replication of tags or adding a read port would solve this issue, banking of the tags would reduce the frequency of conflict, adding a filter on the L1 side would also reduce access to the complete tags.

Approximate knowledge can substantially reduce the number of probes needed and reduces the amount of information that must be stored with the L2 cache and makes communication about L1 evictions less critical. The latter factor can be exploited to schedule communication of the information to minimize overhead, including interference with required communication. Since back invalidation probes are filtered, their interference with normal operation of the core is reduced giving less reason to increase the number of tag reads supported.

An approximate filter could use per L2 block information (where techniques similar to those used to compression coherence directory entries could be used) or could use a separate filter (like a Bloom filter).

Perfect knowledge (or a very close approximation) avoids unnecessary invalidation requests to L1, but effectively requires the equivalent of a directory coherence entry for each L2 cache block and every eviction from L1 must be quickly communicated to L2. A simple implementation might use one bit per L1 cache to track the presence of the block in that cache (e.g., tracking the presence in a single core's L1 instruction and data caches would use two bits per L2 block).

Another, not entirely implausible option for an L2 much larger than the L1 caches would be replicating the entire L1 cache tags, possibly in a compressed format that used the L2 set and way (excluding the bits used for indexing the L1 cache) for the replicated L1 tags.

The information can be kept current by communicating to L2 the address (or in the case of the replicated L1 tags located with L2 just the set and way could be communicated) of every L1 eviction. To include this information in the message requesting the data replacing the evicted block, the victim would have to be selected quickly. While this is not a substantial problem, it treats an L1 victim as if it was immediately replaced (i.e., an access to the victim block before the L2 cache has supplied the new block would be treated as a miss even though the data is still present).

This miss could be made merely conceptual by changing the victim choice in the rare case that the victim is accessed during this small window between victim selection and the response from L2 filling the L1 entry, but in that case an additional message must be sent to the inform L2 of the change in victim.

When the back invalidated block is dirty in L1, this block typically would be written back to memory (or sent to the requesting cache for a coherence invalidation caused by another cache attempting a write to that address; in that case whether it is also sent to memory is another implementation choice). However, when the eviction is not coherence-related, it would be quite possible to change the victim choice. In this case, the L2 might retain the dirty block, possibly requiring another back invalidation if the new victim is (or might be) in L1. Obviously, this same strategy could be used if the L1 informed the L2 cache that the block is a poor replacement choice (e.g., being more recently used than most other blocks in its L1 set).

Note that it is also possible to communicate information about L1 accesses back to the L2 cache so that an LRU-oriented L2 replacement policy would less often choose a block that is still in L1. While doing this for every L1 access or even every L1 access that influences replacement (with LRU replacement an access of the most recently used block will not change the state), would be excessively expensive, partial information could be sent when convenient. E.g., extra information could be included with a miss handling request or extra messages could be sent to L2 when the interface is otherwise idle (using a separate queue of replacement policy update information from which entries can be dropped if the interface is busy when more information is added to a full queue).

Since back-invalidations are relatively rare, the cost of unnecessary invalidation requests (i.e., when the block is not actually in a particular L1 cache) might be lower than the cost of reducing or completely avoiding them. On the other hand, with L2 cache potentially shared among several L1 caches (e.g., an L2 cache shared by two cores might include four L1 caches), avoiding the need to broadcast the invalidation to all the included L1 caches would have some attraction.

These implementation details do not appear to be documented in general, so the above is derived from reasoning about the tradeoffs.


Assuming the original instance is not easy in NP-hardness reduction Partition problem: given a non-empty finite set $P = \{p_i : i ∈ I = \{1,\dots,m\}\}$ of $m$ positive integers such that $\sum_{i=1}^m p_i = 2T$, can $I$ be partition into two disjoint subsets $I_1, I_2$ such that $\sum_{ i \in I _ 1} p_i = \sum_{ i \in I _ 2} p_i = T$?
My question is: when we deriving reduction from Partition to another problem, can we assume that $\max_{ i\in I} p_i \leq T$?

A polynomial time reduction from PARTITION to a language $L$ is a polynomial time function $f$ such that if $x$ is a Yes instance of PARTITION then $f(x) \in L$, and if $x$ is a No instance of PARTITION then $f(x) \notin L$.
If $x$ is an "easy" instance — belongs to some polynomially solvable class of instances — then $f$ can just solve it, outputting a fixed Yes or No instance of $L$. Therefore you can assume that $x$ is a "hard" instance.


Assigning one variable to another in 3 address code? 3 address code is a very common topic in many of the CS theories. I encountered it while studying Compiler Design. According to the Wikipedia article, it says -

  Each TAC instruction has at most three operands and is typically a combination of assignment and a binary operator.

Now my query, does that mean I can assign a variable to another variable(operand) even if it doesn't changes any thing, as this action doesn't violates the exact meaning of TAC(at most three operands). Example for clarity:

a = b*c - d*4

TAC

t1 = b
t2 = c
t3 = d
t4 = t1*t2
t5 = t3*4
t6 = t4 - t5
a = t6

In all the above lines, I haven't violated the TAC rule of at most 3 operands, but in the first 3 lines, I have assigned three variables to three different operands even if it isn't required.

Now technically will that be considered wrong? I know it's inefficient but is it wrong in technical terms? What I think is it's not wrong because the code optimization stage which comes after this will do the filtration if required. Still I want to know the opinions.

Three address code is an intermediate language used internally by (some) compilers. What is "right" depends on the specific rules that that compiler expects/enforces. Efficiency, as you state, is normally not an issue, as the intermediate language is designed for easy massaging and ultimately traslating into efficient target code.


Data model and database schema I need to test my understanding of the difference between the data model and database schema. According to my understanding, the data model is a description of how the data will be stored and the relationships between the data. While the schema is very similar to a database model and according to the book  "Database Management systems   " by Raghu and Johannes " A description of data in terms of a data model is called schema"  and it's a template of how the data will be stored. Is that right?

A data model is set of general abstraction mechanisms: for instance you have the relational data model, with mechanisms as the relation, primary and foreign keys, etc. Or an object oriented data model with mechanisms like classes, aggregation, generalization, etc.
The schema instead is the description of a particular slice of reality for modeling purposes, for instance to build a database, expressed using a specific data model.


Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28) My question is related to the exercise 4.28 in the book of Nielsen and Chuang (Quantum Computation and Quantum Information). Here is the exercise

For $U=V^2$ with $V$ unitary, construct a $C^5(U)$ gate analogous to that
in Figure 4.10, but using no work qubits. You may use controlled-$V$ and
controlled-$V^{\dagger}$ gates.

I think the exercise in the current form is not possible to solved. Since any usage of a controlled-$V$ or $V^{\dagger}$ gate gives even 4 cases (with case I mean a combination of qubits) where $V$ or $V^{\dagger}$ is applied. So we can increase the number of applied $V$ gates with any usage of a controlled-$V$ or decrease the number of applied $V^{\dagger}$ gates with any usage of a controlled-$V^{\dagger}$ by 4. But to obtain the controlled-$U$ gate, we may only have $2$ usages of a $V$ gate. Thus any way we apply the controlled-$V$ or $V^{\dagger}$ gates, in the end we will always have more than 2 cases where a $V$ or $V^{\dagger}$ is applied (with applying I mean that it does not contract with another controlled gate, so it will really be applied at the end).

Note that this problem does not occur for controlled-X gate since an addition can be though as an addition modulo 2, therefore we can decrease the numbers of cases where a qubit is switched.

Since I think that this chapter is heavily influenced by the paper https://arxiv.org/abs/quant-ph/9503016.pdf which constructs a $C^3(U)$ with controlled-$V$ gates where $V^4=U$, I think it should be $V^16=U$ in the exercise. However I am not certain if there really does not exist a solution, maybe one using maybe gates creating a superposition like the Hadamard gate. So my question is, if someone has a solution for this exercise or a proof that it is impossible to do.


Matching two sets when you cannot do within-set comparisons Suppose you have two lists, A and B, each with length n.  The elements of A cannot be compared with other elements of A--there is no order relation among them--and likewise for B.  However, elements of A can be compared with elements of B.  So for instance, suppose we have a function compareTo(a,b) where a is an element of A and b is an element of B.  If a is less than b it returns -1, if they're equivalent it returns 0, and if a is greater it returns 1.

Further suppose that a perfect matching exists between the elements of A and B, in the sense that for every element of A there is precisely one element of B such that compareTo(a,b) evaluates to 0.  And vice versa (for each b there is precisely one a such that they're equivalent).

How do we write an efficient algorithm to find the perfect matching?

My attempts: Well, there's the naive algorithm which takes an element of A and finds its corresponding element of B, repeating until all matchings have been found.  This runs in O(n^2) so we want to beat this.

It sounds kind of like Gale-Shapley but an input to that algorithm is a preference list.  In this setting we have ties, where preference lists don't.  And even generating something like a preference list would take n^2 time.  Since it is fundamental to Gale-Shapley that members of one set propose to their highest preferences of the other, this doesn't seem applicable to the given problem.

We could try to use an element of A to partition the set B and try to divide-and-conquer.  But you would only have divided B and wouldn't know which elements of A to give to the recursive call.  You could then try to use B to partition A.  To describe this more, let's give a specific example.  Suppose A = [a1,a2,a3,a4] and B = [b4,b1,b3,b2] and suppose that ai < bj if i < j, and likewise for = and >.  We could arbitrarily select a1 and then use it to partition B into the elements that come out greater in the comparison, [b4,b3,b2] and the elements that come out smaller [].  Since along the we way we found that a1 matched b1 we make that assignment and eliminate them from the rest of the algorithm.  Now that we know a1 was quivalent to b1 we can use b1 to partition A into [] and [a2,a3,a4].  We recursively call the algorithm on the smaller sets [], [] which satisfies the conditions: they have the same length and have perfect matching.  And recursively call the algorithm on the larger sets [a2,a3,a4], [b4,b3,b2] which also have the same length and have a perfect matching.

I think this algorithm is correct, but in the worst case it doesn't beat the worst-case runtime of the naive algorithm.  So I don't think I'm on the right track here.

This is the so-called "nuts and bolts" problem, and your pivoting approach can be shown (under uniform choices of pivots) to give a randomized algorithm with expected query complexity $O(n \log n)$, using the analysis of Quicksort as a template.

Fast deterministic algorithms are less obvious. The first true breakthrough paper I know of for this is that of Alon et. al., which shows one simple algorithm with query complexity  $O(n^{1.5} \sqrt{\log n})$ (basically by combining the quicksort approach you describe with a moderately expensive pivot-finding procedure), and another much more involved one with complexity $O(n\,\textrm{polylog}\,n)$ (also based on quicksort, but the identification of the pivot goes through some more hardcore expander machinery).

Subsequently, Komlós et. al. found an asymptotically optimal algorithm with $O(n \log n)$ deterministic query complexity using a different approach based on sorting nets.


Check if current interval is overlapping some intervals, or is being overlapped Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l_{i}, r_{i}$, both inclusive, the interval $i$ means that all elements in the range $[l_i, r_i]$ are covered. Our task is to check for any of those $N$ intervals is the interval $i$, or the range $[l_i, r_i]$ being covered twice or more. Look in the examples to make it clear.

Example

$N = 3$, we have the intervals $I = \{ (1, 3), (4, 6), (1, 7) \}$. Let's illustrate the intervals

1 2 3 4 5 6 7 8 9 10...
-----               -> Interval 1
      -----         -> Interval 2
-------------       -> Interval 3

We can see that the elements that are being covered by Intervals 1 and 2, are already covered with Interval 3, so we should return one of those indexes.

Please note that $K = 10^9$, so we cannot store the whole array.

What I think

If we were able to store the whole array of $K$ members, we could easily solve with lazy propagation, and range minimum queries, but since we cannot do that, I think that we should create dynamic segment tree where we will keep only the ranges we need to store the value for.

For example, if we need only the range $[1, 128]$ we do not need to store the ranges $[1, 63]$ and $[64, 128]$. This will save memory and time, but is it enough fast to solve this problem, and what will be the time complexity for this solution if we assume that $N \leq 10^5$.

Hint: Sort $\{l_1,r_1,\ldots,l_N,r_N\}$ and replace the sorted list with $1,\ldots,2N$ to effectively reduce $K$ to $2N$.

(There might be better ways of solving the problem, but this reduction at least gets rid of the dependence on $K$.)


What is the time complexity of this algorithm? In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed:

She represented the cost of the algorithm  by the following sum:

$\sum\limits_{i=1}^n \sum\limits_{j=1}^i\sum\limits_{k=1}^j 3 = \frac{n^3}{2} + \frac{3n^2}{2} + n $

The step by step used to solve the sum bellow:

n = 10
count=0
for i in range (0, n):
    for j in range (0, i):
        for k in range (0, j):
            count+=3

print count

Then, I wrote a algorithm in python to verify the solution, but it not produce the expected output, for example, for n = 10 we expected 660 operations, but it print 360.

Change the index to start with 1 like in the bellow didn't worked either, in fact it got more distance from the expected (252).

n = 10
count=0
for i in range (1, n):
    for j in range (1, i):
        for k in range (1, j):
            count+=3

print count

In Python, range(0,n) iterates through the values 0, 1, 2, .., n-1 (but not n).  Therefore, your summation should have been

$$\sum_{i=0}^{n-1} \cdots$$

rather than

$$\sum_{i=1}^{n} \cdots$$

and similarly for the other sums as well.


About the pseudo polynomial complexity of the KnapSack 0/1 problem I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some doubts.
A question that frequently arises when discussing the complexity of the dynamic programming solution for the KS problem is something like ¿Why $O(n \cdot W)$ is not considered polynomial?.
The common answer is that, by definition, we are concerned with the running time of an algorithm as a function of the size of the input. So, while is correct to say the running time is bounded by a polynomial in the value of $W$, is not polynomial in the size of $W$, because in fact what we have is $O(n \cdot 2^W)$.
Here we can also ask ¿Why not $O(2^n \cdot 2^W)$?, i.e. by the same reasoning $n$ should also be exponential in the length of the input. But the "trick" is that it seems $n$ is usually (always?) not considered part of the input at all. Instead, the input is (by convention i guess) just a list of $n$ weights, a list of $n$ values, and capacity $W$. Indeed, we don't need $n$ itself in the input.
Questions:

Suppose we have $n$ itself in the input, as nothing stops me of doing it in this way. The algorithm loops from $0$ to $n$ in the same way it loops from $0$ to $W$. Now, is correct to say the running time is $O(2^n \cdot 2^W)$ ?.
But if (1) is the correct, i dont think this algorithm with $n$ in the input have the same asymptotic behavior as the common one. How $O(2^n \cdot 2^W)=O(2^{n+W})$ compare with $O(n \cdot 2^W)$ ?.
Consider the usual naive recursive algorithm for the KS 0/1 problem. This is said to be $O(2^n)$, because in the worst case two recursive calls on $n-1$ are needed. In this case, $n$ is clearly in the input, but we are considering $n$ as a value when doing the recurrence analysis. So, considering earlier discussion, i'm tempted to say that in fact we have $O(2^{(2^n)})$ which is double exponential and not just exponential ... but does this make sense?

Whether $n$ is "included in the input" or not is irrelevant. No "tricks" are being used to sneakily hide $n$ from the input by implicitly including it as the length of a list.
The input is at least $n$ bits long because it must include a list of all the values and weights of items. If we are not given the values and weights of the items as part of the input, then how are we supposed to solve the problem (if we do not know the weight/value of some items)?
Now, since we know that the input has length (in bits) at least $n$, any running time of the form $n, n^2, n^3,...$ is polynomial in the length of the input.
However, the length of a (reasonable representation of the input) is at most $O(n\log W)$ (assuming the values of the items are on the same order of magnitude as their weights). For every item we must give the weight and value, and this can be done with $\log W$ bits per item (by giving the binary representation of the weight/value).
As Yuval noted, $nW$ is not polynomial in $n\log W$.
It does not matter if we consider the input as the lists only or the lists "together with" $n$. If we also include $n$ explicitly, it just makes the input $\log n$ bits longer. But since the input is already at least $n$ bits long, having $\log n$ extra bits makes no difference.


What's the connection between the two "Fast Walsh Transform"? First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$ in $O(n \log n)$ time, using an algorithm called Fast Walsh Transform, where $n$ represents the length of the binary digits.

However, when looking at wikipedia page, it says that the Walsh Transform is to accelerate the evaluation of an $n \times n$ Matrix called Walsh Matrix. I also found it reasonable.

My question is, what's the connection between the two evaluations? I know that a convolution is a linear transformation and can be represented as a vector multiplied by a matrix. But where's the matrix in the First convolution? I am so confused, and does it represent that some multiplications with specified matrixed could be accelerated to $O(n \log n)$? (Thus the matrix is $n \times n$)

Suppose that $A$ and $B$ are vectors of length $n$, where $n$ is a power of 2. We index $A$ and $B$ using binary vectors of length $\log_2 n$, and define their convolution $C$ as
$$
C_i = \sum_{j \oplus k = i} A_j B_k.
$$

You can calculate the convolution of $A$ and $B$ using the following algorithm:

Compute the Walsh transform of $A$: $\alpha = H_n A$.
Compute the Walsh transform of $B$: $\beta = H_n B$.
Multiply $\alpha$ and $\beta$ pointwise: $\gamma(S) = \alpha(S)\beta(S)$ for all $S$.
Compute the inverse Walsh transform of $\gamma$: $C = H_n^{-1} \gamma$.

(Note that up to normalization, $H_n^{-1}$ and $H_n$ are the same matrix.)

The way we compute the convolution of $A$ and $B$ is using the Walsh transform and its inverse. The Walsh transform itself simply consists of multiplying a vector by the Walsh matrix, which can be done in $O(n\log n)$ time. Since the third step takes only $O(n)$ time, the entire algorithm runs in $O(n\log n)$.


Why do we care about random Boolean SAT formula? I've been looking for a reference for the above question.

As far as I know the answer is:

If we can make a solver that is efficient for all randomly generated instances, it should be efficient for any instance.

i.e. if we make a solver that doesnt rely on any inherent structure, it will always be efficient.

Is this correct? Either way, does anyone have a reference to a paper I can cite for the answer.

If your solver is efficient for random 3-SAT, it by no means entails that it is efficient for an arbitrary 3-SAT instance. Randomly generated instances are very different from instances that arise in practice (meaning they are structured differently). For instance, you can read about the phase transition in random $k$-SAT: depending on the clause-to-variable ratio, an instance can be easy (not constrained enough, or too constrained) or hard (in some sense critically constrained). This phenomenon is rather fascinating in itself.

You can always argue that if you have a solver that does not exploit any structure of the input and is always rather magically efficient, much of the theory we have developed around SAT is useless. Unfortunately, many people have worked a lot on the problem, and we are still unable to give an efficient algorithm for e.g. SAT (not to mention an algorithm that would be efficient in practice as well!). So how do we cope with this? We look at e.g. structural aspects of the input: what can we leverage? How can we be fast at least sometimes? Because we can't solve a problem we care about, we look for other approaches and angles of attack.

I think the main reasons we have been interested in random $k$-SAT is that first, such instances are easy to generate to test our solvers. We have also learned that random instances are very different from instances that arise in practice (and of course those are the instances we often care about). This has increased our understanding of the nature of computation, heuristics, complexity, and ultimately made us able to build faster solvers as well.


Hash for verifying both compressed and uncompressed data? Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart?

Trivially one could just use a hash function twice (once on the uncompressed version and again on the compressed version) and concatenate the outputs, or use a hash function that internally does that, but I wonder if it's possible otherwise.

For example, imagine we've got these functions:

Hash getHash(byte[] data);
byte[] compress(byte[] data);
byte[] decompress(byte[] data);
bool verify(byte[] data, Hash hash);

...then I'm looking for these properties for a nontrivial byte array D (that is uncompressed):

verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true
D == decompress(compress(D)) for all D, i.e. lossless compression
verify(E, getHash(D)) == false "most of the time" when E != D, i.e. collision "resistant" hashing

This could be useful when verifying persisted compressed data: you could verify the correctness of the compression algorithm and of the uncompressed data both at the same time without having to decompress it or store multiple hashes.

I'm not sure where to start looking for this. I think what I'm describing is some kind of homomorphism but apparently I need to level up my search skills. It seems like a Difficult Problem™; for example, the Deflate algorithm outputs data structures like a Huffman tree/table, and the mathematical relationships of serialized data structures being run through hash functions aren't immediately obvious to this OP.

In most situations you probably don't want to have D and compress(D) to have the same hash value, as that leads to hash collisions.  Usually hash functions are designed to avoid hash collisions -- and this is a good thing.  For instance, in cryptographic contexts, any hash scheme that has the properties you ask for would automatically be considered cryptographically insecure.

Therefore, trying to design a hash function with this property is probably a bad idea.  Instead, you should probably use the alternative solution: when you verify a hash value, hash both the data D and the compressed version compress(D) and see if either of those hash digests match the expected value.  That's probably a much better solution in practice.

If you absolutely must achieve this by artificially introducing collisions into your hash, here is a way you can do it.  Disclaimer: This is totally theoretical; it is not useful in practice.

Define the verify procedure as follows:

Verify(D, Y):
1. If Hash(D)==Y or Hash(Compress(D))==Y or Hash(Uncompress(D))==Y, return true; otherwise, return false.

Yes, this is totally trivial.

No, I don't think you'll find anything that is faster than this and that also satisfies the properties to be a good hash function.  Hash functions are specifically designed to avoid having any mathematical structure, while at the same time being very fast.  Mathematical structure is considered a weakness in a hash function.  In contrast, you are asking for a hash function with some structure.  Inserting such artificial structure into the hash function might be possible, but the natural ways of doing it probably will either introduce lots of bias into the hash function (e.g., lots of collisions) or slow it down a lot.

To put it another way, right now hash functions are optimized to meet two criteria:

Be fast.
Be "random-looking" (few collisions, unbiased, etc).

You are proposing to look for a hash function that meets three criteria:

Be fast.
Be "random-looking" (few collisions, unbiased, etc).
Also, satisfy the additional properties you requested that verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true.

Obviously, it's harder to meet three criteria than to meet two.  If you want to meet three criteria, something will have to give: and in your situation, that means the resulting hash function will either be slower or less "random-looking" than standard hash functions (probably significantly so).

So, I don't expect there's any better solution for what you want.  Instead, just do the natural solution you mention of hashing twice.


Shuffling Bits For Uniform Distribution I am writing an hashing algorithm to be used in key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to be retrieved OR given a key and value we determine a location to store the value. We want the keys to be designed/modified such that whole storage space is uniformly used. In my application, if there too many collisions, we would be forced to evict certain data items. The input is a key and output of the mechanism sought is a "better key" that reduces the collision.
I assume that key would not have more than 64 bits. For uniform distribution in the data store I want key bits to be shuffled appropriately so that all the data do not collide in the same slot of data store.
The approach I am thinking is to have a predefined padding table, from where we take rest of the bits and shuffle whole thing to produce a new key. For Example, for a smaller key value which can be accommodated in a byte, we pad rest of seven bytes (for 8 byte word). In case of 2 byte long key, we have another pad of 6 bytes and so on. I am not sure if this is an efficient way to do the job, but exploring should worth it.
If this is a good way, want to understand from you, how can I create such a table? What bits should be filled in it etc. Will be glad if there any pointers.
The idea of padding bits is to create uniform distribution. For Example, if the key is a very small number 0xab (say) then the padding bits could be 0x12345cdeadbeef00 such that we could OR the two things to form 0x12345cdeadbeefab. Now we shuffle the whole thing such that the resultant key is uniformly distributed in the storage space.

It sounds like you might be trying to re-invent double-hashing.  I recommend reading up on standard strategies for hash tables, including open addressing, closed addressing, cuckoo hashing, 2-choice hashing, and so on.


Proving a sorting operation in type system I want to know how far a type system in a programming language can be beneficial. For example, I know that in a dependently typed programming language, we can create a Vector class incorporating size of the vector in the type signature. It is like a de-facto example. We can also write a function append using those signatures so that compiler proves resulting list's size will be the sum of the input lists.

Is there a way to encode, for example, in a sorting algorithm's type signature so that compiler guarantees resulting list to be a permutation of the input list? How this can be done, if it is possible?

Yes, it is possible to express a precise type for a sorting routine, such that any function having that type must indeed sort the input list.

While there might be a more advanced and elegant solution, I'll sketch an elementary one, only.

We will use a Coq-like notation. We start by defining a predicate requiring that f: nat -> nat acts as a permutation on $0..n-1$:

Definition permutation (n: nat) (f: nat -> nat): Prop :=
  (* once restricted, its codomain is 0..n-1 *)
  (forall m, m < n -> f m < n) /\
  (* it is injective, hence surjective *)
  (forall m1 m2, m1 < n -> m2 < n -> f m1 = f m2 -> m1 = m2) .

A simple lemma can easily be proved.

Lemma lem1: forall n f, permutation n f -> m < n -> f m < n.
... (* from the def *)

We define what is the $m$th element of a list having length $n$. This function requires a proof h stating that $m<n$ indeed holds.

Definition nth {A} {n} (l: list A n) m (h : m < n): A :=
... (* recursion over n *)

Given an ordering on A, we can express that a list is sorted:

Definition ordering (A: Type) :=
   { leq: A->A->bool |
     (* axioms for ordering *)
     (forall a, leq a a = true) /\
     (forall a b c, leq a b = true -> leq b c = true -> leq a c = true) /\
     (forall a b, leq a b = true -> leq b a = true -> a = b)
    } .

Definition sorted {A} {n} (o: ordering A) (l: list A n): Prop :=
...

Finally here's the type for a sorting algorithm:

Definition mysort (A: Type) (o: ordering A) (n: nat) (l: list A n):
   {s: list A n | sorted o s /\
                  exists f (p: permutation n f),
                  forall (m: nat) (h: m < n),
                     nth l m h = nth s (f m) (lem1 n f p h) } :=
... (* the sorting algorithm, and a certificate for its output *)

The output type states that the result list s is $n$ elements long, it is sorted, and that there's a permutation of $0..n-1$ that maps the elements in the input list l to the ones in the output list s. Note that we have to invoke the lemma above to prove $f(m) < n$, which is required by nth.

Note however that it is the user, i.e. the programmer, which has to prove their sorting algorithm correct. The compiler will not simply verify that the sorting is correct: all it does is checking a provided proof. Indeed, the compiler can not do much more than that: semantic properties such as "this program is a sorting algorithm" are undecidable (by Rice theorem), so we can not hope to make the proving step fully automatic.

In the far, far future, we can still hope that automatic theorem provers get so smart that "most" practically used algorithms can be automatically proved correct. The Rice theorem only states that this can not be done in all cases. All we can hope for is a correct, widely applicable, but inherently incomplete system.

As a final note, it is sometimes forgotten that even simple type systems are incomplete! E.g. even in Java

int f(int x) {
   if (x+2 != 2+x)
      return "Houston, we have a problem!";
   return 42;
}

is semantically type safe (it always returns an integer), but the type checker will complain about the unreachable return.


An infinite decidable language that is a subset of $\overline { A_{TM}}$ What is an example of an infinite decidable language $L$, such that $L \subseteq \overline { A_{TM}}$ (which is known to be not Turing Recognizable)?

And of coures some evidence that L is indeed decidable and a subet as required

Fix a special TM $M_d$ which infinitely loops on any input $x$. In other words, $M_d$ does not care about input $x$ and always infinitely loops on any input. Such a TM could consist of a single state and instructions such as $\delta(q_0, a) = (q_0,a)$ for all input symbols $a \in \Sigma$,  which tells $M$ to stay in the same state and never move the head. So, given its description $\langle M \rangle$ it is easy to recognize this machine by inspecting its states and instructions.

Since $M_d$ never halts on any input $x$ the following language must be infinite

$$L = \{\langle M_d,x \rangle \mid x \in \Sigma^*, M_d \text{ is the fixed TM} \}$$. This language is also a subset of $\overline{A_{TM}}$ since $M_d$ never halts on any input $x$. Thus, if we are given $\langle M_i,x \rangle$ we simply decide by checking whether $i=d$, i.e., whether $M_i$ is the same as $M_d$ by inspecting $M_i$'s states and instructions meaning $L$ is decidable.


Using Induction to prove that $n^3log^4n=O(n^4)$ I need to prove the following asymptotic relation for the purpose of cacluating a recurrence relation:
$$n^3log^4n=O(n^4)$$
I tried and failed to do it with induction, which, if possible using basic Calculus 1 level math, I would like you to help me with.
I am not required to do it with induciton or anything, I just wondered if I can do it.

I was able to prove it though, in a differet manner:
$$f \in o(g) \Rightarrow f \in O(g)$$
$$lim_{n\to \infty} \frac{n^3log^4n}{n^4}=0$$
Using L'Hôpital's rule 4 times, which proves that:
$$n^3log^4n=o(n^4)$$
By the definitino of $o$.

Therefore it also follows that $$n^3log^4n=O(n^4)$$

For the basis of the induction let $n=1$ and with $c=1$:
$$f(1) = 1^3log^4(1) = 0 \leq 1=1^4 \cdot 1=c \cdot g(1)$$
From here I think that it would be enough to show that:
$$log^4(n) \leq n$$
Although I am not sure how to continue from here.

You showed that f (n) = o (g (n)). That's it. There is nothing else to prove.

If you look at the definition of o (f (n)) and O (f (n)), they are almost identical except one says "for every eps > 0" and the other says "there is one c > 0". You can take every single eps of the little-o definition and use it as the c in the big-O definition.


What does $\sigma(t_0, \ldots, t_{n-1}) \in \mathcal{T}_{\Sigma}^{0}$ in this paper mean? The paper is "Mappings and Grammars on Trees" by William C. Rounds. There was a definition of ranked alphabet in page 3 and I can't understand the second part of the definition.

Definition. A ranked alphabet is a pair $(\Sigma, r)$ where $\Sigma$ is finite, and $r: \Sigma \rightarrow \mathbb{N}$.
We set $\Sigma_n = r^{-1}\{n\}$
Let $(\Sigma, r)$ be a ranked alphabet. The set $\mathcal{T}_{\Sigma}^{0}$ (the constant $\Sigma$-terms) is the smallest set of strings such that:
$\ldots$
(b) if $t_0, \ldots, t_{n-1} \in T_{\Sigma}^{0}$, and $\sigma \in \Sigma_{n}$, then $\sigma(t_0, \ldots, t_{n-1}) \in \mathcal{T}_{\Sigma}^{0}$

The $\sigma$ should be set of the alphabet which is ranked $n$, how can a set of alphabet become a function?
Thank you.

You're over-thinking it. It just says that, if $t_0$, ..., $t_{n-1}$ are in $T^0_\Sigma$ and $\sigma$ is a symbol in the alphabet $\Sigma_n$, then the string consisting of $\sigma$, followed by $($, followed by... is in $T^0_\Sigma$


How do you calculate the training error and validation error of a linear regression model? I have a linear regression model that I've implemented using Gradient Descent and my cost function is a Sum of Squares Error function. I've split my full dataset into three datasets, a training set, a validation set, and a testing set. I am not sure how to calculate the training error and validation error (and the difference between the two).

Is the training error the Residual Sum of Squares error calculated using the training dataset?
Is the validation error the Residual Sum of Squares error calculated using the validation dataset?
What is the test set for exactly (I've learned the model using the training set, from the textbooks I've read I think this is the set to use to learn the model)?

Any help in clearing up these points is much appreciated.

Yes. Yes. The test set is used to get an unbiased measure of the performance of your model. This is explained in many sources, better than I can explain here; I won't try to repeat them. See, e.g., https://en.wikipedia.org/wiki/Training,_validation,_and_test_sets, https://stats.stackexchange.com/a/104750/2921, or standard textbooks.


What do you call a function from symbols of alphabet to languages? Speaking of context-free (and maybe regular? or just any?) languages, what do you call a function defined as follows:

Let $\Sigma$ be the alphabet of $L$, $\forall \sigma \in \Sigma: f(\sigma) = L'$, where $L'$ is some language. I also met this definition: $f:\Sigma \to 2^{\Delta^*}$.

The reason I'm asking this is because I study in a language which is even more foreign to me than English, and it's hard to find what the terminology in the book means. I've only encountered this in connection to context-free languages, but since I don't really know what I'm looking at, I can't tell if that's something specific to them (my guess though is that it's not).

In the book I'm reading from, (which also happens to be in Hebrew) the word used to describe this concept is "הצבה", literally meaning "substitution" or "positioning", "fixing something in place".

It looks like it refers to a substitution, but that the given definition is incomplete.

Anyway, in formal language theory, people often use monoid morphisms between free monoids. To avoid overloading the term "morphism", a monoid morphism from a free monoid $A^*$ into the monoid $2^{B^*}$ of languages of $B^*$ (under concatenation product of languages) is often called a substitution.

Now, since a morphism from $A^*$ into any monoid is entirely defined by the image of its letters, a substitution from $A^*$ to $B^*$ might be given as a map $\sigma: A \to 2^{B^*}$. But then it is extended to a map $A^* \to 2^{B^*}$ by setting $\sigma(1) = \{1\}$ and $\sigma(a_1 \dotsm a_n) = \sigma(a_1) \dotsm \sigma(a_1)$.

Reference. Page 5 in First four chapters of
Berstel's book Transductions and Context-Free Languages, Teubner (1979).
(Page 13 in the printed version)


What algorithm will tell us how to divide-up a round robin tournament into rounds? We are designing a tournament for a game such as soccer (football) or chess. The tournament is "round robin." By "round robin," we mean that every team gets to play against each other team exactly once. For example, if you are playing, and there are 8 other teams, then you will play exactly 8 matches before the tournament is over.

A single "match" is played with 2 teams competing against each other. For example, (team 3 against team 9) is a single match. Formally, a match is a set of two integers, such as {3, 9}.

The tournament is divided into rounds. All teams who are scheduled to play during the current round play simultaneously. If team 2 is playing team 5 during round 10, then team 2 cannot simultaneously play against team 3 during the same round. In different notation, if {2, 5} ∈ R10 then {2, 3} ∉ R10. In general, no round is allowed to contain the same team more than once.

Formally, a round is a set of matches. For example, $R = \{\{1, 2\}, \{3, 5\}, \{4, 6\}\}$ is a round. A valid round $R$ is a round such that for every two distinct matches, M1 and M2, in $R$, $M1$ ∩ $M2$ is the empty set. This captures the idea that no round is allowed to contain the same team more than once.

For some natural number, $n$, the tournament has:

$2*n$ teams
$(2*n-1)$ rounds
$n$ matches per round.

The algorithm we seek, for any even number of teams, will output a a description of which matches to have in each round.

For example, for 6 teams, the algorithm output might be:

round 1: {1, 2}, {3, 5}, {4, 6}
round 2: {1, 3}, {2, 4}, {5, 6}
round 3: {1, 4}, {2, 5}, {3, 6}
round 4: {1, 5}, {2, 6}, {3, 4}
round 5: {1, 6}, {2, 3}, {4, 5}

Note that every team plays at most once per round, and that every team plays every opposing team exactly once before the tournament is over.

You want the algorithm for constructing a Graeco-Latin square, or any of the algorithms described in https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm


Why is the OS design able to reduce power consumption? I have read that OSes like Android and iOS are somehow optimised to improve battery life.

My understanding is that a CPU executes a certain number of operations in a certain time, so I would think that you can speed up applications by reducing number of operations required, but since the CPU will still do x operations in y time, that should not affect power?

Also, if a process occupies more RAM, does it consume more power?

Common CPUs that go into smartphones, laptops and even desktop PCs have a variable clock rate. When the scheduler detects that it has idle time, it can reduce the clock rate, and increase it again if there are more processes competing for CPU time.

CPUs optimized for battery-powered devices tend to be composed of many functional components that each have their own clock (example: ARM Cortex A8). When one component is idle, the operating system can turn it off (or reduce its clock), which saves power. For example, on many multicore CPUs (such as the ones in high-end mobile devices), each core can be turned on or off separately. ARM is particularly good at this game, which is one of the reasons why most smartphones have ARM CPUs.

Varying the clock rate or turning off the clock of electronic components is known as power management. It tends to be a complex part of writing and optimizing an operating system for a battery-powered device, with many dependencies on the exact hardware model.

What goes for the CPU goes for peripherals too. The backlit display is a major consumer of power on a smartphone, for example, followed by the radio. The CPU operating system may play a role in power management of peripherals; secondary chips also runs their own firmware which performs power management as well.

Applications have their part to play in keeping power consumption down: they must allow the operating system to do its thing. The worst thing an application can do is polling — running a loop like while (not_ready()) {}. Even introducing a small delay as in while (not_ready()) {usleep(100);} doesn't help as it doesn't allow enough time for the processor to go into low-power mode, or if it does, each unfruitful wake up means wasted energy. Thus the operating system APIs must be designed so that applications never need to poll, but can instead subscribe to some kind of event mechanism and remain idle until they are notified of a relevant event. Applications in turn need to take advantage of such mechanisms, so the design of the whole software stack has an impact on power consumption.

You can get some information about what's responsible for your PC's power consumption with Intel's Powertop utility. Smartphones typically have a way to see how much power applications have been consuming as well. Accounting for power consumption by application precisely is difficult: if a component wakes up for two applications, the wake-up time may be accounted to one of them somewhat arbitrarily or to neither; peripherals' power consumption are also not always be easily tracked to the application responsible.

A RAM chip doesn't know which of its bits store data of an active process, so it can't be turned off selectively in this manner. A process's power consumption isn't related to the amount of memory that it uses (except inasmuch as the RAM accesses consume power, but re-using the same memory or using different RAM areas makes no difference with respect to power consumption).


On proving NP-completeness by reduction to 3-partition problem Consider a problem $X$ can be reduced to 3-partition problem. So, when 3-partition has a solution then $X$ has a solution. But if 3-partition does not have a solution, they $X$ may or may not have a solution. In this case, is it legal to say that the problem $X$ is np-complete?

No, that doesn't prove NP-completeness.

The thing you describe isn't a reduction.  It must be that the instance of $X$ has a solution if, and only if, the instance of 3-partition has a solution.
Reducing $X$ to 3-partition just proves that $X$ is in NP.  To prove completeness, you need to reduce an NP-complete problem to $X$.

I suggest that you revise the basic concepts from your class notes, textbook or online resources.


Formulating a recursion using mathematical notation So I'm assigned a task that involves formulating a quite complex recursion of several variables using 'mathematical notation'. The assignment is quite sparse when it comes to additional information, but below is the code anyway;

int partDist(String w1, String w2, int w1len, int w2len) {
if (w1len == 0)
  return w2len;
if (w2len == 0)
  return w1len;
int res = partDist(w1, w2, w1len - 1, w2len - 1) +
(w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);
int addLetter = partDist(w1, w2, w1len - 1, w2len) + 1;
if (addLetter < res)
  res = addLetter;
int deleteLetter = partDist(w1, w2, w1len, w2len - 1) + 1;
if (deleteLetter < res)
  res = deleteLetter;
return res;

}

The method calculates the amount of the following operations it takes to get from String w1 to w2 and vice-versa;

Adding a letter
Removing a letter
Change an already exisiting letter

I'm not really sure where to proceed from there. I've managed to write something along the lines of a mathematic formula with conditionals but it just looks really messy and with a lot of hand-written conditions.

Abbreviating partDist to $D$, you are looking for a formula for $D(w_1,w_2)$. Given the form of the recursion, it will be easier to state a formula for $D(x_1\sigma_1,x_2\sigma_2)$, where $\sigma_1,\sigma_2$ are symbols (i.e., characters) and $x_1,x_2$ are strings; additional base cases will cover the cases in which $w_i$ cannot be decomposed as $x_i\sigma_i$. The formula will be a minimum of two or three terms, depending on whether $\sigma_1 = \sigma_2$ or not.

Alternatively, you can write a recursion for
$$ D(x_1x_2\ldots x_n,y_1y_2\ldots y_m). $$
Here the base cases would be $n=0$ and $m=0$, and in the recursive case you will have to distinguish between $x_n = y_m$ and $x_n \leq y_m$. Here all the $x_i$ and $y_j$ are symbols.