Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)? This problem is from  Algorithms, problem 2

The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($log n$) time algorithm to find the median of the 2$n$ lists.'

My question is regarding the case where median($X$) is less than the median($Y$).

Here is the proof that the authors(gave) that any element in $X$ less than median($X$) cannot be the median of the two lists.

    Suppose an element e is in $A$ and e $\lt$ median($X$). Then there will be less than $\frac12n$ elements less than e(in $X$)
    Since e $\lt$ median($X$) $\lt$ median($Y$) there are less than $\frac12n$ elements less than e(in $B$)

Because of 1 and 2, the median cannot be any element in $A$ that is less than median($A$)

I agree with every step in the proof and with that statement. However, here is the diagram of possibilities where the median of the two lists can be

Based off that proof, I understand why all the elements  below the median of $A$ and in $A$ cannot be the median of the two lists. But what justification did author use to eliminate median($X$) as a possibility? It wasn't included in the shaded region.

$X_m$ and $Y_m$ are not shaded, because each of them is potentially the median of $X \cup Y$.

Consider two examples (Below I take the $\lfloor (n+1)/2 \rfloor$-th element as the median of an array of size $n$):

(1) $X = \{ 2, 4, 6 \}$ and $Y = \{ 3, 5, 7 \}$.

(2) $X = \{ 2, 4, 6 , 8 \}$ and $Y = \{ 3, 5, 7, 9 \}$.

I think the caption of Figure 1 is wrong: median of two sorted lists lies in the unshaded region.


Is the IO monad technically incorrect? On the haskell wiki there is the following example of conditional usage of the IO monad (see here).

when :: Bool -> IO () -> IO ()
when condition action world =
    if condition
      then action world
      else ((), world)

Note that in this example, the definition of IO a is taken to be RealWorld -> (a, RealWorld) to make everything more understandable.

This snippet conditionally executes an action in the IO monad. Now, assuming that condition is False, the action action should never be executed. Using lazy semantics this would indeed be the case. However, it is noted here that Haskell is technically speaking non-strict. This means that the compiler is allowed to, for example, preemptively run action world on a different thread, and later throw away that computation when it discovers it doesn't need it. However, by that point the side-effects will already have happened.

Now, one might implement the IO monad in such a way that side-effects are only propagated when the whole program has finished, and we know exactly which side-effects should be executed. This is not the case, however, because it is possible to write infinite programs in Haskell, that clearly have intermediate side-effects.

Does this mean that the IO monad is technically wrong, or is there something else preventing this from happening?

This is a suggested "interpretation" of the IO monad. If you want to take this "interpretation" seriously, then you need to take "RealWorld" seriously. It's irrelevant whether action world gets speculatively evaluated or not, action doesn't have any side-effects, its effects, if any, are handled by returning a new state of the universe where those effects have occurred, e.g. a network packet has been sent. However, the result of the function is ((),world) and therefore the new state of the universe is world. We don't use the new universe that we may have speculatively evaluated on the side. The state of the universe is world.

You probably have a hard time taking that seriously. There are many ways this is at best superficially paradoxical and nonsensical. Concurrency is especially either non-obvious or crazy with this perspective.

"Wait, wait," you say. "RealWorld is just a 'token'. It's not actually the state of the entire universe." Okay, then this "interpretation" explains nothing. Nevertheless, as an implementation detail, this is how GHC models IO.1 However, this means that we do have magical "functions" that actually do have side-effects and this model provides no guidance to their meaning. And, since these functions actually have side-effects, the concern you raise is completely on point. GHC does have to go out of its way to make sure RealWorld and these special functions are not optimized in ways that change the intended behavior of the program.

Personally (as is probably evident by now), I think this "world-passing" model of IO is just useless and confusing as a pedagogical tool. (Whether it's useful for implementation, I don't know. For GHC, I think it is more of a historical artifact.)

One alternative approach is to view IO as a describing requests with response handlers. There are several ways of doing this. Probably the most accessible is to use a free monad construction, specifically we can use:

data IO a = Return a | Request OSRequest (OSResponse -> IO a)

There are many ways to make this more sophisticated and have somewhat better properties, but this is already an improvement. It doesn't require deep philosophical assumptions about the nature of reality to understand. All it states is that IO is either a trivial program Return that does nothing but return a value, or it's a request to the operating system with a handler for the response. OSRequest can be something like:

data OSRequest = OpenFile FilePath | PutStr String | ...

Similarly, OSResponse might be something like:

data OSResponse = Errno Int | OpenSucceeded Handle | ...

(One of the improvements that can be made is to make things more type safe so that you know you won't get OpenSucceeded from a PutStr request.) This models IO as describing requests that get interpreted by some system (for the "real" IO monad this is the Haskell runtime itself), and then, perhaps, that system will call the handler we've provided with a response. This, of course, also doesn't give any indication of how a request like PutStr "hello world" should be handled, but it also doesn't pretend to. It makes explicit that this is being delegated to some other system. This model is also pretty accurate. All user programs in modern OSes need to make requests to the OS to do anything.

This model provides the right intuitions. For example, many beginners view things like the <- operator as "unwrapping" IO, or have (unfortunately reinforced) views that an IO String, say, is a "container" that "contains" Strings (and then <- gets them out). This request-response view makes this perspective clearly wrong. There is no file handle inside of OpenFile "foo" (\r -> ...). A common analogy to emphasize this is that there is no cake inside of a recipe for cake (or maybe "invoice" would be better in this case).

This model also works readily with concurrency. We can easily have a constructor for OSRequest like Fork :: (OSResponse -> IO ()) -> OSRequest and then the runtime can interleave the requests produced by this extra handler with the normal handler however it likes. With some cleverness you can use this (or related techniques) to actually model things like concurrency more directly rather than just saying "we make a request to the OS and things happen." This is how the IOSpec library works.

1 Hugs used a continuation-based implementation of IO which is roughly similar to what I describe albeit with opaque functions instead of an explicit data type. HBC also used a continuation-based implementation layered over the old request-response stream-based IO. NHC (and thus YHC) used thunks, i.e. roughly IO a = () -> a though the () was called World, but it isn't doing state-passing. JHC and UHC used basically the same approach as GHC.


PTAS vs. FPTAS input I am trying to understand what is the PTAS, FPTAS and what is the difference between them.

I found this analysis:

PTAS definition vs. FPTAS

but I cannot understand what do we mean by saying:

"....time complexity is polynomial in the input size and also polynomial in 1/ϵ" ?? Ok n has to do with the linear O(n) worst case that the algorithm runs. But O(1/ε) how does it work?

For example, the running time $O(2^{1/\varepsilon} \cdot n^2)$ corresponds to a PTAS, since the running time depends polynomialy on $n$, but not on $1/\varepsilon$ since it is in the exponent. The running time $O(1/\varepsilon \cdot n \log{n})$ depends polynomialy on $n$ and $1/\varepsilon$, so it corresponds to a FPTAS.

NB, you also need to show that your algorithm has an approximation ratio of $(1 + \varepsilon)$ (or -) to show the algorithm is in fact a (F)PTAS.


Relaxing hypotheses of Master Theorem This question is related to Master Theorem on oscillating function.

Consider a recurrence of the form

$T(n) = a T(n/b) + f(n)$

Master Theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).

Suppose, however, that $f(n)=\Theta(g(n))$ for a function $g(n)$ that does not violate the regularity condition, so that the Master Theorem is applicable if $g(n)$ is used instead of $f(n)$.
Consider then the following recurrence:

$T'(n) = a T'(n/b) + g(n)$

and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.

Can I then safely conclude that $T(n)=\Theta(g(n))$? Or there are some reasonable conditions on $g(n)$ we can add (I suppose that if $g(n)$ is polinomially bounded then maybe Akra-Bazzi method will apply, even if one have to swich integration and $\Theta$, and I'm not sure this is sound)?

Notice that from $f(n)=\Theta(g(n))$ we cannot deduce that $f(n)$ is always less than or equal to $g(n)$ or to a $d\cdot g(n)$ for some fixed $d$ (indeed, $g(n)$ can be equal to 0 for some value of $n$, so I'm not totally convinced by the answer to Regularity condition in the master Theorem in the presence of Landau notation for f as it is not possible to prove the base case of the induction, unless one changes the initial condition). So I cannot prove by induction that $T(n)<T'(n)$ for all $n$ and, anyway, I only want to prove $T(n)=\Theta(T'(n))$.

To give some context, this is the case I want to apply the result to: consider the recurrence

$T(n)=2\cdot T(n/2)+f(n)$

where I only know that $f(n)=\Theta(n\sqrt{n})$. Then I can unfold the recurrence obtaining
\begin{equation*}
\begin{split}
T&(n)=2T\left(\frac{n}{2}\right)+\Theta(n\sqrt{n})=
2\left(2T\left(\frac{n}{4}\right)+\Theta\left(\frac{n}{2}\sqrt{\frac{n}{2}}\right)\right)+\Theta(n\sqrt{n})
=\\
&=\ldots=2\left(2\left(2\ldots \left(2T\left(\frac{n}{2^h}\right)+\Theta\left(\frac{n}{2^{h-1}}\sqrt{\frac{n}{2^{h-1}}}\right)\right)\ldots\right)\right)+\Theta(n\sqrt{n})
\end{split}
\end{equation*}

until $2^h=n$, i.e. $h=\log(n)$. Then $T(n)=\sum_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)$.

Performing the calculations I get
\begin{equation*}
\begin{split}
T(n)&=\sum_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\Theta\left(\sum_{i=0}^{\log(n)-1} 2^i\cdot\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\\
&=\Theta\left(n\sqrt{n}\cdot\sum_{i=0}^{\log(n)-1} \frac{1}{\sqrt{2^i}}\right)
\end{split}
\end{equation*}
The series $\sum_{i=0}^{+\infty} \frac{1}{\sqrt{2^i}}$ is convergent, so I can conclude (I hope correctly) that $T(n)=\Theta(n\sqrt{n})$.

On the other hand, I cannot directly apply Master Theorem, as from $f(n)=\Theta(n\sqrt{n})$ I cannot conclude $2f\left(\frac{n}{2}\right)<cf(n)$ for some $c<1$. Indeed, if definitively we have $c_1 n\sqrt{n}\leq f(n)\leq c_2 n\sqrt{n}$, then

$f(n)\geq c_1 n\sqrt{n}= 2\sqrt{2}c_1 \frac{n}{2}\sqrt{\frac{n}{2}}\geq\frac{2\sqrt{2}c_1}{c_2}  f\left(\frac{n}{2}\right)=\frac{\sqrt{2}c_1}{c_2}  2f\left(\frac{n}{2}\right)$

and so

$2f\left(\frac{n}{2}\right)\leq \frac{c_2}{\sqrt{2}c_1} f(n)$

but $\frac{c_2}{\sqrt{2}c_1}$ is not necessarily less than 1.

Yes. Here is the idea.

If $f(n) = \Theta(g(n))$ then there exist constants $C_1,C_2>0$ such that for large $n$,
$$ C_1g(n) \leq f(n) \leq C_2g(n). $$
Now consider the two recurrences
$$
T_1(n) = aT_1(n/b) + C_1g(n) \\
T_2(n) = aT_2(n/b) + C_2g(n)
$$
Choosing suitable initial conditions, you can prove inductively that
$$
T_1(n) \leq T(n) \leq T_2(n).
$$
You consider a regime in which applying the master theorem gives you that $T_1(n) = \Theta(g(n))$ and $T_2(n) = \Theta(g(n))$. It follows that $T(n) = \Theta(g(n))$.


Verifier - Complexity Theory A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V  \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\right\}.$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?

A verifier for a language $L$ is an algorithm that accepts as input an instance $x$ of $A$ and a witness $w$, and has the following properties:

The algorithm always halts.
If $x \in A$ then there is a witness $w$ such that the algorithm accepts $\langle x,w \rangle$.
If $x \notin A$ then for all witnesses $w$, the algorithm rejects $\langle x,w \rangle$.

We are often interested in polynomial time verifiers. Such a verifier exists for the clique problem, which is: given a graph $G$ and a parameter $k$, decide whether $G$ contains a $k$-clique. Here is one polynomial time verifier for this problem: it accepts as witness a list $S$ of vertices, and on input $G,k,S$ it accepts if $S$ is a set of $k$ vertices which form a clique in $G$. I'll let you check that this satisfies all the required properties.


Does "standard" Dijkstra's algorithm work with bi-directional edges and zero cost edges? I have been reading about Dijkstra's algorithm and I think I understand it. I followed the algorithm in pseudo-code from Wikipedia, and now I wonder:

If my graph is bi-directional and I add each edge to my graph twice (once "forwards", once "backwards"), will the "standard" Dijkstra's algorithm work?
Is it ok that some of my edges are zero cost? (the rest are all positive - none are negative)

And finally, what is a Dijkstra "heap" algorithm? Is it the same as Dijkstra's algorithm using a PriorityQueue?

Yes, both of these cases work. You can even have zero-cost loops.


Generate code from automata I am trying to figure out the process of generating code (set of instructions, implementation language specifics dont matter at this time) from an automaton.

The description of my intent is vague because although I am an electrical engineer, with extensive coding experience, I have no theoretical CS background and I am struggling to even articulate what I mean. The issue at hand is related to a digital circuit that I am working with. At this point I am not even aware of what I need to start looking into. Another way of describing my intent is, say I got a transition model of a process with the data requirements that are associated with the states. Knowing that, can I generate a program that will implement that model? Is there a field of study that deals with problems like this? Or should I just develop some logic to solve a limited interpretation of the model?

I believe I am using incorrect or misleading terms from a CS standpoint but I will appreciate if I can get some guidance on how to formulate my intent and then try to understand the possible solutions, if any.

Thanks!

A simple way to do it is to just write an interpreter that follows the transition table. I.e., do something like (in C):

state = INITIAL;
symbol = get_next();
while(symbol != END) {
   state = table[state][symbol];
   symbol = get_next();
}
if(is_accepting(state))
   /* Accept */

Next simpler is to write a rat's nest of gotos, transferring among them according to the symbol at hand (each label in the program corresponds to a state of the automaton).

Writing a decently organized,structured program from an automaton is possible, but far from automatic (and it would take a fair amount of work to check it really is faithful to the automaton).


Why does Fleury's algorithm have to return to the starting node? Recently, I am reading the Fleury's Algorithm part of the document [1]. There is a sentence on page 3 of this document:

  Note that, when the algorithm terminates, we must return to $v_{start}$ because every vertex has an even degree.

I don't understand why we must return to $v_{start}$. Could anyone please teach me?

Eulerian circuits by Ethan Kim (accessed Oct 14, 2016)

Suppose you end up at a vertex different from the start. You may have visited the vertex before, say $k$ times. Each time you visited the vertex you used up one edge to enter it and one edge to leave it. So $2k$ edges, an even number. When you enter it for the last time, you used up $2k+1$ edges, an odd number. Since the degree of all nodes is even, there must be an edge left over which you can leave the vertex and the algorithm wouldn't have stopped.

The start vertex is special because you don't need to enter it to visit it the first time (right at the start).

Note that a graph can also be eulerian if it has exactly two vertices with odd degree. Then you have to choose one of them as a start vertex and you will end up at the other odd-degree vertex at the end of the algorithm. I leave it to you to prove why this is the case.


Complete finite automaton to never fail a match but either match original or up until the orginal Suppose I have a finite automaton to match a simple string "abc" and I built some software around it to not only match the start of a string or a full incoming string, but rather to search through a string and find the first match. As an example consider the string to be "12abcxxx".

The naive approach is to start with reading the '1' and trying a transition in the automaton. It fails. So we advance the input and try again, with `2'. Fail again. Now read 'a', 'b', 'c' nicely transition though the automaton, reach the stop state, store it, read 'x', fail and declare a match for the latest stop state we ran through.

If we assume that every 'fail' in this algorithm is inefficient, while transitions through the automaton are fast, an improvement would be to extend the automaton such that it matches either 'abc' or '[^a]+' and mark the different stop states as 'found abc' and 'not found abc'. Then '123' would be a match, supposedly much faster then three fails to skip over.

But adding '[^a]+' is not the only optimization. We could even add something like '([^a]|a[^b]|ab[^c])+' (which is not completely correct) to the automaton to skip over the non-matching sequences quickly.

Question: Working with a finite automaton that allows to mark stop states with different markers, and given an automaton for a regular expression re, is it possible to "complete" the automaton such that it implements the quick skip over non-matching substrings as described informally above.

If it is possible, what would be the operation to perform either on the regular expression or an NFA or DFA representation? I would expect the result to talk about something like the complement set of the prefix set recognized by the original automaton.

Question rephrased: Reading the first answer I realized that the question is equivalent to the following: Given a regular language $L$, is there a regular language $L_p$ that satisfies the following: For all strings $s\in\Sigma^*$, $L_p$ shall contain the prefix of $s$ that ends just before an $s_x\in L$ or the complete $s$ if no such substring exists.

Here is what I came up with finally. I need the following operations on  finite automata, for automata a and b.

allPrefixes(a) creates an automaton that matches all non-empty prefixes of the language L(a). The implementation is quite simple on a DFA. Make sure there are no useless states (those with no path to a stop state). Then make all states except the start state into stop states.
invert(a) creates an automaton that matches the complement of L(a).
asSubstring(a) creates an automaton that matches every string in $\Sigma^*$L(a)$\Sigma^*$.
not(a) is a shortcut for invert(asSubstring(a)).
or(a,b) is the automaton that recognizes L(a)$\cup$L(b).

Given an automaton a, the automaton which comes very close to what I was after is then easy to describe as c=or(a, not(allPrefixes(a)).

Remember that I want filtering, i.e. find a match, remove the matching input, find a match again and so on until end of input. The automaton c either matches my original a or all kinds of stuff that does not end in any prefix recognized by a. Except for a suffix of the input matching only a prefix of a, there will always be a prefix of the input being matched by c.


Is hedge union always as fast as divide and conquer? Adams describes a divide-and-conquer algorithm for finding the union of two sets (represented as weight-balanced binary search trees). He then describes a then-new "hedge union" algorithm which he claims improves on the divide-and-conquer one. However, he does not offer a proof, or even a real explanation, of why it should be $O(m + n)$, let alone why it should be faster than divide-and-conquer.

Blelloch, Ferizovic, and Sun show that Adams's divide-and-conquer algorithm actually attains the theoretically optimal $\Theta (m \log (n/m + 1))$ where $m \le n$. They do not, however, address the hedge union algorithm.

Is hedge union, in fact, as efficient as divide-and-conquer? The least obvious part is the inner trim. It appears, at least superficially, to duplicate work between the left and right subtrees that the full split shares between them. Perhaps this is okay for some reason, but I don't know why.

A further inquiry: Haskell's Data.Set and Data.Map use hedge variants of intersection and difference, as well as union. I have not found any published discussion of those algorithms at all. Similar questions apply to these as well.

While I have yet to see, or produce, a theoretical analysis of the hedge algorithms, I do have some empirical evidence that they are worse than the divide-and-conquer algorithms for binary trees.

Starting with the code in the Haskell containers package, I optimized the hedge union algorithm by manually applying call-pattern specialization to reduce intermediate allocation. This improved its performance by about 10%, giving it a fair shot.

Starting with the divide-and-conquer code in Adams, I optimized the union algorithm by adding special cases when either of the inputs is a singleton (the hedge union code optimizes one side thus, and it's not clear if the other side can be optimized similarly).

I tested each implementation using a collection of set operation benchmarks packaged with containers. Divide-and-conquer was usually faster than hedge, sometimes twice as fast. When it was slower, it was only slightly so.

Similar benchmarks of other set operations gave similar results.

Speculation:

Hedge algorithms may be helpful when using trees with a large branching factors, which may be more expensive to split recursively. They may also be helpful for small subtrees, where they may save enough allocation to be worth the extra work.


Number of processes needed to maximize CPU utilization under I/O wait conditions A computer has 2 GB of RAM of which the operating system occupies 256 MB. The processes
are all 128 MB (for simplicity) and have the same characteristics. If the goal is 99% CPU
utilization, what is the maximum I/O wait that can be tolerated?

My professor said that there are 14 processes in the memory before proceeding with the solution. Why are there 14 processes?

You want all processes to fit in memory. If there are $N$ processes, then together with the OS they take up $256+128N$ megabytes. Since there is only room for $2048$ megabytes, we need $256+128N \leq 2048$. Dividing by $128$, this is $N+2 \leq 16$.


Does removal of unit production from the grammar may increase number of total production? There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions)

(a) O(m)
(b) O($m^2$)

(c) O($k^m$)

(d) O($2^m$)

My attempt:

He asked about number of total production remains in the minimized grammar ,
 so , if the there is no null production , it is advantage , as you know when we convert a grammar without null production , generally , removal of all production introduces new production in the resultant grammar (it can be upto set of all subset of given max RHS number of variable , so exponetial ) .

But , in given grammar , you don't have null production , so you are removing only unit production (i.e. A--->B type productions ) , resultant grammar maximum 'm' production , where m is number of variable .
example :-
S---->A
A---->B
B---->a/b/c
resultant grammar ,
S---->a/b/c
So , it is O(m) time .

  Can you explain in formal way, please?

Hint: Consider the grammar
$$S \to \overbrace{X\cdots X}^{\text{$n$ times}} \\ X\to a|b$$
What happens when you remove unit productions?


How much space an ascii character really takes on a 64 bit word addressable memory? I know that an ASCII character needs 1 byte of memory for storage, but if a computer uses a 64-bit word addressable memory does it mean that the character actually takes 8 bytes even when only 1 byte was needed?
Does being a 64-Bit word addressable memory mean the same as being a 64-Bit machine?

It depends.  A program can store 1 ASCII character in each 64-bit word, or 8 ASCII characters in each 64-bit word.  It's up to each individual program to decide how it wants to store and format its data in memory.  The latter would probably be more typical.


Functional problem and verifying solutions Is there a functional problem for which there is an algorithm that can decide if a solution is a solution or not in polynomial time but we can't find a solution in polynomial time?

Let FP be the class of functional problems.

Update:
Every problem in FP, say $a$, has a correspondent decisione problem $a'$ (the associated decision problem $a'$ is the problem where we ask if a possible solution is a solution), I ask if there is a functional problem $a$ for which $a'$ is in P but $a$ is NOT in FP.

In this link: Hamiltonian cycle, verifying and finding

we have instead a functional problem HC (hamiltonian cycle) for which HC' is P and HC is in FP.

Intuitively I think that the kind of problems I search, should be 'more' the problem of kind of HC. But maybe the hard part, given $a$ (with $a'$ in P), is to prove that $a$ is NOT in FP.

It appears that you are asking whether FP = FNP.  That is an open problem.  It is known that FP = FNP if and only if P = NP.  I suspect that most theoreticians expect that it's likely that P != NP, which would imply FP != FNP.  If FP != FNP, there exists a function problem whose solutions can be verified in polynomial time, but where you can't find a solution in polynomial time.  In particularly, any FNP-complete problem -- such as FSAT, say -- will have that property, if FP != FNP.  So, the FNP-complete problems are particularly good candidates for having the property you articulate.  See https://en.wikipedia.org/wiki/Function_problem for an overview.


Rearrange an array using swap with 0 This is a Google interview question. I got it from a website.

You have two arrays source and target, containing two permutations of the numbers [0..n-1]. You would like to rearrange source so that it equals to target. The only allowed operations is “swap a number with 0”. Find the minimum number of swaps?
e.g. {1,0,2,3} -> {1,3,2,0}  swap 0 with 3. one swap is enough.

My attempt on problem: If we consider arrays as strings we could use edit distance to convert source to target if other edit distance operations like insert,delete,replace etc are allowed but here only allowed operation is swapping.

Without loss of generality you can assume that the target array is $0,1,...,n-1$: you can "relabel" the target array as 0,1,2,...,n-1 (and relabel the corresponding numbers in the source array, too). The allowed operation becomes "swap a number with x" (where x is not necessarily 0) and the target array is 0,1,2,...,n-1.

You can build a directed graph with $n$ nodes and an edge from node $n_i$ to node $n_j$ if $n_i = j$, i.e. the target position of $n_i$ is $j$ (skip nodes that are already in the correct position). The resulting graph contains one or more distinct cycles.

You can arrange the cycle containing the zero following the arcs in the reverse direction, then "jump" to another cycle and arrange it; the "entry point" doesn't matter.

In the example of the figure above the swap number is zero and the target permutation is $0,1,...6$; after completing the first cycle (blue one) you must enter the second cycle (red one) in order to complete it; if $(n_i \rightarrow n_j)$ is a directed arc of the second cycle, then it must modified in $(n_i \rightarrow 0 \rightarrow n_j)$. The "entry point" is irrelevant (the number of swaps needed to arrange the second cycle doesn't change). You can also interpret the swaps on a cycle like a shift of its numbers.

The procedure always ends with the sorted array (after arranging a cycle, its numbers are never moved again). If there are $m$ cycles and the $i$-th cycle has $p_i>1$ numbers that needs to be arranged and cycle 1 contains the number used for the swaps, the total number of swaps is $(p_1-1)+(p_2+1)+...+(p_m+1)$. If the number used for the swaps is already in place the number of swaps is $(p_1+1)+(p_2+1)+...+(p_m+1)$. To prove that the number of swaps used is optimal, you can observe that every number of each cycle must be moved (requires a swap), and there is no way to move a number of a cycle without "moving" the zero on that cycle.


Scheduling algorithm with defined starting intervals and processing times I need to design an algorithm for opening and closing some valves at regular times. The input schedule will look something like this:

Every 5 minutes, open each of valves 1, 2, and 3 for 5 seconds
Every 8 minutes, open each of valves 4, 5, and 6 for 10 seconds

The main constraint on this schedule is that only one valve can be open at a time.

If I were given just the first line from above as my schedule, the result would be like:

t % 300 = 0: open valve 1
t % 300 = 5: close valve 1, open valve 2
t % 300 = 10: close valve 2, open valve 3
t % 300 = 15: close valve 3

Adding in the second line raises some more problems, like what is the overall time period (i.e. the divisor in the %)? I believe this should be the least common multiple of all the time periods: 2400 = 300 * 8 = 480 * 5. The schedules then become 8 and 5 copies, respectively, of the base schedules lined up sequentially.

I would want to determine if it is possible to fulfill the schedule. A simple sanity check is that the sum of all the open times is less than the total amount of time in the LCM, but I do not believe this is sufficient.

Second, I need to determine what the actual combined schedule is. I believe this would be a series of starting offsets for each valve's schedule. In the simple case I illustrated above, the offsets for each of valve 1, 2, and 3 are 0, 5, and 10, respectively.

I have looked into cyclic static scheduling, earliest deadline first algorithms, etc., but have been unable to synthesize this knowledge into the algorithm that I need here. The difficulty I see is that I do not have an ending deadline but a starting deadline: once the first valve opens at t=0, it must also open at t=300, 600, 300*n.

Other analogies I have considered are:

packing byte patterns into a buffer without overwriting non-null values (view each time slice as a byte and the value at the byte is the number of which valve is open)
dispatching trains of different speeds at given intervals and avoiding collisions
arranging transparent pieces of plastic with some colored areas in a stack (or cylinder since this is repeated) so that a max of one color is present at any given point

To recap: I need to determine a schedule meeting the above criteria. If determining the schedule is computationally intensive, it would also be nice to quickly determine if such a schedule is possible as well.

Am I on the right track here? What should I search for to move forward in this algorithm design? Has this problem been solved already?

For this particular problem, you have an evident solution. If you work only in seconds, you have GCD(5min, 8min) = 60s. Moreover the sum of the required times of opening is $3\times 5 + 3 \times 10 = 45 s$.

Thus, you can assign to each valve an offset in the 60s period without any risk of collision. Then, you can decide independently for each valve for each 60s period if you actually use the assigned slot or not. That is to say one every 5 periods for valves 1, 2, 3 and every 8 periods for valves 4, 5, 6.


If A is polynomial time reducible to B such that B <= A, does it mean B must be a polynomial time algorithm? I don't understand what it means for A to be polynomial time reducible to B. I'm guessing is that we can revised the algorithm some how such that it becomes B, where B is a polynomial time algorithm.

Can someone point out if I have this completely wrong?

A language $A$ is polynomial time reducible to a language $B$ if there is a polynomial time function $f$ such that $x \in A$ iff $f(x) \in B$. In particular, if $B$ can be solvable in polynomial time, then so can $A$.

There are other notions of reducibility in complexity theory, some stronger than this and some weaker. A weaker notion is polynomial time oracle reducibility: $A$ is polynomial time oracle-reducible to $B$ if $A$ can be solved in polynomial time given oracle access to $B$ (this can be defined formally). Stronger notions put more constraints on $f$, such as being computable in logarithmic space.

Weaker notions of reducibility could seem more natural: if $A$ is polynomial time oracle-reducible to $B$ and $B$ can be solved in polynomial time, then so can $A$. Why would we want to put more constraints on our reduction? For example, assuming $\mathsf {NP} \neq \mathsf {coNP}$ (which is a common assumption), an NP-complete cannot be polynomially reduced to its complement. For example, SAT, the language consisting of all satisfiable CNFs, isn't reducible to coSAT, the language consisting of all unsatisfiable CNFs. Intuitively, this seems ludicrous, since if you could find out whether a CNF is unsatisfiable, surely you could find out whether a CNF is satisfiable!

Indeed, Cook first defined NP-hard problems using oracle reduciblity rather than the modern many-one reducibility (described in the first paragraph of this answer). The problem with oracle reducibility is that it is hard to reason about, whereas many-one reducibility leads to a richer complexity theory. Also, the polynomial hieerarchy, which mirrors the classical arithmetical hierarchy from recursion theory, only makes sense using many-one reducibility. Perhaps in the future you will be able to formulate your own opinion on this matter.

When studying the internal structure of $\mathsf P$, we must use stronger notions, since all non-trivial problems in $\mathsf P$ are polynomially reducible to each other (the only exceptions are $\emptyset$ and $\Sigma^*$). The most common notions are logspace reducibility, in which $f$ has to be computable in logarithmic space, and the even stronger AC0 reducibility (also known as first-order reducibility), in which $f$ has to be computable by uniform polynomial size circuits having constant depth.


Can a computer determine whether a mathematical statement is true or not? I was reading Introduction to the Theory of Computation by Michael Sipser and I found the following paragraph quite interesting:

During the first half of the twentieth century, mathematicians such as Kurt
Godel, Alan Turing, and Alonzo Church discovered that certain basic problems ¨
cannot be solved by computers. One example of this phenomenon is the problem of determining whether a mathematical statement is true or false. This task
is the bread and butter of mathematicians. It seems like a natural for solution
by computer because it lies strictly within the realm of mathematics. But no
computer algorithm can perform this task.
Among the consequences of this profound result was the development of ideas
concerning theoretical models of computers that eventually would help lead to
the construction of actual computers

As a CS student, completely new to the theory of computation, this is hard to believe for me. It said that a computer can't solve a basic task such as determining whether a mathematical statement is true or false. Can't it really!? I have programmed lots of codes that determine if a mathematical statement is true or not. For example,  a simple code such as return 6 == 2*3 will return true if this statement is true, so why does the text says that a computer can't perform this task?
I'm sure I'm missing something here. Perhaps I'm mistaken by the definition of "Mathematical statement".
But I'm quite sure "Is 6 equal to 2 * 3?" is a mathematical statement and can be validated by a computer.
So what did the text mean by that? I'm confused!
PS: Sorry if the Complexity theory tag is misplaced here. As I said I'm new to the field and on the same page the author of the book stated that the theories of computability and complexity are closely related.

The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not.
The standard choice for the class $\mathcal{C}$ is statements about natural numbers, for example:

Every even integer greater than two is a sum of two primes.

The class $\mathcal{C}$ contains all statements of the form:

For all natural $n_1$ there exists natural $n_2$ such that for all natural $n_3$ there exists natural $n_4$ such that ... there exists natural $n_{2m}$ such that $P(n_1,\ldots,n_{2m})$,

where $P$ is an expression using logical operators, comparison operators, addition, subtraction, multiplication, division, and integer constants.
Another popular choice for the class $\mathcal{C}$ is:

The following algorithm halts: ...

In both cases, there is no algorithm that takes an arbitrary statement from class $\mathcal{C}$ and correctly outputs whether the statement is valid or not.

It is crucial that the algorithm be required to answer correctly for all statements in $\mathcal{C}$. We can easily write an algorithm that answers correctly on a single statement from $\mathcal{C}$. Indeed, one of the following algorithms will work:

The statement is valid.

The statement is not valid.

Similarly, we can design an algorithm that answers correctly on two different statements $A,B$. One of the following will work:

The statement is valid.

The statement is not valid.

If the statement is $A$, then it is valid, otherwise it is not valid.

If the statement is $B$, then it is valid, otherwise it is not valid.

We cannot implement this strategy in the case of infinitely many statements, since an algorithm, by definition, has a finite description. This is the hard part – being able to decide, for infinitely many statements, whether they are valid or not.


Can the plus operator in regex be replaced by the star operator? Full disclosure, I'm interested in what this means about transformations on NFAs, but regex expressions seem like a easy way to ask the question.

If you have a regex that uses the plus operator (match one or more) can it, in the general case, be transformed into a regex that uses only the star operator (match zero or more).

Since all regular expressions can be converted into an NFA, and all NFAs can be converted into a regular expression (assuming the alphabet is the unicode character set lol), if it's true for one, it's true for both.

An hand-contrived example regex:

<[a-zA-Z]+>

A regex recognizing the same language, without the + operator:

<[a-zA-Z][a-zA-Z]*>

This may seem intuitively true for such a simple example, but I'd like to know for certain that it is generally true. Also, is there an algorithm that can convert an NFA containing a plus-like flow into a star-like flow NFA? Thanks!

True. For any regular expression $R$, (the meaning of) $R^+$ equals $R \cdot R^*$, and conversely, $R^*$ equals $R^+\mid\varepsilon$ (where $\mid$ here is the choice operator 'or', and $\varepsilon$ the expression matching the empty string).

Thus in any regular expression dialect it suffices to include only one of star and plus without loosing expressibility. Translation of plus into star can be done recursively (inside-out).


How to convert pixel relative focal lengths to mm. Ive been playing around with the Intel Realsense R200 Camera.
I am able to exact focal length in x and y i.e. fx and fy,
but only "up to scale relative to pixel width and height, respectively"

At the moment I dont see any way of querying the pixel dimensions in mm from the API nor can I find them in the tech specs.

So my question is: How can I get the fx and fy in mm?
One way I can think of is to take a picture of my checkerboard pattern and count the number of pixels and divide by the size in mm.

Is there a better/more elegant way? It seems kind of..imprecise.

Best,
Marc

There is only one focal length, $F$. It is the distance between the focal point and the image plane.

The numbers you have, are actually not lengths. They are calculated by $f_x=F\cdot s_x $ and $f_y=F\cdot s_y $  where $s_x$ and $s_y$  are the size of your image in pixels. To get the focal length in mm as you want, simply divide $f_x$ with the width (in pixels) of your image.


Does every infinite context free language contain an infinite regular subset? Can someone explain to me if this is true or not?

No.

A counterexample is simply $E=\{a^nb^n\mid n\ge0\}$, the classic context-free language that is not regular.

For the sake of contradiction, suppose $E$ has an infinite regular subset $S$. So $S$ satisfies the pumping lemma for regular languages. Suppose $p\ge1$ is a pumping length of $S$. Since $S$ is infinite, $w=a^mb^m \in S$ for some $m\ge p$. Since $|w|=2m\gt p$, $w$ can be written as $w=xyz$, satisfying the following conditions:

$|y| \geq 1$
$|xy|\leq p$
$\forall n\geq 0$, $xy^{n}z\in S$

Since $|xy|\le p$ and $w$ starts with at least $p$ $a$'s, $y=a^k$ for some $k\ge1$. Since $xz=xy^0z$ has less $a$'s than $b$'s, $xz\not\in S$. This contradiction shows that $S$ is not regular. That is, no infinite subset of $E$ is regular.

What we just showed above is the fact that given any language, if every word in it cannot be pumped as in the pumping lemma for regular languages, then that language does not contain an infinite regular subset.

Here is a related exercise.

Exercise. A language is called prefix-closed if all prefixes of every string in the language are also in the language. Let $P$ be an infinite, prefix-closed, context-free language. Show that $P$ contains an infinite regular subset.


The Church-Turing-Thesis in proofs Currently I'm trying to understand a proof of the statement:

"A language is semi-decidable if and only if some enumerator enumerates it."

that we did in my lecture. One direction of the proof goes as follows:

Let E be an enumerator that enumerates L. We construct a TM M, that semidecides L in the following way:

Given an input string x, we design M in the following way :

Run E to enumerate the next string y of L. Compare it with x.
If x=y accept, else goto 1

Am I right if I say, that it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis?
Furthermore is there anything to take care of when constructing an algorithm in such a context as not to hurt the "definition" of intuitively computable?

Thanks for any answers.

A Turing machine provides a formal definition of a "computable" function, while the Church-Turing-Thesis says that intuitive notion of "computable" coincides with the formal definition of "computable", i.e., all functions computable by TMs. This is just a hypothesis, and it is up to you to believe or not.

When we describe a procedure in order to show that some function is computable (or problem is solvable) we usually describe it at a high level, to avoid long and tedious rigorous formal details. So, you are right that "it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis". In other words, first we informally describe a procedure using English, and then since we believe in correctness of the the Church-Turing-Thesis we conclude that the function is computable.

Another example is computing $\pi(n)-$ the $n$th digit of the decimal expansion of $\pi$. Intuitively, we can draw a circle, measure its circumference and radius, and divide the circumference by two times the radius. But this method is not suitable to implement on a computer. The Turing-Church thesis says this function is indeed computable on a Turing machine. For example, $\pi(n)$ might be computed using Taylor series.

As for the wrong usage of the thesis, usually the error may lay in a wrong assumption. For example, the following wrong procedure may seem to decide the Halting problem:

Let L be the Halting Problem language
IsHalt(W,w)
  Recursively enumerate elements of L and complement of L
  and process one element from each set at a time
  If <W,w> is in one of them then depending in what set <W,w> is
  return true or false

Since we loop on both $L$ and $\overline{L}$, and we enumerate each element of these sets, the procedure eventually must halt with true or false. But the wrong part is that we assumed the $\overline{L}$ is r.e.


How does SpaCy make its dependency tree? I discovered that SpaCy had the ability to make dependency trees. For instance given a question “To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?”

We can create its dependency tree with the following code :

I know that it is a set of edges $E$ which represents the relations of labeled dependencies of the particular analysis of $G$. More precisely, an edges $w_i, r, w_j \in E$ represents a relationship of dependence of head $w_i$ towards $w_j$ labeled with the type of relationship. A dependency graph $G$ is therefore a set of dependency relations between tokens in $S$.

For instance we present the dependency graph that follows
 by the following graph:

$G = (V, E)$
$V = \{\mbox{It, is, a, replica, of, the, grotto, at, Lourdes, France, where, the, Virgin, Mary}\\ \mbox{reputedly, appeared, to, Saint, Bernadette ...}\}$
$E=\{\mbox{(is, NSUBJ, It), (is, ATTR, a replica), (a replica, PREP, of),...}\}$

But I was wondering how does $E$ was made with Spacy? How does the dependency tree method chose which node is the root and which aren't?

I have heard from this French paper that, on the one hand that $E \subseteq V \times R \times V$ where $R = {r_1, ..., r_m}$ is a finite set of dependency possible names that we call dependency relationship. They can link two tokens in a sentence. A dependency name $r \in R$ is also called a labeled edge. For example, a relationship between a head verb and its subject can be noted with $r = SBJ$.

On the other hand it was an analysis problem of finding the dependency graph that has the highest score for an input sentence.

Yet I haven't seen where there is a child-children ordering creation.

The context is that I am using SpaCy dependency trees to get the root of sentences of a paragraph and match it with the root of a question.

For the question given above we have to find the answer in the following paragraph :

  Context — “Architecturally, the school has a Catholic character. Atop
  the Main Building\’s gold dome is a golden statue of the Virgin Mary.
  Immediately in front of the Main Building and facing it, is a copper
  statue of Christ with arms upraised with the legend “Venite Ad Me
  Omnes”. Next to the Main Building is the Basilica of the Sacred Heart.
  Immediately behind the basilica is the Grotto, a Marian place of
  prayer and reflection. It is a replica of the grotto at Lourdes,
  France where the Virgin Mary reputedly appeared to Saint Bernadette
  Soubirous in 1858. At the end of the main drive (and in a direct line
  that connects through 3 statues and the Gold Dome), is a simple,
  modern stone statue of Mary.”

The expected answer is  “Saint Bernadette Soubirous”.
The sentence having the answer — is “It is a replica of the grotto at Lourdes, France where the Virgin Mary reputedly appeared to Saint Bernadette Soubirous in 1858”. Its dependency tree of the sentence containing the answer is :

Matthew Honnibal, who created Spacy, answered me :

  The full answer is rather complicated :). I've written a few blog
  posts over the years to make it more accessible. The best place to
  start is this blog post:

  https://explosion.ai/blog/parsing-english-in-python

  Since v2, we use a more complicated machine learning strategy,
  following the general architecture described here:
  https://explosion.ai/blog/deep-learning-formula-nlp . More specifics
  about the model architecture can be found in this description of the
  NER model: https://www.youtube.com/watch?v=sqDHBH9IjRU

  The transition system is mostly described by this paper:
  http://aclweb.org/anthology/D15-1162 , but with some modifications for
  sentence segmentation.

I already started with the first one which I didn't completly understand yet. I will update this post through my reading progress but leave the question open if a concise question comes to your mind.


Minimum diameter spanning tree problem Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) > 0\ \forall e \in E$, find the spanning tree $T(V, E')$ of $G$ such as maximal distance between vertices in $T$ is minimal.

I've done my research and haven't found much literature on this particular problem (I've seen Euclidean MDST and bounded MDST, but not MDST itself) and wondered if there's any good explanation of polynomial solution to that problem. Also, I saw a theorem stating that $\Theta(n^3)$ solution exists here, but no full solution is anywhere.

I believe this community would benefit if solution is described here.

The answer is given in the paper that you link to. Specifically, there is a $O(mn+n^2 \log n)$-time algorithm for the problem (with positive edge weights, as required) that works as follows.

The absolute 1-center is the point in the graph - either a vertex or an edge - from which the distance to the furthest vertex is minimum. Now, denote by $T(v)$ a shortest path tree connecting $v$ to all vertices in $V$. It holds that $T(a)$ is a minimum diameter spanning tree of $G$, where $a$ is an absolute 1-center of $G$. Here, if the absolute 1-center is an edge, we subdivide it to obtain the vertex $a$ from which $T(a)$ is then computed from.

An absolute 1-center $a$ can be found by the Kariv-Hakimi algorithm within the mentioned bound, while $T(a)$ is computed by any standard shortest path algorithm.


Can bottom-up architectures be effectively programmed in top-down paradigms? The subsumption architecture, proposed by Rodney Brooks in 1986, is a "bottom-up" approach, in which robots are designed using simple hierarchical models.  These models build upon and subsume the lower modules to form a final product.  For example, a robot can be given a "find opening" module which is subsumed by a more abstract "find doorway" module, which is then itself subsumed by an "exit the playing field" module.

Now, obviously, in a more "object-oriented" design, we could have started the design with the "exit the playing field module", but for sake of argument, assume some of the more primitive components (as "functions") will likely get reused in other higher concepts.

Realizing that implementing this robot in a procedural language (or a functional one, for that matter) could be the simplest, but is it counterproductive to try to conceive of a subsumption architecture-based robot in an object-oriented programming paradigm? (realizing also that it's perhaps difficult to weigh a software engineering paradigm against a robotics one)  To obtain a solution, is there some form of "adapter" that can be implemented for increasing the effectiveness of using what may be two conflicting paradigms?

I would like to generalize this into a more common scenario. This I believe makes sense since the particulars of subsumption architecture are perhaps not a primary aspect in the question (and the same problems occur in non-robotic fields as well).

In general software archtitecture there is a bi-directional approach, or multi-paradigm approach, as in the question. The bottom most layer of an operating environment is generally written bottom up. Very specific code bits are written to driver very specific hardware elements on the system. These are then combined to form higher level components. I suspect we could easily describe this as a subsumption approach if we simply describe our robot as the system itself, and the goals to control specific aspects of that system. Though I'm not sure it is improtant to do so.

From the top-down most applications are written in higher level languages, or described in terms of an abstract machine. This is quite far removed from the bottom most libraries which will actually be doing the work.

At some point these two layers have to meet -- actually they meet at many locations in a variety of scenarios. This where you have to "adapt" the layers to be suitable for the other layer. The term "adapter" here is 100% correct. There is indeed a software pattern called "adapter" which is used for this purpose.

Aside from specific adapters we can actually consider the entire toolchain of any modern programming. The compiler itself, along with the liner and an execution VM, are the primary interface between the two layers.  That is, a high level language is written in one domain, and the compiler is what allows it to work in the lower level domains.

If you are looking specifically for paradigm effectivness, consider that high-level languages exist for imperative programming (C++), functional programming (Haskell), and declarative programming (Prolog). These paradigms all ultimately work on the same underlying low-level libraries.

Is the question in robotics much different? No, I don't believe so. Indeed if the same ideas were formulated today I don't think they'd have a robotic specific term (subsumption architecture) as there is no strong difference from normal software architecture. You even indicate in your last paragraph both a functional and imperative paradigm for controlling a robot. I would however use a domain specific language to be used -- and again, the vast assortment of domain specific languages is further evidence that multiple paradigms can be efficiently adapted to each other.


How to determine the max offset of a value, given the range, step size and amount of steps Given

The starting and the end values of X
The maximum step (maximum delta)
Exact amount of steps

I need to determinte the maximum and the minimum possible values that X could become during this chain of changes and still make it from the start value to the end value with the steps that are less or equal to the maximum step value.
E.g. for data:

X_start = -10; X_end = 1;
MaxDelta = 7;
MaxSteps = 4;

The answer would be: Max = 4; Min = -11;
Sequences:
−10 → −3 → 4 →1
−10 → −13 → −6 →1
P.S. There is no need to generate such sequences, only the max and min values.
I have been thinking about the ways to do it efficiently and I am stuck. I have an idea that a binary search might be useful.
Any help/tips/suggestions would be much appreciated.

Suppose we start at $s$ and want to end up at $e$. We take $n$ steps, $n^+$ positive steps and $n^-$ negative steps. Then we can reach maximum $m \in[s, s + n^+\delta]$ and can end up in $[m-n^-\delta, m]$. We get equations:
\begin{align}
n &= n^+ + n^-\\
n^+ &\geq 0\\
n^- &\geq 0\\
s &\leq m \leq s+n^+\delta\\
m-n^-\delta &\leq e \leq m\\
\end{align}
Rearranging we get our upper bounds:
\begin{align}
m &\leq s+n^+\delta\\
m&\leq e+n^-\delta\\
\end{align}
Substitute and realize maximum:
\begin{align}
m &= \min(s+n^+\delta, e+n\delta - n^+\delta)\\
m &= s + \min(n^+\delta, e-s+n\delta - n^+\delta)
\end{align}
This looks complicated, but set $x = n^+\delta$ and $c = e-s+n\delta$ you only need to solve how to maximize:
$$\min(x, c - x)$$
Can you take it from here?


How to apply the substitution method to n/2? I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it.

In standard induction proofs you prove a base case, assume it holds for n then show it holds for n+1 and therefore show it applies to integers larger than the base case.

For when you solve recurrences like T(n) = T(n/2) the proof has a base, assumes T(n/2) then proves it holds for T(n). Does this proof not only hold for the numbers that are multiples of two of the base cases? Would this not require an infinitely large number of base cases to show what it holds for?

Could someone please explain this to me?

You're entirely correct - if all you prove is $T(1)$ and $T(n/2) \Rightarrow T(n)$, then you prove that $T(n)$ holds for all powers of $2$. One way to fix that is to prove $T(n)$ for all odd $n$, but that defeats the idea of induction. Instead, usually one actually proves the stronger $T(\lfloor n/2 \rfloor) \Rightarrow T(n)$ or $T(\lceil n/2 \rceil) \Rightarrow T(n)$, and both are enough to deduce $T(n)$ for all $n$.

In many cases, if you can prove $T(n/2) \Rightarrow T(n)$ then you can also prove the stronger claims, but it's technically more awkward. So instead of dealing with this mess, you are only shown the weaker claim. The "interesting" ideas are found already there, and to prove the stronger claim requires just working harder but no new ideas (other than routine tricks used for handling floors and ceilings).


Use a Monitor like a Semaphore? When using monitors for most concurrency problems, you can just put the critical section inside a monitor method and then invoke the method. However, there are some multiplexing problems wherein up to n threads can run their critical sections simultaneously. So we can say that it's useful to know how to use a monitor like the following:

monitor.enter();
runCriticalSection();
monitor.exit();

What can we use inside the monitors so we can go about doing this?

Side question: Are there standard resources tackling this? Most of what I read involve only putting the critical section inside the monitor. For semaphores there is "The Little Book of Semaphores".

Monitors and Semaphores are to accomplish the same task, to ensure that between n processes/threads that each enter their critical section atomically. Although Monitors go towards a Object Ordinate Approach to this, making the code easier to read for example. In this case a Monitor is at a higher level then a Semaphore. You can use a Semaphore to implement a Monitor. In that case a Monitor has a counter variable in the same way a Semaphore does.

The V and P of a Semaphore is very much like the wait and signal of a Monitor. In which wait and signal are used on a Monitors condition variables. They can be used to implement the same functionality of a Semaphore. Even though there are some minor differences, such as for signal with no process in need of being unblocked there is no affect on the condition variable. Along with that locks are also used within the procedure.

While in most cases you don't want to. You can use a Monitors condition variables and lock outside of it (monitor.lock,monitor.condition_i), basically doing the normal things we do within a procedure but on the outside, not within it's function. This is assuming you want to have the critical section outside of the monitor, otherwise there is no need in doing this:

// monitor enter
monitor.lock.acquire();
while(...)  monitor.condition_i.wait( monitor.lock );

runCriticalSection();

// monitor exit
monitor.condition_j.signal();
monitor.lock.release();


Recurrence Relations I am starting to learn recurrence relations in class and I am having issue with this example:

T(N) = 2N - 1 + T(N-1)

I am bit confused as to get the base case.
I'm sorry if this seems elementary, but I am having a difficult time grasping this concept.

Thank you for your help!

In applications to time complexity of algorithms, you are often only interested bounding the growth (i.e., $O(), \Omega()$ asymptotics), and often the initial values incide as multiplicative factors to the solution (or their influence is swamped by the growth of terms that don't include them). So you'll often see sloppy statements that omit initial values.


What is the intuition behind a Free-Choice Petri Net? So I've found this definition in a paper called Time and Petri Nets, Popova-Zeugmann, L., but I am unable to understand the intuition behind it.

  N is a free-choice net (FC net) if each shared place is the only pre-
  place of its post-transitions, i.e., $\text{if}\ t, t' ∈ p^•\ \text{then}\ ^•t\ =\ \{p\}\ =\ ^•t'$.

Could someone give me an example of what this allows to, or disallows to do?

The literature on Petri nets has many papers that really aim to teach the concepts used.

In the case of free-choice Petri net, such an introduction can be found in the paper Structure Theory of Petri Nets: the Free Choice Hiatus by Eike Best, in the ACPN (Advanced Course on Petri Nets) 1986. (An online copy is here.)

If anywhere, the intuition behind free-choice nets should be explained there, but that doesn't really happen, and I haven't seen such an explanation elsewhere, either.

As far as there is an intuition behind free-choice nets, it is expressed by their name: whenever there is a choice, say, between step B or step C (that is to say: we have a place A with an arc to transition B and an arc to transition C), then that choice is free, that is to say, neither B or C are subject to any other additional conditions (that is to say, they cannot have additional input places).

Rather than focusing on intuition, the paper describes free-choice nets as follows, and I think this is the standard way to explain them:

One of the reasons Petri nets interest us is that they offer descriptions of concurrent system behaviour that can be statically analyzed. We can prove certain properties of the behaviour of Petri nets.
However, for unrestricted Petri nets, certain important properties are extremely hard to analyze; for instance, the question whether the net is live, or whether a given marking can be reached. So it is interesting to study restricted forms of Petri nets for which such analysis is easier.
One possible restriction is to say: no place may have more than one input transition, or more than one output transition. This type of Petri net is called an S-net. This eliminates parallelism and basically turns the net into a state machine. For instance, we can no longer write down a process in which the first thing to happen is A, then B and C in whatever order, and, finally, D. We can't put B and C in parallel.
Another restriction is the reverse: no transition may have more than one input place or more than one output place. This type of Petri net is called a T-net or marked graph. Now, we do have parallelism, but we no longer have choice. For instance, we can no longer write down a process in which the first thing to happen is A, then either B or C, and, finally, D. We can't have a choice between B and C.
Both restrictions are very severe, so it's interesting to look at compromises. Free-choice nets are just that: to quote Wikipedia, they are the nets in which every arc from a place to a transition is either the only arc from that place or the only arc to that transition. I.e. there can be both concurrency (parallelism) and conflict (choice), but not at the same time. So this is a proper generalization of S-nets and T-nets.
Certain properties of the behaviour of Petri nets that are hard or impossible to decide for arbitrary Petri nets become doable for free-choice Petri nets.

So the prime motivation for free-choice nets is not any particular intuition, but the fact that they allow certain forms of static analysis of behaviour.


Combining adjacent memory blocks This is a conceptual issue that I am having in designing an algorithm for a memory allocator that works in conjunction with memory pooling.  Free blocks are put on one of several free lists within the pool.  The size of the block determines which list it is on.  The question is how to figure out if the adjacent physical memory blocks are free and available for coalescing when they are on different lists? Or, in other words, how to figure out if physically adjacent memory blocks are also free when the blocks are on different lists and then combine them.

Granted, the time on this is expensive so I plan to run this only when a suitable block cannot be found or carved out of an existing block.

The only viable approach that I can think of is to scan the entire pool while looking for a signature.  Then search all the lists to verify that the address of that block is on a list.

I have done some research and found the following links:

How does worst-fit memory allocation react when encountering contiguous empty memory blocks?
http://faculty.kfupm.edu.sa/ICS/saquib/ICS202/Unit34_MemoryManagement.pdf

Any suggestions or ideas?

I would suggest keeping a hash table (which you possibly are) to search for addresses.  Use one table for all the different pools.  Do not keep separate tables for each pool.

The idea is that you start from a newly released block. You know its start address and its length.

To find blocks after the newly released one we simply calculate the first address after the block and search for it.  If we find one we join them.

Now we search backwards.

To search backwards our address table must contain not only the start, but the end of blocks.

We search the table for entries matching our end-of-block address.  Again if we find them we join.

If we are doing this check every time we get a newly released block then we do not need to check more than one post- and pre- address block each time.  As these are hash table look-ups they'll be fast.

If we do this check periodically we will need to scan all blocks systematically for matches, including rechecking new joined up super blocks for additional matches.


The sorting problem for partially ordered sets I have two questions about sorting for posets, one easy and one hard:

Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ from the set. Is there a sub-quadratic time algorithm that can accomplish this, perhaps for some suitable data structure?

Hard: suppose we actually want to sort the list by putting it into some suitable data structure (such as a directed graph). Does there exist a nice data structure leading to a sub-quadratic time sorting?

The second is the natural generalization of the sorting problem to posets. The first is an easier variant that will suffice for this application.

Take a worst case scenario.

The set is built out of pairs of objects $a_i, b_i$ where $a_i < b_i$ and there exists no order between $a_i < b_j$ when $i\neq j$.

This means that to know whether you can delete an element you need to check it against every other element resulting in a quadratic general case.

The best data structure to avoid that is where each node has a direct reference to which nodes it is greater or equal to. But to build that you need a quadratic algorithm.


Regularity of language of words containing a square $$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this language regular or not regular?

Slightly more formally, for an alphabet $\Sigma$, the language of repetitive strings over $\Sigma$ is defined as follows.
$$ RR = \{w: w=uyyv \text{ for some }u, y, v \in \Sigma^*, y \text{ is not empty}\}$$ The question is, is RR a regular language?

There are three cases.

$\Sigma$ has one symbol.
WLOG, let $\Sigma=\{a\}$. Then $RR = aaa^*$ is a regular language.
$\Sigma$ has two symbols.
WLOG, let $\Sigma=\{a, b\}$. Suppose $w\in RR$ does not contain $aa$ or $bb$. That is, if an $a$ in $w$ is followed by another symbol, that symbol must be $b$; if a $b$ in $w$ is followed by another symbol, that symbol must be $a$. That means, if $w$ starts with $a$, it must contain $abab$; otherwise, it must contain $baba$. So any string in $RR$ must have one of $aa, bb, abab$ and $baba$ as its substring. Obviously, any string  that contain one of those four strings is a repetitive string. So we can write $RR = (a+b)^\ast(aa+bb+abab+baba)(a+b)^\ast$ as a regular expression. Hence, $RR$ is regular.
$\Sigma$ has 3 or more symbols. This is the most interesting case.
WLOG, let $\Sigma\supseteq\{a,b,c\}$. We know there is an infinite sequence $u$ of $a,b,c$'s that has no consecutive repeated substring. Let $u_k$ be the first $k$ symbols in $u$. For example, if $u=abcabacabcb\cdots$, then $u_1=a, u_2=ab, \cdots, u_6=abcaba, \cdots$.
Let $i<j$ be two positive integers. Then $u_j=u_iv$ for some non-empty string $v\in\Sigma^*$. Since $u_iv=u_j\notin RR$ and $u_jv=u_ivv\in RR$, $u_i$ and $u_j$ are in different Myhill–Nerode equivalent classes for $RR$. So we have infinitely many Myhill–Nerode equivalent classes that are represented by $u_1, u_2, \cdots$ respectively. According to the Myhill–Nerode theorem, $RR$ cannot be regular.

In the analysis for the last case, we have used one of Alex Thue's results on non-repetitive string over three symbols. He showed that there are many such strings of infinite length. One of them is given by the following procedure. Let $\Sigma = \{a,b,c\}$. Let $A_0 = a$ and $\phi : a \mapsto abcab, b\mapsto acabcb, c\mapsto acbcacb$. So
$$\begin{aligned}
A_0 = a& \\
\phi(A_0)= a&bcab\\
\phi^2(A_0)= a&bcab\ acabcb\ acbcacb\ abcab\ acabcb\\
\phi^3(A_0)= a&bcab\ acabcb\ acbcacb\ abcab\ acabcb \\
a&bcab\ acbcacb\ abcab\ acabcb\ acbcacb\ acabcb\\
a&bcab\ acbcacb\ acabcb\ acbcacb\ abcab\ acbcacb\ acabcb\\
a&bcab\ acabcb\ acbcacb\ abcab\ acabcb\\
a&bcab\ acbcacb\ abcab\ acabcb\ acbcacb\ acabcb\\
\cdots\end{aligned}
$$
Note that $A_0$ is a prefix of $\phi(A_0)$. By a very easy mathematical induction, we can show that $\phi^n(A_0)$ is a prefix of $\phi(\phi^{n}(A_0))=\phi^{n+1}(A_0)$. (Thinking about this recurrence relation, I can feel the logic beauty of self reference. That is why I cannot help but writing down this example.) So we can specify a unique infinite string, $\omega$ whose prefix can be $\phi^n(A_0)$ for any $n$. $\omega$ is the wanted string. For a proof that $\omega$ is a string without consecutive repeated substrings, reader can check Axel Thue, Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen; Norske Vid. Skrifter
I Mat.-Nat. Kl.; Christiania; 1912 page 1–67.

In fact, as HendrikJan pointed out, the language of repetitive strings over three or more symbols is not context-free. This fact is proved in Repetitive strings are not context-free by R.Ross and K.Winklmann, RAIRO - Theoretical Informatics and Applications, 16 (1982) 191-199.

Since the complement of a regular language is also a regular language, the complement of the language of repetitive strings is also regular, too. In fact, if the alphabet has one or two symbols, they are finite languages. All non-repetitive strings over $\{a\}$ are $\{\epsilon, a\}$. All non-repetitive strings over $\{a,b\}$ are $\{\epsilon, a, b, ab, ba, aba, bab\}$.

Exercise. Show that an infinite language that does not contain a square is not context-free.

Question. Is the language of almost repetitive strings defined below regular? If no regular, is it context-free?
$$ RR = \{w: w=uyxyv \text{ for some }u, y, v \in \Sigma^*, y \text{ is not empty}, x\in\Sigma\}$$


Reduction from Vertex Cover to an Independent Set problem Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim that independent set can also be solved in time polynomial in terms of $n$ and exponential in terms of $k$ ? ($k$ here stands for the minimum size of an independent set)

No. The typical reduction from Independent Set to Vertex Cover doesn't preserve the parameter ($k$). A graph with a vertex cover of size $k$ has an independent set of size $n-k$, so we no longer have $n$ restricted to the polynomial part.

This separation is one of the basic conjectures of Parameterized Complexity. Parameterized Complexity is a bivariate complexity theory where problems are given with not only the normal input, but also a parameter. For example the (natural) parameterized version of Vertex Cover is:

  Vertex Cover
  Input: A graph $G$, a positive integer $k$.
  Parameter: $k$.
  Question: Does $G$ have a vertex cover of size at most $k$?

So each parameterized problem has two (formally explicit) metrics: the size of the input $n$, and the parameter $k$. We then say that a problem $\Pi$ is fixed-parameter tractable if there is an algorithm that decides each instance $(x,k)$ of $\Pi$ in time bounded by $f(k)\cdot|x|^{O(1)}$ for some computable function $f$ dependent only on $k$ (i.e. polynomial with constant degree in $|x| = n$, but essentially free in $k$). We call the class of all such problems $FPT$.

So Vertex Cover is in $FPT$ when parameterized by the size of the vertex cover.

The main intractability framework for Parameterized Complexity is called the $W$-hierarchy, a series of classes $W[t]$ where $W[i] \subseteq W[i+1]$ and $FPT \subseteq W[1]$. Although it's split into lots of classes, the $W$-hierachy bears a practical relationship to $FPT$ in a similar manner to that of $NP$ to $P$, in that if a problem is $W[t]$-hard for some $t$, then it has no $FPT$ algorithm unless $W[t] = FPT$, and we conjecture that $FPT \subset W[1]$ for similar reasons to $P \subset NP$.

Getting back to your question again, finally, it turns out that Independent Set is $W[1]$-complete when parameterized by the size of the independent set. That is, unless $W[1] = FPT$, Independent Set has no algorithm with running time bounded by $f(k)n^{O(1)}$ for any $f$, where $k$ is the size of the independent set.

Additional Note:

Of course we don't have to parameterize by the size of the answer, we can use anything we feel like, the normal guidelines are that it should be something that can reasonably be expected to be small compared to the input size, and it should be able to vary independently of the input size. A common structural parameter for example is the treewidth of a graph. You can parameterize by measures relating to the size of the input, but then we have to introduce a bunch of different classes.


What's the error-correcting capacity (randomly errors, or burst errors) of polar code? Polar codes, invented by Arikan, with low encoding and decoding complexity. But the minimum distance of polar codes is not great. The normalized minimum distance goes to 0 with the block size. Yet, the existing decoding algorithms for polar codes can asymptotically achieve channel capacity.

Generally, a code with minimum distance $d$ can correct $\frac{d-1}{2}$ errors (random errors). And Polar code is also error-correcting code, I was wondering how many errors can it correct( e.g. A $[2048, 614]$ with $BEC(0.19)$ polar code.)? Much appreciated.

I am not an expert but I think you may be asking the wrong question. Polar codes don't have a meaningful "error correction capability" obtainable as in algebraic codes by (d-1)/2. Alternatively, this is not the meaningful parameter of significance.

For finite lengths their performance is usually analyzed in BEC (Binary Erasure Channel) and AWGN channels (Additive White Gaussian Noise). The well-cited paper On Finite-Length Performance of Polar Codes: Stopping Sets, Error Floor, and Concatenated Design by A. Eslami and H. Pishro-Niki on arxiv here as well as some more recent papers confirm this.


What counts as an operation? Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all operations to be equal?

Surely, dividing two very large numbers is more time-consuming than adding one to a number (as in each iteration of a for loop). Multiplication, for example, can consist of any number of small additions. So, instead of just adding them up shouldn't we be applying some kind of weight to each operation depending on the type of operation (addition, multiplication, etc) and the size of the numbers involved?

My problem is that I am being asked to prove that the complexity of my algorithm is $O(f)$ (for some function $f$) and I am not sure how to do this in a mathematically rigorous fashion because of the inherent vagueness in the definition of a "simple operation". So how would I go about this?

Simple operations are anything that takes constant time to achieve.
The confusion is that division does not seem to take constant time, and in fact, in general, it does not. BUT!

Division and addition both take constant time if, say, you are adding two 32-bit integers together, which is usually how it goes. However, if you are adding arbitrarily large numbers, they won't really be constant-time, though sometimes I think people will treat it as if it is because the numbers are kind of assumed to not get super big.


Finding simpler equivalent regular expressions I'm doing an exercise from my book that says:

Let $r$ and $s$ be arbitrary regular expressions over the alphabet $\Sigma$. Find a simpler equivalent regular expression:
a. $r(r^*r + r^*) + r^*$
b. $(r + \Lambda)^*$
c. $(r + s)^*rs(r + s)^* + s^*r^*$

The book doesn't cover how to simplify regular expressions, so I searched online and I presumed you would use the algebraic laws for regular expressions. I was able to use these laws to come up with something for part a. only:
a. $r(r^*r + r^*) + r^*$
$r(r^+ + r^*)+r^*$
$r(r^+ + r^+ + \Lambda) + r^*$
$r(r^++\Lambda)+r^*$
$rr^+ + r\Lambda + r^*$
$rr^+ + r + r^*$
I don't know how to approach b. or c., because b. has $(r + \Lambda)^*$ and c. has $(r+s)^*$, and I couldn't find how to deal with these. Any hints?

A better approach would be to understand what words do these regular expressions represent. For example, what words are in $(r+\Lambda)^*$? They look something like $r_1r_2 \Lambda r_3 \Lambda = r_1r_2r_3$, where $r_1,r_2,r_3$ are generated by $r$. It seems that $\Lambda$ isn't making much of a difference. This should help you simplify $(r+\Lambda)^*$. The same approach works for the other expressions (including the first one, which you haven't simplified completely).


What is the best known data structure for online dk-NNG? I want to build the distance constrained k-Nearest Neighbours Graph, i.e. for every point $p$ in the data cloud $P$ there are at most $k$ undirected edges to points that are closest among all possible vertices using $L_2$ metric with additional constraint that are no further than $d$.

There are only insertions (in batches of $10^6$ points) and neighbourhood retrieval queries used. The results have to be exact - I cannot use approximate nearest neighbours or reduce dimensions.

The setting is following:
There are 50 dimensions, not correlated. The $k=9$ is number of neighbours, $d$ is given distance. The data is sparse in every dimension, mean and median are meaningful, data is random and unstructured in any way (but for sure not from uniform or Gaussian distribution).

So far I have tried to build parallel kd-tree with partial rebalancing, the ball trees, m-trees, r-trees, Sparse ktree (octree with more dimensions) partitioning and two-projection hashes. But I am facing problem, that either insertion time is far too long or k-nng queries are too long. I think this happens because the structures are either static or not really prepared to maintain full neighbourhood graph.

I have tried linear scan, it performs good for very small data, worse than z-curve localised version or sparse ktree. Up to some $n$ it outperforms any treelike structure. I made one modification to naïve algorithm: used one AVL (right threaded) per dimension keeping nodes connected among trees and checked only points within distance $d$ at each dimension - this one performs well, but due to its memory consumption and lack of multidimensional structure scales poorly.

What data structure would be the best in practice for dk-NNG?
If this is not enough, I would like to optimize the number of neighbours checked, for localised data the number of bins traversed.

I'm not familiar with dk-NNG, but have you tried a PH-Tree? It has excellent insertion times and very good kNN search.
I tested several scenarios with up to 40 dimension and $10^6$ and $10^7$ points. It usually competes with R*Tree (R-Star-Tree) for kNN-search, but has much better update performance.

You could also try an R*tree, they are almost always faster than a standard R-Tree. An implementation in Java can be found here.


Strengths and limitations of arrays What are the strengths and limitations of arrays? What considerations go into choosing an array over another data structure, or vice-versa?

Here a simple answer is;

Arrays

allow fast random access in $\mathcal{O}(1)$ to their elements since and they are sequential in memory.
$\mathcal{O}(1)$ time write or update an element
if not created in heap memory size is very limited.
The size is fixed.

Vectors

Access and write is similar to array
The size not fixed. When capacity is full, extended.


Showing a problem is $P$-complete Consider the well-known language: $$L = \{\langle M,x,1^t \rangle \ \ |\ \text{$M$ accepts $x$ after $t$ steps}\}$$

I've encountered some technical problem while trying to show a logarithmic reduction from some $L'\in P$ (which will show completeness of $L$)

Basically, the reduction is: $$f(x) = \langle M_{L'},x,n^c\rangle $$

Where $n^c$ is the time it takes for $M_{L'}$ to decide some input, $x$.

At first everything seems legitimate, but...  How do we construct $M_{L'}$ at the first place?

In other words, do we have an "access" (as the reduction function) to the machine description?

You need to show that for every $L'\in P$ there exists a logspace reduction from $L'$ to $L$. Your $f$ has $\langle M_{L'}\rangle$ hardcoded into it. The encoding was part of its definition, $f$ does not ask what is the encoding of the machine for $L'$ when it tries to compute $f(x)$.

One way to think of this is as follows: consider the sequence of functions $\left\{f_{s ,c}\right\}_{c\in\mathbb{N}, s\in\{0,1\}^*}$ where
$f_{s, c}(x)=\left(s, x, 1^{|x|^c}\right)$. Since $L'\in P$, there exists a function in this sequence which is a reduction from $L'$ to $L$ (the specific index depends on the machine deciding $L'$, but we don't really care about it).


Defining Local Search stopping criteria When performing a local search, for example, a 2-node exchange in a metaheuristic (like GRASP), what is the usual stopping criteria for that procedure?
Some bibliography says that the local search stops when no further improvement can be found in the neighboorhoud of the current solution. My question is: whether it is correct to stop the local search as immediately as a first better solution is found?

The stopping criterion depends on the specific algorithm used; some common ones include after a fixed number of iterations, or after the total improvement over the past $t$ iterations is at most $u$ (for some parameters $t,u$).

No, it's not correct to stop after you make the first improvement.  Usually you will need many iterations of improvements.


Show that Vertex-Cover is NP-complete, using Stable-Set My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too.

My approach: i know, Stable-Set is NP-complete, and all Problems that are NP-complete can be reduced to each other. If i could solve one NP-complete problem, i might be able to solve all NP-complete problems. It should be possible to create a function with polynomial complexity to reduce Vertex-Cover to Stable-Set. At least, this was, what my Professor told.

Now all i have to do, is to find this polynomial function, in order to Show that Vertex-Cover is NP-complete. But here is where i am stuck.. so i need some advice how to build such functions.

You have it backwards- you have to reduce a known NP-complete problem to the thing that you want to show is NP-hard. If you were to reduce Vertex-Cover to Stable-Set, you would be saying that Stable-Set is at least as hard as Vertex-Cover... but Vertex-Cover could still theoretically be polynomial.

Since this seems like a homework problem, I don't want to actually give the solution here. What you need to do is find a way of transforming the Stable-Set problem into the Vertex-Cover problem. That way, any solution to Vertex-Cover would be a solution to Stable-Set, so VC is at least as hard as SS. After that, you need to show that VC (note that you need to work with the decision version of VC and SS, which asks does there exists a VC/SS of size k) is in NP by showing that given a witness, you can check if it's correct or not.

Solutions to both problems are sets of nodes in a graph. If there's a VC of size k, that means that all edges have at least one node touching them. If there's a SS of size k, that means no edge has two nodes touching them. I'd suggest drawing out some graphs, finding the VC and SS of both of them, and seeing if there's a relationship between the two sets, as well as the size of each set and the number of nodes in the graph. While I haven't worked out a proof, I don't think you need to do a transformation on the graph itself (like drawing in new nodes/edges) in this case. However, for some problems, you might need to.

Here is a handout on NP-completeness reductions, which might help you. I suggest reading some reductions to get a handle on it.


Why is the type ∀t.t un-inhabited in System F? How do you prove that there exists no term with the type $\forall t. t$ in System F?

I tried searching through Pierce's TAPL and Reynold's ToPL, but could not find anything. I suspect that the proof may involve some kind of model theoritic argument, but I fail to see where to start.

The simplest proof is giving a model where types are interpreted as propositions, and terms as proofs, then observing that $\forall \alpha.\alpha$ is interpreted as the false proposition, so any $\cdot \vdash t : \forall \alpha.\alpha$ would be a proof of falsehood. It is important to remember that $\forall \alpha.\alpha$ is only uninhabited for sure in the empty context $\cdot$, in other contexts it may be trivially inhabited.

Concretely, first interpret each $A$ type with $n$ free type variables in the following way:

$$
\begin{alignat*}{2}
& [\![ A ]\!] && : \mathsf{Bool}^n \to \mathsf{Bool}\\
& [\![ \alpha ]\!]\,\gamma && := \text{$\alpha$-th component of $\gamma$}\\
& [\![ A \to B ]\!]\,\gamma && := [\![ A ]\!]\,\gamma \Rightarrow [\![ B ]\!]\,\gamma\\
& [\![ \forall \alpha.\,B]\!]\,\gamma && := [\![B]\!]\,(\mathsf{true},\,\gamma)\,\land\,[\![B]\!]\,(\mathsf{false},\,\gamma)
\end{alignat*}
$$

Interpret every typing context $\Gamma$ with $n$ free type variables as:

$$
\begin{alignat*}{2}
  & [\![\Gamma]\!] : \mathsf{Bool}^n\to \mathsf{Bool}\\
  & [\![\Gamma]\!]\,\gamma := \bigwedge\limits_{A\,\in\,\Gamma}\,[\![A]\!]\,\gamma
\end{alignat*}
$$

Then show for each $\Gamma \vdash t : A$ term, that for each truth valuation $\gamma : \mathsf{Bool}^n$, if $[\![\Gamma]\!]\,\gamma = \mathsf{true}$, then $[\![A]\!]\,\gamma = \mathsf{true}$. This can be done by induction on terms.

Now, $[\![\forall \alpha.\alpha]\!]$ with no free type variables evaluates to $\mathsf{false}$, since it's $\mathsf{true}$ when $\alpha$ is instantiated to $\mathsf{true}$, and $\mathsf{false}$ when it's instantiated to $\mathsf{false}$, and the conjunction of these is $\mathsf{false}$. Assuming $\cdot\vdash t : \forall \alpha.\alpha$, we have by the previous result that $[\![\forall \alpha.\alpha]\!]$ is $\mathsf{true}$, a contradiction, hence there is no $\cdot\vdash t : \forall \alpha.\alpha$.


Is it true that if L* is recursive, L is also recursive? Is it true that if $L^*$ is recursive, where $*$ is Kleene star, $L$ is also recursive?
I know that the opposite direction is true:

If $L$ is recursive, then $L^*$ is recursive.

But I don't know how to prove it in this direction.

No.
Take any language $L$ over $\Sigma = \{0, 1\}$ that contains 0 and 1. Then $L^* = \Sigma^*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively enumerable language.


Formula for sufficiently lengthy encryption key? As you add length to an encryption key, at some point the message becomes impossible to brute-force decrypt. This is because at that point, if you go through all the possible keys, you'll get many meaningful decryptions just by random chance and you won't be able to determine which was the original message.

As you add length to the message though, these meaningful decryptions become rarer until there is once again a small enough number of them left to figure out which is the right one (if you know what you're looking for, that is).

Has anybody figured out a way to estimate the required key length for this obfuscation by quantity to happen for more popular encryption algorithms?

That's not how security works. Sometimes you want to use encryption in circumstances in which there are two possible messages, and you want encryption to be secure even in these cases. That's because encryption is used as a building block in more complicated cryptographic protocols. Also, attacks could be based on multiple related (or even unrelated) messages.

Instead, security is based on the fact that nobody can try and decrypt a message with respect to all possible keys since there are too many, and there is no better way of finding the key. The second requirement is security of the cryptosystem, and currently there is no way to prove it. Instead, we use standard systems which are being researched and so far have revealed no weaknesses.

Suppose that our system is cryptographically secure. How can we guarantee that there are too many keys to try all of them? The standard approach is to agree on a key length in advance, usually 128 bits (or more). Classical (rather than quantum!) computation cannot run $2^{128}$ steps even if you parallelize it across atoms of the universe, and wait a million years. That's considered secure enough.


Resetting Vector clocks in distributed systems I understand that vector clocks are preferred over lamport clocks because sometimes lamport clocks cannot account for the casuality and we use extra space to store the timestamps in the vector clocks.
What i dont understand is about the resetting of the vector clocks.
Why do the vector clocks overflow and how the resetting is done in such scenario?

Vector clocks overflow for the same reason that regular integers do. Vector clocks generally maintain a fixed number of bits per process to capture the event count for each respective process. There is naturally a maximum value that each of these bit strings can represent. Any one of these values can potentially be increased beyond their capacity, and thus overflow. For example, if we presume that one process has the following vector clock:
$\vec{P3} = (5, 3, 7) = (101_2, 011_2, 111_2)$
And then $P3$ has an internal event, increasing their event count from 7 to 8:
$111_2+1=000_2$
This number is too large to be represented with only 3 bits. And so the clock overflows back to zero. This will prevent us from properly computing causal ordering in this system, and undermines the consistency of the distributed system.
We can of course allocate many bits to each process to reduce this risk. However, since the vector clocks are regularly passed between processes, we would like to minimise this since it reduces the throughput of communication channels (regardless of whether it is a network, file, shared memory etc).
Therefore we require a mechanism to safely reset clocks within the system, such that we can maintain the constraints of the distributed algorithm. From my understanding this can be done in a few ways:
Blocking Globally
If a process detects that its own counter is about to overflow, it sends a message to every other process informing them to reset their event count for that process on their local clocks. This will halt the distributed algorithm until the process that initiated the reset receives confirmation from every other process.
Consensus Protocols
Depending on how the distributed algorithm is structured, we may not require the full event history to ensure causal ordering for events. Some distributed algorithms have rounds of consensus which allow us to repeatedly incrementally work from a point of stability. These are like rounds in a card game, and offer natural opportunities to reset clocks. This is particularly true of Gossip algorithms. This is very similar to the global blocking algorithm above, but does not wait until an overflow to reset clocks.

There might be some other vector clock reset mechanisms that I am not aware of. It is also possible to organically grow the number of bits used per process as required (which might actually be easiest).
You can read more on these topics with the following academic papers:

Resetting Vector Clocks in Distributed Systems
Randomized Gossip Algorithms


Can a non-regular language be made regular via concatenation when they don't share characters? So this is a follow-on question to my other question (Can we make a non-regular language regular via concatentation?).

Given the following,

$L = \{0^n1^m2^m \mid n>1, m>1\}$

$A = \{0^n \mid n>1\}$

$B = \{1^m2^m \mid m>1\}$

Is $L$ in fact just $A$ and $B$ concatenated (I believe it is, but I want to verify that)?

Further, does proving $B$ non-regular prove that $L$ is non-regular since they don't share characters?

First, the equality $L = AB$ is correct. Next, if you know that $B$ is non-regular, you can prove that $L$ is non-regular as follows.

Suppose that $L$ is regular. Then $(00)^{-1}L = \{0^n1^m2^m \mid n \geqslant 0, m>1\} = 0^*B$ is regular. It follows that $0^*B \cap \{1,2\}^* = B$ is regular. Contradiction.


Why does 9 qubit Shor code have distance 3? Distance of a Stabilizer code($S$) is defined by minimum weight of an element in $N(S)-S$ .

Why 9 qubit Shor code has distance 3?

Is there a way to directly see $N(S)-S$ from $S$?

Distance 3 means that an error operator acting on 3 qubits maps a valid code-state to another valid code-state. For the Shor code, an example would be a simultaneous phase flip on the 1st, 4th and 7th qubits ($Z_1Z_4Z_7$).

You can easily check that $Z_1Z_4Z_7∉S$, but that it commute with $S$, hence is part of $N(S)$.


Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time? The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.

$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of insertion sort, it implies that $O(n^2)$ is upper bound of algorithm no matter what type of input is, means it doesn’t matter whether input is sorted, unsorted, reverse sorted, have same values, etc the upper bound will be same $O(n^2)$. But this is not the case of insertion sort. Insertion sort running time depends on type of input used. So when the input is already sorted, it runs in linear time and doesn’t take more that $O(n)$ time.

Therefore to write insertion sort running time as $O(n^2)$ is technically not good.

We use $\Theta$-notation to write worst case running time of insertion sort. But I’m not able to relate properties of $\Theta$-notation with insertion sort, why $\Theta$-notation is suitable to insertion sort.If $f(n)$ belong to $\Theta(g(n))$ we write it as $f(n)= \Theta(g(n))$, then $f(n)$ must satisfies the properties. And properties state that there exits constants $c_1$, $c_2$ and $n_0$ such that $0$$\leq$$c_1\cdot g(n)$$\leq$$f(n)$$\leq$$c_2\cdot g(n)$ For all $n>n_0$. How does the insertion sort function lies between the $c_1\cdot n^2$ and $c_2\cdot n^2$ for all $n>n_0$.

Running time of insertion sort as $\Theta(n^2)$ implies that it has upper bound $O(n^2)$ and lower bound $\Omega(n^2)$. I’m confused as to whether the lower bound on insertion-sort is $\Omega(n^2)$ or $\Omega(n)$.

You are confusing two different notions.
The definition of $\Theta$ that you give is correct, and indeed the running time of insertion sort, in the worst case, is $\Theta(n^2)$, since it has a quadratic running time.

The fact that this is the worst running time is somewhat irrelevant here. You have some function, and you are classifying it as $\Theta(n^2)$, because you can.

Indeed, the runtime of the algorithm in the best case can be a different function, which may or may not be $\Theta(n^2)$.

It may make more intuitive sense to just say that in the worst case, the runtime is $O(n^2)$, which implies that in all the cases the runtime is $O(n^2)$, but observe that this is also implied by the stronger $\Theta$ notations.

As an illustrative example, consider this: You can get home in two paths, one takes 10 km, and the other 3 km, but the 3 km is only open on certain hours of the day.

You can say the following: when you walk home, in the worst case you will walk exactly 10 km. This is true, and it implies that you always walk at most 10 km. But the former is a stronger claim, so why not use it?