Polygon casting - Removing from mold by rotation The following question appears in Section 4.9 of "Computational Geometry: Algorithms and Applications" By Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf:

  Show that the problem of finding a center of rotation that allows us
  to remove $P$ with a single rotation from its mold can be reduced to the
  problem of finding a point in the common intersection of a set of
  half-planes.

$P$ here is a simple polygon with a given orientation, cast in a mold -

Whether $P$ can be removed with a translation can be reduced to whether
a common intersection of a set of half-planes is unbounded: Each edge of $P$, continued to a line, defines the half plane touching the outer side of the edge. The intersection of these half-planes is unbounded in a direction $\vec{v}$ if and only if translating $P$ by $\vec{v}$ does not cause any edge to push against the mold.

How can this reduction be modified to solve the case of removing $P$ with a rotation around a point?

Consider the marked edge of the following object (light gray) in its mold (dark gray) -

Where must $p$ be such that an arbitrary points on the edge will not be pushed against the mold? This figure shows the direction a point on the edge will be moving in when rotated around a point $p$ -

Notice that the point will be moving perpendicular to the line connecting it with $p$. Now recall that in order not to push on the mold, the points of the edge must move in the direction of the inner half-plane defined by the edge. This means that the possible locations for $p$ lie on a half-plane perpendicular to the edge. Here's the half-plane (in green) corresponding to an inner point of the edge -

The half-plane corresponding to the upper vertex of the edge, in this case, is contained in all of the half-planes for inner points, and so a rotation around any point in it moves the entire edge such that it does not push on the mold.

Whether $P$ can be removed with a rotation around $p$, is thus equivalent to whether $p$ is in the common intersection of the half-planes defined by $P$'s edges.


Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?

Yes, there is a pseudo-polynomial algorithm for this problem.

Here is a wrong algorithm. Can you spot the biggest error?

Let $K=\sum_{i=1}^n{a_i}$. If $K$ is not divisible by 3, return none.

Run the pseudo-polynomial algorithm with $\lfloor K/2\rfloor$ replaced by $K/3$ everywhere. Adapting the algorithm so that it tracks the set of numbers whose sum is a given number. If that run of that algorithm return false, return none. If yes, remove the set of numbers from $a_1, a_2, \cdots, a_n$, we reduce the problem to find a subset of the remaining numbers whose sum is $K/3$, or half of the sum of remaining numbers, which is, of course, the partition problem again and which can be solved in pseudo-polynomial time.

Let us see how to construct a correct algorithm.

In the pseudo-polynomial algorithm for partition into two disjoint subsets, the goal is to compute function $p$ such that $p(i, j)$ is True if a subset of $\{x_1, \cdots, x_j \}$ sums to $i$ and False otherwise.

Now for partition into three disjoint subsets we have two variable parts, the first subset and the second subset (the third subset is the remaining integers), our goal is to compute function $q$ such that $q(h,i,j)$ is True if there are two disjoint subsets of $\{x_1, \cdots, x_j \}$ such that one of them has sum $h$ and the other has sum $i$, where $0\le h\le K/3, 0\le i\le K/3$. We have the following recurrence relation, ignoring a few corner cases because of the out-of-bound situations that are easy to figure out.

$q(h, i, j)$ is True if either of the following is true.

$q(h, i, j − 1)$
$q(h, i − x_j, j − 1)$
$q(h-x_j, i, j − 1)$

$q(h, i, j)$ is False otherwise.

I will leave the rest for readers to figure out.

Exercise 1. Write the correct algorithm roughly or fully in pseudocode or in your favorite programming language. Adapt it so that it will track the subsets in order to return the wanted three disjoint subsets.

Exercise 2. Show the time-complexity of the correct algorithm is $O(nK^2)$.

Exercise 3. Generalize to PARTITION-INTO-M-SETS for any given integer $M\ge2$.


Terminology First-Order Logic A graph $G$ is said to be a  model of a first-order sentence $\varphi$ if $G$ satisfies $\varphi$. Now let $\varphi(x_1,...,x_r)$ be a first order formula with free variables $x_1,...,x_r$. What is the standard terminology for a tuple of vertices $(v_1,...,v_r)$ of $G$ such that $G$ satisfies the formula $\varphi(v_1,...,v_r)$ obtained by substituting $x_i$ with $v_i$?

What I'm having trouble is to find the right terminology to connect $G$ to the assignment. The only thing I can think now is the following.

"$(v_1,...,v_r)$ is a satisfying assignment for $\varphi$ in $G$."

But maybe there is a shorter way.

I think that's often called a "variable assignment", since it assigns to each variable a value (a vertex in the graph, in your case).

If the graph is equipped with a set of such tuples, these might be considered to be hyperedges, i.e. edges connected to an arbitrary number of vertices (not necessarily two of them).


Monetary computations theory (manual/textbook) My problem is due to the fact that I am manipulating a set of amounts that span over some intervals of time (start date/end date) and that are rounded to cents. I have to multiply each of them by some fraction (percentage), and I have to round the results to cents. Then I have to match the sum of what I calculated to the total amount (the sum of all chunks) multiplied by the same fraction (to make sure that precision loss didn't cause a lot of damage to the "big picture"), and if I have an error, I put it into the last (or first?) calculated value. Then I have to "balance" all the amounts for every start date I have (and, probably, for an end date too).

Example: $A_i$ is a monetary amount that is associated to a date $D_i$, $i\in [1, n]\subset\mathbb{N}$. I need to calculate commissions for every amount. I know the commission rate $cr$. Every commission amount should be rounded. So, I have $n$ commission amounts $CA_i$. The problem is that after rounding off the amounts, I get that ($\lceil x\rceil$ is the rounded value of $x$ in what follows):
$$\sum_{i=1}^n \lceil A_i*cr\rceil \neq \left\lceil\biggl(\sum_{i=1}^n A_i\biggr)*cr\right\rceil$$

Let's assume that I correct this error by adding the difference to $AC_n$. Now, I might have another problem: let $\{d_j\}_{1\leq j\leq m}$ be the set of all (distinct) dates $D_i$. So, I have that
$$\sum_{k=1}^? \lceil B_k cr\rceil \neq \left\lceil\biggl(\sum_{k=1}^? B_k\biggr)*cr\right\rceil$$
where $B_k = \{A_i \text{ such that } D_i = d\}$, for some date $d\in \{d_k\}$.
In other words, if I group the rounded results by date, there will still be an error compared to the total commission for this date. So, I should balance across every date (not forgetting about the total amount!)

This balancing is a very intuition-based approach, which might work or not. I've been looking for some formalization on the internet, but All I got was either the classic numerical analysis (after some brief introduction to floating point representation errors and rounding errors, it immediately goes to linear equations etc.) or just "Don't use floating point to represent money" articles. Are there any accessible sources on the specific topic of monetary calculations?

Let me illustrate one problem which could happen, and one way to solve it. You want to distribute a given amount of cents $N$ into $k$ piles, in proportions $p_1,\ldots,p_k$, where $p_1,\ldots,p_k \geq 0$ and $p_1 + \cdots + p_k = 1$. The problem is that $Np_i$ need not be an integer. As a simple example, you might want to divide $20$ cents into $1/3:2/3$ proportions. The fractional solution is
$$ 6\frac{2}{3}:13\frac{1}{3}. $$
It seems fair to round this to $7:13$ since $2/3 > 1/3$. More generally, compute $m_i = \lfloor N p_i \rfloor$ and $r_i = Np_i - m_i$. Here $m_i$ is the initial allocation and $r_i$ is the fractional one that you want to round. You need to add up some amount $R = N - \sum_i m_i$ of cents to make the total exactly $N$. Sort the $r_i$ in non-increasing order, and give one cent to the first $R$ parts according to this order (break ties arbitrarily). This is just a generalization of the example above.


Normalization in IBM hexadecimal floating point According to the Wikipedia link of IBM hexadecimal floating point:

  Consider encoding the value −118.625 as an IBM single-precision
  floating-point value.

  The value is negative, so the sign bit is 1.

  The value 118.62510 in binary is 1110110.1012. This value is
  normalized by moving the radix point left four bits (one hexadecimal
  digit) at a time until the leftmost digit is zero, yielding
  0.011101101012. The remaining rightmost digits are padded with zeros, yielding a 24-bit fraction of .0111 0110 1010 0000 0000 00002.

  The normalized value moved the radix point two digits to the left,
  yielding a multiplier and exponent of 16+2. A bias of +64 is added to
  the exponent (+2), yielding +66, which is 100 00102.

  Combining the sign, exponent plus bias, and normalized fraction
  produces this encoding:

  S Exp         Fraction
    1 100 0010    0111 0110 1010 0000 0000 0000
  In other words, the number represented is −0.76A00016 × 1666 − 64 =
  −0.4633789… × 16+2 = −118.625

Now, the definition of normalization according to Wikipedia says that

  In base $b$ a normalized number will have the form
  $±d_0.d_1d_2d_3...×b_n$ where $d_0≠0$, and the digits
  $d_0,d_1,d_2,d_3,...$ are integers between $0$ and  $b−1$

So, how is $0.011101101012 \times 16^2$ a normalized number?
In fact this number cannot be represented as a normalized one with base $16$ exponent because the closest we can get is  $1.1101101012 \times 16^1 \times 2^2$. What am I missing here?

I'm going to start with this famous quote from James Wilkinson's 1970 Turing Award Lecture, Some Comments from a Numerical Analyst.

  In the early days of the computer revolution computer designers and
  numerical analysts worked closely together and indeed were often the
  same people. Now there is a regrettable tendency for numerical
  analysts to opt out of any responsibility for the design of the
  arithmetic facilities and a failure to influence the more basic
  features of software. It is often said that the use of computers for
  scientific work represents a small part of the market and numerical
  analysts have resigned themselves to accepting facilities "designed"
  for other purposes and making the best of them. I am not convinced
  that this in inevitable, and if there were sufficient unity in
  expressing their demands there is no reason why they could not be met.
  After all, one of the main virtues of an electronic computer from the
  point of view of the numerical analyst is its ability to "do
  arithmetic fast." Need the arithmetic be so bad!

In 1970, Fortran had only been cross-platform for four years. A lot of numerical analysis was being done on IBM hardware, and System/360 in particular, but every CPU vendor had its own floating point format, and most of them (as Wilkinson indicated) were not designed by those who demanded high-quality floating point arithmetic.

Today, the industry has standardised on IEEE-754. It's imperfect, because everything is, but it's reliable and can be relied upon.

Wikipedia's definition of "normalised number" (or "normalized number"; I'm going to type it as my dialect spells it) is the current modern definition. It's the one you learned in high school when discussing scientific notation. It's the one used by IEEE-754. It's the one that's in all the modern textbooks.

But it's not the only normal form for floating point that has existed, and I think that's the source of the confusion here.

Interestingly, it's not the only normal form in use today! There is at least one place in modern programming where a different normal form is still in use, because it pre-dates IEEE-754.

The C standard library has a function to extract the parts of a floating-point number's normal form, called frexp. But the normal form that it uses is that the mantissa is in the range $\left[ 0.5, 1 \right)$, not the modern $\left[ 1, 2 \right)$. This is a notorious "gotcha" for numeric analysts working in C or C++ today.


Is the punctuation part of the alphabet? Given a language $L \subseteq \Sigma^*$, (it could be Italian, English, C++ or anything else), should we consider the punctuation (".", ";", "->") as a part of the alphabet $\Sigma$ upon the language is built on or not?

Yes, for a couple of reasons.

In natural language, punctuation changes the parsing and meaning of sentences. The classic example is "The panda eats shoots and leaves" (describing its diet) has a different meaning than "The panda eats, shoots, and leaves" (describing its violence before it departs). A parser should, in theory, generate different parse trees for these two sentences.
In formal languages, punctuation doesn't really exist as an entity separate from other symbols. So unless adding and removing punctuation from a word NEVER changes its membership in a language, you want to consider it, since any decision procedures will need to know about this.

For formal languages, we can't ignore that sometimes, what you call punctuation, might change the properties of the language.

For instance, it's easy to accept the set $\{ w.w^R \mid w \in \Sigma^* \}$ with a deterministic pushdown automaton. But remove the $.$ character as a delimiter, and we need non-determinism to guess where the end of the first string is, and where its reversal starts.


Root Color of a Black Red Tree It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice versa. I get the first half, that a red root can be changed to black at any time, but in what circumstance is it impossible to change a black node to red?

For instance, consider the branch: black--red--black--red--black. We can always change it to red--black--black--red--black, since a black node does not need to have red children.

The root colour of a red-black tree carries no significance. In fact, you can save memory by not encoding it. Didactically, it is meaningful to talk about a root's colour to illustrate what it means to be red or black, because it is a special case because it has no parent which is going to count it when it evaluates the sixth restriction in Wikipedia's list (that the path from a particular node to a leaf should contain the same number of black nodes).

As for your more general question about when changing a black node to a red one is allowed: a set of nodes can be repainted if afterwards, the black-height criterion is still satisfied. For example, if a row of the tree is saturated (if it is at depth $k$, there are $2^{k}$ nodes), then you can colour that row black. You may not colour only part of a (saturated or not) red row black. Another example: in the tree $1:red \rightarrow\{ 2:black, 3:black\rightarrow\{4:red, 5:red\}\}$, you can flip the colours of $\{3,4,5\}$ and still have a legal RB tree. This is true generally for subtrees of even height and alternating colours. Maybe you can think of more examples.


Counting Total Number of Non-Equivalent Configurations in a 2-D Grid This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both.

Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ thru $12$ inclusive. Each cell in this grid can be in any of $k$ states (where $k$ ranges from $2$ thru $20$).

The problem is to find the total number of distinct (non-equivalent) state configurations of this grid.

Definition: Two configurations of a grid, $c_1$ and $c_2$, are deemed "equivalent" if it is possible to change $c_1$ to $c_2$ by swapping any pair of rows and/or any pair of columns (you can perform the swap operation as many times as you want).

To take an example, let's consider a grid with $w=2$, $h=2$, and $k=2$. We will represent each of the two states as $0$ and $1$ respectively.

One possible configuration of the grid is one where all the cells are in state $0$:

00
00

You could swap any rows and/or columns without changing anything. So the above counts as 1 configuration.

Another configuration is where only 1 cell is in state $1$. There are 4 possible arrangements:

01 10 00 00
00 00 01 10

But note that all of the 4 arrangements are "equivalent", because you can get any of the arrangements by swapping rows and/or columns. So the above counts as 1 configuration.

Next, exactly 2 cells are in state $1$:

11 00
00 11

Another (non-equivalent) way in which 2 cells are in state $1$:

10 01
10 01

And yet another:

10 01
01 10

So there are 3 non-equivalent configurations in which exactly 2 cells are in state $1$.

Next, exactly 3 cells are in state $1$:

10 01 11 11
11 11 10 01

1 configuration, just as in the case where only 1 cell was in state $1$.

Finally, all 4 cells are in state $1$:

11
11

1 configuration, just as in the case where all 4 cells were in state $0$.

So, counting them up, there are exactly $7$ distinct configurations for the case where $w=2, h=2, k=2$.

For reference, here are some brute-force test cases I ran on some additional examples (where the w,h,k values are fairly small):

w=2,h=1,k=1 Answer: 1
w=2,h=1,k=2 Answer: 3
w=2,h=1,k=3 Answer: 6
w=2,h=1,k=4 Answer: 10
w=2,h=1,k=5 Answer: 15
w=2,h=1,k=6 Answer: 21
...
So at least when w, h are fixed at 1,2 (or at 2,1), the pattern seems pretty obvious as k increases. Here is another suite of test cases for w=2, h=2:

w=2,h=2,k=1 Answer: 1
w=2,h=2,k=2 Answer: 7
w=2,h=2,k=3 Answer: 27
w=2,h=2,k=4 Answer: 76
w=2,h=2,k=5 Answer: 175
w=2,h=2,k=6 Answer: 351
...
This is much less obvious to me. If there is a pattern, I'm unsure how to find it.

One more suite of test cases for good measure:

w=2,h=3,k=1 Answer: 1
w=2,h=3,k=2 Answer: 13
w=2,h=3,k=3 Answer: 92
w=2,h=3,k=4 Answer: 430
w=2,h=3,k=5 Answer: 1505
...
yep I'm lost as to what insight if any can be gained.

So, for some arbitrary $w,h,k$, I'm wondering whether there is some type of closed-form formula or perhaps a way to get the answer via dynamic programming/recursion or perhaps divide-and-conquer? I've tried a few of these approaches and didn't really see any obvious breakthrough. The answers get very large very quickly (for example, for $w=2,h=3,k=4$, the answer is 430). I can only imagine how large the answer would be for, say, $w=12,h=12,k=20$.

I would appreciate any help on this. Thanks!

We will use Burnside's lemma, plus some additional optimizations.

Note that row swaps and column swaps commute, so the group of allowable transformations to the grid is exactly $G = S_w \times S_h$, where $S_n$ is the symmetric group on $n$ symbols.  Note that $G$ embeds in $S_{wh}$ via a canonical embedding $\varphi : G \to S_{wh}$, given by $\varphi(\pi,\sigma) = \tau$ where $\tau$ is defined by $\tau(i,j) = (\pi(i), \sigma(j))$.  Therefore, we will think of $G$ simultaneously as the direct product $S_w \times S_h$ and also as a subgroup of $S_{wh}$.

Now let's count the number of grids that are fixed by a group element $g=(\pi,\sigma) \in G$.  Define the cycle type of a permutation $\pi$ to be the multiset of lengths of the cycles in the cycle decomposition of $\pi$.  If $\pi \in S_n$, the cycle type of $\pi$ is a partition of $n$.  With this in mind, we will let $\ell(\pi)$ denote the cycle type of $\pi \in S_w$ and $\ell(\sigma)$ the cycle type of $\sigma \in S_h$.  Finally, let $\ell((\pi,\sigma))$ denote the cycle type of $(\pi,\sigma)$, thinking of $(\pi,\sigma)$ as an element of $S_{wh}$.  We can express $\ell((\pi,\sigma))$ in terms of $\ell(\pi)$ and $\ell(\sigma)$: let $x,y$ range over $x \in \ell(\pi), y \in \ell(\sigma)$, and for each $x,y$, $\ell((\pi,\sigma))$ has $\gcd(x,y)$ copies of $\operatorname{lcm}(x,y)$.

Now the number of grids that are fixed by $(\pi,\sigma)$ is

$$f(\pi,\sigma) = k^{|\ell(\pi,\sigma)|},$$

where $|\ell(\pi,\sigma)|$ counts the number of cycles in $(\pi,\sigma) \in G$ (multiplicities are counted).  By the above characterization of $\ell(\pi,\sigma)$, we see that

$$f(\pi,\sigma) = k^{\sum_{x \in \ell(\pi)} \sum_{y \in \ell(\sigma)} \gcd(x,y)}.$$

To apply Burnside's lemma, it remains to sum $f(g)$ over all elements $g \in G$, as Burnside's lemma tells us that the total number of non-equivalent grids is

$$N = {1 \over |G|} \sum_{g \in G} f(g) = {1 \over w! h!} \sum_{g \in G} f(g).$$

In principle, we could compute this sum by enumerating all $w! h!$ elements in $G$, then evaluating $f$ on each, and summing the result.

It turns out this can be optimized further, as $f((\pi,\sigma))$ depends only on $\ell(\pi)$ and $\ell(\sigma)$, but not on any other aspect of $\pi$ or $\sigma$.  Thus, we can more efficiently evaluate the sum using the formula

$$\sum_{g \in G} f(g) = \sum_{P,Q} n(P,Q) \times k^{\sum_{x \in P} \sum_{y \in Q} \gcd(x,y)},$$

where the inner sum ranges over all partitions $P$ of $w$ and all partitions $Q$ of $h$, and where we define

$$n(P,Q) = |\{(\pi,\sigma) \in G : \ell(\pi)=P, \ell(\sigma)=Q\}|$$

to count the number of group elements of $G$ whose cycle types are $P,Q$.  Now we have

$$n(P,Q) = n_w(P) \times n_h(Q),$$

where $n_w(P) = |\{\pi \in S_w : \ell(\pi)=P\}|$ is the number of permutations in $S_w$ with cycle type $P$, and similarly $n_h(Q)$ is the number of permutations in $S_h$ with cycle type $Q$.  Finally, it is easy to compute $n_w(P)$ for any desired partition $P$; it is

$$n_w(P) = {w! \over \prod_{x \in P} x}.$$

Plugging in, we find that the total number of non-equivalent grids is given by

$$N = \sum_{P,Q} {k^{\sum_{x \in P} \sum_{y \in Q} \gcd(x,y)} \over \prod_{x \in P} x \prod_{y \in Q} y}.$$

This can be computed by two nested for-loops that iterate over all partitions $P$ of $w$ and all partitions $Q$ of $h$.

What is the running time of this algorithm?  The  asymptotic running time is approximately $O(p(w) p(h))$, where $p(n)$ is the number of partitions of the integer $n$.  It is known that asymptotically $p(n) = O(\exp\{\pi \sqrt{2n/3} \})$, so it follows that the asymptotic running time of this algorithm is approximately $O(\exp\{\pi \sqrt{2/3} (\sqrt{w}+\sqrt{h})\})$, or equivalently, approximately $O(2^{3.7(\sqrt{w}+\sqrt{h})})$.  This should allow you to handle the full range of values $1 \le w,h \le 12$, as for that range we have $\sqrt{w}+\sqrt{h} < 7$ and $2^{3.7 \times 7} \approx 2^{26}$ is not too large.


Is the Rice Theorem applicable for these problems? I have 1 problem :-->

L = { < M > | TM halts on no inputs }

I have solved the above problems by reductions given in the book and even there are many links in stackexchange site. I have no problems in the reduction method.

But, just trying to be more curious, I tried to solved these problems by using rice theorem. I know that rice theorem is applied on the property of languages and here it is property of TM's but i tried some conversion here .

Though, I am getting the right answer but i want to confirm is what i have tried is legal or Can It be solved like this ?

As the TM halts on no inputs, which means it is not halting on the inputs in the language as well as inputs not in the language.

So, I wrote it as

L = { < M > | L(M) = PHI }

which is surely a non trivial property and as well as non monotonic property, hence the language is Undecidable and as well as Non RE.

Well, I am new to this topic. So, i don't know whether I am right in the conversions or Can I assume something like this. Please correct me if i am being stupid .

Rice's theorem cannot be used to show the undecidability of these two languages.

Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property is a vague notion from everyday life. However, a property means something very precise in the context of computability theory: A property is a class of Turing-recognizable languages.

Rice's theorem can be applied whenever we are faced with a non-trivial class of Turing-recognizable languages $\mathcal{S}$, that is, a class of Turing-recognizable languages that is neither the empty class or the class of all Turing-recognizable languages. Rice's theorem tells us that if $\mathcal{S}$ is a non-trivial class of Turing-recognizable languages, then

$$L_{\mathcal{S}} = \{ \langle M \rangle \mid M \text{ is a Turing machine such that } L(M) \in \mathcal{S} \}$$

is undecidable.

But there is no class of recognizable languages that corresponds to

$$A = \{ \langle M \rangle \mid M \text{ halts on no input} \}$$

For consider the Turing machines $M_1$:

"On input $x$, loop forever"

and $M_2$:

"On input $x$, reject"

We have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.

Similarly, there is no class of languages that corresponds to

$$B = \{ \langle M \rangle \mid M \text{ halts on at least one input} \}$$

Here, we can choose $M_1$ as

$M_1:$ "On input $x$, if $x = aa$ then reject, else loop forever"

and $M_2$ as

$M_1:$ "On input $x$, reject"

Again we have that $\langle M_1 \rangle \in A$ but $\langle M_2 \rangle \notin A$, while we also have $L(M_1) = L(M_2)$.

A correct application of Rice's theorem to a decision problem about Turing machines must identify a non-trivial class of Turing-recognizable languages that the decision problem corresponds to.

See my note http://people.cs.aau.dk/~hans/ANoteOnRicesTheorem.pdf for more about correct applications of Rice's theorem as well as a discussion of incorrect applications of the theorem.


Why do we say that polynomial time is easy? For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so.

Intuitively, I can guess what the relation between P problems and easy problems is. Experience tells me that P problems are easy too. However, using only mathematical terms and theoretical arguments, why is P the class of easy problems?

I don't think it is possible to argue strictly with only mathematical or theoretical terms. Very much does come down to heuristics.
Of course an algorithm with runtime $O(n^{1000})$ or something similarly ridiculous would not be "easy" and in most practical cases worse than an algorithm of modest exponential growth. Yet such algorithms just don't happen in practice. And if an algorithm initially has a quite high runtime, then more often than not it can be improved dramatically, which means that the problem is a lot less "difficult".
As an example, take the AKS algorithm (which tests whether a given number is prime). It started out as $O(n^{12})$ (if I recall correctly), being one of the polytime-algorithms with the greatest exponent. But it was improved to $O(n^{6+\epsilon})$ in a quite short time. And very fast probabilistic algorithms for the primality problem exist as well, which shows that proving primalty is a lot easier than, say, your favorite NP-complete problem (assuming $P\neq NP$).

Of course the above could all turn out to be completely wrong. Maybe there exists a polytime algorithm for every NP complete problem which does not have a "practical" exponent. Knuth advocates that scenario; you might want to read question 17 here.


Greedy algorithm for even item distribution I have this problem where I need to design a greedy algorithm. The problem is as follows:

A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $c_i$ of chocolates. Furthermore, the factory would like to have the same amount of chocolate in each store. Therefore, they hired a truck driver to haul chocolates between the stores, but the driver eats two chocolate bars for each kilometer he drives.

Calculate the largest amount of chocolate $C$ they can have at each store.

Input: The position $p_i$ and chocolate supply $c_i$ of each store. The positions are in increasing sorted order.

Output: The largest amount $C$, such that each store can have a chocolate supply of at least $C$ after the truck driver has hauled between the stores.

I have a problem with identifying the greedy choice property for the problem. So far I came up with the following:

The greedy choice can be the minimum arithmetic mean of two neighbouring stores minus the delivery cost divided by $C$, but it has to be larger or equal to 1. I came up with the following equation:
$$\min\{\frac{\frac{1}{n} \cdot (c_i + c_{i_{neighbour}} - delivery_{cost})}{C}\}$$

Where the delivery cost is $2\cdot |p_i - p_{i-1}|$.

I am not sure if this approach is the right one. I am open for hints and partial solutions.

It looks like a greedy algorithm cannot do it alone.

Here is an approach based on binary search.

Suppose we have a subroutine to determine that if it is possible to have a chocolate supply of $s$ after the truck driver has hauled between the stores, given $s$. Note that if $s$ is possible, than $t$ is possible for any $t<s$.

Let $m$ be the maximum among $c_i$. Let us check if $m/2$ is possible. If yes, let us try $(m/2 + m + 1)/2$. (+1 to ensure we will try $m$ just in case). If no, check $m/4$. I believe you can see the rest of binary search algorithm. Be careful with various boundary cases.

Now the problem is how to build that subroutine? We can think recursively. Let $s$ be given. If $c_1>s$, we will use a truck to move $c_1-s$ chocolates to $p_2$. Whatever is left when the the truck has reached $p_2$ will be added to $c_2$. So we got $c_2'$. If $c_1=s$, $c_2'=c_2$. If $c_1<s$, compute $d_2$, the least amount of the chocolate needed to be carried on a truck that starts from $p_2$ can reach $p_1$ to increase $c_1$ to $s$. Subtract that amount from $c_2$ and get $c_2'$, which might be negative. We can see that $s$ is possible initially if and only if $s$ is possible for $c_2', c_3, \cdots, c_n$ at $p_2,p_3,\cdots, p_n$ respectively.

There should be enough hint above. I will let you finish the rest of work.


Showing that a bijection preserves homomorphism I have the vocabulary $\tau = \{+, 0 \}$ and the structure $R = (\mathbb{R}, +^R, 0^R)$ where $+^R$ is a binary function symbol representing the normal addition of numbers and $0^R$ is the constant $0$ in $\mathbb{R}$. I 'm trying to prove that the bijection $$\sigma : \mathbb{R} \rightarrow \mathbb{R} \text{ with } \sigma(x) = -x$$
is an automorphism of $R$.
What I (think I) only need to show: the homomorphism property for each function symbol, in this case  $$+^R : \sigma (x +^R y) = \sigma(x) +^R \sigma(y) \ \forall x, y \in \mathbb{R}$$ holds. We don't need to worry about $0$, since it's covered by our bijection's definition.
So, the homomorphism property seems to work for every $x$ and $y$ I pick, for example:
$$\sigma(1+^R1) = \sigma(2) = \sigma(1) +^R \sigma(1) = -1 +^R -1 = -2$$
$$\sigma(2+^R1) = \sigma(3) = \sigma(2) +^R \sigma(1) = -2 +^R -1 = -3$$
etc.
We can't prove by induction because we're not working in $\mathbb{N}$. Can anyone show me or give me a hint how I can formally prove this for all numbers in $\mathbb{R}$?

The symbol $0^{\mathbb R}$ is a 0-ary function symbol, and you need to handle it as well. Since $-0 = 0$, this is not a problem.
As for $+^{\mathbb R}$, high school arithmetic shows that
$$
-(x+y) = (-x) + (-y).
$$
More generally, $-$ is an automorphism of any Abelian group. An Abelian group is a set together with a binary operator $+$, a unary operator $-$, and a constant $0$ such that:

$x+y = y+x$.
$(x+y)+z = x+(y+z)$.
$x+0 = x$.
$x+(-x) = 0$.

The mapping $x \mapsto -x$ is an automorphism. Notice that

For all $x$, $(-x)+x=x+(-x)=0$.
For all $x$, $(-x)+(-(-x))=0$.
Hence $x = x+0 = x+((-x)+(-(-x))) = (x+(-x))+(-(-x)) = 0+(-(-x)) = (-(-x))+0 = -(-x)$.

Therefore $-$ is an involution. In particular, if $-x=-y$ then $x=-(-x)=-(-y)=y$, so that $-$ is one-to-one. Since $-(-x)=x$, it is also onto.
Since $0 = 0 + (-0) = (-0) + 0 = -0$, we see that $-$ maps $0$ to itself.
Since $-(-x) = -(-x)$, we see that $-$ maps $-$ to itself.
Finally,
$$
(x+y)+((-x)+(-y)) = (y+x)+((-x)+(-y)) = ((y+x)+(-x))+(-y) = (y+(x+(-x)))+(-y) = (y+0)+(-y) = y+(-y) = 0.
$$
Therefore
$$
-(x+y) = (-(x+y)) + 0 = (-(x+y)) + ((x+y)+((-x)+(-y))) = ((-(x+y))+(x+y)) + ((-x)+(-y)) = ((x+y)+(-(x+y))) + ((-x)+(-y)) = 0 + ((-x)+(-y)) = ((-x)+(-y)) + 0 = (-x)+(-y).
$$
This shows that $-$ maps $+$ to itself.


Weighted Set covering problem with a fixed number of colors I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost.

I have a fixed number of colors, C = {1 , 2, ... , m}. Some of the sets mentioned above interfere with each other. I cannot assign same color to both those sets together.

I want to pick the sets and color them from my available color list in the following way:

**Objective: Minimize the total cost of the selected sets

Constraints:

All elements of the universe are covered
No two sets that interfere with each other is assigned the same color**

If the second constraint, i.e., coloring constraint, is taken out, the problem reduces to standard weighted set covering problem. I can solve that using a greedy manner. For example, greedy unweighted set covering will work in the following way: -- 1. pick the set with the highest number of elements at first, 2. Remove that set and the associated elements from the universe, 3. Repeat step 1 until all elements of the universe are covered.

But the coloring constraint in the presence of interference among sets and a fixed number of colors complicates the issue.

For example, let's assume,

U = {1, 2, 3, 4, 5}.

There are three sets, {1, 2, 3}; {2, 3, 4, 5} ; {4, 5}.

Assume {2, 3, 4, 5} interferes with both {1, 2, 3} and {4, 5}. {1, 2, 3} and {4, 5} do not interfere with each other. Assume that there is only one color in the system.

A standard greedy unweighted set coloring solution will pick {2, 3, 4, 5} at first and {1, 2, 3} in the second round. But that is an infeasible solution to my problem since they interfere with each other and I have only one color in my system. A feasible solution will be the selection of {1, 2, 3} and {4, 5}.

I wonder how I can minimize the total cost while meeting the color constraint. Any hint on the unweighted version of the problem (where all sets have equal cost) will be very helpful, too.

Thanks,

Nazmul

Additional information: The coloring of the sets and the interference can be understood by my application scenario.

I am looking at a wireless cell. I have a set of frequencies, possible base station locations and their associated users. Each set is associated with a station and it shows the set of users that the base station can serve.

"Interference" from one set to the other means that the users' signals of one set reaches the other set's base station. In a wireless setting, this interference is not symmetric. But assumption of symmetry is OK in the algorithm because if set A interferes with set B, A & B both should get different colors if they are selected.

The interference among sets is not transitive. Set A may interfere with set B (A's users may interfere with B's base station) and set B may interfere with set C (B's users may interfere with C' base station) but that does not mean that set A will interfere with set C.

The current example is showing that two sets interfere if they intersect. This is just a coincidence. I will have a pre-generated look up table that shows which set interferes with which set before the algorithm starts. This pre-generated table will be an input to the optimization problem

General advice

The question is confused about what you are looking for.

There is obviously no hope for a polynomial-time algorithm that finds the optimal solution to this optimization problem.  This problem is at least as hard as weighted set covering (without coloring restrictions).  Weighted set covering is NP-hard.  Therefore, your problem is NP-hard.  Therefore, any general polynomial-time algorithm that always outputs the optimal solution to your optimization problem would imply that $P=NP$ (which seems unlikely).

Obviously, if the question is confused about what you're looking for or if you are unable to communicate it in the language that computer scientists understand, then that reduces the likelihood that anyone will be able to answer your question in a way that helps you.  We're not mind-readers.

Based on your comments, I suspect that what you actually want is an approximation algorithm for your problem, or a heuristic algorithm.  So, here is my advice, based upon my inference of what I suspect you actually want (as opposed to what you said you want).

First, I suggest that you learn about approximation algorithms and heuristic algorithms.  Learn the terminology, learn some basic results, learn some of the standard examples of approximation algorithms.  This will help you communicate with others and be able to express your requirements clearly in a language that other computer scientists can understand.  Also learn about standard strategies for dealing with NP-completeness (e.g., Dealing with intractability: NP-complete problems).

Second, I suggest that you take a closer look at the sort of problem instances typically arise in your application.  If you want to maximize the chance you find an approximation algorithm or heuristic algorithm that is useful in your application scenario, you need to analyze the parameters and properties of the problem instances that arise in your application.  What are typical values of $k,m,n$?  That's the sort of question you should be asking (and communicating in the question).

Without that kind of information, I don't think anyone here can predict what the best approach to your particular problem might be.  However, I'll suggest some candidate approaches that you could try out.

SAT solvers

You can formulate (the decision problem version of) your problem as a SAT instance and then try solving it with an off-the-shelf SAT solver.

We'll solve the decision problem version: given $u$, we'll test whether there exists a solution of total cost at most $u$.  Introduce boolean variables $x_1,\dots,x_k$.  The intent is that $x_i=1$ means that the $i$th set $S_i$ is selected, and $x_i=0$ means that it is not.  Also introduce variables $c_1,\dots,x_k$, where $c_i\in \{1,\dots,m\}$ represents the color assigned to the $i$th set (if it is selected).  Note that each $c_i$ can be represented as a number of boolean variables using standard techniques.  Finally, introduce variables $y_0,y_1,\dots,y_k$, where $y_i$ is an integer that represents the total cost of all sets that were selected from out of the first $i$ sets.  Each $y_i$ can be represented as $\lceil \lg (u+1) \rceil + 1$ bits, using binary encoding.

Now we're going to add some constraints to capture the requirements for a solution to be valid.  For each element $u \in U$, we'll add a constraint to require that element $u$ is covered by at least one of the selected sets:

$$\bigvee_{u \in S_i} x_i.$$

(Here the logical OR is taken over all sets $S_i$ that contain $u$; at least one of them must be selected.)  Also, for each pair $i,j$ of sets that interfere, we'll add a constraint to require that they have been given different colors: namely, $c_i \ne c_j$.  Finally, we'll add constraints to define the $y_i$'s: $y_0=0$, and for each $i=1,\dots,k$:

$$y_i = y_{i-1} + \begin{cases}
\text{cost}(S_i) &\text{if $x_i=1$}\\
0 &\text{otherwise} \end{cases}.$$

Finally, we'll add the constraint that the total cost is at most $u$: namely, $y_k \le u$.  To deal with overflow, it helps to add constraints that $y_i \le u$ for all $i$ and to make sure you've allocated enough bits for each $y_i$ so that you can encode all integers in the range $0,1,\dots,2u$.

Notice that all of these constraints can be encoded in SAT (i.e., as CNF clauses) in a straightforward way.  Some SAT solver front-ends, such as STP, even provide support to make it easy to express these: they'll convert the integer constraints to CNF by bit-blasting.

Now that you've formed a CNF formula representing the assertion that there exists a solution of total cost $\le u$, you feed it to a SAT solver and see whether it can find a satisfying assignment.  If it can, then you know the optimal solution costs at most $u$; if it can't, you know the optimal solution costs at least $u+1$.  Now you can use binary search to find the optimal solution.

This is not an approximation algorithm: this algorithm finds the exact optimum.  Of course, it is a heuristic.  SAT is NP-complete, so there is no guarantee that this algorithm will run in polytime (and we can be pretty sure that on some problem instances, it won't).  However, SAT solvers are pretty good in practice, and so this might work pretty well on problem instances that arise from practice.

This formulation is a straightforward combination of the formulation of weighted set cover as a SAT problem, and the formulation of graph coloring as a SAT problem (see e.g. here).  If you are having trouble following this, study other reductions to SAT and other ways of encoding standard problems as SAT instances.

Integer linear programming

Another approach would be to formulate this as an integer linear program, then feed it to an off-the-shelf ILP solver.

The approach is very similar to the formulation in SAT.  You can use similar variables to that listed in my SAT formulation above.

Boolean variables can be encoded as integer variables that are restricted to be in the range $0 \le \cdot \le 1$.  Boolean operations on boolean variables can be expressed using the techniques shown here: Express boolean logic operations in zero-one integer linear programming (ILP)

I recommend encoding the $c_i$'s as a one-hot encoding, i.e., introduce boolean variables $c_{i,j}$ where $c_{i,j}=1$ means that the $i$th set (if selected) is assigned the color $j$.  Then you can add the constraints

$$\sum_j c_{i,j} = 1 \text{ for each $i$}$$

and

$c_{i,j}+c_{i',j} \le 1$ for each pair of sets $i,i'$ that interfere and each color $j$.

There's no need for the variables $y_0,\dots,y_k$ or to limit yourself to the decision version of the problem.  Instead, you can make the objective function be

$$\sum_i \text{cost}(S_i) x_i,$$

which is a linear function of the variables (as required).

Now feed it to an ILP solver, and see what the best solution it can find is.

Naive greedy algorithm

There's a straightforward extension of the greedy algorithm, that could be used for your problem.  It will only sometimes find a solution, so it is incomplete; other times, it will fail to find any valid solution.

In particular, at each point in time, we will have a partial solution (some sets that can be colored with $\le m$ colors).  We will incrementally select a set to add to the partial solution greedily.  We can prioritize the sets as follows, to help us select the next set.  The priority of $S_i$ is the number of additional elements of $U$ that would be covered if we selected $S_i$ (over and above the number of elements that have already been covered by our current partial solution), divided by the cost of $S_i$.  Given a partial solution, we find a coloring for the sets (using some heuristic for graph coloring that tries to color them with as few colors as possible), then for each $i$ we see whether adding $S_i$ would increase the number of colors above $m$.  If we can't find a way to color the current selection + $S_i$, then we throw away $S_i$.  Out of the remaining unselected sets, we choose the set with the highest priority.  We repeat until we can make no further progress.

If this process ends with a selection that covers all of $U$, then we have found a candidate solution.  It may not be optimal (it probably won't be), but it is a solution.  If it ends without covering all of $U$, then the algorithm failed.


On the hardness of constraint satisfaction I am interested in the hardness of the following question.

Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\mathbf{v}_m$ with each $\mathbf{v}_j \in \{-1,1\}$.

Our objective is to maximize the number of nonnegative dot products between $\mathbf{x}$ and each $\mathbf{v}_j$, where each $0\leq x_i\leq 1$.

That is

$$\max_{\mathbf{x}}\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$$

$$\text{such that} 0\leq x_i \leq 1$$

These constitute linear constraints and I know in general that maximizing the number of satisfied linear constraints is NP, but these constraints differ in two main ways. The first is that none have a bias term, and the second is that each coefficient of the optimization variables is either 1 or -1.

As pointed out by Antti Röyskö the solution $\mathbf{x} = 0$ always maximizes the objective function since  $\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$ corresponds to the number of constraints $\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0$ which are satsificed, and $\mathbf{x}$ satifies all constraints.

However, the problem becomes much more interesting if we dont allow degenerate solutions. In fact, by removing $\mathbf{x} = 0$, the problem goes from having a closed form solution, to being NP-hard. It takes a bit of work, but you can actually reduce any integer feasibility program down to your problem.


$A$ and $B$ are Turing-recognizable and their union is $\Sigma^*$, find a decidable $C$ with $A - B \subseteq C$ and $B - A \subseteq \overline{C}$ Sorry for long title - the question is a bit unwieldy. To state the question precisely, I'm wondering about the following proposition:

  Let $\Sigma = \{0,1\}$. If $A$ and $B$ are Turing-recognizable and $A \cup B = \Sigma^*$, then there exists a Turing-decidable language $C$ such that $A \cap \overline{B} \subseteq C$ and $\overline{A} \cap B \subseteq \overline{C}$ (equivalently, $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

So, my current train of thought is as follows.
Because $A \cup B$ is $\Sigma^*$, we have that $\Sigma^*$ is partitioned into exactly three disjoint sets: $A - B$, $A \cap B$, and $B - A$. That is, given $x \in \Sigma^*$, $x$ is in exactly one of these sets.

The basic way I can think of to obtain a decidable language is to enumerate one in lexicographic order (which always yields a decidable language). So one idea would be to enumerate $\Sigma^*$ in lexicographic order, and print a string if and only if it is not in $B - A$, but that poses a problem because we would have to decide membership in $B - A$, but they are merely recognizable.

I've thought about enumerating $A$ and $B$ but since they're only recognizable, the enumerations could be in any arbitrary order, making it impossible to compare them to test for membership in $A-B$ or $B-A$.

Finally, I know that $A$ and $B$ (if they are infinite) have infinite decidable subsets, but I don't think that will help.

I'd appreciate some hints if anyone has any.

Edit: Missed a hypothesis that $\Sigma = \{0,1\}$, which I'm not sure is relevant (I wouldn't think so), but it might be.

Got it. The question makes it seem more complicated than it really is.

Let $M$ and $N$ be TMs that recognize $A$ and $B$, respectively.
Construct an enumerator $E$ that behaves as follows:

For each $s_i \in \Sigma^*$ (in lexicographic order):
Run $M$ and $N$ on $s_i$ simultaneously. It must be the case that $s_i$ is in at least one of $A$ or $B$. So, at least one machine is guaranteed to halt.
If $M$ halts, $s_i \in A$, which means certainly $s_i \not\in \overline{A} \cap B$, so print $s_i$.
If $N$ halts, $s_i \in B$, which means certainly $s_i \not\in A \cap \overline{B}$, so do not print $s_i$.

So $E$ prints at least all the strings in $A \cap \overline{B}$, and definitely does not print strings in $\overline{A} \cap B$.
$E$ enumerates a language in lexicographic order, so its language is decidable and satisfies the conditions.


What is the best way to index lookups on a 2D array of integers that is boundless in x and y? Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer).

What is the best way to index these points in order to have an optimised lookup on an arbitrary (x,y) coordinate? Is an O(1) lookup solution possible?

Hash map / Hash table (depending on the language used)

Per comments, Some reasoning why:
According to Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, the big O of hash tables is O(1) to O(N) for insert, size, and time.

So best case is O(1) solution. If you are able to control the upper and lower bounds, then you have a 'max' number that you could add and can create a table with that in mind.

If you have a 2 by 2, then you can have a table with 4 rows, where the index is the grid coordinate and the value is then the place in memory. Again, language dependent ( this may be hard to do in JS, where C would be easy)


How to write decoder for compressed stringified objects Aim: schema aware transformation.

I've written a code(in js) which can transform data {projectDetails: [ {detail : {}, id : "gwl" }], name: "amit"} into string @gwl|amit. But I'm not able to complete the decoder to transform it back.

Problem: logic to transform string back to object

In detail

Consider that following schema is given to transform data into string and back to object.

var schema = {
    type: "object",
    properties: {
        "projectDetails" : {
            type: "array",
            properties: {
                "detail" : {
                    type: "object",
                    properties: {
                        "first" : { type: "string"},
                        "last" : { type: "string"}
                    }
                },
                "id" : { type: "string"}
            }
        },
        "name" : { type: "string"}
    }
}

Consider following chars to understand the transformation;

| : boundary indicator. To separate consecutive dynamic data fields.
^ : next field(set of fields) is/are repeated array item
$ : empty value
# : missing, null, undefined field
@ : empty object or array
! : missing, null, undefined object or array
Y : True
N : False

Example: Transform

{projectDetails: [ {detail : {}, id : "gwl" }], name: "amit"}
> @gwl|amit

{projectDetails: [ {detail : {} }], name: "amit"}
> @$amit

Problem: transform string back to object

Implementation

I iterated the schema to updated every data field with possible next char may occur in transformed string to identify the boundary of current field. It can help to reduce number of comparisons while decoding.

E.g. for the field id in above schema next possible chars in transformed string can be : [$^|#].

Since this way complicate the solution, following regular expression can be used (.*?)([|^#@!YN]) to read next field always. (it returns 2 matches every time, if first match is empty just ignore it and read further.)

Challenge

> @$

For above string, my decoder fails. Why? Because this is how I transform the string back.

I read the schema.
Since projectDetails is an array type, I loop
Since array's item is of type object, I use recursion
detail is object type and since the first field value in string is @. I mark it empty
I read next field and mark it with $
I come out from the recursion.
Since there is no array separator, I read next field of the root object.
I find nothing in transformed string to read.

Note I don't want to convert transformed string into array of fields. It'll cause issue in case of big objects.(I've faced it with other project)

Found the answer.

As described in question about encoding schema, there can be multiple objects falling to same encoded string. Hence I was facing the difficulty to write the decoder.

To solve the above problem, I've added 2 more chars to know the start of the object/array;

| : boundary indicator. To separate consecutive dynamic data fields.
^ : next field(set of fields) is/are repeated array item
$ : empty value
# : missing, null, undefined field
@ : empty object or array
! : missing, null, undefined object or array
Y : True
N : False
{ : object start
[ : array start


Given this transition system, for which states are these (very basic) LTL formulas fulfilled? I missed a lot of lectures for this module due to surgery so I'm trying to teach it to myself now. This is the question I've been working on:

First of all, would I be correct in saying that the LTL formulas are b, c and e? CTL are a, d and f?

For (b) I'm guessing the answer is s1 and s3, since those are the only states with b in them.

Looking at (e), this says that the state must always contain b or a, so the answer is s1, s2, s3 and s4  (all states). Is this correct?

(c) is the one I can't get my head round. What exactly is it saying in english?

For now I'll just focus on the LTL stuff, so I just want to get b, e and c 100% correct. Any help is highly appreciated since I'm struggling a bit with this module.

Many thanks in advance!

Note that questions of the form "am I correct" are generally not acceptable on this site. Still, your question shows an effort, so here are some answers:

As for your classification to LTL/CTL - you are correct.

Let's look at (b) - it interprets to "always b", which means that in every path starting from the state, b must always hold. This is not the case for any state in the system (since every path eventually reaches s2, in which b does not hold).

As for (e) - it means that in every path, in every suffix, $bUa$ hold, so in every suffix it is true that b holds until a holds. In this system, you are correct that all states satisfy this.

(c) is perhaps easier than the other two - it reads as "next next a", and a state satisfies it if in every path from it, in two steps you will reach "a". In this system, every path gets within two steps to s2, s3, or s4, all of which have "a", so the formula holds.


Inference and Unification algorithm provided to a Unification graph of two expressions I am trying to unify two expressions given a unification algorithm $unify$ applied to the unification graph of the two expressions. However, I struggle a lot in understanding how exactly the steps of this algorithm is actually done - and my teacher failed to explain this in much detail. The following example is part of an exercise.

The two expressions I am trying to unify are:
$$list(int) * list(alpha)$$
$$alpha * beta$$

With the following unification graph:

      *         *
    /   \      / \
   /     \    /   \
 list   list /     \
  |      |  /       \
  |      | /         \
 int   alpha        beta

The algorithm is from the Dragon Book and shown below:

boolean unify(Node m, Node n) {
    s = find(m); t = find(n)
    if (s = t) then true;
    else if (nodes s and t represent the same basic type) return true;
    else if (s is an op-node with children s1 & s2 and
             t is an op-node with children t1 & t2) {
        union(s,t)
        return unify(s1,t1) and unify(s2,t2)
    }
    else if (s or t represents a variable) {
        union(s,t)
        return true;
    }
    else return false;
}

My method of approach with this algorithm yielded the following result:

(1) Union the two constructors $*$ and call unify(list,alpha) and unify(list,beta)_

(2) Since the dragon book states that a variable is a leaf node, I can use Step III to union list <- alpha, and list <- beta. This returns true in the function._

From above I have that $alpha = list(int)$ and $beta = list(alpha)$. I can then construct the unified type to be:
$$list(int) * list(list(int))$$

Can anyone verify for me if this is correct? I found the algorithm a bit tricky to understand, especially since I compare a constructor list with basic types in the (2) step.

Yes, your solution and process are correct, assuming that alpha and beta are variables. It might help to rewrite your terms in a more uniform way, e.g.

T1 = *(list(int), list(alpha))
T2 = *(alpha, beta)

Here, a term always satisfies the grammar:

Term ::= Constant
       | Variable
       | Func "(" Term+ ")"

Furthermore, it might clarify things to think of the unification process as taking a third argument: a substitution in which the two terms are to be unified. This substitution is simply an association between variables and terms, and it provides a context in which to resolve variables. Additionally, the unification process results in either a failure (if the terms do not unify in the substitution), or a substitution which both indicates success and provides a way to construct a "most general unifier".


Image registration algorithms for images with varying distances I have two cameras side by side. I'd like to register two images taken from each camera. I think global transformation will not work for this issue since changes of distances between two images for the closer objects are significantly higher. What should I do in this case? I tried to read some papers but I am not sure which one is the perfect match for me. Do you have any suggestions such as "read this paper", "apply this algorithm", "know this and that" etc.

edit: I forgot to say that the project is real-time. Image registration will be implemented in the GPU.

Since you need to implement image registration for real-time your should have fast registration algorithm, such as differential total variation (DTV) or binary gradient angle descriptor. However, these methods implement for challenge dataset or multimodal in consideration of your images are mono-modal meanwhile these methods should work perfectly in your case.

Your algorithm should include these steps:

Image descriptor to extract the images features.
Feature selection: find the most similar features (this step is important to remove outliers which is common)
Minimise the distance between the related image features to get the optimal transformation.
Apply image transformation on the floating image.


Mathematical equivalent of reduce()? filter() in functional programming can be thought of as being analogous to an equation that filters the range of the variable.

map() can be through of as a function mapping domain to codomain.

reduce() is the only one I have a problem with. To me it just seems to be a special instance of map / function, where $R^{n} \rightarrow R^{1}$.

Is there a unique general mathematical concept / object associated with reduce()?

Map
applies a unary function to each element in the sequence and returns a new sequence containing the results, in the same order

$$\mathrm{map}\colon (E\to F) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle F\rangle\,.$$

Filter tests each element with a unary predicate. Elements that satisfy the predicate are kept; those that don’t are removed.

$$\mathrm{filter}\colon (E \rightarrow \mathrm{boolean}) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle E\rangle\,.$$

Reduce combines the elements of the sequence together, using a binary function. In addition to the function and the list, it also takes an initial value that initializes the reduction, and that ends up being the return value if the list is empty.

$$\mathrm{reduce}\colon (F \times E \rightarrow F) \times \mathrm{Seq}\langle E\rangle \times F \rightarrow F\,.$$

Example:

\begin{align*}
\mathrm{result}_0 &= \mathrm{init} \\
\mathrm{result}_1 &= f(\mathrm{result}_0, \mathrm{list}[0]) \\
\mathrm{result}_2 &= f(\mathrm{result}_1, \mathrm{list}[1]) \\
&\ \ \vdots\\
\mathrm{result}_n &= f(\mathrm{result}_{n-1}, \mathrm{list}[n-1])
\end{align*}

Hence you can see it as a function $\mathbb{R}^n \rightarrow \mathbb{R}$

Source: http://web.mit.edu/6.005/www/fa15/classes/25-map-filter-reduce/


Checkers algorithm - find the best last move in the game given the positions of all pieces This is the FinalTurn task of the Manganum 2017 challenge.
This is the problem and I need to solve it in a timely and performance-efficient manner, which I have not been able to do so far:

  A checker game on an infinite board between players A and B is in progress. There are two types of pieces in checkers: pawns and queens. Pieces can move only diagonally and forward. A  queen can move any number of steps in one of these two directions. If there is a piece belonging to player B on the line of player A's queen's movement, player A can beat it by leaping over it and optionally passing some more empty fields. Player A can beat only one of player B's pieces in one move. After beating one of player B's pieces in this way, player A can continue his turn and make another move, but only if he can beat another piece. Player A gains 1 point for beating a pawn and 10 points for beating a queen. Player A is left with his last piece: a queen. Now it is A's turn − the last turn in the game. Player A wants to know the maximum number of points he can score in a single turn. Can you help?

  $T is a string of N characters with pieces values. "p" and "q" represent player B's pawn and queen, and "X" represents player A's queen. Arrays $X and $Y are the x and y coordinates of pieces.

  For example, given:

$X = [3, 5, 1, 6];
$Y = [1, 3, 3, 8];

  $T = "Xpqp";

  the function should return 10

Do you know a good DP (dynamic programming) algorithm that would find the solution for the problem efficiently? In my solution:
-I used the buffer for already found maximum possible scores for individual fields, so I don't do double checks.
-Also, I put all enemy (player B) pieces in a two dimensional array, for easier detection if there is enemy piece on a certain field (if [x][y] is not set, then there isn't).
-I am doing the check for each field that it didn't cross the border of no possibility of getting any more points (no more pieces to be beaten beyond this point), so there are three borderlines:
a) one that limits the height (if we are on the same level as the highest enemy piece, no use checking if any more can be beaten, because there isn't)
b) two borders that are left and right diagonal that form the imagined border angle.
Despite this, I only got 46% on the assessment online test.

Some hints since I can't comment: I'd suggest trying to rotate the board by 45 degrees. Then your problem essentially reduces to your queen going right/upwards. The rest can then be solved with Segment Tree or Treap.


How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge? Here is the problem:

Input:

A series of source/sink nodes at fixed positions with given outwards/inwards flow
Edges are NOT specified. The edges can connect any nodes.
The  total source and sink flow match
A concave cost function that gives a cost per edge in terms of flow capacity

Expected output:

The minimum costing graph (not necessarily fully connected) that connects all sources to sinks and permits the required flow, without creating extra nodes.

Therefore the network topology is unspecified and should be optimized.

Many thanks.

Your problem is $\rm NP$-hard by a reduction from the minimum-weight Steiner tree problem.

Let $G=(V,E;w)$ be a graph with non-negative edge weights $w(e)$, $e \in E$, and let $S \subseteq V $ be a non-empty set of terminal vertices.

The vertex set in your problem will coincide with $V$. Choose the concave function $c_e(x)$  that describes the cost of sending $x$ units of flow across edge $e$ as $c_e(x) = w(e)$.
Pick an arbitrary terminal $s \in S$ and make it a source with supply $|S|-1$.
Make every vertex in $S \setminus \{ s \}$ a sink with demand $1$.

There is a Steiner tree $T$ of cost at most $k$ if and only if your problem admits a flow of cost at most $k$.

$\Rightarrow$) $s$ send one unit of flow to each vertex $v \in S \setminus \{ s \}$ using the unique path in $T$ between $s$ and $v$.

$\Leftarrow$) Consider the subgraph $H$ of $G$ induced by the set of edges traversed by non-zero flow. Since $H$ contains at least one path from $s$ to each vertex in $S \setminus \{ s \}$, it must have a connected component $C$ that spans all the vertices in $S$. Let $T$ be an arbitrary spanning tree of $C$. The cost of $T$ w.r.t. $w$ is exactly the contribution of the edges in $T$ to the cost of the flow. By our choice of the concave functions, this is upper bounded by the cost of the flow itself.

Notice that, by suitably subtracting epsilons from the cost functions, you can adapt this reduction to work for strictly concave functions. In this case it is convenient to relate  a flow of cost at most $k$ to Steiner tree of cost at most $\lceil k \rceil$.


What runtime complexity if DNF formula not PAC-learnable, $O(2^N)$ or $O(2^{2^N})$ runtime? Valiant's theory of PAC learning looks at the tradeoff between expected error and algorithm runtime in different classes of learning problems.  In particular, a lot of his analysis focuses on which classes of disjunctive normal form (DNF) formulae are learnable in polynomial time while minimizing expected error (PAC learnable).

However, many classes of DNF formulae are not PAC learnable.  This means that learning takes an exponential amount of time based on the number of variables $N$ in the formula, i.e. the algorithm runtime is $O(2^N)$.

I assume that the DNF formula that is learned in this case is not the minimal DNF formula, since it is NP-Hard to do so, meaning the complexity is $O(2^{2^N})$.

If so, then this is confusing to me.

Say there are $2^{10}-5$ samples from $f$, and the algorithm has to predict the remaining 5 bits.  If my understanding of PAC learning is correct, there is an algorithm that should be able to accurately predict the 5 bits in $O(2^N)$ time.

However, it also seems to me that to accurately predict the 5 bits the algorithm has to figure out which of the $2^{5}$ different ways of filling in the bits has the shortest DNF formula, due to Occam's razor.  But, if the algorithm has to figure out the shortest DNF formula in each of the $2^5$ permutations, then it has to perform logic minimization, which has a runtime of $O(2^{2^N})$.  Then, that means that if a DNF formula is not PAC learnable, its runtime is super-exponential, not exponential.

So, which is it?  Does a DNF being not PAC learnable mean the algorithm's runtime is $O(2^N)$ or $O(2^{2^N})$?

There's a misconception here.  PAC learning doesn't require the learning to find the shortest formula.  It merely requires the learner to find any formula that has sufficiently low generalization error.  If there are multiple formulas that meet that criteria, the learner is allowed to output any of them -- not necessarily the shortest.

Take a closer look at the formal definition, and hopefully you'll see how that follows from the definition.


Why is this argument for $P\neq NP$ wrong? I know its silly, but i managed to confuse myself and i need help settling this

Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the
fact that there exists some oracle $A$ for which $P^A\neq NP^A$, hence $P\neq NP$

Whats wrong?
Thanks!

Sure, you just have to be careful thinking about what it means to have an oracle.

The problem comes from an annoying abuse of notation we use in CS: In the statement $P=NP$, $P$ refers to a set of languages. But in the statement $P^A = NP^A$, $P$ refers to a class of Turing Machines (determinstic polytime TMs). You should think of these two $P$s as of completely different types.

So even if the two sets of languages $P$ and $NP$ are the same, deterministic polytime TMs still do not work in the same way as nondeterministic ones. In particular, given an oracle, a nondeterministic TM can "ask many questions at once", which is something the regular TM cannot do. So even if they decide the same set of languages when neither type of machine is given additional help, the oracle might help one type of machine more than another.


How to find a Deterministic PDA for an intersection of languages There are two languages,

$\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and
$\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$

where $N_a$ means the number of occurrences of $a$ in the string $w$. Same for $N_b$.

I've proved that $L_1$ has a DPDA (hope this is right).

Now I want to know whether $L=L_1\cap L_2$ has a DPDA or not.

I applied the Pumping lemma but it seems like there is no contradiction. I tried to draw the DPDA but failed. Maybe $L$ has a nondeterministic PDA but not a DPDA. However I cannot prove this.

Could anyone give me some hints?

Your conjecture is right. $L$ is context-free, but not deterministic context-free.

To see that it is context-free, take a repaired verion of the grammar from @Raphael's comment: $S \rightarrow aSbS ~|~ bSaS ~|~ aSbSbS ~|~ bSaSbS ~|~ bSbSaS ~|~ \epsilon$.

Now, assume there is a DPDA $A$ that accepts $L$, and consider words of the form $b^na^m$.

Since the set of suffixes that complete $b^n$ to a word in $L$ differs for each $n$ and $A$ is a DPDA, we can conclude that after reading $b^n$, $n$ larger than some threshold $n_0$, $A$ will be in a state $q_n$ with stack contents of the form $\gamma' \gamma^{i_n} \gamma_n$ and the size of all $\gamma_n$ is bounded by a constant.

Now we group the numbers $n>n_0$ into equivalence classes, based on $q_n$ and $\gamma_n$. Since there are only finitely many equivalence classes, at least one of the equivalence classes wil contain infinitely many values. In the following, we only consider values from this equivalence class $C$.

Now assume, there is $n_1 \in C$, so that when reading $a^{n_1}$ $A$ will go from stack $\gamma'\gamma^{i_{n_1}}\gamma_{n}$ and state $q_n$ to stack $\gamma'\gamma\gamma_{n_1}'$ and state $q_{n_1}'$ without looking at $\gamma'$. Since $b^{n_1}a^{n_1}\in L$, $q_{n_1}$ is accepting. However, since $A$ did not look at $\gamma'$, it will perform the same computation, if it starts reading $a^{n_1}$ with stack contents $\gamma'\gamma^{i_{n_2}}\gamma_n$, $i_{n_2}>i_{n_1}$. By the infiniteness of $C$, it contains $n_2>n_1$ with $i_{n_2}>i_{n_1}$. Thus $A$ would accept $b^{n_2}a^{n_1} \notin L$. So, such an $n_1$ can not be in $C$.

From the previous observation, we can conclude that for each $n_i\in C$ there is a value $n_i'<n_i$, so that after reading $b^{n_i}a^{n_i'}$, $A$ is in a state $q_{n_i}'$ and $A$'s stack contains $\gamma'$. Since $C$ contains infinitely many values $n_i$, we can find $n_1<n_2\in C$ so that $q_{n_1}' = q_{n_2}'$. Now we distinguish 2 cases:

If $n_1-n_1' > n_2-n_2'$, $b^{n_1}a^{n_1'+(n_2-n_2')} \notin L$, but since $A$ can not distinguish, if it has read $b^{n_1}a^{n_1'}$ or $b^{n_2}a^{n_2'}$ and $b^{n_2}a^{n_2'+(n_2-n_2')} \in L$, $A$ can not handle both words correctly.
If $n_1-n_1' \leq n_2-n_2'$, $b^{n_1}a^{n_1'+(n_2-n_2')+n_2} \notin L$, while $b^{n_2}a^{n_2'+(n_2-n_2')+n_2} \in L$, and as in the other case $A$ can not distinguish them.

Thus, such an $A$ can not exist.


Proof by Turing Reduction I need to proof the following by turing reduction.

Given two languages:

$Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$

$I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$

Where $\langle M_1 \rangle$ is the encoding of Turing Machine $M_1$.

I need to show that $ I \le_T Q $ ($I$ can be reduced to $Q$ using a Turing Machine).

So far I came up with the following idea, which I think isn't correct.

Create Turing Machine $M'$ so that a mapping from $Q$ to $I$ is found:

$M'$ takes as input a random word $u$ for example $aab$
$M'$ removes the input ($u$) from its tape
$M'$ guesses words $v$ and $w$
$M'$ checks if $v \in L(M_1)$ and $ w \in L(M_2)$ if and only if $v = w$

Your solution doesn't quite make sense for many reasons:

The reduction should take $\langle M \rangle$ as input, and using an oracle to $Q$, decide whether $\langle M \rangle \in I$.
The reduction should be deterministic (so step 3 is invalid).
The function of the arbitrary word $u$ is not explained; indeed, steps 1 and 2 seem useless.
You don't explain what $M_1,M_2$ are in step 4 (are you trying to reduce from $Q$ to $I$?).
You don't explain how to implement step 4.

Also, you are missing a proof that your reduction works. Without a proof, your solution is wrong even if it could be completed to a correct solution.

One solution goes along the following lines (I'm assuming $L(M)$ consists of all inputs on which $M$ halts; I also say that $n \in L(M)$ is accepted by $M$):

Given $M$, let $M'$ be the machine that on input $n$, simulates $M$ on $n$, and then (if $M$ halted) tries to find an $m > n$ accepted by $M$ (if there is no such $M$, it never halts); you can implement this using the technique of dovetailing.
Give $M$ and $M'$ to the $Q$ oracle, and return its answer.

The idea is that $L(M)$ is infinite iff $L(M) = L(M')$. I'll leave you the details.


How to prove that sequences of stack operations are not context-free By stack I mean the language of sequences it represents, say, a stack with data domains $N$ (natural number) is: $\{ \mbox{push(0)}, \mbox{push(1)}, \mbox{push(0).push(1)}, ..., \mbox{push(0).pop(0)}, ...\}$.

This language is not against Pump lemma of CFL, right ? But I read from some materials that this language is NOT context-free. So why is that ?

The language is context-free. If we replace $\mathrm{push}(k)$ by $[_k$ and $\mathrm{pop}(k)$ by $]_k$ and delete the dots, then we get exactly all prefixes of a Dyck language with $N$ different types of brackets.


How to find a path that connects all the dots in the matrix? I have a matrix that consists of 0, 1, 2.

0 - dot.
1 - block.
2 - start dot (initial position in the path).

I have to create a path from the start dot, that

connects all the dots in the matrix and
visits each dot ONE time
doesn't visit blocks

In other words, create a Hamiltonian path in a matrix.
A pic below exhaustively shows what I want.

The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach.

A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a genetic algorithm, ant colony optimization, or some more problem specific heuristic.

[1] Papadimitriou, Christos H., and Umesh V. Vazirani. "On two geometric problems related to the travelling salesman problem." Journal of Algorithms 5.2 (1984): 231-246.


Chomsky or Greibach Normal Form? I tried to solve this exercise:

Discuss the normal forms (CNF or GNF) of a grammar with productions:

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | \epsilon$

Same request with the following grammar:

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | c$

I applied the rules to convert a grammar into its normal form and I think that both are CNFs.

For the first grammar:

$S\rightarrow BC | CB|C'B|c$

$B\rightarrow C'B | c$

$C\rightarrow C'C | c$

$C'\rightarrow c$

For the second grammar:

$S\rightarrow BC | CB|TB|c$

$B\rightarrow TB | c$

$C\rightarrow TC | c$

$T\rightarrow c$

Is that correct?

A context-free grammar is in Chomsky normal form if all productions are of the form $A \to BC$ (where $B,C$ are not the starting symbol), $A \to a$, or $S \to \epsilon$, where $S$ is the starting symbol. A context-free grammar is in Greibach normal form if all productions are of the form $A \to a\alpha$, where $\alpha$ consists only of non-terminals (but not the starting symbol), or $S \to \epsilon$, where $S$ is the starting symbol.

Every context-free grammar has an equivalent context-free grammar in Chomsky normal form, and another one in Greibach normal form; there could be several equivalent context-free grammars in either normal form.

When you applied the rules to convert your grammars into normal form, you got Chomsky normal form because the rules were designed for converting a given context-free grammar to Chomsky normal form. You could follow other rules and get Greibach normal form.


“In object-oriented programming, the program is organized around its data” In a description of OOP in my textbook, it is written that “in procedure oriented program the program is organized around its code while in object oriented programming, the program is organized around its data”. What is the meaning of this statement? An explanation with an example would be of great help.

procedure oriented programming means you can group some operations to finish a task when you know how to do it，step 1，step 2……
object oriented programming means you can inspect a object from two parts，its features (states or data) and its behavior in different states.


Distinguishing between side-by-side liquid streams I'm new to computer vision and am looking for advice. I'd like to perform computer vision on a spiral system, in this system a down flowing liquid separates into different regions based on density:

The regions can be visually distinguished based on colour. What I'm hoping to do is automatically detect changes in the average colour of each region, width of each region and perhaps total breakdown of regions.

Could you please suggest which techniques of computer vision would be best for this type of analysis? and would you suggest an approach using Matlab or python + library (any)?

I would suggest looking into standard methods for image processing.  You could use the Hough transform to detect circles.  You could potentially use morphological transforms and the watershed algorithm to smooth out and remove noise and detect boundaries between the regions.


Average codeword length in Huffman encoding at most log n I am interested in the following question:

Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords.

I'm thinking of a worst case when the full binary tree (generated by Huffman's algorithm) has height $n-2$, but I still have to take the letter frequency into account, and I am stuck.
(Also I observed that the letter frequency shrinks by a factor of two when traversing down the tree.)

Huffman's algorithm is known to be optimal, that is, produce a code which minimizes the average codeword length (with respect to the input distribution).

Let us notice now that there is a code in which each codeword has length $\lceil \log n \rceil$, and in particular the average codeword length is $\lceil \log n \rceil$ (with respect to any distribution). Hence Huffman's algorithm produces a code in which the average codeword length (with respect to the input distribution) is at most $\lceil \log n \rceil$.

Here are two comments. First, we cannot replace $\lceil \log n \rceil$ with $\log n$. For example, if $n = 3$ and you consider the uniform input distribution, then the optimal average codeword length is $5/3 > \log 3$.

Second, the average codeword length is only guaranteed to be small with respect to the input distribution. For example, if the input distribution is $1/2, 1/4, 1/8, \ldots, 1/2^{n-1}, 1/2^{n-1}$ then the optimal code has codeword lengths $1,2,3,\ldots,n-1,n-1$, and so the average codeword length with respect to the uniform distribution is roughly $n/2$. The average codeword length with respect to the input distribution, however, is constant (tends to 2).


Why is word-addressable the exception, not the rule? As stated on Wikipedia:

  Most modern computers are byte-addressable

instead of word-addressable. Why is this case? Since the CPU processes words (of predominantly 64 bits or 8 bytes) now, wouldn't the word-addressable approach be more efficient?

Byte operations will always be important because a lot of a modern workload involves bytes. Text processing and bytecode interpretation (including emulation of other CPUs) are obvious examples, but also device drivers often need to be able to manipulate bytes efficiently.

Byte-addressed memory can be emulated with word-addressed memory and a reasonable assortment of bit manipulation instructions, however this means that you need more instructions to do the same thing, and those instructions have long chains of data dependencies between them.

RAM is reasonably cheap, but the instruction pipeline in a modern CPU is not.

Every so often, ISA designers reason that byte and short word load/store instructions aren't that important. Within two revisions, those instructions inevitably get added. This was the case with MIPS and Alpha, for example. Code density, it turns out, is quite important.

Note that this isn't true of arithmetic and logic operations. Given a sufficient number of registers (which, I might add, 32-bit x86 and earlier did not have), there doesn't seem to be any gain in implementing byte and short-word arithmetic and logic instructions. Well, for non-vectored instructions, anyway.


What is the shortest superstring for $\{c (ab)^k, (ba)^k, (ab)^k c\}$? In this paper on PDF page 3, they give $\{c (ab)^k, (ba)^k, (ab)^k c\}$ as an example of an input to the GREEDY algorithm for shortest superstring that causes it to have an approximation ratio of 2.

As far as I can tell, the shortest superstring of that set is either $c (ab)^k c (ba)^k$ or $b (ab)^k c (ab)^k$ -- either way, the length is $4k + 2$. Unfortunately, this contradicts the claim in the paper that GREEDY outputs a string of length 2 times the optimal superstring.

Without loss of generality, we can assume that GREEDY will never output a string longer than the concatenation of its input set -- if the GREEDY algorithm really is described in that way, we can just add an if statement to check that case and return the concatenation instead.
The length of the concatenation of the input strings is $6k + 2$.
For all $k \in \mathbb{N}$, $1 \le \frac{6k + 2}{4k + 2} \le 1.5$
Therefore either the approximation ratio for any reasonable algorithm on this class of problems must be less than or equal to 1.5, or what I think is the shortest superstring is not actually the shortest one.

Can someone either explain why this line of argumentation doesn't work, or say what the actual shortest superstring of this set is?

A shorter superstring is $c(ab)^{k+1}c$, which has length $2k+4$.


Can a recursive language be uncountable? Does there exist a recursive language $L$ whose cardinality is uncountable?

I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to reject the initial question.

Languages are collections of words. Words are finite strings.

As Shaull stated in his comment, every language over a finite alphabet is countable. (In fact, every language over a countable alphabet is also countable.)

Languages of infinite words, sometimes called $\omega$-languages, are considered in computer science. For example, they are the subject of $\omega$-automata theory. But the Turing machine formalism is about the usual notion of language.


red black tree and 2-3-4 tree isomorphism Are all cases of addition and removal in 2-3-4 trees isomorphic to cases of addition and removal in red black trees?

It depends what you mean by isomorphic. Indeed a black node with its (zero, one or two) children corresponds to a 2-3-4 node (with 1,2,3 keys and 2,3,4 children). The basic operations on the two types of trees are really different but translate quite well.

There is a single difference in symmetry: there is only one type of 3-node (2 keys, 3 children), whereas in a red-black tree the red child to the black node may be at the left or right side.


Searching the space of permutations I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I don't know which one. An oracle however knows the true permutation. To find the true permutation, I'm allowed to query the oracle for pairwise comparison between 2 objects (is a before b in the true permutation?).

A naive strategy would be to do a binary search (ask the "right" pairwise comparison question that eliminates half the permutations at every stage), to find the true permutation in log n steps. My question is, can this always be done? Or can I find an adversarial set of permutations such that O(log n) queries aren't enough.

Edit:
Example: Say my objects are 1,2,3,4. The set of permutations is {1243, 2341, 1342, 3412}. I don't know the true permutation. I ask "Is 2 before 4 in the true permutation?". The oracle returns yes. So I know its among the first two permutations. I then ask "Is 1 before 3 in the true permutation?" to find the true permutation.

Consider the following set of $n$ orders, which I give for $n = 6$:
$$
123456 \\
213456 \\
132456 \\
124356 \\
123546 \\
123465
$$
Hopefully the generalization to arbitrary $n$ is clear.

If you never compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an argument, but it can be converted to one); this is tight (for this example).

Let me also mention two well-known papers in the area:

Fredman showed that if there are $\Gamma$ many possible orderings, then you can find the correct one using $\log_2 \Gamma + 2n$ queries.
Kahn and Kim showed that if the potential orderings constitute all possible orderings extending some partial order, then $O(\log \Gamma)$ queries suffice.


Upper bounds for a binomial coefficient I have an algorithm with worst-case time complexity in  $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $.
I need an argument which shows that the runtime complexity is solely a function of its parameter $k$, i.e. that the input size $p$ does not matter for runtime complexity.
My own argument goes as follows:
$$ \binom{k}{p-1} = \frac{k!}{(p-1)!(k-(p-1))!} \leq k!$$
Where the first equality follows from the definition of the binomial coefficient and the second inequality follows from the observation that both  $(p-1)!$ and $(k-(p-1))!$ are greater than or equal to $1$.
Thus the algorithm runs in $\mathcal O (k!)$, which is a not a function of $p$ as required.
Is this argument correct or am I missing something?
Maybe I am overcomplicating things and there is a faster / better argument?

The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows:
$$
\binom{k}{p-1} \le \sum_{i=0}^{k} \binom{k}{i} = 2^k
$$
Where the equality $\sum_{i=0}^{k} \binom{k}{i} = 2^k$ follows from the fact that the summation on the left is counting the number of possible subsets of a set with $k$ elements, grouped by cardinality: the $i$-th term of the sum (for $i=0, \dots, k$) is the number of subsets with exactly $i$ elements.
Also, using Stirling's approximation and assuming that $k$ is even (this is just for convenience, if it's not you can consider $k+1$ instead to get the same asymptotic bound):
$$
\binom{k}{p-1}  \le \binom{k}{k/2} = O\left( \frac{ (k/e)^k \sqrt{k} }{ k (k/2e)^k } \right) =
O\left(\frac{2^k}{\sqrt{k}} \right).
$$


Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment.

  $\text{Suppose that } \{ a^nb^n : n \ge 1 \} \text{ is non-regular.}$
  $\text{Prove using closure results that } \{ 0^i10^i : i \ge 1 \} \text{ is non-regular.}$

Starting off I assumed for contradiction that the language is regular. Then I took countlessly many compliments and intersections and homomorphisms, none leading me anywhere close.

I understand using Pumping Lemma would quickly solve this problem, but the question restricts the proof technique to not using Pumping Lemma.

How would one go about solving such a question with the given restraints? Is there a methodology as to find the correct closure results to use or is it mostly intuition and luck?

I would say that luck and intuition are improved by experience :)

The trick is also to use inverse morphisms! They can perform nondeterministic letter substitutions.

A related example.
Consider the morphism $h: \{a,b\}^*\to \{0\}^*$  with $h(a) = h(b) = 0$, then $h^{-1}$ maps a word $0^n$ to any string $w\in\{a,b\}^*$ with length $n$.

Background. It is easy to write a FSA with output that maps strings $0^i10^j$ to strings $a^ib^j$, and regular languages are closed under finite state transductions (input-output transformation by two-tape finite state automaton). If you are not familiar with this result, by Nivat's Theorem: any finite state transduction can be written as a composition of an inverse morphism, intersection with regular language, and a morphism.


Term for size of maximum independent set An independent set is a set of vertices in a graph, no two of which are adjacent.

A maximum independent set is a largest independent set for a given graph G.

Is there a standard term for the size of the largest independent set in a given graph?

If not, what short term can you suggest for this size? Maybe "independence number"?

Yes, it's called the independence number and it's usually denoted $\alpha(G)$.


Topics from theoretical computer science suitable for a bachelor (undergrate) thesis? Is the field of theoretical computer science so complex, that it is just "too much" for a bachelor thesis? Unfortunately I haven't found any old thesises because the relevant chair of the university hasn't been occupied for years.

Because of theoretical computer science is the only topic that really interests me, I thought of writing my bachelor thesis in this field. What would be suitable topics or at least fields that can be arranged in the limited focus of a bachelor thesis? I thought of topics like parametrized complexity or formal software verfication (which is actually a bit of the target)

As a bachelor student that is writing his thesis in that field I can guarantee you there are a lot of topics suitable for a bachelors degree.
Personally, I am working on graphs and some specific algorithmic problems over those.
I suggest you ask your professors if they have some topics for you.
At my university usually professors have a list of "problems" and we can either choose between one of those or propose our own topic.
Obviously because it is "just" a bachelor thesis you'll have to be specific and concentrate on some smaller problems e.g.

Formal verifiation of smaller programs in some specific language (like haskel)
Finding some polynomial algorithm to a specific problem that hasn't been researched too much. (Also, if you can't find anything new, explaining why the problem is "complex" can also be a good plan b)
Testing of specific cryptographic protocols under specific assumptions (allowing the attacker to have some specific information etc..)


Meaning / proof of these regex I came across following excerpts while reading about regular expressions identities:

  The regex associative laws are:
  $$(L+M)+N=L+(M+N)$$
  $$(LM)N=L(MN)$$
  Some important implications out of associative laws are:
  $$r(sr)^*=(rs)^*r$$
  $$(rs+r)^*r=r(sr+r)^*$$
  $$s(rs+s)^*r=(sr+s)^*sr$$
  $$(LM)^*N*\neq L*(MN)*$$

The issue is that

I don't find the implications much intuitive as the identities themselves are. How can I understand the implications intuitively? I can always form a strings belonging to left hand side regex and check whether it can be accepted by other regex. The first implication is very simple to test this way. However how can I make them more intuitive??
Are these implications simply made up expressions which are tested rigorously to hold true and they don't have any specific expression as we can form many such expressions?
I am unable to get the point behind stating these implications. I dont think of any problem in which I can use these regexes straight / immediately. It may be because I am not able to get intuition behind these implications so that it may strike in my head immediately when to use these implications.

For all three of your statements, the answer is that, generally speaking, the implications simply aren't as intuitive as, say, the associative laws. Look at the analogous problem with algebraic expressions: we have associative laws for addition and multiplication and we also have a distributive law that states that for any expressions $p,q,r$ we have
$$
p\cdot(q+r)=(p\cdot q)+(p\cdot r)
$$
Eventually, these rules should be intuitively obvious. However, one implication of these rules, that
$$
(p+q)^3=p^3+3p^2q+3pq^2+q^3
$$
is probably not as intuitively obvious as the rules used to derive that identity. The utility of the result above is that it can be used as a tool to simplify other more complicated problems.

It's the same for regular expressions: the fact that, say, $r(sr)^*=(rs)^*r$, is correct can be proven rigorously, but having done that you can use it as a tool to show that
$$
aa+(aab)^*aa=aa+aa(baa)^*=aa(\epsilon+(baa)^*)
$$
should you ever need to. For example, there is a handy technique, involving what's known as Arden's lemma that can be used to produce a regular expression describing the language accepted by a finite automaton. Depending on how it's applied, this can produce several regular expressions from the same FA, so it might fall to you to show that the expressions are indeed equivalent, in which case the "implications" you listed might be handy.

The upshot (here's the tl;dr part), is that the implications you mentioned are simply tools you can use when needed: they've beed proven to hold, but there's no reason why they should be intuitively obvious.


Can two free variables in lambda calculus have different values? I am studying lambda calculus for the first time and I was trying to do the reduction beta of the lambda term $(\lambda x.xy)y$. Can I assume that these two free variables $y$ are the same? Or do I need to rename the rightmost $y$?

$y$ is free in the term you have given, so it is indeed the same variable.

You would not have the same variable in case $y$ was bound by the lambda. That would be the case, for example, if the term were to be $(\lambda y.xy)y$; then the rightmost $y$ would be free, but the one in $xy$ would be bound by lambda and, hence, a different variable.


Can I use machine learning to predict someone will buy something in a specific time? I have a dataset which has timestamp and goods variable for an object like the following example:

On Moday, John bought Beer, chicken, pizza.
On Tuesday, John bought pizza, pork and beef.
On Wednesday, John bought beer, coke and Vegetable

Can I use machine learning to predict what good will he buy in a specific time and what model can be applied?

Can we answer the question: "What will he buy on Thursday?"

Short answer:
Yes it can be done using machine learning if you have  features with sufficient information.
Long answer:
You can model this either as a multilabel problem (i.e Beer, chicken, pizza are multiple labels [non mutually exclusive] for the same data point) or as a multiclass problem (by creating a combination like "Beer, chicken, pizza". In the multiclass case the labels would be mutually exclusive). You can use day of the week, name of person and some other attributes as features (aka predictors) for the model.
For a more detailed answer you'd need to tell us what you have already tried out so that the community can help you.
Also, see this   related question.


Good data structure for finding all points in one set a distance from each point in another set Let $X$ and $Y$ be two sets of points in $\mathbb{R}^3$. Assume that the cardinality of $Y$ is larger (much larger if you want) than $X$.   For each $x_i \in X$, I need to find all $y \in Y$ such that the distance between $x_i$ and $y$ is less than a (fixed) radius $R$. That is, for each $x_i$, I want the set $E_i = \{y \in Y: \|x_i-y\|\ \leq R\}$.

Now this looks to me like a nearest-neighbors type problem just with two different sets of points. If I'm correct, usually something like an R-tree or kd-tree is good for finding nearest neighbors within a single set $X$. But this seems a bit different. I could naively just iterate through $X$ and find the $y_j \in Y$ such that $\|x_i-y_j\| \leq R.$ and I suppose store that in a gigantic array, but this seems like the worst possible method. On the bright side, this is at least embarassingly parallel so there is that at least.

Any suggestions would be greatly appreciated and I apologize if this is a trivial question (I'm not a computer scientist!) Also, if this is the incorrect place to ask such a question, please let me know. If the question is unclear or requires additional information, just let me know. Thanks!

Sort the big set $Y$ into a regular grid, then for any query point $x_i,$ find its cell and you only have to check the adjacent cells to determine $E_i$ very quickly. For sorting, indeed, some parallel algorithms are faster than others, see this poster for an overview and example of using fast GPU radix and count sort.


Complexity of recursive solution to coin change How do you go about analysing coin change recursive solution. i.e,
T(N,K) = T(N,K-1) + T(N-1,K) for K denominations that add up to amount N.

You can find the problem description and pseudo code here - http://www.algorithmist.com/index.php/Coin_Change#Recursive_Formulation

A general method for solving recurrences of this form is generating functions. The exact solution also depends on the initial values. In your case, one possible solution is $T(n,k) = C 2^{n+k}$.