Call‑by‑name will succeeds where call‑by‑value may fails: some example cases? I've landed to SML pages, comparing call‑by‑name and call‑by‑value, asserting the former always succeed while the latter may fails. As this seems counter intuitive to me, I feel at least an example case would be useful.

Call-by-value, call-by-name and call-by-need

  Theorem (Church Rosser 1)

  For a purely functional language, if call-by-value evaluation and
  call-by-name evaluation both yield a well-defined result then they yield the
  same result.

  Theorem (Church Rosser 2)

  If a well-defined result exists for an expression then the call-by-name
  evaluation strategy will find it where, in some cases, call-by-value
  evaluation will not.

What make it counter‑intuitive to me, is that call‑by‑name may re‑evaluate expressions multiple times, which I don't understand how it can make it succeed when call‑by‑value and its one‑time evaluation, would fails. If, as the context is FP and its referential transparency, both expression are supposed to evaluated to the same, how evaluating multiple time may make something succeed or alternatively potentially fails if the same expression is evaluated only once? Unless there are side‑effect somewhere?… is this related to side effects and non‑pure FP?

As a reminder, here is what would look like call‑by‑value and call‑by‑name with SML (if there is an error here, feel free to tell), added call‑by‑need to help not confuse one with the others:

(* This, is supposed to sometime fails… *)

fun call_by_value a =
   a + a  (* `a` is evaluated only once *)

(* …when this is supposed to succeed *)

fun call_by_name a =
   a () + a ()  (* `a` is evaluated for each of its reference *)

(* None of the above should be confused with call‑by‑need: *)

fun call_by_need a =
   let val a' = a ()  (* memoization *)
   in fn () => a' + a'  (* to be evaluated when needed *)
   end

val _ = print (Int.toString (call_by_value 2) ^ "\n")
val _ = print (Int.toString (call_by_name (fn () => 2)) ^ "\n")
val r = call_by_need (fn () => 2) ()  (* memoization *)
val _ = print (Int.toString r ^ "\n")

Call-by-value evaluates the arguments to a function exactly once.  Call-by-name evaluates the arguments to a function, zero, once, or more times.  Call-by-need evaluates the arguments to a function zero or once, but not more than once.

The trick you are looking for here is a case where call-by-value needs to evaluate an argument once while call-by-name does not need to evaluate its argument at all.  The particular thing that Church and Rosser were worried about was that the argument might be an infinite loop.

So if I have the following

fun call_by_name (cond a b) =
  if cond
    a
  else
    b

and

fun loop_forever () =
   loop_forever()

Then

call_by_name(true, 1, loop_forever())

will return 1 while

call_by_value(true, 1, loop_forever())

will loop forever.

Actually, call-by-name is super cool because it allows you to implement control-flow constructs like if-then-else and while-do.  Suppose, for example that your language doesn't have if-then-else built in.  You can implement boolean values True and false and if-then-else in call-by-name as follows:

fun True  (t f) = t
fun False (t f) = f
fun if_else (cond t f) = cond(t f)

Now

if_else(True, 1, loop_forever())

returns 1 and

if_else(False, loop_forever(), 0)

returns 0.


Is the given language decidable? L = { < M > | M is a turing machine and   }

Obviously, the language which L(M) is polynomially reducible to, is context free and hence recursive, so it is a decidable language .

Now, L(M) is reducible to decidable language.

I think this language is not decidable, as this language is non-trivial in the sense of rice theorem, as no recognizable language can be a part of L(M) and even this context free language belongs to L(M).

Is my understanding right ?

Yes, your understanding is right.

The first part (about context-free languages which are decidable) is unneeded. To apply Rice, you only have to show that the property at hand only depends on $L(M)$ (which it does, trivially) and prove that the set is nontrivial. So the whole exercise bogs down to: exhibit $M$ satisfying the reduction property, and $M′$ not satisfying it.

To prove/disprove reduction you may have to use the fact that the language $0^p1^{2p}$ is decidable, as you argued.


Compare-and-Swap in an RDBMS for custom locks and lock escalation I'm applying the Compare-and-Swap technique to a SQL database to create custom row-level locking in my dataset, allowing for safe READ UNCOMMITTED isolation at the database level.

The Resource table includes a LockOwner GUID and a IsLocked BIT field.  To acquire a lock, a dirty-read query gets the ID, LockOwner, and LockStatus.  If Unlocked, attempt to UPDATE the Resource by (ID, LockOwner) with a newly generated LockOwner and LockStatus of Locked.  Abort and start again if no rows are updated - meaning someone else got there first.  Otherwise, the Lock is held in the READ UNCOMMITTED transaction.  The transaction is needed to allow rollback on client failure/abandon, but the dirty reads avoid locks.

This seems to me to work great for resources that are independent of each other.  But what must I add to account for a new kind of lock, ResourceGroup?

ResourceGroup to Resource is a one-to-many relationship.  Resources can be locked individually, but if the ResourceGroup needs to be locked, then all of the Resources must also be locked.

Locking a ResourceGroup is a far less frequent need than locking a Resource, so the scheme should be optimized for Resource queries, avoiding requiring joins to ResourceGroup if possible.

I am imagining a scenario where locking a ResourceGroup involves marking the member rows with some flag, but I'm not sure what scheme doesn't interfere with the original Resource-only scheme.  Part of the problem comes from the UPDATE of a Resource while it is locked (and therefore already UPDATED in another transaction).  I believe that even if the fields are different within the record, the UPDATE will place an UPDATE LOCK on the row, so any lock on ResourceGroup would introduce blocking that we are trying to avoid.  Even if we could do this, how would the ResourceGroup lock acquisition mechanism know when all of the Resources (which may have had locks in process as we began locking their peers) have been released?

There may be differences in this locking granularity by RDBMS, I'm on MS SQL 2005+.

The Prevent race conditions across multiple rows on Stackoverflow seems to be relevant.

Also, I would urge you to use SQL server locks instead of your own lock column (which it sounds like you're doing).

And it looks like doing hierarchical locks is kind of clumsy in SQL, so if you're finding this to be a huge bottleneck you could try a locking service like zookeeper.


Is this special case of a scheduling problem solvable in linear time? Alice, a student, has a lot of homework over the next weeks.  Each item of homework takes her exactly one day.  Each item also has a deadline, and a negative impact on her grades (assume a real number, bonus points for only assuming comparability), if she misses the deadline.
Write a function that given a list of (deadline, grade impact) figures out a schedule for which homework to do on which day that minimizes the sum of bad impact on her grades.
All homework has to be done eventually, but if she misses a deadline for an item, it doesn't matter how late she turns it in.

In an alternative formulation:

ACME corp wants to supply water to customers.  They all live along one uphill street.  ACME has several wells distributed along the street.  Each well bears enough water for one customer.  Customers bid different amounts of money to be supplied.  The water only flows downhill.  Maximize the revenue by choosing which customers to supply.

We can sort the deadlines using bucket sort (or just assume we have already sorted by deadline).
We can solve the problem easily with a greedy algorithm, if we sort by descending grade impact first.  That solution will be no better than O(n log n).
Inspired by the Median of Medians and randomized linear minimum spanning tree algorithms, I suspect that we can solve my simple scheduling / flow problem in (randomized?) linear time as well.
I am looking for:

a (potentially randomized) linear time algorithm
or alternatively an argument that linear time is not possible

As a stepping stone:

I have already proven that just knowing which items can be done before their deadline, is enough to reconstruct the complete schedule in linear time.  (That insight is underlying the second formulation where I am only asking about certificate.)
A simple (integral!) linear program can model this problem.
Using duality of this program, one can check a candidate proposed solution in linear time for optimality, if one is also given the solution to the dual program.  (Both solutions can be represented in a linear number of bits.)

Ideally, I want to solve this problem in a model that only uses comparison between grade impacts, and does not assume numbers there.
I have two approaches to this problem---one based on treaps using deadline and impact, the other QuickSelect-like based on choosing random pivot elements and partitioning the items by impact.  Both have worst cases that force O(n log n) or worse performance, but I haven't been able to construct a simple special case that degrades the performance of both.

A few things I found out so far.

We can reduce ourselves to solving the following related problem:

newtype Slot = Slot Int
newtype Schedule a = Schedule [(Slot, [a])]

findSchedule :: Ord a => Schedule a -> Schedule (a, Bool)

I.e. give the input data already sorted by deadline, but allow an arbitrary non-negative number of tasks to be done on each day.  Give the output by just marking the elements on whether they can be scheduled in time, or not.

The following function can check whether a schedule given in this format is feasible, ie whether all items still in the schedule can be scheduled before their deadlines:

leftOverItems :: Schedule a -> [Int]
leftOverItems (Schedule sch) = scanr op 0 sch where
  op (Slot s, items) itemsCarried = max 0 (length items - s + itemsCarried)

feasible schedule = head (leftOverItems schedule) == 0

If we have a proposed candidate solution, and all items left out, we can check in linear time whether the candidate is optimal, or whether there are any items in the left-out set that would improve the solution.  We call these light items, in analogy to the terminology in Minimum Spanning Tree algorithm

carry1 :: Ord a => Schedule a -> [Bound a]
carry1 (Schedule sch) = map (maybe Top Val . listToMaybe) . scanr op [] $ sch where
  op (Slot s, items) acc = remNonMinN s (foldr insertMin acc items)

-- We only care about the number of items, and the minimum item.
-- insertMin inserts an item into a list, keeping the smallest item at the front.
insertMin :: Ord a => a -> [a] -> [a]
insertMin a [] = [a]
insertMin a (b:bs) = min a b : max a b : bs

-- remNonMin removes an item from the list,
-- only picking the minimum at the front, if it's the only element.
remNonMin :: [a] -> [a]
remNonMin [] = []
remNonMin [x] = []
remNonMin (x:y:xs) = x : xs

remNonMinN :: Int -> [a] -> [a]
remNonMinN n l = iterate remNonMin l !! n

data Bound a = Bot | Val a | Top
  deriving (Eq, Ord, Show, Functor)

-- The curve of minimum reward needed for each deadline to make the cut:
curve :: Ord a => Schedule a -> [Bound a]
curve = zipWith min <$> runMin <*> carry1

-- Same curve extended to infinity (in case the Schedules have a different length)
curve' :: Ord a => Schedule a -> [Bound a]
curve' = ((++) <*> repeat . last) . curve

-- running minimum of items on left:
runMin :: Ord a => Schedule a -> [Bound a]
runMin = scanl1 min . map minWithBound . items . fmap Val

minWithBound :: Ord a => [Bound a] -> Bound a
minWithBound = minimum . (Top:)

-- The pay-off for our efforts, this function uses
-- the candidate solution to classify the left-out items
-- into whether they are definitely _not_ in
-- the optimal schedule (heavy items), or might be in it (light items).
heavyLight :: Ord a => Schedule a -> Schedule a -> ([[a]],[[a]])
heavyLight candidate leftOut =
    unzip . zipWith light1 (curve' candidate) . items $ leftOut
  where
    light1 pivot = partition (\item -> pivot < Val item)

heavyLight not only checks a proposed schedules for optimality, it also gives you a list of items that can improve a non-optimal schedule.


Training given pairs of similar values, not labels I have pairs of "similar" values $(x_i, y_i)$ drawn from a space $x_i, y_i \in S$, and want to train a neural network $N$ such that $N(x_i)$ would be "close" to $N(y_i)$ for all $i$, yet, to make it useful, the overall image of $N$ would be as spread apart as possible. Note that the training data says which values are similar, but does not imply that values from different pairs are necessarily different (i.e. these aren't labels).

Defining a cost function to be something like $\frac{1}{2} \sum_i \| N(x_i) - N(y_i) \|^2$ doesn't work, because $N(x) = 0$ would then be a trivial solution. Another option I considered is to require that, assuming the inputs are distributed with zero mean and unit variance, say, the outputs would be distributed with zero mean and unit variance too. I don't know how to efficiently enforce it though, or whether it would even give good results.

I see it as a kind of unsupervised learning with some "hints" provided.

So, my question is: what kind of problem is this? How to approach it? Can you direct me to any previous similar research?

I'm not convinced that a neural network is necessarily the right tool for this.  When you have a hammer, it's tempting to think that everything looks like a nail... but sometimes the answer is "No, you dummy, that's a screw, use a screwdriver, not a hammer."

So, I'll comment on several kinds of methods you could explore, for your problem.  I suggest you look into them all and see which works best in your specific application.

Clustering

It looks like your problem is basically a clustering problem.  There are many standard algorithms for clustering data.  For instance, if your space is $S=\mathbb{R}^n$, many clustering algorithms are known.  There are also many clustering algorithms known that can work on any metric space.  I recommend you take a look at https://en.wikipedia.org/wiki/Cluster_analysis to familiarize yourself with some of the standard methods, and look to see whether any of them might suit your application well.

Neural networks and autoencoders

If you are set on using a neural network (which, again, might not be the right attitude), an alternative approach might be to learn an auto-encoder for the data.  This is a standard way to use neural networks for unsupervised learning.  This basically asks the neural network to find a way to project high-dimensional data down to some lower-dimensional space, in a way that preserves as much as possible of the structure of the original data.  Empirically, it often seems to be an effective way to do unsupervised learning.

You could train a neural network in this way, and then use it to project your inputs to the lower-dimensional space and measure distances in the projected space.  There are standard training algorithms to fit an autoencoder.

See also https://en.wikipedia.org/wiki/Neural_network#Unsupervised_learning and https://en.wikipedia.org/wiki/Autoencoder.

Metric space embeddings

You might also want to look into the literature on metric space embeddings.  A metric space embedding is a map $f:S \to \mathbb{R}^n$ from a metric space $S$ to $\mathbb{R}^n$, such that $f$ approximately preserves the distance metric on $S$.  In other words, we seek to find $f$ such that

$||f(x)-f(y)||_2 \approx d_S(x,y)$$

for all or most $x,y \in S$.  This is an embedding into $\mathbb{R}^n$ with the Euclidean norm (or into $\ell_2$ if we don't care about the dimension $n$).

There's been a lot of work on this subject, including the computational aspects of learning/finding such embeddings.  See, e.g.,

https://en.wikipedia.org/wiki/Machine_learning#Similarity_and_metric_learning and https://en.wikipedia.org/wiki/Similarity_learning#Metric_learning
Embedding Finite Metric Spaces into Normed Spaces, Chapter 15 of Lectures on Discrete Geometry by Jiri Matousek.
Distributional Scaling: An Algorithm for Structure-Preserving
Embedding of Metric and Nonmetric Spaces.  Michael Quist, Golan Yona.  Journal of Machine Learning Research 5 (2004) pp.399-430.
The CMU course CS 15-859(J): Algorithmic Applications of Metric Embeddings, especially Lectures 1 and 5.
Finite Metric Spaces - Combinatorics, Geometry, and Algorithms.  Nathan Linial.  Proceedings of the International Congress of Mathematicians III, 2002.
The Geometry of Graphs and Some of Its Algorithmic Applications.  Nathan Linial, Eran London, Yuri Rabinovich.  Combinatorica 15(2), 1995.

I'm not an expert on this subject, so there's probably more relevant work out there (e.g., in the machine learning or systems community).


How can I prove algorithm correctness? How can I prove algorithm correctness ?
when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true.
but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases.
So how can I prove mathematically if my algorithm produce the expected output or not ?

For example, consider the program below.

You’re given a read only array of $n$ integers.
Find out if any integer occurs more than $n/3$ times in the array in linear time and constant additional space.

Algorithm:
We will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with its proper count. If we reach the size of count array we decrement one from count of each number. If number count becomes zero it can be safely eliminated from the count array.

Here is an example:

Input: 4 3 3 7 2 3 4 5
count arr (4,1) 4 as first element and 1 is its count till now
count arr (4,1)(3,1)
count arr (4,1)(3,2)
count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes
count arr (3,1). We will proceed with next element in the array which is 2.
count arr (3,1)(2,1)
count arr (3,2)(2,1)
and so on. At the end count arr will be (3,1)(5,1).

We will make another loop to the input array to count occurrence of 3 and 5 and if any one exceeds $n/3$ it will be printed out.

In practice, to prove an algorithm you should search a good invariant property for each loop. For example, if you compute in a given order the sum of $n$ integers with a for loop (indexed by $i$), the invariant could be : "At the end of an iteration, the $sum$ variable contains the sum of the $i$ first values". It's  invariant over iterations number and always true, it's easy to prove this by recurrence on the iterations number. Afterwards you can easily conclude that, at the end of the loop, $i=n$ and thus that $sum$ is the expected sum.

Then, there is several levels of strictness, but for simple algorithms we can generally conclude promptly since the correction of the algorithm becomes almost always trivial with all the loops invariants. A very classical approach is to prove before that the algorithm finishes and after that the algorithm is correct when it ends. For complete examples you can look here. For more subtil algorithms, you can also need some mathematical theorems which provide some links beetween objects.

Your example is very close to Misra-Gries algorithm. You can look for the proof of the Misra-Gries algorithm and try to adapt it or you can try to bound the number of times the count of the most frequent number is decreased.

In general, there isn't a systematic way to find if an algorithm produces the expected output or not. Indeed, this systematic way would be an algorithm and such an algorithm can't exist (Rice's theorem).


How can I define this syntax? I wanted to define syntax for a graph path considering it may branch out anywhere.

For instance, I have a path going from a to e following b, c, d: a, b, c, d, e.

Let's consider it (may) branches from b now: a, b, (x | y), d, e which actually means three different paths:

1) a, b, d, e

2) a, b, x, d, e

3) a, b, y, d, e

So, each parenthesis actually means "the path might either go through any of the nodes defined in the parenthesis connecting the node just before parenthesis and right after parenthesis or through none of the nodes defined in the parenthesis".

With more inner parenthesis, a single string line may generate even more paths. For instance: a, b, (x | (z | t) | y), d, e which means these five paths:

1) a, b, d, e

2) a, b, x, d, e

3) a, b, y, d, e

4) a, b, z, d, e

5) a, b, t, d, e

6) a, b, z, y, d, e

7) a, b, t, y, d, e

8) a, b, x, z, d, e

9) a, b, x, t, d, e

So, how can I define this syntax mathematically?

You are mixing two things here: syntax and semantics.

First, syntax. What is the language of strings $L_P \subseteq \Sigma^*$ with $\Sigma = \{\mathtt{a}, \dots, \mathtt{z}, \mathtt{)}, \mathtt{(}, \mathtt{,}\}$ that describe a set of paths as you specify them? You can specify $L_P$ by the formal grammar

$\qquad\begin{align}
  S &\to T\mathtt{,} S \mid \mathtt{(}S\mathtt{)}S \mid T \\
  T &\to [\mathtt{a}\dots\mathtt{z}]
\end{align}$

Note that the key feature is recursion for the parts inside parentheses. Depending on the parsing algorithm you want to employ, you may have to refactor this grammar.

Next, which set of paths does a given string $p \in L_p$ describe? Note that this is independent of the syntax; we could define anything we want as the meaning of $p$. Your specification is quite precise, and can be described by these by recursive functions:

$\qquad\begin{align}
  \varphi(t) &= \{t\} \quad, t \in [\mathtt{a}\dots\mathtt{z}], \\
  \varphi(t\mathtt{,}w) &= \varphi(t) \cdot \varphi(w) \quad, t \in [\mathtt{a}\dots\mathtt{z}], w \in \Sigma^*, \\
  \varphi((v)w) &= (\psi(v), \{\varepsilon\}) \cdot \varphi(w) \quad, v, w \in \Sigma^* \\
\end{align}$

and

$\qquad\begin{align}
  &\psi(t) = \{t\} \quad, \mathtt{t} \in [\mathtt{a}\dots\mathtt{z}], \\
  &\psi(t\mathtt{,}w) = \psi(t) \cup \psi(w) \quad, t \in [\mathtt{a}\dots\mathtt{z}], w \in [\mathtt{a}\dots\mathtt{z},\mathtt{,}]^*, \\
  &\psi(v_0(w_1)v_1(w_2) \dots v_{k-1}(w_k)v_k) =  \\
    &\phantom{=}\bigcup_{i \in [0..k]} (\psi(w_1), \{\varepsilon\}) \cdot \dots \cdot (\psi(w_{i}), \{\varepsilon\}) \cdot \psi(v_i) \cdot (\psi(w_{i+1}), \{\varepsilon\}) \cdot \dots \cdot (\psi(w_k), \{\varepsilon\}) \quad, v_i \in [\mathtt{a}\dots\mathtt{z},\mathtt{,}]^*, w_i \in L_P. \\
\end{align}$

Note how $\varphi(p) \subseteq [\mathtt{a}\dots\mathtt{z}]^*$ is the set of paths described by $p$.

Warning: Your syntax has the troublesome feature that a comma-separated list of path elements has different meaning outside and inside of parenteses (resulting in two functions for the semantics). In combination with your semantics, that means e.g. that you can not describe the set of paths $\{ad, abcd\}$.

Warning: Your semantics have the troublesome feature that any list of atoms in parentheses may produce at most one atom (selection), but if one element of the list is another list we suddenly get more (selection + concatenation). In other words, the semantic of $\mathtt{,}$ inside of parentheses changes depending on context. This is what makes the semantics so horrible. But then, maybe that is how it has to be: you seem to want it that way.


Bellman Ford facts and specific question The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following:
$d(v)>d(u)+w(u,v)$
holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)$ is the length of best path was found for vertex $u$.
If in any step there is no update for all vertexes, the algorithms terminate.
If Bellman-Ford will be used for finding all shortest paths from vertex $s$ in graph $G$ with $n$ vertex, terminate after $k < n$ iteration then following is True:
number of edges in all shortest paths from $s$ is at most $k-1$

I think some times this is true and sometimes is false (when we check all edges simultaneously... maybe this is wrong), but I need a clear definition for the above sentence or a small example about logic.  I need verification of the above fact. is it always true? why?
New Updates:
The above statement is dependent on the implementation of your algorithm (at least I think).
Which implementation makes it true and under which condition it becomes false...
I see 4 version of Belman Ford on This Jeff Erricson Algorithm Book on Page 295.

The claim is true. Any correct implementation of Bellman-Ford must guarantee this. Think about an arbitrary shortest path from $s$ to $v$. Besides being a shortest path with regard to the total weight, it must also satisfy another property: the path must be also shortest with regard to the number of edges used. In other words, the algorithm wants to determine shortest paths that are also simple paths (no vertices are repeated, i.e., all of the vertices in the path are distinct).
Why there is a need to ask for shortest and simple paths? Because there are obviously shortest paths with regard to the total weight that are not simple, e.g. there can be zero weight cycles. Bellman-Ford assumes that there are no negative weight cycles (the algorithm is able to detect a negative weight cycle) but there can be zero weight cycles, since they are actually allowed by the definitions. The problem caused by a zero weight cycle is that you can use it to arbitrarily augment the number of edges of a shortest path, by putting it somewhere in the middle of a shortest path. The total weight will remain the same, so the path will be a shortest path with regard to the weight, but not with regard to the number od edges composing it. This is the reason why you want shortest paths which are simple as well. The algorithm rules out zero weight cycles, throwing them away.
Now, everything follows immediately. A simple path can not have more than $|V| - 1$ edges: that is exactly the number of passes done by Bellman-Ford (since we assume no negative weight cycles, a shortest path can visit each vertex at most only once). Given a path $v_0 = s$ -> $v_1$->...->$v_k=v$ during the $i$th iteration the algorithm relaxes all of the edges; in particular, during iteration $i$ it relaxes the edge $(v_{i-1}, v_i)$. Therefore, after $i$ iterations the algorithm has correctly set the distance of vertex $v_i$ from $s$. And we know that the input graph does not contain negative weight cycles, that the path is simple and that a longest simple path may have at most  $|V|$ -1 edges. So, the algorithm is correct.


What is the diference between $\lambda x.1$ and $1$? I know that I can $(\lambda x.1) 0 \rhd_\beta 1$. This is the constant 1, but can I contract it automatically? I mean, is $1$ the normal form of $(\lambda x.1)$?
It seems reasonable to do it but when goes to combinators this sense stops, I mean, if I can $\lambda x.1 \rhd_\beta 1$, then I would $\lambda xy.y \rhd_\beta \lambda y.y$ but $(\lambda xy.y) a b \rhd_\beta b$ and $(\lambda x.1) a b \rhd_\beta 1 b$ so that $\lambda x.1 \not\equiv_\beta 1$
What rules I'm missing on Lambda cauculus that forbids the contraction $\lambda x.1 \rhd_\beta 1$?

$\lambda$-contraction is defined as $(\lambda v.M)N \triangleright_\beta M[v/N]$. A $\lambda$-term of the form $(\lambda v.M)N$ is called a redex (= reducible expression). In order to reduce a term, you need a redex -- that's just how $\lambda$-contraction is defined.
The reason that $\lambda x.1$ can not be any further reduced is that it does not contain any redex: It is not and does not contain any terms of the form $(\lambda v.M)N$, so $\lambda$-contraction is just not applicable anywhere. The term thus already is in normal form.
In contrast, $(\lambda x.1)0$ contains a redex, namely itself -- with $v = x$, $M = 1$ and $N = 0$ --, and $\lambda$-contraction yields the normal form $1$.
Obviously $\lambda x.1$ and $1$ are non-equivalent normal forms: One is a function that yields a number, the other one is a number.
$(\lambda x.1)$ is different from $(\lambda x.1)0$ in the same way in which, say, $f: x \mapsto x^2$ is different from $f(2)\ (= 4)$. A function is not the same as the value of the function at an argument, and a function can not be applied to yield a value without an argument present.


How to decrease the confidence of a Monte Carlo algorithm in its answer? Recall that a Monte Carlo algorithm is $p$-correct if it outputs a correct answer with probability at least $p$. In the case of decision problems, where the answer is binary, repeating the MC algorithm can increase the confidence that a correct answer is obtained.

However, in the case where more than 1 possible answer is correct, this confidence can actually decrease. I'm wondering how many times $k$ does such an algorithm have to be run to obtain a confidence in the answer that is less than 50%.

Here's what I've done:

Suppose that $k=3$ and I have a 75%-correct MC algorithm that outputs 5 possible answers, 4 of which are right, and 1 is wrong. I think in this case, the 75% "correctness" of the algorithm is split between all possible right answers, such that each correct answer has a "probability" of 75%/4.

Suppose the right answers are $a, b, c, d$ and a wrong answer is $e$.

In this case, if I list all possible combinations of outputs of an MC algorithm that I run $k=3$ times, I get a list of tuples $(a, a, a)$, $(a, a, b)$... and so on, each of which is associated with a probability of occurring. So for instance $(a, a, a)$ has probability $(0.75/4)^3$ of occurring and $(a, a, e)$ has probability $(0.75/4)^2 * 0.25$.

So if I build a table associating each possible tuple to its probability of occurring, and sum the probabilities of all events where the algorithm would output the correct answer by majority voting (ties are split by choosing randomly), this should give me the final "confidence" of the algorithm. In this case, I get numbers around 0.65-0.75 (because of the randomness in tying splits).

However, I haven't been able to find a $k$ that gets this value to below 50%.

Any ideas if I'm doing something wrong? Help is much appreciated.

You can compute the probability that outcome $e$ is the unique plurality answer, when repeating the algorithm $k$ times, as follows:
$$
\sum_{\substack{a+b+c+d+e=k \\ a,b,c,d,e \geq 0 \\ e > a,b,c,d}} \frac{n!}{a!b!c!d!e!} \left(\frac{1}{4}\right)^e \left(\frac{3}{16}\right)^{k-e}.
$$
This can be computed explicitly. When $k = 70$, the probability is roughly $0.502$, and this is the minimal $k$ for which the probability exceeds $1/2$.


Are regular and context free languages closed against making them prefix-free? For a language L we define:

$\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $

Are regular / context free languages closed under this operation ?

For regular languages I thought about taking the DFA that accepts the language L and create a new NFA by making all accepting states sinks (so the only way of being accepted by the automata is that when reading the last letter we reach an accepting state for the first time).

Can't we make the same thing with a pushdown automata for context free languages ?

Edit (as Raphael pointed out, the example below is wrong):

But here is a strange language that I think implies the opposite:
$L = \{ 0^{i}1^{j}2^{n} \mid i \le n \ \text{ or }\ j \le n \} $
$A(L) = \{ 0^{i}1^{j}2^{n} \mid n = \min(i,j) \} $

$L$ is context free but $A(L)$ isn't. Obviously, at least one of the things I wrote above is wrong. Anyone have any clue what is going on here ?

Can't we make the same thing with a pushdown automata for context free languages ?

No. Your construction needs to start with a deterministic automaton, and PDAs cannot be determinized.


How to match two sets of points based on the closeset distance? I have a set of points (tiny triangles) $K=\{1,2,\ldots, k\}$ and a set points (tiny circles) $N=\{1,2,\ldots, n\}$ and a matrix of positive real values $\mathbf{D}=\left[d_{ij}\right]$ for all $i\in K$ and for all $j\in N$. The entry of the matrix $d_{ij}$ can be viewed as the Euclidean distance between triangle $i$ and circle $j$.

I would like to assign the triangles to the circles with the constraint that each assigned point is assigned to its closest neighbor. Also, the assignment must be one-to-one. For example, let

$$
\mathbf{D}=\begin{pmatrix}
1 & 1 & 5\\
2 & 3 & 1\\
5 & 8 & 6
\end{pmatrix}.
$$
Now:

triangle 1 would like to be assigned to circle 1 or 2 and then 3 (we have a tie);
triangle 2 would like to be assigned to circle 3 then 1 and then 2;
triangle 3 would like to be assigned to circle 1 then 3 and then 2;

How can I solve this problem?

I thought of creating a list of preferences based on $\mathbf{D}$ like in the example:

List of preference for triangle 1: 1, 2, 3
List of preference for triangle 2: 3, 1, 2
List of preference for triangle 3: 1, 3, 2

But how can I continue on solving this?

You have an instance of a bipartite matching problem. There are some variations on the problem. I think you're looking for a minimum cost bipartite matching, but maybe you're looking for a stable matching.


What's the theory behind the operator precedences of common operators? Could for example the precedence ordering of addition, multiplication, exponentiation, boolean and/or and zip/cross product be inferred from a few rules?

There is really no theory behind it: operator precedence is a purely human construct.

The reason is that expressions are not linear blocks of text. They are trees. For example, you can represent any arithmetic in Reverse Polish Notation. In a tree, there is no ambiguity. An operator acts on its children, end of story.

Humans are good at reading things linearly, and bad at reading trees hierarchically. So, we write equations and expressions as linear sequences of characters, with rules for parsing, parentheses to imply the tree structure, and operator precedence rules to remove some of the "obvious" parentheses.

One could imagine a system in which 2+3*4 was (2+3)*4. Math works just as well in such a system, and the choice is totally arbitrary. It is simply not the arbitrary choice we happen to use.


Conflicting definitions of quasipolynomial time The textbook The Nature of Computation uses the following definition of quasipolynomial time:

  A quasipolynomial is a function of the form $f(n) = 2^{\Theta(\log^k n)}$ for some constant $k > 0$, where $\log^k n$ denotes $(\log n)^k$. Let us define QuasiP as the class of problems that can be solved in quasipolynomial time.

So presumably the definition for QuasiP could be written $TIME(\bigcup_k 2^{\Theta(\log^k n)})$. However every other definition I've found on the web, in particular the one from Wikipedia, suggests the alternative definition $TIME(\bigcup_k 2^{O(\log^k n)})$.
Now I can't see how these definitions are supposed to be equivalent. In fact I can imagine that there's a function $f$ that requires $2^{\log n}$ steps for even values of $n$ and $1$ step for odd values of $n.$ $f$ would fail to be in $2^{\Theta(\log^0 n)}$ because of the even values of $n$ and it would fail to be in $2^{\Theta(\log^k n)}$ for any $k > 0$ because of the odd values of $n$. However $f$ is still in $2^{O(\log^1 n)}$.
So apparently such an $f$ is in QuasiP according to the second definition but not according to the first. Did I make a mistake in the reasoning here? And if not am I correct in assuming that the definition in The Nature of Computation is erroneous?

Both definitions are equivalent, since when we say that a problem can be solved in time $t$, we usually mean that it can be solved in time at most $t$. For example, a problem can be solved in time $n$ if there is an algorithm solving it whose running time $T(n)$ satisfies $T(n) \leq n$.


The fastest way to check if a move is a winning move in Tic Tac Toe I'm creating a tic tac toe game, there will be two players: X and O. X will be a human, and O is an AI which will always choose the best move to play.   My board is an 11x11 board and the winning condition is 5 in a row.

How do I know if a board is at end state (where one player has won)? For the 3x3 board, you can do it easily with just a few steps. But for the larger board (11x11) and the winning condition is smaller than the dimension, it's way more complex. The best solution I have found is to check for each n x n (n is the winning condition) square for a winner.  But that seems slow.

So here is my question: if you know the last move of a player, can you use that position to check if that player wins without checking every n x n square in the board?

Yes, you can do this more efficiently.  If you have a board position and the last move made to get to that position, you can check whether the board position is an end state using the following insight:

The previous board position wasn't an end state.  Thus, if the board is an end state, that can only happen because there's a 5-in-a-row that includes the square where the last move occurred.

So, if the last move was in square $s$, check whether there's a 5-in-a-row that includes square $s$.  There are only 4 directions to check (horizontal, vertical, and both diagonals), and you can check each direction efficiently.


What's the complexity of the Bombe? Now my knowledge of this comes through watching The Imitation Game, a glance of a wiki article, and a couple of computerphile videos, so forgive me if it's obvious.

While watching the Imitation Game, I couldn't help but think that the Bombe that was being developed was just doing a naive search through all possible combinations, so there would be some days where you'd run through all 159 quintillion odd settings before you got to the right one. So why was it so good?

I understand that quite a few setting could be discounted, as the enigma machines couldn't map a letter to itself, but surely that's still quite a lot of settings to search through. And while it'll be faster than doing it by hand, it's still quite a lot.

So naturally, I'm guessing that one of my assumptions is wrong, and Turing and co. are in fact, smart cookies. What sort of algorithm are they using to break the cypher, or how are they filtering the possible iterations down?

No, the Bombe was not doing brute-force search over all possible internal settings of the Enigma machine.  Read the Wikipedia article on the Bombe, which has a detailed explanation of the techniques used by the Bombe: https://en.wikipedia.org/wiki/Bombe.


Making sense out of byte-order in text I have stumbled about the way a text file is saved by the OS.
I have typed:

printf "ab" | hexdump

and the output was:

  6261

which are the letters in reversed order. My first intent was endianess, but this cannot be true, since at this level, such abstractions must be transparent to the programmer and user. Also endian would be:

$$ab  \mapsto 6162  \mapsto 2616$$

So I wondered, why would someone save a file like that?

Greetings,
Niclas

I'm not sure this is the right place for this question. Anyway, hexdump is interpreting your input as a 16-bit little-endian number, therefore the bytes 0x61 and 0x62 (which leave the pipe in the "correct" order) appear reversed. Try printf "ab" | hexdump -C .

00000000  61 62                                             |ab|
00000002


Does any parser ever parse non deterministic unambiguous context free grammar? I have been informed parser parses unambiguous context free grammars of $DCFL$.

I was wondering if there could be a parser which could make a parsing table for unambiguous grammars of $NCFL$?

Note: This has been discussed here briefly in comments.

There are a number of general parsing algorithms (Earley, GLR, GLL, etc.) which can handle arbitrary context free grammars, even ambiguous grammars. (For ambiguous grammars, an entire parse forest is produced, usually as a spaghetti-like graph structure, because grammars can produce an infinite number of parses, or an exponential number if null cycles are removed.)

What these parsers cannot do is parse any grammar in time linear to the length of the input. It could take up to cubic time, although GLR parsers can parse unambiguous grammars in quadratic time even if the grammar is non-deterministic. (In practice, GLR parsers tend to be close to linear time for typical applications, because the grammars are "mostly" deterministic and unambiguous.)


Upper bound on register machine contents I am doing some work on register machine theory which revolves around a 2-register register machine and attempting to show that it is not possible to compute an upper-bound on the final contents of its two registers on the basis of its program code and initial input, in halting configurations only. I believe this can be related in some way to the busy beaver problem, but I cannot quite see how, and the stipulations that it is for halting configurations only has confused me somewhat.

What do I know so far?

Clearly a register machine configuration specified by the 3-tuple (instruction label, register 0, register 1) has an infinite number of possible states, owing to the abstract nature of the machines, as no practical limit is imposed on the size of the natural numbers which can be stored in each register.
I considered whether I could simply define a partial function $f : \mathbb{N}^3 \to \mathbb{N}$ where the arguments are the program encoded as a natural number and the initial contents of the two registers, but I do not think this gets me anywhere. I defined the function to be undefined when the partial function computed by the register machine specification is undefined on the given input, as the problem specifies computing the upper bound for halting configurations only. Therefore, I cannot use a diagonal argument to suggest it would imply the halting problem, because being undefined for a non-halting configuration suggests it would not.
Secondly, I tried to come up with a proof on the basis that there is an infinite number of possible configurations which a 2-register machine can be in. In particular, there is an infinite number of possible programs $e \in \mathbb{N}$ which could be executed, and each of those programs can be executed on an infinite number of initial register configurations $\mathbb{N}^2$.By construction, if there is a machine which can decide this partial function for any given combination, then I thought it may be the case that it required an infinite number of states in which to do so - which is of course not possible, as a register machine must be specified by a finite number of instructions.

I am not confident that either approach is correct or not, and wonder whether either of the above is a correct tact or if a formal proof exists for this?

Hint: Your computation model is Turing-complete. If you could compute an upper bound, that would enable you to solve the halting problem.


What is the difference between control flow and control logic? I'm trying to learn about declarative programming, and while reading the wiki it said the following:

  In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.

What exactly does this mean? I am struggling to find a definition that effectively differentiates the two terms, especially in the context of declarative programming. Is it just describing a type of abstraction?

Thanks for your help.

P.S Would it help if i could tag this as declarative programming? I can't create the tag myself

Control flow is oriented around the idea of imperative statements. What is the computer doing at this given time? What will it do next? What actions should it perform?

Declarative programming abstracts this away (or at least tries to). You're program is now not a set of instructions for the computer to follow, but a sort of specification for the problem. In order to be powerful enough to be Turing complete, these specifications are usually recursive.

The main difference is that a declarative program makes no promises about how it will be run. You state the logic, and the compiler/interpreter makes a program that fulfills that logic.

One of the most important aspects of a declarative description is that it's (relatively) standalone. A procedure in an imperative language says "do this thing to the current state". A declarative program says often will not depend on its context, or will make its context more explicit.

In practice, you can usually infer the control flow of a declarative program pretty easily, especially in strict languages like ML, F# or Elm. There's a pretty close correspondence between recursive declarations and loops, and between declarative functions and imperative procedures.

Things get fuzzier in a language like Haskell, where evaluation is lazy (you don't decide what gets run when). Or in Prolog, where there's an implicit backtracking search that the runtime does for you. You're not coding these things manually, you're simply specifying what the result should look like, not how you will get that result.


Average-case complexity of linear search where half of the elements in the array are duplicates I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows:

A(n) = $\frac{n + 1}{2}$

However, I am having trouble coming up with the Average Case complexity in the case where half of the elements in the size n array are duplicates. Take, for example, this array of integers:

1 2 6 6 5 4 6 6 6 3

Here is my thought-process so far:

I know that if we are looking for a specific element x in the array, the probability of doing it in a certain number of comparisons is $\frac{1}{n}$, since the distribution is uniform. So the average number of comparisons is still $\frac{n + 1}{2}$. (referencing this question's approved answer)

If the element we are looking for x is the duplicate number, however, then what is that probability of doing it in a certain number of comparisons? From there, how would I then compute the average-case complexity?

Let us assume the elements in the array are the multi-set $M=\{1,2,\cdots,n-k, d, d, \cdots, d\}$, where $d$, an element that is different from $1,2,\cdots, n-k$, appears $k\ge 0$ imes. The situation raised by OP is simply the special case when we let $n=2k$.

In order to discuss the average time-complexity of a linear search, we must specify the distribution of the array as well as the element or the distribution of the element we are searching for.

The distribution of the array assumed

The most common distribution discussed in various articles and in people's mindset is probably the following simplest one.
    $$\text{All orderings of the multi-set are equally likely.}$$
That distribution is assumed throughout this answer.

The average number of comparisons needed when we search for $d$

The following answer is given in the wikipedia analysis.

$$\begin{cases}
  n                   & \mbox{if } k = 0 \\
  \displaystyle\frac{n + 1}{k + 1} & \mbox{if } 1 \le k \le n.
\end{cases}$$

The above answer is easy to prove by induction on $n$.

The average number of comparisons needed

Assume $k\ge 1$ from now on. Two cases will be shown.

the case with one extra element

Let $o$ stands for an element not in the set $S=\{1,2,\cdots,n-k, d\}$.
If we are searching for a specified element in $S\cup\{o\}$, where each element is equally likely to be specified, here is the computation.
$$\begin{align}
E[\text{search for } x] &= \sum_{x!=d \text { and } x!=0}\frac 1{n-k+2}E[\text{search for }x] + \frac1{n-k+2}E[\text{search for }d] + \frac1{n-k+2}E[\text{search for }o]\\
&=\frac{n-k}{n-k+2}\frac{n+1}2 + \frac1{n-k+2}\frac{n + 1}{k + 1} + \frac1{n-k+2}n\\
&=\frac{n+1}2 + \frac1{k+1} - \frac{2}{(k+1)(n-k+2)}
\end{align}$$

In particular, if we let $n=2k$, then
$$E[\text{search for } x] =\frac {n+1}2 + \frac2{n+2}-\frac{8}{(n+2)(n+4)}$$

the case with $M$ alone

What is the average number of comparisons need among the cases when the element we are search for turned out to be an element in $M$, assuming that we are searching for an element in the union of the multi-set $M$ and another multi-set $M'$ that is disjoint with $M$, where all elements in $M$ will be equally likely to be searched? The inclusion of the $M'$ is to ensure that we do NOT know whether the element to be found belongs to $M$ before we start the search.

Here is the computation.
$$\begin{align}
E[\text{search for } x] &= \sum_{x!=d}\frac 1{n}E[\text{search for }x] + \frac k{n}E[\text{search for }d]\\
&=\frac{n-k}n\frac{n+1}2 + \frac k{n}\frac{n + 1}{k + 1}\\
&=\left(1-\frac{k-2}n -\frac2{n(k+1)}\right)\frac {n+1}2
\end{align}$$

In particular, if we let $n=2k$, then
$$E[\text{search for } x] =\frac14\left(n+5-\frac 4{n+2}\right)$$

Please note that we have not computed the situations when we know the element to be searched is an element of array before we start the linear search, which might be the more common situations. Readers are encouraged to dive into those situations.

The wikipedia item is a good place to start your journey of finding, reading, and playing with the many variations and generalization of this question.


Techniques/tools for constructing hard instances of a puzzle game Are there techniques and/or software tools that can be used to
  construct hard instances of a simple puzzle game (or a simple planning
  problem)?

With "hard" I mean that any solution of the instance is "long" with respect to the input size.

What I have in mind:

model the puzzle game using a constraint programming language (or even STRIPS);
the tool starts with assigning some random values to the model parameters to construct an instance;
solve the instance and if solutions are "easy" (shorter than a fixed length) or no solution is found in a specified amount of time, try to adjust it using some heuristics (or other techniques such as GA or simulated annealing).

As I understand it, the problem you are interested in is Bounded PlanSAT which asks whether there is a solution of length $k$ or less. PlanSAT on the other hand asks whether there exists any plan than solves the problem. Bounded PlanSAT is, for example, decidable even if we add function symbols to our language and thus make the number of states infinite. Both of these decision problems are indeed in $\text{PSPACE}$.

As for your problem of generating hard instances (meaning long solutions), one approach could be GRAPHPLAN which uses a data structure called the planning graph. Now, the planning problem asks if we can reach a goal state $G$ from the initial state $S_0$. Suppose we are given a tree of all possible actions from the initial state to successor states, and their successors, and so on. Indexed appropriately, we could answer the question of "is $G$ reachable from $S_0$?" just by looking it up. This is naturally impractical, since the tree is of exponential size. The planning graph is a polynomial-size approximation to this tree that can be constructed quickly.

The planning graph can't answer for sure whether $G$ is reachable from $S_0$, but it can estimate how many steps it takes to reach $G$. The estimate is always correct when it reports $G$ is not reachable, and it never overestimates the number of steps. Hence it is an admissible heuristic.

I agree this is perhaps not exactly what you are looking for. Nevertheless this way, one does not have to actually solve the instance. I don't think solve time is a particularly useful measure of hardness. For some solvers, some instances are easy. For some solvers, they are hard. In this sense, something like long solutions seem like a good measure of hardness.

Another thing that crossed my mind was the fact that classical planning can be represented as a constraint problem (SAT/CSP, see for example SATPLAN). If translated as SAT for example, one can use all the tools available in that domain. You might be interested for example in the question Measuring the difficulty of SAT instances. As for directly generating an instance of planning that has a solution of length more than $k$, I don't know the answer to.

By the way, if you want to solve instances in practice, Helmert (2001) analyzes many classes of planning problems and notes that constraint-based approaches such as GRAPHPLAN and SATPLAN are best for $\text{NP}$-hard domains while search-based approaches do better in domains where feasible solutions can be found without backtracking. Both have problems in domains with many objects because they must create many actions. One can also check out the International Planning Competition (IPC), similar to the SAT competition(s).


How many node does the final B-tree have? I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is:

  Suppose that we insert the keys $\{1,2,...,n\}$ into an empty B-tree with minimum degree 2. How many nodes does the final B-tree have?

I think given that a node will have between $t-1$ and $2t-1$ keys, where $t$ is the minimum degree, so the answer for this question will be somewhere between $n$ and $n/3$? This is where I'm stuck, any help would be appreciated.

Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children.
If we imagine to construct a minimun nodes b-tree, we'll have:
$n = 1 + 2  + 2\lceil m/2\rceil + 2\lceil m/2\rceil^2 + ... + 2\lceil m/2\rceil^{h-2}$where every addend is the number of nodes for every level, from the root (that can contains even one key), to the leaves level, and
where h is the height of the b-tree;
If you consider the series, you have $n=1+2 \frac{ \lceil m/2\rceil^{h-1}-1}{\lceil m/2\rceil-1}$.
Instead, if you consider the maximum number of nodes, you will have:
$n= 1+m+m^2+...+m^{h-1} =  \frac{m^h-1}{m-1}$.
where at the same way, every addend is the number of nodes for every level, and
where h is the height of the b-tree;
You can easily find the result if you substitute 2 instead of m in the formula.


Find long connected similar subsequences in two given sequences I'm looking for pointers to algorithms which will find long connected similar subsequences which two given sequences have in common. For example, in case of two strings:

abcaabbaabUVWXYZ
UVWXeYZababababab

I'm interested in:

**********UVWXYZ
UVWXYeZ**********

Not in:

ab*aabba*b*****
******aba*ab*bab

(which would be one possible longest common subsequence for the given strings).

For the example above, e represents a (small) difference in the otherwise identical strings UVWXYZ and UVWXeYZ. This is where the similarity comes in. e is not necessarily an addition of a single character. It may be a change as well. When thinking on longer strings, multiple characters (even in direct succession) may be different.

The algorithm should probably be driven by a rating function for the length and the similarity of subsequences.

I'm aware that this problem is rather vague, so any pointers to possibly related problem domains and corresponding algorithms are appreciated as well.

Update:
Removed exclusion criterion "LCS", because it actually seems to be what I'm looking for.

Let's call this problem LCCS, which is different with LCS. One straightforward way is to use a brute force algorithm with time complexity $O(nm(n+m))$.

 1. Input: A[1..n], B[1..m]
 2. Output: Length of the longest common connected subsequence
 3. max = 0
 4. for i from 1 to n
 5.    for j from 1 to m
 6.        if (lowercase(A[i]) = lowercase(B[j]))
 7.           i' = i
 8.           j' = j
 9.           len = 1
 10.          while (i' <= n and j' <= m)
 11.             i'++
 12.             j'++
 13.             if (lowercase(A[i']) != lowercase(B[j'])) break;
 14.             else len++;
 15.          if (len > max) max = len
 16. return max


How to construct a grammar that generates language L? I'm in a Formal languages class and have a grammar quiz coming up. I'm assuming something like this will appear.

Consider the alphabet $\Sigma$ = {a, b, c}. Construct a grammar that generates the language $L = \{bab^nabc^na^p \mid n ≥ 0, p ≥ 1\}$. Assume that the start variable is $S$.

One possible grammar is: $G = (N, \Sigma, P, S)$,
where

$N = \{S,U,V\}$

$\Sigma = \{a,b,c\}$

$P = \{
  S \to baUV,
  U \to ab|bUc,
  V \to a|aV
\}$

The key observation here is breaking $bab^nabc^na^p$ into 3 parts, $ba$, $b^nabc^n$, and $a^p$, one fixed, one growing bidirectionally, and one simple repeatition. Express the growing patterns first, then merge them along with the fixed parts.


Minimum path cover--- Disjointed paths with minimum total number of edges Let $T=(\mathcal{V},\mathcal{E})$ be an udirected acyclic graph and $|\mathcal{V}|=n$. Let $\mathcal{V'}$ be $\mathcal{V'}\subset \mathcal{V}$ where $|\mathcal{V'}|=2m\leq n$. There are $2m \choose 2$ pairs of nodes in the set $\mathcal{V'}$. For each pair of nodes $(w,w')$ in the set $\mathcal{V'}$, there is a unique path form $w$ to $w'$ lets call it $\text{path}(w,w')$ and it contains all the edges in the path of $w,w'$. I would like to find a collection of pairs of nodes of $\mathcal{V'}$, where each node of $\mathcal{V'}$ appears in one pair exactly, thus we have $m$ pairs in total in the final desired collection. Lets call that collection of pairs $F(\mathcal{V'})$, also, $F(\mathcal{V'})$ should be found such that the total number of edges in the paths $\text{path}(w,w')$ is minimum, where $(w,w')\in F(\mathcal{V'}):$$$\min_{F(\mathcal{V'})} \sum_{(w,w')\in F(\mathcal{V'})} |\text{path}(w,w')|. $$ Notice that a necessary condition for the choice of pairs $F(\mathcal{V'})$ is that the paths should be disjointed (have no common edges), otherwise we have a total number of edges greater than the minimum possible.

I would like to know what the algorithm is that finds $F(\mathcal{V'})$ in polynomial time. Is this related to the Hamiltonian cycle problem? My graph is acyclic which should help to get a polynomial time algorithm.  *By disjointed paths I mean paths with no common edges, they may have common vertices. **By minimum path cover I mean the total number of edges in the collection of paths is minimum since the number of paths is always chosen to be $m$.

A Trivial Algorithm

You can compute the lengths of all-pair shortest paths among $\mathcal{V}'$, and solve a minimum perfect matching in a complete graph on $\mathcal{V}'$ where the weight of an edge $(u,v)$ is the length of the shortest path from $u$ to $v$.

A Smarter Algorithm

Consider the connected component containing $\mathcal{V}'$, it must be a tree.

At each step we move the deepest nodes in $\mathcal{V}'$ to their fathers. If two nodes move to the same node, we decide to match them and do not consider them any more in following steps. If more than two nodes move to the same node, repeatedly match arbitrary two of them until no more than one node is left.

This algorithm runs in $O(|\mathcal{E}|)$.


Joining line segments to make tree Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and every segment is an edge in the tree.

Disclaimer: the proof is quite technical. OTOH, I don't see a comfortable way to do this, because the initial set of segments can be as crazy as possible, even if none of them intersects.

Let's prove that we can make a tree not only from the set of disjoint segments, but also from the set of disjoint trees. So, the initial statement will be just a special case of it when all trees are segments.

The new statement will be proved by downward induction on the number of trees. When we have only one tree, we are done. To make an induction step, it's enough to connect two trees without intersecting or touching other trees.

Define distance between different trees $S$ and $T$ as $d(S, T) = min_{s\in P(S), t\in P(T)}d(s, t)$, where $P(X)$ is a set of all points belonging to tree $X$ (not necessarily vertices), $d(s, t)$ is a usual Euclidean distance.

Then take $(S, T) = argmin_{R, W \hbox{ are trees}, R \ne W} d(R, W)$. Let $d_0 = d(S,T)$. Also define $s$ and $t$ as the points which deliver us the minimum distance.

WLOG $s$ is a vertex. This statement requires some geometrical analysis. The most complicated case is when $s$ and $t$ lie strictly inside some segments. But if so, these segments must be parallel to each other, otherwise we can draw a height from some point to the opposite segment and get a distance smaller than $d_0$. And if they are parallel, the segment $st$ is perpendicular to them both, and we can simply move it to the one of the ends of the segments, so one of points actually becomes a vertex.

First, prove that the segment $st$ doesn't intersect or touch other existing segments. We do it by contradiction. If such segment exists, set the intersection point to $u$. It lies strictly inside $st$, because the tree set is disjoint and not self-intersecting. There is a tree $U$ such that $u\in U$. But either $U \ne T$ or $U \ne S$, thus $d(U, T)$ or $d(U, S)$ is well-defined and is smaller than $d(s, t) = d_0$. Contradiction.

Second, if $t$ is already a vertex, we are done, because we can draw a new segment connecting vertices $s$ and $t$. Otherwise define the segment which $t$ belongs to as $K$.

Third, let's continuously move $t$ on $K$ to one of the ends of $K$. If we reach the end without $st$ touching any other points, we are done. If not, assume that we got a segment $st'$ for $t'\in T$, and also $st'$ contains some other vertex $v \in V$. If there are more than one such vertex, take closest to $s$.

Let's look what happens if $V \ne T$. Geometry says that $st$ is perpendicular to $K$. So, if we draw a height from $v$ to $K$, we get a segment shorter than $st$, and it will deliver a distance from $V$ to $T$ smaller than $d_0$.

And if $V = T$, we can just forget about $t$ and connect $S$ and $T$ using segment $sv$.


Complexity of recursion T(n) = 2T(n-1) + C? I am trying to calculate the Time Complexity of the Recursive Function, suppose this,

function T(int n){
 if(n == 1) return 1;
 return T(n-1) + T(n-1);
}

the time complexity equation is: T(n) = 2T(n-1) + C, taking C = 1 and T(1) = 1.
Now, since I am working on this, I am confused whether I am doing the right process using Back Substitution. This is how I approached the calculation.
I have followed the below question, but did not find it very satisfactory, so raising the question again.

Complexity of Recursion T(n) Function

This is how I approached the problem:

1. T(n) = 2T(n-1) + 1
2. T(n-1) = 2T(n-2) + 1 //since we have T(n-1) in Eq(1)
3. T(n-2) = 2T(n-3) + 1 //since we have T(n-2) in Eq(2)

Back Substitution to Solve for final complexity

1. T(n-1) = 2(2T(n-3) + 1) + 1
2. T(n) = 2(2(2T(n-3) + 1) + 1) + 1
        = 2(4T(n-3) + 1 + 2) + 1
        = 8T(n-3) + 1 + 6
        = 8T(n-3) + 7
        = 8T(n-3) // Ignoring 7, since it is a constant
        = 2^3T(n-3)
        = 2^kT(n-k)

Substituting the value of K, since base case is n = 1

1. n-k = 1
2. k = n-1

//Substituting the value of k in the above T(n) Equation
T(n) = 2^{n-1}T(n-n+1)
     = 2^{n-1}T(1)
     = 2^{n-1} * 1
     = 2^{n-1}

So from above I got 2n-1, is the above process correct, or needs improvement. I am starting off with time complexity, and this recursion is kind of tricky for me. Please help!


$a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma? $L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\neq$ into smaller and larger. You will have four sets. You can give CFG's for each. Then since CFGs are closed under union, you have your proof.

Now how can I go around proving that $L$ is not regular? If you prove that the each of these four sets are not regular, you still can not prove that the union is not regular, can you?

Lets assume towards contradiction that L is regular.
Then, by closure properties, we have $\bar L$ is regular, and thus also $\bar L \bigcap (a^*b^*c^*)$ is regular. But calculating it, we find out $\bar L \bigcap (a^*b^*c^*)=\{a^nb^nc^n\}$ is not regular.


Optimizing method for counting length of elements between blocks I'm currently trying to do a count of the number of elements between obstacles, for example:

000100001000 Would yield 3,4,3 and 01001110 would yield 1,2,1. More precisely i'm trying to find the sum of the above lengths passed to this function:

$f(x) =  \frac {x(x+1)} {2}$

So the first example would yield a result of 22 (6+10+6) and the second would yield a result of 5 (1+3+1).

This is done repeatedly with the first element 'chopped off'. So for 000100001000, this would be calculated for 000100001000, 00100001000,0100001000 ,100001000 ,00001000 and so on (note that the answer for 10010 and 0010 would be the same since we're counting the distance between ones)

Currently i've just been using an $O(N^2)$ brute force approach, but i feel that i can easily improve this to O(N) since most of the information is already calculated after the very first element is processed. I'm wondering if there's a constant time method to process the subsequent elements after the first one is processed, but if not, what is the best approach?

Edit: I found a way to optimize the algorithm that requires this algorithm, but that implies that some of the zeroes could be transformed into ones when a digit is 'chopped off'. It's safe to assume that the element(s) that get transformed would be random.
Eg:
0010 when chopped may transform into 011 or 110 or 111 instead

One gap can be calculated as tetrahedral number $P(x) = \sum \limits _{i = 1} ^{i=x} f(i) = \frac{x * (x + 1) * (x + 2)}{6}$ where $f(i) = \frac{i * (i + 1)}{2}$
After calculating all gaps to calculate chopped off sum you need to subtract $P(x) - P(x-1)$ from the sum.


Recent Garbage collection survey paper Many years ago I read a GC survey paper that was updated every few years with advances; I tried to find such a paper today to point a questioner on Stackoverflow at.

However all I can find is very old survey papers that don’t include current thinking on items like hardware assistance.

the area seems to be "mature" in the sense that garbage collection theory/ dynamics is relatively well understood, surveys that come up in searches are years old and many state-of-the-art algorithms are now implemented, and maybe research in the area is far less common or active. also hardware assisted garbage collection seems an uncommon combination theoretically (also/ incl operating system aware/ crosscutting such as algorithms that intentionally mesh well by design with caches, paging, virtualization, etc). speaking as a practitioner in the field, garbage collection algorithms tuned with hardware features or OS mechanisms seems a promising idea that hasnt been explored much.

here is one survey turned up of 3 state of the art algorithms from 2013 and there is a hardware mechanism on the 1st (for reference counting).

Low Pause-Time Garbage Collection
Written Preliminary Examination II / DeLozier


Find total count of all paths starting from a fixed vertex to all other vertexes of the graph Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e.

$$
\text{#(paths from 1 to 2)}+\text{#(paths from 1 to 3)}+\cdots+\text{#(paths from 1 to $n$)}.
$$

We have to find this in linear time, as number of vertexes can be as large as 100000. I tried using DFS in this question to generate all the paths and keeping up count of these but this is not fast enough.

Is there any mathematical formula for this?

P.S. I am only interested in total number of paths, not generating all the paths. Each vertex has up to 4 or 5 edges.

For example, if the adjacency matrix of a 4 nodes graph is like this:

  A B C D
A 0 1 0 0
B 1 0 1 1
C 0 1 0 1
D 0 0 1 0

Then the number of paths are

from A to B: 1
from A to C: 2
from A to D: 2
therefore 5 paths

So I want the answer to be 5.

The edges may be unidirectional or bidirectional and I want to find only simple paths.

Suppose you have a polynomial-time algorithm $\mathcal{A}$ to solve this problem, then consider a graph $G$ and arbitrary two vertices $s$ and $t$. We construct a new graph $G'$ by add a new vertex $t'$ into $G$, as well as an edge $(t,t')$. Now we have

\begin{align}
\text{#(paths from $s$ to $t$ in $G$)} =&\ \text{#(paths from $s$ to all other vertices in $G'$)}\\
&-\text{#(paths from $s$ to all other vertices in $G$)}.
\end{align}

That means, we can use $\mathcal{A}$ to count the number of paths between two vertices in polynomial time. However, the latter problem is #P-hard. So such an algorithm $\mathcal{A}$ does not exist unless $\mathbf{P}=\mathbf{NP}$.


Randomized linear search -- Why does reducing the sample size make the running time constant? I have two search algorithms (for determining if an element $x$ is in a list $A$ of length $n$):

(1) Pick a random index $i$ from $L = [1, \ldots n]$. If $A[i] = x$, terminate. Otherwise, pick a new random index $i$, still in the list $L = [1, \ldots , n]$. Repeat until we've either found a $j$ such that $A[j] = x$ or until every index in $A$ has been exhausted.

(2) Similar to Algorithm $(1)$, except,for element $i$ at every iteration, we perform $L.\text{remove}(i)$ ($L$ has the index $i$ removed from it). This way, we're guaranteed to terminate within $n$ steps (as opposed to potentially running the algorithm forever, as in (1)).

Now, in (1):

  If we let $X = $ the number of iterations before Algorithm (1) terminates, we have $$X \sim \text{Geo}(1/n)$$ from which we get $E[X] = 1/(1/n) = n.$

In (2):

  Let Y = number of iterations before Algorithm (2) terminates.
  Let $Y_i$ = event that the algorithm terminates after $i$ iterations.

  Then $$P(Y_1) = \frac1n \\ P(Y_2) = \frac{n-1}{n}\left(\frac1{n-1}\right) = \frac1n \\ P(Y_3) = \underbrace{\left(\frac{n-1}n\right)\left(\frac{n-2}{n-1}\right)}_{P(\text{two failures})} \ \underbrace{\left(\frac{1}{n-2}\right)}_{P({\text{one success}})} = \frac1n \\ \vdots \\ P(Y_n) = \frac1n$$

  hence $$E[Y] = \sum_{i=1}^n iP(i \ \text{iterations are required to terminate}) = \sum_{i=1}^n \frac1n = n \cdot \frac1n = 1$$ but this doesn't make any sense. How can the expected number of iterations be constant.

Shouldn't $E[Y]$ vary linearly with $n$? What's going on here?
Also, when calculating the expected running time (of each of these algorithms), how do I take into account the possibility that the given list does not contain the element $x$? Obviously, it increases the expected running time, but by how much?

You made a simple algebraic error.  You said $\Pr[Y=i] = 1/n$, then you wrote

$$E[Y] = \sum_{i=1}^n i \Pr[Y=i] = \sum_{i=1}^n {1 \over n},$$

but that is incorrect: you omitted the $i$ in the second sum, i.e., you didn't plug in the value of $\Pr[Y=i]$ correctly.  Assuming that both indexing into the list and removing an item from the list can be done in one time step, the correct derivation is

$$E[Y] = \sum_{i=1}^n i \Pr[Y=i] = \sum_{i=1}^n i \cdot {1 \over n} = n(n+1)/2 \cdot {1 \over n} = (n+1)/2 = \Theta(n).$$


Is this finite graph problem decidable? What factors make a problem decidable? I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is provided here)?

  Input: A directed and finite graph $G$, with $v$ and $u$ as vertices
  Question: Does a path in $G$ with $u$ as initial vertex and $v$ as final vertex exist?

Any problem that requires only examining a finite amount of data is decidable, because there is an algorithm that consists of enumerating all the potential solutions. It may be ridiculously slow, but that's not relevant: if there is an algorithm, it's decidable.

The problem you state assumes a finite graph, which strongly hints that it's decidable. Strictly speaking, you need to look a bit further. The problem is a property on the paths in the graph, and there is sometimes an infinite number of paths, when the graph contains a cycle (you can loop around this cycle as many times as you like). However, it's easy to turn the problem to a finite problem: if there is any path beginning with $u$ and ending with $v$ that includes a cycle, then you can cut out all the cycles in that path, and you have a new solution which does not include a cycle. Since there is a finite number of paths that do not involve a cycle (if the graph has $k$ edges, there are at most $k!$ paths that do not use the same edge more than once), the problem of finding a path from $u$ to $v$ is finitary, hence decidable.

Incidentally, this property is called connectivity.

This approach is a common one, called reduction. Given a problem which is not straightforward, we reduced it to a problem we knew how to solve.

It is often difficult to prove that a problem is undecidable. To prove that a problem is decidable, all we need to do is exhibit an algorithm that decides it. To prove that a problem is undecidable, we need to prove that no algorithm can exist. There are a few well-known undecidable problems. In practice, most of the time, when we prove that a problem is undecidable, we show that there is a well-known undecidable problem that reduces to our problem. Since an algorithm for our problem would solve the well-known undecidable problem, our problem must also be undecidable.

You can't really say that “most” problems are decidable or “most” problems are undecidable. In some theoretical sense, almost all problems are undecidable, but we have a strong tendency to tackle “interesting” problems, and those are more likely to have a solution.


Decidable problems for which no concrete decision procedure is known I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. I suppose the decidability of these problems are proved non-constructively, so that they have this kind of counter-intuitive property.

I think that in graph theory, there are a number of problems in this trait. I am wondering if you are aware of any of these.

Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n \in \mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:

Always return "true".
Always return "false".

But you need to solve $P=NP$ to know which one.


Showing a language is a subset of another language? I'm actually trying to give an example of a language being context-free and its superset that isn't context-free. I came up with this, but I'm not sure if this particular language is a superset of the other.

Let A be a context-free language. A = {a^n b^n | n >= 0}.

Let B be a non context-free language. B = {a^n b^n c^n | n >= 0}.

What I'm not sure of is if A is a subset of B. I saw something regarding proving if a regular language is a subset of another regular language, but I don't know if it applies to this situation.

Can someone provide some clarity on this, please?

A language $B$ is a superset of another language $A$ if it contains all the strings of $A$ and some more. In your example, $A$ contains $ab$, but $B$ only contains string with $c$'s in them, so $ab\not\in B$, so $B$ is not a superset of $A$, i.e. $A \not\subseteq B$.

What you are looking for is a language $B$ which is not context-free but which does contain all of $A$. For example, you could let $C$ be some very difficult language, for example, the language of TMs that halt on the empty tape, or the language of prime numbers, and let $B=A\cup C$. Then whatever the complexity it $B$, you can be sure that it's not context-free. This trick won't always work. For example, if $A=\Sigma^{*}$, then no superset of $A$ exists, and certainly not one that isn't context-free.

What you read about one language a subset of another language is probably succinctly captured in the Wikipediag page on context-free languages (link) and that of regular languages (link) under the section of closure properties. A closure property is a theorem states that, for example, if $L_1$ and $L_2$ are both context-free, then $L_1 \cup L_2$ is also a context-free language. In this case you can say context-free languages are closed under union.


Uniform convergence for a class of finite dimension The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. Convergence of Stochastic Processes. Springer, 1984. However, I have trouble finding the proof. Anyone knows a reference?
Let $\Phi$ be a distribution over $\mathcal{X}$. With probability $1-\delta$ over $x_1,...,x_N\sim\Phi$, for all $a\in\mathcal{A}$ it holds that $\left|\frac{1}{N}\sum\limits_{i=1}^na(x_i)-\mathbb{E}_{x\sim\Phi} a(x)\right|\le\sqrt{\frac{2d}{N}\ln\frac{eN}{d}}+\sqrt{\frac{1}{2N}\ln\frac{2}{\delta}}$
where $\mathcal{A}: \mathcal{X} \rightarrow \mathbb{R}$ is a set of real-valued functions and $d$ is the psuedo-dimensionof $\mathcal{A}$.

The keyword to look for is Dudley's chaining integral, see e.g. Vershynin's book "High Dimensional Probability" which contains a chapter on the chaining technique. Chaining allows us to bound the empirical Rademacher complexity in terms of the empirical $L_2$ covering numbers of $\mathcal{A}$. Your result is directly obtained from the chaining integral and a result (which is think is credited to Dudley-Pollard) which relates the $L_1$ covering numbers (irrespective of the distribution) to the pseudo dimension, see e.g. theorem 4.2 in these notes. You still need to go from $L_2$ covering to $L_1$ somehow, this is easy when the functions are binary valued.


What is the type system (or class of type systems) that that ensures all your tree Branches end in Leaves? I've come across this situation numerous times in the past few years where I have some classes like (pseudo-Java):

interface Node<T> { ... }

final class BranchNode<T> implements Node<T> {
    List<Node<T>> children;
}

final class LeafNode<T> implements Node<T> {
    List<T> elements;
}

If you know the height of a balanced tree in advance, you can make classes for each height of node instead of a single BranchNode class.  I think Daniel Spiewak did this in his Scala PersistentVector implementation:

final class Height2Node<T> implements Node<T> {
    List<Height1Node<T>> children;
}
final class Height1Node<T> implements Node<T> {
    List<LeafNode<T>> children;
}

But if you don't know the height of the tree or need to support an arbitrary height, or only care whether a node is a Branch or a Leaf, is there a type system that can ensure that all your Branches end in Leaves?

I mean, you could walk the tree and use instanceof to find some leaf nodes and calculate the height of a given node from that and write code to ensure a balanced tree.  But I'm wondering if a type system exists that can model this in such a way that it allows building a valid tree and prevents building an invalid one?  If so, what is that type system, or class of type systems that can help solve this problem?

I've heard the words, "dependent types" and "higher kinded types" before. I could maybe even recognize simple examples of one or the other, but would have trouble explaining what they mean.  So go easy on me, or provide links.  Thanks in advance!

To be honest, I'm unsure about whether this is a CS question or a programming question. There is a strong programming part to it, yet encoding requirements in types requires reasoning on types which is more on the CS side. Anyway, here is an answer.

There are several options to encode that requirement into types.

Basically, we need to encode that each BranchNode has at least one child. This means that a leaf can only be a LeafNode.

A naive approach would be

final class BranchNode<T> implements Node<T> {
    Node<T> firstChild;
    List<Node<T>> otherChildren;
}

We can even keep only a (private) children list, and enforce that using a constructor.

// Make these private
private Node<T> firstChild;
private List<Node<T>> otherChildren;

// Make this to be the only public constructor of the class
BranchNode(Node<T> firstChild, List<Node<T>> otherChildren) {
    children = otherChildren.clone();
    children.add(firstChild);
}

Note the usual caveats, though. One can break this invariant using nulls, non termination, or by creating circular references, e.g. a BranchNode which is its own child (this is easy to achieve if the tree is mutable, for instance). Unwanted subclasses also can break the invariant.

Another option is to exploit the usual Church encoding of algebraic data types into polymorphic types. In theory, this is related to initial algebras and catamorphisms. In OOP practice, this is known as the "visitor pattern".

I'll pretend leaves contain a single int. One can generalize this using generics, as usual.

interface Visitor<R> {
   R visitNode(int data);
   R visitBranch(R firstChild, List<R> otherChildren);
}

interface Node {
   <R> R visit(Visitor<R> v);
}

Pseudo code follows, since Java is too heavy for writing this in a readable way, and I'm not completely familiar with its functional libraries.

class LeafNode implements Node {
  int data;
  visit(v) = v.visitNode(data);
}

class BranchNode implements Node {
  Node firstChild;
  List<Node> otherChildren;
  visit(v) = v.visitNode(firstChild.visit(v),
                         otherChildren.map(_.visit(v)));
}

The advantage of this approach is that the invariant can not really be broken by adding subclasses. One can create a new Leaf2Node subclass, but if that has the same visit(v), it will behave as LeafNode. The implementation of visit(v) in general will be limited by types, and running visit(v) will always (if terminating) end with calling v.visitNode(data) when a leaf is encountered.


Does Damas-Milner still have principal types if existential type schemata are added? In the Damas-Milner type system, type schemata can be formed in two ways:

$T$
$\forall X. S$

Where $T$ ranges over monotypes and $S$ ranges over type schemata. The type-checking algorithm for this system is well known, and explanations of it can be found in several places.

What happens if I add a third type schema former?

$\exists X. S$

In other words, type schemata must still be in prenex normal form, but both universal and existential quantifiers may be used. As in Damas-Milner, only let-bound variables may be ascribed type schemata.

My questions are:

Does this system still have principal types?
How much does the type-checking algorithm change?

Yes, adding existentials doesn't add many complications for type inference, if quantifier alternation is controlled carefully. This is not surprising since universals and existentials are dual and the the function space operator gives a form of negation. Small type annotations that can help regaining type-inference are discussed in (4).

Adding existentials to pragmatically viable programming languages was first discussed in N. Perry's dissertation (1).  Perry's work was later formalised by Odersky and Läufer in (2). Läufer also described how to integrate existentials with Haskell type classes (3).

1. N. Perry, The Implementation of Practical Functional Programming Languages.

2. K. Läufer, M. Odersky, Polymorphic type inference and abstract data types.

3. K. Läufer, Type classes with existential types.

4. M. Odersky, K. Läufer, Putting type annotations to work.


What happens if there is context switch while executing system call? Suppose a process does system call, hence it goes to kernel mode, the registers are saved. Now the system call will be running in process' allocated kernel stack.

Can there be a context switch when a system call is processed?
Is really the system call allocated process' kernel stack?
If context switch is possible, this means kernel has set the timer for this. Right?
Are system calls part of job scheduling(separately) or this are include in job scheduling of process?

I am really messed up with this kernel stack.

If the kernel decides to do a context switch, it's in response to some event which caused the processor to enter kernel mode. This can be either a system call or an interrupt (which can be a timer interrupt or some other interrupts).
Whether the kernel is processing an interrupt or a system call, there are good and bad times to do a context switch. The kernel does what it wants to do, and then at the end of the processing it decides which user thread to schedule next. If it decides to schedule a thread which wasn't the last scheduled thread, it then does a context switch.
During critical parts of the processing, the kernel may disable interrupts. If an interrupt happens while the kernel is already active and doesn't have interrupts disabled, what usually happens is that the kernel does what needs to be done immediately (for example, read data from a peripheral), and adds an element to a queue to remember what needs to be done later. In Linux, these are called the “top half” and “bottom half” of interrupt processing; I don't think there's a standard term even though the concept is common. For example, if a network interrupt is triggered while the kernel in the middle of communicating with a disk, the kernel reads the network packet and stores it into a queue; then, when the disk I/O is finished (or can be paused), the kernel processes the network packet, and at this point it may decide to schedule a task that has received some input from the network.
In case there's any doubt, a timer is not required for a context switch. A context switch can happen any time a system call is in progress. The connection between timers and context switches is that if user code never makes any system call, and there is no system event (user input, networking, etc.) that causes an interrupt, the only way a context switch can happen is if a timer interrupt causes the kernel to wake up. And there are operating systems that only have non-preemptive multitasking; such kernels don't set a timer interrupt, and only do a context switch during a system call.


How to produce a context free grammar for this language? I've already attempted it but I am finding it difficult to understand if this is correct.

give a context free grammar for the following:

$$ \{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$$

The answer i've attempted is:
$S \to XY$
$X \to pppXp \mid \ q$
$Y \to qYr \mid \epsilon$

I've been trying to understand if i need to break down:
$$ \{p^{3+m+n} \}$$ in to

$$ \{p^{3}p^m p^n \}$$

to give me: pppXp

then q and r would value to

qYr | $\epsilon$

A common approach to figure out a context-free grammar for some simple languages is to find, by peeling off terminals, smaller and smaller languages that are nicely structured such that if you use a nonterminal to represent each smaller language, you can restore the larger languages from the smaller ones with a production rule.

$S=\{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$

If you peel off $p^3$ from the front and $p$ from the back $m$ times, you got language $B=\{p^nq^nr^2\mid n\ge 0 \}$. Can you see how to produce $S$ from $B$ by one production rule? In fact, that is part of what you have written.

Peeling off $r^2$ at the end, you get language $C=\{p^nq^n\mid n\ge 0 \}$. Can you get $B$ from $C$? Can you produce/recall a context-free grammar for $C$?


How can I make k nearest neighbor queries fast on unit hypersphere? I have $m$ points $D = \{x_1, \dots, x_m\}$ with $x_i \in \mathbb{R}^n$. After some preprocessing / building up data structures for those points, I get $T$ queries $y_i \in \mathbb{R}^n$ with $i=1, \dots, T$. Each query comes at a time and independently. The datastructures for the queries should not be modified by the past queries. After receiving an query $y_i$, the $k$ nearest neighbors

$$NN_k(y_i) \subset D \text{ with } |NN_k(y_i)| = k \text{ and }$$
$$\forall x_a \in NN_k(y_i) \forall x_b \in D \setminus NN_k(y_i) : \|x_a - y_j\|_2 \leq \|x_b - y_j\|_2$$

All points $x_i$ and all queries $y_j$ are on the unit hypersphere, so $\|x_i\|_2 = \|y_i\|_2 = 1$.

How do I process those queries fast?

Limits

To get a feeling for what matters, here are some orders of magnitude:

$100 \leq n \leq 1000$: Dimension of points
$m \geq 100\,000$: Candidates
$T \geq 10\,000\,000$: Number of queries
$3 \leq k \leq 20$: Expected number of returned points
Reasonable memory consumption (e.g. less than 2GB for the data structure)

The query time for a single brute force approach is in $\mathcal{O}(m \cdot n)$ as it just compares every candidate point in $D$ with the query and stores the closest $k$ of them.

Misc

I've just implemented this with Python (see code).

k=5, n=128, m=100000, T=100: 0.56s per query. (Brute force approach)

That is actually much better than I expected. However, I guess this could be an order of magnitude faster with a good data structure / smarter algorithm. I wrote the Python script in a way which should make it easy to run your own experiments on your tests, if you like.

As a rule of thumb, when the number of dimensions $n$ is less than about 10, fancy data structures (like k-d trees) work well; when the number of dimensions is greater than about 30, fancy data structures typically perform poorly and may be no better than a brute-force linear scan.  Wikipedia lists a similar rule of thumb: if $m \gg 2^n$ (where $m$ is the number of points in the data structure and $n$ is the number of dimensions), then k-d trees work well, otherwise they won't.  Exceptions exist, e.g., where your data is "structured" and non-random, but this is probably a good first guideline.

In your example, the number of dimensions is at least 100.  Therefore, I wouldn't expect any of the fancy data structures (k-d trees, M-trees, etc.) to be better than the simple linear scan.

Essentially, you are suffering from the curse of dimensionality.

You mention that your points are all on the surface of the hypersphere.  Unfortunately, this doesn't help much.  Heuristically, points on the surface of a $n$-dimensional hypersphere are a lot like points in a $n-1$-dimensional space.


How does one figure out where a class of languages falls under some complexity class? I was wondering how can someone prove that one class of languages is of a certain complexity? For example, how could I show the Turing-recognizable languages are in P?

Would I have to come up with an algorithm that runs in deterministic polynomial time?

Turing recognizable languages are not (generally) in P, as the time hierarchy theorem implies. To show that a class $L_1$ is contained in a class $L_2$, you need to show that every language in $L_1$ belongs to $L_2$. For example, to show that $L$ (logspace) is contained in $P$ (polytime), you argue as follows: every language in $L$ is decided by some machine running in logarithmic space; this machine must run in polynomial time; so the language is in $P$. In this example, the same machine was used, but this is not necessary. For example, Savitch's theorem shows that $\mathrm{NSPACE}(s(n)) \subseteq \mathrm{DSPACE}(s(n)^2)$, and here the same machine cannot be used (since a non-deterministic Turing machine is not necessarily deterministic).


Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels Prove that any binary tree with $n$ nodes has at least $1+\log_2 n$ levels.
I tried setting $n=8$ and plugging in $8\geq\log_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.

Hint: A binary tree with $1+h$ levels contains at most $1+2+2^2+\cdots+2^h = 2^{h+1}-1$ vertices.


Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart? Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$.

  If both source $s$ and destination $t$ are fixed, can we compute the shortest path from $s$ to $t$ without computing distances for all other nodes from $s$?

More fundamentally,

  Is single-source single-destination shortest path problem easier (e.g., in terms of worst-case time complexity) than its single-source all-destination counterpart?

Nope. In order to find the distance from $s$ to $t$ it is necessary to determine the length of all paths that are at least at the same distance as $t$ is. If $t$ has a "median" distance half of the distances will be known that way.

In certain application areas (with an exponentially sized "implicit" state space) it can still be worthwhile to start searching from both sides and look for nodes that are found in the middle.


Finding N most distinct values in set given distance metric Let's say you are given a set with $V$ vectors and you are given a simple Euclidean distance metric $d(a,b)$ for $a, b \in V$. Then what would be the most efficient algorithm to build a subset $S$ of a desired size $k$ such that the sum of the distances between the elements of the subset is maximized?

In other words, how does one find a subset with the most distinct vectors?

I have tried modeling this as a complete graph where the nodes are vectors and the edges the Euclidean distances between them, but I couldn't find a graph algorithm that solves this problem. It seems like finding an independent set of given size $|S|$ with the maximum number distance between them.

This problem generalizes maximum independent set and its relatives. Indeed, suppose that you could solve your problem. Then you could use the solution for deciding whether a graph contains an independent set of size $k$. Given a graph $G = (V,E)$, form a metric space by setting $d(u,v) = 1$ if $\{u,v\} \in E$ and $d(u,v) = 2$ if $\{u,v\} \notin E$. The graph contains an independent set of size $k$ iff there are $k$ points in the metric space in which the sum of distances is $k(k-1)$.


Algorithm for finding the limit of unkown function I have a case of costly calculations method like this:

Input -> Output
0 -> 8
8 -> 9
9 -> 9.5
9.5 -> 9.6
9.6 -> 9.65
9.65 -> 9.654

I use the output for the next input so this way im trying to find where the output exactly matches the input or is a tiny fraction smaller.
The goal of the algorithm is to find the smallest X=Y or X>Y where (X-Y) > 10^(-10).

However since the method for calculations is costly I'm looking for an efficient way to reduce the amount of time I'm calling the method, but still retain for example the accuracy of 10 fractional digits.

Some additional Caveats:
Output is not always increasing by increasing the Input. It might hop around the limit from both sides. Also increasing the Input value more drastically might change the value the Output approaches to which is not the desired outcome.

Since I'm posting here first time i would be glad if someone tagged this question with proper tags, since honestly i don't know which tags to use.

This is some form of fixed point iteration (you are going $x_{n + 1} = f(x_n)$, and looking for $x^* = f(x^*)$). If you know that the convergence is linear (i.e., $e_{n + 1} \approx C e_n$, where $e_n$ is the $n$-th error), you can accelerate the convergence by Aitken's $\Delta^2$ method. Say you have $x_0$, $x_1$ and $x_2$. A (hopefully much better) approximation is given by:

$\begin{align*}
  x^+
    &= x_2 - \frac{(\Delta x_1)^2}{\Delta^2 x_0} \\
    &= x_2 - \frac{(x_2 - x_1)^2}{x_2 - 2 x_1 + x_0}
\end{align*}$

Start with $x_0 = x^+$ and compute new values for $x_1, x_2$. Repeat until satisfactory precision.


Prove that {0^{n^3} | n≥0} is not context free I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L = \{0^{n^3} \mid n\in\mathbb{N}\}$ is context-free or not.

Based on my intuition, it won't be.  There is no pattern of $0$'s that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i \ge 0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.

Gilles suggests a sophisticated method for solving this exercise, which is also the "proper" method; we will say more about it below. But let's start with applying the pumping lemma. The pumping lemma states that if $L$ is context-free then there exists some integer $n$ such that all words $w \in L$ of length at least $n$ can be written in the form $w = uvxyz$ with $|vxy| \leq n$ and $|vy| > 0$ (i.e. not both $v,y$ are empty), such that $uv^ixy^iz \in L$ for all $i \geq 0$.

Let's see what this means in your case. Suppose $L$ were context-free, and let $n$ be the integer given by the pumping lemma. Take some $m$ satisfying $m^3 \geq n$. Since $0^{m^3} \in L$ and the word has length at least $n$, we can write $0^{m^3} = uvxyz$ such that $|vy| > 0$ and $|vxy| \leq n$, and furthermore $uv^ixy^iz \in L$ for all $i \geq 0$. So $vy = 0^t$ for some $1 \leq t \leq n$, and for all $i \geq 0$, $0^{m^3-t+it} \in L$, that is, for all $i \geq 0$, $m^3 + (i-1) t$ is a cube. Your mission is to somehow reach a contradiction from this data.

Now for Gilles' proof. We can consider the language $L$ over the unary alphabet $\Sigma = \{0\}$. Parikh's theorem states that $L$ is context-free iff it is regular. The proof is not difficult: if $L$ is regular then it is context-free, and in the other direction you take a grammar for $L$ and massage it into an equivalent right-regular grammar; the idea is that $xy = yx$ if $x,y \in 0^*$.

The next step is to find a criterion for when a language $L_A = \{ 0^n : n \in A \}$ is regular. By considering a DFA for $L_A$, it is not hard to show that $L_A$ is regular iff $A$ is eventually periodic, that is, for some $a \geq 0$ and $b \geq 1$ it is the case that $x \in A$ iff $x + b \in A$ for $x \geq a$. This is not the case for the set of cubes, since the gap between adjacent cubes tends to infinity. We conclude that $L$ isn't regular nor context-free.