Can someone help me understand cache conscience radix sort? (excerpt from journal article attached) Article:

CC-Radix: a Cache Conscious Sorting Based on Radix sort

(IEEE 2003)

I'm trying to figure out what the author means by this section:

  Explanation of CC-Radix For clarity reasons, we explain the recursive
  version of CC-Radix sort as shown in Figure 3. However, we use the
  iterative implementation of CC-Radix for the evaluations in this paper
  because it is more efficient. The parameters of CC-Radix are bucket, which
  is the data set to be sorted, and b, which is the number of bits of the
  key that still have to be sorted. Constant b is explained below.

CC-Radix(bucket, b)

￼if fits in cache (bucket) then
   Radix sort(bucket, b )
￼￼￼￼￼￼else
   sub-buckets = Reverse sorting(bucket, )
   for each sub-bucket in sub-buckets
      CC-Radix(sub-bucket, )
endfor
￼￼￼￼￼endif
end

  Figure 3. Pseudocode of CC-Radix The algorithm starts by checking
  whether the data struc- tures to sort bucket fit in cache level Li.
  Those data struc- tures are vectors S and D and the counter vectors C, one
  for each of the digits of the key. If so, CC-Radix calls Radix sort.
  If the data structures do not fit in cache level , the algorithm
  partitions that bucket into sub-buckets by sorting the bucket by the
  most significant digit using the counting algorithm (explained above).
  Here, we call this process of partitioning, Reverse Sorting, and it
  takes into account the computer architecture of the machine. For each
  sub-bucket, the CC-Radix sort is called again. Note that the first
  call to the routine processes the com- plete data set. Further calls
  to the routine process sub- buckets. Note also that certain subsets of
  the data may need more Reverse sorting calls than others depending on
  the data skew.

  Now, we explain the details of Reverse sorting and the sizing of the
  parameters of Radix sort. Reverse sorting. After each call of Reverse
  sorting, the number of digits that remain to be sorted for a specific
  sub- bucket is decremented by one.

I don't understand the "Reverse Sorting" part of this - how is that supposed to work?

I know this is a long shot, but I'm really stuck on what they mean.  Any help is appreciated!

The naming in the pseudo-code seems to be making things more confusing than they need to be, and it also seems to be glossing over some detail, but here's what I think is going on.

Let's just jump right in on a small example.
Suppose we have a data set, the integers 0-7 in binary:
$000, 001, 010, 011, 100, 101, 110, 111$. But obviously they're not necessarily given to you in sorted order. Let's say the input is actually:
$110, 101, 000, 010, 100, 111, 001, 011$.

If all this data fits in the cache, then you just run normal radix sort. That's the first branch of the if statement. For illustration, lets say that the cache can only hold two elements. Therefore, we end up in the else branch. The "reverse sorting" step splits the input into two sub-buckets based on the most significant bit.
So we get two buckets:

$1: (10, 01, 00, 11)$ and $0: (00, 10, 01, 11)$. We recursively call our function on each of these smaller buckets. Since they are smaller, they might now fit inside the cache, and we could run normal radix sort.

So now we're in the recursive call on the first sub-bucket. The input is
$1:(10, 01, 00, 11)$. However, our cache size is only 2. Therefore we move into the else branch again. We split the input into
$11:(0,1)$ and $10:(1, 0)$. and call the function recursively. Now finally on each of these recursive calls, the input is small enough to fit in the cache, and we run normal radix sort.

The other recursive calls function similarly.
Their pseudo-code seems to be missing how the partitions are pieced back together in a cache conscious way. Maybe this is obvious or covered elsewhere in the paper.


Could a quantum computer perform linear algebra faster than a classical computer? Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has anyone created a quantum algorithm for linear algebra, and what is it's running time? In theory, an operation such as matrix-matrix multiplication is highly parallelizable, however in practice it requires a lot of work to implement parallel matrix-matrix multiplication that runs quickly. Would a quantum computer provide any practical advantage?

Here are some pointers:

Quantum algorithm for linear systems of equations by Harrow, Hassidim, and Lloyd. This paper shows how to solve sparse systems of linear equations very quickly.
Quantum Algorithms for Linear Algebra and Machine Learning by Anupam Prakash. This PhD thesis proposes a quick algorithm for singular value estimation, and presents several applications.


Sorting functions by asymptotic growth Assume I have a list of functions, for example

$\qquad n^{\log \log(n)},  2^n, n!, n^3, n \ln n, \dots$

How do I sort them asymptotically, i.e. after the relation defined by

$\qquad f \leq_O g \iff f \in O(g)$,

assuming they are indeed pairwise comparable (see also here)? Using the definition of $O$ seems awkward, and it is often hard to prove the existence of suitable constants $c$ and $n_0$.

This is about measures of complexity, so we're interested in asymptotic behavior as $n \to +\infty$, and we assume that all the functions take only non-negative values ($\forall n, f(n) \ge 0$).

If you want rigorous proof, the following lemma is often useful resp. more handy than the definitions.

If $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ exists, then

$c=0 \qquad \ \,\iff f \in o(g)$,
$c \in (0,\infty) \iff f \in \Theta(g)$ and
$c=\infty \quad \ \ \ \iff f \in \omega(g)$.

With this, you should be able to order most of the functions coming up in algorithm analysis¹. As an exercise, prove it!
Of course you have to be able to calculate the limits accordingly. Some useful tricks to break complicated functions down to basic ones are:

Express both functions as $e^{\dots}$ and compare the exponents; if their ratio tends to $0$ or $\infty$, so does the original quotient.

More generally: if you have a convex, continuously differentiable and strictly increasing function $h$ so that you can re-write your quotient as
$\qquad \displaystyle \frac{f(n)}{g(n)} = \frac{h(f^*(n))}{h(g^*(n))}$,
with $g^* \in \Omega(1)$ and
$\qquad \displaystyle \lim_{n \to \infty} \frac{f^*(n)}{g^*(n)} = \infty$,
then
$\qquad \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.
See here for a rigorous proof of this rule (in German).

Consider continuations of your functions over the reals. You can now use L'Hôpital's rule; be mindful of its conditions²!

Have a look at the discrete equivalent, Stolz–Cesàro.

When factorials pop up, use Stirling's formula:
$\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

It is also useful to keep a pool of basic relations you prove once and use often, such as:

logarithms grow slower than polynomials, i.e.
$\qquad\displaystyle (\log n)^\alpha \in o(n^\beta)$ for all $\alpha, \beta > 0$.

order of polynomials:
$\qquad\displaystyle n^\alpha \in o(n^\beta)$ for all $\alpha < \beta$.

polynomials grow slower than exponentials:
$\qquad\displaystyle n^\alpha \in o(c^n)$ for all $\alpha$ and $c > 1$.

It can happen that above lemma is not applicable because the limit does not exist (e.g. when functions oscillate). In this case, consider the following characterisation of Landau classes using limes superior/inferior:

With $c_s := \limsup_{n \to \infty} \frac{f(n)}{g(n)}$ we have

$0 \leq c_s < \infty \iff f \in O(g)$ and
$c_s = 0 \iff f \in o(g)$.

With $c_i := \liminf_{n \to \infty} \frac{f(n)}{g(n)}$ we have

$0 < c_i \leq \infty \iff f \in \Omega(g)$ and
$c_i = \infty \iff f \in \omega(g)$.

Furthermore,

$0 < c_i,c_s < \infty \iff f \in \Theta(g) \iff g \in \Theta(f)$ and
$ c_i = c_s = 1 \iff f \sim g$.

Check here and here if you are confused by my notation.

¹ Nota bene: My colleague wrote a Mathematica function that does this successfully for many functions, so the lemma really reduces the task to mechanical computation.
² See also here.


Type inference with imports I understand how a type inference algorithm infers types within a single file by building on top of already inferred types and identified constraints (e.g. in the Hindley-Milner type system).

I am wondering about how this process works/is implemented for languages where some bindings are imported from other files. I wasn't able to find any useful information elsewhere, so I figured I'd just test my luck here.

The trivial approach would obviously be to leave the imported binding type-less (e.g. substitute a type variable) and continue adding constraints. Then, when the actual definition of the binding is encountered in the other file, it is checked that the constraints and actual type can be unified.
This approach has the major drawback that it basically discards all type information regarding a binding that may be present where it is defined.

Building on that first approach one could start by identifying an optimal order of analyzing files. In the case where there are no circular dependencies, this additional step would solve the problem. But in a lot of cases there are circular dependencies.

In TypeScript for example (afaik), circular dependencies are allowed without any loss of type information.

How is this problem usually handled in type inference algorithms?
Are there any resources/papers that describe this problem?

The first option is to simply process all the imports and see what is in them. This is not what you are asking, because it is equivalent to having everything in a single file, more or less. And it can be prety expensive to process all the dependencies.

What you are looking for is the notion of interface, also known as signature. To simplify things, an interface lists all the constants that are implemented in a given unit (file, module) together with their types. Thus, given that some file imports file X, all we need is an interface for X. Such an interface may be written by the programmer, or generated automatically and stored somewhere by a compiler, there are many ways to accomplish this.


Greater than or equal to operation (32-bit ALU) I'm trying to construct a greater than or equal to operation by adding some logic gates or building blocks (i.e. multiplexor and decoder) to my current 32-bit ALU

I'm not quite sure how to do this and nothing on google comes up for this operation from what I could tell.

ALU Design:

Question: How do I add a greater than or equal to operation to the current ALU? Also can you explain the changes you make so I can understand what's going on, thank you!

David Richerby's comment is right, in that the typical way it's "done" is to perform a subtraction and examine the "carry out" bit.

But I think it's worth stepping back for a moment and making a general comment about modern ALU design which may help you.

Thanks to Moore's Law, the number of transistors (and hence gates) required to implement a functional unit is not a serious limitation. Moreover, integer ALUs are not even close to the most power-hungry components of a modern CPU. So the main thing that needs to be conserved in a modern integer ALU design is propagation delay.

For essentially-single-cycle operations such as logic and add/subtract arithmetic, many modern integer ALUs are designed so that all potential operations are performed in parallel, and the "correct" one is selected with a multiplexer. This has the advantage that some of the multiplexer logic can be performed in parallel with the ALU operation, which again saves on propagation delay.

The same technique is used in floating point, incidentally. When performing a IEEE-754 floating point operation, the typical final step is that the result needs to be rounded correctly, using some logic which involves testing the answer and the FPU's current rounding mode. Many "real" FPUs essentially duplicate circuitry for some of the operation, performing three versions in parallel ("round up", "round down", and "pass through") and using a final multiplexer stage to decide which one to keep.

Of course, in real CPUs, ALUs typically aren't designed at the gate level these days, they are designed at the transistor level. So, for example, the multiplexer stage is probably achieved with high-impedance outputs followed by an amplifier stage to clean up the signal.


Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point.

One solution would be for each query to scan through every interval and see if it is contained in this interval or not, this would give us O(amountOfQueries*n) time.

I'm not sure how you would achieve better bounds for these queries with interval trees. In these trees every node is an interval but it also contains the maximum end point of the set of all intervals in the right sub tree.

If for each query you decide to search for all intervals that contain it in this interval tree, then you can still get the O(n) time if all intervals contain this point.

So, how can interval trees help in this case?

I think I have an algorithm but I'm not sure if it's correct.

We want to maintain an augmented binary search tree $S$ on each interval end point. The splitting element will always be the median end point so that the total height of our tree in the end is in the order of $\log_{2}N$.

In every node we use some data structure to store all intervals that go through the splitting element.

Assuming nothing more for our data structure, we can see that if $x_q$ is the query point, every time we visit a node we check to see if $x_{q}$ is to the right or to the left of the splitting element. If it is to the left, then no interval stored in any node of the right subtree will intersect $x_{q}$ so we will only need to check the left sub tree. The same applies to the case where $x_{q}$ is to the right of the splitting element.

So far we can find all relevant intervals in $O(\log n)$ time, but to find the exact intervals that intersect $x_{q}$, we have to see what's going on in this structure that we have for every node, so we also have to query each such structure along a root to leaf path to find exactly the intervals that intersect $x_{q}$

To do this, we can have two sorted lists $L$, $R$ on every node, each list will store the same intervals but $L$ will store them in a sorted order according to the left point and $R$ according to the right point.

Then whenever we visit a node we see if $x_{q}$ is to the left of the splitting element. If that's the case, we do a binary search on $L$ to find the right most interval that contains this point, since we know the index of this interval in $L$ we can find the total amount of intervals.

We process similarly $R$ if $x_{q}$ is to the right of the splitting element.

This algorithm will give us a $O(\log ^2 N)$ complexity.


Understanding a proof in the sweep line algorithm when finding all line segment intersections You have a set of line segments and you want to find all intersections.

First  sweep line approach:

Use a priority queue Q for the events as they come, where each event is just an end point of a line segment.

Use an unordered list L for the status of the sweep line, that is, all the segments that are currently intersecting the sweep line.

If you reach a beginning of a new segment, add it to the status and test it for intersections against all other segment in the status.

If you reach an end of a segment, remove it from the status.

This algorithm is O(n^2) if for example all segments are intersecting the x coordinate and assuming that you are sweeping from top to bottom.

Second sweep line approach:

It can be proved that we only have to test for intersections horizontally adjacent segments that are currently in the status of the sweep line. If you understand this proof then you can just use an ordered set for the status and come up with an easy O(nlogn) algorithm.

Here's part of the proof that I don't understand:

I don't think this is a clean proof of the lemma. Events are only either end points or intersections. So in practice the sweep line will never have no event points on it and from the image it seems like the sweep line is moving continuously, which is wrong because the sweep line moves from either an end point to another end point or end point to an intersection or an intersection to another end point.

How would you prove this lemma correctly?

The proof is absolutely correct. Of course, the algorithm only computes something when the sweep line comes to an eventpoint. Nevertheless you can think of the sweep line as a continiously moving line even if the algorithm does not hold everywhere to compute something.

Therefore you can always find a position, where the sweep line $l$ is close enough to $p$ and has no event point on it. In other words, you can always find a position above $p$ without eventpoints, where $p$ is the next eventpoint (maybe one of many). On this position, $s_i$ and $s_j$ are adjacent. There is no word here, that the algorithm computes something at this point and there is no conflict between the continuously moving sweep line and the discrete computing-positions of the algorithm.


Is there a poly-time algorithm for expanding out polynomials so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of
$$
z = (x+y)(x-y) \implies x^2+xy-xy+y^2
$$
but for any input with $n$ number of operations.
$$
z = (x_1+x_2+x_3+...+x_n)\cdot(x_1+x_2+x_3+...+x_n)\cdot...\cdot(x_1+x_2+...x_n) = ?
$$

I tried just doing the basic "by hand" method, but to me that seems like it would be on the scale of $n!$. Is there a better way of doing this? Thank you!

For the particular polynomial in the question, we have the multinomial theorem.
$$ (x_1+x_2+\cdots+x_n)^m = \sum_{k_i\geq 0,\, k_1+k_2+\cdots+k_n=m} \binom{m}{k_1,k_2,
\cdots,k_n} x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$$
where the coefficients are knowns as multinomial coefficients, and can be computed by
$$ \binom{m}{k_1,k_2,\cdots,k_n} = \frac{m!}{k_1!\,k_2!\cdots k_n!}$$

For most of general products of multivariable polynomials, there is no such closed formula for their expansion.


Static access pattern in Distributed Databases The access patterns of user requests may be static, so that they do
  not change over time, or dynamic. It is obviously considerably easier to plan for
  and manage the static environments than would be the case for dynamic distributed
  systems. Unfortunately, it is difficult to find many real-life distributed applications
  that would be classified as static. The significant question, then, is not whether a
  system is static or dynamic, but how dynamic it is. Incidentally, it is along this
  dimension that the relationship between the distributed database design and query
  processing is established.

What does it mean for an access pattern to be “static”? Could you show a practical example of a static access pattern?

I found what you copied in the following text

The idea is that users access (querying, updating or etc ..) of the database changes with time. It may be at its peaks in sale seasons for example if the database belongs to a commercial applications. etc .. - if it is always fixed and predicted then it is static.

From your copied text: it says that: "it is difficult to find many real-life distributed applications that would be classified as static. The significant question, then, is not whether a system is static or dynamic, but how dynamic it is." --

perhaps, a static access pattern is a collection of sensor nodes that update the database with their readings in a periodic time, with equal size updates always. -- or a set of servers that get a synchronization clock in a periodic manner  (quite theoritical i guess)


Two-State Turing Machine for Parenthesis Matching In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet (symbols), you can reduce the number of states down to only 2.

I was looking for examples of different Turing Machines and a common example presented is the Parenthesis matcher/checker. Essentially it checks if a string of parentheses, e.g (()()()))()()() is balanced (the previous example would return 0 for unbalanced).

Try as I may I can only get this to be a three state machine. I would love to know if anyone can reduce this down to the theoretical minimum of 2 and what their approach/states/symbols was!

Just to clarify, the parentheses are "sandwiched" between blank tape so in the above example
- - - - - - - (()()()))()()() - - - - - - - would be the input on the tape. The alphabet would include (,),1,0,-, and the *halt* state does not count as a state.

For reference the three state approach I have is as follows:
Description of states:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

Transitions Listed as:

Action: State Symbol NewState WriteSymbol Motion

// Termination behavior
Action: s2 - *halt* 0  -
Action: s1 -  s3    -  r

//Transitions of TM
Action: s1 (  s1  (   l
Action: s1 )  s2  X  r
Action: s1 X  s1  X  l
Action: s2 ( s1 X  l
Action: s2 X  s2 X r
Action: s3 (  *halt* 0 -
Action: s3 X  s3     X r
Action: s3 -  *halt* 1 -

Forgive the informal way of writing all this down. I am still learning the theoretical constructs behind this.

Just a "source code" compendium of Raphael's answer: this a working version that uses the same trick (on state q1) and has tape alphabet:
_  ( ) [ { / \   (where $\_$ is the initial blank symbol)

q0:  _ -> accept  // accept on empty string and on balanced parenthesis
     ( -> {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -> reject  // reject if found unbalanced ")"
     \ -> /,L,q0  // go left
     / -> \,R,q0  // go right

q1:  ( -> [,R,q1  // replace "(" with "[" and continue ...
     ) -> /,L,q1  // ... until first ")", replace it with "/" and goto left
     [ -> \,R,q1  // found matching "(" bracket, goto right and search for another ")"
     _ -> reject  // no ")" found for the first "{", reject
     { -> \,R,q0  // this must be the last match, goto q0 and check if it is true
     \ -> /,L,q1  // go left
     / -> \,R,q1  // go right

You can see it at work using a Turing machine online simulator; the source code is:

0 _ Y r halt
0 ( { r 1
0 ) N r halt
0 \ / l 0
0 / \ r 0
1 ( [ r 1
1 ) / l 1
1 [ \ r 1
1 _ N r halt
1 { \ r 0
1 \ / l 1
1 / \ r 1

A final note: if you want to see how this technique can be pushed to the limit, read (and try to understand :-) the construction of the Universal Turing machine with 2 states and 18 symbols by Y. Rogozhin in "Small universal Turing machines"


Running Time of Modular Exponentiation I am trying to understand why the modular exponentiation algorithm has a running time of about $\log(n)$ where $n$ is the exponent. Here is the algorithm:

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

I think it has something to do with the number of bits for the binary representation of the exponent. What is also an intuitive numerical example?

The main idea is that $a^x \cdot a^x = a^{2x}$.

Now, in order to get, say, $a^{10}$ you can do $res = res * a$ for 10 times.
On the other hand you can do compute $a^2=a\cdot a$, then $a^4=a^2\cdot a^2$, then $a^8 = a^4 \cdot a^4$, and get the final result by multiplying $a^8$ with $a^2$. That is, we "break" the computation in a similar way to the binary representation of the exponent.

Let me give  do the example in more details, and then give the general statement.
note that $10 = 1010_{(2)}$, and can think of each '1' bit as an element we need to multiply in order to get the final answer (here $a^8$ for the 4th bit, and $a^2$ for the 2nd lsb bit. The power is the same as the "value" of that bit in binary..).

Generaly, in order to compute $a^{exp}$, consider $exp_{(2)}$: the MSB is always 1, and you will have to compute the element $a^{2^{\lfloor \log exp \rfloor}}$, which will take you $\log exp$ (modular) multiplications, and generate
$a^2, a^4, a^8, a^{16}, ..., a^{2^{\lfloor \log exp \rfloor}}$. Finally, with another up to $\log exp$ multiplication you will multiply all the elements that correspond to a '1' bit in the binary representation of $exp$.


Kernelization algorithm for the following problem We are given an undirected graph $ G $ and a positive parameter
$ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not have any path on three vertices.
Is there any deterministic kernel algorithm for this problem with $ \Theta (k^2) $ vertices?
Kernelization algorithm definition: Given $ (G,k) $, output an equivalent instance $ (G’,k’) $ of the same problem in polynomial time, such that $ |G’| \leq f(k) $ and $ k’ \leq k $.

Your problem can be stated as $3$-path vertex cover problem. A simple google search gives this paper. The authors design a kernel of size $5k$ for this problem.


Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space? My recent question on Programming Puzzles and Code Golf got some fair attention and showed that not only it is very easy to output $10^{100}$ symbols and halt, but actually quite convenient in many programming languages as well.

While posting it I was wondering whether I should ask for $10^{10^{100}}$ instead but decided against that because while theoretically straightforward, I think it's simply physically impossible within this universe.

Here's my reasoning: to iterate over some command $b^m$ times, one needs $O(m)$ space to maintain the counter. Physical computers of today aside, $10^{100}$ just exceeds the estimated number of particles in the known universe by many orders of magnitude.

My question is not about alternative possibilities of physical realization of memory storage but about the principle. I'm not well-grounded in restricted Turing computation. Are there some tricks towards reducing the space complexity below $O(m)$ given that the value of the counter is never needed, just the fact that it counts the proper number of times and then halts?

The answer really depends on your computation model. On a (fixed) Turing machine, you can count up to $n$ using no space. A better formulation of the question is like this:

  Is there a function $f\colon \mathbb{N} \to \{0,1\}^*$ satisfying $|f(n)| = o(\log n)$ and a program $P$ such that $P(f(n))$ uses space $O(f(n))$ and outputs $1^n$?

It is a basic result of Kolmogorov complexity that this is impossible, even without the restriction on space. However, if you are willing to allow randomness and to incur some (multiplicative) inaccuracy, you can use the approximate counting technique of Morris and Flajolet, for which $|f(n)| = \Theta(\log \log n)$.


Is running AES NI in parallel possible (one encryption per core/thread)? AES NI seems to perform AES operations much faster than doing in software. However, if I have a machine with a large number of cores (say 32 cores), can I perform 32 AES encryptions using AES NI instruction i.e. one per core? Or can I just run one AES instruction?

It depends mostly on the memory bandwidth. Each core contains the dedicated AES hardware, but the CPUs need to obtain the data to encrypt or decrypt somehow. Even with a single core you have to be careful about how you dispatch instructions to get maximal performance, see Intel's white paper, page 48 bottom.

If you already have the machine, you can always try it out and let us know how it went.


Minimum cost max flow network problem with an alternative flow cost Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow * edge.weight over edges, but rather sum of  [edge.flow > 0] * edge.weight over edges, where [edge.flow > 0] equals one if the flow is greater than zero, and zero otherwise? Is it intractable, as I suspect?

I'll tell you about the original problem that I believe reduces to this problem. A bunch of friends have a dinner, and agree to split the bill evenly. But not everyone has enough money to cover their share at that moment, so some pay more than their share, some less, with the intent to settle later. Later on, they want to settle with a minimum number of transactions, where one transaction is money changing hands between a pair of friends.

This clearly maps to a bipartite network with edges of unlimited capacity from all the ones who underpaid going to all of those who overpaid, and edges of capacity equal to the amount underpaid going from source to the underpaid nodes, and edges of capacity equal to the amount overpaid going from overpaid nodes to the sink. To minimize the number of transactions we need to minimize the number of nonzero flow edges between the under- and overpaid.

This is sometimes called the minimum edge-cost flow problem or fixed-cost flow problem. As you suspected, it is indeed NP-hard, even when the network is bipartite. It is listed as problem ND32 in the list of NP-hard problems by Garey and Johnson:

M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

An approximation algorithm is discussed here:

S.O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth, R. Ravi. Flow Improvement and Network Flows with Fixed Costs. In Operations Research Proceedings 1998: Selected Papers of the International Conference on Operations Research Zurich, p. 158--167, Springer, Berlin, 1998.

The idea is to solve a standard linear-cost flow problem in which edge capacities are unchanged, but the cost of one unit of flow along edge $e$ is defined to be the edge weight divided by the edge capacity. This will give a solution that may weigh up to $F$ times the weight of the optimal solution, where $F$ is the flow value; but it will not weigh more than that.

If the approximate solution is not good enough, you might want to resort to an ILP solver.


How many gates until Turing Complete A computer can be pretty much made using just nand gates and a clock. Suppose you randomly place down nand gates on a board and connect them randomly to other nand gates. How many gates does someone have to put before it can be expected that the "computer" is Turing Complete?

A single finite machine is never Turing-complete.  (Such a machine with $n$ bits of internal memory has only $2^n$ states, so it can be modelled as a DFA with at most $2^n$ states.)  So, strictly speaking, it only makes sense to even ask about Turing-completeness when you have a machine model that is unbounded, or when you have an infinite family of machines $M_1,M_2,\dots$ of increasing size.

For similar reasons, strictly speaking, the computer sitting on my desk is not Turing-complete, either, because it is finite.  Nonetheless, it is useful to think of it as Turing-complete, in a looser sense: there is a natural abstraction of my machine where we disregard its finiteness (consider an abstract model where instead of being limited to 1TB of disk space, it has an unlimited amount of disk space).  For many purposes, the differences between my actual finite machine and the abstract, idealized machine with unlimited storage isn't very important.  But for your question, the difference can't be ignored, and to make your question well-specified, you'd have to think about how you plan to address this important distinction.

If you're interested in computing models that are somehow "simple"/"small" yet Turing-complete, you might be interested in rule 110, tag systems, and the lambda calculus.  See also
Universal binary rewriting system.  Do some searches on these terms on this site (and elsewhere) to learn more about these topics.


Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \{a^ib^jc^k \mid i ≠j ≠ k ≠ i \}$ is not context free.

From my understanding, we want to prove that all 3 conditions of the pumping lemma hold. This will not guarantee that the language is context-free. However, I have found a case where it breaks

Let the string be $abbccc$

If $u = \lambda$,
$v = a$,
$x = aa$,
$y = a$,
$z = bbccc$.

Therefore, when we pump the string for $i = 2$, we get $aaaaaabbcccccc$, which is NOT in the language because we have the same number of $a$'s and $c$'s. How is this possible?

The Pumping Lemma states: "... there exists a constant $p$ such that for each word $w\in L$ with $|w|\ge p$ there exists a decomposition $w = uvxyz$ such that ...", where $p$ is the pumping constant.

You have chosen your own decomposition, and shown it not fit the pumping property. Perhaps there is another decomposition that will work?

And even in the case your example would work, I can claim that the pumping is larger than 6.


Computer vision methods without "pre-training" I'm new to computer vision and I have a common question that I couldn't figure out with Internet or books.
As I understood, in general, there are two main approaches in modern computer vision: neural networks based methods and more "classical" methods that use feature extration (edges, keypoints, gradient and etc), like edge detectors, HOG, SIFT and others.

In case of neural networks everything is clear: we have a networks and we use datasets to train it. In other words, we can't use neural networks without previous training it (I call it "pre-training").

And as I understood, we have a bit different situation with features based methods. All examples and techniques that I have already seen consist of two steps. At first, we extract features (maybe with scene pre-processing), and then we use a classifier to recognize the object by those features. If we want classifier to work, we need to train it. So, again, like in case of neural network, we need pre-training.

My question is: are there any computer vision methods that don't need pre-training? Of course, maybe we can use something like a custom, or sometimes "naive" algorithm for certain situation, but are there more common methods? And another related question - are there any methods that can tell us just if the scene contains object, without telling were is it and what kind of that object class is it, again, without pre-training?

Thanks for all answers!

Yup, there are lots of them.  For example, image segmentation through graph cuts, camera calibration, image morphing, image stitching, reconstruction of a 3D scene from multiple 2D images, optical flow algorithms, motion tracking, image restoration and inpainting, and probably many more.


DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead? Summary
I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.)
Normally, when attempting to add an edge to a DAG that would cause a cycle, you instead detect the situation and abort.  I'm seeking an algorithm that will instead attempt to add the new edge anyway, modifying the graph such that it still represents the same tree, potentially partially decompressing parts of the graph in order to avoid the cycle.
Does an efficient algorithm to do this already exist?  I have been unable to find one in a perfunctory literature search, though I am not aware of the proper terminology for this operation, if one exists.
Simple Example

In this example, we are adding the edge F->C, which creates a cycle.  To break this cycle, we can split the E node into one version of E with C as a parent and one version of E with D as a parent (notated E'), similarly with F and C.
Slightly more complicated example

In this example we have several more cases. The offending edge from F to D is highlighted.  But there are several paths through the graph, some involving nodes upstream from D, some involving nodes downstream from D, and potentially some not involving D at all.
This graph is a compressed version of this tree:

where the highlighted copies of F are where placing D as a child is permissible. As you can see, these three nodes correspond to the three ways of reaching F' in the previous figure.
Motivating use case
In the game of Go, there is, in certain rulesets, the idea of superko, which forbids repetition of a previous board state.  Such positions are usually very rare in practice.  In order to efficiently search the game tree, we would want to take into account transpositions of sets of moves which leave the board the same, which is why a graph structure is useful, but in situations where a superko is possible the history of the position is also important, not just the current situation.  So while F->C would be a legal move normally, it is only a legal move in situations where C is not part of the node's history, i.e. we went through node D instead of node C.  So we would need to consider the cases separately.
Known Caveats
I am aware of the DAG cycle detection algorithm, and it seems like it might be easy to adapt this algorithm to perform this task, but I cannot seem to make it work. I am also aware that it is not always possible to split a graph in this manner to remove the cycle.

Any graph of this type can be represented using this simplified model (left):

where M1, M2, and M3 are metanodes that can represent 0 or more nodes, and edges involving M1, M2, and M3 can represent 0 or more edges.
In order to split the graph in the manner I am seeking, it's required to classify these nodes using the reachability algorithm.  The members of M1 are all nodes $k \not \in \{A, B\}$ such that $A \not \le k$.  The members of M2 are all nodes $k \not \in \{A, B\}$ such that $A \le k \land B \not \le k$.  Finally the members of M3 are the remaining nodes $k \not \in \{A, B\}$ and $B \le k$.
The members of M2 are duplicated along with B and A.  All edges from M1 to M2 or B are routed to M2' and B' instead.  And the edges from M2 and B to
M3 are duplicated for M2' and B'.  Finally, an edge from B' to A' is made.
The algorithm fails to place A' if and only if there are no edges connecting M1 to B and there are no edges from M1 to M2 or M2 to B, which represents the fact that there is no path to B without going through A, so there is no possible way to place A'.
So this problem can be solved with $O(n)$ lookups using pretty much any general reachability algorithm.


If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity? That is, if h(n) = h*(n), then A* only expands nodes that lie on an optimal path to the goal. But does this imply that A* will always take a linear time in the solution length to find an optimal solution?

I suspect I may be overthinking this problem, but if h(n) = h*(n) then we are measuring the exact heuristic cost of arriving at a goal node $n$ from x. But I can't see why this would be true, because even though you have a perfect heuristic, it is not monotone, and so you may have a cheaper f-value that may be expanded at a later point in the search, which no longer means the search space is linear.

First, to be specific I’m going to assume your heuristic function runs in constant time and we have a graph G with n nodes, and that you are asking about linearity with respect to n.

I claim that in the worst case A* will run in quadratic time.

Suppose G is a complete graph where every edge has a weight of 10000 except for the “true path” which winds from the starting node along every other node until the final node, and these edges have weight 1.

By definition of A*, every time we visit a node, we look across all its edges to queue up nodes into our priority queue of paths to explore. By construction, we visit every node and hence consider every edge. It is a complete graph on n nodes, so there is roughly n^2 edges, thus this process takes quadratic time


Removing $\epsilon$ transitions in a NPDA NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions.

However, NFA's with $\epsilon$ transitions could be converted to those without any $\epsilon$ transitions and hence they can be made to halt.

I was wondering if this is possible even for the case of NPDA's.

Is there a canonical epsilon-free form for PDAs

This effect I would not consider this a "halting problem" but there is a point here. A pushdown automaton can end its computation in an unbounded sequence of $\varepsilon$-moves. This behaviour can be avoided for general PDA, indeed. For each PDA there is an equivalent PDA without $\varepsilon$-moves. This is equivalent to Greibach Normal Form for grammars.

For deterministic PDA, DPDA, the situation is different. We would like to avoid this unbounded behaviour, in particular for the construction of the complement of the language of the DPDA. As you might know DPDA are closed under complement. Quite involved constructions can avoid infinite computations, but we cannot avoid $\varepsilon$-moves.

The language $\{ a^mb^nc^n \mid m,n\ge 1\} \cup \{ a^mb^nd^m \mid m,n\ge 1\}$ can be accepted by a DPDA but it has to use  $\varepsilon$-moves.


Reducing the integer factorization problem to an NP-Complete problem I'm struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Ladner's Theorem there exists a class of languages in NP but not in P or in NP-Complete. Every problem in NP can be reduced to an NP-Complete problem, however I haven't seen any examples for reducing a suspected NPI problem (such as integer factorization) into an NP-Complete problem. Does anyone know of any example of this or another NPI->NPC reduction?

Just to be absolutely clear, Integer Factorization is not known to be NP-intermediate, just suspected to be based on the lack of either NP-completeness proof or polynomial-time algorithm (despite lots of work put into both). I don't know of any natural problem (i.e. not constructed by Ladner for the proof) that is definitely NP-intermediate if P and NP are different.

Okay, after that disclaimer, Graph Isomorphism is another likely candidate for a natural NP-intermediate problem. There's a simple polynomial-time reduction from it to Subgraph Isomorphism - just leave the graphs the same! Graph Isomorphism is just the special case of Subgraph Isomorphism where both graphs have the same size. The final touch is that Subgraph Isomorphism is NP-complete.

Apart from that, there is always of course the not-so-informative reduction promised by the  Cook-Levin Theorem, we known that any NP-intermediate problem has some nondeterministic polynomial-time Turing Machine that decides it, and we can convert this into an instance of SAT (just have to build the TM!).


Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free? These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup  \{ a^n b^{2n} \mid n \geq 0 \}$
cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give no references as to where the proof comes from.

I was wondering, does anybody know of an academic paper or textbook that gives a full proof? I'd love to be able to cite it, but I haven't been able to find one.

The result is proved in Ginsburg and Greibach, Deterministic context free languages, Inform. Control 9(6), 620–648, 1966, Theorem 4.1 on page 24 (643). However, the proof looks somewhat different.


How is the data stored in AVL tree in a memory? I have been struggling to visualize how is the AVL tree is stored in memory?
Does it store data in array or list, If so how is it connected with its child and parents.

If I wanted to be really pedantic, the question would be unanswerable, as it depends on the particular implementation.

In most cases, however, the individual nodes of the tree are stored in one sequential chunk of memory that's allocated by whatever method your system/language provides (most common being malloc and/or new), each containing the key and the two pointers to child nodes, either of which can be a special value NULL, if a child is not present.

The individual nodes are usually scattered around the memory, with no clear relation between how/where they are located. We leave this for the memory allocator of the environment to handle. When we allocate a new node, we place its address (a pointer to it) in an existing node (or, as a special case, in the root pointer), so we can navigate to it.

Think of this as a linked list, where each item can have not only one, but two successors.


Difference between HSI and YCbCr for pattern recognition by color I am doing a project on face detection in C#. I want to find the skin area by using skin color segmentation. For that purpose, I have to extract the skin area.

I know I can use HSI or YCbCr, but what is the exact difference between these?

I'm not an expert, but judging from the Wikipedia articles, YCbCr is used for image compression (JPEG and television [YPbPr]), while HSI is used in computer vision. Since you're doing computer vision, if we believe Wikipedia then you should use HSI. Of course, you could always experiment with both representations and all six dimensions. See what works best. If you're fitting a linear model, then it doesn't really matter, and you can even use RGB.


Meaning of polynomially larger or smaller in the context of the master method I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or larger than $f(n)$.

What I mean is $n^{\log_ba}$ being polynomially larger or smaller than the function $f(n)$ for recurrence relations of the form: $T(n) = aT(\dfrac nb) + f(n)$.

Case 1 is the case in which $n^{\log_ba}$ is polynomially larger than $f(n)$.
Case 2 is the case in which $n^{\log_ba}$ is equal to $f(n)$.
Case 3 is the case in which $n^{\log_ba}$ is polynomially smaller than $f(n)$.

As my book defines it, for case 1 to apply $n^{\log_ba-\epsilon}$ for some $\epsilon > 0$ must be larger than $f(n)$. in other words, $n^c > f(n)$ where $c< \log_ba$.

Similarly, for case 3 to apply $n^{\log_ba+\epsilon}$ for some $\epsilon > 0$ must be smaller than $f(n)$ or in other words $n^c < f(n)$ where $c > \log_ba$.

Another way to think of subtracting $\epsilon$ is to think of $\dfrac{n^{\log_ba}}{ n^e}$ for some $\epsilon > 0$.

and another way to think of the adding of the $\epsilon$ is to think of $n^{\log_ba}*n^\epsilon$ for some $\epsilon > 0$.

In my class slides on the master method the first example uses the recurrence $T(n) = 4T(\dfrac n2) + 1$ and suggests the possibility that case 1 applies. $n^{\log_ba}$ would be $n^2$ and $f(n)$ would be 1.

The slide points out that $f(n)$ is NOT polynomially smaller than $n^2$.

I do not fully understand this because if you take $0 > \epsilon > 1$ such as $1/2$ for example.

You can then subtract this epsilon from $n^2$ and you'd have $n^{1.5}$ which would still be greater than $f(n) = 1$ for any $n > 1$.

So how is this not an example of being polynomially smaller?

Further, the slide which explains that $f(n)$ in this example is not polynomially smaller, indicates that $T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$ doesn't work

but why would they have attempted to divide $n^2$ by $\log n$ in the first place? I get the the division is equivalent to subtracting an $\epsilon$ from the exponent of $n$, but why $\log n$, what is the significance?

*Edit: my professor's response:

As an example (assuming all numbers are positive to keep it sjmple), the idea is that for any numbers $p$ and $q$, if $q > p$, $(n^p)*log(n) < n^q$ asymptotically, no matter how close to $p$ the number $q$ is.

So $n^p*log(n)$ is not polynomially larger than $n^p$ because for any $q > p$, eventually it will be smaller then $n^q$

(This answer refers to the version 6 of the question, which does not contain "my professor's response".)
It looks like there is some typo/inconsistency/misunderstanding somewhere in your class, the slides or your post. Hence, I will start from scratch, addressing the problems I can recognize.
Let me fix the meaning of "polynomially smaller" and "polynomially larger" in the current context. There are other usages, which are not relevant here.
Meaning of polynomial differences.
$f(n)$ is polynomially smaller than $g(n)$ if $f(n) = O(g(n)/n^\epsilon)$ for some $\epsilon > 0$.
$f(n)$ is polynomially larger than $g(n)$ if $f(n) = \Omega(g(n)n^\epsilon)$ for some $\epsilon > 0$. We will never say $f(n)$ is polynomially equal to $g(n)$.
Here are some examples.

$f(n)=1$ and $g(n)=n^2$. Then $f(n)$ is polynomially smaller than $g(n)$. This is what you believed and it is correct.
$f(n)=g(n)=n^2$. Then $f(n)$ is not polynomially smaller nor polynomially larger than $g(n)$.
$f(n)=n^{1+\frac{1000}{\log n}}$ and $g(n)=n^2$. Then $f(n)$ is polynomially smaller than $g(n)$.
$f(n)=\dfrac{n}{\log n}$ and $g(n)=n$. Then $f(n)$ is not polynomially smaller nor polynomially larger than $g(n)$.

$T(n) = 4T(\dfrac n2) + 1$
$a=4$, $b=2$, $n^{\log_24}=n^2$ is polynomial larger than the constant function 1. This is case 1 of the master's theorem.
$T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$
$a=4$, $b=2$, $\dfrac{n^2}{\log n}$ is not polynomially smaller nor polynomially larger than $n^2$. None of the three cases of master's theorem can be applied. However, the extension of case 2, case 2b can be applied.

Simple exercises
Exercise 1. Suppose $f(n)$ is polynomial smaller than $g(n)$. Show that $f(n)$ is eventually smaller than $g(n)$, i.e., there exists some constant $n_0$ such that $\lvert f(n)\rvert \lt g(n)$ for all $n>n_0$.
Exercise 2. Verify that $f(n)$ is polynomial smaller than $g(n)$ if and only if $g(n)$ is polynomial larger than $f(n)$, assuming that both $f$ and $g$ are always positive.
Exercise 3. Suppose $f(n)$ is polynomial smaller than $g(n)$. Find another function $h(n)$ such that $f(n)$ is polynomial smaller than $h(n)$ and $h(n)$ is polynomial smaller than $g(n)$.


Is it possible to solve maximum weight independent set in linear time for a cycle? Given a cycle of $n$ vertices and each vertices of the input graph $G$ assigned a weight.

We want to find an independent set of cycle such that weight of the vertices taken in the independent set is maximum.

A brute force way is consider cycle as a set of three consecutive vertices and pick the one with max weight, but the runtime of this algorithm will be $O(2^\frac{n}{3})$.

This can be done in polynomial time by dynamic programming. Let the cycle be $x_1\dots x_\ell x_1$ and let $I$ be a maximum-weight independent set.

First, observe that either $x_1\in I$ or $x_1\notin I$.  In the first case, $I$ is the union of $\{x\}$ and a maximum-weight independent set in the path $x_3\dots x_{\ell-1}$ and, in the second case, $I$ is a max-weight ind-set in the path $x_2\dots x_\ell$.

So it suffices to be able to find a max-weight ind-set in a path $y_1\dots y_k$.  But we can do this by the same trick: either the set is $y_1$ plus a max-weight ind-set in $y_3\dots y_k$ or it's a max-weight ind-set in $y_2\dots y_k$.


Constructing Turing machines I get the main ideas of Turing machines. But I can't construct a Turing machine to solve a given question.

The question I'm trying to solve is "Construct a Turing machine that recognises the set of all strings that contain an even number of $1$s."

How can I think about all the cases? Is there a way to do it?

It is simpler than what you think. You don't even need a Turing machine that writes to the tape.

Here is a Turing machine whose final state would be $YES$ if the string (in tape) contains an even number of 1's, and in $NO$ if the string contains an odd number of 1's, assuming the string marks its end with a #, and it starts from left to right.

Let $ M = (Q, Γ, Σ, δ, s, B, F)$ be a Turing Machine with the definition

$$Q = \{read_0,read_1,YES,NO\}$$

$$Γ = \{1,0,\#\}$$

$$Σ = \{\}$$

$$F = \{YES,NO\}$$

$$s = read_0$$

$$B=\#$$

$δ$ is given by $δ_{q\ t} = ( move \,\ next\ stage)$ where $t$ is the tape symbol that it reads, and $q$ represents each state:

$$δ_{read_0\ 0} = (R,read_0)$$
$$δ_{read_0\ 1} = (R,read_1)$$
$$δ_{read_0\ \#} = (0,YES)$$
$$δ_{read_1\ 0} = (R,read_1)$$
$$δ_{read_1\ 1} = (R,read_0)$$
$$δ_{read_1\ \#} = (0,NO)$$

Basically what it does is that if it see $1$ it alters between $read_0$ and $read_1$ states. And if it is in $read_0$ state and sees $\#$, which means the string ended, it would go to the final state, $YES$. If it is in $read_1$ and sees $\#$ it would go to $NO$.

So if the string contains three $1$s, the states change in this way $$read_0 \rightarrow read_1 \rightarrow read_0 \rightarrow read_1 \rightarrow NO$$ implying that it doesn't contain an even number of 1s.


Need help with adding elements to hashtable with linear probing Here is an example problem which I have having trouble figuring out. The red text is the answer.

I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at index 3, 5 at index 1, etc.)

But when the table is resized, each element has a new position. HOW is 1's new index 0? HOW is 5's new index 7? How did each element of the array get assigned their new index upon table resize?

Any help would be appreciated.

Thanks

It's not explicitly defined - rather there's an implicit subindex (based off the table's size) to the hash-function. At the start we had e.g., $h(0) = h_7(0) = 3$. They are then informing you that $h_14(0) = 8$. There is no explained reason for this. They then re-insert the data to the larger hash table going over the old data in the order it appears in the hash table.


Difference between *device descriptor* and *device handler* I am studying Computer Architecture,
and am a bit confused about the difference between device descriptors and device handlers in operating systems. Am I correct in saying that a device handler is actually a device driver?

What confuse me is that while the terms
device handler and device handler appear in the course slides,
I couldn't find then in the course textbook.
The closest term I could find there is device driver.

Where did you find that terminology? Check how it is defined there.

If it was up to me, a "device descriptor" would be a way to describe a device, perhaps a data structure giving details on it (or some sort of reference to it, like a pointer or an index into an array of the above).

As you state, in my book a "device handler" would be some sort of routine (or a set of routines) to manage it, a driver.


Terminology for describing a kind of server What is the adjective used to describe the fact that a server keep track of queries made by a user. I take the example of a database server.

Such a server would be stateful rather than stateless: roughly speaking, stateful means that it keeps some information, possibly partial information, on past queries.  If you are looking for a single word to capture the idea that the server stores a complete record of all past queries, in their entirety, I don't know of a single word that does that -- so just use a sentence to describe what you're talking about.


How to represent symbolic knowledge using real numbers - theory about neural networks and natural/analog computing? One can define the semantics of one definite word using the references to real world entities, relationships with the other words and other concepts and represent all this knowledge about this one word using logical symbolic expressions. And then one can encode all this set of symbolic expressions into vector of real numbers. This is word embedding that is used in natural language processing, distributional semantics of the word in opposite of the formal semantics of the word.

One can consider function of software program (e.g. functional program or any other program). One can encode this program in the multiple vectors and matrices of real numbers that are used for the definition of neural network.

One can consider symbolic meta-knowledge and encode them into vectors or neural networks as well.

The decoding process can be more tricky. There is more or less elaborate decoding of neural network - e.g. see Google queries "logical program extraction from neural networks" or "symbolic rule extraction from neural networks". But I have not seen the work about extraction of more or less static knowledge base from the word-embedding-vector.

So - I have two questions regarding this matter:

Is there symbolic knowledge extraction from the word-embedding vectors - some kind of decoding algorithm from vector of real numbers to the set of logical formulas?
Is there general theory of mentioned encoding algorithms? The usual approach is to train neural networks and to arrive at the encoded form using non-symbolic methods, non-algorithmic methods, implicit way. I have heard about embedding of symbolic knowledge in neural networks to speed-up training, but such kind of work is scarce. But what about general encoding algorithms?

There are discrete, natural Goedel numbers (encoding algorithms) that can be assigned to any theorem of first order logic. But what about such Goedel numbers for the sets of formulas or for some computational program (as a set of commands)? Can we enumerate all such sets using natural numbers only or maybe the real numbers are needed instead naturally. Or maybe even set of real numbers are required for encoding the set of symbolic formulas or program statements? Is there such research work which I can develop further? If no, then what ideas can be mentioned for such encoding/decoding schemes?

Such encoding-decoding algorithms can be related to biological computing and ultimately they can lead to the explanation of brain activity.

No, probably not.  I think you're expecting too much from the current state of the art in word embeddings.  Word embeddings don't magically capture all semantic knowledge.  They don't reflect perfect understanding of the language.  Instead, they're just useful mappings where similar words often have similar embeddings.  Moreover, the way word embeddings are constructed has nothing to do with logical formulas.

I don't think you're going to find that word embeddings solve the problem of converting from natural language to formulas.

I don't know what would count as a general theory of encoding algorithms for you.  There are certainly multiple papers that propose different methods of constructing different word embeddings; you could read those to understand the state of the art.


How to properly compare performance of a prototype against a baseline Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average).

I have m queries/problems that I run on each software with a timeout T. I record the raw running times $b_1,\dots,b_m$ of B and $t_1,\dots,t_m$ of P.  It could be that for some (few) problems B is still faster than P, moreover it could be that there are very short times such as 0.01s or considerably longer ones, for instance, 3000s. Now my question is, what is a good measure to compare the performance of B and P quantitatively on average?

A straightforward (but probably crude) measure could be just computing the average running times $b_a = \frac{1}{m}\sum_{i=1}^m b_i$ and $t_a = \frac{1}{m}\sum_{i=1}^m t_i$, and taking $\frac{b_a}{t_a}$.

A variation of this measure is taking the average of times when both systems didn't timeout and counting the number of timeouts, although not sure how to get just one measure from these four values.

These two measures do not address one my concern related to the variance in the values of the times. For instance, for $m=2$, $b_1=2500$s, $t_1=8$s, $b_2=2000$s and $t_2=1000$s, the first measure is 4.4643. Does it mean that P performs on average 4 times faster? Would it be more reasonable to take the average of the normalised times $\frac{1}{m}\sum_{i=1}^m \frac{b_i}{t_i}$? In this case it would be equal 157.25 and, seems to me, would better reflect the performance gains.

And again, a question is how to take timeouts into account properly.

I am sure that there should be standard approaches to comparing performance of two systems(for instance, databases), but I wasn't able to find anything quickly. I would also be grateful to see an explanation why one measure is better than the other, and what are the standard measures (at least on the scientific community).

The general answer is of course: "It depends on the problem and the final utilization of your software".

The first question you should answer is what makes a given version query time so variable ? Is it query dependent ? Does the software have some buffering between queries ? Maybe a ressource variable availability ?

Generally the performance of an algorithm is evaluated considering the worst query possible. Let's take an example, you need an algorithm to find where a function change of sign:

You may loop on all points one by one or do a binary search. The former would sometimes performs faster if the searched point is one of the first. Nevertheless, in worst case it has to analyse all points whereas the latter finds the solution in logarithmic time.

Now if you have a timeout, the main metric you have is how many timeouts gets each solution. Maybe you even can identify what queries lead to timeout for each algorithm. In my opinion, there is no sense to compare average query time if some algorithm gets timeout more often.


Show that if A is regular so is $A^{R}$ I'm stuck on "For any language $A$, let $A^R = {w^R | w \in A}$ Show that if A is regular, so is $A^R$."

According to my research (see references), the steps required to prove this question, are:

Reverse all the links in the automaton
Add a new state (call it $q_s$)
Draw a link labeled with ϵ from state $q_s$ to every final state
Turn all the final states into normal states
Turn the initial state into a final state
Make $q_s$ the initial state

Anyway, I decided to make a toy-example to check if those steps made sense to me.

So here it is :

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

I want to read $w = {ab}$, However, I'm extrapolating that we can also read $w = \{ab\}^+$.

So I have built an DFA for it :

Then, I followed the instructions and built this NFA :

Now the questions :

1- Why do I have to make it  as an NFA instead of making an DFA that recognizes $w = {ba}$ or $w = \{ab\}^+$ ?

2- Can i kill the state $q_3$ of this NFA ? It's dead so why it should be there anyway?

3- Why the first state of the NFA transitions with $\epsilon$ ?

Whats really bothering me is the first question.
I can make an DFA that recognizes the Reverse of w = "ab". So why everywhere I research says that I must do it as an NFA?

Here's the DFA that recognizes $w = {ba}$, Once Again, I'm extrapolating that we can also read $w = \{ba\}^+$. Not sure if i should assume that, anyway :

"You need at least 10 reputation to post more than 2 links."

So why isnt that DFA enough to prove that if A is regular, so is $A^r$ ?

References :

"You need at least 10 reputation to post more than 2 links."
cs.stackexchange.com/questions/3251/how-to-show-that-a-reversed-regular-language-is-regular

Why do I have to make it as an NFA instead of making an DFA...

You don't have to, but making an NFA allows you to use $\epsilon$ transitions, which are convenient for making your procedure.

Can i kill the state q3...

Sure, but it wouldn't be useful for your proof.  Dead states don't hurt anything, and it would be harder to write this step into your procedure.

Why the first state of the NFA transitions with ϵ?

Because the FMS you are working from may have had multiple final states, so you need a way to encode multiple potential starting points.  Using $\epsilon$ transitions gives you a choice of multiple states.

What you're trying to do is make a procedural proof.  In essence, you're trying to show that for every FSM $A$, you can follow some formula to construct a FSM that also accepts $A^R$.  If you can always construct a Finite State Machine for $A^R$, then $A^R$ must be Regular.

The machine that results from your process doesn't have to be the most efficient machine or contain the minimum possible number of states.  This isn't a work of art, it's a proof of concept: if you can always make an appropriate reversal machine, then your reversal must always be regular. All it must do is work every time to accomplish your proof.


Algorithm for token replacement game I'm having problems finding an algorithm to the following problem:

A and B take turns replacing a number $n$ of tokens with either $floor((n+1)/2)$ or $n-1$. The player who makes one token remain wins. We want to know, if there is a way for B to win the game no matter the moves of A. A begins the game.

My idea is the following:

Is n = 1 -> No way for B to win the game

We try all moves of first A then B and check for 1 -> There is a way for B to win

But this does not incorporate the "no matter the moves of A" criteria.

I'd check what happens for some small(ish) values of initial $n$, working up. If you know who wins if there are at most $n$ on the table, working out what happens with $n + 1$ is easy.


Machine learning algorithm(s) for recognizing simple graph patterns I generate some simple graphs based on usage stats of a website, and they may look like these:

I call the 'pattern' on the left 'convergence', and the 'pattern' on the right 'divergence'. The terms 'convergence' and 'divergence' are loosely and visually defined, and they simply means that the two curves either become closer and intersected (decreasing difference in Y while increasing in X) or become apart (increasing difference in Y while increasing in X)

Of course, the curves may neither converge nor diverge. An extreme case of such case is they may evolve more or less parallel to each other.

My problem is to recognize the convergence and the divergence patterns. This may be trivial as done visually by human, but I want to automate the task using an algorithm, and likely a ML algorithm. "Pattern recognition' comes to mind as a (broad) area relating to this kind of problem.

I have some very high-level idea about a possible approach: first manually label some existing graphs as 'convergence', 'divergence', or 'other', and then use a set of these categorized graphs/images to 'train' the ML algorithm in the hope that the algorithm can recognize the patterns on its own after proper training.

My specific questions are:

What are the recommended ML algorithm(s) for this problem? And any pointer to the theory and implementation of such algorithm(s) is appreciated.
I may be terribly ignorant, but: does such a ML algorithm operate on the graph/image directly or does it operate on the underlying data points that make up the graph? In other words, what would be the input to the algorithm? A series of images or a bunch of numbers?

I suspect machine learning is the wrong approach.  Instead, I suspect you will do better to define a metric and measure the metric, or define a hypothesis and use hypothesis testing.  You are not trying to predict the future evolution of these values; that's something that ML might be suitable for, but that's not what you're trying to do, so ML doesn't seem like the right tool for the job.

Let me suggest an approach.  If $f(t),g(t)$ are the values of the measurements at time $t$, define $D(t) = |f(t)-g(t)|$ (the absolute value of the difference).  $D(t)$ measures how close they are.  Then, you want to test whether $D(t)$ is increasing or decreasing.  If $D(t)$ is decreasing, then you have a situation of "convergence"; if $D(t)$ is increasing, then you have a situation of "divergence".

How can you test whether $D(t)$ is increasing vs decreasing, over some time period?  Here's one simple approach.  You could separate your time window into two halves, the first half and the second half.  Calculate the average value of $D(t)$ over the first half, say $\mu_0$, and the average value of $D(t)$ over the second half, say $\mu_1$.  Now you can compare $\mu_0$ to $\mu_1$, to determine whether it is increasing or decreasing.

Alternatively, another approach would be to use simple linear regression on $D(t)$ to fit a linear model $D(t) \sim \alpha t + \beta$, and then test whether the slope $\alpha$ is greater than zero or smaller than zero.

However, one problem with this is that your conclusion might be confounded by noise: it might be that $D(t)$ is neither increasing nor decreasing, but all you're seeing is statistical noise.  So can you separate out the case where $D(t)$ is increasing from the case where $D(t)$ is decreasing?

The answer is yes: you can test for statistical significance using hypothesis testing.  If you observe $\mu_0 > \mu_1$, you can use a hypothesis test to test whether this difference is statistically significant (e.g., using a permutation test).  Or, if you fit a linear model and find $\alpha > 0$, you can use a hypothesis test to test whether the difference from zero is statistically significant (this is covered under standard textbooks on linear regression).

There's lots more one can say about hypothesis testing, but this should give you the general approach.  The short version is: don't use machine learning; using an appropriately chosen statistical measure or statistical hypothesis test.


Does overclocking a cpu speed up a poorly optimised process? Perhaps this isn't exactly a computer science question, but I thought this wouldn't strictly fit in Electrical Engineering either. Let me know if I should move this somewhere else

Suppose I have a process that is single-threaded and rather poorly optimised. It doesn't max out my processor, and instead stays stuck at around 20% usage. Would overclocking my CPU even really affect the running speed?

Optimization is not really something that should be guessed at. Instead you need to measure what is going on to determine the chokepoints and where changes need to be made.

A faster processor may have little or no effect especially since the CPU utilization is not maxed out. CPU speed affects only those parts of the program which are actually running on the CPU. If the program is waiting for something else such as an I/O operation, a faster CPU doesn't help. The chokepoint is not the CPU speed but rather the I/O speed.

So you may have a faster CPU but that just means that your program gets to a place where it has to wait for something else to happen a bit faster. If your program requires user input then no matter how fast the CPU, the program is still bounded by the speed of a human doing the input.

Program speed also is affected by the algorithms being used. A faster CPU may help a bad algorithm go faster, a kind of linear increase, a better algorithm may provide several orders of magnitude improvement in speed and performance.

Another possible throughput increase can come from multi-threading. This only really helps if you can divide out the overall problem into multiple, asynchronous tasks that can be run simultaneously and the results of each task combined when all are done. The more need there is for synchronizing tasks and events the more likely that multi-threading will not provide that much of an improvement.

With multi-threading there is always the question of how many separately running cores are in the CPU or how many CPUs are being used for the program.

Multi-threading with a single core on a single CPU may or may not help since the various threads are sharing the same core and CPU. It depends on whether some threads are able to progress while other threads are waiting for some resource or event to happen such as I/O to complete.

If you are able to divide out the program into multiple threads and assign the different threads to different CPU cores or multiple processes and assign the different processes to different CPUs then more things can be happening simultaneously. However if all those threads are not compute intensive and are waiting rather than running then it may not make that much difference.

Finally the actual hardware design can make a large difference in the throughput of a CPU. Overclocking a CPU means that it is running faster however it is the same hardware. The differences in throughput between various CPU generations is not due to just CPU clock speed. There are also hardware improvements so that two CPUs with the same clock speed will show very different processing throughput because the hardware design of one is superior to the other. This is where design details such as branch prediction, prefetch, size of the onboard cache, and other hardware details really make a difference.


Combinational Logic - Need help with proof by rewrite In my Computer Logic class we were assigned the following problem:

  Complete a truth table that has $3$ inputs $(A, B,C)$ and one output
  $(F)$.   $F$ is        asserted whenever $B$ or $C$ are asserted, but
  deasserted if both $B$ and $C$ are asserted.  $F$ is asserted whenever $A$ is
  asserted and $C$ is deasserted.  $F$ is deasserted in all other cases.

After which we are supposed to

  Determine the sum-of-products equation for $F$.  Show the terms instead
  of the minterm abbreviations (show $ABC$ instead of m7).

Finally, we are supposed to:

  Prove that $F$ from question $2$ is equivalent to $F = BC' + B'C + AC'$
  using proof by rewrite.  HINT: remember the uniting law is the key to
  minimization.

Here is what I have:

1)

A    B    C    F
0    0    0    0
0    0    1    1
0    1    0    1
0    1    1    0
1    0    0    1
1    0    1    1
1    1    0    1
1    1    1    1

2) $F = A'B'C + A'BC' + AB'C' + AB'C + ABC'$

Number three is what is throwing me. I am using the axioms of boolean algebra, such as the Uniting Law, but so far all I have been able to do is the following:

3)
    A’B’C + A’BC’ + AB’C’ + AB’C + ABC’ = BC’ + B’C + AC’

A’B’C + A’BC’ + AB’C’ + AB’C + ABC’

A’B’C + AB’C + A’BC’ + AB’C’  + ABC’            Commutative Law

B’C + A’BC’ + AB’C’ + ABC’                      Uniting Law

A’BC’ + ABC’ + B’C + AB’C’                      Commutative Law

BC’ + B’C + AB’C’                               Uniting Law

That's as far as I am able to get. Did I screw up the truth table, resulting in incorrect minterms, or did I miss something?

Appreciate the help!

The last line is wrong :
1    1    1    1
Should be :
1    1    1    0

But the equations following are correct.

For the simplification :
BC’ + B’C + AB’C’ = BC' + B'.(C+AC') = BC'+B'.(C+A)=BC'+B'C+B'A

(I don't know the name of the rules used, there is some associativity, "X+X'Y = X+Y", etc...)

--- edit ---

Let's prove that X+X'Y = X+Y

Using :

A = A.B + A.B'
A = A+A
A + AB = A.(1+B) = A
A + A' = 1

X+X'Y = XY+XY'+X'Y = Y(X+X') + XY' = Y + XY'

Repeating (A=A+A) :

X+X'Y = X+X'Y + X+X'Y = X+X'Y + Y+XY'

= X + Y + X'Y + XY'

= X+XY' + Y+X'Y

= X + Y


Negative Numbers in 32 bit Floating Point IEEE Numbers So I understand the logic behind converting positive decimal numbers to IEEE 32 bit floating numbers but I'm not completely sure behind the negative one's. If for example we have a decimal number say -15.5, do we have to do two's complement first then convert it to the floating point representation or we directly do it for 15.5 and at the sign bit we do 1.
Thank you in advance.

Contrary to two's complement representation of negative integers, the negative numbers in IEEE floating-point are represented with only a sign bit change, as shown in there.
For example, $0\cdot01111100\cdot01000000000000000000000$ is the representation of $0.15625$, and $1\cdot01111100\cdot01000000000000000000000$ is the representation of $-0.15625$.
In particular, there are two representations of zero (the positive one and the negative one).


Why can't we compute the lexicographically-least word of a given length on which a given TM halts? I had this question in my exam. but my answer is wrong(I didn't receive explanations why...)
$$f(\langle M\rangle,1^n)=\left \{ \texttt{the lexicographically smallest } x\in\left \{ 0,1 \right \}^n \cap L(M) \texttt{ if } n>100\texttt{ and }L(M)\cap \left \{ 0,1 \right \}^n \neq\varnothing \texttt{, otherwise undefined}\right \}$$
I answered it is computable.
for input $(\langle M\rangle,1^{n})$ when $n \geq101$
I run the machine on all possible inputs in $\Sigma^{n}$ and output the first result when conditions are
met.
I was wrong and apparently the language is not computable. what did I miss?

Since for a given $n$, there are only finitely many strings in $\Sigma^n$, saying "run $M$ on all words from $\Sigma^n$" does make sense. But we need to be somewhat careful about the details here.

We could run $M$ on all $w \in \Sigma^*$ in parallel. If we do that, then (assuming that $M$ halts on at least one of them, which we may do here), there is a first word for which we learn that $M$ halts on it. But "first" here refers to our particular simulation, and to how long $M$ takes on the various words. This will generally not be the lexicographically first word; so this is not doing the job.

We could run $M$ on the words $w \in \Sigma^*$ in lexicographic order. But now, if $M$ doesn't halt on $0^n$, we never proceed beyond this particular simulation.

To prove that the function is indeed non-computable, mirror the proof of Rice' theorem.


applying CTL/LTL model-checking on some system I apologies if my title is vague, I'm trying to apply CTL/LTL model-checking on some system written in java, however, I still don't understand how to reach a result using either of the approaches mentioned. Do I model my LTS/write specification and use a tool like SPIN to validate that or? I'm mainly looking for a point at a direction that will help me in making a start.

Again sorry but I made this thread after so much frustration searching for an explanation to my problem.

Thank you

I'm pretty sure that you need your system to be designed in Promela, rather than Java. You then input the system in Promela, and the specification in LTL (or CTL) to SPIN, which outputs a C code for a model checker for the specific instance.


efficient cumulative all over combinations of boolean vector elements Problem

Given a vector of bools of length n I wish to compute the logical and over all subsets up to length k.

By logical and I mean that for a subset to give true all of its elements must be true.

Example:

With a boolean vector of 3 elements (indexes below each for reference below)

v = [true, true, false]
i =    0     1     2

The intended result for all subsets (i.e. up to k = n):

result = [true, true, false, true, false, false, false]
i.e        0     1      2     0&1   0&2    1&2   0&1&2

where the true at 01 is the result of true & true from the 0 and 1 indices in the original vector.

If we limit up to k = 2 the intended result is:

result = [true, true, false, true, false, false]
i.e        0     1      2     0&1   0&2    1&2

The order of the output need not be this one.

What I want

I want an algorithm that will not perform more operations than it needs to specify the entire result. Reducing the number of operations should lead to improved performance.

My current approach is to iterate the combinations and subset the vector with each and reduce it via logical &. But this is very wasteful as for 012 I recompute the result of 01... There must be a better algorithm but I am having no success.

You can do this without computing the logical AND's at all: you can enumerate all subsets that consist entirely of "true" and enumerate all subsets that contain at least 1 "false".

First, enumerate all subsets of length $k$ with all "true".

Then, enumerate all subsets of length $k$ that contain the first occurrence of "false" in the vector.

Then, enumerate all subsets of length $k$ that contain the second occurrence of "false" but not the first.

Etc...


Give a Context Free Language, is the complement of this language always recursive(REC)? I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I cannot wrap my head around this argument.

What I know about a CFL(say L) is that the complement of this CFL(say L') need not necessarily be a CFL. This creates fair bit of skepticism about nature of such a complement in my head and makes me feel that there is a possibility this complement L' could fly off anywhere in Chomsky Hierarchy as long as it is not a CFL. Why would it be restricted to REC?

In my head, I find myself coming up with arguments like following:
"Every CFL is in RE and complement of an RE need not necessarily be RE and thus need not necessarily be REC! Thus there could be CFLs whose complements are not in REC.
"
or
"Complement of a CFL may fall under RE and there are RE languages which are NOT REC. Thus there is a possibility that a certain complement may not be in REC"

Thread like : What is complement of Context-free languages?
did not answer my question.

We have $\text{CFL} \subset \text{R} \subset \text{RE}$. As you have mentioned, $\text{RE}$ is not closed under complementation, but $\text{R}$ is. Hence, the complement of a CFL is also in $\text{R}$ (though not necessarily another CFL).


NTM's and the halting problem It is often stated that nondeterministic Turing machines cannot recognize any more languages than ordinary Turing machines. In particular, it is stated that there is no NTM that can take as input a DTM/input string and state whether that DTM will halt.

Is this proven, or is this an assumption under the same banner as the Church-Turing thesis?

If it is proven, does anyone have any citations for this in the literature?

A nondeterministic Turing machine can be simulated using a deterministic Turing machine in exponential time (can be shown as a simple exercise). Furthermore, NDTM is a generalization of DTM. So, the computability powers of NDTMs and DTM are equal, in sense of decidability. So, the Halting problem is not decidable by a NDTM. However, their time complexity is different.


Does this classify as Information retrieval? I’m trying to figure out if what I’m doing would classify as Information Retrieval. According to this Thread:

  Information retrieval is based on a query - you specify what information you need and it is returned in human understandable form.

I’ve a script that reads unstructured text (titles of books) and extracts names (which I gathered in a list beforehand) from the titles and outputs a CSV with all matched names. Would that be a simple use case of Information Retrieval or is this called „tagging“? If both not, what would one call this technique?

Thanks for your help!

You could consider that a form of information retrieval, if you want.  It sounds like keyword matching, so not one of the more sophisticated forms of information retrieval, but sometimes the simplest solutions are the best.

I wouldn't worry too much about the name.  There's no strict, hard-and-fast definition of exactly what counts and what doesn't.  The term serves as an aid for communication, and to my way of thinking, it sounds fine to consider what you are doing as a form of information retrieval.


Recursive function calculating number of ways to sum $a + 2 b + 3 c = x$ Using python need to code a recursive function with one input and no global integers that calculates the number of options to get $x$ using $a*1+b*2+c*3$.

Say $x=3$, there are four options: $\lbrace (1,1,1),(1,2),(2,1),(3)\rbrace$.

Recursion is a pretty bad choice here, but here is the recursion you could use:
$$
f(n) = \begin{cases} 0, & n < 0, \\ 1, & n = 0, \\ f(n-1) + f(n-2) + f(n-3), & n > 0.\end{cases}
$$
For example,
$$
\begin{align*}
f(-2) &= 0, \\
f(-1) &= 0, \\
f(0) &= 1, \\
f(1) &= f(0) + f(-1) + f(-2) = 1, \\
f(2) &= f(1) + f(0) + f(-1) = 2, \\
f(3) &= f(2) + f(1) + f(0) = 4.
\end{align*}
$$
The dynamic programming approach implied by this example is a much better idea; it can be implemented in constant space and linear time, whereas the recursion will take linear space and exponential time. You could also use matrix powering to compute $f$:
$$
f(n) =
\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}
\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}^n
\begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}.
$$
The generating function is
$$
\sum_{n=0}^\infty f(n) x^n = \frac{1}{1-x-x^2-x^3}.
$$
Finally, you can also find an explicit solution:
$$
\begin{align*}
f(n) &= \mathrm{round}(Cx^n), \\
C &= \frac{1}{3} + \frac{\sqrt[3]{847+33\sqrt{33}}}{66} + \frac{4}{3\sqrt[3]{847+33\sqrt{33}}}, \\
x &=
\frac{1 + \sqrt[3]{19-3\sqrt{33}} + \sqrt[3]{19+3\sqrt{33}}}{3}.
\end{align*}
$$
This explicit solution isn't very helpful since you need a lot of precision, but it does give you the correct asymptotics; note $C \approx 0.6184199223$ and $x \approx 1.839286756$.


Show that $0^i$ where $i$ is a power of 2 is not context free I'm having difficulty trying to use the pumping lemma in order to show that $L= \{0^i \mid \ i \text{ is a power of 2 }\} $ is not context free.

I"m starting by stating that $ s = 0^p$ and then $ s = uvxyz $ and that in order for a language to be context free it must follow the 3 conditions: $|vy| > 0$ , $|vxy|\le p$ and for some $m \ge 0, \, uv^mxy^mz \in L$.

So I guess I"m struggling on how pumping something $uv^mxy^mz$ will not be in $L$. Would I try and use something along the lines of pumping down $uv^0xy^0z$ for this to not be in $L$. Any help greatly appreciated!

If you're still confused, here's the proof. Let $p$ be the integer of the Pumping Lemma and consider the string $0^{2^p}$. If $L$ was a CFL, then (since $2^p\ge p$) the PL would apply to $0^{2^p}$ we'd have $0^{2^p}=uvxyz$ with

$|vxy|\le p$
$|vy| > 0$

So if we let $v=0^k, y = 0^j$, we have from (1), $k + j =|vy| \le |vxy| \le p$ and from (2), $k + j=|vy|>0$. In other words,

  $0<k+j\le p$

Now pump up: The PL assures us that $uv^2xy^2z\in L$, and observe
$$
|uv^2xy^2z| = 2^p+(k+j)\le 2^p+p< 2^p+2^p=2^{p+1}
$$
as long as $p>0$, so the pumped string $uv^2xy^2z$ has length strictly between $2^p$ and $2^{p+1}$. No such string can be in $L$, so we have a contradiction to the PL implication that $uv^2xy^2z\in L$ and so our initial assumption, that $L$ was a CFL, must be false.

You could shorten this proof if you knew that (1) any context-free language over a 1-symbol alphabet must be regular and (2) the language $L=\{0^{2^n}\mid n\ge 0\}$ is not regular.


(Un)computability of a restricted Halting Problem Before I start with my question, I want to state some notation I am using. I fix some arbitrary but fixed enumeration of Turing Machines (TMs) and denote with $\Phi_i : \mathbb{N}\to\mathbb{N}$ the function that is computed by the $i^\text{th}$ TM in this enumeration. Furthermore $\Phi_i(x) \downarrow$ denotes that the computation of $\Phi_i(x)$ terminates with some result $y$, i.e., $\Phi_i(x) = y$. Furthermore, $\Phi_i(x) \uparrow$ denotes that the computation of $\Phi_i(x)$ never terminates.
I know that the following function is not computable:
$$
f(x) = \begin{cases}
1 & \text{if } \Phi_x(x)\downarrow \\
0 & \text{otherwise}
\end{cases}
$$
Now, suppose we fix some $n \in \mathbb{N}$ and define:
$$
h(x) = \begin{cases}
1 & \text{if } \Phi_x(x)\downarrow \text{ and } x \le n\\
0 & \text{otherwise}
\end{cases}
$$
I found some lecture notes which state that $h$ is computable because it is the characteristic function of a recursive set (because it is finite) and is therefore computable. Is this claim correct?
If $h$ is actually computable I can't think of an algorithm because one simply can't decide if $\Phi_x(x)$ diverges to return $0$ in the case that $x \le n$.

Fix a value of $n$. For $b \in \{0,1\}^n$, consider the following algorithm $A_b$:

If $x \leq n$ then output $b_x$, otherwise output $0$.

Clearly one of the $2^n$ algorithms of the form $A_b$ computes your function $h$, hence $h$ is computable.


Eliminating $\varepsilon$-productions during elimination of left recursion I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any.

I have the grammar

$\qquad S \to Aa \mid b$
$\qquad A \to Ac \mid Sd \mid \varepsilon$

I can see after removing the epsilon productions the grammer becomes

$\qquad S \to Aa \mid a \mid b$
$\qquad A \to Ac \mid Sd \mid c \mid d$

I'm confused where the $a \mid b$ for $S$ and $c \mid d$ for $A$ come from.
Can someone explain this?

The idea of the algorithm is to first find out which non-terminals can produce $\epsilon$, and then eliminate them in all possible ways.

Finding out which non-terminals produce $\epsilon$. The idea here is to start with the set $X^{(0)}$ of non-terminals which have an $\epsilon$ production. We then construct the set $X^{(1)}$ which includes $X^{(0)}$ and all other non-terminals having productions in $X^{(0)*}$ (that is, have productions in which the right-hand side consists of non-terminals in $X^{(0)}$ only). Continue this way until the process stops. The final set $X$ consists of all non-terminals which could produce $\epsilon$.

For example, in your case $X = X^{(0)} = \{A\}$. If there was a production $S \to A$, then you would have $X^{(0)} = \{A\}$ and $X = X^{(1)} = \{A,S\}$.

Eliminating non-terminals which could produce $\epsilon$. Now we simply take all productions containing non-terminals in $X$, and eliminate these non-terminals in all possible ways. That is, for each production containing terminals in $X$, you add additional productions resulting from deleting some of the non-terminals in $X$, in all possible ways. If you get $\epsilon$ productions this way, you just remove them (unless it's the possibly allowed $S\to\epsilon$).

For example, in your case the affected productions are $S \to Aa$ and $A \to Ac$. Handling the first, you add the production $S \to a$, and handling the second, you add the production $A \to c$.


Algorithm for implementing the modulus "%" operator? How can an efficient modulus operator be implemented?

Here's a naive way of defining A % B:

  given $(a,b) \in \mathbb{Z}$ (represented as int)

  while $a > b$ : $(a,b) \mapsto (a-b,b)$

  return $a$

This could be very slow. E.g. $(a,b) = (10^7, 13)$.  I could be subtracting 13's for a long time.

One more possibility is that % is defined in terms of another infix operator / as well as the int function (here in C and verbatim in Python):

  a % b = a - (b * int(a/b))

This is probably not how Python implements it's modulus operator (as it makes a call to C or Fortran).   The % operator is need to reduce fractions or compute GCD's.

Here are some examples of truncation and division from Wikipedia:

You don’t “implement the modulus operator”. You check wit the standards for your programming language how it is defined, and that’s what you implement. For languages like C, C++, Objective-C, Swift and many others, a % b is defined as a - b * (a/ b). And that’s what you implement.

To be efficient: Most processors have built-in division and multiplication. Many support faster implementation of division if b is known. And at last if you want to know whether a % b = 0, you can do that without calculating a / b exactly which makes it a bit faster.


Where are the address, control and data buses on a computer So have been reading up on data buses, address buses and control buses and I understand what they do, but am confused about where they can physically be found. Some books/sites I have found state that they are inside of the CPU, some state that they transmit data all over the computer. E.g. the control bus can send signals to any other device within the computer, but then another book states that the control bus is inside of the CPU and synchronises the components of the CPU.

Can anyone help clarify this please?

The answer is "all of the above".

There are busses all over the system, some are going to be physically internal to a CPU, others might be be between CPU and memory, but not I/O, still others might connect I/O devices (EX: The PCI bus) and others may connect all 3.

Consider what a "bus" is.  I would define a bus as a group of related signals that are intended for a specific purpose.  Busses usually have additional qualifiers to help identify what their purpose is and define what they actually connect with.  IE: A Memory Data Bus would probably connect the data lines of a cache controller on a CPU with main memory.  A Memory Address bus would probably connect the address lines.  A Memory Control bus would carry control signals that signal the state of the other buses and/or provide clocks.  Often these 3 functions are grouped together to define a single "bus".  Sometimes the physical connections on busses are multipurpose where they are used alternately to carry memory or address information.

There are usually bus adapters that allow information to be passed between different busses in a system.  These will sometimes be named something like "bridge", "bus adapter", "gateway", "Hose interface", etc.   These bus adapters allow a system to pass data between busses with different data widths, clock speeds and signaling characteristics.  For example a PCI bridge would connect a PCI bus to a system bus that operates at a higher frequency and may transfer data in larger (or smaller) chunks.


Are all terms of type forall a. a operationally bottom? Is there a proof that all terms of type $\forall{a}. a$ are operationally $\bot$, in a non-weakly-normalising version of System F?

If you ask a free theorem calculator such as this one for the free theorem of $\forall{a}. a$ (written just $a$, as the tool adds implicit $\forall$s for each free type variable), you get the rather unhelpful

forall t1,t2 in TYPES, R in REL(t1,t2). (f_{t1}, f_{t2}) in R

Which seems to me only to imply that instantiations of $f$ at any two types are related by any relation.

Does this imply that $f$ must be a looping term?

Sure, just take R to be $\{(\bot,\bot)\}$, the relation which only relates bottoms.

This is a strict continuous relation, so it satisfies the requirements of the free theorem you linked to.


Generate a random magic square on a large field If consecutive natural numbers 1 .. n^2 are placed in a n*n grid so that sum of numbers in each column and in each row is a constant then we call it a magic square.
I would like to generate magic squares of size 16x16 and 256x256 for not skewed byte mapping. Maps arranged as magic squares tend to have better distribution properties. Algo should produce a map that depends on the seed, rather than yield the same result each time.

expectedSum = ((1+n*n)*n)/2). I can shuffle an array using some form of SecureRandom that accepts a seed. Then in case of a small square I can go for a brute force for loop.I can just brute force 3x3 magic square. Considering symmetries I need to check less than 8*(7!) or about 40k possibilities.

This approach wouldn't work for 16x16 board because 256! > 10^500 is quite large. My best guess is to find two row_column pairs such that sums along row and column are greater than the expected sum  in first pair and lower in second pair. If shared element in first pair is greater than in the second pair - swap elements.  This algo seems better than bruteforce (can complete in reasonable time), but there is no guarantee that it halts. Consider 2x2 square to see how it fails.

What is a good Monte-Carlo approach to solve a large magic square?

Here's a decent algorithm that will quickly generate large magic squares.

First Step: Establish Rows
1. Put all numbers in a bucket.
2. Loop through the rows, 0 to n.
3. Take out n (where n is the size of row) numbers randomly from the bucket.
4. Sum those numbers. If they don't equal the solution sum, goto 3.
5. If they do equal the solution sum, stick them into your grid at the row you are on, remove the numbers used from the bucket, and goto 2.

You'll now -- very quickly -- have a square with each row having the correct sum.

Second Step: Establish Columns
1. Loop through the columns, 0 to n.
2. Shuffle the elements in each row from the beginning of the row + the column you are on, to the end of the row. (That is, if we are working on the first column, shuffle all the elements in each row. If we are working on the second column, shuffle all the elements but those in the first column, etc.)
3. Sum the column. If it doesn't equal solution sum, goto 2.
4. Goto 1 and proceed to the next column.

Now, in this step, you'll need a bail counter... that is, after 1000 tries or so, give up and return to the First Step. The number of attempts needs to increase as n increases... For a 25x25 grid, for example, let it try 100,000 times or so before giving up and creating a new set of rows.

Third Step: Establishing Diagonals
1. Swap any two rows and swap any two columns.
2. Check diagonals sums.
3. If the sum equals solution sum, you're finished. If not, go to 1.

Once again, stick in a bail counter... after 10,000 tries or so, go back to First Step.