# Question
Title: In what situations should a particular sorting algorithm, such as heap sort, be chosen over others?
In my algorithm class my teacher said that we should always use counting sort when we want to sort integers. After he said this I was curious to know in which situations I should choose one sort algorithm over another.

Looking at the complexities of the worst cases of the algorithms I know (heapsort, mergesort, quicksort and countingsort), excentuating the case where I want to sort integers, I will choose mergesort when I want a stable sorting algorithm or I will choose heapsort when I want to save memory.

Searching a little I found flashsort, but I still do not understand very well when I should implement it instead of others. Since I am beginning to study algorithms, I would like to know at this initial moment when a sort algorithm is preferable over others.

# Answer
> 5 votes
Most programming language standard libraries come equipped with one or more built-in sort routines these days. Most of the time, that's what you want.

"Library sort" algorithms tend to use a combination of basic sort algorithms that you've seen in class, and tune themselves either at compile time or at run time.

That's why, for example, the standard library sort in C++ might use merge sort on linked lists and quick sort on arrays. And a typical industrial-strength quick sort implementation will revert to insertion sort on small intervals, or heap sort if the partitioning strategy seems to be going awry.

Most library sorts are comparison-based because of external constraints. They must work on user-defined data types, for example, and it's typically much easier for the user of such a sort algorithm to supply a comparison operation than, say, a radix extraction operation. Moreover, users often want to sort on secondary keys if primary keys are equal (e.g. surname then first name). It's much easier to express this in terms of comparison rather than some other formulation.

I've been in the business a long time, and there's really only a few times I can think of where writing my own sort was the best option. Two examples that are easy to explain:

First example: I wrote the sort subsystem for a database server. It me about six months. As with library sorts, it used a combination of sort algorithms and adjusted its behaviour depending on what situation it found itself in. Sorting database records is an interesting case because accessing the sort key is sometimes the most expensive operation; disk seeks are one of the most expensive things there is, especially if the disk is network-attached.

The main idea which cracked this problem was to use the fact that users almost always wanted to sort on multiple keys. So I used partitioning sort algorithms which discovered "ranges" where the primary sort key was the same. Secondary keys are only needed to resolve those ranges. Many sort algorithms (e.g. ternary quick sort, radix sort) can be adapted to return ranges.

Second example: I wrote some firmware which needed to read about 1000 values from a hardware device, and then do quantile extraction. The complication is that the microcontroller that this ran on had essentially no extra read-write memory available, so algorithms like radix sort or quick sort were not an option. I used Shell sort, which was by far the best tradeoff.

There's a bunch of special-case information that everyone who has worked with sorting knows, such as "bubble sort is always worse than insertion sort", and "heap sort has terrible constant factors; last resort only". But this general advice is probably all you need to know:

1. The best sort algorithm is the one that fits the peculiarities of your data and your platform.
2. The second-best sort algorithm is one you didn't have to write.
3. Make sure that sort is a bottleneck before getting fancy.

Knowing lots of sort algorithms is good for you, but not necessarily to the point where you can implement them from memory. Knowing that there *is* a tradeoff is more valuable knowledge than what the tradeoffs actually are. Then, when you come across one of those few times where you need to write your own sort, you'll know where to look.

# Answer
> 0 votes
Your question "*when a sort algorithm is preferable over others.*" is somewhat broad, and maybe opinion-based. You could answer this question by reading about each sort algorithm. Usually textbooks (or articles such as on Wikipedia) discuss when and in which situations a certain algorithm more preferable over others.

Nevertheless, counting sort algorithm, unlike comparison based ones (such as Quick Sort or Merge Sort) runs in linear time, but at some cost. The keys are assumed to be non-negative integers. Time complexity of this algorithm is $O(a\_{max} - a\_{min})$ and so this algorithm is suitable only when $a\_{max} - a\_{min} \approx N $, where $N$ is the number keys. This article provides more detailed information. And this discusses the flash sort algorithm.

---
Tags: algorithms, sorting
---


# Question
Title: Is $G_2(V_2,E_2)$ a subgraph of $G_1(V_1,E_1)$ given number of vertices and adjacency matrix for both?
Given $n\_1$ and $n\_2$ number of verteces and the adjacency matrix for both graphs, one should determine whether $G\_2$ is a subgraph of $G\_1$.

I am supposed to use C++ for this, and though I could probably come out with a solution including $20$ for functions, it's most likely not the best approach to the exercise.

Do I have to(?):

* Assume the graphs have $n\_2$ common vertices (because this has to be in order for $G\_2$ to be a subgraph of $G\_1$, right?)
* Check to see if any of the $\begin{pmatrix}n\_1\\ n\_1-n\_2\end{pmatrix}$ possibly resulting graphs after the removal of $n\_1-n\_2$ vertices from $G\_1$ is equal to $G\_2$

Althogh not sure how to compute the above.

This must be an easy exercise since it's for beginners in graphs, but I guess there's just something I am missing. Could you give me some hints on how to approach this in a better way? I've looked for this one a while, hopefully it's not a duplicate.

# Answer
This problem is more general form of the graph isomorphism problem. No polynomial time algorithm is known solving it. The state of the art suggests possible approaches.
> 0 votes

---
Tags: algorithms, graphs
---


title: Why is the language $NP-hard$?

text:
# Question
Title: Why is the language $NP-hard$?
Let's denote $IS(G)$ to be the size of the maximal independent set in $G$. Consider the following language: $$A = \left \\{ G\ |\ IS(G)\ge \frac{1}{5}n \right \\}$$

I know that $gap-IS \[1/8 + \varepsilon , 1/4-\varepsilon\]$ is $NP$-hard.

How can I infer that $A$ is $NP$-hard by utilizing the gap problem?

# Answer
> 1 votes
You reduce $\text{gap-IS}\[1/8+\epsilon,1/4-\epsilon\]$ (for any $\epsilon \< 1/20$) to $A$. The reduction is the identity function. Let's see why it works:

* If a graph $G$ is a YES instance of $\text{gap-IS}\[1/8+\epsilon,1/4-\epsilon\]$ then it has an independent set of size at least $(1/4-\epsilon)n \geq n/5$.
* If a graph $G$ is a NO instance of $\text{gap-IS}\[1/8+\epsilon,1/4-\epsilon\]$ then it has no independent set of size $(1/8+\epsilon)n \< n/5$.

Hence a graph $G$ is a YES instance of $\text{gap-IS}\[1/8+\epsilon,1/4-\epsilon\]$ if and only if it is a YES instance of $A$.

---
Tags: complexity-theory, reductions, np-hard
---


# Question
Title: Does the specific size of matrices affect the performance of matrix operations?
I was reading DeepMind's paper on I2A's and realized that the sizes of the hidden layers in their model were all like 32, 64, 256, and so on: all powers of 2. I have found the same thing in other papers.

Is there any performance reason for it? Maybe related to data structure alignment?

More concretely, I would like to know if I should use this "special" sizes when training my own models.

# Answer
> 1 votes
While you can only be 100% certain when you ask the authors, most authors use this simply because you have to choose one value. The specific value doesn't matter too much, only the order of magnitude. Taking a power of 2 seems to be a natural choice.

You can also take a setup which uses a power of two and reduce the number by one. The computation time should be roughly equal, probably be a bit lower. If it is noticeably higher, there might be a performance benefit of using the choice of the author.

## See also

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


title: Master Theorem Usage

text:
# Question
Title: Master Theorem Usage
I know how to use the master Theorem for a general formula e.g. $T(n) = a \cdot T(\frac{n}{b}) + f(n)$.

I saw some books suggest that we can use the mastere theorem for formulas like: $T(n) = T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n)$

How is that possible?

My guess: We use it separately. Once for $T(n) = T(\frac{n}{5}) + O(n)$ and once for $T(n) = T(\frac{7n}{10}) + O(n)$ and join between.

Thanks!

# Answer
You can use the idea of the Master Theorem and apply it to these occurrences. That is what I have done here, I would recommend looking at that answer because it will answer your question.

Basically we can look at the fractional terms inside the recurrence calls. If the sum to less than $n$, then the "conquer" part of "divide-and-conquer" will dominate the "divide" part.

For your example we have the fractions: $\frac{n}{5} + \frac{7n}{10} = \frac{9n}{10} \< n$. Therefore the $O(n)$ term will dominate and the overall time complexity will be $\Theta(n)$. This is an idea of the Master Theorem, figuring out which dominates: "divide" or "conquer". Again, I highly suggest looking at this answer for a more in-depth proof.
> 1 votes

---
Tags: recurrence-relation, master-theorem
---


title: The Church-Turing-Thesis in proofs

text:
# Question
Title: The Church-Turing-Thesis in proofs
Currently I'm trying to understand a proof of the statement:

"A language is semi-decidable if and only if some enumerator enumerates it."

that we did in my lecture. One direction of the proof goes as follows:

---

Let E be an enumerator that enumerates L. We construct a TM M, that semidecides L in the following way:

Given an input string x, we design M in the following way :

1. Run E to enumerate the next string y of L. Compare it with x.
2. If x=y accept, else goto 1

---

Am I right if I say, that it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis? Furthermore is there anything to take care of when constructing an algorithm in such a context as not to hurt the "definition" of intuitively computable?

Thanks for any answers.

# Answer
> 5 votes
A Turing machine provides a formal definition of a "computable" function, while the Church-Turing-Thesis says that intuitive notion of "computable" coincides with the formal definition of "computable", i.e., all functions computable by TMs. This is just a hypothesis, and it is up to you to believe or not.

When we describe a procedure in order to show that some function is computable (or problem is solvable) we usually describe it at a high level, to avoid long and tedious rigorous formal details. So, you are right that "it is sufficient to just name an algorithm to prove the existence of such a TM M because of the Church-Turing-Thesis". In other words, first we informally describe a procedure using English, and then since we believe in correctness of the the Church-Turing-Thesis we conclude that the function is computable.

Another example is computing $\pi(n)-$ the $n$th digit of the decimal expansion of $\pi$. Intuitively, we can draw a circle, measure its circumference and radius, and divide the circumference by two times the radius. But this method is not suitable to implement on a computer. The Turing-Church thesis says this function is indeed computable on a Turing machine. For example, $\pi(n)$ might be computed using Taylor series.

As for the wrong usage of the thesis, usually the error may lay in a wrong assumption. For example, the following wrong procedure may seem to decide the Halting problem:

```
Let L be the Halting Problem language
IsHalt(W,w)
  Recursively enumerate elements of L and complement of L
  and process one element from each set at a time
  If <W,w> is in one of them then depending in what set <W,w> is
  return true or false

```

Since we loop on both $L$ and $\overline{L}$, and we enumerate each element of these sets, the procedure eventually must halt with true or false. But the wrong part is that we assumed the $\overline{L}$ is r.e.

---
Tags: computability, turing-machines, proof-techniques, semi-decidability, church-turing-thesis
---


# Question
Title: Should crossover operation in a genetic algorithm modify individuals in order to be "valid"?
I'm working in a project to create levels for a videogame using genetic algorithms.

I'm using a undirected graph to represent the level, each node represent a room and each room have a maximum of four possible connections (north, south, east, west). Also each connection just have one compatible connection (North \<=\> South , East \<=\> West), this mean you can't connect North with East for example, or North with North (Also a room can't be connected with itself).

Anyway, I already have a way to create the initial population with thoses restrictions, but now I'm thinking about the crossover function.

Let's say I crossover two graphs by cutting them in half and merging those halves, there are chances for a room to have more than four connection or using the same connection to connect two differents rooms.

So my question is, Should I create a crossover method to respect thoses restrictions or just to lower the score of thoses individuals?

# Answer
In my experience, a well crafted operator that avoids or repairs constraint violations is nearly always far preferable to one that relies on selection alone to find feasible solutions.
> 1 votes

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: If you increase the address space for an OS, does the Phys Mem used by the program increase?
I am learning about the OS.

I know: that Address Space Size = # of pages x page size

So if I increase Address Space Size, then the number of pages increases:(not the page size). However, isn't the Virtual Page Number a one-for-one mapping to Physical Page Numbers(frames), so if the number of pages increases with the address space doesn't the frames and hence, the size of RAM used increase with address space increases?

Or, does bigger address space cause more physical frames so each frames physical memory size reduces as total memory is split among more frames.

# Answer
> 2 votes
No. Due to the way virtual memory works, you can have more virtual pages than physical pages (frames). Some virtual pages might not be mapped to any physical page.

It doesn't really make sense to talk about "if you increase the address space size, the number of pages increases". It might be slightly more useful to think of it as "if you increase the number of pages, the address space size increases".

But really, in any given architecture, the address space size is often fixed and cannot be modified: the size of a virtual address is fixed and cannot be changed, and that determines the number of pages and thus the maximum size of the available virtual address space.

# Answer
> 1 votes
> I know: that Address Space Size = # of pages x page size

First note that different hardware behaves differently here:

The 80286 CPU did not know about "pages" at all, the ARM250 CPU had a configurable page size while the 80386 CPU has a fixed page size (4096 bytes).

In the rest of the text I'm assuming you are talking about the 80386 case because nearly all modern x86 OSs use this.

> However, isn't the Virtual Page Number a one-for-one mapping to Physical Page Numbers

Yes and no:

One virtual page (4096 bytes) corresponds to one physical page (4096 bytes) which means that there is an 1:1 mapping.

However virtual pages have a "present" flag and a "read-only" flag and multiple virtual pages can be mapped to the same physical page.

This is used for the following mechanisms:

If the **"present" flag** is not set then a virtual page is not mapped to any physical page. This means any attempt to access this page will cause the CPU to notify the OS **before** the instruction accessing the memory is executed.

(Btw.: This mechanism is responsible for the crash of a C program when accessing the NULL pointer.)

If your program allocates memory many OSs will not really do anything but the OS will only "remember" that certain virtual memory pages **can** be used by the program. As soon as the CPU notifies the OS about an attempt to access the page the OS will assign a physical page to the virtual page.

The **"read-only" flag** is used for a mechanism that is called "copy on write":

In many cases there is the probability that two pages contain exactly the same data. Under Linux/Unix this is the case when using the `fork()` command; using shared libraries (`.so` or `.dll`) under any OS (Linux/Unix/Windows/...) is another example.

In such a case the OS will map the virtual pages containing the same data to the same physical page: Because they contain the same data only one page in RAM is needed.

If the program makes the attempt to write to one of these pages the OS is notified (due to the "read-only" flag). The OS will then take a free physical page, make a copy of the original physical page and then map the virtual page to the physical page containing the copy.

---
Tags: operating-systems, memory-management, virtual-memory, paging, memory-allocation
---


title: Solving $T(n) = 4T(n/2) + n^2log_2(n)$

text:
# Question
Title: Solving $T(n) = 4T(n/2) + n^2log_2(n)$
My first thought was using the third case of the master theorem, but I am not sure if I can use $\epsilon \rightarrow 0$, so $f(n) \in \Omega(n^{log\_2^4+\epsilon})$.

Otherwise, I tried solving the equation by iteration where I got $T(n) \in \Theta(n^2log\_2^3n)$ instead of $T(n) \in \Theta(n^2log\_2n)$.

Which solution is right and why? Thanks.

# Answer
When you applied the master theorem, f(n) is n^2 right. This is anyways asymptotically lesser than O(n) which is the n^2log(n). Hence at each node of the recursion tree, the O(n) would dominate computation hence T(n) is O(n). The reason why this is true is because when you apply the recursion tree the number of processes at each node if you calculate would be 2O(n/2)+4O(n/4)...... whose sum turns out to be lesser than O(n).
> -1 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Data Searching from a large data set without reading each element
I have just started learning algorithms and data structures and I came by an interesting problem.
I need some help in solving the problem.

There is a data set given to me. Within the data set are characters and a number associated with each of them. I have to evaluate the sum of the largest numbers associated with each of the present characters. The list is not sorted by characters however groups of each character are repeated with no further instance of that character in the data set. Moreover, the largest number associated with each character in the data set always appears at the largest position of reference of that character in the data set. We know the length of the entire data set and we can get retrieve the data by specifying the line number associated with that data set.
For Eg.
C-7
C-9
C-12
D-1
D-8
A-3
M-67
M-78
M-90
M-91
M-92
K-4
K-7
K-10
L-13
length=15
get(3)= D-1(stores in class with character D and value 1)
The answer for the above should be 13+10+92+3+8+12 as they are the highest numbers associated with L,K,M,A,D,C respectively.
The simplest solution is, of course, to go through all of the elements but what is the most efficient algorithm(reading the data set lesser than the length of the data set)?

# Answer
> 3 votes
Say you have $n$ entries, $m$ distinct letters, and the $i$-th letter occurs $k\_i$ times. You can find the last occurrence of the $i$-th letter using a variant of binary search: Double your step size until you find a different letter (or run out of the array), do binary search between your last and second-to-last step. This takes about $2\log k\_i$ many steps. So in total you need about

$$\sum\_{i=1}^m \log k\_i = \log \prod\_{i=1}^{m} k\_i$$

many steps. That product is biggest when all terms are equal, so you have something like $m\log (n/m)$ many steps.

Naively implemented, this is not always better than looking at all elements though. If you work out all the details, you'll see that for example when $m=n$ you have to be a bit careful.

---
Tags: algorithms, data-structures, optimization, data-mining
---


title: Why product type is a dependent SUM?

text:
# Question
Title: Why product type is a dependent SUM?
It might just be a stupid question but I simply see no obvious reason why dependent sum type is a generalized form of product type. Concretely, the sigma type $\Sigma(x:S)T$ degenerates to a product type if $T$ does not depend on $x$ and is expressed to be $S\times T$ in this case.

Where the SUM part in dependent sum type is coming from? Also, the type of dependent functions is called dependent PRODUCT type. Might I ask why it's called product type as well? I kind of sense that it has something to do with algebraic data type but I can't get through it.

# Answer
> 18 votes
Let's do products first. The usual cartesian product $A \times B$ is also called a *binary* product because we are making a product of *two* sets. We could make a ternary product $A \times B \times C$. What is the most general case? Well, to have an index set $I$ and a family of sets $X\_i$, one for each $i \in I$, and then we make the product of all these $X\_i$'s. This is written as $\prod\_{i \in I} X\_i$. When $I$ is infinite, it is called an infinitary product. Other products are a special case, for example if we take $I = \\{1, 2\\}$, $X\_1 = A$ and $X\_2 = B$ then $\prod\_{i \in \\{1,2\\}} X\_i = A \times B$, so a binary product is a special case of the general product.

We can do the previous paragraph in type theory, as there is nothing specific to sets there. Given a type family $i : I \vdash X(i) \ \mathsf{type}$, we may form the type $\prod (i : I) X(i)$. To get a binary product $A \times B$ as a special case, take $I = \mathsf{Bool}$, set $X(\mathsf{false}) = A$ and $X(\mathsf{true}) = B$.

Now let's try sums. I will assume you understand the sum of two sets or types, $A + B$. We could have a ternary sum, $A + B + C$. Again, there is a general case: take a family of sets $(X\_i)\_{i \in I}$ and form their disjoint sum, or coproduct. In set theory it is written as $\coprod\_{i \in I} X\_i$, while in type theory it is written as $\sum (i : I) X(i)$ and called *dependent sum*. One way to see why people call it a sum is to consider how many elements it has. If $A$ has $a$ elements and $B$ has $b$ elements, then $A + B$ has $a + b$ elements. In general, if $X\_i$ has $x\_i$ elements, then $\sum (i : I) X\_i$ has $\sum\_i x\_i$ elements.

We saw that the binary product is a special case of a general product. But it is *also* a special case of a dependent sum. Suppose $A = \\{0, 1, 2\\}$. Then $A \times B = B + B + B$. In general, if we want $A$-many copies of $B$, then that's $$A \times B = \underbrace{B + B + \cdots + B}\_{A}$$ Of course, such notation is silly, so we prefer to take $I = A$ and $X\_i = B$ and then the same thing is written as $$A \times B = \sum\_{i \in I} X\_i$$ or to confuse beginners $$A \times B = \sum\_{a \in A} B.$$ This just says that $A$ times $B$ is the same thing as adding $A$-many $B$'s together. It's the first thing we're told about multiplication, except that here it's about sets, not numbers (but that's irrelevant, really).

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


# Question
Title: Is a Knapsack Problem with only Color Constraints NP-Complete?
I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors.

There exists a constraint on the number of different colors of objects in the knapsack (but no "weight" constraint), and the goal is to maximize the value of the knapsack.

It's basically the same setting as in this model http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.9533&rep=rep1&type=pdf except that there is only one knapsack and the items are "weightless".

Is this problem hard, easy, yet to be classified? I would really appreciate any pointers. Please and thank you in advance.

# Answer
> 2 votes
So, items have only 2 parameters:

1. Color. I assume that each item has one color ("**one** of C colors"). If not, this problem is probably $\mathsf{NP}$-hard.
2. Price.

Now we need to pack a knapsack to maximize the price. Knapsack can have at most $k$ colors.

Algorithm:

1. For each color count the total price of items that are colored by color $C\_i$. Call these values $P\_i$. Takes linear time.
2. Find $k$ maximal values of $P$. Takes polynomial (linear?) time. Can be done using sorting.

This is the answer.

# Answer
> 0 votes
> Trying all combinations of k colors must be doable in O(n^k+1) time, isn't it?

No, I think that would be factorial in C. There are ${C}\choose{k}$ different combinations of k colors (the number of subsets of k colors to choose from a set of C colors).

> Each item has only one color or can be multiple-colored?

Yes, each item has only one color and thank you very much for your excellent answer. That's what I was looking for!

PS. I am still figuring out my way around the forum so I don't know yet how to reply directly.

---
Tags: complexity-theory, np-complete, decision-problem, knapsack-problems, colorings
---


# Question
Title: How append, prepend, and generally insertAt work in RRB-tree
I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient in this data structure describe this procedure?

# Answer
> 5 votes
Currently there's no "magic trick" to do an insertAt for RRB-trees: It can be implemented by doing

```
concat(append(leftSlice(rrb, i), elt), rightSlice(rrb, i))

```

Append can (as I've shown in my thesis) be very efficient. If you don't want to focus on transients and tails, then chapter 5 explains how you modify the persistent vector append algorithm to work for RRB-trees. In short, you have to first find the path to walk, then walk and update it just as in the persistent vector, but in addition you have to update the slot sizes.

Prepend is simply a special case of concatenation.

# Answer
> 1 votes
How cool is it to be in a field and an age where Jean Niklas L'orange can answer your questions? That's a great response!

Another approach to consider is to localize the "focus". The focus is analogous to the "tail" in Rich Hickey's PersistentVector. It's a little buffer to take new items added to the vector without having to update the tree for each of those items. The difference being that the tail always comes at the end and the focus can move around.

If inserts are localized (meaning each insert is within a few indices of the previous) you can simply move the focus to where the inserts are happening. This can be great for building a tree by inserting at zero. The "insert(0)" tab of this spreadsheet shows a few RRB-Tree implementations kicking java.util.ArrayList's butt, above 100 items. Both axes are logarithmic.

It's worth noting that you can often wait until the focus is the size of the strict-node-length and push it into the tree without copying it. This means you never have to deal with any non-full leaf node in a strict tree, or too-small node in a relaxed tree.

---
Tags: trees, persistent-data-structure
---


# Question
Title: What is the importance of disjoint edges in k-opt algorithms?
I'm trying to implement a k-opt algorithm and I'm bogged down on a detail: the importance of choosing disjoint edges.

My question: Is there any benefit to considering adjacent edges, or is the full power of the heuristic achieved when only disjoint edges are considered?

Wikipedia seems confused on this question. Its description of k-opt explicitly says "k mutually disjoint edges", but then it describes 2-opt and 2.5-opt as special cases of k-opt, and describes both those algorithms as processing adjacent edges. Is there something I'm not understanding here?

# Answer
> 1 votes
I have a partial answer to my own question. I believe there is a benefit to considering adjacent edges. The full power of the heuristic is not achieved when only disjoint edges are considered.

To arrive at this conclusion, I implemented two versions of the 4-opt algorithm in C#. One version considers only disjoint edges and the other considers both disjoint and adjacent edges. Then, I used both algorithms to solve the Travelling Salesman problem for 1000 scenarios of 25 nodes each.

The two algorithms found the same solution 52.7% of the time. The disjoint+adjacent algorithm found a better solution than the disjoint-only algorithm 45.7% of the time. The disjoint-only algorithm found a better solution than the disjoint+adjacent algorithm 1.6% of the time.

The disjoint+adjacent algorithm found tours that were, on average, 99.1% of the length of the tours found by the disjoint-only algorithm.

Based on these results, I'm fairly confident that there is a benefit to exploring adjacent edges in the k-opt algorithm.

I call this a partial answer because I'm not yet clear on whether it is efficient to explore adjacent edges. Yes, exploring adjacent edges in my experiment improved the tour length by an average of 0.9%, but perhaps I could have improved the tour length more than that by using the same computing effort exploring some 5-opt steps instead.

My experimentation suggests that it is optimal to first explore 2-opt steps, then to explore 3-opt steps that include adjacent edges, then to explore 3-opt steps that include no adjacent edges, then to explore 4-opt steps that include adjacent edges, then to explore 4-opt steps that include no adjacent edges, etc. However, that is preliminary speculation. If anyone knows of k-opt documentation that covers this level of detail, please let me know about it.

# Answer
> 0 votes
Of course, the k edges must bu non-connected. k-opt aims to cut a tour (in the Traveling Salesman case) into k parts by removing k edges and then reconnect these parts so that the output is a tour different from the first one and must be **feasible**.

Let's take the example of 2-opt and the following tour *T: \[1,2,3,4,5,6,7,8,9,10\]*.
One of the possibilities is to cut the tour from the edges (2,3)&(6,7) and connect (2) with (6) and (3) with (7), the obtained tour will be *\[1,2,6,5,4,3,7,8,9,10\]*.
Choosing for example (2,3)&(3,4) will lead to an infeasible tour: the two edges must be composed by four different nodes/cities.

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


# Question
Title: Strongly connected and completely specified Moore equivalent of a Mealy Machine
Problem: Prove that if a Mealy machine is strongly connected and completely specified, the corresponding Moore machine will also be strongly connected and completely specified.

My approach so far:

As the Mealy Machine is completely specified, we have 2 cases for each state:

1. All transitions coming into this state have the same output.
2. At least 2 transitions coming into this state have different outputs.

For case 1: The equivalent for this state would simply be changing the notation, i.e. mark all transitions into this state simply by the input symbols and just mention the output with the state as is.

Now, as the machine is completely specified, each such input transition and it's corresponding output will be defined, and the states resulting due to such states will also have completely specified transitions.

For case 2: The equivalent for such a state requires the 'splitting'/addition of new states such that each 'split' state corresponds to the different outputs that can be generated. We split a state into a 2 corresponding states.

Now, as the machine is completely specified, each such input transition and it's corresponding output will be defined, and the states resulting due to such states will also have completely specified transitions.

*Strongly Connected Machine*: If for any two states $S\_i, S\_j$ of the machine, there exists a finite sequence of input characters that can make the machine transition from $S\_i$ to $S\_j$, the machine is strongly connected.

*Completely Specified Machine*: Consider $M = (I,O,S,F,Z)$

* $I:$ Input Symbols
* $O:$ Output Symbols
* $S:$ Set of States
* $F:$ Transition function $F: S\times I \rightarrow S$
* $Z:$ Output function
* $Z: S \rightarrow O $ (Moore)
* $Z:$ $S\times I \rightarrow O$ (Mealy)

Now, if for every $(p,x)$ such that $(p \in S, x \in I)$ there exist some $q \in S$ and $y \in O$ such that $F(p,x) = q$ and $Z(p,x) = y$ (Mealy), $Z(p) = y$ (Moore)

**My Question:**

I'm having a hard time trying to formally prove the above while I can see it is true with the above intuition. I can similarly say that if the mealy machine was strongly connected, even after replacing it with 1(or 2) states, it would most definitely still be strongly connected. I was looking for help on formalising this above approach or a more solid proof on this.

# Answer
Let $M\_1 = \langle Q, \Sigma, \Delta, \delta, \lambda, q\_0 \rangle $ be a Mealy machine where $\Delta$ is the output alphabet and $\lambda$ is the output function.

Let us denote states of the corresponding Moore machine by $q\_{ib}$ if there is input $a$ and output $b$ such that $\delta(q\_j, a) = (q\_i, b)$. This means if the Mealy machine enters a state $q$ by emitting more than two different outputs then the state $q\_i$ "splits". Also, denote corresponding Moore machine's transition function by $\delta'$.

Now consider two states $q\_{ib\_1}$ and $q\_{jb\_2}$ (of corresponding Moore machine). Existence of the state $q\_{jb\_2}$ implies that there is a state $q\_k$ and input symbol $a$ such that $\delta(q\_k, a) = (q\_j, b\_2)$. Since we made assumption that the Mealy machine is strongly connected, there is a string $w$ such that $\delta(q\_i, w) = (q\_k, b\_k)$ for some output symbol $b\_k$. So, we have $$\delta'(q\_{ib\_1}, wa) = \delta'(\delta'(q\_{ib\_1}, w),a) = \delta'(q\_{kb\_k}, a) = q\_{jb\_2}$$ This shows that the corresponding Moore machine is also strongly connected.

As for the completely specification, let $q\_{ib\_1}$ be a state of the Moore machine, and $a$ is an input symbol. Then $\delta'(q\_{ib\_1}, a)= (q\_{jb\_2}, b\_2)$, where $\delta(q\_i, a) = (q\_j, b\_2)$, which shows it is completely specified.
> 0 votes

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


# Question
Title: Understanding basic operation of TM and FA
As turing machine always halts on **dead configuration**,so consider the case where it halts in final state,if on second last state by reading an input alphabet it comes to final state. Now in final state it will try to find the transition for the next symbol(i.e blank) and as there will be no transition on final state so machine will halt/dead in final and we can say string is accepted.

If i consider the case of Finite automate,now FA reaches the final state and the next is blank then we say machine will stop and string is accepted.But this is not **dead configuration**.

But in both cases the input is coming from tape and in case of FA ,it will halt when blank comes on tape and there is no dead configuration.But same behaviour in TM is having dead configuration behaviour.

Can someone please explain the difference in these two case from point of dead configuration.?

P.S:- By dead configuration,i mean that transition on the state is not defined for given alphabet

# Answer
> 2 votes
Turing machines (and RAM machines) and (most) finite automata operate in two different input models. Finite automata usually accept their input in a streaming fashion: they read one input symbol, do something, read another input symbol, do something, and so on. When the input is exhausted, they report their output. Turing machines, in contrast, get all their input on the input tape, and then do whatever processing they wish. They don't have to stop after they have scanned the entire input.

This difference in the input model explains the different semantics you have indicated. There are, however, finite automata which have input semantics similar to a Turing machine, namely two-way finite automata. Although behaving superficially like Turing machines, they are equivalent in power to deterministic finite automata (DFAs).

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


# Question
Title: In Amortized Analysis, can we chose how big $n$ is?
Suppose I want to show by contradiction that the amortized cost of a data structure with some operations cannot be **less** then $\Theta(k)$. I assume for the sake of contradiction that it is possible. Can I then choose an $n$, large enough, and a special sequence of operations and show that they take $\Theta(nk)$ and conclude that the amortized cost has to be at least $\Theta(k)$? Or does my counter example must be for any chosen size of $n$ sequences?

In other words, I want to show that for any large $n$ that satisfies $\frac{n}{2}\>2^k-1$, the counter example works. Is this sufficient?

Edit: To show what I mean here is an example: I have a binary counter that supports the option INCREMENT and DECREMENT. It starts at all zeros at the start. I wanna show that the ammortized cost cannot be less than $\Theta(k)$.

So I assume the opposite. And I first do $2^k$ increment operations so that I have \[1(k-1 zeros)\] as the binary counter. Then I do $m$ DEC INC operations in succession where each of them will take $\Theta(k)$.

here we have $n=2^k+m$. Choosing $m=2^k$, we get $n=2^{k+1}$ so $m=\Theta(n)$. So we get total amount of work $\geq km=k\Theta(n)=\Theta(nk)$ so the amortized time is $\Omega(k)$.

**However, the above argument only holds if $n\geq 2^{k+1}$, does this constitute a proof?**

# Answer
It depends a bit on what you mean with "choose an $n$". If you pick a fixed $n$, say a million, then no, that's not enough. Asymptotic notation already means "for sufficiently large inputs, the runtime is...". So a counterexample of any fixed size won't do.

If however you show a method that for an infinite number of sufficiently large $n$ produces a counterexample, then this is valid.
> 1 votes

---
Tags: algorithm-analysis, amortized-analysis
---


title: Shortest Path using at most k colors

text:
# Question
Title: Shortest Path using at most k colors
I have an edge-colored network, in which edges also have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the number of colors of edges in a path should not exceed an integer $k$.

It corresponds to finding shortest Paths on a multimodal network, with the only restriction being a limitation in the number of changes of modes allowed (e.g. different bus lines, and no more than three changes of bus).

I am trying to determine the complexity of this problem.

I have found a line of research combining graph theory and formal languages theory \[1\], which is interested in the more general problem of paths constrained by the fact that the word formed by the labels of a path belongs to a certain formal language. Theorems state that:

1. The problem is in $P$ if the above language is context-free.
2. It is $NP$-hard for regular languages.

So alternatively, my question could be stated as follows:

Is a language over a finite alphabet, in which words can be of any length, but have to use a limited number $k$ of different letters, regular or is it context-free? E.g. the language of words using at most four latin letters. "HELLO" is okay but "HELPS" is not. Is this regular or context-free?

I would appreciate any pointers to literature discussing the problem in either form (but would really prefer a purely graph-theoretic proof of NP-hardness or polynomial algorithm). Otherwise, I guess I will have to invest a few weeks learning about formal languages.

Thank you in advance. The help I have received so far in this forum is outstanding.

\[1\] Barrett, C. et al. 2000. Formal-language-constrained Path problems. SIAM journal of computing. Vol. 30, No. 3, pp 809-837.

# Answer
Here is a reduction from SAT to your problem. Let $\phi = C\_1 \land \cdots \land C\_m$ be a CNF on the variables $x\_1,\ldots,x\_n$. Consider the following graph with parallel edges (those can be easily eliminated if need be). There is a vertex for each variable and each clause, and additionally there are is a vertex $s$. There are $2n$ colors, one per literal, and we will choose $k := n$. The edges are:

1. From $s$ to $x\_1$ there are two edges, colored $x\_1$ and $\lnot x\_1$.
2. From $x\_{i-1}$ to $x\_i$ there are two edges, colored $x\_i$ and $\lnot x\_i$.
3. From $x\_n$ to $C\_1$ there is an edge per literal in $C\_1$, colored as the literal.
4. From $C\_{j-1}$ to $C\_j$ there is an edge per literal in $C\_j$, colored as the literal.

Then $\phi$ is satisfiable iff there is a path from $s$ to $C\_m$ which uses at most $n$ different colors.
> 2 votes

---
Tags: formal-languages, graphs, shortest-path, routing
---


# Question
Title: Non-deterministic logarithmic time complexity class
Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$?
It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to derive a proof from this intuition.

# Answer
$\mathsf{DLOGTIME\subsetneq NLOGTIME}$. Search in unsorted array is a problem from $\mathsf{NLOGTIME}$, but it can't be solved deterministically in logarithmic time. This is proven. I also think that $\mathsf{NLOGTIME\not\subset DTIME}(o(n))$.

Padding argument here do not have an implication for $\mathsf P$ vs. $\mathsf{NP}$.
> 1 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, nondeterminism
---


# Question
Title: Domain theory: Definition of isomorphisms
Consider the following definitions of CPOs, monotonicity and continuity: The pair $(M, \leq)$ is called CPO (*complete partial order*), if

* $M$ is a set,
* $\leq$ is a partial order on $M$,
* there exists a least element according to $\leq$ in $M$ (called *bottom*, $\bot$),
* for every chain $m\_0, m\_1, m\_2, \dots$ in $M$ its supremum $\bigsqcup \\{m\_0, m\_1, m\_2, \dots\\}$ (least upper bound) exists in $M$.

(where a chain is a sequence $m\_0, m\_1, m\_2, \dots$ of elements in $M$ such that for all $i, j \in \mathbb{N}$ $m\_i \leq m\_j \vee m\_j \leq m\_i$ holds)

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called *monotone* if for all $a, b \in M$

$$a \leq b \implies f(a) \sqsubseteq f(b)$$

holds.

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called *continuous*, if it is already monotone and for all chains $m\_0, m\_1, m\_2, \dots$ we have

$$f\left(\bigsqcup \\{m\_0, m\_1, m\_2, \dots\\}\right) = \bigsqcup \\{f(m\_0), f(m\_1), f(m\_2), \dots\\}.$$

I read in a book using above definitions that two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ are *isomorphic* if there exists a function $f \colon M \to N$ such that

* $f$ is bijective
* $f$ and $f^{-1}$ are continuous (and therefore monotone).

I understand the demand of $f$ **and** $f^{-1}$ being monotone, so that they preserve the order.

---

Question: Why is this not sufficient? Why do we also demand $f$ to be continuous? Why its inverse function too? What are examples where a violation of one property would result in a strange view of equivalence? Another question: Is it possible to drop one property, because the other would imply it? I'm thinking about to demand only $f$'s continuity and to show that $f^{-1}$'s continuity follows – however I was not able to do so, or to come up with a counter example.

Edit: I suggest a »domain theory« tag.

# Answer
I think I have found an answer to my question, by proofing that the monotonicity of $f$ and $f^{-1}$ imply the continuity of $f$ and $f^{-1}$. Please correct me if I made a mistake – I will give you some days to check my proof before I accept my own answer.

---

**Lemma**: If a function $f \colon M \to N$ between two cpos is monotonic, the inequality

$$\bigsqcup\\{f(m\_0), f(m\_1), f(m\_2), \dots\\} \leq f\left(\bigsqcup\\{ m\_0, m\_1, m\_2, \dots\\}\right)$$

holds for all chains $m\_0, m\_1, m\_2, \dots$. This is well known and easy to show, so I will skip the proof of this.

---

Let $f \colon M \to N$ be now a bijective function between two cpos and let it, and its inverse $f^{-1}$, be monotonic. By the above lemma we have already one side of inequality to proof the continuity of $f$. It remains to show that

$$f\left(\bigsqcup\\{ m\_0, m\_1, m\_2, \dots\\}\right) \leq \bigsqcup\\{f(m\_0), f(m\_1), f(m\_2), \dots\\}$$

holds for all chains $m\_0, m\_1, m\_2, \dots$ in $M$. Since $$\bigsqcup\\{f(m\_0), f(m\_1), f(m\_2), \dots\\} = f\left(f^{-1}\left(\bigsqcup\\{f(m\_0), f(m\_1), f(m\_2), \dots\\}\right)\right),$$

and both $f$ and $f^{-1}$ are monotonic, the above inequality is equivalent to

$$\bigsqcup\\{ m\_0, m\_1, m\_2, \dots\\} \leq f^{-1}\left(\bigsqcup\\{f(m\_0), f(m\_1), f(m\_2), \dots\\}\right).$$

However, again by above lemma we have

$$ f^{-1}\left(\bigsqcup\\{f(m\_0), f(m\_1), f(m\_2), \dots\\}\right) \geq \bigsqcup\\{f^{-1}(f(m\_0)), f^{-1}(f(m\_1)), f^{-1}(f(m\_2)), \dots\\} = \bigsqcup\\{ m\_0, m\_1, m\_2, \dots\\}.$$

So $f$ is continuous. You show the continuity of $f^{-1}$ in the same way.
> 2 votes

---
Tags: denotational-semantics
---


title: Question on Predicates and Quantifiers

text:
# Question
Title: Question on Predicates and Quantifiers
I am reading from *"Discrete Mathematics and Its applications"* by Kenneth H. Rosen, 7th edition. Consider the **highlighted part** in the following example taken from the same book:

> **Question** Use predicates and quantifiers to express the system specifications “Every mail message larger than one megabyte will be compressed” and “If a user is active, at least one network link will be available.”
>
> **Solution:** Let S(m, y) be “Mail message m is larger than y megabytes,” where the variable x has the domain of all mail messages and the variable y is a positive real number, and let C(m) denote “Mail message m will be compressed.” Then the specification “Every mail message larger than one megabyte will be compressed” can be represented as ∀m(S(m, 1) → C(m)). Remember the rules of precedence for quantifiers and logical connectives! Let A(u) represent “User u is active,” where the variable u has the domain of all users, let S(n, x) denote “Network link n is in state x,” where n has the domain of all network links and x has the domain of all possible states for a network link. Then the specification “If a user is active, at least one network link will be available” can be represented by
>
> **∃uA(u) → ∃nS(n, available)**.

"Existential quantifier" **∃u** is used here, So I think, it should be **∃uA(u)∧ ∃nS(n, available)** in place of **∃uA(u) → ∃nS(n, available)**.

Generally, we use 'implication' with 'universal quantifier' as shown in **∀m(S(m, 1) → C(m))**.

Please correct me, if I am wrong.

# Answer
> 2 votes
The meaning of $$ \exists u A(u) \land \exists n S(n,\text{available}) $$ is "there exists an active user, and there exists a network link which is available". The conditioning is missing here.

If $P = \exists u A(u)$ and $Q = \exists n S(n,\text{available})$, then we are trying to model "if $P$ then $Q$", whose formal form is $P \rightarrow Q$, whereas your answer is $P \land Q$.

In particular, if there *doesn't* exist an active user, then $P \land Q$ is always false, whereas $P \to Q$ is always true.

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


title: $UCYCLE$ is in $L$

text:
# Question
Title: $UCYCLE$ is in $L$
I'm trying to understand the log-space algorithm for $$UCYCLE = \\{ \langle G \rangle \ | \text{ $G$ is an undirected graph containing a cycle} \\}$$

The basic idea is traversing from every $v\in V$, remembering the first edge and checking if we got back to $v$ from another edge.

What I don't quite understand is the way of traversing; This answer says:

> For the undirected cycle problem, you can traverse each connected component: at each node, when coming in through edge $k$, leave through edge $k+1$. (We can assume edges are ordered at each vertex.)

I don't quite understand it - after exhausting all the edges of the form $\langle v,u\_i \rangle$ where do we go from here? I could of course remembering what edge brought us to $v$ but then we clearly exceed the $O(\log n)$ boundary.

# Answer
> 7 votes
First of all, let me give the correct attribution to this algorithm: Cook and McKenzie, Problems complete for deterministic logarithmic space.

The setup of Cook and McKenzie is that you are given an undirected graph in which the edges incident to a vertex $v$ are ordered (cyclically), and given one of them it is possible to find the next one in the order.

Consider now the following algorithm, for an vertex $v$ and an incident edge $e$:

* Set $v\_0 = v$ and $e\_0 = e$.
* Let $v'$ be the other endpoint of $e$. Set $v = v'$.
* Repeat:
* + Let $e'$ be the edge following $e$ in the cyclic order of $v$.
* + Let $v'$ be the other endpoint of $e'$.
* + Replace $v,e$ by $v',e'$.
* Until $v = v\_0$.
* If $e \neq e\_0$, return "cyclic", otherwise return "don't know".

We now have two claims:

1. If $G$ is acyclic then the algorithm returns "don't know" whatever $v,e$ we start with.
2. If $G$ is cyclic then there is a choice of $v,e$ for which the algorithm returns "cyclic".

To see the first claim, suppose that $G$ is acyclic, and let $v,e$ be given. Consider the connected component containing $v$. If we remove $e$ then it breaks into two connected components $C\_1,C\_2$, the first containing $v$, the other not containing $v$. At the first step of the algorithm, it moves to $C\_2$. The only way to return to $C\_1$ is via the edge $e$, and when that happens, the algorithm will return "don't know".

To see the second claim, suppose that $G$ contains some cycle $v\_1,\ldots,v\_\ell$, and suppose for the sake of contradiction that whenever running the algorithm with $v,e$ it outputs "don't know". Let us run the algorithm with $v=v\_1$ and $e=(v\_1,v\_2)$. Let the edges incident to $v\_2$ be $e,e\_1,\ldots,e\_t$. According to the assumption, the algorithm will take the edge $e\_1$, get back to $v\_2$ via $e\_1$, traverse $e\_2$, get back to $v\_2$ via $e\_2$, and so on. In particular, it will reach $(v\_2,v\_3)$ before reaching $e$. By assumption, the only way to go back to $v\_1$ is via $e$, and so the algorithm will reach $v\_3$ before it goes back to $v\_1$.

Let the edges incident to $v\_3$ be $(v\_3,v\_2),e'\_1,\ldots,e'\_s$. As before, the walk will traverse $e'\_1$, go back to $v\_3$ via $e'\_1$, traverse $e'\_2$, go back to $v\_3$ via $e'\_2$, and so on. In particular, it will reach $(v\_3,v\_4)$ before reaching $(v\_3,v\_2)$. Now, by assumption $(v\_3,v\_2)$ is the only way to get back to $v\_2$, which is the only way to get back to $v\_1$. Therefore the algorithm will reach $(v\_3,v\_4)$ before it goes back to $v\_1$.

Continuing in this way, we see that the algorithm will traverse $(v\_4,v\_5),\ldots,(v\_\ell,v\_1)$, and the last edge will be the first time at which it gets back to $v\_1$. We reach a contradiction since $(v\_\ell,v\_1) \neq (v\_2,v\_1)$.

---
Tags: algorithms, complexity-theory, space-complexity
---


# Question
Title: Prove that context free languages aren't closed under DropMiddle
The question is simple:

> $\qquad \operatorname{DropMiddle}(L)=\\{xy\in\Sigma^\* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\\}$.
>
> Prove that CFL's aren't closed under $\operatorname{DropMiddle}$.

I should probably be looking for a counter example, but I'm coming up short. I know that the language $ww$ ($w$ is a word in some CFL) isn't a CFL, but I can't figure out if I'm on the right track at all.

# Answer
> 4 votes
First off, you are right about looking for a counter example. However, $ww$ is a dead end, since no matter what you add to the middle, you'll stiil have a language that is not context-free.

Hint 1: If the middle character is in some way special in $L$, you can essentially modify a PDA for $L$ to nondeterministically guess the middle and the removed letter and it will accept $\operatorname{DropMiddle}(L)$. So you should try to look for a language, where the dropping makes the middle special.

Hint 2: If the specialness of the middle is the only feature of $\operatorname{DropMiddle}(L)$, a PDA could just use its stack to determine the middle. So you need to force it to use the stack in a different way.

Solution:

> $L = \\{ aw\_1aw\_2aw\_3a\ldots aw\_na \mid w\_i\in \\{(,)\\},~ w\_1\ldots w\_n \text{ is correctly parenthesized} \\}$.
> The $w\_i$ part forces any PDA for $L$ or $\operatorname{DropMiddle}(L)$ to use its stack to count open parens. Thus it is impossible to check if, the single missing $a$ after dropping is indeed missing from the exact middle of the word.
> Formally proving that $\operatorname{DropMiddle}(L)$ is not context-free should be doable with Ogden's Lemma.
> Choose a word $(^k)^k(^k)^k$ (plus the $a$s inbetween) and mark $k$ characters each left and right of the middle.

# Answer
> 1 votes
Dropping the middle symbol is usually an action that is not observed. But we can make it special by using a special symbol.

Let $L = \\{ a^n b^m \\# a^n b^\ell \mid n,m,\ell \ge 0 \\}$. Then $L$ is context-free.

Consider $K = \textrm{DropMiddle}(L) \cap a^\*b^\*a^\*b^\*$. The intersection with the regular language forces us to look at strings where $\\#$ was indeed the middle symbol, i.e., strings where $m=\ell$. Thus $K = \\{ a^n b^m a^n b^m \mid n,m \ge 0 \\}$, which is not context-free.

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: Is there a generic algorithm for translating equational rules into corresponding data structures?
When implementing a term rewriting system, one “optimization” one can do is to represent operators known to have certain equational properties with a more directly representative data structure. For example, one can use lists to represent uses of a binary operator known to be associative, rather than using the naïve syntax tree representation one is forced to use in the absence of any information about an operator.

I thought I recalled a result that stated that there was an algorithm that could take *any* (finite) set of equational rules about an operator and transform them into a data structure definition specialized for that set of equational rules. However, when I tried to look for this result, I couldn't find anything like it anywhere. Am I not looking hard enough or not in the right places, or did I just imagine this result entirely? If I *did* imagine it out of thin air, is there any less-powerful result of the same form that *is* known, or any counter-result that dashes my hopes of such a generic algorithm existing?

# Answer
It sounds like what you are asking for is, for a given equational system $\cal E$, to give a *canonical representation* for equivalence classes modulo $\cal E$.

Indeed, if your signature is the binary operation $\\\_\cdot\\\_$, and your equation is $$ (x\cdot y)\cdot z=x\cdot(y\cdot z)$$

then you can represent any element as $a\_1\cdot(a\_2\cdot(\ldots\cdot a\_n)\ldots)$ (where the $a\_i$) are atoms. As Derek Elkins points out, a good way to do this is to apply Knuth-Bendix completion to $\cal E$, (possibly) obtaining a rewrite system $\cal R$ that is confluent and terminating and computes, for each term $t$, a unique element that is a representative of $t$'s equivalence class under $\cal E$.

Now it is useful to note that in this case, the set of canonical forms happens to be isomorphic to the data types of lists of atoms. The fact that elements of an algebraic datatype captures the equivalence classes is not obvious, and is not true in general: if you add commutativity, that is the equation $$ x\cdot y = y\cdot x$$ then it's clear that there is no algebraic (first-order) datatype that captures exactly the normal forms, as this is isomorphic to **sorted** lists of atoms.

A reasonable question is to ask whether there is always such a data structure using *dependent types*. In particular, there is a version of sorted list using dependent types, namely:

```
data SortedList =
  Nil : SortedList
  Cons : forall x:Atom, forall l:SortedList , x <= min l -> SortedList

```

taking inspiration from this agda code. Note that `min` needs to be defined on `SortedList`, making this an inductive-recursive definition, but I'm pretty sure this can be avoided with a little more messiness (say, embedding list into sorted list).

I think the question needs to be made more precise though, because there is a type in *extensional* dependent type theory such that each element of that type represents exactly one equivalence class: namely, the type of all equivalence classes! It can be defined by

$$ \mathrm{Q}\_E:=\\{y|\exists x, \overline{x} = y\\}$$ where $\overline{x}$ is defined by: $$\overline{x}=\\{z| z=\_E x\\} $$

In general, quotient types are a tricky subject in type theory though, especially without sufficient extensionality, see e.g. Pragmatic Quotient Types by Cyril Cohen.

In conclusion:

1. In the naive version of your question, the answer is that it is impossible to associate an inductive data type to an equational theory such that each element of the type represents a unique class.
2. It *is* sometimes possible to compute a rewrite system which computes a unique representative of that class if the algorithm terminates and succeeds.
3. When allowing for dependent types, the question becomes more complex and is, I believe, still somewhat open, with some progress.
> 3 votes

---
Tags: data-structures, reference-request, term-rewriting
---


# Question
Title: Algorithm for determining if a statement is a paradox
Please bear with me, since I have just started working on this.

Assuming that the laws of thought apply.

The basic goal of the algorithm is to recast the statement into true or false premises and check if a true and false clashes. If there is a clash then the statement or the set of statements is/contains a paradox. This is the rule for determining if a statement or a set of statements is/contains a paradox.

When I say clash, it means that a statement upon recasting cannot be said to have both true and false attributes.

Rule 1:

"This statement is true" is true. "This statement is false" is true.

The set of both statements is a paradoxical set.

Rule 2:

If in a statement there is a clash between true and false statements then it is a paradoxical statement.

"This statement is false" is true

Russell’s paradox:

"R, which is the set of all sets which are not members of themselves, is a member of itself" is True "R is a set of all sets which are not members of themselves" is true. "R is a set of all sets which are members of themselves" is false. "R is a member of itself" is true. Collectively it cannot be true, because there is a clash.

Now, we only need to recast the statement into true and false using the "not" operator to evaluate if a statement is true or false. We can evaluate all truth values and find if there is a clash between a true and false somewhere. If there is a clash then the collective set of statements or the statement is a paradox.

I got a couple in there. Can anyone throw me a paradox where this fails? I am trying to make it even simpler. Thank you so much! I think you will need some logic to recast more complicated statements, but this should identify the simple ones.

If nothing else, could you please verify this to be correct, and let me know if there is any procedure for finding if a set of statements contains a paradox currently exists. I think the general procedure detailing a clash between true and false in a paradox is absolutely correct.

I just came to know that there is a boolean procedure for finding self reference paradoxes, but it seems to me that my method might just be slightly more efficient, since it does not require solving for the entire set of statements but can halt whenever a clash is found. It could be hard to find if the set of statements has a solution or a clash or not, in the case of Wen's paper on the same, which recasts statements as boolean statements.

I can use this to disprove strong AI. Can someone please tell me if it is already proven that a human like intelligence cannot be recreated on a Turing machine.

# Answer
So, there are a few problems with this.

* First, what is your formal definition of a paradox? Is it just a statement that can be found to be both true and false in some system? Paradox tends to be a bit of an informal term, so in CS we usually just refer to this as a contradiction, or an unsound logical system.

For example, Russel's paradox isn't actually a paradox, it's a proof by contradiction. We assume a premise i.e. "any set characterized by a logical proposition exists.", and show that we can prove falsehood from it, thus concluding that the premise must be false. (In intuitionist logic, this is actually how falsehood is defined).
* How are you encoding your logic statements? Traditional propositional logic doesn't give much in the way for describing self reference, so you probably need something higher order. Starting with natural language statements and converting them into logic is a whole separate problem.
* Your problem seems undecidable, since you could use it to determine if one can prove false from an arbitrary proposition, which means you can use it to determine if an arbitrary statement is true, which means you can use it to determine if a Turing Machine halts on given input.
> 4 votes

# Answer
Since the precise logical framework to be used is not clear from the question, I'll use logic in a quite liberal way, as the generic "laws of thought" mentioned in the question.

I claim that the problem is at least as hard as deciding whether any formula $p$ is true. Therefore, it is undecidable.

For this, let $p$ be any logical formula, and define $q$ as the formula "this proposition is equivalent to $\lnot p$".

Since "this proposition is true" is not a paradox, while "this proposition is false" is one, it follows that $q$ is a paradox if and only if $p$ is true.

Hence, provability can reduced to paradox-checking.
> 0 votes

---
Tags: algorithms, logic
---


# Question
Title: Determine whether a variable has positive influence in Boolean function
Given a Boolean function $f$ over the set of variables $X =\\{ x\_1,...,x\_n \\}$, the influence of $x\_i$ is defined as the probability that changing only $x\_i$ on random input changes $f$.
Given a function $f$ presented in $\text{CNF}$, and a coordinate, are there any known methods for determine if the coordinate has positive influence?

# Answer
Given a CNF $\phi$ and a variable $x\_i$, deciding whether $\phi$ depends on $x\_i$ is NP-complete. It is clearly in NP: all we need to verify that $\phi$ depends on $x\_i$ is two inputs different on $x\_i$ on which $\phi$ evaluates to different values.

In the other direction, we reduce from SAT. Given a CNF $\psi = C\_1 \land \cdots \land C\_m$, let $x$ be a new variable and consider the CNF $\phi = \psi \land x$. If $\psi$ is satisfiable then $\phi$ depends on $x$, since substituting such a satisfying assignment reduces $\phi$ to $x$. If $\psi$ is not satisfiable then $\phi$ is always false, and in particular doesn't depend on $x$.
> 2 votes

---
Tags: complexity-theory, discrete-mathematics, boolean-algebra
---


# Question
Title: Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation
In this blog the author states that the following

> So we now have a rather poor estimate of the number of values in the dataset based on bit patterns. How can we improve on it? One straightforward idea is to use multiple independent hash functions. If each hash produces its own set of random outputs, we can record the longest observed sequence of leading 0s from each; at the end we can average our values for a more accurate estimate.

can be replace with

> A better approach is one known as stochastic averaging. Instead of using multiple hash functions, we use just a single hash function, but use part of its output to split values into one of many buckets. Supposing we want 1024 values, we can take the first 10 bits of the hash function as a bucket number, and use the remainder of the hash to count leading 0s

I am confused on his description of replacement, can someone help me understand what does take the "first 10 bits of the hash function as a bucket number" mean? And how is it a direct replacement of the hashing multiple times and take the average.

Thanks

Edit:

The author claims that given a random hashed set of element, by counting the highest consecutive k prefix bit that is 0, you can estimate the cardinality of the distinct set to be `2^k`.

But using `2^k` once might not be a good idea, so he suggest using multiple hashing to determine the average of `2^k`. For example given `n` distinct n hash function. `2^k_approximate = (2^k_1 + 2^k_2 + .....2^k_n)/n`

However he claims that multiple hash can be be replace by using the first 10 bit of a single hash function as a bucket number. Which I don't quite understand why that would be similar to the original multi hash average technique.

# Answer
> 1 votes
Let us start with the original approach. We compute the hash values of all input elements, and choose the minimal one $h$. If the leading bit is at position $k$, then we estimate that the number of distinct inputs in the output is roughly $2^k$.

The idea behind this is that we think of the minimal hash as a minimum of $N$ random strings, where $N$ is the number of distinct inputs. We expect the leading bit of such a minimum to be at position roughly $\log\_2 N$.

When using $D$ different hash functions, the corresponding experiment is

> Choose $N$ random strings for each of $D$ many bins.

We then calculate the leading bit of the minimal string in each bin, and use this to estimate $N$.

Now suppose that we use the top $B$ bits to choose one of $2^B$ buckets, and compute the minimum value in each bucket. As before, this should be similar to the following experiment:

> Distribute $N$ random strings into $2^B$ bins at random.

As before, we then calculate leading bits and use them to estimate $N$, but since this step is identical to the corresponding step in the multiple hash method, we just concentrate on the first part of the experiment (putting random strings into bins).

We expect each bin to get roughly $N/2^B$ random strings, and so this experiment is very similar to the following one:

> Distribute $N/2^B$ random strings for each of $2^B$ many bins.

This is the same as the experiment for multiple hash functions, with $D = 2^B$ and $N$ reduced by a factor of $2^B$.

You might be put off by the difference in $N$. However, this difference disappears when we calculate the number of hash function evaluations. If we have a quota of $M$ hash function evaluations, then in the multiple hash case we can only use $M/D$ inputs, whereas in stochastic averaging we can use $M$ inputs.

---
Tags: algorithms, algorithm-analysis, probability-theory, probabilistic-algorithms, hashing
---


# Question
Title: Is the language of all non-palindromes context-free?
Is the language $L = \\{ w \mid w \in (a,b)^\* \wedge w \text{ is not a palindrome} \\}$, context-free? I think this grammar:

$ S \rightarrow aSa \mid bSb \mid aAb \mid bAa\\ A \rightarrow aAa \mid bAb \mid aAb \mid bAa \mid a \mid b \mid aa \mid ab \mid ba \mid bb $

generates it, but I'm unable to conclude anything using the pumping lemma for context free languages.

# Answer
> 2 votes
If $w$ is not a palindrome then there must be some $i$ such that the $i$th letter from the left is different from the $i$th letter form the right; and vice versa (prove!). This means that $$ L = \\{ \Sigma^{i-1} a \Sigma^\* b \Sigma^{i-1} : i \geq 1 \\} \cup \\{ \Sigma^{i-1} b \Sigma^\* a \Sigma^{i-1} : i \geq 1 \\}, $$ which is easily seen to be context-free.

Your grammar almost manages to capture this characterization. Unfortunately, it doesn't generate the words $ab$ and $ba$. A simpler grammar is $$ \begin{align\*} &S \to aSa|bSb|aTb|bTa \\ &T \to aT|bT|\epsilon \end{align\*} $$

---
Tags: formal-languages, formal-grammars
---


title: Source code for Network File System

text:
# Question
Title: Source code for Network File System
I am doing a small project which explains how operations (file open, file write etc.) are done in client side and server side in network File system. Can anyone help me out providing its source code so that i can track its operation.

It would be helpful if you can explain how the process takes place in real time.

# Answer
This question is very likely to be closed because it's not on topic here.

However, there is one computer science aspect to your question, which is about the design of network file systems and NFS in particular, rather than just asking for source code. To help answer *that* question, here are the main papers on NFS:

They may be a challenging read, but they are worth it.

The best reference that I know of is Brent Callaghan's book *NFS Illustrated*. If you have access to a well-stocked university library, it should be there. Also worth mentioning is RFC 1094, which is definitely not for the faint-hearted.

Almost all good operating system design books have a section on networked file systems, and will often use NFS as a case study. Additionally, almost all Unix-like open source operating systems (e.g. Linux, BSD, OpenSolaris derivatives) come with NFS implementations.

If you can use a search engine, they are not difficult to find, but it will probably help a lot if you have the paper handy.
> 1 votes

---
Tags: distributed-systems, filesystems
---


title: range / interval query algorithm

text:
# Question
Title: range / interval query algorithm
I've an hash (base 32 for what it's worth):

```
hash = 'ab352eghjhngd4'

```

And I've subscribers that want to listen to new hashes in a **range**.

```
   listener = { startAt: 'ab31', endAt: 'ab40', obj }
   listener2 = { startAt: 'ab350', endAt: 'ab351', obj }

```

In this case `listener1` should be notified of the new hash while `listener2` shouldn't.

I'd like to find another algorithm than just iterating through all listeners to find if they fit.

---

I was thinking of holding an array for `startAt`

```
startAtOrderedArray = [
       { startAt: 'ab31', endAt: 'ab40', obj },
       { startAt: 'ab350', endAt: 'ab351', obj },
       { startAt: 'uc', endAt: 'uc2', obj }
    ]

```

Then using binary search I can forget the third item because it's above the hash which was `ab352eghjhngd4`.

Then I can do the same with `endAt`.

```
endAtOrderedArray = [
       { startAt: 'uc', endAt: 'uc2', obj },
       { startAt: 'ab31', endAt: 'ab40', obj },
       { startAt: 'ab350', endAt: 'ab351', obj },
    ]

```

So I end up with:

```
 before = [
           { startAt: 'ab31', endAt: 'ab40', obj },
           { startAt: 'ab350', endAt: 'ab351', obj },
        ]

 after = [
           { startAt: 'uc', endAt: 'uc2', obj },
           { startAt: 'ab31', endAt: 'ab40', obj },
        ]

```

So now if an item is in both array then it's interested in the hash.

The issue however is the complexity is still linear so I'm wondering how can I do better ?

---

*I'd like the question to be as general as possible but for my specific use case it is likely that the first char of `startAt` and `endAt` are the same. So `{ startAt: 'ab', endAt: 'u23' }` is not likely.*

# Answer
> 4 votes
Use an interval tree. It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(\log n)$ time.

---
Tags: algorithms, hash, searching
---


# Question
Title: Linear time multiplication on RAM machine?
This page says following:

> Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM

Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) using RAM?

# Answer
The page is not fooling you. I'll refer you to the original paper, but accordingly they show the following:

> *Theorem 6.1* There exists an SMM which performs integer-multiplication in linear time, i.e. there is a constant $c$ such that any $2N$-bit input is read as the concatenation of two $N$-bit integers $x$, $y$, and after at most $cN$ many steps their product $z=xy$ is output in binary representation.

It is a rather detailed paper which would be silly to write up all here. See below.

Schönhage, A. (1980). Storage Modification Machines. *SIAM Journal on Computing*, 9(3), 490-508. https://doi.org/10.1137/0209036
> 2 votes

---
Tags: algorithms, asymptotics, integers, multiplication
---


title: What is "time-slice multi-threading"?

text:
# Question
Title: What is "time-slice multi-threading"?
My goal is to understand the exact differences between SoEMT, SMT and "time-slice multi threading".

Thus far I already found information on SoEMT and SMT and it does not seem to hard to find more on google. However my problem is: Time-slice multithreading. The best I found - apart from a long winded book, was:

– Processor switches between software threads after a predefined time slice – Can minimize the effects of long lasting events – Still, some execution slots are wasted For Time-slice multithreading I found:

However, this doesn't really go into detail how this things are achieved, for what purpose, its pros, cons and implementations etc.

I would thus be quite happy, if someone knew a good resource, that read up further on that topic. Bonus, if it also compares SoEMT, SMT. As always thanks in advance.

# Answer
Time-slice multithreading is the convectional multithreading where CPU creates an illusion of executing more than once program at a time but the CPU can execute only one of these programs at a time. The OS maintains the illusion of concurrency by rapidly switching between running programs at a fixed interval, called a **time slice**. Time slice multithreading works similar to RoundRobin fashion.

For detailed understanding refer

1. Definition (Convectional multithreading)
2. Stackoverflow answer
> 2 votes

---
Tags: operating-systems, concurrency, threads
---


# Question
Title: TM that finds the middle of an input string in O(n) time
Is it possible to find a TM with O(n) complexity that finds the middle of an input string? Or at least to prove that it cannot be done?

I can use a two-taped TM if it helps.

# Answer
With a two tape TM it is not difficult:

Move to the right on the input tape. Every second step write something to the secondary tape. Once you reach a blank on the input tape (i.e. the end of the input), start moving to the left on the input tape. Each step delete a symbol from the secondary tape. You have reached the middle if the second tape is empty.
> 2 votes

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


# Question
Title: Is an infinite tape alphabet for TM valid?
Can I use an infinite alphabet for the tape in a turing machine?

e.g. with input string as (1, 0)\* can I define the symbol 1j as the symbol 1 with j marks on top of it where j in a natural number, to be used on the tape?

# Answer
Turing machines have a finite tape alphabet.

You can think of a generalization of Turing machines with infinite tape alphabet, but there are two problems:

1. The description of the machine is no longer finite.
2. Such a machine can decide any language over $\\{0,1\\}$ (exercise).

There are ways around it - for example, we might require the rules to be finitely specifiable in some specific form. The resulting model will then be equivalent to Turing machines (in terms of computability).
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Example of Minimum Test Collection Problem
I'm studying the **Minimum Test Collection** problem and I can't find an example of some instance of the problem, given values to the sets. The Garey and Johnson book only contains the proof of its NP-Completeness.

I hope someone can give me an example in order to understand in a better way the problem.

The problem is defined as follows:

**Instance:** A finite set **A** of "possible diagnoses," a collection **C** of subsets of **A**, representing binary "tests," and a positive integer J≤|**C**|.

**Question:** Is there a subcollection **C′****C** with |**C′**|≤ **J** such that, for every pair $a\_{i},a\_{j}$ of possible diagnoses from **A**, there is some test c∈**C′** for which |{$a\_{i},a\_{j}$}|∩ c|=1 (that is, a test c that "distinguishes" between $a\_{i}$ and $a\_{j}$)?

Thanks.

# Answer
The formal definition of the problem from Garey and Johnson is

> **Minimum Test Collection**
>
> *Instance:* A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J\leq |C|$.
>
> *Question:* Is there a subcollection $C'\subseteq C$ with $|C'|\leq J$ such that, for every pair $a\_i,a\_j$ of possible diagnoses from $A$, there is some test $c\in C'$ for which $|\\{a\_i,a\_j\\}|\cap c|=1$ (that is, a test $c$ that "distinguishes" between $a\_i$ and $a\_j$)?

Think of $A$ as a set of diseases, and each element of $C$ is a set of all the diseases in $A$ that have some particular symptom. You can use these sets to figure out what disease a person has. For example (not necessarily medically accurate), suppose our diseases are $$A = \\{\mathrm{flu}, \mathrm{measles}, \mathrm{ebola}\\}$$ and our tests are $$C = \\{\mathrm{cough}, \mathrm{rash}, \mathrm{bleeding}\\}\\,,$$ where \begin{align\*} \mathrm{cough} &= \\{\mathrm{flu}, \mathrm{ebola}\\}\\ \mathrm{rash} &= \\{\mathrm{measles}, \mathrm{ebola}\\}\\ \mathrm{bleeding} &= \\{\mathrm{ebola}\\}\\,. \end{align\*}

A doctor might try to diagnose a patient by checking whether they have a cough and/or a rash and whether they're bleeding. Minimum Test Collection asks if we can do any better than that, since tests might be expensive to carry out.

In this case, we can. It's enough to check whether the patient is coughing and whether they're bleeding. If they're bleeding, we know they have ebola. If they're not bleeding, but they are coughing, they have the flu; if they're neither bleeding nor coughing, they must have the measles. (Note we're assuming as part of our test procedure that these are the only three diseases in the world, and that people only go to the doctor if they have at least one symptom.)
> 2 votes

# Answer
In the Minimum Test Collection Problem you have some universe $S$ of items that you want to distinguish and a collection $C$ of tests that for a given item are either positive or negative. You want to select a minimal subset $C'\subseteq C$ of these tests that allow you to distinguish every pair of items.

For example you can have the items {Plexiglass, Glass, Wood} and the tests "Does it float?" (Wood, Plexiglass), "Does it burn?" (Wood, Plexiglass), "Is it transparent?" (Plexiglass, Glass). You can select the tests "Does it float?" and "Is it transparent?" to distinguish the items:

* Plexiglass, Wood: Both float, but only Plexiglass is transparent
* Plexiglass, Glass: Both are transparent, but only Plexiglass floats
* Glass, Wood: Only Glass is transparent, only Wood floats.

For every single test there is a pair where the test is true for both, so you can't select only one test.
> 1 votes

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


title: Multi- Knapsack problem variation

text:
# Question
Title: Multi- Knapsack problem variation
I'm trying to model a scenario where there are `n` items, each having weight and volume. We also have `m` number of knapsack, each having a weight and volume capacity, where these items need to go inside. A feature that I am looking for is that the value property of each item which depends on which knapsack it goes into. For instance, item 1 has value of v1 if goes into knapsack 1, and v2 if it goes to knapsack 2.

How can I model the problem as a knapsack and an optimization problem so to maximize the overall value? So far I came into a multiple knapsack problem, 2 dimensional. For for the value, I don't have any clue.

# Answer
> 2 votes
The simplest approach is to formulate this as an instance of integer lienar programming. You have zero-or-one variables $x\_{i,j}$, where $x\_{i,j}=1$ means that item $i$ is placed into knapsack $j$. Then all of your constraints can be straightforwardly expressed as linear inequalities on these variables.

---
Tags: algorithms, optimization, dynamic-programming, approximation, knapsack-problems
---


title: Master Theorem linearithmic function

text:
# Question
Title: Master Theorem linearithmic function
I am trying to find the running time of the given recurrence by the Master Theorem: $T(n)=16T(\frac{n}{2})+n^3\log^4 n$

I get $a=16$, $b=2$ and $f(n)=n^3\log^4n$, It seems that it's Case 1 of the master theorem. because $f(n)=O(n^{4-\epsilon})$ for some $\epsilon \>0$ **(?)**

but I can't find this epsilon, and I am doubting if I can truly use the Master Theorem in this case.

What's I am missing?

# Answer
> 1 votes
It's easy to prove that

$\qquad\displaystyle n^3 \log^k n \in o(n^{3+x})$

for *all* $k \geq 0$ and $x \> 0$. That should give you plenty of $\epsilon$ to choose from.

---
Tags: asymptotics, master-theorem
---


# Question
Title: Tour de France problem : Dynamic programming
Here is the question:

You are doing the Tour de France and you are given a map with all the n places where you can refill your water bottles. Your bottles fit 2 liters of water with which are enough for m kilometres. Your goal is to stop as few times as possible to refill your bottles, since you care about a good time for the Tour de France. Design an efficient algorithm using dynamic programming, prove its correctness and analysis its run time. Give the one-dimensional array A. And the time complexity of filling your array.

I just confuse about this question. And what is the motivation to use dynamic programming.I think it looks like bin packing problem without change the order of choice. Why not use greedy next fit approach(e.g refill at kth station if we can't reach k+1th station without refill)could someone give some hint? Thanks

# Answer
> -1 votes
The most common reason not to use a greedy algorithm is if it wouldn't return the optimal solution on the problem you care about.

Presumably they suggest you use dynamic programming because it is possible to solve it that way, and/or they think that solving it using dynamic programming will be useful practice that will help you learn how to build dynamic programming algorithms.

---
Tags: algorithms, dynamic-programming
---


title: n-bit 2's Complement Conversion

text:
# Question
Title: n-bit 2's Complement Conversion
I'm learning 2's complement conversion for positional number systems. For the most part I have only seen 2's complement for represented in 8-bits. I had a discussion with a friend who explained that for values that exceed 8-bits (\>255) you would need to go to the next largest word size i.e. 16-bit followed by 32 and 64... That is all well and good, however I don't fully understand if or why I can't do 2's complement for something like a 5-bit, 21-bit, etc system.

For example, if I were to represent `0000 0001 1100 0111` as a 13-bit value I would take off some 0's `xxx0 0001 1100 0111`, perform some arithmetic to find the complement, `xxx1 1110 0011 0001` therefore the 13-bit 2's complement of `(0 0001 1100 0111)` is `(1 1110 0011 0001 0001)`? Please let me know if I am missing something...

# Answer
You can do this for 13 bits, or 15 bits etc, etc.. there is nothing stopping you.

The reason you jump to the next word size is because of the computers hardware. If a register has 8 bits and you are only using 6 bits, the register STILL has 8 bits.

You can design a system with 13 bit word size, and it will still work the same.
> 1 votes

---
Tags: arithmetic, number-formats, binary
---


# Question
Title: Examples of sets $A$ and $B$ such that $A \leq_m B$ but not $B \leq_m A$
I know that such sets exist and they are called sets that are not m-complete, but I am not sure how to find them. Can someone give examples?

# Answer
> 4 votes
I post my comment, as an extended note, which shows a small "formal trick".

A trivial example over natural numbers $\mathbb{N} = \\{n \> 0 \\}$, is:

$A = \\{ n\\} = \mathbb{N}$ and $B = \\{2n \\}$ (even numbers).

According to the definition of many-one reduction: a many-one reduction from $B$ to $A$ is a total computable function $f : \mathbb{N} → \mathbb{N}$ that has the property that each $x$ is in $B$ if and only if $f(x)$ is in $A$.

Clearly we have $A \leq\_m B$: a many-one reduction that works is $f(x) = 2$

But $B \nleq\_m A$ because given $x \notin B$ (e.g. $x = 3$) you cannot map it to a $f(x) \notin A$ because $A$ contains all elements.

# Answer
> 5 votes
Let $A$ be a computable set of all even nonnegative integers, and $H$ be the language of the Halting problem. Assume also that $w\_1 \in H$ and $w\_2 \notin H$. Then define a mapping as following:

$$f(x) = w\_1 \text{ if } x \text{ is even}, w\_2 \text{ if } x \text{ is odd } $$ This function is clearly computable and $x$ is even iff $f(x) = w\_1 \in H$, i.e., $A \leq\_m H$. However, $H \nleq\_m A$, otherwise $H$ would be computable/recursive.

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


# Question
Title: Is a non-deterministic turing machine that both accepts and rejects the same input valid?
I.e. - if a TM accepts the word 0011100 on one path, while on another the same word is rejected. Do we say that 0011100 is part of the language, or do we say that it is not a valid TM?

# Answer
A non-deterministic Turing machine accepts a word if an accepting computation exists. There can be many non-accepting computation paths. This is what makes recognizing the complement of the language more difficult than just inverting accepting an rejecting states as you would do with a deterministic machine.
> 1 votes

---
Tags: turing-machines, nondeterminism
---


# Question
Title: Many to one reductions from undecidable Turing Machine to a decidable language
From what I read, a many-to-one reduction $A \leq\_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$. However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

But what if I try to reduce the language $ATM$ : {$(i,w)$ | $TM\_i$ accepts $w$} to a well-known computable Turing-decidable language (i.e. $VERTEX-COVER$) using this function $f$:?

Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

In this case, $f$ is computable, and if $(i,w) \in A$, then $f(i,w)$ = $g \in VERTEX-COVER$. Since many-to-one reductions do not have to be surjective, I do not have to map all elements in the vertex-cover set, and yet, $g$ meets the conditions of the many-to-one reduction. There is also no necessary condition for $f$ to have a 'pullback' function $\hat{f}$, where $\hat{f}$ is an 'inverse' that maps all elements in vertex-cover back to $ATM$ since $A \leq\_m B$ does $\textbf{not}$ necessarily imply $B \leq\_m A$. (the pullback function $\hat{f}$ holds only if $f$ is surjective, which is not necessary in $\leq\_m$).

Given the lemma, if $A \leq B$ and $B$ is decidable, then $A$ is decidable. In this case, $VERTEX-COVER$ is decidable, then $ATM$ should be decidable... which is clearly wrong.

There is something obvious that I am missing here ...

# Answer
> 2 votes
> From what I read, a many-to-one reduction $A \leq\_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$.

No. It's not "for each element $x\in A$ there exists a computable $f$ ...", but "there exists a computable total $f$ s.t. for each $x\in A$ we have $x \in A \iff f(x) \in B$".

Your definition is wrong because:

1. it allows us to pick a different function for each $x\in A$, when we must pick only one;
2. it only states $x\in A \implies f(x)\in B$, when we need the double implication $\iff$;
3. $f$ must be total (maybe this is supposed to be implicit when you don't say "partial", but it's important)

> However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

Correct.

> Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

How do you check that TM $i$ accepts $w$? I guess you are simply suggesting to simulate TM $i$. If you do that, there is a possibility of non termination here: precisely, every time $i$ diverges. Hence, $f$ is not total in this case: since its implementation diverges on some inputs.

# Answer
> 1 votes
Your function $f$ has to be computable, meaning $f(x)$ must be defined for all $x\in \Sigma^\*$, such that $x\in ATM \text{ iff } f(x) \in VC$. **But you don't describe how you are going to map $x$ to $VC$**, which of course is impossible. In other words you still need to decide if $x\in ATM$ before you map $x$ into $VC$.

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


title: Oracle Turing Machine EXP^EXP

text:
# Question
Title: Oracle Turing Machine EXP^EXP
I'm reading Arora Barak and in that it is written that when $O \in \mathrm{P}$, then $\mathrm{P}^O = \mathrm{P}$. Can this be generalized? Intuitively, I think that $\mathrm{NP}^\mathrm{NP} \neq \mathrm{NP}$ but $\mathrm{EXP}^\mathrm{EXP} = \mathrm{EXP}$. Am I right? Any elaboration on the same would be appreciated.

# Answer
> 8 votes
No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O\left(2^{2^{\mathrm{poly}(n)}}\right)$ time.

This is just because you can give exponentially long input to an oracle which can solve it. So, the total power is $\exp(\exp(n))\ne \exp(n)$.

To see why $\mathsf P$ is self-low just take a machine that can run quadratic time and give to it the same oracle. While the resulting machine will be able to solve all languages in $\mathsf{DTIME}(n^4)$ it is still polynomial. Generalizing, $\mathrm{poly}(\mathrm{poly}(n))=\mathrm{poly}(n)$.

Was wrong, now understood that this is the only way to make machine that faster. Thanks to Ariel.

P.S. There is a parsimonious exp-time reduction from $\mathsf{2EXP}$-complete problem to an exponentially longer $\mathsf{EXP}$-complete problem.

---
Tags: complexity-theory, time-complexity, complexity-classes, oracle-machines
---


# Question
Title: What are all the decidable languages that can be constructed using a turing machine with only the Reject and Accept states?
What languages can be decided by a two-state TM that has two states: one accepting and one rejecting?

As a newbie in TMs, there are some definitions I am not familiar with, of which the answer is obviously dependent, like:

* Can we draw an outgoing arrow from the Accept or Reject states?
* Can either of these two states be the starting state?

# Answer
> 1 votes
If there are only two states, the rejecting state and the accepting state, then the machine must start in one of those states. That means it must immediately halt, which should tell you what language it can accept.

---
Tags: turing-machines
---


title: Is uniform cost search optimal?

text:
# Question
Title: Is uniform cost search optimal?
In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path), but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops? If solution is using a closed set to track explored nodes, we will lose ability of reopening a node when less cost is seen, thus optimal might compromise.

# Answer
> In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path)

Kinda. While it's true that the algorithm should output the optimal path, that's probably not what your notes were referring to. Rather, it's likely that they were making a claim about the algorithm itself being optimal in terms of performance.

A blog post, "Artificial Intelligence - Uniform Cost Search (UCS)", provides a claim like this:

> Uniform Cost Search is the best algorithm for a search problem, which does not involve the use of heuristics. It can solve any general graph for optimal cost. Uniform Cost Search as it sounds searches in branches which are more or less the same in cost.

The logic behind this claim seems simple enough: you don't want to search down paths that can't be optimal, since that'd be wasteful, but you don't have any way of knowing which paths might be optimal in advance. So, by going down each equally, you don't assume any effective bias.

I'm not 100% if this is true in all cases in which this claim's made, but it seems like a useful tidbit to be aware of.

> but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops?

There can't be negative costs. If there are negative nodes, you'd have to modify the algorithm by removing its termination condition, effectively reducing it to a brute force search.

For example, consider using UCS and finding an apparently optimal path without having searched the entire space. Then, it turns out that there's a node that you didn't search that has a cost of $-{\infty}$. Presumably an optimal path should've gone through that node, but the search couldn't have found it since it terminated too soon.

### Disclaimer about method names

Basic, widely known methods like this often have some variation in exactly how different sources define them or what name the method is given. For example, below I linked the relevant Wikipedia article, which calls it "Dijkstra's algorithm". The Wikipedia article discusses several different implementations.

Claims about algorithms with fuzzy definitions and frequently confused names should be taken with a grain of salt as there's plenty of room for miscommunication.

### Further reading

Wikipedia's article on Dijkstra's algorithm would likely be helpful:

> In some fields, artificial intelligence in particular, Dijkstra's algorithm or a variant of it is known as **uniform-cost search** and formulated as an instance of the more general idea of best-first search.
> 7 votes

# Answer
I had the same confusion. After reading the text I found that there was a condition. The condition was that every step cost should be positive. It can never be zero or negative. Only then the algorithm is optimal.
> 1 votes

# Answer
Nat already made it clear that the costs must be positive, but I'd just like to add that there's an additional condition and is that there must exist a cost $c^\prime$ such that $c^\prime \leq c$ for all other costs in your (possibly infinite) Graph, i.e. there must be some minimal positive cost. Think about it for a second, let's say there is a sequence of monotonically decreasing costs in your graph $G$ like $1, \frac{1}{2}, \frac{1}{4}, \ldots, \frac{1}{2^n}, \ldots$, if your goal $g$ is at a distance $3$ from the start then you may never reach it.
> 0 votes

---
Tags: search-algorithms
---


# Question
Title: How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7
I am trying to solve the recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 but without success.

And from here I don't know how to continue?

# Answer
> -3 votes
According to your recurrence equation 2t(n-1) futher breakdown like 2\[2t((n-1)-1)+t((n-1)-2)+5(n-1)+7\] and for solution of this equation explore recurrence equation solution

---
Tags: recursion
---