title: Role of the MMU in a Page Fault Swap

text:
# Question
Title: Role of the MMU in a Page Fault Swap
When a virtual memory address outside the range of loaded into physical RAM is referenced and a page fault occurs, does the Memory Management Unit rely on DMA (Direct Memory Access) to swap the referenced page into RAM, or is an interrupt routine that uses the CPU to copy in the memory in some more mundane way occur?

Please assume the x86 architecture.

# Answer
For x86 if the hardware page table walker tries to load a page table entry from a speculative access (or hinted by a prefetch instruction) and the Present Bit is zero, then a page-fault exception is generated (*Intel® 64 and IA-32 Architectures Software Developer’s Manual*, Vol. 3A, 4.7 PAGE-FAULT EXCEPTIONS).

The OS then handles this exception by using OS-specific structures to find where the page is stored and return it to memory. (An OS can choose to mark a page as not present even though it is still in memory. This could be used to give the page a brief last chance before being victimized with potentially less overhead in the common case of the page not being reused before another free page is required.)

A transfer from a hard drive is almost certain to use DMA as such is more efficient. (Network storage using something like ISCSI or a network file system would typically have more processor involvement since such protocols are not typically implemented as part of the networking hardware interface.)

Other ISAs with hardware page table walkers would behave similarly. (An ISA whose hardware page table walker uses hashed page tables like Power Servers and Itanium \[which also has the option of using linear page tables\] can have a page table miss from a conflict in the hash table. Such page tables are sometimes used as "software TLBs" in that software fills the page table and like a TLB the page table can suffer a miss, which is different than a hit with the page table entry marked invalid/not-present.)

With a *software* page table walker (e.g., older MIPS, Itanium using linear page tables when the virtual address associated with the location of the PTE is a TLB miss), the software would typically check to ensure the page table entry was marked as valid/present before inserting it into the TLB (loading an invalid PTE usually only makes sense for a sectored TLB entry where multiple PTEs are cached with a single virtual address tag). This avoids an additional exception.
> 3 votes

---
Tags: memory-management, virtual-memory
---


# Question
Title: Random permutations by probability matrix
I have the following problem:

I need to generate $\ell$ random permutations each of length $n$ from a list of $m$ elements ($m \ge n$) by a predefined probability matrix $P$ of size $n$ x $m$.

Distribution probability matrix $P$ = {$p\_{i,j}$} describes the probability that i-th position is occupied by $j$-th element ($i\in \\{1,\dots,n\\}$ and $j \in \\{1,\dots,m\\}$).

Of course $1 \ge p\_{i,j} \ge 0$ and $\sum\limits\_{j=1}^m(p\_{i,j}) = 1$ (rows of matrix P are normalized, to be equal 1)

$\sum\limits\_{i=1}^n(p\_{i,j}) \> 0$ (each element has nonzero probability to be at least on one position)

If $p\_{i,j} = 0$, then $i$th position of permutation can not be occupied by $j$th element. If $p\_{i,j} = 1$, then $i$th position is occupied only by $j$th element

Example: For $$P = \begin{bmatrix} 0.5 & 0.5 & 0 \\ 0 & 0.5 & 0.5 \\ 0.5 & 0 & 0.5\\ \end{bmatrix},$$ I get only two permutations \[1 2 3\] and \[2 3 1\] with the same frequency. But for $$P = \begin{bmatrix} 0.01 & 0.99 & 0 \\ 0 & 0.01 & 0.99 \\ 0.99 & 0 & 0.01\\ \end{bmatrix},$$ I significantly prefer permutation \[2 3 1\]

Realistic values $\ell = 1\\,000$–$10\\,000$, $n = 30$, $m = 50$

Is there any suitable and effective (fast) algorithm?

Edit: The problem is motivated by permutation sampling for stochastic combinatorial optimization. Permutations are parametrized via probability matrix P. The probability matrix P is generated by black-box objective function responses.

Edit2: This is typical algorithm for permutation sampling at stochastic optimization problem:

Generation of partial permutations $x$ by probability matrix $P$

1. Generate a random permutation $(\pi\_1, ... ;\pi\_{n})$ of the set of positions $(1,...,m)$.
2. Define $P(1) = P$ and set $a = 1$.
3. Generate $x\_{\pi\_{a}}$ according to the distribution formed by the $a$-th row of $P(a)$ , that is $(p\_{(\pi\_{a},1)},... ,p\_{(\pi\_{a},m)})$. Thus, element $x\_a$ is placed into position $a$.
4. Obtain $P(a+1)$ from $P(a)$ by first setting the $x\_{a}$-th column of $P(a)$ to 0, and then renormalizing the rows to sum up to 1.
5. If $a = n$ then stop and return $x$; otherwise set $a = a + 1$ and return to step 3.

Matrix $P$ is during optimization cycle obtained by update algorithm, which produce stochastic (not bistochastic) matrix. I want to be sure, that this algorithm is mathematically correct.

# Answer
> 5 votes
Your problem is not well-defined. As David Eisenstat notes in his comment, your matrix actually has to be bistochastic rather than just stochastic, since every convex combination of permutation matrices is bistochastic. Also, there could be many ways of representing a given bistochastic matrix as a convex combination of permutation matrices. As a simple example, the matrix $$\begin{bmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{bmatrix}$$ can be obtained by taking all permutations or just $123,231,312$.

The Birkhoff–von Neumann theorem states that every bistochastic matrix is a convex combination of permutation matrices. Its algorithmic proof gives a polynomial time algorithm that gives such a combination with at most $n^2$ matrices, which is probably optimal or close to optimal. In the literature you might be able to find faster algorithms; if you do, please let us know.

---
Tags: permutations, randomness
---


# Question
Title: Use of Big O Notation in a recent paper by Khot et al
I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075).

The following sentence appears in the third paragraph of the very first page:

> "... the fraction of satisfied constraints is at least $\rho(f) + \Omega(1)$"

At the bottom of page two we have a similar notation where GapCSP(f)$\_{1-o(1), \rho(f) + o(1)}$ is defined.

It is confusing for me where the "limit" is being taken here. Put another way, what is the number that's varying inside the asymptotic notation?

I would think that maybe the limit is taken as the number of constraints goes to infinity, but the paper specifically mentions that fixed *instances* of CSP can have a fraction of $1 - o(1)$ constraints satisfied. But what values could be varying within a fixed instance? (page 2 paragraph 2)

# Answer
In general, when you see big-O notation in algorithms, the default assumption is that the number that's varying is the size of the input. Here the input size is $n+m$.

In this case the claim is valid if you think of it in terms of $m$, the number of constraints.

The claim that is being made here is a very basic claim. It's basically a consequence of the fact that $\text{Var}\[X\] \to 0$ as $m \to \infty$, where the random variable $X$ is the fraction of constraints satisfied by a random assignment. (Heuristically, if you were willing to assume independence, it would follow from the Central Limit Theorem. In this case, you cannot assume independence, but a similar result follows nonetheless.)

If you are not sure how to prove this claim, or were unable to recognize this as a fairly standard concentration result, then you're probably going to find the rest of the paper very difficult going, and you might need to start by reading more basic textbooks and papers before diving into this paper.
> 3 votes

---
Tags: asymptotics, landau-notation, notation
---


title: Max heap conversion

text:
# Question
Title: Max heap conversion
In the binary tree shown below, which of the following trees is created after conversion into a (max) heap?

There are 4 anwsers to choose :

By definition, a max heap is a complete binary tree in which the value in **each internal node is greater than or equal to the values in the children of that node.**, so `a`, `c`, `d` are all correct, but there is only one correct anwser!

What am i missing here ?

# Answer
There is a typo in your options. In option (b) the root should be 16 not 1. The tree thus formed is the correct answer.

To get it from your original tree do this

> for i = floor(Array.Length/2) down to the first element: Max-Heapify(Array,i)
> 1 votes

---
Tags: binary-trees, heaps
---


title: What are activation records?

text:
# Question
Title: What are activation records?
What are the open activation records of a recursive algorithm ?

Edit:

Activation records are the number of times that we call a function that is not finished yet. Correct?

So we can find the number of activation records only when we are given a specific input array and we cannot say something for a general array with dimension n. Or can we?

# Answer
Your question is very poorly stated, except for the title. There is not a single sentence that is really correct or meaningful semantically.

So I will stick to the title, and explain what is wrongt with the text.

Activation records are a programming language implementation concept. Programming languages can be used to implement algorithms in programs, but the concept of an algorithm is an abstract notion, rather than a concrete realization in a specific programming language.

An activation record is a chunk of memory containing usually the local data necessary to execute a subprogram call (the name vary with languages, such as function, procedure, method, subroutine ...), as well as memory and code control flow. More dynamic parts of the data used may be stored in other places (heap).

Thus an activation record is not the number of whatever. But the number activation records in use do, in general, correspond to the number of calls that have not been returned ... though that is not necessarily true in some languages (see below).

In simpler programming languages, subprogram calls are well nested so that the first subprogram to be returned from is the last one that was called. Hence activation records can be stored on a pushdown stack. That will not apply to such control structures as coroutines.

Also, it may be that data in activation records can still be used by the program after the subprogram has been returned. This happens for example when the result of a subprogram can be another subprogram to be executed later (I skip the details).

So, in such a case, one may have to keep in memory more activation records than there are unfinished calls. And the pushdown stack no longer works properly without specific techniques to handle the problem.

Last, this is a general concept. I have no idea what your input array is for or what it does in your program. So that I cannot answer you. Many programs do not have arrays at all, but do have activation records.
> 6 votes

---
Tags: terminology, programming-languages, compilers, recursion, stacks
---


# Question
Title: Maximizing sum of ranges of vertices edges
Consider an arbitrary undirected graph $G = (V,E)$. Suppose you have a collection of $|E|$ positive integers and each integer must be assigned to one edge. Let us denote the collection of integers assigned to vertex $v$'s edges as $w(v)$. How would one assign the $|E|$ integers to the $|E|$ edges so as to maximize:

\begin{equation} \sum\_{v \in V}{max(w(v)) - min(w(v))} \end{equation}

In other words, how would one maximize the sum of the range of each vertice's edge assignments?

As an example, consider the graph pictured below. Same graph, same set of $|E|$ integers, but different assignments of integers to edges leads to the above equation evaluating to either 16 or 18.

# Answer
I'll start by giving a negative example to @seteropere algorithm:

Let $G=(V,E)$, where $$V=\\{x\_1,x\_2,x\_3,y\_1,y\_2,y\_3\\}\ \ \ ,\ \ \ E=\\{(x\_i,y\_i)\mid i\in \[3\]\\}\cup\\{(x\_1,x\_2),(x\_1,x\_3)\\}$$ Let the weight collection be $\\{3,3,2,1,1\\}$.

The proposed algorithm starts by assigning weights $1,2$ and $3$ for $x\_1$, and assume that $(x\_1,y\_1)$ was assigned 1.

This already means that the optimal solution profit (5, see figure) is not obtainable.

---

> That said, this problem is poly time solvable after all , greedily, but differently.

**Hint**: given a graph $G$ such that $\Delta(G)\geq 2$, prove that in the optimal solution there exists a vertex $v$ such that the maximal number and the minimal number are both in $w(v)$.

---

P.S.

The opposite problem, in which we aim to **minimize** $$\sum\_{v \in V}{max(w(v)) - min(w(v))}$$

Is quite interesting by itself.
> 3 votes

---
Tags: graphs
---


# Question
Title: How to find expected number of slots of a certain size k in hash table?
If you can make no assumptions about the hash function, how can you find the expected number of slots of certain size k in a hash table? Looking more for a theoretical proof type of answer than a programming answer.

# Answer
I assume under "size of slot" you mean length of chain in hash table with separate chaining collision resolution.

From Knuth, TAoCP, Vol. 3, 6.4, ex. 34 probability of k-length chain in hash table with $M$ slots and $N$ entries is

$\binom{N}{k} \left ( M-1 \right )^{N-k} / M^N$

Assuming "ideal" hash function, however practical real-world hash functions are often very good and could be considered as "ideal" for applying theoretical results.

Applying famous $e$ representations via limits and Stirling's approximation, I derived that the probability in terms of $α=N/M$ (load factor) is approximately equal to k-th value in Poisson distribution with parameter $λ=α$, i. e.

$\alpha^k e^{-\alpha}/k!$

Seems reasonable and was my first assumption before analysing the formula from TAoCP, because average chain length is obviously $α$, which correspond Poisson distribution expected value.

If $α$ (load factor) is equal to 0.75, then probabilities of slot chains to be of the specific length are:

```
k = 0 -- 0.47
k = 1 -- 0.35
k = 2 -- 0.13
k = 3 -- 0.03
k > 3 -- 0.01

```
> 5 votes

---
Tags: algorithm-analysis, hash-tables
---


# Question
Title: Creating all possible subsets and complexity calculation
I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm. Now I would like to know how to calculate the complexity of the algorithm. Can anyone help me with better clarification. Here is my code:

```
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
int N,M,a[15];
map<int,vector<int> >multiple;
void creating_subset(int i,int m,int l)
{
  if(i>=M)
  {
    multiple[l].push_back(m);
    return;
  }
  creating_subset(i+1,m*a[i],l+1);
  creating_subset(i+1,m,l);
}
int main()
{
  cin>>M;
  for(int i=0;i<M;i++)
  cin>>a[i];
  creating_subset(0,1,0);
  for(int i=0;i<multiple[3].size();i++)
  printf("%d ",multiple[3][i]);
  cout<<endl;
  return 0;
}

```

# Answer
> 1 votes
Your code doesn't really generate all subsets, but it does go over all subsets. The complexity of your code depends on the complexity of the data structures you use, which you'll have to figure out yourself. The proverbial "innermost loop" in your case is the `if (i >= M)`, and this part runs $2^M$ times (once for each subset). If the complexity of the innermost loop is $C$, then the overall complexity of the code would be $O(2^M C)$, since the complexity of all other parts pales in comparison.

---
Tags: algorithms, algorithm-analysis, time-complexity
---


# Question
Title: How does the momentum term for backpropagation algorithm work?
When updating the weights of a neural network using the backpropagation algorithm with a momentum term, should the learning rate be applied to the momentum term as well?

Most of the information I could find about using momentum have the equations looking something like this:

$W\_{i}' = W\_{i} - \alpha \Delta W\_i + \mu \Delta W\_{i-1}$

where $\alpha$ is the learning rate, and $\mu$ is the momentum term.

if the $\mu$ term is larger than the $\alpha$ term then in the next iteration the $\Delta W$ from the previous iteration will have a greater influence on the weight than the current one.

Is this the purpose of the momentum term? or should the equation look more like this?

$W\_{i}' = W\_{i} - \alpha( \Delta W\_i + \mu \Delta W\_{i-1})$

ie. scaling everything by the learning rate?

# Answer
> 11 votes
Using Backpropagation with momentum in a network with $n$ different weights $W\_k$ the $i$-th correction for weight $W\_k$ is given by

$\Delta W\_k(i) = -\alpha \frac{\partial E}{\partial W\_k} + \mu \Delta W\_k(i-1)$ where $\frac{\partial E}{\partial W\_k} $ is the variation of the loss w.r.t. $W\_k$.

Introduction of the momentum rate allows the attenuation of oscillations in the gradient descent. The geometric idea behind this idea can probably best be understood in terms of an eigenspace analysis in the linear case. If the ratio between lowest and largest eigenvalue is large then performing a gradient descent is slow even if the learning rate large due to the conditioning of the matrix. The momentum introduces some balancing in the update between the eigenvectors associated to lower and larger eigenvalues.

For more detail I refer to

http://page.mi.fu-berlin.de/rojas/neural/chapter/K8.pdf

---
Tags: machine-learning, neural-networks
---


title: Lower bound of this harmonic series sum

text:
# Question
Title: Lower bound of this harmonic series sum
I'm stuck on an excercise in my maths class. How can I find an explicit lower bound for the harmonic series sum:

$$\sum\_{x=1}^{2^m}\frac{1}{x}\\,?$$

# Answer
You should have asked this on Math Stack Exchange

But here's the soultion $$\sum\_{x=1}^{2^k}\frac{1}{x}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+ \cdots+\frac{1}{2^k}$$ can be written as $$\sum\_{x=1}^{2^k}\frac{1}{x}=1+\left(\frac{1}{2}\right)+\left(\frac{1}{3}+\frac{1}{4}\right)+\left(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\right)+ \cdots+\frac{1}{2^k}$$ It can be observed that $$\frac{1}{3}+\frac{1}{4}=\frac{7}{12}\>\frac{1}{2}$$ $$\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}=\frac{533}{840}\>\frac{1}{2}$$ similarly $$\frac{1}{2^m+1}+\frac{1}{2^m+2}+\cdots+\frac{1}{2^m+2^m}\>\frac{1}{2}$$ so, $$\sum\_{x=1}^{2^k}\frac{1}{x}\ge1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+ \cdots+\frac{1}{2}$$ $$\sum\_{x=1}^{2^k}\frac{1}{x}\ge1+\frac{k}{2}$$
> 4 votes

# Answer
You can get a very good bound by using an integral. Since $1/x$ is decreasing, we have $$ \int\_t^{t+1} \frac{dx}{x} \leq \int\_t^{t+1} \frac{dx}{t} = \frac{1}{t}. $$ Therefore $$ \sum\_{t=1}^n \frac{1}{t} \geq \int\_1^{n+1} \frac{dx}{x} = \log (n+1). $$ Similarly, $$ \sum\_{t=1}^n \frac{1}{t} \leq 1 + \int\_1^n \frac{dx}{x} = \log n + 1. $$ Even better estimates show that $$ \sum\_{t=1}^n \frac{1}{t} = \log n + \gamma + O\left(\frac{1}{n}\right), $$ and the Wikipedia article on Euler's constant $\gamma$ contains even more accurate expansions.
> 2 votes

---
Tags: discrete-mathematics
---


title: Converting Base 16 to Base 8?

text:
# Question
Title: Converting Base 16 to Base 8?
I understand the basic but what I dont understand is this:

so base 16 to base 10

357/16 = 22.3125 but on this example im looking at says remainder 5?

# Answer
The trick in converting from hexadecimal (base 16) to octal (base 8) is using a (perhaps imaginary) binary (base 2) intermediate. To demonstrate this, let's convert from base 10000 to base 1000, where the intermediate would be decimal (base 10). Consider this number, whose digits are separated by a space:

> 3 1415 9265 3589 7932 3846

The corresponding number in base 1000 is

> 314 159 265 358 979 323 846

This example is not completely academic. In some situations one converts between base 1000, used in many European languages, and base 10000, used in Chinese.
> 0 votes

---
Tags: discrete-mathematics
---


# Question
Title: Word tiling, where you must use each tile exactly once
Given words $w\_1,\ldots,w\_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w\_{i\_1} \cdots w\_{i\_n}$ (in the monoid $\\{0,1\\}^\ast$) for some permutation of indices.

Is this a known problem? Is it NP-complete?

Details:

1. The words $w\_1,\dots,w\_n$ are part of the input. Therefore, there is no a priori upper bound on $n$, $|w\_i|$, or $|w|$. However, we may assume that $|w|=\sum |w\_i|$.
2. If we restrict the problem to instances with $|w\_i|\le k$ (where $k$ is a fixed constant), we obtain a new problem $WT\_k$. $WT\_k$ belongs to $P$. It's possible to build a polynomial-time algorithm for $WT\_k$, using dynamic programming. Indeed, in this case the number of different words $w\_i$ is bounded by $2^k$. Hence any sequence $\\{w\_1,\ldots,w\_n\\}$ can be encoded by a $2^k$-tuple of integers (an element of $\mathbb{Z}^{2^k}$). It is convenient to assume that $w\_i\ne \varepsilon$.

Now with every initial segment $w'$ of $w$ we associate a set of tuples in $\mathbb{Z}^{2^k}$ that describe sequences of $w\_i$'s resulting in $w'$. For instance, with $\varepsilon$ we associate a single tuple $(0,\ldots,0)$ and $\varepsilon$ is considered processed. Then for every processed segment $w'$ we go over its tuples and see which ones we can append to $w'$ (which $w\_i$'s are still available). For instance, if $w' w\_i$ gives another initial segment $w''$ of $w$ then we add the corresponding tuple for $w''$. Eventually, all initial segments will be covered. Here it is crucial that $k$ is fixed, as it ensures that the sets of tuples associated with every $w'$ is polynomially bounded (with a very large degree).
3. I suspect that the general problem is NP-complete and I'd appreciate any suggestions.
4. Clearly the problem can be viewed as a sort of a bounded Post correspondence problem with a fixed collection of pairs $(w,\varepsilon),(\varepsilon,w\_1),\ldots,(\varepsilon,w\_n)$. Not sure if this helps, though.
5. Clearly, the restriction to a binary alphabet is irrelevant. One can work with any countable alphabet. Need to be careful though: the item 2 does not hold when the alphabet is unbounded.

# Answer
I can't speak to whether it's a known problem, but it is NP-complete.

It's clearly in NP, so we just have to show NP-hardness. The following reduction is from the strongly NP-hard 3-partition problem, which asks, given a multiset of positive integers $\[x\_1,\ldots,x\_{3m}\]$, whether there exists a partition into $m$ submultisets such that the sum of each submultiset is equal to the integer $s=\frac{1}{m}\sum\_{i=1}^{3m}x\_i$. For each $i\in\\{1,\ldots,3m\\}$, make a string $a^{x\_i}$. Make $m-1$ strings $b$. The target word $w$ is

$$a^sba^sb\cdots ba^s.$$
> 3 votes

# Answer
The problem is NP-complete. This can also be done very simply with sub-set sum:

Given a set of numbers $x\_1, x\_2, ... x\_n$ that sums to $s$ and a number $k$. For each number $x\_i$, make 2 words $a^{x\_i}$ and $b^{x\_i}$. The word $w$ is $a^{k}b^{k}a^{s-k}b^{s-k}$

* If there is a subset that sums to $k$, then we can construct the word $w$ by using the corresponding $a^{x\_i}$'s to build the first part of the word $w$.

The corresponding $b^{x\_i}$'s are used to build the second part of $w$. All other words are used to form the other part of $w$
* If there is permutation that forms $w$, then we look at the first part that contains just $a$ see which words form that part. And then we take their corresponding numbers from the original subset to form the subset that sums to $k$.

The transformation is in poly-time. For the length of the transformed input, we can encode each word with just a pair of character and number to avoid too long input.
> 2 votes

---
Tags: complexity-theory, np-complete, strings, permutations
---


# Question
Title: A real-world example for a kind of real-time applications
I submitted a paper regarding hard real-time systems to an engineering journal. But the referees generally agreed my task model is too limited. My task model is a frame-based real-time application where all the tasks in the application have a common deadline D and are independent from each other. In the following Figure you can see a model of this application.

The tasks T1 to T5 are independent from each other and have common deadline D.

> "Independent" means that order of the tasks execution is flexible (is not important) or the tasks can be executed concurrently.

There are related works that have considered this type of real-time application, but none of these works include any real-world examples. The referees said that to convince the readers I must provide some real-world examples of this kind of application.

Does anybody know a real-world example for this kind of real-time application?

# Answer
> 1 votes
**Example 1:** Playing a multimedia stream where Task 1 must decompress an audio "frame" while Task 2 must decompress a video frame by the same deadline: the playback time for a given video frame.

This is a little unrealistic though because in practice there's a demux task that task 1 and 2 both depend on, and usually the audio and video playback frames have different repeating deadline frequencies.

**Example 2:** A robot might run all its control loops with the same frequency for simplicity. The control loops all depend on receiving a new set of sensor input values, then they all run, and they all send outputs to the actuators. E.g. Task 1 controls the motor for the left side of the tank drive, Task 2 controls the motor for the right side of the tank drive, while Task 3 controls the robot arm. It just simplifies things a bit to give all the control loops the same deadline unless there are interdependencies such as needing to mux the actuator control data into a single packet to send over a network to the actuators. In that case, a Mux task depends on all the control loop tasks.

---
Tags: operating-systems, applied-theory, real-time
---


title: How is wordnet curated?

text:
# Question
Title: How is wordnet curated?
I use Princeton's WordNet in NLP applications. I always read that it is "human-curated." But how is it curated? Who decides that words belong in a synset? How does the process work? Wikipedia does not give many details. How does it work?

# Answer
> 3 votes
As far as I know, they do the same way they created things like Penn tree bank. They have a panel of experts, usually linguists, who sat together and decided synset taxonomy based on various widely used dictionaries.

PS: Please up-vote me so I can up vote others, thanks :)

---
Tags: natural-language-processing
---


title: Find path to point and avoid bear

text:
# Question
Title: Find path to point and avoid bear
I'm so far a self taught programmer who's mostly been working on simple web and app development. But now my teacher wants me to enter a school competition in programming. Of course the competition is based on problem solving and such, areas I'm guessing counts as computer science. Even though I don't have much experience with this kind of problem solving I have been getting along quite well through the exercise problems.

Unfortunately I'm now completely stuck on one of the harder exercises and I could really use some help.

The problem is as follows: You're in a cave which can be represented as a grid which size is defined by `w` and `h`, the cave also has walls inside it. Your goal is to get to the exit without the bear, who's also in the cave, reaching you. You are able to move only one step at a time and you have to move every tick. The bear is able to two steps at a time to reach you.

But the bear is a bit stupid. First it moves horizontally until it's in the same column as you and then it continues by moving vertically until it reaches you. The bear is not aware of the walls and simply walks right into them.

The output should be a sequence of movements defined as U: up, L: left, D: down and R: right.

I'm currently programming in python but I'm not to interested in a real implementation. I would much rather have directions on how to think and reason to solve these kinds of problems.

I have a few test-cases if needed.

# Answer
The obvious approach for typical path finding problems such as this one is that you store the state of the problem in a data structure, usually a lookup array.

In this case, you will have 2 variables, one for your position and one for the bear's position. Since the bear's movement is dependent on other factor, you can do a top down search approach and recursively check your options.

The running time will be polynomial to the size of the grid which will be $O((wh)^2)$. There might be other optimizations, but this will be the general direction.
> 1 votes

---
Tags: algorithms, artificial-intelligence
---


# Question
Title: Equivalence of some Automata & Language & NFA
I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the language of this figures (nfa, regular expression and grammar):

# Answer
> 1 votes
We'll describe, in words, the languages encoded in each representation. Then, we'll see whether we end up with equivalent languages.

We'll start with the regular expression. This regular expression says: all strings that start with an $a$ or a $b$, followed by any number of repetitions of either of the strings $b$ or $bb$. Note that the $bb$ is completely superfluous in this definition since we can always just choose $b$ twice in a row. So this language is really "either an $a$ or a $b$, followed by any number of $b$s.

Now, for the automaton. The first observation is that the only way we can get an $a$ is if it's the first symbol we see; that's the only place an appropriate transition is defined and we never return to the initial state. We don't need to see an $a$ to accept; we can see a $b$ instead and accept (both $a$ and $b$ are accepted by the automaton). Now, how many $b$s can we see and still accept? Suppose the NFA always goes to state $2$ after the first input symbol (why not? it's an NFA). If we:

* see no more $b$s, we are in an accepting state... so we can see no $b$s and accept
* see one more $b$, we can go to state $4$ and accept
* see two more $b$s, we can go to state $3$ and then return to state $2$ where we accept
* more than two $b$s, we can go to state $3$, back to state $2$, and then we're in exactly the same situation as we were earlier, except now we have 2 fewer $b$s to worry about processing.

This should convince you that we can, in fact, see any number of $b$s after seeing either an $a$ or a $b$. Notice that we get the same thing as we did for the regular expression.

Now for the grammar. We note that the only way to produce a string with an $a$ is to use the production $S \rightarrow aAB$, so if we have a string with an $a$, it starts with an $a$ and that's the only $a$ in the string. In this case, we can always choose $B \rightarrow \epsilon$ and use the productions for $A$ to get any string of $b$s.

However - it appears your concerns were justified. Consider the other production for $S$ - $S \rightarrow bAb$. This is the only way we can get a string that starts with $b$. This production **also** says that any string that starts with a $b$ must have at least two $b$s in it - one at the front, and a different one at the back. In particular, we cannot get the string $b$ from this grammar. But this string is assuredly in the languages of the RE and automaton.

Therefore: $L(r) = L(M) \neq L(G)$.

---
Tags: formal-languages, regular-languages, automata, formal-grammars, regular-expressions
---


# Question
Title: Is $n$ times $O(1)$ equivalent to $O(n)$?
I am having a hard time figuring out if $$\sum^n\_{i=0} O(1) =O(n)\\,.$$

I think it doesn't but I am unable to find a convincing explanation for that, does anyone have an intuitive yet mathematical answer for that?

# Answer
Think in terms of the definition: $f(m)=O(g(m))$ means that there exists some constants $c\>0, M\ge 0$ such that $f(m) \le c\cdot g(m)$ for all $m\ge M$ so when you write $$ \sum\_{i=1}^nO(1) $$ you mean that there are $n$ functions, $f\_1, f\_2, \dotsc, f\_n$ and constants $c\_1, c\_2, \dotsc, c\_n$ such that $f\_i(m)\le c\_i\cdot1$ for all sufficiently large values of $m$. Your sum then is $$ \sum\_{i=1}^nO(1)=\sum\_{i=1}^nf\_i(m)\le \sum\_{i=1}^nc\_i\le \max\_{1\le j\le n}\\{c\_j\\}\cdot n $$ for all sufficiently large $m$. The problem here is, as Hendrik and babou pointed out, the $\max$ term is a function of $n$. For instance, if $f\_i(m) = i$ were constant functions, individually they are all in $O(1)$ but their sum $$ F(n) = \sum\_{i=1}^nf\_i(m)= \sum\_{i=1}^ni = \frac{n(n+1)}{2}\notin O(n) $$ The constants are not the only problem here, though, even if we restricted them all to be bounded by some constant $K$. Suppose we had defined the functions $f\_i(m)$ to be $$ f\_i(m) = \begin{cases} 2^i & \text{if $m\<i$}\\ 1 & \text{if $m\ge i$} \end{cases} $$ Now each $f\_i(m)\in O(1)$, since for each of them we could find a $c\_i\>0,M\_i\ge 0$ such that for all $m\ge M\_i$ we have $f\_i(m)\le c\cdot 1$ (just pick $c\_i=1$ and $M=i$ for instance).

In this case, we also don't have $F(n)\in O(n)$: even though all the $c\_i = 1$ we can't now find a **fixed** N so that $F(n)\le Kn$ for all $n\ge N$, since we chose the functions $f\_i$ so that the "crossing point", $M\_i$, is a moving target. No matter what $N$ you pick, there will be a point where beyond $N$ the sum will be larger than $Kn$.

It seems that the best you can say is that $F(n)=O(n)$ when all of the $c\_i$ are less than or equal to a single fixed bound and the same holds for all the $M\_i$. Useful in some cases, I suppose, but woefully wrong in general.
> 11 votes

# Answer
You are correct to think that the equality $\sum^n\_{i=0} O(1) =O(n)\\,$ is not verified.

Actually, if it has meaning at all, it may be contrived as verified, but not in the way you have in mind.

For the equality to be meaningful, you must consider that the first $n$ is just a parameter that does not grow asymptotically, and that the second $n$ stands for the identity function $\lambda n.n$, which vould be a cleaner notation.

With such assumptions, the equality would be correct if interpreted as inclusion (another problem in common uses of Landau notation), since $\sum^n\_{i=0} O(1)= O(1) \subset O(n)$.

But I suppose that is not what you intended, and that $n$ is supposed to grow asymptotically.

Actually I tried to prove the equality wrong, but my problem was that I think it is meaningless, because the variable $n$ is not really supposed to be used in such definitions, and it appears only as a notational abuse, since $n$ is supposed to be asymptotically at infinity, with respect to the terms of the "finite" sum.

I guess, what you mean by this notation is that a sum of $n$ functions that are each bounded by a constant when $n$ is sufficiently large will be bounded by $Kn$ for some constant $K$ when $n$ grows asymptotically to infinity.. This is not true, as the constants may grow arbitrarily. It is a problem of quantifier order.

Take the following infinite sequence of functions:

$$\forall i\geq 0 \\; f\_i(x)=i$$

These function are all constant, thus

$$\forall i\geq 0 \\; f\_i\in O(1)$$

Then consider the function

$$F(n)= \sum^n\_{i=0}f\_i(n)$$

You are tempted to say that since $\forall i\geq 0 \\; f\_i\in O(1)$, you then have

$$F(n)\in \sum^n\_{i=0}O(1) = (n+1)O(1) = O(n)$$

The argument $n$ of $F$ is supposed to be at infinity, since it is the same as the arguments of the $f\_i$ that are replaced by their asymptotic limits. But then, it is also the upper bound for the sum, which is not at infinity.

Actually you have simply $$F(n)= \sum^n\_{i=0}i = \frac {n(n+1)} 2$$

Hence it is quite clear that $$F(n) \in O(n^2)$$.

and more to the point that $$F(n) \notin O(n)$$.

I can probably give a clearer explanation with time, but the main point is, you cannot use a variable that is already supposed to be at infinity. It is out of your reach :).
> 5 votes

---
Tags: asymptotics, landau-notation
---


title: Showing that A' is a regular language

text:
# Question
Title: Showing that A' is a regular language
Let $\Sigma = \\{0,1\\}$, and suppose that $A$ is a regular language. Define $$A' = \\{ u \mid \exists a, b \in\Sigma: abu \in A\\}$$ i.e., $A'$ is obtained from $A$ by taking every string in $A$ and removing its first 2 characters. Show that $A'$ is regular.

My solution so far is:

* $ab \in \Sigma^\*$ which is regular.
* $A$ is a regular language
* $abu ∈ A$, this means $u$ must be regular for all $abu \in A$ so $A'$ is regular.

Not sure if this makes sense, but please let me know if there's a better way, more formal.

Note: It's not an assignment, I'm just studying for my exam.

# Answer
A *word* cannot be regular, only a *language* can be regular. So it's not clear what you mean by "$ab \in \Sigma^\*$ which is regular", and even less what you mean by "$u$ must be regular for all $abu \in A$".

Given a DFA (or an NFA) $M$ for $A$, you can construct an NFA $M'$ for $A'$ as follows. Let $T$ be the set of states in which $M$ finds itself after reading some $ab \in \Sigma^\*$ (so $1 \leq |T| \leq |\Sigma|^2$), in symbols $$T = \\{ q(\sigma,ab) \mid a,b \in \Sigma \\},$$ where $\sigma$ is the starting state of $M$ and $q$ is its transition function. Add to $M$ a new starting state $s$, and connect it to all sets in $T$ using $\epsilon$ productions. Hopefully you can see why the resulting automaton $M'$ accepts $A'$.

Here is a more difficult exercise for you to try. Show that if $A$ is regular then $\\{u \mid abu \in A\text{ for a }\textit{unique}\text{ pair }a,b \in \Sigma\\}$ is also regular.
> 3 votes

---
Tags: formal-languages, regular-languages
---


title: Runtime of nested loops

text:
# Question
Title: Runtime of nested loops
What is the asymptotic runtime of fthe ollowing piece of code in terms of number of updates to S in worst case.

```
Void foo( int n)
{

    int S = 0;

   for ( i=1 ; i<= n ; i++)
    {

           for( j = 1 ; j<= i*i ; j++)
               {
                  if(j % i == 0)
                     {
                       for( k=1 ; k<=j ; k++)
                       s++;
                     }
               }
     }
}

```

My way :

1. **Outer for loop** will execute **'n' time**.
2. **Middle for loop** will execute **'n^3' times**. Because j is reaching to i\*i.
So if n =10 ,i will move from 1 to 10. j will execute 1\*1 + 2\*2 + 3\*3 + ..... + 10\*10. i.e. 1^2 + 2^2 + ... + n^2 = maximum term is n^3.
3. **Inner for loop** will execute **maximum 'n' times**. Suppose n = 10 , and i reaches to 10 i.e. i = 10 , so j can reach 1 to 10 * 10. In this maximum 10 times i.e. n times 'if loop' condition will be fulfilled.

so total n * n^3 * n = Theta ( n^5 )

But answer is given as Theta ( n^4 ) and explained in totally mathematical terms ( which I didnt get )

Did I make any mistake ?

# Answer
You can get a better bound by taking into account the fact that the innermost loop only runs $1/i$ of the times. The number of times that the body of the $j$-loop is executed is $$ \sum\_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3), $$ as you notice correctly. The innermost loop is run whenever $j$ is a multiple of $i$, that is, for the values $ti$ for $t=1,\ldots,i$. Therefore the $k$-loop is executed this many times: $$ \sum\_{i=1}^n \sum\_{t=1}^i ti = \sum\_{i=1}^n i \sum\_{t=1}^i t = \sum\_{i=1}^n i \frac{i(i+1)}{2} = \frac{n(n+1)(n+2)(3n+1)}{24} = \Theta(n^4).$$ In total, the running time is $\Theta(n^4)$. Note that there is no need to calculate the exact formula; for example, we could use the rough lower and upper bounds $$ \sum\_{i=1}^n i \sum\_{t=1}^i t \geq \sum\_{i=n/2}^n (n/2) \sum\_{t=n/4}^{n/2} (n/4) = n^4/64, \\ \sum\_{i=1}^n i \sum\_{t=1}^i t \leq \sum\_{i=1}^n n \sum\_{t=1}^n n = n^4, $$ which are good enough for our purposes.
> 0 votes

---
Tags: algorithms, asymptotics, runtime-analysis, loops
---


# Question
Title: Solving recurrence relation with two recursive calls
I'm studying the worst case runtime of quicksort under the condition that it will never do a *very* unbalanced partition for varying definitions of *very*.

In order to do this I ask myself the question what the runtime $T(n, p)$ would be in the case quicksort always happens to partition in some fraction $0 \< p \leq {1\over 2}$ such that $\lfloor{p(n-1)}\rfloor$ elements are in the left partition and $\lceil(1 - p)(n - 1)\rceil$ are in the right partition (leaving $1$ element, the pivot, in the middle).

It shouldn't be hard to see that $T(n, p)$ gives an upper bound for the worst case where $p$ is the maximally unbalanced allowed partition, as any partition with fraction $\> p$ will be more balanced and have a smaller runtime, and any fraction $\<p$ is not allowed.

It's obvious that $T(n, {1 \over 2})$ is the best case and $T(n, 0)$ is the worst case of quicksort. Both have easy recurrence relations that are found in any educational resource. But I have no clue how to study $T(n, p)$ in general. The obvious relation would be:

$$T(n, p) = n + T(\lfloor{p(n-1)}\rfloor, p) + T(\lceil(1 - p)(n - 1)\rceil, p)$$

Here I get stuck. I've tried searching around, but all literature that I could understand about divide and conquer algorithms took the "divide" literally and *"cheated"* the analysis using the fact that the partitions are always equal in size, merging the terms into one times a constant.

I do not know how to deal with two recursive calls, and I do not know if it is safe to remove the rounding. Is this possible to solve analytically, and if yes, how?

P.S.: I'm not interested in asymptotics (which is easy to show $\Theta(n \log n)$ for any constant $p$). I am interested in how much slower quicksort becomes as $p$ gets smaller, for example I'm interested in the ratio $T(n, 0.25) \over T(n, 0.5)$.

P.P.S: As an undergraduate student I apologize if I've made obvious things too lengthy or underexplained nontrivialities. And while I don't know if it's looked down upon here so much as other SE sites, I'll note that this is personal interest, not homework.

# Answer
> 9 votes
As you mention, the Akra–Bazzi theorem shows that the solution to the recurrence $T(n,p)$ is $O(n\log n)$ for all $p \in (0,1)$. However, this does not reveal the nature of the dependence on $p$. To determine the latter, we can use a recursion tree approach.

At the root of the recursion tree is the interval $\\{1,\ldots n\\}$. Its two children are the intervals $\\{1,\ldots,pn\\}$ and $\\{pn+1,\ldots,n\\}$, whose total length is again $n$. Each of these nodes has two children (assuming $n$ is large enough), and so on. For simplicity we ignore rounding errors, that is, we assume that $pn$ is an integer; this is just a technicality, and I wouldn't worry about it. We stop the process whenever a node has length at most $1$. The complexity of the algorithm is proportional to the total length of intervals in the tree. When $p \neq 1/2$, the *leaves* (nodes at which we stop the process) have different depth, and that makes it more difficult to determine the overall complexity.

We can obtain a simple upper bound by noting that the tree has at most $\log\_{1-p} (1/n)$ levels: each node is at least a factor of $1-p$ smaller than its parent. Just like in the analysis for $p = 1/2$, the total length of intervals at any level is at most $n$, and we obtain an upper bound of $O(n\log\_{1-p} (1/n))$ on the running time. Since $\log\_{1-p} (1/n) = \log n/\log (1-p)^{-1}$ and $\log (1-p)^{-1} = -\log (1-p) = p \pm O(p^2)$ for small $p$, we can write this as $O(n\log n/p)$.

Here is a more accurate calculation. Consider level $t$. Suppose we don't stop the process upon reaching a small interval. We can generate a random vertex by taking $t$ steps, in each of which we go left (say) with probability $p$ and right (say) with probability $1-p$. Each time we take a left step the log of the length of the interval decreases by $-\log p$, and each time we take a right step it decreases by $-\log (1-p)$. A vertex is in the actual tree of the log of the length decreased by at most $\log n$. The total weight of intervals on level $t$ of the tree is exactly the probability that a vertex generated according to this process correspond to a decrease of at most $\log n$. That is, if $D$ is the distribution which is equal to $-\log p$ with probability $p$ and to $-\log(1-p)$ with probability $1-p$, and $X\_1,\ldots,X\_t \sim D$ are independent, then the total weight of level $t$ is $\Pr\[X\_1+\cdots+X\_t \leq \log n\]$. For super-constant $t$, the random variable $X\_1+\cdots+X\_t$ is roughly normally distributed with mean $\[-p\log p-(1-p)\log(1-p)\]t$ and variance linear in $t$, so for $t$ satisfying $\[-p\log p-(1-p)\log(1-p)\]t \leq (\log n)/2$, say, the probability will be very close to $1$, while for $t$ satisfying $\[-p\log p-(1-p)\log(1-p)\]t \geq 2\log n$, say, it will be very close to zero. Defining $h(p) = -p\log p-(1-p)\log(1-p)$ (known as the binary entropy function), we conclude that the running time is $\Theta(n\log n/h(p))$ (uniform in $p$, as $n\to\infty$). As $p\to 0$ we have $h(p) \approx -p\log p$, and so our earlier estimate was not tight.

Another way of looking at the same analysis is by having an infinite sequence of independent random variables $X\_1,X\_2,\ldots$ as before, and defining a stopping time $T$ to be the first time $t$ such that $X\_1 + \cdots + X\_t \geq \log n$. The running time is then proportional to $n\mathbb{E}\[T\]$. The elementary renewal theorem then states that $\lim\_{n\to\infty} \mathbb{E}\[T\]/\log n = 1/\mathbb{E}\[D\] = 1/h(p)$, implying that the total size of intervals equals $(1+o(1))n\log n/h(p)$. More accurately, for every constant $p$ the total size of intervals is $(1+\alpha\_p(n))n\log n/h(p)$, where $\alpha\_p(n) = o(n)$. The convergence in the elementary renewal theorem is exponential in the time parameter — $\log n$ in our case — so should be polynomial in $n$, that is, $\alpha\_p(n) = O(n^{-C\_p})$. The convergence is also probably uniform for $p \in (\delta,1-\delta)$ for any $\delta \> 0$.

---

Summarizing, the total length of intervals in the recursion tree, which is proportional to the running time, is of the following form for every $p$: $$ T(n,p) = (1+o(1)) \frac{n\log n}{h(p)}, $$ where $\log n$ and $h(p) = -p\log p-(1-p)\log(1-p)$ are taken to the same base, and the $o(1)$ is a function depending on $p$ and tending to $0$ with $n$.

Moreover, it is probably true that for any $\delta \> 0$ and any $p \in (\delta,1-\delta)$ it is true that the total length of intervals is of the form $$T(n,p) = (1+O(n^{-C\_\delta})) \frac{n\log n}{h(p)}, $$ where $C\_\delta \> 0$ and the hidden big O constant depend only on $\delta$. In particular, it should be the case that for all constant $p\_1,p\_2$, $$\lim\_{n\to\infty} \frac{T(n,p\_1)}{T(n,p\_2)} = \frac{h(p\_2)}{h(p\_1)}, $$ and the convergence is polynomially fast.

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation
---


# Question
Title: Maximum single-precision floating-point format number
According to this wikipedia article the maximum single precision is 7f7fffff. Can some explain me why it is (7f7fffff)16 and not (7fffffff)16?

(7f**7**fffff)16 = (0111 1111 **0**111 1111 1111 1111 1111 1111)2
(7f**f**fffff)16 = (0111 1111 **1**111 1111 1111 1111 1111 1111)2

# Answer
> 3 votes
The second exponent is FF, which signals NaN according to Wikipedia, and so the highest exponent is only FE. This is verified by the following C code snippet:

```
unsigned int i = 0x7FFFFFFF;
float f = *(float*)&i;

```

If you print `f` you get `nan`.

---
Tags: number-formats
---


# Question
Title: Proving NP-hardness of strange graph partition problem
I am trying to show the following problem is NP-hard.

> *Inputs:* Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph
>
> *Output:* Partition of $G$, $G\_p=(V,E\_p)$ obtained by removing any $e$ edges from $E$ which maximizes
>
> $$\max \sum\limits\_{G\_i \in \\{G\_1,G\_2,...,G\_k\\}} \frac1{|G\_i|}\left(\sum\_{v\_j \in V\_i}w(v\_j)\right)^{\\!2},$$
>
> where $G\_p=G\_1 \cup G\_2 \cup \dots \cup G\_k$ and elements of $G$ are disjoint.
> $V\_i$ is the vertex set for $G\_i$ and $w(v\_j)$ is the weight for vertex $v\_j$

Plain English explanation: We wish to partition a graph by removing $e$ edges to maximize an objective. The objective computes for each of the resulting disjoint subgraphs the sum of the vertices for the subgraph, squares that value, and divides by the cardinality. Finally we sum this over all subgraphs.

So far I have attempted to reduce from NP-hard problems such as ratio-cut, partition (non-graph problem), and max multicut. I've also attempted to show special cases of the problem are NP-hard (less ideal). The reason I suspect this problem to be NP-hard (besides most graph partitioning problems being NP-hard) is the presence of the cardinality term and cross terms between partition weights. Any input/problem suggestions would be helpful. A NP-hard proof for any kind of specific graph would be useful.

# Answer
Let's reduce multiway cuts problem, a variant of minimum $k$-cut, to your problem. In particular, consider the minimum 3-way cut problem, which is NP-hard for all edge weight equal to 1 (see The complexity of multiway cuts).

A (minimum) 3-way cut problem is: given a graph $G = (V,E)$ and terminals $s\_1,s\_2,s\_3\in V$, find a minimum set of edges $E'\subseteq E$ such that the removal of $E'$ from $E$ disconnects each terminal $s\_i$ from the others. Its decision version is to find out if it's possible to disconnect $s\_1,s\_2,s\_3$ by removing no more than $w$ edges, where $w$ is a part of the input.

Given graph $G$, terminals $s\_1,s\_2,s\_3$ and integer $w$, we would like to reduce the 3-way cut problem to your "strange graph partition problem". For each terminal $s\_i$, we add $N$ more verteces to be its neighbors. As hinted by its name, $N$ would be a sufficiently large number. The weight of all verteces are 0 except for $s\_1,s\_2,s\_3$, whose weights are $1,10,100$ resp. Denote this new graph by $G'$. It's obvious that $s\_1,s\_2,s\_3$ can be disconnected by removing $w$ edges in $G$ if and only if they can be disconnected by removing $w$ edges in $G'$.

If a partition $G'\_p$ of $G'$ disconnects $s\_1,s\_2,s\_3$, its score is roughly $10101/N$, or more precisely, no less than $$\frac{10101}{N+n}$$ as the part containing $s\_i$ has no more than $N+n$ verteces, where $n$ is the number of verteces in $G$. On the other hand, if a partition $G'\_p$ fails to disconnect $s\_1,s\_2,s\_3$, its score is no more than $$\frac{10060.5}{N-w}$$. When $N$ is sufficiently large, $\frac{10101}{N+n} \> \frac{10060.5}{N-w}$, so $G$ can be 3-way partitioned by removing $w$ edges if and only if $G'$ has a partition removing $w$ edges, whose score is at least $\frac{10101}{N+n}$.
> 2 votes

---
Tags: algorithms, complexity-theory, np-hard, set-cover
---


title: Use a Monitor like a Semaphore?

text:
# Question
Title: Use a Monitor like a Semaphore?
When using monitors for most concurrency problems, you can just put the critical section inside a monitor method and then invoke the method. However, there are some multiplexing problems wherein up to n threads can run their critical sections simultaneously. So we can say that it's useful to know how to use a monitor like the following:

```
monitor.enter();
runCriticalSection();
monitor.exit();

```

What can we use inside the monitors so we can go about doing this?

Side question: Are there standard resources tackling this? Most of what I read involve only putting the critical section inside the monitor. For semaphores there is "The Little Book of Semaphores".

# Answer
> 3 votes
Monitors and Semaphores are to accomplish the same task, to ensure that between **n** processes/threads that each enter their critical section atomically. Although Monitors go towards a Object Ordinate Approach to this, making the code easier to read for example. In this case a Monitor is at a higher level then a Semaphore. You can use a Semaphore to implement a Monitor. In that case a Monitor has a `counter` variable in the same way a Semaphore does.

The **V** and **P** of a Semaphore is very much like the **wait** and **signal** of a Monitor. In which *wait* and *signal* are used on a Monitors condition variables. They can be used to implement the same functionality of a Semaphore. Even though there are some minor differences, such as for *signal* with no process in need of being unblocked there is no affect on the condition variable. Along with that locks are also used within the procedure.

While in most cases you don't want to. You *can* use a Monitors *condition variables* and *lock* outside of it (`monitor.lock`,`monitor.condition_i`), basically doing the normal things we do within a procedure but on the outside, not within it's function. This is assuming you want to have the critical section outside of the monitor, otherwise there is no need in doing this:

```
// monitor enter
monitor.lock.acquire();
while(...)  monitor.condition_i.wait( monitor.lock );

runCriticalSection();

// monitor exit
monitor.condition_j.signal();
monitor.lock.release();

```

---
Tags: concurrency, synchronization
---


# Question
Title: How to find $c$ and $n_0$ for Big-Oh questions
I understand the theory behind the definition of Big-Oh, but when I try a question, I don't get how you would find the $c$ and $n\_0$ values.

For example: if $f(n) = n!$ and $g(n) = 2^n$, how would I go about finding the $c$ and $n\_0$ values for $g(n) = O(f(n))$?

# Answer
> 2 votes
In general, you should first set up the inequality and then try to solve for $n$ in terms of $c$. Often, this won't be feasible - there may not be a way to analytically obtain a closed-form solution involving only $c$ and $n$. In such cases, you can usually massage the inequality down to something where solutions can be determined by inspection.

In this case, we can start with the inequality $2^n \leq cn!$. You should be able to convince yourself that this isn't going to be a super-clean solution for $n$ here. Instead, we can try to massage this into a form that can be reasoned about.

Both of these terms involve repeated multiplication; we can write them out like that and see whether we notice a trick: $2 \times 2 \times ... \times 2 \leq c \times 1 \times 2 \times ... \times n$. We notice that the LHS is a product of $n$ terms, and the RHS consists of $c$ multiplied by $n$ other terms. Of the $n$ terms on the RHS besides $c$, all but $1$ are greater than or equal to the corresponding term on the LHS. If we rewrite the RHS as $(c \times 1) \times 2 \times ... \times n$ and choose $c = 2$, we get $2 \times 2 \times 3 \times ... \times n$. All $n$ of these terms are greater than or equal to the corresponding terms on the LHS, meaning the product is bigger, as we wanted. Thus, the choice $c = 2$ works for *all* choices of $n\_0$.

Just to give you an idea of what a boring resolution would look like: let's show that $f(n) = 2n + 3$ is $O(g(n))$ if $g(n) = n + 1$.

We get $2n + 3 \leq c(n+1)$. Solving for $n$, we get $2n + 3 \leq c(n+1) = cn + c$, so $2n - cn \leq c - 3$ and $n(2 - c) \leq c - 3$. Note that if we choose $c \leq 2$, there are no valid solutions for $n$. We now have two cases: either $c \geq 2$ or $c \< 2$. In the latter case, we can write $n \leq \frac{c-3}{2-c}$ which, along with the constraint that $n \> 0$, yields no solutions. In the former case, we write $n \geq \frac{c-3}{2-c}$. You may now plug in any value of $c$ you like and find an $n\_0$ to suit. We can see that the choice $c = 3$ allows us to choose $n\_0 \geq 0$; the choice $c = 2.5$ requires that we choose $n\_0 \geq 1$; etc.

If you're dealing with more complicated functions - specifically, ones that aren't monotonically increasing - you'll want to choose $n\_0$ from the rightmost interval. Otherwise, the functions cross over each other again for a period, making your choice wrong. Usually, you don't have to worry about runtimes being other things than monotonically increasing, but it is a mathematical possibility of which you should be aware.

# Answer
> 1 votes
In this particular case, as $n$ increases by $1$, $g(n)$ doubles while $f(n)$ gets multiplied by $n+1$. That means that for $n \geq 1$, $g(n+1)/f(n+1) \leq g(n)/f(n)$, and so you can choose $n\_0 \geq 0$ of your choice and $c = g(n)/f(n)$.

In the general case, suppose that you know that $g(n)/f(n) \to \gamma$, where $\gamma \neq \infty$. The proof of this should in principle give you a value of $n\_0$ beyond which $g(n)/f(n) \leq \gamma+1$, say. One almost never has to do this sort of thing beyond introductory courses, so I can't offer any more general advice.

# Answer
> 1 votes
Remember that the answer is not unique and you don't need to find the minimal possible values of $c$ or $n\_0$.

For example:

* $n!\geq\tfrac12\times2^n$ for all $n\geq 2$
* $n!\geq\tfrac34\times2^n$ for all $n\geq 3$
* $n!\geq1\times2^n$ for all $n\geq 4$
* $n!\geq2\times2^n$ for all $n\geq 5$

But, in this case, it's enough to observe that $2^n$ doubles each time $n$ increases, whereas $n!$ goes up by a factor of $n$ each time $n$ increases. Therefore, if you can find any $n\_0\geq 1$ and any $c$ for which $n\_0!\>2^{n\_0}$, then $n!\>c.2^n$ for any $n\>n\_0$. For example, $1! \> \tfrac1{1\\,000\\,000}2^1$, so you can take $n\_0=1$ and $c=\tfrac1{1\\,000\\,000}$.

Usually, though, we just use standard facts, such as $p(n)=O(e(n))$ if $p$ is a polynomial and $e$ an exponential. Many of these facts and some techniques for proving them are in the answers to our reference question on Landau notation.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Not understand exchanging argument proof for optimal prefix code
I am currently reading the Algorithm Design textbook by Kleinberg and Tardos and I am having difficulty understanding a proof using an exchange argument

Statement: A binary tree corresponding to the optimal prefix code is full

Proof: This is easy to prove using an exchange argument. Let $T$ denote the binary tree corresponding to the optimal prefix code, and suppose it contains a node $u$ with exactly one child $v$. Now convert $T$ into a tree $T′$ by replacing node $u$ with $v$. To be precise, we need to distinguish two cases. If $u$ was the root of the tree, we simply delete node $u$ and use $v$ as the root. If $u$ is not the root, let $w$ be the parent of $u$ in T. Now we delete node $u$ and make $v$ be a child of $w$ in place of $u$. This change decreases the number of bits needed to encode any leaf in the subtree rooted at node $u$, and it does not affect other leaves. So the prefix code corresponding to $T′$ has a smaller average number of bits per letter than the prefix code for $T$, contradicting the optimality of $T$.

Number of things I do not understand.

1) I thought in an exchange argument, you assume you have a solution T and an optimal solution $T^{\*}$ and you prove that your solution T is no worse than $T^{\*}$ implying T is an optimal solution, but they're not doing that here.

2) They also state that they will "convert $T$ into a tree $T'$ by replacing node $u$ with $v$" but they don't assume that $T'$ is an optimal solution. Why?

3) How does contradicting optimality of $T$ prove that "A binary tree corresponding to the optimal prefix code is full"?

# Answer
> 2 votes
What Kleinberg and Tardos show is that given a tree $T$ containing a node with a single child, they can come up with a strictly better tree $T'$, showing that $T$ isn't optimal. Therefore an optimal tree cannot have a node with a single child. Whether this qualifies as an exchange argument or not is not so important.

More generally, the form of the argument is "if X doesn't satisfy P then X is not optimal; hence any optimal X satisfies P". In order to show that X not satisfying P cannot be optimal, they modify X to obtain a better X'. This is a common enough pattern which doesn't usually have a name attached to it.

---
Tags: proof-techniques
---


# Question
Title: is there any hardware device to convert source code into machine language?
Is there any hardware device inside computer that helps to convert high level language into machine, like compiler and assembler ?

# Answer
> 7 votes
No, and yes.

The answer is "no", in the sense that the vast majority of computers have no hardware that does what you typically expect a compiler to do; compilers are written in software. Obviously this ultimately runs on hardware, but we're talking general-purpose hardware.

However, the answer is "yes", in the sense that the machine code that is actually executed often isn't the same as the machine code that a programmer sees (i.e. the instruction set architecture, or ISA for short). Almost all modern CPUs do some degree of dynamic translation of the "machine code" into a form that is more suited for out-of-order execution.

Intel/AMD-type CPUs, for example, translate machine code into RISC micro-operations (called "uops"). It is these instructions which are scheduled and executed.

ARM has something similar. Its ISA is much closer to the format that's executed, but ARM also features Thumb instructions, which are dynamically translated into "core" instructions. The short-lived Jazelle DBX/ThumbEE did a similar thing with direct execution of JVM bytecode.

Almost all modern high-performance CPUs do this to varying degrees. Indeed, there is a fuzzy line between "dynamic translation" and "instruction decoding".

# Answer
> 1 votes
To complement the very good answer by Pseudonym (this was initially intended as a comment, but became long).

As Pseudonym said, all CPUs can be considered has having some form of translation process of code into more elementary steps, of for more elementary cicuit, and *there is a fuzzy distinction between "dynamic translation" and "instruction decoding".*

But if you go one level up, you have byte-code interpreters. Byte code interpreters translate byte-code (i.e. source code at this level) into machine instructions. The first byte code interpreters were written as software programs. Then people started making specilized computers which looked like their machine code was the byte-code. They actually had byte-code interpreters inside, implemented in microcode residing on high-speed memory. Now again, the line is fuzzy: is an unchanging program in microcode on high speed memory to be considered hardware or or precompiled software. But then, in what sense would it be different from other programmable logic device found in various hardware pieces, and in what sense would these be different from hardware assembled from logical gates with a soldering iron. Actually microcode is often *stored in a ROM (read-only memory) or PLA (programmable logic array) structure, or a combination of both.*

The concept of bytecode dates back to the 1960s, and it was much developed for Pascal implementations in the 1970s as p-code (often understood at the time as *Pascal-code*, though meaning now *portable code*) leading to what is probably the first byte-code machine: the Pascal MicroEngine in 1979. Its *p-code was, effectively, its native machine language*.

Around the same time, the Lisp machine was developed, using microcode to implement an instruction set specialized for Lisp.

To my knowledge, this is about as high as hardware will go in the code ecology, but it does make some room for various translations: what is object code for one level is source code for the level below. From a conceptual point of view, there is no difference between hardware and software as to what they can do. It is mostly an issue of flexibility, speed, reliability and cost-effectiveness. And you prefer to have highly complex structures in software so as to be able to debug them and correct them: hardware bugs can be very expensive to deal with. These parameters also fix the level of programmability from very hard circuitry, to programmable logic, to microcode and read-only memory to standard dynamically programmable memory that may contain the code for a compiler.

These remarks about hierarchical, multi-level translation structures also apply to some extent at the program design level, when the translation from general specification to architecture, to algorithms, to source code is done by humans. The same is or can be true for other concepts such as memory management, caching, parallel processing, communications.

**However**, this answer has been cheating a bit in the sense that it talks only of interpretation, not compilation. Interpretation is pretty much an on the fly translation process, but often (not always: it can be memoized) executes the resulting code immediately without memorizing it as a compiler would. Then, the question is only about conversion, not memorization or compilers. Furthermore, interpreters are usually also considered as program translators.

---
Tags: compilers, interpreters
---


# Question
Title: What is a partially computable function?
In the book *Computability, Complexity, and Languages*, Martin Davis writes in chapter two:

> A partial function is said to be partially computable if it is computed by some program.

and also

> A function is said to be computable if it is both partially computable and total.

From the first definition, a partially computable function must be a *partial function*, but from the second definition a computable function must be partially computable and total which is a contradiction, because a function is partially computable if it is partial and a partial function can not be total at the same time!

# Answer
The definition of *partial function* doesn't exclude the possibility that the function is total. On the contrary, every total function is a fortiori a partial function. Perhaps the terminology is unfortunate.

A *function* from $D$ to $R$ is a subset $f$ of $D \times R$ such that for all $d \in D$ there exists a unique $r \in R$ (denoted $f(d)$) such that $(d,r) \in f$. The *domain* of $f$ is $\operatorname{dom} f = D$.

A *partial function* from $D$ to $R$, where $\bot \notin R$, is a function $f$ from $D$ to $R \cup \\{\bot\\}$. When $f(d) = \bot$, we say that $f$ is *undefined* at $d$. The *domain* of $f$ is $\operatorname{dom} f = \\{d \in D : f(d) \neq \bot\\}$. If $\operatorname{dom} f = D$ then $f$ is *total*. For every partial function $f$, $f|\_{\operatorname{dom} f}$ is a total function.

As you can see, a partial function is a function which can be undefined for some of the inputs; a total function is a partial function which happens to be defined everywhere.

Now regarding computability. Every program computes some partial function $f$ from $\mathbb{N}$ to $\mathbb{N}$; if the program doesn't halt on some input $x$, then $f$ is undefined on $x$, in other words, $f(x) = \bot$. A computable function is one computed by an algorithm which always halts.
> 12 votes

---
Tags: terminology, computability
---


# Question
Title: I am having trouble understanding (and implementing) logistic regression for classifying into three classes
(For reference, i am using Kevin P Murphy's Book "Machine Learning: A Probabilistic Perspective" and implementing with MATLAN - without any toolboxes)

I have a dataset with 392 samples (rows), each sample has 8 features (columns), one of which defines the class (i.e. column 1 of features is divided into three equal bins which define the three classes - low, medium, and high).

I am having a really hard time understanding how to create a logistic regression model to classify a sample into one of these three classes.

I just finished learning and making a linear regression model where I learned about both the Ordinary Least Squares (Closed form) solution for the weight vector, and also Gradient Descent (Open Form) solution. But i never implemented gradient descent because my data was fitted perfectly fine with the OLS solution for weight vector.

I am extremely confused how to create a weight vector for Logistic regression, I understand that it requires use of Gradient Descent because there is no closed form solution. I also read about the Newton method for calculating the weights but I don't understand it at all.

And after you use these methods to calculate weights how do you apply the weights to the sample data? In Linear regression it was simply because you simply multiplied the weights by the features (and higher order features for higher order linear regression), but is it the same in logistic regression?

Moreover my understanding so far is that this model only works for binary classification, so how would i do it for three classes?

Basically my question boils down to this:

How exactly do you find the weight vector for logistic regression (using either gradient descent or newtons method, whichever is easier) and how do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two).

# Answer
> **How do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two).**

If you have $n$ possible classes then you must train $n$ logistic classifiers on your training data, with each classifier producing as output the probability that a given sample is a member of the class the classifier is trained to recognize. Once training is complete, to classify a new sample you let all the trained classifiers try to recognize it and accept the judgment of the classifier that produces the highest probability value. This is known as *one-vs-all* or *one-vs-rest* classification and is a standard way to use binary classifiers to do multiclass classification.

The weights are applied the same way in classifying new data as they are when you're training the classifier. You have a weight vector $\theta$ containing coefficients that when combined with a sample's feature vector $x$ yield an hypothesis value. For linear regression $\theta^T\negthinspace x$ (expanded: $\theta\_0 + \theta\_1x\_1 + \theta\_2x\_2 +$ ...) yields the hypothesis value. For logistic regression $\theta^T\negthinspace x$ is used as the exponent in the logistic function to produce the hypothesis value:

\begin{equation} h\_\theta(x) = \dfrac{1}{1 + e^{-\theta^T\negthinspace x}} \end{equation} $e$ is the usual natural log constant $\approx 2.71828$.

$h\_\theta(x)$ is the probability that the sample $x$ is a member of class the classifier recognizes. Compute $h\_\theta(x)$ for each classifier and accept the verdict of the classifier that produces the largest probability value.

> **How exactly do you find the weight vector for logistic regression (using either gradient descent or newtons method, whichever is easier)?**

Gradient descent works the same way for logistic regression as it does for linear regression. You're still trying to minimize the cost function by iteratively nudging the weights to better values using partial derivatives of the cost function. The hypothesis function is different for logistic regression, but the way it is used in gradient descent is the same. Once you've written code to do gradient descent for linear regression, you should be able to just plug in a different hypothesis function and have it work for logistic regression.

Pseudocode for one iteration of gradient descent:

```
newtheta := theta;
learning_rate := 0.01;
for k := 1 to n
   sum := 0
   for i := 1 to m
      sum := sum + (hypothesis(x[i], theta) - y[i]) * x[i][k];
   end
   nudge := sum * learning_rate;
   newtheta[k] := newtheta[k] - nudge;
end
theta := newtheta;

```

**x** is a matrix containing your training data, one sample per row.

**y** is a vector containing the correct classification prediction for each sample, 1 if the sample is in the class, 0 otherwise.

**m** is the number of samples.

**n** is the number of features.

The idea is that you would repeat this process until you reach some minimum and acceptable cost (error) over the training set.
> 7 votes

---
Tags: machine-learning
---


title: Min/max height of B-tree

text:
# Question
Title: Min/max height of B-tree
I have a question asking for the minimum and maximum height $h$ of a B-Tree with 1000 elements under following conditions:

* each block can save 1 to 4 records,
* the number of internal nodes is between 3 and 5 and
* the root has between 3 and 5 children.

The solution is given as $4\leq h \leq7$. How this is reached?

# Answer
In the worst case you will store 1 record per node, so you will need 1000 nodes.

In the best case you will store 4 record per node, so you only need 1000/4 = 250 nodes.

In the worst case you will have 3 children per node, so your tree will only grow by multiples of 3 for each level. So we can say that $3^h \geq 1000$, where $h$ is the height. So $h=\lceil\log\_3 1000\rceil=7$

In the best case you will have 5 children per node, so your tree will be $h=\lceil\log\_5 250\rceil=4$
> 4 votes

---
Tags: data-structures, trees
---


# Question
Title: Recursion problem to see if string fits in given pattern
If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g\*a". A question mark can be replaced with one character and asterisk can be replaced with multiple characters. Other characters have to match. Help me with the asterisk part.

```
def fit_pattern(pattern,string):
    if string == pattern:
        return True
    if pattern[0] == "?" or string[0] == pattern[0]:
        return fit_pattern(pattern[1:], string[1:])
    return False

```

# Answer
Something like...

```
def fits(pattern, string):
    if len(pattern) == 0:
        return (len(string) == 0)

    if pattern[0] == "*":
        if len(string) == 0:
            return fits(pattern[1:], string)
        return (fits(pattern, string[1:]) or fits(pattern[1:], string))

    if len(string) == 0:
        return False

    if pattern[0] == "?":
        return fits(pattern[1:], string[1:])

    return ((pattern[0] == string[0]) and fits(pattern[1:], string[1:]))

```

Explanation:

1. An empty string for the pattern matches only the empty string.
2. A pattern starting with an asterisk matches the empty string only if the rest of the pattern matches the empty string (i.e., it's empty or consists of asterisks).
3. A pattern starting with an asterisk matches an arbitrary string if either (or both) of two conditions hold: either the pattern matches the rest of the string after the asterisk consumes the first character, or the rest of the pattern matches the string (in which case the asterisk consumes nothing).
4. Any non-empty pattern starting with something other than an asterisk cannot possibly match the empty string.
5. If the pattern starts with a question mark, the pattern matches a string if the rest of the pattern matches the string after the first character.
6. In all other cases (not asterisks or question marks), the pattern matches the string if the first characters match and if the rest of the pattern matches the rest of the string.

I suspect the part you're most interested in is the following insight: `*x` matches `ay` if and only if (`*x` matches `y` OR `x` matches `ay`).

Exercise: how would you change this code so that `*` has to match at least one character?
> 0 votes

---
Tags: algorithms, regular-expressions, recursion
---


# Question
Title: Isn't software needed from programs to run?
I am a student who has entered a game programming competition called FBLA at school, and I sent them an email because I had a few questions about how the competition is ran.

The main question I had, since I'm a Java programmer was in short: "Does the program need to be an executable, and if a java update/install is needed to run my program, will they install it?"

Their response was (quote): "The file does need to be a .exe and the entire program needs to be able to run independently on the judges’ machines. Installing JAVA then running your program is not the intent of this competition. I understand your concern as a JAVA programmer, but this competition is set specifically to this format so that all the programmers know, up front, what is expected."

I can understand the file needing to be an *Executable file*, but when they said, "Installing JAVA then running your program is not the intent of this competition." really angered me.

If I'm going to make an application in C++, doesn't it require a version of C++ Redistributable? What about DirectX, that's software needed for some C++ programs, isn't it? What about programming in C, and C#?

My argument to them is doesn't all programming languages have a necessity to some form of software in one way or another? Without it, wouldn't applications be very limited, or not run at all?

If someone could please help me settle this issue for installing Java on a machine being no different to making game applications in other languages, I would really appreciate it.

# Answer
> 1 votes
Languages like C and C++ can be compiled to include all libraries they use statically (as part of the executable). This means that the executable will be able to run by itself. Of course, even in this case the executable is supported by the operating system, but this is "for free".

You are right that practical applications normally use dynamically linked libraries and even external data files, but programs arising in programming competitions are usually more low-key and can stand on their own.

The judges have a very practical reason in requiring that the executable be self-sufficient, namely it makes it much easier for them to run it. Java environments are not standard, take up a lot of space, and are time-consuming to install. In principle (and perhaps in practice) you could compile your Java code to Java bytecode and thence to an actual executable, and if you link the appropriate runtime libraries statically, you would get a standalone executable.

---
Tags: programming-languages, computer-architecture, computer-games, java
---


# Question
Title: How exactly do you calculate the hidden layer gradients in the backpropagation algorithm?
I have been going through the description of the backpropagation algorithm found here. and I am having a bit of trouble getting my head around some of the linear algebra.

Say I have a final output layer $L$ consisting of two visible units, and layer $L-1$ consists of four hidden units. (this is just an example to illustrate my problem)

my understanding is that the weight matrix for this final layer ($w^L$) should be a 4 x 2 matrix.

the reference says to calculate the output error $\delta^{x,L}$ given by:

$\delta^{x,L} = \nabla\_a C\_x \odot \sigma'(z^{x,L})$

where:

$z^{x,L} = w^La^{x,L-1} + b^L$,

$a^{x,L} = \sigma(z^{x,L})$, and

$\odot$ is the hadamard product.

evaluating $\delta^{x,L}$ gives a 1 x 2 vector, as it should given there are two output units.

my problem is when calculating the hidden layer gradients (eg. $L-1$) given by:

$\delta^{x,L-1} = ((w^L)^T\delta^{x,L})\odot\sigma'(z^{x,L-1})$

now if $w^L$ is a 4x2 matrix and $\delta^{x,L}$ is a 1x2 vector then wouldnt $(w^L)^T\delta^{x,L}$ be a multiplication of a 2x4 matrix and a 1x2 matrix, which is impossible?

i feel like i have missed something vital in my understanding, but i cant work out what it is.

is it just as simple as making it $\delta^{x,L}(w^L)^T$? this would be a 1x2 matrix multiplied by a 2x4 matrix, which is perfectly legal. but the formula has it around the other way.

can anyone see where my understanding is flawed? any help would be greatly appreciated

# Answer
You've transposed the sizes of both $w^L$ and $\delta^{x,L}$. $w^L$ should be 2x4 and $\delta^{x,L}$ should be 2x1. $(w^L)^T$ is a 4x2 matrix that will be multipled by a 2x1 matrix yielding a 4x1 matrix suitable for the next step of backpropagation. In general for neural nets the activation units are represented as column vectors and the weights are matrices of dimension |L+1| x |L|, where L is the current layer and L+1 is the next layer (in the forward direction).
> 3 votes

---
Tags: machine-learning, neural-networks
---