What are the axioms of automata theory? Every theory has axioms and theorems derived from axioms.

How many axioms are there for automata theory? What are the axioms of automata theory?

Automata theory is a broad field and researchers keep inventing new types of automata. There is even a conference series on non-classical models of automata. So it is impossible to encompass all of automata theory. For classical models such as context-free grammars, recently formalized proofs of the most basic theorems have been carried out. These are derived from first principles (these are definitions in terms of set theory). See this example for an accessible account: https://www.react.uni-saarland.de/people/hofmann/jhofBA.pdf


Difference between equivalence and implication In terms of CTL formulae, what is the difference between equivalence and implication?

(prop = some proposition, && = conjunction, AG = CTL syntax for "globally holds")

E.g. AG (prop1 && prop2) versus (AG prop1) && (AG prop2)

Are those two formulae related by implication i.e. the left hand side implies the right hand side? Or are they actually equivalent?

First, to answer the question in your question title: the difference between equivalence and implication in CTL formulae is the same as the difference between equivalence and implication in propositional logic, that is, $A \leftrightarrow B$ is the same $(A \to B) \land (B \to A)$.

But your real question is whether $\mathrm{AG}\,(A \land B)$ is equivalent to $\mathrm{AG} \,A \land \mathrm{AG}\,B$. To solve this question, you have to look at the semantics of the operators AG and $\land$; that is, what do $\mathrm{AG}\,\phi$ and $\psi_1\land\psi_2$ mean (for arbitrary formulas $\phi,\psi_1,\psi_2$?

The semantics of CTL works via transition systems. Two formula are equivalent if they are true in exactly the same transition systems and states. Looking at the semantics of AG and $\land$, it should be fairly easy to decide whether there is a transition system where the one formula is true and the other isn't.


Push down automaton for Language of same number of as and bs The task

  Find a pushdown automaton $M$, so that $L(M)=\{w \in \{a,b\}^*\ |\ |w|_a=|w|_b\}$, where $|w|_a$ denotes the number of $a$s in a word $w$.

My solution

I'm using the Wikipedia notation.
$$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \{q_0\})$$
$$Q=\{q_0\}, \Sigma = \{a,b\}, \Gamma = \{Z_0, A,B\}$$
$$\delta\text{ has the following instructions:}$$
$$(q_0, \varepsilon, Z_0, q_0, \varepsilon),$$
$$(q_0, a, Z_0, q_0, AZ_0),$$
$$(q_0, b, Z_0, q_0, BZ_0),$$
$$(q_0, a, A, q_0, AA),$$
$$(q_0, b, A, q_0, \varepsilon),$$
$$(q_0, b, B, q_0, BB)\text{ and}$$
$$(q_0, a, B, q_0, \varepsilon).$$

Questions

Is this correct? Can it be simplified?
If so, how can I argue (not neccessarily proof) its correctness?

The usual approach is to prove by induction the following kind of statement:

  The set of configurations reachable from the initial state upon reading a word $w$ is ...

Here ... depends on $w$. Having proved this kind of statement, you can deduce which words are accepted by your machine, hence proving its correctness.


Resolution Algorithm - No new clauses The standard resolution algorithm returns false if no new clauses are added.

I know that if $KB \land \neg a \implies []$, it returns true by proof by contradiction, but how can I understand the false case intuitively?

When $new\subseteq clauses$ then, if we continued, the next line would be $clauses \leftarrow clauses\cup new$ but $clauses\cup new = clauses$ so we'd be doing the exact same calculation the next time through the loop deducing nothing new and looping forever.

The point is, if we "resolve" all pairs of clauses and deduce nothing new, then we've derived all the consequences from the original set of clauses. If we still haven't derived a contradiction at that point, then $\neg\alpha$ is consistent with $KB$ and thus $\alpha$ is not provable. This last isn't necessarily completely accurate either, as it only shows that $\alpha$ is not a propositional consequence of $KB$. For example, if $KB$ was $\forall x.P(x)$ and $\alpha$ was $P(t)$, then $\alpha$ is provable from $KB$ but not via propositional reasoning.


Cormen. Red-black trees. Why do we need to rotate the tree after fixing its properties? I am reading about red-black trees in Introduction to Algorithms, Second Edition by Cormen. Pages 316, 317.

I don't understand why we need to rotate the given tree. See (c) and (d) in the attached picture.

The author says that the following properties of a red-black tree can be violated after a new node has been inserted:

the root is black;
children of a red node are black.

The second property is restored in (b). The first property wasn't violated because we didn't insert the tree root. So why do we need to perform any other actions after recoloring?

After recoloring in (b), the following rule is still violated:

children of a red node are black.

Recoloring while preserving black height in step (b) introduces new double red nodes 2 and 7, which remains after step (c) and finally eliminated in step (d).


Time complexity of nested loops help How exaclty do you determine this specific codes runtime is theta(n^2)??I can see theres two while loops which go from i and j to n but would like a more precise way of determing this? If someone could explain is simple terms as I am very new to this I would appreciate it.

def f(n):

i = 0

  while i < n:

   j = 0

     while j < n:

      j = j + 1

 i = i + 5

Solution 01) Analysis what code does.

Your code execute the first loop n times.

And for each executions on first loop it will execute n times.

So the result will be n * n = n^2

Solution 02)
Try to count how many times execute the instruction

def f(n):
count = 0
i = 0
  while i < n:
   j = 0
     while j < n:
      j = j + 1
      print("execute:" + count)
      count = count + 1
 i = i + 1


Is it possible to have high compression but low predictability? Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol?

'impossible to predict' - sequence cannot be predicted theoretically. But I was also asking about the real life example (no polynomial algorithm).

Yes. A cryptographic stream cipher can generate an incredibly long string  (e.g. ChaCha20 can generate $256 \times 2^{128}$ bits) from a single small key (e.g. 256 bits).

If you do not know the key that was used this stream is impossible to predict.


Difference between greedy and work conserving scheduler for DAG For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do.

However, I found two different upper bounds on the computation time of $T$. For the following equations $T_{\infty}$ is the computation time on infinite processors and $T_1$ is the duration on one processor.

[1] Greedy Schduler (Theorem 1): $T = T_1/m + T_\infty$

[2] Work-Conserving Scheduler (Theorem 1): $T = (T_1-T_\infty)/m + T_\infty$

Both consider the scheduling of directed acyclic graphs where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to execute before task $v_j$ if there exists an edge $(v_i,v_j)$ between those two tasks. I have x threads that can execute those tasks. However, I am not 100% sure if [2] considers preemptive scheduling for their upper bound, but it does seem to be the case for their theorem 1.

In this presentation (page 41) I have found both equations for an upper bounds of the greedy scheduler.

Is there by definition any difference between the two schedulers?

If I understand well, it is the same scheduling method with different names. I think Work-conserving Scheduler is the more "official" one. "greedy" can indeed qualify many aspects of the problem and one should always precise which. greedy algorithm is a paradigm not a specific method for a specific problem.

Anyway about the upper-bound, the presentation of your last link says that it is:

$T < (T_1-T_\infty) / m + T_\infty$

but that a simpler one is generally used:

$T < T_1 / m + T_\infty$

Of course the latter is greater than the former but both are true. Also note that they are both equivalent to $T_\infty$ when $m$ tends to $+\infty$.


Maximum I/O Data Transfer if DMA is used I was reading lecture notes of Universiti Malaysia Perlis when I am came across following question:

  A computer consists of a CPU and an I/O device $D$ connected to main
  memory $M$ via a shared bus with a data bus width of one word
  $(16-bits)$. The CPU can execute a maximum of $10^6$ instructions per
  second. An average instruction requires $five $ processor cycles,
  $three$  of which use the memory bus. A memory read or write operation
  uses $one$  processor cycle. Suppose that the CPU is continuously
  executing “background” programs that require $95$% of its
  instruction execution rate but not any I/O instructions.  Now very
  large blocks of data are to be transferred between $M $ and $D$.

  Estimate the rate if DMA transfer is used.

P.S. Assume that one processor cycle equals one bus cycle.

The answer says:

$$10^6 * (0.05 * 5 + 0.95 * 2) = 2.15 * 10^6$$

Can someone explain the reasoning behind the answer ?

I could understand that $0.05$ is percent of time devoted by CPU
and $0.95$ is the percent of time devoted by DMA, but what about $5$ and $2$ ?
If it has something to do with cycles, then I did not understand the logic.

After reading more about it and reading the question again and again, I understood the logic

  The question says that on an average an instruction requires $5$
  $cycles$ and the CPU is busy $95$% of the time in executing those
  instructions. Out of these $5\ cycles$, $3\ cycles$ are needed for memory operations. During this time $DMA$ cannot access the memory.

So only $2\ cycles$ are left for $DMA$ to use for 95% of the time.
For 95% time DMA uses
$$0.95 * 2\ cycles$$

For rest 5% time, CPU isn't executing instructions, so all cycles are available, so DMA uses
$$0.05 * 5\ cycles$$

Total cycles available for DMA
$$(0.05 * 5 + 0.95 * 2)\ cycles$$

In $1 second$, CPU can execute  $10^6$ instructions. So rate of transfer is

$$
10^6 * (0.05 * 5 + 0.95 * 2) = 2.15 * 10^6
$$


Is there a connection between the Undecidability Theorem and "software complexity"? I was reading Complexity: The Emerging Science at the Edge of Order and
Chaos and a certain passage got me really intrigued.  When discussing
Chris Langton's explorations of artificial life algorithms, the author
paraphrases Langton stating the following about a certain set of
evolutionary algorithms:

This is the undecidability theorem, one of the deepest results of
computer science: unless a computer program is utterly trivial, the
fastest way to find out what it will do is to run it and see.  There
is no general purpose procedure that can scan the code and the input
and give you the answer any faster than that.  That’s why the old saw
about computers only doing what their programmers tell them to do is
both perfectly true and virtually irrelevant; any piece of code that’s
complex enough to be interesting will always surprise its programmers.
That’s why any decent software package has to be endlessly tested and
debugged before it is released and that’s why the users always
discover very quickly that the debugging was never quite perfect.

But I can't easily see how the undecidability theorem allows one to
conclude that "unless a computer program is utterly trivial, the fastest
way to find out what it will do is to run it and see".
Can such a connection be made formally, or was it more of an empirical
observation?

The author is here referring to the Halting problem, and possibly also Rice's theorem (without putting words into their mouths).
It says indeed that it's not possible to decide in advance whether a Turing machine will halt on any given input or not, thus it makes it impossible to decide in advance what the actual output of the machine will be.
This is the fundamental theorem of the field known as recursion theory, more known in these days as computability theory.
The computability theory comprises infinitely many complexity classes, which we are familiar with from complexity theory, but computability theory typically concerns itself with the complexity classes on the decidable/undecidable level: primitive recursive, through the computable class, to the recursively enumerable, and going infinitely beyond to the highly undecidable problems as can be studied via the arithmetical hierarchy.
There are many connections to our "normal" complexity theory, and indeed a very nice analog can be found from the arithmetical hierarchy to the polynomial hierarchy.


Is this a valid induction proof example ? Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH(
suppose a  root of rank k  has at least $2^k$ vertices in its tree
)is a valid one since it just repeating the statement that we are trying to prove ? What about the induction step?(Then a root ... in its tree.)

How should we add more information to make easy to follow and more convincing?

This is a perfect example of a sloppily written induction proof. Of course the induction hypothesis is not only repeating the proof's statement; otherwise, it would not qualify as a proof at all since it would be assuming the statement is true regardless of the ensuing argument. What is meant, instead, is that $k$ is then fixed and the induction step is conducted for this particular choice of $k$.

The following proof structure is more elegant and IMO much easier to follow (esp. for beginners):

Induction basis: [...]
Induction step: let $k$ be given.
Induction hypothesis (IH): let [statement you are trying to prove] be true for $k$.
Then [ensuing reasoning which shows the statement is true for $k + 1$ by making use of IH].

This makes it explicit for which $k$ the hypothesis should hold as well as what statement it is exactly that we are trying to prove in the induction step.


Determining interests from Twitter text using Latent Dirichlet Allocation I would like to  determine interests or hobbies that people have given their Twitter timeline data. Their timeline is their historical collection of tweets.

The result I am trying to achieve is to automatically label a user with a collection of interests such as:

Finance
Photography
Android Development

I have tried using a topic model, LDA, using an individuals tweets as the corpus but I am not so sure about the applicability of the results. LDA gives a collection of terms associated with the topics it found. This requires some manual interpretation to distinguish what the interest is.

For example you might get some results from LDA like the following:

[Twitter, Java, time, work, day]
[code, IPhone, mobile, look, job]
[football, fantasy, team, pick, score]

I can generally pick out the topics people are interested in here but its just the key word or topic identifier I am interested in not the other contextual terms like team, pick or score in the last example. Ideally I would like to transform these term-based results into something like the following interests:

[Twitter, Java]
[IPhone, Mobile Development]
[Fantasy Football]

I have considered how to do this using a supervised approach. Given your categories of interest and using a bag-of-words model with a naive Bayes classifier the task would be to determine which category the topic terms belong to.

This requires labelled data for each category of interest which could be quite time consuming to create. Is there a possible unsupervised learning approach that could work?

I may have gone down the wrong path using topic models, if so, what existing textual research areas could help.

Not looking for a complete solution to the problem, just any suggestions, references or links would be appreciated.

Thanks for your comments, reformulating the question lead me to a different way of thinking about the problem.

Getting an interest category list is actually reasonably straightforward for broad level hobbies it is just the labelled training data that may be hard to produce.

I found this paper on unsupervised text classification and this is probably a better fit than topic models in this scenario. It uses a small number of keywords (average 3) per category and segmented sentences to produce training data for a naive Bayes classifier.

I think I will use this with some Twitter specific text pre-processing and some sentiment classification to see if the categories are spoken of in a positive light.


Using SMT Solvers in formula checking I'm currently working on a static analysis work in which I need to check whether a given formula is met or not. I hope the following example clarifies my requirement.

Suppose we have a list of three-addressed expressions whose operators are simple arithmetic and bit-wise operators (such as add, sub, and, xor). Each expression could have constant literals or variable symbols. For example, consider the following list:

a = b + 1
c = d
c = c xor d
a = a + c
a = a + 4

What I need is that to see whether a given formula is established or not. For example, the following formulas:

a == b + <some_constants>   # In this example: Yes, because a == b + 5
a == d + <some_constants>   # In this example: No

So can a SMT solver (Z3 for example) help me in this situation? If not, could you please point me out if there is a suitable tool applicable for this requirement?

Yes, absolutely. SMT solvers are actually quite well suited for such problems. Unfortunately, the input language to them (SMTLib) is rather machine-oriented, but there are many "high-level" interfaces to many solvers, Z3 itself providing a Python interface, for instance.

For this problem, I'll use the Haskell SBV library, which translates your constraints more or less directly to Z3. Note that I've put the equations into SSA form (single-static assignment), as is usual in such analyses. The whole problem is:

{-# LANGUAGE ScopedTypeVariables #-}

import Data.SBV

q = do k1 <- sInt32 "k1"
       k2 <- sInt32 "k2"

       a0 :: SInt32 <- forall "a"
       b0 :: SInt32 <- forall "b"
       c0 :: SInt32 <- forall "c"
       d0 :: SInt32 <- forall "d"

       let a1 = b0 + 1
           c1 = d0
           c2 = c1 `xor` d0
           a2 = a1 + c2
           a3 = a2 + 4

       constrain $ a3 .== b0 + k1
       constrain $ a3 .== d0 + k2

Also note that I (arbitrarily) picked 32-bit integers, though you can go with other types as well as needed. As stated, we get:

*Main> sat q
Unsatisfiable

Meaning that there's no such k1/k2 that satisfy your equations, as you yourself observed. If we let go of the second constraint (by commenting out the very last line in the definition of q), we get:

*Main> sat q
Satisfiable. Model:
  k1 = 5 :: Int32
  k2 = 0 :: Int32

Here's the solver picked the arbitrary value of 0 for k2 since there are no constraints on it; but k1 became 5 as you predicted.

Long story short, yes; this sort of reasoning is absolutely possible with SMT-solvers; and there are high-level language bindings that let you express them rather concisely.


Reference Request for Synthesis New to the world of software verification and synthesis. It was suggested to me that the book "Principles of Model Checking" is a good reference for verification, but I am clueless about synthesis. Could someone refer a good book?

Try these slides http://www.cs.bgu.ac.il/~frankel/HonoraryDay09/Slides/AmirPnueli.pdf or these ones http://www.cs.rice.edu/~vardi/papers/fmco06.ps.gz.

Also try googling "From Verification to Synthesis" and look at the work of Moshe Vardi and Orna Kupferman.


How to prove Big-O when $F(N)$ is even or odd If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n > n0$ for both expressions or do I just select the $3n^2+2$ expression?

you have to do for both expressions. But in this case, one expression is strictly smaller than the other one, so you can do it just for the $3n^2+2$ and say $4n+1<3n^2+2$ and therefore also $4n+1<cn^2$.


Strassen algorithm for matrix multiplication complexity analysis I see everywhere that the recursive equation for the complexity of Strassen alg is:
$$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me.
The parameter $n$ is supposed to be the size of the input, but it seems that here it is one dimension of a matrix while the input size is actually $n^2$.
Also, each matrix of the input is divided to 4 sub matrices so it seems the recursive equation should be $$T(n) = 7T(\tfrac{n}{4}) + O(n).$$

It's true that the parameter $n$ usually denotes the size of the input, but this is not always the case. For square matrix multiplication, $n$ denotes the number of rows (or columns). For graphs, $n$ often denotes the number of vertices, and $m$ the number of edges. For algorithms on Boolean functions, $n$ denotes the number of inputs, though the truth table itself has size $2^n$. There are many other examples.


Residence time in multi server system I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is:

R = S + QS

S is service time
Q is number of customers ahead
R is residence time

Then he describes a case with a single queue and two servers and says that the equation becomes

R = S + 1/2 SpQ

p is per-server utilization 0 < p < 1.

I don't understand why p is a factor here. Wouldn't all servers be busy whenever there are customers waiting in line? Why is this different from the single-server case? The explanation given in the book is copied on slide 25 here. I don't understand the reasoning. Why do we need p?

$Q$ represents the average of a discrete random variable.  Sometimes there are no customers waiting in line, sometimes there's one, and sometimes there are many.  So there is some probability distribution for $Q$.  The difference between a two-server queue and a single-server queue that's twice as fast, is the expected service time when the queue is empty except for the one customer receiving service.  That's the transition from state 1 to state 0 in the Markov chain:

Intuitively, when a customer reaches the head of the queue the service in the two-server system will take twice as long as with the single server that's twice as fast.  The expected service time with the two-servers is $S$, while the expected service time with the single fast server is $S/2$.  What's less intuitive is that customers will, on average, spend somewhat less time waiting to get to the head of the queue with the two-server system.

To see this, consider the case of a customer that arrives when there is one customer currently being serviced.  In the two-server case the arriving customer immediately gets the other server.  The total expected response time in this case is $S$, but that's all service time, no waiting time.  In the fast single-server case the arriving customer waits, on average $S/2$ time for the preceding customer to finish and then gets, on average, $S/2$ amount of service.  The total expected response time in this case is also $S$, but it's half service time and half waiting time.  Let's work out the exact difference:

Fast Single-Server

This is an M/M/1 queue with arrival rate $X$ and completion rate $S/2$.  The steady state distribution, $\pi_i$ for the Markov chain in the fast single-server case is
$$\pi_i = (1-U)U^i$$
where $U$, the server utilization, is $XS/2$.

Then the expected number of customers in the queue is
$$ Q_f = \sum_{i=0}^\infty \pi_i i    =
       \sum_{i=0}^\infty (1-U)U^i i =
  (1-U)U\sum_{i=0}^\infty U^{i-1} i      =
  \frac{(1-U)U}{(1-U)^2} = \frac{U}{1-U}.$$

Then by Little's law
$$ R_f = \frac{Q_f}{X} = \frac{U}{X(1-U)} = \frac{XS/2}{X(1-U)} = \frac{S/2}{1-U}, $$
but we want to represent $R$ as service time + waiting time, so
$$ R_f = \frac{S}{2} - \frac{S}{2} + \frac{S/2}{1-U} = \frac{S}{2} + \frac{-S/2 + SU/2 + S/2}{1-U} = \frac{S}{2} + \frac{US/2}{1-U} = \frac{S}{2} + \frac{S}{2}Q_f. $$

So we have that the waiting time is
$$ W_f = \frac{S}{2}Q_f = \frac{SU}{2(1-U)}.$$

Two Slow Servers

This is an M/M/2 queue.  We will again let $U = S X/2$ (this is Little's law for the utilization of each of the two servers, the reason the result is the same as in the fast-server case is that now $X$ is halved rather than $S$ being halved.)  The steady state distribution is:
$$ \pi_0 = \frac{1-U}{1+U} $$
and
$$ \pi_i = 2 U^i \pi_0, \;\;\; i \geq 1.$$

Now
$$ Q_s = \sum_{i=0}^\infty \pi_i i = \frac{2U}{1-U^2}.$$
(Derivation left as an exercise.)

Then by Little's law we get
$$ R_s = \frac{Q_s}{X} = \frac{S}{1-U^2} = \frac{2}{1+U}R_f, $$
which we want to represent as service time ($S$) plus waiting time.

$$ R_s = S - S + \frac{S}{1-U^2} = S + \frac{SU^2}{1-U^2} = S + \frac{S}{2} U Q_s, $$
and the waiting time is
$$ W_s = \frac{S}{2} U Q_s = \frac{SU^2}{1-U^2} = \frac{2U}{1+U} W_f.$$

Summary

The two slow servers always have a service time twice that of the fast server.  The two slower servers have a total response time that is $2/(1+U)$ times the fast servers' total response time.  ($0\leq U<1$, so the response time is always worse.)  But the two slow servers have a waiting time that is $2U/(1+U)$ times the fast server's waiting time, and so there's less waiting time with two slow servers.


Broken stick problem We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible.

The amount of glue need to connect two parts equal the maximum from their sizes. We can only glue two parts at one time.Can we solve this problem in the time complexity smaller than $O(n^3)$? I know only the answer, using dynamic table in this complexity

Homework?

See the problem "Cutting Wood", which involves cutting rather than glueing, but is otherwise equivalent. Provided the orders matters (as noted by Marzio).

  Your favorite sawmill charges by length to cut each board of lumber.
  For example, to make one cut anywhere on an 8 ft. board of lumber costs \$8.
  The cost of cutting a single board of wood into
  smaller boards will depend on the order of the cuts.
  As input, you are given a board of length $n$ marked with $k$ locations to cut

solution to exercise (pdf) Found in several places on the web, don't know the original.


Ratio of decidable problems Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested in other models of computation: Diophantine equations, word problems from rewriting rules using Turing machines, etc. An answer expressed in any classical formalization would be fine, though if you know how much the choice of formalization influences the answer, that would also be interesting.

Given the length $N$ of the statement of a decision problem, we can define the number $D(N)$ of decidable statements of length $N$ and the number $U(N)$ of undecidable statements of length $N$.

What is known about the relative growth of $U(N)$ and $D(N)$? In other words, if I take a well-formed decision problem at random, what is the probability of its being decidable for a given statement length?

 Inspired by this question which asks whether “most problems and algorithms [are] decidable”. Well, if you don't filter by interest, are they?

See Chaitin's research into Omega that shows, as I understand it, that undecidable problems are [paraphrasing] quite numerous, rampant or dense among statements chosen at random. However you have to be careful how you define $U(N)$ and $D(N)$ because they may be actually uncomputable functions. There is also some connections to busy beaver research. Identifying decidable and undecidable statements seems quite analogous to proving that busy beavers halt or do not halt. (e.g. some of all statements are in the form, “busy beaver [x] halts”).


Runtime analysis of a recursive algorithm with a tricky amount of work per recursive call I want to analyze the runtime of this algorithm:

int fun (int arr[], int n) {
    int result = 1;
    int i, j;

    if (n == 1)
        return 1;

    else {
            result = fun(arr, 2n/3);
            for (i = 1; i <= sqrt(n); i=i*2);
                for (j=0; j<sqrt(n)/i; j++)
                    result += arr[j];

            return result;
    }
}

I can see that the runtime recurrence should be something like

$\qquad\displaystyle T(n) = T\left(\frac{2n}{3}\right) + \Theta(X)$

where $X$ is the time of the extra operations per recursion.

I can also see that the extra operations are:

$\qquad\begin{align*}
  \sum_{i=1}^{\log(\sqrt{n})} \sum_{j=0}^{\frac{\sqrt{n}}{i}}1
    &= \sum_{i=1}^{\log(\sqrt{n})}\frac{\sqrt{n}}{i} \\
    &= \sqrt{n} \cdot \sum_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \\
    &= \sqrt{n}\cdot \log(\log(\sqrt{n}))
\end{align*}$

So all in all:

$\qquad\begin{align*}
  T(1) &= 1 \\
  T(n) &= T\left(\frac{2n}{3}\right) + \sqrt{n}\cdot \log(\log(\sqrt{n}))
\end{align*}$

But I could not continue from here to solve this recursion.

I can see three issues with what you have.

There are some inaccurracies in your sums. The outer one needs rounding of the upper boundary, the inner needs a $-1$.
$\displaystyle \sum_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \neq \log(\log(\sqrt{n}))$

The true value of the sum is $H_{\log(\sqrt{n})}$ (will change slightly if you fix the sums). It's true that the difference vanishes in $\Theta$ if you go that route, but better not write equality where it does not hold.
You dropped the recursion at the end! You should have

$\qquad \displaystyle T(n) = T(2/3 \cdot  n) + \dots$

From there, unfold the recurrence:

$\qquad\begin{align*}
  T(n) &= T(2/3 \cdot n) + f(n) \\
   &= T(4/9 \cdot n) + f(2/3 \cdot n) + f(n) \\
   &\dots
\end{align*}$

Spot a pattern, guess the solution and prove it correct by induction! This part is well covered by our reference question in case you have trouble.


max, min gradient and other terms in Neural Network This  link  contains a demo that trains a Convolutional Neural Network on the MNIST digits dataset in browser.

I am not getting below terms-
1. max, min gradient in each layer.
2.max, min activation in layers

3.Forward time per example

4.Backprop  time per example

Classification loss
L2 (a pooling mechanism??! but what this means?) Weight decay loss

What are the meanings of above terms according to given context (webpage demo)?

I suggest you to read an introduction to neural networks. I like neuralnetworksanddeeplearning.com, but I can also recommend chapter 4.3 of my bachelors thesis.

  max, min gradient in each layer

The gradient is like the derivative for high-dimensional functions. Imagine it as an arrow on a landscape. The arrow points into the direction of the steepest ascent, we want to go into the other direction (where the error becomes smallest).

  2.max, min activation in layers

The activation is $\sum w_i x_i$ (details and my BS thesis). Hence it is what each neuron returns, before the activation function is applied. Now you have many neurons per layer and hence a set of activations $A$. Hence you can take the min / max of it. I don't know why you would take the min, but the maximum might give you an indicator which neurons are "responsible" for which feature.

For CNNs, a complete feature map is usually considered to be one neuron (see my MS thesis for some more details). In your case, it simply seems to be the maximum feature returned (hence the brightest pixel; see input layer)

  3.Forward time per example

Measure how long it takes to process the input of a neural network.
(There is also the backward pass for the gradient)


How earliest that the data TLB (Translation Lookaside Buffer) can be accessed in an instruction execution pipeline? In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is:

List item before effective address calculation has started
during effective address calculation
after effective address calculation has completed
after data cache lookup has completed

=====================================================================

I think answer is 3.

Reason- Virtual address is given for TLB look up. TLB -Translation Lookaside Buffer, here Lookaside means during Address translation (from Virtual to Physical). But virtual address must be there before we look into TLB.

Please, explain which is the correct option. According to book the answer is 2.
I think that option 2, is wrong as it is explaining for physical address resolution and not for effective address calculation.

Often the effective address is the sum of a small constant and a value from a register. Not always, so this trick does not always apply. The trick then is to make a gamble: access the TLB based on just the value from the register, in parallel with adding the offset to it. Usually the small offset won't change the page being accessed, if that works out then you might have the result from the TLB a cycle earlier. Of course there needs to be a check afterwards to see if the upper bits of the virtual address didn't change, and if it fails the TLB access has to be re-done.

There is even a patent for this, with way more detail: Guess mechanism for faster address calculation in a pipelined microprocessor


Constant-time adding an element? Is a computer with infinite memory and infinite word size a Truing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we allow constant-time linked link element insertion (at the beginning of the list)?
I doubt this because element insertion requires memory allocation and allocation is usually not a constant-time operation.

Oh, I've found an $O(1)$ allocation strategy:
Because our memory is infinite, we may never deallocate: Just add memory at the end of the used space by incrementing a pointer.


What is the complexity of these tree-based algorithms? Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets.  Each node of the tree represents a subset, with the following properties: subsets represented by two children nodes of the same parent are disjoint, and their union is equal to the subset represented by the parent.  The root represents the full set of points, and each leaf represents a single distinct point.  So there are $\log N$ levels to the tree, and each level of the tree represents a partitioning of the points into increasingly fine levels of granularity.

Now suppose we have two algorithms, each of which operates on all of the subsets of the tree.  The first does $O(D^2)$ operations at each node, where $D$ is the size of the subset represented by the node.  The second does $O(D \log D)$ operations at each node.  What is the worst case runtime of these two algorithms?

We can easily bound the first algorithm as $O(N^2 \log N)$, because it does $O(N^2)$ work at each of $\log N$ levels of the tree.  Similarly, we can bound the second algorithm as $O(N \log ^2 N)$, by similar reasoning.

The question is, are these bounds tight, or can we do better?  How do we prove it?

Apply the master theorem.

The first algorithm takes $O(N^2)$ time because your underlying recurrence is

\[ T(N) = 2T(N/2) + N^2 \]

The second algorithm takes $N\log^2N$ time as you mention. If your work per node is as indicated (and is tight) then this bound is tight as well.

Update: as commenters point out, the assumption here is that the tree is weight-balanced: each child has half the nodes of the parent. This would imply the log N height bound you indicate, but is not implied by it.


What is the differences and similarities between refinement type and liquid types? Looking at the examples here and here both refinement type and liquid types look very similar. What are the differences and similarities?

They are, to a first approximation, the same thing. "Liquid types" come from LiquidHaskell (1, 2), which is a programming language and verification framework based on refinement types. The Scala repository that you link to is an implementation of refinement types for Scala.

In terms of programming language theory, refinement types is the technically correct and more general term. LiquidHaskell and the Scala repository are examples of implementations of refinement types.


Making a branch-and-bound algorithm more efficient for a large input I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course).

I tried implementing dynamic programming first, and that worked fine, but ran into memory issues with larger datasets, so I decided to try branch-and-bound.

My implementation works well for small datasets, but when I try and scale it, it hangs up like the DP algorithm, but I can't tell if it is because it is very slow or space inefficient.

The way I have implemented it is as follows (in bad pseudocode)

initialise global best value as 0
initialise taken list and leave list
initialise priority queue
initialise root node with take and leave lists
order items by (value/weight)
calculate upper bound of root
put root node in queue
while queue not empty:
    get queue element with highest priority (highest bound)
    if current node bound < global best:
        end because cant do better
    if current node value > global best:
        update global best
    if current node level < item count
        if weight with new item <= capacity
            create new take list by copying current node take list and setting take[level] = 1
            create new "left" node with new take list and old leave list
        create new leave list by copying current node leave list and setting leave[level] = 1
        create new "right" node with old take list and new leave list

The node class is:

class node(level, take list, leave list):
    set level as argument
    set lists as argument
    set value by iterating over take list and summing values
    calculate room in bag by capacity - total weight calculated with take list
    set bound by calculating using take and leave lists
    left child = none
    right child = none

My question is: would it be more efficient to calculate the take and leave lists by traversing the tree rather than to explicitly store the lists in each node? I thought it might be quicker to store the lists and just update them with every new node, but I am thinking now that it might run into memory problems with large inputs.

Is it not such a bad thing to have to traverse the tree every time I want to calculate the bound and should I worry more about space issues?

It isn't clear if you are asking about time or memory efficiency.  If you care more about memory, then it would be best to traverse the tree.  If you care more about time, then it would be best to copy and modify both lists at each node.  However, there are more than two alternatives.  You could store a single number at each node, which identifies the items in the knapsack.  For example, the binary number 10110 would denote the first, third, and fourth objects as being in the knapsack.

I don't want to do your homework for you, and you didn't ask me to, but I also recommend considering a more memory efficient DP approach if you haven't already.  Good Luck!


What does > mean in this TAOCP solution? For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd).
However, I fail to understand the solution given in TAOCP.

  Problem:
  Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.

  At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?

  In other words, given the pairs $(x_i, x_{i+1})$ for $1 \le i < N$, in random order, where the $x_i$ are distinct, how can the sequence $x_1 x_2 \ldots x_N$ be obtained, restricting all operations to serial techniques, suitable for use on magnetic tapes. This is the problem of sorting into order when there is no easy way to to tell which of two given keys precedes the other.

  Solution by Norman Hardy, c. 1967: Make another copy of the input file; sort one copy on the first components and the other on the second. Passing over these files in sequence now allows us to create a new file containing all pairs $(x_i, x_{i+2})$ for $1 \le i \le N-2$ and to identify $(n-1,x_{n-1})$. The pairs $(n-1, x_{n-1})$ and $(n,x_n)$ should be written on still another file.

  The process continues inductively. Assume that file F contains all pairs $(x_i,x_{i+t})$ for $1 \le i \le n - t$, in random order, and that file $G$ contains all pairs $(i,x_i)$ for $n-t < i \le n$ in order of the second components. Let $H$ be a copy of file $F$, and sort $H$ by first components, $F$ by second. Now go through $F$, $G$, and $H$, creating two new files $F'$ and $G'$, as follows. If the current records of files $F$, $G$, $H$ are, respectively $(x,x')$, $(y,y')$, $(z,z')$, then:

  If $x' = z$, output $(x,z')$ to $F'$ and advance files $F$ and $H$.
  If $x' = y'$, output $(y-t, x)$ to $G'$ and advance files $F$ and $G$.
  If $x' > y'$, advance file $G$.
  If $x' > z$, advance file $H$.

  When file $F$ is exhausted, sort $G'$ by second components and merge $G$ with it; then replace $t$ by $2t$, $F$ by $F'$, $G$ by $G'$. Thus $t$ takes the values $2$, $4$, $8$, $\ldots$; and for fixed $t$ we do $O(\log N)$ passes over the data to sort it. Hence the total number of passes is $O((\log N)^2)$. Eventually $t \ge N$, so $F$ is empty, then we simply sort $G$ on its first components.

So here is my question:

  If $x' > y'$, advance file $G$.
  If $x' > z$, advance file $H$.

What do the more than sign denote here? $x'$, $y'$, $z$ are strings, is it referring to string size?

What does > denote here?

It's not stated explicitly, but a reasonable meaning can be inferred from context.

The authors assume that the data can be sorted so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what to do and have a fixed relation.

For instance, if we wanted to sort natural numbers in increasing order, $>$ would mean the usual. I we wanted to sort them in decreasing order, you'd have to replace $>$ by $<$ in the solution.


Why is randomness a problem? (i.e. why do we care about derandomization?) I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people really care about derandomization results like P vs. BPP etc. My question is, what's the problem with randomness? If your algorithm is known to only require a polynomial number of random bits, then simply go ask a physicist to get the bits for you, which isn't a problem since you only need a tractable number of them, and then write them on the Turing machine tape and you're good! The goal of complexity theory is to figure out what we can compute in this universe, right? Well, this universe has randomness, right? So why do we care about derandomization? Theoretical and practical answers are both welcome.

Complexity theory is a mathematical theory which aims at addressing one shortcoming of computability theory, namely, it takes into account the use of resources. While it is true that in its early days it aimed to capture the notion of "practical computation" (even particular flavors such as parallel computation, supposedly captured by NC), it has since drifted apart and taken off from reality. As an example you can take higher steps on the polynomial hierarchy, higher complexity classes such as PSPACE, classes defined using alternation, and so on. Indeed, much of this material dates to the early days of complexity theory, showing that it lost touch with reality quite quickly.

Traditionally the two most important resources studied by complexity theory are time and space. However, other resources have also interested complexity theorists, for example alternation and randomness (not to mention the world of circuit complexity). Philosophically speaking, it is a fascinating question whether randomness dramatically reduces the computation time of some problems, or whether the gain is only polynomial (as hinted by the conjecture P=BPP). However, it does not seem to have any practical relevance, though not for the reason you mention. In practice there is no need for actual physical randomness (other than for cryptographic purposes), and pseudorandom number generators work well enough.


Is it computationally possible to voice-recognize and word-tag-time-align audiobooks to their actual text? I would like to know whether it is computationally possible for a computer to go through the words of an audiobook as input, output a file containing both the original audio and the text corresponding to each word (which could be reviewed by a human), and a silent software tag between each word marking each word boundary.

How much of this process could be automated, and how much of it would have to be carried out by a human?

This process would yield a file where instead of just being able to play, pause, and move forward and backwards by a given number of minutes, as could be done in the original audiofile, we could now also provide the following functionality:

move back and forth a given number of words
move back and forth a given number of sentences
move back and forth a given number of chapters (or subsections)
spell the current word
look up the current word in a dictionary
accurately repeat over and over, the text between any two markers, with a custom number of seconds between each repeat (which is good for learning / memorizing stuff)

Note that while audio books were primarily designed for blind people, has increased functionality would both give them more power as well as empower people with learning disabilities or both.

UPDATE: Since the audiobook is created from a text (either a text file or a textbook which can be read using OCR), I wish the case to be considered where the source words and punctuation are available. My problem is having the computer assign a time t_(w_i) to the beginning of each word w_i and store these in the output sound+wordTimes file (which could be post-edited for inaccuracies by humans). I have not seen anything that does this so far.

This link seems to suggest that what I am trying to do is possible (via a technique called forced alignment).

The fact that humans can understand audio books shows that it is computationally possible. This does not make the problem easy for an AI. It also does not mean that you can write a formalism of the language in audio form for parsing. Anything involving audio / recordings is going to involve lots of fuzzy data. This is not generally what someone would call parsing, but instead speech recognition. If you can properly recognize words in the correct context then the rest of the stuff you mentioned like dictionary lookup, and moving around a book is basically trivial.

It is easier to do this if you already have the words though. I would recommend something like splitting the audio based on breaks, and then applying speech recognition on each section to make sure the word matches the audio that was split. This is to check if errors in splitting exist. If there is an error where the word does not match the audio a human could be prompted to manually split them.


Extend reachability to total ordering Given a finite DAG $G = (V, E)$ with $|E| \in \mathcal{O}(|V|)$, I want to compute a total ordering $<$ over $V$ that is compatible to reachability: If there is a transition $(u, v) \in E$, then $u < v$.

The only way I could think of was to use Floyd-Warshall to compute a reachability matrix and then somehow extend that to be total. This would require cubic time, which is too slow for my needs. I require a quadratic time algorithm at most. In a publication I read that this is actually possible in linear time but no procedure or further explanation was provided.

You can compute a topological ordering of the vertices in linear time.


If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$ If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$.

I found a proof on Wikipedia that I didn't fully get:
https://en.wikipedia.org/wiki/Co-NP

In the line "from this it follows that the set of complements..". Why does it follow? It seems like the author took a complement from both sides of the equation, but that can't be right, can it?

We will show the contrapositive: if some NP-complete problem is in coNP, then NP=coNP. Suppose that $L$ is some NP-complete problem which is in coNP. Let $A$ be any problem in NP. Then there is a polytime reduction $f$ from $A$ to $L$ (since $L$ is NP-complete), which means that $x \in A$ iff $f(x) \in L$. Since $L$ is in coNP, this shows that $A$ is in coNP. Hence NP is a subset of coNP.

Now let $B$ be any problem in coNP. Then there is a polytime reduction $f$ such that $x \in B$ iff $f(x) \in \overline{L}$ (since $L$ is NP-complete and $\overline{B}$ is in NP). Since $\overline{L}$ is in NP, this shows that $B$ is in NP, and so coNP is a subset of NP. We conclude that NP=coNP.


How would one construct conjunctively local predicate of order k for checking if a shape is Convex? I was reading Minsky's and Papert's book on perceptrons and it had the definition of conjunctively local as follow (look at the last images if its still unclear):

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and:
$$
\psi(X) = \begin{cases}
1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\
0 \text{ otherwise. }
\end{cases}
$$

Then in the book they claim that testing if a figure $X$ drawn on a 2D Euclidean pixel plan $R$ is conjunctively local of order 3. First recall how one would text for convexity on $R$. Essentially one woul look at three points/pixels and draw a line segment joining the points and if the third chose point between them is not in the drawn figure $X$, then it would not be convex.

My question is given this knowledge, how does one show that $\Psi_{convex}(X)$ is conjuctively local of order 3? The order 3 seems sort of clear to me because each $\varphi$ only needs look at 3 points to test convexity. However, it remains unclear to me how one would construct a general $\Psi(X)$ such that it always test correctly for any drawn geometric shape if its convex or not. I guess maybe part of my quesiton is that the definition of conjuctively local is not clear to me. Is it correct to think of $\Psi$ as a function only on the given geometric shape or is it also a funciton fo the whole plane $R$? It seems clear how to construct $\Psi$ if we know the shape in advance but otherwise it doesn't seem we can fix one single architecture and be able to text for convexity.

One way to construct $\Psi_{\mathrm {CONVEX }}$ is as follows:
define $\phi_{i,j,k}(X) := \begin{cases} 1 & \text{if $(x_i,x_j \in X \Rightarrow x_k\in X)$ } \\ 0 & \text{otherwise}\\\end{cases}$.

Now, we define the set $\Phi$ by picking all pairs of $x_i,x_j\in R$ and all $x_k$ that lie on the line segment between them, i.e. $\phi_{i,j,k}\in \Phi$ for all $x_i,x_j\in R$ and all $x_k\in \{x\in R\mid \exists\lambda\in [0,1]: x=\lambda x_i + (1-\lambda)x_j\}$.

Note that each $\phi_{i,j,k}$ depends on only three values of $R$ and that the shape $X$ is convex if and only if all $\phi_{i,j,k} \in \Phi$ have value $1$. So, according to your definition, $\Psi_{\mathrm {CONVEX }}$ is conjuctively local of order $3$.

This does not seem like a very practical approach to determine the convexity of a shape, in particular when $R = \mathbb{R}^2$, since that means $\Phi$ is of infinite size.

So the basic idea is that for given indices $i,j,k$, the $\phi_{i,j,k}$ are functions of $X$ and exactly three points of $R$: $x_i,x_j$ and $x_k$. The selection of their indices (i.e. the set $\Phi$) is independent of $X$, but does depend on $R$.


Choosing the right function I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining).
What is a good hasing function that guarantees a good distribution of the keys? that means to use all indexes of the array from 0 to 3.

No hash function can guarantee a good distribution. All you can do is finding a hash function that will usually create a good distribution.
The table size is quite important for this: If the table size is a prime p, then just using n modulo p as the hash value is usually quite good. Note that in your case, 4 is not a prime. Actually all your values are multiples of the table size. And if you has pointers for example, then it is quite possible that all pointers are multiples of 8 or 16, so having a table size of 4, 8 or 16 is not clever.
Obviously if your integers are multiples of 4, but with all four possible values modulo 16 being equally minded, then (n / 4) modulo 4 would work quite well. But in general, you should avoid an unfortunate table size like the one you have.


Finding an element in an unsorted array equal to its rank in $O(n)$ time I'm trying to figure out a way to think about this problem. Background: Given an unsorted array of distinct integers (can be positive or negative), I want to determine if there is an element in the array that is equal to its rank (i.e. if I do $S = Sort(Array)$, I want to find an element s.t. $S[i] = i$).

Some approaches I have thought about.

Radix sort: But there's no guarantee on what is the largest/smallest element here
Any comparison based sorting method: But that gets me at least $O(n \lg n)$ time.

So it seems that I am not supposed to sort before I figure out what the ranks of the elements in the array are. I also feel that it needs to be a selection type algorithm, but I am not sure how that can be applied here. Any ideas on where to go from here?

You can preprocess the array to transform all negative numbers to $0$, and to transform numbers greater than $n$ to $n+1$. This transformation does not change the result because negative numbers and numbers greater than $n$ is not able to equal to its rank. This transformation only costs $O(n)$ time.

Now you can do counting sorting with $O(n)$ time.


Construct a TM for checking if a set of parentheses are well formed This was a solved example given in my textbook. When I tried to solve this, I got a different TM that was given as the solution. I tried running a sample string through my TM,  and somehow got the correct answer.
Still the answers dont match. Please let me know if there isvsomething I've missed.
This may sound a simple school homework but I would be grateful for any help

The one in ink is my solution
(https://i.stack.imgur.com/PiJX6.jpg)

This is the textbook answer.
(https://i.stack.imgur.com/p6HY7.jpg)

A very important fact about Turing machines is that there may be many equivalent Turing machines for the same language. In other words, just because your answer and the book's answer are different Turing machines, they may both be correct answers. There is not just one Turing machine for any given task.

I am not sure if your Turing machine is actually correct (building a Turing machine without any errors is hard!), but if you answer the questions in my comments I can probably figure it out and update this answer. We can also try a few more input strings to check.


In a DAG, does there exist a sink for all vertices in the DAG? The following statement is considered true:

  In a DAG, for every vertex $v$, there exists a sink $s$ such that
  there is a path from $v$ to $s$.

However, my counter example to this is a binary search tree. The leaf nodes in a binary tree do not have a path from themselves to a sink. Hence, am I interpreting this statement incorrectly?

A sink is a vertex with an out degree of zero. The leaf nodes of a binary search tree are the sinks. This is the trivial case of the statement as a path always exists from a node to itself, this path contains no edges, however the statement never said for vertex $v$, the sink $s$ could not be itself. Without this not only is the statment not true, but for every graph it is untrue since all DAGS have at least one sink and that sink could not be paired with another sink since that defeats the nature of a sinc.


How is integer factoring not in $P$? Everyone keeps claiming that integer factoring is in $NP$ but I just don't get it... Even with the simplest algorithm (division with all integers up to $\sqrt{n}$) the complexity should be $\sqrt{n}\log(n)$... How is that not in $P$? Is there something I'm missing?

One of the things to remember when dealing with natural numbers (and others, but naturals are the central things here) is the encoding, and that the definitions of $P$ and $NP$ reference the length of the encoding of the input on a Turing Machine (or something closely equivalent).

So the input to integer factoring, as a decision problem, is typically two numbers $n$ and $k$ in $\mathbb{N}$, and the question is whether $n$ has a factor $d \leq k$.

So the magnitude of $n$ is $n$, but the size of its encoding may be only $O(\log n)$ (for example, in binary). This is exponentially smaller than $n$ (i.e. if we take $n' = \log_{2} n$, then $n = 2^{n'}$).

So then the $\sqrt{n}\log n$ "obvious" algorithm runs in time $2^{\frac{n'}{2}}\cdot n'$, which is exponential in the input size.


Maximum join of relations I have a question as follows

  Consider the relations $r1(P, Q, R)$ and $r2(R, S, T)$ with primary keys $P$ and $R$ respectively. The relation $r1$ contains $2000$ tuples and $r2$ contains $2500$ tuples. The maximum size of the join $r1⋈ r2$ is :

My attempt - Suppose all value of $R$ in $r1$ are same.  Then it should be $4499$.

But it's given $2000$. Am I missing something?

$r1⋈ r2$ is the natural join of $r1$ and $r2$/ That is inner join on the common attribute $R$, where $R$ is the primary key of $r2$. It is Cartesian product of $r1$ and $r2$ followed by selection.

For each element $(a,b)\in r1⋈ r2$, where $a=(p,q,r)$ and $b=(r', s,t)$, we must have $r=r'$. That is, $b=(r,s,t)$. Since $R$ is the primary key for $r2$, for any $a\in r1$, there is at most one $b$ that can "join" $a$. So we will have at most 2000 tuples.

By the way, I could not see why "Suppose all value of R in r1 are same. Then it should be 4499". It is not even an option in the original problem.


Are there more Turing-unrecognizable languages than recognizable? Say you generated a language by looking at the output of a lexicographic enumerator and flipping a coin for each string, adding it to the language on heads. What would be the chance of this language being Turing-recognizable?

Yes, in fact one can show that there are uncountably many languages (say by representing a language as a sequence of the form $\{0, 1\}^\mathbb N$ which can be interpreted as the binary form of some real number in $[0, 1]$) while there are only countably many TMs (as any TM can be represented by a finite string), so almost all languages are undecidable, i.e. assuming we draw a language from an uniform distribution the probability of it being decidable would be 0.


Markov chain probability in a complete graph I'm having a hard time understanding the following. Assuming we have a complete graph with $n$ vertices, where initially, one of those has an information. At this point, all we care about is that in each time $t$ a node that has the information chooses randomly one of it's neighboors and sends it the info, only if the receiver does not have it. We don't care how the sending is done.
Let $x_t$ be a random variable representing the number of nodes that have the info at the time $t$. It is indicated that $x_t$ can be modeled by a homogeneous increasing Markov chain. So, if at $t$, if $k$ vertices have he info, then the probability of another vertex receiving the information (using population protocols), that is, to have $k+1$ vertices know it is $\frac{2k(n-k)}{n(n-1)}$. Can someone explain why this stands?

The link to the paper I got this from is this: https://drive.google.com/open?id=0B0RiUAwpE4vnTlFqWmRHdlRYSFp4aDlYcWE5dWxUdWg2ZDA4
and the transition graph of the chain is shown in Figure 2.

The probability that you state is the probability that a random edge of the complete graph connects one of the $k$ nodes to one of the other $n-k$ nodes. This means that in your process, a random edge is chosen, and if exactly one vertex already knows the information, then the other vertex is made aware of it. Information spreads exactly when the chosen edge is of this form, which in your case happens with the probability you mention.


Which is more efficient? lg(n+10^n) higher than 2^lgn Based on the order by asymptotic growth rate which is more efficient?

Compute $\lim_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}$. This is
$$\begin{align}\lim_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}&=\lim_{n\to\infty}\frac{\log(n+1+10^{n+1})-\log(n+10^n)}{1}\\
&=\lim_{n\to\infty}\log\left(\frac{(n+1)+10^{n+1}}{n+10^n}\right)\\
&=\lim_{n\to\infty}\log\left(\frac{(n+1)/10^n+10}{n/10^n+1}\right)\\
&=\log(10)\\
&>1
\end{align}$$
where the first equation was using Stolz-Cesaro theorem (L'Hospital for sequences).
That this limit is larger than $1$ implies that for $n$ large enough $\log(n+10^n)$ becomes larger than $2^{\log(n)}$.


communities problem with union and find I am trying to solve the following problem:

Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry it is also true that $M[2][1]=1$). If $M[2][3]=1$, then $\{1,2,3\}$ is a community. If all other entries are $0$, then $\{0\}$ is a community by itself, $\{4\}$ is a community by itself, etc. One can think of $M$ as representation of a graph with $V$ nodes, and $E$ edges. $M$ is $VxV$ matrix and the entries with value $1$ correspond to edges of an undirected graph. For the above example, the total number of communities is $V-2$.

I need to explain the following:

If we solve the above problem with union and find operations (weighted quick union), it will take $O(E+Vlog(V))$ time, explain.

I wrote the code for this. I am also including weighted union and find algorithm code as well below for completeness (but it is a standard known algorithm I guess). With the way I implement it, it does not look like this algorithm takes O(E+Vlog(V)) time. I need to understand how can this be done in O(E+Vlog(V)) time.

It is said that find operation takes O(log(V)) time because the tree is almost balanced with weighted quick union algorithm.

This is my code:

The code for weighted quick union and find (given):

public class WeightedQuickUnion {

int[] parent;   // parent[i] = parent of i
int[] size;     // size[i] = number of sites in subtree rooted at i
int count;      // number of components

/**
 * Initializes an empty union–find data structure
 * Each site is initially in its own
 * component.
 * n is the number of sites
 */
public WeightedQuickUnion(int n) {
    count = n;
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
}

/**
 * Return the number of components.
 *
 */
public int count() {
    return count;
}

/**
 * return the component identifier for the component containing p.
 * p the integer representing the item
 */
public int find(int p) {
    validate(p);
    while (p != parent[p])
        p = parent[p];
    return p;
}

// validate that p is a valid index
private void validate(int p) {
    int n = parent.length;
    if (p < 0 || p >= n) {
        throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
    }
}

/**
 * return true if the the item p and item q are in the same component.
 */
public boolean connected(int p, int q) {
    return find(p) == find(q);
}

/**
 * Merge the component containing p with the
 * the component containing q.
 */
public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);

    if (rootP == rootQ) return;

    // make smaller root point to larger one
    if (size[rootP] < size[rootQ]) {
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    }
    else {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }
    count--;
}

You are using Adjacency matrix representation, instead just maintain a list of pairs of friend (i.e. edge list) and iterate it once.


Finding least number of line segments with length $L$ that cover $N$ points The problem is defined as:

  Given $N$ points on an infinite line, find the least number of line segments of length $L$ that cover all points (including endpoints) after changing one point.

That means that if I have the points $P = 1,10,15,28$ , $L = 10$ , 3 line segments are needed , changes will occur that the point $i$ will move to position $X$ , after each change , get the number of line segments needed.

Example:

$P = 1,5,11,21,25$ , $L = 6$
, Changes are

$$
1 , 29
$$

$$
2,36
$$

after change #1 : $P = 5,11,21,25,29$ , number of line segments needed is 3

after change #2 : $P = 11,21,25,29,36$ , number of line segments needed is 4

What would be the best approach to do this? , Given that number of points can be $50,000$ and the number of changes can be $50,000$.

Point indexes are just a way of naming them. What matters in the
algorithm is only their positions.

The first thing you need is the management of your points. You need a
structure that sorts them according to position when given the initial
list of positions (ascending or descending order, it does not
matter). This structure must allow you to remove a point, and add it
somewhere else at low cost to keep the list sorted when you operate a
change. You will find many such structures in any course on data
structures and algorithms.

Then you need a structure for representing segments that will group
your points into a collection of buckets of points covered by the same
segment. This collection of buckets is a covering. The construction of
an optimal covering is easy. You can show easily that, given any
covering, you can always replace the lefmost segment by a
segment that start rightward at the leftmost point, to get another
covering. From that you can show by induction that you can get an
optimal covering by placing a segment so that its leftmost end is on
the leftmost point, and then reapeat recursively starting at the
lefftmost point not yet covered.

A symetric proof shows that you can alternatively start from the
right. Actually, combining the two proofs, you can show that you can
always chose your next segment either rightward from the leftmost
point or leftward from the rightmost point, computing from both end towards the middle until the two computations "meet" somewhere in the middle (you can choose that "somewhere"). In all versions of the algorithm, the last segment added may cover points that are already covered (though it can be avoided for the unidirectionnal versions of the algorithm - it does not matter anyway).

We assume first you build your covering from the left only.

Each change is composed of two "half-changes", removal of the point from its former position followed by addition of the point in the sorting structure at its new position. After performing them, you have recompute your segments.
You try to limit the new computation to an incremental change to the previous one, and you must have kept your collection of buckets.
You start at the leftmost segment affected by the leftmost
"half-change" (either addition or removal), and you recompute segments until you find a segment
that is the same as for the previous covering (which ends a first incremental update), and you do some
accounting to know whether and how that changes the number of
segments. If the rightmost "half-change" has been passed in the
process, you are also done for that change. Else you do the same for that
second half-change, still recomputing from left to right as in the
first computation of a minimal covering of segments.

The algorithm could alternatively compute coverings from right to left. It is the same in reversal.

Starting from both
ends may make the algorithm a bit more complicated (you have to work out the changes for yourself), On the other hand
it may improve it somewhat as it can avoid having to recompute all
segments up to the right end in pathological cases of incremental recomputation: you are sure an incremental update will not exceed half the collection of points ( actually it is not exactly half, depending on how the "meeting point in the middle" is chosen). But I guess it is
a minor improvement. You might be even more subtle in choosing the
"middle place"  and in possibly changing it when you move your points,
 to account for
changes of the algorithm behavior according to point density. But this
is marginal and requires a bit of analysis.

Note: the above works for addition and removal of points, without necessarily keeping a constant number of points, provided it is allowed by the structures  that I left unspecified and up to your own choice. The fact that the number of points remains constant in the statement of your problem could be an indication that a specific method is expected that would make use of that fact.

P.S. What do you mean by best approach ?  What is the criterion.


What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory? I am a master computer science student, and I am interested in both geometry and complexity theory.
So I would like to know what is the relations between discrete geometry, computer graphics, and complexity theory ?

I know the answer partially but I would like to have a clear answer since I do like to work on these fields in the future.

Thank you in advance.

Have a look at this slide of David Eppstein in which he tries to draw connections between these subfields. In my opinion, a computational-geometric complexity result is likely to be confined to computational geometry itself without broadly affecting complexity theory in general.

Excerpt from the above slide: Some computational geometry problems have practical applications. Their theoretical hardness are all conjectured to be $NP$-hard but still have not been proven. Some have approximation schemes.


Explanation of a simple algorithm's Big O complexity I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation:

Loop2(n)
    for i := 0 to n
        j := 0
        s := 0
        while s <= i
            j := j + 1
            s := s + j

I can see that the outer loop (alone) is run $O(n)$ times, and that the inner loop is $O(\sqrt n)$. However, the part that confuses me is that the correct answer, according to the paper, is $O(n \cdot \sqrt n)$.

I though that, since the inner loop is dependent on $i$, that it would be run $\sqrt i$ times, for $i$ going from $0..n$. Meaning that in total, the loop would run roughly $n$ times, making the whole algorithm $O(n\cdot n)=O(n^2)$. I kinda drew the logic from an analysis of insertion sort, where $$\sum_{i=0}^{n} n-i = O(n^2)$$

I think I remember the above correctly. Can anyone fix my broken logic here?

The inner loop is $O(\sqrt{i})$, you are correct. Since $i\leq n$, then $\sqrt{i}\leq \sqrt{n}$, and we have
$n\times\sqrt{i}\leq n\times\sqrt{n}$. Hence the complexity is  $O(n\sqrt{n})$.


Designing a PDA that keeps track of the stack size Would it be possible/legal to design a PDA that can use the stack as a way to keep track of the number of inputs seen? (i.e the size of the stack would act as some sort of counter).

What I was thinking:

First transition would require you to push a "1" to the stack
All future transitions would require you to pop the top of the stack (let's call this $x$) and push $x+1$ onto it.

The language of the stack would be the set of all natural numbers excluding 0.

I'm having trouble understanding whether the "push $x+1$" move would work

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

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

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


Origin of a story about a computer in the 50's recommending offing Pensioners There's a story I've heard a few times in various computer science talks, usually offered as a cautionary tale, that goes something like this:

In the late 50s, the British gov't purchased an early computer, and tried to build a computer model of the gov'ts budget, including every variable and factor they could think of.  They then had it run an analysis to find the best ways to save money.  The surprising result was they should decrease spending on traffic lights and cross-walks.
This confused the researchers, since these items were a very small fraction of the total budget, much less then what the computer claimed could be saved by eliminating them.  Upon further examination, they found that the source of the savings wouldn't be due to the direct cost of traffic lights, but were due to the increase in pensioners being killed trying to cross the street, thus saving the gov't X millons of dollars.

Even if the story is apocraphyl (which I sort of assume is the case) does anyone know what the original source is?

The story is clearly made up.

There was no AI in the 1950's that could have come up with that.

There is no AI today and for many years that could come up with that.

Actually, an AI wouldn't come up with this idea at all. You would need a very well calibrated combination of AI and AS (Artificial Stupidity) to achieve this result.


Finite state automaton for the reverse of the language, and multiple starting states I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that?

Also, can a Finite State Automaton have more than one starting state?

FSAs come in several varieties. The most common ones are deterministic (DFA), nondeterministic (NFA), and nondeterministic with $\epsilon$-moves (also called NFAs; sometimes $\epsilon$-NFAs).

The definitions of all three are not completely standard – there are several variants in the literature (for example, some allow the transition function of a DFA to be partial). However, in most standard definitions, all FSAs have a single initial state; though it is perfectly possible to define NFAs and $\epsilon$-NFAs having several initial states.

The reason you have to add a new initial state when reversing an NFA is exactly the requirement that there be a unique initial state. If we remove this requirement, then there is no need to add a new initial state.


An efficient way of calculating ((p*q)) where p and q are prime Let $p$ and $q$ be prime numbers and $\phi$ Euler's totient function. Is there an efficient way of computing $\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, that is not simply based on factoring $p-1$ and $q-1$?
Obviously, if $p$ and $q$ do not equal two, $p-1$ and $q-1$ are even and consequently their prime factorization is entirely different from the prime factorization of $p$ and $q$. Therefore I assume that no such shortcut exists.
Do I overlook something?

No, not efficiently, not in general.  Suppose $p=2p'+1$ and $q=2q'+1$ where $p',q'$ are prime.  Then factoring $pq$ is believed to be hard.  (Indeed, these primes are known as safe primes, and factoring a product of two safe primes is believed to be hard.)  However we have
$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$
If you could compute $\varphi(\varphi(pq))$ from $pq$ efficiently for $p,q$ of this form, then you could factor $pq$ efficiently for $p,q$ of this form.  The reduction works as follows.  Consider the quadratic function $f$ given by
$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$
We can compute the coefficients of $f$, as
$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$
$$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$
so you can use the quadratic formula to solve for the roots of $f$ and recover $p',q'$. From this the factorization of $pq$ can be recovered.
So, no, you are not overlooking anything.  There is likely no efficient way to compute $\varphi(\varphi(pq))$ for arbitrary numbers $pq$ (unless factoring is easy).


Must a Turing machine tape be binary? I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7), ennary (base 9) or even decimal (base 10).
One programmer commented that Turing machines are always binary because the tape includes at least one stage to go to and at least one stage to go back to (or something of that sort; translating from Hebrew without knowing the professional terminology in English).
Must a Turing machine tape be binary? --- Can't it be unary in any situation?
Was there an attempt to create a "similar" model which is unary just for the sake of research (putting efficiency aside)?

If there is just one symbol which can appear on the tape, then nothing about the tape can ever change. Thus, the tape is absolutely useless, and you are left with a finite bidirectional automaton.
However, the blank symbol $\bot$ is often treated as a special case. We could thus consider the situation where each cell on the tape can carry either $0$ or $\bot$, and where we can write a $0$ on a place previously containing a $\bot$, but we can never erase a $0$ and return that cell content to $\bot$. This is as close to unary as we can really get for a TM.
As long as we only consider decision problems, these machines still have the full power. Essentially, the idea is to insert a bunch of auxiliary bits between the bits containing the actual content, and then so simply copy everything to a fresh chunk of tape whenever we need to erase a bit, except for the bit to be erased.
Having a finite number of tape symbols greater than 1 doesn't make much a difference. So binary is just special here because its the smallest alphabet that easily works.


Smallest cost in weighted directed graph with combinations I am trying to develop an algorithm that can traverse a graph with intermediary/all or nothing(?) nodes.

The problem is that there are companies B, C and D that are bidding on projects X, Y and Z.  The companies can do individual bids for any of the projects, or they can say that they will complete a combination of projects for a total of x dollars.  However this combination is all or nothing and cannot be split.  I need to find the path with the least cost for all of X, Y and Z from the initial A (manager) node, that takes into account the combination of costs.

The following graph illustrates the problem that I am trying to solve:

A typical graph traversal algorithm would say that for A -> X the path A -> B -> X with cost 5, for A -> Y the path A -> C -> Y with cost 4 and for the path A -> Z the path A -> C -> Z with cost 6 should be taken.  Making the cumulative total be 15.

However, introducing the idea of an intermediary/combination node, would say that for A -> X the path that should be taken would be A -> B -> X with cost 5.  Then for A -> Y and A -> Z it should share the cost and take A -> D -> DL -> Y combined with A -> D -> DL -> Z with the lump sum of 8.  This would result in the lesser cost of 13.

Some general notes are that this is a very small example of the overall problem that I am trying to solve. At any given time there can be many companies and many projects (100+), and additionally, there can be may bids/edges between the companies and projects and there can be many combinations/lump sum bids.

The could explain the problem best using a graph but it doesn't necessarily mean that it is the best solution. It almost seems to me to be graphing up front, but then introducing the combination nodes makes it seem like a derivative of the knapsack problem. I appreciate any help or direction.

edit Typically there will be 20 companies and anywhere from 20-100 categories.  Typically the number of bids will be (companies) * (categories) where 20% of the bids are combinations.  So if there are 2000 bids approximately 400 could be a combination bid.  The number of projects in a combination could make up only min + 1 or all of the categories.

You can formulate problems like this as an integer program and apply off-the-shelf tools to find (near) optimal solutions.

The example is rendered something like this (the exact syntax depends on the tool).

minimize 5*BX + 10*BZ + 4*CY + 6*CZ + 10*DX + 7*DYZ
subject to
BX + DX = 1  # project X is done once
CY + DYZ = 1  # project Y is done once
BZ + CZ + DYZ = 1  # project Z is done once
binary variables BX, BZ, CY, CZ, DX, DYZ in {0, 1}

The interpretation of, e.g., DYZ is that D is awarded the package of contracts for Y and Z if and only if DYZ has value 1.


Is the problem of determining whether a CFG generates a string in the form 0*1* decidable? Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why?

I think it's undecidable but can't find any undecidable problem to reduce it to.

Yes it is decidable.
We can construct a total Turing machine M that on input $G$ (where G is a CFG) checks whether it generates at least one string in $0^*1^*$.
Let $G_1$ be a regular language such that $L(G_1)=0^*1^*$.
Note that the intersection of CFL and a regular language is indeed a CFL. And hence a CFG for the intersection of $G$ and $G_1$ can be constructed. Call the constructed CFG $G'$. Also, the emptiness problem for CFG is decidable and hence just check the emptiness of the constructed CFG $G'$.
If it's empty, G doesn't generate any string in $0^*1^*$; and likewise if it's  not empty.


regex of three repeating number I need a regular expression, not one using coding syntax, to write an expression that has a vocabulary of 1,2,3 and every string in the language has at most one occurrence of the substring 222 but never has the occurrence of 123.

((1 or 3)*(211 or 231 or 233 or 2211 or 2231 or 2233))* 222

is as far as I could get, I can't see how to prevent 123 from happening while still allowing a string like 1223221222 to occur. Any thoughts?

First, "has no occurence of 123".

So the string can start with any number of 2s and 3s.
Then it has 0, 1 or more components that start with 1, and followed by any number of 2s and 3s other than 23. So the 1 is followed by nothing, a single 2, 22 and any number of 2s and 3s, or 3 and any number of 2s and 3s.

Each of these components could contain three or four consecutive 2s. Four consecutive 2s are not allowed, three consecutive 2s may only happen once. So for each of those components add things to not allow three 2s in a row, or to allow three but not four 2s in a row. And then the language is any number of components with no three 2s, optionally followed by a component with three 2s and any number of components with no three 2s.

It's a bit complicated, but not too bad.

So make regular expressions for "lead_2" = "any number of 2s and 3s, but no three 2s in a row", "lead_3" = "any number of 2s and 3s, with 222 once but not twice, and no 2222", "follow_2" = "1, followed by lead_2 not starting with 23", "follow_3" = "1, followed by lead_3 not starting with 23", and the whole language is

lead_2 (follow_2)* or
lead_2 (follow_2)* follow_3 (follow_2)* or
lead_3 (follow_2)*


How to read Nasa Convolutional code? Here is a picture from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 207(English Version)/Page 206(Japanese Version):

I want to verify whether my interpretation is correct or not. My interpretation is in the picture that has red arrows.

From the picture, I made a table to understand easily the internal condition of Nasa Convolutional code.

So from my interpretation, I got

Out1:Input+S2+S3+S5+S6 .. formula(1)
Out2:Input+S1+S2+S3+S6.. formula(2)

From the excerpt Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

We know that when internal state is 100000, the output will be 11.However, when I use formula(1) and formula(2), I didn't get 11 but instead I got 10.

Out1:Input+S2+S3+S5+S6=1+0+0+0+0=1
Out2:Input+S1+S2+S3+S6=1+1+0+0+0=0

My question is, is my interpretation is correct? If it's correct, why don't I get the output 11? If it's wrong, where did I get it wrong? Please teach and correct me.

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

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

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

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


Why are blocking artifacts serious when there is fast motion in MPEG? Why are blocking artifacts serious when there is fast motion in MPEG?

Here is the guess I made:

In MPEG, each block in an encoding frame is matched with a block in the reference frame.
If the difference of two blocks is small, only the difference is encoded using DCT. Is the reason blocking artifacts are serious that the difference of two blocks is too large and DCT cut the AC component?

DCT is both discrete and finite, it has a limited range in both the space and frequency domains. If the change in a certain location is large or the location changes a lot, the results of the transform will be beyond the sampling range in the frequency domain.

Since as you mentioned MPEG is based on blocks, the result of a block with with missing high frequencies, after transform back to the spacial domain, will result in the loss of detail in that block - making the block look flat.

For a more accurate result try Signal Processing Stack Exchange.


What is a sort in programming language semantics? In Chapter 1 of Practical Foundations for Programming Languages, the author mentions that abstract syntax trees are associated with sorts.

Intuitively, sorts are like types, but I'd like to know if they have a precise definition. I'd be glad if some references are provided as well.

It depends on what semantics we would take for types and sorts. -- However a brief - little informal - definitions could be - Sorts are classes of ASTs and types are classes of values.


Can you complete a basis in polynomial time? Here is the problem: we are given vectors $v_1, \ldots, v_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v_i$ are rational, with numerator and denominator taking $K$ bits to describe. We would like to find vectors $v_{k+1}, \ldots, v_n$ such that $v_1, \ldots, v_n$ is an orthogonal basis for $\mathbb{R}^n$.

I would like to say this can be done in polynomial time in $n$ and $K$. However, I'm not sure this is the case. My question is to provide a proof that this can indeed be done in polynomial time.

Here is where I am stuck.  Gram-Schmidt suggests to use the following iterative process. Suppose we currently have the collection $v_1, \ldots, v_l$. Take the basis vectors $e_1, \ldots, e_n$, go through them through them one by one, and if some $e_i$ is not in the span of the $v_1, \ldots, v_l$, then set $v_{l+1} = P_{{\rm span}(v_1, \ldots, v_l)^\perp} e_i$ (here $P$ is the projection operator). Repeat.

This works in the sense that the number of additions and multiplications is polynomial in $n$. But what happens to the bit-sizes of the entries? The issue is that the projection of $e_i$ onto, say, $v_1$ may have denominators which need $2K$ bits or more to describe - because $P_{v_1}(e_i)$ is $v_1$ times its $i$'th entry, divided by $||v_1||$. Just $v_1$ times its $i$'th entry may already need $2K$ bits to describe.

By a similar argument, it seems that each time I do this, the number of bits doubles. By the end, I may need $2^{\Omega(n)}$ bits to describe the entries of the vector. How do I prove this does not happen? Or perhaps should I be doing things differently to avoid this?

The result of the Gram-Schmidt can be expressed in determinantal form, see Wikipedia. This shows that the output of the Gram-Schmidt process is polynomial size. This suggests that if you run the classical Gram-Schmidt process, then all intermediate entries are also polynomial size (even in LLL, all intermediate entries are polynomial size). However, even if it is not the case, then using efficient algorithms for computing the determinant (see my other answer), you can compute the Gram-Schmidt orthogonalization in polynomial time.


Textbook on formal syntax (and semantics) of programming languages I'd like to learn about formal syntax of programming languages: how do we describe the syntax of a programming language and how it should be parsed? How do we assign formal semantics to a parsed program?
I've looked at textbooks like this one, but it is very practical. I am looking for something more theoretical: an introduction to specifying programming languages fully formally and assigning a fully formal semantics. Is there such a book?

Maybe you will like to book Concrete Semantics (which is freely available as a PDF). It defines the syntax and semantics of an imperative programming language using the proof assistant Isabelle/HOL. In later chapters also types are added to the language and several examples of program analysis are shown.


Master theorem with $T(n) = 6T(n/10) + \lg^2 n$ So I think this falls under case 1...but I am not sure how to formally prove that $n^{lg_{10} 6}$ is asymptotically greater than $\lg^2 n$. I tried using L'hopitals but kinda reached a dead end. Here's what i have so far

$$\lim_{n \rightarrow \infty} \frac{d(\lg^2 n)}{d(n^{\lg_{10}6})} = \frac{2 \lg n (\frac{1}{n})}{(\lg_{10}6) n ^{(\lg_{10}6) - 1}}$$

Is there some better way I can think about proving case 1?

Yuval Filmus pretty much showed the way in the comment above. I will just elaborate on his approach.

First, we raise both to the power lg610.

(nlg106)lg610 = n(lg106 x lg610) = n

and,

(lg2n)lg610 = (lg n)2 x lg610 = (lg n)2.57

Now, taking log of both of these, we get
lg(n) and 2.57xlg(lg(n)) respectively.

lg(n) is asymptotically greater than lg(lg(n)), and thus, our case is proved.


Is finding a set cover of size $k$ NP-complete? I know that set cover problem is NP-complete. We are given a universe  $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe and an integer $k$. The set cover problem is to identify a sub-collection of $S$ of size $k$ or less whose union equals the universe?

Now if I remove or less, and ask instead that is there a sub-collection of $S$ of size $k$ whose union equals the universe? Is this still NP-complete?

Here, of course, $k<m$.

My answer is that the problem is still NP-complete. From the initial problem we simply keep the same instance and we find a set cover of size $s\leqslant k$  then the modified problem has a set cover of size $k$ if $s=k$.

Any help?

Yes, it remains NP-complete, even under the restriction that all subsets of a specific size $s$ (which translates to immediately requiring that $k = n / s$.

For example, for $k = n / 3$, 3-dimensional matching can be directly reduced to your problem.


Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak In Computational Complexity -- A Modern Approach, by Arora and Barak, they have the following claim (Example 3.6).

Let EXPCOM be the following language
$$ \{ \langle M, x, 1^n\rangle \mid M \text{ outputs 1 on $x$ within $2^n$ steps} \}  $$
Then $\mathbf{P}^{\mathrm{EXPCOM}} = \dots = \mathbf{EXP}$. [...]
Clearly, an oracle to EXPCOM allows one to perform an exponential-time computation at the cost of one call, and so $\mathbf{EXP} \subseteq \mathbf{P}^{\mathrm{EXPCOM}}$. [...]

I believe their reasoning is as follows:

Suppose we have a language $L \in \mathbf{EXP}$.

Thus there is a TM $M$ that decides it in time $2^{n^c}$.

We want to create a poly-time oracle-TM $T^{\mathrm{EXPCOM}}$ that decides $L$.

$T$ works as follows on input a string $x \in \{ 0, 1 \}^{*}$. It queries its EXPCOM oracle on input $\langle M, x, 1^{n^c} \rangle $, and outputs the same answer as the oracle.

Clearly $T$ runs in polynomial time, and it decides the same language as $M$. QED.

Here is my confusion. For $T$ to call its EXPCOM oracle, it needs to know which $M$ that decides $L$ (in exponential time). However, 2. only promises the existence of a machine $M$; it doesn't actually tell you how to find it!
(this problem also applies to the running time $2^{n^c}$ of $M$).
So clearly I'm misunderstanding something, but what? Is it my understanding of the language EXPCOM? Is it my description of $T$? Or have I misunderstood oracle-TMs altogether? (Or maybe all three?)

You are correct that $T$ needs to know which Turing machine accepts $L$. This Turing machine is $M$, and you can hardcode it into $T$. There is absolutely no problem with that.

Here is a similar example. Suppose that there is a proof that $P \neq NP$. Then there is a Turing machine that prints a proof of $P \neq NP$.

Proof: According to the assumption, there is a proof $\pi$ that $P \neq NP$. Construct a Turing machine $T$ that prints $\pi$. Then $T$ prints a proof of $P \neq NP$. $\quad\square$

What seems to worry you is that you think of $T$ as accepting $L$ as an input, from which it is supposed to come up with the Turing machine $T$. But this is not the case – all we have to do is to show that for each $L$ there exists an appropriate Turing machine $T$. Moreover, it is not clear how $T$ would accept $L$ as input – a language is, in general, an infinite object.

Sometimes we do need to be worried about the issue that you raised. Here is an example. Let $L_1,L_2,\dots$ be an infinite sequence of decidable languages. For each $L_i$, there is a Turing machine $T_i$ that decides $L_i$. But is there a Turing machine $T$ that accepts an index $i$ and a word $w$ and returns whether $w \in L_i$? Not necessarily (I'll let you come up with a counterexample). When such a machine $T$ does exist, we say that $L_1,L_2,\dots$ are uniformly decidable.

No such uniformity condition appears in your question. We could impose such a condition artificially by providing $L$ as an input via a Turing machine, not necessarily running in exponential time, that accepts $L$. In this case, your criticism would be valid – given a Turing machine that accepts a language in $\mathsf{EXP}$, it is not clear how to find a Turing machine accepting the same language and running in exponential time.


Is oracle computer capable of doing infinite loops? Solve this problem: "build an infinite binary oscilator"

With a Turing Machine we can solve it

a=False
While True:
   a=not a
   print a,

then output will be

True False True False True False ...

(for ever)

I think an oracle can't do it, because its definition, it could solve in "one operation", but here there's not halting as a request of the problem statement. Is it true?

EDIT:  Oracle definition from wikipedia

".. an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used."

So what if that TM ask its black box oracle to create an infinite binary oscilation?

   1- oracle black box can't do infinite loops
   2-TM can't ask that problem to oracle
   3- Does it return a string with a source code as answer? weird
   4-or other options...

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

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


Is there an algorithim to construct a graph with an even number of vertices, and each vertex has k edges? Ideally, such an algorithm would not be a brute force one. Is there a clever way to do this?

The complete bipartite graph $K_{k,k}$ has $2k$ vertices, each of which has degree $k$.