Why do we need so many transistors in a chip, and how are they managed? My knowledge is very vague as all we have are visual diagrams etc, but we have memory address and registers, the ALU being the heart(apparently). Single core CPUs process one instruction at a time AFAIK and multi-core have parallelism to some degree. So where do the millions of transistors come in and how do 32 registers manage everything. We have FPU's I know, how many transistors would these use roughly. Any way to get a fairly simple idea of what the bulk of the transistors do, why more means faster and how the registers 'manage' everything.

This is a huge question. To fully answer it would take far more space than you'd want to read (not to mention that I suspect that there's a limit on the length of any SE answer), but I'll try to give you an idea of what goes on in the CPU.

First, a transistor (when used in a CPU) is essentially a switch, like a light switch except that you don't have to turn it on or off manually. Rather, it is controlled by an electrical current. The most important thing to understand is that modern computers are two-state devices: the only thing that really matters is whether a wire has a current or not.

One then begins the process of chip design by, for example, deciding how an integer (or other data) will be represented. For integers, say, the chip designers generally decide to them by ganging wires together in a logical unit, so with a collection of four wires it would be possible to represent 16 possible patterns: $\mathtt{0000}, \mathtt{0001}, \dots \mathtt{1111}$, where a pattern like $\mathtt{1101}$ would represent a voltage in wires 1, 2, and 4, and no voltage in wire 3 and this collection might be interpreted as the number 13. In this example, we'd have what's known a a 4-bit chip. A modern computer would have either 32 or 64 wires treated as a unit.

It happens that with a suitably-connected collection of switches (aka transistors), one can do things like add two numbers, compare two numbers for equality, decide whether a number is zero or not, and so on. Often, all of these operations are often done at once, simultaneously, and the relevant one is chosen by the current instruction, which determines which of the various results to use, and where that result will be sent. All of this traffic control is also controlled by switches, depending on what the current instruction is (in the program being executed). In addition, things like memory and registers which store information can also be implemented by these switches.

To get a feel for the number of transistors used, an adder circuit in a $n$-bit computer might require about, say, $20n$ transistors, an $n$-bit register might require $50n$ transistors, and the traffic control circuitry to sent the results to the right place might require several hundred more for each bit. It's not hard to imagine that with a lot of functionality and a wide data path (the number of wires ganged together) a modern CPU could easily take millions of transistors.

As to why "more [transistors] means faster", the answer is "not necessarily", but in general, doubling the width of the data path, say from 32 bits to 64, gives you the ability to manipulate larger numbers in a single instruction at the cost of requiring more transistors.

Finally, the registers don't really "manage everything". A register is simply a very fast storage unit, capable of storing and retrieving information far faster than, say RAM memory. For that reason, things like the current instruction are often stored in a special register (called the instruction register), simply because access to its bits is very fast. The current instruction actually "manages everything", and it's stored in a register for speed.

This is a very abbreviated explanation---I've left out a ton of detail and glossed over a lot of technical matters, but I hope it at least gives you a sense of what goes on in a modern computer. [entering duck-and-cover mode in expectation of howls of complaints from computer engineers]

The simple answer is transistors are the basic components of logic gates, registers and storage devices. their various configurations make possible the or and not and flip-flops that comprise the higher order registers and processors. Look up the 7404 (not gate)7408 (and) and the 7432 (or gates). the basic 7474 and the 74279 are storage configurations. I am not  sure if national semiconductor still publishes the actual schematic but texas instruments does.


What's the purpose of the non-deterministic Turing machine? (*) Acronyms

NTDM := non-deterministic Turing machine.
TM := deterministic Turing machine.

(*) Consider the following idea

The NTDM is able to follow, in parallel, all paths of the tree of the universe of solution.  Suppose that in some point in time, for a certain problem, a new theorem is discovered that tells us that we need not worry about certain branches of the universe of solution because those branches yield no solution.  Then in some future point in time, a new theorem appears telling us we need not worry about some other branches of the tree and so on.  New theorems keep on being proved such that eventually there's only a single path to be followed in the tree of the universe of solution.  The problem therefore affords a polynomial solution since at every branch, it tells us where to go.

So the concept of NDTM accounts for all future scientific development.  Therefore, if a problem cannot be solved in polynomial time in the NDTM, then it's not in NP and therefore has no chance of being polynomial, no matter how science might advance.

This seems to be a good reason for the concept.  Is there any flaw in this argument?  In parallel, I'm interested in the question: why was the NDTM invented?

I will try to address why the concepts of NDTM and NP are useful, and possibly what motivated their study.

NDTM is one of many variants of turing mahcine. For example, the classical (deterministic) Turing machine can be equipped with multiple heads and tapes, randomness or quantum states. It can also be constrained by a limited alphabet, limited tape or pre-determined head-movements (see here).

A TM is said to decide a language (a set of words using a pre-defined alphabet), if it can halt on any input written on the tape, and accept precisely inputs belonging to the language. A language is called decidable if any TM decides it. Similarly, a function $f$ on natural numbers is said to be computable if there exists a TM which, given an input $n$, halts with $f(n)$ written on the input tape.

It turns out that all of the mentioned variations of TMs (including NDTM) are equivalent in the set of functions they can compute (similarly, the languages they can decide). This holds for other, much more different models than TMs, and has led to the Church-Turing thesis, which informally hypothesizes that any "reasonable" model of computation is equivalent to the classical Turing machine. In this aspect, NDTMs are useful as an example of fantastical computational models that are nonetheless as strong as a classical TM, supporting the Church-Turing thesis.

As far as I understand (see here and here for history), Turing himself did not focus on complexity classes, and so the previous reason might have been his sole motivation. However, later on it was discovered that different TM variants are not equivalent in the set of problems (languages and functions) they can solve in a certain amount of computation steps (time), bound on working-tape size (memory) and success probability. With this finer resolution, it turns out that the different models are very different, resulting in a zoo of complexity classes for problems.

I hope this is helps show why NDTMs (and the NP complexity class) are not a definite model for the problems science could potentially solve efficiently, but just one of many variations of computational models (less realistic than random and quantum machines, for example). There are, however, some reasons for why the specific class of nondeterministic polynomial time ($NP$) is such a popular attraction of the zoo:

It is relatively easy to explain and reason about. While researchers are working on many other open problems in complexity theory, the question of whether $P\neq NP$ requires only basic knowledge in math to understand, and the concept seems so intuitive that it invites many solution attempts from amateur researchers.
Whether a problem is solvable in polynomial time in a computational model is seen as an approximate measure of practical tractability (this is Cobham's thesis).
Any complexity bound derived by NDTMs can be seen as a bound on verification time by classical TMs (see here for why). Since classical TMs are used as models of practical computation, this has practical implications.
Many real-world important problems just happen to be not just in $NP$, but $NP$-complete. This means that if $NP$ is indeed a different complexity class than $P$, all of these important problems are not solvable in polynomial time with classical TMs.

Note that the fourth reason is unrelated to how realistic NDTMs are as a computational models (compared to classical TMs or other variants), or to any initial motivation for the invention of the concept. NP-complete problems are just surprisingly common in real life, and the scientific interest in them mirrors that.


Radon transform for advanced 3d graphics and games? The Radon transform is used to take 2d projections of an object and create a 3d representation.

It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly too slow to be practical).

For example, a very simple way to display an object is to use a 3d rectangle and texture map each side. This is relatively fast but the 3d detail is limited. When a side is parallel with the visual plane it will represent the detail 100% (so the visual detail would be limited to that of the texture map). Of course it won't represent external 3d effects properly, like lighting.

But by using the Radon transform one could gain a true 3d approximation of the object from the six textures/projections used. By increasing the number of textures/projections the approximation is better.

I'm curious if the idea has potential. Possibly for high-quality 3d models it might pay off in performance and size. Of course 3d models can be optimized to limit their size which also increases speed but visually doesn't change much.

I've been studying the use of OpenGL and DirectX and even though I am at an intermediate level, I believe this is where the use of bump maps, light maps etc comes into play. These are encapsulated in the idea of a Shader. The hardest part about the shader and lighting to work correctly with the 3D object with respect to the angle of the camera view directly depends if your normals are defined correctly. As for what you are describing it does make sense using 3D approximation, however my linear algebra is a little rusty, I am not sure if the conventional 4x4 matrices will work, and when it comes to motion with rotations you might have to redefine your quaternions too.


Turing machines without time steps? In "More Is Different," an article about reductionism in science, the author makes the following off hand remark near the end:

  I find that at least one further phenomenon seems to be identifiable and either universal or remarkably common, namely, ordering (regularity or periodicity) in the time dimension... [It] is noteworthy that all computing machines use temporal pulsing.

As far as Turing machines go, this is true since there is a fundamental "time step" during which a symbol is read, the state is changed, and the read/write head moved.  But this got me wondering: are there any non-Turing computing proposals without this fundamental time step?

There are various models of analog computation, which embody computations which neither involve discrete states nor times. One of the more studied models is what might be called "Shannon machines" (after Claude Shannon): the General Purpose Analog Computer (GPAC).

Shannon's original formulation of GPAC could not compute certain functions, including the Gamma function. However, a 2007 paper cited in that Wikipedia article provides a reasonable reinterpretation of GPAC which turns out to be more powerful, enough so that the authors claim that "the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals."

Claude Shannon is well-known as a pioneer in digital computer design and particularly for his foundational work on information theory, but his genius and sense of whimsy led him to extraordinary achievements in other areas, and analog computation remained an interest throughout his life. One example is his mathematical analysis of juggling, including the construction of a prototype juggling robot. (See here for more information and a brief video including the robot.)

The concept of sequentially performing one step after another seems to be inherent in our intuitive understanding of what constitutes an "algorithm", so it is present in one form or another in all useful models of digital computing. Even in a non-deterministic Turing machine, which can make multiple copies of itself at each step, each individual copy still executes its steps sequentially.

You can envisage a non-sequential "oracle" model which just "knows" the answer to every request/problem sent to it, and responds with that answer immediately - but that is not modelling what we understand an algorithm to be.


Algorithm for Estimating Number of Unique Monthly Visitors Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as simple as just multiplying the number of unique visitors the first week by 4, due to the hotel problem. If 10 people visit your site the first week and the same people are the only visitors to your site the second, third, and fourth week, the total number of monthly unique visitors to your site is only 10.
I know you can use HLL to estimate the number of unique visitors to a site in O(1) space. I'm wondering if there's a similar approach to estimate how many unique visitors there will be after a month, preferably that also works in O(1) space.

After digging into this for a bit, I came across this paper which provides a solution. The paper gives an approach to estimating the number of new species that will be observed given an initial sampling period. It models observing a given species as a Poisson distribution. It gives the following estimator for the number of new species that will be discovered:
$$
\hat{\Psi}(t)=\sum_{k=1}^{k_{m a x}} N_{k} e^{-k}-\sum_{k=1}^{k_{m a x}} N_{k} e^{-k(1+t)}
$$
where $N_{k}$ is the number of species that were observed $k$ times and $t$ is the length of the second sample relative to the initial sample.

Not without making assumptions.  You can't tell the difference between a site with a $N$ users who visit once a week (on a random day of the week), vs a site with $4N$ users who visit once a month (on a random day of the month).


How to solve linear equation with binary tree I'm working on a school project that takes in a simple linear equation and has to return the value of $x$. The code I have transforms $x + 3 = 3x - 2$ into a binary tree format like so:

        =
      /   \
     /     \
    +       -
   / \     / \
  x   3   *   2
         / \
        3   x

With the expression in this format could someone please explain how can I obtain the value of $x$.
Any help is appreciated - if you have an alternative method that may make it easier I'd love to hear it.

For solving this question you should assume a tree with '=' root
And in the left side of root push factors of x and in the right side push your constant values, now variable x is equal to sum of right side division by left side.


optimal testing strategy Here I have a problem in understanding the optimal testing strategy.

In a scenario, You have been given two laptop batteries and a testing device. The testing device will make the battery connected to it (one battery can be connected at a time) deliver x mA, where x is an integer. The testing device is constructed in such a way that the battery will always explode if there’s any risk of explosion at that current.

Now we want a program that receives inputs. Input consists of multiple lines, one line per case (at most 200 test cases). Each line contains a single positive integer n between 1 and 4711 inclusive, giving the current at which the battery is known to explode. Input is terminated by a line containing 0, which should not produce any output.

And produce Output, where for each case, print one line containing the worst-case number of tests to perform when using an optimal testing strategy.

|-----------------|------------------|
|  Sample Input   |  Sample Output   |
|--------- -------|------------------|
    1                0
    2                1
    10               4
    23               7
    0

This was a programming contest question marked as an easy question. but I do not get the definition of the optimal testing strategy.
What can be the boundaries? Generally what this question means?

in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense.

This is the famous two egg problem where

  You are given two eggs and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

The question is badly posed, either because the person posing the question isn't very good at writing English, or because you copied or paraphrased it badly. As asked, we have no idea what "an optimal strategy" is or what it is supposed to be. The crux of the problem is in "giving the current at which the battery is known to explode" instead of "giving a current at which the battery is known to explode". And of course "will always explode if there’s any risk of explosion at that current" is more than problematic.
In the "two egg problem" the optimal strategy is obviously one that minimises the number of stairs that I need to climb, which is likely to invalidate most answers that you find.
In case of the battery, I'd investigate how long it takes until the battery explodes, how much money the tester is paid per hour, and what the cost of an exploding battery is, and determine the optimum strategy from this information.


O(n) sorting array by value - get indexes I am in search of a linear-time sorting algorithm that is capable of returning an array B of indices A, sorted on the value of the corresponding element of A.

For example:

Input = [2, 6, 8, 9, 1, 7, 0]
Output = [6, 4, 0, 1, 5, 2, 3]

Things I have tried:

Storing the index and value in one number, using something like this:

long number = value << 16 | index;

And then applying Countingsort. This however did not work since the JVM couldn't handle an array of ~ 2 million elements. (= the highest "number" value).

The logical solution to that problem was put everything in a map, but I was unsure whether it would still be linear..

Every problem can be solved with yet another indirection:

First create B as an array of self-indexes - i.e set B[i] = i for all i.  Next create a 'comparator' object around A, which compares integers i and j by actually comparing A[i] with A[j].  Now sort B using this comparator.

Assuming you can sort the elements in A in linear time (e.g. they're smallish integers), you can produce an array of indices by sorting tuples of $(a,i)$ where $a$ in an element from A and $i$ is its index

index_sort(A):
    B = []
    for i in 0 to length(A):
        append (A[i],i) to B
    sort B in linear time, considering only the first component of the tuples for the ordering
    C = []
    for i in 0 to length(A):
        let (a,j) = B[i]
        append j to C
    return C


How do I do sum of first k elements of a row of a Pascal's Triangle efficiently? More specifically, I want to:

$^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$

I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j.

The answer it gives is correct for small numbers. Since n and k can be large, I need have keep modding with P, a given prime number.

My method fails since I have to divide with j, which breaks the mod.
Any suggestions?

Your method is fine.  You just need to know how to do modular division.  Modular division is a bit different from division of two integers.  You can do modular division, say $x/y \bmod p$, by computing computing the modular inverse of $y$, $y^{-1}\bmod p$, and then multiplying that by $x$.  You can compute the modular inverse using the extended Euclidean algorithm.

See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.

A slight correction:

$${n \choose j+1} = {n \choose j} \times {(n-j) \over j+1}.$$

You had an off-by-one error in the formula.  To do this modulo $p$, replace dvision by $j+1$ with multiplication by the modular inverse of $j+1$ modulo $p$.

One interesting fact about Pascal's triangle is that each rows' numbers are a power of 11. For instance, the first row is 11 to the power of 0 (1), the second is eleven to the power of 1 (1,1), the third is 11 to the power of 2 (1,2,1), etc. This identity can help your algorithm because any row at index n will have the numbers of 11^n. Then, using something like a "to_string" conversion in C++ or the "read" function in Haskell, you can select the amount of numbers you would like to sum over in your string of numbers, convert them back to an integer, and then sum over them.
Here is some pseudo-code to help illustrate my answer:

    int n = 7
    int k = 5
    int full_row = pow(11,n)
    string str_full_row = to_string(full_row)
    int sum=0
    int index=0
    for string i in str_full_row:
        index+=1
        sum+=(string_to_int(i))
        if index==k:
            break

In this case, the answer is the "sum" variable, and you don't need to use the nCr trick above. The "n" variable is the row, the "k" variable is the amount of terms within the row that you want to sum over (and it starts at 0), and the "index" simply keeps track of the the number of iterations that have happened within the for loop.
I hope this helps!

EDIT: Having reviewed the answers below, I see that there is an obvious mistake for rows in which the numbers within the row are double-digit or beyond. I do not know how to correct this.


What is complement of Context-free languages? I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I can say that complement of CFL is included in P(right?). There is still a question whether complement of CFL is proper subset of P or the whole P. I would appreciate any ideas on how to show that complement of CFL is the whole P(if that's the case of course).

One can understand your question in two ways, according to the definition of "the complement of CFL".

case A: Complement of CFL is the class of all the languages that are not in CFL.  Formally, $$\overline{CFL} = \{ L \mid L\notin CFL\}.$$
In that case, $\overline{CFL}$ is way bigger than $P$, it even has languages that are not in $R$, etc.
But maybe that's not what you meant.

case B: Define the complement-CFL class as $$co{CFL} = \{ \bar{L} \mid L \in CFL\},$$
in words, the set of all languages $L$, such that $L$'s complement is context free.

In that case, what you wrote makes sense:
$CFL \subsetneq P$  (by the CYK algorithm), and also $co{CFL} \subseteq P$ (run the same algorithm, output the opposite answer), and since $CFL \neq co{CFL}$,
then it should be immediate that $co{CFL}\subsetneq P$, right?

Complement of CFL could possibly be CFL but not necessarily is.
Complement of CFL is both recursive (R) and recursively enumerable
(RE). Why? All CFLs are both R and RE. R languages are closed under
complement (but RE are not). In that context, complement of CFL is R
which is inherently RE.


Relationship between Independent Set and Vertex Cover Directly from Wikipedia, a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover.

Does this imply that the complement of the independent set problem is the vertex cover problem?

Well, strictly speaking it's not the complement; co-VC is co-NP-complete whereas Independent Set is NP-complete.  If they were the same, we would know that co-NP was equal to NP, which we do not, and indeed most people believe they are not.

But an easy way of seeing that they are not the same if to consider $(K_4, 2)$, the complete graph on four vertices) which is neither a yes-instance of Vertex Cover nor of Independent Set.  Similarly, the instance $(K_2,1)$ is a yes-instance for both.

However, they are related in the following way.
A set of vertices $C \subseteq V(G)$ of a graph $G$ is a vertex cover if and only if $V(G) \setminus C$ is an independent set.  This is easy to see; for every endpoint of an edge, at least one vertex must be in $C$ for $C$ to be a vertex cover, hence not both endpoints of an edge are in $V(G) \setminus C$, so $V(G) \setminus C$ is an independent set.  This holds both directions.

So $(G,k)$ is a yes instance for Vertex Cover (a minimization problem) if and only if $(G,n-k)$ is a yes instance for Independent Set (a maximization problem).

You may check out this link:

http://www.hananayad.com/teaching/syde423/IndependentSet.pdf

According to this one, both are equally hard (NP-complete), however, optimization version of each problem is NP-hard.


Least number of comparisons needed to sort (order) 5 elements Find the least number of comparisons needed to sort (order) five elements and
devise an algorithm that sorts these elements using this number of comparisons.

  Solution: There are 5! = 120 possible outcomes. Therefore a binary
  tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$
  ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number
  of comparisons needed to sort (order) five elements is 8.

Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it can't be done in 7 comparisons?

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance.

The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline:

Sort the first two pairs.
Order the pairs w.r.t. their respective larger element.

Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.
Insert $e$ into $[a,b,d]$.
Insert $c$ into the result of step 3.

The first step clearly takes two comparisons, the second only one. The last two steps take two comparisons each; we insert into a three-element list in both cases (for step 4., note that we know from $c<d$ that $c$ is smaller than the last element of the list at hand) and compare with the middle element first. That makes a total of seven comparisons.

Since I don't see how to write "nice" pseudocode of this, see here for a tested (and hopefully readable) implementation.

Ph.D. thesis (Stanford University) by H.B. Demuth (1956)

See also Electronic Data Sorting by H.B. Demuth (1985)
Sorting and Searching
by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)

If you can test algorithm, test it on all number combinations.
If you have lot of number, test on lot of random combinations. Not precise, but faster than all combinations.

Minimal
a < b < c = 2
a < b < c < d = 3
a < b < c < d < e = 4

Maximal
3^3
4^4
5^5

Insert to middle use 3-6 for 4 numbers.
Merging use 4-5 for 4 numbers.
Minimal compare by wiki is 5 for 4 numbers :) For 5 is 7. You use 8, still so much.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
If you know all before comparations, you can go down with comparations. My average for 4 numbers is 3.96 / 1024 all combinations.


Shortest non intersecting path for a graph embedded in a euclidean plane (2D) What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)?

For example, in the graph below, you want to go from $(0,0) \rightarrow (-3,2)$. Normally, an algorithm like Dijkstra's algorithm would produce a sequence like:

$$\left[ (0,0) \stackrel {3}{\rightarrow} (0,3) \stackrel{\sqrt{2}}{\rightarrow} (1,2) \stackrel{4}{\rightarrow} (-3,2) \right] = 7+\sqrt{2}.$$

Full graph:

Shortest path:

Shortest non-intersecting path:

However, this path intersects itself on the euclidean plane, therefore I want an algorithm that would give me the shortest non-intersecting sequence, in this case:

$$\left[(0,0) \stackrel{3}{\rightarrow} (0,3) \stackrel{3}{\rightarrow} (0,6) \stackrel{5}{\rightarrow} (-3,2) \right] = 11.$$

This path is longer than the shortest path, but it is the shortest non-intersecting path.

Is there an (efficient) algorithm that can do this?

TikZ sources

Full graph.
Shortest path.
Shortest non-intersecting path.

It is NP-complete to even decide whether any path exists.

It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem.

Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem:

The global structure is a grid of wire pieces adjoined by a column of clause pieces. Logic formula is satisfiable iff there exists a non-intersecting path through the graph.

It is impossible to cross two pieces of the path, but it is neccessary to cross two logic wires. Rather, the path flow is strictly given: a wire point is given by two nodes. The sequence of the wire points through which the path passes is forced by the reduction. Logic is represented by which node is chosen. Any path can be chosen as long as it passes through all wire points.

In this diagram, the path is represented by the red curve and the logic flow is represented by the black wires:

Now let's build each component.

Wiring uses three tiles: the crossing, the branch point, and the vertical wire. Let's start with the hardest one:

The basic idea behind the crossing is to prepare a path for each pair of wire points and bend the possible paths enough so that all pairs except those that encode the same logic (compatible paths) cross each other. Of course we can't just say two parallel edges intersect, but we can introduce extra order-2 nodes to make two paths intersect.

Supposing the paths come from north to west and from south to east, we can: collect each path from north with its compatible path from east on a line (some incompatible paths will cross each other); cross each pair with each other by reversing the order of pairs; distribute the paths to their south and west endpoints. This is best explained by a diagram. Here, each pair of nodes represents a wire point. Paths with the same color code (carrying the same logic) don't intersect, paths a different color code do:

The branch point and the vertical wire work the same, but there are fewer paths to correlate:

The clause box follows the same logic: each literal exposes one of its paths to the reading wire, then converging to the south (if it's the northernmost term or the term to the north converges to the north) or to the north (if the term to the north converges to the south). The reading wire (one node at the endpoints) branches to become one path per literal. Each reading path then crosses the literal's true-path if the literal is negated, the false-path if it is not. Note that the converged path may or may not cross a clause boundary. For consistency, here's a diagram for $\neg A \vee \neg B$:

It is possible to generalise this reduction to encode an arbitrary tree of AND and OR gates by branching the reading wire in different way. In particular, SAT-CNF and SAT-DNF are both possible to reduce to the non-intersecting path problem in the way described as above.

the problem seems to date to Turan 1944. this looks like a good survey of theory and algorithms, the Crossing Number of Graphs: Theory and Computation by Mutzel. wikipedia has some info under crossing number of graphs


Is a kind of reverse Kleene star of a context-free language context-free? Recently I had a question on one of my assignments asking to prove or disprove the following:

Let $L$ be a language. If $L^*$ is context-free then $L$ is context-free.

Now obviously this is false since we can take some non-context free language $L_1$ and the alphabet $\Sigma$, then make $(L_1 \cup \Sigma)^* = \Sigma^*$ is context-free and clearly $L_1\cup \Sigma$ is not.

Now I was thinking about a similar problem but now with respect to the words in the language, and was wondering if it is true or not. If $C$ is a context-free language then $C'$ is a context-free language where $w\in C'$ if and only if $\{w\}^*$ is contained in $C$.

My suspicion is that this is also false, but I can't come up with a counterexample. Somehow one needs to construct a CFL $C$ such that the subset of all the "periodic" words of $C$ together are not context-free.

Let me solve a simpler question first. Suppose we'd like to know

  If $C$ is context-free, must $F(C)=\{w: ww \in C\}$ be context-free?

The answer is no: $F(\{a^i b^i c^j a^j b^k c^k\})=\{a^i b^i c^i\}$.

As for the original problem, consider the context-free language that contains words of the form $\{a^i b^i c^j d a^j b^k c^k d\}$ or those which don't contain exactly two $d$'s.

Define $D=\{w: w^\ast \subseteq C\}$. Suppose $D$ is context-free. Then $E=D\cap a^\ast b^\ast c^\ast d$ is context-free.

I claim $E=\{a^i b^i c^i d\}$, which is not context-free. Suppose $w = a^i b^j c^k d$. We have $w \in E$ exactly if $w^n \in C$ for every $n$. This condition is clearly satisfied when $n \neq 2$, because $w^n$ will not have exactly two $d$'s. For $n=2$, $w w=a^i b^j c^k d a^i b^j c^k d\in C$ which is equivalent to $i=j=k$.

Take the language $L = \{a^{n^2} \colon n \ge 1\}$, it is easy to prove non-regular (and non-context-free). However, $L^*$ is the language denoted by $a^*$, which is regular (and thus context free).


Are there any problems that get easier as they increase in size? This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size?  I doubt any practical problems are like this, but maybe we can invent a degenerate problem that has this property.  For instance, perhaps it begins to "solve itself" as it gets larger, or behaves in some other bizarre way.

No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$.

Let $T(n)$ be the best possible running time for solving such a problem, where $n$ is the size of the input.  Note that the running time is a count of the number of instructions executed by the algorithm, so it has to be a non-negative integer.  In other words, $T(n) \in \mathbb{N}$ for all $n$.  Now if we consider a function $T: \mathbb{N} \to \mathbb{N}$, we see there is no such function that is strictly monotonically decreasing.  (Whatever $T(0)$ is, it has to be finite, say $T(0)=c$; but then since $T$ is monotonically strictly decreasing, $T(c) \le 0$ and $T(c+1) \le -1$, which is impossible.)  For similar reasons, there is no function that is asymptotically strictly decreasing: we can similarly prove that there's no running time function $T(n)$ where there exists $n_0$ such that for all $n \ge n_0$, $T(n)$ is monotonically strictly decreasing (any such function would have to become eventually negative).

So, such a problem cannot exist, for the simple reason that running times have to be non-negative integers.

Note that this answer covers only deterministic algorithms (i.e., worst-case running time).  It doesn't rule out the possibility of randomized algorithms whose expected running time is strictly monotonically decreasing, forever.  I don't know whether it's possible for such an algorithm to exist.  I thank Beni Cherniavsky-Paskin for this observation.

The question asks: "is it possible to have a problem that actually gets easier as the inputs grow in size?" What if the inputs are resources to be used by the algorithm to work on a job. It is common knowledge that the more the resources the better. Below is an example, in which the more there are employees the better.

1) You are given two inputs:
i) The number of employees in an industry. This is a natural number and is the main input $n$.
ii) Information about the industry. There are $t$ tasks to be done by the workers, labeled A, B, C, D... There are $p$ places that connect the tasks enabling the employees to switch between tasks. They are labeled 0, 1, 2, 3... The information given is a simple directed graph made up of routes, for example: A-1, 1-2, 2-B, C-3... For simplicity each route has a cost of 1.

2) Problem:
Starting from the first tasks A, and with $n$ employees, you are to find an optimal strategy for the employees to use in order to visit all the tasks. Tasks can be visited more than once. Recall that you cannot switch between tasks unless you find a path between them. The path from task A to B is independent of that from B to A.

3) Output:
The output is the paths between tasks to be taken by the employees. Each path is associated with the number of employees taking it. For example:

A to B with $n1$ employees (a forward path)
A to C with $n2$ employees (a forward path)
B to D with $n3$ employees (a forward path)
D to B with $n4$ employees (a reversed path)
B to E with $n5$ employees (a forward path)

4) Possible solution:
One possible solution is to first compute the shortest path to the closest nodes from A. This will be a forward path. Then recursively compute the forward path for each visited tasks. The result is a tree. For example:

          A
      B      C
    D   E

Now is the time to determine how the employees are going to traverse the tree so to visit the tasks. Starting from task A with $n$ employees, $n1$ are sent to the left subtree and $n2$ are sent to the right subtree. If $n2 \neq 0$ then none from the left subtree will ever need to go to the right subtree.

For $n=\infty$ the employees will all just move forward. For $n = 1$ the employee will have to use reverse paths in order to visit other tasks. For D to B for example the algorithm will compute that shortest path. This is extra computation. Why not directly compute a shortest path from D to E?! Fine, hopefully that is still extra computation.

But of course computation time will not decrease infinitely (by the way for $n$ too large it will lead to poor resource management and stuff).


What are the gates used to implement Shor's algorithm? I understand theoretically how Shor's algorithm works, but I don't know what specific gates are used (or would be used) to implement it. What would the quantum circuit look like?

There are several correct answers to this question because there are several candidate sets available for use as a universal set of quantum operators and because there isn't an agreed upon best implementation for the primitives needed by Shor's algorithm. Different circuits will trade-off circuit-depth for ancillary qubits and vice versa.  Ultimately, the exact implementation is likely to depend on the architecture of the quantum computer.

What that in mind, you can probably find a version of the details you're looking for in Fast Modular Exponentiation Architecture for Shor's Factoring Algorithm by Pavlidis and Gizopoulos.  The exact circuit layout is lengthy and complex and probably too much for an answer here. The paper has lots of diagrams though and a quick scan should should provide you with a rough feel for the circuit construction. Unsurprisingly, the circuit makes heavy use of Hadamard gates and controlled phase-shift operators both to implement the inverse QFT and the modular exponentiation circuit.

According to quantumplayground.net shor's algorithm uses some swaps, hadamards, measuerments, and Inverse Quantum Fourier Transform gates.

check it out yourself:
Shor's Algorithm


Proof that total computable functions are not enumerable In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made:

  Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all total computable functions from N to N, such that every $f_e$ was total, then $g(i)=f_i(i)+1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

I really don't understand why

  then $g(i)=f_i(i)+1$ would also be a total computable function

Indeed if $g$ was a total computable function, then $\exists k, f_k=g$, so that $g(k) = f_k(k) + 1 = g(k) + 1$, which is impossible.

So it seems to me that building $g$ is impossible, so that we cannot reach a contradiction by saying that we have built another total computable function which is not in our enumeration.

I tried shifting the diagonal to avoid this effect, but other loops of the same kind can't be ruled out.

$g$ is total computable by definition.

By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable.
$1$ certainly is.
$+$ certainly is.
The concatenation of $+$ and $f$ is computable by construction, and that's $g$.

The details depend on the exact definition of "computable" (i.e. the machine model) you use; see e.g. here.

So under the assumption that such $f$ existed, $g$ is computable; therefore, it must have an index in $f$, which is impossible (as you note); therefore, the assumption must be false.

The answer is that you have found a legitimate problem with these naive proofs by diagonalisation. In practice, diagonalisation cannot be applied to computational theory. Diagonalising is only possible in the fantastical land of actually infinite sets. There are no such things in the world of computation.
The problem is this:
It is impossible to build a machine g case by case, because we would require an infinite number of cases, and the description of g would grow in length forever.
However, to define g differently to any total computable function requires that g itself is not a total computable function, otherwise it would be different to itself! But we cannot begin by assuming what has to be proven.
$g(i)=f_i(i)+1$ is not a definition. It is a property. It means "define g of i such that ..."
Unless a procedure can be legally described which computes g, then this property is meaningless in the world of computation. The reason that functions with such properties can be assumed to exist in the fantastical world of actually infinite sets is because the Axiom of Choice allows them to choose elements from every set in an infinite set all at once. Obviously in the finite world of computation, this is impossible.
Finally, I would like to point out that Turing, in his original 1936 paper does not give such a stupidly naive argument for the existence of uncomputable real numbers. His proof is much more complex, precisely because he was aware that direct self-reference such as this must be avoided.


Test if there are two subsets which cover a set Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.

Brute force would take time $O(nm^2)$ but is there any way of solving this more efficiently?

There is an $O(n2^n)$ algorithm which is better than the trivial $O(nm^2)$ algorithm when $m$ is really big. Let $f$ be the characteristic vector of $\mathcal{X}$, of length $2^n$; $f$ can be calculated in time $O(n2^n)$. The number of solutions $U,V$ is exactly equal to
$$ f' \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f. $$
Indeed, if $\chi_U$ is the indicator vector of $U$ then
$$ \chi'_U \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} \chi_V = \begin{cases} 1 & \text{if } U \cup V = S, \\ 0 & \text{otherwise}. \end{cases}$$
The vector $g = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f$ can be computed in time $O(n2^n)$ using an FFT-like algorithm, and then the inner product $f'g$ can be calculated in time $O(2^n)$. I'm lying a bit here: the numbers involved might get big. However, if we replace addition with OR, we still find out whether there are any solutions, and all the numbers are in $\{0,1\}$ now.

The function $g$ is in fact related the upward closure of $f$, which is given by $h_U = g_{\overline{U}}$. The FFT algorithm uses the basic operation $h_{U \cup \{i\}} = h_U \lor h_{U \cup \{i\}}$. This makes it clear why $\bigvee_U f_U g_U = \bigvee_U f_U h_{\overline{U}}$ is what we want.

A solution to this problem is the two subsets $U$ and $V$ from $\mathcal{X}$. If we know $U$ upfront, we can answer this question in $O(n*m)$.

So let us examine the case where we would have a unique $U$, this happens when there is an element $a \in S$ is covered only by $U$. We can check this possibility in $O(n*m)$.

Afterwards, we can find $V$ through brute force in $O(n*m)$. If we don't have this possibility, I am not sure whether we can solve it more efficiently.


A language in NSPACE(O(n)) and very likely not in DSPACE(O(n)) Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\mathbf{CFL}$ (context-free languages).
And also the open problem $\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$ is not so famous as the "analogous" problem: "$\mathbf{P} =^{?} \mathbf{NP}$".

Well, is there really such an analogy:?

Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE(O(n))}$  (like $\mathbf{NP}$ complete languages)?
Moreover: Is there a language $L$ in $\mathbf{CSL}$ which is "complete" in the following sense: if we can prove that $L$ is in $\mathbf{DSPACE(O(n))}$ we get that $\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$?
(Maybe just a matter of opinion) Are both problems on the same level of difficulty?

The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$, and so $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ implies the well-known conjecture $\mathsf{L} \neq \mathsf{NL}$.

The conjecture $\mathsf{L} \neq \mathsf{NL}$ is considered (by some) to be more approachable than the conjecture $\mathsf{P} \neq \mathsf{NP}$. I'm not sure many people have an opinion on the conjecture $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$.

The bigger picture here is whether Savitch's theorem, which states that $\mathsf{NSPACE}(t(n)) \subseteq \mathsf{DSPACE}(t(n)^2)$ for reasonable $t(n) \geq \log n$, is tight. While $\mathsf{NPSPACE} = \mathsf{PSPACE}$, I think that most people believe that $\mathsf{NSPACE}(n^k) \neq \mathsf{DSPACE}(n^k)$. On the other hand, I'm not sure that people believe that $t(n)^2$ is the optimal blowup; perhaps a smaller exponent also works, at least in some cases. See for example a recent arXiv paper, The parameterized space complexity of model-checking bounded variable first-order logic, by Yijia Chen, Michael Elberfeld, and Moritz Müller.

$SAT$ is in $NTIME(n) \subseteq DSPACE(n)$. Under the assumption of $L = P$, then $NP$ is strictly contained in $DSPACE(n)$ since we can transform polynomial time reductions into logarithmic space reductions and $DSPACE(n)$ is closed under logarithmic space reductions. They are not equal due to the Hierarchy Theorem. However, when $L = NL$ then $DSPACE(n) = NSPACE(n)$ as result of applying the padding argument. Since $L = NL$ when $L = P$ then $NP$ is strictly contained in $NSPACE(n)$. However, $CSL = NSPACE(n)$ and thus $CSL \neq NP$ and hence, there could not be the case that some $CSL-complete$ problem is in $NP$ because that would imply a contradiction with $CSL \neq NP$ that we obtained after assuming    $L = P$.

In addition, you could see a possible attempt of proving $L = P$ here:

https://hal.archives-ouvertes.fr/hal-01999029


Context-free language and regular expressions I have the following context-free language:

S -> ASa | b
A -> aA | a

I don't understand why this is not regular. I first said that it's generated by the regular expression a+ba+. The following is regular however

S -> ASa | b
A -> aA | e

e stands for the empty string. I don't understand their differences.

The subtlety is that in the first case, the number of $a$'s before the unique $b$ must be at least the number of $a$ after, i.e. your language is $\{a^nba^m|n\geq m\}$, so it is not regular. This is because each $A$ produces at least one $a$.

In the second case however, this constraint disappears, and your language becomes indeed $b+a^*ba^+$ which is regular.

See, in the CFG grammar you need to store the value of n and m in order to compare the condition i.e. n>= m.So memory is required,preferably a stack.Whereas, in the regular grammar its either b or any string ending with ba. You don't need anything to remember to satisfy the grammar,as there is no such condition where you need to store the value.


p constant in pumping lemma for regular languages We have a language

$L = \{ a^{n^{2}}, n < 12\}$ We have to find minimum constant P for pumping lemma.

What does p represent here? I thought p in pumping lemma represent number of states , yet the right answer is $p >= 122$ , i would understand if it was $p <= 122$.

So for example it would be correct when $p = 155$. But how could we create such automat with 155 states?

The key here is that $L$ is a finite language.  Therefore it can be recognized by a DFA which has no cycles - in this case, a chain of 122 states, numbered 1 through 122, with transitions on $a$ from each state $i$ to state $i+1$ [except for a loop on $a$ from state 122 to itself], with states 1, 4, 9, ..., 121 being final.  For P=122, this automaton satisfies the Pumping Lemma - i.e all strings in $L$ of length at least P can be pumped - in a purely vacuous sense, because there are no strings in $L$ of length at least P.

From Wikipedia:

  for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y zero or more times are still in L.

So p has to be equal or greater than number of states. If you choose a word w with length < number of states, you will have no cycles in the path from initial state to final state determined by w, and then you can't find (for every division of w in xyz, with |xy|<=p and |y|>=1) a substring y which you can remove from w (or multiply as many times as you want) obtaining a new word w' in L.


Are there peer-reviewed papers studying the pros and cons of functional programming? Can somebody refer me to peer-reviewed papers studying the advantages or disadvantages of writing code in a functional style? Are there papers which discuss the applications of Lambda Calculus in fields such as Machine Learning, Language Design, etc.?

There is a famous paper "Why Functional Programming Matters" by John Hughes. The main argument of this paper is the modularity of functional programs.

Also, the work by Chris Okasaki about functional data structures is very interesting. The article "Red-Black Trees in a Functional Setting" provides a very clear implementation of red-black trees using functional programming language, which is much simpler than their imperative implementation in the book "Introduction to Algorithms" by Tomas H. Cormen et al.

a semifamous high quality, free reference in this area is Structure and intepretation of computer programs by Abelson and Sussman, MIT professors, some more info on wikipedia. they advocate functional programming as a way of understanding the theory and abstraction of programming such that understanding of functional programming will help one understand/apply the same principles in any language. they make some effort to discriminate it from/juxtapose it with what is called "imperative style" but without side-by-side comparisons.


Proving $\Omega(cf) = \Omega(f)$ I'm trying to prove the following lemma:

$c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that:

$\Omega(cf(n))$ = $\Omega(f(n))$.

I know that it is obvious but I'm trying to construct a proof that is as complete as possible. My current approach is like this:

This lemma is equivalent to saying that: $f(n) \in \Omega(cf(n))$ iff $cf(n) \in \Omega(f(n))$.

We can also restate that as:

If $t(n) \in \Omega(cf(n))$ then $t(n) \in \Omega(f(n))$.
If $t(n) \in \Omega(f(n))$ then $t(n) \in \Omega(cf(n))$.

For 1.,

$(*)$ $\exists d_1, d_2 \gt 0, \forall n \gt n_0, n_1, \forall n \in N$:

$t(n) \ge d_1cf(n)$ and $t(n) \ge d_2f(n)$

Now let's fix $d_1, d_2$ and $n_0, n_1$ to be any constants that fulfils $(*)$, such that:
$n'=max\{n_0, n_1\}$ and $d_1c \ge d_2$, using this we can say that:

$t(n) \ge d_1cf(n) \ge d_2f(n)$ and hence the 1. is satisfied because $t(n) \in \Omega(cf(n)), \Omega(f(n))$. The proof of 2. is mutatis mutandis.

Do I have a mistake in my proof, is there a better/more elegant way to prove this lemma? Shortly how can I improve this?

I think you're trying to take too many steps at once. Try to think about it one small step at a time.

Always think about:

What are the definitions I have available
What do I know already? What is proven?

Proving sets equal

Since you have two sets, $\Omega(cf)$ and $\Omega(f)$ and you want to prove them equal, you first need to think about what it means for two sets to be equal:

$$A = B \Longleftrightarrow A \subseteq B \land A \supseteq B$$

This tells you, that you need to show two things:

$\Omega(cf) \subseteq \Omega(f)$
$\Omega(cf) \supseteq \Omega(f)$

Proving $A$ to be a subset of $B$

For this, you need to apply the definition of $A \subseteq B$:

$$ A \subseteq B \Longleftrightarrow \forall a  \in A:(a \in B)$$

Nature of our proof

As you can probably see by now, our proof will have the following form:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf):\\
&\Rightarrow \dots\\
&\Rightarrow g \in \Omega(f)
\end{align*}
$$

The proof goes the same way for $"\supseteq"$.

Filling in the dots

Keeping this structure in mind, the path you need to follow is already laid out.

Using this definition for \Omega: $ \Omega(f) = \{ g |\, \exists\, n_0 \in \mathbb{N}, c > 0 \forall n \geq n_0: cf(n) \leq g(n) \} $

One direction of the proof could look as follows:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf): \\
&\Rightarrow \exists\, n_0\in \mathbb{N}, c'>0: c'cf(n) \leq g(n)\ \ \forall n \geq n_0 &\text{definition of } \Omega\\
&\Rightarrow \exists\, d>0,  n_0\in \mathbb{N}: d f(n) \leq g(n)\ \ \forall n \geq n_0 &\text{Let } d=c'c\\
&\Rightarrow g \in \Omega(f) &\text{definition of } \Omega
\end{align*}
$$

My opinion is that the $=$ sign should be interpreted as $\subset$ in the asymptotic complexity context. Consider the case when we write $n^2=\Omega(n)$. This is mentioned in CLRS's "Introduction to Algorithms", page 49.

Another point is that considering the definition of $\Omega$, it naturally hides constant coefficients inside, so you can show the "equality" easily by stating $c_2=c\cdot c_1$, defined as follows:

$\Omega(f)=\{g|∃n_0∈N,c_2>0∀n≥n0:c_2f(n)≤g(n)\}$,
$\Omega(cf)=\{g|∃n_0∈N,c_1>0∀n≥n0:c_1\cdot cf(n)≤g(n)\}$.


Spotting the difference between two arrays using divide-and-conquer Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.

For simplicity, assume we can use two subroutines that can sum any subarray in our first and second arrays, respectively.

How would we use this to find a suitable algorithm using a divide-and-conquer approach? And if so, how many times would it have to call the subroutines? I assume we can start by dividing our arrays into two and solving our problem recursively from there.

Compute sums for the first two halves of the arrays, if they agree, the difference (if any) is in the second halves. If they don't agree, check first quarters, and so on.

You could just compare the values in a loop, which is trivial and works just fine. And we are now arguing about constant factors.

Consider how many array elements you read if the first two items are different (answer: n items from each array). Quite inefficient.

As a micro-optimisation adding k elements and comparing the sum would often be faster than comparing k elements. You could in a loop compare sums of k elements for some small fixed k.

Of course this only works if your guarantee (“exactly one item different”) is true, and the items are small integers so there is no overflow or rounding error. So just go with a straightforward loop unless speed is essential.


A tentative satisfiability algorithm General satisfiability (with a few exceptions such as Horn Clauses) is not believed to have an algorithmic solution. However, the following algorithm appears to be a solution for general satisfiability. What exactly is the flaw with the following algorithm?

Let $W$ be an empty set which will contain all variables that necessarily have to be true or false.
Let $L$ be the set of clauses.
Loop through $L$.
Every time a non-conditional variable† is found, remove it from $L$ and insert it into $W$.
If this leaves an empty AND implication‡, remove all variables in that empty implication from $L$ and insert into $W$.
If this leaves an empty OR implication‡, create new instances of the algorithm, where each instance deals with one variable in the implication (i.e. if the implication is: $x V \implies y$, create one instance where $x$ is inserted into $W$, one where $y$ is inserted into $W$ and one where $x$ and $y$ are inserted into $W$).
Set all variables in $W$ to the value they necessarily have to be.
Reinsert the variables in $W$ in $L$ with their changed values and check if all clauses  are satisfied.
If satisfiability is met, then return $L$, else return "Not Satisfiable".

† A non conditional variable is defined as a variable that is necessary true or false, e.g. $\implies x$ or $\implies \neg y$.

‡ An empty implication is defined as an implication where one side is empty (e.g. $\implies x \wedge y$) or the other side is necessarily true (e.g. $\mathrm{true} \vee a \implies b$.

To get a more intuitive understanding of the algorithm consider the following set of clauses $L$:

$$\begin{align}
  a \wedge b &\implies c & \text{(i)} \\
  &\implies f \wedge g & \text{(ii)} \\
  f &\implies \neg a & \text{(iii)} \\
  f \vee a &\implies b & \text{(iv)} \\
  &\implies c & \text{(v)} \\
\end{align}$$

The algorithm will do the following:

1) Since $c$, $f$, $g$ are non-conditional variables, the algorithm will insert them into $W$. $W = \{c, f, g\}$.

2) Removing $c$, $f$ and $g$ will leave the empty clauses: $\implies \neg a, a \wedge b, b$. These will be added to $W$. $W = \{c, f, g, b, \neg a\}$.

3) Reinserting the variables into $L$ will result in the first clauses being violated: $a \wedge b \implies c$. Since $a$ is false, $c$ is false, meaning clause (v) is violated. The algorithm will return "Not Satisfiable"

I am aware that the algorithm appears confusing. Please feel free to ask for clarification.

From comments I now realize that there is no known efficient general satisfiability algorithm. I'm still interested in feedback about my algorithm. Does it work? How does it compare with common algorithms?

Problem 1

The case of $(x\rightarrow y \vee \overline y)$ should be a "non conditional variable" with respect to $x$ (ie. that $\overline x$ should now be inserted into $W$). If this is not true, then your algorithm needs an extra step to infer this. Assuming $(x\rightarrow y \vee \overline y)$ is a "non conditional variable", we continue.

Problem 2

NOTE: this is one problem I noticed; there may very well be other problems.

The problem is with the "empty OR implication" split into two algorithms, is that in its current form, the split does not cover all cases. In particular:

You start with $(x \vee c \rightarrow y)$, then $c$ is removed and we are left with an empty OR implication of $(x \vee [] \rightarrow y)$. You suggest now splitting it into two new problems and solving each of them; one with $x=T\wedge y=T$ and one where $y=T$. But this does not cover all cases. What about the case when $x=F\vee y=F$. However, your algorithm never considers the possibility that $y$ is false.

I think you might be able to fix this by formulating the two new problems as one with $y$ and one with $\overline x$.

Problem 3

What happens when you are left with a bunch of clauses in the form:

$$(a\wedge b \rightarrow c)$$

or

$$(a \rightarrow b \vee c)$$

After reducing everything, these clauses will remain, and you won't be able to test their satisfiability easily.

Analysis

Note: This "O" notation, $\mathcal{O}(something)$ etc., is called Big O notation. $\Omega(something)$ is called Big-omega.

Supposing the algorithm did work in general, it would run in time of $\Omega(2^m)$ worst case, $m$ being the number of variables. The reason is, each splitting of problem into problems of similar size means that the algorithm runs in exponential time. To visualize this concept, look at the following image of a full binary tree (image from here):

Now imagine the original problem is the node on top. We split the problem into two problems on the second level, but they are of similar size (we only get rid of one variable, $x$ or $y$ from the empty OR implication, so we will still have lots of empty OR implications to do each level). We will potentially have to split the problem $\mathcal{O}(m)$ times to get rid of $m$ variables. This means we will have to deal with a tree with $m$ levels. A tree with $m$ levels has $2^m$ leaf nodes (nodes at the bottom). This is called exponential time, and is informally somewhat on-par with all known boolean satisfiability algorithms. But so is brute force: there are $2^m$ possible assignments of the variables, so by brute force you can guess each assignment and check for satisfiability with similar performance!

Before you feel you have a "new" SAT algorithm, please review the standard/classic backtracking/search algorithm in the literature for the problem dating to ~1962, the Davis–Putnam–Logemann–Loveland algorithm. most backtracking/recursive algorithms for the problem  will likely end up looking somewhat similar to this algorithm, although it can take quite a while to demonstrate this equivalence.

Serious analysis would involve benchmarking your algorithm against examples (or random instances) vs DPLL.

And so it is helpful merely to summarize how your algorithm differs from it. without reviewing your code, odds are:

The algorithm has a bug in it. either returning false positives or negatives (ie algorithm returns "formula is satisfiable" when it is not or vice versa, respectively). this can be usually caught by very thorough testing of a large range of randomly generated formulas and checking against another known correct algorithm/implementation eg DPLL.
Your algorithm is not as good as DPLL.
If it is as good as DPLL or "better", it is generally due to branching and variable selection heuristics/strategies and the distribution of instances under testing.

The algorithm can be easily understood by an intelligent undergraduate however it seems rarely taught at the undergraduate level or in undergraduate textbooks, or perhaps not even often referenced, possibly leading to a mistaken view or impression that basic SAT algorithms are not well understood etc.

Also recently just ran across this "live" site called ToughSat by Yuen and Bebel for generating hard instances for use with benchmarking, some based on factoring [one of the classic SAT hard instance generation methods]. there are others eg DIMACs that store archives of hard instances although it may no longer be online.


Shortest path between two points with n hops Is there an efficient algorithm which computes the (possibly approximately) shortest $n$-edge path between two points $A$ and $B$ in a weighted complete graph? Dijkstra won't work because it will just give the trivial answer of $A\to B$. I'd like to find an $n$-edge path (e.g. for $n=4$, find $C$, $D$ and $E$ which minimize total path length of $A\to C\to D\to E\to B$).

If vertices can be visited more than once, then yes: you can create $n+1$
copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v_1, \dots, v_{n+1}$ and each edge $uv$ in the original graph becoming the set of edges $u_iv_{i+1}$ for all $1 \le i \le n$; now run Dijkstra on the resulting graph with start vertex $A_1$ and end vertex $B_{n+1}$.  Intuitively, each edge traversed in any path necessarily takes you to the next "level" of the graph.

If vertices cannot be visited more than once, then there's no known poly-time algorithm, since setting setting $n$ to one less than the number of vertices would solve the NP-hard Hamiltonian Path problem.  (Although the HP problem technically asks for any path that visits all vertices exactly once, a poly-time algorithm for the simple-paths version of your problem would nevertheless give you a poly-time algorithm for HP: just run it $O(n^2)$ times, one for each possible pair of start and end vertices.)

I will describe an algorithm that will solve any hamiltonian path problem in any number of dimensions in polynomial time. Due to triangle inequality we know the solution to a hamiltonian path problem will be a perimeter( on the euclidian plane). The brute force practice of finding every possible path can be pared in to polynomial time by only finding sufficiently short possible perimeters. The data sets of distances between points(in any number of dimensions) will be sorted. The three shortest distances will form a triangle. For each side of this triangle the next shortest point to include will be found by finding the closest point to include along each side. Using the sorted tables the computer will find the next closest non-included point and then sum with the path the other point on the perimeter. These possible inclusions can be stored in a sorted list so that as every new point is added only two new line segments will need to find their next closest points. This continues until the first possible solution is found. This solution becomes the goal post and will be no longer than 200% of the actual solution. From my initial thought errors induced would have to be under 15% of the next closest point inclusions. The algorithm would then be able to go thru the data and construct new possible solutions by including the next shortest points up to 15% longer than the first path. Recursive addition will then construct a new possible perimeter until it becomes the new goalpost or passes it.


Is there a complexity metric for finite state machines? I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each Turing machine as one of the criteria to guide the evolution process.

However, I couldn't find any references as to a canonical complexity metric for FSMs. I imagine the metric would include some combination of the number of states, number of transitions, and number of input symbols, but I'm not sure how these would be combined appropriately into a normalized metric.

Is there a canonical (ideally normalized) complexity metric for finite state machines?

Yes, there is a canonical complexity metric for finite state machines: the number of states.  It's as simple as that.

The number of transitions or input symbols don't matter (for this standard, canonical metric).  We don't use a normalized metric based on the combination of such values.  We just count the number of states.

You could take the three-dimensional vector (states, transitions, symbols) as your measure of complexity.

Disadvantage: you get incomparable levels of complexity.

Advantage: you retain all the information.


Checking if there are 2 elements in an array that sum to X in O(n lg n) I have thought about the most useful way of checking an array for 2 elements that sum to X.
The trivial solution is to check the sum of every element with every element, and the complexity of this solution is $O(n^2)$.

My solution is:
Say the array is A.
It's length is N.
Elements are from A[0] to A[N-1]

Pseudo-Code is:

Check_Sum(A,left,right) {
  mid <-- floor( (left+right)/2 )

  if(A[left]+A[right]=X)
    return true

  return Check_Sum(A,left,mid)||Check_Sum(A,mid,Right)
}

My question is: Is the complexity of my solution equal to $O(n \lg n)$?

Sort the array say ascending order- Takes O(nlogn)

Keep two pointers in the array say fingers. Finger f1 at the first element and finger f2 at the last element.

Sum the elements to get f1+f2:
if f1+f2  == X you have found your solution
else if f1+f2 > X decrease f2 to point to the element to its left
else increase f1 to point to the element to its right

This step will take O(n) making the overall cost O(nlogn)

This solution is also referred to as the finger pointing solution. Can be used in any sorted collection where you can traverse in both the direction for eg in trees.

Easiest solution:

Put all elements in a hash map -> O(n) to O(n^2) depending on has function
Iterate through list doing a lookup for (Sum - A[i]) -> O(n) with O(1) lookups
If Sum is 2x A[i], check for second instance value in the map

Solution in O(n) to O(n^2) depending on has function


Optimizing hash table for common subset of keys? Are there variants of hash tables that take advantage of the likely distribution of key values? For example, if I'm using utf-8 encoded unicode strings as identifiers in a compiler but expect the majority of them to fit into ASCII, can I optimize for that use case?

Yes, it's sometimes possible to optimize hash tables based on expected key values (i.e. make certain classes of keys at the expense of other classes). But I don't see how there could be one in your case.

There are two ways to potentially make hash tables faster: use a hash function with fewer collisions, and use a hash functions that's faster to calculate. But they pull in opposite directions: you can either make the hash function faster or better, not both.

Hash functions are designed to spread out likely key values in the first place. So if you have “typical” input, there's nothing to be gained here.

For example, if you're making exact string comparisons, then the fact that the strings are encoded in UTF-8 doesn't affect the way the hashes are calculated. The hash function looks at all the bytes of the string anyway, and has a low probability of collisions except for specially-crafted data. A hash function specialized to pure-ASCII strings won't be faster to calculate (operations are on bytes anyway, even on words, not on individual bits) nor have more collisions (repeated bit patterns like “all upper bits are 0” is something typical hash functions are designed to cope with).

An example where you can gain performance for typical cases is when the key for the hash table is a large data structure, such that there's a gain to be made by hashing only part of the data structure. Say the key consists of both a name and some large extra data, and most keys have different names, but occasionally there are distinct keys with the same name. Then you might use a two-level table: first hash on the key, and then, only in buckets where there is more than one entry, calculate the hash of the extra data.

In the case of a string, the closest thing would be to hash only a prefix. But that typically gives bad results in practice; for example, in a compiler, it's very common to have large sets of identifiers with a common prefix.

Another case where a simpler, partial hash function can be useful is when equality between keys is hard to test. This may be the case with Unicode strings if you need to treat different representations of the same text as equal, e.g. treat combining characters as equivalent to non-canonical forms. In this case, you may want to avoid doing the work of normalizing each string. However that wouldn't help for the pure-ASCII case, since normalizing a pure-ASCII string is easy. It might help with typical “tame” uses of Unicode (sticking to characters that are common in one language).

A hash table is not necessarily the best structure to represent a mapping from keys to values. Search trees or tries have many advantages. Balanced search trees have guaranteed $O(\lg(n))$ behavior, whereas hash tables are harder to protect against deliberately-crafted key sets (not so much an issue in compilers, but it can be an issue when interpreting code from an untrusted source, e.g. a web browser running Javascript code from some random website). Hash tables are pretty much impossible to share intelligently — you have to copy the whole table. With trees, on the other hand, sharing comes naturally. Sharing is very often useful in compilers, between scopes that differ only on a few identifiers.

Shortly, yes, - you can use this information for improvements. But you should define a current implementation and an optimization goal for a precise answer.

For example, you could optimize average search by key time. Let's assume that the "ASCII" set means that the last bit inside the utf-8 (8 bit) set is zero. Let's assume that you'd been used a naive hash Map and hash function as implementation. Always 8 buckets (static), the unsophisticated hash function is the last 3 bits. All ASCII symbols appear uniformly, and the utf-8's remainder chars are "very sparse."

Optimization: change the last 3 bits to the first three bits. You just get rid from "almost"(depending on the "very sparse") 1/3 adding hash collisions. Look at any article about hash Map's performance to figure out what performance boost you got via elimination of 1/3 hash collisions on average. Operations complexity for Java's HashMaps.

Avg. situation changed like. (hash function time + 1 or 2 operations with list for accessing)

000 - "NUL"(00000000)" -> "7" (11100000)

(a bucket with "000" hash label and two collided elements)

010 - "ESC(00111010)"

becomes (hash calculation + 1 operation)

000 - "NUL"

111 - "7"

001 - "ESC"

If there was no "very sparse" utf-8 remainder (and non-uniform access patterns) both hash functions act in the mentioned aspect equally. This is how, in principle, we can use size, keys, values, access patterns distribution and other use-cases info for optimizations.


Time complexity of insertion in linked list Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this:

  What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

In my opinion, the answer should be $O(n^2)$ because in every insertion, we will have to insert the element in the right place and it is possible that every element has to be inserted at the last place, giving me a time complexity of $1 + 2 + ... (n-1) + n = O(n^2)$

However, the solution that I have says that we can first sort the elements in $O(n \log n)$ and then, we can insert them one by one in $O(n)$, giving us an overall complexity of $O(n \log n)$.

From the given wording of the question, which solution is more apt? In my opinion, since the question mentions "linked list needs to be maintained in sorted order", I am inclined to say that we cannot sort the elements beforehand and then insert them in the sorted order.

The question only says that the target list needs to be maintained in sorted order. It doesn't say anything about any other data structure that you may choose to use. The proposed solution first does some preprocessing of the arguments to insert, then does the insertion proper. This is allowed by the problem statement.

A practical reason to do this, rather than insert the elements then sort, would be if the linked list object is shared with another thread that requires it to always be sorted. (In such a scenario, you'd need to ensure that inserting one element is atomic.) So this question isn't just making strange requirements for the sake of being strange. It's the sort of requirements that come up often in the real world of programming.

Another solution with the same complexity would be to insert the elements into the target list as they come, and maintain a parallel data structure mapping element values to node pointers in the target list. To insert each element, find the preceding element in the mapping, and insert the new element after this node. This assumes that the insertion process creates the list nodes as it goes (as opposed to filling existing blank nodes).

This question is more about reading comprehension than about algorithms. The way it's worded, it's a bit of a trick question. It's somewhat poorly worded because it relies on precise reading, but fails to state some key assumptions, such as the fact that obtaining the elements to insert costs $O(n)$, comparing two elements can be done in $O(1)$, and the input domain is effectively unbounded (exercise: come up with an $O(n)$ algorithm if the inputs are integers in the range $[1,42]$). But the given answer is correct.

You made the assumption that there's no way to use an auxiliary data structure. Nothing in the problem statement forbids using auxiliary data structures. A simple way to forbid auxiliary data structures would be to require $O(1)$ memory overhead.

Note that even under this assumption, your reasoning is wrong, or at least imprecise. If you happened to know that the elements are given in the correct order, you could maintain a pointer to the tail of the list, and keep inserting there, which would take $O(n)$. The worst case is not if every element has to be inserted at the last position in the target list, but at the last position reached when traversing the list in some way. The worst case is indeed $\Theta(n^2)$, but to prove this, you have to prove that finding the insertion point in the list takes $\Theta(n)$ time, and this requires proving that the distance from any pointer you have into the list is bounded below by $\Omega(n)$. This is the case if you have a constant number $A$ of pointers (you implicitly assumed $A=1$, with a single pointer at the start of the list), so that you need to traverse at least $k/A$ nodes after $k$ insertions in the worst case.

It should be O(n).
Follow the algorithm as -

1) If Linked list is empty then make the node as
   head and return it.

2) If the value of the node to be inserted is smaller
   than the value of the head node, then insert the node
at the start and make it head.

3) In a loop, find the appropriate node after
   which the input node is to be inserted.

To find the appropriate node start from the head,
   keep moving until you reach a node who's value is greater than
   the input node. The node just before that is the
   appropriate node

4) Insert the node after the appropriate node
   found in step 3


How to find 5 repeated values in O(n) time? Suppose you have an array of size $n \geq 6$ containing integers from $1$ to $n − 5$, inclusive, with exactly five repeated. I need to propose an algorithm that can find the repeated numbers in $O(n)$ time. I cannot, for the life of me, think of anything. I think sorting, at best, would be $O(n\log n)$? Then traversing the array would be $O(n)$, resulting in $O(n^2\log n)$. However, I'm not really sure if sorting would be necessary as I've seen some tricky stuff with linked list, queues, stacks, etc.

The solution in fade2black's answer is the standard one, but it uses $O(n)$ space. You can improve this to $O(1)$ space as follows:

Let the array be $A[1],\ldots,A[n]$. For $d=1,\ldots,5$, compute $\sigma_d = \sum_{i=1}^n A[i]^d$.
Compute $\tau_d = \sigma_d - \sum_{i=1}^{n-5} i^d$ (you can use the well-known formulas to compute the latter sum in $O(1)$). Note that $\tau_d = m_1^d + \cdots + m_5^d$, where $m_1,\ldots,m_5$ are the repeated numbers.
Compute the polynomial $P(t) = (t-m_1)\cdots(t-m_5)$. The coefficients of this polynomial are symmetric functions of $m_1,\ldots,m_5$ which can be computed from $\tau_1,\ldots,\tau_5$ in $O(1)$.
Find all roots of the polynomial $P(t)$ by trying all $n-5$ possibilities.

This algorithm assumes the RAM machine model, in which basic arithmetic operations on $O(\log n)$-bit words take $O(1)$ time.

Another way to formulate this solution is along the following lines:

Calculate $x_1 = \sum_{i=1}^n A[i]$, and deduce $y_1 = m_1 + \cdots + m_5$ using the formula $y_1 = x_1 - \sum_{i=1}^{n-5} i$.
Calculate $x_2 = \sum_{1 \leq i < j \leq} A[i] A[j]$ in $O(n)$ using the formula
$$
x_2 = (A[1]) A[2] + (A[1] + A[2]) A[3] + (A[1] + A[2] + A[3]) A[4] + \cdots + (A[1] + \cdots + A[n-1]) A[n].
$$
Deduce $y_2 = \sum_{1 \leq i < j \leq 5} m_i m_j$ using the formula
$$
y_2 = x_2 - \sum_{1 \leq i < j \leq n-5} ij - \left(\sum_{i=1}^{n-5} i\right) y_1.
$$
Calculate $x_3,x_4,x_5$ and deduce $y_3,y_4,y_5$ along similar lines.
The values of $y_1,\ldots,y_5$ are (up to sign) the coefficients of the polynomial $P(t)$ from the preceding solution.

This solution shows that if we replace 5 by $d$, then we get (I believe) a $O(d^2n)$ algorithm using $O(d^2)$ space, which performs $O(dn)$ arithmetic operations on integers of bit-length $O(d\log n)$, keeping at most $O(d)$ of these at any given time. (This requires careful analysis of the multiplications we perform, most of which involve one operand of length only $O(\log n)$.) It is conceivable that this can be improved to $O(dn)$ time and $O(d)$ space using modular arithmetic.

DATA=[1,2,2,2,2,2]

from collections import defaultdict

collated=defaultdict(list):
for item in DATA:
    collated[item].append(item)
    if len(collated) == 5:
        return item.

# n time


A multi-user, multi-processing operating system cannot be implemented on hardware that does not support A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

Address translation
DMA for disk transfer
At least two modes of CPU execution (privileged and non-privileged)
Demand paging

My attempt:

Somewhere it explain as : Address translation is needed to provide memory protection so that a given process does not interfere with another.

We also need at least 2 modes of execution to ensure user processes share resources properly and OS maintains control. This is not required for a single user OS like early version of MS-DOS.

Demand paging and DMA enhances the performances- not a strict necessity.

    Can you explain it in a formal way, please?

None of the above.

As you noted, DMA and demand paging can be useful features but are not necessary to support multiple users and multiprocessing.

Address translation is not necessary even for memory protection. Memory protection can be separated from address translation via a protection lookaside buffer or memory protection unit.

Providing a distinct privileged operating mode in the processor is not necessary for a multiuser system. In theory, provable trust of software can provide protection against misuse by users. Another alternative is capability systems; one can use non-forgeable fat pointers to provide resource protection.

Cannot be implemented is not the same as it's very hard to implement.

If a hardware supports turing-complete programming, then anything can be implemented on it, given enough time and memory. This means you could theoretically implement a multi-user, multi-processing operating system on a Turing machine. Written in Brainfuck.


Does a simple calculator require an operating system? I don't mean a TI-84 type calculator, and I also do not mean a simple calculator app on your phone.

Does a basic scientific calculator require an operating system?

No.

Operating systems have several purposes, such as interfacing with the hardware and, managing multiple concurrent or sequential applications and providing protection between different users. A calculator has only user and only one application so there's nothing to manage there.  And the hardware is simple enough that the single application may as well just talk directly to it, rather than going through the intermediate layer of an operating system.

yes we need a os for calculator which will manage the embedded os .purpose of os is to control hardware resources.OS by itself can not be used, it will need an embedded os for calculator


Does the word "efficient" usually refer to polynomial time or polylogarithmic time? This question is strictly about terminology.

I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and the Wikipedia article on computational complexity theory use the word in that way.

However, other sources (e.g. the Wikipedia articles on NC and P-complete) reserve the word "efficient" for algorithms with polylogarithmic runtimes and use "tractable" for algorithms with polynomial runtimes.

This conflicting terminology is obviously confusing. Of course, any (good) formal discussion of algorithmic complexity will precisely define its terminology, but in general, are either of the two usages above clearly more conventional than the other? If someone uses the term "efficient" in an informal discussion of computational complexity without defining it, is it more likely that they mean "polynomial time" or "polylogarithmic time"?

There is no one true answer.  It depends on context.  The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time".  Polylogarithmic time is used only in very narrow contexts.

In general, if you think your audience might not be sure about the meaning, then I recommend you to define your terms.

Perhaps this is a reference to Cobham's thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis?wprov=sfla1. Usually the word used is "feasible" though.


Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent? I fail to understand why cut off value would be system dependent, and not a constant.

From Princeton University website

  Cutoff to insertion sort. As with mergesort, it pays to switch to
  insertion sort for tiny arrays. The optimum value of the cutoff is
  system-dependent, but any value between 5 and 15 is likely to work
  well in most situations.

Would it be safe to assume that optimal cut off value is equal to optimal set size for Insert sort?

Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well it caches it and so on. Insertion sort and quicksort use different instructions and hava different memory access patterns.  So the running time of quicksort versus insertion sort for any particular dataset on any particular system will depend both on the instructions used to implement those two sorting routines and the memory access patterns of the data.  Given the different mixes of instructions, it's perfectly possible that insertion sort is faster for lists of up to ten items on one system, but only for lists up to six items on some other system.

When a partition reaches the size that can fit in a machine dependent sized cache, then it will be faster .
It's more interesting to look at the mathematics behind the machine independent answer of 10 being the cut off point.
C_N is the number of comparisons to sort N elements; in quick sort,
each element is compared with the partitioning element until the left and right pointers cross ( so the last comparison happens once again ), so there are
N + 1 comparisons for the current partitioning call. Then there are recursive calls on the left and right partitions either side of the partitioning element.
In randomized quicksort, where all the elements are shuffled first, then the average number of comparisons in the two partitions is given by
$ { \sum_{j=0}^N \big( C_{j-1} + C_{N-j-1} \big) \over N  } $.
The goal is then to simplify the solution of the quicksort average comparison count equation , and then incorporate the given average comparison cost of insertion sort $ {j(j-1) \over 4 } $ at a given cutoff $M$.
The sum is simplified, because there is symmetry of C terms around half $N$.
$ {2 \over N} \sum_{j=0}^N C_{j-1} $
Eliminate the sum by subtracting the equation for $N-1$
$$ C_N  = N + 1 + {2 \over N} \sum_{j=0}^N C_{j-1} $$
minus
$$  C_{N-1} = (N-1) + 1 + { 2 \over N-1} \sum_{j=0}^{N-1} C_{j-1} $$
Multiply by N and N-1 respectively the equations to make the subtraction easier.
$$ N C_N - (N-1) C_{N-1} = N(N+1) - (N-1)(N) + 2 \bigg(\sum_{j=0}^N C_{j-1} -\sum_{j=0}^{N-1} C_{j-1} \bigg)$$
Collecting terms and subtracting the sums,
$$ N C_N = (N-1)C_{N-1} + 2N + 2 \bigg( C_{N-1} \bigg)  = (N+1)C_{N-1} + 2N $$
Dividing by N(N+1) , the suitable summation factor,  which simplifies to a recurrence equation that can be telescoped.
$$ {C_N \over N+1} = {C_{N-1} \over N} + { 2 \over N+1} $$
Telescope, whilst maintaining that  $ C_{N-1} <> C_{M} $
$$ {C_N \over N+1} = {C_{M+1} \over M+2} + \bigg(2 \sum_{j=M+3}^{N+1} {1 \over j} = 2 \big( \sum_{j=1}^{N+1} {1\over j} - \sum_{j=1}^{M+2} {1\over j} \big) \bigg) $$
$C_{M+1}$  follows the original recurrence equation, but with the insertion cost inserted instead of recursive partitioning.
$$ {C_{M+1} \over M + 2} = (M+1) + 1 + 2 \sum_{j=1}^{M+1} {j(j-1) \over 4} $$
Since $ \sum_{j=1}^{P} { P \choose Q} = { P+1 \choose Q+1} $
$$ {C_{M+1} \over M + 2 }  = M + 2 + 2/2 { M+2 \choose 3} = M + 2 + (M+2)(M+1)(M) / 6 $$
$$ C_{M+1} =  1 + { M(M+1) \over 6 } $$

Since $ \sum_{j=1}^N {1\over j} = H_N \approx ln N  + \gamma $ , the whole equation looks like
$$ C_N = (N + 1) \bigg(1+ {M(M+1) \over 6(M+2)} + 2\big(ln (N+1) - ln (M+2) \big) \bigg) $$

So for N = 1000, C_N is minimum when M = 10, independent of the machine.

This is a student answer (mine) to an Exercise from the AofA website,
Introduction Analysis of Algorithms Sedgewick
The answer is  a middle school algebra expansion of some answers found on a discussion forum, mainly this thread : Flores, Yao and Spreng ,
and a it's a good idea to try to independently reach their answers. I got to the first one, and found it came up with 6 which was the wrong answer, and re-read the thread several times before being able to understand the abbreviated answer by Yao, having to dive into the book to get his assumptions , which are explained above in a middle school algebra way ( that's about my level, after 30+ years of not doing maths ).


Whether TM accepts epsilon? $L = \{ \langle M \rangle \mid \epsilon \in L(M) \}$, where $M$ is any Turing machine.

Why is the above problem undecidable? Can't we just check whether the initial state is a final state and say the TM accepts $\epsilon$ if the initial state is the final state else it doesn't? We can also just check if the TM goes to an accepting state on the blank symbol.

First, a note on notation: $L(M)$ is a language which is a set. Languages don't accept or reject, Turing machines do. You can either say "$\epsilon \in L(M)$" or "$M$ accepts $\epsilon$".

There are many Turing machines in this language that don't meet your description. For example, imagine a machine that upon reading a blank goes and writes, say, 111 and then accepts. The initial state does not need to have a transition to an accept state on a blank symbol in order to belong in this language.

Here's another perspective on why this language is undecidable using Kleene’s Recursion Theorem. Imagine that there is some decider $D$ that, given the description of a TM $\langle M \rangle$, $D$ accepts if $M$ accepts $\epsilon$ and rejects otherwise. Now create a Turing machine with the following behavior:

Get my own description <M> and then run D on <M>.
If D accepts <M>:
   If input is empty, reject. Otherwise accept.
Else:
   If input is empty, accept. Otherwise reject.

The existence of this decider allows us to create the above Turing machine which is a contradiction. Essentially, if the decider says the Turing machine is supposed to accept the empty string, it then goes and rejects and if it's supposed to reject, it then goes and accepts. This idea of being able to use self-reference and ask "What am I about to do?" and then doing the opposite shows that no single machine can predict behavior of all others.

$M$ may be doing computations regardless of the input, rather then checking then first checking it and secondly compute things accordingly


Seems like NP cannot equal coNP by the definition of NP A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will generally be an intractable number of possibilities. How can it be possible to deterministically verify the no answer  for all possibilities in polynomial time?

As an example, would it not be necessary to address every non-empty subset to verify a no answer for the subset sum problem?

This kind of argument presupposes that the only way to (for example) prove that a SUBSET-SUM instance is not solvable is by going over all subsets and checking that their sum doesn't match. This isn't true — a meet-in-the-middle algorithm works in time $O(\sqrt{2}^n)$ rather than $O(2^n)$, where $n$ is the number of sets.

Furthermore, consider the analog of this question for polynomial space rather than time. In this case it does hold that NPSPACE=coNPSPACE, for the simple reason that PSPACE=NPSPACE.

If I'm understanding your question correctly, then I see no problem with the ability to verify a "no" answer in polynomial time. I think you misunderstand what the complement is calling for.

Given the subset-sum problem, an answer would be a subset of the given set, and to verify that answer would be to determine whether or not its sum equals the target sum. So for a "no" answer, simply add all values in the answer (in exactly the same way you're adding the values of a "yes" answer) to arrive at the conclusion that the sum of the subset does not equal the target sum for the specified problem.

You say:

  The complement is that the no answer must be similarly verifiable.

This is still true. You don't have to be able to verify all possible "no" answers, together, in polynomial time to satisfy the complement. You only have to be able to verify a given "no" answer in polynomial time. Which holds.