# Question
Title: How can I compare two algorithms using their Big-Oh complexities?
I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of time complexity. I tried plotting graphs but two functions seem to be going together.

# Answer
> 1 votes
You will need to compare the rate of change for both functions. This can be accomplished by taking the derivative of both functions:

$$ O\_1'(n^2 log(n)) = \frac{d}{dn} n^2 log(n) = n + 2n × log(n) $$ $$ O\_2'(n^{2.32}) = \frac{d}{dn} n^{2.32} = 2.32n^{1.32} $$

Plot these derivatives and compare the graphs. If they still seem too close, continue to take higher order derivatives such as $\frac{d^2O}{dn^2}$, $\frac{d^3O}{dn^3}$, etc. Eventually, you will notice a clear difference in the rate of change.

For those who don't have access to plotting software, you can evaluate the slope of the tangent line for an arbitrarily large n-value:

$$ O\_1'(10^6)=\frac{d}{dn} n^2log(n)\bigg|\_{n=10^6} = 10^6 + 2(10^6) × log(10^6) ≈ 2.8631 × 10^7$$

$$ O\_2'(10^6)=\frac{d}{dn} n^{2.32}\bigg|\_{n=10^6} = 2.32(10^6)^{1.32} ≈ 1.9296 × 10^8$$

This means, for $n=10^6$, $O\_1$'s tangent line @ $(10^6, y\_1)$ would result for some equation:

$$y - y\_1 = (2.8631 × 10^7)(x - 10^6) $$

and $O\_2$'s tangent line would result in:

$$y - y\_1 = (1.9296 × 10^8)(x - 10^6) $$

Now, the answer is clear: $O(n^{2.32})$ has a much more steeper rate of growth than $O(n^2log(n))$ for large values of $n \> 10^6$. Conclusion: $O(n^2log(n))$ is more efficient than its counterpart.

# Answer
> 1 votes
I see, that answer is done and accepted, but let me share some thoughts:

Short answer: knowing only upper bounds it's impossible to compare algorithms. We can compare upper bounds, but this doesn't give answer to algorithms relation.

Long answer: assume we have $f\in O(n^2\log n)$ and $g \in O(n^{2.32})$. Because $\exists N \in \mathbb{N}$ such that for $n \> N$ holds $n^2\log n\<n^{2.32}$, then $ O(n^2\log n)\subset O(n^{2.32})$, so knowing only $g \in O(n^{2.32})$ does not gives warranty, that it is not in $ O(n^2\log n)$ also.

Let me bring analogy: if $x\<5$ and $y\<10$, then we cannot say how $x$ and $y$ are related to each other, without additional info. For example both variants $x=1,y=2$ and $x=2,y=1$ satisfies given conditions.

# Answer
> 1 votes
$O(n^{2.32})$ is kind of unusual. Do you have a mathematical proof for this, or is it an estimated based on observations? In that case, you can't draw any conclusions from it.

Big-Oh is an upper bound. So first you need to check what is the actual behaviour. If an algorithm runs in $O(n)$ then it is correct (but not very useful) to say it runs in $O(n^{2.32})$, so check that first.

If both are strict upper bounds (so the algorithms are not $o(n^2 \log n)$ and not $o(n^{2.32})$) with a little o, then the second algorithm will be slower at least for some cases if n is large. If it was $\theta$ then it would be the case for all large n.

In practice, if you want to decide which algorithm to use after you implemented them both, you would measure their execution time for their typical inputs, and find the average time and the worst time. As long as the worst time is acceptable, you'd take whichever one takes less time on average for *your* inputs. For example, if you need to sort a million arrays of size 10 containing almost sorted, the Big-O of the sorting algorithm is irrelevant; what counts is the average sorting time for arrays of size 10 that are almost sorted.

Quite often the execution time for small n is "fast enough". In that case you will care for cases where one or both of the algorithms are *not* "fast enough". So if the usual case is "fast enough", you worry more about the unusual, very large cases.

Another problem happens when the average time is low and the worst case should be very rare, but is very slow. In that case an adversary might give you inputs that run very slow. For example, Quicksort is typically fast, but for every deterministic implementation, an adversary can prepare inputs of size n that take O(n^2) time. They will never happen in practice, only when created by an adversary.

# Answer
> 1 votes
$O(n^2\log n)$ is better, since $\lim\_{n \to \infty} {n^2\log n \over n^{2.32}} = 0$.

# Answer
> 0 votes
If this is a recursive algorithm, and you want it fast: Calculate the exact runtime for both algorithms for small n. Then algorithm A doesn't recursively call A for smaller n, but the faster of algorithm A and algorithm B. And you will have a base case for small n that is calculated without recursion. Consider that one as well. This may give you overall the fastest algorithm, especially if one algorithm is inferior until n gets quite large.

For recursive algorithms, the execution time often doesn't grow smoothly with n, so you might end up with a table telling you for which n the base case is fastest, for which case A is fastest, and for which case B is fastest.

---
Tags: time-complexity, runtime-analysis, big-o-notation
---


# Question
Title: Why compute finish time in topological sort
In depth first search each vertex can be associated with a discovery time and a finish time. I am reading the following implementation of topological sort in terms of depth first search

```
TOPOLOGICAL-SORT(G)
1 call DFS(G) to compute finish times for each vertex
2 as each vertex is finished, insert it to the front of a linked list
3 return the linked list of vertices

```

I don't see why it's necessary to compute the finish time for each vertex. Also the finish time is not used anywhere in the algorithm after it's being computed, so why do we need it?

# Answer
> 1 votes
I guess the algorithm you presented is from CLRS. You are right that the finishing time is not necessary for the algorithm to work. Once the vertex is completely explored (all its neighbors are visited) then you can just marked the vertex as explored and then add it to the linked list. In a way, the finish time will be implied by the order of the vertices in the list.

However, if you will read the proof used in CLRS to show that the algorithm works correctly, that is the time they make use of the finish time. So I guess they add that to the algorithm for the sake of making the proof easier to state.

# Answer
> 1 votes
Denote $\text{post}(v)$ (for *postvisit number*) its finish time. Then for any directed graph $G = (V, E)$, the two following properties are equivalent:

1. $G$ contains a cycle;
2. there exists an edge $(u, v)\in E$ such that $\text{post}(u)\<\text{post}(v)$.

So the postvisit ordering can be used to decide the existence of a cycle, or to find a topological ordering when there is no cycle: the reverse of a postvisit ordering is a topological ordering given the previous equivalence.

See *Algorithms* from Dasgupta, Papadimitriou and Vazirani for more details.

---
Tags: algorithms, graph-traversal, depth-first-search, topological-ordering
---


# Question
Title: PushDown automata for a^(n) b^(2n) c^(2n) d^(n)
i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)"

i am arguing that there is no pda for that question but our ta says that we can push 5x to the stack then pop x each time we read a b or c or d. i am arguing that doesn't guarantee count because we might get only "d"s which one of us is right

# Answer
You are right that the suggestion of the TA does not work. Using that approach one will accept $\\{\\; a^n b^i c^k d^\ell \mid 5n = i+j+\ell \\;\\}$. We can force the PDA to make $i$ and $j$ even, but that will not help much.

Of course this does not prove that there is no PDA for the language $K = \\{\\;a^nb^{2n}c^{2n}d^n \mid n\ge 1\\;\\}$ : another clever technique might work.

Recall that $L = \\{\\;a^nb^nc^n\mid n\ge 1\\;\\}$ is a very similar language, known not te be context-free. Hence it is intuitively clear that also your language is not context-free.

To formally show that one might use the direct approach and use the pumping lemma for CF languages to show it is not context-free. Alternatively one may use closure properties of the context-free languages to show that if $K$ is context-free then so is $L$ (leading to a contradiction). Informally the language operations you need would be halving the number of $b$'s and $c$'s and deleting the $d$'s. Formally those can be "implemented" by homomorphisms and their inverses. Those operations map letters to words.
> 0 votes

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


# Question
Title: Simple description of the LR(0) table generator algorithm?
I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think "recusive descent". But no. I am not talking about recursive descent top-down, I am talking about bottom up, LR, simple, no look-ahead, driven by a state-transition table.

I built the tokenizer, manually cobbled together the state event transition and action table, and I have an action function which updates the stack for each thread of parallel parsing.

All is working nicely. The only problem is for me to create the state transition table. My grammar isn't so hard. I don't even have a lot of complex repeated groups.

```
name        :             famname foobar
name        :             famname suffixes foobar
name        : PREFIX_WORD famname suffixes foobar
famname     : WORD_R
famname     : WORD
suffixes    : WORD
suffixes    : suffixes WORD
foobar      : bar FOO
foobar      : FOO bar
bar         : NUMBER UNIT denominator
bar         : NUMBER UNIT
denominator :         SL_UNIT
denominator : SL_NUMBER  UNIT
denominator : PER NUMBER UNIT

```

I am not showing the semantic actions above, but I know how that's done.

For this simple structure I could still do it manually, but if I expand this grammar to about 2 - 10 times as many symbols it would become a nightmare to get right and I would waste a lot of time debugging my manually created state transition table.

I don't even care much about shift/reduce and reduce/reduce conflicts. So I don't even care about look-ahead to disambiguate. All I want is take a BNF structure as the above and transform it into a table of (old\_state, token\_type, new\_state, action).

I am having a hard time to find a description that is intuitive for me. It's not that I couldn't drill through the literature with some extra effort, but I have very little time. I know there is something with item set and closure, but most descriptions I find are for more complicated considerations.

One idea I had was to just expand the structure by resolving all higher symbols to atomic token type sequences. And do it breadth first with detection of cycles. Then I have all the paths through the state transition graph and I could already produce a huge table from that, or I could try to squeeze out common sub-paths from the different paths. I know in a grammar for something like a programming language, trying to expand all possible token type sequences would be crazy. But in my case I could probably do it.

Perhaps there is only a couple of ah ha! moments from my naive idea to something serious?

# Answer
> 0 votes
I think the commenters are gracious for not having down-voted my question. It seemed I was lazy. But I was lazy no more. The last two days I have put my head into this matter and I just finished the implementation and verified it against the textbook example.

Of all the texts and presentations I could find I found these lecture notes the best:

What had confused me in the past was all that theoretical talk about "item" and "item set". Also this dot notation seemed weird.

But what helped me was actually doing it all (in SQL) where it is clear that one production on the RHS has a sequence, and so we have a production id and a sequence number to get to exactly one RHS symbol (non-terminal or terminal). So what an "item" really is is one RHS symbol of one production, at least if we terminate the RHS symbols with one (implicit) termination, i.e., even though the rule: `E : E "+" T` has only 3 RHS symbols, a position 4 is valid and indicates the end of the production.

Then thanks to these lecture notes above for going directly from "item" to "state" and even including the transitions immediately in the picture (and for having a picture in the first place).

**So, the approach in a nutshell is this:**

**To Prepare**

1. Add a single trivial start symbol to the grammar if needed, so that if the real start symbol has multiple productions, there will be only one production for the top-level start symbol.
2. Think of the productions as a relation: PROD(P#, LHS, SEQ#, RHS), these tuples are all "items" (for lack of a better word), example
3. For ease of use complete the Production by adding a terminal item to each, this is so that if you ask for the next step by increasing to the next RHS symbol, you can find the final one which just has nil RHS symbol.
4. Now magically the State Transition network emerges simply from the following actions.

Why that initial trivial start symbol is required can be seen with the standard example:

```
E : T
E : E "+" T
T : F
T : T "*" F
F : n
F : "(" E ")"

```

If you don't add `E' = E` then there is not one top level symbol. You could start at E but you can also start at T or at F. You just don't know where to start!

**To Begin**

1. Create your first state (S0) with that trivial single start symbol production's first RHS (also trivially the original start symbol)
2. Now for that one RHS symbol of the start symbol, add more member items into the state by taking the first RHS symbol (item) of all productions with LHS being that initial RHS symbol of S0
3. Now do the same for all items you have added, and recursively until nothing new is added (this is the transitive closure of LHS -\> RHS tuples).

I found it helpful to think of these items as individual PROD(P#,LHS,SEQ#,RHS) tuples. It's not that you need to write out the full `LHS : RHS1 RHS2 RHS3 ...` line and put a dot somewhere.

**To Iterate**

1. For each item in your completed state, make a list of unique RHS symbols
2. For each such unique RHS symbols, find all member items in your state that have that unique RHS symbol. (Remember an item is just one position on the RHS of a production, it's not a line of text with a dot somewhere. So there is only one RHS symbol (or nil) in any item, therefore there is no question about the RHS symbols have a dot before them or not.)
3. Now each of these (groups of) member items from your current state for the same unique RHS form a new state.
4. Each new state is defined by the next step in the production PROD(P#,LHS, ++SEQ#, RHS').
5. Regardless if RHS' is something or nil, each group of such production steps coming from one unique RHS identify one state.
6. You might have already seen that state before, check if you find one with the same definition items, if so, use that existing state, if not, make a new state.
7. For all new states, generate the closure by again going to the start RHS symbol of each production for the item that defines the state, and from there recursively for each item you just included (closure)
8. Continue for all such unique RHS symbols, for all previously generated states.
9. Note: the transitions come right out of this procedure, whether the state already existed, or you just created a new one, the transition from the current member item of your current state becomes a next state.
10. There is at most one transition from each member item of a state
11. Multiple member items of a state may have the same new state
12. The RHS of each member items of the state are the event which triggers the transition (at least the terminal symbols are.)

**To Conclude:**

So at the end of this process of unique RHS, state member for that RHS, next SEQ# of the RHS sequence of the production, merging states that already exist, and then complete the closure again, and recording the new state for each state member item, magically the entire finite state automaton has been defined.

Is this explanation shorter and more concise or intelligible as all he outstanding CS lectures and text books and lecture notes? Probably not. But it is concise enough to promise that the state transition network comes out of this one procedure right from the productions of the grammar.

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


# Question
Title: NSPACE(n^2) and DSPACE(n^2) class problems
What problems belong in NSPACE(n^2) and DSPACE(n^2) class? Examples?

# Answer
The empty problem $\emptyset$ (the problem whose answer is always *false*) is in both $\mathsf{NSPACE}(n^2)$ and $\mathsf{DSPACE}(n^2)$.

(If you are unsatisfied with this answer, then you should be more precise in your question).
> 0 votes

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


title: Check whether a decomposition is in 3nf

text:
# Question
Title: Check whether a decomposition is in 3nf
In a database systems course, we have been presented with the following definition for third normal form (3NF):

> A relation $R$ is in 3NF means:
> a nontrivial dependency $A\_1,\dots,A\_n\to B\_1,\dots B\_m$ can hold in $R$ only if $\\{A\_1,\dots,A\_n\\}$ is a key (either minimal or super) in $R$ or
> for $1 \leq i \leq m$, each $B\_i$ is a part of a minimal key.

Given the relation $R(A,B,C,D)$ with FDs:$A\to C$ and $C,D\to B$, is the following decomposition of $R$ in 3NF?:
$R\_1(A,C)$ $R\_2(A,B,D)$.

I think it is not in $3NF$:

* In $R\_1$, $\\{A\\}$ is a key and $A\to C$ is a nontrivial dependency. It meets the first condition, so $R\_1$ is in $3NF$.
* In $R\_2$, $C,D\to B$ is a nontrivial dependency and $\\{A\\}$ is a key. The first condition is not met because $\\{C,D\\}$ is not a key and $\\{B\\}$ is not a part of a key.

Am I correct?

# Answer
> 0 votes
The dependency `C, D -> B` does not hold in `R2` since the three attributes are not present in it and that dependency cannot be derived by taking the closure of the union of the the projection of the dependencies over `R1` and `R2`.

So the decomposition is in 3NF (actually it is in BCNF), but the dependency `C, D -> B` is lost. A decomposition that preserves data and dependencies is for instance:

```
R1(A, C)
R2(B, C, D)
R3(A, D)

```

---
Tags: database-theory, databases
---


# Question
Title: Assign items from inventory to people maxmizing the number of satisfied people
We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We want to maximize the number of people who receive all the items on their list. The inventory may not have enough items to satisfy all the wishes.

To give an example:
Alice - wants: 1 apple
Bob - wants: 3 bananas, 1 cherry
Charlie - wants: 2 apples, 1 banana

Inventory: 1 apple, 3 bananas, 2 cherries

One optimal solution is:
Alice - gets: 1 apple
Bob - gets: 3 bananas, 1 cherry
Charlie - gets: 1 cherry

Alice and Bob are satisfied, and it doesn't matter what Charlie gets.

Here is what I tried so far:
I tried searching for a similar problem, but the only thing I could find are variations of the assignment problem, or the matching problem, all of which do not quite match the one at hand. I don't think the assignment problem applies, because it has a cost function for each assignment, which is independent of the other assignments, but here we have global cost function. We could model the situation similar to a matching problem where we would have a bipartiate graph of vertices one side being the people and the other being the items with edges representing the wishes (we could have multiple edges for a pair of person and item to represent the amount) and have a "capacity" on each item to represent the inventory. Then we could find some sort of matching which satisfies the constraints. But I am not sure which algorithm could be used for that.

# Answer
In the special case where the inventory doesn't have multiple copies of any object, this is the set packing problem. It is NP-hard, so you shouldn't expect any efficient solution. Since your problem is a generalization of a NP-hard problem, it too is NP-hard, so not solvable efficiently.

If you have to solve it in practice, you might consider formulating it as an instance of integer linear programming or SAT and then using an off-the-shelf ILP solver or SAT solver. See, e.g., https://en.wikipedia.org/wiki/Set\_packing#Integer\_linear\_program\_formulation.
> 1 votes

---
Tags: algorithms, graphs, matching, bipartite-matching, assignment-problem
---


# Question
Title: How sparsity term in loss function for sparse autoencoder is making hidden units inactive?
I am working on a **Sparse Autoencoder** but Andrew NG's notes are hard to understand. My question is about the following equation: **Loss Function**.

In sparse autoencoder, **the goal is to inactive some nodes to obtain low-level features** or more precise features. Now if you check Andrew NG's Notes on sparse autoencoder (available on Google Scholar easily and the loss function image is also attached) there is a sparsity term added to the loss function. **My question is How the sparsity term inactives the hidden units because whatever the value of KL divergence (it is basically a sparsity term) is, it still adds up in the actual loss and makes the loss value bigger this way we are not reducing the loss but we are increasing it.**

I am expecting an answer which is a bit clear and easy to understand.

# Answer
I suggest that you think about this differently. An autoencoder maps the input to a "representation". The representation is a vector that contains the output of the hidden units. (It is also sometimes called an "embedding".) A vector is said to be "sparse" if most of its entries are zero. The goal of a sparse autoencoder is to map the input to a representation that is a sparse vector.

This loss function encourages the network to compute a sparse representation, because of the penalty term in the loss function. If the representation is sparse, the penalty will be small. If the representation is not sparse, the penalty will be large. When we train a neural network, training tries to find weights that will make the loss function small. Thus, training will try to find weights that make the penalty small. In other words, training will try to find weights that makes the representation sparse. The more sparse the representation is, the lower the loss will be, and so stochastic gradient descent will try to drive the neural network weights towards values that make the loss lower, i.e., make the representation sparse.

See also https://en.wikipedia.org/wiki/Penalty\_method for the use of penalty terms in loss functions.
> 0 votes

---
Tags: machine-learning, neural-networks, weighted-graphs, python, sparse-matrices
---


# Question
Title: Longest increasing subsequence when a number can be added to all numbers in a subarray
A sequence $(a\_1,a\_2, \dots, a\_n) $ and natural numbers $n$ and $k$ are given.

We want to calculate the longest (strictly) increasing subsequence of sequence $(b\_1,b\_2, \dots, b\_n)$ for which there exist an interval of pointers $\[l, r\]$ and an integer $x$, $-k\le x\le k$, such that $b\_i = a\_i + x$ for $i \in \[l, r\]$, and $b\_i = a\_i$ for $i \notin \[l, r\]$.

Input: The natural numbers $n$, $k$ and the sequence $a$.

Output: The longest increasing subsequence that can be created through a sequence $b$.

I want to find a polynomial-time algorithm that solves this problem

I know how to find longest increasing subsequence in general.

I think we'll have to use Dynamic Programming.

# Answer
Here's a simple solution that runs in `O(n)` time. To explain the solution, we must make a few observations.

First, note that having a negative value of `x` has the same effect as a positive value (ex. having `x = -3` will produce a sequence `b` with the same longest increasing subsequence as `x = 3`) so we should only test positive values of `x`.

Given this, also note that it will never be sub-optimal to have the interval `[l, r]` be at the end of an increasing subsequence, as any optimal solution without `[l, r]` at the end can be turned into another optimal solution by simply extending `[l, r]` to go all the way to the end of the subsequence. It can be proved that extending `[l, r]` to the right will never make an increasing subsequence worse.

Thus, a naive solution would be to simply go through all possible optimal values of `l` for each possible value of `x`. This would give us an `O(nk)` algorithm. However, we can realize that all optimal solutions with `[l, r]` starting at a fixed `l`, another optimal solution can be made by simply increasing the value of x; the only purpose of the interval `[l, r]` is to 'fix' the step between `a[l-1]` and `a[l]` in order to maintain an increasing subsequence. Therefore, it is always optimal to set `x` to the highest value possible -- in this case, `k`. This removes the need to loop through all values of `x` an allows for a solution in `O(n)` time.

Pseudocode:

```
Keep an integer "sl" to store the index of l that gives the current LIS
Keep an integer "sr" to store the length of the current LIS, initialized to 0
Keep an integer "tl" to store the current index of l
Keep an integer "tr" to store the current length if l were to be at tl, initialized to 0
Keep a boolean "used" to remember whether we've used the a[i]+x rule yet
For each value of i from 0 to n-2:
    If (not used) and (a[i+1] <= a[i]) and (a[i+1]+x > a[i]):
        tl = i+1
        tr++
        used = true
    Else if (used) and (a[i+1] > a[i]):
        tr++
    Else:
        If (tr > sr):
            sr = tr
            sl = tl
        used = false
        tr = 1
If (tr > sr):
    sl = tl

Keep an array "b" of size n, initialized to be the same as the given array a
For each value of i from sl to n-1:
    b[i] += k
return b

```

This algorithm is `O(n)` because it runs one loop through all the items `a`, which is `n` items.

Cheers.
> 0 votes

# Answer
All indices below are understood to take valid values.

As expected, we will use dynamic programming.

Consider an increasing subsequence of $$a\_1,\cdots a\_{l-1}, a\_l+x, a\_{l+1}+x, \cdots, a\_r+x, a\_{r+1}, \cdots, a\_n$$ that ends at element $a\_e$ or $a\_e+x$.

Classify that subsequence

* by $(e, 0,\`\`\text{before"})$ if $e\<l$
* by $(e, x,\`\`\text{added"})$ if $l\le e\le r$
* by $(e, x,\`\`\text{after"})$ if $e\>r$ and that sequence contains at least one element of the form $a\_i+x$.

Let $dp\[e\]\[x\]\[stage\]$ be the length of the longest sequence that is classified by $(e, x, stage)$, where $1\le e\le n$, $-k\le x\le k$, $stage$ is one of $\`\`\text{before"}$, $\`\`\text{added"}$ and $\`\`\text{after"}$.

What we are asked to compute is the maximum of all $dp\[e\]\[x\]\[stage\]$.

We have the following recurrence relations: (function $\max$ takes value $0$ if its arguments turn out to be empty)

$$dp\[e\]\[0\]\[\`\`\text{before"}\]=1 + \max\_{d\<e\text{ and }a\_d\<a\_e}dp\[d\]\[0\]\[\`\`\text{before"}\]$$

$$dp\[e\]\[x\]\[\`\`\text{added"}\]=1 + \max(\max\_{d\<e\text{ and }a\_d\<a\_e+x}dp\[d\]\[0\]\[\`\`\text{before"}\],\ \max\_{d\<e\text{ and }a\_d\<a\_e}dp\[d\]\[x\]\[\`\`\text{added"}\])$$

$$dp\[e\]\[x\]\[\`\`\text{after"}\]=1 + \max(\max\_{d\<e\text{ and }a\_d+x\<a\_e}dp\[d\]\[x\]\[\`\`\text{added"}\],\ \max\_{d\<e\text{ and }a\_d\<a\_e}dp\[d\]\[x\]\[\`\`\text{after"}\])$$

The first recurrence relation is, in fact, (one of) the usual recurrence relation that is used to compute the longest increasing subsequence of a sequence.

The base cases are $dp\[1\]\[0\]\[\`\`\text{before"}\]=dp\[1\]\[x\]\[\`\`\text{added"}\]=dp\[1\]\[x\]\[\`\`\text{after"}\]=1$ for all $x$.

(By the way, $dp\[e\]\[0\]\[\`\`\text{before"}\]=dp\[e\]\[0\]\[\`\`\text{added"}\]$ for all $e$. So we can remove stage $\`\`\text{before"}$.)

The time-complexity is $O(kn^2)$ since, basically, there are $O(nk)$ entries to compute and it takes $O(n)$ to compute each entry.

---

If we adapt the $O(n\log n)$-time algorithm for the usual longest subsequence problem, we will have a $O(kn\log n)$ algorithm.
> 0 votes

---
Tags: algorithms, dynamic-programming, arrays, polynomial-time, longest-increasing-subsequence
---


# Question
Title: How many words of memory map to the same cache entry?
I am going over some practice questions for the Major field exam and it asks:

A processor with a word-addressable memory has a two-way set-associative cache. A cache line is one word, so a cache entry contains a set of two words. If there are  *M*  words of memory and *C* cache entries, how many words of memory map to the same cache entry?

I am not sure how to even approach this problem since I am not too familiar with computer organization. Any help would be appreciated. Thanks!

# Answer
> 0 votes
The total cache size is C entries of two words each = 2C words.

The total memory is M words.

Assuming that the same number of words are mapped to each cache entry (and this is a very very safe assumption), there are M / (2C) words mapped to each entry.

There is another answer claiming this is the same question as in some test, with a different answer. Since the answer is wrong, I assume that the questions were not quite the same, but the link in that answer doesn't work.

PS. Words of memory mapped to each cache line is usually quite irrelevant. It's a measurement that changes if you double, quadruple or halve the memory size which is all irrelevant to the cache performance.

# Answer
> -1 votes
Cache has `C/2` fixed locations

which further implies, we have

`M / (C/2)` = `2M/C`

words of memory which map to same location

# Answer
> -1 votes
The correct answer is M/C. This question is on the Computer science Major Field Assessment Test. https://www.ets.org/Media/Tests/MFT/pdf/mft\_samp\_questions\_compsci.pdf

---
Tags: computer-architecture, cpu-cache
---


title: Lopsided merge algorithms

text:
# Question
Title: Lopsided merge algorithms
Is there a faster algorithm to merge two sorted linked lists where one is guaranteed to be much larger than the other?

By merging two sorted lists I mean taking two sorted lists $A$ and $B$ and producing a new list that contains all the elements of $A$ and $B$ and is sorted itself.

The typical solution, which Wikipedia lists and I have written in Haskell below, is $O(n+m)$

```
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] =[]
merge a@(_:_) [] = a
merge [] b@(_:_) = b
merge (a : ax) (b : bx)
 | a <  b = a : merge ax (b : bx)
 | a >= b = b : merge (a : ax) bx

```

However simply inserting each element of the shorter list into the longer one using binary search is $O(n\log m)$1, which when $n \ll m$ is considerably better than $O(n + m)$. This doesn't even use the fact that the smaller list is already sorted which may be leveragable for better speeds.

Are there a faster algorithms to merge two sorted lists where one is much larger than the other?

---

It has now been pointed out that I was incorrect about this, it cannot be done that fast because we to walk through the list for binary search.

# Answer
If by "faster" you mean in terms of *number of comparisons* (so walking the list just to find an index doesn't matter) or if you weren't using linked lists, then yes there are faster algorithms. Specifically in cases where as you said, one list is guaranteed to be "much" longer than the other.

This paper gives an algorithm for lists where $n/m \> 8$. I don't understand it well enough to summarize, sorry.

Timsort takes inspiration from ideas like that and applies them to real world data when merging runs in "galloping mode". He explains the logic in a bit more detail in the original explanation (under "Merge Algorithms").
> 1 votes

# Answer
Assume two sorted lists A and B with n and m elements, where n is much smaller than m.

First, it will be faster if you can modify B, because most of the links between list elements are correct and don't need changing. If you create a new list, you have to set up n+m connections correctly. But anyway, do your list items support being in multiple lists? (Not if each item just has a "next" field)? If not, then you modify B.

Second, is there a way to access arbitrary items in constant time? Being a list, there should be no way to do this. So binary search doesn't help much - you still need to follow m links so the time is linear.

Assuming n is much smaller, and comparisons are slower than going through a linked list: Normally you would iterate through the list B until you find an item less than an item of A, then you insert that item, and so on. Initially you would skip say m / 4n items. Iterating through the list should be fast (just following a link), but there are much less than M comparisons.
> 1 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: How $log((mn^2)!) = \theta (mn^2 log(mn))$?
Knowing that $log(n!) = \theta(nlogn)$

# Answer
**Hint:**

$$\log(mn)\le\color{blue}{\log(mn^2)}\le\log(m^2n^2)=2\log(mn).$$
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Deriving the regular expression for C-style /**/ comments
I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /\**/ comments. Now, I've found this expression on the web:

```
/\*([^\*]*\*+[^\*/])*([^\*]*\*+|[^\*]*\*/

```

However, as you can see, this is a rather messy expression, and I have no idea whether it actually matches exactly what I want it to match.

Is there a different way of (rigorously) defining regular expressions that are easy to check by hand that they are really correct, and are then convertible ('compilable') to the above regular expression?

# Answer
I can think of four ways:

1. Define an automaton for the language you are interested in. Convert the regular expression to an automaton (using Brzozowski's derivatives). Check that both automata accept the same language (determinize and minimize or use a bisimulation argument).
2. Write loads of test cases and apply your regular expression to them.
3. Convert the automaton defined in point 1 to a regular expression, using standard techniques.
4. A combination of the above.
> 6 votes

# Answer
If you want to be sure that you're parsing C comments, you need to confront your model with the C specification. C99 §6.4.9 defines the syntax of comments as follows:

> 1. Except within a character constant, a string literal, or a comment, the characters `/*` introduce a comment. The contents of such a comment are examined only to identify multibyte characters and to find the characters `*/` that terminate it.
>
> 2. Except within a character constant, a string literal, or a comment, the characters `//` introduce a comment that includes all multibyte characters up to, but not including, the next new-line character. The contents of such a comment are examined only to identify multibyte characters and to find the terminating new-line character.

This is English prose, not a formal definition, but there is a reasonably clear interpretation in terms of a nondeterministic finite automaton (NFA) that consumes a comment:

* From the initial state, `/` followed by `*` enters the in-multiline-comment state, and `/` followed by `/` enters the in-single-line-comment state.
* From the in-multiline-comment state, `*` followed by `/` enters the post-comment state.
* From the in-single-line-comment state, a newline enters the post-comment state.
* Any other character leaves the state unchanged.

Note that to know whether the initial state applies, you have to perform a little more analysis to detect string and character literals.

Once you have an NFA, you can use standard techniques to build a regular expression (I don't see them in the Wikipedia articles, but they should be discussed in textbooks).

If you already have a regular expression and would like to test it, you can compare its generated language with the one from the NFA deduced from the language specification: equality of regular languages is decidable. One way to decide the equality is to build a minimal deterministic automaton for each; if the languages are equivalent, the minimal DFAs will be isomorphic.
> 5 votes

# Answer
If you are writing a parser, this kind of stuff is handled by the lexical analyzer. And there you can express this by regular expressions, or (as the `flex` examples I've seen show) just "escape into the underlying language" and finish off the job there. I.e., on seeing `/*` just skip ahead until you find `*/` (a DFA for this is easy to build, and from there a C fragment is simple to write).
> 0 votes

# Answer
No answers but three "don't do that" replies. Tsk!

In Emacs, I use `(rx (seq "/*" (*? anything) "*/"))` which expands to `"/\\*[^z-a]*?\\*/"`

Sadly, grep, sed, et. al., lack `*?` non-greedy repetition.

The kooky `[^z-a]` does what `"\\(?:.\\|\n\\)"` does.
> -1 votes

---
Tags: compilers, parsers, regular-languages
---


# Question
Title: Find if a given number must be in a set that is closed under gcd and lcm with some given elements
Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated).

> There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ and $\text{lcm}(A, B)$ are also in $S$.
>
> You are given $n$ positive integers $a\_1$, $a\_2$, ..., $a\_n$, which are elements of $S$ and a positive integer $k$. Find whether $k$ must be an element of $S$.
>
> For example, for 2 integers $45$ and $75$ and $k=15$, the answer is "YES" since $\gcd(45,75)=15$.
> For example, for 2 integers $45$ and $75$ and $k=9$, the answer is "NO" since $S$ can be $\\{1, 15, 45, 75, 225\\}$, which does not contain $9$.

I stumbled into it and lost an entire afternoon to it. Does anyone have an idea how to start? I could theoretically run a brute-force that lasts forever, but that seems to just defeat the purpose of the question.

# Answer
#### The idea

Without listing all elements in $S$, we can, following a usual approach, try checking whether $k$ is in $S$ "from the perspective of each distinct prime factor" of $k$. The subtlety and the difficulty is how and what we can do at each distinct prime factor.

#### A simple and fast algorithm

1. If $k=1$, return "YES" if all $a\_i$'s are relatively prime and "NO" otherwise.
2. Now $k$ has at least one prime factor. Factorize $k$ to obtain $k=\prod\_{j=1}^\ell{p\_j}^{e\_j}$, where $\ell\ge1$, $p\_j$ is a prime, $e\_j\ge1$ for all $j=1, \cdots, \ell$.
3. For $j$ from $1$ to $\ell$, do the following.
    1. Find all multiples of ${p\_j}^{e\_j}$ among $a\_i$'s. If there is none, return "NO".
    2. If $k$ is not a multiple of the greatest common divisor of those multiples, return "NO".
4. Return "YES".

#### Time-complexity and space complexity

The algorithm runs in $O(\sqrt{M}+\max(n,\log M)\max(1, \log M))$ time, where $M=\max(a\_1,\cdots, a\_n)$.

It can be implemented with $O(1)$ auxiliary space.

An implementation in Python runs well within half a second for each test case at the online judge, where $n\le 50000$ and $M\le10^{12}$. Of course, your mileage might vary.

#### Proof of Correctness.

Call a set of positive integers dm-closed if it is closed under gcd and lcm.

Let $U$ be the set of all factors of the least common multiples of all $a\_i$'s. Verify that $U$ is a dm-closed set that contain all $a\_i$'s.

Let us prove that the algorithm returns 'NO' $\implies$ $k$ is not in some dm-closed set that contains all $a\_i$'s. There are three cases.

1. The algorithm returns 'NO' at step 1.1. That means there is a number $h\>1$ such that all $a\_i$'s are multiples of $h$. Consider the set of all numbers in $U$ that are multiples of $h$.
That set is a dm-closed set that contains all $a\_i$'s but does not contain $k=1$.
2. The algorithm returns 'NO' at step 3.1. That means for some $j$, no $a\_i$ is a multiple of ${p\_j}^{e\_j}$. Consider the set of all numbers in $U$ that are not multiples of ${p\_j}^{e\_j}$.
That set is a dm-closed set that contains all $a\_i$'s, which does not contain $k$, since $k$ is a multiple of ${p\_j}^{e\_j}$.
3. The algorithm returns 'NO' at step 3.2. That means for some $j$, $k$ is not a multiple of $g\_j$, the greatest common divisor of all $a\_i$'s that are multiples of ${p\_j}^{e\_j}$. Consider set $$D=\\{u\in U\mid \text{either }u\text{ is not a multiple of }{p\_j}^{e\_j}\text{ or }u\text{ is a multiple of }g\_j\\}.$$ $D$ is a dm-closed set that contains all $a\_i$'s, which does not contain $k$, since $k$ is a multiple of ${p\_j}^{e\_j}$ but not a multiple of $g\_j$.

Let us prove that the algorithm returns 'YES' $\implies$ $k$ is in every dm-closed set that contains all $a\_i$'s. Let $S$ be an arbitrary dm-closed set that contains all $a\_i$'s. There are two cases.

1. The algorithm returns 'YES' at step 1.1. That means the greatest common divisor of all $a\_i$'s is 1. Since $S$ is closed under gcd and $S$ contains all $a\_i$'s, $S$ must contain 1.
2. The algorithm returns 'YES' at step 4. That means the algorithm does not return at step 3.1 nor at step 3.2. So, for all $j$, $k$ is a multiple of $g\_j$, the greatest common divisor of all $a\_i$'s that are multiples of ${p\_j}^{e\_j}$. Note that $g\_j$ is a multiple of ${p\_j}^{e\_j}$. Let $h$ be the least common multiple of all $g\_j$. Note that all $g\_j$ are in $S$, and hence so is $h$.

* Since for all $j$, $k$ is a multiple of $g\_j$, $k$ is a multiple of $h$.
    * Since for all $j$, $g\_j$ is a multiple of ${p\_j}^{e\_j}$, so is $h$. Since ${p\_j}^{e\_j}$'s are pairwise relatively prime, $h$ is a multiple of $k$, the product of all ${p\_j}^{e\_j}$'s.

So $k$ and $h$ are multiples to each other. Hence $k=h$. Since $h$ is in $S$, so is $k$. $\quad\checkmark$
> 1 votes

# Answer
Take John’s answer. However, we don’t actually need a prime factorisation. Let’s say we have a large x which might be prime or composite (and finding out takes a long time). Instead of trying to factor x, we calculate the gcd with the other numbers. A gcd ≠ 1 means we found a factor. If all gcds are = 1 then it doesn’t matter whether x is composite or not.

With this incomplete information we can determine if k has to be an element of S.
> 0 votes

---
Tags: algorithms, time-complexity, sets, number-theory
---


# Question
Title: Vector clock :why Singhal Kshemkalyani differential technique require FIFO for message passing?
> Singhal–Kshemkalyani’s differential technique is based on the observation that between successive message sends to the same process, only a few entries of the vector clock at the sender process are likely to change. This is more likely when the number of processes is large because only a few of them will interact frequently by passing messages. In this technique, when a process Pi sends a message to a process Pj , it piggybacks only those entries of its vector clock that differ since the last message sent to Pj.

I am understanding above but not the following statement

> this technique requires that the communication channels follow FIFO discipline for message delivery. link

Chapter 3 -Logical clock from above book and sub topic is Efficient implementations of vector clocks

Thanks lot.

# Answer
> 3 votes
All it's saying is that the messages between two processes need to be received in the order they are sent. If I'm going to send only differences between the previous message, we both better agree on what "the previous message" is.

For example, if I send "increment the first and second component" and then "increment the first and third component" but you receive them in the opposite order, you are likely to make form incorrect assumptions about how these messages relate to messages you're receiving from other processes. The correct intermediate state will have a vector clock that looks like $(1,1,0)$ but the one you'd reconstruct from the out of order messages is $(1,0,1)$. A message from another process with vector clock $(2,0,1)$ might then look like its strictly after the out-of-order message when, in fact, it is concurrent with it.

# Answer
> 0 votes
Say P1 sent a message to P2 saying ((1,x1),(3,x3),(4,x4)) informing P2 of updates in the values on 1,3, 4 Process ids. Later, it sends another msg to P2 saying ((1,x11),(5,x7)). This time it sends information only about itself and pid 7. If the second message reaches P2 before the first message; then P2 will know only about the update in process 1 and 7 and may go ahead sending further msgs to other processes say P10. Later it would realise that the msg he had sent P10 is incorrect as it does not reflect the updates on pid 3 and 4 and hence was incorrect

---
Tags: distributed-systems, clocks
---


title: Complexity of taking recursive modulo

text:
# Question
Title: Complexity of taking recursive modulo
Given 2 integer $M$ and $N$, a recursive modulo is $M \bmod (M \bmod (M \bmod ...(M \bmod N)$ until the result is 0. What is its time complexity?

I guess that it's $O(log(M))$ but I can't prove it.

# Answer
> 2 votes
Extending on @gnasher729's answer, I tried to find, given $N\in \mathbb{N}$, what is the smallest $M$ such that $N$ iterations of modulo are necessary before getting $0$ (and even finding if such an $M$ existed).

What we want to find is the smallest $M$ such that $\forall k\in \\{1, …, N\\}$, $M \equiv -1 \mod k$. Denote $f(N)$ such an $M$.

A few lines in Python after that, I found the following values:

* $f(2) = 1$;
* $f(3) = 5$;
* $f(4) = 11$;
* $f(5) = f(6) = 59$;
* $f(7) = 419$;
* $f(8) = 839$;
* $f(9) = f(10) = 2519$;
* $f(11) = f(12) = 27719$;
* $f(13) = f(14) = f(15) = 360359$.

Given those observations, I conjectured that the following algorithm could compute $f(N)$:

* $f(2) = 1$;
* if $N \> 2$, then
    + either $N = p^{\alpha}$ with $p$ prime, and $f(N) = p\times (f(N-1) + 1) - 1$;
    + or $f(N) = f(N-1)$.

After a bit of search, I found out that I just rediscovered a formula to compute $\text{lcm}(1, 2, …, N) - 1$.

Given the definition of the least common multiple, it is clear that $f(N) \equiv -1 \mod k$ for all $k\in \\{1, …, N\\}$.

$f(N)$ is indeed the smallest such $M$: assume $M\<\text{lcm}(1, 2, …, N) - 1$. Then there exists $k\in \\{1, …, N\\}$ such that $k \not\mid M + 1$. That means that $M\not\equiv -1\mod k$.

# Answer
> 0 votes
It’s obviously O(n) since the first modulo gives a result from 0 to N-1, then 0 to N-2, and so on. You can also construct m so that n steps are indeed needed. However, such an m could be very large, so the size of m will also limit this. (m = LCM(1..n) - 1 seems to be the smallest such number, so the number of steps can be n only if m ≥ LCM(1..n) - 1.)

For random x, the result of x mod n is (n-1)/2 on average, so the expected number of iterations would be log2(n).

For any m, n = m gives one iteration, and n \> m gives two iterations. If n \< m, then for m-1 ≥ n ≥ floor(m/2) + 1 we get all values from 1 to m - floor(m/2) - 1 after the first iteration.

For m \< 100,000, the worst case is m = 93,596 and n = 33,851 where n = (93596 modulo n) goes through the sequence 25,894, 15,914, 14,026, 9,440, 8,636, 7,236, 6,764, 5,664, 2,972, 1,464, 1,364, 844, 756, 608, 572, 360, 356, 324, 284, 160, 156, 152, 116, 100, 96, 92, 32, 28, 20, 16, 12, 8, 4, 0. This is 34 iterations or 2.26 * log2(n). It is also the first record holder with even m. For m \< 1,000,000, the worst case is m = 830,939 and n = 226,858 with 42 iterations.

So it seems that the worst case number of iterations grows at a small multiple of log\_2 (m), with some n not far from m, and the values m modulo n around maybe 3/4 n instead of n/2. The case of having results modulo n of n-1, n-2, n-3 etc. is just too rare.

---
Tags: complexity-theory, time-complexity, number-theory
---


# Question
Title: Find hamilton cycle in a directed graph reduced to sat problem
I need to find a **Hamiltonian cycle** in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to construct a CNF formula to find an **Hamiltonian path**:

`Xi,j` \- node j is in position i in the path

List of constraints:

1. Each node j must appear in the path `x1j ∨ x2j ∨ · · · ∨ xnj` \- for every node j
2. No node j appears twice in the path `¬xij ∨ ¬xkj` for all i, j, k with i 6= k.
3. Every position i on the path must be occupied - `xi1 ∨ xi2 ∨ · · · ∨ xin` for each i
4. No two nodes j and k occupy the same position in the path - `¬xij ∨ ¬xik` for all i, j, k with j != k
5. Nonadjacent nodes i and j cannot be adjacent in the path - `¬xki ∨ ¬xk+1,j` for all (i, j) !∈ E and k = 1, 2, . . . , n − 1.

My question is, how can I find **Hamiltonian cycle** using these constraints? I understand that I need to check if there's a cycle (`v1==vn`), that's one thing (But I got constraint 2). Second, it's a directed graph and I don't know how can I assure that the vertices would be in the right order of the edges, I thought about this:

Every two nodes must have edges - `Xki ^ Xk+1j` for each (i,j)∈ E and k = 1, 2, . . . , n − 1.

But it doesn't seem to work, any help would be appreciated.

EDIT

What I did was to add another constraint -

6. No edges from the set: (i,j)!∈ E that are the last and the first

# Answer
> 4 votes
Just add the constraint that $x\_{1j}=x\_{nj}$ for all $j$, and make a special exception to constraint 2 so that you omit constraint 2 in the case where $i=1$ and $k=n$.

Everything works fine for a directed graph. You just need to interpret constraint 5 appropriately.

# Answer
> 2 votes
I suppose practical SAT solvers might search for and remove them, but I'd still suggest not giving it redundant variables - if you do know `v1==vn`, then just replace each instance of `vn` with `v1`.
If `n` is the number of vertices then you'd actually have `v0 == vn`, rather than `v1==vn`.

You can remove any one of {1.,2.,3.,4.}, since the combination {3.,4.} or {1.,2.}
will force X or its transpose respectively to be the graph of a function, and
for functions from a finite set to itself, surjectivity is equivalent to injectivity.

# Answer
> 0 votes
I think all you need is to extend the fifth constraint to all k = 1, ...,n and where there is k+1 in the constraint, add (mod n) operator.

This ensures that there is an edge from the last vertex to the first in the path, meaning it's a cycle.

---
Tags: graphs, satisfiability, propositional-logic, hamiltonian-path, hamiltonian-circuit
---


# Question
Title: algorithm analysis - complex dependant nested loop
First of all, I know there are many questions like this on the site. But I think this case is a bit different.

Consider the following code:

```
int i, j, k;

for (i = 1; i <= n; i++){
    for (j = 1; j <= (n-i); j++) {
        System.out.print(" ");
    }

    for (k = 1; k <= (i-j); k++) {
        System.out.print(i);
    }

    System.out.println();
}

```

What would be the time complexity of this code? It seems like O(n^2) to me but I can't justify it properly.

How our professor told us to compute complexity is just by adding all the summations together from every line.

$$ (n+1) + \sum\_{j=1}^{N-i} + \sum\_{j=1}^{N-i} + \sum\_{k=1}^{i-j} + \sum\_{k=1}^{i-j} + n $$

However, I've never seen examples with summations like $\sum\_{j=1}^{N-i}$, It's always either $\sum\_{j=1}^{N-1}$ or some constant number being subtracted from N, which is easier to sum. So, How would I solve this? And is it O(n^2)?

# Answer
The number of print statements executed is $$ \sum\_{i=1}^n \left\[ \left(\sum\_{j=1}^{n-i} 1\right) + \left(\sum\_{k=1}^{i-(n-i+1)} 1\right) + 1 \right\], $$ where the second sum is zero if $1 \> i-(n-i+1)$.

The running time is proportional to the number of print statements, so it remains to compute the value of the expression above, or at least to give a good estimate. This I leave to you.
> 0 votes

# Answer
For better analysis the code, you can rewrite loop that use variable $k$ in terms of $n,i$ not $j$:

```
  int i, j, k;

    for (i = 1; i <= n; i++){
        for (j = 1; j <= (n-i); j++) {
            System.out.print(" ");
        }

        for (k = 1; k <= (i-(n-i+1)); k++) {
            System.out.print(i);
        }

        System.out.println();
    }

```

Let $T(n)$ be time complexity of code. Therefore our code have two disjoint inner loop that displayed by the following summation (suppose each operation `System.out.print` need constant time, notice that, the inner loop with variable $j$ has the cost $(n-1)+(n-2)+\dots+1=\sum\_{i=1}^{n-1}i$), so:

$$T(n)=\sum\_{i=1}^{n-1}i+\sum\_{i=1}^{n}\left(\sum\_{k=1}^{i-n+i-1}\mathcal{O}(1)\right)$$ $$=\sum\_{i=1}^{n-1}i+\sum\_{i=1}^{n}\left(\sum\_{k=1}^{2i-n-1}\mathcal{O}(1)\right)$$ $$=\sum\_{i=1}^{n-1}i+\sum\_{i=1}^{n}(2i-n-1)=\Theta(n^2)+\mathcal{O}(n^2)$$ $$=\Theta(n^2)$$
> 0 votes

# Answer
Let us work out an example with $n=5$.

The outer loop is executed with $i=1,2,3,4,5$. Thus the first inner loop executes $4+3+2+1+0$ `print`'s. And the second inner loop $0+0+0+2+4$ `print`'s.

For $n=6$, we have $5+4+3+2+1+0$ `print`'s. And the second inner loop $0+0+0+1+3+5$ `print`'s.

We can easily generalize and get the counts $n$ (outer), $\dfrac{(n-1)n}2$ (first inner) and $\dfrac{n^2-1}4$ or $\dfrac{n^2}4$ depending on the parity of $n$ (second inner).
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Top type in JavaScript?

text:
# Question
Title: Top type in JavaScript?
I am wondering, what is the top type, $\top$, in JavaScript? The diagrams at MDN make it look as if 'null' is a top type, but wikipedia's entry for top type indicate that it is Object in JS, which makes more sense. Am I misreading the MDN article?

# Answer
> 3 votes
JavaScript / ECMAScript does not have a static type system, so it doesn't really make sense to talk about "types". In general, "type theory" means "static type theory", and thus you will get non-sensical results when trying to apply type-theoretic concepts to dynamically-typed languages.

From the point of view of traditional type theory, ECMAScript has either no types or a single type `dynamic`, i.e. ECMAScript is either *untyped* or *uni-typed*. To make matters worse, the ECMAScript Specification also uses not one but two different kinds of types in the specification.

Part of the confusion is that the term "type" is used differently by different people. In traditional Programming Language Theory, "type" means "static type" and there is no other kind of type, period. But, there are also Computer Scientists who oppose this dogmatic view. For example, in his influential paper on Typeful Programming, Luca Cardelli admits that static typing is limited and thus dynamic typing is necessary (but argues that as much as possible should be statically typed and dynamically only if there is no other choice).

This gets even more confusing in languages like Java where both the static and the dynamic types are relevant, for example, overload resolution depends on the static type but virtual method dispatch depends on the dynamic type.

Over the years, there have been several attempts at creating a static type system for ECMASCript or an ECMAScript-like language:

* *ECMAScript 4* was an abandoned revision of ECMAScript. ES4 included a whole smorgasbord of features – which is ultimately why it collapsed under its own weight – including static typing. ES4 tried to be everything for everyone, it included both delegation-based and inheritance-based code re-use, both prototype-based and class-based OOP (with interfaces thrown in for good measure), both standalone constructors and constructors with are members of classes, both dynamic and static types and everything in-between, where the static typing rules can be both nominative and structural and the types can be either manifest or inferred. It had both packages and namespaces (which, to add even more confusion, are not what you think they are). And if that weren't enough, it also contained the entirety of ECMAScript for XML (E4X).
* *ActionScript* was the programming language for Flash. It started out as a variant of ECMASCript, over time, it added classes and static types, then it became a superset of ECMASCript 4.
* *JavaScript 2.0* was Mozilla's proposed successor of JavaScript 1.5. It was turned into a superset of ECMAScript 4.
* JScript.NET was an ECMAScript-like language for the .NET platform based on JScript with static types.
* *Closure* is an ECMAScript compiler / transpiler / optimizer / minifier / type checker by Google.
* *Flow* is a static type checker and type annotation language for ECMAScript by Facebook.
* *TypeScript* is a superset of ECMAScript with static typing by Microsoft.
* plus dozens of academic research projects …
* Most recently, there is a proposal to add type annotations to ECMAScript proper. However, this is not a type system, its purpose is merely to make it easier to work with systems like Flow or TypeScript by essentially having ECMAScript treat type annotations as comments and ignore them.

Of these, the two most widely-used ones are Flow and TypeScript. I am most familiar with TypeScript, so I will focus on that.

If you want to understand type systems related to ECMAScript, it makes sense to study the type systems that have been designed by people much smarter than me. All of these type systems tend to be rather complex and feature-rich with many advanced and cutting-edge features, since they are designed to capture highly dynamic and reflective programming patterns of a language that was never designed to have a static type system.

TypeScript has no fewer than 7 different "special" types, 6 of which could be reasonably classified as either a *bottom type* or a *top type*. In fact, some of those types even act as both at the same time and sometimes, the behavior depends on a configuration parameter.

`any` is a type that is designed to, effectively, "turn off" the type system. A value of type `any` can be assigned to a reference of any arbitrary type and a value of any arbitrary type can be assigned to a reference of type `any`. A value of type `any` can be passed as an argument for any arbitrary parameter type. A value of type `any` can be used with any arbitrary operator, and you can access any arbitrary property on a value of type `any`. Depending on the setting of the configuration parameter `noImplicitAny`, an operation whose type the type checker cannot figure out will either raise a type error or just be typed as `any`.

Since `any` is assignment-compatible with everything and everything is assignment-compatible with `any`, `any` acts both like a top type and like a bottom type.

The main use case for `any` is when you want to adopt typing for a large, previously untyped, code base or you are interacting with an untyped third-party code base that you have no control over. Usually, if you add typing to a previously untyped code base, you will be greeted with thousands, if not tens of thousands of type errors. You can quickly "fix" every type error by annotating the type as `any`, and then refine those annotations over time, preventing you to get buried under a mountain of type errors without making progress on your application.

`unknown` is the tamer, type-safe, cousin of `any`. `unknown` was introduced relatively late in the development of TypeScript. Its use is somewhat similar to `any` in that operations whose type TypeScript can't figure out can be configured to have type `unknown`. Also similar to `any`, `unknown` acts as a top type, meaning, every type is assignment-compatible with `unknown`. But the opposite is not true: unlike `any`, a value of type `unknown` can only be assigned to `unknown` and `any`. Also, you cannot access any properties on `unknown`.

You always have to narrow the type first (using a conditional runtime type check, type assertion, etc.), after which TypeScript's flow-sensitive type system will no longer consider the type to be `unknown`.

`object` is the top type for all object types, but not primitive types.

Both `null` and `undefined` denote the absence of a value. If `strictNullChecks = false`, they behave as bottom types which are inhabited by the values also called `null` and `undefined`. The fact that there are two types in TypeScript is because there are two values in ECMAScript. The fact that there are two values in ECMAScript is due to hysterical raisins. According to the ECMAScript specification, `undefined` is for un-initialized variables and `null` is for intentionally absent values.

`void` has similar semantics to `void` in C, Java, or C#. It is used the same way that *unit* is used in impure functional languages, i.e. to denote that an expression does not evaluate to a useful value (or, in other words, that the expression is evaluated purely for its side-effects, or in even other words, that the expression is not an expression at all but a *statement*). However, *unit* typically only has a single, useless, value (hence why it is *called* "unit"), whereas in TypeScript, there is no `void` value. OTOH, a function typed as `void` is actually allowed to return *any* value (so, one could say that *all* values are `void` values) but on the *other* other hand, one is not allowed to do anything with a value of type `void`.

`never` is the "impossible" bottom type, i.e. it represents a value that will never exist. For example, a function that never returns would have the type `never`.

Here is a handy table with the assignment compatibility of all the special types:

|  | `any` | `unknown` | `object` | `void` | `undefined` | `null` | `never` |
| --- | --- | --- | --- | --- | --- | --- | --- |
| `any` |  |  |  |  |  |  |  |
| `unknown` |  |  |  |  |  |  |  |
| `object` |  |  |  |  |  |  |  |
| `void` |  |  |  |  |  |  |  |
| `undefined` |  |  | ✓✗? |  |  | ✓✗? |  |
| `null` |  |  | ✓✗? | ✓✗? | ✓✗? |  |  |
| `never` |  |  |  |  |  |  |  |

\[TypeScript Playground Example and with `strictNullChecks = false` for comparison\]

---
Tags: type-theory, type-checking
---


# Question
Title: Aggregate text data of some particular column
I have a dataset as follows

```
Biodata
last_name  first_name  age   Description     Hobby
Smith       John       20    In high school  Music
Johnson     Robert     45  Software Developer Gardening
Williams    David      15     Junior school  Baseball
Davis       Michael    65     Traveler       Skydiving
Miller      Molly      25     Scientist      Cycling

```

Now I got a question from a assignment that **Aggregate text data under “Description” and “Hobby”**

I cannot understand what is the meaning of Aggregate text data?

If any one understand the question please share their view point. I want to know it theoretically how could any one aggregate text data depend upon description and Hobby column.

This is a coding assignment of python. But currently I don't bother about coding. I want to know the theoretical meaning of this question and want to solve it manually.

Thank you in advance

# Answer
> 0 votes
My assumption is that they want you to normalize the text data in those columns. In other words, you may create a collection of the text, and the two columns would *refer* back to that collection. Does that make sense?

# Answer
> 0 votes
Create two lists,

descriptions = \[ \],hobbies = \[ \]

Iterate through the rows of data and append the description and hobby for each row to the appropriate lists.

Aggregated data is now stored in the descriptions and hobbies lists

---
Tags: terminology, logic, data-sets
---


# Question
Title: Minimal Number of Transactions to Settle Outstanding Poker Game
There are several players at the end of the poker night with wins and losses, with zero sum. What is the optimal solution to settle the balance that minimize the total number of transactions (eg. if we consider a transaction as a venmo payment).

```
name  | balance (N means how much net win, negative means lost)
A     | -200
B     | +100   <- biggest winner
C     | -50
D     | +25
E     | +75
F     | +50

```

**Solution1: 12 constant**

One naive solution is to have a central bank every everyone buys in before the game and cashes out in the end, there will require a constant 2\*n transactions - 12 transactions in this case.

**Solution2: 5 pay the biggest winner**

Another better solution is to have all the losers pays the biggest winner, then the winner gives to other smaller winners.

Transactions needed will be 5:

```
Send -> Receive | Amount
A -> B          | 200
C -> B          | 50
B -> D          | 25
B -> E          | 50
B -> F          | 50

```

**Solution3: 4 cancel out?**

Just by the look at the amount, a better solution only takes 4 transactions:

```
Send -> Receive | Amount
A -> B          | 100
A -> D          | 25
A -> E          | 75
C -> F          | 50

```

Thoughts: I feel this is related to a graph problem but also looks like a linear planning, but I lack the proper knowledge background to tell if a proper algorithm exists.

```
    A    B    C    D    E    F   Sum
A                               -200
B                               -50
C                                0
D                                0
E                                0
F                                0
Sum  0  +100   0  +25   +75  +50

```

Minimize the number of populated cells.

# Answer
This problem is strongly NP-hard.

A set of transactions can be regarded as a directed graph. Let $A$ be the set of vertices corresponding to players with positive losses and let $B$ be the set of vertices corresponding to players with positive wins. The number of transactions is at least $\max(|A|,|B|)$ because each vertex in $A$ must have at least one outgoing edge, and each vertex in $B$ must have at least one incoming edge.

Suppose $|A| \geq |B|$ and there is a solution with $|A|$ transactions. Then, every $a \in A$ has exactly one outgoing edge. For each $b \in B$, let $A\_b$ be the set of vertices reachable to $b$ then the sum of losses in $A\_b$ is equal to the win of $b$. That is because there are no outgoing edges from $A\_b$ other than $b$, and $b$ has no outgoing edges.

With these facts, a reduction from the 3-partition problem is straightforward. We have positive integers $a\_1, \dots, a\_{3m}$ and $t = \frac{1}{m} \sum\_{i=1}^{3m} a\_i$ with restriction: $t/2 \< a\_i \< t/4$ for each $i$. The 3-partition problem with restriction is strongly NP-hard.

We create $3m$ players $A$ with losses $(a\_i)\_i$, and $m$ players $B$ with wins $t$. The 3-partition problem instance has a solution if and only if there is a set of $3m$ transactions clearing all wins and losses.

For a 3-partition $(A\_i)\_{i=1}^m$, we can make $3m$ transactions of from $\\{ a \rightarrow b\_i \mid i \in \[m\], a \in A\_i \\}$.

Conversely, for a solution with $|A| = 3m$ transactions, we have a solution to the 3-partition problem instance as $\\{A\_b \mid b \in B \\}$. The sum of integers is $t$ as shown above, and we have $|A\_b| = 3$ due to the restriction.
> 1 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Is P vs NP, a paradox in a hypothetical perspective?
In a hypothetical scenario, where a precise and formal definition does not exist here, and thus expressed with analogies and verbal reasoning for the sake of simplifying the P, NP problem.

A(lan) Turing Machine arrives to the "Universal-Algorithm-Island", and meets Christopher, an oracle with a True or False response.

ATM: "Long time no seen".

Christopher: "True".

---

**Case 1**

ATM: "... do all machines in 'UAI' have NP algorithm to solve them?".

Christopher: "True".

ATM: "Do all machines in 'UAI' have no NP algorithm to solve them?".

Christopher: "False".

**Case 2**

ATM: "... do all machines in 'UAI' have P algorithm to solve them?".

Christopher: "False".

ATM: "Do all machines in 'UAI' have no P algorithm to solve them?".

Christopher: "True".

---

Otherwise, the oracle is lying.

Generally speaking, in regard to the above - both classes cannot be equal, otherwise its a contradiction.

Does this make sense?

# Answer
> 4 votes
This makes no sense to me. You imagine a scenario that is self-contradictory, and then observe that it is a contradiction, and.. then what? All that proves is that your scenario can't happen.

It's like me imagining scenario where I walk up to a knight who never lies, and then the knight tells me "2+2=5". Well, that scenario is self-contradictory, so it can't happen -- it is not internally consistent. I don't get to conclude that P!=NP from this scenario, or that the Goldbach conjecture is true, or anything useful at all. All I can conclude is that my scenario can't actually happen.

The complexity P, NP are mathematical objects with a precise, formal definition. The notion of "in a hypothetical perspective" has no meaning here. Either P = NP, or it doesn't. It's not the kind of statement where there are multiple valid perspectives on it. It would be like me trying to claim that "2\*3 = 7 from a hypothetical perspective" - nonsense. This is not something you can reason about with analogies or verbal reasoning.

I don't think you are going down a fruitful path. The way you are approaching this doesn't seem to engage with the actual P vs NP question at all.

# Answer
> -4 votes
Interesting perspectives presented by (Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, 2013, Chapter 7), has shown analogies to the Liar-paradox, Circuits and more, relating to the P, NP problem.

This tackles directly the hypothetical perspective, in sense of being a paradox, which brings up intuition of why P, NP problem is also one.

---

An interesting solution given by 'ChatGPT Dec 15 Version', is the following: "... The P versus NP problem is similar to the liar paradox in that it involves a self-referential aspect, in this case the relationship between the time it takes a computer to solve a problem and the time it takes a computer to verify a solution. Just as with the liar paradox, it is not clear whether it is possible to definitively resolve the P versus NP problem, and it continues to be an active area of research in computer science. "

---
Tags: complexity-theory, turing-machines, philosophy, hypercomputation
---


# Question
Title: Is this varient of longest increasing nested sets problem NP-hard？
There are two types of sets $\mathcal{X} = \\{X\_{1}, X\_{2}, \ldots, X\_{n\_{1}} \\}$ and $\mathcal{Y} = \\{Y\_{1}, Y\_{2}, \ldots, Y\_{n\_{2}}\\}$ such that $X\_i, Y\_j \subseteq \[m\]=\[\mathrm{poly}(n)\]$ and $n = n\_{1} + n\_{2}$. Given a sequence $\alpha$ over $\mathcal{X} \cup \mathcal{Y}$, the goal is to find the longest (increasing with respect to $\alpha$) sub-sequence $\beta$ such that

1. the sub-sequence $\beta$ restricted to $\mathcal{X}$ is a sequence of nested sets, that is $\left. \beta \right|\_{\mathcal{X}} = (X\_{i\_{1}}, X\_{i\_{2}}, \ldots, X\_{i\_{\ell}})$ satisfies that $X\_{i\_{1}} \subseteq X\_{i\_{2}} \subseteq \cdots \subseteq X\_{i\_{\ell}}$.
2. These two sub-sequences $\left. \beta \right|\_{\mathcal{X}}$ and $\left. \beta \right|\_{\mathcal{Y}}$ have no common elements, that is, for every pair of sets $X\_{i}, Y\_{j}$ in $\beta$, $X\_{i} \cap Y\_{j} = \varnothing$.

Is (the decision version of) this problem NP-hard, or can it be solved in polynomial time (with respect to $n$)?

For the special case, if $\mathcal{Y}$ is empty, this problem can be solved by using dynamic programming in polynomial time.

# Answer
This problem is polynomial-time solvable.

Suppose we know the last selected $X\_\ell$. Then, remove all $Y$s that have a non-empty intersection to $X\_\ell$. Now, we don't have to check for the second condition anymore because we have $X\_i \cap Y\_j \neq \emptyset \implies X\_\ell \cap Y\_j \neq \emptyset$ by the first condition $X\_i \subseteq X\_\ell$. Therefore, we reduced the problem to $n\_1$ subproblems of the already-known polynomial-time solvable case of when $\mathcal{Y}$ is empty.
> 2 votes

---
Tags: dynamic-programming, np-hard
---


# Question
Title: Function whose domain is strictly included in its range
Hi I'm doing some exercices on reductions and one of them is like this:

My problem rather than doing the reduction is understanding it. For the positive case I want that if Mx(x) never stops then p's domain has to be strictly included in q's domain which has to be stricly included in p's range. Am I wrong? Therefore Dom(p) has to be stricly included in Range(p), right?

Let's forget about reductions for a moment, my problem here is: is there any function $f(x)$ whose domain is strictly included in its range?

We would want to have $Dom(f(x)) = \\{1\\}$ and $Range(f(x)) = \\{1, 2\\}$ That would mean that 1's image has to be 1 **AND** 2 :/

What am I doing wrong?

Thanks for your time and have a nice day! :D

# Answer
Without getting to the technicality of codomain/range/image and surjective functions, the property you ask for can surely happen. For instance,

$$f(x) = 2x$$

defined over the domain interval $\[0,1\]$, has the image $\[0,2\]$. This should not happen over finite domains.
> 1 votes

# Answer
You are completely violating the rules for a function. For any element x in the domain there is only one image. This is the thing which differentiates a function from a relation. In a relation it is perfectly valid for an element to be related to b as well as c.
> 0 votes

# Answer
I solved the problem:

It did seem impossible to make a deterministic function with the described properties (since only integer numbers are allowed). The trick of this exercise is using infinite domains.
> 0 votes

---
Tags: reductions, undecidability, semi-decidability
---


# Question
Title: How to count number of 1s of the first k positions in a bitset (bitmap)?
**Input**: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.

**Output**: the total number of 1s in the first $k$ position of $b$.

Obviously it can be done in $O(k)$, is there any more efficient way in C++ such as $O(\frac{k}{W})$, where $W$ is the word size of the machine? Note that the popcount instruction only works when $k=L$, but $k$ is varying.

# Answer
> 2 votes
Popcount is going to be your best option here. As `j_random_hacker` mentions in a comment, popcount on a single word can be done in $O(\log W)$ time if implemented by hand, or $O(1)$ if the machine provides a dedicated opcode for it (which should take a constant number of clock cycles—but then again, $W$ should also be a constant for any given machine).

(Note: if $b$ is longer than a single word, then you can just use popcount directly on the first $\lfloor \frac{k}{W} \rfloor$ words, and ignore the last however many others, in $O(\frac{k}{W})$. It's only the one word in the middle that you need any fancy algorithm for. So I'm going to be solving the special case where $k \< W$. If this isn't the case, which it normally won't be, then replace $k$ with $k \bmod W$.)

The part that depends on $k$ is getting rid of the $W-k$ unneeded bits. One way to do this is masking: generate a mask of $k$ ones, then AND your value with it. (You can generate such a mask by starting with 1, left-shifting $k$ times, then subtracting 1 and taking the complement. Or you can start with only the highest bit set and arithmetic-right-shift $k$ times.)

Another way is to just push the unneeded bits off the end of the word: logical-right-shift your number $W-k$ times and the unwanted bits will be gone.

Which of these is most efficient depends on the specifics of your machine. If it can do bitwise operations and variable shifts in a constant number of clock cycles, then the whole thing is still $O(1)$. If it can't do variable shifts, then it takes $O(k)$; if it can't do constant-time bitwise operations, then there's no way to get better than $O(W)$.

# Answer
> 0 votes
If you can access the bits as an array of W bit words: Let k = nW + k'. If k' \> 0 then shift the last word by (W - k') bit positions and use the result instead of the last word, so n is increased by 1.

If there is a fast "popcount" instruction then you use that.

Otherwise, you can split a word w into (w & 0x33333333) and ((w \>\> 1) & 0x33333333) with enough 3's to catch every bit, and interpret this as an array of 32 2-bit counters. Add this counters in groups of three, and instead of about k bits you have about k/3 2 bit counters.

Take these counters and split them into (w & 0x0f0f0f0f) and ((w \>\> 2) & 0x0f0f0f0f) and you get two 4 bit counters for each 2 bit counters. These can hold results up to 15, the 2 bit counters hold numbers up to 3, so you add them in groups of 5 and get k/15 4 bit counters. Next you add 8 bit counters 17 at a time and get k/255 8 bit counters, then k/65535 16 bit counters and you will end up with a single 64 bit counter.

This is quite fast because we process 1.5 words at a time in the first round, 3.75 words at a time in the second round, almost 32 words at a time in the third round.

---
Tags: counting, bit-manipulation, c++
---


# Question
Title: To write an IP and relax it to LP for finding a multi-set in a graph
I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given:

* A digraph `G = (V,E)` with wv being the weight on vertex `v` for every `v ∈ V`.
* A multi-set S is a set such that it contains elements more than one time. Suppose from a directed edge `e = (u,v)` either u is in S atleast one time or v is in S atleast 2 times.
* The weight of the set S is the sum of all the vertices in it, vertices that appear multiple times also appear in the sum multiple times.

I have to write an IP for finding the multi-set that d-covers and minimizes the weight, relax it to LP and provide a rounding scheme that guarantees 2-approximation to the best multi-set

---

My proposed solution:
For IP:

min Σv∈V wv . xv
s.t xu \+ 2xv ≥ 1 ∀ {u,v} ∈ Σe∈S
xu \+ 2xv ∈ {0,1}

Relaxed LP:
min Σv∈V wv . xv
s.t 0 \< xu \+ 2xv ≤ 1 ∀ {u,v} ∈ Σe∈S
OPT ≥ Σv∈V wv . xv

---

Apart from this, I have to also write a rounding scheme that guarantees a 2-Approximation to the best multiset. Which I don't understand how to approach.

Your kind help would be appreciated in correcting my solution and with the rounding scheme.

Thank you in advance.

# Answer
I think there is a problem in the definition of your IP and LP systems.

If $x\_u$ represents the number of times you can select a vertex $u$ in the multiset $S$, then you want to verify the following conditions:

* For an edge $(u, v)\in E$, either $x\_u \geqslant 1$ or $x\_v \geqslant 2$. That means that $x\_u + \frac{x\_v}2\geqslant 1$ (or equivalently $2x\_u + x\_v\geqslant 2$). There lies your first error, since you wrote $x\_u + 2x\_v\geqslant 1$ instead.
* Since you used "at least" in the description of the previous condition, the lines $x\_u+2x\_v\in \\{0,1\\}$ in the IP system and $0\<x\_u+2x\_v\leqslant 1$ in the LP system are wrong. Nothing prevents you to have a $x\_u$ greater than $1$, and $x\_u+2x\_v$ could even be equal up to $6$ (see below).
* If you want an upper bound, it would be on $x\_u$ (and $x\_v$), not on the sum. For the IP, it would be $x\_u\in \\{0,1,2\\}$ and for the LP it would be $0\leqslant x\_u \leqslant 2$.

To summarize:

* IP:

Minimize $\sum\limits\_{v\in V}x\_vw\_v$.

s.t. $2x\_u + x\_v\geqslant 2$ for $(u, v)\in E$

and $x\_v \in \\{0,1,2\\}$ for $v\in V$
* LP relaxation:

Minimize $\sum\limits\_{v\in V}x\_vw\_v$.

s.t. $2x\_u + x\_v\geqslant 2$ for $(u, v)\in E$

and $0\leqslant x\_v \leqslant 2$ for $v\in V$

Now suppose you want to compute a solution (not necessarily optimal) to the IP system. Using the LP relaxation, a way to do it is the following:

* compute an optimal solution $X =\\{x\_v\mid v\in V\\}$ to the LP relaxation;
* consider $y\_v = \left\\{\begin{array}{ll}0 & \text{if }x\_v\< 0.5\\1&\text{if }0.5\leqslant x\_v\leqslant 1\\2&\text{otherwise} \end{array}\right.$
* then $Y = \\{y\_v \mid v\in V\\}$ is a solution (not necessarily optimal) to the IP system.

To show the last claim, we need to verify that the $y\_v$ still satisfy the conditions :

* $y\_v \in \\{0, 1,2\\}$ by definition;
* for $(u, v)\in E$, $2x\_u + x\_v \geqslant 2$. Let us distinguish:
    + if $x\_u \geqslant 0.5$, then $y\_u = 1$ and $2y\_u + y\_v \geqslant 2$;
    + otherwise, $x\_u \< 0.5$ and $x\_v \geqslant 2 - 2x\_u \> 2 - 1 = 1$, and $y\_v = 2$, so $2y\_u + y\_v \geqslant 2$.

Finally, we want to prove that this is a $2$-approximation. Assume $X^\* = \\{x\_v^\*\mid v\in V\\}$ is an optimal solution to the IP system. Since $X^\*$ is also a (non necessarily optimal) solution to the LP system, then: $$\sum\limits\_{v\in V} x\_vw\_v \leqslant \sum\limits\_{v\in V}x^\*\_vw\_v$$ But given the definition of $y\_v$, we have $y\_v\leqslant 2x\_v$. That means that: $$\sum\limits\_{v\in V} y\_vw\_v \leqslant 2\sum\limits\_{v\in V}x^\*\_vw\_v$$ We conclude that this is indeed a $2$-approximation.

To find the right formula for $y\_v$, it was a bit of a trial-and-error process:

* my first intuition was to try to round $x\_v$ to the nearest integer: $y\_v = \left\lceil x\_v - \frac12\right\rceil$. However, that did not guarantee that $2y\_u + y\_v\geqslant 2$ for $(u, v)\in E$ (for example, $x\_u = 0.4$ and $x\_v = 1.2$ satisfies $2x\_u + x\_v \geqslant 2$, but we would have $y\_u = 0$ and $y\_v = 1$);
* my second try was to round $x\_v$ up: $y\_v = \left\lceil x\_v\right\rceil$. While this would give a valid solution, it would not be a $2$-approximation;
* my third try was to consider $y\_v = \left\lceil x\_v - \frac13\right\rceil$. This would again provid a valid solution, and a better one that the previous, but this is only a $3$-approximation, not a $2$-approximation (proof left to you as an exercise).
> 0 votes

---
Tags: graphs, approximation, linear-programming, integer-programming
---


# Question
Title: 2NF decompositions are dependency preserving?
I have read that 1NF, 2NF and 3NF decompositions are lossless and dependency-preserving.

Consider this example on a relation $R(A,B,C,D)$ with functional dependencies set as $FD =${ $AB \rightarrow CD, A \rightarrow C, BC \rightarrow D$ }

Here when we do 2NF decomposition we get $R\_{1}(A,C)$ with $FD =${$A \rightarrow C$} and $R\_{2}(A,B,D)$ with $FD =${$AB \rightarrow D$}

The functional dependency $BC \rightarrow D$ is lost when we join but we know that 2NF is dependency preserving so why is it that we are unable to preserve the original FD?

# Answer
Although you decomposed the table using the dependency that violates 2NF $(A\rightarrow C)$, the new tables are in BCNF, and decomposition to BCNF is not always dependency preserving.
> -1 votes

---
Tags: database-theory
---


# Question
Title: How does caching, paging, virtual memory, and OS all tie together for UNIX copy-on-write?
In my OS course, the instructor mentioned the following: In UNIX if a parent process creates a new child ("fork") then the child is an exact duplicate of the parent. This means its memory space is a copy of the parent's.

Now if the child process immediately calls "exec", it replaces its own memory space with that of a new program. This means that time spent in copying the parent's memory space is wasted.

So, UNIX has a solution copy-on-write. That is when a child is created the pages of the parent are shared with the child, they are also marked "copy-on-write". So, as long as both are solely reading the page one memory space is shared between the two. But when either of them attempts to modify a page, a new copy is made for that page and page is modified.

So, given this explanation, I have a few questions. Most of them are concerned with the boundary where the software ends and the hardware starts.

1. When a new process is being created, there is a trap to the OS. And the OS does what it does to create a new process. Now, if the pages are marked "copy-on-write" then what happens to the pages of the parent process that were already in cache?

They are evicted, right?
2. What I particularly don't understand is if the child process tries to write to some page that is still being shared between the parent and child, how will the copy happen?

From the perspective of the CPU (hardware) that is executing the child process, it makes a write request. There are two cases here: either there was a cache miss, or a cache hit (the page was (at some time) during a read request loaded into the cache).

If it was a cache hit then wouldn't the hardware just write to that page in the cache disregarding the "copy-on-write" policy of the OS? How would the OS ensure that "copy-on-write" is respected here?

If it was a cache miss then the request goes to the page table and the page address is retrieved but the question remains the same.

Since UNIX is not designed for a specfic hardware, how would it ensure that "copy-on-write" is actually happening? Or is there some hardware support to perform something like this? I looked into cache locking but I don't think that can be used here.

Can someone please explain this?

Thank you!

# Answer
It seems like your understanding of the matter is pretty good. You are just missing one tiny trick: *Make the pages read-only*.

When the OS `fork`s the process, it maps the parent's pages also into the child, *AND sets the pages to read-only*. Before doing that, it also has to remember what the pages were set to before, for reasons we will see soon.

Now, since the pages are set read-only, every attempt to write to the page, from either the parent or the child, will raise an "illegal write" error exception which is trapped by the OS. The OS copies the page, sets both the old and the new page to be writeable, and everything works as we expect it to: pages that are never written are shared, pages that *are* written are copied lazily at the first attempt to write to them.

And if we immediately `exec` after the `fork`, then we completely re-map the child to a different address space and set the pages back to their original read/write status. Which means the only overhead we have for `fork` \+ `exec` is mapping the address space for the child twice and changing the accessibility of the pages to read-only and then back to the original. But we never copy anything, which is what we want to achieve.

There's some small wrinkles to it, but that is the gist of it.

One of the small wrinkles is that the page may not be intended to be writeable in the first place. That's why we have to remember what the status was before we made it read-only: if it is meant to be read-only and was read-only the whole time, we should of course *not* copy it and make it writeable, but instead treat this like we would treat any other illegal write, which usually means terminating the process with an error code.

Another small wrinkle is that we only looked at the special case of a parent and a single child. But, of course, a parent can `fork` multiple children, and each child again can `fork` multiple times, and so on. So, we need to do something a little more sophisticated here, namely, we need to keep a *reference counter* for each page, telling us how many processes are sharing this page right now. When we copy the page, we decrement the reference pointer of the old page by one and create the new page with a reference counter of one. Only pages with a reference counter of one can be writeable.

This gets again more complicated when we consider *shared pages*, i.e. pages that are *meant* to be written by more than one process.

The other small (and some of them maybe not so small) wrinkles are performance-related. For example, the question: at what point does it become more efficient to just copy the whole thing instead of trapping, copying a little bit, trapping again, copying a little bit, and so on and so forth.

But this is unrelated to the basic semantics of the operation. On the fundamental level, the basic trick is really just this: make the pages read-only and trap the illegal write error exception that will occur if either parent or child process tries to write to the page.
> 3 votes

---
Tags: computer-architecture, process-scheduling, paging, os-kernel, cache
---


# Question
Title: Meaning of "untyped bytes" in file systems
I am currently reading reading Chapter 11 of Operating Systems: Principles & Practice by Anderson and Dahlin, which speaks about file systems as abstractions for non-volatile storage.

The distinction between files and directories is first made. Afterwards, in examining what files are, a distinction between file data (i.e., contents of file) and file metadata (i.e., name of file, modification times, permissions, etc.,) is made. My confusion comes when they are speaking about file data. Here is a quote:

> A file’s data can be whatever information a user or application puts in it. From the point of view of the file system, a file’s data is just an array of ***untyped bytes***. Applications can use these bytes to store whatever information they want in whatever format they choose.

What do they mean by untyped bytes?

# Answer
> 2 votes
They mean that the data is an array of bytes, nothing more. It does not come with any type information to indicate how the data should be interpreted. It is up to applications to figure out how to interpret the data.

# Answer
> 1 votes
Bytes can be signed or unsigned, be considered numbers or characters, that's about the only typing information you can attach to them. The text means that the bytes are just eight bits, regardless any interpretation.

---
Tags: operating-systems, filesystems
---


# Question
Title: Is Fortune's algorithms for Voronoi diagrams described anywhere by Prof. Fortune?
One popular algorithm to find the Voronoi diagram out of a collection of points (*sites*) in the plane is Fortune's algorithm. It is usually described in terms of a *sweep line*, whose interaction with *sites* give raise to *parabolas*, whose intersections eventually provide the Voronoi diagram.

The Wikipedia page also includes a reference to Fortune's paper about the algorithm. (*The paper is provided online by some universities, but I'm not sure about the copyright status of those copies so I will not link them here.*)

Last, there is also an *implementation* of the algorithm described in the paper, made in C by Prof. Fortune. One page linking to the original is kept at the Internet Archive.

From what I saw (e.g. here from some years ago), the implementation is consistent with the paper, but *both* are very different from the popular description found around. As an example, the paper talks about hyperbolas, while the popular description deals with parabolas.

**Hence the question**: where can I find the original description by Prof. Fortune of what is widely regarded as Fortune's algorithm for Voronoi diagrams (the one with parabolas)?

**UPDATE** The accepted answer below makes the following citation:

> \[1\]: L. J. Guibas and J. Stolfi. Ruler, compass and computer: The design and analysis of geometric algorithms. In R. A. Earnshaw, editor, Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series F, vol. 40, pages 111–165. Springer-Verlag, 1988.

Prof. L. J. Guibas published some online material in CS268 Geometric Algorithms, available in the Lecture Notes page, including a PDF copy of a derived paper.

# Answer
> 1 votes
The "popular description" of Fortune's algorithm in terms of parabolas does not appear to be due to Fortune, but due to Guibas and Stolfi \[1\]. They start by analyzing the geometrical interpretation of Fortune's algorithm in section 5 of the original paper, and then deviate from the original paper by keeping track of the parabola front instead of working with the transformed Voronoi diagram.

So, to answer your question, given that the parabola interpretation in \[1\] only cites Fortune's paper, I believe the interpretation is original to Guibas and Stolfi. Therefore, the original description of the interpretation "with parabolas" is in \[1\], and such a description authored by Fortune does not exist. (or would not be original)

---

\[1\]: L. J. Guibas and J. Stolfi. *Ruler, compass and computer: The design and analysis of geometric algorithms.* In R. A. Earnshaw, editor, Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series F, vol. 40, pages 111–165. Springer-Verlag, 1988.

---
Tags: voronoi-diagrams
---


# Question
Title: Prove or disprove: f(n-1) is omega(f(n))
Prove or disprove: f(n-1) is omega(f(n)). I actually need a more specific example of this but I thought this claim was interesting. I want to know if (n-1)log(n-1) is omega(nlogn)

# Answer
> 0 votes
Hint: show $(n-1)! \neq \Omega(n!)$

---
Tags: complexity-theory
---


# Question
Title: Indices of Turing machine on different arity inputs
Let $\Sigma$ be an alphabet, and denote by $\mathrm{ind}(\varphi\_M^{(k)})$ the index set (w.r.t some numbering) of the $k$-ary partial computable function $\varphi\_M^{(k)} : (\Sigma^\*)^k \rightarrow \Sigma^\*$, which represents the $k$-ary proper function of the Turing machine $M$. Is it the case that $\mathrm{ind}(\varphi\_M^{(k)}) \subseteq \mathrm{ind}(\varphi\_M^{(k + 1)})$ for every $k \geq 1$? I think this is true simply because every $k$-ary input to $M$ is realizable as a $(k+1)$-ary input to $M$ but with one input word blank. However, to formally show the inclusion is evading me. I thought applying the $S^m\_n$ theorem would be helpful, but I think that merely establishes the inclusion for *some* Turing machine (not necessarily $M$). Any help would be appreciated.

# Answer
> 0 votes
You can define a machine implementing the computable function $(\Sigma^\*)^k \rightarrow (\Sigma^\*)^{k+1}$ for adding the blank to the set of inputs, then compose the machine implementing this function with your machine taking $k+1$ inputs to produce the required machine with $k$ inputs.

The $S^m\_n$ theorem can be used to construct the index for the composed machine.

I'm not sure if you mean whether same machine should be used to represent two functions with different arity? I think they would be different machines.

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