# Question
Title: Why there is forward chaining inference engine (reasoner) for description logics only and not for other logics?
Reasoner is forward chaining inference engine (https://en.wikipedia.org/wiki/Semantic\_reasoner) as opposite to Prolog backward chaining SAT solver (for queries). Why there is reasoner for description logics and not for other logics?

# Answer
This question is a bit strange. I see it's based on the Wikipedia article, but that article is also a bit strange. I will try to clarify some concepts.

---

First, we have a *language* that can be used to make claims whose meaning are formally defined. Such a language may allow us to say, for example, that *if $x$ is a Person, then $x$ is a Human*, which can be done in first order logic as $\forall x (\neg\mathsf{Person}(x) \vee\mathsf{Human}(x))$, in a rule language like Datalog as $\mathsf{Person}(x) \rightarrow \mathsf{Human}(x)$, in description logics as $\mathsf{Person} \sqsubseteq \mathsf{Human}$ and so forth.

Second, we have *semantics*, which formally defines the meaning of claims in the language. One way in which the semantics of a language can be defined is using *model theory*, which essentially maps terms in the language to sets, elements, and relations between sets; for example, we can map the term $\mathsf{Person}$ to a (hypothetical) set $P$ and $\mathsf{Human}$ to a (hypothetical) set $H$, and define the above claims as formally meaning $P \subseteq H$. This gives rise to the notion of models, where for example, $P := \\{ \mathrm{Fred}, \mathrm{Jill} \\}$ and $H := \\{ \mathrm{Fred}, \mathrm{Jill}, \mathrm{Tom} \\}$ is a model satisfying a given set of formal claims (since $P \subseteq H$), while $P := \\{ \mathrm{Fred}, \mathrm{Tom} \\}$ and $H := \\{ \mathrm{Fred}, \mathrm{Jill} \\}$ is not a model (since $P \not\subseteq Q$). In turn, models give rise to entailment between sets of formal claims, where for example, given $\\{ \mathsf{Person}(\mathrm{Tom}), \mathsf{Person} \sqsubseteq \mathsf{Human} \\}$ (in whatever language), we know this entails $\\{ \mathsf{Human}(\mathrm{Tom}) \\}$ as any model of the former set of claims must be a model of the latter set of claims.

Third, we have *reasoning procedures* to decide entailment. One way in which this is done is to use inference rules. For example, we may derive a rule such as $(\mathsf{C} \sqsubseteq \mathsf{D} \wedge \mathsf{C}(x)) \rightarrow \mathsf{D}(x)$ to support reasoning with respect to the $\sqsubseteq$ operator in description logics. This rule may be applied for forward-chaining or backward-chaining. But there are many forms of reasoning procedures suitable for different types of languages; for example, for more expressive description logics, (a finite set of Horn) rules is not sufficient to guarantee complete reasoning, and so tableau-based methods are often used. Also one reasoning procedure can be useful for reasoning in different languages, where Datalog, for example, is natively based on rules.

---

Returning to the question:

> Reasoner is forward chaining inference engine (https://en.wikipedia.org/wiki/Semantic\_reasoner) as opposite to Prolog backward chaining SAT solver (for queries).

A "reasoner" can adopt multiple strategies, including, but not limited to, forward-chaining on rules. Engines that apply tableau-based methods, backward chaining, resolution, etc., are also "reasoners". (The article you base the question on never claims that reasoners are forward chaining rule engines, but mentions this as one strategy.)

> Why there is reasoner for description logics and not for other logics?

There are reasoners for other logics. For example, Vampire is a reasoner for first-order logic, XSB is a reasoner for Prolog, or just check here for a list of different reasoners for different languages.
> 2 votes

# Answer
Section 9.3.2 of the leading artificial intelligence textbook contains a sketch implementation of a forward chaining inference engine.
> 0 votes

---
Tags: logic, semantics, reasoning
---


# Question
Title: What is the most efficient algorithm to compute polynomial coefficients from its roots?
Given $n$ roots, $x\_1, x\_2, \dotsc, x\_n$, the corresponding monic polynomial is

$$y = (x-x\_1)(x-x\_2)\dotsm(x-x\_n) = \prod\_{i}^n (x - x\_i)$$

To get the coefficients, i.e., $y = \sum\_{i}^n a\_i x^i$, a straightforward expansion requires $O \left(n^2\right)$ steps.

Alternatively, if $x\_1, x\_2, \dotsc, x\_n$ are distinct, the problem is equivalent to polynomial interpolation with $n$ points: $(x\_1, 0), (x\_2, 0), \dotsc, (x\_n, 0)$. The fast polynomial interpolation algorithm can be run in $O \left( n \log^2(n) \right)$ time.

I want to ask whether there is any more efficient algorithm better than $O \left(n^2\right)$? Even if there are duplicated values among $\\{x\_i\\}$? If it helps, we can assume that the polynomial is over some prime finite field, i.e., $x\_i \in \mathbf{F}\_q$.

# Answer
This can be done in $O(n \log^2 n)$ time, even if the $x\_i$ have duplicates, via the following divide-and-conquer method.

First compute the coefficients of the polynomial $f\_0(x)=(x-x\_1) \cdots (x-x\_{n/2})$ (via a recursive call to this algorithm). Then compute the coefficients of the polynomial $f\_1(x)=(x-x\_{n/2+1})\cdots(x-x\_n)$. Next, compute the coefficients of $f(x)=f\_0(x)f\_1(x)$ using FFT-based polynomial multiplication.

This yields an algorithm whose running time satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n \log n).$$

The solution to this recurrence is $T(n) = O(n \log^2 n)$. This all works even if there are duplicates in the $x\_i$.

(You might also be interested in Multi-point evaluations of a polynomial mod p.)
> 25 votes

# Answer
You should also look at what you actually want to achieve. The coefficients can grow very quickly, meaning that evaluating the polynomial can have large rounding errors. Given the roots, you can evaluate the polynomial quite quickly without knowing the coefficients, and with high precision.
> 2 votes

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


# Question
Title: Why does the program counter increment before an instruction is completed?
During the fetch, decode, execute cycle, the Program Counter (PC) increments after the operand is copied from the Memory Data Register (MDR), and then carries on with the processing of the instruction.

Why does the PC increment in the middle of the cycle rather than at the end?

My only guess would be that it relates to jump instructions being incremented but I cannot find any sources on this.

# Answer
> 10 votes
The exact details of when (or even how) to increment the program counter are implementation specific details. There are however a few considerations that come into play across most computers.

1. After sending out the PC address, there is (almost) always a delay waiting for memory to respond. Thus there's often not a lot going on. One possible use of this "dead" time to do something useful, like incrementing the PC.
2. The next instruction is going to need the incremented value of the PC before it can proceed. If the processor does this at the end of the instruction, then the PC increment becomes part of the critical path for the next instruction.

The thing is, once this becomes part of the programming model for a processor, it is difficult to change the outward semantics of the PC increment. Consider processors with a PC relative addressing mode. If the value retrieved were to change from incremented to non-incremented, almost all the code would break. Thus the decisions made for early versions of a CPU must be honored in later (pipelined/overlapped/multi-way executing/multi-threaded/etc) versions of that CPU family.

Finally, and while silly sounding, most important; People are just used to having processors work that way. Some really great gains would be needed in order to ignore this bit of orthodoxy.

# Answer
> 2 votes
You don’t actually know that.

What you know from studying the processor’s instruction set is whether instructions using program counter relative addressing are defined to use the location of the instruction itself or the location of the next instruction. That’s something that is defined by the instruction set architecture and is something that can never be changed without breaking all existing applications. But when the processor changes the processor is an implementation detail, and you don’t know.

Actually a modern processor will likely only change the program counter inside the processor when instructions have been committed which may be a long time later.

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


# Question
Title: What is the time complexity of this nested loop code?
In this loop $j$ is dependent on $i$, and $j$ is executing like $n/2$, $n/2-1$, $n/2-2$, ... So does this sum up to $O(n\log n)$?

# Answer
We just have one comparison when $n$ is odd. So, the total complexity is (if we suppose $n$ is even, w.l.o.g.):

$$T(n) = \frac{n}{2} + (n + (n-2) + (n-4) + ... + 2) $$ $$= \frac{n}{2} + 2 \sum\_{i=1}^{\frac{n}{2}}i = \frac{n}{2} + 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \Theta(n^2)$$
> 2 votes

---
Tags: time-complexity
---


title: Which Tree traversal String is unique?

text:
# Question
Title: Which Tree traversal String is unique?
Assume we have a tree and we want to serialize it.

**Example:**

```
Tree

      1
     / \
    3   2
   / \ / \
  5  N N  N
 / \
N   N

```

can result as:

```
"1,3,5,N,N,N,2,N,N", // Pre Order serialization;
"N,5,N,3,N,1,N,2,N", // In Order serialization;
"N,N,5,N,3,N,N,2,1", // Post Order serialization

```

I would like to know, which one of these three serializations is unique for all trees and why ?

# Answer
> 4 votes
**Preorder traversal:**

This traversals always yield unique binary trees. For a proof, please check why recording non-existent children in the pre-order traversal will differentiate different binary trees?.

For instance consider traversal sequence $6,5,N,N,5,3,N,N,2,N,N$.

We can proceed as follow to construct binary tree.

> 1. First symbol is always root of tree.

Root will always be identified uniquely.

> 2. Try to parse remaining part of input recursively(This will be our left sub-tree). When one sub-tree is parsed return.

Here this left sub-tree parsing will start with input $5,N,N,5,3,N,N,2,N,N$ and will return after input $5,3,N,N,2,N,N$ left to be processed.

> 3. Try to parse yet remaining part of input recursively(This will be our right sub-tree).

---

**Post-order traversal**: This is similar to pre-order.

---

**inorder traversal**: This does not always yield unique binary tree. Here is counterexample.

Consider preorder traversal $N,5,N,6,N,3,N,5,N,2,N$. And following two binary trees.

```
        6                    5
       /  \                /  \
      5    5              6    2
     / \  /  \           / \  / \
    N  N 3    2         5   3 N  N
        / \  / \       / \ / \
       N   N N  N     N  N N  N

```

---
Tags: trees, binary-trees, tree-traversal
---


title: Decoding bit streams using Hamming Code

text:
# Question
Title: Decoding bit streams using Hamming Code
I want to decode the following bit stream using Hamming code: **01110110**

Once using even parity and once odd parity. I will show my work. For even parity:

$p\_{1} \\; p\_{2} \\; 0 \\; p\_{3} \\; 1 \\; 1 \\; 1 \\; p\_{4} \\; 0 \\; 1 \\; \\; 1 \\; 0$

Now, we check:

$p\_{1}: p\_{1} \\; 0 \\; 1 \\; 1 \\; 0 \\; 1 $, since there is an odd number of 1's, $p\_{1}=1$

$p\_{2}: p\_{2} \\; 0 \\; 1 \\; 1 \\; 1 \\; 1 $, since there is an even number of 1's, $p\_{2}=0$

$p\_{4}: p\_{3} \\; 1 \\; 1 \\; 1 \\;0 $, since there is an odd number of 1's, $p\_{3}=1$

$p\_{8}: p\_{4} \\; 0 \\; 1 \\; 1 \\;0 $, since there is an even number of 1's, $p\_{4}=0$

so the following hamming code is $$1 \\; 0 \\; 0 \\; 1\\; 1 \\; 1 \\; 1 \\; 0 \\; 0 \\; 1 \\; \\; 1 \\; 0$$

As for odd, the parities will just be the opposite and the code will be

$$0\\; 1 \\; 0 \\; 0 \\; 1 \\; 1 \\; 1 \\; 1 \\; 0 \\; 1 \\; \\; 1 \\; 0$$

Can someone tell me if my work is correct? Because I am a bit confused and would appreciate the help.

# Answer
There are many equivalent Hamming codes depending on the ordering of parity and data bits. Assuming that:

* You are using the specific bit ordering described here: https://en.wikipedia.org/wiki/Hamming\_code#General\_algorithm
* By "even parity" you mean that the parity bits are computed as the sum (modulo 2) of the corresponding groups of bits
* By "odd parity" you mean that the parity bits are computed as 1 minus the sum (modulo 2) of the corresponding groups of bits,

then yes, your simulation of the algorithm is correct.
> 1 votes

# Answer
I'm not really understanding some parts of your question, The Hamming algorithm is used to count the number of 1 bits of a binary number. The idea is to create a `mask = 1` and check for every of the 32 bits if `(mask & n) == 1`, then shift the mask to the left by one. If true is returned, it means that the binary representation of n has a 1 at that position, so increase the bit number. Here is an example:

```
int hamming(int n) {
        int bits = 0, mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) bits++;
            mask <<= 1; //shift left by one
        }
        return bits;
    }

```
> -1 votes

---
Tags: hamming-code
---


# Question
Title: Does assembly language get translated to binary code? If so, is assembly language portable across machines?
I've tried to find the answer through Google but I've come across conflicting uses of terminology, so I just wanted to be absolutely clear.

Here is my understanding: High level code written in a high level language (C I think is one of the lowest-level high level languages) gets translated to assembly code by that language's compiler.

That assembly code then gets translated to machine code (aka binary code aka hexadecimal code) by something (not sure what does this translation).

Does that mean that assembly code, but not machine code, is portable across computers? Or is assembly also not portable, and the only thing portable is code written in a high level language?

# Answer
> 5 votes
Assembler code describes instructions for one particular architecture. It is slightly helpful by allowing you to use human-readable names for instructions, names for memory addresses, doing some simple calculations etc. but it is totally useless to produce instructions for any other processor.

With heroic effort you could create a translator that produces code for a different architecture but nobody would thank you for it. The advantage of assembler code is that it lets you write code for things high level software isn’t designed for - like writing the code to boot a computer, handle interrupts, doing a process switch - and that kind of code is often very machine specific; it might not even be usable on a different computer with the same processor.

So yes, for any portability you need a high level language.

# Answer
> 1 votes
There are at least three different models for translating portable source code written in a high level language into machine code instructions that can be run on a particular type of computer and operating system(the "target platform"). Confusingly, the terms "compiler" and "compilation" are used in all of these models.

1. The output of the compiler can be a file of machine code instructions that can be loaded into memory and run directly by a specific operating system. In this model, some portion of the compiler (usually called the "back end") will be specific to a particular target platform. To compile source code to run on a different target platform will require a different version of the compiler. So the source code is portable, but the compiler is not.
2. The output of the compiler can be a file of source code in some lower level language, called an "intermediate representation". This intermediate representation can then be compiled to machine code that runs on a particular target platform. In this model, both source code and compiler are portable, but the high-level comiler is the first stage in a two-stage process. The reason for this two-stage approach is usually to take advantage an existing compiler infrastructure for the lower level language. For example, several high level languages create intermediate representations in C, since compilers already exist which can compile C for a wide range of target platforms.
3. The output of the compiler can be a file of "virtual code", which is run by a "virtual machine". The virtual machine is a program that runs on the target platform and interprets and executes the virtual code. A different version of the virtual machine is required for each target platform, but the virtual code and the compiler are portable. The advantage of this approach is that the programmer does not need to worry about the differences between target platforms. An example of this approach is Java, where Java code is compiled to Java "bytecode", which is then run on the target platform by a Java virtual machine. Another example is the reference implementation of Python, called CPython.

An assembler is essentially a compiler for a type of language called "assembly language" that is so low level that it is specific to a particular CPU. So when you program in an assembly language, not even the source code is portable (or, at best, it may be portable across a particular family of CPUs, such as x86 processors).

---
Tags: programming-languages, compilers, assembly
---


# Question
Title: Proving inequalities related to Dijkstra's algorithm
Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$.

Define $IN(v)$ as the set of in-neighbors of $v$.

Define $w(u,v)$ as the weight of the edge $(u,v)$.

I am asked to prove the following two inequalities to gain the correctness of Dijkstra's algorithm:

$$spdist(s,v)\leq min\_{u \in IN(v)} \\{spdist(s,u)+w(u,v)\\}$$

and

$$spdist(s,v)\geq min\_{u \in IN(v)} \\{spdist(s,u)+w(u,v)\\}$$

For the ≤ direction, it is quite obvious. Since we must go through either one of the edge $(u,v)$ to reach $v$, $spdist(s,v)$ is by definition smaller or equal to the RHS.

However, I am having trouble proving the ≥ direction. May I have some intuition of tips on how to prove the ≥ direction?

Thanks!

# Answer
> 2 votes
Consider a shortest path from $s$ to $v$. Let $u \in \mathrm{IN}(v)$ be the vertex preceding $u$ in this shortest path. The path from $s$ to $u$ is also a shortest path, and so $\mathit{spdist}(s,v) = \mathit{spdist}(s,u) + w(u,v)$.

---
Tags: graphs, shortest-path, correctness-proof
---


# Question
Title: given a weighted, directed graph. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}?
This is the 24.1-5 question in CLRS. I'm having a hard time understanding the questions and also how to solve it. δ(u,v) is defined as the shortest path weight from u to v if there exist a path from u to v.

Let G=(V,E) be a weighted, directed graph with weight function w:E→R. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}.

What I'm confusing about this question is what is δ∗(v) suppose to be. I also found the answer online but still don't really understand why it is like that. Since this is an exercise in the Bellman-Ford algorithm of CLRS. the answer said to change the RELAX operation of the algorithm. The RELAX operation in Bellman-Ford is what help achieve the shortest path weight after you run this V time for each edge in E.

the ORIGINAL-RELAX operation supposes to be like this:

```
RELAX(u, v, w)
if v.d > u.d + w(u,v)
   v.d = u.d + w(u,v)
   v.pi = u.pi

```

With v.d and u.d being the upper bound for the shortest path from source to u and v. v.pi is supposed to be its predecessor for the current upper bound.

The answer said to change the RELAX operation to this.

```
MOD-RELAX(u, v, w)
if v.d > min(w(u, v), w(u, v) + u.d)
   v.d = min(w(u, v), w(u, v) + u.d)
   v.pi = u.pi

```

I need some explaination to what the problem is asking for and why this answered it.

# Answer
# What is the question?

A vertex `v ∈ G.V` can have shortest paths from other vertices `u ∈ G.V - {v}`. What is the minimum of all these paths to `v`? This is `*(u, v)`. You have to calculate this minimum value for all the vertices

# Why the solution works?

To get to a vertex `v` you have 2 options:

1. Take minimum incoming edge from `u` to `v` i.e. `w(u, v)`
2. Get to `u` and then take the edge from `u` to `v` i.e. `u.d + w(u, v)`

You have to find the minimum of these 2 options. So `min(w(u, v), u.d + w(u, v))`

In either of the cases the `v.pi` will be `u`
> 1 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Deciding whether set of running times is infinite
I have a language $\mathrm{Count}(M)$, defined below, and a finite number $k$.

\begin{align} \mathrm{Count}(M)= \\{k \in \mathbb{N} \mid \text{there exists some input on which $M$ halts after exactly $k$ steps}\\}. \end{align}

I need to check whether the language $L$ is in RE, and whether it is in R. $$L= \\{ \langle M \rangle \mid \text{$\mathrm{Count}(M)$ is an infinite set}\\}.$$

My idea for a solution starts with: even though $L$ is an infinite language, it contains $\mathrm{Count}(M\_i)$ that halts eventually. Each $M$ in $L$ must halt, and $\mathrm{Count}(M)$ is infinite.

So, in order to prove that $L$ is in RE, can I simply say every $M$ in $L$ halts eventually?

# Answer
> 1 votes
Suppose $L \in \textrm{RE}$. Given a Turing machine $M$ you can construct another Turing machine $M'$ that takes an input $x$ and simulates $M$ on an empty input for at most $|x|$ steps.

If $M$ eventually halts, say after $c$ steps, $M'$ will always halt after at most $f(c)$ steps, (for some function $f$), regardless of the choice of $x$. This shows that $\textrm{Count}(M') \subseteq \\{ 1, \dots, f(c) \\}$ is a finite set.

If $M$ does not halt, then $M'$ will halt after simulating $|x|$ steps of $M$ for every choice of $x$. By picking different values of $x$ it is possible to build an infinite set of inputs such that each input results in a different running time of $M'$ (e.g, start with $x=$"1" and let $s$ be the number of steps taken by $M'$ on input $x$. The next value of $x$ will be a string of $s+1$ ones, so that $M'$ necessarily halts after some number $\ell$ of steps such that $\ell \ge s+1$. The next value of $x$ will have $\ell+1$ ones, and so on).

This shows that $\textrm{Count}(M')$ is an infinite set.

Therefore, since $L \in \textrm{RE}$ you have just found a way to accept all (and only) the Turing machines $M$ that do not halt on an empty input, showing that the complement of the halting problem is in $\textrm{RE}$. This is a contradiction as it would imply that the halting problem is in $\textrm{R}$.

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


# Question
Title: Complexity of Hamilton path in directed complete bipartite graphs
Finding a Hamiltonian path in a directed bipartite graph is NP-complete.

> **Problem 1** What is the complexity of the problem if we insist that the underlying graph of the digraph be complete bipartite? Is this known? (In other words, what is the complexity if the digraph is semicomplete bipartite, not just any bipartite digraph)

There is a variant of the problem we wish to consider

> **Problem 2** What is the complexity of the problem if the underlying graph is complete bipartite (that is, the digraph is semicomplete bipartite), and we specify the starting and ending vertex of the path?

# Answer
> 1 votes
These problems can be solved efficiently.

For Problem 2, both \[1\] and \[2\] prove that the problem is solvable in $O(n^{2.5} / \log n)$ time. That is, this is the variant of Hamiltonian path with specific start and end vertices.

For Problem 1, i.e., when the input graph is a semicomplete bipartite digraph, it appears (see \[3\]) that a Hamiltonian path is found in polynomial-time via bipartite matching.

There's a good amount of research on these type of problems on tournaments and other digraphs. You will find more general results by looking at papers that cite the ones I mentioned.

---

\[1\] J. Bang-Jensen, Y. Manoussakis, Weakly hamiltonian-connected vertices in bipartite tournaments, J. Combin. Theory B 63 (1995) 261–280.

\[2\] J. Bang-Jensen, G. Gutin, J. Huang, Weekly hamiltonian-connected ordinary multipartite tournaments, Discrete Math. 138 (1995) 63–74.

\[3\] J. Bang-Jensen, M. El Haddad, Y. Manoussakis, T. Przytycka, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Algorithmica 17 (1997) 67–87.

---
Tags: complexity-theory, graphs, time-complexity, np-complete
---


# Question
Title: Addition, multiplication, and apostrophe used to represent boolean algebra expressions?
I'm looking at a worksheet that expresses boolean logic expressions using multiplication, addition, and apostrophes; something I've never seen before.

I can make a guess that the apostrophe is equivalent to ¬ (except it's suffixed instead of prefixed). But I'm not sure what the addition and multiplication of the variables/propositional atoms would mean. Furthermore, I don't know how a boolean logic formula can "output" something other than just a truth value...

I can't seem to piece together with certainty the meaning of this representation. Could anyone take a look at the below example and maybe make a guess as to a translation of this representation to the more traditional ^, v, and ¬ symbols?

This arose in the context of digital logic in terms of logic gates and such on a CPU, if that makes a difference.

An alleged truth table of the above two expressions (the first row is filled in as an example):

# Answer
Usually $+$ means $\lor$, "multiplication" means $\land$, and $'$ means $\lnot$.
> 4 votes

---
Tags: logic, circuits, boolean-algebra
---


# Question
Title: Is program coding part of computer science?
As an amateur Bash/JavaScript scripter I was wondering if program coding ("writing source code") in general, and abstractless coding in particular (binary) is a concept of Computer Science or just an engineering implementation to ease doing the science and to automate processes.

Is program coding part of computer science?

# Answer
> 1 votes
I read a quote by Bjarne Stroustrup which said that computer science was the study of computers in the same way astronomy is the study of telescopes.

Computer science does indeed study coding in the abstract, particularly among the study of algorithms and data structures. Both of these fields are highly mathematical in nature, and seek to understand the idea of the abstract data type more fully. Of course, practical lessons can be learned and applied to various computers languages, systems, and applications, particularly answering questions like:

> 1. Can it be done?
> 2. What's the way to do it fastest with the least amount of memory?
> 3. How do I compare two different ways to code the same solution to a problem?

When studying algorithms, for instance, Big-O Notation is presented as a way at looking at the computational complexity of an algorithm? Will it finish in linear time? What about polynomial time? In fact, in computational comlexity theory a tremendously important question about what can be solved abstractly with coding is the question of NP-completeness.

When studying coding abstractly, often pseudocode is used to represent instructions as opposed to an implemented language. For example:

> Procedure DoIt()
> Loop from 1 to 100
> If num is divisible by 3
> Print that its divisible by 3
> If num is divisible by 5
> Print that its divisible by 5
> End

Other ways of studying algorithms and data structures include diagrams and graphs, often using tree data structures.

# Answer
> 1 votes
There has always been a very close connection between logic/mathematics and programming. Apart from the theory of data structures and algorithms, which provide a theoretical understanding of how to write good code, an important contribution of theory to everday programming is the invention of programming languages, basic computer architecture, and various specific features of programming langauges.

In fact, mathematicians and logicians essentially invented many things that you probably think were invented by engineers:

1. The idea of a general-purpose computer, of source code, and a general programming language were all invented by a mathematician, Alan Turing.
2. Modern CPU-centered computer architecture was invented by a mathematician John von Neumann, in cooperation with engineers Arthur Burks and Herman Goldstine.
3. Functional programming languages such as Haskell, OCaml, Scheme, Swift and (to some extent) Javascript, are extension of $\lambda$-calculus, which was invented by a logician Alonzo Church.
4. On of the first programming languages is FORTRAN, which stands for "(mathematical) **for**mula **trans**lator".

The connections between mathematics, logic and programming language remain strong, and are getting even stronger. Many features of modern programming langauge were developed by theoreticians: recursion, parametric polymorphism, algebraic datatypes, continuations, etc.

These phenomena are not isolated to programing. All basic sciences (physics, chemistry, biology, ...) have had a profound impact on everyday lives of humans, who have the luxury of taking the modern life for granted. Among these are highly skilled technical experts who have first-hand experience with engineering, but may not have had the chance to see the profound impact that the so-called "theory" has had on their fields of expertise.

---
Tags: terminology
---


# Question
Title: Is there a formal definition of "data structure"?
Data structure is a term that I've heard use I think only somewhat informally in software engineering. Is there a formal definition of it in CS?

# Answer
No, the term doesn't have a formal definition.

You might be interested in the notion of an abstract data type, which does have a formalization.
> 7 votes

---
Tags: data-structures
---


# Question
Title: Solving $T(n) = 2T(n/2) + T(n-1)/\log n$
I am interesting in the asymptotic rate of growth of the following recursion:

$$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$ with base case $T(1) = 1$.

I'm having trouble of solving this recurrence problem, it seems much more tricky than I initially thought, and I'm totally stuck after doing some unrolling. What is a good way to approach this question?

# Answer
> 3 votes
By comparison to the recurrence $T(n) = 2T(n/2)$, we see that $T(n) = \Omega(n)$. By comparison to the recurrence $T(n) = 2T(n/2) + n$, we see that actually $T(n) = \Omega(n\log n)$.

Now let us prove by induction that the other direction holds as well. I will interpret $T(n/2)$ as $T(\lfloor n/2 \rfloor)$. Suppose that $T(m) \leq Cm\log m$ for all $m \< n$. Then $$ T(n) \leq 2C\frac{n}{2}\log \frac{n}{2} + \frac{n\log n}{\log n} = Cn\log n + (1-C)n. $$ For $C \geq 1$, it follows that $T(n) \leq Cn\log n$.

It seems that we have proved that $T(n) = O(n\log n)$, but actually the base case of the induction doesn't hold. However, this shouldn't be too hard to fix (left to the reader).

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Solving recurrence relation with different rules for odd and even n
Assume $T(1) = 1$, and

1. $T(n) = 2T(n/2) + n^2$ for even $n$,
2. $T(n) = T(n − 1) + n$ for odd $n$.

I'm new of learning to solve recurrence problem, for 1, it seems we can apply Master Theorem directly and we got $a = 2$, $b = 2$, $d = 2$, therefore it's the case that $d \> \log\_b(a)$ and $T(n) = \Theta(n^2)$. But I'm unsure for the given $n$ is even, does this effect to our final result?

Because I noticed on the second one, for odd $n$ it changed our result from $\Theta(n^2)$ to $\Theta(n)$. Suppose we have $T(n) = T(n − 1) + n$, we can solve as summation from $0$ to $n$ such $0 + 1 + 2 + \dots + n - 1 + n = n(n+1)/2$, and hence $\Theta(n^2)$. However, if for odd $n$, I'm thinking this naively, we can just sum all odd numbers in the sequence so we have $1 + 3 + 5 + \dots + n = 2n-1$ and hence $\Theta(n)$. Is my assumption accurate?

# Answer
When $n$ is odd, the recurrence can be unrolled: $$ T(n) = T(n-1) + n = 2T\left(\frac{n-1}{2}\right) + (n-1)^2 + n. $$ In total, we always have $$ T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n^2). $$ Applying the master theorem, we conclude that $T(n) = \Theta(n^2)$.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Is log(n) equivalent to (log(n))^x for big-O analysis?
My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis.

ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$

From the left I would get $(n^2)(log(n))^2$ and from the right I would get $(n^2)log(n)$. According to my professor I can just say this function is $O(n^2log(n))$. However, I don't see how these functions grow in the same order. Looking at their graphs it would seem they are quite different.

# Answer
> 1 votes
$f(n)$ is not $O(n^2\log n)$

If we denote $f(n) = (n\log n+1)^2+(log n+1)(n^2+1)$ then: $$f(n) = n^2 \log^2n + 2n\log n + 1 + n^2\log n + n^2 + \log n + 1 \geq n^2log^2n$$

since all the other terms are obviously greater than 0. Therefore by definition $f(n) = \Omega (n^2log^2n)$. Which strictly means it cannot be bounded from above by anything asymptotically greater.

Note that it also holds that $f(n) \leq 10n^2log^2n$, so $f(n) = O(n^2log^2n)$ and also $\Theta$ of the same.

---
Tags: asymptotics, runtime-analysis, big-o-notation
---


title: $\beta$ reduction equational equality

text:
# Question
Title: $\beta$ reduction equational equality
In Categories, Types and Structures, authors talk about exponential objects in section 2.3.1.

> Let $C$ be a Cartesian category, and $a,b \in Ob\_C$. The exponent of $a$ and $b$ is an object $b^a$ together with a morphism $eval\_{alb}: b^a \times a\rightarrow b$ (evaluation map), and for every object $c$ an operation $\Lambda\_c : C\[c\times a,b\]\rightarrow C\[c, b^a\]$ such that for all morphisms $f: c\times a\rightarrow b$, $h:c\rightarrow b^a$, the following equation holds:
> $\beta. eval\_{a,b} \circ (\Lambda (f)\times id\_a )=f$
> $\eta. \Lambda\_c(eval\_{a,b}\circ(h\times id\_a))=h$

Can you please show me the steps to derive the last two equations?

# Answer
The following morphism and commuting morphisms explain why those two equations hold:

$h:c\rightarrow b^a$

commuting morphisms:

$eval: b\_a\times a\rightarrow b$
$f:c\times a\rightarrow b$
$h\times id: c\times a\rightarrow b^a\times a$
> 0 votes

---
Tags: category-theory
---


# Question
Title: Multiple Knapsack Problem with Set of Admissible Balls
We have $m$ bins and $n$ balls.

1. Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3.
2. Each ball $j=1,2,\ldots,n$ can be put into bin $i=1,2,\ldots,m$.
3. For each bin $i=1,2,\ldots,m$, there is a collection of sets $S\_i=\\{X\_1,X\_2,\ldots,X\_{k\_i}\\}$ for given $k\_i$ ($k\_i\geq0$ and $k\_i\leq\binom{n}{2}$). Each $X\_j\in S\_i$ is a 2-cardinality set and it represents the set of two balls that can be put into bin $i$. We can only choose at most one set from $S\_i$.

For example, for $m=2$ and $n=3$. Say we have $k\_1=0$ and $k\_2=2$ and $S\_1=\emptyset$. $S\_2=\\{\\{1,2\\},\\{2,3\\}\\}$. This means that:

1. Ball $1$, $2$ or $3$ can be each put into bin $1$ or bin $2$. This is always true (for all instances of the problem).
2. In bin $1$, we cannot put any set of two balls.
3. In bin $2$, we can put balls $1$ and $2$ or balls $2$ and $3$.

We want to assign the maximum number of balls into the bins. Is this easy or hard?

Since, we have the assumption that $|X\_j|=2$, I was thinking that maybe we can solve it in polynomial-time. I am trying to prove that it is easy by reducing it to maximum flow.

A problem similar to this one but more general was posted here Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?.

# Answer
> 2 votes
This is NP-hard by reduction from 3-dimensional matching (3DM): turn each triple $\\{a, b, c\\}$ into a valid pair $\\{a, b\\}$ of balls for bin $c$, and add a large number of balls that don't belong to any valid pairs (so that if they go in a bin, they must be the sole occupant). The optimal solution will then hold $k+m$ balls ($k$ bins with 2 balls each and $m-k$ bins with 1 ball each), where $k$ is the largest size of any 3DM for the original input.

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


# Question
Title: Big theta of function with multiple types of n
I have the following function:

$\displaystyle\frac{n \cdot 7^n+\frac{8}{n!}}{(n+7) \cdot 7^n}=\Theta(1)$

I don't how they come to this. What is the proper way to analyse a function to theta notation?

# Answer
> 5 votes
You can calculate the limit of the function for $n\to\infty$: \begin{align} \lim\_{n\to\infty}\frac{n\cdot7^n+\frac{8}{n!}}{(n+7)\cdot7^n}&=\lim\_{n\to\infty}\frac{n\cdot7^n}{(n+7)\cdot7^n}+\lim\_{n\to\infty}\frac{\frac{8}{n!}}{(n+7)\cdot7^n}\\ &=\lim\_{n\to\infty}\frac{n}{n+7}+\lim\_{n\to\infty}\frac{8}{(n+7)\cdot7^n\cdot n!}\\ &=1 + 0\\ &=\Theta(1) \end{align}

---
Tags: asymptotics
---


# Question
Title: A problem with the greedy approach to finding a maximal matching
Suppose I have an undirected graph with four vertices $a,b,c,d$ which are connected as in a simple path from $a$ to $d$, i.e. the edge set $\\{(a,b), (b,c), (c,d)\\}$. Then I have seen the following proposed as a greedy algorithm to find a maximal matching here (page 2, middle of the page)

```
Maximal Matching (G, V, E):
M = []
While (no more edges can be added)
     Select an edge which does not have any vertex in common with edges in M
     M.append(e)
end while
return M

```

It seems that this algorithm is entirely dependent on the order chosen for which edge is chosen first. For instance in my example if you choose edge $(b,c)$ first, then the you will have a matching that consists only of $(b,c)$.

Whereas if you choose $(a,b)$ as your starting edge, then the next edge chosen will be $(c,d)$ and you have a matching of cardinality 2.

Am I missing something, as this seems wrong? I have also seen this described as an algorithm for finding a maximal matching in the context of proving that the vertex cover approximation algorithm selects a vertex cover by choosing edges according to a maximal matching. Any insights appreciated.

# Answer
You're correct, you're not missing anything -- except that the algorithm is not wrong. The task is to choose a *maximal* matching, not a *maximum* matching. There may be many possible maximal matchings, many of which are not maximum matchings. It's the difference between a local optimum vs a global optimum.
> 14 votes

---
Tags: graphs, matching, vertex-cover
---


# Question
Title: Language to define perfectly a programming problem
# Is there any language, which can be used to define **all** programming problems **perfectly**?

By perfectly, I mean with these two properties:

* p is the problem.
* d is the definition in the language.
* P(d, p): "d is the definition of the problem p"

$$ \forall p\exists d(P(d, p)) $$ $$ \forall p\exists d1,d2((P(d1, p) \land P(d2, p)) \rightarrow (d1 \Leftrightarrow d2)) $$

**Example:** The simple problem to output the first N numbers, can be defined in many ways, for example in the english language. I want a language which restricts the number of definitions to **1** for **every** problem. In other words, no 2 distinct definitions can define the same problem, and every problem has a definition.

---

## 1. This language exists?

## 2. If such language does not exists, is it possible to create one?

# Answer
> 19 votes
This question is somewhat unclear to me; however, under one interpretation there is a result which indicates that the answer is **unsatisfyingly yes**: namely, the existence of **Friedberg numberings**. Roughly speaking, a Friedberg numbering is a programming language which is Turing complete but in which no two programs perform the same task.

*(More formally: a Friedberg numbering is a computable function $\varphi$ of two variables such that for each computable function $\psi$ of one variable there is exactly one $e\_\psi^\varphi$ such that $\lambda x.\varphi(e\_\psi^\varphi,x)\cong\lambda x.\psi(x)$.)*

A simple proof of the existence of such numberings was given by Kummer.

That said, it's easy to show that we can never "translate into" a Friedberg numbering, which renders the positive result above somewhat misleading at best: if $(\theta\_i)\_{i\in\mathbb{N}}$ is the usual numbering of computable functions of one variable and $\varphi$ is a Friedberg numbering, the map $$(\*)\_\varphi:\theta\_i\mapsto e\_{\theta\_i}^\varphi$$ is not computable. Essentially, what this means is that programming in the usual sense is impossible in the context of a Friedberg numbering: while every computable function has a corresponding program, there's no way to *find* it.

* To prove this, simply note that from the map $(\*)\_\varphi$ we can compute the set of indices for the never-defined function: let $c$ be the unique number such that $\lambda x.\varphi(c,x)$ is never defined, and to tell whether $\theta\_i$ is never defined just check whether $(\*)\_\varphi(i)=c$. *(Note that this can be improved: if we replace the never-defined function with the identity function, or more generally any partial computable function with infinite domain, the resulting set of indices is **strictly more complicated** than the halting problem - it has Turing degree $\bf 0''$. So in fact "translating into a Friedberg numbering" is really very impossible indeed.)*

This "impossibility of translation" is what breaks the "obvious" proof that Friedberg numberings are impossible. It also points the way to the general study of numberings, which is a fruitful area of study within computability theory. The numberings which are Turing complete in a "non-stupid" way are the **acceptable numberings**, which are also those which are maximal in a certain natural pre-ordering on numberings.

# Answer
> 1 votes
No, such a language cannot exist.

Programming can solve many different kinds of problems.

One particular kind of problem it can solve is computing a function from input values to output values. The program will read an input value and produce the output value defined for that input value by that function. For this type of problem, the problem definition is given by some sort of specification of the input-output function.

I think you will agree that we don't want to restrict ourselves to problems that only accept finitely many different input values. For instance, we want to be able to define the problem that takes an arbitrary integer and outputs its value squared. We can only do that if we allow any integer to be an input value.

Furthermore, we don't want to restrict ourselves in the kind of input-output function we can define.

A pretty fundamental result in computability theory says that for any language capable of describing all such functions, it is undecidable whether two descriptions of functions in that language describe the same function. Which directly answers your question.

What is more, it is undecidable even for heavily restricted classes of input-output functions. Consider, for instance, the set of functions with the following properties:

* All input values are strings from some given alphabet of at least two characters; for instance, strings built out of the characters `a` and `b`.
* All output values are either *yes* or *no*.
* The set of input values for which the output value is *yes* is always a context-free language.

No matter which language you design for describing these functions, deciding whether two descriptions describe the same function is undecidable, as equivalence of context-free languages is undecidable.

---
Tags: formal-languages, logic
---


# Question
Title: What's the maximum memory address space that the processor can access directly if it connected to a 16-bit memory?
The question is the following: 3. Given a hypothetical microprocessor which generates a 16-bit address (assume that the program counter and address registers are 16 bits wide) and has a 16 bit data bus. a) What is the maximum memory address space that the processor can access directly if it connected to a "16-bit memory"? b) What is the maximum memory address space that the processor can access directly if it is connected to an "8-bit memory"?

It feels like the answer to both would be 2^16, which is equivalent to 24KiB. It also feel natural to say that an 8-bit memory can tranfer 8 bits and a 16 bit memory can transfer 8 or 16 bit words.

But the problem is that the actual answer booklet says the following: In cases (a) and (b), the microprocessor will be able to access 2^16 = 64K bytes; the only difference is that with an 8-bit memory each access will transfer a byte, while with a 16-bit memory an access may transfer a byte or a 16-byte word.

So 1) 64K? Isn't the unit suppose to be KiB? I am very confused. 2) 16-byte word? Shouldn't it be a 16-bits word?

# Answer
I think there is a confusion here between the number of memory addresses and the total size of memory that can be addressed.

The microprocessor can access $2^{16} = 65536$ memory addresses, regardless of the size of data held at each memory address.

If each memory address holds one byte ($8$ bits) of data then the total memory size that can be addressed directly is $2^{16} \text{ bytes}$, which is $2^6 \text{ KiB} = 64 \text{ KiB}$.

On the other hand, if each memory address holds two bytes ($16$ bits) then the total memory size that can be addressed directly is $2 \times 2^6 \text{ KiB} = 128 \text{ KiB}$.

It also appears your text is using KB as an abbreviation for KiB, which is a common shorthand but not strictly correct.
> 2 votes

---
Tags: memory-access
---


title: Iterative vertex removal algorithm

text:
# Question
Title: Iterative vertex removal algorithm
Let $G=(V,E)$ be a graph, where $|V|=n$,$|E|=m$,$k=m/n$.

We consider the following algorithm:

> while (there exists $u ∈ V (G)$ such that $d\_G(u) \< k$) do
>
> $\quad G ← G − u$;

Prove that the resulting $G$ isn't null.

Implementing the algorithm is easy, but I can't find a way to prove it rigorously. k doesn't change over time.

# Answer
> 1 votes
After removing the first vertex, the new graph has $n' := n-1$ vertices and $m' := m-d\_G(u) \> m-k$ edges. Therefore $$ \frac{m'}{n'} \> \frac{m-k}{n-1} = k. $$ Continuing in this way, we see that at any point in time, the ratio between edges and vertices is always at least $k$. Any graph on $\ell$ vertices has a ratio of at most $\binom{\ell}{2}/\ell = \frac{\ell-1}{2}$, so the number of vertices always satisfies $\ell \geq 2k+1$. In other words, when the algorithm terminates, there will be at least $2k+1$ vertices left.

---
Tags: graphs
---


# Question
Title: Why doesn't 2-opt return an optimal solution?
To find a solution for the Traveling Salesman Problem (TSP), one way to go is an algorithm called 2-opt, which is explained below.

```
The 2-opt algorithm basically removes two edges
from the tour, and reconnects the two paths created.
This is often refered to as a 2-opt move. There is only
one way to reconnect the two paths so that we still
have a valid tour (figure 1).  We do this only if the
new tour will be shorter. Continue removing and re-
connecting the tour until no 2-opt improvements can
be found. The tour is now 2-optimal.

```

For me, this algorithm tries all possibilities for edge combinations, so it should return the best (optimal) solution, right? Wrong, because :

```
If we look at the tour as a permutation of all the
cities, a 2-opt move will result in reversing a segment
of the permutation.
Running the 2-opt heuristic will often result in a tour
with a length less than 5% above the Held-Karp bound.

```

My question is ; why does it not return the optimal solution? Does it not try all possible edge combinations? Can you give an example graph for which 2-opt doesn't give an optimal solution? I'm citing from here : https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf

# Answer
I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better.
> 6 votes

# Answer
In reality, 2-opt might actually give you the optimal solution in fact odds are good that it very often does. But, to prove this requires brute force NP-complete travelling salesman solution. So it might give you the best solution for a particular dataset but you can't know this is optimal rather than pareto-optimal without an NP-complete operation.
> 0 votes

---
Tags: heuristics, traveling-salesman
---


# Question
Title: Name for Turning DAG into redundant tree
I am looking for a term:

How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences in the tree?

The resulting tree will contain all edges and nodes from the original DAG and a number of nodes multiple times.

```
A -> B
|    |
v    v
C -> D

```

Will be turned into:

```
A -> B -> D
|
v
C
|
v
D

```

If you need clarifications, please ask.

# Answer
I am not aware of any standard name for that kind of tree. One of the wonderful things about language is that we can describe things we don't already have a name for; there are many more interesting concepts than there are pre-existing widely-recognized names. I recommend that, if you find in your writing you need a concise name for it, you choose a name that seems suitable to you, and define it before first use.
> 1 votes

---
Tags: trees, spanning-trees, dag
---


# Question
Title: Is there a way to access hard drives while computer sleeps?
Is there any way at all possible or possible with hardware (aside from a NAS) to access hard drives while the computer is in a low power mode such as sleep (aside from WOL)?

For example, can I log into a networked drive located on the computer and spin it up to access data without the computer coming out of low power mode?

# Answer
> 1 votes
Sure. It all depends on the architecture of the machine. For instance, if there is a co-processor that is awake and responds to the network requests by accessing the hard drive, that would be one way to accomplish it.

If you're asking about a specific product or technology, that is off-topic here. But conceptually, you can certainly build a computer that has this capability. Whether any individual computer does have that capability is a question about that specific product or technology.

---
Tags: computer-networks, power-consumption
---


# Question
Title: How shall I understand the undesirable consequences of dynamic scoping?
In *Practical Foundation of Programming Languages* by Harper

> **8.4 Dynamic Scope**
>
> Another approach, called dynamic scoping, or dynamic binding, is sometimes advocated as an alternative to static binding. The crucial difference is that **with dynamic scoping the principle of identiﬁcation of abt’s up to renaming of bound variables is denied. Consequently, capture-avoiding substitution is not available.** Instead, evaluation is deﬁned for open terms, with the bindings of free variables provided by an environment mapping variable names to (possibly open) values. The binding of a variable is determined as late as possible, at the point where the variable is evaluated, rather than where it is bound. If the environment does not provide a binding for a variable, evaluation is aborted with a run-time error.
>
> In the higher-order case, the equivalence of static and dynamic scope breaks down. For example, consider the expression
>
> ```
>  e = (λ (x : num) λ (y : num) x + y)(42).
>
> ```
>
> With static scoping `e` evaluates to the closed value `v = λ (y : num) 42 + y`, which, if applied, would add `42` to its argument. It makes no difference how the bound variable `x` is chosen, the outcome will always be the same. With dynamic scoping, `e` evaluates to the open value `v' = λ (y : num) x + y` in which the variable `x` occurs free. When this expression is evaluated, the variable `x` is bound to `42`, but this is irrelevant because the binding is not needed to evaluate the λ-abstraction. The binding of `x` is not retrieved until such time as `v'` is applied to an argument, at which point the binding for `x` in force at that time is retrieved,and not the one in force at the point where `e` is evaluated.
>
> Therein lies the difference. For example, consider the expression
>
> ```
> e' = (λ (f : num → num) (λ (x : num) f (0))(7))(e)`.
>
> ```
>
> When evaluated using dynamic scope, the value of `e'` is `7`, whereas its value is `42` under static scope. The discrepancy can be traced to the rebinding of `x` to `7` before the value of `e`, namely `v'`, is applied to `0`, altering the outcome.
>
> Dynamic scope violates the basic principle that variables are given meaning by capture-avoiding substitution as deﬁned in Chapter 1. Violating this principle has at least two undesirable consequences.
>
> One is that the names of bound variables matter, in contrast to static scope which obeys the identiﬁcation principle. For example, **had the innermost λ-abstraction of `e'` bound the variable `y`, rather than `x`, then its value would have been `42`, rather than `7`**. Thus, one component of a program may be sensitive to the names of bound variables chosen in another component, a clear violation of modular decomposition.
>
> Another problem is that dynamic scope is not, in general, type-safe. For example, consider the expression
>
> ```
> e' = (λ (f : num → num) (λ (x : str) f ("zero"))(7))(e)
>
> ```
>
> **Under dynamic scoping this expression gets stuck attempting to evaluate `x + y` with `x` bound to the string `“zero”`**, and no further progress can be made.

What does it mean by "with dynamic scoping the principle of identiﬁcation of abt’s up to renaming of bound variables is denied" and "consequently, capture-avoiding substitution is not available"?

Why under dynamic scoping, "had the innermost λ-abstraction of `e'` bound the variable `y`, rather than `x`, then its value would have been `42`, rather than `7`"? How does "static scope obey the identiﬁcation principle" here?

How "Under dynamic scoping this expression gets stuck attempting to evaluate `x + y` with `x` bound to the string `“zero”`"? Isn't it that `x` in `e'` is bound to `7`?

Thanks.

# Answer
I think you're right that that example is a bit confused. I believe the fix is the following, if I got my parantheses right.

```
e' = (λ (f : num → num) (λ (x : str) f ("zero"))(7))(e)

```

should instead be

```
e' = (λ (f : num → num) (λ (x : str) f) ("zero"))(e)(7)

```

If we evaluate e first we'll get:

```
(λ (x : num) λ (y : num) x + y)(42).

x = 42
(λ (y : num) x + y).

```

We've finished evaluating e, since we got to a lambda. But evaluating it in the above expression will cause the bad addition "zero" + 42, since, regardless of what we do with the environment, the x="zero" binding will be the closest. The immediate reduction of the above gives:
> 1 votes

---
Tags: programming-languages
---


title: Combining Predicate Logic and BigO

text:
# Question
Title: Combining Predicate Logic and BigO
I am a beginner to predicate logic and BigO and am having though time understanding the definition of BigO in terms of predicate logic in the picture attached. I particularly am unable to understand what is meant by n0 in this context. Any help is greatly appreciated.

# Answer
> 2 votes
What the definition is saying is: $f\in O(g)$ if there's a number $n\_0$ such that $f(n)$ is less than some multiple of $g(n)$ (that's where the $c$ comes in) for all $n$ larger than $n\_0$. In simple terms, it's saying that $f$ is eventually bounded by some fixed multiple of $g$.

Big-O notation is essentially a simplification describing the ultimate rate of growth of a function. Here we don't care at all if, say, $f(n)$ is bigger than $43\cdot g(n)$ for the first thousand values of $n$: if $f(n)\<43\cdot g(n)$ for all the rest (the bigger values of $n$), we've established that a multiple of $g$ is an upper bound on the values of $f$.

---
Tags: algorithms, logic, first-order-logic, big-o-notation, predicate-logic
---


# Question
Title: What does it mean when a dot appears in a logic gate other than the NOT gate? (in logic diagrams)
For example, this gate:

looks like an OR gate, except there's a dot to the right. The dot is reminiscent of the fact that there's a dot in the NOT gate, so I wonder if it has something to do with that. There's no NOT after this gate in the diagram I'm looking at, so this doesn't to be implementing NOT OR or something like that...

# Answer
This is a `NOR` gate. You can implement a `NOR` gate using a combination of a `OR` and a `NOT` gate. However, in MOSFET implementation or other technologies (i.e. electrical hardware architecture), we can build a `NOR` gate directly and more efficiently (i.e. more efficient than using a `OR` and a `NOT` gate). That's why we use `NOR` as well.
> 2 votes

---
Tags: logic, circuits
---


# Question
Title: Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon
Let's say I give you the following array of points:

(1,1) (1,3), (2,2), (4,1), (4,3)

My (terrible) mspaint drawing of the shape that would be created by these looks like this:

How, given an arbitrary set of coordinates, can I define the edges which constitute a shape with no overlapping edges?

# Answer
A copy from the highest voted answer from SO:

> > Our strategy is to make a plan where we are sure that the polygon includes all points, and that we can find an order to connect them where none of the lines intersect.
> >
> > **Algorithm**:
> >
> > 1. Find the leftmost points p
> > 2. Find the rightmost point q
> > 3. Partition the points into A, the set of points below pq, and B, the set of points above pq \[you can use the left turn test on (p,q,?) to determine if a point is above the line\].
> > 4. Sort A by x-coordinate (increasing)
> > 5. Sort B by x-coordinate (decreasing).
> > 6. Return the polygon defined by p, the points in A, in order, q, the points of B in order.
> >
> > **Runtime**:
> >
> > Steps 1,2,3 take O(n) time.
> > Steps 4,5 take O(nlogn) time.
> > Step 6 take O(n) time.
> > Total runtime is O(nlogn).
> >
> > **Correctness**:
> >
> > By construction, all points besides p,q are in set A or set B. Our output polygon from line 6 therefore outputs a polygon with all the points. We now need to argue that none of the line segments in our output polygon intersect each other.
> >
> > Consider each segment in the output polygon. The first edge from p to the first point in A can't intersect any segment (because there is no segment yet). As we proceed in order by x-coordinate through the points in A, from each point, the next segment is going to the right, and all previous segments are to the left. Thus, as we go from p, through all the points of A, to point q, we will have no intersections.
> >
> > The same is true as we go from q back through the points of B. These segments cannot intersect each other because they proceed from right to left. These segments also cannot intersect anything in A because all points in A are below line pq, and all points in B are above this line.
> >
> > Thus, no segments intersect each other and we have a simple polygon.
>
> Source: Broken link
>
> I understand this is really late, but it might be useful for future viewers.
> 1 votes

---
Tags: algorithms, graphs, computational-geometry
---


# Question
Title: Numerical stability of linear interpolation
Is one of these two functions more numerically stable than the other?

```
def interpolate_a(x, y, z):
    return y + (z - y) * x

def interpolate_b(x, y, z):
    return y * (1 - x) + z * x

```

If so, which one is better and why? After testing these functions with several million inputs, they have always returned the same value. My concern is that with certain inputs, they may return different values, and one will be more correct that the other. Is this possible?

# Answer
"Numerical stability" is a much vaguer term than most people realise. We typically use it when referring to an approximation method, such as some kind of linear analysis, or numeric quadrature, or solving (possibly partial) differential equations. It refers to the property that given some appropriate assumptions (e.g. the inputs are reasonable), the algorithms converges to the ideal solution reasonably, even in the presence of floating-point error.

That's actually not what you're referring to here. However, there is a good answer to the question that you are trying to ask. If x is between 0 and 1 inclusive (and this is an important proviso; it's called "interpolate" but could be used to extrapolate), then `interpolate_b` is better.

In any sensible system of floating point (e.g. IEEE-754), you can assume several things:

1. Multiplying a finite number by zero returns a zero.
2. Multiplying a finite number by one returns that number.
3. Adding zero to any finite number returns that number.
4. For any finite number x, `x - x` returns a zero.

Standard provisos: Inf is not a finite number. NaN is not a number at all. Negative zero is a thing.

The negative zero thing is occasionally relevant, so when I say "returns a zero", or "returns that number" when that number happens to be zero, do be aware that you may get a zero of the opposite sign that you might expect under some circumstances. The exact rules are complicated, and we won't go into them here.

Still, it's more correct to say, for example, that if x is a finite number which is not zero, then `x+0` and `x+(-0)` are both identical to x. If x is zero, then `x+0` and `x+(-0)` may not be identical, and may not be identical to x, but they will differ from x by at most a sign bit.

First, consider the case where x is zero (and neither y nor z are negative zero). Then both `interpolate_a` and `interpolate_b` return *exactly* y. So far, so good.

Now consider the case where x is exactly 1. Then `interpolate_a` returns `y + (z - y)`, because the multiply by x is a no-op. This may not be exactly equal to z due to round-off error. (Exercise: Find two single-precision IEEE-754 numbers which have this property in the default rounding mode.)

However, if you follow through the logic above, you can see that if x is exactly 1 (and neither y nor z are negative zero) then `interpolate_b` returns exactly z.

It's almost always considered a desirable property of any interpolate function that they return exact values at the endpoints. It's this property that makes `interpolate_b` a better choice.
> 6 votes

# Answer
According to the document "P0811R2: Well-behaved interpolation for numbers and pointers" (the link @Eric provided), it depends:

> 1. a+t\*(b-a) does not in general reproduce b when t==1, and can overflow if a and b have the largest exponent and opposite signs.
> 2. t\*b+(1-t)\*a is not monotonic in general (unless the product ab≤0).

The author continues by providing a short list of desirable properties, before suggesting an implementation that fulfills them all.

It is a worthy read. I suggest creating the method one place accessible to all your projects (e.g. your company's single shared math-library wrapper), and reuse it whenever linear interpolation is needed.
> 5 votes

---
Tags: number-theory, numerical-algorithms
---


# Question
Title: Determining whether a change in an memoized algorithm will improve the performance
I have an algorithm that constructs an optimal binary tree using dynamic programming. After introducing what I thought would be an optimization, the algorithm became over 2 times slover. **Question:** Is there an analytical way to determine whether such change will improve the runtime of an algorithm with memoization?

Python code and description follow:

```
def solver(problem, memo={}):
    try:
        return memo[problem]
    except KeyError:
        if is_base_case(problem):
            memo[problem] = base_solver(problem)
            return memo[problem]

    best_score, best_solution = INFINITY, None

    for left_subproblem, right_subproblem in all_splits(problem):

        left_solution = solver(left_subproblem, memo)

        if (base_score(problem) + score(left_solution) >= best_score):  #optimization
            continue                                                #optimization

        right_solution = solver(right_subproblem, memo)

        current_score = base_score(problem) + score(left_solution) + score(right_solution)
        if (current_score < best_score):
            best_score = current_score
            best_solution = combine_solutions(problem, left_solution, right_solution)

    memo[problem] = best_solution
    return memo[problem]

```

The function iterates over all ways to split an instance problem into two subproblems, recursively solves them and stores the solutions.
Optimal tree is a tree that has the lowest score, determined by the `score()` function. The score of a tree is always positive and is a sum of a base score of the root node plus the score of the subtrees.
The optimization in question are the lines marked as `#optimization`. It's supposed to avoid solving the right subproblem, if, based on the left result, it's impossible to create a solution with a better score than the current best.
Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work. However, this is just my hindsight and I would like to have a rigorous way to analyse the problem, in case an algorithm like this was presented to me in pseudo-code.

# Answer
> 1 votes
> Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work.

This is impossible. Not solving and memoizing a subproblem can never make the algorithm slower. Either the subproblem will never be needed (in which case not memoizing it only saves work) or it will turn out to be necessary after all, in which case we would have to compute it. However, the worst case is only that we do not save any time: if we skip the computation *now*, we might have to do it in the future, but this is not more work than doing it now.

The optimization you've done will never cause more work to be done on computing subproblems. Thus, the only reason it could make the algorithm slower is if the optimization itself is expensive to compute. It seems likely either `score` or `base_score` are very slow methods, and your optimization causes them to be evaluated an additional time. You might be able to speed it up by storing `base_score` and `score(left_solution)` in a temporary variable.

---
Tags: algorithms, runtime-analysis, dynamic-programming
---


# Question
Title: Simple proof for NP-completeness of Edge Dominating Set
In a graph, an *edge dominating set* is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D. The Minimum Edge Dominating Set problem is to find an edge dominating set of minimum cardinality. The decision version of this problem is known to be NP-complete, but I would like to inquire whether a relatively simple proof of this fact is known.

The only proof I found in the literature is in the paper that first tackled this problem, by Gavril and Yannakakis. However, the above proof makes use of the fact that Vertex Cover is NP-complete for planar cubic graphs, and the fact that bipartite graphs of degree d can be d-edge-colored. I would prefer a simpler proof, that would only make use of facts typically known to undergraduates who took an algorithms course.

# Answer
I assume that you only want to show the minimum edge dominating set problem is NP-complete for the general graph (i.e., you don't care about what properties the constructed graph has).

In case you missed it, there is an arguably simpler reduction from 3-SAT in the same paper (see Theorem 2). The reduction assumes no further "specialist" knowledge. You can make the presentation even slightly easier by skipping verification of bipartiteness and boundedness of the maximum degree of the resulting graph.
> 5 votes

# Answer
There is a simple reduction in paper *Approximation hardness of edge dominating set problems* (Chlebík and Chlebíková, *Journal of Combinatorial Optimization* 11(3):279–290, 2006).

The reduction is add a universal vertex connected to all nodes and replace every edge by a $P\_5$ with a pendent edge added to the middle vertex. There is an edge dominating set of size $|E|+k$ in the new graph iff there is a vertex cover of size $k$ in the original one. You will need at least one edge for each gadget; the rest is classical. (Actually I think you don't need the universal vertex)
> 4 votes

# Answer
We will reduce Vertex Cover to Edge Dominating Set and complete the proof. Given an instance of the decision version of vertex cover problem $I(G,k)$, we construct $G'$ by adding $nk+k$ new edges to $G$, where $n$ is the number of vertices in $G$:

* add $k$ new vertices;
* add an edge between each of these new vertices and each vertex in $G$, totally $nk$ edges, called *intermediate edges*;
* add a pendant edge to each of the new vertices, totally $k$ edges.

Observe that the edge dominating set in $G'$ contains at least $k$ edges. Also observe that any edge domindating set of size $k$ in $G'$ can only contain intermediate edges. Then we claim that $G$ has a vertex cover of size $k$ iff $G'$ has an edge dominating set of size $k$.
> 1 votes

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


# Question
Title: Can a new company make a processor compatible with Windows and current software?
Would anyone apart from Intel and AMD ever be able to make a processor that can be used on a personal computer, or is it impossible? I believe it is due to them owning the x86 instruction set, which means that a company doesn't have the right to produce a processor which could run a personal computer. But what if the processor used a different instruction set, but in between it translated the x86 architecture to its own? Would that also be breaching the ownership?

# Answer
> 0 votes
In theory a new microprocessor manufacturer could enter the market. In practice this is very unlikely, but not for any reason to do with the x86 architecture - the barrier is economics.

Manufacturing modern microprocessors is a highly complex engineering challenge which requires a lot of very expensive equipment. Getting the design right in the first place requires a massive upfront investment. And the profit margin on each unit is tiny, so in order to turn a profit you also have the additional overhead of investing in automation - you cannot just employ an army of production line staff.

A saturated market place with established players, high fixed costs and low profit margins is not going to be attractive to start-ups or new entrants, or to their investors.

The one thing that might change this is a breakthrough in technology. If you invent a way to manufacture a portable quantum computer from household waste in your garage using a few DIY tools, then you are home and dry.

---
Tags: computer-architecture
---


# Question
Title: Will a vertex present in the set of vertices present in each basis cycle be present in all the cycles?
I read that the XOR of basis cycles can generate all the cycles present in the graph.

I was just wondering if there exists any one vertex which is present in all the basis cycles and is present in all the cycles of the graph.

Can someone point me to something that might help me tackle this problem?

# Answer
> 3 votes
Consider the following graph:

Let $S$ be the set containing the cycles formed by i) the red and black edges, and ii) the blue and black edges. $S$ is a cycle basis in which every cycle contains vertex $x$, yet the cycle formed by the red and blue edges does not contain $x$.

---

Edit: it is also not true that the existence of a vertex $x$ that lies in all cycles of a cycle basis implies that $x$ belongs to all cycles of the graph. See the following counterexample:

The $3$ cycles that can be formed by taking an edge $e$ of color $c$ for $c \in \\{ \mbox{red, green, blue}\\}$ along with the two black edges incident to the endpoints of $e$ form a basis $S$. Vertex $x$ belongs to all the cycles in $S$ but it does not belong to the cycle formed by the red, green, and blue edges.

---
Tags: algorithms, graphs
---


# Question
Title: Undecidable: Given a TM $M$, is there $w$ on which $M$ halts after $\leq |w|$ steps?
The question is: Is there a word $w$ on which a TM $M$ halts after a maximum of $|w|$ (word length) steps?

More formerly, is the language below decidable? $$H=\\{\langle M\rangle \mid \text{ TM $M$ halts after a maximum of $|w|$ steps for some word }w \\}$$

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to prove this conclusion (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?

# Answer
Let $M$ be a Turing machine and consider the Turing machine $M'$ that simulates $M$ on an empty input (regardless of the input to $M'$).

If $M$ halts on empty input then $M'$ eventually halts too. This means that there is a word $w$ of sufficiently large length $|w|$ such that $M'$ halts after at most $|w|$ steps (actually, there are infinitely many such words).

If $M$ does not halt, then also $M'$ doesn't halt (regardless of the its input).

Therefore your problem cannot be decidable as otherwise there would be a Turing machine capable of solving the halting problem.
> 2 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree
I am trying to solve the following recurrence relation: $$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$

I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} \< n$

I am trying to prove it using a **recurrence tree**.

The tree is not balanced. Particularly, the longest path from the root to a leaf is the leftmost one with a length of $\log\_2n$ when the shortest path is the rightmost one with a length of $\log\_3n$.

We get that at each level,except the first one, the cost is $\< n$. In more detail,the first level has a cost of $n$. The nodes on the second level add to a $\frac{5}{6}\cdot n$ cost, the third level has a cost equal to $\left (\frac{5}{6} \right )^2\cdot n$ and so on...

So, untill the height of $\log\_3n$ we have a cost of $$n\sum\_{i=0}^{\log\_3n-1}\left (\frac{5}{6} \right )^i = n\cdot \frac{\left (\frac{5}{6}\right)^{\log\_3n}-1}{\left (\frac{5}{6}\right)-1}$$

So, the result above seems to be a lower bound for my function $T(n)$

Is my approach correct? If yes, then how do I go on in order to prove that the time complexity is **$T(n)=Θ(n)$**.Thanks in advance!

# Answer
> 1 votes
On the one hand, clearly $T(n) \geq n$ (see detailed proof below). On the other hand, let us find prove by induction that $T(n) \leq Cn$, for large enough $C$. The base case trivially holds for $C \geq T(1)$. For the inductive step, we have $$ T(n) = T(n/2) + T(n/3) + n \leq C\cdot (n/2) + C\cdot (n/3) + n = \[\tfrac{5}{6}C+1\]n. $$ (We're cheating here a bit since $n$ isn't necessarily a multiple of 6.) If $C \geq 6$, then $\tfrac{5}{6}C+1 \leq C$, and so we can conclude that $T(n) \leq Cn$, thus completing the inductive step. In total, if we take $C = \max(T(1),6)$ then the proof goes through, hence $$ n \leq T(n) \leq \max(T(1),6) n. $$ This implies that $T(n) = \Theta(n)$.

---

Finally, let us prove that $T(n) \geq n$. We first prove that $T(n) \geq 0$. The proof by induction. The base case clearly holds, and the inductive step is a consequence of $$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + 0, $$ using the inductive hypothesis twice. Finally, $$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + n = n. $$

# Answer
> 0 votes
Defining base cases:

$T(0) = 0;$

$T(1) = 0;$

I got: $$ T(n) = n \\; (\sum\_{r = 0}^{log\_3 \\; {n}} \[ \binom{log\_3 \\; {n}}{r} \\; log\_2 \\; \[{(\frac{2}{3})^r \\; n}\] \\; + \\; \sum\_{r = 0}^{log\_2 \\; {n}} \[ \binom{log\_2 \\; {n}}{r} \\; log\_2 \\; \[{(\frac{3}{2})^r \\; n}\]) $$

$$ $$

You can do the approximation & the bounding yourselves.

Sorta took me longer to format this properly than solve this.

---
Tags: time-complexity, trees, recurrence-relation
---


title: Find a maximum matching in linear time

text:
# Question
Title: Find a maximum matching in linear time
I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of edges) should differ from a maximum matching size not more than a factor of two.

The problem I have is coming up with a linear-time algorithm. I know how to find a maximum matching, but this takes polynomial time.

# Answer
* $M\gets\emptyset$
* While $E\neq\emptyset$ do

+ select $(u,v)\in E$
    + $M \gets M \cup \\{(u,v)\\}$
    + delete all edges incident to $u$ and $v$
* Return $M$

The above algorithm runs in $O(m+n)$ time if we store $G=(V,E)$ using adjacency list.

Now we prove this algorithm is 2-approximation. Let OPT be the maximum matching. For each edge $e\in$ OPT, there must exist $e'\in M$ s.t. $|e\cap e'|\in\\{1,2\\}$, i.e. $e$ and $e'$ share one or two common vertex. Moreover, at most two different edges of OPT are incident to the same edge of $M$.

Now we divide OPT into two disjoint subsets OPT$\_1$ and OPT$\_2$. In OPT$\_1$, no two edges are incident to the same edge in $M$. In other words, $M$ has a subset $M\_1$ s.t. OPT$\_1$ and $M\_1$ are one-to-one, which implies $|OPT\_1|=|M\_1|$. We can pair all edges in OPT$\_2$ s.t. different pairt of edges in $OPT\_2$ are mapped to different edges in $M\_2\subseteq M$. It's easy to show that $M\_1\cap M\_2=\emptyset$ and $M\_1\cup M\_2 = M$.

We have $|M|=|M\_1|+|M\_2|$ and $|OPT|=|OPT\_1|+|OPT\_2|=|M\_1|+2|M\_2|$. Therefore, $2|M|\geq|OPT|$.

**Edited on Jan. 15, 2020:**

The following is a simpler argument. For every matching $M$, we have $2\\#edges(M)=\\#vertices(M)$. For each $e=(u,v)$ in the maximum matching $M^\*$, at least one of $u$ and $v$ appears in a maximal matching $M$. Otherwise, $M$ isn't maximal. Hence, $2\\#edges(M)=\\#vertices(M)\geq\\#edges(M^\*)$.
> 3 votes

# Answer
Given an unweighted, undirected graph $G=(V,E)$ with $E = \\{e\_1, \dots, e\_m\\}$ being our edge set, $e\_i = \\{v,w\\}$ with $v,w\in V$. Furthermore, we have $|E| = m$.

We can create a matching by adding edges greedily. This algorithm is linear in $m$, i.e. $O(m)$.

1. M = $\emptyset$
2. for each edge $e\_i \in E$
    3. if $M \cup e\_i$ form a valid matching, add $e\_i$ to $M$

You still need to show that the greedy algorithm above is a 2-approximation. Let $M$ be the solution of the above algorithm and let $M^\*$ be the optimal solution. Show that $|M| \leq 2|M^\*|$.
> 2 votes

---
Tags: algorithms, graphs, matching
---


# Question
Title: How to handle missing attribute's value with ID3 algorithm?
i am working with ID3 algorithm, and i know that classic ID3 basically can handle missing data. But i am trying to code this algorithm, so what should i do if there is missing attribute's value in training dataset? How can i classify the data point that has missing attribute's value?

# Answer
One approach is to use imputation to estimate a value for the missing attribute, based on other attributes.

See also https://en.wikipedia.org/wiki/Missing\_data#Techniques\_of\_dealing\_with\_missing\_data and https://stats.stackexchange.com/questions/tagged/data-imputation and https://stats.stackexchange.com/questions/tagged/missing-data and https://stats.stackexchange.com/q/208845/2921.
> 0 votes

---
Tags: machine-learning, decision-tree
---


# Question
Title: An operational semantics for lambda-calculus normal order evaluation strategy
TAPL book, page 56 reads:

> Under the normal order strategy, the leftmost, outermost redex is always reduced first.

I understand this as a restriction of the full beta-reduction evaluation strategy, whose reduction rules are given as follows:

$$\frac{t\_1 \to t\_1'}{t\_1 t\_2 \to t\_1' t\_2}$$

$$\frac{t\_2 \to t\_2'}{t\_1 t\_2 \to t\_1 t\_2'}$$

$$\frac{t\_1 \to t\_1'}{λx. t\_1 \to λx. t\_1'}$$

$$\frac{(λx. t\_1) t\_2}{\[x \to t\_2\] t\_1}$$

My question is how to transform these rules so that the normal order strategy condition holds.

# Answer
You can use the following rules:

$\frac{t\_1 \longrightarrow t\_1'}{t\_1 t\_2 \longrightarrow t\_1' t\_2}$

$(λx. t\_1) t\_2 \longrightarrow \[x \mapsto t\_2\]t\_1$
> 1 votes

---
Tags: lambda-calculus, types-and-programming-languages
---


# Question
Title: Is $\Gamma \vdash x x : T$ possible in the simply typed lambda calculus?
Is $\Gamma \vdash x x : T$ possible?

This problem appears on page 104 of Benjamin Pierce's "Types and Programming Languages".

My conclusion is that it is was the case then we would get $x: T\_1 \to T\_2$ and $x: T\_1$ and by some axiom, these types are not equal.

The problem is identifying this axiom but I fear it might be possible to have this equality...

Any hints?

# Answer
> 2 votes
You are on the right track. The argument you would use is on the lines of size of types defined below: (I am assuming you are in the world of simply typed $\lambda$-calculus)

$size(T) = 1$

$size(T \to T') = size(T) + size(T')$

Unification will only work if the size of types is equal, and in this case $size(T \to T') \> size(T)$ hence there cannot be such a term.

However, if you add recursion/non-termination in the type system. You can indeed have such a term. $ \vdash (\lambda x. x x) (\lambda x. x x):\bot$

$\bot$ is the type that represents non-termination.

---
Tags: lambda-calculus, types-and-programming-languages, types
---


# Question
Title: How can Turing complete machines exist theoretically if the halting problem is undecidable
As the question says, if I input on the tape of a Turing complete machine a program that solves the halting problem with the correct inputs the program will never end its execution regardless of memory and time. Isn't the halting problem a computational problem that can't be executed by a Turing complete machine so that it's halts sometime?

# Answer
> 4 votes
The halting problem is the problem of deciding whether a given Turing machine halts on a given input or not.

This problem is undecidable, meaning that no program running on a Turing machine can solve this problem for all possible inputs. Hence, your assumption that such a program exists is wrong.

---
Tags: halting-problem, turing-completeness
---


# Question
Title: Relative vertex capacity in max flow algorithm
I am designing a network for a max flow and would appreciate the following feature:

Say there is a flow incoming to a vertex. I would like to consume some specified amount of that flow and let through the rest. Unlike vertex capacity, which says "let though at most N units of flow", I need to "let through everything but N units of flow".

An example:

* Vertex of relative capacity 10
* Incoming flow = 15. Outgoing flow will be 15 - 10 = 5.
* Incoming flow = 10. Outgoing flow will be 10 - 10 = 0.
* Incoming flow = 5. Outgoing flow will be 5 - 10, which is less than 0, so 0.

Does such a feature exist? And if yes, which edges/vertices/edge capacities do I need to add/remove/modify and how?

Thanks a lot!

# Answer
> 2 votes
For edge "consumptions" I believe the following approach should work: \[I misread your question at first, but am leaving this part for the benefit of future people reading this\]

Suppose you have some edge $u\rightarrow v$ with "consumption" $c$. Then you can model this by inserting a vertex $w$ in the middle to get $u\rightarrow w \rightarrow v$ and then add an edge $w\rightarrow t$ with capacity $c$, where $t$ is your sink. Then you have to ensure that your max-flow algorithm prioritizes pushing flow through $w\rightarrow t$ over $w\rightarrow v$. Thus this flow will be "consumed" as much as possible before going through the edge. I see two ways in which this can be done:

* If your algorithm works by finding an augmenting path, make sure that this augmenting path goes through $w\rightarrow t$ rather than $w\rightarrow v$ if possible (i.e. if $w\rightarrow t$ is not saturated). Also make sure that this holds for the "reverse edges" (i.e prioritize taking flow away from $w\rightarrow v$ rather than $w\rightarrow t$). This should not be difficult to do, but depends on the exact implementation, and on your access to it.
* Or you can use a max-flow min-cost algorithm and give a positive cost (say 1) to every edge except those of the $w\rightarrow t$ type (who receive a cost of 0).

Then to get the answer to your original problem just ignore all the $w\rightarrow t$ edges.

Now, for vertex $v$ with "consumptions" $c$ you can simply add an edge $v\rightarrow t$ with capacity $c$ and modify your algorithm in the same way.

If you don't care about the exact value of the flow through each edge but only the total max-flow, then you don't even need to change anything to the algorithm and can just use the returned value for the new graph as is.

---
Tags: network-flow
---


# Question
Title: What are the difference and relation between type checking and type reconstruction?
In *Types and Programming Languages* by Pierce,

> ML-style let-polymorphism was ﬁrst described by Milner (1978). A num- ber of type reconstruction algorithms have been proposed, notably the clas- sic Algorithm W (Damas and Milner) of Damas and Milner (1982; also see Lee and Yi, 1998). The main diﬀerence between Algorithm W and the pre- sentation in this chapter is that the former is specialized for **“pure type reconstruction”**—assigning principal types to completely untyped lambda- terms—while we have **mixed type checking and type reconstruction**, permit- ting terms to include explicit type annotations that may, but need not, contain variables. This makes our technical presentation a bit more involved (espe- cially the proof of completeness, Theorem 22.3.7, where we must be careful to keep the programmer’s type variables separate from the ones introduced by the constraint generation rules), but it meshes better with the style of the other chapters.

What are the difference and relation between type checking and type reconstruction?

Does type checking apply only to terms with explicit type annotations which don't contain type variables?

Does type reconstruction apply only to terms either without explicit type annotations, or with explicit type annotations containing type variables?

Thanks.

# Answer
> 3 votes
> What are the difference and relation between type checking and type reconstruction?

*Type reconstruction* is a class of problem that involves coming up with a type for a term. For example given a term $\lambda x. x$ can you find the type for this term. Or in general answering the question:

Does a $T$ exist such that the judgement $\Gamma \vdash M : T$ is derivable, where $M$ is the term and $\Gamma$ is the type environment.

*Type checking* on the other hand is a process where the question is:

Given a $T$ and an $M$ can $\Gamma \vdash M : T$ be a valid judgement.

> Does type checking apply only to terms with explicit type annotations which don't contain type variables?

No. You can have a type checking problem that asks whether $\lambda x. x$ has a type $\tau \to \tau$ where $\tau$ is a type variable.

> Does type reconstruction apply only to terms either without explicit type annotations, or with explicit type annotations containing type variables?

As type reconstruction problem is about computing the correct type for a term, if you have an explicit type annotation for a term, you would classify it as a type checking problem.

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


title: NPDA question about accepting condition

text:
# Question
Title: NPDA question about accepting condition
Will an NPDA accept a string that reaches a final state but does not have all its input consumed yet?

# Answer
By “final state” I assume you mean “accepting state”. The answer is no, as the accepting state should have an empty string $\epsilon$ for it to be meaningful.

You can of course define a transition relation that consumes everything after it has reached an accepting state. It will act as a prefix detector.
> 1 votes

---
Tags: automata
---


title: Are hash functions one-way?

text:
# Question
Title: Are hash functions one-way?
I have heard that we can convert any text to hash code , but hash code can't be converted back to text without brute force.

Suppose we consider the text "mal". The hash codes of the individual letters are

> m= 6f8f57715090da2632453988d9a1501b
>
> a= 0cc175b9c0f1b6a831c399e269772661
>
> l= 2db95e8e1a9267b7a1188556b2013b33

Those of the prefix "ma" and of "mal" itself are

> ma= b74df323e3939b563635a2cba7a7afba
>
> mal= 749dfe7c0cd3b291ec96d0bb8924cb46

Each hashcode has 32 elements, which can be either numbers from 0 to 9 or letters from a to f.

What I observed was some when we add a letter some numbers are kept like it is just changing it's order. Is there some logic in it? Is there some easier method?

# Answer
> 1 votes
Well, there is obviously a system. Someone wrote code to calculate the hash codes for strings, and that is the system that the hash code follows.

For normal software development purposes, it's Ok if there is a system that you can recognise, as long as different strings are mapped to different hash codes most of the time. For cryptography, for example when you calculate a hash code for a password, you want hash codes where it is practically impossible to determine the string from the hash code.

For a cryptographic hash, given a hash h, the only way to find a string s with hash(s) = h is to try out all possible strings s calculating hash(s) for each, until we find an s with hash(s) = h. Given a cryptographic hash for the string "1234", you would find such an s quickly.

For ordinary hash functions, if you are given how the hash code is calculated, it is often possible to calculate which is the shortest string s with hash(s) = s. However, any function that maps from an infinite set (strings) to a finite set (fixed length hash codes) must allow many strings to map to the same hash code. So if you map 500 bit strings to 256 bit hash codes, you cannot possibly determine which string was hashed, because many strings have the same hash code.

# Answer
> 1 votes
If you could easily convert from the hash code back to text then this would make the hash code useless for cryptographic purposes. In order to be secure, a cryptographic hash function should be a one-way function, which is impossible (for all practical purposes) to invert.

Another complication is that the hash function output is a fixed length - in your case, your hash values are $128$ ~~bytes~~ bits each. They are printed out in hexadecimal as a string of $32$ characters, and each character represents $4$ ~~bytes~~ bits. But the input to the hash function can be text of any length at all. So there will be many different text strings which give the same hash code (although almost all of these strings will be meaningless nonsense).

If you know that the input text is a single character then you can use a brute force attack - run the hash function on all possible single character texts until you get an output that matches the hash value that you are looking for. The same approach will work for short texts of just a few characters. But if your text could be hundreds or even thousands of characters long then a brute force approach is not practical, because the number of possible texts is much too large.

---
Tags: hash
---


# Question
Title: How to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent?
I am trying to understand what this question is asking in terms of conversion. I know how to convert binary to decimal and vice versa, but the method you need to use has me confused.

I need to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent in the conversion. What I did was take every odd numbered position from base 2 digit from 010111 so "111" I skipped every other number and took the digit from that position (if that makes sense) I only had three digits so I added a 0 to make it 4 bit 0111 which equals 7 in decimal. I know this is wrong but why??

This is the question: - Imagine that a processor is faulty and reads only odd-numbered positions when converting binary numbers to decimals, but it applies the correct positional exponent in the conversion. In radix 10, the binary number 010111 converted by this processor would be:

The mock test answer says the result is 2 but I cannot figure out why

# Answer
> 1 votes
I'm assuming positions are counted from $1$ starting from the least significant bit.

In this case you're using the exponents as if the number was 0111. The question is asking to use the same exponents you would use for the odd-position digits of the number 010111.

To break it down, from the least to the most significant bit, the contribution to the final decimal value of each digit is:

* First digit: $1 \cdot 2^0 = 1$.
* Second digit: would be $1 \cdot 2^1 = 2$ but it is 0 since digits in even position are ignored.
* Third digit: $1 \cdot 2^2 = 4$.
* Fourth digit: ignored.
* Fifth digit: $1 \cdot 2^4 = 16$.
* Sixth digit: ignored.

The final result is: $16+4+1 = 21$.

---

Edit: Since you added that the answer should be $2$ this tells us that positions are either numbered starting from $0$, from the least to the most significant bit, or starting from $1$ from the most to the least significant bit.

In either case you would select the bits $001$ whose contribution would be $1 \cdot 2 + 0 \cdot 2^2 + 0 \cdot 2^4 = 2$.

# Answer
> 0 votes
If the processor is only reading odd numbered bits *and* we assume that the right-most bit is bit $0$ then in effect the processor is doing a bitwise AND with bit string $101010$ before converting to decimal.

$010111\_2 \text{ AND } 101010\_2 = 000010\_2 = 2\_{10}$

---
Tags: arithmetic, binary
---


# Question
Title: Closure of regular languages under "inverse second half"
> **Theorem.** Show that if $L$ is regular, then so is $$ \varphi(L)=\left\\{w \in \Sigma^{\*} \mid \text {there exists an } \alpha \in \Sigma^{\*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\right\\} $$ **Proof.** Let $L$ be a regular language. Because $L$ is regular, there exists a DFA $M$ that accepts it. We construct out of $M$ a $\lambda$NFA $M'$ whose language is $\varphi(L)$.
>
> We can think of a computation of $M$ as moving a token across the states of $M$. The machine $M'$ will reuse the states of $M$, but will use three tokens: white, red and blue. Initially, the blue token is put on $q\_0$ (the initial state of $M$), and the white and red tokens are put on a nondeterministically guessed state (both tokens on the same state).
>
> 1. Describe the transitions of $M'$.
> 2. Describe the acceptance condition of $M'$.

Could someone please help me with that? I research regular expressions, DFAs, NFAs, and conversions between all of theses, but I still don't know how to solve this question.

# Answer
The white token is a placeholder, which just remembers the original state of the red token (of course, the roles of these two tokens can be switched); this is the state at which $M$ would be after reading $\alpha$. The red token corresponds to the $w$ part of the word, and the blue token to its $\alpha$ part.

When reading a symbol, the red token advances according to the rules of $M$, the white token stays put, and the blue token guesses a symbol and advances according to the rules of $M$ (in effect, it guesses one symbol of $\alpha$).

The machine accepts if the blue and white tokens are at the same state (so we guessed correctly the state at which $M$ is after reading $\alpha$), and the red token is at an accepting state of $M$ (so $\alpha w \in L$).
> 1 votes

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


title: help to find An efficient algorithm

text:
# Question
Title: help to find An efficient algorithm
I'm trying to find An efficient algorithm for the following problem:

I have $n$ sets of numbers (different sets might have common numbers) and I need to find union combination of $k$ sets that Will yield the biggest set.

For example: if i have the sets $A1=\\{1,3,4\\}, A2=\\{1,2,4\\}, A3=\\{5,7\\}$ in that case $n=3$ and lets say that $k=2$. $|A1 \cup A3| =5$ or $|A2 \cup A3| =5$ will yield the biggest set In contrast to $|A1 \cup A2|$ = 4.

If this is np hard question (i don't know if it is) a good Approximation will be fine I think that brute force is $O({n \choose k})$ operations.

# Answer
> 3 votes
Your problem is known as the Maximum coverage problem. If $S$ is a solution (a set of at most $k$ sets), then an element is covered if it belongs to $\cup\_{X \in S} X$. You want to find a solution that maximizes the number of covered elements. This problem is known to be $\textrm{NP}$-hard (see below for a possible reduction) and admits a greedy approximation algorithm that will cover at least a $\left( 1- \frac{1}{e} \right)$-fraction of the elements covered by an optimal solution.

In addition, there is an easy reduction from $3$-SAT to your problem.

Consider an instance of $3$-SAT with $n$ variables $x\_1, \dots, x\_n$ and $m$ clauses $C\_1, \dots, C\_m$. You can obtain an instance of your problem by creating two sets $T\_i$ and $F\_i$ for each variable $x\_i$. The sets are defined as follows:

* $T\_i = \\{ j \mid x\_i \in C\_j \\} \cup A\_i$ ;
* $F\_i = \\{ j \mid \overline{x\_i} \in C\_j \\} \cup A\_i$,

where $A\_1, \dots, A\_n$ are arbitrary pairwise-disjoint sets, each containing $m+1$ integers between $m+1$ and $m+n(m+1)$.

Deciding whether you can select $n$ sets such that their union has cardinality at least $m+n(m+1)$ is now equivalent to deciding whether the $3$-SAT formula is satisfiable.

---
Tags: algorithms
---