Practical importance of Turing machines? I am an electrical engineer, and only had one CS course in college 26 years ago. However, I am also a devoted Mathematica user.

I have the sense that Turing Machines are very important in computer science. Is the importance only in the theory of computer science? If there are practical implications/applications what are some of them?

The importance of Turing machines is twofold. First, Turing machines were one of the first (if not the first) theoretical models for computers, dating from 1936. Second, a lot of theoretical computer science has been developed with Turing machines in mind, and so a lot of the basic results are in the language of Turing machines. One reason for this is that Turing machines are simple, and so amenable to analysis.

That said, Turing machines are not a practical model for computing. As an engineer and a Mathematica user, they shouldn't concern you at all. Even in the theoretical computer science community, the more realistic RAM machines are used in the areas of algorithms and data structures.

In fact, from the point of view of complexity theory, Turing machines are polynomially equivalent to many other machine models, and so complexity classes like P and NP can equivalently be defined in terms of these models. (Other complexity classes are more delicate.)

Turing machines are good mind exercise with little practical use. There is no harm in not having one. All applications of a Turing machine are either intuitive or a matter of religion because they cannot be proved or refuted.


What's the difference between a "dead" and "empty" state? In computational theory, I came across both deterministic and non-deterministic finite state machines but I heard someone said there are no dead states in deterministic machines. I thought dead and empty states were the same. What I noticed is that empty states are represented by a special symbol called an empty set ∅. What's exactly the difference?

That ∅ in the figure is just the name of that particular state in that machine.You could name it "cpx" if you want.

The figure is an example showing conversion from NFA to DFA. The conversion algorithm builds the DFA states from subsets of NFA states.The state named ∅ indicates that this state represents a particular subset of the states of the NFA, namely the empty set.

So, the symbol is just for the viewer to understand the significance of that particular state in the machine.

An empty state is the state of a list with zero items in it. A dead state refers to an error in the machine itself. An example would be a job queue being empty vs a computer being dead.


What does it mean by saying "Asymptotically more efficient"? What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ?

$X$ will be a better choice for all inputs.
$X$ will be a better choice for all inputs except small inputs.
$X$ will be a better choice for all inputs except large inputs.
$Y$ will be a better choice for small inputs.

The link for this question is here .

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

I thought that an algorithm more asymptotically efficient should work for all inputs, but I am not getting the reason behind "It works for all inputs except small ones".

First off, both algorithms "work" for all inputs.  The question is about performance.

The answers to that question are kind of crappy.  One way to say one algorithm is asymptotically more efficient than another is if there is some (problem-specific) input size such that for any larger input size the more efficient algorithm will take fewer "computational steps", usually by some abstract measure, e.g. number of comparisons.

The idea of the answers is that an asymptotically more efficient algorithm may still require more steps before that input size.  It can be the case that the asymptotically more efficient algorithm requires fewer steps for all inputs, but it doesn't need to be the case and in practice usually isn't.  So a better wording of the "correct" answer would be "$X$ will be a better choice for all inputs except possibly small inputs".

The wording still isn't that great though.  First off, many more factors go into deciding what algorithm is a "better choice", but I'll give them that the intent is clear enough in this case.  The real issue is "small" and "large".  One of my favorite papers is The Fastest and Shortest Algorithm for All Well-Defined Problems. This paper describes an algorithm which given any specification of a function and a proof that it can be computed in polynomial time will compute that function in optimal time complexity within a factor of $5$ plus an additive term.  For example, if I provided it an implementation of bubble sort as the function specification and the simple proof that it was $O(n^2)$, it would produce a sorting algorithm that was $O(n\lg n)$.  In fact, it would produce an algorithm that was $5cn\lg n + o(n\lg n)$ where $c$ was the constant factor of the asymptotically* optimal algorithm. This is amazing.  There's just one problem: the constant term – hidden in the $o(n\lg n)$ in this example – renders the algorithm almost certainly completely infeasible for virtually any real problem.  What do I mean by "completely infeasible"? I mean the heat death of the universe will happen many times over before that algorithm completes.  Nevertheless, for suitably "large" inputs it will be faster than bubble sort.  My point is it's almost certainly not physically possible to write down by any means a "suitably large" input, let alone compute on it.

At any rate, how I would word the correct answer would be: "$X$ requires fewer steps than $Y$ on sufficiently large inputs".  This is still a bit vague as there are multiple notions of "step" that could apply and an algorithm could be asymptotically more efficient by one metric and less efficient by another.  This wording avoids the value judgement of "better choice"; there are many reasons to choose asymptotically less efficient algorithms or even less efficient algorithms when constant factors/terms are specified such as cache-efficiency or implementation simplicity.

* There is a subtlety here. The asymptotically optimal algorithm may have a worse constant factor, $c$, than an asymptotically non-optimal algorithm. I think it will have the best value of $c$ for any asymptotically optimal algorithm, but it's conceivable that to squeeze out a slight gain in asymptotic efficiency, massive complexity is added that significantly increases the constant factor.

Reason:
If two algorithms for the same problem are of the same order then they are approximately as efficient in terms of computation. Algorithm efficiency is useful for quantifying the implementation difficulties of certain problems.
•   B will be a better choice for all inputs.
•   B will be a better choice for all inputs except small inputs.
•   B will be a better choice for all inputs except large inputs.
•   A will be a better choice for small inputs.


Finding the size of the smallest subset with GCD = 1 This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this problem anywhere.

The problem is: Given a set of $N$ distinct positive integers not greater than $10^9$, find the size $m$ of the smallest subset that has no common divisor other than 1. $N$ is at most 500, and a solution can be assumed to exist.

I managed to show that $m \le 9$. My reasoning is: Suppose there exists a minimal subset $S$ of size $|S|=10$, with gcd = 1. Then all 9-subsets of $S$ must have gcd > 1. There are exactly 10 such subsets, and their gcds must be pairwise coprime. Let these gcds be $1 < g_1 < g_2 < ... < g_{10}$, where $\gcd(g_i,g_j)=1$, for $i \neq j$. Then the maximum number in $S$ is $g_2g_3...g_{10}$. But $g_2g_3...g_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 > 10^9$, a contradiction.

However, even with this, a straightforward brute force is still too slow. Does anyone have any other ideas?

This problem is equivalent to the following, and it's trivial to construct reduction both ways.

Given a list of bit vectors, find the minimum number of them such that and all of them result the $0$ bit vector. $(*)$

Then we show set cover reduces to $(*)$. By set cover, I mean given a list of sets $S_1,\ldots,S_k$, find the minimum number of sets that covers their union.

We order the elements in the sets to be $a_1,\ldots,a_n$. Let $f(S) = (1-\chi_{a_1}(S),\ldots,1-\chi_{a_n}(S))$, where $\chi_x(S) = 1$ if $x\in S$, 0 otherwise. Note this function is a bijection so it has a inverse.

Now, if we solve $(*)$ on $f(S_1),\ldots,f(S_k)$, and the solutions is $\{ f(S_{b_1}),\ldots,f(S_{b_m})\}$, then $\{ f^{-1}(S_{b_1}),\ldots,f^{-1}(S_{b_m})\}$ is the solution to set cover.

Thus I would think this problem is testing one's ability to prune the search space.

If you are able to find a subset with gcd(S) = 1, then I can always remove redundant elements from the subset till only 2 elements remain , which have gcd(S) = 1. Therefore, I can claim that either the smallest subset will contain 2 elements or it will not exist.

Now, we use recursion to solve this problem. Let's divide the array of numbers into 2 parts, one with n-1 elements and one with 1 element (last element). Either the 2 numbers will be in the first n-1 elements or one element will be there from 1st part paired with last element. Therefore, we are able to solve this problem in

T(n) = T(n-1) + O(n) time.
which means T(n) = O(n^2).


Proving NP-hardness of Hamiltonian Cycle problem variant I need to prove that determining whether a graph has a  relaxed-Hamiltonian cycle (definition given ahead) is NP-hard.

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of $G$ exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated twice or even more times).
Note: In a closed walk we can visit a vertex or edge multiple times, but first and last vertex are same. In the relaxed-Hamiltonian cycle this first and last vertex being the same is not counted as repetition.

I am thinking reducing to relaxed-Hamiltonian cycle from Hamiltonian Cycle.
Claim: Construct graph $G'$ given $G$ such that $G$ has Hamiltonian cycle iff $G'$ had relaxed-Hamiltonian cycle.
My idea is that if a graph $G$ has one or more articulation points then it cannot have a Hamiltonian Cycle so simply give a $G'$ which does not have a relaxed-Hamiltonian cycle.
The problem is when graph $G$ does not have any articulation points. In this case the graph $G$ may or may not have an Hamiltonian Cycle. I cannot think of a construction for this case such that my claim holds.
Is my approach correct? If yes please suggest how I could take care of the mentioned case? Otherwise, please hint me towards the correct direction of thinking to get the right construction.

Your definition:

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of G exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated 2 or even more times).

I'll call this revisited vertex (for a given $C$) the nexus of $C$ and look at a case that shows that even if we know which node must be the nexus of any relaxed-Hamiltonian cycle, the problem is still NP-hard.
Consider two graphs $G_1,G_2$ for which finding a Hamiltonian cycle is NP-hard (which may be two copies of the same graph). Then we create $G$ by identifying a vertex in $G_1$ with a vertex in $G_2$, with the single vertex thus created called $w$. $w$ is an articulation vertex so $G$ cannot have a (standard) Hamiltonian cycle.

If a relaxed Hamiltonian cycle exists in $G$, it must have $w$ as its nexus. To visit all nodes in $G$, we have to visit $w$ and that is the only node which allows us to cross into $G_2$ and visit all nodes there. So we have the second (minimum) visit and $w$ is the nexus.
The definition of the relaxed Hamiltonian cycle means that we could in principle find disjoint cycles all including $w$ within either $G_1$ or $G_2$ and still meet the relaxed-Hamiltonian standard. We can avoid this case by ensuring that nodes in $G_1$ and $G_2$ that we pick for identification to create $w$ are maximum degree $3$, so we cannot re-enter a second cycle in the same graph part from $w$.
Then the problem of finding a relaxed Hamiltonian cycle in $G$ is as hard as finding Hamiltonian cycles in both $G_1$ and $G_2$ which we know can be NP-hard.
Further to your claim, we therefore know that if we find a relaxed Hamiltonian cycle for $G$ we have found a Hamiltonian cycle for both $G_1$ and $G_2$ (and $G_2$ is allowed to be a copy of $G_1$).

Here we will refer relaxed- Hamiltonian cycle as Ultra-Hamiltonian cycle.
We know Hamiltonian-Path problem is known to be in NP-complete, Now to prove that ultra-Hamiltonian Cycle is NP-hard we will reduce Hamiltonian-Path problem to ultra Hamiltonian Cycle problem.
To prove: Hamiltonian Path ≤P ultra-Hamiltonian Cycle
Proof:For every instance of the Hamiltonian Path problem consisting of a graph G =(V, E) as the input can be converted to ultra-Hamiltonian Cycle problem consisting of graph G’ = (V’, E’).
We will construct the graph G’ in the following way: V’ = Add vertices V of the original graph G and add 5-additional vertex V0 V1 V2 V3 V4 in butterfly formation(Explained below), such that each and every vertex of the original graph G are connected to vertices V3 and V4. Here in Graph G’ The number of vertices increases by 5, V’ =V+5. E’ = Add edges E of the original graph G and add new edges between the newly added vertices V3 and V4 to the all original vertices of the graph G. In G’ The number of edges increases by the number of vertices 2V. These 5 added vertices (V0 V1 V2 V3 V4) are in a butterfly graph with V0 as articulation point The new graph G’ can be obtained in polynomial time. The validation of reduction can be proved by the following two claims:
i)(Forward Direction) Let us assume that the graph G contains a hamiltonian path covering the V vertices of the graph starting at a random vertex say Vstart and ending at Vend, now since we connected all the vertices to two new vertices V3 and V4 in G’. We extend the original Hamiltonian Path to a ultra-Hamiltonian Cycle by using the edges Vend to V3 and V4 to Vstart respectively. The graph G’ now contains the cycle traversing all vertices exactly once except V0 (articulation point in butterfly graph) which is visited more than once, this traversal start from V0 to V1 to V2 to V0 to V4 to Vstart to ”hamiltonian path in G” to Vend to V3 to V0. (Here V0 V1 V2 V3 V4 are of butterfly graph). So this is ultra-hamiltonian path in G’. .
ii)(backward Direction) We assume that the graph G’ has a ultra-Hamiltonian Cycle passing through all the vertices, inclusive of V0 V1 V2 V3 V4, as V0 is an articulation point so it must be visited more than once and no other vertex is visited more than once, also the path from Graph G can enter the Butterfly graph either at V3 or V4 and leave the butterfly graph at V3 or V4(whichever is not used for entering in butterfly graph). Once the path leave the butterfly-graph it will visit each vertices of Graph G in path and comeback to butterfly graph(never to go back to vertex of graph G). This path must use one of V3 and V4 for exit and other for entry from Butterfly graph to vertices of Graph G (Ad V0 is articulation point and is already being visted more than once, so no other vertex can be visited more than once). Now to convert it to a Hamiltonian Path, we remove all the edges corresponding to the vertex V0 V1 V2 V3 V4 in the cycle. The resultant path will cover the vertices V of the graph and will cover them exactly once. So here we get hamiltonian path in G, from ultra-Hamiltonian cycle in G’ Thus we can say that the graph G’ contains a ultra-Hamiltonian Cycle if and only if graph G contains a Hamiltonian Path. Therefore, any instance of the ultra-Hamiltonian Cycle problem can be reduced to an instance of the Hamiltonian Path problem. Thus, the ultra-Hamiltonian Cycle is NP-Hard.


What are the reasons to learn different algorithms / data structures serving the same purpose? I have been wondering about this question since I was an undergraduate student.
It is a general question but I will elaborate with examples below.

I have seen a lot of algorithms - for example, for maximum flow problems, I know around 3 algorithms which can solve the problem: Ford-Fulkerson, Edmonds-Karp & Dinic, with Dinic having the best complexity.

For data structures - for example, heaps - there are binary heaps, binomial heaps & Fibonacci heaps, with Fibonacci heap having the best overall complexity.

What keeps me confusing is: are there any reasons why we need to know them all? Why not just learn and get familiar with the best complexity one?

I know it is the best if we know them all, I just want to know are there any "more valid" reasons, like some problems / algorithms can only be solved by using A but not B, etc.

There's a textbook waiting to be written at some point, with the working title Data Structures, Algorithms, and Tradeoffs. Almost every algorithm or data structure which you're likely to learn at the undergraduate level has some feature which makes it better for some applications than others.

Let's take sorting as an example, since everyone is familiar with the standard sort algorithms.

First off, complexity isn't the only concern. In practice, constant factors matter, which is why (say) quick sort tends to be used more than heap sort even though quick sort has terrible worst-case complexity.

Secondly, there's always the chance that you find yourself in a situation where you're programming under strange constraints. I once had to do quantile extraction from a modest-sized (1000 or so) collection of samples as fast as possible, but it was on a small microcontroller which had very little spare read-write memory, so that ruled out most $O(n \log n)$ sort algorithms. Shell sort was the best tradeoff, since it was sub-quadratic and didn't require additional memory.

In other cases, ideas from an algorithm or data structure might be applicable to a special-purpose problem. Bubble sort seems to be always slower than insertion sort on real hardware, but the idea of performing a bubble pass is sometimes exactly what you need.

Consider, for example, some kind of 3D visualisation or video game on a modern video card, where you'd like to draw objects in order from closest-to-the-camera to furthest-from-the-camera for performance reasons, but if you don't get the order exact, the hardware will take care of it. If you're moving around the 3D environment, the relative order of objects won't change very much between frames, so performing one bubble pass every frame might be a reasonable tradeoff. (The Source engine by Valve does this for particle effects.)

There's persistence, concurrency, cache locality, scalability onto a cluster/cloud, and a host of other possible reasons why one data structure or algorithm may be more appropriate than another even given the same computational complexity for the operations that you care about.

Having said that, that doesn't mean that you should memorise a bunch of algorithms and data structures just in case. Most of the battle is realising that there is a tradeoff to be exploited in the first place, and knowing where to look if you think there might be something appropriate.

A lot of great answers, just something I think is missing, though Raphael's answer somewhat mentions this.

Ease of implementation is also something to take into consideration.
That's usually not an issue with sort algorithms, because most platforms/languages already have one implemented (and often better than what you could do), but more unusual algorithms might not be available.
Depending on your problem, you might not need the absolute best algorithm if the implementation time is 1 day versus 2 weeks.


Partitioning connected graphs in the plane This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes.

How can we divide the plane using line segments in such a way that each subdivision contains exactly one connected component?

I was thinking of generating a voronoi diagram using the endpoints, but this presents some issues:

Long edges are not guaranteed to be in the correct partition.
The border becomes very complex (There is a separate line segment for most points)

Is there an algorithm that creates less complex borders?

The input would be a planar graph with multiple connected components, where each node has coordinates associated to it.

The output would be a subdivision for the bounding box given by the graph, which divides the plane using line segments.

Example solution using red lines

I'm looking to minimize the amount of line segments required, but optimality is not required.

This is not a full answer to your question, but at least you'll have something working.

Step 1. Calculate minimal bounding axis-aligned boxes for each connected component, and also a minimal "outer" bounding box for all the components.

Step 2. Try to split the outer bounding box by horizontal or vertical segment in such a way that this segment doesn't intersect with any bounding boxes for components - this can be done by analyzing coordinates of bounding boxes only. If that is not possible then split the outer box in halves horizontally or vertically. After splitting recalculate bounding boxes for components which were split as well.

Step 3. Repeat the Step 2 recursively for each box, which contains more than one component.

Step 4. After the Step 3 you'll have a partition of the original outer box into rectangles, each of which contain only one connected component (or part of it). Remove all the edges in this partition, for which both adjacent rectangles contain the same component. After this step you'll have a partition of the outer box, but it won't be a optimal one, and it'll consist of axis-aligned segments only.

Step 5. Amend the partition, replacing axis-aligned segments by arbitrary segments, trying to minimize the total number of segments - I don't know how to do that regularly for now.

I'm not sure what "connected" here mean?

-If it means fully connected then that's finding cliques (a problem widely known to used in GIS applications)

-If it's just connected somehow (not indep vertices), then what D.W. clearly implying in his comment is the min-cut problem (ur lines r all zero cuts no edges passing through them)

*** added 17/4/2020
This Q is dated to Mar 2019, Who brought it into top after one year. I don't like this, I feel deceived and questioning credibility. –


Proof of Strong Duality Via Farkas Lemma I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the problem:

Let A.1: Minimize $c^tX$ subject to $AX\ge b$, $X \ge 0$

Let A.2 (Dual): Maximize $Y^tb$ subject to $A^tY \le c$, $Y \ge 0$

Farkas' Lemma states: Given a matrix $D$ and a row vector $d$, either there exists a column vector $v$ such that $Dv \le 0$ and the scalar $dv$ is strictly positive, or there exists a non-negative row vector $w$ such that $wD = d$, but not both.

The strong duality theorem states: If a linear program has a finite optimal solution, then so does its dual, and the optimal values of the objective functions are equal.

Prove this using the following hint: If it is false, then there cannot be any solutions to

$$AX \ge b, \; A^tY \le c, \; X \ge 0,\; Y\ge 0, \; c^tX \le Y^tb.$$

My attempt at a solution picks up from the hint. If someone will help me complete the proof, I want it to follow my line of reasoning. I know there are many other proofs of this out there.

Let $X'$ be optimal for A.1, and let $c^tX' = \lambda$.

Assume for contradiction that the hypothesis is wrong:

$$\begin{bmatrix}
A^t & -c\\
0 & -1
\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \le \begin{bmatrix} 0\\ 0 \end{bmatrix}, \quad \begin{bmatrix} b^t & -\lambda\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \ge 0 \text{ is unsolvable.}$$

By Farkas' Lemma, we know the following system is solvable:

$$\begin{bmatrix} X & w_2\end{bmatrix} \begin{bmatrix} A^t & -c\\0 & -1\end{bmatrix} \ge \begin{bmatrix} b^t & -\lambda\end{bmatrix}, \text{ where $X,w_2 \ge 0$.}$$

Now, from the system above, we may write $XA^t \ge b^t$, and
$Xc \le \lambda - w_2$.

If $w_2$ is greater than $0$, then we have found a contradiction with the assumption that $X'$ was optimal for A.1.  However, one cannot reach that conclusion if $w_2$ is exactly $0$.

I feel like I can't be that far off from a correct complete proof as I've followed exactly the hint, and the use of Farkas' Lemma which was explained on the previous page. If someone could help me finish/correct the proof, I'd be greatly appreciative.

The following is based on the book "Combinatorial Optimization" by Papadimitriou and Steiglitz (chapter 3)

On LP duality, they first state a theorem that when a LP has a feasible solution, the dual also has one and on optimality their costs are equal (Theorem 3.1 in the book, based on the simplex algorithm)

This follows from the fact that the dual cost is always dominated by the primal cost.

i.e let $x$ and $\pi$ the solutions to the primal and dual respectively, then (i.e $c'$ is transpose vector of $c$)

$$c'x \ge \pi'Ax \ge \pi'b$$

So if the primal has a feasible solution so does the dual and on optimality they (the costs) are equal.

Then the Farkas Lemma (theorem 3.5 in the book) is proved based on this theorem.

But one can reverse the proof of Farkas Lemma in the book and prove Th. 3.1 from Farkas Lemma (Th. 3.5)

A sketch:

Farkas' Lemma states that (as stated in book):

  Given vectors $a_i \in R^n$, $i = 1,..m$ and another vector $c \in R^n$,

  iff $y'a_i \ge 0, \forall i \implies y'c \ge 0$, then $c \in C(a_i)$
  (i.e $c$ is in the cone generated by $a_i$)

Consider a LP:

$$\min{c'y}$$
$$a_i'y \ge 0, i =1..m$$
$$y \ne 0$$

The LP is feasible and bounded because $y = 0$ is a feasible point and $c'y \ge 0$ (by the lemma)

$c$ can be expressed as linear combination of the $a_i$'s using a vector $\pi$, where $\pi_i \ge 0$, i.e

$$c = \sum_1^m{\pi_i a_i}$$

Constructing the dual of the LP as:

$$A_j = col(a_{ij}, i=1..m) \in R^m$$
$$a_i = col(a_{ij}, j=1..n) \in R^n$$

gives the dual LP:

$$\max{0}$$
$$\pi'A_j = c_j, j = 1..n$$
$$\pi \ge 0$$

which has a feasible solution ($\pi$) and equal cost at optimality (strong duality theorem)

Instead of lambda use lambda - epsilon - one ends up with the desired contradiction. Hence for any epsilon >0  there exists a Y_eps s.t. b^T Y_eps > lambda - epsilon.Taking the maximum over all Y_epsilons, max (bT Y_eps) >= lambda. Hence they are equal. Is the maximum value is attained? That remains to be shown, but we can get as close as we want.


Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected If a graph with $n$ vertices has more than $\frac{(n-1)(n-2)}{2}$ edges then it is connected.

I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $|E|>n-1$  edges.

I am not sure what bothers you but as I see it you are confused about the following two facts

If a graph is connected then $e \geq n-1.$
If a graph has more than $e > \frac{(n-1)(n-2)}{2}$ then it is connected.

Notice that the implications in 1 and 2 are in opposite directions.

For a proof of 2. you can check out this link.

Graph G has n nodes n=(n-1)+1
A graph to be disconnected there should be at least one isolated vertex.A graph with one isolated vertex has maximum of  C(n-1,2) edges.

so every connected graph should have more than C(n-1,2) edges.


DSPACE(f(n)) closed under complement I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$ does not change, therefore DSPACE($f(n)$) is closed under complement.

I know that most likely my answer is wrong. Can someone explain why?

Your reasoning is essentially correct. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!).

In case your TMs are only defined as acceptors (i.e., a word not in the language will not necessarily be explicitly rejected, just not accepted), things are a bit more complex. In fact, we must then require more of $f$, namely that it is space-constructible; that is, given $n$ (unary encoded), we should be able to compute $f(n)$ (binary encoded) in space not greater than the value $f(n)$ itself. This property holds for practically all "standard" functions you know.

If that is the case, then, given a TM $A$ which accepts a language in space bounded by $f$, we proceed as follows:

Compute $f(n)$ (using $f(n)$ space).
Initialize a counter with the value $f(n)$. This counter need not use more space than what was already used in step 1; for example, we store it in a separate track of the TM tape.
Simulate $A$. For every step $A$ takes, decrement the counter. If the counter reaches zero, then enter the reject state (or loop without ever accepting).

This takes at most $f(n)$ space in steps 1 and 3 (and we reuse the tape in step 3), while step 2 does not take any additional space at all since representing the counter uses space on the order of $\log f(n)$, which is smaller than $f(n)$ (which is necessarily an integer), and we use a separate track for it.

Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement,[8] because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases.

source


What randomness really is I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by generating random numbers in different distributional curves, like IID, Gaussian etc. for instance. I've been working on the boids project and a question just struck me that what exactly "random" really is? I mean, for instance, every random number that we generate, even in our programming languages like via the Math.random() method in Java, essentially is generated following an "algorithm".

How do we really know that a sequence of numbers that we produce is in fact, random and would it help us, to simulate a certain model as accurately as possible?

The short answer is that no one knows what real randomness is, or if such a thing exists. If you want to quantify or measure the randomness of a discrete object, you would typically turn to Kolmogorov complexity. Before Kolmogorov complexity, we had no way of quantifying randomness of say a sequence of numbers without considering the process that spawned it.

Here's an intuitive example that was really bugging people back in the day. Consider a sequence of coin tosses. The outcome of one toss is either heads ($H$) or tails ($T$). Say we do two experiments, where we toss a coin 10 times. The first experiment $E_1$ gives us $H,H,H,H,H,H,H,H,H,H$. The second experiment $E_2$ gives us $T,T,H,T,H,T,T,H,T,H$. After seeing the outcome, you might be tempted to claim there was something wrong with the coin in $E_1$, or at least for some weird reason what you got is not random. But if you assume both $H$ and $T$ are as probable (the coin is fair), the probability of obtaining either $E_1$ or $E_2$ is equal to $(1/2)^{10}$. In fact, obtaining any specific sequence is as probable as any! Still, $E_2$ feels random, and $E_1$ does not.

In general, since Kolmogorov complexity is not computable, one can't compute how random say a sequence of numbers is, no matter what kind of claimed "totally random" process spawned it.

other answers are good, heres some other angles on this very important/unintentionally deep question. computer scientists have been studying randomness for decades and are likely to continue to study it. it has many deep connections and foremost open questions remaining throughout the field. here are a few pointers.

"true/real randomness" occurs with low-level physical processes & "noise" such as in zener diodes, quantum mechanics etc. which can be harnessed in hardware based RNGs
other numbers generated in the computer realm is what is known as "pseudorandom" which is simulated and can never match "true randomness". these are so-called PRNGs
there is an important sense of "cryptographic hardness of random number generators" that in a sense measures their "quality" or "security" see eg cryptographically secure PRNG. basically a "weak" generator does not have as much computational complexity as a "hard" generator and a "weak" one is easier to break.
another somewhat related sense it comes up is "hardness of proofs". imagine a proof to prove that a RNG is linear time $O(n)$. that proof would seem to be simpler than one required to prove it is quadratic $O(n^2)$ and so on. this concept is still in the process of being formalized/researched but it actually impinges on deep questions like P$\stackrel{?}{=}$NP in a famous paper called Natural Proofs. roughly, the authors show a P$\neq$NP proof must have a certain "complexity" otherwise the same analysis technique could be used to break PRNGs, and moreover, somewhat surprisingly, most or maybe all complexity class separations/techniques known at that date (or possibly even afterwards, to date) do not have sufficient complexity.
an important research topic in TCS is randomized and derandomized algorithms. the idea is, roughly, to study how much the algorithm is altered by replacing "true randomness" with a PRNG and there are various deep theorems on the subject. here is a highranked cstheory.se question that gives some flavor of research in this area: efficient and simple randomized algorithms where determinism is difficult
another key related topic in TCS is information entropy— originally introduced in physics long ago— which studies a closely related concept of "information dis-order" and like some other important concepts in (T)CS seems be one of the key ideas that crosscuts the boundary between applied and theoretical analysis, even some of the formulas are the same.
again attesting to the status of active research, there are other high-ranked questions on cstheory.se that relate to this question. here is one close, almost the same: is a truly random number generator Turing computable


Finding a language for a NFSA I'm having a bit of trouble determining what language the following non-deterministic finite state automaton accepts.

Assuming the alphabet of this machine is ${a, b}$, I deduced that this automaton would accept words of the following characteristic: a word $w$ would be accepted if $w$ had zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s and $b$'s.

Is there a more clear and concise explanation of what sorts of words are accepted by this automaton or would my explanation be suffice? Any suggestions would be appreciated!

You have correctly identified your alphabet, but your verbal description is, indeed,complex.  Your NSA would accept any string with at least 2 as.

There are many ways to describe NSAs. A regular expression or a regular grammar could be appropriate here. If this is for class, I would ask your professor what format he or she prefers.

Let's trace it together:

On q1 state, you are looping on a or b, or you can proceed. That means (a|b|E)*, which can be simplified to a*b*.
Then you move to q2 on an a, which means a*b*a.
Then on q2, it is the same as q1. Creating the expression a*b*aa*b*.
Then transition on a: a*b*aa*b*a
And looping on a or b: a*b*aa*b*aa*b*.

If your alphabet only contains a and b, then a*b* covers all combinations. The above expression can be comprehended as "<anything>a<anything>a<anything>", which can be verbally summarized as "strings that contain at least 2 occurrences of a".


Why don't we use quick sort on a linked list? Quick sort algorithm can be divided into following steps

Identify pivot.
Partition the linked list based on pivot.
Divide the linked list recursively into 2 parts.

Now, if I always choose last element as pivot, then identifying the pivot element (1st step) takes $\mathcal O(n)$ time.

After identifying the pivot element, we can store its data and compare it with all other elements to identify the correct partition point (2nd step). Each comparison will take $\mathcal O(1)$ time as we store the pivot data and each swap takes $\mathcal O(1)$ time. So in total it takes $\mathcal O(n)$ time for $n$ elements.

So the recurrence relation is:

$T(n) = 2T(n/2) + n$ which is $\mathcal O(n \log n)$ which is the same as in merge sort with a linked list.

So why is merge sort preferred over quick sort for linked lists?

The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result.
At the same time the merge sort is external, it requires additional array to return ordered result. In array it means additional space overhead, in the case if linked list, it is possible to pull value out and start merging nodes. The access is more sequential in nature.

Because of this, the quicksort is not natural choice for linked list while merge sort takes great advantage.

The Landau notation might (more or less, because Quicksort is still $\mathcal O(n^2)$) agree, but the constant is far higher.

In the average case both algorithms are in $\mathcal O(n\log n)$ so the asymptotic case is the same, but preference is strictly due to hidden constant and sometimes the stability is the issue (quicksort is inherently unstable, mergsort is stable).

You can write merge sort , partition sort , tree sort and compare results
It is quite easy to write tree sort if you allow some extra space
For tree sort each node of linked list must have two pointers even if we sort
singly linked list
In linked list i prefer inserting and deleting instead of swapping
Hoare partition can be done only for doubly linked list

program untitled;

type TData = longint;
     PNode = ^TNode;
     TNode = record
                data:TData;
                prev:PNode;
                next:PNode;
             end;

procedure ListInit(var head:PNode);
begin
  head := NIL;
end;

function ListIsEmpty(head:PNode):boolean;
begin
  ListIsEmpty := head = NIL;
end;

function ListSearch(var head:PNode;k:TData):PNode;
var x:PNode;
begin
  x := head;
  while (x <> NIL)and(x^.data <> k)do
     x := x^.next;
  ListSearch := x;
end;

procedure ListInsert(var head:PNode;k:TData);
var x:PNode;
begin
  new(x);
  x^.data := k;
  x^.next := head;
  if head <> NIL then
     head^.prev := x;
   head := x;
   x^.prev := NIL;
end;

procedure ListDelete(var head:PNode;k:TData);
var x:PNode;
begin
   x := ListSearch(head,k);
   if x <> NIL then
   begin
     if x^.prev <> NIL then
        x^.prev^.next := x^.next
      else
        head := x^.next;
     if x^.next <> NIL then
        x^.next^.prev := x^.prev;
     dispose(x);
   end;
end;

procedure ListPrint(head:PNode);
var x:PNode;
    counter:longint;
begin
  x := head;
  counter := 0;
  while x <> NIL do
  begin
    write(x^.data,' -> ');
    x := x^.next;
    counter := counter + 1;
  end;
  writeln('NIL');
  writeln('Liczba elementow listy : ',counter);
end;

procedure BSTinsert(x:PNode;var t:PNode);
begin
  if t = NIL then
    t := x
  else
    if t^.data = x^.data then
            BSTinsert(x,t^.prev)
        else if t^.data < x^.data then
            BSTinsert(x,t^.next)
        else
            BSTinsert(x,t^.prev);
end;

procedure BSTtoDLL(t:PNode;var L:PNode);
begin
   if t <> NIL then
   begin
     BSTtoDLL(t^.next,L);
     ListInsert(L,t^.data);
     BSTtoDLL(t^.prev,L);
   end;
end;

procedure BSTdispose(t:PNode);
begin
   if t <> NIL then
   begin
    BSTdispose(t^.prev);
    BSTdispose(t^.next);
    dispose(t);
   end;
end;

procedure BSTsort(var L:PNode);
var T,S:PNode;
    x,xs:PNode;
begin
  T := NIL;
  S := NIL;
  x := L;
  while x <> NIL do
  begin
    xs := x^.next;
    x^.prev := NIL;
    x^.next := NIL;
    BSTinsert(x,t);
    x := xs;
  end;
  BSTtoDLL(T,S);
  BSTdispose(T);
  L := S;
end;

var i : byte;
    head:PNode;
    k:TData;
BEGIN
  ListInit(head);
  repeat
     writeln('0. Wyjscie');
     writeln('1. Wstaw element na poczatek listy');
     writeln('2. Usun element listy');
     writeln('3. Posortuj elementy drzewem binarnym');
     writeln('4. Wypisz elementy  listy');
     readln(i);
     case i of
     0:
     begin
       while not ListIsEmpty(head) do
            ListDelete(head,head^.data);
     end;
     1:
     begin
       writeln('Podaj element jaki chcesz wstawic');
       readln(k);
       ListInsert(head,k);
     end;
     2:
     begin
       writeln('Podaj element jaki chcesz usunac');
       readln(k);
       ListDelete(head,k);
     end;
     3:
     begin
       BSTsort(head);
     end;
     4:
     begin
        ListPrint(head);
     end
     else
        writeln('Brak operacji podaj inny numer');
     end;
  until i = 0;
END.

This code needs some improvements
  Firstly we should limit extra storage to the recursion needs
  then we should try to replace recursion with iteration
  If we want to improve algorithm further we should use self balancing tree


Can BNF consist of zero rules? I am trying to use BNF to describe its own grammar to get used to it. What I can not find any information about is whether BNF must consist of zero or more rules or one or more rules. The difference would be:

<grammar> ::= <grammar> <rule> | <rule>

vs.

<grammar> ::= <grammar> <rule> | ""

The only difference I can see is that an empty language can be described by an emtpy BNF in the second case, but must use <grammar> ::= "" in the first case.

Concretely speaking, the Backus-Naur form is a notation for context-free grammars, applied to the (formal) description of languages at the syntactical level.

While there are extended versions of BNF that have been standardized, the BNF itself hasn't, so there is no way of determining if the empty grammar is "legal" BNF.

As a mathematical object, the possibility of an empty grammar will depend on the definition (of grammar) used. A grammar that has no productions is usually said to define the empty language, but any grammar whose set of possible terminal derivations is empty is also a candidate definition of the empty language.

There is nothing logically wrong with allowing a grammar to have zero rules.  But such a grammar would be entirely useless, as it would not define any language (not even the empty-string by itself).


Efficiently finding the maximum pairwise GCD of a set of natural numbers Consider the following problem:
Let $S = \{ s_1, s_2, ... s_n \} $ be a finite subset of the natural numbers.
Let $G = \{$ $\gcd(s_i, s_j) \mid s_i, s_j \in S,$ $ s_i \neq s_j  \}$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$
Find the maximum element of $G$.
This problem can be solved by taking the greatest common divisor of each pair using Euclid's algorithm and keeping track of the largest one.
Is there a more efficient way of solving this?

Solution 1
Time Complexity: $\mathcal{O}(n\sqrt{\max(s_i)})$
Maintain an array, $\texttt{cnt}$, to store the count of divisors. For each $s_i$, find its divisors and for each $u$ in those divisors, increment $\texttt{cnt}[u]$ by one. The greatest GCD shared by two elements in $S$ will be the greatest $u$ where $\texttt{cnt}[u] > 2$.
For each $s_i$, we only need to check up to $\sqrt{s_i}$ for its divisors, so the complexity is $\mathcal{O}(n\sqrt{\max(s_i)})$.
Solution 2
Time Complexity: $\mathcal{O}(\max(s_i)\log(\max(s_i)))$
Given a value $x$, we can check whether there exists a pair with GCD equal to $x$ by counting all the multiples of $x$ in $S$ and checking whether that count is at least 2.
With that information, loop through all possible values of $x$ and keep the maximum one with at least two multiples in $S$. This works in $\mathcal{O}(\max(s_i)\log(\max(s_i)))$ time since
$$
\sum_{x = 1}^{\max(s_i)} \frac{\max(s_i)}{x} \approx \max(s_i)\log(\max(s_i)).
$$

Here is an efficient algorithm (in Python). Please find the explanation below.

def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S

    s = set(S)
    m = max(S)

    res = 0
    i = m

    while(i > 0):
        a = i
        cnt = 0
        while (a<=m): # a maxed at max of the list
            if a in s:
               cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i -1

    return res

Explanation of the above code snippet :

We observe the following in this problem:

The result can not be more than max(S)
The result is a number, that has two or more multiples in this list S
In-fact the result is max of all such numbers with the property mentioned above.

With these observations, the program does the following:

Make a set of the list. As sets can be searched efficiently in O(log(n))
Find the max of the list and store it in the variable m.
Starting from m till 1, find the first number that has two or more multiples in the set. The first such number found is the result.

I hope this is clear. Please let me know if you need a more detailed explanation.


Difference between Tail-Recursion and structural recursion Is there any difference between structural-recursion and Tail-recursion or they both are same? I see that in both of these recursions , the recursive function is called on the subset of the orignal items.

Structural recursion: recursive calls are made on structurally smaller arguments.
Tail recursion: the recursive call is the last thing that happens.

There is no requirement that the tail recursion should be called on a smaller argument. In fact, quite often tail recursive functions are designed to loop forever. For example, here's a trivial tail recursion (not very useful, but it is tail recursion):

def f(x):
   return f(x+1)

We actually have to be a bit more careful. There may be several recursive calls in a function, and not all of them need to be tail recursive:

def g(x):
  if x < 0:
    return 42             # no recursive call
  elif x < 20:
     return 2 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(x - 3)     # tail recursive

One speaks of tail recursive calls. A function whose recursive calls are all tail-recursive is then called a tail-recursive function.

Tail recursion is a very simple case of structural recursion, where the structure in question is a linked list.  In the language you are probably using primarily, this list is probably not literally in the code; rather, it is a conceptual "list of calls to the function", a concept that may not be possible to express as written using that language.  In Haskell (my language), any tail-recursive function call can actually be replaced by sequencing actions on a literal list whose elements literally are "calls to a function", but this is probably a functional-language thing.

Structural recursion is a way of operating on an object defined as a composite of other (possibly composite) objects.  For example, a binary tree is an object containing references to two binary trees, or is empty (thus, it is a recursively defined object).  Less self-referentially, a pair (t1, t2) containing two values of some types t1 and t2 admits structural recursion, although t1 and t2 need not also be pairs.  This recursion takes the form

  action on the pair = combination of the results of other actions on each element

which doesn't sound very profound.

It is often the case that a structural recursion cannot be tail-recursive, although any kind of recursion can be rewritten as a tail recursion (proof: if you run the original recursion, the actions are completed in a certain order; therefore, the recursion is equivalent to performing that particular sequence of actions, which as I discussed earlier, is tail recursion).

Either the binary tree or the pair example above demonstrate this: however you arrange the recursive calls on the subobjects, only one of them can be the last action; possibly neither one is, if their results are combined in some way (say, addition).  As Andrej Bauer says in his answer, this can happen even with only one recursive call, as long as the result is modified.  In other words, for every type of object other than those that are effectively linked lists (only one subobject all the way down), structural recursion is not tail recursion.


Can context-free grammar generate $a^{2^n}$? Context-free grammar can generate the string a 2 n    for n≥0 .

The production rule P is S→SS|a .

The derivations is, for example:

1) S⇒a  (this is when n = 0)

2) S⇒SS⇒aa  (this is when n = 1)

3) S⇒SS⇒SSSS⇒aaaa  (this is when n = 2)

4) S⇒SS⇒SSSS⇒SSSSSSSS⇒aaaaaaaa  (this is when n = 3).

Am I right?

Someone told me yes but it takes a very long time for big enough n;

someone told me no - that this grammar actually generates $a^+$ because it can be $S \Rightarrow SS \Rightarrow SSS \Rightarrow aaa$.

So, does this mean context-free grammar cannot generate the string $a^{2^n}$?

Is there exist any other context-free grammars that can generate this language?

It is well known (and not very difficult to prove) that a context-free language over a unary alphabet $\{a\}$ is regular.

Thus, your question is essentially, "is $\{a^{2^n}:n\in \mathbb N\}$ regular?"
And the answer to that is no (easy to prove using the pumping lemma).

I just realize that my question is the duplicate of this question, but I'll try to put additional answer here myself, now knowing that $a^{2^n}$ is a context-sensitive language, not a context-free language.

An example of the production rules to generate $a^{2^n}, n \geq 0$:

$S \rightarrow \lambda |AA$

$A \rightarrow AA$

Until the above part, it's okay with context-free grammar rules (the derivation being beautifully $S \Rightarrow AA \Rightarrow A^{2^2} \Rightarrow A^{2^3} \Rightarrow \dots$), but then how to change the non-terminal symbols $A$ to the terminal symbols $a$ is tricky. We cannot simply apply $A \rightarrow a$ because it can affect the numbers for example $S \Rightarrow AA \Rightarrow aAA \Rightarrow aaa$, which is not $a^{2^n}$.

This is where the context-sensitive grammar rule comes in handy, simply change both $AA$ to terminal symbols thus preserve the number of $a$'s generated as $a^{2^n}$, i.e.

$AA \rightarrow aa$.

The need to apply this rule is why this language is not a context-free language.


Counting trees in a graph I would like to know how to modify DFS/BFS in order to return the number of the trees present in a graph. I know that a tree is an acyclic connected graph, and I think that I have to initialize a counter somewhere, but I don't know where. I made the procedure "is-tree(G)" where G is the graph. It returns true if the subprocedure "is-connected(G)" also returns true and if the number of the arcs in G = number of nodes in G - 1, otherwise the procedure returns false. At this point I don't know how to count all the possibile subgraphs which are also trees.

So here is a pseudo code of what i proposed. Maybe i was not clear.

1) Start with a node (Your start node)

2) For each node from root node, try to find a node (if it exists) that has atleast one node that is not visited. (If the graph is a cyclic, this condition is true). To do this, you may use a hashset of visited children for each iteration.

3) do the above till you reach a node which has no children. Thats the end of the algo where you found 1 tree in the graph. For back tracking i think you want to maintain a hashmap of all the nodes that you started with and the value field contains all the connected nodes to the graph. The point you reach a leaf node without violating point(2), you start back tracking to find the parent of the current node; ie the leaf node to the start node.

Thats your subgraph which is a tree.

PS- Leaf node in this case would be a node which has no nodes connected to it/all the other nodes connected to it are already visited previously/only inward connections

So for each node in the graph, initially treat it as a n-ary tree, where it contains the following
class node{
int val;
List<node> = [List of all connected nodes]
}

Since you are doing BFS/DFS, you are sure to visit every node.

- For each node Check if the nodes in the above list has a leaf node.
- Keep a backtracking mechanism (using a map or any other data structure) which
   links to the root from where you started.
Thats your Tree inside the graph. Repeat it till all nodes are visited while updating the count when you get a tree.


Looking for an algorithm to solve a specific Vehicle Routing Problem I am trying to figure out a way to create routes for trucks to complete a list of orders(drops/stops), while minimizing distance traveled.

There is only ever 1 company warehouse in the area.
The trucks have to deliver based on capacity.
Each truck can hold a maximum (usually 18 pallets).
Each order will be for a number underneath that maximum.
There will be a maximum number of trucks specified.
When trucks are finished with their route, they will return to the company
warehouse.

I already have all of the orders, the pallets they are requesting, and the distance between each point.

I am an absolute simpleton when it comes to complex problems like these...  I am hoping that someone has a simple (relatively) solution, or an article of some sort that could help me down my path.

A metaheuristic would do. I would opt for a Large Neighbourhood Search (LNS), a Genetic Algorithm (GA), or Tabu Search (TS).


How to reduce this regular expression into DFA $(a(aa|b)^*ab|b)((ba|a)(aa|b)^*ab|bb)^*((ba|a)(aa|b)^*)^*|a(aa|b)^*$

I know long algorithmic procedures but since regex is large I tried a lot by substituting common patterns for some regex definition but didn't seem to help.

What can be done so that this regex can be converted to DFA easily.

What can be done so that this regex can be converted to DFA easily?

Algorithmic methods are doomed, if you insist on a DFA. Your regular expression contains about sixty characters. Roughly speaking, any procedure for converting to an automaton is going to produce at least one state per character of the regular expression. That means you're going to end up with an automaton with at least sixty states, and it's probably going to be nondeterministic. Determinizing that naïvely is going to give you $2^{>60}$ states, which isn't quite as many as the number of atoms in the earth, but it's still an unmanageably huge number.

Do you really need a DFA? If, for example, you're trying to write a program that will accept strings that match this regular expression, it's straightforward to check if an NFA accepts a particular string: just scan along the string keeping track of the set of states the automaton could be in after each successive character. For a fixed automaton, this can be done in linear time.

If you do need a DFA, you're going to have to figure out what the regular expression does. Break it into chunks.  $(a(aa|b)^∗ab|b)$ matches $b$, along with all strings that have an even number of $a$s, begin with $a$ and end $ab$. It's not too difficult to see that this language is matched by the following automaton (I've omitted a trap state that's reached if any character is read from state $q_3$):

If you stare at that for a moment, you'll realise that states $q_0$ and $q_2$ are the same (both say "if $a$, go to $q_1$; else, go to $q_3$") so we can reduce the automaton to the following.

You could also use algorithmic state-minimization techniques to avoid having to notice things like this.

You can probably produce similar automata for the various "top-level" chunks of the regular expression, and chain them together to get a DFA for the whole thing.

Thinking outside the box: You can use implementations of an algorithm to convert this RegEx to a DFA easily. Looking for regular expression to DFA online in your favorite search engine will lead you pages that allow you to convert the expression within the page. This is very easy and will give you results within a minute.


Automata with no transition for some character Given an automaton and an alphabet $\{a, b\} $,  and the language accepted by the automaton is $ab^*$.

Such an automata can be found here:

My question is: this automaton cannot process the word $ba$ for example. In general,  do automata have to be able to process any word?

In a deterministic automaton, every state must have exactly one transition for each symbol in the alphabet. In a nondeterministic automaton, this requirement is dropped and there could be multiple transitions or no transition for some symbol. If there is no transition for the next character in the string, the automaton rejects its input. This is what happens with the automaton on the left: it rejects the string $ba$ (and every other string beginning with $b$) because it has nowhere to go when it reads that first $b$.

An Automaton is supposed to accept only (all) strings that are in some language for which it is defined, and reject any string not in the language.

The automaton on the left, accepts all strings of from $\mathcal{L} = ab^* \equiv {a, ab, abb, abbb, abbbb, ... }$

strings are not commutative, i.e $ab \neq ba$

As you pointed out, it won't accept $ba$ since that's not in $\mathcal{L}$

and in general, automata accept any string in the language.

[by process i assume you mean accept/reject]


Why does Randomized Quicksort have O(n log n) worst-case runtime cost Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, as the worst case happens when randomly chosen pivot is selected in sorted or reverse sorted order. But in some texts [1] [2] its worst case time complexity is written as $O(n\log{n})$

What's correct?

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

Yes you are corect, it will be $O(n^2)$.

The worst case for randomized quicksort is same elements as input. Ex: 2,2,2,2,2,2

Here the algorithm whatever it picks will be $T(n) = T(n-1) + n$ and hence $O(n^2)$.


How huffman tree uses MinHeap? As far as I know, a minheap is data structure whose parent node's value is less than child node and maxheap is when parent node is greater than child node. Here they have used minheap. But as the node closer to root have less length code than nodes below that level i.e., level 1 codes will have shorter codes than level 5; which means level 1 nodes are more frequently occurring than level 5 nodes. Also the numeric value after addition is also greater than that nodes at high level. I am confused, isn't that definition of max heap but they are using min heap. Please explain why they are using Min heap and not Max heap (considering nodes at lower level are more frequent than at higher level)

Building a huffman tree is bottom up.

You start with the all the leave nodes with their frequency.
Then you select and remove the 2 nodes with the smallest frequencies
create and insert a new compound node with the 2 selected nodes and it's new frequency is the sum of the 2 nodes
if set has 2 or more nodes repeat from step 2

Selecting the 2 nodes with the least frequencies requires a min heap.

ih huffman code,not nodes value should  be considered.Only codes assigned should be considered.If u consider the code,only the upper level nodes will have least bit code


1-to-1 cryptographically secure bit shuffling Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes).  The function should have the following qualities:

It should be 1-to-1 so that all inputs map to some output and so that no two inputs map to the same output.
Given an output element it should be difficult to guess the input that lead to that output, even when the mapping is completely known.

Does such a function exist? Where can I learn more?

This is known as a one-way permutation.  The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements.  There are various candidate constructions for one-way permutations, e.g., based on raising to the third power modulo an RSA modulus or other schemes.

You could try this:

First, take the SHA-256 or other hash of your input value. Then use a basic cypher, something like the classic A=C, B=D, C=E...

The difference is that you use the SHA-256 of the entire input string to determine how much it is shifted by(is it A=B, A=C, A=D, etc.)

Note: I am not a cryptography expert and am not sure how secure this would be.


Why do particles in particle swarm optimization converge to the global best when their personal best has just as much weight? I know this is probably a really basic question but I just cant wrap my head around it right now.
So the basic PSO update formula is as follows:
$$\bar{v}_{n+1} = \omega \cdot \bar{v}_n + c_k \cdot r_1 \cdot (\bar{p}_{best}-\bar{p}_n)+ c_s\cdot r_2 \cdot (\bar{g}_{best}-\bar{p}_n) $$
velocity(n+1) = momentum_component + cognitive_component + social_component
Now both the cognitive part and the social part have the same weight to them on the updated velocity.
So when a particle is moving around the space and lets say the cognitive part pulls the particle in a certain direction while the social component pulls the particle in the opposite direction, shouldnt the particle be stuck forever? Or at least go back and forth never converging?
However if I run the basic vanilla PSO algorithm the particles always seem to converge to the gbest as if their pbest has barely any influence.

The random number biases distance along the vectors, so it changes per update helping in escaping local optimum, and the global best also changes during the algorithm, if you really want some of these answers try programming a visual particle system using PSO.


Efficient immutable data structure for small multi-sets of integer ranges? Background

I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure takes up around 80% of the execution time in insert and remove, so it's time to see if there's something better out there. I'm spending around 1400 clock cycles per insert or remove, so there should be some margin for improvement.

Current implementation

The current model, called Domain, is a fully persistent immutable ordered linked-list of [low, high) pairs, normalized so that for any time two ranges overlap, the first one is the longest. Touching ranges are also joined. Most domains consist of less than 100 ranges, but some consist of up to 10k ranges. The current data structure is chosen because it was easy to work with, avoiding premature optimization.

The Domain datastructure represents a multiset of integers. Internally representing ranges as [low, high) pairs is just an optimization. Since some domains cover many million of numbers, I don't think a multiset would be fast enough to be viable.

A range is a set of b-a unique integers x, a <= x < b, distinct from every previously defined range, with b-a as large as possible.

The operations

The operations supported right now are

insert(a,b) union of two domains, keeping duplicates
remove(a,b) a minus b
intersection(a,b)
ncov(a,n) a with n-1 copies of each present integer removed.
after(a,n) domain of everything in a equal to or greater than n
before(a,n) domain of everything in a equal to or smaller than n
minlen(a,l) domain of all ranges in a with a cardinality of at least l.
trunc_start(a,l) a with the l smallest integers removed from each range.
trunc_end(a,l) a with the l largest integers removed from each range.

Queries:

contains?(a,p) does the domain a contain a specified integer p?
covers?(a,b) is domain b a subset of domain a?
lowest(a) what's the lowest integer in the domain?
highest(a) what's the highest integer in the domain?

Behaviour

The most common use-case is to modify the structure a small bit at a time, from smallest value to biggest. Since inserts might modify the whole structure, the lists are almost always rebuilt completely right now. Changing the access pattern to bulk inserts and deletions is not feasible.

The second most common use-case is intersection between multiple (3+) domains, currently implemented as repeatedly calling the binary intersection function.

Questions

Is there a standard name of this data structure?
Is there a more efficient format? If so, which one(s)?
Would a tree be faster than a linked-list? With or without rebalancing?

I would suggest looking at interval trees and segment trees.  A natural representation is that the data structure contains a union of non-overlapping ranges $[l,u]$ with a multiplicity $m$; the intended meaning is that each integer in the range $l,l+1,l+2,\dots,u$ occurs in the domain with multiplicity $m$ (i.e., appears $m$ times), and the invariant is that the multiplicity of all integers within a single range is the same.

We can't tell you whether a tree would be faster in your application; that's workload-dependent, so the only way to tell is to try it and benchmark it and see.

This can be made persistent using standard techniques (e.g., path copying), if that's useful (e.g., if you have many domains that are similar to each other).

The Google Guava library has a RangeSet data structure that might satisfy some of your requirements. You can check out its implementation to see if it is what you need.

https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/RangeSet.html


Which of the following regular expressions generate(s) no string with two consecutive 1’s? This is a GRE practice question.

Which of the following regular expressions generate(s) no string with two consecutive 1’s? (Note that ε denotes the empty string.)

I. (1 + ε)(01 + 0)*

II. (01+10)*

III. (0+1)*(0+ε)

(A) I only

(B) II only

(C) III only

(D) I and II only

(E) II and III only

My understanding is that neither I nor III generates strings with 11. In I, a string containing 1 is either 1 or 1 surrounded by 0's. In III, all 1's are preceded by 0's. But the correct answer is A, so III must generate a string with 11 somehow. Please explain. Thanks!

III is $(0+1)^* (0+ \epsilon)$ which means pick a word from $\Sigma^*$ where $\Sigma = \{0, 1 \}$ and then concatenate it with either $0$ or $\epsilon$.

so III Does generate a string with two consecutive $1$'s. In fact it generates every string which contains $1$'s, $0$'s or is empty.

A is correct only.
In II:0110 string present which has two consecutive 11
In III also 11 contain from (0+1)* expression...


What is the difference between quantum computing and parallel computing? Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the difference or how are they different?

For a parallel computer, we need to have one billion different processors. In a quantum computer, a single register can perform a  billion computations. This is known as quantum parallelism. Also a quantum computer returns a single randomly-selected correct result, while a parallel computer can directly return all valid results. That's the reason why reading results out of quantum computers generally is slow and getting all results requires running the quantum computation enough times to be relatively certain that the random sampling has seen all possible results.
Hope this helps!
See this also: differences-between-quantum-computing-and-parallelism

One big difference is that in parallel computation separate processors need not be executing copies the same instruction at the same time in lockstep; they may be more loosely synchronized or in some cases completely desynchronized.  In fact, separate processors need not be executing the same sequence of instructions.  This is the distinction between SIMD [Single Instruction, Multiple Data] and MIMD [Multiple Instruction, Multiple Data] parallelism.  Quantum computers are by nature SIMD (interpreting quantum superposition as equivalent to processor replication).

Phrased another way: With multi-core you can run all the different processes on a laptop simultaneously; you cannot do that with a quantum processor.


Examples of processes / problems that cannot be tackled by Turing Machines I know that there are problems that cannot be solved by any algorithm, such as the Halting problem.
I also know that some processes cannot be even adequately approximated by any Turing Machine (equivalently, any digital computer), meaning that some property of the process cannot be simulated due to its intrinsic nature. An example of this would be Chaos, and its non-periodicity.

My question is: are there any other interesting processes in nature that really are outside the realm of what Turing Machines / digital computers can tackle? Any other interesting problems (outside from the well-known textbook ones) that Turing Machines cannot solve?

The reason why I ask for this is that I'm teaching to computer science students, and I want to make sure they understand that computers are not all-powerful machines, but there are problems and phenomena that lie fundamentally outside the realm of possibilities of any digital computer.
What powerful examples could I use, other than Chaos and the Halting problem, to support my argument?

Thank you!

I'll address as answer only part of the question (see my comments for why not all of it). The interesting phylosophical part of the question is basically asking if the Church-Turing thesis (CTT) describes all that happens in the universe. This is much more a physics question than it really is a CS question. CTT has been extended to the Church–Turing–Deutsch principle to account for quatum computers; it basically states that a quantum computer can simulate any physical process in the universe.

So what about continuous processes that we normally model over $\mathbb{R}$? Well, there are two aspects of this:

Models of computation with infinite-precision real-numbers have been devised. Whether you think such a model is the "right" one for physical processes, depends on physics and...
There are tough issues like the Bekenstein bound, which limit the amount of information that can exist in a finite region of space as we currently understand it. For details on this latter issue, it's much better to ask on our physics sister site.

A bit more info with pointer to additional readings is found at https://mathoverflow.net/questions/54820/physics-and-church-turing-thesis

it is known some problems in theoretical physics are undecidable. have not found a nice simple list/ survey. see eg these two refs.

Classical problem becomes undecidable in a quantum setting / physorg
Undecidability and intractability in theoretical physics / Wolfram. the basic idea here is that CAs, cellular automata nearly reflect physical processes and many aspects of CA behavior are undecidable. this was not realized early on in the study CAs when this paper was written.
another ref Church’s thesis meets the N-body problem / Smith asserts (with many refs) that physics is "unsimulable" by computers.


A question about type rule I realized that almost no one explained how to selected the type variable T1

 Γ ⊢ e1 : T1 -> T  ,  Γ ⊢ e2 : T1
 -------------------------------- T-APP
 Γ ⊢ e1 e2 : T

when doing type checking (from bottom to top).

So, the question is how T1 is introduced? Is there any condition about T1?

T1 is a schematic variable. Every consistent substitution of T1 with a type produces an instance of the rule. In a simple enough system, the inference rules can be used directly as the blueprint for a type-checking algorithm. In languages with richer type systems, type-checking algorithms become more complex or even undecidable (which is not a desirable features). Let me give an example where I type-check the program using a simple derivation.

Let's say I have the following program I wish to type-check:

(lambda x: nat. x = 0)(4)

First, we can deduce that 4 : nat by using the usual typing rules for natural numbers, which I will not reproduce here. Then we type-check the lambda abstraction with following derivation (I apologize for the sloppy latex):

$$ \underline{x : nat ⊢ x: nat \quad x: nat ⊢ 0 : nat} $$
$$ \underline{x : nat ⊢ x = 0 : bool}$$
$$ \underline{\lambda x: nat. \ x = 0 : nat \to bool} $$

Finally, using the application rules:

$$ \underline{\lambda x: nat. \ x = 0 : nat \to bool \quad 4 : nat} $$
$$ (\lambda x: nat. \ x = 0)(4) : bool $$

Note that type-checking is much simpler when we're working in a type system without subtyping, in that ever expression is monomorphic. The typing rules are syntax-directed. That is, the structure of the program dictates the type of every expression.

"T1" is obtained from typing context by doing derivation on the right branch of application rule. I worked on some type checking examples and concluded that.


Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s This is for formal-language-style regular expression and not about Unix-style regular expression.

I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings composed of only 0's, and doesn't accept strings composed of only 1's. The regular expression should only accept strings composed of 0's and 1's but without consecutive 1's.

Here's what I've seen so far: $(0+10)^*(ε+1)$

The problem is that it can accept empty string or just 1-character string 1. I would like to skip empty string and 1 since they are not strings of 0's and 1's.

I just couldn't find a good pattern. It seems that I have to create 2 regular expressions so that the first will be $(01+10)(0+1)^*$. If I am right, that will not accept empty string, will not accept just 0's, and will not accept just 1's. Then I would pass the result to the 2nd pattern $(0+10)^*(ε+1)$ to further validate that it has no consecutive 1's.

Could anyone explain what is the best solution to have the correct regular expression for strings of 0's and 1's?

I would suggest you to draw a small finite state automaton. Things to keep track in the states are "seen 0", "seen 1" and "last letter 1" (to avoid consecutive 1's).

There is an "official" algorithm to go from automaton to expression, but with small examples you usually can read the expression directly.

You can at least use two regex' in parallel instead of your chained solution. In Unix syntax it could look like this (should be easily translatable to your style):

(10+)+1?|(0+1)+0?

The first regex forces a group of zeros after every 1 while the latter forces a group of zeros before a 1.


Does it make sense to say Big Theta of 1? Or should we just use Big O? Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$?

Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying Big Theta over Big O in this case.

Remember your definitions! As $n \to \infty$ (the use in CS, almost always) $O(\cdot)$ is an upper bound (within a constant multiple, for large $n$), $\Omega(\cdot)$ is a lower bound (within a constant multiple, for large $n$), and $\Theta(\cdot)$ both of the previous. To see the difference, as $n \to \infty$ you have:

$\begin{align*}
  1 + \lvert \sin n \rvert
    &= O(1) \\
  1 + \lvert \sin n \rvert
    &= \Omega(1) \\
  1 + \lvert \sin n \rvert
    &= \Theta(1) \\
  e^{-n}
    &= O(1) \\
  e^{-n}
    &\ne \Omega(1) \\
  e^{-n}
    &\ne \Theta(1)
\end{align*}$

For the first three, as $\sin x$ moves between -1 and 1, the expression fluctuates between 1 and 2.

To see why $e^{-n} \ne \Omega(1)$ (and so $e^{-n} \ne \Theta(1)$), note that we are looking for a constant $c > 0$ and an $N_0$ so that for all $n \ge N_0$ we have $e^{-n} \ge c \cdot 1$. For any $c$ you pick, you'll find that taking $n > \ln 1 / c$ makes this false. So no $c$ works.

I went and looked it up for this question. "Big Theta" and "Big O" are defined slightly differently, but then found that "Big O" has different definitions depending on where you look.

Depending on who you ask, you can have an amortized "Big O" resulting in O(1) where every n operations, it would have to run a linear step rather than a constant and still label it O(1). We did it this way when I was in college. More information here: https://stackoverflow.com/questions/200384/constant-amortized-time

"Big Theta" is more precise in that everybody agrees on its definition in that such steps are not allowed.


Undecidability instance on a "find a proof/disproof" machine I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on:

Suppose we built the following machine in attempt to solve the halting problem. It takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I. It then tries every one-page proof that machine M never halts on input I. Then it tries every two-page proof of each, and so on and so on.

It's quite plain that this wouldn't necessarily always work. By incompleteness, there are statements that can't be proven true or false; it makes sense that there might be Turing machines that are equivalent to these statements. The undecidability problem assures that indeed these do exist.

So, let's follow that through. [Begin standard proof.] We have built this function $f(a,b)$ to return $1$ if it finds a proof that program $a$ halts on input $b$, and $0$ if it finds a proof that $a$ doesn't halt. (We note that this function $f$ might never return, so it's not total computable.) We can make a function $g(a)$ that first calls $f(a,a)$, and returns $0$ if $f(a,a)=0$, and enters an infinite loop if $f(a,a)=1$.

If $f(g,g)$ terminated and returned 0, then $g(g)$ would terminate and return 0 -- but $f(g,g)$ terminating and returning 0 implies it found a proof of $g(g)$ not terminating, so this is impossible. If $f(g,g)$ terminated and returned 1, then $g(g)$ would never terminate -- but $f(g,g)$ returning 1 implies it found a proof of $g(g)$ terminating. [End standard proof.]

This pair of paradoxes is used in the standard proof to show that there is no function $f$ that always returns $0$ or $1$. There's no problem here, though, because we allow $f$ to not terminate -- and so indeed, it must never terminate, when given the inputs $g$ and $g$.

Here's where I'm confused. Because $f(g,g)$ never terminates, this implies that there is no disproof to be found, because it tries all of them. Suppose that $g(g)$ terminated at some point. Then by running simply it for that many steps, we can see that terminates, and this constitutes a perfectly valid proof.

Keep in mind that $f$ is a real program, and so is $g$. We know that for these concrete values (in some numbering system), $g(g)$ can't terminate, otherwise $f(g,g)$ would find the dumb proof of simply running it to that point.

The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof, and use it to show that $g(g)$ doesn't terminate, but this is also a problem.

I'm sure there's something here I'm dramatically misunderstanding; I appreciate the time from anyone to answer.

So $f(M,I)$ is this machine that "takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I"...

That's fine, but later on you say "The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof."

That is not true, since you didn't write that proof as a formal proof in terms of "ZFC, let's say, or Peano arithmetic, or whatever", so there is no reason to expect $f(g,g)$ to find it.  You didn't even define $f(a,b)$ of $g(x)$ in terms that would translate into most such formal systems.

You assume that you would be able to specify a real formal system if you had to, with sufficient power to express $f$ and $g$ in concrete terms and prove what you say about them, but Godel's theorem says that's not necessarily so.

Furthermore, you say that $f$ and $g$ are real programs, but that is not true until this formal system is specified.  Because of this you have not proven what you set out to prove.  What you have proven is Godel's theorem -- any formal system that allows you to express your claim in terms of itself will either be inconsistent, or will not contain your proof.

It makes no sense because it falls. That is, the traditional breaker to the halting problem is an error of logic and not an actual disproof. As reference Ricky Demer's statement, it ends up not proving ZFC is inconsistent but that the original statement is paradoxical. Suffice it to say that if this were the only reason, we would be able to prove the matter for all non-self-referential cases and throw on all self-referential cases which would be good enough for all reasons we want to solve the halting problem.

I am in possession of a theorem that reads "There exists a set of laws of physics that admit the construction of a hyper computer that can solve the halting problem for the Turing machine, and in turn the Turing machine can solve its halting problem."

If we begin by positing the ability to construct the relativistic spacetime with the property of having infinite inverse time dilation but finite space contraction and finite blueshift we can place a Turing machine within. I once had in my hand a paper that described such a solution to general relativity and considered certain hyper-computer problems within but not the halting problem. If we admit that such a thing could exist in designer laws of physics I need make no more references to the paper I can no longer find.

The laws of physics demanded to construct the anomaly in turn always involves nasty beasts where inverse time dilation is available, and time travel would be available if the laws are anything like our own.

If we consider running a Turing machine in there and signaling by radio on halting, if we get a signal we know the machine halts. Barring breakdown (which we exclude in theory) we therefore know if we get no signal the Turing machine in question does not halt. Due to the infinite time dilation we need wait a finite time only. The downside of the time dilation is while we can receive a signal, we cannot decode it as it is arbitrarily fast. But the mere presence or absence is one bit, and that's all we need.

We may now construct the following machine: The machine accepts a Turing machine descriptor as input, constructs the spacetime anomaly described above with such a Turing machine as described on its tape within, and waits a certain amount of time for an answer (it knows exactly how long because it constructed the spacetime). Obviously this machine halts.

My theorem in turn forces 4-state logic to appear out of nowhere because it must be possible to represent the truth-value of such a beast as the self-halting-test involved, and the truth value is "inconsistent" or "paradox" depending on how you want to define it. (The remaining truth value is "independent"; that is our axioms cannot prove it either true or false at all, like C is to ZF).

We may construct a 4-state reasoning machine that can classify all statements (P) into their four categories as follows: Given a breadth-first theorem solver (the proof of existence is trivial), run A = halts(bredth-first-theorem-solver(P)) and B = halts(bredth-first-theorem-solver(!P)).

If A and not B then P is "true"
If not A and B then P is "false"
If A and B then P is "inconsistent"
If not A and not B then P is "independent" (of axioms)


Why did RSA encryption become popular for key exchange? This is a soft question.  I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message (e.g., the description of iMessage here).  Isn't this exactly the thing that Diffie-Hellman key exchange, which is older (and to me seems simpler) is for?  Looking at Wikipedia, they were also both patented, so this wouldn't have been responsible for the choice.

To be clear, I'm not asking whether it's theoretically important that public key cryptography is possible.  I'm asking why it became a standard method in practice for doing key exchange.  (To a non-cryptographer, DH looks easier to implement, and also isn't tied to the details of the group used.)

There is no strong technical reason.  We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA.

So why RSA?  As far as I can tell, non-technical historical reasons dominated.  RSA was patented and there was a company behind it, marketing and advocating for RSA.  Also, there were good libraries, and RSA was easy to understand and familiar to developers.  For these reasons, RSA was chosen, and once it was the popular choice, it stayed that way due to inertia.

These days, the main driver that has caused an increase of usage of Diffie-Hellman is the desire for perfect forward secrecy, something that is easy to achieve by using Diffie-Hellman but is slower with RSA.

Incidentally: It's Diffie-Hellman key exchange, not Diffie-Hellman secret sharing.  Secret sharing is something else entirely.

There is a dark side to this which cannot be overlooked.
The fact that the RSA was co-opted by the NSA.
The NSA planted a backdoor in the Eliptic Curve cyhper which it supplied to the RSA.
http://www.intelligence-world.org/nsa-infiltrated-rsa-security-more-deeply-than-thought-study/


Does the write through cache copies the whole block or just the byte which is updated? Just a basic question to ask

Does the write through cache copies the whole block or just the byte which is updated?

I went through the following question

Array A contains 256 elements of 4 bytes each. Its first element is stored at physical address 4096.
Array B contains 512 elements of 4 bytes each. Its first element is stored at physical address 8192. Assume that only arrays A and B can be cached in an initially empty, physically addressed, physically tagged, direct mapped, 2K-byte cache with an 8 byte block size. The following loop is the executed

for(i=0; i<256; i++)
A[i] = A[i] + B[2*i];

How many bytes will be written to memory if the cache has a write-through policy?

I calculated it as follows:

The cache can store the whole array with 2 elements per block (block size = 8bytes, element size = 4bytes). For every write, the whole block will be copied. For $0^{th}$ element, the block containing $0^{th}$ and $1^{st}$ element would be written. The same would be done for $1^{st}$ element as well.

So, for every iteration the 2 elements would be written. This makes the number of bytes as $256*2* (4bytes / element) = 2048bytes$.

But in the solution, they have just calculated the number of loop iterations ($256$) multiplied by the element size ($4byte$) which makes the answer $1024bytes$.
If this is true, then the cache would update only the updated byte (not the whole block).

Which is correct?

I would say that write-through cache always knows which addressable units need to be written, so there is absolutely no reason why it should write the rest of the block. Therefore it does not.

I am intentionally saying "addressable units", because (though I am not sure) it would generally be aligned units of the same width as the bus, i.e. usually 4-byte. But that has no effect here when the elements are 4-byte.

In contrast write-back cache is likely to only keep per-block modified status. However a write-back cache would be delaying the writes and since the consecutive passes through the loop end up overwriting whole blocks, it would still write just 1024 bytes.

A cache works by transferring a block at a time from/to RAM, so it copies a full block.


How to prove that 3-coloring is decidable? In order to prove that 3-coloring is decidable, is it sufficient to say:

Each node in the graph has 3 possible colors
Therefore we can enumerate over all $3^n$ possibilities and then check that no two edges connect nodes with the same color

Does that prove that 3-coloring is decidable?  Or do I need to construct a Turing machine for a proper proof?

By 3-coloring I'm talking about the graph coloring problem; i.e. assign one of 3 colors to each node in an undirected graph such that no two adjacent nodes have the same color.

It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince me that 3-colourability is decidable. If you wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to be even more formal, you could write down the full description of the Turing machine and prove that it really does decide 3-colourability.

Having said that, of the options I've listed, it's way more likely that there'd be an error in the description of the Turing machine or in its correctness proof! So it's not clear which proof would be the most believable.

All the non deterministical problems for TM are decidable, so from your description you demonstrated you needed $ 3^{n}$ turing machines to validate a solution. So your explanation is enough.


Question about time-complexity for MST-like algorithm I have got a problem with an excercise about graphs:

Your friend has been hired by a brewery to work out the most efficient
delivery route for the beer-delivery truck drivers. A typical delivery has about 50 stops and the company wants to save money by driving the
shortest possible distance. Your friend ignores your advice and decides on an algorithm, as follows:

Start at the depot,
Go to the nearest location that has not yet been
delivered to:

Deliver
Repeat until you have delivered all the beer

Return to depot

And the quesiton is:
What is the Big-O complexity of this approach? Why?

I do not think this way of solving problem is any algorithm like Prim's algorithm, and I have no clue what can be a complexity. Could anyone explain me?

This problem looks variant of TSP problem(more precisely metric TSP). As you want to traverse all node with the minimum distance.

TSP is one of the classical NP-Hard problem.

What your friend did is a Greedy approach making minimum Spanning tree Which is 2-Approx(metric-TSP) of the minimum distance.

This greedy approach generally works in E log V time but does not have guarantee for exact solution.

By using graph structure we can implement in linear time also.

E(logV) where E is the number of edges in the graph and V is the number of nodes i.e. here number of stops=50
So, E log50 will be the time complexity


How do I know which direction I should rotate a node in an AVL Tree? I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL Trees. We're given the numbers $100,50,25,10,37,32,200$. Creating an AVL Tree until $37$ wasn't that difficult but then I got stuck at balancing out the tree when I insert $32$. The following is my method:

Now I know that there is a conflict at $52$ but since it has 3 nodes (LRL), I don't understand how I should rotate. I think, I should get $37$ as the root node $25$ as it's left child and $52$ as it's right child but I dunno.

I think, I should get 37 as the root node 25 as it's left child and 52 as it's right child but I dunno.

You plan is correct.

What you need to do is a left-right rotation as shown in the third column of the table below. That is,  a left rotation at node 25 followed by a right rotation at 52. It is symmetric to the right-left rotation as shown in the fourth column and as explained in Wikipedia.

1st step : Left-Left rotation.
2nd & 3rd step :Left-Right Rotation.
4th step: Right-Right Rotation.
5th is Final AVL tree.

https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm


How can a language whose compiler is written in C ever be faster than C? Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler  originally written in C, outperform C code?

Figure: benchmark times relative to C (smaller is better, C performance = 1.0).

There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, because its code is written in a slow language. (To be more precise, written in a language with a slow implementation. Languages aren't really inherently fast or slow, as Raphael points out in a comment. I expand on this idea below.) The compiled program would be as fast as its own implementation allowed—we could write a compiler in Python that generates the same machine code as a Fortran compiler, and our compiled programs would be as fast as Fortran, even though they would take a long time to compile.

It's a different story if we're talking about an interpreter. Interpreters have to be running while the program they're interpreting is running, so there is a connection between the language in which the interpreter is implemented and the performance of the interpreted code. It takes some clever runtime optimization to make an interpreted language which runs faster than the language in which the interpreter is implemented, and the final performance can depend on how amenable a piece of code is to this kind of optimization. Many languages, such as Java and C#, use runtimes with a hybrid model which combines some of the benefits of interpreters with some of the benefits of compilers.

As a concrete example, let's look more closely at Python. Python has several implementations. The most common is CPython, a bytecode interpreter written in C. There's also PyPy, which is written in a specialized dialect of Python called RPython, and which uses a hybrid compilation model somewhat like the JVM. PyPy is much faster than CPython in most benchmarks; it uses all sorts of amazing tricks to optimize the code at runtime. However, the Python language which PyPy runs is exactly the same Python language that CPython runs, barring a few differences which don't affect performance.

Suppose we wrote a compiler in the Python language for Fortran. Our compiler produces the same machine code as GFortran. Now we compile a Fortran program. We can run our compiler on top of CPython, or we can run it on PyPy, since it's written in Python and both of these implementations run the same Python language. What we'll find is that if we run our compiler on CPython, then run it on PyPy, then compile the same Fortran source with GFortran, we'll get exactly the same machine code all three times, so the compiled program will always run at around the same speed. However, the time it takes to produce that compiled program will be different. CPython will most likely take longer than PyPy, and PyPy will most likely take longer than GFortran, even though all of them will output the same machine code at the end.

From scanning the Julia website's benchmark table, it looks like none of the  languages running on interpreters (Python, R, Matlab/Octave, Javascript) have any benchmarks where they beat C. This is generally consistent with what I'd expect to see, although I could imagine code written with Python's highly optimized Numpy library (written in C and Fortran) beating some possible C implementations of similar code. The languages which are equal to or better than C are being compiled (Fortran, Julia) or using a hybrid model with partial compilation (Java, and probably LuaJIT). PyPy also uses a hybrid model, so it's entirely possible that if we ran the same Python code on PyPy instead of CPython, we'd actually see it beat C on some benchmarks.

Code written in a language X whose Compiler is written in C, can outperform a code written in C, provided, C compiler does poor optimization compared to that of language X. If we keep optimization out of  discussion then if compiler of X could generate better object code than that generated by C compiler, then also code written in X may win the race.

But if language X is an interpreted language, and the interpreter is written in C, and if we assume that interpreter of language X and code written in C is compiled by same C compiler, then in no way code written in X going to outperform code written in C, provided both implementation follow same algorithm and uses equivalent data structures.