Where in the toolchain does formal specification come in? Where is the formal spec located?
Like this?

Are tests made from formal or informal spec?
I saw a project where they where generated from a the formal
spec and that never made sense to me.

Is the verification step manual or can it be automated?

If it is manual, we now have 3 things to maintain and keep in sync.
The problem of a possible mismatch between informal spec and code has just been moved
between the informal and the formal spec. What did we gain?

If the verification step can be automated completely then
why write any code at all? Just let it be generated from the spec automatically.
If we fold those two steps into one the situation is the same as
before; we have a high level description of our problem which a compiler
turns into a low level representation that can be executed by a machine.
What did we gain?

Tests can be written based on either a formal spec or an informal spec.

Verification always requires a formal specification.  Formal verification might be manual or automated, or some combination of the two; it depends what techniques you use.  Typically, it's hard to do completely automatic verification -- it's more usual that verification systems automate part of the verification task, but require some assistance from the programmer (e.g., to specify invariants or prove lemmas that are hard for the automated system to prove).  See https://en.wikipedia.org/wiki/Formal_verification for an overview; there are also textbooks that give an overview of formal verification.  I suggest reading some standard references on formal verification: they will probably answer a lot of questions you might have.

There's nothing that says you have to have an informal spec, a formal spec, and a program.  You could have just a formal spec and a program.

It is often helpful to have specifications at multiple levels of abstraction/granularity, with theorems relating them.  Higher-level specs may be easier to understand and specify properties about the whole system or properties we ultimately care about, but may be difficult to prove directly; lower-level specs may be more detailed and harder to work with or understand, but may have a more direct mapping to the program and might facilitate proof/verification.

Higher-level specs might be formal, or in some cases they might be less formal.


Determine when Strassen's algorithm for matrix multiplication is better than regular MM I'm trying to find out how to determine the size of the matrices $n$ such that Strassen's algorithm for matrix multiplication is better than the regular algorithm. I know that Strassen's algorithm is $\Theta(n^{lg 7})$, and regular matrix multiplication is $\Theta(n^3)$.

My reasoning goes along the following lines:

When the size of the matrices to be multiplied is $2x2$, Strassen's algorithm carries out 7 multiplications and 24 additions, whereas the regular multiplication requires 8 multiplications and 4 additions.

So I can do something like this, by the definition of the $\Theta$ notation

\begin{align}
31 &= c_1 2^{lg 7} \\
31/7& = c_1
\end{align}

Using a similar reasoning,

\begin{align}
12 &= c_22^{lg 8} \\
12/8 &= c_2 \\
3/2 &= c_2
\end{align}

If this is valid, having determined the constants all that remains is to set the equalities using these constants, and solve for $n$.

I would just like to know if my train of thought is correct, and if it isn't, how to go about finding the size of the matrix $n$ such that Strassen's algorithm is better. I know this might depend on specific implementations of hardware, architecture and so on, but the divide and conquer approach doesn't necessarily have to be used until the algorithm reaches the base case $2x2$. I want to know when to switch to another algoritm, which in this case is the regular matrix multiplication.

If you look at the number of operations, it's obvious that you would do a matrix multiplication using the smallest number of operations. For 2x2 the direct method is best. You calculate for 3x3, 4x4, 5x5 etc. how many operations you need using the direct method, and how many you need using the Strassen method, performing (n/2) x (n/2) products using the fastest method.

If you look at execution time, that is dependent on the computer where you run it, so the point where Strassen is better also depends on the implementation. You would do the same thing as above, but instead of calculating the number of calculations, measure the execution time.


Time complexity in Big O notation for Harmonic series with first k terms missing Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration.

Thanks to the well known $O(\log n)$ upper bound for the Harmonic series, the big $O$ notation of this algorithm comes to $O(n^2 \log n)$.

Now the actual algorithm that I am working on iterates from $k$ to $n$, where $1 < k < n$, spending $\frac{n^2}{k}$ in the first iteration, then $\frac{n^2}{k+1}$, $\frac{n^2}{k+2}$, $\frac{n^2}{k+3}$, and so on.

I've been trying to deduce the upper bound of this new algorithm, but I keep getting the same $O(n^2 \log n)$ time bound, which to me, is counter intuitive and a bit paradoxical, especially considering that the first terms of the harmonic series are the bigger and more significant terms. The time bound that I was actually expecting to get was $O(\frac{n^2}{k} \cdot \log n)$.

Could anyone please be able to shed some light onto this?

Thanks in advance for any help.

We can estimate your sum using an integral:
$$ \int_k^{n+1} \frac{dx}{x} \leq \sum_{i=k}^n \frac{1}{i} \leq \int_{k-1}^n \frac{dx}{x}. $$
Evaluating the integrals, we obtain
$$ \log \frac{n+1}{k} \leq \sum_{i=k}^n \frac{1}{i} \leq \log \frac{n}{k-1}. $$
We can conclude that for $k \geq 2$,
$$ \sum_{i=k}^n \frac{1}{i} = \log \frac{n}{k} \pm O(1). $$


Karatsuba Multiplication Rule in dividing a Number in two parts In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example:

x= 1234
y= 2456

Then a = 12, b = 34, c = 24 , d = 56

What if the digits in each number are not even, or the same? What is the rule in dividing it into two parts?

Example:

 x = 12345
 y = 2478

or

 x = 12456778
 y = 241

Please help.

The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for

x = 12345
y = 2478

you would get a=12, b=345, c=2, d=478. Since the number of digits in x is not even, we are free to choose whether to split into a=12 and b=345 or a=123 and b=45; it makes no difference to the running time. For your second example

x = 12456778
y = 241

you would get a=1245, b=6778, c=0, d=241.


Virtual Memory vs Cache for block identification Both are based on the principle of locality. Then why virtual memory uses table lookup while cache memory uses associative memory for block identification?

I think it's because when using virtual memory, you have access to disk and thus have vasts amounts of memory to store extra data structures than can help you identify each page. In cache, you don't have that much memory, so the way to do things is to add identification (tag and set) bits to each cache line so that you don't need another data structure to identify each cache block because it would be expensive memory-wise. You just iterate over each set, identify the set you're looking for, then iterate over each cache line in that set and identify the cache line you're looking for and then extract the desired bytes. Also, iterating over all cache lines is not that expensive because there aren't a lot of them, but applying this technique to pages, which can be thousands, is really inefficient.


Algorithm to create tournament brackets I'm designing a web app to host e-sports tournaments and want to create an algorithm that generates tournament brackets.

Given a list of participants' user ID's (minimum 4, maximum let's say 64), I want to generate a bracket in the form of a list of pairings, where each element of the pair represents a match participant or a reference to the winner of a previous match, i.e. User 1 vs. User 2, Winner of match 1 vs. User 3, and so on.

A simple example, given the array of entrants:

(user1, user2, user3, user4)

We get the end result as a set of pairs, in the logical order:

(user1, user2), (user3, user4), (winner0 vs winner1)

Where winner0 refers to the winner of match 0 (the first pair in the result set). Thus, the winner of the last match in the set is the winner of the tournament.

I need this to work with any size entrant list between 4 and 64 (or some other theoretical maximum), not just for powers of 2. When the entrant count is not a power of 2, some entrants must get one more or one fewer match in order to fill in the entire bracket. All initial placements will be random.

I suppose it's also possible to represent the result as a binary tree, but I'm not sure I will be able to apply it that way.

Create a new node for each entrant, then put a pointer to each such node in a FIFO queue. Remove the two pointers $p_1, p_2$ in front of the queue, then create a new node with children $p_1$ and $p_2$, and enqueue a pointer to it. Repeat until the queue size is $1$. The one element you're left with is the root of a binary tree that encodes the bracket.


Is this language regular or not? $$L = \big\{ (0^{m^2})^* \ \big \vert \ m \ge 1 \big\}\,.$$

I've given answer as regular but i am not sure. How? Please explain.

Hint. Consider $m=1$ and the question answers itself.


Writing a regular grammar for a regex of decimals So I've got the regex /[1-9][0-9]*(\.[0-9]*[1-9])?/ and I'm trying to write a regular grammar for it.

I started off like this:

S ∶≔ EAB
A ∶≔ DA | ε
B ∶≔ .AE | ε
D ∶≔ 0 | 1 |  2 | 3 |  4 | 5 |  6 | 7 |  8 | 9
E ∶≔ 1 | 2 |  3 | 4 |  5 | 6 |  7 | 8 |  9

But I realised that this does not follow Chomsky's rules for regular grammars. So I was wondering how could I adapt this logic into proper notation.

Thanks!

EDIT: So below is the NDFA generated from the regex above:

Regular grammars (of the right-regular variety) are essentially equivalent to NFAs, in the sense that they include roughly the same information. Once you convert your regular expression to an NFA, you can easily construct from it a right-regular grammar.

What doesn't seem possible is adapting your logic to construct a regular grammar. Unfortunately, there is no simple way to convert an arbitrary context-free grammar to a regular one; indeed, it is undecidable to determine whether a given context-free grammar corresponds to a regular language.


Computer architecture pipelining LOOP:LW    R1,0(R2)
     ADDI  R1,R1,#1
     SW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     BNEZ  R4, LOOP

If we want to move an instruction into a branch delay slot what will be that instruction and the schedule of the instructions?

In the solution they have brought SW R1,0(R2) into the branch delay slot like this:

LOOP:LW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     ADDI  R1,R1,#1
     BNEZ  R4, LOOP
     SW    R1,0(R2)

But according to me it will change the meaning of the program since R2 will be incremented by 4 before storing the word. Can anyone clear this?

There is an instruction already in the branch delay slot - it's just not displayed. So unless that instruction that isn't displayed is a NOP instruction, it will not be executed anymore if the branch is performed, so the meaning of the program has changed. Unless the question is "here is the code for a processor without branch delay slots, modify it for a processor with branch delay slots". In which case the obvious solution is to just move the last instruction before the conditional branch to the branch delay slot.

Independent of branch delay slot, you cannot just move the SW instruction which uses R2 past an instruction that modifies R2. In this case, you can move it if you modify it: R2 is increased by 4, so you can use the address -4(R2) instead of 0(R2).

In general, you initially don't care about branch delay slots and write code as if there were no branch delay slots, and add a NOP after each conditional branch, so you have correct code.

Then you move instructions into the branch delay slots, but carefully: You mustn't move an instruction if there is a branch to the conditional branch (because that instruction would be wrongly executed when branching to the conditional branch). You can't move certain instructions, like branches, returns, calls. And you can't move an instruction that was already moved. Say x = 0, branch if zero, not, branch if not zero, not. You can move the x = 0 into the first branch delay slot, but you mustn't move it into the second one.


Why is the minimum height of a binary tree $\log_2(n+1) - 1$? In my Java class, we are learning about complexity of different types of collections.

Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height of a binary tree is $\log_2(n+1) - 1$, but doesn't offer further explanation.

Can someone explain why?

I'm assuming that by $n$, you mean the total number of nodes in the binary tree. The height (or depth) of a binary tree is the length of the path from the root node (the node without parents) to the deepest leaf node. To make this height minimum, the tree most be fully saturated (except for the last tier) i.e. if a specific tier has nodes with children, then all nodes on the parent tier must have two children.

So a fully saturated binary tree with $4$ tiers will have $1+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$ nodes maximum and will have a depth of $3$. Thus if we have the depth of a binary tree, we can very easily find the maximum number of nodes (which occurs when the tree is fully saturated). If you recall from your algebra classes this is just a geometric series and can therefore be represented like this:

$$
\text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}.
$$

So let's rearrange:
$$
\text{nodes}=2^{\text{depth}+1}-1,
$$
then solve for the depth:
\begin{eqnarray}
\text{nodes}+1&=&2^{\text{depth}+1}\\
\log_{2}(\text{nodes}+1)&=&\log_{2}(2^{\text{depth}+1})=\text{depth}+1\\
\log_{2}(\text{nodes}+1)-1&=&\text{depth}.
\end{eqnarray}
and there's your formula. Now keep in mind this only yields integer values when the every tree is completely filled up (a 'perfect' binary tree) so if you get a non-integer value, remember to round up.


Why is NP-hard not necessarily NP? A problem X is NP-hard if every problem in NP can be reduced to X. But every problem in NP has a polynomial time verification algorithm, so then does that not mean that I can also verify X in polynomial time because every NP problem is reducible to X? Can someone please explain or give an example.

Here is an abstract definition of the concepts NP-hard and NP-complete. If $A,B$ are two decision problems, say that $A \leq B$ if there is a polytime reduction from $A$ to $B$, that is, if there exists a polytime function $f$ such that $x \in A$ iff $f(x) \in B$. Then:
$$
\begin{align*}
&\mathsf{NP\text{-}hard} = \{ B : A \leq B \text{ for all } A \in \mathsf{NP} \}, \\
&\mathsf{NP\text{-}complete} = \mathsf{NP\text{-}hard} \cap \mathsf{NP}.
\end{align*}
$$

Here is a different example. Consider the universe of all subsets of $\mathbb{N}$, ordered under $A \leq B$ if $A \subseteq B$. Let $\mathsf{X}$ consist of all subsets of some fixed set $X$. Define $\mathsf{X\text{-}hard}$ and $\mathsf{X\text{-}complete}$ just as above. You can check that
$$
\begin{align*}
&\mathsf{X\text{-}hard} = \{ S : S \supseteq X \}, \\
&\mathsf{X\text{-}complete} = \{ X \}.
\end{align*}
$$
In a similar way, NP-hardness is a lower bound on the difficulty, whereas NP-completeness is both a lower bound and an upper bound. In contrast to the second example above, there are many NP-complete problems, all of them having the same level of difficulty (two problems $A,B$ have the same level of difficulty if $A \leq B \leq A$).

Finally, here is a concrete problem which is NP-hard but not NP-complete: the halting problem.

The halting problem is NP-hard. Let $A$ be any computable decision problem, say computed by a Turing machine $M$ which always halts. Let $M'$ be the Turing machine which simulates $M$, halts if $M$ accepts, and runs into an infinite loop if $M$ rejects. Define a polytime function $f$ by $f(x) = (\langle M' \rangle,x)$. Then $x \in A$ iff $M$ accepts $x$ iff $M'$ halts on $x$ iff $f(x) \in \mathsf{HALT}$.

The halting problem is not in NP. The halting problem is not computable, and in particular not in NP.


Greedy and backtracking solutions to an arrangement problem with constraints I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class mates but they all seemed to be confused. One gave me a sample answer of code doing it, whereas another one thought he wants some sort of graph with nodes/edges to represent the answer.

  1)
  A group of $n$ teenagers $T_1,\dots,T_n$ are to sit in a single row of $n$
  chairs watching a particularly boring comedy movie. Some
  teenagers quarrel with each other all the time. The problem is
  to devise a seating arrangement for the group in such a way
  that teenagers sat next to each other do not quarrel.

  a) Propose a solution to this problem using the Backtracking
  approach. Specify clearly the search space and any
  pruning conditions used. Show how your algorithm would
  work for 3 teenagers, $T_1,T_2,T_3$, assuming that the only
  quarrelling teenagers are $T_2$ and $T_3$.
  Note: stop the search after finding a solution. [12 marks]

  b) Propose a solution to this problem using the Greedy
  approach. Estimate the complexity of the resulting
  algorithm. [8 marks]

I've spent days going through my notes and reading up on greedy/backtracking but I still don't see how it fits with the question. Whenever I look up Backtracking/greedy approach questions the questions are nothing like how college asks them which makes me very confused...

We've covered dynamic programming, backtracking, greedy algorithms knapsack problem, first fit, next fit minimal spanning trees, Kruskal's algorithm, Prim's algorithm, divide and conquer $N$ queens problem for backtracking.

Overview of the problem

If you takes teenagers as vertices of a graph, and have an edge
whenever the two teenagers are compatible. This gives you an
undirected graph, and what you need is a Hamiltonian path in this
graph (a path that contains every node exactly once). Maybe searching
the web on this abstract version of the problem will yield more
information. Much is said in wikipedia about the Hamiltonian path
problem, which is a NP complete problem. I will only try to discuss
some apects, with my limited competence on the topic, taking into
account the way your question is stated.

Backtracking is just a way of implementing a non-deterministic
algorithm. It is usually simpler to describe the non-deterministic
algorithm, and just say that it is implemented by backtracking, and
possibly explain separately what that is (as I do below)

The non-deterministic algorithm

In the case of the Hamiltoniam path problem (which you can translate
back into your teenagers problem), the non-deterministic algorithm is
as follow:

Choose a starting node for the path, and mark it used.
While there are unmarked nodes do:

Choose a new unmarked node connected to the last node added to the path,
add it at the end of the path, and mark it used.

At the end of the loop you have a Hamiltonian path. The choose
statement is non deterministic, as you have to take one of many
possibilities,  many (or all) of which may not succeed.

Backtracking interpretation

Failure may in general occur in different ways. Here you have failure
when none of the unmarked nodes is connected to the last node added to
the path (i.e. none of the remaining teenagers is compatible with the
last one chosen).

The backtracking implementation consist in keeping track, at each
occurrence of a choose statement, of all the possible choices that
have not yet been tried. If you fail, you go back to the previous
choose, undoing what was done (i.e. node addition to the path and
node marking), discard the choice made and make a new choice from
those that have not yet been tried at that choose statement.

One way of implementing this is to associate a list of remaining
alternative choices to each node of the constructed path. Another
possibility is to rely on the exception mechanism of the programming
language.

Pruning

I am not sure what is (or should be) considered pruning in this case.

Checking that a node chosen is connected to the previously chosen one
is a very trivial form of pruning. No pruning at all would be
exploring the complete set of remaining nodes at each choose
statement, to discover soon after that some fail because the node is
not connected to the end of the path.

Greedy algorithm

The greedy algorithm as described by Yuval Filmus' answer is just the
non-deterministic algorithm, except for the fact that you do not
backtrack. You just fail.  I do not know whether there is more to be
said.

He is much more expert than I am on these issues. However, my own
feeling is that the very concept of greedy algorithm makes less or little
sense in this case.  The reason is that I understand greedy algorithms
as a way of finding good solutions to quantitative optimization
problems, which may not be optimal in some cases.

A greedy algorithm also has to make choices, and does so on the basis
of local optimizations that may not be optimal globally. But it is
expected to succeed anyway and does not have to backtrack: the price
of greediness is that the "cost" (however defined) of the result obtained
by the algorithm may be higher than the cost of the optimal solution.

I do not think that is really very meaningful in an all or nothing
situation, were you are supposed to succeed or to fail, without any
measure of intermediate situations, like placing the largest possible
number of teenagers, or placing them all with the smallest number of
conflictual sittings. These examples may be seen as optimization
variants of the problem where greediness makes sense.

However, we can use heuristics that could possibly increase the
chances of success. In the case of our optimization variants, they
could e seen as greedy techniques that improve the chances of having
near otpimal solution (Though I did not prove anything). But the
greedy algorithm remains basically the non-deterministic description.
The heuritic comes as a way to choose that improves chances of
success, or of approaching the least cost.

One such heuristic, is to always choose one of the unmarked nodes that
has the least number of edges connecting to other unmarked nodes. The
purpose is to keep in your bag nodes that will be easier to connect to
the path, while removing those that are getting hard to use. And if one
of these node is disconnected from all others, or has only one
connection but cannot be added to the path immediately, you know you
have failed and can start backtracking earlier.

We could say that we try to optimize the cost of the search reather
than the cost of the solution obtained, and that this "greedy"
algorithm does increase the chances of success if there is no
backtrack, or reduce the number of search steps if we use backtrack,
or improve the solution obtained if we consider one of the two
optimization variants I described above (maximum number of
non-conflicting teenagers, or minimum number of conflicts).

A global improvement

A global way to improve the algorithm is to decompose the graph into a
a block tree of the graph, where each node is a biconnected
components. This can be done in linear time.

A Hamiltonian path for the whole graph is composed of subpaths in each
of the biconnected components, connected by the edges of the block
tree.

In practice, you solve the given problem at the level of the block
tree, and then you solve it independently for each block, i.e. for
each biconnected component.

Since the algorithm is exponential anyway (NO complete), there is much
to be gained whenever it can be decomposed, thus reducing the size of
the sub-problems.

Actually, if the block tree is not composed of a simple path without
branching, there is no solution to the problem. So that may be a way
of getting much faster negative answers.

This may also be seen as a form of global pruning of the search space.


Algorithm for difference of two semi-decidable languages I have two algorithms

Algorithm 1:

if( Condition1(input)==true )
   print(input);
else
   loop forever;

Algorithm 2:

if( Condition2(input)==true )
   print(input);
else
   loop forever;

for any arbitrary fully-computable conditions 1 and 2.

We know both of these algorithms are partially computable.

I want to write a new algorithm (algorithm 3) like this:

if algorithm1 prints x and algorithm2 does not print x "if and only if" algorithm3 print x

Can I write algorithm3? And how?

You are confusing languages with algorithms.

An algorithms is not "computable" or "non-computable". It can halt or not halt, but the latter doesn't mean that the language it defines is non-computable.

In this case, if conditions 1 and 2 are fully-computable (assuming by that you mean decidable, or recursive), then you can write algorithm 3 as follows:

Given x, check both condition 1 and condition 2. Print the input iff condition 1 holds and 2 doesn't.

The fact that algorithms 1 and 2 are "silly" in that they get stuck for no "good reason" doesn't affect the decidability of their languages.


Is SAT known to be non-context-free or even non-regular? We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas.

Has something similar been done for SAT?

One possible encoding of SAT is as a string over the alphabet $\{x,\land,\lor,\lnot,0,1\}$ which encodes a satisfiable CNF. This language is not regular since intersecting it with an appropriate regular expression, we obtain the language semantically representing $x_i \land \lnot x_i$, which is essentially the language of squares $ww$, classically known to be non-regular. The same argument also shows that UNSAT is not context-free. It is highly likely that similar arguments (perhaps using fancier template formulas) would show that SAT is also not context-free.


How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$? $T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n<4$.
I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess and demonstrate it by induction? also, it should be computed given both upper and lower bound.

You can notice that $T(n) < 3T(n-2)$. This gives you the complexity as $O(3^{n/2})$. You can also observe that $T(n) > 2T(n-3)$. This gives you the complexity as $\Omega(2^{n/3})$. Now, you can at least tell that the complexity is an exponential one.


Partition into pairs with minimum absolute difference, NP-hard? I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$.

The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from $S$ such that $|a_i-b_i|\geq t_i$?

I was trying to prove that this problem is NP-hard by a reduction from 3-Partition Problem. I failed because if I choose the numbers as in 3-partition I cannot guarantee that their absolute difference is at least $t_i$.

Do you have any hints?

You can reduce Numeric 3D Matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_m\},Y=\{y_1,\ldots,y_m\},Z=\{z_1,\ldots,z_m\}$, construct $2m$  elements $x_1+2M,\ldots,x_m+2M,M-y_1,\ldots,M-y_m$ and $m$ values $b-z_1+M,\ldots,b-z_m+M$ for your problem, where $M$ is a very large number. Now the constructed instance of your problem has a solution if and only if the instance of N3DM has a solution.


Max() in Domain Relational Calculus I was looking through my notes on domain relational calculus, and noticed an interesting result in a question about finding the most expensive pizza(s), given a pizza table with schema $\text{pizza}(\underline{id}, size)$. The first idea that came to me was:

$$\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2)\}$$

i.e. A pizza which is at least at big as every other pizza is the most expensive. But the answer given was instead:

$$\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land (\text{pizza}(id2, size2) \to size1 \ge size2))\}$$

The subtle change being that the last $\land$ was switched with a $\to$. I tried converting the if/then to $\lnot pizza(\ldots)\lor size1 \ge size2$ to get an intuitive idea on what exactly causes my former answer to be wrong, but can't seem to put my finger on it. Can anyone grok the differences between both expressions, and why the former isn't the answer? Appreciate it!

For the first solution suppose, given  $id2$ and $size2$ which $\neg pizza(id2, size2)$ and $size1 < size2$. Although, the first solution said $pizza(id1, size1)$ is not maximum (because it is not true for all $id2$ and $size2$), but it can be false.
Because, if $(id1, size1)$ is the only member of the table, it is the maximum.
Therefore, the first solution have some fallacy.

To correct the case, you should mention that if $(id2,size2)$ is member of $pizza$ relation, then $size1 \geq size2$ and you can write this proposition as $pizza(id2, size2) \rightarrow size1 \geq size 2$.


Does White never lose in Chess if Chess is solved? If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?

Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed).

Now it's obvious that White has a strategy to never lose. Because if every move except a pass leads to a loss, then White can pass, and we know that whatever move Black does will lead to a loss for black.

In real chess, nobody knows. And nobody knows if there is a forced win for either white or black either. It is also reasonably likely that there is a time and space limited algorithm that can force a draw.

White starts with an advantage - 1/2 tempo. (Why one half tempo? After e3-e5 e4 White has lost one tempo, and White and Black have effectively swapped sides). We may suspect that with perfect game any advantage would tend to increase. But you need a considerably better position than your opponent in order to win and might not be able to ever get that.


Bloom filter and perfect hashing A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position.

To mitigate the effect of hash collision, multiple functions are used, yielding probabilistic bound if using universal hash.

We can use 10 bits per elements to have 'reasonable' error rate.

If we could directly build a perfect hash function for the set  $S + \infty$, where the last element is one not present in $S$, then we could use only 1 bit per element and have perfect recovery.

What are the fundamental reasons why this reasoning is wrong ?

I think your reasoning is in principle correct. Perfect hashing is an alternative to Bloom filters. However, classical dynamic perfect hashing is rather a theoretical result than a practical solution. Cuckoo hashing is probably the more "reasonable" alternative.

Note that both dynamic perfect hashing and standard cuckoo hashing performance is only expected amortized (you might need to rebuild the data structure completely from time to time). Also Bloom filter are easier to implement. This might be arguments for using a Bloom filter, especially if you can live with false positives.


Formula for finding number of colors to color a map such that no two adjacent counties have the same color Is there a formula for determining the minimum number of colors to color a map with n counties such that no adjacent county have the same color?

No.

The famous four-colour theorem says that four colours are always enough (assuming that counties are contiguous areas of land).
It's easy to tell if one colour is enough: this is the case only if every county is an island, so has no border with any other county.
It's easy to tell if two colours is enough: this corresponds to the adjacency graph being bipartite. You can determine this by colouring an arbitrary county red, then colouring all its neighbours blue, then colouring all their neighbours red, and so on. If this process produces a legal colouring, you have your colouring; if it fails, it turns out that there is no colouring with two colours.
If two colours isn't enough, then it's NP-complete to tell whether three is enough or you have to use four.  This means that, as far as we know, there's no efficent algorithm to determine whether an arbitrary map can be coloured with three colours. This is a result due to Garey, Johnson and Stockmeyer (Some simplified NP-complete graph problems, Theoretical Computer Science, 1(3):237--267, 1976; Science Direct).

There are efficient algorithms to find four-colourings of planar graphs: the two computer-assisted proofs that four colours is enough both gave algorithms. But, as noted above, there's no known efficient algorithm to tell whether four colours is optimal for a given map.


Regular Expressions to Automaton Is there any systematic (algorithmic) method to convert a regular expression like

$(a^*)(b)(b^*)(a^*)c$

to an automaton (let's say a Buchi automaton)?

There are (at least) three algorithms that convert a regular expression to an equivalent finite-state automaton:

Thompson's construction (see e.g. the Wikipedia article)
McNaughton and Yamada's construction
Glushkov's construction (see e.g. the Wikipedia article)

Büchi automata enter the picture if you are working with $\omega$-regular expressions. See e.g. this description of the algorithm for constructing an equivalent Büchi automaton from an $\omega$-regular expression.


Perceptrons: Functions not learnable without bias I am trying to determine which functions are not learnable without a bias when building a perceptron. The set of functions I need to evaluate is {NOT, OR, AND}.

Could someone help interpret these results?

AND FUNCTION

https://imgur.com/a/OTFUT

OR FUNCTION

I get a divide by 0 error in my script.

NOT FUNCTION

https://imgur.com/a/wZnxT

It would appear that the AND function does not crash like the OR function but the end result is incorrect. The OR function simply won't graph due to a divide by 0 error. The NOT function appears to still be learnable.

If desired, I can post my python script with how I generated these graphs. I am using a sigmoid activate function.

If you don't have a bias, your perceptron learns the function

$$y = w_1 \cdot x$$

This means the decision boundary is a line through (0, 0).

AND

$y, x, w_1 \in \mathbb{R}^2$

Function table:

x_1 x_2 y
---------
0   0   0
0   1   0
1   0   0
1   1   1

This is not learnable.

  I am using a sigmoid activate function.

Without a hidden layer, a Perceptron is still a linear classifier.


Why is the array used for a restricted hashing scheme always sized to a 4k + 3 prime? Why is the array used for a restricted hashing scheme always sized to a 4k + 3 prime? When they talk about a restricted hashing scheme are they talking about a non perfect hashing which includes having a collision algorithm which resolves that problem? Can someone please help me?

The mentioned scheme is the most probably Quadratic probing collision resolution in the Hash Table, so it is non-perfect.

The $4k + 3$ prime size of the table is to allow all cells to be probed, the size of different length will result in non accessible cells in the array, degrading performance and wasting space.

Please read about limitations of QP.


SPIN / Promela Verification I have this code here which performs the 'leader election' among a specified number of processes. In Promela, it is written as:

  #define N 5       /* this is the number of processes */
  #define I 3   /* node that is given the smallest number    */
  #define L 10  /* size of the buffer, channel of channels  (>= 2*N) */

   mtype = { one, two, winner };
   chan q[N] = [L] of { mtype, byte};

   byte nr_leaders = 0;

  proctype node (chan in, out; byte mynumber)
  { bit Active = 1, know_winner = 0;
    byte nr, maximum = mynumber, neighbourR;

    xr in;  /* exclusive recv access to channel in */
    xs out; /* exclusive send access to channel out */

    printf("MSC: %d\n", mynumber);
    out!one(mynumber);
  end:  do
    :: in?one(nr) ->
        if
        :: Active ->
            if
            :: nr != maximum ->
                out!two(nr);
                neighbourR = nr
            :: else ->
                /* in case the number equals the max one */
                assert(nr == N);
                know_winner = 1;
                out!winner,nr;
            fi
        :: else ->
            out!one(nr)
        fi

    :: in?two(nr) ->
        if
        :: Active ->
            if
            :: neighbourR > nr && neighbourR > maximum ->
                maximum = neighbourR;
                out!one(neighbourR)
            :: else ->
                Active = 0
            fi
        :: else ->
            out!two(nr)
        fi
    :: in?winner,nr ->
        if
        :: nr != mynumber ->
            printf("MSC: LOST\n");
        :: else ->      /* declare the winner */
            printf("MSC: LEADER\n");
            nr_leaders++;
            assert(nr_leaders == 1)
        fi;
        if
        :: know_winner
        :: else -> out!winner,nr
        fi;
        break
    od
  }

  init {
    byte proc;
    atomic {
        proc = 1;
        do      /* iterate through the processes */
        :: proc <= N ->
            run node (q[proc-1], q[proc%N], (N+I-proc)%N+1);
            proc++
        :: proc > N ->
            break
        od
    }
  }

I'm interested in how I can edit this so I can verify that all processes terminate after I run the code through Spin and that all the processes agree about the one elected leader (that there's one leader).

On this link: http://spinroot.com/spin/Doc/SpinTutorial.pdf on page 31, there's a SPIN property liveliness which includes the verification of termination, so that's what I'm trying to implement now, besides the mutual agreement of the leader.

Thanks for the input!

For the "all the processes agree about the one elected leader" part:

It is a combination (conjunction) of

No more than one process can ever be declared to be the leader: $\Box (\textrm{nr} \_ \textrm{leaders} \le 1).$
Eventually a leader is elected: $\Diamond (\textrm{nr} \_ \textrm{leaders} = 1).$


Naive argument that P ≠ NP Consider the following naïve argument that any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario.

Let $f(x_1,x_2,\dots,x_n)$ be a Boolean function in conjunctive normal form (CNF). The problem SAT is to determine whether there exists a $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ such that $f(x_1,x_2,\dots,x_n)=1$. Nothing is known a priori about the function $f$, so in general, in order to determine this information, it is necessary to plug in each $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ into $f(x_1,x_2,\dots,x_n)$ to test whether $f(x_1,x_2,\dots,x_n)=1$, until one is found to satisfy $f$ or all are found not to satisfy $f$. There are $2^n$ possible $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ to plug into $f(x_1,x_2,\dots,x_n)$ to test. Therefore, any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario. So $P \neq NP$. QED

What exactly is wrong with this argument? More importantly, are there any known counterexamples (algorithms that take $o(2^n)$ in the worst case scenario for SAT)?

Caveat: Note that there are known counterexamples if one restricts $f$ to being in 3CNF, but this is only because 3CNF has a special structure that plain CNF does not have. Plain CNF has no special structure at all, since any Boolean function can be placed in CNF.

The error in your argument is the claim

  Nothing is known a priori about the function $f$, (...) so it is necessary to plug in all $2^n$ values.

, which is simply false. I will demonstrate why it isn't necessary to plug in all possible values and sketch how to arrive at an $O^*((2^k-1)^{n/k})$  time algorithm, where $k$ is the number of clauses. $O^*$ 'hides' poly-logarithmic factors, so for fixed $k$, this would be an $o(2^n)$ algorithm.

A key idea is this: If we wish to satisfy some clause of $m$ literals $l_1 \vee l_2 \vee \dots\vee l_m$ by assigning truth-values, then there are $2^m-1$ ways to do this, as exactly one of the assignments does not satisfy the formula. This means we in fact do not have to test every assignment (for this clause).

Not doing a single test seems like a trivial improvement. However, by recursively applying the procedure to only check at most $2^k-1$ assignments, we get a running time $T(n)$ for which we have $T(n)= (2^{m_i}-1)\cdot T(n-m_i) + O^*(n)$, where $m_i$ is the number of elements of the $i$-th clause. So, $T(n) = (\Pi_{i=1}^l (2^{m_i}-1))T(0)+l\cdot O^*(n)$, where $l$ is the number of clauses. This gives the result $T(n)=O^*((2^k-1)^{n/k})$.

Of course, our improvement still yields a rather unpractical algorithm, but there are other tricks you can apply. To learn more, these slides by William Gasarch are a good read. (The title states 3-SAT, but most methods can be generalised to $k$-SAT)


Generalization of Functors to other datatypes? Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$, we have a functor $F$ which contains $f$, but additionally also maps morphisms on $A$ to morphisms on $B$ (i.e. maps not only $A$ to $B$ but also maps "structure on $A$" to "structure on $B$").

In the category theory of functional programming, objects $A,B$ are types and morphisms are functions $A\to B$ between types. That means functors map types $A,B$ to other types $X,Y$ and map functions $A\to B$ to functions $X\to Y$. Functors in functional programming can thus be seen as a mapping between datatypes that additionally also maps the functional structure on those data types.

My thought was: In the context of object-oriented programming, there really are more kinds of structure on datatypes than just functions between them. For example, given two types $Int$ and $Bool$, we can not only define functions $f:Int\to Bool$, but also things like $p:Int\times Bool$, or more complex datatypes like classes with private component classes.

Is there a generalization of functors to "mappings between datatypes that also preserve structure", where that doesn't need to be functorial? In particular I'm wondering whether such a concept is used in analyzing programming languages.

I guess no one else is going to answer this, so I'll take a crack.

First, there's nothing inherently 'functional' about categories, necessarily. For instance, you can make any monoid into a category, where you have one object, and then the arrows from that one object to itself are the elements of the monoid. The identity element is the identity arrow, and composition is monoid multiplication. Then functors between two monoids in this sense are homomorphisms between the monoids; they are functions that preserve identity and multiplication.

Categories are then generalizations of this to situations where the monoid values have types, and can only be multiplied together when the types correspond. The specifics of this work for functions, but it could be a lot of other things, too. You could try to devise a category where $Hom(X,Y) = X×Y$, and then functors from/to that category would be obligated to map from/to products.

However, it is also common to define additional structure beyond just being a category. For instance, even for 'functional programming,' you are usually talking about (at least) Cartesian closed categories. These are categories $C$ that have additional structure:

$$-×- : C × C → C$$
$$1 : C$$
$$[-,-] : C^{op} × C → C$$

Where $×$ forms binary products, $1$ is a terminal object, and $[-,-]$ forms exponentials, so:

$$C(X×Y,Z) \cong C(X, [Y,Z])$$

And when you have categories with additional structure like this, you also want to talk about functors that preserve that extra structure. So there are Cartesian closed functors between Cartesian closed categories that map products to products, terminal objects to terminal objects, and exponentials to exponentials.

So, yes, you can describe plenty of structure besides just $Hom$, and talk about maps that preserve all that structure (in various senses), not just functors.


A "packing" optimisation problem with application in dynamic programming I'm interested in the following problem :

Input : an integer $n$, and $k$ increasing functions $f_i:\mathbb{N}\rightarrow\mathbb{R}$, such that $f_i(0)=0$ for all $1\le i \le k$

Output : $k$ integers $n_1,\dots,n_k$, such that $n_1+\dots+n_k=n$, with $0\le n_i\le n$

Goal : Maximize $\sum_{i}f_i(n_i)$

My question is : If we suppose that $k=n$, or simply $k=\Omega(n^\delta)$ for some $\delta>0$, is it possible to find the optimal solution in polynomial time (in $n$) ?

What if we first consider very simple functions like : $\forall i,m, f_i(m+1)-f_i(m)\in\{0,1\}$ ?

Such a result could possibly have interesting applications for dynamic programming

Yes.  This can be solved in polynomial time using a straightforward dynamic programming algorithm.  You build a table $A[\cdot,\cdot]$ where $A[i,m]$ denotes the maximal value of $f_1(n_1)+\dots+f_1(n_i)$ subject to the requirement that $n_1,\dots,n_i$ be a partition of $m$, i.e., $n_1 + \dots + n_i = m$.  The entries satisfy the following recursive relation:

$$A[i,m] = \max \{A[i-1,m-t] + f_i(t) : 0 \le t \le m\}.$$

You can fill in this array using the recursive relation in $O(kn^2)$ time, which is polynomial in $n$.  Then, $A[k,n]$ contains the answer to your problem.


How to prove P$\neq$NP? I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point.

We can show that P $=$ NP if and only if we can design an algorithm that solves any given instance of problem in NP in polynomial time.

However, I do not understand how on earth can we prove that P$\neq$NP. Please excuse me for the following similitude as it might be so irrelevant, but telling someone to prove if P is not equal to NP appears to me like telling someone to prove that God does not exists.

There is a set of problems, those are unable to be solved by a Non-deterministic Finite Automata (NFA) with polynomial number of states regardless of the current technology (I know this is a sloppy definition). In addition, we have a considerably large set of algorithms that makes some crucial problems (shortest path, minimum spanning tree, and even sum of integers $1 + 2 + \dots + n$) polynomial-time problems.

  My question in short: If I believe that P $=$ NP,
  you would say "then show your algorithm that solves an NP problem
  in polynomial time!". Suppose that I believe P$\neq$NP. Then what would you exactly ask? What would you want me
  to show?

The answer is clearly "your proof". However, what kind of proof shows that an algorithm cannot exist? (in this case, a polynomial time algorithm for an NP problem)

There are three main ways I'm aware of that could prove that P$\,\neq\,$NP.

Showing that there is some problem that is in NP but not in P. You're probably familiar with the proof that comparison-based sorting need time $\Omega(n\log n)$ to sort a list of $n$ items. One could, in principle, produce a similar proof showing that 3SAT or some other NP-complete problem can't be solved in time $O(n^c)$ for any constant $c$. Geometric Complexity Theory seeks to use tools from algebraic geometry and group representation theory to prove such lower bounds, by considering the symmetries that problems possess.  Circuit Complexity is another.

Showing that P and NP have different structural properties. For example, P is closed under complementation. If you could show that NP$\,\neq\,$co-NP (i.e., that NP is not closed under complementation), then is must be that P$\,\neq\,$NP. Of course, this is just pushing the problem one level deeper – how would you prove that NP$\,\neq\,$co-NP?
Another possibility is that we know that NP is exactly the class of problems that can be defined in something called existential second-order logic.  If one could show that there's no logic corresponding exactly to P (or if there is a logic but it's different to $\exists\mathrm{SO}$), then P and NP must be different. A related (in fact, equivalent) idea is to show that P doesn't have complete problems under reductions defined by first-order logic, since it's known that NP does have complete problems under these reductions.

Prove that some problem isn't NP-complete.  If P$\,=\,$NP, then every non-trivial problem in NP is NP-complete under polynomial-time many-one reductions ("non-trivial" here means not $\emptyset$ or $\Sigma^*$). So, if you can show that some problem in NP isn't NP-complete, then we must have P$\,\neq\,$NP.


Smoothing frequencies without count data I have frequency data for different events under two conditions, resulting in sets of frequencies F1 and F2. I would like to normalize the frequencies of events under condition 1 by their frequencies under condition 2. However, there are events that occur in condition 1 but not condition 2, resulting in divide-by-zero problems when I attempt to normalize.

For raw count data, I understand that there are a number of smoothing techniques (e.g. Witten-Bell) that can help sort this out, but I only have the frequencies, not the individual counts. In other words, I have frequencies like {0, 0.1, 0.2, 0.7} which could correspond to counts of {0, 1, 2, 7}, {0, 10, 20, 70}, etc. Are there any algorithms that are able to smooth this type of frequency data?

Yes. $\:$ Assume that the counts have the smallest sum that would produce your frequency data. $\:$ (How to do that depends on whether the frequencies were calculated and stored as doubles or something else.)


Reduction from Vertex Cover to Dominating Set I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles use a reduction that transforms the input for the vertex cover problem to an input for the dominating set problem by creating a triangle for each edge. Here is one of such articles (See question 7 in the link).

The question that I would like to ask is, if we drop isolated vertices in the input to the dominating set problem, then, we could easily find a counterexample to the reduction - Let the input to the vertex cover problem be a graph containing $N$ isolated nodes and parameter $k=N$. Now, the input to the dominating set problem will clearly be an empty graph with the parameter $k=N$. Now, there is a vertex cover of size $N$. But it is not a dominating set of the transformed graph (i.e. the answer to the vertex cover problem is yes but the answer to the dominating set cover problem is no).

How could I fix the reduction? Could someone please advise me?

If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$  such that  $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each other vertex in $V$. Formally: $E' = E \cup \{ (x,v) \mid v \in V \cup \{y\}\}$.

If $G$ admits a vertex-cover $C$ of size at most $k$, then $G'$ admits a vertex-cover of size at most $k+1$, namely $C \cup \{ x \}$.

If $G'$ admits a vertex-cover $C$ of size at most $k+1$, then $G$ admits a vertex-cover of size at most $k$. This can be easily seen by noticing that $C \setminus \{ x, y\}$ must cover all the edges in $E$, and that $(x,y) \in E'$ ensures that at least one of $x$ and $y$ is in $C$, i.e., $|C \setminus \{ x, y\}| = |C| - |C \cap \{x,y\}| \le |C| - 1 \le k$.

Since $G'$ has no isolated vertex, you can now safely transform it to the graph $H$ of the dominating-set instance (using the known reduction).
In this way you show that $G$ has a vertex-cover of size at most $k$ $\iff$ $H$ has a dominating set of size at most $k+1$.


What does a non-deterministic guess "look like"? I have been trying to understand the solution to the following problem:
"Show that if $L_2$ and $L_3$ are Turing recognisable, then so is $L_2L_3 = \{w_1w_2 : w_1 \in L_2,w_2\in L_3\}$:
which essentially says to use non-determinism to guess a partition $w$ (say $w=xy$) and run the Turing machines $L_1$ and $L_2$ on $x$ and $y$ respectively.
I'm trying to get my head around what this non-deterministic guess "looks like", i.e. what we would say if we were to describe this implementation in more detail.
My thought is if the input string is of length $n$, then the second string $y$ could start at any of the $n$ positions, or be empty, so there are $n+1$ possible partitions. Does this mean we ultimately need to split into $2(n + 1)$ parallel/non-deterministic clones? And how do we manage this splitting in terms of transitions? We obviously don't know the length of the input ahead of time, so we can't immediately have $2(n+1)$ transitions from the start state? Would we scan the input string left to right, spawning two additional parallel threads for each character encountered, or something?
I see this "non-deterministically guess" phrase a lot in example solutions, but I feel like I'm missing a bit of intuition as to why this actually works. Any thoughts would be much appreciated.

Nondeterministic guess is a non formal term we use for two (or more) possible transitions from the same configuration. When talking about a non deterministic finite automata, if a state $q$ has two different transitions for the character $a$, and I want to show that it accepts a certain word $w$, then I treat the junction at $q$ where $a$ is read as the location where the "guess" happens. By "guessing correctly" I refer to the transition that will lead to the eventual acceptance of $w$ (whereas I don't care what would have happened if I took the other transition, the "wrong" guess).
One implementation of guessing a partition of $w$ to $w_1w_2$ would be to have two transitions from the initial state for each character read by the machine head. One transition goes to the state $q$, where $q$ refers to $w_1$ as whatever lies to the left of the current position of the head and $w_2$ as the rest. The other transition stays at the initial state and keeps moving right until it meets blank. Although it's important to realize how to implement such a "guess", it is arguably more important to develop the intuition around the power of nondeterminism and understanding the such a nondeterministic  partition can be done (without going through the tedious details and elaborating on the transition function).
For your problem non determinism doesn't really make things much easier, as you could simply execute both machines on every possible partition (of which there are $n$ where $n$ is the input's length) in parallel via dovetailing.


Problems while trying to prove that $(r|s)^* = (r^*.s^*)^*$ I came across the following equality of regular expressions $$(r|s)^* = (r^*.s^*)^*\,,$$ where $r$ and $s$ are two regular expressions and $.$ denotes concatenation, but I don't know how could I prove it.

My try:

I call $L(r)$ the language defined by the regular expression $r$. And I want to use the fact that two regular expressions $r$ and $s$ are equal iff $L(r) = L(s)$.

The LHS can be writen as follows: $$ L((r|s)^{*}) = \bigcup_{i=0}^{+\infty} L(r|s)^{i} = \bigcup_{i=0}^{+\infty} (L(r)^{i} \cup L(s)^{i})\,. $$

The RHS can be writen as follows:
$$ L((r^{*}.s^{*})^{*}) = \bigcup_{i=0}^{+\infty} L((r^{*}.s^{*}))^{i}\,.$$

But I got stuck at this point and I don't know how to proceed.

In one direction,
$$
L((r^*s^*)^*) \subseteq L(((r|s)^*(r|s)^*)^*) = L(((r|s)^*)^*) = L((r|s)^*).
$$
In the other direction, $L(r) \subseteq L(r^*s^*)$ and $L(s) \subseteq L(r^*s^*)$ imply that $L(r|s) \subseteq L(r^*s^*)$, and so
$$
L((r|s)^*) \subseteq L((r^*s^*)^*).
$$


A concrete example about string w and string x used in the proof of Rice's Theorem So, in lectures about Rice's Theorem, reduction is usually used to proved the theorem. Reduction usually consists a construction of $M'$, using a TM $M$ which is in the form $\langle M,w \rangle$  to be simulated first, an input $x$ to be simulated if $M$ accepts. $M'$ accepts if x is accepted.

I really want a concrete input about $\langle M,w \rangle$  and $x$. For example:

  $L = \{ \langle M\rangle  \mid L(M) = \{\text{ stackoverflow }\}\}$, that is L contains all Turing machines whose languages contain one string: "stackoverflow". $L$ is undecidable.

What kind of $\langle M,w \rangle$ to be simulated?

Suppose we have input x = "stackoverflow" or x = "this is stackoverflow" or any x with "stackoverflow" in it.

What if we first simulate a TM $M$ selected from in the possibilities of all TMs, and this TM accepts only a single character $a$ as its language. So, we simulate this $\langle M,w \rangle$  with $w = a$, and surely it will be accepted. And then input $x$ is also accepted according to the definition of $L$.

So, we conclude that $\langle M,w \rangle$  in which language is a single $a$ is reducible to $L$ that accepts all TMs which have "stackoverflow"?

Edit: I've just looked up a brief definition of reduction. A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Given that definition, I think the correct TM $M$ with its description $\langle M,w \rangle$  in my example should be a TM such that it accepts regular languages. This is the harder problem. If this is solvable, then my trivial $L$ with one string is solvable. But apparently, it's not according to the proof. We can effectively say we reduced from language one string problem to regular language problem and try to solve it. Previously, I thought the other way around: $\langle M,w \rangle$  is reduced to one string problem.

Is my thinking correct?

A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Your characterisation of reduction is a bit misleading. You don't start with an "easy" problem and reduce it to a "harder" problem (how can you know it's an easy problem if it's unknown? Often you're attempting the reduction to find out whether your problem is "easy").

A reduction is a computable transformation from one problem to another. It proves that the source problem is no harder (in some sense) than the target problem.

Sometimes we do this because we already know the source problem is impossible to solve; this proves that the target problem is impossible too. Since the source problem is "no harder" than the target problem, and we already know the source is undecidable, the target problem must be undecidable (or the source would in fact be harder). More intuitively, if we can reduce the source to the target and the source is undecidable, then the target must be undecidable or we could use the reduction and the solution to the target in order to solve the source (which we already know can't be done).

Other times we find a reduction because we know the target problem is decidable. This shows that the source problem is decidable too.

So you can use a reduction argument either to a problem that's already known to be decidable, or from a problem that's already known to be undecidable, depending on what you're trying to prove.

So, Rice's Theorum. I don't quite understand the questions you're asking, since I haven't seen the particular statement of the proof that's giving you trouble. Instead, here's my quickie explanation of how to prove Rice's Theorum, which I'm pretty sure is similar.

Suppose we have an arbitrary language $L$, consisting of (encodings of) exactly those TMs with some non-trivial semantic property $P$.[1] To prove that there is no algorithm for deciding language $L$, I will reduce the Halting Problem to the decision problem for $L$.

So the Halting Problem (or the particular variant of it I will use here) is: given $\langle M, x\rangle$, an encoding of a Turing machine $M$ and an input $x$, does $M$ halt on $x$?

My reduction must transform the input to the Halting Problem $\langle M, x \rangle$ into the input for the hypothetical decider for $L$, which I will call $ML$. $L$ is a language of Turing machines, so $ML$'s input looks like $\langle M \rangle$.

So my reduction will take $\langle M, x \rangle$ and compute $\langle M' \rangle$. $M'$ is a machine that takes an input $w$ and functions as follows:

Simulate $M$ on $x$, ignoring the result
Simulate $MP$ on $w$; accept if it accepts and reject if it rejects

Here $MP$ is a machine that whose encoding is in $L$ i.e. it has the property $P$. Since we're considering a non-trivial property $P$, such an $MP$ is guaranteed to exist.

Note that $x$ is part of the machine $M'$ the reduction has produced, while $w$ is the input to that machine whenever it is run. $x$ and $w$ are completely unrelated. We are assuming we've been given a particular $x$ as part of the input to the Halting Problem, but since we haven't proposed running $M'$, there is no specific $w$ at the moment.

Now, if $M$ halts on input $x$, then $M'$ always gets to stage 2 and thus accepts/rejects exactly the same strings as $MP$. Since the property $P$ is semantic, it doesn't depend on the particular TM, only on the language it accepts, so in this case $M'$ also has property $P$. If $M$ doesn't halt on input $x$, then $M'$ never gets to an accept state regardless of input, so its language is the empty language.

So now we don't want to run $M'$ on anything, since it might not even halt, but we could run our hypothetical $ML$ on it to check whether it's in $L$. This will almost tell us whether $M$ halts on $x$; the only thing we're missing is that the empty language might happen to have property $P$, in which case $ML$ will always accept $M'$ whether or not $M$ halts on $x$. But we can easily amend $M'$: if $P$ is true of the empty language (which our reduction could check using $ML$ if $ML$ could actually exist), then we use $MN$ instead of $MP$ - some machine that doesn't have property $P$ (which is also guaranteed to exist by the non-triviality of $P$) - and then our $M'$ has property $P$ if-and-only-if $M$ doesn't halt on $x$.

So now we've shown that a hypothetical decider for $L$, the language of machines with property $P$, could be used to decide the Halting Problem. Since we already know the Halting Problem can't be decided, $ML$ can't exist. Since the only thing I assumed about $P$ was that it was a semantic and non-trivial property, the proof holds for any semantic and non-trivial property.

I cheated a little in my reduction, since I had to use $ML$ to work out whether the empty language has property $P$, which means the reduction is only computable if $ML$ exists. This breaks my earlier definition of a reduction as "a computable transformation from one problem to another", but the proof by contradiction is still perfectly valid; proving a language undecidable by reduction from an undecidable language is really just a special case of a proof by contradiction anyway.

[1] A property of a TM is semantic if all TMs that accept the same language share the property, i.e. the property doesn't depend on the particular implementation of the TM but only on the language it accepts. A property is non-trivial if there is at least one TM that has the property and at least one TM that doesn't have the property.


Is SAT in P if there are exponentially many clauses in the number of variables? I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$.

I'd like to know why $\text{Long-SAT} \in P$. First I thought it is $\text{NPC}$ since I can do a polynomial-time reduction from $\text{SAT}$ to $\text{Long-SAT}$, no?

But maybe I can reduce $\text{2-SAT}$ to $\text{Long-SAT}$? How do I do that?

Unless I'm missing something, it's trivially in P as the length of the formula is exponential in the number of variables. Hence all $2^{n}$ truth assignments can be generated and checked in polynomial time in the length of the formula.


Is inverse CNF polynomial? Suppose we are given a CNF formula $F$ with $n$ variables and $m$ clauses. The question is whether we can represent $\lnot F$ as a CNF formula with the number of clauses polynomial in $n$ and $m$?

No, not necessarily.

If $F$ is $(\neg X_1 \lor \neg Y_1) \land \dots \land (\neg X_n \lor \neg Y_n)$, then expressing $\neg F$ in CNF requires exponentially $2^n$ clauses.  See, e.g., https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF, Which CNF boolean formulas blow up exponentially at conversion to DNF?, and Formulas for which any equivalent CNF formula has exponential length.

However, if you allow introducing additional variables, then you can construct a formula $G$ that is equisatisfiable with $\neg F$ and such that $G$ can be represented in CNF with number of variables and clauses polynomial in $n$ and $m$.


What is the difference between abstract and concrete data structures? I thought associative array (i.e. map, or dictionary) and hashing table were the same concept, until I saw in Wikipedia that

  For dictionaries with very small numbers of bindings, it may make
  sense to implement the dictionary using an association list, a linked
  list of bindings. ...

  The most frequently used general purpose implementation of an
  associative array is with a hash table: an array of bindings, together
  with a hash function that maps each possible key into an array index.
  ...

  Dictionaries may also be stored in binary search trees or in data
  structures specialized to a particular type of keys such as radix
  trees, tries, Judy arrays, or van Emde Boas trees. ...

So, I think, my problem lies in that I don't know that associative array (i.e. map, or dictionary) is an abstract data type and hashing table is a concrete data structure, and different concrete data structures can be used to implement the same abstract data type.

My questions would be

What is the difference and relation between abstract data structures and concrete data structures?
What examples are for each of them (abstract and concrete data structures)? The more the better.
Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.

The abstract data type (ADT) is essentially an API, and a concrete data structure provides an implementation of that API. For a given ADT, there are often several different choices of concrete data structures which support the query and update operations described by the ADT. Every concrete data structure for a given ADT must support all the operations described by the ADT (possibly with some probability of success in the case of randomized structures), but each concrete structure may make different guarantees of the running times of each operation. The choice of which concrete data structure to implement for a given ADT usually depends on the priorities of efficiency of each operation (including initializing the structure) and the complexity of implementing and maintaining the various data types. Some concrete data structures have excellent theoretical guarantees, but the overhead is such that a slightly less theoretically optimal data structure may be a better choice in practice.

There are far too many ADT and corresponding concrete structures to list in a single answer, but here are a few examples:

A dictionary supports Find(x) queries. For an a key $x$, return the element in the dictionary with key $x$, if such an element exists. A dynamic dictionary also supports Insert(x) and Delete(x). Common implementations of a dictionary include different kinds of balanced binary search trees (e.g. red black tree) and various kinds of hash tables.
In addition to Find an ADT may require support of successor(x) queries. That is, maintain a set of keys $S$, and given key $x$, find the smallest key $t \in S$ such that $s < t$. Concrete data structures which support the Successor ADT include various binary search trees, and more complicated structures such as an X-fast trie or van Emde Boas tree (if the keys are integers).
A Priority Queue is an ADT that requires insert and delete-min operations (and sometimes other operations as well, such as find-min increase-key or delete-key). Data structures that implement the priority queue ADT include:

an unsorted linked list, which has fast insert but slow delete-min.
a sorted linked list which has fast delete-min but slow insert
a binary search tree, which has logarithmic insert and delete-min, and $sort(n)$ initialization time.
a binary heap which has logarithmic insert and delete-min, and linear time initialization.
There are also other variants of heap implementations.

An interval stabbing ADT maintains a set of intervals on the real line, and supports a stabbing(x) query, which returns the subset of intervals which contain (are stabbed by) the point $x$. Data structures that implement the stabbing query ADT include a Segment Tree and an Interval Tree.


What factors influence machine epsilon? I was wondering what factors effect a machine's epsilon value. I was thinking about how modern computers can calculate expressions to higher accuracy then their predecessors, but what hardware and software factors allow for improved accuracy? Is it the implementation of better algorithms for computing various functions (examples welcome), the use of more capable hardware, or another factor I can't think of?

My go to thought is the development of better algorithms, but I can think of any that were developed post 1990.

My second thought was that the increased memory available in modern computers allows arbitrary precision arithmetic to produce more accurate results, however not all applications run with arbitrary precision and you can still run into a software "bottle neck" on the outputted precision.

What factors have the greatest effect on machine precision?

The phrase "machine epsilon" is misleading. In reality, it doesn't depend on the machine at all, but on the floating-point data types that the programmer chooses to use.


An integer linear program I have the following problem:

  Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where the only pairs $(x, y)$ that are considered for which $x$ and $y$ are positive integers and $ax + by \leq n$.

I'll be very grateful for any tips about which method could be used to solve this.

If you google for Integer Linear Programming, you'll find that the problem is in general NP-complete. However, your subproblem with just one restriction and two variables isn't difficult to solve.

Have a look at https://en.wikipedia.org/wiki/Cutting-plane_method and especially Gomory's method: You first use the Simplex algorithm to find the optimal solution without considering that the solution should be integers. If by coincidence your optimal solution is integer, you solved the integer linear programming problem. Otherwise, you use Gomory's method to find another restriction which isn't fulfilled by the non-integer solution you found, but by every integer solution of the original problem. You solve the system with the new equation, and repeat until you have an integer solution.


Can a node of Radix tree which represents a valid key have one child? Wikipedia says:

  a radix tree is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.

Now they are situations where the parent of the child represent a valid key in the data set like this example:

from this answer. Obviously you can't merge "smiles" into "smiled" and "smile" or you are going to lose valid entries in your data set.

Here as much as I understood suggests, as seen in the image,:

that for a one child parent with valid key like "organ" to add a child which has the same value (but it is not a parent). When the parent gets two children then that auxiliary child can be removed.

This implementation however for example doesn't seem to care about breaking the "no parent with one child" rule, while adding a child node to a leaf.

So my question is that whether "no parent with on child" rule is coined into the definition of radix tree and if so what is the computational/space advantage of it. It seems to me the 4 solution to keep up with the rule leads  in both space and computational efficiency lost. If not then is it safe to say that Wikipedia definition need to be corrected?

I've used patricia tries extensively, but haven't implemented a radix=2 patricia tree. (I generally used radix=256.)

  So my question is that whether "no parent with on child" rule is coined into the definition of radix tree

Not that I'm aware of. That sounds like an detail of a particular implementation.

Any time you have a valid key, you have a node. Any time you have a longer key that starts with that key, you have a child. So there will be lots of cases (on the order of some log function) of parents with one child, but those parents that have one child will imply a valid key in most implementations.

In your example, "smile" and "smiled" are two nodes, and "smiled" is a child of "smile". Both are valid keys. The "smile" node would have one child, "smiled".

Note that if a parent has only one child (e.g. after a node removal), and the parent does not represent a valid key, then the parent can combine itself with that one child. (That is an implementation choice.) So in your example, if we remove the key "smile", then we can either mark that node as "not holding a key any longer", or we can get rid of it, sliding the "smile" node up the tree.


Examples for Partial Combinatory Algebras I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories [1]). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), which I want to get out here, as neither of my supervisors could help me.

In Total Maps of Turing Categories [2] necessary and sufficient conditions for a category to appear as subcategory of total maps of some Turing category are given. As a corollary, the category of PTIME-functions, LOGSPACE-functions, LTIME-functions etc. can appear as total maps of some Turing category. Does this imply that these classes can be characterized by a specific PCA and (if so) how does it relate to Kleene's first model? In other words, are there complexity classes which can be represented by sub-PCAs of Kleene's first model?
Are there models of PCAs which are not a priori inspired by computability theory? The general setting of applicative system and computable function (see [1] section 4) seems to be rather general such that it may be applicable in general categories. However all my attempts to find a PCA in categories like Top, K-Vec, R-Alg, R-Mod etc. have failed. I am well aware of Kleene's second model, Scott's graph model and the $\lambda$-calculus as they are stated in Realizability - An Introduction to its Categorical Side [3]. I am just curious whether this notion of computability naturally arises anywhere else in ordinary mathematics...

I hope anybody can help me out. No matter what, thank you all for your time.

Consider a subPCA $A$ of Kleene's first algebra. It contains $K$ and $S$. These are sufficient to implement every total computable function, so $A$ must contain at least these, and cannot be just some limited complexity class.

I do not quite understand why Kleene's second algebra and Scott's graph model aren't "topological". Kleene's second algebra is the universal 0-dimensional countably based Hausdorff space. Scott's graph model is the universal $T_0$ countably based space. These characterizations have no trace of computability, but because the spaces are universal it is to be expected that they have a very rich structure, and so can be made into models of $\lambda$-calculus.


When is a root node an articulation point in a graph? I am trying to find the articulation points in a connected undirected graph and I'm finding it difficult to figure out if the root node of the DFS is an articulation point.
Based on the literature I've read the root node is considered an articulation point if it has more than one child link1

My question is around the graph
(0 - 1)
(0 - 2)
(1 - 2)
(1 - 3)
(2 - 4)
(2 - 5)

When we the DFS rooted at 0 should 0 be considered an articulation point? it does have more than one child, however, the children are connected so removing 0 does not increase the number of connected component (doesn't cut the graph)

I would appreciate if someone can shed some light on this for me.

In the example above running DFS rooted at 0 the vector 0 will only have one tree link as the algorithm will follow the route: 0 -> 1 -> 2 -> 0
Since the edge 0-2 is considered a back link and not a tree link 0 is not considered an articulation point.


how does cpu read 32 bit word from memory I'm interested in how  does cpu read 32 bit word from memory .If the processor has 32 bits of address space then it can  address 4,294,967,295 locations  (or 4 gb) Does this mean that each location has 32 bits.?

Address Space and Word Size are indeed two different things. If my processor has an $n$ bit address space, then it can address $2^n$ addresses. Note that this is merely the number of addresses and is not $2^n$ GB.

The word size of a memory refers to the size of the smallest addressable unit of the memory. In other words if my processor has an $n$ bit address space and a word-size of $b$ bytes, then my processor can address $2^n$ locations each of which are $b$ bytes long.


Classification algorithm for high dimensional data which is uniquely definable in a very small sub-space I am new to machine learning, so forgive me if I am doing something absolutely absurd.

I have a classification task (~100 classes) and have about 2 million training data points in a 2000-dimensional space. Coordinates of data points are integers (discrete). All points have non-zero coordinates only for < 10 dimensions. That is, each point can be uniquely defined in < 10 dimensional sub-space.

If I use a Gaussian Mixture Model (GMM) for each class, I will end up with ~100 GMMs in a 2000-dimensional space. I feel that given the fact that each point is uniquely definable in less than 10 dimensional space, there can possibly be a better way of doing it.

What am I missing here?

Since your data are extremely sparse, using GMMs or a traditional SVM will result in an over-fit model. By employing methods that exploit the sparsity of the structure, you should get much better results. Regression methods typically add some penalty function as a measure of the amount of non-zero values. This is usually referred to as "regularization". Doing this exactly (under the $L_0$ norm) is difficult, so relaxations are used (lasso: $L_1$, ridge: $L_2$).

If you are comfortable with Python, SciKit Learn has implementations for several approaches that utilize either lasso or ridge penalties. Here is an example of Lasso penalty for an SVM model. I would try that and see how well it works. It may require a parameter to adjust the regularization amount. You can do cross-validation to find what parameter works best.


Minimum descending stacks Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules:

The first card goes to the top of a stack

For every new card k,or

(i) the k is put on the top of an already existed stack, if the value of the top card of a existed stack is bigger than the value of the card k or

(ii) we create a new stack righter than the other stacks and with the card k.

The game is completed after n rounds when there are no more cards on the first pack of cards.

The problem asks to find the optimal algorithm for minimum stacks and prove that this one is the optimal. Thanks in advance.

Use the following strategy $S$: Put each card $c$ on the stack with the smallest top card $c'$ such that $c' > c$.

Consider a generic strategy $T$, and iteratively simulate $S$ and $T$.
Let $s_i = (s^i_1, s^i_2, \dots, s^i_{h_i})$ be the values on the top of the stacks after placing the $i$-th card $c_i$ according to strategy $S$, in increasing order. Define $t_i = (t^i_1, t^i,_2, \dots, t^i_{k_i})$ similarly for strategy $T$.

Claim: $\forall i=1,\dots,n$, we have: i) $h_i \le k_i$ and ii) $s^i_j \ge t^i_j$ for all $j = 1, \dots, h_i$.

The proof is by induction on $i$.
For $i=1$ we have $h_1=k_1=1$ and $s^1_1 = t^1_1 = c_1$.
For $i>1$ we have two cases.

Case 1) $S$ places $c_i$ in a new stack. Then, by hypothesis we must have $c_i > s^{i-1}_j \ge t^{i-1}_j$ for every $j = 1, \dots, h_{i-1} $. It follows that $k_i \ge h_{i-1} + 1 = h_i$, proving i). Notice that ii) is also verified since, for $j=1,\dots, h_{i-1}$, we have $c_i > s^i_j = s^{i-1}_j \ge t^{i-1}_j = t^i_j$ by induction hypothesis, and $t^i_{h_i} \le c_i = s^i_{h_i}$.

Case 2) $S$ places $c_i$ in an existing stack. Let $\ell$ be the index such that $s^{i}_\ell = c_i$.
We clearly have $k_i \ge k_{i-1} \ge h_{i-1} = h_i$, proving i).
As far as ii) is concerned, for every $j = 1, \dots, \ell-1$ we have $c_i > s^{i-1}_j \ge t^{i-1}_j$, and hence $s^i_j \ge t^i_j$.
Also, $s^i_\ell = c_i = \min\{s^{i-1}_\ell, c_j\} \ge \min\{t^{i-1}_\ell, c_j\} = t^i_\ell$.
Finally, for $j=\ell +1, \dots, h_i$, we have: $s^i_j = s^{i-1}_j \ge \max\{c_i, s^{i-1}_j\} \ge \max\{c_i, t^{i-1}_j\} \ge t^i_j$.

Instantiating the claim with $i=n$ yields $h_n \le k_n$, showing that $S$ is minimizing the number of stacks.


Solving $T(n) = 2T(n/3) + T(2n/3) + n^3$ How can I solve this recursive function using substitution method?
$$T(n) = 2T(n/3) + T (2n/3) + n^3$$
I substitute $T(n/3)$ and after that $T(n/9)$. when it goes to k-step, I'm stuck.

You can use the Akra-Bazzi theorem as
$$g(x) = n^3 \in O(n^c), a_1=2, a_2 = 1, b_1 = \frac{1}{3}, b_2 = \frac{2}{3}$$
So, just we need to find $p$ such that:
$$2\left(\frac{1}{3}\right)^p + \left(\frac{2}{3}\right)^p = 1$$
You can find the computation for finding $p$ here. It is around $1.4$. Now, we can write:
$$T(n) \in \Theta\left(n^{p}\left(1 + \int_{1}^{n}\frac{u^3}{u^{1+p}}du\right)\right)$$
To simplify the term, we can write:
$$
\int_{1}^{n}\frac{u^3}{u^{1+p}}du = \int_{1}^{n}u^{2-p}du = \frac{1}{3-p}u^{3-p} |_1^n = \frac{1}{3-p}(n^{3-p}-1)
$$
Now, by substituting this term in the main complexity term, we can conclude that $T(n) \in \Theta(n^3)$.


computer science vs computer programming? What's the difference between Computer Science and Computer Programming? I've spent nearly all my experience with compsci writing programs and what not, and I certainly like it, but I feel like there's a higher level I could pursue, like the ideas precede concrete programming.

I suppose my question is, what does it mean to be a computer scientist?

EDIT: I've done some thinking, and I have a somewhat more specific question-- what's the difference between the stuff on this stackexchange and the stuff on the cstheory stackexchange?

In some countries, for example in Latinoamerica, I found this "mixing" of terms for careers related to Computer Science, but let's consider that this is not your case and I will venture to pinpoint some differences about CS and CP that you are looking for:

Computer Science refers to the study of the theoretical part of the use of computers. Of course, that it has also its application part, but this is not directly related to programming. If you search for some articles in ACM you will find that there are a lot of authors that state that CS is not necessarily programming. If you choose this path you will be more studying topics more related to algorithms, math in its continuous and discrete flavors, statistics and so on. So I would dare to say that CS is more related to the fields I described before that only to programming.
Computer Programming, as I saw in some Universities as I said before, is more related to the technical field (or IT field according to the ACM standards). For example in a career related to this field, you will learn about the differences between Java, C, Ruby, etc., and you will increase your skills of using those tools, but not necessarily you will get a grasp of the generalities that those languages share (for example in CS you have a course called Programming Languages that deal with that).

So bottom line, CS refers to algorithms, math, theory and applications of this theory; while CP is related to the technical aspects of the different IT tools.


Concise example of exponential cost of ML type inference It was brought to my attention that the cost of type inference in a functional language like OCaml can be very high. The claim is that there is a sequence of expressions such that for each expression the length of the corresponding type is exponential on the length of the expression.

I devised the sequence below. My question is: do you know of a sequence with more concise expressions that achieves the same types?

# fun a -> a;;
- : 'a -> 'a = <fun>
# fun b a -> b a;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
# fun c b a -> c b (b a);;
- : (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>
# fun d c b a -> d c b (c b (b a));;
- : ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'd
= <fun>
# fun e d c b a -> e d c b (d c b (c b (b a)));;
- : (((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
   ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'e
= <fun>
# fun f e d c b a -> f e d c b (e d c b (d c b (c b (b a))));;
- : ((((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
     (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
    ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'e -> 'f) ->
   (((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
   ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'f
= <fun>

In this answer, I'll stick to a core ML fragment of the language, with just lambda-calculus and polymorphic let following Hindley-Milner. The full OCaml language has additional features such as row polymorphism (which if I recall correctly doesn't change the theoretical complexity, but with which real programs tend to have larger types) and a module system (which if you poke hard enough can be non-terminating in pathological cases involving abstract signatures).

The worst-case time complexity for deciding whether a core ML program has a type is a simple exponential in the size of the program. The classical references for this result are [KTU90] and [M90]. A more elementary but less complete treatment is given in [S95].

The maximum size of the type of the type of a core ML program is in fact doubly exponential in the size of the program. If the type checker must print the type of the program, the time may therefore be doubly exponential; it can be brought back to a simple exponential by defining abbreviations for repeated parts of the tree. This can correspond to sharing parts of the type tree in an implementation.

Your example shows exponential growth of the type. Note, however, that it is possible to give a linear-size representation of the type by using abbreviations for repeated parts of the type. This can correspond to sharing parts of the type tree in an implementation. For example:

# fun d c b a -> d c b (c b (b a));;
t2 -> t2
where t2 = (t1 -> 'b -> 'c) -> t1 -> 'a -> 'd
where t1 = 'a -> 'b

Here is a conceptually simpler example: the size of the type of the pair (x,x) is twice the size of the size of the type of x, so if you compose the pair function $N$ times, you get a type of size $\Theta(2^N)$.

# let pair x f = f x x;;
# let pairN x = pair (pair (pair … (pair x)…));;
'a -> tN
where tN = (tN-1 -> tN-1 -> 'bN) -> 'bN
…
where t2 = (t1 -> t1 -> 'b2) -> 'b2
where t1 = ('a -> 'a -> 'b1) -> 'b1

By introducing nested polymorphic let definitions, the size of the type increases again exponentially; this time, no amount of sharing can shave off the exponential growth.

# let pair x f = f x x;;
# let f1 x = pair x in
  let f2 x = f1 (f1 x) in
  let f3 x = f2 (f2 x) in
  fun z -> f3 (fun x -> x) z;;

References

[KTU90] Kfoury, J.; Tiuryn; Urzyczyn, P. (1990). "ML typability is dexptime-complete". Lecture Notes in Computer Science. CAAP '90 431: 206-220. [Springer] [Google]

[M90] Mairson, Harry G. (1990). "Deciding ML typability is complete for deterministic exponential time". Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '90 (ACM): 382–401. [ACM]

[P04] Benjamin C. Pierce. Advanced Topics in Types and Programming Languages. MIT Press, 2004. [Amazon]

[PR04] François Pottier and Didier Rémy. "The Essence of ML Type Inference". Chapter 10 in [P04]. [pdf]

[S95] Michael I. Schwartzbach. Polymorphic Type Inference. BRICS LS-95-3, June 1995. ps


Shuffling a file on disk using $O(\log n)$ memory How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place?

If the file had size $2^m$, then we can first split the file into 2-byte chunks, shuffle them individually, then shuffle each set of neighboring 2 chunks and merge, doing this recursively. Merging can be done using constant memory by reading the start of a chunk and swapping them with another.

But if the file size is not $2^m$ then the above doesn't really work, as for a 3-byte file the last byte cannot be in the middle position. (the chunks here are [1, 2] and [3]).

[EDIT] This doesn't generate all permutations as Yuval Filmus points out.

[EDIT 2] The paper "Random permutations on distributed, external and hierarchical memory" seems like a close match. Other refs/ideas welcome.

The algorithm you suggest doesn't result in a uniform permutation. An in-place algorithm which works for every file size is the Fisher–Yates shuffle.


Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2 The problem says:

Given an undirected simple graph G such that each node has at most d + 1 neighbors, color each node with one of d + 1 colors so that for each edge the two nodes have different colors.

Hint : don't think too hard. just color the nodes. what loop invariant do you need?

I was trying to solve this.. but quickly realized a complete graph of 4 vertices, whose vertices have at most 3 neighbors, cannot be colored with one of 3 colors so that each node has different color nodes.

I did some research and it seems like the book had a typo and it should have been "... each node has at most d neighbors, color each node with one of d + 1 colors... "

It is possible to find a graph with maximum degree of d + 1 that can be colored with d + 1 colors but this cannot be true for any graph with max degree of d + 1, right?

Am I correct in assuming that the typo should be corrected like how I did so AND about the last remark?

You're right that the statement is false. The correct statement states that every undirected simple graph in which each node has at most $d$ neighbors can be colored using $d+1$ colors so that each edge connects nodes having different color. Stated in more idiomatic language, every undirected simple graph of maximum degree $d$ can be (properly) colored using $d+1$ colors.


Count numbers that can be generated by flipping bits according to position intervals We have $M$ bits. $M\le10^5$ Also we have N ranges in the form $[L,R]$. $N\le10^5$ We can choose any range from the given ranges and flip all bits in our number from $L$ to $R$, both inclusive. We can apply each operation any number of times and in any order. We have to calculate the number of $M$ bit numbers that can be formed thus.

for Example if $N=3$
and our ranges are : $[0,0]$, $[1,1]$, $[2,2]$.
Now if we need to find number of three bit numbers that can be formed using the above restrictions, our answer would be 8, since we can form everything from 0 to 7.

Example 2: if we have 3 bits and two ranges $[0,1]$, $[1,2]$, we can form $4$ distinct numbers : $0 (000)$, $3 (011)$, $6 (110)$ and $5 (101)$.

I was thinking of doing something like if we could just obtain the $i^{th}$ bit as $1$ after performing some operations we could simply take $2^X$ for all such bits and that many numbers can be formed. But this approach doesn't seem to work in general.

Hint: For given $N$ and a range $[L,H]$, let $v \in \mathbb{Z}_2^N$ be the characteristic vector of $[L,H]$, i.e. $v_i = 1$ if $L \leq i \leq H$ and $v_i = 0$ otherwise. Given a list of ranges $[L_j,H_j]$ and correspond vectors $v_j$, how can you represent the characteristic vectors of all numbers reachable by the operations you mention? What is the relevant parameter?

Another hint: What happens if all $L_i$ are distinct? How can you handle cases in which $L_i = L_j$ for some $i \neq j$? Try to reduce it to the former case.


Why are those very similar languages in a different complexity class? i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and lecture notes/books, but couldn't find a reason for it. the languages are:

1.$NONEMPTY-INTER_{DFA}\:=\:\left\{<A_1,...,A_k> |\:A_1,...,A_k\:are\:DFAS\:and\:L\left(A_1\right)\cap...\:\cap L\left(A_k\right)\:\ne \varnothing \right\}$

2.$NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$

why is the second can be run in a polynomial time on a turing machine, and the first can not? would really appreciate an explanation for this.

It's because the running time to test $k$ DFAs, each of size $n$, is something like $\Theta(n^k)$.  This is polynomial when $k$ is fixed (like 2), but exponential when $k$ is not fixed (e.g., when $k=n$, you get something like $n^n$).

(We don't actually know for sure what the best running time for that is, but we suspect it's something like that; and that will explain why those similar-sounding problems have different complexity classes.  Likewise, we don't actually know for sure that P is a different complexity class from NP, but we suspect it is.)