title: Highest Product of X Items

text:
# Question
Title: Highest Product of X Items
**How do you find the highest product of *X* items?**

This should optimize for runtime complexity and protect from overflows from large products.

* *Inputs*
    1. An array of both positive and negative Ints representing potential products to the solution
    2. An Int representing the number of products required for the solution
* *Output*: An Int representing the highest product of *X* amount of numbers.

For example, for the *highest product of 3 items*, the input is iterated through while updating the following variables. After the iteration has completed in $O(n)$ time, the *highest product of three* variable is returned as the solution.

* Lowest number
* Highest number
* Lowest product of two
* Highest product of two
* Highest product of three

# Answer
Let the integers be $a\_1,a\_2,\dots,a\_n$ sorted in decreasing order of magnitude, so $|a\_1| \ge |a\_2| \ge \cdots$, and suppose you want to find the product of $k$ of them that is as large as possible.

Then:

* If $a\_1 \times \cdots \times a\_k$ is positive, it is the solution.
* Otherwise, if $a\_{k+1}$ is positive, the solution is $a\_1 \times \cdots \times a\_{k+1}$ (but omit $a\_i$ from the product, where $a\_i$ is the largest of the negative numbers in $a\_1,\dots,a\_k$, i.e., closest to zero).
* Otherwise, if $a\_{k+1}$ is negative and at least one of $a\_1,\dots,a\_k$ is positive, the solution is $a\_1 \times \cdots \times a\_{k+1}$ (but omit the smallest positive number of $a\_1,\dots,a\_k$ from the product).
* Otherwise, if at least one of $a\_1,\dots,a\_n$ is positive, the solution is $a\_1 \times \cdots \times a\_{k-1} \times a\_j$ where $a\_j$ is the largest positive number in $a\_1,\dots,a\_n$.
* If all of $a\_1,\dots,a\_n$ are negative and $k$ is odd, then the solution is $a\_{n-k+1} \times \dots \times a\_n$.

This can be computed in $O(n \lg k)$ time using a heap of size $k$.
> 1 votes

# Answer
**Time Complexity**: $O(nlogn)$

**Space Complexity**: $O(n)$

1. Sort the $input$ array.
2. If the last item is positive, find the product for the first $n$ items.
3. If the last item is negative, count how many $negativeItems$ exist up to $n$, and then round the number, $negativeItems$, down to the closest even number.
4. Starting with the smallest negative item, compare it to the largest item at the beginning of the $input$ array. Then compare the next largest negative item with the second-largest item, and so forth until all $negativeItems$ are compared.

4a. Add the original value of the result of whichever number contains the greater absolute value into the $productArray$.

4b. Add the remaining positive items, $n - negativeItems$, to the $productArray$.
5. Calculate the product from the $productArray$.
> 0 votes

---
Tags: greedy-algorithms
---


# Question
Title: Membership in 1, 5, 2, 13, 10, ... (recursively defined sequence)
Find if a given integer is in the series $1, 5, 2, 13, 10, \dots$ in the most efficient way, where the sequence is given by $$ f(n) = \begin{cases} 1 & n=1, \\ 2f(\tfrac{n}{2})+3 & n \text{ even}, \\ 2f(\tfrac{n-1}{2}) & n\>1 \text{ odd}. \end{cases} $$

The series is infinite of course, and $x$ can be a number with at most 9 digits. The idea is not to hardcode this and maybe find some kind of correlation that will allow you to solve this fast. I want to say that I have an idea of how to solve it but I don't.

# Answer
> 0 votes
Your sequence contains all positive integers not divisible by 3. Let us prove this by induction.

Suppose first that $x$ is divisible by 3, and $f(n) = x$. Considering the definition, we see that $x = 2f(n/2) + 3$, and so $f(n/2) = \tfrac{x-3}{2}$, which is also divisible by 3. By induction, this is impossible.

Suppose next that $x\>0$ is not divisible by 3. If $x=1$ then $x$ appears in the sequence since $f(1) = 1$, so we can assume that $x \geq 2$. We now consider two cases: $x$ even and $x$ odd.

If $x$ is even then $\tfrac{x}{2}\<x$ is positive not divisible by 3, and so by induction, $\tfrac{x}{2} = f(m)$ for some $m$. Then $f(2m) = x$.

Similarly, if $x$ is odd then $\tfrac{x-3}{2} \< x$ is not divisible by 3. Furthermore, since $x \geq 5$, it is furthermore positive. By induction, $\tfrac{x-3}{2} = f(m)$ for some $m$. Then $f(2m+1) = x$.

---
Tags: algorithms, recursion
---


title: Does n^(1-1/d) always dominate log^d(n)

text:
# Question
Title: Does n^(1-1/d) always dominate log^d(n)
Hi I am currently learning about orthogonal range search and found two data structures with two different runtimes and wanted to proof that one always dominates the other.

So I found out about k-d-trees with a query time of

$$\mathcal{O}(n^{1-\frac{1}{d}})$$

and range trees with a query time of

$$\mathcal{O}(\log^{d-1}n)$$

and would like to show that

$$\mathcal{O}(\log^{d-1}n) \<\< \mathcal{O}(n^{1-\frac{1}{d}}) \quad \forall d \in \mathbf{N}$$

I tried around on Wolfram Alpha and the solutions were of the form

$$ n \> \exp\left(-d \cdot W\_{-1}\left(\frac{-1}{d}\right)\right) $$

where $W\_k(z)$ is the analytical continuation of the product log function. But I wasn't able to proof this always holds. Thank you in adnvance :)

# Answer
L'Hôpital's rule shows that for $\epsilon \> 0$, $$ \lim\_{n\to\infty} \frac{\log n}{n^\epsilon} = \lim\_{n\to\infty} \frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}} = \lim\_{n\to\infty} \frac{1}{\epsilon n^\epsilon} = 0. $$ In other words, $\log n = o(n^\epsilon)$ for all $\epsilon \> 0$.

This immediately implies that $\log^C n = o(n^\delta)$ for all $C,\delta \> 0$, taking $\epsilon = \delta/C$.
> 1 votes

---
Tags: runtime-analysis, search-algorithms, search-trees, proof-assistants
---


# Question
Title: Show that if $SAT \in P/klog(n)$ then $SAT \in P$
Show that if $SAT \in P/klog(n)$ then $SAT \in P$

Assuming that there is a a constant $k \in \mathbb{N}$ such that $SAT \in P/klog(n)$, I need to prove that $SAT \in P$.

Since $SAT \in P/klog(n)$, then there is a sequence of advices $\\{a\_n\\}\_{n \in \mathbb{N}}$ of length $|a\_n \le klog(n)$ and a turing machine $M$ that runs for at most $n^c$ steps (for some $c \in \mathbb{N}$ such that:

$$\phi \in SAT \Leftrightarrow M(\phi, a\_{|\phi|}) = 1 $$

I tried to show a Turing machine $U$ that runs in a polynomial time and solves $SAT$.

$U$ on an input $\phi$:

1. calculate the size $|\phi|$
2. write $a\_{|\phi|}$ on start of the working tape
3. simulate $ M(\phi, a\_{|\phi|})$ in a way that when $M$ tries to read $a\_{|\phi|}$, it will read it from the start of the working tape, and the working tape of $M$ will start from offset $|a\_{|\phi|}|$.
4. $U$ will return the same answer as $M$

Is my answer correct? It seems like I'm missing something

Help would be appreciated.

# Answer
You need to combine two ideas here:

1. There are only polynomially many possible advice strings.
2. If you can solve the decision version of SAT, then you can solve the search version of SAT.

There is a slight annoyance that you need the search-to-decision reduction to involve only constantly many different input lengths. Assuming for simplicity that you can perform everything using a single input length $n$, here is what you do: you go over all possible advices for length $n$, and for each one, either determine that the SAT instance is unsatisfiable, or attempt to find a satisfying assignment. If you find a satisfying assignment, then the SAT instance is satisfiable, otherwise it isn't.

I'll let you fill in the details.
> 1 votes

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


# Question
Title: What is the definition of Infinitely Often class in complexity
I was reading a paper and I came across the term $L\notin i.o.Dtime(2^{n^c}/n^c)$. What is the meaning of this?

# Answer
$L\in DTIME\left(2^{n^c}/n^c\right)$ if there exists a machine $M$ running in time $O\left(2^{n^c}/n^c\right)$ which correctly decides membership to $L$ for an infinite number of input lengths, i.e. for every $k\in\mathbb{N}$ there exists $n\ge k$ such that $\forall x\in\\{0,1\\}^n : M(x)=\mathbb{1}\_{x\in L}$. You can think of it as having a non trivial special case where we can decide membership to $L$ (where by non trivial I mean an infinite set of inputs, not just very short ones).
> 3 votes

---
Tags: complexity-theory, complexity-classes
---


title: Flow of control when calling a function

text:
# Question
Title: Flow of control when calling a function
I am learning about embedded and operating systems. I would like to know the order of control flow that occurs when a user-space C application calls a function, for example, printf().

I am slightly confused as to which order is correct:

printf() -\> User-space library -\> system call -\> kernel driver

printf() -\> User-space library -\> kernel driver -\> system call

printf() -\> System call -\> user-space library -\> kernel driver

printf() -\> Kernel driver -\> system call -\> user-space library

# Answer
There is no such thing as a C application. Code written in C is compiled to a binary ELF file on Linux or a .exe file on Windows.

The answer to the question is it depends if the function requires a syscall or not. If it doesn't require a syscall (on Linux):

1. You launch the ELF executable
2. The ELF executable is interpreted and the code and data is placed in memory. A new process takes place. All code including the Linux kernel code that the process requires is placed into memory and linked against the user code (dynamic linking).
3. When the process calls a function, its arguments are placed on the stack, the function code runs and the function returns.

It is as simple as that for a situation when the kernel function doesn't require a syscall.

If it requires a syscall:

1. Steps 1 and 2 above.
2. The function is called as usual with its arguments on the stack.
3. When the kernel function requires to access hardware (like when using printf() to print to the screen), it uses system calls.
4. A system call is done using software interrupt 0x80 (the assembly instruction int 0x80).
5. The CPU is interrupted, looks in the IDT (https://wiki.osdev.org/Interrupt\_Descriptor\_Table), determines the address of the handler and jumps to the handler.
6. The interrupt handler for a system call contains a special instruction: SYSENTER (https://wiki.osdev.org/Sysenter). The SYSENTER instruction makes the processor switch from user mode to kernel mode. A special MSR register contains the address at which the processor will jump when executing a SYSENTER instruction. To write to this register, the OS uses the WRMSR special instruction at boot.
7. The CPU jumps to the address specified by the MSR register. It is now in kernel mode. It runs whatever code is needed to perform the requested operation (specified in EAX by the caller). It then returns the result to the caller by using certain registers depending on the system call. To return it calls SYSEXIT.
8. The request was fulfilled, so the user code can continue where it was.

Here is an example of Hello World app in assembly which does a syscall. Your printf() function will be compiled to something similar.

```
section .data
    hello:     db 'Hello world!',10    ; 'Hello world!' plus a linefeed character
    helloLen:  equ $-hello             ; Length of the 'Hello world!' string

section .text
    global _start

_start:
    mov eax,4            ; The system call for write (sys_write)
    mov ebx,1            ; File descriptor 1 - standard output
    mov ecx,hello        ; Put the offset of hello in ecx
    mov edx,helloLen     ; length of the string in edx

    int 80h              ; Call the kernel

    mov eax,1            ; The system call for exit (sys_exit)
    mov ebx,0            ; Exit with return code of 0 (no error)
    int 80h

```

The right answer would be

printf() -\> User-space library -\> system call -\> kernel driver

The printf() function is placed in RAM alongside your code (and dynamically linked against it), the function is called, makes a system call which brings the processor in kernel mode using SYSENTER and then calls kernel drivers which do the required task like writing to the screen or writing to IO devices.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: What is the time complexity of the original Otsu's method?
I'm trying to give a general comparison of the time complexities of various thresholding algorithms. I have not taken an algorithms course yet, so please forgive any misunderstandings.

Otsu's method is performed on $N$ pixels with $L$ number of pixel intensities (e.g. an 8 bit greyscale image would have $L=256$). The algorithm will choose an intensity $k$, and calculate the variance for pixels with intensity less than $k$, and for pixels with intensities greater than $k$.

Calculating the variance involves finding the mean intensity (summing a total of $N$ pixels), then sum the square of the difference between each pixel intensity and the mean mean intensity (again summing a total of $N$ pixels). This is performed for all intensities.

Therefore, would I be correct to say that the average time complexity of the algorithm is $O(LN)$?

# Answer
> 1 votes
The algorithm can certainly be implemented in $O(LN)$ time, as you say.

It is not hard to optimize it to run in $O(N+L^2)$ time. Simply form a histogram of pixel intensities (count of the number of pixels of each intensity). Then you can compute each variance in $O(L)$ time, rather than $O(N)$ time.

You can improve it further to run in $O(N+L)$ time. Suppose we have computed the sum of values below the threshold and sum of squared values below the threshold; and the same for those above the threshold. That is enough to compute the standard deviations. Then, when we bump up the threshold by one, it is possible to update those four sums in $O(1)$ time. As a result, it takes $O(N)$ time to build the histogram, then $O(L)$ time to compute the score for the first threshold, then $O(1)$ time for each subsequent threshold, and there are $L$ candidate thresholds, for a total of $O(N+L)$ time.

In practice the difference between $O(N+L^2)$ vs $O(N+L)$ might be unimportant, as for 8-bit images, $L \le 256$.

---
Tags: time-complexity, algorithm-analysis
---


# Question
Title: An algorithem for finding the number of primes of the form 4k+3 under some n
I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 million) in less than 10 minutes, any ideas?

Iv'e tried using variation's on the Sieve of Eratosthenes and lagranages method but the first was too slow and i didnt manage to have the second count only primes of the form 4k+3.

# Answer
> 2 votes
Here is a simple algorithm in Python that count the primes of the form $4k+3$ that are less than a positive integer $n$. It uses the standard sieve of Eratosthenes.

```
import math

def number_of_primes_4kp3(n):
    is_prime = [True] * n

    for p in range(2, int(math.sqrt(n)) + 1):
        if is_prime[p]:
            for j in range(p * p, n, p):
                is_prime[j] = False

    count = 0
    for i in range(3, n, 4):
        if is_prime[i]:
            count += is_prime[i]

    return count

print("n    ", "number of primes 4k+3")
for i in range(1, 9):
    count = number_of_primes_4kp3(10 ** i)
    print("10**" + str(i), count)

```

It takes about 20 seconds for the Python program above on an old Mac computer of mine to compute `number_of_primes_4kp3(10 ** 8)`, returning `2880950`.

When I use Java instead and only compute `is_prime` for odd numbers (which doubles the performance roughly), it takes less than half a second.

---
Tags: algorithms, time-complexity, number-theory, primes
---


# Question
Title: How to build 4 codewords with a code distance of 5?
I wonder how can I construct 4 (distinct) codewords given the fact that code distance is 5. As far as I know that the code distance is the number of distinct bits between any 2 codewords. How to achieve this code distance for the 6 possible pairs from the 4 codewords available(of any bit length). I named, for example, codewords u, v, w, & x so d(u,v) = d(u,w) = d(u,x) = d(v,w) = d(v,x) = d(w,x) = 5. The code words must be in binary format i.e 00100 10011. I considered a code length of 10 to achieve this but still struggling to find a solution.

# Answer
> 2 votes
```
0000000000
1111100000
0000011111
1111111111

```

---
Tags: information-theory, coding-theory, code-generation
---


# Question
Title: Classification of recursively enumerable sets
It's quite easy to show that there are only three recursive sets up to m-equivalence, namely $\emptyset,\\{1\\},\mathbb N.$ Can we state something "similarly short" for recursively enumerable sets, like there are only 4 recursively enumerable sets up to m-equivalence – $\emptyset,\\{1\\},K,\mathbb N$ (where $K=\\{i\mid\varphi\_i(i)\text{ is def.}\\}$)? More specifically, is every non-recursive recursively enumerable set m-equivalent to $K$?

# Answer
There are **lots** of these. Even with respect to Turing reducibility (which extends $m$-reducibility: if $A\not\ge\_TB$ then $A\not\ge\_mB$), the structure of c.e. sets is extremely rich.

That said, constructing an infinite non-recursive r.e. $A$ with $A\<\_mK$ is significantly easier than constructing one with $A\<\_T K$. The former was done by Post in 1944 who introduced the notions of *creative* and *simple* sets (each of which are necessarily non-recursive), proved that a simple set exists and that $K$ is creative, and proved that no creative set is $m$-reducibile to any simple set; the latter wasn't achieved until a decade later by Friedberg and Muchnik independently, and required a fundamentally new technique (the **priority method**).
> 3 votes

---
Tags: computability
---


# Question
Title: Matrix chain multiplication recurrence and its solution
We want to calculate $A\_1 \times A\_2 \times \cdots \times A\_n$, where $A\_i$ has dimensions $d\_{i-1} \times d\_i$.

In the classical matrix chain multiplication problem, we wish to minimize the total number of scalar multiplications. In this problem, we consider the all intermediate matrices arising in the computation (including the final result but excluding the original matrices), and the cost of a specific order is the maximal number of entries of such an intermediate matrix. As usual, we want to minimize the cost.

As an example, if $n = 2$ the answer is simply $d\_0d\_2$, and if $n = 3$, then there are two orders:

* $(A\_1A\_2)A\_3$, in which the intermediate matrices are $A\_1A\_2,A\_1A\_2A\_3$. The cost is therefore $\max(d\_0d\_2,d\_0d\_3)$.
* $A\_1(A\_2A\_3)$, in which the intermediate matrices are $A\_2A\_3,A\_1A\_2A\_3$. The cost is therefore $\max(d\_1d\_3,d\_0d\_3)$.

Denote by $C\_{ij}$ the optimal cost of multiplying $A\_i,\ldots,A\_j$. We can write the following recurrence for $C\_{ij}$:

$$C\_{ij}=\min\_{i \leq k \<j} \max \\{C\_{i,k},C\_{k+1,j},d\_{i-1}d\_j\\},$$

with base case $C\_{ii} = 0$.

> How do we get this recurrence?

# Answer
> 2 votes
We get the recurrence by considering all possible ways of breaking up $A\_i \times \cdots \times A\_j$.

Specifically, we consider $(A\_i \times \cdots \times A\_k) \times (A\_{k+1} \times \cdots \times A\_j)$ for all relevant values of $k$, which are $i,\ldots,j-1$.

---
Tags: algorithms, data-structures, dynamic-programming, recurrence-relation, matrices
---


# Question
Title: Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?
I want to know whether there is a decision problem, written *EasyProblem*, satisfying the follow property:

* For every valid instance $x$, $x$ is a Yes-instance for *EasyProblem* (if we construct *EasyProblem* as a nature problem). Formally speaking, maybe we can define *EasyProblem* as a language $L \in \mathrm{DTIME}(n)$ or even $L \in \mathrm{DTIME}(1)$.
* The counting version #*EasyProblem* is in #$P$-complete.

Really what I'm asking is: can we construct a very easy decision problem, but its counting version is too hard? Or can we construct a very hard counting poblem, but its decision version is too easy?

# Answer
> 1 votes
An example of a such problem in $\mathrm{DTIME}(n)$ is DNF satisfiability \[1\]. Its counting version is #P-complete \[2\], but its decision version can be solved by simply checking if there is a conjunction that is satisfiable.

For $\mathrm{DTIME}(1)$ I think the answer is that there are no such problems because we can iterate over all computation paths in $O(1)$ so counting is easy.

Note that in general, disallowing instances with answer 0 does not change the #P-completeness of any problem whose decision version is in P because we can check this case in polynomial time.

\[1\] https://en.m.wikipedia.org/wiki/Disjunctive\_normal\_form

\[2\] https://en.m.wikipedia.org/wiki/%E2%99%AFP-complete

---
Tags: decision-problem, turing-completeness, counting
---


# Question
Title: How to know the width/size of a IR (Instruction Register)
I am trying to learn more about the CPU in embedded systems. As I am studying I learned that the IR (Instruction Register) is kind of a special register.

What I would like to know is how to know the width / size of the IR. So, what I mean is for e.g. if I have a 16-bits CPU with 18 address lines (that means max. 256 Kbyte addressable memory). What is the width of the IR of this CPU? In this example the size of opcode are not given. Is it important to know how many opcodes there are. But if it does matter the size of opcodes is maximum 1 byte.

Could someone give me some insight of how this works.

Thank you.

# Answer
In a typical scalar in-order issue microcontroller, the instruction register holds however many bits are needed to control the data path.

Modern microcontrollers are typically Harvard architectures, with program memory stored in flash, with a modest amount of data/read-write memory on-chip. This means that, unlike traditional scalar CPUs, the bus width of program memory and the bus width of data memory does not have to be the same.

Microcontroller instruction sets are typically designed so that the instruction as a whole can be understood from the first word fetched from flash. Any additional words contain data only, and hence do not need to participate in instruction decoding.

As an example, here is the AVR block diagram from a data sheet that I picked at random:

The instruction register holds whatever comes out of program memory. Since AVR has 16-bit instructions, we would expect it to be a 16-bit register.

Now consider the PIC instruction set. Different models have different instruction sizes, anything from 12 bit to 16 bit. Modern microcontrollers can handle this just fine because, as noted earlier, instruction memory can have a different word size from data memory. This instruction word contains all of the information needed to understand what the instruction needs to do, so this is the size of the instruction register.

A mid-range core PIC has a 14-bit instruction word, so it will almost certainly have a 14-bit instruction register. And if you look at a data sheet, this turns out to be correct, and is even labelled on the diagram:

So in summary: On a typical modern microcontroller, the IR size is one word of program memory, and the instruction encoding is carefully designed so that this word contains all the information that instruction decoding needs.
> 1 votes

---
Tags: cpu
---


# Question
Title: Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly?
Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly? The definition of random for our purpose is anything that's random enough to be thought as being random by the general population. I am thinking it is true, but I wouldn't be able to say the exact reason why it would be the case.

# Answer
> 1 votes
In principle yes, but in practice probably not; both of them are likely to be extremely fast.

You can randomly choose between two numbers by generating a random bit. That is extremely fast in practice.

You can't "pick almost any number randomly". Instead, all you can do is sample from a distribution. The time it takes to sample from a distribution depends on the specific distribution you have in mind. However, for most cases commonly encountered, this too is very fast. For instance, if you want to pick uniformly at random an integer from a particular range, that can be done in a standard way by generating some random bits and then using them to select an integer; it will be very fast in practice.

So, while picking between two numbers might be quicker, both operations are likely to be so fast that it's not clear it is worth worrying too much about which is faster.

If you want to understand why this is the case, I suggest you study algorithms for picking a random number and for sampling from various distributions; that will give you a concrete understanding.

---
Tags: algorithms, randomness
---


# Question
Title: What is the duality between path cover and flow?
Let there be a bipartite directed graph $G=(V,E)$.

Let's say we have a path cover of the graph. In some texts it is said that this path cover "induces" a flow on $G$. What does this mean?

How can we extract a flow from a path cover (and similarly, extract a path cover from a flow)?

# Answer
Presumably, the flow would send $k$ units of flow along the edge $(u,v)$, where $k$ is the number of paths in the path cover that traverse that edge.

I haven't verified that this will always be guaranteed to be a valid flow for all possible path covers, but it doesn't seem like it on first glance, so more context might be needed to resolve that.
> 1 votes

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


# Question
Title: Doing induction on recurrences correctly
I have $$T(n)=T(n-1)+n^{2}$$ And I know, by drawing the recursion tree that this is $\Theta (n^{3})$ However, if I try claiming that it's $O(n^{2})$ through induction: $$T(n)\le c(n-1)^{2}+n^{2}\le cn^{2}$$ which evaluates to $$c\ge \frac{n^2}{2n-1}$$ Which makes $c\>0$ for all $n\>1$ and concludes that the recurrence is $O(n^{2})$ which is not correct. So what am I missing?

# Answer
The error is that $c(n-1)^2 + n^2 = cn^2 - 2cn + c +n^2 \leq (c+1)n^2$, so the constant $c$ is in fact no constant, since it grows with every step.

So you get that when $n$ increases by 1, $c$ also does, so you have $O(n) \cdot n^2$, so $O(n^3)$.
> 2 votes

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


title: N-gram language model question

text:
# Question
Title: N-gram language model question
I have this question I found regarding n-gram modelling in the textbook *Speech and Language Processing*:

> Suppose we didn't use the end symbol \</s\>. Train an unsmoothed bigram grammar on the following corpus without using the end-symbol \</s\>.
>
> > \<s\> a b
> > \<s\> b b
> > \<s\> b a
> > \<s\> a a
>
> Demonstrate that your bigram model does not assign a single probability distribution across all sentence lengths by showing that the sum of the probability of the four possible 2 word sentences over the alphabet {a, b} is 1.0 and the sum of the probability of all possible 3 word sentences over the alphabet {a, b} is also 1.0.
> *Note:*
> \<s\> means beginning of sentence.
> \</s\> means end of sentence.
>
> *Speech and Language Processing*, Daniel Jarafsky and James H. Martin, 3rd ed., Exercise 3.5, p.55

My attempt was:

```
Two word sentences:
P(a | b) = count(b a) / count(b) = 1 / 4
P(b | a) = count(a b) / count(a) = 1 / 4
P(a | a) = count(a a) / count(a) = 1 / 4
P(b | b) = count(b b) / count(b) = 1 / 4

```

sum = 1

but when I get to 3 word sentences:

P(a | a, a) = count(a a a) / count(a) = 1 / 64

Now, you get 8 three word sentences which sums to 8 / 64

This is where I am getting lost. I need some pointing in the right direction.

# Answer
For these 2-word sentences, notice that the original equation for the MLE approximation of the probabilities of the bigram is:

$$P(w\_i|w\_{i-1}) = \frac{C(w\_{i-1}w\_i)}{\sum\_w{C(w\_{i-1}w)}} = \frac{C(w\_{i-1}w\_i)}{C(w\_{i-1})}, $$

where the denominator $C(w\_{i-1})$ only equals the count of $w\_{i-1}$ iff there is an end-symbol $\text{\</s\>}$, otherwise the number of times $w\_{i-1}$ appears at the end of the sentence has to be subtracted from its count. Therefore, the "count" function you are using in the denominator is wrong, and the true probabilities in your particular corpus are:

$$\begin{equation} \begin{split} P(a|a) &= \frac{C(aa)}{C(a)} &= \frac{1}{2} \\ P(b|a) &= \frac{C(ab)}{C(a)} &= \frac{1}{2} \\ P(a|b) &= \frac{C(ba)}{C(b)} &= \frac{1}{2} \\ P(b|b) &= \frac{C(bb)}{C(b)} &= \frac{1}{2} \\ P(a|\text{\<s\>}) &= \frac{C(\text{\<s\>}a)}{C(\text{\<s\>})} = \frac{2}{4} &= \frac{1}{2} \\ P(b|\text{\<s\>}) &= \frac{C(\text{\<s\>}b)}{C(\text{\<s\>})} = \frac{2}{4} &= \frac{1}{2} \\ \end{split} \end{equation}$$

and now the sum of the probabilities of all possible 2-word sentences with this vocabulary becomes equal to 1:

$$\sum\_{w, v\in\\{a, b\\}^2}P(\text{\<s\>}wv) = \sum\_{w, v\in\\{a, b\\}^2} P(w|\text{\<s\>})\cdot P(v|w) = \sum\_{w, v\in\\{a, b\\}^2} \frac{1}{4} = 1 .$$
> 1 votes

# Answer
in the Trigram model:

$P(w\_k|w\_1, . . . ,w\_{k−1}) =P(w\_k|w\_{k−2},w\_{k−1})$

hence, the Probability of sentence $w\_1....w\_N$ is as follows:

$ \prod\_{k=1}^N {P(w\_k|w\_{k−2}w\_{k−1})} $

and $P(w\_3|w\_2,w\_1) = \cfrac{count(w\_3,w\_2,w\_1)}{count(w\_2,w\_1)}$

in words: you must divide $count(w\_3,w\_2,w\_1)$ by the number of times $(w\_2,w\_1)$ appeared one after the other, and not separately. Then it should sum to $1$.
> 0 votes

# Answer
I m not sure, but I think this will help you. Here we use the tri-gram model, because the bi-gram model is not used for 3 words, and the answer is not the same as the bi-gram model for this corpus. $$P(a|a,b) = 0/1 = 0$$ $$P(b|b,a) = 0/1 =0$$

Similarly, all combinations of $\\{a,b\\}$ have a zero answer.
> 0 votes

---
Tags: natural-language-processing
---


# Question
Title: Shortest subsequence containing all elements
> Given a sequence $a\_1,\ldots,a\_n$, find the shortest subsequence $a\_i,\ldots,a\_j$ such that $\\{a\_1,\ldots,a\_n\\} = \\{a\_i,\ldots,a\_j\\}$.

I came up with three solutions:

The most straightforward brute-force solution is $O(n^3)$.

We can optimizing brute-force solution, performing a binary search on subsequence length in the outermost loop in $O(n^2 \log n)$.

We can re-use idea from longest common subsequence problem by putting tree-based sets in the table (let's say, elements are comparable with $\<$) with copy-on-write implementation. This would be $O(n^2 \log m)$, where $m$ is the number of different elements.

Could it be done better? Maybe, something like Z-functions for all different values in $O(nm)$?

# Answer
Start by computing the set of all elements in the input sequence. This takes time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ using a hash table.

Suppose there are $m$ such elements $x\_1,\ldots,x\_m$. Initialize a histogram $H$ of length $m$ with zeroes, and a counter $C$ to $m$. Go over the elements in the sequence from left to right. When processing $a\_i$, update $H\[a\_i\] \gets H\[a\_i\] + 1$ (the indexing operation takes time $O(\log n)$ if we are only allowed comparisons, and $O(1)$ using a hash table), decreasing $C$ if $H\[a\_i\]$ were zero. Stop once $C = 0$. If we stopped at $a\_j$, then this means that $a\_1,\ldots,a\_j$ is the shortest subsequence containing all elements and starting at $a\_1$.

Now update $H\[a\_1\] \gets H\[a\_1\] - 1$. If after the update $H\[a\_i\] \> 0$, then $a\_2,\ldots,a\_j$ is the shortest subsequence containing all elements and starting at $a\_2$. Otherwise, continue scanning the sequence, updating $H$ as before, until $H\[a\_1\] \> 0$. If we stopped at $a\_j$, that $a\_2,\ldots,a\_j$ is the shortest subsequence containing all elements and starting at $a\_2$.

In this way we can find the lengths of all shortest subsequences containing all elements and starting at $a\_i$, for each $i$. We output the length of the shortest one. The entire algorithm runs in time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ otherwise.

In the latter case, $O(n)$ is optimal, as a simple adversary argument shows (whenever the algorithm accesses an element, answer $1$; even after accessing all but one element, the algorithm cannot tell whether the correct answer is $1$ or $2$).

If we are only allowed comparisons, then we can get an $\Omega(n\log n)$ lower bound from Element Distinctness. Suppose that we could solve our problem using $T(n)$ comparisons. Given a sequence $a\_1,\ldots,a\_n$, consider the sequence $a\_1,\ldots,a\_n,a\_1,\ldots,a\_n$. If all elements are distinct, the shortest subsequence containing all elements has length $n$. Otherwise, if $a\_i = a\_j$ for $i \< j$ then the subsequence $a\_{i+1},\ldots,a\_n,a\_1,\ldots,a\_{i-1}$ contains all elements and has length $n-1$. This shows that we can solve Element Distinctness in time $T(2n)$. The well-known lower bound $\Omega(n\log n)$ on Element Distinctness implies that $T(2n) = \Omega(n\log n)$, and so our algorithm is optimal. (Formally speaking, we also need to handle odd input lengths. We can do this by adding a fresh element between the two copies of the original sequence.)

Credit for the algorithm: https://www.glassdoor.com/Interview/Find-shortest-substring-in-a-string-that-contains-all-of-a-set-of-characters-QTN\_66124.htm
> 6 votes

---
Tags: algorithms, subsequences
---


title: NP-hardness language

text:
# Question
Title: NP-hardness language
How to prove that language $L = \\{G \\; | \\; \omega(G) \geq \frac{9}{10}\cdot n\\}$, where $n$ \- number of vertices in the graph, NP-hard?

$\omega$ \- is a clique number.

# Answer
> 2 votes
Consider the following reduction from the NP-complete problem $Clique = \\{ \langle G, k\rangle \ : \text{G is undirected Graph that has a clique of size at least k}\\}$ to $L$. The reduction operates as follows.

Given input $\langle G = (V, E), k \rangle\in Clique$:

1. If $k \< \frac{9\cdot|V|}{10}$, output $G' = G \cup K\_{t}$, where $t= 9\cdot |V| -10k$, and $K\_t$ is the complete graph over $t$ vertices. In addition, add edges that connect every vertex in $K\_{t}$ with every vertex in $G$.
2. Othwerwise, if $k \geq \frac{9\cdot|V|}{10}$, output $G'$ that is defined as follows. $G'$ is obtained by replacing each vertex of $v \in V$ by a clique of size 9, denoted $c\_9(v)$, and then for every edge $\\{ u, v\\}\in E$, the two cliques $c\_9(v), c\_9(u)$ in $G'$ are connected, that is, every vertex of $c\_9(v)$ is connected by an edge with every vertex of $c\_9(u)$. Also, add to $G'$ new $t$ isolated vertices, where $t= 10k - 9|V|$.

Correctness:

1. If $k \< \frac{9\cdot|V|}{10}$, then note that $t = 9\cdot |V| - 10k \> 0$, and so the output of the reduction $G'$ is well-defined. Now if $G$ has a clique $C$ of size at least $k$, then $G'$ has a clique of size at least $k+t$ (verify that $C\cup \\{ v: \text{$v$ is a vertex in $K\_t$}\\}$ is a clique of $G'$). Conversely, if $G'$ has a clique of $C'$ of size at least $k + t$, then the set $C = C' \setminus \\{ v: v \text{ is a vertex of $K\_t$} \\}$ is a clique of $G$. Indeed, the reduction does not add new edges between the vertices of $G$. Also note that $C$ is of size $|C| \geq |C'| - | \\{ v: v \text{ is a vertex of $K\_t$} \\}| = |C'| - t \geq k+t - t = k$ in $G$. All in all, we have that $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+t$. Finally, note that $\frac{k+t}{|G'|} = \frac{k+t}{|V|+t} = \frac{k + 9|V| - 10k}{|V| + 9|V| - 10k} = \frac{9|V| - 9k}{10|V|-10k} = \frac{9}{10}$. So, $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+t = \frac{9}{10} |G'|$.
2. If $k \geq\frac{9\cdot|V|}{10}$, then note that $10k - 9|V| \geq 0$, and so the output of the reduction $G'$ is well-defined. For the first direction, if $G$ has a clique $C$ of size at least $k$, then $G'$ has a clique $C'$ of size at least $9k$. Indeed, we can take $C' = \bigcup\_{v\in C} c\_9(v)$, that is, $C'$ consists of the 9-cliques corresponding to the vertices in $C$ (verify that $C'$ is indeed a clique of size at least $9k$ in $G'$). The following holds $\frac{|C'|}{|G'|} \geq \frac{9k}{|G'|} = \frac{9k}{9|V|+t} = \frac{9k}{9|V| +10k-9|V| } = \frac{9}{10}$. So $G'$ has a clique of size at least $\frac{9|G'|}{10}$. Conversely, assume that $G'$ has a clique $C'$ of size at least $\frac{9|G'|}{10} = \frac{9\cdot (9|V| + t)}{10} = \frac{9\cdot(9|V| + 10k - 9|V|)}{10} = \frac{9\cdot 10k}{10} = 9k$. Clearly, none of the added isolated vertices are in $C'$, and thus $C'$ consists of vertices $p$ such that $p\in c\_9(v)$ for some $v\in V$. In words, $C'$ consists of vertices $p$ such that $p$ belongs to one of the 9-cliques of $G'$. Note that there could be two vertices $p\_1, p\_2\in C'$ such that both $p\_1$ and $p\_2$ are in $c\_9(v)$ for some $v\in V$ (that is, $C'$ can have vertices that correspond to the same 9-clique). Now consider the following set $C =\\{ v\in V: \text{ there is $p\in C'$ such that $p\in c\_9(v)$} \\}$. We claim that $C$ is a clique of size at least $k$ in $G$, and thus we're done. To begin with, $|C|\geq k$ because for every $v\in C$ there are at most 9 $p$'s such that $p\in c\_9(v)$ and $p\in C'$, and those 9 $p$'s correspond only to the vertex $v$ in $C$. So in the worst case, $C'$ consists of whole 9-cliques and we replace every 9-clique $c\_9(v)$ with $v$ to get the set $C$. So, as $|C'|\geq 9k$, then $|C|\geq k$. Now to show that $C$ is a clique in $G$, let $v\_1, v\_2$ be two vertices in $C$. We need to show that $\\{u, v \\}\in E$. By definition of $C$, there are $p\_1, p\_2 \in C'$ such that $p\_1\in c\_9(v\_1)$ and $p\_2\in c\_9(v\_2)$. Since $C'$ is a clique of $G'$, we know that $\\{p\_1, p\_2 \\}$ is an edge of $G'$, and by definition of $G'$ this can happen only when $\\{v\_1, v\_2 \\} \in E$ (indeed, vertices of different 9-cliques are connected in $G'$ when the vertices defining the 9-cliques are connected in G).

# Answer
> 0 votes
It depends on what other problems you already know to be NP-hard and whether you use Karp or Turing reductions.

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


title: What is a certificate in plain english?

text:
# Question
Title: What is a certificate in plain english?
I've got this question from a course:

> Show how to efficiently find a certificate for each of the following problems assuming that the decision problem is efficiently solvable.

And it seems like this has been poorly explained and I am getting conflicting answers on how to answer. For explanation purposes I will consider my problem to be `f(x)` where given a truthy value for `x` `f(x)` will output `1` and the opposite for falsey values.

In plain English, a certificate is a variable `x` such that the verifier for a problem can output `1` or `0`. In the case of `f`, a certificate would be `x=1` or `x=0` or similar.

Is this correct?

The problems are made of a few parts:

* The problem, given x can we do y.
* A certificate, an x.
* A verifier, given y is it an actual answer for x.

# Answer
For example, the compositeness problem, "given an integer $X$, is it composite?" might have a certificate $n\_1, n\_2$ where $X=n\_1n\_2$. This certificate would be checkable in time polynomial in the length of the certificate.
> 1 votes

# Answer
You need an algorithm so that if you have a problem p(x), and a certificate c(x), then your algorithm can either tell correctly what the answer to p(x) is, or determine that the certificate is not valid.

For example, if the problem p(x) is "find a non-trivial factor of x", which may be hard to do, then any factor of x is a valid certificate (you just try dividing x by the factor, and if there is no remainder then you have a non-trivial factor of x, and if there is a remainder then you know you have an invalid certificate).

Your example c(x)=1 or c(x)=0 is not a certificate. If I give you one of these, then you still have to solve the problem yourself, because otherwise you don't know whether the certificate was valid or invalid.
> 1 votes

---
Tags: complexity-theory, np
---


title: Proof of the Bubblesort algorithm

text:
# Question
Title: Proof of the Bubblesort algorithm
I'm studying *The Algorithm Design Manual* and I was having some difficulty in the proof exercises, so I asked a question here. Based on the answer I got in that question(which was not the a complete proof),I came up with a proof.

```
Prove the correctness of the following sorting algorithm.
    Bubblesort (A)
        for i from n to 1
            for j from 1 to i − 1
                if (A[j] > A[j + 1])
                    swap the values of A[j] and A[j + 1]

```

```
1.Base case:
    An array of length 1 which is by definition sorted.

2.Inductive hypothesis:
    We'll assume that for all arrays of length (0 <= m) one iteraion of the outer loop with "n" being the length of the array,
    the array gets permutated in such a was  that the last element in the array is the biggest.

3.Inductive step:
    We want to prove that if our assumption is true for lists of length (0 <= m), then it is also true for lists of length (m)

    Let A = a[0], a[1], ..., a[m] (of length m+1)
    After (m-1) iterations of the inner loop based on our assumption, in the list A[0:m-1], a[m-1] is the biggest element.
    At this point,as (j < m),we have one more iteration to perform.
    Before this, j was equal to m-2 and j+1 was equal to m-1. After this loop, j will be equal to m-1 and j+1 will be equal to m.
    If A[m-1] and A[m] satisfy the if statement, that is, A[m-1] > A[m], they will swap.If not, then that would mean that A[m] is
    the biggest element in the list.
    In either case, the last element of the list will be the biggest after one iteration of the outer loop, which was what we were
    trying to prove.  ▮

```

I'm not really sure of it's correctness,so I would really appreciate if you could review it and tell me whether its correct or not. Also please note any inadequacies it may have or things I could've done better as I'm quite new to inductive proofs.

# Answer
Your induction hypothesis is insufficient. In the hypothesis, you are just proving that the last element of the array has the maximum value. However, you have to prove that the resulting array is sorted. Therefore, your induction hypothesis should be the following:

**Hypothesis**: At the end of 't' iterations of the outer "for" loop, the "n-t" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t+1' to 'n'.

**Base case**: For 't = 1', the induction hypothesis says that at the end of the first iteration of the outer "for" loop, the algorithm gives the highest element at the index 'n'. And, you can easily prove this statement.

**Induction Step**: At the end of 't+1' iterations of the outer "for" loop, the "n-t+1" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t' to 'n'. Again, you have to prove this step using the earlier mentioned hypothesis -- for 't' iterations.

This proves the induction hypothesis. And, now you can simply say that at the end of 'n' iterations of the outer "for" loop, all elements of the array are in the sorted order and they occupy the indexes from '1' to 'n'.
> 1 votes

---
Tags: algorithms
---


title: Prove $|d_{s}(u)-d_{s}(v)|\leq1$ in BFS

text:
# Question
Title: Prove $|d_{s}(u)-d_{s}(v)|\leq1$ in BFS
Trying to prove the following problem:

> Given a graph $G=(V,E)$ and vertex $s\in V$, prove that: $\forall (u,v)\in E,\ |d\_{s}(u)-d\_{s}(v)|\leq1$ where $d\_s(v)$ is the shortest path from $s$ to $v$ in BFS.

What I did: Let assume that it's isn't true, meaning there is $(u,v)\in E$ so $|d\_{s}(u)-d\_{s}(v)|\>1$. Lets run BFS on graph $G$. If in BFS process there is edge $(u,v)$, this means that $d\_{s}(u)+1=d\_{s}(v)$ so $|d\_{s}(u)-d\_{s}(v)|=1$ which contradicts $|d\_{s}(u)-d\_{s}(v)|\>1$. This means that there is at least one edge $w\in V$, in the path from $u$ to $v$.

Now I'm stuck. I don't come empty handed, I have the following theorems:

1. Given graph $G=(V,E)$ and vertex $s\in V$, for each edge $(u,v)\in E$ we have $\delta\left(s,v\right)\leq\delta\left(s,u\right)+1$ where $\delta(s,v)$ is the shortest path between $s$ and $v$ (or $\infty$ if no such path) in graph $G$ (note the difference between $\delta$ which on $G$ and $d$ which on BFS).
2. For each vertex $v\in V$ we get $d(v)=\delta(s,v)$ in BFS.

I think I might need to use those two theorems here but I don't see it. My problem is that there is **at least one** vertex $w$ and not exactly one. How can I prove it?

# Answer
First of all your question is quite confusing:

> There is at least one edge $w \in V$

Is it an edge or a vertex?

Maybe it would be easier for you to look at some edge $(u,v) \in E$ and think about the moment in time $\tau$, when the BFS algorithm reached either $u$ or $v$ for the first time (it could reach them both at the same time).
> 1 votes

---
Tags: algorithms, graphs, breadth-first-search
---


# Question
Title: Programming languages and Model of computations
I am learning about model of computation and I found this wikipedia entry that categorises and outlines various model of computation.

Now I want to know the programming languages that builds on these models.

I am aware that functional programming languages are built upon lambda calculus, and that imperative programming is more or less as a result of Turing machine model. But I do not know about the other models and if any programming language have been designed based on them.

Anyone knows if there are languages that builds on model of computation listed on the wikipedia entry?

# Answer
Functional programming languages can often be thought of as built on the lambda calculus.

Imperative programming languages can often be thought of as built on the RAM (Random Access Machine) model of computation.

Some hardware description languages can be thought of as being built on the finite-state machine model, or on digital circuits.

Some declarative languages can be thought of as built on Datalog.

Some concurrent languages can be thought of as built on the actor model or on process calculi (e.g., CSP, the $\pi$-calculus, etc.).
> 1 votes

---
Tags: computation-models
---


# Question
Title: "If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable."
This is given vertabim in my lecture slides and it seems like I'm having difficulty proving this statement mathematically. I know that P is a subset of NP and NP-Complete is also a subset of NP. But what else do we have to prove for this statement?

# Answer
Assume that the following were true:

> A problem $X$ in NP is proven to not to be able to be solved in polynomial time.
>
> A NP-complete problem $Y$ is proven to be solved in polynomial time with algorithm $Z$.

However, since $Y$ is a NP-complete problem we can transform an instance $x$ of $X$ into an equivalent instance $y$ of $Y$ in polynomial time, and then solve it with $Z$ in polynomial time. The sum of two polynomial times is polynomial, thus our assumption is violated.
> 2 votes

---
Tags: computability, np-complete, theory
---


# Question
Title: Turing-completeness, Conway's Game of Life and Logical Gates
I was recently given an assignment at university asking me to discuss the **universal** computational capability of Conway's **Game of Life**.

I'm not required to actually build up a Universal Turing machine in Life, but rather I'm supposed to provide a step-by-step explanation of universality of GoL (as well as the meaning of such result).

I decided to follow this path:

1. Introduce Turing machines, the notion of universality, and Universal Turing machines.
2. Introduce the notion of Turing-completeness and its relation with computational universality.
3. Using such notions and based on previous works and papers, show how Life can be used to simulate a Universal Turing machine.

(Is it a correct reasoning?)

The last point of the assignment asked me to prove the universality of Life by providing an **implementation of logical gates** in such model, and here come my doubts. I have read dozen of times in StackExchange forums, papers, etc. that the necessary conditions for a system to be Turing-complete are:

1. A form of conditional repetition or conditional jump (while, for, if and goto)
2. A way to read and write to some storage mechanism

But I never read anywhere about logical gates (or logical propositions in general). So, my questions are:

1. Is the capability of implementing logical gates (i.e. evaluate any arbitrary logical function) another requirement? Or, is it an **alternative** requirement?
2. Which is the correlation between Turing-completeness and logical gates?

Thank you in advance!

**EDIT**

Here is a link to the pdf file of the report that I submitted, thanks for your suggestions!

# Answer
1. A form of conditional repetition or conditional jump (while, for, if and goto)
2. A way to read and write to some storage mechanism

The computer you typed this message onto is Turing Complete (well, sort of), yet the only tool it uses is logic gates. I can give you a simple(ish) example of each:

For the first requirement, processors can use multiplexers to create conditional jump options. Multiplexers are basically just a bunch of AND gates.

Number 2 is a bit more complex. Computer memory consists of logic gates that feed back into themselves. If you study memory, you begin by studying latches and flip-flops. Here is a simple latch that stores which of the two input lines on the left turned on most recently:

Thus, it stands to reason that, if you can imitate logical gates, you can create a Turing-Complete machine just as you would if you could simulate a Turing Machine. So, it may be that you don't need to show how to simulate a TM in GoL nodes, but instead take a step to show that logical gates are sufficient to be Turing Complete.

I have one further thought for you that might make your life simpler. You don't need every gate. NAND and NOR are each sufficient, *on their own*, to create every other logic gate. You can easily do a search like "nand logical completeness" to find the logic gate diagrams to show this.
> 5 votes

# Answer
I think that your plan is good, but the most important is for it to be **intuitive for you** ! If you don't feel secure with it, just change it !

Then, for GOL, I made multiple lectures, but as I'm French, I don't think you would like to see them... My habitual plan in order to present it is :

1. It's a simulation (kind of a game, but a no-player game)
2. It works with... (an infinite grid, some cells with 2 states, and then some rules)
3. the rules
4. beautiful examples (like *cambrian explosion* in golly)

After that, if you want to speak about the TM from the angle of T-completeness, I suggest you to also just show a bit of $\lambda$-calculus (or at least to speak about Church, for the Church-Turing Thesis), gif you have the time for that.

For your question :

> Is the capability of implementing logical gates (i.e. evaluate any arbitrary logical function) another requirement? Or, is it an alternative requirement?

If you spoke about $\lambda$-calculus, you will have said that it is equivalent to TM. As you said, logic gates allows to compute any function, including all the possible $\lambda$-functions. You're done.

If you really want to use TM to prove the T-completeness of GOL, you could say that the TM's transition table could simply be a set of logic gates, that takes the actual state etc... and output the new one, that the memory tape could also be a memory made out of logic gates, and finally that the read/write head could be something like a multiplexer and a binary counter, that allows to select a cell and to operate on it, and then to change the cell, to operate again etc...
> 1 votes

---
Tags: turing-machines, logic, turing-completeness, cellular-automata
---


# Question
Title: permutations sampling by probability matrix
I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum\_{i}p\_{i,j} = \sum\_{j}p\_{i,j} = 1$, $i,j = 1,2,...,n$).

Probability matrix elements $p\_{i,j}$ define probability of $i = \pi(j)$ and $0 \<= p\_{ij} \<= 1$.

The sampled permutations should correspond to the defined probability matrix $P$ and probability of each permutation should correspond to the following permutation probability

$$p(\pi)=\frac{\prod\_{i} p\_{i,\pi(i)}}{\sum\_{all \pi}\prod\_{j} p\_{j,\pi(j)}}=\frac{\prod\_{i} p\_{i,\pi(i)}}{perm(P)}$$

Example: Probability distribution matrix

$$ P = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 \end{array} \right) $$

produce only two permutations $\pi\_1 = (2 1 3)$ and $\pi\_2 =(2 3 1)$ with the same probability $p(\pi\_1) = p(\pi\_2) =1/2$

This question is a follow-up to Random permutations by probability matrix

I tried a few variations of node histogram based sampling algorithm (NHBSA) by Shigeyoshi Tsutsui. This method is used as a main tool on permutation optimization problems. But the results are not very promising. So, I ask this question here, to learn what is current state of art on this topic.

I tried to test a few algorithms, but all these methods produce permutations with more or less distorted probability matrix even for small n (3 \<= n \<= 10 ). This is the reason why I am asking for help.

> Some comments here states that interpretation of matrix $P$ and permutations probability $p(\pi)$ are not clear enough to define unique permutations distribution.
>
> So, is possible to use $\prod\_{i} p\_{i,\pi(i)}$ for ranking of permutation probabilities, where permutations $\pi$ are generated randomly only by (0,1) restriction matrix via Hungarian algorithm for bipartite graph matching?

**Comment:** I am convinced now, that only "simple" way how to solve my problem is to generate arbitrary (random) permutations $\pi$ which satisfy to (0,1) restrictions in probability matrix only (elements $p\_{i,j}\>0$ should be transformed to $p\_{i,j}=1$) and then rank all these permutations by $\prod\_{i} p\_{i,\pi(i)}$ probability.

The problem how to effectively generate (0,1) restricted permutations (permutations with restricted positions) is different problem.

# Answer
> 0 votes
**The problem has recently been actively studied:**

https://arxiv.org/abs/2007.15043

https://arxiv.org/abs/1904.03836

https://projecteuclid.org/euclid.ejs/1586419218

https://academic.oup.com/comnet/article-abstract/6/6/833/4772759

---
Tags: combinatorics, permutations, sampling
---


# Question
Title: Bellman Ford facts and specific question
The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following: $d(v)\>d(u)+w(u,v)$ holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)$ is the length of best path was found for vertex $u$.

If in any step there is no update for all vertexes, the algorithms terminate.

If Bellman-Ford will be used for finding all shortest paths from vertex $s$ in graph $G$ with $n$ vertex, terminate after $k \< n$ iteration then following is True:

```
number of edges in all shortest paths from $s$ is at most $k-1$

```

**I think some times this is true and sometimes is false (when we check all edges simultaneously... maybe this is wrong), but I need a clear definition for the above sentence or a small example about logic.** **I need verification of the above fact. is it always true? why?**

New Updates:

The above statement is dependent on the implementation of your algorithm (at least I think).

Which implementation makes it true and under which condition it becomes false...

I see 4 version of Belman Ford on This Jeff Erricson Algorithm Book on Page 295.

# Answer
> 1 votes
The claim is true. Any correct implementation of Bellman-Ford must guarantee this. Think about an arbitrary shortest path from $s$ to $v$. Besides being a shortest path with regard to the total weight, it must also satisfy another property: the path must be also shortest with regard to the number of edges used. In other words, the algorithm wants to determine shortest paths that are also simple paths (no vertices are repeated, i.e., all of the vertices in the path are distinct).

Why there is a need to ask for shortest and simple paths? Because there are obviously shortest paths with regard to the total weight that are not simple, e.g. there can be zero weight cycles. Bellman-Ford assumes that there are no negative weight cycles (the algorithm is able to detect a negative weight cycle) but there can be zero weight cycles, since they are actually allowed by the definitions. The problem caused by a zero weight cycle is that you can use it to arbitrarily augment the number of edges of a shortest path, by putting it somewhere in the middle of a shortest path. The total weight will remain the same, so the path will be a shortest path with regard to the weight, but not with regard to the number od edges composing it. This is the reason why you want shortest paths which are simple as well. The algorithm rules out zero weight cycles, throwing them away.

Now, everything follows immediately. A simple path can not have more than $|V| - 1$ edges: that is exactly the number of passes done by Bellman-Ford (since we assume no negative weight cycles, a shortest path can visit each vertex at most only once). Given a path $v\_0 = s$ -\> $v\_1$-\>...-\>$v\_k=v$ during the $i$th iteration the algorithm relaxes all of the edges; in particular, during iteration $i$ it relaxes the edge $(v\_{i-1}, v\_i)$. Therefore, after $i$ iterations the algorithm has correctly set the distance of vertex $v\_i$ from $s$. And we know that the input graph does not contain negative weight cycles, that the path is simple and that a longest simple path may have at most $|V|$ -1 edges. So, the algorithm is correct.

---
Tags: algorithms, graphs, data-structures, trees, shortest-path
---


# Question
Title: checking time for a circuit of size in polynomial k
On the page 1073 of CLRS(Introduction to Algorithms),

> Given a circuit C, we might attempt to determine whether it is satisfiable by simply checking all possible assignments to the inputs. Unfortunately, if the circuit has k inputs, then we would have to check up to 2^k possible assignments. When the size of C is polynomial in k, checking each one takes Ω(2^k), which is superpolynomial in the size of the circuit.

Can I ask what is the reason that checking if one truth assignment is a satisfying assignment takes Ω(2^k)?

# Answer
> 0 votes
You've misunderstood. They are saying that the running time to check all $2^k$ assignments (not the time to check one assignment) is $\Omega(2^k)$. It's a reasonable misunderstanding, as their wording is unclear, but that's what they mean.

---
Tags: np-complete
---


title: modular multiplication

text:
# Question
Title: modular multiplication
I was reading the Modular Multiplication page on wikipedia...and could not understand the algorithm to compute $a \cdot b \pmod{m}$.

```
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
  long double x;
  uint64_t c;
  int64_t r;
  if (a >= m) a %= m;
  if (b >= m) b %= m;
  x = a;
  c = x * b / m;
  r = (int64_t)(a * b - c * m) % (int64_t)m;
  return r < 0 ? r + m : r;
}

```

I get that:

$$ a \cdot b \pmod{m} \equiv ((a \mod{m}) \cdot (b \mod{m})) \mod{m}$$

the step I didn't get is `c=x*b/m`and later doing `r = (int64_t)(a * b - c * m) % (int64_t)m;` what is that for?

The article says:

> by employing the trick that, by hardware, floating-point multiplication results in the most significant bits of the product kept, while integer multiplication results in the least significant bits kept

I can't see how this is related !!!

# Answer
> 11 votes
Here's a more compact and mathematical description of what is going on. Let $a$ and $b$ be the input, already reduced modulo $m$, so $a \< m$ and $b \< m$. (Code-wise, this means after the `b %= m` line.) We want to calculate $ab \mod m$, which is to say, setting $x=ab$, we want to find $r\_x$ such that $x = q\_xm + r\_x$ for some $q\_x$.

### The Non-Overflowing Case

In the non-overflowing case, we could just calculate the modulus and be done with it. Instead, the code calculates: $$y = \left\lfloor\frac{x}{m}\right\rfloor = \left\lfloor q\_x + \frac{r\_x}{m}\right\rfloor = q\_x + \left\lfloor\frac{r\_x}{m}\right\rfloor = q\_x$$ Now $x - ym = q\_xm + r\_x - q\_xm = r\_x$. I elided a concern here though. It could be that $x$ doesn't fit in the mantissa of our floating point variable. As long as $m$ fits, though, this will not be a problem as $x = ab \< m^2$. We'll end up with $x' = x + e$ where $e$ is some round-off error whose magnitude is less than $m$. We proceed as before: $$y = \left\lfloor\frac{x'}{m}\right\rfloor = \left\lfloor q\_x + \frac{r\_x+e}{m}\right\rfloor = q\_x + \left\lfloor\frac{r\_x+e}{m}\right\rfloor$$ In this case, we can't eliminate the $\left\lfloor\frac{r\_x+e}{m}\right\rfloor$ because, while $r\_x \< m$ and $e \< m$, it may be the case that $r\_x+e \> m$ or $r\_x+e \< 0$, though it will certainly be (strictly) between $-m$ and $2m$, so $\left\lfloor\frac{r\_x+e}{m}\right\rfloor$ is either $0$ or $\pm1$. Now $$x - ym = q\_x m + r\_x - q\_x m - \left\lfloor\frac{r\_x+e}{m}\right\rfloor m = r\_x - \left\lfloor\frac{r\_x+e}{m}\right\rfloor m$$ Performing the modulus operation now will get rid of that extra term, however, due to the convention C chooses, `(-1)%m = -1`. To get a convention where we always return a positive number, we can add $m$ to the result if negative.

### The Overflowing Case

Let's assume that we are doing the integer arithmetic mod $N$, e.g. $2^{64}$, and let's assume $ab \> N$ which means $m^2 \> N \> m$. Now the multiplication is going to wrap. We'll write $x = ab = z + kN$ for an integer $k \< m$. That means the computation `a*b` will give the number $z$. The floating point computation is as before assuming, again, that the $m$ fits in the mantissa (which may require 80-bit extended precision floats for larger $m$). For the modulus, define $z = q\_z m + r\_z$ and $kN = q\_N m + r\_N$ so $x = q\_z m + q\_N m + r\_z + r\_N$. As before storing $x$ as a floating point variable may produce some round-off error $|e| \< m$ so again have $x' = x + e$. If we do the same calculation as before it looks like: $$\begin{align} z - \left\lfloor\frac{x'}{m}\right\rfloor m & = q\_zm + r\_z - q\_z m - q\_N m - \left\lfloor\frac{r\_z+r\_N+e}{m}\right\rfloor m \\ & = r\_z - q\_N m - \left\lfloor\frac{r\_z+r\_N+e}{m}\right\rfloor m \\ & = r\_z + r\_N - \left\lfloor\frac{r\_z+r\_N+e}{m}\right\rfloor m \\ \end{align}$$ I've pulled a rabbit out of the hat here. Here, we're doing addition mod $N$, and mod $N$ $q\_N m + r\_N = kN = 0$ so $q\_N m = -r\_N$. As before, we mod by $m$ to get $r\_z + r\_N = x \mod m$, and, as before, the C convention may lead to this being negative which will need correcting.

There's one potential remaining issue. $\left\lfloor\frac{r\_z+r\_N+e}{m}\right\rfloor$ could be $2$. This causes no problem unless $2m \> N$ in which case you'd get the wrong answer. For $N = 2^{64}$ this means $m \> 2^{63}$. (As an aside, if $2m = N$ it causes no issue since we'll end up with $0$.) If we configure the floating point hardware to round down so that $e \leq 0$, this case will not come up. (Though don't forget my restriction that the mantissa can hold $m$!).

### Connecting this to most/least significant bits

To specifically address the part that you quoted, consider an integer, $B$, greater than 2 which we'll think of as a base, as in "base $10$". In the usual $B=10$ case, the number $21$ is represented as $21 = 2B+1$. In a floating point representation we'd write this as $2.1\times B^1$. Now let's say we wanted to multiply two (positive) single base-$B$ digit numbers, the result would require at most two digits, say $cB+d$ where (as required by a \[standard\] base-$B$ representation) $0 \leq c \< B$ and $0\leq d \< B$. If we're restricted to only being able to store one base-$B$ digit of the result, there are two obvious choices, either $c$ or $d$.

Choosing $d$ is equivalent to working mod $B$ as $cB + d = d\mod B$, this is what happens with integer arithmetic. (Incidentally, at the assembly level, integer multiplication often does produce both of these digits.)

Floating point arithmetic, on the other hand, effectively corresponds to choosing $c$, but compensating that by incrementing the exponent. In effect, we represent the result as $c.d\times B^1$ but since we can store only one base-$B$ digit, this becomes just $c\times B^1$. (In practice, we'll consider numbers as multi-digit numbers in a small base (i.e. 2), rather than 1- or 2-digit numbers in a large base. This allows us to save some of the higher digits of $d$ if they aren't needed to store $c$, but in the worst-case scenario all of $d$ is lost. None of $c$ is lost until we start running out of room in the exponent. For the code above, this is not an issue.)

As long as $m$ can be represented faithfully in the floating point format, the expression $\left\lfloor\frac{ab}{m}\right\rfloor$ can be viewed as extracting that upper digit in base-$m$. You can view the code and math above as the interplay between base-$N$ and base-$m$ representations of a number.

### Practicalities

Based on section 5.2.4.2.2 of this draft, the C11 standard appears to only require `long double` to have a mantissa roughly 33 bits in length. (In particular, it appears to only specify the minimum number of *decimal* digits that can be faithfully represented.) In practice, most C compilers when targeting general purpose CPUs and particularly x86-family CPUs, will use IEEE754 types. In this case `double` will effectively have a 53-bit mantissa. x86-family CPUs support an 80-bit format with a mantissa with effectively 64-bits, and several but *not* all compilers will have `long double` indicate that when targeting x86. The range of validity of the code depends on these implementation details.

# Answer
> 0 votes
@D.W I noticed that for the case where e is negative, after the long double division, the value is being roundup, if that's the least significant bit, making it look like it represents exact value negating the rounding error. See this example. (2^63-2)*(2^63-2) = **85070591730234615828950163710522949636**. but this is represented as **85070591730234615828950163710522949632** in long double. This is a case where e is negative. when u divide it by (2^63-1), the answer should be **9223372036854775804.99999999999999999967**. but this is being rounded up to 9223372036854775805. so we really are not getting the case of (r+m) as the quotient we getting is the actual q but not q-1(which we are expecting since e is negative). To avoid rounding up, we need more precision to hold the decimal. The max error u can get when m is of order 2^63 is 2^60 when a*b is in the range of (2^125-2^126). Which requires at least 3 bits to hold the decimal value(e/m), but we are using 63 bits already to hold the mantissa of (a\*b)/m. If we use lower order m, the error will be lesser too, even though we use lesser bits to hold the mantissa, we would need more bits to hold the decimal value. for example, if m is in the order of 2^58, the max error between 2^115 and 2^116 is 2^50. Now the decimal value will be of order e/m (1/2^8) which requires 8 bits. So it looks like the total bits necessary (58+8 = 66) is always 66 bits but we only have 63 bits and hence its rounding up always when e is negative.

---
Tags: algorithm-analysis, modular-arithmetic
---


# Question
Title: Finding the rows/columns of an m-by-m symmetric similarity matrix M which minimizes the sum of the elements in an n-by-n submatrix N, where n < m
I have a machine learning problem where I need to find the most dissimilar subset of rows/columns of an $m$-by-$m$ symmetric similarity matrix $M$ which minimizes the sum of the elements in an $n$-by-$n$ submatrix $N$, where $n \< m$. In other words, by minimizing this sum, we find the most dissimilar rows/columns in $M$ that makes up $N$.

The values of $M$ are real, positive values between zero (dissimilar) and ones (similar). The diagonal consists of ones as the diagonal compares the same object with itself, meaning they definitely are identical. Furthermore, as the matrices are symmetrical, selecting row $i$ from $M$ also includes selecting column $i$ from $M$ (for $N$).

Take a 3-by-3 matrix as an example (i.e. $M$ with $m=3$):

\begin{pmatrix} 1 & 0.8 & 0.2 \\ 0.8 & 1 & 0 \\ 0.2 & 0 & 1 \end{pmatrix}

In this case, the first and second element are relatively similar (0.8), first and third are relatively dissimilar (0.2), and second and third are completely dissimilar (0). Assuming $n=2$, there are three possible ways to construct the submatrix $N$:

1. Select first & second row/column:

\begin{pmatrix} 1 & 0.8 \\ 0.8 & 1 \end{pmatrix}

2. Select first and third row/column:

\begin{pmatrix} 1 & 0.2 \\ 0.2 & 1 \end{pmatrix}

3. Select second and third row/column:

\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}

For this particular case, we know that the third alternative minimizes the sum. However, scaling this problem to $m=5000$ and $n=400$ makes the problem impossible to compute as the number of possible submatrices gets insanely large.

I was initially considering using the Monte Carlo method, but I'm thinking that there might be a more elegant way to do this. Do you have any pointers?

# Answer
Unfortunately this problem is NP-hard, meaning the best exact algorithm you can hope for will take exponential time in the worst case.

It is NP-hard because any algorithm that would solve this problem can also be used to solve the NP-hard problem Independent Set (IS), in which we have a graph $G = (V, E)$ and an integer $k$, and ask whether there is a subset $X \subseteq V$ of $k$ vertices such that no pair of vertices in this subset are adjacent. Given any algorithm for solving your problem, any instance $G$ of IS can be solved by giving this algorithm the adjacency matrix for $G$, in which every element is 1 (indicating a pair of vertices connected by an edge) or 0 (indicating a pair of vertices that are not) as input, together with $N=k$; there is a size-$k$ independent set in $G$ if and only if there is a subset of $N$ rows/columns in the matrix having sum $N$ (i.e., all diagonal elements are 1 and the rest are 0).
> 2 votes

# Answer
You can try using integer linear programming. It isn't a magic silver bullet and probably won't find the optimal solution in a reasonable amount of time, but if you give the ILP solver a time budget, it might find a reasonable solution.

A formulation as ILP: use zero-or-one variables $x\_i$, where $x\_i=1$ means that the $i$th row and column is selected. Introduce zero-or-one variables $y\_{i,j}$, along with inequalities $y\_{i,j} \le x\_i$, $y\_{i,j} \le x\_j$, $y\_{i,j} \ge x\_i + x\_j - 1$. Then your objective is to minimize $\sum\_{i,j} M\_{i,j} y\_{i,j}$, subject to the requirement that $\sum\_i x\_i = n$.
> 1 votes

---
Tags: optimization
---


# Question
Title: What does non-linearity mean in Neural Networks? Why is it necessary?
ReLU units are said to be necessary in CNNs to introduce non-linearity which convolution does not involve. This is needed, because many real-world forms of data are non-linear.

What does non-linearity refer to?

# Answer
> 1 votes
A neural network, in its simplest form, consists of layers of neurons.

The first layer of neurons are the input, and the last layer forms the output.

A neuron $x$ on layer $i+1$ is connected to several neurons $y\_1,\ldots,y\_d$ on layer $i$, and it computes the following function: $$ x = f(\alpha\_1 y\_1 + \cdots + \alpha\_d y\_d + \beta), $$ where $f$ is a fixed function (nowadays often ReLU), and $\alpha\_1,\ldots,\alpha\_d,\beta$ are parameters which are learned in the training period. (The output layer often uses a different $f$.)

If $f$ is the identity function $f(z) = z$, then each neuron in the output is just an affine function of the input. This means that no matter how many layers the neural network has, all it can do is compute linear functions.

In order to allow the network to compute more complicated functions, we introduce *nonlinearity*, in the form of a non-linear function $f$ (that is, a function which is not of the form $f(z) = az + b$), such as ReLU, which is $f(x) = \max(x,0)$. This makes the neural network more expressive.

---
Tags: neural-networks
---


title: Using hashing to solve 4-sum problem

text:
# Question
Title: Using hashing to solve 4-sum problem
The famous 4-sum problem is to find 4 elements at unique indices in an array which sum to a given X. I was looking at one solution I found:

```
findFourElements(A[1], ..., A[n], X)

create hashtable mp
for each 1 ≤ i < j ≤ n:
   mp[A[i] + A[j]] ← (i,j)     // (i,j) is an ordered pair
end for
for each 1 ≤ k < l ≤ n:
   if mp contains A[k] + A[l]:
      (i,j) ← mp[X - (A[k] + A[l])]
      if i ∉ {k,l} and j ∉ {k,l}:
         return A(i),A(j),A(k),A(l)
      end if
   end if
end for

```

It is working fine on some test cases I tried. But I have a doubt: in the hashtable we are just storing one occurrence of each pair, but there can be a case in which a solution exists, but since we stored only one occurrence of each pair, we only have overlapping occurrences, and we may miss the non-overlapping ones. But still I am not able to produce any test case to fail it. Is this algorithm correct, or does it fail for some test case?

# Answer
Suppose $A\[i\] + A\[j\] + A\[k\] + A\[\ell\] = X$. If there is a way to break this sum into two non-equal parts, then the problem you mention does not occur. Otherwise, we have \begin{align} A\[i\] + A\[j\] &= A\[k\] + A\[\ell\] \\ A\[i\] + A\[k\] &= A\[j\] + A\[\ell\] \\ A\[i\] + A\[\ell\] &= A\[j\] + A\[k\] \end{align} In fact, all of these are equal to $X/2$, and this implies that $A\[i\] = A\[j\] = A\[k\] = A\[\ell\]$.

The hashtable entry for $X/2$ can only contain two of the indices $i,j,k,\ell$, say $i,j$ (it might contain fewer). The algorithm then finds the correct solution when it reaches $k,\ell$ in the second stage.
> 1 votes

---
Tags: algorithms, data-structures, arrays, hashing
---


# Question
Title: CNNs: Why do the filters identify more complex features as the model goes on?
I have a feeling that it's related to how different output layers are stacked up against one another? However, there's a missing link in that argument that I can't completely get to.

# Answer
> 1 votes
In a convolution neural network, every neuron in layer $i+1$ depends on few neurons in layer $i$. It thus aggregated local information for layer $i$. As you go through the layers, the subset of input that the neuron sees grows, and so the features depend on a larger part of the input. Eventually, neurons depend, in directly, on all inputs.

---
Tags: neural-networks
---


# Question
Title: Mapping a free variable of type A to a cartesian closed category
In From Lambda Calculus to Cartesian Closed Categories, the author explains the interpretation of lambda calculus in cartesian closed category and at one point he explains how a term representing a free variable of type A is mapped to the cartesian closed category as follow:

```
 [Γ x:A :- x:A] = π2 : ([Γ ] × [A]) → [A]

 (A term which is a free
 variable of type A is an arrow from the product of Γ and the type object A to A;
 That is, an unknown value of type A is some arrow whose start point will be
 inferred by the continued interpretation of gamma, and which ends at A.
 So this is going to be an arrow from either unit or a parameter type to A -
 which is a statement that this expression evaluates to a value of type A.)

```

I appreciate if someone can elaborate further on what the author means, perhaps with an example, since I am a newbie to category theory.

# Answer
It's not clear exactly what your confusion is, so I'll try to explain the example more clearly, and you reply in the comments if something's still not apparent.

In the interpretation of the simply-typed $\lambda$-calculus in a cartesian-closed category, contexts $\Gamma$ and types $A$ are interpreted as objects $⟦\Gamma⟧$ and $⟦A⟧$ (types being equivalent to one-variable contexts), while a term $\Gamma \vdash t : A$ is interpreted as a morphism $⟦t⟧ : ⟦\Gamma⟧ \to ⟦A⟧$.

Context extension is represented by taking the product in the cartesian-closed category, that is: $⟦\Gamma, x : A⟧ = ⟦\Gamma⟧ \times ⟦A⟧$. We want to form the projection of the variable $x : A$, which is represented by a morphism $⟦x⟧ : ⟦\Gamma, x : A⟧ \to ⟦A⟧$, which by definition is a morphism $⟦x⟧ : ⟦\Gamma⟧ \times ⟦A⟧ \to ⟦A⟧$. There's one obvious choice here: to project the second component of the product. Taking $⟦x⟧ = \pi\_2$ gives us a term of the correct type and it satisfies the expected properties.

In general, contexts (represented by lists of variables in the type theory) are represented by products of types in the cartesian-closed category, and the term corresponding to the $i^\text{th}$ variable is given by the $i^\text{th}$ projection from the product, $\pi\_i$.
> 1 votes

# Answer
It might help to see explicit algorithms to compile the Lambda calculus to Cartesian closed categories.

A simple algorithm threads an environment through and looks up variables using a sequence of fst and snd

1. Start with an expression such as `[lam f. lam x. f x]` and an empty stack of variables.
2. When you reach a binder turn it into a currying combinator and add the variable to a stack `curry [lam x. f x]` and `[f]` and then `curry (curry [f x])` and `[f, x]`
3. Function application is compiled to `uncurry f . (fanout id x)` so we get `curry (curry (uncurry [f] . fanout id [x]))`
4. When you reach a variable look it up in the stack. `f` is the zeroth variable here.
5. Replace the nth variable with a sequence of fst and n snds referring to the variable. So we get `curry (curry (uncurry fst . fanout id (fst . snd)))`

This works for cs theory but is suboptimal and unreadable.

More practically one iteratively removes variable bindings without passing through an environment or first compiles to a form intermediate between closed Cartesian categories and the lambda calculus.
> 0 votes

---
Tags: lambda-calculus, category-theory
---


# Question
Title: Need help with recurrence relation and postcondition of a function
I just wanted to make sure I'm on the right track regarding this.

Here's the function that I'm dealing with:

```
import math

def Mystery2(A, f, l):
    if f == l:
        return A[f]
    m = math.floor((f+l)/2)
    x = Mystery2(A, f, m)
    c = 0
    i = f
    while i <= l:
        if A[i] == x:
            c = c + 1
        i = i + 1
    if c > (l-f+1)/2:
        return x
    return Mystery2(A, m+1, l)

```

The precondition is given as: A is an array of integers, and $f$ and $l$ are integers $0 \leq f \leq l \< len(A)$.

From what I can see by running the function, the postcondition appears to be that it outputs the element within f and l indices that occurs more than $ \frac{l-f+1}{2}$ times or A\[l\].

I'm not sure how to find a closed form for the recurrence relation representing the worst case runtime.

So far I figured that with $T(n)$ being the worst runtime of the function and $n = l-f$, $T(n)$ will be constant if $n = 0$ and $T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil - 1) + n\*c\_1 + c$, if $n \> 0$. I'm not sure how to convert this into a closed form.

Is it okay to simplify this into $T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil) + n\*c\_1 + c$ for the purpose of comparing it to the master theorem?

Thanks in advance for any help

# Answer
> 0 votes
Without having checked if $T(n)$ is correct, you can find the closed form by:

$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lceil\dfrac{n}{2}\rceil - 1) + n\*c\_1 + c$$

If n is odd, you can rewrite $T(n)$ as:

$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lfloor\dfrac{n}{2}\rfloor) + n\*c\_1 + c = $$

$$T(n) = 2T(\lfloor\dfrac{n}{2}\rfloor) + n\*c\_1 + c $$

If you substitute $T(\lfloor\dfrac{n}{2}\rfloor)$ you get

$$T(n) = 2( 2T(\lfloor\dfrac{n}{4}\rfloor) + \dfrac{n}{2}\*c\_1 + c ) + n\*c\_1 + c =$$

$$T(n) = 4T(\lfloor\dfrac{n}{4}\rfloor) + 2n\*c\_1 + 3c $$

If you substitute $T(\lfloor\dfrac{n}{4}\rfloor)$ you get

$$ T(n) = 4 (2T(\lfloor\dfrac{n}{8}\rfloor) + \dfrac{n}{4}\*c\_1 + c) + 2n\*c\_1 + 3c = $$

$$ T(n) = 8T(\lfloor\dfrac{n}{8}\rfloor) + 3n\*c\_1 + 7c$$

Now you can observe the pattern and see that after substituting $\dfrac{n}{2^{k-1}}$

$$ T(n) = 2^kT(\lfloor\dfrac{n}{2^k}\rfloor) + k\*n\*c\_1 + (2^0 + 2^1 +...+ 2^k)c$$

Let $n = 2^k$

$$ T(n) = nT(1) + n\*log\_2n\*c\_1 + (2^0 + 2^1 +...+ n)c = $$

$$ T(n) = n + n\*log\_2n\*c\_1 + (2^n - 1)c = $$

$$ T(n) = n + n\*log\_2n\*c\_1 + 2^n\*c - c = $$

So you have $O(2^n)$

Now if n is even, you have

$$T(n) = T(\dfrac{n}{2}) + T(\dfrac{n}{2} - 1) + n\*c\_1 + c $$

And you follow the same method as before (i.e., start by substituting n/2 and find the pattern after a few iterations).

---
Tags: runtime-analysis, recurrence-relation, recursion
---


title: Meaning of $\log^{O(1)}(a+b)$

text:
# Question
Title: Meaning of $\log^{O(1)}(a+b)$
What's the meaning of $\log^{O(1)}(a+b)$ ? Is it simply $(\log\_2(a+b))^k$ where k is calculated in constant time ? That is the base 2 logarithm usually in computer science when no other base is set, and the $O(1)$ at the log word means that the whole expression should be raised to the power of that number (which I named k) ?

# Answer
> 5 votes
By definition $$O(g)=\\{f\colon \exists C\>0, \exists N \in \mathbb{N}, \forall n\> N, f(n)\leqslant C g(n)\\}$$ so $O(1)$ can be viewed as set of bounded functions. Outgoing from here $\log^{O(1)}(a+b)$ we can understand as set of functions $\log^{f(n)}(a+b)$ where $f(n) \in O(1)$.

**Addition.**

Understanding of $f \in \log^{O(1)}(a+b)$ not seems to be differ from understanding of $f \in O(1)$ and does not mean that "O(1) can be arbitrary large constant", as is in your comments. $O(1)$ is not constant, or set of constants, but set of functions. In same way $f \in O(1)$ does not mean that $f$ is bounded by any arbitrary large constant, but there $\exists C\_f\>0$ for which we have $f(n) \leqslant C\_f$. So, $f \in \log^{O(1)}(a+b)$, mean, that $\exists g \in O(1)$, i.e. $\exists C\_g\>0$ $g(n) \leqslant C\_g$, such that $f(n)=\log^{g(n)}(a+b)$. In words: function $f$ is bounded by $\log$ having bounded function in superscript. For example, $f$ cannot be $\log^n(a+b)$, but can be $\log^{\frac{1}{n}}(a+b)$ or $\log^{\frac{1}{n}+1}(a+b)$.

# Answer
> 1 votes
As you mentioned, $\log^{O(1)}(a+b)$ can be rewritten as $(\log\_2(a+b))^{O(1)}$ and $O(1)$ means the power of the $\log$ is less equal than a constant.

If this term is mentioned as an upper bound for a given function $T(n)$, we will know $T(n) = o(n)$ (little-oh). And even more, we can say $T(n)$ is less than any $n^\epsilon$ for any $\epsilon \> 0$.

# Answer
> 0 votes
A quantity bounded from above by $(\log(a+b))^C$ for some $C \> 0$.

---
Tags: notation
---


# Question
Title: Minimal DFA accepting strings whose length is divisible by $x$ or $y$
Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$.

After trying various values of $x$ and $y$, I noticed made the following observation:

> If one of $x,y$ is a multiple of the other, then the minimal DFA contains $\min(x,y)$ states, and otherwise it contains $\operatorname{lcm}(x,y)$ states.

Is this true for all values of $x$ and $y$?

Also, what happens if we replace the condition "divisible by either $x$ or $y$" with the condition "divisible by both $x$ and $y$"?

# Answer
> 2 votes
Let $\operatorname{gcd}(x,y) = g$, and suppose that $x,y \> g$. If there is a minimal DFA for the language with $n$ states, then according to the pumping lemma, there is $1 \leq m \leq n$ such that the following holds: $\ell \geq n$ is a length of words in the language iff $\ell + m$ is a length of words in the language, that is:

> For all $\ell \geq n$: $(x \mid \ell \text{ or } y \mid \ell)$ iff $(x \mid \ell+m \text{ or } y \mid \ell+m)$.

Let $\ell \geq n$ be some multiple of $x$. Then $x \mid \ell$, hence either $x \mid \ell+m$ or $y \mid \ell+m$, which implies that $g \mid \ell$ and $g \mid \ell+m$, and so $g \mid m$.

Suppose that $x \nmid m$. Let $\ell \geq n$ be such that $\ell \equiv -m \pmod{x}$ and $\ell \equiv g \pmod{y}$; there exists such $\ell$ since $g \mid m$. Then $x\nmid \ell$, $y\nmid\ell$ (since $y \> g$), but $x\mid \ell+m$, and we reach a contradiction. Therefore $x \mid m$. Similarly, $y \mid m$. Therefore $\operatorname{lcm}(x,y) \mid m$, implying that $n \geq m \geq \operatorname{lcm}(x,y)$ (since $m \> 0$).

Conversely, it is easy to construct a DFA for the language with $\operatorname{lcm}(x,y)$ states, showing that this is the number of states in a minimal DFA, assuming that $x,y \> g$.

If $x = g$ or $y = g$, then the language consists of all words whose lengths are a multiple of $g = \min(x,y)$, and so the minimal DFA contains $\min(x,y)$ states.

Finally, if we replace *or* with *and* in the definition, then we get the language of all words whose lengths are a multiple of $\operatorname{lcm}(x,y)$, whose minimal DFA contains $\operatorname{lcm}(x,y)$ states.

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


title: Shortest Path with a twist

text:
# Question
Title: Shortest Path with a twist
We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can be activated at any node u, such that time between u to v becomes (u,v)/3. The turbocharger has to be used just once. Find the minimum distance path between s to t.
My approach - Use BFS to calculate all the paths. When we find all the paths from s to t, apply brute force to each edge (u,v) and check the minimum result. This approach takes O(V+E) + O(E) time roughly. (I assume).

I am looking for suggestions and better approach to this problem. Please appreciate my learning phase and help me to do better at algorithms.
Thank You.

# Answer
First, your algorithm is not |V|+|E| because each node can be visited more than once. This is because at each stage of your BFS, there is not greedy to always visit the optimal next node. If you are generating all paths, each path visits at most all the nodes once, so the time complexity of your algorithm would actually be O(PN) where P is the total number of paths. In fact, it is likely way larger because each edge can be visited more than once.

However, there is another algorithm that can be applied to this non-negative edge-weight graph: Dijkstra's Algorithm.

To deal with the turbo charger, simply expand the graph such that each each state in your heap stores both the current weight and wether the charger has been used.
> 1 votes

---
Tags: algorithms, graphs, shortest-path, breadth-first-search
---


# Question
Title: • How CPU identify that which device is sending the request? • How CPU decide which action should be taken for each request?
• How CPU identifies which device is sending the request? • How CPU decide which action should be taken for each request?

# Answer
I'm assuming that you are asking how devices communicate with the x86 CPUs.

The motherboard has different types of slots (USB, PCI-Express, VGA, etc). It depends on what type of slot your device requests come from.

The motherboard hardwires the slots to pins on the IOAPIC of the processor.

Devices communicate with the CPU through the IOAPIC. The IOAPIC has several pins including the IRQs pins. Today, each IOAPIC manages 24 IRQs (0 to 23). Each slot/device on the motherboard is given an IRQ by hardwiring (an actual electrical line) the slot's pins to a pin on the IOAPIC.

IOAPIC means In Out Advanced Programmable Interrupt Controller. It is programmable which means that you can change what interrupt is fired by what IRQ. When the device wants to tell the CPU it has data ready or anything else, it triggers the IRQ line. The IOAPIC is programmed by the operating system (OS) (at boot) to fire a certain interrupt number when a certain IRQ occurs.

For example, if a PCI device like a network card receives data which is destined to the computer (the request contains the right MAC address), the network card was made to fire its IRQ. Its IRQ is hardwired to an IOAPIC pin. If the IOAPIC was programmed by the OS to fire interrupt 10 for this IRQ then interrupt 10 is fired.

Each CPU has an IDT (Interrupt Descriptor Table). The address of the bottom of the IDT is stored in the LIDT special register of the processor. The IDT is made of entries which are numbered from 0 to any number.

An IDT entry in C looks like (https://wiki.osdev.org/Interrupt\_Descriptor\_Table):

```
struct IDTDescr {
   uint16_t offset_1; // offset bits 0..15
   uint16_t selector; // a code segment selector in GDT or LDT
   uint8_t zero;      // unused, set to 0
   uint8_t type_attr; // type and attributes, see below
   uint16_t offset_2; // offset bits 16..31
};

```

The offset is split into two parts which once put back together represents the address of the handler for this certain interrupt number. The CPU will calculate the position in RAM of an IDT entry by the formula `idt_base_address + (idt_entry_length * int_number)`. If interrupt 10 is fired then the formula becomes `idt_base_address + (8 * 10) = idt_base_address + 80`. The CPU will look 80 bytes after the base address of the IDT, it will take the offset found at that position, it will then jump at that address.

When the computer boots, the BIOS is programmed to check the motherboard's slots for devices. The BIOS then builds ACPI tables that it writes in RAM depending on what it finds. For example if it finds a Real Time Clock (RTC) on the motherboard it will write in RAM (https://wiki.osdev.org/AML)

```
Device (RTC)
{
    Name (_HID, EisaId ("PNP0B00"))  // _HID: Hardware ID
    Name (_CRS, ResourceTemplate ()  // _CRS: Current Resource Settings
    {
        IO (Decode16,
        0x0070,             // Range Minimum
        0x0070,             // Range Maximum
        0x01,               // Alignment
        0x08,               // Length
        )
        IRQNoFlags (){8}
     })
     OperationRegion (CMS0, SystemCMOS, Zero, 0x40)
     Field (CMS0, ByteAcc, NoLock, Preserve)
     {
         RTSE,   8,
         Offset (0x02),
         RTMN,   8,
         Offset (0x04),
         RTHR,   8,
         Offset (0x06),
         RTDY,   8,
         RTDE,   8
     }
}

```

This language is known as AML which is written in binary form in RAM. The OS needs to learn interpreting this language to determine what devices are plugged on the computer. These AML entries contain the IRQ that the device uses and some information on the device. The OS will use this to set up a handler for that device. Basically, if the OS finds a network card on a certain IRQ then it will setup this IRQ to a certain interrupt number which will point to a suitable handler for that device.

The OS communicates with devices using IO ports. It will use the ACPI tables to determine what device is plugged where and how to communicate with these devices. For every type of device (and any brand), the OS needs a driver. The driver can be either proprietary or open source (conventional). Very often manufacturers of devices will make their device respect certain conventions on how to communicate with them. This will widen the amount of OS which can "drive" their device and make it more user friendly (plug and play).

For example, if it finds a WIFI network card on a certain PCI slot, then it will setup a driver which will have certain special functions (depending on the type of device) that the OS can call. You can write drivers yourself and the OS is responsible to provide programming interfaces to ease the development of drivers and their installation in the kernel.
> 1 votes

---
Tags: operating-systems
---


title: Uniform sampling from a simplex

text:
# Question
Title: Uniform sampling from a simplex
I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should lie within the triangle:

```
x + y + z = 1
0 < x < 1
0 < y < 1
0 < z < 1

```

Ideally I want each point within the area to have equal probability. If it's too hard, I can drop the requirement. Thanks.

# Answer
> 36 votes
Let us first assume that you want to sample within

```
x + y + z = 1
0 ≤ x ≤ 1
0 ≤ y ≤ 1
0 ≤ z ≤ 1

```

This doesn't make quite a difference, since the sample point will still lie in your requested area with high probability.

Now you are left with sampling a point from a simplex. In the 3d example you get a 2d simplex (triangle) realized in 3d.

How to pick a point uniformly at random was discussed in this blog post (see the comments).

For your problem it would mean that you take $n-1$ random numbers from the interval $(0,1)$, then you add a $0$ and $1$ to get a list of $n+1$ numbers. You sort the list and then you record the differences between two consecutive elements. This gives you a list of $n$ number that will sum up to $1$. Moreover this sampling is uniform. This idea can be found in Donald B. Rubin, The Bayesian bootstrap Ann. Statist. 9, 1981, 130-134.

For example ($n=4$) you have the three random numbers `0.4 0.2 0.1` then you obtain the sorted sequence `0 0.1 0.2 0.4 1` and this gives the differences `0.1 0.1 0.2 0.6`, and by construction these four numbers sum up to 1.

Another approach is the following: first sample from the hypercube (that is you forget about `x+y+z=1`) and then normalize the sample point. The normalization is a projection from the $d$-hypercube to the $d-1$-simplex. It should be intuitively clear that the points at the *center* of the simplex have more "pre-image-points" than at the *outside*. Hence, if you sample uniformly from the hypercube, this wont give you a uniform sampling in the simplex. However, if you sample from the hypercube with an appropriate Exponential Distribution, than this effect cancels out. The Figure gives you an idea how both methods will sample. However, I prefer the "sorting" method due to its simple form. It's also easier to implement.

# Answer
> 9 votes
This is to add to the existing answers.

Devroye is an excellent reference for questions of this sort. Chap.7 gives the algorithms needed to generate uniform order statistics, which the OP is after.

For generating uniform order statistics, sorting $n$ samples of $\[0,1\]$ will do. This approach takes $O(n \log n)$ time. A quicker way ( available in the book) involves sampling $n$ random numbers $x\_1,\ldots,x\_n$ from an $\mathrm{Exp}(1)$ pdf. (These are the *spacings* of the uniform pdf). Then, return the values $$ (y\_i)\_{1\leq i\leq n} = \frac{\sum \limits\_{1\ldots i} x\_j}{\sum \limits\_{1\ldots n} x\_j} $$ which are automatically sorted, in $O(n)$ time overall. (I'm overlapping with A.Schulz's answer here- just making the computation more explicit).

The same approach can be adapted, via inverse CDF Sampling, to sample any non-uniform pdf over $\[0,1\]$. There's also a trick that enables you to sample uniformly over a simplex other than the canonical simplex (say $2x+3y+z = 5$).

# Answer
> 3 votes
```
X[0] = 0
for i = 1 to N-1
    X[i] = uniform(0,1)
X[n] = 1
sort X[0..N]
for i = 1 to N
    Z[i] = X[i] - X[i-1]
return Z[1..N]

```

Here, `uniform(0,1)` returns a real number independently and uniformly distributed between 0 and 1.

# Answer
> 2 votes
One other possibility is to use the Dirichlet distribution using the SciPy module. Essentially, if we set $\alpha=(1,\dots,1)^\top$, then the probability density is effectively uniform on a $n$-dimensional simplex where $n$ is the number of elements in $\alpha$.

Here is an example:

```
import numpy as np
from scipy.stats import dirichlet
n = 2
size = 1000
alpha = np.ones(n)
samples = dirichlet.rvs(size=size, alpha=alpha)

```

Now, if I plot it using matplotlib, we can see immediately see that it does a good job:

```
import matplotlib.pyplot as plt
plt.ion()
plt.scatter(samples[:,0], samples[:,1], alpha=0.05)

```

# Answer
> 1 votes
See this paper: Smith, N. and Tromble, R., *Sampling uniformly from the unit simplex*.

# Answer
> 0 votes
```
import numpy as np
def rand_simplex(k):
    return tuple(np.random.dirichlet((1,)*k))

```

This will generate one sample at a time.

---
Tags: algorithms, randomness, random-number-generator, sampling
---


# Question
Title: How can we tell a busy beaver candidate can halt?
If the BB function is computable, does that mean we know how to compute {i | program i eventually halts when run with input 0}, which is a clear contradiction with halting problem.

Does this proof work? Am I missing anything?

Thanks

# Answer
> 0 votes
Since the question has yet to receive an answer, I'll add this *comment* as an answer for future visitors.

You ask *"If the BB function is computable \[...\]"*, well, the Busy Beaver function is not computable, if by *BB function* you mean *given a size $s$ find $BB(s)$*.

Now, some terminology: *Busy beaver* is a *game* where you want to find, given an integer $n$, the Turing machine $BB(n)$ that has

1. $n$ states (plus an additional halting state)
2. is guaranteed to halt provided that the tape is clean when it starts
3. produces the maximum number of 1s on the tape of all halting $n$-state Turing machines.

Now, as you correctly guessed,

> Determining whether an arbitrary Turing machine is a busy beaver is undecidable.

---
Tags: computability
---