How 2d cellular automata rules works? How 2D Cellular Automata rules sequences works?
For example, in elementary cellular automata, when we look at the binary sequence of the rule number, we understand that first bit says if all neighbors are white, and the cell itself is white, the cell in next step is black or white ( depend on the value of the bit ).

But how should I analyze and interpret the binary sequence of rule number? How should I implement the 2D CA when I have the rule number, for example when we have rule number 22369621 with r = 2 ( 25 neighbors ) how can I understand the behavior of this 2D CA to implement that?

When we interpret CA rules in a canonical form bijective with the naturals, it's convienient to think in terms of a lookup table array indexed by a neighborhood into the next cell state, or rather a truthtable with a variable from each of the neighborhood cells.

This works when the number of states is a power of two. If not a power of two, you need to use a mixed-radix encoding to remain bijective with the naturals.

The choice of 22369621 as an example rule hints that you haven't fully grasped how many potential rules there are with a neighborhood of 25 binary state cells mapping into the next binary state center cell. I assume this rule was chosen because its length up to the most significant one is 25, which shows you might be thinking that it only requires 25 bits to fully encode any rule from this type.

However, 25 (2-state) neighbors -> 1 (2-state) center cell requires in the worst case 2^25 bits, not 25.

Let's take a more simple example from the von Neumann neighboorhood: 5 (2-state) neighbors -> 1 (2-state) center. This requires at most 32 (2^5) bits.

So now let's take a random number within 32 bits, such as 3427859663.

In binary this is 11001100010100001111110011001111. We can intrepret these 32 bits as the next cell lookup for each of the configurations those 5 cells in the neighborhood can be in:

  a        *
b c d -> * f *
  e        *

~a ~b ~c ~d ~e ->  f
~a ~b ~c ~d  e ->  f
~a ~b ~c  d ~e -> ~f
~a ~b ~c  d  e -> ~f
~a ~b  c ~d ~e ->  f
~a ~b  c ~d  e ->  f
~a ~b  c  d ~e -> ~f
~a ~b  c  d  e -> ~f
~a  b ~c ~d ~e -> ~f
~a  b ~c ~d  e ->  f
~a  b ~c  d ~e -> ~f
~a  b ~c  d  e ->  f
~a  b  c ~d ~e -> ~f
~a  b  c ~d  e -> ~f
~a  b  c  d ~e -> ~f
~a  b  c  d  e -> ~f
 a ~b ~c ~d ~e ->  f
 a ~b ~c ~d  e ->  f
 a ~b ~c  d ~e ->  f
 a ~b ~c  d  e ->  f
 a ~b  c ~d ~e ->  f
 a ~b  c ~d  e ->  f
 a ~b  c  d ~e -> ~f
 a ~b  c  d  e -> ~f
 a  b ~c ~d ~e ->  f
 a  b ~c ~d  e ->  f
 a  b ~c  d ~e -> ~f
 a  b ~c  d  e -> ~f
 a  b  c ~d ~e ->  f
 a  b  c ~d  e ->  f
 a  b  c  d ~e ->  f
 a  b  c  d  e ->  f

Besides the approach of luts for CA, there are other data structures (or canonical numberings) that tend to remove the redundancies found in the most relevant designed rules that utilize large neighborhoods and especially non-power-of-two states. A good resource for more information about these techniques can be found at the Golly webpage.

http://golly.sourceforge.net/Help/formats.html

Some techniques listed there are:

Rule tables
Rule trees (also known as n-ary decision diagrams)


How to find whether a point is in a line or not Suppose in a given plain there are  fixed number of lines. A point P lies on one of the line. How to find which line intersects the point P ? I am giving an example

In the above graph point P is on the line CE. We can determine it visually.But my problem is how to make the computer understand it. Is there any algorithm available to make it so ?

Any finite line is described by two points. assuming we are talking 2D here, then your graph can be described as a set of points, having X and Y coordinations, and a set of edges $E$, which describe which pair of points are connected with a line. Elementary geometry tell us the function expressing the points on these lines is $Y=(X-X_0)\frac{Y_1-Y_0}{X_1-X_0}+Y_0$ ($(X_0,Y_0), (X_1,Y_1)$ denote the two point's coordinations)

To check whether a point belongs to this line, insert the point's coordinates to the equation and see if the equation holds. since the line is not infinite, we should also check if the point is between the two points defining the line. If the equation holds, it is sufficient to check if one of the point's coordinates (say $X$) is between the two point's defining the line ($X_0$ and $X_1$).

So, for any line in the graph, perform the check explained above, if the above criteria holds, the line contains P.

Checking if P is on a specific line takes constant amount of computational effort, so the running time of this procedure is $O(E)$.


Proof of lemma for flow in residual graph In CLRS 3'rd edition there is a Lemma 26.2 which states that:

Let $G=(V, E)$ be a flow network, let $f$ be a flow in $G,$ and let $p$ be an augmenting path in $G_{f}$. Define a function $f_{p}\colon V \times V \rightarrow \mathbb{R}$ by
$$f_{p}(u, v)=\left\{\begin{array}{ll}c_{f}(p) & \text { if }(u, v) \text { is on } p \\ 0 & \text { otherwise }\end{array}\right.$$
Then, $f_{p}$ is a flow in $G_{f}$ with value $\left|f_{p}\right|=c_{f}(p)>0$

How would you go about proving this?
As I understand we need to check for flow conservation and capacity constraint. We know that $c_f(p)$ is the minimum of the residual capacities on path $p$ which is smaller than the capacities, hence the capacity constraint is satisfied. But how about the flow conservation constraint and proving that the flow value is in fact $c_f(p) > 0$?

Observe that if $v$ is not a vertex of $p$, then $f_p(u,v)=0$.
When $v$ is in $p$ and not a source nor a sink, then there are only two vertices $v_1$ and $v_2$ such that the edges $(v_1,v),(v,v_2)$ are in $p$. Therefore, in the excess flow at $v$ $$\sum_u f_p(u,v)$$ only has two non-zero terms $f_p(v_1,v)=c_f(p)$ and $f_p(v_2,v)=-f_p(v,v_2)=-c_f(p)$.
So, the excess flow is zero.
To see that $c_f(p)>0$ just recall that it is defined as the minimum of the residual capacities of the edges of $p$. There are finitely many edges in $p$ and by definition of augmenting path the residual capacities of its edges are positive. So, you are taking the minimum of finitely many positive numbers. That results in a positive number.


Number of contiguous subsequences summing to a given target I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$.

For example, if $A = \{2,5,6,-1\}$ and $k = 5$ then the answer is $2$, since both $5$ and $6,-1$ sum to $5$.

Here is a simple randomized $O(n)$ time algorithm. We start by rephrasing your problem slightly. Suppose that the original array is $a_1,\ldots,a_n$. Form a new array $b_0,\ldots,b_n$ containing the running sums of the previous array:
$$
b_0 = 0, \qquad b_i = a_1 + \cdots + a_i.
$$
Notice that $a_i + \cdots + a_j = b_j - b_{i-1}$. Therefore we can rephrase the problem as follows:

  Given an array $b_0,\ldots,b_n$ and a target $t$, find the number of pairs $i<j$ such that $b_j = b_i + t$.

As an example, if $A = 2,5,6,-1$ then $B=0,2,7,13,12$, and for $t=5$ we get two solutions: $7 - 2 = 12 - 7 = 5$.

The idea now is very simple: we scan $B$ from left to right, and for each $b_j$, we count the number of values $b_j-t$ which have occurred previously, storing them using a hash table.

Initialize the count of solutions: $N \gets 0$.
Initialize a hash table $H$ containing a single entry: $B[b_0] \gets 1$.
For $j = 1,\ldots,n$:

If $b_j - t \in B$, let $N \gets N + H[b_j - t]$.
If $b_j \notin H$, let $H[b_j] \gets 1$, and otherwise let $H[b_j] \gets H[b_j] + 1$.

Return $N$.

The same algorithm can be implemented in deterministic $O(n\log n)$ time using a self-balancing binary search tree.


Time Complexity of Shifting I'm developing a IMHO very interesting algorithm for integer division. This algorithm uses boolean shifting(It shifts left for multiplication by 2). I'm wondering if << c is $O(c)$ or $O(n)$. I'm hearing it depends on architecture. Algorithms ideally should be architecture independent. So for the purposes of analysing the time complexity of my algorithm, should I consider << c as 1 primitive operation or c primitive operations.

I've looked at the other questions here, and they are saying it depends on the machine.

I'm using RAM model of computation, but don't want to assign << c a cost of 1 when it may in fact cost c.

In the RAM machine model, operations on "machine words" cost $O(1)$, where a machine word has width $O(\log n)$ bits, $n$ being the length of the input (in bits). This reflects the instruction sets of real world CPUs, as mentioned in the other answers.

While the RAM machine model makes sense for many algorithmic tasks, it is not a good fit for large integer arithmetic, since in practice the machine word is fixed while the integer length is growing. Instead, one usually measures bit operations. Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.

These issues are explored in a paper of Martin Fürer, the inventor of the fastest known integer multiplication algorithm (which is also the fastest known integer division algorithm).


Algorithm to find the two closest elements in a BST For example, consider an AVL tree:

Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, and their absolute difference will always be greater or equal to that of the result:

$|c_1-c_2|\leq |o_1-o_2|$, where $c_i$ are the two closest elements, and $o_i$ are any other two elements in the three.

I'm trying to think of an algorithm for this that can be done is O(log n). I can modify the nodes to store additional information, but not sure what I could use.

Specifically the algorithm, I am not sure about. Visually its evident, but algorithm wise I would like a hint.

In most common models of computation, it cannot be ensured to find the two closest elements in a binary search tree (BST) in $O(\log n)$ time or, in fact, in $o(n)$ time. Here $n$ is the number of elements in BST and $o(n)$ is the little $o$-notation.

The idea is simple. There must be enough running time for an algorithm to access at least about half of the elements.

Here is an detailed explanation. It is not rigorous;  to make it rigorous we will need an explicit adversary argument as well as a more detailed formal specification of the model of computation.

Let us fix some model of computation $M$ in which at most $c$ elements can be accessed in a unit time of computation for some constant $c$. In fact, $c$ is usually 1 or 2.

For the sake of contradiction, suppose algorithm $Alg$ can find the two closest elements in a BST of $n$ element in $o(n)$ time. So for constant $\dfrac1{3c}$, there exists a constant $n_0>0$ such that $A$ can find the two closest element in no more than $\dfrac1{3c}n$ time for all $n>n_0$.

Now let $n_1>\max(n_0, 6)$. Let $Alg$ runs on a BST with $n_1$ nodes for some time that is no more than $\dfrac1{3c}n_1$. Then $A$ has accessed at most $\dfrac{1}{3c}n_1\cdot c=\dfrac {n_1}3$ elements.
Let $a_1, a_2, \cdots, a_{n_1}$ be the elements in the BST in nondecreasing order. There must be at least 2 adjacent elements in that nondecreasing list of all elements none of which have been accessed by the algorithm. Those two elements mights be closer to each other than any pair of elements among the elements that have been accessed by $Alg$. That means, $Alg$ may not have found the two closest elements. This is a contradiction.

Exercise. Find the two closest elements in a binary search tree with left-child pointers, right-child pointers and parent pointers in $O(1)$ working space.


Ford-Fulkerson vs Edmonds-Karp I was reading about maximum flow algorithms comparing the efficiency of the different ones. On the Wikipedia Ford-Fulkerson algorithm page, they present the Edmonds-Karp algorithm as the BFS (instead of DFS) variant of Ford-Fulkerson algorithm.

The point is on time complexity, Ford-Fulkerson algorithm has $O(|E||f_{max}|)$ whereas Edmonds-Karp is presented to run in $O(|V||E|^2)$. My main is question is then, how can I decide which of these algorithm is the faster on an arbitrary max-flow problem ?

I feel very unconfortable with the $f_{max}$ even if I understand it, because determining it is the goal of the algorithm so estimating it is likely to be hard on the very general case. Depending on problem, $f_{max}$ may be very high with respect to $|E|$, even if one can possibly apply a scale factor on all edges.

I also do not understand where the runtime difference comes from. Generally BFS and DFS have the same expected runtime, the difference between them is more on problem dependant space requirement and features like shortest path, topological order...

Edmonds-Karp is a specialisation/elaboration of Ford-Fulkerson, so any bound for the latter also applies to the former.  In other words, EK is $O(|E|\min(f_{max}, |V||E|))$ time (and writing it this way does add information, since $f_{max}$ can be much smaller than $|V||E|$ -- and this is the only time when you might otherwise consider using some other variant of FF in preference to EK).

The above does not imply that EK is faster than a particular (say, DFS-based) variant of FF on any particular instance.

BFS and DFS have the same runtime, but DFS only promises to find a path from source to sink in the residual graph -- not necessarily a shortest possible such path, which BFS does promise.  It's possible to show that no modification to the residual graph ever reduces the distance from the source to any vertex; with this, and the fact that BFS always finds a shortest path, it's possible to show that after finding at most $|V||E|$ augmenting paths, no source-to-sink path remains in the residual graph.  This page gives a full proof -- I've only skimmed it, but note that when it says that "That is, [the distance from the source to all other nodes] is always increasing", it in fact means (or should mean) that this never decreases -- that is, the distance from the source to a particular node can stay the same after an augmentation, or it can be larger, but it can never be smaller.


Why doesn't the C/C++ compilers create different tokens for different types of numbers? Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for float/int etc.

However if we have something like this:

int A[10.5];

then will there be a parser error or semantic error?

The book that I'm reading says the parser rather than the semantic routines will detect it, but after the lexical analysis wouldn't that be converted to this:

A[Constants];

meaning the 10.5 will be converted to a Constants token based on that website? Therefore the parser will not notice this is an error because both of 10 and 10.5 will be Constants!

So which one is right? Will the parser or one of the semantic routines detects this error? Do the C/C++ compilers create the same tokens for int numbers and floats?

This is in fact an implementation detail of the compiler. The page you referenced only shows one way of assigning types to tokens, while there are also others. The compiler could have a lexer that distinguishes between integral and non-integral constants and the parser then cannot match the declaration

int A[10.5];

to any rule. But giving an error message stating exactly this to the programmer is not very helpful. Modern C++ compilers have quite complex parsing and compiling routines that give more information in case of errors. As an example, GCC will yield:

me@my-computer:/tmp$ g++ test.cpp
test.cpp: In function ‘int main()’:
test.cpp:9:15: error: size of array ‘A’ has non-integral type ‘double’
     int A[10.5];
           ^

So you will get quite a good error message, and for obtaining it, some semantic interpretation was actually performed.


How to do if a potential function Does not work? Amortized analysis Here is an example taken from CLRS.

q)Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O(lg n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT is O(lg n) and the amortized cost of EXTRACT-MIN is O(1), and show that it works.

$\Phi(H) = 2 \cdot (size of heap = n) = 2n$

insert:

the amortized cost has the formula

$a_n = c_n + (\Phi_{n+1}) - \Phi_n$

$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$

holds ?

$a_n = c_n + (\Phi_{n+1}) - \Phi_n$

$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$

delete is a bit different because after operation n goes down by 1 hence

$a_n = c_n + (\Phi_{n+1}) - \Phi_n$

$= log(n) + 2(n) - 2(n+1) = log(n) - 2 = log(n)$

so delete is obviously wrong since its not O(1) but insert gave correct one. How do I properly show a potential function being incorrect? Is it enough to just show this? Note: I'm not looking to solve the above question just looking how to disprove potential functions.

When you delete, your $actual$ $cost$, or $c_n$ by your notation, is $log(n)$.

it means you want: $\Delta \phi = \phi_{n+1}-\phi_n \approx -log(n)$

Its not hard to find such potential function that satisfies both:

try $\phi = nlog(n)$

for insert:

$Cost_{insert} = log(n) + (n+1)log(n+1) - nlog(n)$

$= log(n)+log(n+1)+nlog(n+1)-nlog(n) = O(log(n))$

$Cost_{delete} = log(n) + (n-1)log(n-1) - nlog(n) $

$= log(n)-log(n-1)+nlog(n-1)-nlog(n) $

$\leq (log(n)-log(n)) +(nlog(n)-nlog(n)) = O(1)$

All potential functions that satisfy $\phi(i) \geq 0 $, $\phi(0)=0 $ are correct, they just may not prove the amortized time you have in mind.


If declarative programming is possible at the instruction/action level? I am considering what the possibilities are with declarative programming. I have a firm understanding of how to use declarative programming in practice, but, short of having examples, I don't know if it's possible to 100% use declarative programming all the way down to the machine code (theoretically).

Standard QA sites like this says stuff like:

  it means describing the problem to be solved, but not telling the programming language how to solve it

A typical example is a SQL query which uses a where clause to define the query rather than implementing the query it step-by-step using something like an iterative loop.

An example I am interested in is an even higher level abstraction than a SQL query: defining an HTTP server. You can define the server and all of it's GET handlers (if we just limit it to that for now) in a completely declarative way, as seen by many declarative frameworks. The declarative frameworks that do similar stuff to this are the ones like Terraform or SaltStack that define machine configurations/states. You are basically defining the state the machine should look like, and the system takes your "definition" and makes it happen.

For the HTTP server you can do like in React:

<Route path='/' component={Home}>
  <Route path='/about' component={About}>
  <Route path='/terms' component={Terms}>
  ...
</Route>

This then automagically gets wired up into a listening server for these changes, and renders the components (this API may not be exact, just pseudocoding it ftm).

In fact, there is a lot that can be done declaratively. HTML and CSS together form an animatable graphics display and is completely declarative. You can define servers, machines, parsers (PEG parser generators), graphics... I don't know what else.

That's mainly what my question is, what can be done declaratively. More specifically, what cannot be done in a declarative fashion. The stereotypical example I am thinking of is simply defining a step-by-step sequence of actions of some sort, but in a declarative, non-iterative way. Is it possible?

Here is my attempt.... Say we are describing some automation steps for interactively going through and clicking around a website. Here is the iterative way:

Visit "/"
Click on "Button 1"
Wait "2 seconds"
Click on "Button 2"
For each "Input" in "Fields"
  Type into "Input"
Click on "Button 3"
Wait "2 seconds"
...

This is similar to assembly instructions like mov. But can this be done in a declarative way (that is also readable and easy to understand)? Does functional programming offer any insight? Maybe one could show how to do this in a functional programming paradigm, or even a logic (prolog-ish) way, if that would help illuminate how it's done. My attempt at declarative is like this:

Current State should be "/"
Button is not clicked
Button has been clicked
2 seconds have passed
...

Basically, just stating the "states" before and after each step sort of thing. That makes it harder to read, and it feels like you are trying to hack around having to build some iterative code anyways. It's like it has to be iterative. Is that so? Is there any way to make this non-iterative and so it still makes sense?

To me, currently, it seems that you can use declarative programming for like 80-90% of things, but then you inevitably need "parsing" code which will take those declarative statements and interpret them, converting them into some iterative sequence. But what I'm left wondering is, can that 10-20% that seems to have "iteration" as a requirement be instead written declaratively? Can you take that 10-20% remaining iterative code and make that declarative too? If so, how would that look or what is the technique?

Machine code is imperative, not declarative, so if you want your code to execute on a conventional CPU, at some point there needs to be some code that converts the declarative program to imperative style (e.g., a compiler), and at least some of that code needs to be written imperatively (because at least some of it needs to be written in machine code).  It can't be turtles all the way down.


which of the following languages are Recursively Enumerable? Which of the following languages are recursively enumerable?

A={⟨M⟩∣ TM M accepts at most 2 distinct inputs}

B={⟨M⟩∣ TM M accepts more than 2 distinct inputs}

For first language I think that we can enumerate all the TM's which accept at most 2 distinct inputs using dovetailing method and same is the case with B language.

But on the contrary, both languages are complement of each other so if one is R.E then other one cannot be. So I know that I am going wrong somewhere.

Can someone please explain me how to find if these languages are R.E ?

$B$ is r.e, but $A$ is not.

You can construct a TM which takes as input $M$ and simulates $M$ on every string of $0$ and $1$ in canonical order for each step $n$. In other words, if $s_1, s_2,...$ are strings on $0$ and $1$ in canonical order, then starting from $n=0$ you run $M$ for $n$ steps on $s_1, s_2,..., s_n$, that is, for each $n$ run $M$ on all $s_1, s_2,..., s_n$ for $n$ steps (not just 1 step for $s_1$, 2 steps on $s_2$,... careful!). Each time just check if a string is accepted. If more than two strings are accepted then halt with accept, otherwise go on.

However we cannot use the same approach for $A$ since we cannot check infinitely many strings and say that they are not accepted except 1 or 2 certain strings IN FINITE amount of time. In other words, suppose we somehow determined that $M$ has accepted two strings, then how can we decide that the rest of infinite number of strings are not accepted by $M$ in finite amount of time?

You can also use the Rice's theorem for recursive index set.
$A$ violates the containment property in the Rice's theorem. Namely, if $L$ is in $A$ and $L \subseteq L'$ for some r.e. $L'$, then $L'$ is in $A$. Assume $L=\{00, 11\}$. Then $L$ is in $A$. Let $L'=\{00,11, 01, 10\}$. Then $L \subseteq L'$ where $L'$ is clearly r.e. But $L' \notin A$.

Update (upon comment)

Task: We want to systematically simulate each TM on every input on $\{0, 1\}$.

Solution: First note that there is a one-to-one correspondence $f$ between the set of natural numbers $N$ and $N^3$ all 3-tuples of natural numbers. So, we can effectively convert each integer $m$ into the corresponding 3-tuple $<i,j,k>$. This means that if we start to count all integers then we can enumerate all possible 3-tuples, so that each 3-tuple is eventually reachable in a finite amount of time.

Now, assume we we have fixed enumerations of all TMs and strings on $0$ and $1$, e.g., $M_i$'s and $s_j$'s.

1) Set $n =0$

2) $<i, j, k> = f(n)$  <= compute 3 tuple

3) Simulate the Turing machine $M_i$ on input $s_j$ for $k$ steps.

4) If $M_i(s_j)$ halts (after $k$ steps) then do whatever you want to do

5) increase $n$ by 1 and go to step 2)

Thus, every machine "has a chance" to run on every input for arbitrary number of steps, fair isn't it?

If some machine, say, $M_{332}$ halts on input $s_{12}$ then there is an integer, say, $461$, so that $M_{332}(s_{12})$ halts in 461 steps. So, if for example $55993$ corresponds to the 3-tuple $<332, 12, 461>$, then when $n$ reaches $55993$ (in the algorithm above) you detect that $M_{332}$ halts on input $s_{12}$.


Probability that a leaf with 1 will be selected in game tree evaluation I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar).

                          (OR) = 1
                          /  \
                         /    \
  Possible inputs:      1      1
                        0      1
                        1      0

You can find detailed description of the problem in this lecture notes or in Randomized Algorithms, pg. 29, by Motwani&Raghavan. Basically, given the OR-node and inputs $0$ or $1$ we evaluate the value of the OR-node by inspecting the input values (leaves). For example if the input is $1$ and $0$ then after reading the first value, $1$, we do not need to read the second value, and hence only one read will need to be done. On the other hand, if the input is $0$ and $1$ then after the reading the first value we still need to read the second value (since it may be equal to $1$).

Randomized version of evaluation tosses an unbiased coin and with probability $0.5$ reads the first input value or the second. So, the problem is, given that the OR-gate has output $1$, to compute the expected number of reads.

Both the lecture notes and the book computes it as following

  If the node is to return a $1$, then at least one of the leaves must return a $1$. With probability $1/2$ this leaf will be selected first and only one evaluation will need to be done. The other possibility
  (also occurring with probability $1/2$) is that both leaves will need to be evaluated. The expected number of evaluations,
  $E^{OR}_1$, is given by $$ E^{OR}_1 = \left(\frac{1}{2} \times 1\right) + \left(\frac{1}{2} \times 2\right) = \frac{3}{2}$$

However, I compute it differently. The probability that a certain leaf is selected is $1/2$, but since we have three possible inputs the probability that the selected leaf has value $0$ is different from the probability that it is $1$. In particular $P(value=1)=2/3$ and $P(value=0)=1/3$. In other words, the probability that a leaf with  $1$ will be selected is slightly greater than $1/2$. I'm probably missing something. Could someone explain what is wrong with my approach?

When you talk about probabilities, you should first decide what is actually random. Note that there are two possible sources of randomness here, the value of the leaves (i.e. were talking about some distribution over the possible inputs), and the random choice of what leaf to evaluate first (i.e. inner randomness of your algorithm).

When we say our algorithm is randomized, we usually mean the latter. The complexity of such an algorithm is considered with respect to the worst possible input. More formally, saying that the algorithm runs in expected time $T$, means that $T=\max\limits_{i\in I}\mathbb{E}\left[T(i)\right]$, where $I$ is the set of possible inputs and $T(i)$ is the running time on input $i$ (which is a random variable, since we have a coin-tossing algorithm). This is a worst case complexity measure, as the probabilistic analysis is done relative to the worst possible input. Here the worst case (conditioning on the output being $1$) is that exactly one leaf evaluates to $0$, and in this case the expected number of evaluations is indeed $\frac{3}{2}$.

The analysis you described corresponds to the former option, i.e. we are interested in average-case complexity, relative to the uniform distribution over possible inputs (so we actually have two sources of randomness here). In this case, conditioning on the output being $1$, you are right to say that the value of a leaf is $1$ with probability $\frac{2}{3}$, which makes the expected running time $\frac{4}{3}$ (where the expectation is taken over the leaves values and the coin outcome).


Program compilation and execution flow I was studying operating system concepts from Silberschatz, Galvin and Gagne's book (sixth edition) and I have some questions about the flow of execution of a program. A figure explains the processing of the user program:

We get an executable binary file when we reach the linkage editor point. As the book says,

  The program must be brought into memory and placed within a process for it to be executed.

I have several questions about this flow:

Before the program is loaded into the memory, the binary executable file generated by the linkage editor is stored in the hard disk. The address where the binary executable file is stored in the hard disk is the logical address as generated by the CPU ?
If the previous answer is yes, Why CPU has to generate the logical address ? I mean the executable file is stored somewhere in the hard disk which pertains to an address, why does CPU has to separately do the stuff ? CPU's main aim is processing after all!
Why does the executable file needs to be in the physical memory i.e ram and can not be executed in the hard disk? Is it due to speed issues ?

First of all, you are fundamentally confusing the purpose of RAM and hard disk. RAM is the only part of memory that CPU can access. Hard disk exists to expand the capacity of RAM as well as store the data permanently (data on RAM is transient).

How it works -

The computer generates an executable and stores it in the hard disk. It is just a passive program right now.
Another process (already in memory and currently running) calls the program you just created using the access path (full psth + name) in the filesystem. This is a system call; an interrupt is issued and control is transferred to OS.
OS decodes the path to get the actual location(s) on hard disk where the program data blocks are stored. Hard disk is treated as any other I/O device; it vouches for CPU time like any other I/O device. Here, OS has two choices:

either it needs to fetch data from hard disk each time hard disk has some to give (hard disk announces it by issuing interrupts) and store it in RAM. But with ever faster hard disk speeds nowadays, frequency of interrupts can be high enough to be inefficient for CPU.
second option is that CPU, while issuing the read command for program data blocks, also specifies the RAM memory addresses to which hard disk should directly copy its data (Direct Memory Access). Since CPU, I/O devices (including hard disk) and memory all share common bus, data can be transferred one at a time. Moreover, CPU meanwhile also has other processes (in RAM) to run while data is being copied by hard disk to RAM. Thus, both CPU and hard disk take turns when copying data to RAM. Here, DMA would be faster if CPU is idle or requires less memory accesses. When hard disk has completed writing data to RAM as specified by CPU, it issues interrupt to CPU to tell it that it has completed its task.

Take note above that CPU has never accessed the data of hard disk directly. The hard disk works the same way as any other device like keyboard or modem would work (via interrupts etc). Now after hard disk has copied data and interrupt generated, OS assigns stack memory and other resources for this newly created process and inserts it into the queue of active processes.

That is why when creating small beginner programs, we can never save the state of programs. We create some variables while the process is running and modify them, but never explicitly store them on the hard disk (unless engaging with the file handling aspect). When we destroy the program all the memory is lost. and all the read, write operations of a language are merely wrappers around the system calls provided by the OS so as to make the code portable across several operating systems (since system calls of each are different). These read/write/open/close system calls are requests for OS to let us access a file on hard disk, different from the RAM.

As to your question about logical addresses, it is a little ambiguous as to what you want to say. Logical addresses are used in reference to RAM by programs, and usually refer to the program's view of its memory. For a program, its logical addresses may start from 0, but that doesn't translate into the fact that all programs start at physical address 0 of RAM! You are right that CPU has to process data, but it needs some data at all to process, with is stored in RAM. The addresses provided by program code are logical (say, get data stored in location '7 + start of program') and CPU has to calculate its actual physical address to work upon (i.e. replace 'start of program' with the base address of process code blocks in RAM).

Thus, logical addresses have nothing to do with hard disks.


How to satisfy bounded waiting in case of deadlock? I have a doubt regarding bounded waiting.

Deadlock implies no Progress because the processes take indefinite time to decide who will enter the critical section .

But, Does deadlock implies no bounded waiting ?

I think No because bounded waiting is per process and deadlock is for the system.

Moreover, In a deadlock, bounded waiting conditon is not violated and bounded waiting is not with respect to time, but with respect to the number of times the processes enter the critical section before intended process enters the critical system .

Would anyone at least care to correct me or suggest what is right and not right?

You are correct.

Consider the simple synchronization algorithm which denies entry to all processes.

In this case we have both deadlock and bounded waiting, since any process $p$ is not bypassed by some process $p'$ before entering the critical section, so you could say bounded waiting is satisfied with the constant function $f=0$.


Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm) I want to reconstruct a graph when given the results of a Floyd-Warshall shortest pair distances matrix, similar to the problem being solved in this question:

Is it possible to reconstruct graph if we have given matrix of shortest pairs

The only difference being that, whilst the problem from the linked-to question seeks to find a graph of $N-1$ edges, I want to produce a graph containing $N$ edges.

I've already found a more efficient way of solving the problem from the question linked above. Instead of using the solution offered there, I have found that building a minimal spanning tree also yields the correct result, namely a graph of $N-1$ edges that, when given as input to the Floyd-Warshall algorithm, produces exactly the matrix of minimum distance pairs with which we started.

Now we have one edge left to add. This is the part I am unable to figure out. It boils down to this:

I have a graph of $N-1$ edges, which is represented by a matrix of shortest pair distances. Out of a list of candidate edges, how can I efficiently (i.e. without brute forcing) find which edge to add that does not change even a single value in the matrix, preserving all minimum distances?

Thanks!

Pick any pair of vertices $u,v$ where it is possible to reach $v$ from $u$.  Add an edge $u \to v$ with a length that is really large.


What would be a decent threshold for classification problem? I'm using machine-learning algorithms to solve binary classification problem (i.e. classification can be 'good' or 'bad'). I'm using SVM based algorithms, LibLinear in particular. When I get a classification result, sometimes, the probability estimations over the result are pretty low. For example, I get a classification 'good' with probability of 52% - those kind of results I rather throw away or maybe classify them as 'unknown'.

EDITED - by D.W.'s suggestion

Just to be more clear about it, my output is not only the classification 'good' or 'bad', I also get the confidence level (in %). For example, If I'm the weather guy, I'm reporting that tomorrow it will be raining, and I'm 52% positive at my forecast. In this case, I'm sure you won't take your umbrella when you leave home tomorrow, right? So in those cases where my model does not have a high confidence level I throw away this prediction and don't count it in my estimations.

Unfortunately, I can't find articles regarding thresholding the probability estimations...

Does anyone have an idea what is a normal threshold that I can set over the probability estimations? or at least can refer me to a few articles about it?

There is no universal answer.  Instead, it depends on your application.  What counts as useful for your application?  That determines what should count as a useful or good-enough machine learning algorithm.  What counts as useful will vary widely from application to application; some applications require 99.99% accuracy, others might be happy with 52% accuracy.

In practice, there are also multiple ways to define accuracy.  If you expect that (in the ground truth) half of the objects should be classified 'good' and half as 'bad', then the obvious accuracy measure suffices, i.e., counting what fraction of instances your classifier outputs the correct answer.  However, if 'good' objects are a lot more common than 'bad' objects, or if the penalty for mis-classifying a 'good' object as 'bad' is very different from the penalty for mis-classifying a 'bad' object as 'good', then you might want to measure accuracy differently.  The best measure of accuracy is again application-dependent; there is no single universal answer.


What is the relationship between minimum vertex cover and minimum clique cover Question:
 What is the relationship between minimum vertex cover of a graph G and minimum clique cover of conflict graph of G?

Thanks!

I believe the minimum vertex cover of G is equivalent to minimum clique cover of the conflict graph of G, or their sizes are  equal, but today I find a counterexample.

Example: in the figure below, a minimum vertex cover is {1, 2}, but the minimum clique cover contains one partition, that is vertext set {$e_1, e_2, e_3$}. The size of minimum vertex cover is 2, while the size of minimum clique cover is 1.

A graph is an ordered pair G = (V, E) comprising a set V of vertices, nodes or points together with a set E of edges, arcs or lines, which are 2-element subsets of V (i.e., an edge is associated with two vertices, and the association takes the form of the unordered pair of the vertices).

A vertex cover of a graph G is a set S of vertices of G such that every edge of G has at least one of member of S as an endpoint.

A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph.

A conflict graph is the graph G = (V, E) where every edge in E is represented by a vertex. Two vertices are adjacent if and only if the edges in E these vertices correspond to intersect each other.

A clique cover or partition into cliques of a graph is a partition of the vertices of the graph into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible.

The minimum clique cover of the conflict graph is at most the minimum vertex cover of the original graph. In other words, if the original graph has a vertex cover of size $k$, then the conflict graph has a clique cover of size $k$. This is essentially because all edges adjacent to a vertex in the original graph constitute a clique in the conflict graph (though as the example of the triangle shows, there are also other cliques in the conflict graph). Details left to you.


Implications of $NL=P$ What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you

$NL = P$ means that every language in $P$ can be decided by a nondeterministic Turing machine using at most $O(\log n)$ space, where $n$ is the size  of the input.

Savitch's theorem states for all $f(n) \in \Omega(\log n)$: $NSPACE(f(n))\subseteq SPACE(f(n)^2)$.

Therefore $NL = P$ implies that every language in $P$ can be decided by a deterministic Turing machine using at most $O((\log n)^2)$ space.


Finding median weights in all paths of an AVL tree with weighted nodes I need some help with proving the complexity of the following problem
(I'm new here, so please excuse my "newbie-ness")

Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree has the parameter $w_i$ (which is an integer)

The task: To make an algorithm which returns an array of size $n$ such that  in the cell $i$ there is the median value of all the $w_i$ of all the nodes from the root of the AVL to the node $i$.

Running time: $O(n\log\log n)$

My solution:

For each node among the $n$ nodes in the AVL, I build a separate AVL containing the $O(\log n)$ nodes(because the depth of each node is $O(\log n)$) on the path to it from the root.
Each insertion to an AVL takes $O(\log n)$ ($n$ = number of nodes), but number of nodes here is $O(\log n)$, therefore, each insertion takes $O(\log\log n)$, and since there are $n$ nodes, then building the $n$ AVLs takes $O(n\log\log n)$
Finding the median for each AVL takes $O(\log n)$ (using Select) since there are $O(\log n)$ values in the tree. Then, we put in the output array at the cell $i$ the median value which we just found.

Thus, building each AVL and finding the median, is done in $O(\log(n) + \log\log n)  = O(\log n)$.

My Question:
I'm uncertain about step 2 in the described algorithm above: does building the $n$ AVL trees takes actually $O(n\log\log n)$ running time?

Your main AVL tree has $n$ nodes. On each you build a small AVL tree with a nomber of nodes bounded by $\log n$, so that the insertion of each node on the small AVL tree has a cost $\log\log n$ steps. Overall that makes $O(n\log n\log\log n)$ steps, not $O(n\log\log n)$ as stated in your step 2.


Recurrence problem T(n) = 2T(n − 1) + 1 Can I solve T(n) = 2T(n − 1) + 1 using the master theorem method?
I don't think it cannot be solved with the master theorem because b=1.
Please let me know, if my guess is wrong.

Here are several ways of solving this recurrence. Throughout, I will assume that $T(0) = 0$.

Method 1: Guessing

Here are some values of $T(n)$:
$$
\begin{array}{c|cccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 \\\hline
T(n) & 0 & 1 & 3 & 7 & 15 & 31
\end{array}
$$
If you're familiar with powers of 2, you will recognize that $T(n) = 2^n-1$. If not, you can look it up on the Online Encyclopedia of Integer Sequences, where you will find it as A000225, under the name Mersenne numbers.

Method 2: Homogenization

We look for a related recurrence without the "$+1$". The first think one could try is replacing $T(n)$ with $S(n) = T(n) + C$, which satisfies the recurrence
$$ S(n) = T(n) + C = 2T(n-1) + C + 1 = 2S(n-1) - C + 1. $$
We see that if $C = 1$ then $S(n) = 2S(n-1)$, and so $S(n) = 2^n S(0) = 2^n$. We conclude that $T(n) = 2^n - 1$.

Method 3: Reduction

The recurrence makes it clear that the first order asymptotics of $T(n)$ should be related to $2^n$, and so suggests considering $R(n) = T(n)/2^n$, which satisfies the recurrence
$$ R(n) = \frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + \frac{1}{2^n} = R(n-1) + \frac{1}{2^n}. $$
This shows that
$$
R(n) = R(0) + \sum_{m=1}^n \frac{1}{2^m} = 1 - \frac{1}{2^n},
$$
and so $T(n) = 2^n - 1$.

If we are only interested in the asymptotics, we could notice that since the series $\sum_{n=1}^\infty \frac{1}{2^n}$ converges, we clearly have $R(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.

Method 4: Generating series

We could also solve the recurrence automatically using generating series. Let
$$ P(x) = \sum_{n=0}^\infty T(n) x^n. $$
Then
$$ P(x) = T(0) + \sum_{n=1}^\infty T(n) x^n = 2\sum_{n=1}^\infty T(n-1) x^n + \sum_{n=1}^\infty x^n = 2xP(x) + \frac{x}{1-x}. $$
We conclude that
$$ P(x) = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x} = \sum_{n=0}^\infty (2^n - 1) x^n. $$
Therefore $T(n) = 2^n - 1$.

Method 5: Combinatorial interpretation

This method is more creative. We find some combinatorial object which we already know how to count, and we show that it satisfies the same recurrence. In this case, we could choose all non-empty subsets of $\{1,\ldots,n\}$. Each such subset is either obtained from a non-empty subset of $\{1,\ldots,n-1\}$ by either adding or not adding $n$, and additionally the subset $\{n\}$, which does not arise in this way. The base cases also match, and so $T(n) = 2^n - 1$.


How to calculate the number of tag, index and offset bits of different caches? Specifically:

1) A direct-mapped cache with 4096 blocks/lines in which each block has 8 32-bit words. How many bits are needed for the tag and index fields, assuming a 32-bit address?

2) Same question as 1) but for fully associative cache?

Correct me if I'm wrong, is it:

  tag bits = address bit length - exponent of index - exponent of offset?

  [Is the offset = 3 due to 2^3 = 8 or is it 5 from 2^5 = 32?]

The question as stated is not quite answerable.  A word has been defined to be 32-bits.  We need to know whether the system is "byte-addressable" (you can access an 8-bit chunk of data) or "word-addressable" (smallest accessible chunk is 32-bits) or even "half-word addressable" (the smallest chunk of data you can access is 16-bits.)  You need to know this to know what the lowest-order bit of an address is telling you.

Then you work from the bottom up.  Let's assume the system is byte addressable.

Then each cache block contains 8 words*(4 bytes/word)=32=25 bytes, so the offset is 5 bits.

The index for a direct mapped cache is the number of blocks in the cache (12 bits in this case, because 212=4096.)

Then the tag is all the bits that are left, as you have indicated.

As the cache gets more associative but stays the same size there are fewer index bits and more tag bits.


Variable Length Encoding of Integers I was just researching Fibonacci encoding of integers. Numbers are encoded in binary and where no two consecutive bits are equal to 1 - other than to terminate the number.

Now other schemes are possible, for example having three or more 1's terminating the number. These representations are more efficient (shorter) for larger numbers but less so for small numbers.

My question is, is it possible to have an optimal scheme where the number of terminating 1's increase as the size of the number increases? And have no ambiguity.

Some examples to clarify:

a. 0 = '1', 1 = '01', 2 =  '001', 3 = '0001', 4 = '00001', 5 = '000001', 6 = '0000001'

b. 0 = '11', 1 = '011', 2 = '0011', 3 = '1011', 4 = '00011', 5 = '10011', 6 = '01011'

c. 0 = '111', 1 = '0111', 2 = '00111', 3 = '10111', 4 = '000111', 5 = '100111', 6 = '010111'

These use 1, 2, and 3 terminating 1's respectively.

There is no optimal scheme for encoding integers. To understand what this statement even means, we need a few definitions.

A codeword $w$ is a word over the alphabet $\{0,1\}$.

A sequence of codewords $w_0,w_1,w_2,\ldots$ is a code.

A code $w_0,w_1,w_2,\ldots$ is prefix-free if no $w_i$ is a prefix of any $w_j$ for $i \neq j$.

A code $w_0,w_1,w_2,\ldots$ is monotone if $|w_0| \leq |w_1| \leq |w_2| \leq \cdots$.

An integer encoding scheme is a monotone prefix-free code.

An integer encoding scheme $x_0,x_1,x_2,\ldots$ is better than an integer encoding scheme $y_0,y_1,y_2,\ldots$ if $|x_i| - |y_i| \to -\infty$.

The codes that you give are examples of integer encoding schemes which get progressively better.

Theorem. For any integer encoding scheme $y$ there is a better integer encoding scheme $x$.

In fact, the situation is even worse: there is no optimal sequence of codes:

Theorem. For any sequence $y_1,y_2,\ldots$ of integer encoding schemes there is an integer encoding scheme $x$ better than all of them.

For proofs see, for example, this paper.

Elias came up with a sequence of codes, including the gamma and delta codes, which are progressively better, culminating in the limiting omega code; but even this code isn't optimal.


FOL substitution - is it possible to substitute two variables with each other? e.g. $\theta=\{x/y,y/x\}$? Let $C = m(P,X,Y) \leftarrow m(Q,X,Z), m(R,Z,Y)$.

Is it possible to do the following substitution?

$D = C\theta$ where $\theta = \{Q/R,R/Q\}$ s.t. $D = m(P,X,Y) \leftarrow m(R,X,Z),m(Q,Z,Y)$

Given the usual substitution function $[x/y]$ s.t.

  $M[x/y]$ is the result of substituting all free occurrences of '$y$' with '$x$' in $M$,

your desired function can be defined as follows:

  $M [x//y] =_{df} M[x'/y][y/x][x/x']$ provided $x'$ doesn't occur in $M$.

Example. Let $C = m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)$. Then:

\begin{align*}
D &= C~[Q~//~R]\\
&= [m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)][Q'/R][R/Q][Q/Q'] \\
&= [m(P,X,Y)←m(Q,X,Z),m(Q',Z,Y)][R/Q][Q/Q']\\
&= [m(P,X,Y)←m(R,X,Z),m(Q',Z,Y)][Q/Q']\\
&= m(P,X,Y)←m(R,X,Z),m(Q,Z,Y)
\end{align*}


Example of an algorithm where a low-order term dominates the runtime for any practical input? Big-O notation hides constant factors, so some $O(n)$ algorithms exist that are infeasible for any reasonable input size because the coefficient on the $n$ term is so huge.

Are there any known algorithms whose runtime is $O(f(n))$ but with some low-order $o(f(n))$ term that is so huge that for reasonable input sizes it completely dominates the runtime?  I'd like to use an algorithm like this an an example in an algorithms course, as it gives a good reason why big-O notation isn't everthing.

Thanks!

Cryptography is an example, if a degenerate one. For example, breaking AES encryption is $O(1)$ — all you have to do is find the right key among a finite number, $2^{128}$ or $2^{192}$ or $2^{256}$ depending on the key size (assume that enough of the plaintext is known to determine the key unambiguously). However even $2^{128}$ operations would take all of the computers today (a billion or thereabouts, each doing about a billion operations per sceond) more than the lifetime of the universe (about a billion billion seconds).

A slightly different way to illustrate why big-O isn't everything is to remark that we sometimes use a different algorithm for small input sizes. For example, take quicksort. With the right choice of pivot (which is a tricky business!), it's $O(n \lg n)$. Quicksort operates by divide-and-conquer: every instance involves doing a lot of sorting of small arrays. For small arrays, quadratic methods such as insertion sort perform better. So for best performance, a quicksort of a large array involves a lot of runs of insertion sort for small sizes.


Infix search in millions of strings Let's say we have millions of strings (each of them < 100 characters):

alpha
allo
blah
hello world
orlando
...

I know how a binary search tree or a trie can help to do "prefix search" (example: find all strings that match al*, i.e. beginning  with al).

Which data structure / algorithm could be used to search patterns inside a word (i.e. not necessarily at the beginning or end), that wouldn't need to do an inefficient O(n) traversal of all the millions of strings?

Example: the pattern orl should match "hello world" as well as "orlando"

Notes:

is that called "infix search"?
I'm looking for something working on strings even without meaning (the pattern qys should allow to find the string uyiuqysidi among millions of other strings), on DNA (pattern ATTG found in GGATCATTGAAGG), on sequences (subsequence 1, 4, 8 found in sequence 7, 2, 1, 4, 8, 19, 32), etc.

Let $\$$ be a symbol not in the alphabet, and let $\{ w_i \}_{i \in \mathbb{N}}$ be the strings you are searching from. Construct the string $S = w_1 \circ \$ \circ w_2 \circ \$ \circ \dots \circ w_n$ and use Ukkonen's algorithm to construct a suffix tree for $S$. You are now able to retrieve all $m$ occurrences of a pattern $P$ in time $\Theta(m + |P|)$, with $\sum_i|w_i|$ preprocessing time.


Classification of intractable/tractable satisfiability problem variants Recently I found in a paper [1] a special symmetric version of SAT called the 2/2/4-SAT. But there are many $\text{NP}$-complete variants out there, for example: MONOTONE NAE-3SAT, MONOTONE 1-IN-3-SAT, ...

Some other variants are tractable: $2$-$\text{SAT}$, Planar-NAE-$\text{SAT}$, ...

Are there survey papers (or web pages) that classify all the (weird) $\text{SAT}$ variants that have been proved to be $\text{NP}$-complete (or in $\text{P}$) ?

Finding a shortest solution for the $N$x$N$ extension of the 15-Puzzle is intractable by D. Ratner and M. Warmuth (1986)

Classic, well-known results
As mentioned by Standa Zivny on the related question of CSTheory, Which SAT problems are easy?, there's a well-known result by Schaefer from 1978 (quoting the answer of Zivny):

If SAT is parametrised by a set of relations allowed in any instance, then there are only 6 tractable cases: 2-SAT (i.e. every clause is binary), Horn-SAT, dual-Horn-SAT, affine-SAT (solutions to linear equations in GF(2)), 0-valid (relations satisfied by the all-0 assignment) and 1-valid (relations satisfied by the all-1 assignment).

Planar-3SAT meaning the planar version of 3SAT is known to be $\mathcal{NP}$-complete. See D Lichtenstein, Planar formulae and their uses, 1981. The non-planar version of 3SAT is of course the very well-known classic $\mathcal{NP}$-complete problem.
Not-All-Equal 3SAT (NAE-3SAT) is $\mathcal{NP}$-complete. However, the planar version of it is in $\mathcal{P}$ as shown by Moret, Planar NAE3SAT is in P, 1988.
More recent and/or "weird" variants
$k$-colourable Monotone NAE-3SAT
Here's a more exotic or weird variant, a decision problem called the $k$-colourable Monotone NAE-3SAT:

Given a monotone CNF expression $\phi$ with exactly three distinct variables in each clause, such that the corresponding constraint graph $G(\phi)$ is k-colourable, is the expression $\phi$ not-all-equal satisfiable?

Here the corresponding constraint graph $G(\phi)$ is a simple undirected graph associated with $\phi$ as follows: Each variable of $\phi$ is a vertex in $G$, and two vertices have an edge between them iff they appear in some clause together.
For $k=4$ the problem is in $\mathcal{P}$. For $k=5$ however, it is $\mathcal{NP}$-complete. See P Jain, On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem, 2010.
Linear CNF variants
While not perhaps being exotic or weird, some well-known variants, namely NAE-SAT (not-all-equal SAT) and XSAT (Exact SAT; exactly one literal in each clause to 1 and all other literals to 0), of the satisfiability problem have been investigated in the linear setting. Clauses of a linear formula pairwise have at most one variable in common. Interestingly, the complexity status does not follow from Schaefer's Theorem.
NAE-SAT and XSAT remain $\mathcal{NP}$-complete when restricted to linear formulas. Moreover, NAE-SAT and XSAT are still $\mathcal{NP}$-complete on formulas only containing clauses of length at least $k$, for each positive fixed integer $k \geq 3$. They are $\mathcal{NP}$-complete for monotone (no positive literals) linear formulas. However, NAE-SAT is polynomial-time decidable on exact linear formulas, where each pair of distinct clauses has exactly one variable in common.
Some further aspects regarding the complexity of NAE-SAT and XSAT under certain assumptions are probably still open. For more specifics, see for example Porschen and Schmidt, On Some SAT-Variants over Linear Formulas, 2009 and Porschen et al., Complexity Results for Linear XSAT-Problems, 2010.


What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of? I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well.

I also know that is it somewhat exponential or even more and with current machines it is rendered impossible to do in less than a year to find it for numbers used in an RSA protocol (they are too big).

What I am asking is what is the actual complexity of such a task? I am looking for average and maximum complexity.

Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm.
You can find the heuristic runtime in the linked Wikipedia-article.
Also in use is the Elliptic Curve Factorization, which needs longer runtime in the worst-case, but has the advantage that the runtime depends on the second-largest factor. Thus every now and then it's faster.
The largest "RSA"-number yet factored is a 768 bit number (RSA Factoring Challenge).


Is $O(N+M)$ exponential or polynomial? So In a review section, our professor asked:

Given integers $N$ and $M$

Is $O(N+M)$ exponential or polynomial.

It's exponential, but I just don't see how that is. I would have thought it's linear.

Exponential or polynomial in what? As stated, it's clearly polynomial in $M$ and $N$.

The complexity of algorithms is given in terms of the length of the input. If an algorithm receives $M$ and $N$ as input, written in binary, then $M+N = O(2^\ell)$, where $\ell$ is the length of the input in bits.

You should ask your professor for clarification. S/he knows what s/he actually said and what the context was; we're just guessing.


Find maximum non contiguous subarray that respect a specific rule Given these two arrays:

[5, 3, 4, 1, 2]

[1, 3, 2, 4, 5]

Find the maximum subsequence in both arrays that the index of the elements are in a crescent order:

Example: [3, 4] it's an answer because the indexes are in a crescent way in both arrays. (same as [1, 2]). Therefore, the subsequence the answer [3, 4, 1] is wrong, because the indexes are the crescent in the first array, but not on the second one.

The output of the program should be the length of the max non-contiguous subarray.

This is the code I wrote for solving this, but it only takes the first subarray, and I'm having difficulty to generate the other possibilities

vector<pair<int, double>> esq;
vector<pair<int, double>> dir;
// N is the size of esq and dir
// pair<int, double> where int is the key (show in the example array) and double is the value, used for sort previously.
int cont = 1;
for (int i = 0; i < N - 1; i++)
{
    int cont_aux = 1;
    pair<int, double> pivot = esq[i];
    auto it_dir = find_if(dir.begin(), dir.end(), [&pivot](const pair<int, double> &p) { return p.first == pivot.first; });
    int last_index = it_dir - dir.begin();

    for (int j = 0; j < N; j++)
    {
        pair<int, double> actual = esq[j];
        auto it = find_if(dir.begin(), dir.end(), [&actual](const pair<int, double> &p) { return p.first == actual.first; });
        int pos = it - dir.begin();

        if (pos >= last_index) {
            last_index = pos;
            cont_aux++;
        }
    }

    cont = max(cont, cont_aux);
}

cout << cont << endl;

I will move my comment to an answer, since you seemed to indicate that the comment solved your problem.

Your problem is normally called the Longest Common Subsequence problem. It does not require the common subsequence to be contiguous. It can be solved efficiently with dynamic programming, and it is an early example of dynamic programming in many textbooks.

There are many implementations of LCS available online. The wiki article on LCS I linked to in the above comment is a good place to start.


Proof that bin packing is strongly NP-complete? Wikipedia claims that bin packing is strongly NP-complete. Unfortunately I haven't been able to find a proof. Does anyone know where to find it?

Such a proof is outlined in Garey and Johnson, 'Strong' NP-Completeness Results: Motivation, Examples, and Implications, mentioned in the Wikipedia article. The proof is by a straightforward reduction from 3-PARTITION. The problem 3-PARTITION one is given $3n$ numbers, and the task is to decide whether they can be split into triples of equal sum. There is a straightforward reduction from 3-PARTITION to BIN-PACKING: if the sum of the numbers is $nB$, ask whether the $3n$ numbers can be packed into $n$ bins of size $B$.

The strong NP-completeness of 3-PARTITION was proved in a different paper of Garey and Johnson, Complexity results for multiprocessor scheduling under resource constraints. The proof is quite long, ultimately a reduction from 3DM (3-dimensional matching), but going through many intermediate steps.


Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular Prove that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular.

Here is my try, I would really appreciate if someone could tell me if this is a correct proof.
Proof:
Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma.
So let p the pumping number.
Let $w=a^pcb^p$. $w$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $|y|>0,|xy|\leq p,xy^iz$ is in L $\forall i \in N$.
Because $|xy|\leq p$ $y $ can only contain the symbol $a$(If $y$ would contain a symbol different from a it would imply that $|xy|>p$, which is not possible). Therefore $y$ must be in the form $y=a^{p-k},0\leq k<p$. So the word w equals $w=a^ka^{p-k}cb^p$, if we set i=2 we get $a^ka^{2p-2k}=a^{2p-k},k<p$ and because $ a^{2p-k},k<p\neq b^p$ it follows that the pumped $w$ is not  in $L$. Which is a contradiction. Therefore $L$ is not regular.
$\tag*{$\blacksquare$}$

Proof:
Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma.
So let p the pumping number.
Let $w=a^pcb^p$. $w$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $|y|>0,|xy|\leq p,xy^iz$ is in L $\forall i \in N$.
Because $|xy|\leq p$ $y $ can only contain the symbol $a$(If $y$ would contain a symbol different from a it would imply that $|xy|>p$, which is not possible). Therefore $y$ must be in the form $y=a^{p-k},0\leq k<p$. So the word w equals $w=a^ka^{p-k}cb^p$, if we set i=2 we get $a^ka^{2p-2k}=a^{2p-k},0<=k<p$ and because $ a^{2p-k}\neq b^p$ it follows that the pumped $w$ is not  in $L$. Which is a contradiction. Therefore $L$ is not regular.
$\tag*{$\blacksquare$}$


Construct regular expression that contains the substring I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring.

So far, the even number of b's can be constructed using like this:

   (aUb(aUc)*bUc)* or (cUa)*b(cUa)*b(cUa)*

to add the substring abcba, do I just attach it to the end of the regular expression and then repeat it or is there a better way?

Any help is appreciated!

Any string containing $abcba$ is of the form $xabcbay$, where $x,y$ are strings. This string contains an even number of $b$'s iff $xy$ contains an even number of $b$'s iff either $x,y$ both contain an even number of $b$'s, or both contain an odd number of $b$'s. This leads to the following regular expression:
$$
(a+c)^*(b(a+c)^*b(a+c)^*)^*abcba(a+c)^*(b(a+c)^*b(a+c)^*)^* + \\
(a+c)^*b(a+c)^*(b(a+c)^*b(a+c)^*)^*abcba(a+c)^*b(a+c)^*(b(a+c)^*b(a+c)^*)^*
$$


Organisation and Architecture of Quantum Computers What are devices and their interconnections used alongwith Quantum Processors? Are they compatible with hardware devices like Cache, RAM, Disks of current computers?

What you describe as current computers is known as the von Neumann architecture. This approach is one of many ways to think about classical computation and there are other classical approaches that might or might-not have relevant generalizations to quantum computing. The von Neumann architecture seems to be unlikely to be relevant to quantum computing, due to its difficulty from both the theoretical and implementation side.

However, as I mentioned on cstheory there is an article on implementing a quantum von Neumann architecture. They do this via superconducting qubits, of course the implementation is very small, with only 7 quantum parts: two superconducting qubits, a quantum bus, two quantum memories, and two zeroing registers. This allows their quantum CPU to perform one-, two-, and three-qubit gates on qubits, and the memory allows (data) qubits to be written, read out, and zeroed. Implementing a quantum superposition of gates is very difficult, and so the program is stored classically.

More likely models of quantum computing to be implemented include: measurement-based, topological, and adiabatic models. Typical implementations of these models look more like physics experiments (which they are!) than computers. Some of the common strategies for implementation include trapped ions, quantum optics, and superconducting circuits.

The circuit approach has been placed on chips and in fact D-Wave (a spin-off from UBC in Vancouver) claims to have built quantum-like computers using the adiabatic model to implement quantum simulated annealing. They have managed to sell this computer to Lockheed Martin but their approach has been met with heavy skepticism.

Lastly, the NMR approach mentioned by @RanG. is interesting, but suspected to be not equivalent to full quantum-computing. It is equivalent to the one-clean qubit model (also known as DQC1) and suspected to be strictly weaker than full quantum computing.


Does this excerpt from the linear probing Wikipedia page make an assumption? Here is the excerpt from the linear probing page at Wikipedia.

  To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and continuing to the adjacent cells h(x) + 1, h(x) + 2, ..., until finding either an empty cell or a cell whose stored key is x. If a cell containing the key is found, the search returns the value from that cell. Otherwise, if an empty cell is found, the key cannot be in the table, because it would have been placed in that cell in preference to any later cell that has not yet been searched. In this case, the search returns as its result that the key is not present in the dictionary.

Does this assume that the linear probing function let's say P(x) is the same for insertion and searching? Must your linear probing function be consistent throughout the hash table? Is there a combination of linear probing functions that work best together?

Yes, it is assumed that probing sequences are identical during the search and insertion. In theory you could use a different probing sequence (e. g. check h(x) index first, then h(x) + 2, and only then h(x) + 1), but it doesn't make any sense - you are better off always using the same sequence to have the minimal expected number of probes.


How do Kruskal's and Prim's algorithms compare to each other? I understand that both of them are used to find minimal spanning trees, and I've seen their implementations, but I don't understand how both of them compare to each other, and how they differ in complexity.

A tree in a graph is a connected acyclic subgraph. A spanning tree in a graph of order $n$ is a connected acyclic subgraph of order $n$ or equivalently a connected acyclic subgraph with $n-1$ edges.
Prim's algorithm consists of building a spanning tree by adding edges (and corresponding vertices), always keeping the connected and acyclic property, until the tree contains all vertices. The complexity of the algorithm is detailled here: it is $O(|E|\log |V|)$ with binary heaps, and $O(|E| + |V|\log |V|)$ (which is slightly better in general case) with Fibonacci heaps, a complicated data structure.
Kruskal's algorithm consists of building the spanning tree by adding edges always keeping the acyclic property, until there are $|V|-1$ edges. Its complexity is detailled there. It is $O(|E|\log|V|)$, but if the edges can be easily sorted, you can reach $O(|E|\alpha(|V|))$ with improved union-find data structure ($\alpha(x)$ is in practice very small, that is $\leq 4$ even if $x$ is the number of particles in the universe).
Both of them are greedy algorithms, but the property you keep invariant is not the same.


Choosing taps for Linear Feedback Shift Register I am confused about how taps are chosen for Linear Feedback Shift Registers.
I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, R3, R2, R1$ and $R0$ and the taps come out of $R0$ and $R3$.
How are these taps decided? When I am given a connection polynomial but no diagram, how do I know what values I should XOR?

The taps are decided by the polynomial in a straightforward way:
for $X^n$, you connect the $n$th tap. Note that in your diagram the first tap is $R4$, the 2nd is $R3$ etc..

Since your polynomial is $X^5+X^2+1$ the feedback is an XOR of the output of the 2nd tap ($R3$) and the 5th tap ($R0$). The "$+1$" of the polynomial ($X^0$) is usually always there and corresponds to the "feedback" itself, i.e., the line connected into the first bit ($R4$).

The output should be the "feedback" line (rather than $R0$). This is important since the polynomial is identified with the generated sequence, and if you take the output of $R0$ you generate a different sequence, not the one identified with $X^5+X^2+1$ (although they are the same up to a prefix)

See more details in Wikipedia: Linear feedback shift register.


Prove or disprove - graph doesn't exists So, we have a directed graph G whose basis graph is connective.
I was asked to prove or disprove If its possible that for every DFS run on G, the output will be two trees containing all G vertices .
The only thing I could think of Is that graph like this cannon have a root (otherwise we could use DFS on the root and the output will be just one tree containing all G vertices).

Any Ideas?

thanks.

If the question is - "Does there exists a directed graph $G=(V,E)$ (whose undirected version is connected) such that each DFS run on $G$ (preferably with different choices of root) always return exactly two trees?", then the answer is No.

Compress all SCCs into supernode, and let $G^*=(V^*, E^*)$ be resulting graph with $V^*=\{S_1,S_2,\ldots, S_k\}$. Each SCC ($S_i$'s) must have either an incoming edge or an outgoing edge. Now,

At least one SCC must have a zero incoming edge (say it is $S_1$).
At least one SCC must have a zero outgoing edge (say it is $S_k$).

If you take a root in SCC $S_k$ as compared to $S_1$, then DFS will give one more tree for sure.


Do I require loading in this example of load store architecture? I'm currently revising for my Concurrent Programming exam and I'm going through the past papers and one question poses the following process:

Process P1
 integer x;
1a: x = a + a;
1b: b = x;
end P1;

and asks the following question:

  Rewrite processes P1 to take into account execution using a ‘load/store’
  architecture.

For 1a  I have broken it down into this:

load a into R
add a to R
store R into x

Where R refers to the register as per my notes.

My trouble lies in 1b. Do I need to load x into R before I store R into b or can I simply bypass the register and store x into b.

You need to load x into R before you store R into b

wikipedia says:

In computer engineering a load/store architecture only allows memory to be accessed by load and store operations, and all values for an operation need to be loaded from memory and be present in registers. Following the operation, the result needs to be stored back to memory.

In your case, x is still in memory and has to be loaded into a register.


If L is not regular and is a proper subset of L1, does it follow that L1 is not regular? If $L$ is not regular and $ L \subset L_1$, does it follow that $L_1$ is not regular also? Can you please provide an explanation? Thanks in advance.

@Vladislav's answer is probably more interesting, but observe that every language over an alphabet $\Sigma$ is a subset of $\Sigma^*$, which is certainly a regular language.


Reducing optimization problem to its decision version There are two problems that need to be solved. Both problems use a compatibility matrix $C$, where $C[a, b]$ is how compatible students $a$ and $b$ are.

(1) Given an $n \times n$ compatibility matrix $C$ for $n$ students, and $r$ rooms with sizes $s_1, s_2, \dots, s_r$, where $n$ is the sum of room sizes, and a target $A$; determine if there is some assignment of the students to the rooms with average compatibility value at least $A$.

(2) Given an $n \times n$ compatibility matrix $C$ for $n$ students, and $r$ rooms with sizes $s_1, s_2, \dots, s_r$, where $n$ is the sum of room sizes; find an optimal assignment of the students to the rooms.

These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For both problems, you find an efficient program on the Internet that solves that problem. Unfortunately your budget will only allow you to buy one such program.

Assume that you have a program that solves the second problem in time $\Theta(n^j)$, for $j ≥ 1$. Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm?
Assume that you have a program that solves the first problem in time $\Theta(n^k)$, for $k ≥ 1$. Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm

I understand how to do problem 15, but for problem 16, I have no idea.

Use binary search on the target $A$, finding the maximal value for which an assignment of average compatibility $A$ exists.

I'll let you work out the resulting multiplicative overhead (which depends on the magnitude of the numbers involved).


Shortest decimal expansion within binary interval Consider an interval $[x-2^n,x+2^n]$ defined by a binary float $x$ and a power of two $2^n$ typically much smaller than $x$. I would like to know whether an efficient algorithm exists to determine the shortest decimal expansion within the interval. What is the basic idea of such an algorithm? Perhaps such an algorithm has already been published?

In my own search, I have come across the work of Steele & White “How to print floating-point numbers accurately”, but it is not clear to me whether it applies in the sense that their results can be adapted to this particular case.

Decimal numbers with k digits to the right of the decimal point are $10^{-k}$ apart. So if you choose k large enough that $10^{-k} < 2·2^n$, then there is a decimal number with k decimals inside the interval. You can for example calculate it as $round (x·10^k) / 10^k$.

You may be lucky, and a number with fewer decimals may be inside the interval. Rounding the result to k-1 or fewer decimals may give a result in that interval.


What is the difference between dynamic programming and a mere caching? I mean why should we use such epic buzzword when you can say: "cache your results!".

There are some other key aspects of dynamic programming besides caching, namely, it is about writing solutions of optimization problems recursively to exploit the fact that optimal solutions are constructed out of optimal solutions to subproblems, and further that caching limits the number of recursive calls to the maximum number of distinct subproblems that need to be solved.

Also, dynamic programming is not so much a formalism, as an intuitive framework for solving many optimization problems recursively.

Further, the use of such an "epic buzzword" is largely the result of brilliant marketing by Richard Bellman...


Implementing the Schur decomposition of a matrix I'm trying do implement the Schur decomposition of a matrix, but I can't find any good articles for the theory. Could someone share one?

It's italian but it's very clear... Read this:

Shur decomposition

Proposition 6.13


What is a suitable data structure in this scenario? I need an efficient data structure for maintaining a set of values.
Here, $n_1$ is the number of insertions per unit time; $n_2$ is the number of deletions per unit time; $k$ is the number of searches per unit time.

I have 4 possible use cases:

$k \gg n_1,n_2$ with limited memory
$n_1 \gg k,n_2$ with limited memory
$k, n_1, n_2$ are comparable with limited memory
$k, n_1, n_2$ are comparable with unlimited memory

I have decided to use a doubly linked list for the second case and a direct address table for the fourth case.

My question is about the first and the third cases. Both Hash Table and Tree (AVL or Red-Black) look promising. Should I choose the Hash Table with an amortised constant time or the Tree with a $\log n$ worst case time?

Depending on how limited the memory is, the best choice for 1 could be a sorted array: Binary search is fast, insertions and deletions are rare and memory overhead is negligible.

For number 2 a (unsorted) singly linked list is better than a doubly linked one, since we (presumably) don't perform any operations that benefit from the backlinks and thus can save the memory (and maintenance time) required for them.

For number 3, unless the hash function and data don't play nicely with each other, the hash table will likely be faster than a tree. If the load factor does not get too low, it will also be more space efficient, since a binary tree with $n$ keys needs $\sim 2n$ pointers.


Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization? So diagonalization as we all know is an extremely productive way of showing uncomputability, the other main tool used by CS people for this task being reduction.

But it has occurred to me that I do not know a single uncomputable problem whose demonstration of uncomputability does not rely on diagonalization or reduction to a problem which relies on diagonalization.

Is there any example out there?

there appear to be "no known examples" of undecidable problems that are not proven through "diagonalization" (precisely formalized), or more strongly, apparently diagonalization is the only way of showing uncomputability. in fact diagonalization, formalized, is an even more general property than undecidability, because exactly the same "mechanism" is behind other key mathematical proofs namely Godels theorem and the uncountability of the reals. this is revealed in the Lawvere fixed point formalism/ theorem.[1][2]

maybe inadvertently, your question is also related or nearly equivalent to the Church-Turing thesis in some subtle or direct ways. the thesis is, roughly, that anything computable is computable by a Turing machine. therefore, equivalently, anything that is not computable is not computable by a Turing machine and all uncomputable Turing languages are reducible to the halting problem and vice versa.

the idea that there exist computations not captured by TMs is considered at best speculative and at worst verging on a "generally not credible" idea by the majority of computer scientists; see eg summary/ "debunking" by Fortnow which also cites several published/ peer reviewed counterclaims.[3] a more recent survey on applicability of Turing machine model and "hypercomputation" etc can be found in [4]

[1] Halting problem, uncomputable sets: common mathematical proof? / cstheory.se

[2] Lawvere, F. William. Diagonal Arguments and Cartesian Closed Categories. Lecture Notes in Mathematics, 92 (1969), 134-145

[3] UBIQUITY SYMPOSIUM 'WHAT IS COMPUTATION?'
THE ENDURING LEGACY OF THE TURING MACHINE / Fortnow

[4] Turing's Titanic Machine? / Cooper, communications ACM


Decidability of languages containing bitstrings and their corresponding ones' complements Consider strings $s \in \{0,1\}^*$. Define $c_1(s)$ to be the ones' complement of $s$; i.e., the string obtained from $s$ by inverting all of its bits. So, for example, $c_1(000111) = 111000$. Call a language $L \subset \{0,1\}^*$ ones' complement closed, or OCC, if $s' \in L$ $\iff$ $c_1(s') \in L$, provided $s'$ is not the empty string. Given these assumptions, I have a few questions.

Does there exist an OCC language that is both Turing-recognizable and not decidable?

Does there exist an OCC language $L$ with the property that both $L$ is not decidable and $\overline{L}$ is Turing-recognizable?

Does there exist an OCC language $L$ that is such that neither it nor $\overline{L}$ is Turing-recognizable?

I am having some trouble answering these questions because of how limited the alphabet $\{0,1\}$ is. I was thinking that perhaps this alphabet alone could be used to encode Turing machines, and from there we could talk about the well-known decidable/undecidable and recognizable/not-recognizable languages involving Turing machine encodings, but I'm not sure this is possible.

Given a language $L$, you can create a language $L'$ which is equivalent in power and OCC:
$$
L' = \{ 0 x : x \in L \} \cup \{ 1 c_1(x) : x \in L \}.
$$
The two languages are recursively equivalent. This means that there is a computable reduction from $L$ to $L'$ and another one from $L'$ to $L$.

Using this construction, you can now answer your own question.


Numerical Boardgame -- Help with with a pruning method (alpha-beta : minimax) I'm developing a simple AI to play a boardgame which consists of N x N squares, each with a predefined value.

44 33 75 12 99 23
53 89 14 01 32 98
34 98 67 45 02 38
89 87 54 21 34 87
65 84 99 72 95 17

Each player can either (a) instant claim an unclaimed cell anywhere on the board, or (b) rush an unclaimed cell from a cell already owned. In the case of (b), any enemy cells that are touching the newly claimed cell are converted to your side.

Example:

Player 1:  (1,1) -- {89}
Player 2:  (3,1) -- {87}
Player 1:  rush->(2,1) -- {98}

In the scenario above, after the rush move, Player 1 now owns all three cells (since (3,1) was an adjacent cell to (2,1)).

I have the MiniMax algorithm working great for this. It's actually quite fun to watch the AI compete against each other. My problem is determining an effective way to prune moves from the tree. I attempted a trivial pruning method of:

 - - If the cell we're claiming is empty
 - - - If the neighbors of the cell we're claiming is empty
 - - - - If the neighbor's-neighbor is an enemy-owned cell
 - - - - - Prune this move

The idea above being, we don't want to claim a cell that could immediately result in the opponent rushing towards us, claiming for themselves the cell we just claimed.

This didn't go well.

I'm a bit at a loss for a decent heuristic for pruning moves at this point. Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out rush that cell as soon as it's claimed. That is to say, if our opponent owns cell (4,4), it wouldn't be ideal for us to choose (4,2) since it could wind up being immediately rushed. But maybe it wouldn't hurt to start at the largest values and just test them out? I don't know.

Any help here is greatly appreciated.

I'm a bit at a loss for a decent heuristic for pruning moves at this point

You can start from the observation that for the side to move there is almost always a better alternative than doing nothing (at least in the first phase of the game, when there are many moves).

So you can try a "null" move (the side to play passes and lets the opponent get a free move): if the score of the subtree search (depth reduced by a R constant) is still high enough to cause a beta cutoff you can prune the tree.

The pseudo-code is something like:

switch_side_to_play()                                     // Null move
score = -ab_search(-beta, 1 - beta, depth - R - 1)
switch_side_to_play()

if (score >= beta )
  // return score (cutoff) or reduce the search depth

As every heuristic, it sometimes fails. This is an example from Chess but the same problem could happen in your game when there are only few moves available.

If White is to move, he will have to move Kd6, which results in stalemate, or move away from the pawn which loses it.

However if White could pass (null-move), Black would have to play Kc7 (White plays Ke7 and the pawn queens).

I'd start trying null move: if it works there is much to gain. If it doesn't work (Checkers / Othello are two well known examples), ProbCut heuristic would be a good alternative.

The general idea of ProbCut is to perform a shallow search. If the result is far outside the alpha-beta window you trust the search, otherwise you have to re-search to the full depth.

If you assume this relationship (linear model) between the value of a shallow search ($v'$) and the values of a full search ($v$):

$$v = a \cdot v' + b + \mathcal{E} $$

($\mathcal{E}$ is an error variable, normally distributed, with mean 0 and standard deviation $\sigma$)

Then the beta-cutoff condition of the alpha-beta algorithm ($v \ge \beta$) becomes:

$$ v′\ge  \frac{Φ^{−1}(p) \cdot \sigma + \beta − b}{a} $$

(same for $\alpha$, see the linked paper for further details).

The nuisance is that you have to tune many parameters, but this is a very general pruning technique.

  Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out rush that cell as soon as it's claimed.

This is similar to captures in chess: you can take a piece but the opponent could recapture.

So a complex heuristic to evaluate the result of a sequence of captures on a square is a possibility, but also a simple heuristic like MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) is very effective.

You could try highest remaining cell + sum of cells claimed by rush or highest remaining cell + sum of cells claimed by rush - (number of attacking cells) % 2.

According to this heuristic the last move has a value of 9 + (1 + 10) - 1. This is very coarse but it isn't for pruning, just for ordering.


Undecidable vs Unsolvable? In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is what does "undecidable" mean ? I read the "undecidable" applies to problems that have Turing Machines but cannot definitively tell us whether an input is valid or not(i.e. it outputs "yes" for valid inputs, and keep going for others indefinitely such that we will not know when, if ever, it will output anything). Then does "undecidable" applies to problems that can not be represented by Turing Machines at all, also? What is the difference between unsolvable and undecidable ?

EDIT:
I was reading my textbook(Introduction to Automata Theory, Hopcroft) and I ran into this: "Remember that showing there is no Turing machine at all for a language is showing something stronger than that the language is undecidable(i.e., that it has no algorithm, or TM that always halts"(pg 388). This seems to imply undecidable problems do not include ones without any TMs. Am I interpreting this correctly ?

Yes, undecidable also applies to problems that cannot be represented by TM at all. The ones where a YES can always be found are a subclass of these called (recursively) enumerable. Unsolvable is a less common term which I know mostly to be used synonymous to undecidable.

So  decidable - undecidable but enumerable - non-enumerable  is a partition of the class of all problems into three classes, where the middle one is intuitively somthing like the easiest undecidable problems.


Logistic model and Linear regression model I am reading the book "An introduction to statistical learning with applications in R". I am reading Logistic Regression and I don't understand why when it's compared to linear regression model, the author said that "the problem with this approach: for balances close to zero we predict a negative probability of default; if we were to predict for very large balances, we would get values bigger than 1." as in the highlight. Could anyone please explain me how the probability can be smaller than 0 or larger than 1?

Your help is really appreciated!

Thank you

You should just keep reading:

  These predictions are not sensible, since of course the true probability of default, regardless of credit card balance, must fall between 0 and 1.

A probability cannot be smaller than 0 or larger than 1. The problem is that the model might predict such a "probability".


Getting started with Data Mining This is the first time that I'm looking in depth into the topic, although I've always been curious.
Could someone let me know about online resources (courses, tutorials, etc) and books that cover the basics of the topic?
I'd like to explore both the theoretical part and the more practical part of Data Mining.

You can start with Data Mining: Concepts and Techniques.

To see data mining algorithms in practice you can use Weka.


Hit/Miss in a 2-way set associative cache with offset "In a 2-way set associative cache of 4 blocks containing 4 words each, which one of these addresses will return a hit when being read? The blocks to be retained in the cache are decided by LRU."

4 word / block means that the offset = 2 bits.

2-way means 4 blocks / 2 = 2 sets. The index then needs 1 bit.

And thus the tag is 3 bits, since we're dealing with 6 bits adresses.

What I'm not too sure about is the hit/miss part. In such a case, do we need to have an exact match for the Index, the Tag and the Offset to get a hit?

Or is a hit encountered as soon as the Index and the Tag match?

If it is the latter then what role plays the offset in such a situation?

No, you don't need to have a match for the offset. When you 'miss' some address (= when its not in the cache) , the whole block is copied from the memory to the cache. i.e for address $001111$ , we will copy the 4 word block: $001100$ , $001101$ , $001110$, $001111$  to the cache. Therefore, for example, in line 4 you get a 'hit', not a miss.

So a hit is encountered as soon as the Index and the Tag match. The offset tells you which word from the block you want to read, as there are 4, and you want only 1. for example, for $001111$ it will skip the first 3 words and read the fourth.

EDIT: if I remember correctly, in a 2-way you need 3 offset bits and not 2. 1 bit is 'block offset' so you know in which block of the 2 has your word (because there are 2 blocks with same tag and index).


Can you explain in terms of logic gates how Babbage’s Analytical Engine worked? On a recent trip to the London Science Museum I saw Babbage’s Analytical Engine.

Apparently this had an ALU (or equivalent). Is the Analytical Engine binary? I can build an ALU out of logic gates but I can’t conceptualise how to do it with gears. I’m trying to map across the concepts.

My question is: Can you explain in terms of logic gates how Babbage’s Analytical Engine worked?

The documentation is quite clear they're still working out what the design was supposed to be.

Taking an approximation - they have developed a Java program to run sample programs. The logic behind the source code shows how it may have worked.


Unconstrained subset sum vs constrained subset sum? In class, we discussed two question types:  constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.
Question 1: Given an unconstrained set of numbers, find whether or not a certain subset of them adds up to a target value.
Question 2: Given a constrained set of numbers, find whether or not a certain subset of them adds up to a target value.
Now in answer to these questions, our professor mentioned that in the former case, there is no way to do better than $2^{n}$ since we would need to check all possible combinations of the n numbers. But in the second case, we can do better since if we know our numbers are in the range of [0,n], our sums can only be in range [0, $n^{2}$], so our running time may be polynomial and not exponential. I have understood up until this point, but when discussing the specific implementation of the two programs is where I am confused.

So, for the first problem(unconstrained subset-sum), the idea is that we do an implicit traversal of a tree. Where for each number in the set we say, use this or no don't use this. So we get $2^{n}$ possible combinations.  I am not sure if we could use dynamic programming in this case also?

But in the other case, the approach used in class was we used a linked list to store all the possible sums that could be computed by a certain subset of the numbers, and then we took another number from the set, and added it to all the values in the linked list to generate all possible sums that could be formed using this number. If the number is already in the list, we don't bother to add it.

Question 1:
What I fail to understand is that, how come this time around the running time is polynomial, when really we are still trying to generate all possible sums like we did the last time? After all we are still trying to generate all possible sums right?
Question 2:
My second confusion is that why cannot we use the second approach (using a linked list to store all the possible sums) to solve the unconstrained subset sum problem?
Question 3:
Finally, my final question is that, in this case(i.e. for the constrained subset sum), I saw that we could use dynamic programming. I am wondering how we can use DP, because the way I am looking at it, each time we are generating unique subsets and so we will never share subproblems?

If you have $n$ non-negative integers $x_1,\ldots,x_n$ in the range $0,\ldots,T$, then their susbets can sum up only to integers in the range $0,\ldots,nT$. This allows us to solve SUBSET-SUM efficiently in the constrained case. The idea is to use dynamic programming: for $m = 0,\ldots,n$, we determine which of the $nT+1$ potential sums are achieved by subsets of $x_1,\ldots,x_m$.
When $T$ is small, say polynomial in $n$, then this leads to a polynomial time algorithm. This is the constrained case. When $T$ is arbitrary, the corresponding algorithm is not efficient. This is the unconstrained case. The difference between the two cases is the number of potential sums – in the constrained case there are only polynomially many potential sums, in the unconstrained case there could be a lot more. In other words, you can use the dynamic programming algorithm in both cases, but the algorithm will only be efficient in the constrained case.
Let me also mention that the $O^*(2^n)$ algorithm in the unconstrained case can be dramatically improved upon using meet-in-the-middle, to $O^*(2^{n/2})$. A naive implementation of meet-in-the-middle uses a lot of memory, $\Theta^*(2^{n/2})$, but this can be improved to $O^*(2^{n/4})$ (the classic Schroeppel-Shamir algorithm).


Expressing that a functor is natural The Haskell List: Type -> Type constructor implements the Functor typeclass with function fmap f = map f. This functor that applies the morphism f to each element of a list works, but there are other equally valid functors, for example fmap f = map f . rev which first reverses the list before mapping over it. Is there a concept in category theory that expresses the fact that the first choice of functor is in some sense "more natural" for this type constructor?

Being a functor requires two properties:

fmap id = id
fmap (f . g) = fmap f . fmap g

The definition fmap fails the first condition:

fmap id = map id . reverse = reverse != id

So that's not a functor at all!

And it even fails the second condition:

fmap (f . g) = map (f . g) . reverse
             = map f . map g . reverse
             = map f . fmap g
             = reverse . map f . reverse . fmap g
             = reverse . fmap f . fmap g
             != fmap f . fmap g

Which is quite clear if you think about it:

fmap (f . g) reverses the list once and then maps its elements via f . g
fmap f . fmap g reverse the list, maps via g, then reverses the list again and then maps via f!


Is randomly building a BST different from random sampling whole trees? What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution

You want to distinguish

  randomly built binary search tree

from

  choosing a binary search tree from a random distribution.

Let me first tell you why this is not a well-posed query. Neither version is
completely specified; the first misses the process by which the tree is built
as well as the used random source, the second lacks a specification of the
distribution to be used. In particular, the "randomly built" trees are
"chosen from a random distribution"!

Now I'll assume that you (or your teacher) made the "usual" assumptions and reformulate
the models.

Starting with the empty tree, we insert keys $s_1, \dots, s_n \in [1..n]$
successively (with BST insertion). The sequence is chosen uniformly at random
from all permutations of $[1..n]$.

This is the famous random permutation model.
Pick a tree uniformly at random from all BSTs with keys $[1..n]$.

There are several ways to see that the two models define different random distributions.

There are $n!$ different permutations but only
$C_n = \frac{1}{n+1} \cdot \binom{2n}{n}$
BSTs. Show that it is not possible to distribute the permutations evenly,
i.e. $C_n$ does not (always) divide $n!$.

In particular, for $n=3$ we have six permutations but five BSTs.
For $n=3$, enumerate all trees and notice that four trees result from one
permutation each while the fifth results from two. Ergo, the random
permutation model is not uniform.
Know (from earlier studies) that BSTs have average height $\Theta(\log n)$
in the random permutation model but $\Theta(\sqrt{n})$ in the uniform model.

The first is a standard result found in most textbooks on the matter. The latter, admittedly, a less known result by Flajolet and Odlyzko [1]; the method of analysis has broader relevance and the result generalises to many families of trees.

The average height of binary trees and other simple trees by P. Flajolet and A. Odlyzko (1982)


Books for the Mathematical Theory of AI/ML I am interested in the mathematical foundations of Artificial Intelligence and Machine Learning. Are there any books which will describe and present the mathematical foundations in detail? I am not that interested in coding and would prefer a text which is heavy in mathematics and the theory.

My favorite is Understanding Machine Learning: From Theory to Algorithms. It’s presentation is very probability oriented and introduces concepts in a very concise, yet insightful way. It covers the foundations of a lot of Statistical Learning Theory and thanks to the rigorous introduction, I found it is easy to build on certain directions that interest me.