# Question
Title: Is there a model of computation based on discrete event dynamic systems?
I asked a question here about discrete event dynamic systems. They are systems whose state evolution depends on asynchronous events. It can be combined with flow to produce a hybrid system.

There must be an event-based model of computation, since it is so applicable to user interactions. Could someone point me in the right direction? Is there a canonical model of computation for event-based systems?

# Answer
Let's first look at what Wikipedia says:

All of these are mathematical formalisms to model the behavior of discrete event systems. To be more precise, for each of them, there is a whole family of related formalisms, and many more formalisms exist outside of these families, thousands or tens of thousands in all, ranging from very popular to very obscure.

You're looking for ones that are *event*-based. Flow-based models are often considered to be event-based: what flows in can be regarded as a stream of events. Furthermore, finite automata were conceived of as an event-based formalism: they were introduced in a memo titled ''Representation of Events in Nerve Nets and Finite Automata''. Concurrent modeling techniques (e.g. Kahn process networks, Petri nets, Communicating Sequential Processes) are often based on finite state machines or variants of that idea. Techniques based on communicating state machines operating in parallel are popular in industry. Their models consist of components passing messages, or events, or data items, to each other over channels. This is really flexible: you can use it for modeling events, or dataflow, or literal message passing, or the flow of abstract information in, let's say, some office workflow process.

You say you're looking for something other than flow-based models, something suitable for describing user interaction. I've worked with modeling technology for embedded systems that makes this distinction. It has two kinds of communication:

* *asynchronous*: used for data flow processing or event flow processing where data or events flow in on a streams, have a bit of processing done, then flow out on another stream
* *synchronous*: procedure calls: one party instigates communication and waits for the response, the other party responds; used for interaction where the volume of communication is low and the calling party needs a result to continue, for instance, user interaction

I think most proponents of concurrent modeling techniques will tell you they don't need to have synchronous communication in their technique because they can emulate it. For instance, this

is how you express a synchronous call in the Petri-net based process modeling tool I used to work on. As you can see, the circles represent states or conditions, but also data items, while the squares represent state transitions. Control flow and data flow are both expressed, but not distinguished within the modeling technique. But this is unusual: techniques based on communicating state machines do separate state changes (within the machines) from event/data passing (between the machines).

Furthermore, there's a movement in systems design and programming that says to avoid synchronous communication in the first place. Systems should be concurrent and event-based by design, all the waiting for replies on synchronous calls just holds up your components for no other reason than your own ineptness at design, synchronous calls are just mental laziness induced by having looked at inherently sequential systems for too long. This approach to interactive applications has gained a lot of traction in recent years.

So many people in this area will say you don't need separate modeling constructs for user interaction: a user input and output to the user are just communications, flowing on communication channels between two system components, one of which is the user. It's message passing and all you need is a message passing formalism.

An alternative to modeling I/O as messages within the system is to model inputs and outputs as properties of state transitions. For instance, this is done in Mealy machines and I/O automata. This is used for model-based testing: the expected behavior of the system is modelled using an I/O automaton and used to generate test cases that are then used to verify whether the actual system meets the specifications. This approach is really focused on interactive systems, not flow-based systems.

So there are many approaches to choose from; none of them can be said to be canonical, but approaches based on some form of state machines are the most popular, so if you'd insist on calling anything canonical, I'd say it's the state machine.
> 1 votes

---
Tags: computation-models
---


# Question
Title: Understanding integer factorization is NP
I can see that Integer factorization problem is in NP. I am looking for a simple intuition behind this. For example if we take the problem of sorting the complexity is $n\log n$ for merge/quick sort where $n$ is the number of objects to be sorted. Along that line if take $n$ as the number to be factorized, then factorization algorithm can be run in polynomial time (checking from 2 to $\sqrt{n}$). I understand this is not the case. Please give how to look it this problem compared to that of sorting problem.

# Answer
The flaw in your reasoning is in considering $n$ as the size of the input.
The input is a number $n$ and its size in memory is $\lfloor \log\_2(n) + 1 )\rfloor$ bits.

Thus, $O(\sqrt n)$ is not polynomial in the size of the input.

In order to be polynomial, you would need an algorithm with time complexity $O(\log^k n)$ which would correspond to a polynomial algorithm of order $k$ w.r.t. the size of the input.
> 3 votes

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


# Question
Title: Understanding the "ordering of the four types of edges" in DFS
The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).

> Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge according to whether $(u,v)$ or $(v,u)$ is encountered first during the depth-first search is equivalent to classifying it according to the ordering of the four types in the classification scheme.

***Problem:*** What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to? What is supposed to prove?

---

The classification scheme is defined on page 609:

> We can define four edge types in terms of the depth-first forest $G\_{\pi}$ produced by a depth-first search on $G$:
>
> 1. ***Tree edges*** are edges in the depth-first forest $G\_{\pi}$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
> 2. ***Back edges*** are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree.
> 3. ***Forward edges*** are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
> 4. ***Cross edges*** are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

---

***Added Example:***

Consider the figure below.

Suppose that a DFS starts from node $u$ and travels along $(u,x)$ first and then $(x,v)$. Both $(u,x)$ and $(x,v)$ are tree edges.

What about the edge $(v, u)$? It should be a back edge according to the classification scheme in the textbook. How is $(v,u)$ classified as back edge according to the classification in the exercise?

Is $(v,u)$ a tree edge while $(u,v)$ a back edge according to the definition in the exercise? This is strange, because in an undirected graph, $(u,v)$ and $(v,u)$ refer to the same edge.

# Answer
I have reviewed section 22.3, "Depth-first search" a couple of times.

> "What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to?

While quoting the textbook, You have used 1, 2, 3 and 4 to label the four cases in the classification scheme. That is an ordering. All it means is that $1 \prec 2 \prec 3 \prec 4$. In other words, tree edges precede back edges, which precede forward edges, which precede cross edges.

---

> What is supposed to prove?

Suppose we have done a depth-first search $S$ on an undirected graph $G$ that has produced the depth-first forest $G\_\pi$ as describe in the textbook.

An edge $e=\\{u,v\\}=\\{v,u\\}$ can be represented by either the directed edge $(u,v)$ or the directed edge $(v,u)$. Note that $(u,v)\not=(v,u)$. Both $(u,v)$ and $(v,u)$ will be explored during $S$. There are two methods to classify $e$ with respect to $S$.

1. $e$ is classified as the earliest type of edge (according to that ordering) which either $(u,v)$ or $(v,u)$ can be classified as.
More specifically, if either $(u,v)$ or $(v,u)$ is classified as a tree edge, then $e$ is classified as a tree edge. Otherwise, $e$ is classified as a back edge. Note that at least one of $(u,v)$ and $(v,u)$ must be classified as either tree edge or back edge (theorem 22.10 of the book).
2. If $(u,v)$ is discovered earlier than $(v,u)$, then $e$ is the same type of edge as $(u,v)$. If $(v,u)$ is discovered earlier than $(u,v)$, then $e$ is the same type of edge as $(v,u)$.

That exercise asks readers to prove the above two classifying methods are equivalent. That is, $e$ is classified as type $X$ by the first method if and only if $e$ is classified as type $X$ by the second method, given any edge $e$ and any type $X$.

(Somewhat informally, an edge is a tree edge if it appears in the resulting tree; otherwise it is a back edge. This seems to be the simplest way to label edges in an undirected graph with respect to a DFS.)

---

Let us take a look at the example given in the question.

Here is the relevant part of running DFS-VISIT $(G,u)$.

1. $u.d = 1$
2. $x.\pi = u$
3. $x.d = 2$
4. $v.\pi = x $
5. $v.d = 3$
6. Now we discover edge $(v,u)$, which connects $v$ to $u$, which is an ancestor of $v$ since $v.\pi=x$ and $x.\pi = u$. That is, $(v,u)$ is a back edge. This is the first time edge $e$ is discovered. So $e$ is a back edge according to second classifying method.
7. $v.f = 4$
8. $x.f = 5$
9. Now we discover edge $(u,v)$, which connects $u$ to its descendant $v$. This edge $(u,v)$ is classified as a forward edge. Since $(v,u)$ is classified as a back edge, a type of edges that precedes a forward edge, $e$ is a back edge according to the first classifying method.
10. $u.f = 6$

We just saw that $e$ is classified as the same type of edge according to either classifying method. That exercise asks readers to prove that is not a coincidence.
> 4 votes

---
Tags: graphs, terminology, graph-traversal
---


title: Is exponentiation in P?

text:
# Question
Title: Is exponentiation in P?
I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?

* Inputs: two numbers $(a,b) \in \mathbb{N}$
* Output: $a^b$

# Answer
> 7 votes
Your problem is not in P, for two different reasons:

1. P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.
2. The output could be exponentially large in the input length: encoding $b$ takes about $\log b$ bits, but encoding $a^b$ takes about $b \log a$ bits.

This still leaves open the possibility that the following problem is in P:

> Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.

While I don't know what the answer to this question is, here is a related problem in FP:

> Given natural numbers $a,b,c$, determine $a^b \bmod c$.

This can be shown using the important technique of repeated squaring.

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


# Question
Title: Choosing correct action in bottom up parsing
Using grammar:

$ S \to aABe \\ A \to bcA \mid c \\ B \to b $

to bottom parse a string $abcccde$, the course of action would be: $ \begin{array}{c|c|c|c} \hline Step & Stack & Input & Action \\ \hline 1 & \epsilon & abccde & Shift \\ 2 & a & bccde & Shift \\ 3 & ab & ccde & Shift \\ 4 & abc & cde & Shift \\ 5 & abcc & de & Reduce \\, by \\, A \to c \\ 6 & abcA & de & Reduce \\, by \\, A \to bcA \\ 7 & aA & de & Shift \\ 8 & aAd & e & Reduce \\, by \\, B \to d \\ 9 & aAB & e & Shift \\ 10 & aABe & \epsilon & Reduce \\, by \\, S \to aABe \\ 11 & S & \epsilon & Done \end{array} $

My questions are:

1. At step 4, why do we choose to Shift rather than to reduce $ A \to c$.
2. How would a parser decide which is correct to choose?

# Answer
1. Because it will allow the string to be parsed. I know that is not a very satisfactory answer, but it really is the only answer. It is similar to asking why a particular step in a proof was chosen, and not some other step: because whoever wrote the proof (or, in this case, the derivation) somehow figured out how to do it.
2. That depends on the algorithm used by the parser. It might try one action, see if it works, and if not backtrack and try the next possibility. It might try both actions in parallel, reporting only the succesful one(s) at the end. It might have an analysis of the grammar that lets it know what to do in particular circumstances. You will probably see various different techniques as your course continues.
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Do "compiler" and "assembler" correspond to frontend and backend phases of a compiler?
In Compilers: Principles, Techniques, and Tools (2nd Edition) 2nd Edition by Alfred V. Aho (Author), Monica S. Lam (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author) , Figure 1.5 gives a language processing system, and Figure 1.6 shows the phases of a compiler. In Figure 1.6, if I am correct, a compiler has a front end (the first four phasesin Figure 1.6) and a backend (the last three phases "machine independent code optimizer", "code generator" and "machine dependent code optimizer" in Figure 1.6).

Literally by the names, the "compiler" in Figure 1.5 should correspond to the all 7 phases of a compiler in Figure 1.6.

But when I try to understand the individual phases of a compiler in Figure 1.6, I found that the book says:

> In App endix A, we put the techniques in this chapter together to build a compiler front end in Java. The front end translates statements into assembly- level instructions.

I was wondering:

Does the "backend" of the compiler in Figure 1.6 correspond to the "assembler" in Figure 1.5, and does the "frontend" of a compiler in Figure 1.6 correspond to the "compiler" in Figure 1.5?

Is the "intermediate repesentation" in Figure 1.6 the "assembly program" in Figure 1.5?

I guess the answers are all yes, but Yuval's reply mentions that an assembler does its job in only one way, while the books seems to say that each of the three steps in the backend can be done in more than one ways.

For Figure 1.5 in the book, let's take GCC as an example. In the following figure from https://medium.com/@andrewlindburg/gcc-main-c-explained-1287d91b12a7, what phases does the compiler perform, and what does the assembler perform? Does "compiler CC1" perform the first four phases in Figure 1.6, and does the "assembler AS" perform the "assembler" in Figure 1.5 and to the backend (i.e. the last three phases) in Figure 1.6 in the book above?

Thanks.

# Answer
> 5 votes
Some compilers translate source code to assembler code in one or more phases, then use an assembler which will produce bit patterns of the instructions needed, and store them in a file that the linker understands.

Many compilers don’t do this. Producing code in assembler (human readable) form takes time. Parsing the human readable form, which is the first thing the assembler has to do, takes time again. Substantial time, actually. By generating the output directly that the linker needs, substantial time can be saved.

So usually there is no assembler involved.

And please note that (1) all these charts are just *examples* of how you could. The UCSD Pascal compiler had one single phase for compiling. And (2) gcc is more than a compiler. There is no iron rule how a compiler has to be organized. It's just a program, and the developers of that program figure out a good way to make the software work.

PS. Do “compiler” and “assembler” in Figure 1.5 and in the GCC figure respectively correspond to frontend and backend phases of a compiler in Figure 1.6? Absolutely not. The whole Figure 1.6 is just a more detailed view of the "Compiler" box in Figure 1.5.

# Answer
> 2 votes
The "front end" of the compiler is the part that is intimately related to the source language, the "back end" depends on the target. Many back ends emit assembly language for convenience (the object file contains not only binary instructions, but also places to fill in with addresses of external variables and functions, data for patching up to be placed at different addresses in memory, ...).

This separation (and the interpolation of the ridiculously named "middle end") was fueled by the desire of getting compilers for lots of languages for a plethora of targets. Less pressing today, but there are still differences between CPU makes and models. The "middle end" collects lots of language- and target-independent transformations that aim at better code (get rid of code that never runs, use knowledge that e.g. a variable can't be zero to avoid to check for this, compute common expressions just once, handle tail recursion, the list is long).

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


# Question
Title: Karp hardness of directed monochromatic triangle problem
Monochromatic problem is a classic NP-complete problem.

Does the complexity stay NP-complete if we use directed graph?

**DIRECTED MONOCHROMATIC TRIANGLE** problem:

> **Input**: A digraph $G(V,A)$
>
> **Output**: **YES** if there exists a triangle-free bipartition of $A$, otherwise **NO**.

A triangle-free bipartition of $A$ is a partition $A=A\_1\dot{\cup}A\_2$ such that both $G\[V,A\_1\]$ and $G\[V,A\_2\]$ are triangle-free.

Note that a triangle in a digraph is the set of $3$ vertices $\\{u,v,w\\}$ such that $(u,v),(v,w),(w,u)\in A$. It means that we only allow triangle that has *consecutive* arcs. For example, $(u,v),(u,w),(w,u)$ does NOT form a triangle.

# Answer
> 3 votes
All directed graphs can be edge-partitioned into two subgraphs that are acyclic and therefore triangle free.

Let $\prec$ be any total ordering of the vertices. For each edge $(u, v) \in A$, put it in $A\_1$ if $u \prec v$, and in $A\_2$ otherwise. Both $(V, A\_1)$ and $(V, A\_2)$ must be acyclic.

---
Tags: graphs, np-complete, np-hard, np, partitions
---


# Question
Title: Prove: Every decidable set is Turing reducible to the empty set
Question- Prove: Every decidable set is Turing reducible to the empty set.

Can anyone help me with this please?

All reductions tutorials I've seen use practical examples of reduction such as sipser's introduction to computation theory:

"A reduction is a way of converting one problem to another problem in such a way that a solution to the second problem can be used to solve the first problem. ... For example, suppose that you want to find your way around a new city. You know that doing so would be easy if you had a map. Thus, you can reduce the problem of finding your way around the city to the problem of obtaining a map of the city"

I don't see how to use this kind of information as a general proof, or how the empty set is even usable to solve anything else in a practical example even.

# Answer
You're trying to prove something, so you need to use something closer to an actual definition of Turing reducibility. The statement you quote from Sipser is an intuition about what reductions do, but it's not precise enough to let you solve problems.

Here's an informal definition of Turing reducibility that lets you start to reason about what it can do.

> A set $A$ is Turing-reducible to a set $B$ if, assuming the existence of a subroutine that determines whether its input is in $B$, we can write a program that determines whether its input is in $A$.

We're considering $B=\emptyset$, so we need to assume the existence of a subroutine that determines whether its input is in $\emptyset$. Well, that's not much to assume. Here's the subroutine:

```
 return false

```

OK – we don't need to assume anything: we know this subroutine exists. So now, we just need to show that every decidable set is Turing reducible to $\emptyset$. That is, we need to show that

> For every decidable set $A$, we can write a program that determines whether its input is in $A$.

So... what's the definition of decidable?
> 5 votes

# Answer
2 languages A and B. If B is \<= t A, then A is \<=t B. run A on B until {}, if A is {} (empty), then B is {}.
> -5 votes

---
Tags: turing-machines, reductions, sets
---


title: Number of steps in worst Case

text:
# Question
Title: Number of steps in worst Case
we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full) and then only way to test if the battery full or empty is to put them in the Walkman and try it out.we can not tell which one is empty or full (one we put inside one full and one empty).

The question is to find the maxmium needed step to run the walkman (to find 2 full batteries)

I modelled the problem like that : let s that the Walkman is a function f which take two argumments and it return 1 it the walkman works ,and 0 otherwise. $$ f: \\{b\_1,b\_2 \dots b\_{30}\\} \times \\{b\_1,b\_2 \dots b\_{30}\\} \rightarrow\\{0,1\\}$$

The answer for the question was at most 18 steps , but somehow i could not figure it out. Any good suggestion how to proceed ?

# Answer
> 1 votes
You arrange your 30 batteries in pairs, where each pair consists of either:

* 2 empty batteries
* 2 full batteries
* 1 full and 1 empty battery

If you have a pair with 2 empty batteries it follows, that there is also a pair of 2 full batteries, thus, you have to test at most all of the pairs (15 steps) until you find a pair of two full batteries.

If your walkman isn't working after testing all 15 pairs, you know that each pair consists of a full and an empty battery. You take the first two pairs with batteries (a,b) and (c,d). You then try the pairings: (a,c), (a,d) and (b,c). You have now tested 18 combinations and either one of them worked or (b,d) has to be a working pair.

I don't know if this counts as 19 steps for your purposes (you have found 2 full batteries after 18 steps but the walkman is not running yet).

---
Tags: algorithms, efficiency
---


# Question
Title: distinguishing between CTL* formulas $A[FG p]$ and $AFAG p$ using transition system
It is to show, using a transition system, that the two formulas $A\[FG p\]$ and $AFAG p$ are **not** equivalent.

For me, it seems strange that they are not equivalent.

As the first one says that any computation path eventually has $p$ always true.

And the second one says that any computation path contains a state such that any path starting at this state has $p$ always true.

Aren't they equivalent?

# Answer
(This is the "standard" example which proves that CTL is not a superset of LTL, in terms of expressiveness)

Consider this system:

* state $q0$, transitions to $q0$ and $q1$
* state $q1$, transition to $q2$
* state $q2$, transition to $q2$

Let $p$ be true in $q0,q2$ but not in $q1$.

```
(p)     (not p)    (p)
 q0 ----> q1 ----> q2
| ^               | ^
\-/               \-/

```

State $q0$ does not satisfy formula $AF\[AGp\]$. Take the infinite path $q0,q0,q0,\ldots$. There is no state in the path satisfying $AGp$ since we can only pick $q0$ and from there the path $q0,q1,q2,q2,q2,\ldots$ does not satisfy $Gp$ since $q1$ does not satisfy $p$.

State $q0$ however satisfies $A\[FGp\]$. Take any infinite path starting from $q0$. Either it is of the form $q0,q0,q0,\ldots$ or of the form $q0,q0,q0,\ldots,q0,q1,q2,q2,q2,\ldots$. Both forms satisfy $FGp$.
> 3 votes

---
Tags: linear-temporal-logic, temporal-logic
---


title: Context-Free Grammar from this language

text:
# Question
Title: Context-Free Grammar from this language
I'm having difficulties with an exercise in a theoretical CS class. The problem is:

let $L\_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast one "a".

What is the CFG that creates $L\_{2}$?

I'm struggling since 2h... I've found out that for example "abba" is not in the language, but to write it formally is quite difficult. Help would be much appreciated.

# Answer
As Aspass.Jack wrote in the comments, let's first define $L\_3$ to be the language where each $a$ is followed by at least 2 $b$'s, and $L\_4$ to be the language where each $b$ is followed by at least one $a$.

Now, if let's say you can define CFGs for $L\_3$ and $L\_4$ with start symbols $S\_3$ and $S\_4$. Then, we simply need to define a grammer with the transition: $$S \rightarrow S\_3|S\_4$$ together with all the transitions from the other 2 CFGs. Hopefully this simplifies your problem.
> 0 votes

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: How to prove the following: Every set is Turing reducible to itself
Question: Prove the following: Every set is Turing reducible to itself.

If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as you like for my sake if not strictly for the answer. Thanks!

# Answer
> 5 votes
Informally, $A$ is Turing reducible to $B$ if you can figure out what $A$ is by asking questions to $B$.

A bit more formally, $A$ is Turing reducible to $B$ if there's some algorithm you can use to figure out whether a number is in $A$ by asking questions about whether or not various numbers are in $B$. For example, an instance of a Turing reduction between $A$ and $B$ might look like the following:

* I want to figure out whether $3$ is in $A$.
* I ask $B$, "Is $17$ in you?"
* $B$ says **yes**.
* I now say, "Okay, based on that answer I now want to ask: is $42$ in you?"
* $B$ says **no**.
* I say, "Great! Now I know that $3$ **is** in $A$.

So, you're trying to do the following: given some arbitrary set $A$ and an arbitrary number $n$, **find a way to figure out whether $n$ is in $A$ by "querying" $A$.** (*HINT*: don't overthink this ...)

---

Incidentally, Turing reductions don't have to be efficient, or non-stupid, or anything else nice; they just have to *work*. For example, in the problem you're trying to solve, there is a "best" Turing reduction; but we could *also* modify that reduction to pointlessly ask "Is $17$ in $A$?" at the end for absolutely no reason, and simply ignore that extra information.

---
Tags: turing-machines, reductions
---


title: Nim game tree minimax

text:
# Question
Title: Nim game tree minimax
Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player alternatively thereafter does the same to some single stack when it is his turn to play. The game proceeds until each stack has either just one penny or two—at which point continuation becomes impossible. The player who first cannot play is the loser. Show, by drawing a game tree, whether any of the players can always win.

My question is why does 4-2-1 not go to 2-2-2-1 ?

# Answer
> 1 votes
According to the rules:

> player divides the original stack into two stacks that must be **unequal**.

---
Tags: board-games
---


# Question
Title: Algorithm for commonalities across related objects
I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application.

The problem is give the data below (two columns) find those ids where the linkedId matches entirely:

**Input**

```
id  linkedId
1   103
2   107
1   107
2   103
4   64
6   120
7   107
8   180
7   64
9   129

```

**Expected output** \[1,2\] as the linkedIds match entirely for the two ids

As I look at the data, I would envisage a graph of some description so that I can establish the various links between the ids and linkedIds but I am at a loss as to how to approach this.

I do not want a solution but more guiding in the right direction.

Thanks

# Answer
I came up with the idea of hashing when I just started looking at this, but seems that the range of the input data is not given, so it's very hard to decide on a specific algorithm.

However, there's another idea:

1. During input, create a table for each `id`, record all the `linkedId` of it, and the **sum of `linkedId`s** of it.
2. After recording all the input, you have tons of ways to find those `id`s whose **sum of all `linkedId`s** are the same, put them into groups, like an $O(n^2)$ brute-force or some $O(n\log(n))$ discretization. This step is a kind of classification, all `id`s in a group may not be the equivalent, but equivalent `id`s must be in the same group
3. Traverse through all groups, find those equivalent `id`s

This is expected to be a lot more efficient than brute-force. Hope it can help you.
> 1 votes

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


title: Double floating precision exercise

text:
# Question
Title: Double floating precision exercise
today I had to deal with this exercise:

> If $x \approx y$, we might expect some cancellation in computing $log(x)- log(y)$. On the other hand, $log(x) - log(y) = log(\frac{x}{y})$, and the latter involves no cancellation. Does this mean that computing $log(\frac{x}{y})$ is likely to give a better result? (Hint: For what value is the log function sensitive (highly elastic)?)

I would assume that in double precision the second expression would be more accurate, but replicating the calculations in R did not show any differences between these two expressions.

```
x1 <- (1/0.999999999999)
y1 <- (1/0.99999999999999)

log(x1)-log(y1)
log((x1/y1))
1/log(1.00000001)

```

# Answer
There is some inaccuracy in the result that is independent of how the result is computed. Basically, even if I did the computation to infinite precision, I would still get some error because the inputs were uncertain. The latter method may help when it is impractical to perform the operation with a bit of extra precision before rounding (as is common in multiple-precision libraries).

As far as independent error, say an estimate $\overline{x}$ of $x$ has a relative error of $\epsilon\_x$ and an estimate $\overline{y}$ of $y$ has a relative error of $\epsilon\_y$. Then we have $\overline{x}=x\\,(1+\epsilon\_x)$ and $\overline{y}=y\\,(1+\epsilon\_y)$. Note that these relative errors may be negative, indicating a smaller result than expected. Then the independent relative error $\epsilon$ in the result is found to be $$\begin{align\*} \epsilon&=\frac{\log(\overline{x})-\log(\overline{y})}{\log(x)-\log(y)}-1\\ &=\frac{\log(x)-\log(y)+\log(1+\epsilon\_x)-\log(1+\epsilon\_y)}{\log(x)-\log(y)}-1\\ &=\frac{\log(1+\epsilon\_x)-\log(1+\epsilon\_y)}{\log(x)-\log(y)}\\ &=\frac{\log\left(\frac{1+\epsilon\_x}{1+\epsilon\_y}\right)}{\log\left(\frac{x}{y}\right)}=\frac{\log\left(1+\frac{\epsilon\_x-\epsilon\_y}{1+\epsilon\_y}\right)}{\log\left(\frac{x}{y}\right)}\\ &\approx\frac{\epsilon\_x-\epsilon\_y}{\log\left(\frac{x}{y}\right)}\\ \end{align\*}$$ So if $x$ and $y$ are similarly sized, the resulting relative error will be horrible no matter how much extra precision is added in computing the result (except if the two relative errors cancel out, but you can never plan on that).

The following Python code demonstrates the precision gain (double precision) from using division (checked against mpmath) as well as the independent loss of precision from using inexact values:

```
def relerr(xbar, x):
    return xbar/x-1

x,y = 1+1e-10,1+1e-10-1e-11
xbar,ybar = x*(1+1e-12),y*(1+1e-12-1e-14)
sub,div,l1p = log(xbar)-log(ybar),log(xbar/ybar),log1p((xbar-ybar)/ybar)
tsub,tdiv,tl1p = log(x)-log(y),log(x/y),log1p((x-y)/y)
mp.prec = 1000
for val in ['sub','div','l1p','tsub','tdiv','tl1p']:
    true = mp.log(mpf(x)/mpf(y))
    print(val+': '+mp.nstr(relerr(mpf(eval(val)),true)))

```

This prints

```
sub: 0.000999201
div: 0.000999201
l1p: 0.000999201
tsub: -8.9999e-11
tdiv: 0.0
tl1p: -9.0e-11

```

You will observe that rewriting using division resulted in zero measurable error compared to the `9e-11` introduced error from the subtraction. You can also see the large increase in relative error (from `1e-12` to almost 0.1%) when using inexact values that are close. If the relative errors have opposite signs, the effect is even worse.
> 1 votes

# Answer
Assume that every single operation has a relative error ≤ eps. Starting with this, what if x = 1.001 and y = 0.999, or x = 10.01 and y = 9.99, or x = 1,001,000,000 and y = 999,000,000? How is log (x / y) affected, and how is log (x) - log (y) affected?
> 1 votes

---
Tags: floating-point
---


# Question
Title: How does one formally show that two lambda functions are $\alpha$ equivalent?
I was going through the following slides and I wanted to show the following:

$$ \lambda x. x \equiv\_{\alpha} \lambda y . y$$

formally. They define a an $\alpha$-conversion on page 15 as follows:

$$ \lambda x . E = \lambda z.(E\[x \leftarrow z\])$$

however, I wasn't sure how to formally show the statement I am trying to show. Essentially I guess I don't know how to formally show in a proof that two distinct objects actually belong to this same equivalence class. The intuition and idea is clear, but how do I know if I've shown the statement?

In fact if someone can show me how to do the more complicated one too that would be really helpful too:

$$ \lambda x.x (\lambda y . y) \equiv\_{\alpha} \lambda y . y (\lambda x. x)$$

how do I know if I've shown what is being asked?

---

Actually I think page 16 is the one thats confusing me most:

> Using the equation above, one has now the possibility to prove $\lambda$-expressions "equivalent". To capture this provability relation formally, we let $E \equiv\_{\alpha} E^\prime$ denote the fact that the equation $E = E^\prime$ can proved using standard equational deduction form the equational axioms above (($\alpha$) plus those for substitution).
>
> **Exercise 3** *Prove the following equivalences of $\lambda$-expressions:*
>
> * $\lambda x.x \equiv\_{\alpha} \lambda y.y$,
> * $\lambda x.x (\lambda y.y) \equiv\_{\alpha} \lambda y.y (\lambda x.x)$,
> * $\lambda x.x(\lambda y.y) \equiv\_\alpha \lambda y.y(\lambda y.y)$.

what does:

> can be proved using standard equational deduction from the equational axioms above

mean?

---

Since there is already an answer that is not helping (because I don't understand the notation) I will add what I thought was the answer but I'm not sure:

I would have guessed that:

$$ \lambda x. x \equiv\_{\alpha} \lambda y . y$$

if and only if there is a variable such that if we plug it into the lambda functions evaluates to the same function with the same variables. i.e.

$$ \lambda x. x \equiv\_{\alpha} \lambda y . y \iff \exists z \in Var : \lambda x . x = \lambda z. ( (\lambda y . y)\[y \leftarrow z\] )$$

if we set $z = x$ we get:

$$\lambda z. ( (\lambda y . y)\[y \leftarrow z\] )$$ $$\lambda x. ( (\lambda y . y)\[y \leftarrow x\] )$$ $$\lambda x. (\lambda x .x )$$

which I assume the last line is the same as $\lambda x .x$ but I am not sure. If that were true then I'd show I can transform $\lambda y . y$ to $\lambda x . x$ which is what I assume the equivalence class should look like. Where did I go wrong?

# Answer
By definition of substitution we have $$x \[x \leftarrow z\] = z$$ therefore $$\lambda z . x \[x \leftarrow z\] = \lambda z . z \tag{1}$$ because $\lambda$-abstraction is a congruence (it preserves equality). By the definition of $\alpha$-equality we have $$\lambda x . x = \lambda z . x \[x \leftarrow z\] \tag{2}.$$ By transitivity of equality we get from (1) and (2) that $$\lambda x . x = \lambda z . z$$ If you require more details than this, you should use a computer proof assistant to check the details.
> 5 votes

# Answer
To be at least semi-formal, we can exploit these facts:

1. $\lambda x.M \equiv\_\alpha \lambda y.(M\[x \leftarrow y\])$ when $y$ is a variable not occurring free in $M$
2. The relation $\equiv\_\alpha$ is an equivalence relation. In particular, it is transitive, so we can perform the renaming of point 1. as many times as we want
3. The relation $\equiv\_\alpha$ is also a congruence, which means that "we can perform renaming in subterms as well". More formally, when $A \equiv\_\alpha B$ then we have $M\[x\leftarrow A\] \equiv\_\alpha M\[x\leftarrow B\]$ -- i.e., we can replace any occurrence of $A$ in a larger term with $B$, and the result will be $\alpha$ congruent.

So, for the exercises:

* $\lambda x.x$ by point 1 can be rewritten as $\lambda y.(x\[x\leftarrow y\])$ which by definition of substitution is $\lambda y.y$
* $\lambda x.x(\lambda y.y)$ by point 1 can be rewritten renaming $x$ into $y$. We can do this since $y$ is not free in $x(\lambda y.y)$. So, we get $\lambda y.y(\lambda y.y)$. Then we can apply the symmetric result we have proven before, i.e. $\lambda y.y \equiv\_\alpha \lambda x.x$, and get (by congruence, point 3) the wanted $\lambda y.y(\lambda x.x)$. Since we performed two renamings, we implicitly relied on transitivity (point 2).

Finally, the sentence

> can be proved using standard equational deduction from the equational axioms above

simply means: this can be proved by replacing some subterms with equivalent terms, possibly many times.

"Equational reasoning/deduction" refers to the process of substituting in a larger formula some subformula with an equivalent one, as if the two formulas could be assumed to be "equal", in some sense. This approach applies whenever we are working with a congruence relation.
> 4 votes

# Answer
The operation $\[x \gets z\]$ is defined inductively on the structure of the expression it is applied to. In particular, one of the rules is $x\[x \gets z\] = z$. This immediately implies $\lambda x.x \equiv\_\alpha \lambda y.x\[x\gets y\] = \lambda y.y$.
> 0 votes

# Answer
My confusion was that the definition is not that there exists a variable name such that the two functions are equal (which I believe is a better definition, probably equivalent to the one provided). Instead they impose the following equational axiom:

$$ \lambda x.E = \lambda z.(E\[x \leftarrow z\]) $$

So we have:

$$ \lambda x.x = \lambda y.(E\[x \rightarrow y\]) $$

by equational axiom. Then:

$$ \lambda y.x\[x \rightarrow y\] = \lambda y.y$$

by realizing that $E = x$ and that substitution of $x$ for $y$ results in $y$ i.e.

$$ E\[x \rightarrow y\] = x\[x \rightarrow y\] = y$$

which results in:

$$ \lambda x.x = \lambda y.(E\[x \rightarrow y\]) = \lambda y.x\[x \rightarrow y\] = \lambda y.y $$

all in one line.
> 0 votes

---
Tags: programming-languages, lambda-calculus, functional-programming
---


# Question
Title: Find the number of strings in the language $(∅∅^∗ + ∅)$
Consider the language $L = \emptyset\emptyset^∗ + \emptyset$.

How many words does $L$ contain? Zero or one?

*Note*: $\emptyset^∗ =\\{\epsilon\\}$.

# Answer
Your language could be simplified as follows, using $\emptyset^\* =\\{\epsilon\\}$:

$$ \begin{align\*} L(\emptyset\emptyset^\*+\emptyset) &=L( \emptyset . \\{\epsilon\\} + \emptyset) \\ &=L(\emptyset +\emptyset) & (\emptyset.\\{\epsilon\\}=\emptyset) \\ &=L(\emptyset) & (\emptyset + \emptyset = \emptyset) \end{align\*} $$

So the language L accepts empty language which is $L =\\{ \\}$, which means that it contains zero elements.

Please be aware that the empty language is different from language consisting of the empty string, which is $L =\\{\epsilon\\}$, and which contains the element $\epsilon$, while the empty language contains zero elements.
> 2 votes

---
Tags: regular-languages, regular-expressions, strings, kleene-star
---


# Question
Title: Coin flipping problem on an $n \times m$ grid
There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly:

* Flipping a row of coins;
* Flipping a colomn of coins;
* Flipping a diagonal line of coins;
* Flipping a counter-diagonal line of coins.

The problem is to check whether we can finally let all coins facing up.

As we can see, there are $3n+3m-2$ kinds of transformations in total ($n$ rows, $m$ colomns, $n+m-1$ diagonals, and $n+m-1$ counter-diagonals). However, these transformations are not independent. For example, flipping all rows and then all colomns except the first colomn is equivalent to flipping the first colomn.

By trying some examples $n,m\ge 3$, I find that there are $3n+3m-9$ kinds of independent transformations in total. Other 7 transformations can be done by combining the $3n+3m-9$ kinds of independent transformations. Using Xor-Gaussian elimination we can check the correctness of the proposition.

If we can prove the above proposition, we can solve the problem in this way:

In the following image, there are $3n+3m-9$ shaded lattices. For any state of coins of these lattices (facing up or facing down), we can always use the above transformations to face up all coins of these shaded lattices (according to the order in the image to face them up). Also, for other unshaded lattices, their state will be uniquely determined. Then we can check whether we can finally let all coins facing up in $O(nm)$ time.

But it seems difficult to prove the independent proposition. Does anybody have some ideas on it? Thank you!

# Answer
> 2 votes
This is just linear algebra. Let $x$ be the vector over $\mathbb{Z}\_2$ representing the initial state of the board, and let $y$ be the goal state of the board. Let $v\_i$ be the vectors corresponding to the allowed flips (flipping corresponds to adding some $v\_i$). Then we want to check whether $x+y$ is in the span of the $v\_i$.

---
Tags: discrete-mathematics, matrices, xor
---


# Question
Title: How does one show $(\lambda x . (\lambda y.x))yx \equiv_{\beta} y$ in lambda calculus?
I wanted to show:

$$ (\lambda x . (\lambda y.x))yx \equiv\_{\beta} y $$

the definition of beta equivalence is on page 17 of these notes.

I did a few attempts but got different things like $x$. I think my main confusion is how to interpret:

$$ yx $$

at the end. Does that mean we are applying $x$ to $y$ or that we are applying $yx$ to the lambda function $(\lambda x . (\lambda y.x))$? I tried both interpretations and didn't get anything that made sense.

I think I understand what $\beta$ conversion means (cuz I could follow the example he gave) but then when I tried doing it myself on this weird example I got non-sense.

# Answer
I will make my answer more sophisticated by using parentheses. The first thing to realize is that $(\lambda x . (\lambda y . x)) y x$ is the same thing as $((\lambda x . (\lambda y . x)) y) x$ because in $\lambda$-calculus application associates to the left, which means that $A B C = (A B) C$. As you can see, $x y$ does not even appear in your expression.

After that, I would follow Yuval's observation that it is impolite to use the same variable for two different purposes: the $x$ and $y$ inside $\lambda$'s are *not* the same as the outer $x$ and $y$. We should rename bound variables to get $$((\lambda a . (\lambda b . a)) y) x$$ Can you do it from here?

P.S. Please stop pelting us with questions about $\lambda$-calculus that all look alike. Take them one at a time, wait for the answers, and *think* about them. It is likely subsequent questions will become redundant.
> 5 votes

# Answer
Here is an unsophisticated answer; undoubtedly more sophisticated ones will pop out in due time.

Let's change the leftmost $y$ to a $z$, to avoid confusion.

When you apply $\lambda x. (\lambda z.x)$ to $y$, you get $\lambda z.y$. When you apply this to $x$ (indeed, to anything at all), you get $y$.
> 2 votes

---
Tags: programming-languages, lambda-calculus, functional-programming
---


# Question
Title: Is every language over any alphabets is accepted by automata?
The answer is no to what i have learned but i am finding difficulties to absorb it reason being . We say for every language we have a grammar as language without grammar makes no sense even in general scenerio also. i have taken this argument as my base for the conclusion of my answer as i found this argument somewhere on stackexchanege please correct me if iam wrong.

coming to point , as there are grammar for every language which also indicate existence of set of rules for the formation of the language. Taking this ahead , i wonder if we can device a set of rules which is indeed a process to derive or generate a solution then why cant we form an automata for the same. Adding more to this point , we know the highest class of automata is turing machines capable of accepting many languages but not all , and we know that the languages not accpeted by turing machines have grammars( as said every language has grammar) means there are some machines automata that does not necessarily satisfies the all the langugaes not accepted by turing machines but do satisfy some but all of them , using this we say there are different classes of machines which are not turing but accept some languages not accpeted by turing machines if this is not true than there must exist the languages that do not have any grammar but as said every languae has grammar. adding more woes to this argument , we have not able to identify any machine more powerful then turing , so this means some of the arguments made here are wrong . but i am finding it difficult to understand which one of them is wrong, so please let me know.

# Answer
> 2 votes
Suppose that $\mathcal{M}$ is any kind of machine model in which every machine has a finite description, say as a binary string. The model can be more powerful than mere Turing machines – for example, it could be Turing machines with access to an oracle for the halting problem.

Since every machine has a finite description as a binary string, there are only countably many machines, and so countably many languages they accept. Since there are uncountably many languages, there must be some language not accepted by any $\mathcal{M}$-machine. In fact, most languages aren't, in the sense that a random language would not be accepted by any $\mathcal{M}$-machine.

The only way out is if machines do not have a finite description. But this is not what we usually understand by *machine*. An example of such a "machine" is one in which an arbitrary language is hardwired. Such machines can, by definition, accept all languages, but they are not so interesting mathematically.

# Answer
> 2 votes
The first premise is wrong. A *language* over an alphabet is just any subset of all strings made from characters of that alphabet. There are uncountably many languages over any alphabet with two or more letters, there are only countably many grammars. So most languages don't have a grammar at all.

Many of these languages are not useful, but they are still languages.

---
Tags: turing-machines, automata, finite-automata
---


# Question
Title: Using Iterative method to find recurrence relation vs Master Theorm
I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem.

$$\begin{aligned} T(n) &= 5T(n/2) +n^2 \\ &= 5^2 T(n/4) + (5/4)n^2 + n^2 \\ &= 5^3 T(n/8) + (5/4)^2 n^2 + (5/4)n^2 + n^2 \\ &= 5^k T(n/(2^k)) + n^2 \sum\_{i=0}^{k-1}(5/4)^i \end{aligned}$$

$n = 2^k =\> \ln(n) = k$

$$\begin{aligned} &=5^{\ln(n)} T(1) + n^2 * \Theta(5^{\ln(n)}) \\ &= n^{\ln(5)} + n^2 * \Theta(n^{\ln(5)}) \end{aligned}$$

$O(n^2 * n^{\ln(5)}) = O(n^{2+\ln(5)})$

Right?

According to the master Theorem,

$a= 5$; $b=2$; $p=0$; $k=2$; $5\>4$

This result in $\Theta(n^{\ln(5)})$ for this problem,

So, do I ignore the $n^2$ in the iterative method? Did I do it incorrectly? If it correct, then why is there a difference between master Theorem and iterative method? Master Theorem have a tighter constraint?

# Answer
Check your maths. The sum with (5/4)^i is much smaller than theta(5^ln n).

Intuitively, T(n) = 5 T(n/2) gives you growth of n^(ln 5)= n^2 * n (ln 1.25). Adding another O (n^2) shouldn't make a difference.
> 0 votes

# Answer
You have been calculating correctly all along, except when it comes to $\sum\_{i=0}^{k-1}(\frac54)^i$, where $n=2^k$.

Note that $\sum\_{i=0}^{k-1}(\frac54)^i = \frac{1-(\frac54)^k}{1-\frac54} = 4((\frac54)^k - 1) = 4\cdot2^{\ln(\frac54)k} - 4 = 4n^{\ln(\frac54)} - 4$, where $\ln(x)$ means $\log\_2(x)$.

So you would have

$$\begin{aligned} T(n) &= 5^k T(n/(2^k)) + 4n^2n^{\ln(\frac54)} - 4n^2 \\ &=n^{\ln(5)} T(1) + 4n^{\ln(5)} - 4n^2 \\ &=(T(1) + 4)n^{\ln(5)} - 4n^2 \\ &= O(n^{\ln(5)}) \end{aligned}$$

The result above obtained by iterative method is, as we should have been expecting, indeed consistent with the result obtained by the master Theorem.
> 0 votes

---
Tags: algorithm-analysis, recurrence-relation, recursion, master-theorem
---


title: Reason for thread pooling

text:
# Question
Title: Reason for thread pooling
Can someone explain what is the reason for **thread-pooling** in `Linux`, even if the threads are light to create and destroy??

# Answer
> 1 votes
Not as light as you think.

Thread pooling is orders of magnitudes lighter, so you can use pooled threads for gazillions of tiny tasks and still be efficient, while the same with freshly created threads would be inefficient.

In my environment, I can use five different threads in ten lines of code (without you even seeing that I'm using threads), which is possible because of highly efficient thread pooling).

---
Tags: threads
---


title: is This reduction possible?

text:
# Question
Title: is This reduction possible?
> If we have $L \in p$ and $L' \neq \emptyset$ and , $L' \neq \Sigma^\*$ . is $L \leq^p L' $ ?

I read this question Reduction between $\Sigma^\*$ and $\emptyset$

Maybe this question is irrelevant to my question, but I'm little seconfused.

# Answer
If $L \in p$, then we can define the reduction function by cases as follows

$$ f(x) = \begin{cases} g(x) & \mbox{if $x\in L$} \\ h(x) & \mbox{if $x\notin L$} \end{cases} $$

where $g,h$ are functions in the same class $p$. Indeed, under such premises, $f$ also belongs to class $p$: it can be computed by first testing whether the input $x$ belongs to $L$, and then computing $g(x)$ or $h(x)$ accordingly. Both of these computation steps belong to class $p$.

If $L'$ is not trivial, we can fix a point $y\_0 \notin L'$ and a point $y\_1 \in L'$, and then let $g(x)=y\_1$ and $h(x)=y\_0$. Since these are constant functions, they are trivial to compute, so they belong to any reasonable class $p$.

You can now verify that $x\in L \iff f(x)\in L'$, proving that $f$ is indeed a reduction.
> 0 votes

---
Tags: reductions
---


# Question
Title: Why did Alan Turing have to define computation before demonstrating undecidability?
It seems to me that Turing could've just presented the following argument:

Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting problem of $\mathcal{M}$ is undecidable from within $\mathcal{M}$.

Proof: Suppose $H$ solves the halting problem in $\mathcal{M}$. Namely $H\in\mathcal{M}$ and $$ H(A) = \begin{cases} 1 & \text{if $A(A)$ halts}\\ 0 & \text{if $A(A)$ doesn't halt} \end{cases}\qquad\forall A\in\mathcal{M} $$

Then construct $$ \begin{split} \overline{H}(A) & = \begin{cases} \infty & \text{if $H(A) = 1$}\\ 0 & \text{if $H(A) = 0$} \end{cases}\\ & = \begin{cases} \infty & \text{if $A(A)$ halts}\\ 0 & \text{if $A(A)$ doesn't halt} \end{cases} \end{split} $$ ($\infty$ indicates an infinite loop. The $0$ could've just as well been a $1$ without affecting the argument.)

Because $H\in\mathcal{M}$ so is $\overline{H}$. After all, it only adds conditional branching and an infinite loop. So we can ask whether $\overline{H}(\overline{H})$ halts - yielding a contradiction in either case. $$\tag\*{$\Box$}$$

It seems to me that with this argument Turing could've just said "I don't care how you define computation. Try coming up with the most powerful notion you can conceive of, then run through this argument, and voila, there's still undecidable problems."

# Answer
> 2 votes
Well, I would like to ask the same kind of question to you.

**Why did Sebastian Oberhoff have to define a computational model before demonstrating undecidability?**

I will answer the above question on behalf of you below, assuming an imaginary line of case development. Of course, you might answer better than me.

Of course, to prove some kind of undecidability, I have to define what it is about. It should be about a general computation model. Whether it is Turing machine, $\lambda$-calculus, or recursive functions, it does not matter much. But I have to **define exactly the meaning of a computation model so that I can proceed to prove some undecidability with mathematical rigor**. My initial thought was that a computational model means some kind of machine that is capable of conditional branching and indeterminate repetition. Then I realized it must be able to simulate another machine of the same kind. So it should be able to encode program as data and decode data as program. It should have some kind of memory. Also it should be able to recognize its own state. And finally I have reached/discovered the basic requirement of a computation model, which, to my surprise, is basically equivalent to what have been found by the father of computer science, Alan Turing, Turing machine. Henceforth, I will humbly refer to my theorem and proof as a modern version of Alan Turing's result.

---

> With this argument Turing could've just said "I don't care how you define computation. Try coming up with the most powerful notion you can conceive of, then run through this argument, and voila, there's still undecidable problems."

Yes, **just as you suspected, Turing did write the same idea with more mathematical rigor**. Here is an excerpt from Wikipedia entry on hypercomputation.

> A computational model going beyond Turing machines was introduced by Alan Turing in his 1938 PhD dissertation Systems of Logic Based on Ordinals. This paper investigated mathematical systems in which an oracle was available, which could compute a single arbitrary (non-recursive) function from naturals to naturals. He used this device to prove that **even in those more powerful systems, undecidability is still present**. Turing's oracle machines are mathematical abstractions, and are not physically realizable.

# Answer
> 2 votes
Without fixing a concrete model of computation, you can't show that you can actually do the "then construct" part of your argument, so it's not a proof.

---
Tags: undecidability, halting-problem
---


# Question
Title: Check if two items are equal after replacing
Let's say that an item is either a natural number or a list of items. Examples of items are:

* 1
* \[2\]
* \[4, \[3, 1\], 3, 4\]

A rule states that two items are equal. For example:

* 1 = 2
* 3 = \[3, 1\]
* \[4, 3\] = \[1, 5\]

When using these example rules, we can transform \[4, \[3, 2\]\] into \[4, \[3, 1\]\] into \[4, 3\] into \[1, 5\] and we can say that \[4, \[3, 2\]\] equals \[1, 5\].

**I want to find an algorithm that, given items $a$ and $b$ and a finite set of rules, determines if $a = b$.**

I already thought of an algorithm that works in some cases. But I hope to find an efficient algorithm that works in all cases. It would also be nice if the algorithm can detect $a \not= b$ instead of infinitely searching for ways to let $a = b$. Is this a known problem? Any help is appreciated.

Note: We can simplify the problem by only allowing the number 1 instead of every natural number. This is equivalent, because we can transform 1 into \[1\], 2 into \[1, 1\], 3 into \[1, 1, 1\], etcetera.

# Answer
> 0 votes
I found a solution to my problem. Let's look at the simpler but equivalent problem in which an item is recursively defined as an empty list or a list of items. I'll summarize the algorithm.

## Variables:

* Int counter starting at 0
* Hash map: list of integers $\to$ integer. The integers represent equivalence classes.

## Function find(item) $\to$ int:

Finds the equivalence class of an item. Recursively call find on all the children of item. Now you have a list of ints. If this list of ints is contained in the hash map, return the corresponding value. If not, add the list to the hash map with the counter as value. Increase the counter and return the value.

## Function merge(int a, int b):

Merges two equivalence classes a and b. In the hash map, replace all occurences (both in keys and in values) of a by b. Now it can happen that one key is mapped to multiple values. If that happens, again merge those values. Repeat this until every key maps to a unique value.

## Algorithm:

For every rule c = d, call merge(find(c), find(d)). Then to see if a = b, check if find(a) = find(b).

---
Tags: algorithms, equality, smt-solvers
---


title: Big O and constants

text:
# Question
Title: Big O and constants
I've already asked this question on stack overflow, but guys have suggested me to ask my question here.

Let's consider classic big O notation definition (proof link):

The $O(f(n))$ is the set of all functions such that there exist positive constants $C$ and $n\_0$ with $|g(n)| \leq C \cdot f(n)$ for all $n \leq n\_0$

---

According to this definition it is legal to do the following (`g1` and `g2` are the functions that describe two algorithms complexity):

$$g\_1(n) = 9999 * n^2 + n \in O(9999 \cdot n^2)$$ $$g2(n) = 5 * n^2 + N \in O(5 * n^2)$$

And it is also legal to note functions as:

```
g1(n) = 9999 * N^2 + N ∈ O(n^2)

g2(n) = 5 * N^2 + N ∈ O(n^2)

```

As you can see the first variant `O(9999*N^2)` vs `(5*N^2)` is much more precise and gives us clear vision which algorithm is faster. The second one does not show us anything.

The question is: why nobody use the first variant?

It is obvious that if functions have different orders of growth (for example `n^2` vs `n`) we don't care about constants. But if not, then constants play very important role in understanding what function has lower growth rate.

My reasoning why nobody does not specify constants is the following:

1. constants are not very representative, for example:

`void foo(int n) {
 int x = 1;
 for(int i = 0; i < n; i++) {
 x += 1;
 x = x << 1;
 }
 }`

Complexity will be: `T1(n) = 1 + (1 + 1) * n = 1 + 2 * n`

```
`void boo(int n) {
   int x = 1;
   for(int i = 0; i < n; i++) {
     x += 1;
     x = x * 1;
   }
 }`

```

Complexity will be: `T2(n) = 1 + (1 + 1) * n = 1 + 2 * n`

So, as we can see both complexities are the same. The problem is that `foo` function will be executed faster that `boo` because of `<<` operation.

We could give each operation it own weight, but it will be too complicated, so to make things simple we just said: no constants in Big O.

The question is: is my reasoning is correct or we have another reasons why we do not specify constants in Big O notation?

# Answer
Evaluating these Big-O constants in real life situations is nearly impossible. Each computer has different hardware, and the precise cost of each operation (or even of only a specific type of operation) is dependent on many different factors such as:

1. What kind of memory did we need to access?
2. Did we have a cache hit/miss?
3. Can these kinds of operations be calculated in Parallel bulks by the CPU?

And many many more.

Even in a more theoretical setting, examining the constants can be very cost-ineffective and complicated. To do so, we need to define a specific cost for each basic operation used by an algorithm instead of just treating them as units, and the complexity analysis for our algorithm will need to be a lot more detailed and careful when counting.

For me the best way to see why we ignore constants is to simply study different algorithms and computer architecture, and while doing so think about how much more work you will need to invest to be able to discuss constants accurately, and what little real-life benefit you will receive from it.
> 3 votes

---
Tags: complexity-theory, asymptotics
---


title: why not just one header in TCP/IP?

text:
# Question
Title: why not just one header in TCP/IP?
I was reading through the computer network fundamentals. I noticed that there are headers added at each layer in the OSI model. However, can we not have just one header above the App layer that defines the header details of every layer ?

I would think answer would be No. But any reasons why ?

Thanks

# Answer
First thing is that OSI model is a reference and theoretical model which breaks down the functionality in different layers although the real implementation of network might differ.

It is better to have abstractions over abstractions. It is good to have multiple layers with different functions rather than a monolithic implementation. If every layer would have its own concern then it will be easy to find the root cause of failure if it occurs.

Also a network for e.g. Internet is a very complex structure which requires different protocols to actually implement it. If the headers would be constructed all at once then it will not be distinguishable how the protocols are actually applied. A protocol which applies to the physical medium (e.g. Ethernet protocol) cannot be applied before actually producing reasonable and transmittable chunks of the data (which is done at an upper layer).

So it is a good practice to do it progressively and this generally applies to entire Computer Science because it is never recommended to have one monolithic chunk rather than multiple small understandable chunks.
> 0 votes

---
Tags: computer-networks, tcp
---


title: Complexity of not P or EXPTIME

text:
# Question
Title: Complexity of not P or EXPTIME
**Question 1:** Is it possible to create an algorithm for deterministic Turing machine that will run not in P neither EXPTIME?

**Question 2:** For me it seems that the answer for my question is `it is impossible`. If my reasoning is correct, it means that any function that describes complexity will have `polynomial(x)` or `2^polynomial(x)` form.

Does my reasoning is correct?

# Answer
> 2 votes
A function $f(n)$ is time-constructible if there is a Turing machine that runs in time exactly $f(n)$, where $n$ is the input size (in bits). Kobayashi, in his paper On proving time constructibility of functions, showed that if $f(n)$ can be computed in time $O(f(n))$ then $f(n)$ is time-constructible. In particular, functions like $n^{\lfloor \log\_2 n \rfloor}$ are time-constructible, even though they lie strictly between polynomial time and exponential time.

In fact, the time hierarchy theorem even shows that there are some decision problems which can be computed in time $O(n^{\log n})$ but not in polynomial time. This shows that there are problem not in $\mathsf{P}$ which can be computed in faster than exponential time.

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


title: Why do pushdown automata use a stack?

text:
# Question
Title: Why do pushdown automata use a stack?
I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?

# Answer
If you change the stack to the queue or multiple stacks, the power of computation will be increased! (as you know, we can model a queue with two stacks). If we use a queue, it can be powerful as a Turing machine. However, the computation power of a push-down automaton is not that much! You can know more about that here.
> 15 votes

# Answer
There are several possible layers to your question.

* Why must PDAs have a stack? -- By definition! That's just how it is.
* But *why* are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition.
* Why *is* it interesting? -- See reinierpost's answer.
* Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over.

I'd like to expand on the second bullet a little. How do different definitions come about?

If you take finite control with different memory models, the resulting classes of automata have *very* different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models.

To list just a few examples of ideas people have had:

And so on and so on.

Note that you can also modify other elements:

* The alphabet -- make it infinite, or continuous.
* The transition function -- make it a relation, or allow $\varepsilon$-transitions.
* The state set -- make it infinite, or allow multiple starting states.
* The inputs -- make them infinite, or trees, or timed sequences.
* Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?)

Interesting things can happen!

That's the beauty of mathematical definitions: you usually get *something*. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's *useful* (a dreaded question after talks!), maybe not. But it always *is*.
> 39 votes

# Answer
OmG and Raphael have already answered your question:

* pushdown automata use a stack because they're defined that way
* if they didn't use a stack, what you'd get is a different type of automaton, with different properties

At this point you may ask: why does my professor present the pushdown automaton, not some other kind of automaton? What makes the pushdown automaton, with a stack, more interesting than an automaton with some other data structure?

The answer is that non-deterministic pushdown automata can recognize exactly the context-free languages, the languages generated by context-free grammars, which were introduced early on in the history of computer science, in the 1950s, as a technique to describe the syntax of languages: both natural languages, such as English or Russian, and artificial languages, such as programming languages (the first programming language they described was FORTRAN).

This was a big deal at the time. Cybernetics and behaviorism were all the craze. Computers were starting to be applied commercially. One of the areas they were applied to was language processing. How can we describe language?

Well, it consists of utterances (things people say or write down), that consist of sequences of items (words, or sounds). A person who wants to say something will emit those utterances; another person receives them, and makes sense out of them. What if we want to make a computer do the same thing? We will need to find a way to describe a language that can be taught to a computer. We will need a way to generate valid utterances that a computer can use, and a way to recognize those utterances that a computer can use - such that the utterances are actually the utterances of a language humans use, such as English or Russian.

Descriptions of devices that could do such things already existed: there were state machines and various kinds of automata. However, Noam Chomsky, a mathematical linguist at MIT involved in a mechanical translation project, realized state machines aren't powerful enough to describe natural languages such as English, as they cannot describe the phenomenon of recursion in language. He needed something similar, but with the power to describe recursion, and arrived at the context-free grammars, a simple attempt to mathematically formalize rules of grammar as they've been used in describing and teaching languages since at least 500 BC. He proved that these can indeed describe more languages than state machines can, but fewer than some other techniques - a result known as the Chomsky hierarchy. He hoped they would suffice to describe languages such as English and Russian.

Context-free grammars generate utterances. Chomsky thought they basically described how a person generates sentences when speaking. You also need a device to describe how utterances are recognized. That is what pushdown automata are for. They can recognize exactly the utterances generated by a context-free grammar. So they were thought to describe more or less how a human recognizes sentences when listening.

Soon afterwards, it was proved that context-free languages aren't actually capable of describing the syntax of languages completely - you need all kinds of additional machinery to do it properly. This is true both for natural languages and artificial languages. (To be honest, I think Chomsky meant to come up with visibly pushdown languages, except he didn't realize the difference, and if he had, it would have saved us all a lot of hassle.)

However, context-free languages and pushdown automata are mathematically very simple and elegant devices, and the Chomsky hierarchy is a simple and elegant result, so they are very useful in education to explain the basics of computer-based language description and recognition (formal language theory). For this reason, they have continued to be a standard part of the theoretical computer science curriculum, and many techniques used in practice are based on them, so they really are requisite knowledge if you want to study anything related to natural language processing, programming language implementation, and other language-related topics.
> 28 votes

---
Tags: automata, pushdown-automata, computation-models
---


# Question
Title: Confirmation of alternative correctness proof for Floyd-Warshall's all-pair shortest-path algorithm
The most common proof for Floyd-Warshall's algorithm is an induction proof on the outer-most loop, which says

$\delta^k(i,j)=\begin{cases} \min\\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\\} & \text{for}\\,k\geq 1\\ w(i,j) & \text{for}\\,k=0\\,\text{(i.e., base case)}, \end{cases}$

where $d^k(i,j)$ is the shortest path from $i$ to $j$ using $k$. Here I present another proof using induction on the length of any shortest path. I have a feeling that the main idea of my proof is the same as above, but I'm not sure if it is correct (missing something important). Here is the proof below:

*Proof.* (induction on $l$, the lengths of all shortest paths between all pairs of vertices $x\_i$ and $x\_j$ in the graph)

Base case $l=1$: the shortest path between some pair of vertices $x\_i$ and $x\_j$ is exactly the edge $(x\_i x\_j)$. In this case, $d\_{ik}+d\_{kj}\geq d\_{ij}=k((x\_i x\_j))$ for all $k$ by the fact that $(x\_i x\_j)$ is the shortest path. The algorithm will not change $d\_{ij}$ in this case, so it is correct.

Now, suppose that the algorithm will correctly find the length of all shortest paths of length up to some $c$, and that the shortest path between some pair of vertices $x\_i$ and $x\_j$ is $(x\_i x\_{p\_1} x\_{p\_2}\cdots x\_{p\_c} x\_j)$, which has length $c+1$. Now, let $x\_{p\_m}$ be the vertex in the path that has the biggest index in the distance matrix, and consider the path divided into $(x\_i\cdots x\_{p\_m}\cdots x\_j)$; let $P\_1=(x\_i\cdots x\_{p\_m})$ and $P\_2=(x\_{p\_m}\cdots x\_j)$. For $P\_1$, the algorithm will correctly find its length by the inductive hypothesis, since it is of length at most $c-1$ and it is the shortest path between $x\_i$ and $x\_{p\_m}$; similarly the algorithm will correctly find the length of $P\_2$, since it is of length at most $c-1$ and it is the shortest path between $x\_{p\_m}$ and $x\_j$. The algorithm will correctly do the comparison $d\_{i p\_m}+d\_{p\_m j}\<d\_{ij}$ when $d\_{i p\_m}$ and $d\_{p\_m j}$ are the length of $P\_1$ and $P\_2$, respectively, and update $d\_{ij}$ correctly. This is because $p\_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P\_1$ and $P\_2$ and stored them in $d\_{i p\_m}$ and $d\_{p\_m j}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

P.S. To clarify, this is for a homework problem (as these problems typically are), and I am asking this after the due date. Most large universities in the U.S. nowadays employs graders (I am one myself), which means that my alternate proof may or may not receive a careful look. My point is that I want to know whether I missed something in the proof.

# Answer
Your effort towards a new kind of proof for Floyd-Warshall algorithm is appreciated.

On one hand, your proof is very well written. It cannot be said to be all wrong as apparently you have tried to avoid saying anything wrong.

On the other hand, I would not call you proof a proof that is different from the usual induction proof on the loop variable of the outer-most loop.

> ... $p\_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P\_1$ and $P\_2$ and stored them in $d\_{i\_{p\_m}}$ and $d\_{p\_{m\_j}}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

Take a moment to reflect. What you said above is basically the induction hypothesis in the usual induction proof on the loop variable of outer-most loop. That induction hypothesis can be viewed as a proposition that is even stronger than the final result of the Floyd-Warshall algorithm. Armed with that kind of knowledge, it is expected the correctness can be proved easily. In other words, it is not far fetched to say you just proved its correctness by admitting its correctness. Or, you just repeated the usual proof with some extra unnecessary logic.

There is another hidden flaw in your proof that is actually critical. Suppose there is a negative cycle in a connected graph. Floyd-Warshall algorithm handles that situation graciously. However, there is no shortest paths between any pairs of vertices in the graph, since given any path, you can always find another path that is shorter. So, your induction hypothesis becomes void in that case.
> 1 votes

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


title: How huffman tree uses MinHeap?

text:
# Question
Title: How huffman tree uses MinHeap?
As far as I know, a minheap is data structure whose parent node's value is less than child node and maxheap is when parent node is greater than child node. Here they have used minheap. But as the node closer to root have less length code than nodes below that level i.e., level 1 codes will have shorter codes than level 5; which means level 1 nodes are more frequently occurring than level 5 nodes. Also the numeric value after addition is also greater than that nodes at high level. I am confused, isn't that definition of max heap but they are using min heap. Please explain why they are using Min heap and not Max heap (considering nodes at lower level are more frequent than at higher level)

# Answer
> 3 votes
Building a Huffman tree is bottom up.

1. You start with the all the leaf nodes with their frequency.
2. Then you *select and remove* the 2 nodes with the *small*est frequencies
3. create and *insert* a new compound node with the 2 selected nodes and it's new frequency is the sum of the 2 nodes
4. if set *has* 2 or more nodes repeat from step 2

Selecting the 2 nodes with the least frequencies requires a min heap.

# Answer
> 1 votes
Actually the more efficient algorithm (described by Moffat in 1995 or so) is the following:

* sort input nodes by frequency, put them into queue A
* make an empty queue B for intermediate nodes
* choose two smallest nodes among two smallest nodes in A and two smallest nodes in B, and pull them off their queues
* push combined node into the queue B
* repeat until you have no nodes in A and only one node in B

This way, nodes in A and B remains sorted, so you can find smallest ones on the end of queue.

As result, after initial sort (which is usually count sorting with #buckets ~= #nodes, plus something simple for a few remaining too large elements), you access both queues only sequentially, so the algorithm spends only ~10 cpu cycles per node.

AFAIR, Moffat idea was even more advanced, allowing to build huffman tree in-place for a small runtime penalty compared to the standard queue implementation.

# Answer
> -2 votes
ih huffman code,not nodes value should be considered.Only codes assigned should be considered.If u consider the code,only the upper level nodes will have least bit code

---
Tags: data-structures, heaps
---


# Question
Title: how does $PATH$ being $NL$-complete help to prove $NL = coNL$
There is a proof in Sipser showing that $NL = coNL$ (theorem 8.27 in the 3rd edition).

In the proof idea, the first sentence is: "We show that $\overline{PATH}$ is in $NL$, and thereby establish that every problem in $coNL$ is also in $NL$, because $PATH$ is $NL$-complete." I'm having trouble understanding this.

Sipser did not elaborate on this, but it sounds like the logic behind this sentence is:

1. $PATH$ is $NL$-complete
2. so $\overline{PATH}$ is $coNL$-hard
3. and $\overline{PATH}$ is in $NL$
4. so $coNL \subseteq NL$

If so, why can we get 2 from 1?

More generally, since $PATH$ can be *decided* in $NL$ (Sipser example 8.19), why can't we just flip the result to decide $\overline{PATH}$ directly?

# Answer
> 3 votes
$\mathsf{NL}$ consists of all languages accepted by nondeterministic Turing machines using logarithmic space. One way to think of such machines is as follows:

* The input is written on a read-only input tape.
* There are one or more work tapes of logarithmic size.
* There is a read-only oracle tape on which the head is constrained to only move to the right.

We can think of each such machine as computing a Boolean function on two arguments: $x$, which is the actual input, and $y$, which is the initial contents of the oracle tape. Such a machine $M$ nondeterministically computes the language $L(M)$ given by: $$ x \in L(M) \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ accepts}. $$ In other words, a language $L$ is in $\mathsf{NL}$ if there exists a logspace Turing machine $M$ with an auxiliary oracle input such that $$ x \in L \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ accepts}. $$

A language is in $\mathsf{coNL}$ if its complement is in $\mathsf{NL}$. Equivalently, a language $L$ is in $\mathsf{coNL}$ if there exists a logspace Turing machine $M$ with an auxiliary oracle input such that $$ x \notin L \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ rejects}. $$ Equivalently, $$ x \in L \Longleftrightarrow \forall y \text{ $M(x,y)$ accepts}. $$

Suppose now that $L$ is in $\mathsf{NL}$, say $L = L(M)$, and let $M'$ be obtained from $M$ by complementing the output. Then $$ x \in L(M') \Longleftrightarrow \exists y \text{ s.t. $M'(x,y)$ accepts} \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ rejects}. $$ As you can see, $L(M')$ isn't necessarily the complement of $L(M)$. Indeed, given any machine $M$, we can come up with another machine $\tilde{M}$ such that $L(M) = L(\tilde{M})$, but $\tilde{M}(x,y\_0)$ always rejects, for some fixed $y\_0$ (for example, $\tilde{M}(x,0\Sigma^\*)$ always rejects, and $\tilde{M}(x,1y) = M(x,y)$). In this case, $L(\tilde{M}') = \Sigma^\*$.

---

Now I can answer your questions:

* $\overline{\mathsf{PATH}} \in \mathsf{coNL}$ since $\mathsf{PATH} \in \mathsf{NL}$ and *by definition* $\mathsf{coNL}$ consists of the complements of all languages in $\mathsf{NL}$.
* Furthermore, $\overline{\mathsf{PATH}}$ is $\mathsf{coNL}$-hard because $\mathsf{PATH}$ is $\mathsf{NL}$-hard. Indeed, suppose that $L \in \mathsf{coNL}$. Then $\overline{L} \in \mathsf{NL}$. Since $\mathsf{PATH}$ is $\mathsf{NL}$-hard, there is a logspace reduction $f$ such that $x \in \overline{L}$ iff $f(x) \in \mathsf{PATH}$. Thus $x \in L$ iff $f(x) \in \overline{\mathsf{PATH}}$, and so $f$ also reduces $L$ to $\overline{\mathsf{PATH}}$.
* Flipping the output value of a nondeterministic machine does not result in complementing the accepted language.

Elaborating on the second point, for some nondeterministic complexity classes $\mathsf{X}$, it is known that $\mathsf{X} \neq \mathsf{coX}$. The simplest example is $\mathsf{RE} \neq \mathsf{coRE}$: the halting problem is in $\mathsf{RE}$ but not in $\mathsf{coRE}$. Therefore $\mathsf{NL} = \mathsf{coNL}$ is a nontrivial statement.

---
Tags: complexity-theory
---


# Question
Title: Coin Change Problem Recurrence Relation with one parameter
I have been looking through the recursive formulation for the coin change problem here and am wondering if it is possible to define the function $ C(N, m) $ in one parameter as $C(N)$, therefore not depending on the set $ S\_{m} $? What would this function look like in general? If a concrete example is needed what would it look like for the set of coins {3 cents coin, 4 cents coin, 5 cent coin}?

# Answer
> 0 votes
One possible definition is $$ C(N) = \sum\_{i \in S\_m} C(N-i), $$ with base cases $C(0) = 1$ and $C(x) = 0$ for negative $x$. This counts the number of ways to write $N$ as a sum of elements of $S\_m$ *where order matters*, that is, if $a \neq b$ then $a + b$ is different from $b + a$. As an example, if $S\_m = \\{1,2\\}$ then $C(3) = 3$ since $3 = 1 + 1 + 1 = 1 + 2 = 2 + 1$.

It is, however, possible to obtain a one-parameter recurrence relation, using inclusion exclusion: $$ C(N) = \sum\_{\emptyset \neq A \subseteq S\_m} (-1)^{|A|+1} C(N-\Sigma A), $$ where $\Sigma A$ is the sum of elements in $A$. For example, if $S\_m = \\{3,4,5\\}$, then the recurrence is $$ C(N) = C(N-3)+C(N-4)+C(N-5)-C(N-7)-C(N-8)-C(N-9)+C(N-12). $$ The initial values are $$ C(0) = 1, C(1) = C(2) = 0, C(3) = \cdots = C(7) = 1, C(8) = \cdots = C(11) = 2, $$ or in table format: $$ \begin{array}{c|ccccccccccc} N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\\hline C(N) & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 \end{array} $$

---
Tags: recurrence-relation, coin-change
---


# Question
Title: Bipartite Perfect Matching "Assignment Problem" - finding an assignment of a particular weight
The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to enumerate assignments one-by-one in increasing order of their weights using methods like Murty's algorithm, where each new enumeration takes polynomial time.

We can assume that there are 2n vertices in the bipartite graph and that the weights on all present edges are non negative integers less than some value k. Missing edges will need a higher weight or infinity.

My questions is, is it possible to find an assignment of a particular weight (that is not minimal), say W, in polynomial time? Naively, if one tries to enumerate assignments, it may take exponential time to find an assignment of weight W since there may be exponentially many assignments of weight less than W.

Further, if it is possible to find an assignment of weight W in polytime, is it possible to enumerate all assignments of weight W, similar to Murty's algorithm?

I know that we can formulate the assignment problem as a linear program

$\min \sum\_{i,j} w\_{i,j}x\_{i,j} $

such that

$\sum\_i x\_{i,j} =1$
$\sum\_j x\_{i,j} =1$
$x\_{ij} \ge 0$

I am not sure whether we can directly add the constraint
$\sum\_{i,j} w\_{i,j}x\_{i,j} \ge W$
and still obtain integral solutions for $x\_{i,j}$s. Thoughts?

# Answer
The problem becomes NP - Complete when the weights are exponential in the number of variables. This can be shown by a reduction from the subset sum problem described in the paper "Planarizing gadgets for perfect matching do not exist" by Gurjar et al. (link)
> 1 votes

---
Tags: graphs, linear-programming, enumeration, bipartite-matching, assignment-problem
---


# Question
Title: Is the runtime of binary search big omega of logarithm of n?
My question is that can we say that runtime of the binary search is $\Omega(\log n)$?

I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst case. And for this reason the time complexity of binary search is $\Theta(\log n)$.

However, I still cannot interpret if it is also $\Omega(\log n)$ even if I think (and know that) it is. So, I just need some scientific explanation.

# Answer
To prove the lowerbound of $\Omega(\mathrm{log}n)$, it is best to use an adversary argument.

For each $n$, you can fix some pattern of access when running binary search, i.e. a sequence of $Left-Half$, $Right-Half$ of length $log(n)/2$, then put the searched value at the index when you go according to that sequence.

For the remaining of the array, just put in arbitrary value such that they are all less than the searched value at the lesser index and larger than the searched value at higher index.
> 1 votes

# Answer
First, you can analyze the time complexity of binary search in whatever case you wish, say "best case" and "worst case". In the best case, you use $f(n)$ time, while in the worst case you use $g(n)$ time. These are two functions of $n$, describing two different scenarios you have defined. Now, you can make statements such as $f(n) = O(1)$ or $g(n) = \Theta(\log n)$. However, the Big Oh of a function has *nothing* to do with time complexity, it is merely something applied to a function that could just as well be representing the number of apples you get for $n$ euros.

In particular, thinking along the lines of "$O$ is always for best case, $\Omega$ is for the worst case" (or whatever), is wrong and dangerous.

To you specific question: if a function $g(n) = \Omega(\log n)$ and $g(n) = O(\log n)$, then $g(n) = \Theta(\log n)$. The function $g(n)$ might be representing the time complexity of binary search or the number of apples, it doesn't matter. And as always, look at the definitions and you can stop guessing.
> 2 votes

---
Tags: algorithm-analysis, time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Is there an algorithm to find all vertices that are inside of a shape?
In computational geometry, is there any algorithm to find all vertices that are inside of a shape?

* All vertices of graph has $x$\- and $y$-coordinates
* Shape is a set of points with $x$\- and $y$-coordinates (unicyclic graph)
* I need a fast algorithm. I am trying to avoid iterating over all vertices

**Example**:

# Answer
It seems to me that the problem is not about graph theory, but computational geometry. Phrased slightly differently, your input is a set of two-dimensional points $P$ (corresponding to the coordinates of the vertices of some graph drawing) and a polygon $Q$. The task to determine a subset $P'$ of the points $P$ that are contained within $Q$.

One possible algorithm is to iterate over each point $p$ in $P$, and check whether $p$ is inside $Q$. This classic point in polygon problem has many simple and efficient algorithms.
> 2 votes

# Answer
As said elsewhere, this is a problem in computational geometry. The graph structure is of no use.

There is a simple sweepline solution.

Sort the points and polygon vertices by ordinates. Now by a merge-like traversal, you an enumerate all the points in the slab between two successive vertices. By counting the number of edges on the left of every point, you can determine the insideness.

The number of operations will be $O(n\log n+m\log m)$ for the sorts ($n$ points and $m$ edges). Then assuming that the slabs contain on average $e$ edges (a small even number for ordinary polygons), the counting phase will cost like $O(e(n+m))$ operations.

With a little more sophistication, I suspect that this can be limited to $O(n\log m+m)$ in the worst case.
> 1 votes

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


# Question
Title: Complexity of determining spanning bipartite graph
A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum possible number of edges) from given graph $G$:

Given a planar graph $G$, we need two disjoint sets $V\_1$ and $V\_2$. We define $V\_2=V \setminus V\_1$ where $V = V(G)$. In the following, $H$ is the bipartite subgraph with $V(H)=V\_1 \sqcup V\_2$ and $E(H) = K\_{V\_1,V\_2} \cap E(G)$ where $K\_{V\_1,V\_2}$ is the complete bipartite graph on $V\_1$, $V\_2$.

1. Start with first $i$ vertices of $V$ in vertex set $V\_{01} \subseteq V$ and then $V\_{02} = V \setminus V\_{01}$
2. In iteration $i$, let our current chosen vertex set be $V\_{i1}$
3. If $\exists x \in V\_{i1}$ such that $d\_{H}(x) \lt \frac12 d\_{G}(x)$, then consider the bipartite spanning graph $H'$ with $V(H') = V\_{i1}' \sqcup V\_{i2}'$ where $V\_{i1}' = V\_{i1} \setminus x$, $V\_{i2}'= V\_{i2} \sqcup x$, $E(H') = K\_{V\_{i1}',V\_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex $x$ which satisfies above property from $V\_{i1}$ to $V\_{i2}$.
4. Similarly do for $ V\_{i2}$. If $\exists x \in V\_{i2}$ such that $d\_{H}(x) \< \frac{1}{2} d\_{G}(x) $, move vertex $x$ to $V\_{i1}$. Go to step 2.
5. Repeat until $(\forall x \in V(H))\\, d\_{H}(x) \geq \frac{1}{2} d\_{G}(x)$
6. After this $V\_1 = V\_{i1}$ and $V\_2 = V\_{i2}$. We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V\_{1} \sqcup V\_{2}$ satisfies the property that $$(\forall x \in V(G))\\, d\_{H}(x) \geq \frac{1}{2} d\_{G}(x)$$

**Analysis of this procedure**:

1. Could somebody help me analyze this algorithm?
2. Can I assume I know the degrees of the vertices in the bipartite graph $H$, in the intermediate steps?

2.1. If I can assume so, then each induction iteration has $2n$ steps. And, in the worst case, could there be $n!$ permutations of induction iteration (Any permutation of $i$ vertices is possible for the first vertex set). Is the worst-case upperbound $O(n!\times n)$?

# Answer
1. We cannot analyze your algorithm since it is, as currently presented, not an algorithm to start with. In particular, you did not specify what is the starting value of $i$, in the very first iteration.
2. Surely, when you have $V\_{i1}$ and $V\_{i2}=V\setminus V\_{i1}$, it is easy to compute the degrees of the vertices in $H$.

2.1. IMHO, even after you fix some starting value of $i$ for the first iteration, there cannot be any guarantee that your algorithm would stop. Since, swapping vertices between $V\_{i1}$ and $V\_{i2}$ does not necessarily decrease the number of "bad" vertices, i.e. those vertices $x$ for which $d\_H(x)\le \frac12d\_G(x)$.
> 1 votes

# Answer
In answer to your comment:

> By maximum spanning bipartite graph I mean same vertex set as given graph and the maximum number of edges possible. Is the complexity $O(n^3)$ correct for this algorithm? If so it would solvable in P time.

No, that problem, also known as Bipartite Edge Deletion, or Edge Bipartization, is:

> Given a graph $G = (V, E)$ and an integer $k$, is it possible to delete at most $k$ edges $E'$ such that $G' = (V, E \setminus E')$ is bipartite,

which is NP-complete.

It happens to be "equivalent" to the "vertex deletion" version of the problem, which is also known as Odd Cycle Transversal.
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Loading a word from byte-addressable cache
I have asked a similar question at stack-overflow, but then I found this question here, and figured it should go here instead..
So, my question is pretty much the same as the one in the question I linked:
I know that in a byte-addressable cache, a byte-offset (usually the LSB of the address) is used to determine which byte to access out of the designated cache block.
But, if the offset allows the selection of 1 byte out of the block, we would need 4 subsequent accesses to the cache in order to access a single word (assuming a word equals 4 bytes), and I somehow doubt that's the way things execute in real time.. Any clarification regarding that will be appreciated, as I didn't find an answer to that in the previous question).
Thanks in advance :)

Edit: To clarify my question - I'm trying to understand how can a Byte-Addressable memory output more than 1 Byte at a time.
I'd understand it if the memory Always outputs a whole word, for example, and the byte is then extracted by the CPU according to the requested address by specifying an offset of 0x0 to indicate that it needs 2 bytes - the 1st and 2nd bytes, 0x1 to indicate it needs the 3rd and 4th bytes, 0x00 to indicate it needs only 1 byte - the first byte, 0x01 to extract only the 2nd byte, 0x02 to extract only the 3rd byte, 0x03 to extract only the 4th byte, and specifying no offset at all to tell the CPU "do not extract any specific bytes - process the word as a whole".
That will make for a nice explanation - But I've seen no indication of anything of the sorts while looking at various CPU implementations..

# Answer
Alright, Thanks for the help :) I was still pretty confused, but after talking to a few more people around the globe, I got an answer which left me convinced:

All that's required from memory so we can call it "Byte-Addressable" is that we can access a single byte out of the memory's data. That means - even if the Memory (as a component - RAM for example) isn't byte-addressable by itself (which means that each address contains, for example, 4 bytes of data instead of 1), then the Memory's DATA can still be considered byte-addressable if you implement another mechanism to let you interact with a single byte out of the data retrieved - Even if that mechanism exists in the CPU, and has nothing to do with the memory's hardware on its own. For example:
Say we have a CPU with a Word-Addressable RAM connected to it.
In order to access a single byte, we add a mechanism to our CPU so it ANDs each Word with a Mask, thus masking-out any irrelevant bytes, leaving us with only the desired Byte (If the RAM's output is 4 bytes-long, say, `0x09ABCDEF`, and we are only interested in the 4th byte (`0xEF`), we can AND the output with the Mask `0x00000011`, resulting in our desired byte, preceded by 0s (`0x000000EF`. In case of a signed output, we should Sign-Extend the output, instead of simply masking it).
So, in the above case, thanks to the mechanism we've implemented in our CPU - We are able to access a single byte from memory. A similar mechanism may be implemented in order to Store a single byte in memory, as well.
Then although our RAM is still WORD-Addressable, our MEMORY (the RAM's Data) is Byte-Addressable, thanks to our CPU.
This has caused a lot of confusion for me up until now, as I've assumed Memory to mean the actual hardware memory, and not its stored data.
Hope this answer manages to help anyone else who might be confused because of it :)
> 0 votes

# Answer
What makes you think that?

If you have a modern high-performance CPU with 256 bit = 32 byte vector registers, then the byte offset determines which group of 1, 2, 4, 8, 16 or 32 consecutive bytes to transfer. Nobody in their right mind would transfer individual bytes. Much too slow.

What *will* happen and may slow down things a little bit is that if the group of bytes to transfer is not contained in *one* single cache line, then two accesses are made to two different cache lines. For example, if your cachle lines are 64 bytes and you try to access a 32 bit (four byte) item at byte offset 61, 62 or 63.
> 0 votes

# Answer
Your whole question is predicated on the belief that byte-addressable means that only bytes can be returned. That's like assuming that, because every page in a book has a number, it's only possible to tell somebody "Please read page 17" and you can't say "Please read pages 17 and 18. That simply isn't true.

It's perfectly possible to build hardware that, when you give it an address $A$, returns the byte at that address, and also the bytes at addresses $A+1$, $A+2$ and $A+3$, regardless of whether $A$ is a multiple of four. Heck, it's even possible to build hardware that returns the bytes at addresses $A-4$, $A$, $A+3$ and $A+9$. It's hard to imagine a use for that, but you could do it. And, although both my examples have returned four bytes, you could build hardware that returned any other number of bytes. Indeed, you could build hardware that returns any computable function of the memory.

> how can a Byte-Addressable memory output more than 1 Byte at a time?

By having an arrangement of transistors and wires that does that. Literally, that's all you need.
> 0 votes

---
Tags: cpu-cache, memory-access
---


# Question
Title: What is a min-max theorem in graph theory?
I'm currently studying a paper which uses extensively the term '`min-max theorems`' in graph theory, and claims to present a tool allowing to generalize these theorems. (here is the link to the paper if needed)

Among those, we can find for example :

* The max-flow-min cut theorem.
* Edmond's disjoint arborescences theorem (link).

I have some intuition about what a min-max theorem would be, but I can't come with a concise and precise definition.

**My question is** : what would be a definition of such a family of theorems ?

And a second question along : is this min-max theorem concept always linked to the strong duality theorem, meaning that they mainly state that one problem is actually the dual of the other, like the max-flow-min-cut is ?

# Answer
A min-max theorem is simply a theorem that says that the minimum value possible for one quantity is the maximum value possible for some other. For example,

* Max-flow min-cut says that the value of the biggest flow between two vertices in a weighted graph is equal to the value of the minimum cut that separates them. Closely related, Menger's Theorem says that the maximum number of edge-disjoint paths between two vertex sets is equal to the size of the minimum cut that separates them.
* Edmonds' Theorem says that the maximum number of edge-disjoint spanning arborescences is equal to the minimum value of something called $\varrho(X)$ over certain non-empty vertex sets.
* The cops and robbers characterization of treewidth says that the minimum width over all tree decompositions is equal to the maximum number of cops that a robber can escape (er, plus or minus one, probably).
> 2 votes

---
Tags: graphs, duality
---