# Question
Title: Difference between intended interpretation and extended interpretation in first-order logic
I am currently reading "Artificial Intelligence - A modern approach" and I really do not get the difference between intended interpretation and extended interpretation in first-order logic.

Are extended interpretations all possible assignments from a symbol in my knowledge base to an object in the world? And is the intended interpretation the interpretation the "author" of the sentences wanted to have?

So when there is a symbol like "John" in my sentences does that mean that it really refers to the human being John in the real world (if I have intended interpretation).

And the extended interpretation could be: "John" in my sentences refers to the human being Mary in the real world.

Are the extended interpretations a set of all possible interpretations and is the intended interpretation one specific interpretation in this set?

So do I interpret my sentences either intended or extended?

And if I say in my interpretation that John and Mary (as constants) refer to the same object in my model can I unify them then, i.e. UNIFY(John,Mary) = {John/Mary}?

# Answer
> 2 votes
You should only care about *intended interpretation*. I don't like the concept of the *extended interpretation*. The latter is only included to make precise the concept of quantification, but I think it makes things more confusing instead.

Before understanding what an intended interpretation is, you should really know what a model is, and what a *language* or *signature* is. To follow their example: A language can be consisting of the constants *Richard* and *John*, the predicates (the arity in backets) *Brother* (2), *OnHead* (2), *Person* (1), *King* (1) and *Crown* (1). Finally you have the unary function *LeftLeg* (1).

That was the language, and though we use words as *Brother*, this should really impose *no* meaning, we could just as well have written it *A*.

A *model*, on the other hand, or what they call an *intended interpretation* is a *domain*, together with \*interpretations of the above predicates, constants and functions. Here's an example:

* Domain = { Richard, John, Crown, Dog }
* Brother = { (Richard, Crown), (Dog, John) }
* OnHead = { (Dog, John), (Richard, Dog), (Crown, Richard) } (*the crown' on Richard's head, Richard's on Dog's head, Dog's on John's head*)
* Person = {John, Dog}
* Richard = Richard (oops, heavy overloading!)
* John = Dog (oops, heavy overloading!)

I didn't complete the definition, but I hope you get the point. If you put all those above together as a KB, (Domain, Richard, John, Brother, OnHead, Person, etc...), you get your inteded interpretation.

The extended interpretation you should ignore. Completely. At least if you understand what $\forall x P(x)$ means for some first order sentence $P$. And $\exists x P(x)$.

# Answer
> 1 votes
An **interpretation** creates a link between symbols, on one hand, and objects, relations or functions, on the other hand. Examples of interpretations are the links between names and people in the real world or the links between Numbers (which are objects in the world of mathematics), and the corresponding symbols (1, 2, …).

To discuss intended/extended interpretations in this context of an example, let's assume a finite domain, containing only the 9 first natural numbers (1, 2, …, 9).

Some of the possible interpretations are as follows:

1. One ← 1 (symbol 1 refers to number one), Two ← 2, Three ← 3, …
2. One ← 9, Two ← 8, …
3. One ← 2, Two ← 3, …

In this case the **intended interpretation** is the first one, which we are all used to and the rest are unintended interpretations. And as you said, is the interpretation that the author would have.

An **extended interpretation** comes into play only when we are talking about quantifiers.

Consider this sentence: $\forall x: x \ge 1$

Here x is a variable which can refer to any object in the domain. That means we can link it to any of the objects in the domain:

* x linked to number one: $1 \ge 1$
* x linked to number two: $2 \ge 1$
*

An extended interpretation is created as we link a **variable** to an object in the domain. So, basically a universal/existential quantification is the conjunction/disjunction of all the extended interpretations.

---
Tags: logic, artificial-intelligence, first-order-logic
---


# Question
Title: Are registers stack, per core or per application based?
I am doing a study on I found on youtube called OpenSecurityTraining: Introductory Intel x86. From what I understand there are registers like EAX, ECD, EDX, ect... and each have a purpose and hold/move information in memory.

Are these registers per stack/application? Meaning, each application will have it's own EAX, EDX, ect... that it uses to hold or move data in and out of memory?

# Answer
> 3 votes
Each processor has it's own registers. each *process* has it's own values to the registers which getting stored/reload during context-switch.

# Answer
> 3 votes
Each virtual core has its own registers. Let's say you have a quad core Intel processor with hyperthreading. Each core has two virtual cores, the processor has four cores, so you have a total of eight sets of registers in that processor.

Each thread has registers. The operating system lets you have huge number of threads, but you can have at most one thread running per virtual core. So on the processor mentioned above, there could be eight threads running, using eight registers. For all the other threads that are not running, the operating system will store the register values that the thread should have, and when a thread is paused it's registers are stored, and when another thread is unpaused the stored register values are restored in the actual registers.

---
Tags: memory-management, stacks
---


# Question
Title: How would the classes of regular, context-free, decidable, and Turing-recognizable languages relate to each other
I'm a bit confused as to how they relate to each other. I think I understand them individually but not sure how they would relate.

# Answer
> 0 votes
Short answer:

Regular $\subseteq$ Context-free $\subseteq$ Decidable $\subseteq$ Turing-recognizable

Long answer: take a look at the computation models. You will see that each one is an extension of the one before it.

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


# Question
Title: Are single-dimentional arrays better than multi-dimentional in the GPU?
I'm making simulations like Ant colony simulation, boids, and cellular automata in Go (to learn Go), but I believe this can apply to most languages.

From what I've read (this), using 1D arrays is generally better, but the post only addresses CPU processing. I want to do my simulations with the GPU and that may have some implications I'm not aware of.

In my case, a `Map` object is a 2D array of `Cell` objects.

```
struct Cell {...}
struct Map {
  Cell[][] cells;
}

```

Is it better to use 1D arrays instead of multi-dimensionals when working with the GPU?

# Answer
This is likely going to be dependent on what technology and libraries you use to program the GPU (PyTorch? TensorFlow? CUDA? BLAS? something else?), and thus seems likely to be out of scope here. Typically the data must be transferred/copied onto the GPU anyway, so I'd expect the structure of it in RAM only affects the time to transfer to the GPU's memory, not the time to do the GPU computation once it has been copied into GPU memory in the memory layout that the GPU wants.
> 0 votes

---
Tags: arrays, parallel-computing
---


title: Grasshopper Optimization Algorithm

text:
# Question
Title: Grasshopper Optimization Algorithm
I am currently reading a paper on a meta-heuristic called 'Grasshopper Optimization Algorithm'.

The main idea of the algorithm is to utilize the social behavior of grasshoppers in a swarm to solve optimization problems. The distance to other grasshoppers in the swarm is used to determine, if a grashopper is repelled (exploration) or attracted (exploitation) from grasshoppers in its proximity.

However I am not sure if I understood the first part of the proposed formula correctly:

$$X\_i^d = c\left(\sum\limits\_{j=1,j\neq i}^Nc\frac{ub\_d-lb\_d}{2}s\left(\lvert x\_j^d-x\_i^d\rvert\right)\frac{x\_j-x\_i}{d\_{ij}}\right) + \widehat{T}\_d$$

$X\_i^d$ calculates the next position of a search agent (grasshopper) with respect to the postion of the other search agents and the best found solution so far. So the next position of a grasshopper depends on its own position, the positions of all other grasshoppers in the swarm and the best solution found so far.

$\widehat{T}\_d$ denotes the best solution found so far.

$c$ is a decreasing coefficient that regulates if the search agents explore or exploit in the search space. With increasing iteration count $c$ decreases and the search agents tend to exploitation.

$s\left(\lvert x\_j^d-x\_i^d\rvert\right)$

The part in brackets calculates the distance between grashoppers. $s$ is a formula which takes this value and determines if the search agents should explore or exploit.

$\frac{x\_j-x\_i}{d\_{ij}}$ is a unit vector, where $d\_{ij}$ denotes the distance between two grasshoppers.

It states that $ub\_d$ is the upper bound and $lb\_d$ is the lower bound in the $d$-th dimension. It further states that the part $c\frac{ub\_d-lb\_d}{2}$ linearly decreases the space that grasshoppers (search agents) should explore and exploit.

I dont undertsand what is meant with 'upper and lower bound in the $d$-th dimension'. Upper and lower bound for what exactly?

Can somebody help?

Information extracted from this paper:

Grashopper Optimization Algorithm

# Answer
I suspect they probably mean $$ub\_d = \max\_i x\_i^d$$ where $x\_i^d$ is the $d$h coordinate of $x\_i$; and similarly for $lb\_d$, but using $\min$ instead of $\max$. But I don't know -- I am just speculating based on context.
> 1 votes

---
Tags: algorithms, heuristics
---


# Question
Title: Optimal clustering with optimal number of clusters as well as max and min cluster size constraints
I need to cluster $N$ data points.

I don't know the number of clusters to be formed. It needs to be found optimally.

Also, there is maximum and minimum cluster size constraints, where $C\_{\max}$ is the maximum size that one cluster can get and $C\_{\min}$ is the minimum size that one cluster must get.

The coordinates of the $N$ data points are stored in a matrix $D\in\mathbb{R}^{2\times N}$, $D$ is a matrix of $N$ rows and each row has two elements defining the $x-$axis and $y-$axis coordinates. However, $D$ can be expressed in any convenient form, for example, $D\in\mathbb{R}^{N\times 2}$ or $D\in\mathbb{C}^{N\times 1}$ (where the coordinates are expressed as a complex number: $x+iy$)

How can I formulate this as a mathematical optimization problem and solve it efficiently?

Data points can be uniformly distributed over a 2D plan of any given size.

# Answer
> 1 votes
**Answer 1.** There are various clustering algorithms depending on different requirements. You can employ $k$-means clustering method since it is fast, simple, and popular.

**Answer 2**. If you do not know the number of clusters, employ Elbow method. That is, first cluster the data for $k = 1$. Then cluster the data with $k = 2$, then $k = 3$ and so on. Initially, the cost of the clustering will decrease rapidly with increase in $k$. Once the $k$-means cost starts to appear constant with increase in $k$; that value of $k$ is the desired number of clusters.

**Answer 3.** When there are constraints on the size of clusters, the problem is (informally) known as the balanced clustering problem or capacitated clustering problem. The Wikipedia article does contain a few links of its implementation. This is a research paper for the balanced $k$-means problem. You might have to do some more research on this topic to find the perfect answer as per your requirement.

---

*Note:* The clustering problem that minimizes the $k$-means objective is $\mathsf{NP}$-hard. Therefore, you can expect to find an optimal solution to your problem in polynomial time.

# Answer
> 0 votes
One possible approach is to use agglomerative clustering, merging clusters until you get something whose size is in the acceptable range.

If you prefer to use optimization, another possible approach is to define an objective function $\Phi$ that measures the quality of a clustering, as a sum of two terms: $$\Phi = L + P$$ where $L$ measures how tightly coupled the clusters are (it might be any standard objective function for clustering, e.g., sum of pairwise squared distances between pairs of points in the same cluster, as in k-means clustering), and $P$ is a penalty term that measures whether the cluster sizes are as desired (e.g., $P = \max(\ell-s,0)^2 + \max(s-u,0)^2$, where $s$ is the size of an individual cluster and $\ell,u$ are the desired minimum and maximum cluster sizes). This is basically applying the penalty method for constrained optimization. As an alternative, you could use the barrier method instead of the penalty method, which would involve replacing $P$ with a barrier function that becomes infinite once the cluster size is too big or too small (e.g., $P = b\_u(x) + b\_{-\ell}(-x)$ where $b\_u(x) = -\log(u-x)$ if $x \< u$ or $b\_u(x) = +\infty$ if $x \ge u$).

---
Tags: optimization, clustering
---


# Question
Title: How to represent bottom element (integer domains) in SMT formula
I'm doing some work with static analysis and need to represent local variables as SMT formulas. In general this is fairly straight forward, depending on the domain of the static analysis. However, my question lies when needing to represent impossible or infeasible values, e.g., divide by zero paths from the static analysis under an integer domain. This is often referred to as the bottom element, ⊥.

I'm struggling to develop a formula which can represent these "impossible" (integer) values. Is there a way to do this?

I've been thinking along the lines as an impossible inequality, but I've been unsuccessful thus far. Similarly, I've thought about attempting to represent using divide by zero within an SMT formula, such as the following Z3/SMT formula:

```
(declare-const a Int)
(assert (= (/ a 0.0) 1.0))
(assert (= (/ a 0.0) 2.0))
(check-sat)

```

However, given the application, I'm not sure this is going to be helpful.

Application: I'm using this to compare results between two different static analyses between different domains.

tl;dr:

How to represent infeasible, bottom integer elements as SMT formula?

## Edit

I didn't try this enough, maybe the question is more along the lines of "is there a more eloquent way to model a bottom value besides the following?":

```
(declare-const a Int)
(assert (and (>= a 0) (< a 0)))
(check-sat)

```

The above will yield `unsat`, as expected. And since I'm trying to compare results of different static analyses, I can formulate questions about locals as such (is a top value equal to a bottom value):

```
(declare-const a Int)
(declare-const b Int)
(assert (= (and (>= a 0) (< a 0))
           (or (>= b 0) (< b 0))))

(check-sat)

```

This will also yield `unsat`.

# Answer
> 2 votes
First, you need to figure out the semantics of your language: does divide-by-zero cause the program to abort/halt/throw an exception, or does execution proceed and the divide-by-zero returns a NaN?

If it causes the program to halt, then you should not try to represent $\bot$ values. Instead, treat division as a conditional statement, that first tests whether the divisor is zero, and if so, aborts/halts/etc.

If it returns a NaN, then one approach is to introduce an extra boolean variable associated with each program variable. This boolean indicates whether the corresponding program variable holds a NaN. You should be able to work out the appropriate constraints to ensure these boolean variables receive the appropriate values.

---
Tags: satisfiability, smt-solvers
---


# Question
Title: eliminate left recursion of below grammar
Please look at this grammar: $$ → \ | \ \ | \ \\ → \ | \ \ | \ \\ → \ | \ d$$

I eliminated B from the grammar and it converted to:

$$ S → SAAS \ | SAd \ | \ Ab | \ b \\ A → SAS \ | \ Sd \ | \ a \ | ASS \ | dS $$

But I can't eliminate loop recursion between A and S.Was it a good solution I removed the B at first? How can I solve that?

any help is much appreciated.

# Answer
$$ → YX \ | \ Y \\ Y → Ab \ | \ b \\ X → ABX \ | \ AB \\ A → SB \ | \ BS \ | \ a \\ → \ | \ d$$

At first I say which rules have a left recursion, considering that the middle tree which is A(the one that A node is the root) has not called itself in its children from the beginning of the left of each child so there is no left recursion in tree which A is root.Similarly the right tree(the one that B node is the root) in its children has not called itself from the beginning of the left of each child, so they do not need to remove the left recursion, so They they have the previous rule (the fourth and fifth lines of my answer A→SB|BS|a,→|d ).

So our problem is the tree with the S root. I come and look at the children of the S root, there is only one child who starts with S from the beginning of the left of child, so I just have to correct one left recursion to right recursion,

Now I know that there are two children left of the tree with S root, since I only have a left recursion which I want to convert to the right recursion, So I have to put those two children on the left side of this conversion to the right! (For example, if we have two of these conversions we have to pack each of two children(with no recursion) with those two conversions.)

So I write the second line of my answer (Y→Ab|b) and then I write the third line of my answer (X→ABX|AB), which is actually the left-to-right conversion, The first line that these two children connect to each other, and the last two lines are the two trees in the middle and right.
> 1 votes

---
Tags: context-free, left-recursion
---


# Question
Title: Finding an algorithm to return the $\log n$ largest element in an array
I have just proved that for every $\alpha, \beta\>0 : (\log n)^\alpha=O(n^\beta)$.

Now, given an array of $n$ elements, I want to find an efficient comparison based algorithm for finding the $\log n$ largest elements in the array, and returning them in sorted order.

I will appreciate your help on what is the best way to solve this question, and how should I think when countering such a question.

# Answer
> 1 votes
A possibility (don't think it's the simplest way, though) is:

* Transform the array into a max-heap;
* find (without extracting) the $\log n$ largests elements in the heap.

The first step can be done in $O(n)$. For the second step, let's give a little bit details:

* The largest element is found among one element (it's the root);
* the second largest must be found among two elements (the two children of the root);
* in general, the $k$-th largest element must be found among $k$ elements, because each time you select an element to be the largest, you remove it from the candidates and add its two children.

That means that after having found the $k$ largest elements, finding the $k+1$-th is done by searching the maximum value among $k+1$, so it is done in $O(k)$. Since we want to find at most $\log n$ elements, the total search takes $O((\log n)^2)$ time, and with the property you proved, it is $O(n)$.

That means that the total complexity of the algorithm is $O(n)$ which is obviously optimal since you need to browse all elements of the array.

**Edit:** Actually, I realize (that confirms what I initially said) that there is a simpler way to do it:

Use a quickselect algorithm to find the $\log n$-th largest element (no plural here) of the array (this is done in $O(n)$). By doing so in place, the $\log n$ largest elements will be placed in consecutive positions at the end of the array. You can then sort those $\log n$ elements in time complexity $O(\log n \log \log n) \subset O((\log n)^2) \subset O(n)$.

# Answer
> 0 votes
Further to what Nathaniel said, you can think of this as a simple modification of quicksort, where you ignore any partitions which fall outside the range of interest.

Given:

```
algorithm quicksort(A, lo, hi) is
if lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)

```

Then this algorithm sorts the top $k$ elements in order, leaving the other elements in an unknown order:

```
algorithm quicksort_k(A, k, lo, hi) is
if lo < hi then
    p := partition(A, lo, hi)
    quicksort_k(A, k, lo, p - 1)
    if k > p then
        quicksort_k(A, k, p + 1, hi)

```

The expected running time is $O(n \log k)$.

The same trick works with any sort algorithm that is conceptually based on partitioning, such as MSD radix sort.

---
Tags: algorithms, data-structures, proof-techniques
---


title: Minimizing flow on a 2D matrix network

text:
# Question
Title: Minimizing flow on a 2D matrix network
I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it clear that I am not searching for a solution here, but asking a community of more experienced individuals if they have experience with/heard of similar problems to what I am about to describe.

Given an `nxn` matrix, let some small number of matrix indices (I will refer to them as nodes from now on) be colored blue, and rest of the nodes be colored white. Any white node that is adjacent (not including diagonal) to a blue node will become blue unless a block is placed between them. So for example, in a 2x2 grid, if the node at (0, 0) is blue and the rest are white, the whole grid will become blue unless blocks are placed between (0,0) and (0, 1) as well as (0, 0) and (1, 0).

Now, each block placed has a cost of 1, and each white node being converted to a blue node will have some cost greater than zero (the cost will be the same for all white nodes). The goal is to place blocks on the matrix such that the total cost is minimized.

It most problem instances, especially with a low cost of white nodes becoming blue, it will be optimal to let some white nodes suffer becoming blue. For example, going back to the 2x2 problem instance, if each white to blue conversion only costs .25, then letting all the nodes become blue will cost .75, whereas placing 2 blocks would cost 2, and so the minimum cost would be .75 and letting the blue spread across the grid.

I am wondering if anyone can recall a problem instance/algorithm that is similar to what I am attempting to solve and could suggest researching it? I have scoured the internet relating to min-cut/max-flow algorithms, but I am having trouble relating this problem to anything regarding network flow. Any suggestions of problems to research would be much appreciated.

# Answer
Build a grid graph, with one node per entry in the matrix, and edges between each pair of adjacent nodes. Also add a source node $s$ with an edge from $s$ to each blue node, and a sink node $t$ with an edge from each white node to $t$. Set the capacity of each edge to 1, except the $s$-to-blue edges have capacity $\infty$, and the white-to-$t$ edges have capacity given by the cost of allowing that white node to become blue.

Now, find the minimum $(s,t)$-cut in this graph, using any network flow algorithm. The $s$ side of this cut will contain all of the nodes that become blue, and the edges that cross the cut will indicate where to place blocks (for blue-to-white edges that cross the cut) and which white nodes become blue (for white-to-$t$ edges that cross the cut).

---

Why does this work? We're going to treat the final colors as defining a cut $(B,W)$: $B$ contains all nodes that are ultimately blue (and $s$), and $W$ contains all that remain white (and $t$). This means that any edge between an ultimately-blue node and an ultimately-white node crosses the cut, which matches the problem requirement that such an edge must have a block on it. Also, if $b \in B$ is any node that was originally white but becomes blue, then the edge $b \to t$ crosses the cut (since $t \in W$), so we think of it as having a block between it and $t$. Finally, we want to know the cheapest way to choose a set of blocks. The total cost of a set of blocks is the sum of the capacities of the edges that were blocked, so this total cost matches the total capacity of the edges that cross the cut $(B,W)$, i.e., the capacity of the cut. So, finding a min-capacity cut will find you the cheapest way to place a set of blocks that match the problem requirement.
> 2 votes

---
Tags: algorithms, dynamic-programming, network-flow
---


# Question
Title: Is complement of equality problem of Turing machines Turing-recognizable?
Complement of equality problem of Turing machines is unrecognizable or not-recognizable but How? As per my knowledge it is recognizable if you can decide its accept condition but not reject condition and the opposite is the case with unrecognizable. But in complement-Eq problem of TM if a string/input accepted by one but not by other you can Accept it, and reject condition will be undecidable so it should be Turin-recognizable.

# Answer
Let's start with the definition of *recognizable*:

> A language $L$ is recognizable if there exists a Turing machine $T$ such that if $x \in L$ then $T$ halts on $x$, and if $x \notin L$ then $T$ does not halt on $x$.

You haven't specified what you mean by "complement of equality problem of Turing machines", so let me assume that you mean the language $L$ consisting of pairs $(T\_1,T\_2)$ of Turing machines which do not recognize the same language, that is, there exists $x$ such that $T\_1$ halts on $x$ and $T\_2$ doesn't, or vice versa.

You could try recognizing $L$ by going over all words $x$, and for which one, checking whether $T\_1$ halts on $x$ and $T\_2$ doesn't, or vice versa. While you can recognize that $T\_1$ halts on $x$, you cannot recognize that $T\_2$ doesn't halt on $x$, so this strategy fails.

To show that this language is unrecognizable, you can use a reduction from the non-halting problem. Suppose that $T$ is a Turing machine, and we want to determine whether it doesn't halt on the empty input. Construct a new Turing machine $T\_1$ which erases its input and transfers control to $T$, and let $T\_2$ be a fixed Turing machine which immediately halts. Then $(T\_1,T\_2) \in L$ iff $T$ does not halt on the empty input.
> 1 votes

---
Tags: turing-machines, turing-recognizable
---


# Question
Title: Bubble sort: average number of total key comparisons
I want to know the steps for finding a Formula for *Average number of total comparisons in bubble sort*.
Please look at this example:

> ```
> 4 3 2 1 -> 3 2 1 4 ->   3 comparisons
> 3 2 1 4 -> 2 1 3 4 ->   2 comparisons
> 2 1 3 4 -> 1 2 3 4 ->   1 comparisons
>
> ```

For ordered and reverse ordered input we have different formula for number of total comparisons:

```
Min = n-1
Max = n(n-1)/2

```

*And I want a formula with steps to get average of it* \- all possible inputs - / expected number of key comparisons for each of *n* input values selected from a uniformly random source

**My try**

```
(Sum of total comparisons)/(n-1) =>  n(n-1)/2/(n-1) => (n-1)

```

*NOTE : (n-1) is number of steps*

is it right?

# Answer
> 0 votes
I'm assuming that all elements in the array you're sorting are distinct.

The average number of comparisons over all permutations of the array is equal to the expected value of the number of comparisons, so let's calculate that instead.

The total number of comparisons done to sort some array $A$ (length $N$) is equal to $N - 1 + (\text{Number of inversions in } A)$, where an inversion is a pair of indices $i \< j$ where $A\_i \> A\_j$. By linearity of expectation, the expected number of comparisons is thus $$ N - 1 + \sum\_{i \< j}P(A\_i \> A\_j) = N - 1 + \frac{N(N - 1)}{4} $$

---
Tags: algorithms
---


# Question
Title: Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?
I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=NP" problem, but I was wondering whether there were any particular instances when people were close to it. I've also heard about the factoring number problem being solved by a quantum computer by Shor's algorithm. Would this count as an algorithm which solved an NP-problem in polynomial time please ? Please do ask if you want me to clarify any parts in my questions. Thanks in advance.

# Answer
> 10 votes
By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no.

However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. Randomization isn't known to help "as-is", and many NP-hard problems are known that are also hard to approximate (finding an approximation will yield $P=NP$)

There are also attemps taking a look at notions much *stronger* than the usual turing machine. For instance, the quantum computer can be considered one. Another obvious example is the non-deterministic turing machines, in which - by definition - $NP$ would be in polynomial time.

# Answer
> 5 votes
If the answer to the first question were to be yes, then $P=NP$, as stated in nir shahar's answer. This has not been done.

### "The easiest NP hard problem"

However you next asked if any NP-hard problems have been solved in ***close*** to polynomial time, for which you might love to learn about what has been called "The easiest NP hard problem" because there's a pseudo-polynomial time solution using dynamic programming, and there are heuristics that solve the problem in many cases, sometimes optimally. The problem is the partitioning problem: Decide whether a set of positive integers can be partitioned into two sets such that the sum of the numbers in one set equal the sum of the numbers in the first set. Despite it being an NP-complete problem, it can be solved quite efficiently, as for example described in this PDF.

# Answer
> 4 votes
Strictly speaking, as the other answers explain, no. A polynomial-time algorithm for an NP-hard problem is not known nor expected to exist. But I think your underlying question is whether or not there are examples of natural NP-hard problems that are, in some sense, easier to solve than some other NP-hard problems.

There are several flavors in which you can quantify the hardness of NP-hard problems more closely. For example, there are problems that are extremely difficult to *approximate* (e.g., maximum clique) while some problems we can approximate arbitrarily close (e.g., knapsack). You could also have a look at *exact algorithms*: there are natural problems for which the best algorithms run in time $O^\*(2^n)$ and there is some evidence no algorithms faster than that exists, while others admit runtimes of roughly $O^\*(2^\sqrt{n})$ (e.g., planar problems) or even better. Or, you could look at *parameterized complexity*, where the idea is to do a two-dimensional analysis, i.e., take not only the size of the input $n$ but also pick some additional parameter, such as solution size or some structural parameter $k$. Then, some problems admit algorithms whose runtime is of the form $f(k) n^{O(1)}$, where $f$ is some computable function depending only on $k$, while some problems don't (e.g., $k$-clique).

# Answer
> 2 votes
The other answers are correct, but f I may add an observation: it seems like you are conflating classes of problems and particular instances. There are a number of instances that can be solved in polynomial time in classes that are NP-hard in general. For instance, Boolean satisfiability is NP-hard in general, since it reduces to 3SAT. However, there are a bunch of instances called Horn clauses which can actually be solved in linear time. Notice that these instances are a subset of all instances of SAT. If you do not know whether the instance you have to solve is a Horn clause, the problem is NP-hard. If you do know that your instances are restricted that way, you have HORNSAT, which is in P. It all depends what your input potentially could be, and complexity goes by the worst-case instance.

---
Tags: complexity-theory, time-complexity, np-hard, np, p-vs-np
---


# Question
Title: Optimize stacking time series by offsetting start times (feels like a backpack problem?)
1. Given a time-series of data collected from a **single** running process that takes 8 hours to complete:

| Minute | GB of Disk Space Used |
| --- | --- |
| 0 | 0 |
| 1 | 8 |
| 2 | 15 |
| 3 | 22 |

...Etc. It is sampled every minute, for 8 hours. The # of GB used jumps up and down a lot, and ends back at 0, like a big spiky mountain shape. I'm making a (large) assumption that running multiple instances of this process in parallel takes up proportionally more space, but doesn't slow eachother down.

2. I've also got a hard upper bound that the summed area graph (the total of all space usage at any given minute) can't go above.

My personal upper-bound is 780GB (the amount of spare disk space), and if I ran **53 processes in parallel starting at the same time**, they would all add up at minute 2 to (53 * 15) = 795 (which is \> 780), the disk would run out of space, and everything would crash. Or if I ran 35 in parallel, they would crash at minute 3. No crashing allowed!

3. The goal is complete as many runs of the process as possible within the next 7 days, by "packing them in" and running them in some overlapping manner by deciding when each run of the process starts.

## First Attempt: Greedy

At first I thought it was a simple **greedy** problem: At every minute, ask "can you start a new process without the total of all running processes exceeding the limit in the future?" If yes, great! start a new one. If not, wait a minute and try again. This leads to "start 3 processes immediately. Wait until they all finish. Then do it again for 7 days."

## Second Attempt: recursive?

Done! wait... that feels wrong, backpack-packing style. What about *"If you line up runs A and B just right, they make a valley you could fit C in to."*

Which makes it feel like a recursive solve problem. Is there an accepted way to optimize this sort of thing?

## Third Attempt: Minimize the Maximum (like Tetris?)

My best guess at this point is a simple optimization strategy:

1. Define a time bound (7 days)
2. Place the next process start time at whatever is the minimizes the "max space used on the drive, over all time"
3. If there are ties, move the graph to the soonest start point.
4. Repeat #2 until nothing more fits.

This would work out to:

1. First process starts immediately.
2. Second process starts *before* the first one finishes: Whenever is in the downslope of the first one exceeds the upslope of the second one.
3. Keep adding process start times until there isn't a place to slot in one more.

# Answer
I suspect this problem is NP-hard, but haven't been able to prove it. In any case, Integer Linear Programming (ILP) is a good way to solve it.

Let $c\_1, \dots, c\_n$ be the series data. For each valid start time $i$, create a variable $x\_i$ to hold the number of copies to start at this time and add the constraint $x\_i \ge 0$. For each minute of time $i$ (now also including the 8 hours' worth after all valid starting times), add the constraint $\sum\_j c\_{i-j+1}x\_j \le 780$. Objective: Maximise $\sum\_i x\_i$.

Although this will make for a fairly large ILP instance, my feeling is that will be a "nice" one that can be solved to optimality quickly by a commercial solver like CPLEX or Gurobi. But in case it's not: Even a free LP solver will solve the LP relaxation of this without difficulty; rounding down the $x\_i$ gives a feasible solution. If there are few variables $\ge 1$, so that rounding gives an unhelpful answer, you can always just remove some of the variables (I suggest removing the ones with the lowest values) and re-solve.
> 2 votes

---
Tags: optimization, greedy-algorithms, packing, time-series-analysis
---


# Question
Title: Difference between present - absent bit and valid - invalid bit in a page table?
while reading I found this:

> Present/Absent bit – Present or absent bit says whether a particular page you are looking for is present or absent. In case if it is not present, that is called Page Fault. It is set to 0 if the corresponding page is not in memory.

and

> Valid and Invalid bit are present in the page table of concern process and it indicate whether address generated by cpu is valid or invalid and tells whether the address generated belongs to process address space or not.

Also since the page table contains only the page entries for a process so how come V/I bit present in page table tell that the generated address is not valid for the addresses not present in process.

I am a beginner, so please help me build my concepts.

# Answer
Many people confuse these two bits. I'll try to explain the concept to best of my knowledge.

Let's say we have 32 bit architecture. so process virtual address space(VAS) will have size of 2^32. VAS space of a process has kernel code, user code and data part. Page table of process contains entries for both user/kernel part. kernel page table entries are same for all processes that is these virtual addresses are mapped to same physical memory frame for all processes.because memory has just one copy of OS code.

process when initialized doesn't use the full VAS.virtual addresses which are not in use as of now have valid bit zero(**Invalid**). It can make use of more addresses by calling sbrk(), brk() system call.These system calls are used internally by malloc in C(if no holes are present already). which will add more virtual address to process page table that means it will make those pages **valid**.

Now there is a catch, page table entries which had valid bit set recently are not yet mapped to physical frames, that is where present/absent bit comes into picture. or if they are swapped out due to lack of physical memory.

Now when process will try to access these newly validated virtual address/swapped out address, as present bit is not set it will generate a page fault. Now we'll switch to kernel mode to service the page fault.OS has the disk address of the page to be loaded, once page fault service routine is finished it will make present bit set in the process page table. Meanwhile this page fault routine is being serviced,current process is contexted out and new process is given the cpu as per scheduling algorithm so that CPU cycles are not wasted.

I hope this answer helps.
> 4 votes

# Answer
Let us suppose you have 32 bytes of VAS and the page size is 4 bytes, so the total number of pages is 8. Now suppose that you have allocated 8 frames in PAS, but as of now you don't require all pages simultaneously. Now consider the following case: in the PAS you have only two pages of processes present. You can load all pages in a single frame, but you didn't. So whenever any request comes from the CPU (other than that already present in frame), for that request the valid/invalid bit will show zero.

The conclusion is that if the frame is allocated for a page, but that page is not present in PAS, then for that page, the page table entry will show 0 in the valid/invalid bit.
> 1 votes

---
Tags: operating-systems, paging
---


# Question
Title: Is there a theorem that says when an array of numbers can be searched faster than linearly?
I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, which means some knowledge of the structure of the collection, but maybe there is something else.

# Answer
In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this).

However, if you know more about the structure of the array, there are plenty of things you can do.

For example, imagine the array has the following property: its elements are sorted increasingly up to a certain index $i$, and sorted decreasingly after that. Can you do faster than a linear search? Yes! You can still search elements in $O(\lg n)$.

What if I ask you to search in an array $A$ that is sorted increasingly except for $1$ element, which is out of place? (you don't know which element). You can still search in $O(\lg n)$, how :)?

What if the array $A$ holds the following property: when you divide it in chunks of size $\sqrt{n}$, say $A\[0..\sqrt{n}-1\], A\[\sqrt{n}..2\sqrt{n}-1\], \ldots, A\[n-\sqrt{n}..n-1\]$, then each of the chunks is sorted. Can you do faster than a linear search? Yes! if you do a binary search in each chunk, then you get complexity $O(\sqrt{n}\lg n)$.

What if you know the array $A$ has only two elements, $x$ and $y$, and they both appear the same number of times? Can you find an element in less than $n$ comparisons? Yes!

In general, there are many different kinds of informations you can have about an array that speed up search, and different forms of knowledge would have different impacts on how much you can speed up.
> 3 votes

---
Tags: algorithms, complexity-theory, search-algorithms
---


# Question
Title: How do we define the term "computation" across models of computation?
**How do we define the term computation / computable function generically across models of computation?**

Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function".

A function f with domain f is said to be Turing-computable of just computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F) such that q0w ⊢\* Mqₘf(w), qₘ ∈ F, for all w ∈ D (Linz:1990:243)

Computable Functions A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape. (Sipser:1997:190)

Definition 5.12 A function f: Σ\* → Σ\* is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape. (Sipser:1997:190)

A partial function σ: Σ\* → Σ\* is said to be a computable function if σ(x) = M(x) for some Turing machine M. (Kozen:1997:347)

I need to have the term \[computable function\] defined generically across models of computation so that I can know whether or not a specific C function is a \[computable function\].

**Linz, Peter 1990**. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

**Sipser, Michael 1997**. Introduction to the Theory of Computation. Boston: PWS Publishing Company

**Kozen, Dexter 1997**. Automata and Computability. New York: Springer-Verlag.

# Answer
Definition 5.12 is a standard way of defining a "computable function". I see that you wish it was defined generically, but things are not as you wish they were; computability is typically defined with respect to a single model of computation.

That said, if you have any other Turing-complete notion of computation, then it is easy to prove that you can replace "Turing machine" with "machine in that model of computation" and you'll get an equivalent notion: in other words, there will be a Turing machine that computes $f$ iff there is a machine in that model of computation that computes $f$. So the concept is indeed quite generic, even if the definition is not articulated that way.

See also https://en.wikipedia.org/wiki/Computable\_function#Definition.

The exact semantics of C are messy and hard to formalize, and there appears to be some debate about whether C is Turing-complete, so C code is typically not a good way to prove that a function is computable or to reason about whether a function is computable.
> 4 votes

# Answer
When we unify on the Sipser and Kozen definitions of "computable function" we have the mapping from one possibly empty finite string to another possibly empty finite string.

This can be generalized to all models of computation that operate on finite strings. C functions deriving 0/1 integer return values from finite string inputs would seem to meet the above specification.

**Language acceptor of the Chomsky hierarchy:**
`int Accept(char* S); // returns 0 or 1`

It would seem that the above C function could implement every Turing computable language acceptor that does not require more memory than is available.

Please critique this I am aiming for the best quality answer.
> 0 votes

---
Tags: computation-models, turing-completeness, church-turing-thesis
---


title: Sorting by repeated reversal

text:
# Question
Title: Sorting by repeated reversal
> Let $A$ be an array of $n$ integers containing the numbers $\\{1, 2, \dots , n\\}$ in some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i \< j ≤ n$, let $\mathrm{Reverse}(A, i, j)$ be a procedure that reverses the subarray $A\[i\], A\[i + 1\], \dots , A\[j\]$ of the array $A$ while leaving the remaining elements of the array unaffected. Prove that the following algorithm sorts the array $A$ and also terminates.
>
> **for** i := 1 to n − 1
> **while** A\[i\] ≠ i **do**
> Reverse(A, i, A\[i\])

I am able to prove this if the elements are in descending order. Why does this algorithm work for an arbitrary order?

# Answer
> 4 votes
If the algorithm terminates at all then $A\[i\] = i$ for $i \leq n-1$, and so $A$ is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching $i = i\_0$, we know that $A\[j\] = j$ for $j \< i\_0$, and so $A\[i\_0\],\ldots,A\[n\]$ is a permutation of $i\_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices to show that the inner while loop terminates when $i = 1$.

Suppose that the inner while loop never terminates when $i = 1$. Let $j$ be the maximal value which appears infinitely many times as $A\[1\]$. After finitely many iterations, $A\[1\] \leq j$ always. Since $A\[1\] = j$ infinitely many times, there must be some subsequent iteration in which $A\[1\] = j$. After that iteration, $A\[j\] = j$. In all subsequent iterations, $A\[1\] \leq j$, which ensures that $A\[j\]$ stays $j$, guaranteeing that $A\[1\]$ never equals $j$ again. However, this contradicts the definition of $j$.

The maximal number of iterations of the inner loop is A000375. There is no known formula!

I couldn't find the sequence for the maximal *total* number of iterations of the inner loop (over all $i$) on OEIS.

# Answer
> 1 votes
If you're familiar with cycle sort, you can start to see that this algorithm also operates in a similar way (although it's super inefficient).

Essentially, the inner loop doesn't terminate until the element in the current position $i$ is $i$. So when the outer loop moves on to the next element, you are guaranteed that the subarray to the left is sorted and in the final state ($1,2,3,\dots,i-1$)

Now to prove that the inner loop terminates... assume that it never terminates. So at a certain point, the value at $A\[i\]$ will loop through some values $t\_1,t\_2,\dots,t\_k$, none of which are $i$. Let $T=\\{\text{all values $A\[i\]$ loops through infinitely}\\}$. Clearly $|T|\<n-i$.

When $t\_2$ is at $i$, then $t\_1$ will be at position $t\_1$. For $t\_1$ to ever return to position $i$ (which it must as it's an infinite loop), there must be a $t\_p\>t\_1$ in $T$. Otherwise $A\[t\_1\]$ will never be affected by a reversal.

By symmetry this is true of all $t\_j \in T$. Hence $T$ must contain an element which is strictly larger than every element in $T$... a contradiction. Hence the inner loop terminates.

You could also say that this finite set $T$ must contain an infinite sequence of strictly increasing numbers, which is not possible.

---
Tags: algorithms, algorithm-analysis, sorting
---


# Question
Title: How do I solve a search problem on an infinite graph?
I have a search problem that requires me to find a path from $v\_s$ to $v\_g$ in the graph $G = (V, E)$ where $v\_s, v\_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \times V$ is an undirected set of edges connecting vertices. Both $V$ and $E$ can be infinite. Each edge has an associated cost $c: E \rightarrow \mathbb{R}$ and the cost of a path (an ordered set of edges) between adjacent vertices that leads from the start to the goal is the sum of the cost of all of its edges. My goal is to find the path with minimal cost (assume it exists).

From my understanding, because this graph could possibly have an infinite branching factor, A\* is not guaranteed to return a solution (or terminate). Are there any viable alternative algorithms that are designed for handling graphs with large or infinite state and action spaces? I'm not looking for guaranteed termination or optimality, just some names of algorithms that might be used in these sorts of problems as my search for "heuristic search infinite state space" doesn't turn much up.

# Answer
I believe you can use any algorithm for heuristic search. On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A\* or other standard algorithms for heuristic search.
> 1 votes

---
Tags: search-algorithms, heuristics
---


# Question
Title: Checking the existence of a pattern in a given prefix
I need to design an algorithm that given a string $T$ of length $n$, performs $O(n)$ preprocessing, and can then answer queries of the sort "does a string $P$ of length $m$ appear in $T$ before position $k$" in time $O(m)$. The algorithm should use a suffix tree.

Unfortunately there are not any good bioinformatics books with fair examples and practical methodologies. Dan Gusfield's book does not offer a solution manual.

# Answer
Recall that in a suffix tree for $T$, each leaf corresponds to a suffix of $T$, and is labeled by its position. Furthermore, each internal vertex corresponds to a common prefix of some suffixes of $T$. We label each internal vertex with the minimal position of a suffix covered by it.

Construct a suffix tree for $T$, and augment it by labeling the internal vertices as described above. Given a pattern $P$, traverse the suffix tree to find the vertex corresponding to $P$ (it might correspond to some extension of $P$), and check whether the minimal position written there implies that $P$ occurs before position $k$.
> 0 votes

---
Tags: algorithms, time-complexity, bioinformatics, suffix-trees
---


# Question
Title: How to solve this max contiguous subarray sum with a twist?
How to solve the max contiguous subarray problem, where we have an addition parameter $M$, and the contiguous subarray must include both $A\[M\]$ and $A\[M-1\]$?

For example, for the zero-indexed array $1, -4, 2, -2, 4, 1, -1, 1$, if $M=1$ then the contiguous subarray must include the first two elements, and so the answer is $-1$ (corresponding to the contiguous subarray $1,-4,2$).

The code I have right now without this "twist" is:

```
procedure MaxSubarraySum(A):
    current_sum <- 0
    max_sum <- (-infinity)
    N <- A.length
    for i <- 0 to N do:
        current_sum <- current_sum + A[i]
        if current_sum > max_sum then:
            max_sum <- current_sum
        endif
        if current_sum < 0 then:
            current_sum <- 0
        endif
    endfor

    return max_sum

```

But I'm stuck on how to change it so that `max_sum` always include $A\[M\]$ and $A\[M - 1\]$.

# Answer
Let the input array be $A\[1 \dots n\]$ and consider any contiguous subarray $A\[i \dots j\]$ of $A$ such that $i \le M-1$ and $j \ge M$ (that is, $A\[i \dots, j\]$ includes both $A\[M-1\]$ and $A\[M\]$).

The subarray $A\[i \dots j\]$ maximizes $\sum\_{k=i}^j A\[k\]$ if and only if:

1. $A\[i,\dots M-2\]$ is a (possibly empty) suffix of $A\[1 \dots, M-2\]$ that maximizes $\sum\_{k=i}^{M-2} A\[k\]$;
2. $A\[M+1,\dots j\]$ is a (possibly empty) prefix of $A\[M+1 \dots,n\]$ that maximizes $\sum\_{k=M+1}^{j} A\[k\]$.

This is easy to prove using a cut-and-paste argument. Notice that 1. and 2. are essentially the same problem, which can be solved by a trivial $O(n)$-time algorithm that computes the sum of all prefixes/suffxes of $A$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Time complexity of repeating a procedure $k$ times
Suppose I want to deploy the algorithm for finding connected components in a graph $k$ many times. Now the time complexity for finding connected components in an undirected graph is $O(v+e)$. Then what will be the time complexity, $O(k(v+e))$ or $O(ke)$?

Similarly, I have deployed a method $k$ times which requires $O(n^2+n^2)$. What will be its complexity, $O(kn^2)$ or $O(k(n^2+n^2))$?

# Answer
It is possible that an algorithm gathers information when it's running and doesn't throw it away. If gathering that information takes O(n^2) but solving the problem with the help of the information gathered only takes O(n), then solving the same problem k times could run in O(n^2 + kn). All depends on your algorithm.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Sort an array with a constant number of unsorted elements
I am trying to sort an array that I know to have a constant number of unsorted elements (elements that are not in their right place).
In the solution I looked at they say you can do this in $O(n)$ time:
you can find any unsorted element in $O(n)$ and then move it to the right place in $O(n)$ also. I am not seeing how you can do these things in $O(n)$.

I mean, I thought of an algorithm that iterates from 1 to $n$ ($n$ is length of the array), checks if the element at the index is in it's sorted place and if the answer is no then you can use partition for bringing it to the right place (partition works in $O(n)$).

Because I have a constant number of elements that are not in their right place I will use partition constant $\times n$ times which means the algorithm is $O(n)$ as asked. Problem is that checking for every index if the element in the index is in his right place is $O(n)$ and doing it for every index is $O(n)$ so it sums up to $O(n^2)$ so maybe the solution is not right. (Every other solution I wrote also has this problem)

I will be glad for any help.

# Answer
Denote the array by $A\_1,\ldots,A\_n$. If $A\_i \> A\_{i+1}$ then at least one of the two elements is out of place. We scan the array, and each time we find such a pair, we remove both elements. In $O(n)$ time, we obtain a sorted subarray $B$ together with $O(1)$ many unsorted elements, forming a set $C$. We sort $C$ in $O(1)$ and merge it with $B$ in $O(n)$.
> 5 votes

# Answer
An important observation is that an un-sorted array $A$ must contain at least one index $i$, such that $A\[i+1\]\<A\[i\]$ (assuming we are sorting in **ascending** order).

In particular, if you assume that the first $k$ elements are ordered (but the array is not fully ordered), then in the last $n-k$ elements you will have such a behavior, and in particular there will be a smallest index in which this behavior exists.

This allows us a way to find all "wrong" places in $O(n)$: start from scanning elements from the start, and scan until you find such an element. Then, fix the element's position in the array, and continue scanning again (its important to fix the element's position!)

Notice that the "fixing" process is assumed to take $O(1)$, since we are (currently) only interested in the scanning process.

---

Another way to sort elements (not using the quicksort and partitioning idea) is to use bubble sort. The total number of "bubble transfers" must be *at most* $c\cdot n$ where $c$ is the number of unsorted elements. Take a quick look at bubblesort to confirm that any other element will not take more than $O(1)$ time overall.
> 2 votes

---
Tags: sorting, arrays
---


# Question
Title: Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta
So far I've understood that because of the definition of $\Theta$, we have $c\_1n^2 \le f(n) \le c\_2n^2$.

I'm not sure how to proceed from there.

# Answer
> 1 votes
Since $f(n) \in \Theta(n^2)$ there exist two constants $n\_0$ and $c\>0$ such that $f(n) \ge c n^2$ for all $n \ge n\_0$.

Suppose then that $f(n) \in O(n)$. For some $n'\_0$ and $c'\>0$, we have $f(n) \le c'n$ for all $n \ge n'\_0$.

Selecting $n = \max\left\\{ n\_0, n'\_0, 1+\left\lfloor \frac{c'}{c} \right\rfloor \right\\}$ leads to the following contradiction: $$ c' n\ge f(n) \ge c n^2 \ge c \cdot \left(1+\left\lfloor \frac{c'}{c}\right\rfloor\right) \cdot n \> c \cdot \frac{c'}{c} \cdot n = c'n. $$

---
Tags: algorithms, asymptotics, proof-techniques
---


# Question
Title: How to find the compression method used on an unknown sequence of bytes?
I have a sequence of bytes: https://drive.google.com/file/d/17sfchPgsySi2ilIxLuBb1q-UUqq5lO87

What the data is, is unknown (see NOTE below).

I'm pretty sure this data is compressed in some way, due to the ent analysis results:

```
$ ent first-chunk

Entropy = 7.997831 bits per byte.

Optimum compression would reduce the size
of this 949674 byte file by 0 percent.

Chi square distribution for 949674 samples is 2962.74, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.3922 (127.5 = random).
Monte Carlo value for Pi is 3.157487727 (error 0.51 percent).
Serial correlation coefficient is 0.001738 (totally uncorrelated = 0.0).

```

According to the Chi square distribution the data is definitely not random. And compression is at an optimum. This leads me to believe the data is compressed and not encrypted. Is this a correct inference?

I've tried to decompress this data assuming the compression method to be zip, gz, xz, lz4, deflate, lzma, bzip, using tools like unlzma, gunzip, unzip, unlz4, zlib-flate etc. and none of them have worked. I always end up with a "file format not recognized" or a "invalid header check" error.

How do I find what compression method was used on the data? Could it be that the compression headers are missing?

---

NOTE:

This data is part of a slightly larger data file that is (possibly) the firmware and additional memory of a bluetooth speaker Flash memory. The whole file is: https://drive.google.com/file/d/1e9yG8xMkZ331C2TOTOzo9Y93L4abxX9F

# Answer
This file contains some repeated long byte sequences. In particular, the 66(decimal)-byte sequence beginning `49 97 CE...` occurs many times, and always at an offset that's a multiple of 66.

If you decrypt the file as a bitwise Vigenère cipher with that as the key, the result has a lot of structure. It appears to be divided into 66-byte records with 64 bytes of payload followed by a 2-byte checksum. (I assume it's a checksum because it's a deterministic function of the first 64 bytes, and the first 64 bytes sometimes have simple patterns like `01 01 01...` but the last two bytes always look like garbage.)

Beyond that, I can't figure anything out. Notably, while some records consist entirely of recognizable patterns (except the checksum), and some begin with recognizable patterns and end as garbage, none begin as garbage and end recognizably, which makes me think that there may be more to the encryption than a simple xor.
> 3 votes

# Answer
It's a reasonable hypothesis, but definitely not guaranteed, that it was compressed. There is general no way to know for sure which compression method was used. You've already tried some reasonable things to try.
> 0 votes

---
Tags: data-compression, entropy
---


# Question
Title: Show that P is closed against the Kleene star
I have that question that looks kinda easy at first but it is quite hard.

> Let $L\in P$. Prove that $L^\*\in P$

**my approach:**

I tried to generate a Turing machine but I got stuck with the thing of the poly time machine, I only managed to create a non-deterministic machine. I know that there is a complicated method with graphs or with dynamic programming, But I am asking for a full proof or a more gentle one, "computational models"-oriented and not with algorithmic approach, but both kinds of proof will be good.

# Answer
> 11 votes
Hint: Use dynamic programming. If the input is $x\_1 \ldots x\_n$, compute inductively whether $x\_1 \ldots x\_i \in L^\*$. Use the fact that you can check whether $x\_{j+1} \ldots x\_i \in L$ in polynomial time.

# Answer
> 6 votes
Just extending a bit more what Yuval Filmus has already said. Suppose your input is $x\_1\ldots x\_n$.

Let's use a memorization array $A$, where $A\[i\]$ is $True$ in case $x\_1 \ldots x\_i$ is in $L^\*$ and is $False$ otherwise.

Consider the deterministic Turing machine $M$ that does the following:

1. Set $A\[0\]$ to $True$, since the empty string $\epsilon$ is in $L^\*$.
2. Compute $A\[i\]$ bottom-up. If there is some $j$ with $0 \leq j \< i$ such that $A\[j\] = True$ (i.e. $x\_1 \ldots x\_j \in L^\*$) and $x\_{j+1} \ldots x\_i$ is in $L$, set $A\[i\] = True$. Put $A\[i\] = False$ otherwise. Do that for every $i$, starting at $1$ and ending at $n$. Notice that this step can be done in polynomial time, because we can decide in polynomial time whether $x\_{j+1}\ldots x\_i$ is in $L$ ($L$ is in $P$ by hypothesis).
3. If $A\[n\] = True$, **accept**. Otherwise, **reject**.

# Answer
> 1 votes
Let `w=x1..xn` be a word over some alphabet. Consider all options of continuous subwords of w. we have to choose the left index `:= i` and the right index `:= j` (which can be the same).

In total we have n choose 2 `(if i!=j) + n (if i=j)` subwords. any way this is bounded by n^2. we can check in polynomial time for each i,j (j\>=i) if xi..xj∈L. and because we have at most n^2 subwords we can check it for all i,j in polynomial time.

**Now the tricky part:** consider the directed graph:

`G. G = (V,E) V = { [i,j] | xi..xj∈L} U {v1,vn}` (we add 2 more vertex v1 and vn, you will see why in a minute).

`E = {(v1,[1,j]) | [1,j]∈V} U {([i,n],n) | [i,n]∈V} U {([i,j][j+1,k]) | [i,j],[j+1,k]∈ V}`

Now check if G has a directed path from v1 to vn in polynomial time. (BFS / DFS starting at v1). it easy to see G

# Answer
> 0 votes
Let $R$ be a polynomial-time decider for $L$. Construct a deterministic Turing machine $M$ that decides $L^\*$.

$M =$ "on input $w=w\_1...w\_n$:

1. Initialize a directed graph $G$ with $n$ nodes.
2. For $i=1; i\leq n; i++$:

3. For $j=1; j\leq n, j++$:
        4. Run $R$ on $w\_i...w\_j$. If $R$ accepts, add a vertex from node $i$ to node $min(j+1,n)$ of $G$.
3. Run any polynomial-time graph search on $G$ to find a path from node $1$ to node $n$. Accept if any exists. Else, reject."

Because we can construct a polynomial-time decider for $L^\*$, $L^\* \in P$.

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


# Question
Title: Are joins/pullbacks of bloom filters possible?
An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and respectively. The union of two bloom filters is the same as the bloom filter generated by the union of the sets, while the intersection will at least always be greater than or equal to the bloom filter generated by the intersection of the sets.

This got me thinking, if I use bloom filters to represent tuples, is there a way to do it that allows for efficient projections, cartesian products, and joins, so that it could be used as a heuristic for constraint propagation?

# Answer
> 1 votes
Ok, so the short answer to this question seems to be a "yes, but it grows quickly in size". You can view the bloom filters for each tuple element as vectors of bits. In that case, their tensor product will be a "bloom filter" for the cartesian product, where projection can be done by taking partial traces.

The downside of this is that the number of bits grows exponentially with the size of the tuple. You can mitigate this by maintaining a list of bloom filters for all pairs of tuple elements instead, which is still useful for constraint propagation, and gives projection as the intersection of the projection of each pair filter.

# Answer
> 0 votes
Nope. Bloom filters don't support those operations.

---
Tags: np-complete, sets, database-theory, constraint-satisfaction, bloom-filters
---


# Question
Title: a conjunctive normal form that is a tautology
Are there any examples of CNF formulas that are tautologies? Such that every clause contains different variables so phrases like (a or not a) are rejected?

# Answer
Take any clause in the formula. If all variables in that clause are different, we can always assign $0$ to a non-negated variable and $1$ to a negated variable. This makes that clause $0$. Therefore, it makes the CNF formula $0$. Thus, tautology is not possible unless there is $A \vee \neg A$ in every clause.

This is probably what Kyle Jones stated in his comment.
> 2 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Uniform convergence for a class of finite dimension
The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. Convergence of Stochastic Processes. Springer, 1984. However, I have trouble finding the proof. Anyone knows a reference?

Let $\Phi$ be a distribution over $\mathcal{X}$. With probability $1-\delta$ over $x\_1,...,x\_N\sim\Phi$, for all $a\in\mathcal{A}$ it holds that $\left|\frac{1}{N}\sum\limits\_{i=1}^na(x\_i)-\mathbb{E}\_{x\sim\Phi} a(x)\right|\le\sqrt{\frac{2d}{N}\ln\frac{eN}{d}}+\sqrt{\frac{1}{2N}\ln\frac{2}{\delta}}$

where $\mathcal{A}: \mathcal{X} \rightarrow \mathbb{R}$ is a set of real-valued functions and $d$ is the psuedo-dimensionof $\mathcal{A}$.

# Answer
> 3 votes
The keyword to look for is Dudley's chaining integral, see e.g. Vershynin's book "High Dimensional Probability" which contains a chapter on the chaining technique. Chaining allows us to bound the empirical Rademacher complexity in terms of the empirical $L\_2$ covering numbers of $\mathcal{A}$. Your result is directly obtained from the chaining integral and a result (which is think is credited to Dudley-Pollard) which relates the $L\_1$ covering numbers (irrespective of the distribution) to the pseudo dimension, see e.g. theorem 4.2 in these notes. You still need to go from $L\_2$ covering to $L\_1$ somehow, this is easy when the functions are binary valued.

---
Tags: machine-learning, reference-request, learning-theory
---


# Question
Title: In C++ how does "sizeof(array)/sizeof(array[0])" give the number of elements in an array? Why isn't it affected by the length of each element?
I'm playing around with C++ and was looking at how to loop through an array of unknown length. The following code was suggested and works perfectly from the little testing I've done:

```
std::string words[5] = {"Lorem ipsum dolor sit amet orci aliquam.", "Hi", "Welcome", "World", "LoopyDoopyDoo"};
for (int i = 0; i < sizeof(words)/sizeof(words[0]); i++){
     DO STUFF
}

```

From what I've read the sizeof() operator returns the size of a variable in bytes.

What I don't understand is how this isn't affected by the number of characters in each element of the array. I printed out the sizeof() value to check and the array size is always evaluated at 160 bytes and element 0 as 32 no matter how many characters are present. I thought that it might be allocating 32 bytes but not using them all so I stored some text that should use 40 bytes, but still no change. Am I missing something here? Is text stored differently in C++?

Any help in understanding how this actually works would be appreciated, thanks!

# Answer
C and C++ are low-level languages that give the programmer precise control over the memory layout. Each object takes a constant amount of memory which is fully determined (on a given implementation) by its type. The `sizeof` operator lets programs know this size.

An object may contain pointers. The data that the pointers points to, if any, is not part of the object. The size of an object is what some higher-level language might call the “shallow” size: it only considers the object itself, not other objects that the object references.

For example, an object of type `std::string` has a certain size. This size is independent of the content of the string. This means that the only way to implement `std::string` for strings of unbounded length is for the `std::string` object to contain a pointer to the actual content of the string. `sizeof(std::string)` is the size of this pointer plus other data that the `std::string` type keeps track of (that would typically be the length of the string, the size allocated for the string, a pointer to the class's method table). It has no relation with the length of the string.

An array is an object which consists of several objects of the same type. Since the elements of the array all have the same type, they all have the same size.
> 1 votes

---
Tags: arrays, loops, c++
---


title: "NP-complete" optimization problems

text:
# Question
Title: "NP-complete" optimization problems
I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. However, I am not exactly sure what the term NP-complete means in the context of an optimization problem. Does this just mean that the corresponding decision problem is NP-complete? And does that mean that the optimization problem may in fact be harder (perhaps outside of NP)?

In particular, I am concerned about the fact that while an NP-complete decision problem is polynomial time verifiable, a solution to a corresponding optimization problem does not appear to be polynomial time verifiable. Does that mean that the problem is not really in NP, or is polynomial time verifiability only a characteristic of NP decision problems?

# Answer
> 16 votes
An attempt on a partial answer:

*Decision problems* were already investigated for some time before *optimization problems* came into view, in the sense as they are treated from the approximation algorithms perspective.

You have to be careful when carrying over the concepts from decision problems. It can be done and a precise notion of *NP-completeness* for optimization problems can be given. Look at this answer. It is of course different from the NP-completeness for decision problems, but it is based on the sames ideas (reductions).

If you are faced with an optimization problem that doesn’t allow a verification with a feasible solution, then there is not much you can do. That is why one usually assumes that:

* We can verify efficiently if the input is actually a valid instance of our optimization problem.
* The size of the feasible solutions is bounded polynomially by the size of the inputs.
* We can verify efficiently if a solution is a feasible solution of the input.
* The value of a solution can be determined efficiently.

Otherwise, there is not much we can hope to achieve.

The complexity class $\mathrm{NP}$ only contains decisions problems per definition. So there aren’t any optimizations problems in it. And the *Verifier-based definition* of $\mathrm{NP}$ you mention is specific to $\mathrm{NP}$. I haven’t encountered it with optimization problems.

If you want to verify that a solution is not just feasible, but also optimal, I would say that this is as hard as solving the original optimization problem because, in order to refute a given feasible and possibly optimal solution as non-optimal, you have to give a better solution, which might require you to find the true optimal solution.

But that doesn’t mean that the optimization problem is harder. See this answer, which depends of course on the precise definitions.

# Answer
> 0 votes
For the relation between decision and optimization (search) problems, take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search, SIAM Journal of Computing 23(1), feb 1994. In a nutshell: If the decision problem is NP-complete, the search problem is hard too, and can be solved calling the decision problem's solver a polynomial number of times.

# Answer
> 0 votes
You need to look at every individual optimisation problem. Typically you want a “solution” which maximises the value v, while a decision problem would be “is there a solution with a value \>= k”

The question is: if you can solve the decision problem, repeatedly, does that allow you to solve the optimisation problem? Usually it lets you solve “what is the maximum value of any solution” using binary search. The difficult part is finding a solution when all you know is that there *is* a solution.

# Answer
> 0 votes
You can easily define NP-hard optimisation problems: We call a decision problem D NP-hard if any decision problem in NP can be reduced to D in polynomial time. And we can use the same definition for *any* problem P: P is NP-hard if any decision problem in NP can be reduced to P in polynomial time.

The problem is defining something analogous to NP. If we have a problem “What is the smallest possible value of v”. This is equivalent to asking “is there a solution with a value v” and “is there no solution with a value v-1”. So we can see many optimisation problems as a combination of a problem in NP, and a problem in co-NP.

# Answer
> -1 votes
The reason most optimization problems can be classed as P, NP, NP-complete, etc., is the Kuhn-Tucker conditions. I'll talk in terms of linear-programming problems, but the KTC apply in many other optimization problems. For each optimization problem there is a dual. If the goal in the original problem is to maximize some function, then the dual (usually) has a function to be minimized.\* Feasible, but non-optimal solutions to the original problem will be infeasible/invalid for the dual problem, and vice-versa. If, and only if, a solution is feasible for the primary and dual, it is an optimal solution for both. (Technically, may be one of a large number of optimal solutions which give the same result.)

So finding an optimal solution of an optimization problem is equivalent to finding a valid solution for the primary and dual. You may use optimization algorithms to find that solution, but the overall process is an existence proof.

* If you want to flip from minimization to maximization, multiply the objective function by -1.

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


title: color adjustment algorithm

text:
# Question
Title: color adjustment algorithm
Got a problem I'm not sure how to approach.

I'm being given a string of text with indeterminate length, around typical "body text" size. The text is a solid color, and the background can be a solid OR a gradient of one or more colors of varying luminance. The goal is to make the text readable across the entire background while adjusting the color channels as little as possible.

How could I find the SMALLEST possible color adjustments to the foreground and/or background that would make the text readable, according to WCA standards or others?

# Answer
> 2 votes
The text has a luminance value $t\_0$ and the background occupies a luminance interval $\[L\_0,H\_0\]$, $L\_0 \le H\_0$. I think what you want is to ensure a separation of at least some $s$ between them. There are many degrees of freedom here; one way to capture most of them is to decide beforehand on a way to penalise changes in these variables, as well as the penalty for changing the background interval width $H-L$, and then look for a solution that minimises this penalty cost.

We could use a linear cost model, where the absolute value of the change in each variable is penalised, but this has the disadvantage that optimal solutions are not always unique. So let's use a quadratic cost model (least squares), with penalty weights $c\_t, c\_L$ and $c\_H$ for changes to the main variables, and also a weight $c\_d$ for the penalty for changing $H-L$ (i.e., stretching or squashing the background luminance range). Then you want to choose $t, L$ and $H$ to minimise $$p = c\_t(t-t\_0)^2 + c\_L(L-L\_0)^2 + c\_H(H-H\_0)^2 + c\_d(H-L-H\_0+L\_0)^2$$ such that $L \le H$ and either $t \ge H + s$ or $t \le L - s$. This gives a lot of flexibility: Set any of the $c$-parameters to zero to express that you don't care about changes in the corresponding quantity; set it extremely high to try hard to avoid changing it. A sensible first choice might be to set them all equal to 1, and if that yields solutions that "look wrong", increase the weights of whichever values moved around too much.

If $t\_0$ is already separated from $\[L\_0, H\_0\]$ by $s$, then leaving it unchanged is the optimal solution. Otherwise, intuitively, an optimal solution must have a tight gap, i.e., either $t = H+s$ or $t = L-s$. This can be solved by solving for each of the two cases separately and choosing the better one.

To solve for the first case, substitute $t = H+s$, find the partial derivatives of $p$ w.r.t. the two remaining variables $H$ and $L$, set these to zero:

$$\begin{align} p & = c\_t(H+s-t\_0)^2 + c\_L(L-L\_0)^2 + c\_H(H-H\_0)^2 + c\_d(H-L-H\_0+L\_0)^2\\ \frac{\partial p}{\partial L} & = 2c\_L(L-L\_0) + 2c\_d(H-L-H\_0+L\_0) = 0\\ \frac{\partial p}{\partial H} & = 2c\_t(H+s-t\_0) + 2c\_H(H-H\_0) + 2c\_d(H-L-H\_0+L\_0) = 0 \end{align}$$, and solve the resulting set of simultaneous equations for these variables to find the minimum:

$$\begin{align} L & = \frac{c\_LL\_0 + c\_d(H\_0-H-L\_0)}{c\_L - c\_d}\\ H & = \frac{c\_t(t\_0-s) + c\_HH\_0 + c\_d(L+H\_0-L\_0)}{c\_t + c\_H + c\_d}\\ & = \frac{c\_t(t\_0-s) + c\_HH\_0 + c\_d(\frac{c\_LL\_0 + c\_d(H\_0-H-L\_0)}{c\_L - c\_d}+H\_0-L\_0)}{c\_t + c\_H + c\_d} \end{align}$$

Having computed the optimal value of $H$, you can substitute this back into the expressions for $L$ and $t$, and then calculate $p$ for this case. The derivation for the $t=L-s$ case is very similar. Finally, pick whichever gives the lower $p$ value.

---
Tags: algorithms
---


# Question
Title: Why is it not always possible to compute the centroid of feature vectors?
Hi in the data mining and machine learning course that I'm taking there is a subject on feature spaces and there is this part about feature vector aggregation and metric spaces that I don't really understand. Now our curriculum is basically a huge presentation and the whole information about feature vector aggregation fits on one slide, anyway what I don't understand is this:

For a given sample $D$ the centroid can be computed as $C\_D = \frac{1}{|D|}\cdot\sum\_{o\in D} o$

and then on the slide it says, quote:

> In a general metric space (that is, not a vector space), where we only have pairwise distances, it might not be possible to compute a centroid

I don't really think I understand what "only pairwise distance" means (my guess is it has something to do with the fact that a metric space defines the distances between all pairs of elements in its set) or why the consequence of it is that you can't always compute the centroid.

I read somewhere that metric spaces does not have to define addition or scaling and if that is the case it makes sense to me that you can not calculate the centroid. Is this what it essentially is about or am I completely misunderstanding something?

# Answer
A metric space consists of a set $X$ of "points" and a metric $d\colon X \times X \to \mathbb{R}\_{\geq 0}$ (giving the "distance" between any two points) which satisfies the following constraints:

1. Symmetry: $d(x,y) = d(y,x)$ for all $x,y \in X$.
2. Non-triviality: $d(x,y) = 0$ if and only if $x = y$.
3. Triangle inequality: $d(x,y) \leq d(x,z) + d(z,y)$ for all $x,y,z \in X$.

The definition of centroid doesn't make sense for a general metric space, since you cannot perform arithmetic on the elements of $X$.
> 3 votes

# Answer
> In a general metric space (that is, not a vector space), where we only have pairwise distances, it might not be possible to compute a centroid

The above quote is correct but it is misleading. A centroid is only defined for the Euclidean space. It is the coordinate-wise average of each point in the dataset. Another definition of a centroid is that it is a point in the Euclidean space that minimizes the sum of squared distances of the points in the dataset $\mathcal{D}$, i.e., $$\mu = \arg min\_{c \in \mathbb{R}^{d}} \sum\_{x \in D}\\|x-c\\|^{2}$$.

As Yuval said the concept of a centroid is meaningless in general metric space.

Let us look at a practical example of a metric space, where the above definition does not make any sense. Consider an undirected graph $G = (V,E)$ with weights on the edges. Such a graph could be a representation of a road/railway network of a country, i.e., a node representing a city, an edge representing a road, and weight representing the length of the road.

Note that cities can be mapped to a 2-D Euclidean space. However, the Euclidean distance between them is not useful here since there might not be a direct road connecting every pair of two cities. A more meaningful measure would be the shortest path distance between every pair of two cities/nodes in the graph.

Suppose, we want to establish an industrial site in one of the cities such that the sum of transportation cost to every other city is minimized. In other words, we want to find a city $c$ that minimizes the following objective function:

$$\mu = \arg min\_{c \in V} \sum\_{v \in V}d(v,c)$$

This definition is similar to the definition of a centroid. However, here $d(v,c)$ is the shortest path distance between the cities $v$ and $c$, instead of the Euclidean distance. Also, note that the space is a metric space since the shortest path distances follow triangle inequality. The other properties of the metric space are also easy to verify.

Opening the industry at the centroid makes no sense at all since the Euclidean distances are not representing the actual transportation cost.
> 0 votes

---
Tags: data-mining, features
---


# Question
Title: Proof of correctness of reversal algorithm for array rotation
We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if `A = {1, 2, 3, 4, 5, 6, 7}` then for `d = 2`, the resultant rotated array is `{3, 4, 5, 6, 7, 1, 2}`.

One algorithm which does this goes as follows:

1. Reverse `A[0..d-1]` (0-indexing)
2. Reverse `A[d..n-1]`
3. Reverse `A[0..n-1]`

These three steps surprisingly rotate the array correctly. What is the math behind this algorithm? Why does it give a correct solution? It feels magical to me. I am not able to put up a formal proof of its correctness.

# Answer
Here is a proof by picture, which follows the steps of the algorithm: $$ 0,\ldots,d-1,d,\ldots,n-1 \\ d-1,\ldots,0,d,\ldots,n-1 \\ d-1,\ldots,0,n-1,\ldots,d \\ d,\ldots,n-1,0,\ldots,d-1 $$ You can easily turn this into a formal proof by giving a formula for the permutation after each step, which you can easily prove correct.
> 3 votes

# Answer
First, we can see the rotation problem (as described in the question) as equivalent to: interchange of two blocks of elements which are at index-ranges $\[0, d-1\]$ and $\[d, n-1\]$. Let's call these blocks, with elements exactly as the original array $A$, as $B\_1$ and $B\_2$. As result of this interchange, the order of these blocks in $A$ should change from $(B\_1,B\_2)$ to $(B\_2,B\_1)$.

In the provided algorithm, after the first two steps, array $A$ would contain:

$B\_1$(reversed), followed by, $B\_2$(reversed).

Now, if this modified array $A$ is read/iterated from end to start, it should return elements in order:

$\[B\_2$(reversed)(reversed) $\leftrightarrow B\_2\]$, followed by, $\[B\_1$(reversed)(reversed) $\leftrightarrow B\_1\]$.

which is the intended order. The third step modifies $A$ to reflect such order, by reversing.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: maximal independent set on grid graph proof
I'm trying to figure out proof of maximum independent set from: this link. (1b part).

And I'm bit confused why exactly sum of $w(v)$ is less than or equal to sum of $w(v')$. Shouldn't it be other way around? As we define $v'$ if it is in $T$ and is in $S$

# Answer
> As we define v′ if it is in T and is in S

I think you're misinterpreting the definition of $v$:

> For each $v \in T$, define $v'=v$ if $v\in S$ or as its neighbor in $S$ otherwise

$v'$ is *always defined*; it's just a question of *what* it's defined to be. The above definition means that, if $v \in S$, $v'$ is defined to be $v$, and if $v \notin S$, $v'$ is defined to be $v$'s greater-or-equal-weight neighbour in $S$ (the existence of which was established in part 1a). Then $w(v) \le w(v')$ for each $v \in T$ by construction.

(This is the only way I see to parse the definition that makes grammatical sense, though I think it could be worded better, to prevent people reading "define $v'=v$ if $v\in S$" as a "parenthesised unit".)
> 0 votes

---
Tags: algorithms, graphs, np-hard, approximation
---


# Question
Title: How to prove that a binary heap can't be sorted with complexity that better than O(nlogn)
I am trying to prove that you can't sort binary heap with better complexity than O(nlogn). We proved at class that every sort based on comparison can't have better cocmplexity than O(nlogn) and i know nothing about the items in the heap (except its a heap) so you can't use radix sort or linear sort. Problem is i feel like its not enough to say this things. I don't know how i am supposed to prove it and i am searching for help.

# Answer
> 1 votes
A binary heap with $n$ elements can be built in time $O(n)$. If there was a (comparison based) sorting algorithm capable $A$ of sorting the elements in a heap in time $o(n \log n)$ then you could obtain a (comparison-based) sorting algorithm $A'$ that works for arbitrary sequences $S$ of $n$ elements. Algorithm $A'$ is as follows:

* Construct a heap $H$ from $S$.
* Execute $A$ with input $H$.

Such an algorithm requires time $O(n) + o(n \log n) \in o(n \log n)$ and hence it contradicts the $\Omega(n \log n)$ lower bound on comparison-based sorting algorithm. Therefore, algorithm $A$ cannot exist.

---
Tags: sorting, arrays, heaps
---


# Question
Title: Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"
Do two halting Turing machines accept the same language?

Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"):

Let M be an arbitrary Turing machine. Let M′ be a Turing machine that on input x, simulates M (on some predefined input) for |x| steps and accepts if (and only if) M halts within |x| steps. If M doesn't halt then M′ accepts the empty language. If M does halt then the language M′ accepts is non-empty. This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether M′ is equal to the machine accepting the empty language.

How is this proof using "reduction from the Halting problem to the problem of detecting equality?" Asking whether a TM halts in a finite number of steps (|x| in the proof above) is decidable. So how would the problem of detecting equality outlined above provide a way of solving the halting problem?

In other words my problem with understanding the proof is this: How does detecting equality in the way described above decide whether the machine M halts on input x?

# Answer
Let $\langle M, w\rangle$ be the input to the halting problem.

We will construct $M'$ that simulates $M$ as you described with $w$ as the predefined input.

As you have said, $L(M')\neq \emptyset\iff M \text{ halts}$. However, we simulated $M$ on $w$, hence $L(M')\neq \emptyset \iff M \text{ halts on } w \iff \langle M, w\rangle\in H\_{TM}$ where $H\_{TM}$ is the halting problem.

Define the function $f$ that given $\langle M, w\rangle$ will output $\langle M', M\_{empty}\rangle$, where $M\_{empty}$ is a TM that immediately rejects.

We will have: $\langle M, w\rangle \notin H\_{TM} \iff L(M')= \emptyset \iff L(M')\neq L(M\_{empty})\iff \langle M', M\_{empty}\rangle\in EQ\_{TM}$

$f$ is computable, and hence it is a reduction from $\overline H\_{TM}$ to $EQ\_{TM}$.

$\overline H\_{TM}$ is not decidable, and thus also $EQ\_{TM}$ isn't decidable
> 0 votes

---
Tags: undecidability, proof-techniques, halting-problem
---


# Question
Title: How to do binary search on a path in a binary heap
I am trying to solve this question:

Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap\[i\]$ in time $O(\log(\log n))$.

**My solution:**

Before the loop, I will create a new linked list and initiate $heap\[i\]$ to be the first item in the list. Then, I will run a loop on the heap that will start from index $i$, and in every iteration, it will extract the parent of the item in the index $i$ to a new array and will break after extracting the root of the heap.

Then, I will use binary search on the new array (I know that every parent in the heap is bigger than its children. So the new array is already sorted). The problem is that the extraction of the parents cost me $O(\log i)$ which can be in the worst-case $O(\log n)$, and for that reason, my solution can't work.

I will be grateful for any help.

# Answer
Note that a path from the root to $heap\[i\]$ is in the sorted order. Moreover, the path length is $O(\log n)$. You just need to do binary search on this path. For that, you need to access the $i^{th}$ ancestor of any node in the heap in $O(1)$ time. Assuming $1$ based indexing, the $1^{st}$ ancestor of $heap\[i\]$ is located at $\lfloor \frac{i}{2} \rfloor$ location in the array. The $2^{nd}$ ancestor of $heap\[i\]$ is located at $\lfloor \frac{i}{4} \rfloor$ location, and so on. Using it you can easily perform binary search on the path from root to $heap\[i\]$ in $O(\log \log n)$ time.

**Pseudocode:**

Assume that we have a *min heap*. Initialize, start = $1$ and end = $h = \lfloor \log(i) \rfloor$

```
BinarySerach (start, end)

mid = (start + end)/2
index of mid = i/(2^(h- mid)) //(h-mid)^th ancestor of i

if (end-start = 1)
    if (heap[index of mid] == x) return "YES"; otherwise "NO".

if (heap[index of mid] >= x)
   return BinarySearch (start, mid)
else
   return BinarySearch (mid+1,end)

```
> 2 votes

---
Tags: search-algorithms, heaps, search-problem, binary-search
---


# Question
Title: CFG and PDA for the set of strings in $\{a, b, c\}^∗$ such that the number of b’s is equal to the sum of number of a’s and c’s
I'm trying to find the CFG and PDA for the above language. I have so far come up with this
$S \to S\_1S\_2 \\ S\_1 \to aS\_1b \\ S\_2 \to bS\_2c$
However, I realized that this is just a subset of the required language. How do I consider the remaining ones? Also, how do I construct a PDA for it? Any help is appreciated.

# Answer
For the PDA, I think you use the stack to track the number of A plus the number of C minus the number of B seen so far, using both positive and negative tokens:

* If the stack is empty and you see an A or a C, you push a "+1" token.
* If the stack is empty and you see a B, you push a "-1" token.
* If the stack is not empty and you see the kind of token that's already on there (e.g. you have a +1 token and you see an A or a C), then you push another of the same token.
* If the stack is not empty and you see the wrong kind of token (e.g. there's a "-1" token on the stack and you see an A or a C), you pop one token.

Depending on your formalisation of PDA you may want to start off by pushing a "zero" token in order to check whether the stack is "logically empty" or not.

The stack keeps the invariant that there can never be both a "+1" and a "-1" token on it at the same time.

The word is in the language if and only if the stack is (logically) empty at the end of the string.
> 1 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: Conditions for an Language to be infinite
given 'r' , a regular expression that does not include λ or ∅, What are the Conditions of 'r' so that L(r) would be infinite?

# Answer
> 1 votes
Regular expressions correspond to a simple recursive definition, which starts with the symbols from some alphabet and extends them with applications of three operators: alternation, concatenation and Kleene closure.

So ask yourself: Which of these operators can produce an infinite set?

---

Formal definition:

Let $\Sigma$ be a finite set of symbols. Then the set of regular expressions $R\_\Sigma$ is the smallest set of expressions which can be constructed using these rules:

* Every $c \in \Sigma$ is in $R\_\Sigma$.
* $\lambda$ and $\emptyset$ are in $R\_\Sigma$.
* If $r$ and $s$ are regular expressions over the alphabet $\Sigma$ then so are:

+ $(r+s)$
    + $(rs)$
    + $(r^\*)$

A standard proof technique for properties of regular expressions is to apply mathematical induction to this definition.

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


# Question
Title: Non-brute force algorithm for a Eulerian like path
I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one and no more than a dozen. I want to find the path that goes to as many vertexes and edges as possible without using any edge more than once.

In addition there are a few special cases that I would like to add but an algorithm that doesn't solve for these is fine:

* There are pairs of vertexes that are connected with multiple edges. I can traverse multiple of these edges but I cannot immediately return to the previous vertex I was at without first going to another vertex.
* There are some edges that are one way.
* Some vertexes will change the destination of edges connected to themselves depending on the edge you arrived from. In practice this is always a vertex with two edges that if arrived from one edge will change the other edge to return to the source of the first edge and if arrived from the other edge the first will not change. In theory it doesn't have to be though.

I know this problem cannot be solved in polynomial time and I have thought of ways to speed up the brute force method I am just wondering if anyone else has any ideas.

# Answer
Regarding the problem of visiting as many vertices/edges as possible without using any edge twice: one can look at this problem as the problem of finding an Eulerian subgraph with a maximum number of vertices/edges. Or alternatively, as the problem of deleting a minimum number of vertices/edges so as to make a graph Eulerian.

You might be interested in the following paper, which studies the complexity of such problems in detail. In particular, they show several polynomial-time solvable or fixed-parameter tractable cases. In particular, the edge deletion problems are solvable in n^3 time if a constant number of edge deletions is sufficient.

https://doi.org/10.1007/s00453-012-9667-x
> 0 votes

---
Tags: np, graph-traversal, hamiltonian-path, eulerian-paths
---


# Question
Title: Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS?
The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS.

**Problem 7-1.b**

*Hoare's partition algorithm* from the book.

**Part b:** Assuming the subarray $A\[p,\cdots,r\]$ contains at least two elements, show that the indices $i$ and $j$ are such that we never access an element of outside the subarray $A\[p,\cdots,r\]$

---

I think this it is not possible to prove this because this statement is not correct, i.e., during the course of execution we happen to access elements outside the array. Here I prove the converse of **part b** by using a counter-example.

Consider the array A = \[1,2\]. Let p = 1 and there r =2.

* Initially, $i = 0$, $j = 3$ and $x = 1$.
* After the loop $5-7$ executes once, $j$ becomes 2 and the condition in line 7 fails resulting the termination of the loop $5-7$.
* Now we reach the loop $8-10$. Now let's look at the state after this loop executes twice. $i = 2$ and the condition in line 10 still holds. Therefore the loop executes a third time and $i$ becomes 3.
* Now to test the condition in line 10 we access $A\[3\]$ which is outside the subarray $A\[1,\cdots, 2\]$

---

Is there a mistake in my reasoning or is the problem statement wrong?

# Answer
> 1 votes
The problem statement is correct.

I think you getting confused about: repeat $j \gets j-1$ until $A\[j\] \leq x$. It means that if $A\[j\]\>x$ then do $j \gets j-1$.

Similarly, loop $8-10$ means that if $A\[i\]\<x$ then do $i \gets i+1$.

Therefore, the algorithm executes in the following way on $A = \[1,2\]$:

1. After the loop $5-7$, $j$ becomes $1$ since $A\[2\] \> x$.
2. After loop $8−10$, $i$ becomes $1$ since $A\[1\] = x$.
3. Since $i = j = 1$, the algorithm terminates and returns $1$.

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: Compression algorithm using key value mapping
Would it be possible to do better than standard compression if you fed a bunch of zipped files through a machine learning algorithm that kept track of the most common bit sequences and produced a lookup map, with a heuristic for giving the longest / most commonly used sequences the shortest key values?

The compression algorithm would then go through a zip file and replace sequences from the map with their lookup key. If the map was big enough (both compress / decompress parties would have access to it) could you reliably get a smaller file than the original?

Some doubts I have about this method:

* Files your learning algorithm had never seen before wouldn't contain many sequences that had been seen before
* The keys would have to be smaller than the sequence of bits it replaces in order to save space, maybe it quickly runs out of keys smaller than common sequences
* Zip files don't repeat bit sequences very often so we wouldn't be able to find large pieces to replace

# Answer
All of your doubts are correct.

What you're describing is called static-dictionary compression. It works well for short text strings (see smaz, for example, though I doubt that its fixed dictionary was obtained by machine learning).

It would probably not accomplish much when applied to zip files because deflate doesn't tend to produce common bit sequences that are long enough to be further compressed – because eliminating those sorts of sequences is essentially its job.

A weakness of deflate is that its maximum copy length is 258, which means that long repeating sequences of bytes will tend to produce repeating (offset,length) pairs in the output, which can be further compressed by another pass. But the encoding of the repeated (offset,length) pair varies from file to file (even the length part, because the bit pattern used to represent a length of 258 isn't fixed), so you would need a dynamic dictionary to benefit from this.
> 2 votes

---
Tags: data-compression
---