Given a low resolution video, is it possible to create a higher resolution image This question is purely theoretical as I've not been able to find anyone who's done such a thing, so my question is - is it possible, and if not why?

Say you have a short video (CCTV) of a face, or number (car licence) plate, and that video is of too poor quality to discern who that person is or what the number plate says, would it be possible to combine details from several frames of video to interpolate and thus make a clearer image than can be gained from a single frame?

Surely some frames would contain detail that others lack (due to pixel boundaries, shadows etc)?  Are there any examples of machine learning or CV that  do this?

It heavily depends on the setting, accuracy and goal, but shortly, yes, even considering practical application.

Theoretically of course it is possible, with various (or used together) techniques like sharpening, noise removal, scene reconstruction, frames merging, geometry reconstruction or even motion blur removal. The last one works by solving optic equation and could be used with success if you treat consecutive frames as one speeding object, applying frames as artificial motion blur, for example Practical Layered Reconstruction for Defocus and Motion Blur.
The most straightforward technique would use shifted grids (frames) and after applying constraints from "big pixels" and how they round at the discrete domain the result is in the "reconstruction domain" - all pixels represent ranges of possible chrominance / luminance. The accuracy increases with the number of frames used. Here are two problems: the additional processing is needed to estimate the repative position of frames (which in the case of static camera gets easier - the equivalent of motion capture of smart objects) and the number of frames. If these came from different cameras (angles, coordinates, intrisinc camera setting) the scene reconstruction with possibly light oblivious merge (the light condition may vary, it must be equalized).

As stated earlier it depends, the plate recognition is easier, it reduces to contours extraction of low resolution data / blurred setting or image reconstruction discarding colours (which are known and not interesting), with some degree of certainty - the numbers under noise should be matched with patterns.

For the face recognition it gets harder due to unknown pattern, possibly 3D reconstruction from frames, which are low resolution, and hopefully with full colour after processing. This is a part of active research, because many powerful algorithms yield grayscale images.

Generating perceptualy clearer images is quite established field, heavily dominated by SSIM derivative techniques (the theoretical-empirical model for images compression, that could be fed with "reconstruction domain" image and return the most plaussible one), but reconstruction beyond doubt is harder task.

Here are some good to read articles about it:
Super resolution algorithm

An Algorithm for Repairing Low-Quality Video Enhancement Techniques Based on Trained Filter

Video Superresolution Reconstruction Using Iterative Back Projection with Critical-Point Filters Based Image Matching

VIDEO SUPER RESOLUTION RECONSTRUCTION FROM LOW RESOLUTION IMAGES USING SPLINE INTERPOLATION


Big-Endian/Little-Endian argument - paper by Danny Cohen Reading a book I was redirected to "On holy wars and a plea for peace" paper by Danny Cohen, which covers the "holy war" between big-endians and little-endians considering byte-order.

Reaching the summary of the memory section I got confused as the author sais:

  To  the best of my knowledge only the Big-Endians of Blefuscu have
  built systems with a consistent order  which  works  across
  chunk-boundaries, registers,   instructions   and   memories.      I
  failed  to  find  a Little-Endians' system which is totally
  consistent.

Which kind of contradicts his previous text sections covering little-endian:

e.g.

  When they add the bit order and the byte order they get:

               ...|---word2---|---word1---|---word0---|
              ....|C3,C2,C1,C0|C3,C2,C1,C0|C3,C2,C1,C0|
             .....|B31......B0|B31......B0|B31......B0|

  In  this regime, when word W(n) is shifted right, its LSB moves into
  the MSB of word W(n-1).
                                     4

  English  text  strings  are  stored  in  the  same order, with the
  first character in C0 of W0, the next in C1 of W0, and so on.

  This order is very consistent with itself, with the Hebrew language,
  and (more importantly) with mathematics, because significance
  increases with increasing item numbers (address).

he even lateron sais:

  The  Big-Endians struck again, and without any resistance got their
  way. The decimal number 12345678 is stored in the VAX memory in this
  order:

                       7 8  5 6  3 4  1 2
                  ...|-------long0-------|
                 ....|--word1--|--word0--|
                .....|-C1-|-C0-|-C1-|-C0-|
               ......|B15....B0|B15....B0|

  This ugliness cannot be hidden even by the standard Chinese trick.

How did the author get to this completely different conclusion on overall consistency?

An answer does not have to only base on the text, but may also include other sources which might clear up how the statement is sound.

The first statement says that there is a system that consistently uses the big-endian convention for various things (instructions, registers, etc.) The second statement says that the little-endian convention is more elegant ("consistent with itself").

How are these contradictory?


Comb sort average complexity The wikipedia page about comb sort claims that the average complexity of comb sort is Omega(n^2/2^p) where p is the number of increments. Take as example an uniform distributed array of 1000 elements, using the standard shrink factor of 1.3 the length of the gaps list is 23. Is this the p mentioned in the wikipedia article? If it is the complexity is omega of 1000^2 / 2^23 ~ 0.120 Someone could please explain what I don't understand? Thank in advance

The average-case lower bound for uniformly distributed data is $\Omega(\frac{n^2}{2^p})$, $p$ here denotes the number of increments, not actual gaps.

The number of passes is given as the input with gaps, which are in form of list, say $\{k_1, k_2,\dots,k_p\}$ where given $k$ is single increment value. There are $p$ increments to go, this $p$ is in the equation.

To avoid explicit list one may use shrink factor, which behaves similarly to shellsort and use the gap divided by consecutive powers of this factor.


Usefulness of a linked list with a cycle Is a singly-linked list that contains a cycle considered a corrupted data structure or is there some practical use for it?

(You could argue that a car without its front shield is not corrupted, if the owner intends for it to be like that, so lets understand the word "corrupted" in a sense of "damaged into state that it is useless".)

One of the possible ideas that I got is that it can represent some sort of a computation: the initial "non-cycled head" of the list can be viewed as the initialisation phase, whereas the "cycled tail" can serve as a never-ending computation. However, this reasoning is a bit Texas Sharp-shooter fallacy to me.

Any ideas?

In the case of circular linked list - this might be a buffer, neat structure to handle operations that must be consecutive or form a ring (like in parallel programming).

What if not the whole list is cycle?
This might be intended like conflict resolving, and thanks to cycle it will not go further.
It might be the case that every operation changes state so there is cycle, but it will eventually resolve.

If you write a turn-based game with general loop, there might be cycle if user can do something multiple times per turn. So here it is intended.

And totally not constructive - cycle came from bug, so it pushes application into infinite computation.


Is the language in class P So class P is the class of languages that are decidable in polynomial time on
a deterministic single-tape TM.

I can show that the decider for a language L* runs in polynomial time.

So is it true that this language in class P?
STARCLOSED DFA = { | A is a DFA, and L(A) = L(A)*}

A language L is equal to its Kleene closure if and only if L contains ε and L = L^2. So in a sense, this problem boils down to testing whether those two conditions are true. The test for whether L contains ε is pretty easy to accomplish - just see if A's start state is accepting. The trickier part is seeing whether L = L^2.

If you already know that ε ∈ L, then L ⊆ L^2, so the only way that L isn't equal to L^2 is if there's a string in L^2 that isn't in L. This is something we can test in polynomial time, as follows:

Construct an NFA for L^2 by applying the concatenation construction to A and itself. Call the resulting automaton B.
Take the cross product of B and the automaton formed by flipping the accept and reject states of A. Running this automaton corresponds to simultaneously running A and B, with the accepting states corresponding to executions that lead to an accepting state in B and a rejecting state in A.
Run a DFS over this net automaton to find an accepting state. If one exists and is reachable, there's a string in L^2 that isn't in L, and otherwise every string in L^2 is in L.

Step (1) takes polynomial time and builds an automaton with 2n states, where n is the number of states in the original automaton A, since we're just duplicating the states in A and adding in some new transitions. Step (2) builds an automaton with 2n^2 states, and the DFS in step (3) runs in time polynomial in n.

Overall, this construction runs in polynomial time.


Complete proof of PAC learning of axis-aligned rectangles I have already read PAC learning of axis-aligned rectangles and understand every other part of the example.
From Foundations of Machine Learning by Mohri, 2nd ed., p. 13 (book) or p. 30 (PDF), I am struggling to understand the following sentence of Example 2.4, which is apparently the result of a contrapositive argument:

... if $R(\text{R}_S) > \epsilon$, then $\text{R}_S$ must miss at least one of the regions $r_i$, $i \in [4]$.

i.e., $i = 1, 2, 3, 4$. Could someone please explain why this is the case?
The way I see it is this: given $\epsilon > 0$, if $R(\text{R}_S) > \epsilon$, then $\mathbb{P}_{x \sim D}(\text{R}\setminus \text{R}_S) > \epsilon$. We also know from this stage of the proof that $\mathbb{P}_{x \sim D}(\text{R}) > \epsilon$ as well. Beyond this, I'm not sure how the sentence above is reached.

Let $R_S, R_T$ denote the sample rectangle (smallest consistent rectangle) and the target rectangle correspondingly. Since $R_S\subseteq R_T$, $R(R_S)\le \mu\left(R_T\setminus R_S\right)$. The intuition behind taking strips of mass $\epsilon$ around the edges of $R_T$ is that you want to satisfy two conditions:

The strips, $r_1,...,r_4$ should have large enough mass so that with high probability $m(\epsilon)$ samples do not miss them (this would follow from a simple bound for a geometric random variable).

The strips should have small enough mass, so that if all were seen by the samples, then $R_T\setminus R_S\subseteq \bigcup\limits_i r_i$, where the latter union has small probability thus bounding $R(R_S)$.

Your question is settled by the geometric argument in the second point. If all strips were seen by the samples, then we can only err on points in the strips.


Find the efficiency class I have to find the efficiency class of this algorithm

b = 3
a = 4
for i = 4 to n^2
    if (i mod 2 == 0)
        a = a+2
    else
        b = b*3
end for

I solve it like this, first I find the time for executed a then b and the total is the addition, is it right? I'm not sure if I have to do it like this or not, I let $n=\frac{n^2}{2}$ because of the $\bmod 2$ is it right?

$t_a(n)=\sum_{j=1}^{n^{2}/2}1=\dfrac{n^{2}}{2}$

$t_b(n)=\sum_{j=4}^{n^{2}}1-\dfrac{n^{2}}{2}=n^{2}-\dfrac{n^{2}}{3}-3$

$t(n)=\dfrac{n^{2}}{2}+n^{2}-\dfrac{n^{2}}{3}-3=\Theta (n^{2})$ by the polynomial theorem.

The final result is true. But, you have a fault in your computation, as in each iteration you have at least a comparison. Hence, instead of $\frac{n^2}{2}$, we will have $n^2 - 3$. Anyhow, the final result is the time complexity is $\Theta(n^2)$.


What does canonical extension mean? Density-reachability is a canonical extension of direct density-reachability.
What is meant by canonical extension?

Source: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf

The term 'extension' could generally be interpreted in mathematical sense1 as an enlargement of the domain of a pre-existing function.

In your case, assume Density-reachability could be described as a process $d\colon A \rightarrow B$ mapping inputs from domain $A$ to output in domain $B$. An enlargement of domain could be viewed as another map $e\colon A \rightarrow A'$ which maps where the old inputs in $A$ could be thought of as special cases in subset of $A'$ that is the image of map $e$.

An extension then could be described as any map $x\colon A' \rightarrow B$ which statisfy
$$x \circ e = d$$
There could be many such $x$, so picking extension is a choice. The above equation basically expresses that

  If I pick $a \in A$ from the old domain, translate it to the new domain as $e(a)$, then use this new tool $x$ which could be thought of as an extension of old tool $d$ along the translation $e$, then the final result must agree with just using the old tool $d$ to begin with.

or
$$x \circ e(a) = d(a)\qquad; \forall a \in A$$

The term 'canonical' simply implies that the choice of extension is the obvious, natural one of the situation.

1 At least from the perspective of category theory.


How to identify labels in unsupervised learning? Let's say I am working on handwritten digit recognition (0 to 9). I know for instance that if I use clustering then I need to look for 10 clusters. But once I have the 10 clusters,how do I identify automatically which cluster corresponds to which digit?
In general, say I have some other classification task where I don't have the labels for the training data, but I know that there are, lets say, two classes. I want to build a model which can then tell me, for the test instances, which classes they belong to. But again the problem that even if I can group the train cases together, how do I know the actual label of the test instance in this unsupervised setting?

You can't, in a completely unsupervised setting.  You need something more: e.g., a training data set where you have labels for at least some of the instances, or some other information that allows you to set a label for each cluster.

How is the computer supposed to know that a circle means zero as opposed to some other number, if you don't tell it that?  Obviously, it can't.  In fact, in the Eastern Arabic numbering system, there's a zero-looking character that actually means the number 5, not the number 0.  Obviously, a computer can't possibly know which of those two meanings is intended, if you don't tell it somehow.


Execution time estimation I've been trying to wrap my head around the following question for ages, its part of my revision for the upcoming end of year exam, however I fail to see how there is a link from the number to the letter, how will one cycle from 1 to a and iterate to get there? if that makes any sense! We were told that when estimating execution time of a loop, it is likely to be the number of times the loop executes, so therefor a list of length n would take approximately n units of time to execute, that makes sense, its just the cycle from 1-a, then 1-b? like, how many iterations will the loop run to get from 1 to a? it just confuses me! anyhow here it is as on the practice paper:

z := 0
for i from 1 to a
  for j from 1 to b
    for k from 1 to c
      z := z + a*b*c

• How long does it take to compute the k-loop?

• How long does it take to compute the j-loop?

• How long does it take to compute the i-loop?

• How long does it take to compute the algorithm?

There's no list here. In this problem, $a, b, c$ are simply numbers, so the $k$ loop will iterate $c$ times, taking the values $k=1, k=2, \dotsc,k=c$ for any values of $i$ and $j$. Working outwards, the $j$ loop will iterate $b$ times and each time will perform a complete $k$ loop. In other words, the total amount of work done by the $j$ loop will be $bc$: $b$ iterations of the $j$ loop, each involving $c$ steps of the inner $k$ loop, no matter what the $i$ value is. Finally, in a similar way, the outer $i$ loop will iterate $a$ times, each time doing $bc$ work. The total number of iterations, then, will just be $abc$.

For example, with $a=2, b=3, c=2$ the $(i, j, k)$ values will be, in order,
$$\begin{array}{c}
(1,1,1) \\
(1,1,2) \\
(1,2,1) \\
(1,2,2) \\
(1,3,1) \\
(1,3,2) \\
(2,1,1) \\
(2,1,2) \\
(2,2,1) \\
(2,2,2) \\
(2,3,1) \\
(2,3,1) \\
\end{array}$$


Number of ways to make $n$ cents How to find a recurrence relation for $F(n)$ the number of ways to make n cents change using only pennies (4 cents), nickels(5cents), and dimes(10cents) and ordering matters.

There are three exclusive case here

Start with pennies then new subproblem is $F(n-4)$
Start with nickels then new subproblem is $F(n-5)$
Start with dimes then new subproblem is $F(n-10)$

$$F(n) = F(n-4)+ F(n-5) + F(n-10) $$

Is there any other way to solve this problem. The above method is ok but seems like magic to beginner. Is there any systematic approach to solve this problem?

Problem is also available on https://math.stackexchange.com/questions/248853/how-to-find-recurrence-relation-for-this-problem

If we try to apply your recurrence to $n = 9$ and add the base case $F(0) = 1$, then we get $F(9) = 2$. Now this might be the answer you want, since there are indeed two possibilities: penny+nickel and nickel+penny, but usually we consider these the same.

There are two ways to proceed if we want to compute the number of ways without regard to order. The first way is to consider three different functions $F,G,H$ which correspond to using all coins ($F$), only nickels and dimes ($G$), and only dimes ($H$). The recurrences are
$$
F(n) = F(n-4) + G(n-5) + H(n-10), \\
G(n) = G(n-5) + H(n-10), \\
H(n) = H(n-10),
$$
with initial conditions $F(0) = G(0) = H(0) = 1$ and $F(m) = G(m) = H(m) = 0$ for negative $m$. This gives a joint linear recurrence for the triplet $F(n),G(n),H(n)$.

The other approach is to use generating functions, which give us the following expression:
$$
\sum_{n=0}^\infty F(n) x^n = \frac{1}{(1-x^4)(1-x^5)(1-x^{10})} = \frac{1}{1-x^4-x^5+x^9-x^{10}+x^{14}+x^{15}-x^{19}}.
$$
This shows that the sequence $F(n)$ satisfies the recurrence
$$
F(n) = F(n-4) + F(n-5) + F(n-10) \\- F(n-9) - F(n-14) - F(n-15) + F(n-19)
$$
with initial conditions $F(0) = 1$ and $F(m) = 0$ for negative $m$.

This can be seen as a kind of inclusion/exclusion principle — I'll let you work out the details.


If $L$ is NOT Turing-recognizable, does that mean that super sets with $L$ are also not? Suppose there is a language $L$ that is not Turing-recognizable. Now suppose, for every word in $L$, you would concatenate a "0" as prefix, resulting in $L' = \{0w | w \in L\}$. Does this mean that $L'$ is also not Turing-recognizable?

I would argue that $L'$ is also not Turing-recognizable:

No Turing machine recognizes $L$. So there exists no TM that recognizes all the words in $L$. That means that all the words that can not be recognized by a TM that are in L, also can not be recognized even with a "0" added before them. Because after the TM's head reads the "0", we assume that the head will read what comes after, which is a word that is not Turing-recognizable. One could argue that the head doesn't need to read the word and just go to "accept" after reading the 0, but then I can also build a TM that would just go to "accept" straight away before reading this word at all, meaning that the word was not Turing-recognizable which contradicts the initial statement.

In other words, after reading the "0", the TM will have to come across the not Turing-recognizable word, which it can't recognize. Therefore $L'$ is also not Turing-recognizable.

To generalize, I think if a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable.

However, I feel my explanation is shaky and I'm not convinced I am correct. Can anyone verify my claim, and either prove me wrong or give tips for a better proof?

If $L'$ were Turing-recognizable then there would be a TM $M$ which would enumerate every string in $L'$. In particular, we could construct a TM that would print on the tape every string in $L'$. Then we could easily modify this machine to enumerate the language $L$. Just do not print the first symbol on the tape (skip the initial $0$). Thus we construct a machine which enumerates $L$. But $L$ is not Turing-recognizable (not r.e.) by assumption. A contradiction.

$L'$ in your example may be expressed as a concatenation of languages $\{0\}$ and $L$, that is, $L' = \{0\}L$. However, we cannot generalize this result to arbitrary languages. For example, $\{0,1\}^*L = \{0,1\}^*$ is r.e. even if $L$ is not r.e. language on $0$ and $1$ containing empty string.

As for your claim "a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable", it is false too, since a not Turing-recognizable language $L$ on $0$ and $1$ is a subset of $\{0,1\}^*$ which is definitely r.e., even decidable.


How to define a language for an independent set problem of a graph? Let a graph $G=(V,E)$ have an independent set $I\subseteq V$ with $\{u,v\}\notin E$ for all $u,v \in I$ and $k \in \mathbb{Z}_{>0}$ where $|I|=k$.

How can I define the language $L_{P_{Independent Set}}$ to this decision problem?

I know that $I$ could be written as $I = \{u,v\} \in V | \{(u,v)\}\notin E \}$ but don't really understand how to describe the language.

A language $L$ describes decision problem $p$ means that $\forall x \in L $ the instance $x$ is a Yes/Accept instance of $p$.

For the independent set problem, we have to define language $L$ such that every $x\in L$ be an independent set of graph $G=(V, E)$.

So one possible way to define decision language for independent set problem is
$$L=\{I\,|\, I\subseteq V ,\,\forall u,v\in I \, (u,v)\notin E\}.$$

If you wish to define the language generally you can write it as
$$L=\{(G=(V,E),I)\,|\, I\subseteq V ,\,\forall u,v\in I \, (u,v)\notin E\}.$$


If a point is a vertex of convex hull The exercise is

  Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex  of convex polygon formed from points of $S$.

The problem is I am a little bit confused with time complexity $O(n)$. The more naive solution would be to construct convex polygon in $O(n\log n)$ and test if $p$ is one of the vertices.

Hint: the point $p$ is a vertex of the convex hall iff there are two half-lines from it such that all points fall inside the angle created by them.

Here is an idea for an algorithm based on this hint:

   Design an algorithm with two variables $q$ and $r$ (input points). The algorithm will examine each of the input points and will update $q$ and $r$ so that all points checked so far fall inside the wedge $\angle qpr$.


Which order is "lexicographic order"? To choose 3 items out of 5 items [1, 2, 3, 4, 5], Donald Knuth's lexicographic algorithm (The Art of Computer Programming, Vol 4A, 2011, p. 358, Algorithm L (lexicographic combinations)) gives:

[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]

or, if strictly following the algorithm, each combination is reversed, making it:

[[3, 2, 1], [4, 2, 1], [4, 3, 1], [4, 3, 2], [5, 2, 1], [5, 3, 1], [5, 3, 2], [5, 4, 1], [5, 4, 2], [5, 4, 3]]

while Combinatorial Algorithms by Nijenhuis and Wilf, 2nd Ed, 1978, p. 26 cited "alphabetic order" or "lexicographic order" of:

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], ...

so they are different.  Which is actually lexicographic order, or are all of them lexicographic order, and why?

There is no one universally accepted lexographical ordering. Any author is free to introduce their own ordering, as long as it is consistent within their scope of discussion.

It's just like binary tree traversing algorithms like preoder, inorder or postorder traversal. There is no one correct traversal, its upto the author to decide which one to use, and stick with it throughout their discussion about the topic.


Given a list of students and their courses, place them in specific classes I could use some help coming up with the best way to solve this problem. I've been curious as to how something like this would work, as the worst case seems way too bad.

Problem

Given a group of students and the courses they are enrolled in, and a schedule with 8 class blocks in it, how could you place them in specific classes?

Keeping in mind you can have as many classes for a specific course as long as there is a teacher who is free to teach the class.

Specifics

There are 8 class "slots" where you can put any class, but a teacher can not teach two classes at once.

Inputs and outputs

The input is a list of students each with data on which courses they are taking. There is not specific data structure I have in mind, the problem is more theoretical than literal.

The output would be assigning a value 1-8 to each class, specifying when they would take it.

At first glance, the stable matching problem's solution is discussed in the following pdf.
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf

It would be hard to cast the course assignment problem as stable matching because he fact that the courses have a finite capacity

However, the following pdf states that, http://dss.in.tum.de/files/bichler-research/2014_diebold_matching_course_allocation.pdf

  The allocation of students to courses is a wide-spread and repeated
  task in higher education, often accomplished by a simple first-come
  first-served (FCFS) procedure. FCFS is neither stable nor
  strategy-proof, however. The Nobel Prize in Economic Sciences was
  awarded to Al Roth and Lloyd Shapley for their work on the theory of
  stable allocations. This theory was influential in many areas, but
  found surprisingly little application in course allocation as of yet.
  In this paper, we survey different approaches for course allocation
  with a focus on appropriate stable matching mechanisms. We will
  discuss two such mechanisms in more detail, the Gale-Shapley student
  optimal stable mechanism (SOSM) and the efficiency adjusted deferred
  acceptance mechanism (EADAM). EADAM can be seen as a fundamental
  recent contribution which recovers efficiency losses from SOSM at the
  expense of strategy-proofness. In addition to these two important
  mechanisms, we provide a survey of recent extensions with respect to
  the assignment of schedules of courses rather than individual courses.
  We complement the survey of the theoretical literature with results of
  a field experiment, which help understand the benefits of stable
  matching mechanisms in course allocation applications.


Runtime of good suffix table creation in Boyer-Moore algorithm According to Wikipedia, both bad character table and good suffix table can be created in $O(n)$ time, where $n$ is the length of the pattern. It is pretty obvious how bad character table can be computed in linear time, but I don't understand how good suffix table can be computed in linear time. I thought about it a lot, and could not come up with an $O(n)$ algorithm to generate that table. I also looked at the Java implementation provided in Wikipedia, but I think it runs in $O(n^2)$ time. For example, look at the following two lines taken from makeOffsetTable method.

for (int i = needle.length - 1; i >= 0; --i) {
    if (isPrefix(needle, i + 1)) {

Outer for loop iterates needle.length (i.e. $n$) times, and within the loop body isPrefix is called, which contains a loop that starts with the following header.

for (int i = p, j = 0; i < needle.length; ++i, ++j) {

Just to make it easier on the eyes, here is the two loops shown together.

for (int i = needle.length - 1; i >= 0; --i) {
    for (int i2 = i + 1, j = 0; i2 < needle.length; ++i2, ++j) {

I can get rid of j of the inner loop to further simplify it.

for (int i = needle.length - 1; i >= 0; --i) {
    for (int i2 = i + 1; i2 < needle.length; ++i2) {

What I see here is that with each successive iteration of the outer loop, inner loop will have one additional iteration. So, the number of iterations for the inner loop will be $0, 1, 2, 3, 4, ..., (n-1)$ which adds up to $(n-1)n/2$, which is $O(n^2)$, which is not linear.

So, the question is, does it really take more than linear time to compute the good suffix table, or am I making a mistake with runtime calculation?

The implementation provided in Wikipedia is $O(n^2)$. But these tables can actually be built in $O(n)$ time via Z-algorithm. Since you can find Z-algorithm on internet easily, I just provide a sketch here.

Let $s[i,j]$ denote the substring of $s$ from $i$-th position to $j$-th position. Like what we see in the $O(n^2)$ code, we want to find the largest value $z_i$ satisfying $s[i-z_i+1,i]=s[n-z_i+1,n]$ for each $i$ (the longest matching suffix).

Now compute $z_i$ from back to front. Let $l$ be the smallest number s.t. $s[l,r]=s[n-r+l,n]$ for some $r>i$. If $l\le i$, we have $s[l,i]=s[n-r+l,n-r+i]$, which means we can get some information from $z_{n-r+i}$. If $z_{n-r+i}\le i-l$, $z_i=z_{n-r+i}$. Otherwise $s[l,i]=s[n-i+l,n]$ and $z_i>i-l$. In this case, we should find the real $z_i$ by brute force, but at the same time we get a smaller $l$, which provide more information for future computation. Since $l$ is non-increasing, the algorithm works in $O(n)$.


Finding the number of leaves in a imbalanced recursion tree I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00.

So we have a recursion formula

$\qquad T(n) = T(n/10) + T(9n/10) + O(n)$

If we build a recursion tree it looks like

                   T(n)                     -- Level 1       = c*n
             /               \
       T(n/10)             T(9n/10)         -- Level 2       = c*n
        /   \             /         \
 T(n/100)  T(9n/100) T(9n/100)  T(81n/100)  -- Level 3       = c*n

   /                                  \                      <= c*n
    .                                .
    .                                .
 0(1)                                 0(1)

where $c$ is a constant larger than $0$.

Shortest path from the root to the leaf is $\log_{10}(n)$.

Longest path from the root to the leaf is $\log_{10/9}(n)$

Therefore, the cost could be calculated as Cost = Cost of each level * number of levels.

With the shortest path cost, we get a lower bound of $cn\log_{10}(n)$, and with the  longest path cost an upper bound of  $cn\log_{10/9}(n)$.

And now I have to add the costs of leaf nodes, which leads to my problem. In the video it says the total number of leaves is in $\Theta(n)$. I have trouble figuring out how he got to $\Theta(n)$.

The video further says $T(n)$ is bounded by

$\qquad cn\log_{10}(n) + O(n) \leq T(n) \leq cn\log_{10/9}(n) + O(n)$

Wouldn't it make more sense to say it's

$\qquad cn\log_{10}(n) + O(n^{\log_{10}(2)}) \leq T(n) \leq cn\log_{10/9}(n) + O(n^{\log_{10/9}(2)})$

where $\Theta(n^{log_{10}(2)})$ represents the leaves on the left and $\Theta(n^{\log_{10/9}(2)})$ represents the leaves on the right.

Or is there a way to simplify these terms to $\Theta(n)$?

Why is thetotal number of leaves in $\Theta(n)$? Because each level in recursion tree corresponds to a splitting of an array's range. When we have one element we can't split it any more so we stop. That's $\Theta(1)$ per leaf. How many 1-element areas are there in an $n$ element array? The answer is $n$.

He is summing up all levels. But levels are not all populated. Some paths down are short, some long. The more to the left in the tree, the shorter is the path. So going down the right "spine" of the tree, how many levels are there? $\log_{10/9}(n)$. What each level sums up to? Initially, $cn$ (where $c$ is a constant, $n$ is number of elements in the array) - while the levels are totally populated - i.e. all nodes represent splits - i.e. no one-element ranges are reached yet. Then, we start missing some leaves, so instead of "equal" , we can write $\leq cn$. So the total sum is less than $cn\log_{10/9}(n)$.
Or, let's go down the left spine and sum all levels up. There will be some uncounted tree to the right and down. So the total is greater than this summation, which equals $cn\log_{10}(n)$. He uses "or-equal" just because he's a mathematician who doesn't like to be wrong in some corner cases. :)

This is all pretty straight-forward and intuitive.


Simple (non-mathematical) definition of polynomial time? Computational Complexity Theory is complex.  My understanding of polynomial time is in relation to other time complexity classes, such as non-deterministic polynomial time.  This is fine for engineers and mathematicians, but I'm looking for a simple definition of the term, suitable for laypeople.

Would it be incorrect to cast polynomial time as "time measured in (computational) operations?"

Obviously there would be subsequent qualifications for different time complexity classes, and time complexity may be more properly a ratio based on the problem size, but again, that's a bit more complex than what I'm looking for here.

Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size.

Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1.

For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential time, although, as we know, this is wrong on many counts.


Algorithm to decide whether two vertices are ancestors/descendants of each other Is there an algorithm that performs the following:

Input: A directed graph and two vertices within that graph
Output: Whether one of the two vertices is the ancestor of the other

For example, in this graph:

A is an ancestor of D. B is neither the ancestor nor the descendant of C.

The best I can think of doing is performing a DFS/BFS from each of the two input vertices and seeing if either search includes the other vertex. This takes O(|V| + |E|) time. Is there a well-known, faster algorithm?

DFS only requires $O(|V|+|E|)$ time, not $O(|V| \cdot |E|)$ time.  (Same for BFS.)  Therefore, DFS is an efficient solution for this problem.  This is about as efficient as you hope for, as it takes that much time just to read the entire input -- you can't hope for something faster.

The problem becomes more interesting if we're provided the graph $G$ and allowed to do some precomputation, and then want to answer many queries efficiently.  This is considerably more challenging, but in some cases, it is possible to do better than running a DFS from scratch every time you receive a new query.

For instance, if the graph is a tree, there is an efficient solution: do a DFS once, and store the pre and post numbers at every node; then each ancestor query can be answered by testing for interval containment.
In a more general graph, this is known as a reachability query, and there are algorithms in the literature for this problem.  See, e.g., https://cs.stackexchange.com/a/41432/755 and https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038.  Without loss of generality, you can assume the graph is a dag (if not, first compute all strongly connected components in linear time, and label each vertex with its scc; then you only need to consider the dag of scc's).


Given a set of n balls with different weights and a scale that compares two balls Write an algorithm to determine if there's a set of > n/4 balls of the same weight. The algorithm cannot exceed O(n log n) time.

One way I was thinking about this was using divide and conquer. My original algorithm was as follows:

findSet(S) #S is the set of n balls
    If |S| = 1, return the lone ball
    If |S| = 2 or 3, return any ball
    Divide S up into 4 subsets of equal length, run findSet on each
    If no run returns a ball, return nothing
    If a single test returns a ball, weigh the ball against all other balls
      in S. If we generate a set of balls > n/4, return the ball

    If >=2 tests return balls, let B denote the set of these balls.
    For each ball b in B, weight b against all elements in B.
      If we generate a set of balls > n/4, return the corresponding b.

I think the algorithm is O(n) because the recurrence would be T(n) = 4T(n/4) + n which can be reduced to O(n log4 n). However, I'm pretty sure this algorithm is incorrect. Primarily, I'm not sure if the base cases will ensure we choose a ball b that is > n/4 in the original set.

Assume you have a sorted array of all weights. If any such element existed then more than %25 of that array had to be occupied with that element. Then either element at %25 marker, %50 marker and %75 marker has to contain such element. So we have 3 candidates but no such sorted array. Assume N is divisible by 4 below. There might some tweaks to be done for edge cases which can be handled.

Do Worst-Case Linear-Time Selection to find the median of the entire array.
Create two arrays of size |N / 2| both. For the first one but everything smaller than the median. For the second one put everything that is larger. If either of the arrays or not full pad the array with the median element. Then find the median of both of these arrays as mentioned in step 1.
We have 3 candidates. For each candidate count how many of them have equal weight. If any has counter more than |N / 4| output this element.

Runtime: Each step is linear with respect to input. We iterate over the entire balls multiple times but still it is O(N).

Problem with the proposed algorithm is mainly the probable imbalance of the random partitions of the set


"Immediate" method of translating arbitrary mutable program to equivalent unmutable program? Consider the following program in "mutable style":

x=1
x=f(x);
x=f(x);

We can rewrite this in "immutable style" without changing the higher-level structure of the program:

x1=1
x2=f(x1);
x3=f(x2);

We turned it into an immutable style program by only making "local changes": We simply took the mutable variable $x$ and changed the program wherever $x$ appeared to make it immutable.

Question: Can we in general turn an arbitrary mutable program into an immutable program by only making local changes, so that the higher level structure of the program stays the same?

Obviously this will depend on the language. You may assume any language features you want. e.g. this answer talks about monads (though it's not clear to me whether they can always be used to translate programs using only local changes).

The state monad allows us to translate any stateful (you call it "mutable") program to a pure one. The changes required to the program are "local" in the sense that you only need to make superficial changes to the syntax, assuming you use Haskell-style do notation. For example, the following is the Haskell translation of your program into a pure program:

do x <- 1
   x <- f x
   x <- f x

You think you can make your transformation by renaming variables, but this will not do when recursion or loops are involved. For example, it is not clear how to use your idea here:

s = 0
i = 0
while (i < n) do
   s = s + i
   i = i + 1
done

Following your scheme we get the non-sensical:

s1 = 0
i1 = 0
while (i1 < n) do
   s2 = s2 + i1
   i2 = i2 + 1
done

You need to think more carefully about your idea (and I don't see how to make it work).


How did each class of languages receive their name? If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable languages. There's also the class of recursive languages (which fits in between CSL and RE), but Chomsky didn't include this class in his hierarchy for whatever reason.

How did each of these classes receive its name? For instance, what does "recursively enumerable" mean in the context of a Turing machine being able to construct a RE language? What is context, and what differentiates "freeness" from "sensitiveness"? I can imagine that a language is "regular" because it can be generated by a regular expression, but I'm not sure if this is the reason behind the name.

(And a bonus question just for the fun of it: why didn't Chomsky include recursive languages in his hierarchy?)

Regular Languages:

There's some good discussion of this here: https://ell.stackexchange.com/questions/83917/how-did-regex-get-its-name

Context-Free vs Context-Sensitive Grammars:

For CFGs and CSGs, the "context" part is the idea that certain rules can be extended  to apply based on relative positions of symbols rather than on single specific symbols.

Context-free grammars have substitutions that only allow you to replace single non-terminal characters at a time and does not consider the symbols around it. Since the context of where in a string the symbol occurs does not matter, we call the rule context-free.

Examples:

$S \rightarrow foo$ is a context-free rule
$aSb \rightarrow a foo b$ is not context-free due to it only contextually applying when $S$ is surrounded by both an $a$ on the left and $b$ on the right. It is instead, context-sensitive.

Context-sensitive grammars allow you to construct rules that operate on these situations where the relative locations of symbols matter. Since the rules can be specific respective to relative positions of terminal and non-terminal symbols, the rules are said to be context-sensitive.

Recursively Enumerable:

A set (language) is recursive if a Turing machine can tell you if a particular element is a member of that set or not in finite time. The name comes from a field called recursion theory, where recursion is a mathematically formal way to derive what computability is.

For example, the set of even binary numbers ($2\mathbb{Z}$) is a recursive set because I can take any number and test whether or not it is even in finite time on a Turing machine.

A set (language) is recursively enumerable if a Turing machine can enumerate over all the elements of that set. If an element you are testing for is in the set, you will eventually encounter it while enumerating through elements of the set. However, since the set can be infinitely large, you potentially will never be able to look at them all. If your element you are searching for is not actually in the set, you will neither be able to encounter it or know for certain that it is not in there.

Recursive languages are not part of the Chomsky hierarchy because the hierarchy is specific to grammars. It is not known if there is a natural grammar that captures recursive languages. See Decidable languages and unrestricted grammars?

Side Note: Typically we say that Turing machines recognize languages (not construct).


NFA accepting $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$ I have to construct NFA that accepts language $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$.

My solution is this automata:

Can you tell me, if this is correct or not? If yes, it is possible to construct this NFA with less states?

I will address your second question, namely, whether there is an NFA with fewer states. The appropriate technique here is fooling set:

  Let $L$ be a language, and let $x_1,\ldots,x_n,y_1,\ldots,y_n$ be words such that $x_iy_i \in L$ but for every $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. Then every NFA for $L$ contains at least $n$ states.

(The proof is a simple exercise.)

In our case, we take
$$
\begin{array}{c|cc}
i & x_i & y_i \\\hline
1 & bbaa & \epsilon \\
2 & bba & a \\
3 & bb & aa \\
4 & b & aaa \\
5 & \epsilon & bbaa
\end{array}
$$
For all $i$ we have $x_iy_i = bbaa \in L$. Conversely, if $i < j$ then $|x_jy_i| < 4$ and so $x_jy_i \notin L$.

In fact, we have proven the following more general result:

  If the minimal length of a word in $L$ is $\ell$, then every NFA for $L$ contains at least $\ell+1$ states.


How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance I was working in my project when I was struck by the question of whether it would be necessary, or at least cautious, prevent overflow and underflow in the calculation of these two distances.

I remembered that there is an implementation of the calculation of the hypotenuse to prevent this. Most languages implementers, and is known for Hypot

The calculation of the Euclidean distance remains the same "pattern" and I thought that if Hypot() controls the overflow and underflow should also beware of the Euclidean distance.  I've disappointed to note that the language we use, and others, do not control the overflow and underflow for calculating distance. Will not worth spend this "additional effort"?

I did a searchs and came to a question in Math.StackExchange

There is no definitive answer to this issue and is somewhat old. The first thing I wondered is: Will okay? I think that yes, seeing that is a generalization of the same procedure that performs Hypot().

I decided to extrapolate this concept to the Mahalanobis distance. The original is as follows:

$$D_M(X,Y,L) = \sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i}\right)^2}$$

Since $L$ is the vector of eigenvalues.

And my proposal is this:

$$D_M(X,Y,L) = C\sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i }\frac{1}{C}\right)^2}$$

That is the same to:

$$D_M(X,Y,L) = C\sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i C}\right)^2}$$

And $C$ is the max value from the $|(X_i-Y_i)/L_i|$:

$$C = \max_{i}\left(|\frac{X_i-Y_i}{L_i}|\right)$$

Is it okay?

That is a long solved problem. First, if you are using double precision floating point numbers in IEEE754 format (which is most common), that's what extended precision was invented for. Even in the extreme case, $X_i$ and $Y_i$ huge, $L_i$ tiny, the numbers involved are less than $10^{1300}$ and extended precision goes up to about $10^{4000}$.

Without extended precision available, or if your numbers are already in extended precision, you just calculate the result and check whether you had an overflow or if the result is tiny. Tiny results are critical as well: If you use double precision floating point numbers, and your numbers are around $10^-200$, then squaring them gives you zero. There will be a lower bound c where you can prove "if the result is greater than c, then any underflow in the calculation didn't change the final result".

If overflow happens, or underflow happens, then you scale the numbers by a suitable power of two. Do NOT divide by the maximum value, because that introduces rounding errors, and there are cases with n = 2, $L_i = 1$, where $|X_1 - Y_1| ≤ |x_1 - y_1|$, $|X_2 - Y_2| ≤ |x_2 - y_2|$, yet the calculated distance of X, Y is greater than the calculated distance of x, y, due to rounding errors. Scaling by a power of two avoids the problem because it doesn't create any rounding errors.

And you want to make sure that the order of numbers doesn't make a difference. For n = 2 you must make sure that no fused multiply/add operations are used. For n ≥ 3 you probably want to sort the numbers so the ones with smallest absolute difference come first. Otherwise you can get into situations where the distance between $(X_1, X_2)$ and $(Y_1, Y_2)$ is not the same as the distance between $(X_2, X_1)$ and $(Y_2, Y_1)$.


What exactly is computer science? I have a question that, no matter how much I think about, I do not have the answer to.  The question is what exactly is computer science?  The reason I am asking is that I went into college thinking computer science was going to be about software engineering disciplines and deep study in the realm of application and practicality; these excited me.  However, after taking core requirement classes for computer science, many so devoted to discrete mathematics (set theory, group theory (abelian properties, etc.), probability, etc.), I became disillusioned and frankly, sick of taking these abstract-concept related courses, asking myself daily when I would use these concepts in my daily life as a developer.

I've searched online for the answer, but none have satisfied me so far.  Several arguments have boiled down to essentially saying something like "If you want to do gaming, you have to be good at trigonometry, which is math"; clearly, this is not what I am looking for.  If someone could guide me into truly understanding why discrete math and structures is essential to the software engineer, and to the world outside the realm of the academia aspect of computer science, that would be awesome.  Thank you!

"...asking myself daily when I would use these concepts in my daily life as a developer." The answer depends on the job. It sounds like you don't like math/theory, so you would not apply for/ get a job that requires a deeper understanding of CS, as many higher-level jobs do.

However, the truth is that the vast majority of software engineering jobs requires very little math or theoretical computer science, or even a good understanding in computer systems (which you didn't mention). If you just want to write code for websites or applications or do front-end, you can do that just fine without knowing most of the topics taught in a CS curriculum. Most of this knowledge is simply uneccessary, although having a degree will certainly help you get a job. However I know people who went into the software engineering profession with degrees in journalism or theater or other completely unrelated fields.

Also, there are some colleges that offer a degree in Software Engineering, which is much more focused on the practical side, including software development cycles and practices.

This is all practical advice. As for what Computer Science is, there is probably no universally accepted answer. It's a broad field, with many different sub-fields. However, most people would probably not consider simple software programming as Computer Science.


How to prove that $L_{D}\leq L_{U}$? I have the following two languages:
$$
L_{U}\triangleq\left\{ \langle M,x\rangle\,:\,M\text{ accepts }x\right\} ,L_{D}\triangleq\left\{ \langle M\rangle\,:\,M\text{ accepts }\langle M\rangle\right\}
$$
I'm trying to prove that $L_{D}\leq L_{U}$. For that I need to show that there exists $f\,:\,\Sigma^{*}\to\Sigma^{*}$ total, can be calculated by a Turing machine and follows: $\forall x\in\Sigma^*$, $x\in L_D$ iff $f(x)\in L_U$.
Let there be $f\,:\,\Sigma^{*}\to\Sigma^{*}$ so $f\left(\langle M\rangle\right)=\langle M,M\rangle$. I have proved that $f$ is total and also follows the last condition. All that left to do is to prove that $f$ can be calculated by a Turing machine. How should I describe the steps of machine $M_f$ on $\langle M\rangle$?

It is the turing machine that clones its input. If you want a description of this machine's operation, you may find this useful.


RDT2.1 - does the Sender listener to "ack" even though state=ready? Computer Networking:
  A Top Down Approach
  Featuring the Internet,
  Jim Kurose, Keith Ross
  Addison-Wesley 4nd edition , page -223.

Also here slide 60 .

RDT2.1 (Reliable data transfer) -

Sender(s):
state=ready; i=0;
On rdt_send(d,m):
    if state=ready
    then
    { p=<s,d,m,i,
    EDC(s||d||m||i)>;
    udt_send(p);
    state=busy; }
On udt_deliver(a)
     If a=<“ack”,EDC(“ack”)>
    then
    { i++;
    state=ready; }
    else udt_send(p);

When the Sender side is in state=ready , does he still listener to "ack" recived from the Reciver ?

I need to know this , cause if so it seems that the Sender can get duplicate "ack"'s from the reciver and inc the i without sending any packet mainwhile .

From the code above, Yes.

Regarding your second note. A sender will go to the busy state if it sends a message and there it will wait for an ACK. I can imagine that the reciver would send multiple ACK's only if there is some fault. Usually, such faults are not considered in the basic protocol description, but are considered in the actual implementation.


Show that NP is not equal to SPACE(n) I want to show that $\text{NP} \neq \text{SPACE}(n)$ and tried it like this:

Let $L$ be in $\text{SPACE}(n)$ so there is a deterministic $k$-tape TM which decides $L$ in polynomial time. Let's consider a binary alphabet. There are $2^{kn}$ possible strings on the working tapes so for an input of length $n$ the TM can be in $2^{kn} \cdot k \cdot n \cdot |Q|$ different configurations where $Q$ is the finite state set.

Since the TM is deterministic and decides $L$ no configuration can be visited twice (otherwise we would be in an infinite loop). So $2^{kn} \cdot k \cdot n \cdot |Q|$ is also an upper bound for the runtime of the TM which is exponential and therefore not in $NP$.

Is this argumentation enough? I found this answer on the internet and now I'm confused because it looks so much more complexive but also comprehensibly...

In order to prove that $\mathsf{SPACE}(n) \not\subseteq \mathsf{NP}$, you need to identify a language in $\mathsf{SPACE}(n)$ which is not in $\mathsf{NP}$. Not every language in $\mathsf{SPACE}(n)$ would work — for example, every regular language is in $\mathsf{SPACE}(n)$, and all of these are also in $\mathsf{NP}$.

Your argument, as I understand it, is roughly as follows:

Every machine in $\mathsf{SPACE}(n)$ runs in at most exponential time.
Hence every such machine is not in $\mathsf{NP}$.

The second conclusion is not correct, since exponential time is only an upper bound. For example, a DFA uses constant space and does run in polynomial time.

Worse, even if some machine in $\mathsf{SPACE}(n)$ does run in exponential time, it could be that there exists another machine accepting the same language that runs in polynomial time — especially if we are allowed to use nondeterminism. As an example, it is suspected that $\mathsf{SAT}$ (which is in $\mathsf{SPACE}(n)$) requires exponential time, but it does belong to $\mathsf{NP}$.

The proof outlined in your link is not too hard, given the space hierarchy theorem. This theorem gives you a language $L$ which is in $\mathsf{SPACE}(n^2)$ but not in $\mathsf{SPACE}(n)$. The padded language $L' = \{ 1^{|x|^2}0x : x \in L \}$ does lie in $\mathsf{SPACE}(n)$ (why?), and so if the latter is equal to $\mathsf{NP}$, it follows that $L' \in \mathsf{NP}$. However, $L$ polytime reduces to $L'$, and so it would follow that $L \in \mathsf{NP}$ as well, contradicting $L \notin \mathsf{SPACE}(n)$.


What are examples of inconsistency and incompleteness in Unix/C? In Richard Gabriel's famous essay The Rise of Worse is Better, he contrasts caricatured versions of the MIT/Stanford (Lisp) and New Jersey (C/Unix) design philosophies along the axes of simplicity, correctness, consistency, and completeness.  He gives the example of the "PC loser-ing problem" (discussed elsewhere by Josh Haberman) to argue that Unix prioritizes simplicity of implementation over simplicity of interface.

One other example I've come up with is the different approaches to numbers.  Lisp can represent arbitrarily large numbers (up to the size of memory), while C limits numbers to a fixed number of bits (typically 32-64).  I think this illustrates the correctness axis.

What are some examples for consistency and completeness?  Here are all of Gabriel's descriptions (which he admits are caricatures):

The MIT/Stanford approach

Simplicity -- the design must be simple, both in implementation and interface. It is more important for the interface to be simple than the implementation.
Correctness -- the design must be correct in all observable aspects. Incorrectness is simply not allowed.
Consistency -- the design must not be inconsistent. A design is allowed to be slightly less simple and less complete to avoid inconsistency. Consistency is as important as correctness.
Completeness -- the design must cover as many important situations as is practical. All reasonably expected cases must be covered. Simplicity is not allowed to overly reduce completeness.

The New Jersey Approach

Simplicity -- the design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design.
Correctness -- the design must be correct in all observable aspects. It is slightly better to be simple than correct.
Consistency -- the design must not be overly inconsistent. Consistency can be sacrificed for simplicity in some cases, but it is better to drop those parts of the design that deal with less common circumstances than to introduce either implementational complexity or inconsistency.
Completeness -- the design must cover as many important situations as is practical. All reasonably expected cases should be covered. Completeness can be sacrificed in favor of any other quality. In fact, completeness must be sacrificed whenever implementation simplicity is jeopardized. Consistency can be sacrificed to achieve completeness if simplicity is retained; especially worthless is consistency of interface.

Please note I am not asking whether Gabriel is right (which is a question not appropriate for StackExchange) but for examples of what he might have been referring to.

The question's title suggests that some basic user interface inconsistencies may interest you:

Unix commands don't follow any particular syntax for specifying options and flags. For example, most commands use single letters preceded by '-' as flag: cat -n some_file, but exceptions like tar tf some_file.tar and dd in=some_file out=some_other_file count=2 exist in commonly used commands.

Unix and its descendants and relatives have multiple slightly different regular expression syntaxes.  Shells use "*" where other programs (grep, egrep, vi) use '.*'.  egrep has '+' and '|' as operators, grep does not.

The basic "everything is a file" system call interface could be viewed as incomplete: read/write/seek/close doesn't fit every I/O device.  Badly needed exceptions get lumped into "ioctl" calls, but devices like sound cards don't even fit that very well.


Finding median from given range What is the most effective way of finding median from $N$ numbers within given range ? It is guaranted that $N \leq 10^{9}$.

The input consists of $L$ lines.

Each line consists either of:

a)  S X , which means store number $X$, where $X \leq 10^{9}$.

or

b)F X Y,  which means find median from stored numbers within range $(X,Y)$. where $1 \leq X,Y \leq 10^{9}$

For each F X Y ( median range request ) it should print the median from all stored numbers within range $(X, Y)$

Example:

Suppose the input:

S 20
S 10
S 22
S 30
S 25
F 21 30
S 5
S 7
S 9
F 5 20

Output:

   Median from range (21, 30) : 25
   Median from range (5, 20) : 9

Explanation:

The first median request for range (21, 30) satisfie 3 numbers: 22 25 30 where the median is 25.

The second median request for range (5, 20) satisfie 5 numbers: 5, 7, 9, 10, 20 and we pick up the median which is 9.

The mean is not guaranted to be close to median. The requests for storing S do not have to go consecutevly.

It can be done in $O(L \log L)$ time, which is optimal by reduction from sorting.

Consider a Red-Black Tree $T$ (or any other self-balancing tree) where each node $v$ is augmented with $s(v)$, the number of nodes in the subtree rooted in $v$. Keeping such information updated between insertions is trivial.

In order to show that such structure supports median queries in $\log L$ time, it is sufficient to show that we can perform the following operations in $\log |T|$ time:

Given $v \in T$, determine $\#v$.
Given $n \in \mathbb{N}$, find $v \in T$ such that $\#v = n$.

To solve the first problem, initialize a variable $x := 0$ and then find $v$. Whenever in the search you are located at a node $w$, if you move right, it means that $v$ is higher than $w$ and each node in the left child of $w$. In such a case, we set $x := x + s(w.left) + 1$. When we reach $v$, we similarly set $x := x + (v.left) + 1$.

After that last update, it will hold $x = \#v$, that is true because $v$ is the minimum of the tree $T_L$ obtained starting from $T$ and cutting the left branch every time you moved to the right while searching $v$, and, conversely, the maximum of the analogous $T_R$.

The second problem can be solved by a similar idea: initialize $x:=0$ to keep track of how many elements you "discarded" by going right, and then perform a dichotomic search.


transformation between two formulations of the mincost flow problem According to this slide, the following two formulations of the mincost flow problem are equivalent:

Given directed graph G = (V, E)

  Let u denote capacities
  Let c denote edge costs.
  A flow of f(v,w) units on edge (v,w) contributes cost c(v,w)f(v,w) to the objective function.

...

  Send x units of flow from s to t as cheaply as possible.
  General version with supplies and demands

  No source or sink.
  Each node has a value b(v).
  positive b(v) is a supply
  negative b(v) is a demand.
  Find flow which satisfies supplies and demands and has minimum total cost.

I can see that 2. is a special case of 3. in which only two nodes (s and t) and have non-zero demand. But I cannot figure out how to transform the more general problem 3. into problem 2.

Can anyone help explain how to transform 3. to 2. ?

That is, how to e.g. add edges and/or change capacity/cost, to solve problem 3. with a solver of problem 2.

I would say that 3. is a special case of 2. instead but it is a point of view.

On 3., you can create a new node "source" which has edges to every supply nodes (b(v) > 0). These edges have cost 0 and capacity b(v).

Then you create a new node "sink" which has edges from every demand node. These edges have cost 0 and capacity -b(v).

All this replaces the b(v) values which are not needed anymore.


Denumerably many isomorphism types Computability and Logic by Boolos and Burgess says that formula $\Gamma_d$ in example 12.12

∀x∀y(∃u(u ≠ x ∧ u ≡ x) ∧ ∃v(v ≠ y ∧ v ≡ y)) → x ≡ y)

supports models, whose domain is partitioned into equivalence classes of any size, e.g.

is possible. Yet, I do not understand how this is possible. Suppose my x is the first dot. Then, I can find u, which is the second dot. Similarly, let y be the first dot in the second equivalence class and another dot v is in its companion in the eqivalence class. The formula says that x and y must be in the same equivalence class. But they are obviously not!

Are they trying to cheat me?

They are not trying to cheat you. You need to read the text of Example 12.12, following the formula.  It says:

  A denumerable model of $\Gamma_d$ will consist of a denumerable set $X$ with an equivalence relation in which any two elements $a$ and $b$ that are not isolated, that is, that are such that each is equivalent to something other than itself, are equivalent to each other.

Thus $x$ and $y$ in your example must be equivalent in the model, and the picture is not an accurate representation of what $\Gamma_d$ captures.


If a language is contained in other langauge, is it of the same complexity? If some language $L$ is in P, and some other language $K$ is contained in $L$, does that mean that $K$ is also in P?

Thanks :)

No. $\Sigma^*\in\mathbf{P}$ and every langauge is a subset of that – even undecidable ones.


Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3? The following problem is from my algorithms class:

  Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $G(V_1)$ denotes the subgraph induced by $V_1$ and $\delta(G(V_1))$ denotes the minimum degree of graph $G(V_1)$. Prove this decision problem is NP complete.

I'm trying to prove
$$\text{PARTITION} \le_p \text{This-Problem}$$
but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it?  Could anyone help me out here?

For convenience of description, we consider the problem as a coloring problem where vertices in $V_1$ are colored red and vertices in $V_2$ are colored blue.

The following is a reduction from 3SAT.

For any instance of 3SAT with $n$ variables (assume $n\ge 4$ without loss of generality), construct a complete graph of $2n$ vertices $V=\{v_1^0, v_1^1, \ldots, v_n^0, v_n^1\}$ where $v_i^0, v_i^1$ respectively represent the positive and negative literals of the $i$th variable. We also add some additional structures. Note that only named vertices can be in more than one structure.

For each $i$, add the following structure (note I emit the edges among named vertices and the same below):

This structure ensures all the unnamed vertices are colored red, and at least one of $v_i^0$ and $v_i^1$ must be colored red.
For each clause $l_1\vee l_2\vee l_3$, say their corresponding vertices are $u,v,w\in V$, add the following structure:

This structure ensures all the unnamed vertices are colored red, and at least one of $u,v,w$ must be colored red.
For each $i$, for each pair of vertices $\{u,v\}\subseteq V$, add the following structure:

If both $v_i^0$ and $v_i^1$ are colored red, then all the unnamed vertices must be colored red, and at least one of $u$ and $v$ are colored red. Note this holds for all pairs $\{u,v\}$, so if both $v_i^0$ and $v_i^1$ are colored red, there are at most one vertex colored blue, which is impossible. As a result, this structure ensures at least one of $v_i^0$ and $v_i^1$ is colored blue. Combined with the first type of structures, it is ensured that $v_i^0$ and $v_i^1$ are colored different colors.

Now if there is a proper coloring, exactly one of $v_i^0$ and $v_i^1$ is colored red. If it is $v_i^0$, assign the $i$th variable 1, otherwise 0, then the assignment is a valid assignment for the 3SAT instance.

On the other hand, if there is a valid assignment for the 3SAT instance, color $v_i^0$ red and $v_i^1$ blue if the $i$th variable is assigned 1, otherwise color $v_i^0$ blue and $v_i^1$ red. Note the subgraph induced by $\{v_1^0, v_1^1, \ldots, v_n^0, v_n^1\}$ is a complete graph, this is a legal coloring. All unnamed vertices in the first two kinds of structures are colored red, and for a structure of the third type, if both $u$ and $v$ are colored blue, color all the three unnamed vertices blue, otherwise color them red. This is a proper coloring. Q.E.D.


Explain auto continue passing style transformations Recently I saw 3 cps transformation rules, but no explanations were given.

expressions: $e :=x\left|e e^{\prime}\right| \lambda x \cdot e$

rules:
$$
\begin{array}{l}{[[x]]=\lambda \kappa \cdot \kappa x} \\ {[[\lambda x \cdot M]]=\lambda \kappa \cdot \kappa(\lambda x \cdot[[M]])} \\ {[[M N]]=\lambda \kappa \cdot[[M]](\lambda m \cdot[[N]]](\lambda n \cdot(m n) \kappa)}\end{array}
$$

When transforming fib, fib n = ... is transformed into fib n k = ..., but if we use the second rule, the first param of the transformed function will be k which differs

fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fib_cps 0 k = k 1
fib_cps 1 k = k 1
fib_cps n k = fib_cps (n - 1) (\x -> fib_cps (n - 2) (\y -> k (x + y)))

Could someone please explain it for me?

About the 3rd rule, why we need to transform both fn and arg when transforming function application, and why it's like this?

The code you posted takes a few shortcuts. The mismatch with the rules of the CPS transform comes form your code being in Haskell, which features integers (0,1,2), arithmetics (+,-), definitions by cases, and recursion, while the CPS transform only covers the pure lambda calculus, without all the bells and whistles that come with a "usual" programming language.

Anyway the idea of a CPS function is that you never return the result of the function in a direct way. Rather, you pass that result to a continuation function, usually named k, which is an additional parameter to the function. Often, it is convenient to take k as the last parameter -- this is only a convention, though, and we could choose otherwise.

For instance, the constant-zero function becomes

zero n = 0

zero_cps n k = k 0

Squaring:

square n = n*n

square_cps n k = k (n*n)

Now, in the last line I cheated a bit, since there I am using * as the regular multiplication function, instead of using a CPS variant of multiplication. Your fib_cps code does the same for + and -, which are not translated into CPS.
Let's continue with this.

Now, what if we want to CPS transform this composition?

f n = square (square n)

f_cps n k = ???

Intuitively, in f_cps we want to call square_cps, take its result, and pass that to another square_cps. But we can't do that directly, since square_cps does not return its result, it passes it to the continuation. So, we need to write something like

f_cps n k = square_cps n (\m -> ...???...)

where m is the "result" of square_cps, hence m=n*n. What do we do with m? We want to square it again.

f_cps n k = square_cps n (\m -> square_cps m (\o -> ???))

here o will be the square of the square of n, hence n*n*n*n. That is the final result, so we can pass it to k, which expects the result of f.

f_cps n k = square_cps n (\m -> square_cps m (\o -> k o))

So, in CPS style, we use this "idiom":

function_cps arg1 arg2 ... arg2 (\x -> ...)

meaning "call function with the args, let x be the result, and then proceed with ...".

Code like f1 (f2 (f3 (f4 n))) becomes

f4 n  (\x4 ->
f3 x4 (\x3 ->
f2 x3 (\x2 ->
f1 x2 (\x1 ->
... use x1 here ...))))

(If you happen to be familiar with monads in Haskell, you'll see that this is very similar to a monadic do block. This is not a coincidence since CPS is strictly related to the Cont monad.)

In your fib_cps code, we need to do

fib (n-1) + fib (n-2)

This is transformed into a program which evaluates fib (n-1) first (let x be its result), then fib (n-2) second (let y be its result), and finally returns x+y.
In code

fib (n-1) (\x ->
fib (n-2) (\y ->
k (x+y)))

where the last line combines the results and passes their sum to k, the continuation of the call fib_cps n k.

You might have noticed that we needed to fix an evaluation order: first fib (n-1), then fib (n-2). This order was not present in the original code. Indeed, to transform some code to CPS, we need to be more explicit about what we want to evaluate first.

In your CPS rules, application $MN$ is transformed into

$$
[[M]](\lambda m.\ [[N]](\lambda n.\ \ldots)
$$

which forces $M$ to be evaluated first, then $N$, giving an evaluation order, similarly to what happened above.

Further, the CPS term above always evaluates $N$. This is done according to the call-by-value (CBV) semantics, where function arguments are always evaluated. So, the CBV CPS transform matches such semantics, which is used by languages like Ocaml.

Note that Haskell, instead, uses a call-by-name (CBN) semantics instead, where e.g. zero (non terminating expression) returns 0 immediately without evaluating its argument. If we wanted to use CPS completely preserving Haskell's semantics, we should use another form of CPS called the CBN CPS transform, which is subtly different.

In your posted fib_cps code, CBV CPS is used, even in Haskell, since

+ always evaluates its arguments
we are not using a CPS version of +
CBV CPS is arguably a bit simpler to understand

I hope this does not sound too confusing. Continuations are quite tricky to understand.


About a pre-processing step for primal-dual weighted set cover problem I was reading the paper titled "Primal-dual RNC approximation algorithms" by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.

They present a dual fitting based algorithm for weighted set cover. First let me set up the required concept to clarify where I am having trouble. Suppose we have $n$ elements ($U$) and $m$ sets ($S$). Each set has a positive weight. Let $E_v$ holds the sets in which the element $v$ is present. Let $\beta =$max$_{v \in U}$ min$_{s \in E_v}$ weight(s). Let also $IP^*$ is the weight of an optimal set cover. It is easy to see, $IP^*\geq \beta$.

Now assume we have an approximation algorithm for weighted set cover. What the paper is saying in the lemma is that you can do a pre-processing before starting the approximation algorithm as follows. You can scan through the sets and add any sets that have weight $\leq \beta/n$. Since there are $n$ elements the additional cost is at most $\beta$. Then they claim that

  Since $\beta$ is a lower bound on $IP^*$, this cost is subsumed in the approximation.
  And this is the statement I did not understand.

The goal is to give an $O(\log n)$ approximation algorithm, starting with an algorithm that is already an $O(\log n)$ approximation algorithm, and optimizing it further. Adding the low cost elements results in an approximation ratio of $1 + O(\log n) = O(\log n)$, since the total weight of sets we add is $\beta$, which is also an upper bound on the value of the optimal solution.


Ensure a vertex has the highest flow in max-flow algorithm Let's suppose we have a supplier, sorting facilities, shipping companies and
a target warehouse.
We produce n packages of the product, and each goes to a different sorting facility (so every facility receives exactly one package).
A sorting facility then passes the processed product to a shipping company,
each sorting facility is only connected to a limited number of shipping companies, meaning that It can only use a limited subset of all shippers to deliver the product to the warehouse.
Now, the company owner's brother runs shipping company A and the owner really want's to help his brother start up his bussiness.
We need to ensure that all packages are delivered, but company must A deliver most of them - so It's a max flow problem with a requirement, that vertex corresponding to company A has the highest flow of all the shipping companies vertices.
Here Is a sample graph representation I have came up with. Vertex 0 is the supplier, vertices 1-6 are the sorting facilities, vertices 7-10 are the shipping companies, and 11 is the warehouse.
Now, assuming vertex 7 is the owner's brother's company, we want to get a maximum flow in this graph such that flow through 7 is greater than flow through 8, 9 or 10
How can this graph (or any of the max-flows algorithms) be modified to ensure, that the requirement holds for vertex 7?

Add auxiliary nodes 8a, 9a, 10a between nodes 8, 9, 10 and node 11, so that for example we have 8 -> 8a -> 11. Set all the capacities on the (8 -> 8a, 9 -> 9a, and 10 -> 10a) edges to $c = 0$, and run max flow. If there is a solution (if the maximum flow through the graph is equal to the number $n$ of packages to be shipped) then congratulations - we are done. Otherwise, set the capacities to $c = 1$, and go again. And so on until you find the smallest capacity $c^*$ such that the maximum flow is $n$. If the flow through vertex 7 is larger than this capacity $c^*$ then we have a solution, but if not there is no solution. If you continue to increase up to $c = n$ and there is no solution, then the original problem has no solution.

As requested by D.W. I will elaborate on the correctness and efficiency of this solution. The simple method of increasing $c$ by $1$ each time to find $c^*$ can be improved by binary searching instead: as $c$ increases the maximum flow will also increase up to $n$, and therefore we can binary search on the possible values of $c$ in order to find the smallest $c^*$ such that the maximum flow is $n$. This improves the number of calls to a max-flow subroutine from $n$ to $\log n$.
In order to show correctness I will set up some more notation. In any allocation of flow to the graph, let $f_0$ be the flow through the special warehouse, and $f_1, \ldots, f_k$ the flow through the other warehouses. We will call an allocation of flow "feasible" if $f_0 + f_1 + \cdots + f_k = n$ and $f_0 > f_i$ for all $i = 1, \ldots, k$ and "infeasible" otherwise.
Suppose there is no feasible flow. Then no matter how we set $c$ in our algorithm, it will never find a feasible flow either (introducing capacities to vertices only limits the set of solutions). Therefore the algorithm gets the correct answer in this case.
Suppose there is a feasible flow. Out of all possible feasible flows, choose one which minimises $c' = \max_{i = 1, \ldots, k} f_i$. Then there is no feasible flow where $f_i < c'$ for all $i$, and there is a feasible flow where $f_i \leq c'$ for all $i$, and hence our algorithm will arrive at $c^* = c'$. However, the algorithm may not arrive at the same flows: in particular if $g_0, g_1, \ldots, g_k$ are the flows found by the algorithm, we are guaranteed that $g_i \leq c'$ for all $i = 1, \ldots, k$, but we may not have $g_0 > g_i$ for all $i$.
I think this is a problem with the algorithm actually: it finds $c^* = c'$ correctly, but needs some help in order to figure out whether flow through the special node can be made strictly larger. There are some things you could do with the residual graph here, or you could use a reduction to a circulation problem with lower bounds on capacities: use the algorithm above, but as a final step introduce the constraint that the flow through the special node must be at least $c^* + 1$, and check for a solution.


How does Warrens Abstract Machine work? I've recently learned about Prolog and Logic programming which I find pretty cool, but the compiler is currently like magic to me and I want to know how they work.
After a little bit of research I discovered that logical compilers are based on Warrens Abstract Machine (WAM). I've tried to find some information on WAM, but the Wikipedia page only describes what it is and not how it works and the book Warrens Abstract Machine: A Tutorial Reconstruction doesn't read very well for me.
Could I please have basic explanation of how WAM works?

This may be a question that's too broad to cover here.
The WAM covers a lot of Prolog-specific capabilities (e.g. unification, nondeterminism, the cut) that other abstract machines do not, and its design is also quite subtle in its details (e.g. garbage collection on backtracking is designed into the machine). There is a reason why the WAM Book is 130 pages long: it is complicated and hard to understand!
Still, the WAM Book is the best explanation that I'm aware of, and there may be no substitute for going through that, working through the exercises, hand-compiling small examples of your own, and possibly even implementing parts of the WAM in a suitable language.
I'm going to suggest that you try with it again, and ask specific questions here if you get stuck on something.
But if that doesn't sound like something that you want to do right now, you may want to go through a less complicated abstract machine first, such as the SECD machine. The WAM was, after all, influenced by abstract machines that came before it, and that is assumed knowledge.


Are deterministic and nondeterministic Cellular Automata equivalent? It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs.

I haven't even found a definition anywhere. It feels like NCAs can't be equivalent to CAs (not in the same lattice at least), even though I can convert a NFSM to a FSM the possibly exponential growth of the required states doesn't fit to the CA definition, it would need a higher dimensional lattice (i.e. more local neighbours).

So, are NCAs and CAs equivalent ? Are there papers or books discussing this ?

I think you should define precisely what you mean by equivalent, and
possibly what kind of CA you are willing to consider, with what
communication grid. So I will just assume the simplest interpretation.

Given that it is fairly easy to build deterministic cellular automata
with Turing power (even with a 1 dimemsional grid), and that according
to the current wisdom of the Church-Turing Thesis, we have little
chance to improve on that, my best bet is that non-deterministic
cellular automata cannot be more powerful than deterministic
ones. Given that adding non-determinism can only increase the
computational power, i.e. a deterministic automaton is a special case
of non-determinism, whe should not expect non-deterministic cellular
automata to be less powerful than deterministic ones.

Hence, in terms of computational power, deterministic and
non-deterministic cellular automata are equivalent.


Is a PDA's stack size linear bounded in input size? I was thinking as follows: At each step, a PDA can put arbitrary many symbols onto the stack. But this number is constant for every individual PDA, so it can't be more than, say, $k$ symbols per step. Using only regular transitions, the stack can rise to maximally (more or less) $kn$ symbols in a run on an input sized $n$.

But what about $\epsilon$-transitions? Is there a simple argument why their maximum number should as well be independent of the input size?

So, in short: Is a PDA's stack size linear in the input size?

No. In NPDAs, you can have cycles of $\varepsilon$-transitions that add symbols to the stack. Thus the stack content can be unbounded.

Proving that CFL ⊆ CSL via automata is tough; the trusted route via grammars seems advised.


Algorithm to convert rendered number back into symbolic form If you have a number such as $3.14626437$ and you need to know what symbols create it, as far as I know, there are two tools:

1- ISC

2- wolframalpha

and the answer is $\sqrt2+\sqrt3$

I am wondering what algorithm these websites are using and how much is their complexity?

RIES is another method for finding closed-form expressions; its web page describes the algorithm it uses.

If you do a Google search for algorithm for inverse symbolic calculator, you will find Wikipedia's page on algorithms for finding integer relations between multiple real numbers (as the page describes, you look for an integer relation between $x$, the number you care about, and a list of other standard mathematical constants).


relation between ntime and dtime Given DTIME($n^2$) contains NTIME($n^{100}$) show that P=NP.

I think it's supposed to be straightforward but I just can't see it.

Take $L$, a language in NP. $L$ has a Turing machine which runs in NTIME$(f(n))$. If $f(n)$ is $\Omega(n^{100})$ it's obvious, but what about $O(n^{100})$?

Hint: What is the time complexity of the fastest nondeterministic Turing machine that is a decider for $SAT$?


Prove grammars with long derivations generate infinite languages Suppose $G$ is a CNF (Chomsky normal form ) grammar which has $v$
  variables. ($|V| = v$) If there is a string that $G$ derivatives in
  more than $2^v$ steps, prove that $L(G)$ is infinite.

Any ideas how can i prove this?

I know derivation tree in a CNF grammar is binary. So my idea is to calculate maximum number of leaves in the tree and prove that if $L(G)$ is finite this can't be reached in more than $2^v$ steps. Can anyone help me how to prove this part?

G is in CNF. We can ignore the derivation S->eps since it is the only derivation of an empty string so it is only part of a derivation of length 1. I assume that the start symbol S counts as one of the "variables" or non-terminals, so there are (v-1) other non-terminals. S can only appear at level zero of the derivation.

In a derivation, every step replaces a non-terminal with a terminal, or increases the number of non-terminals by 1. Therefore, if N generates a string x of terminals and non-terminals, x is either a single terminal with a one-step derivation, or x consists of at least two symbols.

If G generates a string s, and in the derivation a symbol N derives itself (N -> x N y, where x, y are strings of terminal and non-terminal symbols), then we found that either x or y are non-empty, and derive non-empty strings of terminals (since they were part of a derivation). And since we derived N -> x N y, we can derive N -> $x^k N y^k$ for any k > 0, so the language is infinite.

So we have seen that if a non-terminal N occurs twice in any derivation, the language is infinite. Now look at the derivation of a tree. Level k of the tree has at most $2^k$ nodes. If the tree has a height h, then the nodes at levels $k = 0$ to $k = h-1$ may have contributed a derivation step, for a total of $2^h-1$ derivation steps. If a string s is derived in more than $2^v$ steps (actually, in $2^v$ or more steps), then it has a height v+1 or greater. If you look at a node at level v+1, then there are v non-terminals at levels 1 to v, and since there are only v-1 non-terminals after than S, one non-terminal must occur twice. Which makes the language infinite.

We can make any grammar epsilon-free quite easily: Introduce a new symbol $S_0$ and a rule $S_0->S$, so that $S_0$ will not occur on any right hand side of a rule. Then as long as there is a derivation N->eps with N ≠ $S_0$, remove that derivation, and for every rule with N on the right hand side, add rules with any possible subset of these N's removed. Remove all duplicate rules, and the only rule containing eps that is possibly left is $S_0 -> eps$. In an epsilon-free grammar we have the same fact that if the grammar contains a string s where the derivation contains a derivation N -> x N y where x or y are non-empty, then the language is infinite.


Understanding kQBF: changing order of quantification? 2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(X,Y,Z)$ is valid. But what I can't understand is following:

Can't we change order of quantification? E.g. isn't following true $\exists X~\forall Y:\varphi(X,Y) = \forall Y~\exists X:\varphi(X,Y)$?
If we can, what prevents us from doing this in the second case and reducing 3QBF to 2QBF? E.g. $\exists X~\forall Y~\exists Z:\varphi(X,Y,Z) = \exists \{X, Z\}~\forall Y:\varphi(X,Y,Z)$.

The main idea is to reduce the number of alternations to one.

What I thought:

Let we have a formula $\forall x_1~\exists y_1...\forall x_k~\exists y_k:\varphi(x_1,y_1...x_k,y_k)$. Then we can construct a truth-table (theoretically) where columns will be sorted this way:

x_1 x_2 ... x_k y_1 ... y_k ф
  0   0 ...   0   0 ...   0 _
  0   0 ...   0   0 ...   1 _
  .   . ...   .   . ...   . .
  .   . ...   .   . ...   . .
  1   1 ...   1   1 ...   1 _

Then we can divide table (no row/column moving) in $2^k$ parts each containing $2^k$ rows. If each of that part has satisfiying assignment, formula is valid. But that means that there is no difference at all in which order we should assign variables, since truth-table of formula is independent on the quantifiers.

In other words following must be true: $\forall x_1~\exists y_1...\forall x_k~\exists y_k:\varphi(x_1,y_1...x_k,y_k) = \forall x_1~\forall x_2...\forall x_k~\exists y_1...\exists y_k:\varphi(x_1,y_1...x_k,y_k)$

It seems that we can change order of quantification in first order logic. Compare following sentences:

There exists a village such that all villagers have shovels. Here we have two alternations ($\exists X~\forall Y~\exists Z$).
Every villager has a shovel in some village. This is logically equivalent, but has only one alternation ($\forall Y~\exists Z~\exists X$).

There are 4 another ways to move quantifiers and all of them will produce equal statements. Yet I do not have any reasons to think we can't change order of quantification in logic.

Ability to change order of quantification $\Leftrightarrow \mathsf{NP = PSPACE}$. This problem is open for decades and logic rules I used are not something really new. So, this is strange... like I am missing something.

$\exists x\forall y \hspace{1mm}\varphi$ is not equivalent to $\forall y \exists x \hspace{1mm} \varphi$.

Consider for example the formula "for all $x$ there exists $y$ such that $y=x^2$". When evaluated over the reals, this is true (every real number has a square). However, if you switch the quantifiers you get the statement "there exists $y$ such that for all $x$ it holds that $y=x^2$". Note that this has an entirely different meaning, since now the statement reads "there exists a real number which is the square of all real numbers", and this is obviously false.

The order of quantifiers is important, so you can't trivially reduce $kQBF$ to $(k-1)QBF$.


Can a cross-compiler be self-hosting? My understanding is that a self-hosting compiler will take as input the language it is written in and a cross-compiler will output a language which runs on a platform which is different to what it runs on.

Can we combine these two compiler types into one?

This is certainly possible, and there are two possibilities:

There are two compilers for a language. For example, Haskell has GHC, and GHCJS, which is a JavaScript cross-compiler. GHC is written in Haskell, and GHCJS is written in Haskell (and normally compiled with GHC), so GHCJS is a self-hosted cross-compiler.
You run your self-hosted cross-compiler in a target language. So, if you had a Foo to Python cross-compiler, and it's the only compiler for Foo, and it's written in Foo, it can be self hosting, but you would have to cross-compile it, then run the result in a Python interpreter.

Basically, be careful that you don't confuse a language with a compiler. A language can have many compilers.


What is the difference between Simulated Annealing and Monte-Carlo Simulations? What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?

Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness.

In Monte Carlo simulation, we are aiming at computing some quantity $A$ by finding an easily samplable random variable $X$ whose expectation is $A$. We estimate $A$ by averaging many samples of $X$. More sophisticated versions of this are rejection sampling and MCMC.

Simulated annealing is a heuristic for optimizing an objective function $f$ over a domain $D$. We start with an arbitrary point $x \in D$, and then try making local changes which improve the value of $f$; this is local search. In simulated annealing, we also allow making local changes which worsen the value of $f$, with some small probability. The probability is smaller the more the change makes $f$ worse.


What happens when you don't use a metric in k-means? K-means is a clustering algorithm which works like this:

def kmeans(int k, Coordinate[] points):
    Step 1: initialize k cluster centers to any (distinct) coordinates
    Step 2: check which points are closest to which cluster centers
    Step 3: move the cluster centers so they are central to their nodes
            e.g. by taking the average coordinate
    Step 4: back to step 2 (with some stop criterion)

Usually, the Euclidean metric is used in Step 2. What happens when no metric,  but only a (symmetric) function $d: points \times points \rightarrow \mathbb{R}$ is used? Can k-means still produce meaningful results?

You should use k-means when you have coordinates and a euclidian distance metric. Its not just the distance that matters - you need to reassign cluster centers. So if you have coordinates, why use something other than euclidian distance? If you don't have coordinates, you can't use K-means.


Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$ Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation.
  Assume that $t(n)= \Theta (1)$ for suffucuently small $n$.
  $$t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$$

I am a bit confused on how to approach such question, I did solve questions such as $t(n)=3t(n/4)+nlogn$, but never saw an example where $t(n)=at(\frac{n}{b})+ct(\frac{n}{d})+f(n)$.

Any solutions or hints on how to solve this problem would be appreciated.

If we are not restricted by "using the master theorem", then either a better version of the master theorem, the versatile Akra-Bazzi method or the elementary way to show many recurrence relations mean $\Theta(n)$ or $\Theta(n\ln n)$ is an easy approach.

Otherwise, let us see how we can use the master theorem. We assume here $t(n)\geq 0$ for all $n \geq 0$, although the final asymptotic answer is actually valid without that non-negativity restriction. Let $c$, $m$ be two positive constants such that $t(n) \lt m$ for all $n < c$.

To bound $t$ from below, let us define function $t_1$ by
  $$t_1(n) = \begin{cases}
    0 & n <= c\\
    t_1\left(\frac{n}{5}\right)  + n & n\gt c
  \end{cases}$$

To bound $t$ from above, let us define function $t_2$ by
  $$t_2(n) = \begin{cases}
    m & n <= c\\
    t_2\left(\frac{n}{5}\right) + (t_2\left(\frac{n}{5}\right) + m) + n & n\gt c
  \end{cases}$$

The rest of this solution will be proving $t_1(n)\leq t(n)\leq t_2(n)$ for all $n\ge 0$ by  induction followed by applying the master theorem to $t_1$ and $t_2$ to show that $t(n) = \Theta(n)$. It is left as an easy exercise for interested readers.


Maximizing the rank of a binary matrix by zeroing matrix entries Given a Square Binary Matrix.

The entries of the Matrix are the integers modulo 2 (i.e., GF(2)). The Rank of the Given Matrix is an Integer value R0.

What is the fastest known Algorithm to maximize the Rank of the matrix if the following operations are permitted:

Each 1 entry in the matrix can be replaced by a 0.
No 0 entry can be set to 1.

Approaches Tried:

Since Rank is the measure of number of independent vectors, the current attempt involved using a Gaussian elimination to simplify the matrix. The idea behind it was, if a larger Rank is possible we would be able to obtain the matrix for that Rank, by using the original and the simplified matrix. I am not sure if that is going to work.

Tried searching for some references, but not much success.

The largest rank equals the size of a maximum matching of the corresponding bipartite graph, for which there are known efficient algorithms; see for example Wikipedia.

On the one hand, if the graph contains a matching of size $m$, then we can delete all other entries, thus obtaining a matrix in which an $m\times m$ minor is a permutation of the identity, and so of rank $m$. Thus the maximum achievable rank is at least the size of any matching.

On the other hand, suppose that by deleting entries of the original matrix $A$, we can obtain a matrix $B$ whose rank is $m$. The matrix $B$ must contain an $m\times m$ minor $C$ whose rank is $m$ (find a set of $m$ rows which form a basis for the row space, then a set of $m$ columns which form a basis for the column space). In particular, $\det C \neq 0$ and so there must be a "generalized diagonal" in $C$ which consists only of $1$s (since $\det C$ is the sum of the products of all generalized diagonals). This generalized diagonal appears already in $A$, and constitutes a matching of size $m$ in the corresponding graph.


Why do logic gates behave the way they do? I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do.

Why for example:

1 AND 1 = 1  // true AND true
1 OR 0 = 1   // true OR False
0 AND 1 = 0  // false AND true

And so on..
Is it a conditional definition for example, like it is like that by definition?
Or there is a logical/intuitive explanation for these results?

I have searched google, also looked at the Wiki page of logic gates for an explanation of 'why' but I can only find 'how'.
I would appreciate any answer or resources.

As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here:

A|B||0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f
-+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
0|0||0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1
0|1||0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1
1|0||0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1
1|1||0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1

A and B are the inputs, 0 through f are the possible permutations of outputs.

These gates have been named:

0 = FALSE
1 = AND
2 = A NIMPLY B (A AND NOT B)
3 = A
4 = B NIMPLY A (B AND NOT A)
5 = B
6 = XOR
7 = OR
8 = NOR
9 = XNOR
a = NOT B
b = B IMPLY A (A OR NOT B)
c = NOT A
d = A IMPLY B (B OR NOT A)
e = NAND
f = TRUE

6 of these (0,3,5,a,c,f) discard one or both inputs. The IMPLY and NIMPLY gates are rare, though they are certainly used in formal logic. AND, OR and XOR are easiest for humans to reason with, but for physical hardware, NOR and NAND are also used heavily, because they can be simpler to implement and make smaller circuits. The same probably holds for XNOR.

So, as stated earlier, it's not so much that we decided that the gates should behave this way, but that 16 possible gates can be defined, and we came up with descriptive names for them.


Do most bitstrings expand if they halt when executed by a Universal Turing machine? According to the counting argument, most bitstrings are incompressible or only slightly compressible.  However, the counting argument does not work in the opposite direction, since there are an infinite number of bitstrings that are longer.  So, the counting argument does not tell us whether most bitstrings will or will not expand when run on a universal Turing machine and halt.

Is it known whether most halting bitstrings will expand?

By 'expand' I mean that a bitstring $b_1$ generates a bitstring $b_2$ when run on a universal Turing machine,
\begin{align*}
 \mathcal{U}(b_1)=b_2,
\end{align*}
such that the length of $b_2$ is greater than $b_1$
\begin{align*}
\ell(b_2) > \ell(b_1).
\end{align*}

Both can happen.

The counting argument applies to all TMs that always halt.

In the partial world, you can construct Turing machines for both extreme cases (and everything in between) like so. Assume $T$ is a Turing machine. Construct

T<(x) = if |T(x)| < |x| then return T(x) else loop

and

T>(x) = if |T(x)| > |x| then return T(x) else loop

Note that if T(x) loops, both T<(x) and T>(x) loop; that's not a problem.
It's easy so see that for T<, all halting inputs contract, and for T> all expand.

Rice's theorem immediately shows that these expansion/contraction properties (and related ones) are undecidable, by the way.