Query on consequences of $\mathsf{P=BPP}$ We know $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$ or permanent does not have polynomial sized circuits. However permanent needs superpoly circuits imply $\mathsf{NEXP\not\subseteq P/Poly}$ since $\mathsf{P^{\#P}\subseteq  PSPACE\subseteq NEXP}$. So why dont we just say $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$?

The conclusion is that the permanent does not have polynomial-size (constant-free) arithmetic circuits or $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$. Permanent not having polynomial-size constant-free arithmetic circuits is not known to imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$.

However, there are a couple more recent similar results whose conclusion is not a disjunction, but simply a lower bound on some polynomial family in $\mathsf{NEXP}$:

Jansen and Santhanam showed that if PIT is in $\mathsf{NSUBEXP}$ then there is a family of polynomial whose integer evaluation problem is in $\mathsf{NEXP}$ but which do not have poly-size constant-free arithmetic circuits.
Carmosino, Impagliazzo, Kabanets, and Kolokolova show that if PIT over a fixed finite field is in $\mathsf{NSUBEXP}$ then there is a multilinear polynomial whose evaluation problem over that same finite field is in $\mathsf{NE}$ that does not have poly-size arithmetic circuits. (This paper also has many other results of interest, including true hardness-to-randomness equivalences, avoiding many of the usual caveats.)


Which one grows faster asymptotically: $\log(\log^an)$ or $\log^a(\log n)$ Could someone explain to me which function grows faster?

$f(n)=\log(\log^an)$ or $g(n)=\log^a(\log n)$

Assuming $\log^a n$ means $\log n$, raised to the power $a$:

Let $t = \log \log n$, then the first expression equals $t·a$, while the second expression equals $t^a$. For $a > 1$ the latter grows faster, for $a < 1$ the former is faster, and for $a = 1$ they are identical.


I know Binary Search is more efficient than Ternary search, but my results are opposite. Help interpreting results? I have a piece of code that applies recursive Binary and Ternary searches on sorted arrays of increasing size, i.e. 500, 1000, 2000, 4000, etc. The entire code segment is about 200 lines so I've been forced to upload it to Pastebin which you can find here. When the main method is executed, arrays are created and populated according to some heuristic, which here happens to be A[i] = 8 * sqrt(i). The arrays are then searched to see if they contain a key that's randomly generated and may or may not be in the array.

I've ran the tests over a dozen times and each time, the ternary search outperforms the binary search in terms of average comparisons needed before finding the key or knowing that it's not in the array. Shouldn't Binary Search have fewer comparisons if it's a better complexity (log(2) (n) instead of 2*log(3)(n))? Are my sample sizes too small or have I made a mistake in my code somewhere? For example, here's some sample output:

Binary search results:

Average number of comparisons for array of size 500: 7.4
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 8.1
Average number of comparisons for array of size 4000: 9.3
Average number of comparisons for array of size 8000: 9.0

Ternary search results:

Average number of comparisons for array of size 500: 4.6
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 5.3
Average number of comparisons for array of size 4000: 5.9
Average number of comparisons for array of size 8000: 6.0

Note: The 'y' variable in the code is the number of comparisons, this is an assignment and that's what it's supposed to be named as per the specs.

As already noted in the comments, the experiment doesn't measure the amount of comparison operations, but instead it measures the depth of the recursion needed to find the given number. Here's code that should produce a proper experiment (replacing value $\rightarrow target$, lo $\rightarrow low$, $hi \rightarrow high$, $y \rightarrow comparisons$ for readability):

int $\texttt{binarySearch}$(array $a$, int $target$, int $low$, int $high$, int $comparisons$):

$\quad$__int__ middle = $\frac{low+high}{2}$;

$\quad$ if ($a$[middle] $= target$) then

$\quad\quad$__return__ comparisons+1;

$\quad$ else if ($target$ < a[middle]) then

$\quad\quad$ return $\texttt{binarySearch}(a, target, low, middle-1, comparisons+2)$

$\quad$ else

$\quad\quad$ return $\texttt{binarySearch}(a, target, middle+1, high, comparisons+2)$;

And similarly for $\texttt{ternarySearch}$:

int $\texttt{ternarySearch}($array $a$, int $target$, int $low$, int $high$, int $comparisons$):

$\quad$__if__ $a\left[low + \frac{high-low}{3}\right] = target$ return $comparisons+1$;

$\quad$__else if__ $a\left[low+ 2\frac{high-low}{3} \right] = target$ return $comparisons+2$;

$\quad$__else if__ $target < a\left[low + \frac{high-low}{3} \right]$ return

$\quad\quad\texttt{ternarySearch}(a, target, low, low + \frac{high-low}{3}-1, comparisons+3)$

$\quad$ else if $target < a\left[low + 2\frac{high-low}{3} \right]$ return
$\texttt{ternarySearch}(a, target,$

$\quad\quad low + \frac{high-low}{3}+1, low + 2\frac{high-low}{3}-1, comparisons+4)$

$\quad$ else return $\texttt{ternarySearch}(a, target, low + 2\frac{high-low}{3}, high, comparisons+4)$

Hope this helps. You might still have to catch the $low > high$ case. Lastly, you test your cases by populating your array with $a_i = \sqrt{i}$, and then measuring with $\texttt{xSearch}(rand(max = 8\sqrt{n}))$. Is there any reason you test specifically that way? Your results will be skewed because you will (especially with larger $n$) query your array for relatively low indices. It is better methodologically, unless your target application is representative of this test case, to populate your list with numbers $1 \ldots n$, and then to shuffle the list at random, to produce a random permutation. Then query for item $rand(max=n)$.


Can a program language be malleable enough to allow programs to extend language semantics With reference to features in languages like ruby (and javascript), which allow a programmer to extend/override classes any time after defining it (including classes like String), is it theoretically feasible to design a language which can allow programs to later on extend its semantics.

ex: Ruby does not allow multiple inheritance, yet can I extend/override the default language behaviour to allow an implementation of multiple inheritance.

Are there any other languages which allow this? Is this actually a subject of concern for language designers? Looking at the choice of using ruby for building rails framework for web application development, such languages may be very powerful to allow designing frameworks(or DSLs) for wide variety of applications.

Converge has some pretty impressive meta-programming facilities.

  At a simple level, this can be seen as a macro-like facility, although it is more powerful than most existing macro facilities as arbitrary code can be run at compile-time. Using this, one can interact with the compiler, and generate code safely and easily as ITrees (a.k.a. abstract syntax trees).

which is a step up from Scheme's hygienic macros that allow referentially transparent macro definitions.

Mechanisms like quasiliterals have allowed constructing and destructuring of parse trees in other languages, but those are more often used for interacting with domain-specific languages (DSLs) instead of self-modification.

Newspeak's reflection allow exceptions to be implemented as library code.

  7.6 Exception Handling

  Because Newspeak provides reflective access (7.2) to the activation records(3.6), exception handling is purely a library issue. The platform will provide a standard
  library that supports throwing, catching and resuming exceptions, much as in
  Smalltalk.

Perligata:Romana demonstrates how an entirely new syntax can be skinned onto a language.

  This paper describes a Perl module -- Lingua::Romana::Perligata -- that makes it possible to write Perl programs in Latin.

Arguably not semantically significant, PyPy is an interpreter generator for languages whose semantics are specified in a highly statically-analyzable subset of Python, and they use it to experiment with new language constructs in Python like adding thunks to the language.

Also of interest might be Ometa.

  This dissertation focuses on experimentation in computer science. In particular,
  I will show that new programming languages and constructs designed specifically to
  support experimentation can substantially simplify the jobs of researchers and programmers alike.

  I present work that addresses two very different kinds of experimentation. The ﬁrst
  aims to help programming language researchers experiment with their ideas, by making it easier for them to prototype new programming languages and extensions to existing languages. The other investigates experimentation as a programming paradigm, by
  enabling programs themselves to experiment with different actions and possibilities—
  in other words, it is an attempt to provide language support for what if...? or possible
  worlds reasoning.

Alex Warth's dissertation demonstrates using an Ometa to define significantly new semantics (transactional semantics via worlds) in JavaScript+Ometa.


Random function "returns a uniformly distributed int". Does this mean the probability of every number is the same? Most functions that generate random numbers are described as:

  Returns a pseudorandom, uniformly distributed int value between 0
  (inclusive) and the specified value (exclusive)

If I use it to generate a number in the range [0..9], does uniformly distributed mean that the probability for 3 and 8 is the same?

As I understand it, if I run the function a sufficient number of times, I'll have the same number of occurrences for each number, 0 through 9.  Is this correct?

Alternatively, would we instead have a normal distribution where we would get more occurrences of the numbers 4, 5, and 6, as they are closer to the mean and hence have a higher probability of occurring?

Uniform distribution is when all values have the same probability. A random uniformly distributed integer in the range $0,\ldots,9$ will attain each of the values with probability $1/10$. In practice, you function is not truly random but only pseudorandom, so the probabilities won't be exactly $1/10$ but only very close to $1/10$.

Normal distribution is a probability distribution on real numbers. If we "bin" them then we get a normal distribution on the integers. If we "cap" it (there are several ways of doing this) then we get a probability distribution on a finite set of integers.


DCEL operations on quad-edges, Twin, Next, and Prev Suppose I have a quad-edge data-structure, and I want to be able to perform the operations of DCEL (twin, next, prev) on the quad-edge data structure. Let the current edge I am operating on be e. I know that e.twin would simply be e.rot.rot. I am just unsure about next and prev.

(Quad-Edge visualization given below.)

next should be equivalent to Lnext in the picture. Thus I tried to derive it and got e.rot.rot.rot.Onext.rot. prev should be equivalent to Lprev, which is the twin of Onext, i.e. e.Onext.rot.rot.

Is this correct? I am using quad-edges to prove properties on half-edges, so I want to make sure I got the basics correct before I proceed.

It looks like you took these diagrams from this CMU publication. This publication also refers to the C++ header cell/edge.hh, describing basic and derived operations on edges.

So, according to this header, operations Rot, InvRot, Sym and Onext are considered basic ones, and all the other operations - derived ones. The DCEL operations next and prev are equivalent to quad-edge operations Lnext and Lprev, which are defined in this header as inline functions (I'm dropping the C++ syntax and keeping the meaning):

e.Lnext = e.InvRot.Onext.Rot
e.Lprev = e.Onext.Sym

So, your formulas look correct, with slightly overused operation Rot.


What are the drawbacks of Normalized Mutual Information clustering evaluation method? What are the drawbacks of Normalized Mutual Information (NMI) clustering evaluation method?
For evaluating what clustering algorithms, is the NMI evaluation method suitable?

It is a matter of preference.

If you come with an information theory background, you'll like NMI better. If you come from a classification background, Rand index is pretty much the "accuracy" that you are used to, but on pairs.


In a LP problem Ax = b, how to solve for A instead of x? I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A.
Constraints are:

Each column of A must add up to 1.

A will start with some values being 0, and those must remain 0. In other words, A is sparse.

I know of algorithms to solve MOLPs like simplex and Benson's, but I'm seeing differences between how the inputs to those algorithms are expressed and how my problem is framed. What I'm looking for is how to transform or reframe my problem so that it can be solved by these algorithms, or alternatively, how an algorithm can be changed to accommodate the extra constraints.
The main differences I see are:

In most MOLPs of the form Ax = b, A is known and x is the thing to be solved for. In my problem, it's the opposite. x is fixed, and A is what needs to be solved for.

In my problem, x can contain both positive and negative values, and the objective is to get each row of b as close to zero as possible. I feel like this can be dealt with with slack variables, though, so that's not as much of an issue.

How to incorporate my constraints of A's columns adding up to 1, and A's sparcity.

Let $a_{ij}$ represent member of matrix $A$. This can either be the constant $0$ if you want $a_{ij}$ to be $0$ in the solution matrix, or a variable for a linear programming problem. Then you want to add linear constraints:
\begin{alignat}{2}
&\!\min_{a}        &\qquad& \sum_{i} s_i\\
&\text{subject to} &      & \forall j \left(\sum_{i}a_{ij} \leq 1 + \epsilon \right),\\
&                  &      & \forall j \left(\sum_{i}a_{ij} \geq 1 - \epsilon \right),\\
&                  &      & \forall_i \left(\sum_{j}a_{ij}x_j \leq s_i\right),\\
&                  &      & \forall_i \left(\sum_{j}a_{ij}x_j \geq -s_i\right).
\end{alignat}
This finds the optimal matrix $A$, with the desired elements set to $0$, that has columns adding up to $1$ (within a certain precision) and minimizes $\left\lVert Ax\right\rVert_1$.


Algorithm for weighted elliptic curve fit Background:
I was trying to detect a face solely on the bases of features and the confidence of the features found.
I am using a method to identify the features along with the response (confidence). Stronger features have higher responses.
I was trying to identify rotations of face. So, I was thinking about using ellipse bound to identify single face from image.

Question:
Is there any standard algorithm/standard library that does weighted elliptic curve fit for all the points?

(Mostly, the points would be in and around the ellipse with weights. However, there may be outliers. All points will have to be considered. The outliers will have less weight though.)

Inputs to the algorithm: coordinates of the points and the weights of the points.

Expected output from the algorithm: Minor axis, major axis, 2D orientation angle and the centre of the ellipse (using weighted curve fitting).

If there are 'n' number of features, I could calculate the centre of ellipse using the weighted average of features.
But, how would I determine minor axis, major axis and the rotation of the ellipse?

Attempts:
I tried with circle and it works very well. But, it does not have rotational information (it just draws a circle when face is rotated).
I found literature survey about elliptical curve fits using iterative methods.
I also ideated that rectangular curve fit would also do (as length of the rectangle can be major axis of ellipse and breadth of rectangle can be minor axis of ellipse).

But, I have been unable to observe any 'universal' solution. (For example, if the face is far from the camera, ellipse should be smaller accordingly. Many curve fitting algorithms use parameters which are translation variant)

Images for unweighted and weighted curve fitting:

Unweighted elliptical curve fitting would be as shown in left. It would probably just use least mean square fitting (with iterations for angles). But, this method is not desired as it would not account for the importance of features (for example, a feature of a shirt in an image would be "less important" than the one on face. Hard thresholding or binarising destroys information). Desired weighted elliptic curve fitting is as shown in right.

Fitting an ellipse to a set of points is sometimes known as elliptical regression.  Doing a Google search on that phrase will find you many resources on the subject (e.g., 1, 2, etc.; I can't vouch for any of these).

Let's focus first on the case where you ignore outliers.  Then, there are two methods.  One way is to use least-squares fitting and directly compute a best fit (e.g., the method of Fitzgibbon et al).  An alternative method is to use iterative methods, where you write an objective function $\Phi(p)$ that captures how well the ellipse parameters $p$ fit the data and then use gradient descent, the Gauss-Newton method, or some other method of optimization.  See, e.g., the Levenberg-Marquardt algorithm.

You'll also need to decide on objective function, or equivalently, on the error model.  Standard methods typically measure the "goodness of fit" by measuring the vertical error: for each point, you measure the length of the vertical line from that point to the fitted ellipse, and that is the error associated with that point; then, you sum up the squares of those errors.  This is the right model if you think that your measurement of the $x$-coordinate is perfect and your measurement of the $y$-coordinate is corrupted by random errors.  However, in practice that's probably often not the case; rather, we probably think that the location of the point has been shifted from the ellipse in a random direction.  In that case, a better measure of "goodness of fit" would be to measure the distance from the point to the ellipse (in whatever direction makes that distance minimized; not restricting only to a vertical distance), and then take the sum of those squared distances.  This does require you to use iterative methods to minimize this objective function.  A similar issue arises in linear regression (see here) and it might be easier to understand in that scenario first.

OK, that should handle the case where you have no outliers.  What if you do have outliers?  Then there are multiple reasonable approaches.  One is to use an objective function that is robust to outliers: for instance, use the median of the squared distances rather than the sum of squared distances, or use the Huber loss function instead of the square.  The downside of these methods is that they make it harder to compute the gradient and thus harder to apply iterative methods (and the non-iterative methods probably can't be used at all).

An alternative way to deal with outliers is to use RANSAC, which is a general procedure for dealing with outliers.  An overview is that you pick a small random sample of the points, hope that the random sample has no outliers, tentatively fit an ellipse to the sample, use the tentative ellipse to classify the points into inliers vs outliers based on how far they are from the tentative ellipse, then fit a new ellipse to all the inliers; and repeat 1000 times with 1000 different random samples, taking the best solution found.  This is a generic method for dealing with outliers that has the advantage of being usable with existing non-robust methods for elliptical regression.  You don't need to modify the loss function, objective function, or algorithm at all, since you are only applying elliptical regression to inliers, so you can use any method for elliptical regression without needing it to be robust to outliers.


Why do grammars in Chomsky Normal Form have derivations of length 2n-1? I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3):

  The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters has exactly 2n−1 steps.

I could get how $2n$ comes since there are only 2 variables on the R.H.S of each production but couldn't get how the expression $−1$ came in $2n−1$.

Let $n$ be the length of a string. We start with the (non-terminal) symbol $S$ which has length $n=1$.

Using $n - 1$ rules of form $(non-terminal) \rightarrow (non-terminal)(non-terminal)$ we can construct  a string containing $n$ non-terminal symbols.

Then on each non-terminal symbol of said string of length $n$ we apply a rule of form $(non-terminal) \rightarrow (terminal)$. i.e. we apply $n$ rules.

In total we will have applied $n - 1 + n = 2n - 1$ rules.

example

Observe following grammar in Chomsky-normal form.

$
\begin{align}
S & \to AB \\
A & \to BC | AC\\
A & \to h|b\\
B & \to a \\
C & \to z \\
\end{align}
$

Consider following derivation

$
\begin{align}
\text{Current string} & & \text{rule applied} & & \text{#rules applied} & & \text{#length of string} \\
S & & \text{\\} & & 0 & & 1 \\
AB & & S \to AB & & 1 & & 2 \\
BCB & & A \to BC & & 2 & & 3 \\
\vdots & & \vdots & & \vdots & & \vdots \\
A\cdots CB & & \text{[multiple rules]} & & n-1 & & n
\end{align}
$

This last line represents a string containing only non-terminals. You can see that a string containing $n$ non-terminals is derived using $n-1$ rules. Let's continue. Applying $n$ rules of form $A \to a$ to each non-terminal in the string above gives you a string containing only terminals and thus a string from the language decided by the grammar. The length of the string has not changed (it's still $n$) but we applied an additional $n$ rules so in total we have applied $n-1 + n = 2n - 1$ rules.

While this explanation hopefully gives you an intuitive understanding, I think it would be an useful excercise to construct a formal proof using induction.


Is monoid the category for untyped lambda calculus? If cartesian closed categories are the model for simply typed lambda calculus, then can it be said that a monoid is a categorical model for untyped lambda calculus?

$C$-monoids and their variants is what you are looking for. You can find further references and an account of what is what in Martin Hyland's Towards a Notion of Lambda Monoid.


Instruction Translation Imagine two machines of different architecture which produce output of a standard format.

If you have a program for one machine and can observe it's operation and output, what techniques exist to automatically produce an equivalent program for the alternate architecture?

By equivalent I mean produces equal output (by some equality relation) for equivalent input.

A "simple" way of solving this problem is to write an emulator for the first machine's instruction set on the second machine. Then set the first program as input to this emulator. One could also apply partial evaluation techniques to optimise things a little, which would result in an emulator that runs only the first program (and nothing else).


Enumerate all paths in a given series-parallel graph Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition.

I have a graph dataset that is of this type, and I have to enumerate all paths in the series-parallel graphs. Are there any existed algorithms? If so, what is the time complexity of it?

Treat SPG as DAG
We can see easily that every path from the source to the sink in a series-parallel graph (SPG) always goes nearer and nearer to the sink. It can never go backwards. There is no sideways. For the example in the illustration provided in the question, it can never move "up". This phenomenon can be proved easily by structural induction.
So we can view a SPG as a directed acyclic graph (DAG) naturally, where every edge is assigned the direction such that its head is nearer to the sink than its tail. For the SPGs in the illustration of the question, the head of an edge is lower than its tail.
Many Algorithms for DAG
There have been many algorithms that lists all paths from a source node to a destination node in a DAG such as this one and this one.
Time-complexity and space-complexity
For simplicity, assume the given SPG is a simple graph. (The case of multi-graph is not much different.) We have $|E|\le2|V|-3$. This inequality will not be used here; it is shown just to illustrate an SPG is a relatively simpler graph.
What is the maximum number of paths from source to sink in an SPG of $n$ vertices?
A rough estimate is $2^{\Omega(n)}$. In fact, we can show that the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, which is $\Theta(4^{n/5})$. So the worst time-complexity for all algorithms is about $\Omega(n4^{n/5})$.
If the algorithm stores that all paths in full detail before outputting anything or if the space used by output is counted towards usages, then the space-complexity is $O(n4^{n/5}$). However, if the space used by output is not counted towards space-complexity, the space-complexity can be reduced to $O(n)$ if we use a depth-first search such as the following code in Python, assuming the adjacency list of the SPG is given in the input.
def list_paths(g, path):
    children = g[path[-1]]
    if len(children) == 0:
        print(path)
    else:
        for node in children:
            path.append(node)
            list_paths(g, path)
            path.pop()

"""
Output all maximal paths from source in O(n)-working-space-complexity.
The parameter g is assumed to be an adjacency list that represents a valid DAG.
"""

def list_all_paths(g, source):
    list_paths(g, [source])

g = {1: [2, 3],
     2: [4, 5, 6],
     4: [7],
     5: [7],
     6: [7],
     7: [8],
     3: [8],
     8: [9],
     9: [10, 11],
     10: [12],
     11: [13],
     12: [14],
     13: [14],
     14: [],
     }

list_all_paths(g, 1)

""" Expected Output
[1, 2, 4, 7, 8, 9, 10, 12, 14]
[1, 2, 4, 7, 8, 9, 11, 13, 14]
[1, 2, 5, 7, 8, 9, 10, 12, 14]
[1, 2, 5, 7, 8, 9, 11, 13, 14]
[1, 2, 6, 7, 8, 9, 10, 12, 14]
[1, 2, 6, 7, 8, 9, 11, 13, 14]
[1, 3, 8, 9, 10, 12, 14]
[1, 3, 8, 9, 11, 13, 14]
"""

By the way, the number of all paths can be computed directly in $O(n)$ time and $O(n)$ space by either recursive dynamic programming or iterative dynamic programming following a topological sort.

Exercise 1. Show the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, where $\%$ is the remainder operator. (For $n=12$, the maximum number is $4\times5=20$)

Exercise 2.  Verify the algorithm above in Python still works if the given DAG g is not a simple graph, i.e., that might be parallel edges. What is its time-complexity and working-space-complexity when $g$ is a SPG that is not necessarily a simple graph?


Algorithm for compressing binary data that can efficiently be partially decompressed So I have been given the following problem and since I have no experience at all in this field, I would really appreciate some advice/guidance.

These are the requirements:

So three times per second a certain amount (fixed per session) of 32-bit values come in. These values have to be stored into a file with a timestamp per data-entry and it must be possible to at any time, with a given timestamp and interval, read out the values that are stored in that file.

This is all relatively simple to do, but this produces a 5GB file every 24 hours. If this file is zipped, it just leaves a 500MB file, so it is compressable but in that case you can't instantly retreive datapoints because you would have to unzip the entire file.

So I was thinking that this could be solved like this:

Buffer the first 10MB of sensor data.
Then sort all the values by the amount of times that they contain the same value. (Sensor data, so quite a few of the channels will
mostly contain stable values)
Run an algorithm that detects recurring patterns, replaces those patterns with shorter values and defines a table with the recurring patterns and their replacements.
The compress the buffer and save it to the disk and compress every new series of sensor data with the pre-defined table.

If this would be implemented properly, it should be possible to uncompress an individual datapoint and the file is sorted by timestamp so finding the right one should be trivial with a binary search.

So I guess the questions I'm having are the follwing

Is this at all possible? I do not expect compression results near Zip and 2x - 5x would be enough.
What is a good (and if possible semi-easy to implement) algorithm to find patterns in binary data? I have been doing some research and I mostly ran into algorithms that only apply to text data.

Any form of help is greatly appreciated!

Eliminate timestamps

If the data is sampled at regular intervals (e.g. three times per second), it is sufficient to store the timestamp of the first point and the interval. This enables you to calulate the offset from a timestamp and vice versa and grants you access to any datapoint in constant time.

Compression schemes

As others have already laid out, you will always lose the ability to seek when using a compression scheme. Compress blockwise and search within the blocks.

Lempel-Ziv-like algorithms

The Lempel-Ziv family and similar algorithms provide good compression for data with many/long reoccurring strings, but fail to recognize the relationship between integers in noisy or slowly changing sequences. Below are three sequences of integers: the first consists of constant values, the second counts upward and somehow resembles timestamps, and the third is noisy and represents a sensor reading.

$$[900, 900, 900, 900, 900, 900, 900, 900, 900, 900]$$
$$[890, 892, 894, 896, 898, 900, 902, 904, 906, 908]$$
$$[900, 890, 905, 901, 918, 892, 919, 916, 904, 920]$$

Zip will greatly reduce the size of the first sequence, have a hard time on the second and won't provide any compression on the third.

Delta encoding

To reduce the number of bits per number, the range of possible numbers must get smaller. If we incorporate the knowledge that values change slowly, we conclude that storing only the difference to the previous value yields values close to zero. The three example sequences above become:

$$[900, 0, 0, 0, 0, 0, 0, 0, 0, 0]$$
$$[890, 2, 2, 2, 2, 2, 2, 2, 2, 2]$$
$$[900, -10, 15, -4, 17, -26, 27, -3, -12, 16]$$

If we know the rate of change is approximately constant, as in case of timestamps, we can apply delta encoding twice. Below is a sequence of timestamps in original form and after applying delta encoding once/twice.

$$[96, 296, 497, 701, 904, 1102]$$
$$[96, 200, 201, 204, 203, 198]$$
$$[96, 104, 1, 3, -1, -5]$$

All we need now is a way to make the (on average) smaller numbers into less disk space.

Variable width integers

We can reduce the number of bits by using variable width integers that use less bits for smaller (by magnitude) numbers. The usual encoding is:

For numbers that fit into 7-bit signed integers, use one byte.
For larger numbers

store the 7 least significant bits in one byte.
set the MSB (continue-flag).
encode the remainder in the following bytes, using the same encoding.

This way 32-bit integers are encoded in 1-5 bytes, dependent on the actual value.

Conclusion

If possible, don't store timestamps at all (independent of compression).
Compress in blocks. Trade-off between access time and compression.
If the sensor readings are exactly constant for some periods of time, zip is the way to go.
If the sensor readings are approximately constant, use delta encoding.
If the timestamps are changing at approximately constant rate, use delta encoding twice.


maximum distance in between points in taxicab metrics - inserting and deleting points Let's define distance (taxicab metrics) between two points $(x_1, y_1)$ and $(x_2, y_2)$ as
$$|x_2-x_1| + |y_2-y_1|$$

Initially, there are given empty set of points.
I think how to find maximum distance between two arbitrary points (among inserted points). Possible operations are:
1. Insert point
2. Delete point
3. Find maximum distance (taxicab metrics) between two points.

I can do it using AVL tree (augmenting). Then I can insert and delete point in $O(\log n)$, whereas find costs $O(n\log n)$ where $n$ is number of points.

However, I consider is it possible to speed up operation Find.
Any ideas ?

Yes, I think you can get $O(\log n)$ for $find()$ too.

First, figure out how to implement $find()$ in $O(n)$ time. Here are some ideas:

You can iterate over all possible choices for the first point $(x_i, y_i)$.
Now the problem is that depending on where the other points are situated in relation to $(x_i, y_i)$ the distance formula can take $4$ different forms. Each one of them entails different signs for the coordinates. We don't know where the maximum will come from, so let's iterate over all $4$ cases. Let's say the first case is $(x_i, -y_i)$. You'll have to match this with a $(-x_j, y_j)$, and you'll want to match it with one that has the maximum sum $-x_j + y_j$. Your first concern is how to obtain this best sum in $O(1)$. Your second concern is convincing yourself this solution is correct, because nowhere have we made sure that the best $(-x_j, y_j)$ actually has $x_j <= x_i$ so that $|x_i - x_j| = x_i - x_j$. We're trying to maximize the result of each case, but we're taking all points into account for all $4$ cases, disregarding their position relative to the fixed point. Can you see why this actually works?


Lower bound on worst case pancake number? Given n pancakes, for each permutation we can compute the minimum number of pancake flips.  If we take the maximum over all possible permutations, we get the worst case pancake number $P_n$.

I think I can prove that $P_n \geq n$.  My argument is that I can start from the sorted pancake, and do a "anti-sorting" of the pancake by first flipping at position n, then position at n-1, n-2, etc.

For example, the case of n=5 would yield 34251.

Sorting such a pancake would take at best n steps.

Am I doing something wrong?

I assume that you are talking about the Pancake sorting (wiki) problem. Your argument for $P_n \ge n$ is rather informal.

The paper "Bounds for Sorting by Prefix Reversal (1979)" gives the lower bound $P_n \ge n$ in the Introduction section. Better lower bounds are also mentioned in this paper.

This paper "Pancake Flipping Is Hard" (2011) proves that determining the minimal number of moves for a given stack is NP-hard.


Building functionally complete boolean circuits out of trinary logic There are some not-very-commonly considered forms of trinary logic using 3 truth values. Even entire (unusual/rare) ternary computers have been built from it.

  Is there some knowledge or reference of how to convert some trinary logic systems into functionally complete boolean circuits/logic?

"Functionally complete" means all boolean functions can be computed. I am asking the more general question above in case the following more specific question does not have an answer. The motivation is more this specific following case. Consider the following "trinary truth table" for a single trinary operator.

   a b c

a  a c a
b  c b b
c  a b c

  Is it possible to somehow create functionally complete boolean circuits out of the single above trinary truth table operator? Or, maybe it can be definitively proven it's not possible?

I am also looking for any reference to that or something similar.

It is not possible to "invert" a value. Here is a list (computed in Python) of all unary functions achievable using your gate (the order of inputs is abc):

aaa
aba
abb
abc
aca
acc
bbb
cbb
cbc
ccc

An inverter would have one of the patterns ba?, c?a, ?cb (depending on which two values you choose to encode True and False), which none of these functions have.

On the other hand, it is possible to compute all monotone functions. Use a for True and c for False. The Or gate is realized as $x \lor y = (xy)$. The And gate is realized as $x \land y = ((((xb)y)b)a)$. (Note that your gate is symmetric but not associative.) There might be other solutions, e.g. using b and c.

Edit: Here is how to extend this to a complete simulation using double wires, according to vzn's suggestion. We represent True by (a,c) and False by (c,a). Negation is accomplished by swapping the two wires. The Or gate is formed by applying the Or gate described above for the first wire, and the And gate for the second wire. The And gate is defined analogously.

Further edit for the curious: here is how to compute all unary functions. We start with the list abc,aaa,bbb,ccc corresponding to the identity function and all constants. We now repeatedly choose two members and compose them, i.e. given functions $f,g$, we compute the function $(fg)$. Eventually the process stabilizes, that is generates no new functions, and we get the ten functions listed above.


Time complexity of removing duplicates in lists Question

I am wondering what is the minimum time complexity of get the unique value of a array in two conditions: keep the order or not.

For example, suppose we have a original array [3,6,1,1,2]. I want to get [3,6,1,2], this result keeps the original order and drops duplicates. If there is no need to keep the original order, [1,2,6,3] or [6,2,1,3] works fine.

I think time complexity of not keeping the order is $O(n)$ using a hashtable.
Under keeping order condition, approch may have a time complexity of $O(n^2)$.

  So, Am I right? Can someone give a detailed prove the time complexity of the best in each condition?

For more infomation:

I use Python, I find 2 python code for drop duplicates in a list.

How do you remove duplicates from a list whilst preserving order?
removing duplicates in lists

The running time is expected $O(n)$ for both problems.  Simply scan over the input list, and as you examine each item, add it to the hashtable; if it wasn't already present, output it.  The running time is $(n)$ because, with a suitable hash function, the expected time it takes to insert or look up an item in a hash table is $O(1)$.

The worst-case running time with this approach is $O(n^2)$, but you can make the probability of this happening exponentially small with a suitably chosen hash function.

Alternatively, if you care a lot about worst-case running time, you can replace the hashtable with a self-balancing binary tree and achieve $O(n \log n)$ worst-case running time for both problems.


Context free grammar for L={ ((ab)^n)^m } I want to write a cfg for the following language:

$ L = {((ab)^n)^m }$ $m,n >= 0$

this language produces (abababababab) where:  $n=2, m=3 \\ or \\ n=3, m=2$

I have no idea what to do with it!

No need for a CFG: this language is regular!

$$L = (ab)^*$$

Any number of $ab$s is in the language: just set $n$ to 1, and $m$ to the number of repetitions. So all you need is a Kleene star.

If you really want a CFG, you can do it like this:

$$S \rightarrow SX \mid \varepsilon$$
$$X \rightarrow ab$$

This is the "standard" way of translating a Kleene star into a CFG.


What's an Instruction Set Architecture I'm a beginner and I don't understand what an Instruction Set Architecture is (I read the wikipedia page related to it).
Can anyone explain it to me in a simple manner please?

It's a description of how a certain processor is designed, e.g. which commands it understands, how many registers it has, how it handles interrupts, etc. Any program you write (in assembly) or compile (e.g. from C) for a specific ISA can run on any processor that uses that ISA.

To run a program compiled for one ISA on a different ISA, you need an emulator that translates commands and potentially simulates registers, etc.

For example, desktop PCs use the x86 ISA family, which is why you can run Windows, Ubuntu, etc on any x86 processor.

Smartphones and Raspberry Pis have processors with the ARM ISA, which is why you can't run regular x86 Windows on a RaspPi, instead requiring one specially built for ARM.


Computing farthest pair of points in d dimensions Question: Given $n$ points in metric space, find a pair of points with the largest distance between them.

If we restrict ourselves to $d$-dimensional Euclidean space then, a naive algorithm of finding distances between all pairs of points in a space of dimension $d$ and selecting the maximum requires $O(dn^2)$ time.

However, finding a farthest pair for points in a plane can be done in time $O(n\log n)$. This is done by restricting our search to pairs of antipodal points on the convex hull. But, this approach does not scale well with higher dimensions.

Is there any solution better than the naive one either for the case $d=\Omega(n)$ (i.e., high dimensions) or for the case $d=O(\log \log n)$ (i.e., low dimensions)?

For the case $d = 3$, there exist $O(n\log n)$ algorithms due to Clarkson and Shor (randomized) and Ramos (deterministic). For higher dimensions there seem to exist only approximation algorithms, see for example a presentation of Vigneron. You can use the Johnson–Lindenstrauss lemma to reduce the problem (approximately) to dimension $O(\log n)$, in time $\tilde{O}(dn)$ (see for example Ailon and Chazelle).


Decidability of language containing strings of length equal to that of some substring of 1s in $\pi$? I read that the following language is decidable.

$\{w | w \in \{0, 1\}^* \text{ and } 1^{|w|} \text{ is a substring in binary expansion of } \pi \}$

The proof has been given by considering the two possible cases

Suppose it is true that there exists a minimal integer $N$ such that the
binary expansion of $\pi$ only contains substrings of 1 having length at most $N$.
That is, it contains substring $1^N$ but not $1^{N + 1}$. Define a corresponding turing machine $M_N$ such that it accepts the input string if it is of length $N$, otherwise rejects it. This machine decides the given language.
Suppose the binary expansion of $\pi$ contains substrings of $1$s of all lengths. Then the Turing machine that accepts all strings decides the given language.

We are not able to construct a single Turing machine that decides the language given, but one of these machines thus constructed will decide it but we do not know which. I don't quite understand how this language is decidable?

You are confusing knowledge and truth. Something may be true without us knowing precisely why. An object may exist without us being able to construct it.

If you belive in classical logic, then it is true that the maximum length of consequtive 1's in the expansion of $\pi$ is either finite or infinite. In each case, there exists a decision procedure for your language. Therefore a decision procedure exists.

But we do not know which of the cases happens, and so we not not know a particular decision procedure, even though one exists. If you don't like this line of reasoning, then you should ask for a constructive proof of decidability of your language.


Deep DFS traverse on graph According to chess rules, the (undirected) graph generated from the Knight move on a keypad is the following:

$$
\begin{array}{ccccc}
3 & - & 4 & - & 9 \\
| & & | & & | \\
8 & & 0 & & 2 \\
| & & | & & | \\
1 & - & 6 & - & 7
\end{array}
$$

The question is:

Consider the uniform distribution on all $n+1$-sequences $(s_i)_{i=0}^n$ starting with $s_0=0$.  What is the expected value and the standard deviation of $\sum_{i=1}^n s_i \bmod n$, under this distribution on sequences?

My naive approach is simply traverse every single sequence of fixed given length and do the calculation. But as the $n$ grows, the number of visits grows exponentially. For example, for $n=1024$, the number of sequences exceeds $6.04\times 10^{367}$. Hence a DFS or any kind of traverse is not a feasible approach.

So my second thought is using some analytic method. To get a few ideas, I first did some simulations on $\sum s_i$ (without modular reduction) with $10^5$ trials. The program generates the following distribution which doesn't match any obvious candidate so I couldn't advance further. So I am thinking if this is the correct way to tackle this problem. Any hint or help is appreciated.

You can compute the exact distribution of $\sum_{i=1}^n s_i$ using dynamic programming: for each vertex $v$, index $m \in \{0,\ldots,n\}$ and index $S \in \{0,\ldots,9m\}$, calculate the number of walks of length $m$ starting at $0$, ending at $v$, and summing to $S$. The running time is roughly $O(n^3)$ (the extra $n$ factor is due to the length of the numbers involved).

If you want an estimate, you should first find the stationary distribution of the Markov chain corresponding to a random walk on your graph. Given that, $\sum_{i=1}^n s_i$ has roughly Gaussian distribution with parameters that you can calculate from the stationary distribution; more specifically, roughly $N(n\mu, n\sigma^2)$ (this requires a version of the central limit theorem for Markov chains). This Gaussian approximation shows that the sum lies inside the interval of width $n$ centered around $n\mu$ with high probability, so taking modulo $n$ doesn't have much effect beyond shifting this interval to $\{0,\ldots,n-1\}$.


Does the k-clique problem became easier on sparse graphs? Some definitions, just to not create confusion:

A sparse graph is a graph that contains a number of edges less or equal than the number of vertices.
In $k$-clique problem we are given a graph and an integer $k$, and the task is to decide whether the graph contains a $k$-clique.

I think that even if we have a sparse graph, nothing changes for the $k$-clique problem (it always has complexity $O(n^k)$ if $k$ is less than number of vertices and it has complexity $O(n^n)$ if $k$ is equal to the number of vertices), but I'm not so sure about this.

Is a $k$-clique easier to find if the graph is sparse?

Let me not completely agree with Yuval's answer.

Indeed, in some sense sparsity does make a maximum clique problem easier, and this is proved also by solving it on real-life networks. Usually benchmarks for a maximum clique are pretty dense. And here is why.

If it is known an integer $k$ that is a lower bound of the clique number (or the number itself, but we are looking for a clique), then one can reduce the graph to $(k-1)$-core, that is the graph where each node has a degree at least $k-1$. The resulting graph might be considerably smaller in size and thus, for example, IP solver might get a huge boost. How to reduce: delete all vertices with degree smaller than $k-1$ until those exist.
If you look at sparsity not from the density perspective, but from the degeneracy perspective, things are even more formalized. Usually we say that graph is "sparse" when its degeneracy is low. And there exists FPT algorithms with running time around $O^{*}(2^{d/4})$ where $d$ is graph's degeneracy (here big-O star means that the algorithm depends polynomially on the graph size).

Conclusively, the maximum clique problem is immensely easier on sparse instances, though it still remains $\mathcal{NP}$-Complete (but FPT on degeneracy).


Which queue does the long-term scheduler maintain? There are different queues of processes (in an operating system):

Job Queue: Each new process goes into the job queue. Processes in the job queue reside on mass storage and await the allocation of main memory.

Ready Queue: The set of all processes that are in main memory and are waiting for CPU time is kept in the ready queue.

Waiting (Device) Queues: The set of processes waiting for allocation of certain I/O devices is kept in the waiting (device) queue.

The short-term scheduler (also known as CPU scheduling) selects a process from the ready queue and yields control of the CPU to the process.

In my lecture notes the long-term scheduler is partly described as maintaining a queue of new processes waiting to be admitted into the system.

What is the name of the queue the long-term scheduler maintains? When it admits a process to the system is the process placed in the ready queue?

I found an appropriate answer. I was asking about the job queue (which I already described). The diagram included in this answer comes from a  power-point that uses concise language to explain processes and schedulers and relates the topic to the diagram.

It may be of intrest to other users, also learning this topic, that sometimes time-sharing systems (such as UNIX) have no (or minimal implementations of a) long-term scheduler.

Check these sources for more information:

1.Wikipedia Article

2.Operating System Concepts (Pages 88-89)

 ©Bernard Chen 2007


Is every linear-time algorithm a streaming algorithm? Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear time algorithms. This is a bit bold as in general, a linear time algorithm can jump around at will (random access) which a streaming algorithm can not; it has to investigate the elements in order. I may perform multiple passes, but only constantly many (for linear runtime).

Therefore my question:

  Can every linear-time algorithm be expressed as a streaming algorithm with constantly many passes?

Random access seems to prevent a (simple) construction proving a positive answer, but I have not been able to come up with a counter example either.

Depending on the machine model, random access may not even be an issue, runtime-wise. I would be interested in answers for these models:

Turing machine, flat input
RAM, input as array
RAM, input as linked list

For streaming algorithms to be meaningful, they have to work with significantly smaller amount of work space than the input itself.  For example, if you allow the same amount of work space as the input, then you can trivially state any algorithm as a “single-pass streaming algorithm” which first copies the input to the work space in single pass and then only use the work space.

I think that it is typical to restrict the work space to at most polylogarithmic in the input size when talking about streaming algorithms.  Under this assumption, median selection does not have an O(1)-pass streaming algorithm by the result of Munro and Paterson [MP80]: any P-pass streaming algorithm for median selection on N elements has to store Ω(N1/P) elements.  On the other hand, median selection has a well-known deterministic linear-time algorithm [BFPRT73].

[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan.  Time bounds for selection.  Journal of Computer and System Sciences, 7(4):448–461, Aug. 1973.  DOI: 10.1016/S0022-0000(73)80033-9

[MP80] J. Ian Munro and Mike S. Paterson.  Selection and sorting with limited storage.  Theoretical Computer Science, 12(3):315–323, Nov. 1980.  DOI: 10.1016/0304-3975(80)90061-4


The sum of all integers less than n with a zero For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703

In this problem, n is smaller than $10^{18}$ , and the algorithm should finish within 1 second.

Here are some hints. First, as András suggests, it is easier to sum instead all integers without a zero, and then use the well-known formula $1+\cdots+n = n(n+1)/2$.

Let $S_n$ be the sum of zero-less numbers up to and excluding $n$, and let $T_k$ be the sum of zero-less numbers of width exactly $k$. We start by calculating $S_{10^k} = T_1 + \cdots + T_k$. We have
$$ \begin{align*}
T_1 &= 1 + \cdots + 9 = 45, \\
T_2 &= 11 + \cdots + 99 = (1 + \cdots + 9 + 10 + \cdots + 90)\cdot 9 = 45 \cdot 11 \cdot 9, \\
T_3 &= 111 + \cdots + 999 = (1 + \cdots + 9 + 10 + \cdots + 90 + 100 + \cdots + 900)\cdot 81 \\ &= 45 \cdot 111 \cdot 81.
\end{align*} $$
In general we get the formula
$$ T_k = 45 \cdot (1+10+\cdots+10^{k-1}) \cdot 9^{k-1} = 5 \cdot (10^k-1) \cdot 9^{k-1}, $$
from which it is easy to compute $S_{10^k}$:
$$ S_{10^k} = \frac{5}{9} \sum_{\ell=1}^k 90^k - \frac{5}{9} \sum_{\ell=1}^k 9^k = 50 \frac{90^k-1}{89} - 5 \frac{9^k-1}{8}. $$
For the general case, let's take as an example $n = 1234$. Zero-less numbers less than $1234$ come in the following forms:

Numbers less than $1000$: there are $1 \cdot S_{1000}$ of these.
Numbers of the form $1XYZ$ where $X<2$: there are $1 \cdot S_{100}$ of these.
Numbers of the form $12YZ$ where $Y<3$: there are $2 \cdot S_{10}$ of these.
Numbers of the form $123Z$ where $Z<4$: there are $3 \cdot 1$ of these.

The general case is similar. Suppose $n = d_k \cdots d_0$, where none of the digits is zero. Then
$$ S_n = d_k S_{10^k} + (d_{k-1}-1) S_{10^{k-1}} + \cdots + (d_1-1) S_{10} + (d_0-1). $$
If one of the digits is zero, say $n = 1230456$, then we can replace $n$ with $1230000$, and use the same recipe as before, stopping at the first zero digit.


Playing the game of life on an infinite grid I would like to implement Conway's game of life on a grid that is infinite in all directions. It should be initialized with an initial pattern and then run, e.g, like this:

set(-500,200)
set(-501,201)
set(-502,202)
start()

What data structure should I use?

Matrices usually start with (0,0). One solution is to keep track of the smallest and largest index of a living cell, and move the matrix accordingly (so in the above example, we will need a 3-by-3 matrix). However, this might require to copy the entire matrix whenever a new cell is born.

Another solution is to use a hashtable indexed by pairs of indices. However, in this case the calculation of the next step will be more expensive since cells will not be next to their neighbors.

Is there a better data structure for such infinite grid?

If you want to do better than iterating over each cell, or at least the range of live cells, use Hashlife.

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478?pgno=1

https://www.youtube.com/watch?v=l228ARRYkNE


Can a Language be determined by its kleene closure? Lets assume that we have access to a oracle (machine that determines without details) for $L^*$, can we calculate $L$ from this machine?
The cost of operation is measured by number of queries from oracle.

Can any property of $L$ like being prefix free or regular help?

What if the language be finite and instead of $L^*$ we have an oracle access to $L^k$ for a known $k$?

Consider $L_1 = \{a\}$ and $L_2 = \{a, aa\}$. In this case $L_1^* = L_2^*$. Thus a language is not uniquely determined from its Kleene closure.

Moreover you cannot determine a lot of information about a language from simply querying an oracle. Even if you had access to an oracle for $L$ itself rather than $L^*$, you would not learn much.

That is because you can only ever do a finite number of queries to the oracle. So for a finite number of strings, you know if they are in the language. It could be that every string, which you did not query, is in the language, which would make $L$ regular. Or it could be that none of the strings, which you did not query are in the language, which would also make $L$ regular. It is also possible to simply pick any arbitrary regular language $L'$ and assume that the rest of the strings are in $L$ if they are in $L'$ and vice versa. In that case $L$ would also be regular, because adding or removing a finite number of strings from a regular language would also produce a regular language.

The parts of $L$ which you did not yet query the oracle about could also have a non-regular structure, it could even be non-computable.

There are properties about $L$ which could help. For example if a property about $L$ was stated in such a way, that there would only be a finite number of languages satisfying the property, the problem would get a lot simpler.

For certain properties about $L$, it would even be possible to identify an $L$ from an infinite set of candidates, however such an algorithm would not necessarily terminate, if given an input not satisfying the property.

For example if it is required that $L$ consists of exactly one string, there are infinitely many candidate languages, but knowing the alphabet, it is possible to search for this string and find it in finite time. If this algorithm was executed on $Ø$ (which does not satisfy the property), the algorithm would never terminate.


Representing Integral domains in computer memory? Earlier I wrote this question about an algorithm computed on an integral domain.  However as commented I didn't suggest any particular ways of storing an integral domain in computer memory.  I set out to do this but found it a particularly difficult task.

It is in fact impossible to store all the integral domains in memory because the fields are uncountable1 and are a subset of the integral domains.  However I am not concerned with fields because they don't have any primes anyway.

How might one represent non-field integral domains in computer memory?  Is the set of all non-field integral domains countable?  If it is uncountable is there any useful subset of them that can be represented in computer memory?

1: The rationals are a field.  Every polynomial extension of a field is also a field.  Thus the number of polynomial field extensions of $\mathbb{Q}$ is the powerset of the irreducible polynomials on $\mathbb{Q}$ which is uncountable.

In general this question has no precise answer: the class of integral domains is not even a set, much less a countable set! (For example, for each set $A$, we can find an integral domain $D_A$ larger than $A$, e.g. $\mathbb{Z}[A]$, which is sufficient to show that integral domains can't be all gathered into a set).

In general you need to specify something to describe the elements of the set, and how to compute multiplication and addition.

A popular choice, which covers a large portion of the interesting examples, is to take a known ring or field $R$, typically $\mathbb{Z}$ or $\mathbb{Q}$, or some finite field $\mathbb{F}_q$, and look at some quotient ring of the form $D = R[X_1,\ldots,X_n]/(P_1,\ldots,P_k)$, where the $P_i$ are polynomials in the $X_j$.

Now it's not even clear that $D$ is an integral domain, which is equivalent here to the fact that $I=(P_1,\ldots, P_k)$ is irreducible. This can be determined using the Gröbner basis method as explained here.

Now there is an obvious representation for the elements of $D$: every element is represented by a polynomial, which we know how to represent, and do addition and multiplication on. The only issue is equality, since it needs to be modulo $I$. But this also is possible using known techniques, similar to the Gröbner basis ones.

It would be great if someone had implemented all of this up somewhere, though. Oh but they have! The Sage mathematical software toolchain builds on all of these observations to offer a ton of ways to concretely work with these kinds of rings. They even have an is_integral method for quotient rings!

Sage is a fantastic piece of software that I highly recommend, which probably does a lot of what you want.


Data structure that allows accessing elements by index and delete them in O(logn) I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would like to do both operations in O(logn) time.
Which data structure should I use to meet this requirement?
Clarification:
Deleting element on index(5) will move element from index(6) to index(5)
the element at index 6 change indexes so that it now has index 5
and 7th element changes to 6th so on ..

Take any self-balancing binary tree (e.g. AVL) and replace every node's key with the number of left descendants it has. This is easy to keep up-to-date for tree insertions/deletions (in $O(log n)$ time), and rotations (in $O(1)$ time).
Then to find the node with index $i$ you start at the root and repeatedly compare $i$ with the value of the current node $v$. If $i < v$ you go to the left child, $i = v$ you found the correct node and $i > v$ you subtract $i := i - v$ and go to the right child.


Size of constant depth circuit for digital comparator? Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers?

Two $n$-bit binary numbers can be compared using a digital comparator circuit.
The straightforward way to implement such a circuit is to compare the high-order bits; if they are the same then continue to compare the second most significant bits, and so on.
This circuit has size (measured in the number of gates) that is roughly quadratic in $n$, with linear depth.
By standard arguments, this can be folded up into an equivalent circuit of roughly the same size that has logarithmic depth (in $n$).

In fact, constant depth circuits of size $O(n^2)$ are sufficient for a digital comparator, if unbounded fan-in gates are allowed: see Heribert Vollmer's Introduction to Circuit Complexity (Exercise 1.4).
Is a tight lower bound known?

Comparison can be implemented by subtracting twos-complement numbers and then testing whether the most significant bit is 0 or 1.  Subtraction can be implemented as addition ($x-y = x + \overline{y} + 1$, where $\overline{y}$ is obtained by flipping all bits of $y$).  Addition can be implemented using carry-lookahead methods.

If you put all this together, I think you get a comparison circuit that uses $O(n)$ gates and has constant depth.

In particular, let $g_i = a_i \land b_i$ ("generate"), $p_i = a_i \lor b_i$ ("propagate"), $q_i = p_{i+1} \lor \cdots \lor p_{n-1}$, $t_i = g_i \land q_i$, and $c_{n-1} = t_0 \lor \cdots \lor t_{n-2}$ ("carry").  This lets you compute the carry into the most significant bit in constant-depth and $O(n)$ gates.  That's all you need for the results of the comparison (you don't need to compute the value of the other bits of the sum).  The reason this requires fewer gates than a full addition or full subtraction is that we only need the carry into the most significant bit, not all the carry bits.

Double-check my reasoning -- I could have gone awry somewhere.


How does the Y combinator exemplify "Lambda calculus inconsistency"? On the Wikipedia page for Fixed Point Combinators is written the rather mysterious text

  The Y combinator is an example of what makes the Lambda calculus inconsistent. So it should be regarded with suspicion. However it is safe to consider the Y combinator when defined in mathematic logic only.

Have I entered into some sort of spy novel?  What in the world is meant by the statements that $\lambda$-calculus is "inconsistent" and that it should be "regarded with suspicion"?

It's inspired from real events, but the way it's stated is barely recognizable and “should be regarded with suspicion” is nonsense.

Consistency has a precise meaning in logic: a consistent theory is one where not all statements can be proved. In classical logic, this is equivalent to the absence of a contradiction, i.e. a theory is inconsistent if and only if there is a statement $A$ such that the theory proves both $A$ and its negation $\neg A$.

So what does this mean regarding the lambda calculus? Nothing. The lambda calculus is a rewriting system, not a logical theory.

It is possible to view the lambda calculus in relation to logic. Regard variables as representing a hypothesis in a proof, lambda abstractions as proofs under a certain hypothesis (represented by the variable), and application as putting together a conditional proof and proof of the hypothesis. Then the beta rule corresponds to simplifying a proof by applying modus ponens, a fundamental principle of logic.

This, however, only works if the conditional proof is combined with a proof of the right hypothesis. If you have a conditional proof that assumes $n=3$ and you also have a proof of $n=2$, you can't combine them together. If you want to make this interpretation of the lambda calculus work, you need to add a constraint that only proofs of the proper hypothesis get applied to conditional proofs. This is called a type system, and the constraint is the typing rule that says that when you pass an argument to a function, the type of the argument must match the parameter type of the function.

The Curry-Howard correspondence is a parallel between typed calculi and proof systems.

types correspond to logical statements;
terms correspond to proofs;
inhabited types (i.e. types such that there is a term of that type) correspond to true statements (i.e. statements such that there is a proof of that statement);
program evaluation (i.e. rules such as beta) correspond to transformations of proofs (which had better transform correct proofs into correct proofs).

A typed calculus that has a fixed point combinator such as $Y$ allows building a term of any type (try evaluating $Y (\lambda x.x)$), so if you take the logical interpretation through the Curry-Howard correspondence, you get an inconsistent theory. See Does the Y combinator contradict the Curry-Howard correspondence? for more details.

This is not meaningful for the pure lambda calculus, i.e. for the lambda calculus without types.

In many typed calculi, it's impossible to define a fixed point combinator. Those typed calculi are useful with respect to their logical interpretation, but not as a basis for a Turing-complete programming language. In some typed calculi, it's possible to define a fixed point combinator. Those typed calculi are useful as a basis for a Turing-complete programming language, but not with respect to their logical interpretation.

In conclusion:

The lambda calculus is not “inconsistent”, that concept does not apply.
A typed lambda calculus that assigns a type to every lambda term is inconsistent. Some typed lambda calculi are like that, others make some terms untypable and are consistent.
Typed lambda calculi are not the sole raison d'être for the lambda calculus, and even inconsistent typed lambda calculi are very useful tools — just not to prove things.


Name for sorting algorithm "while not sorted, swap the FIRST unordered pair" A typical bubble sort steps through all pair indices until it reaches the end of the list, then starts a new pass.

For a toy problem, we have a variant that just performs the first available swap in each iteration and repeats until sorted. It does not continue from the position of the last swap.

Is there a standard name for this sort? It seems so trivial that it must have a name, but we were surprised not to find it on any obvious lists. It's just like, a raw comparison sort.

Bubble

4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
3, 2, 1, 4 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

Variant

4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
2, 3, 4, 1 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

Don't worry, this is not meant to be a good sorting algorithm, just for a fun thing.

In more detail, this variant of bubble sort finds the leftmost pair of adjacent items that are in the wrong order. Then it swaps those two items. This operation of "find and swap" is repeated until the given list is sorted. In other words, this variant of bubble sort swaps the items in the leftmost inversion of the given list repeatedly until the given list is sorted. (Note the two items in the leftmost inversion must be adjacent).

There is no standard or popular name for this variant of bubble sort, or so I believe.

I would call it left-bubble sort, a name that captures its conceptual intention. We could also have right-bubble sort, which swaps the items in the rightmost inversion repeatedly until sorted. We could also have random-bubble sort, which swaps two randomly-selected adjacent items that are in the wrong order repeatedly until sorted. If we do not even require the two items to be adjacent, we can have random-swap sort. Depending on how the inversion is selected randomly, "random-swap sort" can become bogo-sortopt, bozo-sortopt, and bozo-sort+opt that  appear in this article.

The above description of left-bubble sort does not specify how to find the leftmost inversion in each iteration. A naive implementation may always comparing the first two items, then the next two items and so on until it finds the first inversion or stops. We can observe that the initial part of the list during the left-bubble sort is sorted. Since there cannot be any inversion in the initial part of the list, we can optimize the implementation by just comparing the item that was just moved to the left with the item right before it without comparing the initial adjacent items.

Whether we use the naive implementation or the optimized implementation above, left-bubble sort behaves exactly the same as the simplest insertion sort, in terms of the states the given list goes through until sorted. The simplest insert sort here corresponds to the first pseudocode at this Wikipedia page, which is implemented in Programming Pearls (2000) by Jon Bentley.

Here is an illustration of the states produced by left-bubble sort.

4, 3, 2, 1    <- 4 is considered inserted into the expected place.
3, 4, 2, 1    <- 3 is inserted into the expected place
3, 2, 4, 1
2, 3, 4, 1    <- 2 is inserted into the expected place
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4    <- 1 is inserted into the expected place

In particular, left-bubble sort builds the final sorted array (or list) one item at a time, which is the defining characteristic of "insertion sort" according to that Wikipedia page. We can thus treat (the optimized version of) left-bubble sort as another name for the simplest insertion sort.


How to solve a recurrence relation with a sum? How do I solve the following recurrence relation?

  $$
T(n) = 1 + \sum_{j=0}^{n-1} T(j).
$$

I thought of solving it by generating its recursion tree. I found that the height of the tree would be equal to $n$ but wasn't able to find the cost of each level.

Here are several ways to solve your recurrence relation.

Guessing

Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this guess, you can verify it by summing the appropriate geometric series: if $T(m) = 2^m$ for $m < n$ then

$$
T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-1} 2^m = 1 + (2^n-1) = 2^n.
$$

Computing the first few values

Another approach which is very  useful is to compute a few values of the sequence:
$$ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... $$
If we're lucky, as in this case, we might spot a pattern. If not, it's always a good idea to consult the on-line encyclopedia of integer sequences. A quick search would reveal the sequence A000079.

Creative telescoping

In the method of creative telescoping, we try to find a combination of terms that results in major cancellation. In our case, we can try $T(n+1)-T(n)$:

$$
T(n+1)-T(n) = \sum_{m=0}^n T(m) - \sum_{m=0}^{n-1} T(m) = T(n),
$$
and so $T(n+1) = 2T(n)$. Unrolling this rule, we deduce $T(n) = 2^n T(0) = 2^n$.

Back-substitution

Another way to look at the preceding trick is to try to "back-substitute" the recurrence inside itself:

$$
T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-2} T(m) + T(n-1) = 2T(n-1),
$$

from which we can proceed as before.

Generating series

A very general method is that of generating series. Let $G(x) = \sum_{n=0}^\infty T(n) x^n$. Since $1/(1-x) = \sum_{n=0}^\infty x^i$, multiplying by $1/(1-x)$ is like computing "running sums":
$$
\frac{G(x)}{1-x} =
\sum_{n=0}^\infty \sum_{m=0}^n T(m) x^n =
\sum_{n=0}^\infty (T(n+1)-1) x^n = \\ \frac{G(x)-T(0)}{x} - \sum_{n=0}^\infty x^n = \frac{G(x)-1}{x} - \frac{1}{1-x}.
$$
From this it is not hard to deduce
$$
G(x) = \frac{-1/x-1/(1-x)}{1/(1-x)-1/x} = \frac{-(1-x)-x}{x-(1-x)} = \frac{1}{1-2x} = \sum_{n=0}^\infty 2^nx^n,
$$
and so $T(n) = 2^n$.

Recursion tree

It is also possible to deduce the value of $T(n)$ using a recursion tree. Each path in the recursion tree for $T(n)$ corresponds to a sequence of decreasing numbers $n_0 = n, \ldots, n_\ell$, where $n_\ell \geq 0$ (possibly $\ell = 0$); this is because all leaves are labeled by $1$. The set of possible decreasing sequences is in one-to-one correspondence with subsets of $\{n-1,\ldots,0\}$, because once we know which numbers appear, we also know their order. The number of subsets of $\{n-1,\ldots,0\}$ is exactly $2^n$.


The language of all borderless words Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please?

A word $w$ has a border $u$ if $u$ is both prefix and suffix of $w$ (and $u$ does not equal $\lambda$ or $w$).

The borderless words are also known as unbordered or bifix-free ("A note on bifix-free sequences", PT Nielsen, in a paper as early as 1973).

The language of unbordered words is not even context-free, see the paper "Inverse star, borders, and palstars" by Ramparsad etal, in TCS with a preprint on ArXiv. The technique to obtain this result is Ogden's Lemma, an extension of classical pumping, and discussed elsewhere on this forum.


Maximum possible file size in the filesystem A file system with 300GByte disk uses a file descriptor with 8 direct block address ,1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes.What is the maximum possible file size in this filesystem?
This is previous year question I could not get the idea and couldn't solve it...plz help

You may find the answers here and here

I should have posted this as comment but I don't have enough reputation points.


Creating Best Clusters of Objects Based on Distance Between Them I have an array of images. And, there is a function that calculates the distance between two images.

I wish to cluster the images based on this distance. So the clusters contain images that are all at short distance to each other.

So only the distance between two images can be used to form the clusters. An image has no usable properties on their own. As many common clustering algorithms expect objects to have usable properties, it seems I can use these algorithms.

To limit computational complexity, I've introduced a few thresholds to decide if two images may end up in the same cluster:

calculated distance (I want to optimize for shortest distance, but above a certain distance, images are not close enough to ever share a cluster)
input array distance (e.g. an image at index 23 may only cluster with images up to index 123)
creation data interval (images created more than N hours apart, may not share a cluster)

Some details:

There can be up to 100k images.
Roughly 25-50% of images will be 'unique' and do not end up in a cluster with others. Of the remainder, most will be expected to end up in clusters with a size below 10, with 5% outliers above that.
The maximum cluster size is something I want to set somewhere between 10 and 50.

Given the above and the nature of the image set, a graph (image: edge, calculated distance: vertex) would consist of disjoint parts consisting of up to a few hundred images. So the algorithm needs to be able to cluster sets of well below 1000 images.

The clusters must be optimised for distance, such that closer images end up together in a cluster. I'm aware that parameters like minimum and maximum cluster size would be needed; it's a play between creating a few large clusters with a higher maximum distance, or more smaller clusters with images that are closer together.

What kind of algorithm(s) could I use?

You can use Cluster Edge Deletion, however, the problem is NP-hard.

Create a graph where the vertex set is the set of your objects, and you create an edge between two objects if the distance is at most the threshold.

Now, the Cluster Edge Deletion problem is to find the set with fewest edges to delete such that the remaining graph is a cluster graph (a graph whose connected components are cliques).  In this solution, every object belongs to a cluster in which the distance to every other object is bounded by the threshold.

Alternatively, you can run $k$-means (with increasing $k$) until you're satisfied with a solution.  Take note that the $k$-means algorithm is randomized and gives an approximate solution (as also this problem is NP-hard), so you might want to run the algorithm several times per $k$.


Unique ID from date and rotating offset Hopefully this is the right board for my question, We are facing an issue creating a unique ID from the following inputs :

datetime (can be present more than once in the same set, cannot not be present in 2 different sets)
offset ( an integer representing each line position in the set, the offset will be reset when switching to next/previous set)

As output we would like to get a unique ID, which will be used for sorting purpose later.

The concrete example for this issue is the rotating logs files. They will be collected into same database/table and later-on they will be shown and sorted/filtered based on this unique id.

Example :

log1.txt (set 1)

2017-08-06 10:36:07,988 something (let say offset=54)
2017-08-06 10:36:07,988 something (let say offset=108)
2017-08-06 10:36:07,988 something (let say offset=162)
...
2017-08-06 10:40:06,488 something (let say offset=1200)  => A

log2.txt (set 2)

2017-08-06 10:40:06,788 xyz (let say offset=20)
...
2017-08-06 10:40:07,488 xyz (let say offset=200) => B
...

Obviously a naïve uid function by adding offset as milliseconds to the date will lead to collusion, the frequency of the collusion cannot be foreseen, it depends on the logged text and the rotation size. (A & B for collusion example).

Regards

You can create a unique identifier by concatenating the two fields in question. If there are files where both fields are identical, concatenate an extra field disambiguating them.


Combine abstract factory with decorator pattern I'm working on a simple project of software engineering that should combine two patterns.
I choose Abstract Factory and Decorator patterns to modify (dynamically) objects created with the concrete Factory classes.
My question is: is delegating object decorations to those Factory classes a design error?

Here's the UML scheme:

I don't see that as a problem.

Factory are used to implement the Dependency Injection (DI) pattern, where one wish to dispense a section of code from having to know how to construct objects of a certain class, which could involve other secondary classes and render the aforementioned section of code more coupled to the rest of the codebase. The less coupling, the easier it is to update the code — the client part (that section of code), or the service part (the object being created — Cake in your case).

When it comes to decorators, you are essentially describing an algebra on the object: you start from some class instance (Cake object), and by applying an operator (the decorator), you obtain another object from the same class (to be precise, it's a subclass, so it's more akin to a refinement operation, but for our purpose, ignoring that part is OK).

The client code needs to know about that algebra, as a part of how it may manipulate the object, so you have to disclose this information. Now it could be in the form of a set of methods on the Cake class, a set of functions acting as operators,  or methods on a class implementing that algebra.

The 2nd option might be more complicated to implement,  if decorators need to share some information on the Cake class only available at runtime; you'd have to implement the DI pattern on them,  and you would end up with either the first or the 3rd solution.

The remaining options are equivalent from the client code point of view, not adding more dependency either way.


Least number of comparisons needed to sort (order) 5 elements Find the least number of comparisons needed to sort (order) five elements and
devise an algorithm that sorts these elements using this number of comparisons.

  Solution: There are 5! = 120 possible outcomes. Therefore a binary
  tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$
  ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number
  of comparisons needed to sort (order) five elements is 8.

Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it can't be done in 7 comparisons?

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance.

The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline:

Sort the first two pairs.
Order the pairs w.r.t. their respective larger element.

Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.
Insert $e$ into $[a,b,d]$.
Insert $c$ into the result of step 3.

The first step clearly takes two comparisons, the second only one. The last two steps take two comparisons each; we insert into a three-element list in both cases (for step 4., note that we know from $c<d$ that $c$ is smaller than the last element of the list at hand) and compare with the middle element first. That makes a total of seven comparisons.

Since I don't see how to write "nice" pseudocode of this, see here for a tested (and hopefully readable) implementation.

Ph.D. thesis (Stanford University) by H.B. Demuth (1956)

See also Electronic Data Sorting by H.B. Demuth (1985)
Sorting and Searching
by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)


Could an alternating approach yield a fairer solution to the stable marriage problem? With the G-S algorithm solution to the stable marriage problem, the proposers get the best possible stable matches, while the reviewers get the worst possible stable matches. This is because the proposers keep walking down the list from their best preference downwards till the stable solution is found, while the reviewers walk up the list from where they start.

To improve the fairness to both parties, consider an alternating variant of the algorithm, where in each cycle, proposers and reviewers exchange roles (for example, in each cycle, men and women switch between the role of proposer and reviewer). Would this terminate with a stable match? If yes, would the resulting stable match be fairer to both parties than the original G-S algorithm?

The idea of the Gale-Shapley algorithm is to consider the graph of possible matchings (i.e. marriages) and trim edges that cannot happen in a stable matching. Eventually, we cannot trim any more edges, and then we can read from the graph a stable matching, indeed both the man-optimal and the woman-optimal stable matchings. For this view, check out for example the beginning of Section 6.3 in this paper. In your algorithm, you haven't specified how the final matching is generated (though perhaps it follows from the proposal terminology), so it's hard to evaluate the result. However, since the graph you'll get in the end is probably the same as in the symmetric Gale-Shapley algorithm, the usual extraction procedures probably wouldn't produce anything other than the two optimal stable matchings. Perhaps it's best if you gave a complete pseudocode of the algorithm, and also tested it on a few sample inputs.

The stable matchings form a lattice structure, so you might think it helps to take the two optimal matchings and generate something "in the middle". However, since they are the top and bottom elements in the lattice, neither the join nor the meet would produce anything new. Instead, there are ways to generate random stable matchings, and these might be fairer to both parties.

For more information, consult Knuth's Marriages Stables (available also in English) and Gusfield and Irving's The Stable Marriage Problem: Structure and Algorithms.


How to prove that context sensitive languages are closed under intersection and complement? This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context sensitive languages will also produce a context sensitive language.

From the context sensitive closure properties Wikipedia, and princeton.edu.
I know that those languages are closed under intersection and complement.

I have spent too much time on finding the formal prove of those statements. Where / How can I find the proofs? Or how to prove them by myself? Can anyone point me to a reference ? Can any one post here the proofs ?

The first closure property, closure under intersection, is a DIY proof if you choose the right model for the context-sensitive languages. By defining them with the help of linear-bounded automata you can run two of these automata successively to test (nondeterministically) for acceptance of the intersection.

Second, closure under complement, is hard! It used to be a famous open problem until solved independently by Immerman and Szelepcsényi. It is quite a surprising proof, how to prove complement for a nondeterministic automaton. The technique is called inductive counting and works for larger families of complexity classes: NSPACE($s(n)$)=co-NSPACE($s(n)$), where context-sensitive equals linear nondeterministic space.


Expected number of independent sets of size $k$ in random graph $G(n,p)$ I am looking for a formula for determining the expected number of independent sets of size $k$ (for arbitrary $k$) in a random graph $G(n,p)$. Here $n$ is the number of vertices and each edge is included with independent probability $p$. I would like to be able to calculate this for arbitrary $p$ if possible.

I have come across the article [1] which provides a formula for the special case $p = 0.5$.

I have also come across the article [2] which in p. 12 provides a value for some cases other than $p = 0.5$, so I would assume it is known for some $p$ values other than $0.5$.

My questions are:

Do you know how one shows, or could you provide a reference for the formula shown in [1] for the case $p = 0.5$. The paper gives some references but they are about clique problems and I am not sure how I could arrive from them to the result shown in that paper.
Is there a known formula for arbitrary $p$?
If not, for what $p$ values is a formula known and where could I find such formulas?

[1] Chromatic and Independence Numbers of $G_{{n}, {{1}\over{2}}}$

[1] Feo, Thomas A., Mauricio GC Resende, and Stuart H. Smith. “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 42, no. 5 (1994): 860–78.

The probability that a specific set of size $k$ is independent is exactly $(1-p)^{\binom{k}{2}}$ (why?). Linearity of expectation shows that the expected number of independent sets of size $k$ is $\binom{n}{k} (1-p)^{\binom{k}{2}}$ (why?).

If you can't follow this calculation, please follow Denis Pankratov's advice and look up linearity of expectation and indicator random variables.


Church-Rosser on an example In lambda calculus, starting from $KII$ we can get by a single $\beta$-reduction to either

$\lambda y.II$

or $KI$

Now, according to Church-Rosser, these should be reducing into a common normal form. But the first reduces to $I$ and the second to $\lambda y.\lambda z.z$.

Am I doing wrong $\beta$-reductions or the theorem holds only on some condition? I do not see a common reduct here.

Remember that $1)$ application is left associative and $2)$ application has higher precedence than abstraction. This is:

$1)$ $ A B C = (A B) C \neq A (B C)$
  $2)$ $ \lambda x. A B = \lambda x. (A B)  \neq (\lambda x. A) B$

So

$KII = (KI)I = ((\lambda x y. x) I) I = (\lambda y. I) I = I$


Intersection of context free with regular languages The intersection of a context free language L with a regular language M, is said  to be always context free. I understood the cross product construction proof, but I still don't get why it is context free but not regular.

The language generated by such an intersection has strings that are accepted both by a PDA and a DFA. Since it is accepted by a DFA, shouldn't it be a regular language? Plus, if the intersection is regular, it also implies context free, since all regular languages are also context free.

Can someone explain to me why the language obtained by such an intersection is not regular?

If $L$ is context-free then there is a PDA $\mathscr{P}$ that accepts it. If $M$ is regular then there is a DFA $\mathscr{F}$ that accepts it. The intersection language consists of the words that are recognized by $\mathscr{P}$ and $\mathscr{F}$.

Any word that is in the intersection is accepted by $\mathscr{F}$, but not all words that are accepted by $\mathscr{F}$ are in the intersection: only those that are also accepted by $\mathscr{P}$.

The cross product proof consists of constructing an automaton $\mathscr{P} \otimes \mathscr{F}$ which contains the mechanics of both $\mathscr{P}$ and $\mathscr{F}$, and which accepts only words for which both sides accept. The cross-product automaton is a PDA (and therefore the recognized language is context-free) — intuitively, because the cross product with an $n$-state DFA consists of taking $n$ copies of $\mathscr{P}$ and adding $(q,a,[q])$ arrows between matching states in $\mathscr{P}$ where the DFA has $a$ arrows. The result is not a finite automaton in general (not even a non-deterministic one) because the $\mathscr{P}$ part relies on the stack and this reliance does not go away in $\mathscr{P} \otimes \mathscr{F}$ in general.

A trivial example is that $\mathscr{A}^*$ is regular, and if $L$ is context-free but not regular then $L \cap \mathscr{A}^* = L$ is context-free but not regular.


Proving using a SAT solver that KB entails D Suppose you're given this KB:
$$KB = (A, A ⇒ B, A ⇒ C, B ∧ C ⇒ D)$$
How would you show using a SAT solver that $KB \vDash D$?

TL;DR: Use the SAT solver to search for a counterexample.
To check that $KB \models \varphi$, you need to know whether there is any assignment that is consistent with $KB$ but that does not satisfy $\varphi$.  In other words, you need to know whether $KB \land \neg \varphi$ is satisfiable or not.  If $KB \land \neg \varphi$ is satisfiable, then you have found a counterexample that demonstrates that $KB \not\models \varphi$.  If $KB \land \neg \varphi$ is not satisfiable, then you proven that $KB \models \varphi$ is true.
Now apply that to your specific example.


MST with half the edges the maximum weight I have been cracking my head over the following question -

  You are given an undirected connected graph with an even number of
  edges. Half of the edges have weight less than C (possibly with
  repetitions), and the other half of edges all have weight C. Is it
  true that every MST of the graph includes the same number of edges of
  weight C?

  If Yes, describe an efficient algorithm for finding the number of
  edges of weight C in every MST of the graph. The output is between 0
  and |E| / 2, no need to return the MST.

  If No, show a counterexample.

My work so far -

I've managed to prove to myself that the number of C weighing edges included in a spanning tree (not minimum) can be anywhere between 0 and |E| / 2 (using a cycle with C edges crossing it).

Obviously, I couldn't find a counterexample yet. It feels like what's preventing me from creating two different MST's with a different number of C edges is that for creating a graph that has more than one MST you need to have cycles, and if a C edge is contained in the cycle it won't be chosen (Kruskal). That is the direction I'm leaning towards for a proof, proving a more general claim obviously.

Assuming the above is in fact true, I need to show an efficient algorithm for finding the number of C edges in every MST. The question states there is no need to return an MST, so it seems like there should be a better algorithm than finding the MST and counting the number of C edges in it, meaning this algorithm should be more efficient than sorting. From what I showed above, it could be anywhere between 0 and |E| / 2 so I'm kinda lost here too.

If the answer is "yes", then there is an easy algorithm: just compute any MST and report the number of edges with weight $C$.  If they all have the same number of edges with weight $C$, then the particular MST you compute won't change the answer.

So now you want to know whether the answer is yes.  To see that it is, observe that each MST is constructed by running the greedy algorithm on a specific linear extension of the partial order induced by the weights.  In your case, the edges $E$ partitioned into sets $E_{<C}$ and $E_C$, and every edge in $E_{<C}$ comes before any edge in $E_C$ for all of these linear extensions.  That tells you that every MST is made of a spanning forest $F$ on the subgraph induced by $E_{<C}$ and some edges from $E_C$; since all the choices for $F$ have the same size, we are done.


The heaviest induced subgraph problem I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ of $G$ that maximizes the sum:
$
\sum_{e \in E'} w_e(e) + \sum_{v \in V'} w_v(v)
$.

The problem is NP-Hard (by the reduction from maximum clique problem) so any suggestions for approximation solutions (even greedy) and links to the literature would be appreciated.

$\newcommand{\R}{\mathbb{R}}$
Let's consider a special case of the problem where vertex has negative weight and edges have positive weight.
So $w_v: V\to \R^-$ and $w_e: E\to \R^+$.

Finding the heaviest induced subgraph is equivalent to a min-$st$-cut computation on a suitable graph. We will refer to the slides about densest subgraph in this presentation.

Indeed, minimizing $w_e(E(V'))+w_v(V')$ is equivalent to minimizing $(-w_v(V')) + \frac{1}{2} w_e(E(V',\bar{V'})) + \frac{1}{2} \sum_{v\in \bar{V'}} \deg(v)$. (Note the degree here are weighted degree, that is $\deg(v) =\sum_{e:v\in e} w_e(e)$)
The derivation of the above fact is similar to slide 21.
Then, this can be solved easily by modeling it as a min-$st$-cut in some other graph (see slide 22). It is crucial to have negative vertex weights and positive edge weights for the reduction to work.


What are the implications of Homotopy Type Theory? I've recently come across the topic of homotopy type theory and I'm interested to learn more. I have a very limited background in type theory.
Can anyone tell me, in functional programming terms or through practical examples, how exactly is HoTT going to change the way we view mathematics, and what are the implications of HoTT on proof assistants? Thanks!

I won't lie: I don't understand the homotopy part of homotopy type theory. But I have a decent grasp of Univalence, which is the axiom at the heart of Homotopy Type Theory (HoTT).
The main idea of univalence is that we treat equivalences (essentially, isomorphisms) as equalities. When two types are isomorphic, you have a way to get from one to the other and back, and the round-trip is the identity in both directions. But there's no way to lift properties between isomorphic types: if you have a proof that 2 is the only even prime for unary natural numbers, you can't automatically lift the proof of that property to binary natural numbers, even though you can convert 2 back and forth between the formats.
The eliminator for equality (sometimes also called the $J$ axiom) allows you to lift any property between equal things. So if we have an equality for every isomorphism, then we could transport the above property from unary to binary numbers. This is what univalence gives us: an axiomatic way to lift properties over isomorphisms.
The main implications of this are:

For programming: univalence is specifically about equality types, which are dependent types, so it only really affects dependently typed languages. What it allows us to do in those languages is to write code using efficient data structures, show that those structures are isomorphic to simpler structures, prove things about the simpler structures, and automatically lift those proofs back to the automatic structures.
For math, it makes formal something that has been implicit for a long time, which is that mathematicians tend to treat isomorphic things as if they were equal. Univalence provides a foundation that justifies this. So it brings the "formalized" math of proof assistants closer to the way mathematicians think of math.

There are also some cool things you can do with univalence. You can define Higher Inductive Types (HITs), where in addition to giving data constructors for inductive types, you give path constructors, which are equalities that must hold. When you pattern match, you then have to show that you preserve these equalities.
HITs allow you to do things like "define integers as a natural plus a sign but, but ensure that positive and negative 0 are truly equal.
However, there are some strange consequences to univalence. First, it means that we cannot have $Refl : x \equiv x$ as the sole way to construct an equality proof, because univalence lets us construct equalities between things that are definitely not syntactically identical. This means that univalence is incompatible with "Uniqueness of identity proofs" and axiom $K$. In practice, this means that the rules of dependent pattern matching must be weakened to be consistent with univalence. Jesper Cockx has a whole line of research on how to do this well.
The other problem is that we lose "canonicity" i.e. the idea that every term can be fully evaluated to a value in canonical form. For equality, Refl is the only canonical proof of equality. So this means that when running programs, sometimes we get "stuck" on the use of univalence as an axiom. This makes sense: we basically said "pretend I have a function that transforms isomorphisms into equalities". We never gave that function, so if we try to evaluate code that calls it, we'll get stuck.
The main effort to solve this problem is Cubical Type Theory. Cubical models equality in such a way that canonicity is preserved, but univalence can be proved as a theorem in the language. So univalence is now not an axiom, it's an actual function that can be applied.
If you're interested in this more, there are two main resources I'm familiar with. The HoTT Book is the canonical reference. There's also  Univalent Foundations in Agda, which is less focused on the homotopy theory, and more on the implications that univalence has for logic. I'm sure there are also more books I'm not familiar with. The Cubical Agda paper is also good.