title: Does MMU contain and manage CPU caches?

text:
# Question
Title: Does MMU contain and manage CPU caches?
I read about `Virtual Memory` in various CS references, however I'm still not sure whether `CPU caches` such as *TLB*, *L1* and *L2* are integrated within `MMU`. Also I don't know if the `hit`/`miss` operations are managed by *hardware* (i.e MMU) or by *software* (i.e OS).

Does anyone have any idea?

# Answer
> 3 votes
First the term MMU refers to many different thing (more on later below). For now let's defined MMU as "virtual to physical address translation".

The caches L1 and L2 are always managed in hardware, however note that for proper operation the OS still has to interact with the cache on some occasions (notably when using DMA). An important point to be aware of is that depending on whether the caches are virtually or physically indexed, they have a different relationship with the MMU. Indeed a virtually indexed cache (typically L1) will usually be accessed by the CPU without going through the MMU and it will not only contain the data but also the security bits associated with the MMU (privilege bit, read/write, cacheability, etc). On the other hand, a physically indexed cache must come after the address translation and does not care about the MMU at all. This also applies to higher levels (L3 and L4) which are always physically tagged (and sometimes outside the CPU die).

Thus a typical CPU will have the core with a memory bus connected to the L1 (which is typically split between data and instruction, but this is not important here). On cache miss, the L1 will issue read/write on a bus that goes through the MMU then L2, L3, L4 and finally DRAM.

The MMU itself may consist of different things. The simplest forms of MMU are just segmentation and PMU (protection memory unit). More advanced forms of MMU include a TLB so as to support paging. The TLB itself is always a hardware component (essentially just another cache). However there are two very different ways of managing the TLB:

* in hardware: the MMU has a "page table walker" that can issue read to the memory to load TLB entries on a miss (this includes x86, ARM, etc)
* in software: the MMU triggers a CPU exception on a TLB miss, and then the OS does the page table walk in software, fills the TLB with the entry and return from the exception (this includes MIPS)

# Answer
> 2 votes
It depends. Low level caches and MMUs are usually quite interdependant, because they are directly in the paths of data and instruction busses.

Depending on applications, some CPUs can have a cache and no MMU (small microcontrollers) or a MMU and no cache (historical : i386, MC68030)

The MMUs deal mostly with addresses (from virtual to physical), whereas caches associate addresses ranges with data. Whether the cache is placed before, after or in between the MMU gives for cache tags and indexes either virtual or physical addresses. Virtual caches can have lower latency but generate coherency problems, whereas physical caches (placed dowstream from the MMU) have higher latency but simpler management.

*I AM SIMPLIFYING A LOT*

* TLBs are inside the MMU. They are sometimes called "address translation caches", but are not part of the caches which stores data.
* For the caches, hit/miss is managed mostly by hardware, but some special software assistance is sometimes needed for optimisation (prefetching) or to manage coherency (for example a peripheral doing direct memory accesses in a system where the cache is not automatically made coherent through hardware mechanism)
* For the MMU, some CPU families (ISA="instruction set architecture") use hardware management of TLBs, which are automatically fetched from global tables in RAM, whereas some other families uses software loading.

+ Hardware : x86, ARM, MC68K
    + Software : MIPS, Sparc64
    + Some have a bit of both : PowerPC.

---
Tags: computer-architecture, operating-systems, memory-management, virtual-memory
---


# Question
Title: Grammer Class/Production Rules of Programming Languages
I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to **2 questions**:

Doesn't variable scoping require a context-sensitive grammer? Particularly, I'm thinking of the following valid C code:

```
int main(){
    int count=0;
    count++;
    return count;
}

```

As opposed to the following invalid C code:

```
int main(){
    count++;
    int count=0;
    return count;
}

```

There could also be some other stuff involving namespaces and classes for C++, or the '.' operator for C structs, for example. I get the impression that, as a result, C (and various descendents) does (do) have context-sensitive aspects (though this may only be partial context-sensitivity). Thus question 1:

**Is it correct to say that C and some derivative languages, as well as some other languages, can only be generated by grammars with a minimum of context-sensitivity?**

**Secondly is there a relationship between language class and grammar class?**

Particularly, I'm thinking of the language BrainF\*** when I ask, since its syntax is clearly generated by a context-free grammar, yet its implementation is turing complete (assuming an implementation with an infinite tape). Does this mean that there are languages that have regular grammars, yet are turing complete?

# Answer
The issue is where you want to draw the line for what is considered "syntax". Sure, variable scoping typically requires context-sensitivity, but that doesn't need to be handled by the parser. The parser could just parse the syntax allowing out-of-scope variables, and a follow-on pass could check for out-of-scope errors. In practice, many real implementations of parser for real languages are context-sensitive, but this is handled in an ad-hoc manner by sharing state between productions and allowing "actions" to be attached to context-free productions. In particular, few (no?) languages use general-purpose context-sensitive parsing approaches. In fact, few uses general-purpose context-free parsing approaches. Instead, tooling for potentially limited classes of context-free grammars is used and, as mentioned, ad-hoc "semantic actions" lead to the parser actually being context-sensitive but this done in a way that is not captured by the context-free grammars that putatively describe the language.

In other words, a context-free grammar for a language often describes a larger language than what is actually accepted. But rejecting a program after parsing it for out-of-scope variables, say, is no different than rejecting it for having a type error. Type checking is almost never done while parsing. So what checks are done while parsing or later is usually done as a matter of convenience, and many aren't nicely described by a grammar.

The grammar complexity of the syntax has little to do with the computational complexity. For example, *every* bit string is a syntactically (and semantically!) valid Jot program, and Jot is Turing-complete.
> 3 votes

# Answer
> Does this mean that there are languages that have regular grammars, yet are turing complete?

Yes, there are. Take any Turing-compete language and use the string $1^n$ to represent the $n$th syntactically valid program in the lexicographic order. This gives you a Turing-complete language whose grammar is $1^\*$, though it's a little awkward to parse. ;-)
> 3 votes

# Answer
On top of what Derek Elkins said, C is a bit of a weird case, because its grammar is formally ambiguous. Consider this piece of code:

```
typedef int T;

void f(void) {
    T * b;
}

```

This function declares a local variable, `b`, which is of type pointer-to-`T`.

Now consider this:

```
int T, b;

void f(void) {
    T * b;
}

```

Here, the body of the function doesn't declare any local variables, but does multiply two integers (and throws the result away).

The only difference between the two is the semantic context in which it appears. If was `T` declared as a type, then the line of code in the body of `f` is a declaration. If it wasn't, then it is an expression.

It is essentially impossible to write a context-free grammar which parses C without something extra, and there are essentially two ways that C compilers can handle this. They can either feed back information from the parser to the lexical analyser so that lexical analysis can distinguish identifiers that represent type name from identifiers which don't, or parse it as an ambiguous construct and work out which one it really is later.

Actually, it's even more complicated than this, because there are four distinct namespaces of identifier in C which do not interfere. This code is completely valid, if useless:

```
typedef int T;
struct S { int T; }

void f(void) {
    T: do_something();

    goto T;

    // T is still a typedef name even though
    // it's also the name of a label
    T t = 1;

    // Same here; S is still a typedef name
    // even though it's also the name of a struct
    S s = 1;
    struct S ss = { .T = 1 };
}

```
> 2 votes

# Answer
David Richerby already showed a Turing-complete regular language consisting of numbers only. His technique can be applied to arbitrary programming languages, not just Turing machines: the programs of a programming language are enumerable, so you can number them and write a preprocessor that replaces each number with the program it stands for. Therefore, if the target language is Turing-complete, so is your new language, and it will be the language consisting of all numbers, which is a regular language.

However, this feels like cheating: those numbers don't express the structure of the programs they express. But we can also create Turing-complete regular languages in which programs do faithfully express their structure.

One example is, once again, Turing machines. For instance, we can denote Turing machines like this:

```
<machine> :== initial <state>; <finals> <transitions>
<finals> :== | final <state>; <finals>
<transitions> :== | <transition>; <transitions>
<transition> :== on <state> reading <symbol> <action>
<action> :== go left | go right | write <symbol>
<symbol> :== a | b | c | ...
<state> := q<number>
<number> := <digit> | <posdigit><number>
<digit> :== 0 | <posdigit>
<posdigit> :== 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

This is a regular language. Each of its members describes a Turing machine. Each Turing machine over the given alphabet is represented by a member of this language. (By multiple members, to be precise.) Therefore, as a notation for Turing machines, this language is Turing-complete.

You'd probably rather look at 'real' programming languages, ones that are used in practice, such as , or Common Lisp, or PostScript. You'll need one that is Turing-complete (which can be hard to determine; for instance, I'm not entirely convinced that C isn't Turing-complete, because C has dynamic linking and (I think) (with some tinkering) the linked fragments can use different pointer sizes). Then, you need to find a Turing-complete subset of that language that is regular, or can be made regular through some syntactic transformation.

Is this possible?

I think so, but this deserves a discussion on its own, as it's really a separate question.
> 1 votes

---
Tags: formal-languages, formal-grammars, programming-languages
---


title: Sort huge file algoritm

text:
# Question
Title: Sort huge file algoritm
**What algorithm should be used here to solve this problem efficiently?**

One file stores 5 year log of user IDs & their website visit dates in random order. There were around 1,000,000 users on the website and 1/4 of them were active. Active users visited the website 100 times a day on average.

You need to create a new file in which user IDs would be sorted in ascending order. For the same user IDs records should be sorted by their visit date in ascending order.

Input example:

```
1234567890 2013-03-08 12:26:09
0987654321 2013-03-09 09:23:17
1234567890 2014-01-01 00:00:34
0087645544 2015-02-03 17:45:01
0087645544 2015-01-03 11:05:06

```

Output should be:

```
0087645544 2015-01-03 11:05:06
0087645544 2015-01-03 17:45:01
0987654321 2013-03-09 09:23:17
1234567890 2013-03-08 12:26:09
1234567890 2014-01-01 00:00:34

```

**What I've tried so far:**

From what I've yet found out, the `External Sort` algorithm should be used here. But how exactly, there are different types of it (2-way, k-way etc)? And how do I apply it to the second column (which is visit date)?

# Answer
> 3 votes
I suppose the file is too large to fit in the main memory at once. In this case a basic solution is to divide the file into small enough parts so that you can sort each part individually in memory using any standard sorting algorithm. You can then merge the parts by placing a pointer to the start of each file and repeatedly advancing the pointer with the smallest element, collecting the elements into one big sorted file (you can keep track of the minimum using a heap data structure). This is called a $k$-way merge, where $k$ is the number of parts. If the heap does not fit into the main memory, then we can merge just $k' \< k$ files at a time, and then merge $k'$ of the merged files at a time, then merge $k'$ of those, and so on, until only one file remains.

I think this is more or less what the Linux `sort` command does for large files. It can also handle keys consisting of multiple columns. Check the manual of the program for the details.

---
Tags: sorting, mergesort
---


title: LL(1) parsing table construction

text:
# Question
Title: LL(1) parsing table construction
i have the following CFG

```
E -> ABC
A-> a|Cb|epsilon
B-> c|xA|epsilon
C-> y|z

```

and the First of the Non-Terminal :

```
First(E) = {a,y,z,epsilon}
Frist(A) = { a,y,z,epsilon}
First(B) = { c,x,epsilon }
First(C) = {y,z}

```

the follow of Non-Terminal :

```
follow(E)={$}
follow(A)={c,x,y,z}
follow(B)={y,z}
follow(C)={b,$}

```

my problem is how to construct the parsing table , i constructed the table and i got the following , but i think there is something missing/mistake in the table

```
    x    a    b    c    y    z    $
------------------------------------
E       ABC            ABC  ABC  epsilon
A eps.   a        eps. Cb   Cb
B  xA              c   eps.  eps.
C                       y     z

```

i hope the table is clear ,

Note : in the row A i got epsilon with both Cb in y And Cb in z , but i did not write it in the table , **is that mean the grammer is not LL(1) ??**

thank you!

# Answer
> 0 votes
Let's start with the general case. Given a production of a grammar, let's say A -\> α where α is a general string, to compute the LL(1) parsing table T the algorithm says:

```
foreach(A -> α in the grammar):
  write A -> α in T[A,b], ∀  b ∈ first(α);
  if ( ℇ ∈ first(α) ):
     write A -> α in T[A,x], ∀ x ∈ follow(A);

```

**If at the end of the algorithm you have any cell in the table T with more than one entry then the grammar is not LL(1)**, as in your case. To run this algorithm you need to compute the set of firsts and follow of a symbol. I see you did right the follows sets, but you mistake in the firsts set of E. So here is the algorithm to compute the firsts set of a symbol X:

```
if(X is a terminal symbol):
  first(X) = X;
  break;
if (X -> ℇ ∈ productions of the grammar):
  first(X).add({ ℇ });
foreach(X -> Y1....Yn ∈ productions of the grammar):
  j = 1;
  while (j <= n):
    first(X).add({ b }), ∀ b ∈ first(Yj) ;
    if ( ℇ ∈ first(Yj)):
       j ++;
    else:
       break;
if(j = n+1):
  first(X).add({ ℇ });

```

So going back to your example:

```
First(E) = {a,y,z,c,x}

```

and in the table:

```
T[E,$] = E -> ABC

```

---
Tags: compilers, parsers
---


# Question
Title: Expected number of nodes in the independent set produced by a coloring algorithm on a graph with maximal degree $k$
We have a graph with $n$ nodes and maximal degree $k$. On this graph we run a coloring algorithm that finds a maximum independent set. The algorithm colors every node green with probability $\frac{1}{k}$ and colors the node red otherwise. This is done independently for every node. Return the independent set of nodes $x$ where $x$ is green and all neighbors of $x$ are red.

> 1. Show that the expected number of nodes in the independent set is **at least** $\frac{cn}{k}$ where $c$ is some constant. (That is, $c$ does not depend on $k$).
> 2. Prove that the expected approximation ratio of the algorithm is **at least** $\frac{c}{k}$

I have no idea where to start on showing this.

I think I have figured out that the algorithm fails with probability $1-(1-\frac{1}{k})^k$ and that for any fixed node the probability for that node being put in the independent set is $\frac{1}{k}(1-\frac{1}{k})^k$. I am not sure, however, that these results are completely correct. That might be the reason I can't find a way of showing this or I could be missing something obvious. Help would be appreciated.

For anyone wondering, this is a practice problem for an upcoming exam.

# Answer
As you've computed the probability of a node be in the dependent set is $\frac{1}{k}(1-\frac{1}{k})^k$. Hence, the expected number of these nodes is $n\frac{1}{k}(1-\frac{1}{k})^k$. As $\frac{1}{e} \leq \frac{1}{k}(1-\frac{1}{k})^k$, so the expected would be at least $\frac{cn}{k}$ (for $\frac{1}{e} \geq c$).

Hence, the expected approximation ratio is $\frac{cn}{k}$ over $n$.
> 0 votes

---
Tags: algorithms, probabilistic-algorithms
---


# Question
Title: Number of seeks in an I/O efficent algroithm
A seek is the task of positioning the read/write head of the disk to the required data block, and irrespective of the size of the data block, all contiguous data can be accessed using a single seek. Seek complexity of an algorithm is defined as the number of times the algorithm leaves one data locality for another, (or, in other words, chooses to read or write a block that is not physically contiguous with the last block read or written) thereby necessitating a seek.

Now consider the simple I/O efficient Matrix Transposition algorithm. It takes $E\_{P \times Q}$ as input and outputs its transpose $F\_{Q \times P}$

### Algorithm

Let $s=\sqrt{M/2}$

**for** $i = 1$ to $\lceil P/s \rceil$

$\hspace{20px}$**for** $i = 1$ to $\lceil Q/s \rceil$

$\hspace{40px}$ $F\_{ji} = E^T\_{ij}$

$\hspace{20px}$**endfor**

**endfor**

This is in fact a tiling method, that creates two tiles (matrix) of size $\sqrt{M/2} \times \sqrt{M/2}$ for input and output matrices and after its computation it writes the tile in to Disk.

When $P, Q \leq \sqrt{M/2}$ and matrix is in *row-major* order The two matrices fit in the main memory together (which is obvious). Simply Read $E$ in, compute $F$ and write $F$. It has been claimed:

> If a seek is needed between two rows, then $S = P + Q$ (where $S$ is number of seeks) If rows follow one another contiguously, then $S = 2$.

I can't understand the above sentence. If both matrices fit in memory, then why any seeks are needed?

# Reference

This statement is in I/O Efficient Algorithms for Matrix Computations Which is a Ph.D thesis. The definition is in Page 2 and the Algorithm in Page 12.

Thanks

# Answer
> 1 votes
You're missing the trivial point that the input is on disk, and needs P seeks to be read, while the output needs to go to disk and needs Q seeks to be written. (Or 1+1 in the cases they're contiguous on disk).

This is just setting the baseline; when you exceed the internal memory size you'll need more seeks to write out temporary data structures.

---
Tags: algorithms, complexity-theory, big-data
---


# Question
Title: Transforming a bounded knapsack to 0/1 knapsack
Could I transform a bounded-knapsack problem into a 0/1 knapsack problem using the following way-:

Example: Lets says I have 3 types of items

$n=3$

$p\_j=\\{10,15,11\\}$

$w\_j=\\{1,3,5\\}$

$b\_j=\\{6,4,2\\}$

$c = 10$

Here $n$ denotes the number of types of items, $p\_j$ denotes the profit gained by including 1 item of a that particular type, $b\_j$ denotes how many items of a particular are available. And $c$ denotes the total capacity of the knapsack.

So for each item of a particular type I transform the item by including all the various ways of adding it, so for the first item, since there are 6 of them I include in my transformed array all 6 ways of taking them ie. $(1,1\*p\_j),(2,2\*p\_j)..$ and so on. Example, the expansion of the first item would be:

$(1,10),(2,20),(3,30)...(6,60)$

So now the expanded array would contain $6+4+2=12$ elements.

**Now if I use that against the standard dynamic programming approach for 0/1 knapsack problem would I be able to get the optimal solution ?**

This text(page 3) introduces an algorithm that converts a bounded knapsack to 0/1 knapsack by adding $\sum\_{j=1}^n \lceil log\_2(b\_j + 1) \rceil$ terms for each item. **I am just wondering why that even works ?**

An extract from the text reads the following:

> Notice that the transformations introduces $2^q$ binary combinations.

Can someone tell me how that works ? And if the above described way actually can lead to the optimal solution.

# Answer
> 1 votes
The approach you described does not work necessarily.

If you have the following situation (I made it simpler)

```
          | Profit | Weight | Total |
Object 1  |   5    |   3    |   3   |
Object 2  |   2    |   6    |   2   |

```

If you transform the problem according to your proposal we get the following situation

```
            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |   10   |   6    |
Object 1.3  |   15   |   9    |
Object 2.1  |    2   |   6    |
Object 2.2  |    4   |  12    |

```

If the capacity of the knapsack here is $15$ the 0-1 knapsack algorithm will give you an invalid optimal answer. Taking object 1.2 and object 1.3 with profit $25$ and weight $15$, but this items are supposed to be exclusive (if you take 2 items of element 1 you can't take 3 also).

So another approach to transform it in a 0-1 knapsack is by creating a new item per instance.

```
            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |    5   |   3    |
Object 1.3  |    5   |   3    |
Object 2.1  |    2   |   6    |
Object 2.2  |    2   |   6    |

```

The solution of this problem is equivalent to the original problem, but this don't scale very well, because if you have up to $10^9$ (or more) instance of an object, you need to create one item per instance.

Why this model works? and how can we improve it? This model works because we split each object in several group of items (each group of size 1)and it allows us to combine them in order to get any number of objects up to the maximum. For example, if one object appear 7 times we split it in $(1,1,1,1,1,1,1)$ and if we want in the optimal solution only $3$ of them, then we pick any subset of size $3$ of this set.

But we can split them in other ways, keeping the condition that we can take a subset that sums whatever sum we want up to the maximum. For example you can split $10$ like $(1, 2, 3, 4)$, and this partition is useful since you can get any sum up to $10$. There is a canonical way to split a number in $log\_2(n)$ numbers that has this property. Split the number in power of 2 starting from $1, 2, ...$ until you can't split it anymore, and add the remainder to the partition too.

For example:

```
5 -> (1, 2, 2)
10 -> (1, 2, 4, 3)
15 -> (1, 2, 4, 8)
1000 -> (1, 2, 4, 8, 16, 32, 64, 128, 256, 489)

```

Then if your original problem looks like this

```
          | Profit | Weight | Total |
Object 1  |   5    |   3    |   7   |
Object 2  |   2    |   6    |   17  |

```

We split $7=1+2+4$ and $17=1+2+4+8+2$ You transform it into this equivalent 0-1 knapsack problem

```
            | Profit | Weight |
Object 1.1  |   5    |   3    |
Object 1.2  |  10    |   6    |
Object 1.3  |  20    |  12    |
Object 2.1  |   2    |   6    |
Object 2.2  |   4    |  12    |
Object 2.3  |   8    |  24    |
Object 2.4  |  16    |  48    |
Object 2.5  |   4    |  12    |

```

The optimal answer here gives you a straight forward way to recover the original answer, and the amount of new elements you create for each different item is at most $O(log(frequency))$, where $freq$ is the instance you have of some particular object.

---
Tags: dynamic-programming, knapsack-problems
---


# Question
Title: can every LR(k) grammer be transformed to LR(1)
when i was studying compilers i came across this in Wikipedia every DCFL has a corresponding unambiguous grammar and hence can be parsed by an LR(1) parser which is the most powerful parser then what is the significance of LR(k) parsers are they more powerful than LR(1) when every DCFL can be parsed by LR(1) why do we need LR(k)?

# Answer
> 6 votes
Remember that the point of parsing (in almost all practical applications) is not simply to recognize whether or not a sentence is in a language, but rather to find the parse tree corresponding to the sentence in order to do further processing (such as compilation). Or, to put it another way, few people would purchase a "compiler" which took some input and whose output was limited to one of two sentences:

* That input is a syntactically valid C program
* That input is not a syntactically valid C program.

By a large, the desired product is an executable, not just an assurance that the program could be compiled if you had a compiler.

So, it is true that if there is an LR(k) grammar for a language, then there is also an LR(1) grammar. But it is not the same grammar (unless k is 1) and it will therefore not produce the same parse tree.

It is possible to mechanically transform the LR(k) grammar into an LR(1) grammar in a way that the original parse tree can be recovered, but it is not a procedure you want to try by hand. (Trust me on this.)

So if you have an LR(k) grammar and you want to build a parser, you could:

* Find an LR(k) parser generator
* Find a program which mechanically tranforms an LR(k) grammar into the corresponding LR(1) grammar and the code necessary to transform a parse tree produced by the LR(1) grammar into the corresponding parse tree which would have been produced by an LR(k) parse. Then feed the LR(1) grammar into an LR(1) parser generator and add the parse tree recovery code to the semantic actions.

These two tasks are not particularly different. The mechanical transformation of an LR(k) grammar into an LR(1) grammar blows up the size of the grammar much in the way that the LR(k) parse tables are much larger than the LR(1) parse tables. From a practical viewpoint, it is roughly equally difficult to find an LR(k) parser generator as it is to find an automatic LR(k)→LR(1) transformer.

---
Tags: compilers, lr-k
---


# Question
Title: How many 3-SAT expressions with up to N variables are satisfiable?
## TL;DR

There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-sat expressions with exactly 4 variables. Of those, how many are satisfiable? How did you get that number?

## Problem Statement

Assume you have a 3-SAT equation where all the clauses have exactly 3 distinct variables (i.e. $X$ and $\neg X$ will never appear in the same clause), and no clause appears more than once (i.e. some expression won't have both $(X \lor Y \lor \neg Z)$ and $(X \lor \neg Z \lor Y)$). With this construction, there are a finite amount of expressions with only N variables.

For the class of expressions with up to N variables, is there an equation to compute how many are satisfiable?

## Example of N=3

For example, with N=3, there are 254 solutions.

We know this because for N=K, there are exactly $8 \*\binom{K}{3}$ distinct clauses, as you must select three distinct variables for each clause, and 1 of 8 possible sign values for those variables (+/+/+, +/+/-, +/-/+, +/-/-, ...). If there are $8 \*\binom{K}{3}$ possible clauses, then there must be $2^{(8 \*\binom{K}{3})} - 1$ possible boolean expressions, because each clause may appear or not (so $2^{(8 \*\binom{K}{3})}$) and we have to subtract one for the case with no clauses.

For N=3, there are 255 possible expressions (using the lemma above), and only one is unsatisfiable. So there must be 254 distinct satisfiable expressions.

How about for N=4?

# Answer
> 2 votes
There is almost certainly no non-trivial formula that will tell you the number of solutions. By non-trivial, I mean something not of the form $$ \sum\_{x\_1, \dots, x\_n\in\\{0,1\\}} f(x\_1, \dots, x\_n)\\,, $$ where $$f(x\_1, \dots, x\_n)=\begin{cases}1 &\text{if $x\_1, \dots, x\_n$ satisfies the formula}\\ 0&\text{otherwise.}\end{cases} $$

Note that if we have a formula $F$ (trivial or otherwise) that tells us how many satisfying assignments there are, we can decide 3-SAT just by computing $F$ and checking whether $F=0$ (unsatisfiable) or $F\>0$ (satisfiable). This means that computing $F$ is **NP**-hard so, assuming that **P$\\,\neq\\,$NP**, $F$ is difficult to compute, which suggests that $F$ can't have any nice form.

In fact, $F$ is complete for the complexity class **#P**, which is essentially at least as hard as all of the polynomial hierarchy. This means that it seems to be quite a lot harder than "just **NP**-hard". Furthermore, we can't even approximately compute $F$ in any efficient way unless **P=NP**. Even being able to approximate $F$ with exponential additive error would allow us to distinguish between $F=0$ and $F\>0$ and thus allow us to solve 3-SAT. For example, given a formula with $N$ variables and $F$ solutions, we can create a formula with $2N$ variables and exactly the same clauses (so variables $N+1, \dots, 2N$ aren't mentioned in the formula and can take any value). This formula has $2^NF$ satisfying assignments and being able to approximate that number strictly better than $\pm 2^{N-1}$ would allow us to tell the difference between $F=0$ and $F\>0$.

# Answer
> 2 votes
I agree with other people here in that there is probably no nice closed formula to compute this number, and if there is one we don't know it yet

However, a lot of research has looked at random 3-SAT problems. It is well known that they experience a "phase transition". With $N$ variables and $M$ clauses, $N$ and $M$ big, there's a number $\alpha \approx 4.267$ such that most problems with $\frac{M}{N} \> \alpha$ are unsat, and most others are sat

That's no proof, but it's a hint that the number of satisfiable problems may be close to the number of problems with less that $\alpha N$ clauses for some constant $\alpha$. That is about $\dbinom{N}{3}^{\alpha N} \equiv N^{3\alpha N}$ when $N$ is big - very small compared to the total number of SAT problems $2^{N^3}$

Edit: Link about random 3-SAT with an estimation of $\alpha$

# Answer
> 0 votes
Well this is a way to find all solutions (and hence the number of solutions) and that is simply to try all solution. But this is terribly inefficient and there are exponentially many solutions. The reason it is very unlikely that there is an efficient algorithm for your question is because it is NP-hard, as we can reduce the satisfiability of a 3-SAT equation to computing the number of solutions. In particular, if we can solve your question in polynomial time, then we can solve 3-SAT in polynomial time by checking whether the number of solutions is greater than 0.

---
Tags: satisfiability, boolean-algebra, counting, 3-sat
---


# Question
Title: What is the error-detection-probability of CRC
I have a table which stores all serial numbers of devices in my system:

```
|------------------------|--------------------------|
|            #           |  Serial number (4 bytes) |
|------------------------|--------------------------|
|            1           |        0x????????        |
|------------------------|--------------------------|
|            2           |        0x????????        |
|------------------------|--------------------------|
|           ...          |            ...           |
|------------------------|--------------------------|
|           31           |        0x????????        |
|------------------------|--------------------------|

```

If I add a device to the system the position in the table is not predictable. If something in the system changes (e.g. add one or more devices, remove one or more devices, replace a device) I want to detect with a "high" propability that the system change. Therefor I want to use a CRC-32. In my system I have at least always 2 devices but max. 31 devcies. Meaning that the input of the CRC can vary between $2^{64}$ to $2^{992}$ different input streams.

As far as I understand:

* The minimum input should be at least 32 bits
* The most important is to use the right generator polynom. E.g.:
    + CRC-32
    + CRC-32-IEEE
    + CRC-32C
* The selection of generator polynom depends on:
    + Input stream length
    + Error-detection-feasability
    + Collision probablility
* Detection of a single bit error: All CRC's can do this
* Detection of burst errors: All $n$-bit CRC's can detect burst errors up to $n$ consecutive bits. Also meaning appending new $n$-bit to the end of the input stream.

My concerns are the collision probability of the CRC32 is to high and due to that I don't detect a change in the configuration. Therefor I want to calcualte this probabilities and my questions are:

1. Is CRC the right method to use for my use case? If not what would be the best?
2. What is the "best" generator polynom for my use case?
3. How to cacluate the error-detection-feasability or collision probability if more then 32 consecutive bits change?
4. How to cacluate the error-detection-feasability or collision probability if $x$ not consecutive (different locations in the complete input stream) bits change?

# Answer
> 1 votes
There's nothing in your requirements that forces you to use a CRC32. You could use any checksum. If the collision probability for a CRC32seems too high, use a different checksum.

For instance, if you use SHA256, you will never have to worry about collisions -- for all engineering purposes, you can treat them as impossible (something that will never happen in your lifetime). And then you won't need to worry about selecting generator polynomials or anything like that; someone else has done all that work for you. You just use the standard SHA256 algorithm.

---

P.S. Using a basic checksum algorithm will require you to recompute the checksum on the entire table any time you insert or delete one row. If that's too slow, there are a number of schemes to speed that up, such as a Merkle hash tree.

---
Tags: coding-theory, error-correcting-codes, crc
---


# Question
Title: Are dynamic and agent-based network formation models exclusive groups?
I am studying network formation models and I have seen the separation of those models into two groups (wikipedia):

* Agent-based models:

Aka game-theory based models. This distinction makes sense to me. But it mentions a "fixed number of players". Are there no game theoretic models with a dynamic number of players?

* Dynamic models:

These seem to be the ones not involving game theory. But as the name suggests they are categorized by their dynamic number of nodes.

---

So where do game theoretic models with a dynamic number of nodes fit? Are they in both classes? Why is the Erdös-Rèny Model considered dynamic? Where does this categorization come from? Why not simply use game-theoretic and non-game-theoretic as a categorization as is implied in the wiki article?

# Answer
> 0 votes
I think you're taking the list in Wikipedia too seriously. It's not a statement that "all possible methods fall into exactly one of these two categories". Rather, it's a rough categorization that might be helpful in rapidly getting a first overview of the field. Often a categorization exists because it is useful and does a reasonable job of capturing many of the methods in the literature. Categorizations don't have to cover the entire space of possible methods to be useful.

Of course one could have other categorizations, but they might lend less insight into the kinds of methods that are most typically used or studied.

Wikipedia even mentions the possibility of combining both methods in the very article you linked to: https://en.wikipedia.org/wiki/Network\_formation#Growing\_networks\_in\_agent-based\_setting.

---
Tags: graphs, game-theory
---


# Question
Title: P reduction between np-complete to np-complete
given 2 lagnauges A,B which are npc. is there a reduction function from A to B $A \leq\_PB$ ?

my idea was to say that since they are decideable, we can do this: $$ f(x) = \begin{cases} y \in B & \text{ } if x \in A \\y \notin B & \text{if }x \notin A.\end{cases} $$

is this is correct? or its not something that can be true? / depands on p equal or not equal to np

# Answer
Hint: What is the definition of "**NP**-complete"?
> 3 votes

# Answer
Rather than spoon-feeding you the answer, I will tell you how to find the answer for yourself.

I suggest you write out the definition for the notation $\le\_P$. Then, check whether your reduction meets the criteria for that notation.

> Hint: the $P$ is important.
> 2 votes

---
Tags: complexity-theory, formal-languages, turing-machines, reductions
---


# Question
Title: Finding a minimum equivalent graph of a digraph
It is said that this problem is NP-complete but I couldn't find the proof. Is there any paper on this problem or not?

# Answer
> 0 votes
This problem (or more precisely, its decision version) lies in NP, as a small enough equivalent digraph would give an NP-certificate. What remains is to show that this problem is NP-*hard*.

This paper shows that finding a minimum equivalent digraph is NP-hard even when restricted to digraphs with cycles of length at most $5$, via a reduction from SAT. This means that the problem in general is NP-hard and therefore also NP-complete.

---
Tags: algorithms, np-complete, reference-request
---


# Question
Title: Is a computer equivalent to a Turing machine or linear bounded automata?
Till date I have read that a Turing machine can do whatever a computer can.

Wikipedia Turing machine

mentions that since a real machine can have only a finite number of configurations it is equivalent to linear bounded automata.

Is this true?

# Answer
> 5 votes
A machine bounded by $\Theta(1)$ memory is a finite state automaton (As a matter of fact, proving that $\textsf{DSPACE}(\Theta(1)) = \textsf{REG}$ is a classical exercise).

We say that "Turing machines can do whatever computers can" because, as long as we keep in mind that real computers are subject to limitations in computational power, it's more useful to think of computers as imperfect implementations of a universal Turing Machine rather than perfect implementations of a finite state automaton.

---
Tags: turing-machines
---


# Question
Title: list('\a','\b','\c') prints '\x07', '\x08', '\\c'
In python3.6, I tried

```
In [60]: a = '\a'
In [61]: b = '\b'
In [62]: c = '\c'
In [63]: l =[a, b, c]

```

If test `l`

```
In [64]: l
#it output following list instead of  ['a','\b','\c']
Out[64]: ['\x07', '\x08', '\\c']

```

encapsulate them directly in a list.

```
In [70]: ['\a','\b','\c']
#it output following list instead of  ['a','\b','\c']
Out[70]: ['\x07', '\x08', '\\c']

```

What's the mechanism behind it?

# Answer
> 1 votes
Backslash is the escape character to allow you to enter non-printable characters into a string literal.

One of the most known escape sequences for example is `\n` for a newline.

`\a` is the bell character and `\b` is the backspace character.

---
Tags: python
---


# Question
Title: NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?
As a follow-up from my old question here, I'm wondering more about the equivalence proof. Intuitively, NP has been described as the class of all problems which a solution certificate can be verified in polynomial time. Let's say we have a problem $K$ in NP and we have a certificate $c\_e$ obtained externally that proves a YES or NO result for $x$.

From my understanding of the proof implications, if we have a NTM which solves $K$ in polynomial time, this implies that there exists a verifier for $K$ which takes any certificate and says whether that specific certificate is a valid "solution" for if $x$ results in YES/NO. The proof involves the fact that the NTM generates its own certificate $c\_n$ which the verifier then uses, but this has nothing to do with $c\_e$ from what I see. From my understanding, the verifier should take any arbitrary certificate (including $c\_e$) and verifies that it indeed leads to the answer. But instead, the verifier uses only the certificate $c\_n$ created by the NTM to verify whether $x$ results in YES/NO. In other words, the verifier isn't able to check any arbitrary certificate - it's only able to check the one created by the NTM.

To rephrase in case I'm not making sense – constructing a verifier, in my interpretation, means this verifier can take any certificate and check whether it's a proof for $x$. But the equivalence proof has the verifier take a specific certificate $c\_n$ created by the NTM and only checks whether that is a valid proof for $x$. So what makes the verifier able to verify for any arbitrary certificate $c\_e$?

I must be getting confused somewhere. Is there any point which labels my misunderstanding? I'd really like to fully grasp the intuition of the proof.

# Answer
A non-deterministic Turing machine has a special instruction that allows it to non-deterministically "guess" a bit. The list of bits guessed by the machine is sometimes called a *certificate*. You can imagine that the guessed bits are taken from an auxiliary tape, whose contents you can think of as a certificate.

Here is an example. Consider the problem SAT: the input is a formula, and wish to find out whether the formula is satisfiable. A non-deterministic Turing machine for this problem "guesses" an assignment, and then checks ("verifies") that it satisfies the given formula. Alternatively, the machine gets a certificate and verifies that it is a satisfying assignment for the input formula. This is exactly the same Turing machine, only the process of non-deterministic guessing is visualized as reading from an auxiliary input, which we think of as a certificate.
> 2 votes

---
Tags: turing-machines, np, nondeterminism
---


# Question
Title: How are optimal weights computed in best-Worst Multi-criteria Decision Making Method (Step 5 of BWM)? Can someone explain it with an example?
Title: Best-worst multi-criteria decision-making method Author:Jafar Rezaei, Pub: Omega 53 (2015) 49-57 BWMCD

From this example How are optimal weights (W1\*, W2\* etc) computed on Page:22 ? what are the values of WB, Wj, aBj, WW, ajW for W1 and W2 such that optimal weight of W1\* = \[0.1579, 0.2469\] and W2\* = \[0.4286, 4932\].

PS: Not much experience in Linear Programming.

# Answer
> 0 votes
The optimal weights are the solution to the optimisation problem given by model (2), i.e. the optimisation problem:

> $ \min \xi$
>
> s.t.
>
> $|\frac{w\_B}{w\_j}-a\_{B\_j}|\leq \xi$, for all $j$
>
> $|\frac{w\_j}{w\_W}-a\_{jW}|\leq \xi$, for all $j$
>
> $\sum\_j w\_j=1$
>
> $w\_j\geq0$, for all $j$

The parameters $a\_{B\_j}$ and $a\_{jW}$ are defined in the slides on pages 10 and 11. From this, your can work out the values in the particular example.

Solving the above problem may be difficult, which is why model (5), a linear approximation of model (2) is suggested.

> $ \min \xi^L$
>
> s.t.
>
> $w\_B-a\_{B\_j}w\_j\leq \xi^L$, for all $j$
>
> $-(w\_B-a\_{B\_j}w\_j)\leq \xi^L$, for all $j$
>
> $w\_j-a\_{jW}w\_W\leq \xi^L$, for all $j$
>
> $-(w\_j-a\_{jW}w\_W)\leq \xi^L$, for all $j$
>
> $\sum\_j w\_j=1$
>
> $w\_j\geq0$, for all $j$

(This is essentially model (5) from the slides, but with the absolute value inequality split over 2 inequalities)

As the variables are the values $\xi^L$ and $w\_j$, the goal function and all constraints are linear, so this is a linear optimisation problem (aka a linear program). This means that we can use the technique of linear programming to find a solution to this problem, which would give the required values.

---
Tags: decision-problem, social-networks
---


# Question
Title: Why is $3^{\log_2 n}$ the same as $n^{\log_2 3}$?
I am reading about divide and conquer algorithm at following link on page on 57 in this link. The document analyzes the running time of the algorithm. At the very top level, when $k = 0$, this works out to $O(n)$. At the bottom, when $k = \log\_2 n$, it is $O(3^{\log\_2 n})$, which, the author claims, can be rewritten as $O(n^{\log\_2 3})$.

My question is:

> Why can $O(3^{\log\_2 n})$ be rewritten as $O(n^{\log\_2 3})$?

# Answer
The two expressions are equal: $3^{\log\_2 n} = n^{\log\_2 3}$. To see this, you can use the following identities: $\log\_a b = \log\_c b/\log\_c a$, $\log\_a b = 1/\log\_b a$, and $a^{\log\_a b} = b$. Using these identities, we get $$ 3^{\log\_2 n} = 3^{\log\_3 n / \log\_3 2} = 3^{\log\_3 n \cdot \log\_2 3} = (3^{\log\_3 n})^{\log\_2 3} = n^{\log\_2 3}. $$
> 6 votes

# Answer
We will use the following facts:

* $2^{\log\_2 x}=x$; and
* $\log\_2 x^y = y\log\_2 x$.

So,

$$\begin{align} x=3^{\log\_2 n} &= 2^{\log\_2(3^{\log\_2 n})}\\ &=2^{(\log\_2 n)(\log\_2 3)}\\ &=2^{y \log\_2 n}\\ &=2^{\log\_2 n^y}\\ &=2^{\log\_2 (n^{\log\_2 3})}\\ &=n^{\log\_2 3}.\end{align}$$
> 0 votes

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


# Question
Title: Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time
Ok, so I got this for homework and been struggling for a while now. The full assignment requires this:

While **N = number of elements** in given array and **n = number of different elements**,

**init(S,A\[1...N\])** \- accept an array A as input and initialize S data structure in O(Nlogn) time

**insert(S,x)** \- insert the key x to S in $O(\log n)$ time

**freq(S,x)** \- return the number of appearances of x in S, in O(logn) time

**mostFreq(S)** \- return the most frequent element in S, in O(1) time

I was thinking of using a balanced bst, inserting elements from the array one by one, but it would be $O(n \log n)$ and not O(Nlogn) as required.

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

as for the last function (mostFreq) - I have no idea how to deal with it whatsoever. I guess it involves holding some variable that will be updated on each insert, but I got nothing.

So it's clear I'm pretty lost :) any suggestions?

# Answer
> As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

That's exactly the solution I would go for.

Store a mapping of $\langle x, freq\_x\rangle$ in the BST. Because each $x$ will be unique in the bst you will be able to search for the frequency with just $x$.

insert becomes

```
if x is in BST then
    replace <x, freq> with <x, freq+1> in bst
    if freq+1 > max_freq then
        max_freq := freq+1
        max_x := x
    endif
else
    insert <x, 1> into bst
    if max_freq = 0 then
        max_freq := 1
        max_x := x
    endif
endif

```

You don't really need a tree, instead a hashtable would drop the complexity down to O(1) for every access and O(N) for init.
> 0 votes

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


title: Hamming distance and parity

text:
# Question
Title: Hamming distance and parity
For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: $$2^p \geqslant p + k + 1$$ This because at least $p$ bit are required to code $n$ error on a single bit $+ 1$ for the "no error" word.

For an Hamming code with distance $d$ you can detect $d-1$ bit of errors and correct $\lfloor d-1/2 \rfloor$ bit of errors.

However you can have **SEC (7,4)** and **SEC (12,8)** with the same Hamming distance $d = 3$ but the the first has $p = 3$ bit for the parity while the second has $p = 4$ bit for the parity.

The first question is what does it mean for an Hamming code H having an Hamming distance = 3 ? Does it mean that all $k$ or $n$ bit of data are required to have $d=3$ with each other ?

What is the relationship between the parity and the distance in an Hamming code ?

# Answer
> 1 votes
A (binary) code $C$ is a collection of binary strings of some length $n$, known as *codewords*. The minimal distance of $C$ is the minimum Hamming distance between (different) codewords. Hamming codes have minimum distance 3, which means that (1) every two codewords differ in at least 3 places, (2) there exist two codewords which differ in exactly 3 places.

Hamming codes are examples of an important class of codes known as *linear codes*. You can think of linear codes in many ways:

1. A linear code of length $n$ is a linear subspace of $\\{0,1\\}^n$. The dimension of the code is known as the *rate* $k$.
2. A linear code is a code which is closed under XOR, that is, the XOR of any two codewords is again a codeword. It turns out that the number of codewords is always a power of 2, say $2^k$. The parameter $k$ is known as the *rate*.
3. A linear code is a way of encoding $k$-bit messages using $n$ bits. The original bits of the message are put in fixed places, and every other bit is an XOR of a certain fixed subset of the message bits. For example, the SEC(7,4) code encodes a 4-bit message $x,y,z,w$ using 7 bits: $$ x \oplus y \oplus w, x \oplus z \oplus w, x, y \oplus z \oplus w, y, z, w $$

The minimal distance of a linear code is also the minimal Hamming weight of a non-zero codeword. So the fact that Hamming codes have minimum distance 3 means that (1) every non-zero codeword has at least 3 ones, (2) there exists a codeword having exactly 3 ones.

We have mentioned three parameters: the length of the code $n$, the rate of the code $k$, and the minimal distance $d$. There is no exact relation between these three parameters, though there are various bounds relating the three quantities. One of these bounds is the Hamming bound: $$ \sum\_{\ell=0}^{\lfloor \frac{d-1}{2}\rfloor} \binom{n}{\ell}\leq 2^{n-k}. $$ For example, for the SEC(7,4) code this gives $$ \binom{7}{0} + \binom{7}{1} \leq 2^{7-4}. $$ You can check that equality holds, and indeed this is the case for all Hamming codes. Codes for which equality holds are called *perfect codes*. Apart from a few trivial and exceptional cases, Hamming codes are (essentially) the only perfect codes.

---
Tags: error-correcting-codes, hamming-code, bit-manipulation
---


# Question
Title: Why RAID 2 would ever be used instead of RAID 3?
According to this source and Tanenbaum's Modern Operating Systems a possible implementation of RAID 2 consists of 4 data disks and 3 disks which contain parity bits. Why don't we need 4 disks that stores parity bits, why just 3?

Also in RAID 3 we need just one disk for storing parity bytes for 4 data disks. What would be any potential interest in RAID 2 over RAID 3? As far as I understand read/write speeds are the same in RAID 2/RAID 3.

# Answer
RAID 2 doesn't use parity: it uses a Hamming code. This allows error correction as well as error detection. Remember that a parity bit is just a bit that tells you whether the sum of the other bits is odd or even. It wouldn't make sense to have more than one of those because they'd all be telling you the same thing.

If you're using RAID 3 with four data bits and one parity bit, all you can do is detect when an odd number of bits have changed. You read the four data bits, add them together (mod 2) and, if the answer isn't equal to the parity bit, then you know that something has been corrupted. But you don't know *what* has been corrupted: it could be any one of the data bits, or it could even be the stored parity bit. All the disc controller can say is, "Sorry, but something's gone wrong and I can't give you the data you wanted." Note that, if *two* bits get corrupted, you won't notice since, e.g., 1+0+0+1=0+0+1+1.

In contrast, RAID 2 would store three error-correcting bits along with the four bits of data. Having the extra two bits gives you more power: you can now detect *and fix* any single-bit corruption. This works by looking simultaneously at all seven bits (four data, three EC). Because of the way the code is designed, any two valid combinations must differ by at least three bits. If you see a valid combination, you're happy. If you see an invalid combination that's only one bit different from a valid one, then it must be at least two bits different from every other valid combination, so you can fix the error on the assumption that it's more likely that one bit was corrupted than two. (See Wikipedia for full details). We assume that three bits being corrupted simultaneously is so unlikely that it will never happen: in principle, that could corrupt one valid combination into a different one.

The above assumed that two-bit corruptions are much less likely than one-bit corruptions. An alternative RAID 2 set up when two-bit corruptions aren't *so* rare would be to say "I don't know if this invalid combination was a one-bit or two-bit error but something's gone wrong." That would allow you to detect all one-bit and two-bit errors, but not correct anything.
> 6 votes

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


# Question
Title: How to show that some problem is in NP and that it's NP-complete
I need some help with the following question:

> Recall the *subset sum problem*, which is known to be NP-complete:
>
> *"Given a finite set of natural numbers and a number $n$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."*
>
> We consider the *great subset sum problem*:
>
> *"Given a finite set of natural numbers adding up to $N$ and a number $n \> N/2$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."*
>
> a. Show that the great subset sum problem is in NP by giving the notion of certificate and arguing that the certificate can be checked in polynomial time.
>
> b. Show that the great subset sub problem is NP-complete.
>
> *(Hint: extend the set by adding one large number.)*

This was my "proof" but I think it lacks details and I feel it's wrong because I didn't use the hint for part B. Can someone tell me if did something wrong? But please, don't get use too many technical terms as we mainly use text and I might not understand your explanation.

---

**a)** A certificate for the great subset sum problem is a subset of the given set of natural numbers.

Certificate checking is done by adding up the numbers in the subset and comparing the result to the number **n** without forgetting the extra requirement that **n** \> $N/2$.

Clearly, if **m** is the size of the original set of numbers (i.e., the size of the input), then the verification requires at most $m-1$ additions, one comparison, and final checking step, so it can be done in $O(m)$.

$O(m)$ because of the following: Adding 2 numbers takes O(1), you have to do that m-1 times. Then do one computation which also takes O(1) and finally do one comparison which also takes O(1), so in total that's O(m).

**b)** From the first part of the exercise it already follows that the great subset-sum problem is in NP.

To show that the great subset-sum problem is NP-complete, it remains to prove that it is NP-hard. The latter we can do by showing a polynomial-time reduction from the subset sum problem to the great subset sum problem.

Let **S** be a set of natural numbers and let **n** be a natural number. Let $S^\prime$ be obtained from **S** by dividing every number in **S** by **2**; clearly, $S^\prime$ can be obtained by an algorithm whose running time is linear in the size of **S**. Note that **S** has a subset such that the numbers in that subset add up to **n** if, and only if, $S^\prime$ has a subset such that the numbers in that subset add up to **n** where **n** \> $N/2$.

So, we have now presented a polynomial-time reduction from the subset-sum problem to the great subset-sum problem. Since the subset sum problem is NP-hard, it follows that the great subset sum problem is NP-hard too.

---

# Answer
When performing a reduction it is important to keep in mind exactly what you are doing. In particular you are trying to reduce *from* a known hard problem (here subset sum, $\mathsf{SS}$) *to* your problem (here great subset sum, $\mathsf{GSS}$) such that yes-instances of the hard problem map to yes-instances of your problem and no-instances map to no-instances.

As mentioned in the comments, if you simply divide each number in $S$ by two (and also divide $n$ by two) you *do not* get an instance of $\mathsf{GSS}$; it might not be the case that $\frac{n}{2} \geq \frac{N}{2}$.

Please think about the problem a bit more before looking at the solution below.

> Let our $\mathsf{SS}$ instance be $S = \\{s\_1, ..., s\_k\\}$ with $\sum\_{s\_i \in S} s\_i = N$ and target $n$. We construct the following $\mathsf{GSS}$ instance: $S' = \\{s\_1, ..., s\_k, N\\}$ with target $n' = N + n$. Observe that this *is* a $\mathsf{GSS}$ instance since $n' \geq \frac{1}{2}\sum\_{s \in S'} s = N$. It remains to show that yes-instances map to yes-instances and no-instances map to no-instances. If some subset $A \subseteq S$ adds up to $n$ then $A \cup \\{N\\}$ adds up to $N + n$. If not then no subset of $S'$ adds up to $n'$ since $n' \> N$ so this subset must contain $\\{N\\}$ and a subset of $S$ which adds up to $n$.
> 0 votes

---
Tags: complexity-theory, np-complete, np-hard, np, subset-sum
---


title: Does starvation freedom imply progress?

text:
# Question
Title: Does starvation freedom imply progress?
The above answer taken from the book https://www.amazon.com/Operating-Systems-Sibsankar-Haldar/dp/8131730220 says starvation freedom may not imply progress as processes can be deadlocked.

I think that starvation freedom implies deadlock freedom so there is no chance of deadlock and progress is also satisfied.

Is the answer in the picture correct ?

# Answer
It depends on how exactly you define "starvation freedom" and "liveness."

I believe the book is talking about starvation freedom from the perspective of the OS scheduler, which usually does not know about locks managed by user processes. So, the book is partially right (in some context).

Your definition is more broad and is what someone working in distributed systems would think (see https://en.wikipedia.org/wiki/Liveness. Note the important assumption "All processes are assumed to correctly use the mutex...").

However, I'd think that "liveness implies starvation freedom," but there's no justification in the book for the first statement in the answer.
> 1 votes

---
Tags: operating-systems, synchronization, deadlocks
---


# Question
Title: Finding unique cubiods with given volume
I have an interval of intigers and I need to find all unique cuboids which have volume that falls within said interval.

I came up with a loop that goes over all uniqe combinations of 3 numbers (size of the cuboid) (1x1x1, 1x1x2, ...; also 2x1x1 is considered the same as 1x1x2) from 1 to the upper range of the interval. And then checks if the calculated volume falls within the interval. This solution works perfectly if the upper range isnt is too large. But if the interval ends in thousands the solution becomes very slow.

I am not really interested in code as I am in an algorithm on how to solve this differently. How would you go on about solving this?

# Answer
**Hint.** Once you've chosen the first two dimensions, it's trivial to calculate what (if any) range of values for the third dimension give a volume within your interval.
> 1 votes

# Answer
You could factorise each integer target volume in the range. Then every way of producing a cube of the target volume corresponds to a way of partitioning its factors into 3 sets, with each set corresponding to one dimension. (Note that this can still produce duplicate cubes in cases where some factor appears more than once, like 12 = 2\*2\*3 -- to deal with this, treat each distinct factor as an item that you can choose in a certain quantity, rather than treating copies of the same factor as distinct items that you can choose either once or not at all.)
> 0 votes

---
Tags: algorithms
---


# Question
Title: Trying to understand a way to split an AVL tree in O(log n)
I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn right. Later, you merge all the marked subtrees.

Now, i've drawn a complete BST with 15 nodes and tried the algorithm by splitting node 7:  Now, I mark nodes 2 and 5, try to merge them, and the left tree does not have node 6 in it. The description about how to split trees is not complete and I don't know what i'm supposed to do with it.

# Answer
So, basically, what you are saying, is that you have a bunch of left leaning avls and want to merge them? That's what I understand from the first graph. You can merge and rebalance them in O(log(n)) time.

What I did was to make each tree a right child of the previous one, and then you start to rebalance at the root and moving to the right, with the rebalancing being a single or double rotation depending on the balance factors of the node and its children, and then you move to the right children and repeat.

```
@staticmethod
def ReBalanceRightist(parent, node):
    assert parent is not None
    while node is not None:
        AvlNode.UnlinkNodes(parent, node)
        node = AvlNode.ReBalance(node)
        AvlNode.LinkNodes(parent, node)
        parent = node
        node = node.right

```

First you unlink them, because you don't know if node will still be the root of that subtree, rebalance, and set the result of that rebalance as the new child. Then rinse and repeat.

This works with O(log(n)) complexity as each left subtree is already balanced, and you just need one rebalance operation to balance a node (O(1)), then you repeat this along the branch, and the branch length is at most log(n), so you get O(log(n)) complexity.

I had to implement a remove\_below(x) and remove\_above(x) functions for an Avl, so that all the nodes with keys lesser than x or bigger than x would be removed from the tree, respectively, and the problem in the end is the same, which is, how to merge k right/left leaning trees.

You can look at the code here:

https://github.com/Izikiel/AvlPython
> 1 votes

# Answer
I think the devil is in the phrase "every left son of every node where you turns right". If you look at the picture on the slide each marked subtree has a node attached at the top. So in your example you mark 2 as the left son of 4 and 5 as the left son of 6. Now in the merging process you need to include 4 and 6 as well as the subtrees rooted at 2 and 5
> 1 votes

---
Tags: algorithms, data-structures, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: Can SSL be hacked if we know some of plain data?
As I know, SSL/HTTPS is two stage, first stage is public key encryption/decryption which transfers key of the second stage which is symmetric. It is true we don't have key, but we can have some of plain data and guess key so (at least some of messages), do you agree it is possible so?

Thanks!

# Answer
> 2 votes
No, it is not possible. Any modern encryption algorithm is designed so that even even if you have some ciphertext and part of the corresponding plaintext, it is *unfeasible* to find any information (other than the length) about the part of the plaintext that you don't know. This is true even if you get to choose all of the plaintext except one bit, and you get the corresponding ciphertext and you want to find the bit that you don't know. This property is called indistinguishability under chosen-plaintext attack (IND-CPA for short).

*Unfeasible* is a technical term, meaning that it requires an amount of computation that cannot be performed in practice. The theoretical definition is that the complexity of the attack is more than polynomial over the size of the key. In practice, key sizes are chosen so that it would take more than the total computational power available in the world for more than a lifetime to break the key (for example, it would take a billion PCs more than the age of the universe to break a 128-bit key).

Note that I simplified the definitions a bit; the actual definitions are fairly complex and subtle. If you want to understand them precisely, read a cryptography textbook.

In practice, this assumes that:

* There is no flaw in the protocol, such as using the same key for different purposes or accepting invalid output, that could lead to the implementation acting as an oracle.
* There is no flaw in the implementation, that could lead to secret information leaking directly or indirectly.
* The algorithm genuinely has the IND-CPA property. It is in fact not known whether any encryption algorithm (apart from the very unwieldy one-time pad) has this property. In practice, people use algorithms that cryptographers have spent many years trying very hard to break, and failed.

In practice, most security flaws related to cryptography are due to implementation bugs. A minority are due to protocol weaknesses, and modern protocols tend to be designed with more attention than protocols designed 20 years ago. Flaws in modern encryption algorithms are extremely rare.

---
Tags: cryptography, security
---


# Question
Title: Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)
I read *The Complexity of Theorem-Proving Procedures* by Stephen A. Cook (1971). Cook explains how to create a boolean formula $\Phi$ from $(M,w)$, where $M$ is a non-deterministic Turing machine that always halts in a polynomial number of steps and $w$ is a string in $\Sigma^\*$ so that $\Phi$ is satisfiable if and only if $M$ accepts $w$.

* Is every accepting path/route of $M$ with input $w$ a satisfying assignment of $\Phi$?
* Is every rejecting path/route of $M$ with input $w$ a falsifying assignment of $\Phi$?
* Is the number of satisfying assignments of $\Phi$ equal to the number of accepting routes/paths of $M$ with input $w$?
* Is the number of falsifying assignments of $\Phi$ equal to the number of rejecting routes/paths of $M$ with input $w$?

# Answer
The reduction in the Cook-Levin theorem is parsimonious, i.e. it preserves the number of witnesses. You should note that $\Phi\_{M.w}$ does not talk in terms of computation paths, it is simply a boolean formula. However, if you look at the details of the reduction, you will see that each accepting path for $w$ corresponds to a satisfying assignment for $\Phi$, and vice versa. Once you show that $\Phi\_{M,w}$ treats its variables as a possible path for $M$ on $w$, and is satisfied iff that path is accepting, the first three questions are naturally answered in the positive.

The reduction does not preserve the number of "non-witnesses" (note that the total number of possible witnesses for the input and output is not necessarily equal, hence a parsimonious reduction might change the number of "bad" witnesses), so the last point is wrong. As an example, suppose $M$ accepts $w$ on every path (hence it has zero rejecting routes), but any assignment to the variables of $\Phi\_{M,w}$ which does not represent a valid computation of $M$ on $w$ is not satisfying.

Note that it is an open problem whether every NP complete problem has parsimonious reductions (i.e. for every $\mathsf{L\in NP}$ there exists a parsimonious reduction from $L$ to the complete language). Most classical NP complete problems are known to have such reductions, but this is not known in general, see this related post.
> 4 votes

---
Tags: complexity-theory, turing-machines, satisfiability, strings, nondeterminism
---


title: Why is RTS/CTS optional?

text:
# Question
Title: Why is RTS/CTS optional?
I was reading in Wikipedia about it and one of the main things that were pointed out was that it is only an optional mechanism. This bugs me more than it should as I cannot find any information that I can understand about it.

Can anyone explain to me like I am a five-year-old why are they optional?

# Answer
RTS/CTS are signals used to control data flow when the input and output rates are different. When the rates are identical then there is no need for flow control.
> 1 votes

# Answer
Besides RTS and CTS, there are a few other "optional" signals such as DTR, DCD,...

These signals are mostly about checking if the other end of the cable is ready. Ready can mean that the internal buffer is not full, or related to some hardware condition, such as being powered or that the phone line is up ("DCD"=Data Carrier Detect).

These signals can be made optional in several cases :

* The buffers are very large, or the datarate is low, and there is no practical risk of losing data. The endpoints are always ready. This is the case nowadays with computers used as terminal emulators over asynchronous serial lines.
* Some flow control mechanism is used to signal over the data lines when to start and pause transmissions : For example XON / XOFF https://en.wikipedia.org/wiki/Software\_flow\_control
* The protocol has messages and answers, for example an initiator sends a message of predefined lenght, and waits for the answer of the target. There are many other options, such as time-triggered communications. Serial lines can be used for many purposes. There are traditional terminal or teletype connections, there are also gazillions communications protocols for embedded or industrial applications. The protocols can be designed to not need hardware flow control signals.
> 2 votes

---
Tags: algorithms, computer-networks, communication-protocols, protocols
---


# Question
Title: Can we apply binary search for finding key 'x' in unsorted array?
Suppose we are given A, an array of size n, comprised of an increasing sequence of numbers followed immediately by a decreasing one. What is worst case time complexity of optimal algorithm to determine if a given number x is in the array?

The explanation given on the this site is confusing to me. How we can apply binary search on unsorted array?

They have provided following explanation =\> This is an application of Binary search, which has time complexity $Θ(log n)$ in worst case.

# Answer
> 3 votes
We can find the break point (where the type of sequence changes) in theta(log n). Then we can search individually on both sides of the break point (each of which is a sorted sequence). So overall theta(log n) only.

# Answer
> 2 votes
First use binary search to find the index, where the ordering changes from increasing to decreasing. Now you can use binary search on both partitions of the array.

---
Tags: algorithms, arrays, searching
---


# Question
Title: Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?
**CNFSAT** is the language of all strings that are encoding of **satisfiable** boolean formula in conjunctive normal form while **CNFFAL** is the language of all strings that are encoding of **falsifiable** boolean formula in conjunctive normal form.

Any boolean formula is **satisfiable** if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to **true**.

Any boolean formula is **falsifiable** if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to **false**.

**CNFFAL** is in $\Bbb{P}$, because the deterministic Turing machine that decides **CNFFAL** in polynomial time only needs to find falsifiable clause and deciding whether or not disjunction of literals is falsifiable is as hard as deciding **1SAT** that is deciding the satisfiability of conjunction of unit clauses, where each unit clause is single literal, and it is also in $\Bbb{P}$.

Because of the fact that $\Bbb{P\subseteq NP}$ **CNFFAL** is also in $\Bbb{NP}$ and also non deterministic Turing machine to decide **CNFFAL** is to guess and choose an truth assignment non deterministically and accept if the input boolean formula evaluates to false, reject otherwise.

According to the fact that $CNFFAL\in\Bbb{NP}$ and to the paper of Cook, Levin and Karp that was submitted in 1971, it is also true that $CNFFAL\le\_PCNFSAT$.

I want to know if $CNFFAL\le\_PCNFSAT\implies CNFSAT\le\_PCNFFAL$.

In other words I want to know if it is also true that $CNFSAT\le\_PCNFFAL$, because I read the 1971 paper of Cook, Levin and Karp and as I understood, the deterministic polynomial time reduction from an arbitrary NP language to satisfiability problem is done by first describing the non deterministic Turing machine that decides the arbitrary NP language in polynomial time and then there is polynomial time deterministic algorithm to generate the boolean formula that is **true** on every **accept** path/route of the non deterministic Turing machine for the input string and it is **false** on every **reject** path/route of the non deterministic Turing machine for the input string.

Therefore the string is in the arbitrary NP language if and only if the non deterministic Turing machine that decides the arbitrary NP language in polynomial time accepts the string and the non deterministic Turing machine accepts the string if and only if there exists an accept path/route, i.e. the non deterministic Turing machine has an accept path/route for the input string and there exists an accept path/route or the non deterministic Turing machine has an accept path/route for the input string if and only if the boolean formula is satisfiable.

Let $NTM\_{CNFFAL}$ be the non deterministic Turing machine that decides **CNFFAL** in polynomial time as described above.

Therefore if the input boolean formula $\alpha$ is **falsifiable** then there exists an **accept** path/route, i.e. $NTM\_{CNFFAL}$ for $\alpha$ as input has **accept** path/route, but if $\alpha$ is also **satisfiable** then there also exists **reject** path/route, i.e. $NTM\_{CNFFAL}$ also has **reject** path/route for $\alpha$, but if $\alpha$ is **unsatisfiable** then **all** paths/routes of $NTM\_{CNFFAL}$ are **accept** and therefore the boolean formula $\beta$ generated from $NTM\_{CNFFAL}$ is **tautology** and not **falsifiable**.

Therefore $\alpha$ is **unsatisfiable** if and only if $\beta$ is **tautology**.

Therefore $\alpha$ is **satisfiable** if and only if $\beta$ is **falsifiable**.

So my question is does $CNFSAT\equiv\_PCNFFAL$?

# Answer
> 1 votes
No, $CNFFAL\le\_P CNFSAT$ doesn't appear to imply $CNFSAT\le\_P CNFFAL$, as far as we know.

As you say, we know that $CNFFAL\le\_P CNFSAT$ is true. However, $CNFSAT\le\_P CNFFAL$ is true if and only if $P = NP$.

Consequently, the claim $CNFFAL\le\_PCNFSAT\implies CNFSAT\le\_PCNFFAL$ is logically equivalent to the claim that $P=NP$. There is no known proof that $P=NP$ (and many would consider it surprising if that is true).

I didn't understand why you think the implication does hold. I couldn't quite follow your reasoning. The notation $\beta$ is never explained clearly (I don't know what you mean by "the boolean formulated generated by a NTM"; NTMs don't generate boolean formulas, so that would need to be defined more clearly). It's hard to know what you might be thinking, but if I were forced to speculated, I'd guess that the flaw in your reasoning might have something to do with the situation where $\alpha$ is both satisfiable and falsifiable. Then it's true that $NTM\_{CNFFAL}$ has both an accept path and a reject route, but so what? It's not clear why that would imply anything interesting.

# Answer
> 0 votes
If CNFSAT \<\_P CNFFAL that would make CNFFAL NP-complete but CNFFAL is in P. So such reduction is not possible otherwise CNFSAT would belong to P.

---
Tags: complexity-theory, turing-machines, reductions, satisfiability, nondeterminism
---


title: algorithm for list display

text:
# Question
Title: algorithm for list display
I'm working on a website which gets a list of objects like this:

`Object { model: "modelhandler.comment", pk: 5, fields: Object }`

where the field objects contains this:

`Object { user: "TestUser",id: 6, video: 7, description: "test new video comment lol", reply_to: 5, uploaded: "2018-01-12T09:14:24.281Z", updated: "2018-01-12T09:14:24.281Z", indent: 0}`

The goal of the site is to find all comments which have reply\_to set to a number (not null) and increment it's indent value and all it's children's indent value.

for example consider this list of comments:

```
comment 1 (id: 1, indent: 0, reply_to: null)
comment 2 (id: 2, indent: 0, reply_to: null)
comment 3 (id: 3, indent: 0, reply_to: 1)
comment 4 (id: 4, indent: 0, reply_to: 3)
comment 5 (id: 5, indent: 0, reply_to: 1)
comment 6 (id: 6, indent: 0, reply_to: null)

```

Now I want to run trough the list and set all indent values according to the reply\_to value. so the list becomes:

```
comment 1 (id: 1, indent: 0, reply_to: null)
comment 2 (id: 2, indent: 0, reply_to: null)
comment 3 (id: 3, indent: 1, reply_to: 1)
comment 4 (id: 4, indent: 2, reply_to: 3)
comment 5 (id: 5, indent: 1, reply_to: 1)
comment 6 (id: 6, indent: 0, reply_to: null)

```

Now this has to happen inside a for loop which allready runs trough the list once:

```
for(var i = 0; i < array.length; i++) {
    //do stuff here
    //set the indent value here
    if(reply_to)
        indent++;

    //do more stuff here
}

```

this was my idea for achieving this but it will only increment indent once as it travels trough the list only once. is there a better way to do this?

# Answer
> 1 votes
Assuming the replies are guaranteed to be below the lines they're replying to, you can do this.

```
if (reply_to != 0)
{
    array[i].indent = array[reply_to].indent + 1;
}

```

---
Tags: algorithms
---


# Question
Title: Why do we need so many sorting algorithms?
We have some best sorting methods like quick sort, merge sort etc., then why we need other sorting methods which perform poor?

# Answer
> 9 votes
Some kind of sorting algorithms may end up being visually more pleasing, giving nicer intermediate steps allowing for visual inspection of data where a human can recognize where in the process one is and analyze what goes wrong and sanitze the data accordingly.

I know I have used sometimes some costly sorting algorithm because it came in handy during game programming, giving just the right effect(revealing something on monitor, sorting inventory, etc...) on screen without it looking computer generated.

Like T.S. Elliot said:

> The journey, Not the destination matters...

To see what I mean(source of images https://i.stack.imgur.com/BZIvm.jpg):

> !
>
> !
>
> !
>
> !
>
> !
>
> !
>
> !

# Answer
> 0 votes
We probably don't need all the O(n^2) ones. But some of them can be useful during the end-game. For example, a popular C++ standard library employs merge-sort to implement std::stable\_sort, but switches to insertion-sort when a sub-array has length 32 or less.

But the real reason that we have "so many" sorting algorithms is that throughout the years, no beginner has been able to resist the urge to invent their own sorting algorithm.

---
Tags: algorithms, sorting
---


title: $P/poly$ as oracle to itself?

text:
# Question
Title: $P/poly$ as oracle to itself?
How can we show $P/poly^{P/poly}=P/poly$?

What tricks are generally used for self lowness of a class such as $BPP$, $SPP$ etc?

# Answer
There are no general tricks for proving self lowness, note that the classes that you yourself mentioned are very different in nature. Recall that $L\in P/poly$ iff there exists a Turing machine $M(x,y)$, which runs in time polynomial in $|x|$, and an advice sequence $\\{\alpha\_n\\}\_{n\in\mathbb{N}}$, such that for all $x\in\Sigma^\*$ it holds that:

$x\in L \iff M\left(x,\alpha\_{|x|}\right)=1$

$L\in P/poly^{P/Poly}$ if the machine $M$ above can also query membership to some other language $O\in P/Poly$, so there exists a machine $M\_O(x,y)$ which satisfies the above conditions with advice sequence $\beta\_n$.

To show that $L$ lies in $P/Poly$, the natural approach would be to use $M$ with the same advice sequence $\alpha\_n$. The problem arises when $M$ queries its oracle $O$ on some string $s$, what do we do then? Here the natural approach would be to simulate $M\_O$ on $s$, but what advice should we feed to $M\_O(s,\cdot)$ ? Suppose $M$ runs in time $n^c$, then on a length $n$ input, $M$ can only query its oracle on strings of length $\le n^c$. This leads to the following solution, on length $n$ inputs, your $P/Poly$ machine for $L$ would use the advice $\left(\alpha\_n,\beta\_0,\beta\_1,...,\beta\_{n^c}\right)$, and simulate $M$ on the input with advice $\alpha\_n$. Whenever $M$ queries the oracle on a string $s$, simulate $M\_O(s,\beta\_{s})$ to obtain an answer, and continue executing $M$.
> 1 votes

# Answer
It been a while since I studied complexity, so I may be confusing with notations.

Take language in $A^B \in P/poly^{P/poly}$, decided by TM $M$. We know that $B \in P/poly$, and hence theirs exist another TM $M'$ which deciding $B$.

Build a $P/poly$ TM $T$ thats simulates $M$. Whenever $M$ query the oracle on input $(x,a)$, $T$ can simulate $M'$ on $(x,a)$ and return whatever it does, and continue the simulation.

The running time remains polynomial.
> 0 votes

---
Tags: complexity-theory, complexity-classes, oracles
---


# Question
Title: Is $O(\log_2 n)$ close to $O(n)$ or $O(1)$?
We know that asymptotically $O(1)$\< $O(\log\_2 n)$ \< $O(n)$, but $O(\log\_2 n)$ is asymptotically close to $O(n)$ or $O(1)$?

# Answer
> 2 votes
As far as I understand your question, you have to take a look at the differences: $O(\log n - 1) = O(\log n)$ versus $O(n - \log n)$. Since

\begin{eqnarray} n - \log n & \stackrel!\> & \log n\\ n & \> & 2 \log n\\ \end{eqnarray}

you have $O(\log n) \subset{} O(n - \log n)$. The difference to $O(n)$ grows faster than the difference to $O(1)$.

Thus, $O(\log n)$ is closer to $O(1)$ than $O(n)$.

# Answer
> 1 votes
In some areas, we use $\widetilde O$ instead of $O$ to ignore $\mathsf{poly}(\log n)$ terms. The reason is that $\mathsf{poly}(\log n)$ terms are very small compared to polynomial terms such as $n^\epsilon$, even for an arbitrarily small $\epsilon\>0$.

So, roughly you can say $O(\log n)$ is closer to $O(1)$.

# Answer
> 0 votes
Here is a similar question:

> I know that $1 \< 10 \< 10^6$, but is $10$ close to $1$ or to $10^6$?

I'm not sure what kind of answer you expect – you'll have to explain when two functions $f,g$ are asymptotically close. Often we consider $f,g$ to be asymptotically close if $f = \Theta(g)$. Other times, we also allow logarithmic differences, that is, we say that $f,g$ are asymptotically close if $f = O(g \log^C g)$ and $g = O(f \log^C f)$ for some constant $C \> 0$. Under both of these definitions, $\log n$ is asymptotically close to neither $1$ nor $n$.

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


title: Simplifying sum of falling factorials

text:
# Question
Title: Simplifying sum of falling factorials
I wrote the worst algorithm in the world. Doesn't matter what it does. I have just a question about folding formula for it's time complexity into some shorter form which would be easier to compute. So I concluded that the equation for the number of operations is as follows:

$$n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \dots + n!\\,.$$

**Can we fold this sequence to some nice equation which will give us exact number of operations needed to complete this algorithm?**

# Answer
You gave the closed form for the number of operations: $$ \sum\_{m=1}^n n(n-1)\cdots(n-m+1) = \sum\_{m=1}^n \frac{n!}{(n-m)!} = n! \sum\_{m=0}^{n-1} \frac{1}{m!}. $$ We can estimate this sum as follows: $$ n! \sum\_{m=0}^{n-1} \frac{1}{m!} = n! \left(e - \sum\_{m=n}^\infty \frac{1}{m!}\right) = en! - 1 - \frac{1}{n+1} - \frac{1}{(n+1)(n+2)} - \cdots = \\ en! - 1 - O\left(\frac{1}{n}\right). $$
> 4 votes

---
Tags: algorithm-analysis, discrete-mathematics
---


title: Flexible Team Orienteering Problem

text:
# Question
Title: Flexible Team Orienteering Problem
In Team Orienteering Problem `(TOP)` we have a graph $G=(V,E)$ and $K$ participants, We are supposed to find $K$ paths with total edge cost less than a threshold while maximising total vertex rewards. The constraint on reward collecting is once a reward has been collected by some participant the it can not be collected again by another participant. e.g. each vertex have only one piece of reward.

But given a graph like this, and two participants, where $s,t$ are the start and terminating points. I want to have two pieces of reward in $d$ but only one piece of reward in $b$ and $c$.

Does this problem has a name ? Is that proven to be NP-Complete ?

# Answer
> 1 votes
I don't know if it has a name but it's **NP**-hard. Just take $K=1$, give every edge and vertex weight $1$ and ask if there's a solution with vertex reward $|V|$ and edge cost at most $|V|-1$. This happens if, and only if, there's an $s$–$t$ Hamiltonian path. The decision version "Can I get reward at least $R$ with cost at most $C$" is **NP**-complete.

---
Tags: np-complete, traveling-salesman
---


title: What does 'relocation' mean?

text:
# Question
Title: What does 'relocation' mean?
I am reading about `Base & Bounds` memory protection mechanism, and I noticed the use of the term *'relocation'* in the context of `address space`, but failed to understand the meaning associated with it.

Below are some examples:

1. U.C Berkeley L02/CS162:

> relocating loader
2. Wisconsin S15/CS537

> Each process appears to have a completely private memory of size equal to the bounds register plus 1. Processes are protected from each other. No address relocation is necessary when a process is loaded.

Furthermore, I searched for the term and found only the definition on Wikipedia that wasn't very clear to me.

Does anyone have any idea?

# Answer
*Relocation* means moving stuff from one place to another. In your case, there is a program which contains some absolute addresses, which make sense if the program is located at a certain address A. If the program is loaded to a different address B, we need to update all of these addresses, translating them by B−A. This is *address relocation*. A loader (a program loading another program to memory) which does this is called a *relocating loader*.
> 3 votes

---
Tags: operating-systems, memory-management, virtual-memory
---


# Question
Title: Algorithm to select sets of objects while maximizing number of objects covered
If we have different objects,

```
[A1, A2, A3, B1, B2, B3, B4, B5]

```

Some calculations will be performed to find compatible objects. For example, lets assume following 3 sets were formed and every set contains compatible objects:

```
 1. {A1, B2}
 2. {A3, B2}
 3. {A1, A3, B4, B5}

```

Now we need to perform filtering. One node can participate only once. For example, if `B2` has made a pair with `A1`, then `B2` can not participate in any other set. Which means, if we select set 1, then set 2 will be deleted because `B2` has already participated. And set 3 will be deleted because `A1` has already participated.

Now we need to do filtering such that we maximize number of objects being utilized. If we select `set 1`, then we are only utilizing `A1 and B2`. **Thus, optimal way would be to select set 3 which is utilizing 4 objects. And discard sets 1 and sets 2**

Right now, i have a complex function which goes through list of sets recursively and keeps on adjusting until no changes are made to existing sets. This is not only inefficient, but it might not work in cases where changing sets can cause ripple effect.

I am not looking for coded solution, but just a guidance that is there any graph algorithm which I should study?

# Answer
> 3 votes
The problem you're describing can be seen as the weighted independent set problem, as follows: Construct a graph $G=(V,E)$, where every node $v$ in $V$ corresponds to your sets of objects. The nodes $v,w$ have an edge in $E$ if and only if they share an object. The weight of each node is the number of objects contained within the corresponding set.

Now, observe that maximizing the amount of objects used corresponds to finding a set of nodes in $G$ such that 1. none of the nodes are adjacent and 2. the sum of weights over these nodes is maximized. This is precisely the weighted independent set problem.

Unfortunately, this problem is NP-hard, which means an exact efficient algorithm is unlikely to exist (and even less likely to be found). This means that, unless you only have to deal with small values, you would either have to resort to heuristic or approximation algorithms, of which there are a few in the literature. It may be possible that only a particular kind of graphs arise (e.g. trees). In that case, there may be an efficient algorithm, but that depends on your input.

---
Tags: algorithms, graphs, optimization, graph-traversal, java
---


# Question
Title: Understanding PDA and Equivalence of PDA and CFG
When we wanted to construct a PDA for $0^n1^n$ the idea was to put all the zeroes (which is a part of the input string) to the stack associated with the PDA, and then pop each of them when we get a $1$ from the latter part of the input.

But when we try to prove that, we can create a PDA for a given CFG we put nonterminals and terminals in the stack and try to match it with input and pop from the stack.

Why do we do something like this? For a problem, we push some part of my input to the stack and match rest of them, and for some problems do not push any input symbol rather only use inputs to compare?

Maybe I am missing some intuitive part of it.

# Answer
> 2 votes
Your question is, in essence,

> Why does the proof that every context-free grammar can be converted to an equivalent PDA proceed in a particular way rather than in another way?

It's hard to answer such a question unless it gets more specific. For example, you can ask why the resulting PDA have to invoke nondeterminism. The answer is that some context-free languages cannot be accepted by a DPDA. Indeed, while this particular proof uses PDAs acting in a certain way, another proof might use PDAs acting in a different way.

One alternative such proof uses the Chomsky–Schützenberger representation theorem. The theorem states that every context-free language can be realized as $$ h(D \cap R), $$ where $D$ is a Dyck language (the language of all correctly nested strings of parentheses of some fixed number of sorts), $R$ is a regular language, and $h$ is a homomorphism. This theorem, which can be proved directly using context-free grammars (see, for example, Context-free languages and pushdown automata by Autebert, Berstel and Boasson, from the Handbook of Formal Languages), allows to convert a context-free grammar to a PDA which is more like the one for $0^n 1^n$, along the following lines:

1. Start with a PDA for $D$. This is a PDA that pushes whenever encountering a left parenthesis, and pops whenever encountering a right parenthesis (checking that the two parentheses, the one on the stack and the one being read, have the same type).
2. Construct a DFA/NFA for $R$, and use the product construction to construct a PDA for $D \cap R$.
3. Construct a PDA for $h(D \cap R)$ by replacing each transition on $\sigma$ to a transition on $h(\sigma)$.

If you apply this construction to $0^n1^n$ (which you can realize as $D \cap 0^\*1^\*$, where $D$ is the Dyck language with a single type of left parenthesis $0$ and the corresponding right parenthesis $1$) then you get a PDA which is remarkably similar to the one you describe.

# Answer
> -1 votes
That,

**we can create a PDA for a given CFG**

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


# Question
Title: How to reduce Untyped λ-Calculus to Normal Form?
I have an assignment to do which involves reducing an Untyped λ-Calculus expression to Normal Form. I am struggling to come to terms with Lambda Calculus though.

For example, one small part of the expression is:

```
((λ n f x . n f (f x)) (λ f x . x))

```

Does this mean that we substitute `(λ f x . x)` in for every n, f and x? Giving us the following:

```
((λ n f x . (λ f x . x) (λ f x . x) ((λ f x . x) (λ f x . x))))

```

If so, can this be reduced further? I know I am probably way off with this, but I just do not understand it; any help would be appreciated.

# Answer
> 3 votes
> **EDIT: Thanks to @ljedrz Comment.**
>
> Before doing the reduction is worth noting that: $$ (\lambda n f x . n ~ f (f ~ x)) = (\lambda n f x .((n f) (f ~ x))) $$ This is a convention, the parenthesis always associate to the left

It can be reduced further, but I advise you to change the second expression to an $\alpha$-equivalent one.

$$ \Big(\big(\lambda n f x . (n ~ f) (f ~ x) \big) ~ (\lambda h y . y) \Big) $$

This might not be necessary in this specific problem, but might also save you some headache later trying to keep track if some free variables got captured.

\begin{align\*} \Big(\big(\lambda \color{red}{n} f x . \color{red}{n} ~ f (f ~ x)\big) ~ \color{red}{(\lambda h y . y)} \Big) &\rightarrow\_\beta \big\[n ~ / ~(\lambda h y . y)\big\] \big(\lambda f x . n ~ f (f ~ x)\big)\\ &\rightarrow\_{\alpha} \big( \lambda f x. (\lambda h y. y) ~ f ~ (f~x) \big)\\ \Big( \lambda f x. \big((\lambda \color{red}{h} y. y) ~ \color{red}{f}\big) ~ (f~x) \Big) &\rightarrow\_{\beta} \Big(\lambda f x.\big\[h ~ / ~ f \big\]\big(\lambda y.y\big) ~ (f ~ x) \Big)\\ \Big( \lambda f x. ((\lambda y. y)) ~ (f~x) \Big) &\rightarrow\_{\beta} \Big(\lambda f x.\big\[y ~ / ~ (f ~ x)\big\]y\Big)\\ &\rightarrow\_{\alpha} \Big(\lambda f x. (f ~ x) \Big) \end{align\*}

Which cannot be reduced further.

# Answer
> 2 votes
You might find it easier (I do) to practice β-reductions using De Bruijn indices, as they make α-conversions unnecessary and the indices help keep track of the substitution order.

Using them, the reduction (normal order) of your expression would look as follows ($\color{blue}{abstraction\ to\ drop}$, $\color{red}{bound\ variable\ to\ substitute}$, $\color{green}{the\ substitute\ expression}$):

\begin{align} (\color{blue}{λ}λλ\color{red}{3}2(21))\color{green}{(λλ1)}\\ λλ(\color{blue}{λ}λ1)\color{red}{2}(21)\\ λλ(\color{blue}{λ}\color{red}{1})\color{green}{(21)}\\ λλ21 \end{align}

---
Tags: lambda-calculus
---


# Question
Title: interference graph: assigning variable to itself
I'm studying the theory behind compiler design, and was assigned with building an Interference graph for a certain code 3-address code.
We were taught to first divide the code into blocks (according to GOTOs), and draw lines that represent a variables lifeline.
I am not sure on *a = a op c* (that is, same variable is both read and assigned in same command). I am following this examples, which sadly, has a typo that makes it hard to understand this very end-case. Here, *a=a+b+c*, so **a** is both used and assigned.
I have initially treated that with no special care (logic being "i know some interpreters can read RHS before LHS"), but now I am not quite sure.
My question really:
I think perhaps the example should have mark a's line starting from the *read()* command, end it in the *a=a+b+c* but also re-draw the line. This way an extra register will temporarily hold a's value before assigning it back to a. Is that correct?

# Answer
> 4 votes
You are right. The lifetime of `a` could be split into two spans. That said, how would you notate that in the interference graph? That is, how would you notate that one variable only interfered with one span of another variable's lifetime?

This is one of the motivations for Static Single Assignment (SSA) form. By having each assignment write to a "new" variable, you're never in the situation where a variable's lifetime is in potentially disjoint spans. You also have a name for each span of a (source-level) variable's lifetime, so the interference graph can be finer grained.

It is, however, *safe* to treat the lifetimes as starting at the first assignments and ending at the last uses. So while it may not be *optimal* to give each variable one single span of lifetime, it will never cause incorrect behavior.

---
Tags: compilers
---