For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not.

In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that includes every vertex exactly once, and which therefore doesn't repeat any edge. That's just the definition; it's a problem about graphs and it may or may not correspond to any particular problem in the real world.

In TSP, we are given the cities and the matrix of distances between them. That's all the values are: distances. In particular, there is a distance between every pair of cities, regardless of what the road network looks like. You need to visit each city and your job is to choose the order in which to visit them, to minimized the total journey length. For example, consider the following distances:

                 B    P    W
Baltimore        -   100   40
Philadelphia    100   -   140
Washington DC    40  140   -

The shortest route is to, say, start in Philadelphia, drive to Baltimore, drive to DC, then drive back to Philadelphia.  If the distances look a bit strange, it's because I-95 runs from Philadelphia to DC and passes through Baltimore.  This means that "then drive back to Philadelphia" means passing through Baltimore again. This doesn't matter, because TSP isn't modelling that. It's just modelling visiting each city and completely ignores what happens en route between cities, except for the distances.

In contrast, if you represented this as the graph

    40       100
W ------ B ------- P

then there is no Hamiltonian cyle at all.  This doesn't correspond well to the idea of travelling between cities: as you rightly ask, why not allow yourself to drive back through Baltimore?  Should we add in a road from Washington to Philadelphia that doesn't go via Baltimore? That seems weird, as it would be longer. Why force yourself to do that? TSP isn't Weighted Hamiltonian Cycle.

The formal relationship between the two problems is that TSP is the restriction of weighted Hamiltonian path to the case where the graph is complete.  Alternatively, you can associate a weighted Hamiltonian path instance as corresponding to the TSP instance where there's one city per vertex and the distance between two cities is the length of the shortest path between the corresponding vertices.

Note that, in the above, I've referred to the "distance" between cities.  Even more formally, one should talk about an abstract "cost".  The distinction is that distance sounds a lot like it ought to be symmetric and obey the triangle inequality, which corresponds to metric TSP. Cost isn't necessarily either of those things.


The underlying principle is that the definitions of small o and big O are different.

Big O definition

$O(f(n)) = \{g(n) | \exists c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) \leq c*f(n)\}$

In words:

$g(n)$ is an element of $O(f(n))$ if there exists a $c > 0$ and a $n_0 > 0$ such that for all $n > n_0$, $0 \leq g(n) \leq c*g(n)$

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 20$, $n_0 = 1$, you can check that for all $n > 1$, $0 \leq 10n^2 \leq 20*n^2$, so $10n^2 \in O(n^2)$

Small O definition

$o(f(n)) = \{g(n) | \forall c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) < c*f(n)\}$

In words:

$g(n)$ is an element of $o(f(n))$ if for any $c > 0$, there exists a $n_0 > 0$ so that for all $n > n_0$, $0 \leq g(n) < c*f(n)$.

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 1$, you can check that there is no $n_0 > 0$ so that for all $n > n_0$, $0 \leq 10n^2 < 1*n^2$

Therefore the condition does not hold and $10n^2 \notin o(n^2)$.

Informal explanation

$g(n) \in O(f(n))$ if $g(n)$ grows slower than or in the same fashion as $f(n)$.
$g(n) = 10n^2$ grows in the same fashion (quadratically) as $f(n) = n^2$, so $10n^2 \in O(n^2)$.

$g(n) \in o(f(n))$ if $g(n)$ grows strictly slower than $f(n)$.
$g(n) = 10n^2$ grows in the same fashion and thus not strictly slower than $f(n) = n^2$, so $10n^2 \notin o(n^2)$

NOTE: I've used notation like $10n^2 \in O(n^2)$ because the definitions were actually sets. But in practice, there's accepted notation abuse and $10n^2 = O(n^2)$ is written instead.


Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

Let $n$ be the length of a string. We start with the (non-terminal) symbol $S$ which has length $n=1$.

Using $n - 1$ rules of form $(non-terminal) \rightarrow (non-terminal)(non-terminal)$ we can construct  a string containing $n$ non-terminal symbols.

Then on each non-terminal symbol of said string of length $n$ we apply a rule of form $(non-terminal) \rightarrow (terminal)$. i.e. we apply $n$ rules.

In total we will have applied $n - 1 + n = 2n - 1$ rules.

example

Observe following grammar in Chomsky-normal form.

$
\begin{align}
S & \to AB \\
A & \to BC | AC\\
A & \to h|b\\
B & \to a \\
C & \to z \\
\end{align}
$

Consider following derivation

$
\begin{align}
\text{Current string} & & \text{rule applied} & & \text{#rules applied} & & \text{#length of string} \\
S & & \text{\\} & & 0 & & 1 \\
AB & & S \to AB & & 1 & & 2 \\
BCB & & A \to BC & & 2 & & 3 \\
\vdots & & \vdots & & \vdots & & \vdots \\
A\cdots CB & & \text{[multiple rules]} & & n-1 & & n
\end{align}
$

This last line represents a string containing only non-terminals. You can see that a string containing $n$ non-terminals is derived using $n-1$ rules. Let's continue. Applying $n$ rules of form $A \to a$ to each non-terminal in the string above gives you a string containing only terminals and thus a string from the language decided by the grammar. The length of the string has not changed (it's still $n$) but we applied an additional $n$ rules so in total we have applied $n-1 + n = 2n - 1$ rules.

While this explanation hopefully gives you an intuitive understanding, I think it would be an useful excercise to construct a formal proof using induction.


Program to check whether a string is accepted by an unrestricted grammar

Unfortunately, you cannot.

Nobody can since the membership problem for unrestricted grammar is undecidable. Here is a reference in Wikipedia.

On the other hand, the membership problem for context-sensitive grammar or, what is equivalent, noncontracting grammar is decidable. 1

Just in case it is not clear to you, a collection of decision problems (a.k.a, yes/no questions) is decidable if there is a program which will solve any given one of them correctly within finitely many steps. It is undecidable if there is not such a program.
The existence of undecidable problems could be the best technical backdrop for this story.

You will learn its formal definition in your study of computer science (or you might have). There will be lots of undecidable problems coming to you; so if you suspect one, you should probably wait until you have studied the chapter about undecidability and somewhat more before you raise a similar question. Or you could just search around using the keyword "decidable" or "undecidable"


You can prove it by contradiction:

Suppose that $P \neq NP$ and there is a polynomial-time reduction from 3-SAT to 2-SAT; then 2-SAT is NP-complete, but 2-SAT is also solvable in polynomial time, so
for all decision problems $A \in NP$ you can decide $x \in A$ reducing $x$ to the corresponding 2-SAT instance in polynomial time and solve it in polynomial time (and the total time is still polynomial); so $A \in P$ and hence $NP \subseteq P$. But we also have $P \subseteq NP$, so $P = NP$ which is a contradiction. :-)


Since big O is only an upper bound, you cannot really tell which algorithm is faster. Let us therefore assume that the running times of the two algorithms are actually $\Theta(n+m)$ and $\Theta(nm)$. Since your graphs are all connected, you have $n-1 \leq m \leq \binom{n}{2}$, and so the first algorithm runs in time $\Theta(m)$ and the second in time $\Omega(m^{1.5})$. This shows that as $m\to\infty$ (equivalently, as $n\to\infty$), the first algorithm is asymptotically faster.


See for instance this book: Lattice Theory with Applications, Vijay K. Garg, which starts off as follows:

  Partial order and lattice theory now play an important role in many disciplines of computer science
  and engineering. For example, they have applications in distributed computing (vector clocks,
  global predicate detection), concurrency theory (pomsets, occurrence nets), programming language
  semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other
  disciplines of mathematics such as combinatorics, number theory and group theory. In this book,
  I introduce important results in partial order theory along with their applications in computer
  science. The bias of the book is on computational aspects of lattice theory (algorithms) and on applications (esp. distributed systems).

The book doesn't seem to mention recursion theory (theory of computable sets), but from Wikipedia's article on Computability theory, we see:

  When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

Further reading, see the blog post Lattice Theory for Programmers and Non Computer Scientists.


Are supersets of non-regular languages also non-regular?

Since this holds for all $x\in L_1$, we can construct a finite automata which language is $L_1$.

And how would you do this? You have an infinite amount of paths in hands which you have to mold into a finite set of states and edges.

In fact, the statement does not hold.

   Remember that $\Sigma^*$ is regular but there are non-regular languages.


Question on an Algorithm for Longest Increasing Subsequence

Update:
I have thoroughly read through the paper myself and understand the problem better. So the algorithm fails if I make the above deletion (i.e. removing elements from a boundary layer). Layers $L_i = \{a_j | b_j = i\}$ are only for initialization, and for the duration of the algorithm, only the boundary layers are kept in tact to calculate one of the local data structure (which assumes the boundary layers are unchanged). This is a probabilistic algorithm and the paper show that we can get success rate to $1-n^{-10}$ after $20\log n$ repeats.


Is there a faster solution for the Google Code Jam Great Wall Problem

The obvious room for improvement is this step:

  Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A\log A)$

We know that the tribes will attack from a particular day, in regular intervals. That means we should be essentially merging lots of pre-sorted lists. Also the problem statement tells us that there will never be more than 1,000 tribes (i.e. 1,000 lists to merge); a tiny number compared with the 1,000,000 maximum attacks! Depending on your implementation's relative timings, switching this could cut the processing time in half.

That's really all I can suggest for optimising the theoretical complexity, but I have no proof that it would be optimal after this change.

I gave the puzzle a go myself, but I used a much dumber representation of the wall: a binary search tree (C++'s std::map to be precise) storing locations where the wall's height changes. With this, I was able to add and removed nodes as required (i.e. if a complicated section was subject to a large, overwhelming attack, or multiple attacks of the same strength touched, the number of nodes would reduce significantly). This solved the large input in 3.9 seconds (on my mid-spec development laptop). I suspect there are several reasons for the improvement:

As you pointed out, boxing and unboxing can get expensive, but C++'s template-based containers avoid this entirely.
While the wall representation I used is theoretically worse, in the vast majority of cases being able to dynamically reduce the number of nodes made it super-fast (most test cases maxed-out at under 1k nodes, and all but 2 were under 10k). In fact, the only case which took any significant time was #7, which seems to have been testing lots of non-intersecting ranges.
I used no pre-processing (stages are determined by keeping track of when each tribe will next attack, and searching for the joint-lowest each turn). Again this is theoretically worse, but for the majority of cases I suspect the lower overhead means it was faster (I'll test this and get back to you). Update: I added a priority queue for attacks, similar to the method described above (although instead of creating the large array I calculated it on-the-fly) and saw the time decrease to 3.0 seconds for the large input.

In short, while I think your algorithm is near-optimal in the general case, there are several ways you could speed it up for typical inputs.


Exponential reduction vs Polynomial Reduction

In fact, depending on the class you want to reduce to, you need to be careful about the reduction you are doing.

For instance to preserve the class $P$, you need to do $LOGSPACE$-reductions.
For the class $NP$, you need $P$-reductions.

I'm also afraid that you reverse the reductions: to show that a problem $B$ is in $NP$, you need to reduce it (polynomially) to a problem $A$ in $NP$. Meaning that if you to how to solve $A$ in $NP$, then you can solve $B$ by reducing it to $A$.

So to sum up, if $B\leq_P A$ and $A\in NP$, then $B\in NP$. Indeed the NP algorithm is clear: perform your reduction (polynomial time) and then solve the instance of $A$ you reduced to (in $NP$).

However, if the reduction is exponential, then we cannot say anything about $B$, except that it is in $EXPTIME^{NP}$, i.e. you can solve it in exponential time with an $NP$ oracle. It is in fact the same that just saying $B\in EXPTIME$, since the NP oracle does not add power.


Why we do isomorphism, automorphism and homomorphism?

Isomorphism formalizes the notion of equal graphs. For example on this figure you see three isomorphic graphs

More formally, an isomorphism of graphs $G_1$ and $G_2$ is a bijection $f:V(G_1) \mapsto V(G_2)$ that preserves adjacency. That is to say:

$$u \sim_{G_1} v \iff f(u) \sim_{G_2} f(v)$$

It is not hard to find such a bijection for every pair of graphs on the picture.

Now if $G_1 = G_2$ then the obtained mapping becomes an automorphism - a isomorphism from the graph to itself.

You might ask what is the intuitive notion of graph automorphism  and the answer is that it gives you some kind of information of which vertices are "equivalent" in a graph. In other words if there is an automorphism of $f$ of graph $G$ such that the vertex $v$ is mapped to vertex $u$ then in a way the neighbourhood of $u$ and $v$ "looks" the same.

This in turn leads to the notion of graph symmetries. A graph $G$ is said to be vertex-transitive if for every pair of vertices $u,v \in V(G)$ there is an automorphism $f:V(G) \mapsto V(G)$ such that $f(u) = v.$ An example of a vertex-transitive graph is the Petersen graph

and as you can see the graphs "looks" pretty symmetric. That is precisely because it has "many" automorphisms of the described type.

Graph homomorphisms are usually not studied by layman and are more or less of theoretical purposes. For example they are closely related to the notion of vertex-colourings.  See also Hadwiger Conjecture


What is the difference between symbol recognition, classification and identification?

The way I've seen it used classification divides a data set into different groups (or classes), while symbol recognition means looking for a specific pattern and checking if it is present in the data or not.

If I understand correctly, what you are talking about is optical character recognition but instead of matching the symbol to an ASCII/unicode value you match it to a LATEX symbol. I think that this could be called both symbol recognition and identification.


"Learning occupancy grid maps with forward sensor models, S.Thurn,2008" a formula that is difficult to overcome

The vector $c_t$ has exactly one coordinate which is 1, and the rest are 0s. You can check that if, for example, $c_{t,k}=1$, when you substitute $c_{t,k}=1$ and $c_{t,\ell}=0$ for all $\ell \neq k$ in (26) you get (22). The same happens for (24) and (25).


Disprove unrealistic speed-up of total Turing machines

Suppose that the input alphabet is $\{0,1\}$, and consider the language $L_1 = 0^*$. We can easily construct a Turing machine $T_1$ such that $S_{T_1}(I) = |I|+1$. On the other hand, $S_{T_2}(I_c) \geq |I_c|+1$. Since $|I_c|=|I_1|+1+|I_2|$, we get
$$
S_{T_2}(I_c) \geq |I_1|+1+|I_2|+1 = S_{T_1}(I_1) + S_{T_1}(I_2).
$$


Prove or Disprove: an infinite intersection of regular languages is a context-free language

"I know that this statement is false, but couldn't find an example to disprove it."
It might come as a surprise to you that, in fact, every non-context-free language can be a counterexample. We have the following fact, assuming any fixed alphabet $\Sigma$.

Let $L$ be a language. Then there exist regular languages $L_1, L_2,...$ such that $L=\cap_{k=1}^{\infty}L_k$.
Proof. The other answer indicates how to construct $L_i$. For clarity, here is the construction.

Let $L_i$ be the words in $L$ with length at most $i$ together with all the words with length greater than $i$. More formally, let $L_i=\{w\in\Sigma^*: w\in L\text{ and } |w|\le i\}\cup\{w\in\Sigma^*:|w|\gt i\}$. Then $L=\cap_{k=1}^{\infty}L_k$.
Each $L_i$ is regular since $L_i$ is the union of two regular languages.

$\{w\in\Sigma^*: w\in L\text{ and } |w|\le i\}$, as a finite set, is regular.
$\{w\in\Sigma^*:|w|\gt i\}$ is regular.

So, even if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, $L=\cap_{k=1}^{\infty}L_k$ can be non-regular, non-context-free, non-context-sensitive, etc.


I will try (1) and go for infinite (the bonus).

The finite case is called the code problem: finding possible decompositions is like decoding. Its classical algorithm is called Sardinas–Patterson. It is not immediately clear it is a finite search space. The lengths of the decomposition might be long. Still it is not Post Correspondence as that has additional restrictions.

The finite case has a simple regular language solution: for every pair of distinct $s,t \in S$ test whether the regular set $s S^* \cap t S^*$ is empty. (The Sardinas-Patterson tries that "in parallel".) This does not work in the infinite case as there would be infinitely many $s,t$ to test.

In the infinite (but regular) case I would build a new finite state automaton based on an automaton for $S$. It simulates in parallel the two different decompositions by keeping track of a pair of states, one for each decomposition. On a letter both pairs make a step on the same letter. In a final state each component may either restart (it has seen an element in $S$) or proceed (trying to find a longer word in $S$). Now we need one additional boolean addition to the state-pair as we need to check whether the two components made different choices in at least one point. Accept if both simulations end in a final state (and we have seen a point where the two decompositions differed). Now again there are no two different decompositions for the same string iff the language of the automaton is empty.

And indeed, for context-free the problem must be undicidable, but I do not have a reference at hand now.


The time complexity of isSame is not linear in the height of the smallest tree. Think for example of two copies of a complete binary tree (where all nodes have the same value).

That said, the time complexity of isSame is always $O(m)$, where $m$ is the number of vertices in the smallest of the two input subtrees.

Let me assume that the number of vertices $m$ of $t$ is at most the the number of vertices $n$ of $s$ (as otherwise the answer is trivial).

Your algorithm requires time $\Theta(n m) = O(n^2)$ in the worst case.
The upper bound is obtained by simply multiplying the number of vertices of $s$ with the $O(m)$ upper bound to the complexity of isSame.
The lower bound is obtained, e.g., by letting $s$ be a path on $n$ nodes rooted in one of its endpoints and $t$ be a path on $m$ nodes rooted in one of its endpoints (as before, all vertices have the same value). The first $\lfloor n/2 \rfloor$ invocations of isSame require $\Omega(m)$ time each, for an overall time complexity of $\Omega(n m)$.
Notice that this is  $\Omega(n^2)$ for $m=\Omega(n)$.


Network throughput with random delay selected from uniform distribution

Let $f(t)$ be the probability distribution function for the probability that the current cycle (from the moment when node 1 broadcast the last message to the moment when node 1 will start broadcasting the next message) has duration $A+t$.

For $d\leq t\leq D$, $f(t)$ must be proportional to $A+t$. We can use the fact that $\int_d^D f(t)\mathrm{d}t=1$ to deduce that $f(t)=\frac{A+t}{\lambda}$ for $d\leq t\leq D$, where $\lambda=D(\frac{D}2+A)-d(\frac{d}2+A)$. $f(t)=0$ if $t>D$ or if $t<d$.

Denote by $P_s$ the probability that node 1 is not broadcasting at any time during a given time period of duration $A$. It can be shown, by considering the conditional probability that node 1 does not broadcast during the given time period given that node 1 is in a cycle of length $t$ at the start of the time period, that $P_s=\int_A^D f(t) \frac{t-A}{t+A} \mathrm{d}t=\frac{1}{\lambda}\left(\frac{\max(A,D)^2}2-A\max(A,D)-\frac{\max(A,d)^2}2+A\max(A,d)\right)$.

The probability that a given message is transmitted successfully is $P_s^{N-1}$. The throughput is then $\frac{NP_s^{N-1}}{A+\frac{D+d}2}$, since the average length of a cycle is $A+\frac{D+d}2$.


Can three regular languages be concatenated?

Concatenation is associative:
$$
(L_1L_2)L_3 = L_1(L_2L_3) = \{w_1w_2w_3 : w_1 \in L_1, w_2 \in L_2, w_3 \in L_3\}.
$$
We denote the common value by $L_1L_2L_3$.

A class of languages closed under concatenation of two languages is also closed under concatenation of three or more languages, as a simple induction shows.

The "zero" element for concatenation is the empty language $\emptyset$, which satisfies $L\emptyset = \emptyset L = \emptyset$. The "one" element for concatenation is the language consisting of only the empty word $\{\epsilon\}$, which satisfies $L\{\epsilon\} = \{\epsilon\}L = L$.


Bounded Quadratic Congruence Problem Variant (for some specific Residue)

Yes.  If $a=1$, the problem is no longer NP-complete; the answer to the problem is always "yes, there is such a positive integer".


The way $O(f(n))$ is defined, $O(k \times f(n))$ = $O(f(n))$ for positive constants $k$. Therefore, $O(2n)$ = $O(n)$. The reason this works is that $f(n) = O(g(n))$ if and only if there exists some constant $c$ such that for all $n \geq n_0$ it holds that $f(n) \leq c \times g(n)$. We can therefore demonstrate that $k \times f(n) = O(f(n))$ since $k \times f(n) \leq c \times f(n)$ precisely for $c \geq k$.


Memory Requirement for a Computable Problem

Yes, there's plenty of theoretical work on space complexity.  No, it's not necessarily Turing machines; you can talk about space complexity in other models of computation, e.g., the RAM model.  You might find that more practically relevant.  I suggest you study RAM machines and existing work on space complexity.

It's not clear what you mean by "levels of memory", and I don't see anything there that's useful.  Instead, standard space complexity results talks about the space requirement: e.g., $\Theta(n)$ space, $\Theta(n^2)$ space, $\Theta(2^n)$ space.  See also LOGSPACE, PSPACE and similar complexity classes.


Using Amdahl's law how do you determine execution time after an improvement?

Since the FP speedup  slows down  the cache by a factor of $2/3$, the cache is "sped up" by $3/2$. Hence the overall speedup is

$ S = \frac{1}{0.7 + 0.2/2 + 0.1 \times \frac {3}{2}} = 1.05 \equiv 5\%$

The execution times now have the ratio: $0.7:0.1:0.15$ for remaining operations:FP:cache. The percentage time spent on FP now is $\frac{0.1}{0.7+0.1+0.15} = 0.105 \equiv 10.5\%$.


Search & read on AVL trees that follow the BST rules while keeping a worstcase balance difference of 1 between subtrees.
read  knuth sorting & searching


How to tackle different sample size in the training set in SVM

A SVM classifier requires a fixed-length feature vector, i.e., all feature vectors must have the same length.  There are multiple solutions:

Pad out the strings to fixed length.
Choose a different set of features, so that there is a fixed number of features.
Pick a fixed number $k$, and look at windows of length $k$ (i.e., substrings of length $k$).  Classify each window of length $k$ using your SVM, then combine those results somehow (e.g., majority vote).
Use a different classifier, such as a recurrent neural network (e.g., LSTM).  See also https://datascience.stackexchange.com/q/16115/8560 for more possibilities.

It's hard to say what will be most appropriate for your particular situation, without knowing more about your learning task.

Based on your subsequent comments, it sounds like you want to learn a DFA.  There's lots written on learning DFAs, using Angluin's algorithm, SAT solvers, or other methods.  Follow the link above for some entry points into the literature on that.  I don't think a SVM  is the right tool for that job -- this sounds like an XY problem.


When is the concatenation of two regular languages unambiguous?

Hint: Given DFAs for $A$ and $B$, construct an NFA which accepts words in $AB$ having at least two different decompositions. The NFA keeps track of two copies of the standard NFA for $AB$ (formed by joining DFAs for $A$ and $B$ with $\epsilon$ transitions), ensuring that the switch from $A$ to $B$ happens at two different points.


Yes, that's exactly the correct algorithm, and what you have produced is Karger's algorithm.
Since the algorithm is randomized, you can run it several time over in the hope of getting a better solution.  There is no guarantee that you will get the optimum cut, but you can make the error probability as low as you want to.
Here is Thore Husfeldt's illustration of it (cc-by-sa-3.0), 10 repetitions of the contraction procedure in Karger’s algorithm for minimum cut on a 10-vertex graph.  The 5th repetition finds the minimum cut of size 3.


what is the k-line-connected graph definition

Judging from the proof of Lemma 1 in the paper, 3-line-connected is the same as 3-edge-connected; line is probably a translation from Japanese.


Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$

I will describe a method running in $O(|n|) = O(\log n)$ where $|n|$ is the length of the number written in decimal representation. We will follow a dynamic programming scheme. For each $k \in \{0, \dots 10\}$ and each positive integer $j \leq n$ we will compute the number of integers of length $k$, whose sum of digits is equal to $k$. This can be computed using dynamic programming where $$C(k, j) = \sum\limits_{i\in\{0, \dots k\}}C(k-i, j-1),$$
since we can add $i$ to the left of a number of length $j-1$ and sum $k-i$ to construct a number of length $j$ and sum $k$.

Let $P$ be a prefix sum over $C(10, j)$ for $j = 0, 1 \dots$, clearly $P(i)$ tells how many integeres of length at most $i$ sum up to 10.
Now the solution to you problem can be fond recursively by finding the greatest $i$ such that $P(i) \leq n$ and subtract it from $n$. This $i$ tells the lengths of your number. And the result of the subtraction is the order of your number among numbers of length $i+1$. Now you can find the left most digit of your number by trying to set the left most number to some value $k \in {1 \dots 9} and checking how many ways you can construct the rest of the number.

I suspect the solution can be found in $O(\log |n|) = O(\log\log n)$ by only building $C(k, 2^r)$ for integers $r$ and binary search for the greatest value of $r$ where $C(10, 2^r)$ is at most $n$.


I don't understand how you call $R$ from $S$. The following is a possible solution.

Let's reduce $A_{TM}$ (halting problem) to  $\overline{A} = \{ \langle  M \rangle | M \text{ is } TM \text{ such that } L(M) = \Sigma^*  \}$ instead of $A$, since decidability of $\overline{A}$ would imply decidability of $A$.

First note that $M_\emptyset (\text{ TM accepting nothing )} \notin$ $\overline{A}$ and it is clearly that $\overline{A}$ is not empty since a TM machine simply accepting any string is in $\overline{A}$, so let's choose $M_1$ from the set $\overline{A}$ and let $L_1$ be the language recognizable by $M_1$.

For any $\langle M, w \rangle$ construct a new TM $M'$

  M'(x)
   Simulate M on w
   If M accepts w then run M_1 on x
   If M_1 accepts x then ACCEPT

Now let's show the reduction:
$\langle M,w \rangle \in A_{TM} \Rightarrow M \text{ accepts } w \Rightarrow M'$ accepts $x$ exactly when $M_1$ accepts $x \Rightarrow L(M') = L_1$ which implies $\langle M_1 \rangle \in \overline{A}$. So we have obtained

$$\langle M,w \rangle \in A_{TM} \Rightarrow \langle M' \rangle \in \overline{A}$$

Similarly, $\langle M,w \rangle \notin A_{TM} \Rightarrow M \text{ does not accepts } w \Rightarrow M' \text{ accepts no string } \Rightarrow L(M') = \emptyset $ which implies $\langle M' \rangle \notin \overline{A}$. So we have obtained
$$\langle M,w \rangle \notin A_{TM} \Rightarrow \langle  M' \rangle \notin \overline{A}$$

Now if $\overline{A}$ were decidable then on any input $\langle M, w \rangle$ we could construct $M'$ as above and decide if $M$ halts on $w$ by checking $\langle M' \rangle \in \overline{A}$.

Finally, the general case of the proof above is known as the Rice's theorem, which you could apply directly to prove that $A$ is not decidable.


Computing the size of an m-associative cache

I'm not sure if the first question is actually a question or a Hint. Anyway cache size can be calculated as follows.

Memory is byte addressable.
Masking off 8 bits for cache line, that means, cache line in 2 ^ 8 bytes.
Using 17 bits for TAG indexing, that is 2^17 cache entries.
Therefore, you have 2^8*2^17 bytes in the cache. That is 2^25 = 2^5*2^20 = 32 MB.


Kolmogorov Complexity of String Concatenation

Let $w = 0^{2^n}$, so that $K(w) = O(\log n)$. The string $w$ has $2^n+1$ prefixes, and so some prefix $x$ satisfies $K(x) \geq n$. This example strongly violates your inequality.

On the other hand, given $xy$ and $|x|$, we can easily extract $x$. This shows that $K(x) \leq K(xy) + O(K(|x|))$. In particular, if $|x| = n$ then $K(xy) \geq K(x) - O(\log n)$.


Prove simple theorems in Haskell in automated way

Look at Agda [1][2]
I think that it's exactly what you are looking for.
I recommend using its emacs mode for autocompletion and hole/interactive programming. [2]/quick-guide.html
A very good introduction is plfa [3], also [2]/tutorial-list.html
[1] https://en.wikipedia.org/wiki/Agda_(programming_language)
[2] https://agda.readthedocs.io/en/v2.6.0.1/getting-started/what-is-agda.html
[3] https://plfa.github.io/


Yes. The constant function $c$ plays the part of $f(n)$. Stated differently, you can use the function $f(n) = c$ to apply the master theorem.

A perhaps simpler way is to find a shift $d$ such that $S(n) := T(n) + d$ satisfies a nicer recurrence. We have
$$
S(n) = T(n) + d = aT(n/b) + c + d = a(S(n/b)-d)+c+d = aS(n/b) +c+d-ad.
$$
If $c+d-ad = 0$, then we get the simple recurrence $S(n) = aS(n/b)$, whose solution is $S(n) = n^{\log_b a} S(1)$ (for powers of $b$). This happens when $d = c/(a-1)$. We conclude that $T(n) = n^{\log_b a}(T(1) + c/(a-1)) - c/(a-1)$ (for powers of $b$).


Not everyone follows the same conventions, but I'll describe the ones I see most commonly.  Your experience may vary.

If $a$ is an array, $a[i]$ is typically used, but not $a_i$.
If $(a_1,\dots,a_n)$ is a sequence, $a_i$ is typically used, but not $a[i]$.  Usually sequences are not updateable.
If $a$ is a string, you might see either $a[i]$ or $a_i$; both are common, in my experience.
I have most commonly seen $s.p$ used for property access.  Sometimes I have seen people use $p(s)$ used.

Different sources may follow different conventions.  There is no one right answer.  A good approach is to find a textbook that you like (e.g., CLRS), and then follow the same conventions they use.  Odds are that they have put some thought into choosing consistent and understandable conventions, so they probably have chosen something reasonable.


A context-free grammar for a language of strings with occurrence properties?

Both $L_1$ and $L_2$ are regular languages. To construct a context-free grammar for them, you can first construct a DFA or NFA accepting them, and then convert it to a regular grammar.


Create an array $A$ of 1000 elements, indexed from $1$.
Store in $A[i]$ the number of input elements equal to $i$. This can be done in linear time by scanning the input elements once.
Create a list $L$ which will contain at most $1000$ elements (and can hence be implemented using a fixed-size array).
Each element of $L$ is a pair $(m_x, x)$ where $x$ is a number and $m_x > 0$ is the number of its occurrences. Initialize $L$ from $A[i]$ as follows: for each $i$ with $A[i]>0$ append to $L$ the pair $(A[i], i)$ (this can be done in constant time since $A$ contains only $1000$ elements).
From now on the algorithm is trivial, as it is just a simulation of the rules in your question.
Repat:

Search $L$ for the element $(m_x, x)$ with $m_x > 1$ that minimizes $x$.
If such an element does not exist, return the length of $L$.
Otherwise:

Delete $(m_x, x)$ from $L$.
If $L$ contains an element $(m_y, y)$ where $ y = x m_x$ increment $m_y$ by $1$; Otherwise add $(1, x m_x)$ to $L$.

An iteration can be carried out in constant time since all list operations take constant time as well ($L$ always has at most $1000$ elements).
Consider now the quantity $\eta$ defined as the number of elements in $L$ plus the number of elements in $L$ with multiplicity greater than $1$.
Initially $\eta$ is at most $2000$.
In all but the last iteration one of the following two things happens:

An element with $(m_x, x)$ with $m_x > 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and some $m_y$ is incremented (causing $\eta$ to increase by at most $1$).
An element with $(m_x, x)$ with $m_x > 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and a new element $(1, x m_x)$ is added to $L$ (causing $\eta$ to increase by $1$).

In any case, each but the last iteration decreases the value of $\eta$ by at least $1$. Since the final value of $\eta$ must be positive, it follows that the total number of iterations is at most $2000 - 1 + 1 = 2000 = O(1)$.
Finally, observe that above procedure only uses constant amount of memory and that any $O(n)$ time and $O(1)$ space algorithm is also a $O(n + k \log k)$ time and $O(k)$ space algorithm, thus also answering your second question.


How to prove every well-balanced orientation of an Eulerian graph is Eulerian?

Your statement follows from Corollary 1 in

L Lovász, Connectivity in digraphs, Journal of Combinatorial Theory, Series B, Volume 15, Issue 2, October 1973, Pages 174-177

The Corollary says, that if you have a vertex $u$, and for every other vertex $v$ the number of edge-disjoint paths from $u$ to $v$ equals the number of edge-disjoint paths from $v$ to $u$, then we have $\text{indegree}(u)=\text{outdegree}(u)$. Since the statement is true for every vertex of the graph, the orientation is Eulerian.

The proof of the corollary and its corresponding theorem is rather technical, but self-contained, and needs less than two pages.


Complexity of testing membership in a disjoint set

There's an easy way to find the node that contains a given value.  You have two data structures: a union-find data structure (that keeps track of which nodes are in the same equivalence class), and a hashtable (that maps from a value to the node(s) that contain that value).

The MakeSet operation adds a new set to the union-find data structure and adds a new entry to the hashtable.  The Union operation and Find operations use only the union-find data structure.  The "look up a node by value" operation uses the hashtable.

The running time of the MakeSet, Union, and Find operations is as in the underlying union-find data structure.  (MakeSet incurs an extra $O(1)$ (expected, amortized) time to insert into the hashtable, but this doesn't change the overall running time of MakeSet.)   The running time of looking up a node by value is $O(1)$ (expected, amortized) time, if you have a good hash function and if each value is only found in a single node.

This doesn't require duplicating the data, if you use pointers in lieu of duplicating: each entry in the hashtable can have a pointer to the node, and each node has a pointer to the value, so values and nodes aren't duplicated.  Of course, this does increase the memory usage (by at most a constant factor); nothing is free in life.


A data structure for holding numbers in 2 sets, using BST?

Since it's your exercise, I don't want to prevent you from finding the solution on your own, but I'll give you some possible hints:

Big hint:

   You can do some work during the Insert operation to make any subsequent Find run fast.

Think about that one for a while.

If you're still stuck, here are some more specific hints.  I recommend you think about each one for 15 minutes or more before moving on to the next one.

Hint #2:

   Suppose you wanted to implement an operation InsertAndFind(a,S), that effectively does Insert(a,S) followed by Find().  Could you make that run in O(log n) time?

Hint #3:

   It would also be possible to have a single data structure (e.g., a single augmented balanced binary search tree), with some information in each node.

Hint #4:

   What information would you want to keep in a node, to determine whether that node is something that could be returned in response to a future Find query?


Designing a PDA that keeps track of the stack size

Note that in your model, you only ever have a single item $x$ on the stack, namely the current number of inputs seen. Thus, you're not really using the stack.

This is sometimes called a register, and there are models called register machines, or sometimes cost register automata, introduced by Alur in 2011.

The power of this model, and certain algorithmic properties of it, depend on what you allow to do with the register. If you allow reading it's value and comparing it to e.g. 0, then very quickly things become undecidable. But if you only allow simpler things, you get all kinds of interesting models.


Tightest upper bound on length of distinguishing string in Hopcroft's algorithm

Let $Q$ be the set of states, $|Q|=n$. Consider the equivalence relation $E_i\subseteq Q\times Q$ of "indistinguishability by strings of length at most i".
Let $k$ be the tightest upper bound. We have a pair of distinguishable states $p,q$ for which the shortest distinguishing string $w$ has length $k$, i.e., $(p,q)\in E_{k-1}\setminus E_{k}$. By reading the first letter $w_1$ of $w$ we also get a pair of states $(\delta(p,w_1),\delta(q,w_1))\in E_{k-2}\setminus E_{k-1}$ for which the shortest distinguishing word has length $k-1$ (it is the word $w_2\dots w_k$). We can continue the same argument down to $0$.
Therefore, $E_0\supsetneq E_1\supsetneq\dots\supsetneq E_{k-1}\supsetneq E_k= E_{k+1}=E_{k+2}\dots$.
The equivalence $E_0$ has two equivalence classes (parts): the accepting and the nonaccepting states. (Assuming that there is at least one accepting and at least one non-accepting state; otherwise nothing is distinguishable and the tightest bound is $-\infty$.) And any equivalence relation can have at most $n$ parts.
By the chain of strict inclusions above, $E_1$ has at least 3 parts, $E_2$ has at least $4$ parts, etc., and $E_{n-2}$ has (at least) $n$ parts which means that $E_{n-2}$ is the identity relation. This implies that the worst-case bound is $k=n-2$.
This bound is tight: Consider a two-element automaton with one accepting and one non-accepting state. We have $n=2$ and $k=0=n-2$.


At it's core a trie is a tree-shaped deterministic finite state machine (no loops, no merges). They work best when you have a preset number of keywords to search for.

The root is the start state and the leaves are all final states but each with its own action.

However for parsing the http optimally one wouldn't use a pure trie. BEcause the input is mostly freeform you are better off using a custom state machine.


Change your code for binary_converter() to return the empty string ('') instead of '0', when you pass it the input zero.

Then, write a new function binary_converter_for_realz(), which checks whether the input is zero; if passed zero, it just returns '0', otherwise it invokes binary_converter() and returns whatever it returns.

This basically treats 0 as a special case, which it is: we don't want a leading zero, except when the integer is zero, in which case we do.


Asymptotic runtime for querying an interval tree

Querying an interval tree is $O(\log n + m)$, where $n$ is the size of the tree and $m$ is the size of the output. This explains your confusion. Note that there is a trivial $\Omega(m)$ lower bound.

Unfortunately I couldn't find an online proof of this bound, and since there are many variants of interval trees and many different queries, it's best if you tried to prove it yourself for your type of interval tree and query.


Let me give a different take on it than vonbrand. Everything you said is true: the RAM model is not realistic for a number of reasons, and whereas it is possible to defend different aspects of it, such a defense doesn't really get to the heart of the matter.
The heart of the matter -- and the answer to your question -- is that the RAM model is the best thing we have. Compared to other models that are accepted, it more accurately models real-life computation. In particular, the reason we adopted the RAM model was primarily a response to Turing machines, as we found that the use of Turing machines leads to problems being artificially difficult to solve in terms of time complexity. The RAM model clearly solves this glaring issue, and thus it has been accepted, even though it remains far from perfect.
A classical example that illustrates the glaring issue with Turing machines is the problem of string equality: given input
$$ w_1 \# w_2$$
where $w_1, w_2$ are binary sequences and $\#$ is a separator, determining whether $w_1 = w_2$. It can be shown that any Turing machine for the equality problem takes $O(n^2)$ time. This is uncomfortable, because Turing machines are what everyone thinks of as the universal model of computation -- yet no software engineer or algorithms researcher believes that string equality really takes $O(n^2)$ time. So what gives? String equality should be linear, so we invent a new model where it is, and the best solution available right now is word RAM machines.
Perhaps some day in the future we will come up with a better model -- one that is simple, conceptually clear, and improves on RAM in its ability to model real-life computational complexity. For now, we can only make do with the best that we have.


Upper bound for the time complexity of a TM in P on input x?

The complexity class P is a set of languages, not a set of Turing machines. A language is in P if it is accepted by some Turing machine running in polynomial time. So for every language $L$ in P, there is a Turing machine $M$ that accepts $L$ and runs in time $p(n)$ for some polynomial $p$, where $n$ is the input length. This is exactly the time bound you're after — its existence is guaranteed by the definition of P.

To show that the problem you were given is P-complete, you need to show that every language in P reduces to your problem. In other words, you need to show that for all languages $L \in P$ there exists a polytime reduction from $L$ to your problem. The reduction accepts an instance of $L$, and can depend on $L$ arbitrarily.

What you seem to be trying to construct is a function with two inputs: a language $L \in P$ (given as a polytime Turing machine) and an instance $x$ of $L$. There is absolutely no need to construct such a function.


Does integer programming $\in$ NP imply $NP=CoNP$?

The notion of duality suggested by the discrete Farkas lemma found in Lasserre's paper does not correspond to an integer program. There is a notion of duality for integer programs (see for example here), but strong duality does not hold, so I doubt it can be used along the lines you suggest.


Clarification regarding definition: Two way non deterministic finite state Automata

As you clearly state, an input is accepted, by definition, if one of the parallel branches accepts. This means that an input is accepted if and only if at least one of the parallel branches accepts. So if one brach accepts and another rejects, the input is accepted.

In non-deterministic automata, acceptance and rejection are not symmetric. An input is accepted iff there is some accepting computation path. An input is rejected iff all computation paths are rejecting.


Should check all $2^n$ possibilities in array?

The query complexity of your problem, which is the number of oracle calls that any correct algorithm needs to make, is $2^n-1$ (or even $2^n$, if the oracle is allowed to return "No" on all inputs, in which case the answer to your problem is "Infeasible"). This assumes your oracle is a black box. When your oracle is given explicitly, the complexity of the problem could depend on the oracle. For the primality oracle, your problem is likely hard, but this could be challenging to prove since the additive properties of primes are not well-understood.

Indeed, suppose that you have an algorithm solving your problem on arrays of length $n$ using less than $2^n-1$ oracle calls in the worst case. Run it on the array $1,2,4,\ldots,2^{n-1}$. Whenever the oracle asks a question, always return "No" (i.e., cannot be used). When the algorithm has finished, there are at least two sets $S,T$ that have not been queried. There we can consider two oracles, one that says "Yes" only on $\Sigma(S)$ (the sum of elements in $S$) and the other that says "Yes" only on $\Sigma(T)$. By construction, $\Sigma(S) \neq \Sigma(T)$, and so the correct answer is different in both cases. However, the algorithm cannot distinguish between the two oracles, and so its output will be wrong for at least one of these two oracles.

If we allow the oracle to return "No" on all inputs, then we can get a contradiction even given an algorithm that makes exactly $2^n-1$ oracle calls in the worst case. Running it on the same array and answering every query negatively, there is always a set $S$ which has not been queried, and the algorithm cannot distinguish between the oracle which answers "Yes" only on $S$ (in which case the answer is $S$) and the oracle which always answers "No" (in which case the answer is "Infeasible").


Number of independent parity checks satisfied by a code

Any given parity check $u$ divides Hamming space exactly in half, into those vectors which satisfy $u$ and those that do not.

Suppose your Hamming space is $X = \{0,1\}^n$. A non-zero parity check $u$ divides $X$ into two sets: $X_0 = \{ x \in X \mid \langle x,u \rangle = 0 \}$ and $X_1 = \{ x \in X \mid \langle x,u \rangle = 1 \}$. The two sets have equal size $2^{n-1}$.

Indeed, let $v$ be some non-zero vector such that $\langle u,v \rangle = 1$ (for example, $v$ could contain a single 1 entry, at some index in which $u$ also has a 1 entry). If $x \in X_0$ then $x + v \in X_1$, and conversely, if $x \in X_1$ then $x + v \in X_0$. Hence we can partition $X$ into pairs $(x,x+v)$ in which the first member is in $X_0$ and the second in $X_1$.

Here are two illustrating examples. If $u = (1,\underbrace{0,\ldots,0}_{n-1\text{ copies}})$ then $X_0$ consists of all vectors with 0 in the first coordinate, and $X_1$ consists of all vectors with 1 in the first coordinate. If $u = (\underbrace{1,\ldots,1}_{n \text{ copies}})$ then $X_0$ consists of all vectors with even parity, and $X_1$ consists of all vectors with odd parity.

Therefore, the $2^k$ vectors of a linear subspace in $2^n$ Hamming space can satisfy at most $n−k$ linearly independent parity checks. The statement here actually doesn't follow from the preceding statement. However, it is similar in spirit (and a generalization of the preceding statement). Earlier we have considered a single parity check $u$. We showed that if $u$ is non-zero, then the set $\{x \in X \mid \langle x,u \rangle = 0\}$ contains exactly half the space. If $u = 0$ then it consists of the entire space.

Now we are considering the common solutions of $m$ different vectors $u_1,\ldots,u_m$. The set $C = \{x \in X \mid \langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0\}$ contains at least $2^{n-m}$ vectors. If the vectors are linearly independent (this generalizes the condition $u \neq 0$), then $C$ contains exactly $2^{n-m}$ vectors. More generally, $C$ contains $2^{n-d}$ vectors, where $d$ is the dimension of the linear span of the vectors $u_1,\ldots,u_m$. I won't prove all these statements, but this is basic linear algebra.

If $C$ is a linear subspace containing $2^k$ vectors, and every element $x \in C$ satisfies $\langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0$, then the dimension of the span of $u_1,\ldots,u_m$ is at most $n-k$, per the discussion above. If we know that $u_1,\ldots,u_m$ are linearly independent, then the dimension of their span is $m$, and so $m \leq n-k$.

These parity checks together form the parity check matrix $H$, which is another way to define the linear subspace.

We can describe a linear code in two ways. One is using a generator matrix $G$: the linear code consists of all linear combinations of the rows. The other is using a parity check matrix $H$: the code consists of all vectors whose inner product with each row is 0. (Some books use rows, other columns.) Using our earlier notation, the rows of $H$ are just the vectors $u_1,\ldots,u_m$, where we insist that the vectors be linearly independent (the same holds for generator matrices).

Here is an example. Let $n = 3$, and consider the code whose generator matrix is
$$
\begin{bmatrix}
1 & 1 & 0 \\
1 & 0 & 1
\end{bmatrix}
$$
(We note that the same code has many generator matrices, and many parity check matrices.)

The code consists of all linear combinations of the rows:
$$
\begin{matrix}
0 & 0 & 0 \\
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1
\end{matrix}
$$
You can check that these are exactly the vectors with even parity. Hence a parity check matrix for this code (in this degenerate case, the unique parity check matrix) is
$$
\begin{bmatrix}
1 & 1 & 1
\end{bmatrix}
$$
We can also treat this as a generator matrix of a code. The resulting code is known as the dual code (dual to the code for which this matrix functions as a parity check matrix).


Does graph G with all vertices of degree 3 have a cut vertex?

Not necessarily true, for example complete graph of 4 vertices have no cut vertex. But there exists a graph G with all vertices of degree 3 and there
is a cut vertex. See the picture. Red vertex is the cut vertex.


6-coloring of a tree in a distributed manner

In the paper, the authors mention that after $\log^* n$ iterations, the number of bits used to encode any of the color labels is at most 3. That means that there are at most eight colors. If we have six or fewer colors, we're done, and otherwise we go through the loop once more.

Let's say that we do one last loop iteration. The root gets the color label 0 or 1. Every other node gets a label equal to the first bit position where that node's old label disagrees with its parent's label, plus one extra bit. Since on entry to this iteration all colors are three bits long in the worst case, there are three possible positions where the bits could disagree. Therefore, each new color is formed from a combination of one of three choices and a bit (one of two choices), so at exit of this loop iteration there are only six possible color labels, so we have a six-coloring. The total number of loop iterations is then $\log^* n + 1 = O(\log^* n)$

Hope this helps!


What is the time complexity of binary sum (recursion)

First of all, calculating the sum can't be better than $O(n)$ in the general case because you have to inspect all elements in order to determine the sum.

The function also does not halve the problem size every step: instead of choosing one subarray, as in binary search, we sum both subarrays. This does not save work at all.

We can determine the running time using the recurrence relation:

$$T(0) = T(1) = 1$$
$$T(n) = 2 \times T(n/2) + 1$$

Setting $k = log_2(n)$ we can write this this as:

$$T'(0) = 1$$
$$T'(k) = 2 \times T'(k-1) + 1$$

Now we can use:

$$T'(n) = \sum_{i = 1}^{k} 2^i \times 1$$
$$= 2^{k + 1} - 1 = 2 \times 2^{k} - 1$$
$$= 2 \times n - 1$$


The language consists of ternary relations $R_1, \dots, R_4$, which represent the clauses as follows:

$(x,y,z)\in R_1$ iff there is a clause $(x\lor y\lor z)$;
$(x,y,z)\in R_2$ iff there is a clause $(x\lor y\lor \neg z)$;
$(x,y,z)\in R_3$ iff there is a clause $(x\lor \neg y\lor \neg z)$;
$(x,y,z)\in R_4$ iff there is a clause $(\neg x\lor \neg y\lor \neg z)$.

($\lor$ commutes so you don't need to consider other patterns of negation.)

The formula then says "There exists a set $T$ of variables such that, if the variables in $T$ are set to true and the ones not in $T$ are set to false, the formula is satisfied."  That is,

$$\begin{align*}
\exists T\,\forall x\forall y\forall z\, \big[&\big(R_1(x,y,z)\rightarrow (T(x)\lor T(y)\lor T(z))\big)\\
&\quad \land \big(R_2(x,y,z)\rightarrow (T(x)\lor T(y)\lor \neg T(z))\big)\\
&\quad \land \dots\big]\,.
\end{align*}$$


References for the computational complexity of training neural networks

At present the theory of computational complexity has little useful to say.  This is largely an empirical science: to find out how many epochs of training are needed or is optimal, the only way to know for sure is to try it and see.  While there is some limited amount of theory, the theory isn't very useful in practice.  Ultimately, we don't really understand why deep learning works or how well it works or exactly what conditions are needed for it to work.

Training usually involves a series of epochs.  The time for each epoch is proportional to the time to evaluate the network on each of the training set instances, once.  There's no theory about the number of epochs needed.  However, in many situations the number of epochs is a relatively small number, say, 20-100 -- not always, but fairly often.  So, that gives you some idea.

Ultimately, topology doesn't seem to affect training time much except insofar as it affects the time to evaluate the classifier on an instance.  It could influence the number of epochs too, but on many networks seen in practice, it doesn't seem to have a large influence for many of the architectures we use in practice.  However, this could be a consequence of the fact that we typically select architectures that do perform well with a reasonable amount of training (i.e., the architecture is often selected so a huge number of epochs isn't needed).  In any case, this isn't a   hard-and-fast rule.

Bottom line: ultimately, we understand very little about the complexity of neural networks, the complexity of training, or rigorous/well-founded/provable answers to your questions.


Finding all paths from s to t in linear time

The algorithm you describe cannot possibly be linear time for a DAG or general graph. Consider the following DAG on $n$ vertices $V = \{v_1, v_2, \ldots v_n\}$. Take a particular node $v_i$, for all $j > i$ add an edge $(v_i, v_j)$. This will create $\Theta(n^2)$ edges in this DAG. Note that a path from $v_1$ to $v_n$ can use any subset of nodes $\{v_2, v_3, \ldots v_{n-1}\}$. That is to say there are $2^{n-2}$ possible paths from $v_1$ to $v_n$. Clearly to print all these would take exponential time.

What you can do in linear time, is determine the subgraph that would contain all possible paths from $s$ to $t$. With a source $s$ in mind, we first check if it can reach $t$ (via DFS), if not then return an empty subgraph. Otherwise we check if $s$'s children $\{v_1, v_2, \ldots\}$ can reach $t$, this can be done recursively top-down or bottom-up if we start at $t$ and work backwards. Let's say $A$ is the set of nodes who are a descendant of $s$ and an ancestor of $t$. $A$ will also include $s$ and $t$ for obvious reasons. The subgraph we are interested will contain exactly the vertices in $A$. With this we can iterate through edges an include them as necessary, or we could even pick up edges long the way as we are determining which nodes are in $A$. This procedure overall will take $O(n + m)$. Of course, this is only interesting in a DAG unless $t$ or $s$ is an articulation point.


Correct term for a priority queue with unique elements

I don't know of a name for the abstract data structure.

There is a well-established implementation of what you describe, though: treaps, a combination of BST and heap (i.e. priority queue). This is with priority and value/key being different things, though.

If priority and value are the same, use any priority queue and add uniqueness, i.e. by combining it with a set/dictionary data structure. (Treaps degenerate to sorted lists in this case.)


There is an issue below:

{s = 0 and j = 0}
while j <= n do begin
  { s + j = (j - 1)j/2 and j <= n + 1}     (*)
    s := s + j;
  { s = (j-1)j/2 and j <= n + 1}           (**)
  { s = j(j+1)/2 and j + 1 <= n + 1}
    j := j + 1;
  { s = (j-1)j/2 and j <= n + 1 }
end;
{ s = (j-1)j/2 and j <= n + 1 and j > n}
{s = n*(n+1)/2}

The part marked with ** seems to use a weakening step (sometimes also called a pre- or post- step), moving from { s = (j-1)j/2 and j <= n + 1} to { s = j(j+1)/2 and j + 1 <= n + 1}. However, this is allowed only if the former implies the second, which is not the case! This step looks completely arbitrary.

You can simply avoid it, and backward propagate as usual.

Further, in * you can also assume that the while guard is true, beyond the invariant.

Here's a possible step towards a fix:

{ s = 0 and j = 0 }                           (1)
{ s = (j-1)j/2 and j <= n + 1 }
while j <= n do begin
  { s = (j-1)j/2 and j <= n + 1 and j <= n }  (2)
  { s + j = j(j+1)/2 and j + 1 <= n + 1 }
    s := s + j;
  { s = j(j+1)/2 and j + 1 <= n + 1 }
    j := j + 1;
  { s = (j-1)j/2 and j <= n + 1 }
end;
{ s = (j-1)j/2 and j <= n + 1 and j > n }     (3)
{ s = n*(n+1)/2 }

Now you need to prove the implications at points 1,2,3. 3 looks simple, and 2 requires a bit of arithmetic. Instead 1 looks false if n<-1. We need a stronger precondition ensuring that.

Indeed, if you manually run the program starting with n=-10, you do not get s=n(n+1)/2 at the end, so the Hoare triple is invalid, hence -- since the Hoare logic is correct -- we can not hope to prove it valid ;-)


How can I prove the minimum pumping length of finite language?

You explanation sounds good (you want to change "smaller than" in "smaller than or equal to").

Suppose towards a contradiction that the pumping length was $k \le 3$ then, since
$w=000$ is a word of length at least $k$ in $L$, you could invoke the pumping lemma to conclude that $w$ can be written as $w=xyz$, with $|y|>0$, in such a way that $xy^ik \in L$ for any choice of $i \ge 0$.

This is a contradiction since the choice $i=4$ yields a word $w'$ of length $|w'| = |x| + 4 |y| + |z| \ge 4$ for which you simultaneously have $w' \in L$ (by the Pumping Lemma) and $w' \not\in L$ (by the definition of $L$).

In addition, to show that $k'=4$ is the smallest possible pumping length, you need to argue that $4$ is a valid choice for the pumping length.
In your case this is trivial as the pumping lemma gives you a property over the set of all words in $L$ of length at least $k'$. For $k'=4$ this set is empty, which makes the statement trivially true.


How to discuss coefficients in big-O notation

Big-$O$ and big-$\Theta$ notations hide coefficients of the leading term, so if you have two functions that are both $\Theta(n^2)$ you cannot compare their absolute values without looking at the functions themselves.  It's not wrong per se to say that $7x^2 + 4x + 2 = \Theta(7x^2)$, but it's not informative because $7x^2 + 4x + 2 = \Theta(3x^2)$ is also true (and, in fact, it's $\Theta(kx^2)$ for any positive constant $k$).

There are other notations you might want to use instead.  For example, $\sim$ notation is a much stronger claim than big-$\Theta$:

$\qquad \displaystyle f(x) \sim g(x) \iff \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1$

For example, $7x^2 + 4x + 2 \sim 7x^2$, but the claim $7x^2 + 4x + 2 \sim 3x^2$ would be false.  You can think of tilde notation as $\Theta$ notation that preserves the leading coefficients, which seems to be what you're looking for if you do care about the leading coefficient of the dominant growth term.


How does the nearest insertion heuristic for TSP work?

I think that by "insertion heuristic" you mean "nearest insertion heuristic". If this is the case, here is how it works:

We're looking to construct a cycle $C$ containing all the nodes of our problem. We will do this by initially constructing a small cycle and slowly adding nodes to it until it contains all the nodes. We start by choosing some starting node $N$ and adding it to $C$. $C$ now contains a single node, $N$.
We want to add to $C$ the node which will increase its length the least. To do this we need to find which node to add to our cycle and then figure out where in the cycle to put it. We select this node by choosing the node (not in $C$) which is the closest to any node in $C$. We then insert this node between two nodes in $C$ such that the increase in length is minimal. More formally: Let $k$ be the node we selected. Find an edge $(i,j)$ such that $d_{ik}+d_{kj}-d_{ij}$ is minimal.
Add $k$ to $C$, remove edge $(i,j)$, and add edges $(i,k)$ and $(k,j)$.
If $C$ contains all the nodes, stop. Otherwise, go to 2.


You might find interesting some of the results in On the Complexity of Fragments of Modal Logics by Linh Anh Nguyen (in Advances in Modal Logic, 2004: 249-268). A version of the paper is available in the home page of Nyugen.

And probably you are already familiar with A guide to completeness and complexity of modal logics by Joseph Y. Halpern and Yoram Moses (in Artificial Intelligence 54, 1992, pp. 319-379). A version of the paper similar to the published version is available in postscript and pdf in the home page of Halpern.


Page cache and its relationship to page table

The only link is that they both operate with the same page size and, well, the same pages.

The reason is the mechanism of file access. You can request access to file via mapping its contents into memory space. In this case, the entire file isn't read into memory at once, instead, the page table is filled with inaccessible pages. Once application tries to access these pages, the actual file contents is read into memory.

So, the file cache stores individual pages of files, and this mechanism is described in the page cache article.


Term for an A*-like pathfinding strategy where only the heuristic goal distance matters


Polynomial Hierarchy --- polynomial time TM

Your definition of $\Sigma_2^P$ is a bit misleading. Both $u_1$ and $u_2$ have to be bounded in length by some polynomial in $|x|$, and this usually forms part of the formula rather than part of the descriptive text. The predicate $M$ has to be polynomial time in the combined input length, which is the same as being polynomial time in $|x|$ since both $u_1$ and $u_2$ have length polynomial in $|x|$.

You have not described the predicate SubgraphIsomorphic correctly. You are given two graphs $A,B$, and you have to decide whether $B$ is isomorphic to a subgraph of $A$. We write it as an NP-predicate as follows:
$$(A,B) \in \mathrm{SubgraphIsomorphic} \leftrightarrow \exists |P| \leq |(A,B)| \mathrm{Isomorphic}(A,B,P), $$
where $\mathrm{Isomorphic}(A,B,P)$ is true if $P$ encodes an injection from the vertex set of $B$ to the vertex set of $A$, and $(x,y)$ is an edge of $B$ iff $(P(x),P(y))$ is an edge of $A$. This is a polytime predicate. Moreover, the injection can be coded in length polynomial in the input $(A,B)$ (for simplicity, I'm assuming that the encoding is such that $|P| \leq |(A,B)|$).


Densely connected non overlapping subgraph

If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters.
When it comes to community detection or clustering, you need to make a formal definition of a community or cluster (in this case it is a clique). There are two types of definitions:

Non-overlapping definitions - There are some definitions that do not allow any overlap between communities such as $k$-cores. Basically, the following properties prevent $k$-cores of being overlapping:

$k$-cores are maximal
Union of two $k$-cores is a $k$-core.

There are lots of different techniques such as modularity optimization, seed expansion, etc. If you are looking for stricter non-overlapping community definitions, you can dig further in this paper (and the sequence of other papers) and find the one ghat works well on coefficient clustering score:

Fortunato, Santo. "Community detection in graphs." Physics reports 486.3 (2010): 75-174.

Overlapping definitions - However, some definitions such as cliques or quasi-cliques, allow overlap between clusters, even though you consider maximality. Below, I show a simple example where few maximal cliques overlap with each other (link for image).


Longest Common Sequence reduction proof question

We can prove that LCS (with an unbounded number of sequences!) is NP-hard by reduction from 3SAT. Let us be given a CNF $\varphi$ with $m$ clauses $C_j$ of the form
$$
(x_{i_{j,1}} = b_{j,1}) \lor (x_{i_{j,2}} = b_{j,2}) \lor (x_{i_{j,3}} = b_{j,3}).
$$
Here $b(j,c)$ is either T or F, and we assume that $i_{j,1},i_{j,2},i_{j,3}$ are all distinct.

We will consider the following strings:

$S_1 = x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} \ldots x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}}$.
$S_2 = x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} \ldots x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}}$.
$S_3 = x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} \ldots x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}}$.

For each variable $x_i$, let $T_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^F$ (for all $j$), and let $F_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^T$.

For each variable $x_i$, $TF_i = T_i F_i$ and $FT_i = F_i T_i$.

Let $R$ be a common subsequence of all these strings.

For every $j$, the string $R$ contains at most one of $x_{i_{j,1},j}^{b_{j,1}},x_{i_{j,2},j}^{b_{j,2}},x_{i_{j,3},j}^{b_{j,3}}$. Indeed, suppose that it contained both $x_{i_{j,k_1},j}^{b_{j,k_1}}$ and $x_{i_{j,k_2},j}^{b_{j,k_2}}$, in this order. Since $R$ is a subsequence of $S_1$, we must have $k_1 < k_2$. However, if $k_1 = 1$ then $R$ cannot be a subsequence of $S_2$, and if $k_1 = 2$ then $R$ cannot be a subsequence of $S_3$.

Thus $|R| \leq m$, and if $|R| = m$ then we can associate with $R$ a choice of equation in each clause.

For every $i$, if $R$ contains both $x_{i,j_1}^{b_1}$ and $x_{i,j_2}^{b_2}$ then $b_1 = b_2$. Indeed, in any subsequence of $TF_i$ all symbols $x_{i,j_1}^T$ precede all symbols $x_{i,j_2}^F$, and in any subsequence of $FT_i$ all symbols $x_{i,j_1}^F$ precede all symbols $x_{i,j_2}^T$.

Thus the chosen equations are all compatible.

This shows that if $|R| = m$ then $\varphi$ is satisfiable. The converse is also easy to establish: given a satisfying assignment, we can choose a satisfied equation in each clause, and then concatenate the corresponding symbols.

Let us give an example. Consider the formula
$$
\varphi = [(x_1 = T) \lor (x_2 = T) \lor (x_3 = T)] \land [(x_2 = F) \lor (x_4=F) \lor (x_1 = F)].
$$
The strings are

$S_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$S_2 = x_{2,1}^T x_{3,1}^T x_{1,1}^T x_{4,2}^F x_{1,2}^F x_{2,2}^F$.
$S_3 = x_{3,1}^T x_{1,1}^T x_{2,1}^T x_{1,2}^F x_{2,2}^F x_{4,2}^F$.
$TF_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_1 = x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F$.
$TF_2 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_2 = x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F$.
$TF_3 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_3 = x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$TF_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F$.

One string $R$ of length $m=2$ which is common to all of these is $x_{1,1}^T x_{2,2}^F$. This corresponds to the (partial) truth assignment $x_1=T,x_2=F$, which satisfies $\varphi$.


In flow networks, may source/sink have incoming/outgoing edges?

Yes, it's possible.

My source is 'Graph Theory and its Applications', 2nd ed, by Gross & Yellen, page 540, question 13.1.8:

  Some authors define an s-t network such that the source s must have indegree 0 and t must have outdegree 0. Describe how a network whose source and sink do not satisfy these additional requirements can be transformed by graphical operations into one whose source and sink do meet such requirements.

However, it doesn't give the construction, I can only think that it would be by adding a supersource and a supersink, as you'd usually do with multiple (though standard) sources and sinks, to 'soak up the leakage'. I am not sure though.


Are there any natural $\Pi_2^P$-complete problems?

There are very many natural complete problems for $\Pi_2^p$, and there is a survey [1] on completeness for levels of the polynomial hierarchy, containing many such problems.  The paper On the complexity of min-max optimization problems and their approximation [2] contains a nice overview of "min-max problems" with several proofs of completeness.  The latter paper is opened   with the following sentence:

  The computational complexity of optimization problems of the min-max form
  is naturally characterized by $\Pi_2^p$, the second level of the
  polynomial-time hierarchy.

Some problems:
Here are some examples, all of which are $\Pi_2^p$-complete, listed in the aforementioned survey [1].

$\forall \exists \text{3SAT}$: Given 3-SAT formula $\phi(x,y)$, is it true that for all $x$ there exists a $y$ such that $\phi(x,y)$ is satisfiable?
NOT-ALL-EQUAL-$\forall\exists\text{3SAT}$
MINMAX SAT, MINMAX CIRCUIT, MINMAX CLIQUE
LIST CHROMATIC NUMBER
GRAPH SATISFIABILITY
DYNAMIC HAMILTONIAN CIRCUIT, LONGEST DIRECTED CIRCUIT
SUCCINCT TOURNAMENT REACHABILITY
CONSTRAINTS OVER PARTIALLY SPECIFIED FUNCTIONS
ARGUMENT COHERENCE
3-COLORING EXTENSION, 2-COLORING EXTENSION
(STRONG) ARROWING, GENERALIZED RAMSEY NUMBER
etc., etc.

References:

[1] Schaefer, Marcus, and Christopher Umans. "Completeness in the polynomial-time hierarchy: A compendium." SIGACT news 33.3 (2002): 32-49. (PDF)

[2] Ko, Ker-I., and Chih-Long Lin. "On the complexity of min-max optimization problems and their approximation." Minimax and Applications. Springer US, 1995. 219-239. (PDF)


Yes, $C$ here is the density of (simple) directed graphs. You can see the Wikipedia entry on dense graphs for more details. In this context, total connectivity is just another name for density.


Given $g(n) = \omega(f(n))$, then $g(n) + f(n) = \Omega(g(n))$?

There is a simpler proof. Assuming (as is usually the case) that $f$ is non-negative, we get $g(n) + f(n) \geq g(n)$, which implies that $g(n) + f(n) = \Omega(g(n))$. There is no need to assume anything.

If we know that $g(n) = \Omega(f(n))$, we can conclude further than $g(n) + f(n) = \Theta(g(n))$. And if $g(n) = \omega(f(n))$ then $g(n) + f(n) \sim g(n)$.


Enumerate partitions of a set with blocks of equal size

Section 5.10 of Ruskey's book Combinatorial Generation gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear extensions of a corresponding poset.

  Partitions of Given Type

  Let $P(n_0, n_1, \ldots, n_t)$ be the set of partitions of the set $\{1, 2, \ldots, n\}$ into blocks of sizes $n_0, n_1, \ldots, n_t$, where $n = n_0 + n_1 + \cdots + n_t$. For example, the partition $\{\{2, 8\}, \{3, 5\}, \{6, 12\}, \{1, 10, 11\}, \{4, 7, 9\}\}$ is in $P(2, 2, 2, 3, 3)$. We have listed the elements in order and the blocks of equal size by the magnitude of their smallest element. The problem of generating the elements of $P$ can be reduced to that of generating the linear extensions of a certain forest poset. The cover relations of the poset consist of chains of sizes $n_i$ together with chains of the maximal elements of the previous chains which have equal values of $n_i$. The linear extension corresponding to our example is $7, 1, 3, 10, 4, 5, 11, 2, 12, 8, 9, 6$. The inverse of this permutation is $2, 8, 3, 5, 6, 12, 1, 10, 11, 4, 7, 9$, which is just our original partition but without the curly braces.

  To be a little more precise, assume that the $n_i$ are listed such that $n_0 \le n_1 \le \cdots \le n_t$, and let $s_i = \sum_{j=1}^{i-1} n_i$. The cover relations of the poset are indicated by the $t + 1$ chains $C_i = s_i + 1, s_i + 2, \ldots, s_i + n_i$ and $D_i = s_i + 1, s_{i+1} + 1, \ldots, s_j + 1$, where $n_{i−1} < n_i = n_{i+1} = \ldots = n_j < n_{j+1}$.

The algorithm per se is described in Pruesse and Ruskey, Generating linear extensions fast, SIAM Journal on Computing 23.2 (1994): 373-386.


Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How?

No. $n^{2.999}\log_2n$ is tighter, for example.


How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?

Hint for part (b): Consider the statistic $r(\pi) = \sum_i |i-\pi(i)|$. Running SQRTSORT can reduce $r(\pi)$ by at most $n$, while $r(n(n-1)\ldots1) = \Omega(n^2)$.

Hint for part (c): I get a running time of $O(n^2\log^{O(1)} n)$.


Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?

Firstly, note that you can reduce $CMCG$ to $MCG$ by setting the value of the node that must be in the set to the  sum of all positive weights of all other nodes $+1$ and then applying $MCG$ and retrieving the result set. Thus $CMCG\in NP$.
As proved in the paper the $NP$-complete Steiner-Tree problem can be reduced to $CMCG$ meaning that $CMCG$ is $NP$-hard. If a problem is in $NP$ and $NP$-hard it is by definition $NP$-complete.
Hope this helps.


Genetic algorithm does not always find the global optima and a higher mutation rate finds a better solution

I'll start with the second question because it's easier.  How could increasing the mutation rate improve the results?

Genetic algorithms can beat random searches when they converge on the right answer.  Similar to other machine learning algorithms, genetic algorithms have an "explore" phase and a "converge" phase.  If the algorithm doesn't run long enough (enough rounds) to enter the converge phase, then a higher mutation rate will likely give you better results.  The other culprit may be that the utility score of offspring may be independent of the utility score of the parents even though their parameters are very similar.  If this is the case (especially around "good" results) then convergence may be impossible and random search would outperform genetic algorithms.

The other question "Why didn't I ever find the best solution?" could also have a few explanations.  First, you could have just been unlucky - especially if you didn't run your experiment very many times.  Intuitively, a single run searching 10% of the space will have roughly a 10% chance of finding the best solution.  Second, it may be that all antenna configurations which are similar to an optimal solution have low scores.  This would make it less likely to produce the optimal solution genetically.


In the foundational paper of Rabin and Scott, Finite automata and their decision problems, the pumping lemma appears as a lemma (Lemma 8) to the following result (Theorem 9):

  The language accepted by an $n$-state DFA is infinite if and only if it accepts some word whose length lies between $n$ and $2n$.

The pumping lemma implies the $\Longrightarrow$ direction.

It also "gives another proof" that the language $\{0^n 1 0^n : n \geq 0\}$ isn't regular (the original proof in the paper uses Myhill-Nerode theory).


Is there a dynamic programming solution to the student allocation problem?

This sounds like it could be solved using a flow network.

Define the graph $G=(V,E)$ such that:

Add a starting node $s$. It will be the "source" node in the flow-graph.
Add a node $v_{s_i}$ for every student $s_i$.
Add a node $v_{p_j}$ for every project $p_j$.
Add the final node $t$. It will be the "sink" node for the flow-graph.

Now, start adding the edges and their weights as following:

For every $s_i\in S$, add an edge $(s,v_{s_i})$ of weight 1.
For every $s_i\in S$ and every preferred project of his, $p_j$, add an edge $(v_{s_i},v_{p_j})$ with weight 1.
Finally, for every project $p_j$ add an edge $(v_{p_j},t)$ of weight $c$.

Run the Ford Fulkerson algorithm on this graph $G$ we defined, and it will spit out an integer flow $f$. Assign a student $s_i$ to project $p_j$ if there is flow between $v_{s_i}$ and $v_{p_j}$ in $f$. Notice there might be students that wont be assigned anything in that way. They cannot be assigned to anything they prefer - so just assign them in any free project.

This algorithm runs in time $\mathcal O(|S||P|)$ since $|V|=\mathcal O(|S|+|P|)=\mathcal O(|P|)$, and each student has up to 3 preferred project so $|E|=\mathcal O(|V|)=\mathcal O(|P|)$ as well and the value of $f$, $|f|\le|S|=O(|S|)$.

It also provides the best possible solution, since it always maximizes the flow's value which is the number you want to maximize (think why).


Reducing the vertex cover problem to a variation of the vertex cover problem

One note is that you'll have to use $k$ in your transformation.

Here's one approach that I think works:

We want some $G' = (V', E')$ that has a vertex cover of size $\le \frac{|V'|}{4}$ iff $G$ has a vertex cover of size $\le k$.

If $k = \frac{|V|}{4}$, just set $G' = G$.

When $k \neq \frac{|V|}{4}$, one idea is to add a disconnected graph $H$ to $G$, where we know the vertex cover size of $H$.

Case 1: $k > \frac{|V|}{4}$. Then we want to add a graph with a small vertex cover. A star graph should do it. A star graph $H$ with $m$ vertices has vertex cover size $1$.

Set $G' = G \cup H$, a graph with $|V| + m$ vertices. It has vertex cover of size $\le k+1$ iff $G$ has a vertex cover of size $\le k$.

What should $m$ be? Let's solve

$$\frac{k + 1}{|V| + m} = \frac{1}{4}$$

This gives $m = 4(k+1)-|V|$. So when $k > \frac{|V|}{4}$, add a disconnected $[4(k+1)-|V|]$-vertex star graph to $G$, and call the $\frac{|V|}{4}$ vertex cover algorithm on that. $\square$

Case 2: $k < \frac{|V|}{4}$, we can add a complete graph with some properly chosen number $m$ vertices*. Will leave it at that.

*In this case when you solve for $m$, $m$ may not always be an integer; this can be dealt with by adding a $\lceil m \rceil$-vertex complete graph, which "overshoots" a bit, and then adding a small star graph

[Let me know for further clarification/etc]


The idea is to store a counter $n_a(w) + n_b(w) - 2n_c(w)$ in the stack. If this number is positive, say $x$, we want to have $x$ many P's on the stack (and nothing else). If this number is negative, say $-y$, we want to have $y$ many N's on the stack (and nothing else). Otherwise we want to have a special indicator $O$ on the stack. At the end, we check that the stack consists of $O$.

I'll let you work out the details.


The starting point is the limit
$$
\lim_{n\to\infty} \frac{\log n}{n} = 0,
$$
which can also be stated succinctly as $\log n = o(n)$. If $f(n)$ is any function such that $\lim_{n\to\infty} f(n) = \infty$, it then follows that
$$
\lim_{n\to\infty} \frac{\log f(n)}{f(n)} = 0,
$$
or more succinctly, $\log f(n) = o(f(n))$. In particular, taking $f(n) = \log n$ we get $\log\log n = o(\log n)$, taking $f(n) = \log\log n$ we get $\log\log\log n = o(\log\log n)$, and so on.

More generally, if $a(n) = o(b(n))$ and $f(n) \to \infty$ then $a(f(n)) = o(b(f(n))$. (The case above was $a(n) = \log n$ and $b(n) = n$.) There are similar rules for big O, which I leave for the reader to discover.


Contrary to Church's lambda calculus, Haskell is typed.

Answer 1

When types are denoted with lower-case letters (such as p1 and p2) that indicates a type variable. When types are denoted with capital letters (e.g. Bool or Int) they're concrete types.

The type p1 -> p2 -> p2 indicates a function in curried form. You can think of it as a function that takes a p1 value as input and returns a new function of the type p2 -> p2, or you can think of it as a function that takes p1 and p2 as inputs, and returns p2 as output. The right-most type indicates the return type.

The types p1 and p2 are here unconstrained, which means that they can be literally any type - Bool, Int, or your own custom type(s). They can also be equal. For example, both p1 and p2 could be Bool.

The interpretation of p1 -> p2 -> p2 as a function that takes p1 as input and returns a function with the type p2 -> p2 makes most sense. What really happens is that in the expression \x -> \x -> x the second x shadows the first x. If you think of the expression as \x -> (\x -> x), you can see that the returned function is \x -> x, and that it doesn't matter what the 'leftmost' x was. Thus, the type of the leftmost x is irrelevant because the value is never used. It'd be more idiomatic to write the expression as \_ -> \x -> x. The underscore is Haskell's wildcard placeholder, indicating that there's a variable there, but we don't care about it.

In the expression \x -> x, however, the input value is being returned unmodified, so that the type must be p2 -> p2 - i.e. the output type must be the same as the input type.

The expression \x -> x is the identity function, and it's already built into Haskell as the function id. Likewise, a function that ignores its input and instead always returns the same result is called const. Thus, the expression \x -> \x -> x is equivalent to const id.

Answer 2

The expression \x x -> x is invalid in Haskell. It would indicate a (curried) function that takes two arguments, but returns a value. Which one of them? Keep in mind that they could be different.

In Haskell, variables are bound to input arguments, but the binding must be unambiguous. That's the way that the language works, but it's quite a standard design.

For an example of a language that behaves differently you might look to Erlang, where a function that receives two arguments with the same variable name indicates a pattern-match where the match only succeeds if the arguments are equal to each other. Erlang is the only language I'm aware of that does it that way, but I only know a handful of languages...


How can one tell when will the state of the circuit components change?

It is not necessarily true, this is only one possible way of achieving synchronization. One could arbitrarily decide that it happens when the signal is low, or when the signal goes from low to high (rising edge), or high to low (falling edge), or even both. This wikipedia page contains more information.


Depth First Search to find Minimum spanning tree

No you wont. Suppose you have as graph the complete graph $K_n$ with $n\ge 4$, for simplicity we pick the $K_4$, but this construction works for all larger $n$.

Every DFS-tree of a complete graph is a path, no matter how you order the edges. But clearly you can define the weights such that a non-path is the MST. See the example below (MST in red).


Is oracle computer capable of doing infinite loops?

I'm with Yuval Filmus on this. Oracle seems to be the wrong characterization. An oracle is normally thought of as something that can decide a problem asymptotically faster than a Turing machine (or at all, for undecidable problems).

What you're describing sounds, perhaps, more like hypercomputation. Consider, for instance, a Zeno machine. It could output "True" after 1 minute, "False" after an additional 30 seconds, "True" 15 seconds later, and so on, completing the task you set out for it in two minutes.


Show that the regular languages are closed against taking "the second half"

Hint: if $L$ is regular, the reversal $L^R$ of the language $L$ is regular; see How to show that a "reversed" regular language is regular.  You should be able to use this fact.

Alternative hint: guess the middle point (non-deterministically), then...

Since this is an exercise problem, I am giving only a hint, not a full solution.  Try solving it yourself.


When average , worst and best case time complexity happens in quick sort?

Remember, for big-O we care about the asymptotic limit. If you choose the $k$th largest (or smallest) element, for constant $k$, then when you make $n$ big enough it's as though you chose the single largest or smallest. The $k$ elements on the other side just aren't enough to matter any more. So statement 2 is true.

Statement 1 is also true; you say you understand the proof of it, so I'm not sure how much detail to go into here. But intuitively, the amount on each side of the pivot grows proportionally to $n$. That's what makes it different from the constant $k$.


Dynamic Programming, Binary Tree: How to factor in depth to recursion?

Turns out that I had a misunderstanding of the scope of dynamic programming.  As I understood it, I was "not allowed" to capture other things outside the recursion besides elementary operations.

So, I just have to literally calculate the sum of values lower than the root on either side to factor in the depth:

$$
T(i,j) = \sum_{i\leq l < j}f_l + min\lbrace + T(i,k-1) + T(k+1,j)\rbrace: i<k<j
$$

Where I can just calculate the sum outside of the recursion.


Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

See here:

  For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.


If $A$ is m-complete for $\Sigma_n$, is $\overline{A}$ m-complete for $\Pi_n$?

Hint: use the fact that $A\le_p B \iff \overline{A} \le_p \overline{B}$ (the same reduction works for both sides).

Try proving this for $NP,coNP$ first, and then check if your proof generalizes to the n'th level too.


You're almost there. You correctly have
$$\begin{align}
T(n) &= T(n-1)+2n\\
     &= [T(n-2)+2(n-1)] + 2n = T(n-2)+2(n-1)+2n\\
     &= T(n-3)+2(n-2)+2(n-1)+2n\\
     &= T(n-4)+2(n-3)+2(n-2)+2(n-1)+2n
\end{align}$$
and in general,
$$
T(n)=T(n-j)+2(n-j+1)+2(n-j+2)+2(n-j+3)+\dotsm+2n
$$
Now all you need is the base value for the recurrence. Let's suppose that it was $T(0)=0$ (for the big-O estimate it really wouldn't matter if we had had, say $T(1)=3$ as our base).

To get to the base case, $T(0)$, we'd then need $n-j=0$. In that case, we'd have
$$
T(n)=T(0)+2(1)+2(2)+2(3)+\dotsm+2n= \sum_{k=1}^n2k=2\cdot\frac{n(n+1)}{2} = O(n^2)
$$


Recursion problem involving head, tail and xor

Hints:

g1(0) = [0] so you can see that f1 for [0] returns [1] and for [1] returns [0]. From here g1 must be clear.
f2 takes a bit and a list of one element and returns a bit so it is one of the boolean functions of 2 variables (they are only 16)
after you know that g2(0) = 0 and the above hints it is easier to calculate g2

I can propose you to post your answer or I will update my answer after some time to be sure that it was not for homework.


Here is an explanation by example. Let $\Theta'(f) = \{ g : g(n)/f(n) \text{ tends to a positive limit} \}$. I will show that $\Theta'(f) \subseteq \Theta(f)$. The first step is to write the definitions. There are several variants of the definitions, and I picked one arbitrarily; you should use the definitions that were stated in class.

  Let $f\colon \mathbb{N} \to \mathbb{N}$.

  $\Theta'(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $x \in \mathbb{R}_+$, $\lim_{n\to\infty} g(n)/f(n) = x$.
  $\Theta(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $a,b \in \mathbb{R}_+$ and $n_0 \in \mathbb{N}$, for all $n \geq n_0$ it holds that $a f(n) \leq g(n) \leq b f(n)$.

The next step is to take a function $g \in \Theta'(f)$.

  Let $g \in \Theta'(f)$. Then there exists a positive $x \in \mathbb{R}_+$ such that $$ \lim_{n\to\infty} \frac{g(n)}{f(n)} = x.$$

Finally, we have to show that $g \in \Theta(f)$. For that we have to come up with positive $a,b \in \mathbb{R}_+$ and $n_0 \in \mathbb{N}$ such that $af(n) \leq g(n) \leq bf(n)$ for all $n \geq n_0$.

  By the definition of limit, there exists $n_0$ such that for $n \geq n_0$,
  $$ \left|\frac{g(n)}{f(n)}-x\right| \leq \frac{x}{2}. $$
  Therefore for $n \geq n_0$,
  $$ \frac{x}{2} \leq \frac{g(n)}{f(n)} \leq \frac{3x}{2}, $$
  implying
  $$ \frac{x}{2} f(n) \leq g(n) \leq \frac{3x}{2} f(n). $$
  Taking $a = x/2$ and $b = 3x/2$, we see that $g \in \Theta(f)$.

Only the latter two steps really belong to the proof. The first one states the claim. It is a very important step — without knowing what you're trying to prove, you won't be able to prove it.


If one-way functions exist are we definitely using them?

One-way functions are an asymptotic concept. A function such as modular exponentiation with specific parameters doesn't qualify for being a one-way function since it only exists for a specific size. The same can be said about hash functions such as SHA1. In order to ask the question, you will need to specify an infinite family of functions of the type you're interested in.

Once you've specified your infinite family of functions, the answer to both of your questions is negative: even conditional on the existence of one-way functions, we don't know whether these particular families are one-way, and conversely, it could well be that one-way functions exist, but these families are not one-way.

Should we care? Probably not. Even if a family of functions is one-way, that doesn't mean that using one of these functions is secure. One-way functions is an asymptotic concept, and a family of one-way functions can have significant weaknesses unless the key length is $10^{100}$, and still be one-way. What we need is more concrete guarantees.

In practice, functions we use are deemed secure since generations of researchers have tried to break them and failed (or at least failed to let us know that they succeeded). There is no relation to theoretical cryptography.


How to define the Atomic Propositions in Model Checking

Formal verification often involves at least three steps:

Make a formal model of the real-world system.  (The formal model might be a state-transition graph or automaton, for example.)
Write down a specification that hopefully captures the real-world requirements.
Verify that the formal model of the system meets the specification.

Formal methods provides guarantees about step 3; if step 3 succeeds, then we know that the formal model meets the spec.  It doesn't provide any guarantees about steps 1 or 2.  If there is a bug in the model, that causes it to fail to accurately capture the behavior of the real-world system, then the result of the verification process becomes meaningless and all guarantees are off.  So, you need some separate way to gain assurance in those steps.

The atomic propositions are part of that modelling process.  Usually, there are some parts of the real-world system that we model in the state-transition graph and others that we don't.  For instance, consider a traffic light.  It has some sensors to sense presence of cars and pedestrians; some logic to determine what color light to show in each direction; and some actuators (light bulbs) to actually display those chosen colors.  We might choose to model the logic in a formal model, and verify that the logic works properly.  This verification process might not verify anything about the sensors or the actuators; it might just assume they are correct.  That might be justified if, for instance, we think the logic is the part that is most likely to have subtle errors.  Then you might have an atomic proposition for "sensor #1 detected a pedestrian at such-and-such cross-walk" ($p_1$) and an atomic proposition for "turn on the green light facing in the N direction" ($q_N$).  Those atomic propositions represent the inputs or outputs to the logic, or facts about the state of the system.  The spec then has to be stated in terms of the atomic propositions, e.g., "it should be impossible to have the green light turned on in the N direction and in the E direction" ($G (\neg q_N \lor \neg q_E)$).


Does XML covers the representation of any structured data and knowledge

XML is nothing more than a well-defined way to store trees of strings. Since even plain strings can encode everything you can encode in practice (i.e. countable sets), yes, XML can "model" everything.

But that's nothing special.

The popularity of XML is probably due to

it being standardized and
the amount of tool support that has developed.

There is no information-theoretic miracle involved.


Why is c) a combinational circuit, but d) not?

A combinatorial circuit corresponds to a "straight-line program" that computes the outputs of the circuit given its inputs. (It has to satisfy some constraints that will exclude circuit (f) among others.)
As an example, if we denote the inputs of circuit (c) by $x_1,x_2,x_3,x_4$ (top to bottom) and the output by $o$, then using $g_1,g_2$ for the intermediate gates, the circuit corresponds to the program

$g_1 = x_1 \land x_2$
$g_2 = x_3 \land x_4$
$o = g_1 \lor g_2$

It also corresponds to the formula $(x_1 \land x_2) \lor (x_3 \land x_4)$. However, not every circuit corresponds to a formula. (The difference is that in some circuits, the output of a gate can appear as an input to more than one gate.)
Circuit (d) cannot be written in this form, since the outputs of I3 and I4 are wired together. What is the relation between the input to the rightmost gate and the outputs of I3 and I4? Not something that can be described combinatorially.
The difference between circuit (c) and circuit (d) is that in circuit (c) wires are not joined together. Rather, the output of each of the AND gates is connected to its own input of the OR gate. In contrast, in circuit (d) the rightmost NOT gate has only one input, but two incoming wires that must share the same input pin.


The main differences are along two dimensions -- in the underlying theory,
and in how they can be used. Lets just focus on the latter.

As a user, the "logic" of specifications in LiquidHaskell and refinement type systems generally, is restricted to decidable fragments
so that verification (and inference) is completely automatic, meaning one does not require "proof terms" of the sort needed in the full dependent setting. This leads to significant automation. For example, compare insertion sort in LH:

http://ucsd-progsys.github.io/lh-workshop/04-case-study-insertsort.html#/ordered-lists

vs. in Idris

https://github.com/davidfstr/idris-insertion-sort/blob/master/InsertionSort.idr

However, the automation comes at a price. One cannot use arbitrary functions as specifications as one can in the fully dependent world,
which restricts the class of properties one can write.

Thus, one goal of refinement systems is to extend the class of what
can be specified, while that of fully dependent systems is to automate
what can be proved. Perhaps there is a happy meeting ground where we can
get the best of both worlds!


Quoted from Chapter 16 of the book:
Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2004):

  (Page 345) We now show that there is no algorithm for solving $k$-set consensus in the presence of $f \ge k$ failures.

and

  (Page 351) Theorem 16.7 There is no wait-free algorithm for solving $2$-set consensus problem in an asynchronous shared memory system with three processors.

The proof is quite complicated. See also the paper: The Asynchronous Computability Theorem for $t$-Resilient Tasks.


Labeling a limited number of points on the screen

Aggregate your data, the setting is in 2D, the number of points is small for clustering, and it will solve the task.

You can use k-means, where $k$ will denote number of labels shown on the screen. Putting labels in place of centroids will with high probability give you good place for labels. If this is not good enough you can refine the placement using iterative method on selected labels by treating them as springs with constraint on minimal distance or solving NLP (Natural Label Placement).

Alternatively you can use dbscan algorithm with $\epsilon$ greater than the size of maximal label, this will give you advantage with no refinement needed but in return you lose control over number of labels displayed.

For more in-depth analysis I recommend the doctoral dissertation Automated Label Placement in Theory and Practice by Alexander Wolff.

There are other approaches like Unaligned Collision Avoidance or simulation by flock where the avoiding/pushing is set greater than labels size. This unfortunately will need more tweaking.