# Question
Title: How likely is for a pseudorandom number generator to generate a long sequence of similar numbers?
How likely is for a pseudorandom number generator to generate a long sequence of similar numbers? "Similar numbers" could be same numbers, or numbers from a given range.

For example, if we consider PRNG algorithm being a simple counter counting from 0 tom MAX, the distribution is uniform and there's a guarantee of not repeating numbers in a sequence. So, not repeating numbers does not break uniformness. But probably it breaks randomness, does it? To what extent? If so, does it mean, that the better the algorithm, the less guarantee we have to not generate similar numbers in sequence?

I'm particularly interested in the answers regarding Mersenne Twister as a most popular PRNG in programming languages implementations. It'd also be great to know how things are in operating systems' crypto-secure PRNGs – Yarrow (macOS), Fortuna (FreeBSD) or ChaCha20 (Linux).

# Answer
Given the same internal state, a pseudorandom number generator (PRNG) must produce the same output. PRNGs have a period: if you run one long enough, it will start repeating the same sequence. (For good PRNGs, the period is long enough that you don't have to worry about it.) For very simple PRNGs such as a simple linear congruent generator of the form

new number = old number $\times$ constant $+$ another constant

the state is just the previous value. In that case, it's impossible to generate the same number twice in a row unless the constants are poorly chosen and the PRNG gets stuck in a short loop. (This has been known to happen, and you don't want to use such a PRNG!) However, you will sometimes generate numbers that are similar (not the same) in various respects. The tests that vonbrand's answer mentioned are designed to verify that such similarities occur with relative frequencies that are close to what should be found if each number had equal probability.

The most common version of a Mersenne Twister (MT) has a 624$\times$32-bit internal state. If the MT is being used to generate 32-bit numbers, it uses up 32 bits of its state each time it outputs a number, and when all 624 internal state words have been used, the MT generates a new 624-word state from its old state. (The number that is output is not the same as the state word that's used; it's a function of the state word, though.) I suppose an MT could theoretically sometimes output the same number in two successive calls on the MT, although I am not certain that that is possible. I think that would require that two successive words in the generated 624-word state were identical (unless it happened because you seeded the MT with a bad state that included the same number multiple times). I don't know whether this is possible; I suspect that it is. But it should be very, very, very rare in the sense that the relative frequency of successive duplicates across the entire period of MT should be small.

For 32-bit numbers, ideally, the relative frequency of choosing the same number twice in a row should be $1/2^{32} \times 1/2^{32} = 2^{-64}$. That would be very rare. On the other hand, the period of the widely-used version of MT, versions of MT19937, is $2^{19937}-1$. This is the number of successive pairs that could, theoretically, contain duplicates, and $2^{-64} \times 2^{19937}-1 = 2^{19873}$ is a large number. However, any use of MT will only make use of a small fraction of the period. At this point, if I wanted to know how common or rare duplicates are, I would look at the test in TestU01 or another test suite that checks the frequency of duplicates. I wouldn't test the entire period, though, unless I had a lot of computing power and was patient. I don't know whether it's possible to assess the frequency of duplicates analytically from the design of MT19937.

I listed some other relevant resources in this answer and said more about Mersenne Twisters in this answer.
> 3 votes

# Answer
The likelihood of, e.g. a string "000000" should be *exactly the same* as every other six-bit strings, i.e. $2^{-6}$ for each. To see if a particular PRNG satisfies such properties requires either hairy math (see for example the exhaustive discussion of congruential generators in Knuth's "Seminumerical Algorithms", it has a chapter on random numbers, other generators like the Mersenne twister you mention have their own analysis) and lots of computer time, or just run a battery of statistical tests (see for example the discussion on random.org's generator, Dwyyer and Wiliams "Testing Random Number Generators", or Cook's "Testing a random number generator"). Cryptographically strong random number generators have other, more stringent requirements (even knowing how the generator works, and a very long history of previous results, it should be computationally unfeasible to predict the next output).
> 1 votes

# Answer
Define what you mean by similar (any way you like).

For a given, fixed x let the probability that a random number y is similar to x be p. Then the probability that n consecutive random numbers $y\_1$ to $y\_n$ are all similar to x is $p^n$.

Now let the numbers x and $y\_1$ to $y\_n$ be numbers generated by a PRNG. Then either the probability that $y\_1$ to $y\_n$ are all similar to x is $p^n$, or we found a statistical test that the PRNG fails.

(I was careful how to state this. The situation is different if x is not fixed. For example if x, y are similar if -0.1 \< x-y \< +0.1 then for some x (say 0.001) the probability that n other numbers are all similar to x can be as low as $0.1^n$, while for 0.1 ≤ x ≤ 0.9 the probability is $0.2^n$. The probability that *all* numbers are similar to each other is different again. And if I define "x and y are similar if the first digit is the same, but the second is different", then you can't have 11 similar numbers).
> 1 votes

---
Tags: randomness, pseudo-random-generators
---


# Question
Title: Does RAM get an indication of data size required
## Pre-information:

I'm sure someone has asked something along these lines, but no matter how I word it, I can't seem to find a definitive answer

## Question:

Does RAM get some kind of indication as to how much data the CPU requires or is there a set amount of data and if the CPU needs more, it needs to call again (and what is that set amount of data).

During a cache miss, the CPU will require at least a single cache line (32, 64 or 128 bytes). Does the CPU need to query RAM multiple times to get a single cache line (assuming the set amount is 8 bytes) or does the RAM return more data per call or does RAM have some way of being notified as to how much data is required?

I'm aware the CPU is most likely going to call more than just a single cache line to avoid the lengthy request from RAM if more data is needed in future from the same block of memory.

## Extra Points:

If you do know and have more information, the following extras would also interest me:

* If this is different depending on CPU make (generational differences can also be interesting but if you do add information about that, please skip similar generations)
* If this is different depending on RAM type
* How the CPU can request a different sized cache line or block size (only applies if RAM returns a fixed size that's the size of a block or cache line)
* Any other useful relevant information or resources for further reading

## Potential answer:

I seem to have found a clue to the answer when looking at the transfer rate of RAM, specifically where it indicates how to calculate the transfer rate from the specifications and from "DDR SDRAM prefetch architecture" which indicates how many 64 bit "blocks" can be requested per call to RAM (e.g. 8 for DDR3 and DDR4, 4 for DDR2 and 2 for DDR1)

# Answer
> 0 votes
In most modern hardware, main memory is more like a peripheral.

What I'm going to describe in what follows is Intel-esque PC-ish hardware, but it's very similar on other systems.

During initial booting, when the power is first applied, the CPU only has cache, firmware, and some memory-mapped I/O. One of the first jobs is to initialise an external piece of hardware traditionally known as the "memory controller" or "memory controller hub" (in PC hardware it's part of the northbridge), which communicates directly with RAM modules.

I say "RAM modules", because they are really like peripherals, as I said. The hardware asks the module how much memory is present, and also negotiate the details of the protocol they will use to transfer data to and from main memory.

Like other modern peripherals, modern RAM modules can burst reads and writes, that is, they can read and write a larger "block" of memory using one transfer operation. So even if the "last" level of cache operates with the same cache line size as lower-level caches, it can transfer larger blocks of data to and from RAM than that.

This is a useful optimisation when performing operations like linear scans through a block of memory. Some combination of the CPU and cache controllers can detect this, and use that information to issue a prefetch from RAM.

# Answer
> 2 votes
RAM just gets requests for data to move to/from the CPU (really the MMU). Data is moved in units of cache lines.

# Answer
> 1 votes
Currently, cache sizes are usually so big that more than one transfer from RAM to cache is needed to completely load a cache line. But reading from RAM takes time for the RAM to receive the address of the data to be read, and then time for the actual transfer, and asking RAM to perform say four transfers in a row is much faster than accessing four random memory locations.

Some processors have a feature that allows them to tell RAM in which order to transfer different parts of a cache line. Say there are four transfers needed to fill a cache line, then you would like to load the quarter cache line first that is actually needed (and then fill the rest).

It would be possible to only partially fill a cache line (and proceed filling a different cache line instead of completely filling the first one).

---
Tags: memory-management, cpu-cache, memory-access
---


# Question
Title: why don't we use machines with random access memory as our basic model of computation?
Turing machines are perhaps the most popular model of computation for theoretical computer science. Turing machines don't have random access memory, since we can only do a read where the slider is currently located.

This seem unwieldy to me. Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

# Answer
> 63 votes
> Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

The short answer is that this model is actually more complicated to describe and prove things about. "Jumping" from one place in memory to another is a more complex operation. Note that it requires:

* Reading an address (requires that we define how the address is written on the tape)
* Jumping to where that address says on the tape

Alternatively I'm not sure what you have in mind by "register machine", but this also requires care. How large can the registers be? And the machine then has separate mechanisms for how it accesses/modifies the registers, and how it accesses/modifies main memory.

In sum, **it's a more complicated model** and Turing machines are easier to deal with.

However, the long answer is that theoretical computer scientists ***do*** use a model with random access memory, in real practice: it's called the **RAM (Random Access Machine) model**. The Turing machine is not considered to be a good model for so-called "fine-grained complexity" (e.g. whether a problem can be solved in $O(n^2)$ or $O(n)$ time), and so this requires more careful models. The RAM model is standard and perhaps, arguably, more accepted than the Turing machine as a model of how real computers work, despite being more complicated.

For example, we can show that for a Turing machine to decide if two strings are equal requires $O(n^2)$ time. But this of course does not hold in more accurate models of computation like the RAM model, where it will take $O(n)$. Therefore:

* If you just care about whether a problem can be solved at all (or whether it can be solved in polynomial time), Turing machines are considered sufficient.
* But if you care about exactly *how difficult* it is to solve, then you have to resort to a more complex model, such as RAMs.

# Answer
> 16 votes
But we do! Read Knuth's "The Art of Computer Programming" series, for one. Almost all of the books with "algorithms"somewhere in the title implicitly use the RAM model.

Different uses, different models.

# Answer
> 8 votes
Register machines *do* get used as a model of computation for parallel algorithms. (PRAM machine)

Having threads communicate with each other through shared the same way they do in real machines is presumably useful; If you're talking about parallel algorithms them you're presumably concerned about time complexity so you want a machine model that can do things with similar efficiency to real CPUs.

If you only care about something being computable *at all* in finite time, running on some finite number of threads greater than 1 is irrelevant, and as other answers point out, Turing vs. Register machine is also fine.

---

(A shared-tape parallel Turing machine sounds insane to me, and maybe you'd have a side-channel for communicating between TMs somehow other than via shared tape? Once you have the added complexity of parallelism, it presumably makes more sense to use a model of computation similar to what we use in real life, although cellular automata or other fundamentally parallel models of computation do exist.)

---

But yes, as you point out, idealized RAM machines as a theoretical model of computation are a thing, too, even for serial computation. (They're a class of "register machines"; in this context every memory location is a "register" (of unbounded size), not like real CPUs where registers are small fast storage separate from memory address space. If you're used to assembly language for real CPUs, this is not what you'd expect from the name.)

I don't know how common it is to use this model; presumably not rare when considering time complexity of algorithms?

# Answer
> 5 votes
If computation time is not an issue, it's possible to formulate a Turing machine algorithm which will find the Nth data location, for some arbitrary-length binary number N, following a particular marker. Plan on using half of the slots on the tape to hold bona fide data, and half to keep track of which location is active. To find the Nth location, first copy the marker to a spot just after the original. Assume for simplicity that one has an "X" in the marker spot before the a copy of the binary number of interest which is stored in little-endian fashion and a "Y" before the first location in the addressable range. Decrement the counter, and if it hadn't been zero, search for the "Y", and once it's found, replace the Y with some otherwise-unused symbol (e.g. Z) and replace the tag for the location to its right with Y. Then search back for the X, and repeat the procedure, decrementing the counter again and then moving the "Y" to the right. Once the counter hits zero, the location of the Y will mark the appropriate position on the tape, and if one searches left from there, one can find the leftmost Z and replace that with a Y in preparation for the next random-access operation.

Such an approach would be horrendously slow, but if one is merely interested in determining what kinds of tasks can be accomplished *at all* in finite time, the fact that an operation requires many orders of magnitude more steps than would be required in a RAM-based machine would be a non-issue.

# Answer
> 3 votes
I'm self-taught in most fields that pertain to programming, software engineering, computer science, and electronic engineering. I have interests that range from 3D Graphics Programming, 3D Game Engine design, hardware emulation, compiler design, os design, hardware design down to the circuitry and from my research and studies I think the best way to answer this is that it comes down to how hardware is actually built and its constraints.

In mathematics, we have notations of values that exceed the limitations of physical hardware. Random Access Memory is used in many computer models, however, we have to look at the nature of what a Turing Machine is and how we use it to perform mathematical computations. We can represent integers and reals, but there are always the underlying issues of precision, truncation, under and overflow of values.

---

You had stated:

> Turing machines are perhaps the most popular model of computation for theoretical computer science. Turing machines don't have random access memory, since we can only do a read where the slider is currently located.
>
> This seem unwieldy to me.

Then you had asked:

> Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

We need to look at the definition of what a Turing Machine is:

> A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
>
> provided by: wikipedia

Do yourself a favor and read over the wiki page thoroughly and consult other resources as this has widely been used as the de facto model for most modern computers.

---

To answer your question you should read the details from the wiki page about how a CPU acts like a Turing Machine and how most programming languages are Turing Complete. It comes down to the layers of abstraction which is in contrast to a what a Turing Machine is while being an Abstract model.

In a computer layout design typically the CPU the Turning Machine has a finite state of registers with finite register sizes and bus widths along with a finite set of instructions that can be performed. The dynamic random access memory modules are normally connected to but separated from the CPU. Internally and at each abstraction layer, a computational device is a finite state machine independently but when combined to build a more complex machine, theoretically can perform an infinite amount of instructions.

If you were to use either a breadboard with integrated circuits, an FPGA, or even a simulator program such as Logisim and start building a basic CPU with its data paths, buses, control lines, etc. You will end up seeing the limitations of the hardware when you start to see the connections between the design of the logic gates, the component layouts, and how an ISA (Instruction Set Architecture) is designed to produce a Turing Machine.

When you begin to understand how an Assembly Language is constructed from an ISA and is used to simplify the ability to talk to the machine in its machine language you will then be able to build higher levels and layers of abstractions on top of it such as the C family of languages, Compilers, Operating Systems and such. Then you will end up with more advanced topics such as compiler theory and Operating System designs.

It pretty much comes down to two main things, finite state machines acting as Turing Machines and the layers of Abstraction. There are two viewpoints that this can be seen from, bottom-up and top-down. Looking from the hardware up to the software or looking down from the software to the hardware and understanding how it works where they meet in the middle. This is where most of the theory is applied. In the end, it is basically a hierarchical design where it is one system built on top of another.

A Turing Machine in itself doesn't require random access memory, however, many Turing Machines are connected to and work with random access models in tandem. They are two separate things that I believe you are trying to compare... Apples and Oranges, yes they are both fruit, but far from the same. Yet, we can use both of them together to make a fruit salad!

Basically a CPU is a Turing Machine that has Registers with a finite set of states, but in a computer system, the CPU is connected to Memory Modules that are Random Access through the system bus or a bus controller. Without the two you wouldn't have a computer system. They talk and communicate with each other to perform a set of instructions based on the current or previous instruction that has already been executed, in memory ready to be executed, and so on...

# Answer
> 2 votes
Because this is a model for finite state machines, not for Turing-equivalent computing, at least in the normal sense where you have a finite memory unit size and address size. On the other hand if you allow these to be infinite, you end up with a model of computing where lots of things artificially take O(1) space or time that's not useful for reasoning about real-world efficiency. Reconciling these issues is possible; the transdichotomous model is one way to do so.

Turing machines and other models are in a sense "better" because they're simpler and the infinitude is only achievable via repetition of highly finite operations. If you want "arbitrary range addressing", you have to construct it yourself within the program rather than the model artificially giving it to you for free. In addition, the "infinite tape" idea at least makes some real-world sense in that you could (to the point of resource exhaustion) keep extending a finite tape on demand, whereas finding a way to cram infinitely many address bits into one storage unit is not happening (but the transdichotomous model, or at least some variant of it, can make this work by essentially saying you throw away your computer and make a bigger one if you run out of space for your problem).

# Answer
> 1 votes
> as our basic model of computation

Turing machines are used to study *computability* and *computational power*. They're essentially *not* used for studying the performance of real-world algorithms.

To determine whether a model of computation is as powerful as a random-access register machine, all you need to do is show that it's as powerful as a Turing machine (which is almost always ***much*** easier.)

Basically Turing machines are used because they **tend to make proofs a lot shorter**.

Consider that it's much easier to provide a mathematical formulation of how a Turing machine simulates a different type of Turing machine, than it is formulate how a register machine simulates a different type of register machine.

# Answer
> -1 votes
Turing invented the 'machine' purely to show, in the simplest possible way,

1)that mechanical computing was possible, and 2) that if a problem could not be solved by it, then it could not be solved.

Performance is irrelevant - no-one has ever built one, or ever will. But we can emulate it, and reason about it.

---
Tags: turing-machines
---


# Question
Title: Why is the complexity of BFS & DFS frequently written as O(V+E) vs. O(max(V,E))
Why is the complexity of BFS & DFS frequently written as O(V+E) vs. O(max(V,E)) when the 2 are equivalent?

I feel like the latter conveys more meaning and is more simplified, and we can more easily see that the time grows as a function of the number of vertices OR edges, whichever is greater, whereas the latter reads "the time grows as a function of the number of vertices AND edges"

# Answer
> 1 votes
While they are equivalent from a big-$O$ perspective, I think that the former is preferable as it directly connects with how the algorithms are implemented. To see this, let's consider fully connected graphs vs. graphs with multiple components, including vertices which are completely disconnected.

In order to cover the former, $O(E)$ is completely sufficient. $O(V)$ is not, as every edge must be traversed. For the latter case, one must also consider all the disconnected vertices, so one has an additional complexity of $O(V)$. Thus, together we have $O(V+E)$.

From an informative standpoint it's clearer that we need to process all edges and vertices. By taking $\max$ it would seem to imply that it's sufficient to look at just edges or vertices. This is often why when we have algorithms dealing with multiple parameters they're all explicitly spelled out - $O(m+n)$ vs $O(m + log n)$ for example, even if $m \> n$, because this matters; how does the algorithm behave if I change one of the parameters and leave the other untouched.

---
Tags: complexity-theory
---


# Question
Title: Disk scheduling algorithm - SCAN and C-SCAN
I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a mistake, but I want to be sure.

The example is the following:

> Description of SCAN: The disk arm starts at one end of the disk, and moves toward the other end, servicing requests until it gets to the other end of the disk, where the head movement is reversed and servicing continues.
>
> Suppose that the cylinder range goes from 0 to 199 and you have the following queue:
> 98, 183, 37, 122, 14, 124, 65, 67
> Head pointer: 53
>
> As seen in the image, the total head movement is of 208 cylinders

I don't understand why 208 cylinders. If I understand correctly, the head will start at 53 and then move to 0 (that's 53 cylinders), then the head will move up and the last service requested is at 183 (that's another 183 cylinders). So the total head movement should be 53 + 183 = 236.

The book also has an image and description of C-SCAN:

> C-SCAN moves the head from one end of the disk to the other, servicing requests along the way. When the head reaches the other end, however, it immediately returns to the beginning of the disk without servicing any requests on the return trip. The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list that wraps around from the ﬁnal cylinder to the ﬁrst one.

Using the same example, with C-SCAN the cylinder would start at 53, then move up to 199 (146 cylinder movements), then go to 0 (199 movements), and then the last request would be at 37 (37 cylinder movements). The total cylinder movements would be 146+199+37=382. My question here is, do we also have to count the cylinders when the head goes back to 0 since it isn't servicing any requests?

Note: This information was extracted from *Operating System Concepts with Java - 8th Edition by Silberschatz, Galvin, Gagne.* You can also find this part of the chapter here.

# Answer
> 3 votes
Here are the examples of various disk scheduling algorithms.

Yes you are correct in both the case. The author here has made mistake. For SCAN: The answer should be 236. For C-SCAN: The answer should be 146+37=183.(Note: The head movement when its not servicing any requests is not counted.) Refer the link, it gives a clear concept of how the different kinds of disk scheduling algorithms are used in practice.

# Answer
> 1 votes
I want to add "Why return trip in C-SCAN should not be counted?" Actually the objective behind calculating total head movement is to find the total time spent by read write head to serve the given request, which is proportional to total head displacement. When we move quickly from one end of the disk to other end, there is a displacement; but the time required is negligible(as no requests are served in between) and hence this displacement is ignored.

---
Tags: computer-architecture, scheduling
---


title: Mod 2 is primitive recursive

text:
# Question
Title: Mod 2 is primitive recursive
> Given a function E(x) which outputs 0 is x is even and 1 is x is odd, prove that this function is primitive recursive.

---

My attempt is as follows

$$ E(x) = x \mod 2$$ To show that any function is primitive recursive, it must be obtained by composition and recursion from the initial functions $s(x) = x + 1; n(x) = 0$ and $u\_i^n(x\_1,x\_2 \ldots x\_n) = x\_i$
We know that $$ E(0) = 0 $$ $$ E(x+1) = (E(x) + 1) \mod 2 $$ By using induction -
$$ E(n) = n \mod 2$$ Let $n = 0$ $$ E(0) = 0$$ which is easily shown to be primitive recursive since it is an initial function of the $PRC$ class.
Assuming that this is true for $n = k$. $$E(k) = k \mod 2$$ Taking $ n = k+1 $ $$ E(k+1) = (E(k) + 1)\mod 2 $$

But at this point, I do not know how to proceed.

# Answer
> 0 votes
Define a function $a(x)$ by primitive recursion as follows: $a(0) = s(0)$ and $a(x+1) = 0$. In particular, this function satisfies $a(0) = 1$ and $a(1) = 0$. Now we can define $E(x)$ by primitive recursion: $E(0) = 0$ and $E(x+1) = a(E(x))$. You can prove that $E(x)$ works by induction (left to you).

---
Tags: computability, primitive-recursion
---


# Question
Title: Finding recurrence relation for running time of an algorithm
I am pretty new to this, consider the following algorithm:

```
Calc_a(n):
    if n ==1: return 1
    else:
    sum = 0
    for i=1 to n-1:
        sum = sum + calc_a(i)
    return sum

```

So after running this algorithm a few times I see it basically finds the n'th element in a sequence defined by this recurrence relation:

$a\_n = \sum\_{i=1}^{n-1}a\_i $

I need to find the recurrence relation for this algorithm running time per input. Walk me through it :)

Lets define running time as $T(n)$.
So the base case n=1 is $O(1)$ (theta?), as we just return 1.
Then we iterate (n-1) times , each time performing addition and calling the function on the current index, this is where I get confused.
I know how to deal with loops and recursion individually, not together.

**My homework specifies that I should use constants rather than asymptotic notations. Does that means I should define the running time of Calc\_a(i) as some constant?**

How should I go about this?

\*** EDIT \****
The answer I've come up with:

$ T(n) = \begin{cases} 1, & \text{if $n = 1$} \\ \sum\_{i=1}^{n-1}( T(i) + B) & \text{else} \end{cases} $

For some constant B.

# Answer
> 1 votes
For starters, there are a few ways to prove recursive complexity. Some helpful notes can be found all over. For this problem, we can think about the *recursion tree*. The root of the tree is the `Calc_a(n)` call, and it's children are all $n-1$ nodes for each `Calc_a(i)` call initiated by the original `Calc_a(n)` call. For each of it's children, we can define the subtree rooted at them in the same manner. Our first step will be to determine how many nodes are in this tree.

Lets for some call `Calc_a(n)`, lets see how many times `Calc_a(i)` is called for some $i\<n$. This is the same as counting all `Calc_a(i)` nodes in the tree defined above. Let's first notice a pattern.

* `Calc_a(n-1)` is only called once, that is clear.
* `Calc_a(n-2)` will be called by the original `Calc_a(n)` call as well as the `Calc_a(n-1)`. **2 calls**
* What about `Calc_a(n-3)`? Well we have 1 from the original call, and we can see that there will be two calls from `Calc_a(n-1)`, and one more from `Calc_a(n-2)` **4 calls**
    + Why are there two calls from `Calc_a(i-1)`? Well, in the previous bullet point we see that for any $i$, `Calc_a(i-2)` will be called twice for every `Calc_a(n)`. We can use that logic here.
* `Calc_a(n-4)`? We have one from the original call. As we can see in the previous bullet point, there will be 4 resulting calls to `Calc_a(n-4)` from `Calc_a(n-1)`, 2 from `Calc_a(n-2)`, and 1 more from `Calc_a(n-3)` **8 calls**
    + Again we use the fact that the previous bullet point showed that there are 4 resulting calls to `Calc_a(i-3)` from any `Calc_a(i)` call.

We notice the pattern unfold that any `Calc_a(i)` is called twice as many times as `Calc_a(i+1)`. Therefore `Calc_a(i)` is called $2^{n-i-1}$ times.

$$\sum\_{i=1}^{n-1}2^{n-i-1}=\sum\_{i=0}^{n-2}2^{i}=2^{n-1}$$ (I'm not sure if you're expected to include the original `Calc_a(n)` call, if you are, just add 1)

## Proof Method 1

Now, as far as $T(n)$ goes, we can define it as $T(n)=f(n)+\sum\_{i=1}^{n-1}T(i)$ where $f(n)$ is the work done in the function *not including the recursive calls*. As I'm sure you can tell, this is just a constant, so each node in the work tree does constant work. So we've determined the number of nodes in the tree. This means that the total work of the tree is simply $T(n)\approxeq 2^{n-1}$ or $T(n)=\theta(2^{n-1})$.

You may be wondering why the sum doesn't contribute to the complexity. Well, we could look at the loop and include the sum, then $T(n)=f(n)+\sum\_{i=1}^{n-1}(g(i) + T(i))$ where $g(i)$ is the complexity of computing the sum from $T(i)$. However, we can just consider $g(i)$ as a constant as well, since most arithmetic operations can be theoretically considered constant time (this is definitely not always the case, but that is a whole nother topic). Because the constant complexity of the addition is dominated by the complexity of the accompanying $T(i)$ call, we arrive at the same complexity.

## Proof Method 2

A more formal method of proving this, and one that may be required (from my experience) on an exam or homework, is to use induction. Generally, the Method 1 above is useful for getting a guess on the complexity. Once you have a good guess, you use induction to prove it, as suggested in the comments below.

**Claim:** $T(n)=\theta(2^{n-1})$

**Base case:** $T(1)=1$ (we can also see that $T(2)=2$ and $T(3)=4$) (Notice we are counting the number of calls to `Calc_a()`

**Inductive step** \begin{align\*} T(n+1) & = f(n+1) + \sum\_{i=1}^n ( g(i) + T(i)) \\ & = f(n+1) + \sum\_{i=1}^{n-1} (g(i) + T(i)) + (T(n) + g(n)) \\ & = f(n+1) + T(n) - f(n)+ T(n) + g(n)\\ & = 2T(n) + g(n) \\ & \leq 2^n+c \quad \text{for some } c\geq g(n) \end{align\*} Where the last line follows from the inductive hypothesis and the fact that $g(n)$ is a constant i.e. $g(n)=O(1)$.

# Answer
> 1 votes
One general way to solve recurrences is to use generating functions. A good reference is Wilf's "generatingfunctionology". Define the generating function:

$\begin{equation\*} A(z) = \sum\_{n \ge 0} a\_{n + 1} z^n \end{equation\*}$

Write your recurrence with no index subtractions, multiply by $z^n$, sum over $n \ge 0$, recognize some sums:

$\begin{align\*} \sum\_{n \ge 0} a\_{n + 2} z^n &= \sum\_{n \ge 0} z^n \sum\_{0 \le k \le n} a\_{k + 1} \\ \frac{A(z) - a\_1}{z} &= \frac{A(z)}{1 - z} \end{align\*}$

The last is because:

$\begin{align\*} \sum\_{n \ge 0} z^n \sum\_{0 \le k \le n} a\_{k + 1} &= \left( \sum\_{n \ge 0} z^n \right) \cdot \left( \sum\_{n \ge 0} a\_n z^n \right) \\ &= \frac{1}{1 - z} \cdot A(z) \end{align\*}$

OK, now we have an equation for $A(z)$, solve that one, using $a\_1 = 1$.

$\begin{equation\*} A(z) = \dfrac{1}{2} + \dfrac{1}{2} \cdot \dfrac{1}{1 - 2 z} \end{equation\*}$

This is a constant term and a geometric series, using Iverson's bracket ($\[\mathit{condition}\]$ is 1 if the $\mathit{condition}$ is true, 0 otherwise), the coefficient of $z^n$ is:

$\begin{align\*} a\_{n + 1} &= \dfrac{\[n = 0\] + 2^n}{2} \\ a\_n = 2^{n - 2} + \dfrac{1}{2} \[n = 1\] \end{align\*}$

# Answer
> 0 votes
You have already found the recurrence relation which, slightly corrected, yields $$ a\_n \leq \sum\_{i=1}^{n-1} (a\_i + B) + C. $$ Let's solve instead what you wrote, $$ a\_n = \sum\_{i=1}^{n-1} a\_i. $$ In order to solve this, let $b\_n = \sum\_{i=1}^n a\_i$. Then $$ b\_n = a\_n + \sum\_{i=1}^{n-1} a\_i = 2\sum\_{i=1}^{n-1} a\_i = 2b\_{n-1}. $$ Therefore $b\_n = 2^n A$ for some constant $A$ Finally, $$ a\_n = b\_n - b\_{n-1} = 2^{n-1} A. $$

---
Tags: recurrence-relation
---


title: Prove Lecture Planning is NP-complete

text:
# Question
Title: Prove Lecture Planning is NP-complete
This is a practice problem from my algorithms class. (And no, it was not assigned as homework. I can't prove this, but you don't have to answer if you don't believe me.) To me this seems like a very difficult problem to show NP-completeness for since due to its abundance of features, it's tricky to mold a known NP-complete problem into it.

> You’ve been asked to organize a freshman-level seminar. The plan is to have the first portion of the semester consist of a sequence of $l$ guest lectures by outside speakers, and have the second portion of the semester devoted to a sequence of $p$ hands-on projects that the students will do. There are $n$ options for speakers overall, and in week number $i$ (for $i = 1, 2, \ldots, l$) a subset $L\_i$ of these speakers is available to give a lecture. On the other hand, each project requires that the students have seen certain background material in order for them to be able to complete the project successfully. In particular, for each project $j$ (for $j = 1, 2, \ldots , p$), there is a subset $P\_j$ of relevant speakers so that the students need to have seen a lecture by at least one of the speakers in the set $P\_j$ in order to be able to complete the project. So this is the problem: Given these sets, can you select exactly one speaker for each of the first $l$ weeks of the seminar, so that you only choose speakers who are available in their designated week, and so that for each project $j$, the students will have seen at least one of the speakers in the relevant set $P\_j$. We’ll call this the Lecture Planning Problem. Prove that Lecture Planning is NP-complete.

I should note that it isn't explicitly stated in the problem, but I'm assuming that a speaker can only give at most one talk. (But if this seems to prevent the problem from being NP-complete, let me know.)

At first I tried solving some graph-based problems (e.g., Independent Set) using Lecture Planning, but wasn't able to proceed because I'm not sure how you would partition vertices into subsets $L\_i$ or $P\_j$.

Thus I decided to go to 3-SAT. Even then, it is not obvious how you would solve 3-SAT using this setup. E.g., what would the clauses be? My first thought was they could be the $l$ subsets $L\_i$, and you would need a variable to be true in each; this would correspond to picking a speaker for that week. But then how do you incorporate the $P\_j$ so as to ensure the formula is satisfied (if satisfiable)?

Also thought about making the clauses the $P\_j$, but again, this didn't really seem to work.

I would greatly appreciate a hint. Thanks!

# Answer
Hint 1: For a SAT problem instance with $n$ variables construct a planning problem with $n$ lectures

Hint 2: Each $L\_i$ will have $2$ elements

Hint 3: Clauses will be $P\_j$, as you have already guessed.
> 2 votes

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


# Question
Title: Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$
> Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$.

I will make the bound to be $\in O(cn)$ instead.

Proof by strong induction.

* **Base case** n =1

$T(1) = c$ and $cn=c\*1=c$ $\checkmark$

* **Inductive Hypothesis** : $T(k) \in O(ck)$ for $1\le k\<n, n\>1$.
* **Inductive Step**: Prove for n. So prove that $T(n) \le O(ck)$.

Right away we can write $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \\ \leq T(n/2)+T(n/4)+T(n/8) + n\\ = c(n/2)+c(n/4)+c(n/8)+n \ \ \ \ By \ Inductive \ Hypothesis$

$$= c(7n/8)+n \le cn+n ... $$ I am stuck here

\*Goal: $\le cn - (some \ stuff)$ and some stuff needs to be $\ge 0$.

# Answer
First, let me mention that $O(n)$ and $O(cn)$ are exactly the same thing. What you are really after is showing that $T(n) \leq cn$ for all $n$.

Let us aim at a slightly more relaxed goal: showing that $T(n) \leq An$ for some possibly larger constant $A$. For the base case, we need $A \geq c$. For the inductive step, we know that $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \leq A(n/2+n/4+n/8)+1 = (\tfrac{7}{8}A+1)n. $$ Recall that our goal is to deduce that $T(n) \leq An$. This would follow if $\tfrac{7}{8}A + 1 \leq A$, that is, if $A \geq 8$.

In total, if we take $A = \max(c,8)$ then both the base case and the inductive step go through.

---

As an aside, you can also use the Akra-Bazzi theorem to directly conclude that $T(n) = O(n)$.

---

Now let us try to obtain more insight on the recurrence. Let $S(n) = 8n - T(n)$. Then $$ S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + 8n - 8\lfloor n/2 \rfloor - 8\lfloor n/4 \rfloor - 8\lfloor n/8 \rfloor - n. $$ Since $8(n/a-1) \< 8\lfloor n/a \rfloor \leq 8(n/a)$, we see that $$ S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + r(n), $$ where $0 \leq r(n) \< 24$. Applying the Akra-Bazzi theorem, we get $S(n) = O(n^p)$ for some $p \< 1$ (the solution to $(1/2)^p + (1/4)^p + (1/8)^p = 1$), and so $T(n) = 8n + O(n^p)$.
> 1 votes

# Answer
It's very important that you understand what f(n) = O (g(n)) means. It means that there is a number $n\_0 ≥ 0$ and a number c \> 0 such that for every $n ≥ n\_0$, f(n) ≤ c * g(n). It is a property of the whole function, not a property of some n. Saying "I prove by induction that for every n, f(n) = O (g(n))" doesn't make any sense at all. What makes sense is to say "I prove by induction that for every n ≥ n\_0, f(n) ≤ c * g(n)".

So what you want to prove per induction using some suitable c, T(n) ≤ cn. One variant of complete induction uses an induction step where you proof "if the statement $S\_k$ is true for every k \< n, then $S\_n$ is also true".

If T(k) ≤ ck is true for every k \< n, then T(n) = T(n/2) + T(n/4) + T(n/8) + n ≤ cn/2 + cn/4 + cn/8 + n = (7/8 c + 1) n.

If c = 1 this means T(n) \< 1 7/8 n. Not what we need, we need T(n) \< cn. If c = 2 it means T(n) + 2 3/4 n. Slightly better but not good enough. For which c is (7/8 c + 1) n ≤ cn, or 7/8 c + 1 ≤ c? That's the case for c ≥ 8. The start of the induction is n=0, and it's easy to show that T(0) = 0.

So you haven't just shown that T(n) = O(n), you have shown the much stronger T(n) ≤ 8n.
> 1 votes

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


# Question
Title: Difficulty in understanding this summations to analyze time complexity
I wanna know if what this link https://stackabuse.com/shell-sort-in-java/'s calculation of the complexity of shell sort is true.

Here's the shell sort algorithm:

```
void shellSort(int array[], int n){
    for (int gap = n/2; gap > 0; gap /= 2){
      for (int i = gap; i < n; i += 1) {
        int temp = array[i];
        int j;
        for (j = i; j >= gap && array[j - gap] > temp; j -= gap){
          array[j] = array[j - gap];
        }
        array[j] = temp;
      }
    }
}

```

Let me attach the site author's calculation using summations:

Where did he get the o(n log n) from? And why O(n^2)?

# Answer
> 1 votes
Shellsort is *notoriously* difficult to analyze (surprising for such a simple algorithm). In Knuth's "Sorting and Searching" it gets an inordinate scrutiny, papers on its performance get published regularly.

Then again, the Busy Beaver function (At most how many ones does an $n$ state Turing machine write starting on an empty tape before halting?) is known only up to $n = 4$, the current record holder with 6 states writes $3.515×10^{18267}$ ones before halting...

---
Tags: algorithms, time-complexity, loops, java
---


# Question
Title: Sqrt(x) function implementation; what is $(i^2 \leq x) \land ((i + 1)^2 > x)$ checking?
Recently I was working on a LeetCode question

```
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only
the integer part of the result is returned.

Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
             the decimal part is truncated, 2 is returned.

```

Here is a solution that I really like and understand, except for one line. It is using binary search to get to the solution:

```
int mySqrt(int x) {
    if (x == 0) return x;
    int left = 1, right = INT_MAX, mid;
    while(left < right) {
        mid = left + (right - left)/2;
        if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
            return mid;
        }
        if (mid < x/mid) {
            left = mid + 1;
        } else { // mid > x/mid
            right = mid;
        }
    }
    return right;
}

```

The conceptual question is: why is it true that given a particular number, say $i$, $$(i^2 \leq x) \land ((i + 1)^2 \> x)$$ returns whether or not $i$ is the truncated integer representation of the square root of $x$? (The code block above returns on the identical condition, but inequality is rearranged to avoid integer overflow)

# Answer
> 1 votes
I'll put the two inequalities together, for readability: $i^2 \leq x \< (i+1)^2$.

Taking the positive square of a positive number is a monotone function. Hence, $$i^2 \leq x \< (i+1)^2 \implies i \leq |\sqrt{x}| \< i +1$$

Then, the interger part of $|\sqrt{x}|$ is obviously $i$.

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


# Question
Title: Is a push-down automaton with two stacks equivalent to a turing machine?
In this answer it is mentioned

> A regular language can be recognized by a finite automaton. A context-free language requires a stack, and **a context sensitive language requires two stacks (which is equivalent to saying it requires a full Turing machine)**.

I wanted to know regarding the truth of the bold part above. Is it in fact true or not? What is a good way to reach at an answer to this?

# Answer
> 50 votes
Two bits to this answer;

Firstly, the class of languages recognised by Turing Machines is not **context sensitive**, it's **recursively enumerable** (context sensitive is the class of languages you get from linear bound automata).

The second part, assuming we adjust the question, is that yes, a two-stack PDA is as powerful as a TM. It's mildly simpler to assume that we're using the model of TMs that has a tape that's infinite in one direction only (though both directions is not much harder, and equivalent).

To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. You start off like so:

* Push the normal "bottom of stack" markers on both stacks.
* Push the input to the left stack (use non-determinism to "guess" the end of the input).
* Move everything to the right stack (to keep things in the proper order).

Now you can ignore the input and do everything on the contents of the stacks (which is simulating the tape). You pop to read and push to write (so you can change the "tape" by pushing something different to what you read). Then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.

For a full formal proof, see an answer to another question.

The relationship the other way should be even more obvious, i.e. that we can simulate a two-stack PDA with a TM.

# Answer
> 1 votes
In the answer by @LukeMathieson it is proved, that non-deterministic two-stack pushdown automaton is as powerful as Turing Machine. A stronger statement is also true:

> Deterministic two-stack pushdown automaton is as powerful as Turing Machine

*Proof:*

Because it is known that deterministic queue automaton is equivalent to Turing machine all we need is to prove that deterministic two-stack pushdown automaton is equivalent to queue automaton. And we get this from the fact that we can simulate deterministic queue automaton using deterministic two-stack pushdown automaton in the following way:

*Put symbol on top of the queue:*

1)Put symbol on top of the fist stack

*Read symbol from bottom of the queue:*

1)Move symbols one-by-one from the first stack to the second stack until we reach the bottom of the first stack

2)Read element from the top of the second stack

3)Move symbols one-by-one from the second stack to the first stack until we reach the bottom of the second stack

---
Tags: computability, turing-machines, automata, pushdown-automata
---


# Question
Title: How would Computer Science help the world in the novel coronavirus outbreak
This may seem off-topic question but I am really wondering how CS folks could help in situations like coronavirus. What novel problems arise from such disease? From CS and ML/AI perspectives, is there anything that Computer Scientists could do to better combat the coronavirus?

# Answer
During a recent Hackathon I witnessed, a team prepared a gadget like a smart watch. The goal is to check how many times does a person cough, to track fever and such. A really cheap piece which can be worn by everyone. The data that can be attained would yield geo-coordinates of the societies and getting affected and need attention. It can help prioritize areas of immediate concern.
> 2 votes

---
Tags: computer-vs-human
---


# Question
Title: A pathfinding algorithm for graphs in which arc weights can change over time
So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction.

Here's the situation, I have a weighted undirected graph of nodes and arcs. I have an implementation that uses A\* for pathfinding on this graph. However, I now have a situation where the weights (cost) of each arc can change over time. That is at each step in the A\* pathfinding algorithm the weights of the entire graph can change.

So I'm trying to see if there is an existing algorithm or alteration of A\*-like algorithm that handles changing weights well. If anyone has any keywords I should be looking into I'd appreciate any pointers you can provide.

# Answer
> 0 votes
Look at pathfinding algorithms in the context of robotic navigation. In many such applications, the observed world is modeled as a graph. Naturally, the environment changes meaning the graph evolves as well.

For a start, have a look at D\* Lite in the work of Koenig & Likhachev. This is a rather standard work in the area, and you'll find plenty of more work regarding replanning by looking at papers that reference it.

---

\[1\] Koenig, Sven, and Maxim Likhachev. "Fast replanning for navigation in unknown terrain." IEEE Transactions on Robotics 21.3 (2005): 354-363.

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: Practical applications of the palindromic substring problem?
The longest palindromic substring problem is certainly an interesting intellectual exercise, and seems to be popular in coding interviews in industry. As an interesting puzzle, its popularity for interviews is not too hard to understand--it's not too hard to find an $O(N^2)$ solution, and if someone manages to come up with a linear time solution, they're probably either a genius or at least well-read, which is arguably as valuable.

Given the apparent frivolity of the problem, however, it seems like a surprising amount of effort has gone in to analyzing it. There are at least three published linear-time solutions (by Manacher, Jeuring, and Gusfield). But, is it actually useful for anything? Are there other problems in which finding a palindromic substring is a necessary step? And in the absence of a direct application, did any of the known solutions to this problem reveal new techniques that have been applicable elsewhere?

# Answer
Lots of string-related algorithms have applications in the field of bioinformatics. Motivations for finding palindromic substrings in bioinformatics include

* Finding secondary structures in RNA folding
* Predicting DNA breakage during gene conversion
* Finding/analyzing clustered regularly interspaced short palindromic repeats (CRISPRs)

These three motivations are presented in an article here and there are most likely many more.
> 5 votes

---
Tags: algorithms, applied-theory
---


# Question
Title: Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix
Ryser has shown that the permanent of an $n \times n$ matrix $A=(a\_{ij})$ can be expressed as

\begin{align} Perm(A) = (-1)^n \sum\_{s \subset \[n\]} (-1)^{|s|} \prod\_{i=1}^n \sum\_{j \in s} a\_{ij}, \end{align}

where $\[n\]=\\{1,2,\dots,n\\}$. This algorithm runs in $\mathcal{O}(2^{n-1}n^2)$ time. I've been trying to derive this, but can't quite get the result. Here's my work so far.

The outer sum is over all non-empty subsets of $\[n\]$, of which there are $2^n-1$. We recall that the number of subsets of size $r$ is ${n \choose r}=\frac{n!}{r!(n-r)!}$.

For each set $s$ in the outer sum we compute $\sum\_{j \in s} a\_{ij}$, which uses $|s|-1$ additions. Next, this sum sees the product $\prod\_{i=1}^n$, which takes $n-1$ multiplications. This happens for each non-empty subset of $\[n\]$, so there are the following number of total additions:

\begin{align} \sum\_{s \subset \[n\]} \left(|s|-1\right) &= \sum\_{k=1}^n (k-1) {n \choose k} \\ &= \sum\_{k=1}^n k {n \choose k} - \sum\_{k=1}^n {n \choose k} \\ &= n \sum\_{k=1}^n {n-1 \choose k-1} - \left(2^n - 1\right) \\ &= n \left( 2^{n-1}-1 \right) - \left(2^n - 1\right) \\ &=n2^{n-1} - 2^n -n +1. \end{align}

The total number of multiplications is $(n-1)(2^n-1)$.

There is also the $(-1)^{|s|}$, which takes another $2^n-1$ operations in total.

This gives us a grand total of $n2^n + n 2^{n-1} - 2^n -2n+1$, which is not correct. It looks like I'm off by a factor of $n$ on the second term here. Where am I going wrong?

# Answer
For a given $s$, you do $(|s|-1)n$ additions, not $|s|-1$ additions: you have to compute the inner sum for each $i\in \[n\]$. Thus, you are missing a factor of $n$.
> 3 votes

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


# Question
Title: What is the earliest use of the "this" keyword in any programming language?
I understand the `this` (or `self` or `Me`) is used to refer to the current object, and that it is a feature of object-oriented programming languages. The earliest language I could find which has such a concept was Smalltalk, which uses `self` but was wondering where and when (which programming language) the concept was first implemented?

# Answer
Simula 67 is generally considered the first object-oriented language and predates Smalltalk by a number of years.

It also used the `this` keyword for the same concept, which can be seen in this book chapter extract:

```
  class Linker;
  begin
     ref(Linker) Next, Sex, Employment;
     text ID;

     procedure Add_to_List(LHead); name LHead; ref(Linker) LHead;
     begin
        Next :- LHead;
        LHead :- this Linker
     end..of..Add..to..List;

     procedure Onto_Lists(Gender,Occupation);
         name Gender,Occupation;
         ref(Linker) Gender,Occupation;
     begin
        Sex :- Gender;
        Employment :- Occupation;
        Gender :- Occupation :- this Linker
     end..of..Onto..Lists;

     InImage;
     ID :- Copy(SysIn.Image);
     InImage;
  end--of--Linker;

```
> 61 votes

---
Tags: programming-languages, history, object-oriented
---


# Question
Title: Converting DFA to Regular Expression Using State Removal
I'm trying to convert the following NFA to a regular expression.

I've attached my work below and end up with the expression $aa^\*bb^\*$. As far as I can tell, this doesn't seem correct but I've been working at it for quite a while. Can anyone tell me where I went wrong? And if it happens to be correct, can you tell me why?

Thanks a lot in advance.

# Answer
> 0 votes
Think of it this way. You can reach 2 from 1 in two ways

* $1\rightarrow 2$
* $1\rightarrow 3 \rightarrow 2$

Then from 2, you can move to 1 by $2\rightarrow 1$. From there again, move to 2 from 1 in the above two ways. So this NFA can be expressed as an RE as follows:

$$RE = (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2) \cdot \[(2\rightarrow 1)\cdot (1\rightarrow 2 + 1\rightarrow 3 \rightarrow 2)\] ^\*$$

Now its just the matter of finding the REs for $1\rightarrow 2$, $1\rightarrow 3 \rightarrow 2$ and $2 \rightarrow 1$.

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


# Question
Title: What is the point of the "check" array in a triple-array trie?
I am currently reading the definition of a triple-array trie as described here.

More precisely, I am trying to understand the nature of the three arrays:

> * ***base***. Each element in base corresponds to a node of the trie. For a trie node s, base\[s\] is the starting index within the next and check pool (to be explained later) for the row of the node s in the transition table.
> * ***next***. This array, in coordination with check, provides a pool for the allocation of the sparse vectors for the rows in the trie transition table. The vector data, that is, the vector of transitions from every node, would be stored in this array.
> * ***check***. This array works in parallel to next. It marks the owner of every cell in next. This allows the cells next to one another to be allocated to different trie nodes. That means the sparse vectors of transitions from more than one node are allowed to be overlapped.

I understand how those three arrays are linked together, but I fail to see the point of the "*check*" array. It seems to me like you could walk the trie without using the "*check*" array at all.

What am I missing?

# Answer
It is a bit confusing. Suppose the alphabet has size $\Sigma$.

Basically the idea is that instead of allocating each state an entire block of $\Sigma$ elements in next\[\] to hold the target states for each possible input character, most of which would just hold a special "this transition is invalid" sentinel value since there are typically only a few valid transitions from each state, check\[\] lets us "overlap" these blocks of $\Sigma$ elements, and thereby save space, provided there are no "collisions" -- that is, elements in next\[\] that correspond to valid transitions from more than one state.

A crucial piece of information that seems to be missing from the article (I only read down to the beginning of the next section, "Double-array Tree") is that initially all check\[\] values must have some special "no current owner" sentinel value (which in practice would be something like -1).

Think of each element in next\[\] as a resource slot, which can be either unallocated (as it is initially), or allocated to exactly one source state: check\[i\] tells you which source state the i-th element is allocated to (or if it is unallocated). The rule is: **If a source state s does not own the slot in next\[\] that corresponds to the transition on some character c, then there is no valid transition from state s on character c**. Specifically, `check[base[s] + c] != s`, which literally means "State s does not own slot base\[s\] + c in next\[\]", *also implies* "State s has no transition on character c".

In this way, all the elements of next\[\] that would have been set to a "this transition is invalid" sentinel value in the original every-state-gets-its-own-block-of-$\Sigma$-elements-in-next\[\]-to-itself scheme become available to be used by some other source state. If some such element, say at position i, is later needed by some other state s, then check\[i\] will be set to s at that time.

## Example

First let's initialise the triple-array trie data structure.

Suppose the alphabet is the digits 0-9, the states range from 0-49, and we have the following transitions for state 17, to which we allocate the block of 10 elements starting at position 20 in next\[\]:

```
Transitions from state 17
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     3     |     40     |      23     |
|     5     |      6     |      25     |
|     8     |     13     |      28     |

```

After adding this information to the triple-array trie, base\[17\] = 20, next\[23\] = 40, next\[25\] = 6 and next\[28\] = 13, and check\[23\], check\[25\] and check\[28\] are all set to 17, with every other element in check\[\] remaining at its initial value of -1.

Now suppose we that we have the following transitions for state 35, to which we try to allocate the *overlapping* block of 10 elements starting at position 22 in next\[\]:

```
Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      24     |
|     3     |     33     |      25     | <-- COLLISION

```

There is a problem, since next\[25\] is needed by both source states. We detect this by noticing that check\[25\] != -1. In this case, either state 17's or state 35's range of slots in next\[\] has to be reallocated somehow. Let's reallocate state 35's range. First, undo the allocation already done (set check\[24\] back to -1; it is not necessary or helpful to change next\[24\] to anything, since there is no meaning attached to the value of next\[i\] when check\[i\] == -1). Now we will try to reallocate state 25's slot range to start at position 24 in next\[\]. (Why 24? It's just a value that I know will work. In practice, you would probably need to just keep trying different starting points until one worked, and there is no guarantee that any will work.) Now it looks like this:

```
Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      26     |
|     3     |     33     |      27     |

```

And there will be no collisions. So after adding the information for states 17 and 25 to the data structure, we will have base\[17\] = 20, base\[35\] = 24, and next\[\] and check\[\] look like this:

```
|  i  | next[i] | check[i] |
|-----+---------+----------|
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
| 20  |don'tcare|    -1    |
| 21  |don'tcare|    -1    |
| 22  |don'tcare|    -1    |
| 23  |   40    |    17    |
| 24  |don'tcare|    -1    |
| 25  |    6    |    17    |
| 26  |   10    |    25    |
| 27  |   33    |    25    |
| 28  |   13    |    17    |
| 29  |don'tcare|    -1    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |

```

Now let's try some queries.

1. Is there a transition from state 17 on character 5? First see if state 17 owns the relevant entry in next\[\]: check\[base\[17\] + 5\] = check\[25\] = 17, so it does (and the destination state is then given by next\[25\] = 6).
2. Is there a transition from state 35 on character 1? check\[base\[35\] + 1\] = check\[25\] = 17 != 35, so state 35 does not own this entry in next\[\] =\> there is no transition from state 35 on character 1.
> 4 votes

---
Tags: data-structures, information-retrieval
---


# Question
Title: What is the name of the data structure that is a tree on the backend but has a list like API?
I'm looking for the name of a data structure. It is organized like a balanced tree. The elements need not be comparable. Instead of asking if the tree contains a thing (like you would with a collection of comparables), you can query for any k'th element in logarithmic time. You can insert before or after any k'th element. So the API is a bit like a list, except all operations are logarithmic.

I think "rope" might be similar but those seem to be restricted to strings only. It could be thought of as a segment tree, where every leaf has a weight of 1, but instead of storing the weights in the leaves the entry itself is stored.

Edit: I think it could also be referred to as an "Order Statistic Tree" but without the comparison operations.

# Answer
> 3 votes
In *"Optimal Algorithms for List Indexing and Subset Rank"* by Paul F. Dietz this data structure is called an "indexed list" and an algorithm is given that has complexity $O(\log n / \log\log n)$ for all operations. Unfortunately this term has little value as a search term.

While that is complex data structure note that you can transform any self-balanced tree into the data structure you want. Just replace the key field of each node with a field that keeps track of the number of elements to the left of it, and update this on inserts/deletes (takes $O(\log n)$ time). Then use that field as your key when searching for element $i$ in the tree.

Also check out "tiered vectors".

# Answer
> 1 votes
The *skip list* is *not* a balanced tree "under the hood", but is almost (probabilistically) tree-like.

It satisfies your "functional requirements" in that it has $O(\log n)$ insertion, and I *believe\** that you can make it so that it can give you the $k$th element in $O(\log n)$ time.

If you keep the list ordered, you can do queries in $O(\log n)$ time.

---
Tags: data-structures, balanced-search-trees, lists
---


# Question
Title: Asymptotic Analysis of Nested Loops with Conditionals
I'm trying to run an analysis of a set of nested loops so that I can determine the value of variable `sum` after the outer loop is finished. The code is as follows:

```
sum = 0;
for (i = 0; i < n; i++) {
  for (j = 0; j < i*i; j++) {
    if (j % i == 0) {
      for (k = 0; k < j; k++) {
        sum++
      }
    }
  }
}

```

Note that this code is in C++. I have no problem doing this sort of analysis via summations for each loop, but the nested 'if' conditional is throwing me off. Here's what I have so far:

* The 3rd loop is only entered if `j` is equal to or a multiple of `i`.
* The outer and innermost loops have simple bounds that can easily be solved via summation.

Where I get hung up is in regard to defining the lower and upper bounds for the second loop when representing via summation. My current equation is:

$\sum\_{i=0}^{n-1} \sum\_{???}^{i\*i-1} \sum\_{k=0}^{j-1}$

I'm subtracting 1 from the upper bounds since the lower bounds start at 0, not 1.

Does anyone have any advice on how to represent this set of nested loops as summations that I can solve to determine the final value of sum? Any help is greatly appreciated.

# Answer
> 2 votes
The condition `i % j == 0` is satisfied when `j` is equal to `m * i` for each `m = 0, ..., i - 1`. Therefore, the condition in the second loop will be satisfied `i` times. In form of summation this can be written as:

$\sum\_{i=0}^{n-1} \sum\_{j=0}^{i-1} \sum\_{k=0}^{j * i - 1}$

Moreover, your code is equivalent to:

```
sum = 0
for (i = 0; i < n; i++) {
  for (j = 0; j < i; j++) {
      for (k = 0; k < j * i; k++) {
        sum++;
      }
  }
}

```

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Are tiny point-symmetric grids of two Pentominos impossible to solve?
The game of Pentomino is a tiling puzzle game played on a grid. A Pentomino piece is a two dimensional shape of five non-diagonally connected tiles. There are exactly 12 unique pieces (ignoring rotation/reflection). The goal of the game is to fill the board with the available pieces without overlapping.

This question concerns point-symmetric boards (not necessarily rectangular) of 10 spaces, i.e. with room for exactly two pieces.

Filling such a board is, of course, trivial when using the same piece twice.

```
Using the Y-piece twice on a point-symmetric hourglass board:
####
 O#
OOOO

```

However, it seems impossible to do when using two different pieces. Is this true? How could this be proved?

This is not the case for larger boards or larger pieces (more than 5 tiles). Of course, the standard 6x10 board using 12 Pentomino pieces is also a counter example when using more than two pieces. Small counter examples:

```
Three 5-tile Pentomino pieces (V, P and L pieces) on a 3x5 grid:
vvvpp
vLppp
vLLLL

The 5-tile pieces P, T and F on an oval-shaped point-symmetric grid.
 ppTF
pppTFFF
  TTTF

Two 8-tile pieces on a 4x4 grid:
####
#OOO
#OOO
##OO

```

# Answer
> 2 votes
Let's see what happens after you rotate the partition around the board's center. The region in which one part maps onto the other part is point symmetric around the board's center. Therefore, the region in which one part is mapped onto the same part is:

* also point symmetric with the same center
* itself partitioned into two point symmetric regions with the same center and
* those two regions have the same area

The smallest non-empty such region has an area of 4. There are three possible configurations (I tetromino, S/Z tetromino, O tetromino). To connect the outer partition of the I tetromino or the S/Z tetromino into a single polyomino you need four extra tiles. For the O tetromino you need five extra, and furthemore you can't connect both regions at once.

Therefore, there is no partition of a 10-tile point symmetric board into a pair of incongruent pentominoes, and only two partitions of 12-tile point symmetric boards into a pair of incongruent hexominoes, up to symmetry:

```
I:   S/Z:
@@@@ @@@.
.@@. @...
.... @@..

```

---
Tags: board-games, tiling
---


# Question
Title: What is the meaning of the mutation rate in genetic algorithms?
Let us suppose that we have a mutation rate of 5%. What does this mean?

* Each gene of each individual has 5% of probability of change to another value? At the end, around 5% of the genes of each individual in the population will be changed.
* Each individual in the population has 5% of probability of having a random gene changed to antoher value? At the end, 5% of the population will have a change in some of its genes.

Besides that...Should I apply the mutation operator over all individuals or only to the children generated by the crossover operator?

# Answer
In general each child is mutated separately, only once at 'birth', and not during their 'adulthood'. Depending on how individuals are specified, '5% mutation' might mean that a random 5% of the bits in the individual's source code are flipped.
> 2 votes

# Answer
The mutation rate represent how probable is that a individual changes by himself. Then, you can specify how much possible is to an individual to change in a mutation (how many gens change etc). A individual can mutate on each epoch based on that probability. With this, we try to potentiate the "exploration" in order to search solutions on a different way and avoid local minimums.
> 1 votes

---
Tags: artificial-intelligence
---


# Question
Title: What other instructions are stored in the ROM?
Apart from the start-up instructions, what other programs are stored in the ROM?

# Answer
You store software in ROM for security, because it cannot be modified. Especially when your device’s operating system is updated, you want that to be controlled by software in ROM so you can detect fake or hacked software updates in a way that cannot be hacked.
> 1 votes

# Answer
ROM is Read Only Memory. It is used to store data/instructions that need not/can not/should not be ever modified (or rarely modified, you can update your BIOS because it is modifiable, but it is rarely done).

Today it is often cheaper to have a CPU and a program to do all sorts of complex tasks than to create custom circuitry (slower, sure; but if that matters depends on exactly what is done). Thus ROM. And that applies to all sorts of things, including some devices; but as devices get more complex, changing said programming is often needed, thus all sort of "firmware" (loaded on startup into the device, not changed until next time).
> 0 votes

---
Tags: memory-hardware
---


title: Find function that satisfy the relation

text:
# Question
Title: Find function that satisfy the relation
Can you find the function that satisfy the relation?

$$f(n) = \Theta(g(n)), f(n) = o(g(n))$$

# Answer
Check the definitions (as commonly used in Computer Science, mostly for run time or other resource consumption):

$f(n) = O(g(n))$ if there is a constant $c\_1 \> 0$ so that for some $N\_1$ we have for $n \ge N\_1$ that $f(n) \le c\_1 g(n)$

$f(n) = \Omega(g(n))$ if there is a constant $c\_2 \> 0$ so that for some $N\_2$ we have for $n \ge N\_2$ that $f(n) \ge c\_2 g(n)$

$f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

$f(n) = o(g(n))$ if $\lim\_{n \to \infty} \dfrac{f(n)}{g(n)} = 0$

$f(n) \sim g(n)$ if $\lim\_{n \to \infty} \dfrac{f(n)}{g(n)} = 1$

$f(n) = \omega(g(n))$ if $\lim\_{n \to \infty} \dfrac{f(n)}{g(n)} = \infty$

You see that $f(n) = \Omega(g(n))$ (one part of $f(n) = \Theta(g(n))$) and $f(n) = o(g(n))$ can't be true simultaneously (check the definition of the limit).
> 1 votes

# Answer
If `oh` is little, it is not possible. Because of the definition of these two symbols. $f(n) = \Theta(g(n))$ means there is two constants $c\_1, c\_2 \> 0$ and $n\_0 \in \mathbb{N}$ such that $g(n) \< c\_1 f(n)$ and $f(n) \< c\_2 g(n)$ for $n \> n\_0$. Hence, it means $\lim\_{n\to \infty} \frac{f(n)}{g(n)} = constant \> 0 $.

However, the definition of the `little-oh` is $\lim\_{n\to\infty}\frac{f(n)}{g(n)} = 0$ and there is not constant $c$ and $n\_1$, such that $g(n) \< c f(n)$ for $n \> n\_1$.

Also, if you mean `big-oh`, by the definition, you can say if $f(n) = \Theta(g(n))$, you can always say $f(n) = O(g(n))$ too.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Write the smallest positive number that can be represented by the floating point system
Using a normalised floating point representation box with an 8-bit mantissa and a 4-bit exponent, both stored using two’s complement.

(a) Write the smallest positive number that can be represented by the floating point system in the boxes below. The result is: Mantissa 0.1000000 and exponent 1000

Do not see how this can could someone please explain.

# Answer
> 1 votes
It is 0.100000, because normalised values are only allowed to start with 01 or 10. The exponent is 1000 (-8 in decimal) because that is the smallest possible value that can be represented using two's compliment in 4 bits. The value of the exponent means that the floating point will be moved 8 values to the left, thus making the result smaller.

# Answer
> 0 votes
That depends on the exact details of the floating point representation. Several are possible. Much more detail than you ever wanted to know is available here.

---
Tags: floating-point
---


# Question
Title: Floyd's cycle detection algorithm, why is it linear time, and how do you prove that tortoise and hare will meet?
I haven't been able to find a full proof of Floyd's cycle detection algorithm. All proofs that I have been able to find just explain why the distance from the start of the graph to the start of the cycle is equal to the distance that hasn't been traveled within the cycle.

But 1) how do we prove that tortoise and hare will meet inside the cycle? And 2) how do we prove that this algorithm is linear time?

# Answer
> 0 votes
Since hare moves 1 step faster than turtle, it will take him d steps to catch up with it, where d is the distance between them when turtle enters the loop, because this is akin to making turtle static and making hare move 1 step at a time. From that, it also follows that this algorithm is linear time and that there's no way that hare will miss turtle.

---
Tags: algorithms
---


# Question
Title: Determining recursive enumerability of given languages
I came across following problem:

> 1. $L=\\{M$ is a turing machine $M$ accepts two strings of different length $\\}$
> 2. $L=\\{M$ is a turing machine $M$ accepts atleast two strings of different length $\\}$

Which one Recursively Enumerable (RecEn)? Which one Recursive (Rec)?

I feel both are not recursively enumerable and hence not recursive. We may list strings in some order and run Turing machine on them. But we may never come across two strings of same length accepted by same TM. So we cannot answer both questions "accepts two strings of different length" and "acceptes *at least* two strings of different length". Am I correct? Also is my approach correct?

# Answer
If (1) means *exactly* two strings of different lengths, not r.e. (2) *is* r.e.: guess two strings, check their lengths are different, verify that $M$ accepts both.

Use the extension to Rice's theorem to prove (1) isn't r.e.
> 0 votes

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


# Question
Title: Efficient rasterisation of vector image with polygons
Imagine I have a 2D area where I have many simple polygons ("simple" meaning not self-intersecting, they are not necessarily concave). A polygon is given to me as a series of points. I have between 25 and 150 polygons in my area. I also have several thousand points that I need to figure out if they are inside any of the polygons or not. I need to do this about every second, with a new set of points. The set of polygons stays the same.

I know there are point-inside-polygon algorithms but they seem to be too computationally demanding for the numbers I have, particularly executing on a mobile phone in real time. So an alternative I am thinking is to pre-compute a black and white bitmap of the area (with white areas outside polygons and black inside). One pixel can simply be a single bit. Or you can see the whole thing as a 1D array of true and false values that the whole 2D area maps unto. So using area coordinates x,y we can access an element in that array and get an answer true/false. This will be considerably faster. The problem then becomes constructing this bitmap. Ideally I want this construction to happen at the phone if it's not too costly. As an alternative the phone can download this bitmap.

So how do I efficiently create this bitmap? I can run the point-in-polygon algorithm for successive "pixels" with the resolution I want, but this seems inefficient for 100K-200K "pixels", and probably rules out the phone processing option. I suspect there are more efficient algorithms than that. How do the programs convert SVG images to bitmap for example? I googled a bit, but what I get is the much more difficult problem of bmp-\>svg, also called vectorisation.

# Update

Inspired by the D.W. suggestion I expanded it to an answer. I have not implemented it to tell you what kind of savings I might get but it seems a bit expensive. Happy to receive completely different approaches.

Practically what I am currently doing is rasterising an svg file using public tools/libraries. I am doing this outside the mobile phone, and transfer the image to the phone.

# Answer
> 1 votes
An alternative approach is to use a quad-tree.

One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon. Given a test point, you traverse the quad-tree, and when you visit a node, you do a point-in-polygon test for each polygon associated with that node. This then lets you do a smaller number of point-in-polygon tests.

An alternative approach is to continue subdividing each region recursively. Stop subdividing when a region intersects with at most 2 polygons (or replace 2 with any other constant) or when you have hit some maximum depth, mark that as a leaf node, and associate those polygons with the leaf node. Given a test point, you traverse the quad-tree until you hit a leaf node, then you do a point-in-polygon test for each polygon associated with that leaf node. This trades space for time: it uses more space (more quad-tree cells) but uses fewer point-in-polygon tests.

It should be straightforward to build either type of quad-tree.

You can think of a quad-tree as a recursive version of your bitmap idea, where the bitmap is stored in a sparse way (large regions of all-white or all-black can often be collapsed to a single node), and where you have an image pyramid of bitmaps.

# Answer
> 1 votes
The quad tree suggestion by D.W. is interesting. I want to expand on it here. The principle of it is to break the area into big (and then progressively smaller) squares and check whether these squares are fully in or fully out of any polygon. Let's call these cases "black" and "white" respectively. If a big square is either black or white you do not have to check all their pixels, so you save some p-in-p tests. If a square is "grey" (meaning some of it is in and some is out of polygons) we just go to the smaller sized squares in the progression. For the smallest possible size we just make an assumption: e.g. if it's partially in we consider it fully in.

The problem then becomes how do we check whether a square is fully in or fully out of any polygons. This is not a trivial task. For example we cannot simply check whether the four corners of the square are in/out and be done. For example look at this image below that shows a square that all of its corners are within a blue polygon, but not all of the square is in the polygon.

So checking for just the corners of the square is not enough, we have to check if the sides of the squares intersect with any of the sides of the polygons (if they cross the square is "grey"). I then discovered that this is not enough either. What if a polygon is entirely inside a square? There will be no intersecting of sides but still the square is grey. The image below shows all the cases we need to check to decide if a square is "grey" "black" or "white".

This is the test to check for the "colour" of the square:

* Check the four corners of the current square: are they **all** either inside the **same** polygon or **all** outside of any polygon? No: the square is grey. Yes: look at next cases.
* Case: all corners are inside the same polygon, do the sides intersect the sides of the polygon? Yes: square is grey, No: square is black
* Case: all corners are outside all polygons. Do the sides intersect the sides of the polygon? Yes: square is grey, No: go to the next case
* Case: All corners outside polygons and no intersection of sides. Are any polygon points inside the square? Yes: square is grey. No: square is white.

I have not implemented this method to check its efficiency but as you can see it involved several (and potentially hundreds) expensive operations for each square. So we will see a significant benefit only if the boundaries are forming big blobs of space without much detail.

Any feedback on this approach is also welcome.

---
Tags: computational-geometry, polygons
---


title: Minimum moves to "stabilize" an array

text:
# Question
Title: Minimum moves to "stabilize" an array
We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A\_i - A\_{i-1}| \leq H$ for each $1\<i\<N-1$. We can modify the element by adding +1 to some element or by adding -1 to some element, we don't have a limit on how much we can use those operations, but we want to make the array stable in minimum moves.

I started solving the task by writing a dynamic programming relation, described by the state $f(i, j)$ meaning the minimum moves to stabilize the first $i$ elements of the array, such that the last element is equal to $j$.

However it seems that this method is slow for big values of $N$. How would you approach solving this problem?

# Answer
> 1 votes
Let $M=\max\_i|A\_i|$.

Besides the linear programming method proposed in this post (which is suitable for small $N$ and large $M,H$), you can optimize your dynamic programming method by building a larger table to reduce the time for querying the minimum value among $f(i-1,j-H),\ldots,f(i-1,j+H)$.

Let $f(i,j,k)$ be the minimum moves to stabilize the first $i$ elements of the array, such that the last element is **in the range $\left\[j,j+2^k\right)$**. Then we have $f(0,j,0)=0$, $$f(i,j,0)=|A\_i-j|+ \min\left\\{f\left(i-1,j-H,\hat{k}\right),f\left(i-1,j+H+1-2^{\hat{k}},\hat{k}\right)\right\\}$$ where $2^{\hat{k}}\>H$, and $$f(i,j,k)= \min\left\\{f(i,j,k-1),f\left(i,j+2^{k-1},k-1\right)\right\\}$$ for $k\>0$. Note each entry can be calculated in $O(1)$ time if we calculate them in some proper order.

Note in an optimal solution, the final $A\_N$ must be in the range $\[-(M+NH),M+NH\]$ (otherwise the final elements are all either greater than $M$ or less than $-M$, which is not optimal), so we need to calculate $f(i,j,k)$ for all $i,j,k$ such that $0\le i\le N$, $j\ge -(M+(2N-i)H)$, $k\ge0$ and $j+2^k\le M+(2N-i)H+1$. The time complexity is $O\left(N(M+NH)\log (M+NH)\right)$, while the naive $f(i,j)$ solution takes $O(N(M+NH)H)$ time.

You can further use the range minimum query technique to reduce the time complexity to $O(N(M+NH))$.

---
Tags: algorithms, dynamic-programming, arrays
---


# Question
Title: generic way to convert imperative if-then-else statements into functional style?
In this question, I asked about a reference for translating imperative code to functional code. I want to ask a more specific question here.

How, in general, do we translate into functional style, a statement of the form:

```
if (cond) then
    do x;
else
    do y;

```

I know that functional languages have if-then-else statements but the expressions are only allowed to be pure. **Is there a general way of doing this translation?**

# Answer
> 2 votes
As was mentioned in comments to the other question, *any* imperative program with side-effects can be *trivially* transformed into a pure program by simply lifting it into the `IO` monad, for example.

Or, by implementing an interpreter for an imperative language in a pure language.

That is, however, not good functional design. (Although, embedding a Domain Specific Language for side-effects into a program to provide *limited* and *isolated* side-effects in clearly demarcated sections of the code *could* certainly be considered good design.)

There *is no general way of doing this translation*. You need to *understand* what the *original problem* is that the program is solving, then *solve* that problem in a functional manner.

---
Tags: functional-programming
---


# Question
Title: In first order logic, how do we normally represent a statement?
I wanted for an example such as:

Everyone has a mother.

I've seen that it is represented in FOL as: $\forall x \exists y:$ Mother(x, y)

I'm seeing that as:For every x, there exists a y, such that y is a mother of x.

I want to know why isn't the following suitable:

$\forall x:$ hasMother(x)

Which I feel can be said as: For every x, x has a mother.

# Answer
This is a good question and comes down to what you want to achieve with the `Mother` entity.

In your first example, `Mother(x, y)` is a (binary) *relation*. That means that you can have as many `y`s as you would like per `x`. With `Mother` as a relation, you can also make formula that checks whether you have *two* `y`s that satisfies motherhood for `x`.

In your other example, `hasMother(x)` is a *predicate* that can only be *true* or *false*. How many mothers do `x` have? Impossible to say. Who is `x`'s mother? We can't say.

You could also conceive of a `mother(x) → y` *function* that maps an `x` to its mother `y`, but then you can have only one mother, and every `x` needs to have a mother (in the model).

It all comes down to (a) what is a natural representation of "the world" (whatever you want to model), and (b) what you want to achieve (whatever you want to get out of your model).
> 2 votes

---
Tags: first-order-logic, ontologies
---


# Question
Title: Find an infinite set of strings that are compressable better than in $O(\log n)$ space
The task is to find an infinite set of strings $a\_1,a\_2\ldots$, where $|a\_{i+1}|\>|a\_i|$ and to find a compression algorithm $f$ for these strings, such that $|f(a\_i)|=o(\log\_2 |a\_i|)$ with $i\to\infty$.

I have considered a set of strings with minimal entropy: $a\_1=b, a\_2=bb$, etc. The optimal compression algorithm for these strings is $f : a\_i\mapsto |a\_i|$, but this compresses each string only to $O(\log i)$ space.

# Answer
> 2 votes
Hint:

> Instead of $a\_i = b^i$, try $a\_i = b^{f(i)}$ for some function $f$.

---
Tags: data-compression
---


title: Is $L \subset 1NL$ when $L \neq NL$?

text:
# Question
Title: Is $L \subset 1NL$ when $L \neq NL$?
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left.

Hartmanis and Mahaney have investigated the classes $1L$ and $1NL$ of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that $1NL \subseteq L$ if and only if $L=NL$.

See the paper here(it is free to download):

https://ecommons.cornell.edu/handle/1813/6253

I wonder this question:

Is $L \subset 1NL$ when $L \neq NL$?

Moreover, I wonder this another question:

Is there any reference that shows whether at least one of the options $L \subset 1NL$ or $1NL \subset L$ or $L = 1NL$ should be true?

Thanks in advance!!!

# Answer
> 1 votes
If they can only move the head right, they are equivalent to finite automata.

---
Tags: complexity-theory, turing-machines, space-complexity, complexity-classes, nondeterminism
---


# Question
Title: Natural deduction proof: distributivity of existential quantification
In a current exam-prep exercise, we were tasked to prove the following formula using natural deduction of first-order logic:

$(\exists x. P \lor Q) \rightarrow P \lor (\exists x.Q)$ for arbitrary $P,Q$ where $P$ does not have free occurences of variable x.

I managed to do the prove, until I arrived at the following:

$\frac{}{\exists x.P\lor Q, P \lor Q \ \vdash \ (\exists x. P) \lor (\exists x.Q)}$

Unfortunately, applying $\lor-elimination$ only strengthens what I need to prove, so applying that doesn't work. In general, whichever rule I try to apply, I cannot get far. I also cannot apply $\exists-elimination$, as the $Q$ in $P\lor Q$ is not guaranteed to have only bound occurenes of x.

Actually, $\frac{}{\exists x.P\lor Q, P \lor Q \ \vdash \ (\exists x. P) \lor (\exists x.Q)}$ is just a rewritten form of distributivity of existential quantification: $\frac{}{\vdash \ \exists x.P\lor Q \rightarrow (\exists x. P) \lor (\exists x.Q)}$.

How shall I proceed in the prove?

# Answer
> 0 votes
You didn't say exactly what you tried, but it looks like you're trying to get there by applying elimination rules. That's not the simplest approach, and it might not work directly without case analysis on $P$ and $Q$ (I haven't tried). There's a very powerful theorem about natural deduction and most other basic logical framework: if there's a way to derive a proposition, there's a way to derive it without using elimination rules. This is called *normalization*. In the Curry-Howard correspondence, normalization of derivations corresponds to evaluation of programs and an introduction-only proof is a value (program with only constructors).

To prove that $(\exists x. P \lor Q) \rightarrow P \lor (\exists x.Q)$, let's use $\rightarrow\_I$: we need to prove that if there's a derivation of $\exists x. P \lor Q$ then there's a derivation of $P \lor (\exists x.Q)$.

If there's a derivation of $\exists x. P \lor Q$, then there is a normal derivation of it, and in particular there is a derivation ending in $\exists\_I$. The premise of this derivation is $\[t/x\](P \lor Q) = (\[t/x\]P) \lor (\[t/x\]Q)$ for some term $t$. This proposition itself has a derivation ending in one of the introduction rules for disjunction: either $\_I\lor$ with the premise $\[t/x\]P$ or $\lor\_I$ with the premise $\[t/x\]Q$. In the first case, we have a derivation of $\[t/x\]P = P$. In the second case, we can apply $\exists\_I$ to derive $\exists x. Q$. In the first case, we can then derive $P \lor (\exists x. Q)$ with $\_I\lor$. In the second case, we can derive the same proposition $P \lor (\exists x. Q)$ with $\lor\_I$. We've shown that if there's a derivation of $\exists x. P \lor Q$ then there's a derivation of $P \lor (\exists x. Q)$, QED.

---
Tags: logic, first-order-logic, natural-deduction
---


title: Priority Queue Using Stack

text:
# Question
Title: Priority Queue Using Stack
Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation. Could it be done? If so how? If not what is the best solution that can be done?

Each operation of a stack using an array is $O(1)$ whereas almost all operation of priority queue is $O(logn)$. an implementation can be done using $2D$ stacks, each elements of the stack is again a stack. When the first element of the main stack is the first element of the other stacks. The dequeue operation will take $O(n)$ as it is LIFO and the priority queue is FIFO.

# Answer
Think about it. You can sort an array by adding all the items to a priority queue, then removing the items in sorted order.

If you could run a priority queue in constant time, you could sort in linear time. But you can't.
> 2 votes

---
Tags: data-structures, simulation, stacks, priority-queues
---


# Question
Title: Analyze undirected weight graph and generate two sub graphs
I have a weighted undirected graph $G\_0$, from which I want to derive weighted undirected graphs $G\_1$ and $G\_2$.

* All nodes in $G\_0$ have a degree of at least one.
* $G\_1$ and $G\_2$ can contain the same node but not the same edge.
* All nodes in both $G\_1$ and $G\_2$ should have a degree of at least one.
* All edges from $G\_0$ should be contained in either $G\_1$ or $G\_2$
* Both $G\_1$ and $G\_2$ are subgraphs of $G\_0$ and cannot contain additional nodes.
* **Edit (Added constraint)**: $G\_1$ and $G\_2$ are both traversable trails

Let's assume that the sum of all the edges in $G\_0$ is $x$.

I need to find the pair of $G\_1$ and $G\_2$ for which the sum of all edges in $G\_1$ is closest to $x/2$.

How would you go about solving that?

**Edit:** After much hassle due to my lack of explanatory powers, here is a better explanation of the problem (this is for an unweighted graph, but it will at least point me in the general direction of a suitable algorithm, also it avoids technical terms because is obvious that I struggle understanding them at the moment)

Lets assume that we have an undirected Graph with Vertices A,B,C,D,E

```
A --- B
|   / | \
|  /  |  C
| /   | /
D --- E

```

Which means an adjacency matrix like this one:

```
  A  B  C  D  E
A -  1  0  1  0
B 1  -  1  1  1
C 0  1  -  0  1
D 1  1  0  -  1
E 0  1  1  1  -

```

Assuming all edges are undirected, we have the following edges:

```
(a,b) (a,d) (b,d) (b,e) (b,c) (e,d) (e,c)

```

What I want is to generate two groups of edges of roughly the same size. (In this particular case, since we have 7 edges, we would get a group of 3 edges and another one of 4 edges.

```
Group 1: (a,b) (a,d) (b,d) (e,d)
A --- B
|   /
|  /
| /
D --- E

Group 2: (b,e) (b,c) (e,c)
B
| \
|  C
| /
E

```

Notice that all edges in each group are connected by at least one node, that is a requirement.

Another valid solution could be, for example:

```
Group 1: (d,a) (a,b) (b,c) (c,e)
A --- B
|      \
|       C
|      /
D     E

Group 2: (d,b) (b,e) (e,d)
      B
    / |
   /  |
  /   |
D --- E

```

And so on, as you see there are many valid solutions but I want to know if there's an algorithm to find one.

# Answer
Sorry about the poor explanation, but after a lot of help here, Stack Overflow and Math Exchange and a lot of reading, I finally understood that what I'm actually trying to do is:

**Given a Graph G, obtain two disjointed trails of approximately the same size so that every edge is visited by one of those trails.**

Thanks to everyone!
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: What algorithms for unification over (multidimensional) array terms?
I am looking for references on implementing unification over multidimensional array terms.

Are there specialized unification algorithms for those cases? I wasn't able to find satisfactory literature on the topic, and I am attempting to write a logic programming library for the J language.

# Answer
> 2 votes
By way of context, I'll assume the goal is to do unification in classical first-order logic in a fixed language $\mathscr{L}$. (Formatting and other corrections welcome.)

Briefly, you can treat arrays as terms and multidimensional arrays as arrays of arrays. You'll also introduce a new term symbol that doesn't occur in $\mathscr{L}$.

So for example, if you have a multidimensional array like the following,

\begin{pmatrix} 1 & 2 & 3\\ x & y & z \end{pmatrix}

you'll first convert it to an array of arrays,

$$\text{((1 2 3) (x y z))}$$

and then convert it to terms. Assuming the term symbol `a` is not in your language, you can now represent your multidimensional array as follows:

```
    a(a(1,2,3),a(x,y,z))

```

---
Tags: logic, arrays, unification, logic-programming
---