Given n numbers How to find out a set of numbers whose sum equal to a certain given number I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s.

for example - the given set is [2,8,3] and given integer 9
Then I can tell {3,3,3} or {3,2,2,2} can be the required sets.

Unfortunately I cannot figure out the best approach (with best time complexity)..
As I tried to do it using nested loops which naturally results into huge time complexity.

Any help is appreciated.

One possible solution is based on knapsack.

Consider the list elements $a_1$, $a_2$, $\ldots$, $a_n$ in any fixed order.
Calculate the following boolean function: $f (k, t)$ is true if it is possible to have the sum of exactly $t$ from some subset of $a_1$, $a_2$, $\ldots$, $a_k$, and false otherwise.
Here, $k$ spans from $0$ to $n$, inclusive, and $t$ goes from $0$ to $s$: we don't need larger sums.

The calculation can be performed in $O (n \cdot s)$ using dynamic programming.
Just observe that $f (k, t) = f (k - 1, t)\mathrm{~or~} f (k, t - a_k)$: for the element $a_k$ and for every possible target sum $t$, we either drop the element from consideration, or take it into our sum.
In the latter case, we must have the chance to take it again, hence the transition to $(k, t - a_k)$ instead of $(k - 1, t - a_k)$.

Now, knowing which $(k, t)$ pairs are possible and which are not, we can recursively construct all possible answers in $O((n + s) \cdot R)$, where $R$ is the number of answers.
Indeed, descend from $(n, s)$ down to $(0, 0)$.
When we are at $(k, t)$, we can see whether $(k - 1, t)$ and $(k, t - a_k)$ are possible, and descend only into the possible branches.
As every descent takes at most $n + s$ steps, finding $R$ possible answers will happen in $(n + s) \cdot R$ time.
Actually, it will be faster since some descent paths share a common start, and some $a_k$ are greater than $1$.


Can neural network process randomness? So the question is : Is it theoretically possible to feed a neural network with some random values to expect an output since randomness is a lack of knowledge in most case.

For this question, I've got some examples.

First case, not a real problem?

We just throw a coin and get the result and we do that a whole bunch of times. For each throw, we get the initial condition (air pressure, force, etc.). Now we put all this data into the neural network for it to process.

My guess : The result is not really random since it only depends on the initial conditions so it's possible and the neural network will do a great job. So I guess that example is not a real problem since the "randomness degree" is weak.

Second case, questioning

Now, we generate a random list of number and sentences that correspond to each other so we have something like :

'zefvkbdl' -> 1613841.009
'nfeovhlzm' -> 963478.29
'jhgcjbklnsczl' -> 1.535953
'ergz' -> 9138630.26
etc ...

In a way that everything was randomdly generated (still, the list of sentences and number were not generated seperatly but each number was generated after a sentence and correspond to that sentence). In that case, is it possible to give a neural network the half of the list (the list can be forever long) and expect it to predict the other half with a great precision ?

My guess : It depends on the generation algorithm but let's pretend that a letter is just a particular index in an array and that the index was randomly generated. Since most of the time, numbers are randomly generated thanks to the digits of time (the last decimals that are changing extremely fast) I'm not sure of that - I guess it might be possible with an extremly powerful neural network to theoretically do that job.

Third case

Let's now be even more theoretical and consider it is possible to store somehow the global state of the universe at each moment of time. The only thing that is truly random at my knowledge is quantum mechanics so let's try it out.
At each point of time, we store the whole universe state and the outcome of measuring a quantum particle state (like the spin of an electron). Is it possible, after the biggest neural network training, to "predict" the outcome of measuring a quantum particle state knowing the state of the universe ?

Since I'm just a curious student, I don't have a lot of knowledge in neural network or quantum mechanics so I probably said a lot of wrong things and I'm sorry for that. I thank you for reading all of this and I hope someone is able to help me anwser or correct me.

Now, the real question I'm asking is : Do randomness truly exist ?

Purely randomness is not possible but in real-world the most randomness that a neural network can process is enough to discover an approximation pattern; the precision depends on the model of the context (exactitude of the Digital Twins) and processing power.

To extract the exact pattern from the pure randomness (I think) is impossible even with a quantum computer and even having all the time and resources of the universe. The reason is that nothing in the universe happens randomly, every effect has a cause. So regarding to the third case (theoretically) if you can reproduce every cause of a "twin universe" you can predict the future.


Are Cellular Automata always computers? I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer.
In the introduction part:

Cellular automata can be viewed as either computers or logical universes where computers may be embbed.

What i am trying to understand is, is it always a given Cellular Automaton  is a computer ?
like Elementary Cellular Automata {ECA} rule 110 and rule 90, i know that rule 110 is universal which makes it a computer but what about rule 90 ... what about other ECA rules are they also computers ?

Suppose we have a cellular automaton (x), how do we know that it is a logical universe (as stated by the author), how can we know if it is a logical universe where computers can be embedd in or not and how can we know if it is just a computer ?

I know that logical universes are Cellular Automata, but what dimensions these universes should be to implement a computer easily, 1D like ECA or 2D like Conway's Game of Life ?

"... is it always a given Cellular Automaton is a computer?"...

I interpret "is a computer" as "being capable of universal computation" or in other words "being capable of simulating an arbitrary Turing machine".

The answer is clearly NO; a trivial example is a CA that doesn't modify the input:

0[0]0 -> 0
0[0]1 -> 0
0[1]0 -> 1
0[1]1 -> 1
1[0]0 -> 0
1[0]1 -> 0
1[1]0 -> 1
1[1]1 -> 1

(rule 204)

According to Wolfram's (qualitative) classification, only type-4 CAs exhibit a behaviour that can potentially be "universal". But it is an informal statement (like many others in Wolfram's NKS) ... in order to say that a particular CA is/is not Universal you must prove it formally.

For a more rigorous introduction to the argument I suggest you to read some research articles on the subject, for example: Kristian Lindgren, Mats G. Nordhal. Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems 4 (1990) 299-318

Or - for a good, more general, introduction to computational universality - read Chapter 7: The Grand Unified Theory of Computation of the (IMO excellent) book:  Cristopher Moore, Stephan Mertens. The Nature Of Computation (2011)


Is there a sometimes-efficient algorithm to solve #SAT? Let $B$ be a boolean formula consisting of the usual AND, OR, and NOT operators and some variables.  I would like to count the number of satisfying assignments for $B$. That is, I want to find the number of different assignments of truth values to the variables of $B$ for which $B$ assumes a true value. For example, the formula $a\lor b$ has three satisfying assignments; $(a\lor b)\land(c\lor\lnot b)$ has four. This is the #SAT problem.

Obviously an efficient solution to this problem would imply an efficient solution to SAT, which is unlikely, and in fact this problem is #P-complete, and so may well be strictly harder than SAT. So I am not expecting a guaranteed-efficient solution.

But it is well-known that there are relatively few really difficult instances of SAT itself. (See for example Cheeseman 1991, "Where the really hard problems are".) Ordinary pruned search, although exponential in the worst case, can solve many instances efficiently; resolution methods, although exponential in the worst case, are even more efficient in practice.

My question is:

  Are any algorithms known which can quickly count the number of satisfying assignments of a typical boolean formula, even if such algorithms require exponential time in the general instance? Is there anything noticeably better than enumerating every possible assignment?

Counting in the general case

The problem you are interested in is known as #SAT, or model counting. In a sense, it is the classical #P-complete problem. Model counting is hard, even for $2$-SAT! Not surprisingly, the exact methods can only handle instances with around hundreds of variables. Approximate methods exist too, and they might be able to handle instances with around 1000 variables.

Exact counting methods are often based on DPLL-style exhaustive search or some sort of knowledge compilation. The approximate methods are usually categorized as methods that give fast estimates without any guarantees and methods that provide lower or upper bounds with a correctness guarantee. There are also other methods that might not fit the categories, such as discovering backdoors, or methods that insist on certain structural properties to hold on the formulas (or their constraint graph).

There are practical implementations out there. Some exact model counters are CDP, Relsat, Cachet, sharpSAT, and c2d. The sort of main techniques used by the exact solvers are partial counts, component analysis (of the underying constraint graph), formula and component caching, and smart reasoning at each node. Another method based on knowledge compilation converts the input CNF formula into another logical form. From this form, the model count can be deduced easily (polynomial time in the size of the newly produced formula). For example, one might convert the formula to a binary decision diagram (BDD). One could then traverse the BDD from the "1" leaf back to the root. Or for another example, the c2d employs a compiler that turns CNF formulas into deterministic decomposable negation normal form (d-DNNF).

If your instances get larger or you don't care about being exact, approximate methods exist too. With approximate methods, we care about and consider the quality of the estimate and the correctness confidence associated with the estimate reported by our algorithm. One approach by Wei and Selman [2] uses MCMC sampling to compute an approximation of the true model count for the input formula. The method is based on the fact that if one can sample (near-)uniformly from the set of solution of a formula $\phi$, then one can compute a good estimate of the number of solutions of $\phi$.

Gogate and Dechter [3] use a model counting technique known as SampleMinisat. It's based on sampling from the backtrack-free search space of a boolean formula. The technique builds on the idea of importance re-sampling, using DPLL-based SAT solvers to construct the backtrack-free search space. This might be done either completely or up to an approximation. Sampling for estimates with guarantees is also possible. Building on [2], Gomes et al. [4] showed that using sampling with a modified randomized strategy, one can get provable lower bounds on the total model count with high probabilistic correctness guarantees.

There is also work that builds on belief propagation (BP). See Kroc et al. [5] and the BPCount they introduce. In the same paper, the authors give a second method called MiniCount, for providing upper bounds on the model count. There's also a statistical framework which allows one to compute upper bounds under certain statistical assumptions.

Algorithms for #2-SAT and #3-SAT

If you restrict your attention to #2-SAT or #3-SAT, there are algorithms that run in $O(1.3247^n)$ and $O(1.6894^n)$ for these problems respectively [1]. There are slight improvements for these algorithms. For example, Kutzkov [6] improved upon the upper bound of [1] for #3-SAT with an algorithm running in time $O(1.6423^n)$.

As is in the nature of the problem, if you want to solve instances in practice, a lot depends on the size and structure of your instances. The more you know, the more capable you are in choosing the right method.

[1] Vilhelm Dahllöf, Peter Jonsson, and Magnus Wahlström. Counting Satisfying Assignments in 2-SAT and 3-SAT. In Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON-2002), 535-543, 2002.

[2] W. Wei, and B. Selman. A New Approach to Model Counting. In Proceedings of SAT05: 8th International Conference on Theory and Applications of Satisfiability Testing, volume 3569 of Lecture Notes in Computer Science, 324-339, 2005.

[3] R. Gogate, and R. Dechter. Approximate Counting by Sampling the Backtrack-free Search Space. In Proceedings of AAAI-07: 22nd National Conference on Artificial Intelligence, 198–203, Vancouver, 2007.

[4] C. P. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman. From Sampling to Model Counting. In Proceedings of IJCAI-07: 20th International Joint Conference on Artificial Intelligence, 2293–2299, 2007.

[5] L. Kroc, A. Sabharwal, and B. Selman. Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting. In CPAIOR-08: 5th International Conference on Integration of AI and OR Techniques in Constraint Programming, volume 5015 of Lecture Notes in Computer Science, 127–141, 2008.

[6] K. Kutzkov. New upper bound for the #3-SAT problem. Information Processing Letters 105(1), 1-5, 2007.


About having analytic control over any algorithm which finds perfect matchings. A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this :  direct all the edges from left to right and put capacity one on each of them - then add a super-source and a super sink with appropriately directed edges from them to each of the vertices on their side with capacity one - now run max-flow on it and that picks out a perfect matching - now remove this perfect matching and repeat - continue doing this till you have exhausted all the original edges - this clearly gives you the needed decomposition of the original graph into disjoint perfect matchings.

So one can think of this algorithm as basically returning you a set of d disjoint permutations on the set of n elements.

Can one say what permutations will be returned? (Will it always return the same set of permutations in the same sequence?)
Its possible that the answer to the above question is implementation dependent and in that case is there some "standard" implementation for which one can analytically write down the permutations that would be returned as a function of the input graph?
Or is there any other way to solve this question where one analytically knows the permutations that will be generated?

Will it always return the same set of permutations in the same sequence?

No.  If you call the algorithm twice with the same input, it's not necessarily guaranteed to give the same output both times.  Many standard max-flow algorithms are non-deterministic, so there is no such guarantee.  For instance, consider any algorithm based on selecting augmenting paths.  If at any iteration there are multiple augmenting paths that would be acceptable, the max-flow algorithm will typically select one of them arbitrarily.  Consequently, it is not deterministic.

However, any such algorithm can easily be made to be deterministic by simply specifying a deterministic rule for resolving all non-deterministic choices.  For instance, whenever there are multiple acceptable choices, you can sort all of the acceptable options using some pre-specified order (say, lexicographic order) and always take the first.


What is the average turnaround time? For the following jobs:

The average wait time would be using a FCFS algorithm:

(6-6)+(7-2)+(11-5)+(17-5)+(14-1) -> 0+5+6+10+13 -> 34/5 = 7 (6.8)

What would the average turnaround time be?

You need to determine at what time each job is completed. With a first-come-first-served scheduler, this is simple to calculate: each job starts as soon as the processor becomes free, and takes exactly its burst time to complete. You've already calculated the start and end times to calculate the wait times, so use that to obtain the turnaround time.

For example, A arrives at time 0. The processor is free, so it starts at time 0 and ends at time 6. Then the processor runs B, which had to wait for 5 units, and finishes at time 8, for a turnaround time of 7.

The answer from the book seems to be totaling the completion times, without regard for the arrival time. This is not something I recognize as “turnaround time”.


$g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$ imply $2 f ( n ) ∈ o ( 2 g ( n ) )$ Prove that if $g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$, then $2 f ( n ) ∈ o ( 2 g ( n ) )$.

I was going over this question in my Algorithms class and could'nt understand why first condition has to be met. How would $g ( n ) ∈ ω ( 1 )$ affect our reasoning? Also, what would happen if instead of $g ( n ) ∈ ω ( 1 )$, it was $g ( n ) ∈ o ( 1 )$?

Considering non negative case we have
$$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$
From this definition for $\forall C>0,$ we have:
$$ C \cdot O(f)= O(C \cdot f) = O(f)$$
It can be written also as:
$$C \cdot g \in O(f) \Leftrightarrow g \in O(C \cdot f) \Leftrightarrow g \in O(f)$$
without any additional condition.


What is memcomputing? In recent article of PM the memcomputing is presented. But I did not understand how it works, according to the text.

What is the general principle of work for this memcomputing? How it is done in hard-ware?

It doesn't work. I am paraphrasing Scott Aaronson in this answer, whose article on the subject gives more details.

They claim to have some way of solving the subsetsum problem efficiently. The basic gist being that they encode all of the numbers in the instance as electrical signals, and then throw all the electrical signals together in to a big melting pot. They then measure the output signal and try to find whether it contains a signal corresponding to a solution.

However, this requires an exponentially precise signal (to be able to figure out whether the particular frequency/signal you want is there) so it isn't really a viable approach to solving $NP$-complete problems. The article claims that this is likely to be resolved in the future and that the general principle of memcomputing might one day become viable but I think that claim should be taken with a grain of salt. It seems that whatever trade-off you make, be it time, energy, memory or precision, you always end up hitting some barrier that requires exponential resources.


Minimal Deterministic Buchi Automata Product Problem:

Let $\varphi = \varphi_1 \land \varphi_2$ be Deterministic Buchi Automata (DBA) expressible LTL formulas.

Let $A$, $A_1$ and $A_2$ be translated DBAs such that ${\cal{L}}(A) = {\cal{L}}(A_1) \cap {\cal{L}}(A_2)$.

What can be said about the relation between the number of states in $A$ and that in the synchronous product $A_1 \otimes A_2$?

Some background:

I found two definitions of the Buchi product, the one given by Vardi in An Automata-Theoretic Approach to Linear Temporal Logic that uses $S = S_1 \times S_2 \times \{1, 2\}$ while the one demonstrated in this presentation uses $S = S_1 \times S_2 \times \{1, 2, 3\}$.

Also, Ehlers has proposed an approach to minimize the DBA in this paper.

However, I have been unsuccessful in finding any rigorous mathematical relation between the sizes of translated DBA $A$ and the minimal synchronous product of $A_1 \otimes A_2$.

My question:

I would like to know about

Any work regarding the size of Minimal DBA Product
Any work about the relation between the number of states.
How to construct the minimal DBA Product, given $A_1$ and $A_2$.

This is only a partial answer (as I believe that the state of the art is insufficient to answer your questions completely - I am happy to be proven wrong here), but I hope that it helps you anyway.

First of all, note that when taking the conjunction of two automata with $n$ and $m$ states, the result having $nm - o(n) - o(m)$ states cannot be avoided. This follows pretty much from the fact that for deterministic automata over finite words, such a blow-up can also not be avoided. At the same time, we have an upper bound on $2nm$ many states for the product. For automata theory researchers, this is actually pretty tight.
The constructions given in the Vardi paper and the one given in the slide set you referred to are slightly different. Both have counters for keeping track of for which automaton an accepting state has to be visited next. In the slide set construction, after both automata have seen accepting states, goes to the counter value of 3, where in the product an accepting state is visited and then switches back to 1. Vardi (who attributes the construction to earlier work by another researcher) does it differently. In a nutshell, the idea is to recycle the accepting states from the factor automata, and to switch the counter only after an accepting state has just been seen. In this way, the "3" counter value is not neccessary, and the construction still works anyway.
As far as I know, there is no research that answers your questions completely. But you may be interested in Schewe's paper that shows that minimizing deterministic Buchi automata is NP-hard (The ArXiV version of the paper can be found here). I would not be surprised if you could base a proof that your problem 3 is NP-hard on his proof ideas. For the case that the factor automata are not already minimal, this proof would be trivial, but I assume that you want to start with minimally-sized automata.


$(max,+)$ matrix product with limited number of values I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). This is the matrix product defined as: $(A\cdot B)_{ij}:=\max^n_{k=1}\{A_{ik}+B_{kj}\}$, for some $n\times n$ matrices $A$ and $B$. This lower bound means that the trivial algorithm is the best one.

Is there a better algorithm if we restrict the values to be in a finite set? For example, all the matrix entries are $0$ or $1$. Note that this is different from Boolean matrix product.

Any reference is welcome.

The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. The APSP problem uses a $(\min,+)$-matrix product. Since $\max_{A} \sum_{a\in A} a = -\min_{A} -\sum_{a\in A}a = -\min_A \sum_{a\in A}-a$, we can express a $(\max,+)$-matrix product as a $(\min,+)$-matrix product and vice versa, as the paper allows edge-weights to be either positive or negative.

So this gives a subcubic algorithm for $(\max,+)$-multiplication when the values are bounded.


Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$ For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$  and outputs $n'th$ perfect number.

How to solve this problem for large $n$ , for example $n$ close to $10^{18}$ ? we can't use brute force method since input can be so large .Can we solve it using DP or binary search ?

Source of the problem : Perfect Number

Note: In given problem statement (in link) $n$ is not large and thus can be solved using brute force.But i am curious to solve it for large $n$.

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

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

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


Solving a complicated recurrence relation How to solve the recurrence relation below?

$$T(n) = \begin{cases}
             2T(\sqrt{n}) + \log n/\log\log n & \text{if } n > 4\\
             1 & \text{if } n \leq 4.
          \end{cases}$$

Preferably by the master theorem; otherwise by any method. I know the Master Theorem fails, but is there any extension for these type of problems?

Following Timot's suggestion, let $S(m) = T(2^m)$, so that $S$ satisfies the recurrence
$$ S(m) = \begin{cases} 2S(m/2) + \tfrac{m}{\log m} & \text{ if } m > 2 \\ 1 & \text{ otherwise.} \end{cases} $$
In fact, we'll analyze the recurrence with a base case of $m = 1$ instead, and assume the logarithm is base $2$. We have
$$
\begin{align*}
S(2^k) &= \frac{2^k}{k} + 2 \frac{2^{k-1}}{k-1} + 4 \frac{2^{k-2}}{k-2} + \cdots + 2^{k-1} \frac{2^1}{1} + 2^k \\ &=
2^k \left[ \frac{1}{k} + \frac{1}{k-1} + \cdots + \frac{1}{1} + 1 \right] = \Theta(2^k\log k).
\end{align*}
$$
Therefore $S(m) = \Theta(m\log\log m)$ and $T(n) = \Theta(\log n\log\log\log n)$.


Right definition of linear grammar I was referring book by Peter Linz, which defines linear grammar as follows:

  A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable.

The wikipedia page also defines it similar way at the top of Linear grammar page

  a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.

By these definition, it seems that the production of the following form is allowed:

  $S\rightarrow aSb$

But next on the same page, wikipedia defines it as follows:

  linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

By this definition, it seems that the productions of the above form are not allowed.

Then what is correct definition?

They second quote from Wikipedia has lost its context. Here it is complete, with emphasis added:

Another special type of linear grammar is the following:

linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

A linear grammar has at most one non-terminal on the right-hand side of any rule, as per Linz' definition.
But any linear grammar can be transformed into an equivalent linear grammar of that special type, simply by adding a new non-terminal. Wikipedia goes on to show an example of this transformation. So it is possible to assume wolog that a linear grammar is in that form, if it turns out to be helpful.


How to get expected running time of hash table? If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much. Am I making a mistake here?

Why not sort the array, then iterate over the sorted array, comparing the current number to the previous number.

n*log(n) for the sort, n for the iteration = 2n*log(n)


How to solve for p in Akra-Bazzi method for analyzing time complexity? Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and webpages online, they all basically say "Here's the equation. Solve for $p$. It equals (whatever). Moving on now to the integral..." without explaining how they solved the equation.

If I had to figure it out I could use a binary search but I imagine there is a more mathematical way to get an exact answer.

It is not at all obvious to me how you're supposed to solve for p.

That is:

$$ a_1 b_1^p + a_2 b_2^p + a_3 b_3^p + \dots + a_k b_k^p = 1, $$

Where all $a_i$ terms are positive and all $b_i$ terms are fractional ($0 < b_i < 1$).

How can you solve for $p$ by hand?

You don't solve for $p$ by hand. You use a computer to get a numerical solution. In general, there is no reason to expect that $p$ have some nice form.

Since the left-hand side of the equation is monotone decreasing, there is at most one solution. Furthermore, when $p \to -\infty$ the left-hand side tends to $\infty$, whereas when $p \to \infty$ it tends to $0$. This shows that a solution does exist. The computer can find it using standard root-finding methods.

This kind of situation is encountered in many other places in computer sciences. Here are two examples:

The approximation ratio of the Goemans–Williamson algorithm is
$$ \min_{0 \leq \theta \leq \pi} \frac{2}{\pi} \frac{\theta}{1-\cos\theta} \approx 0.878, $$
which doesn't have a closed form. Surprisingly, assuming the unique games conjecture, this approximation ratio is the best that polynomial time algorithms can achieve in the worst case.
Running times of fast matrix multiplication algorithms are of the form $O(n^\rho)$ where $\rho$ is in simple cases the solution of an equation similar to the one you describe, and in other cases the solution of a much more complicated optimization problem. Again, there is no closed form for $\rho$ in most cases (other than Strassen's algorithm, perhaps).


Why does the time hierarchy theorem use a rather intricate diagonal argument? Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$?
Where am I wrong?

The output size does not scale with (time) complexity of problems in general.
In fact, complexity theorists are largely interested in decision problems for which the output will either be 0 or 1.


phrase searches and vector space model Consider a system that indexes documents based on vector space model and a simple query, such as qwe asd. When searching we assign weights to both words qwe and asd based on how often they appear in the index. The idea being that if word exists in larger number of documents then it should have smaller impact on relevance. This works well because for each word we usually store statistics: number of occurrences of a given word in the whole index and number of occurrences of a given word in each document (possibly after normalization).

Now consider another query: "qwe asd" zxcrty. We have two parts here: a phrase and a simple word. For the word we have the above mentioned statistics, but for the phrase we do not. This poses a question: how to rank documents against phrase searches? If we find a one document that contains the phrase (qwe asd) and another that contains the single word (zxcrty) which one should be ranked higher?

I somehow doubt that there is one and ultimate solution to this question but would like to know about what approaches are used in existing search engines, whether other models solve the issue and other information that can be useful in analysing the problem.

As you state in your comment, you could use a variety of different approaches. Your question isn't limited to the vector space model. Various language models rely on these concepts as well. Here are two approaches:

N-Grams

One popular approach is the use of n-grams. This approach involves treating adjacent words as one word. For instance, "big house" would be stored in your controlled vocabulary as "big," "house," and "big house" if you chose to use 2-grams (bigrams). Probabilities would be computed per n-gram

Pros: accurately keep track of probabilities of n-grams occuring, easy to extend from unigram model (just follow same ranking functions for unigrams such as tf-idf or Okapi BM25)

Cons: exponentially larger memory usage, many bigrams will only occur once

Inverted Index per Document

This approach requires storing an inverted index within each document in addition to an inverted index of the whole corpus. This would mean that you wouldn't need to store n-grams. Of course, you wouldn't have important information such as the term frequency or document frequency of an n-gram. The idea is that you look up the first word in the n-gram and find it in the document. You compare succeeding words to see if there is an n-gram present there.

Pros: less memory usage (no need to keep track of n-grams in documents), more flexibility (such as ignoring words that don't match)

Cons: less information stored (no TF, DF, etc.), more space needed per document (for inverted index), additional lookup needed, ranking this may be difficult

  If we find a one document that contains the phrase (qwe asd) and another that contains the single word (zxcrty) which one should be ranked higher?

This completely depends on the ranking function and how you choose to weight each thing. How common are qwe and asd? How common is zxcrty? Would you want to give additional weight to larger n-grams? These are all important considerations.


Problems understanding proof of smn theorem using Church-Turing thesis I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem:

Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a computable function $g(x)$ such that $f(x,y) = \Phi_{g(x)}(y)$ for all $x,y \in \mathbb{N}$. Here, $\Phi_n$ refers to the $n$th recursive function.

The proof goes like this:

For a fixed $x_0$, the function $h_{x_0}(y) = f(x,y)$ is computable (this I agree with) and so we there exists an index $e_{x_0}$ so that $h_{x_0} = \Phi_{e_{x_0}}$ (this I also agree with).

So, the function $g$ that to each natural $x$ assigns such index $e_x$ (so that $h_x = \Phi_{g(x)}$) is computable (this is the part I don't understand).

When saying that $g$ is computable it means that we can describe an algorithm that takes $x$ as an input and will output the desired $g(x)$. I don't see how such algorithm can be described. (I guess my confusion has to do with the "there exists an" that I placed in bold letters.)

If it helps, we are using Godel numberings of Turing Machines to index the recursive functions.

In books on computability theory it is common for the text to skip details on how a particular machine is to be constructed. The author of the computability book will mumble something about the Turing-Church thesis somewhere in the beginning. This is to be read as "you will have to do the missing parts yourself, or equip yourself with the same sense of inner feeling about computation as I did". Often the author will give you hints on how to construct a machine, and call them "pseudo-code", "effective procedure", "idea", or some such. The Church-Turing thesis is the social convention that such descriptions of machines suffice. (Of course, the social convention is not arbitrary but rather based on many years of experience on what is and is not computable.)

I am not saying that this is a bad idea, I am just telling you honestly what is going on. Books on analysis skip $\epsilon\delta$-proofs, books on category theory don't verify every naturality square, books on topology rely on geometric intuitions of the readers, etc.

There are standard tricks on how to read computability theory. If the book says "there exists $X$", then that usually means "$X$ can be computed from whatever our current parameters are". If they want to emphasize that whatever they are doing can be computed as a function of a parameter $p$, they will say "whatever we are doing, uniformly in $p$". And obviously, if they say "non-uniformly in $p$", they are emphasizing that whatever they are doing is not computable as a function of $p$.

In Barry's text, he could have emphasized the computability bit by writing "there exists an index $e_{x_0}$, uniformly in $x_0$, such that ..." But since this is an introductory text, sticking in the word "uniformly" will just confuse a good part of the readership. So what are we supposed to do? We certainly do not want to write out detailed constructions of machines, because then students will end up thinking that's what computability theory is about. It isn't. Computability theory is about contemplating what machines we could construct if we wanted to, but we don't. As usual, the best path to wisdom is to pass through a phase of confusion.


Is this applet implementation for the Go-Back-N ARQ protocol correct? I was reading a textbook describing the Go-Back-N (GBN) protocol with Finite State Machines as pictured below:

$\Lambda$ just means "initial state" or "no action", depending on the context. My questions are

This is the interactive animations link to GBN https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/go-back-n-protocol/index.html.
Let's say we are sending packet 0, packet 1 and packet 2, and packet 1 is lost beforen it arrive receiver. So when it is timeout, GBN will make sender re-send packet 1 and packet 2,
And I found an interesting thing which is,if you try the link with above scenario and you send packet 3 just before timeout occurs,this action reset the timer, because you can see the timeout is postponed(otherwise you will see packet 1,2,3 flying in screen).But according to the sender's FSM, after you send packet 3, timeout occurs immediately, then the sender will re-send packet 1 and packet 2, but it didn't happen as timeout is postponed, which
contradicts the fact that time is only get reseted when base = nextseqnum?

On the receiver's FSM, why it needs to set expectedseqnum = 1 and make a packet based on it? why we cannot set expectedseqnum = 0 as the only initialized action?

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

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

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

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

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

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


Real life applications of finite automata I have some confusion about the differences between finite & infinite.
can someone tell me how the Toll machine or Park meter, soda vending machine can be used with infinite language? if not, please give me an example of other application.

As Yuval Filmus said, the KMP substring matching is widely used in practice because of its modularity and efficiency.

A maybe more "practical" exemple is lexical analysis.
(https://en.wikipedia.org/wiki/Lexical_analysis)

Depending on your application (let say or the compilation of a programming language) the parsing phase can be done with some various
generalisation of automatons (state transition machines or pile-automatons for instance). The language they accept is infinite (think of the set of all programs that are syntactically correct in your favorite language), yet
the recognition of a correct program should be done by an automata (or a generalisation of it) which is finitely presented.


Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing A gardener consider aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is:

|               |
|       |       |
|   |   |   |   |

On the other hand, the following configurations would be invalid:

|
|  |
|  |  |

reason: 3rd tree should be higher than the 2nd one

|  |
|  |
|  |

reason: consecutive trees cannot have the same height

Given a sequence of physical trees in a garden, what is the minimum number of physical trees which must be cropped/cut in order to achieve the pattern desired by that gardener?

First, the heights of the physical trees in the garden can be represented by a sequence of integers. For instance, the three examples above can be represented as (3  1  2  1  3), (3 2 1) and (3 3).

Mathematically speaking, the problem maps to find the minimum number of negative sums which must be applied to a sequence of integers (a0, a1, ..., aN) so that each pair of consecutive integers (ai, ai+1) in this sequence alternates between strictly decreasing (ai < ai+1) and strictly increasing (ai > ai+1) .
Example: In (2, 3, 5, 7) , the minimum number of negative sums is 2. A possible solution is to add -2 to the 2nd element and then add -3 to the last element, resulting in (2, 1, 5, 4).

My search model is a graph where each node represents a sequence of physical tree heights and each edge represents a decrease of the height of a tree (from now on called "cut"). In this model, a possible path from the initial node to the goal node in the above example would be

initial node: (2,3,5,7)
action: sum -2 to a1
intermediate node: (2,1,5,7)
action: sum -3 to a3
goal node: (2,1,5,4).

I have used a breadth-first search to find the shortest path from the initial node to the goal node. The length of this shortest patch is equal to the minimum number of trees that must be cut.

The only improvement to this algorithm that I was able to think was using a priority queue that orders the possible nodes to be explored in increasing order 1st by number of cuts (as traditional BFS already does) and 2nd by the number of  "errors" in the sequence of integers in the node: triplets which do not match the required up/down pattern, ie. (ai < ai+1 and ai+1 < ai+2) OR (ai > ai+1 and ai+1 > ai+2), plus the number of consecutive equal numbers pairs  (ai == ai+1)  . This increases the probability that the goal node will be reachable from the first nodes with N-1 cuts in the queue when the times come to evaluate them. However, it is only useful to reduce the search space of nodes with N-1 cuts and not the complexity of the whole search.

The time required to execute this algorithm grows exponentially with the number of the trees and with the height of the trees. Is there any algorithm/idea which could be used to speed it up ?

I'll describe two ways you could solve this problem.  Either works.  In some sense they are basically the same algorithm, just viewed from two different perspectives.

Dynamic programming algorithm

This can be solved in linear time with dynamic programming.  Let $d_i$ denote minimum number of $a_i,\dots,a_n$ that must be cut to produce an alternating sequence if you start in the downwards direction for the first pair (the pair $a_i,a_{i+1}$) and don't cut $a_i$, and $u_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you don't cut $a_i$, and $u'_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you do cut $a_i$.  Then you can write down a recurrence relation that expresses $d_i,u_i,u'_{i+1}$ in terms of $d_{i+1},u_{i+1},u'_{i+1}$, and you can evaluate it in $O(n)$ time using dynamic programming.

In particular, the recurrence relation is $u'_i = 1 + d_{i+1}$ and

$$d_i = \begin{cases}
\min(u_{i+1},u'_{i+1}) &\text{if }a_i>a_{i+1}\\
+\infty &\text{otherwise.}
\end{cases}$$

$$u_i = \begin{cases}
d_{i+1} &\text{if }a_i<a_{i+1}\\
+\infty &\text{otherwise.}
\end{cases}$$

Once you've computed all these values, the final answer for the minimum number of cuts needed for the sequence $a_1,\dots,a_n$ is $\min(d_1,u_1,u'_1)$.

Graph search

Alternatively, we can solve this by building up a suitable graph and then finding the shortest path in this graph.

Label a tree as a "peak" if in  it is higher than its neighbors in the final sequence, and a "valley" if it is lower than its neighbors in the final sequence.  The final sequence will alternate between peaks and valleys.  Here is the two key observations:

The optimal solution will never cut any tree that ends up as a peak.  (Any solution that involves cutting a peak will remain valid if you don't cut the peak, and that reduces the number of cuts by 1.)
In the optimal solution, you can assume without loss of generality that every tree that ends up a valley is cut down to the ground, i.e., to the minimum height.  (Any solution that involves cutting a valley only partway will remain valid if you cut it down to the ground.)

Since we want to find an optimal solution, we will consider only solutions that follow both rules.

Let $a_1,\dots,a_n$ be the sequence.  We will build a graph with $3n$ vertices.  Each vertex has the form $\langle i,t,c \rangle$ where $i \in \{1,2,\dots,n\}$ is an index that identifies a tree, $t$ indicates whether tree $i$ will be a peak or a valley in the final solution, and $c$ indicates whether tree $i$ is cut to the ground or uncut in the final solution.  We'll have an edge from one vertex to the next if they can be adjacent in a final solution.  Thus, we have the following edges:

$\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{no} \rangle$, with length 0, for those $i$ where $a_i>a_{i+1}$
$\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{yes} \rangle$, with length 1, for all $i$
$\langle i, \text{valley}, \text{no}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for those $i$ where $a_i<a_{i+1}$
$\langle i, \text{valley}, \text{yes}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for all $i$

Finally, find the shortest path in this graph from a start vertext to an end vertex, where the start vertices are those of the form $\langle 1, *, *\rangle$ and the end vertices are those of the form $\langle n, *, *\rangle$.  The length of this path will correspond to the minimum number of cuts needed in the optimal solution, and the path itself can be used to reconstruct the final solution.  This shortest path can be found in $O(n)$ time using breadth-first search (BFS) on the graph defined above.


BFS implementation: queue vs storing previous and next frontier The most trivial implementation of BFS would simply store the last frontier (open list), build the new frontier, and then replace the last frontier with the new (like in the example python code below). But almost universally, the first algorithm shown for BFS in textbooks is the queue-based implementation.

What's the disadvantage of the simple frontier-storing approach? I can see it might use slightly more memory (effectively storing the new frontier while the old is still in memory), but usually textbooks only care about big-O complexity. Is there any other problem with it?

# example of a graph
g = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: []}

def bfs(g, root):
    yield root
    boundary = [root]
    visited = {root}
    while boundary:
        new_boundary = []
        for v in boundary:
            for w in g[v]:
                if w not in visited:
                    yield w
                    visited.add(w)
                    new_boundary.append(w)
        boundary = new_boundary

Your analysis is correct.  There is no major disadvantage of the two-list approach you outline.

One nice thing about the queue-based formulation of BFS is that it makes it easier to see the relationship to DFS and Dijkstra's algorithm.  Start with the queue-based formulation, and replace the queue with a stack, and you get DFS.  Replace the queue with a priority queue, and you get Dijkstra's algorithm.  This similarity is aesthetically pleasing and might help understand the algorithm better.

A slight disadvantage of your two-list based scheme is that it has somewhat higher memory consumption: only a constant factor higher, so maybe not a big deal, but it is somewhat higher.  This is because when you're traversing the current frontier, you keep around the items in the list that you've already traversed even after you've finished traversing them.  In contrast, the queue-based method doesn't do that.

Nonetheless, in the big picture, you are absolutely right; both methods are pretty similar and there's not an overwhelming reason to prefer one over the other.


Sort an array based on dependencies I have an array of objects, each of them has a numeric id and another array attached to them.

The array in the object contains the dependencies of that object. Each dependency is an id from the other objects. There are no circular dependencies.

Let's take this diagram:

The ids of the objects are in the upper rectangle, the dependecies are in the lower one.

I need to sort the array in a way, so if an object depends on another object, then it needs to be after that object in the array.

So for the example above it would be

3 1 2 4

You effectively have a directed graph here, where your vertices are the entries of your array, and you have an edge $(i,j)$ between entries $i$ and $j$ iff $j$ depends on $i$. What you want is a topological sort of this graph (https://en.wikipedia.org/wiki/Topological_sorting).


Construct DFA accepting strings ending with '110' or '101' Let the alphabet be $\Sigma=\{0,1\}$. I want to construct a DFA which accepts strings ending with either '110' or '101', additionally there should be only one final state.

I have a solution with more than one final state, but cannot come up with a solution which has only one final state.

There cannot be a single final state. Consider any DFA for the language, and let $\sigma_{110},\sigma_{101}$ be its states after reading $110,101$ (respectively). Clearly $\sigma_{110},\sigma_{101}$ are accepting states. Moreover, they cannot be the same state since $1101$ is in the language but $1011$ is not.


Can we use exponential function in a reduction? If I have an NP-complete graph problem $P1$ whose instance, say, a graph $G$ and a positive integer $k$ and I have another graph problem $P2$ whose instance is a graph $G'$ and a positive integer $k'$. I would like to prove that $P2$ is NP-complete. The reduction is as follows:

set $G'= G$ and
set $k'= f(k)$.
$P1$ is solved iff $P2$ is solved.

My question is: is this reduction correct when $f(k)$ is exponential function?, For simplicity, say, $f(k)=2^k$. I am afraid that this is no longer polynomial-time but then again calculating $2^k$ or $k!$ is polynomial-time problem.

My whole question is general as the title mentions:  Can we use exponential function in a reduction to create some parameter in the instance of the concerned problem?

EDIT

My question is motivated by the validity of using exponentiation in polytime reduction on cstheory.SE where the OP asks about a specific reduction used in some paper. My question is general about using exponentiation in reduction.

For the sake of notation, I'm going to assume you're trying to produce a polynomial time reduction $f$, which that maps instances $x$ of some problem $L_1$ to instances $f(x)$ of some other problem $L_2$.  Instances of $L_i$ have parameter $p_i$ ($i\in\{1,2\}$).  Since the reduction has to run in polynomial time, it has to output at most a polynomial number of bits, say $|x|^q$ for some constant $q$. In particular, the representation of $p_2$ can't be more than $|x|^q$ bits long.

So, suppose the value of the parameter is $k$ in some instance $x$ with parameter $p_1=k$. Whether or not $f(x)$ can have parameter $p_2=2^k$ depends entirely on what the parameters are and how big $p_1$ can be.

If $p_1$ is a number represented in unary, we have $p_1\leq |x|$; if it's a number represented in binary or some higher base, then $p_1 = O(2^{|x|})$. If $p_1$ is the size of some object described in $x$, then its size will depend on what kind of object it is (e.g., if $p_1$ is the size of some set of a graph's the vertices, $p_1\leq |x|$; if it's the number of pairs of vertices with some property, $p_1\leq |x|^2$, and so on).

And, now, what's $p_2$? If it's a number in unary, then $2^k$ is a string of length $2^k$, so we need $2^k\leq |x|^q$, i.e., $k=O(\log |x|)$. If it's a number in binary, then $2^k$ is just a $1$ followed by $k$ zeroes, so we can write this in our output as long as $k=O(|x|^q)$. If it's the size of some structure then, again, it depends on how that structure is represented. For example, if you need to add $2^k$ vertices, you need all those vertices to be stored in at most $|x|^q$ characters, so $k$ had better not be any bigger than about $\log n$.


Using reduction to prove that a given language is not recursively enumerable Let  the language $L$  be as follow  ;

$$L=\{\langle M_1 \rangle \langle M_2 \rangle \mid L(M_1)  \cap L(M_2)=\emptyset \}$$

$\langle M_1 \rangle$ and $\langle M_2 \rangle$ are the encoding of the Turing machine $M_1$ and $  M_2$.

Using Reduction, I have to prove that $L$ is not  recursively enumerable.

In order to prove that I have to find a non-recursively enumerable  language $S$ so that:
$$S \leq L$$
One of the non recursively enumerable that I had in my lesson, were  those :
$${H_{\varepsilon}^\complement}=\{\langle M \rangle \mid \text{M does not halt on empty input} \}$$
 and ;
$${H_{all}}=\{ \langle M \rangle \mid \text{M halts on each input} \}$$

$$ \text{Let then } S = {H_{all}}$$

I  have to prove in this case  that  ;
$${H_{all}} \leq L $$

let then  ;
$$ f : {H_{all}} \rightarrow L  \\
 \langle M \rangle \mapsto \langle M \rangle \langle M^\complement \rangle$$

In this case $M^\complement $ simulate M in each input , when $M$ accepts/rejects, $M^\complement $ rejects/accepts.

$\texttt{case 1}$

$\langle M \rangle \in {H_{all}} \Rightarrow  \text{M halts on each input and accepts/rejects} \Rightarrow  M^\complement\text{ hatls on each input and rejects/accepts} \Rightarrow  L(M) \cap L(M^\complement)= \emptyset  $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \in L $

$\texttt{case 2}$

$\langle M \rangle \not\in {H_{all}} \Rightarrow  \text{M does not halt  on all inputs} \Rightarrow  M^\complement\text{  halts  on some inputs} \Rightarrow  L(M) \cap L(M^\complement) \neq\emptyset  $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \not\in L $

somehow  i think , the contruction of the function of is not  right, does anyone maybe have an other idea or an other S to choose ?

Assume that $L$ is recursively enumerable. We can reduce the Halting problem to $L$ as following. Given $\langle M, w \rangle$, create a TM $M'$ which halts only on the input $w$, and infinitely loops if the input is different from $w$. Clearly $L(M') = \{w\}$ and $L(M) \cap L(M') = \emptyset \iff \langle M,M' \rangle \in L \iff \langle M, w \rangle \notin HALT$. This shows that $\overline{HALT}$ is recursively enumerable. Since $HALT$ is also r.e. it follows that $HALT$ is decidable which is impossible. Thus $L$ is not recursively enumerable.

$HALT = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on input } w \}$.


is a while loop always an indefinite loop? Building on this example and others found elsewhere we have two types of loops, definite and indefinite:

definite being a loop that has its number of iterations known before it is executed. E.g. a for loop:

for x in range(1,10):

and indefinite loops which don't have the number of iterations known before it is executed. E.g. this while loop:

while answer <> "Yes":
    answer = input("are you an idiot?")

I'm checking some teaching materials that have an example of a while loop that looks definite to me as by looking at the code you know exactly when it is going to end:

number = 1
while  number <= 10:
    print(number)
    number = number +1

Is this example a definite loop even though we have to do a little work to work out the for loop equivalent?

Yes, this is definite loop, as long as you (or your compiler for that matter) can infer number of passes.
In some languages (like C), 'for' is a transformation that expands during compilation to 'while' construction like you have shown. Compiler would infer number of steps during optimisation phase, when you have provided constant expression loops of any kind, but will not infer that from variable expressions.


Why does introsort use heapsort rather than mergesort? As part of a homework assignment covering implementation of introsort I'm asked why heapsort is used rather than mergesort (or other $O(n\log(n))$ algorithms for that matter).

  Introsort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. (Wikipedia, retrieved 2014-May-06.)

The only reason I can think of is that heapsort is "in place" ... But tbh I don't really understand why this would matter here though.

The 2 downsides of quicksort is that it requires $O(\log n)$ extra space (to keep the unsorted intervals) and bad pivot selection (or contrived sequences designed to make you select a bad pivot) may cause it to be a $O(n^2)$ time and $O(n)$ extra space algorithm.

Switching to heapsort when the recursion depth becomes too large (at around $\log n$) means we have a guaranteed upperbound that is $O(n \log n )$ time and $O( \log n)$ extra space.

Heapsort's $O(1)$ extra space requirement makes it a better choice to mergsort's $O(n)$ where for a contrived array that $n$ could still be large.

The reason heapsort isn't used for the full sort is because it is slower than quicksort (due in part to the hidden constants in the big O expression and in part to the cache behavior)


How does the TLB identify a particular process? I have read that the translation lookaside buffer (TLB) is implemented in hardware and stores the page numbers and the corresponding frame numbers for faster lookups. Now suppose there are two processes, A and B. Page 2 is mapped to a particular frame number. Now if we are searching for page 2 in the TLB, it can belong to either process A or Process B. So how will the TLB determine which process the page belongs to? Or it is flushed each time a new process is brought into running state? Also, what mechanism is used in TLB lookup?

In the most basic setup, the TLB doesn't determine that.  Instead, the TLB only maintains mappings for the pages that are accessible to the current process.  If process A is currently running, the TLB only contains mappings for the pages that are accessible to process A; so if page 2 belongs to process B, it won't be in the TLB.

Also, you should be aware that the TLB is a cache.  The definitive authoritative mappings are in the page table, and the page table contains mappings only for the process that is currently running.  The TLB is a cache of mappings found in the page table.  It gets filled in as you go.

When you change which process is running, you change the page table (since now you need a different set of mappings), and you clear the TLB (so you don't have any old mappings that are only relevant to the previous process).  Clearing the TLB is also called flushing the TLB.

I suggest reading a good OS textbook.  This information can be found in many places, so do a bit of research.  Also
https://en.wikipedia.org/wiki/Translation_lookaside_buffer may be helpful.

That describes the basic setup.  The disadvantage of the basic setup is that clearing the TLB is slow, which adds a lot of overhead every time you switch processes.  That slows things down.  Many modern processors have optimizations that reduce this overhead.

For instance, modern Intel TLBs have a process context ID (PCID); each TLB entry is tagged with the PCID of the process that the page mapping is for, and the processor will only use that TLB entry if its PCID matches the ID of the currently running process.  The processor fills the PCID when it creates the TLB entry from a register which the operating system must set to a unique value for each process.  You can read about that more by searching for PCID.

Arm processors have a somewhat similar feature called domains.  Each page table entry contains a domain field, which must be set by the operating system if it wants to use this feature.  The processor saves this value in the TLB entry.  On a context switch, the operating system updates a register containing the set of currently accessible domains.  A TLB entry is valid only if the corresponding domain is accessible.


How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F? The well-known Church encoding of natural numbers can be generalized to use an arbitrary (covariant) functor F. The result is the type, call it C, defined by
  data C = Cfix { run :: forall r. (F r -> r) -> r }

Here and below, for simplicity, we will assume that F is a fixed, already defined functor.
It is widely known and stated that the type C is a fixpoint of the functor F, and also that C is an initial F-algebra. For example, if the functor F a is defined by
 data F a b = Empty | Cons a b

then a fixpoint of F a is [a] (the list of values of type a). Also, [a] is the initial algebra. The Church encoding of lists is well known. But I could not find a rigorous proof of either of these statements (C is a fixpoint, and C is the initial algebra).
The question is, how to prove rigorously one of the two statements:

The type C is a fixpoint of the type isomorphism F C ≅ C. In other words, we need to prove that there exist two functions, fix :: F C -> C and unfix :: C -> F C such that fix . unfix = id and unfix . fix = id.
The type C is the initial algebra of the functor F; that is, the initial object in the category of F-algebras. In other words, for any type A such that a function p :: F A -> A is given (that is, A is an F-algebra), we can find a unique function q :: C -> A which is an F-algebra morphism. This means, q must be such that the law q . fix = p . fmap q holds. We need to prove that, given A and p, such q exists and is unique.

These two statements are not equivalent; but proving (2) implies (1). (Lambek's theorem says that an initial algebra is an isomorphism.)
The code of the functions fix and unfix can be written relatively easily:
 fix :: F C -> C
 fix fc  = Cfix (forall r. \g -> g . fmap (\h -> h g) fc )
 unfix :: C -> F C
 unfix c = (run c) (fmap fix)

Given a function p :: F A -> A, the code of the function q is written as
 q :: C -> A
 q c = (run c) p

However, it seems difficult to prove directly that the functions fix, unfix, q satisfy the required properties. I was not able to find a complete proof.
Is it easier to prove that C is an initial algebra, i.e., that q is unique, than to prove that fix . unfix = id?
In the rest of this question, I will show some steps that I was able to make towards the proof that fix . unfix = id.
It is not possible to prove either (1) or (2) simply by using the given code of the functions. We need additional assumptions. Similarly to the Yoneda identity,
 forall r. (A -> r) -> F r   ≅   F A   ,

we need to assume that the functions' code is fully parametric (no side effects, no specially chosen values or fixed types) so that the parametricity theorem can be applied. So, we need to assume that the type C contains only functions of type forall r. (F r -> r) -> r that satisfy the appropriate naturality law (known as "free theorem" after P. Wadler's paper "Theorems for free").
The parametricity theorem gives the following naturality law ("free theorem") for this type signature:
For any types A and B, and for any functions p :: F B -> A and f :: A -> B, the function c :: forall r. (F r -> r) -> r must satisfy the equation
  c (f . p) = f . c (p . fmap f)

Using this naturality law with appropriately chosen p and f, one can show that the composition fix . unfix is a certain function of type C -> C that must be equal to \c -> (run c) fix.
However, further progress in the proof does not seem to be possible; it is not clear why this function must be equal to id.
Let us temporarily define the function m:
 m :: (F C -> C) -> C -> C
 m t c = (run c) t

Then the result I have is written as
fix . unfix  = m fix

One can also show that unfix . fix = fmap (m fix).
It remains to prove that m fix = id. Once that is proved, we will have proved that F C ≅ C.
The same naturality law of c with different choice of p and f gives the strange identity
 m fix . m (m fix . fix) = m (m fix . fix)

But I do not know how to derive from this identity that m fix = id.

$\newcommand{\fix}{\mathsf{fix}}$
$\newcommand{\fold}{\mathsf{fold}}$
$\newcommand{\map}{\mathsf{map}}$
Here is, I believe, how one would use parametricity to prove your last lemma. I'm going to rework some stuff slightly for my own understanding. We have: $$C = ∀ r. (F r → r) → r$$ with $F$ functorial. We have: $$\fix : F C → C$$ corresponding to your definition, and I'm going to call a generalization of your m: $$\fold : (F r → r) → C → r \\ \fold\ α\ c = c\ α$$
So, we want to prove that for all $c : C$, $\fold\ \fix\ c = c$
Parametricity looks like this:
$$∀(R : a \Leftrightarrow b).\\ ∀ (α : F a → a) (β : F b → b).\\ (∀ x y. FR(x,y) → R (α\ x, β\ y))\\ → ∀ c. R (c\ α, c\ β)$$
To unpack this a bit, if we have a types $a,b$, a relation $R$ on them, algebra structures $α,β$, and a proof that they preserve the relation, then $R$ relates $c \  α$ to $c \ β$. The idea behind the "preservation" criterion is that $FR(x, y)$ holds if $x$ and $y$ have the same $F$ 'shape', and corresponding occurrences of $a$ and $b$ values are related by $R$.
So, let's make some choices. Suppose we have $ζ : F z → z$. Then: $$a \equiv C \\ b \equiv z \\ R(c, z) \equiv c\ ζ = z \\ α \equiv \fix \\ β \equiv ζ$$ the result of parametricity for these choices will be: $$R(c\ \fix, c\ ζ) \equiv c\ \fix\ ζ = c\ ζ$$
Then by function extensionality we will obtain $c = c\ \fix = \fold\ \fix\ c$. Our obligation is to prove:
$$∀ fc\ fz. FR(fc,fz) → R (\fix\ fc,ζ\ fz)$$
The goal is $$\fix\ fc\ ζ = ζ\ fz$$
By unfolding the definition of $\fix$ we know: $$\fix\ fc\ ζ = ζ (\map_F\ (\fold\ ζ)\ fc)$$
However, the meaning of $FR(fc,fz)$ is actually that $$\map_F\ (\fold\ ζ)\ fc = fz$$ So the result is immediate.
I haven't thought about whether it's possible to make due with dinaturality. I think it is not, but I could be wrong.
Edit:
The free theorem for this scenario is:
$$(∀ x. f (α\ x) = β (\map_F\ f \ x)) \Rightarrow f (c\ α) = c\ β$$
If we choose $$f = \fold\ ζ \\ α = \fix \\ β = ζ$$ then our obligation is:
$$\fold\ ζ\ (\fix\ x) = \fix\ x\ ζ = ζ (\map_F\ (\fold\ ζ)\ x)$$
which is just the definition of $\fix$. The result is:
$$\fold\ ζ\ (c\ \fix) = c\ ζ$$
which again gives us what we wanted. Note that this is also not the same as dinaturality, though. I believe the difference is that dinaturality allows us to shift $f$ around in the expression, but parametricity allows us to absorb it into one of the algebras.


Why did MIPS include shamt and distinguish funct/opcode? I'm confused as to why the MIPS designers would include 5 bits dedicated to shifting and have separate opcode and function bits.

Because MIPS is so RISC I assume that only shifting would be done in a few instructions, so those 5 bits seem like they're wasting space when they could be put in the immediate. I assume that opcodes and funct are seperate for distinguishing R- and I- type instructions, but this could be done by extending the opcode by 1 bit. With both of these R-type instructions could be 22 bits long. This won't work if the I-type and J-type instructions want to keep their immediate and address, but both seem unnecessary.

There are a few different trade-offs going on here.

First, we want the instructions to be fixed width (32-bits).  This guarantees that instructions are cache-block and page aligned which simplifies cache and page presence and permission checks.

Second we want the various instruction fields (opcode/source regs/immediates) to be fixed width and fixed position.  This makes them faster/less logic to decode and they are needed in the early stages of the pipeline.  (The destination register isn't needed until the end of the pipeline, so it can be in different places in R and I instructions.)  The position and width of the function field matters a little less because that needs to control the function of the ALU, but that's in the third pipeline stage, so you have a little time to work with it if needed.

But now we have a tension between number of possible instructions and the sizes of the immediates.  We want the immediates in the I and J instructions to be long as possible.  This is a 32-bit architecture, and the J instruction has only a 26-bit address.  It gets two zero low-order bits added to it (another benefit of fixed width instructions) but you can still only jump a maximum distance of $2^{28}$ bytes, which makes life difficult for the linker.  (A call of a procedure that is more than $2^{28}$ bytes distant needs to be done with a triple instruction: load-upper-immediate, add-immediate, jump-and-link-register, instead of just a jump-and-link.)  The 16-bit immediate in I instructions is also nice for compiler/linker writers.  (On the SPARC, where the immediate field was only 12 bits they had to add an entire special load-high instruction class with a 20 bit immediate.)

So we really don't want to make the opcode 7 bits (because it will cut into immediates) but with 6-bits we only have $2^6=64$ possible different instructions, which is way too few.  The compromise is: there are exactly two type J instructions (jump and jump-and-link), and only one or two type R instructions, with the remaining 60-or-so opcodes being used for I instructions.

But that leaves some wiggle room with the R instructions.  Aside from the 6-bit opcode, these only need 15 additional bits for register specification, which leaves 11 bits for the extended opcode and/or shift-amount.

You should think of the function field as being an extended opcode for the R instruction.  There's only one R instruction opcode, but there are 64 different functions that the R instruction can perform.

Okay.  We have 60 different I instructions and 64 different R instructions, so where should we put the shift-immediate instructions?

Well, not only are there fewer I instructions, but there are way more things we want to do with I  instructions.  Recall that all the branch instructions need to be I instructions because they have a relative (immediate) offset.  Also all the load and store instructions are I format on MIPS.  And finally we need the load-upper-immediate instruction to be an I instruction.  Not only that, but the R instructions still have 5 additional unused bits, (which is what we need for the immediate of a shift-immediate on this architecture), so this gives further incentive to making the shift-immediates into special (weird) R instructions.

A lot of these decisions are more art than science, but there is an underlying logic that can be discerned.  The key goal is not to make the number of instructions as small as possible, it is to make a high-performance pipeline fit on a single chip (so that tiny companies, like MIPS and Sun were in the 1980s, could compete with IBM and DEC).  (The name RISC, invented by David Patterson, is somewhat unfortunate.  It caught on because it was cute, not because "reduced instructions" is an accurate description of what the MIPS and SPARC architectures were really trying to do.)  So you want the instructions fixed width (and relatively small so that you get better I-cache behavior) to make fetch, paging and decode simpler and faster.  You want the parts of the instruction that need to be decoded early (the opcode, the two source registers, and the sign-extended immediate) to be a fixed width and in a fixed position.  You want immediates to be as long as possible, and you want as many different kinds of instructions as will fit, given all those other constraints.


Understanding the heuristic used for approximate string searching through an FSA The paper I'm looking at: Fast approximate string matching with finite automata (2009)

Explanation of the algorithm (from my understanding anyway):

A word is inputted into the automaton and from each state, a number of possible actions can be taken depending on the current symbol/character being looked at at position $pos$. These "actions" include:

Staying at the current state and deleting the character currently being pointed at by $pos$.
Taking a transition to a next state and substituting the current
character at $pos$ with the transition label used.
Taking a transition to a next state and inserting the transition
label at $pos$.

The action is decides to take is based on a cost function $f=g+h$ (where the lowest $f$ is chosen) for each action.

$g = 0$ if no edit operation is performed on the input word (i.e. the transition label taken to a next state, is the same as the current character at pos) and $g=1$ otherwise.

$h$ is the maximum between two heuristic functions $h(2)$ and $h(\infty)$.

$h(2)$ looks at the transition labels that can be reached within two
transitions from that state (note, not the current state) and
compares those reachable transitions to the next two characters in
the input word after $pos$. $h(2)$ gets $+1$ added for each character in
the input word that does not match any of the characters that the
state $s$ can reach within two transitions.
$h(\infty)$ looks at the transition labels that can be reached until
the end of the path from that state and compares that to the rest of the input word after pos. As with $h(2)$, $+1$ for each character in the input word that can't be matched to any of the reachable characters from state $s$.

Eventually this algorithm will lead to some accepting state where the path up to that accepting state is the closest accepted word to the input.

I think I understand the algorithm correctly since I tried to implement it from my understanding in Java (I'm doing it for my project, although my project only handles regular expressions of a small alphabet of around 3 different symbols as opposed to a natural language dictionary) and it seems to work to some extent and works fine for the example given in the paper, however my problem is is that I don't understand what priority is used in the case where $f$ values tie for $f=g+h$ (tied $f$ values are actually common).

The example used in the paper, inputs the word "dat" into the automaton, what I don't understand is why the algorithm goes from state 0 to state 3 (I circled this part in red) when $f=g+h$ is also 1 for the state 0 choice (I circled this part in blue).

The paper mentions

  "ties were resolved in the priority queue by giving priority to the highest word position."

but I don't understand what is meant by this.

It also mentioned:

  "In our experiments, the strategy of breaking ties so that the node that has advanced farthest in the word to be matched is given priority has proven to be far superior to any of the tiebreaking strategies we explored."

Those two statements are correlated: "giving priority to the highest word position" is the same as "the node that has advanced farthest in the word is given priority".

This appears to be why the algorithm selects state three. State zero does not result in an advancement in word position, whereas the transition to state three is further in the word position and so satisfies their heuristic of highest word position and thus gets priority for first expansion.

To see why this heuristic results in better results, examine the node zero. Deleting 'd' you see all the letters remaining are in the reachable nodes from zero, which means $h = 0$, and we only performed 1 operation, so $f = 1$. However in order to get to the acceptance state along the shortest path we have to take another operation to go to 3 while adding 'c' back, then we transition through the states 5, and 7 making no changes. Obviously the fastest (and shortest) path is to simply swap 'd' to 'c' and transition to state three first, which the heuristic suggests in this case.


Average case of simple algorithm like binary search These questions is about one of my research. As I am not a computer scientist, formal answering is difficult  to me.

I have a special search algorithm which the explanation here will take a lot of time. However I can explain it shortly by some notations.

Assume that we have an array of somethings (in my real research they are some cities which they form a path graph) with length $n$. First, we should select one element by some rules( I ignore the rules here) with $O(1)$ time. indeed, according to the rules this element is nearer element to my solution. However, as this rule does not follow a particular order, we can assume that the selection is random.

This element may take tree label, say $L$, $R$ and $M$. The label can be found in $O(1)$ time. If the label is $M$, then we found the solution. Else, if the label is $l$, then we found that this element is not solution and also all elements before it can not be a solution. similarly, this scenario is also correct when the label is $R$, i.e. this element is not solution and also all elements after it can not be a solution. This leads a binary like search algorithm with the difference  that the first element is not the median of array.
we can summarize the above statements as the following algorithm.

Input: An array $A$ with length $n$.
while length(A) > 1 do
 1.  choose an element $k$  (for example, randomly with uniform
     distribution) with $O(1)$. Find its label with $O(1)$.
 2.If the label is $M$, then stop
 3. else if the label is $l$ then  delete $k$ and all elements before $k$.
 4. else if the label is $r$ then  delete $k$ and all elements after $k$.
end while

I know that the worst case complexity is  $O(n^2)$ and the best complexity is $O(1)$. What is the average complexity?

The average case time complexity is $O(\log n)$ (with a suitable implementation).  Intuitively, each iteration typically removes a constant factor of the elements from the array.

Here's a more formal analysis. Consider an iteration to be "good" if it removes at least $1/3$ of the elements of the array.  Then an iteration is good with probability $2/3$.  Let $X_1$ denote the number of iterations until the first good iteration; this is a geometric random variable, so its expected value is $1.5$.  Let $X_2$ denote the number of iterations after the first good iteration, until the second good iteration.  Again, the expected value of $X_2$ is $1.5$.  And so on.  Now note that after $j$ good iterations, only a $(2/3)^j$ fraction of elements remain, so after at most $k = \lg_{2/3} n$ good iterations, the array will have only a single element and will terminate immediately.  The total number of iterations is $X_1 + X_2 + X_3 + \cdots + X_k$.  By linearity of expectation, the expected value of this sum is $1.5k$.  Thus the expected number of iterations until this terminates is $1.5 \lg_{2/3} n =  \frac{1.5}{\log(2/3)} \log n = O(\log n)$.

You can implement this so each iteration takes $O(1)$ time.  In particular, you don't actually remove elements in steps 3 and 4; you just keep track of the range of indices of non-removed elements.  That's always a consecutive range, so everything is easy.

In this way, the algorithm takes $O(\log n)$ iterations on average, and $O(1)$ time per iteration, for an average-case running time of $O(\log n)$.

Incidentally, with this implementation, the worst case running time is $O(n)$ rather than $O(\log n)$.  Each iteration of the loop removes at least one element from the array, so there can be at most $n$ iterations of the loop, and each iteration runs in $O(1)$ time, for a total of $O(n)$ worst-case running time.


Shortest travelling cost if we have bunch of points in 2D plane I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane and any two of them were Source and Destination. I was asked to calculate the least cost to travel all the points starting from the source and ending on Destination point. The cost to travel between any two points is |x1 - x2| + |y1 - y2|.

So, what I thought of doing was construct a cost matrix and apply Dijkstra since I thought constructing the shortest path tree must be the solution.

But I couldn't think on how to construct this cost matrix. What is the best approach for this?

This is the Traveling Salesman Problem with the $L_1$ metric (also known as the Manhattan distance).

Unfortunately, this version of the TSP is also NP-hard.  Therefore, there is no algorithm that always produces the optimal solution, is efficient, and works for all inputs.  Instead, you'll have to use a heuristic or approximation, or accept a solution that can take exponential time in the worst case.  Dijkstra's algorithm won't suffice.

Strictly speaking, the standard formulation of the TSP doesn't allow you to visit any point more than once.  However, in this situation allowing you to visit a point more than once doesn't make the problem any easier, since visiting a point more than once will never help you find a shorter solution.

Perhaps the following paper will be useful:

The L1 Traveling Salesman Problem.  Donald C.S. Allison, M.T. Noga, Information Processing Letters, vol 18, 1984, pp.195-199.


It is necessary to minimize the functional Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height of $0$, and the lower right the height $1$. For each road we know how many people go in each direction on this road. In this case, if the road leads from the intersection $i$ to the intersection $j$ and the height difference $h = h_j - h_i$, the inconvenience of moving every person on this road is equal to $\max(h, 0)$. For all intersections except two angle are allowed to choose any height. It is necessary to minimize the total inconvenience. In the end, it is necessary to obtain only a total inconvenience, the individual heights are not needed.

I think all heights will lie in the set $\{0, 1\}$. It is clear that you can honestly cycle through all the bitmaps and choose the best. But you need to find more efficient algorithm. One of my ideas was to put all the intersections in the upper left part of the height equals $0$, and the right lower part of the height equal to $1$. Here would be required to find the optimal boundary. I came up with a way of solving by finding maximum flow of minimum cost in $O(N^8)$. Can it be better?

Example:

P. S. Sorry for my bad English.

This problem is exactly the problem of finding the minimum $(s,t)$ cut in a directed graph, where $s$ is the upper-left corner and $t$ is the lower-right corner.  All the vertices on the $s$ side of the cut will be assigned height 0; all the vertices on the $t$ side of the cut will be assigned height 1; and the capacity of the cut is equal to the sum of the counts on the edges that cross the cut in the $s\to t$ direction.  You want to minimize this sum, so you want to find the minimum $(s,t)$ cut. There are many standard algorithms for doing that, based on finding a maximum flow and then applying the min-cut max-flow theorem.


Please explain "decidability" and "verifiability" I am trying to (intuitively) understand the two terms "decidability" and "verifiability".

I have done a reasonable amount of searching and going through the various texts I can put my hands on. However, their intuitive understanding seems to escape me, specially for the second one.

Out of the many definitions found, the following one found in this page, clearly explained decidability to me.

  A language is called decidable if there exists a method - any method
  at all - to determine whether a given word belongs to that language or
  not.

However, I fail to find a parallel definition for verifiability.

In the Theory of Computation book by Sipser, we find,

  P = the class of languages for which membership can be decided
  quickly.

  NP = the class of languages for which membership can be
  verified quickly.

In light of the above, I want to understand verifiability.

Please provide as many examples as you can, at one moment, I try catch the meaning, in the next one, I get confused again.

The key to understand here is that P and NP are classes of decision problems. That means that all of them have yes/no answers.

So when we say a problem like 3-SAT is NP-Complete, it means that given an instance of 3-SAT (aka a word potentially in the language), there is no known efficient way to test if the word is or is not in the language.

To say something is in NP means that there exists some sort of "proof" for each string in the language, which is polynomial in the length of the input.

For example, in 3-SAT, we're asking, does there exist an assignment of True/False to a set of variables in a boolean formula, such that the formula comes out to be true. The word we're testing is the boolean formula. There's no known way to find if there is a single solution that makes the whole formula true. But, if we have a set of true/false values for the variables, it's very easy to check (in polynomial time) if it causes the formula to evaluate to true.

The key point here is that the word we're testing is NOT the true/false values for each variable. The word we're testing is the formula containing the variables, and the language is the set of all boolean formulas which evaluate to true.

We don't know how to efficiently test if the word (formula) is in the language (can evaluate to true), but given a set of true/false assignments, we can verify if it evaluates to true i.e. it is a "proof" that the word (formula) is in the language.
Thus the problem is in NP, but not known to be in P.

NP is actually the class of non-deterministic polynomial solvable decision problems. This is because, in a non-deterministic turing machine, we have "decision" points where we can take one of multiple actions, and our polynomial certifier is basically just telling is which decision to take at each decision point.


How is the control unit affected by pipelining? Compared to not using instruction pipelining. What is different?

One, the control unit is pipelined. Two, because everything is pipelined, it's busy all the time and must be able to produce at least one instruction per cycle. Third, if you have a processor capable of executing more than one instruction per cycle, the control unit must be capable of handling more than one instruction per cycle, which includes decoding multiple instructions per cycle, preloading memory containing instructions before they are needed etc.


Unifying Accept States in NFA I recently read the first question and answer in this homework solution https://cseweb.ucsd.edu/classes/sp08/cse105/hw2s.pdf However, I am not sure if for example, you have two accepting states originally, one in which you leave the accepting state if you read 1 and the other in which you do not leave the accepting state no matter the input then how would one unite the two states. Your help is appreciated.

You can unite them exactly as said in the solution, "simply
add a new final state to the original automaton, add epsilon transitions from every old final state to the new final state, and change every old final state into a regular state."

Suppose $N$ is the original NFA at a final state $F$. Suppose it can go to one of states $E_1, \cdots, E_m$ without any input if there is an epsilon transition from $F$. Suppose on input symbols $s$, $N$ changes to one of states $S_1, \cdots, S_n$.

Let $N'$ with its unique final state $U$ be the new NFA as constructed above from $N$. When $N'$ is at its regular state $F$, what will happen?

It can stay at $F$ without further input.
It can go to any one of $E_1, \cdots, E_m$ as before because of the possible epsilon transition.
On input $s$, it will go to one of $S_1, \cdot, S_n$.
It can go to $U$ without any further input because of the epsilon transition from $F'$ to $U$.

Note that in case 2, 3 and 4 where $N$ has moved to state $s'\in\{E_1, \cdots, E_m, S_1, \cdots, S_n\}$, $N$ can move to another state without further input if there is epsilon transition from $s'$. Furthermore, $N$ can move to still another state without further input if there is still epsilon transition. And so on.

In particular, if $N'$ stays at $F$ on input $s$, it can go to $U$ without any further input.

Yes, an epsilon transition functions like teleporting magically.


The min cut capacity in a network based on a bipartite graph (Hall's Theorem) Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5,

  The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is $\text{Capacity}(S) = |L_2|+|R_1|+\text{edges}(L_1, R_2)$.

Here, $L_1 = S \cap L$, $L_2 = L \setminus S$, $R_1 = S \cap R$ and $R_2 = R \setminus S$. Furthermore, $L$ are the left edges and $R$ are the right edges.

I don't understand how he arrived at the conclusion that

  number of edges that go from $S$ to $\overline{S} = |L_2|+|R_1|+\text{edges}(L_1, R_2)$

I don't understand the meaning of this expression. I drew it out on paper (highlighting all graph elements of the expression) and I still don't get it. Could somebody please explain to me how this expression is generated in simple and detailed terms?

The flow network $G'$ is constructed from the original bipartite graph $G=(L,R,E)$ by adding two new nodes $s,t$, connecting $s$ to all nodes in $L$, connecting all nodes in $R$ to $t$, and orienting all edges in $E$ from $L$ to $R$. And $s$-$t$ cut in $G'$ has the form $(S,\overline{S})$ where $s \in S$, $t \in \overline{S}$. The edges crossing the cut are:

Edges from $s$ to $\overline{S}$, that is, from $s$ to $\overline{S} \cap L$. There are $|L_2|$ of these.
Edges from $S$ to $t$, that is, from $S \cap R$ to $t$. There are $|R_1|$ of these.
Edges from $S \setminus \{s\}$ to $\overline{S} \setminus \{t\}$, that is, from $S \cap L$ to $\overline{S} \cap R$. There are $\mathrm{edges}(L_1,R_2)$ of these.

It is crucial that in $G'$ the edges are oriented, and that when counting edges crossing the cut $(S,\overline{S})$, we only count edges going from $S$ to $\overline{S}$.


Is there a polynomial time algorithm for this decision problem? Is there a factor in $M$ that is $>$ $1$, but $<$ $M$ that is NOT a factor of $N$?

False Result Example

$N$ = 8

$M$ = 16

1, 2, 4, 8, 16

There is no integer that is NOT a factor of $N$ that is $>$ $1$ but < $M$

True Result Example

$N$ = 2

$M$ = 26

1, 2, 13, 26

There is an integer $13$ which is NOT a factor of $N$ that is > 1 but < $M$

Question

I have found a pseudo-polynomial solution, but is there a polynomial solution for this problem in the length of input?

This is hard as the integer factoring problem (simply take $N$ to be 2 or a random prime that has no factor in common with $M$).  Whether there is a polynomial-time algorithm for factoring is a famous open problem, but it is widely believed that there likely is no such algorithm.


Poly-time reduction: D and D Comp Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function.

I will define its complement for further clarity, does every subset such that its size is at least $k$ in $V$ contain at least one edge between its vertices? My intuition is below.
$$f(G, k) = (G, i-k),$$
where $i = |V|$?

Independent set and its complement are NP-complete and co-NP-complete, respectively. If you found a polynomial-time reduction between those two problems, you'd have proven that NP$\,=\,$co-NP, resolving one of the biggest open problems in theoretical CS.


Proof any CFG can be converted to GNF I studied algorithm for converting grammars to GNF and was wondering about
a proof that any CFG can be converted into GNF. I found this paper - ENGELFRIET, Joost. An Elementary Proof of Double Greibach Normal Form, 1992, but I do not understand the proof at all.

Any CFG can be converted into CNF, so we try to prove that any grammar in CNF can be converted into GNF.

At first, a grammar H (not GNF, but can be easily converted into GNF by substitution and by removing rules containing empty string) is constructed from original CNF denoted G as follows:

  1) for rules Y → a
   $$ A \rightarrow  a[Y,A] $$
  2) for rules C → DQ $$ [D,  A] \rightarrow  Q[C,  A] $$
  3) $$ [A,  A] \rightarrow \epsilon $$

Than there are mentioned two statements about this new grammar. These statements are essential for the proof, because they show that the grammar H is equivalent to G. And I do not know why they are right:

  $$
([Y,A] \rightarrow^*_H w) \iff (A \rightarrow ^*_G Y w)
$$
  and
  $$
(A \rightarrow^*_H w) \iff (A \rightarrow ^*_G w)
$$

There is also written that these statements can be shown by induction. I tried to prove them but it seems to me that to prove one of them, I also need to prove the second. So I am stuck at cycle.

Could somebody please explain it to me?

The textbook proofs of Greibach NF I have seen, contain endless substitutions. This way to construct GrNF is much crisper.

The key is to understand what the nonterminal $[Y,A]$ actually represents.
It means a derivation that has a leftward "backbone" which starts from $A$ and ends just before $Y$, as in the picture below.

Now the first production in $H$ can be explained as follows. If I start with $A$ and want to produce GrNF then I must generate a terminal. We choose to generate the leftmost terminal $a$ of the subtree under $A$. So, we produce $a$, but we still must find a derivation $[Y,A]$ of the form in the picture, where $Y$ is the nonterminal that actually produces $a$ using the available production $Y\to a$.


BigO, Running Time, Invariants - Learning Resources What are some good online resources that will help me better understand BigO notation, running time & invariants?

I'm looking for lectures, interactive examples if possible.

MIT OCW Introduction to algorithms video lectures
Design and analysis of algorithms stanford class


Is intersection of regular language and context free language is "always" context free language I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g.,
\begin{align*}
L_1 &= L(a^*b^*)\\
L_2 &= \{a^nb^n\mid n\geq 0\} \quad\text{(which is context free)}\\
L_1\cap L_2 &= \{a^nb^n\mid n\geq 0\}\,.
\end{align*}
But my question is what if the regular language is finite, such as
\begin{align*}
L_1 &= \{ab\}\\
L_2 &= \{a^nb^n\mid n\geq 0\}\\
L_1\cap L_2 = \{ab\}\,.
\end{align*}
Here intersection comes out to be finite and the language generated by intersection of both language is also finite which is regular (I know it's also context-free but regular is a stronger answer here).

What mistake am I making in understanding the concept?

The claim is that the intersection of a regular language and a context-free language is context-free. You've intersected a regular language ($\{ab\}$) and a context-free language ($\{a^nb^n\mid n\geq 0\}$) and the result was a context-free language ($\{a b\}$). Sure, that language is also regular but every regular language is also context-free. The statement isn't that the intersection of a regular language and a context-free language is a non-regular context-free language.
Analogously, the child of two mammals is a mammal. You've taken two mammals and you're saying, "Why is their child a cat? It's supposed to be a mammal."


Write a routine to print the numbers 1 to 6 and back to 1 again without using any loops Can anyone help with this question? I currently have this solution that prints

  1 2 3 4 5 6

but I'm having trouble going back down to 1.

public class noLoop{

     public static void main(String []args){
        noLoop(6);
     }

     public static void noLoop(int n) {

         if (n == 0) {
             return;
         }

         else {
             noLoop(n-1);
             System.out.println(n);
         }
     }
}

public class Foo {
    public static void main(String[] java_is_silly) {
        System.out.print("1 2 3 4 5 6 5 4 3 2 1");
    }
}