Efficient compression of unlabeled trees Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with pointers to $T$. See uli's answer for an example.

Give an algorithm that takes a tree in the above sense as input and computes the (minimal) number of nodes that remain after compression. The algorithm should run in time $\cal{O}(n\log n)$ (in the uniform cost model) with $n$ the number of nodes in the input.

This has been an exam question and I have not been able to come up with a nice solution, nor have I seen one.

Yes, you can perform this compression in $O(n \log n)$ time, but it is not easy :) We first make some observations and then present the algorithm. We assume the tree is initially not compressed - this is not really needed but makes analysis easier.

Firstly, we characterize 'structural equality' inductively. Let $T$ and $T'$ be two (sub)trees. If $T$ and $T'$ are both the null trees (having no vertices at all), they are structurally equivalent. If $T$ and $T'$ are both not null trees, then they are structurally equivalent iff their left children are structurally equivalent and their right children are structurally equivalent. 'Structural equivalence' is the minimal fixed point over these definitions.

For example, any two leaf nodes are structurally equivalent, as they both have the null trees as both their children, which are structurally equivalent.

As it is rather annoying to say 'their left children are structurally equivalent and so are their right children', we will often say 'their children are structurally equivalent' and intend the same. Also note we sometimes say 'this vertex' when we mean 'the subtree rooted at this vertex'.

The above definition immediately gives us a hint how to perform the compression: if we know the structural equivalence of all subtrees with depth at most $d$, then we can easily compute the structural equivalence of the subtrees with depth $d+1$. We do have to do this computation in a smart way to avoid a $O(n^2)$ running time.

The algorithm will assign identifiers to every vertex during its execution. An identifier is a number in the set $\{ 1, 2, 3, \dots, n \}$. Identifiers are unique and never change: we therefore assume we set some (global) variable to 1 at the start of the algorithm, and every time we assign an identifier to some vertex, we assign the current value of that variable to the vertex and increment the value of that variable.

We first transform the input tree into (at most $n$) lists containing vertices of equal depth, together with a pointer to their parent. This is easily done in $O(n)$ time.

We first compress all the leaves (we can find these leaves in the list with vertices of depth 0) into a single vertex. We assign this vertex an identifier. Compression of two vertices is done by redirecting the parent of either vertex to point to the other vertex instead.

We make two observations: firstly, any vertex has children of strictly smaller depth, and secondly, if we have performed compression on all vertices of depth smaller than $d$ (and have given them identifiers), then two vertices of depth $d$ are structurally equivalent and can be compressed iff the identifiers of their children coincide. This last observation follows from the following argument: two vertices are structurally equivalent iff their children are structurally equivalent, and after compression this means their pointers are pointing to the same children, which in turn means the identifiers of their children are equal.

We iterate through all the lists with nodes of equal depth from small depth to large depth. For every level we create a list of integer pairs, where every pair corresponds to the identifiers of the children of some vertex on that level. We have that two vertices in that level are structurally equivalent iff their corresponding integer pairs are equal. Using lexicographic ordering, we can sort these and obtain the sets of integer pairs that are equal. We compress these sets to single vertices as above and give them identifiers.

The above observations prove that this approach works and results in the compressed tree. The total running time is $O(n)$ plus the time needed to sort the lists we create. As the total number of integer pairs we create is $n$, this gives us that the total running time is $O(n \log n)$, as required. Counting how many nodes we have left at the end of the procedure is trivial (just look at how many identifiers we have handed out).

Edit:
 I read the question as T and T′ were children of the same parent.  I took the definition of compression to be recursive as well, meaning you could compress two previously compressed subtrees. If that's not the actual question, then my answer may not work.

$O(n \log n)$ begs for a $T(n) = 2T(n/2) + cn$ divide and conquer solution.
Recursively compress nodes and compute the number of descendants in each subtree after compression. Here's some python-esque pseudo code.

def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1

Where hasSameStructure() is a function that compares two already compressed subtrees in linear time to see if they have the exact same structure. Writing a linear time recursive function that traverses each and checks if the one subtree has a left child every time the other one does etc. shouldn't be hard.

Let $n_\ell$ and $n_r$ be the sizes of the left and right subtrees respectively (after compression). Then the running time is
$$
T(n) = T(n_1) + T(n_2) + O(1) \mbox{ if $n_\ell \neq n_r$}
$$
and $$
2T(n/2) + O(n) \mbox{ otherwise}
$$


Find shortest paths in complement graph I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, where $E$ is the number of edges in the original graph (not the complement graph).

If $G$ is a graph, the complement graph is defined to be the following graph: $e$ is an edge in the complement graph, if and only if it isn't an edge in the original graph. In other words we delete all existing edges, and add all the edges that were missing from the original graph.

So first I of course thought of "building" the complement graph (replacing the vertices in the adjacency list with those that don't appear there), then running BFS on the new list, but of course that would mean that the run-time would be based on the edges in the complement graph, not the original one.

I also noticed of course that after running BFS on the original graph, any vertex that has a distance from $s$ that is greater than 1 (in the original graph) should become 1 in the complement graph (because if they weren't neighbors in the original graph, they are neighbors in the complement graph). But I couldn't get the algorithm to continue according to some specific rules as to when should the distance be updated and to what.  Any suggestions?

I personally, do not see why this is left as unanswered.

Finding something in complement graph and finding that same thing in the graph is essentially have the same time complexity (up to constant factor).

Since swapping between edge $(u,v)$ and non-edge $(u,v)$ is just $O(1)$-time operation. We do not have to transform or convert anything just negate every query output.


Is the empty string of even length? There is this example of regular expressions:

$$(\Sigma\Sigma)^*= \{w\mid |w|\text{ is even}\}\,.$$

From that I understand the empty string is valid as a string of even length. Is this true?

A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.

Yes, that's correct. Empty string is valid as string of even length.

If you consider any language of even length of strings, it will also include an empty string.So, it is true.


Finding a source of a directed acyclic graph in linear time Given a directed acyclic graph $D = (V,A)$, a vertex $v \in V$ is a source if its indegree is zero, meaning that it has only outgoing arcs.

Does there exist a linear time algorithm to find a source in a given directed acyclic graph?

Follow-up question:  Can one in linear time find all sources?

As Yuval mentions, the datastructure is important here. I'll try to give a solution for some of the types of adjacency lists:

Incoming edge list: For each node, there is a list of vertices from which there is an incoming edge to this node. You can simply scan all vertices and check if the size of their adjacency list is $0$  or not. A size $0$ list means no incoming edges, so the node is either a source or disconnected. Assuming a connected graph, this scan of each vertex will give you a list of all sources (or you can stop after finding one) in $O(|V|)$ time - linear in the number of vertices.
Outgoing edge list: For each node, there is a list of vertices to which there is a directed edge from this node. Keep a bit-string with each bit representing a vertex, initialized to 0. Starting from the first node, start scanning its list for vertices to which there is an outgoing edge from this. Every such node (neighbour) cannot be a source, so keep setting their corresponding bit in the bit-string. At the end, all vertices whose corresponding bits are still unset, are the source vertices. You can do this in time linear in the size of the graph - $O(|V| + |E|)$.
Both lists together: For each vertex, there is a mixed list of vertices which have an edge to or from this vertex, with some other attribute indicating which of the two is actually the case. The approach is similar to 2 above, with the addition that any incoming edge immediately rules out the current vertex (and you can mark its bit set). Unlike in point 2 where you need to go through all vertices, here, you might find some source sooner. If you don't stop, you will have all sources. For both cases, time is again linear in the size of the graph - $O(|V| + |E|)$.
Both lists separately: Just pick the incoming edge list and follow 1.

As a side note, if choosing the datastructure is in your hands, you might want to analyze what all operations you intend to perform, and how frequently, and choose an appropriate datastructure.

Edit: For case 1, if you have a dag where the number of sources is very small as compared to $|V|$ (eg, in a tree with one source), and where the average distance from any vertex to a source is small as compared to $|V|$ and you only want any one source, you can use a faster on average algorithm (although worst case asymptotic complexity will be the same). Select any vertex at random, and go to any of its parent (from the incoming edge list), and on to its parent and so on, till you reach a node which has no parent - a source. This small gain of efficiency is for very limited types of graphs with a slightly more complex algorithm.

Assuming you have a graph G=(V, E) given in adjacency list format. (to be clear here the list contains all outgoing edges from the source). You can construct the inverse of the graph G in linear time.
Then you can iterate over the inverse graph and collect all vertices that have empty adjacency list. These vertices have no outgoing edge in the inverse graph which means they have no incoming edges in the original graph, therefore, these are your source vertices.

The running time is linear. Constructing the inverse of the graph takes a max of O(|V|+|E|) time. Iterating over the inverse of the graph takes O(|V|) time.


Name of binary encoding scheme for integer numbers I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute variable length code. Basically it used $\log_2n$ for some symbols and $\log_2n - 1$ for some others.

Unfortunately all my Googling has failed me. I recall something similar to "variable length binary", but I keep ending on VLQ which are a different beast. Since I know your memory better than mine, can you help me?

The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart from a mention in a patent, in this book, or in this Google API
Another mention can be found in the ACM ICPC 2011–2012, Northeastern European Regional Contest, November 27, 2011.

Usually (a, b) is an open interval, excluding a and b, and [a, b] is a closed interval, including a and b. So $(2^{n-1}, 2^n)$ is the set of numbers from $2^{n-1} + 1$ to $2^n-1$.
To encode, subtract $2^{n-1}+1$ from a number x, leaving $0 ≤ x < 2^{n-1}-1$. There are $2^{n-1}-1$ possible numbers, each with same probability, so you can use Huffman coding for just under n-1 bits on average. To be precise, you have $2^{n-1} - 2$ numbers encoded in n-1 bits, and one number encoded in n-2 bits, for an average of $n-1-1/(2^{n-1}-1)$ bits.
You could use arithmetic coding, which would be a tiny, tiny bit shorter on average with a very good implementation, but would be much much more complicated. Not worth it in this case; possibly worth it if you had say $1.5 \cdot 2^n$ different numbers to store and storage size is very important to you.


Throwing an error when initializing an object in c++ Let's say that when initializing a pet class, I wanted to exclude or disallow dogs or cats as species. What would be the proper way to throw an invalid_argument exception?

using std::string;
#include <stdexcept>
using std:: invalid_argument;
struct Pet {
  const string name;
  long age = 0;
  const string species;
  Pet() : name("Dan"), age(0), species("alligator"){}
  Pet(const string & the_name, const string & the_species): name(the_name),
  species(the_species), age(0) {};
};

Pet(const string & the_name, const string & the_species): name(the_name), species(the_species), age(0)
  {

     if (species == "cats" || species == "dogs")
        throw std::invalid_argument( "received negative value" );
  }


How to reverse a subarray of an array How to reverse the order of elements in an array between indices $i$ and $j$.
Ex: For the array [A,B,C,D,E,F], calling the function reverse(array, 1,4) will modify the array to be [A,E,D,C,B,F].
I want to optimize the solution to work with multiple calls on the same array, so pre-computations allowed. What would be the most efficient way to do so?

Let me restate the problem.  We're given an array $A_0$ and a sequence $(\ell_1,r_1),\dots,(\ell_m,r_m)$.  Set $A_{i+1}=\text{reverse}(A_i,\ell_i,r_i)$.  The goal is to compute the array $A_m$.

The naive way to solve this is to just incrementally apply the reverse operations, i.e., incrementally invoke Yuval's reverse algorithm $m$ times.  The running time of the naive solution is $\sum_{i=1}^m (r_i-\ell_i)$.  The question is, can we do better?

The answer is, yes, in some cases.  It's possible to build a data structure to optimize the sequence of reversal operations, in a way that's faster than the naive solution.  With sufficient cleverness, you can get the total running time down to $O(n + m \lg n)$ -- in comparison, the naive algorithm could potentially be as large as $O(nm)$, in the worst case.  I'll explain how to do it below.

We can model the desired rearrangement by a permutation $\pi$ on the array indices.  Such a permutation acts on arrays: given any array $\pi$ and any permutation $\pi$ on the indices, we can obtain an array $\pi A$, namely, the array $A'$ given by $A'[\pi(j)]=A[j]$.  Notice that the operation $\text{reverse}(A,\ell,r)$ should return the array $\pi A$, where $\pi(j)=\ell+r-j$ for $\ell \le j \le r$ and $\pi(j)=j$ for all other $j$.  Let $\text{rev}(\ell,j)$ denote this permutation.

This gives us a new strategy for solving the problem: first, compute $\pi = \text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_1,r_1)$; then, compute $A_m = \pi A_0$.  The latter step can be done in $O(n)$ time, with no additional space.  So, how quickly can we compute $\pi_m$?

Here is one way to compute $\pi_m$.  We will represent a permutation $\pi$ as an interval tree, i.e., a binary tree where each leaf has an interval on the indices.  The intervals on the leaves will be pairwise disjoint, their union will be $\{1,2,\dots,n\}$, and they will be in sorted order (from left to right).  Each internal node will hold an interval representing the union of the intervals on all of its descendants.  Also, we'll annotate each leaf with an affine function of the form $f(x)=x+\alpha$ or $f(x)=\alpha-x$.  The idea is that if we have a leaf with interval $[a,b]$ and function $f$, then $\pi(j)=f(j)$ for $j=a,a+1,\dots,b$.

In this way, we can represent a permutation as this sort of interval tree.  Notice that the identity function can be represented as an interval tree with one leaf, with interval $[1,n]$ and function $f(x)=x$.  Also, the permutation $\text{rev}(\ell_m,r_m)$ corresponding to a single reversal operation can be represented as an interval tree with three leaves, namely $[1,\ell_m-1],f(x)=x$, $[\ell_m,r_m],f(x)=\ell_m+r_m-x$, and $[r_m+1,n],f(x)=x$.

Now suppose we have an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$.  Let me explain how to derive an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$.  Basically, we search the interval tree to find all leaves whose interval overlaps with $[\ell_i,r_i]$, and split them in two pieces if they partially overlap (one piece that doesn't overlap, the other piece containing the rest that is contained within $[\ell_i,r_i]$).  Then, for each such leaf that overlaps $[\ell_i,r_i]$, if it currently contains the function $f$, we replace it with the function $g \circ f$, where $g(x)=\ell_i+r_i-x$.

So, we iteratively do this.  When we're done, we have an interval tree representation of $\pi$.  Now we can compute $\pi A_0$ in linear time.  The running time to construct the interval tree is now dependent on the number of intervals that get treated differently.  In other words, say that indices $j,j'$ are treated differently if there exists some $i$ such that $j\in [\ell_i,r_i]$ but $j'\notin [\ell_i,r_i]$ (or vice versa); otherwise, say that $j,j'$ are treated the same.  Now construct the equivalence classes of the "treated the same" equivalence relation.  Each equivalence class is one interval in the final interval tree, so the total running time is related to the total number of such equivalence relations.  In particular, if there are $k$ intervals in the final interval tree (i.e., $k$ such equivalence classes), then the running time is $O(mk+n)$.

It's possible to speed this up even further by annotating each internal node with an affine function as well.

The idea is that such an interval tree represents a permutation $\pi$ as follows: if we have a leaf with interval $[a,b]$ and function $f_0$, and its parent has function $f_1$, and its grandparent function $f_2$, and so on up to the function $f_d$ on the root, then for every $j \in [a,b]$, we have $\pi(j) = (f_d \circ \cdots \circ f_1 \circ f_0)(j)$.  In other words, the effective function on this leaf is the composition of all of the functions on the path from the leaf to the root.

This tree representation is even better: it allows you to derive the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$ from the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$ in $O(\lg k)$ time, where $k = $ the number of intervals in the tree.  Basically, we may have to split at most two intervals (one on the left side, if it partially overlaps $[\ell_i,r_i]$ on the left, and one on the right).  Then, we need to compose a function $g(x)=\ell_i+r_i-x$ to all of the leaves whose intervals is contained within $[\ell_i,r_i]$.  The latter can be done by identifying $O(\lg k)$ nodes of the tree whose (disjoint) union is $[\ell_i,r_i]$ (by construction you can always find such a set of nodes), and then composing $g$ with the function at each of those nodes: for each such node, if its function was $f$, you update it to $g \circ f$.

Consequently, the total running time of this improved solution is $O(n + m \lg k)$, where $k$ is the number of intervals in the final interval tree.  A conservative upper bound is $O(n + m \lg n)$ to perform $m$ reversal operations on an array of size $n$.  This is better than the naive algorithm, whose running time could be as bad as $O(nm)$.

Hope this works, the code is self explanatory and is in c#

     private static void ReverseSubArray(ref char[] SourceArray, int i, int j)
    {
        int len = SourceArray.Length;
        if (i > len || j > len)
        {
            Console.WriteLine("Improper Index Supplied !");
            Console.ReadLine();
            return;
        }
        else
        {
            int arrayLen = (j - i) + 1;
            char[] NewArray = new char[arrayLen];
            for (int index = i, localIndex = 0; index <= j; index++, localIndex++)
            {
                NewArray[localIndex] = SourceArray[index];
            }
            Array.Reverse(NewArray);
            for (int index = i, localIndex = 0; index <= j; index++, localIndex++)
            {
                SourceArray[index] = NewArray[localIndex];
            }
            Console.WriteLine("Task Done !");
            return;
        }
    }


Steps that guarantee exiting a maze Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting the maze?  I'm looking for a single sequence of commands that will work no matter where in the maze you start from.

Assume that if our partner is given the "move right" command when there's a wall on the right, he will simply stay where he is.

In other words, we're given a maze, and we must choose a sequence of commands.  Then, our partner will be placed somewhere in the maze and will follow the sequence of commands we've chosen in advance.  We want this sequence to ensure our partner will escape, no matter where our partner was initially placed.  Note that the allowable commands do not have any conditional statements, so they cannot follow a different sequence depending on your partner is.

Is there a polynomial-time algorithm to construct such a sequence, given a description of the maze?

Yuval Filmus mentions this is a special case of a synchronizing word problem, and might be related to universal traversal sequences.  I also found a paper that seems relevant:

The Simultaneous Maze Solving Problem.  Stefan Funke, André Nusser, Sabine Storandt.  AAAI 2017.

Unfortunately for general graphs this appears to be a unsolved problem, but I'm wondering if there might be a good algorithm for this specific case.   I came up with a candidate approach: Label every position with the number of minimum steps it requires to exit, and keep track of every agent in the maze. It might be possible to do a A* search this way.

An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $A^*$ (A-star) algorithm, it was originally designed for just such tasks).


Application of the four color theorem I was reading up on the four color theorem and am wondering if there is any practical application of it. (I dont think seperating the map into four different colors can be considered an application.)

I tried Googling for applications but couldn't find any.

One of the 4 Color Theorem most notable applications is in mobile phone masts. These masts all cover certain areas with some overlap meaning that they can’t all transmit on the same frequency. A simple method of ensuring that no two masts that overlap have the same frequency is to give them all a different frequency. But, as the government owns all frequencies and charge for each, one wants to use the minimum possible number of frequencies. The areas covered can be drawn as a map and the different frequencies can be represented as colors.

yes planar graph $n$-coloring for low/fixed $n$ has minimal applications, mainly planar map coloring. however $n$-coloring for arbitrary $n$ is NP complete, it was one of the 1st problems proven NP complete, hence tying into the massive edifice of theory. but actually even $n$-coloring can be reduced to 3-coloring via a basic transformation.[1] so $n$ coloring for $n \geq 3$ is NP complete (but not restricted to planar graphs). there are probably other reductions to 4-coloring & planar maps studied in the literature. ie to get a better feel of its significance one would have to study the possible reductions to it which is a complex/advanced/wideranging topic.

but another angle is that the question of 4-coloring of a planar map/graph was a difficult open problem in mathematics/computer science for many decades (actually over 1½ century old, and one of the earliest highly advanced graph problems). mathematics advances through solving unsolved problems. it fits into a common core pattern of "problems that are easy to state but the solutions/proofs were inaccessable for a long time and are very complex". this is a fundamental asymmetry widespread in math that shows the limits of mathematical/theoretical leverage.

the techniques that are found to succeed can be applied to other unsolved problems and sometimes open new theoretical/conceptual vistas/abstractions. sometimes remarkable proofs are valuable in their own right and the 4-Color theorem fits this category. it is one of the most sophisticated early automated theorem proofs. further work has gone into improved human-readable simplifications since it was discovered and caused a relative shock through the theoretical community on its announcement, and sparked much further analysis and commentary. it serves as a key benchmark/milestone/test case for improvements in automated theorem proving.

[1] 3 coloring is NP complete


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

Is it known whether most halting bitstrings will expand?

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

Both can happen.

The counting argument applies to all TMs that always halt.

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

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

and

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

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

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

There are a finite number of bitstrings with a length less than the output, but an infinite number with greater length.  Therefore, it is much more likely a halting bitstring will produce a shorter bitstring than a longer bitstring.


Compute height of AVL tree as efficiently as possible Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$

Each node of an AVL tree stores its balance factor ($\bf$), defined as

$$\bf(v)=\height(v.\text{left}) - \height(v.\text{right}).$$

We can recursively compute the height of an AVL tree in $O(\log n)$ time, using the following recursive procedure:

Height($v$):
1. If $v$ is a leaf node, return 0.
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
3. If $\bf(v)=-1$, return Height($v.\text{right}$).
4. If $\bf(v)=0$, return Height($v.\text{left}$). (returning Height($v.\text{right}$) would work too)

This recursive algorithm works, because the balance factor tells us which is taller, the left subtree or the right subtree, and the algorithm always recurses into the taller subtree.

My question is: Is there a faster algorithm?  Can we do better than $O(\log n)$ time?  Assume we can't augment the tree to store extra information in it; we are restricted to only the information that is already normally stored in an AVL tree.

No.  There's a $\Omega(\lg n)$ lower bound.  You can't do better than $O(\lg n)$ time.  In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree.

Let $T_1$ be a tree of height $H$, where the balance factor at every node at all but the bottom two levels is 0.  In other words, it is a perfect binary tree of height $H$, except that some subset of the leaves are missing; at the level above the leaves, all nodes have balance factor $+1$, $0$, or $-1$; and at all levels above that, the balance factor is $0$.

Let $T_2$ be an analogous tree of height $H+1$, i.e., it has height $H+1$ and the balance factor at all but the bottom two levels is 0.

Both $T_1$ and $T_2$ are AVL trees.

Now note that any algorithm has to visit at least $H-1$ nodes to distinguish $T_1$ from $T_2$.  Their first $H-2$ levels look identical (every node has two children and has balance factor 0), so you can't tell them apart until you have visited at least $H-1$ nodes.  To count as a correct algorithm for this problem, the algorithm has to produce the right answer on both $T_1$ and on $T_2$.

Consequently, any algorithm has to have worst-case running time at least $H-1$, i.e., $\Omega(H)$.

For every node in the AVL, we keep the height of the node as well - so that the balance factor can be calculated in constant time. Can you expand the definition for your "height()" function?


How many bits representation of data on tape of Turing machine consumes I am wondering how to represent signed number, vector, matrix on binary tape of Turing machine to consume the smallest possible amount of memory.

For signed number it is obvious: encode sign as a single bit and sum it with the length of number representation $\lceil\log_2(\mathrm{abs}\,(n)+1))\rceil$.

But how is it possible to represent a vector of numbers with different size. How to consume minimal amount of memory?

Note that the usual representation of signed integers in binary is not the one you propose.

In general, though, being super-efficient about coding in Turing machines isn't really important. We mainly use Turing machines for:

computability, where we don't care about efficiency at all;
complexity, where we only care about efficiency up to constant or even polynomial factors.

We don't use Turing machines for real computation where we care about the "real" efficiency, where making your program twice as fast makes it twice as good.

So, from the point of view of Turing machines, it's completely adequate to code vectors and so on by something like the following. Pick any sensible format for the individual data items and write those out with each bit doubled (i.e., $1011$ becomes $11001111$). Then separate each item with $01$. This means that storing the vector/matrix/whatever takes "twice as many bits as it should" but that constant factor just isn't important for the things we use Turing machines for.

I see 3 ways of doing it:

Storing the length and the items
Storing a bit after each item indicating whether it's the last item (can't store the empty list)
Storing a bit before each potential item indicating whether there are any more items

BTW, I think your number representation has no way to figure out where it ends.


Find maximum element in sorted arrays in logarithmic time Been stuck on this for a while, would really appreciate some help:

  Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right. For example, [35,42,5,15,27,29] is a sorted array that has been circularly shifted k = 2 positions, while  [27,29,35,42,5,15] has been shifted k = 4 positions. Give an algorithm for finding the maximum element in A that runs in O(log n) time.

The elements in A are distinct.

I understand that to achieve O(log n) time I'll probably have to search through the list by starting at the middle, and then going left or right, then splitting the list in half over and over, but I'm not sure how to attack it beyond that.

If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm.

Consider the sorted array $[0,0, \dots, 1]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements.

However, if you assume the elements are distinct, then you can indeed give an $O(\log n)$ time algorithm.

Assume the array was sorted ascending. Once it is cyclic shifted, we will have that, in the rotated array (say $a[1,2, \dots n]$), that $a[1] \gt a[n]$. (It might help to draw a figure here, plotting $i$ on x-axis and $a[i]$ on the y-axis).

Now if you pick a $j$, you compare $a[j]$ with $a[1]$ and move right or left, depending on whether it is greater or lesser, like binary search.

I think we could do the follow
first, choose the middle number which is 5 and then compere it with the lift term in your case it is 35.
If the middle < left then we can eliminate the right part of the array which is [5,15,25,29].

this is the idea but it needs to add some conditions to be more efficient.

Thanks
@Baghdadi


Practical exponential time algorithms for polynomial-time solvable problems Inspired by this quote attributed to Alan Perlis:

  For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.

How I interpret this statement is that some exponential running times should be preferred over polynomial ones for realistic problem sizes. I have never actually seen such a case though.

I wonder if there are any problems for which exponential algorithms are known that are preferable to the best polynomial ones up to a nontrivial problem sizes?

The simplex method for linear programming has worst case exponential time complexity but is widely used in practice instead of the polynomial algorithms (which do exist).

another big/ widespread example is Prime detection/ generation for RSA cryptography. theres a P-Time algorithm discovered early this century but it runs slow in practice so the probabilistic Miller-Rabin test is used. the algorithm runs slower the more bases are tested and could be said to run in exponential time (or at least nonpolynomial) in worst case as certainty of (non)primality is increased. a pragmatic/ P-time limit/ "compromise" is chosen in implementations so that its efficient but there is still high certainty.

see also

How are primes generated for RSA? and How can I generate large prime numbers for RSA? / crypto.SE


In algorithm analysis what does it mean for bounds to be "tight" For example we could say alg(x) runs big omega(n) but this bound is not "tight".

What is meant by "tight"? Is it that the bound isn't at its maximum?

So maybe a tighter bound could be big omega (1)??

Generally speaking, a bound is tight if there is no "better" bound.

Take, for instance, $f(n) = \sin(n)$. Then, $-1.5 \leq f(n) \leq 2n$ are valid bounds on $f$ but they are not tight -- there are better bounds, e.g. $-1.2 \leq f(n) \leq 1.5n$.

Now, $-1 \leq f(n) \leq 1$ are tight bounds -- there are no tighter ones.

You will note that the range of $n$ is relevant here. I implicitly let $n \in \mathbb{N}$ (or $\mathbb{R}$ if you want) here; if we consider $n \in \{ \pi i \mid i \in \mathbb{N} \}$ there are better bounds.

Now, using Landau symbols the terminology is used similarly: $f \in \Omega(n)$ is a tight bound if there is no "better" $\Omega$-bound, i.e. one with a faster-growing parameter function. If we also know that $f \in O(n)$, then both bounds are tight and we have $f \in \Theta(n)$. It is, however, very possible that you have, say, $f \in \Omega(n)$ and $f \in O(n^2)$ and both bounds are tight.

Here, and in particular in the context of algorithm analysis, the range of (the implicit) parameters is relevant as well: are you talking about all inputs? Worst-case inputs? The average case? For instance, $\Omega(n)$ is a tight (lower) bound on the asymptotic running time of (improved) Bubblesort if you consider the best case, but not for average or worst case.

Note that "tight" can be relative to your goals. If you want to prove asymptotics of the form $f \sim g$, you wouldn't call a $\Theta$-bound "tight".

This question might be a duplicate of this question.

$O$ notation represents the upper bound of an algorithm and $\Omega$ the lower bound. $\it{\Theta}$ combines the two yielding an asymptotically tight bound.


Using two hash functions for increased password security? Forgive me for my brief knowledge on hash functions as I am not from a computer science background, however I am researching password security for my thesis and have been looking into hashing functions for password security. I understand that a password goes through a hashing function and is stored in a separate database, at which point if the user enters the same password at a later date, that entry is then ran through the same hashing function and checked the output is the same. My question is, if lots of companies are being breached and passwords have been found out using the algorithms, would it be more secure to then use a second hashing function on the already hashed password and store all the password entries 'double hashed'?

Simply hashed passwords are susceptible to brute force or rainbow table attacks.  Hashing the passwords again will simply increase the cost of computing an entry in these tables (by one hash), but that is not an appreciable increase in the challenge of cracking them.

Several techniques available in practice including salt ing the password, wherein you prepend the password with a random substring (known as the salt), which you also prepend (in plaintext) to the hash.  So, whereas a password "hello" might hash to h("hello"), the salted password would be foo || h("foo" || "hello").  If "foo" is random, then this means that I may need to store all possible salted hashes for a given password in order to crack it.

To complicate the crack-ability of the password hash even further, one may add a pepper, which is a random (but not published) string prepended to password before hashing.  Checking a password in this case requires checking all possible peppers with a given password to see if any hash to the stored hash value.

Current best practice goes like this: Step 1, the password is combined with a random sequence of characters (the "salt"), which means that even if two users use the same password, the combination salt + password will be unique for each user, and cracking one combination salt + password does not help at all cracking anyone else's password. Step 2, the combination salt + password is hashed using a cryptographic hashing function, but not once, not twice, but a gazillion times so that calculating the hashed password takes a significant amount of time. Step 3, the salt is stored, but the hashed password is not actually stored, but used to encrypt a master password for that user which is required to decrypt that user's information.

The hashed password is not stored, so someone who manages to steal the complete information on the server still cannot access any user's data. To steal one user's data, an attacker has to guess passwords. Turning each password into a hashcode takes significant amounts of time, so cracking just one good (hard to guess) password should be very hard to crack. And that's just one password.


Sort an array that contain two sorted array in $O(n)$ Given an array $A[1..n]$. $A$ is mixed of two sorted arrays $B$ and
$C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in
the descending order.
Consider the following example: $B=[2,4,6,8]$ and $C=[9,7,5,1]$. As a
result $A=[2,9,7,4,6,5,8,1]$. Interestingly, The instructor said: $A$
can be sorted in $O(n)$. Anyone can give me a hint?

My attempt:
I tried to partition the array $A$ into sorted arrays $B$ and $C$, but I could not do it because my approach encountered counterexamples.

Let $a$ is the first element of $A$. Let $A$ is composed of array $B = (b_{1},\dotsc,b_{n})$ and array $C = (c_{1},\dotsc,c_{n})$.
Now, we will partition $A$ into arrays: $B'$ and $C'$ in the increasing and decreasing orders respectively. Following is the process:

Let $p$ be a pointer. Initially, $p$ is pointing to $a$. Let $b$ be the element in $A$ next to $a$.
There are two possibilities:

Case 1: $a<b$. Then, one of them must be an element of $B$. In this case, if $a$ is greater than the last element of $B'$, add $a$ to $B'$. Move the pointer to $b$ and go to step $1$.
Otherwise, add $a$ to $C'$ and $b$ to $B'$. Move the pointer to the element next to $b$ and go to step $1$.
Case 2: $a>b$. Then, one of them must be an element of $C$. In this case, if $a$ is smaller than the last element of $C'$, add $a$ to $C'$. And, move the pointer to $b$ and go to step $1$.
Otherwise, add $a$ to $B'$ and $b$ to $C'$. Move the pointer to the element next to $b$ and go to step $1$.
The above process produces the array $B'$ in increasing order and $C'$ in decreasing order. However, note that these arrays might not be of the same size.
Correctness: Proof by induction.
Base Step: $A$ is composed of $B$ and $C$. $B'$ and $C'$ are empty right now. In Step $2$, Case 1, we add $a$ to $B'$. If it is indeed an element of $B$ then we are good. If not, then $b \equiv b_{1}$ and we can assume that $A$ is composed of a new array $B' = (a,b_{1},\dotsc,b_{n})$ having elements in the increasing order, and array $C' = C \setminus a$ having elements in the decreasing order. Therefore, adding $a$ to $B'$ is correct.
Similarly, we can prove the correctness of Step $2$, Case $2$.
And, the correctness of the further steps follows from the induction step.

After obtaining $B'$ and $C'$, you can merge them using merge sort like step in $O(n)$ time.

Here is the natural intuitive way to sort the array. The idea is to keep track of two inserting positions.

(Data structure) A node contains a value, a pointer to its previous node, which can be null, and a pointer to its next node, which can be null.

Initialize a two-way linked list $L$ with three nodes, the head, a node whose value is the first element of $A$ and the tail. Initialize two pointer $p_1$ and $p_2$, both of which point to the unique node in $L$. It will always be true that $L$ is sorted by its values and $p_1$ is before or the same as $p_2$.

Iterate over the remaining element of $A$ in order. Suppose the next element is $a$.

If $a \lt p_1.val$, search $L$ element by element backwards starting from $p_1$ until a node with value that is not bigger than $a$ is found or the head of $L$ is reached. Insert a node with value $a$ just after that node. Update $p_1$ to point to the inserted node.
If $p1.val \le a\lt p_2.val$, search $L$ element by element backwards starting from $p_2$ until a node with value not bigger than $a$ is found. Insert a node with value $a$ just before that node. Update $p_1$ to point to the inserted node.
Otherwise, $a\ge p_2.val$. Search $L$ element by element forwards starting from $p_2$ until a node with value not smaller than $a$ is found or the tail of  is reached. Insert a node with value $a$ just before that node. Update $p_2$ to point to the inserted node.

I will leave you to figure out why this is a linear algorithm.


How to construct XOR gate using only 4 NAND gate? xor gate, now I need to construct this gate using only 4 nand gate

a b out
0 0 0
0 1 1
1 0 1
1 1 0

the xor = (a and not b) or (not a and b), which is
\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

I know the answer but how to get the gate diagram from the formula?

EDIT

I mean intuitively, to me, I should get this one if I do it step by step followed by the definition xor = (a and not b) or (not a and b).

\begin{split}\overline{\overline{\overline{A}{B}}\cdot\overline{{A}\overline{B}}}\end{split}

and xor will be constructed with 5 nand gates (first #1 image below)

my question is more like: imagine the first person in history figure out this formula, how can he or she (the thinking process) get the 4 nand soltuion from this formula, step by step.

\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

From that formula? It can be done. But it's easier to start with this one: (using a different notation here)

a ^ b = ~(a & b) & (a | b)

Ok, now what? Eventually we should derive ~(~(~(a & b) & a) & ~(~(a & b) & b)) (which looks like it has 5 NANDs, but just like the circuit diagram it has a sub-expression which is used twice).

So make something that looks like ~(a & b) & a (and the same thing but with a b at the end) and hope that it'll stick around: (and distributes over or)

(~(a & b) & a) | (~(a & b) & b)

Pretty close now, just apply DeMorgan to turn that middle or into an and:

~(~(~(a & b) & a) & ~(~(a & b) & b))

And that's it.


What is running time of an algorithm? What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm? If so, how ?

What do we mean by running time of algorithms?

Depends on who is talking. It can mean everything from actual time in seconds to execution count of some asymptotically dominant instruction.
Things get muddied further by widespread overuse of Landau notation.

Also, one typically distinguishes at least worst, average and best case.

  when we say running time of bubble sort is $O(n^2)$, what are we implying?

Here we use that the actual running time is in $\Theta$ of the execution count of an asymptotically dominant operation. We can rigorously show that Bubblesort takes $\Theta(n^2)$ comparisons (in fact, we can get the exact number for worst-, best- and average case), that all other operations happen only $O(n^2)$ often, and thus the real running-time has to be in $\Theta(n^2)$ as well.

That assumes that our machine model (usually RAM) and the real machine differ only by constant factors (unknown to us). If you analyzed formally on the TM model, you could not carry over Landau bounds as easily. In general, converting between (reasonable) models can add a polynomial factor.

  Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm?

No, not at all. Assuming that by "asymptotic complexity" you mean a Landau bound on the runtime function $T$,

you only know the behaviour of T for $n \geq n_0$ for some $n_0$ that may be larger than anything you ever see in inputs;
you only know the behaviour up to a constant factor $c$;
you only know the type/degree of the leading terms but lower terms can be significant (i.e. the absolute error of your bound can tend to infinity, even if you have a tight estimate of the constant factor of the leading term).

Even if you knew $n_0$, lower-order terms and all constant factors,

these bounds are usually not tight and
the analysis gives you the execution of some operations, not actual time.

The only way to use formal analysis for predicting actual running times is

analysing the execution counts for all statements,
analysing up up to small error terms, and
know how many (nano)seconds each statement takes.

Sometimes we can do 1. and 2. but 3. is very, very tough for real machines -- which is why everybody in TCS analyses on clean machine models.

Asymptotic complexity is not used to find actual running times of algorithms but as a comparison tool to find out which algorithm is more efficient. When you say $Algorithm_1$ is O(nlogn) as opposed to $Algorithm_2$ which is O($n^2$) you simply mean $Algorithm_1$ is a better algorithm in terms of run time complexity.

Now coming to your question about finding actual time taken here's a possible solution.
Say your algorithm's running time is approximated as a function of the form T(n)=a$n^2$, now you know beforehand that T(100)=10 seconds. Hence you substitute T(100) and get $a*10000=10$, or $a=1/1000$.
Now you want to find out the running time when the i/p size is 200(say). You just substitute 200 in T(n)=$1/1000$*$a^2$ and get the required time in seconds.


The difference between a bit and a Qubit Ok, I have done a lot of research on Quantum computers. I understand that they are possibly the future of computers and may be commonplace in approximately 30-50 years time.

I know that a Binary is either 0 or 1, but a Qubit can be 0 or 1. But what I don't understand is how it can be anything other then 0 or 1. Surely a computer can only understand on and off, despite however fast it may be?

Probably the easiest analogy is to probabilities. If your computer can flip fair coins, you can think of each coin being in state Tails with probability 1/2 and in state Heads with probability half. So it's appropriate to think of a coin not as a bit but as a vector of two elements $(p_T, p_H)$, where $p_T$ is the probability of tails, $p_H$ is the probability of heads and we have that $p_T \geq 0$, $p_H \geq 0$, and $p_T + p_H = 1$. Once we sample a coin its state "collapses" to either tails or heads.

Just about the same happens with qubits. You can also think of quibit as being "in between" two states. It's also easiest to think of qubit not as a bit but as a vector of two elements $(q_0, q_1)$. Now, however, we allo $q_0$ and $q_1$ to be negative, and even further, to be any two complex numbers, as long as $|q_0|^2 + |q_1|^2 = 1$. Just as with sampling coins, once you measure a qubit, it collapses to either $0$ or $1$, and in fact you get $0$ with probability $|q_0|^2$ and $1$ with probability $|q_1|^2$. However, and this is the crucial part, these quantum probabilities can be made to cancel each other because they take negative values; this cannot happen with classical probability. This is the power of qubits.

BTW these complex valued quantities describe amplitudes and are related to the wave-particle duality, i.e. the discovery that particles in fact behave as waves, until you measure them, and then they behave as particles. The cancelation I am talking about is in fact interference between waves. So another answer to your question is that a qubit is not a discrete object that's either in one state or not, it's a wave..until  you measure it.

In Quantum theory, a Qubit has an extra state (superposition) which differentiates it from a regular bit. A regular bit can have states 0 ("off") or 1 ("on"). A Qubit, can have one extra state, which is a superposition of both 0 or 1. This is essentially a "do not know" state (or both), since we don't know whether it will be a 0 or a 1. However, there are probabilities in which it can be a 0, or can be a 1. When observed, it can be decided if it's a 0 or a 1.


Can x86 Instruction Set be changed with microcode update? How I understand microcode translate an instruction to microinstructions. And CPU has a unit that stores all possible of microinstructions. These microinstructions can be changed, because it load every time after boot from motherboard. Can instruction set be changed?
I am sorry if i ask strange question, if I misunderstood , please correct , thanks
and again I am sorry if my English grammar is bad. (google translate)

That depends completely on the CPU. Some CPUs don't use microcode at all. Some CPUs use a mixture of hardcoded instructions and microcoded instructions. This mixture can be anywhere between almost all hardcoded and only a few microcoded instructions to almost all microcoded and only a few hardcoded instructions.
For CPUs that have microcode, the microcode could be either modifiable or not modifiable.
If all instructions are microcoded (there are no hardcoded instructions) and the microcode is stored and loaded in such a way that you can load a different one at will, then it would theoretically be possible to load microcode that implements a completely different instruction set.
However, the feasibility of that still depends on the internal design of the CPU. An extreme example would be the Transmeta Crusoe and Efficeon CPUs. These were 128 bit VLIW designs internally, and in order to execute x86 code, they had a software layer called Code Morphing Software, which was essentially an interpreter and JIT compiler from x86 to the internal VLIW code. The Code Morphing Software was running entirely in the standard RAM. This makes it sound like it should have been very easy to just load a different version of the Code Morphing Software and turn the CPU into an ARM or PowerPC or SPARC or MIPS CPU, right?
Well, not according to Linus Torvalds, who worked for Transmeta at the time. He was asked this exact question, and his answer was that the internals of the CPU are so specifically optimized for interpreting x86 code that writing a CMS implementation for, say, MIPS would be no different (and no more performant) than simply writing a MIPS emulator for x86 … which already exist anyway.
On the other hand, the CPUs of the Xerox Alto, Dandelion, Dolphin, and Dorado workstations were explicitly designed to be microcoded for different use cases. They would run completely different microcode depending on whether they were running Interlisp, Smalltalk, or the Star system. For example, the Smalltalk system implemented the most important instructions of their VM in microcode, so that in some sense, the CPU could directly execute (parts of) Smalltalk byte code. You could say that when running the Smalltalk system, Smalltalk byte code was the ISA!

I very much doubt that any modern CPU will use microinstructions nowadays, and the ability to change this would be an incredible security risk. Absolutely totally unacceptable.
Being able to change the microcode would mean you cannot trust any code in your computer at all.


Does Deadlock imply Starvation If there is a deadlock between the processes does that mean that there is starvation also?

My Thinking:
deadlock is no process using that resources , but starvation is like not giving chance to only that process so there is progress in starvation but not in deadlock
Is my thinking right?

You should first state the deadlock freedom property and the starvation freedom property more precisely.
I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2.

Freedom from Deadlock If some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.
Freedom from Starvation Every thread that attempts to acquire the lock eventually succeeds.

Note that by definition, starvation freedom implies deadlock freedom. Thus, if a mutual exclusion algorithm suffers from deadlock, it also suffers from starvation.
A direct argument is that: deadlock means that some thread attempts to acquire the lock, but no threads succeed. That is a special kind of starvation.

Both the cases, CPU needs to wait infinitely, as deadlock definition says:A system is in deadlock if more than one process waiting for a instances that never going to happen. Similarly, in starvation also, the process need to wait infinitely to get their chance to execute.


Difference between multi-agent systems and distributed systems What is the difference between multi-agent systems (MAS) and distributed systems, in the context of control with agents?

What is the difference between multi-agent systems (MAS) and distributed systems, in the context of control with agents?

Multi Agent System
According to the book;  Innovations,theories in  multi agent systems and applications, September,2015

It states that in multi agent system,agents have the ability to solve complex real world problems besides being autonomous and interlinked. thus exhibiting some intelligence

Therefore,MAS falls under the umbrella of Distributed Artificial intelligence.e.g. Autonomous cars,SoftBots to mention but a few.

On the otherhand in Distributed systems,agents perform a specific task with the centralised agent taking control of the goal,that's achieved.e.g cellular network applications controlled by NOC,aircraft system that is controlled by Area Control Centres.

Therefore,Distributed systems,fall under the umbrella of  Distributed Computing


Do Turing machines assume something infinite at some point? In a previous question What exactly is an algorithm?, I asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm.

One of the answers that caught my attention was this one:

  The factorial example gets into a different model of computation,
  called non-uniform computation. A Turing Machine is an example of a
  uniform model of computation: It has a single, finite description, and
  works for inputs of arbitrarily large size. In other words, there
  exists a TM that solves the problem for all input sizes.

  Now, we could instead consider computation as follows: For each input
  size, there exists a TM (or some other computational device) that
  solves the problem. This is a very different question. Notice that a
  single TM cannot store the factorial of every single integer, since
  the TM has a finite description. However, we can make a TM (or a
  program in C) that stores the factorials of all numbers below 1000.
  Then, we can make a program that stores the factorials of all numbers
  between 1000 and 10000. And so on.

Doesn't every TM actually assume some way to deal with infinity? I mean, even a TM with a finite description that computers the factorial of any number N through the algorithm

 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

contains the assumption that a TM has the "hardware" to compare numbers of arbitrary size through the "<=" comparator, and also ADDers to increment i up to an arbitrary number, moreover, the capability of representing numbers of arbitrary size.

Am I missing something? Why is the approach that I presented in my other question less feasible with respect to infinity than this one?

A Turing machine does not have the ability "to compare numbers of arbitrary size through the <= comparator" because a Turing machine does not have a "<= comparator". A Turing machine has a fixed, finite set $Q$ of states and a fixed, finite tape alphabet $\Sigma$. At each step of the computation, the Turing machine looks at its current state and the symbol under its read/write head and decides what to do next: which state to enter, which symbol to write to the tape and which way to move the tape head.

Because of this, a Turing machine cannot compare arbitrarily large numbers in a single <= instruction. Using the state, it can remember at most $|Q|$ different numbers and, using the alphabet, it can write at most $|\Sigma|$ different numbers in a single tape cell (using each possible symbol to represent one number).  As such, to compare arbitrarily large numbers on a Turing machine, you must write each number as a sequence of digits on the tape and write an algorithm that will take multiple steps to compare those two numbers.  As you can imagine, this makes writing Turing machine programs a rather fiddly endeavour.

Turing machines don't really "deal with infinity": they deal with unbounded finite things, at least in their standard definition.  The input is a finite string and, after any finite number of steps, the machine has only examined or written to a finite number of tape cells. There is no bound on the size of the input or the number of computation steps but, the input is finite and, after any finite number of steps, only a finite amount of output has been produced.

"thinking out of the box" and generalizing on this question that does get to some heart of the abstraction of Turing machines, and coming up with a different angle not already answered: yes, Turing machines have some intrinsic aspects of "assuming infinities" just as the concept is intrinsic to mathematics. TMs are an abstraction of physical machines. the physical concepts of Time and Space are purposely used in TM theory but as abstractions, however also with aspects of their real counterparts.

in short the TM can possibly run forever in theory, aka the halting problem. the tape is infinite but only a finite amount of it can ever be written to at a given time. a TM that runs forever basically assumes that time and space are unlimited, ie "infinite". in fact there is a corresponding Time and Space hierarchy / "continuum" that is infinite.

but no physical realization of this abstract concept is possible assuming the physical universe is bounded (space, time, matter, the last of which is somewhat analogous to "symbols" or "ink" in the Turing machine). somewhat similarly/ analogously, in physics sometimes the universe is regarded as unbounded/ infinite, but only as an abstraction. to flip this, that is also why the "modelling" of a modern computer as a Turing machine is itself an abstraction, because the computer can only have finite memory etc.

another useful comparison is the number line in mathematics. the number line is infinite, but it denotes finite numbers. every number on the number line represents a finite quantity, but there an infinite number of these finite quantities. the Turing machine tape has a strong similarity to the number line concept from mathematics. Turing could have easily defined it as only infinite in one direction, but he defined it as infinite in both directions, much like the mathematics number line, with negative positions "left" on the tape and positive positions "right".


Are there any programming languages which support user defined control structures? For instance, the user would define a for each loop in their code as having a structure something like:

foreach([variable1] : [variable2]){
    [statements]
}

(when [ ] are placeholders) and then the pieces would be used like this:

for(i = 0; i < variable2.length; i++){
    variable1 = variable2[i];
    statements
}

and then in the rest of the program, the user could use a for each loop with that format:

total = 0;
foreach(num : numbers){
   total += num;
}

I hope that example makes sense. To be clear, I am saying that in this hypothetical language a for each loop does not exist, but the user can define one which will, for then on, work exactly the same as any other structure. Are there any languages which allow this?

There are two aspects to your question:

Can we arrange a convenient syntax to express one control structure in terms of another?
Can we actually define new control flow mechanisms.

For example, suppose we have a language which only has the if statements without else:

if A then B

Can we express if A then B else C somehow? Yes, like this:

a = A ;
if a then B ;
if not a then C

It would be even better if we could package up the above piece of code into convenient syntax so that we could write just if A then B else C.

Sometimes we can define new control structures using existing ones. For instance, a while loop

while A do B

can be replaced with a call to a recursive function (under some technical assumptions):

function whileLoop():
   if A then (B ; whileLoop ())

whileLoop();

This sort of transformation is a bit more involved because it requires that for each while loop we define a new recursive function. If we were to automate the process, we would have to worry about many details (how to invent unique names of generated functions, do the functions have access to the local variables, etc.) than when we're performing just a straightforward syntactic translation of one variant of loop to another.

On the other hand, there are control mechanism which simply are not expressible in a language, unless already supported. One such example would be continuations. You can't get these in C, for example, but they exist in Scheme.

Your question is about syntax: can we make a syntactic transformation that replaces one piece of syntax with another piece of syntax. Languages usually deal with this sort of thing through a macro mechanism or syntax extensions. Here are some examples:

C has macros which will get you some of the way
Scheme has a more elaborate macro system which gets you a lot further
Racket, a descendant of Scheme, has an elaborate multi-stage computation system which allows essentially arbitrary syntax extensions
OCaml has the camplp5 syntax extension tool which allows pretty much arbitrary syntax extensions
Template Haskell is an extension of Haskell which allows meta-level transformations of syntax.

I am sure there are many other languages with similar facilities that I am not familiar with.

My programming language, MICGBF, solves your problem.

Any time you make a program, it turns that program into a single command, using a self-changing interpreter.

For example, if you give it the commands ������ and run it, then my programming language would make a new command called <insert tab here> which would execute ������. This could be helpful for making long programs short.

The proof for this is in the Python 3 code


Polynomial-time algorithm with exponential space is eligible? I'm curious about two things.

When we define the class called "probabilistic polynomial-time algorithm" in computer science, does it include polynomial-time algorithm with exponential space?
For example, when algorithm is considered to be given a input from domain $\{0,1\}^n$,
what if the algorithm internally queries its exponential sized table (ex. $0^n\to0,0^{n-1}1\to1$ and so on..) and outputs the result? Does it still polynomial-time algorithm?
In theoretical cryptography, one-way function $f:\{0,1\}^*\to\{0,1\}^*$ has a requirement, which is related with hard-to-invert property, as following block.
If the answer to above question is yes, is it possible to construct algorithm $A'$ to simulate exactly same as $f$ for every value in $\{0,1\}^n$ using exponential table as described in above question? If then, it implies that it's impossible to design one-way function which is definitely not true. So what have i missed?

  For every probabilistic polynomial-time algorithm $A'$, every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,

  $Pr[A'(f(U_n),1^n)\in f^{-1}(f(U_n))]<\frac{1}{p(n)}$

  where $U_n$ is random variable uniformly distributed over $\{0,1\}^n$

Regarding your first question, what you're missing is where your "exponential table" comes from. Your algorithm has a finite description and should work for every $n$. So it cannot explicitly contain the $n$-table for all $n$. It could contain instructions for computing the table, but then it would have to first execute them, and constructing an exponential size table takes exponential time.

On the other hand, your program could use a (supposedly) exponential amount of uninitialized space. Since its running time is polynomial, it only accesses polynomially many cells. You can implement memory access in such a way that if $T$ cells are ever accessed then $\tilde{O}(T)$ memory is used (exercise). The corresponding running time might become much worse, but still polynomial.

A third possibility are non-uniform computation models, which are popular in cryptography. Here the idea is that the algorithm is allowed to use a certain hard-coded amount of data which depends only on $n$. However, this data has to be polynomial size. This restriction comes from the interpretation of the model in terms of circuits. A machine running in polynomial time corresponds to circuits for every $n$ of polynomial size. If we now relax the constraint that all these circuits come from some single algorithm, then we get non-uniform polynomial time, which is the same computation with advice depending on $n$ of polynomial size (exercise).

The answer to the first question should obviate the second one. I would just mention that sometimes, instead of probabilistic polynomial-time algorithms, one considers (deterministic) polynomial size circuits.

Nope.  In the standard framework in the cryptographic community, that kind of algorithm is usually not considered probabilistic polynomial-time: if necessary, we tweak the definition to ensure that it's not.

Technically speaking, in cryptography some folks have suggested we use the sum of the running time plus the size of the program's code as our measure of the time for the attack (you can think of it like this: if the code of the program is $k$ bits, it will take $k$ time steps just to read that code into memory before you start running it).  If you hear someone say "running time" in cryptography, they might actually mean that sum.  I think I first learned this technical detail from Phil Rogaway, but I have no idea whether he is first.

If you don't believe me, here's an example citation to the literature: you can look at Bellare et al, The security of the cipher block chaining message authentication code, Journal of Computer and System Sciences.  See Section 2.2, Model of computation, where they write:

  We fix some particular Random Access Machine (RAM) as a model of computation.  [...] When we speak of A's running time this will include A's actual execution time plus the  length of A's description (meaning the length of the RAM program that describes A).  This convention eliminates pathologies caused if one can embed arbitrarily large lookup tables in A's description.

Notice how they anticipated this corner case and chose definitions that avoid it from being problematic.  With this definition, everything works out in a reasonable way, and your proposed algorithm (with an exponential-sized constant) is not a probabilistic polynomial-time algorithm.

Many cryptographers aren't always this careful about their definition of running time.  It is very common to be a little sloppy and omit this kind of detail.  Often, it doesn't matter.  But when we start to talk about exponential-sized constants, this detail does matter, very much, and that's when it is essential to know about this technical detail, if you want to argue over formalisms.
Nope.

By the way, I stand by my answer on this, despite the (unexplained) downvote.  Many folks are not aware that others in the research community have already anticipated this kind of subtlety, and few papers make a big deal of it, so I don't blame others for being unaware of the relevant definitions in the cryptographic community.


Why isn't this undecidable problem in NP? Clearly there aren't any undecidable problems in NP.  However, according to Wikipedia:

  NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that are] verifiable in polynomial time by a deterministic Turing machine.

  [...]

  A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Now consider the following problem:

  Given a Diophantine equation, does it have any integer solutions?

Given a solution, it's easy to verify in polynomial time that it really is a solution:  just plug the numbers into the equation.  Thus, the problem is in NP.  However, solving this problem is famously known to be undecidable!

(Similarly, it seems the halting problem should be in NP, since the "yes"-solution of "this program halts at the N-th step" can be verified in N steps.)

Obviously there's something wrong with my understanding, but what is it?

I think you misunderstood what it means to solve a diophantine equation, and Matiyasevich's indecidability theorem.

Matiyasevich proved that for every RE set $S$ there is a diophentine equation $f(n;x_1,...,x_k)$ such that $n \in S$ only if there exists integer coefficients $x_1$,..,$x_k$ such that $f(n;x_1,...,x_k) = 0$. In particular, the halting problem is a typical RE set, and so solving the above problem is undecidable.

Note that $x_1, ... x_k$ are not bounded in size, and in general can be arbitrarily large, so there is no "polynomial sized certificate" evident in this problem.

To expand: the integers $x_1, ... , x_k$ need to be written in binary to be a certificate. Since these integers can be arbitrarily large (regardless of $n$), we have that the certificate is not polynomial in $\log n$ or more importantly, not bounded by and computable function.

Every problem in $\mathsf{NP}$ however, has a certificate that is bounded by some polynomial $p(N)$ (where $N$ is size of input). So $\mathsf{NP}$ questions are trivially decidable, since you can enumerate every possible bit string upto length $p(N)$ and if none of them certify the input, return false. If some does then return true.

We think that the dilemma you raised about Diophantine equation is very significant, because it reveals something abnormal in the current definition of NP :
- A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Concerning the definition of NP, it can be traced to the 60’s, where a great number of applicable and significant problems were discovered for which no polynomial algorithms could be found to solve them, in order to recognize these problems from those problems solvable in Polynomial time (P), the concept of NP was put out.

However, the current definition of NP defined as verifiable in polynomial time confuses NP with P, because a problem in P is also verifiable in polynomial time. In another word, such definition leads to the loss of the essence of NP, « nondeterminisme ». Consequently, it causes serious ambiguities in understanding NP, for example, your dilemma : by nature the problem of Diophantine equation is undecidable; but by the definition of NP, it is decidable, …

In our opinion, the difficulty in solving « P versus NP » lies firstly at cognition level, so if we hope to get an insight into « P versus NP », we need at first to question : What is NP?


Scheduling problem on bipartite graph Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament needs to be scheduled.

If $u_i$ and $u_j$ share no common neighbor, these two tournament can be scheduled on the same day. Similarly, one can schedule multiple tournaments in one day if there is no such conflict.

Is there a way to compute the minimum number of days required to complete all the tournaments and the corresponding scheduling?

So here, it looks as though $u \in U$ is a vertex representing the team and $v \in V$ is an edge between the vertices representing the matches possible.

If we can generate a Bipartite Graph, the edges ${ v_i, ...v_j}$  going across are all non-conflicting matches. Those edges for this matching ( $M_1$) can be held on that day. Next, we remove ${ v_i, ...v_j}$ and check to see if we can get more Bipartite Graphs. The edges going across are similarly the non-conflicting matches.

Not sure if this is what you asked for.


The importance of the membership problem Given a word $w$ and a language $L$, we want to check if $w\in L$.  This is called the membership problem. Why is the membership problem important?

The importance is that any computational problem where the answer is yes or no can be phrased as a membership problem in a language. The language is the set of strings for which the answer is yes.

What computation means to us today is that we write programs on the computer and finally run them.Now,the program is basically an algorithm that is implemented through a language,and there are a great many class of problems that do not allow algorithms to compute them or solve them.Now the set membership problem that we consider is carried upon sets of finite strings.when we write a program,the input is in the form of strings and output is also in the form of strings.So,if the set membership problem on the set of inputs and outputs allow algorithms to compute them then we say the program is capable to carry out its job else not.Hence the study of set membership problem on finite strings is a central problem in computer science.


Decidability of the halting problem on real-life finite computers given unlimited input It has been my understanding that, technically, our computers are Finite State Machines.  And, since FSMs halt when they run out of input, the halting problem is technically solvable.  At some point, we must reach an identical state without consuming input if there is an infinite loop.

I also understand that doing this in practice would take far, far, far too long to be useful.  Thus, I have read over and over that, yes, technically the halting problem is solvable for real computers, but it doesn't matter, because we can't do it in practice.

However, in a real computer, while we have a finite (vast) set of states, isn't it the case that we don't have finite input?  Input can easily be generated from non-cyclical random events, such as random radioactive decay, or the motion of water in a stream.  Doesn't this mean that, in fact, our computers are not truly Finite State Machines, and that the Halting Problem is not merely practically unsolvable, but genuinely unsolvable?

The halting problem can be stated as follows:

  Given a program P and an input x, does P halt when run on x?

Here both P and x are finite. In some cases (for example, in program verification) we might also be interested in infinite input which is eventually periodic, or at the very least, has an effective finite description (i.e., it is given by some algorithm). Assuming that this algorithm is also executed on a real machine (otherwise it is "cheating"), the entire setup can be folded to a program running on a real machine, and so the property of having a finite number of states is recovered.

A Turing Machine is, strictly speaking, ALSO a Finite-State Machine; what gives it universal power is in how this FSM is allowed to interact in a largely unrestricted (but still finite) manner with one or more read/write tapes.  Note that since the machine cannot visit more than N tape cells in N steps, these tapes do not need to be actually infinite; they merely need to be enlargeable, with no inherent bound on the eventual amount of enlargement.  It is clearly possible to operate a physically real machine in this manner [though at the moment humans would be required to supply and manage the ever-growing tapes], therefore the theoretical analysis also applies to the physical machine.


Lambda calculus didn't seem abstract. And I can't see the point of it The underlying question:

What does lambda calculus do for us that we can't do with the basic function properties and notation generally learned in middle school algebra?

First of all, what does abstract mean in the context of lambda calculus? My understanding of the word abstract is something that is divorced from the machinery, the conceptual summary of a concept.

However, lambda functions, by doing away with function names, prevents a certain level of abstraction. For example:

f(x) = x + 2
h(x, y) = x + 5 y

But even without defining the machinery of these functions, we can easily talk about their composition. For example:

1. h(x, y) . f(x) . f(x) . h(x, y) or
2. h . f . f . h

We can include the arguments if we want, or we can abstract away completely to give an overview of what's happening. And we can quickly reduce them to a single function. Let's look at composition 2. I can have student layers of detail I can write with depending on my emphasis:

g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4

Let's perform the above with lambda calculus, or at least define the functions. I'm not sure this is right, but I believe the first and second expressions increment by 2.

(λuv.u(u(uv)))(λwyx.y(wyx))x

And to multiply by 5y.

(λz.y(5z))

Rather than be abstract, this seems to get into the very machinery of what it means to add, multiply, etc. Abstraction, in my mind, means higher level rather than lower level.

Furthermore, I am struggling to see why lambda calculus is even a thing. What is the advantage of

(λuv.u(u(uv)))(λwyx.y(wyx))x

over

h(x) = x + 5 y

or a combined notation

Hxy.x+5y

or even Haskell's notation

h x y = x + 5 * y

Again, what does lambda calculus do for us that we can't do with the f(x)-style function properties and notation many are familiar with.

There are many reasons why the lambda calculus is so important.

A very important reason is the lambda calculus allows us to have a model of computation in which computable functions are first-class citizens.

One cannot express higher-order functions in the language of middle school algebra.

Take as example the lambda expression

$$\lambda f. \lambda g. \lambda x. f(g(x))$$

This simple expression shows us that, within the lambda calculus, function composition is itself a function. In middle school algebra, this is not easily expressed.

In the lambda calculus, it is very easy to express that a function will return a function as its result.

Here is a small example. The expression (where I here assume an applied lambda calculus with addition and integer constants)

$$(\lambda f. \lambda g. \lambda x. f((g(x)))(\lambda x. x+2)$$

will reduce to

$$\lambda g. \lambda x. g(x)+2$$

Notice also that within the lambda calculus, functions are expressions and not definitions of the form $f(x) = e$. This frees us from the need to name functions and to distinguish between a syntactic category of expressions and a syntactic category of definitions.

Also, when it becomes impossible (or just notationally cumbersome) to express higher-order functions, one will also have problems with assigning types to expressions.

Function composition has the polymorphic type

$$\forall \alpha.\forall \beta. \forall \gamma. (\beta \rightarrow \gamma) \rightarrow ((\alpha \rightarrow \beta) \rightarrow \gamma)$$

in the Hindley-Milner type system.

A very strong selling point for the lambda calculus is precise the notion of typed lambda calculus. The various type systems for functional programming languages such as Haskell and the ML family are based on type systems for lambda calculi, and these type systems provide strong guarantees in the form of mathematical theorems:

If a program $e$ is well-typed and $e$ reduces to the residual $e'$, then $e'$ will also be well-typed.

And if $e$ is well-typed, then $e$ will not exhibit certain errors.

The proofs as programs correspondence is particularly noteworthy. The Curry-Howard isomorphism (see e.g. https://www.rocq.inria.fr/semdoc/Presentations/20150217_PierreMariePedrot.pdf) shows that there is a very precise correspondence between the simply typed lambda calculus and intuitionistic propositional logic: To every type $T$ corresponds a logical formula $\phi_T$. A proof of $\phi_T$ corresponds to a lambda term with type $T$, and a beta-reduction of this term corresponds to performing a cut elimination in the proof.

I urge those who feel that middle school algebra is a good alternative to the lambda calculus to develop an account of higher-order, polymorphically typed middle school algebra together with an appropriate notion of Curry-Howard isomorphism. If you can even work out an interactive proof assistant based on middle school algebra that would allow us to prove the many theorems that have been formalized using lambda calculus-based proof assistants such as Coq and Isabelle, that would be even better. I would then start using middle school algebra, and so, I am sure, would many others with me.

Lambda calculus exists so that anonymous (aka lambda) functions can be created. If you don't do away with function names, then the namespace can get cluttered and one can run out of available function names. This is especially important when dealing with so-called "higher order functions" that return functions (or function pointers) for obvious reasons.

Essentially, lambda functions are equivalent to locally scoped variables. Functional programming without lambda functions is analogous to procedural programming without any local variables, ie, a terrible idea.

"why lambda calculus is even a thing"
mathematicians love redundancy. lambda calculus is rarely used in math because as you've discovered the notation isn't very useful.

"If you can even work out an interactive proof assistant based on middle school algebra that would allow us to prove the many theorems that have been formalized using lambda calculus-based proof assistants such as Coq and Isabelle, that would be even better. I would then start using middle school algebra, and so, I am sure, would many others with me."
Have you heard of metamath? No lambda calculus involved there, can prove many of  the coq/isabelle theorems


Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and constant space.

The original problem appears here,
however the solution uses $\lg n$ space.
A problem in my course required adjusting the algorithm such that we use constant space.

I thought of the following algorithm:

MyAlgorithm(root, num)
    min<-findMin(root)
    max<-findMax(root)
    while(min.key <= max.key && min != max)
        if((min.key + max.key)=num) return true
        if((min.key + max.key) < num)
            min<-successor(min)
        else
            max<-predeccessor(max)
    return false

According the CLRS book both predeccessor() and successor() functions time complexity depends on tree height which is $O(\lg n)$ in our case since red-black tree is balanced.

However, we have the while loop which theoretically can run almost n times.

For example, because the algorithm above is equivalent to searching for the number num in a sorted array, say we have this array and num<-3:
$$
1,2,3,4,5,6,7,8,9,10
$$
In this case we'll call predecessor(max) $8$ times which is almost $\Theta(n)$ or $\Theta((n-2)\lg n)=\Theta(n\lg n)$ asymptotically.

Am I wrong in my conclusions? How can I prove that the time complexity is indeed $\Theta(n)$?

So we are given a binary search tree $T$ (we, however, do not require it to be balanced). Also we are given an integer; let's call it target_number. We wish to query whether there are two distinct nodes in $T$ such that the sum of their values equals target_number. In order to do that, we need two functions: get_successor(x) and get_predecessor(x). Given a node x get_successor(x) returns the tree node whose value is larger than that of x and is the smallest such value. The definition of get_predecessor(x) is symmetric.

The algorithm is now (as in your question): point to the minimum node, and point to the maximum node. Compute the sum $S$ of the nodes pointed by the two pointers. If $S$ is less than the target number, move left pointer to its successor node. If $S$ is greater than the target number, move right pointer to its predecessor node. Otherwise, we have a match and return true.

query(root, target_number)
    left_finger  = the minimum node of the entire tree rooted at root
    right_finger = the maximum node of the entire tree rooted at root

    while left_finger != nil and right_finger != nil and left_finger != right_finger
        tentative_sum = left_finger.value + right_finger.value
        if tentative_sum < target_number
            left_finger = get_successor(left_finger)
        else if tentative_sum > target_number
            right_finger = get_predecessor(right_finger)
        else
            return true
    return false

Next, we need to give a strong argument that it runs, in fact, in $\Theta(n)$. Take a look at operation get_successor: If you start from the minimum node and visit the entire tree in successor order, you do $\Theta(n)$ work regardless the fact that get_successor runs in worst case $\mathcal{O}(\log n)$, and that is why: you visit each node at most three times: from the parent, returning from the left child and returning from the right child; we spend constant time at each node.

As you can see from the below diagram, each node x has at most 3 incoming arcs and has at most 3 outgoing arcs. Traversing each arc is $\Theta(1)$. So basically, if we start from a minimum node, and keep advancing to the successor nodes, we do essentially in-order traversal that is, however, iterative instead of recursive. Same argument for starting from the maximum node via get_predecessor.

Now, we do the same traversal but in "both directions" (the left_finger proceeds towards successor nodes and right_finger proceeds towards predecessor nodes, and we terminate (at latest) when the two fingers meet. Thus, running time is linear in tree size and space complexity constant since no recursion is involved.

First thing that popped into my mind, was using a hashmap (or just a key - storage) while iterating.

In the HashTable, I would store an addend for the sum, and while iterating I would look up if the value is in the list.

Addends[] //KeySet
for value in Values {
   if(Addends.contains(value) // Pair found
     return true
   Addends.add(Sum - value)
}


Machines for context-free languages which gain no extra power from nondeterminism When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.

For the first and last levels1 (regular languages and recursively enumerable languages), it makes no difference to the power of the model whether we consider deterministic or nondeterministic machines, i.e. DFAs are equivalent to NFAs, and DTMs are equivalent to NTMs2.

However for PDAs and LBAs, the situation is different. Deterministic PDAs recognise a strictly smaller set of languages than nondeterministic PDAs. It is also a significant open question whether deterministic LBAs are as powerful as nondeterministic LBAs or not [1].

This prompts my question:

  Is there a machine model that characterises the context-free languages, but for which non-determinism adds no extra power? (If not, is there some property of CFLs which suggests a reason for this?)

It seems unlikely (to me) that it would be provable that context-free languages somehow need nondeterminism, but there doesn't seem to be a (known) machine model for which deterministic machines are sufficient.

The extension question is the same, but for context-sensitive languages.

References

S.-Y. Kuroda, "Classes of Languages and Linear Bound Automata", Information and Control, 7:207-223, 1964.

Footnotes

Side question for the comments, is there a reason for the levels (ordered by set inclusion) of the Chomsky hierarchy to be number 3 to 0, instead of 0 to 3?
To be clear, I'm talking about the languages that can be recognised only. Obviously questions of complexity are radically affected by such a change.

As far as I know, we do not know whether Non- deterministic context-sensitive languages are more powerful than deterministic context-sensitive languages. And the simplest reason behind this is: Till now no-one has been able to give a language that is accepted by the non-deterministic LBA and not accepted by the deterministic LBA. So if someone can come up with one such language that is accepted by ND LBA and not accepted by deterministic LBA then only this will be proven. As we know this method of proving is called proof by contradiction.
Because proving something is TRUE is a hard problem but proving something FALSE is easy, just get one instance where it fails and we're done.

In my understanding of theory of computation, the only situation non-determinism  does not  give you extra flexibility (i.e,.. power) is at the recursively enumerable/ recursive level. This is primarily because of the halting problem and it's limitations on the TM's capabilities in decidability, which I believe this answers one of your questions in the foot notes as well as a sidebar. The Chomsky Hierarchy is a logical representation of moving up the flexibility latter (if I might say), allowing more power to the machine. Does this help any with your question/thoughts?

As far as the PDA's and LBA's I will have the other accomplished folks here in the community help with that, my experience has been more with TM's and the theory associated with the higher (more RE) part of the hierarchy (at least as taught in my undergrad).

Peter Linz theory of computation

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd_sbs_14_img_0?_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4


Complexity of a knapsack variant Consider the following traditional integer knapsack problem:

$\max \sum_{i=1}^k p_i \cdot x_i\\
\text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\
x_i \in \{0,\ldots,k_i\} \text{ for each } i$

Now consider a laminar family $\mathcal{I}$ of sets, i.e., a collection of subsets of $\{1,\ldots,k\}$ such that for each pair $I_1,I_2 \in \mathcal{I}$ it either holds that $I_1 \subseteq I_2$ or $I_1 \supseteq I_2$ or $I_1 \cap I_2 = \emptyset$. For each of these subsets $I_j \in \mathcal{I}$, we insert an additional cardinality constraint of the form

$\sum_{i \in I_j} x_i \leq \mu_j$

for some number $\mu_j$.

Clearly, this problem is weakly $NP$-complete in general since it contains the traditional (integer) knapsack problem. The question is what happens if the profits $p_i$ are polynomially bounded. Does the problem remain $NP$-complete or is it easy to solve now? We are thinking about this problem for months now.

What we know so far:

If we omit the cardinality constraints or restrict ourselves to only one cardinality constraint that involves each of the variables, the problem becomes easy to solve (this isn't as trivial as it sounds since the maximum amounts $k_i$ are still not polynomially bounded).
Accordingly, if the maximum amounts $k_i$ are polynomially bounded, the problem becomes easy to solve as well.

The above results imply that, in order to prove $NP$-completeness, a possible reduction would need to make use of decision variables that are not polynomially bounded and must incorporate suitable laminar cardinality constraints with values $\mu_j$ that aren't polynomially bounded as well.

So, does anyone have some clue on how to prove or disprove the $NP$-completeness of the problem?

It can be solved by a similar DP for traditional knapsack problem, and thus still weak NP-complete. In the following we assume that the subsets $I_j$ are mutually disjoint, and the other case (some subsets are super sets of others) is similar.

In the DP algorithm for knapsack, let $T[p,i]$ be the minimum weight to reach profit $p$ by only using the first $i$ items. Now arrange the items such that all items in the same $I_j$ are consecutive. Since $I_j$ are disjoint, when dealing with $x_i$, we only need to consider  how many items in $I_j$ can be picked. Thus, for each $p$ and $i$, let $D[p,i,q]$ be the minimum weight to reach profit $p$ by only using the first $i$ items and using only $q$ items in $I_j$. The table size is bounded by $P\times n^2$, where $n$ is the number of items and $P$ is the maximum profit. Since you assume that $P$ is polynomial, it takes polynomial time.


Show that every infinite language has a non-regular subset I'm trying to solve this problem:

  Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular

But can this be correct? If I have the language $\{a\}^*$ for example, that's infinite but you can make a DFA for any sub-language of it, right?

There's a hint that this can be proved using diagonalization, but I think I must be misunderstanding the question.

The powerset of the language contains all the sublanguages. This will be uncountably infinite, but there are only countably many regular languages (for a particular, finite alphabet)

Consider the language $L = \{a^n \mid n \text{ is prime}\}$.  $L$ is a subset of $\{a\}^*\!$, which is a regular language but it is not regular so has no DFA.


similar language by two DFA then why wrong answer I attempted a mock paper for finite automata .so i was asked to create a DFA which accepts a language in which inputs are a,b and number of b's should be divisible by 3.The first image is my answer  for which i was not given marks .but when i checked the answer of the paper they gave the second image as the correct answer.Both the DFA give the accept the language(number of b divisible by 3),so can any one tell how the second DFA in the second is better than the first one,or where did i go wrong.

First DFA does not accept $\epsilon$ which has 0 number of $b$'s which is divisible by 3 (0 is said to be divisible by 3). So first answer is incorrect, where as second is correct.

There is no problem with your DFA but the reason why the second image is more appropriate is because the DFA is having less number of states in other words it is an (optimized/minimized) DFA .May be you have not gone through further topics in finite automata like minimization of DFA .After covering that topic even you will end up with DFA which is minimized like the second DFA in the image. Its better if you cover all topics in finite automata before attempting mock tests.