Finding potential function for dynamic array About dynamic array, doubling it's size with every element that is beying its limit:

From what I understand, the number of operations between the $n$th element and the $n+1$th  depending on if $n+1$ is $2^k + 1$ (for some $k \in \mathbb{N}$).

If so, we need to allocate a new array and copy the last n elements + the new element. From what I see, if I define a potential function $\phi(n)$ then it should be $\phi(n+1) = \phi(n/2) + n/2 + 1$

Explanation: $\phi(n/2)$ is the last time we expanded the array, $n/2$ are the next elements that were inserted to only one (the last) array, and $1$ is the current element.

However, from what I saw (wikipedia) the actual function is  $\phi(n) = 2n - N$ where $n$ is number of elements and $N$ is array length.

Either way, $\phi(n) \le 2n$, and my HW assignment was to show it is bounded by $3n$ :(

Is $3n$ a too big bound or am I missing something?
Is the $\phi$ equal to the one wiki has (I can't see how...)? how do they differ

EDIT: I now have a new notion about the answer - using the bank / accounting method. My initial array has size of 2. The assignment is to show that paying 3 for each insertion will ensure I'm never in "overdraw". I know that if I only pay 2 for each insertion, then when I insert the first 2 elements, I paid 4 and used only 2, when I insert the 3rd, I use 3 and pay only 2 (so I use 1 from the bank, which leaves only 1 there). In the 4th insertion I'll add another 1 to the bank, but in the 5th insertion I'll have to overdraw!

So, clearly $2n$ isn't enough!! which makes me think $3n$ will do.

I know what I added here might contradict my first notion, and I don't understand to actually answer this. Any help will be appreciated. Thanks

$2nd$ EDIT:

The HW assignment is to show a specific $\phi(n)$ so that $a(n) = t(n) + \phi(n) - \phi(n-1)$, where:

$a(n)$ is the amortized value of the $n$th insertion
$\phi(n)$ is the potential function
$t(n)$ is the actual value the insertion is worth ($1$ or $n+1$)

It's easy to see that, using the Wikipedia function ($\phi(n) = 2n - m$ [m is the array's size]$)$, if $t(n) == 1$ then $a(n) = t(n) + \phi(n) - \phi(n-1)$ is actually $a(n) = 1 + [(2n - m) - (2(n-1) - m)]$ which is $1 + 2 = 3$. But what about when $t(n) = n+1$?

You've already proved it! You said you were meant to bound it by $3n$ and you've bound it by $2n$. Well, $2n \leq 3n$, right?


Extracting non-duplicate cells in a particular matrix with repeated entries Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \left\{1,...,\frac{n^2}{2}\right\}$ is written to two cells so that each cell contains exactly one number.

How can I show that $n$ cells $c_{i, j}$ can be chosen with one cell per row and one cell per column such that no pair of cells contains the same number.

This was an example problem for an exam I'm studying for. I tried it now for several hours but I can't get it right. I think random permutations can help here but I am not sure.

Choose a permutation $\pi$ uniformly at random, and let $P = \{ a_{i, \pi(i)} \mid i\in [n]\}$.  The set $P$ contains exactly one element in each row and each column of given the matrix $A$.

Now consider any pair of entries in $A$ with the same value.  If those two entries lie in the same row or the same column, they cannot both be in $P$.  If those two entries are in different rows and columns of $A$, then the probability that both entries lie in $P$ is exactly $1/n(n-1)$.

There are $n^2/2$ different values in the matrix.  So the expected number of values with both entries in $P$ is at most $n^2/2n(n-1) = n/2(n-1)$.  If $n\ge 4$, this expected value is less than $1$, which implies that the probability of choosing no matching pairs must be positive.


Are there color conventions in CS? I don't remember seeing any color conventions in Computer Science used to represent some abstract information or to simplify diagrams.

For instance, chemists have the CPK coloring which associates elements to colors.

Electrical technicians have the electronic color code for resistors and wire colors (black for neutral/ground red for phase).

Physicists have conventions for magnets (North pole red, South pole blue), and even quarks have colors!

In CS, one of the only cases I know of are red-black trees, but it's not so much the concepts themselves, but this particular implementation.

I'm asking because I wonder if these colors could be useful in some contexts, for instance: if CFGs were always depicted with a given color for starting node and a different one for ending node; or in programming languages, having something as "immutable data is green, mutable data is blue", or in cryptography ("hash functions are yellow, symmetric encryption is blue, asymmetric is orange"), or computer architecture ("processors are red, memory is blue, buses are green"), etc. I've never seen for instance UML color conventions, or in automata theory, or other areas which frequently use diagrams. Apart from the very universal conventions of "green = good/pass, red = bad/stop", nothing seems to stick.

Computer security (especially, military-oriented branches of it) has the concept of red/black separation, with accepted definitions of what is red and what is black.


Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive? Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$.

How do I show that each $L_i$ are recursive ?

I see that for $x \in \Sigma^*$, $x$ belongs to exactly one $L_i$.

My idea is to run every Turing machine simultaneosly, stopping as soon as one of them accepts $x$ (must happen at some definite time by assumption).

What theory can I use to make my idea rigorous ? I've considered an non-deterministic TM, but also a $k$-tape TM, but none seems to suit my needs ?

Can someone help ?

If you already proved the binary case, a more formal answer is to observe that, for any i, the complement of $L_i$ is r.e. since it is a finite union of r.e. sets. Since the set and its complement are r.e., it is recursive.


how to mapping reduce any r.e. language to the diagonal language K? We know that the halting problem $A_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to $A_{TM}$. How can this be done?

Let $A=L(M)$ be any r.e. language. We reduce $A$ to $K$ using the following reduction function $f(x)$.

Given any word $x$, construct a TM $N_x$ such that, when run on input string $y$, it ignores it, and simulates $M$ on $x$. If $M$ accepts, we make $N_x$ accept, otherwise we make $N_x$ diverge. We let $f(x) = \langle N_x \rangle$.

$f$ is clearly a total computable function. It is also simple to check that $x\in A \iff f(x)\in K$.

Note that $f(x)\in K$ means that the TM encoded by $f(x)$ halts on input $f(x)$. This means that $N_x$ halts on input $y = \langle N_x \rangle$. The value of $y$ is actually irrelevant, since $N_x$ will ignore it, and halt only when $M$ accepts $x$, i.e. when $x\in A$.

In a sense, the "trick" here was to ignore the diagonal property which is used in the definition of $K$, and just make $N_x$ halt on all inputs $y$ or diverge on all inputs $y$. In such way, we surely include the diagonal, and we simplify the reduction function $f$.

If we really wanted, it is possible to define a function $f(x)$ which produces the encoding of $N_x$, which always halts (or always diverges, if we prefer that) on any $y\neq f(x)$, and instead halts on the the diagonal $y=f(x)$ if and only if $x\in A$. Defining such $f$, however, is harder, and requires the second recursion theorem. Ignoring $y$ makes $f$ much simpler to construct.


Difference between read-only Turing machine and non-erasing Turing machine I cannot quite feel the difference between two models.

The first one is read-only Turing machine which is basically the same as Turing machine with write protected input. See this question for example: Single-tape Turing Machines with write-protected input recognize only Regular Languages

It was said that it indeed recognizes only regular languages because there is no way to copy an input without rewriting it somewhere.

And there are non-erasing Turing machines that (in binary representation) cannot overwrite $1$ with $0$. This is equivalent to full power Turing machine as it was explained here Non-erasing Turing machines and loss of generality and in the paper http://arxiv.org/pdf/1304.0053

But what is the difference? We still cannot copy some strings like $1111$ due to lack of overwriting power.

So why it is weak when we cannot write only on input but strong when we cannot overwrite $1$ with $0$ everywhere? Why we can encode strings in one case but not the other?

A non-erasing TM has a tape alphabet $\{0,1\}$ where $0$ acts as blank. The $0$ can be rewritten into $1$, but that symbol cannot be "erased", i.e., written back into $0$.

This restriction seems to be equivalent to symbols that can be rewritten only a finite number of times. TM's do have the capability of interpreting a finite segment of tape as one symbol. Then $0000$ can be rewritten into $0001$ then into $0011$, into $0111$, into $1111$. A little modulo counting interprets these segments as $0,1,0,1,0$.

Recall that a TM is equivalent to a finite state machine that has a queue as basic datastructure. It can read and delete on one side, and write on the other. To see that this is equivalent to a TM a rotation trick is done: the queue holds the tape in a circular fashion, but can only move on the tape in one direction. To move into the other direction just move all the way.

This rotation trick can also be done on the tape of a TM, and needs only finite rewrites on the same position. One needs to be able to rewrite the tape from $Ax$ into say $xB$ where $A,B$ are symbols and $x$ is a string.


Quick union and heuristic by size Studying Quick-Find and Quick-Union heuristic I've found clear that:

with quick find trees and a union based on the size of the trees we can make a union in $T_{am}(n)=O(\log(n))$
with quick find trees and a union based on the height of the trees we can make a find in $T(n)=O(\log(n))$

But I read that using quick union trees and an union based on the size of the trees we can also have a find in $T(n)=O(\log(n))$, so my question is how can this be demonstrated? What relationship is there between height and size?

For example knowing that $\text{size}(A)=4$ I could have both:

        A                A
      / | \              |
     1  2  3             1
                         |
                         2
                         |
                         3

To union-by-size two trees, you have to find their roots first. Since union-by-size takes logarithmic time (your first bullet), then first must take logarithmic time as well.

Here is a more formal argument. Say you want to union-by-size two trees $T_1$ and $T_2$. Assume that their heights are logarithmic in their sizes:

$H(T_1)\le \log(n_1)$ and $H(T_2)\le \log(n_2)$

Where $H$ is the height function and $n_1$ (resp. $n_2$) is the number of nodes in tree $T_1$ (resp. tree $T_2$). There are two cases to consider: either one tree has fewer nodes than the other or both trees have the same number of nodes.

Case # 1

Say $n_1\lt n_2$. The resulting tree $T$ has height $H(T)=\max\{H(T_1)+1, H(T_2)\}$

Depending on the max we have:

$H(T)\le \log(n_1) + 1\le \log(2n_1)\le \log(n_1 + n_2)\le \log(n)$ (because $n_1\lt n_2$)

Or,

$H(T)\le \log(n_2)\le \log(n)$

Case # 2

In this case, $H(T)\le \max\{H(T_1),H(T_2)\}+1$.

Again depending on the max we have:

$H(T)\le \log(n_1)+1\le \log(2n_1)\le \log(n_1+n_2)\le \log(n)$ (because $n_1=n_2$) and likewise for the other one.

For the base case choose $n=1$ because $H(T)=0\le \log(1)=0$


Does PDA epsilon transition only transition when there's no more input? For the Pushdown Automata episilon transition $\epsilon$ which is shorthand for $\epsilon; \epsilon / \epsilon$, does this mean that at any point, regargless of if there is input or not, you can transition to the next state?  Or does it only transition to the next state when there is no more input?

A PDA is always allowed to take $\epsilon$ transitions, just like an NFA. More generally, the PDA is not allowed to peek at anything beyond the current letter. It cannot tell whether it has finished reading the word or not. Whether it can take a transition or not depends only on the contents of the stack and, in the case of a transition "swallowing" an input symbol, on the next symbol in the input (if any).


How to determine how many dots are in a resource in a resource allocation graph? I understand most concepts regard a resource allocation graph but I see that some resources have more dots (not sure what they are actually referred to) in them than others such as the example below, R1 and R3 have one dot, R2 has two dots and R4 has three dots. I cannot find anything online that explains this so I would just like to know, how would you determine how many dots should be in a resource when drawing the graph?

The dots represent the number of clients a resource can serve simultaneously. So, in the example in the question, resources $R_1$ and $R_3$ can only serve one client at a time, $R_2$ can serve two and $R_4$ can serve up to three clients at the same time.


The meaning of modulo in “formula modulo a background theory” I have been reading some papers where I keep reading stuff like “first-order formula modulo a background theory”. Does anyone know what modulo means in this case ? Is it something like “with respect to”?

A theory, in this sense, is an equivalence relation on the formula, which states when these formula are equivalent (as in: $F$ is equivalent to $G$ iff $F$ implies $G$ and $G$ implies $F$). The theory is usually presented by a set of deduction rules, though this is not an obligation.

The word theory is often used in the context of rewriting systems: if you have rules to rewrite terms (which may be formulas, but the concept is more general) of the form $t \rightarrow t'$, then the induced equivalence relation $t_1 (\leftarrow \cup \rightarrow)^* t_2$ (any number of rewriting steps, alternating directions as often as desired) is the equational theory of this rewriting system.

Technically, “first-order formula modulo a theory $T$” means that you are manipulating equivalence classes which are sets of formulas. Intuitively and practically, this is saying that we are manipulating formulas, but we may replace a formula by some other equivalent formula at any time.


Minimum cost closed walk in a graph Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices?

Does this problem have a name? I tried to reduce this to similar problems (in particular the traveling salesman problem) to see if it was NP-hard, but was unsuccessful.

Here's an example:

Then a possible closed walk is: A,B,C,D,C,B,A, with a cost of 6.

Thanks!

This problem is equivalent to TSP. Compute all pairwise shortest distances between the vertices in the given graph $G$. Then take the complete graph $K_n$ that is weighted with the shortest-distances of the original graph $G$. The TSP tour of the complete graph corresponds to the shortest min-cost closed walk.

More precisely, a shortest tour $\pi$ in $K_n$ decodes a closed walk in $G$: just replace every edge $(u,v)$ in $\pi$ by the shortest path from $u$ to $v$. Clearly, the costs are preserved. Assume that there would be a shorter closed walk in $G$. Select select the vertices in order they appear first. This permutation implies a tour in $K_n$ (maybe even shorter than the closed walk in $G$), hence we have a contradiction.

See the figure for your example.


feature selection in decision tree classifier i want to build decision tree classifier, and i have no idea how to extract feature from text (my file is text) can anyone help me? is BOW, N-gram orTF-IDF useful?

This depends on your application but the trend is to use Deep Learning.  That is, allow the algorithm to learn the features as opposed to do feature engineering (e.g. choose between BOW, n-gram etc).

See for example this paper (Gender Classification with Deep Learning by Aric Bartle, Jim Zheng) where they compare the performance of BOW/n-gram/vs Deep Learning via Recurrent Convolutional Networks.   Deep Learning generally outperforms classic feature engineering.

https://cs224d.stanford.edu/reports/BartleAric.pdf


Why do we use stacks and not queues on system-level? From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations.

Why don't we use queues and FIFO operations? It's just a matter of moving pointers anyway.

Because some things need to be done LIFO and some things FIFO.

For example, when a function call returns, it needs to return to the last item on the call stack, i.e., the function that called it. It would make no sense to return to the first item on the call-stack. Conversely, if you're serving requests, the next request you serve is the first one to enter the service queue. (It turns out that, actually, serving queues from the back can be more efficient but that has the obvious disadvantage that it risks starvation for things at the front of the queue and, in real-life queues of people, it just gives people a huge incentive to leave the queue and re-join.)


Amortized analysis of virtual, dynamic array using potential function You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a virtual array $A[0...n-1]$ is simulated by an actual array $B[0...m-1]$ where $m\ge n\ge 1$. Initially, $m=n=1$.

Extend: If $n<m$: increment $n$ and set $B[n-1] = NULL$. Else: set $m=2m$, allocated a new array $B'$ with length $m$, copy $B[0...n-1]$ to $B'[0...n-1]$, deallocate $B$, rename $B' $to $B$, increment $n$, and set $B[n-1] = NULL$.

Show, using a potential function, that the amortized cost of $N$ extend operations is $O(N)$.

The potential function I was thinking of using was $r(s)$ defined as the number of elements in the virtual array $A$ at time $s$. So $r(0) = 0 \le r(s)$ for $s > 0$.

However, when I calculate the potential of the extend operation, I get $r(s+1)-r(s) = n+1-n = 1$ (i.e. the number of elements in the array after the operation minus the number of elements in the array before the operation). Yet, the actual amount of work seems to be much higher in the "else" case $\Rightarrow 2m$ (to allocate new array $B'$) $+n$ (to copy from $B$ to $B'$) $+m$ (to deallocate $B$) $+3$ (to rename, increment, and set to $NULL$).

So the amortized cost (equal to actual cost + potential cost) is clearly not $O(1)$, and so the cost of $N$ extend operations will not be $O(N)$. What am I doing wrong here?

What am I doing wrong here? You're using the wrong potential function. Keep looking. If you want to know the solution, the Wikipedia page on the potential method contains the answer.


Implementing abduction over first order theories I am interested in implementing abduction over a full first order theory ie it may be non-Horn. (Aside: Almost all the references I've seen for abduction operate over Horn theories eg "Modeling Abduction over Acyclic First-Order Logic Horn Theories in Answer Set Programming: Preliminary Experiments". Is there a reason for this other than lack of minimal hypotheses?) Are there frameworks that might be suitably modified for my purposes? Alternatively, does anyone know of a way of coaxing a SMT solver into perhaps giving me something close to what I need?

thanks!

You could use an SMT solver inside a counterexample-guided inductive synthesis loop to learn an expression that fits. The paper below does something similar. If you aren't interested in finding the weakest expression, you could save on computational costs by using templates.

Albarghouthi, Aws, Isil Dillig, and Arie Gurfinkel. "Maximal specification synthesis." ACM SIGPLAN Notices. Vol. 51. No. 1. ACM, 2016.


Meaning of Free (Arbitrary Abstract Algebra Term) I'm currently learning abstract algebra and the word free appears (free monoid, free vector space) throughout different literatures. Is there a general (and simple) definition of the word (and possibly examples in functional programming) or is it merely a highly overloaded word? Many Thanks!

Yes, and in fact there is even a general notion of an algebraic theory, and thus algebraic object. An algebraic theory consists of:

a sort
constants and function symbols
algebraic axioms, that is universally quantified sentences which may contain equality, but no other logical symbols (ie. $\exists,\vee,\to,\neg$)

It is worth noting that the theory of fields is not algebraic, thus there are no free fields.
So the theory of monoids $\mathcal M$ has a sort $M$, constant $e : M$, function symbol $\mu:G\times G\to G$, and axioms

$\forall x.\mu(x,e)=x$
$\forall x.\mu(e,x)=x$
$\forall x,y,z.\mu(\mu(x,y),z)=\mu(x,\mu(y,z))$

In general, given an algebraic theory $T$ we may consider the set of terms in this theory. Categorically, a free algebra for $T$ is the initial object in the category of algebras for $T$. The standard way to construct the free algebra is to take the term model for $T$, that is the underlying set of the free algebra is the set of terms of $T$ modulo the equivalence relation generated by the axioms of $T$.
So what we mean by a free structure in the theory $T$ generated by the set $B$, is to consider a free algebra for the theory $T_B$ containing an additional constant symbol for each element of $B$.
This description is concrete but a bit complicated. There is a much simpler but more abstract construction using the theory of monads, because an algebraic theory corresponds precisely to a monad.

An example for monoids in a functional programming language could look as follows, by interpreting the theory of monoids as a monad:
type 'a mon =
| Id
| Bin of 'a mon * 'a mon
| Var of 'a

let return (x : 'a) : 'a mon = Var x

let rec bind (x : 'a mon) (f : 'a -> 'b mon) : 'b mon =
match x with
| Id -> Id
| Bin (s,t) -> Bin (bind s f, bind t f)
| Var u -> f u

let rec eq (a_eq : 'a -> 'a -> bool) (s : 'a mon) (t : 'a mon) : bool =
match (s,t) with
| (Bin (Id,u), v) | (Bin (u,Id), v) | (u, Bin (Id,v)) | (u, Bin (v,Id)) -> eq u v
| (Bin (Bin (u1,u2),u3), v) -> eq (Bin u1, Bin (u2,u3)) v
| (u, Bin (Bin (v1,v2),v3)) -> eq u (Bin v1, Bin (v2,v3))
| (Id,Id) -> true
| (Bin (u1,v1), Bin (u2,v2)) -> (eq u1 u2) && (eq v1 v2)
| (Var x, Var y) -> a_eq x y
| _ -> false

type two = A | B

let two_eq x y : bool =
match (x,y) with
| (A,A) | (B,B) -> true
| _ -> false

Then the type two mon with relation eq two_eq gives the free monoid on two elements.
The function return : two -> two mon gives us the two generators return A and return B.
The function bind : two mon -> (two -> 'b mon) -> 'b mon tells us that a map from the free monoid on two elements to another (in this case free) monoid is uniquely determined by what the elements of two are mapped to.


Why are the total functions not enumerable? We learned about the concept of enumerations of functions. In practice, they correspond to programming languages.

In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is not enumerable. That would mean that we can not devise a programming language that allows us to write all total functions but no others---which would be nice to have!

So how is it that we (apparently) have to accept the potential for non-termination if we want decent computational power?

Because of diagonalization. If $(f_e: e \in \mathbb{N})$ was a computable enumeration of all total computable functions from $\mathbb{N}$ to $\mathbb{N}$, such that every $f_e$ was total, then $g(i) = f_i(i)+ 1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

Suppose we think of a universal computable function $h(e,i)$, where "universal" means $h$ is a computable binary function and that for every total computable unary function $f(n)$ there is some $e$ such that $f(i) = h(e,i)$ for all $i$. Then there must also be some $e$ such that $g(n) = h(e,n)$ is not a total function, because of the previous paragraph. Otherwise $h$ would give a computable enumeration of total computable unary functions that includes all the total computable unary functions.

Thus the requirement that every function is a system of functions is total is incompatible with the existence of a universal function in that system. For some weak systems, such as the primitive recursive functions, every function is total but there are not universal functions. Stronger systems that have universal functions, such as Turing computability, simply must have partial functions in order to allow the universal function to exist.


Bounds on probe lengths and number of rehashes with universal hashing Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $x\neq y$ are mapped to the same hash-value is bounded by $k/m$ when I have $m$ bins and $k$ is some constant (I am mainly interested in $k=1$ and $k=2$):

$$\Pr_h\left[h(x)=h(y)\right] \leq \frac{k}{m} $$

I have $n$ keys mapped to $m$ bin and I keep a constant bound on the load factor $n/m\leq \alpha$.

With this setup, I am interested in putting a bound on how many collisions I allow in any bin, $K$, and rehashing whenever I have to insert a key in a bin that already holds $K$ elements. For a given bound on the load factor, $\alpha$, and a given bound on the maximum elements in any bin, $K$, I am interested in knowing the probability of picking a hash function that puts less than $K$ elements in each bin.

This is a setup I am interested in for teaching purposes, and I am aware that there are smarter solutions to hash tables, but I would like to handle this setup before moving on to them. In my lecture notes, I have already described rehashing and just want to take this to a probabilistic analysis place, so I want to know the expected number of rehashes needed in this setup.

I would actually also love to know if I could put a bound on the probe length in open addressing hashing and rehash when I reach that, but I guess this is a much harder question.

I guess that if I can fix the probability of hitting any given bin more than $K$ times at a constant $p$, I have a strategy for sampling my way out of the problem, where I expect to rehash $1/p$ times if the number of keys, $n$, and the number of bins, $m$, are fixed. But if I add keys one at a time, resize when $n/m>\alpha$, and rehash when I exceed the bound $K$ in any bin, do I have any guarantee that I will not have to rehash for every new element added after number $K+1$? I mean, my rehash could put $K$ elements in the largest bin and the next key could then trigger a rehash. An advisory, of course, cannot pick the keys so this happens, if I sample random functions, but do I have any probabilistic bounds that guarantee that I can rehash to keep probe-lengths bounded by a constant and still not rehash so often that I break the amortised constant running time on the table operations?

This does not seem like a good example for teaching purposes, as there's no clean analysis or useful conclusions you can draw.

In particular, from only the assumption that you have a weakly universal hash function, you can't draw any useful conclusions about the probability of a having less than K items in the bucket.  That would require some notion of K-wise independence.  Weak universality is a weakened form of 2-wise independence, and if $K>2$, it gives you no information about K-wise independence.  In particular, the hash function could be arbitrarily bad, and the probability could be arbitrarily high.  You need stronger assumptions about the hash function to do any useful analysis.

Instead of assuming weak universality, if you want to get a clean analysis, I suggest you assume that the hash function is (or behaves like) a random function, chosen uniformly at random from the set of all possible functions with that signature.  Then the calculations get easy, since each output of the hash function is uniformly random and independent of all other outputs.


Difference between linear bound automata and a Turing machine Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a Turing machine?

Notice that linear bounded automata are precisely all TM's who use $O(n)$ space.
Now, by the space-hierarchy theorem, for any $f$ where $n=o(f)$ (for an extreme example, $f(n)=2^n$) we would have $DSPACE(O(n))\subsetneq DSPACE(O(f))$.
Thus there are languages who require space complexity bigger than $O(n)$, and therefore are not solveable by linear bounded automata but can be solved by a ($O(f)$ space) turing machine.


Understanding of self-information I am trying to fully understand the meaning behind the self-information of events. While I totally understood how to calculate it, all explanations I find online lack of an explanation why less likely events have more self-information.

I can't figure out what consequences this has and can't put it into perspective like other concepts in computer science.

What does the self-information really mean? Can someone put it into context and why exactly less likely events have a higher self-information?

The self-information is a measure of deviation from expectation of random variable in shannons (bits, the unit may vary when used in different context) when sampling a random variable.

Straight from definition it is reciprocal of probability of occurence for some event, so a little example would help.

Imagine that somewhere it rains only in one month every year (for some random number of days). From the event it is a sunny day we know almost nothing and it could be any month, so it meets the common (the most probable) outcome and we learned almost nothing, so it is not very important piece of information. But the event it rains gives us the exact month, so it is worth more in the sense that we have learned more, hence the higher self-information.

Some people call it a surprisal, which means "not the expected outcome". You need more memory to store rare event, (sorry for circular ref, but it is one of consequences, for the compression) think about the entropy encoding, it takes the most amount of bits to store the least expected events. Huffman codes and self-information.


Undecidability of a restricted version of the acceptance problem It's known that the following language, the so-called acceptance problem is undecidable:

$A_{TM} = \{\langle M,w\rangle\,\vert\,M\text{ is a TM which accepts }w\}$

The proof is by contradiction: Assume there is a TM $H$ which decides $A_{TM}$. Let $D$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D$ simulates $H$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H$ rejects this input and rejects, if $H$ accepts it. That is, $D$ accepts $\langle M\rangle$ if $M$ rejects its own code, and vice versa. Running $D$ on its own code, $\langle D\rangle$, leads to contradiction.

Let's restrict $A_{TM}$ by excluding all input strings which encode a TM:

$E = \{w\,\vert\,w\text{ is a structurally valid encoding of a TM}\}$
 $A'_{TM} = \{\langle M,w\rangle\,\vert\,M\text{ is a TM which accepts }w\text{ and }w\not\in E\}$

I'd like to know whether $A'_{TM}$ is also undecidable.

I tried to prove it the above way: Assume there is a TM $H'$ which decides $A'_{TM}$. Let $D'$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D'$ simulates $H'$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H'$ rejects this input and rejects, if $H'$ accepts it. The problem is that running $D'$ on its own code, $\langle D'\rangle$, doesn't necessarily lead to contradiction. I mean since $\langle D',\langle D'\rangle\rangle$ is not a member of $A'_{TM}$, we don't know what $H'$ will do with it.

Note: An encoding of TMs, and TMs along with an input string

Let $M = (Q, \Sigma, \Gamma, \delta, q_{i}, q_{a}, q_{r})$ be a TM, where

$Q$ is the set of states,
$\Sigma = \{0, 1\}$ is the input alphabet,
$\Gamma$ is the tape alphabet ($\Sigma\subset\Gamma$),
$\delta: (Q-\{q_a, q_r\})\times\Gamma\rightarrow Q\times\Gamma\times\{L,R,S\}$ is the transition function,
$L$, $R$ and $S$ denote the respective head movements, "left", "right" and "stay", and
$q_i$, $q_a$ and $q_r$ are the initial, accepting and rejecting state, respectively.

Let's assign a unique positive integer to each element of $Q$, and do the same in case of $\Sigma$, $\Gamma$ and $\{L,R,S\}$. Now every transition rule $\delta(p, a) = (q, b, m)$ can be encoded as $\langle p\rangle 1\langle a\rangle 1\langle q\rangle 1\langle b\rangle 1 \langle m\rangle$, where $\langle x\rangle$ denotes a sequence of $0$'s, with length being equal to the positive integer assigned to $x$. The encoding of $M$, denoted by $\langle M\rangle$, can be created by concatenating its transition rules, separated by $11$'s. The combined encoding of $M$, and an input string, $w\in\Sigma^*$, denoted by $\langle M,w\rangle$ is $\langle M\rangle111w$.

The complication forbidding the input from being an encoding of a Turing machine is easy to overcome. All you need to do is tweak $D$ a bit, so that instead of accepting an encoding $\langle M \rangle$ of a Turing machine, it accepts some other input which can be decoded into an encoding of a Turing machine, while at the same time not being an encoding of a Turing machine itself.


Passing parameters to threads in Programming language course my professor take an example.

Suppose the following code:

int x=initialization();
Thread T1=new computethread(x);
Thread t2=new evaluatethread(x);
...
...
Thread t100=new evaluatethread(x);

threads t1 to t100 needs the initial value of variable x for their computation and t1 need to change the x, which transfer of parameter for computethread, evaluatethread is preferred?

my professor say:

1) call by value result

2) call by ref

is preferred for sending x to computethread,  evaluatethread, why call by result or call by name or this order like   2) call by value result,     1) call by ref is not preferred?
why he conclude these are better?

Call by reference is cheaper than call by value since you don't need to copy your object. That's why we prefer it when possible. If the thread needs to change its local copy, then you need it to have a copy of its own, which is the same as call by value.


Computing the intersection of N sets over an M-element universe Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$.

1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$?

2.) I am also looking for a good parallel and a good distributed algorithm.

Usual method is you sort all the sets, and select common elements by looking at the beginning of each sorted sequence. This gives you $O(NM)$ algorithm if you do bucket sort. Or in the bucket sort step itself you may check if all the sorted sequence has common elements by doing an operation AND on the bits.

There is even better algorithm that runs in $O(\Sigma_{i=1}^N |S_i| + M$ (i.e. $O(n+M)$) if sets are not multisets (which is the case here). Let $V[1..M]$ be a zero vector. For each $i \in 1..N$, for each $x \in S_i$ do  increment $V[x]$. Select those $x$ for which $V[x] = N$. (Note: For multisets also we can do something similar, but we need to do some housekeeping to ensure that we increment only once for a particular element $x$ in a set $S_i$ even if it occurs multiple times.)

If the elements of each sets are already stored in efficient search data structure they you can do it another way. This also works if you have domain as general values rather than values from $Z_M$. You take the smallest sized set $S_{min}$ and select elements from $S_{min}$ one by one by checking if it belongs to every set $S_i$ in time $O(\log |S_i|)$. This gives you $O(N\cdot
|S_{min}|\cdot \log(|S_{max}|))$-time algorithm, where $S_{max}$ is the largest set, and which might be better than $O(NM)$ if smallest and largest sets are small enough.


Reversing Key Algorithm I have to craft up a number made of 19 digits so that, after some mathematical operations made 11 times, the resulting sum of the remainders of the first ten operations is equal to the the remainder of the eleventh operation. The eleven calculations are as follows. I need to reverse them in order to be able to craft up the x.

op_10 : (x / 256) mod 256 => This is the remainder that must be equal to the sum of the ten remainders below.

op_0 : (x / 72057594037927936) mod 256 => 1st remainder

op_1 : (x / 281474976710656) mod 256 => 2nd remainder

op_2 : (x / 65536) mod 16 => 3rd remainder

op_3 : (x / 1048576) mod 16 => 4th remainder

op_4 : (x / 16777216) mod 16 => 5th remainder

op_5 : (x / 268435456) mod 16 => 6th remainder

op_6 : (x / 4294967296) mod 16 => 7th remainder

op_7 : (x / 68719476736) mod 16 => 8th remainder

op_8 : (x / 1099511627776) mod 16 => 9th remainder

op_9 : (x / 17592186044416) mod 16 => 10th remainder

Is there such an algorithm?
x is the number i need to craft up.

You forgot to mention that $x$ is in fact $64$ bits long. Write $x$ in binary notation:
$$ x_{63} x_{62} \ldots x_1 x_0. $$
We have
$$
\begin{align*}
op_0 &= x_{63} \cdots x_{56} \\
op_1 &= x_{55} \cdots x_{48} \\
op_2 &= x_{19} \cdots x_{16} \\
op_3 &= x_{23} \cdots x_{20} \\
op_4 &= x_{27} \cdots x_{24} \\
op_5 &= x_{31} \cdots x_{28} \\
op_6 &= x_{35} \cdots x_{32} \\
op_7 &= x_{39} \cdots x_{36} \\
op_8 &= x_{43} \cdots x_{40} \\
op_9 &= x_{47} \cdots x_{44} \\
op_{10} &= x_{15} \cdots x_8
\end{align*}
$$
All these, in binary notation.

I'll let you take it from here.


black-box function optimization with binary vector input: terminology and NP-hardness proof I have a black-box function optimization problem:
$$\arg\max_{\vec{x}} \; f(\vec{x}, \vec{y}) \\\text{subject to } \vec{x} \in \mathbb{Z}_2^N, \|\vec{x}\|_1=K, K<N, \vec{y} \in \mathbb{Z}_2^M$$

The function $f(\cdot)$ is a black-box function whose output I can only simulate: I cannot access its exact form. The variables $\vec{x}$ and $\vec{y}$ are two binary vectors as the inputs of $f(\cdot)$. Given $\vec{y}$, I am seeking the optimal $\vec{x}$ that maximizes $f(\vec{x},\vec{y})$.

My questions:

Is there similar research having the same form as my problem? What is the terminology for such problems?
The brute force method to do the optimization is to exhaust all $\binom{N}{K}$ possible $\vec{x}$. Is this problem NP-hard? How can we prove this problem is an NP-hard problem?
In practice there should be some heuristics and techniques to be used to speed up the search and return an approximate optimal solution. Can someone point me out the names of possibly feasible techniques?

NP-hardness is a property of languages, that is, of subsets of $\Sigma^*$ for some finite alphabet $\Sigma$. Your problem is not of this form, since you also need to give the algorithm access to the function $f$. Such problems are known as "optimization with a value oracle" (and several other similar names) — the value oracle in your case is the function $f$.

To show that such a problem is hard, we typically given an information-theoretic lower bounds on the number of value oracle calls of any valid algorithm. This captures much, but not all, of the difficulty of solving the problem (it ignores the computational complexity of deciding which questions to ask the oracle). In your case, it is easy to show that any valid algorithm must query the oracle at all possible inputs, using an adversary argument. This makes your problem not so interesting.

In practice, problems tend to have more structure. For example, if you know that for each $\vec{y}$, the function $\vec{x} \mapsto f(\vec{x},\vec{y})$ is submodular, then you can use approximation algorithms for (non-monotone) submodular maximization. In some cases, for example maximizing supermodular functions, there are efficient algorithms that find an optimal solution. In other cases, for example maximizing submodular functions, finding even an $\alpha$-approximate maximum can be hard (requiring exponentially many value oracle queries) if $\alpha$ is too close to 1, but at some point the problem becomes easy again (can be solved in polynomial time).

Any heuristics to your problem will have to rely on some properties of your function. So your first task is to learn more about the structure of your function. In some cases, such as cryptography, there is nothing more to learn, and then there is no real way to speed up the search. But in most optimization contexts you are able to say more about your function, at least roughly, and this informs the algorithms and heuristics that you subsequently use.


What is the exact algorithm to find maximum clique of a given unit disk graph? A unit disk graph is an intersection graph $G = (V,E)$, such that given $n$ disks on the plane with identical radius. Each disk $d_u$ corresponds to a vertex $u \in V$, and there is an edge $uv \in E$ if, and only if $d_u$ and $d_v$ intersects.

In 1990, Clark, Colbourn, and Johnson showed that the problem can be solved in polynomial time. However, the linked paper does not provide an exact algorithm.

I have been studying the paper for some time, and I still don't see how the observations in Section 3 can be utilized to develop an algorithm. Mostly because point sets that are used to prove the claims are infinite.

Moreover, I have scanned through many papers, and all of them mention the polynomial-time solvability only. I could not even find a verbal definition of the algorithm anywhere.

I am not asking for coding or some well-defined algorithm, but I would really appreciate a roughly written complete algorithm.

First note that the algorithm is expressed in the so-called proximity model (see preliminaries), so in what follows the points considered will be the centers of your circles, and $d$ will be their common diameter.

It may be confusing, as the circles drawn in the observations are not directly related to the circles from the intersection model (the radius is $d(a,b)$).

With the notations of the article, $H_{A,B}$ is finite because $V$ itself is finite ($H_{A,B}$ is a subset of the $n$ input points).

Input: d, G = (V, E) with V set of points in the plane, and E is the set
       of {u, v} s.t. d(u, v) <= d
best clique = empty
for all pair of points (u, v) from V:
    let V' = set of vertices w of V s.t. d(u, w) <= d and d(v, w) <= d
    let E' = set of {x, y} s.t. x and y are in V' and d(x, y) > d
    // G' = (V', E') is bipartite
    candidate clique = MaxIndependentSet(G')
    best clique = max(best clique, candidate clique)
return best clique

If you want to use Hopcroft-Karp, you may need to have an explicit partition $V'=A\cup B$ s.t. all edges of $E'$ are connecting a vertex of $A$ and a vertex of $B$. This can be done by checking the sign of the cross product $(\textbf{w}-\textbf{u})\times(\textbf{v}-\textbf{u})$.


How can I represent a set of graphs for learning purposes? I have a network of labelled digraphs and a I need to perform a unsupervised learning algorithm on this data.

I am interested in embedding a network of description logic documents in a vector space using the ideas in the paper Co-embedding Attributed Networks (which is a variational auto-encoder). look at the picture:

The first step is to represent each digraph as a feature vector in a vector space.

I have googled a lot but I haven't found good explanations (I also search for supervised algorithms like support vector machine working on a set of labelled digraphs but google doesn't retrieve good results).

My question is: How can I represent a set of labelled digraphs into a vector for learning purposes? (this representation algorithm must have linear complexity)

I don't think that paper is suitable for what you want to do.  That paper generates an embedding of nodes: given a graph $G$ and a node $v$ in $G$, it outputs an embedding of $v$ (a representation of some properties of $v$).  You want an embedding of the entire graph: given a graph $G$, you want to compute an embedding of $G$ (a representation of the entire graph $G$).

So, I suspect you'll need to consider a different approach.  A usual starting point would be to do exactly what @Juho recommended: brainstorm some features that might be relevant (e.g., number of nodes, average degree), then map the graph to a feature vector (a list of the values of these features), and use the feature vector as your representation of the graph.  More sophisticated methods are possible as well, but I'd recommend you start with the simple approach before diving into more complex methods, especially if you are not very experienced in this field.


What is the name of this quantum gate? As I was watching a video about single qubit quantum gates, I came across the following gate:
$$\begin{bmatrix}e^{i\sigma}&0\\0&e^{i\theta}\end{bmatrix}$$ The video didn't mention the name of the gate. It gave only the matrix and the following information:

$|0\rangle \rightarrow e^{i\sigma}|0\rangle$
$|1\rangle \rightarrow e^{i\theta}|1\rangle$
$\alpha |0\rangle + \beta|1\rangle \rightarrow \alpha e^{i\sigma}|0\rangle + \beta e^{i\theta}|1\rangle$

In the comments below the video, someone asked what $\sigma$ and $\theta$ could be, and the reply was all real numbers, but this was from someone other than the video maker, so I don't know if this is true.

What is the name of this gate?

This is a phase shift gate.

Notice that

$$\begin{bmatrix}e^{i\sigma}&0\\0&e^{i\theta}\end{bmatrix}=
e^{i\sigma}\begin{bmatrix}1&0\\0&e^{i(\theta-\sigma)}\end{bmatrix}
$$

Multiplying the state by a constant (with unit norm) will not affect your measurements.


Definition(s)/characterization(s) of intractability I've been searching around for definitions of intractability, and I realized that despite being widely used, the concept of intractability (when talking about computing problems of course) is not formally defined.

I'm currently writing a report in which I characterize some problems as intractable (in my context, they are intractable because their output size can be exponential w.r.t the input size), and I need to feel 'comfortable' about what intractability is in order to write coherent stuff in the report.

The way I understood it is the following: a problem is intractable if it cannot be solved reasonably fast, with reasonably big instances.

This leaves a lot of space for human appreciation of what a reasonable execution time is, and what a reasonable input size is. This also allows to describe some problems in P as intractable (if it runs in O(n^150) for instance) , and even in some cases, to eventually describe some NP-complete problems as tractable (many MILP problems can actually be solved fast with reasonably big instances).

My questions:

Is there a better/more elegant/more precise way to define intractability ?
Are there problems/contexts which could be described as being on the border, meaning that they're really not easily fitting in any of the 2 categories (tractable/intractable) ?

What is intractable or not inherently depends on what the underlying computational model is as well as what your conventions are. By far, the most widely used notion is based on the Cobham-Edmonds thesis, which states that, for any given machine model for which time (or any equivalent thereof) is a valid resource, the tractable problems are those that can be solved in polynomial time. In this sense, tractability quite certainly has a formal definition.

This means that, if you are using run-of-the-mill TMs, then the class of tractable problems is $\mathbf{P}$. If you use probabilistic TMs (with two-sided error), it would then be $\mathbf{BPP}$. If you use quantum circuits, $\mathbf{QBP}$. For ATMs, $\mathbf{PSPACE}$—and so on.

  Are there problems/contexts which could be described as being on the border, meaning that they're really not easily fitting in any of the 2 categories (tractable/intractable) ?

The way tractability is usually understood, this is impossible. There is a well-defined set of tractable problems. Using standard logic, a problem is either in that set or it isn't. You could identify some problems as more difficult than others, but that is a different concept altogether since it would produce a whole spectrum of hardness (and, hence, is not quite captured by the aforementioned notion of tractability). What would rather fit that notion is time complexity itself; after all, it allows you to express a problem's hardness based on the time resources (as a function on $\mathbb{R}_0$) needed to solve it. (And, as we know, most such functions can be compared using, for instance, asymptotic analysis.)

TL;DR: Intractability is a discrete concept; time complexity is a continuous one (or as continuous as it can be in the set of (computable) $\mathbb{N} \to \mathbb{R}_0$ functions).


Can we convert any given turing machine to a turing machine with only 2 states? if so, how? So i remember reading somewhere that we can convert any turing machine into a turing machine with 2 states (or 3, i don't remember) but there was no proof for it and i couldn't find it either

So my question is :

For every turing machine, what is the minimum number of states that we can have after converting it to this minimal state turing machine?

and what is the properties of this turing machine that we have converted our original turing machine to?is this a standard turing machine or we do this by increasing the number of tapes or...? ( how is this possible?)

What i mean by convert is build a Turing machine which accepts the same language but only with 2 or 3 states

You can't always find an equivalent Turing machine (in the sense that it has the same language) having less than $N$ states.

Note that the semantics of a Turing machine is determined by its states and transition function. After fixing the alphabet, to fully describe a machine you only need to specify how it reacts to every symbol from every state. This description has length of $O(|Q|\log |Q|)$. Thus, if you bound the number of states by some constant $N$, then there's only a finite number of different machines ($\sim N^N)$, which means that not every decidable language has an equivalent machine in this set.


An approach to determine whether language is regular or not? I have the following problem. I need to determine whether this language is regular or not:

$L:= \{ w \in \Sigma^*: \forall \alpha ∈ \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$

$|w|_\alpha$ => $|w|$ is the length of the word $w$ and $|w|_\alpha$ is the number of $\alpha$ characters in that word.

For example: $w$ = 100111 => $|w|$=6, $|w|_0$ = 2, $|w|_1$ = 4.

I know that I need to use deterministic/non-deterministic finite automata, regular expression/grammar to prove that it is regular or to use pumping lemma to prove that it is not.

But I'm not sure how to approach this problem to start proving something. Is this trial and error method or is there some way to know from the start?

I appreciate your help!

I'm not aware of any completely "algorithmic" method to decide whether a language is regular.

For the specific language you are interested in, you can start by observing that it can be written as combination of unions and intersections of a finite number of regular languages:
$$
\bigcap_{\alpha \in \Sigma} \left( L_{2,\alpha} \cup L_{3,\alpha} \right),
$$
where:

$L_{2,\alpha}$ is the language containing all words $w$ such that $|w|_\alpha$ is divisible by 2.
$L_{3,\alpha}$ is the language containing all words $w$ such that $|w|_\alpha$ is divisible by 3.

It is easy to show that all these languages are regular (since, in each language, $\alpha$ is now fixed). A DFA for $L_{2,\alpha}$ has two states $q_0, q_1$ where $q_i$ means that the number of characters equal to $\alpha$ encountered so far is $i$ modulo 2. A DFS for $L_{3,\alpha}$ is similar but has $3$ states.

The regularity of $L$ follows from the fact that regular languages are closed under union and intersection.


Is it possible to use plants as a medium to store data? By what data structure? my question is simple.
Is it possible to use plants as a medium to store data?

My opinion is: Possible, but we need to solve, how to distinguish 2 states.
Duplication and CRC of stored DATA is quiet simple. Growing new plants is easiest possibility, but we need to create unit, which will take care about raid and duplicating informations between all plants.

Could there be a different data-structure? What is a potential of storing data into plants? What about security? How would you write data into plants without losing that information?

No, this is not a joke. Think about it. It grows everywhere, it is protected against water, cold, wet, dry, magnetic field, shaking and so on.

Try to remember, you can use your own garden as a datastore for your music, films and data. Or just use public garden to share media, photographs, messages or opinions by connecting remotely to plants.

What you propose sounds like it would be quite error laden, as plants are not necessarily independent, and those grown in the same area of the same species might share a common root system, so what you might consider redundancy is not a guarantee that your data will be preserved.  I would also venture to say that it's rare for a plant to be hardy against cold weather, and especially against something like an herbicide.

What you might consider is the concept of biocomputing and, more specifically, DNA computing, which uses the ordering of the base pairs to store and manipulate information.  The field is still in its infancy, but Turing machine-like behavior has been achieved, and in some cases basic algorithms can be implemented (e.g., the Hamiltonian path problem as cited in the Wikipedia article).


Sensitivity analysis of $MST$ edges I am working on the following exercise:

Consider an undirected graph $G = (V,E)$. Let $T^* = (V,E_{T^*})$ be a $MST$ and let $e$ be an edge in $E_{T^*}$. We define the set of all values that can be assigned to $w_e$ such that $T^*$ remains a MST as $I_e$.

Show that $I_e$ is an interval.
Devise an efficient algorithm to calculate $I_e$ for a given edge $e$.
Devise an efficient algorithm that determines all $I_e$ in one step. It should be more efficient than repeatedly using the algorithm from 2.

I did the following:

Consider an edge $e$ in $E_{T^*}$. Delete it from $G$ and find the new lowest weighted edge connecting the resulting components, say $e'$. The upper bound for $I_e$ is $w(e')$. The lower bound would be $-\infty$.
Use the algorithm sketched in 1.
I do not know what to do here. Could you help me?

The solution in short. For each edge $e$ not in the tree, check the path between its endpoints in the tree. The weight of each edge on this path is upper-bounded buy the weight of $e$. Keep track of the smallest upper-bound for each edge on the tree while iterating over all edges not in the tree. Following is a sketch of the correctness.

Let us call an edge in a simple cycle Heavy for this cycle, if its weight is maximum among all edges in the cycle. We claim that each edge $e$ in $G\setminus T^*$ is Cycle heavy for some cycle in $G$.

Proof. By adding the edge $e$ to the tree, it constructs a cycle with a path in the tree between its endpoints. If there is an edge in the cycle with strictly heavier weight, we can remove this edge and keep $e$ constricting a lighter tree which contradicts the assumption that the given tree is minimum.

On the other hand, it is not hard to prove that an edge is in an MST of a given graph if it is not heavy for any simple cycle containing this edge. The correctness of the sketched algorithm follows directly from this statement.


Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$ I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states.

However recently came across following text:

  If $n$ is power of $2$
  Let $n=2^m$, so number of minimum states $=m+1$.
  For $n=8=2^3$, we need $3+1=4$ states.
  Else If $n$ is odd
  Number of states $=n$.
  For $n=5$, we need $5$ states.
  Else if $n$ is even
  Keep dividing it with $2$ until you get odd quotient. The result is final odd quotient plus number of divisions done.
  For $n=20,20/2=10,10/2=5→5+2=7$ states

I was guessing:
Q1. From where all these facts came. (I know this must have come from general pattern that such DFAs follow, but then I have below doubts)
Q2. Are these points indeed correct?
Q3. If yes (for Q2), then what can be the reason for each point?
Q4. Do these three bullet points cover all cases? (I guess yes, since there is even and odd, but I am new to this, and I was guessing if any such more point is left unmentioned in my textbook, especially since I did not find any reference book (by Peter Linz and Hopcroft-Ullman) talking about this topic)

Case 1: $n$ is a power of 2

If you wanted to check whether a decimal number is divisible by some power of 10,  you can just look at the number of trailing zeros. For example, all numbers that are divisible by $100 = 10^2$ end with 2 zeros (this is of course including numbers ending with more than 2 zeros). The same idea can be applied here for binary numbers and powers of 2. Specifically to check for multiples of $n = 2^m$, you can simply check if the string ends in $m$ zeros. For example, if $n = 16 = 2^4$, all multiples of $n$ will end in 0000 (4 zeros). Thus we can create the following DFA for $n = 16$:

This construction can be extended to all multiples of 2, where you have $m+1$ states to ensure that your input ends in at least $m$ zeros (reading a 0 takes you one state forward, reading a 1 takes you back to the start). As suggested in the comments on your question, you can show that you can't do any better than this using a Myhill–Nerode argument.

Case 2: $n$ is odd

The general idea here is that when a number is divided by $n$, the possible remainders are $0, 1, \ldots, n-2$ or $n-1$. We can give our DFA one state for each of these possible remainders so as we process a string, we're keeping track of the remainder of what we've read so far and transitioning to the appropriate remainder based on what character we read. Then, we accept if we finish in the remainder 0 state.

Design DFA accepting binary strings divisible by a number 'n' walks through a detailed method for constructing such a DFA, and you can find out more about this by searching for "DFA based division". This gives a total of $n$ states, which is optimal by Myhill-Nerode because these remainders are exactly the equivalence classes given by the relation $\equiv_L$ for the language $L = \{\text{binary strings divisible by }n\}$.

Case 3: $n$ is even (and not a power of 2)

The technique in case 2 also works here but it isn't optimal. Every $n$ in this case can be expressed as $2^km$ where $m$ is odd (this is the division procedure described in your question). Thus, to check whether a binary string is divisible by $n$, we check whether it is divisible by both $2^k$ and $m$.

We know that it takes $k$ states to check divisibility by $2^k$ (case 1) and $m+1$ states to check divisibility by $m$ (case 2). We can take a DFA for divisibility by $m$, unmark the accepting state and make it the start state for a DFA for divisibility by $2^k$, giving our final DFA $k+m$ states.

As an example, here's the DFA for $n = 6$:

The top three states ensure that the number is a multiple of 3, and the final accept state ensures that it is a multiple of 2.


Online and parallizeable set intersection algorithm I have problem that is reducible to the following:

From a collection of stacks, find all items whose "keys" are on all stacks.

My current solution to this problem is to just pop things off as quickly as possible store the items in the language's set type, compute the intersection every once in a while (the stacks are refilling constantly), and use that set, repeat.

The issue here is that the equivalent of the pop operation is expensive (I can do this at most 4k times a second), and it kills the chance of multithreading (as pops are destructive).

Is there a way of doing this such that I can multithread the intersection bit? I cannot practically use shared memory or requeuing items. The threads can communicate with each other via pipes/sockets if need be, but such communication should be kept to a minimum (not really interesting in starting up some whole separate client/server thing just for this part of my application)

As an idea of what I am dealing with, there can be up to 15 million items on the queues at any one time. By the time its "over" all items will have a match.

Ideas?

Clarification: These are message stacks (well queues really but the same thing) over the network. A pop is a consume operation over network, and push is a publish. Thats why its so slow. Since the issues is one of latency rather than bandwidth, multithreading can potentially help. I am not CPU bound. I have ~10 stacks, and up to 10 million items at a time. I have no control over the implementation of the stacks.

Apparently this is a distributed systems problem.  You have ~ 10 stacks, each with up to 10 million items at a time, and each stack living on a different machine.

Here is one simple candidate solution.  Have a separate "monitor" machine, whose sole purpose is to continually compute the intersection.  Any time one of the stacks is modified, the machine storing that stack should send a message to the monitor message describing the change.  (These diffs can be batched, depending upon your latency requirements.)

Now you have all the data on a single machine, the monitor machine.  When running on a single machine, you can completely avoid all of the concurrency issues associated with multithreading or distributed systems -- e.g., the need for synchronization, locks, etc.

Moreover, the amount of data is small enough that it could easily be stored in the available RAM on that monitor machine.  (Why?  If each entry is large, hash it first using a good hash function and a large enough hash output that you won't see collisions.  If each hash value is 128 bits, then storing all 100 million hashed items takes 1.6GB.  If you use SHA256 truncated to 128 bits as your hash function, by the birthday paradox, the chances of encountering a hash collision are incredibly small.)

Once all of the data is living in RAM on a single machine, the problem becomes much easier.  For example, one approach would be to build an index data structure: a hashmap that maps each key to a 10-bit bitmap that indicates which of the stacks it is stored on.  You can easily update this hashmap as the individual stacks change.

You can also easily use this hashmap to compute the intersection: just have a doubly linked list threaded through the entries of this hashmap where the bitmap is equal to 11111111111 (all 1's).  Any time a bitmap changes from 11111111111 to something else, you remove it from the doubly linked list.  Any time a bitmap changes from something else to 11111111111, you insert it into the doubly linked list.

The amount of data you need to transfer from other machines to the monitor machine is very small, especially since you only need to send the hashed items to the monitor, not the original items.  If each of the 10 machines will do at most 4k push/pop's per second (taken from your question), then that's 64 KB of hashed data per second per machine.  If we add another 32 bytes or so of overhead (packet headers), that's about 200 KB/s of data out of each machine, or about 2 MB/s of data into the monitor machine -- a very manageable amount.  On a 1 Gbps Ethernet link you won't notice this, and you might not notice it even on a 100 Mbps link.  You can reduce the amount of traffic by a factor of 2-5x by batching such messages and/or by using a shorter hash.

This should provide an efficient algorithm to compute the intersection, and keep it updated on the fly as each of the stacks change.


How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case? The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows:

  Prove that merging two sorted arrays of N items requires at least 2 * N - 1 comparisons. You must show that if two elements in the merged lists are consecutive and from different lists, then they must be compared

If we are trying to find the lower bound then wouldn't the number of comparisons be N, not 2 * N - 1? If the largest element is some array Ais smaller than the smallest element in some array B then at most you would only have to do N comparisons since after all of A's elements are placed in the merged array then the remaining elements in B's can simply be appended in to the merged array.

The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2 * N - 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

Note: I am not asking for an answer to the HW question itself as I know that is deprecated. I am confused about the implied assertion the question is making about the lower bound

What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound.

  The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2*N* - 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

No, it just needs to be true for some input (for infinitely many N).

For example, when we say that $\Omega(n \log n)$ is a lower bound for sorting, this does not mean that every array requires $\Omega(n\log n)$ comparisons. It just means that some arrays require that many comparisons, and thus there is no $o(n\log n)$-time algorithm for sorting.


What do CPUs do when a program aborts with an error? If a very severe interrupt occurs, say a divide by zero, this will quit the program. How is this done, is there a special instruction in the processor or is it a software routine? And after quitting the program, where will the CPU jump to?

CPUs don't have a notion of “program aborting”. Some CPUs have features that help operating system manage separate programs, but the concept of separate programs exists primarily at the level of the operating system.

The specification of the CPU specifies what happens for each instruction for all data. For example, it might specify that div r1, r2, r3 divides the integer value stored in r2 by the integer value stored in r3, stores the result into r1, and then moves the instruction pointer to the next instruction. It might furthermore specify that in case r2 is zero, the CPU executes a trap — this is what most CPUs do on a division by zero. Typically, on a trap:

The CPU saves the current value of the program counter into a register assigned to this purpose.
The CPU sets the reason for the trap (a constant that means “division by zero”) into a register assigned to this purpose.
The CPU reads an address from somewhere and sets the program counter to this address. This address is called the trap vector. This “somewhere” is usually either a register, or a memory location which is calculated from a value in a register.
The CPU switches to a privileged mode (e.g. kernel mode, ring 0).

(Note that details vary from CPU to CPU, I am only describing typical behavior.) Traps are very similar to interrupts; the difference is that a trap is due to an event happening in the CPU whereas interrupts are triggered by external events.

The operating system decides what happens when a trap occurs by providing some code and setting the trap vector to its address. The trap handling code typically analyses the reason for the trap and decides what to do, which may or may not include terminating the current process. For example, some operating systems allow application code to react to trap (e.g. with signal handlers on Unix) — then the kernel's trap handler looks up the address of the application trap handler in some internal kernel data structure and jumps to that after setting the processor in the appropriate mode.

An example of a trap which often doesn't result in the death of the application is a memory fault, when the application tries to access a virtual address which is not mapped in the MMU. On operating systems that implement swap, the trap handler looks up the virtual address to see if there is actually data that is mapped there in the application but that is currently swapped out to disk. If that is the case, the trap handler loads the content of the page from disk and updates its memory management data structures. Then it jumps back to the application, arranging to cause the application to execute the memory access instruction again. This time the instruction will succeed, and the application is unaware that the first attempt fails (except via some indirect means such as timing).

If the trap handler decides to terminate the program, it does so in pretty much the same way as if the program had called the exit system call: it frees the resources allocated to the process, then invokes the scheduler to execute whatever other threads have something to do.


Mapping graph to another graph's sub-graph How to solve the induced sub-graph isomorphism problem?

This is the induced subgraph isomorphism problem, which was one of the problems proven NP-complete in Cook's original paper on NP-completeness.  For a quick way to see that it's NP-complete, you can let $G$ be a complete graph on $k$ vertices to solve CLIQUE on $G'$. Unless you can restrict the form of $G$ and/or $G'$, you're probably out of luck in your quest for a good algorithm.

The problem seems to be easier if you insist that $G$ and $G'$ have the same number of vertices. In this case, you have the graph isomorphism problem. This is generally thought not to be NP-complete and, in December 2015, Babai announced an subexponential-time algorithm, which runs in time $\exp\exp(\tilde{O}(\sqrt{\log n}))$, where $\tilde{O}$ denotes hidden factors of $O(\log\log n)$.
This is faster than $O(\mathrm{e}^{n^\epsilon})$ for all $\epsilon>0$. (The algorithm was originally announced as having quasipolynomial running time but an error in the analysis came to light in January 2017.)


Regular expression for odd binary numbers without leading zeros I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0\cup1)^*1$, but that doesn't match just 1. The best it matches is 11.

First you might just add that single $1$ to your expression as an alternative to what you already have. One obtains $1 \cup 1(0\cup 1)^*1$.

An alternative is $1(0^*1)^*$. That one is shorter, but not necessarily better.

Actually that expression I obtained by starting with the FSA below, and realizing that the rightmost two states could be replaced by iterating $0^*1$.


What is the relation between a web server and a local file serve in distributed systems? I am learning distributed systems ( although I am an Electrical engineer ) using the book distributed systems concepts and design. The author says that "A web server is often a client of a local file server that manages the files in which the web pages are stored." I cant understand in the first place what is the relation between a web server and a local file server. So please someone explain this statement using a simple example. Thank you very much.

Often the content is stored on a local filesystem (or file server); the web server accesses the content by reading it from the local filesystem (or file server), then provides it to the web client on demand.  So the web server is making use of a local file server -- in that sense the web server is a client of the local file server.


Dynamic Shortest Path with Linear Programming Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps.

There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is denoted as $A_{xt}$. For this example, consider $A_{00}=1$ and $A_{10}=23$. The goal is to carry a ball from node $1$ to node $G=15$. Each agent can carry the ball or throw it at distance $k=2$ (measured in Manhattan distance). The shortest path is, in this case, for Agent $0$ to carry the ball until node $3$, while Agent $1$ moves to node $13$. Then, Agent $0$ throws the ball to Agent $1$, which kicks it to the goal node.

How can this be modeled? If agents cannot move without the ball (not a dynamic graph), the problem is fairly simple. Assume $X_{ijt}=1$ (an activated edge) when the ball is carried or is kicked from node $i$ to $j$ at timestep $t$, and all actions cost (or have weight) $1$. All nodes (except starting and goal nodes) must have the same amount of ball 'entrances' as 'exits'.

$ \sum X_{ijt_1} = \sum X_{jit_2}, \forall i,j,t_1,t_2$, where $t_1<t_2, d(i,j)=1$ (adjacent nodes) or $j=A_{xt}$ (passing towards an agent)

The entrance and exit nodes will have a single activated edge.

$ \sum X_{A_{00}j0} + \sum X_{A_{00}A_{x0}0} = 1, \forall j,x$, where $x\neq0, d(A_{00},j)=1, d(A_{00},A_{X0})\leq k$

$ \sum X_{iGT} = 1, \forall i$, where $d(i,G)\leq k$

However, if all agents can move at any given point, then the graph is dynamic, since the passes that can be performed are different in each timestep. I don't know how to model this. Before, because $A_{1t}$ was static until it got the ball, I could list all the restrictions a priori, but now, I cannot do it. I can create a set of restrictions based on $A_{xt} \forall x,t$, but I don't know how to then input this problem into a linear programming solver (for example, a simplex method).

Our matrix is modelled as a graph $G = (V,E)$ with directed edges $E$ between cells $V$. We denote $V_{kl}$ as the set of nodes $j$ that respect $d_{jl} \leq k$. The edges $E$ exist between all nodes $j \in V_{kl}$ and node $l$, for any $l \in V$. Activated edges represent movements (such as players moving with the ball to an adjacent cell or passing the ball to a faraway agent). All player actions (moving, kicking or passing) take exactly $1$ action, therefore the weight of all edges in our graph is always $1$. Throughout this paper, unless specified otherwise, we use $i \in [1, p]$ to identify an agent, $t \in [0, T]$ to identify different timesteps and $l,j \in V$ to identify nodes. We must define the position and movements of each agent $i$, as well as the position and movements of the ball, all across $t$. Assuming $l_1 \in V_{1l}$ and $l_k \in V_{kl}$, then

\begin{equation}
  \begin{split}
    A_{ijt} = &
    \begin{cases}
      1     ,& \textrm{if Agent $i$ is on cell $j$ at timestep $t$}    \\
      0     ,& \textrm{otherwise}
    \end{cases} \\
    Y_{ill_1t} = &
    \begin{cases}
      1     ,& \textrm{if Agent $i$ moved from cell $l$ at timestep $t$ to cell $l_1$ at timestep $t+1$}    \\
      0     ,& \textrm{otherwise}
    \end{cases} \\
    B_{jt} = &
    \begin{cases}
      1     ,& \textrm{if Ball is on cell $j$ at timestep $t$}    \\
      0     ,& \textrm{otherwise}
    \end{cases} \\
    X_{ll_kt} = &
    \begin{cases}
      1     ,& \textrm{if Ball moved from cell $l$ at timestep $t$ to cell $l_k$ at timestep $t+1$}    \\
      0     ,& \textrm{otherwise}
    \end{cases}
  \end{split}
\end{equation}

These definitions inherently model the behaviour of our agents and ball, by limiting agents to only move $1$ unit of distance at most, and the ball to move $k$ units of distance at most. Both $B_{j0}$ and $A_{ij0}$ are defined for all $j,i$. We must now model the relation between $A$ and $Y$, as well as between $B$ and $X$. In fact, $A_{i,l,t+1}$ (representing agent $i$ being on cell $l$ at timestep $t+1$) must be the sum of $A_{i,l,t}$ (agent $i$ may have been in that cell in the previous timestep and remained stationary) with $\sum_j Y_{ijlt} - \sum_j Y_{iljt}$ (agent $i$'s movements entering or leaving that cell). If the agent remains stationary, the latter part of the sum is equal to $0$. Analogously, a similar relation exists between $B$ and $X$. Formally, for all $i$, $l$, $t$,

\begin{equation}
    \begin{split}
        A_{i,l,t+1} & = A_{i,l,t} + \sum_{j \in V_{1l}} Y_{ijlt} - \sum_{j \in V_{1l}} Y_{iljt},             \\ % player positions are related to their movements
          B_{l,t+1} & = B_{l,t} + \sum_{j \in V_{kl}} X_{jlt} - \sum_{j \in V_{kl}} X_{ljt}.                 \\ % ball positions are related to its movements
    \end{split}
\end{equation}

Our optimization function now differs in the fact that $t$ must be taken into account. This is necessary due to the fact that the ball may remain in the same place for several turns, which counts as movement to the same cell. In other words, reaching the goal $G$ on the second timestep $t$ and waiting there for $50$ turns is equivalent to waiting $50$ turns and then entering the goal. Therefore, our objective functions is now

\begin{equation}
Z = \sum_{t,l \in V_{kG} \setminus G} ( t * X_{lGt} ) .
\end{equation}

We must update the previously described constraints so that the ball enters the goal $G$ only once at any timestep $t$ and leaves the source $S$ at timestep $0$. Our modeling of $B$ dependent on $X$ will ensure that the ball will move among the cells from $S$ to $G$.

\begin{equation}
    \begin{split}
        \sum_{l \in V_{kS}} X_{Sl0} & = 1,                \\ % ball leaves Source once
        \sum_{j \in V_{kG} \setminus G,t} X_{jGt} & = 1,  \\ % ball enters Goal once
    \end{split}
\end{equation}

Finally, we must guarantee that the agents do not overlap and that they carry the ball, kick it to the goal $G$, or pass it at each other. In other words, the amount of agents at node $j$ cannot exceed $1$ and the ball must either be at one of the agent's positions or at the goal $G$. Formally, for all $j$, $t$,

\begin{equation}
    \begin{split}
        \sum_{i} A_{ijt} \leq & 1,                              \\ % only 1 agent per cell
        B_{jt} \leq & \sum_i A_{ijt} + B_{Gt}.                  \\ % ball can only exist at Goal or where there are agents
    \end{split}
\end{equation}


How to prove a L=L(G) without knowing the L? How does one prove L(G)=L if the language is not given and only the grammar G is given?  If there is no pattern to be seen in the grammar that would create the strings w of a language L, how would you go about doing this?

In cases like this, where you have a grammar and want to guess what the language is, a good way is to approach the problem systematically, by trying to derive some short strings. For example, if you had a grammar $G$ like this,
$$\begin{align}
S &\rightarrow SA \tag{1}\\
S &\rightarrow \epsilon \tag{2}\\
A &\rightarrow aS \tag{3}\\
A &\rightarrow bA \tag{4}\\
A &\rightarrow \epsilon \tag{5}
\end{align}$$
then here are a few derivations, where the relevant production is labeled:
$$\begin{align}
\epsilon&: S \stackrel{2}{\Longrightarrow}\epsilon\\
a&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}aS\stackrel{1}{\Longrightarrow}a\\
b&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}bA\stackrel{4}{\Longrightarrow}b\\
aa&: S \stackrel{1}{\Longrightarrow} SA\stackrel{1}{\Longrightarrow}SAA\stackrel{2}{\Longrightarrow}AA\stackrel{3}{\Longrightarrow}aSA\stackrel{1}{\Longrightarrow}aA\stackrel{3}{\Longrightarrow}aaS\stackrel{2}{\Longrightarrow}aa\\
\end{align}$$
If you try this for, say $ab,ba,bb$, you'll find that they're all in $L$ which prompts a guess that this grammar generates all strings over the alphabet $\{a,b\}$. This isn't too hard to show, by induction on the length of a string in the language.

The proof goes like this:

Base. Show that the length-0 string, $\epsilon\in L(G)$. (We've done this already.)

Induction. Let $w$ be any string of length $n>0$. Our inductive hypothesis is that any shorter string, $z$ is in $L(G)$, i.e., there is a derivation $S\stackrel{*}{\Longrightarrow}z$. Now either $w=za$ or $w=zb$. We'll do one case and leave the rest to you:
$$
S\stackrel{1}{\Longrightarrow}SA\stackrel{3}{\Longrightarrow}SaS\stackrel{2}{\Longrightarrow}Sa\stackrel{*}{\Longrightarrow}za = w
$$
so $w\in L(G)$, as required.


How are partial measurements performed on a N qubit quantum circuit? I am trying to understand quantum computing concepts and have gone through alot of websites and books such as: Quantum Computing by Mikio and https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lecture1.pdf
So I do understand conceptually how to make measurements but I have enclosed images of a circuit i devised for an example and I am not able to attain the result of stage 5 (which is the output of the 1st two qubits only) when represented as matrices?. No paper/text explains this concept with proper examples. Any help is deeply appreciated. I have posted a similar question on the physics forum but they denied to respond as they assumed it some homework problem and had other issues. I am stuck and unable to move forward from here. Also it is not an assignment or anything. Thank you for your help.

To measure a single qubit you:

Split the amplitude vector into "target qubit is Off" and "target qubit is On" parts.
Weigh up the parts. Add up the squared magnitudes of the amplitudes within each part. This gives you the probability of each.
Randomly pick one of the parts. (Or keep tracking both. Just make sure you never interfere parts from one with the other anymore.)
Renormalize the part(s). Divide by the squared-magnitude-sum, so the result totals to 100% again.

You'll probably find the calculations a lot easier if you do one operation at a time instead of a whole column at a time.

Also, you'll probably find my quantum circuit simulator Quirk helpful. It lets you drop state displays into the middle of circuits. Useful for checking your work. Here's your circuit in Quirk, with various displays sprinkled in:

The vector entries are not in quite the same order, but they agree with your results.

As you can see, the top measurement results are 50/50 random and the third qubit ends up pointing right (i.e. in the state $|0\rangle - |1\rangle$ regardless of the measurement outcome). (Trying to factor out a qubit often makes states easier to understand.)

Basically what has happened is easier to explain if you think in terms of the X gate as an X-axis control. Given the state of the third qubit during the CCNot, that "control" is satisfied. So really it's like the controls on the top two wires are a controlled-Z. This entangles the top two qubits.


Finding a hamiltonianISH path in a graph Problem statement

Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions.

Given any starting node.

What algorithm will allow for finding the longest(ish) path.

Considering that each node can only be visited once.

Considering that we don't care where the path ends.

Considering that speed is more important than necessarily visiting each node.

Example

I have traced an example of the desired result in the image below. As you can see, the path does not visit each node and that is fine. I'm looking for a fast algorithm that will give me one of the longest possible path on this graph. 80% coverage or more is what I'm shooting for.

This is the longest path problem.  It's NP-hard to find the longest path in a general graph.  You can try applying any standard algorithm for finding longest paths.  Search on this site for "longest path" and "Hamiltonian path" to find many references.  Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation algorithm (e.g., using a local search algorithm).


Showing that minimal vertex deletion to a bipartite graph is NP-complete Consider the following problem whose input instance is a simple graph $G$ and a natural integer $k$.

  Is there a set $S \subseteq V(G)$ such that $G - S$ is bipartite and $|S| \leq k$?

I would like to show that this problem is $\rm{NP}$-complete by reducing either 3-SAT, $k$-CLIQUE, $k$-DOMINATING SET or $k$-VERTEX COVER to it.

I believe I can reduce the 3-COLORING problem to it so I would only need to see how to reduce one of the mentioned problems to it.  But since that would be rather messy I am wondering if someone sees an elegant reduction to the aforementioned problems.

Also, is there a name for this decision problem?

Your problem is a special case of a broader class of problems named node-deletion problems:

J. M. Lewis and M. Yannakakis, "The node-deletion problem for hereditary properties is NP-complete"

... This paper deals with the class of graph problems defined as follows:
for a fixed graph property $\Pi$, find the minimum number of nodes (or vertices) which must be deleted from a given graph $G$ so that the result satisfies $\Pi$. We call this the node-deletion problem for $\Pi$. Our results show that if $\Pi$ is a nontrivial property which is hereditary on induced subgraph, then the node-deletion problem for $\Pi$ is NP-hard. Furthermore, if we add the condition that testing for $\Pi$ can be performed in polynomial time, then our results imply that the node-deletion problem for $\Pi$ is NP-complete. ...

Your problem is the node deletion problem for bipartiteness, but (as noted by Pal), it is known today as the Odd cycle traversal (OCT) problem.

EDIT

For what regards a direct reduction, I thought of this one from 3SAT.

Given an instance of 3SAT with $n$ variables and $m$ clauses, build the following graph: add two nodes $x_i, \overline{x_i}$ for each variable and an edge between them. To simulate a truth assignment, add $n+1$ nodes for each variable $x_i$ and connect them both to $x_i$ and $\overline{x_i}$; in this way, in order to make a bipartite graph deleting at most $n$ nodes, at least one between $x_i$ and $\overline{x_i}$ must be deleted . Finally for each clause $C_j$ add 4 nodes and build an odd cycle that connects the variables in $C_j$.

The resulting graph $G$ can be made bipartite deleting at most $n$ nodes if and only if the original 3SAT formula is satisfiable.


Is every X3SAT instance with no cycles satisfiable? Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly one literal is true?  X3SAT is NP-hard even if we assume all literals are positive (monotone) and no two clauses have more than one literal in common (linear).

A cycle is a set of clauses such that each clause has one free literal and two backbone literals. A literal is free if it appears in only one clause in the cycle. A backbone literal appears in exactly two cycle clauses.

My question: Is a linear and monotone X3SAT instance with no cycles always satisfiable?

Background: We can think of linear monotone X3SAT as the following problem:  we are given a set of clauses, where each clause has three positive literals and no two clauses have more than one literal in common; the goal is to determine whether there is a set of literals such that each clause contains exactly one literal from the set.

I have generated a number of unsatisfiable linear monotone X3SAT instances and they all have large numbers of cycles, so I'm wondering if every unsatisfiable linear monotone X3SAT instance will have at least one cycle.

The smallest linear and monotone cycle has three clauses:

$\quad$ 3-cycle: $(a,x_1,x_2)(b,x_2,x_3)(c,x_3,x_1)$
$\quad$ Free: $a,b,c$
$\quad$ Backbone: $x_1,x_2,x_3$

A cycle can have more than three clauses.  A cycle with $k$ clauses has $2k$ distinct literals, $k$ free literals, and $k$ backbone literals. A $k$-cycle has $\lceil F_{k+3} / 2\rceil$ satisfying assignments, where $F_i$ is the $i$-th Fibonacci number.

The smallest unsatisfiable linear and monotone X3SAT instance has six 3-cycles, but only five clauses:

$\quad (a,x_1,y_1)(a,x_2,y_2)(a,x_3,y_3)(x_1,x_2,x_3)(y_1,y_2,y_3)$

It contains the following 3-cycles:

$\quad(x_1,x_2,x_3)(a,x_1,y_1)(a,x_2,y_2)$
$\quad(x_1,x_2,x_3)(a,x_1,y_1)(a,x_3,y_3)$
$\quad(x_1,x_2,x_3)(a,x_2,y_2)(a,x_3,y_3)$
$\quad(y_1,y_2,y_3)(a,x_1,y_1)(a,x_2,y_2)$
$\quad(y_1,y_2,y_3)(a,x_1,y_1)(a,x_3,y_3)$
$\quad(y_1,y_2,y_3)(a,x_2,y_2)(a,x_3,y_3)$

X3SAT can be converted into a max weight independent set problem. Let each literal be assigned a vertex. Two vertices have an edge iff the two literals appear together in a clause. The weight of each vertex is the number of clauses the literal appears in (one half the degree of the vertex). The X3SAT instance is solvable only if there is an independent set with weight equal to the number of clauses. If the instance is satisfiable then the graph can be made bipartite by removing exactly one edge from each clause.

The graph below is a positive answer without words.

Here is the detailed proof.
Definitions
Let $X$ be an instance of X3SAT.

$X$ is linear if any two clause shares at most one variable.
$X$ is monotone if all literals in all clauses are positive.
A walk in $X$ is a sequence of clauses where each clause is not disjoint with the clause following it. The length of the walk is the number of its clauses. A walk starts with variable $v$ if its first clause contains $v$. A walk ends with variable $v$ if its last clause contains $v$. A walk is said to connect two variables if it starts with one of the variables and ends with the other variable. In particular, any clause connects all variables in it.
A trail is a walk in which all clauses are distinct.
$X$ is connected if there is a walk between any two variables.
A cycle is a walk whose first clause is its last clause. A simple cycle has no repeated clauses except the first and last clause. $X$ is acyclic if $X$ has no simple cycles, i.e., there is at most one trail between any two variables,
For any two variables, the distance between them is the minimum length of a walk that connects them. The distance between a variable and itself is 0.

A linear monotone acyclic instance of X3SAT is always satisfiable.
Let $X$ be a linear monotone acyclic instance of X3SAT whose set of variables is $V=\{v_1,v_2, \cdots, v_n\}$. Because of monotonicity, we will use variable and literal interchangeably. Each clause in $X$ is also treated as the set of three variables in it.
Assume $X$ is connected. Otherwise, $X$ is the union of two disjoint linear monotone acyclic instances of X3SAT that can be treated independently.
Let $d(u)$ denote the distance from $v_1$ to variable $u$.
Claim 1. For any clause $c=(t,u, w)$, $\{d(t), d(u), d(w)\}=\{\ell, \ell, \ell-1\}$ for some $\ell\ge1$.
Proof: If $c$ contains $v_1$, then it is easy to see that $\{d(t), d(u), d(w)\}=\{1, 1, 0\}$. Now assume $c$ does not contain $v_1$.
WLOG, let $d(w)=\ell-1 > 0$ be the minimum among the three distances. Let $c_1, \cdots, c_{\ell-2}, c_{\ell-1}$ be the unique trail from $v_1$ to $w$. The shared variable between $c_{\ell-2}$ and $c_{\ell-1}$ cannot be $t$ or $u$, since $d(t)\ge \ell-1$ and $d(u)\ge\ell-1.$ That means $c_{\ell-1}\not=c$. Suppose there is a trail $b_1, b_2, \cdots, b_{\ell-1}$ from $v_1$ to $t$. Then for the same reason, $b_{\ell-1}\not=c$. We can reduce the walk $c_1, \cdots, c_{\ell-2}, c_{\ell-1}, c, b_{\ell-1}, b_{\ell-2}, \cdots, b_1, c_1$ to a simple cycle, which is a contradiction, which implies that there is no trails of length $\ell-1$ from $v_1$ to $t$, i.e., $d(t)\gt\ell-1$. Since $c_1, c_2, \cdots, c_{\ell-1}, c$ is a walk of length $\ell$ from $v_1$ to $t$,  $d(t)=\ell$. Similarly, $d(u)=\ell.$ QED.
Fix a total order $\prec$ on $V$. For example, we can let $v_p\prec v_q $ if $p<q$.
Let $A_0=\{v_0\}$. For all $\ell\ge 1$, define $A_{\ell}$ recursively by
$$A_\ell=
\{t\in V: d(t)=\ell \text{ and the last clause of the shortest trail}\\
\text{ from } v_1\text{ to }t\text{ is }(t,u, w)\text{ for some }u,w\in V \text{ such that }\\
d(t)=d(u)=\ell\text{ and }d(w)=\ell-1\text{ and } w\not\in A_{\ell-1}\text{ and }t\prec u\}$$
Let $A=\cup_{\ell=0}^{\infty}A_\ell$. Note that if $d(t)=\ell$, then $t\in A$ iff $t\in A_\ell$.
Claim 2: $A$ shares exactly one variable with each clause.
Proof. Let $c$ be a clause in $X$. By claim 1, $c=(t,u,w)$ where $d(t)=d(u)=\ell$, $d(w)=\ell-1$ and $t\prec u$. The last clause of the shortest trail from $v_1$ to either $t$ or $u$ is $c$.

$w\in A_{\ell-1}$. By definition, $t$ and $u$ are not in $A_\ell$.
$w\not\in A_{\ell-1}$. By definition, $t\in A_\ell$ and $u\not\in A_\ell$.

QED.

Exercises
Let X be a linear monotone acyclic instance of X3SAT with $n$ variables and $m$ clauses.
Exercise 1..(One minute or two) Explain that $A_1$ is empty. Give an example where $A_3$ is not empty.
Exercise 2.. Show that $n= 2m+1$.


Notions of efficient computation A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing thesis:

  Any reasonable model of computation can be efficiently simulated on Turing machines

However, I'm not aware of solid theory for analyzing the computational complexity of algorithms of $\lambda$-calculus.

Do we have a notion of computational efficiency for every known model of computation? Are there any models that are only useful for computability questions but useless for computational complexity questions?

As far as I know, the main models of computability are λ-calculus, Turing machines and recursive functions. I am not aware of the situation regarding complexity in recursive functions, they may or may not be useless for complexity.

It may be seen as a fortunate coincidence that Turing machines, which are not so arguably very inefficient machines, are also a very good model of complexity. What made things natural is that there are a lot of transformations involving TMs that are polynomial. (Universal machine, simulation of a $n$-taped machine with a 1-taped machine, from an arbitrary alphabet to a binary one, simulating a PRAM, ...) and that polynomials are a class of functions stable by arithmetic operations and composition – which makes them a good candidate for complexity theory.

Pure λ-calculus was in itself useless for complexity. However a simple type system came into play and allowed guarantees of termination for some λ-terms in a very easy way. Then some other systems (systems T, F, ..) allowed a great expressiveness while keeping termination.

Efficiency or complexity being a refinement of termination and types being closely related to logic, later came light linear logics which characterizes several classes of complexity. (Elementary, P, and some variations for PSPACE and others). The research in this domain is very active and is not restricted to these complexity classes, and is not even restricted to the λ-calculus.

tl;dr: λ-calculus was useful for computability, termination and complexity theory.

However to give credit where credit is due Turing machines are a good and unanimous way to define what is complexity, but that's true only for loose bounds like "polynomial", not for tight bounds for which PRAM-like models are more suitable.


What undecidable language $B$ is reducible to its complement? I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$...
However, I could find it hard to construct an example ... my difficulty is that given an undecidable but Turing recognizable language, say $A_{TM}$, its complement $\overline{A_{TM}}$ is not Turing recognizable and loops. If I reduce such a language (say $x \in A_{TM} \leq_m y \in  \overline{A_{TM}}$, the instance $y \in \overline{A_{TM}}$ cannot be recognized by any TM (since by definition, $\overline{A_{TM}}$ is looping)...
Any help ?

Let $H$ be the language of all Turing machines that halt on empty input.
Clearly $H$ is undecidable.
Let $L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$.
Clearly $L$ is undecidable. If $L$ were decidable, then a Turing machine $M$  for $L$ would also imply the existence of a Turing machine $M'$ that decides $H$. $M'$ with input $T$ simply simulates $M$ with input $(1,T)$.
Moreover, for a Turing machine $T$ and $x \in \{0,1\}$ we have:
$$
(x, T) \in L \iff (1-x, T) \not\in L \iff (1-x, T) \in \overline{L}.
$$
This, combined with the fact that we can decide whether a given word encodes a valid Turing machine, shows that $L$ is reducible to $\overline{L}$.


Myhill-Nerode equivalence classes I need to find the Myhill-Nerode equivalence classes for the language $$ L = \Sigma^*\setminus \left( \{\epsilon, cc \} \cup \{ cca^i: i\geq 2 \} \right) $$ over $\Sigma = \{a, b, c \}$
I'm familiar with the idea of separating suffix, but I really don't know where to start here.
Thanks!

To begin with, note the the Myhill-Nerode equivalence classes for a language $L$ is the same as the Myhill-Nerode classes for its complement $\overline{L}$. This follows immediately by definition, and I leave it you (it also appears here).
So given $\Sigma = \{a, b, c\}$, we need to find the Myhill-Nerode classes for $\overline{L} = \{ \epsilon, cc\}\cup \{cca^i: i\geq 2 \}$. There are many ways to do so, one can, for example, consider what happens in a minimal deterministic automaton for the language - it is known that the states of the minimal deterministic automaton correspond to the Myhill-Nerode classes. Yet, the given language is simple enough, you can actually experiment with it a bit and show that the following are the equivalence class for $\overline{L}$ (indeed, $\overline{L}$ has a simple structure - every word of length at least $4$ in the laguage is of the form $cca^i$, so clearly all these words are equivalent. Then, you can look at words of length < 4, and try to see which among them are equivalent, etc.):

$C_1 = \{ \epsilon\}$.
$C_2 =  \{ c\}$.
$C_3 =  \{ cc\}$.
$C_4 = \{ cca\}$.
$C_5 = \{ cca^i: i\geq 2\}$.
$C_6 = \Sigma^*\setminus \left( \bigcup_{i\in [5]} C_i\right)$.

Clearly the 5 sets above partition $\Sigma^*$, so to show that they are indeed the Myhill-Nerode classes, we need to show that all the words in the same set are Myhill-Nerode equivalent, and for every $ 1\leq i < j \leq 6$, it holds that the words in the set $C_i$ are not equivalent to the words in the set $C_j$.
There you go, try to prove that the above sets are indeed the equivalence classes. That should be easy enough now.