# Question
Title: An efficient way to get the dual graph from a triangulation
An answer to a previous question I asked advised me to find the dual graph of a triangulation. I'm given the graph in the following form:

How can I get the dual graph from a list of edges given this way?

# Answer
> 1 votes
The way the triangulation is given to you encapsulates this information, since along with each edge you are given the triangles it is part of. This allows you to reconstruct the edges of the dual graph (and from them, the vertices).

You can also recover this information, at higher cost, if the triangulation is given to you as a graph. In polynomial time you can, for example, find all triangles (the vertices of the dual graph) and all pairs of triangles intersecting at an edge (the edges of the dual graph). You can do it naively in $O(n^4)$, though I'm sure this can be brought down significantly, perhaps even all the way to $\tilde{O}(n)$.

---
Tags: algorithms, graphs
---


title: What is a ridge - Hill climbing

text:
# Question
Title: What is a ridge - Hill climbing
I do not understand what is a ridge for hill climbing. The definition I found is a place where all points appear like a maximum, but how is that different than a plateau?

# Answer
> 3 votes
The same answer you'd get on The Great Outdoors Stack Exchange: it's one of these.

Photo: ridge from Mount OtenSho to Mount Tsubakuro, Japan. By Alpsdrake; public domain; from Wikipedia

On a plateau, your value doesn't change much if you move in *any* direction. On a ridge, your value doesn't change much if you move in one direction, but it falls a lot if you move in the other directions.

---
Tags: algorithms, optimization, terminology
---


# Question
Title: Space efficient data structure for subsets of [1:n]
Let $S= \\{1,2,3...,n\\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search($x$) can be done in $O(1)$ time, where $x\in A$. Space used by data structure should be $O(n \log^{\*}n)$ or $O(n)$ bits. Model of computation is RAM.

# Answer
> 2 votes
Bit vectors fulfill all your requirements.

# Answer
> 0 votes
Bit vectors, as mentioned by Raphael, fulfill all the requirements and it is a very simple and fast option. But there is an alternative called Minimal Perfect Hashing, which could be represented succinctly requiring few bits in practice.

A bit vector $B$ can also be compressed in order to achieve $$O(nH\_0(B)) \text{ bits}$$ of space. Depending on the distribution of 0's and 1's, this could be $o(n)$ bits.

---
Tags: data-structures, sets, space-analysis
---


# Question
Title: greedy algorithms - minimizing total payment
The question:

I want to buy $n$ books. In the book store there's a big sale according to which, if you buy three books, then the cheapest book in any triplet costs only 20% of its full price. Let $c\_1, c\_2, …, c\_n$ be the full price of the books you want to buy.

Suggest an algorithm for minimizing your total payment. Prove its optimality and analyze its time complexity.

My algorithm:

1. sort the prices of the books from big to small, such that $c\_1 \ge c\_2 \ge ... \ge c\_n $ (change the locations of the books).
2. each book $c\_i$ if $i \\% 3 = 0 $ then change its price to $c\_i=0.2\cdot c\_i$
3. return the sum of all books $\sum\_{i=1}^nc\_i$

Now, I'm having trouble proving that this is the optimal solution. I want to prove that if $i\\%3=0$ for $c\_i$, then I have a discount on this book.

I'm having a hard time formalizing the Greedy choice property. Given an optimal solution, what happens if $c\_i$ such that $i\\%3=0$ is not in the optimal solution? (doesn't have a discount)?

# Answer
> 2 votes
This answer is a hint.

Assume an optimal solution exists. Order its choices so that they agree with your algorithm's choices for as long as possible; the order after this is unimportant. If all of them agree, then your algo picked an optimal solution, so you're done! If not, then at look at the first group of 3 where they disagreed. Even though you don't know exactly what an optimal solution is, you know that one exists, and you can make *changes* to it -- e.g. swapping some books in its ordering -- to produce a new solution.

Can you think of a way to change it in such a way that (a) it now agrees with your algo for 1 more group of 3 *and* (b) its score didn't get worse? If so, then clearly you could repeat this step until... What happens?

# Answer
> 0 votes
For every price-reduced item, you must have purchased two items at the same or higher price. Therefore, you cannot get one of the two highest priced items reduced, you cannot get two of the five highest priced items reduced, you cannot get 100 of the 299 highest priced items at a reduced price.

$c\_1$ and $c\_2$ cannot be the first reduced item. $c\_1$ to $c\_5$ cannot be the second reduced item. $c\_1$ to $x\_{299}$ cannot be the 100th reduced item. So using the groups $(c\_1, c\_2, c\_3)$, $(c\_4, c\_5, c\_6)$ etc. gives the optimal result.

---
Tags: algorithms, graphs, greedy-algorithms, proof-assistants
---


title: Maximum weighted disjoint set union

text:
# Question
Title: Maximum weighted disjoint set union
I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this problem the *Maximum Weighted Disjoint Set Union*, which is obviously not the name by which the problem is known (if it is known).

In this post, the problem (stated slightly differently) is related to *Weighted Independent Set*. However, I will show below that this problem is simpler than independent set and, even if it possesses the same time complexity, it may allow for a solution with smaller run-time requirements.

The problem is as follows. We are given a set $U$ of elements (the universe, e.g., $U=\\{1,2,3,4,5\\}$). We're also given a set $S=\\{S\_1,S\_2,\ldots,S\_n\\}$, where $\forall\_iS\_i\subseteq U$. Furthermore, each set $S\_i$ is assigned a weight $w\_i$. The task is to find a set $S'\subseteq S$, such that the sets in $S'$ are disjoint and the sum of their weights is maximal.

One might think that this problem corresponds to weighted independent set. Namely, the vertices in the graph correspond to the sets in $S$ and there is an edge between two vertices if the corresponding sets have non-empty intersection.

Note, however, that important information is lost in the process of translation. For an example of such a loss, suppose $S\_1=\\{1,2\\}$ with $w\_1=1$, $S\_2=\\{3,4\\}$ with $w\_2=1$, $S\_3=\\{1,2,3\\}$ with $w\_3=3$. Note that we do not need to consider a cover $S'$ that contains both $S\_1$ and $S\_2$. This is because $S\_3\subseteq S\_1\cup S\_2$ and $w\_3\>w\_1+w\_2$. The information needed to perform this cut-off is not present in the corresponding instance of the weighted independent set problem.

If I am correct in this reasoning, then this problem deserves attention and I am wondering whether it received any. In addition, I am hoping to get an off-the-shelf implementation in C++ which I can use (this problem happens to be a sub-problem of the research problem in a different field that I am trying to solve).

# Answer
This is a weighted version of Set Packing, which was one of the 21 classic problems proven NP-hard by Richard Karp:

> Richard M. Karp (1972). "Reducibility Among Combinatorial Problems" (PDF). In R. E. Miller and J. W. Thatcher (editors). *Complexity of Computer Computations*. New York: Plenum. pp. 85–103.

As the unweighted version is already NP-hard, your weighted version is too, so it's unlikely that any algorithm will solve every instance of it in polynomial time.
> 2 votes

---
Tags: algorithms, set-cover
---


# Question
Title: Viterbi Algorithm: initial state with ONE probability
The Viterbi Algorithm can be used to calculate the most likely path, based on observations in a Hidden Markov Model.

Using the same notations as Wikipedia, "each element `T1[i, j]` of `T1` stores the probability of the most likely path so far `X = (x[1] , x[2] , ... , x[j])` with `x[j] = s[i]` that generates `Y = (y[1] , y[2] , ... , y[j])`.

Now suppose, that the initial distribution $\pi$ is such that for one state the probability is `1` (let's call it state `K`), and for all other states it is `0`. Also, let's say that in the emission matrix `B` all elements are strongly between 0 and 1 (i.e. `0 < B[i, j] < 1` for all `i` and `j`.

In this way `0 < T[K,1] < 1` and for all other states `T[i,1] = 1`.

**Problem**: For me, the part `T[K,1] < 1` feels intuitively wrong. How can it be, that the first state is `K`, with probability `1`, still the most likely path contains it with probability less than `1`?

I understand that the reason must be something like: "There are more different paths. One where the first state is `K`, and the first observation is `y1`. One, where the first state is `K`, and the observation is `y2`. Etc.".

However, it is also true, that "no matter what the observation is, the first state is `K` with probability `1`".

**Question**: What is the explanation for this (seeming) contradiction? (The best would be if it is "intuitive".)

# Answer
Wikipedia is wrong. That's not what $T\_1$ stores. Rather, $T\_1$ stores the likelihood of a path... namely, the likelihood of the path that has the highest likelihood. What's the likelihood of a path $\hat{X}$? It is the probability of generating the output sequence $Y$ given that you followed the path $\hat{X}$, i.e., the probability $P(Y | \hat{X})$. Note that this is *not* the same as $P(\hat{X} | Y)$.

The probability $P(Y | \hat{X})$ might be less than 1, even if we're certain that $\hat{X}$ was the path that was followed. In particular, you can have $P(Y | \hat{X}) \< 1$ even if $P(\hat{X}) = 1$. This can happen, for example, if there are multiple possible output sequences that could arise when following the path $\hat{X}$.

As usual, Wikipedia is not a primary source. Don't use Wikipedia as your only source for learning new material. It is helpful as a summary, but when you find something in Wikipedia that is confusing or that doesn't make sense, go to a primary source -- e.g., a highly reputed textbook. Wikipedia does have errors, poor writing, gaps in its explanation, and so on, so it is not a substitute for a high-quality primary source.
> 1 votes

---
Tags: probability-theory, hidden-markov-models
---


# Question
Title: Is it possible to evaluate $n!$ in $O(1)$?
I'm working on a formula that'll evaluate the partial sum of the harmonic series from $t\_1$ to $t\_n$. The problem is that I'm almost certain the final formula will include factorials. But if the formula has a factorial, then it's runtime complexity would be at least $O(n)$. And this would defeat the entire point of having a general formula, because I can just iterate over the first $n$ terms and add those in $O(n)$. Utilizing the gamma function wouldn't help either since it'll require $n$ "integration by parts" steps. So is there any way to evaluate factorials faster than $O(n)$?

# Answer
> 1 votes
There are two scenarios:

1. Your integers are of fixed size. Then, you absolutely can compute $n!$ in $O(1)$. In fact, every algorithm that computes $n!$ satisfies this. Why? There are finitely many inputs to your algorithm. If it takes $f(n)$ steps to compute $n!$, and there are finitely many $n$ values, then there must be some maximum for $f$. That's the upper bound on your runtime.

Is this answer useful? No, since it doesn't give you any hints as for how to speed up an algorithm. But, it hints that maybe Big-O notation isn't an accurate measure of time for your particular application.
2. Your integers are of unbounded. Then there can't be an $O(1)$ way to compute it.

How do we know? Well, suppose you have an algorithm that takes at most $k$ steps for any input. Give it an input with $k+1$ bits. It can't possibly examine each bit, since looking up a bit requires a step. So your algorithm only looks at $k$ bits of the $k+1$-length function. But then, if you give the same input with the ignored bit flipped, it will give the same answer! This is impossible, since factorial is an injective function. Flipping a bit should always give us a different answer, so we must examine each bit, so we can't compute it in $O(n)$.

---
Tags: time-complexity, mathematical-programming
---


# Question
Title: Minimum expected cost through an unconventional graph with probabilities at which edges are selected
I'm having trouble identifying the approach to minimize the cost of reaching a certain state in an optimization problem. I've modeled it here as a game.

**Problem Structure**
You buy heroes and send them into a dungeon consisting of rooms containing each two challenges (random number check with a given threshold per room) that each hero can choose between (one hero completing a challenge does not allow another to skip it). The goal is to have any hero survive to the final room, and the secondary goal is to minimize the cost for doing so.

The first challenge costs a small fixed amount and success leads that hero to the next room (other heroes must complete their own challenges). The second challenge costs a medium fixed amount and if the challenge is successful, he rolls a fair 5-sided die. Anything below a 5 will move the hero to the next room. A 5 will move the hero 2 rooms ahead.

Failure on any challenge leads to the hero's death unless "divine protection" has been bought for this attempt at the chosen challenge (can only be used in the first two rooms). You can also buy a "charms" for your hero that will improve chances of success for a single attempt by various factors (1.5x, 2x, etc).

**Example:**

```
All heroes cost 300g.
The 1.5x charm costs 650g.
The 2x charm costs 1100g.
The 2.5x charm costs 2100g (but this can't be used at the same time as protection).
Divine protection for room 1 costs 2000g per challenge.
Divine protection for room 2 costs 4500g per challenge.
In the first room, challenge 1 costs 120g and has 40.5% success before charms.
In the first room, challenge 2 costs 210g (has same success rates but also 20% of successes move 2 rooms).
In the second room, challenge 1 costs 140g and has 13.5% success.
In the second room, challenge 2 costs 230g.
In the third room, challenge 1 costs 160g and has 10.% success.
In the third room, challenge 2 costs 250g.
In the forth room, challenge 1 costs 180g and has 4.1% success.
In the forth room, challenge 2 costs 270g.
In the fifth room, challenge 1 costs 300g and has 2.7% success.
In the fifth room, challenge 2 costs 390g.
The sixth room is the final room ("you win the game").

```

All `g` values can change due to *market fluctuations*, but I'm looking to solve the optimization problem for any snapshot in time (where we can say the costs are 'fixed' while we're calculating, but we'll have to plug the numbers in again the next time we calculate).

**Question**

Without the 20% chance on successes to skip a room, it can be modeled as a dynamic programming problem, but I haven't been able to figure out an approach to make that work.
What kind of approach would be appropriate for minimizing the expected cost of putting a hero in a given room?

# Answer
> 1 votes
Once you know the expected success rate for room 3 (given a certain budget), you should be able to work out the expected success rate for room 2 (given a certain budget).

In other words, let $A\[r,b\]$ denote the probability of success when starting at room $r$ and starting with budget $b$, using the optimal strategy. Given $A\[r+1,\cdot\]$, you can compute $A\[r,\cdot\]$ via a simple recurrence (consider all possible things you could buy, and the probability of beating room $r$, and how much that reduces your budget when starting at room $r+1$). This immediately leads to a dynamic programming algorithm for your problem.

If charms persist from one room to the next, use $A\[r,b,c\]$ where $c$ is the set of charms you already have when you start at room $r$.

---
Tags: optimization
---


# Question
Title: Given an unordered array and a value v, what are the two numbers that added are equals to v
The array max size is 10^5 I can only imagine on trying every possibility, on a O(n^2) solution, there is a better way for solving that? Thanks a lot!

# Answer
I've found the better solution on this link https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/
> -1 votes

---
Tags: arrays
---


title: LTL Formula Until with same atoms (aUa)

text:
# Question
Title: LTL Formula Until with same atoms (aUa)
I am trying to solve some past papers in preparations for my next exam and I've stumbled across the following exercise:

While I managed to solve most parts of the exercise, I am still unsure about the formula ((b)U(b)). I am unsure which node I should start checking from and on the general definition of U.

As far as I understood a state matches a general formula aUb if it satisfies the proposition b. So in this example would the states s1, s2 and s4 all satisfy ((b)U(b))? Am I approaching this the wrong way?

Thanks a lot

# Answer
First of all LTL is defined over traces. In verification, we typically say that a state satisfies some LTL formula if all of the traces starting in the state satisfy the formula. I henceforth assume that this is what is meant in the question and this definition has been given in your course.

The Until operator is defined over a word as follows:

$$ w \models \psi \mathcal{U} \phi \quad \text{ iff } \quad \exists i \in \mathbb{N}: \forall j\leq i. w^i \models \psi \wedge m^j \models \phi $$

In this equation, $w^i$ represents the word starting at position $i$, where all letters before position $i$ have been removed. Applied to the concretization $\psi = b$ and $\phi = b$, we have:

$$ w \models b \mathcal{U} b \quad \text{ iff } \quad \exists i \in \mathbb{N}: \forall j\leq i. w^i \models n \wedge m^j \models b $$

Note that without loss of generality, we can assume that the $i$ searched for in the definition is always 0, because for $j=0$, we need to have $w^0 \models b$ for a word $w$ to be a model of $b \mathcal{U} b$. But then we can also choose $i=0$. Then the definition simplifies to:

$$ w \models b \mathcal{U} b \quad \text{ iff } \quad m^0 \models b $$

Hence, you are searching for all states for which all outgoing paths start with a $b$ state, which is equivalent to saying that you search for all states in which $b$ hold.
> 0 votes

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


# Question
Title: Are machine codes always numerical? (WIkipedia is Ambiguous)
Wikipedia article on machine code and more in general Wikipedia's take on machine code seems pretty amiguous sometimes.
Often it makes me wonder if there's more, or it is just bad generalization.

Look at this:

> Machine code or machine language is ......Numerical machine code (i.e., not assembly code) may be regarded as the lowest-level representation of a compiled or assembled computer program or as a primitive and hardware-dependent programming language.

It seems to treat numerical machine codes as a subset of machine codes.
Does this imply assembly has to be considered a machine code too?
Or...Is it just implying that exists some non-numerical machine code?
Maybe it's just bad-written, or maybe it's me.

Again, article on object code:

> In a general sense an object code is a sequence of statements or instructions in a computer language,\[2\] usually a machine code language (i.e., binary) or.....

"i.e, binary" Does this mean that there are non-binary machine codes?

I'm a little bit confused.

# Answer
**Yes and no and, really, it doesn't matter.**

All data in computers, including programs, is stored in devices that have two possible states – e.g., memory cells that can be at a high voltage or low voltage or areas of a disc that are magnetized north–south or south–north. These two-state systems are naturally interpreted as the binary digits 0 and 1. Any sequence of 0s and 1s can naturally be interpreted as a number written in binary.

Machine code is data that is stored on computers. Therefore, it is stored in a sequence of two-state cells, which can be viewed as a sequence of binary digits, which can be viewed as a binary number (or a sequence of binary numbers if you divide it into blocks). Does that mean it *is* a binary number? Really, that's a question of philosophy. The computer doesn't say "That pattern of 1s and 0s represents the number 3476247, which means I should do X": it just says "That pattern of 1s and 0s means I should do X." To the computer, it's just an instruction. But if you and I want to talk about that instruction, it's probably easiest to first see it as a number and then figure out what instruction it stands for.
> 4 votes

# Answer
Machine code isn't necessarily numerical, but it will eventually have to be *represented* by some binary number, as all things that a modern computer can store or reason with must be stored as something representing a binary number (e.g. electrical pulses, small pits and bumps, etc.) .

Assembly code is not the same a machine code (on most machines), since this needs to undergo the process of assembly to be transformed into machine code. Assembly code is not very different from machine code, but it is more easier for humans to interpret and edit.

Also note that the word 'binary' is often used to denote a file/data on a computer that has no direct human-readable interpretation. As such, only the computer reads it, so we regard the data as 'binary', since that is the way the computer interprets all data.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Vertex Disjoint Directed Max Steiner Tree Packing
I am not getting enough literature on **Vertex Disjoint/Vertex Capacited Min Steiner Tree Packing** Most of the few papers that I have found refers to one reference which is *not accessible over internet*.

> Korte, B., H. J. Pr6mel and A. Steger, "Steiner Trees in VLSI-layout", in Paths, Flows, and VLSI-Layout, Korte, B., L. Lovisz, H. J. Prtimel and A. Schrijver (Eds.), Springer-Verlag (1990).

One early works\[1\] claim the following is known to be NP-Complete

> Given an undirected graph $G=(V,E)$ and a Family Terminal sets $\psi = {N\_{i}\subseteq V: i=1...K}$ where $N\_{i}\cap N\_{j} = \phi$ edge cost $c(e) \geq 0 \\;\forall e\in E$, vertex cost $n(v) \geq 0 \\;\forall v\in V$ find a **minimum-cost** Family $\Gamma = \\{T\_{N\_{i}}\\}$ where each $T\_{N\_{i}}$ corresponds to Steiner tree for terminal vertices $N\_{i} = (V\_{N\_{i}},E\_{N\_{i}})$ and $V\_{N\_{i}} \cap V\_{N\_{j}} = \phi \\;\forall i \neq j$, where cost of the Tree is determined by $C(T\_{N\_{i}}) = \sum\_{e\in E\_{N\_{i}}} c(e) + \sum\_{v\in V\_{N\_{i}}} n(v)$

But this does not imply any constraint on $\vert N\_{i} \vert$ which makes me believe that it is NP-complete for $\vert N\_{i} \vert = 2$ as well. Am I correct ? or the authors just missed to put the limits ?

Also does not consider negative edge weights and directed graphs.

In that paper authors show for **series parallel graph** it can be solved in polynomial time $O(n^{5})$ worst case complexity. But series parallel graph is $k$ connected for a fixed $m$ and often $m=2$. Probabbly that's why it can be solved in P time.

Another early work \[2\]

> we prove that PVCD with unit capacitiesis NP-hard even in the simplest non-trivial case where there are only three terminals (one root r and two other terminals) and we are asked to find only 2 vertex-disjoint Steiner trees. The problem becomes trivially easy if any of these two conditions is tighter, i.e., if the number of terminals is reduced to 2 or the number of Steiner trees that we have to find is reduced to 1.

* Packing Vertex Capacitated Directed Steiner Trees (PVCD)

Which actually implies $\vert N\_{i} \vert = 2$ it is trivially easy to solve (i.e. **Not** NP-Complete).

Here does these two papers conflict ? or in undirected case $\vert N\_{i} \vert$ can be arbitrary ?

\[1\] Chopra, Sunil, and Kalyan T. Talluri. "Minimum-Cost Node-Disjoint Steiner Trees in Series-Parallel Networks." VLSI Design 4.1 (1996): 53-57.

\[2\] Cheriyan, Joseph, and Mohammad R. Salavatipour. "Hardness and approximation results for packing Steiner trees." Algorithmica 45.1 (2006): 21-43.

# Answer
> But this does not imply any constraint on $|N\_i|$ which makes me believe that it is NP-complete for $|N\_i|=2$ as well. Am I correct?

No, not necessarily. Just because a problem is NP-complete, doesn't mean it will remain NP-complete when you add some restriction to the set of instances (inputs).

Example: Graph coloring is NP-complete. 2-colorability is not. In other words, the following problem is NP-complete:

* Given an undirected graph $G$ and an integer $N$, determine whether the graph $G$ can be colored using $N$ colors.

However, it is not NP-complete for the special case $N=2$.
> 1 votes

---
Tags: graphs, np-complete
---


title: What does an "I/O Task" mean?

text:
# Question
Title: What does an "I/O Task" mean?
While reading an article, I noticed the use of term 'I/O Task':

> Indeed, suppose the currently running process is performing an I/O task (which, by definition, does not need the CPU to be accomplished). Then, the OS may interrupt that process and give the control to one of the other in-main-memory programs that are ready to execute (i.e. process context switching).

However, AFAIK a *unit of execution* (task definition) is either a thread or a process.

So what does an "I/O Task" mean?

# Answer
> 2 votes
Reading / writing from disk.

Reading / waiting for keyboard / mouse input.

Reading / waiting for network data.

Printing a page.

Basically, as the text says, an I/O task is anything which the CPU can't perform on its own, and has to rely on other components. Usually this involves waiting a long time, compared to the CPU speed, so it's better to switch to another task while waiting.

In this way, even if the browser is waiting for the server to respond, the other running tasks can move on (unless they also need to wait for I/O, of course).

---
Tags: operating-systems, multi-tasking
---


# Question
Title: Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?
I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a\_1, \ldots, a\_n$, and for each $1\leq i\leq n$ I would like to compute $|\lbrace j|j\>i\wedge a\_j \> a\_i\rbrace|$.

My idea: Implement an AVL tree, put elements from this sequence to this AVL tree from the last one to the first one. Before putting each element obtain the amount of larger elements the tree already contains. I can implement an AVL tree that would allow such operations.

But alas, I do have to implement such an AVL tree, since unfortunately the standard C++ `std::set` doesn't allow obtaining the distance between two iterators in logarithmic time.

Now I need this to solve a task from one of the former exams on algorithms and data structures. These exams usually contain two tasks, a "simpler" one and a "harder" one. And this is the "simpler" one. Now I doubt that a "simpler" task would require implementing an AVL tree. A "harder" task might; but a "simpler" one, doubtfully. Therefore, I would say, there should be a less laborious way to solve this task.

Is there any simpler way to compute what I need to compute?

# Answer
You can use any balanced binary search tree data structure (doesn't have to be AVL tree). Some such data structures are easier to implement (maybe a AA tree, left-leaning red-black tree, or splay tree?). If you don't care about worst-case running time, it doesn't need to be balanced. One pragmatic solution might be to use skip lists.

Are you sure the exam required students to *implement* their solution? In my experience, exams in the algorithms and data structure courses I'm familiar with rarely require implementing the solution -- it is enough to describe the solution clearly. A solution based on augmenting an AVL tree can be described in a fairly simple way: you say "take a AVL tree, and modify it in such-and-such a way", and that doesn't require re-describing all the details of how AVL trees work. Only you know what the typical expectations are for the kind of exam you are looking at.
> 1 votes

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


# Question
Title: Improving copy cost of a bit array by using big-endian Patricia Trees (or similar)
I have an algorithm that on each iteration generates a copy of an object containing a bit array and modifies it (the modification is limited to just 1 element per copy)

While doing the time analysis I cannot neglect the copy cost as this bit array is encoding information about the input set, so for a very large number of elements I have to account for it..

I has been said that effective data structures exists, like big-endian Patricia trees, that can achieve a $O(log(n))$ when copying an instance, and I confirmed there are implementations using them like Data.IntSet from haskell that provides a very good TC for certain operations that I can use to refactor this part of the algorithm ($O(min(n,W))$ W=word size)

I have seen another post in Stack Exchange explaining that is possible to achieve a similar copy cost with AVL persitent trees.

I'm looking for confirmation about this or any other specialized structure that can achieve the reported time complexity for copy.

# Answer
> 2 votes
Yes, you can use standard techniques for persistent data structures to make a version of Patricia trees that has the properties you want. See also What classes of data structures can be made persistent? and on this site.

---
Tags: data-structures, time-complexity
---


# Question
Title: Relating indexes for parameters and variables
I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help.

I have the following binary variable

* x(r,m) = 1 if referee r is assigned match m

and the following parameters:

* time(m,t) = 1 if match m takes place at time t
* avail(r,t) = 1 if referee cannot officiate a game at time t

I want to define my x variable to 0, when avail(r,t)=1, but is this even possible?

# Answer
Yes.

This appears to be an instance of the assignment problem. In the assignment problem, you construct a bipartite graph. The vertices on the left represent referees. The vertices on the right represent matches. You draw an edge from a referee $r$ to a match $m$ if the referee $r$ is potentially available to officiate in that match. You can use the time() and avail() parameters to work out which edges to draw. Then, a solution to the assignment problem (a maximum matching in this bipartite graph) will represent a way to assign referees to matches. Thus, this captures the restrictions you want to enforce in a simple and natural way.
> 1 votes

---
Tags: optimization, linear-programming, integer-programming, variable-binding
---


title: Definition of NP

text:
# Question
Title: Definition of NP
We know that NP is the class of languages recognized by a nondeterministic Turing machine (NTM) in polynomial time. I've also read that NP is the class of problems can be solved by NTM in polynomial time. It is clear that every decision problem can be seen like a recognition language problem, but if we have a function problem (given $x$ find $y=f(x)$) what can we say?

In short, let $A$ be the decision problems solved by NTMs in polynomial time and $B$ be the function problems solved by NTMs in polynomial time. Is NP equal to $A$ or $B$ or both?

# Answer
> 2 votes
**NP** is a class of languages and languages correspond to decision problems. Specifically, any language $L$ corresponds to the decision problem, "Here's a string $x$. Is it in $L$?"

# Answer
> 1 votes
**NP** *by definition* is the class of decision problems solvable in polynomial-time on a non-deterministic Turing machine. So, by definition, **NP** is your $A$ set. **NP** can't also be $B$ for superficial reasons: **NP** is a subset of functions $2^\*\to 2$, and so it simply doesn't contain any functions $2^\*\to2^\*$ whose output isn't always one bit long.

There is a separate class **FNP** for the class of *search* problems solvable in polynomial-time on a non-deterministic Turing machine. A decision problem $\varphi$ is in **NP** when $$\forall x\in 2^\*.\varphi(x)\iff \exists u\in2^{p(|x|)}.M(x,u)=1$$ for some polynomial $p$ and polynomial-time (deterministic) Turing machine $M$. A function $f$ is in **FNP** if given $x$ it finds a $u$ such that $M(x,u)=1$. Note, there is no constraint on how much time $f$ takes to produce a $u$ from $x$. That said, on a non-deterministic Turing machine, we can just guess the bits of $u$ and then check them against $M$ in polynomial-time. (We can cast an arbitrary function computed in polynomial-time on an NDTM $F$ as the relation $R(x,\langle u,y\rangle)\iff F(x,u)=y$ where $u$ represents the non-deterministic choices which is calculable in polynomial-time simply by simulating $F$ with choices $u$.)

As mentioned on the Complexity Zoo page, The Complexity of Decision Versus Search shows that if **EE** $\neq$ **NEE** or (citing a different result) if **NE** $\neq$ **coNE** then there are problems in **FNP** that can't be reduced to corresponding decision problems in **NP** in the sense if for *any* suitable machine $M$ we're provided an oracle for $\varphi(x)\equiv\exists u\in 2^{p(|x|)}.M(x,u)=1$ we could compute in polynomial-time some $u$ for the particular $x$ we were given such that $M(x,u)=1$. Any decision problem whose corresponding search problem is reducible to the decision problem can't be **NP**-complete: given an oracle for an **NP**-complete problem, we'd then be able to efficiently compute **SAT** whose search problem we *can* reduce to the corresponding decision problem, and which we can then use to compute the $u$ for the original problem by reducing it to **SAT**.

So the focus on decision problems doesn't seem completely innocuous, but we do have **P** = **NP** $\iff$ **FP** = **FNP**, so for at least the **P** = **NP** problem it doesn't matter. This can be partially seen from the above since if **P** = **NP** then every problem in **NP** is **NP**-complete and the counter-example to the reduction of search to decision doesn't exist.

---
Tags: turing-machines, np, decision-problem
---


title: P=NP, isn't it?

text:
# Question
Title: P=NP, isn't it?
Cook and Levin showed in 1971 how deterministically in polynomial time from every non deterministic Turing machine **M**, that halts in polynomial number of moves/steps, and string **w** to create the boolean formula $\Phi\_{M,w}$ in **conjunctive normal form** that is **true** for each **accept** path/route of **M** on **w** and **false** for each **reject** path/route of **M** on **w** and therefore $\Phi\_{M,w}$ is **satisfiable** if and only if **M** accepts **w**.

Suppose $NTM\_{CNFFAL}$ is non deterministic Turing machine that decides in polynomial time the language **CNFFAL**, that is the language of all strings that are encoding of **falsifiable** boolean formulas in **conjunctive normal form**, by just guessing truth assignment that evaluates the input boolean formula to **false**.

Let **f** be any boolean formula in **conjunctive normal form**.

Therefore $\Phi\_{NTM\_{CNFFAL},f}\equiv\lnot f$ since Cook and Levin reduction is **parsimonious** and $\Phi\_{NTM\_{CNFFAL},f}$ is also in **conjunctive normal form**.

Therefore **f** is **falsifiable** if and only if $\Phi\_{NTM\_{CNFFAL},f}$ is **satisfiable**.

Therefore **f** is **satisfiable** if and only if $\Phi\_{NTM\_{CNFFAL},f}$ is **falsifiable**.

This suppose to show that $CNFSAT\le\_PCNFFAL$, where **CNFSAT** is the language of all strings that are encoding of **satisfiable** boolean formula in **conjunctive normal form**, also show that **CNFFAL** is NP Complete, since **CNFSAT** is already NP Complete and we all know that $CNFFAL\in\Bbb{P}$.

Therefore $\Bbb{P=NP}$, isn't it?

# Answer
> 1 votes
In the comments of Yuval Filmus' answer, the OP suggested that while, for any two CNF formulas $f$ and $\tilde{f}$,

($f \text{ falsifiable} \iff \tilde{f} \text{ satisfiable}) \iff (f \text{ satisfiable} \iff \tilde{f} \text{ falsifiable}$)

wasn't usually true, it was implied in that specific case by the parsimonious reduction of the CNFFAL instance $f$ to the CNFSAT instance $\tilde{f}$, thus proving that

$f \text{ satisfiable} \iff \Phi\_{NTM\_{CNFFAL},f} \text{ falsifiable}$.

This answer is supposed to show evidence that it isn't the case (assuming it isn't clear to the reader), as a complement of the previously mentioned answer (per request of the OP in the comments).

---

I'll try to exhibit an example making clear that it isn't the case. Now, building the corresponding $\Phi\_{NTM\_{CNFFAL},f}$ of some $f$ would be a bit tedious, so I'll build a parsimonious reduction from CNFFAL to SAT instead (contrast with the parsimonious reduction from CNFFAL to CNFSAT used in the question), but such that the falsifiability of the SAT instance doesn't imply the satisfiability of the CNFFAL instance.

I claim that, for any CNF formula $f$, any assignment $(a\_1, \dots, a\_n)$ falsifying $f(a\_1, \dots, a\_n)$ allows me to build a unique satisfying assignment of $\tilde{f}(a\_1, \dots, a\_n, c) = \lnot f(a\_1, \dots, a\_n) \land c$ (and vice-versa). This (admittedly dumb) reduction from CNFFAL to SAT preserves the number of solutions so it's parsimonious.

Now let's assume $f(a, b) = (a \lor b) \land (\lnot a \lor b) \land (a \lor \lnot b) \land (\lnot a \lor \lnot b)$.

There indeed are as many ways to falsify $f$ as to satisfy $\tilde{f}$ (4, per the previous parsimonious reduction). Therefore:

$f \text{ falsifiable} \iff \tilde{f} \text{ satisfiable}$

However there also are 4 ways to falsify $\tilde{f}$ (just set $c$ to 0) whereas $f$ is clearly unsatisfiable. Therefore:

$\lnot(f \text{ satisfiable} \iff \tilde{f} \text{ falsfiable})$

Contrast this with that excerpt of the reasoning in the question:

> Therefore $\Phi\_{NTM\_{CNFFAL},f}\equiv\lnot f$ since Cook and Levin reduction is **parsimonious** and $\Phi\_{NTM\_{CNFFAL},f}$ is also in **conjunctive normal form**.
>
> Therefore **f** is **falsifiable** if and only if $\Phi\_{NTM\_{CNFFAL},f}$ is **satisfiable**.
>
> Therefore **f** is **satisfiable** if and only if $\Phi\_{NTM\_{CNFFAL},f}$ is **falsifiable**.

---

The previous statement stems from the fact that $\tilde{f}$ uses more variables than $f$, hence the number of possible assignments of $\tilde{f}$ is greater than the number of possible assignments of $f$. Indeed, if those two numbers of possibilities were equal, the reduction being parsimonious would indeed lead to the equivalence of $f$ being satisfiable and $\tilde{f}$ being falsifiable (by a simple counting argument, as the set of falsifiable assignments is the complement of the set of satisfiable assignments).

In the question, $\Phi\_{NTM\_{CNFFAL},f}$ has been obtained thanks to Cook-Levin's reduction from an arbitrary NP problem to CNFSAT. That formula doesn't necessarily requires the same amount of variable as $f$ (and is actually very likely to require a far greater amount), so the equivalence doesn't necessarily holds.

# Answer
> 10 votes
Every CNF is falsifiable (choose a clause and choose a truth assignment which falsifies it). Unfortunately, the opposite of "CNF $\varphi$ is satisfiable" is not "CNF $\varphi$ is falsifiable". Rather, it is "CNF $\varphi$ is not satisfiable".

Also, even the two were opposites, your proof would only show that NP=coNP, which is not known to imply that P=NP.

---
Tags: complexity-theory, turing-machines, reductions, satisfiability, p-vs-np
---


# Question
Title: How is this definition of the quantum Fourier transform to be understood?
In regards to the **quantum** Fourier transform Page 845 of The Nature of Computation states

> The amplitudes $\tilde{a}\_\mathbf{k}$ are the Fourier coefficients of $a\_\mathbf{x}$, $$\tilde{a}\_\mathbf{k} = \langle \mathbf{k}|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum\_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a\_\mathbf{x}\\,.$$

Here $x$'s are the standard basis vectors and the $k$'s are (presumably) the Fourier basis. And $\psi = \sum\_\mathbf{x} a\_\mathbf{x}|\mathbf{x}\rangle$.
To pick a concrete example let the number of qubits, $n$, be 2. The book isn't clear on this but my first guess is that the $\mathbf{k}$'s should be these:

$$ \begin{bmatrix}1/2\\1/2\\1/2\\1/2\end{bmatrix}, \begin{bmatrix}1/2\\\-i/2\\\-1/2\\i/2\end{bmatrix},\begin{bmatrix}1\\\-1\\1\\\-1\end{bmatrix},\begin{bmatrix}1/2\\i/2\\\-1/2\\\-i/2\end{bmatrix}. $$

Though, I've also heard the argument that they should be the columns of

$$H \otimes H = \begin{bmatrix}1/2 & 1/2 & 1/2 & 1/2\\1/2 & -1/2 & 1/2 & -1/2\\1/2 & 1/2 & -1/2 & -1/2\\1/2 & -1/2 & -1/2 & 1/2 \end{bmatrix},$$

where $H$ is the $2\times 2$ Hadamard matrix. However, the book also states that

> each "frequency" is, like $\mathbf{x}$, an $n$-dimensional vector mod 2.

And I don't see how to convert the entries of either of these bases into elements of $\mathbb{Z}\_2$.
Ignoring that issue I immediately run in to the following. Take the first vector of either basis as $\mathbf{k}$ and compute the Fourier coefficient $\tilde{a}\_\mathbf{k}$ according to the definition above while also using $|\psi\rangle = \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2\end{bmatrix}^T$ as an example. On the one hand

$$ \langle\mathbf{k}|\psi\rangle = 1\\,. $$

But on the other hand

$$ \frac{1}{\sqrt{2^n}}\sum\_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a\_\mathbf{x} = \frac{1}{2} \left((-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2}\right) = i\\,. $$

What am I not getting here?

# Answer
> 1 votes
The index $\mathbf{k}$ goes over all vectors in $\\{0,1\\}^n$ (which can be identified with $\mathbb{Z}\_2^n$). The index $\mathbf{x}$ also has the same range, and $\mathbf{k} \cdot \mathbf{x} = \sum\_{i=1}^n k\_i x\_i$. You can think of this sum as being computed modulo 2 (or in $\mathbb{Z}\_2$) if you wish, since $(-1)^2 = 1$.

As an example, when $n = 2$ we get $$ \begin{align\*} \tilde{a}\_{00} &= \frac{a\_{00} + a\_{01} + a\_{10} + a\_{11}}{2}, \\ \tilde{a}\_{01} &= \frac{a\_{00} - a\_{01} + a\_{10} - a\_{11}}{2}, \\ \tilde{a}\_{10} &= \frac{a\_{00} + a\_{01} - a\_{10} - a\_{11}}{2}, \\ \tilde{a}\_{11} &= \frac{a\_{00} - a\_{01} - a\_{10} + a\_{11}}{2}. \end{align\*} $$

This is exactly the tensor square of the $2\times 2$ Hadamard matrix.

---
Tags: quantum-computing, fourier-transform
---


# Question
Title: How to prove Halting problem is solvable by oracle machine
How can we prove that the Halting problem is solvable by a machine with access to some oracle?

# Answer
An oracle machine is a regular machine, such as a Turing machine, with an attached device that is an oracle. This oracle, often called a black box to signify that it is not constructible in the real world, answers questions about some set.

For instance if the oracle is a $K$ oracle then it can answer yes or no whether numbers are in the set $K$ (I'm taking $K$ to be the name of the set of natural numbers $e$ such that Turing machine $e$ halts on input $e$). So obviously the Halting Problem can be solved by a machine that has access to this oracle.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: maximum matching number decreases when vertices collapse?
It seems that the maximum matching number **decreases** when some *independent* (not connected) vertices collapse into one vertex, but I don't know if it is absolutely true. Would maximum matching number **increases** when two vertices are connected to form a new edge?

Any proof? Thanks!  Definitions: Given a graph G = (V,E), a **matching** M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

A **maximum matching** (also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges.

# Answer
I just find the proof in Karp, Richard M., and Michael Sipser. "Maximum matching in sparse random graphs." Foundations of Computer Science, 1981. SFCS'81. 22nd Annual Symposium on. IEEE, 1981.
> 1 votes

# Answer
Try to find a proof that it can't happen! Keep trying. Hint:

> Suppose you have a maximum matching for the collapsed graph. Can you use that to find a matching for the original graph? How many edges does it have? What does that imply about your question?

If you're really stuck, try to write a program to enumerate all graphs with at most 6 vertices (say) and see if the matching number can ever increase after collapsing an edge. That should enable you to form a reasonable conjecture, which you can then try to prove, or should give you a counterexample.
> 2 votes

---
Tags: graphs, matching
---


# Question
Title: How to find max flow in a graph after decrementing an edge capacity?
We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for each edge. We're also given some edge $e'$.

How can the max flow be found if we decrement the capacity value of an edge $e'$ by $1$ in **linear** time?

# Answer
> 13 votes
If the capacity of edge $c(e') \ge f(e') + 1$ i.e. the max flow remains the same, there is no chance max flow increase, as it would increased without decreasing $c(e')$.

Suppose that $c(e') = f(e')$ (this edge is saturated) and we decrease the capacity in $1$ unit. You need to remove one unit of flow from $s$ to $t$ that goes through edge $e'$. Let say that $e'= (u,v)$.

**Removing flow:** Just run two **BFS**, one starting from $s$ to $u$ going through edges that has flow greater that $0$, the other from $v$ to $t$ equally from edges that has flow greater than $0$. (It is guaranteed you will reach your goal in both cases since there is a unit of flow traversing this edge). Select a path from $s$ to $u$ and remove $1$ unit of flow from each edge and do the same with a path from $v$ to $t$. Complexity: $O(|V| + |E|)$

**Recover max flow:** Now we have a valid flow network but not necessarily the network with max flow. So now you just need to run one iteration of augmenting path with the capacity of edge $e'$ reduced. (Just like running one iteration of Ford-Fulkerson algorithm) Running just one iteration has the complexity of a single **DFS** which is $O(|V| + |E|)$.

Overall complexity of this approach would be $O(|V| + |E|)$ which is **linear** in the amount of nodes and edges.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?
If **M** is non deterministic Turing machine and **w** is any string then $\Phi\_{M,w}$ is satisfiable if and only if **M** accepts **w** according to Cook and Levin (1971).

By the definition of non deterministic Turing machine, **M** accepts **w** if and only if **M** has an accept computation on **w**.

But if **all** computations of **M** on **w** are **accept** then is $\Phi\_{M,w}$ necessarily a **tautology** more than just satisfiable?

We know for sure that if **M** rejects **w** then **all** computations of **M** on **w** are **reject** and $\Phi\_{M,w}$ is unsatisfiable.

# Answer
> 3 votes
The formula $\Phi\_{M,w}$, which says "Turing machine $M$ accepts input $w$" is never a tautology.

If you look at how the formula is defined, the variables denote things like "At time $t$, the machine is in state $q$" and "At time $t$, the $i$th cell of the tape contains symbol $\sigma$" and the clauses say things like, "$M$ is only in one state at a time", "every tape cell contains only one character at a time" and "the tape cells don't change except where the head is." Thus, any assignment to the variables that violates these conditions (e.g., in two states at once, two characters in the same tape cell, characters on the tape changing without being written by the head), then $\Phi\_{M,w}$ is falsified.

---
Tags: complexity-theory, turing-machines, satisfiability, strings, nondeterminism
---


# Question
Title: Not able to prove non regularity using pumping lemma
$L$ = $0^p1^q0^p$. Where $p, q \geq 0$

Here for any string $w \in L$ , I can have $u$=$0^p$, $x$ = $1^q$ and $v$= $0^p$ and $x^i$ will belong to L for all $i \geq 0$

So how do I prove it to be non regular using pumping lemma as there doesn't exist a string $w \in L$ which cannot be decomposed into the form $ux^iv$ for all $i \geq 0$.

# Answer
> 1 votes
Don't forget that the pumping lemma guarantees that $|ux| \leq n$, where $n$ is the pumping length (which is also a lower bound on the length of $w$). You can use this condition to forbid the situation you describe.

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


# Question
Title: Why doesn't Quantum Turing Machine contradict with Church-Turing thesis
I studied about Quantum Turing machine and i figured out that the difference between QTM and TM is in transition function and also if a problem is unsolvable by a TM then it is unsolvable by a QTM but I need a justifiable reason to claim QTM does not contradict with Church-Turing thesis.

# Answer
> 4 votes
Quantum Turing machines can be simulated by classical Turing machines. See Deutsch's fundamental paper Quantum theory, the Church-Turing principle and the universal quantum computer.

---
Tags: complexity-theory
---


# Question
Title: What is the computational complexity category of $T(n) = m^{\frac{n-1}{m}}$?
I'm analyzing the computational complexity of an algorithm whose input size is $n$. Finally, I've ended up with $T(n) = {m^\frac{n-1}{m}}$ where $m$ is a constant. Can one explain the type name corresponding to this computational complexity (e.g., exponential, etc.)?

# Answer
> 1 votes
Since $c=m^{\frac{1}{m}}$ is a constant, your $T(n) = c^{n-1} \in \Theta(c^n)$ is simply exponential.

---
Tags: terminology, asymptotics
---


title: LTL Until Tautology

text:
# Question
Title: LTL Until Tautology
Today I had to prove some tautologies as an exercise, one of them was:

(Ga)-\>(Fb) equivalent aU(b v ¬a)

It is clear that I have to prove the implication in both ways. After putting into negation normal form i get that:

F(¬a v b) -\> aU(b v ¬a) and viceversa.

I managed to prove the opposite implication, since aU(b v ¬a) implies that at some point we will either see b or ¬a, but I couldn't get around proving the other direction. I am sure it is because we have a and ¬a on the opposing sites of U, but the reasoning is not clear to me.

Can someone clear this up for me?

# Answer
Let us try to prove that $F(\neg a \vee b) \rightarrow a\\,\mathcal{U}\\,(b \vee \neg a)$ is a tautology. For this, we have to show that every word that is a model of $F(\neg a \vee b)$ is also a model of $a\\,\mathcal{U}\\,(b \vee \neg a)$

Let $i \in \mathbb{N}$ be the least index of the word for which we have $w^i \models (\neg a \vee b)$, where $w^i$ denotes taking a word $w\_0 w\_1 w\_2 \ldots$ and removing all letters up to $w\_{i-1}$. By the assumption that $w \models F(\neg a \vee b)$, we know that such an index exists, so we can pick the least such index. Because $i$ is the least such index, we know that for all $0 \leq j \< i$, we have $w^j \not\models (\neg a \vee b)$, and hence $w^j \models a \wedge \neg b$ and also also $w^j \models a$.

So we know that $w^i \models (\neg a \vee b)$ and for all $0 \leq j\<i$, we have $w^j \models a$. By the definition of the until operator, we thus have $w \models a\\,\mathcal{U}\\,(\neg a \vee b)$.
> 3 votes

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


# Question
Title: Asymptotic complexity class preservation under logarithm?
If $f(x)$ and $g(x)$ are two functions such that

$$f(x) \not\in \Omega(g(x))$$

does

$$\log f(x) \not\in \Omega(\log g(x))$$

hold?

# Answer
This does not hold for all $f$, $g$. Consider $f(x) = x!$ and $g(x) = x^x$. It is the case that $x! \not\in \Omega(x^x)$ yet, using Stirling's approximation, we have that

$$\log (x!) \in \Theta(x \log x)$$

Since, $\log(x^x) = x \log x$, we have

$$\log f(x) \in \Theta(\log g(x))$$
> 1 votes

---
Tags: asymptotics
---


title: Median-of-medians in O(log n) memory

text:
# Question
Title: Median-of-medians in O(log n) memory
Is there a way to use median-of-medians to find a median in,
simultaneously,  O(log n)  memory and O(n) comparisons?

The user orlp on this site seems to claim that there is.

Getting  O(log n)  *auxiliary* memory seems to be straightforward,
but I have no clue how that can be improved to O(log n) memory.

# Answer
There is no such way.
This paper shows

> that any comparison-based randomized algorithm for finding the
> median requires $\Omega(n \log \log\_{\hspace{.02 in}S} n)$ expected time in the RAM model
> (or more generally in the comparison branching program model),
> if we have S bits of extra space besides the read-only input array.
> This bound is tight for all $S\gg \log n$, and remains
> true even if the array is given in a random order.

$n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)} \\; = \\; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$
and
$\operatorname{polylog}(n) = 2^{\log(\hspace{.02 in}\operatorname{polylog}(n))} = 2^{O(\hspace{.02 in}\log(\hspace{.02 in}\log(n)))} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}o(1)}\hspace{-0.03 in}\right)} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$
so since
$2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \\: \cdot \\: \operatorname{polylog}(n) \\;\\;\\; \subseteq \\;\\;\\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \\: \cdot \\: 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$
$= \\;\\;\\; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}+\hspace{.02 in}(\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)} \\;\\;\\; = \\;\\;\\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$

and

$\Omega \hspace{-0.04 in}\left(n\log \log\_{2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}} n\right) \\;\\;\\; = \\;\\;\\; \Omega \hspace{-0.04 in}\left(n\cdot \left(\log(\hspace{.02 in}\log(n))-\log \left(\log \left(2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}\right)\right)\right)\right)$
$= \\;\\;\\; \Omega(n\cdot ((1\cdot \log(\hspace{.02 in}\log(n)))-((1-\Omega(1)) \cdot \log(\hspace{.02 in}\log(n)))))$
$= \\;\\;\\; \Omega(n\cdot (1-(1-\Omega(1))) \cdot \log(\hspace{.02 in}\log(n))) \\;\\;\\; =$
$\Omega(n\cdot \Omega(1) \cdot \log(\hspace{.02 in}\log(n))) \\;\\;\\; = \\;\\;\\; \Omega(n \log \log n)$

and

pointers can be represented with  O(log(n))  bits

,
even when one measures with polylog(n)-bit machine words and assumes that
input-elements fit into such words, comparison-based selection algorithms
that use at most    $2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$  $\Big($equivalently,  $n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)}\Big)$    space
require  $\Omega(n \log \log n)$  comparisons on average,
even if the array is given in a random order.
> 1 votes

---
Tags: asymptotics, space-complexity, comparison
---


title: Counting to infintiy problem

text:
# Question
Title: Counting to infintiy problem
I came across this explanation for count to infinity problem

However, i don't understand that after the BC link broke, followed by which B erroneously updated the path to C at a cost of 3; Now why will A update the cost to C as 4 (after getting updates from B) since its current cost to C is 2 which is lesser than that advertised by B?

# Answer
> 1 votes
I'll describe what happens, and then describe why each router made the decisions that it made using the scenario from the question.

The starting situation is a steady-state where the routers $A$, $B$, and $C$ have the connectivity $$A\stackrel{1}{\to} B\stackrel{1}{\to} C$$ $B$ is connected to $C$ in one hop, $A$ is connected to $B$ in one hop, and $A$ knows that it is connected to $C$ via $B$ in two hops.

1. The connection from $B$ to $C$ goes down.
2. $B$ notices this and updates its distance information from $1$ to $\infty$.
3. Before $B$ notifies $A$ of the change, $A$ broadcasts an update saying that it has a route to $C$ in $2$ hops.
4. $B$ updates its routing table to record its belief that it can reach $C$ in $3$ hops via $A$.
5. $B$ broadcasts an update saying that it has a route to $C$ in $3$ hops.
6. $A$ updates its routing table to record its belief that it can reach $C$ in $4$ hops via $B$.
7. Et cetera.

From the comments, your issue is with step $6$. If $A$ already has a route to $C$ in $3$ hops, why wouldn't it just ignore the worse route via $B$ in $4$ hops and stay at $3$ hops? Well, the purpose of a router is to route messages. If I give $A$ a message to send to $C$, it needs to know who to send it to so that it eventually reaches $C$. $A$ knows that it will need to send to the message to $B$ for it to most efficiently reach $C$. In particular, $A$ knows that its distance estimate for a route to $C$ is based on the distance estimate of $B$. So if $B$ says that the distance has increased, $A$ knows that the distance has also increased for it (unless it can find a better route).

Of course, this is exactly what we want. Given the following connectivity diagram, if the connection marked by $(\*)$ goes down, we want $A$ to start routing via $D$ ($3$ hops) rather than $B$ ($4$ hops) to send messages to $F$. That $B$ had a $2$ hop path in the past shouldn't matter. If $B$ loses all connectivity to $F$ (e.g. the connection between $B$ and $C$ also goes down), we certainly don't want to keep trying to route through $B$ just because it *was* the best route in the past. $$\require{AMScd} \begin{CD} A @\>\>\> @\>\>\> B @\>\>\> C \\ @VVV @. @V(\*)VV @VVV \\ D @\>\>\> E @\>\>\> F @\<\<\< G \end{CD}$$

To put it a different way, we're talking about a dynamic version of the Bellman-Ford algorithm where edges can be added or removed in an online manner. Removing edges, in particular, makes the updates no longer monotonic. That is, we can no longer only keep the "best" routes we've ever heard, and we instead have to deal with potential "retractions".

Returning the the original, simpler scenario, the issue is when $B$ receives an update from $A$ that $A$ has a $2$ hop route to $C$, $B$ doesn't know that this information is dependent on $B$'s route to $C$. If $A$ had said that its route to $C$ was *via $B$*, then $B$ would have realized that this route was no longer useful and would not have updated its routing table in step 4. The split horizon modification solves this particular scenario by simply not having $A$ inform $B$ about any routes that $A$ can only reach (directly) through $B$, so step 3 never occurs as far as $B$ is concerned.

---
Tags: algorithms, graphs, computer-networks
---


# Question
Title: Can the Same Function Have Different Asymptotic?
Say we had a function $4^k$.

The asymptotic of this function would be $\Theta(4^k)$, and thus we would say the function has exponential run-time.

But what if $k = \log{n}$? Then our same function would be $4^k = 4^{\log{n}} = n^{\log{4}} \in \Theta(n^{\log{4}})$.

(Step 2 to 3 is accomplished via a change of logarithm base).

Would we now say the function runs in polynomial time?

Or something more nuanced, like

“The function is exponential in respect to k, and polynomial in respect to n”?

# Answer
> 3 votes
Your question is more a question about language than about computer science and you are confusing functions and runtimes of algorithms.

$O, \Theta, o$ are ***mathematical* tools to compare functions** but it stops there. Functions are functions, mapping values to values and do not have a "runtime".

Algorithms have runtime which is the function that maps a size $n$ with the maximal time needed by this algorithm to solve instances of size $n$.

$O, \Theta...$ notations are about *functions*. In your first example, you have a function $k \mapsto 4^k$. This function is a function of $k$ and grows exponentially. This function of $k$ is indeed $\Theta(4^k)$ but it is also $\Theta(4^{k+1})$ because $(1/4) 4^{k+1} \leq 4^k \leq 4^{k+1} $. It is also $\Theta(4^{k+489})$ for what it is worth. So there is nothing unique about this. It is simply a way of focusing on the main part of a function when we are only interested in its asymptomatic behavior.

If you have an *algorithm* which runs in time $4^k$ it means its runtime, which is a function, is $4^k$, that is, when the size of the input is $k$ then the algorithm finished in less that $4^k$ steps and for some input of size $k$, you need $4^k$ steps. In this case, *this algorithm runs in exponential time*.

If you have an *algorithm* which runs in time $\Theta(4^k)$, it means that the runtime of the algorithm, which is a function, is $\Theta(4^k)$ and indeed you have an exponential time algorithm.

If you have an *algorithm* which runs in time $O(4^k)$, it means that the runtime of the algorithm, which is a function, is $O(4^k)$. In this case, you cannot say for sure that your algorithm runs in exponential time. It may well be that the true runtime of your algorithm is $\Theta(k)$ but that you haven't proven it yet.

Now you ask what if "$k=\log(n)$". In this case, you are now talking about the following fuction: $n \mapsto 4^{\log n}$ which turns out to be $n^{\log 4}$ which is indeed bounded by a polynomial in $n$. So if you have an *algorithm* which runs in time $n^{\log 4}$ on input of size $n$ then this algorithm runs in polynomial time.

But if your algorithm runs in time $n^{\log 4}$ for input of size $\log(n)$, then this algorithm runs in exponential time.

# Answer
> 3 votes
The asymptotic behaviour of a function always depends on the parameter in the function. So for your example, I'd say that claiming that the function is exponential w.r.t. $k$, but polynomial w.r.t. to $n$ is correct.

When we look at the running time of algorithms, we consider it to be a function of the size of the input (usually the number of bits in a binary encoding). So, for an algorithm, it is always well defined whether it is for instance polynomial or not, but this can depend on how you define or encode your input.

---
Tags: asymptotics
---


# Question
Title: How is the traveling salesman problem verifiable in polynomial time?
So I understand the idea that the decision problem is defined as

> Is there a path P such that the cost is lower than C?

and you can easily check this is true by verifying a path you receive.

However, what if there is no path that fits this criteria? How would you verify the answer of "no" without solving the best path TSP problem, and finding out the best one has a worse cost than C?

# Answer
**NP** is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances.

The class of problems where you can verify "no" instances in polynomial time is **co-NP**. Any language in **co-NP** is the complement of some language in **NP**, and vice-versa. Examples include things like non-3-colourability. The problem you describe, "Is there no TSP path with length at most $C$?" is also in **co-NP**: if you unpick the double-negation, a "no" instance to that problem is a "yes" instance to TSP and we can verify those in polynomial time.

There are some problems, such as integer factorization and any problem in **P**, that we know to be in both **NP** and **co-NP**. (Thanks to user21820 for pointing this out.)

It's not known whether **NP** and **co-NP** are the same set of problems. If they're the same, then we can verify both "yes" and "no" instances of TSP. If they're different, then **P$\\,\neq\\,$NP**, since we know that **P$\\,=\\,$co-P** (because we can just negate the answer of a deterministic machine, giving the answer to the complement problem).
> 36 votes

# Answer
> "How is the traveling salesman problem verifiable in polynomial time?"

Either in the way you describe, or there's not known to be such a way.

> "However, what if there is no path that fits this criteria?"

In that case, for all NP machines for the decision problem, the machine will return no for all candidate-certificates.

> "How would you verify the answer of "no" without solving the best path TSP problem, and finding out the best one has a worse cost than C?"

Well, one could receive an interactive proof that there are no such paths.

The problem you describe, TSP, is not known to be in coNP, so there's not known to be an "NP-like" way of verifying that there is no such path.
> 2 votes

---
Tags: complexity-theory, time-complexity, np, decision-problem, traveling-salesman
---


# Question
Title: Is there a heuristic or function to determine if two arrays of integers are alike or similar
What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say `a = [0, 1, 2, 3, 4]`, `b = [0, 2, 1, 3, 4]`, and `c = [1, 4, 2, 0, 3]`. Is there a function to determine that `a` is closer to `b` than `c` is?

So the function I am looking for I think should be similar to SHA, but without the avalanche effect. The examples I give is using arrays of integers, but obviously this should also work on any arbitrary stream of data.

# Answer
There are many measures of similarity between sequences (or arrays or even strings), which one to use depends on the specific goals for the similarity. It may be the case that some trial and error is required to find the 'best' one. Therefore, I'll give a brief overview of some well-known similarity measures:

First, I consider distances most commonly associated with *strings*:

* Edit distance: Here, we count minimum the number of 'edit operations' required to transform string $A$ into string $B$. These edit operations are usually inserting, deleting or substituting a single character in your string or array. Usually, the different operations have different costs. The Levenshtein distance is a special case of the edit distance that is commonly used to compare words.
* Hamming distance: This distance simply counts the number of indices between two sequences that differ, which is the same method you described in your comment. This can at times be a decent metric, but it often doesn't come close to an our intuitive notion of 'similarity'.

There are many more string metrics, but those above are the most commonly known.

Next, you could also consider metrics over *time series*: here the sequences are interpreted as measurements at increasing time-steps. Usually, we assume there is some distance measure over the individual elements of your sequences, this can be taken as simply $d(x,y) = \begin{cases} 0 & \text{if $x=y$}\\ 1 & \text{if $x\neq y$}\end{cases}$, if you don't have a more reasonable notion of distance between your characters.

* Dynamic Time Warping (DTW): This distance finds a suitable 'alignment' between the pair of sequence that minimizes the sum of the distances between the alignment. An advantage of this method is that this measure is insensitive to 'time shifts': The sequences $A=\langle 1, 2,3,4,5 \rangle$ and $B=\langle 0 ,1, 2,3,4\rangle$ have maximum Hamming distance, but a low DTW distance, as DTW is allowed to match the element $A\[1\]$ to $B\[2\]$, $A\[2\]$ to $B\[3\]$ and so on. Computing the DTW between two sequences takes $O(n^2)$ time (if both sequences have length $n$), but there are many faster approximations and heuristic speed-ups.
* Longest Common Subsequence (LCS): This isn't always used as a similarity measure, but the length of a LCS between two sequences $A$ and $B$ can be seen as inversely proportional to the distance between $A$ and $B$ (i.e. long common subsequences mean high similarity). A disadvantage of this measure is that it often ignores too much of the relevant structure of the sequences, but it sometimes works fine.

Other similarity measures for time series can be found here.
> 3 votes

---
Tags: hash, hashing, string-metrics, edit-distance
---


title: prove that $h(x)$ is partial recursive

text:
# Question
Title: prove that $h(x)$ is partial recursive
If $f:A^\*\rightarrow A\*$ and $g:A^\* \rightarrow A^\*$ are partial recursive we want to prove $h:A^\* \rightarrow A^\*$ with the following definition is partial recursive $$ h(x) = \begin{cases} \lambda & f(x) = \lambda\\ g(x) & \textrm{otherwise} \end{cases} $$ for $x \in Dom(f)$.

One of my friends tried using a $\textrm{step}$ function that we know is primitive recursive and also partial recursive $$ \textrm{step}(x,y) = \begin{cases} C\_{\lambda} & x = \lambda\\ y & \textrm{otherwise} \end{cases} $$ and defined $h(x) = \textrm{step}(f(x),g(x))$. but I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive. Is this solution correct or not?

# Answer
> I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive.

Yes, you are, or at least you should be. Consider $h'(x) = \textrm{step}(f(x), \Omega(x))$ where $\Omega$ is not partial recursive. Would you consider that to be partial recursive? If not, why not?

If you define $h(x)$ as your friend has, you need to prove firstly that it's equivalent to the original definition. Once you've done that, it suffices to prove that it's partial recursive. But composition of p.r. functions gives a p.r. function, which is the key step that either your friend forgot to state or that you have overlooked.
> 1 votes

---
Tags: computability, primitive-recursion, mu-recursion
---


# Question
Title: Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences
Given inorder and preorder (or postorder) traversal sequences of a

1. binary tree
2. balanced binary tree
3. binary search tree

of n nodes, what is the time complexity of creating the respective unique tree.

# Answer
Assuming inorder and preorder sequences are given -

**1. For binary tree :** Starting with the root node, traverse the preorder sequence and for each node, binary search on the given inorder sequence, separating the left and right subtrees. Recurse on the next node with the new *piece* of the inorder sequence. Time complexity in worst case : **T(n) = T(1) + T(n-1) + O(logn) = O(nlogn)**

**2. For balanced binary tree :** Follow the same procedure as in 1. But, since the tree is balanced, the time complexity in worst case is different: **T(n) = 2T(n/2) + O(logn) = O(n)**

**3. For binary search tree :** Traverse the preorder sequence and at each node, keep a flag (=key of the parent node). If the next node in the sequence is less than the flag, then the node gets to be the left or right child of the current node. Else, we go back to the parent recursively and apply the same procedure to it. **Time complexity = O(n)** since we are creating nodes in the preorder sequence.
> -1 votes

---
Tags: time-complexity, binary-trees, binary-search-trees
---


# Question
Title: Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms
I want to prove that $H(L\_1 \cap L\_2) = H(L\_1) \cap H(L\_2)$ is not always true.

If $L\_1 = (ab)^\*$ and $L\_2 = (ba)^\*$ with mapping $H(a) = 1$ and $H(b) = 1$, $H(\epsilon) = 2$, then $H(L\_1 \cap L\_2) = 2$ while $H(L\_1) \cap H(L\_2) = (11)^\*$.

Is the above example correct to prove the above statement? Is it allowed to map two symbols to one same symbol?

# Answer
> 3 votes
Given two finite non-empty alphabets $\Sigma,\Delta$, a *homomorphism* is a mapping $h\colon \Sigma^\* \to \Delta^\*$ that satisfies the following two properties:

* $h(\epsilon) = \epsilon$.
* $h(xy) = h(x) h(y)$.

(Actually the first property follows from the second, since it implies that $h(\epsilon) = h(\epsilon \epsilon) = h(\epsilon) h(\epsilon)$, and so $h(\epsilon) = \epsilon$.)

It is not hard to show that $h$ is determined by its value on letters of $\Sigma$. Indeed, if $w = \sigma\_1\ldots \sigma\_n$, where $\sigma\_1,\ldots,\sigma\_n \in \Sigma$, then $h(w) = h(\sigma\_1) \ldots h(\sigma\_n)$. Conversely, if $h\_0\colon \Sigma \to \Delta^\*$, then the mapping $h(\sigma\_1 \ldots \sigma\_n) = h\_0(\sigma\_1) \ldots h\_0(\sigma\_n)$ defines a homomorphism. In formal language theory, one often identifies $h$ and $h\_0$.

---
Tags: formal-languages, regular-languages
---


# Question
Title: PDA pushing nothing given an input and the current stack top
If we had a language $$\sum = \\{a,b,c\\}$$ for a pushdown automata, and the transition $$a;A/AA$$ means "If you read in an `a` and `A` is at the top of the stack, push `A`", then would you be able to push nothing if you encounter an `a` and `A` is at the top of the stack with the transition: $$a;A/\epsilon \space C$$
I am new to this notation so I am unsure of if I am doing it correctly.

# Answer
> 3 votes
In a commonly used model for pushdown atomata instructions of the automaton are of the form $(p,a,A,q,\alpha)$ meaning in state $p$, read $a$ from the input, pop $A$ from the stack, change to state $q$ and push $\alpha$ to the stack. In a diagram for the pda this can be represented as an edge from $p$ to $q$ labelled by $a; A/\alpha$. Note the first symbol of $\alpha$ end at the top of the stack.

There are some complications. First $a$ can be the empty string, so that the automaton ignores the letter on its input tape. To the contrary, the automaton cannot easily ignore its stack. The topmost symbol is always popped.

So if we want to perform the instruction "read $a$ whatever is on the stack" this is implemented as a set of instructions $(p,a,A,q,A)$ for *all* stack symbols $A$. If we want to perform "read $a$ when $A$ is on the stack (and leave $A$ there)" we just have the instruction $(p,a,A,q,A)$ for *this particular* symbol $A$. This seems to be your case.

Also the instruction "read $a$ and pop $A$" is then $(p,a,A,q,\varepsilon)$, pushing nothing after popping $A$.

Finally, the fact that we always need to pop at least one symbol means that formally the automaton cannot move on the empty stack, and blocks. This means if it did not just accept its input, it cannot continue and the computation fails. (Be aware, not all books agree on the precise details here.)

---
Tags: pushdown-automata
---


# Question
Title: How should I "read" a dereference operator?
For example, when I look at some code like

```
int x = 1;
int * y = &x;

```

I can read it like

```
x equals 1
y equals the address of x

```

but how would I "read" something like

```
*y = 1;

```

My best guess is

```
The value at address y equals 1

```

But I'm wondering if there's a better way to think about it.

# Answer
> 2 votes
I always read `*y =1` as: assign the value $1$ to the memory location pointed by `y`.

Why?

`y` is a pointer type variable, so it has an address as a value. It another words, it points to this address. When we want to, indirectly, manipulate the memory area pointed by `y` we use `*y`. Hence `*y=1` tells that the value $1$ should be stored in the memory location pointed by `y`.

---
Tags: memory-access, c
---


title: Solving retreat formulas

text:
# Question
Title: Solving retreat formulas
I want to solve the following formula: $T(n)=T(n-1 )+ c\cdot\log n $, $T(1)=d$

I though about master but then I realized there is no dividing here so it's not gonna do it, I tried to expand the formula like this:

$T(n-1)=T(n-2) + c\cdot \log(n-1)$

$T(n-2)=T(n-3) + c\cdot \log(n-1)$

How do I find the general formula? How do I proceed from here? My professor taught us only master theory, no iteration

# Answer
If you unroll the formulae you get: $$T(n) = T(n-1) + c \cdot log(n) = \sum\_{i=2}^{n} c\cdot log(i) + d = O(n \cdot log(n)) $$

Last equality is true from the following fact: $$\sum\_{i=1}^n log(i) \ge \sum\_{i=\frac{n}{2}}^n log(i) \ge \frac{n}{2} \cdot log(\frac{n}{2}) = O(n \cdot log(n))$$ $$\sum\_{i=1}^n log(i) = log(n!) \le log(n^n) = n\cdot log(n) = O(n\cdot log(n))$$
> 1 votes

---
Tags: algorithms
---


# Question
Title: How do I arrive at the multiplication function in lambda calculus?
I'm familiar with how Church numerals are defined in the lambda calculus, i.e. as functions that take two arguments and apply the first argument $n$ times to the second.

Then I have the successor and addition functions, both of which I managed to derive and understand:

$$\begin{align} \mathrm{succ} &:= \lambda nsz.s (n s z) \\ (+) &:= \lambda nm.n\ succ\ m \\ \end{align} $$

But multiplication is where I'm stuck.

I understand that we can define a multiplication function $(\*)$ by adding the number $m$ to $0$ exactly $n$ times. After all, $3 \times 2$ is simply $2 + 2 + 2 + 0$.

So that could mean that $(\*)$ looks like this:

$$(\*) := \lambda nm.n\ ((+)\ m)\ 0$$

This appears to be a somewhat intuitive definition of a lambda calculus multiplication function to me, and if I try it out with $2$ and $3$, after some messy reductions, the result seems correct and $(\*)\\,2\\,3 \rightarrow 6$.

But then elsewhere I found this definition for multiplication:

$$\mathrm{mult} := \lambda xya.x (y a)$$

Now I don't see how you arrive at this function $\mathrm{mult}$. My definition $(\*)$, which takes two arguments, seems intuitive enough to me. But his here, which takes two arguments, one for the $x$ and $y$ respectively, which are the numbers to be multiplied, and then a third one $a$, just seems impenetrable to me—and I cannot figure out why it works, or how you would derive it.

Can somebody help me understand the reasoning and derivation of this $\mathrm{mult}$ function?

# Answer
You know that $(\bar{n}\ s)$ corresponds to $s^{(n)}$, i.e. function $s$ applied $n$ times to its argument. You want to obtain a function that iterates some function $s$ exactly $n \cdot m$ times. From the above observations and some simple rules for the composition of functions we can immediately derive the body of $\textsf{mult}$:

$$s ^ {(n \cdot m)} = \left( s ^ {(m)} \right) ^ {(n)} = \bar{n} \left(s ^ {(m)} \right) = \bar{n}\ (\bar{m}\ s) $$

Hence

$$ \textsf{mult}\ :=\ \overbrace{\lambda n m.}^\text{ parameters}\underbrace{(\lambda sz.n\ (m\ s) z)}\_{\text{Church numeral}}$$

or, if we $\eta$-contract, we get

$$ \textsf{mult}\ :=\ \lambda nms.n\ (m\ s)$$
> 5 votes

---
Tags: lambda-calculus, church-numerals
---


# Question
Title: k-means clustering with efficient point lookup?
What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still efficiently lookup a point $p$ and classify it into a cluster ID (an integer)?

Obviously standard $k$-means alone is not sufficient. Would putting the centroids of each cluster into a BSP or $k'$D-tree do the trick? I used $k'$ there because that $k'$ has nothing to do with $k$.

# Answer
Instead of the classical $k$-means algorithm where you

* classify all points and then
* update the center of each cluster to be the average of all points of that cluster,

you could use the *sequential* variant of $k$-means:

```
centers = random(k)
while True:
    p = next_point(points)
    c = find_center(centers, p)
    c = c + a * (p - c)

```

`next_point` iterates all the points and maybe prefers new points (*online*) for example by using deque and putting new points front.

`find_center` classifies a point. This takes $O(k)$ naive and $O(\log k)$ using a spacial datastructure like a k-d tree.

$a \in \[0,1\]$ says how much a center moves in the direction of the given point. Usually this is time dependent and gets lower with time, i.e. $a(t) = \lambda\_1 e^{-\lambda\_2 t}$. Maybe one could boost the weight of new points though.
> 1 votes

---
Tags: trees, binary-search-trees, clustering
---


# Question
Title: an appropriate data-structure to represent a family of sets (Which supports exactly MAKE-SET(x), UNION(S1,S2), REPORT(S))
I need to represent a family F of sets with some appropriate datastructure. The datastructure needs to support the procedures MAKE-SET(x), DISJOINT-UNION(A,B) and REPORT(A). I dont have a problem with implementing the procedures themselves. Its pretty straightforward if you follow the idea introduced in the chapter on disjoint-set data-structures in Introductions to Algorithms (CLRS for short). My problem is, in this book there is an added procedure Find(x), that, given any member of F, finds the set it belongs to by returning a representative of its set. But i am not meant to implement this procedure. So how exactly am i supposed to represent the family F? I figure we need some way of representing this collection seeing as otherwise what we have is just loose and unassociated sets. What do i do?

if it serves any interest here is the original problem statement:

> We are interested in maintaining a family of sets of integers F = S1, …, Sk under the following operations:
>
> • MAKE-SET(x ): add the set {x} til F
>
> • REPORT(Si ): report (ex. print) all elements in Si.
>
> • UNION(Si , Sj ): add the set Si ∪ Sj to F . delete Si og Sj from F.
>
> • DISJOINT-UNION(S1, S2): Like UNION except it is assumed Si and Sj are disjoint, meaning., Si and Sj do no share any elements. If Si and Sj are not disjoint the result of the operation is not defined.
>
> 4.1. Come up with a datastructure, which supports MAKE-SET and DISJOINT-UNION in O(1) time and REPORT(Si ) in Θ(|Si|) time. Hint: use an appropriate list datastructure

# Answer
What they mean is: find data structures and algorithms to implement the MAKE-SET, DISJOINT-UNION, and REPORT operations. That's all that they mean by "represent the family of sets". The representation is the data structure where the data is stored.
> 1 votes

---
Tags: data-structures, sets, union-find
---


# Question
Title: True Postcondition, with true Precondition
In my exam preparation I stumbled across the follwoing exercise regarding pre and postconditions:

As far as I understood the question, we need to express some condition for p, such that if that condition holds for p, then we have that {true} p {true}.

The conclusion I got to when trying to think about it intuitevely is that p could simply be a skip statement, but I found myself wondering what a {true} postcondition implies. I know a {true} precondition means that there is no restriction on inputs, what does it mean for postcondition? What would be such a suitable condition to express p?

Thanks!

# Answer
> 2 votes
A true postcondition means there is no restriction on outputs.

Think about it. The condition `x > 5` means: it's true (anything goes), as long as `x` is greater than `5`. The only way for that condition to be invalidated is when `x` isn't greater than `5`. The condition *true* means: `x` doesn't even need to be greater than `5`. There is no way to invalidate that condition at all. Anything goes.

(If you don't mind, I'll leave the rest to you.)

---
Tags: correctness-proof, hoare-logic, program-correctness
---


# Question
Title: Prove complexity bound without reduction?
The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the complexity of the reduction itself).

In particular, I'm thinking about the fact that breaking RSA encryption is believed to be at least as difficult as factoring a composite number into primes, but nobody has ever figured out how to express prime factorization *in terms* of RSA decryption. My question is: if somebody wanted to go about proving that breaking RSA is at least as difficult as prime factorization without relying on reduction, what techniques might be available to them?

# Answer
As mentioned on Wikipedia, there is no known proof that breaking RSA is at least as difficult as prime factorization -- and there are reasons to believe it might not be. In other words, we don't currently expect any such proof to exist. See the reference listed in Wikipedia.
> 1 votes

---
Tags: algorithms, complexity-theory, np-complete, reductions, cryptography
---


# Question
Title: What is the complexity of the following problem?
**Input:** $M$ is non deterministic Turing machine that always halts in $cn^k$ moves/steps, where $c$ and $k$ are constants and $n$ is the length of the input string of $M$, $w$ is any string in $\Sigma^\*$ and $a$ is another string in $\Sigma^\*$ where $\Sigma=\\{0,1\\}$.

**Output**: Does $a$ represent a valid computation of $M$ on $w$?

$a$ indeed encodes truth assignment, when the symbol $0$ encodes **false** value and the symbol $1$ encodes **true** value.

If $a$ **satisfies** $\Phi\_{M,w}$, where $\Phi\_{M,w}$ is the boolean formula that deterministic Turing machine can compute in polynomial time by the Cook Levin reduction that is satisfiable if and only if $M$ accepts $w$, then $a$ is indeed represents a valid computation of $M$ on $w$ since the Cook Levin reduction is **parsimonious**.

But if $a$ **falsifies** $\Phi\_{M,w}$ then this is **not** necessarily true that $a$ represents a valid computation of $M$ on $w$, because it is possible that the given non deterministic Turing machine $M$ accepts the given string $w$ on **all** computations, paths and routes and the given truth assignment $a$ still falsifies $\Phi\_{M,w}$.

So in case that $a$ falsifies $\Phi$, how do I decide whether or not $a$ represents a valid computation of $M$ on $w$?

What is the complexity of this problem?

Does exist polynomial time deterministic algorithm that decides/solves this problem or nobody doesn't know if such algorithm exist yet?

# Answer
> 0 votes
As Ariel explained in the comments:

"then $a$ indeed represents a valid computation of $M$ on $w$ since the Cook Levin reduction is parsimonious" - This has nothing to do with the reduction being parsimonious, this is a result of the specific construction of the reduction. Also, you don't have to appeal to Cook-Levin to encode computations of a Turing machine, there is no real reason to talk about assignments for boolean formulas in this context. You can simply say that $a$ is a description of $M$'s tape, state, and head location during some prefix of its computation.

Additionally, the input should consist of $M,w$ alone, you don't have any information about $M$'s running time from its encoding (how would you know if the machine actually runs in exponential time?). Now, the problem is trivially solvable in polynomial time by reading $a$ and checking that any configuration is reachable from its predecessor by one of $M$'s transition functions.

---
Tags: complexity-theory, turing-machines, reductions, satisfiability, decision-problem
---


title: What's difference between SUM and OR?

text:
# Question
Title: What's difference between SUM and OR?
While studying ALU I came across this example, now what's difference between operations of OR Gate and SUM(Adder), in binary language

# Answer
The OR and AND operations are 2-in 1-out.

An Adder is either 3-in 2-out (shown in your diagram) or 2-in 2-out (not shown). In part, because an Adder has 3 ins and 2 outs, it is composed of more underlying gates than AND and OR.

(But to be clear, it does not require new kinds of gates, the existing AND and XOR, OR, NOT gates, or the negating ones NAND, etc.. suffice.)

If we add two 16-bit numbers (not necessarily on a computer, but speaking mathematically) we get a 17-bit answer. (That we often send that answer back to 16 bits is to risk errors in our systems; and the potential for these errors require mitigation techniques, but that is off topic to this question.)

Think of base ten. In the general case, Two one-digit numbers add up to one two-digit number (though the upper digit may be zero). If we're doing long addition, we carry from one column to the next (going left). That carry going in means we're now adding 3 digits together, and the result is one digit along with a possible carry for the next column. That's why adders sometimes take 3 inputs and other times 2 inputs. The 2-input is for the least-significant-digit, whereas the 3-input is for the rest.

The last column has a carry out that is not used further, but just part of the result. This is why we get one more digit than have the inputs.

In binary the maximum inputs would be a=1, b=1, and CarryIn=1. That adds to 3 (decimal) and 3 is represented as 11 in binary. The first of those one's (from 11 in binary) is the CarryOut and the second pf those one's is the Result in your diagram.
> 1 votes

---
Tags: computer-architecture, boolean-algebra
---


# Question
Title: Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography?
In this cryptography scheme, we take $g$ and $p$ (a large prime number). and taking the customary clients Alice and Bob who chose $a$ and $b$ secretly whereas $p$ and $g$ are known in public. *I haven't mentioned the other requirements taken into consideration for selection of these parameters.*

So here is how this works:

1. Alice calculates $A = (g^a)\mod n $.
2. Bob calculates $B = (g^b)\mod n$.
3. Alice sends $A$ to Bob who then computes $(A^b)\mod n$ to get the final key. Vice-versa happens when Bob sends $B$ to Alice.
4. The end resulting keys of both Bob and Alice have to be equal.

Now, my doubt is that how come $(((g^a)\mod n)^b)\mod n = (((g^b)\mod n)^a)\mod n $ holds true?

# Answer
> 1 votes
In general, we have that $a\cdot b \mod n = (a\mod n) \cdot (b\mod n) \mod n$ for any positive integers $a,b,n$. To see this, we write $a= k n +r\_a$ and $b=ln+r\_b$, where $r\_a= a \mod n$ and $r\_b = b\mod n$. So, we get \begin{align} a\cdot b \mod n &= (kn +r\_a) (ln+r\_b) \mod n \\ &= kln^2 +knr\_b + ln r\_a + r\_ar\_b \mod n\\ &= n (kln +kr\_b + lr\_a) + r\_ar\_b \mod n\\ &= r\_ar\_b \mod n\\ &= (a\mod n) \cdot (b\mod n) \mod n \end{align}

From this, it follows that $a^b \mod n = (a\mod n)^b \mod n$ for any positive $a,b,n$. Using this equality, we can 'move' exponents through modular reductions, from which your equality follows.

---
Tags: cryptography, number-theory
---


# Question
Title: Can you give me an example word that is in the language $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $
Again, the language is $L = \\{w | w ∈ \\{a,b\\}^∗ ∧ |w|\_a = |w|\_b\\} $
Now I'm unsure about what the '\*' indicates. Whether it means that either a or b can be repeated, or only one of them or if you can repeat a pattern made of a and b.
An explanation would also be appreciated but I thought one or more examples of what would be a word in the language and what not would be quicker.

# Answer
The language $L$ contains

* all strings $w$ over the alphabet $\\{a,b\\}$ such that
* the number of $a$'s equals the number of $b$'s in $w$.

Like $aaabbb$ or $abababab$.
> 1 votes

# Answer
Check your definitions: $\*$ is the Kleene star.

So, $\\{a,b\\}^\*$ is the set of all finite strings over alphabet $\\{a,b\\}$.
> 3 votes

---
Tags: formal-languages
---


# Question
Title: How to validate a connect X game (Tick-Tak-Toe,Gomoku,...)?
Currently I am working on a Gomoku AI (or generally Connect-X games).

Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was surprised how difficult this is to make with a decent performance.

My question is what is the most efficient algorithm to check for a win in a connect-x game.

So basically I tried 2 things:

Firstly I created an Array where I saved all board coordinates (at compile time) into a 1D Array. This means all rows,cols and diagonals point for point and traversing this array and checking the corresponding on the actual board until (if any) a X long sequence was found.

My second approach was to calculate all patterns (horizontal,vertical,diagonal) with X points each at compile time (with Template-Meta-Programming) and traversing only those for each point played on so far and terminating if any member of the sequence was missing.

The first approach was way too slow and the second one was too complex for this problem I think.

What algorithm suites this problem best?

# Answer
One approach that may be useful is to represent your field by a matrix and use a matrix vector product to test whether there is a winning position. Suppose we are playing connect $3$ and are testing whether player $A$ wins by a horizontal row, in this field:

```
A A A _ B
B _ _ B _
B B _ B A
A A _ A A

```

Construct a matrix $M$ by representing player $A$'s pieces by $1$, player $B$'s pieces and empty fields by $0$:

$M = \begin{pmatrix} 1 &1&1&0&0\\ 0 &0&0&0&0\\ 0 &0&0&0&1\\ 1 &1&0&1&1\\ \end{pmatrix}$

Now, multiply the matrix by the vector $v=(1,2,4,8,16)^T$:

$Mv = (7,0,16,27)^T$. As we are looking for adjacent $1$'s, we see that there is a value in $Mv$ equal to $7$ ($=1+2+4$), $14$ ($=2+4+8$), $28$ ($=4+8+16$), $15$ (=$1+2+4+8$), $30$ ($=2+4+8+16$) or $31$ ($=1+2+4+8+16$).

Since the first entry of $Mv$ is equal to $7$, we know there is a row of three $1$'s there.

In general, for a $k\times n$ size grid, we take the vector $v=(1, 2,4,\ldots , 2^i,\ldots, 2^n)^T$ and know that there is a connected line of length at least $x$ when any of the values $\\{\sum\_{i=j}^{j+y} 2^i \mid 0\leq j \leq n-y, x\leq y\< 2x\\}$ are present in the vector $Mv$. (we can take $y\<2x$ as when $y\geq 2x+1$, there must have been a row of length $x$ already on the field)

To test for columns, we can simply take the transpose of the matrix.

To test for diagonals, rotate the field such that they become rows and add padding to construct a rectangle: e.g. given our playing field above, a rotation for a diagonal would be:

```
_ B _ _
_ _ _ _
A B A _
A _ B A
A _ _ A
_ B B _
_ B A _
_ A _ _

```

(Note that it doesn't matter whether we place the padding to the left or the right, as we only check rows)
> 1 votes

---
Tags: algorithms, artificial-intelligence, search-trees, board-games, computer-games
---


title: CFG to PDA - no empty transitions

text:
# Question
Title: CFG to PDA - no empty transitions
Working for my exam, this question popped up.

> Given the production rules below, draw a pushdown automaton to recognise the language it generates:
> S → AB
> A → BA
> B → BB
> B → T
> T → b

Questions:
1. Since A has no empty transition, wouldn't this just end up in an infinite loop?
2. What order are the values entered into the stack.
If first you enter S, would it then be B at top of the stack and A at bottom or the other way around?
3. Below is my current interpretation of the PDA. Is it correct? Or does the question ask for the transition table?

# Answer
> 1 votes
This grammar will in fact get into an infinite loop because there is no transition for A to turn into a terminal.

---
Tags: automata, context-free, formal-grammars, pushdown-automata, simulation
---


# Question
Title: How does a buffer overrun corrupt the return address?
I got stuck on the following note while reading a paper about computer security:

> The **stack mixes program data and control data**
>
> – by overrunning buffers on the stack we can corrupt the return addresses!

In fact, I didn't understand how a buffer overrun corrupts the return address within a stack frame. Also the use of the term `buffers` was not very clear to me - what do they mean?

# Answer
> 1 votes
When your code calls a function, the called function usually allocates memory for its variables, just before the memory where the return address is stored (the address of the caller).

Let's say you have an array int a\[100\], and a double variable x. The compiler may quite reasonably allocate memory for x either just before or just after the memory for a. In the first case, setting a \[-1\] = 100; a \[-2\] = 1000; will likely change x. In the latter case, setting a \[100\] = 100; a \[101\] = 1000; will do the same thing. Trying to store into an array, using an index that is too small or too large, is called a "buffer overflow".

Now if you store a \[102\] = 0; or a \[103\] = 0; then chances are that this overwrites the memory where the caller's return address was stored. And if the function tries to return, the processor will start running code at the address that you stored into a \[102\] and a \[103\] with all kinds of negative consequences.

---
Tags: operating-systems, memory-management, virtual-memory, security
---


# Question
Title: How do I tell if $G$ is a forest in log-space?
How does to prove that language $$\textbf{X} = \\{G \mid\text{ all connected connected components in $G$ are trees}\\} \in \textbf{L}\\,?$$ I know how to prove that language of undirected trees is in $\textbf{L}$ but I don't know what to do next.

# Answer
> 0 votes
Using Reingold's algorithm, you can count the number of connected components in a graph. For example, you can count the number of vertices which have the minimal index in their connected component (assuming some arbitrary ordering of the vertices), that is, the number of vertices $i$ that are not connected to any $j \< i$.

Now use the following criterion: A graph contains a cycle iff there is an edge whose removal does not increase the number of connected components.

---
Tags: complexity-theory
---


# Question
Title: Why would this be a deterministic context free language? $L = \{a^n b^n | n>0 \}$ $\cup$ $\{ a^n b^{2n} | n < 100 \}$
so the book that I'm reading says this is a deterministic context free language $L = \\{a^n b^n | n\>0 \\}$ $\cup$ $\\{ a^n b^{2n} | n \< 100 \\}$

But i think this is wrong Because :

at the beginning of building the DPDA, we have to decide whether we should go with the first one or the second, and considering both of them start with a there is just no way we could build a DPDA right?? or am i wrong?

i also tried solving this by first building the $a^nb^n$ and then going for the second one if the stack is not empty, but still couldn't come up with anything, i tried putting 2 a's for every a input but didn't work

so how is the book saying this can be build with a DPDA?

Also i have to say I KNOW that non infinite languages are regular, but this one is not infinite!

# Answer
Maybe you can create 100 states that push two $a$'s onto the stack for every $a$, and then pop these $a$'s for every $b$. In the event of getting to the 100th state, when you read the 101st $a$, pop 100 $b$s from the stack and continue as you would for the first language alone.
> 1 votes

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