# Question
Title: What is the current status of parallel or concurrent programs in the Curry-Howard isomorphism?
In Girard's *Proofs and Types* we can read :

> From an algorithmic viewpoint, the sequent calculus has no Curry-Howard isomorphism, because of the multitude of ways of writing the same proof. This prevents us from using it as a typed $\lambda$-calculus, although we glimpse some deep structure of this kind, probably linked with parallelism.
>
> *Proofs and Types*, J.Y Girard (Page 28)

But we can also read (about Linear Logic) that

> From the viewpoint of computer science, it gives a new approach to questions of laziness, side effects and memory allocation \[GirLaf, Laf87, Laf88\] with promising applications to parallelism.
>
> *Proofs and Types*, J.Y Girard (Page 149, written by Yves Lafont)

How are parallel programs linked to the Curry-Howard isomorphism ? What are the current thoughts about that ?

# Answer
The Concurrent Logical Framework is one interesting area including its descendants, like Linear Meld and LolliMon. This is based on intuitionistic linear logic.

Classical linear logic has connections to the Linear Chemical Abstract Machine (CHAM) as described by e.g. A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine which explicitly describes the result as a Curry-Howard type result.

Alexander Summers' thesis Curry-Howard Term Calculi for Gentzen-Style Classical Logics which I have not read seems to be aimed directly at the problem of providing a Curry-Howard correspondence for Gentzen-style calculi. The $\lambda\mu$-calculus by Curien and Herbelin introduced in The Duality of Computation is a seminal work in this vein of (non-linear) lambda calculi corresponding to classical logics.

At any rate, this is all still a lively area of research. There are many recent papers on this topic. The above doesn't even mention the even more substructural side of separation logic and the corresponding Hoare Type Theory which focuses on imperative programming languages. For example, there's Towards type-theoretic semantics for transactional concurrency whose references you can trace for prior work.

(As a bit of a pedantic note, most of these are focused on *concurrency*, not parallelism per se.)
> 7 votes

# Answer
For concurrency in general, there is a very active line of research, which I tried to summarise in this reply: https://cs.stackexchange.com/a/102711/98901

I add here a comment on parallelism, below.

---

Avron \[1996\] introduced the notion of *hypersequents*, i.e., collections of sequents in judgements.

In \[Kokke et al., 2019\], we showed that a conservative extension of linear logic with hypersequents can be used to type parallelism in process calculi. Essentially, if you have two independent proofs in linear logic of the hypersequent $\mathcal{G}$ and $\mathcal{H}$, respectively, then you can derive $\mathcal{G} | \mathcal{H}$, where $|$ is the operator for composing hypersequents. Following Abramsky's interpretation of "Proofs as Processes" \[Abramsky, 1996\], we get a typing rule for parallelism: say that you have two independent processes $P$ and $Q$ typed by $\mathcal G$ and $\mathcal H$ respectively; then, the parallel composition $P|Q$ (with $P$ and $Q$ independent) is typed by $\mathcal G | \mathcal H$.

We have just started scratching the surface of the semantic interpretation of this, but that this is parallelism is pretty evident: the semantics of the parallel composition allows for seeing simultaneous actions from both processes, and there is a theorem in the paper stating that neither of the two processes needs to wait for the other to perform at least some action (the Readiness Theorem). The extension to more than two actions at the same time seems straightforward. (The typing already allows for it, but the semantics in that paper does not fully take advantage of it.)
> 4 votes

---
Tags: reference-request, logic, parallel-computing
---


# Question
Title: Algorithm for closest available resource
My apologies if question is not in correct format. I don't post here often. I don't know what tags would be appropriate for this question, or even if this is an appropriate question.

Looking for algorithm for closest available resource.

n people P1-Pn, n taxis T1-Tn, are in a 2 dimensional coordinate system eg x,y

Determine Person Taxi pairs if each person walks to the closest taxi that will be available to them, and not taken by another person. Ties of two (or more) people to same taxi can go to the person of lower index. Ties of two (or more) taxis as closest taxi can go to taxi of lowest index.

Does this go by a common problem name? What algorithms exist?

As for what algorithms exist, I can think of 2 right off but I doubt they be considered efficient. 1. use recursion, eg find closest person taxi pair, remove both from available list, and run again. 2. enumerate (n squared) all possible P-T pairs into binary tree sorted by distance value, and then traverse binary tree starting with lowest value until each P has unique T. 3. or can someone offer better algorithms?
Thank you

# Answer
I would call this problem as closest matching between two equal sets with priority.

Here is an $O(n\log n)$ algorithm, assuming the distance is the 2-dimensional Euclidean distance. It might work with the Manhattan distance as well; however, I have not double checked that.

Build a balanced 2-d tree for all taxis in $O(n\log n)$ time. Attach to each node an inventory number, the number of all points in the rectangle or half plane represented by that node, which can be done in an $O(n)$-time tree traversal.

Now iterate over $P\_1, P\_2, \cdots, P\_n$ in that order. For each person $P$, do the following.

> Find all nearest taxis of $P$, using the inventory number and ignore the unavailable taxis, which takes (amortized) $O(\log n)$ time. Assign the taxi with the lowest index among them to $P$. Mark that taxi as unavailable. Subtract one from the inventory number attached to each node that contain $P$, which takes $O(\log n)$ time.
> 1 votes

# Answer
I would compute all taxi-people pair distances (O(n²)).

Then I would solve the Stable marriage problem with Gale–Shapley algorithm (O(n²)). People looking for the closest taxi and taxis looking for the closest person.

An interesting point of your problem is that it is indeed symmetric on people and taxis. If it is solved considering taxis looking for people, the solution would be the same.

It makes an overall O(n²) solution quite easy to implement.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Can all Turing-computable problems be solved with a machine with finite tape and infinite controls?
We know all computer computable problems can be solved using the infinite tape and finite control system of the turing machine. Now think something different, let the tape is finite but the control system is infinite. Now can we solve the same set of problems with this machines?

# Answer
Assuming the tape is always made long enough to hold the input, then infinite control allows you to decide any language at all. The infinite control can just contain one state for each possible string that's been read so far. When it reaches the end of the input, it can accept or reject as appropriate.
> 2 votes

---
Tags: computation-models
---


title: is $0^x1^y$ context-free?

text:
# Question
Title: is $0^x1^y$ context-free?
given that L is regular, does the following make a context-free language?:

i) $\\{0^x1^y \mid 0^{x+y} \in L\\}$

ii) $\\{0^x1^y \mid 0^{x-y} \in L\\}$

since L is regular, i presumed that i) can be put into a pushdown automata, but i don't see how to do that for ii). if ii) cannot be put into a pushdown automata, it means it is neither context free nor regular? how can it be shown?

and regarding i) it is a context free, right?

thank you very much for your effort. first post here and i'm glad to join this community

# Answer
> 2 votes
Your first language is actually regular: if $s$ is the substitution mapping $0$ to $\\{0,1\\}$, then $$ \\{ 0^x 1^y : 0^{x+y} \in L \\} = s(L \cap 0^\*) \cap 0^\*1^\*. $$ Your second language is context-free, since we can write it as $L \cap 0^\*$ concatenated with $\\{0^y 1^y : y \geq 0\\}$. It need not be regular, as the example of $L = \\{\epsilon\\}$ demonstrates: in this case, your language is just $\\{0^y1^y : y \geq 0\\}$.

---
Tags: automata, regular-languages, context-free
---


title: Expectation of $u'^t v$ = $u^t v$

text:
# Question
Title: Expectation of $u'^t v$ = $u^t v$
I have another question with dimensionality reduction. I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $.

I need to understand why $E\[u'^T v' \]= u^Tv$ where $u'=Su$.

I just have a intution, that maybe i just prove the left(or right span vector), but the hint is compute $E\[S^TS\]$ that for me this expectation is expectation of E\[ I \] that if i m wrong will be 0...

I m a bit lost with this stuff.

i m thinking to do this

$E\[u^t v\] = E\[u^T \sum vi \]$

another question is about the interval ... using $1 /\sqrt k $ is the same if i use a -1,1 with scaled factor of $\sqrt k $?

# Answer
The idea is that $$ \mathbb{E}\[u^{\prime T} v'\] = \mathbb{E}\[u^T S^T S v\] = u^T \mathbb{E}\[S^T S\] v, $$ due to linearity of expectation. You can take it from here.
> 1 votes

---
Tags: reductions, probability-theory, matrix
---


# Question
Title: Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$
Consider the following language: $$L = \\{a^nb^{n^2} \mid n≥1\\}\\,$$

When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, and the second one to repeat $n$ times the count of $n$. Thus, because of the way we’re using the second tape, it should have a $\Theta(n^2)$ space complexity, and I would say the same concerning the time one. I thought it was correct, but the solution is $TM(x)=|x|+n+2$, where, $x$ is, supposedly, the length of the string, hence $\Theta(|x|)$. It seems correct to me, so is my reasoning completely wrong, or just a different way to express it?

Could we have reasoned about it differently, and say, for example, for every $a$ we write down a symbol on the first tape, and then count the $b$'s, by scanning the symbols back and forth $n$ times? This time, the space complexity should just be $\Theta(n)$, while the time complexity should remain unchanged. What would change if we had a single-tape TM?

# Answer
Your confusion stems from a double use of $n$. Let's write $L$ differently: $$ L = \\{ a^i b^{n-i} : n-i = i^2, i \geq 1 \\}. $$ Here $n$ is the input length. It should be clear that the space complexity is $O(n)$.

Your first estimate just translates to a space complexity of $O(i^2) = O(n)$, since $n = i^2 + i$.
> 2 votes

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


# Question
Title: Either find a perfect matching, or return a witness that none exist
I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options:

1. If a perfect matching exists, it returns the matching;
2. Otherwise, it returns a witness based on Hall's theorem, i.e., a set $S\subseteq X$ such that the number of neighbors of $S$ is smaller than $|S|$.

I found in wikipedia various algorithms for finding a maximum matching in an unweighted bipartite graph. Such algorithms can be used to determine if a perfect matching exists. But does any of these algorithms also return an evidence in case of failure?

EDIT: I have read the links in the answer of Yuval Filmus below, but it took me some time to fill in the missing details. For future reference, here is a detailed solution. Below, let $n := |X| = |Y|$.

**Step 1**. Define a flow network with $2n+2$ nodes in the following structure:

$$ s \rightrightarrows X \rightrightarrows Y \rightrightarrows t $$

where:

* $s$ is a new source node connected to all vertices in $X$ with capacity 1;
* every original edge of $E$ is directed from $X$ to $Y$ with capacity $\infty$;
* each vertex in $Y$ is connected with capacity 1 to a new sink node $t$.

**Step 2**. Use the Ford-Fulkerson algorithm to find a maximum flow in that graph. Suppose the maximum flow size is $m$ (which must be at most $n$).

**Step 3**. If $m = n$ then we are done - the flow induces a matching of size $n$ which is perfect.

**Step 4**. Otherwise, $m \< n$. The FF algorithm also returns an *$s$-$t$ minimum cut* of size $m$ \- a partition $(C,C')$ of the vertices in the graph, such that $s\in C$, $t\in C'$, and the sum of capacities of edges directed from $C$ to $C'$ is $m$.

This cut cannot cross any edge of $E$, since these edges have infinite capacity. Hence, the cut size is determined by edges from $s$ to $X\cap C'$ and from $Y\cap C$ to $t$. So $m = |X\cap C'| + |Y\cap C| = (n-|X\cap C|)+|Y\cap C|$. Hence: $|X\cap C| = |Y\cap C| + (n-m) \> |Y\cap C|$. Since the cut cannot cross edges of $E$, all neighbors of $|X\cap C|$ must be in $|Y\cap C|$, so $|X\cap C|$ is the desired Hall-violator.

# Answer
You can find a maximum matching in a bipartite graph using network flow. The min cut max flow theorem translates to Hall's condition, so a min cut would give you the "evidence". See for example this document or this question on Mathematics.
> 2 votes

# Answer
I would use a degenerated version of the Hungarian algorithm (O(n^3)).

In the basic version on a U, V bipartite graph, you loop on the elements of x of U to give them the best assignement y from V. if y is already assigned, you make a growing subset X of U that may change their affectation without regret until:

* either X has at least |X| neighboors in V =\> then you move your assignements to add properly x.
* either X cannot grow anymore without regret and you accept to modify the weights (as the regret cannot be prevented).

For your problem, there is no weight. So if you are in the second case, just break off and you have your **X** subset. Else you will reach the last x of U and have a perfect assignement.
> 2 votes

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


title: Computer Networks, OSI model

text:
# Question
Title: Computer Networks, OSI model
1. What layer of OSI model does define the route of information transmission between sender and receiver computers?

A) Session layer B) Physical layer C) Data link layer D) Network layer E) Transport layer

In this question I think answer must be Network layer.But my teacher insists that answer is Transport layer.Even though i have shown in so many books it was written like that:

"Path Determination. The network layer must determine the route or path taken by packets as they flow from a sender to a receiver. The algorithms that calculate these paths are referred to as routing algorithms."

this is from book that name is "Computer Networking: Top-Down approach, 5th edition,James Kurose",

chapter 4.1.Introduction and Network Service Models

# Answer
> 1 votes
The Transport layer offers services as:

* Connection-oriented communication
* Same order delivery
* Reliability
* Flow control
* Congestion avoidance
* Multiplexing

The network layer is responsible for packet forwarding including routing through intermediate routers.

The answer is definitely Network layer.

---
Tags: computer-architecture, shortest-path
---


# Question
Title: Instructing operating system - Knowing it's functionalities
TL;DR: I would like to know how a programming language, the OS and drivers work together to perform a task.

I (and we all) have used various softwares/modules/packages on the top of our OS which provides us with a very simple API/GUI/CLI to perform tasks. But one question which keeps me disturbing is:

How does that software/module/package actually perform any specified action? I mean, it actually should be instructing OS to do that. So, OS should be providing procedure calls. But many functionalities aren't provided by the OS itself but the device driver provides it. So, how does the OS know what functions are supported by this particular device? And how can we instruct a particular device to perform a particular task?

Like suppose we are planning to change the IP address of a computer, we can do it through the OS's GUI or CLI. IP address is a logical thing and doesn't belong to a specific device (hardware), so we don't need any device driver for that. Keeping this simple, how can I write a module in python (without using already available API functionality) to change the IP address of a computer? Suppose the language itself i.e. python or a module/package written in python provides this functionality that calling a function such as change\_ip() does the task. But how does it actually work in background? I know the background job is different for different OSes but I don't know how that module/package/language interacts with the OS. Or is it doesn't actually interact with the OS and performs the operations itself? (Maybe its possible in some cases)

Now, some other example. Suppose I would like to change the MAC address of the machine. Now, this operation is device dependent (the Network Card). Also, few NICs doesn't support this MAC changing functionality. This is actually dependent on the device driver and not the driver itself. So how can the OS know if the function is supported or not? Also, if the module/package/language is directly performing tasks without the help of OS, how can it know if the functionality is supported?

A very few might understand this question.. I don't know how to ask.. I am pursuing BE in Computer Engineering and I know several concepts and theories. But our education system makes us learn the things separately and not understand them in a combined manner. Like what would be the benefit if I know Operating System and Python but I don't know how they interact with each other and work in a combined manner. So, this is the base of my query.

I looked for an answer on Google but never found one.. Thank you..

# Answer
> 1 votes
There are many possible OSes, each one with its own design philosophy and technical conventions. Here's a rough, but reasonably common design for an OS. Beware that, for brevity, I had to simplify things a bit and cut some corners. OS design is a huge topic (we have whole university courses covering that!), so don't expect this to be comprehensive.

First, we exploit some hardware support to separate the OS from the userland processes. At any time, a bit register inside the CPU tells whether the CPU is executing in "OS mode" (AKA supervisor mode) or "user mode".

In OS mode, the CPU runs unrestricted, and can read/write everywhere in RAM, modify any register of the CPU, send messages to devices ("To video card: make pixel at 542,234 black"), and so on. In user mode, the CPU can only read/write at some RAM address, and use only some CPU registers. It can not directly send messages to devices.

Crucially, it can not flip the bit which turns the CPU into OS mode, otherwise a process could bypass the protection and pretend to be the OS.

Well, almost. The CPU actually allows executing a kind of magic instruction -- let's call it `help!` -- which precisely flips that bit and put the CPU in OS mode. There is a big catch, though: `help!` also acts as a jump to a special address in RAM where OS code lies. So, a process can not go in OS mode and still execute its code, but it has to jump to a specific location, causing a part of the OS code to be executed.

Usually, before asking `help!`, the process writes some numbers in the CPU registers.

After `help!` is called, the OS reads those CPU registers, and interprets those numbers as a request from the process. For example, if in register `r1` there is number `0`, this could be a request to change a pixel in the screen (the pixel having coordinates in registers `r2` and `r3` and the new color in `r4`). The OS then runs the code to ask the video card to change that pixel. Since every card likely requires a different message to be sent for that, the OS first calls a device driver with an hardware-independent message (`color pixed X,Y as C`) and that driver will then craft and send the message to the video card. Note that the driver is run in OS mode -- it is a component of the OS (in this basic design, at least).

If instead register `r1` there is number `1`, this could request a file to be opened (the file name being specified by `r2`). This could involve asking the disk diver to access the disk.

And so on. When the OS is done, it flips the CPU mode back to "user mode" and jumps to the process code, so that it can continue.

There are usually many possible requests from a process to the OS, usually specified by an ABI (application binary interface) which describes what registers to write and with what. Sometimes there's no public ABI, but programmers are supposed to call instead a usermode library, typically written in the C programming language. That library has a public API (in C), and will provide a bridge from that to the internal OS unpublished ABI.

There requests are known as "system calls" or "syscalls", by the way.

If you want to do a syscall in python, without relying on absolutely any library, you can not. This is because bare python does not give you a way to control the registers, or to run the `help!` instruction. Python is not special here, bare C also does not allow that, as with most programming languages.

Usually, though, one exploits some library. Or, if one really wants to go low-level, one can write a small module directly in assembly, and then call that from C or python (or anything else). That could require to use a "foreign function interface", so to link the assembly module with the language. In C it's usually very easy to do, since the language is low level. In python, calling assembly could be harder to do, but it's surely doable.

I strongly recommend you try to read an OS textbook. It should cover these topic in much more detail than we can do here.

---
Tags: operating-systems
---


# Question
Title: How to perform local search to find maximal induced subgraphs?
I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.

What I mean by local search is moving from solution to solution by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

# Answer
All three problems are easy to formalize as local search problems. Let $f$ be a function that measures the quality of a solution $s$, in your cases

$f(s)$ is

* the number of edges (or vertices) in the tree $s$
* the number of edges (or vertices) in the forest $s$
* the number of vertices (?) in the bipartite graph $s$

and your goal is to maximize $f$.

Lastly, you need to define a *neighborhood function* $N(s)$ that gives all possible ways of modifying a current *solution* $s$ to a new solution $s'$.

To illustrate $N(s)$ in the simplest case, the tree: $$ N(s) = \\{ X \subseteq V(G) \mid \text{is\_tree}(V(s) \setminus X \cup (X \setminus V(s)) \\}, $$

and my apologies for the terse syntax. It is simply all the ways you can delete a certain set of vertices from the solution $s$, simultaneously adding a different set of vertices, at the same time keeping the property that the new $s'$ is a tree.

Now, the search algorithm simply starts with a random solution (tree) $s$ (which might be the empty tree), and just randomly walk $N(\cdot)$.
> 0 votes

---
Tags: graphs, graph-traversal, heuristics
---


title: The first Turing machine

text:
# Question
Title: The first Turing machine
Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web.

# Answer
"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:

* Writing proofs about physical wires and switches is extremely difficult.
* Writing proofs about Turing machines is (relatively) easy.
* Anything physical wires and switches can do, you can build a Turing machine to do (\*) (\**).

But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.

Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's *stronger* than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.

So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.

(\*) Specifically, any *calculation*: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.

(\**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.
> 61 votes

# Answer
Turing never built a physical Turing machine. The point of Turing machines was not to be a practical physical computer but to formalize what it's possible to compute and, indeed, to formalize what "computation" even means.
> 18 votes

# Answer
Let me bring some serious fun, although it might not be the wanted answer.

---

**Claim One**: Lots of Turing machines have been built, by Alan Turing and by many others.

Proof. Pointing to an immovable bolt in a bombe, Alan Turing said with his usual keen insight and simplicity, "look, a Turing machine that halts upon any given input".

**Moral**: There are many kinds of Turing machines. Many of them are extremely simple. But they are (functionally) Turing machines.

---

**Claim Two**: It is undecidable whether a machine has unbounded memory.

Proof. I have a computing machine, for which it will take one second to demonstrate each additional bit of memory. I want to convince you that it does not have unbounded memory. However, being a cautious positivist, you insists that nobody can reject that it has unbounded memory in any time soon or even forever.

**Moral**: be careful when we are talking about objects that expand on demand.
> 8 votes

# Answer
This is a perfect place and time to referr to the actual paper where the Turing machine is first described. One link is here:

https://www.cs.virginia.edu/~robins/Turing\_Paper\_1936.pdf

Of course, he is more modest, so he calls it the "automatic machine". There is no actual machine, only a beast of imagination.

Turing, as far as we know, never even tried to build the "automatic machine". He was however extremely influential in making a number of other machines. The WW2 bombe, used to break Nazi Germany ziphers, is the most famous example.

Sadly, it was first well after his death that the general public was made aware of his achievements. (He killed himself it is said, after beeing brutally subjected to chemical sterilization as beeing a convicted homosexual).
> 8 votes

# Answer
The TM only exists on paper. It is a theoretical model of computation. It actually can't be built (because the tape is infinitely long).

So, the answer is: no, Turing never built a TM in real life, because he can't.

---

Please do not keep arguing that "we can build a Turing machine, just that it doesn't have infinite tape, because by definition a TM has an infinitely long tape. If it does not have an infinitely long tape, then it is not a Turing machine. It is as simple as that.

I am fully aware that people have built "TMs with finite tapes" and neither am I doubting the usefulness of that (i.e. bounded automata): in fact, given an long enough tape, we can compute basically all practically interesting things (that are Turing computable). But for every natural number $n$, there will be a TM that would necessarily require a tape of length $n+1$ to simulate, so there's never a "large enough" tape. (Think why.)

Setting a step back, there are easily TMs we can't build or evem simulate with finite resources. Take the TM which writes one * on its first step, goes right and writes two \*s on its second step, etc. This TM can not be built or even simulated without an infinite amount of memory.
> 3 votes

# Answer
Here is a video with a real Turing machine working. Its quite nice and helped me to stop seeing it as a mere mathematical model:

https://www.youtube.com/watch?v=E3keLeMwfHY
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Matrix Representation for logical gates?
I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \\, \\, \Rightarrow$$ where:

$$ \begin{bmatrix} X, \ \neg X \end{bmatrix}\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} X \oplus \neg X, \ 0 \oplus \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} 1, \ \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix}$$ $$ = Y \oplus (\neg X \neg Y) = X \Rightarrow Y$$

Note that the juxtaposition of two variables without an operator corresponds to conjunction i.e. $XY = X \wedge Y$ and of course $1 \wedge X = X$ and $0 \wedge X = 0$ and are written accordingly. Actually all of the propositional logical operators can be done with a unique binary $2 \times 2$ matrix - it is fascinating.

# Answer
Yes, "all of the propositional logical operators can be done with a unique binary 2×2 matrix".

In fact, every possible map $g: \\{0,1\\}\times\\{0,1\\}\to\\{0,1\\}$ can be done with a unique binary 2x2 matrix.

Here is a proof.

$$\begin{align} &\quad \begin{bmatrix} X, \ \neg X \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\\&= \begin{bmatrix} XA \oplus \neg XC, \ XB \oplus \neg XD \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\ &= XAY \oplus \neg XCY \oplus XB\neg Y \oplus \neg XD\neg Y\\ \end{align}$$

* Suppose the above expression equals $g(X,Y)$.
    + Let $X=0, Y=0$, we get $0\oplus0\oplus0\oplus D=D=g(0,0)$.
    + Let $X=0, Y=1$, we get $0\oplus C\oplus0\oplus 0=C=g(0,1)$.
    + Let $X=1, Y=0$, we get $0\oplus0\oplus B\oplus 0=B=g(1,0)$.
    + Let $X=1, Y=1$, we get $A\oplus0\oplus0\oplus 0=A=g(1,1)$.
* Conversely, if we have $A= g(1,1)$, $B= g(1,0)$, $C=g(0,1)$ and $D=g(0,0)$, the above expression can be verified to be equal to $g(X,Y)$ for all $X, Y$.

So we have proved that

$$ \begin{bmatrix} X, \ \neg X \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = g(X,Y) \\ \Leftrightarrow A= g(1,1),\ B= g(1,0),\ C=g(0,1),\ D=g(0,0)$$

If we use in-fix notation for $g$, we have $$ \begin{bmatrix} X, \ \neg X \end{bmatrix} \begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = XgY, $$ or $$ \begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix} \equiv g. $$ In particular, we can substitute $g$ by anyone of $\land, \lor, \oplus, \odot, \Rightarrow, \Leftarrow, \equiv$.

---

For more related concepts and computation, please check boolean rings.
> 3 votes

---
Tags: discrete-mathematics, matrices, propositional-logic
---


# Question
Title: Which of the following statements are true for the given special cases of the Traveling Salesman Problem?
I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

> Which of the following statements is true?
>
> * Consider a TSP instance in which every edge cost is either 1 or 2. Then an optimal tour can be computed in polynomial time.
> * Consider a TSP instance in which every edge cost is negative. The dynamic programming algorithm covered in the video lectures might not correctly compute the optimal (i.e., minimum sum of edge lengths) tour of this instance.
> * Consider a TSP instance in which every edge cost is negative. Deleting a vertex and all of its incident edges cannot increase the cost of the optimal (i.e., minimum sum of edge lengths) tour.
> * Consider a TSP instance in which every edge cost is the Euclidean distance between two points in the place (just like in Programming Assignment #5). Deleting a vertex and all of its incident edges cannot increase the cost of the optimal (i.e., minimum sum of edge lengths) tour.

I argue as follows:

The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.

If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.

Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex v, skip straight from v's predecessor to its successor on the tour. Because Euclidean distance satisfies the "Triangle Inequality", this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.

However, I'm not able to find any significance for TSP problems with unit edge costs. Is option 1 merely a trick, or is there more to it?

# Answer
OP here.

Papadimitriou and Yannakakis have shown that it is possible to approximate the TSP problem 1 in polynomial time within accuracy $ \frac{7}{6} $. This guarantee has been further improved by Bläser and Shankar Ram to $ \frac{65}{56} $. However, no matter how good those results are, they are still approximations, and not an optimal solution. Thus, option 1 is incorrect.

The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.

If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.

Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex $ v $, skip straight from 's predecessor to its successor on the tour. Because Euclidean distance satisfies the Triangle Inequality, this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.
> -1 votes

# Answer
Statement 1 is false (assuming P $\neq$ NP) because any instance $G$ of the NP-complete Hamiltonian Cycle problem can be reduced to an instance of the TSP in which every edge cost is either 1 or 2.

Why? Define a TSP instance on a complete graph $K\_n$, with edge cost 1 whenever the corresponding edge is also in the original graph $G$, and edge cost 2 otherwise. Now a TSP tour of cost $\le n$ exists in the complete graph if and only if $G$ has an Hamiltonian cycle.
> 2 votes

---
Tags: algorithms, complexity-theory, np-complete, reductions, traveling-salesman
---


# Question
Title: System restarted before transaction is committed
Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.

```
T1 start
T1 B old=1200 new=10000
T1 M old=0 new=2000
T1 commit
T2 start
T2 B old=10000 new=10500
T2 commit

```

Suppose the database system crashes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?

(a) We must redo log record 6 to set B to 10500

(b) We must undo log record 6 to set B to 10000 and then redo log records 2 and 3

(c) We need not redo log records 2 and 3 because transaction T1 has committed

(d) We can apply redo and undo operations in arbitrary order because they are idempotent

According to me, the answer should be (a), as transaction T1 has been committed and has been written back into memory. But my solution says that the answer should be (b).

Am I right or what am I doing wrong?

Thanks in advance!

# Answer
The correct answer is (b) under the assumption that the recovery algorithm used is the *undo-redo* algorithm, which is one of the most commonly used, and which can be used if the DBMS adopts both the *immediate update* policy and the *immediate commit* policy (instead of the *deferred update* and the *deferred commit* policies).

The *immediate update* policy allows that updated pages can be written to the database before the transaction has committed; The *immediate commit* policy allows the commit record to be written to the log before all updated pages have been written to the database. Those policies require the use of Write Ahead Log (WAL) rule (write the updates to the log file before writing to disk) and of Commit rule (the after-images of the updates are written to the log file before the commit of the transaction).

Under this hypothesis, when a failure occurs, the recovery algorithm *must* undo all the transactions non committed, and *redo* all the transaction committed, going back in the log file **until a checkpoint record is found or until the beginning of the log file**.

So, the correct answer is (b) since also T1 must be redone. In fact, we do not know if its updates to the database have been written or not (as I said, assuming that we are in the case of *immediate commit* policy).
> 2 votes

# Answer
Regardless of the commit policy of the database, (a) cannot be right. After the restart, the log contains

```
T2 start
T2 B old=10000 new=10500

```

Since there is no commit record for T2, there is no way to know that T2 was finished. Maybe T2 should have included another part whose record was not written. Therefore it cannot be correct to perform any part of T2.
> 1 votes

---
Tags: concurrency, database-theory
---


# Question
Title: Bucket computation, cutting array with lines
Given an NxN array, drawing a line from the edge's midpoint to the opposite field how can the N buckets be found covering the majority of the line's path?

A visual aid:

Is there a better way to this than computing the linear equation and iteratively advancing in tiny steps to check which bucket we fall on? If not what is the lower limit step size to choose?

# Answer
> 1 votes
For the considered line you know the start position (xs, ys) and the end (xe, ye). For instance on the N=7 visual you provide, let's take the first upper left line:

```
xs = 0
ys = 4.5
xe = 7
ye = 2.5
(I use coordinates right, down starting from upper left corner).

```

Let's take a parameter t of the linear position on the line with t=0 on start and t=1 on end. You know how many verticals or horizontals your line crosses and at which t value. In our exemple:

* 6 verticals crossed at t = v/7 with v=1 to 6 (not counting outlines).
* 2 horizontal crossed at t = 0.25 and t = 0.75.

Now just sort t increasing all these crossings:

```
(1/7, V), (0.25, H) (2/7, V), (3/7, V), (4/7, V), (5/7, V), (0.75, H), (6/7, V).

```

They correspond to cell change starting in cell (1, 5) to cell (7, 3). So you can compute the relative length of the line in each cell. For instance:

```
cell (1, 5) L = 1/7-0 = 1/7
cell (2, 5) L = 0.25-1/7
...

```

And you know how to select the X pixels now.

# Answer
> 1 votes
You probably want to look at Bresenham's line drawing algorithm. Rather than moving along the line itself, you move along the $x$-coordinates a "pixel" (i.e., array entry) at a time and compute which $y$-value puts the greatest part of the line in the pixel $(x,y)$.

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


# Question
Title: Constructing a pushdown automaton that accepts L*
Would appreciate if you could take a look at what I did and help me finish it.

> Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^\*$. Use a "double bottom" if need be.

My attempt:

Given $M = (Q,\Sigma,Γ,\delta,q\_0,⊥,∅)$, we'll add a double bottom by altering the function: $\delta' := \delta'(q\_0',\epsilon, ⊥')={(q\_0, ⊥⊥)}$, so M' is basically $M' = (Q\cup{q\_0',q\_f},\Sigma,Γ∪{⊥'},\delta',q\_0',⊥',{q\_f})$. The accepting state is reached by $\forall q \in Q\colon \delta' (q,\epsilon,⊥')={(q\_f,⊥')}$.

How do I finish it so that it accepts $L^\*$?

# Answer
> 1 votes
The Kleene star is, as you know, the union $\bigcup\_n L^n$ of arbitrary powers $L\cdot L\cdot\ldots\cdot L$ of $L$.

If $M$ is the automaton that accepts $L$, then in order to make an automaton for $L^\*$ you basically have to make it possible to restart the automaton after accepting $L$. Be careful in choosing final state or empty stack acceptance.

---
Tags: automata, pushdown-automata
---


# Question
Title: Choosing heuristic for A* algorithm where cost is less than absolute distance
Looking for information on choosing a heuristic for instances where the cost of traversing an edge can be less than one.

For example, say movement is allowed in the cardinal directions. Should all edge costs be at least one, then I would consider diagonal distance. However, if costs can be less than one, this could lead to an instance where diagonal distance will be an overestimate and thus is not an admissible heuristic.

My thought on the matter is perhaps to find the smallest possible cost and figure out a constant to divide diagonal distance by to guarantee it will never overestimate?

Would appreciate some guidance or some resources to look further into this.

# Answer
The simple options are to either multiply all path costs such that minimum cost is 1. Or multiply the heuristic such that the min cost is more or equal than the heuristic tells you for the same path.

The more complicated option is to look at the graph and estimate the chance that you will end up going through the low cost area. This requires some precalculation of the low cost areas and their influence on paths.

For example a low cost highway, any heuristic that is close to it will need to get a bonus to account for taking the highway. But heuristics that are not going to take the highway can use the larger estimation.
> 3 votes

# Answer
I don't know how helpful diagonal distances actually are here.

You could figure out the minimum cost of any edge, and then multiply the Manhattan distance (vertical difference plus horizontal difference) by that.

It would be better (give you a tighter lower bound) to figure out the minimum cost of any *vertical* edge, and then multiply the vertical component of the distance between source and target by that, do the same for horizontal edges, and then add the (separately) weighted horizontal and vertical distances together.

If your graph is grid-shaped, it would be better still to figure out, in a preprocessing step, for each column $x$ of parallel horizontal edges, what the minimum weight is of any edge in that column, and store this in $h\[x\]$. Then for each row $y$ of parallel vertical edges, figure out the minimum weight of any edge in that row, and store that in $v\[y\]$. Then for source and target at $(x\_s, y\_s)$ and $(x\_t, y\_t)$, respectively, $\sum\_{i=x\_s}^{x\_t} h\[i\] + \sum\_{j=y\_s}^{y\_t} v\[j\]$ is a lower bound on the distance from source to target. (You can even compute this in constant time, by building a list of partial sums for each direction during preprocessing, and subtracting: e.g. if you have precomputed $H\[a\] = \sum\_{b=1}^{b=a} h\[i\]$, then $\sum\_{i=x\_s}^{x\_t} h\[i\] = H\[x\_t\] - H\[x\_s - 1\]$.) Rationale: Any path from source to target must cross each of those rows and columns *somehow*, and you can't do better than by using the least-cost edge to do so in each case.
> 1 votes

---
Tags: algorithms, artificial-intelligence, heuristics
---


title: Max flow and Matching problem

text:
# Question
Title: Max flow and Matching problem
Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .

# Answer
> 4 votes
Based on the book "*Algorithm Design*" by Kleinberg and Tardos, Kevin Wayne has a set of slides (second part here) where the following applications of max flow and matching are presented in some detail:

* survey design
* airline scheduling
* image segmentation
* project selection
* baseball elimination
* assignment problem
* input-queued switching

For even more examples, have a look into the exercises of Chapter 7 of Kleinberg and Tardos' book, or into the exercises of the book "*Network Flows: Theory, Algorithms, and Applications*" by Ahuja, Magnanti and Orlin.

---
Tags: reductions, np-hard, approximation
---


# Question
Title: Reducing a graph without changing its chromatic number
Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name?

Take this cactus graph as an example (although my question is about an arbitrary graph):

The edges with vertex of degree 1 could be removed without affecting the vertex chromatic number. I think something similar should be possible with cycles e.g. removing the two vertices in the bottom of the cactus should not affect its chromatic number.

Are there polynomial algorithms that removes edges **to the extent that no more edge can be removed** without affecting an arbitrary graph chromatic number? I would prefer not to reinvent the wheel.

If the answer is no, are there algorithms that remove **an arbitrary number of edges** without affecting an arbitrary graph chromatic number?

My goal is to simplify graphs before feeding them into other algorithms.

I will also appreciate references to relevant literature. Thank you!

# Answer
The general idea of taking a problem instance and reducing it to a smaller one that gives the same answer is called kernelization. It's widely used in parameterized complexity theory and not just for colourings.
> 3 votes

---
Tags: graphs, colorings
---


# Question
Title: Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$
How can I prove that $SEQ\_{CFG} = \\{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\\}$ is decidable ?

I know that $EQ\_{CFG} = \\{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\\}$ is not.

# Answer
> 0 votes
Another way to see that your problem is undecidable is by reduction from universality. It is known that one cannot decide whether $L(H) = \Sigma^\*$. This is just your problem when $L(G) = \Sigma^\*$.

# Answer
> 4 votes
We also know that $L(G)=L(H)$ iff both $L(G)\subseteq L(H)$ and $L(H)\subseteq L(G)$.

Now assume $SEQ\_{CFG}$ is decidable, then we can decide both ...

---
Tags: context-free, proof-techniques
---


title: A totally-ordered set of functions

text:
# Question
Title: A totally-ordered set of functions
When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well represented by $\Theta(n)$. This makes me ask whether it is possible to define a set of "representative functions" which are totally ordered by the $o$-notation?

Concretely, let $F$ be the space of all positive, monotonically increasing real functions on $N$ (the natural numbers). I am looking for a subset $G\subseteq F$ with the following properties:

1. For every two functions $g\_1,g\_2 \in G$, either $g\_1(n) = o(g\_2(n))$ or $g\_2(n) = o(g\_1(n))$.
2. For every function $f\in F$, there is a function $g\in G$ with $g(n)=\Theta(f(n))$

Does there exist such a set? If so, how can it be represented (e.g. how many real parameters are required?)

# Answer
This question is very natural since most if not all common functions that appear in the runtime-analysis of algorithms form a totally ordered set in terms of little $o$-notation or big $\Omega$-notation such as shown in this answer by Robert S. Barnes or this answer by Kelalaka.

---

However, **there is no such totally-ordered set of representative functions for all positive increasing functions**.

The basic reason is the first property, when applied to $F$, does not define a total-order.

Define two strictly increasing $f\_1(n)$ and $f\_2(n)$ from $\Bbb N$ to $\Bbb N$.

$$f\_1(n)=2^{(2\lceil\frac {n+1}2\rceil)^2+n}$$ $$f\_2(n)=2^{(2\lfloor\frac {n}2\rfloor+1)^2+n}$$

Then $$\sup\lim \_{n\to\infty}\frac {f\_1(n)}{f\_2(n)} \ge \lim\_{n=2i+1\to\infty}\frac {f\_1(n)}{f\_2(n)} =\lim\_{i\to\infty}\frac {2^{(2(i+1))^2+2i+1}}{2^{(2i+1)^2+2i+1}} =\lim\_{i\to\infty}2^{4i+3}=\infty$$

$$\sup\lim \_{n\to\infty}\frac {f\_2(n)}{f\_1(n)} \ge \lim\_{n=2i\to\infty}\frac {f\_2(n)}{f\_1(n)} =\lim\_{i\to\infty}\frac {2^{(2i+1)^2+2i}}{2^{(2i)^2+2i}} =\lim\_{i\to\infty}2^{4i+1} =\infty$$

In plain words, neither of $f\_1(n)$ and $f\_2(n)$ grows asymptotically the same or faster than the other one ignoring a constant factor.

Let $F$ and $G$ be defined as in the question. Suppose $G$ exists. Then there is $g\_1, g\_2\in G$ such that $g\_1(n)=\Theta(f\_1(n))$ and $g\_2(n)=\Theta(f\_2(n))$. Then $g\_1(n)\>c\_1(f\_1(n))$ for some constant $c\_1\>0$ and $g\_2(n)\<d\_2(f\_2(n))$ for some constant $d\_2$. (In usual cases, we have to say "for $n$ large enough". However, that clause can be omitted since all values here are positive. Anyway, we can add that clause as well.)

$$\sup\lim \_{n\to\infty}\frac {g\_1(n)}{g\_2(n)} \ge \sup\lim\_{n\to\infty}\frac {c\_1f\_1(n)}{d\_2f\_2(n)} \ge \frac{c\_1}{d\_2}\sup\lim\_{n\to\infty}\frac {f\_1(n)}{f\_2(n)} =\infty $$

Symmetrically, $\sup\lim\_{n\to\infty}\dfrac {g\_2(n)}{g\_1(n)}=\infty$. We see that $g\_1\not=g\_2$ but neither $g\_1(n) = o(g\_2(n))$ nor $g\_2(n) = o(g\_1(n))$. This contradition shows $G$ does not exist.

---

How about if we drop the first requirement so that the functions in $G$ are not required to dominate each other?

Then this question becomes closely related to the question Big O notation and the maximal set of comparable functions as found by OP, where a couple of enlightening answers explain the situation pretty well, indicating there is hardly any hope for a nice positive answer. Even countably-infinitely real parameters cannot parametrize continuously a set of representative functions in the equivalence classes of increasing functions where two functions are in the same equivalence class if they are related by $\Theta$ and each function only uses finitely-many parameters.

---

Explicit rigorous answers to the following exercises might be long. However, the ideas should be simple for experienced users.

(**Exercise 1.**) For any given positive integer $n$, construct $n$ increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f\_1$ and $f\_2$, neither $f\_1=O(f\_2)$ nor $f\_2=O(f\_1)$.

(**Exercise 2.**) Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f\_1$ and $f\_2$, neither $f\_1=O(f\_2)$ nor $f\_2=O(f\_1)$.

(**Exercise 3.**) Let $h(n)$ be a given function from $\Bbb N$ to $\Bbb N$. Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f\_1$ and $f\_2$, neither $f\_1=O(h\ f\_2)$ nor $f\_2=O(h\ f\_1)$.
> 1 votes

---
Tags: asymptotics, complexity-classes, mathematical-analysis
---


# Question
Title: Who first introduced the pushdown automaton?
I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble finding a source that first introduces pushdown automata. Who first developed them, and what was the context?

# Answer
Ginsburg (in his book *The Mathematical Theory of Context-Free Languages*, McGraw-Hill, 1966) states in the Historical References (Section 2.7, page 81):

> Pushdown acceptors were first formalized by Chomsky \[Ch5\] and Evey \[Ev\], although the notion of a pushdown tape has been used since 1954.

\[Ch5\] N.Chomsky, context-free grammars and pushdown storage, MIT Res. Lab. Electron. Quart. Prog. Rept. 65, 1962.

\[Ev\] R.J.Evey, The theory and applications of pushdown store machines, Mathematical Linguistics and Automatic Translation, Harvard Univ. Computation Lab. Rept. NSF-IO, May, 1963.

The context can be read from the Preface of the same book.

> The concept of a context-free language was first introduced by Chomsky in 1959 in an attempt to find a reasonable mathematical model of natural language such as English, French, etc. In the period 1959-1960, several papers developing the theory were written. In the late 1960, it was discovered that the "ALGOL-like" languages, that is, the languages defined by Backus normal form (the metalanguage used to describe the widely publicized programming language ALGOL-60), where identical with the context-free languages. Since then, there has been a flurry of activity in the theoretical development of context-free languages. Much of this work has been done by those concerned either with natural languages in connection with computers, or with programming languages. The remainder has been by mathematicians and logicians intrigued by the inherent problems, techniques, and results. This activity has been given birth to a number of theoretical results of concern to computer science, and especially to programming technology. For example, we have the characterization of a context-free language in terms of a pushdown acceptor (a device used in the parsing aspect of compiling). \[...\]
> 5 votes

---
Tags: pushdown-automata, history
---


# Question
Title: Sampling perfect matching uniformly at random
Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am okay with a distribution that is close to uniform, but not quite uniform, then is there an efficient algorithm?

# Answer
There is a classical paper of Jerrum and Sinclair (1989) on sampling perfect matchings from dense graphs. Another classical paper of Jerrum, Sinclair and Vigoda (2004; pdf) discusses sampling perfect matchings from bipartite graphs.

Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform sampling is difficult.
> 10 votes

# Answer
If you assume that your graph is planar, then there is a polynomial time procedure for this sampling problem.

First, the problem of counting the number of perfect matchings is in P for planar graphs. ( https://en.wikipedia.org/wiki/FKT\_algorithm ) ( A good exposition of this fact can be found in the first chapter of Jerrum's book on Counting, Sampling and Integrating.)

Next, for each edge $e$ of $G$, count the number of perfect matchings of $G \setminus e$. This can be turned into the probability that a uniform perfect matching contains $e$ \- just divide by the number of perfect matchings in $G$. Sample an edge according to this probability, and continue inductively.

(This is taking advantage of the fact that matchings are a "self-reducible" structure, so counting problems and uniform sampling problems are essentially the same. You can see JVV "Random Generation of Combinatorial Structures from a Uniform Distribution" for more on this point of view.)

A simple proof that this gives the correct distribution:

Let $c(H)$ denote the number of ordered perfect matchings in a graph $H$, as ordered sequences. (Which is $n!$ times the number of unordered perfect matchings, $n = H/2$.)

Let $e\_1, \ldots, e\_n$ the sequence of edges chosen in this procedure. Since each step was independent of the former, the probability of choosing this sequence of edges is:

$\frac{ c(G \setminus e\_1)}{c(G)} \frac{ c(G \setminus \\{e\_1, e\_2\\} )}{c(G \setminus e\_1)} \ldots \frac{ c(G \setminus \\{e\_1, \ldots, e\_{n-1} \\}) }{c(G \setminus \\{ e\_1, \ldots, e\_{n-2} \\} )}$.

Note that $c(G \setminus \\{e\_1, \ldots, e\_{n-1} \\}) = 1$, since $G \setminus \\{e\_1, \ldots, e\_{n-1} \\}$ is just the edge $e\_n$. So this product telescopes and leaves $1 / c(G)$.
> 3 votes

---
Tags: algorithms, complexity-theory, matching, sampling
---


title: Solving $T(n) = 3T(n-1) + 2$

text:
# Question
Title: Solving $T(n) = 3T(n-1) + 2$
I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence:

$$T(n) = 3T(n-1) + 2, \quad\quad T(1) = 1$$

My work at solving it: $$\begin{align\*} T(n) &= 3^2T(n-2) + 3\*2 + 2 \\ &= 3^3 T(n-3) + 3^2\*2+ 3\*2 + 2 \\ &= 3^4 T(n-4) + 3^3\*2 + 3^2\*2 + 3\*2 + 2 \\ &= \dots \\ &= 3^k T(n-k) + 3^{k-1}\*2+3^{k-2}\*2 +\dots+3\*2+2 \\ &= 3^k + 3^{k-1}\*2+3^{k-2}\*2 +\dots+3\*2+2 \\ &= 3^k +\[\sum\_{i=1}^{k-1} 3^i\*2 \] + 2 \end{align\*}$$

where $k = n - 1$.

I guess the Big O would be exponential since the above would be less than $3^n$ which is $O(c^n)$?

I am stuck on how to finish this and find out what the time complexity is in Big O notation.

# Answer
As Apass.Jack hinted at in the comments, you were a bit careless when multiplying and adding everything. Here is a hint for you: $$\begin{align\*} T(n) &= 3T(n - 1) + 2 \\ &= 3^2 T(n - 2) + 2 \cdot 3 + 2 \\ &= 3^3 T(n - 3) + 2 \cdot 3^2 + 2 \cdot 3 + 2 \\ &= 3^4 T(n - 4) + 2 \cdot 3^3 + 2 \cdot 3^2 + 2 \cdot 3 + 2 \\ &= \cdots \\ \end{align\*}$$

When solving these types of recursion, it usually helps *not* to simplify expressions (e.g., "$2 \cdot 3$" helps you a lot more than multiplying and writing just "$6$"). This is the only way you can manage to recognize more complicated patterns.

Bonus exercise once you are done with this: Try and solve the more general recurrence $T(n) = a T(n-1) + b$ for arbitrary $a$ and $b$.
> 1 votes

# Answer
Let us add $1$ to both sides of your recurrence: $$ T(n) + 1 = 3T(n-1) + 3 = 3(T(n-1) + 1). $$ This shows that $$ T(n) + 1 = 3^{n-1}(T(1) + 1), $$ and so $$ T(n) = 2 \cdot 3^{n-1} - 1. $$
> 3 votes

---
Tags: recurrence-relation
---


# Question
Title: d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions
Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.

Then for a fixed $|V|$, what is the largest possible ratio between this runtime and the runtime of Dijkstra using a Fibonacci heap? Where knowing the Fibonacci heap: delete\_min = $O(\log |V |)$, insert/decrease\_key = $O(1)$ (amortized) and $|V|$ × delete\_min + $(|V | + |E|) $ x insert $= O(|V|\log|V|+|E|)$.

On the other hand, d-ary heap implementation : delete\_min = $O(\dfrac{d \log|V|}{\log d})$, insert/ decrease\_key =$O(\dfrac{\log|V|}{\log d}$), and |V | × delete\_min + (|V | + |E|) × insert = $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d})$.

As trying to follow a provide solution, but I am not sure why it reduces to $O(\dfrac{\log|V|}{\log |E|/|V|})$, in the case 1 where |E| dominates, so Dijkstra with Fibonacci heap is $O(|E|)$. How can we get the ratio as $O(\dfrac{\log|V|}{\log |E|/|V|})$ while Dijkstra with d-ary heap is $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d}$)?

# Answer
The crux is right there in the first paragraph of the post.

> Let's say that Dijkstra’s algorithm with the priority queue using a $d$-ary heap. We can achieve the best runtimes for the algorithm with $d$ being $\sim |E|/|V|$.

As you have pointed out, the time-complexity of Dijkstra with $d$-ary heap is $O\left((|V|\cdot d+|E|)\dfrac{ \log|V|}{\log d}\right)$. Substituting $|E|/|V|$ for $d$, we see the best time-complexity of Dijikstra with d-ary heap is $O\left((2|E|)\dfrac{\log|V|}{\log|E|/|V| }\right)=O\left(\dfrac{|E|\log |V|}{\log |E|/|V|}\right)$.

In the case 1 where $|E|$ dominates, the ratio of the best time-complexity of Dijkstra with $d$-ary heap to $O(|E|)$, the time-complexity of Dijkstra with Fibonacci heap is $\dfrac{\log|V|}{\log |E|/|V|}$ (ignoring some constant factor), which takes its maximum value when $|E|$ takes its minimum value, $|V|\log |V|$. Hence we get the ratio $\dfrac{\log|V|}{\log\log|V|}$.
> 1 votes

---
Tags: asymptotics, heaps, performance, comparison
---


# Question
Title: Optimal dividing of K people into N groups
A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either `4 groups of 3`, or `3 groups og 4`. Each student can pick up to 3 other students that person would most rather be with.

I tried to set this up as an undirected weighted graph, and implement shortest path algorithms, but the shortest path here doesn't ensure that as many students as possible get their top wish.

What algorithm should I look into here, in order to achieve to most optimal solution to a problem like this?

Here is a visualisation of the problem:

# Answer
Solution in pseudocode:

```
initialize collection of persons (e.g. an array):
    - each person itself is described by its position in collection
    - each person itself contains collection of positions (e.g. an array)
      that describe wished persons for the person to be grouped with
(example: persons = [[1,2], [0,2], [0,3], [0,2]])

initialize empty collection of groups (e.g. an array):
    - each group itself is described by its position in collection
    - each group itself contains collection of positions (e.g. an array)
      that describe grouped persons

initialize number of persons per group (example: 2)
initialize total group count to be number of persons divided by number of persons per group (example: 2)
initialize constraint c1 as: any group shouldn't exceed the number of persons per group
initialize constraint c2 as: group count shouldn't exceed the number of total group count
initialize constraint c3 as minimum required of wishes granted per person in any group, for the solution to be valid (example: 1)
[*]initialize dictionary of solutions, where key is a pair (persons, groups), and value is a solution or an empty value

call group(persons, groups)

procedure group(persons, groups):
    [*]if there is a pair (persons, groups) in dictionary of solutions
    [*] return that solution

    for each person (let's call it this-person)
        for each person among this-persons wishes (let's call it wished-person)
            if wished-person is already grouped in any of the groups
                if this-person can be grouped in the same group with wished-person, at the same time satisfying c1
                    set new-groups as groups with this-person grouped accordingly
                    set new-persons as persons without this-person
                else
                    nothing can be done with wished-person, so continue with the next wished-person
            else
                if both this-person and wished-person can be grouped in any group, at the same time satisfying c1 and c2
                    set new-groups as groups with this-person and wished-person grouped accordingly
                    set new-persons as persons without both this-person and wished-person
                else
                    nothing can be done with wished-person, so continue with the next wished-person

            if there are any other persons left in new-persons
                set possible-solution to recursive call, group(new-persons, new-groups)
                if possible-solution is not empty
                    [*]add item to dictionary of solutions, key is the pair (persons, groups), value is possible-solution
                    return it as a solution
            else if all the groups satisfy c3
                return new-groups as the solution

    [*]add item to dictionary of solutions, key is the pair (persons, groups), value is empty
    return empty value

```

The decision tree will exhaust all the possible paths towards the solution. However, if you use dynamic programming you can improve the performance by avoiding the execution of already known paths. The dynamic-programming part is marked with `[*]` in pseudocode.

You might further improve the performance by preferring least-popular persons over most popular when grouping.

Here's a Python implementation in case anyone needs it: https://repl.it/@OzrenTkalcec/Dividing-of-K-people-into-N-groups

*Disclaimer: I'm not a data scientist, but I like to solve puzzles like this one :)*

HTH
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Are Big-Theta functions asymptotic monotonically non decreasing?
For example, suppose $f(n) = \Theta(n^2)$, then does that mean for any sufficiently large $n$, $f(n) \le f(n+1)$? Is it a general case for all Big-Theta?

# Answer
No, it may not be true.

Consider the following function on $\Bbb N$.

$$f(n)=\begin{cases} (n+2)^2\quad &\text{when } n \text { is odd,}\\ n^2\quad &\text{when } n \text { is even.}\\ \end{cases}$$

Then $f(n)=\Theta(n^2)$. However, for all odd $n$, $f(n)\>f(n+1)$. In fact, $f(n)-f(n+1)\to\infty$ when $n$ goes to $\infty$ along the odd numbers.

---

Here are two related exercises.

**Exercise 1.** Give an example of $f(n)=\Theta(n)$ such that $f(n)\>f(n+1)$ for infinitely many $n$.

**Exercise 2.** Let $g(n)\ge0$ be an unbounded function on $\Bbb N$.

* Let $h(n)=\Theta(g(n))$. Prove that $h(n)\<h(n+1)$ for infinitely many $n$.
* Construct $f(n)=\Theta(g(n))$ such that for any number $c$, $f(n)-f(n+1)\>c$ for infinitely many $n$.
> 5 votes

# Answer
It's not true in general: consider a function that is $\Theta(1/n)$.
> 1 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: ARM STM instruction: page fault problem with MMIO
The ARM `STM` instruction is described here in the ARM manual. This instruction writes all or a subset of registers at memory locations starting from a base memory address. The manual does not impose any restriction on the start address. So, can the start address be such that some/all of the writes end up in MMIO address? If so, there can be a problematic scenario where a page fault happens in the execution of the STM instruction: Suppose the base memory address is `b` and 10 registers are to be written. The range `b` to `b+5` belongs one page and the range `b+6` \- `b+9` belongs to the next page. Suppose the virtual first page (where `b` belongs) is mapped to a physical page that corresponds to MMIO. Suppose the next virtual page is mapped to DRAM. Suppose that whe the STM execution tries to do the 7th write, to the address `b+6`, a page fault happens because the DRAM page is swapped out. The page fault handler loads that DRAM page and restarts the `STM` instruction. The first 6 writes (`b` to `b+5`) will be done again. Because these writes go to MMIO which can be mapped to devices, this operation may not be idempotent, e.g. it can launch some missiles twice!. The first 6 writes should not be repeated. How do page handlers handle this problem, if they handle it at all?

The STM instruction is just an example. The same problem happens with any instruction that does multiple writes that span different virtual pages.

# Answer
> 1 votes
What if the STM instruction were executed speculatively, and an instruction ahead of it faults? Or it's behind a mispredicted branch?

I can't speak for all ARM variants (things have probably changed over time), but the semantics of any instruction must be that if the instruction causes a fault, it's as if the instruction didn't happen.

What modern ARM cores probably do is use the store buffer. All stores (apart from TCM, which is by definition not MMIO) go through the store buffer. The only difference is in how the store buffer is flushed.

Presumably the store buffer has enough entries to satisfy a STM instruction. If the instruction (or an instruction ahead of it) faults, the relevant entries in the store buffer are purged. When the instruction retires (i.e. when it reaches the head of the reorder buffer), the stores are released for writing.

---
Tags: computer-architecture, operating-systems, cpu, memory-hardware, virtual-memory
---


title: jump to MMIO address

text:
# Question
Title: jump to MMIO address
In the ARM architecture, what happens on executing a jump instruction whose jump target address is an MMIO address (or in paging mode, a virtual address that is mapped to an MMIO address)? Would this such an instruction abort? If it succeeds and sets the EIP accordingly, what happens next: Will the CPU actually fetch the next instruction by reading MMIO address (which may be connected to a peripheral device)?

If it succeeds, reasoning about such a CPU seems problematic because reads and writes to IO addresses are potentially visible to the outside world, unlike DRAM. For example, the effect of out-of-order instruction prefetching will be visible to the outside world via IO.

# Answer
The MMIO is read into instruction cache, and the code executes as normal. The instruction cache assumes that the contents of memory underneath it do not change unless the cache is explicitly flushed.

Not only does this work, it's common practice to execute code directly from flash devices in very small embedded applications.
> 1 votes

---
Tags: computer-architecture, cpu, memory-hardware, virtual-memory, memory-access
---


# Question
Title: Simplifying SOP: implementing OR with NAND
I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such:
$a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a \*\bar b)}$
In other words, we would need two NOT gates (which are basically NAND gates), and another NAND gate.
However, I want to practise Boolean algebra simplification. Using a truth table I have formed the Sum of Products:

$f(a,b)=ab' + a'b + ab$
I have worked down a number of paths unsuccessfully. I would appreciate if someone could either show the steps of simplification, or give me some guidance on the laws to use to achieve this simplification. If there are any notation mistakes I have made, please let me know :)

# Answer
> 1 votes
Unfortunately, you've gotten as far as you can get on this problem.

(Note: I'm going to write AND, OR, NOT, and NAND as $\wedge \vee \neg \uparrow$ respectively, since the standard sum/product/overbar notation tends to end up with lots of stacked bars, and I don't like those.)

You currently have:

$$(a \wedge \neg b) \vee (\neg a \wedge b) \vee (a \wedge b)$$

At this point, you could use NANDs to build all those NOTs and ANDs and ORs…but building an OR was your goal in the beginning! Normally, going into sum-of-products form is exactly the right next step to take, but here you're stuck, because you started with a simple sum in the first place.

It turns out the simplest way to build an OR gate out of NANDs is exactly what you were doing at first.

$$\neg a = a \uparrow a$$

$$a \vee b = \neg a \uparrow \neg b$$

$$a \vee b = (a \uparrow a) \uparrow (b \uparrow b)$$

To my knowledge, nobody's ever found a way to build OR with less than three NANDs, and I very much doubt it's possible (though I wouldn't know how to prove that).

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


# Question
Title: What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?
I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$ O\left(n^{2.376}\right). $$ How much easier is it to simply determine whether the same system has any solution?

More precisely, given a system of $m$ equations and $n$ unknowns, what is the complexity of establishing whether it has any solution?

# Answer
Whether or not Coppersmith-Winograd is the "best" algorithm depends on your circumstances, of course. CW and algorithms like it are usually considered impractical due to high constant factors. Strassen's algorithm is more common in practice.

But since computational complexity is what you are interested in, CW was beaten quite recently.

As far as we know, calculating the determinant of a matrix, or eigenvalue estimation, or anything else that could be used to determine if a matrix is singular or not are at least as complex as matrix multiplication.
> 3 votes

---
Tags: algorithms, complexity-theory, linear-algebra
---


# Question
Title: Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?
This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?

# Answer
> 3 votes
First, let us note that for monotone $f$, the statement holds for some $c \> 1$ iff it holds for all $c \> 1$. Indeed, let $1 \< c\_1 \< c\_2$. If the statement holds for $c\_2$ then $f(c\_1n) \leq f(c\_2n) = O(f(n))$ due to monotonicity. In the other direction, let $M$ be an integer so that $c\_2 \geq c\_1^M$. Then induction shows that $f(c\_1^Mn) = O(f(n))$, and so $f(c\_2n) = O(f(n))$ due to monotonicity.

If $f$ is a polynomial then $f(n) = \Theta(n^A)$ and so $f(cn) = \Theta((cn)^A) = \Theta(n^A) = \Theta(f(n))$. A similar argument works when $\Omega(n^{A-o(1)}) \leq f(n) \leq O(n^{A+o(1)})$.

In the other direction, suppose that $f(n) = n^{g(n)}$, and suppose that $g(n)$ is nondecreasing. Then $f(cn) \geq c^{g(n)} f(n)$, and so $f(cn) = O(f(n))$ iff $g(n)$ is bounded. So in some sense, if $f(cn) = O(f(n))$ then $f$ must have polynomial growth.

# Answer
> 2 votes
Counterexample: $f(n) = 2^n$. Then $f(2n) = f(n)^2$.

---
Tags: complexity-theory, asymptotics, mathematical-analysis
---


# Question
Title: transformation between two formulations of the mincost flow problem
According to this slide, the following two formulations of the mincost flow problem are equivalent:

Given directed graph G = (V, E)

> * Let u denote capacities
> * Let c denote edge costs.
> * A flow of f(v,w) units on edge (v,w) contributes cost c(v,w)f(v,w) to the objective function.

...

> 2. Send x units of flow from s to t as cheaply as possible.
> 3. General version with supplies and demands
>
> * No source or sink.
>     * Each node has a value b(v).
>     * positive b(v) is a supply
>     * negative b(v) is a demand.
>     * Find flow which satisfies supplies and demands and has minimum total cost.

I can see that 2. is a special case of 3. in which only two nodes (s and t) and have non-zero demand. But I cannot figure out how to transform the more general problem 3. into problem 2.

*Can anyone help explain how to transform 3. to 2. ?*

That is, how to e.g. add edges and/or change capacity/cost, to solve problem 3. with a solver of problem 2.

# Answer
> 1 votes
I would say that 3. is a special case of 2. instead but it is a point of view.

On 3., you can create a new node "source" which has edges to every supply nodes (b(v) \> 0). These edges have cost 0 and capacity b(v).

Then you create a new node "sink" which has edges from every demand node. These edges have cost 0 and capacity -b(v).

All this replaces the b(v) values which are not needed anymore.

---
Tags: network-flow
---


# Question
Title: Is TSP a more detailed form of the "Set Inclusion" question?
# *Background*

## Set Inclusion

GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.

QUESTION: Are there any \[blue-backed cards\] with a \[face value \<= L\]?

* 2 **independent** variables: \[blue/white cards\], \[integer face values\]

**Function A**: Select a blue-backed card

* face value depends on which card you select
* each blue card *potentially* has face value \<= L
    + thus, worst-case = \[check all blue cards\]

**Function B**: Select a face value \<= L

* blue back depends on which card you select
* each card w/ face value \<= L *potentially* has blue back
    + thus, worst-case = \[check all cards w/ face value \<= L\]

Function B cannot exist. There is no way to verify that a selected card has a blue back, since don't know key info:

* How are cards marked with a blue back?

WORST-CASE: turn over all blue-backed cards (Function A)

---

## Travelling Salesman

GIVEN: complete graph, G(V,E), where all edges are positive, integer values.

DEFINITION: "config"

* {A, B, u, v} where u & v are 2 vertices, and A & B are the remaining vertices split up as evenly as possible

DEFINITION: "optimal tour of a config"

* shortest path from u to v, only going thru each vertex in A once, and
* shortest path from v to u, only going thru each vertex in B once

Assume we have a function, `f`, that returns the optimal tour for a given config, in sub-exponential time. (EDIT: if you can prove this function must take exponential time, you've shown $P\neq NP$.)

A smallest tour must be the optimal tour of one of the configs in G.
Any config could produce the smallest tour.

NOTE: Each tour is an edge-set that can form |V|/2 or |V| configs, for even or odd |V|, respectively.

---

A COMPLETE GRAPH is equivalent to: set of cards, some with blue backs, and each with a positive, integer face value.

* each **card** represents a set of edges with size = |V|
* **blue backs** mark any edge-sets that are an optimal tour for a config
* **face value** is the sum of the edge-set represented by the card

QUESTION: Are there any \[blue-backed cards\] with a \[face value \<= L\]?

* 2 **independent** variables: \[blue/white cards\], \[integer face values\]

Consider case where L = length of smallest tour.

* Only need look at blue cards (edge-sets that are an optimal tour for a config)
* Only need look at cards w/ face value = L (edge-sets with sum = L)

**Function A**: Select blue-backed card

* face value depends on which card you select
* each blue card *potentially* has face value = L
    + thus, worst-case = \[check all blue cards\]

**Function B**: Select a card with face value = L

* blue back depends on which card you select
* each card w/ face value = L *potentially* has blue back
    + thus, worst-case = \[check all cards w/ face value = L\]

Unlike "Set Inclusion", now you can verify that a selected card for Function B has a blue back, by running `f` on the selected card's configs.

However, ***controlling either variable, \[choosing blue card\] or \[choosing card w/ face value = L\], causes the other to be uncontrollable.***

WORST-CASE:

* FACE-DOWN Approach: turn over all cards with blue back (Function A)
* FACE-UP Approach: turn over all cards with face value = L (Function B)

---

# *Question*

So the final question: ***Is TSP-Decision a version of "Set Inclusion" that has enough information to define a Function B***?

If so, does this mean that the worst-case running time of TSP-Decision is lower-bounded by the smaller of the 2 domains of Functions A and B? i.e. min{number of **blue cards**, number of **cards with face value = L**} -- still only for the case where L = length of smallest tour.

EDIT: Both those lower-bounds are exponential, so if we can show that TSP-Decision is lower-bounded by them, we've shown that P != NP.

# Answer
As far as I can see, your model is that the edges of the graph are represented by cards and the edges on the optimal TSP tour are cards with blue backs. You're asking if TSP corresponds to the problem of identifying the cards with the blue backs. If that is the case, the answer is "yes".

However, there is a huge caveat. In the set inclusion problem, we can tell in constant time if the back of a card is blue: you just turn over that one card and look at it. You assume that we can do the same in TSP: in constant time, we can tell whether any single edge is in the optimal tour. This is a completely unrealistic assumption because it's impossible to tell if an edge is on the optimal tour without examining at least one edge from every vertex.

I think that what you've observed is basically that, if somebody has somehow solved a TSP instance, you can find the solution by asking them whether each individual edge is in the optimal tour. This is obviously true, but it's not very interesting.
> 2 votes

---
Tags: algorithms, complexity-theory, graphs, time-complexity, traveling-salesman
---


# Question
Title: Ambiguous grammar to equivalent unambiguous grammar
I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.

Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$

My closet try was:

Given the ambiguous CFG :
$S \to A$
$A \to aAb\mid C$
$B \to b$
$C \to abC\mid\epsilon$

But the string "$ab$" is ambiguous

# Answer
As you have observed, the only problem in the original CFG is that the string $ab$ can be generated by both $A$ and $B$.

Here is a hint. Instead of generating $ab, a^2b^2, a^3b^3,\cdots$, can you let $A$ generate $a^2b^2, a^3b^3,\cdots$ without generating $ab$?
> 0 votes

---
Tags: automata, formal-grammars
---


# Question
Title: Is the complexity of this algorithm O($\sqrt{n}$) or linear?
Let's say I have two identical jars and I want to find the height that the jars will breaks when dropped from various heights. I can drop the jars from height increments using steps on a staircase. I want to solve this problem sublinearly.

I decided to increment using square numbers (1, 4, 9, 16..etc) for a complexity of O($\sqrt{n}$), where n is the number of steps on the stairs, so I know that I have an upper and lower bound once the first jar breaks. If the jar breaks at 16, I know that the height that it breaks at is between 9 + 1 and 16. If I were to run the algorithm linearly (on the second jar) from 10 to 16, would this make my algorithm linear?

# Answer
**No**, it would not make the algorithm linear. The worst-case scenario would be $n = m^2 + 1$, where $m$ is some positive integer. In this case, you have an additional $(m+1)^2 - m^2 = 2m + 1$ many tries (since the next square after $m^2$ is $(m+1)^2$ and $n \< (m+1)^2$), which is roughly equal to $2\sqrt{n} \in \Theta(\sqrt{n})$.
> 1 votes

---
Tags: algorithms
---


title: Tailrecursive definition for a function

text:
# Question
Title: Tailrecursive definition for a function
In an exam I took we were asked to provide a tailrecursive definition of a recursive function. I failed miserably and the provided solution makes absolutely no sense to me. If anyone could explain that would be very helpful for my resit. The provided solution is the following:

---

Given are the functions $f, g, h \in \mathbb{N} \rightarrow \mathbb{Z}$ with $f.0 = 20, g.0 = 37, h.0 = 13$ and for $n\>0$:

$$ f.n = 3\*g.n-7\*h.n \\ g.n = n^2-h.(n-1) \\ h.n = f.(n-1)+g.(n-1) $$

---

For the tailrecursive version of $f$ specify

$$ \psi \in \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{N} \rightarrow \mathbb{Z} \\ \psi .a.b.c.d.n = a * g.n + b * h.n + c * (n + 1)^2 + d $$

Such that $f.n = \psi .3.(-7).0.0.n$

Then

$$ \psi .a.b.c.d.0 = 37 * a + 13\*b+c+d $$

and

$$ \psi .a.b.c.d.(n+1)\\ = \text{\\{ spec \\}}\\ a\*((n+1)^2+h.n)+b\*(4\*g.n-7\*h.n)+c\*((n+1)^2+2\*n+3+d)\\ = \text{\\{ arithmetic \\}}\\ 4\*b\*g.n+(a-7\*b)\*h.n+(a+c)\*(n+1)^2+d+c\*(2\*n+3)\\ = \text{\\{ Construction Hypothesis \\}}\\ \psi .(4\*b).(a-7\*b).(a+c).(d+c\*(2\*n+3)).n $$

---

The main problem I am having is how they arrived at the specification, since the actual calculation I can follow. If anyone has any insights as to how the specification was obtained I think I would be able to grasp the answer better.

Thank you in advance.

# Answer
I cannot find a way to make the specification coincide with what your solutions say, but I can get very close to that (personally, I think that your solutions contain a small mistake).

The first part should be $a\*((n+1)^2-h.n)$ (and not $a\*((n+1)^2+h.n)$), as per the definition of $g$ in terms of $h$.

The second part, $b\*(4\*g.n-7\*h.n)$, comes from the definitions of $h$ and $f$: $b\*h.(n+1)=b\*(f.n+g.n)=b\*((3\*g.n-7\*h.n)+g.n)=b\*(4\*g.n-7\*h.n)$.

Finally, $c\*((n+1)^2+2\*n+3$ is just a (uselessly convoluted) way of writing $c\*(n+2)^2$.
> 0 votes

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


title: Intersection of two incomplete DFAs

text:
# Question
Title: Intersection of two incomplete DFAs
Let assume that I have the following two automata A1 and A2 :

I have to do the **intersection** of the two, so I did this :

My question is related to the "∅". If I have two incomplete automata without dead states, and given a specific state, one automaton has a transition for one symbol but the second doesn't have it, what should I do ? For example I am in the state 13 in the transition table and I read "b", should I rather put ∅ or 4 and make it non final ?

# Answer
> 1 votes
To answer the question, there are two different manners to solve this.

1. By adding a dead state whenever you have an incomplete automata. By doing so, you will no longer have to worry about what to do if one automata has a transition from a specific state but not the other.
2. You can still do the intersection of the two without adding dead states.

In this example, if you are focusing on the state 1 and 3 with the symbol 'b' :
\- From A1, you have no transition : δ(1,b) = ∅
\- From A2, you have a transition : δ(3,b) = 4

Since one has a transition, but not the other, then the resulting automata will have the transition : δ(13,b) = ∅. Therefore, it is indeed acceptable to put ∅.

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


# Question
Title: Lambda term satisfying two equations using Bohm Trees
Hi I'm trying to solve this exercise but I can't find any material online, it's not an homework I actually have sort of a solution (it looks incomplete though), but from that I can't really understand much about how to tackle the problem. Anyway we're asked to find a term $\Delta$ such that: $$ \left\\{\begin{matrix} \Delta(\lambda x y. x (y(\lambda u.yuy)x)x)=y\_1 \\ \Delta(\lambda xy.x(y(\lambda u.yu(\lambda abc.cab))x)x) = y\_2 \end{matrix}\right.$$

I looked at a similar exercise where the idea was to define $\Delta$ to be an abstraction of the type $\lambda x. x R\_3$ where $R\_3$ is the ROTATION operation on Bohm Trees (takes the leftmost child of a tree with k+1 subtrees and makes it the new root).

Could someone please explain me how to solve these type of problems? thanks

# Answer
> 2 votes
This task can be solved very well by observation and inserting simple functions.

First, $\Delta$ should obviously be a function applying its argument to at least two terms (because it's $\lambda x y.$). So let's set $\Delta = \lambda f.fXY$, which gives $$X(Y(\lambda u.YuY)X)X=y\_1 \\ X(Y(\lambda u.Yu(\lambda abc.cab))X)X = y\_2$$ Now we see that $Y$ is mostly applied to other terms that seem complex enough to solve this task for themselves, so why not just set $Y=I(=\lambda t.t)$?
This leads us to $$X(XI)X=y\_1 \\ X(X(\lambda abc.cab))X = y\_2$$ $X$ is now an abstraction of at least two variables, but we see that the second one (it's always $X$ in the first application) can probably be ignored. Setting $X=\lambda p q.Mp$: $$M(\lambda q.MI)=y\_1 \\ M(\lambda q.M(\lambda abc.cab)) = y\_2$$ The same ways we did with $\Delta$, we see that M takes an argument with at most three abstractions, so we make $M=\lambda f.(f P Q R)$. Doing several beta reductions, this yields $$PQRQR=y\_1 \\ RPQQR = y\_2$$ with the obvious solutions $P=\lambda a b c d.y\_1$ and $R=\lambda a b c d.y\_2$ and the free parameter $Q$.
Now finally, we can insert these terms back into $M$, $X$ and $\Delta$ to yield the solution $$\Delta=\lambda f.f(\lambda p q.p(\lambda a b c d.y\_1)I(\lambda a b c d.y\_2))I$$ (setting $Q=I$ for brevity's sake).
There could very well be a smaller solution, but I think the derivation process is the simplest you can get with this one.

---
Tags: lambda-calculus
---


# Question
Title: Binary Floating Point Range/Precision for 4-bit Mantissa and 4-bit Exponent
I'm trying to understand binary floating point and using just a 4-bit mantissa and a 4-bit exponent (both 2s compliment) to keep things simple.

As far as I can tell, the largest denary number I can represent is 112: 0111 0111

So why do I have trouble representing denary 11 (eleven) in this system? I get that the largest (positive) mantissa is 7 in denary (0111). So I'm inferring that I can't represent consecutive positive integers between 0 and the maximum value of 112.

Is that correct? If so, can someone help me to see why please? Which numbers in this range can I represent?

# Answer
> 2 votes
Yes, that is correct. Your mantissa has only three magnitude bits, so you can only represent numbers from -8 to 7, multiplied of course by any power of 2 from $2^{-8}$ to $2^7$. 11 is impossible to represent, because any positive exponent gets you multiples of 2, any negative exponent gets you numbers less or equal to $7\*2^{-1}=3.5$, and exponent 0 is just numbers from -8 to 7.

---
Tags: floating-point, binary
---


# Question
Title: Algorithms for elementary operations using other elementary operators
The question asks to provide an algorithm to compute

$(i)$ The product of $n$-bit numbers using reciprocation operation and addition operation but not using multiplication and squaring.

$(ii)$ The square of a polynomial of degree $n−1$ using only reciprocation and addition operation but not using multiplication and squaring.

$(iii)$ The product of two $n − 1$ degree polynomials using only squaring and addition operations but not using multiplication and reciprocation operations

All the operations stated above are on $n$-bit integers.

**My try**: The question asks to express some operator in terms of other elementary operators , so for eg. for (i) I tried writing $(\frac{1}{A} + \frac{1}{B})^{-1} = \frac{AB}{A+B}$, but to get $AB$, I still have to multiply LHS by $A + B$. I think I can do $(ii)$ if I do $(i)$ as a polynomial is similar to a n-bit integer if you consider the bits as $(a\_ix^i)$. I don't have an idea for $(iii)$ yet.

# Answer
> 1 votes
Throughout this answer, when we say we will be using some operations, it implies that no other operations is allowed. We also assume 1 is available as an operand.

The above clarification is considered as an improvement of original statement of problems. There will be further modification/clarification of the original problems, which have to be made because of the ambiguity of the original problems.

---

Here is the answer to part (i)

> Part (i). The product of two non-zero numbers using only reciprocation operation and subtraction operation.

Please note I have replaced by addition by subtraction; otherwise, it is impossible. Also I removed the specification of $n$-bits, which seems distracting and harmful; otherwise, $\dfrac13$ is problematic. I have also added the condition that the numbers are non-zero. Otherwise, we have to add an operation that checks whether a number is non-zero and acts accordingly. Also 1 have to be available. Otherwise, we cannot produce 1, which is needed in the final operation.

Let the two non-zero numbers are $A, B$.

1. we get addition by $X+Y=X-((Y-Y)-Y)$.
2. we get 4=1+1+1+1.
3. we get $X\to \dfrac {X^2}4$ by $\dfrac {X^2}4=X+\dfrac1{\dfrac1{X-4}-\dfrac1X}$.
4. We get multiplication by $AB=\dfrac{(A+B)^2}4-\dfrac{(A-B)^2}4$.

This answer at mathoverflow uses division by 2 or multiplication by $\dfrac12$ without explanation, which can be considered as a minor flaw. In fact, we can do division by 2 as $\dfrac A2=\dfrac1{\dfrac1A+\dfrac1A}$.

---

> Part (ii). The square of a polynomial with given coefficients using only reciprocation and subtract operation.

Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, this part can be done easily as a consequence of part (i).

---

> Part (iii). The product of polynomials with given coefficients using only squaring and subtraction operations and division by 2.

We get addition by $X+Y=X-((Y-Y)-Y)$. We get multiplication by $XY=\dfrac{(X+Y)^2-X^2-Y^2}2$. Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, we can compute the product of two polynomials.

Note that division by 2 is needed. Otherwise, it can be proven that it is not possible to do multiplication although we have $2XY=(X+Y)^2-X^2-Y^2$.

---
Tags: algorithms, complexity-theory, arithmetic
---


# Question
Title: How to calculate a direct mapped chace capacity with tag and valid bits?
I've seen some very useful posts about this, but none took into consideration both the tag and valid bits. This is a question I took from a notebook in my computer engineering course.

> Consider a machine with a direct mapped cache, with 1 Byte blocks and 7 bits for the tag. This machine has a RAM with 2 KB capacity. Calculate the cache's total capcity, counting the tag bits and valid bits.

Breaking a cache into parts, I have the **tag bits**, **set index** and **block offset**.

I already know I have 7 tag bits, but then I'm really not sure how to calculate the rest, because in this type of question we are usually given the words per block. I think the offset is 3, because 2^3 (8 bit blocks).

I feel like the question itself doesn't give enough, shouldn't it be stated how the system address is (byte/word addressable)? Also, is the RAM capacity relevant to the question at hand?

# Answer
> 0 votes
Unless specified otherwise, addresses are always byte adresses (and with a cache with 1B/block, any other choice would not make sense)

Ram size is relevant as it indicates addresse width.

Cache blocs are 1 byte -\> offset=0b (offset indicates byte position in block and only 1 possible position).

RAM is 2kB (2^11) -\> address is 11 bits

Adress width=Tag with+Index width+Offset width

Tag=7b, Address=11b, Offset=0b -\> index=4b

Cache is direct Mapped -\> Cache size for data=number of blocks * block size = 2^(index size)\*(Block size)

-\> Cache Size (data) = 2^4\*1B=16B

Block associated with Tag(7b) + 1 valid bit -\> 1 extra B for control per block

Total cache size = 16 block each with 1B data and 1B control -\> 32B

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


# Question
Title: Shortest path in graph by flipping binary colored nodes to one color
Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the minimum path such that all nodes are converted to black (or white, since it is equivalent)?

# Answer
This problem is $NP$-complete, there is a quite simple reduction from Hamiltonian Path. Therefore, there's (likely) no way to solve this problem efficiently in general, so the solution method will need to be tailored to the inputs you are interested in solving (brute force for small instances, heuristic methods for large instances, specialized methods for instances with special structure,...).
> 1 votes

---
Tags: shortest-path, graph-traversal, colorings
---