# Question
Title: Design a data structure with constant insertion and sublinear range maximum query
Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a\_i, b\_i)$, where $a\_i$ is a timestamp and $b\_i$ is an arbitrary real. How can we design a data structure with the following two methods:

1. $\mathcal{O}(1)$ insert
2. Sublinear lookup to determine when, given some timestamp $q$ as an argument, find the maximum value of $b\_i$ for all elements $(a\_i, b\_i)$ already in our data structure with $a\_i$ in the range $(q-1, q)$.

Note: The $a\_i$'s are not necessarily in sorted order in the stream. There are no additional assumptions about the the distribution of the timestamps or the values $b\_i$. While I am looking for a solution with worst-case time complexity for both methods, I would also be interested in seeing if the data structure could be achieved in amortized time complexity for each or both methods.

# Answer
If they're timestamps, there's a good chance they are approximately randomly distributed across some range, say $\[\ell,u\]$. In this case there exist reasonable solution.

You can hash each pair into $k$ equal-width buckets in this range, i.e., using the hash function $h(a,b) = \lfloor N(a-\ell)/(u-\ell) \rfloor$, where $k$ is roughly similar to the number of items seen so far. Within a bucket, remember the largest value of $b$ of all pairs that hashed into that bucket. Then insert can be done in $O(1)$ expected time, and lookup can be done in $O(1)$ expected time.

Of course, we won't know $\[\ell,u\]$ exactly, and $\ell,u,k$ will change over time. However you can adjust on the fly, by keeping track of the smallest and largest timestamp seen and the number of pairs seen so far. Every time the number of pairs doubles, you update the hash function and rehash. Naively, that sounds like it takes $O(n)$ time to rehash, but you can spread that out over the next $n/4$ inserts, maintaining the $O(1)$ expected running time.

---

If the timestamps aren't uniformly distributed but they come iid from some distribution, and the distribution is "smooth" enough, then I think you can find a similar solution. Keep track of the integer-percentiles of the $a$ values (i.e., the 0% percentile value, the 1% percentile value, the 2% percentile value, and so on); it is possible to estimate these values using streaming quantile estimation / streaming histogram estimation. To hash a pair, convert its $a$ value to a percentile (a real number $p$ in the range $\[0,1\]$), using linear interpolation among these 101 known percentile values; then $p$ will be approximately uniformly distributed on $\[0,1\]$, and you can hash $p$ into equal-width buckets as before. If the distribution is smooth enough, linear interpolation will work well and $p$ will be approximately uniformly distributed. If the distribution is not smooth, this may work poorly.
> 0 votes

---
Tags: algorithms, data-structures, search-algorithms
---


title: Different Classes of NP

text:
# Question
Title: Different Classes of NP
I was solving problems related to P and NP where I encountered the following problem:
Given a standard definition of NP,
if x belongs to L then there exists y such that |y| \<= |x|^d and A(x, y) = 1;
if x does not belong to L then for every y with |y| \<= |x|^d we have A(x, y) = 0.
1. what is the new class formed when we don't include the second statement?
2. what is the new class formed when we don't include the first statement?
I am well versed with the definitions of P and NP but unable to figure out how to determine these new classes.
Any help in understanding these concepts would be appreciated.

# Answer
Here is a big hint to help you solve the problem:

> Can you give an example of a language that *is* in this class? Can you give an example of a language that is *not* in this class?
> 1 votes

---
Tags: algorithms, complexity-theory, decision-problem
---


# Question
Title: Definition of Disjointness for binary strings
Basically, most of the definition for disjointness are such that $DISJ(A, B) = 1$ if $A \cap B = \emptyset $ and $DISJ(A, B) = 0$ for other case. My confusion is how is $0$'s influence in here. For example, is all-zeros string considered as $\emptyset$ and therefore the result will be $1$ no matter what the other string is ? Another case is if two disjoint string, e.g., $01$ and $10$ becomes not disjoint after same number of $0$ appended to each string.

Currently my thought is, based on most research papers in communication complexity field, that $DISJ(A, B) = 0$ iff there exists one entry is $1$ for both $A, B$. Would like some clarification and related detailed definition with source.

# Answer
We identify a binary string with a set in the following way: $x \in \\{0,1\\}^n$ corresponds to the set $\\{ i \in \[n\] : x\_i = 1 \\}$. In particular, $0^n$ is identified with the empty set.
> 1 votes

---
Tags: disjoint-sets
---


# Question
Title: Regular expression for all binary strings avoiding 0110
Consider the language $$ L = \\{ w : w \in {0,1}^\* \text{ and } w \text{ doesn't contain } 0110 \text{ as a substring.} \\} $$ What is a regular expression for this language?

I thought of $1(1)^\*0(0)^\*$. But this seemed to not contain any strings starting with $0$. If I do $1(1)^\*0(0)^\* | 0(0)^\*1(1)^\*$ then it can contain $0110$. How can I improve my answer to this question?

# Answer
> 1 votes
A string avoids $0110$ regardless of any initial or final $1$-runs, so we it suffices to consider strings starting and ending with $0$. We can write every such string as follows: $$ 0^{a\_1} 1^{b\_1} 0^{a\_2} 1^{b\_2} \cdots 0^{a\_\ell}, $$ where $a\_1,b\_1,a\_2,b\_2,\ldots,a\_\ell \geq 1$. This string avoids $0110$ if $b\_i \neq 2$ for all $i$.

The following infinite regular expression corresponds to the above: $$ \epsilon + 0^+ + 0^+(1+111^+)0^+ + 0^+(1+111^+)0^+(1+111^+)0^+ + \cdots $$ Here the first summand corresponds to the edge case $\ell = 0$. We can describe all of these cases using a single regular expression as follows: $$ \epsilon + (0^+(1+111^+))^\*0^+ $$ Bringing back the initial and final $1$-runs, this gives the following regular expression for your language: $$ 1^\* + 1^\*(0^+(1+111^+))^\*0^+1^\* $$ Using some case analysis, we can simplify this into $$ 1^\*(0^+(1+111^+))^\*0^\*1^\* $$

---
Tags: regular-expressions
---


# Question
Title: To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$
How do I efficiently find the median of $k$ sorted arrays each of length $n$? Note that the total number of elements will be $nk$. I know it can be done in $O(nk \log k)$ time using merge technique. Is there a more efficient algorithm?

For two arrays it can be done in $O(\log n)$ time, but I can't see how to apply that here.

# Answer
Let us denote the arrays by $A\_1,\ldots,A\_k$, their sizes by $|A\_1|,\ldots,|A\_k|$, their medians by $m\_1,\ldots,m\_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.

Let $m\_r = \min(m\_1,\ldots,m\_k)$ and $m\_s = \max(m\_1,\ldots,m\_k)$. Define $$ N = \sum\_{i=1}^k \lceil |A\_i|/2 \rceil. $$ There are at least $N$ many elements in $\mathbf{A}$ whose value is at least $m\_r$, and at least $N$ many elements in $\mathbf{A}$ whose value is at most $m\_s$.

If $N \geq t$ then elements larger than $m\_s$ cannot be the $t$'th smallest element. In particular, we can throw out the upper half of $A\_s$. Similarly, if $N \geq n+1-t$ then elements smaller than $m\_r$ cannot be the $t$'th smallest element, and so we can throw out the lower half of $A\_r$ (and update $t$ accordingly, by subtracting $\lfloor |A\_r|/2 \rfloor$). Note that $\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$, and so at least one of these cases must happen.

How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $k$ arrays roughly by half (the reduction is $\ell \mapsto \lceil \ell/2 \rceil$). One can check that it takes $\lceil \log \ell \rceil$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is $$ \sum\_{i=1}^k \lceil \log |A\_i| \rceil \leq k + \sum\_{i=1}^k \log |A\_i| \leq k + k \log \sqrt\[k\]{|A\_1| \cdots |A\_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}. $$ After an initial round which takes $O(k\log k)$ time, each subsequent round can be implemented in $O(\log k)$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $k$ elements, and we can run a linear time selection algorithm to find the $t$'th smallest element in $O(k)$. In total, this algorithm runs in time $$ O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|). $$ When $|A\_i|=n$ for all $i$, this is $O(k\log (kn))$.
> 5 votes

---
Tags: time-complexity, sorting, arrays, heaps, mergesort
---


# Question
Title: What is the need for "some constant" times $n$?
I have a question regarding the following sentence:

> So we can make the following expressions:
>
> The best case running time of LINEARSEARCH is a constant function $T(n)=a$ OR $Θ(1)$
>
> The worst case running time of LINEARSEARCH is a linear function of $T(n)=an + b$ OR $Θ(n)$
>
> Merging them together, the running time of LINEARSEARCH is no more than some constant times $n$

There is reference to *some constant*, what is the point of this constant? Why is not just that the running time is $n$?

What is the *some constant* and why does it need to be taken into consideration?

# Answer
> 1 votes
What is the running time of an algorithm? To answer this question, we need to specify an exact computation model with a cost for each operation. Whatever computation model you choose to use, it is highly unlikely that the running time of an algorithm on an input of size $n$ is *exactly* $n$. It is far more likely to be of the form $an+b$ for some constants $a,b$, and even more likely to vary a bit with the exact input, but to be *bounded* by some expression such as $an+b$.

As an example, consider the following algorithm for computing the maximum of an array $A\[1\],\ldots,A\[n\]$:

```
max = A[1]
for i = 2, ..., n:
  if A[i] > max:
    max = A[i]
return max

```

Let us convert it into "machine instructions":

```
      max = A[1]                 (1)
      i = 2                      (2)
LOOP: if i>n, jump END           (3)
      if A[i]≤max, jump CONT     (4)
      max = A[i]                 (5)
CONT: i = i + 1                  (6)
      jump LOOP                  (7)
END:  return max                 (8)

```

Let's assume that each line costs $1$ time unit (this is a quite arbitrary assumption). How much time does the algorithm take on an input $A$ of length $n \geq 1$?

Lines $1,2,8$ run once. Line $3$ runs $n$ times each. Lines $4,6,7$ run $n-1$ times each. Line $5$ runs once per "left-to-right record" of $A$ beyond $A\[1\]$, which can be any number of times between $0$ and $n-1$. In total, the running time is between $3+n+3(n-1)$ to $3+n+4(n-1)$, that is, between $4n$ and $5n-1$.

If we choose a different cost model, we will likely get a different running time. However, this running time will likely still be $O(n)$. This is why big O notation is so useful – it hides such details.

---
Tags: asymptotics, big-o-notation
---


title: Harvard processor structure

text:
# Question
Title: Harvard processor structure
In my books it is written that the concept of pipelining can happen only with Harvard structure as CPU can both fetch data from and write back data to memory at the same time my question is how can fetching and writing back be done at the same time when there is only one bus for data just like von Neumann structure? How can using an instruction bus be helpful when it only carries instruction but not data?

So if I want to add `2+5` here `2` and `5` are data but `+` would be the instruction right?

If I fetch 2 and 5 from data cache and add from instruction cache then execute and again write back the result 7 which would be a data to memory and before the whole process is done fetch another data for example 7 and 6 like in what the book stated according to the picture would it still be fetching (the data 7 and 6) and rewriting the data 7 (result of execution) happen at the same time both these numbers are data and have to be fetched and rewritten using data bus so it still be impossible to fetch and rewrite them at the same time and the instruction bus wouldn't be useful.

# Answer
> 1 votes
This is one of the reasons why most modern general-purpose CPUs have split L1 caches, one for instructions and one for data. (It's not the only reason, of course.)

You see, modern CPU pipelines don't interact with a von Neumann-type bus at all, but directly with cache. As far as the pipeline is concerned, instruction memory and data memory are separate because the caches are separate.

# Answer
> 1 votes
Instruction execution cycle have multiple stages like fetch, decode, execute, write back. An instruction execute in multiple clock cycles (separate one for each stage). In pipelined execution multiple instructions are using different stages. Fetch stage access memory to get instructions. Other stages access memory to load and store operands. If there is a single bus connecting the processor to memory either fetch stage can complete or any of the other stage that access the memory to load /store operands (data). If there is a separate bus for instruction and data (or separate cache for instruction and data), both fetch and other stage that access memory for operands(data) can proceed. It is not necessary that every instruction access memory, while being decoded, executed or writing back the result, but some instruction will always be fetched by the fetch stage in **every cycle**. Presence of split L1 cache for instructions and data is akin to having a Harvard architecture. Even though there is a single bus connecting processor and memory(Von-neumann architecture).

Pipeline stalls are avoided by using Harvard architecture.

"2+5" will take multiple cycles, even multiple instruction to execute. On x86 a simple program will be

```
//two variable to store data

var1 db 2
var2 dw 5

// program
mov ax,[var1]
add ax,[var2]
mov [sum],ax   // where sum is a memory location.

```

So there are three instructions. Say you have 3 stage pipeline Fetch,Decode and Execute. Then every instruction will go through 3 stages in 3 clock cycles. Separate cache for instruction and data will ensure that while Instruction 1 is loading the value of var1 in execute stage using the bus connecting data cache, instruction 3 can be fetched using the bus connecting the instruction cache.

---
Tags: computer-architecture
---


# Question
Title: How do computers really communicate with hard-drives on x86_64?
All of us have saved a file on our computers using a programming language. If I look down through the layers of abstraction, I usually get stuck at a kernel-level call or a C-call like `fwrite();` But even at this already deep level things like filesystems and location of storage are hidden from us. For example, one cannot tell on which drive a file is stored when the partition uses more than one drive, nor do you need to care which file-system is used.

This leads me to an extensive set of questions:

Imagine you are a creator of an OS running on `x86_64.` You have not yet created an abstraction for working with external devices. Somebody now plugs in a device using a USB - Port.

1. Does this interrupt the processor or does this change a flag the OS can read? How would you make sure a routine is set up which will start communicating with the device once plugged in?
2. After this routine is set up, which protocols are you using to communicate with the device? Does it matter that the device is plugged in via USB, or would other ports work the same? If it does matter, how does the program know? (x86: Which assembly instructions are achieving communication with any device?)
3. You have now figured out that the device is indeed a hard-drive. Is communicating with every hard-drive the same? You would now like to - only for the matter of further questions - do the following: If this device contains another OS (OS-signature in boot section), start the other OS (reading), if however, the disk does not contain another OS you would like to inject your data to the disk at byte `disk_size/2`. (Writing) How would you accomplish that? (Protocol?, Assembly - Instruction?) EDIT: In my mind, a UEFI is also a tiny little OS. The boot section - in my mind - correct me if I am wrong - is a part of a hard drive where Bios or UEFI is searching the actual OS. So any OS could start another OS...

Kind regards!

Disclaimer: I am not asking for assembly code, I am asking for the mechanism in general. However, examples given in x86\_64 are welcomed.

# Answer
The processor has a control bus which allows it to tell the motherboard it wants to write somewhere else than RAM. When the processor sets a certain line on the control bus, it can write data to a port instead of RAM.

The processor can send data to certain ports which, by convention, are used to talk to hardware. The Hard-Drives have controllers which will answer to certain values on their respective conventional ports. These will be called commands. SATA drives which are the most common types today use certain ports for bilateral communication between processor and hard-drive.

An example is PIO mode that all SATA compliant drives must respect. In PIO mode (https://wiki.osdev.org/ATA\_PIO\_Mode), the port 0x1f7 is used to send commands to the drive. It will then output its data onto a certain port that the processor will read to fetch the data.

As to USB, it is similar. The USB controller (xhci today see https://wiki.osdev.org/XHCI and https://wiki.osdev.org/Universal\_Serial\_Bus#USB\_2.0\_Host\_Controllers) is actually polling its own USB port to determine if a device is plugged in at some point. This provides the plug and play functionalities.

When you do a read/write operation you use IO ports again just like before but these ports are mapped to RAM addresses creating RAM holes known as the PCI hole. To determine the memory mapped ports locations you need to parse the ACPI tables which are built by the BIOS during initialisation of the system. The ACPI tables have conventional locations in RAM that the OS can look for. Once the OS finds these tables it needs to interpret language known as AML to determine what devices are connected on the computer and where (at what RAM address) to find the ports/registers to communicate with these devices.

Other hardware then hard-drives (keyboard/mouse) work with interrupts and ports which is another complex subject.

PS: Developping your own x86-64 operating system is not that unrealistic. Osdev.org can help on that path. If you have some time and go step by step you will learn a lot.
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Can a computational complexity class be redefined by using any complete (decision) problem?
Let $\mathcal{C}$ be a basic complexity class (such as $\mathrm{NP}, \mathrm{PSPACE}$). And $\mathcal{C}$ is closed under a reduction "$\leq$" (such as polynomial time many-one reduction "$\leq\_{m}^{p}$", polynomial time Turing reduction "$\leq\_{T}^{p}$").

Suppose that a decision problem $L \subseteq \Sigma^{\*}$ is complete for $\mathcal{C}$ under reduction "$\leq$". Let $\[L\]^{\leq}$ denote the closure of $L$ under reduction "$\leq$", which means that $\[L\]^{\leq}$ is a class consists all the languages that can be reduced to $L$. $$\[L\]^{\leq} = \\{ L' \in \Sigma^{\*}| L' \leq L \\}$$

Does $\mathcal{C} = \[L\]^{\leq}$ hold true?

Here is my proof. Firstly, $L \in \mathcal{C}$, thus for every $L' \in \[L\]^{\leq}$, we have $L' \in \mathcal{C}$ which leads that $\[L\]^{\leq} \subseteq \mathcal{C}$.

In the other hand, since $L$ is complete, for every $L' \in \mathcal{C}$, $L' \leq L$. We conclude that $L' \in \[L\]^{\leq}$ which means that $\mathcal{C} \subseteq \[L\]^{\leq}$.

Now, I have proved that $\mathcal{C} = \[L\]^{\leq}$.

If this is correct, I can say that $$\[\text{SAT}\]^{\leq\_{m}^{p}} = \[\text{3-SAT}\]^{\leq\_{m}^{p}} = \mathrm{NP}$$ Am I right?

# Answer
> 3 votes
If $X$ is any NP-complete decision problem, then NP consists of all decision problems which are polytime many-one reducible to $X$.

We cannot replace polytime many-one reductions with polytime Turing reductions, however (unless NP=coNP), since coSAT is polytime Turing reducible to SAT.

---
Tags: np-complete
---


# Question
Title: I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y}
So far i've tried with making x = z = p and y = 2\*p, but it seems that if I place vxy to represent all b's then I can't get a contradiction.

# Answer
> 1 votes
The pumping lemma for context-free languages says the following:
For every context-free-language $L$ there exists a constant $p$ such that for every word $s \in L$ of length at least $p$, we can write $s = uvwxy$ and:

* $|vx| \ge 1$
* $|vwx| \le p$
* $uv^nwx^ny \in L$ for $n \ge 0$

To prove that $L = \\{a^xb^yc^z: x \< y \land x = z \\}$ is not context-free we will do the following:
Assume language $L$ i context-free and let $p$ be the constant from the pumping lemma.
Take the word $s = a^pb^{p+1}c^p$, which is clearly in $L$, and express it as $s = uvwxy$ as is stated in the lemma.
We know that $|uvw| \le p$ so $v$ consists only of $a$'s.
Denote $s\_n = uv^nwx^ny$
Now consider the possible cases:

1. If either $v$ or $x$ contain more than one letter, than $s\_2$ will not be of the form $a^\*b^\*c^\*$, so we know that $v$ and $x$ will consist of at most one letter.
2. If $v$ is empty and $x$ consists of $b$'s then $s\_0$ will not have more $a$'s than $b$'s. If $x$ consists of $c$'s then $s\_2$ will have more $c$'s than $a$'s.
3. If both $v$ and $x$ are non-empty then if $v$ consists of $a$'s and $x$ of $b$'s then we in $s\_2$ we will have more $a$'s than $c$'s. If $v$ consists of $a$'s and $x$ of $c$'s than for large enough $m$ in $s\_m$ we will have more $a$'s than $b$'s. If $v$ consists of $b$'s and $x$ of $c$'s then in $s\_2$ we will have more $c$'s than $a$'s.
4. If $v$ and $x$ consist of the same letter (i.e $w$ is empty) then following the same type of reasoning we will also reach a contradiction.

Thus we have reached a contradiction for every possible case and so $L$ is not context-free.

---
Tags: context-free, pumping-lemma
---


# Question
Title: What algorithm is most suitable for large text compression?
Currently, I am looking for an lossless compression algorithm that is suitable for a large amount of text, that will be further encrypt by AES and use as the payload in steganography.

Based on A Comparative Study Of Text Compression Algorithms, it seems that Arithmetic coding is preferable in Statistical compression techniques, while LZB is recommended for Dictionary compression techniques.

So now I am wondering whether Statistical compression or Dictionary compression is more suitable for large English text compression in terms of compression ratio and ease-to-implement.

I have search through but still barely have an idea of the suitable algorithm. Thank you very much for your time in answering. Have a nice day. :)

# Answer
The Linux kernel has a huge source code, with about 3.2 million lines of code. Source code is totally text, so this can give you an idea about the level of compression that is possible. The entire source code is distributed as a .tar.xz file. Its size is close to 110 megabytes. This offers great compression. Decompress it and see the difference in file size!
> -2 votes

---
Tags: data-compression
---


# Question
Title: "Reshaping" vs Polymorphism In Data Wrangling
A lot of the work in data science -- machine learning in particular --involves "reshaping" arrays, tables, and other data structures. These data transformations are not really lossy transformations (except for subsets/selective views), but rather simply getting existing data into a different *form* acceptable to existing algorithms.

This seems to be a big step backward in computer science, away from data abstraction. In particular, it seems polymorphism has somehow been forgotten in all the work geared toward morphing the data into the proper form.

Am I missing something about this problem that renders it particularly immune to the application of mature technologies to hide data representation from the abstract functions?

# Answer
> 1 votes
> Am I missing something about this problem that renders it particularly immune to the application of mature technologies to hide data representation from the abstract functions?

I would say so. And that is empirical experience of what works.

In theory data is data. A general artificial intelligence agent should be able to classify a picture as a cat or a dog regardless of whether it's a photo, a drawing, in color or black/white, altered through an Instagram filter to have a human face, a PNG, JPEG or MP4, compressed with zip, or infinite other possibilities.

But that's purely theory. In practice data representation matters, **a lot**. The very same task your machine learning method gets state of the art on might not learn at all if you change the data representation. In practice *feature engineering* is a huge part of any machine learning project. And the existence and importance of this task should indicate that with current techniques it's not feasible to even begin to think of hiding the data representation.

---

As an example, take the recent success of GPT-3 and transformers. **The entire novelty of this technique** comes from the way data is represented and learned from inside the neural network.

Another example, AlexNet. It popularized the now standard deep convolutional neural network. **A convolutional neural network only really 'works' on (multiple slices of) 2D data**. Any other representation and the convolution stops making any sense at all.

In state of the art machine learning, data representation is *everything*.

---
Tags: machine-learning, polymorphisms
---


# Question
Title: Can I assume every clause of 3SAT has one positive literal?
Can we assume that each clause in 3SAT contains at least one positive literal? That is, there is no clause with all negative literals (but it is fine that there is a clause with all positive literals).

# Answer
No, you can't.

If each clause has at least one positive literal, then, by assigning TRUE to all variables, one gets all clauses satisfied.
> 2 votes

# Answer
You can assume this, in the sense that you can transform a 3SAT problem into this form with only polynomial size overhead. The idea is to to a Tseitin Transform on one variable in each clause with 3 negative literals.

So if you wanting to eliminate $\lnot x$, you introduce a fresh variable $y$ and add the clauses $ x \vee y$ and $\lnot y \vee \lnot x$. This is basically just encoding $\lnot x \iff y$. You can add a third dummy positive variable to ensure that these clauses also are not all negative.
> 1 votes

---
Tags: complexity-theory, satisfiability, 3-sat
---


# Question
Title: Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time
I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values:

```
a, b, c, d ⊆ ℝ
i ⊆ {true, false}

// unconditional inequality constraints
a < b

// conditional inequality constraints
i -> b < c
i -> b < d
!i -> b > c
!i -> a < d

```

and I would like to answer questions about the system, such as "is **a** greater than **d**?" and "is **c** less than **d**?".

One approach would be to formulate this as an integer linear program: in the example above, the non-indicator variables would have domains \[0, 3\], the indicator variables \[0, 1\] and a feasible solution might be:

```
i = 0 (false)
a = 0
b = 1
c = 0
d = 2

```

I could then answer "is **a** greater than **d**?" by comparing the integer values assigned to **a** and **d**. However, I could get the wrong answer for "is **c** less than **d**?": the solution above suggests yes, but there exists another feasible solution

```
i = 0 (false)
a = 0
b = 3
c = 2
d = 1

```

in which the answer appears to be no. (The correct answer is that we cannot determine the relationship between **c** and **d**.)

Now, I could generate ALL the feasible solutions, iterate over them, and check whether `c < d` in each one -- but I have to answer enough of these questions that this approach would be too slow.

Is there a more efficient and elegant way? Perhaps constraint programming is not even the right way to think about this -- I considered formulating it as a directed graph-search problem instead, where directed edges represent inequality relationships, but my actual system contains conditional constraints as well. The wonderful answer that I received on a related question (https://scicomp.stackexchange.com/questions/36090/constraint-programming-problem-with-conditional-constraints-and-some-unknown-ind) directed me here. Glad for any suggestions or references to relevant papers or textbooks!

Edit: After asking this question to several people (both here and elsewhere), I have received multiple suggestions to reduce these constraints to a comparability graph. To illustrate the challenges of this approach, I have added conditional constraints to my example system above. Is there a way to incorporate such constraints into a comparability graph?

# Answer
> 1 votes
If the constraints you have are of the form $a \< b$ and $a=b$ (i.e., only unconditional inequality constraints), you can model them with a directed graph: each node represents a variable, and an edge $v \to w$ corresponds to the inequality $v \< w$. Then you can answer queries by doing a straightforward reachability check. (If you see the equality $v=w$, then merge the two vertices $v,w$ into a single vertex.)

---

When you add conditional equality constraints, the problem becomes NP-hard.

Proof of NP-hardness: I will show a reduction from 3SAT to your problem. Suppose we have a 3SAT formula $\varphi$ on variables $x\_1,\dots,x\_n$. Consider a single $C\_i = \ell\_i \lor \ell\_j \lor \ell\_k$, where $\ell\_i,\ell\_j,\ell\_k$ are three literals (e.g., $\ell\_i$ is either $x\_i$ or $\neg x\_i$, etc.). We will translate this to the constraints $$\begin{align\*} \ell\_i \implies &y\_{i0} \> y\_{i1}\\ \neg \ell\_i \implies &y\_{i0} \< y\_{i1}\\ \ell\_j \implies &y\_{i1} \> y\_{i2}\\ \neg \ell\_j \implies &y\_{i1} \< y\_{i2}\\ \ell\_k \implies &y\_{i2} \> y\_{i3}\\ \neg \ell\_k \implies &y\_{i2} \< y\_{i3}\\ \end{align\*}$$ $$y\_{i0} \> y\_{i3}$$ Notice that if at least one of $\ell\_i,\ell\_j,\ell\_k$ are true, then these seven constraints are simultaneously satisfiable; but if $\ell\_i,\ell\_j,\ell\_k$ are all false, then they are not satisfiable. So, we translate each clause of $\varphi$ into several constraints as above, obtaining a large system of constraints. Then this system has a satisfiable solution if and only if $\varphi$ is satisfiable.

In conclusion, testing satisfiability of your kind of constraints is NP-hard. It follows that answering queries is also NP-hard (answering a query is the same as testing satisfiability of the constraints plus the query). Consequently, you shouldn't expect any algorithm that is both efficient and always correct.

If you have to solve it in practice, you could try applying a SAT solver. Add boolean variables $s\_{b,c}$ to represent $b\<c$; then you can translate each constraint into a clause. For instance, $b\<c$ translates into $s\_{b,c}$, and $i \implies b\<c$ translates into $\neg i \lor s\_{b,c}$. Finally, add clauses that enforce the consistency of the $s$'s, i.e., $\neg s\_{a,b} \lor \neg s\_{b,c} \lor s\_{a,c}$ for each $a,b,c$. Now answering a query amounts to conjoining the query and testing satisfiability of the resulting SAT formula, which you could do with an off-the-shelf SAT solver. Some SAT solver allow you to "push" a clause, test satisfiability, and then "pop" the clause.

# Answer
> 0 votes
Is there a specific language you must write that in?
If not, then if all you need are questions of type $x = y$? and $x \< y$?, I would say Prolog is a safe bet. You could just load your equalities and inequalities as rules and then add a general rule that says that $\<$ and $=$ relations are transitive and $=$ is also reflexive and then you could ask a question like "Is it true that $b \> c$?"

---
Tags: integer-programming, constraint-satisfaction, constraint-programming, comparison, smt-solvers
---


# Question
Title: Compression algorithm for statistical data with a desired outcome size
I did some basic research on regular lossy and lossless compression algorithms but somehow I couldn't really figure the right direction for the information I need.

My basic problem is that I would like to compress a series of numbers with an unknown number of data points (can be 10, can also be a 1000). The numbers themselves are domain-specific in a way that I know what they mean. For example I have LAT/LONG from GPS-Data but also Degrees from a Gyroscope or Acceleration in G's from an Accelerometer.

What I am doing is basically whenever something changes for example in acceleration I store the value. At the end what I want to do is to compress this series of data by providing the *maximum* size of the compressed data which should then affect not the data itself but its actual accuracy. For example acceleration would always result in a simple diagram at the end with more or less accuracy depending on the provided output size.

Does something like that exists? Could you maybe throw me into the right direction?

The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.

I hope its understandable if not please let me know so I can try to explain the issue a little bit further.

# Answer
I don't know of any scheme, but it's possible to define one, so I'll propose one here. In particular, one possibility would be to compress this into a piecewise-linear function, where you replacing a segment of data with a line (a piece), and where you choose which segments to do that to in a way that minimizes the loss. This might work well if your data contains occasional periods of activity followed by long stretches of inactivity.

Here is a candidate metric to measure how much loss is incurred by the compressed version of the data. Suppose you have data points $(x\_i,y\_i)$; and after compression and decompression you assign $\hat{y}\_i$ to $x\_i$. Then I suggest measuring the loss as

$$L = \sum\_i (y\_i - \hat{y}\_i)^2.$$

Then it is possible to use dynamic programming to construct a piecewise linear approximation that uses $k$ pieces and, out of all such piecewise linear approximations, choose the one minimizes the loss $L$. In particular, let $A\[i,j\]$ denote the lowest-loss piecewise linear approximation for $x\_1,\dots,x\_i$, using at most $j$ pieces. Then we have a recursive relationship

$$A\[i,j+1\] = \min\_{i\_0} A\[i\_0,j\] + \ell\_{i\_0+1,i}$$

where $\ell\_{i\_0+1,i}$ denotes the loss associated with the best-fit line going through points $(x\_{i\_0+1},y\_{i\_0+1}),\dots,(x\_i,y\_i)$ (can be found using linear regression). You can then fill in the entries of the $A$ matrix using dynamic programming and find the best piecewise linear approximation that uses $k$ pieces.

This lets you find the best piecewise linear approximation, given a maximum size $k$ for the compressed data (since the size of the compressed data is proportional to $k$). Of course, you can generalize this idea to use piecewise polynomial functions or some other form of approximation.
> 0 votes

# Answer
> Does something like that exists? Could you maybe throw me into the right direction?

> The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.

When talking about signals that change over time with a fixed sample rate your question actually has a proper mathematical answer. It can be beaten for very specific kinds of signals that have patterns in them you already know beforehand, but if it's a generalized signal over time without any further information, it's essentially as good as it gets.

And that answer is found in the Fourier transform. By first transforming your data from the time domain into the frequency domain you get all the power you desire. You become time-independent, and you can drop the coefficients that are above frequencies you care about. You can also downsample, using more/less bits for coefficients that are important/not important.
> 0 votes

---
Tags: algorithms, data-compression
---


title: #perfectMatchings is self-reducible

text:
# Question
Title: #perfectMatchings is self-reducible
How can one show that the counting problem:

Given a graph, output the number of perfect matchings

Is self reducible?

I found a hint in Moore's Chapter on Counting, Sampling and Statistical Physics:

> Let G be a graph and e one of its edges. Show that we can modify G to produce two graphs, G0 and G1, such that the number of perfect matchings of G that include and exclude e is the number of perfect matchings of G1 and G0 respectively.

But I could not come up with a proof. The main question here is: How can we proof self-reducability of #perfectMatchings?

Aside: I don't know of a formal definition of self-reduciability. I just know the intuitive phrasing "partially solving the problem results in a smaller problem of the same kind". But is there a formal definition?

# Answer
> 2 votes
To count all perfect matchings containing an edge $e = (x,y)$, simply remove both endpoints $x,y$. To count all perfect matching not containing the edge $e$, simply remove the edge.

---
Tags: complexity-theory, counting
---


# Question
Title: Turing machine state transition diagram vs finite state machine state transition diagram
If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would there be any difference between the diagram representing the deterministic Turing machine and the diagram representing the deterministic finite automata, or is the difference between them in the context that surrounds the diagram and in the labeling ie. one can read and write to the tape while the other can only read?

# Answer
Summary : you may still be able to tell them apart , but not necessarily

First refere to the formal definition to a Turing machine from Wikipedia

Now consider the transition function δ :

1. First , δ does not allow transitions from accepting states , so in a state diagram of a TM you expect some state to have no transitions from it , unlike a DFA where every state must have transitions out of it , other definitions of TMs allow transitions from final states , but have accept/reject states taking effect immediately , and so you don't expect these states to have transitions
2. δ is a partial function , thus you don't need to define a transition for each state and each symbol , unlike DFAs which require a transition from each on each symbol (refer to Wikipedia under complete and incomplete) , so in a DFA you have all states having equal number of transitions/arrows from them but not necessarily in a Turing machine

Arguments :

1. 1 would be nullified if TM and DFA have no final states to begin with
2. 2 can also be nullified should we choose to provide transition from all states on all symbols for a TM , or go for the less common alternative definition for the DFA in Wikipedia and then not all states need to have equal number of transitions
> 1 votes

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


# Question
Title: Optimal scheduling order for two queues of jobs
I have two queues of jobs and each job consists of the pair (utilization %, time to complete). I have one machine and its utilization cannot exceed 100%. The first job in a queue must be completed before the second one can be started (and so on). What is an algorithm to find the best schedule for these jobs so that the total time is minimized?

# Answer
There is a simple pseudo-polynomial time algorithm that works when all tasks take the same unit time. You can transform your problem into this by rounding all completion times to some greatest common divisor, and splitting all longer tasks up into copies of unit portions. E.g. if your original completion times were $6$, $8$ and $12$ seconds you could use $2$ seconds as your unit time. Then you'd have respectively 3 copies, 4 copies and 6 copies of the unit task in a row.

Let's name the two queues $A$ and $B$. Let $T\[i,j\]$ be the optimal time needed to run the first $i$ tasks from $A$ and the first $j$ tasks from $B$. Let $A\[i\]$ be the resources required for task $i$ from $A$ and similarly for $B$. Let $m$ be the maximum number of resources available.

Of course $T\[x,0\] = T\[0,x\] = x$. Then:

$$T\[i,j\] = 1 + \begin{cases}T\[i-1, j-1\] & \text{if }A\[i\] + B\[j\] \leq m\\\min (T\[i-1,j\], T\[i,j-1\]) &\text{otherwise}\end{cases} $$

If you keep track of your choices you can reconstruct the optimal solution. The above is also amenable to bottom-up dynamic programming, in fact you only need to have two arrays $T\_i\[j\]$ and $T\_{i-1}\[j\]$.

---

I'm not claiming the above is terribly good or an optimal solution, but it's a simple algorithm that gets the job done. Perhaps someone else has a better answer.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Is there any hope for real "simulated machines" in our lifetime?
Without going into details about my life's story, here's the basic facts:

* I grew up with 386 and 486 and Pentium PCs running MS-DOS 5 (I believe), Windows 3.1 and Windows 95, a well as various game consoles from the 8-bit, 16-bit and 32-bit eras.
* I have almost none of them left, and what's more, most game cartridges are long sold off, and I no longer have a working CRT TV.
* I have regularly and extensively tested just about every emulator in existence since the late 1990s, on both x86, Xbox, ARM (RPI) and other platforms. To me, they are all useless, even after heavy configuration/fine-tuning. I will have to accept your opinion if you disagree, but please don't try to convince me that it's like running the real thing. (The RetroArch filters/shaders look nothing like a CRT, BTW.)
* All of those cheap "NES Mini"-like re-release consoles preloaded with games are nothing like the real thing. Useless.
* All of those expensive third-party retro multi-consoles, whether they use FPGA or emulation, are also useless.
* Everdrives are really cool in theory, but I recently found out that they do use emulation/approximation after all, for the hardware chips found in numerous/most game cartridges. This means that it won't be *quite* the same as running it on the real hardware, even if it's probably extremely difficult to tell any difference in this case.
* Buying actual old hardware now is impossibly expensive unless you get very lucky offline.
* Finding a new/non-junk CRT TV is impossible for me. (May not be for you, depending on your context.)
* VMware, Virtualbox, Virtual PC, DOSBox all don't work anywhere near a real IBM PC.

Barring me suddenly striking gold and becoming rich enough to actually buy real "new old stock" copies of all the games and computers and consoles and things I ever wanted, and decorate a dedicated "Angry Video Game Nerd" room, is there any hope to getting this in virtual form within a few years or so? Or will this take so long that, by the time we do get it, the only ones who were actually there are 90+ and senile anyway? And the ones who are young then won't know the difference either way?

From past discussions, I've learned just how computationally expensive and difficult it is to actually simulate a machine, even a relatively simple one, properly. It seems like almost infinitely more powerful computers than those we have today would be necessary for this to ever become reality.

In my dream scenario, I launch a program on my desktop called `Nostalgia.exe`. This brings up a fullscreen 3D room which looks just like my old boy room in the house, long ago in a different era. There, I can virtually walk up to my 486 PC in a first person view (my avatar has the exact same height as I had when I was nine years old), virtually press the power button, hear the loud fans spin up and seeing the BIOS screen with the big "IBM" logo show on the 14" virtual CRT monitor, and then it loads into Windows 3.1 and I'm able to use it as if I were back there again, exactly like the real computer.

No "VMware tools". No weird error messages or glitches that didn't happen on the real hardware. No incorrect speed-ups or slow-downs. Exactly like it was back then, or would be now if I had the real hardware still around and in working condition.

And when I get bored of that, I walk over to the virtual SNES, put in my Top Gear cartridge, flick on the power, pick up the virtual SNES controller and rock away to the amazing soundtrack as the sprites fly past me on both sides on the virtual 14" PAL CRT TV with the RF connector between it and the console.

And then a virtual Mother tells me that the food is done, and that the new Donald Duck cartoon has arrived in the mail... Alright, that's perhaps going a bit too far, but you get the idea... Of course, since this is a virtual world, I have a secret door in the wall which opens up straight into a massive virtual arcade, with all the games powered on at once and in attract mode, with me walking around in the darkness and putting virtual coins (yes, my specific currency) into the slots.

I know that "similar" things have been done in a very lame manner, typically for VR, using normal emulators inside 3D environments. This is not what I'm talking about, and I have no requirement whatsoever that it needs to be VR. I don't even have a VR headset anymore.

To make it clear, I'm not saying that I think that this exists. I'm wondering when, if ever, I can expect it to become reality. Because the current options to re-experience our childhoods just don't cut it.

# Answer
The problem with retro machines is that their abstractions are not isolated from the underlying physical phenomena very well. What you describe requires faithful physics simulation, which would also require quantum mechanics simulation, and we don’t know yet whether it is possible to simulate QFT fully even if we had large-scale quantum computers.

So, currently the only way is faking all noticable effects, and this way may never end.
> 1 votes

---
Tags: simulation
---


# Question
Title: Use the diagonal method to prove that there is a total function from N to N which is not computable
I'm really not sure how to approach this problem.

# Answer
> 0 votes
Hints:

* The diagonal argument proved the real numbers to not be countable.
* Computable: there is an algorithm that computes it -\> there is a Turing machine that computes it. Are those countable?

---
Tags: computability
---


# Question
Title: Deciding whether complement of context-free language is context-free
I need to find out if the following problem is decidable:

> Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language.

I am having trouble in defining the $TM$ I need in order to solve this problem. My thinking was to see if it is possible to construct a $TM$ that takes an encoding of a $CFL$ as input and halts in an accept or reject state depending on whether $\bar{L}$ is a $CFL$ or not. Is this line of thinking correct? If so, may I also know how to proceed further.

# Answer
Your problem can be formalized in several equivalent ways:

1. Given a context-free grammar $G$ over $\Sigma$, is $\overline{L(G)} := \Sigma^\* \setminus L(G)$ context-free?
2. Given a PDA $M$ over $\Sigma$, is $\overline{L(M)}$ context-free?

Since we can effectively (and efficiently) translate between the two representations, both problems are equivalent. We stick to the first one.

It is well-known that given a context-free grammar $H$ over $\Sigma$, deciding whether $L(H) = \Sigma^\*$ is undecidable. We will reduce this problem to Problem 1.

Let us be given a context-free grammar $H$ over $\Sigma$. If $\Sigma$ is a singleton, then $L(H)$ is regular, and so $\Sigma^\* \setminus L(H)$ is also regular and context-free. Otherwise, let $a,b \in \Sigma$ be two distinct symbols. Construct a grammar $G$ over $\Sigma \cup \\{\\#\\}$ (where $\\#$ is a fresh symbol) for the language $$ L = (\Sigma^\* \setminus \\{ww : w \in \Sigma^\*\\}) \\# \Sigma^\* \cup \Sigma^\* \\# L(H). $$ If $L(H) = \Sigma^\*$ then $L = \Sigma^\* \\# \Sigma^\*$ is regular, and so its complement is regular and context-free. Otherwise, let $x \notin L(H)$. If $\overline{L}$ were context-free, then so would the following language be: $$ \overline{L} \cap \Sigma^\* \\# x = \\{ww : w \in \Sigma^\*\\} \\# x. $$ This would imply, however, that $\\{ww : w \in \Sigma^\*\\}$ is context-free, which is known to be false.

Summarizing, $\overline{L(G)}$ is context-free iff $L(H) = \Sigma^\*$.

Compare Theorems 11–12 in Hendrik Jan's notes.
> 6 votes

---
Tags: automata, context-free, undecidability
---


# Question
Title: Looking for clarity on step in fractional knapsack problem proof
I'm reading through the proof for the fractional knapsack problem presented here: https://www.cs.rice.edu/~nakhleh/COMP182/Knapsack.pdf

I follow the proof until the definition of the new set $Q = \langle q\_1, q\_2, ..., q\_n \rangle$

* for every $1 \leq i\<j: q\_{i}=o\_{i} ($also $q\_{i}=y\_{i})$ which is constructed as follows:
* $q\_j=y\_j$
* For $i=j+1$ to $n$

\begin{array}{l} \- d^{\prime} \leftarrow \min \left(q\_{i}, d\right) \\ \- q\_{i} \leftarrow q\_{i}-d^{\prime} \\ \- d \leftarrow d-d^{\prime} \end{array}

I don't understand where the $q\_{j+1...n}$ elements come from. We only fill $Q$ up to $q\_j$, but to fill $q\_{j+1}$ we reference $q\_i$ which is undefined — should it be 0? What am I missing?

# Answer
All appearances of $q\_i$ on the RHS are errors -- they should be replaced with $o\_i$. I imagine the author was thinking of "initialising" $Q$ to be equal to $O$, and then updating its elements in-place.

Another minor issue I have is with the line "After this procedure is done, the total value of the solution $Q$ is equal to the total value of $O$ (make sure youunderstand why!)". This is true, but as this is the key part of an introductory proof, I think it would have been better to break it into its two parts:

1. For any $k \> j$, moving positive weight from $o\_k$ to $o\_j$ results in a solution with value $\ge$ the original solution.
2. The original solution $O$ was assumed optimal, so the $\ge$ becomes a $=$.
> 0 votes

---
Tags: knapsack-problems
---


# Question
Title: Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Given the following language, I am tasked with giving a context-free grammar that generates it.

$\left \\{ a^{3n}b^{m}c^{n}|n\>0, m\>0\right \\}$

Would this be correct?

$A \rightarrow aaaA$
$B\rightarrow Bb | b$
$C\rightarrow Cc|c$
$S\rightarrow ASBSCS|\epsilon $

# Answer
Unfortunately your grammar generates only $\epsilon$ (which is not in the language, since $n$ and $m$ are greater than 0), as you don't delete the $A$; moreover you don't control that the number of $A$'s is thrice the numeber of $C$'s.

You can try something like this:

$S\rightarrow aaaS'c$
$S' \rightarrow aaaS'c | B$
$B\rightarrow Bb | b$
> 2 votes

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


# Question
Title: How to calculate the output frequency of this counter?
The present state Q2,Q1,Q0 of the counter before applying the clock pulse was (101). If the input Clock frequency to the circuit is 100KHz, then the output frequency of the circuit will be ?

My Approach: I have built the state table and I concluded that from 101 it goes to 010 and from 010 to 101 again so it acts like mod-2 counter. But I don't understand the part in which we're applying frequency. Can someone help me to visualize it?

# Answer
The J-K Flip-Flops in your circuit are positive edge triggered, (since they have a `>` mark on the clock input of their schematic.)

Positive edge triggered means that the Flip-Flops are triggered on the *rising* edge of the clock.

If the input frequency is $f$, the time between 2 successive rising edges of the input clock is $1/f$ seconds.

The output toggles on the rising edge of the input clock, since the output goes from 101 -\> 010 -\> 101 and so on. So each bit of the output becomes HIGH on a rising edge of the clock and LOW on the *subsequent* rising edge of the clock. In other words, each bit of the output becomes HIGH on every **second** rising edge of the input clock. Thus, each bit of the output becomes HIGH every $2 / f$ seconds. The frequency of the output is then $f / 2$ Hz.

For f = 100 kHz, the output is f = $(100 * 10^3 / 2)$ Hz = 50 kHz

**Computer simulation results:**

In the waveform above, which is created from a simulation of your circuit, `clk` is the input clock and `q` is the output. `q[2]`, `q[1]`, and `q[0]` represent the outputs of the Q2, Q1 and Q0 flip-flops respectively.

From the waveform it can be observed that frequency of the output is half of that of the input.
> 0 votes

---
Tags: digital-circuits
---


# Question
Title: Proving NP-completeness for a not so cheesy problem
Let's say we have a matrix M\[1..B, 1..B\] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. The mouse can move from a given positon (i, j) either in the direction (i+1, j) or (i, j+1). When the mouse visits a given position (i,j), it collects all the given cheese immediately, so if it decides to return to an already visited position, it will already be empty. Additionally, the mouse can ONLY reverse/back ONCE when traversing the matrix, because we can assume that this mouse doesn't particularly like to change its mind.

So given all these prerequisites, the question is whether or not it is possible for the mouse to collect exactly A pieces of cheese, starting from the position (1,1) and ending up in the position (B,B)?

There should be a proof that this problem is NP-complete by showing it is in NP and by reducing the NP-complete problem Subset Sum.

For showing it is in NP I was thinking about maybe looping through the whole matrix and counting the total number of cheese and then maybe have some sort of boolean condition to check whether or not the amount of cheese the mouse has collected equals to the total amount of cheese located in the matrix and that this will take polynomial time to do. However, I am not sure this is the right way to do and I am even more unsure of how to reduce Subset Sum to this problem. Thus, I am grateful for your help and advice!

# Answer
The problem is in $NP$ since a certificate is the path itself, which has length at most $2B-1 + 2 = 2B+1$.

Given an instance $\langle S, k\rangle$ of subset sum where $S = \\{x\_1, \dots, x\_n\\}$ is a set of integers and $k$ is the target value, you can create an instance of your problem by choosing: $B=n+2$, $M = \mbox{diag}(0, x\_1, x\_2, \dots, x\_n, 0)$, and $A = k$.

Clearly any path in $M$ that collects $A$ pieces of cheese implies the existence of a subset $S' \subseteq S$ such that $\sum\_{x\_i} x\_i = A = k$.

On the converse notice that, given any $S' \subseteq S$ satisfying $\sum\_{x\_i} x\_i = k$, it is possible to find a path $P$ in $M$ with the sought constraints (actually, backtracking is not even required) that traverses $M\[i+1, i+1\]$ if and only if $x\_i \in S'$. This shows that pieces of cheese collected by $P$ are exactly $k=A$.

Also notice that your problem can be solved by pseudopolynomial-time dynamic programming algorithm having complexity $O(A \cdot B^2)$.
> 0 votes

---
Tags: algorithms, np-complete, np-hard, np, matrices
---


# Question
Title: How a swapper manipulates entire processes in the operating system?
The below-given lines are written in the book of the operating system (Page -307), details of the book are as follows:

OPERATING SYSTEM PRINCIPLES, 7TH ED., Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Wiley India Pvt. Limited, Nov 27, 2006

"A lazy swapper never swaps a page into memory unless that page will be needed. In the context of a demand-paging system, the use of the term swapper is technically incorrect. ***A swapper manipulates entire processes***, whereas a pager is concerned with the individual pages of a process. We thus use pager, rather than swapper, in connection with demand paging."

Can you please kindly explain how a **swapper manipulates entire processes**?

# Answer
One processor can only execute one process at a time. Today processors have several cores/threads in the same chip. Even if you have one core in your processor, the OS needs to swap the entire execution context (the entire process) in order to execute something else and it needs to do it efficiently to prevent latency in rendering.

What is called a swapper here is the part of the OS which does this execution context swap.

For example, on Linux the task\_struct is a structure containing the process information. When Linux calls schedule(), the function will determine what process should run next and on what core based on priority. This priority is probably stored in the task\_struct.

Paging swapping and process swapping is quite different. Every process has its own page tables.

For example, on x86-32 systems (32 bits systems) you are going to have 2 levels of page table: PDT (page directory table) and PT (page table). The CR3 register contains the address of the bottom of the PDT and the PDT contains addresses of the PTs. Since on most systems pages are 4KB, one PDT, which has itself a size of 4KB, can map up to 4MB. If your PDT is full, it will thus map the whole address space available (4GB) (https://wiki.osdev.org/Paging). A virtual address is separated in chunks representing the offset in respective tables. For virtual address 0xABCDEF12, on x86-32 you have 0xF12 as the offset in the physical page, ten bits as the offset in the PT and the most significant 10 bits as the offset in PDT.

When a process swap occurs, all page tables are kept in memory (RAM) and the actual physical pages are kept where they are. The only thing which changes is the CR3 register which will point to a new address. At this address is another PDT for the new process taking place. The TLB (page cache) needs to be flushed as well.

Page swapping is completely different. It involves taking pages that are on a swap partition on the hard-disk and loading it to RAM. Linux for example works with interrupts to manage page swapping. The CPU was made to throw an exception (or interrupt) and launch a certain interrupt handler when a page fault occurs (when the CPU tried to execute or read data that isn't in RAM). For x86-32, the interrupt number of a page fault is 0xE (https://wiki.osdev.org/Exceptions). When a page fault occurs, the CPU will look in its IDT for the address of the handler (code present in RAM that will run to manage the page fault). The address of the IDT is stored in a special register called the LIDT.

A page fault can occur when the PT contains a page which has the present bit not set. This means that the page is mapped but not present in RAM at the moment. The page fault handler registered by the OS will thus take the page on the hard-disk and load the page to memory and return.

With virtual addressing, each process is considered to have a full 4GB of virtual address space. One core has only one process running and this process has access to the whole 4GB of virtual address space. The same virtual address can point to 2 different addresses in physical RAM. The OS uses this to map the process space to different positions in RAM so that processes don't interlace each other. If physical RAM is full (which is rare nowadays), the OS will place some pages not currently in use onto the hard-disk. I often installed Linux on computers without swap space. I simply considered that RAM would never be full and thus I would not need it.

As an example, Linux uses ELF files as executable files. Very often, the ELF file's code will be mapped to virtual address 0x400000. Every process' code is mapped to the same virtual address. Thus the OS needs to setup its page tables accordingly and needs to determine what process is going to get what part of the available RAM. It is done so that all processes don't interfere with each other or the kernel.

Processes are swapped according to a timer which raises an interrupt after some time. The timer is programmed to a certain time, counts down to 0, then raises a certain interrupt number. The OS will register a handler to that interrupt number which will call a scheduler which will determine what process goes next and reschedule the timer etc. When processes are swapped all registers are stored onto the process' stack and a pointer to the stack is kept in a structure somewhere (https://en.wikipedia.org/wiki/Context\_switch).
> 2 votes

# Answer
Swapping a process means to move all of its memory onto the hard disk. Paging means to move a single page of memory onto the hard disk. So, the difference is the granularity at which data is moved between main memory and persistent storage (the hard disk). Over time, the term "swap" has been used more broadly and not everyone uses the word "swap" in a way that is consistent with that bright-line distinction.

See https://en.wikipedia.org/wiki/Paging#History and https://en.wikipedia.org/wiki/Paging#Unix\_and\_Unix-like\_systems.
> 1 votes

---
Tags: operating-systems
---


title: Solving $T(n) = 16T(n/2) + n$

text:
# Question
Title: Solving $T(n) = 16T(n/2) + n$
I am trying to solve the following recurrence relation :-

$T(n)=16T(n/2)+n$ using masters theorem. I got $\Theta (n^2)$ (Which matched the first case in the theory) which is wrong, any help with this please?

# Answer
First, let's review the master theorem:

> The following theorem can be used to determine the running time of divide and conquer algorithms. For a given program (algorithm), first we try to find the recurrence relation for the problem. If the recurrence is of the below form then we can directly given the answer without fully solving it. If the recurrence is of the form $T(n) = aT(\frac{n}{b}) + \Theta(n^k\log^p n)$, where $a \geq 1$, $b \> 1$, $k \geq 0$, and $p$ is a real number, then:
>
> 1. If $a \> b^k$, then $T(n) = \Theta(n^{\log\_b a})$.
> 2. If $a = b^k$:
>     * a. If $p \> -1$, then $T(n) = \Theta(n^{\log\_b a} \log^{p+1} n)$.
>     * b. If $p = -1$, then $T(n) = \Theta(n^{\log\_b a} \log\log n)$.
>     * c. If $p \< -1$, then $T(n) = \Theta(n^{\log\_b a})$.
> 3. If $a \< b^k$:
>     * a. If $p \geq 0$, then $T(n) = \Theta(n^k \log^p n)$.
>     * b. If $p \< 0$, then $T(n) = O(n^k)$.

Source : Data Structures and Algorithms Made Easy : Data Structure and Algorithmic Puzzles

In your example, we have

1. $a = 16$
2. $b = 2$
3. $k = 1$
4. $p = 0$

Then, $a = 16$ and $b^k = 2^1 = 2$.

So we have $a \> b^k$, which is case 1.

So our answer is $\Theta(n^{\log\_b a}) = \Theta(n^{\log\_216}) = \Theta(n^4)$.
> 1 votes

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


# Question
Title: Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$
This is my attempt at a proof:

Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$
$L^{+}$ is regular since there is a $REGEX$ $E^{+}$ accepting $L$

I am very unsure if my proof makes sense or is correct. Can someone please advise?

# Answer
In this type of poblems , we usually construct a DFA that recognises the the language under some operation (in your example L+) using the DFA recognising L

So , bearing in mind the construction we use to build a DFA of L\* , can you build a DFA that accepts L+ (please try before viewing the answer )

It is the same construction without adding a new start state

Let M be a DFA recognising L , we add sigma-moves from all of M accept states to the start state

Formally , if δ is the transition function for M , add the following rules to δ :

δ(qa,ε) = q0 ,where q0 is the start state of M , and qa ∈ F is an accept state of M

M now accepts a string in L , then returns to start state , and repeats again till end of string , allowing for concatenations of strings in L

Hopefully you can see that the only difference between this construction and that of L\* is that now we don't just accept ε , we need to have at least one string in L before we can accept
> 0 votes

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


# Question
Title: What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?
How can an NDTM have a growing number of branches as you feed larger and larger inputs with only finite number of transition rules specified--ie what is the relationship between the number of branches and the number of transitions?

An NDTM has a finite number of states, a finite number of input symbols and a finite number of transitions--but presumably the number of branches used grows as you feed larger and larger strings to it--how, mechanically, does this work?

if the number of branches keeps growing as word size grows does this not imply an infinte number of transition rules need be spelled out in the definition of NDTM (since there are an infinte number of word sizes) or do # of transition rules and # of branches not have a one-to-one relationship like this?

# Answer
we can see how the computation tree grows with finite alphabet and rules even when using a DFA , consider the following :

We begin at 1 , then when reading a , we arrive at 1 and 2 , reading another a , 1 arrives at 1 and 2 , 2 arrives at 1 and 2 , so we are at 1,2,1,2 and so on , here is a part of the computation tree :

Hopefully you can see how the computation tree grows exponentially with every symbol , the arrows to the left represent the string read up to this level

Of course the same can be shown for a TM , you can imagine this DFA as a TM , which reads a symbol , writes nothing then goes to right , and you will yield same result

As for a relation , we know that every t(n) time nondeterministic single-tape Turing machine has an equivalent 2O(t(n)) time deterministic single-tape Turing machine.
> 1 votes

---
Tags: complexity-theory, nondeterminism
---


title: proving that a problem is in P

text:
# Question
Title: proving that a problem is in P
I read online that this problem is in P:

> Problem = {a^n, where n is a primary number}

I can't find any algorithm that decides if a word `w` in `{a}*` is in `Problem`, can someone help me because I'm not really convinced that this problem can be solved in polynomial time.

# Answer
> 2 votes
Hint: does being in P have something to do with the length of the input?

# Answer
> 1 votes
This might help you: The AKS primality test is in P.

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


# Question
Title: Lower bound on algorithm solving certain recurrence
I have to find the lower bound of the following recursion:

$A\_1 = C\_1 = p\_1$, $B\_1 = D\_1 = 1-p\_1$, $F\_k = A\_k + B\_k$. Evaluate $F\_n$. \begin{align} A\_{k+1} &= (A\_k + 2C\_k) p\_{k+1} + (1-p\_k) p\_{k+1}, \\ B\_{k+1} &= (B\_k + 2D\_k) (1-p\_{k+1}) + p\_k (1-p\_{k+1}), \\ C\_{k+1} &= C\_k p\_{k+1} + (1-p\_k) p\_{k+1}, \\ D\_{k+1} &= D\_k (1-p\_{k+1}) + p\_k (1-p\_{k+1}). \end{align}

In this case all numbers of the form $p\_i$ are given inputs (there are $n$ of them).

I have to find the lower bound of this algorithm.

Since it's runtime is just $O(n)$ (right?), I know for sure that the maximum possible value of the lower bound is $\Omega(n)$. How would I go about proving/disproving that $\Omega(n)$ truly is the minimum bound and that $\Omega(n-1)$ is not/is attainable?

The only main method I know for proving stuff like this is an Adversary Argument but after a couple hours of thinking, I still haven't been able to come up with an argument to prove what I want.

Any helps/tips/suggestions would be greatly appreciated.

# Answer
> 1 votes
There's quite a lot of confusion here:

1. $\Omega(n)$ and $\Omega(n-1)$ are absolutely the same.
2. You don't an adversary argument to show that this algorithm runs in $\Theta(n)$. It follows immediately from the description of the argument.
3. There is a difference between analyzing the running time of a *particular* algorithm and showing that *every* algorithm that correctly solves a problem must run in at least so many steps.

In order to show that *any* algorithm computing $F\_n$ correctly must run in time $\Omega(n)$, we will show that any such algorithm must read all inputs $p\_1,\ldots,p\_n$. The starting point is the following observation:

> The correct output is different for the instances $p\_1=\cdots=p\_n=0$ and $p\_1=\cdots=p\_{i-1}=0,p\_i=1,p\_{i+1}=\cdots=p\_n=0$.

Given that, we can use a simple adversary argument to show that any algorithm correctly computing the function must read all $p\_j$. Indeed, run the given algorithm, answering $0$ whenever it queries the value of some $p\_j$. If it announces the answer without querying, say, $p\_i$, then it cannot tell apart the two instances above, and in particular, its answer will be wrong on at least one of them.

---
Tags: algorithms, lower-bounds
---


# Question
Title: Is there a graph theory textbook that covers treewidth thoroughly?
Can someone recommend a graph theory textbook that covers treewidth thoroughly?

Something that focuses on the graph-theoretic structure of bounded treewidth graphs rather than solving problems on them. Don't need the strongest/newest results but would prefer something that

Preferably something that covers sublinear treewidth of planar and minor free graphs.

# Answer
I don't know if the thing you are looking for exists, but here are at least some pointers:

*Parameterized Algorithms* by Cygan *et al* (free PDF version) has a chapter dedicated on the topic. This is slightly algorithms oriented, but contains structural stuff too.

*Graph Theory* by Diestel has one chapter, (12. Minors, Trees and WQO) on the subject, about 40 pages. homepage

Bodlaender has a chapter *Treewidth of Graphs* in the Encyclopedia of Algorithms. homepage

Heggernes has a short compendium used for her advanced algorithms class Treewidth, partial $k$-trees, and chordal graphs.

You also have Ton Kloks' book, Treewidth springer, but it's getting rather old. I have not read this one, so I don't know much about it.
> 1 votes

---
Tags: graphs, reference-request, treewidth
---


# Question
Title: Undirected graph whose BFS and DFS trees have roots of degree 2
> Draw a graph on $5$ vertices that satisfies all of the following conditions:
>
> 1. $G$ is an undirected connected graph.
> 2. For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$.
> 3. For every node $v∈V$, in the spanning tree received by DFS($v$), $\deg v=2$.

I was trying to draw many graphs but none of them satisfied all of the conditions.

I was also trying to disprove that such a graph exists, but couldn't find any strong claim that I could use for my proof.

Can you give me a hint?

# Answer
The degree of the root in a BFS tree equals the degree of the vertex in the original graph. Hence condition 2 states that your graph is 2-regular. Since it is connected, it must be a 5-cycle. Running DFS on the 5-cycle results in a path, and in particular, the root has degree 1.

This argument shows that there's nothing special about the number 5: the result remains true for *any* number of vertices.
> 0 votes

---
Tags: graphs, spanning-trees
---


# Question
Title: Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?
I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.

# Answer
> 1 votes
Construct a new graph $G'$ with the same set of vertices, and with an edge $(u,v)$ iff there is a path of length 2 from $u$ to $v$ in the original graph. Then, check whether $G'$ has any cycles of any length. A cycle in $G'$ corresponds to an even-length cycle in the original graph, and vice versa, so this provides a correct algorithm. The running time is $O(|V||E|)$.

# Answer
> 0 votes
if you have no limits to complexity, try this:

For each node **v** in the graph:

1)Apply the bfs from v

2)Take the visit three and for each leaves **u** check to see if there is an edge **(u,v)** in the graphs, if this is true then there is a cycle that hold **v** and you can count it as an *even lenght cycle* if and only if **u** has odd depth

Repeat for each node in the graph and get the number of *even lenght cycle* whit a complexity of O(|V||E|) where V is the set of nodes and E is the set of edge in the graphs.

Hope this help!

# Answer
> 0 votes
Do a BFS from any node, say r, construct the BFS tree.
For each edge ({u, v}) in the graph that isn't a tree edge, check whether `u.level + v.level` is even or odd.
If it's odd then the graph has an even cycle.
If it's even, then the graph has an odd cycle.

Proof:
BFS yields the shortest path between nodes r,u and r,v.
The levels of the BFS tree are equal to the distances from r.
If there is an edge between u and v that isn't a tree edge, then (r-\>v, v-\>u, u-\>r) forms a cycle of the length = 1 + length(r-\>v) + length(r-\>u)
We need to check whether this length is even or not.

Complexity:
O(V + E) + O(E) = O(V + E)

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Recurrence relations and induction: guessing the right bound
I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$ This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-1)+n$$ and $$T(n)=T(\sqrt{n})+1$$ because they were both easier to solve.

Does it makes sense to guess an upper bound for the original recurrence relation (and try to confirm that guess through induction) based on the complexities I obtained for both for these (i.e. use the one with larger order of growth for example)?

If not then what are some ways to find/guess an upper bound for such a relation?

# Answer
> 1 votes
For sure, $T(\sqrt{n})\leq T(n)$, so $T(n)\leq 2T(n-1)+n$, but this produces an exponential upper bound, which is correct but to big to be useful.

Anyway, in this case if we start from the solution of the recurrence $S(n)=S(n-1)+O(n)$, which is $O(n^2)$, we observe that $S(\sqrt{n})=O(n)$, so also the solution of $T(n)=T(\sqrt{n})+T(n-1)+O(n)$ is in $O(n^2)$.

I have to admit that this approach doesn't seem (also to me) very formal, so I've confirmed that guess by explicit calculation. Indeed, suppose $T(n)=an^2+bn+c$, then $T(\sqrt{n})+T(n-1)+n=an^2+(1-a)n+b\sqrt{n}+a-b+c$: we have equality if $a=1$, $b=0$ and $c=-1$, so $T(n)=n^2-1$. Clearly, this is not an exact solution as it depends on the starting point, I mean, it is correct only if $T(1)=0$; in general you have to check that $T(n)=O(n^2)$ (actually, $T(n)=\Theta(n)$) by induction.

---

So, returning to your question: no, you cannot simply split the equation and take the solution with larger order of growth. E.g., consider the recurrence $T(n)=T(n^{3/4})+T(n-1)+n$: if $S(n)=O(n^2)$, then $S(n^{3/4})=n^{3/2}$ is no more a $O(n)$, so we cannot conclude as before. But if you have a recurrence of the form $$T(n)=T(f(n))+T(g(n))+O(h(n))$$ (with reasonable assumption of functions $f,g,h$, I mean, positive, monotone, ...) and the solution of, say, $S(n)=S(g(n))+O(h(n))$ is such that $S(f(n))=O(h(n))$, then you can make the (more than) reasonable assumption that $T(n)=O(S(n))$, and confirm it by induction.

---
Tags: asymptotics, recurrence-relation, big-o-notation
---


title: 3Col reduction Variation, Special edges

text:
# Question
Title: 3Col reduction Variation, Special edges
I have a question concerning NP reduction.

My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding out if the TRI-Graph is 3 coloring is NP-Complete.

I'm not asking for the answer. But I've been racking my brain on how to approach the reduction.

I'm curious to know if you guys have suggestions on which problem I should use to reduce it to my trigraph.

I've tried SAT3, CLIQUE, but those tri-edges make it very hard, maybe I'm going about it the wrong way.

Anyhow, any help would be appreciated. Thanks in advance.

# Answer
You can reduce from $3$-coloring.

Given an instance (graph) $G=(V,E)$ of $3$-coloring, create a tri-graph $G'=(V', E')$ by transforming each edge $e=(u,v) \in E$ to a tri-edge $(u,v,z\_e)$ in $G'$ (where $z\_e$ is a new vertex).

A 3-coloring $c : V' \to \\{1,2,3\\}$ of $G'$ induces a $3$-coloring of $G$: simply color $v \in V$ with color $c(v)$. A 3-coloring $c : V \to \\{1,2,3\\}$ of $G$ can also be transformed into a $3$-coloring of $G'$ by coloring each vertex $z\_e$, where $e=(u,v) \in E$, with the unique color in $\\{1,2,3\\} \setminus \\{c(u), c(v)\\}$.
> 1 votes

---
Tags: graphs, np-complete, reductions, np-hard, p-vs-np
---


# Question
Title: Failing to solve a recurrence by induction
My question is strongly related to the one asked here:

How do I show T(n) = 2T(n-1) + k is O(2^n)?

$$T(n)=2T(n-1)+1$$

Going with the steps, I reached the point where:

$$c\*2^{n}\geq c\*2^{n}+1$$ which implies $$0\geq 1$$ which is false for all possible values of $c$ and thus the claim $T(n)=O(2^{n})$ should be incorrect.

However, most answers to the question just mention that in such case, one should try alternative methods to find/prove the upper bound. I don't understand how should I be able to justify that, is this a scenario in which "induction fails" ? because I've never heard of such one.

# Answer
More interesting than solving the recurrence is to show where exactly your complete induction proof went wrong.

To show a statement S(n) by complete induction you prove manually that S(n) is true for all $n ≤ n\_0$ for some $n\_0$, and then you show that for $n \> n\_0$, if S(n') is true for all n' \< n, then S(n) is also true. That's a quite general form of complete induction; the simplest form is to show that S(0) is true, and if S(n-1) is true then S(n) is also true.

You picked the statement S(n): T(n) ≤ $c \cdot 2^n$. That's true for n = 0 as long as T(0) ≤ c. Unfortunately, S(n-1) doesn't imply S(n): S(n-1) means $T(n-1) ≤ c \cdot 2^n$, so $T(n) = 2T(n-1) + 1 ≤ 2c \cdot 2^{n-1} + 1 = c \cdot 2^n + 1$. And that doesn't prove S(n).

This doesn't mean the statement S(n) is wrong; it just means you failed to prove it. But with complete induction, if you make the induction statement stronger, then you also make the pieces that you can use in your induction proof stronger.

So now we claim S(n): $T(n) ≤ c \cdot 2^n - 1$. That's a stronger statement. It is true for n = 0 if $T(0) ≤ c - 1$ or c ≥ T(0) + 1. And now S(n-1) means $T(n-1) ≤ c \cdot 2^n - 1$, and therefore $T(n) = 2T(n-1) + 1 ≤ 2(c \cdot 2^{n-1} - 1) + 1 = c \cdot 2^n - 1$, which is exactly the statement S(n).
> 1 votes

# Answer
Ok lets try solving this by substitution ,

$T(n) = 2T(n-1) + 1$

from this we know , $T(n-1) = 2T(n-2) + 1$

so $T(n) = 2(2T(n-2) + 1) + 1$

$T(n) = 2^2T(n-2) + 3$

lets substitute one more time

$T(n-2) = 2^2T(n-3) + 1$

$T(n) = 2^2(2T(n-3)+1) + 3$

$T(n) = 2^3 T(n-3) + 7$

Hopefully you can notice the pattern now $T(n) = 2^{k}T(n-k) + 2^{k}-1$

So , for $k = n$

$T(n) = 2^{n}T(n-n) + 2^{n}-1$ , we know that $T(n-n) = T(0) = 1$

$T(n) = 2^{n} + 2^{n}-1$

so clearly , $T(n) = O(2^n)$
> 1 votes

---
Tags: complexity-theory, asymptotics, recurrence-relation, induction
---


# Question
Title: Regular language is closed given transposition of rightmost character to leftmost
It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I've been unable to come up with a generalized 'concept' or 'proof' that shows it's true for all regular languages. Could anyone help me out? It's on occasions like these that I see the value of formal definitions for DFA (instead of just drawings), however it's been a while since I've studied those.

# Answer
> 1 votes
This answer assumes that the transposed language never contains the empty string.

Let $L$ be a regular language, say accepted by a DFA with states $Q$, initial state $q\_0$, accepting states $F$, and transition function $\delta$.

We construct a new DFA with states $Q' = q'\_0 \cup (Q \times \Sigma)$. The initial state of the new DFA is $q'\_0$. The transition function is defined as follows: $\delta'(q'\_0,\sigma) = (q\_0,\sigma)$, and $\delta'((q,\sigma),\tau) = (\delta(q,\tau),\sigma)$. Finally, the set of accepting states $F'$ contains all states $(q,\sigma)$ such that $\delta(q,\sigma) \in F$.

The new DFA reads the first symbol $\sigma$ and remembers it. It then simulates the original DFA, accepting a word if adding $\sigma$ would result in the original DFA accepting it.

# Answer
> 0 votes
Lets try solving this question ,

The basic idea is that we need to remember the first symbol we read $\alpha$ , then we begin our computation from the start state and the second symbol , once we finish we arrive at a state q , if there is a transition from q to an accept state on $\alpha$ we accept

So , we have a DFA M that accepts a language L , we want to construct M' to accept the transposed language L'

In M' we begin in a new start state $q\_0'$

Now for each $\alpha \in \Sigma$ we make a copy of M , name it $M\_\alpha$ , so when we are in $q\_0'$ and we read a symbol $\alpha$ we go to the start state of $M\_\alpha$

Formally , $\delta(q\_0',\alpha) = q\_{0\_{\alpha}}$

Now how is each $M\_\alpha$ different from the original M ?

$M\_\alpha$ is the same as M , all we have to change is the set of accept states , the new accept states are the states who have a transition on $\alpha$ to accept state ,

So let $F\_\alpha$ be the set of accept states for $M\_\alpha$ , if in M a rule exist $\delta(q,\alpha) = q\_{accept}$ , then $q\_\alpha \in F\_\alpha$ (here q in M corresponds to $q\_\alpha$ in $M\_\alpha$ )

The other answer provided earlier is the same idea expressed more formally (sorry to provide another answer when it is the same idea , could not fit all this into a comment !!!)

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


title: Conv Net dimensions misunderstanding?

text:
# Question
Title: Conv Net dimensions misunderstanding?
I was asked this question: Given an image with shape \[1,28,28\], what will be the shape of the output of a convolution layer with 10 5x5 kernels (filters) without padding?

Now, are the shape dimensions \[row, column, depth\]? I really don't understand how you apply a 5x5 kernel on such image, because its 1x28...

What am I missing here?

# Answer
The order of dimensions usually depends on the library you are using

Tensorflow : (Height,Width,Channel) : HWC

PyTorch: (Channel,Height,Width) : CHW

In your case the image seems to go with CHW , since you cant apply 5x5 filters on a 1x128 image

As for the final shape , we follow the rule :

for input length N, and k-size filter , output-length = N-k+1

so each of the 10 filters produces output length = 28-5+1 = 24

so output length = (10,24,24) in the CHW format

Here is a simple Tensorflow code to test it if you want :

```
from tensorflow.keras.layers import Input,Conv2D
x = Input(shape=(28,28,1))
x = Conv2D(filters = 10, kernel_size = 5, padding='valid')(x)
print(x.shape)

```
> 1 votes

# Answer
The image dimensions can either be CHW (Channel, Height, Width) or HWC (Height, Width, Channel). In this case, the image dimensions appear to be CHW, and so you're possibly looking to apply a 5x5 kernel to a 28x28 image.
> 0 votes

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


# Question
Title: Many-one reductions between the set of true sentences and a particular arithmetical set
Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic.

Let TH(N) = {ϕ : ϕ is a first order sentence in the language of arithmetic and N |= ϕ} (Where N is the standard model of arithmetic - , x, \<, +, 0, and the successor; S)

Let γ(x) be some formula with exactly one free variable, namely x. Then assume X = {n : γ(n)} to be the arithmetical subset of the natural numbers defined by γ(x).

My question is: Is there a way to show either of X or TH(N) many one-reduce to each other?

# Answer
> 1 votes
For any such $X$ we have $X\le\_mTh(\mathbb{N})$ but not conversely (and in fact $Th(\mathbb{N})$ is **vastly** more complicated than $X$).

To see that $X\le\_mTh(\mathbb{N})$, we want to translate a question of the form "Is $n\in X$?" into one of the form "Is $\psi\_n$ a true sentence?" for some appropriate sentence $\psi\_n$. Now "$n\in X$" is equivalent to "$\gamma(n)$," and that's **almost** a sentence in the language of arithmetic - the only issue is that "$n$" isn't a symbol in the language of arithmetic (which consists only of $0,1,+,\times,\<$). Do you see a quick way around this?

> Each natural number $n$ has a corresponding **numeral**, usually denoted "$\underline{n}$," which is just an appropriate string of the symbols $0$," "$1$," "$($," and "$)$" (or is the symbol "$0$" if $n$ is $0$): e.g. $\underline{4}$ is the string $((1+1)+1)+1$. Then if we let $\psi\_n=\gamma(\underline{n})$, we have that $\psi\_n\in Th(\mathbb{N})$ iff $n\in X$.

Note that here I'm conflating e.g. the *number* $0$ and the *constant symbol* $0$; this is annoying, but standard.

---

The other direction is a consequence of Tarski's undefinability theorem: just show that anything many-one reducible (or even Turing-reducible) to an arithmetically definable set is itself arithmetically definable. This will show that we never have $Th(\mathbb{N})\le\_mX$ (or even $\le\_TX$) for such an $X$. The key here is to show that the basic notions of computability theory are arithmetically definable:

> Use Kleene's $T$-predicate to talk about computable reductions.

---
Tags: undecidability, arithmetic, incompleteness
---


# Question
Title: Distinguishability given black box access to the distribution
Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie, we are only given a sampling device that can sample from $D$. Consider a sample $z \in \\{0, 1\\}^{n}$, taken from either $D$ or $U$. We want to know which one is the case, and to do that, we consider polynomial-time algorithms that use the sampling device.

Let the best distinguisher algorithm use the black-box sampling device a polynomial number of times (at most) and get samples $z\_{1}, z\_{2}, \ldots, z\_{k}$ from $D$, for some polynomial $k$. My intuition is that, if this best algorithm decides that $z$ indeed came from $D$, then it must be true that $z\_{i} = z$ for at least one $i \in \[k\]$. In other words, since we know nothing about $D$ or its support, we have to "see" $z$ at least once in the samples we collect from $D$ to ascertain that $z$ indeed came from $D$. How do I mathematically formalize this statement?

Also, does this same intuition hold if we are given a polynomial number of samples as input (taken from either $D$ or $U$) instead of just one and are also given access to a black-box sampler for $D$?

# Answer
> 0 votes
You can't. Your intuition is wrong. I will give an explicit counter-example. Actually, I'll give you two: two for the price of one.

Suppose $n=1$, the distribution $D$ always outputs 1, and $U$ is uniform on $\\{0,1\\}$. The following algorithm is an optimal distinguisher:

* Never use the black box. If the input $z$ is 0, guess that it came from $U$, otherwise guess that $z$ came from $D$.

Suppose we run this algorithm on an input $z$ and it guesses that $z$ came from $D$. Then it's not true that $z$ must be equal to one of the queries to the black box; the algorithm didn't make any queries to the black box.

If you're not happy with that, you can obtain another explicit counterexample by considering the following algorithm, with $U$ being the uniform distribution and $D$ a distribution that outputs $1$ with probability $3/4$ and $0$ with probability $1/4$:

* If the input $z$ is 0, get a sample $z\_1$ from the black box, ignore $z\_1$, and guess that $z$ came from $U$.
* Otherwise, get a sample $z\_1$ from the black box, ignore $z\_1$, and guess that $z$ came from $D$.

Notice that if this algorithm guesses that $z$ came from $D$, it is not necessarily true that $z=z\_1$ (it can happen that $z=1$ but $z\_1=0$), so your claim is not true about this algorithm either; yet this algorithm is an optimal distinguisher.

It's often useful to test your intuition on some simple examples.

I suspect what you're missing is that the adversary is assumed to know the distributions $D,U$ in advance and then choose an algorithm based on knowledge of $D,U$ -- a different distinguisher algorithm for each different $D$. There's no requirement to choose a single algorithm that works for all $D,U$.

---
Tags: algorithms, probability-theory
---


# Question
Title: Can someone please help with the proof of this?
Given an unambiguous context-free language L and an unambiguous regular language L (moreover, every regular language is unambiguous) such that L∩ R = ∅, then prove that L∪ R is also unambiguous.

# Answer
Take unambiguous grammars for L and R with start symbols $S\_L$ and $S\_R$. For L union R take a grammar that starts with $S-\>S\_L$, $S-\>S\_R$. Since no string is both in L and R, only one of the initial two rules can succeed, so the grammar is unambiguous.
> 1 votes

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


title: Are assembly languages untyped?

text:
# Question
Title: Are assembly languages untyped?
I'm writing my Bsc thesis about type systems of various languages and I want to have a short section about assembly languages. Initially I thought I'll bring up assembly as a counter example to languages with advanced type systems. My goal was to explore the reasons why assembly omits most (all?) type system features but eventually I found papers about typed assembly languages and I started to get confused. So here are my questions:

* Can we say that assembly is generally untyped? If so, what is the reason we don't have assemblers with advanced types and type checkers?
* Arguments for having a typed assembly language?

Here is a list of papers about typed assembly languages from the end of the last century: http://www.cs.cornell.edu/talc/papers.html. Links to other papers are highly appreciated!

# Answer
> 3 votes
Assembly language is normally untyped, in the sense that there is no type-checking. Adding type-checking is a non-trivial research challenge (hence the papers you see). Papers on typed assembly language should explain the motivation. One application is that they can be used to support proof-carrying code, which can be used to securely execute untrusted code. Another potential application is to support formal verification. But I suggest reading some of the key papers to see what they say about the applications and motivation for typed assembly language.

You can find other papers yourself by doing a literature search -- see https://crypto.stackexchange.com/q/8316/351.

# Answer
> 3 votes
Many assembly languages **do** have certain features that could be considered static typing. Most often this is for making programming easier, rather than type *checking.*

In many assembly languages you can define the equivalent of C's `struct`s and `union`s. Many assembly languages also allow the usage of arrays, where the type (in the sense of byte-count) of the elements is determined at assemble time.

n.b. "x86 assembly" is a very vague term; every assembler has its own dialect. I'll refer to MASM, as it is the most featureful assembler.

It says a lot that MASM has the `TYPEDEF` keyword. It also has the `ASSUME` keyword which marks the value of a register as a pointer to a specific type which will affect later usages of the register. You can also use `LENGTHOF`, `SIZEOF`, and `TYPE` for arrays which return statically-available information.

In MASM, there is a distinction between `near` and `far` addresses and variables can be declared with certain types. Structs can be defined with a particular *alignment* which influences how the fields are accessed. Structs, unions and arrays can be nested. Bitfield types also exist.

ARM assembly is intended to be a compiler target rather than convenient for humans (as far as assemblies go) so it doesn't have any of these features.

**Regarding machine code itself:** Theoretically it is possible for a computer architecture to use extra bits to determine the type of that word. Some old computer architectures did use an extra bit to distinguish data from pointers.

# Answer
> 3 votes
* Can we say that assembly is generally untyped?

If you mean "assembly" as, e.g. x86 assembly language, then I think yes, to some degree. Types are some constraints that we can statically checked/proved, then there is so little (but not nothing) we can do given an x86 assembly program, e.g.

```
add rcx, [@addr]
jmp rcx

```

so it's possible to infer that `[@addr]` is a 64-bit memory values starting from `@addr`, but it's very hard to statically check whether the next `jmp rcx` is safe or not because we must know whether `rcx` is a valid address which contains executable code.

Another example is

```
mov rax, @pointer0
mov rcx, @pointer1
add rax, rcx

```

suppose that `@pointer0` and `@pointer1` are valid pointers, then this program should not type-check because adding two pointers seems meaningless. But x86 assembly allows that.

If we add an "advanced" type system into x86 assembly language, then... it wouldn't be this language anymore (the type system isn't independent from the language).

* Arguments for having a typed assembly language?

Typed assembly language (TAL) means intermediate languages (not adding type system into existing x86 assembly language), its goals is (verbatim from the paper):

> ...to provide a fully automatic way to verify that programs will not violate the primitive abstractions of the language.

that means, given some program (at a high-level language) which has been type-checked to satisfy some properties, then when the program is compiled into another program (in TAL), we can still check (in TAL) that these properties are satisfied.

# Answer
> 0 votes
Machine language is untuned. It's simply numbers which are interpreted as actions by the main and ancillary processors.

The most basic kinds of assembly language follow this. But there is no reason that types can't be used. For example, you could declare a certain set of data as a string. Then the assembler can emit an error when you attempt to do arithmetic on this data.

Undoubtably, types were invented in the higher languages, and have migrated down the language stack as their utility began to be recognised.

# Answer
> 0 votes
JVM byte code can be considered an assembly language, and it is most definitely typed. Classes, interfaces, exceptions are actual parts of that assembly language. Any system that executes JVM byte code will actually include a byte code verifier to check that all the instructions are properly typed.

---
Tags: type-checking, assembly
---


title: Undetectable error correcting codes

text:
# Question
Title: Undetectable error correcting codes
I have a 256 bit string (indistinguishable from random) which I wish to encode into a greater length string using an error correction code.

The result must also be indistinguishable from random. It should not be possible to detect the presence of error correction from the result.

Is it possible? And if so, how?

PS: Related: https://crypto.stackexchange.com/questions/80890/error-correcting-codes-that-are-indistinguishable-from-random

# Answer
One natural approach is to apply the error-correcting code, then encrypt the codeword with a stream cipher (e.g., AES-CTR mode). The recipient can decrypt (this will not increase the number of bits with an error), then decode the code to correct any errors. Anyone who does not know the symmetric key will be unable to distinguish the transmitted ciphertext from a random string.
> 1 votes

# Answer
Encrypting an error-correcting code does not, in general, result in an error-correcting code. So that approach is probably a non-starter.

On top of what everyone else has said, I don't see how error correcting codes can be indistinguishable from randomness for most reasonable definitions of "indistinguishable". The whole point, after all, is that encoded messages are *not* equally likely; uncorrupted messages are more likely than corrupted ones.
> 1 votes

# Answer
What you are asking for: You want transformations T and T’, such that X = T(S) is undistinguishable from random, T’(X) = S, and if X’ = X with few random bit errors, then T’(X’) = S as well.

But strings with errors can be distinguished: If A has no errors, then adding some random bit changes leaves T’(A) unchanged. If A already contains errors, then fewer random bit changes are needed to change T’(A).
> 1 votes

---
Tags: cryptography, error-correcting-codes
---