# Question
Title: Richard Karp's 21 NP-Hard problems, the meaning of his research?
In Richard Karp's paper "Reducability among combinatorial problems" he lists 21 NP-Hard problems. Though I can somewhat understand the ideas and motivation behind the paper I am searching for some clarity.

From what I know and understand this paper showed the parallels between the various problems. Specifically that they are all abstractly the same problem. That given a solution (specifically a P-time solution?) to one of these problems you could solve all of them because they are all statements of a more abstract problem.

Is this a proper summary of the work he presents? Is there a more eloquent and proper yet short way to say it?

Karp's paper: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf

# Answer
> 8 votes
The short way to say it is that these problems are $\mathcal{NP}$-complete.

Of course this only has meaning to those who understand what $\mathcal{NP}$-complete means.

Not only does this say these problems are all somehow equivalent (polynomial-time equivalent to be marginally more precise), but that you can use them to solve ***any*** problem in $\mathcal{NP}$, not just each other, with only a polynomial blow-up in the time cost. This immediately gives us that if any of them have a polynomial-time algorithm, then ***everything*** in $\mathcal{NP}$ does, and hence we would have $\mathcal{P} = \mathcal{NP}$ (summed up in Theorem 3 from the paper).

To see what Karp's paper in particular represents however, we have to pay attention to a touch of history (not all that usual for most computer scientists I know, but bear with me ;) ). This paper was published in 1972, it was only the year before that Cook proved that $\mathsf{Satisfiability}$ was $\mathcal{NP}$-complete, this was the first "natural" problem proven $\mathcal{NP}$-complete1, but Cook doesn't mention $\mathcal{NP}$, let alone $\mathcal{NP}$-completeness (and he used a weaker type of reduction than Karp, but that's another story). So what you see in Karp's paper is the first codification some of the ideas that have formed one of the central parts of complexity theory, not only does he get these ideas out into the literature, he also says "hey, there's a lot of problems that we're interested that are $\mathcal{NP}$-complete".

So in one go, he coherently defines $\mathcal{NP}$-completeness, shows what it means for solving problems efficiently2, and gives a bunch of (interesting) problems that are $\mathcal{NP}$-complete.

In some sense it is the founding document of complexity theory. It took a lot of ideas that were starting to gain currency, and put them together in a (relatively3) clear statement of how all this complexity stuff can work.

**Footnotes**

1. The definition of $\mathcal{NP}$ almost immediately gives complete problems - anything along the lines of "Does this non-deterministic Turing Machine halt in a polynomial number of steps?" or similar, but these are not the most interesting problems in the world (to most people).
2. Using Edmonds' idea of deterministic polynomial-time as a working definition of "efficient".
3. Though the reductions are fairly cursor and opaque by modern standards. On the other hand, he crams 21 in there.

# Answer
> 4 votes
To add some to the other already detailed answer: Cook's paper introduced the class of NP-complete problems but only gave a single "canonical" instance, SAT(isfiability). Karp showed in his paper in a "few strokes" that a wide variety of open problems that did not previously seem to be linked were in fact all NP-complete. So this later paper demonstrated somewhat dramatically it's more than merely an isolated or narrow theoretical curiosity; it's a basic classification in computer science, and hinted that many more (NP-complete problems) lay waiting to be identified, and that was exactly the case.

That view has only grown significantly in subsequent decades as NP-complete problems are found to be quite ubiquitous and cross virtually all scientific mathematical fields. There are now in the *hundreds* of NP-complete problems identified, possibly over a *thousand* (in a sense computer scientists have lost track somewhat, and at times it becomes difficult to discriminate "separate" problems from each other).

Nice modern surveys of this perspective can be found in e.g.:

Another related historical reference that came out in 1979 later and catalogued extended Karp's ideas to *dozens* of problems organized by category is:

# Answer
> 0 votes
Here is more research about the problems themselves:

The gist of it is that the problems are indeed all NP-Complete, but their individual complexity varies a lot. While any NP-Complete problem can be reduced to any other, creating actual reductions is difficult. **Satisfiability** happens to be much easier to work with than most other NP-Complete problems.

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


# Question
Title: Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?
Sources:

It can be seen that a Hash Table has no access/indexing complexity given the above sources. This doesn't make sense to me, since given a key, I can look it up in constant time by hashing it and iterating through the associated bucket (assuming the key space is less than the number of buckets, and on average). If this isn't the definition of an access/index, then how come a Binary Search Tree for example has $O(\log n)$ for access/indexing? It also doesn't do direct memory addressing and must also find the key outside that.

Also how can a Hash Table have $O(1)$ search complexity? If I'm looking to search for something, given that a Hash Table is unordered, I will on average have to search through $n/2$ nodes, giving $O(n)$ complexity. If this isn't the definition of search, then how come an array for example has $O(1)$ for access/indexing and $O(n)$ for search?

# Answer
> 2 votes
I think you have interchanged the idea of index and search.

Access/index here means given a position or index, like in an ordinary array or list, return the element in that index. This is why arrays support this operation in $O(1)$ time. Index or access is supported by BST because you can use them to implement sorted list. See order statistic tree for reference on how to do this. Hash table does not support index/access since the idea behind them is to "systematically scatter" elements in the structure to prevent/reduce collision, and with that, we do not expect to use such structures to maintain order of elements to support position based access.

Search on the other hand, means given an element, find it in the structure. So the $O(1)$ average search time for hashtables come from the way it searches - compute the hash of the element and perform some extra search in the bucket or probing. For arrays, with no assumptions about the elements, the only possible search is via linear search, thus the $O(n)$ running-time.

---
Tags: time-complexity, data-structures, big-o-notation
---


# Question
Title: Determining Big O of a for loop nested within a while loop
I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :)

Im a computer science student currently taking on Introduction to computer science, we recently learned about Big O and its formal definition. While looking at exercises, me and my friends had problem agreeing on the correct most **Precise** upper bound for this function

```
Pseudocode :
Function foo(L is list)
    n = length of L
    Do while n > 0
        n = n floor division over 2
        Do for i=0 upto i=n-1
            Something with complexity of O(1)
        End for
    End while
    return L

Python:
def foo(L:list):
    n = len(lst)
    while n>0:
         n = n//2
         for i in range(n):
             # some O(1) code
    return L

```

**My attempt:** So we know that the innermost loop in relative to n at Log(n) - 1 times, then we also know the outer while loop runs Log(n) times.

so that gives us O((Log(n))^2) time complexity

**My friend's attempt:**

The innermost loop is a simple for loop over n so that is of time complexity of O(n) and the outer most loop runs at Log(n) times which gives us O(nlog(n))

at this point I'm Completely lost , How does the inner loop give us O(n) if its loop times is determined by n which is reduced to half each time ? as in this is not a simple nested loop that loop over the same number of iterations A clarification is much much much appreciated

Happy weekend.

# Answer
> 2 votes
Both are wrong.

The inner loop makes $n$ iterations, for $n$ decreasing in a geometric progression. If the initial $N$ is an exact power of $2$, the total is

$$\frac N2+\frac N4+\frac N8+\cdots2+1=N-1.$$

---

* you confuse the *value* of $n$ and the *number of times* it is halved,
* they don't take into account the fast decrease of $n$.

# Answer
> 1 votes
You are both wrong, the correct asnwer is $O(n)$ (and is not very intuitive why).

To clarify, before I explain *why* this is $O(n)$ \- you are right that you friend's attempt is impercise because $n$ changes in the outer 'while' loop.

However, your answer is actually wrong for the exact same reason! You didn't carefully enough fogure how $n$ changes and how that affects the inner loop.

Now, to explain why the overall complexity is $O(n)$: in the first iteration of the outer loop, we "pay" $\dfrac{n}{2}$. In the next iteration, we "pay" $\dfrac{n}{4}$. In the next one, $\dfrac{n}{8}$, and so on.

So, the general formula for the run-time will be:

$$\frac{n}{2}+\frac{n}{4}+...+1\le n\cdot \left(1+\frac{1}{2}+...\right)=n\cdot 2=O(n)$$ Where the last equality is derived as the sum of a geometric series.

# Answer
> 0 votes
Your answer of $O((\log n)^2)$ is incorrect because the cost of each iteration is not $O(\log n)$; for example, the cost of the first iteration is proportional to $n/2$. Your friend’s answer $O(n \log n)$ is correct, but this upper bound is not asymptotically tight. It’s not wrong to say that the total cost is $O(n \log n)$, but $O(n)$ is a better upper bound, and this upper bound is asymptotically tight.

The amount of work done in the first iteration is $n/2$, in the second iteration is $n/4$, etc, and sothe total cost is $\frac{n}{2} + \frac{n}{4} + \cdots = \Theta(n)$.

---
Tags: time-complexity, big-o-notation, loops
---


title: Applying the Master's Theorem

text:
# Question
Title: Applying the Master's Theorem
Below is a problem I made up and my solution to it.

Problem:
Given the following recurrence relationship, find $\Theta(T(n))$. $$ T(n) = T\left( \dfrac{n}{2}\right) + n^2 $$

Answer:
To solve this problem, I use the Master's Theorem. I am using this link as reference:
Wikipedia Article
\begin{align\*} a &= 1 \\ b &= 2 \\ c\_{crit} &= \log\_2 1 = 0 \\ \end{align\*} This means we are in case 3. Hence the answer is: $$ T(n) = \Theta(n^2) $$

I am concerned my answer is wrong because we have: $$ T(n^2) = n^2 + (\dfrac{n}{2})^2 + (\dfrac{n}{4})^4 + ... 1 $$ Here we have $O(\log n)$ terms. Hence, I was thinking the answer might be: $$T(n) = \Theta ( \log(n) n^2 ) $$ I do believe that: $$T(n) = O( \log(n) n^2 ) $$ That is $\log(n) n^2$ represents an upper bound on $T(n)$.

# Answer
> 1 votes
$$\begin{align} T(n) &=& n^2 + \left(\frac{n}2\right)^2 + \left(\frac{n}4\right)^2 + … \\ & = & n^2 \left(1+\frac14 + \frac1{16} + …\right)\\,\\,\\,\\,\\ &\leqslant& n^2\sum\limits\_{k=0}^{+\infty}\frac1{4^k} =\frac{4n^2}{3}\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\, \end{align}$$

There is no problem here: even if there are $\mathcal{O}(\log n)$ terms, those terms are smaller and smaller.

# Answer
> 0 votes
You are right that there are on the order of $\log n$ terms in the sum and that each term is $n^2$ times a constant; however, the upper bound $O(n \log n)$ thus obtained, while correct, is not asymptotically tight because the coefficients decrease at a geometric rate and sum to at most some fixed constant $c$. More specifically, the coefficients are $1, 1/4, (1/4)^2$, etc, and the sum of these constants is at most $2$. So, the total cost might be more than $n^2$, but the total cost is still at most $2n^2$, and the constant $2$ is subsumed in asymptotical notation.

More generally, if the common ratio $0 \< r \< 1$ in a geometric progression is less than $1$, then $1+r+r^2+\cdots+r^{\log\_2 n} = \Theta(1)$. This is why, in this case of the Master theorem, the total cost of all levels of the recursion tree is dominated by the top level of the recursion tree, i.e. the constant $1$ In the sum $1+r+r^2+\cdots+r^{\log\_2 n}$ dominates the sum (by up to a constant factor).

---
Tags: time-complexity
---


# Question
Title: Is there a simpler solution for this recuurence?
Consider this recurrence relation, $$T(n)=T(n-\sqrt{n})+1$$ I try to show that $T(n)=O(\sqrt{n})$.

Also, I read this link, but my question is, can I claim that, at each step $n$ decreased by at least $\sqrt{\frac{n}{2}}$ to reach $\frac{n}{2}$?

# Answer
> 3 votes
I'm assuming that the base case is $T(n)=1$ for $n\le 1$. If you accept the fact that $T(\cdot)$ is an increasing function, you can show by induction on $m \ge 1$ that $T(m^2) \< 2m$.

If $m \le 1$ then the claim is trivially true. Assume now that the claim holds for $m \ge 1$. You have: $$ \begin{align\*} T((m+1)^2) &\le T((m+1)^2 - (m+1)) + 1 = T(m^2 + 2m +1 - m-1) +1 \\ &= T(m^2 + m) + 1 = T(m^2 + m -\sqrt{m^2+m})+2\\ &\le T(m^2)+2 \< 2m+2=2(m+1). \end{align\*} $$

Then $T(n) = O(\sqrt{n})$ follows by choosing $m = \lceil \sqrt{n} \rceil$ since $T(n) \le T(m^2) \< 2(m+1) \< 2(\sqrt{n} +2) = O(\sqrt{n})$.

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


# Question
Title: Recursive algorithm for adding numbers from 1 to n with O(1) time complexity
So I have a recursive algorithm which sums up the numbers from 1 to n **plus one** (hence the return 1):

```
public static int S(int n) {
    if(n < 0) {
        return 1;
    }
    else {
        return n + S(n-1);
    }
}

```

This algorithm has a time complexity of O(n).

Is it possible to derive an algorithm which produces the same output as the one shown above but with a constant time complexity of O(1)?

# Answer
> 0 votes
The sum $1+2+3+\cdots+n$ is equal to $n(n+1)/2$; hence, the following function would return the same output:

```
Function S(n):
    if n < 0, then return 1
    Else return n(n+1)/2 + 1

```

It takes time $O(1)$, but does not make recursive function calls. Generally, a recursive function would take linear time, unless you are willing to consider contrived versions like the code shown below, where the depth of recursion is bounded by a constant:

```
Function S(n):
    If n is even, then return 1+n(n+1)/2
    Else return n + S(n-1)

```

# Answer
> 1 votes
Yes. The method was invented by Carl Friedrich Gauss, aged 6. It’s simple. Add the first and the last number. Add the second and the second-to-last number. Then the third and third to last. And so on. Find the pattern.

# Answer
> 1 votes
Any algorithm that has $O(1)$ complexity must be extremely simple.

In your case, there is just a known closed form for this summation, so your program can return it within $O(1)$ (well technically this is assuming that addition, multiplication and division can be done in constant time)

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


# Question
Title: Matching problem in bipartite network with more than one edge per vertex
I'm interested to know if there is an algorithm to find possible solutions for the matching problem, in a bipartite network where each vertex have maximum number of connections greater than one. For reference the original matching problem only requires that each vertex only have one edge.

More specifically, imagine that i have two groups of individuals $X = \\{a,b,c,d\\}$ and $ Y= \\{e,f,g,h\\}$. I want to generate random solutions such that every element of $X$ is connected to at least 1 of $Y$ but to no more than 3, and that every element of $Y$ is also connected to either 1,2 or 3 elements in $X$.

Any ideas how to implement that, or, if there is a specific name for this kind of problem? That makes it more likely to find a function in R that solves it.

# Answer
> 0 votes
With only two groups of 4 individuals, there are at most $2^{4 \times 4} = 65536$ different candidate solutions, so it is trivial to enumerate all possible solutions and check each one to see whether it meets your conditions.

# Answer
> 1 votes
When you generate random instances, you need to consider if you have a specific probability distribution in mind. You could suppose that the degree of each vertex is chosen uniformly at random from $\\{1,2,3\\}$.

If $a\_1,a\_2\ldots,a\_n$ and $b\_1,b\_2,\ldots,b\_n$ are the left and right vertices of the bipartite graph, then choose each $a\_i$ and $b\_j$ at random from $\\{1,2,3\\}$. The degree sequence $(a,b)$ is realizable (i.e. there exists a bipartite graph having $(a,b)$ as its degree sequence) if the Gale-Ryser theorem is satisfied, which you can check. This theorem would not be satisfied for all random instances, but it does give a condition that is both necessary and sufficient for a degree sequence to be realizable. Then, you can generate a bipartite graph with this degree sequence; see Exercise 1.4.32 of \[D. West, Introduction to Graph Theory, 2e\]. An issue is perhaps most degree sequences might not be realizable.

See also the Wikipedia articles on bipartite graph realization and on the Gale-Ryser theorem.

---
Tags: graphs, matching, bipartite-matching
---


# Question
Title: Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says the time complexity will be $\Theta(n^2)$, but I don't understand why it's not $\Theta(n^2\log n)$? I tried using a recurrence tree, and since it looks similar to the one for a linear merge method, just with $T(n)=2T(n/2)+\Theta(n^2)$ instead of $T(n)=2T(n/2)+n$. So why does it not give a similar solution? I understand that the master theorem can be used to prove this, but I don't understand why the approach used when finding a runtime for merge sort with linear merge doesn't work here.

# Answer
> 1 votes
Because the work done is $$ T(n) = 2T(n/2) + n^2 \leq \sum\_{i=0}^{\log\_2 n} 2^i \left(\frac{n}{2^i}\right)^2 = n^2 \sum\_{i=0}^{\log\_2 n} \frac{2^i}{2^{2i}} = O(n^2). $$

Try for yourself to see what happens when you remove the factor squared in the summation.

# Answer
> 1 votes
In the recursion tree, the cost of the top level (i.e. level 0) is $n^2$. There are two nodes in level $1$, each having a cost of $(n/2)^2$; hence, the total cost of level $1$ is $n^2/2$. In level $2$, there are $4$ nodes, each with a cost of $(n/4)^2$; hence, the total cost of level $2$ is $n^2/4$. Thus, each level has a cost $n^2$ times a coefficient, but these coefficients decrease geometrically, i.e. the coefficients are $1, 1/2, 1/4, 1/8$, etc. Hence, the total cost of all levels is $n^2 (1+1/2 + 1/4 + \cdots) \le 2n^2$, and hence the total cost is $\Theta(n^2)$.

Thus, even though the formula for the total cost has on the order of $\log n$ terms and each term is of the form $n^2$ times a coefficient, the sum of these coefficients is bounded from above by a constant. Recall that constants are subsumed in asymptotic notation.

More generally, when the common ratio $r$ is less than $1$, we have that $1+r+r^2 + \cdots + r^{\log\_2 n} = \Theta(1)$, i.e. the first term $1$ dominates the sum. This is why, in this case of the Master theorem, the total cost $n^2 (1+r+r^2+\cdots+r^{\log\_2 n})$ is dominated by the first term; equivalently, the total cost of all levels of the recursion tree is dominated by the top level.

# Answer
> 0 votes
Assume $n=16$.

Standard MergeSort involves the cost $16+2\cdot8+4\cdot4+8\cdot2$. If we divide by $n$, $1+1+1+1$.

"Quadratic" MergeSort involves $256+2\cdot64+4\cdot16+8\cdot4$. If we divide by $n^2$, $1+\dfrac12+\dfrac14+\dfrac18$.

Do you see the patterns ?

---
Tags: asymptotics, runtime-analysis, recurrence-relation, big-o-notation, master-theorem
---


# Question
Title: Understanding time complexity of algorithm to determine if parenthesis are matching
Both these algorithms determine if all the parenthesis in a string are balanced and properly nested.

The first algorithm uses "a constant amount of memory, regardless of the length of the string."

The second algorithm "may use O(n) memory but must use a stack".

I understand how the algorithms work but I don't understand the descriptions of time complexity.

My understanding is that they are both O(n) because they both use a single for loop and the length of time it will take to execute them depends on the size of the string.

Also on algorithm 2 I believe the last bit should be if t!=0 instead of ==?

Any help understanding these descriptions of time complexity would be greatly appreciated. Thanks.

# Answer
> 0 votes
Two algorithms can have the same (asymptotic) time complexity but differ in their space complexity. The amount of extra storage space consumed by the algorithm is another performance measure of the algorithm.

Both your algorithms have the same asymptotic running time $O(n)$, but they differ in their memory usage. The first algorithm uses only $O(1)$ auxiliary storage space (for example, the variable count is used). On the other hand, the second algorithm takes $O(n)$ extra storage, because in the worst-case, the input would be of the form $(^{n/2} )^{n/2}$, i.e. $n/2$ opening parantheses followed by $n/2$ closing parantheses, and the algorithm would have to store $n/2 = O(n)$ bytes on the stack.

Yes, the == should be !=.

---
Tags: algorithms, time-complexity, algorithm-analysis, big-o-notation
---


# Question
Title: How are a graph and a binary tree represented as data structures in CLRS' Introduction to Algorithms?
In CLRS' Introduction to Algorithms:

(1) In 22.1 Representations of graphs

> The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V. For each u in V , the adjacency list Adj\[u\] contains all the vertices v such that there is an edge (u,v) in E. That is, Adj\[u\] consists of all the vertices adjacent to u in G. (Alternatively, it may contain pointers to these vertices.) Since the adjacency lists represent the edges of a graph, in pseudocode we treat the array Adj as an attribute of the graph, just as we treat the edge set E. In pseudocode, therefore, we will see notation such G.Adj\[u\].

Does G.Adj being an array means that the vertices being its indices must be natural numbers 1, 2, ...?

(2) In 22.3 Depth-first search

> ```
> DFS(G)
> 1 for each vertex u in G.V
> 2   u.color = WHITE
> 3   u.pi = NIL
> 4 time = 0
> 5 for each vertex u in G.V
> 6   if u.color == WHITE
> 7     DFS-VISIT(G,u)
>
> DFS-VISIT(G,u)
> 1 time = time + 1 // white vertex u has just been discovered
> 2 u.d = time
> 3 u.color = GRAY
> 4 for each v in G.Adj[u] // explore edge (u,v)
> 5   if v.color == WHITE
> 6     v. = u
> 7     DFS-VISIT(G,v)
> 8 u.color = BLACK // blacken u; it is finished
> 9 time = time + 1
> 10 u.f = time
>
> ```

Is G.V an array that stores the vertices of G?

u is an element in G.V, and is used as an index to access an element in array G.Adj. Does u having attribute color, pi, d and f means that u is an object?

So is u a natural number or an object?

Which is better in representing a vertex, as a natural number or an object?

Which is better,

* representing vertices as objects with names and stored independently, and referring to each vertex object by its name, or
* representing vertices as objects stored together as elements in an array, and referring to vertex objects as elements of the array?

(3) In 10.4 Representing rooted trees:

> In this section, we look specifically at the problem of representing rooted trees by linked data structures. We first look at binary trees, and then we present a method for rooted trees in which nodes can have an arbitrary number of children.
>
> We represent each node of a tree by an object. As with linked lists, we assume that **each node contains a key attribute**. The remaining attributes of interest are pointers to other nodes, and they vary according to the type of tree.
>
> **Binary trees**
>
> Figure 10.9 shows how we use the attributes p, left, and right to store pointers to the parent, left child, and right child of each node in a binary tree T. If x.p = NIL, then x is the root. If node x has no left child, then x.left = NIL, and similarly for the right child. The root of the entire tree T is pointed to by the attribute T.root. If T.root = NIL, then the tree is empty.

So a binary tree is represented as an object T, and a node of the binary tree as an object T.x in the pseudolanguage.

How different are object T for a binary tree and object G for a graph?

Does T have an attribute T.V for storing the representations of its nodes? Similar to G.V for a graph?

Are the representations of the nodes of a binary tree stored in an array?

Thanks.

---

p.s. the pseudolanguage used in the book is described in 2.1 Insertion sort:

> We access array elements by specifying the array name followed by the index in square brackets. For example, A\[i\] indicates the ith element of the array A. The notation ".." is used to indicate a range of values within an array. Thus, A\[1 .. j\] indicates the subarray of A consisting of the j elements A\[1\], A\[2\], ..., A\[j\].
>
> We typically organize compound data into objects, which are composed of attributes. We access a particular attribute using the syntax found in many object-oriented programming languages: the object name, followed by a dot, followed by the attribute name. For example, we treat an array as an object with the attribute length indicating how many elements it contains. To specify the number of elements in an array A, we write A.length.
>
> We treat a variable representing an array or object as a pointer to the data representing the array or object. For all attributes f of an object x, setting y = x causes y.f to equal x.f . Moreover, if we now set x.f = 3, then afterward not only does x.f equal 3, but y.f equals 3 as well. In other words, x and y point to the same object after the assignment y = x.
>
> Our attribute notation can cascade. For example, suppose that the attribute f is itself a pointer to some type of object that has an attribute g. Then the notation x.f.g is implicitly parenthesized as (x.f).g. In other words, if we had assigned y = x.f , then x.f.g is the same as y.g.
>
> Sometimes, a pointer will refer to no object at all. In this case, we give it the special value NIL.

# Answer
> 1 votes
```
Does G.Adj being an array means that the vertices being its indices must be natural numbers 1, 2, ...?

```

Either a natural number or an object that can be mapped to natural number between $1$ and $n$. You don't need this fine grained distinction to discuss the pseudocode of the algorithm since you can go form one to another (e.g., by storing an integer ID of each node in the node object, and by keeping an array that maps IDs back to objects).

```
Is G.V an array that stores the vertices of G?

Does u having attribute color, pi, d and f means that u is an object?

So is u a natural number or an object?

Which is better?

```

`G.V` can be an array that stores the vertices, our you could simply iterate over all vertices IDs of the graph (i.e., `for i=1,...,n:`).

Again, `u` could be an object with `color`, `pi`, etc as fields or these information can be maintained as satellite data somewhere else, for example, with parallel arrays indexed with the vertex ID. The important bit is that, given a vertex `u`, you can access its satellite information.

There is no absolute "better" solution. It probably depends to your specific case.

```
Does T have an attribute T.V for storing the representations of its nodes? Similar to G.V for a graph?

```

It could, but it doesn't have to.

```
Are the representations of the nodes of a binary tree stored in an array?

```

Again, they could but they don't have to. You could allocate an instance of each node object independently in the heap and refer to nodes with pointers. This is what the quoted part of the book appears to be describing.

Alternatively, you could allocate all nodes in the tree contiguously into a single array. You can still use pointers to refer to other nodes, or you could replace pointers with the index in this backing array (a pointer and the index are essentially the same thing in this case).

# Answer
> 0 votes
Figure 22.1 in the CLRS textbook seems to imply that the adjacency list of a graph is stored as follows: the nodes are labelled $0,1,\ldots,n-1$, there is an array of $n$ pointers, and each pointer points to a linked list of all neighbors of the corresponding node.

For example, one can create an array of $n$ pointers and initialize them to NIL. Each time a new edge $ji$ is added (to the initially empty graph), element $i$ is added to the $j$th linked list and $j$ is added to the $i$th linked list (in the case of undirected graphs).

You could take the approach of creating an object for each vertex or edge, as you suggest. This is done in \[Guttag, “Introduction to Computation and Programming Using Python, 2nd Edition”, Section 12.2\].

Or, you could create a list of lists in Python, of the form $\[Adj\[0\], Adj\[1\],…,Adj\[n-1\]\]$, where $Adj\[1\] = \[2,3,7\]$ would mean vertices $2,3,7$ are neighbors of $1$. The for loops would just iterate over this list, as desired. You could use an array d, where d\[i\] is the distance to node i, i.e. the d-value of node i.

Another implementation for graphs - this one is in C - can be found in \[Steven Skiena, “The Algorithm Design manual”, Section 5.5\].

For binary search trees, the tree is completely determined once you know the pointer variable T, which points to the root node of the tree. By following the left child or right child pointers of each node, one can reach any node in the entire tree.

Another good reference is \[Aho, Hopcroft and Ullman, “Data Structures and Algorithms”\]. Their section on linked lists is a good starting point if you want to understand pointers. They also explain how binary trees can be implemented with arrays (and apply this to Huffman codes).

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


# Question
Title: What is the big-O of the function 2 log(log n) + 3 n log(n) + 5 log(n)?
What is the big-O of the function $2\log(\log(n)) + 3n\log(n) + 5\log(n)$?
Is it just $O(n\log(n))$ for the whole function? I'm not sure how to represent $2\log(\log(n))$.

# Answer
Starting with an analytical assessment of the function's terms, we'll first format all terms as similarly as possible to each other, in order to more easily compare with one another. To do so, all constant factors will be removed, leaving only the variable elements of each term. This is acceptable to do since we're ultimately seeking Big-$O$ classification, which typically sets all constants within its expression to a value of $1$.

* $2\log(\log(n)) \to \log(\log(n))$
* $3n\log(n) \to n\log(n)$
* $5\log(n) \to \log(n)$

Rewriting,

$\quad f(n) \to \log(\log(n)) + n\log(n) + \log(n)$,

where $n \in \mathbb{N}.$

Now, since each term varies only by their logarithmic arguments, we can establish an inequality by direct comparison of those arguments, resulting in

$\quad \log(\log(n)) \lt \log(n) \lt n \log(n),\ \forall n \gt 1$

Therefore, it follows that

$\quad f(n) \in O(n\log(n))$
> 3 votes

# Answer
Please note that "the big-O of the function" isn't a correct formulation. We assume $\log$ is the binary logarithm $\log\_2$. But actually the proof can be extended to any base.

---

We have

$$\log(x)\lt x, \forall x\>0$$ and, if we plug in $\log(n)$ for $x$ $$\log(\log(n))\lt \log(n).\tag 1$$

Recall the definition of $f(n)=O(g(n))$: $$|f(n)|\le M |g(n)|,\forall n\ge n\_0$$ for appropriate $M$ and $n\_0$.

So if we choose $f(n)=\log(\log(n))$, $g(n)=\log(n)$, $M=1$ ,$n\_0=2$

we see that $(1)$ is $$\log(\log(n))=O(\log(n))$$ and of course $$\log(\log(n))=O(n\log(n)).$$ So all three function in your expressions are $O(n\log(n))$ and therefore every linear combination of them $$a\log(\log(n)) + b \\, n\log(n) + c\log(n), \quad a,b,c \in \mathrm R$$ is $O(n\log(n))$.
> 2 votes

# Answer
The best way to find big-o of a function like this:

$$f(n) = \sum\_{i=1}^k f\_i(n)$$

is to find an i where:

$$\forall j \in \[1,k\], j\neq i \rightarrow \lim\_{n-\>\infty} \frac{f\_j(n)}{f\_i(n)} =0$$

therefor big-o is $$n\log(n)$$
> 0 votes

# Answer
It is obvious that $\log n\le an$ for some constant $a$ because the number of digits of $n$ cannot exceed $n$. Then substituting $n$ for $\log n$, $\log\log n\le a\log n$. (For the base-2 logarithm, $a=1$ works.)

Combining, we have

$$2\log\log n+3n\log n+5\log n\le (2a+3n+5)\log n\le cn\log n$$ because for $n\ge1$ and $c=2a+5+3$,

$$\frac{2a+5}n+3\le c.$$
> 0 votes

# Answer
Yes, the expression is $O(n \log n)$. For large $n$, $n \log n$ dominates $\log n$ and $\log \log n$.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Repeated vertices in cycles (graph theory)
In graph theory, can a cycle contain repeated nodes/vertices not including the first and last ones? If so, can you please give an example?

# Answer
> 1 votes
Usually cycles are assumed not to have any repeating vertices (other than the first and last vertices being identical). If repeating vertices are allowed, then one talks about *closed walks*. In order to stress that cycles have no repeating vertices, we call them *simple cycles*.

That said, terminology isn't always fixed. If in doubt, define the terms you use.

# Answer
> 1 votes
A cycle does not contain repeated vertices (and does not have a starting vertex).

In contrast, a *closed walk* starts at a vertex, has a sequence of vertices and edges (with repetitions allowed), and ends at the starting point. A *closed trail* starts at a vertex, has a sequence of vertices and edges (with edges distinct, but vertices may be repeated), and ends at the starting point. A *cycle* is a closed walk (of length at least 3) that does not repeat vertices and that has no starting vertex and no direction.

These are standard definitions; see \[Bollobas, “Modern Graph Theory”, GTM 184, p. 4-5\].

---
Tags: graphs
---


# Question
Title: Why we can't use deduction theorem on soundness to contravene second incompleteness with lob's theorem
I'm starting to learn modal logic and there is something that's bothering my mind for a while.
we know from deduction theorem that $((\vdash q) \rightarrow (\vdash p)) \Leftrightarrow(\vdash (q \rightarrow p))$
and also from soundness we know that $\vdash\Box q \rightarrow \vdash q$
so here's my problem, why can't we deduce that $\vdash \Box q\rightarrow q$ if we do that with lob's theorem ($\vdash(\Box q \rightarrow q) \leftrightarrow \vdash q$) we can contravene second incompleteness so it is a wrong thing to do but why ? don't we proof all these sentences in meta so what's the difference ?

# Answer
> We know from deduction theorem that $(\vdash q\rightarrow\vdash p)\iff (\vdash p\rightarrow q)$

This is **false**. If $\not\vdash q$ then the clause $(\vdash q)\rightarrow(\vdash p)$ (re-parenthesized for clarity) is vacuously true, regardless of what $p$ is. So just take $q$ to be some independent sentence and set $p=\neg q$; we trivially have $\not\vdash p\rightarrow q$ but $(\vdash q)\rightarrow(\vdash p)$, a counterexample to your claim.

---

The issue is with your interpretation of the deduction theorem. The deduction theorem says $$\\{p\\}\vdash q\quad\iff\quad\vdash p\rightarrow q,$$ or more generally $$T\cup\\{p\\}\vdash q\quad\iff\quad T\vdash p\rightarrow q,$$ but that's very different from what you've written. In particular, the deduction theorem manipulates **individual sequents** (turning "$\\{p\\}\vdash q$" into "$\vdash p\rightarrow q$" or similar) rather than hypothetical comparisons of different sequents (such as your "$(\vdash q)\rightarrow(\vdash p)$").
> 2 votes

---
Tags: logic, first-order-logic, modal-logic, incompleteness
---


# Question
Title: Prove/find context free grammar is unambiguous for the language $L$
I am trying to find a grammar and prove that it is unambiguous for the language $L$, where $$L = \\{ w \in \\{a,b\\}^+; |w|\_a = |w|\_b \\} $$ Essentially: word $w$ contains at least one $a$ and $b$; where the number of $a$ is equal to the number of $b$.

**What I tried:** I am currently working with a grammar that has the following rules: (updated based on Tonita's suggestion) $$\begin{align} S &\to AS \mid BS \mid A \mid B\\ A &\to aXb\\ B &\to bYa \\ X &\to AX \mid \varepsilon\\ Y &\to BY \mid \varepsilon \end{align}$$ I believe that this CFG does indeed produce all words of the language $L$; since it won't produce an empty word, will always produce a word containing an equal amount of a's and b's, and covers all of their possible permutations. Now I wanted to ask how would I go on proving that this grammar is **unambiguous**; or whether my grammar satisfies the provided language at all!

Currently, I am trying to work out a way to prove that all the words can only have exactly one derivation tree, pretty lost here, would appreciate any concepts/hints/solutions/advice.

# Answer
Your updated grammar is SLR(1) which can be seen there, thus unambiguous, but constructing SLR-parsing tables is not an elegant way to prove things. If you use the following grammar form (which is almost equivalent to yours but distinguishes the first derivation to produce non-empty words), then the proof is much simpler: this grammar is LL(1), and it is not hard to construct the parsing table.

$$ \begin{array}{l} S \rightarrow A S\_1\\;|\\;B S\_1\\ S\_1 \rightarrow A S\_1\\;|\\;B S\_1\\;|\\;\varepsilon\\ A \rightarrow a X b \\ X \rightarrow A X\\;|\\;\varepsilon\\ B \rightarrow b Y a \\ Y \rightarrow B Y\\;|\\;\varepsilon \end{array} $$ The LL(1)-property guarantees that your grammar is unambiguous as well. Still, this method is again rather technical than elegant and involves the grammar change.

But you can notice that the nonterminals $X$ and $Y$ produce languages of balanced brackets if we use the mappings $a\rightarrow ($, $b\rightarrow )$ (for $X$) and $a\rightarrow )$, $b\rightarrow ($ (for $Y$). This leads to a reasoning that I like the most.

First, we can easily prove that no prefix of $(w)$, where $w$ is a balanced bracket sequence, is a balanced bracket sequence. Do it yourself.

Then it is easy to see that the rule $S\rightarrow A$ can be applied only to words having structure $a w b$, where $w$ is balanced w.r.t. $(a,b)$; but these words cannot be parsed by rule $S\rightarrow A S$, because that forces a balanced-bracket-prefix to exist. Thus, there is the only possibility to split the word to the part parsed by $A$ and the remainder parsed by $S$: since the prefix of the form $a w' b$ (where $w'$ is balanced w.r.t. $(a,b)$) is unique.

The same reasoning works for parsing the $(b,a)$-balanced parts.

Hope that helps!
> 3 votes

---
Tags: formal-languages, automata, context-free, ambiguity, chomsky-hierarchy
---


title: What is a de Bruijn sequence exactly?

text:
# Question
Title: What is a de Bruijn sequence exactly?
I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess).

There are two good resources I am looking at for better understanding (it seems like they have a good model of them):

Looking first at the website, they say that $k$ is the number of symbols in the alphabet (so for binary it's 2), and $n$ is the length of each substring in an overall string (I don't know what the string is labeled as, maybe "DB sequence" I guess, de Bruijn sequence, of substrings). They show this as a $k = 2, n = 4$ system:

```
0000 0001 0010 0101 1011 0110 1101 1010
0100 1001 0011 0111 1111 1110 1100 1000

```

So I see, $n = 4$ (length of substring), and $k = 2$ ($1$ and $0$).

However, then I get lost at the sentence:

> `0000101101001111` is a DB sequence where the 16 unique substrings of length 4 visited in order are:

I get there are 16 unique substrings, but where does `0000101101001111` come from? Breaking it into 4, it is:

```
0000
1011
0100
1111

```

That's the 1, 5, 9, 13 elements of that sequence. Why did they just use that to describe this DB sequence?

Then in the linked paper, they show:

They say each of these lines is a DB sequence with $k = 2$ and $n = 6$. So from all that I conclude that the substring is length 6 in this case. So I break down the first line:

```
000000
100001
100010
100011
100100
101100
110100
111101
010111
011011
1111

```

It doesn't even break into equal length substrings all of length $6$, what am I missing? I thought this should be substrings of length 6 which cover all possibilities of the substring combinations...

So going back to wikipedia, they have some examples, let's see.

> Taking A = {0, 1}, there are two distinct B(2, 3): 00010111 and 11101000, one being the reverse or negation of the other.

where $B(k, n)$. Breaking the first down into 3 chunks, we have:

```
000 101 11

```

Also not chunks of 3. What am I misinterpreting?

# Answer
> 2 votes
A deBruijn sequence $B(k,n)$ has length $N=k^n$ and is *cyclic* i.e. it can be extended by repeating the sequence.

If it is $x\_0,\ldots,x\_{N-1}$ then the subsequences $$ x\_0\cdots x\_{k-1}\\ x\_1 \cdots x\_{k}\\ ~\\ \vdots\\ ~\\ x\_{N-1} \cdots x\_{N+k-1} $$ are all distinct and thus cover each $n-$tuple over an alphabet of size $k.$

---
Tags: algorithms, combinatorics, discrete-mathematics
---


# Question
Title: If you can reduce A to B, does that mean B reduces to A?
If you can reduce A to B, does that mean B reduces to A?

Sorry for the stupid question. I think the answer should be yes, because if you can convert all yes-instances of A to yes-instances of B, then you basically just have to do the opposite to reduce yes-instances of B to yes-instances of A.

# Answer
> 1 votes
> basically just have to do the opposite

**Not all functions are surjective!**

It souds like you're thinking about some variant of *many-one reducibility*, where $A\subseteq\mathbb{N}$ is reducible to $B\subseteq\mathbb{N}$ iff there is some "simple" (for now let's say that this means *polynomial-time computable*) function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that for all $x$ we have $$x\in A\iff f(x)\in B.$$ But what if this $f$ isn't surjective? For example, suppose $A=\mathbb{N}$ and $B$ contains the set of even numbers. Then $x\mapsto 2x$ reduces $A$ to $B$, but how can I figure out whether $3\in B$ just by thinking about $A$? Since $3\not\in ran(f)$, the fact that $f$ lets us convert $A$-questions to $B$-questions doesn't help us here - **we can't always go backwards**.

---
Tags: reductions, polynomial-time-reductions
---


title: How are interrupts handled?

text:
# Question
Title: How are interrupts handled?
Andrew S. Tanenbaum, in his book *Modern Operating Systems*, states that

> Once the CPU has decided to take the interrupt, the program counter and PSW are typically then pushed onto the current stack and the CPU switched into kernel mode.

> Once the interrupt handler (part of the driver for the interrupting device) has started, it removes the stacked program counter and PSW and saves them, then queries the device to learn its status.

I am not able to understand, why the CPU first stores the registers in the stack and then later the interrupt handler saves them in the Process Table. Wouldn't it be better if it could directly save the current registers in the Process Table without pushing them into the stack?

# Answer
This is a matter of abstraction. Details like the process table or where this data is saved are a matter of the design of the operating system. Different operating systems may store this information in a different place, and may have a different mechanism for keeping track of where to save it. Some OS's might not even have a process table at all. So, it doesn't make sense to try to hardcode this into the CPU.

In general, there is a separation of responsibilities between the CPU and the operating system. It wouldn't make sense to try to take everything that is currently done by the operating system and hardcode it into the CPU, because that would limit the flexibility of the OS, and would make the CPU more complex for little gain.
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Proving 2SAT is in P vs algorithm for finding a satisfying assignment
I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path search?

Furthermore, is the proof for the corollary correct? The algorithm is presented there without proof.

# Answer
> 1 votes
You don't need the corollary in order to show that 2SAT is in P. Rather, it uses the same techniques to give a fast algorithm for finding a satisfying assignment for satisfiable 2CNFs.

If you're not sure whether the algorithm actually works, try proving it.

---
Tags: algorithms, complexity-theory, satisfiability, polynomial-time, p-vs-np
---


# Question
Title: How do data registers work in assembly programming?
I'm learning assembly programming and I can't seem to get my head around the register usage, as I'm using **emu8086** which emulates old 8086 processors. According to 8086 (16-bit architecture) the four General Purpose Registers are:

My confusion is: why does using **DL** and **DH** give different results, as they both are the lower and higher byte registers of **DX** which is a 16-bit register?

**Code 1:**

```
.model small
.stack 100h
.data
.code
main proc
    mov dl, 'A'
    mov ah, 2
    int 21h

    mov dl, 10    ;for next line feed, using lower byte data register
    mov ah, 2
    int 21h

    mov dl, 'B'
    mov ah, 2
    int 21h

endp
end main

```

**OUTPUT**

```
A
 B

```

**Code 1:**

```
.model small
.stack 100h
.data
.code
main proc
    mov dl, 'A'
    mov ah, 2
    int 21h

    mov dh, 10    ;for next line feed, using higher byte data register
    mov ah, 2
    int 21h

    mov dl, 'B'
    mov ah, 2
    int 21h

endp
end main

```

**OUTPUT:**

```
AAB

```

# Answer
DL and DH are two different registers and they are used for different tasks. In particular, the interrupt you are using, int21 service02, prints to the screen the content of register DL (and ignores DH). See http://spike.scu.edu.au/~barry/interrupts.html#ah02

In your second code fragment, you put 'A' in DL and execute int21, which prints 'A' to the screen. Then you change DH (but not DL! DL='A' still) and execute int21, which, again, prints 'A'.

Note that if you were performing 'MOV DX, 10' this would have changed both DH and DL, and caused the same effect as 'MOV DL,10", in this case. But changing DH only affects the upper part of DX, leaving the lower part, DL, unchanged.
> 1 votes

---
Tags: assembly
---


# Question
Title: Covariance and Contravariance: Conflict without a Cause
Here is the last paragraph at page 441 of the paper ‘Covariance and Contravariance: Conflict without a Cause’ by Giuseppe Castagna:

> How is all this translated into object-oriented type systems? Consider a message $m$ applied (or “sent”) to $n$ objects $e\_1$, …, $e\_n$ where $e\_i$ is an instance of class $C\_i$. Suppose we want to consider the classes of only the first $k$ objects in the method selection process. This dispatching scheme can be expressed using the following notation:
>
> $$m(e\_1, …, e\_k | e\_{k+1}, …, e\_n).$$
>
> If the type of $m$ is $\\{S\_i → T\_i\\}\_i$, then the expression above means that we want to select the method whose input type is the $\text{min}\_i \\{S\_i | (C\_1 × … × C\_k) ≤ S\_i\\}$ and then to pass it all the $n$ arguments. The type, say $S\_j → T\_j$, of the selected branch must have the following form:
>
> $$\underbrace{(A\_1 × … × A\_k)}\_{S\_j} → \underbrace{(A\_{k+1} × … × A\_n) → U}\_{T\_j}$$
>
> where $C\_i ≤ A\_i$ for $1 ≤ i ≤ k$ and $A\_i ≤ C\_i$ for $k \< i ≤ n$. If we want to override the selected branch by a more precise one, then, as explained above, the new method must covariantly override $A\_1, …, A\_k$ (to specialize the branch) and contravariantly override $A\_{k+1}, …, A\_n$ (to have type safety).

I expected $C\_i ≤ A\_i$ for $1 ≤ i ≤ n$ (instead of $C\_i ≤ A\_i$ for $1 ≤ i ≤ k$ and $A\_i ≤ C\_i$ for $k \< i ≤ n$), because the call $m(e\_1, …, e\_n)$ is not type safe if we allow some argument types to be greater than the parameter types of the selected method.

Am I misinterpreting the paragraph or did the author make a mistake?

# Answer
> 2 votes
Yes, it is an error. For an application as in the example the relation must be, of course, the one you wrote, that is, $C\_i≤A\_i$ for $1≤i≤n$. The important sentence, however, is the one that follows, namely

> *If we want to override the selected branch by a more precise one, thenthe new method must covariantly override $A\_1,…,A\_k$ (to specialize the branch) and contravariantly override $A\_{k+1},…,A\_n$ (to have type safety).*

It is in that case that the relation I (wrongly) wrote for the application must hold. That is, if the overriding method is defined for *parameters* of type $C\_1,...,C\_n$, then $C\_i≤A\_i$ for $1≤i≤k$ and $A\_i ≤ C\_i$ for $k\<i\leq n$. That is just to say that the theory is correct while the explanation is not.

I would strongly suggest abandoning this paper and rather continue with its recent follow-up, since I have reframed the problem of covariance and contravariance in terms of a much more modern type theory and giving practical examples in Perl6: Covariance and Contravariance: a fresh look at an old issue (a primer in advanced type systems for learning functional programmers) (published in Logical Methods in Computer Science, vol. 16, n. 1, pag. 15:1―15:58, 2020, but the link above gives the latest revised version).

Hopefully, the paper above is much more accessible than my 27-year-old paper, since I wrote it for an audience of undergraduate CS students and all is explained using running code.

P.S. Since I continually revise the paper above, feedback is highly welcome.

---
Tags: programming-languages, type-theory, object-oriented
---


# Question
Title: Finding a $d$-dimensional hyperplane containing $n$ given points
I'm currently trying to find the equation of the $d$-dimensional hyperplane which includes $n$ given points, where $n \ge d$.

Theoretically, it isn't hard - the $d$-dimensional hyperplane is represented as

$$\sum\_{i=0}^{d-1} a\_i x\_i = a\_d$$

for some constants $a\_0, a\_1, \dots, a\_d$.

I have $d$ equations in $d+1$ variables (but one is linearly dependent on all others), solve it. Easy.

But, in practice, I'm having quite a hard time implementing it:

If $n \> d$, I think I need to remove points, and remain only with $d$ points, in order to be able to solve the equation system and find the $a\_i$.

Also, I think I may need to take into account degenerate axes (an axis which is a constant for all given points), and remove those axes before solving the system equation?

I managed to get working code in Python for regular, "normal" cases (I've only tested this in two dimensions for now), but for "hard" cases (like the two dimensional plane $y = -x$, where $a\_2 = 0$), my code fails - I'm getting mostly exceptions like:

> Last 2 dimensions of the array must be square

I'll add my code below, though it looks bad. I don't really like it, but I'm trying to make it work before making it look decent.

I'd really appreciate suggestions!

```
def getPlaneFromPoints(points):
    d = len(points[0])
    degenerateAxes = set()
    for j in range(d):
        # If values in that dimension do not change: if this dimension is degenerate
        if np.all(points[:, j] == points[0][j]):
            degenerateAxes.add(j)
    # Remove degenerate axes
    points = points[:, [j not in degenerateAxes for j in range(d)]]
    # Take at most d points, if there are more than d points
    # I think it's necessary in order to solve the equation system?
    points = np.array(points[:d])
    # The result without the degenerate planes
    non_degenerate_result = np.linalg.solve(points, np.ones(len(points)))
    finalResult = np.zeros(d + 1)
    currIndex = 0
    for i in range(d + 1):
        if i == d:
            finalResult[i] = -1
        elif i in degenerateAxes:
            finalResult[i] = 0
        else:
            finalResult[i] = non_degenerate_result[currIndex]
            currIndex += 1
    return finalResult

```

# Answer
This may or may not answer your question, but there's a useful trick you should know.

Sppose you are trying to solve the overdetermined linear system:

$$Ax = b$$

Pre-multiplying both sides of the equation by the transpose of $A$ gives a system that isn't over-determined:

$$A^{T}A x = A^{T}b$$

The solution to this system is the least-squares fit of the original problem. Moreover, $A^{T}A$ is not only square, it's also symmetric and positive definite (assuming it's not singular), so you can use specialised techniques such as Cholesky decomposition or the conjugate gradient method to solve it.
> 2 votes

---
Tags: linear-algebra
---


# Question
Title: Generating combinations that fulfill certain restrictions for graphs
I am working with graphs, let's say I have 4 nodes, named **A, B, C, D**, each node has to be connected a certain number of times to the other nodes.

**A: 3, B: 3, C: 2, D: 2**

This means that **A** and **B** are connected three times and **C** and **D** two times. All the possibles pairs generated are the following:

**(A, B), (A, C), (A, D), (B, C), (B, D), (C, D)**

Now I need to generate all combinations of **5** pairs where **A** and **B** appear three times and **C** and **D** two.

This is an example of an acceptable combination: **(A, B), (A, C), (A, D), (B, C), (B, D)**

Here the set fulfills this condition: **A: 3, B: 3, C: 2, D: 2** With **A** and **B** appearing three times and **C** and **D** only two.

This is an example of an unacceptable combination: **(A, B), (A, C), (A, D), (B, C), (C, D)** Here the set doesn't fulfill this condition: **A: 3, B: 3, C: 2, D: 2** With **A** and **C** appearing three times and **B** and **D** only two.

Anyone know how I could create an algorithm that gets me only the combinations of pairs that fulfill this condition?

# Answer
Your problem is addressed in Kim, Toroczkai, Miklós, Erdős and Székely, On realizing all simple graphs with a given degree sequence.
> 2 votes

# Answer
Here is an algorithm I've coded myself that does what I asked:

import numpy as np
from itertools import chain, repeat, count, islice
from collections import Counter

def unique_combinations(iterable, r):

    def repeat_chain(values, counts):
        return chain.from_iterable(map(repeat, values, counts))

    def unique_combinations_from_value_counts(values, counts, r):
        n = len(counts)
        indices = list(islice(repeat_chain(count(), counts), r))
        if len(indices) < r:
            return
        while True:
            yield tuple(values[i] for i in indices)
            for i, j in zip(reversed(range(r)), repeat_chain(reversed(range(n)), reversed(counts))):
                if indices[i] != j:
                    break
            else:
                return
            j = indices[i] + 1
            for i, j in zip(range(i, r), repeat_chain(count(j), counts[j:])):
                indices[i] = j

    values, counts = zip(*Counter(iterable).items())
    return unique_combinations_from_value_counts(values, counts, r)

def havel_hakimi(deg_sequence, edge_list=[], i=0):

    node = deg_sequence.pop(0)
    a = []
    for j in range(len(deg_sequence)):
        if deg_sequence[j] <= 2:
            factor = deg_sequence[j]
        else:
            factor = 2
        a += factor * [(i, j+i+1)]

    i += 1
    for combination in unique_combinations(a, node):
        deg_sequence_copy = deg_sequence.copy()
        edge_list_copy = edge_list.copy()
        edge_list_copy += combination
        subtract_vertices_list = [item[1]-i for item in combination]

        for vertex in subtract_vertices_list:
            deg_sequence_copy[vertex] -= 1

        while deg_sequence_copy[-1] == 0 and len(deg_sequence_copy) > 1:
            deg_sequence_copy.pop(-1)

        if not all(v == 0 for v in deg_sequence_copy) and len(deg_sequence_copy) > 1:
            havel_hakimi(deg_sequence_copy, edge_list_copy,  i)

        if all(v == 0 for v in deg_sequence_copy):
            print(edge_list_copy)
            pass

        else:
            pass
```

> 0 votes

---
Tags: algorithms, graphs, combinatorics
---


# Question
Title: Cost of increasing a binary counter with a starting value n times
Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b\_i$ for each $i = 0, . . . , k − 1$. Let $b = b\_0 + 2b\_1 +· · · + 2^{k−1} b\_{k−1}$. The cost of each increment is the number of bits flipped. Show that for $n ≥ b$ the cost of $n$ increments from that initial state does not exceed $4n$. Prove that this bound does not necessarily hold if we do not require that $n\ge b$.

I know how to bound the cost of binary counters when they start at 0 using the aggregate method, but I'm not sure how to solve this when we can start at any arbitrary number. My first guess would be to separate out the increments in between $b$ to $2^{k-1}$ and $0$ to $n - (b - 2^{k-1})$ but then I don't see the significance of the $\ge b$ restriction.

# Answer
#### Aggregate method $\def\C{\mathcal C}$

The $i$-th bit is flipped every $2^i$ steps.

Imaging the counter was increased from $0$ to $b$ and then from $b$ to $b+n$. The total cost of all $n+b$ increments is: $$(n+b) + \frac{n+b}2 +\frac{n+b}4 + \cdots +\frac{n+b}{2^{\lfloor log\_2(n+b)\rfloor}}\le 2(n+b)\le 4n$$

So, the total cost of the last $n$ increments is at most $4n$. $\quad\checkmark$

#### Potential method.

Assume that you have proved the amortized cost of each increment is at most 2 before. Imagine the counter is increased from $0$ to $b$ and then from $b$ to $b+n$. The total cost of all $b+n$ increments is no more than the total amortized cost of all $b+n$ increments, which is at most $2(b+n)\le 4n$. Of course, the cost of last $n$ increments is no more than the total cost of all $b+n$ increments. $\quad\checkmark$

---

Otherwise, let us start from scratch.

Let $\C$ be the $k$-bit binary counter. The value of $C$ is the binary number represented by $\C$, i.e., $$V(\C)=d\_0 + 2d\_1 +· · · + 2^{k−1}d\_{k−1},$$ where $d\_i$ is the value of $i$-th significant bit of $\C$. We may refer to $\C$ at a moment by $V(\C)$ at that moment.

The potential of $\C$ is defined as the number of $1$s in it, i.e.,

$$ \Phi(\C) = d\_0 + d\_1 +· · · + d\_{k−1}$$

---

Let us compute the amortized cost for an increment operation.

Suppose the $j$-th increment reset $t\_j$ bits, changing the value of $\C$ to $v\_{j-1}$ to $v\_{j}$. ($v\_0=b$)

The actual cost of the increment, $c\_j$ is therefore at most $t\_j+1$, since in addition to resetting $t\_j$ bits, it sets at most one bit to $1$.

* If $v\_j=0$, i.e. $\Phi(v\_j)=0$, then the $j$-th increment resets all $k$ bits, and so $\Phi(v\_{j-1})=t\_j=k$.
* If $v\_j\>0$, then $\Phi(v\_j)=\Phi(v\_{j-1})-t\_j+1$.

In either case, $\Phi(v\_j)\le \Phi(v\_{j-1})-t\_j+1$, and the potential difference is $$\Phi(v\_j)-\Phi(v\_{j-1})\le \Phi(v\_{j-1})-t\_j+1-\Phi(v\_{j-1}) = 1 - t\_j$$

The amortized cost $$\widehat{c\_j}=c\_j + \Phi(v\_j)-\Phi(v\_{j-1})\le (t\_j+1)+(1-t\_j)=2$$

---

After $n$ increments, the amortized cost $$\sum\_{j=1}^n\widehat{c\_j}=\sum\_{j=1}^nc\_j + \Phi(v\_n)-\Phi(v\_0)\le2n\\ $$ So, $$\begin{aligned} \sum\_{j=1}^nc\_j &\le 2n -\Phi(v\_n)+\Phi(v\_0)\le2n -\Phi(v\_n)+v\_0\\ &=2n-\Phi(v\_n)+b=2n-\Phi(v\_n)+n= 3n-\Phi(v\_n)\le3n\\ \end{aligned}$$

That is, the cost of $n$ increments from the initial state $b$ does not exceed $3n$.

With tighter estimation, we can see that, in fact, the cost is at most $2n + \log\_2(b+1)$.
> 1 votes

---
Tags: time-complexity, arithmetic, binary, amortized-analysis
---


# Question
Title: Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$
Turing Machine for the Language $L=\\{(a^n)b(a^n)b(a^n) | n\geq0\\}$

Here is what I have **tried**:

**1. Starting State**
Read $a$, Write $x$, Move Right, Go To **2**
Read $x$, Write $x$, Move Right, Go To **1**
Read `Bottom`, Go to State `YES`.

**2. Looking for $ab$**
Read $b$, Write $b$, Move Right, Go To **3**
Read $a$, Write $a$, Move Right, Go To **2**

**3. Middle Segment**
Read $a$, Write $x$, Move Right, Go To **4**
Read $x$, Write $x$, Move Right, Go To **3**

**4. Looking for $ab$**
Read $b$, Write $b$, Move Right, Go To **5** Read $a$, Write $a$, Move Right, Go To **4**

**5. Last Segment**
Read $a$, Write $x$, Move Right, Go To **6**
Read $x$, Write $x$, Move Right, Go To **5**

**6. Back to Beginning**
Read $x$, Write $x$, Move Left, Go To **6**
Read $a$, Write $a$, Move Left, Go To **6**
Read $b$, Write $b$, Move Left, Go To **6**
Read `Bottom`, Write `Bottom`, Move Right, Go To **1**

However the problem is that it Accepts the Empty String but the Smallest Acceptable Input is $bb$. Please help in resolving the issue.

> **Implicit Information**
>
> * `Bottom` means `Blank Symbol`, often denoted by `B`
> * `Starting State` means $q\_o$
> * $\Sigma = \\{a,b\\}$ (Input Alphabet)
> * $T = \\{a,b,x,Bottom\\}$ (Tape Alphabet)
> * `YES` means `Accept State`

# Answer
> 2 votes
Please check the start state, since your TM will accept when its `Bottom`, which from your explanation is `Blank`. That should be the reason for the TM accepting an empty input. Also, you do not have any means for checking a $bb$ input at the start.

---
Tags: formal-languages, turing-machines, lambda-calculus, computation-models
---


# Question
Title: Is it faster to use Counting Sort to lexicographically sort characters in a word in Python?
Assuming I have very long words, is it worth it to use Counting Sort with its memory overhead to achieve linear time complexity?

I wrote a Python function that sorts the characters in a given string using Counting Sort, but it looks like I have to go through the overhead of constructing the output list and converting it to string at the end.

```
def count_sort(s):
    counts = [0] * 26
    res = []
    for i, c in enumerate(s):
        counts[ord(c)-97] += 1
    for i, c in enumerate(counts):
        for j in range(c):
            res.append(chr(i+97))
    return "".join(res)

# print(count_sort("noise")) -> "einos"
# print(count_sort("nuance")) -> "acennu"

```

I feel like this would be more efficient in programming languages with mutable strings, like C++, for example. I also wonder if it even makes sense to use if I know that words are short

# Answer
> 1 votes
Asymptotically, it doesn't matter if you have very long or short words, counting sort would take more space and time if the **range** in which those words lie is very large, since you will have to store counts for that range. The complexity of counting sort is $O(n+k)$ where $k$ is the range, which must be $O(n)$ for it to have a linear time and space complexity.

Now applying this to your problem, it can be interpreted as sorting multiple words of length 1 using counting sort. If you are sure that your string would comprise of only lowercase alphabets(or any fixed range for that matter), counting sort should work just fine for small use cases. It's easy to see that sorting a binary/ternary string would be much more efficient than sorting an alphabetical string in this case. You might want to optimise the extra space by only maintaining counts for the characters which actually occur in your string, for ex: if your string contains only 3 characters b,f,k, then you can avoid storing counts for rest of the alphabets.

As far as implementation is considered, it is language specific. You might find some way in assembly which is even more efficient. And if your input is truly very large, the likes of which can't be stored in the RAM, then you'll need to dump it on a storage device and sort it, which again is an implementation detail.

---
Tags: time-complexity, sorting, strings, python
---


# Question
Title: How would I show function $f(x)=4x$ is Turing computable?
How to show $f: \mathbb{N} \to\mathbb{N}$ with $f(x)=4x$ where $x$ is in the set of natural numbers $x\in\mathbb{N}$) is Turing Computable?

My guess is obviously *there is a finite number of operations needed to reach a solution meaning it is Turing computable*.

Not sure how to prove this though! Can someone please expand?

# Answer
> 1 votes
If you can show an **algorithm** works on a Turing Machine to compute the $4x$, then you can show it is Turing computable. You can also use any TM that can be reduced to a TM as well *\[Example: the double tapes, double heads and other variants\]*

The really cheap way to do this is if you have a TM-complete programming language, which there are a lot of, you can just write such a program and say there exists a TM that computes this function.

Otherwise, if this is for an assignment, my guess is your professor wants you to come up with a more TM type algorithm, with tapes and a head.

Such an algorithm that's really naïve is you could mark every section of the tape all the way until you encounter where $x$ is. Then, you shift all of the marks and $x$ to the next part of the tape, essentially shifting all your $\\{1, 2, \ldots, x\\}$ to $\\{x+1, x+2,\ldots, 2x\\}$. Do this until you have $\\{3x+1, 3x+2, \ldots, 4x\\}$. Then, go erase every $x$ except for $4x$, and that's your output.

---
Tags: formal-languages, turing-machines, computability, automata, arithmetic
---


title: Recursive function - proof by induction

text:
# Question
Title: Recursive function - proof by induction
Let $\Sigma$ denote an alphabet and $\[ \Sigma \]$ set of lists.

I've encountered the following function:

$f(\[\])=\[\]$ (empty list)

$f(\[x\])=\[x\]$, for $x \in \Sigma$

$f(x:L)=f(L)$, for $x \in \Sigma$ and $L \in \[ \Sigma \]$

The function is supposed to return a tail for nonempty list. That is:

$f(\[x\_1,x\_2,...,x\_n\])=\[x\_n\]$

How would you understand the ":" operator in the definition?

Inductive proof should be possible for showing that such a "tail function" is indeed working.

# Answer
I think it's a template match, meaning if you have some list $L = \[x\_1, x\_2, \dots, x\_n\]$, then $L = x:L'$ where $L' = \[x\_2, x\_3, \dots, x\_n\]$.

So you can imagine what that definition is saying is that $f(x:L)$ is equivalent to operating on the rest of the list, i.e. $L$ in this case, hence $f(L)$.

Induction follows pretty easily because once you've shown for a list of length $n$, to show $n+1$, you just use the function definition, which peels off the first element, and you immediately have a list of $n$, which is true by the inductive hypothesis.

Note that there are also notations such as

* $L:y$ : $y$ is the last element
* $x:L:y$ : $x$ is the head, $y$ is the tail
> 2 votes

---
Tags: recurrence-relation, recursion, induction
---


# Question
Title: How can I prove the file on DVD is the original?
I have an old file written to a DVD-R several decades ago, and it turned out this file can potentially has some value as NFT (non-fungible token). The file was published online and have been copied several times by rather famous companies. I want to prove that I own the original file.
I know that this DVD at least contains file creation date attribute. But is this enough? What if I make a .iso image of this DVD and say this proves the file has not been tampered?

# Answer
There's no value in just owning the file of an NFT, that's why there are so many memes about right clicking JPEGs and saving them. Owning the smart contract is what really matters in the NFT world, so even if you had the original file that represents the backing asset by how the NFT is stored on the blockchain, it's irrelevant, because anybody else could also find that backing asset and then make another DVD.

In terms of verifying the file you can likely do a hash checksum and see if it matches up with the file you're curious about.

If you're curious about how NFT files are stored and assets are displayed, this is a good reading: https://art.haus/on-chain-nfts-and-why-theyre-better/

You're talking about an off-chain case.
> 3 votes

---
Tags: cryptography, filesystems
---


# Question
Title: Do I need to learn probability for CLRS?
I am currently learning Discrete mathematics.

there is a topic on dicrete probability (which I havent covered yet), but I also know there is non-discrete probabiltiy but I dont know what they really are.

My aim is to learn math so I can understand CLRS, is probability needed for clrs ?

# Answer
> 1 votes
If you're studying CS at school, I'd recommend just learning what the curriculum tells you to. CLRS is intro to algorithms, which is a pretty broad subject. Do you technically need any prereqs? Not really, but will it benefit you eventually? Yes. It might take a while, but off the top of my head, there are some continuous probability concepts that appear later on when you need to prove algorithms with randomization and prove that it works with high probability. In these cases, you might not always have a discrete probability system.

In terms of discrete vs non-discrete probability, it's not so much about learning one or the other. They are sort of related in terms of concepts (fundamentally it's pretty much the same), but because of finite elements vs infinite elements, the math checks out differently.

At the end of the day, probability is just

$$\frac{\text{what you want}}{\text{what you want} + \text{what you don't want}}$$

These values might represent a discrete set, or a continuous set (geometric), but the concept is still the same.

So TLDR I would recommend learning everything, as it will definitely be useful down the line, but for practical reasons, just follow whatever your curriculum tells you to do.

It never hurts to learn more.

---
Tags: algorithm-analysis
---


# Question
Title: Bounding the height of a tree in a variant of disjoint set union
Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $\ell\_i$ = $⌊\log\_2|T\_i|⌋$ and, when merging $T\_i$ and $T\_j$, we use the following rules:

• if $\ell\_i$ \< $\ell\_j$ , we make the root of $T\_i$ point to the root of $T\_j$ ;

• if $\ell\_i$ \> $\ell\_j$ , we make the root of $T\_j$ point to the root of $T\_i$;

• if $\ell\_i$ = $\ell\_j$ , we choose one of the two options above arbitrarily.

Recall that we define the height of a rooted tree as the length of the longest path from a leaf to the root; e.g., the height of a tree that only contains one node is $0$. Prove that under our rules, the height of a tree that contains $s$ nodes does not exceed $2\log\_2s$.

I think this is meant to be solved using induction - I've solved the $\ell\_i\>\ell\_j$ case (the $\ell\_j$\>$\ell\_i$ is symmetric).

I'm stuck on the $\ell\_i$ = $\ell\_j$ case, here's my attempt:

$\ell\_i \le \log\_2|T\_i|$
$\implies 2^{\ell\_i} \le |T\_i|$

as $\ell\_i = \ell\_j$ we have $2^{\ell\_i} = 2^{\ell\_j}$

$\therefore 2\log\_2(|T\_i|+|T\_j|) \ge 2\log\_2(2^{\ell\_i} + 2^{\ell\_j})$
$ = 2\log\_2(2\cdot2^{\ell\_i})$
$ = 2\log\_2(2^{\ell\_i + 1})$

(which should be but I can't prove)$ \> h + 1$ where $h$ is the height of $T\_i$

How do I prove this?

# Answer
> 2 votes
Let me solve the case where you got stuck. Suppose $T\_i$ with $\ell\_i$ and $T\_j$ with $\ell\_j$ is merged into tree $T$, where $\ell\_i$ = $\ell\_j$.

WLOG, suppose we make the root of $T\_i$ point to the root of $T\_j$. Then $h(T)$ is either $1+h(T\_i)$ or $h(T\_j)$.

$$|T| = |T\_i| + |T\_j|\ge|T\_i| + 2^{\ell\_j}=|T\_i| + 2^{\ell\_i+1}/2\gt|T\_i| + |T\_i|/2=\frac32|T\_i|$$

Let $\log$ mean logarithm with base 2. Then $$2\log|T|\gt 2\log(\frac32|T\_i|)=\log\frac94+2\log|T\_i|\gt1+2\log|T\_i|$$

Thanks to the induction hypothesis,

* $1+h(T\_i)\le1+2\log|T\_i|\lt 2\log|T|$
* $h(T\_j)\le 2\log|T\_j|\lt 2\log|T|$.

We conclude $h(T)\lt 2\log|T|$. Other cases can be done, in fact, more or less similarly.

---
Tags: data-structures, trees, induction, disjoint-sets
---


# Question
Title: Simplifying Notations in Recurrence Relation
In the CLRS book, section 4.4 they try to resolve the following recurrence:

$$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$

Later, they write the same recurrence as

$$T(n) = 3T\bigg(\frac{n}{4}\bigg) + cn^2$$

And I do not understand why they change $\Theta(n^2)$ to $cn^2$

Mathematically speaking, Theta is a set, while $cn^2$ is a number. Furthermore I know that $cn^2 \in \Theta(n^2)$ but not every polynomial in $\Theta(n^2)$ is in the form $cn^2$.

I'd enjoy to have a mathematical proof of what they did is correct, even if it's "easy to see", but I'm not satisfied with that.

**Update**
For whoever might be interested in the same question and seek for an answer, other than the given answers, I wrote a document here: https://www.overleaf.com/read/npvdnwyfxpcb

# Answer
> 1 votes
You may consider

$$T(n) -3T(\lfloor n/4 \rfloor) = \Theta(n^2) $$

which means that for some $N$, $n\>N$ implies

$$T(n) -3T(\lfloor n/4 \rfloor) \le cn^2.$$

And if $n$ is a power of $4$, you may drop the floor:

$$T(n) -3T(n/4) \le cn^2.$$

These transformations are meant to make the resolution more tractable, and will not impair the final conclusions.

---
Tags: algorithm-analysis, asymptotics, recurrence-relation, big-o-notation, notation
---


# Question
Title: Prove irregularity of a language using closure properties
Given the language $L=\\{a^{j+1}b^kc^{j-k}|j\ge k\ge 0 \\}$ I need to prove that it is not a regular language using closure properties.

I was having a trouble handling $a^{j+1}$ so I tried to prove this first for $L\_1 = \\{a^jb^kc^{j-k}|j\ge k\ge 0 \\}$, I assume $L\_1$ is regular and define an homomorphism $h: \\{a,b,c\\}\rightarrow \\{a,b\\}$ such that $$h(a) = b,\space h(b) = a,\space h(c)=\varepsilon$$ and I get $L\_2=h(L\_1)= \\{b^ja^k|j\ge k\ge 0 \\}$ which is also regular by my assumption and the closure of homomorphism, and from the reverse closure I get $L\_3 = L\_2^R = \\{a^kb^j|j\ge k\ge 0 \\}$ is also a regular language but I already know that $L\_3$ isn't regular, a contradiction, therefore, $L\_1$ isn't regular.

Going back to the original language $L$, I think I need to find a way to reach $L\_1$ from $L$ while using closure properties so the assumption of $L$'s regularity leads to a contradiction, but so far I couldn't find any

# Answer
> 3 votes
Suppose that $L$ is regular. Since regular languages are closed under intersection, then $$ K = L \cap a^\*c^\* = \\{a^{j+1}c^j \mid j \geqslant 0 \\} $$ would be regular and the left quotient of $K$ by $a$ $$ a^{-1}K = \\{u \mid au \in K\\} = \\{a^jc^j \mid j \geqslant 0 \\} $$ would also be regular. I suppose you already know that this latter language is not regular. Thus $L$ is not regular.

# Answer
> 1 votes
Assume $L\_3 = \\{a^kb^j|j\ge k\ge 0 \\}$ is the only language that is known to be non-regular.

---

Let $L\_4=\\{b\\}$, the language that contains one string, $c$. Then $(h(L\circ L\_4)\cup\\{\epsilon\\})^R=L\_3$. Since $L\_3$ is non\_regular but $ L\_4$ and $\\{\epsilon\\}$ are regular and regular languages are closed under concatenation, homomorphism, union and reversal, $L$ must be non-regular.

---

Let $L\_5=\\{a\\}$. Then $(h(L\_5\backslash L))^R=L\_3$, where $L\_5\backslash L$ is the left quotient of $L$ by $L\_5$. Since $L\_5$ is regular and regular languages are closed under left quotient, homomorphism and reversal, $L$ must be non-regular.

---

It might be more reasonable to assume that $L\_6=\\{a^nb^n\mid n\ge0\\}$ is known to be non-regular, since that is the first language presented as non-regular in many textbooks.

**Exercise**. With the assumption above, show $L$ is non-regular using closure properties.

---
Tags: regular-languages, closure-properties
---


title: Why do combinators look this way?

text:
# Question
Title: Why do combinators look this way?
Out of curiosity, why do combinators look this way? For example, why is $K = \lambda x y \to x$ and why is it called $K$? Why is it not $\lambda x y f m \to f m x$? These are just arbitrary letters, I have no idea what this function does. Or why is $S = \lambda f g x \to f x (g x)$?

Who first discovered that combinators should look this way? Who named them?

# Answer
> 5 votes
The combinators $K$ and $S$ first appear in Moses Schönfinkel, Über die Bausteine der mathematischen Logik, though he calls them $C$ and $S$. He actually defines five combinators, $I,C,T,Z,S$, and then shows that they can all be expressed in terms of $C$ and $S$ alone.

The modern notation appears in Haskell Curry, Grundlagen der Kombinatorischen Logik, in the order $I,K,B,C,S$ (which correspond to Schönfinkel's $I,C,Z,T,S$).

Schönfinkel calls $C$ the *constant function* (the German word starts with K), and $S$ the *fusion function*; perhaps the letter $S$ is in analogy to $Z$, the *composition function* (the German word starts with Z), defined by $Zxyz=x(yz)$. (To complete the picture, $I$ is the *identity function*, and $T$ is the *swap function* defined by $Txyz=xzy$.) Curry gives no explanation whatsoever for his choice of letters.

# Answer
> 3 votes
This is so because $K$ and $S$ can be used to generate all other $\lambda$-terms (up to extensional equality), refer to this proof for the details.

---
Tags: lambda-calculus, history, combinatory-logic
---


# Question
Title: What is the formalism used to describe optional arguments called?
Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example:

> foo \[opt1\[opt2...\]\] req1 req2 \[opt3...\]

It alone is not as powerful as regular expressions since it cannot express the language of zero or more ab's nor the language of strings with even number of a's.

Is the format known under a name?

# Answer
Answers to a related StackOverflow question point us towards Wikipedia's page on CLIs, which under a subsection titled *Command Description Syntax* describes a similar syntax:

> Built-in usage help and man pages commonly employ a small syntax to describe the valid command form:
>
> * angle brackets for required parameters: `ping <hostname>`
> * square brackets for optional parameters: `mkdir [-p] <dirname>`
> * ellipses for repeated items: `cp <source1> [source2...] <dest>`
> * vertical bars for choice of items: `netstat {-t|-u}`

The Wikipedia article has listed the die.net Linux man page documentation as **one** of its sources, which indeed — under the *Synopsis* section — describes a similar format:

> **SYNOPSIS**
> briefly describes the command or function's interface. For commands, this shows the syntax of the command and its arguments (including options); boldface is used for as-is text and italics are used to indicate replaceable arguments. Brackets (\[\]) surround optional arguments, vertical bars (|) separate choices, and ellipses (...) can be repeated. For functions, it shows any required data declarations or #include directives, followed by the function declaration

This is all to say, I don't think there is a canonical answer to your question. There are just different (pretty similar) conventions that are documented near their place of use.

To give my twopence's worth, I think Wikipedia's "Command description syntax" or something like "Manpage synopsis format", would be good names for the convention.
> 0 votes

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


# Question
Title: If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable
I should prove or give a counterexample to the above statement.

In my opinion, this statement is false but I don't manage to find the right counterexample.

My idea was to define $C = Σ^\*$ because $Σ^\*$ is decidable and contains all the undecidable languages but I fail to find an undecidable language that contains a decidable language.

# Answer
> 6 votes
1. There exists undecidable languages.
2. $A = \emptyset$ and $C = \Sigma^\*$ are decidable.
3. ????
4. Profit.

---
Tags: computability, undecidability
---


# Question
Title: Pumping Lemma $A = \{0^n1^n \mid n \geq0\}$. Prove $A$ is not regular
**Question :** Are my Justifications Correct?

**Pumping Lemma**
$A = \\{0^n1^n \mid n \geq 0\\}$. Prove $A$ is not regular :

Suppose $S = 0^p1^p$ and $p = 3$.
Therefore, $S = 000111$. Breaking $S$ into $xyz$

---

**Case 1 :** $y$ is in the $0's$ part.

Therefore, $xy^iz \notin A $ for $i = 3$, because if $i = 3$, then $S\_i = 0 000 111$ Therefore, there is an additional $0$, so $xy^iz \notin A $

---

**Case 2 :** $y$ is in the $1's$ part.

Therefore, $xy^iz \notin A $ for $i = 3$, because if $i = 3$, then $S\_i = 000 111 1$. Therefore, there is an additional $1$, so $xy^iz \notin A $

Also, $|xy| \> p$, because as $i$ increases, the amount of $1's$ is not equal to amount of $0's$ ?

---

**Case 3 :** $y$ contains $0's$ and $1's$

Therefore, $xy^iz \notin A $ for $i\geq1$ ? Because as $i$, the order of the symbols is violated.
Also, $|xy| \> p$

---

I am confused at what value of $i$ does $xy^iz \notin A $?
**Can someone please clarify?**

# Answer
In your proof, you assume $p=3$. This would only prove that there does not exist a machine \[a finite automata\] with three states accepting the given language $A = \\{0^n 1^n: n \ge 0\\}$. To show the language is not regular, you should not assume any fixed value of $p$. Also, you can assume that the length of $xy$ is at most $p$, which means $y$ would contain only 0’s. Here’s a proof:

Suppose there exists a machine with $p$ states accepting the given language $A$. Let $S = 0^p 1^p$. Then, there exist strings $x,y$ and $z$ such that $S = xyz$, $|xy| \le p$, $|y| \ge 1$ and $xy^kz \in A, \forall k \ge 0$. (This can be proved by the pigeonhole principle and is implied by the pumping lemma.) However, the conditions $|xy| \le p$ and $|y| \ge 1$ imply $y$ is a string of one or more zeros, whence $xyyz \in A$, a contradiction because $xyyz$ contains more $0$’s than $1$’s.
> 1 votes

---
Tags: formal-languages, regular-languages, automata, finite-automata, pumping-lemma
---


# Question
Title: Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
Given the **recurrence**

$$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$

My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with the **substitution** method.

So $T(n)$ is $\leq cn$ for every $c\geq4$. So in my opinion $T(n)$ is $O(n)$.

Who is **right?**

# Answer
> 5 votes
You are right: you can apply the Akra-Bazzi method to find that $T(n) \in \Theta(n)$.

Your professor is right: since $\Theta(n) \subseteq \mathcal{O}(n\log n)$, it is also true that $T(n) \in \mathcal{O}(n\log n)$.

# Answer
> 2 votes
Let $n=2^m$. The recurrence is written

$$T(2^m)=2T(2^{m-3})+2T(2^{m-2})+2^m$$

or

$$U(m)=2U(m-3)+2U(m-2)+2^m.$$

A particular solution is given by $U=c2^m$ and more precisely

$$c=2\frac c8+2\frac c4+1,$$ giving $c=4$.

Then the characteristic polynomial of this ordinary linear recurrence has three roots with a modulus smaller than $2$ (https://www.wolframalpha.com/input?i=roots+of+x%5E3-2x-2%3D0) and the homogeneous response becomes neglectable compared to the particular solution.

Hence the solution is indeed asymptotic to $2^m=n$.

---
Tags: time-complexity, asymptotics, recurrence-relation, big-o-notation, master-theorem
---


# Question
Title: Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?
1. $L=\\{a^n b^m:n\neq m\\}$
2. $L=\\{a^n b^l c^k :k\neq n+l\\} $

Can we take in case 1 $w=0^{2p}1^p$?

But my resource says that, we need to take $w=0^{p}1^{p+p!}$

Similarly in case 2, I want to take $w=a^p b^p c^{3p}$

but my resource, item 23 as shown below says that we need to take something else. $w=a^{p!}b^{p!}c^{(p+1)!}$

I guess that $a^{(p+1)!}$ is for c.

I have the proof, so please don't bother doing the proof, I just want to know if we can choose different values like I said? I know we can't, but I don't know the reasoning behind it.

# Answer
> 3 votes
The negation of "pumpable" as described in the pumping lemma states:

```
for all n
exists w in L with |w| > n
for all...
exists...
for which...

```

You can choose that w freely as long as it has at least length n as there often is more than one combination that satisfies this. Your resource can only demonstrate the solution for one specific instance.

# Answer
> 3 votes
> I have the proof, so please don't bother doing the proof, I just want to know if we can choose different values like I said? I know we can't, but I don't know the reasoning behind it.

Yes, we can.

The pumping lemma states that for every regular language $L$, there exists a pumping length $p$ such that every $s \in L$ with $|s| \geq p$ can be partitioned into $xyz$ such that $xy \leq p$, $|y| \> 0$ and $xy^iz \in L$ for all non-negative integers $i$.

This means, on a principal level, you can start a pumping lemma proof of non-regularity with *any* string in $L$, as long as its length is at least $p$, so none of the strings in your question are obviously invalid. However, you might not be able to complete the proof with any given string.

For example, for the language $L = \\{0^n 1^m : n \neq m\\}$ you won't get far with $0^{2p}1^p$. We can simply set $x = \epsilon$, $y = 0$ and $z = 0^{2p-1}1^p$. This will only break the conditions of the lemma when $p = 1$, but this caveat changes little since it's just possible 1 isn't a valid pumping length for the language.

The factorial trick used in the source you cite ensures the number of $0$ and $1$ will align for large enough $i$ no matter the choice of otherwise-legal $xyz$, proving the three conditions cannot be satisfied. To illustrate, suppose we have some partition where $y = 0^n$ with $1 \leq n \leq p$. This means $xy^1z$ begins with $0^p$, $xy^2z$ begins with $0^{p+n}$, $xy^3z$ begins with $0^{p+2n}$ etc. More generally, the number of leading zeroes in $xy^iz$ is $p+(i-1)n$. Meanwhile, the number of trailing ones is $p + p!$. Subtract $p$ and divide by $n$: the equation will be satisfied when $i = 1 + \frac{p!}{n}$.

However, in general, the important take-away is that there is no particular "magic string" you *must* use. Any string that can be used to create the necessary contradiction works, some are just easier to use than others and some might not work at all.

# Answer
> 0 votes
Yes, you can choose different strings of length at least $p$ (where $p$ is the constant given in the pumping lemma) than the one given in the resource; however, not all strings will help you complete the proof. In particular, the string $0^{2p} 1^p$ in the first example, and the string $a^p b^p c^{3p}$ in the second example, will not work (i.e. will not push the proof through).

We need to start with a string in $L$, and then pump it to obtain a string not in $L$. But your choices of strings don’t achieve this objective. For the string $0^{2p}1^p=xyz$, $y$ is a string containing one or more $0$’s, and any pumped string such as $xyyz$ or $xyyyz$ would continue to have more $0$’s than $1$’s and hence belong to $L$. In the case of a string $S=a^p b^p c^{3p} \in L$, if $p=3$, then $S=a^3 b^3 c^9$, and if $y=aa$, then all pumped strings continue to belong to $L$ because $a^1 b^3 c^9, a^3 b^3 c^9, a^5 b^3 c^9, a^7 b^3 c^9 \in L$.

Recall that your adversary gets to choose the value of $p$. Your adversary also gets to choose the value of $|y|$. In the proof given in your resource, this length $|y|=m$ was not assumed to be a fixed value but could be any value between $1$ and $p$ (inclusive), and the proof still went through because it was shown that one of the pumped strings did not belong to $L$.

To understand this better, you can work out the proof of the pumping lemma from scratch, using the pigeonhole principle. Given a language $L$ (that you want to prove is nonregular), by way of contradiction, suppose there exists a DFA with $p$ states accepting $L$. Let $S$ be any input string of length at least $p$. Then, by the pigeonhole principle the first $p+1$ states that the DFA visits for this input string must have a repetition, and the first substring of $S$ that takes the machine from this repeated state to itself is the substring $y$. Any pumped version of the string would also take the machine to the same accepting state and hence must also be accepted by the machine. You need to prove that there exists a pumped version of the input string that is not in the given language. You don’t get to choose the length of $y$, you can only be sure that the part of the input up to and including $y$ has length at most $p$, and that $y$ has length at least $1$.

To summarize: given a language $L$ that you want to prove nonregular, your adversary gets to choose $p$, you get to choose $S$ (based on $p$) to be any string in $L$, your adversary can choose how to partition $S$ as $xyz$ (subject to the constraint $|xy| \le p, |y| = i\ge 1$), and you get to show that there exists an $i$ such that $xy^iz \notin L$. This proves that there does not exist a machine with $p$ states accepting $L$, for any arbitrary $p$. You showed that for every machine with $p$ states, there is some string $S$ that cannot be pumped.

---
Tags: regular-languages, pumping-lemma
---


title: Finding the optimal packet size

text:
# Question
Title: Finding the optimal packet size
I have recently started reading the book Computer Networking: A Top-down Approach in hopes to get introduced to computer networks. When attempting one of the questions from the book for practice, I got stuck and spent the whole day today trying to make some progress.

The questions is:

> Consider sending a large file of F bits from Host A to Host B. There are three links (and two switches) between A and B, and the links are uncongested (that is, no queuing delays). Host A segments the file into segments of S bits each and adds 80 bits of header to each segment, forming packets of $L = 80 + S$ bits. Each link has a transmission rate of $R$ bps. Find the value of $S$ that minimizes the delay of moving the file from Host A to Host B. Disregard propagation delay.

I was able to identify that the number of packets we have is $\frac{F}{S}$, and the delay for the first packet will be $N \cdot \frac{L}{R} = 3 \cdot \frac{80+S}{R} seconds$ where $N$ is the number of links. This is all I could come up with and I don't know what to do from here. A **detailed** and **newbie-friendly** explanation to this question would be greatly appreciated!

# Answer
> 0 votes
You are on the right track. The value of $S$ that minimizes the delay of moving the file from host A to host B is $S = \sqrt{40 F}$, which can be shown as follows.

The first packet reaches the destination after a delay of $3 \times d\_{trans}$, where $d\_{trans} = \frac{80+S}{R}$ is the transmission delay, as you’ve already shown. Each of the subsequent $\frac{F}{S}-1$ packets that follow this first packet will take another $d\_{trans}$ time to reach the destination. Hence, the total delay for all the packets is $d\_{trans} \times \left(3 + \frac{F}{S} - 1\right) = d\_{trans} \left( \frac{F}{S} +2\right) = \left(\frac{80+S}{R}\right)\left(\frac{F}{S}+2\right) =: f(S)$.

We have that $$f(S) = \frac{80F}{RS} + \frac{160}{R} + \frac{F}{R} + \frac{2S}{R}.$$

To find the minimum value of $f(S)$, we set the derivative $f’(S)$ to equal $0$, and we obtain

$$\frac{80F}{R} \left(\frac{-1}{S^2}\right) + \frac{2}{R} = 0,$$ i.e. $S = \sqrt{40F}.$ At this value of $S$, $f’’ \> 0$, and so this is a local minimum.

---
Tags: computer-networks
---


# Question
Title: prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$
I need to prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$.

Where CorrectSATSolver $= \\{C | C(\varphi) = 1 \iff \varphi$ is satisfiable$\\}$. In other words, CorrectSATSolver problem is as follows: Given a circuit C, decide if the circuit C solves the SAT problem.

I don't understand how to use the assumption.

I have already proven in class thet CorrectSATSolver $\in coNP$, I'm not sure if it helps.

I would very appreciate any help. Thank yoy

# Answer
If $|C| \< 2^{n/100}$ then $C \not\in \text{CorrectSATSolver}$ since otherwise we would have $\text{SAT} \in \text{Size}(2^{n/100})$.

Assume then that $|C| \ge 2^{n/100}$. Evaluating $C$ for a fixed assignment requires time $|C|$ and there are at most $2^{n}$ possible distinct truth assignments to a formula of size $n$. Therefore $\text{CorrectSATSolver}$ can be decided in time $O(2^{n} \cdot |C|) = O((2^{n/100})^{100} \cdot |C|) \subseteq O(|C|^{101})$ by exhaustively checking the output of $C$ for all possible assignments.
> 0 votes

---
Tags: complexity-theory, circuits, sat-solvers
---


title: DFA without the substring "abb"

text:
# Question
Title: DFA without the substring "abb"
$$ L\_{1}:=\left\\{w \in\\{a, b\\}^{\*} \mid w\right. does \ not \ have \ the \ substring \left.a b b\right\\} $$

Hello, I wanted to ask whether this dfa is correct according to L1.

# Answer
> 0 votes
The DFA is not correct. For example, the string $a$ is not accepted by the DFA because $q1$ is not an accepting state, but the string $a$ belongs to $L1$ because it does not contain $abb$.

---
Tags: finite-automata
---


# Question
Title: Am I drawing the recursion trees correctly?
I guess I've already figured out what is a recursion tree and how to construct one. Inspired by Figure 2.5 of "Introduction to Algorithms, 3rd Edition by CLRS", I drew some recursion trees for the recurrence $T(n) = 2T(n/2) + cn$.

the recursion tree for the recurrence when n=16

the recursion tree for the recurrence when n=13

the recursion tree for the recurrence when n=7

Could someone help double-check my understanding?

# Answer
> 3 votes
$T(n/2)$ is not well-defined if $n$ is odd. The merge sort recurrence - if you want to take floors and ceilings into account - is actually $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + cn$. So, if $n=13$, the subproblems would have sizes $7$ and $6$, respectively (not $8$ and $5$, respectively).

It’s ok to be sloppy and assume $n$ is a power of $2$ because that doesn’t affect the final conclusions. Recursion trees are usually drawn with this simplifying assumption, and the intuition carries over to the general case.

---
Tags: recursion
---


# Question
Title: 4-SAT but two literals per clause must be true
I'm trying to show that a modified 4-SAT in which at least two literals per clause must be true is NP-complete. I'll call it $4\_2$-SAT. I understand the reduction from 3-SAT to 4-SAT, and I know why $4\_2$-SAT is in the class NP, so I'm just struggling on the reduction from 4-SAT to $4\_2$-SAT (or any other way to show that $4\_2$-SAT is NP-hard).

My initial attempt was to try and convert an instance of 4-SAT

$(a \vee b \vee c \vee d)$

into an instance of $4\_2$-SAT by spelling out the requirement as

$(a \wedge b) \vee (a \wedge c) \vee (a \wedge d) \vee (b \wedge c) \vee (b \wedge d) \vee (c \wedge d)$

and then convert to CNF and add extra literals if needed to get to four per clause, but this conversion does not preserve the answer of the original 4-SAT clause.

Any hints or help as to how to convert an instance of 4-SAT into $4\_2$-SAT would be appreciated.

# Answer
Schaefer's dichotomy theorem settles the complexity of your problem.

Consider a constraint satisfaction problem (CSP) in which there is a finite collections $S$ of types of constraints over Boolean variables, and an instance is a conjunction of constraints of the form $R(\ell\_1,\ldots,\ell\_k)$, where $R \in S$ is a $k$-ary constraint and $\ell\_1,\ldots,\ell\_k$ are arbitrary literals; the goal is to determine whether the instance is satisfiable, that is, whether there is a truth assignment to the variables which satisfies all constraints. For example, 3SAT is the case in which $S$ consists of the constraint $x \lor y \lor z$, and in your problem $S$ consists of the constraint $R\_{4,2}$ "at least two out of $x,y,z,w$ are true".

* If each $R \in S$ is equivalent to a 2CNF, then the CSP can be solved in polynomial time by reduction to 2SAT. This condition holds iff the set of satisfying assignments of each $R \in S$ is closed under *ternary majority*: if $R$ is a $k$-ary constraint, then for any three satisfying assignments $a,b,c$, the assignment $\operatorname{maj}(a\_1,b\_1,c\_1),\ldots,\operatorname{maj}(a\_k,b\_k,c\_k)$ also satisfies $R$.
* If each $R \in S$ is equivalent to a conjunction of linear equations, then the CSP can be solved in polynomial time using Gaussian elimination. This condition holds iff the set of satisfying assignments of each $R \in S$ is closed under *ternary XOR*: if $R$ is a $k$-ary constraint, then for any three satisfying assignments $a,b,c$, the assignment $a\_1 \oplus b\_1 \oplus c\_1,\ldots,a\_k \oplus b\_k \oplus c\_k$ also satisfies $R$.
* In all other cases, the CSP is NP-complete.

In your case, you can check that $R\_{4,2}$ is not closed under the two operations above:

* The truth assignments $(1,1,0,0),(1,0,1,0),(1,0,0,1)$ satisfy $R\_{4,2}$, but their majority $(1,0,0,0)$ doesn't.
* The truth assignments $(1,1,0,0),(0,0,1,1),(1,1,1,1)$ satisfy $R\_{4,2}$, but their XOR $(0,0,0,0)$ doesn't.

Therefore your problem is NP-complete.

The proof of Schaefer's theorem gives a gadget reduction from either 3SAT or 3NAE-SAT to any NP-complete CSP (3NAE-SAT only occurs if the set of solutions of each $R$ is closed under complementation, which is not the case for $R\_{4,2}$), but this reduction is rather verbose.

In your case, here is a simple reduction from 3SAT to your problem: replace each clause $a \lor b \lor c$ with the constraint $R\_{4,2}(a,b,c,d)$, where $d$ is a new variable common to all clauses (alternatively, you can make $d$ a new variable for each clause, which would make it a gadget reduction in the sense of Schaefer's theorem).
> 3 votes

---
Tags: np-complete, np-hard, np, satisfiability, 3-sat
---