# Question
Title: Structural equivalence of self-referential structures
Given two types, T1 and T2, how does structural equivalence work when they're self-referential? Further, how do we go about proving it?

```
T1: struct { a: int, b: pointer to T2 }
T2: struct { a: int, b: pointer to T1 }

```

I was attempting to create a directed graph, and by proving the directed graphs are equivalent, we can prove the types are equivalent. For example:

$$G1: T1.b \rightarrow T2 \rightarrow T2.b \rightarrow T1 \rightarrow T1.b$$ $$G2: T2.b \rightarrow T1 \rightarrow T1.b \rightarrow T2 \rightarrow T2.b$$

I don't know if I'm the right track here or not.

# Answer
> 11 votes
Since your types both reference each other, these are not inductive types, but coinductive types.$^{1}$ That's because, if you expand out T1 and T2 (as you have done partially in the question), you get an infinite structure:

```
T1 = { a: int, { a: int, { a: int, { a: int , { ... } } } }

```

The phrase "coinductive types" may be scary, but all this means is that T1 and T2 represent **infinite trees**, rather than finite trees.

So your question is: how do you prove two coinductive types are structurally equivalent? The answer is with something called a bisimulation relation -- another scary word and formal concept that just means proving the two infinite trees are identical.

So in your example, we can write out the same type for `T2` and get the infinite tree

```
T2 = { a: int, { a: int, { a: int, ... } } }

```

Since the infinite trees for T1 and T2 are the same, we know that types T1 and T2 are structurally equivalent.

How do we prove this formally? We would define the bisimulation relation $\sim$ -- a relation between the nodes of the infinite tree for T1 and nodes of the infinite tree for T2 -- as the set of the following three pairs: $(\text{a}, \text{a}), (T1, T2), (T2, T1)$. Here is the picture of what's going on:

```
  T1              T2
 /  \            /  \
a    T2         a    T1
    /  \            /  \
   a    T1         a    T2
       /  \            /  \
      a    T2         a    T1
             \               \
              ...             ...

Bisimulation relation (mapping between left nodes and right nodes):

  T1      ~      T2
  T2      ~      T1
  a       ~      a

```

Now notice that for any node (type) $T$, we can prove that $T \sim T'$ implies that both children of $T$ and children of $T'$ are also bisimilar: this is because the left child is always `a` and the right child alternates, for $T1 \sim T2$ the right children are $T2, T1$ and for $T2 \sim T1$ the right children are $T1, T2$. So the bisimulation relation is a bijection between the nodes of both trees that preserves their structure, which proves that the two trees are the same.

$^{1}$ NB: it's technically possible to interpret T1 and T2 as inductive types, but then they are both empty (have no elements) because there is no way to construct an element of T1 or T2 in an inductive manner (that is, in order to create a T1 or a T2, you need to already have a T1 or T2 for it to point to). So I assumed that's not what you meant here.

# Answer
> 3 votes
```
T1: struct { a: int, b: pointer to struct { a: int, b: pointer to T1 }}

```

and

```
T2: struct { a: int, b: pointer to struct { a: int, b: pointer to T2 }}

```

seem to be structurally equivalent.

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


# Question
Title: Is the clique decision problem in co-NP?
Is the *clique decision* problem in *co-NP*?

**Definitions**:

"In the *clique decision problem*, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains a k-clique, and false otherwise." (https://en.wikipedia.org/wiki/Clique\_problem)

"A decision problem is in *co-NP* precisely if only no-instances have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate." (https://en.wikipedia.org/wiki/Co-NP)

# Answer
> 2 votes
It is not known, but believed to be unlikely. The Clique problem is NP-complete. If a NP-complete problem was in co-NP, then we would have NP = co-NP. It is an open problem whether NP = co-NP, but most complexity theorists expect that NP != co-NP -- which would imply that Clique is not in co-NP.

See also https://en.wikipedia.org/wiki/Co-NP#Relationship\_to\_other\_classes, If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$

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


# Question
Title: Design and analyze an efficient algorithm that, given n distinct integers, returns an element which is neither the smallest nor the largest
I'm trying to prepare for mock exam, could you please help me with possible solutions? Design and analyze an efficient algorithm that, given n distinct integers, returns an element which is neither the smallest nor the largest

# Answer
Straight forward and simple solution- 1)Randomly select any three integers from the list ,say p,q,r.

2)Return the element which is not maximum and minimum among p,q,r. Since all elements in the given list are distinct. Thus the solution is guaranteed for n\>=3.
> 2 votes

# Answer
As said elsewhere, the solution is the median of any three elements. As there can be $3$ outcomes, any solution based on comparison of the values must do at least $2$ comparisons. On the other hand, only $3$ different comparisons can be made. So far, we cannot tell if the worst-case requires $2$ or $3$ comparisons.

Now, WLOG, we can assume that the first comparison is $(a,b)$. For the second comparison, we can choose between $(a,c)$ and $(b,c)$. Then

* if we observe $a\<b,a\<c$, we still don't know which is the median element;
* if we observe $a\<b,b\>c$, we still don't know which is the median element.

In conclusion, the optimal solution (in the worst-case sense) must take $3$ comparisons.
> 2 votes

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


# Question
Title: Converting P = NP into an effective equivalence algorithm
If P = NP, then is it the case that there exists a total recursive function from the set of polynomial-time nondeterministic Turing machines to the set of polynomial-time deterministic Turing machines such that it sends every nondeterministic machine to an equivalent deterministic machine?

# Answer
> 1 votes
Yes, this is a consequence of the existence of NP-complete problems. (Of course a bit of care is needed to state the result precisely, e.g. the set of polytime (non)deterministic machines is not itelf recursive.)

---
Tags: complexity-theory, computability
---


# Question
Title: How to determine if two vertices (or two edges) fall on a cycle of a specific length?
A **walk** is a finite or infinite sequence of edges which joins a sequence of vertices. A **trail** is a walk in which all edges are distinct. A **cycle** in a graph is a non-empty trail in which only the first and last vertices are equal.

We know that determining whether two vertices (or two edges) fall on a triangle is relatively easy. However, I am not sure if there are any algorithms for general k-cycles. That is to say, I would like to determine whether two given vertices (or two edges) fall on a cycle of a specific length.

I am not aware of the existence or complexity of such an algorithm. However, I think if the length of the cycle is equal to the order of a graph, it must be NP-hard, because determining whether a graph is Hamiltonian is NP-hard.

# Answer
> 1 votes
If $k$ is an input, and the cycle is not allowed to repeat vertices, then as you say, the problem is NP-hard, as it is at least as hard as the Hamiltonian cycle problem (simply set $k$ equal to the number of vertices in the graph).

If $k$ is fixed and small and the cycle is not allowed to repeat vertices, I believe the problem can be solved in polynomial time (but exponential in $k$) by adapting the methods in https://cstheory.stackexchange.com/q/19508/5038.

If the cycle is allowed to repeat vertices and edges, then the problem is easy to solve. Let $A$ denote the adjacency matrix, so that $A\_{ij}=1$ if there is an edge $(i,j)$ in the graph and 0 otherwise. Note that $A^n$ can be computed efficiently using matrix multiplication, and $(A^n)\_{ij}$ counts the number of (non-simple) walks from $i$ to $j$ of length $n$ (where vertices and/or edges can be repeated). It follows that vertices $i,j$ are on the same cycle iff there exists $\ell$ such that $(A^\ell)\_{ij}\>0$ and $(A^{k-\ell})\_{ji}\>0$. This gives an efficient algorithm for your problem in this case.

---
Tags: graphs
---


# Question
Title: Declaring a JavaScript object in pseudocode
What's the proper way to declare an object in pseudocode. For example:

```
const car = {type:"Fiat", model:"500", color:"white"};

```

Would it be correct to write

object car { type: "Fiat" model: "500" color: "white" }

Or should a different format be used?

Thanks in advance.

# Answer
> 3 votes
There is no one "proper" way. Pseudocode is not a formally defined language that has an accepted syntax. Rather, it is an informal form of communication.

The criterion is: will it be clear to the reader? That will require you to use some judgement and knowledge of your audience.

If you are not sure, I suggest you use a different syntax that you are confident readers will understand, and/or include an explanation of your syntax in the text that accompanies the pseudocode.

---
Tags: pseudocode
---


# Question
Title: Does $\texttt{DTIME}(O(1))$ contain only finite languages?
My question is pretty much just the title.

It is pretty easy to see that any finite language can be solved in $O(1)$ time. For this reason, every finite languages is in $P$, $L$, and $DTIME(O(1))$.

But are finite languages the *only* languages that can be decided in constant time?

# Answer
No, for example the language of all possible input strings can be decided in O(1) time. Just return True without reading the input. More generally, note that you can only read a constant prefix of the input in constant time.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: How to determine the max offset of a value, given the range, step size and amount of steps
Given

1. The starting and the end values of *X*
2. The **maximum** step (maximum delta)
3. **Exact** amount of steps

I need to determinte the maximum and the minimum possible values that *X* could become during this chain of changes and still make it from the start value to the end value with the steps that are less or equal to the maximum step value.

**E.g.** for data:

* X\_start = -10; X\_end = 1;
* MaxDelta = 7;
* MaxSteps = 4;

The answer would be: Max = 4; Min = -11;
Sequences:
−10 → −3 → 4 →1
−10 → −13 → −6 →1

P.S. There is no need to generate such sequences, only the max and min values.

I have been thinking about the ways to do it efficiently and I am stuck. I have an idea that a binary search might be useful.

Any help/tips/suggestions would be much appreciated.

# Answer
Suppose we start at $s$ and want to end up at $e$. We take $n$ steps, $n^+$ positive steps and $n^-$ negative steps. Then we can reach maximum $m \in\[s, s + n^+\delta\]$ and can end up in $\[m-n^-\delta, m\]$. We get equations:

\begin{align} n &= n^+ + n^-\\ n^+ &\geq 0\\ n^- &\geq 0\\ s &\leq m \leq s+n^+\delta\\ m-n^-\delta &\leq e \leq m\\ \end{align}

Rearranging we get our upper bounds:

\begin{align} m &\leq s+n^+\delta\\ m&\leq e+n^-\delta\\ \end{align}

Substitute and realize maximum:

\begin{align} m &= \min(s+n^+\delta, e+n\delta - n^+\delta)\\ m &= s + \min(n^+\delta, e-s+n\delta - n^+\delta) \end{align}

This looks complicated, but set $x = n^+\delta$ and $c = e-s+n\delta$ you only need to solve how to maximize:

$$\min(x, c - x)$$

Can you take it from here?
> 0 votes

# Answer
For a given number of steps, the $\delta$ is

$$\delta=\frac{x\_e-x\_s}{n}$$ and you have the constraints $\delta\le\delta\_{\max},n\le n\_{\max}$ (if I understand anything of your question).

So

$$\left\lceil\frac{x\_e-x\_s}{\delta\_{\max}}\right\rceil\le n\le n\_{\max}.$$

---

There is only a solution when $x\_e-x\_s\le \delta\_{\max}n\_{\max}$.
> 0 votes

---
Tags: algorithms, binary-search
---


# Question
Title: Why this greedy algorithm does not return the optimal solution to this NP-hard problem?
**Problem:** In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w\_{ij}$ with bin $j$. The objective is to assign the items to the bins (while respecting the bins capacities) such that the number of assigned items is maximum. I know that this problem is NP-hard.

**Question:** why the following algorithm is not optimal?

**Algorithm:**

* For each bin $j$, assign the maximum. Here, assign the maximum means to iterate the items such that $w\_{1j}\leq w\_{2j}\leq\cdots\leq w\_{nj}$ and add to bin $j$ the items in that order until the capacity $C$ is filled.
* Take the union. This means that, if bin $j$ is assigned a set $S\_j$ of items, then the result would be: $\bigcup\_j S\_j$.

So for example if I have this instance: $C=4$ and $m=3$ and $n=7$. The weights are given by: $$\begin{pmatrix} 2 & 4 & 4\\ 2 & 1 & 4\\ 4 & 1 & 2\\ 4 & 1 & 4\\ 4 & 1 & 4\\ 4 & 4 & 4\\ 4 & 4 & 2 \end{pmatrix}.$$

So the algorithm gives the following assignment:

* bin 1: items 1 & 2,
* bin 2: items 2, 3, 4, & 5
* bin 3: items 3 & 7

Finally, we choose the following assignment:

* bin 1: items 1 & 2,
* bin 2: items 3, 4, & 5
* bin 3: item 7

Maybe I choose the bad example, can you show me how this algorithm fails?

# Answer
> 2 votes
One thing (which has been pointed out in the comments) is that it is unclear what you mean when you say "union". It appears that what you're doing is simply excluding items assigned to previous bins (but perhaps I do not understand, because "union" is a strange word for this). For example, when you've assigned 1,2 to bin 1 and 2,3,4,5 to bin 2, in the first step, in the final output you only assign object 2 to bin 1, and not bin 2.

Under this assumption, here is a simple example that shows that your greedy algorithm is not optimal. Assume we have two bins, both with capacity 5. Assume we have four items, with weights w\_1 = 1, w\_2 = 2, w\_3 = 3, w\_4 = 4 (we'll assume each item has the same weight for both bins). Then if you start assigning from smallest weight upwards until the bins are filled, your assignment is:

* bin 1: items 1 and 2
* bin 2: items 1 and 2

and after you exclude previously assigned items you end up placing items 1 and 2 in bin 1 and nothing in bin 2 (which is clearly not optimal, since you can place either of the other items in bin 2).

Perhaps you mean a different greedy algorithm, where first you assign 1 and 2 to bin 1, and then (since 1 and 2) are already assigned, you skip those and start again from lightest to heaviest weight, assigning item 3 to bin 2 (upon which there is no space for item 4). This assigns items 1, 2, and 3, and gets a score of 3.

But of course, it is possible to assign all the items, by assigning 1 and 4 to bin 1, and 2 and 3 to bin 2. The greedy algorithms miss this assignment.

As you've mentioned, this problem is NP-hard; in fact, it is hard even for the version where there are only two bins and the item weights are the same for all bins, where it reduces to the Subset Sum problem.

# Answer
> 1 votes
Let C be even. Take C items where $w\_{ij} = 1$ and C items where $w\_{ij} = 2$.

Your greedy algorithm will put the same C items in each bin, so you find a solution with C items. Instead you can put C items of size 1 into bin 1, then C/2 items each of size 2 into bin 2 and bin 3, giving a solution where you get C items instead of 2C.

---
Tags: algorithms, np-hard, greedy-algorithms
---


# Question
Title: Brzozowski's algorithm for Kleene star NFA
I have some troubles in understanding of the Brzozowski's algorithm for NFA to minimized DFA transformation. Or maybe I'm doing a mistake in the NFA to DFA transformation steps.

The Algorithm, as described in Wikipedia, is as follows:

1. Reverse the NFA.
2. Transform to DFA.
3. Reverse DFA.
4. Transform to DFA again.

Let's assume we have the following language: `A*` (zero or more repetitions of `A`).

For this language we may have the following NFA (over-complicated for a purpose):

1. I'm reversing it.
2. Turning reversed NFA to DFA using the Powerset approach.

1. The init state `3` Epsilon-closure is `{1, 2, 3}`.
    2. Closure `{1, 2, 3}` transits by `A` to `{1, 2}`.
    3. Closure `{1, 2}` transits by `A` to `{1, 2}`.

So, we have two new states for these two new closures and transitions between them as follows:

All states are final as their closures contain state `1`. `{1, 2, 3}` state is a Start state is it contains state `3`. This is clearly a DFA that reads the reversed language which is equal in this case to original one `A*`. There are redundant states, but I assume it does not contradict the Algorithm requirements.
3. Reverse it again.
4. Turning to DFA again.

1. The init state `3` Epsilon-closure is `{1, 2, 3}`.
    2. Closure `{1, 2, 3}` transits by `A` to `{1, 2}`.
    3. Closure `{1, 2}` transits by `A` to `{1, 2}`.

New closure-states and the topology of the final Automata are the same as on step 2.

But this DFA is not minimal. Can you explain me, please, where did I make a mistake?

Thanks in advance!

Ilya.

# Answer
> 4 votes
I realized this question is a duplicate.

Basically, as @Pseudonym mentioned above, when reverting DFA you should avoid introducing new starting state of the NFA even if there were multiple finish states in DFA. Instead just merge epsilon closures of each reversed NFA start state into a single closure and treat it as a start closure during the Powerset construction.

For those of you who faced this suboptimal issue after reading of the Wikipedia Article's Note:

> or add an extra state with ε-transitions to all the initial states, and make only this new state initial.

Please be aware, that this note is simply wrong.

---
Tags: finite-automata
---


# Question
Title: How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c
I know that, *T(n,m) = T(n-1,m) + T(n,m-1) + c* it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m).

The base condition is: *when m or n = 0, T(m,n) = 1 i.e., T(0,n)=1 and T(m,0)=1*.

But, how do I derive the time complexity from the above recurrence relation?

# Answer
> 1 votes
**Hint:**

A solution of the homogeneous recurrence is well-known to be

$$T(n,m)=\binom{n+m}n=\frac{(n+m)!}{n!\\,m!}$$

by Pascal's identity.

And a particular solution of the non-homogeneous solution is simply

$$T(n,m)=-c.$$

---
Tags: algorithms, time-complexity, algorithm-analysis, recurrence-relation, recursion
---


# Question
Title: How is an Assembly Language Processed by a CPU's Circuitry?
I'd like to have a bit more understanding of how, on a circuitry/hardware level, an assembler program works.

I think I have a very broad-brush understanding of how a CPU would process machine code on a hardware level. Please bear with me for this very generalised, hypothetical example:

If you took 00101110 in machine code, with the first part 0010 as an opcode and the second part 1110 as location address...

I think I understand, broadly, how those 8 bits of data would be fed along 8 wires to an instruction register, and how from there, the opcode 0010 gets fed along 4 wires into a variety of checking circuits to check the opcode, and a checking circuit would output true if if the opcode corresponded to the configuration of that circuit. Like this (yes I've been watching crash course computer science):

And i think I understand how, in broad terms, the location address 0111 would be sent along 4 wires that feed into multiplexors attached to four latch matrices, causing address location 0111 to be accessed in each of those matrices, each of which then feeds back whether its data bit at the location was a 1 or 0 / on or off.

What I'm saying is that I think I can begin to see, or at least imagine, how a processor 'processes' a binary number, on the level of hardware/circuitry, without it seeming like magic.

My question is, can someone explain to me on this level how a CPU, as part of an assembler, would translate assembly code?

For example, how would the circuitry take MOV EAX \[EBX\] and act on that as an instruction? I know that it would parse it, etc., but HOW does it parse it, on the level of wiring? Like how does it take a 'MOV' and translate that into the correct configuration of on/off wires?

On a related note, obviously the 'MOV' isn't stored as 'MOV' in the computer's memory - it's stored in binary. So if it's already stored in binary, why do we need to bother to translate it to a different binary configuration using an assembler?

# Answer
An assembler is a *program* that reads assembly language commands and translates then into a sequence of binary instructions, addresses and data values that is called machine code. The machine code is stored in the computer's memory and can be executed by the computer at some later time. Machine code is read and "understood" directly by the CPU.

So a command such as "load the value 10 into register A" might be written in assembly language as "LDA 10" and then stored in machine code as one byte 00101010. The first four bits of the machine code instruction 0010 represent the LDA instruction and the second four bits 1010 represent the value that is to be loaded.

Note that the assembler makes life easier for the programmer by translating the "LDA" instruction *and* translating the value 10 from decimal to binary. It will also do other stuff like allowing the programmer to use labels, which it then translates into specific memory addresses.

In the simplest CPU architecture, when the CPU executes the instruction 00101010 it actually runs a sequence of low level microinstructions which will be something like this:

1. Add 1 to the register that tells the CPU where the next instruction is stored in memory
2. Set a control line to take control of the data bus.
3. Load the lowest four bits of the machine code instruction onto the data bus.
4. Release control of the data bus.
5. Set a control line to tell Register A to read and store the value on the data bus.
6. Read the next instruction from memory.

In the very simplest/oldest CPU architecture this final translation from machine code to microinstructions is hard wired in logic gates.

A good guide to this sort of stuff for beginners is "But How Do It Know".

Bonus question: If an assembler is a program that creates other executable programs, how is the assembler created in the first place ?
> 4 votes

# Answer
The CPU only understands machine code. Assembly language has to be *compiled* to machine code in order for the CPU to execute it.

Machine code isn't very user friendly. While the very first computers might have been programmed directly in machine code, this has no longer been the case for decades. First, assembly language was invented, and programs, called assemblers, were written that converted assembly language into machine code. The next innovation was higher-level programming languages, that were converted into machine code by a more sophisticated type of program called a compiler. Nowadays we have additional levels of sophistication, like bytecode and virtual machines.

Throughout all this historical development, one thing stayed the same — CPUs only understand machine code, which a compact way of encoding instructions. Modern CPUs typically understand some dialect of an instruction set architecture like x86. There are only a few common instruction set architectures nowadays, and this means that there are many different CPUs which accept, roughly speaking, the same machine code.

The same instruction set architecture could support several assembly languages. For example, there are two different conventions for x86 assembly: AT&T and NASM. Under one convention (AT&T), `mov %eax, %ebx` means *move the contents of the eax register to the ebx register*; under the other (Intel), `mov eax, ebx` implies a move in the *opposite* direction. The CPU is completely oblivious to such differences, since all it gets to see eventually is machine code. The machine code produced by AT&T `mov %eax, %ebx` and Intel `mov ebx, eax` is identical: `89C3` in hex, or `1000100111000011` in binary.
> 3 votes

# Answer
That translation isn’t done by the CPU when it executed the instructions. It is done a lot earlier, when a program called “assembler” translates the assembler instructions into sequences of bits that the CPU can execute.

You say “it’s stored in binary”. Yes, it is translated from assembler to binary, and the binary code is stored.

How does the assembler do it? Write a C program that reads an integer, say the letters “1”, “2”, “3”, “4”, and writes the binary number 1234. An assembler is just the same, only more complicated.
> 2 votes

# Answer
I couldn't find any answer to the question online but i think i figure it out.

1- when you type on your keyboard any alphabetical letters, you actually sending a binary code NOT the letter itself. So...

2- the alu of the computer it is a hardware circuits which takes the instructions it is based on and execute them. **Here the ALU will NOT understand the MOV alphabetically**

3- so Basically what developers did on early stage of making computer languages is making an assembler. Which is like a software and what it does is simple actually.

So what they did is writing a code(software) using binary already stored in the computer memory which takes the the MOV and translate it to binary.

It is something similar to this :

When You type on your keyboard: MOV Command using assembly language Before it goes to the ALU it will go to the software-harward which does this through circuits

Mov Command In binary when entering it by the keyboard M 01001101 O 01001111 V 01010110

***Notice here : using assembly language MOV Command doesn't mean it is equal MOV String which has different value.***

These 3 binaries in consecutively will send the The MOV Command to the main as 4 digits ALU

In general I think these 2 stages all done in the processor and how it is built in.

To confirm my theory you will find some processor not using same commands . And can't understand probably assembly language, since they built on another set of instruments entirely......

Or that's how I think about it I'm not sure
> 0 votes

# Answer
The assembler translates human-readable instructions to machine-language code, which are mere binary numbers. The codes are made of an opcode (identification number of a specific operation) followed by arguments (register number, memory address, immediate value).

The processor fetches the opcodes one after another and has logic to recognize them and trigger a sequencer that will know where and when to fetch the next parts of the instruction, then execute them by fetching data from the appropriate source, directing it to the relevant section of the ALU and moving the results where appropriate.
> 0 votes

---
Tags: computer-architecture, assembly
---


# Question
Title: If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?
Just like the title states.

If I have a pseudo-random generator $g\colon \Sigma^n \rightarrow \Sigma^{2n}$ and a one-way function $f$, is $g'(x)=f(g(x))$ a pseudo-random generator? And why?

My instinct tells me it is, but I can't really explain why.

# Answer
**Hint:** Forget about the stretch of the PRG and let's instead focus on the whether the output of $f$ necessarily looks like a random string (even if we give it a truly random string instead of a PRG output).

**Answer:** The claim is false for a general OWF. A OWF is not guaranteed to have a "random looking" output. Specifically, the output can have an obvious tell which distinguishes it from a truly random string, e.g., $f(x)$ may always start with the bit $0$. In this case, a simple distinguisher that outputs the first bit of the given string has a constant advantage, which means that $f(x)$ is not pseudorandom. Extending this to show that $f(g(x))$ is not a PRG should be straightforward.
> 1 votes

---
Tags: complexity-theory, pseudo-random-generators, mathematical-analysis, one-way-functions
---


# Question
Title: Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$
I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages in NP reduce to in polynomial time.

But is this idea that NP-completeness implies all problems are in P if they are in P all encompassing? Of course, it works for other problems in NP, but let's take a problem in, say, EXPTIME, which P is known to be a proper subset of.

Is it correct to say that there is a polynomial time reduction from a language $A$ and a language $B$ in EXPTIME, if and only if $B \in P \Rightarrow A \in P$? How about the inverse? $B$ (in EXPTIME) reduces to $A$ iff $A \in P \Rightarrow B \in P$? And of course, what about the general case?

# Answer
No, this only works one way.

If there is a polynomial time reduction from $A$ to $B$, then $B \in P \implies A \in P$. This works irrespective of the what kind of languages $A$ and $B$ are.

The converse is not true. For example, take two languages $A, B \notin P$ such that there is *no* polynomial time reduction from $A$ to $B$ (these exist by the time hierarchy theorem). Then it still holds that $B \in P \implies A \in P$, since both sides of the implication are false.
> 3 votes

---
Tags: complexity-theory, reductions, logic, polynomial-time, polynomial-time-reductions
---


# Question
Title: EPSILON(CFG) = {<G,H> | G and H are CFGs where the concatenation is epsilon. is this language Turing-recognizable?
It is given that the language is not decidable.

Is this language Turing-recognizable?

# Answer
> 0 votes
Consider the language $\overline{\mathsf{EPSILON}\_{\mathsf{CFG}}} = \\{ \<G, H\> \mid \text{$G$ and $H$ are CFGs and $L(G) \cap L(H) \neq \\{\varepsilon\\}$} \\}$.

If $\overline{\mathsf{EPSILON}\_{\mathsf{CFG}}}$ and $\mathsf{EPSILON}\_{\mathsf{CFG}}$ were both recognizable, then they would both be decidable\*. Since $\mathsf{EPSILON}\_{\mathsf{CFG}}$ is not decidable, at least one of $\overline{\mathsf{EPSILON}\_{\mathsf{CFG}}}$ and $\mathsf{EPSILON}\_{\mathsf{CFG}}$ cannot be recognizable. It is not hard to show that $\overline{\mathsf{EPSILON}\_{\mathsf{CFG}}}$ is recognizable, which implies that $\mathsf{EPSILON}\_{\mathsf{CFG}}$ is not recognizable.

To see that $\overline{\mathsf{EPSILON}\_{\mathsf{CFG}}}$ is recognizable, notice that the problem of deciding whether a word is generated by a CFG is decidable. Then we can test whether $G$ and $H$ both generate $\varepsilon$. If that's not the case, we can immediately accept. Otherwise we can iteratively consider each word $w \in \Sigma^\* \setminus \\{ \varepsilon\\}$ and test whether $w$ is generated by both $G$ and $H$. If that's the case we accept.

---

\*Altough $\overline{\mathsf{EPSILON}\_{\mathsf{CFG}}}$ is not the complement of $\mathsf{EPSILON}\_{\mathsf{CFG}}$, the only difference lies in the words that do not encode a valid pair of CFGs. However, for any reasonable encoding, is decidable to test whether a word encodes a valid pair of CFGs.

---
Tags: undecidability, turing-recognizable
---


# Question
Title: Is there a good platform/software/language to make a computer analyze this optimization problem?
I am trying to optimize a building layout in a game, and it seems like the problem could be solved by a computer much quicker than by my own trial and error. However, I only have a cursory understanding of programming (mostly JavaScript), so I'm hoping some software exists which can do most of the work for me, or some open-source code is available that does something similar enough to be adapted to my purpose without too much difficulty.

I tried searching for programs/code related to graph theory, as the node-and-link nature of the game's building layout seems connected to graph theory, but I wasn't able to find anything. Most results were about drawing graphs or analyzing the properties of known graphs, rather than finding a graph with the desired properties. I also tried more general searches with no luck.

# The Problem To Which I Want To Find An Optimal Solution

We have a finite square lattice of 248 nodes, each of which can only be linked to its immediate neighbors (up to four Links total per node, fewer at the boundaries of the grid). Each node can contain a Workshop, contain a Module, or be empty. There is an additional special blocked node at the center of the grid which cannot contain a Workshop or Module, and to which all **non-empty** nodes **must** be connected by a path of Links through other nodes. A picture of the grid of nodes and possible Links is included below.

There are finite numbers of Workshops (12), Modules (48), and Links (120) available. There are five different types of Workshops (the total of 12 can consist of any combination of the 5 types) and six different types of Modules (the total of 48 can consist of any combination of the 6 types).

**The challenge is to get all Workshops up to maximum efficiency given the limited numbers of Modules, Links, and nodes. I want to be able to input any desired mix of Workshop types (for anywhere between 1 and 12 Workshops in total) and have the computer calculate the layout of Workshops, Modules, and Links that satisfies all requirements using the minimum possible number of Modules and Links, OR, if such a layout is impossible, calculate the layout that comes closest to satisfying all requirements.**

# Layout Requirements

Each type of Workshop requires three types of Modules nearby, with varying strength depending on Workshop type, for full productivity. The strength of a Module's effect decreases linearly with distance: at a distance of one Link the strength is 5 Module-strength-points (MSP), at two Links it is 4 MSP, at three Links it is 3 MSP, at four Links it is 2 MSP, at five Links it is 1 MSP, and at six Links or farther it is 0 MSP. The required minimum MSP from each Module varies with the type of Workshop; values are given below.

Workshops and Modules both produce heat (except the Radiator Module, which produces cooling or "negative heat"), and Workshops must be in a specific temperature range to function; values are given below. The magnitude of the temperature effect of a Workshop or Module decreases by 2° per Link from one to five Links, then drops to zero at six Links or farther. For example, the Solar Cells Module increases a Workshop's temperature by 10° at a distance of one Link, 8° at a distance of two Links, 6° at a distance of three Links, 4° at a distance of five Links, and 0° for any greater distance.

The effects (including temperature) of Workshops and Modules only travel across empty nodes to which they are linked. A node with a Workshop or Module on it will block the effects of any Workshops or Modules beyond it. The central node also blocks effects, but has no effect or heat itself. A Workshop always spreads only its base heat level to other linked Workshops, even if nearby Modules/Workshops are raising or lowering its effective heat level. The requirement that all non-empty nodes be connected to the central node is not blocked by other Modules/Workshops, so the connection can pass through occupied nodes.

Module effects and heat travel along the shortest available path of Links through empty nodes to each **separate** Workshop, so if a direct path is blocked but a less-direct path is available, the less-direct path will be used. If more than one free path to the same Workshop is available, the shortest one is used for calculations. Even if more than one free path of the same length is available, only one counts (buildings only affect each Workshop once). One Module can affect many Workshops, so for maximum efficiency, Modules should be shared by multiple Workshops when possible. Effects/heat from multiple Modules/Workshops can travel down a single Link, so branching Link paths allow many more than four buildings to affect a single Workshop despite each individual node only allowing up to four Links.

# How a Layout is Graded

A Workshop on its own, with no Modules and within its required temperature range, has a productivity of 10. With all Module-strength-point requirements fully satisfied, a Workshop has a productivity of 80, or the base 10 productivity-points plus 70 bonus productivity-points. Each Workshop requires a total of 21 Module-strength-points, receiving 10/3 ≈ 3.33 productivity-points for each Module-strength-point up to the maximum for that Module type. There is no penalty or bonus for having higher-than-required Module-strength-points.

Workshops that are outside their required temperature range drop by levels to 75%, 50%, and finally 25% productivity as their temperature goes farther above or below the required range. I haven't figured out the exact calculation behind the penalty yet, but even 1° of deviation outside the desired range leads to a 25% loss in productivity, so maintaining the desired temperature is critical.

An optimum layout will have all temperature requirements met, and all Module-strength-point requirements met (or exceeded), for all Workshops. If meeting all the Module-strength-point requirements is impossible, the most-optimal layout will have the greatest total number of Module-strength-points (ignoring any that go over the requirement for that Module type) per Workshop.

# The Construction Grid

# Workshop Stats

* Workshop-Agriculture

+ Base Temp: 20°
    + Min Temp: 20°
    + Max Temp: 39°
    + Module Requirements
        - Module-Artificial-G: 6
        - Module-Solar: 3
        - Module-Greenhouse: 12
* Workshop-Biotech

+ Base Temp: 5°
    + Min Temp: 30°
    + Max Temp: 39°
    + Module Requirements
        - Module-Artificial-G: 9
        - Module-Solar: 6
        - Module-Greenhouse: 6
* Workshop-Electronics

+ Base Temp: 5°
    + Min Temp: 0°
    + Max Temp: 9°
    + Module Requirements
        - Module-Solar: 6
        - Module-Stowage: 6
        - Module-Recycling: 9
* Workshop-Energy

+ Base Temp: 30°
    + Min Temp: 20°
    + Max Temp: 29°
    + Module Requirements
        - Module-Artificial-G: 3
        - Module-Solar: 15
        - Module-Stowage: 3
* Workshop-Heavy-Industry

+ Base Temp: 30°
    + Min Temp: 20°
    + Max Temp: 29°
    + Module Requirements
        - Module-Solar: 6
        - Module-Stowage: 9
        - Module-Recycling: 6

# Module Heat

* Module-Radiator: −20°
* Module-Solar: +10°
* Module-Greenhouse: +2°
* Module-Artificial-G: +6°
* Module-Stowage: +6°
* Module-Recycling: +8°

# Answer
That's a complex set of requirements, and I don't think I understand them all, so I'll suggest a few general approaches for this sort of problem:

One standard approach is to formulate this as an instance of integer linear programming, and use an off-the-shelf ILP solver. There are a range of techniques to map such constraints to ILP, used widely in operations research. For instance, you can introduce zero-or-one boolean variables $x\_i$, one for each candidate location, indicating whether it has a link or workshop or module there, and other variables to indicate the flow of heat/module effects.

A very simple approach is to use random search.

Another somewhat better approach is to use local search, where you start with one configuration and then iteratively improve it. For instance, you could use hill climbing starting from a random configuration and repeat many times, or use simulated annealing. You'll need to define a set of simple moves to make a small change to a configuration: e.g., move a Workshop by one square (and update the links), insert a Workshop (creating Links as needed), remove a Workshop, etc.
> 1 votes

---
Tags: graphs, optimization
---


# Question
Title: Data structure for represent the cake in cake dividing problem?
Got inspiration while reading history book. Inspired by: China, the cake of kings and emperors, Le Petit Journal 1898

**Background:**

> After the Second Opium War, United Kingdom(UK), France, Russia, Germany and Japan have a meeting to dividing China the cake.

The cake have fixed size but can be break down into many small pieces with different size. To make it is easier to divide, the cake start point is denoted as 0 and end point is denoted as 1, then a piece of cake can be denoted as P(i, S) with i is the position of that piece in the cake and S is the size of that piece

> Initially, UK grab half of the cake, the rest grab few pieces at different location and some pieces of the cake no one want it. Then France noticed that UK take too much and start to complain. UK then split that big piece in to many smaller pieces and give other country some pieces among them, of course there are also pieces no one want among them, then UK take another not so large piece somewhere else. But this piece is overlapped with one piece Germany have, so Germany have no choice but to give up on their piece and pick somewhere else. After few more debates everything has become a mess and hard to track which piece belong to whom. UK then make a call to his brother America and ask him which data structure can be used to represent this cake.

**Problem:** To avoided starting World War over China the cake, America must think of a data structure to store \<Country - Cake pieces\> information which as efficient as possible to perform these following operation:

1. Given P(i, S), find out the previous piece and the next piece and check if it is overlapped or not
2. Given P(i, S), add owner information
3. Given i, find out the owner of cake piece contain it
4. Given P(i, S), remove owner information
5. From the start position to the end position of the cake, list all owned cake pieces in order

Data structure do not need to store unowned cake pieces

**Question:**

1. If you are America, what data structure would you suggest if all operation have same frequency of usage and show complexity of each required operation to prove your opinion?
2. Given that operation 2 and 5 is used the most, what data structure would you used?

# Answer
> 0 votes
**Assumption** :The cake is not 'cut' but 'marked' because cut result in partitions and hence there will be no overlaps.

An Interval tree can be used to solve this problem. Interval tree is a self-balancing BST. Each cake piece P(i,S) forms a node with range values i and i+S.
**The structure of an Interval tree is given below**

```
struct Interval
{
  float left;       \\ left - stores the leftmost value of the range
  float right;       \\right-stores the rightmost value of the range
 }
struct node
{
  Interval *interval;
  string ownerinfo;  \\ storing the name of the owner
   node *leftchild,*rightchild;  \\leftchild and rightchild are the pointers to the left subtree and right subtree of a node
 }

```

Each cake pieces P(i,S) are inserted into the tree takes **O(logn)** in worst case.

**Queries :**
1)The previous pieces inserted into the tree can be stored into a temporary variables. Checking whether the pieces overlap takes **O(1)** time.
2)Adding owner information takes **O(logn)** time in worst case. Traversing from a root node to the node representing the piece P(i,S) takes **O(logn)**. The traverse is analogous to binary search.
3)The range or piece in which a point is contained can be find in **O(logn)** time .Since there is a possibility for the pieces to overlap a point i can be present in more than one cake pieces.Thus multiple answers are possible.
4)Similar to addition removal takes **O(logn)** time. Since removing owner information result in unowned cake pieces the nodes have to be removed and subtrees must altered. Deletion is similar to AVL trees.
5)The preorder traversal gives the owned pieces in the order.It takes **O(n)** time.

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


title: Half Clique Property question

text:
# Question
Title: Half Clique Property question
Hey I had this question and am stuck on part (b).

I don't see how its possible to find a graph with 7 vertices and 15 edges that does **not** have the half-clique problem. If there is a way, could someone share their thought process rather than the answer as I would like to figure it out on my own.

Thanks a lot!

# Answer
> 1 votes
Consider a clique $C$ with vertex-set $V = \\{1,2,3,4,5,6,7\\}$. $C$ has $\binom{7}{2} = \frac{6 \cdot 7}{2} = 21$ edges.

For any $S \subseteq V$ with $|S| \ge \lceil V/2\rceil =4$, either:

* $S$ contains at least two vertices in $\\{1,2,3\\}$; or
* $S$ contains at least $2$ vertices in $\\{4,5,6\\}$.

From the above it should be easy to construct the desired graph.

> You can simply delete all the edges between vertices that are both in $\\{1,2,3\\}$ or both in $\\{4,5,6\\}$ to obtain a graph that has $21- 2 \cdot \binom{3}{2} = 21 - 2 \cdot 3 = 15$ edges and does not have the half-clique property.

---
Tags: algorithms, graphs, clique
---


# Question
Title: Does the unsolvability of the halting problem imply the existence of Turing machines which cannot be proven either to halt or not halt?
My understanding is that this statement regarding the halting problem is proven:

> There does not exist any TM C that can, given a Turing machine A and input B as inputs, determine in a finite number of steps whether A halts on input B, and that works correctly for all A and B.

What I want to know is whether this related statement is also proven:

> There exists some TM A and input B for which no analysis exists which can prove whether A will halt on B.

To my mind this seems to create a contradiction as follows:

Assume TM A and input B exist.

If A halts on B, it must do so in a finite number of steps - this is a property of Turing Machines in general. Therefore, if A halts on B, such can be proven by simulating A for a finite number of steps.

Because it is impossible to prove whether A(B) halts, A does not halt (because if it did, such would be provable).

A is proven to not halt, but was given the property of being unprovable as to whether it halts - this is (P ∧ ¬P), an apparent disproof by contradiction.

Have I misapplied a rule here, or is there an important aspect of this problem I'm missing?

I'm trying to understand whether the insolvability of the halting problem expresses a limit on the power of Turing Machines to solve or a more general unprovability of some true statements.

Edit: What I'm getting from some helpful comments seems to be that the problem pretty quickly becomes degenerate in that "prove" can't be defined in a way that is both true to the intuitive sense of the word and formalizable.

# Answer
Elaborating from my comments above, here is at least one partial answer to your question:

As has been clearly known for about 100 years, there is no program that can correctly solve the halting problem 100% of the time, given any other program we want it to analyze. Or, at least, as Turing put it, such a program "cannot be a \[Turing\] machine." So, on the one hand, this would seem like a profound limitation for how powerful computers can ever get.

On the other hand, clearly people "solve the halting problem" for specific situations all the time. Every time you debug a program and realize that you need a mutex because your threads will deadlock, you have "solved the halting problem" for your program. Even something as mundane as proving a mathematical theorem is equivalent in strength to solving the halting problem, but grad students do it every day (first-order validity is RE-complete). And then there's the *entire discipline* of computational complexity theory: in order to determine the asymptotic complexity of *any* algorithm, the first step is to show that the worst-case running time is finite - meaning we have to show that it halts on *all* inputs - which is *much harder* than the halting problem! Yet we haven't given up on computational complexity as a useless endeavor. How does this work?

The first way to start making sense of this situation is to relax our constraints for the halting problem. We can look at programs which can correctly solve the halting problem for *some* subset of inputs. In this situation, we will say that we don't really care what the program does for programs outside of this subset: it can return the wrong answer, or not halt at all, or return a special error value; whatever you want. This is something like what humans do when we solve the above "real-world" problems: we have some subset of things we know how to analyze, and outside of that we basically give up. Of course, humans are even less rigorous than this; even when we look at some program which we do know how to analyze, there's always some chance we'll get it wrong anyway, or get stuck until we give up. But good enough.

The same, presumably, would be true for artificial intelligence algorithms: I really don't want to get into a huge debate about the future of AI here, but I will simply say that clearly, they are getting very good at writing and debugging code - including debugging bugs which could cause programs to deadlock, hang, or otherwise "not halt" - and they will also certainly get much better. However, they, like humans, can also screw up, or return an "I don't know" answer. Training (e.g. from GPT-3 to GPT-4) can increase the subset of situations these AI systems can correctly analyze. So again, the idea of looking at "partial oracles" which can solve the halting problem "sometimes," or "enough of the time for problems I care about," or etc, would seem to be relevant here as well.

Here is the subtlety with all of this: you have to determine what it actually means to "analyze" or "prove" that a program will halt at all. So, for instance, let's say you follow the majority of mathematicians and formalize your proof in ZFC set theory, such that a Turing machine is defined as a "set" of symbols, states, and so on, where the first+order ZFC axioms tell us what a "set" means. Then, you can go about looking for some mathematical proof of whatever it is you want to prove.

The main problem, here, is that if you start with ZFC - or *any* first-order proof system - we can *reverse-engineer* an algorithm that will never halt, but which ZFC will not be able to prove doesn't halt - unless ZFC is inconsistent and can prove anything, at which point we don't want to use it at all. I will call this algorithm the *Gödel algorithm* for ZFC, as it's really just a restatement of Gödel's famous incompleteness theorem in computer science-ish terms.

It's very simple: any mathematical proof formalized in something like ZFC is just a finite-length string of symbols on some alphabet. So we just enumerate through all strings, one by one - and at each step, we check if the current string happens to encode a valid proof that 1 = 0. If we have, then we have proven that ZFC is inconsistent. If ZFC *is* consistent, then no such proof string will exist, and this program will never halt.

We may ask if this particular program is an example of your Turing machine *A*. After all, the standard foundation of mathematics is insufficient to prove that it doesn't halt - unless the standard foundation of mathematics itself is logically contradictory. But this isn't the entire answer either. Just because ZFC set theory can't prove this, doesn't mean that *nothing* can prove it. We just can't prove it using ZFC itself - we need to go to a *stronger theory* which is able to prove this. In fact, a natural example of such a theory really does exist, which is ZFC plus the existence of a strongly inaccessible cardinal, or equivalently a "Grothendieck universe." But then, we can similarly reverse-engineer a "Gödel algorithm" for that theory. And of course, if ZFC *were* not to be consistent, then all of these stronger theories which prove its consistency would be inconsistent as well, which would topple the entire house of cards.

That doesn't mean your question has no answer. It does mean that you have to figure out what kind of "proof" would satisfy you. For instance, we could trivially prove that some Turing machine halts by simply stating it as an axiom: Turing machine T halts, formalized somehow or another. This would be a formal system of logic which does prove that T halts, but it would be silly. An even worse example is just to look at the algorithm TRUE, which just returns "true" and accepts any input. This will, through sheer random chance, correctly assess the halting status of any program which really does halt, if sent in as input - also silly.

Some deep thought is required to determine what you would view as a valid proof system: something where we haven't baked the answer to the haltingness of individual Turing machines into the axioms, but which are somehow derivable from some basic first principles. If you can actually figure out how to phrase that question in a rigorous way - and I'm not sure how - then you can ask if, for any candidate Turing machine $T$, some *consistent* proof system does exist which has whatever properties you are looking for, and which correctly proves if $T$ will halt.
> 4 votes

# Answer
Great question! To try to give a slightly shorter answer:

Fist, we know that for any formal system, no matter how powerful, there **are** TMs A and B such that A cannot be proven to halt on B. Given your argument, how can this be?

To be concrete, we can define "provable" formally as "provable in ZFC" (any other powerful axiomatic system would work, too). When that is done, your argument is actually correct (!), but doesn't show what you think it shows.

What you have showed is that:

* IF there is a TM A and an input B, such that it is impossible to prove in ZFC whether A halts on B
* THEN A does not halt on B.

However, the flaw in your argument is "A is proven to not halt". We only showed that A does not halt, not that it is provable that that is so.

It is useful to denote "provable" with a box symbol: $\square$. You first assumed, towards a contradiction, that $$ \lnot \square P \land \lnot \square \lnot P $$ You then correctly observed that, where $P$ = A halts on B, $$ P \to \square P $$ from which it follows (correctly!), using the contrapositive and $\lnot \square P$, that $$ \lnot P $$

But it does not follow that $\square \lnot P$. Godel's theorems show that there are for any formal system, statements that are true, but not provable in that system. So unfortunately, we cannot make this final leap in your argument.
> 3 votes

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


# Question
Title: Disjoint Subset Sum Reduction (NP-Complete)
I am using past materials to review for an upcoming assignment and came across this question:

Disjoint Subset Sum:

Input: A set of integers S and a goal g(in the set of natural numbers)

Output: YES if there are at least two disjoint(non-overlapping) subsets of S where the elements of each subset sum to exactly to g otherwise NO

I need to prove that this is NP-Complete.

I know how to prove it is in NP. However, I am struggling with the reduction from subset sum to this problem. My initial thought was adding 0 and g to the set in subset sum to modify the input because if subsetsum had a subset that summed to g then the second disjoint subset must be 0 and g. The problem with this is that subset sum takes in a set of non-negative integers(according to the way I learned it) so 0 and g can already be in the set. I have tried other ways but I can't seem to account for any edge case that arises.

I think there is an edge case: adding 'g' to some subset S doesn't change if g already exists(so I think the reduction has to do with adding g)

Any help is appreciated! I wasn't able to find anything similar online(only the partition problem) so I'm asking here!

# Answer
You are almost there. First of all it is useless to add $0$, even if it were allowed by the problem statement. Second, if the subset-sum instance is trivially a yes-instance because its set of integers already contains the target value (notice that you can detect this in polynomial time) then you can return any fixed yes-instance of disjoint subset-sum.

To summarize, if $\langle S', g' \rangle$ is an instance of subset-sum, a possible polynomial-time reduction to disjoint subset-sum returns the instance $\langle S,g\rangle$ where:

* If $g' \in S'$ then $S =\\{1, 2, 3\\}$ and $g = 3$;
* Otherwise ($g' \not \in S'$), $S = S' \cup \\{g'\\}$ and $g = g'$.

To see that this works, consider a yes-instance $\langle S', g' \rangle$ of subset-sum. If $g' \in S'$ then $\langle S,g\rangle$ is trivially a yes instance of disjoint subset-sum. If $g' \not \in S'$, then let $S^\* \subseteq S^\*$ be a set such that $\sum\_{s \in S^\*} s = g'$. A solution to the disjoint subset-sum problem is given by the two sets $S^\*$ and $\\{g'\\}$.

Suppose now that $\langle S,g\rangle$ is a yes-instance of disjoint subset-sum. Then there are two disjoint sets $S\_1, S\_2 \subseteq S$ such that $\sum\_{s \in S\_1} s = \sum\_{s \in S\_2} s = g = g'$. Since at least one of $S\_1$ and $S\_2$ does not contain $g'$, this set is also a solution to the original subset-sum instance $\langle S', g' \rangle$.
> 1 votes

---
Tags: np-complete, np-hard, subset-sum
---


# Question
Title: What name is used in the literature for an interpreter or compiler which compiles and executes all function calls which have constant literal inputs?
In the following discussion, we use the term *old programming language* to refer to programming languages which had their first release prior to the year 1990.

In *old programming languages*, there was a strong distinction between:

> 1. run-time functions.
> 2. compile-time macros.

In a running example, suppose that a computer programmer wrote code to emulate a Word Processor such as Libre Office Impress.

Before a computer programme was compiled, a computer programmer typed-in code for compile-time macros.

After at run-time, a non-computer programmer might write their resume for a job as a fork-lift operator inside of a word process such as Libre Office Impress.

Clearly, run-time code depends on what the prospective fork-lift operator would type into their resume.

> 1. In an older programming language, the compile-time macro `MACRO_CONCATENATE("Insert", "Picture")` might be replaced by `"Insert Picture"` at compile-time.
> 2. The runtime function `concatenate(x, y)` would execute at run-time.

What name has been previously established in the computer science literature for a compiler which ignores the traditional distinction between run-time functions and compile-time macros?

What do you call a compiler that does the following?

> * At compile-time, the compiler executes functions calls if the function call had constant literal inputs at ***compile-time***
> * The compiler executes functions which have run-time dependent inputs at ***run-time***?

As another example, consider the following...

```
big_letters = "".join(chr(x) for x in range(ord("A"), ord("Z")))

```

That code could be simplified, as follows:

```
big_letters = 'ABCDEFGHIJKLMNOPQRSTUVWXY'

```

Some compilers execute all function-calls in a given programme if both of the following conditions are met:

> 1. The inputs to the function-call are constant literals such as `"A"`
> 2. The tree of callees (descendants) of the function-call contain no calls to runtime-only functions. Runtime-only function read from file, write to file, use `stdout`, `stdin`, `cin`, `fprinf`, `print`, etc...

Some compilers build trees of nodes such that:

* Each node $p$ in the tree represents a function-call $f$ or a constant literal such as `3.9020`
* Suppose that function-call $f$ calls the function defined in the defintion for function $F$.
* A child of node $p$ is node $k$ such that node $k$ represents a function-call $g$.
* function-call $g$ is associated with the definition of a function $G$. function-call $g$ is a function-call present inside of definition of function $F$.

For example, if a function named `MakeDinner()` calls `MakeSpinachSauce()` and `MakeFlatBread()`, then `MakeSpinachSauce()` and `MakeFlatBread()` are children of `foo`.

So, if the inputs are known at run-time, the work gets done at run-time.

If the inputs to a function are not known until an unemployed warehouse worker types their resume for a Fork-Lift operator job, then the work for those functions is done at run-time.

Leaf-nodes of the tree are:

* constant literals, such as `12.8302` or `"hello world"`.
* calls to run-time only functions which have no callees

The compiler identifies constant literal leaf nodes.

We compute the parents of constant literal leaf nodes.

After the parent of some constant literal leaf nodes is calculated, we delete the constant literal leaves.

Computing the parents of leaf nodes continues in a recursive manner until all nodes have one or more children which are run-time only functions.

What is the name of this type of programming language?

Functions are executed at run-time if the functions call a function which calls a function which calls a run-time only function.

Functions are executed at compile-time if the function only calls functions which call functions which call functions which process constant literal integers, strings, floats, etc...

# Answer
This is known as partial evaluation.

See also constant propagation and compile-time function evaluation.
> 2 votes

---
Tags: programming-languages, language-design
---


title: Sorting Numbers in O(N)?

text:
# Question
Title: Sorting Numbers in O(N)?
Why is sorting numbers Omega(nlogn)? I'm thinking of an reduction algorithm where:

For all the numbers x\_i, we create a point (x\_i, 0) on a 2d graph.

Fit a line directly to the right starting from the leftmost point.

Sorted numbers are the order in which we encounter the points.

Would this not be an O(n) number sorting algorithm?

# Answer
> 1 votes
I'm not going to analyse your algorithm; it's very instructive for you to discover if it will work or not. But let's talk about the computational complexity of sorting.

Let's assume for a moment that you have $n$ items, all of which are distinct.

There are $n!$ possible ways to put these in order. You can think of sorting as discovering which of these permutations is the correct one. If you think about it, this is equivalent to determining an integer between $1$ and $n!$ (or, equivalently, between $0$ and $n!-1$).

How much information do you need to do that?

Well, given $k$ bits of information, you can distinguish at most $2^k$ possible things. Or, alternatively, you can represent a number between $1$ and $2^k$ or between $0$ and $2^k-1$.

So it follows that to sort these $n$ items, you need $\log\_2 n!$ bits of information.

Using Stirling's approximation:

$$\log\_2 n! = n \log\_2 n - n \log\_2 e + O(\log\_2 n) = \Omega(n \log n)$$

Therefore, you need $\Omega(n \log n)$ bits of information to sort $n$ items.

If all you have to test items is a "less than" comparison operator, then this returns one bit of information every time you call it, so you must perform $\Omega(n \log n)$ comparisons. You cannot get around this, because if you perform any fewer comparisons, you do not have enough information to distinguish between all possible permutations of the input.

This does not, however, mean that, in general, sorting requires $O(n \log n)$ time. We can do better than this if we modify our assumptions.

For example, what if not all of the $n$ items were distinct? If they were all the same, you can test this in $O(n)$ time, and then sorting is a $O(1)$ no-op.

In general, sorting $n$ items which are not necessarily distinct requires $O(nH)$ comparisons, where $H$ is the Shannon entropy of the keys.

Another assumption we could change is the one that we only have a test/query operation that returns one bit of information. If we had one that returned $O(\log n)$ bits of information, we might be able to sort in $O(n)$ time. And, indeed, we can do this using an algorithm such as radix sort under some reasonable assumptions (e.g. that you are sorting integers in the range $\[1,n^c\]$ for some constant $c$).

Just as an aside, because I love this paper, I have to mention this again. An algorithm is known that stably sorts $n$ integers in the range $\[1,n^c\]$, in $O(n)$ time, using $O(1)$ extra space. This means that, from a theoretical perspective, in-place integer sorting is a solved problem.

Your language's standard library probably only supplies a comparison-based sort. The reason why is not because it's the fastest algorithm available, but because it has the most convenient user interface. "Library sort" algorithms need to work with user-defined types, and requiring the user to only write a "less than" or "less than or equal to" operator makes it much easier to use.

# Answer
> 1 votes
You are thinking in terms of a putative geometric computer, that implements an implicit order axiom, and is operated by an observer. What you are missing is that the observer has a *synoptic* view on that data, with an apparent $O(1)$ complexity, and is similar to parallel computing. This is not how a sequential computer works.

---

Now imagine a mechanical computer holding a paper strip such that its length is sufficient to represent the whole range of input values. It can move the strip at constant speed to any location and punch a hole. It can also detect the holes and return their position.

Assuming that the total travel time is proportional to $n$ \[which is a questionable hypothesis\], this computer will sort as follows:

1. move to every position in turn and punch a hole;
2. return to the leftmost point;
3. detect all holes from left to right.

In the worst case, the first operation will take time $O(n^2)$ and the other two, time $O(n)$. The sorting per se takes no time, it is implicit.

# Answer
> 0 votes
You can sort *some* arrays in O(n). One case is an array of n elements, created by starting with a sorted array of n elements, and modifying O (n / ln n) of those elements. An obvious case is an array that is already sorted, or sorted in reverse order, or the concatenation of two arrays that are each sorted or sorted in reverse order.

These cases happen quite often. For example, you might have a list of employees sorted by last name, and over a month a few of those change their last name, or have typos corrected. As long as the number of changed entries is O (n / ln n), you can sort the array in O (n).

---
Tags: reductions, sorting
---


# Question
Title: Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form
Here's what Wiki says:  And here's what Mike Sipser says in his Introduction to Theory of Computation:

The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting that for a grammar to be in Chomsky's normal form, it should have all of those forms while Wiki explicitly says that it has to be only one of the many.

Which one should I be believing?

# Answer
Sipser clearly implies an *or* between those two rules. The two definitions say the same thing.

Meanwhile, in formal language theory, it is quite common for two textbooks or article to *not* say the same thing when defining terms. For instance, some definitions of context-free grammars do not permit $\epsilon$ rules at all.

So in general, the definition you should "believe" is the one used in the article or textbook you're using at the time, and when writing your own, you supply your own definition. It will be OK as long as it is essentially equivalent to a definition used by somebody else.

For instance, there is an easy and well-known rewriting process to eliminate all $\epsilon$ rules from any context-free grammar except possibly leaving $S \rightarrow \epsilon$. As a consequence, for most purposes it is of little consequence whether or not a definition of context-free grammars allows $\epsilon$ rules; that is just a detail to bear in mind while reading the text at hand.
> 16 votes

# Answer
Sipser doesn't require that both of those forms be used. It just requires that every rule fit one of those two patterns.
> 8 votes

---
Tags: formal-languages, computability, context-free, formal-grammars, pushdown-automata
---


title: Relation between algorithms and models

text:
# Question
Title: Relation between algorithms and models
I have found this question some time ago. While reading it, I had a problem with understanding the following idea:

***Question, part 1:*** *Is one allowed to talk about the time/space bound of any algorithm (e.g. the $O(n)$ time bounded algorithm proposed in the cited question's comments) without considering at least one concrete model (e.g. a Turing machine) that could guarantee a solution to the problem within that bound?*

That is to say, would an algorithm $A$ presenting some worst-case time upper-bound $O(f(n))$ always be guaranteed to have one corresponding Turing machine $M$ that could run it on all inputs within the same given time bound?

***Question, part 2:*** *How could the algorithm for the cited problem be represented on one Turing machine? Does the fact that Alice owns information Bob does not (the number $k$) influence the way the Turing machine would be built? How do you see it?*

Thank you very much.

# Answer
> 0 votes
Allowed probably isn't the right word. You can do anything you want.

You can certainly have a lower bound without being sure whether it is tight or not. For instance, I can say that sorting takes at least $\Omega(n)$ time, without knowing whether there is an algorithm for sorting that runs in $O(n)$ time.

Perhaps what would help you would be to learn about models of computation: Turing machines, RAM model, transdichotomous model. Many algorithm textbooks start with a discussion of how running time is computed (which is implicitly a model of computation), which would be a good place to start.

# Answer
> 0 votes
The computational model is implicit in the question: the basic operation is the $=k \\,?$ query, and taken as the unit. Whatever any actual implementation.

In fact, you don't evaluate a time-complexity, but a query-complexity. Just like when you rate a sorting algorithm based solely on the number of comparisons.

---
Tags: algorithms, complexity-theory, time-complexity, turing-machines, algorithm-analysis
---


# Question
Title: How to store set of long char strings to search for long char string key
I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key. What is the best algorithm to store the set and to search for a match?

# Answer
> 1 votes
A hash-table seems a good option. As the keys are long, collisions should be minimized. So don't fear to be generous on the number of buckets (low fill factor).

Unless your strings have long prefixes in common, a sequential search among the colliding strings will not be very costly (early termination in case of mismatch).

If there are long common prefixes, you can do the comparison backward from the end, or even from... the middle.

# Answer
> 0 votes
One approach is to use a suffix array (or suffix tree). That allows very fast searching for a match.

Given multiple words, there is a standard way to compute a suffix array (or suffix tree) associated with them: concatenate them, separated by some separator. For instance, if the words are APPLE, CAT, and DOG, you obtain the string APPLE\\$CAT\\$DOG\\$. Then, compute the suffix array/tree of that single long string.

# Answer
> 0 votes
One solution that pops to my mind is to do a hash on the strings, store the hashes in some efficient tree and the hits as a list. A suitable hash algorithm might decrease the number of actual string searches. Additionally given a good hash algorithm you might only need to check a few chars.

On second thought, there are two further things to consider when selecting algorithm.

1. What is the balance between searching, adding and deleting? I assumed that searching is a lot more common that adding/deleting.
2. Where does the strings differ? If they in average all are about the same length and all start with a few hundred characters the same in the beginning it might influence your choice.

---
Tags: search-algorithms
---


# Question
Title: Can a total programming language be Turing-complete?
I've seen two answers to this:

Wikipedia says no:

> These restrictions mean that total functional programming is not Turing-complete.

And the Wikipedia article cites D.A. Turner as the coiner of "total functional programming," and Turner says on page 755 of Total Functional Programming:

> There are two obvious disadvantages of total functional programming
>
> 1. Our programming language is no longer Turing complete
> 2. If all programs terminate, how do we write an operating system?

But Conor McBride says total programming languages *can* be Turing-complete:

> Now represent the semantics of Turing machines as coinductive processes and review your hasty and inaccurate repetition of the common falsehood that totality prevents Turing-completeness. You exactly get to say “we know how to run it for as long as we’re willing to wait, but we can’t promise you it will stop”, which is both the truth, and exactly the deal when you work in a partial language. The only difference is that when you promise something does work, you’re believable. The expressive weakness is on the partial side.

Turner had indeed thought about codata, and it plays a big role in their article re problem (2), but they don't seem to think codata helps with (1).

Would an answer to McBride's Retort be something like:

> Re "Now represent the semantics of Turing machines as coinductive processes ..." A Universal Turing Machine won't halt (if executing a program with an infinite loop), but a copgram will always halt until someone asks it to compute some more: to actually do computation for infinite time rather than just *representing* an infinite computation requires non-termination.

# Answer
> 7 votes
I'm pretty sure McBride isn't claiming that a total programming language can be Turing complete, just that it's a useless distinction in practice. You can take any program in a partial language and replace all not-provably-terminating loops with loops that run at most $2^{128}$ times, and the result is theoretically different but not observably different.

> You exactly get to say “we know how to run it for as long as we’re willing to wait, but we can’t promise you it will stop”, which is \[...\] exactly the deal when you work in a partial language.

I.e. maximum run times are bounded in the real world.

> The only difference is that when you promise something does work, you’re believable. The expressive weakness is on the partial side.

I.e. there's an expressivity tradeoff in using total vs partial languages, but the expressive advantage of total languages is useful in practice, while the theoretical expressive advantage of partial languages has no practical consequence.

---

Edit: In response to OP's comment, I think ruakh's comment is correct. McBride is implicitly suggesting that a better notion of completeness ought to not only replace Turing completeness as the de facto standard for real-world languages, but also take the name of Turing completeness and the brand identity associated with it, because it's more deserving of it. Maybe it would be more accurate to say he thinks the better notion of completeness ought to have been called Turing completeness from the beginning. It matters because the perception that total languages are deficient in some practical way, due to their lack of Turing completeness, may have actually hindered their real-world adoption.

# Answer
> 5 votes
A rhetorical question to keep in mind: would anyone take you seriously if you said ZFC is "not Turing complete" and therefore insufficient to express the algorithms that we write in mainstream programming languages?

First, what is the usual argument about total languages? The reasoning is as follows:

1. In a total language, the function type $A → B$ classifies only1 the functions that are somehow able to be verified total.
2. Any feasible verifier is going to reject some actual total definitions.
3. Therefore, $A → B$ does not contain all Turing-computable, total functions from $A$ to $B$.

This reasoning is correct. However, what is *not* correct is the further assumption that to write a program accepts an $A$ and produces a $B$, it must be recognized by the system as a (total) function $A → B$. Certainly the *total* part is not the case in mainstream programming languages, because there $A → B$ means some class of *partial* functions from $A$ to $B$.

So, are total languages incapable of representing partial functions? **No**. There are potentially many ways to do it. One of the fancier ways is to define the free ω-complete partial order $A\_⊥$ over a type $A$. Then the *total* functions $A → B\_⊥$ act much like the *partial* functions from $A$ to $B$ from current (eagerly evaluated) programming languages.

From a practical perspective, this $A\_⊥$ is not really very different from the previous coinductive definitions of a 'partiality monad.' The actual differences I can think of are:

1. The quotient inductive-inductive type (QIIT) would be a lot slower in certain scenarios, because it is based around representing successive approximations as $ℕ → A\_⊥$ (note the similarity to emulating a partial recursive function using "fuel"). With the coinductive type, if you observe a value and get $\mathsf{later}\ x$, then $x$ is a value that represents something closer to the answer. The analogue of this with the QIIT is trying $f\ 0$ and getting $⊥$, so you need to try $f\ 1$, but there is no work shared between $f\ 0$ and $f\ 1$, it just restarts from the beginning.
2. The quotienting ensures that people can't quibble about the type "not really" representing partial functions, but something else. I think this might be the reason that people reject the coinductive version. You can observe how long its taking, and stop running at some point, so it's "not really" modelling partial functions, and therefore "not really" Turing complete. This is the reason why it has its advantages in #1, though.

So, even total languages without the features needed to faithfully represent the more 'topological' aspects of partial recursive functions have at least one way of representing *practical* aspects of them. If your 'main program' is allowed to be a total function of type $A → B\_⊥$, with the proviso that it will (somehow) just be executed similarly to a partial function in a normal programming language, then there essentially aren't any $A$-to-$B$ programs that we genuinely can't express in this total language.

What does our argument above actually show in this light? That there are partial functions, i.e. total functions $f\_⊥ : A → B\_⊥$ that 'actually' converge to a well-defined value on every input, but we cannot exhibit corresponding total functions $f : A → B$, and prove that $f\_⊥\ x$ converges to $f\ x$. But, this is also true of, say, ZFC (hence the earlier rhetorical question), the mathematical system often considered to underlie all our mathematical reasoning, including about programming. Some of the details differ a bit,2 but the discrepancy still exists.

And what is the limitation of not being able to recognize some actually total functions as such? It is *good* to be able to show that large parts of our program are (more) genuine total functions. But, if that is impossible or infeasible, we are not worse off by only recognizing them as an encoding of partial functions, so long as we are still allowed to execute partial functions as programs. As McBride says, we are actually more honest in distinguishing recognizably total functions from partial functions, which most languages don't do. Another major use for total function is that they make sense to use in dependently typed languages for calculations that happen (and must terminate) during type checking, and we can't just use partial functions for those purposes. But most 'Turing complete' languages *also* don't let you do this. Many don't have anything like this *period*, and at best you usually get a stilted total language to program in at the type level, rather than one that has comparable convenience to the value level.

There are *engineering* questions to be considered. For instance, neither the QIIT nor the codata solution seem like the ideal encoding from a performance perspective. It's possible (something like) the QIIT is actually not as bad as I made it seem, if the runtime executor can somehow pass it a fake value that makes a 'limit' actually run with infinite "fuel," and never have to restart from scratch. That'd take care, though, and probably still have overhead. These are questions about efficiency of the representation of partial functions, though, not whether or not they *can* be represented.

---

1: For the purposes of this answer, where a programmer would care what functions they are able to write syntactically and get accepted by the language. The fact that there are mathematical models of the total language where the semantics of $A → B$ includes things that are not the image of any syntax doesn't help them write the missing programs as total functions.

2: E.G. you might be able to define non-computable ZFC functions that 'actually' correspond to converging partial recursive functions, but not prove that the partial recursive function converges to the values of the non-computable function. Whereas in a total programming languages, the functions are all expected to be computable, so you'd be stopped at the step of defining the corresponding function, rather than the proof that the function is computable.

# Answer
> 3 votes
I'm inclined to disagree with McBride here, for the simple reason that while you can express program semantics totally via coinduction, it is not enough to solve the halting problem for the object language (because you would need to run the coinductive trace to exhaustion, which of course may be infinite).

---

I think he has an important point, though: In functional programming, we often conflate *divergence* of a program with the mathematical meaning of *partiality* of a function.

Consider an evaluation function of an operational semantics `eval : term -> value`, returning the value whenever the expression halts. `eval` is a partial function, undefined on inputs that diverge, because then it diverges itself and never produces a value.

In some sense, divergence in the *object language* is lumped into partiality of the *meta language*.

That is a problem in mathematics, because you can never say "give me the value `v` of `e`", because that value does not always exist. If you prove theorems about `v`, you better be sure that the `v` in question actually exists. So now you have got to figure out what the *domain* of `eval` is. At best, `eval` is written in a way that it loops *only* when the inputs `e` diverge! And now you need two artefacts: `eval` as well as the "ground truth" semantics that tells you when `e` diverges; that's exactly when `v := eval e` is undefined. Well, hopefully. That's what you have to prove about `eval`.

Note that the halting problem doesn't have anything to do with it since we are determining divergence of an object program in the meta language, math.

Traditional denotational semantics solves this problem by returning a distinct element ⊥ when `e` diverges. The main point is that this yields a total function! Alas, the clever use of topology means that the naive translation into a program (denotational semantics *look* like definitional interpreters, after all!) simply loops on diverging inputs. Nevertheless, it is a mathematically sound and thus total definition.

I think the confusion of divergence and partiality presumably stems from the fact that traditionally, ⊥ is a *partial* element in the underlying approximation order, which means there are (many) other elements `d` that are strictly larger than ⊥, while for converging `e` what you get back is a *total* element, i.e., one that does not have a `d` that is strictly larger. At some point, we seem to have identified "`eval e` returns a partial element in some approximation order in the meta language" with "`eval` is a partial function, and undefined for `e`", with "`e` diverges".

---

But since at least a decade, Xavier Leroy (perhaps among others? Not exactly my area of expertise, I'm afraid) popularised a *coinductive* definition of the operational semantics. I find these slides quite approachable. He defines Capretta's coinductive `delay` monad

and then he asks

Yes, we can, as he shows us, by only doing small, incremental steps before each `now` or `later` constructor (productivity). That is quite like a trace produced by a small-step operational semantics; indeed the type of potentially infinite traces can be regarded as a concretisation/elaboration of the `delay` type. A diverging program would simply produce an infinite sequence of `later (later ( ... ))`, a well-defined mathematical object.

Now that we have at our hands a function definition of a Turing-complete programming language's semantics that is *totally defined* as a mathematical function, we can reason about it in proofs and theorem provers such as Coq.

All this *does not* imply that there is a total (in the unfortunate sense that it diverges nowhere) ~~function~~ program `halts : term -> bool` that we can define in terms of `eval`; for that we'd need some worker function that keeps on eating `later` constructors from the result of `eval` until it finds a `now`; and that might take an infinite amount of time (when a `now` never happens). Of course, such a definition will not yield a total definition either, because it will not be guarded recursive in the `delay (option term)`, so you wouldn't be able to define `halts` in the total fragment of Coq.

---
Tags: turing-completeness, coinduction
---


# Question
Title: Find the asymptotic bound for the recurrence relation: $T(n) = T(\sqrt{n}) + 5n$
I've tried to expand the recursion:

$$T(n) = T(n^{\frac{1}{2}}) + 5n = T(n^{\frac{1}{4}}) + 5(n^{\frac{1}{2}} + n) = T(n^{\frac{1}{8}}) + 5(n^{\frac{1}{4}} + n^{\frac{1}{2}} + n)$$

We have a total of $\lfloor\log\_2(n)\rfloor + 1$ elements in the recursion. So we can easily find an upper bound: $$T(n) = O(n\cdot \log\_2(n))$$

The thing is, I'm not sure it's a tight upper bound. More over, I haven't been able to reach a tight lower bound from the recursion. I've tried to, but I didn't get to the same assymptotic bound I've found above.

Any help would be appreciated.

# Answer
> 2 votes
Taking the square root of $n$ halves the number of bits, so you indeed halve that number $\lg n$ times before the iterated square root falls below some predefined constant (say $4$).

Now we can write

$$n+\sqrt n+\sqrt\[4\]n+\sqrt\[8\]n+\cdots\<n+\sqrt n+\sqrt n+\sqrt n+\cdots=n+\sqrt n\lg n,$$ which is $O(n)$.

---

**Justification:**

With $n=m^2$, $$\sqrt n\lg n\le n$$

becomes $$2m\lg m\le m^2$$ or $$2\lg m\le m,$$

which is true as of $m=4$.

# Answer
> 0 votes
You can use induction to show that $T(n) = O(n)$.

More concretely, try to prove using induction that you can find a $c\in \mathbb{R}^+$ and $n\_0\in \mathbb{N}$ such that for all $n\>n\_0$, it will hold that $T(n) \< cn$.

Basically, substituting this in the induction will reduce your recurrent formula into a simple equation that you will need to solve to find the suitable constants $c$ and $n\_0$.

---

**Hint:** try picking $n\_0\>4$

# Answer
> 0 votes
Dropping the factor $5$ and reducing by $S(n):=\dfrac{T(n)}{5n}$, and with $S(10)=0$ (arbitrarily):

$$S(100)=\frac{S(10)}{10}+1=1$$ $$S(10000)=\frac{S(100)}{100}+1=1.01$$ $$S(100000000)=\frac{S(10000)}{10000}+1=1.000101$$ $$S(10000000000000000)=\frac{S(100000000)}{100000000}+1=1.00000001000101$$

It is clear that $S(n)$ gets closer and closer to $1$.

$$1\<S(n)\<(1+\epsilon)$$ where $\epsilon$ is a constant as small as you want, and $n\>n\_0$, giving

$$5n\<T(n)\<5(1+\epsilon)n.$$

# Answer
> 0 votes
We want to find, $T(n) = T(\sqrt{n}) + 5n$

Assume $T(\epsilon) = c \> 1$, $\epsilon \> 1$ .

So $T(n) = T(\epsilon^{2k}) \\ = c + 5(\epsilon^2 + \epsilon^4 + \cdots + \epsilon^{2k}) \\ \< c + 5((k-1)\epsilon^{2(k-1)} + \epsilon^{2k})\\ = c + 5 (o(\epsilon^{2k}) + \epsilon^{2k}) = O(5n)$

# Answer
> 0 votes
Hint.

$$ T\left(2^{\log\_2 n}\right) = T\left(2^{\frac 12\log\_2 n}\right)+5n $$

or recasting

$$ R(z) = R\left(\frac z2\right)+5\cdot 2^z $$

and recasting again

$$ C(m) = C(m-1) + 5\cdot 2^{2^m} $$

and after solving, backwards...

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: How do I solve this recurrence equation?
I have to express the solution of the recurrence equation T(n) = T(an) + n where a is a constant, 0 \< a \< 1, in terms of θ using the iteration method. I am unsure of how I calculate the cost of each level and the number of levels because of the constant a.

# Answer
To resolve $$T(n)=T(\tilde{a}n)+n$$

you can apply the Master Theorem(https://en.wikipedia.org/wiki/Master\_theorem\_(analysis\_of\_algorithms)):

the recurrence: \begin{equation} T(n) = \begin{cases} a T(n / b) + f(n) & n \> 1 \\ T\_1 & n = 1 \end{cases} \end{equation} with constants $a \geq 1$, (b \> 1), the function (f(n) \> 0), with constants $ \alpha = \log\_b a $ has the solution:: \begin{equation\*} T(n) = \begin{cases} \Theta(n^{\alpha}) & \text{\\(f(n) = O(n^c)\\) para \\(c \< \alpha\\)} \\ \Theta(n^{\alpha}) & \text{\\(f(n) = \Theta(n^{\alpha} \log^\beta n)\\) con \\(\beta \< -1\\)} \\ \Theta(n^{\alpha} \log \log n) & \text{\\(f(n) = \Theta(n^{\alpha} \log^\beta n)\\) con \\(\beta = -1\\)} \\ \Theta(n^{\alpha} \log^{\beta + 1} n) & \text{\\(f(n) = \Theta(n^{\alpha} \log^\beta n)\\) with \\(\beta \> -1\\)} \\ \Theta(f(n)) & \text{\\(f(n) = \Omega(n^c)\\) with \\(c \> \alpha\\) y \\(a f(n / b) \< k f(n)\\)}\\ &\text{for \\(n\\) large with \\(k \< 1\\)} \end{cases} \end{equation\*} in our case: $a=1$, $b=\frac{1}{\tilde{a}}$ and $f(n)=n$ $\Rightarrow \alpha=0$

so \begin{aligned} T(n)&=\Theta(f(n))\\ &=\Theta(n)\\ \end{aligned} otherwise, as it says Yves Daoust:

\begin{aligned} T(n)&=T(\tilde{a}n)+n\\ &=(T(\tilde{a}^2n)+\tilde{a}n)+n\\ &=((T(\tilde{a}^3n)+\tilde{a}^2n)+\tilde{a}n+n)\\ &\vdots\\ &\text{notice that we have a polynomial of n}\\ &=T(\tilde{a}^m n)+ \Theta(n)\\ \end{aligned} where, for finite m (when does the recursion stop?) $$T(n)=\Theta(n)$$ I suppose that for that m $T(\tilde{a}^m\cdot n)$ it has a constant cost (the base case, as Yves says).

The base case is important when defining recurrence!

to do it exactly you must calculate the sum of the m terms:

\begin{aligned} T(n)&=((T(\tilde{a}^3n)+\tilde{a}^2n)+\tilde{a}n+n)\\ &=T(\tilde{a}^m n)+ n\sum\_{i=0}^{m-1}(\tilde{a}^i)\\ &=T(\tilde{a}^m n)+n\frac{1-\tilde{a}^m}{1-\tilde{a}}\\ \end{aligned}
> 2 votes

# Answer
**Hint:**

$$T(n)=T(an)+n=T(a^2n)+an+n=T(a^3n)+a^2n+an+n=\cdots$$

You can stop the expansion when $a^kn=1$ and use the geometric sum formula.
> 0 votes

# Answer
Hint.

Making $n = a^m$ we have

$$ T(a^m) = T(a^{m+1})+a^m $$

or recasting

$$ R(m+1) = R(m) - a^m $$

etc.
> 0 votes

---
Tags: algorithm-analysis, asymptotics, recurrence-relation
---


title: Constrained precedence parsing

text:
# Question
Title: Constrained precedence parsing
This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem?

The setup is as follows: we are given $n$ operator nodes $x\ast\_1 x\ast\_2\dots\ast\_n x$ connecting $n+1$ leaves (whose identity is not important, here denoted by $x$) and the goal is to construct a valid parenthesization of the operators, i.e. a tree with the $\ast\_i$ at internal nodes and with $x$ at the leaves. The operators may not be reordered but they can be reassociated. This is subject to two constraints:

1. Each operator $\ast\_i$ has a (left associative) precedence $p\_i$, meaning that we prefer $(a\ast\_ib)\ast\_jc$ over $a\ast\_i(b\ast\_jc)$ if $p\_i\le p\_j$.
2. Each operator $\ast\_i$ may require that its left or right argument is or is not a leaf. (That is, there are four combinations of "left leaf, right leaf", "left leaf, right non-leaf" etc and each operator specifies a subset of these four possibilities. I will abbreviate these with $x$ for "leaf" and $T$ for non-leaf subtree, so an operator specification is a subset of $\\{xx,xT,Tx,TT\\}$.) A valid solution must satisfy the constraints of all operators.

For example: suppose $\ast\_1$ has constraint $\\{xT\\}$ and $\ast\_2$ has constraint $\\{xx,xT\\}$, and they both have precedence $1$. Of the two possible trees $(x\ast\_1 x)\ast\_2 x$ and $x\ast\_1 (x\ast\_2 x)$, the precedence prefers the first one, but the first tree violates the conditions on both nodes, as $\ast\_1$ sees configuration $xx$ and $\ast\_2$ sees $Tx$ and neither of these is allowed. The second tree has $xT$ for $\ast\_1$ and $xx$ for $\ast\_2$ so this is a valid solution (and the best solution since it is the only one).

With only condition (1), this is a straightforward precedence parsing problem and linear time solutions exist. With condition (2) however, it becomes a constraint satisfaction problem and it would not be surprising to me if linear time solutions no longer exist. A brute force solution would enumerate all trees and hence would be exponential time, but I think it is likely not NP complete because of the locality and linearity of the constraints: some kind of dynamic programming is likely possible.

*Note: there is also a question here regarding what condition (1) even means in the presence of constraints. It specifies a preference ordering on individual tree rotations but what if the rotation is not valid? Is there a way to lift (1) to a sensible ordering on entire trees which reduces to standard precedence parsing when the constraints are trivial?*

# Answer
Here's a dynamic programming solution to the problem. To address the aside, we score candidate solutions by the number of edges between two internal nodes that represent a violated precedence ordering (so for example if $+$ has lower precedence than $\times$ then $(1+2)+(3\times 4)$ has a cost of 0 and $1+((2+3)\times 4)$ has a cost of 1 because of the $(2+3)\times 4$ subtree which violates precedence). In the absence of constraints, it is always possible to get cost 0 by performing tree rotations on any violated edges, so this reduces to standard precedence parsing in that case. The goal is to return a tree with minimal cost among those that satisfy the constraints.

The subproblem we use in the recursion is to give an optimal tree with designated root $\ast\_i$. We evaluate the configuration of $\ast\_i$ right away: the left side is a leaf iff $i=1$ and the right side is a leaf iff $i=n$. If this configuration is not legal then there are no solutions with $\ast\_i$ at the root.

Otherwise, if the left side is a leaf then it is feasible with cost 0, else we consider each $\ast\_j$ for $j\<i$ as a possible root for the left subtree, and recursively get an optimal subtree, if one exists, along with its cost. The total cost contribution is then this cost, plus 1 if $p\_j\>p\_i$. Taking the min over these gives us the best left subtree (or fail if no solutions exist).

We can do the same thing for the right subtree: If it is a leaf then we are done, and otherwise we take the min over the cost of all choices of root. The total cost of the tree itself is the sum of left and right costs.

As a mathematical expression, we can say that $\mathsf{cost}(a,b,i)$ calculates the cost of the optimal tree on the substring $x\ast\_a x\ast\_{a+1} x\dots x \ast\_b x$ of the original expression, rooted at $\ast\_i$:

$$\begin{align} \mathsf{cost}(a,b,i):={} &\mbox{if }(i=a,i=b)\in\mathsf{config}(\ast\_i)\\ &\mbox{then }\\ &\quad\phantom{{}+{}}\left(\mbox{if }i=a\mbox{ then }0\mbox{ else}\min\_{a\le j\<i}\left(\mathsf{cost}(a,i-1,j)+\[p\_j\>p\_i\]\right)\right)\\ &\quad{{}+{}}\left(\mbox{if }i=b\mbox{ then }0\mbox{ else}\min\_{i\<j\le b}\left(\mathsf{cost}(i+1,b,j)+\[p\_i\le p\_j\]\right)\right)\\ &\mbox{else }\infty\\ \end{align}$$

The optimal tree is just the min over all possible roots:

$$\mathsf{OPT}:=\mbox{if }n=0\mbox{ then }0\mbox{ else}\min\_{1\le i\le n}\mathsf{cost}(1,n,i)$$

The total number of subproblems is $O(n^3)$ since we have one for each triple $1\le a\le i\le b\le n$, and the cost of each subproblem is $O(n)$ since we have to do a min over $a,\dots, b$. So the total cost is $O(n^4)$, which is pretty bad for a parsing algorithm but still polynomial time.
> 2 votes

---
Tags: algorithms, complexity-theory, dynamic-programming, parsers
---


# Question
Title: How do I make a stable sorting algorithm that uses an unstable algorithm as a subroutine
The stable algorithm has to run in O(n) time and must call the following unstable algorithm at least once.

EDIT: Calling unstablesort() is free (costs 0 operations).

```
def unstablesort(l):
    return selectionsort(shuffled(l)) # shuffled(l) returns list l randomized

```

This is apparently an easy question but frankly I don't know where to start.

# Answer
**Hint:**

Unstable sorting shuffles the data in an unrecoverable way (because identical keys are... identical), so you must somehow save the initial position information.
> 2 votes

---
Tags: algorithms, sorting
---