# Question
Title: If each pixel contains the channels for the 3 primary colours, why can a 1-bit picture only be presented in white and black?
I'm an igsce student. I'm taking computer science as an OL subject this year.

Pixels are the small squares which make an image. Inside each pixel there are 3 channels: one for blue, one for green, one for red. The three primary colours from which any other colour can be made. And that's how I imagine it: When we say an image is 8-bits we actually mean that for each channel (in one pixel) of green, blue or red there are 8 bits. So green can have 255 shades/intensities/brightness and so on for the rest of the colours.

So even for a 1-bit image, each pixel **contains 3 channels one for each of the primary colours. The only difference is that there's only 1 intensity/brightness/quantity for each colour.**

So even in 1-bit image the three primary colours still exist so more colours other than black and white can be made by mixing the three colours together, 8 colours to be exact. Why is it said then that a 1-bit image is only black and white?

# Answer
> 3 votes
Please read the Wikipedia article 8-bit color.

> *8-bit color graphics are a method of storing image information in a computer's memory or in an image file, so that each pixel is represented by one 8-bit byte. The maximum number of colors that can be displayed at any one time is 256 or 2⁸.*

In other words, the problem is that 8 bits mean that all three primary colors red, green, and blue, are encoded in 8 bits in total. From Wikipedia:

> The simplest form of quantization frequently called 8-bit truecolor is to simply assign 3 bits to red, 3 to green and 2 to blue (the human eye is less sensitive to blue light) to create a 3-3-2
>
> ```
> Bit    7  6  5  4  3  2  1  0
> Data   R  R  R  G  G  G  B  B
>
> ```
>
> 8-bit color image, but this process is sub optimal. There could be different groupings of colors that make evenly spreading the colors out inefficient and likely to misrepresent the actual image. Because the color map doesn't need to have every color in it and just needs to accurately represent the more color dense image, an arbitrary color can be assigned to each of the 256 available color 'slots' on the map. \[...\]

Concluding, 1 bit means that you can have only two states, e.g. black/white.

---
Tags: colorings, digital-image-processing
---


title: Understanding P vs NP

text:
# Question
Title: Understanding P vs NP
I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial time. Furthermore, if we consider the church turing thesis, and if P != NP, then no computational formalism can solve NP-complete problems in polynomial time. Would I be fine saying this?

# Answer
> 5 votes
> I know that NP-complete problems cannot be solved in polynomial time.

We don't know this. This is exactly the P vs NP question. NP-complete problems can be solved in polynomial time iff P=NP.

> If P ≠ NP, then all problems in NP cannot be solved in polynomial time.

P is a subset of NP, so some problems in NP can definitely be solved in polynomial time.

> Furthermore, if we consider the Church-Turing thesis, and if P ≠ NP, then no computational formalism (ever) can solve NP-complete problems in polynomial time.

The Church–Turing thesis isn't really relevant here, since it is about *computability* rather than *complexity*. It could be that P ≠ NP but NP-complete problems can be solved in polynomial time by randomized algorithms or by quantum algorithms (though both of these are considered unlikely).

---
Tags: np-complete, decision-problem, p-vs-np
---


title: Connection of different buses to memory

text:
# Question
Title: Connection of different buses to memory
The address bus(of cpu) is connected to a digital decoder inside the memory which sets 1 pin logic high and activates the read/write operation of the memory let's say DRAM. Is the data bus(of cpu) connected directly to the bit line of the DRAM(columns) or are there some in between steps?

# Answer
> 2 votes
**With all due reserve.**

DRAM chips today are placed on DIMMs which look like

The black chips seen on the DIMM are the DRAM chips. DRAM chips inside look like

Each big gray square is called a bank. One bit of DRAM looks like

You see that between the output of the DRAM chip and the bit stored in the capacitor there is a sense amplifier. That is used to amplify the voltage of the stored energy. You need this because the energy stored in one capacitor is not strong enough to just be sent over to the bus. The sense amplifier is detailed at http://pnrsolution.org/Datacenter/Vol3/Issue2/119.pdf.

> Sense amplifier is not only an amplifier but a positive feedback device that quickly pushes the readout voltage to 1 or 0. The gates of the DRAM cells are tied to the row decoder and the bit-line pairs are connected to the sense amplifier.

A detailed explanation of the hardware interface of DRAM chips is found at https://compas.cs.stonybrook.edu/~nhonarmand/courses/sp15/cse502/res/dramop.pdf. This pdf is very detailed. For the read operation it says:

> To read the data from a memory cell, the cell must be selected by its row and column coordinates, the charge on the cell must be sensed, amplified, and sent to the support circuitry, and the data must be sent to the data output. In terms of timing, the following steps must occur:
>
> 1. The row address must be applied to the address input pins on the memory device for the prescribed amount of time before RAS goes low(tASR) and held (tRAH) after RAS goes low.
> 2. RAS must go from high to low and remain low (tRAS).
> 3. A column address must be applied to the address input pins on the memory device for the prescribed amount of time (tASC) and held (tCAH) after CAS goes low.
> 4. WE must be set high for a read operation to occur prior (tRCS) to the transition ofCAS, and remain high (tRCH) after the transition of CAS.
> 5. CAS must switch from high to low and remain low (tCAS).
> 6. OE goes low within the prescribed window of time. Cycling OE is optional; it may be tied low, if desired.
> 7. Data appears at the data output pins of the memory device. The time at which the data appears depends on when RAS (tRAC),CAS (tCAC), and OE (tOEA) went low, and when the address is supplied (tAA).
> 8. Before the read cycle can be considered complete,CAS and RAS must return to their inactive states (tCRP, tRP).

To be clear, this is how DRAM chips work with their own pins. This is not how the DIMM itself works. The DIMM is a bit different. You can look at JEDEC specifications on DDR RAM to see how DRAM work a bit better. For example, the JESD79-4 standard is about the DDR4 SDRAM (Synchronous DRAM) (http://www.softnology.biz/pdf/JESD79-4B.pdf). In this document is stated how bank groups and banks are selected. The address pins are multiplexed meaning that depending on if RAS or CAS is set then address pins will either select a column or a row. Page 5 is especially interesting because it describes the actual pins of the DDR4 DRAM chip.

To determine how actual DIMMs work, one can look at other JEDEC specifications (https://www.jedec.org/standards-documents/docs/module4\_20\_26\_annexa). This website presents the actual document that you must be registered to download. This documents specifies the pin description of DDR4 DIMMs. The DDR4 DIMM is 288 pins (144 on each sides). The pins that are important for your question are the DQ pins. There are 64 DQ pins which is not for no reason. It is because DDR4 supports 64 bits machines. The DQ pins are probably connected to the data bus of the computer.

For actual interface between memory and Intel CPUs you can look at the External Memory Interface Handbook Volumes 1, 2 and 3 from Intel. These volumes are available on internet and are pretty lengthy. They are pretty hard to understand. The document at https://www.intel.com.br/content/dam/doc/datasheet/core-i5-600-i3-500-pentium-6000-datasheet-vol-1.pdf is a description for the core i5 processor which is pretty good. It has a pin description at the end of the document for the processor. There are 64 bidirectional SA\_DQ pins and 64 SB\_DQ pins. These pins are used for I/O to and from RAM.

> The Integrated Memory Controller (IMC) supports DDR3 protocols with two independent, 64-bit wide channels each accessing one or two DIMMs.

Based on the above statements, there are several interfaces between the data bus and the actual bit line of the memory cell. A path will have to eventually be opened between the processor SA\_DQ pins and the DQ pins of the DIMM using the data bus. The DQ pins of the DIMM are themselves connected to the output data buffers of the banks of the DRAM chips.

---
Tags: cpu, memory-hardware, memory-access
---


title: De morgan's law in formal language

text:
# Question
Title: De morgan's law in formal language
I found in some exercise in computation the following step:

I can't understand why is it equal terms, based of what I know about De morgan's law:

1. OR should be replaced by AND
2. where $w=\varepsilon$ come from

# Answer
> 1 votes
Let $\Sigma$ be the alphabet on which $A\_{TM}$ is defined over, and assume w.l.o.g that:

1. $A\_{TM}\cup \overline{A\_{TM}} = \Sigma^\*$, and
2. $0, 1 \notin\Sigma.$

The set $J$ can be written as:

$$ J = \\{0\\}\cdot A\_{TM} \ \cup \\{1\\}\cdot \overline{A\_{TM}} $$ where $J$ is defined over the alphabet $\Sigma \cup \\{ 0, 1\\}$. Now, using De morgan's law, it holds that: $$ \overline{J} = \overline{\\{0\\}\cdot A\_{TM}} \ \ \cap \overline{\\{1\\}\cdot \overline{A\_{TM}} } \\ $$ $$ =\left(\\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\\{0, 1\\}$ and $u\in \Sigma^\*$} \\} \cup \\{0\\}\cdot \overline{A\_{TM}} \ \cup \\{1\\}\cdot \Sigma^\*\right) \ \cap \\ \left(\\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\\{0, 1\\}$ and $u\in \Sigma^\*$} \\} \cup \\{1\\}\cdot A\_{TM} \ \cup \\{0\\}\cdot \Sigma^\*\right) \\ $$ $$ = \\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\\{0, 1\\}$ and $u\in \Sigma^\*$} \\} \cup \left( \left\[\\{0\\}\cdot \overline{A\_{TM}} \ \cup \\{1\\}\cdot \Sigma^\* \right\] \cap \left\[ \\{1\\}\cdot A\_{TM} \ \cup \\{0\\}\cdot \Sigma^\*\right\] \right) $$

$$ = \\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\\{0, 1\\}$ and $u\in \Sigma^\*$} \\} \cup \left( \\{ 0\\}\cdot \overline{A\_{TM}} \cup \\{ 1\\}\cdot A\_{TM} \right) $$

So, we have that $w \in \overline{J}$ iff $w$ does not encode a bit followed by a word of the form $\langle M, w \rangle$, or $w = 1x$ for some $x \in A\_{TM}$ or $w = 0y$ for some $y \in \overline{A\_{TM}}$.

Finally, note that they're implicitly assuming w.l.o.g that every nonempty word in $\\{0, 1\\}\cup \Sigma^\*$ is of the form "$\text{bit} \cdot \langle M, w\rangle$". This assumption is okay, as checking whether a word respects some encoding can be easily done by a TM.

---
Tags: formal-languages, turing-machines, computability
---


# Question
Title: What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?
# Background

I have a list of 50 million $A-A\_i$ pairs, where $i\>1$, and $A$ and $A\_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.:

$$ \text{New List}= \\{A, B, C, ...\\} $$

Here is a generic illustration of what the list of pairs looks like:

```
list of pairs = [['A', 'A1'],
                 ['A', 'A2'],
                 ['A', 'A3'],
                 ['B', 'B1'],
                 ['C', 'C1'],
                  ...

```

Here is some actual data:

```
`['394.NGR_c13430',
  '(3R)-hydroxymyristoyl-[acyl-carrier-protein] dehydratase'],`
`['394.NGR_c31790',
  '(Di)nucleoside polyphosphate hydrolase'],`
`['394.NGR_c00410',
  '(Dimethylallyl)adenosine tRNA methylthiotransferase MiaB'],`
`['394.NGR_c28950',
  '1,4-alpha-D-glucan:1,4-alpha-D-glucan 6-glucosyl-transferase'],`
`['394.NGR_c28950',
  '1,4-alpha-glucan branching enzyme GlgB'],`
`['394.NGR_c34010', '1-(5-phosphoribosyl)-5-[(5-ph']]`
`    9606.ENSP00000170630   1IAR`
`    9606.ENSP00000170630   1ITE`
`    9606.ENSP00000170630   287261`
`    9606.ENSP00000170630   287263`
`    9606.ENSP00000170630   287265`
`    9606.ENSP00000170630   287267`
`    9606.ENSP00000170630   287269`
`    9606.ENSP00000170630   287271`
`    9606.ENSP00000170630   3566`

```

(Sorry for the sloppy formatting, but I hope you get the idea.)

# My Attempt

I'm doing:

~~names := empty list
for row in list:
| name := first element in row
| for name in names: | | if name not in names:
| | | append name to names
~~

```
for line in proteins:
|    name := first element in "line"
|    for prot in prots:
|    |    if prot in name:
|    |    |    append alias to D_{prot}

```

Where `D_{prot}` is $D\_{prot}$, a sublist in D containing the $A\_{i's}$ of `prot`.

However, this approach is extremely slow. Even running this on only 10 million of the pairs takes more than half an hour. I'm only a statistician and not familiar with the intricacies of computer science or Python. Is there a better way of doing this?

# Also...

I know for a fact that there are only 10 million unique values ($A$ values).

With $n$ = 50 million and $p$ = 10 million, I thought my algorithm was $O(np)$. Is it? Is this efficient?

Thank you

# Answer
## Question 1: How to solve the finding uniques problem

If your data is consistently formatted in this way:

```
[
  ['somestring', 'someotherstring'],
  ['anotherstring', 'anotherotherstring'],
]

```

And so on, you can actually just call `dict` directly on it and it will reduce all of the first items to keys, and keep the last of the second items as the values, and this runs extremely quickly. You can then retrieve the keys from the dictionary to get your unique list.

Here is an example:

```
a = [
  ['somestring', 'someotherstring'],
  ['anotherstring', 'anotherotherstring'],
]
b = dict(a)
print(list(b.keys()))

```

I tested this with a data set resembling the one you describe, with 50 million entries and 10 million unique values. On a single core in my laptop it took only about 15 seconds to run and used about 5.5 GB of memory. It actually took 10 times as long to make the data as it did to reduce it to a unique list. I have included the code I used to test below:

```
import random
import string
import time

def make_data(n, min_len, max_len, repeat_chance=0.0):
    dataset = []
    for i in range(n):
        if random.random() < repeat_chance and len(dataset) > 1:
            dataset.append([random.choice(dataset)[0], ''])
        else:
            key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
            dataset.append([key, ''])
    return dataset

def main():
    random.seed(42) # For reproducibility
    start_time = time.time()
    x = make_data(50000000, 10, 100, 0.8) # 50 M with 80% repeats for ~10 M unique
    mid_time = time.time()
    y = dict(x) # Reduce to unique keys
    end_time = time.time()

    print('Make data:  {0:.2f} s'.format(mid_time - start_time))
    print('Make dict:  {0:.2f} s'.format(end_time - mid_time))
    print('Total time: {0:.2f} s'.format(end_time - start_time))
    print('Total items:  ', len(x))
    print('Unique items: ', len(y))

if __name__ == '__main__':
    main()

```

And got the following output which is consistent with the specifications of 50 million entries and 10 million unique values

```
Make data:  169.61 s
Make dict:  15.47 s
Total time: 185.08 s
Total items:   50000000
Unique items:  10000776

```

## Question 2: What is the complexity of that algorithm?

Is adding p unique values to a list and then searching the list for each new value from a list of n values to determine if its unique a O(np) problem?

Intuitively, I expect this to be a O(np2) problem. As n goes up, we must go through each one only once, so linear in n. As p goes up, we must go through more uniques to tell if the new value coming in is unique, so p2. This wiki page has almost exactly this situation, and shows how to derive the O(n2) complexity. But let's not let intuition guess for us, lets do the work.

Here is a plot of n with constant-ish p of 5000 and the time it takes to process it using your algorithm on the vertical axis.

Here is a plot of p with constant n of 1 million and the time it takes to process on the vertical axis.

These plots suggest that the list algorithm offers the complexity we expected of O(np2).

## Bonus Question: How does the dict method compare to the list method?

Just for the intrigue, I also compared the `dict` method to your list algorithm and plotted them together. Blue is the list algorithm, and orange is the dict method.

Since the orange line is a little difficult to see, here is a rerun with only the dict method.

As you can see, the `dict` method maintains linear performance with respect to p, offering an overall performance of O(np) while the list algorithm offers the complexity we expected of O(np2). The `dict` method also outperformed the list algorithm at every test point.

If anyone is so inclined, here is the code used to generate that data.

```
import random
import string
import time
import matplotlib.pyplot as plot

def make_data(n, min_len, max_len, repeat_chance=0.0):
    dataset = []
    for i in range(n):
        if random.random() < repeat_chance and len(dataset) > 1:
            dataset.append([random.choice(dataset)[0], ''])
        else:
            key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
            dataset.append([key, ''])
    return dataset

def get_uniques_listwise(dataset):
    uniqueset = []
    for datapoint in dataset:
        if not datapoint[0] in uniqueset:
            uniqueset.append(datapoint[0])
    return uniqueset

def get_uniques_dict(dataset):
    return list(dict(dataset).keys())

def makechart(testpoints, index, xlabel, ylabel, title, f0, f1=None):
    n_times0 = []
    n_times1 = []
    for testpoint in testpoints:
        dataset = make_data(testpoint[0], 10, 100, 1 - testpoint[1] / testpoint[0])
        start_time = time.time()
        f0(dataset)
        end_time = time.time()
        n_times0.append(end_time - start_time)
        if not f1 is None:
            start_time = time.time()
            f1(dataset)
            end_time = time.time()
            n_times1.append(end_time - start_time)

    plot.plot([x[index] for x in testpoints], n_times0)
    if not f1 is None:
        plot.plot([x[index] for x in testpoints], n_times1)
    plot.xlabel(xlabel)
    plot.ylabel(ylabel)
    plot.title(title)
    plot.show()

def main():
    random.seed(42) # For reproducibility
    n_p_testpoints_n = [
        [100000, 5000],
        [500000, 5000],
        [1000000, 5000],
        [2000000, 5000],
        [5000000, 5000],
        [7000000, 5000],
        [8000000, 5000],
        [9000000, 5000],
        [10000000, 5000]
    ]
    makechart(
        n_p_testpoints_n,
        0,
        'n',
        'time to find uniques',
        'varying n with near constant p=5000',
        get_uniques_listwise,
        get_uniques_dict
    )

    random.seed(42) # For reproducibility
    n_p_testpoints_p = [
        [1000000, 10000],
        [1000000, 15000],
        [1000000, 20000],
        [1000000, 25000],
        [1000000, 30000],
        [1000000, 35000],
        [1000000, 40000],
        [1000000, 45000],
        [1000000, 50000],
    ]
    makechart(
        n_p_testpoints_p,
        1,
        'p',
        'time to find uniques',
        'varying p with constant n=1000000',
        get_uniques_listwise,
        get_uniques_dict
    )

if __name__ == '__main__':
    main()

```
> 1 votes

---
Tags: complexity-theory, sets, lists, data-sets, finite-sets
---


# Question
Title: How to implement conditional probability distribution on set-valued Random Variables
I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing for me. In the usual scenario, for some pair of discrete RVs, $X,Y$, we can compute the conditional probability of two "punctual" events by using the Bayes theorem: $$P(Y=y|X=x)=\frac{P(X=x|Y=y)P(Y=y)}{\sum\_{y'\in\mathcal{Y}}P(X=x|Y=y')P(Y=y')}=\frac{f(x,y)}{\sum\_{y'\in\mathcal{Y}}f(x,y')},$$ where $f(x,y)=\sum\_{(x',y')\in (\mathcal{X},\mathcal{Y})}\chi(x'=x,y'=y)$ is an accumulator function giving the total number of times the specific joint event $x,y$ is observed in the sample space (i.e. the indicator function $\chi(x'=x,y'=y)$ equals one when $x'=x,y'=y$ holds). I'd like to compute such probability when events drawn by $X,Y$ are sets $\boldsymbol{x},\boldsymbol{y}$, respectively. So, how to define the corresponding $f(\boldsymbol{x},\boldsymbol{y})$?

I've tried with two main options: $$(1)\hspace{10mm}f(\boldsymbol{x},\boldsymbol{y})=\sum\_{(\boldsymbol{x}',\boldsymbol{y}')\in(\mathcal{X},\mathcal{Y})}|(\boldsymbol{x}\cap\boldsymbol{y})\cap(\boldsymbol{x}'\cap\boldsymbol{y}')|,$$ and $$(2)\hspace{10mm}f(\boldsymbol{x},\boldsymbol{y})=\sum\_{(\boldsymbol{x}',\boldsymbol{y}')\in(\mathcal{X},\mathcal{Y})}|(\boldsymbol{x}\cap\boldsymbol{y})\cap \boldsymbol{x}'\cup(\boldsymbol{x}\cap\boldsymbol{y})\cap \boldsymbol{y}'|,$$

On the one hand, the motivation behind $(1)$ is that $\boldsymbol{x}\cap\boldsymbol{y}$ provides a measure of how the attributes of both sets should be observed jointly (such as any intersection event). In turn intersecting this intersection event against other intersection events $\boldsymbol{x}'\cap\boldsymbol{y}'$ should provide the measure of how much the joint attributes are observed through the sample space. On the other hand, the motivation behind $(2)$ is that in order to compute $f(\boldsymbol{x},\boldsymbol{y})$ we need to look for $\boldsymbol{x}\cap\boldsymbol{y}$'s attributes in each event of the sample space, without building new events.

However, I'm not sure which one of these analogies is correct (or none at all) with respect to the usual notion of observing the joint event in a sample space. Please, some one can help me to clarify/fix/prove this?

Thank you in advance

# Answer
Your understanding of the basic situation (without sets) has some caveats. It seems that you are defining

$$f(x,y) = \Pr\[X=x \land Y=y\] \times |\mathcal{X}| \times |\mathcal{Y}|.$$

You seems to be assuming that $X,Y$ are independently and uniformly distributed over the sample space $\mathcal{X} \times \mathcal{Y}$. Note that this is a big assumption -- it typically won't hold, and if it doesn't hold, your formula is not correct.

You don't need a fancy accumulator function. There is a simpler expression for $f$, namely, $f(x,y) = 1$ if $x \in \mathcal{X},y \in \mathcal{Y}$ (and $f(x,y) = 0$ otherwise, if you allow that to happen). Again, this is only valid if $X,Y$ are uniformly distributed on $\mathcal{X} \times \mathcal{Y}$.

When $X,Y$ are sets, the exact same formula holds... under the same assumptions. No changes needed at all.

Your proposed formulas (1), (2) are not correct.

In practice, usually $X,Y$ are typically not independently and uniformly distributed. Therefore, these formulas are usually not useful in practice. Instead, you need to work directly with the probabilities; counts and $f$ probably won't be useful in that case.
> 0 votes

---
Tags: probability-theory, sets, probabilistic-algorithms, statistics, finite-sets
---


title: Hash tables versus binary trees

text:
# Question
Title: Hash tables versus binary trees
When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL library implements dictionaries (they call them maps) using (balanced) binary search trees, and the .NET framework uses hash tables under the hood.

> What are the advantages and disadvantages of these data structures? Is there some other option that is reasonable in certain situations?

Note that I'm not particularly interested in cases where the keys have a strong underlying structure, say, they are all integers between 1 and n or something.

# Answer
A whole treatise could be written on this topic; I'm just going to cover some salient points, and I'll keep the discussion of other data structures to a minimum (there are many variants indeed). Throughout this answer, $n$ is the number of keys in the dictionary.

The short answer is that **hash tables are faster in most cases**, but can be very bad at their worst. **Search trees** have many advantages, including **tame worst-case behavior**, but are somewhat slower in typical cases.

Balanced binary search trees have a fairly uniform complexity: each element takes one node in the tree (typically 4 words of memory), and the basic operations (lookup, insertion, deletion) take $O(\mathrm{lg}(n))$ time (guaranteed asymptotic upper bound). More precisely, an access in the tree takes about $\mathrm{log}\_2(n)$ comparisons.

Hash tables are a bit more variable. They require an array of around $2n$ pointers. Access to one element depends on the quality of the hash function. The purpose of a hash function is to disperse the elements. A hash table “works” if all the elements you want to store in it have different hashes. If this is the case, then the basic operations (lookup, insertion, deletion) take $O(1)$ time, with a fairly small constant (one hash calculation plus one pointer lookup). This makes hash tables very fast in many typical cases.

A general problem with hash tables is that the $O(1)$ complexity is not guaranteed.

* For addition, there's a point where the table becomes full; when that happens (or, better, a little before that happens), the table needs to be enlarged, which requires moving all of its elements, for an $O(n)$ cost. This can introduce “jerky” behavior when a lot of elements are added.
* It's possible for the input to collide over a few hash values. This rarely happens naturally, but it can be a security problem if the inputs are chosen by an attacker: it's a way to considerably slow down some servers. This issue has led some programming language implementations (such as Perl and Python) to switch from a plain old hash table to a hash function involving a random number chosen when the hash table is built, together with a hash function that spreads this random datum well (which increases the multiplicative constant in the $O(1)$), or to a binary search tree. While you can avoid collisions by using a cryptographic hash, this is not done in practice because cryptographic hashes are comparatively very slow to compute.

When you throw data locality into the mix, hash tables do poorly. They work precisely because they store related elements far apart, which means that if the application looks up elements sharing a prefix in sequence, it will not benefit from cache effects. This is not relevant if the application makes essentially random lookups.

Another factor in favor of search trees is that they're an **immutable** data structure: if you need to take a copy of a tree and change a few elements in it, you can share most of the data structure. If you take a copy of a hash table, you need to copy the whole array of pointers. Also, if you're working in a purely functional languages, hash tables are often not an option.

When you go beyond strings, hash tables and binary search trees make different requirements on the data type of the key: hash tables require a hash function (a function from the keys to the integers such that $k\_1 \equiv k\_2 \implies h(k\_1) = h(k\_2)$, while binary search trees require a total order. Hashes can sometimes be cached, if there is enough room in the data structure where the key is stored; caching the result of comparisons (a binary operation) is often impractical. On the other hand, comparisons can benefit from shortcutting: if keys often differ within the first few bytes, a negative comparison can be very fast.

In particular, if you're going to need the **order** on the keys, for example if you want to be able to list the keys in alphabetical order, then hash tables are no help (you'll need to sort them), whereas you can straightforwardly traverse a search tree in order.

You can combine binary search trees and hash tables in the form of **hash trees**. A hash tree stores keys in a search tree according to their hash. This is useful, for example, in a purely functional programming language where you want to work on data that does not have an easy-to-compute order relation.

When the keys are strings (or integers), a trie can be another option. A trie is a tree, but indexed differently from a search tree: you write the key in binary, and go left for a 0 and right for a 1. The cost of an access is thus proportional to the length of the key. Tries can be compressed to remove intermediate nodes; this is known as a patricia trie or radix tree. Radix trees can outperform balanced trees, particularly when many keys share a common prefix.
> 35 votes

# Answer
**GCC C++ case study**

Let's also get some insight from one of the most important implementations in the world. As we will see, it actually matches out theory perfectly!

As shown at https://stackoverflow.com/questions/2558153/what-is-the-underlying-data-structure-of-a-stl-set-in-c/51944661#51944661, in GCC 6.4:

* `std::map` uses BST
* `std::unordered_map` uses hashmap

So this already points out to the fact that you can't transverse a hashmap efficiently, which is perhaps the main advantage of a BST.

And then, I also benchmarked insertion times in hash map vs BST vs heap at https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst/29548834#29548834 which clearly highlights the key performance characteristics:

* BST insertion is O(log), hashmap is O(1). And in this particular implementation, hashmap is almost always faster than BST, even for relatively small sizes
* hashmap, although much faster in general, has some extremely slow insertions visible as single points in the zoomed out plot.

These happen when the implementation decides that it is time to increase its size, and it needs to be copied over to a larger one.

In more precise terms, this is because only its amortized complexity is O(1), not the worst case, which is actually O(n) during the array copy.

This might make hashmaps inadequate for certain real-time applications, where you need stronger time guarantees.

Related:
> 4 votes

---
Tags: algorithms, data-structures, binary-trees, hash-tables
---


# Question
Title: Decidability of Turing machines and misconceptions on the halting problem
In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability only arises when we are talking about a class of a problem.

As a rebuttal to the original argument someone replied that if we have a Turing machine and we give it an input w it'll be undecidable to say will it halt or not and was proven by Turing himself.

Is this a correct argument because skimming through wikipedia it looks that's not what Turing actually proved

> Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist

What he proved was that no general solution exists for all possible program-input pairs and not that we can't have a specific algorithm to solve this on a single machine (e.g if we take a halting Turing machine a simple solution would be to say yes for all inputs).

In support of my original statement look at the PCP, no general solution exists but if we are given two string we can sure brute-force them by looking at all possible subsequences and tell whether a correspondence exists or not.

So what I am asking here does my original statement hold weight and what exactly did Turing proved.

Edit: I've realized this question doesn't make much sense and is just not useful to anyone. But because it has answers it can't be deleted.

# Answer
The problem of deciding whether, given a Turing machine $T$ and a word $w$, $T(w)$ halts is undecidable.

If a Turing machine $T$ is **fixed**, the problem of deciding whether, given a word $w$, $T(w)$ halts might or might not be decidable (depending on the choice of $T$).

As an example in which this problem is decidable consider the trivial Turing machine $T$ that immediately halts. As an example in which this problem is undecidable consider an universal Turing machine $T$ in which $w$ encodes a pair $\langle M, w'\rangle$ where $M$ is some other Turing machine, and $w'$ is $M$'s input. The machine $T$ simply simulates $M'$ on $w'$. Clearly if we could solve the halting problem for this fixed $T$ and any $w$, we could also solve it in the general case.

If a word $w$ is **fixed** but the machine $T$ **is part of the input of the problem**, then the problem is undecidable regardless of $w$. Suppose towards a contradiction that this problem was decidable, then given a Turing machine $M$ and a word $w'$ as input, you could decide whether $M(w')$ halts. To do so you construct a new Turing machine $M'$ that clears its tape, writes $w'$, and then simulates $M$ (an encoding of such a machine $M'$ is computable given $M$ and $w$). Clearly $M'(x)$ halts iff $M(w')$ halts, regardless of $x$. In particular, for $x=w$, $M'(w)$ halts iff $M(w')$ halts. It then suffices to decide whether $M'(w)$ halts, which we can do by our hypothesis.

If **both** a Turing machine $T$ and a word $w$ are **fixed**, then the problem does not make much sense since you do not have a class of instances anymore... Notice that, in this case, either $T(w)$ halts or it does not, meaning that one of the following two Turing machines must answer correctly: 1) Always halt and accept. 2) Always halt and reject.
> 3 votes

# Answer
Unfortunately I cannot comment on Steven's answer, but I think the crux of the matter here is a confusion between the terms "problem", "class of problem" and "problem instance" (that is, when the machine and word are fixed, you have an *instance* of the halting problem, not a problem).

As a side note, Turing did not prove in his 1936 paper the halting problem in this form. The machines in his paper mostly compute binary digits of numbers and he proved you cannot tell whether one of these ever stops or runs forever. So his problem only has a machine as input, not a (machine, word) pair.
> 0 votes

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: Statement of the Goldwasser-Sipser Set Low Bound Protocol
I'm trying to understand the statement of the Goldwasser-Sipser Set Low Bound Protocol as presented in "Computational Complexity: A Modern Approach" by Arora and Barak.

In particular, I'm trying to understand why the following claims yield what we would want:

$S \subseteq \\{0,1\\}^m$ is a set such that members can be certified. Both parties know a number $K$. Let $k$ be an integer such that $2^{k-2} \< K \le 2^{k-1}$.

**Claim**: Let $S \subseteq \\{0,1\\}^m$ satisfy $|S| \le 2^{k}/2.$ Then for $p=|S|/2^k$ we have $p \ge \mathbf{P}\_{h \in\_{\_R} \mathcal{H}\_{m,k}, y \in\_{\_R} \\{0,1\\}^k}\left\[\exists x \in S: h(x)=y \right\] \ge \frac{3p}{4}-\frac{p}{2^k}.$

My understanding is that we want:

* If $|S| \ge K$ then the verifier should accept (corresponding to the prover finding such an $x$ in the claim) with "high" probability;
* If $|S| \le K/2$ then the verifier will accept with probability at most 1/2.

I'm getting thrown off by a few things here:

* the claim assumes that $|S| \le 2^k/2 = 2^{k-1} = 2\times2^{k-2} \< 2 K$, so how does this place us in one of the relevant cases?
* How do we actually use those left ($p$) and right ($3p/4 - p/2^k$) bounds to conclude what we want?

Overall, I understand bits and pieces of this setup, but I'm having trouble seeing how it all fits together. Can someone walk through the logic/algebra here?

# Answer
To succeed in distinguishing the case of $|S|\ge K$ from $|S|\le\frac{K}{2}$, you just need a constant gap (independent of $|S|$) in the acceptance probability in both cases. If you managed to achieve such a gap, then applying Chernoff to multiple executions of the protocol would achieve high success probability.

Observe that the interesting case is $k\le m$, since otherwise $K\ge 2^{k-2}\ge2^{m-2}$, and the verifier can convince himself that $|S|\ge K$ simply by sampling strings in $\\{0,1\\}^m$ uniformly at random and checking whether they belong to $S$ (in this case $|S|\ge K$ implies that the probability of falling in $S$ is at least $1/4$, so Chernoff with a polynomial number of samples yields the desired result). From now on assume $m\ge k$, and thus the hash functions are $h\_{a,b}:GF(2^m)\rightarrow GF(2^k)$ given by $h\_{a,b}=(ax+b)\_{1...k}$, where $x\_{1...k}$ in the truncation of a string obtained by taking the first $k$ bits.

For uniformly distributed $a,b\in GF(2^m)$, and every $x\in GF(2^m)$, $ax+b$ is uniformly distributed. This means that $\forall x\in GF(2^m): \Pr\limits\_{\substack{a,b\in GF(2^m)\\y\in GF(2^k)}}\left\[(ax+b)\_{1...k}=y\right\]=\frac{1}{2^k}$. We conclude that $\Pr\limits\_{a,b,y}\[\exists x\in S: h\_{a,b}(x)=y\]\le \frac{|S|}{2^k}$. On the other hand, we can lower bound the same probability by:

$$ \Pr\limits\_{a,b,y}\[\exists x\in S: h\_{a,b}(x)=y\]\ge\\ \sum\limits\_{x\in S}\Pr\limits\_{a,b,y}\left\[h\_{a,b}(x)=y\right\]-\sum\limits\_{x\neq x'\in S}\Pr\limits\_{a,b,y}\left\[h\_{a,b}(x)=y \land h\_{a,b}(x')=y\right\]=\\\frac{|S|}{2^k}-\frac{}{}\binom{|S|}{2}\frac{1}{2^{2k}}\ge \frac{|S|}{2^k}\left(1-\frac{|S|}{2^{k+1}}\right). $$

So far there were no restrictions on the size of $S$. Now, if $|S|\le K\le 2^{k-1}$ then $\frac{|S|}{2^k}\le\frac{1}{2}$, and we obtain $\Pr\limits\_{a,b,y}\[\exists x\in S: h\_{a,b}(x)=y\]\ge \frac{3}{4}\frac{|S|}{2^k}$. We conclude that if $|S|=K$ then the probability of acceptance is at least $\frac{3}{4}\frac{K}{2^k}$ (the bound trivially holds for larger $|S|$, just by taking a subset of size $K$). If on the other hand $|S|\le K/2$ then the acceptance probability is at most $\frac{1}{2}\frac{K}{2^K}$ and we have our constant gap $\ge\frac{1}{4}\frac{K}{2^k}$, and Chernoff completes the proof.
> 2 votes

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: Is the set of strings with equal number of 010’s and 101’s regular?
Consider the language $$L = \\{ w\in \\{ 0, 1\\}^\*: \\#\_{010}(w) = \\#\_{101}(w) \\}$$

Is $L$ is regular? If it is not regular, can we prove that using the pumping lemma (only with pumping down)?

# Answer
The language $L$ is not regular. One might think $L$ is regular as it is tempting to think that the number of 010s and the number of 101s in a word are dependent. Yet, as explained by @gnasher729, this is not the case because occurrences of 010 and 101 can be *far* from each other. It is a bit challenging to prove non-regularity of $L$ using the pumping lemma while restricting only to pumping down. The trick is to consider a word where the occurrences are far from each other, but not too far! so that if pumping down does not decrease the number of 010s then it would definitely increase the number of 101s.

So assume by contradiction that $L$ is regular, and let $p\geq 1$ be a pumping constant for $L$. Consider the word $w = (010)^{2p} \cdot 1\cdot (101)^{2p}\cdot 0$, its not hard to see that $|w|\geq p$, and that $w\in L$. Indeed, $\\#\_{010}(w) = \\#\_{101}(w) = 2p+1$. By the pumping lemma, $w$ can be written as $w = xyz$, where $|xy|\leq p, |y| \> 0 $, and $xy^iz\in L$ for every $i\geq 0$. Note that $y$ lies somewhere in the prefix $(010)^p$ of $w$. We split into cases:

* $y$ does not contain ones: if $y = 00$, then pumping it down (or equivalently removing $y$ from $w$) decreases $\\#\_{010}$ by two, and $\\#\_{101}$ is not affected (what actually happens here is that pumping down replaces an infix of the form $"\cdots 010\cdot 010010 \cdot 010\cdots"$ with $"\cdots 010\cdot 0110 \cdot 010\cdots"$). If $y = 0$, then either $y$ is the first letter of $w$, and thus removing it decreases $\\#\_{010}$ by one, and does not affect $\\#\_{101}$, or $y$ lies between consecutive occurrences of $010$, and thus removing it does not affect $\\#\_{010}$, but increases $\\#\_{101}$ by 1 (what actually happens here is that pumping down replaces an infix of the form $"\cdots 010\cdot 010010 \cdot 010\cdots"$ with $"\cdots 010\cdot 01010 \cdot 010\cdots"$). In all cases, we have that $\\#\_{010}(xz) \< \\#\_{101}(xz)$. Thus $xz\notin L$, and we've reached a contradiction.
* $y$ contains $k\geq 1$ ones: in this case, removing $y$ from the $(010)^{p}$ prefix of $w$, reduces $\\#\_{010}$ by at least $k$. Also, this cannot decrease $\\#\_{101}$ because the first occurrence of $101$ in $w$ lies right before the suffix $(101)^{2p}\cdot 0$ of $w$, and thus all occurrences of $101$ in $w$ are infixes of $z$. Hence, $\\#\_{010}(xz) \< \\#\_{101}(xz)$. Thus $xz\notin L$, and we've reached a contradiction. (Note that in this case, $\\#\_{101}$ can actually increase after removing $y$. Also note that $\\#\_{010}$ can decrease by $k+2$ if for example $x$ ends with $1$ and $y$ starts and ends with $00$).
> 2 votes

# Answer
Try writing a few words that are contained (and not) in your language. See if you can discern some structure that helps answering your question.

**Hint:** CS teachers are a devious, sadistic bunch. This might be a trick question...
> 0 votes

# Answer
Most likely not, because you could have n substrings of the form 00100 and m substrings of the form 1110111, and a finite state machine would have to check that n=m.

I’d use Myhill-Nerode. Prove that the states reached after (00100)^n and (00100)^m must be different if n != m. In the first case, the smallest number of further symbols needed to reach an accepting state is 2n+1, in the second case it is 2m+1. Pumping lemma seems much more difficult.
> 0 votes

---
Tags: regular-languages, finite-automata, pumping-lemma
---


title: Reduce Clique to N-Degree-Clique

text:
# Question
Title: Reduce Clique to N-Degree-Clique
I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where: $$ \text{N-Degree-Clique} = \\{ \langle G, k\rangle: \text{$G$ has a clique of size $\geq k$,} \\ \text{and every vertex of $G$ has degree at least N} \\}$$

I am not sure how to map the last condition and could use help figuring out a reduction.

# Answer
One almost correct reduction looks like: consider the graph $G'$ that is obtained by adding $N$ new vertices to the input graph $G$. Also, add edges that connect every new vertex to all the vertices in $G$. Its not hard to show that $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+1$. Note that the degree of each new vertex equals the number of vertices of $G$, which not necessarily at least $N$. But this is a minor issue that I leave for you to fix (along with proving correctness).
> 1 votes

---
Tags: complexity-theory, graphs, np-complete, clique
---


# Question
Title: Halting (on empty input tape) for an infinite subset of all Turing machines
As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem.

But what if, instead of considering the entire set of Turing machines, we only focus on a subset thereof? Clearly, if the subset is finite, the problem is decidable. But if the subset is infinite, is there an easy way to prove its undecidability?

Take, e.g., the following decision problem (let's call it EVEN):

EVEN = determine whether any given Turing machine **with an even index** halts on an empty input tape.

(Just to be clear about quantifiers, I mean: does there exist a procedure that is able, for any given Turing machine with an even index, to decide whether that machine halts on an empty input tape?)

In this case, the considered set of Turing machines is infinite, but Rice's theorem is no longer applicable (a.f.a.i.k.) and even a diagonalization argument does not seem to be conclusive, since you may end up with a function with an odd index, so self-reference is lost.

So my questions are:

1. is EVEN undecidable? How can you prove its undecidability?
2. what about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? would this problem still be undecidable or does that depend on the subset?

Regarding question 2, one could take the set of TMs that compute, say, f(x) = x, which certainly always halt; however, the set of indices of those TMs is not a recursive set, so the question seems ill-formulated.

# Answer
> 1 votes
> is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.

However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

> What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an injective mapping - you don't need to decide behavioral equivalence.

---
Tags: turing-machines, halting-problem, rice-theorem
---


# Question
Title: Finding largest disjoint subtrees spanning nodes
I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found.

Now for each department, I would like to find the smallest number of the largest subtrees in the taxonomy.

For instance, in the example below leaf nodes have been assigned one of two departments $A$ and $B$.

The expected solution would be: $A$ has two subtrees, namely $x\_2$ and $x\_7$, $B$ has one subtree $x\_4$.

The solution where $A$ has $x\_1$ subtree is wrong because $x\_1$ is the ancestor of nodes that belong to another department.

The solution where $A$ has $x\_3$ and $x\_7$ subtrees is wrong because we want the biggest subtrees possible.

Is it a known problem?

Is there a solution for it?

# Answer
Here's an algorithm. Let $D(l)$ denote the department of the product category of a leaf $l$.

To find the subtree for leaf $l$ do the following. For every leaf $l'$ such taht $D(l') \neq D(l)$, mark the node $\text{lca}(l, l')$. Now, your largest subtree is the subtree rooted in the highest unmarked node. Call this node $\text{root}(l)$.

To compute for all leaves, clear the marks and output $\bigcup\_{l \in L} \text{root}(l)$, where $L$ is the set of leaves.

---

A different (faster) algorithm: For each leaf $l$, move upwards and mark each node with $D(l)$. If you hit a node already marked $D(l)$, you move on to the next leaf. If you hit a node marked with a different color, delete the node. Then your connected components should be your largest disjoint subtrees.

---

You ask if it's a *known problem*, I think that the closest you get to a known problem is the *lowest common ancestor* problem.
> 1 votes

---
Tags: algorithms, trees
---


# Question
Title: Can the perceptron classifier achieve perfect accuracy, on any data set?
I was thinking. Since any data can become linearly seprabale through kernel methods, meaning there is a dimension where this data is linearly seprable, so feed this processed data set into the perceptron algorithm and then it might get to 100 percent accuracy.

Am I correct?

# Answer
The use of a nonlinear kernel never gives any guarantees to make any data set linearly separable in the higher dimensional feature space. Kernels are used to map the data from input space onto a higher dimensional space, in which a hyperplane will be better at separating the data (but no guarantee for linear separable higher dimensional mapped data). That is why we can not be sure that perceptron algorithm will work correctly on higher dimensional mapped dataset or not.
> 1 votes

# Answer
Yes and no.

Yes: Given a large enough perceptron (with enough layers and enough neurons), you can achieve 100% accuracy on the training set: i.e., you can construct a perceptron that perfectly fits everything in the training set.

No, not necessarily: Depending on the learning task, you might not be able to achieve 100% accuracy on the test set, no matter how large your perceptron is and no matter what your kernel is.
> 0 votes

---
Tags: machine-learning, perceptron
---


# Question
Title: Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?
We are given a tree of N nodes from 1 to N where node 1 is the root of the tree. For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance equal to height of subtree of i.

Distance between a & b = total number of edges in path from a to b,height of subtree = maximum distance of the root of the subtree to any node in the subtree.

I have tried to create an algorithm using dfs using adjancey list of arraylist in java but got nowhere.

example input and output: input:

```
first line:
4--> no of nodes---
next each line represents connection of nodes
(1 2),
(2 3),
(2 4)

```

output:

```
-->space separated output for each node as a root.
2 2 1 1

```

# Answer
> 0 votes
First of all, you can notice that the nodes you are looking for are necessarly leaves of the tree (or sub-tree). What you are looking for, in each sub-tree, are the leaves that are at the largest distance from the root.

Let's call:

* $L\_k$, the list of the furthest leaves in the sub-tree rooting at node $k$ (the answer to your problem).
* $h\_k$, the distance from node $k$ to the furthest leaves of the sub-tree rooting at node $k$ (what you call height).

For all leaves, you have:

* $h\_k$ = 0
* $L\_k$ = \[k\]

For all other node, you have:

* $h\_k$ = $max\_i (f\_i) + 1$ for each $i$ child of $k$
* $L\_k$ = $sum\_i (L\_i)$ for each $i$ child of $k$ if $h\_k$ == $h\_i$+1

NB: by $sum$, I mean the concatenation of all the lists verificating the condition.

Globally, you can do a DFS, and once you explored all the subsequent paths from a node $k$, you are able to compute $h\_k$ and $L\_k$.

# Answer
> 0 votes
I tried it in DFS Mechanism, here the code is

```
import java.util.Scanner;

public class codeNew
{
    static Scanner inn = new Scanner(System.in);
    static int n = inn.nextInt();

    static int count1[] = new int[n+1];
    static ArrayList<Integer> adj[] = new ArrayList[n+1];

    static void numberOfNodes(int s, int e)
    {
        if(s != 1  && adj[s].size() == 1) {
            count1[s] = 1;
        }else
        {
            count1[s] = 0;
        }

        for(Integer u: adj[s])
        {

            if(u == e)
                continue;

            numberOfNodes(u ,s);
            count1[s] += count1[u];
        }
    }

    // function to add edges in graph
    static void addEdge(int a, int b)
    {
        adj[a].add(b);
        adj[b].add(a);
    }

    // function to print result
    static void printNumberOfNodes()
    {
        for (int i = 1; i < n+1; i++) {
             System.out.print(count1[i]);
             if(i != n)
             {
                System.out.print(" ");
             }
        }

    }
    public static void main(String[] args)
    {
        for(int i = 0; i < n+1; i++)
            adj[i] = new ArrayList<Integer>();

        for (int i = 0; i < n-1; i++) {
            int x = inn.nextInt();
            int y = inn.nextInt();
            addEdge(x,y);
        }
        numberOfNodes(1, 0);
        printNumberOfNodes();

    }

}

```

Input is

```
4
1 2
2 3
2 4

```

Output is `2 2 1 1`

---
Tags: algorithms, graphs, trees, arrays, java
---


title: facts on tree and MST

text:
# Question
Title: facts on tree and MST
We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.

The following Facts is False, and True.

$I$) Graph $G$ is a Tree.

```
                False.

```

$II$) weight of each ${u,v}$ edge, is at least equal to heaviest edge in shortest path from $u$ to $v$.

```
                True.

```

> Anyone can describe me why the second fact is hold? Intuitive idea or example or proof?

# Answer
> 1 votes
Assumption $II$ is true for any general graph with non-negative edge weights, including the graph $G$ with specific properties. To understand this, think about the inverse of the statement.

Let's assume the weight a $u,v$ edge is lighter than edge $e$ on the shortest path. The shortest path is made out of $e$ \+ $C$ where $C$ is some constant. Because $C \>= 0$(non-negative graph) and $e$ \< edge between $u,v$, by definition the shortest path we have assumed to be optimal is not(because the edge directly connecting $u$ to $v$ would be shorter).

To your specific graph into this, this lighter edge from $u,v$ cannot exist because if it did, it would have to be part of the minimum spanning tree(and thus part of the shortest path as mentioned in your description).

---
Tags: algorithms, graphs, data-structures, trees, discrete-mathematics
---


# Question
Title: Find maximal clique consisting of at least half of the vertices
Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority of the vertices will belong to this clique. This clique may or may not be maximal; however, given these assumptions it will definitely be a subgraph of the maximum clique of $G$.

My goal is to find the most efficient algorithm to find the maximum clique of the graph. If the maximum clique is not unique, finding one of them is fine.

In general, $G$ won't be planar or perfect graph and to the best of my knowledge there is no exponential or linear-time algorithm to solve this problem.

I thought that, one way is to do an exhaustive search of all $n\choose c$ induced subgraphs until I find a clique $C$. Then, one can keep adding vertices to $C$ such that they connect to all vertices currently in $C$ until this clique cannot be enlarged anymore. Then, $C$ will be one maximum clique. Assuming that $n$ is not too large, maybe $n \< 50$, do you think that this is a reasonable method given that $n\choose c$ is large? Is there a more efficient algorithm?

One small optimization is to exclude all vertices with degree $\< c-1$ from consideration.

# Answer
> 2 votes
Each time you remove a vertex $v$ with degree $\<c−1$, the degree of all its neighbours will be reduced by 1, so if any neighbor $u$ gets a degree $\<c−1$ after removing $v$, remove $u$ as well; don't stop on $v$. Once you are done you will get what is called the ($c−1$)-core of the graph, which is the induced subgraph where all of its vertices has a degree $\geq c−1$. The maximum clique will be a subset of such core.

Besides that, $c$ is just a lower bound on the maximum clique size, which doesn't change the fact your problem is NP-hard but over a much tinier graph (if you are minimally lucky).

Also, given the maximal $d$ such as the $d$-core exists (the degeneracy of the graph), $d+1$ is an upper bound to the maximum clique size.

With $c$ and $d+1$ as bounds, your maximal clique will probably be found very efficiently by the algoritm introduced in this paper, where all of the above is explained very well (there are a link to github with the implementation in C++): http://www.optimization-online.org/DB\_FILE/2018/07/6710.pdf

If you have remove enough vertices, maybe your $c$, which is at least a 50% in the original graph, becomes even higher after the previous erosion of the graph, so you could start looking for algorithm variants specialized for dense graphs.

# Answer
> 1 votes
The problem is NP-hard, so you shouldn't expect any efficient algorithm that will always work. You can look for heuristics, or approximation algorithms, or sometimes-efficient algorithms.

If I had to solve it in practice, probably the first thing I would try would be to use a SAT solver. Introduce a boolean variable $x\_v$ for each vertex $v$; then add constraints $x\_v \implies x\_w$ for each edge $(v,w)$; and add a constraint requiring there to be at least $c$ variables set to true. Ask the SAT solver to find a satisfying assignment.

---
Tags: complexity-theory, graphs, np-complete, np, clique
---


# Question
Title: How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length?
$L = {a^n + b^m + a^{n+m}}$

This is the language I want to show is not regular.

Now my problem is to choose p correctly.

Can I just set it as p=2\*(n+m) ?

That's the problem I am facing now.

Thanks for any help I am starting to learn it to use the pumping lemma.

Edit: In the meantime I have done this:

$w=a^nb^ma^{n+m}$

|w|= 2(n+m)=p

$|xy|\leq 2n + 2m$

We choose $x=a^n, y=b^m, z=a^{n+m}$

$|a^nb^m|=nm \leq 2n+2m$

w=xy^iz

Now we set i = 0

$w\_0=a^na^{n+m} \notin L $

$\implies $ L is not regular.

# Answer
> 1 votes
It seems that you are trying to force the string length to be $p$, which is not necessary. What is required is that $|xy| \leq p$. The length of $w$ can be greater than $p$. Also, $n$ or $m$ can be $p$ or some multiple of $p$, whatever makes the reasoning for the impossibilty of partition of $w$ to satisfy the lemma. With that, I think you can follow through and complete your proof.

Just remember, the aim is **not** to look for a partition of $w$ that does not work. Rather show that **no** partition works.

Cheers.

# Answer
> 0 votes
You can't "set" the pumping length.

The pumping lemma states that if $L$ is a regular language, then there is a constant $N \> 0$ such that if $\sigma \in L$ and $\lvert \sigma \rvert \ge N$ then there is a division $\sigma = \alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k \ge 0$ the string $ \alpha \beta^k \gamma \in L$

Here $N$ is the "pumping length".

The use you want to give the pumping lemma is to show it doesn't apply to your language, so the language isn't regular. I.e., *no* $N$ works.

General schema is typical proof by contradiction.

Assume $L$ is regular, thus the pumping lemma applies. Let $N$ be the \[anything at all, we want to prove *none* works\] constant of the lemma. Select $\sigma \in L$ \[as the lemma states *all* long enough strings work, you are free to select a easy one to work with\]. Now prove *no* division $\alpha \beta \gamma$ of $\sigma$ works by picking a "nice" $k$ and prove $\alpha \beta^k \gamma \notin L$.

In your case: Easy to work with is $\sigma = a^N b c^{N + 1}$, any division will give $\alpha \beta$ only $a$, repeating $\beta$ say twice ($k = 2$) will give too many $a$ for the (fixed) number of $c$.

---
Tags: pumping-lemma
---


# Question
Title: Indexing a huge dataset (that does not fit into central memory)
**The problem.**

Let us consider a *huge* file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are huge. In particular, *neither the entire file nor the list of all distinct strings fit into central memory*. The global file may be parsed and/or sorted (in external memory) a few times, though.

The goal is to build the file in which line $i$, for $i=1..m$, is integer $k$ if the string on line $i$ in the original file is the $k+1$-th distinct string appearing in the original file.

**Example.**

For instance, if the original file is:

```
bbb
cccc
cccc
bbb
aaa
ee
aaa
fff
dddd
cccc
bbb
fff

```

then $n=6$, $m=12$, and we should obtain:

```
0
1
1
0
2
3
2
4
5
1
0
4

```

**My approach.**

I take benefit of *standard unix command-line tools*, as follows.

I first build a numbered string occurence file:

```
zcat input.gz | awk '{print NR-1,$0;}' | gzip -c > occurrences.gz

```

I use it to build an index file for strings that respects occurence rank, and starts with character '-', lower than any occurence number:

```
zcat occurrences.gz |
  sort -T. -S1g --stable -k2,2 |
  awk 'BEGIN{old="none";}{if ($2!=old) print $0; old=$2;}' |
  sort -T. -S1g -nk1,1 | awk '{print "-",$2,NR-1;}' |
  gzip -c > index.gz

```

I merge the two files and sort the result to ensure that the line with a string index will be just before all other lines containing this string; I then replace each string, sort according to occurence rank, and I am done:

```
zcat occurrences.gz index.gz |
  sort -T. -S1g -k2,2 -k1,1 |
  awk '{if ($1=="-") i=$3; else print $1,i;}' |
  sort -T. -S1g -nk1,1 |
  cut -d" " -f2 |
  gzip -c > result.gz

```

*Technical detail:* to avoid encoding issues, first set environment variable `LC_ALL` to `C`.

**Question.**

**Is it possible to do *significantly* better than my approach, or to achieve similar performances with a *significantly* different approach, *in practice*?**

Notice that I am not interested in minor, technical improvements, like using *mawk*, *sed*, etc, instead of *awk*. I am not interested in a purely theoretical solution either, that would be better asymptotically but would turn out to be so complex than no implementation is reasonably feasible.

Instead, my concern is the relevance and overall effectiveness of my approach, or variants.

For instance, would any external memory data structure be faster, while using as little memory, with available implementation?

# Answer
> 1 votes
The other approach that I can think of is the obvious one: process the file one line at a time, and consult a dictionary of "seen" lines. What may not be obvious is how to represent the dictionary.

There are plenty of on-disk data structures that would work, and this is a well-researched area given that this is what databases do for a living. Some variant of B-trees, or a hash table (e.g. extensible hashing) would work. Consider Berkeley DB if you need something off the shelf.

If that is too slow, you could use a Bloom filter as an in-memory cache. Then, you need only consult the on-disk data structure if you get a hit in the Bloom filter.

---
Tags: algorithms, sorting, space-complexity, data-sets
---


# Question
Title: Max-Heap PriorityQueue to keep the k highest items and return them in descending order
I have created a custom implementation for PriorityQueue using max-heap and everything works fine.

But now i want to change it and keep only the k highest objects in the heap after every insertion. I have to use only one instance of my PriorityQueue and no other helping data structure. So my problem is how should i know if the object that I want to insert is "better" than the "worst" in the priority queue. It's max-heap implemention so the get(first) returns the "best" object and the get(last) it is not the "worst" necessarily.

I need to keep the complexity of insertion at O(nlogn).

Any idea?

# Answer
> 1 votes
If what you want is to keep the top $k$ items at all times what you need is a min-heap, not a max-heap. After every insert you should check if the length is longer than $k$, and if yes, pop.

If you use numbers as your priorities you can turn a max-heap into a min-heap by simply negating the priority.

# Answer
> 0 votes
Have you considered min-max heap with fixed size $k$? As before compare the new item to be inserted if it is greater than the minimum, if so call remove-min and insert the new item. To get the elements in descending order you can call remove-max. Insert,remove-min, and remove-max takes $O(log\ n)$.

---
Tags: priority-queues
---


# Question
Title: optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$
I want to optimize an algorithm for calculating $g(n)=\sum^n\_{k=2} p(\Omega(k))\Omega(k)$ where $$ p(n) = \begin{cases} 1 &\text{if $n$ is odd} \\ -1 &\text{if $n$ is even} \end{cases}$$ and $\Omega(k)$ is the prime factor counting function or more exactly, I want to optimize calculating all its values up to $n$

My current best try is

```
def Omega(k):
    Factor = 0
    b=1
    while(k>1):
        b += 1
        if (k % b == 0):
            while k % b == 0:
                k /= b
                Factor += 1
    return Factor
sum = 0
for i in range(n)
   w = Omega(i)
   sum += (w % 2 * 2 - 1) * w
   #using it

```

First, I am trying to calculate the current algorithm's computational complexity. we calculate $\Omega(k) ~~n$ times, I haven't managed to calculate $\Omega(k)$'s computational complexity but it seems to be $O(\sqrt k \log k)$ thus, I think the entire program is $O(n^{1.5} \log n)$.
Am I correct?
Can anyone help optimize my algorithm?

**Ideas:**

1. Calculating $\Omega$ less. $\Omega$ is an Completely Additive function, i.e. for any $a,b$, $\Omega(ab)=\Omega(a)+\Omega(b)$. I've tried to use this to optimize the calculation, but have not managed to.
2. Optimizing the prime factorizing algorithm. I'm unsure about this.
The reason I'm interested in this is to graph the function. My current code is the first thing that went into my head, i.e., very nonoptimal.
This function is related to Liouville function.

# Answer
### Algorithm in the question

Although it is correct, it is rather slow. In function `Omega(k)`, `b` goes from 1 to the largest prime divisor of $k$, which is of order $\dfrac {\pi^2n} {12\\,\log n}$ on average for $1 \le k \le n$ as mentioned by the On-Line Encyclopedia of Integer Sequences. So, the running time of computing $g(n)$ is $O(\dfrac {n^2}{\log n})$. It takes more than an hour to compute $g(10^6)$ on my computer.

### A Faster Algorithm

Instead of computing directly the number of prime factors of each number $k$, we can add 1 to $\Omega(k)$ whenever $k$ is a multiple of a power of $p$ for all primes $p$. For example, since 72 is a multiple of 2, 4, 8, 3 and 9 but no other powers of primes, we will get $$\Omega(72)=(1+1+1)+(1+1)=5.$$

Here is the improved algorithm.

```
from itertools import accumulate

def g_up_to(n):
    # return [g(0), g(1), g(2), ..., g(n)], where g(0)=g(1)=0.

    # Omega[k] for k >= 1 is the total number of prime factors
    # of k, counting multiplicity. Omega[0] = 0.
    Omega = [0] * (n+1)
    for k in range(2, n+1):
        if Omega[k] == 0:  # k is a prime.
            power = k
            while power <= n:
                m = power
                while m <= n:
                    Omega[m] += 1
                    m += power
                power *= k
    return list(accumulate((x % 2 * 2 - 1) * x for x in Omega))

print(g_up_to(9))  # print $g[0], ..., g[9]
# [0, 0, 1, 2, 0, 1, -1, 0, 3, 1]
print(g_up_to(10**6)[-5:])  # print g[999996], ..., g[1000000]
# [-14178, -14180, -14184, -14177, -14189]

```

On average, each $O(1)$ number of operations will yield $1$ prime factor. Thus, the running time of the algorithm above is $$O(1)\cdot O\left(\sum\_{k=1}^n\Omega(k)\right)=O(n\log\log n),$$ where $\log\log n$ is the average of $\Omega(i)$ for $1\le i\le n$, as mentioned in Wikipedia. Since $\log\log n$ grows very slowly, this algorithm can be considered as an almost linear algorithm.

It takes less than 1 second to run `g_up_to(10**6)` on my computer.
> 2 votes

---
Tags: algorithms, complexity-theory, time-complexity, primes, program-optimization
---


# Question
Title: How all values hash to the same value with a given formula
When looking at hashing, and given the following question:

```
Given ASCII values: a = 97, b = 98, c = 99, d = 100, e = 101

Given keys: {e, ae, be, ce, de, abe, ace, ade, bae, cae, dae, bce, bde, cbe, dbe}

If we choose: h(k) = k mod 2^6 to map these keys to hash tables indexes, what do you notice?

```

The answer to this is that all of them hash to 37 but when I try this on a calculator they do not and I do not understand how to get 37. I think this has something to do with the low order bits reference in CLRS and the fact that it is not using a prime number but if I add for example:

`a + e = 97 + 101 = 198 % 64 = 6`

`b + e = 98 + 101 = 199 = 199 % 64 = 7`

When I look at the the binary for 6 and 7 they do not end up being the same and neither of the values above ends up resulting in 37.

Any help understanding this is appreciated!

# Answer
They want you to interpret a string of characters as a multi-byte integer.

So for example `abe` is intended to mean:

```
256^2*a + 256*b + e

```
> 0 votes

---
Tags: hash-tables
---


title: Finding optimal separating value

text:
# Question
Title: Finding optimal separating value
## Problem description

We are given two sorted arrays of even numbers: A and B. Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd number to predict which set an element belongs to. If an element is smaller than X, it will be assigned to A,and if it is bigger - to B. The value should be optimal, meaning the number of improperly matched values should be minimal. For example, if A = \[2,4,6\] and B = \[6, 10, 12\]. Separating value 3 would cause 2 mismatched values 4 and 6. Optimal would be 5 or 7, both causing one improper matched element. The algorithm is supposed to return an optimal separating value (only one of there are many) and the number of mismatched items.

## My ideas

At first I thought about using Binary Search for each element of A to find a number of elements of B smaller than it. Then repeat for B.

A better idea would be to generate candidates for such separating numbers. For example, if we only have values 10, 50, 100 we don't have to check all odd numbers, we can just check 9, 11, 51, 101. We could then calculate prefix sums, indicating how many numbers from A are bigger than the checked value and how many elements from B are smart than that value. The sum of the two sums for a number would be the total number of errors. The only thing left is to find the value with minimal errors.

Is this approach even near optimal, maybe we can find a better way. Also, calculating such prefix sums can be tricky because if we want not to care about the range of numbers we would have to find a way to skip some numbers and that makes our iteration harder, although possible.

What are your ideas? Some pseudocode or code in Python is very welcome.

# Answer
Initialize an array of pairs $T\[i\] = (x, c)$ containing all elements of $A$ and $B$. Let $x$ be the elements themselves, and $c = 0$ if the element came from $A$ and $c = 1$ if the element came from $B$. Then sort $T$ based on the $x$ values in ascending order.

Then the number of mistakes you'd get if you choose a value between $T\[i\]\text{.}x$ and $T\[i+1\]\text{.}x$ is:

$$\sum\_{j=0}^i T\[j\]\text{.}c + \sum\_{j=i+1}^n\left(1 - T\[j\]\text{.}c\right) = $$ $$(n - i) +\sum\_{j=0}^i T\[j\]\text{.}c - \sum\_{j=i+1}^nT\[j\]\text{.}c = $$ $$(n - i) +2\sum\_{j=0}^i T\[j\]\text{.}c - \sum\_{j=0}^nT\[j\]\text{.}c = $$ $$- i +2\sum\_{j=0}^i T\[j\]\text{.}c - C$$

where $C$ is just a constant, which doesn't matter if you wish to minimize the quantity. So to find the optimal value:

```
S = 0
best = inf
best_i = 1
for 1 <= i <= n:
    S += 2*T[i].c
    if S - i < best:
        best = S - i
        best_i = i

```
> 1 votes

---
Tags: optimization, dynamic-programming, linear-programming, python
---


# Question
Title: NPC-problem reduction to triangle-free 3-colorability
lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find an NP-complete problem and reduce it to my problem.

I tried it with general 3-colorability, but I was unable to create function F() that would reduce a general graph to a triangle-free graph without changing its colorability.

Is it a good direction? Does it make sense to reduce the 3-colorability problem?

If yes, I would appreciate any advice on how to finish the proof. If I am doing it wrong, I would appreciate any advice on the reduction.

# Answer
We reduce from 3-coloring, following Kráľ, Kratochvíl, Tuza and Woeginger, Complexity of Coloring Graphs without Forbidden Induced Subgraphs. We will need to use a gadget $H$, with the following properties:

* $H$ is a 3-colorable triangle-free graph.
* There are two vertices $a,b \notin H$, not connected by an edge, such that any 3-coloring of $H$ gives $a,b$ different colors.

Given such a gadget $H$, here is how to reduce 3-coloring to triangle-free 3-coloring. We start with a graph $G$. We construct a new graph $G'$ as follows. The graph $G'$ will have all vertices of $G$, together with some new vertices. For each edge $e = (x,y) \in G$, there is a copy $H\_e$ of $H$. We identify $a\_e$ (the copy of $a$ in $H\_e$) with $x$, and $b\_e$ with $y$. This completes the construction.

The new graph is triangle-free. Indeed, suppose that it contained some triangle $u,v,w$. Since the vertices $u,v$ are connected, they must reside in some copy $H\_e$ of $H$. Since $(a,b) \notin H$, at least one of these vertices doesn't belong to $V$, say $u \notin V$. Since all neighbors of $u$ are in $H\_e$, it follows that $u,v,w$ all reside in $H\_e$, contradicting the triangle-freeness of $H$.

If $G$ is 3-colorable, then we can easily complete a 3-coloring of $G$ to a 3-coloring of $G'$ by using a 3-coloring of $H$ (by symmetry, it doesn't matter what colors $a,b$ get, as long as the colors are different). Conversely, the restriction of any 3-coloring of $G'$ to $V$ is a 3-coloring of $G$.

To complete the proof, we need to describe the gadget $H$. Our starting point is any critically 4-colorable triangle-free graph $H'$, such as the Grötzsch graph; here *critically 4-colorable* means that the graph is not 3-colorable, but becomes 3-colorable if we remove any edge.

We take any edge $(a,c) \in H'$ and replace it by an edge $(b,c)$, where $b$ is a new vertex (in particular, $(a,b)$ is not an edge). The resulting graph $H$ is still triangle-free. Since $H'$ was critically 4-colorable, the graph $H$ is 3-colorable: take a 3-coloring of $H' \setminus \\{(a,c)\\}$, and color $b$ appropriately. Any 3-coloring of $H$ must give $a,b$ different colors, since otherwise its restriction to all vertices but $b$ would be a 3-coloring of $H'$.
> 1 votes

---
Tags: graphs, np-complete, reductions, colorings
---


# Question
Title: Analysis of updating vertex and one example?
I see the following image on google:

And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should used sorted array or binary heap for implementation? non of others get us this Amortized Cost?

# Answer
In Dijkstra's algorithm there are $|E|$ **update** operations and $|V|$ **remove\_min** operations.

To implement the algorithm, we can employ different types of data-structures. Since you are looking for the best **update** cost per vertex, you can employ the *Fibonacci heap* or *Hash map* implementation since they give you the minimum **update** cost (as per the table mentioned in your question). Now, suppose you employ Fibonacci heap. Then, the total amortized **update** cost for Dijkstra's algorithm would be $|E| \cdot O(1) = O(|E|)$. Therefore, the amortized **update** cost per vertex is: $O(|E|/|V|)$.

---

These are the three main implementations of Dijkstra's algorithm:

1. Array Implementation (a.k.a. Hash Map as per your table): Update $O(1)$ and Remove\_Min $O(|V|)$
2. Binary Heap Implementation (a.k.a. Hybrid Binary Heap as per your table): Update $O(\log |V|)$ and Remove\_Min $O(\log |V| )$
3. Fibonacci Heap Implementation: Update Cost $O(1)$ and Remove\_Min Cost $O(\log |V|)$

Note that Fibonacci Heap provides the best *update* cost and the best *remove\_min* cost among these three options. Therefore, it is the best of both worlds. Hence, it is best for Dijkstra's algorithm and you can remember this implementation only.
> 1 votes

---
Tags: algorithms, graphs, time-complexity, algorithm-analysis, trees
---


# Question
Title: Given LTL formulas $m$ and $p$, is there a tool that can check whether $m \models p$ does hold?
To the best of my understanding, $m \models p$ asks whether the LTL formula $p$ satisfies the LTL formula $m$. In other words, $m \to p$ is a tautology. Here are some examples of where $m \models p$ holds:

```
Xp |= Fp

q  |= p U q

Gq |= Fq

```

Of course, trying to visualise all this in you head and trying to work out if $m \models p$ holds can get very time consuming, especially if $m$ and $p$ are very long. So, I was wondering there is some tool/software/platform that can compute $m \models p$.

# Answer
Yes, you can use an LTL-to-Büchi-automaton translator for this.

Let's assume that you want to check if $\psi \rightarrow \psi'$ is a valid LTL formula, i.e., every word satisfying the LTL property $\psi$ also satisfies the LTL property $\psi'$. This case is equivalent to finding out if $\psi \wedge \neg \psi'$ is satisfiable. Your $\psi \models \psi'$ notation is another way of writing this, but I would avoid it since the $\models$ relation is often defined differently in current research papers on the topic.

If we translate $\psi \wedge \neg \psi'$ to a Büchi automaton, we can easily check if its language is empty. In fact, optimizing LTL-to-Büchi translators remove states with an empty language, and hence you only need to check if the resulting automaton has no accepting state.

On example LTL-to-Büchi translator is *ltl3ba*. For instance, if you want to check if $\mathsf{F G }\\,a$ implies $\mathsf{G F}\\,a$, you can do that as follows:

```
./ltl3ba -f "(F G a) && !(G F a)"

```

Here, "-f" stands for "translate this formula that is given as a parameter".

The result is given in SPIN never claim form:

```
never {    /* (F G a) && !(G F a) */
T0_init:
    false;
}

```

There is no state ending with "\_accept" in the name, which means in the SPIN never claim notation that there is no accepting state. So $(\mathsf{F G }\\,a) \wedge \neg (\mathsf{G F}\\,a)$ is not satisfiable.

There is also at least one LTL-to-Büchi translator with a web interface, namely the one from the SPOT framework.
> 2 votes

---
Tags: logic, model-checking, linear-temporal-logic, temporal-logic
---


# Question
Title: Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?

# Answer
This shouldn't come as a surprise, but you should definitely be familiar with algorithms and datastructures as well as complexity theory.

Two fundamental text books are downloadable for free, and you can probably find the answer to your question there:

---

But to give my own short answer:

I think knowing some recursion theory (computation theory) is of benefit, since some of the levels in the parameterized hierarchies are based directly on Turing machine theory.

Most crucial is it that you have a good understanding of the complexity classes P and NP, and how to prove that algorithms are running in polynomial time, and how to prove that some problems are NP-complete.

Parameterized complexity is a fun area, enjoy your journey!
> 4 votes

# Answer
If you know Dynamic Programming, I would say you won't face a lot of difficulties studying it. You need to have basic knowledge of design and analysis of algorithms and dynamic programming at least. You can start with Tree-Width and Dynamic Programming. That would be a great place to start studying this topics. Then you will find one thing called 'Nice Tree Decomposition', which can be used to solve a NP-Hard problems using DP. Go through the 'Kernelization' book, it is a very good place to start. Then if you feel lost while studying parameterized algorithms for 3-Coloring, Steiner Tree, Independent set, you can search over the internet and you will find a lot of slides available online. I would suggest you to go through the slides of Daniel Marx titled 'Fixed Parameter Algorithms'.

Hope this helps
> 1 votes

---
Tags: algorithms, complexity-theory, computability, approximation, parameterized-complexity
---


title: Approximation of Set Cover

text:
# Question
Title: Approximation of Set Cover
I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better than $\log n$. So we can use Vertex Cover algorithm to solve Set Cover problem and get a better approximation ratio. Can anyone explain this to me?

Thanks in advance

# Answer
Dinur and Steurer \[1\] showed that assuming $P \neq NP$, there is no polynomial time algorithm which approximates set cover by a $(1-\epsilon)\ln(n)$ factor, for any constant $\epsilon \> 0$.

\[1\] https://arxiv.org/pdf/1305.1979.pdf
> 3 votes

# Answer
**Clarification:** When we say $\ln n$ is the best possible approximation for the set cover problem, we mean it for a general instance of the set cover. That is, there are set cover instances in which an element of the universal set could belong to more than two sets (possibly $\Omega(n)$ also) and for such instances, we can not achieve better than $c \cdot \ln n$ approximation, assuming P≠NP for any constant $c\<1$. Therefore, this lower bound does not hold for the instances when an element belongs to just 2 sets (a.k.a. vertex cover instances). You can check this in the research paper of Dinur and Steurer, as suggested by user3209423940248.

**Answer to your question**: Currently, we do not know any polynomial time reduction from the set-cover instances to the vertex-cover instances. And, if you happen to find such a reduction which could give you better than $c \cdot \ln n$ approximation (for some constant $c\<1$) for the set-cover problem, then you have solved the P-NP problem and you will get famous.

However, assuming P≠NP, such a reduction is not possible.
> 3 votes

---
Tags: algorithms, approximation, set-cover, vertex-cover
---


# Question
Title: Mapping spherical coordinates onto faces of an icosahedron
I'm looking for an algorithm which takes spherical coordinates (say lat-long) and identifies which face of an icosahedron a ray moving in that direction would intersect.

My end goal here is to explore various cartographic map projections from a sphere onto an icosahedron (ex: Gnomic, Fuller Dymaxion, Snyder equal-area). All of these begin with the problem of identifying which face of the icosahedron a given coordinate belongs to and then mapping a standardized spherical triangle onto a standardized flat triangle.

# Answer
The approach in your comment certainly works, and is probably your best bet.

If you think of the Platonic solid centred at the origin, then the coordinates of a a point located at the centre of each face is equal (up to normalisation) to those of a vector normal to the face. So you can, in principle, take a point on the sphere, search all the faces and find the face/normal whose dot product with the coordinates of the point is greatest.

This is surprisingly efficient on modern hardware, because it can use vector instructions effectively.

Do be careful about the fact that the Earth is not spherical. I don't know how these cartographic map projections deal with this (it may not matter with paper maps), but I imagine you would use the normal to the ellipsoid rather than the coordinates of the point on the ellipsoid.

Interestingly, mapping a normal vector to an octahedron is a particularly interesting case because an octahedron can be unfolded into a square. This is such an important problem that there are even survey papers on the topic.
> 3 votes

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


# Question
Title: Is $L:=\{a^k \mid k \text{ is prime}\}$ regular?
For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make sense to me since a while program always returns an element of the integers. How can I use code in my proof?

# Answer
You don’t need any code. If S is any set of integers such that the difference between neighbouring elements becomes arbitrary large, then $\\{a^k: k \in S\\}$ is non-regular.
> 2 votes

# Answer
I don't see how the hint could be useful in applying the pumping lemma except from the fact that there are infinitely many prime numbers. So you start by a picking a word $w$ of the form $a^r$, where $r$ is a prime that is greater than the pumping constant. Then, think how many times you need to pump in order to get a word of the form $a^k$, where $k$ is non-prime. Hint: $k$ is not prime iff it can be written as $k\_1\cdot k\_2$, where $k\_1, k\_2 \notin \\{1, k\\}$.
> 2 votes

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


# Question
Title: Understanding the union of an undecidable language with a finite or decidable language
I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable.

This is confusing me because if $L$ were to be a semi-decidable language, then this would be easy to prove (with either pseudocode or TMs), but as I understand not all undecidable languages are semi-decidable, and I don't know what to do with those ones.

# Answer
> 2 votes
If $L$ is undedidable and $A$ is finite, then $L \cup A$ is undecidable. To see this notice that, given $w \in \Sigma^\*$: $$w \in L \iff (w \in L \cap A) \\; \vee \\; (w \in L \cup A \\;\wedge\\; w\not\in A).$$

Since $A$ if finite both $A$ and $L \cap A$ (which is also finite) are decidable. That is, we can test whether $w \in L \cap A$ and whether $w \not\in A$. If $L \cup A$ were decidable the above formula would then imply that $L$ must also be decidable, a contradiction.

If $L$ is undedidable and $B$ is decidable, then $L \cup B$ might or might not be undecidable, depending on $B$. An example in which $L \cup B$ is undecidable is the one discussed before: let $B$ be any finite language, e.g., $B=\emptyset$. An example in which $L \cup B$ is decidable is $B=\Sigma^\*$ since $L \cup B = \Sigma^\*$.

---
Tags: formal-languages, undecidability, semi-decidability
---


# Question
Title: If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$
I found the following question with an answer here, but I can't understand the steps of the solution.

> Show that if a language $A$ is in RE and $A \leq\_m \overline{A}$, then $A$ is recursive.
>
> **Solution.** Since $A \leq\_m \overline{A}$, it follows that $\overline{A} \leq\_m A$, and since $A$ is in RE, it follows that $\overline{A}$ is also in RE. Since both $A$ and $\overline{A}$ are in RE, it follows that $A$ is in R (this follows from a theorem you learned in class).

Here $\le\_m$ demotes mapping reducibility.

Actually I can't understand most of the answer. In particular:

1. Why does $A \leq\_m \overline{A}$ imply $\overline{A} \leq\_m A$?
2. I understand the following step (why $\overline{A}$ is in RE).
3. Which theorem is used to deduce that $A$ is in R? (I'm not a student in this class)

# Answer
> 2 votes
1. It follows immediately from the definition of a mapping reduction that a reduction $f$ from $A$ to $B$ is also a reduction from $\overline{A}$ to $\overline{B}$. Indeed, if $f$ is a reduction from $A$ to $B$, then, in particular, $x\in A$ iff $f(x)\in B$, which is equivalent to $x\notin A$ iff $f(x)\notin B$, which is equivalent to $x\in \overline{A}$ iff $f(x) \in \overline{B}$. (I only used the fact that $x \to y$ is equivalent to $\neg y \to \neg x$).
2. This follows form the *reduction theorem*: if $A \leq \_m B$, then $B \in RE \to A\in RE$. Try to prove it. Hint: use a machine that computes the reduction, and a machine that recognizes $B$ in order to define a machine that recognizes $A$.
3. To deduce that $A \in R$, they've used the fact that $R \supseteq RE\cap coRE$ (In fact, equality holds). Hint: If $M\_{A}$ and $M\_{\overline{A}}$ are machines that recognize $A$ and $\overline{A}$, respectively, then you know that for every word $w$, at least one of $M\_{A}$ and $M\_{\overline{A}}$ halts on $w$.

# Answer
> 2 votes
The answer to the first question is quite simple. Suppose that $f$ is a mapping reduction from $A$ to $\overline{A}$. Then $f$ itself is also a mapping reduction from $\overline{A}$ to $A$. I'll let you verify that.

Next, let us show that if $A,\overline{A}$ are both RE, then $A$ is in R. How to show that depends on your definition of RE.

* **RE is the set of all languages which can be enumerated.** Suppose that we can enumerate both $A$ and $\overline{A}$. Given a word $w$, here is how to decide whether $w \in A$ or not. Simply run both enumerators in parallel, until $w$ shows up. If it shows up in the enumeration of $A$, then $w \in A$, and if it shows up in the enumeration of $\overline{A}$, then $w \in \overline{A}$.
* **RE is the set of all recognizable languages, that is, there is a Turing machine which halts on an input iff it belongs to the language.** Suppose that there are recognizers for both $A$ and $\overline{A}$. Given a word $w$, run both recognizers, until one of them halts. If the recognizer for $A$ halted, then $w \in A$, and if the recognizer for $\overline{A}$ halted, then $w \in \overline{A}$.

---
Tags: formal-languages, turing-machines, computability
---


# Question
Title: How to determine the pre and post conditions of a program (Hoare-logic)
**Problem**
Below is a program named X:

```
y = 1;
while(y < x){
    y = 10 * y;
}

```

What does this program X do? What are appropriate pre and post conditions?
(Assume that x and y are integers).

**My solution**

Given a whole number x \> 1, X should give us a power of 10 greater than or equal to x.
pre-condition: `(|x = x<sub>0</sub> ∧ x<sub>0</sub> > 1|)`
post-condition: `(|y ≥ x ∧ ∃n(y=10<sup>n</sup>)|)`

However, I don't know if my solution is correct. It would be nice to know how to solve this trivial problem.

# Answer
Here are two other programs that have the same postcondition given the same precondition:

```
y = 1;
while (y < x) {
    y = 100 * y;
}

```

```
x = y = 1;

```

Your postcondition doesn't describe the output it enough detail. In particular:

* The program doesn't change $x$.
* The value of $y$ is the *smallest* power of 10 which is at least $x$.
> 2 votes

---
Tags: hoare-logic
---


# Question
Title: Why do we create universal turing machines?
Why do we create Universal Turing Machine explicilty to simulate the run of a word (say, $w$) on a Turing Machine $M$, given the description on it? Can't we just run $w$ on $M$ itself? I don't see the point of it.

# Answer
Theoretically, the universal Turing machine $U$ was defined to prove the undecidability of certain problems. Roughly speaking, we're talking about a machine that is able to decide what any other Turing machine decides. So assuming that Turing machines fully capture the notion of decidability, then it holds that anything that can be decided, can also be decided by $U$. Conversely, any problem that is not decided by the universal machine $U$ is considered to be undecidable.

To be more concrete, the ability of $U$ to take as input an encoding of another machine $M$ and an input $w$ of $M$, enables us (the machine $U$) to ask questions about other machines $M$. For example, a consequence of this ability is that we can ask whether $M$ halts on $w$: is there a universal machine $U$ that decides whether $M$ halts on $w$? More formally, is there a machine $U$ that decides the language $Halt\_{TM} = \\{ \langle M, w\rangle: M \text{ is a TM and $M$ halts on the input $w$}\\}$.

One, with a diagonalization argument, can prove that the $Halt\_{TM}$ is undecidable. $Halt\_{TM}$ is known as the halting problem: is there a program that eventually halts and tells us whether another program (which is given as input) halts?

So, thanks to universal machines, we can ask all these interesting questions about machines, and get undecidability results.
> 2 votes

# Answer
Basically we are interested in some generalized version of a Turing Machine. Universal Turing Machine is something that can solve any problem. It just needs to be programmed. That's why when we Define a Universal Turing Machine, we write $U(M,x)$, where we say $M(x)=1$ means accept and otherwise reject. Here $M$ can be seen as some program written by some programmer, which we are not interested about. You can think it as your PC, where you can do a lot of stuffs. Some programs are there, some are not. Suppose you install some software, which can be seen as a Turing Machine and your PC is an Universal Turing Machine.
> 1 votes

# Answer
Your desktop computer and your smart phone are Univeral Turing machines because they can be programmed to do whatever we want. That's the point of having Unviersal Turing machines.

If we did not have Universal Turing machines, then instead of just downloading and installing another app (in other words, a word $w$ to be simulated), you would have to buy a new computer every time you wanted new functionality. You'd have a whole lot of computers at home.
> 1 votes

---
Tags: turing-machines
---


title: Regular Expression for language

text:
# Question
Title: Regular Expression for language
I have a grammer with the following productions,

```
S -> aA | bC | b
A -> aS | bB
B -> aC | bA | a
C -> aB | bS

```

I have to construct regular expression for it. I derived words for this language and which are

> b, aab, aba, baa, bbb, aaaab, aaaba, aabbb, abaaa, baaaa, ...

So after I deriving the words I concluded that it's `a language of strings having odd number of b and having odd length`.

Can you please help me to construct regular expression for it.

I appreciate your help.

# Answer
> 0 votes
It seems to me that you may simply consider the automata with states S, A, B, C and exit state X, and with the following transitions:

```
S -a-> A
S -b-> C
S -b-> X
A -a-> S
A -b-> B
B -a-> C
B -b-> A
B -a-> X
C -a-> B
C -b-> S

```

Right?

# Answer
> 1 votes
Note that your grammar is *regular*. Quoting from wikipedia:

> A grammar is regular when no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side. Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language.

In theory, every regular grammar generates a regular language. Also, its not hard to construct the relevant NFA for the generated language: for a specific example on how to do that, you can click here (this is actually what has been done in @Matthieu Latapy's answer). Once you have an NFA for the language, you can translate it into a regular expression (there are several ways to achieve this based on state removal methods which are a bit tedious: see here).

BTW, you already know that your language is all words with "odd length and odd number of b's". It is easy to build a DFA for it consisting of 4 states (hint: your language is an intersection of two languages, each having a DFA with two states).

# Answer
> 0 votes
Your language consists of all strings with an even number of $a$'s and an odd number of $b$'s. How do we construct a regular expression for such a language?

Let us assume for starters that the word starts with $bb$. Thus, it has the form $$ bba^{n\_1}ba^{n\_2} \ldots ba^{n\_m}, $$ where $m$ is even and $n\_1+\cdots+n\_m$ is even. This suggests grouping the $b$'s in pairs $ba^kba^\ell$. There are two types of pairs: a pair with $k+\ell$ even, and a pair with $k+\ell$ odd. If we denote the first type with $E$ and the second type with $O$, then our word is of the form $bs$, where $s$ is a word over $\\{O,E\\}$ with an even number of $O$s. Such words $s$ are described by the regular expression $E^\*(OE^\*OE^\*)^\*$. Also, it is easy to express $E,O$ as regular expressions: \begin{align} E &= b(aa)^\*b(aa)^\* + ba(aa)^\*ba(aa)^\* \\ O &= ba(aa)^\*b(aa)^\* + b(aa)^\*ba(aa)^\* \end{align} Altogether, we obtain a regular expression for all words in your language that start with $bb$.

In the general case, let the word start with $a^kba^\ell b$. If $k+\ell$ is even, then this is the same case as before. Otherwise, we need an *odd* number of $O$s, and so the $\\{O,E\\}$ part of the word is described by $E^\*OE^\*(OE^\*OE^\*)^\*$. Altogether, we obtain the following regular expression: $$ \[(aa)^\*b(aa)^\*+a(aa)^\*ba(aa)^\* + a(aa)^\*b(aa)^\*E^\*O + (aa)^\*ba(aa)^\*E^\*O\]E^\*(OE^\*OE^\*)^\*. $$

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