Does this A-Star heuristic already exist? I've been thinking about the A* algorithm recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's based on a distance-estimating heuristic you provide to it. The heuristic you provide must be able to tell the program, for any given position: 'This position is at least this far away from the destination'. The most simple heuristic being to use Pythagoras's theorem to get the distance "as the crow flies" between said point and a destination.

Now, the thing that interested me is that A* efficiency is tied to the preciseness of your 'getMinDistance' function. If it returns a value too low, the algorithm takes longer. If it returns a value too high, A* may return a non-optimal path. If it always returns 0, you have Dijkstra's algorithm. (also the heuristic must be monotonic, read the wikipedia articles for more details)

The heuristic I thought about goes like this:

Using any method of your choosing, split the graph into regions. Designate a node of each region as the region's center (ideally, its centroid). The graph traversal distance between any node and its region's center should be trivially computable (or cached).
Store the exact graph traversal distance between the centers of every single region. If you have N regions, you should end up with N² distances.
For any two points A and B, and their respective region's centers Ra and Rb, the graph traversal distance AB is superior or equal to RaRb - (RaA+RbB)

The smaller the regions are, the closer this heuristic gets to the actual traversal distance AB.

My questions are:

Is this algorithm actually admissible? I have no idea how to formally prove it.
How efficient is this heuristic? My guess would be "Very if you have a lot of small groups, because A* only examines nodes within the groups that include the optimal path", but again, I'm not sure it's true and I don't know how to prove it.
Was this idea ever published before? If so, what is it called and where can I read about it?
In the same vein, are there video games which are known to use this heuristic?

This idea is called True Distance Heuristics and as you suspected, it can be very efficient.
True Distance Heuristics
True Distance Heuristics (as well as "Pattern Database") is a technique that utilizes the memory to help with the search. The general idea is "let us pre-compute a few important accurate distances, to save a lot of time during the search".
This is also sometimes referred to as "Memory Based Heuristics".
Each technique has different memory requirements and require a different heuristic function (that, of course, may utilize the original heuristic function).  Also, some of course might be more beneficial in specific domains.
Differential
This technique suggests to choose k "pivot" states and store the shortest path from every state to each pivot
Canonical
This consists of 2 different data-sets:
Primary data: choose k pivot states and calculate all pairs shortest path among all of these k states.
Secondary data: From every node (out of all possible nodes), store distance to the closest canonical node.
Others
There are many other memory based techniques that uses this concept. Many prove themselves to be very beneficial, for a relatively small price to pay (in terms of space).
Food For Thought
As you suspected, these techniques can have admissible heuristics. Since it seems that you are interested in this field, I'll let you figure out the right heuristic functions on your on. I'll give you a hint that the formal proof uses simple math. Feel free to ask for these functions in the comments, and I'll answer.
I strongly suggest to draw these out in a simple drawing, it will make everything very clear.


Enumerate probabilistic and other kinds of Turing machines together When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones? So if we want to enumerate nondeterministic or probabilistic TM's, do we need a separate enumeration?

I can see how we could describe probabilistic TM's as strings, just as we describe the deterministic TM's only now we have two transition functions. Then it also follows that checking whether some string enumerates a probabilistic TM is decidable. Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's? Perhaps the first ... digits of the enumeration describe what kind of TM (probabilistic, determinstic etc) it is and then follows the description of the TM in the standard fashion. So then we can enumerate all the TM's?

A related question, does a TM know it's own description? Or can we give it that information without loss of generality?

When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones?

We mean an enumeration of whatever kind of Turing machines we're talking about at the moment. Unless stated otherwise, "Turing machine" is normally taken to mean deterministic Turing machine.

  Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's?

There's no fixed list of "all different kinds of TM's", so I don't see how this would be possible.

  A related question, does a TM know it's own description?

It's not clear to me what it means for a TM to "know" anything.  A Turing machine is just its state set, transition function and so on.


Why models of computation are primarily focused on machines? It seems a lot of courses (like this and this) on theory/models of computation (and even formal languages) cover DFA, NDFA, PDA, and TM in the order of increasing computational power. This of course makes sense, but why aren't various other computation models included in general? For example, we could take the route from untyped lambda calculus to simply typed lambda calculus and so on with decreasing expressiveness. (I know they are detailed in PLT, but aren't they models of computation as well?)

In brief, since all the above (and a lot more) count as different models of computation with different powers, is there any specific reason, historical or else, that the machine-like models are adopted, sometimes even exclusively?

I suspect that there are two reasons:

Historical reasons. This is how we've always done it.  Academia can be slow to change.  Also, machines provide a platform for studying concepts like the power of non-determinism.  We don't know how to fully understand the power of non-determinism when considering realistic models of computation (for instance, we haven't resolved the P vs NP question), but when we look at more limited models of computation, it's possible to fully work out the power of nondeterminism.  So, this gives us a platform for understanding some interesting concepts about computation.
Pragmatic reasons. DFAs, NDFAs, and PDAs are useful and important to understand if you want to build a lexer or parser, so they're very useful when building compilers.  A few decades ago, this was a powerful motivation for studying the subject: here is a practical need (how do we structure the front-end of a compiler?) and one where there is some beautiful theory that is directly applicable.  Thus, such a course might gain support both from theoreticians who are most interested in the theory, and from compilers folks who are motivated by practical concerns.  It's not clear that this is still the most important thing for students to learn these days -- today, how many students are ever going to need to write a lexer or parser for a compiler? -- but academic courses are slow to change.

I'm not trying to argue this is the only reasonable way to do it.  A course on variants of the lambda calculus might be quite interesting, too.  But I suspect these factors might partly explain why such courses are common.


Linear programming restricted to rational coefficients I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function and conditions to be rational numbers. I guess that this restriction is because of time analysis consideration in terms of input length. Am I correct? Are there other reasons?

EDIT: And do we know that if there is a solution to the LP, then there is a rational solution to it?

EDIT 2: If the answer to the previous question is yes, is there a guarantee for the length of resulting rational numbers to be polynomially bounded as a function of input size?

In order to consider the computational complexity of linear programming, we need a way of encoding an instance of linear programming as a string. In particular, we need to fix an encoding of the coefficients, noting that arbitrary real coefficients cannot be encoded in a finite manner. The simplest and most canonical possibility is to ask for all coefficients to be integers or, equivalently, rational. In practice this encoding is usually good enough, so there is no reason to look any further. In principle, however, it is perfectly possible to consider more complicated coefficients. Indeed, any field which supports efficient linear algebra would do.

A feasible linear program always has a basic feasible solution, which is obtained by taking $n$ linearly independent inequalities (where $n$ is the number of variables), and replacing them with equations. The solution of this linear system will always be rational, and furthermore will be polynomially bounded.

Later on you might learn about semidefinite programs (SDPs). In the case of SDPs, we are no longer guaranteed that there exist an optimal solution over the rationals, but there is always an algebraic solution with bounded algebraic degree over the rationals. This fine point has recently been a cause for worry, see Ryan O'Donnell's SOS is not obviously automatizable, even approximately.


What is a trivial language? I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?

A trivial language is one that has no strings, or one that has every string in some alphabet.

In terms of models of computation, a trivial language is one that can be decided by a Turing Machine or lambda function that completely ignores its input.


Word- or byte-addressable? Correct terminology Seemingly, a byte has established itself to be 8bit (is that correct?). RAM and NOR-flash can be normally accessed on a quite granular level, but it is up to the system architecture to determine if the smallest addressable unit is 8bit, 16bit or any other power of two bit number. Would the correct terminology be to call this word-addressable? Or asked differently, is a word the size of smallest addressable unit? Or is there some other term to describe this?

Are mabye nibble, byte, word, double word all variable in bit-length and only defined by the architecture? And it is therefore only coincidence that a byte is always 8 bit? E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

Main question: What is the precise term for the smallest addressable memory block?

Side question: What is the antonym to this word I'm looking for (e.g. used in NAND-flash)? Page-addressable, block-addressable? Are both correct or is one inprecise?

From a computer architecture point of view, and with the caveat that nomenclature sometimes varies, especially when there is a family of related architectures which has evolved for a long time, or when the marketing department decides to that the usual terms have to used in another way (either to put the product in better light by using a bigger number, or to have a simple number to differentiate more or less related products).

A word has the size normally used for integer operations (often expressed as size of the integer or the general purpose registers, i.e. not address or data, internal or external buses, not address registers, not index registers).  A common issue is that when an architecture is an evolution of a previous one, one often keep the term word for the initial size and one use "double word" or "quad word" for what is a word if you look at the architecture in isolation.  Historically words have not always been a power of two (I know of sizes: 12, 16, 18, 24, 32, 36, 60, 64 and I don't think my knowledge is exhaustive).

Word addressable means that the memory is considered as arrays of words, and thus no smaller unit has an individual addresses.

A byte has various definitions.  The term was introduced to mean the unit used in character encoding at a time where multi-byte encoding didn't exist.  It is often used to means the smallest addressable unit for machine which are not word addressable (well as long at it is not one bit). I don't think those two definitions have ever given a different size. (nor a size different from 6 or 8 bits). For word addressable machine it often means some unit smaller than a word that the machine has some support for (for instance the PDP-10 -- a 36 bits word addressable computer -- had byte instructions which could manipulate any size from 1 to 35 or 36 bits).  Nowadays it is also often 8 bits.  Often several of those definitions are practically equivalent.

Byte addressable characterizes machines where the memory is considered as arrays of bytes in one of the above meaning.

AFAIK nibble has only been used for 4 bits quantities.

  E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

Yes, but I'm not sure if it would make much sense to do so if one keeps the CA usage to use byte for something smaller than the word.  Having a word addressable 16-bit processor with no support for something smaller than a word may be a good choice for a special purpose processor.

  Secondarily, what is the antonym to this word I'm looking for? Page-addressable, block-addressable?

Bit-addressable, byte-addressable and word-addressable are the only terms I've seen use.  It doesn't make much sense to address only units bigger than the word at the architectural level.  Word-addressable is nowadays only used for special purpose processors such as DSP.  I don't think bit-addressability has been used for anything else than special purpose one excepted the IBM Stretch.

About your new main question

  What is the precise term for the smallest addressable memory block?

I know of none used in Computer Architecture (byte has been used for something smaller in word adressable machines), but is the definition used by C for byte.


Proving $(a + ab)^*a = a(a + ba)^*$ Need to prove $(a + ab)^*a = a(a + ba)^*$ by using regular algebra.
Concatenation does not commute. So repeated use of commutativity will fail. I am getting confused about which identity I should use to prove this. What I can interpret is that I just need to change the side of $a$ but the $^*$ must be kept outside. But I am not able to do this.
Any help will be appreciated.

This is an instance of the identity $(xy)^*x = x(yx)^*$ with $x = a$ and $y = 1 + b$:
$$
(a + ab)^* a = (a(1+b))^*a = a((1+b)a)^* = a(a +ba)^*
$$


How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step Consider the following matrix:

Input:
The entire list of coordinates ranging from (0,0) to (4,4).

A list indicating certain coordinates which cannot be used to generate a path reached.

So,

each position on the grid is a node
nodes share an edge if exactly one coordinate differs by exactly 1
X nodes (and their associated edges) are deleted

The problem then becomes, find the shortest path in the graph between two nodes. If the nodes are not in the same connected component, there is no such path.

Output:
The shortest path between S and E, considering the positions of the X nodes, given by a sequence of coordinates.

So in the above picture, a possible route may be the following:
(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)->(4,3)->(4,4)

A total of eight steps.

If the Xs occur in a way that prevents any movement (i.e, Xs at (0,1),(1,1), and (1,0), it should return -1 or indicate in some other way no path is possible.)

I have received advice that the A* search algorithm (pseudocode in this link) is relevant to this problem, but I am having difficulty seeing how to apply it.

You're asking how to compute the shortest path between two vertices in a graph.  Solution: use an algorithm for computing shortest paths.  In your case, BFS would be a good choice.  There's no need for A*.


Efficient cardinality of set overlap relation Assume that we have a set S of sets s.
Every pair (s,s') in SxS can be overlapping or not.
How can we efficiently compute the number of pairs (s,s') that are overlapping, i.e. that share at least one element?
Additional: actually each set s occurs a number of times (S is a multiset). I have tried to create a matrix M of scipy.sparse.csr_matrix that stores the subset partial order over S. Then I have tried to add the additional edges for overlaps through M.T.dot(M) to then later compute f.dot(M).dot(f.T), where f gives the frequency for each s. Unfortunately M.T.dot(M) becomes too large, so if anything, we probably have to propagate the counts through the subset partial order one after the other.
Hints: it might seem apparent at first to just take the sum over the union of all elements in all s of their frequency squared to sum up the number of pairs sharing one particular element. However the problem is that this counts many pairs multiple times. For example {a,b} is counted for a and also for b. This is why it seems important to use the subset partial order.
Any ideas?

Consider the following problem. We are given $n$ sets $S_1,\ldots,S_n \subseteq \{1,\ldots,\log n\}$, and have to decide whether there are two disjoint sets among them. This problem is known as Orthogonal Vectors (OV), and it is conjectured that it cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon>0$ (on a RAM machine). See for example Chen and Williams, An Equivalence Class for Orthogonal Vectors.


Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$.

  Find an algorithm that sorts the input in $O(n\log (\frac n k ))$ runtime.
  Find a lower bound for the minimal amount of comparisons in the worst case.

is pretty simple I think:

for each S_i
   mergesort(S_i[n/k])

But with 2. I get results that can't be right: in the worst case there would have to be at least $(\frac n k )!$ comparisons for each $S_i$ because the algorithm will have to pass each combination at least once, also, this is the amount of leaves at the lowest level of the decision tree.

This gives: $T_{worst}(n) = \Omega (k(\frac n k )!)$ which is a lot larger than $O(n\log (\frac n k ))$. So what am I doing wrong here?

If a decision tree has at least $m$ leaves then its height is at least $\log_2 m$. It is the height that bounds the number of comparisons rather than the number of leaves. In your case there are $(n/k)!^k$ leaves, and so $\Omega(\log[(n/k)!^k]) = \Omega(n\log(n/k))$ comparisons.


Is Mersenne primality testing necessarily EXPTIME? The computational complexity of primality testing is usually specified in relation to the bit length of the number being tested.

However, Mersenne numbers have the special property that the characterizing instance exponent $p$ is exponentially more succinct than the number it signifies. Surprisingly, most of the literature I've found appears to assume a unary representation of $p$ rather than binary.

The Great Internet Mersenne Prime Search, for example, aims to identify very large Mersene primes via an optimized distributed Lucas–Lehmer primality test. GIMPS as a virtual computer has at times ranked among the TOP500 in terms of expended computational capacity.

So is all this distributed computing truly necessary? Do we really need to expand $p$ to its verbose representation to verify its primality?

Or is there still a possibility that primality testing for Mersenne numbers could be decidable in polynomial time in the size of the instance $p$ via some clever certificate tree?

Nothing is impossible. But the problem is that you might want to check whether a 10 million digit number is a prime, but that number is just 2 raised to an 8 digit power, minus 1, so the problem size would be just 8.

For random 10 million digit numbers, the problem size is 10 million. For 10 million digit Mersenne numbers, the problem size is just 8. You can't even write down that number in polynomial time in the problem size. You can't even write it in base 2 in polynomial time, where the number is just a huge string of 1's.


Counting inversion pairs A classic application of divide and conquer is to solve the following problem:

Given an array $a[1\dots n]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(i,j)$ such that $a[i] \gt a[j]$ and $i \lt j$.

One approach to this is to do a Merge Sort, but also counting of the number of inversion pairs in the sub-problems. During the merge step, we count the number of inversion pairs that span across the (two) sub-problems and add to the counts of the sub-problems.

While this is good, and gives an $O(n\log n)$ time algorithm, this messes up array.

If we have the additional constraint that the array is read-only, then we can make a copy and deal with the copy, or use an additional data-structure like an order statistics balanced binary tree to do the counting, both of which use $\Theta(n)$ space.

The current question is to try and better the space, while not affecting the run time. i.e.

  Is there an $O(n\log n)$ time algorithm to count the number of
  inversion pairs, which works on a read-only array and uses sub-linear
  (i.e. $o(n)$) space?

Assume a uniform cost RAM model and that the elements take $O(1)$ space and comparison between them is $O(1)$.

A reference will do, but an explanation will be better :-)

I tried searching the web, but could not find any positive/negative answer for this. I suppose this is just a curiosity.

Here is Raphael's answer:

Chan and Pătraşcu give an $o(n\log n)$ time algorithm, but as far as I can tell from skimming the paper, they need $\Omega(n)$ space. Furthermore, Ajtai et al. prove that any (exact) $O(n)$ time streaming algorithm needs $\Omega(n)$ space. There seem to be approximations fitting your criteria, though.


Confusion in "mask bits" This is the question:

  By definition of the IEEE754 standard, 32-bit floating point numbers
  are represented as  follows:

  S (1 bit)  E (8 bits)  M (23 bits)  S: Sign bit  E: Exponent  M:
  Mantissa

  Which of the following is the correct “mask bits” in hexadecimal to be
  used for  extracting only the exponent part of the above format?
  Here, “mask bits” means a bit  pattern which is logically ANDed
  withthe 32-bit floating point value.

  a) 107FFFFF  b)  7F800000  c)  FF100000  d) FF800000

The given answer is b : 7F800000, but i have no idea why, can anyone give me an explanation, i'm greatly appreciated!

Is that because :

7F800000 = 0111 1111 1000 (8)

While others answer contain more "1" in binary format?

When you bitwise AND a number in this format with 7F800000 you get:

    SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM
AND 01111111100000000000000000000000

  = 0EEEEEEEE00000000000000000000000

Everything gets set to 0 except the exponent. Yes, it is necessary for the correct answer to have 8 ones, but it is also necessary that they are in the correct positions. 00007F80 would not be correct because it would result in:

    SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM
AND 00000000000000000111111110000000

  = 00000000000000000MMMMMMMM0000000


Right equivalent elements arising in the proof of the Schützenberger Theorem As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in line 11, namely in the equation: $$" \gamma ( f x ) M ( = mM = mM \cdot M)"$$
But I will break this down in my own words to make this understandable (hopefully).

Let $M$ be an aperiodic monoid, $\Sigma$ a finite alphabet and $\gamma : \Sigma^* \to M$ a surjective monoid-homomorphism. Fix an element of $m \in M$, whose generated right ideal satisfies $m M \neq MmM$ and $mM \neq M$.
With these define the language $L = \gamma^{-1}(mM)$ and $\hat{L} = L \setminus (L\Sigma^+)$ (one can prove that $\hat{L}$ is the smallest set satisfying $L = \hat{L}\Sigma^*$) and $M'' = \{m'\in M \mid \gamma^{-1}(m')\Sigma \cap \hat{L} \neq \varnothing\}$.
For a fixed $m' \in M''$ one can find a $w \in \gamma^{-1}(\{m'\})$ and a $\sigma \in \Sigma$, such that $w \sigma \in \hat{L}$.
Now one has to show, that $mM = \gamma(w \sigma) M$.

Well in my opinion $\gamma(w \sigma)M \subseteq mM$ is rather easy, because $w\sigma \in \hat{L} \subseteq L$, therefore $\gamma(w\sigma) \in mM$, which implies ($M \cdot M = M$) this direction.

But I have trouble proving the opposite direction. I gladly appreciate every hint you give me, because I seem to have some kind of blockade in thinking about this. My guess is that the special property of $\hat{L}$ (above in parentheses) is somehow involved.

Reference:
$^{[1]}$ M.P. Schützenberger. On finite Monoids having only trivial subgroups. Inform. and Computation, 8:190-194, 1965.
A copy can be obtained here: Schützenberger Theorem

As suggested by J.-E. Pin in the comments, this claim is wrong in the general case. To prove this statement a counter-example shall be constructed, but this will be done by a Haskell-program (at the bottom of this answer). But first I want to explain what it should do.
The program looks onto a special kind of maps that map Maybe [-2,-1,0,1,-2] to itself. It suffices to look at maps that only go from [-2,...,2] to Maybe [-2,...,2]. The set of maps that this program looks at is even more limited, because it shall only be those maps, that can be generated by a and b only. The function calculateAll should calculate the all the elements in the monoid generated by these two functions and the identity (this is a rather large monoid with 56 Elements). isAperiodic does what the name suggests, but it does not fail, therefore it is unsafe. Next this program can calculate all the "interesting" candidates, that are those elements of the monoid, whose principal right ideal does not equal the whole monoid and not the principal two-sided ideal. This is done by getCandidates. Then testForOneCandidate generates all the counterexamples for the claim for a fixed element $m$, where only completion with the letter $a$ is considered. This is done as follows:
An element in $m''$, which does not lie in $mM$, but $m''\ast a  \in mM$, is in $M''$. For such an element one only needs to test if $m'' M \neq  mM$. This is what testForOneCandidate does. Retranslating the first result of the call testForOneCandidate (head getCandidates) into potencies of a and b one gets the following in ghci testable counter-example (after loading the code):

*Main> let ba = b `mappend` a
*Main> ba `elem` rightPrincipalIdeal a
False
*Main> let ba2 = ba `mappend` a
*Main> ba2 `elem` rightPrincipalIdeal a
True
*Main> (fromList $ rightPrincipalIdeal ba2) < (fromList
    $ rightPrincipalIdeal a)
True

That is a rather complicated example, but I'm sure that there are simpler ones, it's just the first that I encountered.

Here is the code:

import Data.List (nub,(\\))
import Data.Set (fromList)

data Element = Element (Int -> Maybe Int)

instance Show Element where
  show (Element f) = show (map f [-2..2])

instance Eq Element where
  (==) (Element f) (Element g) = (map f [-2..2]) == (map g [-2..2])

instance Ord Element where
  (<=) (Element f) (Element g) = (map f [-2..2]) <= (map g [-2..2])

instance Monoid Element where
  mempty = Element dropOutside
  mappend (Element f) (Element g) = Element $ \i -> ((f i) >>= g)

-- Helper function
dropOutside :: Int -> Maybe Int
dropOutside i
  | abs (i) <= 2 = Just i
  | otherwise = Nothing

-- First elements that "generate" the monoid
a :: Element
a = Element $ \i -> dropOutside (i+1)

b :: Element
b = Element $ \i -> dropOutside (i-1)

nullElement :: Element
nullElement = Element $ \_ -> Nothing

-- Generates the monoid by the neutral element, a and b.
calculateAll :: [Element]
calculateAll =
  let
      calculateAllRec :: [Element] -> [Element]
      calculateAllRec acc =
          let
              newEs = nub [z| x <- acc, y <- acc,let z = x `mappend` y,z `notElem` acc]
          in case newEs of
               [] -> acc
               _ -> calculateAllRec (acc ++ newEs)
in calculateAllRec [mempty,a,b]

-- Checks whether a given element is aperiodic. (Unsafe)
isAperiodicElement :: Element -> Bool
isAperiodicElement x = isApElRec x x where
  isApElRec x' y'
      | y' == (x' `mappend` y') = True
      | otherwise = isApElRec x' (x' `mappend` y')

-- Checks if the whole monoid is aperiodic. (Unsafe)
isAperiodic :: Bool
isAperiodic = all isAperiodicElement calculateAll

-- Calculates the right ideal generated by a given element.
rightPrincipalIdeal :: Element -> [Element]
rightPrincipalIdeal x = nub [x `mappend` y | y <- calculateAll]

-- Calculates the twosided ideal generated by a given element.
twoSidedPrincipalIdeal :: Element -> [Element]
twoSidedPrincipalIdeal x = nub [z `mappend` x `mappend` y | z <- calculateAll , y <- calculateAll]

-- Calculates all those elements, that generate a right ideal, which is not
-- equal to the whole monoid and the twosided ideal generated by that same element.
-- Results in all elements besides the neutral and the null element.
getCandidates :: [Element]
getCandidates =
  let
      fLcA = fromList calculateAll
  in [x| x <- calculateAll,
         let z = fromList $ rightPrincipalIdeal x,
         z /= fromList (twoSidedPrincipalIdeal x),
         z /= fLcA]

-- Tests for an element m from getCandidates, if there is an element in M withouth mM
-- that reaches mM by adding an a (which amounts to saying that this element m' is in
-- M''). Therefore m'a is in mM. But also m'aM must not be mM.
testForOneCandidate :: Element -> [Element]
testForOneCandidate m =
  let
     mM = fromList $ rightPrincipalIdeal m
     factorsWithA = [m' | m' <- calculateAll ,
                                m' `notElem` mM,
                                let x = m' `mappend` a,
                                x `elem` mM,
                                fromList (rightPrincipalIdeal x) /= mM ]
  in factorsWithA


how to prove that nlogn is not Θ(n) without using limits? i'm studying an algorithms designing and analysis , and i've question about Big-theta

how can i prove that nlogn is not Θ(n) without using limits ?

Remember that $f \in \Theta(g) \iff f \in O(g) \land g \in O(f)$, so $f \notin \Theta(g) \iff f \notin O(g) \lor g \notin O(f)$.

One definition of big-O notation that doesn't use limits is

$$
f \in O(g) \triangleq \exists c, N, \forall n > N, f(n) < c \cdot g(n)
$$

The negation is logically equivalent to

$$
\lnot (\exists c, N, \forall n,  n > N \implies f(n) < c \cdot g(n))\\
\lnot (\exists c, N, \forall n,  \lnot (n > N) \lor f(n) < c \cdot g(n))\\
\forall c, N, \lnot (\forall n,  \lnot (n > N) \lor f(n) < c \cdot g(n))\\
\forall c, N, \exists n, \lnot (\lnot (n > N) \lor f(n) < c \cdot g(n))\\
\forall c, N, \exists n, \lnot \lnot (n > N) \land \lnot (f(n) < c \cdot g(n))\\
\forall c, N, \exists n > N, \lnot (f(n) < c \cdot g(n))\\
\forall c, N, \exists n > N, f(n) \geq c \cdot g(n)\\
$$

So, to show that $n \log n \notin \Theta(n)$, you'll want to find a witness $n$ that will be based on a $c$ and $N$ that are abstract, and show that $n \log n \geq c \cdot n$.

Here is an example with some other functions:

Claim: $n^2 \notin O(n)$.

Proof:
Given $c$ and $N$ as above, let

$$n \triangleq \begin{cases}
c & N < 1\\
N c & N \geq 1.
\end{cases}$$

In the first case, $n^2 = c^2 \geq c \cdot c = c \cdot n$.

In the second, $n^2 = N^2 c^2 = N (N c^2) \geq N c^2 = c (c N) = c \cdot n$.

I won't do the example with $n \log n$, because I'd like you to see the principle and I don't want to accidentally do you homework.


What does "number of gates" mean in circuit complexity? By "number of gates", I am wondering whether these gates include AND/OR gates that can receive several inputs or they just include AND/OR gates that receive two inputs.

The number of inputs to a gate is an independent restriction or allowance on the circuit. The number of gates in a circuit is simply the number of gates.

Of course you can always measure the two separately. For example the $W$-hierarchy in Parameterized Complexity can be defined in terms of the large-gate depth (called in this context the weft) of families of circuits (i.e. the maximum number of gates with unbounded fan-in on any path from the inputs to the output).

Of course we can also take an unbounded fan-in gate (if we're sticking to AND/OR at least) and replace it with a circuit consisting of a several bounded fan-in gates, but the size may increase significantly.


For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times? Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of each node $|V| - 1$ times.

This puzzles me because I think that a single round of breadth first search is enough. Why must we do $|V| - 1$ of these searches?

Either you mixed up two algorithms or you misinterpreted an upper bound. One level of a BFS with priority queue is enough, but during this one round a neighbor of the root may be updated $|V|-1$ times, therefore the update operation needs to be efficient.


Turing Machines: decidability and bounds checking I am wanting to show that it is decidable that a Turing machine M, on input w, ever attempts to move its head past the right end of the input string w.

I'm assuming I construct a TM which shifts the input on the tape on cell to the left, write the cell at the right-hand end with a new symbol (like "!") that's not in the alphabet for input w.
Then add a transition for the head to move left on e cell on reading the extra symbol?

Thoughts?

I can construct a machine $D$ which on input $\langle M,w\rangle$ tells if $M$ moves its head past the right end on input $w$, $D$ accepts if the head does not move past the right end of input, and rejects otherwise. As configurations of length $|w|$ are finite if $M$ ever enters same configuration of length $ \le |w|$ accept. Or if it does not repeat such configuration at some point $M$'s head will move past $|w|$ tape cells. So yes your problem is decidable.


Are Huffman codes self-synchronizing? A code is (statistically) self-synchronizing if, given that the transmitted string is long enough, the receiver is guaranteed to eventually synchronize with the sender, even if bit flips or slips have occurred.

Do Huffman codes have this property in general? In case not, is there a criterion for testing if a Huffman code is self-synchronizing or, equivalently, is there a modified construction of a Huffman code which guarantees self-synchronization?

Assume 256 symbols, each with probability 1/256. The Huffman code words will be all 256 possible eight-bit sequences, and there is no synchronisation at all.

To find if a Huffman code is self-synchronising:

Let S = {}
For each code c:
    For 1 ≤ m < length (c)
        Let s be the last m bits of c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in S
            Add s to S.

Loop:
    If S is empty the the code is self-synchronising.
    Let T = {}
    For each s' in S, and code c:
        Let s be s' concatenated with c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in T
            Add s to T.
    If T = S then the code is not self-synchronising
    Let S = T and loop.


Find all non-decreasing sequences given lenght and size I'm trying to find a solution for this exercise:

  Give the pseudocode of an algorithm which takes two positive integers
  n and k and prints all the non-decreasing sequences of length k
  (1,2,...,n).

  For example n=4, k=3:

  111 112 113 114 122 123 124 133 134 144 222 223 224 233 234 244 333
  334 344 444

  the complexity must be O(n S(n,k)) with S(n,k) the number of the
  sequences to print for n and k.

i think from the complexity required that a backtracking algorithm it's needed  but i could'nt solve it.

i tried something like this:

P(n,k,h: prefix length, S: sequence)

      if h == k then
           OUTPUT S
      else
         for i=1 to n do
             if(i>=S[h])
                   S[h+1]=i;
                   P(n,k,h+1,S);

Hint. Given the available time complexity, a simple recursive algorithm should work. If you need a sequence of length $k$ from the set $\{m, \dots, n\}$ you either include $m$ or you don't.


Prove that the syntax is equivalent I don't "see" why the following syntax is equivalent to the second

syntax1:

E -> E + T
E -> T

syntax2:

E -> T E'
E' -> + T E'
E' ->

(it is to avoid left recursion and I am not understanding why the solution works)

How do I mathematically prove that both syntax definitions are equivalent

An intuitive approach towards the difference is understanding that the productions of syntax #1 add new material to the left of existing symbols whereas those of syntax #2 do so on the right-hand side.

syntax #1:

derived string of terminals: `  T    + T   + T  ...  + T   + T `
derivation step:             `[ n ] [n-1] [n-2]     [ 2 ] [ 1 ]`

syntax #2 (step #n is the application of rule 3 and produces no terminal) :

derived string of terminals: `  T    + T   + T  ...  + T   + T `
derivation step:             `[ 1 ] [ 2 ] [ 3 ]     [n-2] [n-1]`

for a rigorous proof note that under both syntaxes, each derivation leads to an initial T followed by sequence of  + T. for the grammars at hand this can be proven by induction over the number of rule applications.


Check whether set of strings is prefix-free via lexicographic sort? I have a set of strings and would like to establish whether the set has the prefix property, which basically means that no string in the set is a prefix of any other string in the set. So {a, b} is prefix-free (has the prefix property) while {a, b, ba} is not prefix-free (lacks the prefix property) because the entire string b is a prefix of ba.

One can of course implement this with a double-loop for quadratic performance. In JavaScript (so you can pop open your browser’s JS Console and try it, if so inclined):

function isPrefixCode(strings) {
  for (const i of strings) {
    for (const j of strings) {
      if (j === i) {
        continue;
      }
      if (i.startsWith(j)) {
        return false;
      }
    }
  }
  return true;
}
isPrefixCode(new Set('a b c'.split(' '))) // true
isPrefixCode(new Set('ba b c'.split(' '))) // false

I think one can do better by sorting the set of strings lexicographically ($N \log N$), then comparing each element to its previous one (linear). So:

function isPrefixCodeLinear(strings) {
  strings = Array.from(strings).sort();
  for (const [i, s] of strings.entries()) {
    if (i === 0) {
      continue;
    }
    const prev = strings[i - 1];
    if (s.startsWith(prev)) {
      return false;
    };
  }
  return true;
}
isPrefixCodeLinear(new Set('a b c'.split(' '))) // true
isPrefixCodeLinear(new Set('ba b c'.split(' '))) // false

This linearithmic algorithm seems to work for the tests I’ve come up with (and ~100x speedup over the quadratic double-loop algorithm on a 1000-string example), but I’d like to ask

if this approach based on lexicographic sorting is guaranteed to work,
if this approach has a name, and
if the prefix property has a more common term in computer science, or
if there are other algorithms that can solve it.

(I found this question on StackOverflow, about finding whether any entry in a set of strings is prefixed by a specific given string, How to search whether a string is a prefix of strings stored in a set?, which is a related problem to mine, but here I want to consider not just any one string but all the strings in the set.)

Yes. The common prefix is maximal with the closest predecessor (if you're treating the empty string as less than any other, which you are).  Edit:  in general if a prefix key exists it will be the immediate predecessor or there will be another key in between which shares the same prefix, and your test will fail on that.  eg ABC, ABCD, ABCE will fail on the first pair even though the last key also contains ABC and is non-consecutive.  The LCP is indeed maximal with the closest predecessor neighbor, but that predecessor neighbor may not be a prefix; I just wanted to clarify that.
There are situations where the longest common prefix is useful; in particular to augment a suffix array, which is a sorted list of suffixes.  Look up LCP Array. The LCP+1 (roughly) is called the distinguishing prefix; string sorting algos express their complexity in terms of O(n log n + D), where D is the sum of all the distinguishing prefixes of all the keys.  So it's a familiar idea.
"Prefix free" is the term that I remember.
You can put them in a trie and look for strings that end on an intermediate node.  It's a variant of sorting.


is a deterministic algorithm for breadth-first traversal possible (binary heap) Imagine I have a binary heap, traversed in a breadth first manner like so:

                  0
       1          |           2
  3    |    4     |    5      |     6
7 | 8  |  9 | 10  |  11 | 12  |  13 | 14

To the left of root (0) is 1, to the right is 2, to the left of 1 is 3 to it's right is 4 etc.

So node 13 corresponds to the following pattern (right right, left, (or 0,0,1, perhaps)).

The question is, is there an equation, function, or algorithm that will produce the pattern to get to any node without actually producing the entire tree and traversing it?

Say I didn't create the tree in memory (it's just a virtual tree). How would I know that in order to get to 8 I need to start at root and go: left,left, right (1,1,0)?

Is this computable without creating the tree, and traversing it? If so what is the pattern for 42? is it easily calculable (is it linear) ?

I'm sorry for not knowing all the CS terms (I'm not a cs major, but I want to know if there's a deterministic algorithm to produce a path to any node, if so, whats it's computational efficiency) ?

Binary trees can have different structures. Every node can have at most two children. At most means you might have 2 children, you might have one child or no child. This leads to different structural possibilities for the binary tree.

There is no definite pattern to tell how to find a particular node. Closest you can get to a pattern is when you have a binary heap, but in a heap it is fix that the binary tree will be complete binary tree i.e. all the internal nodes will have two children and the leaf nodes at the last level will be as left as possible. For a heap you can determine the left child as $2*i + 1$ and right child as $2*i+2$ where $i$ is the index of node and $i = 0$ for root node.

In the worst case a binary tree can degenerate to a linked list which means you would have to proceed linearly to find the element you want. So, we can say how will the search of a node proceed totally depends on the structure of the binary tree.

To find a node basically traverse the tree with any of DFS or BFS.


Rational agent question from Russell and Norvig Question from Artificial Intelligenge: A Modern Approach by Russell and Norvig (Exercise 2.1).

  Suppose that the performance measure is concerned with just the first
  $T$ time steps of the environment and ignores everything thereafter.
  Show that a rational agent's action may depend not just on the state
  of the environment but also on the time step it has reached.

This question is extremely confusing to me. My initial thought is that this is obvious. A rational agent wants to maximize its performance, and the first $T$ time steps are a factor in the performance measure. So for instance, if the environment is in state $A$ at time step 1, the performance measure can be different than being in state $A$ at step 2 since the state of the environment in step 1 is relevant to the performance measure in the latter case. Thus as the performance measures can be different, the rational agent may make different actions.

Perhaps that is the answer, but I am still confused on why it matters that the performance measure is concerned with only a finite sequence of initial time steps. My interpretation of the question seems to make that irrelevant. Only the fact that the performance measure has some historical factor is of any concern.

Can anyone help clarify what is happening in this question?

This question is obvious as you told and its purpose is to ensure that the reader has understood a part of the chapter.
You are right that the actions that the agent does will differ in the time period T. They will also differ after this period, because the agent's actions will have no value.

One example may be for a car agent that has to cover as much distance as possible and has limited fuel. If only the distance reached during the first hour counts, the car could take it in full throttle(exhausting the fuel very fast). However if there was no time limit the car agent should choose the optimal speed that maximizes the distance covered per fuel unit spent.


What is the purpose of the SKI combinator calculus(or even lambda calculus)? What are some real life examples of its use? I understand what it is, but I don't see how it is any use for algorithms or anything. Maybe I am missing something. I need someone to give me an example of how it can be used so I can understand it better.

The obvious application of the lambda calculus is any functional programming language (e.g., Lisp, ML, Haskell), and any language that supports anonymous functions.

As for combinator calculus, does there have to be a "real-world application"?  Turing machines, for example, are hardly ever used "in the real world" but they form the basis of the theory of computation.  One useful feature of combinator calculi is that they're simpler systems than, e.g., Turing machines. If you want to prove that some other system is Turing-complete, it might be easier to show how it can simulate combinators than to show it can simulate a Turing machine.


Does the set $\{10^n \mid n\geq1\}^*$ include $10100$? Consider the following set constructed with a regular Kleene-star operation:
$$
\{10^n \mid n\geq1\}^*
$$

Would something like $10100$ be in this set? I know $1010,100100100,1000,$ etc would be, but I'm not sure if you can change $n$ per repetition and have it be something like $10100, 101001010010$, etc.

Short answer: Yes. $10100$ is included.

Long answer:

Let's go through how this particular set is constructed. First, the expression
$$
10^n
$$
(in this context) denotes a single string consisting of a $1$ followed by $n$ $0$s (so the string depends on one variable $n$). Then, the set
$$
\{10^n \mid n \ge 1\}
$$
denotes the set of strings $\{10, 100, 1000, 10000, \ldots\}$. This set can also be denoted using the Kleene-star operation as $100^*$ or $10^+$. Note that this set does not depend on $n$ -- rather, $n$ is just a dummy variable used to describe the elements of the set.

Finally, the set
$$
\{10^n \mid n \ge 1\}^*
$$
then denotes a concatenated sequence of elements of the original set, like $10100$, $1000$, $1010000010$, etc. When you use the $*$ operation, the string used each time does not have to be the same (that is, you can change $n$ for each repetition). So you can do $10$ first, then $100$, then $10$ again, etc.


Complement of $0^n1^n | n \in \mathbb{N}$ I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \{ 0^n 1^n | n \in \mathbb{N}\}$ is $A = \{ 0^i 1^j| i \neq j\} \cup (0 \cup1)^*(1)(0 \cup1)^*0(0 \cup1)^*$, but I don't see how $A^* = \sum^*$. Any help would be appreciated!

Since $0 \in A$ and $1 \in A$, any word $w \in \Sigma^*$ can be written has a concatenation of $n=|w|$ words $w_1, \dots, w_n$ such that each $w_i \in A$ (showing that $w \in A^*$). In order to do so it suffices to pick $w_i$ as the $i$-th character of $w$, i.e., $w_i$ is either $0$ or $1$.


Why is the processor's pipeline delay calculated as N*max(Delay) ? why not N*(D1 + D2 + D3 ... )? Consider a four stage pipeline, and each stage has delays D1, D2, D3 and D4, so the total delay because of the various stages should be N * (D1 + D2 + D3 + D4) where N is the number of instructions, but I see that this is not the case, I see here that the delay is calculated as N*max(D1,D2,D3,D4) , why is only the max value taken into account ?

I try to apply the above two ideas for the below chart and none of them work.

For the below chart consider that the numbers on top are the time and the S1, S2, S3 and S4 denote the time spent any stage of an instruction on the pipeline

with N*(max(S1,S2,S3,S4)) = 4*(4) = 16,
and with N*(S1 + S2 + S3 + S4) = 4*(1+2+4+1) = 32

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
S1 S2 S2 S3 S3 S3 S3 S4
   S1    S2 S2       S3 S3 S3 S3 S4
      S1       S2 S2             S3 S3 S3 S3 S4
         S1          S2 S2                   S3 S3 S3 S3 S4

Each stage of the pipeline is only as fast as the slowest stage. The calculation for the latency expresses this by taking the maximum delay (max(D1, D2, D3, D4)) and multiplying it by N, which is the number of stages. Thus: N*max(D1, D2, D3, D4).

Keep in mind, N is the number of stages, not instructions. The formula measures the latency, not the total run time.

Your chart demonstrates this, as you can see that there is more and more delay building up in the first and second stages as they finish faster than the next stage. But there is a problem: where does the data from each stage go before it enters the next stage? The simple answer is nowhere: it is stuck in the current stage until the next stage is free. Your third stage is creating a traffic jam!

Consider this chart, in which each stage has been slowed down to take 4 time units (the n represents that processing is done but the data must wait for the next stage to clear):

    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
    S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                            S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                                        S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!

Here we can see that it takes each individual instruction 16 time units to make it through the pipeline (4 stages * max delay of 4). The total run time is only 28 time units. It takes 16 units for the first instruction to run, and 4 more time units for each additional instruction. So the run time formula is something like: N*max(D1, D2, D3, D4) + (IC - 1) * max(D1, D2, D3, D4) where N is the number of stages and IC is the number of instructions.


Convergence of recursive formula in TextRank I am reading a paper about the TextRank algorithm in keyword extraction and they mention the recursive formula:
$$ \displaystyle S(V_{i}) = (1 - d) + d \ast \sum_{j \in In(V_{i})} \frac{1}{|Out(V_{j})|} \; S(V_{j})  $$

where $ In(V_{i}) $ are the vertices that point to $ V_{i} $ and $ Out(V_{i}) $ are the vertices that $ V_{i} $ points to.

The paper claimed that this algorithm will converge for any arbitrarily small positive threshold and any arbitrary initial values by testing with experiments. However, I am attempting to prove it mathematically that this algorithm will always converge regardless of the choice of the threshold as well as the initial values, but haven't succeeded at this point. My approach is to prove that if $ E_{ij} $ is the error at vertex $ i $ at the $ j $ iteration, then the sequence $ E_{i1}, E_{i2}, \dots, E_{in} $ is a decreasing sequence. Intuitively, it means that the error rate approaches $ 0. $

Any hint or suggestion is appreciated.

Your process is a Markov chain, so I suggest you try applying the theory of Markov chains. There's a rich and powerful theory that has been built up over time, which might be applicable here.

In particular, if we let $S$ denote the column vector $S = (S(V_1),S(V_2),\dots,S(V_n))$, then there is a matrix $n\times n$ $M$ such that each iteration maps $S$ to $MS$.  If the underlying graph is strongly connected, it looks like this Markov chain is irreducible, ergodic, aperiodic, and all its states are recurrent.  From this you should be able to deduce that it has a stationary distribution $\pi$ and that the stationary distribution is the unique limiting distribution of the chain, hence the algorithm eventually converges.  You should check all of this yourself carefully; I haven't checked any of this.

The rate of convergence will be dependent on the magnitude of the second-largest eigenvalue of the Markov chain.

Look at the analysis of PageRank for a detailed, worked example applying these concepts to a similar algorithm.  This analysis can be found in many textbooks and algorithms courses.


Unary function is partially n-computable Please help me prove the following problem:
A unary function $f(x)$ is said to be partially $n$-computable if it is computed by some $\mathcal{S}$ program $\mathcal{P}$ such that $\mathcal{P}$ has no more than $n$ instructions, every variable in $\mathcal{P}$ is among $X, Y, Z_1, . . . , Z_n$ and every label in $\mathcal{P}$ is among $A_1,...,A_n,E$. Prove that if a unary function $f : N \rightarrow N$ is computed by a program with no more than $n$ instructions, then $f$ is partially $n$-computable.
This problem is in Chapter 2, Section 4 of Computability, Complexity, and Languages by M.Davis.
I am quite confused by this problem because the statement at the beginning and the question that needs to be proved are just two ways of saying the same thing. The statement is "q if p" and the question is "if p then q" which both mean "p implies q". So I totally don't understand what is asked to be proved here.

Well there are trivial two conditions you have to prove.
If $f:N\rightarrow N$ is computable in $n$ instructions, then there exists a corresponding program $P$ that computes it in $n$ instructions. $P$ could assign one new variable in every instruction, thus the program uses $\leq n$ new variables. Furthermore the program only contains $n$ instructions meaning there is one label for every instruction at max, hence the number of labels is $\leq n$. This completes the proof (that $f$ is partially n-computable)


Non-trivial tractable properties of triples Many intractable $NP$-complete problems can be modeled as deciding whether a set of triples, $F=${$t_1, t_2, ..., t_n$} where each triple $t_i$ is a subset of three elements over base set $U=${$a_1, a_2, ..., a_k$}, satisfy some non-trivial property. For example, 3-edge coloring of cubic graphs can be modeled as the problem of deciding whether sets of triples satisfy that the elements in each triple must have different color.

I'm looking for examples of non-trivial tractable properties ($P_2$) of sets of triples (which have polynomial time algorithms) given that the sets of triples already satisfies some other non-trivial property $P_1$. Non-trivial property means that there are infinite number of sets of triples that satisfy the property and infinite number of sets of triples that do not. Are all non-trivial properties $P_2$ of sets of triples intractable?

Also, I'd appreciate a survey on the subject.

EDIT: Based on Ben's answer, I added the requirement that $F$ already satisfies some non-trivial property $P_1$ and we are asking weather it satisfies another no-trivial property $P_2$. For instance, in the 3-edge coloring example, the family of triples $F$ must represent the edges incident on the nodes of a cubic graph.

I think your "non-trivial" property would need to be a property of sets of triples, not of triples themselves; i.e. you need that there are an infinite number of sets of triples that satisfy and do not satisfy the property.

Call a triple consists of 3 identical elements a 3-clone. Checking that a triple is a 3-clone can obviously be done in linear time, and checking that a set of triples are all 3-clones can also be done in linear time, because checking each triple is independent of every other triple. And there are an infinite number of 3-clones, and an infinite number of non-3-clone triples; so straightforwardly there are infinite numbers of sets of 3-clones and sets that aren't sets of 3-clones.

I think you need to strengthen the definition of non-triviality; any property of triples that is non-trivial can be lifted to a fairly boring non-trivial property of sets of triples, and there are lots of non-trivial properties of triples that are trivially easy to decide. Even the property of whether the first element of the triple is 1 works. I think the "interesting" properties of sets of triples are not just independently decidable for each triple and then combining the decisions. I'm not sure how to go about expressing that constraint in a rigorous way though.

As for a survey on the subject, I'm afraid I'd never heard of characterising NP-complete problems as properties of sets of triples, so I can't do much for you there.


Analysis of dependent double for Here is the algorithm:

int sum = 0
for (int i = 2N; i > 0; i = i / 4) {
  for (int j = 0; j < i; j+=2) {
    sum++
  }
}

I figured this would be linearithmic, but it's just linear. I would appreciate seeing a formalized summation and not a qualitative explanation. I have tried doing this but I fail to get linear runtime.

The number of iterations is:
$$T = \frac{2N}{2} + \frac{2N}{2 * 4} + \cdots + 1$$

The number of elements in the above formula is $\log_4(2N)$. After simplification, we will have:

$$T = N(1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log_4(N)}}) = \Theta(N)$$

As $1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log_4(N)}} < 2$ is a geometric series with step of $\frac{1}{4}$ in asymptotic sense.


Time complexity of finding predecessor for a dictionary implemented as a sorted array I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it takes O(1) time.

If the data structure looks something like

[(k0, x), (k1, x), ...]

where the keys k0 to kn are sorted, given k, I thought the successor(D, k) would first have to search the sorted array for k ( $ O(log n) $ ) and then get the successor ( $ O(1) $ ) since the array is sorted, and hence the overall time complexity should be $ O(log n) $ instead of $ O(1) $ as mentioned in the book. This should also apply for predecessor(D, k).

For an unsorted array, the time complexity for predecessor and successor remain as $ O(n) $ since searching the unsorted array also takes $ O(n) $.

Did I misunderstand something?

It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given key.

But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given entry index. Clearly this is O(1) for a sorted random access datastructure.

This particular interface is, in general, more useful and more efficient than the key-based interface previously presented, since it more accurately represents the cost of iterating through the dictionaries elements. Most such interfaces do, in fact, take some kind of cursor ("iterator" in C++ parlance) as an argument and return another cursor as a result.


How does reduction of a decision problem work? I am given the following problem description:

Given $l$ lists, $L_1$, $L_2$, . . .$L_l$ each containing $N$ bit vectors of $n$ bits each, we want to find tuples $(x_1,···,x_l)$ with $x_i$ in the corresponding $L_i$, such that:$$⊕_{i=1}^l x_i = S $$ for some target n-bit vector $S$.  In other words, we want to find one element from list such that the XOR of the chosen elements is the target $S$

Now I am required to show that if we can solve the equation in the case where $S=0$, we can for the same cost solve it for an arbitrary value (with exact same parameters, $N$, $n$, and $l$).  I am given a hint to proceed by reducing an instance with $S \neq 0$ to an instance with $S=0$.
What am I missing that I am not able to reduce it?

Let $I$ be your instance and consider the instance $I'$ obtained by replacing each bit vector $y$ in $L_1$ with $y' = y \oplus S$ (where $\oplus$ denotes bitwise xor). Call $L'_1$ the list containing all vectors $y'$.
Consider the tuples $(x_1, x_2, \dots, x_l)$ and $(x'_1, x_2, \dots, x_l)$ where $x_i \in L_i$ and $x'_1 \in L'_1$.
We have:
$$
      x_1 \oplus ( \oplus_{i=2}^l x_i ) = \oplus_{i=1}^l x_i  = S \iff  (x_1 \oplus S) \oplus  ( \oplus_{i=2}^l x_i ) = x'_1\oplus  ( \oplus_{i=2}^l x_i ) = S \oplus S = 0,
$$
showing that there is a solution to $I$ iff there is a solution to $I'$ (and you can convert one solution into the other in linear time).


Adding concept drift to data sets I'm about to work with concept drift problem in data streams.

I need to start with real data sets from UCI machine learning repository and add to them concept drift (in attributes domain).

Do you know tools that can help me with this?
Maybe someone knows it is possible to use MOA[1] framework for this?

What is best way to approach this if I have to do it by myself?

[1] http://moa.cms.waikato.ac.nz/

It sounds like you are trying to generate a synthetic data set, by artificially adding fake drift.

This is a bad idea.  Don't do this.

If you manage to find some algorithm that works well on your synthetic data set, then all you will know is that your algorithm works on a fake data set -- but you'll have no idea whether it is useful in practice.

Instead, I suggest that you try to find some real-world data sets that contain concept drift, and use them to work with.  If you're not sure how to do that, you might not be ready to do research in this area yet: you might want to spend some time talking to your advisor/mentor, or spend a bunch of quality time in the library reading papers in the literature that talk about the concept drift problem.


Why say that breadth-first search runs in time $O(|V|+|E|)$? It's often stated (e.g., in Wikipedia) that the running time of breadth-first search (BFS) on a graph $G=(V,E)$ is $O(|V|+|E|)$.  However, any connected graph has $|V|\leq |E|+1$ and, even in a non-connected graph, BFS will never look at a vertex outside the component that contains the start vertex.  That component contains at most $|E|$ edges, so it contains at most $|E|+1$ vertices, and those are the only ones that the algorithm will visit.

This means that $|V|+|E|\leq 2|E|+1$, so why don't we say that the running time is just $O(|E|)$?

This came up in comments on a question about the running time of Disjkstra's algorithm.

BFS is usually described something like the following (from Wikipedia).

 1  procedure BFS(G,start_v):
 2      let Q be a queue
 3      label start_v as discovered
 4      Q.enqueue(start_v)
 5      while Q is not empty
 6          v = Q.dequeue()
 7          if v is the goal:
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w)

The issue is a somewhat subtle one: it's hiding in line 3!  The question is, what data structure are we going to use to store which vertices have been discovered?

The simplest solution is to use a Boolean array with one entry per vertex.  In this case, we must initialize every element of the array to false and this takes time $\Theta(|V|)$. This applies for every graph, even if there are no edges at all, so we can't assume any relationship between $|V|$ and $|E|$ and we get a running time of $O(|V|+|E|)$.

Can we avoid having a data structure with $\Theta(|V|)$ initialization time?  Our first attempt might be to use a linked list.  However, now testing if a vertex has been discovered (line 10) takes time linear in the number of vertices visited, instead of constant time as before.  This means that the running time becomes $O(|V|\,|E|)$, which is much worse in the worst case.  (Note that we don't want to rewrite that as $O(|E|^2)$ since that's even worse: it could be as bad as $|V|^4$, whereas $|V|\,|E|\leq |V|^3$.)

Using a dynamically resized array would allow us to keep the list sorted, so now look-ups would only take time $O(\log|V|)$ but that still gives a running time of only $O(|E|\log|V|)$, which is still worse than standard.

Finally, we could use a dynamically sized hash table: start with a table of constant size $c$ and double it every time it gets half-full.  This means that the final size of the table is at most twice the number of vertices that are discovered before the algorithm terminates, and this is at most $|E|+1$ because we never discover anything outside the component of the start vertex. Furthermore, the total amount of work done copying the hash table to expand it is at most $c + 2c + 4c + \dots + 2|E|\leq 4|E|$.  Lookups and insertions to the hash table are amortized $O(1)$ so we do indeed obtain a running time of $O(|E|)$.

So $O(|E|)$ is possible, but would want to do that in a real implementation?  I would say probably not.  Unless you have reason to believe that your input graphs will have many small components, the overhead of maintaining the hash table is going to add a noticeable constant factor to the running time.  Growing the hash table could take time $4|E|$ and lookups will require you to compute the hash function and, on average, look at more than one slot in the table. The poor cache performance of hash tables might also hurt you on a real computer.  In most cases with the standard array implementation, the $O(|E|)$ part is the dominant term of the $O(|V|+|E|)$ running time so it's not worth using a hash table to remove the dominated term, given the practical cost of doing this.


What is the purpose of erasing a type application to a term-application in parametric polymorphism? From Types and Programming Languages by Pierce

  23 Polymorphism

  23.7 Erasure and Evaluation Order

  in a full-blown programming language, which may include side-
  eﬀecting features such as mutable reference cells or exceptions, the
  type- erasure function needs to be deﬁned a little more delicately
  than the full era- sure function in §23.6. For example, if we extend
  System F with an exception- raising primitive error (§14.1), then the
  term

let f = (λX.error) in 0;

  evaluates to 0 because λX.error is a syntactic value and the error in
  its body is never evaluated, while its erasure

let f = error in 0;

  raises an exception when evaluated.

  What this shows is that type abstractions do play a signiﬁcant
  semantic role, since they stop evaluation under a call-by-value
  evaluation strategy and hence can postpone or prevent the evaluation
  of side-eﬀecting primitives. We can repair this discrepancy by
  introducing a new form of erasure appropriate for call-by-value
  evaluation, in which we erase a type abstraction to a term-abstraction

erasev (x) = x
erasev (λx:T 1 . t 2 ) = λx. erasev (t 2 )
erasev (t 1 t 2 ) = erasev (t 1 ) erasev (t 2 )
erasev (λX. t 2 ) = λ_. erasev (t 2 )
erasev (t 1 [T 2 ]) = erasev (t 1 ) dummyv

  where dummyv is some arbitrary untyped value, such as unit.

Is the purpose of "erase a type abstraction to a term-abstraction" to prevent the body of a type abstraction from being evaluated?
What is the purpose of erasing a type application to a term-application by adding dummyv?
What is the evaluation rule for an application when the argument is unit?  (I can't find it in the section for type Unit.)

Thanks.

Q1

Is the purpose of "erase a type abstraction to a term-abstraction" to prevent the body of a type abstraction from being evaluated?

Yes.

  We can repair this discrepancy by introducing a new form of erasure appropriate for call-by-value evaluation, in which we erase a type abstraction to a term-abstraction

Q2

What is the purpose of erasing a type application to a term-application by adding dummyv?

The erasure introduces a term-abstraction into a type-abstraction:

eraseᵥ(λX. t₂) = λ_. eraseᵥ(t₂)

So the erasure needs a term-application instead of a type-application. An argument of the term-application can be any untyped value because it will be discarded, so for example unit.

Q3

What is the evaluation rule for an application when the argument is unit?  (I can't find it in the section for type Unit.)

The unit value unit is a value. Therefore we can use (E-APPABS) for an application.

(λx:T₁₁. t₁₂) v₂ ⟶ [x ↦ v₂] t₁₂    (E-APPABS)


Axiomatic Semantics and Postconditions I'll preface this by saying that this IS a homework question.

However, when asked about how to solve it in class, (I believe) my professor was unable to complete it.

The question is:

  Compute the weakest precondition for each of the following
  assignment statements and postconditions:
  $$a = a + 2b - 1\ \{a > 1\}$$ (where a > 1 is the postcondition)

His answer was: "$a > 2 - 2b$."
Is this correct? It seems that he broke the rules of equivalents, by using the ">" as "="

I believe the answer is:
$$\{a>1\;\wedge\; b<\tfrac12\}\quad\text{or}\quad \{a > 0\;\wedge\;2b-1 +a >1\},$$
    where the "$\wedge$" symbol means "and"

We're using Concepts of Programming Languages, by Sebesta, 10th Edition, so any references from that material would be excellent :)

Thanks!

A condition $P$ is weaker than $Q$ if $Q\Rightarrow P$; that is, whenever $Q$ holds, $P$ also holds or, if you prefer, $Q$ guarantees that $P$ holds. $P$ is strictly weaker than $Q$ if $Q\Rightarrow P$ but $P\not\Rightarrow Q$.  Let's look at the three conditions included in the question:

$a>2-2b$
$a>1 \;\wedge\;b>\tfrac12$
$a>0 \;\wedge\; a>2-2b$

(2) $\Rightarrow$ (3) since, if $a>1$ then certianly $a>0$ and, if $b>\tfrac12$, then $2-2b<1<a$. (3) $\Rightarrow$ (1) since if $X$ and something else are both true, then certainly $X$ is true. None of the reverse implications holds: (1) is satisfied by $a=-1$, $b=2$ but (3) is not; (3) is satisfied by $a=\tfrac12$, $b=1$ but (2) is not. Therefore, (1) is strictly weaker than (3) which, in turn, is strictly weaker than (2).

So $a>2-2b$ is the weakest of the preconditions on the table. But is it the weakest possible? Suppose $P$ is any precondition that implies that $a+2b-1>1$.  Rearranging, we see that $P\Rightarrow a>2-2b$, i.e., $P\Rightarrow$ (1). This tells us that no other precondition can be strictly weaker than (1). Therefore, (1) is the weakest precondition.

I don't understand what you mean by `It seems that he broke the rules of equivalents, by using the ">" as "="' since, surely, if (1) breaks that rule, (3) does too? I don't know that rule so maybe somebody else can address that part of the question.


How to understand definition of $\Pi_k$ in arithmetical heirarchy Am reading a text about computability theory, and according to the text, at each level $k$ of the arithmetical hierarchy, we have two sets, $\Sigma_k$ and $\Pi_k$, where $\Pi_k$ is defined as:

$$
\Pi_k=co-\Sigma_k
$$

So that for $k=0$, we have the class of decidable sets and $\Sigma_0=\Pi_0$, and for $k=1$, we have $\Sigma_1$ as the class of computably enumerable (c.e.) sets and $\Pi_1$ as the class of not computably enumerable sets (not c.e.)....

Let $L(M_e)$ denote the language recognized by Turing Machine $M_e$ with Godel number $e$. I came across the following language $E$, where:

$$E=\{e|L(M_e)=\Sigma^*\}$$

i.e. $E$ is the language of all Turing Machine codes $e$ that are computably enumerable. By a diagonalization argument, it can be shown that $E$ is not c.e. This implies that:

$$
E \in \Pi_1
$$

However, if $E \in \Pi_1$, it means that $E = co-A$, for some $A \in \Sigma_1$, using the definition in the above statement... However, the complement of $E$ is:

$$
\overline{E}=\overline{\{e|L(M_e)=\Sigma^*\}}
$$

which (I guess) means that $\overline{E}$ is the language of all Turing Machines $e$ such that on some inputs, $e$ diverges... However, it has been shown that $\overline{E} \equiv_m K^{2}$, i.e. $\overline{E} \equiv_m K^K$, so that, where given two sets $A$ and $B$, we have $A \equiv_m B$ iff $A \leq_m B$ and $B \leq_m A$, and $\leq_m$ refers to a many-to-one reduction:

$$
\overline{E} \equiv_m K^K \in \Sigma_2
$$

Given that $\Sigma_2 \neq \Sigma_1$, it looks like that $\overline{E}$ is not computably enumerable... But doesn't this contradict the definition of $\Pi_1$ which states that the complement of a not c.e. set is c.e. ?

I think am missing something in my understanding of the definitions ...

For $k$ even, a language $L$ is in $\Pi_k$ if there exists a recursive predicate $R$ such that
$$
x \in L \Longleftrightarrow \forall y_1 \exists y_2 \cdots \forall y_{k-1} \exists y_k \, R(x,y_1,\ldots,y_k)
$$
The quantifiers alternate between $\forall$ and $\exists$.

When $k$ is odd, the same definition works, but the last quantifier is $\forall$:
$$
x \in L \Longleftrightarrow \forall y_1 \exists y_2 \cdots \exists y_{k-1} \forall y_k \, R(x,y_1,\ldots,y_k)
$$

For example, the language of all total Turing machines is $\Pi_2$ since
$$
x \in \mathsf{TOT} \Longleftrightarrow \forall y \exists z \, \text{"Machine $x$ halts on input $y$ within $z$ steps"}
$$

The class $\Sigma_k$ is defined in the same way, with the first quantifier being $\exists$ rather than $\forall$.

If you complement a language in $\Sigma_k$ you get one in $\Pi_k$, and vice versa. This is due to de Morgan's laws for quantifiers, and the fact that the negation of a recursive predicate is also recursive.

For example, the language of non-total Turing machines is $\Sigma_2$ since
$$
x \in \mathsf{NTOT} \Longleftrightarrow x \notin \mathsf{TOT} \Longleftrightarrow \exists y \forall z \, \text{"Machine $x$ doesn't halt on input $y$ within $z$ steps"}
$$


Use of existential quantifier in tuple relational calculus It is somewhat confusing to me when to use quantifiers in tuple relational calculus (TRC). I stumbled upon following problem and I am still scratching my head thinking why not TRC query can be constructed without using existential quantifier.

The given problem reads like this:

  Relations:
  student (rollNo, name, degree, year, sex, deptNo, advisor)
  department (deptId, name, hod, phone)
  professor (empId, name, sex, startYear, deptNo, phone)
  course (courseId, cname, credits, deptNo)
  enrollment (rollNo, courseId, sem, year, grade)
  teaching (empId, courseId, sem, year, classRoom)
  preRequisite(preReqCourse, courseID)

  Question: Obtain the names of courses enrolled by student named "Roger".

  Given solution:

{ c.name | course(c) ^
                   (∃s) (∃e) ( student(s) ^
                                     enrollment(e) ^
                                     s.name = “Roger” ^
                                     s.rollNo= e.rollNo ^
                                     c.courseId = e.courseId}

Why I cant just have following? :

{c.name | course(c) ^
                 enrollment(e) ^
                 student(s) ^
                 c.courseId = e.courseId ^
                 e.rollNo = s.rollNo ^
                 s.name = "Roger" }

Something like { c.name | ... } is shorthand for something like

{z : (name) | (∃c) (z.name = c.name ^ ...) }.

As described on, e.g., the Wikipedia page, the fundamental form of the set comprehension (i.e. query) notation expects a variable to the left of the |. If you are familiar with anonymous functions/lambda notation, it is very similar to $\lambda z.(\dots)$. If we named it, it's like we're defining a predicate $P(z)\equiv(\dots)$. The upshot is that the notation effectively binds z (or c in the original form). But in your version without existential quantifiers, nothing is binding e or s. It's like you're referring to undeclared variables in a programming language.

Since whether the variables are bound with a universal or existential quantifier and where exactly that quantifier appears in the formula are all relevant, it would be difficult to infer which quantifiers should be added and where. (And as an additional possibility, we could just imagine that the variables are completely free and essentially become additional parameters to the anonymous predicate we're defining, but that doesn't fit in well with the Tuple Relational Calculus.) Prolog and Datalog do use a syntax that makes existential quantifiers implicit, but they are (in their basic forms) also limited to a language that 1) omits universal quantifiers, and 2) only allows formulas where existential quantifiers can always be pulled to being the outermost connective. Actually, when negation is added to Datalog, this stops being true and this implicit syntax starts to become ambiguous and confusing. Some implementations add an explicit existential and/or universal quantifier in such cases.

The upshot is, at the most fundamental level, all variables need to be bound, either by a quantifier or by the set comprehension syntax. There do exist various shorthands and conventions that are often used that can cloud this picture up, but ultimately every variable is introduced by some binding form.


What does Djikstra mean by "formal techniques" in this essay? In this essay (and others) by Djikstra, he refers to "formal techniques" a number of times.

... for the computing scientist, formal techniques would play a much more important rôle than they had done so far for the mathematician.
... The practical reason was that formal techniques are indispensable for dealing in a sufficiently trustworthy manner with the type of complexities a program designer has to control.
In our history, the computing scientist seems to be the first to be asked to apply formal logic on a grandiose scale and to make formal techniques an integral part of his daily reasoning; in a way, circumstances have forced him to become more mathematical than the Pope is Roman Catholic.
... what else can you expect in a world that has never seriously tried to apply formal techniques on a sizeable scale with elegant effectiveness?

I have only a vague idea of what he means by this term (which I'm sure has to do with the context he was writing in in 1985).
Does he mean something like "formal methods" -- proving mathematically that a program you've written is correct? If so, his assertions don't seem very accurate -- we're not doing that on a "sizable scale."
From other essays, I have the idea that perhaps he means "programming in a language with a specified syntax." To my understanding, this would make the third quote make more sense -- his argument is that mathematicians have no syntax their formulas must follow -- but I don't know why this would be called a "technique" or why it would be called "indispensable", as though it's some new technological advance for writing programs. How would programs be written, if not in terms of some strict syntax?
So I'm not sure I get what he's saying.

It seems quite clear that Dijkstra did mean what is known today as formal methods. He also had the idea that calculations should replace mathematical proof in prose, which you can find in some of the EWDs. It seems that so far his dream hasn't been realized, and while formal methods are used in some extreme circumstances, the average programmer has no use for them.


Interpretation of for loop. for every j != i in {0,....,n-1}

How to interpret this for loop? I never seen this type of definition of for loop.

Is it like -  j=0 to n-1; j !=i ; ++j

Here is the probable interpretation:

  for every $j \neq i$ in $\{0,\ldots,n-1\}$:

    code

should be interpreted as:

  for every $j$ in $\{0,\ldots,n-1\}$:

    if $j \neq i$:

      code

This is similar to the way this kind of statement is interpreted in mathematical text.

It is also possible that the roles of $i$ and $j$ should be switched — this should be clear from context, and it's an ambiguity that also exists in mathematical texts.

As mentioned in Evil's answer, if neither $i$ nor $j$ has been defined, then the interpretation is probably

  for every $i,j$ in $\{0,\ldots,n-1\}$:

    if $i \neq j$:

      code


Prove that the language { uw : |u| =2 |w| } is regular I have a problem with this following question:

  Prove that the language $\{uw : |u|=2|w|\}$ is regular.

I tried to give this regular expression $(uw²)^*$ to resolve it.

Any string of the form $uw$ where $|u| = 2|w|$ is a string whose length is a multiple of $3$. We are therefore considering the language of strings over some alphabet $\Sigma = \{ a_1, \ldots, a_k \}$ (not specified in the question). whose length is a multiple of $3$. Let $\Sigma$ be the regular expression $a_1 + \cdots + a_k$. Then a regular expression descring the language in question is

$$(\Sigma\Sigma\Sigma)^*$$


If L is context free and R is regular then R – L must be context free? Hi I am wondering if L is a CFL and R is RL then would the difference R - L be a context free language?
The difference might be the CF part of the language left then it would be, but I'm not sure how I could go about proving this without giving an example

Context-free languages are not closed under complement. This is a fairly well-known result.


Divide and conquer recurrence relation I have divide and conquer problem and below is the recurrence relation for it
$$\begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\
t(n) &= a\cdot t (n/4) + O(n^2)
\end{align}$$
I solved this recurrence for different values of $a$. These are the solutions below
$$ =\begin{cases}O(n^2),&\text{ for }a = 8\\
O(n^2 \log(n)),&\text{ for }a = 16\\
O(n^5/2),&\text{ for }a=32
\end{cases}$$
Do these solution always apply if $n$ is not power of $4$ and how can I justify it?

You need to define first where the recursion ends. And what t(n/4) means if n is not a multiple of 4.
The likely outcome will be that t(n) for 4^k < n < 4^(k+1) is between t(4^k) and t(4^(k+1)).


Is there a way to tell a picture has been resized? I need to evaluate if the picture was resized (upscaled). Are there any approaches to that already? If not, what do you recommend me to start with?

As Raphael already said, in general it's impossible.

There is the field of image forensics where people look for methods to detect tampering with images. For JPEG images for example, there is a paper about detecting resizing: A new approach for JPEG resize and image splicing detection.


Why is the complement of a language that is not regular also not regular? In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not regular, he wrote that it follows from the fact that the second language was the complement of the first, which we had already proved was not regular.

I was wondering if anyone could explain why this is the case?

Because regular langauges are closed under complementation. That is, if $L$ is regular, so is $\overline{L}$. (Exercise: prove this.)

So, suppose that $L$ is non-regular.  If its complement $\overline{L}$ were regular, then $\overline{\overline{L}}=L$ would also have to be regular.


minimum number of states for the regular expression Could somebody please tell me if there is a way to create a DFA with 8 states for the regular expression $$(111 + 11111)^*$$
I was able to create a DFA with 8 states, but the place I saw the question has answer as 9 states. And if possible, could you please show me the DFA.

Thanks

We can summarize this unary language by the list of possible lengths of words:
$$
0,3,5,6,8,9,10,11,12,\ldots.
$$
Now let us look at (left) shifts of this list:
$$
0,3,5,6,8-\infty \\
2,4,5,7-\infty \\
1,3,4,6-\infty \\
0,2,3,5-\infty \\
1,2,4-\infty \\
0,1,3-\infty \\
0,2-\infty \\
1-\infty \\
0-\infty
$$
There are 9 different shifts, and so 9 different states in the minimal DFA. In this case, the minimal DFA is very simple: it has 9 states $s_0,\ldots,s_8$, with arrows $s_i \to s_{i+1}$ (for $i < 8$) and $s_8\to s_8$, starting state $s_0$, and accepting states $s_0,s_3,s_5,s_6,s_8$.

This sort of reasoning works for all unary languages, though sometimes the minimal DFA won't be a simple path. For languages of the form $(1^{n_1}+\cdots+1^{n_k})^*$, the minimal DFA is in fact always a path, and assuming (without loss of generality) that $\mathrm{gcd}(n_1,\ldots,n_k)=1$, the number of states exactly equals $2$ plus the maximal integer not representable as a sum of non-negative multiples of $n_1,\ldots,n_k$ (in our case, $7$).


Why do more powerful programming languages tend to have slower implementations? I was reading this article. The author talks about "The Blub Paradox". He says programming languages vary in power. That makes sense to me. For example, Python is more powerful than C/C++. But its performance is not as good as that of C/C++.
Is it always true that more powerful languages must necessarily have lesser possible performance when compared to less powerful languages? Is there a law/theory for this?

This is simply not true. And part of why it's false is that the premise isn't well formed.
There is no such thing as a fast or slow language. The expressive power of a language is purely a function of its semantics. It is independent of any particular implementation.
You can talk about the performance of code generated by GCC, or about the performance of the CPython interpreter. But these are specific implementations of the language. You could write a very slow C compiler, and you can write Python interpreters that are quite fast (like PyPy).
So the answer to the question of "is more power necessarily slower" is no, purely because you or I can go write a slow C compiler, that has the same expressive power as GCC, but that is slower than Python.
The real question is "why do more powerful languages tend to have slower implementations." The reason is that, if you're considering the C vs Python, the difference in power is abstraction. When you do something in Python, there is a lot more that is implicit that is happening behind the scenes. More stuff to do means more time.
But there's also lots of social elements at play. People who need high performance choose low level languages, so they have fine grained control of what the machine is doing. This has led to the idea that low level languages are faster. But for most people, writing in C vs Python will have pretty comparable performance, because most applications don't require that you eke out every last millisecond. This is particularly true when you consider the extra checks that are manually added to program defensively in C. So just because lots of specialists have built fast things in C and C++ doesn't mean they're faster for everything.
Finally, some languages have zero cost abstraction. Rust does this, using a type system to ensure memory safety without needing runtime garbage collection. And Go has garbage collection, but it's so fast that you get performance on par with C while still getting extra power.
The TLDR is that more powerful languages are sometimes faster in some cases, but this is not a firm rule, and there are exceptions and complications.


terminology: half adders, full adders I'm very confused about the reasoning for these circuits being called 'full adders' and 'half adders'

I've read before that 'half adders' are called so, because two of them make up a 'full adder', and a 'full adder' is 'full' because you can get all the values $(0,0), (0,1), (1,0), (1,1)$.

But what irks me is that adding two bits would never get you $(1,1)$ in the first place, so why not call it a 2-bit adder, since that's exactly what it does. By extension, a 'full adder', in my mind, should be called a 3-bit adder.

If i think of full adders as '3 bit adders', would I ever run into any conceptual troubles? Same goes with '2 bit adders' and half-adders. Are there any historical insights as to why they are called such?

Cheers.

A "half adder" only does half the job: It adds two inputs x and y.

A "full adder" does the full job: Most of the time, you need to process two inputs, plus a carry from another (half or full adder). A "full adder" adds three inputs x, y and z.


SLR(1) Table construction, FIRST and FOLLOWS when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce.

Do I compute theme for the augmented grammar or the original one?
Is there even a difference?

In SLR(1) parser you need to compute only the follows of non-terminal symbols. When you have to put a reduce in the table, you look at the follows of the head of the production, and then put the production only in columns(correspond to terminals) that are in the follows.


Can a runtime environment detect an infinite loop? Would it be possible for a runtime environment to detect infinite loops and subsequently stop the associated process, or would implementing such logic be equivalent to solving the halting problem?

For the purpose of this question, I define an "infinite loop" to mean a series of instructions and associated starting stack/heap data that, when executed, return the process to exactly the same state (including the data) as it was in before initiating the infinite loop. (In other words, a program generating an indefinitely long decimal expansion of pi isn't "stuck" in an "infinite loop," because at every iteration, it has more digits of pi somewhere in its associated memory.)

(Ported from https://stackoverflow.com/q/16250472/1858225)

It might be theoretically possible for a runtime environment to check for such loops using the following procedure:

After ever instruction executed, the runtime environment would make a complete image of the state of a running process (i.e. all memory associated with it, including registers, P.C., stack, heap, and globals), save that image somewhere, and then check to see whether it matches any of its previously saved images for that process. If there is a match, then the process is stuck in an infinite loop. Otherwise, the next instruction is executed and the process is repeated.

In fact, rather than performing this check after every single instruction, the runtime environment could simply pause the process periodically and make a save-state. If the process is stuck in an infinite loop involving n states, then after at most n checks, a duplicate state will be observed.

Note, of course, that this is not a solution to the halting problem; the distinction is discussed here.

But such a feature would be an enormous waste of resources; continually pausing a process to save all memory associated with it would slow it down tremendously and consume an enormous amount of memory very quickly. (Although old images could be deleted after a while, it would be risky to limit the total number of images that could be saved because a large infinite loop--i.e., one with many states--might not get caught if there are too few states kept in memory.) Moreover, this feature wouldn't actually provide that much benefit, since its ability to catch errors would be extremely limited and because it's relatively simple to find infinite loops with other debugging methods (such as simply stepping through the code and recognizing the logic error).

Therefore, I doubt that such a runtime environment exists or that it will ever exist, unless someone programs it just for kicks. (Which I am somewhat tempted to do now.)


Maximum weight tree with weights on vertices Problem Statement

Let, $G(V,E)$ be a graph with a weight function $w(v)$ defined for all vertices. We need to find a tree $T(V',E')$ such that the resulting tree have maximum sum of weights of vertices, where $V' \in V$ and $E' \in E$. In short, we need to remove some vertices(along with all their edges) from $G(V,E)$ such that the resulting graph is a tree and have maximum weight among all such trees. $T(V'.E')$ should be an induced subgraph of $G(V,E)$.

My Attempt

First, sort the vertices in descending order. Then, pick the vertices in that order ensuring that adding a vertex won't create cycles. If it creates cycles, don't consider that vertex. To check if adding a particular vertex adds cycles, I thought of assigning each component a uniaue number. Hence, if adding a vertex results in joining that vertex to two vertices of the same component, we don't add that vertex. But, I couldn't find an efficient way on how should we keep track of which vertex belongs of which component. Can DSU help me with this approach?

It would seem that you need a Disjoint-set data structure.

When introducing each node $u$ with highest weight not in the tree, get all the nodes $u$ is connected to, call that neighbor set $C$. Iterate over all pairs $\{v, v'\}$ in $C$, $v \neq v'$, and check to see wether the disjoint-set trees of $v$ and $v'$ are same; if yes, adding $u$ will introduce a cycle. Finally, if adding that node $u$ restoring all the induced edges is possible without introducing a cycle, make sure that you add that $u$ to the same Disjoint-Set "tree" that contains all the prior nodes.


Is it possible to write a wait free leader election algorithm? I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously.

Finally I want to know how to derive the consensus number of this algorithm.
Googling did not work.

I believe that leader election derives from consensus algorithm, not other way around.  When electing leader you need consensus about who was chosen.

I'm not sure what you understand by "wait free". All communication in distributed system is asynchronous, and you always need to wait for reply.

You could start all nodes with ordered list of all possible leaders. When leader goes down all nodes could just pick next one from the list.  But again, to notice that leader goes down you need to ping it, and wait for response.  And probably coordinate (create consensus) that we changed a leader (if not, you will have a problem when encountering partitions).

So, last option is to choose one leader at start (trough config) and not allow any change.  But this does not fulfills requirements of most distributed system or leader election problem.


Hardware interrupts from keystrokes If there is an interrupt from every keypress (or one for keydown, one for keyup, one for keypress?) how does the OS handle so many interrupts at the same time. A person typing at 120WPM would be sending more than 500 interrupts per minute. How does a process ever finish if there is a context switch for the CPU to handle the interrupt 500 times per minute.

I must be missing something here?

A modern computer is designed to handle many more interrupts than you could possibly generate with your keyboard.

  You should expect interrupts to range upward from 1,000 per second for computers running Windows 2000 Server

See this link.


Are there hardware lock implementations without test-and-set or swap? Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these?

Also, can we say that all hardware level solutions to the critical section problem can be categorized into just three, namely, interrupt disabling, test-and-set and swap?

Yes, you can implement mutual exclusion with only memory load and store instructions.  There is a long tradition of devising successively simpler solutions to this problem.

The earliest version that I know of, called "Dekker's solution", was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO Advanced Study Institute, pp. 43-112, Academic Press, 1968.  There have been dozens of solutions since then.  I will discuss only a few of the more notable ones.

Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", Comm ACM 17(8):453-455, 1974 introduces the "Bakery algorithm" (because it is based on the analogy of people taking numbers to determine the order in which they will be served at the bakery shop).  One of the particularly notable features of this algorithm is that it demonstrates that no hardware atomicity at all is required to solve the mutual exclusion problem.  Reads that overlap writes to the same location can return any value and the algorithm still works.  Lamport discusses this a bit in the description of the paper on his home page.

Peterson's solution, Peterson, G.L.; "Myths about the mutual exclusion problem," Inf. Proc. Lett., 12(3): 115-116, 1981, is one that is specifically designed to be easy to understand, and reason about.
Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," ACM Trans. Comp. Sys., 5(1):1-11, 1987.  In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section.  It guarantees mutual exclusion and deadlock freedom, but not fairness.  It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention.  (When there is contention, it falls back on an O(N) test.)  He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses.  (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

Apparently people who work on the problem of solving mutual exclusion using just memory reads and writes get frustrated by other people's (lack of) understanding of the problem and its solutions.  This is demonstrated partly by the title of Peterson's paper ("Myths about the mutual exclusion problem") and partly by a short note that Lamport published in 1991: Lamport, Leslie; "The Mutual Exclusion Problem Has Been Solved", Comm ACM 34(1):110, 1991, which Lamport describes somewhat bitterly on his homepage.

So to answer your second question: No.  There are many more than three categories of hardware level solutions to the critical section problem (using just loads and stores is one, others involve compare-and-swap instructions, load-linked/store-conditional instructions (using the cache coherence protocol to test for atomicity), and fetch-and-add instructions.)  In another sense there's really just one category of solutions: those that involve getting a bunch of asynchronous processes to agree on a global order of events.

(Note that this answer is an (extensive) edit of an earlier answer I gave for a very different question.)