Understanding the basic concepts in memory organisation (Before actually proceeding to the question, I want to confess that this is a homework question, please do consider it and help me in improving my understanding a bit more.)

I have recently started learning computer organisation and architecture. I have gained fair understanding for how caches are organised, how mapping between cache and main memory takes place (direct , fully and set-associative mapping), what is a page table(what are pages, blocks etc.), i can that say I have basic knowledge of segmentation , paging, virtual address and physical addresses.( at the basic level ofcourse).

Well I have come across this question:

  A computer has 46-bit virtual address ,32- bit physical address, and a three
     level page table organisation. The page table base-register stores the
     base address of the first level table(t1), which occupies exactly one
     page.Each entry of t1 stores the base address of the page of second level
     table t2. Each entry of t2 stores the base address of the page of the third
     level table t3. Each entry of t3 stores a page table entry (PTE).
     The PTE is 32 bit in size. The processor used in the computer has a 1MB
     16-way set associative virtually indexed physically tagged cache. The cache
     block size is 64 Bytes.

First of all I am facing difficulty in just imagining such type of a virtual computer. can any one help me by giving a simple steps on How to realize such a virtual computer on paper, or just how to understand what is given in the question. What is really asked? How would one represent a computer having a 46-bit virtual address and having three level page table?

  What is virtually indexed and physically tagged cache?

After reading what is given above, I feel that I just know the terms but I am unable to relate them together to solve problems. I will be glad If someone tries to explain how my thought process should be understand and apply these concepts practically to solve such types of problems.

Some questions based on the above paragraph:

What is the size of a page in KB in this computer?
What is the minimum number of page colours needed to guarantee that no
two synonyms map to different sets in the processor cache of this computer?

A good resource where such problems are actually taught to solve will a appreciated. Good articles and views are most welcome.

One can derive the page size from knowing that the page table has three levels, the virtual address space is 46 bits (assume byte addressing), and a PTE is 4 bytes. P bits (where P = log2(page_size)) of the virtual address are not involved in the translation (these provide the offset within the page), so the three levels must translate a 46-P bit address value.

Each node of the page table contains page_size/PTE_size entries, and so each node covers log2(page_size/PTE_size) bits, which is P-2 bits. The page size can then be derived since 46 = (P-2)*3 + P.

(In a simple hierarchical page table, the first level is a single page [in the given design providing 2(P-2) entries]. Each valid entry points to a page-sized table at the second level. Likewise each valid entry in the second level points to a page-sized table in the third level. Each valid entry in the third level provides a page translation. If all the first and second level entries were valid, there would be 2(P-2) * 2(P-2) third level tables each with 2(P-2) entries. Thus 2(P-2)*3 entries would be available, each covering 2P (page_size) bytes.)

With respect to page coloring, one must determine the number of bits that are not part of the page offset which are used for indexing the cache. The number of sets is equal to cache_size/block_size/associativity, so to index to a specific set requires log2(cache_size/block_size/associativity) bits. The offset within the block uses log2(block_size) bits. Using C= log2(cache_size), B= log2(block_size), and A=log2(associativity), C-B-A bits are used to index the set and C-B-A+B, i.e. C-A, bits are used to address the given byte.

Since only P bits are provided as part of the page offset, C-A-P bits use virtual address bits. In order to avoid the problem of two different virtual addresses with the same physical address mapping to different sets, the virtual addresses of any physical pages that are so shared can be colored, i.e., share the same value for the C-A-P virtual address bits. (This forces them to map to the same set. With tagging based on physical addresses, this is sufficient to avoid aliasing issues like a write to one virtual address not updating a cached entry at the same physical address but a different virtual address.)

Each index group is called a color, so to provide C-A-P virtual address bits requires 2(C-A-P) colors.

(The above assumes an "ordinary" cache. Indexing not using simple modulo 2N, e.g., skewed associativity, would have different coloring requirements; but such complexities are typically ignored for problems like this.)


Algorithm to maximize dot product between two sets of vectors I have two sets of vectors $(\mathbf{l}_i)_{1\le i \le n}$ and $(\mathbf{r}_i)_{1 \le i \le n}$. Each vector $\mathbf{l}_i$ is in $[0,1]^4$, same for $\mathbf{r}_j$. I'd like to maximize the dot product $\mathbf{l}_i \cdot \mathbf{r}_j$, i.e. find tuples $(i,j)$ s.t. $\mathbf{l}_i \cdot \mathbf{r}_j$ is as big as possible.

To be clear, if $\mathbf{l}_i=(\mathbf{l}_{i,1},\mathbf{l}_{i,2},\mathbf{l}_{i,3},\mathbf{l}_{i,4})$ and $\mathbf{r}_{j}=(\mathbf{r}_{j,1},\mathbf{r}_{j,2},\mathbf{r}_{j,3},\mathbf{r}_{j,4})$, then:

$$\mathbf{l}_i \cdot \mathbf{r}_j=\sum_{k=1}^4 \mathbf{l}_{i,k} \mathbf{r}_{j,k}$$

The number of tuples I'd like to find should be ideally a parameter of the algorithm, i.e. find the $K$ tuples $(i,j)$ that lead to the greatest values of $\mathbf{l}_i \cdot \mathbf{r}_j$. I won't mention $K$ in the complexities below, let's say $K \ll n$.
I'm looking for $O(n \log^k n)$ ideas. The naive algorithm takes $\Theta(n^2)$ time, which is too big for me ($n \approx 2^{20}$).
My first idea was to try to solve the problem in dimension 2, with the additional constraint on the input $|\mathbf{r}_j|=1$. In that case it is easy to design a $O(n \log n)$ algorithm: sort all $\mathbf{r}_j$ according to their angle with $(1,0)$, then for all $i$, find $\mathbf{l}_i$ in that list by binary search.

In my opinion, intermediary tasks might be:

Try to generalize the formula $\mathbf{u} \cdot \mathbf{v}=|\mathbf{u}| |\mathbf{v}| \cos(\mathbf{u},\mathbf{v})$ to dimension $4$.
Try to remove the condition $|\mathbf{r}_j|=1$ from the algorithm in dimension $2$.

I have no idea on how to solve these two problems.

I'm asking this in a single question because I'm also interested in more general algorithms that may give approximations (e.g. that solve the "maximum dot product" problem in arbitrary dimension).

As a completely different approach, assuming that $d < \log n$, one can generate $O(\log n)$ random vectors $w_i$ with unit norm. For each $w_i$ we look at $\langle l_i, w_i \rangle$ and $\langle r_i, w_i \rangle$. Take the top largest $O(\sqrt n)$ from each list, as potential candidates. After completing we have $O(\sqrt n \log n)$ candidates, and then we check the dot products between the pairs. It is important that $d < \log n$ so that $O(\log n)$ vectors are sufficient to cover the unit sphere well. In your case where $d = 4$ it would seem to be that $d << \log n$.


Explanation of Heavy light decomposition Can anyone explain heavy light decomposition of trees or give a resource to read it from? I have already gone through http://ipsc.ksp.sk/2009/real/solutions/l.html which is the best i could find but still could not understand its working completely.

I am taking this from http://wcipeg.com/wiki/Heavy-light_decomposition

Essentially the decomposition tells you which, if any, subtrees at a node N take up more than half the weight of the tree rooted at N.  Such a subtree gets an edge coloured with the word "Heavy" the rest get coloured "Light".  Note that there can be at most one heavy subtree at any given node.

Here is an implementation in Haskell.

module HLDecom where

{- |
  This data type has data in the leaves and nodes
  that collect a list of subtrees each of which is
  paired with b-type data.  The b should be thought
  of as information on the edge connecting the node
  to the subtree.
-}
data Tree a b = Leaf a | Node [(b,Tree a b)]

data Color = Heavy | Light

size :: Tree a b -> Integer
size (Leaf x) = 1
size (Node ns) = 1 + sum (map (\(a,b) -> size b) ns)

{- |
  The Heavy-Light decomposition of a tree is a
  colouring of the tree's edges with
  either Heavy or Light.

  If the size of a subtree at a node is more
  than half the size of the tree at the node,
  then the edge connecting the node to that
  subtree is heavy otherwise it is light.

  It should be obvious that at any given node,
  there can only be one such heavy subtree
  (there can only be one subtree that
  has > 1/2 the weight), and further we can find
  this subtree by finding the maximum size subtree.
  If this size is more than half the size of
  the whole tree, then it is colored Heavy.

  The implementation below could certainly be
  improved for efficiency; however, the focus
  on being direct and clear.
-}
--hlDecomp :: Tree a b -> Tree a Color
hlDecomp (Leaf x) = (Leaf x)
hlDecomp (Node ns) =
  let
    sizeOfNode = size (Node ns)
    heavyLight = map (\(b,tree) ->
       if size tree >
          sizeOfNode `div` 2
          then (Heavy,tree)
          else (Light,tree)) ns
  in
    Node heavyLight


Computing hash of a compound key Why is the initial value of hash 17 and not 0?

/**
 * Returns an integer hash code for this date.
 *
 * @return an integer hash code for this date
 */
@Override
public int hashCode() {
    int hash = 17;
    hash = 31*hash + month;
    hash = 31*hash + day;
    hash = 31*hash + year;
    return hash;
}

https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Date.java.html

There is no compelling reason that I'm aware of.  The hash algorithm would also work about as well with an initial value of 0, as far as I can see.


Prove or disprove that the following language is context-free Hi guys I was given this question:

  Prove or disprove that the following language is context-free: $$ L = \{ \alpha 2 \beta : \alpha,\beta \in 1(0+1)^*, [\alpha]_2 < [\beta]_2 \} $$ where $[x]_2$ is the numerical value of the string $x$ interpreted as a positive number in base 2. For example, $[1110]_2 = 8+4+2 = 14$, $[10100]_2 = 16 + 4 = 20$, thus $1110210100 \in L$, while $111021110 \notin L$ and $1010021110 \notin L$.

I can't figure out either way if its context free or not. When I was trying to prove it was context free with a DPDA I got stuck because I don't know how to compare two binary strings when one is in reverse of the other because when you put the string left of the 2 into a stack and pull it out it comes out reversed. Because of this I can't compare if one is bigger than the other if they are the same length.

On the other hand I tried using the pumping lemma to prove its not context free. For a string $ 1^{m}210^{m} $ I can show for two cases when $ v^{k}xy^{k} $ is composed of just 1's on the left side or right I can either underpump or overpump. For the third case when $ v^{k}xy^{k} $ is composed of the run of 1's on the left and the 0's on the right pumping in either direction doesn't seem to make the left binary number the bigger value.

I am stuck with either direction I have tried so could somebody point me in the right direction?

You can use the pumping lemma in this way.

By closure properties, if $L$ is context free and it is intersected with the regular language $R = \{ 1^* 0^* 2 1^* 0^*$} the resulting langauge $L' = L \cap R$ is still context free.

We can apply the Pumping lemma to $L'$ and prove that it cannot be CF, so $L$ is not CF as well.

Let $p$ be the pumping length; pick

$$z = 1^p \, 0 \, 0^p \; 2 \; 1^{p} \, 1 \, 0 ^p$$

First note that if $vwx$ is entirely contained in the first half, then pumping it one time is enough to make the first half longer than the second half; making $[\alpha]_2 > [\beta]_2$ and pushing the string out of $L$

If $vwx$ is entirely contained in the second half, then pumping it zero times is again enough to make the first half longer than the second half; making $[\alpha]_2 > [\beta]_2$ and pushing the string out of $L$

So $vwx$ crosses the middle of $z$.

At least one, but at most $p$ positions are contained in $vwx$, so $v$ must be in the $0^p$ before the center and $x$ in the $1^p$ after the center.

If $|v| <> |x|$ then - as above - pumping them one (or zero times) would make the first half longer.

But if $|v| = |x| = k \geq 1$ we can still pump it zero times getting the string:

$$z^0 = 1^p \, 0 \, 0^{p-k} \; 2 \; 1^{p-k} \, 1 \, 0^p$$

but

$$ [ 1^p \, 0 \, 0^{p-k} ]_2 >= [ 1^{p-k} \, 1 \, 0^p ]_2$$

(for $k=1$ we have $1^p 0 0^{p-1} = 1^{p-1} 1 0^p$)


Is this "cycle" condition sufficient for unique minimum spanning tree? Given a connected, undirected, weighted graph $G$, the condition

  The maximum-weight edge in any cycle of $G$ is unique.

is not necessary for $G$ to have a unique minimum spanning tree (MST).

However, is this condition sufficient for $G$ to have a unique MST?

Answer My Own Question by attempting to prove that the condition above is sufficient for a graph $G$ to have a unique MST. I am asking for reviews. Thanks in advance.

First, for each cycle, the unique heaviest edge in it must be not in any MST. Consider the remaining graph $G'$, obtained by keeping removing the unique heaviest edges in cycles from $G$. All MSTs are part of $G'$. If we can show that $G'$ is a spanning tree, then $G'$ is the unique MST of $G$.

$G'$ is connected because each edge removed belongs to a cycle when it was removed.
$G'$ is acyclic because we are keeping breaking cycles.
Thus, $G'$ is a spanning tree.


Different iterations of regular expressions A four-part question dealing with formal languages and regular expressions:

How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string?
How many using just *, +, and •?
How many using just + and •?
How many using just •?

First, note that, over any finite alphabet, there are countably infinitely many regular expressions. This is immediate from the fact that regular expressions are finite strings (which gives the upper bound) and that $a$, $aa$, $aaa$, ... are all regular expressions (which gives the lower bound).  From now on, I'm just going to say "infinite" instead of "countably infinite" because we've established that nothing in this context is uncountable.

If you're allowed to use $\varepsilon$, there are infinitely many regular expressions that match $abcd$: for example, $abcd\epsilon^n$ for all $n\geq 0$.

If you're allowed to use alternation, there are infinitely many: for example, $abcd$, $(a+a)bcd$, $(a+a+a)bcd$, ... .

If you want regular expressions that match only the string $abcd$, Kleene star isn't useful. If it's applied to any regexp that matches any non-empty string, then the resulting regexp will match strings of arbitrary length, so will be invalid. If it's applied only to regexps that are equivalent to $\varepsilon$ then we could have already used those regexps to get infinitely many regexps for $abcd$, as in the $\varepsilon$ case. The only remaining case is that $\emptyset^*\equiv\varepsilon$, so Kleene star and $\emptyset$ together yield infinitely many regexps for $abcd$. However, this case isn't relevant in your case structure, since you eliminate $\varepsilon$ and $\emptyset$ from consideration at the same time.

If you're only allowed concatenation, then there is exactly one regular expression that matches $abcd$: $abcd$ itself.


Decidability of $E_{TM}$ and $A_{TM}$ for "erasing" Turing machines Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization argument not work:

  Assume $A_{ETM}$ is decidable, and $R$ decides $A_{ETM}$. Then, $R$
  accepts $\langle M, w \rangle$ when ETM $M$ accepts $w$. Let $D$ be
  an ETM that accepts exactly when $M$ does not accept $w$. Then, $D$
  rejects $\langle D \rangle$ when $D$ accepts $\langle D \rangle$, a
  contradiction.

Why does this not work?

Alternatively, if $A_{ETM}$ is decidable, why is $E_{ETM}$  undecidable? The conventional contradiction argument would not work in that case, and I don't know how to reduce it any other way.

Thanks in advance!

An ETM (Erasing Turing machine) can be safely simulated due to its erasing-only nature.

It can only pass the right-end of the input to a finite limit or else would plunge off to infinity. Adding this to the input itself, we can conclude that the languages accepted by an ETM must be context-sensitive.

So, an ETM can only accept some context-sensitive language. As a result, $A_{ETM}$ is decidable.

Where is the source that says $E_{ETM}$ is undecidable?


Algorithm to find best solution I am writing a software as small project in TypeScript/JavaScript and got to a problem i cant solve:
A Company makes a new contract with a customer and wants to order materials. There are serval suppliers with fix delivery costs.  Each supplier can offer some of the materials with different pack sizes and prices. What is the best approach to get the materials for the lowest price? I wanted my App to automatically suggest the best order.

* You can order at multiple suppliers;  You can order more materials than needed *

Further explanation:
I know what materials needed for the contract, for Example (Input):

750 of Material 1
250 of Material 2
500 of Material 4
50 of Material 5

I know the delivery Costs and material costs of each supplier. Delivery costs are only paid once for each supplier. I want to get the best solution to order the materials (cheapest).

Output should be a list like:
Ammount - Product of supplier - Supplier

Example:

Material 1

1 x 500Q,P40 from Supplier 1
2 x 125Q,P12 from Supplier 3

Material 2

1 x 250Q,P60 from Supplier 3

....

Your problem is hard, but not too hard.

Start with a subproblem: For one material, you have various package sizes with different cost. You also require a certain amount of material. Find the cheapest way to buy your material.

To do that, use dynamic programming: Let's say you need 5000 units. Find in turn the cheapest way to buy at least 1, 2, 3, ..., 5000 units. The cheapest way for 0 units is buying nothing. To buy at least K units, you either buy one package with size >= K, or you buy one package with size k < K, then buy packages with total size at least K - k at the lowest possible price. Of the choices you have, you use the cheapest one.

Second subproblem: Find all sets of possible suppliers. Just try all possible subsets - for n suppliers there are $2^n$ possible subsets of suppliers, and reject all subsets that don't contain any supplier for a material that is required.

Then for each possibe subset of suppliers, find the cheapest way to buy each material. Add up the cost for the materials, plus the delivery cost. And then take the subset of suppliers that was cheapest.

For small problem sizes, this shouldn't take too long. Of course the problem looks NP-complete if you turn it into a decision problem, so your execution time will grow exponentially with the problem size.

Finding the cheapest way to buy each material seems to be the most time critical. Think how you can optimise it by finding packages you should never buy (if you have a pack of 25 costing 12, and a pack of 24 costing 13, you would never buy the 24), and amounts you don't care about (in your example with pack sizes 100, 200 and 500, your total is always a multiple of 100).


Image segmentation of a high resolution 2D binary image into clusters, threads and points I use python3 script to find out the area proportion of pixel clusters, threads and points in my image. They are originally 8-bit greyscale TIFF images with a resolution of 2048x2168 pixels. I have binarised it into an image composing of the matrix (white) and component particles (black). The particles have random morphologies. I would like to widely categorise them as:

Points which can range between 1x1 to 3x3 blocks of independent square pixels completely surrounded by the matrix
Threads which are linear or diagonal sets of continuous pixels of at least 3 pixels in length and at most 3 pixels in width
Clusters which are any randomly shaped closed morphologies with more than 10 pixels in overall area (or any arbitrary high value)
Others which by any chance is not included the three listed above

Here is an Example(400x400) portion of the image.

First of all, I am confused about the order of progress in this situation. I could scan the whole image pixel by pixel and extract the points in my first step. A second scanning can see for threads and final scanning can look for clusters using boundary tracing.

As you can see, the component is spread in a very uneven manner. To a human eye, the threads appear as blocks with very low aspect ration (AR). Points as noises and clusters as blocks of distinguishable larger areas. Therefore the accuracy level of this classification scheme does not needfully be a high score. The objective, however, is minimal user interaction (fully automatic). One another thing to note is that holes within clusters or threads (that does not break it) can be ignored. The ultimate aim is to get the area percentage of each of the objects so that the detection method can be limited keeping it in mind.

Some specific questions:

Let us say that I identify a large cluster of pixels within the image. How can I split this into a component cluster (high AR) and thread (low AR)? (something similar to Watershed Algorithm)
Should I go for the OpenCV contouring method like Border Following or border tracing (and later ignoring the holes) or something more suitable
I was curious to know if there have been approaches in the past that used random sampling of pixels instead of a pixel by pixel scanning across the entire image.

I would like to know the steps a computer scientist would follow in such a scenario. I am a beginner in image processing and any reference material would be appreciated. For anybody interested in metallography, the images are micrographs and what we see are defects. I am trying to separate cracks, porosities and other openings based on pixel density.

I would suggest decomposing the black pixels into connected components using standard algorithms.  (For instance, OpenCV has an implementation of this, I believe.)  Then, classify each component based on your rules.

(I'm not seeing what boundary tracing offers over connected component labelling, but you could try it too if you wanted.)

I recommend you try it and see how well it works.  This should be pretty straightforward to try.  I'd caution against over-thinking things and try to figure out the perfect solution before trying anything.  In this domain, often multiple rounds of "try something, identify its shortcomings, and improve" are necessary, because it can be hard to predict how something might fail.

If this works, it will be very efficient (it runs in linear time) and quite simple, so you don't need to worry about it being a "brute force" or "naive" method.  I wouldn't worry about micro-optimizations at this stage.  Instead, implement it and see how well its results seem to be.  Only after you are happy with the quality of the results should you even begin to think about potentially optimizing it -- but I would expect that it might be so fast that there is no point in spending any energy trying to optimize it.

You might discover that the connected components are too large and include both clusters and threads.  If so, that's telling you that your rules aren't quite right yet, and you'll need to investigate more sophisticated solutions.  One possible approach might be to apply a morphological operation, such as a thinning operation or erosion, to remove the threads, compute connected components on the result, and use that to identify clusters.  You might also be able to compute a skeletonization of the shapes, and use that to identify threads (e.g., compute the "thickness" of the shape at each point: for each point $p$ on the skeleton, compute the distance to the boundary in the direction perpendicular to the direction of the skeleton at $p$).  Once you've identified each shape separately, you might be able to compute its bounding box and the fraction of pixels within the bounding box that are black, and use a threshold on that fraction to distinguish clusters from threads -- if you can separate the cluster from the thread.  You might need to experiment a bit to see what works well for your images.


Hoare triple for assignment P{x/E} x:=E {P} I am trying to understand Hoare logic presented at Wikipedia,
Hoare logic at Wikipedia
Apparently, if I  understand correctly, a Hoare triple $$\{P\}~ C ~\{Q\}$$ means

  if P just before C, then Q holds immediately after C, as long as C terminates. (A)

However, the assignment axiom schema seems to be interpreted in a different way:

$$\frac{}{\{P[x/E]\} ~~x:=E~~   \{P\}}$$

The wikipedia says:

The assignment axiom means that the truth of $\{P[x/E]\}$ is equivalent to the after-assignment truth of $\{P\}$. Thus were $\{P[x/E]\}$ true prior to the assignment, by the assignment axiom, then $\{P\}$ would be true subsequent to which. Conversely, were $\{P[x/E]\}$ false prior to the assignment statement, $\{P\}$ must then be false consequently.

I think the Hoare triple only affirms that if P[x/E] before x:=E, then P(x) holds after x:=E. It DOES NOT affirm, by its definition, that if P(x) holds after x:=E, then P[x/E] holds before x:=E.

My naive question is, how can $\{P[x/E]\}$ before the assignment can be equivalent to $\{P\}$ after the assignment? Does this contradict with point (A) at the beginning of my post?

Notice that what Wikipedia is saying is that

  The assignment axiom means that the truth of $\{P[x/E]\}$ is equivalent to the after-assignment truth of $\{P\}$.

In other words, ($P$ holds after the execution of $x:= E$) if ($P[x/E]$ holds before the execution). This is equivalent to the definition $A$ you provided, which is generally a more intuitive definition for Hoare triple.


What are the modern alternatives to Backus–Naur form and what are their advantages? I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of all possible notations and the most prevalent one. Though it looks like to be an ancient piece of art. Now I'm wondering that if you want to invent a new programing language what modern alternative you should use and why?
These are what I have found so far:

ISO extended Backus–Naur form (EBNF)
W3C-BNF
augmented Backus–Naur form (ABNF)
Extreme BNF (XBNF)
Translational Backus–Naur form
ANother Tool for Language Recognition (ANTLR)
Wirth syntax notation (WSN)
Van Wijngaarden grammar
Microsoft “M” modeling language
Compiler Description Language (CDL)
Xtext grammar language
definite clause grammar (DCG)
META II

I would like to know what are the advantages and disadvantages of these options?

Answer 1: The question is meaningless as written.
You are mixing different kinds of notations here that are intended for different purposes.

BNF and ABNF are concrete notations for writing the abstract concept of a context-free grammar.
"Van Wijngaarden grammar" refers either to an abstract type of grammar a la "context-free grammar", or to a concrete notation for writing this type of grammar. Van Wijngaarden grammars are strictly more expressive than context-free grammars. In fact, parsing them is undecidable in general, making them more like an esoteric programming language in some respects.
ANTLR is a particular software tool for generating parsers. It has a language for writing grammars that it accepts as input. Like most other parser generators, ANTLR includes specialized features in its grammar language for manipulating the generated parser code. For example, it is possible in an ANTLR input file to directly insert Java code that is to be executed by the generated parser when a certain token is encountered. This sort of feature only makes sense in the context of a parser generator.

Answer 2: It mostly doesn't matter.
If, as you say, "you want to invent a new programing language," there are two situations where writing down a grammar is relevant:

Writing a parser as part of the compiler implementation. Your choice of how to express the grammar here is dictated by how your parser is implemented. Whether you use an ANTLR/Yacc/Bison-style parser generator, a parser combinator library, etc. will determine what your grammar looks like in the source code.

Writing a language specification. Most programming language specifications are written to be read by humans, not computers. Therefore, anything that is sufficiently clear to a human reader is an acceptable choice of notation. It is common for a language specification to define its own grammar notation, rendering the particular choice of notation largely irrelevant. For example, the "Lexical Structure" chapter of the Haskell 2010 Language Report starts with a "Notational Conventions" section that defines how the grammar will be written.


What is the evidence that that types are more basic specifications, and specifications are more detailed types? In the book Type Theory and Functional Programming [Thompson, S 1999] the author explains the relationship between specifications, types and proofs of functions:

The equivalent specifications can be thought of as suggesting different program development methods: using the ∃∀ form, we develop the function and its proof as separate entities, either separately or together, whilst in the ∀∃ form we extract a function from a proof, post hoc.
This analysis of specifications makes it clear that when we seek a program to meet a specification, we look for the first component of a member of an existential type; the second proves that the program meets the constraint part of the specification.

On this same topic, the commenter writes:

Specifications are in a way "more detailed" types. Or, state the other way, types are more basic specifications. Martin-Lof type theory is precisely about fusing the two ideas into one.

My question is: What is the evidence that that types are more basic specifications, and specifications are more detailed types?

As Gilles points out, it depends on what you count as types. If you mean by types something like
types in Java or Scala or Haskell, then this is clearly true.

One easy way to see this is (simplifying a bit) to use a general framework of
specifications to express the behavioural content of types as a
specific case of specification. The best framework to do this at the
moment is $\pi$-calculus as a programming language and Hennessy-Milner
logic as a specification language. I suggest to choose $\pi$-calculus
because it's expressive, and well studied. In particular, most
sequential programming languages are easily seen to be (behaviourally
equivalent to) specific sub-calculi of $\pi$-calculus.  Hennessy-Milner
logic is an expressive modal logic that can be used to nail down
processes up to behavioural equivalence.  Now we take an arbitarty
type, say the function space constructor
$
   int \rightarrow bool
$
and express the constraints this type imposes on programs as a
specification in Hennessy-Milner logic.

Conversely, we need to show that specifications are strictly more
expressive than types but that's fairly obvious, for we cannot specify
e.g. that a method is sorting its input array.


Functional programming with branches that have no order? I was wondering if there is any programming style in which the outcome does not depend on the order of statements or groups of statements such as guards. Vaguely, I imagine this would leave room for things like optimization or parallelization. Using the functional language Haskell as an example:

f x
 | x < 0 = -1
 | x > 0 = 1
 | otherwise = 0

is the same as:

f' x
 | x > 0 = 1
 | x < 0 = -1
 | otherwise = 0

Is it possible in some languages or paradigms to make the semantics of the function not dependent on the order in which the branches are defined (probably with special treatment of the otherwise case)?

Here's the problem:

You always need some way to resolve ambiguity when there are overlapping clauses
There is no easy syntactic way to ensure that clauses don't overlap.

So, if you can think of a way for the behavior of if to be well defined when there are overlapping clauses, that doesn't depend on the ordering of the clauses, then you can do what you're asking for.

And, there are, of course, a bunch of ways to define this: you could always default to the simplest matching condition (with the shortest code), you could attach an integer at runtime to each case and use the one with the highest number, etc.

But at their core, the process of looking at overlapping cases and choosing one, basically involves ordering the cases in some way. Requiring the user to specify the ordering, and having the order in the source code match the "priority" of each clause, seems like the simplest option.

There is likely a way to ensure that ordering doesn't matter in a dependently-typed language, when you can actually construct a proof that all your clauses are mutually exclusive. Or, you can re-order clauses in an optimizer, if a static analyzer identifies a place where all the clauses are mutually exclusive.

Or, if you're in a non-deterministic language like Prolog, you can just explore all the branches that succeed, and have an if expression return multiple answers. But for most languages, this isn't compatible with their deterministic semantics.

In general, you can't just ignore the order.


Solving/Optimizing a linear system in a finite field (Z/2Z) I'm trying to solve the following optimization problem.

A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y are vectors). And I'm looking for X such that the Hamming weight of Y is maximal.

In the best case, there would be a solution with Y_i = 1 for all i, and I would find it using the Gauss algorithm.  But I know it's not the case.

So far, I haven't found a better algorithm than a random/greedy local search, but I'm sure I can use some maths to get a better solution. I've considered running a Gauss algorithm starting with B = (1,...,1) and  somehow backtrack when a run into a contradiction (and switch the b_i that prevent me to get a solution). Could matrix factorization help somehow?

(Note that a random assignment has probability at least 1/(1+$\hspace{.03 in}$(size($\hspace{.03 in}$Y$\hspace{.03 in}$)))

of making at least 1/2 of Y's entries equal 1.  That can be derandomized

by sequentially setting each variable to [something that forces at least

as many of Y's entries to 1 as it forces to 0, with ties broken arbitrarily].)

By this paper's proof of Theorem 5.6, for all real

numbers $\epsilon$, if  $0 < \epsilon$  then the promise problem

Input:  instance of your problem in which each row of A has exactly 4 ones

must output YES if:    there is an assignment which makes more than 1-$\hspace{.03 in}\epsilon$ of Y's entries equal 1

must output NO if:     for every assignment, less than  (1/2)$\hspace{.03 in}$+$\hspace{.03 in}\epsilon$  of Y's entries equal 1

is NP-hard.

When parameterized by the number of zeros in Y, your problem is obviously in W$[\hspace{-0.02 in}$P$]$O,

but I don't know anything else about your problem's parameterized complexity.

This paper gives a possible try for your problem,

although it looks like it's just a student's "3rd Year Project Report".


Selecting elements from two arrays to get a target sum Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.

Design an algorithm to solve the following problem.

For each index $i$ ($1\leq i \leq n$) either select $A[i]$ or $B[i]$ but not both such that the total sum of the picked elements from each of the arrays is at least $k$?

For example $A=[1,2,3,4,5,49]$ and $B=[1,10,10,10,22,12]$, target $k=50$.

Solution

Pick the first and the last elements from A whose sum is 50.

Pick the rest (all but the first and the last elements) from B. That sums up to 52.

So in both Arrays we get a sum at least the target value 50.

Can someone help me to find the algorithm to solve this problem?

Here is an algorithm using dynamic programming. Let us define the function $C:V\times \mathbb{N} \rightarrow \mathbb{N}$ as $C(i, s) = r$, if using only the first $i$ indices we can achieve a sum of at least $r$ in B, when having a sum at list $s$ in $A$. This means $C(i, s) = r$ if there is an index set $I \subseteq [i]$, such that $\sum_{j \in I} A[j] \geq s$ and $\sum_{j \in [i] \setminus I} B[j] \geq r$. If $s$ is greater than the sum of the first $i$ elements in $A$, then set $C(i, s) = -\infty$ It is easy to build the transitions of the dynamic programming as follows. For each $i$ and $s$:
$$C(i+1, s) = \max\{C(i+1,s), C(i, s) + B[i]\}$$
$$C(i+1, s+A[i]) = \max\{C(i+1, s+A[i]), C(i, s) \}$$
The output is yes, if there is $s \geq k$ such that $C(n+1, s)\geq k$.

The correctness is pretty straight forward. The running time can be bounded in $O(nk)$.

On the other hand, this problem is NP-hard. It is easy to reduce the set partitioning problem to this problem. In the set partitioning problem, given a set of integers, you are asked to partition the set into two subsets having equal sums. Let $S$ be an instance of the set partitioning problem and $s$ be the sum of elements in $S$. Set $A = B = S$ and $k = s/2$. The correctness of the reduction is quite straight forward. That is why a pseudo polynomial algorithm (polinomial in the value of the input instead of its size) is the best we can hope for.


Is there a name for algorithms which detect nearly-similar structures? I'm interested in how you might detect similarities in tree structures. For example, in these three JSON documents;

(a)   { name="foo", length=23 }
(b)   { name="boo", length=99, redundant=true }
(c)   { quux="baz", a=44, b=66, c=99 }

it's obvious to the human eye that (a) and (b) are more similar, in content and structure, than (a) and (c). However, I don't know of heuristics I might use to quantify that similarity.

I'm sure such algorithms exist -- they might exist, say, in code that detects similarities in parse trees or abstract syntax trees, to detect duplicate code structures -- but I've no idea how to search for more information because I don't know what to look for.

Is there a name for this kind of algorithm, where you're looking to be able to calculate 'near-ness' between different trees, graphs, or sets?

(Aside: I've just found out about the Levenshtein Distance so maybe there is a common technique like 'print out your data structures as strings and calculate distances between the printed strings' but I'm very new to the concept.)

The search terms you're probably looking for are "similarity measure", "dissimilarity", "distance function", or "metric"... applied to trees.

One approach to your probem is to invent a similarity measure or distance function/metric that can be applied directly to tree.  There are some references on that at https://stackoverflow.com/q/21897879/781723.  You can also easily envision some recursive algorithms for doing that.  For instance, if a tree $T$ has children $T_1,T_2$ (i.e., the left and right subtrees of $T$), you could define

$$d(T,T') = d(T_1,T'_1) + d(T_2,T'_2),$$

with some way to bottom out the recursion at leaves (e.g., if leaves are strings, then use edit distance at the leaves).  You could also combine the distances of the child subtrees in some other way, e.g.,

$$d(T,T') = \sqrt{d(T_1,T'_1)^2 + d(T_2,T'_2)^2}$$

or using any other norm.

Another approach is to identify a set of features that capture aspects of the trees that are important to you.  Then, each tree can be mapped to a feature vector, and you can measure similarity between two trees by computing the similarity of the two feature vectors.  There are many distance metrics one can use on feature vectors (e.g., L1 norm, L2 norm, etc.)

In some cases, there are sophisticated techniques that can be used to speed up the feature-vector-based approach.  See https://en.wikipedia.org/wiki/Tree_kernel.

Finally, you could also look at techniques like shingling or minhash and try modifying them to apply to trees instead of strings/sets.


Does Gödel's first incompleteness theorem apply to quantifier-free arithmetics? Gödel's first incompleteness theorem states roughly that "for any axiomatization of arithmetic, there are statements that can neither be proven to be false nor true."

Does this still hold when it comes to quantifier-free statements?

I.e. if we have the structure of arithmetic: $(\mathbb N, +,\cdot, 0,1)$, and we restrict to sentences $\Phi^{QF}$ about this structure that don't contain $\exists, \forall$, can we then for all $\phi\in \Phi^{QF}$ either prove or disprove $\phi$?

What you are referring to is called Baby Arithmetic ($\mathsf{BA}$) in Peter Smith's book An introduction to Gödel's Theorems.

  $\mathsf{BA}$'s language [has] one single individual constant $0$, the one-place function symbol $S$, and the two-place function symbols $+$ and $\times$.  [...] it lacks quantifiers and variables.

$\mathsf{BA}$ is complete, negation complete, and decidable.


Proving that the clique cover problem is in NPC by reducing from k-coloring Provided that we have to compare it against the graph coloring problem which is NPC. So far,
I can only think of connecting edges from a vertex in a provided graph to all the other edges it is not connected to then I separate the new graph g2, then I connect all the vertices that are not connected in the g2. And then I count the number of subsets. However it doesnt seem to work with a graph that requires four colors?

In the interests of putting up an explicit answer, your approach is correct. The proof is sketched on the Wikipedia page for Clique Cover.

The reduction itself is fairly straightforward. The reasoning is that if a graph is $k$-colourable, then it can be partitioned into $k$ independent sets (one for each colour class), then we just exploit the normal reduction between Independent Set and Clique by taking the complement graph (we swap edges for non-edges and vice versa), so any independent set becomes a clique. So if $G$ is $k$-colourable, it can be partitioned into $k$ independent sets and hence $\overline{G}$ can be partitioned into (i.e. covered by) $k$ cliques (but not necessarily by $k$-cliques ;) ). Conversely if $\overline{G}$ can be covered by $k$ cliques, $G$ has a partition into $k$ independent sets, and hence is $k$-colourable.


How to find several rectangles with minimum area to cover the red cells In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) and Figure 1(c) are two ways. Obviously, (c) is a better way due to the smaller sum of area the green rectangles . Besides, the side length of these rectangles should be at least two unit length, for example, the green rectangles in Figure 2 are not allowed. The rectangles can overlap.

How to do this effectively? Is there any algorithm to do this?

I have a simple idea, firstly, use the K-means algorithm to divide these red cells into K clusters, then for each cluster, find a bounding box(rectangle) to cover it. But the sum area of these rectangles may not be small.

The way I created the pictures in my comment is by Integer Linear Programming, specifically the following model:

$\text{minimize } x \cdot area \\
\text{for each red cell } (i,j): \: \sum_{k \in covers(i,j)} x[k] \ge 1 \\
x \in \{0, 1\}$

Where the decision variables x[i] refer to whether or not to use rectangle i, covers(i, j) is the set of rectangles that contain the cell (i, j), area is the vector of the areas of the rectangles, and the set of rectangles used is all 2x2, 2x3, 3x2 and 3x3 rectangles that fit on the grid and contain at least one red cell. You can use a slightly smaller set, for example it is never necessary to use a piece that's bigger than 2x2 that covers only 1 red cell, it could always be replaced by a 2x2 piece and give a better solution. Any rectangles of other legal sizes can be constructed from these pieces so they can be left out.

Actually even fewer rectangles can be used. For example, a rectangle that can be replaced by a smaller rectangle without uncovering any red cells is redundant. There is also the case where a 3x3 can be replaced by 2 2x2 rectangles, that potentially overlap, such that they together cover (at least) the same red cells, making the 3x3 redundant.

Experiment shows that presolving removes almost all columns (for relatively sparse problems), suggesting that it should be easy to a-priori not-generate many of them. I have not looked into that too deeply yet.

Despite ILP being NP-hard, large instances such as this or even this were solved in a couple of seconds. Maybe there is also an inherently efficient way though, I'm not sure.


Testing two distributions, both accept null hypothesis I have a sample that is collected to verify the accuracy of a new random number generator.
Applying the goodness of fit test to check if this sample comes from the Standard Normal Distribution and Uniform Distribution, I found out that both of these accept null hypothesis although they are contradicting to each other.
Is it theoretically possible? Why?

Hypothesis tests don't accept the null hypothesis.  Instead, they fail to reject the null hypothesis.  That's not the same thing.  For instance, if your sample size is small enough, it's certainly possible to fail to reject both null hypotheses.  All that the tests are saying is that the hypotheses "this data came from a standard normal" and "this data came from a uniform distribution" both seem plausibly consistent with the data, and that's not impossible.


How to calculate conditional entropy I'm new to information theory and I am struggling to understand this problem. Let $p(x,y)$ given by:

How can we calculate $H(X|Y)$? I know $H(X|Y)=H(X|Y=0)+H(X|Y=1)$ but then I don't know how to go further.

$${\displaystyle \mathrm {H} (Y|X)\ =-\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log {\frac {p(x,y)}{p(x)}}}$$

Based on chain rule, we have:

\begin{aligned}\mathrm {H} (Y|X)&=\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log \left({\frac {p(x)}{p(x,y)}}\right)\\[4pt]&=-\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log(p(x,y))+\sum _{x\in {\mathcal {X}},y\in {\mathcal {Y}}}{p(x,y)\log(p(x))}\\[4pt]&=\mathrm {H} (X,Y)+\sum _{x\in {\mathcal {X}}}p(x)\log(p(x))\\[4pt]&=\mathrm {H} (X,Y)-\mathrm {H} (X).\end{aligned}

So for $H(X|Y)$ in your sample, we have:
$$
H(X|Y) = -( 0.25 \times \log(\frac{1}{2}) ) - ( 0.25 \times \log(\frac{1}{2}) ) -( 0 \times \log(\frac{0}{0.5}) ) -( 0.5 \times \log(\frac{0.5}{0.5}) )
$$


Find if a sequence of node is a result of a binary tree preorder traversal Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence is a valid result of a binary tree preorder traversal?

Ex. $1, 1, 0, 1, 1, 0, 0, 1$ is a valid sequence.

Idea of a tree construction

If the length of the sequence is $1$ then just make the first symbol root and stop with SUCCESS. If the first symbol of the sequence is $0$ then construction is not possible, otherwise make it the ROOT and set the root to the ROOT.

for i = 2 to n
 if n[i] is 1 then
   if root.left is free
     root.left = make_node(n[i])
     root = root.left #go to left
   else if root.right is free then
     root.right = make_node(n[i])
     root = root.right #go to right
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 else if n[i] is 0 then
   if root.left is free
     root.left = make_node(n[i])
   else if root.right is free
     root.right = make_node(n[i])
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 end

 if root is nil then break
end

if i < n the construction impossible

Checking without a tree construction

The basic idea is at each step to count how many nodes we can add to the tree. When we read $1$, we add one internal node which allows to add two new nodes and hence $-1+2 = 1$ and so we increment the counter by one. When we read $0$ we add a new leaf and so we decrement the counter.

if a[0] == 0 then
  return FAILURE
else
  counter = 2

for i=2 to n
  if a[i] == 1 then
    counter = counter + 1
  else
    counter = counter - 1
  end

  if counter == 0 then break
end

if i < n then
  return FAILURE
else
  return SUCCESS
end

Construction example

$1,1,0,1,1,0,0,1$

  1 =>  1  => 1  => ... =>  1
       /     /             /
      1     1             1
           / \           / \
          0   1         0   1
                           / \
                          1   1
                         / \
                        0   0

Checking example

c=2, c=3, c=2,c=3, c=4, c=3, c=2, c=3, SUCCESS

At the end c=3 means we still can add 3 leaves.


Computing the mode of XOR subsequences I was confronted with this problem in an online programming challenge and it has been bugging me since:

In the problem, you are given a list of 16-bit numbers, say
$a_0, a_1, ..., a_n$. An "XOR subsequence" is defined as the exclusive-or combination of every element in a consecutive subsequence of the list. The problem is that you must find the most commonly occurring XOR subsequence out of every possible consecutive subsequence in the list. In the event of a tie, the lowest numeric XOR value out of the most frequently occurring ones wins.

The first solution I came up with was an $O(n^2)$ solution where I compute the XOR for consecutive subsequences $a_0,...,a_i$ from $i=0$ to $i=n$, which can be done in $O(n)$, and doing the same thing starting at $a_1$, etc, and incrementing a counter in a map for every result. I know this repeats a lot of work, so I tackled the problem from a different angle and tried to define it mathematically. I defined $X_{i,j}$ to be the XOR of $a_i,...,a_j$ so that I could write the following:

$X_{i,j} =
\begin{cases}
a_i & \text{if } i = j \\
a_j \oplus X_{0, j-1} & \text{if } i = 0 \text{ and } j > 0 \\
X_{0,i-1} \oplus X_{0,j} & \text{if } 0 < i < j
\end{cases}
$

I implemented that with memoization, which I believe eliminates all redundant calculations, but using memoization turns out to be slow and use $O(n^2)$ space when attempting to calculate all $X_{i,j}$ for $0 \leq i \leq n $ and $i \leq j \leq n$, which is unacceptable.

Is there any way I can make this any faster than $O(n^2)$? Or if not, is there any efficient way to reduce the number of computations? Or am I missing some simplification to the problem that doesn't require me to compute every $X_{i,j}$? I'm sort of new to dynamic programming, so it's been hard to wrap my brain around this problem. My original solution was too slow by a factor of about 5 seconds (vs the time limit of 4 seconds for the challenge), so I believe even a constant factor reduction in time would make the solution acceptable.

Yes, this can be solved much more efficiently.  You can solve this problem in $O(b 2^b)$ time using a FFT, if each number is a $b$-bit number.  In the comments, you said $b=16$, so this should be an efficient solution: something like $2^{21}$ steps of computation.

Consider the sequence $b_{-1},b_0,b_1,\dots,b_n$ defined by $b_{-1}=0$ and $b_i = a_0 \oplus a_1 \oplus \dots \oplus a_i$.  Now your problem is equivalent to asking for the value that appears most frequently, out of all of the values $b_i \oplus b_j$ with $i<j$.

Let $x \in \mathbb{N}^{2^b}$ be the characteristic vector of $b_{-1},b_0,\dots,b_n$.  In other words, $x_v$ is equal to the number of times that $v$ appears in the values $b_{-1},b_0,\dots,b_n$; or, equivalently, $x_v = \#\{i : -1 \le i \le n, b_i = v\}$.

Let $y \in \mathbb{N}^{2^b}$ be the characteristic vector of $\{b_i \oplus b_j : i<j\}$.  In other words, $y_v$ is equal to the number of times that $v$ appears in the values $b_i \oplus b_j$; or, equivalently, $y_v = \#\{(i,j) : -1 \le i < j \le n, b_i \oplus b_j = v\}$.

We see that $y = x * x$, i.e., $y$ is the convolution of $x$ with itself:

$$y_v = \sum_u x_u x_{u \oplus v}.$$

This convolution can be computed using a discrete Fourier transform on the group $(\mathbb{Z}/2\mathbb{Z})^b$.  We find

$$y = \mathcal{F}^{-1}(\mathcal{F}(x)^2),$$

where here $\mathcal{F}$ is the Fourier transform and $\mathcal{F}^{-1}$ is the inverse Fourier transform.

Moreover, there is a fast Fourier transform  (FFT) for this group.  The FFT can be computed in $O(N \lg N)$ time, on sequences of length $N$.  Here $N=2^b$, since the characteristic vector has length $2^b$, so the running time to compute $\mathcal{F}$ and $\mathcal{F}^{-1}$ is $O(b 2^b)$.

Once you have the characteristic vector $y$, you just look for the index $i$ such that $y_i$ is maximized.  This is the desired output value.

All in all, this gives an algorithm with $O(b 2^b)$ running time.  This is probably much better than your $O(n^2)$ algorithm, for your particular parameters, but implementing it takes considerably more sophistication (you have to know how to implement a non-standard FFT, for a particular finite group).


How is it valid to use oracles in mathematical arguments? Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle".  Thus, Oracles do not exist almost by definition.  I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).  Have a problem, ask the "magic" Oracle, problem solved $O(1)$ time.  Of course you can't say anything about what is happening in the oracle, because its "magic". From this point of view, Turing Machines (bizarre fetish formalism if you ask me) with Oracles do not exist.  Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently."  I accept that it sounds a bit silly to go as far as "If I could solve problem $X$ in constant time, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the level of detail we're working at, here.

For example, consider an oracle $O_1$ that can solve SAT in constant time, versus an oracle $O_2$ that solves SAT in, say, cubic time. The problems you can solve in polynomial time with access to $O_1$ are exactly the same as the ones you can solve in polynomial time with access to $O_2$. Sure, the polynomial will be better if you use $O_1$, but it's still a polynomial if you use $O_2$. In fact, the answer won't change whatever polynomial bound you assume on the running time of the oracle so we choose to simplify the analysis by choosing the simplest polynomial possible: $1$.

In some cases, you can see oracle arguments as hedging your bets. Although you lead your question with "Oracles don't exist", we don't actually know that. Suppose somebody produced a polynomial-time algorithm for SAT tomorrow. Wouldn't it be a shame if all we could solve with it was SAT? But because we have all kinds of oracle reductions available to us, we could already solve any NP-complete problem efficiently (the many-one reductions used to prove problems NP-complete are just a very restricted kind of oracle reduction). Conversely, if somebody proves tomorrow that SAT has no efficient algorithm, then all that work on oracles tells us that all the other NP-complete problems are also genuinely hard.

But remember that oracle arguments are conditional: if I could do $X$, then I could also do $Y$. If it turns out that you can't do $X$ then, OK, maybe you can't do $Y$ after all. But it's still a perfectly valid what-if question. So, for example, it still makes sense to consider Turing machines with an oracle for the halting problem, even though we know for a provable fact that no Turing machine can actually solve the halting problem. There's nothing wrong with asking the what-if, as long as we remember that it is a what-if.

To address a couple of other points,

  I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).

So we're allowed to use some non-existent things but not others?  Why?

  Turing Machines (bizarre fetish formalism if you ask me)

Are you trying to get a rise out of me, Agent Kujan?

  Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

Yes, that's circular. But it's also a strawman: I've never heard anyone make that argument.


How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution? So usually Sudoku is $9 \times 9$, but this question extends to $n^2 \times n^2$ puzzles with $n > 3$ as well. There are many polynomial time deduction rules that can make progress in finding a solution to a Sudoku puzzle. But then sometimes guessing values and following chains of conclusions might be required to eliminate a cell's value or a combination of cells' values. However, once a valid solution is found, this doesn't guarantee that the solution is UNIQUE. A valid Sudoku puzzle should have only one valid solution but when generating random puzzles, this may take extra computation to verify.

So, my question is, if we allow a certain set of polynomial time deduction rules (say, the most common set described in Sudoku strategy), along with guessing values and following the conclusions, then how much harder can it be to determine there is a unique solution to a given puzzle, versus finding just one solution, in terms of the number of non-unique solutions? Is there an asymptotic difference for certain classes of puzzles?

Yato and Seta show that for every constant $m$, given $m$ solutions to a Sudoku puzzle, it is NP-complete to determine whether there is another solution. They show that the same property is satisfied by other puzzles as well.


Hash Table: Relation between position of a value and Hash table size I need to know whether hash table size, $S$ has any impact on distribution of a value in hash table.

At the moment I'm using SHA512 and I can tolerate up to 50 elements in any bucket, and I have $10^6$ elements; I set hash table length to $S=50000$. This is far more larger than what is suggested in the literature [1]. However, if I reduce the table length I would get overflow (as I have tested and saw it).

To find position of an element in hash table I do $hash(val) mod S$.

Question: Does $S$ play any role in distribution of the value in hash table?
In other words, do I need to set $S$ as a prime number or power of two ?

[1]. http://www14.in.tum.de/personen/raab/publ/balls.pdf

No.  If you use SHA512, you can use any modulus $S$ you want: it doesn't need to be prime.  A power of two is fine and is no better or worse than a prime.

The reason is that the cryptographic properties of SHA512 ensure that the output of SHA512 is (for all practical purposes) essentially a uniformly random 512-bit string.  Because $2^{512}$ is so much larger than your modulus, after reducing modulo $S$, the result will be approximately uniform.  Any non-uniformity will be incredibly, exponentially small: so small that it's not detectable within your lifetime, or the lifetime of the solar system.  (I know there's another answer that claims non-uniformity is a problem, but that answer failed to quantify the extent of the non-uniformity and thus came to the wrong conclusion; the amount of non-uniformity is so exponentially small that it's completely irrelevant in practice).

So, go ahead and use any modulus that's convenient.  It doesn't need to be a power of two or a prime number, if you're using SHA512 as your hash function.


Divide-and-conquer: Determining the top two candidates and whether these two candidates received more than n/2 votes Suppose that each person in a group of n people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes.

Describe a divide-and-conquer algorithm that determines the top two candidates and whether these two candidates received more than n/2 votes.

I have the answer (below), but there's one part I don't understand:

Our algorithm will take a sequence of 2n names (two different names provided by each of n voters) and determine whether the two top vote-getters occur on our list more than n/2 times, and if so, who they are. Actually for technical reasons we will need the top 3 vote-getters.** The votes of each voter are adjacent. Note that we can have at most 3 people (but not 4) with more than half of the votes. Divide the list into two parts, the first half and the second half. (No one could have gotten more than n/2 votes on this list without having more than half votes in one half or the other, since if a candidate got less than or equal to half the votes in each half, then he got less than or equal to half the votes in all.) Thus apply the algorithm recursively to each half to come up with at most six names (three from each half). Then run through the entire list to count the number of occurrences of each of these names to decide which, if any, are the winners. This requires at most 12n additional comparisons for a list of length 2n.

I don't understand why we are coming up with at most six names. I also don't get where the 12n comes from. To be more clear, I sort of understand why the 12n is a thing given the 6 names, but I don't understand why it's 6, and if it means 6 names for each step of recursion, or 6 names after all of the recursion (and if the latter, what happens during each step of recursion?).

The original problem is not quoted/rephrased correctly
Here is one correct version as it appears as exercise 18 in section 8.3 of the book Discrete Mathematics and Its Applications, 7th Edition by Kenneth H. Rosen, with slight modification.

Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than $n/2$ votes.
Devise a divide-and-conquer algorithm that determines whether the two candidates who received the most votes each received more than $n/2$ votes. If so, determine who these two candidates are.

What is difference? As I have emphasized, only when it has been determined that each of the two candidates who received the most votes (the top two candidates) has received more than $n/2$ votes, the desired algorithm is required to determine these two candidates . In other word, if it has been determined that at least one of the top two candidates received at most $n/2$ votes, the algorithm is not required to determine these candidates.
The catch here is that it is possible to determine whether the top candidate received more than $n/2$ vote without identifying who is the top candidate. It is also possible to determine whether the second top candidate received more than $n/2$ vote without identifying who is the second candidate. For example, if we are able to ascertain the most votes received by any single candidate is at most $n/2$, which can happen when we have checked enough but not all of the votes (so we might not be able to identify who are the top candidates), then we are sure that none of the top two candidates received more than $n/2$ votes.
On the other hand, by its very nature, any (usual) divide-and-conquer algorithm cannot find the top (two) candidates unconditionally. The idea is that it can happen that the top candidates overall is not among the top candidates in either half of the list. In fact, it can happen that the top candidate overall is the bottom candidate in each half of the list. For example, 10 people can vote in the following way, $(A,B), (A,B), (A,B), (C,D), C,D), (E,F), (E,F), (E,F), (C,D), (C,D)$. While $C$ and $D$ are the top candidates overall, they are the bottom candidates voted by the first 5 people and they are the bottom candidates voted by the other 5 people.

The "answer" given by the OP, the fourth paragraph in the question, which starts with "our algorithm" and ends before the separator line, is in fact a part of an answer key. For brevity, I will refer to it as "the answer key".
How to understand the answer key
You can check the other cool answer written by D.W., which includes a very detailed analysis of the answer key.
D.W.'s answer describes in great detail, according to the answer key, an algorithm that returns a list of three candidates which contains all the candidates who got more than $n/2$ votes and possibly other candidates. More specifically, if a candidate got more than $n/2$ votes, then he/she must be in the returned list. However, the list may contain people who did not get more than $n/2$ votes. It can also happen that none of the people in the returned list is the top candidate, or the second top candidate, or the third top candidate.
D.W.'s answer also explains clearly "why we are coming up with at most six names" as well as "where the $12n$ comes from".
I have confirmed that D.W.'s algorithm is correct (since he, in his modest way, claim he does not "know whether this algorithm is actually correct") in that it conforms to the answer key and it is a full answer to the original problem except it omits the easy steps such as "if so, determines who these two candidates are".
A better written problem
It turns out, as you must have noticed by now, somewhat subtle to understand exactly what is the requirement of the original problem. Here is my version of the problem that should be much clearer, at least for me.

Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates. Devise a divide-and-conquer algorithm that determines all candidates who received more than $n/2$ votes.

If you are careful, you may point out the my version missed "... to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes". Well, although it is interesting to know that election goal and election rule, it has nothing to do with the specification of the desired algorithm. You may also point out that my version does not require "if so, determine who these two candidates are". Well, if we have determined all candidates who received more than n/2 votes, the number of whom is at most 3, then by just counting the number of votes received by each of those candidates, we can, easily, "if so, determine who these two candidates are".
An interesting algorithm as an exercise
There is an algorithm using linear time and constant space that determines all candidates who received more than $n/2$ votes. The construction of such an algorithm is left as an intriguing and challenging exercise for the readers who has read thus far.
Thanks to Tom van der Zanden, who pointed out a typo in my previous formulation of the exercise.


NP-complete reduction proof -- graph problem While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem:

You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs of $G$'s edges.

As an example, a complete graph on 3 vertices would be described as follows: $G = (V, E)$ = ({$v_1, v_2, v_3$}, {$v_1v_2, v_2v_3, v_1v_3$}). And you could be given a set $S$ which could consist of, say, two elements. E.g. $S$ = {$(v_1v_2, v_2v_3), (v_1v_2, v_1v_3)$}.

Now, we'll define $M$ as a subset of edges that has AT MOST one edge incident to each vertex in $G$, and AT MOST one edge from each pair in $S$. So for the example given above, $M$ could be any one of the following: {$v_1v_2$}, {$v_1v_3$}, or {$v_2v_3$}. $M$ cannot contain two (or more) edges for this example, though; if $M$ contained two edges, then there would be two edges that are incident to a single vertex in $G$, which is not allowed.

Here is the overarching problem statement: Given some graph $G$, some subset of edge-pairs $S$, and some integer $k >= 1$, determine whether $G$ contains a subset of edges, $M$, such that $|M| >= k$.

Your task: show that this problem is NP-complete.

I know I'm supposed to use reduction of a known NP-complete problem to show that the above problem is NP-complete, but I'm quite lost as to where to start, and even which known NP-complete problem to use for the reduction. Since it's a graph problem, I'm thinking perhaps something like vertex cover, independent set, clique, etc. might be used for reduction, but have no idea which or how. I also have a sneaking suspicion that some variant of 3-CNF SAT might be used here, but racking my brain hasn't helped thus far. Thank you for any assistance.

We can reduce independent set ($IS$) problem to the overarching ($OVERARCHING$) problem as follows. We reduce the instance $\langle G, k \rangle$ of IS to an instance $\langle G',S,k\rangle$ of OVERARCHING by the following reduction.

Each vertex $v_i \in V(G)$ becomes an edge $v^1_iv^2_i = e_{v_i} \in E(G')$. $G'$ will be a disconnected graph containing $|V(G)|$ edges and $2|V(G)|$ vertices. For every $v_iv_j \in E(G)$ we will add pair $(v^1_iv^2_i, v^1_jv^2_j) = (e_{v_i}, e_{v_j})$ in $S.$ If we select one of the vertices which are neighbor then we select one of the edge in the corresponding pair in the set $S$. Since all edges are disjoint in $G'$ we have absolute freedom  there in selecting any edge we want.

Then $\langle G, k \rangle$ has a $k$-size independent set if and only if $\langle G',S,k\rangle$ has a $k$-size "overarching" set $M$.

Thus $IS \leq_P OVERARCHING$, and hence $OVERARCHING$ is NP-complete.


Maximize cost in graph with variable costs Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous day. The prisoner knows the calories of each dish for the full week, and wishes to maximize his calorie intake for the week.

I modeled the problem into a bidirected cyclic graph:
l[n], h[n] are the two known arrays of costs and k the number of steps taken through the graph. (The cost to the H node at the kth step is h[k]). L represents eating the low nutrient dish, while H the high one. If you want to get to H you must pass from - first and amass no cost. The costs represent the nutrients gained when moving to each node. (They could be rewards on the nodes instead). S is the start node. The goal is to maximize the cost, given the number of maximum steps n.

I'm looking for a general direction. Does it belong to a known family of problems? If yes, how do you solve them efficiently? Dynamic programming, knapsack or some known modification of a graph traversal algorithm? Is considering it a graph problem wrong, or not particulartly helpful? Sorry for the barrage of questions.

There's no need to introduce a graph; the problem can be solved by a straightforward dynamic programming algorithm.  The running time will be $O(n)$, where $n$ is the number of days.


Grammar for ${a^n b^n c^{n+m}}$ Can we define a grammar for the following language?

$$L = \{a^n b^n c^{n+m} | n,m>=0\}\,.
$$

I can define one for this:
$$L=\{a^nb^n|n,m>=0\}
$$

  S --> aSb | λ

or this one:
$$L=\{b^nc^{n+m}|n,m>=0\}
$$

  S --> Ac
  A --> bSc | Sc | λ

but I can't solve the first one, any hint?

GRAMMAR FOR THE LANGUAGE:{a^n b^n c^n/n>=1}

S->abc|A

A->aABc|abc

cB->Bc

bB->bb

FOR EXAMPLE:INPUT STRING aaabbbccc when n=3

S->A

->aABc

->aaABcBc (A->aABc)

->aaabcBcBc   (A->abc)

->aaabBccBc   (cB->Bc)

->aaabBcBcc   (cB->Bc)

->aaabbcBcc   (bB->bb)

->aaabbBccc   (cB->Bc)

->aaabbbccc   (bB->bb)


Efficient immutable data structure for small multi-sets of integer ranges? Background

I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure takes up around 80% of the execution time in insert and remove, so it's time to see if there's something better out there. I'm spending around 1400 clock cycles per insert or remove, so there should be some margin for improvement.

Current implementation

The current model, called Domain, is a fully persistent immutable ordered linked-list of [low, high) pairs, normalized so that for any time two ranges overlap, the first one is the longest. Touching ranges are also joined. Most domains consist of less than 100 ranges, but some consist of up to 10k ranges. The current data structure is chosen because it was easy to work with, avoiding premature optimization.

The Domain datastructure represents a multiset of integers. Internally representing ranges as [low, high) pairs is just an optimization. Since some domains cover many million of numbers, I don't think a multiset would be fast enough to be viable.

A range is a set of b-a unique integers x, a <= x < b, distinct from every previously defined range, with b-a as large as possible.

The operations

The operations supported right now are

insert(a,b) union of two domains, keeping duplicates
remove(a,b) a minus b
intersection(a,b)
ncov(a,n) a with n-1 copies of each present integer removed.
after(a,n) domain of everything in a equal to or greater than n
before(a,n) domain of everything in a equal to or smaller than n
minlen(a,l) domain of all ranges in a with a cardinality of at least l.
trunc_start(a,l) a with the l smallest integers removed from each range.
trunc_end(a,l) a with the l largest integers removed from each range.

Queries:

contains?(a,p) does the domain a contain a specified integer p?
covers?(a,b) is domain b a subset of domain a?
lowest(a) what's the lowest integer in the domain?
highest(a) what's the highest integer in the domain?

Behaviour

The most common use-case is to modify the structure a small bit at a time, from smallest value to biggest. Since inserts might modify the whole structure, the lists are almost always rebuilt completely right now. Changing the access pattern to bulk inserts and deletions is not feasible.

The second most common use-case is intersection between multiple (3+) domains, currently implemented as repeatedly calling the binary intersection function.

Questions

Is there a standard name of this data structure?
Is there a more efficient format? If so, which one(s)?
Would a tree be faster than a linked-list? With or without rebalancing?

I would suggest looking at interval trees and segment trees.  A natural representation is that the data structure contains a union of non-overlapping ranges $[l,u]$ with a multiplicity $m$; the intended meaning is that each integer in the range $l,l+1,l+2,\dots,u$ occurs in the domain with multiplicity $m$ (i.e., appears $m$ times), and the invariant is that the multiplicity of all integers within a single range is the same.

We can't tell you whether a tree would be faster in your application; that's workload-dependent, so the only way to tell is to try it and benchmark it and see.

This can be made persistent using standard techniques (e.g., path copying), if that's useful (e.g., if you have many domains that are similar to each other).


Context free grammar for language with even number of $0$'s and $1$'s I want to create a Context-Free grammar that generates the language

$$ L = \{ w \in \{0, 1\}^* |\ \text{number of $0$'s is even, and number of $1$'s is also even} \}. $$

I came up with

$$
S \rightarrow 0S0S\ |\ 1S1S\ |\ ABABS\ |\ BABAS\ |\ \epsilon \\
A \rightarrow 0A0A\ |\ 1A1A\ |\ 0\\
B \rightarrow 0B0B\ |\ 1B1B\ |\ 1\\
$$

Looks like it does the job, but how can I be sure that it does indeed generate L.

Any help would be appreciated.

The most common approach to show that two sets are the same is to show that they are subsets of each other.

In this case, that means (1) every string with an even number of $0$s and $1$s has a derivation in the grammar, and (2) every derivation of the grammar has an even number of $0$s and $1$s.

In attempting (2), a reasonable approach is to prove inductively, from smaller strings to bigger strings.

For example, considering $S \to 0S0S$, since the number of $0$s increases by 2 and the number of $1$s stays the same, the resulting string has the desired property when the smaller $S$ strings in the right hand side do.

However, I think you'll find the $S \to BABAS$ case hard to prove correct, which suggests that's where you need to look for a counterexample. Indeed, here's one:

0101010 = (B:0)(A:1)(B:0)(A:1010)(S:) = (B:0)(A:1)(B:0)(A:(1(A:0)1(A:0)))(S:)


Proving that f(N) = N lg N + O(N) implies f(N) = Θ(NlogN) How do you prove the following?

$$f(N)=N\space lg\space N + O(N) \implies f(N) = \Theta(N \space log \space N)$$

Here $lg\space N \equiv log_2\space N$, and $O$ stands for the big-O, and $\Theta$ stands for big-theta. And $log \space N \equiv log_e \space N$, i.e. natural logarithm

My reasoning may not be all that mathematically pleasing (or even correct)...but here goes...

  We have $f(N)=N\space lg\space N + O(N)$

  By definition, $O(f(N))$ stands for the some upper bound for the
  function $f(N)$.

  Therefore, in our relation $O(N)$ (being an upper bound function)
  should theoretically contain $f(N)$ as $N \rightarrow \infty$.

  Now consider the lower bound of $f(N)$ to be some function of $N \space lg \space N$, i.e. $\Omega(f(N)) \equiv f(N \space lg \space N)$

  Now, $lg \space N \equiv log_2 \space N > log \space N$, where $log$
  stands for natural logarithm. Hence natural logarithm is some constant factor of "binary" logarithm, where that constant is less than 1.

So all the above reasoning naturally implies our above assertion, right? Where am I wrong?

Your third line (of the proof) doesn't seem to make sense, are you trying to say $f(N) \in O(N)$? If so, that's not true (you're trying to prove that it's not true!). Lines 4 and 5 are not clear, but if you were to write that in an exam or paper, you'd get in trouble.

As usual with asymptotic analysis, we just need to go back to the definitions. $f(N) \in \Theta(N\log N)$ means there exists constants $N_{0}$, $c_{1}$ and $c_{2}$ such that $c_{1}\times Nlog N \leq f(N) \leq c_{2}\times N\log N$ for all $N \geq n_{0}$.

There's a method involving limits that works, but I'll do it the old fashioned way first:

Lower bound ($f(N) \in \Omega(N\log N)$):

As $f(N) = N\log N + O(N)$ (and because we're dealing with CS so we make mathematical unjustified assumptions like everything is non-negative) we have $f(N) \geq N \log N$, so we can pick $c_{1} = 1$ and any $n_{0} \geq 0$ and we have $f(N) \in \Omega(N\log N)$.

Upper bound ($f(N) \in O(N\log N)$):

By the definition of $O(\cdot)$, we know that $f(N) \leq N \log N + b\times N$ for all $N \geq m_{0}$, for some constants $b$ and $m_{0}$. We can assume that we're using base 2 logarithms and that $N > 2$, so we know then that $\log N \geq 1$. Therefore $f(N) \leq N\log N + b\times N \leq N\log N + b\times N \log N$.

Thus we can pick $c_{2} = b+1$ and andy $n_{0} \geq \max\{m_{0},2\}$ and we get $f(N) \in O(N\log N)$.

Putting it together:
So we have $f(N) \in O(N\log N)$ and $f(N) \in \Omega(N\log N)$, which gives $f(N) \in \Theta(N\log N)$ where $c_{1} = 1$, $c_{2} = b+1$ and $n_{0} = \max\{m_{0},2,0\}$ (obviously the $0$ is extraneous).

The Limit Approach:

We can also take the limit of the ratio of two functions to determine some asymptotic relationships. In particular for us, if $\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)} = k$ for some constant $k$, then $f(n) \in \Theta(g(n))$.

So for our two funtion, we take $\lim_{n\rightarrow \infty}\frac{f(N)}{N\log N}$ apply l'Hopital's rule a couple of times, and conclude that $f(N) \in \Theta(N\log N)$.


Whats the difference between Processor bus and System bus Is there something called Processor Bus? Whist solving one of the MCQ I ended up seeing the term "Processor Bus". Does this thing actually exists?

I did some research, but couldn't find one article that talks about Processor bus.

It would be great, if someone can guide me along.

A lot of terminology is vendor-specific. Different architectures and CPU vendors use different terms to describe different ways of connecting CPUs and peripherals, and the technology is constantly changing.

In what follows, I'm going to use the word "bus", but do be aware that a bus could be realised in multiple ways depending on speed and requirements, such as a point-to-point, crossbar, or switched fabric topology. It's logically a bus, even if it isn't physically a bus.

As a general rule, modern busses are hierarchical, and the hierarchy reflects the way the computer system is constructed. For example, a modern computer may have more than one logical processor/core in a given die or package, and have more than one die or package on the motherboard. A large computer (e.g. a mainframe) may have more than one motherboard connected by a backplane.

Every time you have more than one thing which needs to communicate with each other thing, you need a bus/switch/whatever to connect them together.

Here's a simplified example:

Each package or die comprises multiple logical CPUs which are connected by some kind of internal bus. These are then connected to a common bus which connect the CPUs together, along with high-speed/high-bandwidth peripherals such as RAM (which increasingly looks like a peripheral these days), coprocessors such GPUs, and fast devices such as gigabit ethernet, Fibre Channel, InfiniBand, etc.

This bus is then connected via interfaces to lower-speed busses such as PCI, USB, SCSI, I2C, etc. Most of the things that you typically think of as "peripherals" are connected to peripheral busses such as these.

Of course this is just an illustrative example, not based on any particular computer design. Different architectures do different things. Large-scale high-availability machines (e.g. modern mainframes) typically have "local" RAM for each CPU die or motherboard, and CPUs designed for those high-availability applications commonly have a backplane bus interface built onto each CPU package plus a redundant backplane connection hanging off the high-speed I/O bus.

So given all that, the term "processor bus" probably refers a bus which connects processors together. That would mean one of two things:

The bus connecting logical processors together within a single package or die.
The bus connecting processor packages or dies together.


Somewhat-hardware-conscious algorithm for top k-of-n with $k=\Omega(\sqrt{n})$ The "top k of n" problem: You have n (not necessarily distinct) elements in an array, and you need to return another array containing the k elements with the highest value.

So, I'm going to need a top-k-of-n implementation for something I'm working on. Never mind exactly which programming language and hardware I'm going to use - but do mind that it's going to actually run on actual hardware. Thus there is multi-level caching so dereferencing pointers to arbitrary places should be minimized; there's the balance between computation and memory bandwidth to consider; there's multithreads/SIMDizing/whatever so I would like something parallelizable without too much communication... that's what I meant by somewhat-hardware-conscious.

Anyway, for a really small k I would probably just use a priority queue which fits in cache (or even linear search through several registers). But - what if your k is large? Large that the top k elements won't just be hiding at the top end of an estimated distribution? In this case I was thinking of estimating k using sampling, then (sort of) partitioning on that guess k; seeing how badly I missed; and iterating that, either partitioning my more-than-k or my more-than-n-minus-k. On one hand the length decreases quickly, and on the other hand I get closer to the really-small-k case, until I can settle for a priority queue (say for each core even) for the last bit.

So, my questions are:

Can someone describe known algorithms for this variant of the problem,  meeting my "vague hardware consciousness" constraint?
Does the algorithm sketch I described sound like something you know?
If not, does it sound like a good idea or can you describe shortcomings of this kind of an approach?

Notes:

You may assume the data are non-negative integers if it helps in any way (I don't think it should), or make any any other reasonable assumptions.
This problem is different that the partial sorting problem in that the output does not need to be sorted. Of course, for small k = $o(\sqrt{n})$ there isn't that much of a difference.
The data is in memory, i.e. this is not a streaming algorithm and you can read data multiple times. You can't alter the input; you can make a full copy but hopefully that should be overkill.

If you're allowed to make multiple passes through the data, one efficient approach is to use QuickSelect to find the value of the $k$-th largest element, then follow with a linear scan that outputs all elements that are larger than it.

This is more or less a more carefully-worked out version of the kind of approach you seemed to be considering.

See also https://en.wikipedia.org/wiki/Selection_algorithm.

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another possible approach would be to take a sorting network, which is a hardware circuit that sorts all of the values.  Then, throw away all but the last $k$ outputs, and keep only the gates they depend on.  You might be able to throw away a non-trivial fraction of the sorting network -- I haven't tried to work out how much.  This would solve the partial sorting network, and could potentially be hardware-friendly.

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another approach is to do something like merge sort, but where you only keep the top $k$ elements in each list at each stage.  In other words, split your data so that each processor receives an equal number of items.  Have each processor find the top $k$ of its elements (say, using a priority queue or any other method).  Then merge lists recursively, where each merge operation merges two or more lists of size $k$ and outputs only the first (largest) $k$ elements of the result.  This might work very well for out-of-cache (too-large-to-fit-in-main-memory) situations, or for parallel computing.  If you can fit $B$ items in cache/memory, then each merge step merges $B/k$ lists, so the number of rounds is $\lg_{B/k} (n/B)$.


Relaxation of the null production restriction in Regular and Context Free Grammars I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of some production.

However, in most definitions of regular and context-free grammars (such as those on Wikipedia), this restriction is nowhere to be seen (as an exception, the restriction is mentioned in the article on the Chomsky hierarchy for Type-3 languages).

Is this relaxation intentional in that both variants (with and without the restriction) have the same expressive power, or is this just a "sloppy" definition?
Even if they do have the same expressive power, wouldn't that ensure that Context Free Grammars are not a subset of Context Sensitive Grammars, thus violating Chomsky's Hierarchy?

True.

For CFG we can remove in fact all epsilon rules and obtain the same family of languages, except for the empty word. That can be added by adding the $S\to\varepsilon$ production. It is a so-called normal form.

Like Raphael says: it all depends on what you want to express in the formalism, and what makes proofs convenient.

The definition on type-3 grammars is a matter of taste. I would prefer $A\to\varepsilon$, $A\to aB$ as these two types of productions correspond to final states and transitions in finite state automata.


A heuristic for finding a maximum disjoint set Background

I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares.

This problem is NP-complete. Many papers suggest approximation algorithms (see Maximum Disjoint Set in Wikipedia), but I need an exact algorithm.

My current solution uses the following divide-and-conquer strategy:

Calculate all horizontal and vertical lines that pass through corners of the candidate squares. Each such line separates the candidates into three groups: candidates that are entirely at one side of the line, candidates that are entirely at the other side of the line, and candidates that are intersected by the line. Now there are two cases:

Easy Case: There is a separator line $L$ that does not intersect any candidate square. Then, recursively calculate the maximum-disjoint-set among the squares on one side of $L$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$, and return the union of these two sets. The separator line guarantees that the union is still a disjoint set.
Hard Case: All separator lines intersect one or more candidate squares. Select one of the separator lines, $L$; suppose that $L$ intersects $k$ squares. Calculate all $2^k$ subsets of these intersected squares. For each subset $X$ that is in itself a disjoint set, calculate the maximum-disjoint-set recursively as in the Easy Case, under the assumption that $X$ is in the set. I.e., recursively calculate the maximum-disjoint-set among the squares on one side of $L$ that do not intersect $X$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$ that do not intersect $X$, and calculate the union of these two sets with $X$. Out of all $2^k$ unions, return the largest one.

Question

My question is: What is the best way to select the separator line $L$?

There are two conflicting considerations: On one hand, we want $L$ to intersect as few squares as possible, so that the power set is not too large. On the other hand, we want $L$ to separate the candidate squares to subsets of balanced size, preferrably equal size, so that the recursion ends as fast as possible. What is the best way to balance these conflicting considerations?

EDIT: Additional details

My current heuristic is to pick the separator line that intersects the least number of squares. This heuristic allows the algorithm to process input sets with up to $n=30$ candidates, in several seconds. The optimal solution in these cases has about 10 squares. In general, the number of squares in the optimal solution is near $2\cdot\sqrt{n}$.

When the input grows beyond 30 candidates, the running time becomes much slower (several minutes and more). My goal is to find a heuristic that will allow me to process larger sets of candidates.

Rather than your approach, I suggest you formulate this as an integer linear program and feeding it to an off-the-shelf ILP solver.  Alternatively, formulate it as a SAT problem and feed it to a SAT solver: you'll probably need to take the decision problem version, where you ask whether there exists a subset of $k$ non-overlapping squares, and then use binary search on $k$.  Those would be the first approaches I would try, personally.

If you definitely want to try your approach based upon a "separating line", then I think the best way to answer your question is going to be to pick a representative set of problem instances, and try some different heuristics on them to see which seems to work best.

My intuition suggests that the best way to select the separator line may be to pick the line $L$ that intersects as few squares as possible, without worrying about how balanced the division is (though if there is a tie among multiple lines that each intersect the same number of squares, you could always use "how balanced the division is" as a tie-breaker).  The reason is that you are getting an exponential multiplicative increase in the running time each time you enumerate all subsets of the squares that intersect the line $L$.  I think your prime consideration is going to be keeping that blowup down.  But that's just my intuition, and my intuition might be wrong.  I think you need to do the experiment to find out empirically what works best.

If you do apply your separating line approach, you might consider using a branch-and-bound approach.  Keep track of the best solution you've found so far (i.e., the largest set of non-overlapping squares you've been able to find so far); say that it is of size $s$ at any point in time.  Now anytime your search tree enters a subtree where you can prove that all solutions below the subtree will have size $\le s$, there is no need to explore that subtree.  For instance, if you have a line $L$ and a subset $X$ where you know that the size of $X$ plus the size of the largest sub collection of non-intersecting squares above $L$ plus the total number of squares below $L$ is $\le s$, then there is no need to recursively compute the largest sub collection of non-intersecting squares below $L$, which saves you one recursive call.  But, if you use an off-the-shelf ILP solver, it will already implement these sort of branch-and-bound heuristics for you -- hence my advice to start by formulating this as an ILP problem and applying an off-the-shelf ILP solver.

Finally, the following paper apparently describes an $O(2^{\sqrt{n}})$ time algorithm to compute the exact solution to your problem.  This is an improvement over the obvious algorithm that enumerates all possible subsets of squares, which takes $O(2^n)$ time.

An application of the planar separator theorem to counting problems.  S.S. Ravi and H.B. Hunt III. Information Processing Letters, Volume 25, Issue 5, 10 July 1987, Pages 317–321.
http://www.sciencedirect.com/science/article/pii/0020019087902067


Showing that a binary linear code $C$ is self-dual Let $C*$ be the length 8 binary code obtained by adding a parity check symbol to each word in $C$. (so a word $c_1, c_2, c_3, c_4, c_5, c_6, c_7$ is extended to  the word $c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8$ for which $\sum_{i=0}^8 c_i =0$. Show that $C*$ is self dual (I.e show that $C*=C*^{\bot}$.

Where $C*^{\bot}$ is the orthogonal complement of $C*$

I am given the generator matrix for $C$:

$$G= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 0 & 0  \\
    0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}$$

So I think $C*$ is given by:

$$G*= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\
    0 & 1 & 1 & 0 & 1 & 0 & 0  & 1\\
    0 & 0 & 1 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 0 & 1 &1
\end{bmatrix}$$

I can show  $C*$ and $C*^{\bot}$ have the same dimensions but don't know what to do from here.

$G^*$ is also a parity check matrix of the code $C^*$ since $G^*G^{*T}=0$ and $\dim\ker\left(G^{*}\right)=\text{rank}\left(G^*\right)=4$.
 Since a parity check matrix of $C^*$ is a generator matrix of $C^{*\perp}$, we get that $C^*$ is a self dual code.


How to identify statistically distinct features of different sets? I have two non-overlapping sets of items, with feature counts for each. What standard algorithms can I use to extract the most statistically distinct features of each set?

For example:

Items served at American restaurants (5 restaurants surveyed):

bread: 4
burgers: 2
cheese: 1
cronuts: 2
pasta: 2

Items served at Italian restaurants (10 restaurants surveyed):

bread: 7
pasta: 10
cheese: 8

I want to be able to know that cronuts and burgers are distinctly associated with American restaurant menus, and cheese and pasta are distinctly associated with Italian restaurant menus.

Thanks!

This looks like a standard machine learning problem.  You could use any machine learning technique.  You might start with Naive Bayes.

If you want to evaluate a single feature, you could use information gain or BIC.

For the combination of all features, you can use a machine learning algorithm.  As I mentioned, I would suggest trying Naive Bayes first.  If you need something more powerful, there are many other classifiers: random forests, SVM's, k-nearest neighbors.  Read a textbook on machine learning to learn more about the subject.