When are Dynamic and Lexical Scoping equivalent? I am designing a small DSL and I know that implementing dynamic scoping (with a simple global stack) is easier then using full lexical scoping (each function needs its own scope/closure). What kind of features can be added that do not care how scope is implemented and what features would require a particular kind of scope implementation?

For example, if I have a very simple language that does not allow nested functions or function arguments I feel that both implementation choices are likely equivalent. On the other end of the spectrum, if I wanted to support returning inner functions then I'm pretty sure we would need to allow functions to save their own closures. However, I am not really sure what would happen in the middle if say, I alowed nested functions while not allowing them to be returned or if I allowed functions to be passed as arguments to other functions.

If you allow one function to call another, then you have enough power to distinguish a lexically defined variable from a dynamically defined one.

def scope {
  var x = 10
  def f() {
    return g()
  }
}
def g() {
  return x;
}
scope.f()

If x is dynamically scoped, the code returns 10. If it is lexically defined, the result is an error.

Thus if you want a language where dynamic and lexical scoping behave the same, it will be a rather weak language.


Dove tailing questions about accepting language $L = \{M | \text { M is a TM and there exist some string w that contains five 1's such that M halts}\}$

Where $\Sigma =\{0,1\}$

let $w_1, w_2, \cdots, \in \Sigma^*$ be an effective enumeration. We give a TM $R$ that recognizes $L$

R = "On input <M>
    for s = 1 to infinity:
        for i = 1 to s
            run M on input w_i for s steps
            if M halts on w_i within s steps then
                accept

Can I assume $M$ knows to halt only if there are five $1$'s? Or do I need another if statement such as in line 4

if M halts on w_i within s steps then
    if w_i.count("1") is 5 then
        accept

Showing some machine $R$ that recognizes $L$ is enough to prove that $L$ is recognizable, however, you have yet shown $R$ recognizes $L$.

Formally, you must show:

$M \in L \Rightarrow  R $ accepts $M$
$M \notin L \Rightarrow  R $ does not accept $M$, but not necessarily halts.

Let $S_i$ be all strings in $\Sigma ^*$ of length exactly $i$. It is clear, for any $i$ that is finite, $S_i$ is also finite.

Let $S_i^*$ be a subset of $S_i$, where every $s \in S_i ^*$ contains exactly five $1$'s.

$R$ is a machine that given input $M$:

for $i=5...\infty$
for $s$ in $S_5^* \cup S_6^* \cup \dots \cup S_i^*$

simulate $s$ on $M$ for $i$ steps. If $M$ halts in $i$ steps or less, finish and accept. Otherwise continue.

Suppose $M \in L $ (and we will show $R$ accepts $M$):
 There exists $w^*$ of length $k$ that contains five $1's$ and $M$ halts on $w^*$ in $r$ steps.

Since $S_i^*$ is finite, $S_5^* \cup S_6^* \cup \dots \cup S_k^*$ is also finite (finite union of finite subsets), so $R$ simulates $w^*$ on $M$. Now if $r \leq k$ then $M$ halts and $R$ accepts $M$.

If $r > k$ then surely $w^* \in S_5^* \cup S_6^* \cup \dots \cup S_r^*$, hence at $i=r$ $M$ will halt on $w^*$ and $R$ will accept.

The second step is very simple; if $M \notin L$ then no such $w$ with five $1's$ exists such that $M$ halts on it, and $R$ will run indefinitely.


Constructing PDA to accept language $L=\{a^i b^j c^k \mid k\geq \min(i,j)\}$ How can I construct a PDA which accepts the language   $\{a^i b^j c^k \mid k\geq \min(i,j)\}$
I think about different solutions such as building a stack with two-state. one state is for $i < j$ and another is for $i > j$, But I think it doesn't work.
also, The idea of poping and pushing a and b is not good. I tried it. Can Someone give me a little hint?

Your idea to differentiate between $i<j$ and $i >j$ is good.
To help you building the PDA, note that $L = \{a^ib^jc^k | k \geq i\} \cup \{a^ib^jc^k|k\geq j\}$.
I hope that hint is enough.


Hashing a Specific Range Of a Character Array I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my array remains the same throughout the process of hashing, I only am changing the range. To deal with this, I have to make an entire copy of the array everytime I process a query, and then compute the hash from the above function.

I am using Arrays.copyOfRange to create a copy everytime I process a query. I need to avoid this. So I was thinking of devising a hashing scheme of my own. This scheme should be such that I whould get a unique hash for each array range. Hashes should be same if all characters in the range are same.

Any Help on how to proceed with the making of such a hash function will be appreciated.

Use a rolling hash function, such as the Rabin-Karp hash.  This allows you to compute hashes of any subrange of $A$ very efficiently, e.g., in $O(1)$ time, assuming you use some extra memory to keep track of all of the intermediate states of the rolling hash.

If $A[0..n-1]$ is your array, a rolling hash defines the hash of the entire array using a recurrence like this:

$$x_i = f(x_{i-1}, A[i])$$

where $x_{-1}$ is some fixed constant and $f$ is some function.  Now here's what you can do.  You can store the $x$ values in an array $X[0..n-1]$ (where $X[i]=x_i$).  This will allow you to compute the hash of any prefix of $A$.

If you want to be able to compute the hash of any consecutive range of $A$, choose the function $f$ carefully to be reversible.

A simple instantiation: let $X[-1] = 0$ (for some constant $c$) and

$$X[i+1] = \alpha \cdot X[i] + A[i] \bmod 2^{32},$$

where $\alpha$ is some 32-bit constant (you'll want it to be odd).  Preprocess the array $A$ once to compute the array $X[0..n-1]$.

Now, the hash of $A[i..j-1]$ can be very efficiently computed: it is the following:

$$X[j-1] - \alpha^{j-i} X[i-1]  \bmod 2^{32}.$$

Notice that $\alpha^{j-i} \bmod 2^{32}$ can be computed efficiently using fast exponentiation algorithms, i.e., repeated squaring modulo $2^{32}$.  Thus, assuming you've stored the array $X$ alongside the array $A$, a hash of any range of $A$ can be done in $O(1)$ time.

If you want something even simpler and easier to implement, set $\alpha$ to 1.  Then the hash of $A[i..j-1]$ just becomes $A[i]+ A[i+1]+ \cdots + A[j-1]$, and $X[i]$ stores $A[0] + A[1] + \cdots + A[i]$, so the hash of $A[i..j-1]$ is just $X[j]-X[i]$.
However, the quality of this hash degrades and you might see an increase in hash collisions.


Can we make a PDA with only 1 state which accepts a^n and n is odd? We can have acceptance with empty stack, but in that case our stack at the start has to have a A in it, otherwise this machine will accept the empty string which is wrong

But can we have a non empty stack at the start? is my method right?

But can we have a non empty stack at the start?

By the formal definition PDA has the initial stack symbol $Z$ with which a computation starts.

The idea is to use three stack symbols $Z, Z_{even}, Z_{odd}$ to keep track of whether the number of $a$s read so far is even or odd. If the PDA reaches the end of string and topmost symbol is $Z_{odd}$ then empty the stack.


How does CNN deal with rotation invariant pictures? I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply some rotation invariant techniques? . Few person on stack overflow says that max pooling does rotational invariance , some person says that there is rotational invariant CNN architecture . Give me solid reason that how CNN deal with rotational invariant pictures ? Elaborate the answer .
In machine learning , we do some features extraction techniques like SIFT , SURF etc. and apply some algorithm on it, their features are scale and rotation invariant . How about in CNN ?

With a standard CNN, features are not rotation invariant, and the are not rotation equivariant.  They are translation equivariant, but not rotation equivariant.
If you would like the model to be rotation invariance, then there are fancy methods to provide that, and simple methods.
The fancy method is to use a rotation-equivariant neural network.  There are many research papers on this subject.  See, e.g., Deep Rotation Equivariant Network by Li et al., Learning Steerable Filters for Rotation Equivariant CNNs by Weiler et al., and many others.
The simple method is to use data augmentation.  During training time, randomly rotate the input image before feeding it to the neural network.  You might need to train the neural network for more epochs.
Data augmentation is a lot easier to implement, and my impression is that it gives results that are close to what can be achieved with the fancy methods.  Therefore, I suggest you try data augmentation first.


Simple question about signed integer multiplication If you have a signed integer int x = any
And then state that x < 0
Is the following statement true or false?
((x*2) < 0)

The answer is false, which seems counter intuitive. Is it because X can be any negative value, it can also be a very big negative value which will overflow if multiplied by two.
So if I have the number -30768 1000011111010000
which multiplied by 2 is -61536 11111111111111110000111110100000
But because we only have 16 bits the last 16 are taken resulting in 0000111110100000 which is positive.
Is this the correct explanation? I can't seem to find a good source

Your answer is nearly right.
So x is an unsigned negative value of k bits. The smalles possible value of x is representet by the 2's Complement number 1000....0. If you multiply this number by 2 (or logical shifting it by 1, which is equivalent) you end up with the number 0000...0 which is 0. And therefore (x*2)<0 is false.


Minimum number of sets of points During my work I've encountered this problem:

$G = \{(x_i,y_i,z_i)\}_{i=1}^{n}$ is a group of points in space ($\forall i \;\;  x_i,y_i,z_i \in \Bbb R$) and $ d \in \Bbb R^+$ is a constant.

Divide $G$ to $m$ groups (as few as possible) that follow this rule: for each pair of points in the same group, the distance between these two points is less than or equal to $d$. ($m$ should be, as said, the minimum)

I thought about solving it by turning it into a graph where each point is a node and 2 nodes are connected if and only if the distance between these 2 points is smaller than $d$. Then the solution is the same as finding a minimal cover of the graph using Cliques. This is an NP problem and thus can't be solved in polynomial time unless P=NP. So that doesn't provide a useful solution.

Does anybody have any idea how to solve this problem?

I can't access the paper itself, but judging by its abstract and a mention on p. 5 of this paper, a slight generalisation of your problem was proved NP-hard in 1978: Complete-Link Cluster Analysis by Graph Coloring (Pierre Hansen and Michel Delattre).  I say "slight generalisation" because (I assume that) the problem proved hard allows arbitrary distances between points; it's possible that Euclidean version of the problem, which you seem to have, is easier.  Maybe even the metric version is easier.

For the case of exactly 2 clusters, Wikipedia gives a poly-time algorithm based on 2SAT.


Reduction between two decision problems We are given two decision problems: $Q_1\colon I_1\to\{0,1\}$ and $Q_2\colon I_2\to\{0,1\}$.

By definition, if there exists a function $f\colon I_1\to I_2$ such that for each $x\in I_1$ we have $Q_1(x)=Q_2(f(x))$ then $Q_1$ can be reduced to $Q_2$ by $f$.

Now suppose that $Q_1$ can be reduced to $Q_2$ by a given $f$. My question is: is that true, that there always exists a function $g\colon I_2\to I_1$ such that for each $y\in I_2$ we have $Q_2(y)=Q_1(g(y))$?

I believe so. Since the reduction of $Q_1$ to $Q_2$ by $f$ can be executed in a finite number of well-described steps and since I know explicitly the mapping: $I_1\to I_2$ I think there has to be a way to "reverse" the operation of reduction. Am I right? Is there a formal proof?

First, your definition of reducibility needs to include some sort of restriction on the power of $f$: typically, for example, we require the function to be computable.

Without this restriction, any two decision problems (except the trivial problems "always yes" and "always no") are reducible to each other.  Since there are always $y$ and $n$ such that $Q_2(y)=1$ and $Q_2(n)=0$, there is always a function $f$ that reduces $Q_1$ to $Q_2$: just take
\begin{equation*}
  f(x) = \begin{cases}
         \ y &\text{if }Q_1(x)=1\\
         \ n &\text{if }Q_1(x)=0\,.
         \end{cases}
\end{equation*}

So, we typically restrict to computable functions $f$ as reductions.  Your question is, essentially, is a computable reduction always reversible? The answer to this is no and the reduction $f$ above gives a big hint why: that function is not invertible and there's no reason, in general, to expect that even a computable reduction should be invertible.

For example, consider any decidable problem $Q_1$, and let $Q_2$ be the halting problem.  In this case, we can take $y$ to be the description of any Turing machine that halts immediately, and let $n$ be any Turing machine that just moves the head right forever.  Since $Q_1$ is decidable, the reduction $f$ above is computable.  It tells you how to translate questions about $Q_1$ to questions about the halting problem.  It also kind of tells you how to translate questions about whether or not $y$ and $n$ halt into questions about $Q_1$.  But it doesn't help you determine whether any other Turing machine halts – and it can't, because that problem is undecidable.


Distributivity of $\omega$-regular expressions Recall that a language is $\omega$-regular if and only if it is recognized by a Büchi automaton. How can I prove that

$\qquad (E_1 + E_2).F^\omega$

is equivalent to

$\qquad {E_1.(F^\omega)+E_2.(F^\omega)}$

where

both expressions are omega regular expressions, and
$E_1$, $E_2$ and $F$ are arbitrary regular expressions with
 $\epsilon \notin L(F)$.

One way I could think of is to convert expression to a DFA and check
if it is equivalent.

Or I will really appreciate a hint on how to do the equivalence
proof, but how to represent $E_1$, $E_2$ and $F$ in DFA.

As suggested by Raphael, here's a proof doing it via the sets represented by those expressions.

$\qquad L_\omega((E_1+E_2) \cdot F^\omega)  \\= L(E_1+E_2) \cdot L_\omega(F^\omega) \\= (L(E_1) \cup L(E_2)) \cdot L_\omega(F^\omega) \\= \{w_1w_2 | w_1 \in (L(E_1) \cup L(E_2)) \wedge w_2 \in L_\omega(F^\omega) \} \\= \{w_1w_2|(w_1 \in L(E_1) \wedge w_2 \in L_\omega(F^\omega)) \lor (w_1 \in L(E_2) \wedge w_2 \in L_\omega(F^\omega))\}\\= \{w_1w_2|(w_1 \in L(E_1) \wedge w_2 \in L_\omega(F^\omega))\} \cup \{w_1w_2|(w_1 \in L(E_2) \wedge w_2 \in L_\omega(F^\omega))\} \\= (L(E_1)\cdot L_\omega(F^\omega)) \cup (L(E_2)\cdot L_\omega(F^\omega))\\=L_\omega(E_1 \cdot F^\omega) \cup L_\omega(E_2 \cdot F^\omega)\\=L_\omega(E_1\cdot F^\omega + E_2 \cdot F^\omega)$

So the only thing that's actual work here is to translate the logical operators into set operators.


Bayesian updating for multivariate Gaussian I am reading http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf and come across this slide

What has been confusing me boils down to showing that multivariate Gaussian is conjugate to itself given a Gaussian likelihood. I did quite a bit of searching on both this site and on Google and found the Kevin Murphy's slides showing the univariate case. I tried to generalize to the finite-dimension case but failed in matching the coefficients.

Can somebody help me in deriving the posterior form given the prior and the likelihood? Thank you!

Prior:

$$p_0(\theta_a) \varpropto \text{exp}(-\frac{1}{2}\theta_{a}^{T} (\lambda I_d)^{-1} \theta_a) = \text{exp}(-\frac{1}{2} \frac{1}{\lambda}\theta_{a}^{T} \theta_a)$$

MLE:
\begin{align*}
p(y_{t,a} | \theta_a) &= (2 \pi)^{\frac{n_{t,a}}{2}} |\sum|^{\frac{1}{2}} \text{exp}(-\frac{1}{2} (y_{t,a} - D_{t,a} \theta_{a})^{T} I_{n_{t,a}}^{-1} (y_{t,a} - D_{t,a} \theta_a)) \\
& \varpropto \text{exp}(-\frac{1}{2}(y_{t,a} - D_{t,a} \theta_{a})^{T} I_{n_{t,a}}^{-1} (y_{t,a} - D_{t,a} \theta_a))
\end{align*}

Hence,
\begin{align*}
p_{t,a}(\theta_a) &\varpropto \text{exp}(-\frac{1}{2} \frac{1}{\lambda} \theta_{a}^{T} \theta_a) ~ \text{exp}(-\frac{1}{2}(y_{t,a} - D_{t,a} \theta_{a})^{T} I_{n_{t,a}}^{-1} (y_{t,a} - D_{t,a} \theta_a)) \\
                  &\varpropto \text{exp}(-\frac{1}{2} (\frac{1}{\lambda} \theta_{a}^{T} \theta_a + y_{t,a}^{T} y_{t,a} - y_{t,a}^{T} D_{t,a} \theta_a - \theta_{a}^{T} D_{t,a}^{T} y_{t,a} + \theta_{a}^{T} D_{t,a}^{T} D_{t,a} \theta_a))
\end{align*}

By definition, we also have
\begin{align*}
p_{t,a}(\theta_a) &\varpropto \text{exp}(-\frac{1}{2}(\theta_a - \hat{\theta_{a}})^{T} A_{t,a} (\theta_a - \hat{\theta_a})) \\
                  &\varpropto \text{exp}(-\frac{1}{2}(\theta_a^T A_{t,a} \theta_a - \theta_a^T A_{t,a} \hat{\theta_a} - \hat{\theta_a}^T A_{t,a} \theta_a + \hat{\theta}^T A_{t,a} \hat{\theta}))
\end{align*}

And so we have
\begin{align*}
\text{exp}(-\frac{1}{2} (\frac{1}{\lambda} \theta_{a}^{T} \theta_a + y_{t,a}^{T} y_{t,a} - y_{t,a}^{T} D_{t,a} \theta_a - \theta_{a}^{T} D_{t,a}^{T} y_{t,a} + \theta_{a}^{T} D_{t,a}^{T} D_{t,a} \theta_a)) &= \text{exp}(-\frac{1}{2}(\theta_a^T A_{t,a} \theta_a - \theta_a^T A_{t,a} \hat{\theta_a} - \hat{\theta_a}^T A_{t,a} \theta_a + \hat{\theta}^T A_{t,a} \hat{\theta})) \\
\frac{1}{\lambda} \theta_{a}^{T} \theta_a + y_{t,a}^{T} y_{t,a} - y_{t,a}^{T} D_{t,a} \theta_a - \theta_{a}^{T} D_{t,a}^{T} y_{t,a} + \theta_{a}^{T} D_{t,a}^{T} D_{t,a} \theta_a &= \theta_a^T A_{t,a} \theta_a - \theta_a^T A_{t,a} \hat{\theta_a} - \hat{\theta_a}^T A_{t,a} \theta_a + \hat{\theta}^T A_{t,a} \hat{\theta}
\end{align*}

Equating the "second coefficient" of $\theta_a$
 $$\theta_a^{T} (\frac{1}{\lambda} I_d)\theta_a + \theta_a^T D_{t,a}^T D_{t,a} \theta_a = \theta_a^T A_{t,a} \theta_a$$
Hence $A_{t,a} = D_{t,a}^T D_{t,a} + \frac{1}{\lambda} I_d$,

Similarly, equating the "first coefficient" of $\theta_a$, we have $$\hat{\theta_a}^T = A_{t,a}^{-1} b_{t,a}$$


when to use preorder, postorder and inorder binary search tree traversal strategies What are some examples of when to use preorder/postorder practically? When does it make more sense than in-order?

"Whatever you want in your application. This is like asking when you should drink beer, orange juice or water", commented by one wise user, Gnasher729.

"You use whichever gives you the results you need. Your question is like asking 'What are some examples of when to use subtraction/multiplication practically? When does it make more sense than addition?'", commented by another wise user, David Richerby.

What do the above similes mean exactly? If you have understood what are preorder/postorder and inorder traversals clearly, it becomes obvious for you to choose which one make more sense to use.

So the best answer could simply be reviewing the definition of those traversals. Here is one way to understand them in the usual context of binary trees.

A preorder traversal visits the root node first, followed by a preorder traversal of the left subtree, followed by a preorder traversal of the right subtree.
An inorder traversal does an inorder traversal on the left subtree, followed by a visit to the root node, followed by an inorder traversal of the right subtree.
A postorder traversal does a postorder traversal of the left subtree, followed by a postorder traversal of the right subtree, followed by a visit to the root node.

In a nutshell, each traversal traverses a binary tree recursively. The "pre/in/post" refers to when the root node, which store the value in the middle, is visited, which is first, between first and last, and last respectively. Note that left subtree is always visited before right subtree.

Understanding cannot be solid without relevant examples and exercises. You may check for example chapter 12, "Binary Search Trees" of CLRS to find some.

Here are some usual usage examples.

Preorder traversal is used to get prefix expression on of an expression tree, Polish notation
Postorder traversal is used to get postfix expression of an expression tree, reverse Polish notation
In case of binary search trees, inorder traversal will traverse  nodes in non-decreasing order. This is probably the easiest result if not the most common result. To traverse nodes in non-increasing order, inorder traversal but visiting right subtree before left subtree can be used.


Steiner tree problem with the known optimal subset of Steiner vertices in approximation algorithms I want to prove that the hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree and I need to show this by proving that if this set is provided, then the optimal Steiner tree can be computed in polynomial time.

It is clear that we can find an MST on the union of this set and the set of required vertices with Kruskal algorithm, and by contradiction proof, can be said that if this union of sets didn't give the MST so the subset of Steiner vertices is not the optimal subset.  Any hints or tips would be appreciated.

It can be proved as I mentioned with  contradiction, assume that $S1$ is the optimal subset of steiner nodes and $R$ is the required nodes, so we give the subgraph of main graph including $S1$ and $R$ nodes and the edges between them to Kroskal algorithm then we have a MST for them, we assume that it is not equal to OPT (solution for steiner tree problem), so the given subset (S1) was not optimal I mean at least one steiner node was not given or was given falsly.


Myhill-Nerode Theorem DFA Minimization I am learning how to minimize a DFA. One helpful approach is the Myhill-Nerode Theorem, which explains:

Draw a table for all pairs of states (P,Q)
Mark all pairs where P is a final state and Q is not a final state.
If there are any unmarked pairs such that [delta(P,x), delta(Q,x)] is marked, then mark (P,Q)
Combine all the unmarked pairs and make them a single state in the minimized DFA.

I'm a little lost on the details of the third step.

In the example here, the unmarked pairs in the resulting table are (a,b), (c,d), (c,e), (d,e). The tutorial combines the latter three into a single state such that there are now two states (a,b) (c,d,e).

What are the rules for combining unmarked pairs? Can you combine two pairs
as long as each pair shares a letter with the other? And does the new, merged state take the union of transitions of previous state?

For instance, if state C went to state F on 0 and state D went to state F on 1 and state E never went to state F, then the new, merged state would go to F on 0 or 1, yes?

It's much better to understand what this marking means. Rather than just follow an algorithm blindly, it's preferable to understand what's going on.

Let us say that two states $q_1,q_2$ are equivalent if $\delta(q_1,w) \in F$ iff  $\delta(q_2,w) \in F$ for any word $w$. The simplest case in which two states are inequivalent is when $q_1 \in F$ but $q_2 \notin F$ (or vice versa). When this happens, we can mark this pair of states as an inequivalent pair of states. This is what happens in Step 2.

In Step 3, we make the following observation. Suppose that $q_1,q_2$ are inequivalent, and that $\delta(r_1,\sigma) = q_1$, $\delta(r_2,\sigma) = q_2$. Then $r_1,r_2$ are also inequivalent (why?). Accordingly, if $r_1,r_2$ is an unmarked pair (not known to be inequivalent) and $\delta(r_1,\sigma),\delta(r_2,\sigma)$ (known to be inequivalent) then we can mark $r_1,r_2$ as inequivalent as well.

You can show inductively that at the end of Step 3, a pair of states is marked if and only if the two states are inequivalent. Therefore we can merge any pair of unmarked states, obtaining in Step 4 a minimal DFA (again, there is something to prove here).


Randomized Meldable Heap - Expected Height Randomized Meldable Heaps have an operation "meld", which we then use to define all other operations, including insert.

The question is, what is an expected height of that tree with $n$ nodes?

Theorem 1 of Gambin and Malinkowski, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, pp. 344–349, 1998; PDF) gives the answer to this question with proof. However, I do not understand why we can write:
$$\mathbb{E} [ h_Q] = \frac{1}{2} ((1 + \mathbb{E}[h_{Q_L}]) + (1 + \mathbb{E}[h_{Q_R}]))\,.$$

For me the height of the tree is

$$h_Q = 1 + \max\, \{ h_{Q_L}, h_{Q_R}\}\,,$$

which I can expand to:

$$\mathbb{E} [ h_Q] = 1 + \mathbb{E}[\max \,\{ h_{Q_L}, h_{Q_R}\}] = 1 + \sum k  \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k]\,.$$

The probability that the maximum of a height of two subtrees is equal to $k$ can be rewritten using the law of total probability:

\begin{align*}
\hspace{2em}&\hspace{-2em}
\mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k] \\
&= \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L}\leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\
&\hspace{2em} + \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \\
&= \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\
&\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}]\,.
\end{align*}

So at the end I get:

\begin{align*}\mathbb{E} [ h_Q] &=  1 + \sum k \{ \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\
&\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \}\,.
\end{align*}

This is where I am stuck. I can see that $\mathbb{P}[h_{Q_L} > h_{Q_R}]$ is more or less equal $\frac{1}{2}$ (However we need at most $\leq \frac{1}{2}$). But except that nothing leading to the formula from the beginning.

The heights of the subtrees do not seem to be independent to me.

Thanks for help.

In the paper, $h_Q$ isn't the height.  It's the length of a random walk away from the root in a full binary tree (they insist every leaf is "nil"), so the expression they have is the right thing.

Also, you can avoid induction.  The probability of ending at a specific leaf of depth $d$ is just $2^{-d}$.  So the expected length of the walk is

$$
\sum_{\ell\in \text{leaves}(Q)} \text{depth}(\ell)2^{-\text{depth}(\ell)}
$$

which the entropy of a distribution a set of size $|\text{leaves}(Q)|$.


XOR of two NP-Complete languages Given two NP-Complete languages A and B, show that the language:

$L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$

is not necessarily NP-Complete.

Remember $a\bigoplus b$ when $|a|=|b|$ gives 0 when they have the same digit and 1 otherwise.

Example:  0110$\bigoplus$ 0101 = 0011

I have tried to solve this in my exam only was not so accurate..Help needed.

$A\bigoplus B$ can be empty (and thus definitely not $NP$-complete) if we pick $A$ and $B$ carefully. For instance, if all strings in $A$ have even length and all strings in $B$ have odd length then $A\bigoplus B$ is empty.

It is fairly easy to modify any $NP$-complete language $L$ to have either only even (resp., odd) strings: let $L'$ be the language consisting of strings formed by prepending $1$ to any odd (resp., even) length string from $L$ and prepending $01$ to any even (resp., odd) length string from $L$.

Note that we can easily recover the original language $L$ from $L'$ by noting that any string that was originally of odd length starts with a $1$ (and thus we must drop the first character), and any string that was originally of even length starts with $01$ (and thus we must drop the first two characters).


Why does ε-greedy $Q$-learning not oscillate? I have a intuitive question on the convergence of $Q$- learning. In $Q$ learning for each step a $Q$- value is learned for the state-action pair where the action is selected according to the $\epsilon$-greedy policy determined by $Q$ values.

Now my question is due to $\epsilon$-greedy policy (i.e. due to exploration) is it not possible that the $Q$ values oscillates and does not converge ? each time I am giving chance to non-greedy action his value is improved and may be higher than the value of greedy action after some steps and this becomes greedy now and the same thing continues. Is choosing a small $\epsilon$ enough to prevent this ?

The assumptions for Q-learning's convergence proof require that:

  [...] all state-action pairs be visited infinitely often

So the convergence is understood in a mathematical sense - the Q-function converges to its fixed-point as the number of steps approaches infinity.

In practice, even after your Q-function will be good enough to induce an optimal policy, you will observe "unnecessary" updates each time a non-greedy action is chosen. To avoid that, you can set the learning rate to 0 after the acceptable quality of the solution is achieved.

Also, your intuition about modifying the ϵ parameter, in case of ϵ-greedy policy, seems right. Setting ϵ to 0 will have practically the same effect as setting the learning rate to 0 in the situation described above - in case of a non-stochastic environment.


Time complexity of Dijkstra's algorithm for sparse graph I'm not sure I understand the answer to this question:

  Question 9.

  What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, where $V$ is the number of vertices and $E$ the number of edges. Assume that we are implementing the min-priority queue with a binary min-heap. Choose the anwser the that gives the tightest correct bound.

  $O(V^2)$
  $O(V^2+E)$
  $O(E^2)$
  $O((V+E)\log V)$
  $O(V\log V)$

  Answer: 4 $O((V+E)\log V)$

As I understand it, the algorithm runs in $O((E+V) \log(V))$ with binary heap. Thus when, $E = V^2/\log(V)$, shouldn't the overall time complexity be $O(V^2)$?

Discrete Lizard's answer explains various aspects of the question.

Here is an explicit calculation when $E=o(V^2/\log V)$.

$$\lim_{V\to\infty}\frac{(E+V)\log V}{V^2}=\lim_{V\to\infty}\frac{E}{\dfrac{V^2}{\log V}}+\lim_{V\to\infty}\frac{V\log V}{V^2}=0+0=0$$

That means $O((E+V)\log V)\subsetneq O(V^2)$. So $O((E+V)\log V)$ is a tighter bound than $O(V^2)$ when $E=o(V^2/\log V)$.


Big O Unsure (single problem) int a = 0;
    for (int i = 0; i < n*n; ++i) {
        for (int j = 0; j <= i; ++j) {
            a += j;
        }
    }

Could someone help prove to me that this is function is $O(N^4)$.

I remember doing this problem a while back, but now I do not see it.

I understand that the outer loop is $O(N^2)$ but I am unsure of how this would cause the inner loop to be $O(N^2)$ as well

Consider the range of j in the inner loop:

What is its maximum?
What is its average?
What is its average average?


Why half of the medians are greater than the median of medians? I already saw similar question  Counting elements that are greater than the median of medians but I couldn't find my answer in there.

CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers. This is the algorithm:

  Divide the $n$ elements of the input array into $\lfloor n/5\rfloor$ groups of 5 elements each and at most one group made up of the remaining $n$ mod 5 elements.
  Find the median of each of the $\lceil n/5\rceil$ groups by first insertion-sorting the elements
  of each group (of which there are at most 5) and then picking the median
  from the sorted list of group elements.
  Use SELECT recursively to find the median $x$ of the $\lceil n/5\rceil$ medians found in
  step 2. (If there are an even number of medians, then by our convention, $x$ is  the lower median.).
  Partition the input array around the median-of-medians $x$ using the modified
  version of PARTITION. Let $k$ be one more than the number of elements on the
  low side of the partition, so that $x$ is the $k$th smallest element and there are $n-k$
  elements on the high side of the partition.
  If $i = k$, then return $x$. Otherwise, use SELECT recursively to find the $i$ th
  smallest element on the low side if $i < k$, or the .$(i-k)$th smallest element on the high side if $i > k$.

My problem is the steps 2 and 3. It claims

  at least half of the medians found in step 2 are greater than or equal to the median-of-medians x.

Some thing that I can't understand very well. May be there is a misunderstanding in the median-of-median term. What I understand of the median-of-median is in the following:(Every group of five elements is sorted increasing)

  There is a list $A_1 \cdots A_{75}$ of input array

Step1: Sort every group of five elements
$$\overbrace{A_1A_2A_3A_4A_5}\overbrace{A_6A_7A_8A_9A_{10}}\overbrace{A_{11}A_{12}A_{13}A_{14}A_{15}} \cdots \overbrace{A_{71}A_{72}A_{73}A_{74}A_{75}}$$
step 2 of algorithm (get medians)
$$
\overbrace{A_3 A_8 A_{13} A_{18}A_{23}}\overbrace{A_{28}A_{33}A_{38}A_{43}A_{48}}\overbrace{A_{53}A_{58}A_{63}A_{68}A_{73}}
$$
Then repeat recursively (median of medians)
$$
\overbrace{A_{13},A_{38},A_{63}}
$$
$$
x = A_{38}
$$

From what I understand, in the last level we can guarantee that $A_{63}$ is greater than $x$. In step 2 only $A_{68}, A_{73}$ are greater than $A_{63}$ so they are greater than $x$ as well. Since in step 2 $A_{43}, A_{48}$ are greater than $A_{38}$ So at most five elements among 15 elements in step 2 are greater than the $x$. Then why CLRS claims that half of the medians in step2 are greater than $x$?

thanks in advance.

update

If the algorithm of finding median of medians is not what I did above, How can I find the median of medians of step2 in $O(n)$?

Because $x$ is the median of all the $\lfloor n / 5 \rfloor$ medians obtained in Step 2, it is smaller than or equal to half of those medians by definition of median. See the figure below (from CLRS, the 3rd edition; Figure 9.1).

The problem with your example is that you are finding the median-of-medians $x$ recursively, however, without completing all the recursive steps. You should not stop at Step 3 (the "median of medians" step) in the recursion. Continue the remaining steps. In particular, in Step 4, you will use the "Partition" procedure to establish relationships between the medians obtained in Step 2 and this median-of-medians $x$.

For your added problem: You find it recursively. Why is the time complexity $O(n)$? Well, you can follow the analysis in CLRS.


Can the maximum single sell profit by divide and conquer be O(n)? The single sell profit problem is:

Given a list of prices on each day, find the maximum profit that could have been made by buying on one of the days and selling on a later day.

There is a solution with a single scan that is easy to implement and runs in $O(n)$. This question is not about that. It's about the divide-and-conquer solution.
I've read twice that the divide-and-conquer solution to this problem  is $O(n \log n)$: once when this problem is discussed in Elements of Programming Interviews in Python by Aziz, Lee and Prakash (it's problem 5.6), and once in these PDF lecture notes by Kevin Zatloukal of UW (page 23). Both these sources say the divide and conquer solution is slower than a simple scan.
Neither source presents an implementation (it's not the best approach, so fair enough), and the descriptions are a little terse, but reading between the lines they seem to describe a simple divide-and-conquer down to a base case of a single element, whether the merged result is the maximum of the best trade in the two subproblems and the maximum price in the right minus the maximum price in the left.
Here's that in Python
def best_trade(prices: List[int]) -> int:
    if len(prices) < 2:
        return 0
    else:
        best_left = best_trade_2(prices[: len(prices) // 2])
        best_right = best_trade_2(prices[len(prices) // 2 :])
        return max(
            best_left,
            best_right,
            max(prices[len(prices) // 2 :]) - min(prices[: len(prices) // 2]),
        )

The running time of this for a problem of size $n$, $T(n) = 2 T(n/2) + O(n)$ because the max/min call outside the recursion are O(n). By the Master Method analysis this means the algorithm has time complexity $O(n \log n)$ ($a = 2$, $b = 2$, $d = 1$ so we're in the $a = b^d$ case where the complexity is $O(n^d \log n)$).
My question is: can this problem be solved by divide-and-conquer in $O(n)$?

Answering my own question, yes! The trick is to do the work to compute the max and min of the sublists in the divide-and-conquer recursion rather than when merging the results.
To do this, you need an inner function that returns not just the best trade in a subproblem, but also it's min and max. The combine step is then $O(1)$ rather than $O(n)$.
Here's what that looks like:
def best_trade(prices: List[int]) -> int:
    """
    Divide-and-conquer in O(n).
    """
    def f(start: int, end: int) -> Tuple[int, int, int]:
        if start == end:
            return 0, prices[start], prices[start]
        else:
            best_left, min_left, max_left = f(
                start,
                start + (end - start) // 2,
            )
            best_right, min_right, max_right = f(
                start + (end - start) // 2 + 1,
                end,
            )
            return (
                max(best_left, best_right, max_right - min_left),
                min(min_left, min_right),
                max(max_left, max_right),
            )

    # `else 0` for the corner case where prices = []
    return f(0, len(prices) - 1)[0] if prices else 0

Note that the inner function passes the start and end index of the subproblem down the stack, rather than taking slices, because taking slices is $O(k)$, where $k$ is the length of the slice. By passing pointers we keep the work done outside the recursion to $O(1)$.
With this implementation, $T(n) = 2 T(n/2) + O(1)$ which implies this divide-and-conquer algorithm is $O(n)$.
The general pattern here is to do more work (or return more information) than is strictly necessary in the recursion to reduce the work outside the recursion. In this case, the "extra" work done inside the recursion is trivial, so the running time is significantly reduced, at the cost of a slightly less legible bit of code.
One final point: of course the single scan solution is also $O(n)$ and significantly simpler than either divide-and-conquer solution:
def best_trade(prices: List[int]) -> int:
    """
    Single scan in O(n).
    """
    if not prices:
        return 0
    lowest = prices[0]
    best = 0
    for p in prices:
        lowest = min(p, lowest)
        best = max(best, p - lowest)
    return best


Best sort approach for small data sets I am working with small data sets of N elements, usually with N = 8, 16, or 32 elements; all are positive 64-bit float numbers.  I need to identify the smallest N/2 elements.  It is not required that the smallest N/2 elements be sorted, just that I identify which ones they are from among the group of N.  Each program run must perform this sort up to a billion times, so sort speed improvements could generate useful returns for me.  Right now I am using a simple Quicksort that orders all N elements just to prove out my concept.

It is quite likely that my data are not randomly distributed, but I am not yet at the point where I can get a handle on that.

Eventually, the grand design is that this will find its way into the real world via an X-code implementation.

Any recommendations as to what my best sorting strategy ought to be?

Here are two ideas. It's hard to say whether they're any good - you'll have to implement them.

Use (randomized or deterministic) QuickSelect in order to find the median, and then find the bottom half with a single scan.
Use some hard-coded sorting network, e.g. Batcher, bitonic or pairwise. If there is some hardware support for the basic operation of sorting two memory cells, then this can be pretty fast (even though you're not using parallelism). You can also try to come up with your own sorting network that only sorts in your sense - perhaps trimming one of the ones I listed would do.


Finding running time Apologies for this simple question. I found it in the book Algorithms by Sedgewick and Wayne.

Give a formula to predict the running time of a program for a problem of size N when doubling experiments have shown that the doubling factor is $2^b$ and the running time for problems of size N0 is T.

$$ \frac{T(2N)}{T(N)}=2^b.$$

$$ T(N_0)=T. $$

I am not sure how to proceed after that.

Instead of solving the question for you, let me show you what steps you need to take in order to solve this problem on your own.

Suppose that $T(1) = T_0$ and $T(2n) = C T(n)$ for all $n$.

What is $T(2)$? What is $T(4)$? What is $T(8)$? What is $T(2^k)$?

Now suppose that $T$ is monotone: $T(n_1) \leq T(n_2)$ whenever $n_1 \leq n_2$.

If $2^k \leq n \leq 2^{k+1}$, what can you say about $T(n)$?
Can you now deduce the asymptotic rate of growth of $T(n)$ for arbitrary $n$?


Nontrivial examples of sparse languages A language $L$ is said to be sparse if there exist a polynomial $p$ such that $|L \cap \{0,1\}^n| \le p(n)$.

One trivial example is suppose language is over single alphabet $1$ then $$L = \{1^n | n \in Z^+\}$$

Question : What are the other non-trivial  examples of sparse languages?

I don't think that there exists a reasonable characterization of all sparse languages (for instance, it's trivial to define sparse languages that sit arbitrarily high on the arithmetical hierarchy).

However, since $\{0,1\}^*$ has exponential growth, you need to be able to derive some kind of combinatorial property from the language definition. For example, let $k$ be a constant and consider the following language:

$\qquad L = \{x \mid x \text{ contains $k$ ones}\}$

$L$ is sparse, the key observation being that $\binom{n}{k}$ for a fixed $k$ is a polynomial in $n$.


Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses? I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning about writing GUI programs, and the graphical library (GTK) relies on things like signals and callbacks, which I have not seen modeled by either Turing Machines or the $\lambda$-Calculus; can either the $\lambda$-Calculus or Turing Machines model things like signals, callbacks, sleeping/waiting, or buses? If so, where can I find some good reference material to learn more? If not, why not? and are there any formalisms which are capable of expressing such things?

Yes, there are natural extensions of the $\lambda$-calculus for handling I/O, parallelism, concurrency, exceptions, timeouts, etc. In general such things are viewed as computational effects and there is a rich theory of $\lambda$-calculus for computational effects. This is what Haskell monads are about -- Haskell is $\lambda$-calculus extended with features that you are asking about.

But let me point out that you mix a bunch of features together which are really of two different kinds:

Interaction with external environment: I/O, communication, timeouts, concurrency, etc.
Programming models: callbacks, semaphores, shared memory, parallelism, etc.

A classical Turing machine does not interact with an external environment, but it can be modified to do so. For instance, an oracle is essentially an input stream. The so-called "type 2 machines" are Turing machines with infinite input and output tapes which correspond to an input and an output channel, etc. I am sure someone invented "real-time Turing machines", but I think such endaveours miss the point of mathematical models of computation. A mathematical model is designed specifically to fit well a chosen set of features that we want to model. Turing machines were invented to explain what "possible to compute" means, not "how to compute". If you want to model I/O and such then there are better mathematical models to stick to ($\pi$-calculus was suggested by someone).

The second set of features you asked about is really a bunch of programming methods. As is well known, any Turing complete computational model can be used to simulate any other such model. For instance, a Turing machine can compute things in parallel through a technique known as dovetailing. I would not be surprised if dovetailing was invented several decades before the first parallel operating sytem came into existence. (In fact, it must be the case that dovetailing appreaded already in Turing's original 1936 paper, can someone confirm this?)

Callbacks are well known to functional programers, as these are just functions (but if you spend your life programming operating systems in C you will think they are special), while threads and coroutines are known as continuations. So some concepts that look fancy from one perspective are basic and straightforward from another. Another that comes to mind is the object-oriented idea of an "iterator" which gets vastly generalized in functional programming.


Branch Prediction - LOCAL BHR without tag I have a question about the common course "Computer Architecture".

How is it possible to have a LOCAL Branch Predecitor with 1024 entries, 3 bits for HISTORY but without a TAG.

As I understand,in that way i will get a Global branch predictor because i dont have a way to map a branch to an entry. Am I right? If not,How can it be possible?

The 1024 entries would be indexed by bits from the instruction address, so the history is likely to be for the same branch (especially since there is temporal locality in instruction execution, so the same branch is more likely to be executed nearby in time than some other branch that happens to have the same index in the branch predictor). Without complete tags, there is the possibility of aliasing (where the history at a given index is actually from a different branch than the instruction address being looked up), but since only a prediction is provided even destructive aliasing would only cause a misprediction. With 32-bit addresses and fixed-length 4-byte instructions, 1024 entries would use 20 bits per entry for complete tags, requiring over six times as much storage as an untagged table with 3 bits of history per entry.

(Aliasing can reduce prediction accuracy enough that techniques like agree predictors have been developed to reduce destructive aliasing. In an agree predictor a second source of prediction information [usually static for a per-address predictor, often a dynamic per-address table for a global history based predictor since adding the per-address table also allows tournament prediction] provides a bias for the other predictor; instead of predicting taken or not-taken, the other predictor predicts agree or disagree. Bi-Mode prediction is similar, but uses two tables with table selection based on the branch bias.)

For a local history predictor there can also be aliasing in the table translating the local history into a prediction. If only one table is used one branch's behavior could interfere with predictions for another branch. (This is not a terrible design; the Alpha 21264 used a 1024-entry local history predictor with 10 bits of history and a single shared 1024 entry [indexed by the 10 history bits] predictor with 3 bit saturating counters, along with a global predictor and chooser.)

Using tags (even partial tags) allows the use of associativity and the percentage storage overhead is less if the branch target buffer is merged with the local predictor. (A unified direction predictor and branch target buffer would generally have fewer direction entries than separate predictors and BTB entries for unconditional control flow operations do not need direction prediction.) However, direct-mapped structures are faster (and using tags increases energy use), so there are tradeoffs.

(Similar tagging tradeoffs exist for bimodal [distinct from Bi-Mode] predictors, where a single table indexed by a hash of the branch address provides the prediction, typically using either a two bit saturating counter or a prediction bit and a hysteresis bit.)


Calculating the Transfer Time for a Hard Disk I know that transfer rate is data size over transfer speed - but according to the information given, I don't know what the data size is to calculate the transfer rate.  Am I missing something or was I really not given it?

The information given is as follows:

  A number of files are stored on a 10000RPM hard disk. The platters
  rotate clockwise. The heads move at the speed of 250 centimeters per
  second. The controller overhead of the hard disk is 0.2 milliseconds
  per I/O request. The data transfer speed is 100 MB/s.  Assume one I/O
  request is sent for every file. The average seeking distance is 1
  centimeter. Since a sector is very small, ignore the time to rotate it
  through under the head. Calculate the average time to fetch data for
  each of the scenarios below.

  a. 1 file of 10 sectors is fetched. The sectors are randomly distributed on the disk.

I know I need the transfer rate to calculate fetch time - but again - I don't know the data size so I don't know how to calculate it.

Sectors are usually 512B to 4KB. In your case, it seems that the actual time it takes to read the sectors is negligible compared to seeking (verify this!), and this could be what is meant by the following line:

  Since a sector is very small, ignore the time to rotate it through under the head.

To be sure, make the calculation with respect to the largest sector size (4KB), and check that the data transfer time is negligible. If it isn't, you are indeed missing a data point.


How to tell if a minimax search tree is computationally feasible using parallel computing I am trying to apply the minimax algorithm to a game of Pokemon. This is a problem where the search tree is usually around 20 levels deep (number of turns) and each level has 9 or less branches (number of choices per turn).
What I am wondering is if this is a computationally feasible problem using parallel computing? My idea for how to tackle it is to fork a new thread for the first n number of levels to break up the work.
If my math is correct this means that there will be 9^20 operations that need to be split up (technically it will be less since the number of choices per turn decrease as the game gets closer to the end). I was wondering if there is some sort of constant or general rule of thumb I can use to quickly estimate if this problem is computationally possible and worth pursuing or not?
The most ideal outcome would be if the computation can run in 2 minutes or less, but it isn't a requirement.

Plainly, evaluating $10^{19}$ positions is not going to be feasible in 7200 seconds.  But if you use alpha-beta to prune the search tree and have perfect move ordering you can get that down to around $10^{10}$, a number that looks much more reasonable given that chess engines on PC hardware can do a couple million nodes per second easily.  Since alpha-beta is a serial algorithm, you'll have to do more than just naively divide the search tree among processors to reap its benefits, but there has been a great deal of research in this area: start here.


Undecidable problems limit physical theories Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual circuit based construction. Then there can be no decidable physical theory which can determine, given any input setting of the circuits, whether the circuit will halt. This seems a triviality, but doesn’t this give us a weak sort of unpredictability without reference to quantum or chaotic considerations? Moreover we can strengthen the above argument by noting that there is nothing special about the circuit based UTM, so we have that the behavior of a physical system is in general undecidable at any level where a UTM can be constructed.

Edit: as pointed out by both Babou and Ben Crowell, my suggested circuit construction is merely an LBA. As I argued in the comments, I find it easy, and intuitive to imagine a machine which is physical but is not linearly bounded. Simply construct a machine (robot) which can mechanically move left/right on an input arbitrarily many times, and assume it has a finite, but non expiring power source. Now we also run into the problem that the universe is finite, but that lets us conclude either that the universe is finite, or the originally hoped for consequence must be true (that would still be a surprising conclusion to arrive at from the above argument).

This was initially intended as a comment, as it side-steps a bit the
question. But I think it does answer in its own way.

What is known, or attempted so far, shows that connecting computation theory with physics can
be a pretty subtle endeavour, and I am afraid that the approach
suggested in the question is probably a bit too crude. I am not sure it
is much better than the classical argument that, everything being
finite, all we need is finite state automata theory, and that studying
Turing machines is a waste of time.  (Not my view of things)

Why should such issues be addressed with caution

I should probably motivate the above comparison with the finite
automata argument. My perception is that
computability is, maybe even more than complexity, an asymptotic theory: what
matters is what occurs at infinity. But we do not know whether the
universe is finite or infinite. If it is finite, then what would be
the point of considering infinite computations. The following concerns
physics, and I am not a physicist. I do my best to be accurate, but
you have been warned.

We often see the Big Bang as a "time" when the whole universe was a
very tiny something, with a very small size. But if it had a size at
some point, how did it transform into something infinite at a later time. I am not trying to say it is impossible ... I do not have the
slightest idea. But it could be that it always was infinite.

Then, let us consider the universe as infinite. Does it help us? Well,
we have some problems with the speed of light. If we consider what may
be relevant here (where we are), we have to consider that we can be concerned only by
a part of the universe that is included in a finite sphere. The radius
$r$ of that sphere is such that the relative speed of two points at
distance $r$ due to expansion is equal to the speed of
light. According to what we currently know, without a future variation
in expansion speed, nothing outside that sphere will ever be of
concern to us. So the universe is finite for us for all practical
purposes. Actually, things are even worse if you consider the contents
of this relevant universe: it is shrinking (unless there is some
creation process). The reason is that the sphere is expanding beyond
its own diameter, carrying with it some of its content that becomes
irrelevant too. Remark: that sphere is not what is called the
observable universe (which is dependent on the age of the universe), it is much larger.

Thus, not only "our" universe is finite, but its resources might be
shrinking.  It is possible that in so many billions
years, only our galaxy might be still relevant to us (assuming we
still exist), with the Andromeda galaxy which will hit the Milky Way
before then.

Well, I do not know what is considered established at this time, but
it shows at least that assuming infinity is a big assumption.

However, is it the case that physical limitations prevent us from
using computability theory.  All that can be concluded from the above
is that it may be unreasonable to draw physical conclusions from the
theoretical work on Turing Machines and the halting problem.

However the concerned techniques may also give useful results when
applied to devices or formalisms that are not Turing-complete. I would
not try to go into details, if only because algorithmic complexity is
not my area, but I would guess that, if the structure of the universe
is discrete, complexity could be in some form relevant to the behavior
of some phenomena. Of couse, this is only wild speculation on my
part. Some of the research I reference below is related to such
discreteness issues.

Some examples of work relating physics and computation theory

There is a significant body of work trying to tie computation and
physics, most of which I barely know of.  So, please, do not rely on anything I
might say, but simply take it as pointers to search for potentially
relevant work.

A good part of that work is concerned with thermodynamic aspects, such
as the possibility of reversible computing with no energy cost. I
thinks this ties with functional programming as it is side-effects
that cost energy (but do not trust me). You may take wikipedia as an
introduction, but Google will yield many references.

There is also work trying to tie Church-Turing thesis and physics,
involving information density among other things. See for example:

The physical Church-Turing thesis and the principles of quantum
theory
Around the Physical Church-Turing Thesis:
Cellular Automata, Formal Languages, and the
Principles of Quantum Theory,
Physics and Church-Turing Thesis.

I vaguely recall seen other
interesting takes on this, but it escapes me right-now.

Then you have Lamport's work on clocks synchronization and relativity
in distributed systems.

And, of course, you have quantum computing that apparently changes
some (achievable) time-complexities, though it does not affect
computability.

Another take is Wolfram's work on modelling physical laws with
cellular automata, though the real benefits of this work seem
disputed.

I think that trying to understand all this work could get you closer
to understanding how you can tie some computability knowledge with (as implying)
theoretical limitations of the physical world, though the trend so far
was more to tie limitations of computability to (as consequences of)
properties of the physical universe.

One possible problem in all this is the self-embedding of all our
theories (mathematics, computation, physics, ...) within the limits of
concepts that are syntactically expressible (i.e. by a language)
which might set a limit on the expressive power of our science. But I
am not sure whether the preceding sentence has meaning ... sorry about
that, it is the best I can do to express one nagging doubt.

As an account of personal disappointment, I would add that physicists
(at least on http://physics.stackexchange.com) are not very amicable to discussing what other sciences could have to say
about physical issues (though they are quite willing to discuss what
physics may have to say about other sciences).


Is it OK to change any polynomial time to another polynomial time without breaking equivalency of Turing machines? Is it true that adding to a Turing-machine-equivalent an "oracle" calculating any polynomially calculable (in this machine) function using some other nonzero polynomial time than this machine itself could do, leaves the new Turing machine equivalent (in the sense that polynomial algorithms remain polynomial and exponential ones remain exponential)?

Yes.  You can replace the oracle with subroutine calls to the polynomial-time implementation of the oracle.  Or, to put it another way: $P$ is closed under composition.
The running time remains polynomial: if the original Turing machine used $p(n)$ steps, and the subroutine takes $q(n)$ steps, then the resulting machine will use at most $p(n) + q(p(n))$ steps, which is upper-bounded by a polynomial.


Can the lambda string be generated in any grammar? I'm still quite new to regex, and I've seen topics online of people talking about removing lambda productions, but that has yet to be discussed in the class and the only formal definition of the rules in a grammar that I was given by my teacher:
$rule ∈ V$ $\times$ $(V ∪ Σ)^*$
where V is the set of variables and Σ is the set of terminals. Going strictly from this definition, I would assume I should be able to generate an empty string since V and Σ are both sets and that I believe the empty string can be generated from either of those sets.
For an exam I was given this definition of a grammar G:
$S \rightarrow  aS | Sb | a$
and I was later asked to write a regex that would represent this grammar. I figured that $S \rightarrow λ$ should be implicit. In other words, I should be able to generate the string 'b' from $Sb \rightarrow λb$
The regex I gave was $a^*b^*$
The T.A. marked it as incorrect because my regex can generate b, but the grammar G cannot, and because G does not have $S \rightarrow λ$
Can someone explain why $S \rightarrow λ$ would not be included in this grammar based on the definition of $rule ∈ V$ $\times$ $(V ∪ Σ)^*$?
Thank you!

No.  $S \to \lambda$ is not implicit.  It is only present if it is explicitly listed in the grammar, otherwise there is no such production.  There are no implicit rules.  You've misinterpreted the definition.  The definition says what kinds of rules are allowed to be present in the grammar, not what will definitely be present.


Automatic softcore configuration based on intermediate representation (IR) compiler output When compiling a piece of software (with LLVM for exmple), you first transform your code into some kind of intermediate representation (IR code). This IR code needs to be converted to your target specific assembly code.

When we have a fixed processor architecture, often optimizations are made to make the machine run a bit faster, or consume less memory. It is always a trade off when designing the ISA, is this computation general enough to dedicate a separate instruction for it, so that later on when compiling software, these optimizations can be made.

With soft cores, however, we could make a whole new processor every time we have a new piece of code.  Often we see soft cores being designed for a specific purpose, while still keeping them general purpose enough so that they can be reused, or still work well when the software is changed.

It seems possible to, instead of first making designing the processor and then compiling the code for the target, making the processor based on your code. Profiling and debugging could be done on a general purpose machine running the intermediate representation code. Based on those results, an effective instruction set can be generated. With that instruction set, a soft core can be generated.

Designing an instruction set and building a good soft core and making a proper tool chain for target compilation steps is a lot of work, but it seems possible to automate this process. I could not find anything on this topic however.

Is this just too complex to do, and are we just better of having a few settings for your soft core with a bunch of optional extensions? Like you often see with soft cores like the Microblaze or NIOS II.

Or is this already a thing and can I just not find it? I do know of coarse grain reconfigurable architectures, but these are more for parallel computations and aim to replace FPGAs for some purposes.

Also, is this stack exchange the right place for these quite multidisciplinary questions?

Soft cores are still intented to be able to run different applications and have a general purpose, with of course some new instructions or peripherals usefull for the needs of what will run on the FPGA.

When wanting to optimize only one application from a common software programming language to run on a FPGA, there are already some compilers trying to do this, like recently reconfigure.io which aims to use Go: https://reconfigure.io/

If the project doesn't need to be able to load and run new programs in a general way, you're better to not use a soft core as it will waste a lot of resources on your FPGA.

If for example you're using the LLVM IR representation of a software, you could effectively optimize a soft core for it, but it's losing the aim of a core to be able to run multiple programs efficiently. If you're intending to run only one program in an optimized way, generating an hardware description of it (like what you're doing by using languages such as VHDL or Verilog) will be more efficient.


Applicability of Machine Learning on Images. I am trying to use machine learning to detect and locate an object in a greyscale image. I have about 700 images which are 360x360 pixels in size.
See below for an example of the object and image:

In the first image, the object is indicated by the red arrow. In the second image, the object doesn't exist. Additionally, the object can occur anywhere along the X-axis (labelled theta) with a very slight bias towards the central pixels.

I tried to reduce the number of features by collapsing the image to a 1D array, like so:

array = numpy.sum(numpy.absolute(image), axis=0)

This ensures that I don't discard information that is crucial to my objectives (detecting and locating).

I now have a 1D array which is whiter at indices where the object is located and no noticeable brightness when the object is absent. So I created a training set of 500(samples) x 360(features) with 200 other samples reserved for cross-validation, and trained an SVM on it. The results on the cross-validation samples reported an accuracy of about 66%, and this doesn't seem to change with the number of training samples.

So I have 4 questions for the community:

Does the outlined problem have an acceptable solution in Machine Learning, or does it seem incredibly absurd to apply Machine Learning at all?
I can look for more images, or even synthesise new images from existing ones (by arbitrarily shifting the image left or right). Can I, however,  expect the results to get any better?
With the number of features that I have, what is the number of samples that I must typically have (as a very rough guess, given that you have seen what kind of images I'm dealing with).
The digit recognition problem in Machine learning houses an issue which is relevant to my case -- the algorithm performs poorly when the digits are written off-centre. In my case, the pattern that I am looking for in the 1D array (a bump) is independent of the location so that any one particular group of pixels shouldn't have disproportionate weights. What is one way to work around this limitation? (I'm thinking auto-correlation)

Thank you for your time and help!

It looks plausible that this is the kind of problem machine learning will be good at.  I suspect you might be able to achieve much higher accuracy, but the only way to know for sure is to try it.

For your current approach, the size of your training set is reasonable, assuming you're using a linear SVM.  A linear SVM will have about 360 parameters, and your training set is larger than that, so this is not an unreasonable size of training set.

There are many things you could try, to see if they improve accuracy.  Here are two.

Translation invariance. The properties of an object don't depend on where it is located.  However, the way you're currently training the SVM doesn't take this into account, so you might be missing an opportunity to do a lot better.

One potential solution: first, take all of the positive samples in your training set (the ones that do contain a object) and shift them left or right so the object is in the same position in each (always exactly in the middle).  Take each negative sample and shift it a random amount. Then, train the SVM on the modified training set.  This builds a SVM model that recognizes images that contain an object at the center.  Once you've got a trained SVM model, given a new image I, try all possible ways to shift it and apply the SVM classifier to each; if any of those says "yes", then you've found an object.

A different potential solution that might work better: construct features that are inherently translation-invariant, by definition.  For instance, instead of using the 360 elements of the 1D array as a feature, use the average of the array, or the standard deviation.  Then train a classifier on those few features.

You can probably design some other, more complex translation-invariant features.  For instance, you could try computing the average or standard deviation of the first derivative of the 1D array (the average or standard deviation of $A[i+1]-A[i]$, over all $i$).  Or, rather than doing this on the reduced 1D array, even better, do it on the 2D array: compute some statistics of the first derivative (in the horizontal direction) of the 2D image, and similarly for the first derivative (in the vertical direction).  You could also build a histogram of the intensity distribution of the original 2D image (e.g., 10 buckets; the bucket for 0.2-0.3 counts the number of pixels whose intensity is in the range $[0.2,0.3)$).  You could grid the 2D image into 90x90 non-overlapping cells, where each cell is a 4x4 pixel square, compute the average intensity of each cell, and then compute a histogram of those values.  For instance, this might capture the fact that when there is an object there will be many cells that are all-white, whereas an image with no object probably will have few or no such cells.  Try different ideas along those lines, and you might find some that are effective.

Convolutional neural networks. By reducing to a 1D array, you've thrown away a bunch of information.  You could try applying a CNN classifier directly to the 2D image.  There's been a lot of work on how to do this in the computer vision community over the past 5 years, and CNN's seem to do significantly better than anything else.  You could take a look at the Caffe toolset (or Theano or Tensorflow or any of a number of others).  This might benefit from having more training images, but  you can try it on the set you've already got.

Regularization. Don't forget to use regularization and to optimize hyper-parameters (often, using cross-validation and grid search).


How to get 2-state PDA for CFG? I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown Automaton (PDA). I am however a little bit confused that why this is possible.

Depending on your acceptance definition, you might be able to get away with only a single state. The basic idea is to keep the state information on the stack. The first thing you'd try is for each symbol on the stack to contain the "current state", i.e. each symbol is a tuple $(s,X)$, where $s$ is a state of the original PDA and $X$ is a stack symbol in the original stack alphabet. That way, the state information is stored on the stack. There is a problem here, however: if we pop $(s,X)$, we don't know what state the PDA should be in. For the solution, see these lecture notes. The construction heavily relies on non-determinism.


Why we need to read memory on a write-miss? I noticed that in write-back caches, when the cpu wants to write to a block, it fetches the block from memory and then updates it. If the block is going to be overwritten and changed by processor, why does the cpu need to read that block from memory?

Because write-miss happens only with just a word  missing in a block. So all of the block which contains that word must be fetched and then that special word must be updated.


Where is the second face in a graph with 3 nodes? I understand that to work out the number of faces of a connected planar graph, you use Euler's formula F = A - N + 2, where A is the number of arcs and N is the number of nodes.

For a triangle node (3 arcs and 3 nodes), the number of faces would therefore be 3 - 3 + 2 = 2.

But I can't count two faces, only one (the triangle itself). Where is the second face, or where have I misunderstood?

You probably smack your head against the wall for this but: One face "inside" the triangle, the other one is "outside".


What can be said about the given language? $L = \left \{ ab^{n}a^{n}|n>0 \right \} \bigcup  \left \{ aab^ka^{2k} | k>0 \right \}$

What can be said about the given language L ?

According to me, I think it is CFL and not DCFL as I tried to somehow parse it through a NPDA but not sure though.

The words in the first part start with $ab$, those in the second part start with $aa$.

That should help.


Formal Logic - Natural deduction: Problem with assumptions about exists-negation I'm stuck on how to progress with this proof, despite I have tried, I cannot see the next move.
Given this proof without predicate:

So far what I've accomplished:

My idea is, as I can't see any other option using (-(Sv(P->Q)) as the first assumption in order to introduce a conditional, so the assumption must end in P ^ -Q ^ -S. As you can see I have obatined -Q and -S but, how do I proof P?
SOLUTION:

It is a bit hard to say exactly which introductions you should perform since we don't have your rule set, but I think the over all strategy should be as follows:
From $\neg (S \lor (P \to Q))$ you get $\neg (P \to Q)$.  Since you have $\neg Q$, you should try to introduce $\neg P$ and thus obtain $P \to Q$.  That should be a contradiction and you can conclude $P$.


Randomly select a uniform subsample from a nonuniform dataset I have a dataset of events with timestamps spanning several months. The event rate is "bursty", i.e. there are periods of much higher and lower rate than the average.  I would like to randomly select a subset of these events having approximately uniform time distribution. What weight should be applied to the random sampling?

One approach I've already considered is to histogram the data and weight samples by 1/binheight, but this ends up being dependent on the binning chosen and runs into problems with very sparse samples.

Can the appropriate method also be extended to another, possibly related parameter?  For example, I may have a unix timestamp (1 second resolution) and another parameter measuring phase of the 60 Hz AC power line. My subsample should be uniform in both dimensions.

One approach would be to weight each timestamp with the time since the previous timestamp.  In other words, sort the timestamps in increasing order and then let the timestamps be $t_1,t_2,\dots$.  Now, weight the timestamp $t_i$ with weight proportional to $t_i-t_{i-1}$.  Finally, sample from the timestamps, choosing each possible timestamp with a probability proportional to its weight.  This will ensure that the selected timestamps are distributed uniformly across time.

You can also look at variants of this, where you do some kind of smoothing.  For instance, given a timestamp $t_i$, you can look at the 5 previous timestamps, compute the average duration between them, and choose a weight based on that; this amounts to choosing $t_i$ with probability proportional to $t_i - t_{i-5}$.  Or, you can choose a fixed duration $d$, and choose a timestamp $t_i$ with probability that is proportional to the number of events that occur in the window $(t_i-d,t_i]$ (i.e., proportional to $|\{j : t_i-d < t_j \le t_i\}|$).  The latter is similar to your histogramming idea, so might be a bad choice -- the problem is that you have to choose a fixed duration $d$, which might be problematic.  So try my other suggestions.

There's no way in general to choose a sample that is simultaneously uniform in both dimensions.  For instance, suppose your timestamps are evenly spaced through time, where the earliest 80% have phase 0 and the latest 20% have phase 1; then there's no distribution on timestamps that is simultaneously uniformly distributed in time and uniformly distributed in phase.
However, you can choose one sample that is uniform in one dimension, and uniform in another dimension.


Why does a polynomial-time language have a polynomial-sized circuit? I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs use the same technique used in the Cook-Levin theorem to convert the computation of M on an n-bit input x to a polynomial sized circuit.

What I don't understand is that the resulting circuit is dependent on the input x, because what is being converted into a circuit is the computation of M on the specific input x. By definition of PSIZE, the same circuit must work for all the inputs in a fixed length, and thus is not dependent on one specific input.

So how is the process of creating a poly-sized circuit family for a poly-time deterministic Turing machine works exactly?

Cook-Levin gives one circuit for all inputs of a given size. So although the circuit depends on the input $x$, it only depends on the size of the input. So given TM $M$ with running time $t$, and a number $n$ (the size of input), Cook-Levin gives a circuit $C_n$ of size roughly $t^2$ that solves the problem on all inputs of size $n$. The circuit $C_n$ does not depend on what are the bits of the input for $M$, however we need to know the numbers of input bits as that is going to be the number of input bits for the circuit.


How is the environment designed for testing a reinforcement learning algorithm? I'm working on a project, and have a candidate algorithm which I'd like to test. Before I go any further, I need to get the hang of how to code the "structure" of the environment in which my system is embedded, like what the relevant signals are, how they interact with each other, how they evolve with time, and so on.

I'm looking for resources on design of the environment, for artificial intelligence problems, as I don't want to reinvent any wheels. Any information would be welcome, especially introductory to intermediate level. Thanks!

In reinforcement learning, the "environment" is typically a set of states the "agent" is attempting to influence via its choice of "actions".

For example, in "Reinforcement learning design for cancer clinical trials" by Zhao, Kosorok, and Zeng (2009),

  ..."states" may represent individual patient covariates and "actions" can
  be denoted by various treatments or dose levels.

More abstractly, in "A brief introduction to reinforcement learning" by Murphy (1998),

  The environment is a modeled as a stochastic finite state machine with inputs (actions sent from the agent) and outputs (observations and rewards sent to the agent).

So, the "structure of the environment," what signals are relevant, and how they interact is highly specific to the problem you're trying to solve, as is the choice of where to draw the boundary between the agent and the environment.

In "Reinforcement Learning: an Overview", Sutton and Barto (1998), give an overview of the Agent-Environment interface and note:

  The agent-environment boundary can be located at different places for
  different purposes. ... In practice, the agent-environment boundary is
  determined once one has selected particular states, actions, and
  rewards, and thus has identified a specific decision-making task of
  interest.

"Reinforcement Learning: A Survey" by Kaelbling, Littman, and Moore (1996) also provides an overview of the problem.


Probabilistic analysis of finding 2nd largest value in vector Given the following algorithm for finding the second largest element in a vector:

2ndMAX(v):
  n = length of v
  largest = 0
  second_largest = 0
  for i in 1 to n:
    if v[i] > largest:
      second_largest = largest
      largest = v[i]:
    else if v[i] > second_largest:
      second_largest = v[i]
  return second_largest

How many assignments is the algorithm expected to make to second_largest?

I can see the asymptotic lower and upper bounds on the problem, but how can I approach this probabilistically and give the expected number of assignments?

For the maximum I suppose it is N/2 assignments; but for the 2nd largest I am getting confused. I am trying to divide the cases in: largest comes before second largest, so there are no more assignments past the second largest, but there may be before the largest and between the largest and second largest. But it gets complicated really quickly. I also tried some inductive analysis but couldn't get too far.

Let's assume for simplicity that $v$ is a random permutation of the numbers $1,\ldots,n$. In step $i$, largest is assigned to if $v_i$ is the maximal element among $v_1,\ldots,v_i$ (a "record"), and second_largest is assigned to if $v_i$ is the second maximal element among $v_1,\ldots,v_i$. The probability of each of these events is $1/i$ (the second, assuming that $i \geq 2$), since $v_1,\ldots,v_i$ is a random permutation of $\{1,\ldots,i\}$.

Linearity of expectation shows that the expected number of times that largest is assigned to is
$$
\sum_{i=1}^n \frac{1}{i} = H_n = \log n + \gamma + O\left(\frac{1}{n}\right).
$$
Similarly, the expected number of times that second_largest is assigned to is
$$
\sum_{i=2}^n \frac{1}{i} = H_n - 1 = \log n + \gamma - 1 + O\left(\frac{1}{n}\right).
$$
In both formulas, $H_n$ is the $n$th harmonic number, $\log$ is the natural logarithm, and $\gamma$ is Euler's constant.


How does KMV (k minimum value) perform set intersection better than hyperloglog? In this paper, the author seems to suggest that theta sketches(a variant of kmv) outperforms hyperloglog in cardinality estimation on the intersection of n way streams.

Set Intersection. multiKMV can be tweaked in a natural way to handle set intersection and other set operations.

I am having a hard time understanding how intersection on kmv set can perform intersection accurately

The way I understand it, KMV can be describe by the following

Given a stream of number $x = [x_1, .... x_n]$ if we hash each number in $x$ and produce $h = [hash(x_1).....hash(x_n)]$

KMV attempts to represents and capture the characteristic of the stream by storing $k$ minimum value of $h$

The intersection of 2 streams is basically the naive intersection of 2 kmv set.

However this can't be true because if its true the operation is lossy, and probably cannot sustain more than a couple intersection without loosing its accuracy on estimating cardinality.

Can someone point me a direction on how kmv achieve accurate cardinality estimation of 2 or more streams?

There is no sketching algorithm that is able to estimate the intersection cardinalities without accuracy loss. What is meant by the paper is that it is easy to construct KMV sketches that represent the intersection. However, given two $k$-minimum value sketches, you usually cannot construct a $k$-minimum value sketch for the intersection. You rather end up with a $k'$-minimum value sketch with $k'$ smaller than $k$. Since the number of hashes kept within the KMV sketch determines the estimation accuracy, calculating the intersection also comes with accuracy loss.

For HyperLogLog sketches there is no natural way to construct a HyperLogLog that represents the intersection which makes it more difficult to estimate the intersection cardinality. Since HyperLogLogs can be easily merged, a popular way is to use the inclusion-exclusion principle $|A\cap B| = |A| + |B| - |A\cup B|$ to calculate the intersection cardinality. As investigated by the paper, the accuracy loss of this approach is usually much worse than calculating the intersection cardinality for KMV sketches. However, there also exists another (much more complex) technique for HyperLogLogs which uses the maximum-likelihood method and gives better estimates
than the inclusion-exclusion principle, see https://arxiv.org/abs/1702.01284.


For a graph to be connected, you need at least n-1 edges rigorous proof This fact seems obvious but I was unsure how to go about proving it very rigorous.

Let $|V| = n$ and $|E| = m$ for some connected graph $G$. Then consider the following proposition:

  If a graph is connected then $|E| \geq n-1$, i.e. it needs at least n-1 edges.

The fact seems simple and maybe obvious but I was unsure how to rigorously prove the implication. Maybe contrapositive?

The issue that I have with it is that it nearly feels like an axiom. Is there a way to conclude this without assuming it to be true?

One way to prove this is by showing that a graph on $n$ vertices with $m$ edges has at least $n-m$ connected components. The proof is by induction on $m$. If $m = 0$ the graph is empty and no vertex is connected to any other. Now suppose that the claim is true for $m$ edges, and consider some graph with $m+1$ edges. Let $C_1,\ldots,C_k$ be its connected components. Choose some arbitrary edge $e = (x,y)$, and suppose that $e \in C_i$. Let $A$ be the set of vertices $v \in C_i$ for which there is a path from $x$ to $v$ not passing through $e$. Any vertex in $C_i \setminus A$ has some simple path to $v$ which passes through $e$. This path ends at $e$, and so there is a path from $y$ to $v$ not passing through $e$. This shows that both $A$ and $C_i \setminus A$ are connected even if we remove $e$. Other connected components are not effected by the removal of $e$ (since $e$ doesn't touch any of their vertices), and so if we remove $e$, the graph has at most $k+1$ connected components. The induction hypothesis shows that $k+1 \geq n-m$, and so $k \geq n-(m+1)$, proving the inductive step.

If a graph is connected then it has one connected component, so $n-m \leq 1$, that is, $m \geq n-1$.


Throwing an error when initializing an object in c++ Let's say that when initializing a pet class, I wanted to exclude or disallow dogs or cats as species. What would be the proper way to throw an invalid_argument exception?

using std::string;
#include <stdexcept>
using std:: invalid_argument;
struct Pet {
  const string name;
  long age = 0;
  const string species;
  Pet() : name("Dan"), age(0), species("alligator"){}
  Pet(const string & the_name, const string & the_species): name(the_name),
  species(the_species), age(0) {};
};

Pet(const string & the_name, const string & the_species): name(the_name), species(the_species), age(0)
  {

     if (species == "cats" || species == "dogs")
        throw std::invalid_argument( "received negative value" );
  }


How do i make sure i get the correct Bellman Ford path? I was studying shortest path algorithms and was met with an issue regarding Bellman Ford for the image below.

Following the graph, i see that node 3 has a length of 1 while node 2 has a length of 2. When computing the path from 1 to 8 which is the correct path between 1->2->6->4->7->8 and 1->3->2->6->4->7->8 ?
I can see that 1->2->6->4->7->8 has the smallest path length but i'm confused because node 2 has length 2 while node 3 has length 1.
Will Bellman always give the shortest possible path or might it output a longer path because one of the nodes had shorter length but led to a longer path?

From Wikipedia:

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

What is a shortest path? According to Wikipedia:

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Wikipedia isn't always a reliable source, but in this case the definitions are spot on. Suppose that $G=(V,E,w)$ is a weighted undirected graph. A path between two vertices $x,y \in V$ is a list
$$ v_0 = x, v_1, \ldots, v_\ell = y $$
such that $(v_i,v_{i+1}) \in E$ for all $i < \ell$ (possibly $\ell = 0$). The weight of the path is
$$ \sum_{i=0}^{\ell-1} w(v_i,v_{i+1}). $$
A shortest path between $x$ and $y$ is a path with minimum weight.
The Bellman–Ford algorithm finds the lengths of all shortest paths from a given vertex $x$ to all other vertices. It also generates auxiliary information which makes it possible to find the corresponding shortest paths.


Halting problem vs Universal Language Wikipedia defines halting set as follows:

$H = \{(i, x) |$ program $i$ halts when run on input $x\}$

Ullman defines universal language as follows

$U = \{(M, w) |$ Turing machine $M$ accepts $w\}$

This link says:

The universal TM, $U$, is a TM which takes as input an encoded machine/string pair, $(M,w)$, and performs the actions of $M$ running with input string $w$. The most important achievement is to simulate the accepting (i.e., halting) behavior of M. That is we want:
$M$ halts on $w$   if and only if   $U$ halts on $E(M,w)$
or, in notational terms,
$M↓w$  if and only if  $U↓E(M,w)$

Note that $E()$ is encoding function. Also I feel above defines universal language somewhat different than what Ullman defines. While defining universal TM, Ullman says "$M$ accepts on $w$", whereas above link says "$U$ halts on $E(M,w)$". Its accept vs halt which is I am trying to point out. I feel TM can halt with or without accepting. So I feel the definitions of universal language differs in both sources. Q1. Right?
Thats why the link says:

HALT $= \{ x ∈ \{c,1\}^*: x = E(M,w)$ where $M↓w \}$
HALT is precisely the language accepted by the Universal Turing Machine, U:
$M↓w$  if and only if  $U↓E(M,w)$

where $↓$ seems to be symbol indicating "halts"
But Ullman says:

One often hears of the halting problem for TMs as a problem similar to $L_u$ - one that is RE but not recursive. In fact, the original TM of A. M. Turing accepted by halting, not by final state. We could define H(M) for TM M to be the set of the inputs $w$ such that it halts given input $w$, regardless of whether or not $M$ accepts $w$. Then, the halting problem is the set of pairs $(M,w)$ such that $w$ is in $H(M)$

By this, I feel Ullman disagrees that halting language is what is accepted by Universal TM.
The link also says:

In particular, the universal TM accepts HALT, but no TM can decide HALT.

If I get it correct, I believe "universal TM accepts HALT" means Universal UTM can simulate HTM (accepting TM and w as input) which checks whether input TM halts on input w. Q2. Am I right with this? Q3. But then that does not mean L(UTM) = L(HTM) as said by the same link in fourth quote. Right?
Q4. Can you summarise halting problem vs universal language? I feel the link is somewhat incorrect and Ullman is correct. I believe:

Halting language L(HTM) = {(TM,w) | TM halts on w with or without accepting}

Universal language L(UTM) = {(TM,w) | TM accepts w by halting in final state}

From above definitions, Halting language is not same as Universal language

Universal language can simulate Halting language as follows: (HTM,(TM,w)) | HTM accepts (TM,w) by halting in final state when TM halts on w with or without accepting w

Am I correct with above summary understanding?

So first Q1:
At first the definitions of universal language and the universal machine.
The universal language is defined as you mentioned in the question:
$$ U= \{(M,w)\:|\:\text( TM\:M\:accepts\:w)\} $$
The Universal Turing Machine on the other hand is defined as follows:
A machine, which can simulate an arbitrary TM on arbitrary input. Or you can say: It's a TM U, which you can give a random other TM M and an input w. The Universal TM then simulates the given TM M on that input w.
So the Universal Turing Machine accepts, if and only if the TM M accepts w (because it simulates M on w). It rejects, if and only if, the TM M rejects w. It halts, if and only if the TM M is halting on w (because it simulates M on w). So the Universal Turing Machine accepts the above defined Universal Language.
Now to the question: The definition of the link is a little bit misleading. The Universal TM doesn't accept HALT on default, but you can modify the Universal Turing Machine in a simple way to accept HALT: The reject states are replaced by accept states. The now modified UTM (let's call it U') is accepting HALT. Because now it always accepts, if the machine M is accepting or rejecting the input w, without getting stuck in a loop: U' is accepting, if M is halting on w.
Then Q2:
A "TM M is accepting a language L" means, that it definitely halts on w $\in$ L, but does not mean it halts on w $\notin$ L (it can loop forever). So that means, if the U' is accepting HALT, it holds for sure, only if $(M,w) \in HALT$. If $(M,w) \notin HALT$, the universal TM can halt or can loop forever. So it isn't deciding HALT, it's just accepting HALT.
(Actually it's the slightly modified Universal TM, which is accepting HALT as mentioned in answer Q1.)
Q3:
If you mean the Universal Language with L(UTM) and the halting language with L(HTM), then yes L(UTM) $\neq$ L(HTM).
Q4:
First three points you made are correct.
In the last point you have to be more exact: The (modified) UTM can accept the Halting Language, but cannot decide it. So you can check, whether M halts on w, but it may loop forever.


What is the language feature which allows a variable to be associated with values of different types? In Python,  I can change the types of values associated with a variable:

>>> x=1
>>> x="abc"

In C, I can't do the same.

What is the name of the feature that allows Python to behave so, while not C?

I was wondering if the following language features have to do with  the observation in Python:

no explicit type annotations,instead of explicit type annotations
dynamic typing, instead of static typing
or reference model of variable, instead of value model of variables?

Thanks.

Allow me to address the misconceptions in your question one by one.

In Python, I can change the types of values associated with a variable:
>>> x=1
>>> x="abc"

In type theory, types classify expressions, i.e., syntactic objects, i.e., program fragments. From this point of view, Python has exactly one type. Confusingly, what Python calls “types” are what type theory calls classes of a single type.

I was wondering if the following language features have to do with the observation in Python:

no explicit type annotations,instead of explicit type annotations

Annotations have nothing to do with this. There exist languages, such as ML and Haskell, that allow the programmer to omit most type annotations, yet the type of a variable binding is never allowed to change throughout its scope.
This is not to say that it is impossible to design a programming language in which the type of a variable could change within its scope, but Python is by no means such a language.

dynamic typing, instead of static typing

What I said above about the meaning of “type” in type theory.

or reference model of variable, instead of value model of variables?

There is no such thing as “reference model of variable”. A variable always stands for a value. It just so happens that Python has no values other than object references. For example, the Python expression 2 << 1000 does not evaluate to the number $2^{1000}$. It evaluates to an object that represents the number $2^{1000}$. There can be two different objects that represent the same number, as this snippet illustrates:
>>> x = 2 << 1000
>>> y = 2 << 1000
>>> x is y
False

Of course, in mathematics, it makes no sense whatsoever to distinguish between “this $2^{1000}$” and “that $2^{1000}$”. Since Python's ints do not behave like mathematical integers, Python simply does not have integer values.
Confusingly enough, against established tradition, Python's equality testing operator is called is rather than ==.


Way to solve 5-dimentional Linear assignment problem I faced a problem that looks very hard, the problem is this:

We have 5 people putting dots on a whiteboard, each person uses colored dots with a different color (there are 5 colors, 1 for each person). My job is to  find a cluster of points which contains 3 or more distinct colors. Also, we have some fixed radius $R$, and the distance for each point in a given cluster shouldn't be more than R. Also, there might be points that don't belong to any cluster.

What kind of approach can you suggest? At first, I tried the Multidimensional linear assignment problem, but it seems that this problem is NP-hard, so I want to solve it in a reasonable amount of time (I write code). What kind of solutions can you suggest? Maybe using the fact that this isn't a general problem, I mean we use 2D space where people take action, also there are only 5 people.

If you had as much people as number of people in your clusters (each people must have a dot in each cluster) then maybe you could hope for some divide-and-conquer strategy with polynomial runtime, because of greedy-like regularities. For example, in 1D and with 3 people only, after sorting the points along the axis a greedy sweeping algorithm yields an optimal solution ; with some tweaks maybe this kind of ideas could work in higher dimensions. But with some people who can not be part of a specific cluster, this doesn't seem to work anymore.
If I were you, I'd look for approximation algorithms (good ones are known for the 3d matching). Maybe some of them can yield good approximation factors with your problem's structure.


Longest path of a DAG containing a single node? I'm interested in implementing an algorithm detailed on this Wiki page for finding the longest path of a DAG.

The second part of the algorithm says the length of the longest path of a node with no outgoing edges should be zero, but my programming professor says this node should return 1 as its longest path length. (Perhaps he says this assuming each node's length is set to 0 and a recursive function that visits each node will add 1 to whichever child has the longest path.)

I think that if someone can answer the question: what is the length of the longest path of a DAG containing a single node, then I will have an answer to my question. Though, I'm not sure if a single-node graph constitutes a DAG.

As you can probably tell, I'm new to graphs, so any guidance is appreciated.

You have not misunderstood anything, there is simply a discrepancy of notation: sometimes the length of a path is measured as its number of edges, sometimes as its number of nodes, depending on context. In your implementation, it doesn't matter which convention you use, as long as you are consistent throughout your algorithm. Then if you use the second convention and your algorithm returns $3$ for a particular vertex, it means the longest path to that vertex has three nodes: $abv$. If you use the first convention (which is what this Wikipedia article uses, but not your professor), the algorithm should return $2$, because the longest path has two edges.

If this is an assignment, and your professor uses the convention that paths are measured by their vertices, and says that you should too, then you should too.