How does one know which notation of time complexity analysis to use? In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.

However, there are other notations, such as $o$, $\Omega$ and $\omega$. Are there any specific scenarios where one notation would be preferable to another?

You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement.

$f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the stricter form, i.e. $<$.

$f \in \Omega(g)$ has the symmetric meaning: $f$ grows at least as fast as $g$. $\omega$ is its stricter cousin. You can see that $f \in \Omega(g)$ is equivalent to $g \in \cal{O}(f)$.

$f \in \Theta(g)$ means that $f$ grows about as fast as $g$; formally $f \in \cal{O}(g) \cap \Omega(g)$. $f \sim g$ (asymptotic equality) is its stronger form. We often mean $\Theta$ when we use $\cal{O}$.

Note how $\cal{O}(g)$ and its siblings are function classes. It is important to be very aware of this and their precise definitions -- which can differ depending on who is talking -- when doing "arithmetics" with them.

When proving things, take care to work with your precise definition. There are many definitions for Landau symbols around (all with the same basic intuition), some of which are equivalent on some sets on functions but not on others.

Suggested reading:

What are the rules for equals signs with big-O and little-o?
Sorting functions by asymptotic growth
How do O and Ω relate to worst and best case?
Nested Big O-notation
Definition of $\Theta$ for negative functions
What is the meaning of $O(m+n)$?
Is O(mn) considered "linear" or "quadratic" growth?
Sums of Landau terms revisited
What does big O mean as a term of an approximation ratio?
Any other question about asymptotics and landau-notation as exercise.

If you are interested in using Landau notation in a rigorous and sound manner, you may be interested in recent work by Rutanen et al. [1]. They formulate necessary and sufficient criteria for asymptotic notation as we use them in algorithmics, show that the common definition fails to meet them and provide a (the, in fact) workable definition.

A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)


How to give a context free grammar for any given language ie: a^n (ba)^m a^n i am trying to understand Context free grammar and generate a CFG for any given language.

when you're given a language , what is the best way to generate a CFG from it? are there any steps to follow to help you create a CFG for any language? is there ways of breaking down the language to make it simpler so that it helps you generate the CFG.

for example if i was given  L={a^n (ba)^m a^n | n,m >=0 }

does that mean i need to have equal number of a's on both side, and have zero or more ba in between  the a's ?

S---> aSa |ε

X---> baX |ε

any helps is appreciated.

The reference question "How to prove that a language is context-free?" has some examples to build a context-free grammar using a simple toolbox. As is mentioned there one needs a "nesting structure" to make this work.

You ask about the difference between language like $L_1 = \{ab^na^nc \mid \dots \}$ and $L_2 = \{a^n (ab)^m a^n \mid \dots \}$. In both cases the parts that are iterated the same $n$ number of times have to be generated in parallel. Productions like $Y\to b Y a$ are good for that.

In case of $L_1$ the $a\dots c$ pair is around the repeat $b^nc^n$ and can be generated before $S\to a X c$, but also independently as $S\to AXC, A\to a, C\to c$  .
In case of $L_2$ the $(ab)^m$ is inside the repeat $a^n\dots a^n$ and has to be generated after, like your own solution $S\to aSa, S\to X, X\to abX\mid \varepsilon$.


Are chatbots a good example of overfitting? In my highschool class we are learning about Artificial Intelligence, and especially the problems that come with machine learning. I was wondering if chatbots like cleverbot were good examples of overfitting. Obviously, when you get a reply that doesn't make sense, is that a result of the bot modeling a training dataset too closely, or is it something else completely?
Thanks for the help

There is no expectation that an Machine Learning (ML) system will perform perfectly. Not just in the practical sense that we obviously haven't yet figured out how to make a human-level chatbot, but in a more formal sense that ML systems, particularly neural nets, but this is true for many other ML algorithms, approximate functions and this approximation is going to have some error.

So the fact that an ML system sometimes produces "incorrect" responses doesn't indicate anything. Overfitting is when the ML system performs extremely well on the training set and catastrophically poorly for even relatively small departures from the training set. To show this requires showing poor performance on many examples which are near the training set. Overfitting is unlikely when the training set is large compared to the number of parameters of the ML system (e.g. the weights of a neural network).

You can get nonsensical answers just as well from underfitting or false generalizations. The ML system can easily "learn" a "rule" that makes sense in some situations but not all but be either unable to model (underfitting) or unaware of (false generalization) the exceptions.

At the extremes, you're just off distribution, meaning the input you're giving the system is very unlike the input it was trained on. Obviously at this point there's no reason to expect it to perform well in any sense. An extreme example is training a chatbot on an English language corpus and then talking to it in Spanish.


Proving inequalities related to Dijkstra's algorithm Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$.

Define $IN(v)$ as the set of in-neighbors of $v$.

Define $w(u,v)$ as the weight of the edge $(u,v)$.

I am asked to prove the following two inequalities to gain the correctness of Dijkstra's algorithm:

$$spdist(s,v)\leq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$$

and

$$spdist(s,v)\geq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$$

For the ≤ direction, it is quite obvious. Since we must go through either one of the edge $(u,v)$ to reach $v$, $spdist(s,v)$ is by definition smaller or equal to the RHS.

However, I am having trouble proving the ≥ direction. May I have some intuition of tips on how to prove the ≥ direction?

Thanks!

Consider a shortest path from $s$ to $v$. Let $u \in \mathrm{IN}(v)$ be the vertex preceding $u$ in this shortest path. The path from $s$ to $u$ is also a shortest path, and so $\mathit{spdist}(s,v) = \mathit{spdist}(s,u) + w(u,v)$.


Data compression with Turing Machine For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best compression level? One can think about splitting data as small chunks and for each small chunk iterate all possible (de)compression codes to get best compression. Is there any research or existing algorithms, utilizing ideas like that?

Suppose the first byte of the compressed file indicates which decompression algorithm to use, and then you use that algorithm to decompress the rest.  Sure, you could do that.  Absolutely.  Some compression formats already do exactly this.

That said, it's also possible to view this as a single decompression algorithm.  The master algorithm looks at the first byte of the file and then branches to a subroutine that handles the rest of the file.  That can be considered a single algorithm.  So at a fundamental level there is no fundamental distinction that can be drawn.


Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*? If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪
  (rs)*.

I think this is not true. And I believe this would always be true :

  (r ∪ s)* = r* ∪ s*

I wanted to clarify this because of (rs)*. What do you think the right hand side would be if r* ∪ s* ∪ (rs)* ?

Consider the alphabet $\Sigma = \{a,b\}$, and the regular expressions $r = a$ and $s = b$. Then $(r+s)^* = \Sigma^*$ whereas $a^*+b^*$ and $a^*+b^*+(ab)^*$ are both smaller.


Is Reed Solomon also a Fountain code? Once you encode your message as a polynomial you can effectively generate and stream an endless number of points on that polynomial of which only a finite subset would be required to recover the polynomial.

Why isn't Reed Solomon also a Fountain code? I have never seen it listed as such and I looked.

It's difficult to call Reed-Solomon a fountain code. This is due to two reasons.

The first reason is rather technical.
Let's assume you use a systematic code. After sending the message itself (the systematic part), the "fountain" is the remaining redundancy symbols = evaluation of the polynomial in other points. In order to be decoded correctly, you must attach to each symbol the index it belongs to, i.e., the point it is evaluated in. You cannot permute the symbols order and still decode correctly, hence the index is crucial.
So RS by itself doesn't fit the decoding properties of fountain codes, where any order of received symbols is OK. However, this is merely a technicality since you can always send the symbol along with its index (this is also done in fountain codes).

The second reason is more meaningful and inherent.
In a (systematic) $[n,k]$ block codes (e.g., Reed-Solomon), there are exactly $n-k$ redundancy symbols. That's it. You don't have a "fountain" of "infinite" number of redundancy symbols you can send. You only have $n-k$, and once the decoder receives enough of them it will be able to decode. Using RS notations, you can evaluate the polynomial only in points in the finite field $\mathbb{F}$, and there is a finite (and relatively small) amount of them.

So the "fountain" in block-codes reduces to only be re-sending the $n-k$ redundancy symbols again and again, and requiring the decoder to collect (almost) all of them. This is not as good as the properties fountain codes are providing.


Recursively enumerable but non recursive subset of an infinte recursive language How can we show that, for every infinite recursive language, it has a subset that is recursively enumerable but not recursive?

I think we need to show there's a list of natural numbers that can't be ordered but I don't know how to build such a subset.

Is there another way of arguing or another type of argument in order to prove such subset exists?

Hint. Let $S$ be any infinite recursive language. By considering, e.g., the lexicographic order, we can talk of the first, second, third, etc. strings in $S$. Use this indexing to define what you need to define.


Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA? Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation closure is most often presented by demonstrating the NFA. I'm just curious whether this is out there somewhere

There is a simple proof using automata. Suppose the original language is $L$, and we are substituting $R_a$ for $a$ (for each $a \in \Sigma$). Starting with an automaton for $L$, replace each edge $(x,y)$ annotated $a$ with a copy of an automaton $A_a$ for $R_a$, connecting $x$ to the starting state of $A_a$ with an $\epsilon$-edge, and connecting each accepting state of $A_a$ (which is not accepting any more in the new automaton) to $y$ with an $\epsilon$-edge.


Schedule two trains whose tracks overlap so they don't crash I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve.

Recently I was asked this question and did not even know what algorithmic technique to use to answer it!

There are two trains, which run between stations and share a portion of track. For instance train 1 runs between stations A B C D E F G H and train 2 runs between stations I J K B C D E F L M so the trains share the track between B C D. At each end of the track the train turns around and goes the other way on its track. The trains go from station to station in 1 unit time. I need to prevent the trains from crashing head on on the shared track, I have the power to stop either train at any station and restart it again when I please.

How can I solve this problem without using a ton of if else clauses, what CS principles should I be using here?

edit

Some background, the first solution I wrote was just a simple check to see if the other train was on the shared track before sending the other train out. That seemed ad hoc to me and I'm sure it did to the company I interviewed for as well.

I figure there must be an algorithm or at least a school of thought for this type of problem, after all how do they build extensible systems for managing shared runway space at an airport, or managing traffic flow at stop lights.

My intuition is that this is a very introductory problem to a school of thought in computational problem solving I have not yet encountered.

I might be wrong, but could anybody clear the air for me?

A related and well studied area is threading/multiprocessing. Your initial solution is a simple lock; the critical section of tracks can only be used by one train at a time. To extend this while avoiding deadlocks (two trains waiting in each other) or starvation (a train waits forever), you would want to use some more sophisticated locking mechanism and scheduler.


I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example):
Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between 1 to 100.
Given the outputs X, Y, Z, which are determined by a combination of the inputs eg:

A=2, B=3,C=4, returns X=76, Y=87, Z=34
A=5,B=1,C=100 returns X=52, Y=45, Z=24 etc.

The problem is, I have no clue how the inputs affect the outputs and so id like to find an algorithm of some sort that can try out various combinations of inputs in a logical manner (not randomly) to find the optimal output or get as close as possible to said optimum output, which in my case is finding the highest possible valued combination of X,Y,Z so best case scenario is finding a set of inputs that return 100, 100, 100 as the XYZ values.
If anyone has any idea how I could approach this or if a question like this has already been answered, I appreciate any and all help.
Thank you!

This would fall under something called black box optimization. In general, there are several methods you could try in practice such as (stochastic) hill climbing or say a genetic algorithm. Such methods might seem "random", but they take some care in moving in a smart way but also use some "randomness" to escape local optimums.


Need help understanding how to find big theta of a snippet of code Say I have a snippet of code:

k = 5
i, j = 0

for i -> n
    if i == k
        for j -> k
            /* do something */
        end for
    k = k * 4/3
    end if
    /* do something */
end for

I can tell that the algorithm is worse than n but can't be worse than n^2. In fact it seems like it would be less than n log (n). Though I admit these are just guesses I'm making. Is there any methodology to figuring out what the big theta is for such algorithms?

In order to estimate the running time of the code it is enough to count the number of times the two "do-somethings" are executed. Call them do-something 1 and do-something 2 (in their order of appearance). Do-something 2 is executed about $n$ times. As for do-something 1:

If $n < 5$, no times.
If $5 \leq n < (4/3)5$, $5$ times.
If $(4/3)5 \leq n < (4/3)^25$, $(4/3)5$ times.
Generally, if $(4/3)^k5 \leq n < (4/3)^{k+1}5$, $(4/3)^k5$ times.

Be creative and estimate the number of times that do-something 1 is executed in terms of $n$. Conclude the running time of the code snippet.


Add on interval, Query for number of elements less than val We have an array of numbers and we are supposed to do the following queries on it:

Add number x to all elements on the subarray with indices [ L, R ] of the array.
Query for number of elements less than number x of the whole array.

Note that x is given in each query and is not fixed.

I have a solution with time complexity $O(q \cdot log(n) \cdot \sqrt n)$ where $n$ is the size of the array and $q$ is the number of the queries (Storing sorted subarray in each block). However for constraints $n, q < 1e5$ with time limit of 2 seconds this is not efficient enough. So how to solve it on these constraints?

The only constraint is that the solution should work for 2 seconds when $n, q < 1e5$ and you can answer queries offline. Total complexity should fit in the constraints and the complexity for each query is not important.

Decompose the array to blocks of size $T = \sqrt{n \cdot log(n)}$ and Store the sorted corresponding subarray in each block. For each block $k$ store variable $bound[k]$ which is the number added to the whole subarray of the block. For the second query iterate over blocks and use binary search over $x - bound[k]$ on $k$th block. Time complexity would be $O(\frac n T log(T)) = O(\frac{n \cdot log(n)}{\sqrt{n \cdot log(n)}}) = O(\sqrt{n \cdot log(n)})$.

For updating queries, for each block $k$ that it's subarray is completely in the interval [ L, R ] update $bound[k]$ to $bound[k] + x$. Now we have at most two blocks which are modified but their subarray are not completely in the query interval. Iterate over the modified elements and update them by $x$. Now in each of those blocks you have two sorted arrays (modified and unmodified elements) and you are trying to merge them into one. This can be done in linear time, so rebuilding those two blocks takes $O(T)$. This way time complexity of each update query would be $O(\frac n T + T) = O(\sqrt{n \cdot log(n)})$.

Total complexity: $O((n + q)\sqrt{n\cdot log(n)})$.


Why researchers don't study the parameterizations of the problems unlikely to be NP-Hard? I have seen the parameterization of the very well known problems like vertex cover, hitting set etc which are NP-hard (NP-complete precisely). Many researchers in the past have been studied the parameterization of these problems. My question is why researcher's don't study the  parameterizations of the problems unlikely to be NP-Hard?

This is not true, there is a program known as "FPT inside P" where we look for interesting parameterizations for problems inside P. The results are perhaps indeed more scattered as opposed to FPT for hard problems which you tend to see much more.

For example, look at the work of Niedermeier and others [1,2] for graph matchings. There is also work for longest path on interval graphs [3]. You will find more by looking at papers that reference the ones mentioned.

[1] Korenwein, Viatcheslav, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. "Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments." In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[2] Mertzios, George B., André Nichterlein, and Rolf Niedermeier. "The power of linear-time data reduction for matching." Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017.

[3] Giannopoulou, Archontia C., George B. Mertzios, and Rolf Niedermeier. "Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs." Theoretical Computer Science 689 (2017): 67-95.


Is there a zero-knowledge protocol for bit vector agreement? Suppose Alice knows a secret vector of $N$ bits, say $A=\langle a_1, a_2, \ldots, a_N\rangle$ and Bob similarly knows $B=\langle b_1, b_2, \ldots, b_N\rangle$.  Is there a protocol that allows them to determine the number of bits that their vectors have in common, without revealing any additional information about what the vectors are or what positions agree?

That is, we would like Alice and Bob to be able to determine the size of the set $$X(A,B) = \{i\mid a_i=b_i\}$$ without learning anything else about $A$ and $B$, and without revealing any information to an eavesdropper.

Obviously if $X(A,B) = N$ or $X(A,B)=0$, then Alice now knows Bob's vector and vice versa, and in other cases each gets some incomplete information about the other vector, but that is unavoidable.  Perhaps that means that a true zero-knowledge protocol is by definition impossible.  But  I would like the information leakage to be no greater than this necessary amount.

I think you actually want secure multi-party computation, not zero-knowledge proofs.  In secure multi-party computation, Alice has a secret input $a$, Bob has a secret input $b$, and we want to compute $f(a,b)$ so that both Alice and Bob learn $f(a,b)$ but neither one learns anything more about the other's secret.  That maps directly to your situation.  In your situation, $f$ is the Hamming distance function that counts the number of positions where Alice and Bob's bitvectors agree.

It's a standard theorem that for every poly-time computable $f$, there is a poly-time protocol to compute $f(a,b)$ in a secure multi-party computation sense.  There are also toolkits to automatically derive such protocols, given a circuit/description of $f$.  For instance, you could look at VIFF or UVA's toolkit.

You'll want to be aware of the differences in threat model between the honest-but-curious threat model (aka semi-honest threat model) vs malicious threat model.  The honest-but-curious threat model is a bit of an academic curiousity; for most real applications, I suspect the malicious threat model will be more appropriate, but the protocols do tend to be more expensive.

The following paper might be of interest as well, not for your particular problem, but as an interesting tool for computing monotonic functions, where the inputs are sets:

Lea Kissner and Dawn Song.  Privacy-Preserving Set Operations, CMU-CS-05-113.

(I previously thought your problem could be reduced to Cardinality Set Intersection, from Section 5.2 of the following paper, by making Alice's set is $S_1 = \{i : a_i=1\}$, Bob's set is $S_2 = \{i : b_i=1\}$, and computing $|S_1 \cap S_2|$ -- but as you accurately point out, that doesn't work, because you actually want to compute $|S_1 \Delta S_2|$.)

There are a bunch of cryptographers who hang out on Cryptography.SE and who are knowledgeable about this area.


Path finding under constraints Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the minimal weight of all paths from $b$ to $a$. How do you find two paths $l_1,l_2$  such that:

$l_1=(a,v_1,..,v_n,b)$
$l_2=(b,u_1,..,u_m,a)$
$w(l_1) + w(l_2)\leq 1.1(\alpha + \beta)$
From all the paths holding the above, bring to minimum the sum of weights on the edges $e=(u,v)\in l_1$ such that $(v,u)\in l_2$

Less formally, I want to find a path starting at $a$ ending with $b$ and returning to $a$ such that the path is not too long (at most 10% longer than the optimal solution) and tries to use as much as different roads as possible (if it used some road $(x,y)$ when going from $a$ to $b$ , it would try to avoid the road $(y,x)$ when going back to $a$)

One solution would be to use integer linear programming (ILP).  This is not guaranteed to have a polynomial worst-case running time (ILP can take exponential time), but ILP solvers are pretty impressive, and for reasonable-sized graphs, this might just be an effective solution in practice.

For each edge $e \in E$, let $x_e,y_e,z_e$ be integer variables with the constraint $0 \le x_e \le 1$, $0 \le y_e \le 1$, $0 \le z_e \le 1$ (so that $x_e,y_ez_e$ are forced to be either 0 or 1).  The meaning of $x_e=1$ is that $e$ is part of the path $l_1$, and the meaning of $y_e=1$ is that $e$ is part of $l_2$, and the meaning of $z_e$ is that $e$ is part of both $l_1$ and $l_2$.

Now introduce the following constraints:

$\sum_{(a,v) \in E} x_{(a,v)} = 1$ (i.e., at least one of the edges out of $a$ must be selected in $l_1$).
$\sum_{(v,b) \in E} x_{(v,b)} = 1$ (i.e., $l_1$ contains an edge into $b$).
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} x_{(u,v)} = \sum_{(v,w) \in E} x_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
$\sum_{(b,v) \in E} y_{(b,v)} = 1$ (i.e., $l_2$ contains an edge out of $b$).
$\sum_{(v,a) \in E} y_{(v,a)} = 1$ (i.e., $l_1$ contains an edge into $a$).
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} y_{(u,v)} = \sum_{(v,w) \in E} y_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
$\sum_{e \in E} w(e) (x_e + y_e) \le 1.1 (\alpha+\beta)$ (condition 3 in the question holds).
For each $e \in E$, $z_e \ge x_e + y_{-e} - 1$, $z_e \le x_e$, and $z_e \le y_{-e}$, where $-e$ is the reversal of the edge $e$ (i.e., if $e=(u,v)$, then $-e=(v,u)$).  (This enforces that $z_e = 1$ if and only if $x_e = y_{-e} = 1$.)

Now minimize $\sum_{e \in E} w(e) z_e$.  This will minimize the total weight of the edges that are common to both $l_1$ and $l_2$.


Defining $a^n b^{n^2}$ with one existential SO binary relation Is it possible to define the language:

$$L = \{ a^n \; b^{n^2} \}$$

  using an existential second order sentence over strings (ordered structures with unary predicates $U_a(x), U_b(x)$) using only one binary relation?

The sentence should have this form: $\exists M ( \exists B_1,...,B_n ( \varphi ))$ where:

$M$ is a binary relation
$B_i$ are monadic
$\varphi$ is first order with signature (available relations) $\sigma = \langle <, U_a, U_b \rangle$

If not, how to prove it? (or cite a textbook in which I can find similar exercises)

First off, I assume you also want to have a binary relation on the domain, acting as a linear order: <. Furthermore, I assume you want to deal with existential second-order logic, which in general allows more than one existential quantifiert.

Then, you can employ Fagin's theorem: wikipedia
And what remains to show is that you can recognize the language $a^{n}b^{n^{2}}$ in polynomial time. Can you do that?

Edit:
Now, since it is clarified that you indeed want to just have an existential binary relation, consider the following:

Büchi-Elgot-Trakthenbrot tells us that regular languages (which yours is not, but that needs a prove) are exactly those that can be described by MSO. The prove gives already big insights in how many different variables you need.
Those languages definable in MSO are exactly those that are definable in existential MSO (see for this Finite Model Theory by Ebbinghaus and Flum, thm 6.2.3)
Those languages definable in existential SO are those recognizable in NP, that's Fagin's theorem.

So you have that e-MSO matchs the regular languages. If you can prove that the different existential quantifiers in BET are necessary for recognizing a language and a binary relationvariable cannot encode the unaries, you are done.

A different approach (possibly more fruitful) is to argue the following way:
The constraint $a^2 = b$ is a meta constraint. You have to emulate this inside your language to get it in the object-world. Now im general SO over the empty signature is strong enough for such, but this is a different exercise. So you have to show two things:
Is your framework strong enough to emulate $x \mapsto x^2$ relative to the discrete order? Pay attention, Beth's Definability Theorem does fail in general in the finite, as does Craig's Interpolant Theorem (both for FO). This is also in above's book, 3.5.1.
If you succeed in doing so, you still have to following problem: You need to get the "meta-size" of $U_a$ and $U_b$ into the object language. This is possible if you allow existential quantifiers of the form "exists exactly n many x:", which is possible in FO. However, you can only do this for a fixed number, additionally, you cannot get the "object-size" into the meta language. You could employ counting to test for sizes. In the MSO setting, they are of the form "$C_n(X)$ which is satisfied iff $ X mod n = 0$. These are not possible to emulate with just a binary relationvariable and FO. Can you show that even using those, you cannot get enough?

Another edit: Lets consider the solution with two binary relations, $R$ and $S$. I'll furthermore use $\bot$ as the smallest element of the order, $\top$ as the largest.

$\forall x, y: (x,y) \in R \implies U_a(x) \wedge U_b(y)$
$\forall x: ((x,\top) \in R \iff x = \bot) \wedge ((\bot,x) \in R \iff x = \top)$
$\forall x: \exists y: (x,y) \in R$
$\forall y: \exists! x: (x,y) \in R$
$\forall x_1, x_2, y_1, y_2: x_1 < x_2 \wedge U_a(x_1) \wedge U_a(x_2) \wedge (x_1, y_1) \in R \wedge (x_2, y_2) \in R \implies y_2 < y_1$

Well, $R$ does split $U_b$ into $|U_a|$ many equivalence classes, each of which is not empty and the smaller the values in $U_a$, the large the corresponding values in the factorized $U_b$. A model of this sentence can look like this (numbers being the elements in $U_a$ and letters being the elements in $U_b$ factorized by the equivalence relation induced by $R$.

  w = 1-2-3-cc-bbbbbbb-a

What is left now is to make sure that the equivalence classes have the appropriate size. For this, note that we can indeed encode $x \mapsto x^2$ inside a binary relation (somewhat). See here that if $n = 1$, we have to append 1 element to the end and if $n = m + 1$, then for this one element more in $U_a$, we have to add as many elements to $U_b$ as we did for m, and two additional ones ($(n+1)^2 - n^2 - (n^2 - (n-1)^2) = 2$, aka when considering adding +1 repeatedly to $n$, one has to add 1, 3, 5, ... to $n^2$).

So, let's encode this behaviour with $S$:

$\forall y_1, y_2: (y_1, y_2) \in S \implies U_b(y_1) \wedge U_b(y_2)$
$\forall y: \neg (y, \top) \in S$ (probably redundant)
$\forall y_1: (\exists y_2: (y_1, y_2) \in S) \implies (\exists! y_2: (y_1, y_2) \in S)$
$\forall y_1: (\exists y_2: (y_2, y_1) \in S) \implies (\exists! y_2: (y_2, y_1) \in S)$
$\forall y_1, y_2: (y_1, y_2) \in S \implies (\exists x_1, x_2: (x_1, y_1) \in R \wedge (x_2, y_2) \in R \wedge \neg \exists x_3: (x_1 < x_3 \wedge x_3 < x_2) \wedge x_1 < x_2)$
$\forall y_1: (\exists x_1, x_2: x_1 < x_2 \wedge (x_1, y_1) \in R) \implies \exists y_2: (y_1, y_2) \in S$

This asserts that $S$ acts only on $U_b$, that if it is defined, it'll be uniquely defined (an injective partial function so to say, I'll use it from now on as a function), nothing is mapped to the largest element and whenever "$y_2 = S(y_1)$", than $y_2$ is in the equivalence class induced by the direct successor of the inducer of the equivalence class of $y_1$. Furthermore, $S$ is defined for each element that is not member of the "least" equivalence class.

With the help of this auxiliary function, we can control the size of the equivalence classes produced by $R$:

$\forall x: \bot < x \wedge U_a(x) \implies (\exists x': x' < x \wedge (\neg \exists x'': x' < x'' \wedge x'' < x') \wedge (\forall y: (x', y) \in R \implies (x, S(y)) \in R \wedge \exists^2 z: U_b(z) \wedge (x, z) \in R \wedge \neg \exists q: S(q) = z \wedge \forall w: (x, w) \in R \implies (w = z \vee \exists y: (x', y) \in R \wedge w = S(y)))$

This formula expresses that for each element in $x \in U_a$, which is not the smallest one, there is a next smaller one $x'$. The elements which are paired with $x'$ in $R$ translated with $S$ are paired with $x$ in R, there are two additional elements which are not the image of any of those. Lastly, there are no elements paired with $x$) besides these two additionals and those that came from $x'$.

The following is now up to you:

Prove that all models of this sentence are words of the form $a^nb^{n^2}$
Prove that every word of the form $a^nb^{n^2}$ does satisfy this sentence
Show that you can indeed encode the two relations into one


Automatically generate meaningful queries for a data table My field of research is not Database or AI. But I have some problems to solve, and would like to know which branch this kind of problems belong to, and what are the results.

The main question is: given a table of data, there are lots of possible queries that can be made. But some queries are meaningful, some are meaningless. Are there some algorithms to automatically generate a ranked set of meaningful queries, from the relationships inside the table?

Here is an example:

ArticleID   Price   Quantity    Sale
A01         10      3           30
A01         10      3           30
A02         20      4           80
A02         20      5           100
A03         15      3           45
A03         15      4           60
A03         15      5           75
A04         20      2           40
A04         20      3           60
A04         20      4           80

There are two relationships in this table, which may be given or inferred (the detection of the relationships is not an issue here): a) one ArticleID maps one Price; b) Sale = Price * Quantity.

Then, the first issue is, how to automatically generate some queries? For instance:

1) Sum of Quantity by ArticleID
2) Sum of Sale by ArticleID
3) Sum of Price by ArticleID

The second issue is, how to rank the meaningful queries? For example,
intuitively, we can say that Query 1 and Query 2 make more sense than Query 3. And this conclusion can be more or less inferred from the two given relationships.

Certainly, the problem becomes more complexe when there are relationships among several tables. The tables and the relationships that I study are not very complicated.

Could anyone tell me which field this problem belongs to? Are there some good results/proposals that are easy to understand?

I have no idea whether this has been addressed before. I have never
seen it (but I am not in databases), and I would be surprised  if no
one had adressed it. Since there are no answers yet, I will attempt to
give a view that may hopefully help. It is very elementary, and it
would really require more study of how this kind of view may combine with
the various types of queries one can make. What I write below was strongly
influenced by your example and the queries that go with it. But there
is more to a relational database.

As remarked by Raphael, generating queries is relatively easy. But
that is not your problem. What you want is meaningful queries. It is
a semantic issue that depends much on the semantics you attach to your
columns.

I suspect that you may have a typing problem, which I tend to
see also as a dimensional problem in the physics sense. It may not be
easy or even meaningful to attempt to deal with it in a purely
automated way. I am not thinking of elementary types as found in most
programming languages, but of abstract types as found now in object
oriented languages, and all languages with data abstraction.

Hence, first of all, you should look whether there is something to
be learned from object oriented databases.

I also know that physicists use "databases" to store their
experimental data before exploiting it with specialized software.  If
information can be found on these tools (usually very proprietary),
there is a possibility that they may have addressed this typing issue,
though a physicist told me that is not the case.

Also you should make clear what you intend to provide as input to your
generator, so that your queries make sense. Short of providing some
kind of semantic information, a column of numbers is just a column of
numbers, and any idea you may have to fold, spindle or mutilate them
with SQL queries is fair game. You have to say what data, what semantic information, you provide
to your generator, if you hope for an answer (which is a variant of
the GIGO principle).

I will attempt to illustrate a possible type vision with
physics. Physics uses a lot of scalar quantities: weight, distance,
speed, date, duration, temperature, heat.

You could have these quantities appear to qualify columns in the data
base of a physicist. But not all operations between them make sense.
Testing equality of weight and date probably does not. Actually,
testing equality between to quantities that have different physical
dimension is likely to be meaningless, unless there is some implicit
relation that only the database creator can know about. The same goes
for addition quantities with different dimensions.

Some dimensions have additive qualities, such as weight or volume,
while others do not, such as temperature or density, though they can
be averaged (some of them). Physicists distinguish them by talking of
intensive or extensive properties. Extensive properties are
proportional to the amount of material. They can be added.

I suspect that these concepts exists also for your store management
database, but may have to be refined (I am not sure). The price per
unit of a good is clearly an intensive property. Adding these prices
makes no sense (whether its concerns the same article or different
ones). But, for example, taking the average may have sense, if you do
it for distinct articles.

Now such a classification can lead to more knowledge. For example. the
ratio of two extensive properties is an intensive one. This is why the
price per unit is intensive.

But these concepts apply to properties of materials, and I suspect
things may be more complex than that in general. A ratio could be
additive in a context where   intensive/extensive does not apply.
Still, though speeds can be added in physics, if you have a column of
speeds in your database, it is very likely that adding them makes no
sense, and that taking the average makes a lot of sense.

More generally, dimension equations may give you hints of what makes
or does not make sense. Maybe there are other concepts such as
intensive and extensive properties.

Then, in the same spirits as abstract typing in programming languages,
with a specification that states the allowed primitive operations, you
could have a specification of your database that give you information
about columns (such as dimension, or allowed operations) from which
you can infer whether a queries is meaningful.

But I do not believe this can be inferred from a simple knowledge of
the database without any semantic knowledge provided by the
designer. This knowledge should be part of the design process anyway.

Another point is about ranking. I am not sure that making sense can be
rated on a subtler scale than (true, false). If things can make sense
at all, they can be very important to some people and without interest
to others.  This can probably be measured by actual database use. But
again, it also depends on what you want the ranking for, and on the
kind of semantic information you can provide.


Regarding Backus' Commentary on von Neumann-style Programming in John Backus' 1978 FP paper "Can Programming Be Liberated from the von Neumann Style" he says

To help assemble the overall result from single words [von Neumann ie.
conventional mutation-based] languages provide some primitive
combining forms in the statement world--the for, while,and
if-then-else statements--but the split between the two worlds [ie. between the expression-only and statement-only, as I understand him]  prevents
the combining forms in either world from attaining the full power they
can achieve in an undivided world.

He shows the expressiveness of functional programming, that's what the paper is about, but he implies there's a similar expressiveness that can be got from the statements-only part, per the above quote. However I don't know what he means by this; he gives no examples.
The only language that appears ruthlessly statement-y that I can think of is (pure) prolog (eg. see https://en.wikipedia.org/wiki/Prolog#Quicksort, there's no expressions as such only statements giving relationships) and it's not statements so much as the backtracking that gives it the power.
So what did Backus mean by this? What example languages are there that are statement only (but without backtracking)?
Edit: belated link to orginal paper https://dl.acm.org/doi/10.1145/359576.359579 for interest.
(The question has nothing to do with BNF form. Also, if someone can edit the title to better summarise the long quote, please do Edit: that's much better, thanks!)

Reading the quote literally without the interpolated interpretation, I think what Backus is saying is that a powerful language is one which makes no distinction between expressions and statements.
That is, where all statements are also expressions, like a functional language.
I don't think Backus was claiming that an "all statement" language - the meaning of which is not entirely clear in this context - would be powerful or even feasible. Rather, he is claiming that the existence of certain statements that cannot be analysed as expressions, is a defect in language design.


Why do we need full-fledged workstations running massive OSes with massive software? I've grown up with computers. While watching old computer TV programmes and documentaries and reading the news about constant issues with these modern systems -- everything from the sheer amount of change/bloat/costs to all the security and privacy issues -- one thing that really stikes me hard is:

Why do normal people need computers that are so powerful and complicated?

In decades past, we used simpler, less powerful computers to perform all kinds of tasks, without the issues we face today.

I'm not suggested we swap out current computers for thin clients.  I'm simply saying that current computers seem more powerful than necessary for vast majority of tasks that any person employed by an average company would logically need.

Even in the early 1990s, computers had advanced to the point where "all basic input/output tasks" were "solved". If I were running a company, I would create a minimal computer terminal which runs a minimal OS, and which just boots up and displays a "browser-like" interface that talks over HTTPS to my "mainframe".  I'd use a simple username/password system, with no password resets or two-factor auth, and once logged in, the employee would see only the sections that are relevant for them, coded by me.  For example, a secretary would see a basic form where she can input appointments, list current ones, etc. A different kind of employee, whose job is just to deal with customer support, would only see a minimal list of current support tickets and only have the ability to respond to these in a manner which cannot be misunderstood or abused.  I'd log every action so that I can later look up exactly who messed up or went rogue.

I notice that modern systems don't seem to work that way.  Instead, we have full-fledged PCs with expensive, bloated, and insecure Microsoft or Linux software.  We spend enormous amounts of time, effort, and money to educate employees on how to use it, maintain it, and deal with all the problems that inevitably arise from exposing the general public to such complicated systems.

Why is this?  Why is the only choice between a complex Windows system, a fragile Linux, or some kind of ChromeOS thin client that exposes my data to Google?  Why don't we have a privacy-respecting, minimal thin client OS that can't do anything but display basic HTML, basic CSS and connect over HTTPS, has no system storage or ability to change it, and is just something you hook up to a standard display and network cable and mouse and keyboard.

I realize one still needs to administer the server/mainframe, but presumably this could be done by skilled professionals, rather than the general public.

Can you help me understand why computing works this way today?

You are conflating a number of issues here.

Why does my software have all these features to begin with?

Because other computers' software has those features, and network effects punish any software developer who doesn't follow the herd.

Let's take an example from your question: Why does my web browser need to do anything other than basic HTML and CSS? Well, have you ever tried browsing the modern internet with all JavaScript disabled? It's functionally unusable. The problem is that, once JavaScript existed in a widely used browser (Netscape), people started using it in their webpages. That meant that other browsers had to add support for it to prevent their users from complaining that webpages are broken. And once more users had support for it in their browsers, more webpage authors started assuming that users had it. Round and round the positive feedback loop goes.

Software developers have strong incentives for adding features to software, and strong disincentives for removing them or even changing them.

It's taking 25 years to kill Flash Player, despite it being an incredibly complicated, bug-ridden, security nightmare black box that Adobe themselves no longer wants anything to do with. You know that all hell is going to break loose on December 31, 2020 when the plug finally gets pulled and people can no longer play their beloved Flash games from 2001.

Why do employees of a company need to have full PCs rather than dumb terminals that can only view intranet pages?

Because intranet pages work great until an employee needs to do anything other than the specific tasks that the programmer has predetermined are that person's job.

What happens when someone else (either inside or outside the company—let's call her "Alice") wants to send you a presentation to review and edit? Every person at every job role at my company has had to do that at some point—managers, engineers, administration, facilities, you name it.

You can receive Alice's presentation file on your internal webmail, but you need some way to edit it. And that means your computer needs to be able to edit PowerPoint files, because that's what everyone uses. And PowerPoint files are ludicrously flexible in what sort of content can be contained in them. So we're back to the network effects problem. If Alice sends me a PowerPoint file and I can't edit on my computer because it uses features that my software doesn't support, that's my problem as far as Alice is concerned.

It's functionally impossible to forsee all the things that someone might need to do for most modern jobs, for the simple reason that if it were possible, that job would probably already be fully automated. And that's not even accounting for the fact that many companies allow their employees to use company computers for all sorts of things that are not strictly part of their job description, such as streaming music.

There's also a more general principle here. As you correctly point out, most PCs are "fundamentally overpowered and overcomplicated for the vast majority of tasks that any person employed by a normal, non-highly specialized IT company, or government entity, would logically need." The problem is that a computer that does all the tasks you need 95% of the time but is useless the remaining 5% of the time when you need to do something weird and specialized—is useless as a computer.

I've heard it said that in software design, 10% of the features cover 90% of what any user needs, but that the remaining 10% of what any user needs is different for each user. If you take the set of features used by each user and intersect all of these sets, the result is not sufficient for any user.

"This interface would have a simple username/password system, with no demands to reset passwords or 'two-factor auth' or any of that nonsense"

This gets its own subheading, because this is a totally separate class of issues from everything else you mention. Go over to Security.SE and read about why these things exist. There are very specific reasons for these security practices, that are totally orthogonal to any discussion about complexity of software.


Understanding constraint formula concept in Java JLS defined a concept called "constraint formula". There is a formal definition:

  Constraint formulas are assertions of compatibility or subtyping that
  may involve inference variables. The formulas may take one of the
  following forms:

  ‹Expression → T›: An expression is compatible in a loose invocation context with type T (§5.3).
  ‹S → T›: A type S is compatible in a loose invocation context with type T (§5.3).
  ‹S <: T›: A reference type S is a subtype of a reference type T (§4.10).
  ‹S <= T›: A type argument S is contained by a type argument T (§4.5.1).
  ‹S = T›: A reference type S is the same as a reference type T (§4.3.4), or a type argument S is the same as type argument T.
  ‹LambdaExpression →throws T›: The checked exceptions thrown by the body of the LambdaExpression are declared by the throws clause of the
  function type derived from T.
  ‹MethodReference →throws T›: The checked exceptions thrown by the referenced method are declared by the throws clause of the function
  type derived from T.

I have some misunderstanding about it. As far as I've understood we have a set of all Java types, denote it by M. Could we say, that any constraint formula defines a subset of M, for instance

‹S <: T› = {S | (S belongs to M) and (S is a subtype of T) }

First, not all of the constraint formulas work with types, some of them work with expressions, or other objects. For example, what would be the set for the formula ‹1+1 → Integer›?

Second, a formula might contain zero, one (at either position) or two inference variables (denoted by Greek letters). What would be the set for ‹String → Object›, ‹α → Object›, ‹String → α›, or ‹α → β›?

Third, I think you should think about constraint formulas as predicates, not as sets. For example, the formula ‹String <: Object› is satisfied, while ‹Object <: String› isn't.

And when you have a constraint formula with inference variables, you can start talking about sets of types (or sets of pairs of types for formulas with two variables) that satisfy the formula.

This means that I think that the closest you can get to your equation would be something like:

{α | ‹α <: T› } = {α | (α belongs to M) and (α is a subtype of T) }

(Though the second part is unnecessarily verbose, "α is a subtype of T" already implies "α belongs to M".)


What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)? An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that
$$\left( \bar{M}, M \right) \in R \Leftrightarrow \bar{M} = M^O$$

Given an OTM $\bar{M}$, how to find the TM $M$ such that $(\bar{M},M) \in R$?

Given a TM $M$, how to find the OTM $\bar{M}$ such that $(\bar{M},M) \in R$?

By using the definition of the OTM in wiki, In my opinion,
$$\bar{\Gamma} = \Gamma,~\bar{q}_{start} = q_{start},~\bar{q}_{accept} = q_{accept}, \bar{q}_{reject} = q_{reject} $$
and
$$Q_{0} = Q \cup\{ q_{query} , q_{response}\}$$
I have no idea about the relation between $\bar{\delta}$ and $\delta$. And what about the non-deterministic OTMs and NDTMs?

The definition of $R$ you gave above doesn't make much sense, it looks like you're trying to build an equivalent TM that doesn't use the oracle, but the point of an oracle machine is to provide the TM with capabilities it wouldn't normally have.

For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

If all the oracles you are using are oracles for decidable languages such as those used in complexity theory, then you can obviously simulate them (just construct a universal Turing Machine and use it to carry out the computation), but that's besides the point because it interferes with time/space complexity.

Nondeterministic oracle machines are exactly the same, the nondeterministic part is the transition function, queries to the oracle are treated as though they were a single computational step that magically happens, it is completely orthogonal to nondeterminism.


How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way? I'm considering the following definition of one-way functions:

  Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all polynomial-time randomized algorithms $A$ and all constants $c$,
  $$\underset{x\in\{0,1\}^k}{\mathbb{E}}\Big[\mathbb{P}[A(f(x))=b(x)]\Big]=\frac{1}{2}+o(k^{-c})$$

Note that $A(f(x))=b(x)$ is an event, not because $x$ is random but because $A$ is a randomized algorithm.
Now suppose $f$ isn't a one-way function, then this expectation will be noticeably different from $1/2$. But for any particular $x$ the probability might still be close to $1/2$. Indeed the probability could be exactly $1/2$ (or even 0) for a large fraction of the $x$, provided for the remaining $x$ $f(x)$ can be inverted with sufficient accuracy to make the expectation noticeably different from $1/2$ again.
So what do I do if I'm presented with such an $f(x)$? The fact that many other $f(x)$ can easily be inverted seems of little consolation then. I don't see any way to invert $f$ then. In particular in connection with pseudorandom number generators I'm reading statements like

  We will show that if any tester $A$ can tell the difference between $g(x) = (f(x),\,b(x))$ and a random string, then we can use $A$ to "break" our one-way function, and calculate $b(x)$ from $f(x)$ with $1/\text{poly}(k)$ probability.

I can read this in two different ways.

$x$ is random and there's a $1/\text{poly}(k)$ chance of getting an $x$ for which $b(x)$ can be computed from $f(x)$ exactly.
For every $x$ $b(x)$ can be computed from $f(x)$ with a $1/\text{poly}(k)$ chance of success.

(1) has the problem that the text presents a randomized algorithm to compute $b(x)$ from $f(x).$ It isn't exact.
(2) is false based on the preceding discussion.

Both (1) and (2) are possible.  (It's also possible to have a combination of them.)  It doesn't really matter which holds; either way, that means that $f$ is not one-way.

You say (2) is false because of the preceding discussion, but I'm not exactly sure why you think it is false.   One-wayness is not a property of a specific value of $x$; rather, it is a property of a function $f$.  And, just because a function $f$ is not one-way doesn't mean it can be inverted for every possible output.  If $f$ can be inverted on a significant fraction of outputs, it is not one-way.  If $f$ can be inverted on all outputs, with a significant probability, it is not one-way.

Perhaps the confusion comes from a misunderstanding about what the definition of a one-way function is.  The definition you quote at the beginning is not the definition of a one-way function.  Rather, it's the definition of a hardcore bit.

The part you quoted appears to claim/imply that it is the definition of a one-way function with hardcore bit (which is not the same as the definition of a one-way function).  That claim/implication is not correct.  The precise statement is that this is the definition of a function with hardcore bit.  This definition implies nothing about onewayness.  So why did they call it the definition of a one-way function with hardcore bit? I don't know; you'd have to ask the author. But my guess is that this definition is normally only used with functions you already know to be one-way, so there's an implicit assumption that $f$ is already known to be one-way, and given such an $f$, the definition is describing what it means for $b$ to be hardcore for $f$.

You say "suppose $f$ isn't one-way, then this expectation will be noticeably different from 1/2".  That actually doesn't follow.  You can have a function $f$ that isn't one-way but does have a hardcore bit.  Then the expectation will not be noticeably different from 1/2.  E.g., consider the function $f$ given by $f(x)=0$: it's not one-way, but it does have a hardcore bit, and the expectation is exactly 1/2.

It sounds like you want to understand one-wayness.  If so, hardcore bits are a distraction.  You should be looking for the definition of a one-way function and trying to understand that, not looking at the definition of a hardcore bit.


Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good Suppose that I want to enumerate all English language words of length 5.
If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations.
However, suppose that I can check a partial specification to see if there are any words consistent with it.
By partial specification I mean an assignment of some letters to some positions, with the others free to vary. E.g. "is there a word that starts with "HO" and ends with "Y" (but has any of the 2^26 configurations of third and fourth letter)?
An obvious algorithm would be to formulate it as a 26-tree, and traverse it depth-first, stopping once a pattern was deemed not "good" (e.g. as far as I'm aware there are no five letter words in English that start with "AAA", so we can skip checking "AAAAA", "AAAAB", ..., "AAAZZ").
Is it possible to do any better (average, worst case)? How about under additional assumptions on the distribution of letters (any such learning would need to be part of the algorithm, since my actual problem is not about natural language)? As another view on the second question: what sorts of heuristics are helpful?

If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. $5^{26}$ is of order $10^{18}$, while the actual number of English words is of order $10^5$. So, depending on your application, simply enumerating all words and checking whether they satisfy the constraints may already be sufficiently efficient.
If we are talking about words of a sufficiently small length, then you can just precompute the answer in advance. I.e. word cut will be in an answer for masks ___, c__, _u_, cu_, etc. For words of length at most 5, it'll result in $\le 2^5 \cdot10^5$ memory, which is of order of few MBs.
If the length is big, then you can split the mask into two parts. For each part, we find all the answers, and then intersect them. For example, we treat mask a_b_c_d_e_ as an intersection of a_b_c|_____ and _____|_d_e_. For both submasks, we find the set of words containing this submask, and then intersect them. If the final answer is small, then, hopefully, the result for at least one of these submasks will be small. You can also try to select the positions to include into each submask randomly.
For even bigger lengths, you can split the mask into more than $2$ parts. However, you can probably use that there are not many very large words and simply enumerate them all.


Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG) Let G = (V, E) be a graph which is hierarchical in the sense that its vertices are arranged in levels/layers (say 1 to k) and an edge can only be from a vertex at level i to a vertex at level i+1. Vertices at level 1 and k are called the roots and the leaves, respectively. The problem is to find all descendant leaves of each root.
For instance, for the following graph,

the answer would be:
1: 12, 13
2: 12, 13
3: 12, 13, 14, 15, 16
4: 14, 15, 16

A naive solution can be to run a DFS for each root which will take O(r(n+m)) time where r is #roots, n is #vertices and m is #edges.

Can we do better?
Another way to see the same graph is that it is a bipartite DAG.

Define $\ell(v)$ to be the leaves reachable from a node $v$. Note the following:

  Lemma 1: For all non-leaf nodes $v$ we have: $$\ell(v) = \cup_{u \in c(v)} \ell(u)$$ where $c(v)$ is the set of all children of $v$.

We now construct an algorithm around this:

Let $A = \{v_1, v_2, \ldots, v_n\}$ be the reverse topological order of nodes in $G$.
For all $v \in A$:

If $v$ is a leaf node, define $\ell(v) = \{v\}$.
Otherwise, define $\ell(v)$ as we did in Lemma 1.

Now the complexity of this is $O(km + n)$ where $k$ is the average cost of union-ing the $\ell$-sets of the children of a non-leaf node. How you go about union-ing the sets is up to you. Standard merging is easy to implement. You could also try using a disjoint-set data structure, but this becomes tricky because a node might have multiple parents.


How can a 64KiB computer do the same task as a modern computer? I took an extremely interesting intro to CE course, learning about transistors/memory/logic gates up to LC-3 assembly. Something that was really interesting to me was learning about how a processor's frequency is its speed, determined by the clock signal (if anyone can point to a link of how a clock cycle is made/works or explain, highly appreciated) but my main question is about his claim that any turing-complete computer can accomplish the task of another - performing the same binary operations, just in different amounts of time - that the processor doesn't matter. This depends on memory, though, right? A modern video game wouldn't be able to run on a 64 KiB computer, so I'm wondering if when the textbook and my prof make that claim, it's simply referring to the frequency of the clock cycle (and assuming unlimited/uncapped memory).
Thanks!

The key considerations are infinite memory and unlimited time.  If those two considerations were met, then all modern computers are equivalent.  Since no real computers have infinite memory, and no real humans can afford to wait forever for a calculation, that equivalence is more conceptual than real.


Running time of naive recursive implementation of unbounded knapsack problem How does one go about analyzing the running time of a naive recursive solution to the unbounded knapsack problem? Lots of sources say the naive implementation is "exponential" without giving more detail.

For reference, here's a bit of Python code that implements the brute-force solution. Note that this can run for a long time even on smallish inputs. One of the interesting things about Knapsack is some inputs are lot harder than others.

import random, time
import sys

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value

    def __repr__(self):
        return "Item(weight={}, value={})".format(self.weight, self.value)

def knapsack(capacity):
    if capacity==0: return ([], 0)
    max_value = 0
    max_contents = []
    for item in items:
        if item.weight <= capacity:
            (contents, value) = knapsack(capacity-item.weight)
            if value + item.value > max_value:
                max_value = value + item.value
                max_contents = [item]
                max_contents.extend(contents)
    return (max_contents, max_value)

def generate_items(n, max_weight, vwratio=1):
    items = []
    weights = random.sample(range(1,max_weight+1),n)
    for weight in weights:
        variation = weight/10
        value = max(1, int(vwratio*weight + random.gauss(-variation, variation)))
        item = Item(weight, value)
        items.append(item)
    return items

n=30
max_item_weight=100
capacity=100

items = generate_items(n=n, max_weight=max_item_weight, vwratio=1.1)

st = time.time()
solution, value = knapsack(capacity)
print("completed in %f"%(time.time() - st))

Note that this algorithm can be improved upon nicely by memoizing yielding a O(nW) pseudo-polynomial time solution, but I was interested in understanding how to analyze the brute-force algorithm more precisely.

You will be trying every sequence of items that fit, adding the same item multiple times if that is possible. So first you need to check if you actually wanted the same item to be used multiple times. Whether you did or not, you can make the algorithm a lot more efficient if you only add items in ascending order, that is if you added item k, then you only add further items k, k+1, k+2, ... or only items k+1, k+2, ... depending on whether you wanted to allow the same item multiple times.

You could also save substantial time again by sorting the items for example in descending order. If you do that, you can try adding items with the smallest first, and when an item doesn't fit, you know further items won't fit either - so you can stop the search there.

Anyway, the time depends entirely on the data. If all the items are in size between capacity/2 and capacity then it's $O (n^2)$ (could be $O (n)$ with improvements described earlier). If any item has weight 0, then your algorithm never ends; you should check that first. In the worst case where all n items have size 1 and the capacity is W, your algorithm takes $n^W$ steps - that's especially bad because that particular problem is trivial.


Guessing the structure of a finger tree from the number of elements I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger tree from the sequence efficiently, as described below, and then concat it to the original finger tree. Concat is a very cheap operation compared to adding many elements.

To construct the finger tree, I put the elements into an array, and get its length. Then I build the finger tree from the bottom up, starting with the deepest deep tree and working outwards. This should be much, much more efficient.

In order to do this, I must guess the structure of the resulting finger tree from the number of elements to be added, and I'm not sure how to do this.

From first principles, every 2-3 tree is a finger tree viewed from another angle, so you could solve the problem by solving the somewhat easier problem of "What shape are the valid 2-3 trees of size $n$?"

You can also look at many existing finger-tree libraries. The first one created, was, of course, the Haskell one. The function you are looking for is replicate, which takes a value $v$ and size $n$, then creates a finger tree of size $n$ containing $n$ copies of $v$. The real work of replicate is done in applicativeTree, which has individual cases for $n \leq 8$ and recurses for larger $n$.


CFG for language of all palindromes whose number of 1s is divisible by 3 The question is the following:

  Construct a CFG for $L_2 = \{w \in \{0, 1\}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$.

I can construct a CFG for $\{w \in \{0,1\}^* \mid w = w^R\}$ as follows

$$S → 1S1\mid 0S0\mid 0\mid 1\mid \epsilon$$

I don't understand how to make $w$ divisible by 3 in my CFG.

One way is to use the closure of context-free languages to intersection with a regular language.

In this case, though, it is simple enough to construct the grammar explicitly. The idea is to have three different symbols, $S_0,S_1,S_2$, where $S_b$ generates all palindromes in which the number of 1s is equivalent to $b$ mod 3. The productions for $S_0$ are
$$
S_0 \to 0S_00 \mid 1S_11 \mid 0 \mid \epsilon.
$$
I'll let you figure out the productions for $S_1,S_2$, as well as which symbol is the starting symbol.


Application of difference array for overlapping glass-tint problem For this problem, I heard that using a difference array can solve the problem but I can't seem to figure out how to solve this problem. Could anyone give me some advice? Please keep it simple since I am only a high school student preparing for the national infomatics Olympiad.

Given an array of numbers, we can construct a new array by replacing each element by the difference between itself and the previous element, except for the first element, which we simply ignore. This is called the difference array, because it contains the first differences of the original array. We will denote the difference array of array A by D(A). For example, the difference array of A = [9, 2, 6, 3, 1, 5, 0, 7] is D(A) = [2-9, 6-2, 3-6, 1-3, 5-1, 0-5, 7-0], or [-7, 4, -3, -2, 4, -5, 7].
Source

I've found a solution in Python , but I can't understand it.
Canadian Computing Competition: 2014 Stage 1, Senior #4:

You are laying N rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors.
You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the x-axis or the y-axis (that is, there are no "diagonal" pieces of glass).
You would like to know the total area of the finished stained glass window with a tint-factor of at least T.

Input Specification:

The first line of input is the integer $N$ ($1\leq N\leq 10^3$), the number of pieces of glass. The second line of input is the integer $T$ ($1\leq T\leq 10^9$), the threshold for the tint-factor. Each of the next $N$ lines contain five integers, representing the position of the top-left and bottom-right corners of the $i$-th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order $x_1$ $y_1$ $x_2$ $y_2$ $t$, where the top-left corner is at $(x_1,y_1)$ and the bottom-right corner is at $(x_2,y_2)$, and tint-factor is $t$. You can assume that $1\leq t\leq 10^6$. The top-most, left-most coordinate where glass can be placed is $(0,0)$ and you may assume $0\leq x_1<x_2\leq K$ and $0<y_1<y_2\leq K$, and ...

Output Specification:
Output the total area of the finished stained glass window which has a tint-factor of at least $T$.
I have an implementation but I'm not quite sure how it works. Any explanation would be greatly appreciated.

First, I will look at this problem from a more (high-level) theoretical perspective and then go through the details required in an implementation, based on the solution you linked to.

Given all the rectangles, we can divide the area in rectangular portions such that every portion is rectangular and all points in the same portion intersect the same set of rectangles. An division of the example input in rectangular portions can be seen below:

Our task is to identify the rectangular portions of glass that have at least the required tint $T$. To do this, it is necessary that we iterate in some manner over all these rectangular portions to determine their tint. It is also sufficient: the portions are determined by considering all rectangles they intersect, at which point we can inspect their tint. So, we can create an algorithm that solves this problem in $O(R)$, where $R$ is the number rectangular portions and this is (asymptotically) the best we can do.

But how big can $R$ become? If we have some collection of rectangular portions of the intersection of $i$ rectangles and add a new rectangle, we create one new portions for each portion that is intersected by one of the four edges of the new rectangle. So how many portions can intersect the same horizontal line? At most $2i-1$, since the same horizontal line can be intersected by at most $2$ vertical lines for every rectangle added (apart from the first). So, after adding all rectangles, we get $R\leq \sum_{i=1}^N 4\cdot (2i-1) = O(N^2)$.

So, our algorithm will run in $O(N^2)$. Given that $N\leq 10^3$, it should be fast enough if we implement it efficiently.

But implementing this efficiently could be rather tricky. Sure, it's easy to say that you can just add rectangles and create new portions as a result of their intersection, but that would be pretty cumbersome to implement and possibly inefficient.

This is where the 'difference array' approach comes in. The principle is slightly easier to explain with a 1D-array, so we will restrict the problem to that for now. Suppose we have input

x1 x2 t
11 20 1
13 14 2
17 18 1
12 19 1

So, we can draw it like this:

The array $A$ contains the tint values over all contiguous 'rectangles' in 1d, which is what we need. The array $dA$ is the difference array of $A$. Observe that this difference array can be easily found: after sorting the endpoints of our 'rectangles', we add the tint-value of the rectangle on the left side (when 'entering' the rectangle) and subtract it on the right side (when we 'leave' the rectangle). After we found are difference array $dA$, we can compute $A$ by noting that $A[i] = \sum_{j=1}^n dA[j]$. Then, we scan $A$ to find the areas that have tint $\geq T$ and add the area to our final value and we're done.

For 2D arrays, we do exactly the same thing, but now with an extra dimension to keep track of.

Let me make a final remark: it is in general very hard to 1. reconstruct an algorithm from an implementation and 2. understand an implementation of an algorithm without understanding the algorithm. Therefore, just inspecting source code to understand an algorithm is generally a hopeless task. In this case, I could only understand the implementation in this source after I understood the explanation.


Simplified big O notation of $O(nm)$ for $n\gg m$ Assume $n$ is much greater than $m$. Would $O(nm)$ simplify to $O(n)$? Is there an explanation?

It depends what "$n$ is much greater than $m$" means but, in general, no. For example, one common definition of "much greater" is that $m=o(n)$. But, in this case, we can still have, e.g., $m=n^\epsilon$ for some $\epsilon<1$, or $m=\log^c n$ for any $c\geq 0$ and, in both of these cases, $nm\neq O(n)$.

To get $nm=O(n)$, you need $m=O(1)$.


Order of argument application in lambda calculus I encountered the following exercise in a textbook about logic:

$\lambda x \lambda Y(Y(x))(j)(M)$

It seems that the expected result from the textbook should be $M(j)$, since there were some type specifications on the variables. However, if I substitute $M$ for $x$, and $j$ for $Y$, then the result would become $j(M)$, which would be erroneous in terms of type.

I've seen elsewhere expressions such as:

(λa.λb.λs.λz. a s (b s z)) x y →
(λb.λs.λz. x s (b s z)) y →
λs.λz. x s (y s z)

which seems to have the same application order of arguments as the one desired by this exercise.

It actually seems to make sense if I think of function application in Haskell, but I still find it weird since I expect the rightmost argument to be substituted first for the leftmost lambda term.

Therefore, does the notation $\lambda x \lambda Y(Y(x))(j)(M)$ implicitly entail $\lambda x (\lambda Y(Y(x))(j)(M))$, which would yield the desired result? Is such implicit omission of brackets a normal convention in lambda calculus, and thus every such expression should be treated as such? Or did I misunderstand the order of argument application in lambda calculus after all?

It seems that your book uses the notation
$$
\lambda x_1 \ldots \lambda x_n (M_1 \ldots M_k)
$$
instead of the more commonly found (in my experience)
$$
(\lambda x_1 \ldots \lambda x_n. M_1 \ldots M_k)
$$
Both notations are used for logical quantifiers by different authors, so it's not completely surprising. E.g., compare
$$
\exists x (P(x) \land Q(x))
\qquad {\rm vs} \qquad
(\exists x. P(x) \land Q(x))
$$

In the second style, the scope of binders ($\lambda x$, $\exists x$) extends as far to the right as possible.

About application order: the notation of your book
$$
\lambda x_1 \lambda x_2 \lambda x_3 (M) N_1 N_2 N_3
$$
stands for
$$
(((\lambda x_1 (\lambda x_2 (\lambda x_3 (M)))) N_1) N_2) N_3
$$
It is correct that the outermost application is of $N_3$ but this does not get bound to $x_1$. To see where $M_3$ goes, one first needs to reduce the function
$$
((\lambda x_1 (\lambda x_2 (\lambda x_3 (M)))) N_1) N_2
$$
to a lambda, and this involves applying $N_2$ first. That will require applying $M_1$ first, in turn.

The net effect is that $N_i$ gets bound to $x_i$.

Since you mentioned the Haskell notation, it is basically the same thing, even if Haskell uses the other notation (binders extend to the right as possible).


"Type" of a function template? In C++ a simple function like

int id_int(int x){return x;}

has type id_int :: int->int
a class template like

template<class T>
class List<T>{...};

has kind List :: *->*

But what is the type or kind of a function template like

template<class T>
T id(T x){return x;}

Could it be id :: \x. x->x? Does this even make sense?

A function like T id(T x){return x;} is actually a (parametrically) polymorphic function, and there are many frameworks that allow assigning a type to such beasts.

One of the most popular frameworks to talk about such things is system F, which allows expressing the type of the above statement as: $$\forall T:*.\ T\rightarrow T$$

This requires the ability to quantify over types to form other types, which is the main feature of system F. Note that because id is a value, it's type has itself a kind, that is
$$\forall T:*.\ T\rightarrow T\ \ :\ \ * $$

in keeping with the analogy with List, whose kind is, as you noted, $*\rightarrow *$, which makes it a type constructor.

Note also that the List type constructor is not a term in system F, for that you need to go further out to system ${F}_\omega$, which was designed in part to study how polymorphism and type constructors may interact.


Are there lambda-calculus functions which always output booleans, but are not constant functions? In labmda calculus, true = $\lambda x,y.x$ and false = $\lambda x,y.y$.

Is there a term $f$ such that for any other term $x$, $f x$ normalizes to true or false BUT $f$ does not have the same output for all inputs?

That is not possible. By the "genericity lemma" (Barendregt book, lemma 14.3.24), if $C[M] = N$ with $M$ unsolvable, and $N$ normal form, then $C[L] = N$ for any term $L$.

So, if $x$ is an unsolvable term (like $\Omega=(\lambda w.ww)(\lambda w.ww)$) and $f x = {\sf true}$ (normal form), then $f y = {\sf true}$ for any term $y$. The same holds for $\sf false$ or any other normal form.

The intuition here is that an unsolvable subterm will make the whole term diverge as soon as it is needed for the computation, much like while (true) {} hangs the program in imperative programming as soon as the loop is executed.


How is implication same as entailment In propositional logic (Artificial intelligence to be specific) $\alpha$ entails $\beta$ iff $\alpha\Rightarrow\beta$ is a statement.
However if I write the truth table for implies ($\Rightarrow$) if $\alpha$ is false implies that $\beta$ is a true sentence as shown in the table below in the fourth row.

\begin{array}{cc|c}
    \alpha & \beta & \alpha\Rightarrow \beta\\
\hline
    T & T & T\\
    T & F & F\\
    F & T & T\\
    F & F & T
\end{array}

Now this should be false according to the model checking approach, since there could be models in which $\alpha$ is false but $\beta$ is true given that $\alpha$ entails $\beta$.  This is further supported by the book on artificial intelligence by Peter Norvig that states that $\alpha\vDash\beta$ iff M$(\alpha)\subseteq M(\beta)$, where $M(\alpha)$ is the set of all models where $\alpha$ is true.

Let $\varphi$ and $\psi$ be formulas of propositional logic. We write, as Norvig says, $\varphi\vDash \psi$ iff $M(\varphi)\subseteq M(\psi)$: that is, iff every truth assignment that makes $\varphi$ true also make $\psi$ true. This is the case iff $\vDash \varphi\Rightarrow\psi$, i.e., if the formula $\varphi\Rightarrow\psi$ is true in all truth assignments (is a tautology).

Entailment and implication operate at different levels. An implication is something that may be true or false, depending on which truth assignment you're considering at the moment, whereas an entailment is a statement about all truth assignments.  In particular, the truth of the entailment $\varphi\vDash\psi$ depends only on truth assignments that make $\varphi$ true. If a particular truth assigment makes $\varphi$ false, then it cannot make the entailment false. Similarly, if an assignment makes $\varphi$ false, it cannot make the implication $\varphi\Rightarrow\psi$ false.


What is difference between Buffering and Spooling with respect to Operating System I have googled a lot to find the answer and found some links like this, this and this and even in a book Understanding Computers Today and Tomorrow (13th edition) couple of paragraphs are written as given below:

  Some input and output devices are exceedingly slow, compared to today’s CPUs. If the CPU had to wait for these slower devices to finish their work, the computer system would experience a horrendous bottleneck. For example, suppose a user sends a 100-page document to the printer. Assuming the printer can output 20 pages per minute, it would take 5 minutes for the document to finish printing. If the CPU had to wait for the print job to be completed before performing other tasks, the computer would be tied up for 5 minutes.
  To avoid this problem, most operating systems use two techniques—buffering and spooling. A buffer is an area in RAM or on the hard drive designated to hold input and output on their way in or out of the system. For instance, a keyboard buffer stores characters as they are entered via the keyboard, and a print buffer stores documents that are waiting to be printed. The process of placing items in a buffer so they can be retrieved by the appropriate device when needed is called spooling. The most common use of buffering and spooling is print spooling. Print spooling allows multiple documents to be sent to the printer at one time and to print, one after the other, in the background while the computer and user are performing other tasks. The documents waiting to be printed are said to be in a print queue, which designates the order the documents will be printed.

but I cannot clearly understand the difference between Buffering and Spooling.

Can anyone explain the difference between them in simple and easily understandable terms.

Also in couple of the links mentioned above, it is written as :

  The main difference between buffering and spooling is that the latter allows the I/O of one job to overlap the computation of another. Buffering only allows the I/O of a job to overlap with its own computation.

so what is meant by overlapping the computation of own or other job?

[I don't know whether this is a proper place to ask this question or not, if not, then kindly tell where should I post this to get the answer]

There's not really a significant difference.  Spooling uses buffering.  Buffering can be used for other purposes, too.

The second quote you include in your question (I/O overlap, etc.) looks to me like it's not very helpful.  The key question is whether you have one buffer per process (job) or a shared buffer that is common to all jobs.  If you have one buffer per job, obviously they can overlap.  If you have a single buffer for all the jobs, then if one job starts writing to it, other jobs might need to be locked out (depending upon how you implement the buffer).

Don't worry about these words.  Memorizing the names and the terms "buffering" and "spooling" is not important.  What's important is the concept: the idea of storing some data in a temporary space in memory, so that when the recipient is finally ready to use it, it's all there for them in one spot.


How should I describe the relationships between type expressions? Lets say I have two type expressions: Maybe a (X) and Maybe Integer (Y), where Maybe is a type constructor, Integer is a Type  and a is a type variable.

What language should I use to describe the relationship between these expressions, and type expressions in general? I've been using the language of sets: X describes a subset of Y, X and Y intersect, and so on. Is this generally accepted, or is there a different, widely accepted language for describing the relationships between type expressions?

In the example provided, I would like to express th at expression X describes many possible types, and that includes all of the types described by Y.

The set-theoretic intuitions can make sense in the semantics, especially in the context of realizability semantics (where types are interpreted as sets of terms). In this case, the polymorphic type $\forall \alpha. \mathrm{Maybe}(\alpha)$, written Maybe a in Haskell, intuitively corresponds to the intersection over every type $T$ of the
elements of $\mathrm{Maybe}(T)$. Or in other words, $⟦\forall \alpha. \mathrm{Maybe}(\alpha)⟧ = \bigcap_T ⟦\mathrm{Maybe}(T)⟧$, where $T$ ranges over the semantic domain (and elements of the semantics are injected into the syntax).

On the other hand, set-theoretic intuition does not really make sense on the side of the type system, because standard set operations are not allowed. For instance, it is not possible to refer to the intersection of two types in the syntax (at least when you are not working with intersection type systems, and I don't think this is the case in Haskell). However, one operation on types that is primitive in all type systems with polymorphism is instantiation. This corresponds to the elimination rule for the universal quantifier (or polymorphism), and it states that if you have a term $t$ of type $\forall \alpha, \mathrm{Maybe}(\alpha)$ then the term $t$ can be seen as an element of type $\mathrm{Maybe}(T)$ for any type $T$, for example $\mathrm{Integer}$.


About complexity of a language I have a language which is made out of and has a grammar only operating on well parenthesized words or words of one symbol. I want to know if the problem of belonging to this language is decidable.

Example. Consider the following grammar:
$$a \to a(aa) \\ a \to b \\a (a(a(ab))) \to b$$
I'll denote by $L(x)$ the language generated by the above grammar and rule $S \to x$.

Trivially, $b \in L(a)$, using rule 2.
Also $b \in L(a(aa))$ by the sequence of productions $a(aa) \to a(a(a(aa))) \to a(a(a(ab))) \to b$.
However $b \notin L(aa)$ because after applying rule 1 any number of times and then rule 2, symbol $a$ will be repeated $2n + 1$ times and rule 3 can only remove $4m$ of them.

Note, the grammar is actually dealing with trees. Parentheses denote a subtree and symbols denote leaves. Hopefully the notation is clear enough. The language seems much weaker than RE but stronger than context free.

(I completely removed the previous answer, which was applicable only to this particular example).

Your grammars seem to be known as ground term rewriting systems nowadays.

They are rather old. They might be introduced by W.S. Brainard: Tree generating regular systems. Inform. and Control 14 (1969) 217-231.

Concerning your question. I googled a paper of a good old collegue. Joost Engelfriet: Derivation trees of ground term rewriting systems. If my hunch, that this is the correct model, is correct, I like to cite Theorem 4 of that paper:

  For every extended ground tree grammar $G$ a regular tree grammar $G'$ with $L(G') = L(G)$ can effectively be constructed.

It is in the section called "New proofs for old results", so that must be a known result.


Nim game tree + minimax Problem : Two players have in front of
them a single pile of objects, say a stack of 7 pennies. The first player divides the original
stack into two stacks that must be unequal. Each player alternatively thereafter does the
same to some single stack when it is his turn to play. The game proceeds until each stack has
either just one penny or two—at which point continuation becomes impossible. The player
who first cannot play is the loser. Show, by drawing a game tree, whether any of the players
can always win.

Why is the state 6-1 not going to 3-3-1?If we have 6-1 pennies we can remove 3 pennies from the 6 stack and we have 3-3-1 pennies.So why isn't 3-3-1 not a child of 6-1?

Because - according to the rules above - each player must divide a stack into two stacks that must be unequal.


Optimal combination, given pairwise costs I want to pick k objects from a pool of n. Not any k objects, the optimal k objects: that which minimizes the cost of the set, defined as the sum of pairwise costs for all pairs within the set.

What NP-complete/hard problem is this an instance of?

What is a good (i.e. fast but finds a low cost) way to solve this problem.

This is a generalization of independent set.  In particular, if all edge weights are either 0 or 1, then there's a solution to your problem with total sum 0 iff there is an independent set of size k.  It follows that your problem is NP-hard.

More usefully, your problem is equivalent to the maximum edge-weighted clique problem, which asks to find the $k$-clique that maximizes the sum of edge weights between clique vertices.  (Your versions asks to minimize the sum rather than maximize the sum, but if we negate the edge weights it becomes equivalent.)  Here's one example of a paper that studies that problem, and describes some experiments with different approaches to that problem:

Solving the maximum edge weight clique problem via unconstrained quadratic programming.  Bahram Alidaee, Fred Glover, Gary Kochenberger, Haibo Wang.  European Journal of Operational Research, vol 181, 2007.

A literature search seems to turn up other papers on the subject as well.  (See also https://stackoverflow.com/q/16625964/781723.)


Help Finding Loop Invariant From For Loop I have created the algorithm below...

        String A = v[0];
        int val = 1;

        for (int i = 1; i < v.length; i++) {
            if (val == 0) {
                A = v[i];
                val++;
            } else if (v[i].equals(A))
                val++;
            else
                val--;
        }

The goal of the algorithm is to find the item that occurs in more than half the array.

Let v = {"one", "two", "one", "three", "one", "two", "two", "one", "one"}

The string "one" occurs 5 out of 9 times.  So, at the end of the loop, the String A will be equal to "one".

I'm lost as to how to derive a loop invariant from this.  Could someone provide me with some direction?

See this question on Stack Overflow. You should provide reference for an algorithm when you did not write it, at least explain how you came up with it if you "created" it.

Terminology: this question is about finding the majority element of an array.

The invariant at step $i$ is:

A occurs at least in val cells of v[0..i]
The remaining (i + 1 - val) cells can be discarded without changing the majority element.

The algorithm is easy to accept as correct when you understand that if you remove two different elements of the array, then it keeps its majority element.


Show a predicate is primitive recursive Let $S(i,x_1,\ldots, x_n)$ be a primitive recursive predicate.
 \begin{equation}
 f(i_1,i_2,x_1,\ldots, x_n) =
 \begin{cases}
  1 &\text{ when for all i, }\; i_1 \le i \le i_2,\; S(i,x_1, \ldots, x_n)=1\\
  0 &\text{ otherwise}
 \end{cases}
\end{equation}

Show that $f(i_1,i_2,x_1,\ldots, x_n)$ is also primitive recursive

I use Davis Computability and Complexity book.
I get I need to write as described in this page.
Show $x^y$ is a primitive recursive function

But how to do for predicates? Even a similar example which has predicates would be very helpful.

Do not get confused by the word "predicate". It is actually quite common to show that a function is primitive recursive by using another function for which we already know that it is primitive recursive in its definition.

For example, in the proof that multiplication is primitive recursive one usually defines multiplication using addition, which is not a basic primitive recursive function.

If "predicate" confuses you check out its definition, e.g., wikipedia. It is just a function $f: \mathbb{N} \rightarrow \{0,1\}$. So you can use a primitive recursive predicate just as a primitive recursive function of that kind.

All you need to show is, as mentioned in the comments, that the bounded quantification is primitive recursive.


SAT and Polytime Reductions If an algorithm for $SAT$ runs in $O(n^{\log n})$ time, and if $L$ belongs to $\mathsf{NP}$, is there an algorithm for $L$ that runs in $O(n^{\log n})$ time?

Since any input x for L can be reduced to SAT in O(|x|^c) time, the created SAT instance will have size at most n=O(|x|^c).  So the n^(lg n)-time algorithm for SAT will be an |x|^O(lg |x|)-time algorithm for L.


Finding optimal price in a sale A furniture store is having a sale: purchase two items at the price of the more expensive one. John, having just moved to a new house, rushed into the store and chose $2k$ items of furniture, $f_1, f_2, \dots, f_{2k}$. The items are priced $p_1, p_2, \dots, p_{2k}$, respectively. Help John arrange the items in pairs so that the overall cost of the $2k$ items is minimal. Suggest an algorithm that runs in time $O(k\log k)$ and prove its correctness and running time.

Ok, so it sounds not too complicated: first, I will sort all the $2k$ items by their prices to array, and then each cell and his next are one couple. This takes time $O(k\log k)$.

How can I prove the correctness of what I suggest? I thought about assuming that there is a cheaper solution to get a contradiction but I dont know how to prove this.

Let's do the case $k = 2$. If the prices are $p_1 \geq p_2 \geq p_3 \geq p_4$ then there are three possible pairings $(p_1,p_2),(p_3,p_4);(p_1,p_3),(p_2,p_4);(p_1,p_4),(p_2,p_3)$ with cost $p_1+p_3;p_1+p_2;p_1+p_2$. So the first pairing is the best.

There are several ways to show that this pairing strategy is optimal in general. You might start by showing that given an arbitrary pairing in which $p_1$ is not matched with $p_2$, there is a way to modify it so that $p_1$ is matched with $p_2$, and the overall cost is lower. This leads to one proof.

Another idea is to show directly that the cost is always at least $p_1+p_3+\cdots$. For example, $p_1$ is always the largest in its pair, and $p_3$ is either the largest in its pair, or it is paired with $p_2>p_3$ or with $p_1>p_3$. You have to modify this argument so that you don't double count prices (for example, if $p_1$ is paired with $p_3$ and you follow the argument as stated, you will count $p_1$ twice).

There might be other ways to prove it, so if you have other ideas, by all means go ahead and try them out.


Algorithm for finding fixed cycles in bipartite graphs in sublinear time Does there exist an algorithm that will compute in sublinear time whether a bipartite graph contains a cycle of fixed length? For example given a $K_{3,3}$ graph finding if it contains a cycle $C_4$.

I considered the answer to be no. As a DFS could be used and then compare to see if after a certain traversal we were back at a node we've already visited. That would be $O(n)$ time at best. However, as a counter argument to that, a complete graph will always contain a cycle, and if we know the cycle length then search time should be dependant on the cycle length which would be $O(1)$ or big-oh of the cycle length. If we know whether we're in partition A or B all we have to do is return to the first node since both sets connect to all nodes of the other.

In general, you can't determine if there is a e.g., 4-cycle in an arbitrary graph in sublinear time. This is shown by a simple adversary argument: if you don't read the whole input (this is what sublinear means), how can you possibly know if a critical edge is present that creates the 4-cycle? There are similar questions asked already, but these appear in a different context (usually, these are related to sorting). For instance, see this question.

If you assume the input graph is complete, or has some other structure that guarantees the existence of a 4-cycle, an algorithm for solving the problem can immediately output YES. But if the input graph is arbitrary, again by an adversary argument you cannot determine if the graph is say complete in sublinear time.

For example, if the input is a $K_{3,3}$, you can immediately answer YES. So suppose the input graph is an arbitrary bipartite graph, and we are looking for a $k$-cycle for a fixed $k$. If $k$ is odd, we can output NO, as bipartite graphs are characterized by having no odd cycles. Otherwise, an adversary argument shows that for even $k$, sublinear time is not achievable. Similarly, it is easy to see you cannot test for bipartiteness in sublinear time. (For both cases, consider having read $m-1$ edges, and the last $m$th edge to be read decides if you have a path or a cycle).


Regular expression for a finite automaton appears to be wrong For the following finite state machine:

The language recognized by it is given to be: $0+(10+11)(0+1)^*$ in my samples book, which I think is clearly wrong, since there's no return path to the final state.

I think the language recognized should be just an epsilon or nothing. I wanted to confirm if I am right or wrong with the answer.

Yes, you are right.

As given FA is DFA. It is accepting string only $\{\epsilon \}$.

And, complement of given  DFA accepting :
$\implies (1+0+1(0+1))(0+1)^*= (1+0+(10+11))(0+1)^*$

$\implies 1(0+1)^*+0(0+1)^*+(10+11)(0+1)^* = (0+1)^+ =$ { accepting everything other than $\{\epsilon \}$ string over alphabet $\{0,1\}$}.


Lack of time hierarchy theorem for probabilistic machines The Wikipedia page on the time hierarchy theorem states:

  A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has advice.

However, wouldn't the usual time-hierarchy theorem suffice in this case? For instance, we know that $BPP \subset EXP$, and since the ordinary time-hierarchy theorem implies that $EXP \subsetneq 2EXP$, we likewise know that $BPP \subsetneq 2EXP$. Could we not repeat with the bounded probabilistic version of $EXP$, and so on?

The deterministic time hierarchy theorem is based on our ability to simulate "weaker machines" (namely, those which run in time $T$ whereas the simulator is allowed to run in time $T\log T$), and know their response on a given input. This way, we can construct a machine running in time $T\log T$ which differs from every machine running in time $T$ on at least one input (simple diagonalization).

In the context of BPP however, the response on a given input (i.e. whether or not it belongs to the language accociated with the given probabilistic machine) is determined by the probability of accepting that input, namely if it exceeds some agreed upon threshold. You can of course compute this probability in a naive manner, and diagonlize just like in the deterministic case. This is similar to what you suggested, but calling this a time hierarchy theorem for probabilistic time is hardly fair, since the jumps are big enough to allow you to simply apply the deterministic time hierarchy theorem, avoiding any probabilistic issues. This does not answer for example whether or not $BPTime(n)\subsetneq BPTime(n^2)$.