# Question
Title: How does the Inorder-tree-walk algorithm move to a different node after hitting a leaf?
A friend and I did the **Inorder-tree-walk** with pen and paper. We both can't figure out how the algorithm would move 'up' the tree again upon hitting a leaf:

We are using the algorithm as described by our professor and taken from "Introduction to Algorithms, Third Edition" Chapter 12 page 288:

```
Inorder-tw(node)
 if node != nil
   Inorder-tw(node.left)
   print node.key
   Inorder-tw(node.right)

```
* To visualize what we did on paper I wrote each "round" as {1; \<key\_of\_node\>}
* To understand our thought process you should read all the {1; ..}'s first, then all the {2; ...}'s and so on
* We are stuck when we hit the node with the key 11 where both; `node.left` and `node.right == nil`
* This is exactly the point were we don't understand how the algorithm is able to be called again with a the node of the key 17
* We know that the answer is \[11,17,18,31,47,57,69,78,81\]

```

                    47            Inorder-tw(node): {1; 47} {2; 18} {3;17} {3; 11} {5; nil}
                  /   \             if node != nil: {1; T} {2; T} {3; T} {4; T} {5; F} node=nil 11.right
                 /     \                Inorder-tw(node.left): {1; 18} {2;17} {3;11} {4; nil}
                18      78              print node.key {4; 11}
                /\       /\             Inorder-tw(node.right) {4; nil}
               /  \     /  \
              17   31  57   81
              /         \
             /           \
            11            69

```

The example was take from here Though the examples are nicely visualizing what happens in each step, they don't show us how the input is "changed" in the recursive call upon hitting any leaf. As in my head we are stuck forever at node with the key 11 that returns children of the value `== nil`.

Writing out the calls as I understand them it would be:

```
Inorder-tw(47)        Inorder-tw(18)        Inorder-tw(17)        Inorder-tw(11)          Inorder-tw(Nil)
  47 != Nil -> True     18 != Nil -> T        17 != Nil -> T        11 != Nil -> T          Nil != Nil FALSE
  Inorder-tw(47.left)   Inorder-tw(18.left)   Inorder-tw(17.left)   Inorder-tw(11.left)

```

I can't understand how the algorithm is supposed to `print` even though the if statement is evaluated as `FALSE`.

Can anyone explain how the algorithm manages to move back up the tree by changing the input in the recursive call upon hitting a leaf?

# Answer
To understand what happens "when we hit the node with the key 11", let us isolate the call `Inoder-tw(node17)`, which executes the following.

```
    if node17 != nil
       Inorder-tw(node11)  # since node17.left is node11
       print 17            # since node17.key is 17
       Inorder-tw(nil)     # since node17.right is nil

```

So, right after the call `Inorder-tw(node11)`, which prints key `11`, the algorithm will run `print 17`.

It is as simple as that.

---

You might be wondering how the algorithm will know to come "back" to the statement `print 17` when its reaches the end of execution of `Inoder-tw(node11)`, i.e., when it has found that both `node11.left == nil` and `node11.right == nil`.

Well, the call `Inorder-tw(node11)` is just another statement. The pseudocode specifies that, in the form of simple serial statements, when that statement ends, the next statement should be executed. That is how you should understand the pseudocode/the specification of the algorithm.

---

It is a completely different problem as to how an algorithm/this algorithm can be implemented in a particular language runtime or computation model.

* In most popular language runtimes, such as JavaScript, Python, Java, C/C++, C#, etc, there is a "call stack" that remembers where the algorithm/program is running. That is, what are the calls the lead to the current function/procedure/method call. You should have seen those "call stacks" many times when you encounter a runtime error in various languages.
* The runtime also keep track of which statement is running, what is the next statement and, when there is to a need to jump elsewhere to execute, how to locate and reach "elsewhere".

However, how an algorithm is able to run in each language runtime as it is specified is implementation detail. While it is helpful/important to understand those implementation details (so that you can believe that it is possible to implement an algorithm), you should be able to understand the specification of the algorithm by pseudocode, directly.
> 3 votes

# Answer
The function `Inorder-tw` calls itself recursively; there are 2 recursive calls, 1 for each child of the node. The computer (or an equivalent manual execution on paper) will use an internal memory stack to remember such recursive calls' sequence along with their arguments (here the `node` pointer) and the instruction-location to resume to. That is how, when the function returns (upon finding node as null, or having processed the node), the program is able to resume its execution in the "parent" node's call.

In your example, the call with node=(11) will resume when the left-child call returns, and also when the right-child call returns.
> 2 votes

# Answer
It seems like you missed the basic understanding of recursion. That's okay - some teachers don't teach it very well and a lot of students don't get it to "click".

Note: some textbooks might call these "algorithms" or "routines" or "procedures". I don't know what's in *that* textbook. I'm using the word "function" which is standard in most programming languages.

Do you understand what happens when one function calls another function? Like this (Python language):

```
def f(x): # this is how you define a function in Python
  print(x+" world")

def g():
  f("hello")
  f("goodbye")

```

I'm not expecting you to know Python but I hope you can see that when you call `g` it prints `hello world` and then prints `goodbye world`. If you can't see why that is, go back and study functions some more.

---

Now, consider that there's no rule stopping a function from calling itself.

...

That's it. That's what recursion is. *Recursion is the fact that a function is allowed to call itself*. That's all there is. It's not a special rule!

There are things to keep in mind when writing recursive code - like the "always shrinking" rule - but those answer the question: "How can I use recursion to do something useful?" and they do *not* answer the question: "What is recursion?" which is what you need to understand first.

---

One thing you do have to worry about is getting a stack overflow error if you have too many nested function calls. But that's not even special to recursion. You could have a million different functions where each function calls the next one, and get a stack overflow error that way instead:

```
def f0():
    pass # this line does nothing
def f1():
    f0()
def f2():
    f1()
... and so on ...
def f1000000():
    f999999()

def main():
    f1000000() # probably a stack overflow

```

isn't really much different from:

```
def f():
    f()

def main():
    f() # definitely a stack overflow

```

except the second one is much easier to write, and therefore, you can do it accidentally. If you wrote a million functions, then you knew what you were doing - it wasn't a mistake.

---

Back to your code. Your code says: "To print a tree in-order, if the root node isn't nil, then print the left child of the root node in-order, then print the root node, then print the right child of the root node in-order."

If I told you these instructions in English, could you follow them? You could. And so can the computer. It has no problem with these instructions.

However, you might need to use pencil and paper to remember what you're doing, because otherwise it could get confusing. When you have to print the left child of 47, you can write down that you still have to go back and print 47 and then its right child.

The computer also does this. Every time it calls a function, it writes down what to do after that function returns. When the function returns it looks at the last writing, erases it, then goes and does that. So when it calls `f("hello")` it will write down that after `f` returns it has to go back to the second line of `g()` (the one that says `f("goodbye")`). Then it will go to `f("hello")`. Once `f("hello")` finishes it will look at the stack and go back to the second line of `g()` (the one that says `f("goodbye")`).

That section of memory is called "the stack". When there are too many nested function calls going, it fills up that section of memory and that's the "stack overflow" error. It's not a certain number of calls, by the way - it depends on how much data the computer has to save for each call.
> 2 votes

---
Tags: algorithms, binary-search-trees
---


# Question
Title: Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming
I have recently been working on an applied project where I have to solve optimization problems.

I have found that it is much easier to solve an integer linear program (ILP) as opposed to a mixed-integer linear programs (MILP), in the sense it is faster for me to find feasible solutions as well as to prove optimality.

I am wondering if there is some kind of formal result that confirms this (i.e. on the time complexity of ILP vs. MILP).

To be clear, when I am refering to an ILP I mean an optimization problem of the form

$$\begin{align} \min\_{x} \quad & c^Tx \\ \text{s.t.} \quad & Ax = b \\ \\; & x\in\mathbb{Z}^N\end{align}$$

where the variables are integer-valued so that $x\in\mathbb{Z}^N$ but the parameters are real valued so that $c \in \mathbb{R}^N$, $A \in \mathbb{R}^{M \times N}$, $b \in \mathbb{R}^M$. In turn, an MILP would be different in that at least one of the variables would take on a real value.

# Answer
Knowing that integer programming (ILP) is NP-complete, it follows that mixed integer linear programming (MILP) is NP-complete too as MILP generalizes ILP.

My guess is that your thinking and feeling comes from insufficient testing: you don't have enough test cases with different structure, and you don't mention what algorithms you use. Even though both problems are hard, there are (even exact) algorithms that perform well on suitably structured instances. You should look at where the really hard instances are (they are not necessarily large), and try running your algorithms again.
> 2 votes

# Answer
Mixed-integer linear programming (MILP) is at least as hard as Integer linear programming (ILP), so this is already a theoretical justification for ILP being easier to solve. Both are NP-hard, but NP-hardness is often a rather blunt sword, especially when it comes to practical behaviour (see for example the enormous practical success of the Concorde solver for the NP-hard TSP problem). If you look at a more fine-grained classification, you also find that there are fixed-parameter tractable algorithms for ILP (which have a polynomial worst-case run time if certain input parameters of the ILP are fixed), such as the LLL algorithm, see https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz\_lattice\_basis\_reduction\_algorithm.

There are also many empirically successful algorithms that are used in modern MILP solvers (such as SCIP) that get stronger the more integer variables you have.
> 0 votes

# Answer
With usual linear programming, you can find an optimal solution in a reasonably straightforward way. Any variable that has a different condition attached to it adds difficulty. So usually it’s the number of integer variables that add complications. Integer variables with strong restrictions may be easier to remove completely.

(Other restrictions: x might be restricted to x= 0 or x\>= 20, for example. )
> 0 votes

---
Tags: reference-request, time-complexity, integer-programming
---


# Question
Title: Are Nondeterministic Finite Automata not allowed 'sink-states'?
By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are against the rules of a NFSA/NFA or should not be allowed. My teacher said they are not allowed in a NFA/NFSA, but even if you have a 'sink state' in a NFA/NFSA I can see the diagram working and meeting the conditions. Can someone please clarify about this.

# Answer
Well, your teacher is wrong. In fact, we have a term for finite automata which the *always* have a transition for each symbol: they are "complete". You could not have complete DFAs or NFAs which accept all regular languages if you did not have "sink states", as you call them.

(By the way, I don't think there's a standard term for states like this, by the way, but I like "sink state".)

A string is accepted by a NFA if there is some path that ends in an accepting state, even if there is a path for the same string which ends up in a "sink state". By the way, it's not a "state we don't get out of" in the sense that we loop forever, because the *input* to a DFA or NFA is finite.

Now of course these states are *inefficient*. If you're writing a lexical analyser, for example, you don't want to consume the rest of an input program if a lexical syntax error is detectable early. But there's no theoretical problem with them.

It's also worth noting that NFA and DFA construction algorithms based on Brzozowski derivatives often naturally generate these sink states. See, for example, figure 2 in this tech report. Rather than detect them directly (which isn't difficult), you can remove these states with DFA minimisation if you were going to perform that step anyway. In fact, you can *add* a known sink state with no incoming transitions $q\_\mathrm{sink}$ to the non-minimised DFA, perform minimisation, and then any state merged with $q\_\mathrm{sink}$ must also be a sink state and can be safely removed.
> 1 votes

---
Tags: finite-automata, regular-expressions, nondeterminism, simulation
---


# Question
Title: Examples of cryptographic methods using outside randomness
Most cryptographic protocols like pseudorandom number generators run only on "internal" information: that is you set a seed and the next state is a function of its previous state etc.. I am wondering if there are any examples of cryptographic protocols that make use of "external" randomness or information, which is assumed to be known by an adversary? For example is there a PRNG or block cipher that has some "injection step" where it pulls in some public source of information to assist in the encryption?

The only example I can come up with is an IV for AES.

# Answer
> 1 votes
A salt or IV or nonce or public key all meet your requirements.

---
Tags: cryptography, pseudo-random-generators
---


# Question
Title: $L_p$ contains all binary strings whose value as binary number is prime. What are those values?
Context-: https://math.stackexchange.com/questions/1600257/determining-if-a-binary-string-represents-a-prime-integer

Confused text-:

> The problem of testing primality can be expressed by the language LP consisting of all binary strings whose values as a binary number is prime. That is, given a string of 0's and 1's, say "yes" if the string is the binary representation of a prime and say "no" if not. For some strings, this decision is easy. For instance, 0011101 cannot be the representation of a prime, for the simple reason that every integer except 0 has a binary representation that begins with 1. However, it is less obvious whether the string 11101 belongs to LP, so any solution to this problem will have to use significant computational resources of some kind: time and/or space, for example.

I didn't understand why 0011101 can't be representation of prime.

# Answer
The concept of prime is the usual one (a non-unit positive integer is prime if and only if it has no positive integer divisors except for $1$ and itself).

The author is probably just trying to say that, in general, deciding whether a given binary number is prime is a non-trivial task. However, you might be able to easily tell that **some** binary numbers cannot possibly be prime (for example any binary number that ends with $0$ and is not $10$).

I don't really agree with the provided explanation though. $0011101$ is a valid binary representation of the decimal number $29$, just like $029$ is a valid alternative decimal representation of the decimal number $29$. In a positional number system adding leading zeroes to a number does not change its value.

Perhaps the author has previously restricted him/herself to binary representations whose most significant bit is $1$ (except for the number $0$)?
> 1 votes

# Answer
I got the answer. I don't know which rule is that, but every binary number except 0 starts with 1. So We are starting 0011101 with 0, so it is not valid binary representation hence not binary prime. But it is hard to decide if 11101 is prime binary string or not as it needs to be processed using some algorithms.
> 1 votes

---
Tags: primes
---


title: Huffman Coding as optimal

text:
# Question
Title: Huffman Coding as optimal
In our lecture, the Huffman coding was described as optimal. Optimal with regard to the minimum information content. When asked, the professor explained to me that the length of a fixed code word should be minimal. I have now looked up on the internet what the common information is, this characterises the code as minimal with regard to the average codeword length. I therefore wanted to ask how one can imagine the connection between these two characterisations.

# Answer
> 3 votes
Given a probability distribution $\mu$ on a (usually) finite set $X$ and an alphabet $\Sigma$, a *prefix code* consists of an assignment of a word $c(x)$ over $\Sigma$ for each $x \in X$, such that no $c(x)$ is a prefix of $c(y)$ for $x \neq y$. The *average codeword length* is $$ \mathop{\mathbb{E}}\limits\_{x \sim \mu} |c(x)|. $$ A *minimum redundancy code* is a code which minimizes the average codeword length.

Huffman's algorithm is a particular algorithm which is guaranteed to produce a minimum redundancy code. Huffman's algorithm makes some arbitrary choices along the way, and consequently there are many codes which it can produce (for example, we could change the meaning of $0$ and $1$). Each such code is called a *Huffman code* for $\mu$. Gallager showed in his classic paper Variations on a Theme by Huffman that not every minimum redundancy code is a Huffman code, since Huffman codes satisfy some additional properties which are not satisfied by all minimum redundancy codes.

Minimizing the length of a fixed codeword is easy — we can always find some code in which it has length 1. Similarly, minimizing the length of the longest codeword is easy — the answer is always $\lceil \log\_{|\Sigma|} X \rceil$. Sometimes we are interesting in minimizing the average codeword length *subject to* the longest codeword being at most some length; this cannot be solved using Huffman's algorithm.

# Answer
> 0 votes
Huffman coding is optimal if you have a sequence of symbols, each appearing with a known probability, no correlation between the symbols, no limitation on the length of code words, and when you want each symbol to be translated to exactly one code word.

There is a variation of Huffman coding when symbol length is limited. (Limiting the code word length can make decoding faster, with very little increase of average codeword length). There is arithmetic coding which doesn't have a a fixed relation between code word and symbol and usually gives better correlation.

The most important technique is exploiting correlation between symbols. After you read "seq", what would you guess is the next letter? Most most likely a "q", most likely followed by another vowel. If you get probabilities for each letter, depending on the previous letter, and use a different Huffman code for each of these sets of probabilities, you can encode plain English text with three bits per letter. Of when you encode music, you can predict the next sample quite well from the previous ones, and only encode the difference between your prediction and the actual sample.

---
Tags: coding-theory, huffman-coding
---


# Question
Title: How to count the leaves of a tree without a outside function counter?
I got bombed in a interview because I was asked to write an algorithm which would count the leaves of a tree, I did this:

```
class TreeNode{
TreeNode[] children;
int value;

ctor(){
 children = new TreeNode[]();
}
}

class CountingClass{
int count;

ctor(){
count = 0;
}

void Count(TreeNode node)
{
 if(node.Children.Count > 0)
 {
   foreach(TreeNode item in node.Children)
   {
     Count(item);
   }
 }
 count++;
}

}

```

the interviewer appreciated demostrating my OOP approach but he wanted a solution contained in the function.

I got nervours and gave up after 20 minutes figuring it out. I was trying to pass an int as ref in the param but he said that is not what he was looking for either.

What is that thing I am missing here?

# Answer
You can count the leaves of the tree via a simple recursive function. Implement `count_leaves(TreeNode node)` as follows:

* If `node.children` is empty, return `1` as this node is a leaf itself
* Otherwise, return the sum of `count(child)` for all `child` in `node.children`

No external counters or complicated passing is needed.
> 0 votes

---
Tags: algorithms, recursion
---


title: What is "function of size of input"?

text:
# Question
Title: What is "function of size of input"?
Context-:

> Problems that can be solved by a computer using no more time than slowly growing function of size of input are called tractable. Polynomial functions are slowly growing functions. Functions that grow faster than any polynomial are deemed to grow too fast.

I googled about input size-:

For sorting arrays-: input size is array size.

For combinatorial problems-: Input size is number of objects

For graphs-: it is number of vertices and edges etc.

But I am still unable to understand what does a function of size of input really means?

# Answer
> 0 votes
"Function of the size of the input" when refering to time, means that the time an algorithm needs to run (that is, the algorithm's complexity) depends on the the number of elements of the input you give to the algorithm.

For example, the complexity of

```
Input: An array of integers of size n, named arr[n]

for (i = 0; i < 4; i++) return arr[3];

```

is $O(1)$ which is constant and does not depend on the value of $n$. On the other hand, the following algorithm

```
Input: An array of integers of size n, named arr[n]

for (i = 0; i < n; i++) print arr[i];

```

will enter the loop $n$ times, so the time the algorithm needs to run depends on the size of the array which is $n$ and its complexity is $O(n)$.

A "*slowly growing function*" that is mentioned in your excerpt is a function that is not very steep such as a logarithmic, linear or polynomial function. In the following image you can see some common functions that are fast growing and slowly growing with respect to the size of the input

# Answer
> 0 votes
When we talk about things like Big-O notation for time or space complexity, the result is a function. We say that when a function takes in a value, it is a function "of" that value. (In other words, mathematical functions written $f(t)$ are said to be functions of time or functions with respect to time.)

In this case, we are making a function that takes in the "size of input" -- as you said, the array size, the number of vertices, etc. That allows us to create a function to talk about the performance.

If we say that an algorithm is $O(n^2)$ (for example, Bubblesort), we took in the "size of input" $n$ and created the polynomial function $n^2$ to talk about how fast the function performs in relation to the input size $n$. (For those who don't know what $O(n^2)$ means, a quick analogy: if I multiply the number of records by 3, the resulting time it takes will be multiplied by 9, or $3^2$.) Since $n^2$ is a polynomial time, it is considered a slowly growing function in your definitions. (That being said, there are many much better sorting algorithms -- this is not an advertisement for Bubblesort!)

If we say that an algorithm is $O(2^n)$, this is still a function which makes use of the input size $n$... but since $2^n$ is an exponential function, it is considered to grow too fast to be useful according to your definitions above.

---
Tags: algorithms, automata
---


title: Subset Sum With Interval Integer Target

text:
# Question
Title: Subset Sum With Interval Integer Target
Define the subset sum with interval integer target problem (SSIITP) as follows:

**SSIITP Input**:

* A multiset $S = \\{a\_1, …, a\_p\\}$ of positive integers $a\_i$.
* An integer $T$.

**SSIITP Output**:

* True, if there is a subset $S’ \subseteq S$ such that $\sum\_{x \in S'} x \in T .. 2T$.
* False, otherwise.

Where $a .. b$, for two integers $a$ and $b$, is an integer interval including every integer between $a$ and $b$: $a, a+1, a+2, \dots, b-2, b-1, b$.

Is SSIITP NP-hard?

# Answer
> 2 votes
The problem is solvable in polynomial time and hence it is not $\mathsf{NP}$-hard (unless $\mathsf{P}=\mathsf{NP}$).

Here is a polynomial-time algorithm: assume without loss of generality that $T \ge 1$, that $a\_n \> 2T$, and that, for $i=1,\dots,n-1$, $a\_i \le a\_{i+1}$. Moreover, we can also assume that there is no $a\_j$ that satisfies $T \le a\_j \le 2T$ (since otherwise the answer is trivially "true").

Define $\sigma(j) = \sum\_{i=1}^j a\_i$. If there is any $j \in \\{1,\dots, n\\}$ that satisfies $T \le \sigma(j) \le 2T$ then $\\{a\_1, \dots, a\_j\\}$ is a feasible solution and the answer is "true".

On the contrary, if for every $j$ you have $\sigma(j) \< T$ or $\sigma(j)\>2T$, then you can immediately answer "false".

To see that this is indeed the case, define $j^\* \ge 1$ as the smallest value of $j$ that satisfies $\sigma(j)\>2T$ (notice that $j^\*$ always exists since $\sigma(n) \ge a\_n \> 2T$). We must simultaneously have $\sigma(j^\*-1) \< T$ and $\sigma(j^\*) \> 2T$, hence $a\_{j^\*} = \sigma(j^\*) - \sigma(j^\*-1) \> T$, which implies $a\_{j^\*} \> 2T$.

Clearly, for all $j \ge j^\*$ we have $a\_j \ge a\_{j^\*} \> 2T$ and hence no solution can possibly contain $a\_j$. However, the sum of the elements in any subset of $S \setminus \\{a\_{j^\*}, \dots, a\_n\\} = \\{a\_1, \dots, a\_{j^\*-1}\\}$ can be at most $\sigma(j^\*-1)\<T$. This shows that there is no feasible solution.

---
Tags: algorithms, complexity-theory, np-hard, polynomial-time, subset-sum
---


# Question
Title: What is the meaning of the statement "a sequence of n PUSH, POP and MULTIPOP opreations"
I am reading CLRS 3rd Ed, chapter 17.1 (Aggregate analysis pg453) and I came across this statement.

> Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack.

I am confused as in:

1. Do the push, pop, and multipop cumulatively add up to n operations.
(there is a total of n operations which consists of x pushes, y pops, and z multipops where x+y+z = n)
or
2. Are they talking about n push, n pop, and n multipop operations?
or
3. 1st operation(push, pop, Multipop), 2nd operation(push, pop, Multipop), ..., nth operation(push, pop, Multipop)

The question is does the statement from the book imply 1 or 2 or 3 or something I did not mention above. Thanks

# Answer
As phan801 commented, the first interpretation, a sequence of $n$ operations, each of which is either push or pop or multipop, is correct.

Either one of the other two interpretations might stand a small chance without surrounding context or with a very different context. However, had it been the intended meaning, "the phrase would probably have a different structure", such as, "n push operations, n pop operations, and n multipop operations" or "n operations, each being a push operation followed by a pop operation followed by a multipop operation".

A strong indication of the actual meaning comes from the introductory sentence of this section, "17.1 Aggregate analysis".

> In aggregate analysis, we show that for all $n$, **a sequence of $n$ operations** takes worst-case time $T(n)$ in total.

The interpretation 2 means three sequences of $n$ operations instead of "a sequence of $n$ operations".

The interpretation 3 could have been more possible if push-then-pop-then multipop is a reasonable combination. However, after push-then-pop, multipop operation will always be a non-operation, since the stack is assumed empty initially. There is nothing interesting to analyze for this interpretation. (Even if the stack is not empty initially, we would probably use "push-then-multipop" since we can combine a pop operation followed by a multipop operation into another multipop operation".) So this combination of three operations as one operation does not make much sense.
> 4 votes

---
Tags: algorithms, algorithm-analysis, amortized-analysis, stacks
---


# Question
Title: Nonlinear Knapsack with small integer weights
I have a problem that looks like a 0-1 Knapsack problem, except that the value of each item is a vector of length about 5, $v=(v\_1,\dots,v\_5)$. I want to maximize the product of components of the sum of the value vectors that are selected. In other words, if $S$ is the set of value vectors for the selected items, I want to maximize $$\prod\_{i=1}^5 \sum\_{v \in S} v\_i.$$

I know that there is a dynamic programming algorithm for that would be very fast for a normal Knapsack with my parameters (max weight 100, about 100 different items) but it isn't directly applicable to my problem, as in my case an optimal weight $w$ solution doesn't help find a weight $w+1$ solution.

Does a fast general algorithm for my problem exist? If not, could I preprocess the vectors in some slow way to make this fast? They are often nonzero in only one component.

# Answer
> 0 votes
There is an efficient algorithm for the special case where all value vectors have only a single non-zero coordinate, and where all items have weight 1.

Let $S\_j$ denote the set of value vectors that are nonzero only in the $j$th coordinate. Sort them by decreasing value. Let $t\_{j,w}$ denote the sum of the $j$th coordinates of the $w$ largest vectors in $S\_j$. Then your problem becomes to find $w=(w\_1,\dots,w\_5)$ such that

$$t\_{1,w\_1} \times \cdots \times t\_{5,w\_5}$$

is maximized, subject to $w\_1+\dots+w\_5 \le 100$. This can be solved using dynamic programming, with fewer than $5 \times 100^2$ steps of computation. In particular, for each $j,w$, we compute the maximum possible value of $t\_{1,w\_1} \times \dots \times t\_{j,w\_j}$ subject to $w\_1+\dots+w\_j \le w$. This can be done efficiently using dynamic programming, by solving the subproblems in order of increasing $j$. The solution for $j=5$ and $w=100$ then gives a solution to your original problem.

What if a few of the items have more than one non-zero coordinate? One approach would be to enumerate over all possible subsets of those vectors, then for each, identify which of the remaining vectors to pick using the above algorithm. If you have 10 items with more than one non-zero coordinate, this might require something like $2^{10} \times 5 \times 100^2$ steps of computation (probably fewer in practice). Perhaps someone else will find a better way to handle this case.

---
Tags: knapsack-problems
---


# Question
Title: no-input Turing Machine which accepts in k or fewer steps
Can we prove by induction that $A\_k$ is computable for every choice of $k \in \mathbb{N}$?

$A\_k$ is the set of descriptions of a no-input Turing Machine which accepts in $k$ or fewer steps.

# Answer
Well, just simulate $M$ for $k$ steps and see if it accepts or not

---

Or, if you want to prove by induction for some reason (there shouldn't be any reason to do this), then just run the machine for one step and then use the induction hypothesis.
> 0 votes

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


# Question
Title: True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)
Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph.

True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning tree resulting from BFS(s).

I assume that this one is True, and I think that because if $v$ is a leaf in every DFS(s), that means $v$ has no children on $G$ graph, but I struggle to prove it.

I'd like to get some help.

Thanks a lot!

# Answer
> 0 votes
Note that $v$ is a leaf in the spanning tree given by BFS($v$) if and only if $v$ is a leaf in $G$ (by definition of BFS).

That said, you should try with a graph $G$ that is a circular graph (or cycle graph), and any vertex $v=s$.

If you want an answer when $v \neq s$, then we can indeed show that if $v$ is a leaf in any DFS($s$), then $v$ is a leaf in $G$ (and so $v$ is a leaf in any BFS($s$)).

Indeed, suppose $v$ is not a leaf in $G$. Then it means that $v$ has two neighbors $x$ and $y$. If we suppose that $v$ is a leaf in any DFS($s$), then consider such a DFS where $x$ is explored before $y$. We have now two possibilities:

* $v$ is explored before $x$. Since $v\neq s$, that means that $v$ is not a leaf in the resulting spanning tree (because in this tree, $v$ has two neighbors);
* $v$ is explored after $x$. Then a graph traversal similar to this one until $x$, which then explores $v$ then $y$ then continues the DFS from $y$ would still be a DFS. In the resulting spanning tree, $v$ has two neighbors, so $v$ is not a leaf.

We proved that $v$ not a leaf in $G$ implies there exists a DFS($s$) where $v$ is not a leaf, or equivalently $v$ is a leaf in every DFS($s$) implies $v$ is a leaf in $G$ implies $v$ is a leaf in every DFS($s$).

---
Tags: algorithms, graphs, trees, search-algorithms
---


# Question
Title: Does reducing a NP Hard problem to a NP problem make that NP hard problem a NP Complete problem?
I was asked a question in my algorithms exam which had this as the core question after simplifying. I had written that it would be NP-Hard but I got it wrong my professor is saying that it would be NP-Complete.

Kindly help me resolve my doubt.

# Answer
A problem that is both NP hard and in NP is NP-complete.

On the other hand, after reading your question I'm not sure what you are asking.
> 3 votes

---
Tags: algorithms, np-complete, np-hard, np, decision-problem
---


# Question
Title: How to prove a problem is NOT NP-Complete?
Is there any general technique for proving a problem NOT being NP-Complete?

I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of any real solution, and just proved it was in P. Obviously this is not a real answer.

NP-Complete is defined as the set of problems which are in NP, and all the NP problems can be reduced to it. So any proof should contradict at least one of these two conditions. This specific problem, is indeed in P (and thus in NP). So I am stuck with proving that there is some problem in NP that can't be reduced to this problem. How on the earth can this be proven??

Here is the specific problem I was given on exam:

> Let $DNF$ be the set of strings in disjunctive normal form. Let $DNFSAT$ be the language of strings from $DNF$ that are satisfiable by some assignment of variables. Show whether or not $DNFSAT$ is in NP-Complete.

# Answer
Based on the comments, you seem to want an unconditional answer.

However, DNF-SAT is in L, by assigning variables to satisfy the first disjunct. Hence if it is NP-complete, then L=NP.

On the other hand, if L = NP then DNF-SAT is NP-complete under logspace reductions, trivially. (In fact, if L=NP then every problem in NP is NP-complete under logspace reductions.)

It follows that L=NP iff DNF-SAT is NP-complete under logspace reductions.

So you cannot currently make an unconditional statement that DNF-SAT is not NP-complete, as you seem to want to do. It is not necessary to assume P≠NP, but the answer does have to be conditional on something, and L≠NP is the weakest possible hypothesis that guarantees the desired result.
> 9 votes

# Answer
A problem $Q$ is NP-complete if it is both NP-*hard* and *in* NP. This means that you need to disprove one of these two.

1. Under the assumption that P $\neq$ NP, you can give a polynomial time algorithm solving $Q$. Rarer, under the assumption that graph isomorphism is not NP-hard, you can show that $Q$ is polytime reducible to graph isomorphism.
2. You show that $Q$ is not in NP. This is harder, and you must usually use other assumptions, like non-collapse of polynomial hierarchy, that NP $\neq$ coNP or show that it is hard for some other class higher than NP, e.g. by showing that it is NEXPTIME-hard.

Usually, the answer is to give a polynomial time algorithm, which would be the simplest for DNF-SAT, but this relies on the hypothesis that P $\neq$ NP. However, proving that DNF-SAT is not NP-complete without any assumptions implies, as Shaull points out, proving that P $\neq$ NP, so that is somewhat trickier.
> 19 votes

# Answer
By the nondeterministic time hierarchy, you could show that the problem is $\mathsf {NEXP}$-hard; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is *in* $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.
> 12 votes

# Answer
I believe what the lecturer really wants is that you could distinguish problems that are in P from problems that are NP-complete in the meaning given language can you build an efficient algorithm ? if yes then it is suspected not to be NP-complete because we dont think that languages in P is NP-complete ! otherwise you still have to prove that the problem is NP-hard !

note that there exists some problems that we dont know there status such as graph isomorphism,factoring given number,... we think that these problems are not NP-complete but no one could prove that ! specifically we have evidences that graph isomorphism is not NP-complete! other problem is the unique game conjuncture that we suspect that unique game is NP-complete but no proof exists! so the approach you have describe is not helpful!
> 2 votes

# Answer
If you showed that the problem is in P, then you can wait a few hundred years until someone finally proves that P ≠ NP and then it is proven not NP-complete.

Or you can just say "this problem is in P, therefore it is not NP-complete unless P = NP".
> 1 votes

# Answer
As is the case with all proofs, there is no formula for proving a statement, you have to do some intelligent guesswork, trial and error and hopefully you'll be able to prove what you are trying to prove. To prove a problem is NOT NP-Complete, negate the definition (DeMorgran Law), that is to say prove the problem NOT in NP or prove the problem NOT NP-Hard.
> -1 votes

---
Tags: complexity-theory, np-complete, proof-techniques
---


# Question
Title: A query regarding Complexity class BPP and NP
It is known that:

* $\Sigma\_2^P \subseteq \Delta\_3^P$ i.e. $NP^{NP} \subseteq \Delta\_3^P$.
* $BPP^{NP} \subseteq \Delta\_3^P$

If $\Sigma\_2^P = PSPACE =\> BPP^{NP} \subseteq NP^{NP}$

Doesn't that imply: $\Sigma\_2^P = PSPACE =\> BPP \subseteq NP$?

Am I missing something?

# Answer
> 1 votes
I have not verified your claims, but I will still try to answer.

In the general case, given a language $A$ and two complexity classes $\mathcal{C}\_1$ and $\mathcal{C}\_2$, the equality $\mathcal{C}\_1^A = \mathcal{C}\_2^A$ does not imply $\mathcal{C}\_1 = \mathcal{C}\_2$ (and same with inclusion).

In particular, Baker, Gill and Solovay proved in 1975 that there exists two languages $A$ and $B$ such that $\mathsf{P}^A=\mathsf{NP}^A$ and $\mathsf{P}^B\neq \mathsf{NP}^B$ (but it is still not known whether $\mathsf{P} =\mathsf{NP}$ or not). The idea is that giving and oracle to a non-determinist class let that class use this oracle non-deterministicaly, meaning potentially using it independently on every computing path, resulting in virtually calling the oracle an exponential number of times.

That means that $\mathsf{NP}^A \subseteq \mathsf{P}^A$ but it is not necessarily true that $\mathsf{NP}\subseteq \mathsf{P}$.

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


title: Need help with constructing a DFA

text:
# Question
Title: Need help with constructing a DFA
I am trying to construct the DFA that accepts the following language

$$ L\_2 := \left\\{ w \in \\{a,b\\}^\* \mid \\#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \right\\} $$

My solution is illustrated below. I feel like my current solution is incomplete/wrong.

# Answer
Here's an idea to construct such a DFA. Consider differently the two parts of the language: $L = L\_1 \cap L\_2$ where $L\_1 = \\{u\in\\{a,b\\}^\*\mid |u|\_a \equiv 0 \mod 3\\}$ and $L\_2 = \\{ubabbabv\mid u,v\in \\{a,b\\}^\*\\}$.

Note that I reworded "being divisible by $3$" into "being equal to $0$ modulo $3$". This will help to contruct the automaton.

For such an automaton, you need to keep track of the value of $|u|\_a \mod 3$. This can be done using only three states. An automaton recognizing $L\_1$ could be the following one, where $q\_i$ denotes the state where $|u|\_a \equiv i \mod 3$:

Now to build an automaton recognizing $L$, you can first build an automaton recognizing $L\_2$, then triple each states and completing transitions according to the value of $|u|\_a$.

Though, honestly, this is very tedious and annoying. The person giving this assignment could have chosen a short substring condition.
> 0 votes

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$
Text of the problem:

> Solve the following recurrence equation and prove it by applying the principle of induction: $T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \end{cases}$

after doing the recursion tree, I find that the complexity (if I'm not wrong) is $ \Theta (\log\_2 n) $

But I don't know how to do the induction step.

# Answer
> 2 votes
First of all note that $T(n)$ is indeed **not in** $\Theta(\log n)$, which makes the proof difficult.

You need to understand that if $T(n) = T(n/2) + n^2$, then $T(n) = \Omega(n^2)$, since it uses $n^2$ time in the first "iteration" or "level".

You have made a mistake when drawing the call tree. The call tree will look like this:

$$ n^2 + \left(\frac{n}{2}\right)^2 + \left(\frac{n}{4}\right)^2 + \left(\frac{n}{8}\right)^2 + \cdots + \left(\frac{n}{2^i}\right)^2$$

You are right that the "tree" (or path) terminates after $\log\_2(n)$ calls, so the summation should look like

$$\sum\_{i=1}^{\log\_2 n} \left( \frac{n}{2^i}\right)^2 = \sum\_{i=1}^{\log\_2 n} \left( \frac{n^2}{2^{2i}}\right) = n^2 \cdot \sum\_{i=1}^{\log\_2 n} \left( \frac{1}{2^{2i}}\right) = n^2 \cdot c, $$ for some constant $c$.

Now, since $T(1) = 3$, let's try to prove by induction that $T(n) \leq 3n^2$.

* Base case 1: $T(1) = 3 \leq 3\cdot 1^2 = 3$
* Base case 2: $T(2) = 3 \leq 3\cdot 2^2 = 12$
* Induction hypothesis: $T(n') \leq 3n^2$ for all $n' \< n$.
* Induction step: $T(n) = T(n/2) + n^2 \leq 3 \left(\frac{n}{2}\right)^2 + n^2 = 3/4 n^2 + n^2 \leq 3n^2$.

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


# Question
Title: Regular expression for words without two equal consecutive letters
I need to find a regular expression for the language over $\\{a,b,c\\}$ consisting of all words in which no two consecutive letters are the same. For example, $abacbabca$ is in the language, while $abbc$ isn't.

How do I do that? Any help would be greatly appreciated!

# Answer
> 1 votes
Let's start with a regular expression for all *non-empty* words over $\\{a,b\\}$ without $aa$ or $bb$. Such words must alternate $a$'s and $b$'s, making it easy to construct a regular expression for this language.

Now let's consider the language of all words over $\\{a,b,c\\}$ without $aa,bb,cc$. Such a word is either empty, or of the form $w\_1 c w\_2 c \cdots w\_{n-1} c w\_n$, where $w\_1,\ldots,w\_n$ are words over $\\{a,b\\}$ without $aa$ or $bb$, and furthermore $w\_2,\ldots,w\_{n-1}$ are non-empty. Using this description, you can easily construct a regular expression for your language using the regular expression constructed in the preceding paragraph.

---
Tags: regular-expressions
---


# Question
Title: Find the class of the problem PP1 and PP2 using the information given below
Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be reduced to PP1 in polynomial time, then PP1 can be reduced to PP2, and PP2 can be reduced to another NP problem in polynomial time. Specify the PP1 and PP2 classes with clear justification?

This was the question asked in one of my algorithms exam. I thought the answer for both the problems would be NP-hard, the logic which I thought of is that since all P1, P2, ...., Pn are NP problems and using the definition of NP-hard we can derive that PP1 is NP-Hard. After this for finding the class of PP2, since PP1 can be reduced to PP2. Therefore, we can say that PP2 is also NP-Hard.

The next bit of the question mentions about PP2 further being reducible to a NP problem but I don't feel that this information would be useful in finding the class of PP2. Let's assume the problem after reducing PP2 is some 'X' problem. This 'X' problem would be NP-Complete because it is NP-hard and NP as well.

My teacher says that PP1 is NP-Hard and PP2 is NP-Complete. According to him PP2 is NP- Complete because it is reduced to a NP problem but my doubt is how does this prove that PP2 is a NP problem. Please clarify my doubt.

# Answer
Considering it as the entire set of NP as you said according to this statement: *A problem X is NP-hard if every problem Y ∈NP reduces to X.*

Since P1, P2,...Pn can all be reduced to PP1, PP1 is a NP Hard Problem.

Now we have a)PP1 reducible to PP2 and b)PP2 reducible to some NP problem. According to this:

*A reduction from problem A to problem B is a polynomial-time algorithm that converts inputs to problem A into equivalent inputs to problem B. Equivalent means that both problem A and problem B must output the same YES or NO answer for the input and converted input.*

*– If B ∈ P, then A ∈ NP*

*– If B ∈ NP, then A ∈ NP*

*– If A is NP-hard, then B is NP-hard*

According to a) subpart since PP1 is NP-hard PP2 is also NP-hard

According to b) since PP2 is reducible to NP problem PP2 is also a NP problem. And as found in a) and b) PP2 is both NP-hard and NP so PP2 is NP complete

I got the italicized reference text from https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6\_046JS15\_lec16.pdf
> 2 votes

---
Tags: algorithms, np-complete, np-hard, np, decision-problem
---


# Question
Title: Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations
**Problem Description:** We have an array of $n$ positive integers and in one operation we have to choose two elements in the array and decrease them by $1$. (Elements on which we are performing this operation must be positive). How can we do this operation on this array repeatedly as many times as possible?
*\[Problem taken from here\]*

**Greedy Algorithm:** We repeatedly choose two largest elements in the array and decrement them by $1$.
The final array will have all elements equal to zero (`[0,0,.....,0]`) or will have exactly one non-zero element (`[0,0,...,0,x,0,...,0]`, where `x` is positive integer).

Example: `Array = [1,2,3,4]`;

* `int operations = 0;`
* Picking indices (0-indexed) `2` and `3` and subtracting $1$.
So now Array becomes `[1,2,2,3]`
`operations = 0+1 = 1;`
* Picking indices 2,3 | Array = `[1,2,1,2]`, `operations = 1+1 = 2 ;`
* Picking indices 1,3 | Array = `[1,1,1,1]`, `operations = 2+1 = 3 ;`
* Picking indices 0,1 | Array = `[0,0,1,1]`, `operations = 3+1 = 4 ;`
* Picking indices 2,3 | Array = `[0,0,0,0]`, `operations = 4+1 = 5 ;`

Argument is

* if `(Array[j] == Largest element) >= (Sum of Array[i] for all i != j)`,
then `max_operation = (sum of Array[i] for all i != j)`.
* else
`new_Sum = ∑Array[i]; 1<=i<=n` ;
`max_operations = (Integer)(new_sum/2)`;

---

**Confusion:** I am not able to understand why this algorithm works. How can I prove this algorithm for `else` case that `max_operations = (Integer)(new_sum/2)`. What is the correct proof for this greedy algorithm?

---

# Answer
> 2 votes
The goal is to make sure the one remaining element is as small as possible (if there is one). So as long as you reduce the 2 largest elements every step you will get to the lowest remaining element possible?

I'm not sure more than this is necessary to "prove" it.

# Answer
> 2 votes
Once we have played with the operations for a few times, we will soon realize that too large an element may not be able to pair with all other elements. So, while the end goal is to perform as many operations as possible, the immediate goal in each step could be reducing the largest element. Furthermore, we would like to reduce the next largest element as well, since it might become the largest element later. That is how we may find the greedy algorithm described in the question, which picks the two largest element in each step.

The question is how we can prove rigorously that greedy algorithm does work.

---

At each point of time when the algorithm is running,

* let $b$ be the biggest value of all elements, or 0 if there is no elements.
* let $r$ be the sum of all (non-zero) elements except one element that is equal to $b$ , or 0 if there is only one non-zero element.

### Case I, $b\>r+1$ initially (Easier Case)

Suppose $b$ is $a\_i$ for some $i$ initially. Every operation must include an element other than $a\_i$. The sum of all elements other than $a\_i$ is $r$ initially. So the most operations possible is (the initial) $r$.

Any algorithm that always pair $a\_i$ with another element will perform (the initial) $r$ operations. In particular, the greedy algorithm will perform the most operations.

### Case II, $b\le r+1$ initially

**Claim.** During a run of the greedy algorithm, it is always true that $b\le r+1$.

Intuitively, the claim makes sense since each operation will reduce the two largest elements. Instead of reading the short proof below, it is probably faster for you to prove the claim is true by yourself.

**Proof**. Suppose $b\le r+1$ at some step. The greedy algorithm will reduce the two largest elements (so we have $r\>0 $). We will show that $b\le r+1$ still hold after the operation.

* If the largest element is unique, then both $b$ and $r$ will be reduced by $1$. $b\le r+1$ after the operation.
* Otherwise, there are at least two elements of the biggest value. WLOG, let them be $b\_1$ and $b\_2$, which will be reduced. After the operation, either $b\_1-1$ or $b\_2-1$ is a summand of $r$ while $b$ is as most as big as $b\_1$. So $b\le r+1$ after the operation. $\checkmark$.

Consider a greedy run. When the run stops, $r$ must be 0; Otherwise, there are at least two nonzero elements, which means another operation can be made. Thanks to the claim, $b$ must be either $0$ or $1$. So the sum of all elements at the end, i.e., $b+r$ is

* either $0$, which is, of course, the least possible,
* or $1$, which is also the least possible, since the the sum of all elements was odd initially and has been staying odd all the time.

Since each operation reduces the sum of all elements by $2$, the maximum number of operations corresponds to reducing the sum of all elements as much as possible. So the greedy algorithm performs the maximum number of operations.

---

**Exercise**. Suppose each operation will reduce three elements (instead of two elements) by 1 each. Design a greedy algorithm to perform as many operations as possible. Prove it is correct.

---
Tags: algorithm-analysis, arrays, greedy-algorithms, correctness-proof, priority-queues
---


# Question
Title: Which maintainability metric has the strongest empirical evidence?
There are lots of code metrics that claim to measure maintainability, e.g. CK and Li & Henry metric suits. However, it seems elusive to me to find a meta-study that compares different metrics to decide their current empirical status.

In contrast, here's a quite brilliant such study about *fault prediction*: https://romisatriawahono.net/lecture/rm/survey/software%20engineering/Software%20Fault%20Defect%20Prediction/Radjenovic%20-%20Software%20fault%20prediction%20metrics%20-%202013.pdf

I'm looking for something similar for maintainability/changeability prediction.

To be clear, there are multiple meta-studies on maintainability metrics, but they don't seem to compare their evidence, more like listing what's been researched about and what not.

# Answer
This answer is based on the study Empirical evidence on the link between object-oriented measures and external quality attributes: a systematic literature review (PDF) by Ronald Jabangwe, Juurgen Borstler, Darja Smite, Claes Wohlin, 2014. They selected 99 papers to review in total.

"Vote counting" here means to get a point (or two) for each study that shows a strong connection between the specific metric and maintainability.

## Description of important metrics

WMC = Weighted method for classes.

> Weighted methods for Class (WMC) was originally proposed by C&K as the sum of all the complexities of the methods in the class .

LOC = Lines of code; todo: size of class, function, library, code-base?

RFC = Response for class

> This is the size of the Response set of a class. The Response set for a class is defined by C&K as 'a set of methods that can potentially be executed in response to a message received by an object of that class' .

CBO = Coupling between objects

> Coupling between objects (CBO) is a count of the number of classes that are coupled to a particular class i.e. where the methods of one class call the methods or access the variables of the other .

DIT = Depth of inheritance tree

> Depth of Inheritance Tree (DIT) is a count of the classes that a particular class inherits from .

NOC = Number of children

> Number of Children (NOC) is defined by C&K the number of immediate subclasses of a class .

## Quotes from the study

> There are insufficient numbers of studies on maintainability to draw conclusions. Nevertheless, Fig. 7 \[picture above\] shows that there is a potential link between maintainability, and measures that quantify complexity and cohesion properties.

> Results from our systematic review suggest that inheritance measures have a weak link with reliability and maintainability across studies, particularly the two inheritance measures DIT and NOC.

The study also notes that code metrics must be regarded in an organizational context:

> team structure and team strategy can vary across development settings, and studies show that such organizational characteristics have an impact on quality
> 1 votes

---
Tags: empirical-research, metrics
---


# Question
Title: Design an optimal algorithm that finds 2 array indices in a sorted array such that $A [i] + A [j] = k$
Text:

```
Given a non-descending ordered array A and an integer k, design an algorithm to find,
if any, the indices of a pair of elements whose sum is equal to k.
Discuss the complexity and the optimality of the solution.
Example
Input: 1, 3, 4, 5, 7  k=7  Output: 2,3 because A[2] + A[3] = 7

```

I tried to write the easiest algorithm to solve the problem and then try to improve it as much as possible,

Here's my first try:

```
function searchpair(A, k) : int
{
  for i <- 0 to length(A) do
    for j <- 0 to length(A) do
      if(A[i]+A[j] == k) do
        return (i,j)
    end
  end
}

```

The complexity of this algorithm is clearly $O(n^2)$, and it's not a good result, so I thought it was not necessary to check for elements larger than k (unless there are negative elements as well), and in this case, I transformed the previous algorithm into this:

```
function searchpair(A, k) : int
{
  n = length(A)
  while(A[n] > k) do
    n = n-1
  for i <- 0 to n do
    for j <- 0 to n do
      if(A[i]+A[j] == k) do
        return (i,j)
    end
  end
}

```

Depending on the array I could save a lot of operations, but the complexity is still an $O (n ^ 2)$. I've thought about applying a divide-and-conquer approach, but I can't think of any way to apply it, for example:

taking the array of the example: 1, 3, 4, 5, 7, and k = 7 A divide-and-conquer algorithm works

```
1) 1, 3, 4
  1) 1,3 NO
  2) 3,4  --> FOUND
2) 4, 5, 7
  1) 4, 5 NO
  2) 5, 7 NO

```

but assuming that k = 6, this approach doesn't work anymore, is it possible to obtain an algorithm of complexity less than $O (n ^ 2)$?

# Answer
> 3 votes
Given $i$, you could find an index $j$ verifying $i \leqslant j \< n$ such that $A\[i\] + A\[j\] = k$ using a binary search. This would result in a total complexity $\mathcal{O}(n\log n)$.

This is only possible if the array is sorted.

Note that it can even be done in linear time, with one index working from the left and one from the right. For $k=0$, with negative numbers allowed, this solution was given here: How to develop an O(N) algorithm solve the 2-sum problem?

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


# Question
Title: Difference between Lamport timestamps and Vector clocks
Lamport timestamps and vector clocks sound like almost the same thing. Both are used to determine the order of events in a distributed system. What are their key differences?

# Answer
**Summary:**

* Lamport timestamps and vector clocks are both logical clocks, and both provide a **total ordering of events consistent with causality**.
* Vector clocks allow you to determine if any two *arbitrarily selected* events are causally dependent or concurrent. Lamport timestamps cannot do this.
* Lamport timestamps are more compact. Vector clocks require overhead proportional to the number of nodes.

Both logical clocks allow one to totally order events in a way that is consistent with causality; this is true because every causal dependency results in an increased timestamp. For both clocks, you can assert that if A "happens before" B, then `Clock(A) < Clock(B)`.

Vector clocks take this a step further by allowing one to compare any two events and check to see if they are causally dependent or concurrent. Put another way, not only can you show that if A "happens before" B, then `VectorClock(A) < VectorClock(B)`, you can also assert the converse: if `VectorClock(A) < VectorClock(B)` then A "happened before" B.

Lamport timestamps employ a per-node counter to provide a causal ordering of events and an unique node ID to break ties and provide a total ordering, so the overhead of a Lamport timestamp does not vary with the number of nodes. Vector clocks employ per-node counters of every node, so the size of a vector clock is proportional to the number of nodes.

A great resource I found that more formally summarizes these concepts is a paper about Hybrid Logical Clocks, which can be found here: https://cse.buffalo.edu/tech-reports/2014-04.pdf Hybrid Logical Clocks are similar to Lamport timestamps, but they also provide a few other benefits.
> 14 votes

# Answer
Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ordering. Total ordering although more compact cannot tell whether two operations are concurrent or causally dependent.
> 7 votes

---
Tags: distributed-systems, synchronization
---


# Question
Title: How to write a non-ambiguous grammar for the syntax of lambda calculus?
I tried to write a non-ambiguous grammar for lambda calculus, but it does not really work. The recursive-descent parser is easy to write though. I googled but all results I collected so far are ambiguous, or rely on PEG which has a notion of explicit try-backtrack.

I'm now quite skeptical the non-ambiguous CFG does not actually exist. It must be written in Context-Sensitive Grammar to be non-ambiguous. Does it or does it not? Is it provable?

**edit**: Actually my original problem is a lambda calculus enhanced with a parallel evaluation operator `+`. So `expr + expr` is also `expr`. The ambiguous grammar is as follows:

```
E -> E E | E + E | n | x | lam x. E | (E)

```

My best approximation so far is:

```
E -> P
P -> P + A | A
A -> lam x. A | B
B -> B L | L
L -> x | n | (E)

```

However it does not accept `x lam y.y`.

# Answer
> 3 votes
You certainly don't need a context-sensitive grammar to solve this problem (and it probably wouldn't help you, either). In fact, you can solve it with the precedence declarations available in most standard parser-generating tools. For example, a simple bison grammar is:

```
%left '+'
%left LAMBDA_LEFT
%left APPLY "lambda" VALUE ID '('
%%
expr : expr '+' expr                            { $$ = make_para($1, $3); }
     | expr expr              %prec APPLY       { $$ = make_apply($1, $2); }
     | "lambda" ID '.' expr   %prec LAMBDA_LEFT { $$ = make_lambda($2, $4); }
     | '(' expr ')'                             { $$ = $2; }
     | ID                                       { $$ = make_ident($1); }
     | VALUE                                    { $$ = make_value($1); }

```

There are a few tricks in the above. Normally, precedence declarations are used in operator grammars, which are grammars in which no production has two consecutive non-terminals. This is not an operator precedence grammar because of the application production ($E\to E E$); in effect, the application "operator" is invisible. To compensate, I defined precedence levels for the four tokens in $\mathit{FIRST}(E)$, which act as a kind of stand-in for the missing application operator. This works, but it's a bit fragile; adding more features to the grammar must be done with a bit of care. In addition, I needed to use a pseudo-terminal (`APPLY`) to assign the application production to a precedence level, since Bison only automatically assigns productions which have at least one terminal symbol (using the last terminal symbol).

The key feature of that precedence declaration is the pseudo-terminal `LAMBDA_LEFT`, which is used to give the lambda production a left precedence distinct from its right precedence. If the expression grammar meets the requirements of an operator-precedence grammar, then the use of explicit left-precedence declarations can be used to produce deterministic LR parsers.

Bison/yacc-style precedence declarations do not introduce any extra power into the CFG formalism, which is evident from the way they are implemented. Precedence declarations are used only to resolve parsing conflicts; the parser generator produces a pushdown automaton for the grammar as written, and then uses the declarations to remove all but one transition from any state which has multiple transitions on the same terminal. (More accurately, the parser generator tries to remove conflicting transitions. Since precedence declarations are only used to resolve shift-reduce conflicts, not reduce-reduce conflicts, not all grammars can be resolved in this way.) The result is still a pushdown automaton, with the same states but fewer transitions, and is now deterministic. Thus, the language it accepts could be accepted by a deterministic context-free grammar; DPDAs and DCFGs accept the same set of languages.

Unfortunately, the usual proof of this correlation doesn't tell us how to construct the deterministic context-free grammar. Nonetheless, both mathematicians and parsing practitioners are generally satisfied with this outcome, the first group because "a solution exists" and the second group because there is a practical work-around which is not very difficult to apply. However, sometimes it is useful to actually produce the deterministic context-free grammar. And that is possible. It's even possible to do automatically, although the simplest automatic approach I know of produces a lot of unnecessary non-terminals. (See Annika Aasa, *Precedences in specifications and implementations of programming languages*. Theoretical Computer Science, 142(1):3–26, 1995. doi:10.1016/0304-3975(95)90680-J.)

In simple cases, like this one, the transformation can be done by hand. The problem is that cascading precedence grammars can't capture the fact that a lambda expression cannot be the left operand of an application (because the application should be inside the lambda), while an application cannot be the right operand of an application (because application is left-associative). This inversion of precedences is problematic in itself, but there is a further complication: the left operand of an application also cannot be an application whose right operand is a lambda. Or an application whose right operand is an application whose right operand is a lambda. And so on.

Consequently, we need two different non-terminals for application: one (`left-apply`) describes the subset of expressions which can be used as the left operand of an application, and the other describes the complete application syntax:

```
expr  : expr '+' apply            { $$ = make_para($1, $3); }
      | apply
apply : left-apply lambda         { $$ = make_apply($1, $2); }
      | lambda
      | left-apply
left-apply
      : left-apply atom           { $$ = make_apply($1, $2); }
      | atom
lambda: "lambda" ID '.' apply     { $$ = make_lambda($2, $4); }
atom  : '(' expr ')'              { $$ = $2; }
      | ID                        { $$ = make_ident($1); }
      | VALUE                     { $$ = make_value($1); }

```

---
Tags: formal-languages, automata, parsers
---


# Question
Title: Solve this integer program (problem: Travelling salesman problem)
How do one solve the following integer program? $$ \begin{align\*} \text{minimize} \quad &\sum\_{(i,j) \in E} d\_{ij} x\_{ij} \\ \text{subject to} \quad & \sum\_{j \in V} x\_{ij} = 2 \\;\\; \forall i \in V \\ &\sum\_{i,j \in S, i \neq j} x\_{ij} \leq |S|-1 \\;\\; \forall S \subset V, S \neq \emptyset \\ &x\_{ij} \in \\{0,1\\} \end{align\*} $$

# Answer
You solve *any* integer program by *any* algorithm for the problem. In general, integer programming is NP-hard, so there are naturally many approaches for the problem ranging from exact algorithms to various heuristics.

There are various tools that provide you with suitable methods, like Gurobi, CPLEX, MATLAB and Mathematica.

As a remark, if you only care about small instances (say at most 12 vertices), then you can also just try all possible tours and pick the shortest one easily. In that case, you can forget about an IP model. Such a model will be more useful when you can't afford to enumerate all possible solutions, but need something smarter to hopefully avoid some of this work.
> 1 votes

# Answer
Your problem is TSP on the graph given by the vertex set $V$, the edge set $E$, and the weights $d\_{ij}$.
> 0 votes

# Answer
Because you have exponentially many constraints, a natural approach is branch-and-cut. You can solve the LP relaxation actually in polynomial time by using a separation algorithm, i.e. by using cutting planes. For smaller problems the LP relaxation value will usually already coincide with that of the integer program. You can find the separation algorithm in the wonderful book "The Traveling Salesman Problem: A Computational Study". The Concorde solver is probably the easiest way to get a solution to your problem. If you want to implement something yourself, I would recommend to extend the TSP example from SCIP. https://www.scipopt.org/doc/html/TSP\_MAIN.php
> 0 votes

---
Tags: graphs, integer-programming, traveling-salesman
---


# Question
Title: Minimum spanning tree formulation as integer program
The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a constraint for every subset of vertices, so the number of constraints would be exponential.

That makes me wonder, is it is possible to write down the constraints for a IP corresponding to MST such that the number of constraints is polynomial in the number of vertices? Furthermore, if it is possible, does it hold that every problem in P can be written as a LP with at most polynomial number of constraints?

Thank you very much!

# Answer
> 1 votes
Yes, it's possible.

It's trivially possible that every problem in P can be reduced to LP in polynomial time, for uninteresting reasons: given an instance of the decision problem, the reduction solves the decision problem (in polynomial time), then either outputs a feasible LP instance or an infeasible LP instance (where these instances are hardcoded). I realize that's pretty uninteresting and probably not what you wanted.

# Answer
> 0 votes
There are IP formulations for MST with polynomially many constraints, see, e.g., "Optimal trees" by Magnati and Wolsey. For example, you can use the max-flow/min-cut theorem to find an equivalent formulation to the cut-based one that you mentioned: Replace each edge by two anti parallel arcs. Select one vertex as the root. Require that for each other vertex there is a unit flow from the root to this vertex. Very surprisingly, there are problems in P that you provably cannot formulate as an LP with polynomially many constraints. I would recommend the book "Integer programming" by Conforti et. al. for more Details.

---
Tags: algorithms, linear-programming, integer-programming, minimum-spanning-tree
---


# Question
Title: Function or signal as machine learning model output
I am new to machine learning. I've seen that machine learning models such as ANN or SVM can be used to predict scalar outputs taking scalar inputs.

I am trying to create a model that has a number of scalar inputs and outputs a function (the 'output signal' from now on), instead of scalar outputs. What model should I use for this? The output signal is a monotonically decreasing function, with its image ranging from 0 to 1 (always starting at 1 and settling at 0), and its domain from 0 up to a certain time when it settles to zero.

I thought perhaps I could either 'discretize' the output signal and take the discrete points as different scalar outputs. For example, take its value $y\_n$ at different times $t\_n$, and setting $y\_n$ as the outputs of the model.

Another way I thought that could perhaps work is applying a Fourier transform and do the same with the coefficients.

Is there a better way to do this? I will also have little amount of signals (200-400) to train my model, and I can add scalar inputs as needed.

Thank you! :)

# Answer
The approaches you mention are plausible. I will mention two more possibilities.

# Monotonic neural nets

You are imagining building a network $F$ that takes one input, the scalar inputs (call them $s$), and produces an output signal $F(s)$ that is itself a function.

An alternative is to build a network that takes two inputs: (1) your scalar inputs $s$, (2) a time $t$, and outputs the value of the function at time $t$. In other words, you build a network $F$ that evaluates the output signal at a given value $t$ to yield $F(s,t)$ -- this is the value of the output signal at time $t$.

There are methods in the literature for ensuring that the neural network is a monotonic function of $t$. See, e.g.,

Unconstrained Monotonic Neural Networks. Antoine Wehenkel, Gilles Louppe. NeurIPS 2019.

Application of the back propagation neural network algorithm with monotonicity constraints for two-group classification problems. Norman P. Archer, Shouhong Wang. Decision Sciences 24(1).

Counterexample-Guided Learning of Monotonic Neural Networks. Aishwarya Sivaraman, Golnoosh Farnadi, Todd Millstein, Guy Van den Broeck.

The easiest approach is to force all neural network weights to be non-negative (the bias terms can be negative). This is not the optimal method, but it is easy to implement. The others are complex enough to implement that they might not be worth it.

In your case, you'd have to adapt these methods so that $F$ is monotonic with respect to $t$ but not necessarily with respect to $s$. I think you might be able to do that with an architecture something like $F(s,t) = G(H(s),t)$ where $G$ is monotonic and $H$ is not.

# Isotonic regression

Another possibility might be to use your neural network to produce an output signal, as you described, and then use isotonic regression as a post-processing step to make the output signal monotonic.

A potential showstopper problem with this idea is that I'm not sure whether isotonic regression is differentiable, which is needed for doing end-to-end training of the entire process.
> 1 votes

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


# Question
Title: If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$
I have been given an assignment that I'm having a very hard time understanding.

The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (so if the language is regular, the complexity is $O(\log \log n)$). The computational model to be used is a Turing machine with one input and one work tape.

Here's an excerpt from a book called *Theory of computation* by Dexter C. Kozen that I will be using to prove the assumption (if it's not allowed to post such an excerpt here please let me know, I'll remove it and share just some parts there instead, I posted it whole as I consider all information there to be important).

I have read this excerpt several times and there are several parts that I wasn't able to grasp. If I understand this correctly, $N$ is equal to all possible configurations (a crossing sequence) for a *single* cell. On the other hand, $\sum^{m}\_{i=0} N^{i}$ is equal to crossing sequences on $m$ cells. So the thing I don't understand about this is why the $n/2$ first (or last) crossing sequences have to be distinct. I suppose I understand that you'd be able to cut a part of the input string if there were two identical crossing sequences on two positions, but I don't see why the number of required distinct crossing sequences equals $n/2$ and not some other number. For example, why do we partition $x$ into 2 parts and not 4 or some other number?

One other thing that I really don't understand is the very last equation, which says "Combining (1.3), (1.4) and (1.5) and taking logs, we get $S(n) \geq \Omega (\log \log n)$." I just don't understand how it's possible to come up with this equation by taking those three mentioned equations. The first step should be replacing $N$ in those equations, which gives me these two equations:

$\frac{n}{2} \leq \sum^{m}\_{i=0} (q \cdot S(n)\cdot d^{S(n)})^{i} = \frac{(q \cdot S(n)\cdot d^{S(n)})^{m+1}-1}{(q \cdot S(n)\cdot d^{S(n)})-1}$

$m \leq 2 \cdot (q \cdot S(n)\cdot d^{S(n)})$

I don't know how to combine these two equations and reach the desired equation that is $S(n) \geq \Omega (\log \log n)$. Thank you for any help in advance.

# Answer
> If I understand this correctly, $N$ is equal to all possible configurations (a crossing sequence) for a single cell.

That's not accurate: a crossing sequence is a *sequence* of configurations. We form the crossing sequence at position $i$ as follows: we trace the execution of the Turing machine, and whenever the head on the input tape crosses the $i$'th position (either toward position $i+1$ or toward position $i-1$), we concatenate the current configuration (state, contents of work tape, and head location on work tape) to the crossing sequence.

> On the other hand, $\sum\_{i=0}^m N^i$ is equal to crossing sequences on $m$ cells.

No. That's the number of crossing sequences of length at most $m$ at a *single* cell.

> I don't understand about this is why the $n/2$ first (or last) crossing sequences have to be distinct. I suppose I understand that you'd be able to cut a part of the input string if there were two identical crossing sequences on two positions, but I don't see why the number of required distinct crossing sequences equals $n/2$ and not some other number. For example, why do we partition $x$ into 2 parts and not 4 or some other number?

Suppose that the crossing sequence $c$ occurs at position $i$. Then the crossing sequences at positions $1,\ldots,i$ are all distinct: if the crossing sequences at positions $j\<k\leq i$ were identical, deleting the part of the input corresponding to positions $j+1,\ldots,k$ will result in a shorter input $x$ with the same crossing sequence $c$ (at position $i-(k-j)$. Similarly, the crossing sequences at positions $i,\ldots,n$ are all distinct. What we *cannot* say is that the crossing sequences at positions $1,\ldots,n$ are all distinct — the same argument doesn't work.

For the rest of the argument, we want to find as many distinct crossing sequences as possible. Therefore we take the maximum between $i$ (the number of crossing sequences corresponding to positions $1,ldots,i$) and $n-i+1$ (the number of crossing sequences corresponding to positions $i,\ldots,n$), which is always at least $n/2$.

> One other thing that I really don't understand is the very last equation, which says "Combining (1.3), (1.4) and (1.5) and taking logs, we get $S(n) \ge \Omega(\log\log n)$."

The equations in question state \begin{align} N &= qS(n)d^{S(n)} \\ \frac{n}{2} &\le \frac{N^{m+1}-1}{N-1} \\ m &\le 2N \end{align} The second equation simplifies to $$ n \leq 2N^{2m}. $$ Applying the third equation, $$ n \leq 2N^{4N}. $$ Taking logarithm, $$ \log n \leq 4N\log N + \log 2. $$ If $x \leq y\log y$ then $y = \Omega(x/\log x)$, and so $$ N = \Omega\left(\frac{\log n}{\log\log n}\right). $$ Substituting the value of $N$, $$ qS(n)d^{S(n)} = \Omega\left(\frac{\log n}{\log\log n}\right). $$ Taking another logarithm, $$ \log q + \log S(n) + S(n) \log d \geq \log \log n - O(1). $$ Since $\log q + \log S(n) = o(S(n))$, the left-hand side is $O(S(n))$, and so $$ S(n) = \Omega(\log\log n). $$
> 0 votes

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


# Question
Title: Time complexity when loop index is an exponent
For any $n$ and any $x$, if one implements a loop to calculate:

$$\sum\_{i=0}^n x^i$$

What is time complexity of said loop if we assume $x^i$ to have time complexity of $O(i)$?

What confuses me is the fact that in each iteration, $i$ will have a different value.

# Answer
With your assumption that computing $x^i$ has $O(i)$ complexity, the iteration with some $i$ will have complexity of $O(i)$ too (it simply adds $x^i$ to the current sum). So, complexity of each iteration can be taken $ci$ for some $c$. Total complexity of all iterations:

$ \sum\_{i=1}^{n} ci = cn(n+1)/2 $

which belongs to $O(n^2)$.

But for an efficient method, you can refer to the formula for sum of a geometric progression.
> 1 votes

---
Tags: time-complexity, runtime-analysis, loops
---


# Question
Title: What attributes are bound statically vs dynamically
I am having a hard time understanding the concept of what attributes get bound statically instead of dynamically. Below is code and from that code, what gets bound statically?

Here is an example (In C):

`static int count = getRand(0, 100); // getRand is a library`

# Answer
I'm not an expert of C/linkers/binding but I'm not sure to understand what you mean with the code you provided. Static binding versus dynamic binding is very different and it has nothing to do with the `static` keyword in C++. C has no dynamic binding "out of the box". See this question: https://stackoverflow.com/questions/16420628/what-are-static-and-dynamic-binding-in-c-strictly-c-not-c.

The static keyword in C makes the variable appear in the data segment of the executable. It will be global to all functions and will be accessed using a relative offset from RIP by default. It can also be called using an absolute address. For example, look at the following code:

```
class A{
    public:
    static int var;
};

int main(){
    A::var = 4;
    return 0;
}

```

It compiles to

```
main:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    $4, A::var(%rip)
    movl    $0, %eax
        popq    %rbp
        ret

```

In particular the line `$4, A::var(%rip)` accesses the variable A::var as an offset relative to RIP (the instruction pointer). In this case, I think only the symbol is kept because the address of A::var will be determined by the linker after compilation. On Linux, the ELF executable has a symbol table and it will have a symbol defined for A::var. I don't remember well the exact structure of ELF files so I can't tell how it is done exactly. Basically the symbol will be resolved by the linker to have the right offset from RIP.

Now, as to dynamic vs static binding, this is done via the `virtual` keyword in C++. It is really a matter of resolving symbols at runtime instead of at compile/link time (https://www.ibm.com/docs/en/i/7.3?topic=only-virtual-functions-c).

For example, on the link I provide you have this code (that I modified a bit):

```
class A {
   void f() {  }
};

class B: public A {
   void f() { }
};

void g(A& arg) {
   arg.f();
}

int main() {
   B x;
   g(x);
}

```

It compiles to (in Intel syntax):

```
A::f():
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        nop
        pop     rbp
        ret
g(A&):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        mov     rdi, rax
        call    A::f()
        nop
        leave
        ret
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        lea     rax, [rbp-1]
        mov     rdi, rax
        call    g(A&)
        mov     eax, 0
        leave
        ret

```

In the g() function the A::f() is called instead of B::f(). It is often not the desired behaviour because we inherited the class and would like that the compiler resolves that we want to call the inherited class override of the function. This is often called polymorphism in C++. We pass a reference to B in the g(A&) function and would like that the compiler still call the B::f() function by determining the type of the object referenced instead of using the type of the reference itself.

This cannot be done at compile time because the type of the reference passed to the g() function is not known yet. In static binding (without the `virtual` keyword on A::f()), the compiler simply assumes you are calling A::f() and blindly calls it.

If you add the `virtual` keyword on A::f():

```
class A {
    public:
        virtual void f() {  }
};

class B: public A {
    public:
        void f() { }
};

void g(A& arg) {
   arg.f();
}

int main() {
   B x;
   g(x);
}

```

The g() function changes to this:

```
g(A&):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        mov     rax, QWORD PTR [rax]
        mov     rdx, QWORD PTR [rax]
        mov     rax, QWORD PTR [rbp-8]
        mov     rdi, rax
        call    rdx
        nop
        leave
        ret

```

It will resolve the right function to call based on the type of the object referenced passed to it. It will find that using some tables somewhere. I apologize that I don't have more information on how it is done. Maybe someone else can help with that.

For info, I compile the code with https://godbolt.org if you want to have a look. For the rest of the stuff in the different functions I show see my answer here: What are pointers in low-level language like C
> 1 votes

---
Tags: variable-binding
---


title: Problems with simulating NFA with DFA

text:
# Question
Title: Problems with simulating NFA with DFA
I have this NFA:

I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when selecting a letter. However here the problem starts at {1}, where the dfa wouldn't have any connection for letter a and thus wouldn't be a proper DFA. How can I resolve this ?

# Answer
> 1 votes
You missed state $\emptyset$. The transition from state $1$ when character $a$ is read goes to $\emptyset$.

Since all transition from $\emptyset$ also go to $\emptyset$, you can also use the standard convention of omitting $\emptyset$ (and the transition for character $a$ from state $1$).

If a DFA has some missing transitions, it can always be completed by first adding a non-final state $q$, and then adding all missing transitions to $q$.

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Insertion Sort running time calculating using summtion
I was reading Introduction to algorithms, and stopped at the calculating the running time.

> For each $j = 2,3,..,n$ where $n = A.length$, we let $t\_j$ denote the number of times the while loop test in line $5$ is executed for that value of $j$ .

so I don't understand this statements with the sums and why the lines 6,7 it takes $t\_j-1$

# Answer
Fix a value of $j$, i.e., an iteration of the outer loop. If the condition of the while loop at line 5 is tested $t\_j$ times during this iteration (as per definition) then it must be false exactly once. In particular, it must be false in the last of the $t\_j$ tests, which causes the inner while loop to terminate.

As a consequence, each instruction in the body of the inner while loop is executed $t\_j - 1$ times. Summing the above expression over all considered values of $j$ (from $2$ to $n$) yields $\sum\_{i=2}^n (t\_j - 1)$.
> 1 votes

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


# Question
Title: Partition a graph into paths edge-disjoint of length 2
Given an undirected graph $G=(V,E)$. We want, if possible, to partition $G$ into paths of length 2 such that each pair of paths is edge-disjoint. I seek an algorithm with linear time $O(V+E)$ and a proof that shows us why the algorithm is correct.

My idea is that we can't partition any graph this way. But when we can, we can use DFS to partition our graph. But I can't formulate my idea.

# Answer
> 2 votes
We only need to consider the case in which the graph is connected and number of edges is even. We hence assume the above conditions once for all.

As a first observation, notice that if the graph is a star then it can easily be partitioned.

You can then show by induction that other graphs can also be partitioned. The induction is on the number $m$ of edges. If the graph has $0$ edges then the claim is trivial.

Consider an even value of $m\>0$. If $G$ is a star we are done. Otherwise, since graph has at least $2$ edges, and we can compute an arbitrary rooted spanning tree $T$. Let $u$ be the deepest leaf of $T$. If there are multiple choices for $u$ prefer a vertex that has at least one incident non-tree edge. Let $v$ be $u$'s parent, and let $w$ be $v$'s parent (if any).

* If $u$ has at least $2$ incident non-tree edges, then select and remove them.
* Otherwise, if $u$ has exactly $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.
* Otherwise, if $v$ has at least $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.
* In the only remaining case neither $u$ nor $v$ have incident non-tree edges. Moreover $w$ exists, since otherwise $v$ would be the root $T$, $T$ would have height $1$, and no child of $v$ would have any incident non-tree edge, implying that $T$ is a star. Select remove the path containing $(u,v)$ and $(v,w)$.

Ignore any vertex whose degree has been reduced to $0$. The remaining graph has $m-2 \ge 0$ edges, and the claim follows by invoking the induction hypothesis.

The above proof immediately leads to a liner-time algorithm once you observe that the spanning tree of the graph needs to be computed only once.

---
Tags: algorithms
---


# Question
Title: conversion of NFA to DFA (omitted states)
I've been given following task: *Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction)*

My solution to this:

Would like to ask for a verification here, especially for the part of this task which is enclosed in parentheses: ***omit unreachable states, if they appear during construction***. I do not fully understand that requirement and therefore I'm not sure if my solution is correct. Did I present some states which should be omitted on the graph/table? I feel like each state is reachable here and maybe task's description itself would have more sense for different example.

Kind regards,

# Answer
> 0 votes
The generic "theoretical" construction starting from a non-deterministic automaton with state set $Q$ introduces all subsets of $Q$ to be the states of the DFA. This wil introduce many states (subsets) that are nor reachable from the initial states. These states do not contribute to the language, so they can be omitted. From a theoretical point of view this is not relevant, in fact it might be harder to prove correctness if one applies these extra operations.

The "practical" approach (as you have applied here) is to start with the initial state, and to discover (in a breadth-first fashion) what are the states we reach by applying the transition function to sets we got previously.

So, I think you did what was asked. For instance, the state $123$ is not reachable.

Regarding the state $5$, you should realize it represents the empty set (of states) $\varnothing$.

---
Tags: automata, finite-automata
---


title: Is Max 3-SAT W[1]-hard?

text:
# Question
Title: Is Max 3-SAT W[1]-hard?
Is Max 3-SAT a W\[1\] hard problem, parmeterized by some parmeterize? I can't find the relevant literature.

I accept any parameterization.

# Answer
> 1 votes
The **W hierarchy** consists of classes of decision problems. The decision versions of MAX-SAT problems are just slightly disguised SAT problems. For example, to transform the decision problem "is there a variable assignment that satisfies *k* clauses?", add a unique variable to each CNF clause, then add a constraint that demands that at least *k* of the unique variables be set false. (All this can be done in polynomial time.) If the resulting SAT instance is satisfiable, the answer to the MAX-SAT problem is yes, otherwise the answer is no.

Since SAT Karp-reduces to CLIQUE and CLIQUE is W\[1\]-hard, SAT must be as well, and therefore so is the decision version of MAX-SAT.

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