Why not implement Union-Find structure using root as the direct parent? I just learned about using UF with union by rank and path compression. A path can be compressed via attaching a node to its root after Find is called on the node. If the goal here is to flatten the tree, why not just implement the tree such that each node is directly attached to its root (instead of its true parent)? That way, maximum compression would be achieved from the start. What is the con of this as long as union by rank is used along with it?

Because then a Union operation would be very slow: when you Union two trees, you would have to reparent all of the nodes in one of the trees.


How deep do neural networks need to be? My question is a bit on the philosophical side, and there is probably not one single 'correct' answer on this. Nonetheless, I'm curious to hear your opinion...

I'm currently designing a convolutional neural network to locate features in images taken by a microscope. These features are geometrically quite simple and similar to one another, with only minor contextual variations from image to image. When I look at modern general-purpose covnets, they often have tens of convolution/pooling layers, making them a bit heavy. I can imagine that one needs many layers of abstraction when detecting cars, cats, and cods all in once, which are very distinct from one another.

Returning now to my more specialist network: would it need as many conv/pool layers as a general-purpose covnet? Or should I consider a different strategy all together (like having more fully-connected nodes)?

EDIT: Based on the comments, I feel I should rephrase/clarify my question a bit. Recently I looked into the YOLO architecture, which seems to strike a nice balance between accuracy and speed. The original version of YOLO features 24 convolutional layers, and two fully-connected layers. When I ported this architecture into TensorFlow, I noticed my GPU was struggling memory-wise: TensorFlow would give numerous performance warnings related to an insufficient memory pool, and sometimes crash from running out of RAM on the GPU. YOLOv2 only has 9 convolutional layers, and has a smaller memory footprint.

In this paper it is claimed that YOLOv2 is more accurate than its bigger brother on various VOC test sets. However, this page says v2 actually performs a worse than its predecessor in terms of accuracy, because it has fewer layers. These contrasting claims made me wonder if more layers is really better in terms of accuracy.

Turning this question inside-out, one could ask if a deep, memory intensive architecture is really necessary if the problem is relatively simple (like detecting only a single object class, instead of one thousand), while maintaining good accuracy. Intuitively I'd say that the detection of objects defined by fewer features requires fewer layers, but when it comes to deep learning, intuition has failed me on several occasions already.

At present, I have yet to start training with either architecture, so I cannot directly perform experiments on my own input data and compare the outcomes. I had hoped there would be a general rule of thumb or general guidelines for a situation like this. The comments below seem to suggest there aren't. But perhaps after this clarification, someone could offer some more advice.

The only way to know is to try it and see.  There is no general theory that allows us to reliably predict the outcome of such experiments.

That said, I question the motivation.  You say that it feels "a bit heavy", but it's not entirely clear to me what that concretely means or why it would matter.  Perhaps it is worth mentioning that even with dozens of layers, neural networks can be surprisingly fast.  Remember the warning about premature optimization: don't let a general fear or assumption that the simple solution might be slow tie you up in knots and lead you to overly complex solutions.  Instead, in this case I suggest you try the simplest solution first, and measure how well it performs.  Only if you have evidence that it fails in some concrete, measurable way would you then consider more complex approaches.  This will help you avoid unnecessarily complicating your life.

Finally, remember that there are other approaches to computer vision other than deep neural networks.  People were doing object detection before neural networks became popular, and there are other methods that might be effective for detecting simple geometric shapes (e.g., morphological operators, Hough transform, shape descriptors, and more).  But try the simple things first, and measure.


Time complexity of comparing $N$ strings I would like to double check myself.
As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length).
In case I have $N$ strings and I would like to know whether they are all different.
Is there an algorithm for this that is faster than $O(n \cdot N^2)$?

It’s much better. Say you have strings implemented as a sequence of 8 bit characters. You put each string into one of 256 bins depending on the first character. Then you examine the bins with more than one entry, by putting strings into bins depending on the second character and so on.
The worst case is all strings starting with the same $k$ characters for $k$ close to $n$; this is handled in $O(kN)$ steps. Your algorithm suffers badly in this case.


Shortest Path Passing All Routes Is there a shortest path algorithim that calculates the shortest route passing all available roads, ending where you started? This differs from the Travelling salesman problem as you need to pass through all roads between the cities, not just the cities. The traditional shortest path algorithims do not work because they only calculate the shortest distance between 2 points, and don't guarantee passing through all of the roads. Here is a vague map of my problem.

For a solution to be valid, it must pass through every road in between the points labeled.

Construct the line graph of $G$, then solve the Travelling Salesman Problem on the resulting line graph.  This yields the optimal solution to your problem, assuming you want to visit every edge in your graph exactly once.

See also the route inspection problem (also known as the Chinese postman problem).


Is this language with prefix regular? Is this language regular?
${w ∈ (a + b)∗ : |u_{a}|>= 2009 · |u_{b}|}$ for every non empty prefix $u$ of string $w$}
I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|> 2009 · |u_{b}|}$} and $L_{2}= a^*b^*$.
$L_{2}$ is regular.
I tried to show that $L_{prefix}$ is non-regular using pumping lemma.
for string z= $a^{2009n} b^n$
pumping 'a'
for i=0 : $$ z=uv^iw $$
$$z= uv^0w   $$
$$z=a^{2009n-p} b^n$$
so there is less 'a' than 2009'b'
pumping 'b'
for i=2  $$z=uv^2w $$
$$z=a^{2009n} b^{n+p} $$
again to much 'b' and less 'a' than should be.
So this is non-regular language and concatenation of this two also is non-regular .
Is it correct? Or maybe it's somehow regular?

Let $k=2009$ and $L = \{w : |u_a| \ge k\cdot |u_b|$}. I think it is easier to prove using Myhill-Neorde's Theorem.
Consider the strings $a^k, a^{2k}, a^{3k} \ldots$, we claim that all of these have a $L$-distinguishable suffix. Consider $a^{lk}$ and $a^{mk}$ with $l < m$. Let $x = b^m$. We have $a^{lk}b^m \notin L$ but  $a^{mk}b^m \in L$ (Why?). Therefore, there are infinitely many $L$-equivalence classes, which proves that, by Myhill-Nerode's theorem, that $L$ is non-regular.

Your argument is almost correct:
Assume, for the sake of contradiction, that $L$ is regular. Therefore, by closure property of regular languages, $L' = L(a^*b^*) \cap L$ will also be regular. Notice that all the words in $L'$ will be of the form $a^{n_1}b^{n_2}$ s.t. $n_1 \ge kn_2$.
Now, consider a word $w = a^{kn}b^{n}$ in $L'$. Using pumping lemma, for a sufficiently large $n$, there should exist a partition of this string $w = xvy$ such that $v \ne \epsilon$. Now, three case arises:

If $v$ lies in the part $a^{kn}$: pumping down will lead to a contradiction
If $v$ overlaps both the $a$'s and $b$'s parts: $v$ should be of the form $a^{m_1}b^{m_2}$. Pumping up will result in a string of the form $a^{kn}b^{m_2}a^{m_2}b^{m_2 + n}$, which doesn't belong to $L'$ (why?)
If $v$ lies in the part $b^n$: pumping up will lead to a contradiction


Deadlock and safe state I read that system being in safe state doesn't guarantee that deadlock is not possible.

Can someone give me an example where system is in safe state and deadlock is possible?

That is not possible, when a deadlock occurs, the system is in an UNSAFE state. A safe state wouldn't have any purpose if a deadlock could occur.


composite number Pumping Lemma for L = {$0^p$∣$p$ is a composite number} Consider the language $L = \{0^p \mid p \text{ is a composite number}\}$.

I know that this is not a regular language. I have thought that to prove this language is not regular take the complement (prime numbers) which must be regular, but its complement has prime numbers and 0 and 1 occurrences of 0's.

Could anybody give me a hint to prove without taking complement?

The Pumping Lemma will give you a way to generate strings in the language whose lengths are in an arithmetic progression.  If you pick the initial string right, you should be able to apply Dirichlet's (?) Theorem that arithmetic progressions having certain properties necessarily include infinitely many primes.


Does every thread have its main function? Does every thread have its own main function?
I know that its have its own stack, but what about main function (not necessarily a function which called main).
For example, when creating a thread, we pass a function as an argument for the new thread to run it.
I tried to search about this topic, but couldn't find answers.

For any reasonable definition of a 'main function', no.
Each thread has to start at some point in the code. For the main thread that is usually called the main function.
Modern programming languages are often designed that when starting a new thread it starts in a given function. You could call that the 'main function' of that thread, but is more commonly called its entry point.
However the entry point of a thread does not have to be at some dedicated function, or even at the start of a function. As a counterexample I would invite you to look at POSIX fork().


Is there a difference between the name scheduler and scheduling? Sometimes I read about the term "scheduler" (offline-scheduler, online-scheduler,...) and then I see terms called "scheduling" (offline-scheduling, online-scheduling, preemptive scheduling, non preemptive scheduling). Currently I think, that scheduling is the real work and scheduler is just a umbrella term. Is that correct ?

This is more a question of English than computer science. For almost any regular verb (and "schedule" is a perfect example), the [verb]er is the thing that does the [verb]ing. The scheduler is the software that schedules.


Universal quantification in description logic I'm struggling to understand the universal quantification operator in description logic. Here is an example of the problem:

given the DL concept

$\forall R.A $ (where $A$ is an atomic concept and $R$ is an atomic role)

and an interpretation $\mathcal{I}$ such that $\Delta^\mathcal{I} = \{a\}$ and $R^\mathcal{I} = \emptyset$ and $A^\mathcal{I}$ is empty or not , is it true that $(\forall R.A)^\mathcal{I} = \{a\}$?

More generally speaking, is it always the case that if $R^\mathcal{I}$ is empty then $(\forall R.A)^\mathcal{I} = \Delta^\mathcal{I}$?
Is it a vacuous truth?

In Description Logic quantification restrictions define new concepts. The semantics of $\forall R.A$ defined so that $x\in (\forall R.A)^{\mathcal I}$ if and only if for each $y\in\Delta^{\mathcal I}$ where $(x,y)\in R^{\mathcal I}$ we have $y\in A^{\mathcal I}$.

With this definition one can check that your understanding is correct: for an empty role $R$ $\top \sqsubseteq \forall R.\bot$ (all things are  related to no other thing through $R$). I dare say that few practical ontologies ever use empty roles as constructors.


Finding the Voronoi cell a point belongs to Given a set of Voronoi edges. Each edge consists of (indices of, pointers to) 4 points: $\mathrm{left}$ and $\mathrm{right}$ are sites, $\mathrm{begin}$ and $\mathrm{end}$ are vertices (one of them or even both (in case if all the sites lies on a straight line) may point to infinity). $\angle \Big(\overrightarrow{(\mathrm{left},\mathrm{right})},\overrightarrow{(\mathrm{begin},\mathrm{end})}\Big) \equiv +{\pi \over 2}$. Sites and vertices lies in two dedicated arrays. Sites are lexicographically ordered (i.e. by $x$ then also by $y$), vertices also can be easily sorted in the same manner.

What is the best way to locate point in Voronoi diagram defined as above (here, find closest site)? What are the best online and best offline ways (if differs)? I sure both of them can be constructed in linear-logarithmic time, but maybe one of them can have much lesser constant factor?

I will consider this problem on a Voronoi diagram with $n$ sites and $m$ query points.
Generally, trapezoidal decompositions work nicely for point-location. However, as we here have a subdivision of convex cells, we instead can construct a triangulation of the Voronoi diagram in $O(n)$ that can answer point location queries in $O(\log n)$, which is in fact optimal$^*$. (The complexity for the triangulation is in terms of the edges, but this doesn't matter as the number of edges of a Voronoi diagram is it most $3n-6$).

So, if we are given a Voronoi diagram on $n$ sites and $m$ query points at once, this gives an $O(n+m\log n)$ time algorithm. It makes no difference when we get the query points, so this algorithm is also online in that sense.

It isn't very clear what would be provided if the sites would be 'online', as some edges will be removed and others added when adding sites. If the number of edges added and removed are given, there is a constant number of them and the triangulation can be updated in constant time, so the total running time would remain $O(n+m\log n)$.

Another approach that may not be as good in theory but might work better in practice is to use quadtrees: you can store the set of closest sites for every square in the tree and partition the squares until the size of all those sets is small enough. Then simply locate the square containing the query point and compare all sites in the set for that square to find the nearest site.

*: See the paper: Kirkpatrick, David. "Optimal search in planar subdivisions." SIAM Journal on Computing 12.1 (1983): 28-35.


Start learning about Theory of Distributed Systems? What's the best way that anyone can do to have a good introduction to the theory of distributed system, any books or references, and topics should be covered first and requirements to start learning in this topic.

Roger Wattenhofer's Principles of Distributed Computing lecture collection is also a good place to start.

It is freely available online, it assumes no prior knowledge on the area, and the material is very well up-to-date — it even covers some results that were presented at conferences a couple of months ago.


Why 'let' can not be reduce to a lambda application in (extended) Calculus of Constructions I do not understand the difference highlighted in the chapter 2.5 of the book Theorem Proving in Lean:

  Notice that the meaning of the expression let a := t1 in t2 is very similar to the meaning of (λ a, t2) t1, but the two are not the same. In the first expression, you should think of every instance of a in t2 as a syntactic abbreviation for t1. In the second expression, a is a variable, and the expression λ a, t2 has to make sense independently of the value of a. The let construct is a stronger means of abbreviation, and there are expressions of the form let a := t1 in t2 that cannot be expressed as (λ a, t2) t1. As an exercise, try to understand why the definition of foo below type checks, but the definition of bar does not.

def foo := let a := nat  in λ x : a, x + 2
def bar := (λ a, λ x : a, x + 2) nat

What is the explanation behind this?

In an untyped language, those expressions would be equivalent. When working with types, instead, one might have a type while the other one has no type.

Assume that numbers and arithmetic operators all work on $\sf nat$. Then $e_0 = 2+2$ can be typed as $\sf nat$. Now, we can try to perform a $\beta$-expansion, i.e. to "apply $\beta$ backwards", and reach $e_1 = (\lambda x:{\sf nat}.\ x+2)2$.

$$(\lambda x:{\sf nat}.\ x+2)2 \to_\beta 2+2$$

This new expression $e_1$ would still have type $\sf nat$. But we could also go further
to $e_2=(\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2){\sf nat}$.

$$(\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2){\sf nat} \to_\beta(\lambda x:{\sf nat}.\ x+2)2 \to_\beta 2+2$$

Now, $e_2$ can not be typed. If it had a type, every subterm of $e_2$ would also be typeable, including $e_2' = (\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2)$, but this subterm can not be typed. The only type we can assign here would be of the form

$$
e_2' : \prod_{\tau:{\sf Type}} (\mbox{something})
$$

in which case this would also be typeable:

$$
e_2' \, {\sf bool} \to_\beta (\lambda x:{\sf bool}.\ x+2)2
$$

The above is nonsense, since $2$ is not a $\sf bool$, so it should not be bound to $x$.

Indeed, we just discovered that types are not preserved under $\beta$-expansion.

A first question arises:

  Couldn't we $\beta$-reduce the expression before typing?

Yes, and that's (roughly) what ${\sf let}\ \tau = {\sf nat}\ {\sf in}\ e$ does: it types $e$ knowing that what $\tau$ actually is.

And now one might counter with:

  If $\sf let$ works in that way, why don't we use the same technique for lambdas?

We can't do that, since lambdas are not always immediately applied to an argument. The syntax ${\sf let}\ x = t\ {\sf in}\ e$ shows what is the value of $x$, namely $t$. The syntax $(\lambda x. e) t$ also shows the value of $x$ but not all lambdas are used in that way: sometimes we want to use $(\lambda x. e)$ without an argument. Say, we want to pass that to another function $F (\lambda x. e)$, or build a pair of functions $(\lambda x. e, \lambda x. e')$. Here, we don't know what $x$ is. Unlike the $\sf let$ case, here $x$ could even take many values, e.g. if $F = \lambda k. k 0 + k 1$ then $F (\lambda x. e)$ makes $x$ to be $0$ on one call and $1$ in the other call.

So, $\sf let$ is less general than a lambda, and we can have a "special" typing rule for that.


Average length of s-t (simple) paths in a directed graph Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating them? What if paths are allowed to revisit vertices?

Relevant results on special graphs could also be helpful.

calculating/estimating/approximating the average path length has been studied for some random graph models including the Erdos-Renyi model and the Barabasi-Albert scale free networks, and also the Strogatz small world graphs which may be suitable as approximations for your graphs. [it would be better if you could narrow down/detail some nature/characteristics of the graphs you're studying.]

Computing the average path length and a label-based routing in a small-world graph — Philippe J. Giabbanelli, Dorian Mazauric, and Stephane Perennes
Average path length in random networks — Agata Fronczak, Piotr Fronczak, Janusz A. Holyst
The average distance in a random graph with given expected degrees
— Fan Chung, Linyuan Lu
AN ESTIMATION OF THE SHORTEST AND LARGEST AVERAGE PATH LENGTH IN GRAPHS OF GIVEN DENSITY — Laszlo Gulyas, Gabor Horvath, Tamas Cseri and George Kampis


Automata for languages derived from an automaton by number of state visits My question in response to this answer: what would the finite automata look like for $L_1$ and $L_0$ in the answer?

I get how the languages are formed; however, since $M_L$ cannot remember how many times it has looped, how does $q$ branch off (if it does) into the two different DFAs for $L_0$ and $L_1$?

Definitions:

$L$ = infinite regular language
$q$ = state within the DFA for $L$, $M_L$, where $M_L$ loops
$L_1$ = {w in A | $q$ is visited an odd number of times}
$L_0$ = {w in A | $q$ is visited an even number of times}

Starting with an automaton for $L$ with state set $Q$, starting state $s_0$, transition function $\delta$, and accepting states $F$, here is how to construct automata $M_1,M_0$ for $L_1$ and $L_0$. The state set of both is $Q \times \{0,1\}$. The starting state is $(s_0,0)$. The transition function is given by
$$
\delta'((s,x),a) = \begin{cases} (\delta(s,a),x) & \text{ if } \delta(s,a) \neq q, \\ (\delta(s,a),1-x) & \text{ if } \delta(s,a) = q. \end{cases}
$$
The accepting states of $M_1$ are $F \times \{1\}$, and of $M_0$ are $F \times \{0\}$.

In words, in addition to remember the original state, the new automaton also remembers the parity of the number of times that $q$ has been visited. Acceptance is determined accordingly.


Computability of equality to zero for a simple language Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$.

In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and can optionally contain $\pi$ and/or $e$.
$O$ can be any subset of $\{+,-,\cdot,/,\hat\ \}$.

Is equality with zero decidable? Are sign comparisons decidable? If so, are they feasible?

"Invalid" operations ($0/0$, $0^0$, ...) produce $NaN$, $NaN \neq 0$ and $NaN$ propagates through computations as usual.

Some combinations are trivial: if we restrict ourselves to field operations, and don't include either $\pi$ or $e$ in $L$ then we can just compute the resulting fraction and be done with it. Or if we restrict to $\mathbb{Z} \cup \{\pi\}$ and $\{+,-,\cdot\}$ we can compute the polynomial and check the coefficents. On the other hand powers (and hence $n$-th roots) and $\pi$ and $e$ make things considerably harder.

The "equality with zero" problem is an instance of the constant problem.

This is a rather tricky question! As you seem to understand, the real issue is the presence of $\hat{}$. It is intimately related to a well known conjecture: Schanuel's conjecture, which states that, essentially, there are no non-trivial algebraic relationships between $\pi$ and $e$.

The (expected) positive answer to this conjecture would give you a decision procedure for comparison with $0$:

Reduce the expression using algebraic equalities (e.g. $(x^y)^z = x^{yz}$ etc.)
Separate the terms with exponents and the terms without.
Check that the base ($x$ in $x^y$) of the terms with exponents are all linearly independent.
The term is 0 iff it is trivial i.e. it reduces to 0 by algebraic operations.

A related question is Tarski's exponential function problem which involves variables. However it is relatively simple to reduce concrete expressions with exponents to functions with variables given the Lindemann-Wierstrass theorem.

Edit: I don't know anything about the actual complexity of the problem, though. Note that it strongly depends on your computational model e.g. whether arithmetic operations constant time.

Edit 2: I made a crucial mistake: it's not the base $x$ in $x^y$ that needs to be taken but rather $y\ln(x)$, which is much harder to check for linear independence.


Quantum Supremacy Task I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years to compete is over my head. Is anyone able to explain it in simpler terms?

First of all it seems that google has exaggerated a little bit by shooting the $10000$ years results. It seems that IBM, on his current and most powerful classic super computer, is able to perform the same task in $2.5$ days, saving the entire search space (Hilbert space) on a $250$ petabytes hard drive. This does not mean that google's result is not to be taken into consideration: it is definitely a milestone but it will not change the world as many claim, it will not provide us with stable and multipurpose quantum computers  within a year or two (
to tell the truth, with current technologies it is not even practically possible to get computers with enough qbits and keep them in a consistent state).

Having made this premise, we come to the experiment:

Essentially (and in simple terms, very simple terms)
what they did was to correctly sample from the possible outputs of a $53$ qbits random quantum circuit using a statistical test called linear cross-entropy benchmark and sampling about $5000000$ results in about $200$ seconds. The test was a stochastic triumph.

Some notes:

people (outside the discipline) are going crazy blathering of a proof of $P = NP$ or $BQP = BPP$ and then some...
All these things are false, none of these important open problems have been solved by the experiment.
The real importance of having scalable quantum computers lies in being able to perform simulations of physical systems efficiently, which entails dramatic results in the industrial field: desig of new medicines, design of new materials, etc.
Quantum computers will not spell  the end of cryptography: not all cryptographic methods can be efficiently cracked by a quantum computation and, in addition, we already know post-quantum cryptographic techniques: for example lattice cryptography.


Finding the Largest "Ordered" Difference in Elements of an Array Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$.

I would like to design an algorithm to find the maximum profit that you can given this array of prices. Profit is made by buying at a given date $i$ and selling at a later date $j$ so that $i \leq j$.

One easy solution is the following "exhaustive algorithm":

profit = 0
for i = 1 to N-1
  for j = i+1 to N
    if P(j) - P(i) > profit
      profit = P(j) - P(i)

The issue with this however is that it takes time $\Omega(N^2)$.

Can anyone think of something faster?

The first observation is that the strategy of buying at the lowest price or selling at the highest price does not always maximize the profit. As you also note, the simple brute-force method works by trying every possible pair of buy and sell dates in which the buy date precedes the sell date. A period of $n$ days has $n \choose 2$ dates and $n \choose 2$ is $\Theta(n^2)$.

To achieve $o(n^2)$ running time, a simple transformation is applied to the input array. Instead of looking at the daily prices given, we will instead work with the daily change in price, where change on day $i$ is the difference between the prices after day $i-1$ and after day $i$. With a transformed input array like this, we now want to find the nonempty, contiguous subarray whose values have the largest sum. This contiguous subarray is called the maximum subarray.

For a detailed divide-and-conquer algorithm running in $\Theta(n \log n)$ time, see for example Chapter 4 of the Cormen et al. book, 3rd edition, page 68-74. The Wikipedia page also mentions Kadane's linear time algorithm and gives pseudocode.


Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free? I have to determine, and prove, whether the language  $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma).

I tried to construct a grammar, but I don't have a working one. I have no problems to construct the language $L=\{a^{2n} \mid$ n is a natural number$\}$. So I tried the pumping lemma, but I don't find the proof, that this is not context free.

Can someone tell me of what type this language is? A hint how to prove this would also be very nice.

Suppose that $L$ is CFL then $L$ is regular because it is a unary language. So exist a constant $N$ associated to $L$ by the pumping lemma for regular languages.

We choose the word $\sigma = a^{2^N}$ and $|\sigma| = 2^N > N $ so the pumping lemma should complies for $\sigma$. Then exist a factorization of $\sigma = \alpha \beta \gamma$ such that:

1) $|\alpha \beta|\leq N $

2) $|\beta|\geq 1$

3) $\alpha\beta^i\gamma \in L \forall i \in \mathbb{N}_0$

$|\alpha\beta^i\gamma|= 2^N + |\beta|(i-1)$ choosing $i=2$:

$|\alpha\beta^2\gamma|= 2^N + |\beta|$ so:
$$2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N$$
$$2^N<2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N<2^N +2^N$$
$$2^N<|\alpha\beta^2\gamma|<2^{N+1}$$

Then $|\alpha\beta^2\gamma|$ can't be a power of 2(with natural exponent) so $\alpha\beta^2\gamma\notin L$ and we find a contradiction. Finally $L$ can't be regular and it is not CFL too.


Formal program verification in practice As a software engineer, I write a lot of code for industrial products. Relatively complicated stuff with classes, threads, some design efforts, but also some compromises for performance. I do a lot of testing, and I am tired of testing, so I got interested in formal proof tools, such as Coq, Isabelle... Could I use one of these to formally prove that my code is bug-free and be done with it? - but each time I check out one of these tools, I walk away unconvinced that they are usable for everyday software engineering. Now, that could only be me, and I am looking for pointers/opinions/ideas about that :-)

Specifically, I get the impression that to make one of these tools work for me would require a huge investment to properly define to the prover the objects, methods... of the program under consideration. I then wonder if the prover wouldn't just run out of steam given the size of everything it would have to deal with. Or maybe I would have to get rid of side-effects (those prover tools seem to do really well with declarative languages), and I wonder if that would result in "proven code" that could not be used because it would not be fast or small enough. Also, I don't have the luxury of changing the language I work with, it needs to be Java or C++: I can't tell my boss I'm going to code in OXXXml from now on, because it's the only language in which I can prove the correctness of the code...

Could someone with more experience of formal proof tools comment? Again - I would LOVE to use a formal prover tool, I think they are great, but I have the impression they are in an ivory tower that I can't reach from the lowly ditch of Java/C++... (PS: I also LOVE Haskell, OCaml... don't get the wrong idea: I am a fan of declarative languages and formal proof, I am just trying to see how I could realistically make that useful to software engineering)

Update: Since this is fairly broad, let's try the following more specific questions: 1) are there examples of using provers to prove correctness of industrial Java/C++ programs? 2) Would Coq be suitable for that task? 3) If Coq is suitable, should I write the program in Coq first, then generate C++/Java from Coq? 4) Could this approach handle  threading and performance optimizations?

I'll try to give a succinct answer to some of your questions. Please bear in mind that this is not strictly my field of research, so some of my info may be outdated/incorrect.

There are many tools that are specifically designed to formally prove properties of Java and C++.

However I need to make a small digression here: what does it mean to prove correctness of a program? The Java type checker proves a formal property of a Java program, namely that certain errors, like adding a float and an int, can never occur! I imagine you are interested in much stronger properties, namely that your program can never enter into an unwanted state, or that the output of a certain function conforms to a certain mathematical specification. In short, there is a wide gradient of what "proving a program correct" can mean, from simple security properties to a full proof that the program fulfills a detailed specification.

Now I'm going to assume that you are interested in proving strong properties about your programs. If you are interested in security properties (your program can not reach a certain state), then in general it seems the best approach is model checking. However if you wish to fully specify the behavior of a Java program, your best bet is to use a specification language for that language, for instance JML. There are such languages for specifying the behavior of C programs, for instance ACSL, but I don't know about C++.
Once you have your specifications, you need to prove that the program conforms to that specification.

For this you need a tool that has a formal understanding of both your specification and the operational semantics of your language (Java or C++) in order to express the adequacy theorem, namely that the execution of the program respects the specification.

This tool should also allow you to formulate or generate the proof of that theorem. Now both of these tasks (specifying and proving) are quite difficult, so they are often separated in two:

One tool that parses the code, the specification and generates the adequacy theorem. As Frank mentioned, Krakatoa is an example of such a tool.
One tool that proves the theorem(s), automatically or interactively. Coq interacts with Krakatoa in this manner, and there are some powerful automated tools like Z3 which can also be used.

One (minor) point: there are some theorems which are much too hard to be proven with automated methods, and automatic theorem provers are known to occasionally have soundness bugs which make them less trustworthy. This is an area where Coq shines in comparison (but it is not automatic!).
If you want to generate Ocaml code, then definitely write in Coq (Gallina) first, then extract the code. However, Coq is terrible at generating C++ or Java, if it is even possible.
Can the above tools handle threading and performance issues? Probably not, performance and threading concerns are best handled by specifically designed tools, as they are particularly hard problems. I'm not sure I have any tools to recommend here, though Martin Hofmann's PolyNI project seems interesting.

In conclusion: formal verification of "real world" Java and C++ programs is a large and well-developed field, and Coq is suitable for parts of that task. You can find a high-level overview here for example.


Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle? When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, but I can never force the product of running time and consumed memory below a clearly palpable limit. This is formally similar to Heisenberg's uncertainty principle: the product of the uncertainty in position and the uncertainty in momentum of a particle cannot be less than a given threshold.

Is there a theorem of computer science, which asserts the same thing? I guess it should be possible to derive something similar from the theory of Turing Machines.

(I asked this question originally on StackOverflow.)

This phenomenon is known in computer science as a time-space tradeoff. For example, Ryan Williams proved that if a computer solves SAT on instances of size $n$ in time $T$ and using memory $S$ then $T \cdot S \geq n^{1.8}$. (We don't expect this to be tight.) A classical result states that when recognizing palindromes on a Turing machine, $T \cdot S = \Omega(n^2)$.


Why do we distinguish between term abstraction and type abstraction in System F? In System F, we distinguish between types and terms. Types are defined by the following BNF:

\begin{align}
A, B ::=&~\alpha && \text{(type variable)} \\
       &|~A \rightarrow B && \text{(function type)} \\
       &|~\forall \alpha. B && \text{(universal quantification)}
\end{align}

Terms are defined by the following BNF:

\begin{align}
t, u ::=&~x && \text{(variable)} \\
        &|~\lambda x : A. t && \text{(term abstraction)} \\
        &|~t~u && \text{(term application)} \\
        &|~\Lambda \alpha. t && \text{(type abstraction)} \\
        &|~t~A && \text{(type application)}
\end{align}

Can term abstraction and type abstraction be combined into a single binder? Similarly, for term application and type application? As a programmer, this distinction between terms and types at the term level seems wasteful to me. However, I'm sure that there must be a good reason for it.

Well there should be a distinction between types and terms somehow. If we had a "plus 10" function it wouldn't make any sense to apply it to a type. What is a type plus 10? So we need some kind of type system that differentiates between types and terms. This much is unavoidable. I suspect that this is the brunt of your issue.

But lets try and consolidate things a bit.

$$
\begin{align}
t, u ::=&~x && \text{(variable)} \\
        &|~\lambda x : A. t && \text{(term abstraction)} \\
        &|~t~u && \text{(application)} \\
        &|~\lambda \alpha : Type. t && \text{(type abstraction)}\\
\end{align}
$$

where Type is a new keyword. Then applications can be type checked to ensure that only terms that have types of the form $\forall a. t$ can have types applied to them and that terms of the form $\lambda x : Type. t$ have type $\forall x. t$

This is however just a rebranding of System-F! All I have done is unified the syntax a bit. This does manage to consolidate application but you might then ask what happens when we say "Type is a Type too!" so that we can have only one kind of abstraction as well. So you might try and define things like this

$$
\begin{align}
A, B ::=&~\alpha && \text{(type variable)} \\
       &|~A \rightarrow B && \text{(function type)} \\
       &|~\forall \alpha. B && \text{(universal quantification)}\\
       &|~Type && \text{(type of types)} \\
\end{align}
$$

and then try something like this for terms

$$
\begin{align}
t, u ::=&~x && \text{(variable)} \\
        &|~\lambda x : A. t && \text{(abstraction)} \\
        &|~t~u && \text{(application)} \\
\end{align}
$$

Now I have introduced some terms I didn't want to! like $\lambda x : Type \to Type. t$. We don't even have the proper machinery to use something like that! So it doesn't seem like we can consolidate much further than our first attempt lest we introduce functions on types which would take us outside of system F! Infact the above move takes us outside of system-$F\omega$ as well! Consider the term $\lambda x : \forall a. a \to Type. t$. That's a dependent type!

If we morph the system into something closer to dependent types we eventually can drop the distinction if we are very carful. Such a system would not be System-F however and thus the distinction is needed as long as we are in System-F.


Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints? Consider the Traveling Salesman Problem:
Input: $n$ cities, distances $c_{ij}$ for each ordered pair $(i,j)$ of them.

Output: Find a shortest round tour visiting every city exactly once.

I came across the following ILP formulation, where we introduce a variable $x_{ij} \in \{0,1\}$ for each pair of cities $i,j$ where $x_{ij} = 1$ means arc $i,j$ is part of the tour. Then we have:

Minimize
 $$\sum_{1 \leq i,j \leq n} c_{ij} x_{ij}$$

Subject to
$$\forall k = 1, \dots, n: \sum_{1 \leq i \leq n} x_{ik} = 1$$
$$\forall k= 1, \dots, n: \sum_{1 \leq j \leq n} x_{kj} = 1$$
$$\forall \subsetneq S \subsetneq \{1, \dots, n\}: \sum_{i,j \in S} x_{ij} \leq |S| -1 $$

While I understand the purpose of the first two constraints to make sure there is only one incoming and one outgoing edge per city, I do not understand the purpose of the third constraint. From what I read, this constraint is to make sure that solutions consisting of several disconnected tours are not possible - But how is this enforced by the third constraint and why are disconnected subtours not prevented by the first two constraints already? If we have two disconnected subtours, then at least one vertex must have an incoming edge but no outgoing edge, no?

Consider this example:

Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of the two connected components for $S$ it violates the inequality.


How does cache partitioning prevent covert/side-channel attacks? In a report on an open-source separation kernel (Muen kernel) I was reading,
in the future work section, it says that cache coloring can be implemented to prevent covert/side-channel attacks.

It is mentioned that

  In a second step each subject is associated with a color. All subjects of a given color share the same cache partition. In turn subjects of differing color have no access to identical cache locations, which means the cache cannot be used as a side-channel.

I understand what page coloring/cache partitioning is, but I do not understand how having different subjects use different cache partitions can solve side-channel attacks. Can anyone enlighten me on this?

Most L2 (and L3) caches are indexed with the physical (not virtual) address modulo a power of two that is larger than the page size. This allows different physical address colors to map to different indices, isolating replacement decisions (i.e., only accesses from the same color can cause a cache miss). The added latency from cache misses (often measured in the attacker program) can reveal the index of cache line that was replaced.

Partitioning also avoids capacity use measurement, which provides less specific information (compared to used index).

Color-based partitioning would typically not avoid bandwidth use measurement in a shared cache under default hardware configurations (which tend to be demand-based rather than fair-share; strict fair-share decreases throughput under variable demand).

For L1 caches, isolation based on physical page color would have no effect in caches that are virtually indexed. L1 sharing is more easily restricted to a temporal granularity that would not leak a significant amount of information.

It might be noted that performance isolation for multi-use systems (where different uses may give different values to different resources and even to the predictability of resource availability) is the primary/original motivation for Intel's Cache Allocation Technology ("ensuring consistent performance and prioritizing important interactive applications"), but such features can help narrow side-channels for security-oriented isolation.


How can I calculate the effective bandwidth of a memory system? I am currently doing my homework for my Computer Architecture class. One of the questions asks:

  A computer has a 64-bit data bus and 64-bit-wide memory blocks. The memory devices have an access time of 35 ns. A clock running at 200 MHz controls the computer and all operations take an integral (i.e. whole number) of clock cycles. What is the effective bandwidth of the memory system?

The problem is, there's pretty much nothing in my textbook that explains how to figure this out. Searching online doesn't return much help either. I'm not asking anybody to answer the actual homework question for me, but if you could explain to me how to figure it out, or point me in the right direction I'd really appreciate it!

An N-bit wide data bus can transfer N bits in one clock cycle, after a latency of d clock cycles (or t seconds).

I think the above sentence has everything you'd need to solve this problem.


In a Turing machine, what is the difference between the instruction table and the algorithm? In a Turing machine, what is the difference between the instruction table and the algorithm?

The instruction table seems to be an algorithm for completing the task no?

The Turing machine instruction table is a concrete implementation of the abstract algorithm. Usually, in one's everyday life as a computer scientist, there's not much to be gained by distinguishing these two concepts. Indeed, one can take the position that the Turing machine is the definition of "algorithm".


Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages? $S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff

If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$ is recursively enumerable, then $L'$ is in $S$
If $L$ is an infinite language in $S$, then there exists at least one finite subset of $L$ that is in $S$
The set of all finite languages in $S$ is enumerable, i.e. a Turing machine can list all the finite languages in $S$

Source of the statement: https://cs.stackexchange.com/q/2322 and some online notes

Isn't the 3rd one contradictory to the 1st one?

No, it is not contradictory. Both conditions are positive in the sense that they "put things in $S$", so they cannot be at odds with each other.

There is an equivalent formulation of $S$: there is an r.e. set $B$ of finite languages such that
$$S = \{L \mid \text{$L$ is r.e. and $\exists L_0 \in B \,.\, L_0 \subseteq L$}\}.$$
In words: $S$ is generated by an r.e. set of finite language $B$ in the following way: $S$ contains precisely all r.e. languages which contain an element of $B$.


Non-existence of PSPACE-hard unary language I'm trying to prove that unless $\mathsf{P}=\mathsf{PSPACE}$, there is no unary language which is $\mathsf{PSPACE}$-hard.

Assuming there is an unary language $A$ which is $\mathsf{PSPACE}$-hard, it doesn't seem reasonable to solve $A$ in polynomial time. How can this be proved then?

Suppose that $A$ is a unary PSPACE-hard language. We will show how to solve TQBF, a PSPACE-complete language, in polynomial time.

Recall that an instance of TQBF is a quantified formula of the form $\psi = \exists x_1 \forall x_2 \exists x_3 \forall x_4 \ldots \phi(x_1,\ldots,x_n)$, where $\phi$ is an arbitrary propositional formula. The instance is a Yes instance if the formula is valid.

We construct a binary tree which will represent the truth value of $\psi$. We do it level by level. Each vertex in the tree corresponds to a partial assignment of $x_1,\ldots,x_n$. At the root, we just write the empty assignment.

Suppose that we have constructed the $i$‘th level, where $0 \leq i < n$. We construct the $(i+1)$’th level as follows. For each vertex $\alpha$ on the $i$’th level, we add two children, $\alpha \cup \{x_{i+1} = 0\}$ and $\alpha \cup \{x_{i+1} = 1\}$. For each new vertex $\beta$, we consider the formula $\psi_\beta = Q x_{i+2} \ldots \phi(\beta,x_{i+2},\ldots,x_n)$. We apply the polytime reduction from TQBF to $A$ on $\psi_\beta$, obtaining a “truth value” $t_\beta$; note that there are only polynomial many possible values for $t_\beta$. These truth values may repeat; for each truth value $t$, we pick one vertex of that truth value (“live vertex”), and point all other vertices (“shadow vertices”) having the same truth value to that vertex; we won’t add new children to the shadow vertices in the next step.

After $n$ such steps, all the (polynomially many) leaves are labeled by complete truth assignments $\gamma$ to $x_1,\ldots,x_n$. We can evaluate $\psi_\gamma$ directly, and so obtain the real truth values of all live vertices on the $n$’th level, and deduce the real truth values of all shadow vertices on the $n$’th levels. From these we can deduce the real truth values of all live vertices on the $(n-1)$’th levels, and hence of all shadow vertices on that level; and so on. Eventually, we will find the truth value of $\psi$.

Since each level contains only polynomially many vertices, this algorithm runs in polynomial time. It follows that $\mathsf{P}=\mathsf{PSPACE}$.


Check if an array is a substring of another array Given two sequences $A$ and $B$,
we want to check if $A$ is a subsequence of $B$ where the elements of $A$ appear in $B$ consecutively and in the same order.

Example 1.

input: $A = (4 , 6 , -5), B = (2 , 4 , 6 , -5 , 4)$,
output: Yes

Example 2.

input: $A = (2 , 6 , 4), B = (2 , 4 , 6 , -5 , 3)$,
output: No — although $B$ contains all the elements in $A$,
the order is not correct.

Example 3.

input: $A = (2 , 6 , 4), B = (2 , 3 , 6 , -5 , 4)$,
output: No — although $B$ contains all the elements of $A$ in the correct order, they are not consecutive.

Let $n$ and $m$ be the size of $A$ and $B$.

How fast can we solve this problem?

What I have tried

I have an algorithm that runs in time $O(nm)$ as follows:

  go over elements of A,
  for each of them go over elements of B and see if we can find a matching element,
  which is after the matching element for the previous element of A.

The problem is called substring search or string search or string matching. It's called a substring even if the elements of the array aren't characters. In this answer, I'll use character to refer to elements of the arrays, but this can be any kind of data (numbers, nested data structures, …). The standard terminology is:

subset (without multiplicity): all the elements of $A$ are also found in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,2)$.
subset with multiplicity: for every element of $A$, there is a corresponding element in $B$. The difference from the basic subset problem is that if an element in $A$ is repeated, it must be repeated at least as many times in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,1,2)$ but not of $(3,4,1,2)$. The terminology around this problem isn't completely standardized, sometimes ”subset“ refers to this.
subsequence: the elements of $A$ are also present in $B$, in the same order, but there may be other elements in between. For example $(1,2,3)$ is a subsequence of $(0,1,0,2,3,4)$ and $(1,2,2,3)$ but not of $(3,1,2,0)$.
substring: the elements of $A$ are also present in $B$, in the same order and consecutively. For example $(1,2,3)$ is a substring of $(0,1,2,3,4)$ but not of $(1,2,2,3)$.

Substring search is a very well-studied problem. The naive approach, where you take each possible starting position in $B$ in turn and try to match $A$ there, runs in $O(m\,n)$ where $m$ is the length of $A$ and $n$ is the length of $B$.

The naive approach can be improved because it often ends up making tests which could have been known to be false or whose outcome doesn't affect the final result. For example:

If one of the elements of $A$ never occurs in $B$, this can be noticed with a single pass in $B$, in time $O(n)$: there's no need to test the other characters of $A$. More generally, if a character in $A$ occurs rarely in $B$, it's best to match this one first against the elements of $B$.
When matching abcdabe at the start of abcdefabcdabcdabe, once position $5$ is reached (a ≠ e), the naive algorithm tries to match $A$ starting at position $2$. An improvement is to notice that the first character of $A$ wasn't present in the positions of $B$ that have already been read, so there's no need to test $A$ again against earlier positions.

Improved substring search algorithms rely on preprocessing $A$ to notice opportunities like these to make the matching more efficient. For example, a simple approach from a theoretical perspective is to build a deterministic finite automaton that recognizes the regular expression $\mathord{.}^*A$, which recognizes all strings that end in $A$. If the automaton ever reaches an accepting state, this indicates that $A$ has been found as a substring of $B$. This algorithm requires a preprocessing phase on $A$ which requires $O(m^2)$ time; after this, $B$ can be processed with no backtracking. Each position in $B$ requires $O(1)$ time to analyze the character in $B$ and look it up in the table of transitions from the current node in the automaton. Thus the running time for the search (including preprocessing) is $O(m^2 + n)$.

Two common substring algorithms are:

Knuth-Morris-Pratt, which builds on the same idea as the finite automaton, but constructs a more specialized table in time $O(m)$, for a total running time of $O(n)$.
Boyer-Moore, which also builds a table, and tries matching from the end of $A$, which allows it to skip characters in $B$. The basic Boyer-Moore algorithm has a $\Theta(m\,n)$ worst case (like naive search), but can pass over non-matching strings in time $n/m$ in the best case. There are Boyer-Moore variants with an $O(m+n)$ worst case.

Intuitively, $O(m+n)$ is as good as it gets, since in the worst case all characters in $m$ and $n$ must be read (the worst case being reached when $B$ is full of substrings that are close to $A$ but not identical).


Space complexity of string indices: O(1) or O(log|S|)? Say you have a string S and wish to store indices of it, e.g. letter at index 3 of "toast" is 'a'. Seems that people generally consider an index as taking O(1) space to store*. But doesn't it take O(log(|S|)) space?

If we use binary bits...

length 4 string => index must be at least 2 bits
length 8 string => index must be at least 3 bits
length n string => index must be at least log(n) bits

*An example of where I'm seeing O(1) suggested: educational sources state that a suffix tree has O(|S|) space complexity, where S is the input string, because there are O(|S|) nodes in the tree, and each node is just an index in the input string. This implies that each index takes O(1) space, but this seems untrue to me. Seems like the tree takes O(|S| log(|S|)) space.

*More examples: Many basic data structures (hash tables, BSTs, etc) use memory pointers (equivalent to string indices), and everyone considers these pointers fixed-size.

These are correct (unless you explicitly specify a non-standard model of computing):

$O(1)$ space,
$O(1)$ words of space,
$O(\log|S|)$ bits of space.


What was going on before PAC learning I am investigating PAC learning (computational learning theory) as a beginner with no previous knowledge of machine learning / AI. I am investigating the model mainly from a historical point of view.

For this, the most important things are of course the results based on the model. There are enough papers out there that document these results. But I also want to write something about what was going on before PAC learning, as to sketch the historical context up to where Valiant came with the notion of the PAC model.

No papers/surveys I've found so far document this, and as someone with no real knowledge of machine learning, it is hard to find this out. I am therefore asking this soft question here, because I believe there are enough experts that can help me with this. References are highly appreciated.

When I can research and study what was going on before PAC, I might get a better appreciation as to why the academic world is so enthusiastic about the PAC model, which is also something interest to document in my historical work!

References are highly appreciated.

An author is expected to address the question of the context and relevance of his results at the begin of his publication. I just skimmed over the introduction of "L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984." again, and found out that Valiant indeed well covered your question.

The original paper by Valiant is both freely available and not too difficult to read. (Except section 7, which only proves that the author can also tackle challenging mathematical problems, but doesn't contribute much to the real content of the paper.) Reading at least its introduction will be more rewarding than reading my overly long answer to this question, so I suggest to really try it.

The rest of this answer tries to cite some passages from the introduction which should indicate whether reading this introduction might answer the question about the historical context. Note however that an author has the natural prerogative to be biased with respect to such questions.

  ... such a system would, at least, be a very good start. First, when one examines the most famous examples of systems that embody preprogrammed knowledge, namely, expert systems such as DENDRAL and MYCIN, essentially no logical notation beyond the propositional calculus is used.

This is interesting information for the context, because propositional calculus is significantly weaker than predicative calculus or the various systems of type theory sometimes used today. (Strange enough though, Prolog (1972) and ML (1973) were among others intended as meta-languages for "such" expert systems, and seem to go beyond simple propositional logic as far as I can see. Also, the relational model (1969) for database management is claimed to be based on predicate logic.)

  Perhaps the main technical discovery contained in the paper is that with this probabilistic notion of learning highly convergent learning is possible for whole classes of Boolean functions. This appears to distinguish this approach from more traditional ones where learning is seen as a process of "inducing" some general rule from information that is insufficient for a reliable deduction to be made.

I fully agree here. It is important to be able to explain how your solution is able to solve a given problem, and in which sense it is a solution. Otherwise, you just end up with "no-free lunch" theorems which don't allow you to distinguish a buggy implementation of a dubious heuristic from a correct implementation of an appropriate heuristic.

  In summary, this paper attempts to explore the limits of what is learnable as allowed by algorithmic complexity. The results are distinguishable from the diverse body of previous work on learning because they attempt to reconcile the three properties ((1)-(3)) mentioned earlier. Closest in rigor to our approach is the inductive inference literature [...]. There is a large body of work on pattern recognition and classification, using statistical and other tools [...]. Learning, in various less formal senses, has been studied widely as a branch of artificial intelligence.

The properties ((1)-(3)) were that (1) "the machines can provably learn whole characterizable classes of concepts" which are (2) "appropriate and nontrivial for general-purpose knowledge" and (3) "the computational process requires only a feasible (i.e., polynomial) number of steps".


Finding the number of intersections of $n$ line segments with endpoints on two parallel lines Let there be two sets of $n$ points:

$A=\{p_1, p_2, \dots, p_n\}$ on $y=0$

$B=\{q_1, q_2, \dots, q_n\}$ on $y=1$

Each point $p_i$ is connected to its corresponding point $q_i$ to form a line segment.

Example:

I need to write a divide-and-conquer algorithm which returns the number of intersection points of all $n$ line segments and runs in $O(n logn)$.

I was reading about Sweep Line Algorithm but found out its complexity depends on the number of intersections, which can be ${O}{n\choose 2} \subseteq O(n^2)$ (besides the fact that it isn't a divide-and-conquer algorithm).
I believe I should use the fact that each set of points has the same $y$ value, but I'm not sure how. Any suggestions?

Since all points are distinct, this is a version of the Counting Inversions problem. First, sort the points $p_1, \dots, p_n$ in order of increasing $x$ coordinate to obtain an ordered list $p[1],p[2], \dots, p[n]$. We now relabel the points $q_1, \dots, q_n$ with respect to this new ordering of the $p$'s such that $p[i]$ and $q[i]$ are endpoints of a line segment, for all $1 \leq i \leq n$. Altogether, these steps take $O(n \log n)$ time.

Now, we want to count the number of inversions in $q[1], \dots, q[n]$; an inversion is a situation where $i < j$ and $q[i] > q[j]$ (we compare the points by their $x$ coordinates). This is because $i < j$ implies $p[i] < p[j]$ by construction, and $p[i] < p[j]$ and $q[i] > q[j]$ if and only if the line segments $(p[i], q[i])$ and $(p[j], q[j])$ intersect. Hence, the number of line segment intersections is precisely the number of inversions in $q[1], \dots, q[n]$.

There is a well known divide and conquer approach for counting these inversions. Can you take it from here?


Can a deterministic finite automaton ever go into an infinite loop? As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.

A deterministic finite automaton can only go to infinite loop if the input string is infinite. For finite inputs, the automaton stops when the input string ends. For infinite inputs, for example the automaton for regex 0*1 will loop infinitely if the input string is an infinite sequence of 0.


Is there a term for these "descendancy" subgraphs of directed acyclic graphs? Consider a directed acyclic graph $G$ with vertex set $V$.  Choose a vertex $v$, and let $H$ be the subgraph containing $v$ and all other vertices in $G$ that are reachable from $v$ (along with the associated directed edges).

(In other words, if we choose $v \in V$, then we are interested in the subset consisting of $v$ and all of its descendants).

Is there an accepted term for this particular subset of vertices (or the subgraph)?  It seems to be a fairly elementary concept so I expected to find a commonly used phrase for this, but my search is coming up empty so far.   Thanks for any answers or leads!

Kind of. But we're going to use the usual computer sciency way of describing this, using the language of binary relations.

You're probably already familiar with binary relations, like equality $=$, less-than-or-equal-to $\le$, subset $\subseteq$, and so on. In general, a binary relation $R$ over a set $X$ is a subset $R \subseteq X \times X$. If $(x,y) \in R$, we denote this as $xRy$.

If $\forall x \in X, xRx$, then $R$ is reflexive. The relations $=$ and $\le$ are reflexive, but $\lt$ is not.

If $\forall x, y, z \in X, xRy\,\wedge\,yRz \Rightarrow xRz$, then $R$ is transitive. Plenty of relations are transitive, including all of the ones given above. If $x \le y$ and $y \le z$, then $x \le z$.

Given a relation $R$, the reflexive transitive closure of $R$, denoted $R^*$, is the smallest relation $R^*$ such that $R \subseteq R^*$, and $R^*$ is reflexive and transitive.

Interpreting your graph as a binary relation (since the edges don't really seem to matter to you, you're only interested in the set of vertices), this is exactly what you want: $xR^*y$ if and only if $y$ is a "descendant" (by your meaning) of $x$.

When looking at the literature, you will need to know one more piece of notation: the transitive closure of $R$, denoted $R^+$, is the smallest relation $R^+$ such that $R \subseteq R^+$, and $R^+$ is transitive. Algorithms for computing the transitive closure and the reflexive transitive closure are related, since they differ only by the "diagonal" entries: $R^+ \cup \left\{ (x,x)\,|\,x \in X \right\} = R^*$.

There are several standard algorithms for computing the RTC of a relation. If the relation is dense, in the sense that it's feasible to represent it as a bit matrix, the Floyd-Warshall algorithm is one of the fastest practical algorithms; its run time is $\Theta(|V|^3)$ in theory, but the inner loop is quite fast on real hardware given that it it a bunch of bit vector manipulations.

For sparse relations, see Esko Nuutila's thesis, which contains a very good survey as well as some more recent algorithms.


Why contraction and weakening rules are the upside down? On the A taste of linear logic paper, the author claims that:

  A rule consists of zero or more judgements written above a line, and one
  judgement written below. If all the judgements above the line are derivable, then the judgement below is derivable also.

He then proceeds to show the following rules:

He then describes those rules as:

  Contraction expresses that any hypothesis may be duplicated, and Weakening expresses that any hypothesis may be discarded.

That looks upside down. Reading the "Contraction" rule in English, we have that "if assumptions Γ, A, A imply B, then assumptions Γ, A also imply B" - notice that we discarded an assumption instead of duplicating it. Similarly, the "Weakening" rule adds an assumption to the conclusion, rather than discarding one from the premises as the author seems to suggest. Why?

Contraction is called contraction because it contracts the two hypotheses into one: $A, A$ is contracted into $A$. Weakening is called weakening because it allows one to deduce a weaker fact: $\Gamma \vdash B$ is stronger than $\Gamma, A \vdash B$ since fewer hypotheses are needed to obtain the conclusion. The names come from forward reasoning: deducing facts from other facts. When you're deducing new truths, you can take already-proven truths and add hypotheses or remove duplicated hypotheses.

When you look at contraction from the point of few of backward reasoning, i.e. examining why a fact might be true, then the contraction duplicates a hypothesis. Similarly the weakening rule discards a hypothesis. When you're trying to prove a goal, you can duplicate or discard hypotheses to get a new goal whose truth implies the truth of the original goal.


Heap structure in array, computing parent and child I am studying data structures from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, that means, a binary tree with all of its levels complete except possibly the lowest, which is filled from the left up to a point.

In this book it says that a common way to represent this data structure is an array, beginning from the index 1 of the array and putting from left to right the first level of the tree, then from left to right the second level of the array and so on. It states that this representation is useful because given a node $n$ of the tree lying in position $A[i]$ of the array, its parent and children can be easily computed as :

Parent = $A[i/2]$

Left child = $A[2i]$

Right child = $A[2i+1]$

I am having a hard time trying to understand why its parent and children are in these positions on the array, could someone give me an intuitive explanation of why this is the case?

While it is possible to write a formal proof, I think the best proof is by picture:

If you still want a formal proof, here it is. We start by noting that level $d$ of the tree (counting from 0) contains $2^d$ nodes, and so a simple induction shows that level $d$ occupies the indices $2^d, \ldots, 2^{d+1}-1$. Consider now the $i$th node on the $d$th level (again, counting from zero). Its children are nodes $2i,2i+1$ on level $d+1$, as the following table makes clear:
$$
\begin{array}{c|c}
\text{parent} & \text{children} \\\hline
0 & 0,1 \\
1 & 2,3 \\
2 & 4,5 \\
\cdots & \cdots
\end{array}
$$
The index of the $i$th node on the $d$th level is $2^d + i$. The indices of nodes $2i,2i+1$ on level $d+1$ are $2^{d+1}+2i,2^{d+1}+2i+1$. Notice that
$$
2^{d+1}+2i = 2 \times (2^d + i), \\
2^{d+1}+2i+1 = 2 \times (2^d + i) + 1.
$$
This explains the formulas for the left and right children. The formula for the parent follows similarly, since
$$
\lfloor (2^{d+1}+2i)/2 \rfloor = \lfloor 2^d + i \rfloor = 2^d + i, \\
\lfloor (2^{d+1}+2i+1)/2 \rfloor = \lfloor 2^d + i + 1/2 \rfloor = 2^d + i.
$$


An algorithm to find highest lines in at least one point Suppose we have $n$ lines $L_1, L_2, \dots, L_n$, where $L_i$ has the equation $y = a_i x + b_i$. We call $L_i$ the highest line at $x_0$ if for each $j \in \{1, 2, \dots, n\}$

$$a_i x_0 + b_i \ge a_j x_0 + b_j.$$

Goal: Find an algorithm in $O(n \log n)$ time to return a set of lines that are the highest lines in at least one point.
Hint: Use the divide and conquer technique.

Since we should use divide and conquer technique, I think I should split the problem into two subproblems with size of $n/2$ and try to solve these two first. I don't know what to do next. Thanks in advance.

If the lines are unlimited (as they seem to be) then the way to go seems to divide the lines by their slope.

Preprocessing:

Sort all the lines lexicographically by their slope and constant term. This allows to remove each line which is parallel to some higher-placed line. The ordering is also used to split the lines into subroups depending on their slope later on.

Recursion:

Divide the lines into lines with positive and negative slope. For each group call recursion. From each recursion we get two lists, a list of top-lines (ordered as they appear on top from left to right) and a list of top-intersections of the top-lines (ordered by x-coordinate) corresponding to the points where one line takes over the previous one.

Now we only need to combine the two results we got from recursion. The algorithm passes through the intersection-point lists in parallel, going through positive-slope lines from right to left, and through negative-lines from left to right until the x-coordinates of the intersections meet. To do this properly, we need always make the step on the side with higher y-coordinate.

(I strongly suggest to draw it, it's easier to see in a picture. Imagine bunch of lines forming a "U"-shape and the algorithm descends with equal vertical speed on both sides until it reaches the lowest point of the "U"-shape.)

In this way we found a "middle" point where one positive- and one negative-slope top-line meet in a new top-intersection. From the list of lines we know which lines meet there and we can compute the intersection point they share (the lowest point of the "U"-shape).

We can now construct the total list of intersections of top-lines (all the point we went through + the new intersection point we found in the middle) and the list of the corresponding top lines.

Note that it might happen that all the positive-slope intersection might be too much to the left (so we do not get a "U"-shape). In that case we only get one positive- and one negative-slope line as a result, intersecting in an "V"-shape.

Now, how to split the groups in the recursion? Well, simply realize that by tilting (by less than 90 degrees) what the algorithm understands us "horizontal" none of the necessary properties is violated (within the subgroup). Thus the algorithm can again split the groups into smaller groups, while the left-right orderings remain consistent. So in fact we don't want to split lines into positive and negative slope, but simply split by the median slope each time. (splitting by the horizontal direction just makes it easier to understand)

Complexity:

Each level of recursion is linear-time in respect to the number of lines (going through lists in parallel, concatenation of lists, etc.). Since the lines are already ordered by their slope (from preprocessing), we can always split by the mean slope in linear time. So the total time is O(nlogn).

Hope the description is somewhat clear. I did not go into details as that would be lengthy.


Taking the modulus of 2 arrays I'm putting together a primality tester for large numbers. When the numbers were smaller things were more straightforwards. I got refined it to a point where I could quickly test any number within the range of long long ints. I wanted to be able to test larger numbers. I've gotten it to read the numbers in as strings then convert to an array. I now have the issue of not knowing how to perform mod on arrays. (int*)mod(int) isn't too bad but (int*)mod(int*) is more complicated.

In short:

Is there a relationship between n%c and n%a,n%b where a+b=c
How do you take the mod of 2 sums where either sum would give you overload.

Representing integers that are larger than the machine integer size by an array of digits is the standard way to do it, and it's usually called bignum, or more formally arbitrary-precision arithmetic.

Division on bignums is not simple. There's no shortcut: it isn't like with addition and subtraction where you can make a single loop that goes over both arrays. You can use the long division method you learned in primary school. There are more complex methods that have better performance in general; the Wikipedia article has a good overview.

There is no useful relationship between $n \bmod (a+b)$ and $n \bmod a$ and $n \bmod b$. I don't see where this would come up anyway. (On the other hand, $(a+b) \bmod p$ is either $(a \bmod p) + (b \bmod p)$ or $(a \bmod p) + (b \bmod p) - p$ depending on whether the sum overflows $p$).

When computing with numbers modulo $n$, always reduce modulo $n$ after each operation, to avoid having numbers grow too large. During one operation, it's usually useful to allow one more digit, to accumulate carries on partial results.

Note that primality testing is rarely done on large numbers, because it gets extremely slow. In cryptography, approximate algorithms are used, that have a small probability of accepting a composite number as prime (but if the algorithm says “prime”, then the number may not be prime, but it's “difficult” to factor).


Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)? I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays for front-of and end-of operations make sense intuitively, but for operations in the middle, not so much.

I see why the middle insert is O(n) for a dynamic array - half the elements need to be shifted one by one.

But, when it comes to linked lists, don't half the elements need to be traversed one by one starting from the head to find the insertion point? And if so, why doesn't that also make linked lists O(n) for middle insertion? And if it does, why is it not represented that way in the Wikipedia article?

You are right: if we have to find a particular place and then insert a value there (for example, insert an element in a sorted list), it is $O(n)$ for a linked list.

However, the Wikipedia article you seem to mention considers another operation named insertAfter: given a node, insert an element after that node.
When the particular node after which to insert is given to us, we spend only $O(1)$ time to do so, as we don't have to search for it.

An example usage is "duplicate each value $x$ we find in the list".
An example solution is to traverse a list, and whenever we find an $x$, add a duplicate right after it, and immediately step over it.
Each such insertion takes $O(1)$, and the whole solution is $O(n)$.
Note that, without any preallocation strategy, solving such a problem with a dynamic array is $O(n^2)$ worst case.


How to XOR automata? Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online.

$x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) (\neg ((x|y)(\neg x|y))|z)$. This is way too complicated and time consuming to draw. Isn't there another way?

Thank you for taking the time!

Note that the construction for the intersection and union ("and" and "or") of two automata is exactly the same, except for the definition of which states are accepting. The same principle applies to any Boolean combination of any finite set of languages: use the product construction and the appropriate definition of which states should be accepting.


Turing Machine - Tape Question I have a question regarding Turing machines.

Are these two tapes the same thing?

First one =  _ _ _ _ * A A A B B B

Second one =  * A A A B B B

_ denotes a blank tape cell.

Well, kind of, but not really. A defining characteristic of a Turing machine is its current head position, where the head is reading and writing from the tape. These two tapes appear to be identical, but the tape head isn't in the same place. It depends on how you define "the same thing": the tapes themselves are the same, but the Turing machines' states are not.


Why does the solution of an NP problem have to be polynomial size? I've read in "Introduction to Algorithms" (CLRS) that formal language $L$ is NP-language if and only if there is a polynomial verification algorithm $A(x, y)$ and a constant $c$ such that $$L=\{x\in\{0,1\}\mid \exists y \text{ with } |y| \leq |x|^c\text{ and } A(x, y)=1 \}\,.$$

What is the purpose of the constraint: $|y| \leq(|x|^c)$?

First, let's refresh the proof that the definition given is indeed equivalent to the standard definition of NP, i.e., the class of languages accepted by polynomial-time nondeterministic Turing machines.

Suppose $L$ is accepted by a polynomial-time Turing machine $M$. There is some $c$ such that $M$ runs in time $|x|^c$ for all inputs $x$. The verification algorithm is as follows: given $x$ and $y$, interpret $y$ as being a sequence of states of $M$ (expressed in some appropriate alphabet), and accept the pair $(x,y)$ if, and only if, $y$ describes an accepting path of $M$ on input $x$. Now, for any string $x\in L$, $M$ has an accepting path of length at most $|x|^c$, there exists a $y$, also of length at most $|x|^c$, such that $A$ accepts $(x,y)$. If $M$ rejects $x$, then there is no accepting path, so no string $y$ can describe an accepting path, so $A$ rejects $(x,y)$ for any string $y$.

Conversely, suppose that a polynomial-time algorithm $A$ exists with the properties stated in the question. We can construct a nondeterministic polynomial-time algorithm for $L$ as follows.  Given input $x$, nondeterministitically "guess" (generate) a string $y$ of length at most $|x|^c$ and see if $A$ accepts $(x,y)$. If $x\in L$, then there is a string $y$ of length at most $|x|^c$ such that $A$ accepts $(x,y)$, so our machine accepts; if $x\notin L$, then no string $y$ has the desired property, so our machine rejects. This is a nondeterministic polynomial time algorithm because it does a polynomial about of guessing and a polynomial amount of simulation of $A$.

So, what goes wrong with this if we remove the condition that there exists some $y$ specifically with length at most $|x|^c$?  Well, the first half of the proof still works: if $L$ is in NP then $A$ exists and, hey, it still happens to have the property that $|y|\leq |x^c|$, even though that wasn't required. However, the other half of the proof breaks. We no longer have the guarantee that it's enough to guess $|x|^c$ bits. In fact, we have no guarantee at all. We'd have to keep guessing longer and longer strings to test with $A$ and, actually, the procedure would never terminate for $x\notin L$: there's no way to tell if there really is no $y$ for which $A$ accepts $(x,y)$ or if there is such a $y$ but it's just so long that you've not seen it yet (undecidability of the halting problem).

So, without the polynomial bound on $|y|$, every NP langauge can still be expressed in this way but, unfortunately, so can all recursively enumerable languages. The polynomial bound is required to restrict the class of languages described to just NP.


Is {a^i b^j c^k | i≤j or (k=j≤i)} context sensitive? $$L = \{a^i b^j c^k \mid i \le j \text{ or } (j \le i \text{ and } j = k)\}$$

I think the given language is CSL as i can break this language like this

$$L = \{a^i b^j c^k \mid i \le j \text{ and } j = k\}
 \cup \{a^i b^j c^k \mid j \le i \text{ and } j = k\}
 \cup \{a^i b^j c^k \mid i \le j \text{ and } j \le i \text{ and } j = k\}$$

Last language i,j are independent, hence DCFL.

When we take union of these languages, we get CSL.

Is my approach right?

There are two possible interpretations of the condition on $i,j,k$:

$(i \leq j \lor j \leq i) \land j = k$. This condition is equivalent to just $j = k$, and so the language in question is $\{ a^i b^j c^j : i,j \geq 0 \}$, which is a prototypical context-free language.
$i \leq j \lor (j \leq i \land j = k)$. A linear-bounded automaton can decide this language (exercise), so it is context-sensitive. On the other hand, using the pumping lemma you can show that it is not context-free (exercise).

I would guess that the second interpretation is the one that was intended.


Büchi automaton with modified acceptance condition Consider a Büchi automaton $\mathcal{A}$ with the modified acceptance condition, that an $\omega$-word $\mathcal{w}$ is accepted by $\mathcal{A}$ iff every run $\rho$ of $\mathcal{A}$ on $\mathcal{w}$ is accepting (rather than at least one run being accepting). I need to show that this automaton also accepts only $\omega$-regular languages. How do I go about doing that?

Let $S$ and $F$ be the set of all states and all accepting states of $\mathcal{A}$, respectively. For $t \in S \setminus F$, let $\mathcal{A}$ be the automaton obtained by making $t$ the only accepting state. For $t \in S \setminus F$, let $\mathcal{B}_t$ be the automaton obtained by removing all states in $F$, and making $t$ the starting state. We think of $\mathcal{A}_t$ as an NFA, and of $\mathcal{B}_t$ as a Büchi automaton. The following language is $\omega$-regular:
$$ L = \overline{\sum_{t \in S \setminus F} L(\mathcal{A}_t) L(\mathcal{B}_t)}. $$
An $\omega$-word $w$ is not in $L$ if and only if on some run of $\mathcal{A}$, no accepting state appears infinitely often. Therefore an $\omega$-word $w$ is in $L$ if and only if on all runs of $\mathcal{A}$, some accepting state appears infinitely often.


Finding numbers near the median in linear time Problem:
Describe (English is enough) a linear algorithm that, given a set $S$ of $n$ distinct numbers and a positive integer $k \leq n$, returns the $k$ numbers in $S$ that are closest to the median of $S$.
Answer:
I interpret the term linear algorithm to mean one that runs in $O(n)$ time. It is not clear to me if that means worst case or average case. I would tend to think worst case.
\newline
I claim that problem may not have a unique solution. For example, if we are given
$S = \{ 1, 2, 3, 4, 5 \}$ and $k = 2$ then we have the following two valid solutions:
\newline
$S = \{ 2, 3 \}$ and $S = \{ 3, 4 \}$.
Here is my algorithm, which I do not believe meets the performance requirements
of the question:
Let ans be the set of numbers we want to return.
Compute the median of S and call that value m.

Initialize the set ans to the first k elements of S.
// One data structure to hold ans would be an array. A better choice might be
// a binary tree / heap.
for i = k+1 to n (inclusive)
       if S[i] is closer to the median then the element of ans that is farthest
            away from the median then
                update ans by replacing that element with S[i]
       end if
end for
return ans

I am assuming that we can find the median in $O(n)$ time. Depending on the data structure chosen for ans, the running time for the code will be $O( n \log k )$ which is linear in $n$.
This does not seem right to me. Is it? If it is wrong, where did I go wrong?
Does this problem even have a valid solution?

There is an algorithm that finds the $\ell$-th smallest element in an array of length $n$ in time $O(n)$. You can find the $(n-k)/2$-th smallest and the $(n+k)/2$-th smallest elements in $O(n)$ using this algorithm, and then, using an additional pass, find all elements in between.


Kth smallest element in an arra What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?

You can use quickselect with median of medians to find a good pivot so that the total running time is linear in the worst case.


How do we derive the runtime cost of Karatsuba's algorithm? I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it.  I seem to have gotten about 75% of the way to the solution on my own, but lack the last 25% to fully understand why the complexity is $O(N^{\log3})$ where the log function is base $2$.

I worked out myself that the recursion tree has height $\log N$ (easy to see), and I understand the coefficient $3$, which can trade places with $N$ due to the properties of logs, comes from the fact that each level of recursion results in three leaves per node of the tree.

I think the main thing that's tripping me up is I'm that not clearly seeing why $\log N$ can be expressed as the exponent of $3$, although I see where $\log N$ and $3$ come from, and I see how in the next step you can swap $N$ and $3$ to get $N^{\log3}$ (something I learned in highschool).

To put this another way, I've been unable to work this problem out to visualize sequentially how this formula plays out for the algorithm.  I.E, without already knowing the Master theorem, how does one derive this formula (I assume it's possible) by simply walking through the Karatsuba algorithm and watching the patterns emerge.

UPDATE: In writing out my understanding of the wikipedia explanation line by line to identify where I got stuck, I finally saw the pattern.  However, maybe putting it here will help someone else.

"Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up."

I understood this to mean that for integers with n digits, m is the ceiling of half n (m being the exponent applied to the Base in the algorithm).  This can be seen if you simply look at the definition of the algorithm.

"In particular, if n is $2^k$, for some integer k, and the recursion stops only when n is 1, then the number of single-digit multiplications is $3^k$, which is nc where c = ${\log3}$"

I took this to mean, given n is some power of 2 (2, 4, 8, ...), the number of single digit multiplications performed is 3 * (exponent of 2).  I worked out how this conclusion was reached by writing out the tree and finding that each sub-problem involves 3 multiplications, and at the base of the recursive tree, you should have $3^{m - 1}$ sub-problems for that bottom level.  However, the -1 can be ignored as, using the properties of exponents, you can factor that out into a constant, which Big-O doesn't consider.  Therefore, if we are looking for the exponent of 2, we can get that exponent of 3 as a log relative to n, thus $3^{\log n}$, which by a law of logarithms turns into $n^{\log 3}$.  Since the computational complexity of each sub-problem by itself is a constant 7 (4 additions and 3 multiplications) independent of the number of digits in the number representation, the computation itself can be ignored in the efficiency analysis, giving us $O(n^{log 3})$


Binary tree traversals reversed Am I correct in saying that

traverse(node):
    if node is null, return
    print node
    traverse(node's right subtree)
    traverse(node's left subtree)

would produce output that is the reverse of post-order traversal?

post-order(node):
    if node is null, return
    post-order(node's left subtree)
    post-order(node's right subtree)
    print node

I am mostly interested because if this is true, it greatly simplifies the iterative method for post-order traversal. It "feels" right with a hand-wavey explanation - and with testing on some trees - but how would I prove it?

I would say you are right. If the post order of a tree is "left-recursion, right-recursion, root" then the reverse is "root, reverse-right-recursion, reverse-left-recursion", which is exactly what you propose. Technically the proof would state "by induction on the structure of the tree".


reducing $CLIQUE$ from decision to search problem consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\}$$

  Suppose there's a polynomial time algorithm for $CLIQUE$. I need to show a polynomial time algorithm for finding a clique of size $k$.

Now, the idea is pretty easy if there's only one clique in the graph - You remove each vertex $v_i$ and query for $CLIQUE(G_i, k)$.

If there are two cliques in the graph this algorithm could not be applied since no matter which vertex will be removed there will always be a clique of size $k$.

An alternative would be removing each one of the ${m}\choose{k}$ but if $k = n/2$ for example, that wouldn't be a polynomial time algorithm anymore.

So my question is, can we solve this problem for the general case where there might be multiple cliques?

Keep removing vertices until the graph no longer contains a clique of size $k$, and let $v$ be the last vertex that you removed. It follows that there is some $k$-clique which contains $k$. Remove all vertices from the graph other than neighbors of $v$ (so $v$ itself is also removed), and recursively find a $(k-1)$-clique in the new graph. Add $v$ to this clique to create the desired $k$-clique.

The algorithm can also be formulated iteratively:

Let $C = \emptyset$ (this will be the clique).
Let $\ell = k$ (the current size of the clique).
Go over all vertices $v$ in the graph:

Check if after removing $v$ from the graph, the new graph still contains an $\ell$-clique.
If so, continue to the next vertex.
Otherwise, add $v$ to $C$, decrease $\ell$, and remove from the graph all vertices other than the neighbors of $v$.

Return $C$.


Do expressions have much to do with referential transparency? In other words, can a programming language be referentially transparent even if not everything is an expression?

And can you say that if in a programming language, everything is an expression, then it is referentially transparent?

I think the question is a bit poorly stated because it uses the term "expression" in an unclear way. So for the purposes of this answer let us say that an expression is a term which does not trigger any computational effects (such as divergence, I/O, mutation of state, exceptions, etc.). In Algol-like languages the opposite of expression is a command. I will say term for any piece of syntax.

I shall take referential transparency to mean that we may replace a term with its value without changing the program. More precisely, we obtain an observationally equivalent program when we replace the term with its value. Note however that referential transparency is not sensitive to efficiency, as replacing a term with its value almost always results in a more efficient program.

For example:

print "Hello, world!" is not referentially transparent because it returns the unit value (void is a horrible, horrible misnomer because it suggests that no value is returned, when in fact the trivial value is returned; in contrast, raising an exception return no value) -- if we substitute the unit value, the program won't print anything anymore
x = x + 3 is not referentially transparent because it changes state (the value of x)
3 + 4 is referentially transparent because we may substitute it with 7 safely
while true do skip done is an infinite loop, which is not referentially transparent. If we replace it just with skip (the unit value) then the program might do things it otherwise would not, such as launch missiles.

I hope you see now why your question is unclear. If you define "expression" as "free from all effects" then almost by definition it will be referentially transparent. If you define "expression" syntactically as "such and such syntactic forms are expressions", then we would have to check whether the syntax allows us to construct terms which are not referentially transparent.

One more point: it does not make sense to say that a programming language is referentially transparent, but rather that a particular term or a program is referentially transparent. So we should interpret the question from the first sentence as "if a programming language contains terms that trigger computational effects, must it have some non-transparent terms?", and I think then "yes" is the obvious answer because we just consider a command which triggers a computational effect.

You then ask about languages in which "everything is an expression". Well, that would be a pure language whose only possible effect is non-termination (because of infinite recursive calls). Depending on the language evaluation strategy this may or may not cause expressions to be referentially non-transparent. For example, in Haskell sometimes it does not matter that an expression is non-terminating because Haskell won't evaluate it until it is needed, which may be never. But in general non-termination is the thing to worry about in a pure language.

There are languages in which all terms are referentially transparent by design. Such languages cannot be Turing complete, however (assuming they have sane syntax). An example is Agda, which does not allow you to write a non-terminating expression, but it is still very powerful as a programming language, and a proof assistant.

A far more interesting question is whether a term can be referentially transparent even though it triggers computational effects. The answer is positive, and useful. Many data structures are self-modifying but they look referentially transparent from the outside, let me just mention splay trees as a famous example. Another example are caching strategies where lookups are cached (state change) so that they may be answered faster in the future. It is an interesting challenge for programming languages to properly account for such phenomena so that compilers can see what is going on and take advantage of the situation. For example, in a splay tree we may reorder lookups and updates, or if we work with two splay trees it does not matter which tree we work with first (so long as the data is not migrating between them). Note however.

I hope that answers your questions a bit by putting them into wider context.


Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve
\begin{align*} & {\rm minimize}~ \sum_{i=1}^n x_i/y_i \\
&\mbox{ subject to } Ax + B y \leq c \\
& x>0, y>0,
\end{align*} where $A$ and $B$ are given matrices and $c$ is a given vector.

This feels like it should be NP-hard due to the non-convexity of the objective, but I have no idea how to show this, or even whether I'm missing some kind of clever trick that makes it convex. If the matrices $A$ and $B$ were positive, you could plug in $x_i=e^{u_i}, y_i = e^{v_i}$ and the problem would become a convex problem that you could solve via geometric programming, but positivity is not an assumption. I'm not even sure what would be a natural combinatorial problem to try to write in this format, so any suggestions would be very welcome.

Your objective function is indeed not convex, but you can make it convex with the appropriate transformation, which means it is solvable in polynomial time. But applying this reformulation is complex: you should try a non-convex solver first and stop there if it works in practice.

The easy way: Non-convex quadratic model

As pointed in the comments, it is a quadratic program, so you can solve it with a non-convex quadratic solver. Although not a polynomial-time algorithm theoretically, these solvers are really efficient in practice.

\begin{align*} {\rm minimize}&~ \sum_{i=1}^n r_i \\
\mbox{ subject to } & \\
& Ax + B y \leq c \\
& r_iy_i \geq x_i \\
& x>0, y>0
\end{align*}

The hard way: Convex fractional programming reformulation

Stated as follows, it is clear that it is a fractional programming problem:
\begin{align*} {\rm minimize}&~ \frac{\sum_{i=1}^n x_i \prod_{j\neq i} y_j}{\prod_{j=1}^n y_j} \\
\mbox{ subject to }& \\
& Ax + B y \leq c \\
& r_i \geq x_iy_i \\
& x>0, y>0
\end{align*}

Both the numerator and denominator are convex, so you can follow the transformation given in the above link to make it convex. This makes it solvable in polynomial time.

$$
\begin{align*}
z_i &= \frac{x_i}{\prod_{j=1}^n y_j} \\
w_i &= \frac{y_i}{\prod_{j=1}^n y_j} \\
t &= \frac{1}{\prod_{j=1}^n y_j} \\
\end{align*}
$$

And solve (yes, the convexity is far from obvious):

$$
\begin{align*} {\rm minimize}& ~ \frac{1}{t^{n-1}} \sum_{i=1}^n z_i \prod_{j\neq i} w_j \\
\mbox{ subject to } & \\
& \frac{\prod_{j\neq i} w_j}{t^{n-1}} \leq 1 \\
& Ax + By \leq ct \\
& z>0, w>0, t \geq 0
\end{align*}
$$


Does a bitonic sorter compare a pair of elements more than once? I've got two questions about bitonic sorting:

Does a bitonic sorter compare a pair of elements more than once?
How many comparisons does a bitonic sorter perform in the case where the size of the array not a power of two.

1) yes, the exact same comparison is made, interleaved with other operations. The butterfly network creates tones and checks local and far pairs, after far pairs it still has to apply local ones.

2) The original bitonic sort by Batcher requires the sequence that is a power of two. It makes tones in bitonic sort phase and then bitonic merge phase. The given algorithm introduced dummy nodes (infinite value or maximum that can be stored) for inputs $2^k - c$ and after sorting strips them from result. So the original network uses the number of comparisons equal to the net sorting the next power of two input size. The modifications that use less comparisons are not successful because of environment they run in. While it is possible to avoid not needed comparisons, it introduces branching at higher level (or special blocks, since it is no longer symmetric), to choose what comparator should be used and (in my opinion) is not any more bitonic sort.

You might be interested in more general sorting networks, where the exact number of compares is the subject of creating the sorting net for given $n$. The structure and algorithm depends on number of comparators available. The net is created for exactly given size, and it is not required to be power of two or be even. The optimal networks are found for $n \le 10$.

I recommend Optimal sorting networks by Daniel Bundala and Jakub Závodný about pursuit of better networks (these are general, not bitonic) with algorithmic approach.