Why is Adleman's molecular algorithm for Hamiltonian Path linear?

You are right that in the coding of the graph one needs a possibly quadratic number of strands to represent the edges.

My guess is that Adleman likes to distinguish the two kinds of operations. First there is the coding of the input graph, which may be very complicated to avoid accidental combinations. Then there is the number of laboratory steps to actually check the presence of Hamiltonian paths.

I think this might be explained by the way he envisions how molecular computing can be used. Given a big "database" of available strands one performs a number of laboratory steps to find the solution to a  problem. This is then the same operation performed in parallel to zillions of molecules. This I read from the way how he explains the number of operations performed per second.


Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?

You may have to rebalance during insertions, that much is clear: inserting a sorted sequence of values would otherwise lead to a degenerate tree.

By looking at the setup graphics of the four types of rotation, you can easily see that the height of the affected subtree after the insertion is the same as before. Thus, no node outside of this subtree can be imbalanced.

Thus, we never need more than one rotation when inserting. We can stop moving up the tree after we've rotated once, and efficient (non-recursive) implementations do exactly that.


Has this generalization of Turing machines studied before?

A general notion of machines based on graphs was given by Wilfried Sieg and John Byrnes in K-Graph Machines: Generalizing Turing's Machines and Arguments. It may or may not be related to what you are doing.

Also note that it is quite easy to find a complete formalization of Turing machines. Why are you saying that "the tape of a Turing machine ... is usually left out when introducing Turing machines". That's an odd thing to say. Let's perform an experiment. For instance, what is unclear about the definition given on Wikipedia (following a standard textbook)? All you need is a formalization of finite sequences, and I'd be flabbergasted if Mizar hasn't got those.


What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph?

I've only ever heard of directed and undirected graphs, whose definitions can be found in Wikipedia. Rudimentary search reveals the following interpretations of unidirectional and bidirectional graphs; it is possible that these terms also have different interpretations:

A unidirectional graph is another name for an undirected graph.
A bidirectional graph is a directed graph obtained from an undirected graph by replacing each edge $\{x,y\}$ by a pair of edges $(x,y),(y,x)$.


Do we need both path compression and union by rank together in disjoint set data structure?

No, you are not right, at least not if you want the fastest possible running times.  Using both is faster than using just one of them alone.  Using just Union by rank gives you a $O(m \lg n)$ running time per operation, whereas using both Union by rank and path compression gives you a $O(\alpha(n))$ running time per operation, which is asymptotically faster.  Here $n$ is the number of elements and $m$ is the number of operations performed on them. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity.


Bijective algorithm(s) that can shuffle a range of numbers back and forth

The subject is called format-preserving encryption,

and your last bullet point is addressed by tweaks.

Simple
http://web.cs.ucdavis.edu/~rogaway/papers/feistel.pdf

http://arxiv.org/pdf/1208.1176.pdf

http://web.cs.ucdavis.edu/~rogaway/papers/sr.html
Complex


What is the use case for multi-type-parameter generics?

Some use cases for multiple type arguments include

maps/dictionaries Map<K,V>, where you have one key parameter and one value parameter
product types Pair<A,B>
sum types, AKA variants Variant<A,B>, which represent a value which might be either of type A or of type B
Function-like types Func<A,B> representing a function from A to B
"Visitor" objects for parametric types. I.e. a visitor for List<A> is ListVisitor<A,R> where R is the return type of the visitor.

If we did not have multiple type arguments, or any other way to emulate multiple argument types (e.g. nested parametric classes class T<A> { class U<B> { ... which are a sort-of curried version of the two-arguments class), we could not express the examples above in a generic way.

Of course, a programming language could disallow generic classes and still have a specific primitive type for some of the examples above. For instance, Func<A,B> could be a primitive type, instead of a user/library-defined class type.


Suggestions for Short Examples Contrasting Functional Programming Languages

Project Euler has nice problems for showcasing the core of a programming language.
An important part of a programming language are user defined (container) data structures. Bread and butter containers include random access arrays, bidirectional lists, hash tables, and search trees. You may take the implementations from standard libraries of the languages to get interesting real world programs for you comparisons.
A strong point of functional programming languages is that they allow modular reuse of standard algorithms. The C++ stl header algorithm provides a nice collection of those reusable standard algorithms.


Is Starvation Possible in LOOK Algorithm

The wiki article also says that

  This is because LOOK is biased against the area recently traversed, and heavily favors tracks clustered at the outermost and innermost edges of the platter.

However, I found it confusing.

The reason why LOOK avoids starvation is quite easy: For any request, it will be served within a finite time interval $t$ (since it is submitted): Suppose the number of cylinders in a disk is $N$, then we can set $t = 2N$.


Proving that Rice's theorem does not apply to a property

The answer is right but the argument is not sufficient. Try to build a contradicting example as a proof. Describe how to encode each machine into a binary number (can be found in any tcs book). Then choose some random non-trivial property say number of tates equal to 4. Show that there is a machine the belong to the ass and a machine that does not. Finally describe a universal machine deciding the property (which is doable if the encoding is injective/reverseable (which is usually the case). Since the example contradics the theorem it early does not apply here. The intuitive reason is that you defined property in machines and not on languages.


Is it possible to solve the halting problem if you have a constrained or a predictable input?

The intuitive answer is that if you don't have unbounded loops and you don't have recursion and you don't have goto, your programs terminate. This isn't quite true, there are other ways to sneak non-termination in, but it's good enough for most practical cases. Of course the converse is wrong, there are languages with these constructs that do not allow non-terminating programs, but they use other kinds of restrictions such as sophisticated type systems.

Recursion

A common restriction in scripting languages is to dynamically prevent recursion: if A calls B calls C calls … calls A, then the interpreter (or checker, in your case) gives up or signals an error, even if the recursion might actually terminate. Two concrete examples:

The C preprocessor leaves a macro intact while it is expanding that macro. The most common use is to define a wrapper around a function:

#define f(x) (printf("calling f(%d)\n", (x)), f(x))
f(3);

This expands to

(printf("calling f(%d)\n", (3)), f(3))

Mutual recursion is handled as well. A consequence is that the C preprocessor always terminates, although it's possible to build macros with high run-time complexity.

#define f0(x) x(x)x(x)
#define f1(x) f0(f0(x))
#define f2(x) f1(f1(x))
#define f3(x) f2(f2(x))
f3(x)

Unix shells expand aliases recursively, but only until they encounter an alias that's already being expanded. Again, the primary purpose is to define an alias for a similarly-named command.

alias ls='ls --color'
alias ll='ls -l'

An obvious generalization is to allow a recursion depth of up to $n$, with $n$ perhaps being configurable.

There are more general techniques to prove that recursive calls terminate, such as finding some positive integer that always decreases from one recursive call to the next, but these are considerably harder to detect. They are often hard to verify, let alone infer.

Loops

Loops do terminate if you can bound the number of iterations. The most common criterion is that if you have a for loop (without tricks, i.e. one that really counts from $m$ to $n$), it performs a finite number of iterations. So if the body of the loop terminates, the loop itself terminates.

In particular, with for loops (plus reasonable language constructs such as conditionals), you can write all primitive recursive functions, and vice versa. You can recognize primitive recursive functions syntactically (if they are written in an unobfuscated way), because they use no while loop or goto or recursion or other trick. Primitive recursive functions are guaranteed to terminate, and most practical tasks don't go beyond primitive recursion.


An ID (auto increment integer) always as primary key for each db-table?

I assume you are using RDBS.As far as you can set any value as primary key this will not cause strict programming trouble - but will be cumbersome.

What about convention that people use integer?
This comes from two parts:
It is easier to give unique id from autoincremented value.
Second is from relations and optimizations - database internally connects related items, so setting something different will cause overhead.

You should read two pages:
normal forms in database and primary keys.

Normal form is something you should have (at least third level) in your database, it saves programming trouble later like with splitting keys manually.


You haven't defined when a randomized protocol is declared to be successful, so I will assume that at the end of the protocol, Bob tells a judge what he thinks the message is, and we want that for each message $x$, the probability that Bob is correct is at least $1-\epsilon$.

Let $X$ be a random $n$-bit string, and let $\Pi$ be the corresponding transcript. Let $R$ be the randomness in the protocol (i.e., given $R$ the protocol is deterministic, and Bob's output is deterministic). Let $Y$ be Bob's output, and let $B$ be an indicator variable for the event $X=Y$.

The definition of correctness of the protocol shows that
$$
\begin{align*}
H(X|\Pi R) &\leq H(BX|\Pi R) \\ &= H(B|\Pi R) + H(X|\Pi RB) \\ &\leq 1 + \Pr[B=1] H(X|\Pi R,B=1) + \Pr[B=0] H(X|\Pi R,B=0) \\ &\leq 1 + 1 \cdot 0 + \epsilon \cdot n \\ &= \epsilon n + 1.
\end{align*}
$$
This implies that
$$
H(\Pi|R) = H(X\Pi|R) - H(X|\Pi R) = H(X) - H(X|\Pi R) \geq (1-\epsilon) n - 1,
$$
since $H(X\Pi | R) = H(X | R)$ (given $R$, Alice's input $X$ determines the transcript $\Pi$) and $H(X|R) = H(X)$ (since Alice's input and the randomness are independent).

We conclude that the communication complexity is at least
$$
(1-\epsilon) n - 1 = \Omega(n).
$$


What is the difference between Strict 2Phase Locking and 2Phase Locking?

There are mainly two reasons for adopting Strict 2PL rather than Basic 2PL, explained in [1].

The first reason is about the time when a 2PL scheduler can release some (read/write) lock owned by some transaction on some data item.
A second reason for the scheduler to keep a transaction’s locks until it
ends, and specifically until after the DM processes the transaction’s Commit or
Abort, is to guarantee a strict execution. Strict executions are recoverable and avoid cascading aborts (ACA).

[1] Chapter 3 "Two Phase Locking" in the Book "Concurrency Control and Recovery in Database Systems"; Page 59. By Bernstein et al., 1987.


Pumping lemma: if you can keep pumping, what does this tell you?

If you are not sure, it is probably because you want to know why. This question is frequent among students in computer science that are learning the pumping lemma for the first time and it is the cause of a lot of errors.

Logic

The reason is very simple. It is because of logic. I will explain it considering the pumping lemma for the regular languages but it is analog for the context-free version of the lemma. The statement that has been proved is the following:

$$1)\ L\text{ is a regular language}\implies L\text{ complies with the pumping lemma}$$

This is all we know. Notice that this implication is in one direction. In other words we can't conclude:

$$2)\ L\text{ complies with the pumping lemma}\implies L\text{ is a regular language}$$

It is a common mistake to invert the propositions in the first implication and expect to obtain a  logically equivalent statement (you can't use the second statement!).

When we use the pumping lemma we are actually using the contrapositive of the first implication:

$$3)\ L\text{ doesn't complies with the pumping lemma} \implies L\text{ is not regular}$$

The first and the third statements are logically equivalent. This is why we search for a contradiction when trying to force $L$ to fulfill the pumping lemma. If $L$ doesn't comply with the lemma then we are sure that $L$ is not regular. If you were paying attention you could have noticed that we can't prove that $L$ is regular using the pumping lemma. If you want to prove that $L$ is a regular language you should find a regular expression, NFA or a DFA (or even a regular grammar) that denotes $L$.

Inside the pumping lemma

Another big source of error is the incorrect interpretation of the lemma. Every word in the lemma is very important:

Pumping lemma: If $L$ is regular then there exists a constant $N\in \mathbb{N}$ such that for all $\sigma$ in $L$ with $|\sigma|\geq N$ there exists a decomposition $\sigma=\alpha\beta\gamma$ such that:

a) $|\alpha\beta|\leq N$

b) $\beta \neq \epsilon$

c) $\alpha\beta^i\gamma \in L\ \forall i \in \mathbb{N}_0$

Common mistakes

1) My word $\sigma$ complies with the pumping lemma so $L$ must be regular:
This is wrong for so many reasons. First, we can't conclude that $L$ is regular using the pumping lemma (see the Logic section). Second, a lot of words can comply the three conditions but the lemma clearly state that all $\sigma\in L$ with $|\sigma|\geq N$ should comply. So good luck trying with another word!

2) If I choose this particular $\alpha$, $\beta$ and $\gamma$ I find a contradiction!:
This is wrong too. The lemma states that there exists a decomposition(at least one) that fulfill the lemma. So if you choose one and it doesn't meet the three conditions it doesn't say too much... Now you have to try with all the remaining possible decompositions! You will find a contradiction when you prove that is impossible to find such a decomposition.

3) If I choose the word $\sigma=\epsilon$ I find a contradiction!:
This is wrong for two reasons. First, $N>0$. Second, the lemma states that there exists a constant $N$. If you choose $N=0$ (wrong by definition) or $N=1$, $N=2$, etc and you find a contradiction it is okay. Now you have to try all the remaining integer $N$! This is the reason why you should never try to choose a specific constant $N$ and why you should use a generic constant instead.

4) I tried a lot of words and all of them comply with the pumping lemma... what do I do?:
At this point you have two options. You can suspect that $L$ is regular and try to find a regular expression(or NFA, DFA, regular grammar...) that denotes $L$. If you suspect that $L$ is not regular then maybe it is time to use closure properties to simplify the problem or you can continue your epic quest of proving that $L$ is not regular by trying others words.

These are all the tips I have for now. If I can remember some more in the future I will add them here.


Data structure for testing all subsets of a query for membership

Let's say all your sets are finite subsets of $\mathbb N$. Let $S\subseteq \mathcal P( \mathbb N)$ denote your set of sets.

You want two operations:

$O_1(S,s')$: For any $s'\subseteq \mathbb N$, add $s'$ to $S$
$O_2(S,s')$: For any $s'\subseteq \mathbb N$, is there some $s\in S$ so that $s\subseteq s'$?

Here are a few ideas to speed things up:

You're going to test if a set if a subset of another a lot so you should probably keep the size $|s|$ of each set $s$ available in $O(1)$ so that when you need to test if $s\subseteq s'$, you start by checking if $|s|\le |s'|$ and if not, you can return false right away. And it you indeed have $|s|\le |s'|$, then you just run the normal slow test.
Note that if you have $s_1\in S$ and $s_2\in S$, so that $s_1\subseteq s_2$, then if $s_2\subseteq s'$, you also have $s_1\subseteq s'$. So you don't need to keep $s_2$ in $S$ for $O_2$. So you can represent $S$ by a set of sets so that $s\in S$ and $s\subsetneq s'$ implies $s'\not \in S$.  In other words, you only need to keep track of the sets in $S$ that are minimal for inclusion. This can be implemented pretty efficiently: When adding a set $s'$, for all sets $s\in S$ so that $|s|\le |s'|$ (ordered by increasing cardinal), if $s\subseteq s'$, then don't add $s'$ because it won't be minimal (or is already in $S$). Otherwise, add $s'$ and then among sets $s\in S$ so that $|s'|<|s|$, remove those so that $s'\subseteq s$ (because they are no longer minimal).
Keep a set $t$ that's equal to the union of all sets in $S$. Then, instead of running $O_2(S,s')$, you can run $O_2(S,s'\cap t)$ instead (because if for some $s\in S$, $s\subseteq s'$, then since $s\subseteq t$, $s\subseteq s'\cap t$ and, if $s\subseteq s'\cap t$, then $s\subseteq s'\cap t \subseteq s'$).

With these ideas in mind, I'd represent $S$ by a dictionnary (implemented as a doubly linked list of pairs $(key,value)$ with the keys in increasing order) $d$ so that $d(k)$ is a doubly linked list containing exactly the minimal (for inclusion) sets in $S$ of cardinal $k$.

O1(S,s')
  if O2(S,s')
    return
  if d(k) doesn't exist
    d(k) := new_doubly_linked_list()
  add(d(k),s')
  S.t := union(S.t, s')
  for each key k of d so that |s'|+1 <= k
    for s in d(k)
      if subset(s', s)
        remove s

_O2(S,s')
  for each key k of d so that k <= |s'|
    for s in d(k)
      if subset(s,s')
        return true
  return false

O2(S,s')
  return _O2(S,inter(S.t,s'))

(Notice that even though I didnd't do it explicitely in the code of O1, you can do a single traversal of the doubly linked list representing d)

I don't think this improves too much in the worst case but in average it should.


How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm

$$
\begin{align*}
\sum_{h=0}^{\lfloor\lg n\rfloor} \left\lceil\frac{n}{2^{h+1}}\right\rceil O(h)
&<
\sum_{h=0}^{\lfloor\lg n\rfloor} \left(1+ \frac{n}{2^{h+1}}\right) O(h)  \\
&<
\sum_{h=0}^{\lfloor\lg n\rfloor} \left(\frac{n}{2^h} + \frac{n}{2^h}\right) O(h)
=
2n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ O(h) }{2^h}
= O\left(n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ h }{2^h}\right).
\end{align*}
$$.


Minimizing a regular expression is PSPACE-hard.  Therefore, if you're looking for a general set of techniques to minimize a regular expression, there's no good solution: there is no good set of techniques that always works and is always efficient.  See https://cs.stackexchange.com/a/12278/755 and https://cs.stackexchange.com/a/43863/755 and https://cstheory.stackexchange.com/q/12361/5038.

Of course, none of these results rule out the possibility of techniques that work for your particular example or that sometimes work.  However, they show that you shouldn't expect any general technique, i.e., any technique that works for all regular expressions and always gives the optimal answer and is asymptotically efficient.

That said, there are some ad-hoc methods you can use.  For instance, by staring at it, you can quickly recognize that

$$abb^* + a = ab^*,$$

since $ab^* = a(b^*) = a(\varepsilon + b b^*) = a + abb^*$.


Is there a name for the problem of spatially organizing a graph as to minimize total edge length?

This is a version of graph drawing, restricted to vertices being on a grid, but allowing more than two dimensions.  The one-dimensional case is an example of a graph layout problem, known as Minimum Linear Arrangement. In all of these problems, one is interested in minimizing some metric of the resulting diagram, which could be the number of edge crossings or, in your case, the total length of the edges.

These kinds of problem are very often NP-hard, even in the one-dimensional case: in particular Minimum Linear Arrangement, the 1D version of your problem, is NP-hard. There's a survey of graph layout problems by Díaz, Petit and Serna (ACM Surveys, 34:313–356, 2002; .ps.gz).


Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be
$$
    {\sf eats}({\sf cat}, {\sf head}({\sf tuna}))
$$
Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows:
$$
\mbox{World $w$: }\qquad\qquad
\begin{array}{l}
  [\![ {\sf cat} ]\!]^c = 5 \\
  [\![ {\sf tuna} ]\!]^c = 4 \\
  [\![ {\sf squirrel} ]\!]^c = 2 \\
  \ldots \\
  [\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\
  \ldots \\
  [\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \}
\end{array}
$$
(A structure can define more symbols than those used in the formula, hence
the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$.
Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$.
Predicate symbols are interpreted as subsets of $D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $[\![-]\!]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have
$$
  [\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c))
$$
which is
$$
  < (5, g(4))
$$
i.e.
$$
  5 < \pi \cdot 4
$$
which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.


Finding a cycle in a graph with the biggest value (the sum of all edges)

You should note that this problem is NP-hard (i.e., when all edges have uniform weight, a cycle of maximum weight is a Hamiltonian cycle). So unless your inputs are small or somehow usefully structured, it's probably a better idea to go for heuristics since there is likely no polynomial-time algorithm.

To fix your exact algorithm, possibly with a few tricks to speed things up as well, you can have a look at the description of an algorithm given by Rubin [1].

[1] Rubin, Frank. "A search procedure for Hamilton paths and circuits." Journal of the ACM (JACM) 21.4 (1974): 576-580.


Compression of sequence with Direct Access

You can use the so-called "binomial encoding", described in one of my answers on math.stackexchange. You have to consider, though, whether it will be worthwhile. The naive encoding takes $n \log_2 k$ bits, and the best encoding saves about $O(\log n)$ bits (the best encoding uses $\log_2 \frac{n!}{f!^k}$ bits). Plug in your actual numbers to see what kind of saving you can expect.

Edit: I can't find my supposed post on math.stackexchange, so here is a summary of binomial coding (or rather multinomial coding), as it applies in this case. For a vector $x$ of length $k$, define
$$ w(x) = \frac{(\sum_i x_i)!}{\prod_i x_i!}. $$
Note that for $x \neq 0$,
$$ w(x) = \sum_{i\colon x_i > 0} w(x-e_i), $$
where $e_i$ is the $i$th basis vector. For example, if $k = 2$ and $x_1,x_2>0$ then
$$ w(x_1,x_2) = w(x_1-1,x_2) + w(x_1,x_2-1). $$
This is just Pascal's identity
$$ \binom{x_1+x_2}{x_1} = \binom{x_1+x_2}{x_1-1} + \binom{x_1+x_2}{x_1}. $$

For every vector $x$ and every $i$ such that $x_i > 0$, define
$$ w(x,i) = \sum_{j < i\colon x_j > 0} w(x-e_j). $$
Given a sequence $\sigma$ of letters in $\{1,\ldots,k\}$, let $H(\sigma)$ be its histogram, a vector of length $k$. For a non-empty word $\sigma \neq \epsilon$, let $\sigma_1$ be the first symbol, and $\sigma_{>1}$ be the rest, so that $\sigma = \sigma_1 \sigma_{>1}$. We are now ready to define the encoding:
$$ C(\sigma) = \begin{cases} w(H(\sigma),\sigma_1) + C(\sigma_{>1}) & \sigma \neq \epsilon \\ 0 & \sigma = \epsilon. \end{cases} $$
$C(\sigma)$ is an integer between $0$ and $\frac{n!}{f!^k}-1$.

Here is an example, with $k=f=2$. Let us encode $\sigma = 0101$:
$$
\begin{align*}
C(0101) &= w((2,2),0) + w((1,2),1) + w((1,1),0) + w((0,1),1) \\ &=
0 + w(0,2) + 0 + 0 = 1.
\end{align*}
$$
You can check that the inverse images of $0,1,2,3,4,5$ are
$$
0011,0101,0110,1001,1010,1100.
$$
These are just all the solution in increasing lexicography order.

How do we decode? By reversing the encoding procedure. We know the initial histogram $H_1$. Given an input $c_1$, we find the unique symbol $\sigma_1$ such that $w(H_1,\sigma_1) \leq c_1 < w(H_1,\sigma_1+1)$. We then put $H_2 = H_1 - e_{\sigma_1}$, $c_2 = c_1 - w(H_1,\sigma_1)$, and continue. To test your understanding, try to decode $0101$ back from its encoding $1$.


Showing the following language is decidable

You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.

So. We have some DFA $M$, and we can build a PDA $N$ which recognizes the language $\{w : \#_0(w) = \#_1(w)\}$, where $\#_a(w)$ denotes the number of occurrences of the symbol $a$ in the string $w$ (note this is not the same as $\{0^n 1^n : n \geq 0\}$). Then $L(M) \cap L(N)$ is context-free. Checking if $M$ accepts a balanced string amounts to checking if $L(M) \cap L(N)$ is the empty language. But it's known that emptiness of context-free languages is decidable. Given $M$, we can easily construct the machine which recognizes $L(M) \cap L(N)$ and check if $L(M) \cap L(N)$ is empty. So your problem is decidable!


prove that NDFA = { | M1 and M2 are DFAs such that there is at least one string x that is accepted by neither M1 nor M2} is decidable?

We try to decide the language $NDFA$ using a language that decides $ANFA$.

If $x$ is not in neither $L(M_1)$ or $L(M_2)$, then it means that it's not in $L(M_1) \cup L(M_2)$, in other words there is at least one string $x$ which is not in $L(M_1) \cup L(M_2)$, thus $L(M_1) \cup L(M_2) \neq \Sigma^*$ We know that we can (in finite time) construct a $NFA$, $M$ for language $L(M_1) \cup L(M_2)$. Now since $ANFA$ is decidable, $\overline{ANFA}$ is also decidable, so there is a $TM$ that can decide that $L(M) \neq \Sigma^*$, therefor the original language $NDFA$ is also decidable.


The two requirements for a problem to be in NP are

it must be possible to check a given solution in polynomial time;
there must be some polynomial $f$ such that solutions to instances of length $n$ have size at most $f(n)$.

Properly, the "solutions" are referred to as "certificates" since they don't have to be an actual solution to the problem. Normally, the certificate to something like a satisfiability problem would be a satisfying truth assignment, but anything that "proves" the instance is in the langauge is acceptable. In particular, the proof that every language in NP can be thought of in these terms uses a description of the accepting computation of a Turing machine as the certificate.

This gives intuition why the certificate has to have polynomial length: the Turing machine was only allowed to run for a polynomial number of steps. Indeed, if you dropped the polynomial length requirement on the certificate, even the halting problem would "be in NP". The certificate would be a description of the steps taken by the Turing machine before it halts; you can easily check in polynomial time that a certificate is valid, but the certificate itself might have arbitrary length.


It may seem at first as though computing the two's complement of b would cost you a whole separate incrementer, but you can easily merge it into the adder that you need anyway: just set the carry-in.

Alternatively (for example if you are somehow forced to use an adder without carry-in, or if it just works out better in combination with other logic) you may used that a - b = ~(~a + b), which obviously only ever needs inverters and a normal adder. This does put inverters before and after though, whereas to calculate the two's complement of b you'd only need inverters before the adder (and a carry-in but that's almost free).


Can one show NP-hardness by Turing reductions?

There are (at least) two different notions of NP-hardness. The usual notion, which uses Karp reductions, states that a language $L$ is NP-hard if every language in NP Karp-reduces to $L$. If we change Karp reductions to Cook reductions, we get a different notion. Every language which is Karp-NP-hard is also Cook-NP-hard, but the converse is probably false. Suppose that NP is different from coNP, and take your favorite NP-complete language $L$. Then the complement of $L$ is Cook-NP-hard but not Karp-NP-hard.

The reason that $\overline{L}$ is Cook-NP-hard is the following: take any language $M$ in NP. Since $L$ is NP-hard, there is a polytime function $f$ such that $x \in M$ iff $f(x) \in L$ iff $f(x) \notin \overline{L}$. A Cook reduction from $M$ to $\overline{L}$ takes $x$, computes $f(x)$, checks whether $f(x) \in L$, and outputs the converse.

The reason that $\overline{L}$ is not NP-hard (assuming NP is different from coNP) is the following. Suppose $\overline{L}$ were NP-hard. Then for every language $M$ in coNP, there is a polytime reduction $f$ such that $x \in \overline{M}$ iff $f(x) \in \overline{L}$, or in other words, $x \in M$ iff $f(x) \in L$. Since $L$ is in NP, this shows that $M$ is in NP, and so coNP$\subseteq$NP. This immediately implies that NP$\subseteq$coNP, and so NP=coNP.

If some Cook-NP-hard language $L$ is in P, then P=NP: for any language $M$ in NP, use the Cook reduction to $L$ to give a polytime algorithm for $M$. So in that sense, Cook-NP-complete languages are also "hardest in NP". On the other hand, it is easy to see that Cook-NP-hard=Cook-coNP-hard: a Cook reduction for $L$ can be converted to a Cook reduction for $\overline{L}$. So we lose some precision by using Cook reductions.

There are probably other shortcomings to using Cook reductions, but I'll leave that to other answerers.


Finding "entrance" points in a set of d-dimensional points. Can I do better than O(N^2)?

Your problem is similar to finding Maxima of a point set in a $d$-dimensional space. In $2$-$D$ and $3$-$D$ there is a simple Divide and Conquer algorithm that has a $O(n \log n)$ running time. For higher dimension, there is $O(n (\log n)^{d-3}\log \log n)$ time algorithm as given in the Wikipedia page.
You can covert your problem to the Maxima problem, by simply negating the coordinate values of the input points. In other words, your problem is a Minima problem.


Question about time-complexity for MST-like algorithm

This problem looks variant of TSP problem(more precisely metric TSP). As you want to traverse all node with the minimum distance.

TSP is one of the classical NP-Hard problem.

What your friend did is a Greedy approach making minimum Spanning tree Which is 2-Approx(metric-TSP) of the minimum distance.

This greedy approach generally works in E log V time but does not have guarantee for exact solution.

By using graph structure we can implement in linear time also.


So if a problem is more difficult the language it represents is smaller?

$L_1$ and $L_2$ are always countably infinite, and thus "equally big".

If any language is finite, then it is "constant time" recognizable.


Could a Van Emde Boas tree be used for storing matrices?

Yes you are right; but actually I think what you need is a hash table, which supports insert, delete and find in O(1) (although it requires some randomization).

Of course, you can replace a hash table by a VEB tree, when the elements are integers. However, if you want to optimize the space usage, you still need hashing when constructing the VEB tree. Luckily, there's some data structure called Y-fast trie that supports operations similar to VEB tree, but only needs linear space, and is deterministic.


Notice that the word 000 is not accepted by your automaton. To see why your automaton is wrong. Look at the strongly connected component that includes the initial state (the first two states in your figure, lets call them $q_0$ and $q_1$). This component is meant to read the (0|1)* prefix. Hence, you must be allowed to get out of this component(i.e., guess when to start reading the 000 part of the word) from either $q_0$ or $q_1$. To fix your solution, you should add a transition, labeled with 0, from $q_0$ to the third state in your figure (lets call it $q_3$). Or you can replace the whole component with a single state q. such that q is initial, has a self-loop labeled with 0,1 and has a transition, labeled with 0, to $q_3$.


Decidability of language of TMs which accept only their Gödel number

The recursion theorem states that if $A(x,y)$ is a two-input Turing machine then there is a Turing machine $M$ such that $M(x) = A(x,\langle M \rangle)$. Moreover, $M$ can be constructed from $A$ effectively (i.e., using an algorithm). Using this, we can reduce the halting problem to your problem. Given a Turing machine $B$ and an input $z$, construct a new Turing machine $A(x,y)$ which acts as follows:

If $x = y$ then simulate $B$ on $z$.
Otherwise, enter an infinite loop.

Use the recursion theorem to construct a new machine $M$ that on input $x$ acts as follows:

If $x = \langle M \rangle$ then simulate $B$ on $z$.
Otherwise, enter an infinite loop.

Then $M \in L$ iff $B$ accepts $z$.


Maximum product of contiguous subsequence over $\mathbb{R}$

You can adopt the dynamic programming solution; the other solution looks harder to adapt.

Given an array $A_1,\ldots,A_n$, we let $P_i$ be the maximum positive product of a subsequence of $A_1,\ldots,A_i$ containing $A_i$, and we let $N_i$ be the minimum negative product of such a subsequence. If no such subsequences exist, we let $P_i = 0$ or $N_i = 0$.

Initialization:

If $A_1 = 0$ then $P_1 = N_1 = 0$.
If $A_1 > 0$ then $P_1 = A_1$ and $N_1 = 0$.
If $A_1 < 0$ then $P_1 = 0$ and $N_1 = A_1$.

Iteration:

If $A_i = 0$ then $P_i = N_i = 0$.
If $A_i > 0$ then $P_i = \max(A_i, A_i P_{i-1})$ and $N_i = A_i N_{i-1}$.
If $A_i < 0$ then $P_i = A_i N_{i-1}$ and $N_i = \min(A_i, A_i P_{i-1})$.

If $\max(P_1,\ldots,P_n) > 0$, then this is the answer. The only way in which this fails to happen is if there is no subsequence whose product is positive. This can only happen if the array contains only negative numbers and zeroes, and every two negative numbers are separated by at least one zero. If there is at least one zero, then the answer is zero. If there are no zeroes, then $n = 1$, and the answer is $A_1$.


What is the relationship between two definitions of Turing-computability of a partial function?

Definition 1 is incorrect. It does not define the notion of partial computable function correctly. Definition 2 is correct.

Proposition: A partial function $f$ is computable according to your definition 1 if, and only if, it is a partial computable function whose domain $\mathrm{dom}(f)$ is a computably decidable set.

Proof.
Suppose $f$ is computable according to definition 1. Then for every $n \in \mathbb{N}$, we have $n \in \mathrm{dom}(f)$ if, and only if, $\bar{f}(n) \neq \bot$. So we can decide whether $n \in \mathrm{dom}(f)$.

Conversely, suppose $f$ is a partial computable function whose domain $\mathrm{dom}(f)$ is decidable. Then $\bar{f}$ is computable because we can compute it like this: given input $n$, if $n \in \mathrm{dom}(f)$ then output $\bot$, otherwise output $f(n)$. $\Box$


Suppose input graph is simple (without parallel edges), now, If you solve your problem, you can check existence of Hamiltonian path, actually if s-t path of cost zero for some pair exists means there is Hamiltonian path and you can check this for all pair of vertices as (s,t), so you are unlucky to have polynomial time algorithm except $P=NP$.


How to understand out of bound in the following theoretical context?

It is often useful to allow arrays of zero length. These are just empty arrays. The length of the subarray $A[i\ldots j]$ is $j-i+1$, so when $j=i-1$, we just get an array of length 0.

Why is this useful? Here are some examples:

An array $A[1\ldots n]$ can always be partitioned into two arrays $A[1\ldots i]$ and $A[i+1 \ldots n]$ of lengths $i,n-i$. This works even for $i \in \{0,n\}$.
We can construct an array $A[1\ldots n]$ inductively using the formula $A[1\ldots i] = A[1\ldots (i-1)] \cdot A[i]$. The base case is the empty array $A[1\ldots 0]$.

Having arrays of negative length makes less sense, and could lead to confusion and errors, since there is no semantics under which the formula $|A[i\ldots j]| = j-i+1$ would hold for them, since array lengths are non-negative.


It looks like you are taking the "internal state" as each row in your table from input to s1, all the way to s6. But internal state is defined as from s1 to s6.

So internal state is 7 digits, not 6. And it is:

Row 1 - 000000, output 00
Row 2 - 100000, output 11
Row 3 - 110000, output 10
Row 4 - 111000, output 01

Compare rows 2 to 4 and you can see it matches with what the author wrote.


Difference between Binomial and Fibonacci heap (marking)

In binomial heaps the structure of the trees in the heap is very strict, they all have a number of elements that is a power of two. When a node is removed it is the root of a tree, and all the children (which are again roots trees with a power of two elements) are merged with the other original trees.

There are no nodes that have an "imperfect" number of children, and there is no marking needed to indicate that.


Concrete example of Vertex Cover to Subset Sum reduction

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem...

We do?

  ... mostly to prove Subset Sum is NP-Complete.

There's no particular reason to go down that route. Karp [1] defined the Knapsack problem as: given $a_1, \dots, a_r, b\in\mathbb{Z}$, is there a set $S\subseteq \{1, \dots, r\}$ such that $\sum_{i\in S}a_i=b$? This is one variant of what is now called Subset Sum. If you prefer to define Subset Sum such that $b$  is always zero, we'll come back to that in a minute.

Karp shows that Subset Sum is NP-complete by the chain of reductions
$$\text{SAT}\leq \text{3SAT} \leq \text{Chromatic Number}\leq\text{Exact Cover}\leq\text{Subset Sum}\,.$$
In particular, the reduction from Exact Cover to Subset Sum produces an instance where the $a_i$'s and $b$ are all positive so, if you want to define Subset Sum as "is there a subset whose total is zero?", you can set $a_{r+1}=-b$.

Since Subset Sum and Vertex Cover are both NP-complete, there is clearly a reduction between them. However, you shouldn't expect that there's a "nice" reduction where a small VC instance naturally transforms into a small Subset Sum instance that makes you say, "Aha, now I understand." And that applies to most pairs of NP-complete problems.  In complexity theory courses, we teach the simple, intuitive reductions, usually between problems that are somehow similar, or between SAT or 3SAT and a problem that isn't about Boolean formulas. That can give the impression that there's a natural reduction between any pair of NP-complete problems; in reality, there usually isn't.

[1] Richard M. Karp, Reducibility among combinatorial problems. In Complexity of Computer Computations, Plenum Press, 1972. (PDF)


Proof of the master thorem case with floors and b = 2

In fact, let $b=1.5$, we will have $(1-\frac{1}{b-1})<0$, in which case $(1-\frac{1}{b-1})^{\log_ba}$ does not even make much sense!

The problem can be traced to when the following too-relaxing relaxation was made.

$$1-\frac{b^{j}}{n}\frac{b}{b-1} \geq 1-\frac{b^{\lfloor \log_bn \rfloor -1  }}{n}\frac{b}{b-1}$$

Can we find $\Theta(\log n)$ times when the left side is greater than, for example, $\frac12$? That should be enough to generate the factor $\log n$ needed.

Let us solve the following equation for the index $j$.
$$1-\frac{b^{j}}{n}\frac{b}{b-1} \gt \frac12$$
We get
$$j \lt \log_b\left(\frac{n(b-1)}{2b}\right)=\log_bn-\log_b\frac{2b}{b-1}=\frac{\log n}{\log b}-c_0$$
where constant $c_0=\log_b\frac{2b}{b-1}$.

The above should be enough to set you moving for a complete proof, although there might be a couple of other minor technicalities ahead.


What's the accurate definition of a compiler?

As the comment points out, there's not a formal definition for "compiler", instead it's understood to be that program which translates source code into the target language. Both definitions given are adequate. The definition in Wikipedia is a good one:

In computing, a compiler is a computer program that translates
computer code written in one programming language (the source
language) into another language (the target language). The name
"compiler" is primarily used for programs that translate source code
from a high-level programming language to a lower level language
(e.g., assembly language, object code, or machine code) to create an
executable program.


Am I correct?

Not completely
It is wrong for 2 reasons:

Assembly code is just a human readable version of machine code. So the conversion process to assembly can be skipped if is not required. Unlike other codes, assembly directly corresponds to machine code. Assembly code is dependent on the Instruction Set Architecture of the machine. Converting to assembly is done by the assembler and it is optional. Machine code can be produced without the intermediate assembly code conversion step. As far as hierarchy is concerned, the assembly code and machine code are at the same level.
Machine code is not at a level above Micro code for 2 reasons:

Not all architectures are microcoded. So microcode is optional.
Microcode is independent of the machine code. Machine code corresponds to what the machine does. Micro code corresponds to how the machine does it. Machine code corresponds to the Instruction set. Micro code corresponds to the
micro architecture of the machine. 2 machines having different microcodes can utilize the same machine code if they share the same instruction set architecture.
In fact, Intel corporation sometimes updates the microcode of their processors to patch up vulnerabilities. This is called microcode update. Even after the microcode is updated, the processor can still utilize the same machine code, because the microcode is independent of the machine code. Machine code is not converted to micro code. Both microcode and machine code are sequences of bits. While microcode is optional, machine code is essential.

Is there a level of code below Micro code?

No.

Is hardware control (in logical gates and transistors) code?

No. Code is a sequence of instructions. Hardware is not a sequence of instructions. Hardware is fixed. Code can be modified. Hardware control cannot be reprogrammed, software control can be reprogrammed.


How to build a label flow graph for static analysis

You want to build a graph where the vertices are the set of runtime locations in memory.  Unfortunately, this isn't possible.  The set of runtime locations can be an unbounded set.

For instance, consider code that creates a linked list to hold $n$ data items provided on the input; the number of memory locations is at least $n$, so if the data items are provided on the input, there is no upper bound on the number of memory locations.  Or, consider code like

while (...) {
    char *p = malloc(..);
    ... do something with p ...
    free(p);
}

Each call to malloc() creates a new memory location, so the number of runtime memory locations is at least the number of iterations of the loop.  There may be no fixed upper bound on the possible number of iterations of the loop.

Different static analysis techniques deal with this in different ways:

Data flow analysis typically deals with this by ignoring everything in the heap, and only trying to reason about local variables.  In this way, you obtain a finite graph.
Points-to analysis deals with this using abstraction.  It builds a points-to graph, where each node in the graph corresponds to a potentially unbounded number of runtime memory locations.  At each node in the graph, we record facts that are known to be true for all of the runtime memory locations that correspond to that node.  For instance, we might have one node per malloc() call site.  In other words, we might have a single node for all runtime memory locations that are allocated by any of the calls to malloc() on line 79 (the first call to malloc() on that line, the second call to malloc() on that line, etc.; they're all merged into a single node).

You might want to spend some time reading up on how data flow analysis and points-to analysis work.

More generally, I suggest you ask a new question where you tell us what you're trying to achieve.  Presumably the graph you were talking about was only a means to an end; what was the end goal?  Presumably you wanted to build it only because you thought it'd help you with some task; what is it you really want to learn about the program?  If you ask a new question telling us what your goal is (what you're trying to infer about the program), we might be able to suggest an appropriate static analysis technique that would be suitable for that goal.


I suggest formulating this as an instance of SAT.

You can formulate this as an instance of SAT by thinking of it as trying to color each square in the grid with a color.  For each color, arbitrarily designate one of the two endpoints as the "starting position" for that color, and the other endpoint as the "ending position".  Define boolean variables $x_{i,j,c,k}$, with the intended meaning that $x_{i,j,c,k}$ is true if grid square $(i,j)$ is colored $c$ and is the $k$th square along the path from the starting position for $c$ to the ending position for $c$.

You can write down a boolean formula representing the constraints on the variables $x_{i,j,c,k}$ that must hold, for this to be a valid solution to the puzzle.  For instance:

If $x_{i,j,c,k}$ is true, then either $(i,j)$ must be the end position for color $c$, or else $x_{i',j',c,k+1}$ must be true for some square $(i',j')$ that is adjacent to $(i,j)$.  Moreover, this is true for exactly two squares (not more, not less), unless $(i,j)$ is the starting position, in which case it is true for exactly one square.
For each square $(i,j)$, exactly one of the $x_{i,j,c,k}$ is true.
If $(i,j)$ is the starting position for color $c$, $x_{i,j,c,0}$ is true.  If $(i,j)$ is the ending position for color $c$, one of $x_{i,j,c,k}$ must be true.

And so on.  This ensures that the solution to the formula contains a path that starts at the starting position for color $c$ and ends at the ending position.

Then, feel this boolean formula to an off-the-shelf SAT solver and ask it to find a solution.

This may be an effective solution for the puzzle sizes you mention. I expect it may be more effective than trying to write your own custom rules, as SAT solvers embody many clever strategies built up over decades of research to try to find solutions for these kinds of combinatorial questions.  At least, it should be pretty easy to implement in just a few hours and see how well it works.

Apparently, this puzzle is NP-hard, so you should not expect to find a polynomial-time solution.  This suggests to me that a SAT solver might be a reasonable approach.


As a definition, the input size of a problem is the minimum number of bits $(\{0,1\})$ needed to encode the input of the problem. Since it is given that input length $|\sigma|=m$ , you should have $Ceil ( {\log_2 m}) $ bits to encode $\sigma$.


What is the time complexity of the piece of code given below

The loop executes at most $O(\sqrt n)$ times because i is incremented in every iteration of the loop. You claim that it is also executed at least $\Omega(\sqrt n)$ times. This is not true because it has an early exit (the return statement). For example for even numbers the function returns during the first iteration.

If you recall the definition of $\Omega$, we have $f(n) \in \Omega(g(n))$ if there is some constant $n_0$ such that for all $n>n_0$ we have $c*g(n) < f(n)$ for some constant $c$. By this definition the runtime of your program can't be $\Omega(\sqrt n)$ because the loop makes only one iteration for infinitely many inputs (that is, you can't find a suitable $n_0$).

You can of course restrict your analysis to the worst case ($n$ is a prime number). Then you are correct in saying that the runtime is $\Theta(\sqrt n)$. There is a question about the relation of $O$, $\Omega$, best and worst case in case you find this confusing.


How can solutions of a Diophantine equation be expressed as a language?

The first thing you'll want to do is look at the phrase itself, and ignore all the references to languages for a moment.

So, what are the non-negative solutions to the diophantine equation $3x-y=1$? If we fix some $x$, then $y = 3x-1$. This means that the set of solutions is $\{ (x, 3x-1)\ |\ x > 0 \}$ (note that $x=0$ yields a negative $y$, and a positive $x$ yields a positive $y$).

Now, we can associate a string with any non-negative number pair $(x, y)$: for instance, $(100, 299)$ can be associated with the string (100, 299). If we apply this to every pair in the set, the resulting set of strings is the language of this set. Note that the question does not really make it clear how to associate a string with a solution, but I'm pretty sure they mean the above.

Now all you have to do is figure out in which level of the Chomsky Hierarchy this language falls. As I have a mild suspicion that this is a homework question, I'll not immediately spill the beans. If you can confirm this is not a homework question and you still need help, I'll edit the answer in.


Prove that palindromes are not regular language without using pumping lemma

You can use the Myhill–Nerode criterion.

Suppose that $A$ is a DFA accepting your language. Let $q_n$ be the state which the DFA reaches upon reading the word $0^n1$. As the DFA has finitely many states, we must have $q_n = q_m$ for some $n \neq m$. On the one hand, when at state $q_n$, upon reading $0^n$ the DFA must reach an accepting state, since $0^n 1 0^n$ is a palindrome. On the other hand, when at state $q_m$, upon reading $0^n$ the DFA must reach a non-accepting state, since $0^m 1 0^n$ is not a palindrome. We have reached a contradiction since $q_n = q_m$.


1.-The definition that my teacher told me about CNF: It is a context-free language whose productions are from two types:

Type 1: A−>a|A∈N,a∈Σ

Type 2: A−>BC|A,B,C∈N

Nothing less and nothing more.

2.-You can always simplify a CFL but that is not necessary. At least from a theorycal point of view.

3.-    There isn't best rule. Remove useless production is just a way you can polish your CFL.

It is important to notice that when you have ϵ productions you don't meet the requirements for a context-free grammar so you can't make the conversion to CNF. If you eliminate those productions you are generating a CFG very similar to the original grammar but not equivalent . They denote different languajes although the differences can be considered trivial.

Then you mention "remove unit productions" and "adjust resulting productions" this are the steps of the algorithm to convert a CFG in a CNF.

Polish the grammar could be mandatory in a practical context.

4.- I still don't know anything about Greibach normal form so good luck!


How many edges must a graph with N vertices have in order to guarantee that it is connected?

The formula is worthless without a proof.

Suppose we have a graph on $n$ vertices which is not connected. Then it is possible to divide into two disjoint subgraphs, say one with $i$ vertices and another with $n - i$ vertices. The component with $i$ vertices has at most $i (i - 1)/2$ edges, while the component with $n - i$ vertices has at most $(n - i) (n - i - 1)/2$ edges (this happens when the two components are complete graphs). Therefore we have at most
$$i (i - 1)/2 + (n - i) (n - i - 1)/2 = i (i - n) + n (n - 1) / 2$$
edges. The number of edges has a fixed part $n (n - 1) / 2$ and a variable part $i (i - n)$ which depends on $i$. We would like an upper bound for the variable part. By using the method of completing the square we can write it as
$$i (i - n) = (i - n/2)^2 - n^2/4.$$
As a function of $i$ this is a parabola whose minimum is at $i = n/2$. Thus, to get the largest possible value in the allowed range $0 < i < n$ we should plug in the value of $i$ which is furthest away from the minimum. This happens when $i = 1$ or $i = n - 1$, and both give us the same estimate:
$$i (i - n) = (i - n/2)^2 - n^2/4 \leq (1 - n/2)^2 - n^2/4 = 1 - n.$$
We may thus estimate the number of edges as
$$i (i - n) + n (n - 1)/2 \leq (1 - n) + n (n - 1)/2 = (n-1)(n-2)/2$$
We conclude that the number of edges in a disconnected graph with $n$ vertices is at most $(n - 1)(n - 2)/2$. This is a tight upper bound which is achieved when one of the subgraphs is a point and the other a complete graph on $n-1$ vertices.


Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

You should read up on Patience Sorting first; that's a greedy algorithm to calculate a partition into nonincreasing subsequences (described there as piles of cards). Moreover, the number of subsequences (piles) is minimal.
To prove that, we need to consider two things.
Claim 1: the length of the LIS is a lower bound on the number of piles. That follows from the fact that each of the elements in the LIS must go into a different pile, for if any two elements end up in the same pile, it would no longer be nonincreasing.
Claim 2: the number of piles obtained by Patience Sorting is a lower bound on the length of the LIS. Wikipedia has a proof. To summarize: whenever we place a card C in pile X > 1, we add a pointer from card C to the current top card at pile X - 1 (which is necessarily smaller). If we end up with N piles, we can start at the card on top of pile N, and follow back pointers to construct a strictly increasing subsequence of length N (in reverse).
Combine 1 and 2 to conclude that the length of the LIS is equal to the minimum number of nondecreasing subsequences in the partition (and such a partition is produced by Patience Sorting).
If this is still unclear, there is a similar question about Patience Sort here:
How to prove the optimality of the "patience sort" algorithm?


Exactly how many clocks does a Computer consists of and how do they synchronize with each other?

Modern processors tend to have more clocks than processors in the past, because that means when a part of the processor isn't used, it may be possible to switch off that part completely, including the clock, to save energy.

Clocks are often not synchronised, because synchronising and keeping them synchronised is expensive and complicated, and if you can make a part of the processor work correctly without synchronising its clock, that's overall cheaper.


Thompson's construction, transforming a regular expression into an equivalent NFA

You can do concatenation with an epsilon transition, but it is not necessary. Many implementations avoid it because concatenations are common and the epsilon transitions significantly increase the machine size.

There is some nice code in Russ Cox's famous essay on regular expressions, which implements a common strategy: fragment machines are built without any endpoint. Instead, the fragment descriptor contains a list of states in the fragment which would have a transition to the endpoint if there were one. In this way, two fragments can be concatenated by backpatching the second fragment's start state number as the head (target) of all outgoing transitions from the states in the first fragment's endpoint list.

You will find real code (in C) in the linked essay; search for the heading starting "Implementation"


Does a bitonic sorter compare a pair of elements more than once?

1) yes, the exact same comparison is made, interleaved with other operations. The butterfly network creates tones and checks local and far pairs, after far pairs it still has to apply local ones.

2) The original bitonic sort by Batcher requires the sequence that is a power of two. It makes tones in bitonic sort phase and then bitonic merge phase. The given algorithm introduced dummy nodes (infinite value or maximum that can be stored) for inputs $2^k - c$ and after sorting strips them from result. So the original network uses the number of comparisons equal to the net sorting the next power of two input size. The modifications that use less comparisons are not successful because of environment they run in. While it is possible to avoid not needed comparisons, it introduces branching at higher level (or special blocks, since it is no longer symmetric), to choose what comparator should be used and (in my opinion) is not any more bitonic sort.

You might be interested in more general sorting networks, where the exact number of compares is the subject of creating the sorting net for given $n$. The structure and algorithm depends on number of comparators available. The net is created for exactly given size, and it is not required to be power of two or be even. The optimal networks are found for $n \le 10$.

I recommend Optimal sorting networks by Daniel Bundala and Jakub Závodný about pursuit of better networks (these are general, not bitonic) with algorithmic approach.


Construction of graph with given Wiener Index

This question is addressed on the Wikipedia page Wiener index. Gutman, Yeh and Chen showed that there are no (unweighted) graphs with Wiener index 2 or 5, but all other values are attainable. In a subsequent paper, Gutman and Yeh determine which Wiener indices are attainable on bipartite graphs, and on the way explain how to prove the earlier result, an explanation which we reiterate here.
Consider the clique on $n$ vertices. Its Wiener index is $\binom{n}{2}$. Pick a vertex $v$ from the clique. Suppose we remove $m$ edges $(x_1,y_1),\ldots,(x_m,y_m)$ not adjacent to $v$. Since $x_i,y_i$ are connected via $v$, each edge we remove increases the Wiener index by one, and so the resulting Wiener index is $\binom{n}{2} + m$. The maximal number of edges we can remove is $\binom{n-1}{2}$, which corresponds to a Wiender index of $\binom{n}{2} + \binom{n-1}{2} = (n-1)^2$. We deduce that for every $n$, there are graphs having Wiener index $\frac{n(n-1)}{2}$ to $(n-1)^2$. Let's list these ranges for small $n$, starting with $n = 2$:
$$ [1,1], \; [3,4], \; [6,9], \; [10,16], \; [15,25], \ldots $$
Denoting the intervals as $[a_n,b_n]$, starting with $n=5$ we have $a_{n+1} < b_n$, which is not hard to check directly. Therefore, in this way we can construct graphs of any Wiener index other than $2$ or $5$.
It remains to rule out 2 and 5. First, note that a graph of $n$ vertices has Wiener index at least $\binom{n}{2}$. Since $\binom{4}{2} = 6$, it is enough to consider all graphs on at most 3 vertices:

A path of length 1 has Wiener index 1.
A triangle has Wiener index 3.
A path of length 2 has Wiener index 4.

These are the only connected graphs on at most 3 vertices.


Regular expression for words where the same symbol can repeat at most two times consecutively?

Every string over $\{a,b\}$ can be decomposed into runs of the same letter. For example, $$ abbaabba = a^1 b^2 a^2 b^2 a. $$
Since the alphabet is binary, the runs just alternate between the two letter. In your case, every run has length 1 or 2. We can distinguish between four types of words in your language, depending on which run is first and which run is last; additionally there are some corner cases. The set of words in your language in which the first run is $a$s and the last run is $b$s corresponds to the regular expression $((a+aa)(b+bb))^+$.

I'll let you figure out the rest.


Why all problems are not in P complexity?

Chess is a fixed, finite problem. Because there's no input, you can solve it in a constant amount of time.

Computational complexity considers problems with inputs and looks at how the cost of the computation increases as the input gets longer. For example, you could generalize chess from an $8\times 8$ board to an arbitrary $n\times n$ board and ask how the time taken to compute which side can force checkmate varies as a function of $n$.  Certain versions of this problem (it depends on exactly what rules you take) have been proven to require an amount of time that is exponential in $n$, which implies that they can't be solved in only a polynomial amount of time.


For proof automation in Coq, when is it appropriate to use canonical structures or Equations instead of Ltac?

Choosing how to structure your development based on what proof automation you're using seems backwards.  First you decide what functions and definitions you want to prove theorems about, then you decide what theorems you want to prove, and then finally you decide how to prove them.  Unless you are doing interesting abstract math, it is not until the third step that you should even consider what the proof automaton will look like.

There's an intermediate step, which is deciding how dependently typed to make your code.  Unless you know what you're doing, the first rule of thumb is that you should never combine your proofs and your programs; the proofs must depend on the programs, but the programs must not depend on the proofs.  (The second rule of thumb is that if you do convince proofs and programs, you must never separate them after they are combined, or must never recombine them after they are separated.  This case comes up when formalizing abstract math.)

After you have decided what theorems to prove, now you must decide how to prove them.  This is best done on a whiteboard, or with paper, or talking with colleagues.  There are a couple different kinds of proofs you might be writing:

are you doing very finicky dependent type hackery?  Use Equations or build the proof term yourself.  (This is not entirely fair to equations, but I think it occupies the unfortunate middle ground of being most useful when you have dependent types that are painful enough that you don't want to deal with them manually, but not so painful that it's hopeless to avoid manual labor)
are you writing a well-defined decision procedure?  Use canonical structures if you want something fast, lightweight, easy to do proofs about, but exceedingly hard to debug.  Use MetaCoq if you want something powerful and general.  Use your own custom reflective automation if the generality of MetaCoq makes proving things too painful (I'm not actually sure how much MetaCoq gives you out of the box; it's plausible that proving things in it is quite easy.)
are you performing long complicated chains of reasoning that don't generalize?  Then write your proof by hand (perhaps using ssreflect).  But also reconsider your decisions about what theorems to prove, and maybe include more lemmas.
are you proving things by taking a bag of tricks and throwing them at your problem again and again until it's solved.  You probably want Ltac2 (or Ltac, if you're not ready to use a language still requiring a great deal of polish, and would prefer instead to use a stable language which is overflowing with quirks).  If you have good tactic hygiene, Ltac is not too painful to debug (and Ltac2 is much better).  The rule of thumb when writing tactics is that every tactic should either do one precisely specified thing (these are tactics like destruct, induction, revert, generalize, rewrite, etc), or should be nothing more than "keep repeatedly trying whichever tactics in this bag of tricks work" (tactics like auto, autorewrite, now, easy, done, trivial, etc).  If you have tactics in the middle-ground, that try to apply this bag of tricks then that bag of tricks then this chain of reasoning and then this third bag of tricks, then you will be in for a rough time.


Reduction from NP-complete problem to unknown complexity problem and vice-versa

I shall assume "$\le$" indicates a poly-time, many-one (i.e., Karp) reduction. This seems to be the case since you are referring to NP-completeness.

  If I show that $B \le A$ I can state that A is also NP-complete because the two required conditions are satisfied: (i) A is in NP (ii) i reduced a NP -complete problem to A.

If $B \le A$, that is, $B$ is reducible to $A$, then $A$ is necessarily $\mathbf{NP}$-hard, that is, any problem in $C \in \mathbf{NP}$ is reducible to $A$ (i.e., $C \le A$). This is because any problem $C \in \mathbf{NP}$ is reducible to $B$ (due to the $\mathbf{NP}$-completeness of $B$) and we have $C \le B \le A$; using the transitivity of (this form of) reduction we obtain $C \le A$. However, this does not at all imply that $A \in \mathbf{NP}$—otherwise, any $\mathbf{NP}$-hard problem would be $\mathbf{NP}$-complete! To prove $A$ is $\mathbf{NP}$-complete, thus, you would also have to prove $A \in \mathbf{NP}$ separately.

  If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

$A \le B$ means $A$ is reducible to $B$, which can be reformulated as $B$ being at least as hard as $A$, as you have stated. In no way does this imply that $A$ is $\mathbf{NP}$-complete. Granted, it could be the case, but, for all we know, $A$ could be in $\mathbf{P}$, a regular language, or even trivial (i.e., $\Sigma^\ast$ or $\varnothing$).


How to find the minimum number of vertices whose removal make the graph disjoint

This problem is known as vertex cover.  The minimum vertex cover of a graph is the smallest number of vertices adjacent to every edge.  The complement of a vertex cover is an independent set.

Given a graph $G = (V,E)$ and $k \in \mathbb{N}$, the problem of finding whether $G$ has a vertex cover of size at most $k$ is NP-complete.  However, it admits a polynomial kernel and is thus fixed-parameter tractable.  It also admits a quite easy and nice $2^k n^{O(1)}$ branching algorithm:

Pick any edge $e = vu$:  Either $v$ goes to the vertex cover, or $u$ goes to the vertex cover.  Make a recursive algorithm which picks $e$, removes $v$ from the graph and calls itself recursively with $k-1$ as parameter.  If that fails, proceed by removing $u$.  If that fails as well, can conclude that there is no such vertex cover.

There are also nice 2-approximation algorithms for this problem.

Ps.  this is maybe one of the "easier" NP-hard problems.  So if you want to implement it, you're in good luck despite the hardness.

Pps.  if you want to find an independent set (also known as stable set) of size at least $k$, you are out of luck, as that problem is $W[1]$-complete, see the W-hierarchy.  However, there is an $O(2^{0.288n})$ exact algorithm solving independent set using Measure and Conquer by Fomin et al. (SODA 2006) (doi=10.1.1.79.831).  A quick caveat here:  Many are confused upon first reading why a trivial reduction does not show that independent set is in FPT as well.  The answer here lies in the fact that a reduction will set the new parameter $k' = O(n-k)$, i.e., the new parameter will depend on $n$ as well.


Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors

Divide your original array into $n/\log n$ blocks of length $\log n$. Put each processor in charge of each block, and find the maximum using the usual algorithm in time $\log n$. We now need to compute the maximum of an array of length $n/\log n$. Pair up the elements and compute the pairwise maxima to reduce the size of the array by a half. Repeat it $\log n$ times to find the maximum of the entire array.

The same idea also shows that you can compute the maximum in parallel in constant time using $n^{1+\epsilon}$ computers for every $\epsilon > 0$. (Exercise.)


minimum and maximum nodes of MultiWay tree of height h

This looks correct.

Note that the sum of the geometric series can be expressed more concisely:

$$\sum\limits_{i = 0}^{h} M^{i} = \frac{M^{h + 1} - 1}{M - 1}$$


How to prove that a transformed language is regular using an NFA

Here's how to do it using closure operations; a similar idea can be used for constructing an NFA.

There are three cases to consider. The first case is words consisting only of ones. In this case, we want to transform $1^n$ to $10^n$. We accomplish this as follows. Let $h\colon \{0,1\} \to \{0,1\}^*$ be the homomorphism defined by $h(0) = 1$ and $h(1) = 0$. We capture this part of $\operatorname{plus}(L)$ by the expression $1h(L \cap 1^*)$.

The second case is words of the form $1x01^n$, which should be transformed to $1x10^n$. Here the construction is a bit more complicated. Let $a\colon \{0,1,0',1'\} \to \{0,1\}^*$ be defined by $a(\sigma) = a(\sigma') = \sigma$ (where $\sigma \in \{0,1\}$). The expression $a^{-1}(L) \cap 1(0+1)^*0'1'^*$ replaces $x01^n$ with $x0'1'^n$. To complete the transformation, define $b\colon \{0,1,0',1'\} \to \{0,1\}^*$ by $b(\sigma) = \sigma$, $b(0') = 1$, and $b(1') = 0'$. The expression $b(a^{-1}(L) \cap 1(0+1)^*0'1'^*)$ handles this part of $\operatorname{plus}(L)$.

The final case is the word $0$ (if it is in $L$), which should be transformed to $1$. This is accomplished by $h(L \cap 0)$.

In total, we obtain
$$
\mathrm{plus}(L) = 1h(L \cap 1^*) \cup b(a^{-1}(L) \cap 1(0+1)^*0'1'^*) \cup h(L \cap 0).
$$
Note that any words in $L$ which are not binary encodings (in other words, the empty string and strings with leading zeroes) are just ignored. This can of course be changed if wanted.


NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT

MAX-2-XOR-SAT is a generalization of the more familiar problem MAX-CUT.

To see this, consider a graph $G=(V,E)$. We will have a variable $x_v$ for each $v \in V$, and a constraint $x_u \oplus x_v$ for each edge $(u,v) \in E$. We can identify a cut $S \subseteq V$ with a truth assignment by $S = \{ v \in V : x_v = 1 \}$. You can then check that the number of clauses satisfied is exactly the same as the number of edges cut by $S$.


Benefit of Backward Pass at compile time

Many major compiler optimizations use backward passes.  For example, computing liveness information, which is used to do dead code elimination, usually requires a backwards pass over the CFG of a program in order to identify unnecessary statements.  Partial redundancy elimination, a powerful algorithm for eliminating redundant computation or rearranging code, consists of two forward passes combined with two backward passes to determine what expressions are available (forward), what expressions are anticipated (backward), etc.

Hope this helps!


Finding the smallest positive missing number in array of integers contains negative and duplicates number

The solution has two parts. The first part filters out all non-positive numbers - this can be done in-place using the partition subroutine of quicksort.

After the first part, we have an array $A[1],\ldots,A[n]$ of positive numbers, and we want to find the smallest positive integer which is not present. We create a new Boolean array $B[1],\ldots,B[n]$ initialized to false. We go over all elements in $A$, and whenever we find an element $i \leq n$, we set $B[i]$ to true. We then find the smallest index $i$ such that $B[i]$ is false - this is the smallest positive integer which is not present. If all elements of $B$ are true, then $n+1$ is the smallest positive integer not present (why?).

As an optimization, we store the array $B$ by modulating the sign of elements in $A$: to represent $B[i]$ being false we use a positive sign for $A[i]$, and to represent $B[i]$ being true we use a negative sign for $A[i]$.


The seed is an initial number of the pseudorandom number generator(PRNG) which is in fact fully deterministic. It returns a sequence of numbers that looks random enough for many purposes, but always generates the same sequence for given value.

In order to make simulation non-repeatable (returning always the same value) they advice different initial value for every simulation (this is what non-fixed seed means).

Image taken from here


When you are stuck in a place like this, it pays to check if the method can work at all. That is, try to prove the opposite. Since the Pumping lemma does not characterise REG, this is actually possible.

Claim: Your language $L$ fulfills the conditions of the Pumping lemma with $p=1$.

Let $w = uu^Rv$ for $u, v \in \Sigma^+$; say $|w|=n$ and $|u|=m$. With the (canonical) notation from the Pumping lemma, pick $x = \varepsilon$, $y=w_1$ and $z = w_2\cdots w_n$.

By definition, $|y| \geq 1$ and $|xy| \leq p$. Furthermore,

$xy^0z = (u_2\cdots u_m) \cdot (u_2\cdots u_m)^R \cdot u_1 v \in L$,
$xyz = w \in L$, and
$xy^iz = u_1 u_1^R (u_2 \cdots u_m) u^R v \in L$, for $i \geq 2$.

Q.e.d. -- $L$ has the Pumping property.

That is, the Pumping lemma can not be used here, you need other methods.


How to represent/implement the hypotheses class for a DAG learner

OK here is what I did:

I read about the most specific $ms$ and most general $mg$ hypotheses here. Intuitively, the hypotheses class is defined as these two hypotheses and anything in between.  That is, for a hypothesis $h$ with DAG $G_h$, in order for $h$ to be in the hypotheses class $H$, it must be the case $G_{ms}\subseteq G_h \subseteq G_{mg}$.

For now, I used only $ms$ since my problem transformed to learning only one labelling $\{+\}$.  Initially $G_{ms}=\emptyset$. Every example $x$ consist of pair of vertices $(x[a],x[b])$. if $\zeta(x)=\{+\}$ then there is an edge from $x[a]$ to $x[b]$ in $G_{ms}$ where $\zeta(x)$ is the labelling of $x$ according to the target function $h^*$.

After seeing $i$ examples $G_{ms}$ has $i$ edges. Any hypothesis $h$ with $G_{ms}\subset G_h$ is included in my hypotheses class $H$.


All nearest neighbor in a changing 2d euclidean space

You want a data structure that supports nearest neighbor search in 2D.  There are many options, but a simple one that is widely used for practical situations is a quadtree data structure.  It supports both efficient lookup and efficient insert operations.


This link confirms my intuition that $L(R)$ where $R$ is a regular expressions simply means "the language produced by the regular expression $R$".

In that case, $ab \in L_2$ but $ab \notin L_1$

In case link is down:

Operators used in regular expressions include:

Union: If R1 and R2 are regular expressions, then R1 | R2 (also written as R1 U R2 or R1 + R2) is also a regular expression.
L(R1|R2) = L(R1) U L(R2).

Concatenation: If R1 and R2 are regular expressions, then R1R2 (also written as R1.R2) is also a regular expression.
L(R1R2) = L(R1) concatenated with L(R2).

Kleene closure: If R1 is a regular expression, then R1* (the Kleene closure of R1) is also a regular expression.
L(R1*) = epsilon U L(R1) U L(R1R1) U L(R1R1R1) U ...


Are run time bounds in P decidable when the problem is promised that an input program must halt?

Given a Turing machine $T$, construct a new Turing machine $T'$ which, in input of length $n$, simulates $T$ for up to $n$ steps. If $T$ halts then $T'$ also halts, and otherwise $T$ counts up to $2^n$ and then halts.


Can the regular image of a context-free language be undecidable?

If $L_1$ is context-free, then so is $L_2$. You can show this easily using closure properties of context-free languages. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$; we assume that $\Sigma$ and $\Sigma'$ are disjoint. Define a homomorphism $h\colon \Sigma \cup \Sigma' \cup \{|\} \to \Sigma^* \cup \{|\}$ by $h(\sigma) = h(\sigma') = \sigma$ and $h(|) = |$, and a homomorphism $k\colon \Sigma \cup \Sigma' \cup \{|\} \to \Sigma^*$ by $k(\sigma) = \sigma$ and $k(\sigma') = k(|) = \epsilon$. Then
$$
L_2 = k(h^{-1}(L_1) \cap \Sigma^{\prime\ast} | \Sigma^*).
$$
The family of context-free languages is closed under homomorphisms, inverse homomorphisms, and intersection with regular languages, hence $L_2$ is context-free as well.


Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$?

No, it is not sufficient to say "let $d(n) = n$ which is $O(f(n))$. Therefore $ad(n) = an$ which is trivially $O(f(n))$". Although that is a reasonable way to to understand the proposition quickly, it is neither sufficient nor necessary. It cannot be considered as a proof. It can easily lead to misunderstanding if communicated.

To show that "if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$", let us apply the relevant definitions.

$$\begin{align*}
d(n)\text{ is }O(f(n))
&\Longrightarrow \limsup_{n\to\infty}\dfrac{|d(n)|}{f(n)} <\infty\\
\left(\text{since } \limsup_{n\to\infty}\dfrac{a|d(n)|}{f(n)}=a\limsup_{n\to\infty}\dfrac{|d(n)|}{f(n)}\right) &\Longrightarrow\limsup_{n\to\infty}\dfrac{a|d(n)|}{f(n)} <\infty\\
&\Longrightarrow\limsup_{n\to\infty}\dfrac{|ad(n)|}{f(n)} <\infty\\ &\Longrightarrow ad(n)\text{ is }O(f(n)).\\
\end{align*}$$

The proof above is rigorous, although it is hardly the way we as humans understand the proposition. Here is another approach.

$$\begin{align*}
d(n)\text{ is }O(f(n))
&\Longrightarrow |d(n)|\text{ is bounded above by } cf(n)\text{ when $n$ is large enough for some constant } c\\
&\Longrightarrow |ad(n)|\text{ is bounded above by } acf(n)\text{ when $n$ is large enough for some constant } c\\
(\text{let } c'=ac)\ \ &\Longrightarrow |ad(n)|\text{ is bounded above by } c'f(n)\text{ when $n$ is large enough for some constant } c'\\
&\Longrightarrow ad(n)\text{ is }O(f(n)).\\
\end{align*}$$

The approach above can be considered as a proof among people who are familiar with the stuff. It is probably the way to understand the proposition as well. You can imagine that the graph of $cf(n)$ lies above the graph of $d(n)$, and, hence, the graph of $acf(n)$ lies above the graph of $ad(n)$.


Using software to calculate the complexity of an algorithm

Depending on your background, the CLRS book is a solid introduction. I think in the very first chapter, they walk you through of how to analyze a simple algorithm in terms of both correctness (showing the algorithm really solves the problem) and complexity (how many steps the algorithm performs). There are lots of other books out there some other people might prefer more.

In general, there is no software that does this for you. Coming up with right invariants etc. is somewhat of an art requiring insight and experience. Read more about complexity theory, and you'll discover some inherit impossibilities and problems related to automating such analysis.


Yes, the running time is $O(U+n)$, assuming that each iteration of the inner loop takes $O(1)$ time.  The way to prove it: try to write down an expression for the running time, as a function of $U$ and $n$.  What did you get?  Now, see you can show that this expression is at most $c \cdot (U+n)$, for some constant $c$ that you get to specify.


Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

$\{ww\mid w\in\{0,1\}^*\}$ not being context-free does not imply every subset is also not context-free. In this case, $0^n1^n0^n1^n$ passes the pumping lemma, since it can be written as follows $0^p1^p0^p1^p=0^p1^{p-1}1^n0^n0^{p-1}1^p$.


Are there any algorithms or data structures that need to find the median value of a set?

if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement

The application of this algorithm is trivial - you use it whenever you want to compute a median of a set of data (array in other words). This data may come from different domains: astronomical observations, social science, biological data, etc.

However, it is worth mentioning when to prefer median to mean (or mode). Basically, in descriptive statistics, when our data is perfectly normal distributed then mean, mode, and median are equal, i.e. they coincide. On the other hand, when our data is skewed, i.e. the frequency distribution for our data is (left/right) skewed, the mean fails to provide the best central location because the skewness is dragging it away from the typical value to left or right, while the median is not as strongly influenced by the skewed data, and thus best retains this position pointing to a typical value. Thus computing a median might be preferable when you deal with skewed data.

Also, machine learning is where statistical methods are heavily used, for example $k$-medians clustering.


Matching vertex values with sum of edge weights on bipartite graph

I've got bad news.  There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely).

Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary.  The knapsack problem has a pseudopolynomial time algorithm, which means that there is an algorithm whose running time is polynomial in the numbers (but not polynomial-time in the size of the input).  In your setting, that turns into an algorithm whose running time is polynomial in the size of the unweighted graph (with a massive number of edges) but not polynomial in the size of the weighted graph (with a small number of edges).

You could try expressing this as an integer linear programming (ILP) instance, and then solve with an ILP solver.  It's possible that might yield a more efficient solution.  The core idea is to introduce an integer variable $x_{i,j}$ that counts the number of impressions provided to company $i$ in tag $j$; then you can introduce a few linear inequalities to capture the problem's requirements.


The binary expansion of $2^n-1$ consists of $n$ ones. This is because the binary expansion of $2^n$ consists of a one followed by $n$ zeroes. This is similar to $10^3-1 = 999$ in decimal.

If we want these $n$ bits to be the left $n$ bits out of $m$ bits, then we need to add $m-n$ zeroes to the right. This is the same as multiplying everything by $2^{n-m}$. Compare $100 \cdots 54 = 5400$. This operation is usually known as left shift, and many languages support it natively. For example, in C you would use the following code to generate the mask:

  ((1 << 24) - 1) << (32-24)


What is the fastest to find just smallest prime number to a given number N where N can be as large as 10^18?

By fast primary testing you can test whether a given number is probably prime or not, actually methods like Miller Rabin are very fast and because we know the gap of size $O(\log n)$, between two consecutive primes, you can expect that when you start from $N$, you should visit few numbers by fast primarily testing, also, in most cases, fast primarily testing algorithms for the range you mentioned are correct.

In your case, because your numbers are bounded just few composite numbers can pass the miller rabin test which are:

2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321

You can see them in this list, So you just need to check the number that passed the Miller Rabin test, is in above list or not, and by using this code, is possible to do it in less than a second.


The Gas Station Problem - fast implementation

Your recurrence relationship isn't quite right -- you need to relate the input parameter f to f1 and f2 somehow.  I think you can get rid of f2 completely:

checkTank(f) = if f <= U then f else INF
D[v][f] = min(u, f1 | u->v in Edges and f1 in 0..tankCapacity)
             { D[u][f1] + checkTank(f - f1 + distance(u, v)) * fuelRate[u] }

Entries D[v][f] for values of f which would imply putting more gas in the tank than it can hold will correctly get assigned INF by the above.  (Here I assume that adding any nonnegative value to or multiplying any positive value with INF yields INF again; in an actual implementation you might want to specially check and avoid further processing of such values.)

But in any case, the algorithm in the paper is fast because they exploit a dominance rule (Lemma 2.1) that implies that an optimal solution can always be found even if you only look at O(n) particular different gas tank levels at each node, and you aren't making use of that here.  If you don't make use of that same property, I think your algorithm will be at best pseudopolynomial (they say this in the paper; BTW that doesn't necessarily make it a terrible algorithm in practice) and in effect usable only with integer-weight fuel amounts.

Regarding adding the missing edges: For the case where you don't limit the number of stops, the running time is O(n^3), so it's safe to run Floyd-Warshall at the beginning to calculate the minimum path distance between all pairs of vertices that lack an edge, as it's also only O(n^3) and therefore doesn't increase the running time asymptotically.

At first glance it seems possible to accept an incomplete graph, and allow "fill stops" at which 0 fuel is filled.  But this invalidates Lemma 2.1, since now there can be graphs in which an optimal path involves filling up less than the full amount at some node w, before travelling to some node u with higher cost, "filling up" with 0 fuel there, and then travelling on to reach (on an empty tank) some other node v with cheaper fuel than w.  You can play around with Lemma 2.1 to allow arbitrarily long strings of special "0-fill" stops between "real" stops, and this works, but it doesn't buy you anything: for each vertex u, instead of having to consider all possible neighbours w of u and their distances d(w, u) to u, you'll have to consider all possible vertices w and the lengths of their shortest paths to u, which means that you might as well calculate them all at the start and make edges with their weights.

Finally you can discard/ignore/avoid calculating any edges longer than U or which violate the Triangle Inequality (in fact these constraints also apply to any edges already in the original graph).


Why is the log in the big-O of binary search not base 2?

When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with respect to their asymptotic behavior.

For example
$$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ where
$C = \frac{1}{\log_{2}10}$.

So $\log_{10}n$ and $\log_{2}n$ differs by a constant $C$, and hence both are true:
$$\log_{10}n \text{ is } O(\log_{2}n)$$
$$\log_{2}n \text{ is } O(\log_{10}n)$$
In general $\log_{a}{n}$ is $O(\log_{b}{n})$ for positive integers $a$ and $b$ greater than 1.

Another interesting fact with logarithmic functions is that while for constant $k>1$, $n^k$ is NOT $O(n)$, but $\log{n^k}$ is $O(\log{n})$ since $\log{n^k} = k\log{n}$ which differs from $\log{n}$ by only constant factor $k$.


For a Turing Machine $M_1$, how is the set of machines $M_2$ which are "shorter" than $M_1$ and which accept the same language decidable?

$L_{M_1}$ is in $R$ simply because the number of machine descriptions smaller than a given machine description is finite and any finite language is in $R$.


$c=5$ is clearly the wrong answer, since for any $n$,
$$cn^3 < 5n^3 + \text{(positive terms)}$$

However, if we take $c>5$ then there will exists some $N_0$ such that for $n>N_0$
$$cn^3 \ge 5n^2+2n^2+22n+6$$

If we let  $g(n)=(c-5)n^3-2n^2-22n-6$, then Since $\lim_{n\to\infty} g(n)=\infty$,  by the limit definition there always exists $N_0$ such that for any $n>N_0$, $g(n) >0$. This implies the above claim.

To find that $N_0(c)$ you can try to find the roots of $g(n)$. $N_0$ will be the most positive root.


Are there any decision complexity classes which have no "complete" subclass?

Apart from the many answers from the Mathoverflow link commented above by Ariel, we have a very simple example as follows.

Under widely accepted conjecture that $\mathrm{P}\neq \mathrm{NP}$, we have that $\mathrm{NP}\setminus \mathrm{NP}$-$\mathrm{complete}$ does not have complete problem and therefore the "hard" part of it is well "above" it.

For the proof, use Ladner's result on $\mathrm{p}$-degree, for any two different $\mathrm{p}$-degrees $\mathrm{A}$ and $\mathrm{B}$, if $\mathrm{A}<_p\mathrm{B}$, then there must exist another $\mathrm{p}$-degree $\mathrm{C}$ in between: $\mathrm{A}<_p\mathrm{C}<_p\mathrm{B}$. So by removing $\mathrm{NP}$-$\mathrm{complete}$ from $\mathrm{NP}$, every $\mathrm{p}$-degree below the complete degree always has another non-complete degree above it.


Evaluating the average time complexity of a given bubblesort algorithm.

Recall that a pair $(A[i], A[j])$ (resp. $(i,j)$) is inverted if $i < j$ and $A[i] > A[j]$.

Assuming your algorithm performs one swap for each inversion, the running time of your algorithm will depend on the number of inversions.

Calculating the expected number of inversions in a uniform random permutation is easy:

Let $P$ be a permutation, and let $R(P)$ be the reverse of $P$. For example, if $P = 2,1,3,4$ then $R(P) = 4,3,1,2$.

For each pair of indices $(i,j)$ there is an inversion in exactly one of either $P$ or $R(P)$.

Since the total number of pairs is $n(n-1)/2$, and the total number and each pair is inverted in exactly half of the permutations, assuming all permutations are equally likely, the expected number of inversions is:

$$\frac{n(n-1)}{4}$$


Counting with constant space bounded TMs

Let me give an explanation which does not differ in content from the accepted answer, but brings the question back to the realm of regular languages.

The language you are dealing with can be defined as follows. Let $s \in \Sigma^{\mathbb{N}}$ be a (countably) infinite string of symbols from some finite alphabet $\Sigma$, and let $s[1:i]$ be the prefix of the first $i$ symbols in $s$. In your case $s$ is the input and and $\Sigma$ is the nonnegative positive integers $\{0, \ldots, 60000\}$. $L(s)$ can be defined as a language of triples $(s[1:i], a, j)$ where $(s[1:i], a, j) \in L(s)$ if and only if there are $j$ occurrences of $a$ in $s[1:i]$. Convince yourself, using the pumping lemma, that for any fixed $s$, $L(s)$ is not regular. Then convince yourself that if a bounded memory Turing machine could solve your problem, it could also recognize the non-regular language $L(s)$. This argument ought to work even if we fix $a$ and define a similar language $L(s, a)$.

These kinds of examples are the reason why our computational model of choice (our = the algorithms community) is the word RAM machine, and we assume that word size grows with input size. This is supposed to model the fact that as the instances we face in reality grow, so does the memory of our computers. Of course, at some point we'll face physical limits of the hardware: there is only so much memory that can be accessed fast by a single/finitely many processors. One way to go beyond these limits is memory hierarchies and the modeling becomes more complicated, but there is some very nice theory as well (see external memory models and cache-oblivious algorithms).


Is this applet implementation for the Go-Back-N ARQ protocol correct?

I'll address question 2 first, since it seems easier than the other one.  The answer is simply because both transmitters begin tagging their payload messages from 1, namely with nextseqnum = 1; you can see this is so for the sender from the top-left corner of the image you posted.  Don't be misled by the fact that the receiver issues the sndpkt = make_pkt(0, ACK, checksum) at the outset; that first packet is only crafted, but not sent (it would if the receiver hit the default state).  On the other hand, there might be an inconsistency in the way the applet enumerates its packets, since it starts from 0.

Question 1 seems to ask: if a sequence of packets 0, 1, 2 is sent and

Packet 1 is lost
A new packet, 3, is sent just before the timeout

then no timeout occurs, although no instruction seems to be encoding for that.  Although I counted the passing of time with my hands, your observation seems to be correct: given the above conditions, upon sending a new packet, the events associated with a timeout do not manifest.  This could be due to a small bug in the applet, although I would ascertain more before contacting the book authors.

which contradicts the fact that time is only get reseted when base = nextseqnum?

Beware! The timer is also reset upon receiving an acknowledgement that is not the last one, as shown at the bottom of Figure 3.20.  However, I do not think your experiment is affected by this behavior since the triggering conditions aren't met.


I'm assuming that your code works in the following way:

The input is an $n \times m$ bit matrix.
You add a parity bit to each row, chosen so that the parity of the new row is even.
You add a parity bit to each column, chosen so that the parity of the new column is even.
You end up with an $(n+1) \times (m+1)$ bit matrix in which the parity of each row and column is even.

Suppose now that between 1 and 3 errors occurred. There must be either a row or a column in which exactly 1 error occurred (I'll let you figure out why). This row or column will have odd parity, and so you will be able to detect that an error occurred.


Proving the set of finite languages is countable without using the union of countable sets

Let your finite alphabet be $\Sigma = \{a_1, \dots, a_\ell\}$ and let $\#$ be some character not in $\Sigma$. Let $L=\{w_1, \dots, w_n\}$ be a finite language over $\Sigma$. You can consider the string $\#w_1\#w_2\#\dots\#w_n$ to be a number in base $|\Sigma|+1$ by associating the symbols $a_1, \dots, a_\ell, \#$ with the base-$(|\Sigma|+1)$ digits $0, \dots, \ell-1, \ell$, respectively (starting the string with $\#$ ensures that the leading digit isn't zero). This gives a map from the set of finite languages over $\Sigma$ to a subset of the integers, so that set of languages is countable.


What is a proof of normalization of Morte?

I'm afraid there is no simple proof of the normalization for the CoC, as it implies the consistency of a very strong form of logic.

A good reference is Geuvers, A short and flexible proof of strong normalization for the calculus of constructions.

The intuition of the proof is hard to convey, but basically it is shown that for each type $T$, there exists a notion of "term computable at type $T$", which is a predicate, intuitively a subset of the set of $\lambda$-terms. A computable term has good properties, in particular it is always normalizing. Building this notion of computability involves building a kind of model for the CoC, often called a realizability model.

Then it is shown that any well typed term $t:T$ is computable at type $T$.


How to propose a method to construct an automaton?

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

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

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


Is there a clear definition of "computable" for models of computation which are not turing complete?

Some basic fact that you are missing here is that all the encodings that you mention are equivalent from the perspective of computability: there is a computable function mapping the binary encoding of a number to its unary encoding, or vice versa. Therefore for the sake of defining computability, it does not matter which of these encodings you choose for numbers. Just fix your favorite encoding.

Computability is at its core a property of string functions $f\colon \Sigma^* \to \Sigma^*$. When you define computability in any other domain, you have to fix an encoding. In practice, all "reasonable" encodings are equivalent in the sense of the preceding paragraph, so the exact encoding doesn't matter.

The encoding does, however, matter in restricted models of computation. To take an extreme example, suppose that you consider time-restricted Turing machines: say you want your machine to terminate in time $O(n^c)$ for some $c$, where $n$ is the length of the input (as a string). We can no longer switch between binary encoding and unary encoding, because binary encoding is much more compact. When we talk about a polynomial time computable function of integers, we specify that integers are encoded in binary. Even this is a somewhat arbitrary choice, since decimal encoding would lead to the same notion of polynomial time computability.

So to answer your question – the encoding is specified as part of the definition of the restricted model.


Languages accepted by modified versions of finite automata

This combined with Alex's answer give the complete picture.

$L(DDFA)\subseteq L(DFA)$ can be proven by adapting the usual powerset construction with a modified final state condition. In the power set construction, states are sets of states from the original automaton. Usually after performing the powerset construction, a state is final if one of the states in the set is final in the original automaton.

In type-1 DDFA, final states in the constructed automaton are the sets where all elements are final in the original automaton.
In type-2 DDFA, final states are the singleton sets of the final states from the original automaton.

In both cases, the resulting automata are DFAs.

Now type-2DDFA's can express only the languages $\{\epsilon\}$ and $\emptyset$, depending on whether the starting state is accepting or not. This is because the two transitions from a state need to go to distinct states, but acceptance is only possible if they end up on the same state.