# Question
Title: Mathematical Induction Problem from Concrete Abstractions
This is a problem from 'Concrete Abstractions' which is available free on the web\[1\]. It's a book similar to SICP. The problem:

> Exercise 2.16 Consider the following procedure foo:

```
(define foo
  (lambda (x n)
    (if (= n 0)
        1
        (+ (expt x n) (foo x (- n 1))))))

```

> Use induction to prove that `(foo x n)` terminates with the value $$\frac{x^{n + 1} - 1 } {x - 1}$$
>
> for all values of x != 1 and for all integers n \>= 0. You may assume that `expt` works correctly, (i.e., `(expt b m)` returns $b^m$). Hint: The inductive step will involve some algebra.

I've watched a video on induction on Khan Academy and read the induction material in the book, but I can't connect the dots to solve this problem.

Edit: I am stuck at the Inductive step. My work: Base Case:

```
(foo x 0)
(if (= n 0)
    1)

```

returns $1$ and

$\frac{x^{0+1} - 1} {x - 1} = \frac{x - 1}{x - 1} = 1$

So for the inductive hypothesis: Assume `(foo x k)` terminates in $\frac{x^{k+1} - 1}{x - 1}$ for all $k \geq 0$. Then for $k+1$: I essentially add $k+1$ for the assumed formula above, so: $\frac{x^{k+1} - 1}{x - 1} + k+1$. What I get is a long equation that I have no idea what to do with.

# Answer
> 3 votes
Your induction step is recorded incorrectly.

You wrote:

$$\frac{x^{k+1} - 1}{x - 1} + k+1$$

You should have written:

$$\frac{x^{k+1} - 1}{x - 1} + x^{k+1}$$

Basically, you are proving the formula for the sum of the geometric sequence.

---
Tags: induction, lisp
---


# Question
Title: Approximation algorithms for Euclidean Traveling Salesman
I am trying to find a way to solve Euclidean TSP in a polynomial time. I looked at some papers but I couldn't decide which one is better. What is the general approximation algorithm for solving this problem in polynomial time?

# Answer
Euclidean TSP is not even known to be in $NP$, basically because it seems that even to verify if there is a hamiltonian cycle of length at most $k$, we need to computing the sum of square roots. But the problem "$\sum\_{i}\sqrt{a\_i}\<k?$" is not known to be in $NP$.

Anyway Euclidean TSP has $PTAS$.
> 2 votes

---
Tags: algorithms, reference-request, approximation, traveling-salesman
---


# Question
Title: Using diagonal argument to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension
Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ whenever $H(x)$ is defined, then $BIG(x)$ is not computable. This is a homework question so I don't want a full solution just some help!

$\bf{NOTE}:$ The predicate $T(y,x,z)$ means that it holds iff program $y$ takes an input $x$ (could be $n$-ary) and has a computational history z! This is supposed to be the Kleene T predicate basically.

The function $H(x)$ I believe returns the smallest computational history $y$ such that a program $\\{x\\}(x)$ (program takes input of its own configuration and runs) runs and halts, since $\mu y R(x,y)$ means the smallest $y$ such that $R(x,y)$ holds. Maybe I am not quite clear what it means for $BIG$ to agree with $H(x)$ or what it's own input. I think I need to create a diagonal function that uses $BIG$ if $BIG$ was computable and show that if I had some program $e$ then it must agree with $BIG$ but based on my definition of that diagonal function it isn't. If you are reading this you might see the mess of my thinking, any help would be greatly appreciated!

# Answer
> 1 votes
(This answer assumes my conjectural interpretation of the predicate $T$.) The function $H(x)$ is given by $$ H(x) = \begin{cases} t & \text{if program $x$ run on input $x$ halts after $t$ steps} \\ \bot & \text{if program $x$ never halts when run on input $x$} \end{cases} $$

Hint: Given a total computable function extending $H$, show how to solve the halting problem. There is no need to use diagonalization – this is already taken care of in the proof that the halting problem is undecidable.

---
Tags: computability, mu-calculus
---


# Question
Title: Can a computer game can run on a boot mode without the aid of os?
I meant that that the game programmer can just add its own code to the game to manipulate its own low level function as the operating system does provide in a common executables,and load it into the boot mode using its own bootstrap

# Answer
> 1 votes
Yes, it is possible to boot computer to the specially designed program, which will be some game. But this will be harder, because there will be no drivers for advanced hardware, only elementary BIOS functions, basic video memory access. For example, if author want to add sound to the game, he can used PC speaker, or write own driver for ... for which card? Sound blaster, or RTL? What if user has another card? Same problem for video: game may know about some Radeon and will not work on older or newer AMD card or on Nvidia or Intel.

So, writing a bootable computer game is the same as writing both the game and the Operating System with drivers (or stealing its codes like in PS4's Orbis OS with FreeBSD sources or SteamOS with linux sources).

---
Tags: operating-systems
---


title: ARQ Protocols and sequence numbers

text:
# Question
Title: ARQ Protocols and sequence numbers
What will happen if sequence number is not used in an ARQ protocol (e.g, Go-back-N, selective repeat)?

# Answer
> 1 votes
You're basically asking "what happens when a critical part of the ARQ protocol is missing?" To name a few consequences: it wouldn't know when to stop ACK'ing incoming packets, or know if they are coming in the right order, or know if all of them got there.

---
Tags: efficiency, computer-networks
---


# Question
Title: Examples of algorithms that have runtime O(N + M) resp O(NM)
I'm looking for examples of loops that have running time $O(nm)$, $O(n+m)$ and $O(n\log m)$ to help me understand these concepts. Could anybody give some examples and explain why they have the given running time?

# Answer
The following fragment sets `t` to a value that is $O(nm)$ (actually, it's equal to $mn$). the outer loop executes $n$ times and, each of those times, the inner loop executes $m$ times.

```
t = 0;
for i=1 to n do
    for j=1 to m do
        t = t+1;

```

The following fragment runs the first loop $n$ times and then runs the second loop $m$ more times, for a total of $n+m$ (which is a trivial example of $O(n+m)$).

```
t = 0;
for i = 1 to n do
    t = t+1;
for i = 1 to m do
    t = t+1;

```

Finally, this fragment runs the outer loop $n$ times. Each time, `p` is set to $m$ and then halved until it reaches 1. This answers the question "How many times do I have to multiply 1 by 2 to get something bigger than $m$, which is $\log\_2 m$. So the value of $t$ is $O(n\log m)$. (We don't need to worry about the base of the logarithm, since $\log\_a m = k\log\_b m$ for some constant $k$, which all gets lost in the $O(-)$.)

```
t = 0;
for i = 1 to n do
    p = m;
    while (p > 1) do
        p = p/2;
        t = t+1;

```

---

The code fragments here are similar to the ones that appeared in the original version of the question. I removed them from the question, since questions that contain answers aren't well-suited to this site.
> 6 votes

---
Tags: algorithms, algorithm-analysis, asymptotics
---


title: how to represent Sparse Matrices

text:
# Question
Title: how to represent Sparse Matrices
I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices.

Could you please suggest me some other way to store/represent sparse matrices?

# Answer
As already indicated in the comments, the wikipedia article about Sparse matrix, Band matrix, and Skyline matrix cover the topic of the question quite well. Also, the computational science stackexchange site might be a better fit for such questions in general.

One might perhaps add that band matrices can't handle low rank modifications directly, so that one might want to use the Sherman–Morrison–Woodbury formula in this case. For the other representations, it is normally more beneficial to incorporate low rank modifications directly into the matrix via additional rows and columns, see below.

---

**Some information about representations of Sparse matrices**

A general Sparse matrix can be represented as a bipartite graph. This representation is useful for applying combinatorial algorithms like the Dulmage-Mendelsohn decomposition during preprocessing. In this case however, it is likely that you actually have a matrix pencil $A+\epsilon B$, which is important to know for the combinatorial algorithm, because this indicates which elements are expected to be small. A quick'n dirty fix is to apply the combinatorial algorithm to a related block Toeplitz matrix like $\begin{bmatrix}A\\B&A\end{bmatrix}$ or $\begin{bmatrix}A\\B&A\\\&B&A\end{bmatrix}$ instead, but this is starting to get off-topic now.

If a "fixed" mapping between rows and columns is available, it makes sense to specify the symmetry type of the matrix as "general", "symmetric", "skew-symmetric" or, "Hermitian". If the symmetry type is more specialized than "general", then the matrix can be represented by a undirected graph, otherwise a directed graph can be used.

Note that these representations also apply to block-matrices (i.e. both the row indices and the column indices are partitioned into subsets), and encoding some a-priory information into such a block-structure can be a good idea both for speed and robustness.

I could also explain here how low rank modifications fit into such a general framework, but this section is already quite long. Often one can incorporate low rank modifications by just adding the corresponding row and column vectors as additional rows and columns with a small identity matrix between them. The advantage here is that the sparsity pattern of the original matrix is preserved.
> 2 votes

---
Tags: data-structures, linear-algebra
---


# Question
Title: What's the time complexity of this append method?
I made a method that appends a sequence to another sequence.

So: (append \[1,2,3\] \[4,5,6\]) = \[1,2,3,4,5,6\]

**CODE In C#**

```
IEnumerable<int> Append(IEnumerable<int> xs,IEnumerable<int> ys)
{
    using(var iteratorX = xs.GetEnumerator())
    using(var iteratorY = ys.GetEnumerator())
    {
        bool isTrueForX = false;
        bool isTrueForY = false;
        while((isTrueForX = iteratorX.MoveNext()) || (isTrueForY = iteratorY.MoveNext()))
        {
            if(isTrueForX) yield return iteratorX.Current;
            else if(isTrueForY) yield return iteratorY.Current;
        }
    }
}

```

I would like to know what is the time-complexity of this algorithm.

# Answer
> 1 votes
Your code defines the combined list implicitly by defining an iterator that iterates over list xs first and after reaching the end of that list iterates over ys.

If $T\_1(l)$ denotes the time for a single call to the iterator of list $l$, $T\_a(l)$ denotes the combined time for all calls needed to iterate ove $l$, and the combined list is called $x.y$, we find $$T\_1(x.y) = {\cal O}(\max\\{T\_1(x),T\_1(y)\\})$$ and $$T\_a(x.y) = T\_a(x)+T\_a(y).$$

The first one will typically be ${\cal O}(1)$ and the second one ${\cal O}(|x.y|)$.

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


# Question
Title: Disjoint Set - Tree Implementation with Union-By-Rank and Path Compression
Union-By-Rank and Path Compression is supposed to improve the performance of a tree implementation of a disjoint set.

However, in looking at the UNION(x, y) operation, I noticed that if x and y are actually the roots of the 2 trees being merged, no path compression actually takes place. The resulting tree would simply have a depth equal to the larger depth of the 2 trees.

Is my understanding of the algorithm correct?

# Answer
> 3 votes
I assume you are talking about Union Finddata structure. When you do UNION($x,y$), you just change the parent pointer of one of $x$ and $y$ to root of the other. The depth of resulting tree is not exactly equal to larger depth of two trees because, initially if the depth of two trees are equal, then the depth of new tree formed will be $1$ plus the old depth.

Coming to the original question, path compression takes place when we do FIND operations and not during UNION operations. When we do FIND($x$), we first find root $p$ of $x$ and for all ancestors of $x$ and also for $x$, we change the root pointer to $p$. You can see that this can reduce the height of tree drastically. After some FIND operations, next FIND operations will take time close to $O(1)$. This is formalised by saying that $n$ FIND operations take time $O(n\alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.

---
Tags: algorithms, data-structures
---


# Question
Title: Physical Meaning Behind Matrix Factorization
As we all know, Matrix Factorization is an effective method to do rating prediction jobs in recommender systems. Thanks to the work of Yahuda Koren. My question is why MF can do this job? What's the physical meaning behind it?

# Answer
> 7 votes
The idea in matrix factorization is to find the latent variables which connect the input and the output. Suppose that we are interested in a movie recommendation system, and that movies "live" on a one-dimensional axis, having romantic comedies in one end, and action movies in the other. Each "input" and "output" move can be rated in this scale (say $1$ to $-1$). Given the input movies, we can estimate a person's location $p$ on the axis (say a point in $\[-1,1\]$) by taking the inner product between the movies they saw and their "ratings" $r\_i$, i.e. $p \approx \frac{1}{n} \sum\_{i=1}^n r\_i$, where $1,\ldots,n$ are the movies seen by the person. Given the location, we can estimate how much that person will like other movies: movie $t$ will be liked by an amount proportional to $pr\_t$ (this is just a simplistic linear model).

In this example, the recommendation matrix can be decomposed as an outer product $A\_{it} = r\_i r\_t$. More generally, the situation could depend on several latent variables, and this is the general situation described by matrix factorization. The number of latent variables is the "middle" dimension in the factorization. If you have found a good factorization with only a few variables, then you have a succinct explanation of your data that could have predictive power.

# Answer
> 2 votes
a rough intuition (other than the basic data compression concept) is as follows. recommender systems that use matrix factorization methods eg SVD can be seen as a set of linear weights of natural features found via unsupervised means. a "feature" eg for a movie database is a large set of movies of varying weights. they dont necessarily have recognizable human meanings but could be given loose interpretations based on correlations with other variables associated with the subjects. such as "movies that women like, movies that men like, movies that kids like, movies that republicans like," etcetera. an individuals tastes are then represented *approximately* as a linear weighted combination of all these "factors". hence its very similar to statistics-based Factor Analysis where, roughly, causes & effects are decomposed into weighted "factors". some accounts of the Netflix contest refer to this concept.

---
Tags: machine-learning, data-mining, recommendation-systems
---


# Question
Title: Is building this tournament fixture an NP-Hard / NP-Complete problem?
I'm curious to know if this problem is NP-Hard / NP-Complete, which I believe would mean I'm unlikely to find a polynomial-time algorithm to solve it.

I have written a program which randomly generates a tournament fixture, and I call it many times to try to pack the matches into the smallest number of rounds.

When it comes to complexity theory I am still a novice, so laymen's terms would be appreciated.

**Inputs:**

* a set of countries, each of which may enter one or more entrants to the tournament (e.g. Australia might enter two entrants, UK might enter three entrants, and South Africa might enter one entrant)

**Constraints:**

* each match consists of two entrants playing against each other
* during a round, an entrant can only play in a single match
* no entrant wants to compete in a match against another entrant from the same country
* no entrant wants to compete against another entrant more than once in the tournament
* each entrant must play the exact same number of matches overall
* the number of matches each entrant must play is determined by MIN(for each entrant, total number of possible matches that satisfy the other constraints)

For example, say we have the following entrants:

* AU #1 and #2
* UK #1, #2 and #3
* SA #1

The possible matches in this (artificially small) case are:

```
AU1 v. UK1   AU1 v. UK2   AU1 v. UK3   AU1 v. SA
AU2 v. UK1   AU2 v. UK2   AU2 v. UK3   AU2 v. SA
UK1 v. SA    UK2 v. SA    UK3 v. SA

```

Since we want each entrant to play the exact same number of games, the maximum number of games per entrant is three (this can be derived from the total number of entrants (6) less the number of entrants from the largest country (3)).

Since there are six entrants in total, and there are two entrants to each match, the maximum number of courts we can utilise in a round is 3.

A sample fixture is:

```
          Court 1      Court 2      Court 3
Round 1   AU1 v. UK1   AU2 v. UK2   UK3 v. SA
Round 2   AU1 v. UK2   AU2 v. UK3   UK1 v. SA
Round 3   AU1 v. UK3   AU2 v. UK1   UK2 v. SA

```

This is a nice example because it's easy to find a solution where each entrant has played exactly 3 games each, and they all pack perfectly into 3 rounds across 3 courts. Two of the possible 11 matches have not been played, but we don't care. We sum the results from each entrant's 3 games to determine an overall ranking, which is then used to generate the finals matches.

I have other scenarios where there are more entrants and I have been unable to pack them so neatly, but by running my program many times it almost always finds a near-optimal packing where the number of rounds and unused courts is minimised.

**Output**

The first problem is if there is a polynomial-time algorithm to generate an optimal fixture.

The optimal fixture is defined by:

* minimum number of unused courts (which implies minimising the number of rounds)

The second problem is, given a fixture "A", how to determine if it is an optimal solution, i.e. is it possible to prove that there can exist no better packings for a given set of entrants. If "A" involves no unused courts in any round, then the answer for that one is clearly "Yes" - but if there are any unused courts in any round, the answer is, I think, difficult to derive.

# Answer
At first glance, even a simple solution would appear to merely be ${\cal O}(n^2)$, which is obviously polynomial time. To make the rest of my answer more readable, I'm going to define the following variables:

`numEntrants` = the total number of entrants
`largestNumEntrants` = the number of entrants from the country with the most entrants
`numRounds = numEntrants - largestNumEntrants`

For the purposes of the rest of my answer, I will assume that numEntrants is even. If it is not even, then some odd number of entrants must have a bye each round and that greatly complicates matters when trying to make sure every entrant plays the exact same number of matches.

As you correctly observed in your question statement, the largest possible number of rounds is the total number of entrants minus the number of entrants from the country with the most. We can quickly observe that `numRounds` is in ${\cal O}$(`numEntrants`). Furthermore, the number of possible matches within a round is also in $\cal O$(`numEntrants`). Specifically, it is exactly `numEntrants / 2`.

My suggested solution would then be as follows:

Arrange the entrants in an ordered list (which I'll call `entrantList`) in such an order that all of the entrants from a particular country are adjacent to each other.

```
for (int round = 0; round < numRounds; round++)
{
    for (int i = 0; i < (numEntrants / 2); i++)
    {
         Match entrantList[i] with
             entrantList[(i + largestNumEntrants + round) % numEntrants] for round.
    }
}
```

This algorithm clearly runs in $\cal O$(`numEntrants`$^2$) time and, as far as I understand them, satisfies all of your constraints, at least when `numEntrants` is even. Obviously, ${\cal O}(n^2)$ means that the problem is in P and is definitely not NP-Hard or NP-Complete.

This algorithm ensures that each entrant plays each other entrant a maximum of 1 time because it simply selects the entrant after the one it was previously matched with on each iteration. It ensures that no entrant from the same country plays another entrant from the same country because all entrants from the same country are adjacent to each other in the list and it starts with an offset of largestNumEntrants.
> 1 votes

---
Tags: complexity-theory, np-hard
---


# Question
Title: Why do I not get the correct smallest possible value in 2's complement?
When using 2's complement with 4 bits, the largest positive int I can represent is 0111. The smallest negative one is 1000.

The smallest int should intuitively be the negative of 0111 - 1 = 0110 since we can represent one more positive than negative int.

If we invert the bits of 0110 and then add 1, however, we get 1010, which differs from 1000. What am I doing wrong?

# Answer
> The smallest int should intuitively be the negative of 0111 - 1 = 0110 since we can represent one more positive than negative int.

This is incorrect. If you'd, for example, read the Wikipedia article, you'd have seen that $n$-bit two's complement can store integers between $+2^{n-1}-1$ and $-2^{n-1}$. If two's complement worked the way you proposed, you'd only be able to represent $2^n-2$ different values in an $n$-bit field, which "wastes" two possible values: this would be worse than ones' complement, which "wastes" one value by being able to represent $-0$.
> 2 votes

---
Tags: encoding-scheme, number-formats
---


# Question
Title: Checking if there are 2 elements in an array that sum to X in O(n lg n)
I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this solution is $O(n^2)$.

My solution is: Say the array is A. It's length is N. Elements are from A\[0\] to A\[N-1\]

Pseudo-Code is:

```
Check_Sum(A,left,right) {
  mid <-- floor( (left+right)/2 )

  if(A[left]+A[right]=X)
    return true

  return Check_Sum(A,left,mid)||Check_Sum(A,mid,Right)
}

```

My question is: Is the complexity of my solution equal to $O(n \lg n)$?

# Answer
Sort the array say ascending order- Takes O(nlogn)

Keep two pointers in the array say fingers. Finger f1 at the first element and finger f2 at the last element.

Sum the elements to get f1+f2: if f1+f2 == X you have found your solution else if f1+f2 \> X decrease f2 to point to the element to its left else increase f1 to point to the element to its right

This step will take O(n) making the overall cost O(nlogn)

This solution is also referred to as the finger pointing solution. Can be used in any sorted collection where you can traverse in both the direction for eg in trees.
> 9 votes

# Answer
You probably meant `if (A[left]+A[right]=X)`. Otherwise you would be comparing the same two elements over and over.

Even with this change your algorithm does not solve the problem. If e.g. $A\[1\]+A\[N-2\]=X$, it will never detect this.

Regarding complexity, your algorithm satisfies the recurrence $$T(N) = 2\cdot T\left(\frac N2\right) + 1.$$ Using the Master theorem, we find that the solution to this recurrence is in $\Theta(n) \subset \cal O(n \log n)$.
> 2 votes

# Answer
You can also use Balanced Binary Trees(BBT) for this. When you see the first $i$ elements of input, put them in BBT. Let the tree be called $T$. When you get $(i+1)$th element with value $y$, search $T$ for the element $X-y$. If present, report that there exist two elements with the given property. If not, put the $(i+1)$th element in tree and continue the process. If you don't find a pair that satisfies the given property even after inserting all $n$ elements, we can say that there is no such pair in the array with the given property.
> 2 votes

# Answer
Hint: Sort the array.

(This is always a good idea when you're aiming at $O(n\log n)$.)
> 1 votes

# Answer
Call the array A. A linear time algorithm exists if $\max A = \mathcal O(n)$.

```
insert the elements of A into a set S.
for every element a in A:
    if S contains x - a:
        return the pair (a, x - a)

```

This assumes that the set data structure's 'insert' and 'contains' run in constant time. One such data structure is *the bit array*.

Different data structures yield different running times. If S is a *red-black tree*, both the first line and the for loop take $\mathcal O(n \log n)$ and you get your bound.
> 1 votes

# Answer
All elements are assuming positive. If negative numbers exist, we can convert them to positives by adding the smallest number.

**Solution One:** Do an in-place merge sort on the array `A`. Loop through each item `A[i]`, use a binary search to check if `K-A[i]` is in the array. If found, return the pair `(A[i], K-A[i])`; else, return null;

Time complexity is $O(n \log n )$; Space complexity $O(1)$.

**Solution Two:** Allocate an array `m` of size `K`. Find the first element in the array `A[s]` that is less than `K`, and set `m[A[s]]=1`. Loop through each remaining item `A[i]`, check to see if `m[K-A[i]] == 1`. If `m[K-A[i]] == 1`, return the pair `(A[i], K-A[i])`; else return null in the end.

Time Complexity: $O(n)$ Space Complexity: $O(K)$

Here is the implementation details:

http://stones333.blogspot.com/2014/03/given-number-k-and-array-of-positive.html
> -2 votes

# Answer
Easiest solution:

* Put all elements in a hash map -\> O(n) to O(n^2) depending on has function
* Iterate through list doing a lookup for (Sum - A\[i\]) -\> O(n) with O(1) lookups
* If Sum is 2x A\[i\], check for second instance value in the map

Solution in O(n) to O(n^2) depending on has function
> -3 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, arrays
---


# Question
Title: Problem in finding the floating point representation?
So, i was trying:

$(-10.75)\_{10}$ and to convert it into 32 bit binary floating point representation.

i did this:
According to IEEE standard: $(-1)^{-s} * 1.M * 2^{E-bias} $

```
 sign bit= 1 bit
 exponent= 8 bits
 mantissa= 23 bits

```

bias= $2^{n-1}-1 = 127$

```
  - 10   . 75
  ⇓  ⇓      ⇓
= 1 1010 . 11
= 1 1.01011 x 2^-3
= 1 1.01011 x 2^(124-127)
= 1 01111100 0101100 0000 0000 0000 0000   = 32 bits
  ⇓ ________ ____________________________
  ⇓    ⇓                  ⇓
 sign  Exponent         Mantissa

```

But the answer presented is:

```
  - 10   . 75
  ⇓  ⇓      ⇓
= 1 1010 . 11
= 1 1.101011 x 2^-4
      -------> why this happened, and why is 1 before '.'
= 1 1.101011 x 2^(123-127)
= 1 01111011 1010110 0000 0000 0000 0000   = 32 bits
  ⇓ ________ ____________________________
  ⇓    ⇓                  ⇓
 sign  Exponent         Mantissa

```

If i am wrong, where is it and please explain why.. Any help is appreciated.

# Answer
> 4 votes
Both answers seem wrong to me. A quick conversion in C++:

```
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>

int main (void)
{
    float x = -10.75;
    uint32_t* p = (uint32_t*)&x;
    printf("%x\n",*p);

    return 0;
}

```

Gives the output: `c12c0000`

Which is `1 10000010 010110000…`

Your mantissa calculation is the correct one, but the binary exponent is +3, not -3 (that is, your number is greater than 1, not less than 1). In bias-127, that exponent becomes 130 (decimal).

# Answer
> 2 votes
```
  - 10   . 75
  ⇓  ⇓      ⇓
= 1 1010 . 11                              (1)
= 1 1.01011 x 2^3                          (2)
= 1 10000010 0101100 0000 0000 0000 0000   (3)
  ⇓ ________ ____________________________
  ⇓    ⇓                  ⇓
 sign  Exponent         Mantissa

```

(1):

* sign is -, so first bit is 1.
* 10 converted to binary is 1010
* 0.75 converted to binary is 0.11

(2):

* signbit is still 1
* 1010.11 x 2^0 = 1.01011 x 2^3

(3):

* signbit is still 1
* exponent is 3, bias is 127, so we convert 127+3=130 as 10000010
* we copy everything after the decimal point into the mantissa and padd with 0's.

As to your questions

> why this happened, and why is 1 before '.'

* No idea why it says exponent -4, clearly it has to be 3.
* In scientific notation there is always exactly one digit in front of the decimal point and it is never a 0. So in binary decimal notation there is always a 1 in front of the decimal point. And just because there is always a 1, we don't need to include that in our representation. That's why the mantissa only consists of the part after the decimal point.

---
Tags: computer-architecture, floating-point
---


# Question
Title: How to tell which value belongs to the key during hashing
To prevent collisions in Hash table , seperate chaining with linked list is used . Hash table works by hashing the key and storing the value in the bucket.

Assuming 4 keys hash to the same bucket , and the bucket has a linked list which has 4 nodes , how would we know which value belong to the key when we try to search for the value of the key .

For eg : These 4 key-value :**a:4** , **b:3** , **c:2** , **d:1** , hash to bucket 23. At bucket 23 , there is a linked list of values : **4 , 3 , 2 , 1** , how would we know which values belong to which key

# Answer
> 4 votes
You don't just store the values, you store them along with the keys. So when you search for a key in the linked list you traverse through the list and look for the key you want.

---
Tags: hash-tables, linked-lists
---


# Question
Title: How many times can you divide a list of n elements in 1/2
I am trying to wrap my head around recursion and divide and conquer algorithms. Can someone provide a proof and explanation of how many times a list of n elements can be divided in 1/2 on both sides.. In other words the total number of half divisions in a recursive divide procedure on a list of size n.

# Answer
> 1 votes
Lets assume that the base case in the recursive division procedure is a list of only 1 element.

You mentioned that division is done on both sides. So it turns out that there is no need to think in terms of recursive division. This is because no matter what the procedure is, you end up sub-dividing until there is only 1 element.

So a similar question will be: how many times can we divide a list of n elements into its single elements? Well we do this every day, and we do this **n-1** times!

# Answer
> 2 votes
You haven't explained what "divide in half" means, but let's assume that it means to divide the list into two halves of as equal size as possible (equal if the number of elements is even, almost equal if it's odd).

You can draw recursive "division in half" as a tree. The root is labelled by the original number of vertices, $n$. A node labelled $1$ is a leaf. Any other node labelled $m \> 2$ has two children labelled $\lfloor m/2 \rfloor$ and $\lceil m/2 \rceil$ (this is the "division in half"). As yemelitc shows in their answer, the number of leaves is $n-1$; this is irrespective of the division being "in half". On the other hand, the *depth* of the tree (number of edges in longest path from root to leaf) is $\lceil \log\_2 n \rceil$. You can try to prove this in the case where $n = 2^k$ (you can use induction on $k$).

---
Tags: recurrence-relation, recursion, divide-and-conquer
---


# Question
Title: Solve the recurrence $f(n+1)=f(n)^2,\, f(0)=2$
I have a problem with an exercise asking me to solve the following recurrence: $$f(n+1)=f(n)^2, \quad f(0)=2$$ Can someone explain how to solve this? I tried but couldn't.

# Answer
$f(n) = 2^{2^n}$ will solve the recurrence.

* $f(0) = 2^1 = 2$
* $ f(n+1) = 2^{2^{n+1}} = 2^{2\cdot 2^n} = \left(2^{2^n}\right)^{2} = f(n)^2 $
> 3 votes

# Answer
Hint, Consider the function $g(n) = \log\_2 f(n)$
> 4 votes

# Answer
We are given $f(n+1) = f(n)^2$. Now, recursively write $f(n)$ also in the given form. So, if we write it recursively we get the following equations$$f(n+1)=f(n)^2$$ $$f(n)=f(n-1)^2$$ So, using above two equations, $$f(n+1)=f(n-1)^4$$ This doesn't seem to give any hint (If you see any pattern here, great). So, expand more. $$f(n-1) = f(n-2)^2$$ Putting it again in the equation gives, $$f(n+1) = (f(n-2)^2)^4 = f(n-2)^8$$ Now, the patterns becomes clear. For each value you subtract from $n$, power of the function value multiplies by 2. So, we can generalize saying $$f(n+1)=f(n+1-x)^{2^x}$$ We have not yet made use of the base case given. We know $f(0) = 2$. So, put $x=n+1$. We get $$f(n+1) = 2^{2^{(n+1)}}$$ Finally, we get our answer $f(n) = 2^{2^n}$.

This is basically what Priyatham has said, but there is also a way of making guesses. It's not left entirely to your luck
> 3 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Neural network: noisy temporal sequence converter (transducer?producer?) on demand?
I start to suspect this problem is very hard now that I cannot find a single relevant literature on the subject, but it's too late to change the class project topics now, so I hope any pointers to a solution. Please pardon the somewhat artificial scenerio of this question, but here goes:

Technical version:

Let $\Sigma\_{c}$ and $\Sigma\_{q}$ and $\Sigma\_{a}$ be 3 disjoint finite alphabet (c, q, a stand for content, query and answer respectively). Let $L\_{c}\in\Sigma\_{c}^{\*}$ and $L\_{q}\in\Sigma\_{q}^{\*}$ be FINITE languages, wherein $L\_{q}$ have the property that for every string in the language all of its prefix are in the language too. There is an unknown function $f:L\_{c}\times L\_{q}\rightarrow\Sigma\_{a}^{\*}$. Consider a mysterious machine that receive continuous stream of symbol through a channel one at a time step (we assume that the symbol are clearly distinguishable). This machine, whenever being feed with a string in $c\in L\_{c}$ (with the symbol in correct temporal order) followed by a string in $q\in L\_{q}$ will output (through a different output channel) the value of $f(c,q)$ as a temporal sequence, one symbol at a time. Note that the machine always output after every new symbol from $\Sigma\_{q}$. Note that the empty string is in $L\_{q}$, which means the machine also output something before any symbol on $\Sigma\_{q}$ have arrived, but only if it is certain with high probability that the full string in $L\_{c}$ have been received.

The objective is to construct a neural network that emulate that mysterious machine, if we have only access to its input and output channel to use as training data, and we do not know $f$. We also have to assume that the input channel are noisy in the following sense: random noise are inserted into the input channel at high probability, delaying input symbol, and we initially do not know which one is noise and which one is authentic; also symbol in the input channel are sometimes lost at low probability. EDIT: Note: we do not know $L\_{c}$ nor $L\_{q}$, only the mysterious machine know, in fact we do not even know the alphabet $\Sigma\_{c}$ and $\Sigma\_{q}$ other than the fact that they are disjoint and are subset of the set of all possible input symbol (input symbol not in either set are certainly noise, but we can't tell which set it belongs to initially; note that it is still possible for symbol from the alphabet to be noise).

(why neural network: beside the noise problem, also because that's what I wrote in my class project proposal)

(layman version: consider Sherlock Holmes sitting in his chair, bored. Dr. Watson give a short description of the client. Once he's done, Sherlock Holmes give a conclusion about the client. Dr. Watson is astonished, and ask more question, and Sherlock Holmes reply. The conclusion must obviously based on the description alone; and subsequent answer have to answer the question being asked, taking into account the contexts which consists of question already being asked (for example, the same "How did you know?" following "Age?" demands different answer than when following "Height?"). Now you want to make a neural network that simulate Sherlock Holmes, having all the recordings of those session. Dr. Watson however tend to insert in long description that are rather irrelevant, making long statement before finally getting around to ask question, and sometimes accidentally omit crucial information, but otherwise describe people in a rather fixed order of details. The neural network must be able to deal with that. Of course, this is a just a layman's description, the situation is much less complex.)

I have looked through various relevant literature, and I cannot find anything relevant. Conversion to spatial domain is useless due to high amount of noise causing very long input sequence. I have looked into LSTM to deal with the memory problem over arbitrary long time lag, but I for the life of me cannot figure out how is the network is supposed to be trained when there are arbitrarily long noise insertion everywhere or possibilities of missing symbol (every method I found seems to force a fixed time-lag between input and output, and missing symbol immediately wreck any method based on predicting the next item in the sequence). Also, is it too much to ask for network that isn't too hard to code? Integrate-and-fire neuron is even worse than LSTM in term of difficulty in coding.

Thanks for your help. It's due in 2 days, so please be fast.

# Answer
> 2 votes
I unfortunately know very little of neural network. The closest thing that your project reminds me of is speech recognition, and I would look at that literature. I am thinking of the first stage of speech recognition, when the sound stream is transformed into a word lattice (or a word stream, if you keep only the most likely path in the lattice). But all I know on this is based on Hidden Markov Models and Viterbi algorithm \[1\]. I have not looked at the field for a long time, and I have no idea how it would translate in neural network, but I would suggest you look at that literature, for example by searching the web for *neural networks* and *speech recognition*.

I doubt you can code anything serious in 2 days. I would not even try, but I do not know what kind of programming is expected. But maybe a good description of what should be done, with appropriate references would be enough.

You should simplify your question, if you find out that your requirements are too strong, particularly on noise. At first, you should limit yourself to very simple kinds of noise. Problems are seldom solved the first time in full complexity. You first solve simple cases, then try to see where you could do more. For one thing, do you know how to do it without any noise? What are the limitations? Then you can start adding simple noise, and see what changes.

Your input, content and query, do not seem to have much reason to be distinguished, or do you have a strong reason to distinguish them? I would think that at some point your system must enter a state when it starts answering on the output tape.

\[1\] Bahl, L. R.,Jelinek, F., & Mercer,R.L. (1983).A maximum likelihood approach tocontinuous speech recognition. IEEETrans. Pattern Anal. Machine Intell., PAMI 5, 179-190.

These authors actually published several papers on the subject for noisy input, including insertion, deletion and substitution of symbols. There are surely others, and this work is quite old. I am not sure the paper referenced is actually about learning. But the same people worked on learning too, such as parameters identification for Hidden Markov Models.

---
Tags: formal-languages, neural-networks
---


# Question
Title: Why does merge sort run in $O(n^2)$ time?
I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that **Big O is the upper bound** running time/space of the algorithm, **Big Omega is the lower bound** running time/space of the algorithm and **Big Theta is like the in between of the two**.

This particular answer on SO stumbled me with the following statement

> For example, merge sort worst case is both ${\cal O}(n\log n$) and $\Omega(n\log n)$ - and thus is also $\Theta(n\log n)$, but it is also ${\cal O}(n^2)$, since $n^2$ is asymptotically "bigger" than it. However, it is NOT $\Theta(n^2)$, Since the algorithm is not $\Omega(n^2)$

I thought merge sort is ${\cal O}(n\log n)$ but it seems it is also ${\cal O}(n^2)$ because $n^2$ is asymptotically bigger than it. Can someone explain this to me?

# Answer
> 8 votes
This is actually a mathematical matter and not the matter of the worst case running time. First you have to know that Big O does not represent worst case running time of some algorithms. Big O comes from mathematics and it represents an asymptotic upper bound for some mathematical functions.

You can see that the graph of $n^2$ is always above the graph of $n\log n$. so you can say $n^2$ is an upper bound on $n\log n$ as the value of $n\log n$ is always less than $n^2$. So mathematically you can say $n\log n=O(n^2)$. Similarly graphs of all $n^i$ for $i\geq 2$ are always above the graph of $n\log n$. So you can say $n\log n$ is also $O(n^3),O(n^4),O(n^5),\ldots$

But one thing you have to remember that though $n\log n$ is $O(n^2)$ but $n\log n$ is not $\Theta(n^2)$, because $n\log n$ is not $\Omega(n^2)$. Mathematically you can say $n\log n$ is $o(n^2)$.

If you still have any confusion regarding my answer, you can ask me here.

# Answer
> 3 votes
Let's consider a simpler situation. For numbers $x,y$, say that $x = S(y)$ if $x \leq y$, that $x = L(y)$ if $x \geq y$, and that $x = E(y)$ if both $x = S(y)$ and $x = L(y)$. Since $1 = S(1)$ and $1 = L(1)$, it is the case that $1 = E(1)$. But it is also the case that $1 = S(2)$.

The situation with running times is similar. Given two positive functions $f,g$, we say that $f = O(g)$ if $f(n) \leq Cg(n)$ for some $C \> 0$ (independent of $n$), that $f = \Omega(g)$ if $f(n) \geq cg(n)$ for some $c \> 0$, and that $f = \Theta(G)$ if $f = O(g)$ and $f = \Omega(g)$. For example $2n = O(n)$ since $2n \leq 2 \cdot n$ and $2n = \Omega(n)$ since $2n \geq n$, and so $2n = \Theta(n)$. It is also the case that $2n = O(n^2)$ since $2n \leq 2\cdot n^2$.

For numbers we have the important property of transitivity: $x \leq y \leq z$ implies $x \leq z$. The same relation holds for functions: if $f = O(g)$ and $g = O(h)$ then $f = O(h)$; indeed, if $f \leq C\_1 g$ and $g \leq C\_2 h$ then $f \leq C\_1C\_2 h$. The running time of merge sort $T(n)$ is $\Theta(n\log n)$, and $n\log n = O(n^2)$, and so $T(n) = O(n^2)$, but $T(n)$ is not $\Omega(n^2)$ and so $T(n)$ is not $\Theta(n^2)$. The class $\Theta(n\log n)$ is a *tight* bound on $T(n)$; $O(n^2)$ is an upper bound which is not tight.

# Answer
> 1 votes
Intuitively, $f=\cal O(g)$ means that $f$ *grows no faster* than $g$. Clearly, $n \log n$ grows no faster than $n^2$ and we can write $n \log n = \cal O(n^2)$. Symmetrically, $f=\cal \Omega(g)$ means that $f$ *grows at least as fast* as $g$. $n \log n$ does not grow at least as fast as $n^2$ so we have the inequality $n \log n \neq \cal \Omega (n^2)$. When $f$ grows no faster than $g$ and at least as fast as $g$, it makes sense to say that $f$ grows as fast as $g$; write $f=\cal \Theta(g)$.

To answer your question, notice that *grows no faster than* is *transitive*. For numbers $x,y,z$ we all know that if $x\lt y$ and $y\lt z$ then this implies that $x\lt z$. Now for functions $f,g,h$, we have that if $f=\cal O(g)$ and $g=\cal O(h)$ then this implies that $f=\cal (h)$. Let $f=\cal O(n\log n)$. Since $n \log n = \cal O(n^2)$, we have that $f = \cal O(n^2)$.

This should hopefully help you better understand Big O notation. You can prove transitivity of $\cal O$ using the formal definition:

> For functions $f,g$, we say that $f$ is Big O of $g$ (write $f=\cal O(g)$) if there exist constants $n\_0,c \gt 0$ such that $f\le c\times g$ whenever $n\ge n\_0$.

This means that starting at some point along the $x$ axis (we call it $n\_0$) the function $f$ is always bounded above by a constant multiple of $g$.

# Answer
> 0 votes
I do not find any contradiction between your (said) understanding and the answer from StackOverflow you posted. It seems your problem is at the level of your understanding of *upper* bound and *lower* bound.

In this context of algorithm complexity, upper bound means *cannot be asymptotically worse than*. As such all algorithms are $O(\infty)$. Lower bound means *cannot be asymptotically better than*. As such all algorithms are $\Omega(0)$.

However for those algorithms for which there exists an $O(f(n))$ and an $\Omega(f(n))$, where $f(n)$ is some function of $n$, there also exists a $\Theta(f(n))$. So we notice that of the three only $\Theta$ is unique.

---
Tags: algorithms, terminology, asymptotics, landau-notation
---


title: Solve recurrence

text:
# Question
Title: Solve recurrence
!\[enter image description here\]\[1\]

I have a problem to solve this recurrence. I tried by myself but it doesn't look understandable. Solve the following recurrence

# Answer
As FrankW mentioned, your question seems to be: Solve the recurrence

> $$f(n+1) = \begin{cases}2 & n=0\\f(n)+3 & n\>0\end{cases}$$

The solution $f(n) = 3n-1$ is already given. It just needs to proven:

* base case: $f(1)=3-1=2$
* otherwise: $f(n+1) = 3(n+1) - 1 = 3n + 3 - 1 = 3n - 1 + 3 = f(n) + 3$

**Edit**

As to your comment on how to find $f(n) = 3n-1$ (though it was given in the question), use induction on n:

* $f(1) = 2$
* $f(2) = 2+3 = 5$
* $f(3) = 5+3 = 8$
* $f(4) = 8+3 = 11$
* $f(5) = 11+3 = 14$
* $f(6) = 14+3 = 17$

So try to find a function for which $f(1) = 2, f(2) = 5, f(3) = 8, f(4) = 11, f(5) = 14, f(6) = 17,\ \dots$ Clearly it is $f(n) = 3n-1$
> 2 votes

# Answer
Judging from the image, I think the exercise is trying to ask the following:

> Given the recurrence $$f(n) = \begin{cases}2 & n=1\\f(n-1)+3 & n\>1\end{cases},$$ show that $f(n) = 3n-1$.

Does this help?
> 2 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Why do we use several bits instead of a single bit for storage of objects in Bloom Filters
Bloom filters are a variant of hash tables except it is much more space efficient at the cost of a low probability of false positives .

How it works : Assume there are 10000 bits , 3 hash functions and an object Foo is to be inserted into the Bloom Filter .

Insertions : Foo will be hashed by the 1st hash function and the 3405 bit index is set to 1 , Foo is hashed by the second hash function and the 1001 bit index is set to 1 , Foo is hashed by the third hash function and the 5555 bit index is set to 1 .

Check exist : Foo will be hashed to the three different hash function and if all the bits at the respective index is set to 1 , the object is said to exist with a small chance of false positive else the object cant be found .

My question is : Why do we use more than 1 (in this case 3 bits ) to determine if a objects exist in the Bloom Filter , doesnt it increase the chances of collision with other objects which may also set the same bit to 1 . To me , it seems best to use a single hash function as it saves the most space (1 bit only) and least chances of collision with other objects in the Bloom Filter

# Answer
> 1 votes
Consider Bloom filters in which $k$ hash functions are used. If we look up a value which is in the filter, then we always conclude that it is indeed in the filter. Things are more complicated when we look up a value which is *not* in the table; we could erroneously conclude that it were in the table.

Suppose the filter is of size $n$, and $m$ values were put into the table. So roughly $km$ positions are set to $1$. If we look up a value which was not put in the filter, then assuming that the hash locations corresponding to it are random, the probability that we erroneously conclude that it is in the filter is $$ \left(\frac{km}{n}\right)^k. $$ The correct value of $k$ thus depends on the expected $m/n$. Suppose that $m = n/10$. Then we have the following error probabilities: $$ \begin{array}{c|l} k & \text{error probability} \\\hline 1 & 0.1 \\ 2 & 0.04 \\ 3 & 0.027 \\ 4 & 0.0256 \\ 5 & 0.03125 \end{array} $$ So in this setting the error probability is minimized for $k = 4$. Since $k$ also effects the running time, we might as well choose $k = 3$ for these parameters, for which the error probability is almost as good.

---
Tags: data-structures, bloom-filters
---


# Question
Title: What is a fixed point in the context of Roger's fixed-point theorem?
In the Wikipedia article on Rogers' theorem, it is stated that all total computable functions have a fixed point. The notation is a little hard for me to understand; a symbol is used that is used to denote "semantic equivalence." I do not know what semantic equivalence is; I would appreciate it if someone could shed some light on what a fixed point is in this context, and on what semantic equivalence is in this context.

# Answer
The notation is explained in the Wikipedia entry (though regrettably after its first use): for partial functions $f,g$, we say that $f\simeq g$ if for all inputs $x$, $f$ halts on $x$ iff $g$ halts on $x$, and if both halt on an input $x$, then $f(x) = g(x)$. In other words, $f$ and $g$ compute the same partial function, and so they are *semantically equivalent*: they result in the same outcome.

The idea behind *semantic equivalence* is that two programs might be different but could be equivalent in the sense that they compute the same function. For example, if there are two statements $x \gets 0; y \gets 1$ and we switch their order to $y \gets 1; x \gets 0$ then the resulting programs are different *syntactically* but equivalent *semantically*.

Roger's theorem shows that for every total computable function $P$, which we think of as a transformation rule for programs, there is some program $e$ that is equivalent to $P(e)$. The rest of the Wikipedia entry explains why this is useful.
> 6 votes

# Answer
Semantic equivalence can be contrasted with **syntactic equivalence.** You can think of something as being syntactically equivalent if it "looks" the same (the syntax of some expression is equivalent). Semantic equivalence means that something is equivalent in meaning.

Fixed-point semantics are generally used to describe loops and recursion for the denotational semantics of a programming language. When we are trying to **define** a recursive function, such as the factorial function $fact$, we cannot just write $fact(n) = \text{ if } n \leq 0 \text{ then } 1 \text { else } n \cdot fact(n-1)$ and be done, because this is not a definition of $fact$, it is a recursive equation. In order to define $fact$, we actually need to construct it as the union of a sequence of partial functions $F^i$.

I think to really understand how this works, you should try to think of functions as sets. For $fact$, we define $F^0(\emptyset) = \emptyset$, and $$F^{i+1}(\emptyset) = \text{ if } n \leq 0 \text{ then } 1 \text { else } n \cdot F^{i}(\emptyset)(n-1),$$ where $F^{i}(\emptyset)(n-1)$ denotes the application of the function given by $F^{i}(\emptyset)$ on $n-1$. Now we have that $fact = \bigcup\_{i \geq 0} F^i(\emptyset) $, where $F: (\mathbb{N} \rightharpoonup \mathbb{N}) \rightarrow (\mathbb{N} \rightharpoonup \mathbb{N})$ (note that $\rightharpoonup$ denotes a partial function). Given our definition of $F$, each function $F^0, F^1, F^2, F^3, F^4,...$ is equivalent to

$$ \begin{align} \emptyset &= \emptyset\\ F(\emptyset) &= \\{ (0, 1) \\}\\ F(F(\emptyset)) &= \\{ (0, 1), (1, 1) \\}\\ F(F(F(\emptyset))) &= \\{ (0, 1), (1,1), (2,2) \\}\\ F(F(F(F(\emptyset)))) &= \\{ (0, 1), (1,1), (2,2), (3,6) \\}\\ ... \end{align} $$ As you can see, $F^4$ contains solutions up to $n=3$ for $fact$. The union of all of these functions is $fact$. Therefore, we say that $fact$ is the **fixed-point** of $F$ because if you apply $F$ to $fact$, you get $fact$, or $F(fact) = fact$.

In the example from the wiki article, $e = fact$, and $\varphi\_{fact}$ is the denotation of $fact$. The denotation of some expression is the mathematical definition of that expression. We just defined $fact$ mathematically. Therefore we can define the denotation of $fact$ (using the notation from the wiki article) as $\varphi\_{fact} = \bigcup\_{i \geq 0} F^i(\emptyset)$. Since $fact$ is the fixed-point of $F$, we also have that $\varphi\_{fact} = \varphi\_{F(fact)}$, which implies that $fact$ is semantically equivalent to $F(fact)$. We can strengthen our notion of semantic equivalence here: If both functions are equivalent with respect to their definitions (their sets), then they are semantically equivalent.
> 3 votes

---
Tags: computability
---


# Question
Title: How to compare algorithms in class NC time complexity with other classes?
I know these relations :

\begin{gather} \mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\ \mathrm{NC}^i \subseteq \mathrm{AC}^i \subseteq \mathrm{NC}^{i+1} \\ \mathrm{NC}^1 \subseteq \mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{AC}^1 \subseteq \mathrm{NC}^2 \subseteq \mathrm{P} \end{gather}

But I don't know how to compare an algorithm with time complexity of $\mathrm{NC}^i$ to an algorithm with Polynomial complexity?

For example, Topological sort $\mathrm{NC}^2$ with BFS $\mathcal{O}(|V| + |E|)$

# Answer
The class NC is by definition a subset of P, since it consists of uniform polynomial size circuits with some restrictions (namely, polylogarithmic depth). It is unknown whether $NC \neq P$, but this is strongly suspected.

Let me comment that $O(NC^2)$ is a syntax mismatch since $NC^2$ is a complexity class rather than a function. We simply say that topological sort is in $NC^2$.
> 5 votes

---
Tags: complexity-theory, time-complexity, parallel-computing
---


title: MIPS: sign extend in I-Type commands

text:
# Question
Title: MIPS: sign extend in I-Type commands
My lecturer told me that when I use an arithmetic I-Type command (ADDI,SUBI etc.) , the IMM field gets sign extended, and when I use a logic I-Type command (ORI,ANDI etc.) , the IMM field is just bits.

He also said that if the IMM field contains a negative number, it is represented in 2's complement.

Let's say I have a command, and two binary numbers X Y, so that X's 2's complement representation looks exactly like Y in regular representation.

Note: X is negative and not the same as Y.

Given a question in which I should say what is the value in the IMM field in an arithmetic I-Type command, how do I know if it's X or Y?

# Answer
In an arithmetic I-type command, the IMM-field is treated as a signed number. So if the first bit is 1, the number will be treated as negative (X in your terms.) The number Y is simply too large to be used as argument of an arithmetic I-type command.
> 2 votes

---
Tags: computer-architecture, number-formats
---


title: Horn clause to Prolog

text:
# Question
Title: Horn clause to Prolog
At the needs of my HW at uni I need to transform some Horn clauses to Prolog but I cannot figure out how to do it. I found out some guides but they describe how to do it with only one fact. So can you give me a brief example on how to do it?

Eg John is beautiful and rich

we can transform it at: `not (Beautiful(John)) ^ not(Rich(John))` which is a Horn clause right? So how this can be translated it Prolog?

another example Everyone loves somebody. Horn clause: $\forall X \exists Y Loves(X,Y)$ how can this be implemented in Prolog?

Thx in advance

# Answer
A horn clause is a disjunction with at most one positive literal, e.g.

\begin{align} \lnot X\_1 \lor \lnot X\_2 \lor \ldots \lor \lnot X\_n \lor Y \end{align}

The implication $X \rightarrow Y$ can be written as disjunction $\lnot X \lor Y$ (proof by truth table). If $X = \lnot X\_1 \lor \lnot X\_2 \lor \ldots \lor \lnot X\_n $, then $\lnot X$ is equivalent to $X\_1 \land X\_2 \land \ldots \land X\_n$ (De Morgan's law). Therefore, the above clause is logically equivalent to

\begin{align} (X\_1 \land X\_2 \land \ldots X\_n) \rightarrow Y \end{align}

A Prolog program basically is a (large) list of horn clauses. A Prolog clause (called rule) is of the form `head :- tail.`, which in logic notation is $head \leftarrow tail$. Therfore, any horn clause

\begin{align} \lnot X\_1 \lor \lnot X\_2 \lor \ldots \lor \lnot X\_n \lor Y \end{align}

is written in Prolog notation as `Y :- X1, X2, X3, ..., Xn.`

A horn clause containing no positive literal , e.g. $\lnot X\_1 \lor \lnot X\_2 \lor \ldots \lor \lnot X\_n$ can be rewritten as $(X\_1 \land X\_2 \land \ldots X\_n) \rightarrow \bot$, which is `:- X1, X2, X3, ..., Xn.` in Prolog notation.

Regarding your examples:

1. *"John is beautiful and rich"*, is a CNF, and each clause contains at most one positive literal, hence it can be written in Prolog as `beautiful(john).` and `rich(john).`
2. $\forall X \ \exists Y \ \operatorname{Loves}(X,Y)$

That nested extential quantifier can be eleminated by Skolemization, which is introducing a new function for the extential quantifier inside the universal quantifier: $\forall X \ \operatorname{Loves}(X,p(x))$, which in Prolog notation is `loves(X,p(X)).`
> 9 votes

---
Tags: first-order-logic, prolog
---


# Question
Title: Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?
Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine with a psuedo-random number generator can't do? (a trivial thing it can do would be generating truly random numbers)

# Answer
> 2 votes
As long as decision problems (or optimization problems) are concerned, probabilistic Turing machines are equivalent to non-probabilistic Turing machines, since you can just simulate all the possible coin tosses (there are some subtleties here since the probabilistic Turing machine could halt only with probability 1, but let's ignore them).

However, there could be a difference in *efficiency*. Using truly random coin tosses could allow you to solve a specific problem faster. However, it is conjectured that truly random coin tosses can't bring down the level of difficulty from non-polynomial to polynomial, that is, if you have a probabilistic polynomial time algorithm for a problem, then there exists a deterministic polynomial time algorithm for the problem. This conjecture is known as the P=BPP conjecture. The idea is that you can simulate the truly random coin tosses with a sufficiently sophisticated PRNG. The simulation might be costly in running time, but it incurs only a polynomial overhead, and from this point of view that's a cost we're willing to pay.

Practically speaking, PRNGs are good enough, although in some rare cases you need to be slightly careful and use something beyond the fastest known PRNG. Only in cryptography does it sometimes make sense to use truly random coin tosses, since you can get absolute security guarantees this way (*one-time pads*), though in practice cryptographic PRNGs are used and they seem secure enough.

---
Tags: turing-machines, randomness, probabilistic-algorithms
---


# Question
Title: Proving a language is not a regular language but a context free language
I have the languages $L\_1$ and $L\_2$ such that $L\_1 = \\{a^nba^n :n \in N\\}$ and $L\_2 =\\{a,b\\}^\*\setminus L\_1$.

I want to prove that $L\_2$ is not a regular language. I know that to prove that $L\_2$ is not a regular language I can use the pumping lemma but I'm unsure about the details.

I also want to prove that $L\_2$ is a context free language. Do I need a Push Down Automaton that accepts the language to prove that $L\_2$ is a context free language? If so, what would this Push-Down Automaton look like?

# Answer
While it is possible to show that $L\_2$ is not regular using the pumping lemma, it is easier to do so by making use of the fact that the regular languages are close under complement, i.e. a language is regular if and only if its complement is regular.

In order to show that $L\_2$ is context-free, you can give either an automaton or a context-free grammar for the language. The automaton is presumably the easier way in this case. Hint: $L\_2$ is a deterministic context-free language, so there is a deterministic PDA for $L\_2$ that can be derived in a straightforward way from the deterministic PDA of $L\_2$'s complement.
> 3 votes

---
Tags: formal-languages, regular-languages, context-free, pushdown-automata
---


# Question
Title: How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?
Suppose that I have a set of $N$ points in $k$-dimensional space ($k\>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The brute-force method would require $N(N-1)$ distance calculations, which is not acceptable. I attack the problem by first sorting the cells in a grid¹, such as in this answer, followed by brute-force within each grid cell and a number of neighbours (which is easily calculated from the cell size $w\*h$ and the maximum distance $t$).

My solution seems to work acceptably well for my purposes, and the results appear to be correct. However I'm neither a computer scientist nor a mathematician, and I'm not sure what tools I could use to calculate the optimal cell size. In fact, I developed the aforementioned possibly naive algorithm because it seemed like a reasonably okay method. I *guess* the optimal cell size depends in some way on $N$, $t$, on the cost of the distance function, and on the implementation of the sorting in cells, on the distribution of points, and on other things. How would I make a guess of the optimal values of $w$ and $h$, with or without a priori knowledge on the approximate number of pairs I expect to find?

Does the answer change if the N points are divided in two sets $S\_1$ and $S\_2$, and each pair shall consist of one element from each set?

---

¹Not necessarily euclidian. The points may, for example, be locations on a sphere, i.e. on Earth, with latitude and longitude.

# Answer
> 6 votes
There's an enormous amount of work on data structures and algorithms for this sort of problem. I suggest you start by reading the general literature on this problem.

Start by reading about algorithms for nearest neighbor search, including all nearest neighbors and the fixed-radius nearest neighbors problem. Those techniques are applicable to your problem.

Then, read about quadtrees, octrees, k-d trees, VP trees, and the general category of BSP trees.

# Answer
> 3 votes
Let's start with a special case, $k=2$, and a bunch of assumptions. Let's assume that your grid is a dense $k$ dimensional square array of cells, and each cell contains some relatively simple implementation of a set of points (for example, a linked list of points.) Let's also stick with Euclidean distances, assume you don't care about the edge conditions (points that move outside the grid), and that the points are independently uniformly randomly distributed.

I'm also going to assume you know the average density (in terms of expected number of points within a sphere of radius $t$).

Now let's look at the two extreme cases. If you make your cells too small then most of the cells will be empty, and you'll spend most of your time iterating through empty cells. If you make your cells too large then you will do a larger number of extra distance computations for points that are farther than $t$ away.

I can't think of any reason you would want your cells to be larger than $t \times t$. With $k=2$ and cells of this size you need search 9 cells. That's a search area of $(3t)^k$. With cells of size $t/2 \times t/2$ you need to search 25 cells. That's a search area of $\frac{25}{4}t^2$. With cells of size $t/M \times t/M$ you need to search approximately $(2M+1)^k$ cells, and the area you search is $(\frac{2M+1}{M}t)^k$, so in the limit you are getting arbitrarily close to $(2t)^k$. (When $M$ gets sufficiently large you may be able to avoid searching some of the cells in the corners, but I'm ignoring that too.)

This is where the density, $\delta$, (the average number of points in a volume of $t^k$) comes in. If the cost of iterating over an empty cell is similar to the cost of doing a distance calculation, then you are trying to minimize $$(2M+1)^k + \delta (\frac{2M+1}{M})^k$$. Take the derivative with respect to $M$, set it equal to 0, and solve for $M$ and you get something like $\hat{M}^{k+1} = \delta/2.$

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


title: Sandwiching Languages

text:
# Question
Title: Sandwiching Languages
I am studying for my algorithms final and came across the following problem:

Find three languages $L\_1 \subset L\_2 \subset L\_3$ over the same alphabet such that $L\_2 \in P$ and $L\_1,L\_3$ are undecidable.

I am having trouble coming up with an example of three such languages. My first thought was to use a form of the halting problem for both $L\_1$ and $L\_3$ since that is pretty much the only undecidable language I know and am familiar with. I was thinking of perhaps coming up with something of the form \begin{align\*} L\_1 &= \\{M \mid \text{$M$ is a Turing machine that starts with 00 and halts}\\}\\ L\_2 &= \\{M \mid \text{$M$ is a Turing machine that starts with a 00}\\}\\ L\_3 &= ? \end{align\*} but this doesn't seem to be working. Any ideas are appreciated!

# Answer
Hint: Let $L\_3 = L\_2 \cup M$, where $M$ is a language similar to $L\_1$ and disjoint from $L\_2$.
> 3 votes

# Answer
Hint: Your approach can be completed and you need to change only one word in the description of $L\_1$ to get a description for $L\_3$ that works.
> 3 votes

---
Tags: formal-languages, computability, undecidability
---


# Question
Title: Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$
I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free grammar that describes this language. After defining a context-free grammar I want to formally prove that this context-free grammar describes this language.

I've came up with the context-free grammar production rules: $$ \begin{align\*} &S\to0S1S \\ &S\to1S0S \\ &S\to\epsilon \end{align\*} $$ Is this the correct context free grammar to define this language?

Im kind of stumped for the proving part. I'm guessing I will need some sort of induction?

# Answer
Your grammar does work. And you are correct in assuming that induction is a worthwile proof-technique. As a hint, you can use the following induction hypothesis:

IH: All the words of length at most $n$ that can be derived from $S$ have an equal amount of $0$'s and $1$'s.

Can you fill in the anchor and step from here?

---

As D.W. pointed out, the above is only enough to prove that the grammar will not produce any wrong words, or $L(G) \subseteq L$. In order to complete the proof, you also need to show that $L \subseteq L(G)$, i.e. all the words in the language are generated by the grammar.

For this part you can try an induction with the hypothesis

IH: All the words of length at most $n$ that have an equal amount of $0$'s and $1$'s can be derived from $S$.

(Of course, you can combine these two inductions, but having them seperate may be easier to handle if you are unexperienced.)
> 6 votes

# Answer
As FrankW mentions, your grammar does generate the language. As D.W. mentions, the induction argument that FrankW suggests easily shows that all the words that your grammar generates have an equal number of 0s and 1s. It is more difficult to prove the other direction, that is, that every word with an equal number of 0s and 1s can be generated by the language. The idea is as follows. Suppose without loss of generality that we are trying to generate a word $w$ which starts with 0. Our goal is to factor $w$ as $w = 0x1y$ in such a way that $x,y$ have an equal number of 0s and 1s (why is that enough?). If $x$ has an equal number of 0s and 1s then $y$ also does (why?), so it is enough to figure out how to find the $0x1$ part. The idea here is to trace the word from left to right, keeping count of the difference between the number of 0s and the number of 1s. For example, for the word $w = 0010110110$, the sequence is $$ \begin{array}{l|c} \text{Subword} & \\#\_0-\\#\_1 \\\hline \epsilon & 0 \\ 0 & 1 \\ 00 & 2 \\ 001 & 1 \\ 0010 & 2 \\ 00101 & 1 \\ 001011 & 0 \\ 0010110 & 1 \\ 00101101 & 0 \\ 001011011 & -1 \\ 0010110110 & 0 \end{array} $$ This shows that we can break $w$ as $0|0101|1|0110$ (so $x = 0101$ and $y = 0110$). Another possibility is $w = 0|010110|1|10$. Both of these correspond to $0$ entries in the table. See if you can come up with an argument showing that these $0$ entries must always exist. Don't forget to account for cases like $0|1|\cdots$ ($x = \epsilon$) and $0|\cdots|1$ ($y = \epsilon$).
> 4 votes

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


title: Limits to the definition of a language

text:
# Question
Title: Limits to the definition of a language
Is there any limit to what we can define as a language? Is any set of symbols a language?

For example, given the alphabet $\Sigma$, do we say that the language $L = \Sigma$ has alphabet $\Sigma$?

Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)? I always hear languages described as *problems*, but what are we really saying when we say that a language *is* a problem?

# Answer
> Is there any limit to what we can define as a language?

No. Any set of strings over some alphabet is a language. Typically, in computer science, we're only interested in the case where the alphabet is finite and usually, though not always, we only consider finite strings, too.

> Is any set of symbols a language?

A set of symbols is an alphabet. A language is a set of strings whose characters are in some alphabet, though you could also consider an alphabet to be a language of words of length 1..

> For example, given the alphabet $\Sigma$, do we say that the language $L=\Sigma$ has alphabet $\Sigma$?

As above, yes.

> Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)?

A language is a language; the definition hasn't changed over time so I'm not sure what you mean by a "modern equivalent". A complexity class $C$ is a class of languages, classified by the amount of some resource (typically time or space) required to determine whether, for some $L\in C$, an input word is a member of $L$.

> I always hear languages described as problems, but what are we really saying when we say that a language is a problem?

Languages and decision problems are essentially the same thing. Given a language $L$, the corresponding decision problem is "Given a word $w$, is $w\in L$?" More formally, a problem is a collection of objects of some kind (e.g., graphs or formlas) such as the 3-colourable graphs or satisfiable 3CNF formulas. A language then, is an encoding of the elements of a problem as strings, e.g., strings representing the adjacency matrices of 3-colourable graphs.
> 6 votes

---
Tags: formal-languages, terminology
---


# Question
Title: Merge-by-weight to solve reachability problems in trees and DAGs
Let $T = (V, E)$ be a tree with a designated root $r \in V$. The fact that the tree is rooted allows us to speak of "subtrees of $T$ rooted at some node $x \in V$". Let's say we have a (not necessarily injective) function $c: V \rightarrow \mathbb{N}$ that assigns a color to every node.

We want to find for every node $x \in V$ the number of distinct colors in the subtree rooted at $x$. So if $A(x)$ is the set of children of $x$, we want to find for every node $x$, the cardinality of the set

$S(x) = \bigcup\_{y\in A(x)} S(y) \cup \\{c(x)\\}$

There is a rather simple algorithm that solves this problem offline in $O(n \log^2 n)$:

* Process the nodes in depth-first order
* Represent the sets $S(x)$ as a persistent, self-balancing binary search trees
* For every node $x$, let $y \in A(x)$ be the child of $x$ that maximizes $|S(y)|$. Now we just merge for every other child $z \in A(x) \setminus {y}$ the set $S(z)$ into the set $S(y)$ via insertion. We also insert $c(x)$ and now have $S(x)$ as a binary search tree and can give the answer for node $x$

We can even avoid the persistent trees by mutating the subresult for the heaviest child instead of creating a new set.

The typical argument I have seen to justify the bound is the following:

> A "move" consist of taking an element from a set and inserting it in another set. Let's prove that there's at most $O(n \log n)$ moves, each move can be done in $O(\log n)$, the total complexity is $O(n \log^2 n)$.
>
> When you are merging two sets you move all elements from smaller set (assume its size is $k$) to the bigger one, so every element in the smaller set now is in a set with at least size $2k$. In other words every element that has been moved $t$ times is in a set with at least size $2^t$, thus every element will be moved at most $O(\log n)$ and we have $n$ elements so in total there will be at most $O(n \log n)$ move operations.

(Quote from a Codeforces comment).

While this is a beautiful argument, it's not *quite* correct, because usually we remove duplicates, so sets don't in fact grow exponentially (for example if every node has the same color).

I am convinced that the bound holds, because I can prove it using structural induction. What I want to know is the following:

* Is there a way to prove the $O(n \log^2 n)$ bound using an argument similar to the above, by bounding the number of "moves" of the color of a node? In other words, can the proof be "fixed" easily?
* The argument from above would also hold in DAGs, not only in trees. However it seems unlikely that we could achieve a runtime better than $O(n \cdot m)$ to solve this problem in a DAG, so I guess there is no fix for the proof idea in this case. Am I right? Is there a good intuition for that?

# Answer
> 3 votes
There are two (equivalent) ways to fix the argument:

1. Start by not eliminating duplicates. Then the argument works. Then argue that removing duplicates can only decrease the running time.
2. Count elements with multiplicity, that is, consider each set $S(x)$ as a multiset.

Both of these arguments require a slight modification of the algorithm: for each vertex $x$, you keep track of the size of the subtree, and use this to select the heaviest child rather than the number of distinct colors.

This argument breaks down for a DAG since a vertex can have multiple parents.

---
Tags: graphs, trees
---


# Question
Title: Subgraph Isomophism Problem - Color Coding Technique - Proof Sketch
I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a theorem (6.3) that says if $H$ is a graph on $k$ vertices with treewidth $t$ and $G = (V, E)$, then a subgraph of $G$ isomorphic to $H$ can be found in $2^{O(k)}V^{t+1}$ expected time. They do not include a proof, but do state that the proof is similar to the case where $H$ is a forest (namely theorem 6.1, which they do provide a proof of).

As I am trying to understand how they algorithm would work for graphs of bounded treewidth, I was wondering if anyone could provide a proof sketch of the algorithm, as I don't see how it would be similar to the proof of 6.1 - Any help would really be appreciated, as this is for a course project, and I am having difficulties figuring out the algorithm.

A copy of the paper can be found here: http://www.tau.ac.il/~nogaa/PDFS/col5.pdf

# Answer
The idea is to repeat the proof of Theorem 6.1, only during the recursive construction in the second paragraph, we use the tree decomposition of $H$ rather than $H$ itself. We pick a vertex in the tree decomposition, which correspond to up to $t+1$ vertices of $H$, and split $H$ into two parts $H',H''$ accordingly, applying the algorithm recursively. Since we are dealing with groups of up to $t+1$ vertices at a time, we have to calculate the color sets for sets of $t+1$ vertices rather than for single vertices.

There are many resources online for this general approach, dynamic programming for graphs of bounded treewidth. You can consult Section 2.4 of Hajiaghayi's thesis or a presentation by Marx.
> 3 votes

---
Tags: graphs, graph-isomorphism
---


title: The crux of Savitch's Theorem

text:
# Question
Title: The crux of Savitch's Theorem
In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going to quote the text verbatim, because quite frankly I don't fully understand it (which is why I was unable to really ask my question in enough detail):

> We need to simulate an $f(n)$ space NTM deterministically. A naive approach is to proceed by trying all the branches of the NTM’s computation, one by one. The simulation needs to keep track of which branch it is currently trying so that it is able to go on to the next one. But a branch that uses $f(n)$ space may run for $2^{O(f(n))}$ steps and each step may be a nondeterministic choice. Exploring the branches sequentially would require recording all the choices used on a particular branch in order to be able to find the next branch. Therefore, this approach may use $2^{O(f(n))}$ space, exceeding our goal of $O(f^2(n))$ space. (Sipser, "Introduction to the Theory of Computation" 334)

He goes on to describe Savitch's use of a subroutine called $CANYIELD$, a TM that decides whether some configuration $c\_2$ is reachable from some other configuration $c\_1$ in $t$ steps. It is recursively defined, so that $CANYIELD(c\_1, c\_n, t)$ results in two recursive calls $CANYIELD(c\_1, c\_m, t/2)$ and $CANYIELD(c\_m, c\_n, t/2)$, and so on until the "distance" between configurations is $0$ or $1$, or it is deemed unreachable. I think this can also be described as $STCON$ on a configuration graph of the TM in question.

So, there are two questions I have.

1. I understand how the size of each level and the depth of $CANYIELD$ results in no more than $O(f^2(n))$ use of space, but I don't understand how the intermediate configuration $c\_m$ is found. Is this just not important given that all we care about is space? How do we know that the space used to obtain $c\_m$ is negligible?
2. I don't understand why we need $2^{O(f(n))}$ space in the naive approach. Why can't we "forget" about branches we've executed, so that we are still using at most the space required to go all the way down one branch?

# Answer
> 6 votes
A program running in space $f(n)$ can take up to $2^{O(f(n))}$ time (the constant depends on the alphabet size). Hence, it could potentially make up to $2^{O(f(n))}$ non-deterministic choices. Naively, going over all of them requires that many steps. Savitch's theorem shows how this can be accomplished using only $O(f(n)^2)$ space. The idea is to use a recursive "meet in the middle" approach. Let an upper bound on the running time of the machine be $T$. The *initial tape* is the the state of the tape when the machine is started up. The *final tape* is the state of the tape at the end of the execution. We "guess" (i.e., go over all possibilities) the final tape, and try to verify that this final tape can be reached from the initial tape. At the first level of the recursion, we "guess" the contents $X$ of the tape at time $T/2$. We then recurse into two similar tasks:

1. Verify that $X$ can be reached in $T/2$ steps from the initial tape.
2. Verify that the final tape can be reached from $X$ in $T/2$ steps.

Each of these is solved by recursion. We can reuse the space of the first task when we execute the second task. The base of the recursion is when the number of steps is one, in which case we can verify the claim directly. If it checks out, great. Otherwise, we signal failure, and this signal prompts us to make the next guess (at the appropriate level of recursion).

Each level of the recursion requires storage space of size $f(n)$, and there are $\log T = O(f(n))$ levels, so the total space consumption is $O(f(n)^2)$.

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Characterisation of graphs that are not 3-colorable
We know that *all* graphs with odd cycles (odd number of vertices) are not 2-colorable. Is there a similar characterisation for 3-colorability? I am looking for undirected graphs that are not 3-colorable depending on a single graph property e.g. vertices/edges parity or anything else that can be generalised.

# Answer
> 9 votes
As far as we know, there is no simple characterization for 3-colorability. Indeed, deciding if a given graph is 3-colorable is $\sf NP$-complete. Thus, more precisely, there is likely no polynomial-time characterization for 3-colorable graphs.

However, we know plenty of structured graph classes for which the problem is easy. For example, Grötzsch's theorem states every triangle-free planar graph is 3-colorable. Furthermore, such graphs can be 3-colored in linear time. In a random graph setting, almost all graphs with $2.522n$ edges are not 3-colorable \[1\].

You can find plenty of graph classes for which 3-coloring is easy on ISGCI.

---

\[1\] Achlioptas, D., & Molloy, M. (1999). Almost all graphs with 2.522 n edges are not 3-colorable. Electronic Journal of Combinatorics, 6(1), R29.

# Answer
> 4 votes
Hajós came up with a calculus for proving that graphs are not 3-colorable. The calculus is complete, in the sense that every non-3-colorable graph can be proved to be non-3-colorable. Pitassi and Urquhart related the strength of this proof system to the classic Extended Frege proof system: if one system is optimal (has short proofs for all true statements), then so is the other.

# Answer
> 3 votes
For each value $k\in \mathbb{N}$, any graph that has a $(k+1)$-clique is not $k$-colorable. So a 4-clique rules out the existence of a 3-coloring.

Be aware, that this is only a necessary condition (i.e. there are graphs without a 4-clique that are still not 3-COL), while the odd-length cycle condition for 2-colorings is also sufficient (i.e. any graph without an odd-length cycle is 2-COL).

---
Tags: graphs, colorings
---


title: What is an reflective tower?

text:
# Question
Title: What is an reflective tower?
I've just read in a discussion about dynamic typing

> Reflective towers is an open problem for statically typed languages.

What are reflective towers?

I think it might be related to reflection, but I'm not sure.

If you create an example, I would prefer Java.

# Answer
A reflective tower is a model for language extension. It is modeled as an infinite (tower) series of interpreters. Each interpreter is executing a program which is the interpreter one level bellow it with the programmers' program being at level 0.

Each program is a piece of code that performs computation and in that sense a function but it is also a modifiable struct (it is a data-structure).

You can read about it here
> 5 votes

---
Tags: type-theory, reflection
---


title: On Shannon Capacity

text:
# Question
Title: On Shannon Capacity
Let $G$ be a graph whose Shannon Capacity is $\Theta(G)$. Is there any graph product for which the Shannon Capacity is $\Theta(G)^k$ where $k$ is the number of times the product is taken?

# Answer
The Shannon capacity is defined as $$ \Theta(G) = \sup\_k \alpha(G^k)^{1/k}, $$ where $G^k$ is the strong graph product. It is not hard to show that $\alpha(G^{k+l}) \geq \alpha(G^k) \alpha(G^l)$, and this implies that $\alpha(G^k)^{1/k}$ converges. Therefore $$ \Theta(G) = \lim\_{k\to\infty} \alpha(G^k)^{1/k} = \lim\_{k\to\infty} \alpha(G^{tk})^{1/{tk}} = \Theta(G^t)^{1/t}. $$
> 2 votes

---
Tags: graphs, information-theory
---


title: P, NP and polynomial time reduction?

text:
# Question
Title: P, NP and polynomial time reduction?
If $P = NP$ would this imply that polynomial time reduction from an $NP$- to a $P$-problem would be possible? And if $P\neq NP$ does it imply that a polynomial time reduction from an $NP$- to a $P$-problem would be impossible?

# Answer
Since $P \subseteq NP$, every problem in $P$ is also in $NP$. So in both cases there is an $NP$-problem that can be reduced to a $P$-problem. Simply choose a problem in $P$ as the $NP$-problem and the same problem as the $P$-problem.

If you replace $NP$-problem by $NP$-complete problem, both of your statements hold.
> 5 votes

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language?
If two regular languages $L\_1$ and $L\_2$ are both **not** context free languages then is $L\_1 \cup L\_2$ also **not** a context free?

I am aware that if $L\_1$ and $L\_2$ are context free languages then the language $L\_1 \cap L\_2$ is also context free but cannot quite connect the dots. If someone could help out that would be great.

# Answer
> 6 votes
First, note that CFL is not closed under intersection, contrary to what you've mentioned. For example: $$ L\_1 = \\{a^ib^ic^j|i,j \geq 0\\}, \quad L\_2 = \\{a^ib^jc^j|i,j\geq 0\\}. $$ We see that $L\_1 \cap L\_2 = \\{a^ib^ic^i|i\geq0\\}$, which is not CFL.

For your question, Take two languages $L\_1, L\_2$ which are not CFL. Let $$ \begin{align\*} L'\_1 &= \\{0x|x \in L\_1 \\} \cup \\{1x|x \in \Sigma^\*\\}, \\ L'\_2 &= \\{1x|x \in L\_2 \\} \cup \\{0x|x \in \Sigma^\*\\}, \\ \end{align\*} $$ which are both not CFL. It's easy to see that $L'\_1 \cup L'\_2 = \Sigma^\*$, which is CFL (as it is a regular language).

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


title: Complement DCFGs and handles

text:
# Question
Title: Complement DCFGs and handles
If I have a DCFG G for some language over {0,1}\* and a DCFG H for its complement, with disjoint non-terminals, and a (perhaps partially reduced) string, can they both have a handle for the string? So the right hand sides of these rules would consist of only terminals and one would be a (maybe proper) prefix of the other. I think it's possible but I'm not certain and can't quite show it.

# Answer
> 1 votes
What you want is not necessarily possible. So you have to build grammars that will make it possible.

Try prefixing both languages by $\\{0,1\\}^3$ (for example). That is, if $L\_G$ and $L\_H$ are the languages corresponding to your grammars, consider the languages $\\{0,1\\}^3$.$L\_G$ and $\\{0,1\\}^3$.$L\_H$.

You should be able to build grammars for them, and also prove that they are complement of each other. You should also be able to show that since, there are DPDAs recognizing the two languages $L\_G$ and $L\_H$, you can build from them DPDAs that recognize your augmented languages.

If you build the grammars as you should (it is very easy), you will get your double handle.

The only problem is that, since both handles are on the same side, you cannot use them for a bicycle, or for a heavy pot.

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


# Question
Title: Does the OS create its own bootstrapped stack frame when running a program?
I've been doing nand2tetris exercises and I'm quite interested in how compilation actually works. In nand2tetris when creating the VM language I had to create a "bootstrap" which called the main method of the program.

In other languages such as C, Java or even interpreted languages like PHP, does the OS/interpreter/VM automatically create its own first frame on the stack, and then invokes the main method of the program as a new second stack frame?

I'm trying to think about how initial arguments are passed to a program, and how programs are able to return values. Does each OS have a standard way of creating this initial stack frame which all languages adhere to? When I run a program from command prompt and pass it arguments, what is actually creating that initial stack frame that pushes these arguments onto the stack and that invokes my main method?

# Answer
I have no idea how each system operates, and do not inquire since I usually do not need to know. However it seems rather easy to make an educated guess, based on whatever experience I have. There are many variants that exist. For example a program is often byte code to be interpreted by a virtual machine. It is all very flexible.

Usually, the program will have its own run time environment, for which some inital space can be allocated at the bottom of the stack, or anywhere else, since it will not have to move while the program executes, and also because it will exist in only one copy for a run of the program (it is not called recursively). But bottom of stack is probably simpler. Whether you want to consider that space as a frame or not is probably not very important. However, it may be simpler for the compiler/interpreter to maintain a structural consistency with frames at least for that part which may be visible to or accessed by the rest of the program, so that access is always done consistently.

This is set up by code inserted by the compiler in the compiled code (or linked to it), and is supposed to respect some standards of communication with the OS (operating system) it is intended for, so that data can be passed by the OS to the application, and returned from the application to the OS.

Such standards are usually OS dependant, and must be conformed to by the language compiler. The standard may simply imply agreement on the location were the information to be passed is stored, and possibly ways of specifying its size, upon call to or return from the program.

The stack of frame policy is needed for recursion, and it is possible only as long as you do not have functions (called also methods, sub-program, procedure ...) that can return functions as result. The first important recursive language with that property was Algol 60, and the stack of frames was invented for the implementation of Algol 60.

The stack of frame was invented to implement recursion. However it is useful even for allocating space to non-recursive function, as it is a convenient, simple, fast and easy way to allocate storage for the function only for the exact duration of that function execution.

Note that the stack policy no longer work as simply if functions can have functions as result. Then frames may have to be allocated on a heap (managed with a garbage collector) or occasionally transfered from the stack to the heap.

The OS does not create an initial frame, whether on stack or anywhere else. There must be a separation of responsibility. Some languages (at least older ones) do not even use frames, while others do use frames, but not organized as a stack. The role of the OS is to allocate some space for the program to run, to place the data to be passed to the program in some predetermined place in that space, and then to pass control to the program code (if compiled), or to the interpreter of the program (if interpreted) with a reference to the program as additional argument.

The code of the application program will then organize the allocated space, initialize what has to be, possibly move data passed by the OS in a more convenient location, etc, and then start with the code that is specific to the application, what you call main method or main program, thus creating its frame on the stack. This is usually done by a standard piece of code included by the compiler with proper parameters.

In the case of interpreted code, the program that is actually called is the interpreter, and the address of the program to be excuted is passed to it as additional data. The interpreter will organize the space, and reserve some for its own needs. Then it will start interpreting your main method/program, thus creating the stack frame for it.

But, as I said, there are many variants. Does this answer your question? or did I miss a point?
> 1 votes

# Answer
Simple: Check it. If you write a small C program, and compile to assembler (`gcc -S ...`), you'll see that C doesn't build a global frame.

But C programs aren't run just like that, the operating system really calls the ELF interpreter (here `/usr/lib64/ld-2.18.so`, see `ld.so(8)`), and that one starts the program itself. That one sets up the `main()` arguments, calls `main()`, collects what it returns, and hands it back.

If I remember correctly, the UCSD Pascal compiler did set up a stack frame for the program, just like a procedure/function. This simplifies the search for global variables (in Pascal you have a stack of nested procedures/functions, and in UCSD Pascal the search for global variables walks down the nesting frames using a static link pointer in each frame). Some Algol compilers used a display, an array of pointers to the frames at each nesting level, and had no specific global frame. This is harder to handle, but more efficient.

So the answer to your question is that it depends. In Algol-type languages (nested procedures) there might be a global frame or not. C-type languages (no nested environments) it isn't needed.
> 1 votes

---
Tags: operating-systems, compilers, stacks
---


# Question
Title: Is List comprehension equivalent to composition of filter and map?
Wikipedia says

> **A list comprehension** is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as **distinct from the use of map and filter functions**.
>
> A list comprehension has the same syntactic components to represent generation of a list in order from an input list or iterator:
>
> * A variable representing members of an input list.
> * An input list (or iterator).
> * **An optional predicate expression.**
> * **And an output expression producing members of the output list from members of the input iterable that satisfy the predicate**.
>
> The order of generation of members of the output list is based on the order of items in the input.

I think a list comprehension can be equivalently converted to combining a filter and a map in the following way:

* "An optional predicate expression." corresponds to a filter
* "an output expression producing members of the output list from members of the input iterable that satisfy the predicate" corresponds to a map

So are list comprehension and combination of filter and map equivalent?

Thanks!

# Answer
## Basic difference

List comprehension and combination of filter and map may be equivalent only in languages with **lazy evaluation**.

The reason is that, without lazy evaluation, filter and map will want to evaluate the whole lists given as arguments, while comprehensions are built from the start as structure that evaluate on a call by need basis.

Hence, comprehensions can in principle include infinite lists, and some languages allow that (e.g. Python)

Also, evaluating all elements of a list may lead to **non terminating programs**, if the evaluation of one element (not really needed) does not terminate, while the corresponding comprehension may never be asked to produce that element, and will not prevent termination of the program.

The semantics of the program may also be changed if the computation of a list element produces **side-effects**. The ccomprehension will produce the side-effects later, if at all, during the execution of the program.

## My interpretation of the wikipedia text

From what I always understood, *comprehension* means the same as *intension*, which is itself opposed to *extension* (wikipedia).

An extensional definition of a set is an actual enumeration of its elements (which works moderately well for infinite ones).

An intensional definition is the usual technique that defines the elements by specifying some property they must have.

The computational counterpart is comprehension, that provides a way of computing the elements, rather than enumerating them explicitly.

Comprehension is in a sense the Curry-Howard counterpart of intension.

The counterpart for extensional sets is a data structure that enumerates the elements explicitly.

Now, one can always define a property by extensionally giving the set of elements that have that property, so that extensional definitions can always be seen as a special case of intensional ones. But that does not seem to be the point of view of wikipedia.

The wikipedia text is not too clear, and could be more explicit (no pun intended)

My feeling is that they do want to exclude lists that are extensional, maybe for typing reasons. It is not supposed to be a specific data-structure, but an object to be used as an iterator , or as a stream possibly (it is very remindful of the literature on coroutines and generators).

Direct use of map and filter with produce extensional lists, data structures actually containing all values.

But similar constructions with the same predicates and functions in comprehensions will produce a non extensional version of the same lists.

Computationally, comprehensions will be naturally evaluated in a call by need mode, which may allow different program organizations. **A comprehension need not be finite, depending on how it is used.**

Analysis of the various languages that use the concept might confirm, or not, this understanding.
> 3 votes

# Answer
Yes. Given any list comprehension, you can always compute the same thing in an equivalent way using map and filter. However, there are some important differences between these two styles of programming.

A list comprehension is a declarative way of specifying what you want. In contrast, using map and filter is an operational specification: it specifies not just what you want, but also specifies exactly how it should be computed. Declarative specifications are arguably nicer, because they let the compiler choose the best way to compute the desired results, and because they let the programmer focus on what they want the computation to return without getting distracted by the details of how it will be computed.
> 3 votes

---
Tags: programming-languages
---