Type system with subtyping on abstract data types? Consider this example on binary trees in some ML-like language:

type tree =
  | Null
  | Node of tree * tree

let rotate_left p =
  match p with
  | Null -> p
  | Node (a, q) ->
    match q with
    | Null -> p
    | Node (b, c) ->
      Node (Node (a, b), c)

In the definition of rotate_left above I only want to consider rotation on trees where the right subtree is also a node:

let rotate_left (Node (a, Node (b, c))) =
  Node (Node (a, b), c)

In relation to a ML-like type system, this second version of rotate_left is partial where as the first version is total.

Is there a type system expressive enough that such functions would be considered total?

Note;
I use the term "subtyping" in the title of this question, since I think of the values of the type of the second version of rotate_left, to be a subset of the values of the type of the first version of rotate_left.

You want to write some executable code (is_left_restartable) and use it inside a type annotation. This is, by definition, a dependent type.

The problem when you have dependent types is that it's hard to keep type checking usable for a programming language. It's generally desirable to keep the type system decidable, because programmers tend to be annoyed when a programming error causes the compiler to loop forever. So at the very least the type constraints need to stick to a subset of the language that guarantees termination. And of course since type constraints are evaluated at compile time, they can't contain any side effects.

It isn't too difficult to define a subset of the language without arbitrary recursion. For example, just forbid recursive functions. And, to keep things simple, forbid the use of library functions or functions defined in a different module — if you don't do this then library functions need to be annotated, not only so that the type checker knows that they're allowed in types, but also so that the compiler knows what to make of them.

Even if type constraints are in a subset of the language that always terminates, that doesn't make them decidable. For example, if the type constraints can include enough arithmetic to encode addition and multiplication of variables — a context in which this comes up naturally is array lengths — then the type system encodes Diophantine equations and is therefore undecidable. It's possible to keep the system decidable if it only allows additions and not multiplications of variables, as in Dependent ML.

Even when type checking remains decidable, it's a lot harder to keep type inference decidable. That's not a big problem in itself, because programmers who want to benefit from the finer-grained types can just write type annotations. But it can be difficult to precisely define when type annotations are needed and when they aren't. It's still a difficult problem to find a good balance between requiring a lot of annotations, and making it easy for programmers to know when annotations are needed.

When the type constraints are purely defined in terms of pattern matching, as in your example, they can be expressed using generalized algebraic datatypes (GADT). GADT have matured enough to be supported in mainstream languages, notably OCaml. To avoid extensive analysis of which functions are allowed in types, most implementations of GADT including OCaml's use the type system to express constraints, not the term syntax. You would need to define is_left_rotatable as a type, and to write a transformation function from matching trees to is_left_rotatable.


Why does parallelising slow down this simple problem against looping through all the data? I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn anything, just on the 4 CPUs of my Mac.

I created a task to add 100 to every element in a 500,000 element list. To my surprise, I noticed that batching this data and using Python's parallelising tools to implement this actually slowed it down hugely, compared to just looping through the 500,000 elements and adding 1.

I'd like to understand why.

Consider the two methods for doing this task below:

import numpy as np
from sqlitedict import SqliteDict
from multiprocessing import Pool, cpu_count
from gensim.corpora.wikicorpus import init_to_ignore_interrupt
from itertools import zip_longest
import timeit as t

def grouper(iterable, n, fillvalue=None):
    args = [iter(iterable)] * n
    return zip_longest(*args, fillvalue=fillvalue)

class Add100ToData():
    def __init__(self):
        self.data = [np.random.randint(0, 100) for _ in range(500000)]

    def add100(self):
        for i in range(len(self.data)):
            self.data[i] = self.data[i] + 100
        return self.data

class Add100ToDataMultiprocess():
    def __init__(self):
        self.data = [np.random.randint(0, 100) for _ in range(500000)]

    def process_batch(self, batch):
        new_data = []
        for i in batch:
            new_data.append(i + 100)
        return new_data

    def add100(self, batch_size):
        processes = cpu_count()
        pool = Pool(processes, init_to_ignore_interrupt)
        gr = grouper(self.data, batch_size)

        for batch_result in pool.imap(self.process_batch, gr):
            count = 0
            for i in batch_result:
                count += 1
                self.data[count] = i
        return self.data

if __name__ == "__main__":
    add1 = Add100ToData()
    start = t.default_timer()
    final1 = add1.add100()
    end = t.default_timer()
    print("Looping run-time: {:.2f} seconds".format(end - start))

    add2 = Add100ToDataMultiprocess()
    start = t.default_timer()
    final2 = add2.add100()
    end = t.default_timer()
    print("Looping run-time: {:.2f} seconds".format(end - start))

This gives me:

Looping run-time: 0.13 seconds
Multiprocessing run-time: 1.23 seconds

Why is there an improvement in simply looping through the data as opposed to parallelising and batching with simple tasks?

When I was doing this for a far more labour-intensive task (one task was transforming 800,000 sentences into their 300-dimensional word embeddings, and another was applying a classifier to these), I gained huge speed improvements using 32 CPUs on the Google cloud, with a very similar code structure to this.

Can someone help me to understand why I'm not getting speed improvements here?

Parallelism has costs. The processes have to be scheduled, communicate with each other, manage resources, etc. In return you can do multiple things at the same time.

When you have a lot of slow tasks that can be done independently, parallel processing will speed things up a lot.

But when you try to parallelize an easy task it might take longer to handle the overhead than to actually do the work. That seems to be the case here.


What does "dummy argument" mean? What is does it mean when an argument to a function is called a dummy argument? I have not encountered this term outside Fortran, is it a general term in computer science? What would be examples of arguments passed as dummy and not passed as dummy?

I found this definition, which I am not sure that I understand, but it sounds like a dummy argument is a variable that is passed by reference, in which case in Fortran all variables are dummy variables? (confused)

Edit: I just run into the following essay which helped me to understand better Fortran's argument/function calling teminology: Dortor Fortran: I've come here for an argument

In fortran a dummy argument is what other languages
refer to as a formal argument. So the dummy arguments
are the list of arguments in the function (or subroutine) definition.

The actual arguments are the list of arguments in the calling
list, at the point in the source code where a function is called (ie used).


If A and B are NP-complete, then A ∪ B need not be NP-complete I am studying the proof of this exercise (link)

  There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example:

  $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$
  $B = \{0x : x ∈ SAT\} ∪ \{1x : x ∈ \{0, 1\}^∗\};$.

  The languages A and B are N P-complete (prove it). On the other hand, A ∪ B contains allbinary strings (i.e. A ∪ B = {0, 1}∗); and thus it is not N P-complete.

I know the Union (L1 ∪ L2) of two NP language L1,L2 ∈ NP is NP. I can describe a TM not-deterministic for $\{1x : x ∈ SAT\}$ (and for $\{0x : x ∈ SAT\}$) and therefore $\{1x : x ∈ SAT\}$ is NP (note, I know SAT is NP). I have a problem to understand why $\{0x : x ∈ \{0, 1\}\}^∗$ is NP? I remember $\{0, 1\}^∗$ is in P, and I cannot describe a TM not-deterministic for $\{0x : x ∈ \{0, 1\}\}^∗$

P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.


Expected behavior of an algorithm to minimize rankings Suppose $n$ students have preferences over $n$ different notebooks. Their preferences can be represented with a square matrix of size $n$ where each column is a different permutation of the vector $[1:n]$, where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.
For example, such allocation in the problem below
  1    2    2
  2    1    3
  3    3    1

would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.
My two questions are the following. If the matrix with preferences is chosen uniformly at random, what is the expected sum of rankings in the assignment that minimizes the sum of rankings?
Second, I can answer this question by running a simulation, but is there a known algorithm that efficiently finds the allocation that minimizes the sum of rankings?
Idea: In the best-case scenario, this sum is $n$. In the worst-case scenario, where each column is identical, the sum is $n(n+1)/2$. The expectation over all possible cases must be somewhere in between.

Finding the minimum matching is known as the assignment problem, and it has efficient solutions.
Your exact problem has been considered by Parviainen, Random assignment with integer costs — it's his "Case I". Parviainen showed that the expected value is between $\frac{\pi^2}{6} n$ and $2n$, and his simulation results suggest an intermediate value $cn$, where $c \approx 1.830$. See also the survey by Krochmal and Pardalos, Random assignment problems.


Compressing normally distributed data Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly?  Given the entropy of the Gaussian distribution, it should be possible to store any value $x$ using $$\frac{1}{2} \mathrm{log}_2(2\pi\sigma^2)+\frac{x^2}{2\sigma^2}\rm{log}_2\rm{e} \;\text{ bits.}$$
Arithmetic coding should provide perfect compression.  In principle it's not too hard. I can calculate the interval boundaries from the cumulative distribution function of the Gaussian.  In practice, I hit considerable difficulties because when using floating point operations I cannot achieve perfect reproduction of the results, and I have no idea how to do this without FP operations.  Perfect reproduction is necessary because the uncompressing code must come up with exactly the same interval boundaries as the compressing code.

So my question is:  How do I compute the interval boundaries?  Or is there any other way to achieve (near) perfect compression of such data?

Strictly speaking, the normal distribution is defined only for continuous variables.  So what I mean here are integers x with a probability distribution function $$P(x)=\frac{1}{\sqrt{2\pi\sigma^2}}\rm e^{-\frac{x^2}{2\sigma^2}}.$$
This distribution does not sum up exactly to 1.  However, for $\sigma>100$  the difference from 1 is less than $10^{-1000}$ and hence it's more precise than any practical calculation would be.

In what follows, I'm going to assume that $x \ge 0$, and then try to put that back later.

First, we'll simplify the notation a little. The length of the code for $x$ should be:

$$L_m(x) = a + b \left(\frac{x}{\sigma}\right)^2 + \log_2 \sigma$$

where:

$$a = \frac{\log_2 2\pi}{2} \approx 1.325$$
$$b = \frac{1}{2 \ln 2} \approx 0.721$$

This suggests that you should divide $x$ by $\sigma$, encode the remainder in $\log_2 \sigma$ bits, then encode the quotient $q$ in $a + bq^2$ bits (say, using arithmetic coding). Instead of storing $20002$ codes using Yuval's method, you now only need $20$ or so.

In a sense, what you're doing here is converting the normal distribution to a standard distribution. Moreover, if you move $\sigma$ to the nearest power of 2, the division can be done using bit shifts and masks. $\sigma=1024$ is close enough to $1000$, so that part of the operation is extremely cheap.

However, there is a catch. To arithmetic code $L_0(10)$, you need about 60 bits. On a 64-bit machine, this is pushing the practical limit of an efficient arithmetic coder. So you should probably consider partitioning the space for more efficient encoding.

One possibility is to use binary arithmetic coding, with one binary symbol per $\sigma$. The probability that $x$ is within $\sigma$ of the mean is $0.6826895$ (or so). The probability that $x$ is within $2\sigma$ given that it is not within $\sigma$ is $0.85660651$ (or so), and so on. I calculate the code length for the $8\sigma$ symbol to be around 27.3 bits, and trying to calculate the length for $9\sigma$ breaks into numeric instability using the simple calculation that I did.

No matter what you try, representing numbers that are more than about $8\sigma$ from the mean is going to be difficult to do well, but given that those numbers are extremely rare, perhaps you should just fall back to a universal code (e.g. one of the Elias codes) for that case.

So in summary, here's the representation that I'd try.

Divide $\left| x \right|$ by $\sigma$. Call the quotient $q$ and the remainder $r$.
Store the sign of $x$ as a single bit.
Arithmetic encode $q$ using a sequence of binary variables:

Use a single binary symbol with $p_0 = 0.6826894921370859$. Store $0$ if $q=0$, or $1$ if $q>0$.
If you stored $1$, use another binary symbol with $p_0 = 0.8566065013011934$. Store $0$ if $q=1$, or $1$ if $q>1$.
...and so on. Stop when you get to $q \ge 8$).

If $q<8$, binary encode $r$ in $\log_2 \sigma$ bits.
If $q\ge 8$, use a universal binary code of choice (Elias gamma is a popular choice) to store $x - 8\sigma$.

Now having said all this, a common approach used in many compression standards, which works fairly well when $\sigma$ is small, is to use exp-Golomb coding. It's not theoretically perfect, but seems to work well in practice.


Most space-efficient lossy dictionary? Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)?

Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ of $n$ key-value pairs $(k_i, v_i)$, assorted with a query operation. Let $K = \{k_1,\dots{},k_n\}$. The query operation is defined as:

$$query_D(k_i) = v_i,$$
$$query_D(k) = \bot \text{ for } k \not\in K.$$

However, false positives (returning a $v_i$ for a $k \not\in K$) or false negatives (returning $\bot$ for a $k_i$), respectively occurring with probability $p_p$ and $p_n$, are acceptable to some degree.

Many efficient techniques exist, but I am having trouble figuring out the most efficient one. I am chiefly interested in space efficiency (as a function of $p_p$ and $p_n$). $query$ efficiency is not a main concern (but should remain sublinear in $n$). I assume that keys and values are of fixed size of respectively $s_k$ and $s_v$. I also assume that keys (both in $S$ and those queried) are uniformly distributed in $\{0,1\}^{s_k}$.

I know of some examples:

Cuckoo hashing
Bloomier filters
Minimal perfect hash function + signature (to alleviate false positives)

They are however not trivial to compare, and I am also not sure there isn't better out there. Any insight would be appreciated!

Let's see what we can do. Values are random and hence are incompressible, but keys can be sorted and then diffed. So, just sort the data, employ difference compression schema for keys and use binary search to find.

It will put your N keys+values into minimum amount of bits required to keep this amount of information.

May be, you can further improve compression ratio by dropping less compressible items.

EDIT: As mentioned here, you can compress keys to smaller values. So, f.e. you can use Bloom filter to check that probed key is included in the result set, and then use compressed 32-bit hash of the key to find it in table with 64K entries with pretty high fidelity. NOTE: at more thorough analysis I realized that Bloom filter will occupy at least the same space you will economy on reducing key values stored in the sorted table.

PS: You can use any rehashing scheme, including Cuckoo hashing, to cut off rehash chains at some point, but anyway sorted sequence should be better compressible than any hashtable containing unused cells.

Perfect hashing just helps you to make hashtable without holes. I don't know what signature you mean here.

Bloom filter by itself only checks value presence, then you still need to store entire key+value pair.


is it necessary to cover all the verticies in eular path? I was going through graph theory and came across the term Euler path or some people prefer Euler trail as vertices can repeat.

According to the definition from wiki (https://en.wikipedia.org/wiki/Eulerian_path), Euler path is defined as under

  In graph theory, a Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once.

Following are the conditions for Euler path,

  An undirected graph (G) has a Eulerian path if and only if every vertex has even degree except 2 vertices which will have odd degree, and all of its vertices with nonzero degree belong to a single connected component.

So as per the definition, I need to cover all edges in a connected graph with non zero degrees.

The same information is stated here at geeks for geeks(https://www.geeksforgeeks.org/eulerian-path-and-circuit/).

so if I need to only consider vertices with non zero degrees then graph (G)can be disconnected?

Note: These are the other information I collected from the wiki page

1)Finite connected graph (with vertices of even degree except 2 or 0 with the odd degree) will have a Euler path.
2)But Euler path can also be present in the disconnected graph as shown in the following picture

3) Doubt does following graph have Euler path,

My answer ,No as all vertices are not in same connected component.

It really comes down to your definition of an Euler trail. The one I'm familiar with is similar to the one on Wikipedia:

  An Euler trail is a trail (path that allows repeats) that uses every edge exactly once.

With this definition, an Euler trail doesn't have to touch every vertex: if there's a vertex with no edges, the Euler trail doesn't have to go anywhere near it.

However, if there's a vertex with positive degree, and another vertex with positive degree, and they're not (weakly) connected, then there can be no Euler trail. Because if you use the edges on one, there's no way to reach the edges on the other.


Proof of Karp-Lipton theorem I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009).
In particular, this book states the following:

Karp-Lipton theorem
If NP $\subseteq$ $P_{\backslash poly}$, then PH $= \Sigma^p_2$.
Proof:
By Theorem 5.4, to show PH $= \Sigma^p_2$, it suffices to show that $\Pi^p_2\subseteq \Sigma^p_2$ and in particular it suffices to show that $\Sigma^p_2$ contains the $\Pi^p_2$-complete language $\Pi_2$SAT.

Theorem 5.4 states that

for every $i \geq 1$, if $\Sigma_i^p = \Pi_i^p$ then PH = $\Sigma_i^p$. That is, the hierarchy collapses to the ith level.

I am failing to understand how $\Pi^p_2\subseteq \Sigma^p_2$ implies $\Sigma_2^p = \Pi_2^p$.
As a more general question: does this hold for every $i$, i.e. does $\Pi^p_i\subseteq \Sigma^p_i$ imply $\Sigma_i^p = \Pi_i^p$ for all $i \geq 1$?

Recall that $L \in \Sigma_i^p$ iff $\bar{L} \in \Pi_i^p$. Suppose now that $\Sigma_i^p \subseteq \Pi_i^p$, and let $L \in \Pi_i^p$. Then $\bar{L} \in \Sigma_i^p$ and so $\bar{L} \in \Pi_i^p$ by assumption, implying that $L \in \Sigma_i^p$. In other words, $\Pi_i^p \subseteq \Sigma_i^p$, and so $\Sigma_i^p = \Pi_i^p$.

Here's why $L \in \Sigma_i^p$ iff $\bar{L} \in \Pi_i^p$. For concreteness, we take $i = 3$. By definition, $L \in \Sigma_3^p$ if for some P-time predicate $T$,
$$
x \in L \Leftrightarrow \exists |y| < |x|^{O(1)} \forall |z| < |x|^{O(1)} \exists |w| < |x|^{O(1)} T(x,y,z,w).
$$
Similarly $\bar{L} \in \Pi_3^p$ if for some P-time predicate $S$,
$$
x \in \bar{L} \Leftrightarrow \forall |y| < |x|^{O(1)} \exists |z| < |x|^{O(1)} \forall |w| < |x|^{O(1)} S(x,y,z,w).
$$
However, these two statements are equivalent, as a simple invocation of de Morgan's laws shows, together with the fact that P is closed under complementation (take $S = \lnot T$).


What is a weighted or probabilistic automaton? I'm developing a program that has some entities (things) that are "classified" according to "relevancy". Sort of like search engine (think PageRank).

Therefore, I'm looking to implement an automaton, which I think should handle "value hierarchies". What I mean is that each "next possible state" should have a value that determines how "relevant" it is relative to the state from which are to be moved to it.

Is this called a weighted automaton?
Or a probabilistic automaton?

This is what I want:

(From: http://engineering.flipboard.com/2014/10/summarization/)

To be able to have the states that can be "moved to" have different "relevancy values".

My application reminds of this:

(notice the "sub contexts" centered at the blue texts)

(From: http://shadow.cios.org:2222/www/vcceguide/images/full-screen/vcce-menunew-conceptanalysis-1c3b-tripleconceptnetwork-conceptmenusearch.png)

I think it's an automaton that (in my program) would be going through those "sub contexts" (moving from blue text to blue text, based on user input). But what kind of automaton?

The setting you suggest is not clear enough to determine what kind of an automaton you are looking for.

A short explanation regarding the types of automata:

A weighted automaton is typically an automaton with a weight function on the edges (or states). Then, a run is assigned a weight according to the weight it traverses. There are many different semantics for the value of a run. These include the maximum/minimum weight, the sum, a discounted sum, an average, etc. Finally, nondeterminism is resolved with some semantics. Typically max/min.

The important thing is that a weighted automaton defines a function $f:\Sigma^*\to \mathbb{R}$, instead of a Boolean language (which can be thought of as a function $g:\Sigma^*\to \{0,1\}$).

Probabilistic automata can be thought of as a sort of weighted automata, but a distinction is usually made (mainly because weighted automata are often defined over a tropical semi-ring). In probabilistic automata, the "weights" (probabilities) are multiplied along a run, and the sum of the (accepting) runs is taken.

If you elaborate or demonstrate the scenario you are thinking of, perhaps I can modify the answer to suggest an appropriate model.


Algorithm to search substring in a circular string? I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt.

However, as far as I understand, these operate on "regular" strings, but what I need is a substring search on a circular string.

A circular string as a string characterized only by its size and the order of the elements, i.e. ABCD is the same as BCDA, CDAB and DABC

An source/query example that should succeed:

Source string: EFxxxABCxxxxxD
Query string:  DEF

Do you know of any references on substring search on circular strings? Any advice on how to do this?

(Possibly) related:

CS: Automaton for substring matching
SO: main differences between the KMP and BM algorithms?
http://en.wikipedia.org/wiki/String_searching_algorithm

Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string.  The source string must be concatenated at least once.

Then perform a simple (non-circular) search on that temporary string.


Lambda calculus: difference between contexts and evaluation contexts Firstly, I'd like to say that my text below may contain errors, so feel free to point out any mistakes in my formulation of the question.

Consider an untyped lambda calculus with booleans and if-statements whose terms are given by this syntax:

 t ::= v | t t | if t t t | x
 v ::= \x.t | #t | #f

Contexts C in this case would be given according to this syntax:

C ::= [-] | \x. C | C t | t C | if C t t | if t C t | if t t C

Additionally, one could define evaluation contexts E according to this other syntax:

E ::= [-] | \x. E | v E | E t | if E t t

I split my question in three sub-points which I'd like to be addressed.

When are the two notions used? I know for example that evaluation contexts are used to define the semantics of the calculus, but the usage of contexts still somewhat eludes me. Also I'd like some confirmation of my knowledge here.
When is one to be preferred to the other and why?
Could you point to relevant articles that could help me sort out this matter?

Context are used for many purposes, but typically to define congruences on programs. Evaluation contexts are a subset of contexts. They are typically used to define reduction relations. Let me give an example of each.

One formal way of defining program equality is to say two programs $M$ and $N$ are contextually equal they can replace each other in each context without a change of behaviour. We can define this as follows: $M$ and $N$ are contextually equal provided for all closing contexts $C[\cdot]$ for $M$ and $N$: $C[M] \Downarrow t$ if and only if  $C[N] \Downarrow t$. We say a context is closing for $M, N$ if neither $C[M]$ nor $C[N]$ have free variables. The expression $M \Downarrow t$ means that the program $M$ reduces in a finite number of steps to the value $t$. (As an aside, note that the definition of contextual equivalence is more involved for rich notions of computation, e.g. concurrent processes.)

In contrast, evaluation contexts are contexts that do not block evaluation.
More precisely, an evaluation context is a term with a hole at the point where the next atomic reduction step must  take place (or may take place for non-deterministic computation).
 So the following rule should hold for evaluation contexts:
$$
  \frac{M \rightarrow N}{E[M] \rightarrow E[N]}
$$
As an example of using evaluation contexts, consider the reduction rules for
call-by-value $\lambda$-calculus, where we do not reduce under $\lambda$. So even when $M \rightarrow N$, we don't have a reduction $\lambda x.M \rightarrow \lambda x.N$. This can easily be expressed with the  general contextual rule above,
together with a grammar for evaluation contexts that omits $\lambda$-expressions. Evaluation contexts were first used in The Revised Report On The Syntactic Theories of Sequential Control and State by Felleisen and Hieb.


Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem I am really confused with this problem.

Here's the problem:

You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at the same place, but multiple arrows can point to the same place and arrows can start and end in the same place. The arrow from place $i$ points to place $a[i-1]$,($a$ being an array representing the game board with $N$ elements and $i$ is between $1$ and $N$, inclusive).There are $0$ to $N$ tokens,inclusive, placed in those places and that, in each round, move along the arrows from their current place. If two or more tokens are in the same place, then you lose that game. But if that doesn't happen for the $K$ rounds specified, then you win the game. There may be multiple ways to solve the problem, but  Two ways are different if there is some $i$ such that at the beginning of the game place $i$ did contain a token in one case but not in the other. Count those ways and return their count modulo $1,000,000,007$.

The whole problem is confusing to me, but what really confuses me is that it states that the arrow that starts from $i$ goes to  $a[i-1]$. How I understand it, for the first example,( $\{1,2,3\} \;5$ Returns:$8$ ), if $a[1]=1$, $a[2]=2$, and $a[3]=3$, then $3$ maps to $2$ and $2$ maps to $1$, but then $1$ maps to $0$,(but point $0$ doesn't exist).

What would be more correct would be if $a[0]=1$, $a[1]=2$, and $a[2]=3$, but then all the points would map to themselves,(though it says in the example that the tokens don't move during the rounds).

I am probably way off, but I couldn't find many explanations, and the ones I found didn't make any sense to me, and I couldn't find many visual depictions either.

$a[0] = 1, a[1] = 2, a[2] = 3$.

"The arrow from place $i$ points to place $a[i−1]$"

So yes, all $3$ places in this sample point to themselves. It actually says in the explanation that "in each round each token will stay in the same place".

In the second sample, all three places point towards the first one.

In the third sample, you have a $2$-cycle: $1$ points to $2$ and vice-versa.

Is everything clear now?


How to vocalize hexadecimal numbers? When I want to vocalize a hexadecimal number like 0x41, so I say "forty one in hexadecimal", "four, one in hex" or what? Or do you always have to calculate and say "65 in hexadecimal notation"? I feel like that would complicate communication if I just want to tell someone what numbers I see on the paper in fornt of me, so he can write them down for example.

The best way is to read out the digits and then say "hex(adecimal)". Don't say "forty-one hex" because "forty" means four times ten, whereas the four in 41h stands for four times sixteen. Don't say "sixty-five in hex" because then the person you're talking to doesn't know if you mean "The decimal number sixty-five, only written out in hex, i.e., four-one-hex" or "The number six-five-hex, i.e., one hundred and five decimal."


Why does this triple loop code have a running time of 1.5lnN * N^2 Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term comes from, but I am completley lost on the $3 \ln N$ term. Unfortunatley this is the only solution.

Let's consider the outer two loops first. For a fixed value of $i$, the number of iterations of the middle loop is exactly $n-1 - (i+1) + 1 = n - i -1$.
Since $i$ ranges from $0$ to $n-1$ (in the outer loop), the overall number of iterations of the middle loop is:
$$
\sum_{i=0}^{n-1} (n - i -1) =
\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}.
$$

For each of those iterations we execute the inner loop for a certain number $x \in \mathbb{N}$ of iterations. Notice that $x$ only depends on $n$ and not on $i$ or $j$.
Before the first iteration, the value of $k$ is $1$, and it doubles after every iteration (i.e., before the next iteration starts). This means that after a generic number $h \in \mathbb{N}$ of iterations (i.e., just before the $(h+1)$-th iteration starts) the value of $k$ is $2^h$. Since the loop continues as long as $k = 2^h < n$, we are interested in the minimum value of $h$ for which the above inequality is not true. This is $x = \lceil \log n \rceil $ if $n \ge 1$ (where we used the fact that $h$ must be a non-negative integer) and $x = 0$ otherwise. Since you are interested in the asymptotic behavior of the algorithm, I will ignore this latter case.

Finally, notice that for each iteration of the inner loop, exactly $3$ array accesses are performed.

To summarize:

We reach the inner loop $\frac{n(n-1)}{2}$ times;
Each time we perform $\lceil \log n \rceil$ iterations;
Each iteration causes $3$ array accesses.

The total number of array accesses is therefore:
$ \frac{3}{2}n(n-1) \lceil \log n \rceil  \sim \frac{3}{2}n^2 \log n$.


Connection of "modern" runtimes and number of steps on a Turing machine Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is O(nlog(n)) and therefore Turing machine which implements this algorithm will do O(nlog(n)) steps. Why is this conclusion correct? And vise versa: if there's no deterministic Turing machine which takes less than exponential number of steps to solve some problem, we aren't able to find efficient algorithm solving this problem.

Your premise that turing machines can implement algorithms with the same efficiency as a modern computer is not correct.

Turing machines can simulate 'enhanced' turing machines that have the properties of modern computers (e.g. random access into memory, multiple memory spaces, etc) with only polynomial slowdown.

However, not all problems can be solved exactly as fast on a turing machine. For example, consider the problem PALINDROME to determine if the input is a palindrome. On a modern computer there is an obvious $O(n)$ algorithm, where you just read the front and back character, and if they match recurse on the inner substring. This problem is known to require $\Omega(n^2)$ time for a classical turing machine to solve. This means turing machines are decidedly "weaker" by some amount compared to an ideal modern computer.


Solutions to synchronization problem need to be executed in critical section I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like test_and_wait() and compare_and_set() are performed atomically at the hardware level and in all other software solutions like mutex, semaphore the code needs to be executed atomically and hence these have to be executed in the critical section themselves.

Does this mean that these software solutions have limited use when compared to the hardware solutions, though it seems that the former are used extensively?

Atomicity and mutual exclusion are different concepts that are related in that either can be used to implement the other.  The important property of mutexes and semaphores is not so much that they are atomic as they guarantee that only one process can get past a particular point at a time.  Atomic read-modify-write hardware primitives like test_and_set() and compare_and_swap() can be used to implement mutual exclusion, but it is not true that atomic hardware operations are required to implement mutual exclusion - Lamport, Leslie; The Mutual Exclusion Problem Has Been Solved, CACM 34(1):110, 1991.

Mutual exclusion requires two different primitives.  For example with a mutex you need both a try_acquire() operation and a release() operation.  You would typically use something like a test_and_set instruction to implement try_acquire(), but a simple store operation is usually sufficient to implement release().  (And test_and_set is not required to implement try_acquire() as demonstrated by Lamport, it's just easier if you have such an atomic instruction.)  Similarly, a semaphore has different down() and up() operations.

Further, most mutexes provide acquire() operations that do more than just try_acquire(), they also provide an efficient way of waiting for the mutex to become available if the try_acquire() should fail.

Conversely: a mutex can be used to implement a complex atomic operation.  Suppose you want to implement an atomic increment operation on a machine that has a mutex (perhaps implemented without atomicity by using something like Lamport's Bakery Algorithm) but you don't have direct access to any atomic instructions.  Something like the following will work:

mutex   m
integer i

atomic_increment():
  m.acquire()
  i = i+1      # only one process at a time can be at this code point
  m.release()

So neither mutual exclusion nor atomicity is more "fundamental" than the other, they are really two different things that can be used to implement each other.


Why Is KD-Tree-based Nearest Neighbor Exponential in K? I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why.

What I'm looking for is a solid runtime-complexity analysis which explains this aspect of the problem.

kNN tends to be exponential because the search space increases with $2^k$. Imagine you partition the space around your search point into quadrants. For k=1 you just have to search two 'quadrants' (higher and lower values), for k=2 it's 4 quadrants, for k=3 it's 8 quadrants, i.e. exponential growth of search space. That is what the kD-tree suffers from, because it has to search $2^k$ sub-branches.

Other trees perform much better, for example the CoverTree. I also found that the PH-Tree works quite well, it seems to consistently take twice as long as the CoverTree for datasets between k=8 and k=27 (I didn't have datasets with higher k).


Minimum Path cover in a Directed Acyclic Graph Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-disjoint paths that cover all the vertices of $G$ subject to the constraints that:

the weight of each path is at most $k$.
each path should include at least one edge of $D'$.

What is the complexity of this problem?

This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard.

Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i<j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there exist 2 vertex-disjoint paths satisfying your conditions if and only if the weights can be partitioned into two subsets both with sum $k$, which is exactly the partition problem. Hence, your problem is NP-hard.


Proving Blank-halt to be recursively enumerable through reduction to Halting problem To prove the blank-halt problem is undecidable (does a given Turing machine halt on the empty input), it's a case of reducing the halting problem to the blank-halt problem and since the halting problem is undecidable, the blank-halt problem is undecidable.

However to prove the blank-halt problem is recursively enumerable just like the Halting problem, isn't the reduction then the other way around? In order to prove this part does the blank-halt problem get reduced to the halting problem and so if the halting problem is recursively enumerable then the blank halt problem is also recursively enumerable?

I'm confused about the reduction flow.

If you reduce $X$ to $Y$, you're showing that $X$ is no harder than $Y$ and that $Y$ is at least as hard as $X$.

So, by showing that some problem $X$ reduces to the halting problem, you're showing that $X$ is no harder than the halting problem, i.e., that it's recursively enumerable. Remember that we normally define problem classes to include all lower classes, so showing that $X$ is RE doesn't necessarily imply that it's not recursive, for example. In this case, we can separately prove that the blank halting problem isn't recursive, by reducing the halting problem to it, which shows it's at least as hard as the halting problem, as above.


Expressing statements on elephants in propositional logic If I wanted to create a sentence like:

  African elephants can carry coconuts; Asian elephants cannot.

How would I do that with propositional logic?

If you're willing to consider predicate logic (with predicates and quantifiers), there's a plausible way to express this.  Let $P(x)$ stand for the proposition "$x$ can carry coconuts".  Let $S$ denote the set of African elephants and $T$ denote the set of Asian elephants.  Then one interpretation of your sentence is

$$\forall x \in S . P(x) \quad \land \quad \forall y \in T . \neg P(y).$$

Propositional logic doesn't allow quantifiers or predicates; I don't see any reasonable way to express that sentence in pure propositional logic.

Important caveat:  logic is not a way of encoding all English sentences.  It is not intended as a model of conversational language.  Rather, it is a way of making precise certain mathematical subjects, and supporting a particular type of mathematical reasoning.  So don't expect it to be more than it is.


How to choose waiting process in a preemptive priority-based scheduler If my CPU schedule is preemptive priority,
and I have no new processes coming, how I should choose from the waiting processes?

“Preemptive priority” is a property of a scheduler, it is not a complete specification. Under preemptive priority scheduling, you choose the waiting process that has the highest priority. If there are multiple process with that priority, knowing that the scheduler is preemptive priority-based isn't enough to know what it will do. If you want to completely describe a scheduler, you need to specify that case as well.

Two common choices that are used together with preemptive priority-based scheduling are preemptive round-robin (interrupt processes after a certain time if another process with the same priority is ready) and non-preemptive round-robin (a ready process is only ever interrupted by a higher-priority process). But there can be more complex algorithms as well.


Find total number of assignment in the worst case? I have this algorithm

Algorithm (A[1..n])
    for i <- 1 to n do
        if (A[i] < 0) then
            A[i] <- 1 * A[i]
        End if
    End for

I have to find the total number of assignment in the worst case, but I'm a little bit confused, do I say I have 2 or 1, one for the assign A[i] in the statement and second for the i in the for loop (i <- 1).

Likely the question is asking you to focus on line 4, in which you assign a value to A[i]. You can also focus on the for-loop with and its control variable to get a complete answer, but the only way to know for sure is to ask the person responsible for the problem.

Anyway, more precisely, the question is how many assignments do you do in the worst case as a function of the array length $n$. As you can see, this number is determined by the number of times the preceding if-branch evaluates to true. Your task is to argue how many times that can happen in the worst case.


Is there a PDA for every Type 3 Grammar? we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset of type 3 grammar. Am I wrong?

You need to check the definitions: type-3 (regular) is a (proper) subset of type-2 (context-free). Therewith, every type-3 language has a PDA that accepts it.

Essentially, you take a finite automaton for your type-3 language, add the stack but never use it. Up to minor definitory differences (e.g. w.r.t. acceptance), this gives you a PDA for the language. This is also one way to prove that all regular languages are context-free!


Homomorphisms and isomorphisms in an equational calculus Suppose we have an algebraic specification in the form: $\{S,F,w\}$ where $S$ are the sorts, $F$ are the functions and $w$ are the set of equations.
For example, the specification for natural numbers:

$S = \{\mathrm{int}\}$
$F = \{
         0: \mathrm{int}, \;
         \mathrm{succ} : \mathrm{int}\rightarrow\mathrm{int}, \;
         \mathrm{pred}: \mathrm{int}\rightarrow\mathrm{int}
       \}$
$w = \{
         \mathrm{succ}(\mathrm{pred}(x)) = x, \;
         \mathrm{pred}(\mathrm{succ}(x)) = x
       \}$

My question is, why and where do we need homomorphisms and isomorphisms in this case? How do homomorphisms and isomorphisms look like between algebras ?

Can you come up with two different algebras, say, one where the domain is $\mathbb{N}$ and one where the domain is $\{0,1\}$ and in the former, suc and pred work as you would assume, and in the latter, they are modulo 2 operations?  Then, try to come up with a homomorphism from one to another.

Then, try to make an algebra, where the domain is $\{0, s0, ss0, sss0, \dots\}$ and define suc and pred as you would guess.  Make an isomorphism from this one to the one with $\mathbb{N}$ as domain.

Finally, you can make the "term algebra", which has as domain all strings that are valid "terms", i.e.: "0" is in the domain, and for every element $t$ in the domain, "suc($t$)" is in the domain, and "pred($t$)" is in the domain.  Their interpretation is simply that the constant 0 maps to the string "0".  The term pred(suc(suc(suc(0)))) maps to the string "pred(suc(suc(suc(0))))".  Now, you might have a hard time making an isomorphism from this to the standard algebra (the one with $\mathbb{N}$), since "0" and "pred(suc(0))" should both map to 0.

I'm not sure exactly what you ask for, but these two tasks should get you started, at least.


What will be the Turing machine to show that the function $T(n) = n$ is time constructible? Specifically, we need a Turing machine that on input $1^n$ outputs binary representation of $n$ on output tape in $O(n)$ time. I am not able to get any thing better than trivial $O(n \log n)$ time. Any hints or solution?

You almost certainly have the right machine: just implement a binary counter and increment it once for each character of the input.

What you need is a more sophisticated analysis of the running time. You've presumably reasoned that the counter will end up with $\log n$ bits, you need to increment it $n$ times and each increment could change all the bits, so there are $O(n\log n)$ operations.  This is completely correct but you can do better.

Suppose the current value of the counter is even. How many bits do you have to change to increment the counter? How often do you need to change more than two bits? How often do you have to change all $\log n$ bits to increment the counter?


The complexity of checking the correctness of the problem solution on the Turing machine There is a powerful simulation of Turing machine. At the input it takes problems of class P. At the output it gives solution for the problem. So, is it easier (in complexity theory) to test the correctness solution of the given problem than to solve this problem? If checking the solution is really easier than solving the problem, how much?

The practical side of my question is based on the fact that there is a large network of distributed computing. People for the award offer the power of their computers (their GPUs) to solve various problems from other people (from customers). We need an effective algorithm of protection against fraud when a person sends the wrong solution. If checking the correctness of the solution is really much easier than solving the problem, the customers themselves could easily check on their computers the correctness of the sent answers for which they pay. The most common problems are related to the solution of linear homogeneous integral equations and solved in a fraction of seconds, but in general the problem can be any of the class P.
Thank you! I really hope for an answer.

What you might be looking for is an application of probabilistically checkable proofs (PCPs) for verifying computation. People have been working lately on making this practical, see for example Computational integrity with a public random string from quasi-linear PCPs, and other works by Eli Ben-Sasson and Alessandro Chiesa. At the moment this is unfortunately still a mostly theoretical concept.


How to prove Halting problem is solvable by oracle machine How can we prove that the Halting problem is solvable by a machine with access to some oracle?

An oracle machine is a regular machine, such as a Turing machine, with an attached device that is an oracle.  This oracle, often called a black box to signify that it is not constructible in the real world, answers questions about some set.

For instance if the oracle is a $K$ oracle then it can answer yes or no whether numbers are in the set $K$ (I'm taking $K$ to be the name of the set of natural numbers $e$ such that Turing machine $e$ halts on input $e$).  So obviously the Halting Problem can be solved by a machine that has access to this oracle.


Cardinality of formal languages Given the theorem:
Let $\Sigma$ be an alphabet. The set $\mathcal{P} \left( \Sigma^{\star} \right) $ is uncountable.
In other words, there are uncountably infinite languages over any alphabet.
Can someone explain to me how does it hold for $| \Sigma | = 1$ ?

The thing you need to remember is that even if Σ has only one symbol , Σ* still has infinite strings over that one symbol , even if Σ = {a} , Σ* = {ε,a,aa,aaa,....} , (a^n , n≥ 0) , Σ* has infinite strings just like with any other alphabet , and so we can form infinite languages over an alphabet with a single symbol just like other alphabet , if now you are convinced that Σ* is infinite even if |Σ|=1  just like any other alphabet , then just as you believe that P(Σ*) for  |Σ| >1 is uncountably infinite , hopefully you can see now that P(Σ*) for |Σ| = 1 is also uncountably infinite , since in both cases it is P(some infinite language) , which in both cases is uncountably infinite


Misunderstanding of proof with transitivity of logspace reduction I read a commonly known proof of transitivity of logspace reduction:
Lemma 6.: http://www.cs.au.dk/~arnsfelt/CT10/scribenotes/lecture5.pdf
.  In this proof it is used following trick: Let some turing machine $M_f$ for language $f$ compute only $j$-th bit of output.  Ok, $M_f$ is logspace machine, however tape with output can require $O(n)$ space. Hence, we can't get $j$-th  bit in such easy way.

Where am I wrong ?

$L_f$, by definition, gives you the output of $f(x)$ for a single bit $j$. Note that we do not have to copy $x$, so we're only storing $bin(j)$ and the $j$-th bit of  $f(x)$, which is in logarithmic space. Since $M_f$ computes $L_f$ with logarithmic space, we can simply get the $j$-th bit. This means that $M_h$ can work in logspace in total, as it only asks and stores a single bit of input from $M_f$ every time.


Why are long block lengths commonly assumed/used in channel coding proofs? As the title states, why are long block lengths commonly assumed or used in channel coding proofs?

One reason is that this allows a small fixed overhead per block.  With a sufficiently large block, the effect of this becomes minimal (it's amortized out over the length of the block).


Approximation Algorithm for the Unique Coverage Problem I was reading about the $\mathcal{O}(\frac{1}{\log n})$ approximation algorithm for the Unique Coverage Problem from these notes.

The gist of the algorithm is as follows:

  Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
  Let $i$ be the class of the maximum cardinality.
  Choose any set with probability $\frac1{2^i}$

Then in Lemma 3, they go on to show that

  Lemma 3: The expected number of the elements uniquely covered from class $i$
  is $\frac{1}{e^2}$ fraction of the element in class $i$.

I was able to follow the algorithm till here but I am completely stumped as to how they arrived at the statement immediately following lemma 3

  Therefore, the total profit of uniquely covered elements is at least
  $\frac{1}{e^2 \log n} \times \text{opt}$

How did they arrive to this conclusion? They didn't even show what the upper bound is for this maximization algorithm. What am I overlooking?

It is trivial to prove that the expected number of unique elements covered by the algorithms is $\frac{n}{e^2}$ since it directly follows Lemma 3 but that is about all that I am able to observe :/

Suppose there are $m$ elements and $n$ sets (this is the meaning of your parameter $n$). The algorithm divides the set of elements into $\log n$ classes, so one of these classes, say class $i$, contains at least $m/\log n$ elements. Lemma 3 shows that if you pick each set with probability $1/2^i$, then in expectation you uniquely cover a $1/e^2$ fraction of the elements in class $i$. Thus, you uniquely cover at least $m/(e^2\log n)$ elements in expectation. On the other hand, the optimal cover uniquely covers at most $m$ elements. Thus the approximation ratio of this algorithm is at least $1/(e^2\log n)$.


Inorder Successor in Binary Search Tree This is the problem that I have to solve:

  given a node in a binary search tree, find the node
  with the smallest key that is greater than the key of the given
  node..

The algorithm that is often given is this one:

bst_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x = y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

(you can find further explanations of the problem here.)

Now, I was wondering if this can be another solution:

bst_successor(x)
    {
            if(x == NULL)
                    return NULL;
            if(x.right != NULL)
                    return abr_min(x.right)
            y = x.p;
            while(y != NULL && y.key < x.key)
            {
                    y = y.p;
            }
            return y;
    }

Your code is correct if the key of one node is never equal to the key of a different node.

Otherwise, you code fails to return the correct inorder-successor of the node at the bottom of the following graph.


resource on translating imperative programs to functional programs I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional program/style I mean one in which all objects are immutable and functions are pure, and so forth.

The only example I've seen so far of translating imperative code to functional code is for highly specific and simple code. In particular, the example that seems to be used a lot is the factorial function, and translating iteration into recursion:

//imperative -- iteration
int factorial (n)
   for i=1;i<n;i++
      x=x*i;
   end for
   return x;

//functional -- recursion
int factorial (n)
    if (n==1) return 1; else return factorial (n-1) * n

However, this is such a specific example of a function (the factorial), that it doesn't make it clear to me how in general to translate core constructs in imperative style to functional style. e.g. can we always translate a for loop into recursion?

I'm looking for a comprehensive textbook or other resource that in generality shows how to translate imperative code to functional code

How do we translate the basic building blocks of imperative code to functional code? Can we even do this in general?
How do we translate some examples of not-completely-trivial (e.g. not the factorial function) programs?
Especially interesting, are there fully general automated algorithms for doing these translations? Are they actually used? I can imagine that some compilers do something like this.
(perhaps also interesting, the opposite, translating functional code to imperative code.)

There probably are automated ways of doing it, but the result will be a unreadable mess. You have to understand what the imperative program is doing and rethink it as a functional program. Not easy.

The point is that many imperative algorithms have a recursive idea behind them (think binary search, mergesort, quicksort, any tree walking), there it is recognizing that starting point and write it functionally.

First rule I try to impress on my students: Programs aren't for the computer's consumption, they are principally for ḧuman understanding. Humans will have to write it, and modify it if it turns out wrong (be it a bug or a change in requirements). Today the human's time is much more valuable than the computer's (How much does a computer cost? How much does it's time cost, assuming a life of two years? Take any random program, how often will it have to be run to make up for your salary of a week, if that is what it takes to make it twice as fast?).


Are there algorithms for proving two finite state machines are equivalent? Suppose we call two finite state machines equivalent if they "perform the same computation" - they accept the same language, or they produce the same output for any given input. Is there an algorithm for checking if two finite state machines are equivalent?

Given two deterministic finite automata $A_1,A_2$, you can construct the product automaton $A_1 \times A_2$ using the product construction. Let a mixed state be one which is accepting in $A_1$ and rejecting in $A_2$, or vice versa. The two automata are equivalent iff no mixed stated is reachable from the initial state.


Example of unrestricted grammar which produces non-context-sensitive language I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$.

I can not find any example of real unrestricted grammar which produces a non-context-sensitive language (of words). While there are examples of non-context-sensitive languages like here or here, there are not examples with proper grammars for them. Could somebody provide such example?

(Ideally if you would provide links to corresponding papers where such example(s) are described).

Note: I've tried to build unrestricted grammar for known universal Turing machines, as it was suggested in commentaries above. I've used JFLAP tool for this purposes. But obtained grammars appear to be extremely huge, incomprehensible and complex. If you would use same approach and give clear explanation of result, this would partially suit me. Thanks.

For posterity.

Start with undecidable Post Correspondence Problem, or PCP:

  Given two lists of words $(u_1,\dots,u_n)$ and $(v_1,\dots,v_n)$ does
  there exist a sequence of indices such that $u_{i_1}\dots u_{i_k} = v_{i_1}\dots v_{i_k}$?

The language will consist of PCP over $\{a,b\}$ that have a solution, coded as string $(u_1;v_1) \dots (u_n;v_n) $ with $u_i,v_i \in \{a,b\}^*$.

The grammar will generate a PCP instance, and non-deterministically an attempt for a solution. Then equality of the two strings is tested by deleting matching letters.

The equality check is more easily done when one of the strings is stored in reverse, so we will generate $u^R_{i_k} \dots u^R_{i_1} X v_{i_1}\dots v_{i_k}$.

Generate an instance of PCP.

$ I \to (W;W) I \mid (W;W) $ (add a pair of words)
$ W \to a W \mid b W \mid \varepsilon $ (generate a word)

Copy one of the pairs of PCP and move it to the pair of words around $X$ that should be equal.

$ D \tau \to \tau D$ for $\tau = a,b,(,),;$
$ D ( \to ( L $  (pair selected)
$ L ; \to ; R $
$ R ) \to ) $
$ L \sigma \to \sigma L_\sigma L $ for $\sigma = a,b$ (make a copy)
$ R \sigma \to \sigma R_\sigma R $ for $\sigma = a,b$
$ L_\sigma \tau = \tau L_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$ (move right)
$ R_\sigma \tau = \tau R_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$
$ L_\sigma X \to \sigma X$  (drop copy to the left of $X$, it will
reverse)
$ R_\sigma X  \to X \sigma$  (drop copy to the right of $X$)

Check equality

$ X \to Z $
$ \sigma Z \sigma \to Z$  for $\sigma = a,b$

Start. The $\#$ marks the end of the string, or rather the end of the solution that is generated. The last rule will delete it and at the same time test whether the solution has been completely removed by the earlier rules checking equality.

$ S \to C I X \#$
$ C \to C D \mid D $  for generating the solution, copy several word pairs

Done

$ ) Z \# \to )$

PS. Most constructions for a non-context-sensitive language use diagonalization on context-sensitive grammars to get a language that is still recursive. This one is not recursive, but recursively enumerable.

Indeed many rules are context-sensitive (or rather monotonic/non-contracting). But especially note the rules like $aZa\to Z$: they shorten the string. These are definitely type-0 and not monotonic, and they are essential. After the computation they delete the proposed solution of PCP. Like a scratch tape used by a Turing machine.

PS2. Although the intuitive meaning of each of the productions is explained above, it is not very simple to formally prove the grammar is correct. This is mostly due to the parallellism. There are many nonterminals moving around in the grammar at the same time independently (for instance, when a copy of a PCP pair $(u_i,v_i)$ is made all these letters move in a row to the right; also we can start looking for the next pair to copy even before the last one was finished). This makes it hard to formulate invariants. It takes some time to check that all nonterminals keep in a proper order, for instance. Fortunately none of the moving nonterminals can overtake one another.

For this reason analysing Turing Machines sometimes is less complicated. Only the reading/writing head is moving around.

Example (added by Andremoniy)

Consider simplest case: $(a;a)$. For this string derivation sequence will be:

$S\Rightarrow CIX\Rightarrow D(W;W)X\Rightarrow C(a;a)X\Rightarrow D(a;a)X\Rightarrow (La;a)X\Rightarrow (aL_aL;a)X\Rightarrow (aL_a;Ra)X\Rightarrow (a;L_aRa)X\Rightarrow (a;L_a aR_aR)X\Rightarrow (a;aL_aR_aR)X\Rightarrow (a;aL_aR_a)X\Rightarrow (a;aL_a)R_aX\Rightarrow (a;a)L_aR_aX\Rightarrow (a;a)L_aXa\Rightarrow (a;a)aXa\Rightarrow (a;a)aZa\Rightarrow (a;a)Z\Rightarrow (a;a)$


Find close pairs of real points in a set Given an array $S$ with $n$ real numbers. Design a linear time algorithm that finds $x,y \in S$ such that that $|x-y| \leq \frac{max(S)-min(S)}{n-1}$.
I was thinking that it is similar to the closest point problem but that can only be solved in O(nlogn).
Please help

Hint: by the pigeon principle, if $n$ pigeons have to go into $n- 1$ holes, at least one hole has two pigeons in it. Now let your pigeons be numbers, and make sure that if two numbers go in the same hole, they solve your problem.


Divide numbers into fewest groups with each group's sum bounded We have an integer $K$ and an array of $N$ positive integers each smaller than $K$. How do we group the numbers into the minimum number of groups where the sum of each group is less than or equal to $K$?

As comments suggested it is called the Bin Packing Problem.


Creating admissible heuristics from functions? I'm having trouble figuring out how to create admissible heuristics from cost functions.  For example, if I was trying to create an admissible heuristic from a cost function that takes in starting position and ending position and returns the cost based on differences in height, I don't understand how to create an admissible heuristic from such a basic function.

Any help would be greatly appreciated.

Most beginners in the field see heuristics construction more as an art than a science. While I am not claiming here that there is a truly scientific (or even computable) method to derive them, I am sure they are not an art and we know about specific procedures to derive them (some of which are truly computable). In any case, we do not consider the differences in cost between the goal and start states as you suggest in the question. In all cases, admissible heuristics are obtained after relaxing any component in the problem formulation.

Let me just introduce you to three different methods to compute admissible heuristics: constraint relaxation, pattern databases and max heuristics. First, I will just introduce the overall idea. Next, I will provide further details of every technique. I will try to mention also some of the most relevant works that went along any of these lines including merge-and-shrink and Linear Programming.

In all cases, I will refer to the definition of state spaces which consist of two main ingredients:

States: they are defined by any structure that represents the contents of either the start or final state (denoted as $s$ or $t$ respectively) or any other configuration.
Operators: computable functions that are used to derive the immediately reachable descendants of a given state

Also, I will be using the $N$-puzzle as a running example. The proper definition of a state space in the $N$-puzzle is as follows:

States: they are defined by a permutation $\pi$ of symbols such that $\pi[i]$ represents the contents of location $i$
Operators: there is only one move (i,j) which swaps the contents of locations $i$ and $j$ provided that $\pi[i]=0$ (i.e., the blank location) and that $i$ and $j$ are either vertically or horizontally adjacent.

Please, be aware of the following: these techniques are not so simple that I could fully explain them in detail in a single response so that, unfortunately, my explanations will be rather incomplete

Constraint relaxation [Judea Pearl. Heuristics. Addison-Wesley, 1984] Judea Pearl proposed to pay attention to the constraints of the problem (and there should be some, otherwise we would not have an optimization problem), and then to relax a subset of them so that the resulting problem could be optimally solved. The optimal cost of the so-called relaxed problem can be easily proved to be an admissible estimate to reach the goal state. The constraints are usually found (but not only) in the pre-conditions implemented in the operators.

Take the $N$-puzzle. In this case, the constraints are found in the operator move. How would you program such a function? Well, most likely you would verify that $\pi[i]=0$ (i.e., $i$ is the blank location) and that $i$ and $j$ are either vertically or horizontally adjacent locations. Now, select either one of these constraints or both and relax them.

For example, relax both and consider now the resulting (relaxed) problem. For any state, how many moves does it take to get to the target node? If you are not constrained (and this is the point) to consider adjacent locations or the fact that you have to move the blank then you can swap any pair of locations. The optimal solution of the relaxed problems consists just of swapping the misplaced tiles.

Another example, relax only the first one. In this case, you are forced to swap adjacent locations but you are free to ignore the role of the blank tile. Clearly, the optimal solution consists of the sum of the minimum number of horizontal and vertical moves to place every misplaced tile in its goal location. This is known as the Manhattan distance.

In general, the heuristics that relax less constraints produce better estimations and are prefered.

Pattern databases [Culberson, J. C., Schaeffer, J. 1998. Pattern Databases. Computational Intelligence 14(3): 318-334] Constraint relaxation is just a general procedure that you, as an optimizer, have to follow in order to derive an admissible heuristic that you hard-code in your programs. Pattern databases are, instead, computable means to derive automatically the heuristic value of a lot of different configurations which are then stored in a large table.

I will not go here through more detailed explanations and I do suggest you instead to have a look at Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle I am also providing a reply there but I do strongly suggest you to have a look at the response by Shashwat which is more detailed and uses the $N$-puzzle instead for explaining the main ideas. If you are interested in getting the source code for creating Pattern Databases, please e-mail me (carlos.linares@uc3m.es).

In case you are interested in the current state of the art of admissible heuristics in Automated Planning (introduced next) I do recommend you to have a look at merge-and-shrink (which do generalize Pattern Databases). A nice discussion is offered in: Malte Helmert, Patrik Haslum, Jörg Hoffmann and Raz Nissim. Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces. Journal of the ACM. 2013 (which was accepted at the time of writing but has not seen the light yet as far as I know).

Also, there has been some work on using Linear Programming Tasks to get the optimal cost of the relaxed problems:

A. J. Coles and A. I. Coles. LPRPG-P: Relaxed Plan Heuristics for Planning with Preferences. Proceedings of the Twenty First International Conference on Automated Planning and Scheduling (ICAPS-11). June 2011. They do use Linear Programming Tasks to satisfy numeric preferences.
Florian Pommerening, Gabriele Röger, Malte Helmert and Blai Bonet. LP-based Heuristics for Cost-optimal Planning. ICAPS 2014. To appear. This is a work that continues previous work (by the three first authors) for deriving tighter better informed values when using Pattern Databases as discussed here. The idea is really beautiful and this deserves (imho) a lot of attention.
Blai Bonet and Menkes van den Briel. Flow-based Heuristics for Optimal Planning: Landmarks and Merges. ICAPS 2014. To appear. This work is somehow related to the previous one but relates to merge-and-shrink as discussed here.

(NOTE: all this people are really nice, so that if you contact them to get a copy of the paper to appear it is very likely that they will send it to you. The other option is to wait for ICAPS 2014 to take place and then to download the papers: they are absolutely free).

Note please that, in this context, Linear Programming Tasks are used just to derive optimal costs of the relaxed problems precisely in the same way noted by Raphael: you first relax some constraints (according to any procedure) and then you set up a LP task to derive the optimal cost. I do fully believe that this is a hot topic in the field that will get more and more attention.

Max heuristics [Blai Bonet and Héctor Geffner. Planning as Heuristic Search: New Results. Proc. 5th European Conf. on Planning (ECP). Durham, UK. 1999. Springer LNCS 1809. Pages 359-371] The two previous methods for deriving (either automatically or not) admissible heuristics were motivated by the need of creating domain-dependent solvers. However, what if you want to create a single solver that is expected to optimall solve any problem (with some constraints, of course, and not just saying that "The Answer to life, the universe and everything is 42" :) )? This field is known as Automated Planning In this case we relax the reachability analysis by ignoring the delete effects (i.e., the fact that when swapping two locations they are removed from their initial locations; indeed, they are preserved so that the same tile appears in various places at the same time in the relaxed problem).

We just assume that all actions can be executed in parallel and compute the minimum cost to reach every literal (i.e., any atomic observation of our state formulation such as tile 6 is in location 2) from any other literal. You can certainly assume that actions have to be executed in sequence. In this case, the resulting heuristic is known as h add but it is not admissible so I left out of the discussion.

I am just leaving a lot of details out of the discussion here and I do recommend you to have a look at the paper I am just referencing. This is a simple, very simple idea.

Hope all of this helps,


Algorithm for arranging elements into different sized buckets I have a set of items. For each item, there is a list of buyers I can sell it to and a corresponding price they will pay me. For example:

item1:        item2:       item3:       item4:
  john: 17      john: 19     bob:  42        ...
  bob:  23      mick: 22     mick: 44
  sue:  19      liz:  24     sue:  38
  liz:  20                   joe:  45

I need to assign each item to one buyer so as to maximise the amount of money I make. If it were as simple as this, the assignments would go

item1: bob
item2: liz
item3: joe
          ...

However, I also need to try to meet quotas of items for the buyers.

So these quotas might be:

bob:  99
sue:  30
john: 45
        ...

i.e. I need to sell a total of 99 items to Bob, 30 to Sue etc.

The quotas will not cover all items, so it could be that of a total of 1000 items, only 800 are forced to follow the quotas and the remainder can go to whichever buyer pays the highest amount.

The problem then, is to assign the items in such a way as to maximise revenue while still filling the quotas.

In some cases it will not be possible to meet the quotas because not every item can be assigned to every buyer - for example, if there were only the 3 items above and Joe had a quota of 2, I wouldn't be able to meet it as only item3 can be sold to him. It seems to me two types of solution are available in this case, either of which I'm open to.

Find a solution that minimises the number of unfilled quota positions and maximises revenue.
Run a preliminary algorithm that checks if the quotas are fillable. If they aren't, simply fail at that point (under the assumption that some user will then manually tweak the quotas and run the process again). If they are, then find a solution that fills them and maximises revenue.

I've thought of a few strategies, but none that has the mathematical rigour I'd like.

Also, I'm not really sure what flavour of problem this is, so if anyone can suggest a better title for this question, feel free to edit :)

For context, this is a work-related requirement for an energy broker that wants to assign customers (the 'items' in my example) across its pool of energy suppliers.

Edit: If this can be thought of as a form of the Generalized Assignment Problem (as per @fade2black's) answer, it may be helpful to tweak things in this way: items that can't be sold to a particular buyer are assigned a revenue of 0 with respect to that buyer.

So in other words, every item can be sold to every buyer, but some have a revenue of 0. Presumably any optimisation algorithm will then tend to filter these 0-revenue combinations out.

Your problem can be solved in polynomial time.

You mention two possible goals and say you'd be happy with a  solution to either.  The first goal isn't well-defined, so I'll describe a solution to the second goal.  I can see two possible approaches: (a) use integer linear programming (ILP), (b) use network flow.  The former will be simple to implement, and is flexible (if you later have new constraints it'll be easy to add them), but if you're unlucky, the running time could be exponential.  The second has the advantage of running in polynomial time, but it might be more work to implement.  fade2black described the ILP approach well, so I'll describe the network flow approach.

To solve the problem with network flow, formulate this as a minimum-cost network circulation problem.  In network flow, each edge has a capacity: an upper bound on the amount of flow through that edge.  Minimum-cost circulation also allows you to specify a lower bound on the amount of flow through that edge, and the per-unit cost of sending flow through that edge.

We'll construct a directed graph with a source node $s$, a node $u_i$ for each item, a node $v_j$ for each buyer, and a sink node $t$.  Add edges $s \to u_i$ with cost 0, lower bound $1$, and upper bound (capacity) $1$.  Add edges $u_i \to v_j$ with cost equal to the negative of the amount buyer $j$ will pay for item $i$, lower bound $0$,  and upper bound (capacity) $1$.  Add edges $v_j \to t$ with cost 0, lower bound equal to the quota for buyer $j$, and upper bound $\infty$.  Finally, add an edge $t \to s$ with cost 0, lower bound 0, and upper bound $\infty$.  Now look for the minimum-cost circulation in this graph.  That will correspond to a solution that maximizes the revenue, subject to the requirement that all quotas must be filled.


Best way we know search for an integer Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?"

My question is about the best way we know in terms of time/space to answer this query. Ultimately, the time should be guaranteed (not randomized) and the space must be polynomial of $n$.

Firstly, one can use let's say 2-3 Trees or another type of search trees to do this in $O(log n)$ time and $O(n)$ space.

Secondly, one might say that it can be done in $O(1)$ with hashing, however I should note that this time is random and we are looking only for deterministic algorithms. Universal hashing requires a lot of space.

So, one way to approach the main question is to answer if there is a perfect hashing constructable in poly-time and poly-space?

Another approaches are also appreciated. Thanks.

A very simple solution if your integers are not too big, let's say biggest integer is $U-1$ and there are $U$ different integers (between 0 and $U-1$), is to build a table T (bit matrix) of size $U$ with all bits set to $0$. Upon occurrence of item $k$ set $T(k)\leftarrow 1$.

If you want to search for an item $k$ you simply check if $T(k)$ is $1$ or $0$.
This solution takes $\Theta(U)$ space and $\Theta(1)$ time per inserted item, or per search.
If $U$ is much less than $n$ and you don't make deletions then I think
this solution is ideal in your case. If you make deletions of $U > n$ then more sophisticated solutions are needed


Negation of 8-bit hexadecimal I am looking for a mathematical formula / algorithm to find the negation of a 8-bit hexadecimal without having to expand into a binary form.

E.g;

0000BDDA -> 48602

FFFF4226 -> -48602

Need to get from 0000BDDA -> FFFF4226 without 2' complements / expanding it to binary.

I've been cracking my head at it but to no avail.

Any ideas?

Use the same formula as you do for two's complement. First, compute the complement of the number by complementing all letters. Then add 1. Complementing works using the following table:
$$
0 \leftrightarrow F, 1 \leftrightarrow E, 2 \leftrightarrow D, 3 \leftrightarrow C, 4 \leftrightarrow B, 5 \leftrightarrow A, 6 \leftrightarrow 9, 7 \leftrightarrow 8.
$$
Example: starting with 0000BDDA, we first get FFFF4225, and after adding 1, we get FFFF4226.

Why does this work? Exercise.


Difference between algorithm and procedure I came to know that the important difference between algorithm and procedure is that the algorithm halts and procedure doesn't halts(stops). But i am not able to understand the concept. Please can any one explain with the example?

Let me cite the classic -- D.E. Knuth's "The Art of Computer Programming", 3ed (1997).

Some terminology first.

  The modern meaning for algorithm is quite similar to that of recipe, process, method, technique, procedure, routine, rigmarole, except that the word "algorithm" connotes something just a little different.

Note: the bold face is mine.
Then Knuth goes on:

  A procedure that has all of the characteristics of an algorithm except that it possibly lacks finiteness may be called a computational method.

It turns out that one of the earliest examples of a computational method belongs to Euclid:

  Euclid originally presented not only algorithm for the greatest common divisor of numbers, but also a very similar geometrical construction for the "greatest common measure" of the lengths of two line segments; this is a computational method that does not terminate if the given lengths are incommensurable. Another example of a nonterminating computational method is a reactive process, which continually interacts with its environment.

It seems that by the second case Knuth meant operating systems, web-servers and so on, i.e. the programs that are supposed to run "forever", but do something useful along the way.


Maximum flow with maximum flow on specific edge I am trying to solve the following problem:

We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,v)$ also.

The idea that I had was, computing max flow and on the residual graph trying to compute a cycle that starts from $s$ and passes through the edge $(u,v)$ and trying to increase $(u,v)$'s flow while decreasing the flow from other edges. In other words, trying to maximize the flow of $(u,v)$ while preserving the maximum flow value. But I feel like there's a simpler way.

Can someone point me in the right direction? Is my thinking correct? If not how should I approach the problem?

Any help is appreciated! Thanks!

I would do it kind of the other way around as you suggested.

First compute a flow that saturates $(u,v)$. This can be done with the Ford--Fulkerson algorithm. Look only for augmenting paths which contain $(u,v)$ and augment the flow until the edge is saturated.

In the second step you augment further, but avoid the edge $(u,v)$ when searching for augmenting paths in the residual network. There is no reason to desaturate $(u,v)$. If we desaturate the edge with one path and saturate it with another we can get to the same flow by augmenting with the "product" path which avoids $(u,v)$.

This is not a proof but should guide you in a possible direction how to solve this.


Disprove that a function exists that counts the turing machines that halt on $\epsilon$ Let $L(M_k) = \{ \langle M \rangle | M \text{ halts on }\epsilon \} \cap \Sigma^k $
Disprove that $\exists f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$.

I am not sure where I am wrong:
I said that I can convert the question to whether the language of all the Turing machines that accept the language $L(M_k)$ is decidable,
because if indeed:
$$X = \{ \langle G \rangle | L(G)=\{ \langle M \rangle | M \text{ halts on } \epsilon \}  \cap \Sigma^k \} \in R$$
then there will be enumerator that can count all the Turing machines and therefore there will exist a function from $N$ that will return the description of the Turing machine $M_k$ (the function will be the enumerator).
And I proved why the $X$ is not decidable and therefore the function $f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$ does not exist.
Where am I wrong?

Your question seems to be confusing machines and languages. Define $L_k$ to be the set of encodings of Turing machines of length $k$ that halt on the empty input. The language $L_k$ is finite, and so computable. In particular, there is a function $f\colon N \to \Sigma^*$ satisfying $L(f(k)) = L_k$ (in fact, infinitely many such functions). What you want to show is that there is no recursive function satisfying this property.

The proof is by contradiction. Suppose that there were such a computable function $f$. Now suppose you are given the description $\langle T \rangle$ of some Turing machine, of length $k$, and you want to know whether it halts on the empty input. You compute $f(k)$, and check whether $\langle T \rangle \in L(f(k))$.

Here is a more challenging question: Is the function $g(k) = |L_k|$ computable? (This function gives the number of Turing machines of size $k$ that halt on the empty input.)


Algorithm for grouping identical neighbors in a list I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries.

Example list:

1,1,1,1,1,2,2,2,3,3,1,1,1,2,2,2,2,2,2,2,2,2,4,4,4,4,1,1,1,1,1,1

After 'compression'

1,2,3,1,2,4,1

Is there an algorithm for doing this that is faster than O(n)? In other words, faster than just looking at the next neighbor?

while (1)
    n = 0, m = 1
    if (list[n] == list[m])
        remove list[m]
    else
        n = m
        m = m + 1
    if (m > list.size)
        break

If not, what about this problem makes it O(n)?

You can use an adversary argument (exercise) to show that any algorithm which outputs the correct "compression" must examine all entries in the input, in every case. Such an algorithm cannot run in $o(n)$ on any input.

To answer your question, the reason that this problem requires a running time of $\Omega(n)$ is that the output depends on all entries of the input, in the sense that for every input and every entry there is a way to change the entry that affects the output. (Note, however, that not every change to the input results in a change to the output: for example $1,1,2$ and $1,2,2$ have the same output, but $1,3,2$ does not.)


Amdahl law and parallelism I know after some reading Amdahl law is a embarrassingly parallel programming model. Embarrassingly parallel means there is no communication and tasks work independently. Am I to assume a parallel and a non parallel aspect of the program is embarrassingly parallel?  If not, what makes it embarrassingly parallel?

Your terminology is incorrect.  Amdahl's law is a way of estimating performance of a parallel program.  It is not a "programming model".  Amdahl's law says that if there is a computation, part of which is $M$ sequential (not parallelizable) instructions and part of which is $N$ instructions which could be parallelized, and you have $P$ processors, then the shortest computation time you can hope for is:
$$ M + \frac{N}{P}. $$

So the speedup with $P$ processors is:
$$ \frac{M+N}{M+\frac{N}{P}}. $$

Which, in the limit as $P \gg N$ goes to
$$ \frac{M+N}{M} = 1 + \frac{N}{M}. $$

The takeaway message is simply that you shouldn't fool yourself.  $N/M$ is much more important than $N/P$.


a program discovering himself how to solve propositional calculus it is well-known that propositional logic problems such as

$$ (p\leftrightarrow q)  \lor r \quad\overset{?}{\vdash}\quad (((p\lor q)\to(p\land q)) \land \lnot r)\lor r$$

can be simply solved by evaluating the corresponding boolean functions for the $2^n$ possible values of the $n$ boolean variables (here $p,q,r$).

my question is then : instead of hand-writing such a propositional logic solver, couldn't we search for a program capable of generating such a solver ?

what would be then the minimal core / set of concepts and rules needed for a program being capable of ''discovering'' and ''solving'' the propositional calculus ?

is it a unsolvable artificial intelligence problem, or would it have some nice solutions, helpful for solving the more interesting higher order logics ?

If there are no quantifiers, testing validity of such formulas is equivalent to testing satisfiability of the complement of the formula.  That can be done with a SAT solver.  SAT solvers and the satisfiability problem are well-studied.  So, the minimal set of concepts needed would be: enough to solve SAT.

Statements with quantifiers are harder (QBF).  Higher-order logics are harder still.


Why can't exhaustive search parsing stop after |w| + 1 derivations? If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in the sentential length. Therefore if I do an exhaustive search for some word $w$ then I know I can stop searching after $|w|$ derivations.

My question is why then do textbooks assert that we can stop after $2|w|$ derivations instead? Yes, I agree that this is true, but wouldn't it be easier just to stop at $|w|+1$ and above? What am I missing for this condition?

You increase the length of the sequential form with each derivation, but you also need to convert non-terminals to terminals.

Think of a grammar in Chomsky normal form. For each word symbol, you need to create a non-terminal first (and you create only one per derivation!) and then convert it into a terminal. That's $2|w| \pm 1$ derivations right there.

Yes, CNF is a little wasteful this way, but finding short derivations isn't its purpose, isn't it?


Show that this language is decidable? Let A = {  | M is a DFA which doesn't accept any string containing an odd number of 1s}. Show that A is decidable.
The questions seems simple so I designed the following TM D that decides whether there exists a DFA with this property or not.
D = "On input  w:

Construct a DFA B that accept any string containing an odd number of 1s.
Construct a DFA C s. t. $L(C) = L(B) \cap L(M)$
Call $E_{DFA}$ with input C.
If T accepts, then reject. If T rejects, then accept."

$E_{DFA}$ is defined as following:
$E_{DFA} = \{ <A> |$ A is a DFA and L(A) = $\phi \}$ So assume there is a TM T that decides language $E_{DFA}$. I.e., T accepts if A is empty, otherwise rejects.
Now, my questions is related to the step 4. In Sipser's textbook, he states that if T accepts, then accept and if T rejects, then reject. I don't understand why it says so. For example, If $L(M) \cap L(B) = \phi$, then this means that there are different. So, this is what I said in step 4 above. But in Sipser's answer for this exercise in page 187, it says that if they are empty, then accept. Can you explain to me where is my mistake?

If $E_{DFA}$ with input $C$ accepts, then $C = L(M) \cap B = \emptyset$.
In other words, no word containing an odd number of 1s is also in $L(M)$.
Then, by definition of $A$ you should accept.
Conversely, if  $E_{DFA}$ with input $C$ rejects, then $C = L(M) \cap B  \neq \emptyset$.
That is, there is some word $w \in L(M)$ such that $w$ contains an odd number of 1s. Then, by definition of $A$, you should reject.


Union of right congruence relations Since we started talking about relations on languages and so on i keep on struggling with this subject.

So now iam faced with two questions where i really dont know how to start.

  First of all, the natural relation of a language $L \subseteq \Sigma^*$ is the equivalence relation on $\Sigma^*$ with the equivalence classes $L$ and $\Sigma^* \setminus L$

  Let the natural relations of two arbitrary languages $L_1$ and $L_2$ be right    congruent. Is the natural relation of the language $L_1 \cup L_2 $ also right congruent?

  So a right congruence is a equivalence relation with the added property that:

  $ \forall a \in \Sigma : u \equiv v \Longrightarrow ua \equiv va$

  Intuitively i would say that the union of this two relations remains to be a  right congruence but i dont know how to prove this idea.

  For every equivalence relation $\equiv$, there are at least two languages which are saturated by $\equiv$, true or false?

  An equivalence relation saturates a Language $L$ if: $ u \equiv v \Longrightarrow u \in L \Leftrightarrow v \in L $

  My guess would be that any equivalence relation saturates the Language $L$ and $\bar{L}$

I would be pleased if some one could provide me with a useful hint on how to solve this questions.

I'll walk you through the first question. You can ask the second question separately (see D.W.'s answer).

When faced with a "proof or refute" question like this, we need to try both directions. First, we can try proving the claim. If we seem to get stuck, we can look for a counterexample.

Let's try proving the claim. We are given that $L_1$ and $L_2$ are right congruent. This means the following, for $u,v \in \Sigma^*$ and $a \in \Sigma$:

If $u,v \in L_1$ or $u,v \notin L_1$ then either $ua,va \in L_1$ or $ua,va \notin L_1$.
If $u,v \in L_2$ or $u,v \notin L_2$ then either $ua,va \in L_2$ or $ua,va \notin L_2$.

Let's try to prove that $L_1 \cup L_2$ also satisfies a similar condition. We have to consider two cases: $u,v \in L_1 \cup L_2$ and $u,v \notin L_1 \cup L_2$. The second case looks simpler, so let's start with it. If $u,v \notin L_1 \cup L_2$ then $u,v \notin L_1$ and $u,v \notin L_2$. The assumptions then show that:

Either $ua,va \in L_1$ or $ua,va \notin L_1$.
Either $ua,va \in L_2$ or $ua,va \notin L_2$.

We have to prove that either $ua,va \in L_1 \cup L_2$ or $ua,va \notin L_1 \cup L_2$. We reason as follows. If $ua,va \in L_1$ then $ua,va \in L_1 \cup L_2$ so we're done. Same if $ua,va \in L_2$. The remaining case is $ua,va \notin L_1$ and $ua,va \notin L_2$. In this case, $ua,va \notin L_1 \cup L_2$, so we're again done.

Now let's get back to the other case: $u,v \in L_1 \cup L_2$. This case looks harder. There are many different subcases. Let's start with a simple one: $u,v \in L_1$. In this case we can say that $ua,va \in L_1$ (and then we're done, since $ua,va \in L_1 \cup L_2$) or $ua,va \notin L_1$. What do we do in the latter case? We have to consider membership of $u,v$ in $L_2$. If $u,v \in L_2$ or $u,v \notin L_2$ then either $ua,va \in L_2$ (and then we're done, since $ua,va \in L_1 \cup L_2$) or $ua,va \notin L_2$, in which case we know that $ua,va \notin L_1 \cup L_2$. But what happens if $u \in L_2$ and $v \notin L_2$? Then we seem to be stuck.

Now we switch gears, trying to refute the claim. We got stuck when we had $u,v$ such that $u,v \in L_1$, $ua,va \notin L_1$, $u \in L_2$, $v \notin L_2$. So we try to look for two right congruent languages for which two such words exist. In order to do that, we need first to think of examples of right congruent languages. One very simple example is the language of even-length words. We can enrich the repertoire by taking the language of all words having an even number of some letter $a$.

Here are two examples of this sort: take $L_1$ to be all words with an even number of $0$s, and take $L_2$ to be all words with an even number of $1$s. We can take $u = \epsilon \in L_1 \cap L_2$ (here $\epsilon$ is the empty word) and $v = 1 \in L_1 \setminus L_2$. Since we want $ua,va \notin L_1$, we take $a = 0$. Then $u0,v0 \notin L_1$ while $u0 \in L_2, v0 \notin L_2$. So $u0 \in L_1 \cup L_2$ but $v0 \notin L_1 \cup L_2$, and we have found our counterexample!

As you can see, finding a counterexample is often more creative then proving a statement, which can be quite mechanical. You just need to try a lot of things until something works.

The next step is to reflect on what we have shown. Is there any other operation on two languages which preserves the property of being right congruent? Is there an operation on one language? Indeed, there are: if $L$ is right congruent then so is $\overline{L}$; and if $L_1,L_2$ are right congruent then their symmetric difference $L_1 \triangle L_2$ is right congruent. See if you can prove these claims.

(In fact, right congruent languages are exactly the languages accepted by a DFA with at most two states. This leads to a complete classification of these languages, which I leave to the reader.)


How to prove that a problem can't be solved in time $\mathcal O(n^{1/2 - \epsilon})$? I have seen many problems in graph theory and in other related fields which admit a sublinear (in input size) running time $\mathcal O(n^{1/2})$ algorithm, where $n$ is the input size.  I am not sure but to me it seems that fine grained complexity may be one possibility to prove that there is no algorithm with running time $\mathcal O(n^{1/2 - \epsilon})$, where $\epsilon$ is greater than 0. The model of computation is RAM.

Question : How to prove that a problem can't be solved in running time  $\mathcal O(n^{1/2 - \epsilon})$?

One possibility to get conditional hardness is to give a (fine-grained) reduction from a problem that is known to be hard in some sense. The result will then something along the lines of "if problem X admits an algorithm running in time $O(n^{1/2-\epsilon})$, then problem Y can be solved within some specific time bound". The "specific time bound" should be something we don't know how or believe that can be achieved.

The survey of Williams [1] you refer to contains several examples. As you can see in Figure 1, there are several problems in computational geometry, graph theory, and logic that could be or have been reduced from. Now, for some problems, there is theoretical evidence and belief in the community that the conjectures indeed hold (like ETH). Other ones are less often believed like SETH.

It is an open problem to draw more connections between these problems (see Section 2.6 in [1]), i.e., to find more evidence for hardness other than "here's an isolated problem nobody has been able to find a faster algorithm for decades". For more in this direction, see e.g., this question on CSTheory.

[1] Virginia V. Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis. IPEC 2015 invited talk.


Fine-grained security models for XML data Access control models are typically very coarse-grained, allowing one access to a resource (possibly with some combination of read/write/execute permission) or exclude such access. Some models of database security allow access to be granted on a per row basis (though I don't have a reference handy).

Have fine-grained access control models been designed to limit access to parts of an XML document? What could/should a model look like? Has any work been done in this area? Are other security models applicable in this context?

For example, one could imagine that the model prevents access to a particular subtree. The subtree could either be removed or encrypted.

Note that this need not explicitly apply to XML. Any models devised for semi-structured data are also interesting.

I'm no expert on access control for structured data. This is a 10000-foot view. Don't assume a correlation between what my answer covers, what is scientifically interesting and what is significant in terms of deployment.

Take any access control or permission mechanism and slap some angle braces around it, and you have an XML access control mechanism. It's been done a lot, but it looks like each effort has had little visibility outside the community it originated in.

XACML is a standard (that some people actually use) for specifying access control policies. Some of these policies control data access. I believe the model it uses for actors (PAP, PDP, PEP, PIP) is common in distributed access control systems (for managing data access and otherwise).

XACL (not to be confused with XACL or XACML) is a rich model for access control over elements or subtrees, allowing redaction, encryption and other transformations of content as well as logging.

There's a 2006 survey by Mark J. Estlund. It covers both XML for access control and access control of XML. It's nowhere near complete.

Access Control in Data Management Systems by Elen Ferrari (2010) has a section on XML.