Algorithm to test whether a language is context-free Is there an algorithm/systematic procedure to test whether a language is context-free?

In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \mathbb{N}\}$), test whether the language is context-free or not.  Imagine we are writing a web service to help students with all their homeworks; you specify the language, and the web service outputs "context-free" or "not context-free".  Is there any good approach to automating this?

There are of course techniques for manual proof, such as the pumping lemma, Ogden's lemma, Parikh's lemma, the Interchange lemma, and more here.  However, they each require manual insight at some point, so it's not clear how to turn any of them into something algorithmic.

I see Kaveh has written elsewhere that the set of non-context-free languages is not recursively enumerable, so it seems there is no hope for any algorithm to work on all possible languages.  Therefore, I suppose the web service would need to be able to output "context-free", "not context-free", or "I can't tell".  Is there any algorithm that would often be able to provide an answer other than "I can't tell", on many of the languages one is likely to see in textbooks?  How would you build such a web service?

To make this question well-posed, we need to decide how the user will specify  the language.  I'm open to suggestions, but I'm thinking something like this:

$$L = \{E : S\}$$

where $E$ is a word-expressions and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

Each of $x,y,z,\dots$ is a word-expression.  (These represent variables that can hold any word in $\Sigma^*$.)
Each of $a,b,c,\dots$ is a word-expression.  (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
The concatenation of word-expressions is a word-expression.
Each of $m,n,p,q,\dots$ is a length-variable.  (These represent variables that can hold any natural number.)
Each of $|x|,|y|,|z|,\dots$ is a length-variable.  (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises.  Of course, you can substitute any other textual method of specifying a language in algebraic form, if you like.

By Rice's theorem, to see if the language accepted by a Turing machine has any non-trivial property (here: being context free) is not decidable. So you would have to restrict the power of your recognizing machinery (or description) to make it not Turing complete to hope for an answer.

For some language descriptions the answer is trivial: If it is by regular expressions, it is regular, thus context free. If it is by context free grammars, ditto.

Any language is is accepted by a Push Down Automata, is a CFL. Here is a detailed breakdown to determine whether a language is CFL or not. check if language is CFL or not


Is the class NP closed under complement? Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.

First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.

If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we cannot say whether $\sf NP = coNP$ or not. Notice that $\sf NP = coNP$ implies that the polynomial hierarchy collapses to the first level. However this would not imply that $\sf P= NP$.

It is unknown. A proof of the P vs. NP problem would give you an answer.


What is the knowledge required to understand the formal definition of a Turing Machine? As a computer science student I consider is essential to completely understand how a Turing machine is defined.

What mathematical knowledge is required in order to understand the formal definition of a Turing Machine, as explained in this Wikipedia link.

All you need is some basic discrete mathematics.

The states, tape alphabet and states are finite sets; the blank symbol, starting state, accepting state and rejecting state are elements of one of those sets.

The transition function is a function on finite sets, defined using a Cartesian product of finite sets.

The tape is a sequence of elements of one of the sets.

All you need is some basic discrete mathematics.

The states, tape alphabet and states are finite enumeration types; the blank symbol, starting state, accepting state are elements of those types.

The transition function is a function between finite types, defined using a product type of finite types

The tape is a stream type of elements of one of the types.


Measuring Complexity of Boolean Satisfiability Problem How exactly is the complexity of a SAT solver measured? My main concern is that, for $N$ variables, you can have, e.g., an OR of $O(2^N)$ AND terms, which would take at least $O(2^N)$ time to process. If the formula can contain duplicate sub-expressions, e.g., $(A \land B) \lor (A \land B)$, then the formula's maximum size is unbounded. In this case, wouldn't the complexity be better measured in terms of how complex the formula is, rather than how many variables it takes?

The boolean satisfiability problem (SAT) involves finding a satisfying truth assignment for a set of clauses $C$ over the boolean variables $V=\{v_1, v_2, ..., v_n\}$ so that each clause in $C$ contains at least one true literal. Since $V$ contains $n$ variables and each of these variables can only have $2$ different values (i.e., true or false), the total number of possibilities to be tested is $2^n$. We don't know how to solve SAT in polynomial time (since SAT is NP-complete); therefore, all solvers take exponential time in the worst case. Fortunately, however, there exist several ways to prune the search space.

  Wouldn't the complexity be better measured in terms of how complex the formula is?

The importance of the SAT problem lies in that every decision problem in NP can be reduced to SAT for CNF formulas. Other restricted versions of SAT exist (such as 3-SAT, Horn-SAT, and XOR-SAT); these restricted versions can be either in P or NP depending on the restriction (see Schaefer's dichotomy theorem). Regardless of this, note that problems in NP (such as SAT) are characterized by solutions (in the case of SAT, truth assignments) that can be verified in polynomial time.

There are problems for which there is no reduction to SAT that is of P complexity. Those problems may or may not be solved by computations that can be performed in O(2^n) or less time and space. SAT is always worst case O(2^n) or less by definition.

SAT has a P complexity solution. See arxiv.org/abs/cs/0205064.


What is the 1's and 2's complement of 0.01101? What is the 1's and 2's complement of 0.01101?
I'm unable to find any details on this from google.

Basically how do we represent the floating points in 1's and 2's complement forms?

Even wikipedia only says that 1's complement is the inverted bits of binary representation. The examples only contain integer values. I couldn't find anything clear about what is the exact significance of this system. Hence, unable to deduce if the inverting bits applies to floating points also.

One's and two's complement apply to (fixed-point) encodings of integers.  They don't apply to floating-point numbers.  Floating point is different.

If u want to find 1's complement of  binary float numbers
Use formula
(r^n-r^-m-N)
Eg 0.0110
Here r =2 base of binary no.

n is the number of digits in integer part but in this there is no digit in integer part so n=0
m is digit in fractional part
N is our original Number

Now
(r^n-r^-m-N)
(2^0)-(2-4)-0.0110
(1)-(1/16)-0.0110
(1-1/16)-0.0110
(16-1/16)-0.0110
(15/16)-0.0110
(0.9375)-0.0110
Now we have convert.  0.9375 into binary which is =0.111
(0.1111)-(0.0110)
0.1001


Write algorithm for biased toss of a coin Given a biased coin whose probability for Heads is 0.67 and Tails is 0.33, write an algorithm which will print the Heads and Tails with this probability.

I am not able to proceed with the problem. What should be my approach ?

Let $\xi$ be a random variable uniformly distribuited in $[0,1]$ and $t$ a real value in $(0,1)$, consider the function

$$
Y(\xi;t) = \begin{cases}
1 & \xi < t \\
0 & \text{otherwise}
\end{cases}
$$

Which is a discrete random variable therefore

$$
p_Y(y) = (1-t) \delta(y) + t \delta(y - 1)
$$

This means that if pick a random number in $[0,1]$ and you later compute $Y$, this $Y$ will correspond to a randomly picked value in $\left\{0,1\right\}$, but biased accordingly to $t$. If you use @kngtu pseudocode, it's equivalent to define the distribution above where $t = 0.67$.

If you can generate a random number between 0 and 1, then do

Edit: round random to 2 decimal places

if (random < 0.34)
  return "tails";
else
 return "heads";

That way (assuming the random number generator is actually random) you have a 33% change of tails and 67% chance of heads.


What is a type definition? When reading about data types, "type definition" is often used without any prior explanation to what it means.

For example, in https://en.wikipedia.org/wiki/Type_system, we have the sentence "...  since C++ has stronger rules regarding type definitions  ..."

Any help in clarifying what the difference between, for example, type and type definition is greatly appreciated!

"Defining" a type is the act of building a new type composed of one or more pre-existing data types. For example, the "Complex Number" type is often declared as an ordered pair of "Real Numbers" :

Type Complex
  Real a
  Real b
End

a and b being the real and imaginary parts.

This sample of pseudo-code is a "Type Definition".

Variables can contain different sorts of values, e.g., integers, reals, characters...
This is called the TYPE of the variable.
Some languages are dynamically typed. That means that the interpreter or the compiler decides the type of the variable for you. In static typed languages, you have to define the type yourself when declaring the variable. This is the TYPE DEFINITION.

In a strong typed static languages the rules forbid to mix different types. if you want to add, e.g., a real and an integer you have to explicitly cast the integer to real.

in a weak typed language you can mix types. but since the low level bitpatterns differs between types, you can have unwanted results.

Most languages are somewhere in between. It will be clear that unwanted effects are not acceptable, while the need for an explicit cast makes the code heavy. So most compilers will do an implicit cast for some standard operations. Adding a real and an integer will in that case implicitly provoke a cast to real.


Is $\frac{n}{3}$-CLIQUE NP-complete? Consider the problem
$\frac{n}{3}$-CLIQUE:
determining whether a graph contains a clique with at least $n/3$ vertices.

I want to prove it is NP-complete using a polynomial transformation from CLIQUE.

How can I approach this problem?

Let me explain how to solve this, leaving all details to you.

Given an instance $(G,k)$ of CLIQUE, we want to construct an equivalent instance of $\frac{n}{3}$-CLIQUE, say $G'$. Let us denote by $|G|$ the number of vertices in $G$. There are several cases to consider:

Case 1: $k = |G|/3$. In this case you can take $G' = G$.
Case 2: $k > |G|/3$. In this case you want to increase the number of vertices to $3k$ without changing the size of the maximum clique.
Case 3: $k < |G|/3$. This is the most complicated case. You want to increase the number of vertices to some $n'$ while increasing the size of the maximum clique by some $\Delta$. You are done if you can ensure that $k+\Delta = n'/3$. (In fact, it suffices to have $k+\Delta > n'/3$, since then we can use Case 2.)

You take it from here.

I'do go for the approach of assuming that it is solvable in polynomial time, then proving that given this solution u can reach the solution of the general Clique problem in polynomial time.
So it is only polynomial if P=NP
-i.e., simply prove the 2nd part, think if someone gave u a black box to get n/3 CLIQUE how can u use it to get the general CLIQUE


Do Oracles run in O(1) or O(n) time? The common understanding of what oracle does is that it answers a question after a single operation.  So at first glance, it runs in $O(1)$.  But, doesn't it need to actually read the input?  Wouldn't this take at least $n$ steps?  If so then wouldn't an oracle run in $O(n)$?

The oracle runs in a single step. Yes, it would take an ordinary Turing machine some number of steps to read the input but an oracle isn't an ordinary Turing machine – that's almost the whole point of using them. Also, the time taken for the oracle to read its input is essentially accounted for by the time it took the calling machine to write that input.  So, oracles return in $O(1)$ steps. More precisely, they return in exactly one step.

Also, it's not quite clear what you mean by "$O(n)$ steps". $n$ usually denotes the length of the input we're trying to compute on, which would be the input to the calling machine, not the oracle. The input to the oracle could be arbitrarily long.  For example, you could have a machine that takes an input $x$ and calls an oracle to ask if the string consisting of $2^{2^{2^{|x|}}}$ zeroes is in the language decided by the oracle. Moral of the tale: don't write functions of $n$ without saying what $n$ is.

The time it takes the oracle doesn't matter. The oracle gives you a hint that you can use to determine the answer that you want. You will still need to check that hint, that is you need to write a program that accepts the original input, and the hint, and which in polynomial time outputs "Yes" if the the answer to the original question is "Yes" and the hint is useful. This will typically involve reading the input and the hint.

The oracle doesn't solve the problem. It just gives you a hint. We look at problems where we can prove the existence of a good hint. (For example, to solve the travelling salesman a tour that supposedly solves the problem is a hint, but we need to check that it actually does solve it).


Is $n \log n$ in $O(n^{1.46-\varepsilon})$? I am trying to figure out the solution of the recurrence relation
$$T(n) = 5T(n/3) + n \log n$$ using the Master Method.
I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the part that $\frac{n \log n}{n^{1.46}}$ must be polynomially smaller. If something is polynomially smaller does it mean it can not be bounded either from below or from above (or both)?

When $f(n)$ is said to be polynomially smaller than $g(n)$ it just means that there is some constant $\varepsilon > 0$ such that $f(n) \in O(g(n) n^{-\varepsilon})$.
This is not about being able to bound $f(n)$ from above and/or below but about the growth rate of $f(n)$ when compared to $g(n)$.
In other words you want $\frac{g(n)}{f(n)}$ to  grow at least as fast as some polynomial/root of $n$.
In your particular case, $n \log n$ is indeed polynomially smaller than $n^{1.46}$, and this follow from the fact that $n \log n \in O(n^\alpha)$ for any $\alpha >1$.
A a concrete choice of $\varepsilon$, you can pick $\varepsilon=0.1$ yielding $n \log n \in O(n^{1.46-0.1}) = O(n^{1.36})$.
To see this you can consider the limit:
$$
\lim_{n \to \infty} \frac{n \log n}{n^{1.36}} =
\lim_{n \to \infty} \frac{\log n}{n^{0.36}}  =
\lim_{n \to \infty} \frac{1}{0.36 \cdot n^{0.36}} = 0,
$$
where we used L'Hôpital's rule.
In the above, the choice $\varepsilon = 0.1$ was just a convenient value that works, but any choice of $\varepsilon \in (0, 0.46)$ suffices.

Answering title: $n\lg n = O(n^{1,46 - \varepsilon})$, when $\varepsilon \lt 0.46$.


Numerical example of theoretical diff file size using Kullback Leibler? I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ Wikipedia.  Can anyone point me to a numerical example of this calculation?  I can only find general theory and formulae. I'd like to check my work.  So this is what I have so far...

This is a graph of the individual divergences for each byte probability between two files, say P and Q.  They are calculated according to the standard log formula for divergence.  The byte values (0-255) are along the bottom.  You can see that the divergences are both positive and negative.

I am unsure as to what the units of the y axis are, but following on from Shannon entropy, they must be bits per byte.  And they're small values.  The sum of all the divergences, keeping sign, is 0.019 bits /byte.  Both file sizes are approximately 20KByte, so can I say that the theoretical patch size going from P to Q is 20,000 * 0.019 = 380 bits or 48 bytes?

This feels wrong.  If the graph represents the patch size somehow, then I cannot see how the information contained in this complex shaped graph can be encoded in just 48 bytes.  There are no examples anywhere on the Interweb that I can find.

One further thing.  The above is for two similar files.  If P or Q should be totally random (from a random number generator), the KL divergence calculation = approx. 0.5.  This at least makes some semblance of sense if you think about all of the bits from P to Q being on average 50% different due to the randomness.  Perhaps 48 bytes is correct.  Err, um...

I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL)

That's not quite right.  I suspect you've taken an imprecise, non-technical, handwavy statement from Wikipedia and interpreted too much into it.  They're trying to summarize some underlying theory in an informal way, but such summaries are inevitably incomplete.  Instead, you'd be better off reading and understanding the underlying theory.

There is a sense in which that statement is correct if we make certain assumptions -- e.g., that the source is memoryless (each character is independent of all past ones, with no history), and that we interpret it in an asymptotic, average-case kind of way -- but for many real-world sources of  data, those assumptions don't apply.


Is it possible to decide if a given algorithm is asymptotically optimal? Is there an algorithm for the following problem:

  Given a Turing machine $M_1$ that decides a language $L$,
  Is there a Turing machine $M_2$ deciding $L$ such that
  $t_2(n) = o(t_1(n))$?

The functions $t_1$ and $t_2$ are the worst-case running times of Turing machines $M_1$ and $M_2$ respectively.

What about space complexity?

Here is a simple argument to show that they are undecidable, i.e. there are no algorithms to check if a given algorithm is optimal regarding its running-time or memory usage.

We reduce the halting problem on blank tape to your problem about running-time optimality.

Let $M$ be a given Turing machine. Let N be the following Turing machine:

$N$: on input $n$
1. Run $M$ on blank tape for (at most) $n$ steps.
2. If $M$ does not halt in $n$ steps, run a loop of size $2^n$, then return NO.
3. Otherwise, return YES.

There are two cases:

If $M$ does not halt on blank tape, the machine $N$ will run for $\Theta(2^n)$ steps on input $n$. So its running time is $\Theta(2^n)$. In this case, $N$ is obviously not optimal.
If $M$ halts on blank tape, then machine $N$ will run for constant number of steps for all large enough $n$, so the running time is $O(1)$. In this case, $N$ is obviously optimal.

In short:

$$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$$

Moreover given the code for $M$ we can compute the code for $N$. Therefore we have reduction from halting problem on blank tape to running-time optimality problem. If we could decide if a given Turing machine $N$ is optimal, we could use the above reduction to check if a given machine $M$ halts on blank tape. Since halting on blank tape is unecidable your problem is also undecidable.

A similar argument can be used for space, i.e. it is also undecidable to check if a given Turing machine is optimal regarding the space it uses.

Even a stronger statement is true: we can't decide if a given computable function is an upper-bound on the time complexity of computing a given computable function. Similarly for space. I.e. even basic complexity theory cannot be automatized by algorithms (which can be considered a good news for complexity theorists ;).

Ha! Were the answer yes, we would be living in a different world.

Imagine that the answer to your question was yes (and of course we knew the algorithm $A_0$ that would answer your question), then for any algorithm $A$ for language $L$, we would be able to tell (using $A_0$) if $A$ is optimal or not.

Unfortunately, this is not possible, and indeed I personally think proving (non-trivial) optimality is the most interesting (and difficult) problem in computer science. As far as I know - I would be glad to be corrected - there exists no optimality result for any polynomial problem (except the trivial optimality results of course of algorithms taking time proportional to input size).


Studying Programming Language Theory I have recently become extremely interested in understanding and proving aspects of (functional) programming languages.

However as I dive deeper in, things like $\lambda$ calculus, category theory, and denotational semantics are a little difficult to grok without proper explanation.

I read SICP (quite an enlightening book) but I'm looking to dive deeper into the theory of functional programming. Are there any books/blogs/sites/you-name-it that would discuss the theory of functional programming languages from the ground up?

It is not easy to come by books that consider the denotational semantics of $\lambda$-calculus. One possibility is:

Roberto M. Amadio and Pierre-Louis Curien: Domains and Lambda-Calculi

Type-theoretic accounts are easier to get hold of:

Bob Harper, Practical Foundations of Programming Languages (there is also a printed version).
Benjamin Pierce, Types and Programming Languages.
Frank Pfenning's course on Computation and Deduction, I think he also published a book with the same title.

These books have high ratings and come up on different scientific communities:

Type Theory and Functional Programming by Simon Thompson.

Structure and Interpretation of Computer Programs


Find all nodes on simple paths between two nodes in cyclic directed graph Given two nodes U and V in a cyclic directed graph, how can I find the set of nodes that are part of a simple path from U to V?

Attempt 1

I've tried using a DFS from U that stores the set of visited nodes when V is reached, and backtracks when a cycle is detected. But this algorithm must traverse all paths, and can hence be very slow for large graphs.

I cannot stop the DFS early when a node that has already been deemed to be part of a simple path is reached:

If the DFS goes U -> A -> B -> C -> D -> E -> V, those nodes are deemed to be part of a simple path. After backtracking to E and traversing to F and A, a cycle is found. After backtracking to U and traversing to C, a node that is already part of a simple path is found, but the DFS cannot stop, since further traversal is necessary to figure out that F is also part of a simple path: U -> C -> D -> E -> F -> A -> V.

The same argument shows that I can't stop the DFS early when a node that has already been deemed to be part of a cycle is reached.

Attempt 2

Another idea I've tried is to store on the edges sets of potential cycle root nodes that must be traversed in order to reach V from the edge's sink. For instance for the edge E -> F, A must be traversed in order to reach V. Hence the DFS does not have to traverse this edge if A has already been visited.

It is not straight-forward to decide which nodes are potential cycle roots, and on which edges they need to be stored. My implementation attempts have unfortunately been too slow for large and complex graphs. After the potential cycle roots have been calculated, however, performing the DFS has been fast.

Question

Are there any efficient algorithms for finding the set of nodes that are part of a simple path between two nodes?

Examples

Just to make things really clear, these are the outputs I am looking for for a few different graphs:

Example 1

Nodes that are part of simple paths: U, A and V.

Example 2

Nodes that are part of simple paths: U, A, B, C, D, E and V.

Example 3

Nodes that are part of simple paths: U, A, C, D, E, F and V.

Example 4

Nodes that are part of simple paths: U, A, B, C, D, E, F and V.

This problem is NP-hard. It is actually NP-Hard to prove if a vertex $w$ lays on a simple path from $u$ to $v$. Here is a prove of hardness through a reduction from the two disjoint paths problem.

Given a directed graph $G = (V, E)$ and two pairs of vertices $(s_1, t_1)$ and $(s_2, t_2)$, we build the new graph $G'$ by adding a new vertex $w$ to $G$ and add an edge from $t_1$ to $w$ and an edge from $w$ to $s_2$. The new graph admits an $s_1, t_2$ simple path passing through $w$ if and only if the original graph admits two disjoint paths one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$. Try to prove this claim as an exercise!

EDIT: The answer below is not correct. It finds all vertices that are on some path from $U$ to $V$, not on some simple path from $U$ to $V$. It seems we need a directed analog of biconnected components for this to work.

Add an edge from $V$ to $U$, then find all vertices in the strongly connected component containing $U$ and $V$. (They will be in two different SCCs if and only if there is no path from $U$ to $V$ in the original graph.)

This works because two vertices are in the same SCC if and only if there is a simple cycle containing both vertices.

Credit to bennos on Stack Overflow for providing me the answer when I asked the analogous question for undirected graphs back in 2012. For undirected graphs, you use biconnected components instead of strongly connected components.


Are the capabilities of programming languages the same? Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could (theoretically) do the exact same thing with ever language, don't you?

The answer to the question depends on what you mean by "the same".

It is a famous result of computability theory that many reasonable models of computation all calculate the same nubmber-theoretic functions. That is, all reasonable general-purpose programming languages compute the same partial functions $\mathbb{N} \to \mathbb{N}$. So in this sense the capabilities of all programming languages are "the same". By the way, this is not the Church-Turing thesis, contrary to what you may be told.

However, a programming language can do many other things in addition to computing with numbers. For instance, it may access external devices, run parallel programs etc. While these features do not allow it to compute any extra number-theoretic functions, they may make a difference when it comes to computing other functions. For instance, a famous early example is that of the language PCF. It can simulate Turing machines, but it cannot compute the "parallel or" function, while its parallel variant PCF++ can.

When we look at higher-order functions languages differ in their capabilities. A purely functional language such as Haskell cannot compute the modulus of continuity but a functional language extended with local state can.

So it really depends on what you mean by "the same".

Yes, that's correct.

The usual justification for the computational equivalence of two programming languages X and Y is that we can write an interpreter runX for X programs written in the Y language, and vice versa.

Therefore, any program y written in Y can be simulated in language X using something like runX("y"), and vice versa. So, the computational power of the two languages is the same.

Sometimes, we state these fact stating "all programming languages are Turing-equivalent", i.e. that they can compute anything that a Turing machine can compute (and nothing else).

Note that this does not mean that the two languages have the same features. For instance, X might feature OOP classes, while Y might be purely procedural. X might have primitives for 3D graphics, while Y has not. X might allow access to files, Y might not. X might have garbage collection, when Y has not. X might be a functional (or logic) language, while Y is imperative.
X might feature higher order functions, or dependent types, etc. which Y does not have.
When we say that they have the "same power", here we only mean that they can compute the same set of functions (say, mapping an input strings to an output string).

Finally, note that there do exist some computer languages which are less powerful than general purpose programming languages like Python, Java, and the like. These are not usually called programming languages, even if they might share some aspects. For instance, the Bitcoin scripting language allows some limited computation, but has no loops (e.g. while), so it drastically restricts the algorithms one can implement. The basic querying part of SQL (select) is a simple reporting language, and is not Turing powerful (unless one adds triggers / stored procedures or other more advanced features.).


Algorithm to find diameter of a tree using BFS/DFS. Why does it work? This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.

Why does it work ?
Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.
Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $p_1$ from s to u and $p_2$ from a to b do not share edges, then the path from t to u includes s. So
$d(t,u) \ge d(s,u)$
$d(t,u) \ge d(s,a)$
....(more inequalities follow ..)

The inequalities do not make sense to me.

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges:

1-connectedness (ie. between any 2 nodes in a tree there is exactly one path)
any node can serve as the root of the tree.

Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ starting at $s$ first, some node $y$ starting at $x$ next. wlog $d(s,u) \geq d(s,v)$. note that $d(s,x) \geq d(s,y)$ must hold, unless the algorithm's first stage wouldn't end up at $x$. We will see that $d(x,y) = d(u,v)$.

The most general configuration of all nodes involved can be seen in the following pseudo-graphics ( possibly $s = z_{uv}$ or $s = z_{xy}$ or both ):

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

we know that:

$d(z_{uv},y) \leq d(z_{uv},v)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
$d(z_{uv},x) \leq d(z_{uv},u)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
$d(s,z_{xy}) + d(z_{xy},x) \geq d(s,z_{uv}) + d(z_{uv},u)$, otherwise stage 1 of the algorithm wouldn't have stopped at $x$.
$d(z_{xy},y) \geq d(v,z_{uv}) + d(z_{uv},z_{xy})$, otherwise stage 2 of the algorithm wouldn't have stopped at $y$.

1) and 2) imply $\, \\ d(u,v) = d(z_{uv},v) + d(z_{uv},u) \\ \qquad\geq d(z_{uv},x) + d(z_{uv},y) = d(x,y) + 2\, d(z_{uv}, z_{xy}) \\ \qquad\qquad\geq d(x,y)$.

3) and 4) imply $\, \\ d(z_{xy},y) + d(s,z_{xy}) + d(z_{xy},x) \\ \qquad\geq d(s,z_{uv}) + d(z_{uv},u) + d(v,z_{uv}) + d(z_{uv},z_{xy}) \qquad\qquad\qquad\qquad \\ \, $ equivalent to $\, \\ d(x,y) = d(z_{xy},y) + d(z_{xy},x) \\ \qquad\geq 2*\,d(s,z_{uv}) + d(v,z_{uv}) + d(u,z_{uv}) \\ \qquad\qquad\geq d(u,v)$.

therefore $d(u,v) = d(x,y)$.

analogue proofs hold for the alternative configurations

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

and

                          (x)        (u)
                          /            \
                         /              \
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /
                         \              /
                          \            /
                          (y)        (v)

these are all possible configurations. in particular, $x \not\in path(s,u), x \not\in path(s,v)$ due to the result of stage 1 of the algorithm and $y \not\in path(x,u), y \not\in path(x,v)$ due to stage 2.

First run a DFS from a random node then the diameter of a tree is the path between the deepest leaves of a node in its DFS subtree:


Are there any existing problems that wouldn't be solvable with a halting oracle? I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible for a Turing machine also shows that it is impossible for a Turing+oracle to decide the Halting Problem for a Turing+oracle. Are there any actual, practical, examples of problems unsolvable by a halting oracle?

Note: by "oracle" I mean oracle for a standard Turing machine, not a TM with an oracle itself.

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of such problems (where $\phi_n$ is the $n$-th partial computable function and $W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$ is the $n$-th computably enumerable set):

$\{n \in \mathbb{N} \mid \text{$\varphi_n$ terminates for finitely many inputs}\}$ is $\Sigma^0_2$-complete.
$\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ is $\Pi^0_2$-complete.
$\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ is $\Sigma^0_3$-complete.

None of these can be solved even if you have a Halting Oracle. For instance, consider the second example, "is $\varphi_n$ total?" Given $n$ how would the Halting Oracle help us decide whether the Turing machine encoded by $n$ halts on every input?

[Added 2014-06-03] For a "practical" aspect of all of this, consider the problem: a programmer has written a function void charge_credit_card(int card_number, int amount) and we would like to know whether the function terminates on all inputs. It is impossible to write a compiler which can automatically check this in general. Moreover, even if we allow the compiler to ask us questions of the form "does charge_credit_card terminate when given input (k,m)?", it is still impossible.

Predicting a random oracle is not solvable using, possibly, any kind of hypercomputation.


Why is quicksort better than other sorting algorithms in practice? In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ in the worst case (like mergesort and heapsort), and even linear time in the best case (like bubblesort) but with some additional needs of memory.
After a quick glance at some more running times it is natural to say that quicksort should not be as efficient as others.
Also, consider that students learn in basic programming courses that recursion is not really good in general because it could use too much memory, etc. Therefore (and even though this is not a real argument), this gives the idea that quicksort might not be really good because it is a recursive algorithm.
Why, then, does quicksort outperform other sorting algorithms in practice? Does it have to do with the structure of real-world data? Does it have to do with the way memory works in computers? I know that some memories are way faster than others, but I don't know if that's the real reason for this counter-intuitive performance (when compared to theoretical estimates).

Update 1: a canonical answer is saying that the constants involved in the $O(n\log n)$ of the average case are smaller than the constants involved in other $O(n\log n)$ algorithms. However, I have yet to see a proper justification of this, with precise calculations instead of intuitive ideas only.
In any case, it seems like the real difference occurs, as some answers suggest, at memory level, where implementations take advantage of the internal structure of computers, using, for example, that cache memory is faster than RAM. The discussion is already interesting, but I'd still like to see more detail with respect to memory-management, since it appears that the answer has to do with it.

Update 2: There are several web pages offering a comparison of sorting algorithms, some fancier than others (most notably sorting-algorithms.com). Other than presenting a nice visual aid, this approach does not answer my question.

Short Answer

The cache efficiency argument has already been explained in detail. In addition, there is an intrinsic argument, why Quicksort is fast. If implemented like with two “crossing pointers”, e.g. here, the inner loops have a very small body. As this is the code executed most often, this pays off.

Long Answer

First of all,

The Average Case does not exist!

As best and worst case often are extremes rarely occurring in practice, average case analysis is done. But any average case analysis assume some distribution of inputs! For sorting, the typical choice is the random permutation model (tacitly assumed on Wikipedia).

Why $O$-Notation?

Discarding constants in analysis of algorithms is done for one main reason: If I am interested in exact running times, I need (relative) costs of all involved basic operations (even still ignoring caching issues, pipelining in modern processors ...).
Mathematical analysis can count how often each instruction is executed, but running times of single instructions depend on processor details, e.g. whether a 32-bit integer multiplication takes as much time as addition.

There are two ways out:

Fix some machine model.

This is done in Don Knuth's book series “The Art of Computer Programming” for an artificial “typical” computer invented by the author. In volume 3 you find exact average case results for many sorting algorithms, e.g.

Quicksort: $ 11.667(n+1)\ln(n)-1.74n-18.74 $
Mergesort: $ 12.5 n \ln(n) $
Heapsort:  $ 16 n \ln(n) +0.01n $
Insertionsort: $2.25n^2+7.75n-3ln(n)$

[source]

These results indicate that Quicksort is fastest. But, it is only proved on Knuth's artificial machine, it does not necessarily imply anything for say your x86 PC. Note also that the algorithms relate differently for small inputs:

[source]
Analyse abstract basic operations.

For comparison based sorting, this typically is swaps and key comparisons. In Robert Sedgewick's books, e.g. “Algorithms”, this approach is pursued. You find there

Quicksort: $2n\ln(n)$ comparisons and $\frac13n\ln(n)$ swaps on average
Mergesort: $1.44n\ln(n)$ comparisons, but up to $8.66n\ln(n)$ array accesses (mergesort is not swap based, so we cannot count that).
Insertionsort: $\frac14n^2$ comparisons and $\frac14n^2$ swaps on average.

As you see, this does not readily allow comparisons of algorithms as the exact runtime analysis, but results are independent from machine details.

Other input distributions

As noted above, average cases are always with respect to some input distribution, so one might consider ones other than random permutations. E.g. research has been done for Quicksort with equal elements and there is nice article on the standard sort function in Java

You switched in your question from "is better" to "has better runtime". These are not the same. If you look at the other answers, you will find that Mergesort might run faster - but Quicksort has the advantage that it uses negligible space for things other than the array to be sorted. That means I can call it without fear of running out of memory, no matter how large the array is. That is not quite true for Mergesort, if the data can be close in size to the available data. And if virtual memory is available, Mergesort can take a lot longer due to paging.
In practice you wouldn't just use a O (n log n) algorithm, you would check if you can do things faster in special cases. If your array is mostly ascending or mostly descending with few exceptions, it can be sorted in linear time. (If let's say all but 1/8th of the values are in ascending order, it can be sorted in O (n log n), but much faster than using Quicksort or Mergesort).
If you go a bit further: If your array consists of an initial part that is mostly sorted, a middle part, and an end part that is mostly sorted, and the middle part is substantially smaller than the whole array, then we can sort the middle part with Quicksort or Mergesort, and combine the result with the sorted initial or end parts. However, this doesn't affect the question, because the middle part can still be sorted with Quicksort or Mergesort.
Another question is: Can the work be multi-threaded? The partitioning is hard to divide between two threads. Once the array is partitioned, each half can easily be handled by a separate thread. If you have many threads, being able to use only one for the initial partitioning is painful. With Mergesort, we can also do many smaller merges using many threads. We have the advantage that a single merge can also be run in parallel by one thread producing the lower half of the sorted array, and another thread working from the high values down, producing the higher half of the sorted array. I think this gives a large advantage to Mergesort if many threads are available.


Determine if the language of words with same number of 1's and 2's is context-free or not $$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 is pushed onto the stack, there always is a 2 to get pop it out. The 0's are what is bothering me at the moment. Do we need to include them, or we can exclude them entirely?
I would do this with pumping lemma, but we did not learn that for our class.

When it comes up to deciding if a language is context-free or not, I try the following 'roadmap' to come up with an answer.
$1.$ Try to make a CFG for the given language. If we can make a CFG, we have proved that the language is context-free.
$2.$ If step $1$ did not work out, there is a probabilty that the language is not context-free. So try proving that the given language is not context-free by the pumping lemma.
$3.$ If I fail to prove that language is not context-free, I probably failed to make a CFG so I start to make a PDA.
Remark: This is my way to (dis)prove context-free languages, there are many other ways to do this. So don't take this as a general step-by-step plan.
In your example, we need to (dis)prove $$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
So when we think of a CFG, we should consider that whenever we add a $1$, we should also add a $2$ (and vice-versa), as $|1| = |2|$. We also know that the language can be empty and that the number of $0$'s do not matter.
So
$$S \rightarrow \epsilon $$
$$S \rightarrow 0S$$
$$S \rightarrow 1S2S$$
$$S \rightarrow 2S1S$$
As we were able to make a CFG, we can say that the language $L_2$ is a CFL.

The above language is context free,whenever we encounter any symbol in input we can push it into stack or pop something out of stack or we simply skip that symbol according to definition of pda,so here the condition is that number of 1's and 2's must be equal so we design pda in such a way that when ever we encounter 1 we push that into stack and whenever 2is encountered we pop 1 out of stack and when we encounter 0 we simply skip it at the end stack will be empty and final state is reached if 1's and 2's are equal otherwise they halt at non final.


How do I sort these elements in O(n) time? So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix sort. The run time of radix sort is O(d(n+N)) or O(dn) if n is really large. So how can I modify radix sort so that it runs in O(n)?

EDIT:
I don't think you guys understand this. The amount of elements in the array is n but the ACTUAL value for each element can range from 0 to n^2 - 1. So if we have an array with 10 elements in it then the largest the element can be is 99 and the smallest it can be is 0 but there will still be 10 elements in the array.

If you want to implement this on a RAM with integer math (ie. a real computer if your n is smaller than $2^{32}$), you can have a look at Upper bounds for sorting integers on random access machines. The authors show that integers in the range [0,$n^c$] can be sorted in $O(n(1 + \log c))$. Word RAM models add some loglog factors to that runtime.

I really doubt anyone can sort an array within O(n) unless infinite memory is given. However, if you know the range of numbers and have sufficient memory to store all of them, then you can hash the array (take mod by $n^2$) and store them in a intermediate array of size ($n^2$).You can use another intermediate array of same size to store repetition (if you have repeated elements in original array.). All this can be done in single pass causing O(n). And on second pass iterate over the intermediate array and place them in original array one by one.


Contained optimal combination of inputs I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined score (i.e. a fantasy football formation) within a $50,000 budget, where a lineup must consist of the following formation:

Goalkeeper x1
Defender x2
Midfielder x2
Forward x2
Utility x1 (can be any position apart from GK)

Each player has a single position and a score, they cannot play in any other position. So in our example, say we have 18 goalkeepers, 22 defenders, 32 midfielders and 28 forwards. We need to select 1 GK (from the 18), 2 defenders (from the 22), 2 midfielders (from the 32), 2 forwards (from the 28) and one not already used non-goalkeeper as a "utility" (from the 100 - 18 = 82).

Currently, I am trying to select the optimal lineup using a brute force technique i.e. generate 1,000,000 random combinations of players which fulfills the above formation and select the lineup which has the highest score.

What other algorithms / techniques could I use to improve upon brute force in this computationally expensive environment (i.e. there are trillions of possible combinations)?

It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar formulation is discussed, for example, here.

Short Cut - not perfect but if draft is tomorrow

Create a property productivity = goals / price
Rather than use decimal I would just go 100000 * goals / price

Take the top goalie by productivity
Top 2 defenders by productivity
Top 2 midfielders by productivity
Top 2 forwards by productivity
Substitute the least productive defender, midfielder, or forward with top performing utility player if the utility player is a better performer
(assuming max one utility is a substitute)
This is not going to be perfect

If you are over the cap
Drop the highest salary and run again
This is not going to be prefect as some times dropping number 2 salary will be best
Back to if you are over the cap

If you are under the cap it gets trickier
Drop the lowest performer
From that position drop all player with <= goals
Run again
If under the cap back to step one

Brute Force / Random

Look at actual combinations

gk    18     18
df    22    231
mf    32    496
fd    28    378
ut    76     76

Total number of combinations
59,247,707,904

I you take a random 1,000,000 (random) you are only looking a small fraction
The first short cut would be better than that

Dynamic programming

You can eliminate any player that cost more and produces less goals.

Could also eliminate any two player combos that cost more and produce less goals.

Quickly eliminate over the cap.

Keep the best score and skip if you don't have a chance of making the best score.

Looking at the dynamic programming I am not convinced that you would get the options down sufficiently.  Even if every individual combination was dropped in 1/2 with dynamic programming that is 1.8 billion total combinations.  At 1 per millisecond that is 59 years.

Would need to get the individual combinations down by a factor of 10x eacj to get it down to 7 days.


TSP decision problem vs TSP optimization problem Let's check together whether the TSP-decision problem is NP-complete. Maybe it will help me to understand things better.

Question for TSP-decision problem: Given n cities and a tour from length $k$. The traveller starts at an arbitrary city, visits every other city just once and returns to the starting point. Does a tour from length $\leq{} k$ exist?

Let's first check whether the TSP is in NP:

A proof is given. Proof in this case is a tour. For it to be in NP, we must be able to verify this proof with a deterministic algorithm in polynomial time.
So first we have to check, whether every city is only visited once. This can be done at most in $O(n^2)$. Next we need to calculate the distances and sum them up. This can be done as well at most in $O(n^2)$. The last step is to check whether the calculated length is $\leq{} k$. The hole process would require a polynomial time $\rightarrow 2 n^2 = O(n^2)$.

So the TSP-decision problem is in NP. What about the NP-hardness? We don't need to prove that, because Richard M. Karp proved that the Hamiltonian Circuit is NP-complete. The TSP is a special case of the Hamiltonian Circuit, therefore we know TSP must be NP-complete as well. NP-complete means = NP-hard and NP.

Is this possible with TSP-optimization problem?

Question for TSP-optimization: Given n cities and a tour from length $k$. A traveller starts at an arbitrary city and visits every other city just once and returns to the starting point. Is tour from length k the shortest tour?
We can check in polynomial time, that every city is visited once.
However we can't check whether $k$ is really the shortest tour, because we would have to check every other possible tour as well. That would mean $(n-1)!$ possible tours. And this would make the hole process above exponential.

So TSP-optimization problem is not in NP? Therefore it is not NP-complete, but NP-hard?

Anything wrong about my thoughts?

Only decision problems can be NP-hard or NP-complete; these are problems for which the answer is either Yes or No.

Optimization problems have an optimal solution as an answer. The associated decision problem is, given an instance and a value, whether the the value of an optimal solution is as good or better than the given value.

When we say that an optimization problem is NP-hard, we mean that its associated decision problem is NP-hard; it is an abuse of terms. We could also say that an optimization problem is NP-complete if its associated decision problem is NP-complete.

The TSP optimization problem is, given a graph, find a TSP tour of shortest length. The associated decision problem is, given a graph and a value $k$, decide whether the shortest TSP tour has length at most $k$. These are different than the problems that you describe.

Sometimes we are interested in a weaker version of the optimization problem, namely, given an instance, find the value of an optimal solution. This is the perspective usually considered in the field of hardness of approximation, in which the goal is to show that it is NP-hard to even approximate the optimal value.

I would like to point out that the TSP optimization problem returns a Minimum length Hamiltonian-Cycle for the graph. Now, our job to prove this problem is in NP class invloves

  Checking whether the Minimum length falls within a range.

Now this range is calculated by adding the weight of n-1 number of edges in increasingly sorted order for the minimum bound and decreasingly sorted order for the maximum bound (This maximum or minimum values are not necessarily cycle-lengths).
This whole checking process can be done in polynomial time. Hence, TSP optimization problem also lies in NP class.

If anyone thinks that the way of proving this problem to be NP class isn't correct, I would also point out what Raphael originally posted :

  However we can't check whether k is really the shortest tour, because we would have to check every other possible tour as well. That would mean (n-1)! possible tours. And this would make the hole process above exponential.

This problem itself is similar to the TSP problem and thus is not what we want to look for.

P.S. Please correct me if I'm wrong anywhere !


Maximizing the weighted average value of a set of items by doubling the weight of a subset of items Given a set of $n$ items, each represented by $t_i=(w_i,v_i)$ for $1 \le i \le n$, the weighted average value of those items is defined as:
$$
\frac{\sum_{i=1}^{n}v_iw_i}{\sum_{i=1}^nw_i}
$$

The goal is to find a subset of items to double their weight, such that the weighted average value is maximized.

For example, suppose you have the following set of items, where $t_i = (w_i,v_i)$:

$$
t_1 = (12, 1100000)\\
t_2 = (12, 1000000)\\
t_3 = (12, 850000)\\
t_4 = (10, 800000) \\
t_5 = (8, 1200000)
$$
The weighted average value is 981,481. The best solution is to double the weight of items 1 and 5, which leads to a new weighted average of 1,024,324.

I am trying to come up with an algorithm to find the best subset of items to double, and so far I've tried using bruteforce. For each item, you can choose to either double it, or leave it as it is. This means that there are a total of $2^n$ possibilities to explore, which means exponential complexity. I've also tried a greedy algorithm to pick the highest value-to-weight ratio items, and determine the best number of items to pick, however this solution is not always optimal.

I am wondering, what is the most efficient algorithm to find the best subset of items to double their weight?

Thanks in advance.

This can be solved in polynomial time.

Hint: consider the decision version of the problem.

   Suppose I gave you a value $\alpha$ and asked you whether it's possible to find a subset of items so that the weighted average is at least $\alpha$.

Could you solve that version of the problem?  Does this give you any ideas about how to solve the original problem?

Alternate hint:

   Keep trying other greedy strategies.  You've tried one greedy algorithm, but there might be other plausible greedy algorithms.

I think the below gives the correct answer, but I am not sure how to prove it.

For every pairing, work out the difference it would make to the weighted average if the weight were doubled. This is given by $\frac{x+vw}{y+w}-\frac{x}{y}$ where:

$x$ is the numerator of the weighted average
$v$ is the value of the current pairing
$w$ is the weight of the current pairing
$y$ is the denominator of the current weighted average

Pick the largest positive difference and double the weight. If there are no positive differences, stop.
Repeat, ignoring the value you just doubled.

It seems intuitively that in the worst case, you will end up doubling all but one values, in which case you will make $2n(n+1)/n$ passes (factor of 2 in the numerator to find the largest difference after working them all out: two passes over the dataset per iteration).

I think this is the best naive solution, but can surely be optimised further for practical applications.


Extract Tree from multi-edge undirected graph I have the following multi-edge, undirected graph.

I would like to extract the following tree from it, if I start from the node $A$.

Do you know of any algorithm that I can use to achieve that ?

The problem I am trying to solve is the following.

The first graph represent different relational tables I want to join. Each edge $e_i$ represents one join between two tables (two tables could be joined on different fields, for example).

From that graph, I need to create the tree depicted in the second figure. That tree is then used for executing the joins.

Thanks

The problem is under-specified; nonetheless, I will try to help assuming that you are looking for the graph traversal tree.
To obtain such a tree, you can use a graph traversal algorithm such as breadth-first search. You can find a nice implementation of this algorithm in The Algorithm Design Manual by Steven Skiena.
Note that you need to adapt an important aspect of the algorithm:

Do not set a node as discovered unless the node has been visited from all of its incoming edges. Without this adaptation, each node will only be visited once, and, therefore, the behaviour of the algorithm will be the same as if multi-edges did not exist.

You will also need a data structure to store the tree of interest. In Skiena's implementation, this data structure is an array that is called parent: if node i is discovered from node j, then parent[i] = j.

The vertex that discovered vertex i is defined as parent[i]. Every vertex is discovered during the course of traversal, so, except for the root, every node has a parent. The parent relation defines a tree of discovery with the initial search node as the root of the tree.
Steven Skiena - The Algorithm Design Manual

However, note that you will need a slightly more complex data structure to support duplicated nodes.

I have some solution, not sure this is the best:

I consider a multiedge as single edge, and I keep track where they appear. This way I have a simple graph.
Starting from the root node, I traverse the graph in order to create a tree
for each of the multiedges, I clone the sub-tree add it to the parent. This needs to be done bottom-up (from the leaves to the root).


Choosing spanning trees to maximise node connectivity Given: n variables in X, and m sets of variables where each set, Ci contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints.

Variables in each set Ci must be connected by a spanning tree (no extra edges).
The graph should prefer spanning tree configurations so that the variance of the degrees of all nodes is maximised.
Following the previous constraint, prefer spanning tree configurations such that the degrees of nodes have greater variance, rather than average all around. So given the choice between  configurations resulting in nodes of degree 1, 2, 3 vs 2, 2, 2. Prefer 1, 2, 3.

X = {x1, x2, x3, x4, x5, x6}

C1 = {x1, x2, x3}

C2 = {x2, x4}

C3 = {x4, x5}

C4 = {x3, x5, x6}

The optimal solution for the given variables is:

Each subset of variables Ci is connected by a spanning tree, and the degree of x3 is maximised. x3 has a maximised degree, and there are nodes with degrees of 1 (preferred).

There are a few things I am having trouble with.

Actually defining the problem: this graph is a constraint graph which is to be processed under some tree decomposition or cycle cutset algorithm. Variables in each set Ci share a common attribute. I am trying to remove redundant constraints so that I can get a favourable tree structure, under some ordering, for the next stage. I'm wondering if this preprocessing step is a known problem.
Efficiently implementing this preprocessing step. I am thinking that it may be able to be reformulated as trying to minimise the average all pairs shortest paths, and then if there is a tie, pick the one with the greatest variance. And if this is the case, whether there is an efficient algorithm to do this.

EDIT: A simpler example without cycles.

X = {x1, x2, x3, x4}

C1 = {x1, x2}

C2 = {x2, x3, x4}

There is a spanning tree between, x1 and x2 for C1.

This image shows the graph if I chose all the edges instead of just the spanning tree. It is undesirable as I am trying to minimise the edges, and there is an avoidable cycle.

If I didn't create the x2 to x3 edge, the graph would have the minimal edges satisfied, but not optimal as x2 has a degree of 2. When choosing to not create the  x3 to x4 edge, x2 has a degree of 3.

If I summed the degrees in both cases they are 6. But the second case has a greater variance in the degrees (which is preferred). This is where the concept of dependency comes in, if x2 is removed in the second case, all other nodes are disconnected. In the first case, there would still be an edge between x3 to x4.

My suggestion would be to try simulated annealing.  This looks like a good candidate for that heuristic.  It sounds like you have some idea what the objective function you want to minimize is (that's good; you need one).

I would suggest that you use simulated annealing as follows:

A state is a possible graph (a set of edges).
The cost function for a state might be your objective function plus some penalty for the number of $C_i$'s that aren't fully connected.
To transition between states, you might randomly choose among the following options:

Add an edge chosen at random (or: choose a $C_i$ that isn't fully connected, and add a randomly chosen edge between some pair of variables $C_i$ that aren't currently in the same connected component)
Delete an edge chosen at random
Pick an existing edge $(u,v)$, delete the edge, then randomly choose some other variable $w$ that is in the same connected component as $v$ and add the edge $(u,w)$.

but of course you can play around with it and try different variations to see which works the best.  This might just give you some reasonable solutions.

You could also try formulating this as a SAT or ILP instance, but my sense is that I would try simulated annealing first.  If you're lucky, it just might work well enough that you don't need to bother with anything else.


Minimum number of exchanges needed to get all negative values left of all positive ones Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ?

You can keep a pointer to the currently first positive value in the list, which initializes to 0. Then scan through the list, when you see a negative value swap it with the positive value, and increment your pointer.

You get O(n) swaps in the worst case.

If the first half is positive and second half is negative, you have to have at least n/2 swaps, as the second half needs to swap places with the first half.

To actually get n/2 swaps, you can first count the # of positive values, and if the positive values are greater, iterate the list in reverse order, and keep a pointer first negative value in the list. You can then stop if you have swapped all the positive or negative values.

For your point we will use Quick sort algorithm but only for one time (one pivot) and for the worst case it will take O(nlogn) as we find solution in the first step.


Is there a known maximum for how much a string of 0's and 1's can be compressed? A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that).

This is of course not correct (and it could be that my memory of what he exactly stated is not correct). Understandably it would not be practical to compress any string of 0's and 1's to just two bits because (even if it was technically possible), too many different kind of strings would end up compressing to the same two bits (since we only have '01' and '10' to choose from).

Anyway, this got me thinking about the feasibility of compressing an arbitrary length string of 0's and 1's according to some scheme. For this kind of string, is there a known relationship between the string length (ratio between 0's and 1's probably does not matter) and maximum compression?

In other words, is there a way to determine what is the minimum (smallest possible) length that a string of 0's and 1's can be compressed to?

(Here I am interested in the mathematical maximum compression, not what is currently technically possible.)

Kolmogorov complexity is one approach for formalizing this mathematically.  Unfortunately, computing the Kolmogorov complexity of a string is an uncomputable problem. See also: Approximating the Kolmogorov complexity.

It's possible to get better results if you analyze the source of the string rather than the string itself.  In other words, often the source can be modelled as a probabilistic process, that randomly chooses a string somehow, according to some distribution.  The entropy of that distribution then tells you the mathematically best possible compression (up to some small additive constant).

On the impossibility of perfect compression, you might also be interested in the following.

No compression algorithm can compress all input messages?
Compression functions are only practical because "The bit strings which occur in practice are far from random"?
Is there any theoretically proven optimal compression algorithm?

There is an interesting and completely different algorithm that is used by enterprise backup systems. The idea is that if you have a company with 10,000 computers, then many many of these computers will contain many identical files. For example an email sent to everyone in the company might end up as an identical file on every single hard drive.

So a backup system trying to backup a file should obviously try to compress the file to save space, but first the backup system checks if an absolutely identical file is already saved! So instead of backing up anything, all that the backup system does is for example remembering that you have file number 1,487,578 on the backup system on your hard drive.

This is especially efficient for example when 10,000 users all have identical operating system and applications installed. For single users it's not very useful at all.


Strict-Binary Tree - Same Post-order & Pre-order sequences? I'm going through some past exam papers for my course and I'm having trouble completing this one question.

It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order and post-order traversal sequence".

Is this actually possible? Wouldn't I need to visit the root node before anything else for both sequences, that isn't possible with post-order traversal in a strict binary tree right? Unless the tree consisted of a single node?

I assume I'm missing something obvious. Post-order = LRN, Pre-order = NLR.

It is possible only If all nodes have same value.


Average number of comparisons to locate item in BST This is a GRE practice question.

If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (nodes) in the tree chosen at random?

(A) 1.75

(B) 2

(C) 2.75

(D) 3

(E) 3.25

My answer was 3 because $n=8$ and $\lg(n)$ comparisons should be made, and $\lg(8) = 3$. But the correct answer is 2.75. Can someone explain the correct answer? Thanks!

Recall, how expected value is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then
$$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$
where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the average over the $C(X)$s.

1 node at level 1 {E}
2 node at level 2 {C H}
3 node at level 3 {B D F }
2 node at level 4 {A G}
1*1+2*2+3*3+2*4=22
22/8=2.75(ANS)


Is there always a Big Oh complexity strictly between any two others? I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if one can always find complexities between any other two.

Specifically, for any functions f and g with O(f) ⊂ O(g) does there always exist an h such that O(f) ⊂ O(h) ⊂ O(g)?

This isn't homework or anything. I'm just curious if anyone knows.

Yes: take a function in the middle, for some suitable definition of middle. You have a wide choice.

If $O(f) \subset O(g)$ (where the inclusion is strict), then $g \in O(g) \setminus O(f)$ (because if $g \in O(f)$ and $f \in O(g)$ then $\Theta(f) = \Theta(g)$). Take the geometric mean: let $h = \sqrt{f \cdot g}$ (since we're talking about complexity here, I assume the functions are positive).

Then $f \in O(h)$ and $h \in O(g)$ (if this is not immediately obvious, prove it using the definition of $O$), i.e. $O(f) \subseteq O(h) \subseteq O(g)$. If $O(f) = O(h)$ then $g = f \in O(f)$, which is not the case since we assumed $g \notin O(f)$. It remains to prove that $O(h) \ne O(g)$, and we'll have $O(f) \subset O(h) \subset (g)$.

If $O(h) = O(g)$ then $g \in O(h)$, i.e. there exists $A$ and $C \gt 0$ such that $\forall x \ge A, g(x) \le C \, h(x) = C \sqrt{f(x) g(x)}$. Then $g(x) \le C^2 f(x)$ (take the square and divide by $g(x)$; again, I assume positive functions), thus $g \in O(f)$, which goes against our initial assumption. The hypothesis $O(h) = O(g)$ leads to a contradiction, which concludes the proof.

this seems to be true for "well defined" functions or possible "space/time constructible" however there are known to be so-called (by some) "pathological functions" found by Blum in eg Blums Gap theorem for which it is not the case. so it seems similar to the concept of eg differentiation in calculus which works for "most well behaved functions" but which "pathological exceptions" have been found. there does not seem to be much systematic/further study so far of these "pathological exceptions" in complexity theory.


Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$? We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as minimal average cost cycles, but use Bellman-Ford to discover a minimal cycle and augment along the discovered cycle. Let $V$ be the number of nodes in the graph, $A$ the number of edges, $U$ the maximal capacity of an edge in the graph, and $W$ the maximal costs of an edge in the graph. Then, my learning materials claim:

The maximal costs at the beginning can be no more than $AUW$
The augmentation along one negative cycle reduces the costs by at least one unit
The lower bound for the minimal costs is 0, because we don't allow negative costs
Each negative cycle can be found in $O(VA)$

And they follow from it that the algorithm's complexity is $O(V^2AUW)$. I understand the logic behind each of the claims, but think that the complexity is different. Specifically, the maximal number of augmentations is given by one unit of flow per augmentation, taking the costs from $AUW$ to zero, giving us a maximum of $AUW$ augmentations. We need to discover a negative cycle for each, so we multiply the maximal number of augmentations by the time needed to discover a cycle ($VA$) and arrive at $O(A^2VUW)$ for the algorithm.

Could this be an error in the learning materials (this is a text provided by the professor, not a student's notes from the course), or is my logic wrong?

According to TopCoder the correct running time is $O( A^2 \cdot VUW)$.


How many time and space units does this algorithm take? This is what I counted but I know I'm wrong since my conclusion is not in the choices:

t = time unit
s = space unit
y=1 : 1t & 1s
for 0 <= i <= N : Nt & 1s
y=y*i : 2 reads, 1 write, 1 multiplication therefore 4 time units,
the for loop is thus 4N time units
total time = 4N+1
total space = 2 (because there are only two variables that need to be
stored)

My thoughts about the question
Honestly speaking, this question is really weird. Usually when you ask about the time and space complexity, you mean it in big-O or other asymptotical notation. Not the actual literal number of steps the algorithm takes, since this can change depending on the hardware you are using and a lot of other factors.
So the fact that most answers are with the same asymptotics, it makes absolutely no sense!

My answer to the question
The answer depends on what you define a "time unit" and "space unit". Under normal circumstances, you would say this algorithm takes $\Omega(N\log(N))$ time, and would need $\Theta(N\log(N))$ space as well.
The explanation for that comes from the fact that $y$ at the $k$'th iteration is computed to be $k!$ ($k$ factorial). Saving in memory the value $N!$ needs $\log(N!)=\Theta(N\log(N))$ space, and thus also the running time must be at least $\Omega(N\log(N))$.
An upper bound for the running time depends on the algorithm used for multiplication.

Your answer to the question
Assuming multiplication takes $O(1)$ time, and a single unit of space is defined as a single variable, your solution is correct. This also demonstrates the problem of not using big-O notation, since your answer is correct however it is not one of the listed answers.

I didn't realise the system will give me an answer:


As a Teacher: Choosing a suitable programming language I'm not sure if it's the right place for this question. Sorry if going a bit off-topic.

Choosing a suitable Language for the first programming course is one of the most important things that every related teacher/lecturer should bear in mind; especially if the students are young or having a limited math knowledge.

I'm currently teaching a group of highly enthusiastic young people (about 16 to 17 years old) with a medium knowledge of math. They're attending High School at 10th grade class right now. I'm going to start teaching a programming language for the upcoming semester.

They're a group of handpicked students throughout the city with a extraordinary level of creativity and diligence, so i see that working with a real programming language would not be a hard task for them. So, choosing simple graphical and drag'n'drop solutions like Turtle Art, Scratch, and Tynker are not considered as options.

There are a few factors that should be checked before making a choice:

Simplicity: Most of them probably have not experienced any kind of real coding action before.
Simplicity, Again: One of the main ideas is teaching how to think algorithmic. Having a sophisticated or hardly-syntaxed language will divert them out of the path.
Generality: It's better that the language not be designed for special development cases. Take PHP and MATLAB as examples which are respectively designed for Web Development and Calculation/Modeling.
Minimum Objective stuff: No forced OO programming (like Java). Or at least with the minimum dependency to OO concepts.
Platform: It's important to have Windows as a supported dev environment, as neary all of them are on Windows.
Easy to Set-up: It's better to have a straightforward way of setting up the dev environment.
Industry preference: Not a serious problem. But it should be at least a currently-active language allowing students to reach nearly-real dev experiences.
Hardware Portability: It's important (but not required) that the language be flexible enough to be used on Hardware programming. (I'm not speaking of Hardware Description languages like Verilog and VHDL.) The aim is programming for more simple processor-based hardware like AVR Microprocessors or Raspberry Pi GPIO interface.

I want to know that

is there any other factors that i'm missing?
And, what languages do you suggest as choices?

My answer? Python.

Let me explain by tackling all your points.

Simplicity. Python code reads like English. Seriously, how simple is
print("Hello World!")
Generality. Python can be used for web development (via. Flask/Django), data analysis (via. NumPy/Pandas/SciPy), games (via. PyGame), as well as a multitude of other tasks because of the sheer amount of libraries there are.
Minimum Objective stuff. You can do some OOP in Python but it isn't required.
Platform. Python2.7 is in pretty much on every Linux distro and there are plenty of YouTube videos on setting it up on Windows/Mac. If anything, you can use the online interpreter that Repl.It offers.
Industry Preference. Correct me if I'm wrong, but Python has consistently been ranked as one of the most popular languages.

In my experience teaching, it is extremely important to make sure that the syntax is as easy as possible to write and understand. For a new programmer, it can be pretty discouraging when he/she writes code only to see an error message (especially if he/she does not have the skill to read an error message and debug).

Side note, PythonTutor will be really helpful in explaining some major computer science/programming concepts.

Take a look at Lazarus:

http://www.lazarus-ide.org

Lazarus is a programming environment based on Free Pascal Compiler (FPC). It runs very smoothly on Windows, and also available for other major platforms. FPC supports a modernized version of Pascal, which is called Object Pascal.

Object Pascal is a multi-paradigm programming language. You can write code in standard Pascal, then start using OO features when you need it.

Real world applications can be developed using Lazarus/FPC. They are both quite mature, but you can also use Delphi as a commercial alternative.

FPC can cross-compile your programs to devices like Raspberry Pi or Android.

Besides, future of Pascal is bright. Oberon programming language will eventually take over as the most productive way of developing software:

ht tp://www.projectoberon.com

Hopefully, tools to develop in Oberon will mature in time. There is already a cool compiler for Win64 target:

https://github.com/congdm/AyaCompiler


How to work out physical address corresponding to logical address? I am looking to calculate the physical address corresponding to a logical address in a paging memory management scheme. I just want to make sure I am getting the calculation right, as I fear I could be wrong somewhere.

So, the data I have is as follows:

The logical address: $717$
Logical memory size: $1024$ bytes ($4$ pages)
Page Table:

\begin{array}{| c | c |}
\hline
Page\ Number & Frame\ Number\\ \hline
0 & 5\\ \hline
1 & 2\\ \hline
2 & 7\\ \hline
3 & 0\\ \hline
\end{array}

Physical memory: $16$ frames

So, with $1024$ bytes in the logical memory, and $4$ pages, then each page is $256$ bytes.

Therefore, the size of the physical memory must be $4096$, right? ($256 \times 16$).

Then, to calculate the logical address offset:

$$1024 \mod 717 = 307$$

Is that how we calculate the offset?

And, we can assume that $717$ is in page $2$ ($\frac{1024}{717} = 2.8$)?

So, according to the page table, the corresponding frame number is $3$.

And so to get the physical address, we multiply the frame number and page size?

$$2 \times 256 = 768$$

Then, do we add the offset, like so:

$$768 + 307 = 1,075$$

Thank you for taking the time to read. If I don't quite have this correct, would you be able to advise on the correct protocol to calculating this?

You are correct in your reasoning that the pages are $256$ bytes and that the physical memory capacity is $4096$ bytes.

However, there are errors after that.

The offset is the distance (in bytes) relative to the start of the page.  I.e., logical_address mod page_size.  The bits for this portion of the logical address are not translated (given power of two page size).

The logical (virtual) page number is number of (virtual) page counting from zero.  I.e., $$\frac{logical\_address}{page\_size}$$

As you noted, the physical page is determined by the translation table, indexed using the logical (virtual) address.

Once the physical page number had been found, the physical address of the start of that page is found by multiplying the physical page number by the page size.  The offset is then added to determine the precise physical address.  I.e., $$(physical\_page\_number \times page\_size) + offset$$

So a logical address of, e.g., $508$, with $256$ byte pages would have an offset of
$$508 \mod 256 = 252$$
The logical/virtual page number would be
$$\frac{508}{256} = 1$$
With the given translation table, logical page $1$ translates to the physical page number $2$.  The physical address would then be
$$physical\_page\_number \times page\_size + offset = 2 \times 256 + 252 = 764$$


The time complexity of finding the diameter of a graph What is the time complexity of finding the diameter of a graph
  $G=(V,E)$?

  ${O}(|V|^2)$
  ${O}(|V|^2+|V| \cdot |E|)$
  ${O}(|V|^2\cdot |E|)$
  ${O}(|V|\cdot |E|^2)$

The diameter of a graph $G$ is the maximum of the set of shortest path distances between all pairs of vertices in a graph.

I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.

I assume you mean the diameter of $G$ which is the longest shortest path found in $G$.

Finding the diameter can be done by finding all pair shortest paths first and determining the maximum length found. Floyd-Warshall algorithm does this in $\Theta(|V|^3)$ time. Johnson's algorithm can be implemented to achieve $\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$ time.

A smaller worst-case runtime bound seems hard to achieve as there are $\cal{O}(|V|^2)$ distances to consider and calculating those distance in sublinear (amortised) time each is going to be tough; see here for a related bound. Note this paper which uses a different approach and obtains a (slightly) faster algorithm.

Assumptions:
1. Graph is unweighted
2. Graph is directed

O(|V||E|) time complexity.

Algorithm:

ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

Explanation:
We check for cycle. if graph contains cycle then we keep in moving in the loop, so we will be having infinite distance.
We check for connected. If graph is not connected that means vertex u from G1  to vertex v in G2. Where G1 and G2 is any two sub graph which are not connected. So we will be having infinite distance again.
We will use BFS to compute maximum distance between a given node(u) to all others nodes(v) which are reachable from u.
Then we will take maximum of previously computed diameter and the result return by BFS. So we will be having current maximum diameter.

Running time analyzing:

O(|E|) using DFS
O(|E|) using DFS
BFS runs in O(|E|) time.
We have to call BFS function for each vertex so total it will take O(|V||E|) time.

Total time = O(|v||E|) + O(|E|) + O(|E|)
Since |V||E| > |E|
so we have running time as O(|v||E|).

BFS
DFS

Note: This not an elegant solution to this problem.


Is $\{u u^R u : u \in \Sigma^*\}$ context-free? Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$)

I tried to show it wasn't context-free by using the pumping lemma but I'm out of ideas.

Based on : Pumping Lemma for Context-Free Languages for reversal language

By @lukas.coenig

{ww$^R$w| w $\in$ {a,b}*} doesn't seem to be a context-free language over $\Sigma$  of length two.

Assuming this language isn't context free over an alphabet of size 2 to prove it also over size of 3.. and so on by induction might be interesting..(and if true by induction than there is probably a better way to prove it)


k-ordered array problem An array $A[1...n]$ is said to be k-ordered if
$$A[i - k] \leq A[i] \leq A[i + k]$$
for all $i$ such that $k < i \leq n - k$.
For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.
Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

I can understand how the example array is two ordered, but I am having trouble understanding what the questions 1 and 2 are trying to say.
Can someone please explain to me the meaning of the questions in simple terms?
Thanks!
P.S. First time questioner here. Sorry if I missed anything.

Take your example
$$ A = [1,4,2,6,3,7,5,8]. $$
An array is 1-ordered if it is ordered, and the 1-ordered array corresponding to $A$ is $1,2,3,4,5,6,7,8$. Let's write both arrays together:
$$
1,4,2,6,3,7,5,8 \\
1,2,3,4,5,6,7,8
$$
You can see that matching digits are at distance at most 2.

An array is 2-ordered if its even elements are 1-ordered and its odd elements are 1-ordered. This could be helpful in question 1. A similar property is true for 3-ordered arrays. How do these two properties combine? I suggest you try writing out a few 2- and 3-ordered arrays to see what the possibilities are.


Given a list of students and their courses, place them in specific classes I could use some help coming up with the best way to solve this problem. I've been curious as to how something like this would work, as the worst case seems way too bad.

Problem

Given a group of students and the courses they are enrolled in, and a schedule with 8 class blocks in it, how could you place them in specific classes?

Keeping in mind you can have as many classes for a specific course as long as there is a teacher who is free to teach the class.

Specifics

There are 8 class "slots" where you can put any class, but a teacher can not teach two classes at once.

Inputs and outputs

The input is a list of students each with data on which courses they are taking. There is not specific data structure I have in mind, the problem is more theoretical than literal.

The output would be assigning a value 1-8 to each class, specifying when they would take it.

At first glance, the stable matching problem's solution is discussed in the following pdf.
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf

It would be hard to cast the course assignment problem as stable matching because he fact that the courses have a finite capacity

However, the following pdf states that, http://dss.in.tum.de/files/bichler-research/2014_diebold_matching_course_allocation.pdf

  The allocation of students to courses is a wide-spread and repeated
  task in higher education, often accomplished by a simple first-come
  first-served (FCFS) procedure. FCFS is neither stable nor
  strategy-proof, however. The Nobel Prize in Economic Sciences was
  awarded to Al Roth and Lloyd Shapley for their work on the theory of
  stable allocations. This theory was influential in many areas, but
  found surprisingly little application in course allocation as of yet.
  In this paper, we survey different approaches for course allocation
  with a focus on appropriate stable matching mechanisms. We will
  discuss two such mechanisms in more detail, the Gale-Shapley student
  optimal stable mechanism (SOSM) and the efficiency adjusted deferred
  acceptance mechanism (EADAM). EADAM can be seen as a fundamental
  recent contribution which recovers efficiency losses from SOSM at the
  expense of strategy-proofness. In addition to these two important
  mechanisms, we provide a survey of recent extensions with respect to
  the assignment of schedules of courses rather than individual courses.
  We complement the survey of the theoretical literature with results of
  a field experiment, which help understand the benefits of stable
  matching mechanisms in course allocation applications.


How to compare two circular sequences in linear time? We have two circular sequences, which means there is no start or end in the sequences, how to test if two sequence are equal or not in linear time? I have two circular sequences of E. Coli bacteria with length (4,639,221). I thought about attaching two sample of the first sequence and find the other one in it in linear time, but I was looking for a better idea, using a suffix tree is a suggestion that I think works for this problem.

Start with computing the lexicographlcally least circular substrings$^1$ of the both circular sequences and then compare them directly.

Alternatively you can check for the substring $A$ (the first seqience) in the string $BB$ (a concatenation of $B$, the second sequence) circular sequence with itself) using for example the KMP$^2$

You might also be interested in the application of the Suffix Trees (also Suffix Arrays) and this thesis reviewing the applications to DNA sequences.

$^{[1]}$(described in K. S. Booth. Lexicographically least circular substrings.
Inf. Process. Lett., 10(4/5):240-242, 1980., and here
$^{[2]}$(Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt,  SIAM J. Comput., 6(2), 323–350. Fast Pattern Matching in Strings

Start in first list with a ptr with 1X speed and the second list with 2X speed. They meet at a point after some time if they both are the same lists. From then on, you can check if each of their nodes are the same.
This is linear in time.

If they dont meet, they are not the same circular lists.


Does the Halting Problem have practical relevance? I can calculate all outputs for a finite number of states and inputs Coming from a digital functional hardware verification background, I don’t really understand the Halting Problem. I can represent the program as a state machine and show whether all inputs in all states generate a valid output or lead to an infinite loop.

The only requirement is that the inputs and states are finite. E.g. an infinite counter would lead to an infinite number of states.

Since infinite counters or infinite inputs are impossible in reality, does the Halting Problem really have a practical relevance?

Indeed, if states and inputs are finite (and the tape is finite, which is quite reasonable), then you can easily reduce the Turing machine to a Finite State Machine. However, this is completely impractical, since it doesn't yield any reasonably effective algorithms. I.e. your solution for the halting problem will be to explode the states of the TM with all possible input combinations of size N, and then find a path that reaches a stop state, right? Probably don't want to implement such a check in your compiler.

No, your reasoning is wrong.  Building a state machine and checking for cycles works only if the memory of the Turing machine is finite and bounded in length.  However, the working state of the Turing machine (the tape) is unbounded in length, so there is no upper limit on the set of possible states.  In other words, while the size of the state is finite at any specific time, the total number of possible states that might ultimately be reachable is infinite.

Yes, the Halting problem is important and has practical relevance: see Why, really, is the Halting Problem so important?