Find a particular connected graph within a complete graph keeping all vertices My problem is as follow, imagine a complete undirected graph with weighted edges, i would like to extract a connected graph keeping all the vertices and where the edge with the highest weight is the minimum one compared to all others possible configurations.

Is there another solution than bruteforce it.

Clearly you can focus on trees, since removing edges can only reduce the weight of the maximal edge. What you're looking for is called a minimum bottleneck spanning tree, and an MST is also a minimum bottleneck spanning tree.

To see why, suppose for the purpose of contradiction that $T$ is an MST which does not minmize the maximum weight. Let $(u,v)$ be the maximal weight edge in $T$, and $T'$ be a minimum bottleneck spanning tree. By our assumption $(u,v)\notin T'$, hence there exists a path from $u$ to $v$ in $T'$ which does not contain $(u,v)$, let us denote this path by $P$. Note that all the edges in $P$ are lighter than $(u,v)$. Remove $(u,v)$ from $T$, now $u,v$ are in different connected components. Suppose $P=(w_1=u,...,w_k=v)$, and denote by $i$ the minimal index such that $w_i$ and $w_{i+1}$ are in different connected components in $T\setminus\{(u,v)\}$. Now, $\left(T\setminus\{(u,v)\}\right)\cup\{(w_i,w_{i+1})\}$ is a spanning tree of $G$ with smaller weight, contradicting the fact that $T$ is an MST.


Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver Those terminologies confuse me. As I understand

SAT solver: decide the satisfiability of propositional logic (using DPLL or Local Search).
Decision procedure is a procedure to decide the satisfiability of a certain decidable first-order theory.
SMT solver is a SAT solver + decision procedure.
Theorem prover indicates something like Dynamic Logic, e.g. the KeY tool
Constraint solver: I don't know.

But I see people calling Z3 a theorem prover. So I don't know how to dishtinguish those terms. And what is the most general term for all of them? Thank you.

SMT solver is a SAT solver + decision procedure

A SAT solver is a solver for a decision problem: the SAT problem is a decision problem. Additionally, this decision problem is "self-reducible":

  The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment

  — (wikipedia)

This means that SAT solvers can also give the satisfying assignment, in addition to deciding the problem.

TL;DR SMT solvers solve a generalization of the SAT problem, depending on the types/constraints allowed in the theory. Furthermore, they also allow encoding of higher level type-relationships than the SAT encodings allow.

A SAT solver usually deals with many single boolean variables, that are related only through the clauses/constraints of the CNF. A QF_BV (quantifier-free bitvector) theory SMT solver is basically a SAT solver + more information about the relationships. For example, a QF_BV SMT solver is reducible to SAT1. So why use a QF_BF SMT solver? The the major advantage is that in SAT, an integer is represented by different variables, that at first glance might appear unrelated. A SAT solver would spend much time relearning simple relationships, like $(A = B) \wedge (B = C) \implies (A = C)$ on an integer level, while the SMT solver knows that the individual bits are related this way from the outset, because the QF_BV SMT language is on an integer level (fixed bit-width). Thus a QF_BV SMT solver can reason on the integer level, in addition to the bit level.

See Beaver SMT solver which can even output the equivalent SAT problem that would need to be solved.

While the QF_BV SMT solver has this advantage over a SAT solver, I don't think this is a complexity advantage: they both essentially equivalent and take exponential time to solve their worst-case problems. But practically, a QF_BV SMT solver might be much quicker due to this extra knowledge. See my answer to Limits of SMT solvers, for an example of something considered "hard" that (current) QF_BV SMT solvers and SAT solvers would both choke on.

There are also SMT solvers that try to solve even tougher problems than Boolean Satisfiability (for example allowing types and constraints on reals, or allowing quantifiers); obviously these are theoretically at least as slow as a SAT solver. These SMT solvers are a solving a generalization of the SAT problem; instead of using binary variables, each "theory" allows relationships/constraints over different domains, such as reals, or quantified (for-all) constraints.

  Theorem prover

A automated theorem prover is a solver that given some sort of proof system, some assumptions, and a goal to prove, will "fill in the gaps" between the assumptions and the goal. It will also have some sort of verifier to check proofs (which runs quickly). A theorem prover can rely on a SAT solver to fill in the blanks; in fact, if $P=NP$ and there is a practical algorithm to solve NP-complete problems, one can potentially prove almost all useful provable things (in reasonable time):

  But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook, [19]

    ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.

  — (wikipedia)

  [19]: Cook, Stephen (April 2000). The P versus NP Problem. Clay Mathematics Institute (PDF).

The reason this would work is because "formal proofs can easily be recognized in polynomial time" via the verifier, and $P=NP$ would imply that that problems that can be verified in polynomial time can be answered in polynomial time as well.

But for now, automated theorem mostly provers use heuristics or exponential time algorithms (but are still helpful).

  Constraint solver

These are usually reformulations of the SAT/SMT solvers into other languages. If you've ever use any SAT/SMT solvers to solve a problem, you can really get to love the non-deterministic ability of the solvers. That is, instead of telling the computer how to do something, you tell it what you want, ie. what properties you want the output to have, and a SAT/SMT solver will in a non-deterministic "fill it in", without bothering you with the implementation details. This sort of programming paradigm is very appealing, and is called constraint programming, and to run, it must use a constraint solver (which might use a SAT/SMT solver in the backend, depending on the types and constraints it allows you to use).

  But I see people calling Z3 a theorem prover. So I don't know how to dishtinguish those terms.

AFAIK, Z3 is a suite of many tools, including a SMT solver, several theorem proving/model checking languages, and more.

  And what is the most general term for all of them?

I think the generalization of the satisfiability problem is Satisfiability Modulo Theories, and so "SMT solver" would be the most general of all of these. However, not all actual SMT solver implementations solve all the theories, so this doesn't mean that all SMT solvers are equally general.


Are there problems that are DSPACE(O(1)) complete? I know there are problems that are NL-complete, NP-Complete, PSPACE-complete, etc. Are there problems that are DSPACE(O(1))-complete I.e. NSPACE(O(1))-Complete I.e. Reg-Complete?

Thanks!

YES, there are.

At the beginning of "Andreas Krebs, Klaus-Jörn Lange: Dense Completeness. Developments in Language Theory 2012: 178-189"[Section 6], it is stated that some REG languages with a non-solvable monoid are complete for $\mathrm{NC}^1$ under $\mathrm{DLOGTIME}$-uniform $\mathrm{AC}^0$ reductions. The section goes on to state that a REG language is either in $\mathrm{AC}^0$ or its syntactic monoids are non-aperiodic.

Complexity Zoo states that REG is contained in $\mathrm{NC}^1$.

So, some REG language is complete for the class itself. This is non-trivial.


Problem with the definition of P In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states

  $P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$

"Accepted in polynomial-time" is defined by:

  $L$ is accepted in polynomial time by an algorithm $A$ if it is accepted by $A$
      and if in addition there exists a constant $k$ such that for any length-n string $x\in L$,
      algorithm $A$ accepts $x$ in time $O(n^k)$.

"Accepted" is defined by:

  The language accepted by an algorithm $A$ is the set of strings
          $L = \{ x \in \{0,1\}^* \mid A(x) = 1 \}$,
      that is, the set of strings that the algorithm accepts.

But what if we take $k = 0$, and algorithm $A(\cdot) = 1$, which just returns 1 for everything?
Wouldn't that mean, that $P$ is just class of all languages?

No this means, that the language $L$ that contains all possible words ($L=\Sigma^*$) is in $P$. In other words, no matter what your input is, the algorithm accepts. And the corresponding language is of course (trivially) decidable in polynomial time.

To clarify things: A language is a set of words (the words are considered as encodings of the yes-instances of a problem). A complexity class is a set of languages - so it is a set of sets. When a language $L$ contains all possible words, it doesn't mean that a complexity class that contains $L$, contains all languages.


What the State is, and Where it comes from, when Generating Reachability Graphs For Timed Automata, I found Figure 1 below. For Coloured Petri Nets I found Figure 2. Both are for "Reachability Graph Construction".

However, they don't describe where they got the states from (Figure 3), for generating the reachability graph. They assume you have "states" to generate a reachability graph, but I'm not sure what these states are. In the timed automata case, I'm not sure the automata "states" are what they are describing, it seems like by "state" they mean the program state after the automata runs (or on each step). Likewise for Petri nets, the state isn't the place or the transition, but the program state. At least that's what I'm getting.

Given that, my question is how to construct the program state, so that I can then construct the reachability graph. In addition, I'm wondering what the states actually are composed of. What the state is (boolean predicates, temporal logic expressions, data, etc.).

Some more detail. From here (on Petri nets):

  A marking $M'$ is reachable from a marking $M$ if $M[s\rangle M'$ for some $s \in T^*$... The reachability set Reach(N) of N is the set of
  all markings that are reachable from the initial marking.
  [The markings have to do with the data associated to a place (a Petri net node)]... A Petri net $N = (P, T, F, M_0)$ induces several standard structures on which first-order logics may be interpreted... To specify properties of structures ... obtained from a Petri net $N$, we introduce a first-order logic FO with atomic predicates $x \to y$, $x \overset{*}{\to} y$, $x \overset{+}{\to} y$ and $init(x)$. [Then they go into the model checking part].

That just demonstrates how the Reachability Graph Construction is left out. That is, what it is composed of (in some detail), and how to construct it.

Figure 1 $\downarrow$

Figure 2 $\downarrow$

Figure 3 $\downarrow$

Timed automaton case: Here, a state is typically composed of the current location and the values of all clock variables. Thus, timed automata induce transition systems with an infinite number of states.

The usual approach in this context is thus to build a finite representation of this state set, which is a finite transition system. In the paper "An Efficient State Space Generation for Analysis of Real-time Systems" by Inhye Kang and Insup Lee that you linked to, the state set for this finite transition system is given on page 5, left column. The classical approach involves building a so-called region graph, which is referenced in column 2 of page 4.

Note that CTL model checking of the resulting transition system makes little sense, as the "next-time" operator of CTL does not have a usable semantic in this case. Rather, there are specialized logics (such as TCTL) to reason about properties of timed systems.

Petri net case: In the Petri net case, the states are the possible markings of the network. Note that the state set could be finite or infinite depending on the network. In paper that you referenced ("Petri Net Reachability Graphs: Decidability Status of First Order Properties" by Philippe Darondeau, Stéphane Demri, Roland Meyer, Christophe Morvan), the reachability graph is defined on page 4 as consisting of all markings and having a transition between a marking $M$ and $M'$ if we have $M[t\rangle M′$ some $t$. This notation is in turn explained at the beginning of the page, in Definition 2.


Is complexity of $GI_{di}$ same as $GI_{un}$? Does the graph isomorphism problem for directed graphs($GI_{di}$) reduce to the graph isomorphism problem for directed graphs($GI_{un}$)?

It is clear $$GI_{un}\leq GI_{di}$$ since the set of undirected graphs is subset of set of directed graphs. Does the converse hold true? That is, can an algorithm for undirected graphs used to test for problems in $GI_{di}$ with polynomial increase in complexity? Is $$GI_{di}\leq GI_{un}?$$

The Wikipedia page mentions that digraph isomorphism is GI-complete, and gives a reference. For the proof, something along the following lines should work. Replace each $u\to v$ edges with a path $u\to x\to y\to v$, and attack a clique of size $A$ to $x$, and a clique of size $B \neq A$ to $y$. Choose $A,B > n$ to ensure to these are the only cliques of that size. Instead of a clique you can have a long path or a large star.


How to proof HALT doesn't reduce to L? What method(s) can I use in general to proof HALT doesn't reduce to given language?

Mostly, show that $L$ is decidable, mostly by designing an algorithm to decide it.


Surprisingly high collision rates when hashing a short list with few buckets I'm trying to help my daughter with her CS assignment on hashing. She has an input list of about 4000 English words, each 5 letters long. The prof has limited her to 4000 output buckets (digests? -- it's been a long time since I did this stuff). And the output from the hashing function is an int modulo 4000.

Her naive hash function gets about 1500 collisions. To get something for comparison, I found a handful of hashing functions here and here. I ended up trying almost all of them (oat, fnv, djb, another djb, sax, elf, jsw, and a crc adaptation), because every single one of them got about 1500 collisions. That sure seems like a lot. I'm starting to think maybe we're missing something fundamental. Or not. I don't know.

(I was able to reduce collisions significantly by increasing the number of output buckets to 200k, and returning hash mod 200k from the functions. Naturally, this isn't allowed for the assignment.)

I'm not sure what questions to ask, but the first one that comes to mind is, does 1500 collisions sound about right when using such a small number of output buckets? Or does it sound more like we're doing something totally wrong outside the hashing function? (Presumably not inside it, given that we tried so many different ones.) Or maybe I should ask, is there a way to find out whether 1500 collisions is about right?

Depending on how you count collisions, we can expect either about 2000 collisions, or about 1472 collisions.  The latter is in close agreement with what you observe, so yes, 1500 collisions looks about right to me.

Counting collisions pairwise

I think the most natural way to count collisions is "pairwise".  For instance, if A, B, and C all hash into the same bucket, let's count that as 3 collisions.   If A, B, C, and D hash to the same bucket, let's count that as 6 collisions (not 4, but 6: the 6 collisions are AB, AC, AD, BC, BD, and CD).  And so on.  In general if there are $k$ items in a bucket, that causes ${k \choose 2}$ collisions, with this method of counting collisions.

Then, you can use linearity of expectation to estimate the number of collisions, assuming the hash function is good.  Let $X_{i,j}$ be an indicator random variable that is $1$ if objects $i,j$ hash to the same bucket, or $0$ otherwise.  Let $Y=\sum_{i<j} X_{i,j}$ be the sum of these random variables.  Then $Y$ counts the number of collisions.

Can we estimate a typical value for $Y$?  Well, we can compute the expected value of $Y$ in a straightforward way:

$$\mathbb{E}[Y] = \sum_{i<j} \mathbb{E}[X_{i,j}] = \sum_{i<j} {1 \over 4000} = {4000 \choose 2} {1 \over 4000} = {3999 \over 2} \approx 2000,$$

using the fact that $\mathbb{E}[X_{i,j}] = \Pr[X_{i,j}=1] = {1 \over 4000}$ since there is a 1 in 4000 chance that object $j$ hashes to the same bucket as object $i$ (assuming a good hash function).  Typically, the observed value of $Y$ will be near its expected value.  So, that'd predict that you see about 1500 collisions.  That's a consequence of the number of buckets and the number of items hashed.

In general, if you hash $n$ items into $m$ buckets using a good hash function, you should expect to see about ${n^2 \over 2m}$  collisions, on average, using this method for counting collisions.

Counting collisions by bucket size

On reading your comment, it sounds like you are counting collisions differently.  If there are $k \ge 1$ items in a bucket, it sounds like you are counting that as $k-1$ collisions.  How does that affect things?  Well, it makes the calculation more complicated.  I'll share a much terser analysis for this case, without showing all the details.

Let $N_i$ denote the number of items in bucket $i$.  If the hash function is good, the number of items in a bucket should follow approximately the Poisson distribution with parameter $\lambda = n/m$.  In your case, we have $\lambda=1$.  The total number of collisions (the way you are counting it) is

$$N = \sum_i \max(N_i-1,0).$$

Now,

$$\begin{align*}
\mathbb{E}[\max(N_i-1,0)]
&=
 1 \cdot {\lambda^2 e^{-\lambda} \over 2!} +
 2 \cdot {\lambda^3 e^{-\lambda} \over 3!} +
 3 \cdot {\lambda^4 e^{-\lambda} \over 4!} + \cdots\\
&=
 \lambda e^{-\lambda} + \lambda^2 - \lambda.
\end{align*}$$

(Don't ask me how I summed the series; black magic.)  It follows that

$$\mathbb{E}[N] = \sum_i \mathbb{E}[\max(N_i-1,0)] = (\lambda e^{-\lambda} + \lambda^2 - \lambda) n.$$

In your case $\lambda=1$ and $n=4000$, so we predict $1/e \times 4000 \approx 1472$ collisions.  That has very close agreement with what you are observing empirically, so practice and theory seem to be in close agreement.


Is there Any difference between dynamic programming vs branch-bound vs delayed column generation I was reading about cutting stock problem
https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-Bound and delayed column generation...
I read them but it all look same ...every case we break problem into sub problem

Can anyone shed some more light with some example.?

Dynamic programming is a strategy which avoids explicit enumeration of all possible solutions in the cutting stock problem.
Branch and bound  is a search based technique also based on pruning. However in branch and bound you might in the worst case need to search over all possible solutions.
Column generation is a variant of branch and bound where instead of creating all variables at once they are generated sequentially based on which ones are more "attractive".

In terms of implementation you can implement dynamic programming in any general purpose programming language like C or Java while for column generation  you will need to use specialised linear programming solvers as also for Linear programming based branch and bound.


Non-trivial runs of Prim's algorithm What does it mean when we say that a run of Prim's algorithm is trivial? What are example graphs for either case, that is with and without trivial runs?

Prim's algorithm greedily chooses the smallest edge leaving the set of already connected nodes (until all nodes are connected).

It is not clear what "non-trivial run" means here; I propose this: a run of Prim is trivial if in every step, it can choose the smallest available edge. This would happen on linear chains, for instance.

With this "definition", a non-trivial run is one during which the algorithm can not choose a cheap edge because it would create a cycle, but has to take a more expensive one. Here is an example graph:

[source]

If you start the algorithm with $A$, edge $\{B,C\}$ would be the cheapest after having chosen $\{A,B\}$ and $\{A,C\}$, but it can not be chosen.


What are the mathematical prerequisites for adaptive machine learning algorithms? I am a PhD student in Computer Science who switched his PhD a little bit towards ML algorithms combined with something else... I am an expert in that something else, say image processing, but not an expert in Machine Learning. What should I read/learn to get the ML mathematics right? Especially for adaptive learning algorithms.

The precise mathematical skills that you'll need for your studies will vary depending on exactly which area of ML you'll be working in. In general though Bayes theorem, probability theory and statistics will be your constant companion. Getting a good grasp of these is extremely helpful when it comes to fully understanding how learning algorithms work, and how they can be modified.

Partial differential equations, linear algebra, and mathematical induction are also very important. However beyond these it is difficult to say exactly which areas you should brush up on. In my opinion it depends on what problem you are trying to solve.

For instance is it a regression problem? Is it a classification problem? Are you clustering data? You mention adaptive algorithms, but many ML algorithms could be considered adaptive. As you become familiar with the ML field you'll find that people use different terms to describe exactly the same thing :) a little frustrating to be honest! But the second link you provided is from a non - computer science journal, so just be aware the definition of adaptive in this paper may mean something different in ML. For instance I don't work in adaptive algorithms, but my work has to adapt to high throughput data streams so is most certainly adaptive. But it falls under the category of Semi-supervised learning.

I would recommend taking a look at the following books for more information:

Machine Learning by Tom M. Mitchell, 1997 - This is a great and relatively easy going introduction to machine learning. Despite being over ten years old, this book covers the key topic areas, and introduces you to important concepts. Indirectly this will introduce you to the mathematics of Machine Learning. You'll be able to tell from this book what type of mathematics skills your particular problem may require.

Artificial Intelligence: A Modern Approach by Stuart Russell & Peter Norvig, 3rd Edition, 2009 - All encompassing text (1000+ pages) covers machine learning in great detail. Authoritative text.

Pattern Recognition and Machine Learning (Information Science and Statistics), Christopher M. Bishop, 2006 -  Excellent authoritative text that goes in to ML in great depth. This includes introductory chapters that get you up to speed with the mathematics required to understand learning algorithms (including probability). Can be hard going if you have no mathematics experience.

To support any reading you do I suggest you take a look at the Andrew Ng machine learning course on Coursera. I watched some of these before starting my own study, so too did many of my friends.


How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program? So the wikipedia page gives the following linear programs for max-flow, and the dual program :

While it is quite straight forward to see that the max-flow linear program indeed computes a maximum flow (every feasable solution is a flow, and every flow is a feasable solution), i couldn't find convincing proof that the dual of the max-flow linear program indeed is the LP of the min-cut problem.
An 'intuitive' proof is given on wikipedia, namely : $d_{uv}$ is 1 if the edge $(u,v)$ is counted in the cut and else $0$, $z_u$ is $1$ if $u$ is in the same side than $s$ in the cut, and $0$ if $u$ is in the same side of the cut than $t$
But that doesn't convince me a lot, mainly why should all the variables be integers, while we don't have integer conditions ?
And in general, do you have a convincing proof that the dual of the max-flow LP indeed is the LP formulation for min-cut ?
Edit : Ok i found a proof here http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf , however it only gives a probabilistic way to build the cut from the variables assignement of the LP.

We can write the constraints on the $d_{uv}$ as follows:
$$ d_{uv} \geq z_u - z_v, z_v - z_u $$
$$ d_{sv} \geq 1 - z_v $$
$$ d_{ut} \geq z_u $$
Since we are minimizing $\sum d_{uv} c_{uv}$ and $c_{uv} > 0$, this means that we want to minimize each individual $d_{uv}$, and so in fact
$$ d_{uv} = |z_u - z_v| $$
$$ d_{sv} = 1 - z_v $$
$$ d_{ut} = z_u $$
If we put $z_s = 1$ and $z_t = 0$, then the formula
$$ d_{uv} = |z_u - z_v| $$
holds for all $u,v$.
We can think of $z_v$ as specifying the position of the vertices on the real line. We are penalized $c_{uv} |z_u - z_v|$ for each edge $(u,v)$. Furthermore, $z_s = 1$ and $z_t = 0$. From this description, it is evident that there is no reason to put any vertex beyond the interval $[0,1]$.
If $z_v \in \{0,1\}$ for all $v$, then we can think of the $z_v$ as specifying a cut: one side (which includes $s$) consists of all $v$ such that $z_v = 1$, and the other side (which includes $t$) consists of all $v$ such that $z_v = 0$. If we allow general $z_v \in [0,1]$, then we can think of it as a "fractional cut".
It is natural to ask whether fractional cuts are better than cuts. It turns out that they aren't. The simplest way to see this (same proof as in Luca Trevisan's lecture notes) is to construct the cut randomly: choose a threshold uniformly at random in $[0,1]$, and use it to partition the vertices into those left of the threshold and those right of the threshold. The probability that two vertices $u,v$ are in different sides of the cut is exactly $|z_u - z_v|$, and so the expected weight of the cut is $\sum_{uv} c_{uv} |z_u - z_v|$.
This is a very simple example of the metric method in the design of algorithms.


Is there a crossover operator to cross sections of specific phenotype genes? For example, I've a chromosome with 10 genes, the first 5 genes represent a specific property of phenotype and the last 5 genes represent another property of phenotype.

So, I need a crossover operator that performs the cross considering this configuration, where the parent1's first 5 genes are cross with parent2's first 5 genes and the same for the last 5 genes.

Is there any paper or description of a crossover operator to perform cross in this kind of chromosome?

Let's say you have two parents. For the sake of clarity, let's say that the first five alleles can be either '*' or '-', and the second five either 'x' or 'o'. Our parents might then look like the following.

- - - - - | + + + + +

x x x x x | o o o o o

I'm interpreting the question to mean that you want an operator which only operates on whole phenotypes. As far as I can see, there's only one way to do that, which is to do one-point crossover with the crossover point fixed to the boundary between the two parts.

I question whether this is a good idea. It's a very weak search operator, and in order for it to work reasonably well, I would guess you'd need a very high mutation rate to provide some search power and some sort of elitist selection to keep the mutation from killing your good solutions.

Without more information about your problem, it's hard to say for sure what your needs really are. However, the standard way of handling multiple phenotypic variables is to encode them into a single chromosome, as you've done, but then treat them as one string free of semantics. You just do whatever crossover operator you'd normally do. Yes, that means that your crossover might take part of one property mixed with part of another, but that's what happens in biology as well. In my example, no matter where you put the crossover point, you still get valid offspring. You might do uniform crossover and get children like

- x x - x | o + + o +

x - - x - | + o o + o

but those are perfectly valid offspring. The result is that crossover can explore a much wider part of the search space.

I'm not aware of a reference off the top of my head that compares the two ideas. Probably someone in the early days of GAs has looked at this. But unless you need to cite an authoritative source to justify your decision, I'd say just implement whichever version seems like the right answer for your problem. Both are trivial to code.


Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$? I thought they did, but recently I tried to express $3^n$ as $k \times 2^n + o(2^n)$ for some constant $k$ but wasn't able to. All I found was $3^n = (\frac{3}{2})^n 2^n$. What am I misunderstanding here?
I suppose my question applies to $log_c(n) = O(log_2(n))$ as well.

Additionally to already answered in user5876164's comment let me say, that you cannot express $3^n=k \times 2^n+o(2^n)$, because if we assume it for some $k$, then we obtain: $\left(\frac{3}{2}\right)^n=k+o(1)$, which is impossible, as $\left(\frac{3}{2}\right)^n \to \infty$.


Can a context free grammar for $L$, generate a string not in $L$? from Sipster's definition: Any language that can be generated by some context-free grammar (call it $G$) is called a context-free language (CFL). However, can $G$ generate strings that are not in the the language that recognizes $G$?

By definition, the language generated by a grammar $G$ is the set of all strings generated by $G$. So a grammar generating a language $L$ can generate only words in $L$ (and conversely, it can generate all words in $L$).


Time Complexity analysis for Map-Reduce model I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms.

As a simple example, taking average of n (= 1 billion) numbers can be done on O(n) + C (assuming division to be constant time operation). If i break this massively parallelizable algorithm for Map Reduce, by dividing data over k nodes, my time complexity would simply become O(n/k) + C + C'. Here, C' can be assumed as the startup job planning time overhead. Note that there was no shuffling involved, and reducer's job was nearly trivial.

I am interested in a more complete analysis of algorithm with iterative loops over data and involve heavy shuffling and reducer operations. I want to incorporate, if possible, the I/O operations and network transfers of data.

S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

  Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.


An online parallel algorithm for finding top K elements Suppose we have a function on GPU which calculates elements of array from which we need to select top K elements. The number of elements can be quite big so we can't store them in memory and our algorithm should be online. Another requirement for algorithm is its good parallelization so it could be effectively run on GPU.

Is there any classic approach for the problem? I've thought only of building heap/balanced tree with $k$ elements and inserting new elements into it if new elements is better than existing and popping smaller element. It gives O($n$ log$k$) but it fails with parallelisation because requires synchronization between GPU threads on modifying tree.

Here is one naive solution:
Let the number of parallel processes be $m$. Then, keep a separate buffer/heap/balanced tree for each of the $m$ processes. Divide the range of input into $m$ sections. Whenever you read a number, insert it into the appropriate process' heap. This way, each process only works on its own heap/tree. When you are done with the input, and want to output the top $k$ elements, do a partial mergesort to find the overall top-k.

This will require $O(km)$ space and $O(n\log k + km\log k)$ time.


Understanding recursion tree for withdrawal formula $$
T(n) = T(n-a) + T(a) + cn
$$

Now the solution says that the height of the tree $(h)$ is:
$$
h = \left \lfloor n/a \right \rfloor
$$

And I don't understand why. Maybe I didn't understand the withdrawal formula as needed.

Your recurrence expands into a recurrence tree in the following way. Each node has a label. If the label $n$ is $a$ or smaller, then the node is a leaf. Otherwise, the node has two children, one labeled $n-a$, the other one labeled $a$.

Suppose that you create this tree starting with a root labeled $n$. The root has two children: one is labeled $n-a$, and the other one, labeled $a$, is a leaf. The node labeled $n-a$ has two children, one labeled $n-2a$, and the other one is a leaf. And so on.

It takes roughly $n/a$ steps until this process terminates (since we start with $n$, have to get to $a$ or less, and drop by $a$ each time). Therefore the height of the tree is roughly $n/a$.


How asymptotically bad is naive shuffling? It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

Specifically, since at each of $n$ iterations, one of $n$ choices is made (with uniform probability), there are $n^n$ possible 'paths' through the computation; because the number of possible permutations $n!$ doesn't divide evenly into the number of paths $n^n$, it's impossible for this algorithm to produce each of the $n!$ permutations with equal probability.  (Instead, one should use the so-called Fischer-Yates shuffle, which essentially changes out the call to choose a random number from [0..n) with a call to choose a random number from [i..n); that's moot to my question, though.)

What I'm wondering is, how 'bad' can the naive shuffle be?  More specifically, letting $P(n)$ be the set of all permutations and $C(\rho)$ be the number of paths through the naive algorithm that produce the resulting permutation $\rho\in P(n)$, what is the asymptotic behavior of the functions

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max_{\rho\in P(n)} C(\rho)$

and

$\qquad \displaystyle m(n) = \frac{n!}{n^n}\min_{\rho\in P(n)} C(\rho)$?

The leading factor is to 'normalize' these values: if the naive shuffle is 'asymptotically good' then

$\qquad \displaystyle \lim_{n\to\infty}M(n) = \lim_{n\to\infty}m(n) = 1$.

I suspect (based on some computer simulations I've seen) that the actual values are bounded away from 1, but is it even known if $\lim M(n)$ is finite, or if $\lim m(n)$ is bounded away from 0?  What's known about the behavior of these quantities?

We will show by induction that the permutation $\rho_n = (2,3,4,\ldots, n,1)$ is an example with $C(\rho_n) = 2^{n-1}$. If this is the worst case, as it is for the first few $n$ (see the notes for OEIS sequence A192053), then $m(n) \approx (2/e)^{n}$. So the normalized min, like the normalized max, is 'exponentially bad'.

The base case is easy. For the induction step, we need a lemma:

Lemma: In any path from $(2,3,4, \ldots, n, 1)$ to $(1,2,3, \ldots, n)$, either the first move swaps positions $1$ and $n$, or the last move swaps positions $1$ and $n$.

Proof Sketch: Suppose not. Consider the first move that involves the $n$'th position. Assume that it is the $i$'th move, $i\neq 1$ and $i \neq n$. This move must place the item $1$ in the $i$'th place. Now consider the next move that touches the item $1$. Assume this move is the $j$'th move. This move must swap $i$ and $j$, moving the item $1$ into the $j$'th place, with $i < j$. A similar argument says that the item $1$ can only subsequently be moved to the right. But the item $1$ needs to end up in the first place, a contradiction. $\square$

Now, if the first move swaps the positions $1$ and $n$, the remaining moves must take the permutation $(1, 3,4,5, \ldots, n,2)$ to $(1,2,3,4, \ldots, n)$. If the remaining moves don't touch the first position, then this is the permutation $\rho_{n-1}$ in positions $2 \ldots n$, and we know by induction that there are $C(\rho_{n-1})=2^{n-2}$ paths that do this. An argument similar to the proof of the Lemma says that there is no path that touches the first position, as the item $1$ must then end up in the incorrect position.

If the last move swaps the positions $1$ and $n$, the first $n-1$ moves must take the permutation $(2,3,4,\ldots, n,1)$ to the permutation $(n,2, 3,4, \ldots, n-1, 1)$. Again, if these moves don't touch the last position, then this is the permutation $\rho_{n-1}$, and by induction there are $C(\rho_{n-1})=2^{n-2}$ paths that do it. And again, if one of the first $n-1$ moves here touches the last position, the item $1$ can never end up in the correct place.

Thus, $C(\rho_n) = 2C(\rho_{n-1}) = 2^{n-1}$.


Probable focal point of a set of rays Given a set of two-dimensional rays, how can I determine the probable focal area of the rays?

For simplicity, assume a circle focal area.

Imagine a number of people throwing paper airplanes at a circular target. Some small percent are throwing in the completely wrong direction.

Is there any algorithm that can help me determine a circle (or ideally polygon) of the intended location of the rays?

One possible approach is to try RANSAC.  RANSAC is applicable where we expect: (a) some fraction of the observations (the rays) are erroneous (outliers) and should be ignored, and (b) the remaining ones are all approximately consistent with some low-dimensional probabilistic model.  The RANSAC method then tries to find the best model that (a) minimizes the number of outliers, and (b) among all such models, is as consistent as possible with the remaining observations.

In your case, RANSAC might work well enough.  Some small fraction of the rays are in a completely wrong direction, and will be ignored as outliers.  The remaining ones should all be roughly consistent.  The model could be (for instance) a two-dimensional Gaussian with diagonal covariance matrix.  Such a model has 4 free parameters, so given 2 or more rays, you can fit a Gaussian to it.  Given a model, you can identify which rays are inliers (plausibly consistent with the model) and which rays are outliers.

Given this, one way to apply RANSAC to your problem would be to repeat the following recipe 1000 times:

randomly pick 5 rays
fit a Gaussian to those 5 rays
for each ray, compute the likelihood that it came from that Gaussian, and throw away all those whose likelihood is below some threshold (these are the outliers)
fit a new Gaussian to all those remaining rays (the inliers)
count how many rays remain consistent with the revised model (i.e., count the number of inliers)

Then keep the model with the largest number of inliers, and use the corresponding Gaussian as your model.  In particular, the mean of that Gaussian is your best guess for the target, and the equal-likelihood contour of that Gaussian (the counter corresponding to 2 standard deviations away from the mean) is your circle.  All of the above constants (1000, 5, 2) can be tuned, and variants of this algorithm can be considered.

Why does this work?  Suppose 80% of the rays are correct and 20% are thrown in the completely wrong direction.  Then a random sample of 5 of the rays will, with probability $0.8^5 \approx 0.33$, contain only good rays, and when you fit a Gaussian to them, will give a reasonable estimate of the target and the surrounding circle.  The remaining 67% of samples will have at least one bad ray, which causes a bad model, but the bad models will be thrown away.

The general idea of this sort of approach is: (1) identify a scoring function, which given a model gives you a score for the model; (2) repeatedly pick a random sample of a few rays, fit a model to that sample, use the model to identify outliers, discard the outliers and fit a model to the remaining inliers, and then compute the score of the resulting candidate model; keep the best model you've ever seen.  You can play with the type of model you allow, and the scoring function you use.

Some form of expectation-maximization (EM) potentially might yield even better results.


Efficiently find elements which are out of place in an otherwise sorted list I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the value in Col B breaks chronology in the column.

Structure

    *    Col A    *    Col B    *
    *    Opened   *    Moved    *
Row * --------------------------*
 1  * 06/20 10:00 * 06/22 08:10 *
 2  * 06/20 10:30 * 06/22 08:40 *
 3  * 06/21 10:00 * 06/22 08:30 *
 4  * 06/21 11:00 * 06/22 08:50 *

The table is sorted on Col A, from smallest to largest.

The rule is that the oldest open item should be moved first.
Thus, moving some arbitrary item that isn't the oldest open item is illegal.

Example

The item in row 3 was moved at 08:30, but at that time there was an older item (row 2) that should have been moved first. That means that row 3 represents an illegal operation and should be marked or returned.

My case

My data set is in the range of millions of rows. I need an accurate method for finding these illegal operations, but I am a little stuck on how to approach the problem.

The most workable idea I've had so far, I think, is to build a helper column where the data from Col B is sorted lowest to highest, compare this step by step with the original column, and shift the data downwards every time the data doesn't match. This will leave the helper column with blanks indicating illegal operations in the corresponding row in the original dataset.

Another idea was to compare the current, preceeding and following dates - but this has seemingly expensive weaknesses. Although rare it's conceptually possible that several illegal operations can immediately follow each other, meaning that I have to compare some arbitrary higher number of dates (let's say 15 instead of 2 (the preceeding + following)) for each step in a loop.

While one of these sub-optimal ideas probably will do the work, in the sense that the job gets done eventually, I struggle with the thought that there isn't a better way to solve this.

If I'm understanding the problem correctly, you have a list that's supposed to be monotonically increasing (aka sorted), and need to discard any items that break this rule. The trick being, an item that's greater than its predecessor might still be invalid, if its predecessor was invalid.

I'm going to make one additional assumption: the first row is always correct. (Because I don't see any way it could be wrong, and if there is, you can check that by hand in $O(1)$ before running.)

If this is correct, then here's how I would solve it.

define FlagBadItems(timestamps[0..n]):
    last_good = timestamps[0]
    for item in timestamps[1..n]:
        if item < last_good:
            flag item as bad
        else:
            last_good = item

In other words, we keep a variable called last_good which is the last timestamp we know to be correct. Each row is considered bad if it's lower than last_good. If it's bad, last_good remains the same, otherwise, last_good is updated.

This runs in $O(n)$, since there's a single run through the data set, with constant work per iteration. The space complexity is $O(1)$ for overhead plus $O(n)$ for your input list.


Is it decidable whether a TM reaches some position on the tape? I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$.

  For an integer $c>1$, and the following three problems:

  Is it true that for every input $x$, M does not pass the $|x|+c$ position when running on $x$?
  Is it true that for every input $x$, M does not pass the $\max \{|x|-c,1 \}$ position when running on $x$?
  Is it true that for every input $x$, M does not pass the $(|x|+1)/c$ position when running on $x$?

  How many problems are decidable?

Problem number (1), in my opinion,  is in $\text {coRE} \smallsetminus \text R$ if I understand correct since, I can run all inputs in parallel, and stop if some input reached this position and for showing that it's not in $\text R$ I can reduce the complement of Atm to it. I construct a Turing machine $M'$ as follows: for an input $y$ I check if $y$ is a history of computation, if it is, then $M'$ running right and doesn't stop, if it's not, then it stops.

For (3), I believe that it is decidable since for $c \geqslant 2$ it is all the Turing machines that always stay on the first cell of the stripe, since for a string of one char it can pass the first cell, so I need to simulate all the strings of length 1 for $|Q|+1$ steps (Is this correct?), and see if I'm using only the first cell in all of them.

I don't really know what to do with (2).

Any situation which asks whether a Turing Machine is confined to a finite section of the tape (say of length $n$) on a given input is decidable.

The argument works as follows. Consider the Turing Machine, the tape, and the position of the Turing Machine on the tape.  All together these have a finite number of configurations.  To be specific, there are only $t = n|\Gamma|^n|Q|$ possible configurations.  $\Gamma$ is the set of tape symbols and $Q$ is the set of states.  I'll continue to use the word "configuration" to describe the state of the Turing Machine combined with the state of the tape and its position on the tape for the remainder of this answer, but that is not standard vocabulary.

Run the machine, keeping track of all its past configurations. If it ever goes beyond point $n$, return "yes, $M$ passes position $n$".  Otherwise, the machine is somewhere between 0 and $n$.  If the machine ever repeats a configuration--its state, the symbols on the tape, and its position on the tape are identical to what they were before--return "no, $M$ never passes position $n$."

By the pidgeonhole principle, this has to happen in no more than $t+1$ steps.  So all of the above is decidable; after at most $t+1$ simulated steps you get an answer.

A quick note on why this works: when the machine, the tape, and its position on the tape repeat themselves, there must have been a sequence of configurations between these repetitions.  This sequence will happen again, leading to the same configuration one more time--the machine is in an infinite loop.  This is because we're keeping track of every aspect of the Turing Machine; nothing outside of the configuration can have an impact on what happened.  So when a configuration repeats, it will repeat again, with an identical series of configurations in between.

So confining the tape to a finite part of the string is decidable.  Therefore, by iterating over all possible input strings, the problem is in $\text{coRE}$ for all three questions.  You may have already realized this (between your ideas for 1 and 3 and Ran G's answer for 2 it seems solved completely anyway) but I figured it may be worth posting nonetheless.


Facts about internal and external path lengths of binary tree While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search.

My book specifies some facts about these as follows:

$S_n=1+\frac{U_0+U_1+...+U_{n-1}}{n}$
For large $n$, $S_n=2 \log_en$
Internal path length $I_n$ of binary tree with $n$ internal nodes is at least $n \times \lg(n/4)$ and at most $\frac{n(n-1)}{2}$

Where

$n \rightarrow$ number of (internal) nodes in binary search tree
$S_n \rightarrow$ average number of comparisons required for successful search in a random binary search tree with $n$ internal nodes
$U_n \rightarrow$ average number of comparisons required for unsuccessful search in a random binary search tree with $n$ internal nodes
$I_n \rightarrow$ Internal path length of binary tree with $n$ internal nodes
$E_n \rightarrow$ External path length of binary tree with $n$ internal nodes (not used above)

Out of these I can complete reason out only the maximum internal path length statded in point 3 as follows: It occurs in degenerate binary tree (point 3.6 on this page). In this case, internal path length is $0+1+2+...+(n-1)=\frac{n(n-1)}{2}$.

About the minimum internal path length, the book says following:

  The minimum internal path length occurs in case of the best case binary tree i.e. almost complete binary tree (maximum possible number of nodes having both children). Such tree has $(n+1)$ external nodes at height no more than $\lg {n}$. Multiplying these and applying the below property:
  $$E_n=I_n+2n$$
  we get the bound:
  $$(n+1)\lg n-2n<n \lg (N/4)$$

Q1. However I am still not clear how the above bound is obtained

Q2. Also I did not understood how first two facts out of above 3 are derived and especially what the first fact is meant to imply.

I'm assuming the following model for a binary search tree of size $n$. Consider the following infinite process. At step 0, we have the empty tree. At step 1, we have the tree having some arbitrary value at the root. At step $m>1$, if the current (ordered) contents of the tree at the previous step are $x_1<\ldots<x_{m-1}$, we choose an interval uniformly at random among the $m$ intervals
$$(-\infty,x_1),(x_1,x_2),\ldots,(x_{m-2},x_{m-1}),(x_{m-1},\infty),$$
choose an arbitrary element from the interval, and insert it to the binary tree. A random binary search tree of size $n$ is obtained by stopping this process at step $n$, and erasing the values at the vertices.

You can show that the arbitrary choices do not affect the distribution. Also, the relative order of the elements of the tree at step $n$ (in order of insertion) is a random permutation on $n$ elements.

You haven't explained what you mean by $S_n$ and $U_n$ exactly, so I assume you are using the following definitions:

Let $T_n$ be a random binary search tree of size $n$ before erasing the values. Choose one of the $n$ elements at random, and run binary search on $T_n$ and this element. The average number of comparisons in this process is $S_n$.
Let $T_n$  be a random binary search tree of size $n$ before erasing the values, and let $x$ be the random element inserted by the process at the following step. Run binary search on $T_n$ and $x$. The average number of comparisons in this process is $U_n$.

First fact

Given these definitions, the first fact is easy to prove. Suppose that the element we search for was inserted at step $i$. Note that the distribution of $i$ is uniform over $\{1,\ldots,n\}$. Inserting $i$ at step $i$ requires $U_i$ comparisons in expectation. It takes us the same number of steps to reach this element at the current experiment, and one more comparison to verify that we have indeed found the element. The formula follows.

Second fact

Here we need a non-trivial argument, outlined in the Wikipedia article. Let the sorted elements in the tree be $x_1<\cdots<x_n$. Suppose that the element we look for is $x_i$. The search goes through an element $x_j$ if $x_j$ is an ancestor of $x_i$. Thus, given $i$, the average number of comparisons is $$\sum_{j=1}^n \Pr[\text{$x_j$ is an ancestor of $x_i$}].$$ Now $x_j$ is an ancestor of $x_i$ if among all elements in $\{x_i,\ldots,x_j\}$ (or $\{x_j,\ldots,x_i\}$), $x_j$ was the first inserted. Since the true order of insertion is a random permutation of $x_1,\ldots,x_n$, we conclude that $$\Pr[\text{$x_j$ is an ancestor of $x_i$}] = \frac{1}{|i-j|+1}.$$ Choosing a random $i$, this shows that
$$
\begin{align*}
S_n &= \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n \frac{1}{|i-j|+1} \\ &=
\frac{1}{n} \sum_{i=1}^n \frac{1}{|i-i|+1} + \frac{2}{n}\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{1}{i-j+1} \\ &=
1 + \frac{2}{n}\sum_{i=1}^n \sum_{j=2}^i \frac{1}{j} \\ &=
1 + \frac{2}{n}\sum_{i=1}^n (H_i - 1) \\ &=
\frac{2}{n} \sum_{i=1}^n H_i - 1 \\ &=
\frac{2(n+1)}{n} (H_{n+1} - 1) - 1.
\end{align*}
$$
Here $H_i$ is the $i$th harmonic number, and we used the identity $\sum_{i=1}^n H_i = (n+1)(H_{n+1}-1)$. It is well-known that $H_i = \ln i + \gamma + O(1/i)$ and that $\ln (n+1) = \ln n + O(1/n)$, and so
$$
\begin{align*}
S_n &= 2\left(1+\frac{1}{n}\right) (\ln n + \gamma - 1 + O(1/n)) - 1 \\ &=
2\ln n + 2\gamma - 3 + \frac{2\ln n}{n} + O\left(\frac{1}{n}\right).
\end{align*}
$$

Third fact

The upper bound is given by a path, in which case $I_n = 0 + 1 + \cdots + (n-1) = n(n-1)/2$. For the lower bound, it is easier to consider first the special case $n = 2^m-1$. In that case, the lower bound is given by a balanced binary tree. Such a tree has $2^k$ nodes at depth $k$, and so
$$
I_n = \sum_{d=0}^{m-1} 2^k k = 2^m (m-2) + 2 = (n+1)\log_2 \tfrac{n+1}{4} + 2.
$$
More generally, if $n = 2^m-1+x$ for $x < 2^m$, it is best to put the $x$ extra nodes at depth $m$, and so
$$
\begin{align*}
I_n &= 2^m(m-2) + 2 + mx \\ &= (m-2)(2^m+x) + 2(x+1) \\ &= (m-2)n + m-2 + 2(x+1).
\end{align*}
$$
Notice that $m \leq \log_2 (n+1) < m+1$, that is, $m = \lfloor \log_2 (n+1) \rfloor$. Therefore
$$
I_n = n\lfloor \log_2 (n+1) \rfloor + O(n) = n \log_2 n + O(n).
$$
To get an actual lower bound, notice that
$$
I_n \geq (m-2)n + m > n \log_2 \frac{n+1}{4} \geq n\log_2 \frac{n}{4}.
$$


Relation between logspace-uniform circuits and P-uniform circuits In the book "Computational complexity" of Barak and Arora, on page 112, they state that:

  Theorem 6.15: A language has logspace-uniform circuits of polynomial size iff it is in P.

The proof of this one is left as an exercise to the reader.  I think both directions are trivial:

=> seems trivial, as a logspace TM that generates a circuit also runs in polynomial time, and hence is a P-uniform circuit, which is part of P.

<= seems trivial, as a language that has a polynomial-time TM can be transformed into a circuit with Cook-Levin's theorem in logspace.

However, what I don't get is why the theorem 6.15 explicitly states that the circuits must be of "polynomial size".  How can there exist a logspace-uniform circuit that isn't polynomial in size?  The logspace computable function itself cannot exceed a polynomial bound, how can it produce a circuit of superpolynomial size?

Also, this theorem would imply that logspace-uniform circuits comprise the same languages as P-uniform circuits, which seems very unintuitive to me.
I can't find any information on the relation between logspace-uniform and P-space uniform circuits on the web, so my assumption that they are equal is probably false, but I fail to see see why.

The circuit value problem (CVP) is, given a circuit and an input, to evaluate the circuit. This is a well-known problem which is P-complete with respect to AC$^0$ reductions. Thus one can define P as the class of problems AC$^0$-reducible to CVP. We get the same class if we consider the class of problems polytime-reducible to CVP, or in general $L$-reducible to CVP, where $L$ is any intermediate class between AC$^0$ and P. An $L$-reduction to CVP is very similar to an $L$-uniform circuit (the only difference is that the inputs to the circuit could be any $L$-functions). Specifically, an AC$^0$-reduction to CVP can be converted to a uniform circuit (the notion of uniformity depends on the exact format of circuits, but it can probably be taken all the way down to AC$^0$).

The same phenomenon occurs whenever we have a universal circuit (in the case of P, this is the circuit solving CVP). For a recent example, see this paper on comparator circuits.


What does it mean to multiply or divide polynomials? What does it mean to multiply or divide polynomials?

I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical representation/ interpretation.

I have always pondered what did it mean when someone multiplies a line with a curve to get another hyperplane of a bigger dimension.

I know the formulae and properties of polynomial multiplication & division, I am specifically looking for a graphical/algebraic interpretation of it.

I am a bit uncertain by what you mean by graphical. One notion is to plot or graph a function, like $y=f(x)$, as you would in a highschool level algebra course. Another notion of "graphical" may include some similar to a Cayley graph. I just want to be upfront that the extent of my knowledge does not extend greatly into topology and some algebraic geometry. I will go off on the assumption that overly abstract "graphical" representations do not count.

Graphical Plots: In abstract algebra, the polynomials that work with the $y$ vs. $x$ type of graphing are in the ring of polynomials over $\mathbb{R}$, otherwise known as $\mathbb{R}[x]$. Evaluating any of these for an $x \in \mathbb{R}$ gives you a continuous function that you can plot. This works for $\mathbb{R}[X]$'s extensions, too ($\mathbb{C}[X]$).

Graphs: Cryptography and coding theory involve a massive number of structures, each of which can be represented as a graph. A notable set of examples are graphs depicting algebras over structures of finite size. Rings of polynomials are not one of them, since they contain, at minimum, a countable number of elements. Some intuition can be gathered from how these graphs change as you vary/limit the degree of your polynomial (more on this later). Though I imagine that this is not the kind of representation that you had hoped.

For other graphical/geometrical/topological aspects of crypto and coding theory, you might want to look into things like vector spaces, sphere packing, and lattices.

Polynomials Over Finite Fields:

Even so, it is important to realize that the inclusion of rings of polynomials in cryptography and coding theory are over finite fields. That is, they usually only consider $\mathbb{F}_q[X]$, which is the finite field with $q$ elements. An easily recognized one would be $\mathbb{F}_2^k = \{0,1\}^k$ (your typical algebra over binary strings).

A slight extension of this idea, rings of multivariate polynomials, are also useful. They are typically represented by $\mathbb{F}[X_1,X_2,...]$ where $\mathbb{F}$ is a field. An algebra of multivariate polynomial over $\mathbb{F}_2$ is equivalent to a boolean algebra. A boolean formula, $\varphi(x_1,x_2,...,x_n)$, would be equivalent to evaluating a degree $n$ multivariate polynomial over $\mathbb{F}_2$. The intuition behind this is to see that $+$ and $\times$ act like XOR and AND logic gates on your binary inputs, $x_1,x_2,...,x_n \in \{0,1\}$.

Beyond drawing something fundamentally equivalent to circuit diagrams, I do not see a fruitful way to represent this graphically. Though, this did not stop these guys from trying (I still think it is the same): http://polybori.sourceforge.net/zdd.html

There are obviously way more concepts from abstract algebra that are involved in these areas (e.g. $\mathbb{Z}_p$, the ring integers mod $p$). Some may even have graphical representations that make the idea more intuitive. Though these fall outside the scope of the question, which is specific to algebras over polynomials.


Why, in programming languages in general, must function declarations be followed by a parameter set, external to the sub-routine scope? I understand that in programming languages in general, function routines have what I can generally name a parameter set (or "list"), usually symbolized with parenthesis and if it is not empty, it is also utilized in function calls.

In JavaScript:

function myFunction (passed_parameter_1, passed_parameter_2) {
    // Some code...
}

myFunction(corresponding_passed_argument_1, corresponding_passed_argument_2);

My problem

I never learned in programming courses:

What is the name of that feature
why, in programming languages in general, a user must have this feature, even if the parameter set in routine and the corresponding argument set in call, are both empty.
Why not let a user define a group of parameters (or not) per need, only inside a routine's scope instead

Interim note

One could claim it is needed for a compiler to know what is a function but a keyword such as function reinforce the opinion that it isn't.
One can claim it is needed for separation of internal implementation and external interface but such separation could be done as two different sub-scopes of the main scope ({}), for example:

function myFunction {
    par myPar1
    par myPar2

    // some code

}

myFunction {1,2}

My question

Why, in programming languages in general, must function declarations be followed by a parameter set, external to the sub-routine scope?

In my opinion, your question is formed on the basis of working with a small number of programming languages and extrapolating  conclusions that may not be valid.

Here are some assumptions I have recognised that may not be valid which I will later explore in greater detail:

All function calls must use parenthesis.
All programming languages use these syntactic notations to mean the same thing
There is some common underlying nature that requires things to be like this

I further understand you hinted that you have no significant background in Computer Science theory, but some of the background material to why functions are usually written like this, is about the theoretical evolutionary route that most current languages came from;
So, lets review some of that, as it may help readers (such as students of Computer Science and programming per se) understand your question and our answers more fully.

Consider an early computer language, such as Fortran, which was devised in 1954. It had functions and used parentheses. Actually, at that time the character set available on computer was so limited that it had no other bracketing symbols, and only had upper case letters. It did not have access to []{}<> symbols. Originally all comparisons were made to zero so that comparison operators were not needed, but when they were later introduced they had to be written as .GT. and .LT. due to the lack of characters. The result of this was we could write:

       FUNCTION B
       B=1.0
       RETURN

       FUNCTION C(D)
       C = D
       RETURN

       DIMENSION A(10)
       A(1) = C(1) + B
       STOP
       END

You can see that we have used parentheses for A(1) (which is an array) and C(1) which is a function call, but not for + B which is also a function call. We have used parentheses for A(10) which is an array declaration and also for C(D) which is a function declaration with a formal parameter. Thee design on the language is such that the compiler can work out what is intended and instruct the computer in its machine code to take appropriate actions. However, sometimes this is not convenient for the compiler writer as that may require multiple passes (or readings) of the program to determine what use of parenthesis was intended before determining the semantics of that fragment of code.

Algol 60 also has a similar situation, shown in this example:

  integer function one;
  begin
  one := 1
  end;

  integer function two (integer p);
  begin
  two := p
  end;

  begin
  integer array a [ 1: 10 ];
  a[one] := two(1)
  end

In the above example one is a function that uses no parentheses in its declaration or invocation, whereas two is a function that used parentheses to indicate the formal parameter list (integer p) and also the actual argument (1). this time they are not  confused with arrays at all, because the array exclusively used [] in both its declaration and application. So thus invalidating your assumption on what () might mean.

We also get some symbol overloading in more modern advanced languages. Take Algol 68 for example. It also uses parentheses for arrays and functions (but also almost everything else), but also like Algol 60 that proceeded it, it uses square brackets []:

  ( [] int a := (1,2,3);
      print((a[1])) )

Here '[]' are used to indicate the array declaration, whereas (1,2,3) indicates the array constant used to initialise it. The print statement is even more complex. The inner parentheses (a[1]) indicate an array constant containing one element and the outer print() indicates a function call, and the [1] indicates an array selection operation. The all-encompassing () are used for the program begin and end.

One more historical language is important here, which is LISP. Using LISP we can explore functions as first class objects, lambda functions and other aspects of functions and the notation associated with them. In LISP we can store a function in a named variable like this:

(setq double (function (lambda (x) (+ x x)) ))

Notice that everything is using parentheses; that is the nature of LISP. LISP is constructed entirely of lists denoted by the tuples in parentheses like this:

(x x x x)

Those lists can be either or both data and functions, it makes no difference. Now that the name double contains a function we can do various things with it.

We can invoke the function like this:

(funcall double 11)

This leads into coverage of the notation used in command command languages such as Windows/DOS command prompt and unix shells. In them each line is essentially a function call:

cd path/file

Function calls can be nested by using backtick notation:

cd `which file`

Here no parentheses have been used at all, yet it is a notation familiar to many experienced computer users.

I have not really covered other uses of functions and their notations, such as functions as first class objects, passing functions as arguments, partial parameterisation, lazy evaluation and many many more concepts that could shine a light onto why function notation is as it is. We have to have a notation to ultimately say: This name is a function and I want it to be invoked at this point.

Some of what we are exploring here is the separation between programming language syntax and its semantics. How much of the symbols indicate structure and how much communicate meaning (semantics), and  how can this be determined by automated means. An introduction (to a deeper) theoretical topic can be started by looking at Chomsky Language Hierarchy. Algol 60's nice separation of [] from  () meant that a Context Free Grammar could be used to describe the syntax of the language. Algol 68, in contrast, by the use of symbol overloading (and for other reasons) mean that a more complex Context Sensitive Grammar (known as W-grammars) needed to be used.

The more complex the grammar needed to express the language the more complex the compiler implementation. Language designers wanted both a powerful and expressive language, but also one that could be implemented without undue complexity in the compiler. This often resulted in some stereotyping of language features in ways that were know to be implemented more easily.

In the evolution of languages they developed into different families as they grew from one to another. To prevent the overloading of () meaning begin and end the use of the symbols {} became common place, and the use of [] for array was considered sensible. However many languages use () to indicate both formal parameters and actual arguments, but this is by no means a universal characteristic, and there are exceptions to everything.

When we think that many  languages seem to use the name() notation for function invocation, what we are really seeing is that many languages in common use today inherit a set of notations from the C family of languages through the Algol route. That is all we are seeing is the genealogy of language in the notations.

I hope by a brief tour on the history of the use of parenthesis in the evolution of computer languages and its relation to computer science theory you have gained an insight into what you are trying  to understand.

And if it matters: yes I have worked on Fortran, Algol 60, Algol 68 and other esoteric language compilers


Is the Backus-Naur Form a type 2 grammar? If So why? I understand that the Backus-Naur Form is utilized to assess and specify type 2 grammar, but is it in itself a form of type 2 grammar?

Backus-Naur Form is a conventional notation for writing Context-Free Grammars.

Its usefulness comes from the need to distinguish the character encoding standards that are used to write texts in various computer languages from the higher-order alphabets of terminal and non-terminal symbols (corresponding to lexical units and syntactical variables, respectively) used in the definition of grammars.

The very idea of using CFGs to define the syntax of high-level programming languages was remarkably precocius, which is another reason why the work of John Backus and Peter Naur was so appreciated at the time.


Significance of including $S \to ε$ production rule in regular grammar? Why a production rule $S\to ε$ has been included in the definition of regular grammar? In that case, why it is restricted for $S$ (start symbol) to be present on right hand side of any production rule?

This production rule allows the grammar to generate the empty string. We restrict it to the start symbol so that it can fulfill its function but not interfere with the properties of the grammar in any other way.

In short, it's a hack to allow regular grammars to generate the empty string.


Free and bound variables in a lambda-calculus term For this term:
      $\lambda x.(f (g x))$, what are the free and bound variables?

I'm confused as to how to expand this so it will be easier to see.
If I expand this will it be $\lambda x. \lambda f. \lambda g$?

The free variables in the term you give are $f$ and $g$, $x$ is bound by the $\lambda$-binder.

I am also confused what you mean by "expanding"?  But I guess you want to abstract away those free variables.  If that is true, then you will get $\lambda x . \lambda f . \lambda g . f\ (g\ x)$ (or with the parameters permuted in another way.)


Indexing a huge dataset (that does not fit into central memory) The problem.
Let us consider a huge file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are huge. In particular, neither the entire file nor the list of all distinct strings fit into central memory. The global file may be parsed and/or sorted (in external memory) a few times, though.
The goal is to build the file in which line $i$, for $i=1..m$, is integer $k$ if the string on line $i$ in the original file is the $k+1$-th distinct string appearing in the original file.
Example.
For instance, if the original file is:
bbb
cccc
cccc
bbb
aaa
ee
aaa
fff
dddd
cccc
bbb
fff

then $n=6$, $m=12$, and we should obtain:
0
1
1
0
2
3
2
4
5
1
0
4

My approach.
I take benefit of standard unix command-line tools, as follows.
I first build a numbered string occurence file:
zcat input.gz | awk '{print NR-1,$0;}' | gzip -c > occurrences.gz

I use it to build an index file for strings that respects occurence rank, and starts with character '-', lower than any occurence number:
zcat occurrences.gz |
  sort -T. -S1g --stable -k2,2 |
  awk 'BEGIN{old="none";}{if ($2!=old) print $0; old=$2;}' |
  sort -T. -S1g -nk1,1 | awk '{print "-",$2,NR-1;}' |
  gzip -c > index.gz

I merge the two files and sort the result to ensure that the line with a string index will be just before all other lines containing this string; I then replace each string, sort according to occurence rank, and I am done:
zcat occurrences.gz index.gz |
  sort -T. -S1g -k2,2 -k1,1 |
  awk '{if ($1=="-") i=$3; else print $1,i;}' |
  sort -T. -S1g -nk1,1 |
  cut -d" " -f2 |
  gzip -c > result.gz

Technical detail: to avoid encoding issues, first set environment variable LC_ALL to C.
Question.
Is it possible to do significantly better than my approach, or to achieve similar performances with a significantly different approach, in practice?
Notice that I am not interested in minor, technical improvements, like using mawk, sed, etc, instead of awk. I am not interested in a purely theoretical solution either, that would be better asymptotically but would turn out to be so complex than no implementation is reasonably feasible.
Instead, my concern is the relevance and overall effectiveness of my approach, or variants.
For instance, would any external memory data structure be faster, while using as little memory, with available implementation?

The other approach that I can think of is the obvious one: process the file one line at a time, and consult a dictionary of "seen" lines. What may not be obvious is how to represent the dictionary.
There are plenty of on-disk data structures that would work, and this is a well-researched area given that this is what databases do for a living. Some variant of B-trees, or a hash table (e.g. extensible hashing) would work. Consider Berkeley DB if you need something off the shelf.
If that is too slow, you could use a Bloom filter as an in-memory cache. Then, you need only consult the on-disk data structure if you get a hit in the Bloom filter.


Is this graph algorithm more efficient? Suppose we are given a digraph A. We need to calculate its connectivity digraph B.

I conceived two algorithms:

1.

Set X = A.
Loop
Set Y = X*A united with identity
Stop the loop if Y = X
Set X = Y
End loop
B = X

2.

Set X = A. [Or instead "X = A united with identity" and remove "united with identity" in the third step?]
Loop
Set Y = X*X united with identity [or should it be Y = (X united with identity)*(X united with identity)?]
Stop the loop if Y = X
Set X = Y
End loop
B = X

I think that the algorithms are equivalent but the second one is faster.

Are they really calculating connectivity and are really equivalent?

Is the second algorithm faster not only for incidence matrix representation but also for hash-map or like this representation of digraphs?

Is there an even more efficient algorithm?

You are asking a lot of questions. Let me answer some of them.

Let us denote the contents of the Boolean matrix $X$ after $t$ iterations by $X^{(t)}$. The first algorithm uses the recurrence
$$
\begin{align*}
&X^{(0)}(i,j) = A(i,j), \\
&X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee_k \bigl(X^{(t)}(i,k) \land A(k,j)\bigr).
\end{align*}
$$
You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $t+1$.

The second algorithm uses the recurrence
$$
\begin{align*}
&X^{(0)}(i,j) = A(i,j), \\
&X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee_k \bigl(X^{(t)}(i,k) \land X^{(t)}(k,j)\bigr).
\end{align*}
$$
You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $2^t$.

Since $2^t$ grows much faster than $t+1$, the second algorithm will use less iterations. The worst case number of iterations in the first algorithm is $n$, whereas in the second algorithm this goes down to $O(\log n)$.


Optimal Loading of a Hopping Airplane Minimum Cost Flow Problem I have a Problem with an Optimal Loading a Hopping Airplane example . This is the Part of Minimum Cost Flow Problem.. .. I dont understand a Picture at all. I should to make one example with numbers and i need to show, how could i send flow along the Airline with bigger Revenue und possible smallest cost... Thank you for your Attending..

One approach to understand some complicated situation is to figure out some simplest but still meaningful situations.

In the current situation, let us check a situation when there are only two hops, hop 0 and hop 1. The simpler situation when there is only one hop is too trivial to be instructive, sine there will be no passenger to pick up.

Picking up your pen (or pencil or stylus or your finger), draw the following reduced version of Figure 9.4 in the reference provided.

The above direct network means

there are up to $b_{12}$ passengers at node 1-2 who can be picked up at node 1 (hop 1) and who should be dropped at node 2 (hop 2)
The cost of the arc from node 1-2 to node 1 is $-f_{12}$, where $f_{12}$ is the fare per passenger from node 1 to node 2. That means every passenger picked up will pay $f_{12}$.
The capacity of arc from node 1 to node 2 is $p$. There is no associated cost.
The arc from node 1-2 to node 2 is the imaginary flight with no cost associated nor any capacity limit.
There should be $b_{12}$ passengers reaching node 2. They either take the flight from node 1 to node 2 physically or take the arc from node 1-2 to node 2 virtually without paying any fare.

The minimum cost flow problem for this simple directed network is the following, where $x_{a,b}$ means the number of passengers (the flow) on the arc from $a$ to $b$.

  $$\text{Minimize }\ \ z(x)= (-f_{1-2, 1})x_{1-2,1} + 0x_{1,2} + 0x_{1-2, 2}$$
  subject to
  $$x_{1-2,1} + x_{1-2,2} = b_{12}$$
  $$x_{1,2} - x_{1-2,1} = 0$$
  $$-x_{1-2,2} - x_{1,2} = -b_{12}$$
  $$ 0\le x_{1-2, 1}$$
  $$ 0\le x_{1, 2}\le p$$
  $$ 0\le x_{1-2,2}$$

Why do we want to minimize $z(x)$? Because the total fare collected is $-z(x)$.

All the conditions in the end just means, $x_{1-2,1}\le b_{12}$ and $x_{1-2,1}\le p$. We can solve this problem minimum cost flow easily by letting $x_{1-2,1}=\min(b_{12},p)$, the most passengers available not exceeding the airplane capacity.

Hopefully the above explanation is detailed enough to enable you to further understand the full minimum cost flow formulation for the problem of optimally loading a hopping airplane. You can establish a one-to-one correspondence between feasible passenger routings and feasible flows in the minimum cost flow formulation of the problem.


How a computer ensures that a location in RAM is empty When we declare a variable, how does it get stored in a memory? How does the compiler know from within millions of memory locations which ones are currently not in use or are empty so that it can store the variable there? If it traverses each memory location the whole memory address space and checks on each location whether it is used by some other process or not, it will take like forever until it can allocate memory for a single variable.

In a multitasking system, every process receives its own virtual address space, i.e. the system maps the addresses from $0_h$ to $FFF\cdots F_h$ to available storage space which can reside partly in RAM memory and partly on disk (physical storage). The mapping is made for every process independently, allocating whole pages (typically 2K bytes) at a time.

The compiler is completely unaware of where the data will actually be stored and is free to use the whole address space. The system does the necessary housekeeping and ensures that there are no conflicts.

Actually, the mapping is completely dynamic and pages are moved between RAM and disk, following the needs of the processes and in a way to optimize the access speed. There is not even a relation between the size of the virtual address space and the amount of RAM and disk available.

To summarize, memory allocation is transparent to the compiler, as if the process was alone; only the system knowns which physical pages are free or allocated to a particular process.


String matching algorithm - check if a string matches a pattern This looks like quite the challenge; given a pattern $P$ (of length $n$) and a string $S$ (of length $m$), how would you check whether the string matches the pattern? For instance:

If $P$ = "xyx" and $S$ = "foobarfoo" then $S$ matches $P.$
If $P$ = "acca" and $S$ = "carbuscarbus" then $S$ does not match $P.$

My thoughts so far: This looks like a dynamic programming problem. We can define a boolean

$M(i, j)$ = True iff pattern $P[i:n]$ matches $S[j:m]$

We then need $M(0, 0).$ Note here that the substring notation is $P[i:n] = P_iP_{i+1}...P_n$.

I couldn't think of an efficient recurrence beyond this. It seems like I would have to introduce an extra mapping (from a substring of $P$ to a substring of $S$, indicating that the earlier "matches" the latter; for example in the first example, ("x", "foo") would be part of the mapping. You then replace "x" by "foo" in the substring of P). This would make it $O(2^n)$ or worse though.

If you don't see the intuitive meaning, here's a more rigorous definition: S matches P iff there exists a mapping $$T : P[i:j] \rightarrow S[a:b]$$ for $i, j \in [1, 2 ...n]$ and $a, b \in [1, 2 ...m]$, such that replacing $P[i:j]$ with $S[a:b]$ transforms P into S. For example, in the first case where $P$ = "xyx" and $S$ = "foobarfoo", $T$ is as follows:

T('x') = 'foo'. {Here $i = 1, j = 1, a = 1, b = 3$}
T('y') = 'bar'. {Here $i = 2, j = 2, a = 4, b = 6$}

Replacing all instances (in $P$) of 'x' with 'foo' and 'y' with 'bar', gives us 'foobarfoo' i.e. $S$.

Thus, $S$ matches $P.$

There are various algorithms for pattern matching in string.

Exact String matching algorithms

Brute Force
Rabin Karp
Boyer-Moree
KMP
Aho Corasick etc.

Approximate String Matching Algorithm

Approximate String matching is applied in text searching, pattern
recognition and signal processing applications. For a
text T[1..n] and pattern P[1...m], we are supposed to
find all the occurrences of pattern in the text whose edit
distance to the pattern is at most K. The edit distance
between two strings is defined as minimum number of
character insertion, deletion and replacements needed to
make them equal.

Approximate string matching problem is solved with the
help of dynamic programming.

You can have a look through all these algorithms.
These algorithms will take optimum complexity like O(m),O(n+m) (in case of KMP for example).


$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side.

I need to Show that $L$ is regular.

I'd relly like some help, I tried to think of any way to prove it but I didn't reach to any smart conclusion. what is it about the only side right moves and the regularity?

Hint -- You need to show that your TM has the same power as a finite-state automaton (as the commenter Dave Clarke said), that is, given such a TM, construct a FSA that accepts the same language.

But since the TM has no memory but the tape, ask yourself what a right-only TM can do with its tape.  It should be relatively straightforward to actually construct the parts of the FSA you are looking for. Just go through them -- the states, the input alphabet and most crucially the move function (usually $\delta$) and define them in terms of the parts of the TM you started with. Then you have to show that the two accept the same language, in terms of the definition of "accept" for each, being sure to mention potential looping behavior in the TM.

BTW, this sort of problem is amenable to a pretty convincing "hand-waving" proof that would actually be of a type that is quite acceptable in a research paper.  Your course, however, may be expecting a precise proof, using $\delta$ and the other components of the tuples that constitute the TM and FSA.


Pumping Lemma for single character language I have a question about the Pumping lemma. Condition $2$ of the pumping lemma for a string division $xyz$ states that the middle portion of the string $y^i$ can be 'pumped' for any $i$ greater than or equal to $0$. This means that y can be the empty string and yet still belong to the language. At the same time, the cardinality $|y|$ has to be at least $1$.

How would I be able to apply this if the regular language is only a single character? i.e. $L = \{a\}$. Here, I can set $y = \{a\}$ so that the cardinality is greater than zero --- however, it fails to meet the condition that $y$ can be 'pumped down' to the empty string....

But obviously, $L =\{a\}$ is a regular language.

And there's also something obvious that I missed ...

You interpret the lemma incorrectly. The lemma says that "there is $n$ such that any string $y \in L$, with $|y| \geq n$...". So the lemma does not provide a particular $n$, it only says "there is", not "for all".

If the language is finite then, the pumping length is greater than the longest string in the language. And hence the three conditions of the lemma fails for all strings in the language, meaning there is nothing to "pump". Nevertheless, the lemma holds. Just recall the implication rule $p \implies q$: if $p$ is false then it does not matter if $q$ is true or false, the whole implication is true.

In your example with a single string $a$ take $n$, the pumping length to be $2$. So there is no string of the length greater than or equal to $2$. But it does not mean that the lemma fails.

Update:: the following predicate formula expresses the Pumping lemma for regular languages $$[ L \text{ is regular }] \implies [\exists n\forall x[ \left((x \in L) \land (|x| \geq n) \right)
\implies
(\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| > 0 \land \forall m[m>0 \implies uv^mw \in L))]]]$$

and this is antecedent (conclusion) part of the lemma:
$$\exists n \forall x[ \left((x \in L) \land (|x| \geq n) \right)
\implies
(\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| > 0 \land \forall m[m>0 \implies uv^mw \in L))]]$$

This premise of the antecedent $(x \in L) \land (|x| \geq n)$ is false since $|x|$ is less than $n$ (for each $x \in L$) and hence the whole antecedent is true.


Different probabilistic statement for Simple Uniform Hashing Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them into equations and realize which of the different equations are equivalent and which are not.

Simple Uniform Hashing as described by CLRS in page 259 says:

  we shall assume that any given element is equally likely to hash into any of the m slots, independently of where any other element has hashed to.

So for that description I would mathematically write:

$$ Pr[h(k) = i] = \frac{1}{m}, \forall i \in \{0,...,m-1 \}$$

i.e. the probability that h(k) hashes to any index $i$ is equal to any index in the table of size $m$. Furthermore to satisfy the independence condition it requires I would also write:

$$ Pr[h(k) = i] = Pr[h(k) = i \mid Ops] = \frac{1}{m}, \forall Ops $$

Where $Ops$ is any set describing the keys that might have been hashed before $k$. So its conditionally independent of anything that might have happened before. Those are the equations and maths expressions I would use to describe uniform hashing.

However on page 260 (and on wikipedia ) we have a slightly differently phrased equation which I am having a hard time realizing if its the same as the one I wrote above which says:

$$ Pr[h(k_i) = h(k_j) ] = \frac{1}{m}, k_i \neq n_j$$

i.e. the probability that two non-equal elements map to a spot of the table is $\frac{1}{m}$.

Are these two definitions the same? Why is the second used moe often than the first?

They're not the same, but the one in Wikipedia is a consequence of the simple uniform hashing assumption.

Let $E$ be the event that $h(k_1)=h(k_2)$.  Let $F_x$ denote the event that $h(k_1)=h(k_2)=x$.  Note that

$$E = \bigcup_x F_x,$$

and the events $F_x$ are disjoint.  Therefore,

$$\Pr[E] = \sum_x \Pr[F_x].$$

Now under the simple uniform hashing assumption,

$$\begin{align*}
\Pr[F_x] &= \Pr[h(k_1)=x \land h(k_2)=x]\\
&= \Pr[h(k_1)=x | h(k_2)=x] \times \Pr[h(k_2)=x]\\
&= \frac{1}{m} \times \frac{1}{m}\\
&= \frac{1}{m^2}.
\end{align*}$$

Plugging in, we find

$$\Pr[E] = \sum_x \Pr[F_x] = \sum_x \frac{1}{m^2} = \frac{1}{m}$$

since there are $m$ possible values of $x$.

Therefore, if the simple uniform hashing assumption holds, then the equation you found in Wikipedia also holds.  The reverse isn't necessarily true.


Natural deduction proof: distributivity of existential quantification In a current exam-prep exercise, we were tasked to prove the following formula using natural deduction of first-order logic:

$(\exists x. P \lor Q) \rightarrow P \lor (\exists x.Q)$ for arbitrary $P,Q$ where $P$ does not have free occurences of variable x.

I managed to do the prove, until I arrived at the following:

$\frac{}{\exists x.P\lor Q, P \lor Q \ \vdash \ (\exists x. P) \lor (\exists x.Q)}$

Unfortunately, applying $\lor-elimination$ only strengthens what I need to prove, so applying that doesn't work. In general, whichever rule I try to apply, I cannot get far. I also cannot apply $\exists-elimination$, as the $Q$ in $P\lor Q$ is not guaranteed to have only bound occurenes of x.

Actually, $\frac{}{\exists x.P\lor Q, P \lor Q \ \vdash \ (\exists x. P) \lor (\exists x.Q)}$ is just a rewritten form of  distributivity of existential quantification: $\frac{}{\vdash \ \exists x.P\lor Q \rightarrow (\exists x. P) \lor (\exists x.Q)}$.

How shall I proceed in the prove?

You didn't say exactly what you tried, but it looks like you're trying to get there by applying elimination rules. That's not the simplest approach, and it might not work directly without case analysis on $P$ and $Q$ (I haven't tried). There's a very powerful theorem about natural deduction and most other basic logical framework: if there's a way to derive a proposition, there's a way to derive it without using elimination rules. This is called normalization. In the Curry-Howard correspondence, normalization of derivations corresponds to evaluation of programs and an introduction-only proof is a value (program with only constructors).

To prove that $(\exists x. P \lor Q) \rightarrow P \lor (\exists x.Q)$, let's use $\rightarrow_I$: we need to prove that if there's a derivation of $\exists x. P \lor Q$ then there's a derivation of $P \lor (\exists x.Q)$.

If there's a derivation of $\exists x. P \lor Q$, then there is a normal derivation of it, and in particular there is a derivation ending in $\exists_I$. The premise of this derivation is $[t/x](P \lor Q) = ([t/x]P) \lor ([t/x]Q)$ for some term $t$. This proposition itself has a derivation ending in one of the introduction rules for disjunction: either $_I\lor$ with the premise $[t/x]P$ or $\lor_I$ with the premise $[t/x]Q$. In the first case, we have a derivation of $[t/x]P = P$. In the second case, we can apply $\exists_I$ to derive $\exists x. Q$. In the first case, we can then derive $P \lor (\exists x. Q)$ with $_I\lor$. In the second case, we can derive the same proposition $P \lor (\exists x. Q)$ with $\lor_I$. We've shown that if there's a derivation of $\exists x. P \lor Q$ then there's a derivation of $P \lor (\exists x. Q)$, QED.


Getting N top scores from a matrix I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example:

M[4][4] = {
    (13, 8, 5, 3),
    (11, 9, 7, 4),
    ( 8, 6, 2, 1),
    ( 6, 5, 4, 1)
}

So the top 6 scores of that matrix will be:

top_scores = {
    (13, 11, 8, 6), // 38
    (13, 11, 8, 5), // 37
    (13, 11, 6, 6), // 36
    (13, 11, 8, 4), // 36
    (13,  9, 8, 6), // 36
    (13, 11, 6, 5), // 35
}

What I want is to get the best scores directly, not calculating all the possible combinations and picking the top ones, because the matrix can be much bigger. I've tried to solve it with different approaches, but I failed in all of them.

What you want to do is view your problem as a problem on a directed layered graph. This will allow you to solve the problem using algorithms for the $k$-th shortest paths problem.

In your example you would construct this graph:

The arcs with no label have weight zero.

Finding the $k$-th shortest paths from $s$ to $t$ will find the $k$ top scores according to your definition. There are many efficient algorithms for obtaining the $k$-th shortest paths, including a variation on Dijkstra's algorithm which is probably the easiest to implement.

PS. Some of these algorithms require that the weights of the arcs be non-negative. That can be easily achieved in your case, by adding a large enough constant to every weight, e.g., shifting every weight by +13 in your example. The result is equivalent, since all the paths from $s$ to $t$ contain the same number of arcs.


Expected number of common edges for a given tree with any other tree So I am working on a problem where I have a set of (labeled) nodes and I have a tree structure (rooted) over that set of nodes. The goal for me is to automatically generate that tree structure. To find the performance of my algorithm, I am trying to use the score as the fraction of edges that I have common in the generated tree and the given tree. I want to compare this score with an expected value of the fraction if we generate the tree randomly (equal probability for all tree structures). What should be my approach to find this? Is there a computable efficient method for this? The brute force method (with some optimizations so that I only iterate on the structure without the labels) usually fails over n>10.

I understand if there is some efficient method to find no. of trees with k common edges then my problem is solved to much extent, but I am having a hard time to solve this as well.

EDIT: The edges are considered to be directed, towards the root.

Let $T$ be your reference tree (on $n$ vertices), and let $R$ be the random tree. Label the edges of the tree randomly from $1$ to $n-1$. Let $X_i$ denote the event that the $i$th edge of $R$ is an edge of $T$. Linearity of expectation shows that the expected size of $T \cap R$ is $\sum_i \Pr[X_i]$. Each $X_i$ is a uniformly random edge, and so it belongs to $T$ with probability $|T|/\binom{n}{2} = 2/n$. Hence the expected size of the intersection is $(n-1) \cdot 2/n = 2(1-1/n)$.


Use Fact to decompose a given number Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\in$ P then there is an algorithm that given $n$, it produces its decomposition into prime factors in polynomial time in the length of $n$.

I have tried to create this algorithm as follows:
Given $n\in\mathbb{N}$, if $\mathrm{Fact}(2,n)=1$ then $2\mid n$, in which case we take $n_1=\frac{n}{2}$, if $\mathrm{Fact}(2,n)=0$ then we see what happens with $\mathrm{Fact}(3,n)$ and we continue like this, my problem is that this algorithm is done in a time $O(2^n)$ which is not polynomial and all the algorithms that occur to me end in this problem is it possible to do this in polynomial time?

Use binary search to find the smallest factor, divide and repeat.