# Question
Title: Hash size: Are prime numbers "near" powers of two a poor choice for the modulus?
Cormen et al.'s "Introduction to Algorithms" says the following about the division method hash function $h(k)=k \text{ mod } m$:

> A prime not too close to an exact power of 2 is often a good choice for $m$. For example, suppose we wish to allocate a hash table, with collisions resolved by chaining, to hold roughly $n=2000$ character strings, where a character has 8 bits. We don't mind examining an average of 3 elements in an unsuccesful search, so we allocate a table of size $m=701$. The number $701$ is chose because it is a prime near $2000/3$ but **not near any power of 2**.

The book, however, does not explain what it means by "near". Is $701$ preferrable over, say, $661$ because $661-512\<701-512$? I do not understand how this is relevant to the modulo function involved in the calculation of $h(k)$.

# Answer
> 2 votes
If a string of 8 bit bytes is interpreted as a large integer, and you calculate the value modulo $2^{24}-1$ then the first, fourth, seventh byte etc. are all hashed to the same value, which means the hash will not be well distributed.

# Answer
> 1 votes
This answer possibly explains why choosing M(table size) equal to a power of 2 should be avoided.

> Prime numbers that are too close to a power of 2 will provide the same kind of biasing as a power of 2 for the keys which differs by $+a$ or $-a$ if $2^k=a(modulo)M$.

In division method we simply use remainder modulo M: ***h(K) = K mod M***

In this case some values of M are obviously much better than others.

**Case 1:** If M is an even number h(K) will be even when K is even and odd when K is odd, and this will lead to a substantial bias in many files.

**Case 2:** It would be even worse to let M be a power of 2 (more generally the radix of the computer), since K mod M would then be simply the least significant digits of K (independent of the other digits).

**Case 3:** Similarly we can argue that M probably shouldn't be a multiple of 3: for if the keys are alphabetic, two keys that differ only by the permutation of letters, would then differ in numeric value by a multiple of 3. (This occurs because *$2^{2n}$ mod 3 = 1* and *$10^n$ mod 3 = 1*).

> **Case 4:** In general, we want to avoid values of M that divide $r^k+a$ or $r^k-a$, where k and a are small numbers and r is the radix of the alphabetic charecter set (usually $r=64, \ 256$ or $100$), since a remainder modulo such a value of M tends to be largely a simple superposition of key digits. Such considerations suggest that we choose M to be a prime number such that $r^k!=a(modulo)M$ or $r^k!=-a(modulo)M$ for small k & a.
>
> ***--Donald E. Knuth** (The art of Computer Programming Vol. 3)*

---
Tags: hash
---


# Question
Title: How to convert pixel relative focal lengths to mm.
Ive been playing around with the Intel Realsense R200 Camera. I am able to exact focal length in x and y i.e. fx and fy, but only "up to scale relative to pixel width and height, respectively"

At the moment I dont see any way of querying the pixel dimensions in mm from the API nor can I find them in the tech specs.

So my question is: How can I get the fx and fy in mm? One way I can think of is to take a picture of my checkerboard pattern and count the number of pixels and divide by the size in mm.

Is there a better/more elegant way? It seems kind of..imprecise.

Best, Marc

# Answer
There is only one focal length, $F$. It is the distance between the focal point and the image plane.

The numbers you have, are actually not lengths. They are calculated by $f\_x=F\cdot s\_x $ and $f\_y=F\cdot s\_y $ where $s\_x$ and $s\_y$ are the size of your image in pixels. To get the focal length in mm as you want, simply divide $f\_x$ with the width (in pixels) of your image.
> 2 votes

---
Tags: computer-vision
---


# Question
Title: Formally modelling and describing access rights
Is there a formal theory or framework described in text books that models access rights in a mathematical way. I would expect things similar to the following:

* We have data (objects).
* We have operations on these objects (CRUD, create, read, update delete)
* We have actors (users, principals)
* We might model access rights as triples like (user, operation, object) which describe which user can do what to which object.
* We have a potential hierarchy of objects: a folder has files, a file has meta data and rights may be inherited according to certain rules down the hierarchy.
* We have a hierarchy of actors too.
* Rights may be stored more efficiently by creating triples of (user set, operation set, object set) based on attributes of the objects and the users.

Apart from the pure theory I would expect to read about efficient implementation strategies, data structures etc.

EDIT on: Once access rights are modelled, I would like to read about how these are enforced in real code. Where and when must an operation of some data make the decision whether this is allowed in the given context or not. EDIT off

Further I would expect to see how this maps to real world access control systems in file shares, databases, web applications. Maybe I am just missing the right keywords for a search.

The one paper I found, http://www.sciencedirect.com/science/article/pii/S1877050916301764, is not exactly convincing.

# Answer
The Harrison-Ruzzo-Ullman model has this form. It has principals (e.g., users) and objects (e.g., files), and a matrix that indicates which types of access each principal has for each object. It also models how the sets of access rights can evolve over time. It has no notion of hierarchy for principals or objects built into the model, but you could of course regard the set of principals and objects as hierarchical in the way you want -- that's compatible with the HRU model.

The HRU model concerns itself only with semantics: with who has access to what. It is not concerned with efficiency.

You might also enjoy digging up a textbook that covers this. The catchphrase you want is the foundations of computer security". For instance, you might find Matt Bishop's book *Computer Security: Art and Science* very relevant.
> 1 votes

---
Tags: security, access-control
---


# Question
Title: Determine deadline for periodic task that enter ready queue in RTOS
I am currently trying to optimise the scheduler of FreeRTOS and in general Real-Time Operating Systems as a Project.

In FreeRTOS, and I suspect other RTOS as well, we don't specify the deadline for the tasks, not to mention the tasks would mostly be periodic.

How can we, if possible, generate the deadline for them?

Maybe a constant added to the time task reached the ready queue? Where the constant depends on the priority.

How should I go about it? Looking for suggestions...

In short, how can we implement something like Earliest Deadline First?

I am actually trying to implement Ant Colony Optimisation.

Edit: In FreeRTOS the API of OS doesn't need deadline to create Task, only Priority can be set.

# Answer
You can't generate a deadline from nothing. That doesn't make sense.

Some tasks must be completed by a certain time, or they are useless. Only the programmer who writes the task knows whether this is the case, and if so, knows when they have to be completed by. That's not something that the OS can infer, because it depends on what the task is doing and why.

For instance, a task that adjust the jet engine's power level in response to pilot commands might need to respond rapidly to make sure that safety requirements are met. However, a task that displays frames of a movie on the passenger's entertainment system is probably less critical; if the next frame of video doesn't get displayed or is delayed, there's no great harm done. The OS cannot distinguish those two cases. Only the software developer can.

Therefore, in a real-time OS that tries to meet task deadlines, the deadlines come from the software developer.

For periodic tasks, we might not have a fixed deadline, but we might have requirements on how often they run (e.g., must occur at least two times per second).
> 1 votes

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


# Question
Title: Computer Organization and Assembly Language Programming
Why do we need to learn MIPS Assembly language before learning computer organization? What are the implications of learning it first?

As a computer scientist, why do we need to learn this one and where will these topics will become handy?

with references:

-Computer Organization and Design by Patterson and Hennessy

-Introduction to Digital Logic Design by John Hayes

# Answer
Learning assembly language will be helpful for you in understanding computer architecture, because the CPU is designed to run the instructions that are part of its assembly language. So, to understand what the CPU is doing and why it was designed that way, you need to know what operations it is designed to support.
> 1 votes

---
Tags: computer-architecture, mips
---


# Question
Title: Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria
Given a collection of sets $S\_i$ of disjoint subsets $sub\_i$ of a set $X$, find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in each of $S\_i$, i.e., for

$S\_1$ = $\\{sub\_11,sub\_12,sub\_13\\}$, where $sub\_11$, $sub\_12$, $sub\_13$ are disjoint,

$S\_2$ = $\\{sub\_21,sub\_22\\}$, where $sub\_21$, $sub\_22$ are disjoint

Then find $A$ = $\\{asub1,asub2,asub3\\}$, where $asub1$, $asub2$ are disjoint

and

$asub1$ can be a subset of only one of $sub\_11$ or $sub\_12$ or $sub\_13$ but not more than one of them. Same goes for $asub2$ and $asub3$.

Similarly

$asub1$ can be a subset of only of either $sub\_21$ or $sub\_22$ or but not both of them. Same goes for $asub2$ and $asub3$.

More formally,

$\forall sub\_i \in S\_i,$ and given a subset $asub \in A,$

If $Asub=\\{sub\_i\mid asub\subseteq sub\_i\\}$

$then$ $|Asub|=1$

$Example 1:$

$X = \\{e1,e2,e3,e4,e5\\}$

$S\_1 = \\{\\{e1,e2\\},\\{e3,e4\\},\\{e5\\}\\}$

$S\_2 = \\{\\{e1\\},\\{e2,e3,e4\\},\\{e5\\}\\}$

$S\_3 = \\{\\{e1,e2,e3,e4\\},\\{e5\\}\\}$

$A= \\{\\{e1\\},\\{e2\\},\\{e3,e4\\},\\{e5\\}\\}$

$Example 2:$

$X = \\{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12\\}$ $S\_1 = \\{\\{e1,e2,e11,e12\\},\\{e3,e4,e5,e6\\},\\{e7,e8,e9,e10\\}\\}$ $S\_2 = \\{\\{e1,e2,e3\\},\\{e4,e5,e6,e7,e8\\},\\{e9,e10,e11\\},\\{e12\\}\\}$

$A= \\{\\{e1,e2\\},\\{e3\\},\\{e4,e5,e6\\},\\{e7,e8\\},\\{e9,e10\\},\\{e11\\},\\{e12\\}\\}$

Preferably the algorithm for finding $A$ should take optimal time.

P.S. Forgive me if the mathematical description of the problem is not formal enough or if there are mistakes in it, I am not a mathematician.

# Answer
> 1 votes
Without loss of generality, each asub$i$ can be taken to have exactly one element (size 1). (If there is any solution, then there is a solution where all asub$i$'s are of size 1.)

Now it's easy to iterate over all sets of size 1 and determine which are valid for asub$i$. Let $A$ be the collection of all such sets. There is your solution. As a bonus, I even gave you a solution where $A$ is as large as possible.

The running time is polynomial (in fact, quadratic), so this should be an efficient algorithm.

---
Tags: combinatorics, sets, set-cover, partitions
---


# Question
Title: Longest path among subset of given points
I am looking for an efficient algorithm to solve the following problem:

Given $n$ points in 2D Cartesian space $p\_1,\dots,p\_n \in \mathbb{R}^2$ and an integer $m$, we want to find $s\_1,\dots,s\_m$ such that $1 \le s\_1 \< s\_2 \< \cdots \< s\_m \le n$ and that maximizes

$$\sum\_{i=1}^{m} \\|p\_{s\_i} - p\_{s\_{i+1}}\\|\_2,$$

where $\\|p-q\\|\_2$ represents the $L\_2$ distance between two points. In other words, we want to find a subsequence of the points $p\_1,\dots,p\_n$ such that the distance of following that path is maximized.

Is there an efficient algorithm for this problem?

In my application $m$ is at least 3 orders of magnitude smaller than $n$ and neighboring points $p\_i,p\_{i+1}$ are close to each other, which makes the search space structured. I have tried simulated annealing with and without an adaptive neighbourhood and get decent results, but I want to know if there is a optimal algorithm. Does anyone know other algorithms and ideally their complexity?

# Answer
This can be solved exactly with dynamic programming. The running time will be $O(n^2m)$. It finds the exact optimal sequence, not just an approximation.

Let $A\[t,u\]$ denote the longest path $p\_{s\_1},\dots,p\_{s\_t}$ such that $s\_t=u$. In other words, it is the maximum possible value of $\\|p\_{s\_1} - p\_{s\_2}\\|\_2 + \dots + \\|p\_{s\_{t-1}} - p\_{s\_t}\\|\_2$ such that $1 \le s\_1 \< \cdots \< s\_t = u$.

Notice that we have a recursive equation that defines $A\[\cdot,\cdot\]$. In particular,

$$A\[t,u\] = \max \\{ A\[t-1,v\] + \\|p\_v - p\_u\\|\_2 : 1 \le v \< u\\}.$$

Thus, we can fill in the values of $A\[t,u\]$ incrementally, in order of increasing value of $t$. Each step requires $O(n)$ time, and there are $nm$ entries to fill in, so the total running time is $O(n^2m)$.

In practice the running time might often be something closer to $O(nm)$ if you terminate the search for $v$ early. In the recurrence above you might often be able to prove that if $v$ is much smaller than $u$ the maximum can't be achieved, so you could examine at values of $v$ in decreasing order and stop the iteration early once you know there is no improvement possible with a smaller value of $v$.
> 1 votes

# Answer
\[Cannot post a comment with my karma yet, so this has to be an answer.\]

If you understand german (or the translation thereof) you might find use in the following link. There are multiple approaches with corresponding explanations, complexity estimations as well as C-code available.

In English, and also somehow related to the answer given by @D.W., consider the seventh post in this thread.

Obviously, none of the ideas above are mine, so I do not intend to take credit for it. May mods convert it to a comment.
> 0 votes

---
Tags: algorithms, optimization, time-complexity, computational-geometry
---


# Question
Title: What happens during the DFA reversal construction if the initial state is final?
The steps in reversal of DFA are :-

1. Make final state as initial state. If there are more than 1 final state, then make a new start state with epsilon transitions to these states.
2. Change all initial states to final states
3. Reverse the direction of edges.

Now what if I have a state which is both initial and final ? Will it be initial or final state in the reversed dfa?

# Answer
> 2 votes
Yes. It will be both initial and final in the reversed automaton.

(Separately: If you want the reversed automaton to be a DFA, you may have to be a bit careful about your construction for reversing a DFA, as DFAs are not allowed to contain epsilon transitions.)

---
Tags: automata, finite-automata, closure-properties
---


title: $UP=BPP$ implies $UP=RP$?

text:
# Question
Title: $UP=BPP$ implies $UP=RP$?
https://cseweb.ucsd.edu/~mihir/cse200/ss6.pdf shows $NP$ in $BPP$ implies $NP$ in $RP$ by showing $SAT$ is in $RP$ if $NP$ is in $BPP$ and since $SAT$ is $NP$ complete we have $NP$ is in $RP$.

However since $UP$ does not have a complete problem and so can we still show $UP$ in $BPP$ implies $UP$ is in $RP$?

# Answer
Suppose $L\in \mathsf{UP}$, and let $M(x,y)$ be a polynomial deterministic Turing machine such that:

1. $x\in L \Rightarrow \exists !y : M(x,y)$
2. $x\notin L\Rightarrow \forall y : \neg M(x,y)$

Consider the language $L'$ consisting of words in $L$ along with a prefix of a witness:

$L'=\left\\{(x,w)\big|\exists w' : M(x,ww')\right\\}$

Clearly $L'\in\mathsf{UP}$. Given an oracle for $L'$, one can find the witness for words in $L$ in polynomial time. If $\mathsf{UP\subseteq BPP}$, then $L'\in\mathsf{BPP}$, so you don't actually have an oracle for $L'$, but you have an oracle which is right with high probability.

Now, given $x$, execute the machine for finding a witness for $x$ with an $L'$ oracle, only that now you replace oracle calls with executions of the $\mathsf{BPP}$ machine (after some amplification, I leave the details for you). If the execution resulted in a valid witness $w$ for $x$, i.e. $M(x,w)$ outputs $1$, then output "yes", otherwise output "no". Clearly this solution can only be wrong for positive instances, which makes it a good candidate for an RP machine for $L$. I leave it to you to choose the right success probability to make everything work.

Essentially, the above solution uses the property of self reducibility, and in that sense the same proof as that for $SAT$, or any other self reducible problem in $\mathsf{NP}$.
> 0 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Applying a 1x1 convolution on an existing layer
I am looking at the following github. In this, `layer3` has a shape of `(1, 20, 72, 256)` and I interpret this is as a single layer having 20 input nodes and mapping to 72 output nodes and there are $256$ filters, so the depth is $256$. Then, after applying a `1x1` convolution to this, the new shape becomes `(1, 20, 72, 2)`. I don't quite understand how this comes about.

Is it because there are only 2 classes in the model, so it only needs a depth of two at all points? I keep stumbling over the code and can't get anywhere.

# Answer
> 2 votes
A $1 \times 1$ convolution is a modern technique for dimensionality reduction, originally proposed in the Inception paper by Google team.

Suppose the layer outputs a $(N,H,W,F)$ tensor, where $F$ is the number of feature maps. Then the number of floating-point operations that the subsequent convolutional layer is going to compute is $O(N \cdot H \cdot W \cdot F)$, most importantly it's proportional to $F$. Likewise the number of parameters is also proportional to $F$ and the filter size.

The problem is that deep convolutional networks tend to increase the number filters exponentially, so $F$ can be really large, which makes training deep networks pretty expensive.

The idea is to reduce the size of the tensor via clever application of the convolution to $(N,H,W,F')$, where $F'$ is much smaller than $F$. If the network learns to compress the information of $F$ feature maps into $F'$ feature maps, the whole network will become much lighter both in terms of memory and computational complexity, yet potentially deeper. As it turns out, this trick works magically, so that it's used all over the place before expensive convolutional layers:

> One big problem with the above modules, at least in this naive form, is that even a modest number of 5x5 convolutions can be prohibitively expensive on top of a convolutional layer with a large number of filters.
>
> This leads to the second idea of the proposed architecture: judiciously applying dimension reductions and projections wherever the computational requirements would increase too much otherwise. This is based on the success of embeddings: even low dimensional embeddings might contain a lot of information about a relatively large image patch...1x1 convolutions are used to compute reductions before the expensive 3x3 and 5x5 convolutions. Besides being used as reductions, they also include the use of rectified linear activation which makes them dual-purpose.

The trick itself is pretty simple: apply $F'$ convolutions with $1 \times 1$ kernel size. This doesn't change spatial dimensions of the image, but only reduces the depth.

This is exactly what happened in your case: the depth was reduced from `256` to `2`, which is a 128x boost for the subsequent layer.

---
Tags: neural-networks
---


# Question
Title: How center the eyes of human face at specific pixels?
I am facing a problem with processing some frontal facial images.

I need to adjust the centers of the eyes (irises) to be at certain specific pixels in the image. In other words, i need to transform the image until the centers of the eyes are at specific pixels.

Can anyone help me with this problem, an algorithm, technique, ...etc. that might solve this problem ?

Thanks,

# Answer
> 3 votes
Assuming you can find the centers of the eyes...

1. **Rotate** \- Find the difference of the angle between the actual eyes and your desired angle. Rotate image accordingly.
2. **Scale** \- Find the distance between eyes. Scale according to the desired distance.
3. **Translate** \- Move the image so that one eye lines up. If you've rotated and scaled properly, both should now be in the desired spot.

# Answer
> 2 votes
You can apply homographic transformation to the image, the homography matrix can be estimated using the known positions of the points.

You can use OpenCV for quick implementation.

You can read this paper for your further reference: http://www.robots.ox.ac.uk/~vgg/research/affine/det\_eval\_files/vibes\_ijcv2004.pdf

# Answer
> 0 votes
I found this project very useful.

http://thume.ca/projects/2012/11/04/simple-accurate-eye-center-tracking-in-opencv/

Edit: The project uses image gradients to localize the eye center.

Essentially it uses a heuristic function which assumes that the eye is a circle and thus uses this geometric prior knowledge to estimate the center of the circle, which happens to coincide with the pupuil.

The paper which this is based on can be found here http://www.inb.uni-luebeck.de/publikationen/pdfs/TiBa11b.pdf

---
Tags: image-processing, computer-vision
---


# Question
Title: Understanding the Bitcoin White Paper's Notion of "Signing" and "Verifying"
Consider from the Bitcoin white paper a graphic that includes dotted arrows, labeled "sign" and "verify":

>

What does it mean to "sign" and "verify", as outlined in this paper? Are the terms "private key" and "public key" used in the same way that they are in the RSA encryption algorithm?

# Answer
Yes. It means "sign" and "verify" exactly as in a public key system such as RSA. Bitcoin doesn't introduce new cryptographic primitives or notions; it simply combines existing ones in a novel way. So you would simply use a public key system such as RSA to implement those operations in Bitcoin. The actual algorithm used is ECDSA, but this predates Bitcoin by quite a while. Arguably the "break-through" in Bitcoin is a clever mix of existing cryptographic techniques and aligning incentives.

Another clever aspect is that Bitcoin solves a different problem than what cryptographers traditionally viewed as "digital cash". That is, Bitcoin doesn't meet all the desiderata that one would hope "digital cash" would have, but clearly it's a pretty effective solution to the colloquial meaning of "digital cash".
> 1 votes

---
Tags: cryptography
---


# Question
Title: Neural Network: Why can't we calculate derivatives during forward prop itself?
I have been studying Andrew Ng's Coursera course about Deep Learning. In that he mentions that we calculate the activation functions during the forward pass, and the derivatives $\dfrac{dL}{dz} \ $, $\dfrac{dL}{dw} \ $, and $\dfrac{dL}{db} \ $ during the backward pass.

Consider a single neural node

Here, $x\_{1} \ ,\ x\_{2} \ ,\ ...\ ,\ x\_{n}$ are our inputs to the node

$b$ is the bias

$w\_{1} ,\ w\_{2} ,\ ...\ ,\ w\_{n}$ are the weights associated with the inputs

$\hat{y}$ or $a$ is our activation function where $a\ =\ \sigma ( z) \ =\frac{1}{1\ +\ e^{-z}} \ $

$z\ =\ w\_{1} x\_{1} +w\_{2} x\_{2} +\dots +w\_{n} x\_{n} +\ b$

The term $L\ ( a,y) \ =\ -\\{\ y\log a\ +\ ( 1-y)\log( 1-a) \ \\}$ is our loss function

The way Andrew calculates the derivatives is as follows:

$ \begin{gathered} \dfrac{dL}{dw} \ =\ \dfrac{dL}{dz} \cdot \dfrac{dz}{dw}\\ \\ \dfrac{dL}{dz} \ =\ \dfrac{dL}{da} \cdot \dfrac{da}{dz}\\ \end{gathered}$

We back-propagate to calculate

$\dfrac{dL}{da}\\\$ (1-step back)

$\dfrac{da}{dz}\\\$ and $\dfrac{dL}{dz} \ =\ \dfrac{dL}{da} \cdot \dfrac{da}{dz}\\\$ (2-step back)

$\dfrac{dz}{dw}\\\$ and $\dfrac{dL}{dw} \ =\ \dfrac{dL}{dz} \cdot \dfrac{dz}{dw}\\\$ (3-step back)

However, my question is, why can't we calculate these derivatives during the forward pass itself? Like so,

$\dfrac{dL}{dw} \ =\ \dfrac{dL}{da} \cdot \dfrac{da}{dz} \cdot \dfrac{dz}{dw}\\\$

Step 1: Calculate $z\\\$ as well as $\dfrac{dz}{dw}\\\$

Step 2: Calculate $a\\\$ as well as $\dfrac{da}{dz}\\\$ and $\dfrac{da}{dw} \ =\ \dfrac{da}{dz} \cdot \dfrac{dz}{dw}\\\$

Step 3: Calculate $L\\\$ as well as $\dfrac{dL}{da}\\\$ and $\dfrac{dL}{dw} \ =\ \dfrac{dL}{da} \cdot \dfrac{da}{dw}\\\$

Is there any reason why we take the back-prop approach, and not calculate both sets of functions together during forward prop?

**EDIT**: For a network with $n$ layers, we can calculate the weight derivative for a layer $j$, as:

$ \begin{gathered} \dfrac{dL}{dw^{\[ j\]}} =\dfrac{dL}{da^{\[ n\]}} \cdot \dfrac{da^{\[ n\]}}{dz^{\[ n\]}} \cdot \dfrac{dz^{\[ n\]}}{da^{\[ n-1\]}} \dots \dfrac{dz^{\[ j+1\]}}{da^{\[ j\]}} \cdot \underbrace{\dfrac{da^{\[ j\]}}{dz^{\[ j\]}} \cdot \dfrac{dz^{\[ j\]}}{dw^{\[ j\]}}}\_{combine\ the\ two}\\ \\ =\dfrac{dL}{da^{\[ n\]}} \cdot \dfrac{da^{\[ n\]}}{dz^{\[ n\]}} \cdot \dfrac{dz^{\[ n\]}}{da^{\[ n-1\]}} \dots \underbrace{\dfrac{dz^{\[ j+1\]}}{da^{\[ j\]}} \cdot \dfrac{da^{\[ j\]}}{dw^{\[ j\]}}}\_{combine\ the\ two}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ \\ =\underbrace{\dfrac{dL}{da^{\[ n\]}} \cdot \dfrac{da^{\[ n\]}}{dw^{\[ j\]}}}\\ \end{gathered}$

As can be seen, any layer's derivative can be calculated without the need to backtrack

**Edit 2**: Let's take a 2 layer network

$a^{\[ 0\]} =\left\[\begin{smallmatrix} x\_{1}\\ x\_{2}\\ \vdots \\ x\_{n} \end{smallmatrix}\right\]$

$a^{\[ 1\]} =\left\[\begin{smallmatrix} a^{\[ 1\]}\_{1}\\ a^{\[ 1\]}\_{2}\\ \vdots \\ a^{\[ 1\]}\_{m} \end{smallmatrix}\right\]$

$w^{\[ 1\]} =\left\[\begin{smallmatrix} n\ weights\ for\ layer\ 1\ node\ 1\\ n\ weights\ for\ layer\ 1\ node\ 2\\ \vdots \\ n\ weights\ for\ layer\ 1\ node\ m \end{smallmatrix}\right\] =\left\[\begin{smallmatrix} w^{\[ 1\]}\_{1}\\ w^{\[ 1\]}\_{2}\\ \vdots \\ w^{\[ 1\]}\_{m} \end{smallmatrix}\right\] =\left\[\begin{smallmatrix} w^{\[ 1\]}\_{1( 1)} & w^{\[ 1\]}\_{1( 2)} & \dots & w^{\[ 1\]}\_{1( n)}\\ w^{\[ 1\]}\_{2( 1)} & w^{\[ 1\]}\_{2( 2)} & \dots & w^{\[ 1\]}\_{2( n)}\\ \vdots & \vdots & \dots & \vdots \\ w^{\[ 1\]}\_{m( 1)} & w^{\[ 1\]}\_{m( 2)} & \dots & w^{\[ 1\]}\_{m( n)} \end{smallmatrix}\right\]$

**Step 1**: For the first layer: $z^{\[ 1\]} \ =\ w^{\[ 1\] T} a^{\[ 0\]} =\left\[\begin{smallmatrix} z^{\[ 1\]}\_{1}\\ z^{\[ 1\]}\_{2}\\ \vdots \\ z^{\[ 1\]}\_{m} \end{smallmatrix}\right\]$

$a^{\[ 1\]} =\sigma \left( z^{\[ 1\]}\right) =\left\[\begin{smallmatrix} \sigma \left( z^{\[ 1\]}\_{1}\right)\\ \sigma \left( z^{\[ 1\]}\_{2}\right)\\ \vdots \\ \sigma \left( z^{\[ 1\]}\_{m}\right) \end{smallmatrix}\right\]$

$\dfrac{\partial a^{\[ 1\]}}{\partial w^{\[ 1\]}} \ =\left\[\begin{smallmatrix} \dfrac{\partial a}{\partial w} \ for\ layer\ 1\ node\ 1\ \\ \dfrac{\partial a}{\partial w} \ for\ layer\ 1\ node\ 2\\ \vdots \\ \dfrac{\partial a}{\partial w} \ for\ layer\ 1\ node\ m \end{smallmatrix}\right\] =\left\[\begin{smallmatrix} \dfrac{\partial a^{\[ 1\]}\_{1}}{\partial w^{\[ 1\]}\_{1}}\\ \dfrac{\partial a^{\[ 1\]}\_{2}}{\partial w^{\[ 1\]}\_{2}}\\ \vdots \\ \dfrac{\partial a^{\[ 1\]}\_{m}}{\partial w^{\[ 1\]}\_{m}} \end{smallmatrix}\right\]$

$=\left\[\begin{smallmatrix} \dfrac{\partial a^{\[ 1\]}\_{1}}{\partial w^{\[ 1\]}\_{1( 1)}} & \dfrac{\partial a^{\[ 1\]}\_{1}}{\partial w^{\[ 1\]}\_{1( 2)}} & \dots & \dfrac{\partial a^{\[ 1\]}\_{1}}{\partial w^{\[ 1\]}\_{1( 2)}}\\ \dfrac{\partial a^{\[ 1\]}\_{2}}{\partial w^{\[ 1\]}\_{2( 1)}} & \dfrac{\partial a^{\[ 1\]}\_{2}}{\partial w^{\[ 1\]}\_{2( 2)}} & \dots & \dfrac{\partial a^{\[ 1\]}\_{2}}{\partial w^{\[ 1\]}\_{2( n)}}\\ \vdots & \vdots & \dots & \vdots \\ \dfrac{\partial a^{\[ 1\]}\_{m}}{\partial w^{\[ 1\]}\_{m( 1)}} & \dfrac{\partial a^{\[ 1\]}\_{m}}{\partial w^{\[ 1\]}\_{m( 2)}} & \dots & \dfrac{\partial a^{\[ 1\]}\_{m}}{\partial w^{\[ 1\]}\_{m( n)}} \end{smallmatrix}\right\] =\left\[\begin{smallmatrix} a^{\[ 1\]}\_{1}\left( 1-a^{\[ 1\]}\_{1}\right) \ x\_{1} & a^{\[ 1\]}\_{1}\left( 1-a^{\[ 1\]}\_{1}\right) x\_{2} & \dots & a^{\[ 1\]}\_{1}\left( 1-a^{\[ 1\]}\_{1}\right) x\_{n}\\ a^{\[ 1\]}\_{2}\left( 1-a^{\[ 1\]}\_{2}\right) x\_{1} & a^{\[ 1\]}\_{2}\left( 1-a^{\[ 1\]}\_{2}\right) x\_{2} & \dots & a^{\[ 1\]}\_{2}\left( 1-a^{\[ 1\]}\_{2}\right) x\_{n}\\ \vdots & \vdots & \dots & \vdots \\ a^{\[ 1\]}\_{m}\left( 1-a^{\[ 1\]}\_{m}\right) x\_{1} & a^{\[ 1\]}\_{m}\left( 1-a^{\[ 1\]}\_{m}\right) x\_{2} & \dots & a^{\[ 1\]}\_{m}\left( 1-a^{\[ 1\]}\_{m}\right) x\_{n} \end{smallmatrix}\right\]$

**Step 2**: Moving to the second layer. All the derivatives from first layer get passed on to the second layer, and using them we calculate:

$\dfrac{\partial a^{\[ 2\]}}{\partial w^{\[ 1\]}} =\dfrac{\partial a^{\[ 2\]}}{\partial z^{\[ 2\]}} \cdot \dfrac{\partial z^{\[ 2\]}}{\partial a^{\[ 1\]}} \cdot \dfrac{\partial a^{\[ 1\]}}{\partial w^{\[ 1\]}} =a^{\[ 2\]}\left( 1-a^{\[ 2\]}\right) \cdot w^{\[ 2\]} .\dfrac{\partial a^{\[ 1\]}}{\partial w^{\[ 1\]}}$

$\dfrac{\partial L}{\partial w^{\[ 1\]}} =\dfrac{\partial L}{\partial a^{\[ 2\]}} \cdot \dfrac{\partial a^{\[ 2\]}}{\partial w^{\[ 1\]}}$

Image credits: https://www.mathcha.io

# Answer
You described the simplest case of the neural network, where the center neuron has only one output $a$, which is connected to the final loss function. In general, there can be several outputs and the total error signal coming to this node equals the sum over all output connections. Plus the error messages across these connections are different. And the subsequent nodes can have multiple outputs as well -- in general, it's impossible to tell what the result sum will be until the forward pass reaches the loss function.

Here's a picture for two or more output connections:

... or to make it even more complicated...

That's why you can't just multiply $\frac{da}{dz} \cdot \frac{dz}{dw}$, because the total error signal $\delta$ may not be $\frac{da}{dz}$ or something multiplied by $\frac{da}{dz}$. What is known for sure is the local gradient $\frac{dz}{dw}$. But in order to get $\delta$, all of the later nodes must be processed in the reverse order.

Credit: the pictures are from CS224n class by Stanford.
> 6 votes

---
Tags: neural-networks, backtracking
---


# Question
Title: The meaning of 'Pool' in Computer Science
While reading about `SIMD` on Wikipedia, I noticed the use of the technical term `Pool` in the figure below:

I didn't know what it means; so after searching for it, I found only this article. Yet the definition wasn't very clear to me:

> In computer science, a pool is a set of resources that are kept ready to use, rather than acquired on use and released afterwards. In this context, resources can refer to system resources such as file handles, which are external to a process, or internal resources such as objects

This is not the first time since I have seen the term - I found it on other CS-related materials in the past as well.

Does anyone have any idea about the meaning of 'Pool' in CS? or can provide any reference?

# Answer
> 5 votes
A ***pool*** is basically some grouping. It's kinda vague.

In that figure, the **"*data pool*"** is just some set of data while the **"*instruction pool*"** is just some set of instructions. The figure means to show that a single instruction and multiple data go into the vector unit at a time, and then that single instruction is applied to each of the multiple data independently.

---

### On the "*pooling*" design strategy

I clicked the link to "Pool (computer science)", Wikipedia. That article's worded a bit confusingly because it's talking about a design strategy called "*pooling*" rather than discussing the term "*pool*" itself.

*Pooling* is when a resource is collected up into a pool for some reason. Because it's such a vague term, it can apply in a lot of different situations, so it's hard to give a more specific description without overstating it.

But to give a common example, there's ***thread pooling*** in which a bunch of threads are kept alive-and-waiting to do jobs. This pattern's often useful when you might have a bunch of little jobs that you want to run on different CPU cores. Then, whenever you want to run a job, you pick an available thread from the thread pool and have it run the job.

In principle, you don't actually need a thread pool; you could instead create a new thread each time you want to run a new job. The problem's that threads can be expensive to create and dismiss, so if you're running a bunch of little jobs, it's often highly inefficient to keep creating/releasing threads.

That said, "*pooling*" is unrelated to what the SIMD diagram was referring to as a "*data pool*" and "*instruction pool*". In that diagram, they just meant that they had a bunch of things data and instructions to use on them, which they vaguely referred to as existing in pools.

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Seek to infer "correct" route from sequence of stops
Let us consider school buses. Let a 'Bus Route' be a sequence of bus stops travelled by a single school bus (day after day). Let a 'Bus Stop' be a combination of Latitude (Lat), Longitude (Lon) and Time-of-Day (ToD). That is, a bus may stop at the same Lat/Lon to pick up kids in the morning and again in the afternoon to drop them off. Furthermore, a bus may stop at a certain Lat/Lon at 7am to pick up high school kids, drop them at school, and then visit the same Lat/Lon at 7:30am to pick up middle school kids, and again at 8am to pick up elementary school kids.

Suppose that a bus sends its Lat/Lon/ToD every time it activates its stop-arm (which it does when it stops to let kids on/off the bus). Suppose we have the Lat/Lon/ToD information for a particular bus for 20 consecutive days.

In a perfect world the bus would make every stop at approximately the same time every day. In the imperfect world in which we live these things happen:

When there are no kids waiting at a bus stop in the morning the driver does not stop (so no Lat/Lon/Tod get sent). On any given day there may or may not be kids at any given bus stop.

When no kid are waiting to get off the bus a given stop the bus will not stop (so no Lat/Lon/Tod gets sent).

So, if there are "in fact" 30 stops, on some days the bus will make 30 stops, on other days it may make 20 stops, etc.

Let's assume that algorithms are already in place to analyze the Lat/Lon/ToD tuples for the 20 days worth of data and correctly identify a set of Bus Stops.

Placing the Bus Stops into the correct order would be a simple matter except that:

On some days the bus may visit stops in one order and some days in a different order. So, if Bus Stops are labelled with letters, on one day the path might be: A C D F H I J L N

and on the next day the order might be:

A B C D H F J L M N

(Notice there is a sequence "D F H" in the first and "D H F" in the second) This can happen for several reason, including:

a) different drivers have different ideas about what is the best route. b) the driver made a mistake, missed a stop, and has to go back.

ASSUME: there is nobody to ask, "What is the correct route (sequence of stops)?"

PROBLEM: using only the collected data, how can we construct the sequence "most likely" to be correct?

To be clear, this is *not* an optimization problem; I do not seed to find the "best" route. Rather, if, for example, the bus made exactly the same sequence of stops on 19 of 20 days and on the one odd day the order of two stops was reversed (compared to the other 19) then the "correct" route would be the sequence traveled on the 19 days. What I seek to do is to infer what is most likely the intended route by analyzing when and where the bus actually stops given that drivers skip some stops on some days and sometimes visit some days in different sequence on different days

Thanks for any help you can offer.

Regards, Matt

# Answer
> To be clear, this is not an optimization problem; I do not seed to find the "best" route.

Actually this is an optimization problem! Just instead of optimizing for shortest length or fastest time, you're optimizing for highest likelihood:

> What I seek to do is to infer what is most likely the intended route \[...\]

Now you just have to figure out your model for likelihood.

For example, say that the bus drives$$ \left\[\mathrm{A}\right\]{\rightarrow}\left\[\mathrm{B}\right\]{\rightarrow}\left\[\mathrm{C}\right\] $$half the time, then$$ \left\[\mathrm{A}\right\]{\rightarrow}\left\[\mathrm{C}\right\]{\rightarrow}\left\[\mathrm{B}\right\] $$the other half of the time. But, it tends to do the first route on odd-numbered days, unless it's raining. Except, the driver "*Bob*" reverses this pattern, whereas "*Suzzy*" always does the first one and "*Atomic Robot #7*" always does the second one. What do you infer from that?

Math has no opinion on this topic. For example, if you choose to believe that whatever "*Bob*" does is always correct, even if every other driver disagrees with him, that's your belief; math doesn't object.

So, what you need to do is construct a model for assessing how likely you believe a particular solution is given a set of data, then optimize for likelihood given the data.
> 1 votes

---
Tags: algorithms, graphs, routing
---


title: Discrepancy between heads and tails

text:
# Question
Title: Discrepancy between heads and tails
Consider a sequence of $n$ flips of an unbiased coin. Let $H\_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=\text{max}\_i H\_i$. Show that $E\[H\_i\]=\Theta ( \sqrt{i} )$ and $E\[H\]=\Theta( \sqrt{n} )$.

This problem appears in the first chapter of \`Randomized algorithms' by Raghavan and Motwani, so perhaps there is an elementary proof of the above statement. I'm unable to solve it, so I would appreciate any help.

# Answer
> 9 votes
Your coin flips form a one-dimensional random walk $X\_0,X\_1,\ldots$ starting at $X\_0 = 0$, with $X\_{i+1} = X\_i \pm 1$, each of the options with probability $1/2$. Now $H\_i = |X\_i|$ and so $H\_i^2 = X\_i^2$. It is easy to calculate $E\[X\_i^2\] = i$ (this is just the variance), and so $E\[H\_i\] \leq \sqrt{E\[H\_i^2\]} = \sqrt{i}$ from convexity. We also know that $X\_i$ is distributed roughly normal with zero mean and variance $i$, and so you can calculate $E\[H\_i\] \approx \sqrt{(2/\pi)i}$.

As for $E\[\max\_{i \leq n} H\_i\]$, we have the law of the iterated logarithm, which (perhaps) leads us to expect something slightly larger than $\sqrt{n}$. If you are good with an upper bound of $\tilde{O}(\sqrt{n})$, you can use a large deviation bound for each $X\_i$ and then the union bound, though that ignores the fact that the $X\_i$ are related.

Edit: As it happens, $\Pr\[\max\_{i \leq n} X\_i = k\] = \Pr\[X\_n = k\] + \Pr\[X\_n = k+1\]$ due to the reflection principle, see this question. So $$ \begin{align\*} E\[\max\_{i \leq n} X\_i\] &= \sum\_{k \geq 0} k(\Pr\[X\_n = k\] + \Pr\[X\_n = k+1\]) \\ &= \sum\_{k \geq 1} (2k-1) \Pr\[X\_n = k\] \\ &= \sum\_{k \geq 1} 2k \Pr\[X\_n = k\] - \frac{1}{2} + \frac{1}{2}\Pr\[X\_n = 0\] \\ &= E\[H\_n\] + \Theta(1), \end{align\*} $$ since $\Pr\[H\_n = k\] = \Pr\[X\_n = k\] + \Pr\[X\_n = -k\] = 2\Pr\[X\_n = k\]$. Now $$ \frac{\max\_{i \leq n} X\_i + \max\_{i \leq n} (-X\_i)}{2} \leq \max\_{i \leq n} H\_i \leq \max\_{i \leq n} X\_i + \max\_{i \leq n} (-X\_i), $$ and therefore $E\[\max\_{i \leq n} H\_i\] \leq 2E\[H\_n\] + \Theta(1) = O(\sqrt{n})$. The other direction is similar.

# Answer
> 2 votes
You can use the half-normal distribution to prove the answer.

The half-normal distribution states that if $X$ is a normal distribution with mean 0 and variance $\sigma^2$, then $|X|$ follows a *half distribution* with mean $\sigma \sqrt{\frac{2}{\pi}}$, and variance $\sigma^2 (1-2/\pi)$. This gives the required answer, since the variance $\sigma^2$ of the normal walk is $n$, and you can approximate the distribution of $X$ to a normal distribution using the central limit theorem.

$X$ is the sum of the random walk as Yuval Filmus mentioned.

# Answer
> 2 votes
In first $2i$ flips, suppose we get $k$ tails, then $H\_{2i}=2|i-k|$. Therefore, \begin{align} E(H\_{2i}) & =2\sum\_{k=0}^{i}\binom{2i}{k}(\frac{1}{2})^{2i}\cdot 2(i-k)\\ & = (\frac{1}{2})^{2i-2}\left\[i\sum\_{k=0}^{i}\binom{2i}{k}-\sum\_{k=0}^ik\binom{2i}{k}\right\]\\ & = (\frac{1}{2})^{2i-2}\left\[i\left(2^{2i}+\binom{2i}{i}\right)/2-2i\sum\_{k=0}^{i-1}\binom{2i-1}{k}\right\]\\ & = (\frac{1}{2})^{2i-2}\cdot i\left\[2^{2i-1}+\binom{2i}{i}/2-2\cdot 2^{2i-1}/2\right\]\\ & = 2i\cdot\binom{2i}{i}/2^{2i}. \end{align} Use Stirling's approximation, we know $E(H\_{2i})=\Theta(\sqrt{2i})$.

---
Tags: probability-theory, randomized-algorithms
---


# Question
Title: Does having more bus in the computer increasing speed?
Whát i mention here is for having 2x bus will increasing 2x memory access speed like 3x will have 3x memory access speed like that !

# Answer
> 2 votes
It is difficult to answer in full generality for any kind of bus but I think generally the answer is: no.

First speed is imprecise, there are two notions: latency and throughput. Increasing the width of a bus can increase throughput but it will not help latency. Second, in theory doubling the width indeed doubles the throughput, but there is much to consider than the bus itself. Indeed, the data comes from somewhere (source), is used somewhere else (destination) and will usually travel over several (internal) buses. Thus it is pointless to have a super fast external bus if your CPU and/or internal bus is slow for example. Also if the data comes, for example, from a hard drive then it cannot be read faster than some speed for mechanical reasons and increasing the bus width will not change that. The same applies to the destination: if your CPU cannot process the data fast enough, then having a large bus is also pointless.

Finally, I would like to point out that increasing the width of a bus comes with its own problems, like interference and routing.

---
Tags: computer-architecture, memory-management, memory-hardware, memory-access
---


# Question
Title: Why there is no direct connection between the data bus and the accumulater register
In the data bus all the registers are connected in and out with the data bus but the AC don't have it only out also the memory don't have a direct connection with it ? Please explain if you know

# Answer
The answer as in many cases: Someone thought it was a good idea.

Someone may have evaluated cost and benefits and may have decided that the benefits were not worth the cost.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Comparison Based Sorting Run-time with respect to Total Number of Bits of Input
Comparison-based sorting algorithms are lower bounded by $\Omega(nlogn)$, where $n$ is the number of elements in the input list.

However, when dealing with different models of computation, such as algorithms that deal with arithmetic operations (Euclid-GCD) or, $n$, the size of the input, is no longer the number of elements but the total number of bits required to represent the input. In these cases, time complexity is measured as the number of bit operations needed with respect to the total number of bits in the input.

Looking at the post What Is Pseudo-Polynomial Time How Does It Differ From Polynomial Time?

Polynomial time is defined as:

> An algorithm runs in polynomial time if its runtime is O(xk) for some constant k, where x denotes the number of bits of input given to the algorithm.

Pseudo-polynomail time is defined as:

> An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

Looking at How Can We Assume That Basic Operations on Numbers Take Constant Time?

For word size $w = \theta(logn)$, standard arithmetic operations on these words take $O(1)$ time, by definition.

With these definitions in mind, I have trouble seeing how some comparison-based sorting algorithms are polynomial time with respect to both $n$, the number of elements in the input, and $x$, the total number of bits in the input; the first post I referenced makes this claim.

Why they are polynomial with respect to $n$ is pretty obvious, so I will only look at the bit representation of input $x$ for comparison-based sorting algorithms with 2 different time complexities.

**Merge or Quick Sort on a List of $n$ Elements**

We need $w = \theta(logn)$, as defined in CLRS, since we at least need to be able to index into an array of size $n$. **Assuming all elements fit in a word**, which I think is a reasonable assumption here, $x = wn = \Theta(nlogn)$. **Please let me know if my $x$ is wrong!!!**

Since the running time was $O(nlogn)$, the time complexity with respect to $x$ is $O(x)$. I will interpret this as meaning we need a linear number of operations on the total number of bits needed to represent this input list.

**Selection Sort on a List of $n$ Elements:**

I will assume the same $x = wn = \Theta(nlogn)$ for the input size. The running time is $O(n^2)$. ***Here I need some help: how do I write the running time cleanly in terms of $x$, like I did for Merge/Quick Sort above?*** The first post I referenced just used $w = 32$ bits and easily got $O(x^2)$ polynomial time but this doesn't seem right to me, since the \[second post\] I referenced (How can we assume that basic operations on numbers take constant time?) and CLRS stressed $w$ is not a constant but $\Theta(logn)$.

I have a similar question for counting sort, that has not been answered yet.. the first post I referenced claims it is exponential with respect to $x$ without the $k = \Theta(n)$ condition when $x = \Theta(nlogk)$ bits, but I have trouble changing from $O(n + k)$ in terms of $x$. Please help!!

# Answer
Assume, as is often the case, that all elements in the list have width $\Theta(\log n)$. This means that $w = \Theta(\log n)$ and so $x = nw = \Theta(n\log n)$. You can check that $n = \Theta(x/\log x)$, and this allows you to convert running times stated as a function of $n$ to running times stated as a function of $x$. For example, if the running time of some algorithm is $\Theta(n^2)$ as a function of $n$, then its running time as a function of $x$ is $\Theta(x^2/\log^2 x)$.
> 1 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, sorting, radix-sort
---


# Question
Title: Total Number of Bits Needed to Represent a List of N elements
This is an excerpt from the algorithms textbook **How to Think About Algorithms** by Jeff Edmonds (This book is a gem by the way).

I get his conclusion about Merge/Quick/Heap sorts having $O(NlogN)$ operations with respect to $N$, the number of elements in the input list, and at the same time they are linear in the context that they need $O(n)$ opertaions with respect to the number of bits needed to represent the input list. Different models of computation and a good way to describe one algorithm under different models.

But my question is in the line

> Assuming that the $N$ numbers to be sorted are distinct, each needs $logN$ bits to be represented, for a total of $n = \Theta(NlogN)$ bits.

My understanding of this was that with $N$ distinct numbers, we need word size $w = \theta(logN)$, as defined in CLRS. We want the word size to be able to at least index into $N$ different elements but not so big that we can put **everything** in one word. Also, with $N$ distinct elements, we need $\Omega(logN)$ bits to represent the largest number. Assuming each word will fit in $w$, Edmonds' claim that $n = \theta(NlogN)$ bits made sense. Please correct me if my analysis is wrong up to here.

But when I try to apply this to counting sort, something doesn't seem right. With $N$ again the number of elements in the input and $k$ the value of the maximum element in the list, the running time is $O(N + k)$. Counting sort is linear with respect to $N$, the number of elements in the input, when $k = O(N)$. Using this constraint to represent the input as the total number of bits $n$, I think $n = O(Nlogk) = O(NlogN)$.

So with in the RAM model of computation, how can I express the run-time of counting sort with respect to $n$ bits? Merge/quick/heap sorts had time complexity $O(n)$ with respect to $n$ bits, as was expressed cleanly by Edmonds. I am not sure how to do something similar for counting sort, and maybe possibly for radix sort using counting sort as a subroutine. Any idea how to do this in the two cases when $k = \Theta(N)$ and when this condition is not present? I am suspecting the former will give some kind of polynomial time with respect to $n$ and the latter exponential (hence pseudo-polynomial) time with respect to $n$ bits, but have trouble expressing the mathematics...

# Answer
In the RAM model of computation, machine words are $\Theta(\log n)$ bits long (where $n$ is the size of the input in bits), and operations on machine words can be done in $O(1)$. Counting sort has running time $O(N + k)$ in the RAM model assuming that each value is $\Theta(\log n)$ bits long.

Let us now consider an array consisting of $N$ values, the maximal value of which is $k$. We would need $\log k$ bits to store each value. Assuming that we use $\Theta(\log k)$ bits per value, the input length is $n = \Theta(N\log k)$ bits, and so a machine word is $\log N + \log\log k + O(1)$ bits long. Let us denote by $w$ the number of machine words needed to store a single entry, which we can calculate by $$ w = \left\lceil \frac{\log k}{\log N + \log\log k} \right\rceil = \Theta\left(\max\left(1,\frac{\log k}{\log N + \log\log k}\right)\right). $$ The running time of counting sort is $O(Nw + k)$.
> 1 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, sorting, radix-sort
---


# Question
Title: Generating a Context Free Grammar(CFG) from a Language
I would really appreciate if anyone could tell me how to generate CFG from this language. I am trying to learn the procedure of generating CFGs from CFLs and I am able to solve easier problems.. but I am really stuck on this one, I just can't get it how can I generate at two different positions at the same time.

**`L = {0^i 1^j 0^k | i + j >= 2k }`**

# Answer
> 1 votes
You can construct the grammar using the following nonterminals:

* $S$ is the initial nonterminal. We will include a production $S \to 00S0$ to capture the inequality $i+j \geq 2k$ being satisfied just using $i$.
* $T$ will similarly be a nonterminal that will include a production $T \to 11T0$ which captures the inequality $i+j \geq 2k$ being satisfied just using $j$. We also add a termination production $T \to \epsilon$.
* The production $S \to T$ will allow us to mix both kinds of ways to satisfy the inequality $i+j \geq 2k$. However, there are two problems:

1. We need to allow $i+j \> 2k$.
    2. We need to allow the case $i+j = 2k$ in which $i,j$ are both odd, i.e., at some point the inequality $i+j \geq 2k$ is satisfied by increasing $k$ by 1, and compensating by increasing both $i$ and $j$ by 1.
* To handle the second problem, we will add a production $S \to 01T0$.
* To handle the first problem for $i$, we will add the production $T \to 1T$, and to handle it for $j$, we will add the production $S \to 0S$.

In total, we obtain the following grammar:

$$ \begin{align\*} & S \to 0S \mid 00S0 \mid 01T0 \mid T \\ & T \to 1T \mid 11T0 \mid \epsilon \end{align\*} $$

You can prove by induction the following statements:

1. $T \Rightarrow^\* xTy$ iff $x = 1^j$, $y = 0^k$, and $j \geq 2k$.
    * As a conclusion, $T \Rightarrow^\* w$ if $w = 1^j0^k$, where $j \geq 2k$.
2. $S \Rightarrow^\* xSy$ iff $x = 0^i$, $y = 0^k$, and $i \geq 2k$.
    * As a conclusion, $S \Rightarrow^\* xTy$ if either $x = 0^i$, $y = 0^k$, and $i \geq 2k$, or $x = 0^i1$, $y = 0^k$, and $i+1 \geq 2k$.
    * As a conclusion from (1), $S \Rightarrow^\* w$ if $w = 0^i 1^j 0^k$, where $i+j \geq 2k$.

---
Tags: computability, context-free, pushdown-automata
---


# Question
Title: Is the language given by a context-free grammar always context-free?
Consider the language generated by the following grammar:

$S \to aSBb \mid \epsilon$

$B \to aB \mid bB \mid \epsilon$

Is the above language context-free?

---

The above language looks like $\\{ w \in (a+b)^\* : a^n w\_1b w\_2b ... w\_nb \\}$.

I tried using the pumping lemma to show that this language is not context-free, but I was unable to do so.

# Answer
> 6 votes
Hint: A language $L$ is context-free iff there exists a context-free grammar $G$ such that $L = L(G)$. (Some people take this as the *definition* of context-free languages.)

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Classification of the complement of a language
$L = \\{ \langle M \rangle \mid M \text{ accepts two strings of different lengths} \\}$.

What is complement of this language?

my attempt:

the complement is: $M$ accepts no two strings of same length and this can be done by dovetailing different inputs on M but we can never say IT CANNOT ACCEPT TWO STRING OF SAME LENGTH and hence its NOT RECURSIVELY ENUMERABLE?

# Answer
The complement of $L$ is:

$\bar{L} = \\{\langle M \rangle \mid \text{ all strings accepted by $M$ have the same length} \\}$

Your intuition that $\bar{L}$ is not recursively enumerable is correct, it is in fact complete for $\Pi^0\_1$ by reduction from the emptiness problem. If you only need to prove that $\bar{L}$ is not in $\textsf{RE}$, it is sufficient to observe that $L$ is undecidable (reduction from the halting problem) but $\textsf{RE}$ (trivial).
> 1 votes

# Answer
The complement of $L$ is $$\overline{L} = \\{\langle M \rangle \mid |L(M)|\>1 \implies \text{ all strings of } L(M) \text{ have the same length}\\}$$ In words, $L$ consists of those TM $M$ such that either $L(M) = \emptyset$, or $L(M)$ has only one string, or all strings in $L(M)$ have the same length.

$L$ is recursively enumerable. Given $\langle M \rangle$ you can use dovetailing to search for two strings in $L(M)$ of different length, and accept $\langle M \rangle$ as soon as you find a single pair. You can solve yourself if $\overline{L}$ is recursively enumerable or not.
> 1 votes

---
Tags: turing-machines, computability
---


# Question
Title: Do all algorithms aim to solve decision problems?
An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more abstractly considered decision problems? Is the ultimate reason for a calculation, data processing or automated reasoning to solve a higher decision problem?

Thank you and forgive my ignorance.

# Answer
> 4 votes
There is a class of problems called *decision problems* that have an *yes/no* answer. These problems can be further be classified in *decidable*, where we have a way to solve them, or *undecidable*, for which there cannot be or has not been yet discovered a way to solve them.

However, there is another set of problems where we are not interested in a yes/no answer, but rather in a more specific solution. For example, there are *optimisation problems*, where we are searching for the best value according to some parameters, or *counting problems*, where we are interested in counting the number of instances where certain property occurs.

To sum it up, decision problems are a specific class of problems, a subset of which can be solved by algorithms. However, algorithms can be used to solve problems in other classes.

Now, given an algorithm for a specific problem, one can solve multiple problems equivalent to the original one (there are ways of "translating" a problem in the terms of another one, and having a solution to one problem means having a solution for all such problems).

# Answer
> 2 votes
First, note that a decision problem has a very specific meaning in the context of algorithms: a decision problem is essentially a question to which the answer is either YES or NO.

An algorithm does not necessarily have to solve a decision problem. We may for instance design a (simple) algorithm to find an element of maximum value from an list. However, in complexity theory, it turns out that a decision problem is often a very convenient form to reason with. The complexity classes P and NP for example are both classes of decision problems.

Because decision problems are useful, we often 'reformulate' a problem as a decision problem. We could for instance ask whether the maximum element in a list has at least the value $M$. This is a decision problem version of our earlier problem and algorithms that solve this decision problem could (usually) be used to solve the original problem.

---
Tags: algorithms, decision-problem
---


# Question
Title: What is a "slice" of a parameterized problem $(Q, \kappa)$?
In the book "Parameterized Complexity Theory" by J. Flum, and M. Grohe, there is a definition on page 7:

**Definition 1.10.**
Let $(Q, \kappa)$ be a parameterized problem and $\ell \in \mathbb{N}$. The $\ell$th slice of $(Q, \kappa)$ is the classical problem

$$(Q, \kappa)\_\ell := \\{x \in Q\ |\ \kappa(x) = \ell\\}$$

Which is also referred to in the following chapters. Although I can understand the topics fairly enough, I still cannot understand the term "slice" in detail.

I kind of "memorized" that a slice of an fpt problem is solvable in PTIME. However, I do not really understand the logic behind it.

So, my question is:

> What is a *slice* of a parameterized problem?

# Answer
Consider the *Graph Coloring problem*.

Let $k$-Colorability be the language defined as follows.

* $\\{(G, k)\ | \ \text{$G$ is a $k$-colorable graph}\\}$

Given $\ell \in \ \mathbb{N}$, the $\ell$-th slice of $(G, k)$ is the problem:

* $\\{(G, k)\_\ell | \ \text{$G$ is a $k$-colorable graph and $k=\ell$}\\}$

As you mention, *a slice of an FPT problem is solvable in PTIME*.
Using contraposition you get that if a slice is not solvable in PTIME than the problem is not FPT.
Indeed, if from one hand, 2-Coloring $\in \mathbb{P}$, on the other hand, 3-Coloring (or more generally, for any $k \> 2$) $\notin \mathbb{P}$.
Hence, Colorability is not FPT.
> 4 votes

# Answer
The way you state it, a slice of an parameterized problem is the problem where we use some fixed constant for our problem parameter, instead of a 'free' variable. In a sense, we are only considering the subfamily of the problem for this particular constant, which is probably the logic behind the name 'slice'.

Indeed, if a problem $(Q,\kappa)$ is fixed parameter tractable, there is an algorithm that solves this problem with running time $O(f(n)\cdot g(\kappa))$, where $f$ is (sub)polynomial and $g$ can be superpolynomial. So, if we take a slice of this problem, then there is an algorithm that solves the problem '$(Q,l)$' ($=(Q,\kappa)\_l$) in time $O(f(n)\cdot g(l)) = O(f(n))$, as $l$ and therefore $g(l)$ is constant. So $(Q,\kappa)\_l$ is indeed solvable in PTIME.
> 4 votes

---
Tags: complexity-theory, parameterized-complexity
---


# Question
Title: How to classify a 3D "Knapsack" problem where the only limitation is space, i.e. there is no weight constraint?
The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of the packing. When researching knapsack problems all of the different variations I came across had a weight constraint and most didn't consider geometrical 3D space as a constraint. So my question is: is my problem considered a knapsack problem and/or is there a different term for these kind of problems which I could look into further?

# Answer
In the standard Knapsack problem (solvable by DP) when we are packing objects we do not care about how we put objects in the knapsack, i.e., what only matters is a subset of objects and the sum of weights of these objects. But, in cuboid/rectangle packing problem the configuration of the cubes/rectangle is important to achieve the optimal packing. So, from this point of view these problems are different. I googled and found this heuristic approach and this article.
> 1 votes

---
Tags: optimization, packing
---


# Question
Title: Finding the average time complexity for a max algorithm
I'm trying to find the average-case *number of times that max is assigned a value* by the below algorithm `find_max`.

```
find_max(L):
     max = -oo # negative infinity
     for k = 0 to len(L)-1:
          if L[k] > max:
               max = L[k]
     return max

```

However, I'm struggling to come to a solution. So far, this is what I have done:

I'm defining the sample space to be L containing values which are between 1 and 100, and having them uniformly distributed.

The worst-case running time is $T(n) = n + 1$ because of the initial max assignment, and the case where every element is larger than the previous one.

The best-case running time is $T(n) = 2$ which is the case where all elements have the same value, so there is the initial max assignment and one assignment in the for loop.

So, the running time is distributed between 2 and n+1 inclusive.

Then, the average-case running time is:

$E\[t\_{n}\] = \sum\_{2}^{n+1} t \cdot P(t)$

However, I am having difficulty defining the Random Variable T and the probability formula for values of T.

# Answer
Let $\small n = \mathsf{len}(L)$ and $\small t\_n$ be the times that $\small \mathsf{max}$ is assigned a value. For $\small 0 \leq i \< n$, define a random variable $\small X\_i$ as $$ \small X\_i = \begin{cases} 1 & \text{if } L\[i\] \> \text{$\mathsf{max}$ in the $i$-th iteration of the algorithm}\\ 0 & \text{otherwise} \end{cases} $$ Then we have $$ \small t\_n = 1 + \sum\_{i=0}^{n-1} X\_i $$ By linearity of expectation, $$ \small \mathbb{E}\[t\_n\] = 1 + \sum\_{i=0}^{n-1}\mathbb{E}\[X\_i\] $$ Observe that $\small X\_i = 1$ if and only if $\small L\[i\] \> \max\\{L\[0\], L\[1\], \cdots, L\[i-1\]\\}$. Therefore \begin{align} \small \mathbb{E}\[X\_i\] = \Pr\[X\_i = 1\] =&\small \sum\_{v=1}^{100} \Pr\[L\[0\] \< v, L\[1\] \< v, \cdots, L\[i-1\] \< v, L\[i\] = v\] \\ \small= &\small \sum\_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot \frac{1}{100} \end{align} We thus conclude \begin{align} \small \mathbb{E}\[t\_n\] =&\ \small 1 + \sum\_{i=0}^{n-1}\sum\_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot\frac{1}{100} \\ \small =&\ \small 1 + \frac{1}{100}\sum\_{v=1}^{100}\sum\_{i=0}^{n-1}\left(\frac{v-1}{100}\right)^i \\ \small =&\ \small 1 + \frac{1}{100}\sum\_{v=1}^{100}\frac{1 - \left(\frac{v-1}{100}\right)^n}{1 - \frac{v-1}{100}} \\ \small\text{(for sufficiently large $n$)}\quad\quad\approx&\ \small1 + \frac{1}{100}\sum\_{v=1}^{100} \frac{1}{1 - \frac{v-1}{100}} \\ \small = &\ \small 1 + \sum\_{v=1}^{100}\frac{1}{101-v} \\ \small =&\ \small 1 + H\_{100} \end{align} where $\small H\_{100}$ is the $\small 100$-th harmonic number.
> 1 votes

---
Tags: complexity-theory, runtime-analysis, average-case
---


# Question
Title: What does "effective enumeration" in Turing machines mean?
what is meant by EFFECTIVE ENUMERATION i have comes across this word when I was reading about enumerators for Turing machines is it same as LEXICOGRAPHIC ORDER? so effective enumeration is possible for recursive sets but no recursively enumerable sets? i came across this in this question of a competitive exam

L1 is a recursively enumerable language over Σ. An algorithm A *effectively enumerates* its words as ω1,ω2,ω3,…. Define another language L2 over Σ∪{#}

{wi#wj ∣ wi,wj∈L1, i \< j}.

Here # is a new symbol.

Consider the following assertions.

S1:L1 is recursive implies L2 is recursive

S2:L2 is recursive implies L1 is recursive

which of the following is true ?

# Answer
One way to approach EFFECTIVE ENUMERATION is as following. Let $L=\\{a\_1, a\_2, \dots\\}$ be a set/language. Then we (effectively) enumerate $A$ if we can construct a TM $M$ which prints out (enumerates) all elements of $L$ on the tape, say in the following way: $a\_1$#$a\_2$#$a\_3$#$\dots$. The order of the elements is not important. What is important is that any element of $L$ *will eventually be printed* on the tape, meaning it must not be a LEXICOGRAPHIC order.
> 1 votes

# Answer
"Effective" usually means "computable". Therefore, an effective enumeration is a computable enumeration.

In the problem you note, this is redundant. An algorithm that enumerates a set is, by definition, a witness for the set being effectively enumerable.
> 0 votes

---
Tags: turing-machines, computability, terminology
---


# Question
Title: Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$
I am studying different models of computation and how algorithms can be interpreted under different models.

Here is a math(?) question that has been bugging me.

Suppose we have $n = \Theta(N\log N)$ bits as the size of input and there are N elements in the input. (The implied assumption is each element has $\Theta(\log N)$ bits).

Now we know Insertion Sort has running time of $\Theta(N^2)$ in the worst case with respect to N, the number of elements in the input.

Under the RAM model, the input is $n = \Theta(N\log N)$ bits. So we can say $N = \Theta\left(\frac{n}{\log N}\right)$. I want to show that the running time $T = \Theta\left(\frac{n^2}{\log^2n}\right)$ by first showing that $N = \Theta\left(\frac{n}{\log n}\right)$.

Since $N \leq n$, $N = \Theta\left(\frac{n}{\log N}\right)=\Omega\left(\frac{n}{\log n}\right)$. I am having trouble showing $ N = \Theta\left(\frac{n}{\log N}\right)= O\left(\frac{n}{\log n}\right)$ to be able to use the $\Theta$ notation.

In general, I am not so sure what kind of manipulations are allowed inside $\Theta$ so that its definition is intact.

# Answer
> 1 votes
There is not any strange thing here. As:

$$\frac{n}{\log(n)} = \frac{n}{\log(N\log(N))} = \frac{n}{\log(N)+\log(\log(N))} = \Theta\left(\frac{n}{\log(N)}\right) = O\left(\frac{n}{\log(N)}\right)$$

Therefore, all of them are true.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, landau-notation
---


# Question
Title: Are there polynomial time reductions where the corresponding witnesses can't be translated in polynomial time?
At the heart of NP-completeness is the idea that one can reduce *instances* of any problem in NP to, for example, 3-SAT. But this definition doesn't require that it must be possible to convert witnesses for yes-instances in polynomial time also. Does this fact follow regardless?
I'm looking at this in particular from the point of view of zero-knowledge proofs. Here the existence of computationally zero-knowledge proofs for all problems in NP is demonstrated by showing that 3-colorability has such proofs. But the guarantee that I can translate problems - or "conjectures" - in polynomial time is useless. I need to be able to translate witnesses - or "proofs". How is the possibility of this assured?

# Answer
The proof of the Cook-Levin theorem shows that any problem in NP can be reduced to SAT in such a way that witnesses to the original problem can be converted efficiently to satisfying assignments of the resulting SAT instance. The proof of the NP-completeness of 3-colorability goes via a series of reductions, each of which also has this property.
> 1 votes

---
Tags: np-complete
---


# Question
Title: Why does functional map() operation not permit operating on two elements of a list at a time?
Mathematically it seems so easy to use two elements of a vector as two arguments to a function. $$f(\boldsymbol{x\_{i+1}},\boldsymbol{x\_{i}})$$ In functional programming however a map (function) allows to work with one element at a time only, so one would need to create vector of pairwise 2-tuples from a single initial vector fisrt. **Why is that? Is it also more proper mathematically?**

# Answer
> 4 votes
Conceptually, 1-argument `map` should be able to work on unordered collections, because each application of a mapping function doesn't know anything about the element's index.

Your proposed version does know something about the elements' indices, so treats its argument as an ordered sequence of elements. That's the difference.

For regular lists, we can recover the indices by zipping the list with the (infinite, unbounded) sequence `[1..]`. So, the ability to zip assumes the sequence is ordered - not in values, but positionally.

Mathematicians can have some specific terminology for this, but I think that's the gist of it.

Such sequences you can always split into a special so-called *head* i.e. "first" element, and the rest of them, *deterministically*. But e.g. for truly non-deterministic sequences this is not possible, yet mapping is still a well-defined operation.

---
Tags: functional-programming
---


# Question
Title: Proving worst-case running time is in $\Omega(n^2)$
I was given the following method to argue that an algorithm $A$ has a worst-case running time of $\Omega(n^2)$:

> We need to argue that there exists an input $x$ of size $n$, the running time of $A$ with input $x$, i.e., $t(x)$, is at least $cn^2$, where $x\>0$ is a constant.

If you find a single input of size $n$ that gives A a running time of exactly, $n^2$, then couldn't there still exist a different one that is less than $n^2$, since we're only specifying one input and not all inputs? I'm having difficulty understanding the logic.

# Answer
> 5 votes
The worst-case running time of an algorithm $A$ is a function $T(n)$ which accepts an input length and outputs the maximum running time of algorithm $A$ on an input of length $n$:

$$ T(n) = \max\_{|x|=n} \mathrm{runtime}(A,x). $$

Therefore to prove that $T(n) \geq S(n)$, it suffices to show that for each $n$ there is an input $x\_n$ of size $n$ such that $\mathrm{runtime}(A,x\_n) \geq S(n)$. The fact that there exist other inputs on which $A$ performs better is completely immaterial, since the worst-case running time depends on the *worst* input.

---
Tags: asymptotics, proof-techniques
---


# Question
Title: Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?
Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous? According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars generating them. Every regular language is also DCFL, hence they will follow the same, but I doubt if every grammar corresponding to a DFA is non-ambiguous and that of NFA is ambiguous.

# Answer
Let us consider the following construction of a regular grammar from an NFA. We will have a non-terminal $S\_q$ for each state $q$. The starting symbol is $S\_{q\_0}$. If there is a transition from $q$ to $q'$ upon reading $\sigma$ (possibly $\sigma = \epsilon$), then we add the transition $S\_q \to \sigma S\_{q'}$. If $q$ is an accepting state, we add the transition $S\_q \to \epsilon$. Whether the result is a regular grammar or not depends on your definition of a regular grammar (and on whether you allow $\epsilon$ transitions), but let's ignore this aspect.

You can check that this grammar is unambiguous if and only if, each word $w$ accepted by the NFA has a unique accepting path in the NFA, where an accepting path is something that looks this way: $$ q\_0 \xrightarrow{\sigma\_0} q\_1 \xrightarrow{\epsilon} q\_2 \to \cdots \to q\_f, $$ where $q\_f$ is an accepting state, and the symbols on top of the arrows spell $w$. Such an NFA is known as a *UFA* (U stands for Unique).

Every DFA is a UFA since every word has a unique path through the DFA (or, depending on your exact definition, *at most one* path). Some NFAs are UFAs, others are not.
> 3 votes

---
Tags: automata, finite-automata, formal-grammars
---


# Question
Title: State Machine and State transition Table - Explanation and Creation Of
How do I create a state transition table/array in actual code/pseudo-code?

I haven't experienced the "ah-ha" moment yet with the state machine to coding (and I really want to). I've looked at several code sample and read blog posts, but it's not clicking yet.

I'm looking for a pragmatic explanation of how the state transition table works and how it's created in an array format. If possible, is there a "step-by-step" method to get to the solution?

---

**The particular case/excercise I'm working on is this:** I'm writing a gray-code rotary encoder driver for A micro-controller based on the .netMF framework. It's not real-time and therefore changes the rules a little. Interrupts are captured and queued and then run in a high priority thread. There is a delay so it makes capturing the state of the both encoder pins at the actual time of interrupt in-accurate. In-accurate enough to cause some errors. That being said, when the interrupt is queued, it's state IS captured at that time. When the ISR is finally executed, the pin's state state is passed into it as an argument. Therefore, I can only get ONE pin's state at a time. I think that's sufficient to get this working.

```
Encoder States For Pin A and B:
A B
0 1
0 0
1 0
1 1 - base state(neutral position of the encoder) (move up for one direction and down for opposite direction)
0 1
0 0
1 0

```

The mechanical bounce in the encoders will be captured and queued as well, but from what I understand, the state machine can handle these "errors" and continue to produce a good result if the device makes it through a cycle.

I hope this question is clear. I can add additional information as needed.

# Answer
> 1 votes
The state transition function just says "If you're in state $X$ and receive input $Y$, go to state $A\_{X,Y}$", for every possible $X$ and $Y$.

Designing the transition function is a matter of programming; implementing it is just a case of

```
state := start_state
while state is not a terminating state do
    input := read_input ();
    state := A[state, input];
done

```

---
Tags: transition-systems, design-patterns
---


title: Hamming distance

text:
# Question
Title: Hamming distance
I have some difficulties in computing Hamming distance in following example:

11100000
00011100
10010010
01001001

I know the definition of Hamming distance (in case of two codewords) but how to proceed in above example. Can someone shed some light on how to compute d\_min in above example?

Regards

# Answer
Denote the codewords as $a\_1,...a\_4$. Remember that the hamming distance is the number of different bits between two codewords.

1. $d(a\_1,a\_2) = 6$
2. $d(a\_1,a\_3) = 4$
3. $d(a\_1,a\_4) = 4$
4. $d(a\_2,a\_3) = 4$
5. $d(a\_2,a\_4) = 4$
6. $d(a\_3,a\_4) = 6$

Thus $d=4$.
> 0 votes

---
Tags: error-correcting-codes
---


# Question
Title: What is the precise definition of pseudo-polynomial time (feat. Counting Sort)
From wikipedia

> In computational complexity theory, a numeric algorithm runs in **pseudo-polynomial** time if its running time is a polynomial in the length of the input (the number of bits required to represent it) and the numeric value of the input (the largest integer present in the input). In general, the numeric value of the input is exponential in the input length, which is why a **pseudo-polynomial** time algorithm does not necessarily run in polynomial time with respect to the input length.

From this SO post

> An algorithm runs in **pseudo-polynomial** time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

I have some questions about the wiki definition. To my knowledge, the definition provided by the SO post makes more sense. **Shouldn't the wiki say pseudo-polynomial time is if the running time is
1) exponential (or something greater than polynomial) in the length of the input, and
2) polynomial in the numeric value of the input (largest number of input)
??**

Assuming you have answered the question of definition above,

I am having trouble analyzing the running time of Counting Sort which is $O(N + K)$ with respect to $N, K$, the numeric values of the input.

Assuming we do not have the $k = \Theta(N)$ simplifying condition, the length of the input is $x = \Theta(N\log(k))$ bits.

The Wiki says "In general, the numeric value of the input is exponential in the input length". But $k = 2^{\Theta(\frac{x}{N})}$. With N potentially bringing down the magnitude of the exponent, **I don't really see how $k$ is exponential in $x$.**

In addition, the SO post I referenced claims counting sort runtime is exponential with respect to the length of the input, $x = \Theta(N\log(k))$ bits. **How can $O(N + k)$ be transformed into an expression exponential in $n$ to demonstrate the claim?** I got it down to $O(\frac{x}{\log(x)} + k)$ but got stuck there.

If I just think the length of the input is $\Theta(\log k)$ then I can see why the run-time is exponential but this doesn't seem to be consistent with how $x$ should be defined.

# Answer
> 2 votes
Let us denote the input's length by $n$, and lets remember that $n=\Theta\left(N\log K\right)$. You won't be able to write the **exact** running time of counting sort as an expression of the form $2^{\Omega(n)}$, as this would mean that for large enough inputs, the running time is always exponential. However, in this case, if $K$ is not too large compared to $N$, then the running time is actually linear, this means that there exists an infinite series of inputs with increasing size on which the running time is not exponential.

With this is mind, recall that what you seek is the worst case complexity of your algorithm, i.e. you want to find a certain time bound that holds for all inputs of large enough size. This means that to lower bound the complexity, it suffices to find one series of inputs with increasing size on which the running time is exponential. This allows you to focus on inputs where $K=2^N$, in this case the input size is $n=\Theta\left(\log^2 K\right)$, and the running time is $O(K)=O\left(2^{\sqrt{n}}\right)$, which is definitely exponential.

In general, a pseudopolynomial time algorithm is an algorithm which runs in polynomial time in the numeric value of the input (which means it is not necessarily polynomial in the input's length). Wiki's definition is no different, except it adds the restriction that the running time is polynomial in both the numeric value and the input size, i.e. if the input size is $n$, and its associated numeric value is $v$, we want a time bound of the form $p(n,v)$ for some polynomial $p$. This excludes for example a $2^N+K$ time algorithm for sorting $N$ numbers in the range $\[1,K\]$, although this is polynomial in $K$.

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


# Question
Title: complement of a NON RECURSIVELY ENUMERABLE LANGUAGE
Define languages L0 and L1 as follows :

L0={⟨M,w,0⟩∣M halts on w}

L1={⟨M,w,1⟩∣M does not halt on w}

Here ⟨M,w,i⟩is a triplet, whose first component M is an encoding of a Turing Machine, second component w is a string, and the third component i is a bit.

Let L= L0 ∪ L1. Which of the following is true?

L is not even recursively enumerable as we cannot even design an acceptor for L as even when L0 is RE L1 is not RE

but can anyone explain me what about L COMPLEMENT what is the language ??

L0'={⟨M,w,0⟩∣M doesn't halts on w}

L1'={⟨M,w,1⟩∣M halts on w} what i am working on is will there be any such encodings which satisfy both for the intersection to be non empty if there are no such encodings the set becomes empty and hence regular right ? please help

# Answer
The complement of $L$ is $$\overline{L\_0 \cup L\_1} = \overline{L\_0} \cap \overline{L\_1}$$ where $\overline{L\_0} = \\{D \mid \text{ if } D \text{ is } \langle M,w,0\rangle \text{ then } M(w) \text{ does not halt}\\}$. In other words, $\overline{L\_0}$ consists of those triples $\langle M,w,b\rangle$ which does not include descriptions $\langle M,w,0\rangle$ such that $M$ halts on $w$. Similarly for $\overline{L\_1}$. This post explains why both $L$ and $\overline{L}$ are not recursively enumerable.
> 2 votes

---
Tags: turing-machines, computability, undecidability
---


# Question
Title: What is exponent of denormalized real in IEEE 754 floating point format?
I was reading this link.

Here I noticed that, in table titles "Float Values (b = bias)", in exponent column, entry for denormalized reals is $00..00$, but in value column, the entry is $-b+1$. Why is there $+1$? If we consider bias of $127$ for single precision format, shouldnt it be $0-127$ only? If its $-126$, then shouldnt the entry in the exponent column be $00..01$?

(The article seems to have taken from Stallings book specified in the references. Stallings book also says the same as above.)

# Answer
> 3 votes
Both an exponent field of 00000000 and 00000001 encode an exponent of -126, but with 00000000 there is no implicit leading 1 and with 00000001 there is. Consider going from 0x00800000 (smallest normal) to 0x007fffff (biggest denormal). For 0x00800000 the significand (including leading 1) is still 0x00800000 (a nice coincidence), for 0x007fffff is significand is just 0x007fffff. Since the exponent remains the same, these are just as adjacent as they seem (the distance between them is the lowest non-zero denormal).

If the exponent for denormals was -127, the denormals would only fill up to halfway between zero and the lowest normal, leaving a large gap between the highest denormal and the lowest normal.

---

Normally the number line including denormals looks like this (if you had 2 bits of significand, so 4 numbers per binade): (source)

You can see the denormals and the numbers in the first normalized binade are equally spaced, meaning they have the same exponent. What happens if the denormals had the exponent which their encoding seems to imply?

A gap appears.

---
Tags: floating-point
---


# Question
Title: Time complexity of this nested loop should be $O(n^{48})$ instead of $O(n^6)$
I was asked to solve this code on piece of paper while having a debate in the class. We are all new to DataStrct/Algo. I came up with the answer $O(n^{48})$ which was proved wrong. I am not convinced with the answer they gave me which was $O(n^6)$.

```
void main()
{
    int i;

    for(i=1, i<= n^2; i++)
    for(i=1, i<= n^4; i++)
    for(i=1, i<= n^6; i++)
    printf("0");
}

```

What is the no. of times '0' is printed?

Following is my computation for calculating complexity

1. for loop: $O(n^2)$ then
2. for loop: $O(n^4)$ then
3. for loop: $O(n^6)$

making total of $$O(n^2) \cdot{} O(n^4) \cdot{} O(n^6) = O(n^{48})$$

# Answer
Sorry to say you that you are wrong!

I am no expert but I have tried to break it down for you.

This question not only test your algorithm analysis skills but also test your language skills.

You can learn in detail about algorithmic complexity and how to translate your program to mathematics here Is there a system behind the magic of algorithm analysis?

Save this link or Bookmark it, it will be helpful to you later.

Here is your program

IMP: You need to pay attention to variable 'i' and how it plays its role in all three loops.

This problem checks your syntax knowledge, scope of variable, and complexity knowledge all three in one go.

```
void main()
{
    int i;..............................statement 1 [executed once]

    for(i=1, i<= n^2 ; i++)..............statement 2 [executed twice]
    for(i=1, i<= n^4; i++)..............statement 3 [executed twice]
    for(i=1, i<= n^6; i++)..............statement 4 [executed N^6]
    printf("0");
}

```

statement 1: Scope of 'i' is permeating throughout all three loops that is, once 'i' is incremented, its value is stored and fetched from same memory location by all three loops.

statement 2: 'i' is initialized to 1, checked for the condition (i\<= $n^2$) and control moves to 3rd statement.

statement 3: again 'i' is assigned value= 1, checked for condition (i\<= $n^4$) and control moves to 4th statement.

statement 4: again 'i' is assigned value= 1, checked for condition (i\<= $n^6$) and looped till (i\<= $n^6$) fails to match \[i.e. i\> $n^6$ and condition fails.\]

Execution control is transferred to statement 3 where 'i' is incremented (i++) and checked for the condition again. As soon as it checks the condition, condition fails to meet because now value of 'i' = last value of 'i' + 1. So, it exits the middle loop.

So, execution control moves to statement 2 where again 'i' is incremented (i++) and checked for the condition again. But here again value of i is greater than $n^2$. Control exits the loop.

You can deduce that Big-Oh for your piece of code is $O\left(n^{6}\right)$ and not $O\left(n^{48}\right)$ because your loop actually iterated $n^6$ + 2 + 2 + 1 = $n^6$ + 5 = $O\left(n^{6}\right)$.

So, your printf statement will run $O\left(n^{6}\right)$ times.
> -1 votes

# Answer
***tl;dr*-** It's $O\left(n^{6}\right)$ because it's basically just the inner loop. However, if it weren't for the confusing code construction, it'd have been $O\left(n^{12}\right)$ instead of $O\left(n^{48}\right)$ since nested loops multiply the complexity of their body, leading to $n^2{\times}n^4{\times}n^6=n^{\left(2+4+6\right)}=n^{12}$.

---

The inner-most loop, `for(i=1; i<= n^6; i++)`, should terminate when `i==n^6+1`. After that, the other two loops will check for termination against `i==n^6+1`, ending both immediately. So, the first two `for` loops can basically be ignored.

However, let's say that it wasn't a trick question and the code were

```
                                                                 //  Called:
void foo(int n)                                                  //  1 time
{
  for(int i = 0; i < n^2; i++)                                   //  1 time
    for(int j = 0; j < n^4; j++)                                 //  n^2 times
      for(int k = 0; k < n^6; k++)                               //  n^6 times
        printf("0");                                             //  n^12 times
}

```

. In this case, it'd have been $O\left(n^{12}\right)$, not $O\left(n^{48}\right)$.

This can be seen by rewriting it with single-`n` loops:

```
                                                                 //  Called:
void foo(int n)                                                  //  1 time
{
  //  Two effective n loops for "for(int i = 0; i < n^2; i++)":
  for(int i_0 = 0; i_0 < n; i_0++)                               //  1 time
    for(int i_1 = 0; i_1 < n; i_1++)                             //  n times

      //  Four effective n loops for "for(int j = 0; j < n^4; j++)":
      for(int i_2 = 0; i_2 < n; i_2++)                           //  n^2 times
        for(int i_3 = 0; i_3 < n; i_3++)                         //  n^3 times
          for(int i_4 = 0; i_4 < n; i_4++)                       //  n^4 times
            for(int i_5 = 0; i_5 < n; i_5++)                     //  n^5 times

              //  Six effective n loops for "for(int k = 0; k < n^6; k++)":
              for(int i_6 = 0; i_6 < n; i_6++)                   //  n^6 times
                for(int i_7 = 0; i_7 < n; i_7++)                 //  n^7 times
                  for(int i_8 = 0; i_8 < n; i_8++)               //  n^8 times
                    for(int i_9 = 0; i_9 < n; i_9++)             //  n^9 times
                      for(int i_10 = 0; i_10 < n; i_10++)        //  n^10 times
                        for(int i_11 = 0; i_11 < n; i_11++)      //  n^11 times

                          //  The inner-most loop body:
                          printf("0");                           //  n^12 times
}

```
> 2 votes

# Answer
The most effective loop in the given problem $O(n^6)$. Variable '$i$' change the way all the three loops work in tandem. The first and second (middle) loops will not execute the way they normally they do and that is because of variable '$i$'. Also, the code is neither pseudo code or working program.
> 0 votes

---
Tags: algorithm-analysis
---


# Question
Title: Cover $n$ points in the plane with $k$ circles of radius $1$
I am studying for an algorithms exam and ran into this example problem.

> A circular disk with radius $2r$ can be covered by $7$ circular disks with radius $r$; in the following you can use this statement without proof.
>
> Suppose that we are given a set $S$ of $n$ points in the plane, and we want to cover all points in $S$ by a minimum number of circular disks of radius $1$. Let $k$ be the optimal number of disks needed. Propose a polynomial time algorithm to produce a covering with at most $7k$ circular disks of radius $1$.

I do understand the question but I have no idea where to begin or how to approach this. Should a reduction be used? Or is there a simple and obvious answer? How do you cover $n$ points that you know nothing about? Maybe calculate the distances between them?

I do realize that if the distance between all points is greater than $2$ units, then $k = n$ since every circle of radius $2$ can only cover a single point.

I mainly want to understand the problem so that I can attempt a solution on my own, but a solution to the problem would also be nice, so that I can check my answer later.

# Answer
> 2 votes
Use a greedy algorithm to cover your points with circular disks of radius 2. In other words, repeatedly choose an uncovered point, and cover it with a circular disk of radius 2 centered at the point. Now cover each of your disks with seven disks of radius 1.

Why does this work? Suppose that you covered the points using $k$ circular disks of radius 2 centered at the points $p\_1,\ldots,p\_k$. It is not hard to check that the distance between any two different points $p\_i,p\_j$ is larger than 2 (otherwise $p\_j$ would have been covered by the disk around $p\_i$, assuming $i \< j$), and so no circular disk of radius 1 can cover both $p\_i$ and $p\_j$. This implies that $k$ circular disks of radius 1 are needed to cover the points $p\_1,\ldots,p\_k$, and so at least $k$ are needed to cover the original set of points. The solution produced by the algorithm uses $7k$ circular disks.

---
Tags: algorithms, computational-geometry
---


title: R.E or non R.E?

text:
# Question
Title: R.E or non R.E?
$L\_1= \\{ \langle M \rangle \mid L(M) \text{ is strings of length between } 1 \text{ and } 5 \\}$.

$L\_2 = \\{ \langle M \rangle \mid L(M) \text{ is strings of length at most } 5\\}$.

I am able to figure out that both languages are undecidable as we can have $TM\_{yes}$ and $TM\_{no}$ and as per Rice's theorem it's undecidable . But I am having difficulty in proving whether the language is R.E or non R.E .

Can someone please help me?

# Answer
> 1 votes
Hint: both $\overline{L}\_1$ and $\overline{L}\_2$ are recursively enumerable. For example, to show that $\overline{L}\_1$ is r.e., given $\langle M \rangle$ use dovetailing until you find a string $w$ accepted by $M$ and having length $0$ or greater than $5$. If such string is found, then accept $\langle M \rangle$. This means that if both $L\_1$ and $L\_2$ are not recursive (as you claim) then $L\_1$ and $L\_2$ cannot be r.e., since this would imply that $L\_1$ and $L\_2$ are recursive.

---
Tags: turing-machines, computability
---


title: Is given point covered by any circle?

text:
# Question
Title: Is given point covered by any circle?
Given $N$ circles and $Q$ points. What is the optimal solution for checking "if point is covered by any circle" for every point? The trivial solution would be $O(QN)$.

# Answer
Let's suppose you have a spatial data structure that can be built over a set $S$ of points on the plane and expose the functions.

```
Build(S): Build and return the data structure storing all points in S
ds.Delete(q): Deletes point q from the set S
ds.Search(p): Return the closest point in S to point p

```

Now let's solve the problem backwards, instead of finding if a point is contained by some circle, lets find points for each circle the points it contains.

```
C: Set of circles
P: Set of points
ds := Build(P) # Build the data structure using points to be queried

for each circle c in C:
   do
      p = ds.Search(c.center)
      if p is inside circle c:
          ds.Delete(p)
   while (ds is not empty and one point was deleted)

```

All the deleted points from the data structure are the points that belongs to at least one circle, remaining points are not contained in any circle, otherwise they were being found when processing such circle.

Let $N:=|C|$ and $Q:=|P|$

The overall complexity of this algorithm is $$O(Build(Q) + (N + Q) \cdot Search(Q) + Q \cdot Delete(Q))$$

Here $Build(Q)$ is the complexity of building the set of $Q$ points, $Search(Q)$ is the complexity of searching for a point in a set of at most $Q$ points and $Delete(Q)$ is the complexity of deleting a point in a set of at most $Q$ points.

Notice that this cost is amortized, since after a point is recognized to be inside a circle it is deleted from the set.

One data structure that provides good balance for this operations is kd-tree, but I encourage you to find other spatial data structures that provides better complexity for your case.
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Is my lambda calculus reduction correct and final form valid in simply typed lambda calc?
I'm looking at some lambda calculus at the moment and came across this question:

0:R

1:R

plus: R-\>R-\>R

(lambda f:T . lambda g:U . (f 0) (g 0)) (plus 1) (plus (plus 1 1))

Is it well typed given appropriate types for T and U?

I'm new to lambda calc but I gather that we substitute (plus 1) for f and (plus (plus 1 1)) for g.

This will reduce to
(plus 1 0) (plus (plus 1 1) 0) The right hand side (plus 1 1) will reduce to an R and then we will have (plus R 0) which will reduce to an R. The left side will reduce to an R so the whole expression reduces to the form R R.

Is this correct? Then f and g are of type R -\> R (from currying) to make it valid. Is it an issue that the final expression will be of the form *R R*. Does this mean R gets applied to R then, so R would have to be an 'automorphic' function (mapping from a type to the same type)... is this something related to not having recursion in simply typed lambda calc?

# Answer
> 0 votes
While your way of calculating the types isn't quite how it works, it gives the right answer here. As you say, you end up with `f 0` having type `R` and `g 0` having type `R`. Since we apply `f 0` to `g 0`, `R` must be of the form `R -> X` for some `X`. In other words, you have the equi-recursive type `R = R -> X`. Such types are almost always disallowed. Thus, this would be a type error. If `R` is a fixed primitive type, e.g. a type of primitive natural numbers, then it is simply not the case that `R = R -> X` and so you would also get a type error.

---
Tags: lambda-calculus
---


# Question
Title: What is the role of Numerical Gradient Computation in Backpropagation algorithm?
I was listening CS231n (2017) lectures and noted that there is a lot of attention to Numerical Gradient Computation (NGC). It starts @5:53 in this video and appears a few times later.

Also, looking at the batch normalization materials (example), I found a lot of attention drawn to exactly the same topic (well, probably because it is the same backpropagation...).

As I understood, gradients we use in various optimization methods (vanilla SGD, Adam) require us to know activation function derivative. I suppose, if the activation function is complex or we are lazy enough to take derivative analytically, we need to compute gradient numerically and that is where we use NGC.

**Questions:**

1. Is that the only purpose of NGC in backpropagation?
2. Isn't it faster to use analytically form of the activation function derivative to calculate gradients?

# Answer
The purpose is *pure educational*. Students that jump straight to mid- or high-level libraries like tensorflow, keras, theano, etc don't have to compute the gradients themselves. On the one hand, it saves a lot of time, but on the other hand, it is makes it very easy to abstract away the learning process.

Here's how Andrej Karpathy puts it (the lecturer of the previous cs231n classes at Stanford):

> When we offered CS231n (Deep Learning class) at Stanford, we intentionally designed the programming assignments to include explicit calculations involved in backpropagation on the lowest level. The students had to implement the forward and the backward pass of each layer in raw numpy. Inevitably, some students complained on the class message boards:
>
> “Why do we have to write the backward pass when frameworks in the real world, such as TensorFlow, compute them for you automatically?”
>
> ...
>
> **The problem with Backpropagation is that it is a leaky abstraction.**
>
> In other words, it is easy to fall into the trap of abstracting away the learning process — believing that you can simply stack arbitrary layers together and backprop will “magically make them work” on your data.

I recommend to read the whole post, it's very interesting.

So, you try to compute gradients manually. And when you do that you find that it's pretty hard to assess if the code is right: it's just a raw formula that takes a bunch of floating numbers and returns another bunch of floating numbers. And here you find the alternative numerical method that you can compare to very useful.

Of course, analytical formulas are faster and more precise and they are used in practice whenever possible. But while studying neural networks and back-propagation, it's very useful to get through manual computation at least once. Besides, it sometimes helps to find the bugs.
> 4 votes

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