title: Fastest algorithm for matrix inversion

text:
# Question
Title: Fastest algorithm for matrix inversion
What is the fastest way to compute the inverse of the matrix, whose entries are from file $\mathbb{R}$ (set of real numbers)?

One way to calculate the inverse is using the gaussian elimination method. In this method append more columns(double the number of columns ) to the input matrix and then we try to make last row zero except the last column entry and second last and so on until we get a identity matrix and then we stop and we have a inverse of input matrix. Consider the cost of one multiplication, division and addition is constant. Then total $O(n^2)$ many operations is needed.

Is there any algorithm which is faster than the above algorithm? Please give the algorithm or reference to the algorithm

# Answer
Gaussian elimination requires $O(n^3)$ operations, not $O(n^2)$.

In general, matrix inversion has the same exponent as matrix multiplication (any matrix multiplication algorithm faster than $O(n^3)$ gives a matrix inversion algorithm faster than $O(n^3)$), see for example P.Burgisser, M.Clausen, M.A.Shokrollahi "Algebraic complexity theory", Chapter 16 "Problems related to matrix multiplication".
> 4 votes

---
Tags: algorithms, matrices
---


title: Make n-bit adder

text:
# Question
Title: Make n-bit adder
I understand how 1-bit adders work, but I don't see how to make a 4-bit adder using those 1-bit adders...

This is my 1-bit adder:

How can I use this to create a 4-bit adder?? This is my attempt, but it ain't working because I event don't include a carry-in; and I need two 4-bit inputs.

# Answer
So, the way that a ripple-carry adder works is to separate each column of the addition into its own circuit.

So, consider this addition:

```
A:   0011    3
B: + 0110  + 6
    -----   --
S:   1001    9

```

The first activity that you need to accomplish is to add $A\_0$ (`1`) to $B\_0$ (`0`) to arrive at $S\_0$ (`1`). This is done in its own circuit, similar to the full-adder that you've shown in your question.

So far, we need a circuit where $A\_n$ and $B\_n$ are inputs, and our *sum*, $S\_n$ is our output. So, two inputs, one output. This is slightly different from your circuit. Hold onto that information, because we're about to need it.

The second step is to add $A\_1$ (`1`) to $B\_1$ (`1`) to arrive at $S\_1$ (`0`). Once again, this gets handled in its own circuit. And usually that circuit is directly next to the first circuit, so we now have two adjacent wires with (`0`,`1`) coming out. And our circuit from before is still sufficient, because each $A\_n$ and $B\_n$ has resulted in a proper $S\_n$.

Now, at the third step, things get interesting. Because $A\_2$ (`0`) + $B\_2$ (`1`) can't become `0` without additional information. We need a carry!

Suddenly, each column (each circuit) needs an additional **input** (the carry-in, or $C\_{in}$), and each column needs an additional **output**, $C\_{out}$. We need these wires to facilitate communication between the different columns.

Now, we have three inputs ($A\_2$ (`0`), $B\_2$ (`1`), and $Cin\_2$ (`1`)), and our $S\_2$ of `0` makes more sense. And we have an additional output, because we have to tell the next level of the addition that there was a carry. So now, with three inputs and two outputs, we have created *your* circuit.

And we need one of these for each layer of the addition, chained together like this:
> 1 votes

---
Tags: computer-architecture
---


title: 2:1 Mutual exclusion with semaphores

text:
# Question
Title: 2:1 Mutual exclusion with semaphores
I'm stuck on this semaphore exercise (it's a exam question of a previous exam and I'm studying for that exam):

There are three processes: A, B and C. Process A wants to execute method a(); Process B wants to execute b(); and Process C c();. The Processes are each started once.

The execution of a(); must not overlap with the execution of b(); or c();. However b(); and c(); must always be able to run concurrently. The order of execution must not be forced.

I can use as many semaphores as I want. With every solution I tried so far I always get the case that when e.g. b(); is executing and a(); is waiting, that I will also block c();. The solution is probably simple but I'm too blind to see it.

# Answer
There's a simple solution which takes advantage of the fact that semaphores naturally allow controlling access to a resource with multiple instances. Model the exclusion as a resource with two instances. A requires both instances while B and C each require one. When A starts, it grabs both instances, preventing B and C from starting. When B or C starts, it grabs one instance, which allows the other to start concurrently, but blocks A.

```
A:                  B:                  C:
  V(S, 2)             V(S, 1)             V(S, 1)
  …                   …                   …
  P(S, 2)             P(S, 1)             P(S, 1)

```

This solution works even if the processes run multiple times. A critical ingredient that makes it work is that A atomically excludes both B and C from running.

If you treat B and C's resources as distinguishable, with A requiring both, you run into a classical problem, which is the order of grabbing locks. This problem is similar to the dining philosophers problem. When A starts, it either grabs the *B* resource first, or the *C* resource first. Let's say A grabs *B*, and then tries to grab *C*. If *C* is not available, what should happen? If A keeps the *B* resource then it prevents process B from starting. So A must release *B* and try again. Since A knows that *C* is busy, it can wait on *C* first. In this particular exercise, where the processes only run once, this works. Note that this requires semaphores with a non-blocking “try” operation.

```
A:                  B:                  C:
  lock(B)             lock(B)             lock(C)
  if try_lock(C):     …                   …
    …                 release(B)          release(C)
    release(C)
    release(B)
  else:
    release(B)
    lock(C)
    lock(B)
    …
    release(B)
    release(C)

```

If B and C could run multiple times, this strategy wouldn't work: A must never keep one lock while waiting for the other, because that prevents the corresponding process from running again. In this case, I think there's no wait-free solution with only binary semaphores.
> 0 votes

# Answer
**Use two binary semaphores : x and y.**

x will provide mutual exclusion between A and B while y will provide mutual exclusion between A and C.

When A wants to execute a() then it must check that neither of b() and c() is being executed. Thus code for A would be like this:

```
lock(x)
lock(y)
a()
unlock(y)
unlock(x)

```

For B code would be like this:

```
lock(x)
b()
unlock(x)

```

For C code would be like this

```
lock(y)
c()
unlock(y)

```

You may check different execution sequences to verify my answer.
> -1 votes

---
Tags: concurrency, synchronization
---


# Question
Title: Is a powerful two-way hash function provably impossible?
A two-way hash function that could hash complex strings to a fixed length would change the world.

Imagine the decreased load on wires around the world if, for example, HTML pages could be hashed, then decoded by clients. Power (electricity) savings would be enormous.

Is it absolutely, without a shadow of a doubt, impossible to create a two-way hash function that can encode and decode long, complex strings? If there's even a slight chance that such a hash function could be developed, it seems it would be worth substantial investment of time and other resources to try to develop one.

# Answer
> 3 votes
> Is it absolutely, without a shadow of a doubt, impossible to create a two-way hash function that can encode and decode long, complex strings?

It is absolutely, without a shadow of a doubt, impossible to create an encoding mechanism where you can transmit more than $2^s$ options in only $s$ bits.

Consider the decoding mechanism, which takes an encoding of $s$ bits, and generates the expanded output. There are $2^s$ possible inputs (bit patterns), and hence there are (at most) $2^s$ possible outputs.

For a long, complex string, there are a huge number of such long, complex strings that we might want to send, and hence the $s$ you'll need is quite large.

Now, you can reduce the size somewhat; this is known as 'data compression', and it is fairly well studied technology. However, such technology is dependent on the expected distribution of the preimage (it doesn't work on random data), and the amounts of compression you get (assuming that the decompressor is required to return the exact same value that the compressor had, this is known as 'lossless compression') usually aren't that impressive for real inputs.

---
Tags: hash
---


# Question
Title: How many tapes would Turing Machine require to find the sum of 2 integers (expressed in base2)?
Suppose I wished to devise an algorithm (to be run on a turing machine) which could find the sum of 2 integers (expressed in base2). How many tapes would this require?

My intuition tells me that 4 tapes would be required: 1 for each of the two numbers being added together, 1 to store the 'carry over' value, and 1 to store the output.

Is this correct? Could it be done with fewer tapes?

# Answer
Anything that can be computed with any reasonable extension of a Turing machine can be computed with the standard Turing machine that has a single one-way infinite tape.

For example, you can simulate a four-tape machine by interleaving the characters of the tapes so that, e.g., the four tapes

$$\begin{array}{cccc} a\_1 & a\_2 & a\_3 & \cdots\\ b\_1 & b\_2 & b\_3 & \cdots\\ c\_1 & c\_2 & c\_3 & \cdots\\ d\_1 & d\_2 & d\_3 & \cdots \end{array}$$

with the single tape $$a\_1\ b\_1\ c\_1\ d\_1\ a\_2\ b\_2\ c\_2\ d\_2\ a\_3\ b\_3\ c\_3\ d\_3\ \cdots$$
> 2 votes

---
Tags: turing-machines
---


# Question
Title: Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time
This question is taken from an exam of a Computer Theory Course.

> Describe how a NON-Deterministic Turing Machine with two tapes recognize in **linear** time palindrome strings with **even** length that have the form: $L=\\{ww^R\mid w\in\\{a,b\\}^+\\}$.

* Tape 1: Read-Only & monodirectional
* Tape 2: Read and Write, bidirectional

$w^R$ is the reverse of $w$.

**My guess:**

*With determinism* and $L = \\{{wcw^R | w \in \\{a,b\\}^+ \\}}$ I copy the input from tape 1 onto tape 2, then I check if the first part of the tape is equals to second part using two markers, $X$ for $a$ and $Y$ for $b$ to keep track of the current iteration.

In every iteration of the algorithm I check if there is a corresponding $a$ (or $b$) in the second part of the tape, reading the tape backwards.

In the last iteration, if i read only $X$ or $Y$ i accept, otherwise reject.

*With non-determinism*: i need to guess where is the center of the tape. One of the configuration in the computation tree would be $wq\_cw^R$ where $q\_c$ identify the state representing the string's center. Here i can do the same verification for the deterministic version of the problem.

# Answer
**Hint.** Suppose that, instead, the alphabet was $\\{a,b,c\\}$ you wanted to recognize

$$\\{wcw^{\mathrm{R}}\mid w\in\\{a,b\\}^+\\}\\,.$$

How would you do that on a deterministic version of the machine you're trying to use? Now, in the real problem, nobody's telling you where the middle of the string is. How would you use nondeterminism to get around that problem?
> 2 votes

---
Tags: turing-machines, nondeterminism
---


title: Definition of a grammar

text:
# Question
Title: Definition of a grammar
I am learning about context free grammars and have been through few texts in a undetailed manner on these topic . I think I should know the exact , rigorous ,technical definition of what exactly a "grammar" means .

I could see that ,in all of these lessons, a sequence of equations as follow :

```
 a = bc
 b = ed
 c = gh

```

I was tempted to conclude that "a grammar is a collection of symbols which are related by a set of equations which dictate rules for substitution of a symbol by a series of symbols "

Then I got to know that , not in all series of equations can we substitute one symbol by a series of another symbol .We can do it only in case of "context-free grammars " . Then I went through one of the stackexchange post and through a brilliant answer got to know what context free exactly means .

So , I thought before I proceed ahead I better seek for the exact rigorous definition of a grammar . What exactly is the mathematical/technical definition of a grammar ?

# Answer
> 1 votes
A grammar is a set of production rules for symbol sequences.

But you knew that already. If you edit the question to make it more specific, we can offer more specific answers.

---
Tags: context-free, formal-grammars
---


# Question
Title: f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)?
All functions are from naturals to naturals.

Let f(n) and g(n) be monotonically increasing functions. prove or disprove h(n) = max(f(n),g(n)) =\> h = O(f) or h = O(g)

I've found close questions regarding max(f,g) being O(f+g) but I couldn't derive anything from them regarding my specific problem. Needless to say, I'm new to algorithms and data structures.

any explanations, solutions would be great :)

# Answer
That's not true. Let's define $f$ and $g$:

$$ f(x) = \left\\{\begin{aligned} &1 && x = 0\\ &2f(x-1) && x \equiv 1 \mod 2\\ &4^xf(x-1) && \text{otherwise} \end{aligned} \right.$$ $$ g(x) = \left\\{\begin{aligned} &1 && x = 0\\ &4^xg(x-1) && x \equiv 1 \mod 2\\ &2g(x-1) && \text{otherwise} \end{aligned} \right.$$

They look odd, but you can easily proof (by induction), that: $$ max\\{f, g\\}(x) = \left\\{\begin{aligned} &2^{x}g(x) && x \equiv 0 \mod 2\\ &2^{x}f(x) && x \equiv 1 \mod 2 \end{aligned} \right.$$

Intuition behind this is that for each number $x$ we 'increase' value of one function by $2$ and one by $4^x$. Increasing first function is straight forward, just for keeping function strictly increasing. Multiplication of second function is more interesting. Since $4^x = 2 \cdot2^{x-1}\cdot2^x$, we can split this operation into 3 steps:

1. multiply by $2$ since, another function is multiplied by $2$,
2. multiply by $2^{x-1}$, because another function was already greater by that factor,
3. multiply by $2^{x}$, because we want our function to be greater by this factor

Now you can easily see, that there is no constant $c$ for which $$max\\{f, g\\}(x) \< cf(x)$$ nor $$max\\{f, g\\}(x) \< cg(x)$$.
> 0 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: How does processing speed affect algorithm performance?
I'm currently taking a class on algorithms, and we are studying algorithmic efficiency. I understand classifying algorithms based on their time complexity, but I am confused about the following category of questions:

Suppose algorithm *A* has time complexity *C* (*C* being along the lines of *n*^2, *n* \+ 1, 3 * 2^*n*, etc.), and it takes *t* seconds to execute *A* on a given machine for a certain number of inputs *n*. If you execute *A* on a machine that is *M* times faster than the original machine, how many inputs (*n*) can be processed in *t* seconds (same number of seconds as on the previous machine)?

I know that the greater the time complexity of an algorithm, the less improvement is gained by speeding up the machine, however I can't seem to figure out a reliable equation to compute the new number of inputs. For algorithms with linear time complexity, I think I am correct with: multiply the time complexity (constant * *n*) times the increase in speed to get *M* * constant * *n*. I haven't found much information about this either in books or elsewhere on the web; if anyone can help me create a better equation it would be much appreciated!

# Answer
Let's say that the execution time of an algorithm is $\Theta(f(n))$. That means the execution time is between c·f(n) and C·f(n) for all n ≥ N, for some N, c and C. Because of the constant, you can't say anything definite about the maximum problem size that can be solved in time T on a slow and a fast computer.

You can *assume* that the actual execution time is c·f(n) for a c that you know; that assumption is neither completely unreasonable nor completely justified. Then define for example n' as the value where c·f(n') = k · c·f(n), to get something meaningful for a machine that is k times faster.

Calculating n' depends on the nature of f(n). If f(n) is linear, then n' = k·n. If f(n) is cubic, then n' = $k^{1/3}·n$. If f(n) = c·n·ln n then n' is a bit less than k·n, the exact result is difficult. If f(n)=$2^n$, then n' = $n + \log k$. The last shows why efficient algorithms don't become less important with faster computers in practice: Because the less efficient the algorithm, the less a faster computer can improve the size of a problem that can be solved in fixed time.
> 2 votes

# Answer
Okay so I think I might have just answered my own question. I am not completely sure this is accurate, so feel free to correct me.

If computer 1 can compute *m* operations in *t* seconds, and computer 2 is *x* times faster than computer 1, then computer 2 can compute *xm* operations in *t* seconds.

For an algorithm with linear time complexity, each input *n* requires some constant *a* times *n* operations. To get the number of inputs a faster computer could handle in time *t*, simply multiply *x* times *m*, and then multiply that by your constant *a*.

For algorithms with greater time complexity, you still continue to multiply *m* operations by *x* times faster. However, you also have to account for the fact that *m* operations does not directly translate into *n* outputs in a linear way. If the time complexity is *n*^2, then *xm* operations only gets you sqrt(*x*) more outputs in time *t*.

Update: I'm now not at all sure this is correct, if anyone knows more about this, feel free to chime in.
> 0 votes

# Answer
When considering different clock speeds, the same equipment might be "computer 1" for a few seconds, with power saving 1 GHz clock rate, and then might become "computer 2" for a few seconds, clocked at its max of 2 GHz.

You consider that "computer 1 can compute m operations in t seconds". But there are several "operations". Consider the "add one to an array" algorithm:

```
for (i = 0; i < N; i++) {
    a[i]++;
}

```

Computing effective address within the array may happen quickly, in a single clock cycle, and be strongly dependent on the core's clock rate. Reading a value from the array often takes multiple clock cycles, and will be influenced by prefetcher and state of each cache level. Above we see one of two sequential permutations of array indexes, but any permutation would work, though some permutations will interact badly with prefetch and with cache lines. Changing a core's clock rate typically doesn't alter memory bus timings. Disk I/O, e.g. for page faults, is even further down the memory hierarchy. Pipelines and other overlap of work will additionally muddy the waters.

You spoke of the time it takes for a computer to perform "an operation", but you probably want to speak of the time needed for each of several operations. In practice, a small number of them will dominate so a simplified analysis can focus just on those.
> 0 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: How can a spinlock progress when it's busy-waiting?
I read that in spinlock, process keeps on waiting for the lock continuously in a loop until it receives `signal(lock)` or `release(lock)` from other processes. This causes busy waiting and hence CPU cycles are wasted.

My doubt is, if CPU is continuously checking the value of lock variable in loop, then how will some other process completely execute critical section and release the lock as executing critical section also needs CPU and CPU is busy checking the value of lock in other process?

# Answer
There might be other CPUs in the system, if one is busy waiting, another can be doing something. Furthermore, if the OS uses preemptive scheduling, the thread doing the busy wait might be preempted and another thread will do something and release the lock for example. The signal might also come from an interrupt handler, for example if the thread is waiting for the completion of some I/O operation, and an interrupt will stop the execution of the thread temporarily, signal the lock, and resume the thread.
> 4 votes

# Answer
A spinlock is indeed wasting CPU time while the lock is held by another thread. So why / when would you use a spin lock? You use it when the lock is held for very, very short times.

A "real" lock that stops the thread from running until the lock isn't held anymore has some significant overhead for stopping / restarting the thread. So as long as the average time the lock is held is smaller than this overhead, the spinlock wins. If you hold locks for a long time, a spinlock is terribly inefficient.
> 2 votes

# Answer
Checking some value is equivalent to doing some work by CPU. Now if you have read scheduling properly you would have known that the CPU can be taken from any process even in the middle of a task. So even when a process is stuck on spinlock, nothing will prevent the scheduler from taking the cpu from this process and giving a chance to some other process(maybe the one which is in its critical section).
> 0 votes

---
Tags: operating-systems, concurrency, process-scheduling, mutual-exclusion
---


# Question
Title: The constant in the merge sort recurrence
Assuming that the worst case running time of merge sort can be described with this recurrence:

$\ T(n) = \begin{cases} \theta(1) & \text{if }n = 1\\ 2T(\frac{n}{2}) + \theta(n) & \text{if } n\gt 1 \end{cases} $

*Introduction to Algorithms* says that it is possible for the same constant $\ c $ to represent the time required to solve problems of size $\ 1 $ as well as the time per array element of the divide and combine steps, so that

$\ T(n) = \begin{cases} c & \text{if }n = 1\\ 2T(\frac{n}{2}) + cn & \text{if } n\gt 1 \end{cases} $

**How is there a constant $\ c $ that can represent both times?** Shouldn't the proper way to describe the recurrence be

$\ T(n) = \begin{cases} a & \text{if }n = 1\\ 2T(\frac{n}{2}) + bn & \text{if } n\gt 1 \end{cases} \text{where }a\ll b $

---

If the answer is dependent on the psuedocode provided in the book, I'll post it here. However, there is a single if statement in a trivial mergesort (size 1). Surely, the cost of that single if statement can't be the same as the sum of the costs of all the steps taken in the merge step, as well as the constant-time division of the problem into smaller problems?

Sorry if this has been asked before.

# Answer
Nitpick: Are they really talking about *time*? If they are actually counting some operation, it's well possible (if unlikely) for the same constant to show up in both places.

> How is there a constant c that can represent both times?

It (probably) can not. This is a simplification done with the goal in mind: derive a $\Theta$-bound.

Apply the Master theorem to both candidate recurrences; you'll note that the result stays the same. CLRS know this from experience, so they simplify the recurrence a-priori.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, recurrence-relation, mergesort
---


# Question
Title: Finding solutions to $n m\equiv x \mod n$
Given a modulus $n\in\mathbb{N}$ and another natural number $0\<x\<n$, what's an efficient algorithm to enumerate all pairs of natural numbers $(a,b)\in\mathbb{N}^2$ such that both $a$ and $b$ are less than $n$ and $$ab\equiv x \mod n\text?$$

# Answer
> 1 votes
Let's solve the problem for a specific $a$. Observe that $ab \equiv x \pmod{n}$ if and only if there exists a $m \in \mathbb{Z}$ such that

$\qquad ab + mn = x$

By the Bezout theorem, the above has solutions if and only if $x \mid (a, n)$ (the "if" arrow is the theorem, the "only if" arrow is trivial). One of those solutions can be found by the Extended Euclid algorithm, and all the others can be obtained observing that if $(b, m)$ is a solution, then

$\qquad \left( b + \frac{n}{(a, n)}, m + \frac{a}{(a, n)} \right) $

is also a solution. Repeating the above process for all $a \in \mathbb{Z}/n\mathbb{Z}$ yields all the pairs you are looking for. While it's rather naive, I don't think you can get much better than that if you're looking for all solutions.

---
Tags: number-theory, modular-arithmetic
---


# Question
Title: Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels?
A common modification to the Needleman-Wunsch to reduce running time is to only fill in the cells along a diagonal band of the matrix (slides 27/28). Let 2d + 1 represent the width of the band. Then based on the provided text, this ensures that the *total number* of inserts and deletes does not exceed d.

However, I can't understand the intuition behind the algorithm. If we let L represent a list of the size of each mutation in the alignment in-order (where negative sizes represent deletions), doesn't the band restriction merely say that the sum of values in any prefix slice of L must stay between -d and d? But the total number of mutations could easily exceed d.

E.g. If d = 4, throughout a long alignment, there could be 5 distinct mutations, where L refers to a series of \[insertion, deletion, insertion, insertion, deletion\] with sizes: \[3,-2,2,1,-4\]. Visually, such an alignment would represent a wiggly line through the DP matrix that results in plenty of small insertions and deletions, alternating to ensure that the alignment stays within the band.

In other words, the band does not actually restrict the total number of insertions and deletions as claimed? If I'm misunderstanding something, I'd appreciate any clarification. Thanks!

P.S. Was unsure if this post should go under the bioinformatics stackexchange beta.

# Answer
> 2 votes
You are correct, the number of insertions/deletions $d$ is not constrained (only) by the bandwidth.

However, the algorithm only uses the fact that if we know $d$, then the path must stay within the $2d+1$ band. This band does not have to be tight: a zigzag path would indeed fit within a much narrower band.

---

You may wonder why the smallest bandwidth (which is indeed equal to the maximum sum over prefixes of your list $L$) isn't used as a parameter instead of $d$. Since $d$ is related to the similarity of the strings, it isn't unreasonable that an upper bound of $d$ is known in some applications. The smallest bandwidth doesn't seem to correspond to a 'natural' parameter in the context of similarity as $d$ does, so it doesn't seem reasonable that it is known and can be used in the algorithm.

---
Tags: algorithms, dynamic-programming, subsequences, bioinformatics
---


title: What is bit time in Ethernet CSMA/CD

text:
# Question
Title: What is bit time in Ethernet CSMA/CD
"Propogation delay betwween two links is 200 bit times" I am little confused here, Propogation delay should be in seconds, milliseconds etc but here it is in bit times. I also want to know what is bit time and is it same as Propogation delay.

# Answer
Bit time only calculates the ejection of one bit, it looks at how this bit transmits out of a network interface card at a determined speed. $$bit\\\_time = \frac{1}{NIC\\\_speed}$$ let NIC speed is $10Mbit/s$ then bit time = $$\frac{1}{(10 * 10^6)} = 10^{-7} = 100 * 10^{-9} = 100ns$$ Bit rate is different form propagation delay, as the propagation delay is the amount of time it takes for the head of the signal to travel from the sender to the receiver and bit rate is the number of bits that are conveyed or processed per unit of time.
> 1 votes

# Answer
There are constraints on propagation delays expressed as "bit time" because the protocol, the collision detection, depends on the time each message lasts on the wires. Because the emitter must know if there is a collision to be able to re-transmit messages, having very long propagation delays, longer than message lengths, could hide collisions from the emitter.

This is not an absolute value as it is proportional to the data rate : Faster network need a smaller propagation delay than slower networks for CSMA/CD to work.

The automotive CAN protocol has similar constraints: the maximum data rate depends on the total length of the network for correct master arbitration.

You want values ? A 10Mbps Ethernet network has a nominal bit time of 100ns

A 1GHz Ethernet network has a nominal bit time of 1ns, but, because of encoding, there is no literally bits pushed serially at 1GHz : Sometimes it is 1.25GHz over optical fibres, sometimes it is a several bits per cycle at 125MHz over four twisted pairs, etc...
> -1 votes

---
Tags: computer-networks
---


# Question
Title: Is Mersenne primality testing necessarily EXPTIME?
The computational complexity of primality testing is usually specified in relation to the bit length of the number being tested.

However, Mersenne numbers have the special property that the characterizing instance exponent $p$ is exponentially more succinct than the number it signifies. Surprisingly, most of the literature I've found appears to assume a unary representation of $p$ rather than binary.

The Great Internet Mersenne Prime Search, for example, aims to identify very large Mersene primes via an optimized distributed Lucas–Lehmer primality test. GIMPS as a virtual computer has at times ranked among the TOP500 in terms of expended computational capacity.

So is all this distributed computing truly necessary? Do we really need to expand $p$ to its verbose representation to verify its primality?

Or is there still a possibility that primality testing for Mersenne numbers could be decidable in polynomial time in the size of the instance $p$ via some clever certificate tree?

# Answer
Nothing is impossible. But the problem is that you might want to check whether a 10 million digit number is a prime, but that number is just 2 raised to an 8 digit power, minus 1, so the problem size would be just 8.

For random 10 million digit numbers, the problem size is 10 million. For 10 million digit Mersenne numbers, the problem size is just 8. You can't even write down that number in polynomial time in the problem size. You can't even write it in base 2 in polynomial time, where the number is just a *huge* string of 1's.
> 1 votes

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


# Question
Title: Why Miller–Rabin instead of Fermat primality test?
From the proof of Miller-Rabin, if a number passes the Fermat primality test, it must also pass the Miller-Rabin test with the same base $a$ (a variable in the proof). And the computation complexity is the same.

The following is from the Fermat primality test:

> While Carmichael numbers are substantially rarer than prime numbers, there are enough of them that Fermat's primality test is often not used in the above form. Instead, **other more powerful extensions** of the Fermat test, such as Baillie-PSW, Miller-Rabin, and Solovay-Strassen are more commonly used.

What is the benefit of Miller-Rabin and why it is said to be more powerful than the Fermat primality test?

# Answer
> 7 votes
The Rabin-Miller algorithm also tests, given a number $n$, whether $Z\_n$ has a nontrivial root of Unity.

Carmichael numbers pass the Fermat test (for every basis $a$), but for every Carmichael number $n$, there exist many numbers $a$ such that the test for unity roots fails on $a$ (that is, the sequence $a,2a,...,2^ra$ eventually displays a nontrivial root of unity).

Thus, we have the following:

For Fermat's test, if a composite number $n$ is not Carmichael, then the probability that the test will detect compositeness is at least $1/2$. However, the test will fail all Carmichael numbers.

For the Rabin-Miller test, every composite number will be detected with probability at least $1/2$. This means that the correctness probability is independent of the input (there are no "hard" inputs). This is what makes this algorithm stronger.

# Answer
> 0 votes
I believe your statement is the opposite of what happens. Passing the Miller-Rabin test for a given base means it will pass the Fermat test for the same base. In contrast, there are many composites that will pass the Fermat test for a given base but will fail the Miller-Rabin test for the same base.

See, for example, the paper by Pomerance / Selfridge / Wagstaff in the Wikipedia Miller-Rabin page:

https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

where we see a diagram on page 2 showing the Euler pseudoprimes being a subset of the Fermat pseudoprimes, and the strong pseudoprimes being a subset of those. The Solovay-Strassen test is therefore more discerning than the Fermat test, and the Miller-Rabin test more than either. They both avoid the critical problem of Carmichael numbers. They have essentially the same performance, so we prefer to use the Miller-Rabin test.

# Answer
> 0 votes
It should be obvious that Miller-Rabin is better than Fermat.

With the Fermat test, we check whether $a^{p-1}$ = 1 (modulo p).

With the Miller-Rabin test, to calculate $a^{p-1}$ we find k and odd s such that $p-1 = s·2^k$. Then we calculate $a^s$ modulo p, and calculate k times the square modulo p. That's a pretty obvious way to calculate $a^{p-1}$.

Again, if the result is not 1 (modulo p) then p is composite. But if the result *is* 1 modulo p, then we check whether we got that 1 by squaring an intermediate result that wasn't +1 or -1, and in that case x is also proven composite.

So we do exactly the same amount of work, but there are more ways to prove that x is composite.

---
Tags: algorithms, primes
---


title: What's the language of the NFA?

text:
# Question
Title: What's the language of the NFA?
Given is the NFA `N`:

What's the language of this NFA? What's its complement?

---

I'm learning for a test and I'd like to know if I solved this task correctly.

The language `L` of the `NFA N` should look like this:

```
L(N) = {x ∈ Σ* | x mustn't include 'aba' and x mustn't end with 'ab'}

```

I have tried several different words and I couldn't find any word that breaks my language `L(N)`.

Assuming this is correct, how would the complement of `L(N)` look like?

It needs to be the opposite, right? So something like that (`~` stands for complement):

```
~L(N) = {x ∈ Σ* | x must include 'aba' and x must end with 'ab'}

```

# Answer
I tried expanding my comment to a proper answer. It was easier for me to write down the automata and the whole transformation process rather than using some software to generate it, thus I hope my handwriting is legible enough ;) (elsewise let me know)

The resulting **Regular Expression** is $\[\[b^\*ba^\*b\]^\*\cup\[b^\*aa^\*ab^\*b\]^\*\]^\*$

So the language accepted by your NFA ought to be something of the form $L = \\{((b^lba^hb)^\*(b^iba^jab^kb)^\*)^\*|i,j,k,l,h\ge 0\\}^\*$ (I've given a quasi-final form of the language).

The opposite of this language is $\sim L = \mathtt{REG} - L$

PS: Fortunately, a kind sir named Hendrik Jan observed that my conversion omits the fact that 2 is also a starting point. The solution is **still holds for starting point 1**. Now that you got an idea about NFA to REG conversions, I'll leave the REG determined by **starting point 2** to you. :)
> 3 votes

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


# Question
Title: How to build a parser for syntactic analysis of regular expressions?
Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages?

**My guess**

Given a regular expression *r*, build its FSA, then obtain the grammar that generate *r* in order to build a parse tree

# Answer
> 1 votes
It is absolutely possible and you are on the right track. You will need to make sure your grammar is %100 correct and probably LL(1), from there you can choose one of many algorithm examples that are out there or write your own.

See https://en.wikipedia.org/wiki/Top-down\_parsing and https://en.wikipedia.org/wiki/LL\_parser

Word of warning: The tricky part won't be the implementation but getting your grammar right.

---
Tags: regular-languages, regular-expressions, parsers
---


# Question
Title: Is what the all-zeroes instruction does considered in machine instruction design?
I remember using a simulated machine with with a minimal instruction set in university. In particular I remember that the instruction that consisted of all zeroes loaded was a `LOAD` instruction. So, if you made a mistake and began executing empty memory then it would simply keep executing until it ran out of address space.

`x86` appears to perform an `ADD` on empty memory, so similar behaviour to the example above.

All zeros in `6502` on the other hand, corresponds to the BRK instruction which activates a software interrupt so executing empty memory quickly puts the machine in a known state.

My understanding is that `6502` was designed to be written by humans, whereas (at least modern) `x86` is designed for compilers to output. Historically, when a machine instruction set is designed, how much attention has been paid to the specific representation each instruction has, given that it can have real effects? I've focused on what the all-zeroes instruction does because I expect that would be the most common instruction to be accidentally executed, but I'd be interested in considerations relating to other instruction representations as well.

# Answer
In general ease of decoding and code density seem to be given more emphasis when designing an instruction encoding than catching the accidental execution of data (though the danger of nop slides is well known).

Catching the all-zeroes case is rather inexpensive and a number of ISAs specify that such will *always* be an illegal instruction; e.g., RISC-V (The RISC-V Instruction Set Manual, Volume I: User-Level ISA, Version 2.1: "We reserve all-zero instructions to be illegal instructions to help trap attempts to execute zero-ed or non-existent portions of the memory space. The all-zero value should not be redefined in any non-standard extension. Similarly, we reserve instructions with all bits set to 1 (corresponding to very long instructions in the RISC-V variable-length encoding scheme) as illegal to capture another common value seen in non-existent memory regions.") and Power (Power ISA, Version 2.07: "An instruction consisting entirely of binary 0s is guaranteed always to be an illegal instruction. This increases the probability that an attempt to execute data or uninitialized storage will result in the invocation of the system illegal instruction error handler.")

One might expect memory access protection mechanisms to prevent accidental execution of data, but special casing the all-zero instruction is an inexpensive means of providing a slightly deeper defense. (In addition, some embedded processors do not provide any memory protection.)

Mitch Alsup (a semi-retired computer architect) has designed a RISC-inspired ISA that has a somewhat broad range of illegal instructions meant to catch executing data. From a comp.arch post: "And in particular, opcodes near integer zero are decoded as unimplemented, and Opcodes near FP one (~10\**-5 to ~10\**5) are also decoded as unimplemented; in both positive and negative senses." "Thus jumping into data is highly likely to result in attempting to execute an unimplemented instruction."
> 2 votes

---
Tags: computer-architecture, programming-languages, history, user-interface
---


title: DFS on weighted graphs

text:
# Question
Title: DFS on weighted graphs
I have the following weighted graph with connected nodes. I've made some connections red just to be easier on the eye.

I am applying DFS on this graph and I am not sure if this is correct because on theory DFS takes the first node and that implementation is easy when the graph isn't weighted so we apply alphabetically order. But on weighted graph it's more complicated.

My output solution : `1-3-6-2-5-8-9`

Graph front (step by step):

```
(1)
(3 2)
(6 5 2)
(2 7 5 2)
(5 4 7 5 2)
(8 7 4 7 5 2)
(9 4 7 4 7 5 2)
(4 7 4 7 5 2)

```

My solution is based on the weights, the nodes are coming to the front on ascending order. They key moment on my solution was when it was on node `6` and moved to `2` because `2` wasn't visited. I need some guidance when it comes to weighted graphs and DFS.

# Answer
> 4 votes
To be short, performing a DFS or BFS on the graph will produce a spanning tree, but neither of those algorithms takes edge weights into account. (Source).

So if you apply the DFS algorithm to a weighted graph it would be simply **not** consider the weight and print the output. If you want to identify the shortest path, you would use Dijkstra Algorithm

I suggest you to read these slides from a Data Structures & Algorithm Coruse

# Answer
> 1 votes
DFS do not use weights in any case. In your solution, you are taking the least weight path for DFS. Your solution is okay, I guess. Just add one more clause in your algorithm. That if the least weight path leads to a node that is already visited, then visit the path with the second-lowest weight and so on for each node pushed in the stack. For each connected component, you will get a tree.

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


# Question
Title: Why is the A* search heuristic optimal even if it underestimates costs?
A\* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus on being admissible at the moment).

But why does it always find the optimal solution if the heuristic underestimates? For example, if it underestimates a non optimal path by more than what it underestimates the optimal one, isn't that equivalent to over estimating?

# Answer
> 23 votes
A\* maintains a priority queue of options that it's considering, ordered by how good they might be. It keeps searching until it finds a route to the goal that's so good that none of the other options could possibly make it better. How good an alternative might be is based on the heuristic and on actual costs found in the search so far.

If the heuristic underestimates, the other options will look better than they really are. A\* thinks those other options might improve the route, so it checks them out. If the heuristic only underestimates by a little bit, maybe some of those routes will turn out to be useful. On the other hand, if the heuristic overestimates, A\* can think that the alternatives to the route already has are all terrible, so it won't bother to look at them. But the heuristic overestimates so they might be much better than they seem.

For example, suppose you're trying to drive from Chicago to New York and your heuristic is what your friends think about geography. If your first friend says, "Hey, Boston is close to New York" (underestimating), then you'll waste time looking at routes via Boston. Before long, you'll realise that any sensible route from Chicago to Boston already gets fairly close to New York before reaching Boston and that actually going via Boston just adds more miles. So you'll stop considering routes via Boston and you'll move on to find the optimal route. Your underestimating friend cost you a bit of planning time but, in the end, you found the right route.

Suppose that another friend says, "Indiana is a million miles from New York!" Nowhere else on earth is more than 13,000 miles from New York so, if you take your friend's advice literally, you won't even consider any route through Indiana. This makes you drive for nearly twice as long and cover 50% more distance. Oops.

# Answer
> 5 votes
It is true that if it underestimates a non-optimal path by more than it underestimates the optimal one, then it will explore down those paths before exploring down the optimal one. What is important, and this is what admissibility guarantees, is that while it is exploring down those non-optimal paths it will not find the goal and finish the search before exploring down the optimal path. This is because as it goes down those non-optimal paths, even though they seem great at first, the cost/length of them will start to add up and at some point the algorithm will return to explore down the optimal path. If we were allowed to overestimate the cost to the goal and did so down the optimal path, then we might actually go down the non-optimal path and find the goal (which terminates the search, and therefore prevents us from ever exploring the optimal path).

# Answer
> 2 votes
The important difference between A\* and Best-First search is that A\* combines the value given by the estimate function $e$ with the length of the (shortest currently known) path to the node under consideration.

Suppose your optimal path to the goal has length $k$; then the estimate for your starting state is at most $k$, and for the $i$-th node along the optimal path, the estimate is at most $k-i$. This gives a bound for how far the algorithm will follow any spurious path $p$; as soon as you have taken more than $k$ steps along $p$, the currently explored prefix of the optimal path will look better, and $p$ will be abandoned.

Essentially, A\* search sits in between Breadth-First (uninformed, guaranteed to find a shortest path, but slow) and Best-First (guided by an estimate function, potentially fast, but very dependent on the quality of the estimates).

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


# Question
Title: Can epsilon be in the input alphabet of an FST?
Can epsilon be in the input alphabet of an FST ?

# Answer
The alphabet $\Sigma$ of an automaton can be *any* nonempty set of finite symbols. Surely Greek-speakers would be upset if we forbade $\\{\alpha, \beta, \dots, \epsilon, \dots, \omega\\}$ as a valid alphabet! If you want, you can use $\\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\\}$ as your alphabet. Or $\\{A, \alpha, \clubsuit,8\\}$. Or any other finite, nonempty set.

However, certain symbols have special meanings and we tend not to use them in automaton alphabets. For example, if you want your alphabet to consist of the symbols $\\}$ and $\\{$, things get a bit awkward: you start writing $\Sigma = \\{\\},\\{\\}$ and, er, yeah, that doesn't quite work. Likewise, it's confusing if $\Sigma$ contains symbols such as ${}^\*$, $($, $)$, $+$ and so on: you can easily write $\Sigma = \\{{}^\*, (, ), +\\}$ but, now, when you try to write regular expressions over that alphabet, it's impossible to tell which characters in the regular expression are symbols from $\Sigma$ and which are operators in the regular expression.

$\epsilon$ fits into this second class. When $\epsilon$ isn't in the alphabet, we use that symbol to denote the empty string. As such, if you include $\epsilon\in\Sigma$, it becomes unclear whether writing "$\epsilon$" means "the empty string" or "the string containing one symbol, which is the Greek equivalent of 'e'". So, as a practical matter, we usually prefer not to use $\epsilon$ as a symbol in the alphabet. If you do need to include $\epsilon$ in your alphabet, you should use some other symbol to denote the empty string and you should say so. Similar reasoning applies to all other symbols that could be confused in this and other ways.
> 4 votes

# Answer
Basically, the epsilon (denoted by $\epsilon$) is a string, namely *empty string* (altrenatively denoted by $\lambda$) cannot be a part of an alphabet since a string itself consists of finite sequence of elements of the alphabet, i.e., *symbols*. Empty string is a string of length zero and so it is not a symbol by definition.

Furthermore, by the formal definition of finite automata, the input alphabet is defined as a finite set of symbols, i.e., not strings and hence the empty string cannot be an input symbol.

However, epsilon is allowed as a part of the input in generalization of NFA, called *NFA with $\epsilon$-moves*. In this case the transition function is defined as a function from $\Sigma \cup \\{\epsilon\\}$ into $2^Q$. But epsilon is still not a member of alphabet it is just a part of definition of the transition function.
> -1 votes

---
Tags: automata, finite-automata
---


# Question
Title: How to prove that matrix inversion is at least as hard as matrix multiplication?
Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication problem to solve matrix inversion problem.

**My question:** How to prove that matrix inversion is at least as hard as matrix multiplication?

# Answer
> 18 votes
If you want to multiply two matrices $A$ and $B$ then observe that $$\begin{pmatrix}I\_n&A&\\\&I\_n&B\\\&&I\_n\end{pmatrix}^{-1}= \begin{pmatrix}I\_n&-A&AB\\\&I\_n&-B\\\&&I\_n\end{pmatrix}$$ which gives you $AB$ in the top-right block. It follows that inversion is at least hard as multiplication.

EDIT: I had misread the question, the original answer below shows that multiplication is at least as hard as inversion. Based on the wikipedia article: write block inverse of the matrix as $$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}A^{-1}+A^{-1}B(D -CA^{-1}B)^{-1}CA^{-1}&-A^{-1}B(D -CA^{-1}B )^{-1}\\\-(D-CA^{-1}B)^{-1}CA^{-1}&(D-CA^{-1}B)^{-1}\end{bmatrix}}.$$ Note that $A$ is invertible because it is a submatrix of the original matrix (which is invertible). One can prove that $D-CA^{-1}B$ is invertible because of the following identity ($M$ is the original matrix): $$\det(M)=\det(B)\det(D-CA^{-1}B).$$ Some clever rewriting using Woodbury identity gives $$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}X&-XBD^{-1}\\\-D^{-1}CX&D^{-1}+D^{-1}CXBD^{-1}\end{bmatrix}}$$ where $$X=(A-BD^{-1}C)^{-1}.$$ Let $C(n)$ denote the complexity of matrix inversion for a $n\times n$ matrix. Let $\omega$ be the exponent of the best matrix multiplication algorithm, so that we can multiply two $n\times n$ matrices in time $O(n^\omega)$. Using the formula above, we can express the inverse of an $n\times n$ matrix using:

* two inverses of half-size ($\frac{n}{2}\times\frac{n}{2}$): $D$ and $X$
* six multiplications of half-size: $BD^{-1}$, $(BD^{-1})C$, $X(BD^{-1})$, $D^{-1}C$ and $(D^{-1}C)(XBD^{-1})$
* two additions of half-size

This gives the recurrence $$C(n)=2C(n/2)+6O((\tfrac{n}{2})^\omega)+2O((\tfrac{n}{2})^2).$$ Since $\omega\geqslant 2$, we rewrite the above as $$C(n)=2C(n/2)+O(n^\omega).$$ We can now apply the Master theorem. Using the notation of the wikipedia article, we have $f(n)=Kn^\omega$ for some constant $K$, $a=b=2$ thus $c\_{crit}=\log\_22=1\<\omega$. On the other we have a regularity condition on $f$ since $$af(n/b)=2K(\frac{n}{2})^\omega=2{1-\omega}Kn^\omega\leqslant \frac{1}{2}f(n)$$ because $\omega\geqslant 2$. Thus the theorem tells us that $$C(n)=O(f(n))=O(n^\omega).$$ It follows from that multiplication is at least as hard as inversion.

---
Tags: complexity-theory, lower-bounds, matrices, numerical-algorithms
---


title: Meaning of $|w| ≡ 2 \mod 3$

text:
# Question
Title: Meaning of $|w| ≡ 2 \mod 3$
I'm new to formal language and automata theory and I was left alone with this exercise. The task is to define a formal grammar for given language.

$Σ \in \\{a,b\\}$

$L = \\{ w \in Σ^\*\\, |\\, |w| \equiv 2 \mod 3 \\} $

I already solved tasks of that kind, but now i struggle to understand what $|w| \equiv 2 \mod 3$ means. $|w|$ means the length of $w$ right? Does $\equiv 2 \mod 3$ mean that $|w|$ should be $2$ (because 2 modulo 3 is 2)?

# Answer
Yes, $|w|$ is the length of $w$.

So $|w| \equiv 2 \mod 3$ means that the length of w divided by three should have the remainder 2. It should be from the set $\\{2, 5, 8, \dots\\}$.
> 4 votes

---
Tags: formal-languages, formal-grammars, modular-arithmetic
---


# Question
Title: What is this operator in "The Temporal Logic of Programs" Pnueli 1977?
In The Temporal Logic of Programs there is an operator first appearing on page 3 (48) under "Partial Correctness" that looks like an elongated super set symbol. What is it?

# Answer
> 3 votes
It's implication as indicated in en.wikipedia.org/wiki/List\_of\_mathematical\_symbols

---
Tags: linear-temporal-logic, program-correctness
---


# Question
Title: How are conditionals implemented at hardware level?
Can anyone explain how are conditionals implemented in the CPU?

Is special circuitry used?

# Answer
> 3 votes
The semantics of any non-jump CPU instruction is to increment the program counter PC (a.k.a. instruction pointer) so that the subsequent instruction can be executed next.

Uncoditional jumps overwrite PC with a new, fixed value, written in the instruction. (Or, for relative jumps, add to PC said value)

Conditional jumps instead consider two possible values for PC: one pointing to the next instruction, another written inside the instruction (possibly as a PC increment, for relative jumps). Then, they test some given register, obtaining a bit. For instance, the register might be a flag, which is taken as is. Otherwise, the register might be tested for parity, sign, zero, etc. so to obtain a single bit. This bit controls which one of the two PC values is the one to write in the PC register. Usually, a hardware 2-to-1 multiplexer is responsible to choose between the two ones, exploiting the control bit.

# Answer
> 1 votes
The basis of the if condition is the conditional jump. That means that a jump is taken only if a certain condition it true.

A non-conditional jump is a write to the program counter register. So a condition jump inhibits the write if the condition is not true.

---
Tags: computer-architecture, cpu
---


# Question
Title: Find multiple duplicates in $n$ size data set in linear time
Problem:

> Given a vectors of size $n$ with integer data within $\[1, n-1\]$ range, find $if$ and $which$ numbers are multiple duplicates (numbers appearing more than once). The time complexity ought to be linear and space complexity constant (don't use any auxiliary data structure except the input vector and variables) and the input data set ought not to be modified.

I'm trying to solve this problem for at least one multiple duplicate (as a starting point, although I don't know if the solution to this case can be expanded to the general case of at least two multiple duplicates). Here's what I've done so far:

The $if$ part is relatively easy, taken we can be proven using the pigeonhole principle to show that there $will$ be at least a simple duplicate within the given data set.

The $which$ part, on the other hand, is what gives me headaches. Unlike the missing number problem, we cannot simply Xor the numbers. Neither can we sum them up and subtract the sum from 1 to n-1, thus finding a simple duplicate. Can anyone suggest a good approach towards this problem? You are not allowed to modify the input array.

# Answer
This can't be done in constant space.

Let's think first about algorithms that read the entire input array before producing any output. Note that there are exponentially many possible outputs. In particular, the output might include up to $n/2$ different numbers that are "multiple duplicates". Thus, there are at least ${n-1 \choose n/2}$ different possible outputs, and ${n-1 \choose n/2}$ is $\Theta(2^n/\sqrt{n})$. Now the state of the algorithm (the values of all variables, etc.) before producing output must uniquely determine the output, so that means there must be at least ${n-1 \choose n/2}$ possible states. It requires $\lg {n-1 \choose n/2}$ bits to store that state. It follows that any algorithm that reads all input before producing all output must use at least $\lg {n-1 \choose n/2}$ bits of space; and this is $\Theta(n)$. So any such algorithm must use linear space.

What about algorithms that might produce output as they go? It's still not possible in constant space; such algorithms still need linear space. Consider an input where the first half of the array has no duplicates, and think about the intermediate state of the algorithm at that point. That state must contain enough information to deduce the set of numbers in the first half of the input array (if two such input arrays that differ in their first half produce the same state at this point, then we can construct a way to fill in the second half so that the algorithm is wrong for at least one of those -- just pick a number that appears in the first half of one of those inputs but not the other, and make sure it appears exactly once in the second half). It follows that there must be at least ${n-1 \choose n/2}$ possible states after reading the first half of the input array. As before, it then follows that the algorithm needs $\Theta(n)$ bits of space. So producing output as you go doesn't help -- it still can't be done in constant space.
> 2 votes

---
Tags: algorithms, arrays, searching
---


# Question
Title: Confused about NP-Complete Proof Using Reduction
Consider a job schedule decision problem with only one machine takes input $\\{(r\_1,p\_1,d\_1),(r\_2,p\_2,d\_2),...,(r\_n,p\_n,d\_n),K\\}$; where $r\_i$ is the start time for the ith triple, and $p\_i$ is the process time of the triple; and $d\_i$ is the deadline.Require for each $i$, schedule a job at time $t\_i$ such that $r\_i≤t\_i≤d\_i−p\_i$. Goals to decide whether we can schedule $K$ number of compatible jobs.

I try to show that this problem is at least as hard as SubsetSum problem.

Consider a instance of input to SubsetSum. $\\{a\_1,a\_2,..a\_n;T\\}$

Assume that $∃ I⊆\\{1,2,..n\\}$ such that $∑\_{i∈I}a\_i=T$; then we can design a transformation such that assigns a subset $\\{r\_i,p\_i,d\_i\\}$ some value, and show that taking this set as input to schedule problem will also return True. For example, assign start value to each of job to be 0, process time for each job to be $a\_i$, deadline for each job to be $\sum\_{i\in I} a\_i$. I have prove the $\implies$ direction

However, my problem here is about doing converse proof. We have to show that schedule decision problem taking an instance return true implies that SubsetSum taking kind of "inverse transformation" of that instance also returns true.

My understanding of prove converse direction is that we need some sort of inverse transformation. For example, given any arbitrary set of triple $\\{(r\_i,p\_i,d\_i)\\}$, if this set accepted by schedule problem, then we need to find some "inverse transformation" transform the triples into some array, and a target value that can be accepted by SubsetSum. And this "inverse transformation" compose with our original transformation (designed for ($\implies$) direction proof) should be some identify transformation.

OR

Can we only give the input that has start value to each of job is 0, process time for each job is $p\_i$, deadline for each job to be $\sum\_{i\in I} p\_i$. Basically, use the transformed input from the direction of ($\implies$)

And assume that this set of input accepted by schedule decision problem, we want to show that using the sum over process time and the deadline time as input to SubsetSum can also return true.

I don't which approach is correct here

# Answer
> 0 votes
Your solution is a far way off from being correct. It seems that you are trying to use different transformations for both directions of the proof, while you should actually be using a single transformation from subset sum to the scheduling problem.

> I try to show that this problem \[scheduling\] is at least as hard as SubsetSum problem.

Subset Sum is a hard problem; we don't think it's likely that it can be solved in polynomial time. If you want to show that scheduling is hard, then you need to show that *if we could solve scheduling in polynomial time, then we can also solve subset sum in polynomial time*.

What you are given is an instance of subset sum $\\{a\_1,a\_2,\ldots, a\_n; T\\}$ and a magic machine that somehow solves the scheduling problem in polynomial time. We want to show that it is unlikely that this magic machine could exist, therefore we will show that using this magic machine we can solve subset sum in polynomial time (which we think is probably not possible).

For this, you need *a transformation that takes an instance $A$ of subset sum as input, and gives as output an instance $B$ of the scheduling problem*, such that $A$ has a feasible solution if and only if $B$ does. That is, being able to find a solution for $B$ (in polynomial time) will also let you find one for $A$ (in polynomial time).

> Assume that $∃ I⊆\\{1,2,..n\\}$ such that $∑\_{i∈I}a\_i=T$; then we can design a transformation such that assigns a subset $\\{r\_i,p\_i,d\_i\\}$ some value, and show that taking this set as input to schedule problem will also return True. For example, assign start value to each of job to be 0, process time for each job to be $a\_i$, deadline for each job to be $\sum\_{i\in I} a\_i$.

You can't do this. You can't base the transformation on the assumption that the subset sum instance is solvable. You don't know $I$ (because this is the hard-to-compute thing you're trying to compute), so you can't use it to construct the transformation. You can only use $I$ to show that, the transformed instance - which you constructed without knowledge of $I$ - has a solution.

Hint: you need to design an instance of the scheduling problem that is forced to split the jobs into two groups (one summing up to $T$, one to $\Sigma a\_i - T$). For this, it might be useful to have one or two additional jobs that must be scheduled at a fixed point in time (by setting $r\_i+p\_i=d\_i$).

To summarize: a correct NP-hardness proof consists of the following steps:

1. Take an NP-hard problem (e.g., subset sum) and design a transformation $f$ that maps an instance $A$ of this problem to an instance $B=f(A)$ of the problem you want to show NP-hard (e.g., scheduling).
2. Show that, if $A$ has a solution (is a yes-instance), then $B$ is a yes-instance
3. Show that, if $B$ is a yes-instance, then $A$ is a yes-instance (or show the converse: if $A$ is a no-instance (has no solution) then $B$ is a no-instance as well.

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


# Question
Title: Unambiguous grammar for regular expressions
How to define a non ambiguous grammar for regular expressions on the $\Sigma = \\{a,b\\}$ alphabet?

Given that:

If $\Theta = \\{+, ^\*, (,),\cdot, \emptyset\\}$ is a set of symbols

A *regular expression* on $\Sigma$ is a string such that one of the following condition applies

1. $r = \emptyset$
2. $r \in \Sigma $
3. $r = (s+t)$ or $ r = (s\cdot t)$ or $r = s^\*$

# Answer
I need to define a *context free grammar* to recognize regular expression. I know also that CF grammars are used to recognize mathematical expressions. so the grammar $G$ should recognize regular expressions.

$G:$

$ E \rightarrow E + T \mid T $

$ T \rightarrow T \cdot F \mid F $

$ F \rightarrow(E) \mid E^\* \mid a\mid b\mid\emptyset$
> 3 votes

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


# Question
Title: IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory
Recently it's been in the headlines that IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory. This is several thousand times smaller than one would expect the memory requirements of such a simulation to be. How were they able to do this? Did their simulation run correspondingly faster? Does the capacity to simulate quantum computers this way using conventional algorithms have any impact on our current understanding of the capabilities of quantum computers when compared to classical ones?

# Answer
> 4 votes
This blog post by Scott Aaronson gives a overview of why this simulation does not change anything about our understanding of quantum computers.

Maybe the best way to understand why is to understand what computer scientist are trying to prove at the moment: "quantum supremacy". The idea is to show that quantum computers can solve **some** problems much faster than classical computer (I insist on **some** because we know quantum computer only provide a speedup for some classes of problems but not all.) Now in theory we already have strong evidence that this the case because of Shor's algorithm:

* a quantum computer can factor a $b$-bit integer in time roughly $O(b^3)$
* the best known classical algorithm to factor $b$-bit integer runs in time $e^{kb}$ for some constant $k$
* one can verify if a factorization is correct with a classical computer in time $O(b^3)$

From this one can derive a "practical proof" that quantum computers provide a speedup of classical computers as follows:

* generate a random integer with $b=10000$ bits
* run Shor's algorithm to factor it: this takes maybe a few seconds (or minutes)
* verify answer with a classical computer: takes a few seconds (or minutes)
* factorize the number with a classical computer: takes a millions of years or more

The important fact in this example is that the incredible difference between the quantum and classical computers: a few seconds vs a few million years.

There is one major problem though: to factor an integer that size with a quantum computer, we need to build a quantum computer with many thousands of qubits. At the moment, the largest quantum computer ever built does not even have a hundred. Thus we cannot run the above experience (yet).

This is where Scott Aaronson and the IBM experiment enters the picture. Instead of trying to factor numbers, we want to find another problem as above but where the quantum computer is much smaller so that we can actually build it. One such problem is quantum simulations:

* simulating a quantum system with a quantum computer is very easy (polynomial time)
* simulating a quantum system with a classical computer is very hard (exponential)

So we go ahead and redo our experiment:

* pick a quantum system at random of size $b=100$ qubits
* simulate it with a quantum computer: takes a few seconds/minutes
* simulate it with a classical computer: takes a few million year

Since we can build a quantum computer of that size (~100 qubits), we are done right? Well **no** because how do we know the simulation with the quantum computer was correct? Sure it's fast, but maybe it's wrong! In this case we have not proven anything. You see with factorization, verifying the result is easy, but for simulation it is as hard as the simulation itself... **This is the crucial issue**.

In order to fix this, we want to find a value of $b$ such that the classical computer can still find the answer so that we can verify it but it has to be long enough to demonstrate that the gap between quantum and classical is huge. Researcher are trying to find this *sweet spot*, and think it is around $b=50$ where a supercomputer will take may a few months or year. The IBM paper shows that $50$ is too small. But remember that the simulation for $b=100$ is **trillions** of times harder than for $b=50$ (exponential), thus may the sweet spot is at $b=60$, but it is unlikely that we can ever reach $b=100$.

NOTES: I simplified most of the actual complexity bounds. I ignored the fact that quantum computations only give the correct answer with high probability, one may have to re-run the algorithm several times.

---
Tags: quantum-computing
---


# Question
Title: Solving simultaneous multiple chinese remainder theorem on the quantum computer - possible?
Is it possible to solving simultaneous multiple chinese remainder theorem on the quantum computer?

We have $k$ variables. Each variable can take two values.

The question is: can we calculate all possible circuits equations chinese remainder theorem (which may be $2^k$) and reduce to the smallest result on a quantum computer?

I know the question can be very difficult but I wanted to ask.

I hope I have described the problem quite clearly (but maybe there are ambiguities).

For example we have table:

```
2 3 7 31

A B C D => [RESULT]

0 1 3 4 => 934
0 1 3 27 => 430
0 1 4 4 => 4
0 1 4 27 => 802
0 2 3 4 => 500
0 2 3 27 => 1298
0 2 4 4 => 872
0 2 4 27 => 368

```

Third line:

```
0 1 3 4 => 934

```

means the system of equations:

$x \equiv 0 \pmod 2$

$x \equiv 1 \pmod 3$

$x \equiv 3 \pmod 7$

$x \equiv 4 \pmod {31}$

and solution for this line in CRT (chinese remainder theorem) is 934.

The final result that the algorithm should return (minimum) is **4**. This result is in line:

```
0 1 4 4 => 4

```

This is just an example - I wanted to show to know what I mean.

Someone may have some idea?

Sorry for the (maybe) difficult question.

# Answer
If you prepare a superposition containing the various input problems, a quantum computer will allow you to compute a superposition containing the various outputs.

That being said, I'm not sure why you would want to do this. You only get to sample *one* of the outputs, and you don't get to pick which one. You'll get one of them at random. Presumably you would instead do some quantum computation on the output superposition, perhaps use a QFT to sample from their frequency space... but just remember that this means you must erase the input! Otherwise you won't be able to interfere the various output cases.
> 1 votes

---
Tags: quantum-computing
---


# Question
Title: Can every CFG be converted into an equivalent CFG of this form?
Question:

Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables.

For this question, I have considered that it can be proved by using Greibach Normal Form, because we can get the form: A → aABCDEF... which is similar to the form above: A → xBC or A → ϵ.

However,the pre-condition of Greibach Normal Form is that any context-free grammar which doesn’t produce ϵ. I am not sure whether it can prove with GNF.

Can anyone give me suggestions of this proof ?

# Answer
Since you're allowing $x = \epsilon$ in a production of the form $A \rightarrow xBC$, it seems you can first convert the grammar to Chomsky Normal Form so that every production is of one of the forms $A \rightarrow \epsilon BC$, $A \rightarrow x$, and $A \rightarrow \epsilon$. The only problem is that the productions which produce only a single terminal are not of the form you want, but that isn't too difficult to remedy.
> 1 votes

---
Tags: context-free, formal-grammars, normal-forms
---


# Question
Title: What are barriers to Genetic Programming with cyclic graphs
Genetic programming uses either trees (in case of classical GP) or acyclic graphs (CGP and in a certain sense LGP), to represent evolved programs (phenotypes).

Is there any reason, why cyclic graphs aren't used?

# Answer
Perhaps one reason is that constraints (perhaps somewhat arbitrary ones) would have to be imposed on what it means to interpret a program represented in this fashion.

However, recent work with CGP has actually explored the addition of cycles: Recurrent CGP
> 1 votes

# Answer
It's true that little research has been done on cyclic graph-based GP, but both:

specifically noted the ability of these representations to handle cyclic graphs.

There are also other less well-known papers (but anyway very interesting) that describe cyclic representations and various recombination operators:

Two problems with cyclic GP are:

* evaluation is often performed in an iterated flip-flop fashion and is time consuming;
* memory requirements are greater because in tree-based individuals partial results aren't reused and so can be *discarded* after first use.

Approaches to speed up cyclic GP are described in Strategies to Minimise the Total Run Time of Cyclic Graph Based Genetic Programming with GPUs by T.E. Lewis and G.D. Magoulas (2009).

As noted by NietzscheanAI there is a renewed interest about this topic.
> 0 votes

---
Tags: graphs, genetic-algorithms
---


title: A question on oracle turing machines

text:
# Question
Title: A question on oracle turing machines
I am trying to solve a question from the exercise of this book, pg. 46,section 7.4.

Let $M$ be a deterministic Turing machine that only queries oracle strings that are shorter than the input string. Show that if $A = L(M^A)$ and $B = L(M^B)$ then $A = B$.

I think I have to apply induction. Does it involve self-reducibility concept? Just hints would be sufficient.

# Answer
You can prove by induction that for all $n\in\mathbb{N}$, $A$ and $B$ agree on all the strings in $\\{0,1\\}^{\le n}$, i.e. $A\cap\\{0,1\\}^{\le n}=B\cap\\{0,1\\}^{\le n}$.

The case of $n=0$ follows from the fact that $M$ does not query its oracle on the input $\epsilon$, which means $M^A$ accepts $\epsilon$ iff $M^B$ accepts it. For $n\>0$, let $x\in\\{0,1\\}^{n+1}$ be some length $n+1$ string. We need to prove (under the inductive hypothesis) that $x\in A\iff x\in B$. Suppose $x\in A$, then $M^A$ accepts $x$. Note that on input $x$, $M^A$ queries strings in $\\{0,1\\}^{\le n}$ alone, where $A$ and $B$ agree. This means that replacing the oracle from $A$ to $B$ won't change $M$'s outcome on $x$, hence $M^B$ accepts $x$ and therefore $x\in B$, since $B=L(M^B)$. The same arguments apply in the $x\notin A$ case, which concludes the proof.
> 3 votes

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


# Question
Title: External fragmentation in fixed size partitioning
Can external fragmentation occur in fixed size partitioning ?

I searched everywhere but couldn't find a sentence which says external fragmentation is not possible in fixed size partitioning.

Please someone clear my doubt.

# Answer
You seem to feel external fragmentation should not be possible with a fixed size algorithm – I wonder why?

**Summary**: A fixed size algorithm probably only helps if all requests are for the size it provides.

External fragmentation has, in general, more to do with the order of de-/allocation and the strategy for placement of allocation blocks in the available space than with the size of space allocated for a given request. However, if all requests are for the same single fixed size as the algorithm allows for the caller (i.e. minus any internal overhead), then fragmentation will no longer be a functional problem: although allocated and unallocated blocks may be interspersed, this will not reduce the total number of allocation requests that can be satisfied. There could however be consequences for performance, especially if the algorithm does not maintain a chain of free blocks.
> 1 votes

---
Tags: operating-systems, memory-management
---


# Question
Title: Solving the recurrence $T(n)=T(n−1)/T(n−2)$
How can I solve this? I saw Solving the recurrence $T(n)=T(n-1)\*T(n-2)$ but I don't know how I can apply it to $T(n)=T(n-1)/T(n-2)$?

# Answer
> 5 votes
Then assume $T(0) = a, T(1)=b$ such as $a \neq 0$ and $b \neq 0$. You could write down first few terms and deduce the pattern $$T(0)= a$$ $$T(1)= b$$ $$T(2)= \frac{T(1)}{T(0)} = \frac{b}{a}$$ $$T(3)= \frac{T(2)}{T(1)} = \frac{b/a}{b} = \frac{1}{a}$$ $$T(4)= \frac{T(3)}{T(2)} = \frac{1/a}{b/a} = \frac{1}{b}$$ $$T(5)= \frac{T(4)}{T(3)} = \frac{1/b}{1/a} = \frac{a}{b}$$ $$T(6)= \frac{T(5)}{T(4)} = \frac{a/b}{1/b} = a = T(0)$$ $$T(7)= \frac{T(6)}{T(5)} = \frac{a}{a/b} = b = T(1)$$ $$...$$ Thus the values of $T(n)$ repeat with period of $6$.

# Answer
> 2 votes
If you are dealing with a recurrence for which you have no idea how to attempt the solution, it is always a good idea to try working out the first few terms by hand (or using software such as Excel). If you try this, the solution for this recurrence will probably be quite obvious...

---
Tags: recurrence-relation
---


# Question
Title: Prove that Integer linear programming (ILP) is in NP
Help is needed, I've tried to solve it by myself but I could find any reasonable solution which is solid enough. this is what I've wrote:

> Consider a 0-1 ILP, where each variable x1,x2...,xn can assume values 0 or 1. The number of constraints is m.
>
> We can choose all possible 2n assignments of x1, x2...xn in non-deterministic manner.
>
> Checking the feasibility of each assignment takes O(nm) time, and Computing the value of the objective function for each feasible assignment takes O(n) time Since a nondeterministic manner considers all assignments simultaneously. Thus, we have a non-deterministic polynomial time.
>
> Due to Karp

Please provide a better solution

# Answer
> 0 votes
As stated in the comments, you can show that a problem is in NP by demonstrating the existence of a polynomial time verifier. In this case, such a verifier would be provided the *values* of $x\_1, x\_2, \dots, x\_n$, and would need to answer the question "do these values of $x\_1, \dots, x\_n$ form a solution"? In this case, all you need to do is check that all $m$ contraints are satisfied.

---
Tags: complexity-theory, np, integer-programming
---


# Question
Title: Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time?
I have a graph with n edges and m vertices. This is an **undirected** graph.

I need to find a 3 vertex cycle. Only 3.

I'm confident I need to use an incidence matrix for this as this seems to be the best data structure. I'm familiar with cycle finding algorithms and they are all in crazy polynomial or even exponential time.

However those are for general cycles. Not 3 vertex cycles. I have O(n\*m) time.

Any ideas on how to find this 3-vertex cycle in an undirected graph using an incidence matrix?

First off you can discard any row with less than 2 "1"s. Then I think I need to see some kind of a pattern in the matrix for the 3 vertex cycle. Not seeing it at the moment.

EDIT Current idea:

1. Set up an array of vertices.
2. Go ---\> in the matrix and build edges by assigning them in the matrix.
3. Each time edge is assigned check if that edge on both sides has a vertex with 2+ edges out.
4. If it has check if any of those edges out go to the same vertex \[compare both lists for direct outward vertices from both sides of this edge\].
5. If it's the same must be a 3 vertex loop.

I guess that's like rebuilding from incidence matrix to incidence list.

I'm looking at the below image from wikipedia:

https://en.wikipedia.org/wiki/Incidence\_matrix

# Answer
> 1 votes
Let's assume first that your graph is connected, so that $m \geq n-1$. Convert your incidence matrix into an adjacency matrix in time $O(n^2) = O(nm)$. Now go over all $m$ edges, and for each edge $(i,j)$, go over all vertices $k$ and check in $O(1)$ whether $i,j,k$ is a triangle in the graph (using the adjacency matrix), for an overall running time of $O(nm)$.

If your graph is not connected, then use DFS/BFS to find its connected components, and run the procedure above on each of them. Assuming that the $i$th connected component consists of $n\_i$ vertices and $m\_i$ edges, the running time is $O(\sum\_i n\_i m\_i) \leq O(\sum\_{ij} n\_i m\_j) = O(nm)$.

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


# Question
Title: Finding the number of intersections of $n$ line segments with endpoints on two parallel lines
Let there be two sets of $n$ points:

$A=\\{p\_1, p\_2, \dots, p\_n\\}$ on $y=0$

$B=\\{q\_1, q\_2, \dots, q\_n\\}$ on $y=1$

Each point $p\_i$ is connected to its corresponding point $q\_i$ to form a line segment.

Example:

I need to write a divide-and-conquer algorithm which returns the number of intersection points of all $n$ line segments and runs in $O(n logn)$.

I was reading about Sweep Line Algorithm but found out its complexity depends on the number of intersections, which can be ${O}{n\choose 2} \subseteq O(n^2)$ (besides the fact that it isn't a divide-and-conquer algorithm). I believe I should use the fact that each set of points has the same $y$ value, but I'm not sure how. Any suggestions?

# Answer
> 6 votes
Since all points are distinct, this is a version of the Counting Inversions problem. First, sort the points $p\_1, \dots, p\_n$ in order of increasing $x$ coordinate to obtain an ordered list $p\[1\],p\[2\], \dots, p\[n\]$. We now relabel the points $q\_1, \dots, q\_n$ with respect to this new ordering of the $p$'s such that $p\[i\]$ and $q\[i\]$ are endpoints of a line segment, for all $1 \leq i \leq n$. Altogether, these steps take $O(n \log n)$ time.

Now, we want to count the number of inversions in $q\[1\], \dots, q\[n\]$; an inversion is a situation where $i \< j$ and $q\[i\] \> q\[j\]$ (we compare the points by their $x$ coordinates). This is because $i \< j$ implies $p\[i\] \< p\[j\]$ by construction, and $p\[i\] \< p\[j\]$ and $q\[i\] \> q\[j\]$ if and only if the line segments $(p\[i\], q\[i\])$ and $(p\[j\], q\[j\])$ intersect. Hence, the number of line segment intersections is precisely the number of inversions in $q\[1\], \dots, q\[n\]$.

There is a well known divide and conquer approach for counting these inversions. Can you take it from here?

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


# Question
Title: Find a particular connected graph within a complete graph keeping all vertices
My problem is as follow, imagine a complete undirected graph with weighted edges, i would like to extract a connected graph keeping all the vertices and where the edge with the highest weight is the minimum one compared to all others possible configurations.

Is there another solution than bruteforce it.

# Answer
> 3 votes
Clearly you can focus on trees, since removing edges can only reduce the weight of the maximal edge. What you're looking for is called a minimum bottleneck spanning tree, and an MST is also a minimum bottleneck spanning tree.

To see why, suppose for the purpose of contradiction that $T$ is an MST which does not minmize the maximum weight. Let $(u,v)$ be the maximal weight edge in $T$, and $T'$ be a minimum bottleneck spanning tree. By our assumption $(u,v)\notin T'$, hence there exists a path from $u$ to $v$ in $T'$ which does not contain $(u,v)$, let us denote this path by $P$. Note that all the edges in $P$ are lighter than $(u,v)$. Remove $(u,v)$ from $T$, now $u,v$ are in different connected components. Suppose $P=(w\_1=u,...,w\_k=v)$, and denote by $i$ the minimal index such that $w\_i$ and $w\_{i+1}$ are in different connected components in $T\setminus\\{(u,v)\\}$. Now, $\left(T\setminus\\{(u,v)\\}\right)\cup\\{(w\_i,w\_{i+1})\\}$ is a spanning tree of $G$ with smaller weight, contradicting the fact that $T$ is an MST.

---
Tags: graphs
---


# Question
Title: Construct a computable function from non-computable funciton
Let $f\_1 $ and $f\_2$ be two functions from $\mathbb{N} \rightarrow \mathbb{N}$.

$f\_1$ is turing-computable while $f\_2$ is not.

$h(i)$ is a function that returns $1$ when $f\_1(i) = f\_2(i)$ and $0$ else.

The challenge is to construct $f\_1 $ and $f\_2$ so that $h(i)$ is computable and additionally so that it is not.

My thought process is that for either scenario we have to use the computability and non-computability property and pass that forward to $h(i)$ but I am not sure how.

One thought I had to make $h(i)$ uncomputable is to define $f\_2$ and $f\_1$ on a for a small set of numbers and let $f\_2$ be uncomputable on all other numbers. This way I cannot compute if $f\_2 = f\_1$ so I cannot compute wether $h(i)$ outputs $1$ or $0$.

But I dont know how to make $h(i)$ computable given the requirements that $f\_2$ be uncomputable.

Can anyone nudge me in the right direction ?

# Answer
> 2 votes
There are many ways to do this, here is one example.

To make $h$ uncomputable, you can choose $f\_1$ to be the constant $1$ function, and $f\_2$ to be any non computable binary function, i.e. whose range is $\\{0,1\\}$. In that case $h=f\_2$ is not computable. In fact, when $f\_1,f\_2$ are binary functions, $h$ is never computable (why?).

To make $h$ computable you can let $f\_1$ be the constant $1$ function, and $f\_2$ be any non computable function whose range is $\mathbb{N}\setminus\\{1\\}$. In that case $h$ is zero everywhere.

---
Tags: computability
---


# Question
Title: How do you translate these 2 regular languages in words correctly?
Given are 2 different languages and I'd like to know if I understand them correctly.

L ⊆ ∑\* is a regular language.

1. cycle(L) = {vu ∈ ∑\* | uv ∈ L}
2. L/2 = {x ∈ ∑\* | ∃y ∈ ∑\* : xy ∈ L, |x| = |y|}

I need to know that because the actual task is to show that these languages are regular by either describing how you build a DFA or NFA for them.

But I just like to know if I understood them correctly.

---

So 1. means that every word has an existing reverse.

As example we have word `aaa` and `bab`, if we concatenate them, we have `aaabab`. Now the language says that there is also a word `babaaa`

2. Means that we have two words of same length and we concatenate them?

# Answer
For 1. it is not quite the reverse; it happened to be a reverse in your example. So if $u = aab$ and $v = abb$ and $uv \in L$, then you know $vu = abbaab \in \text{cycle}(L)$, but you wouldn't be able to say that $bbabaa = v^Ru^R \in \text{cycle}(L)$.

For 2. it is not that you want the concatenation of two strings of equal length, but rather you only want the first half of even-length strings in $L$. That is, if, say, $aabbabbabb \in L$, then $aabba \in L/2$.
> 2 votes

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


# Question
Title: Emergent complexity and Turing Completeness
Is there some link between the concept of emergence and Turing Completeness? The ideas feel intuitively like they might be linked, but I can find nothing online.

The idea came to me because I was exploring Conway's Game of Life, and it was hard not to suppose a link between these two properties.

**Edit:** In response to Raphael's point, I have a clarification to the question (which I thought was implied, but in hindsight, it really wasn't)

*Must it be the case that systems that exhibit weak emergent complexity are also Turing Complete?*

# Answer
I suggest you to give a look to S. Wolfram's book "A New Kind Of Science" (that is also available online).

The centeral ideas are:

Though these ideas are probably not new, they are exposed in a fascinating way (to be honest, a rather informal and non-mathematical "way").
> 1 votes

---
Tags: turing-completeness
---


# Question
Title: Computational complexity vs Computational cost
Is there a difference between the computational complexity and computational cost of an algorithm?

# Answer
To answer your question as stated: "computational complexity" typically refers to the $\Theta$-class of a certain (often implicit) measure of computational cost.

That said, I prefer to use the terms like this:

* Use "complexity" when talking about *problems*. For instance, you can say "sorting has $\Theta(n \log n)$ worst-case time complexity (in the comparison model)".
* Use "costs" when talking about *algorithms*. You would say, "Mergesort has a worst-case running-time cost in $\Theta(n \log n)$ (under the RAM model)".

This is consistent with common use, that is every expert will understand what you're saying, but avoids using the term "complexity" for different things.

### Rationale

1. Complexity theory and analysis of algorithms (AofA) are distinct fields with different goals and techniques. It's not helpful to use terminology that muddles the two together.

Side note: teaching only the complexity-theory side of things makes large parts of the AofA literature inaccessible to computer science graduate, which I think is a shame. See the work of Flajolet and Sedgewick if you're interested in these things.
2. "Cost", other than "complexity", is used for *precise* measures like, say, "the number of comparisons" often analysed in sorting. Such a cost measure is (given an algorithm and a machine model) a well-defined function on the inputs (other than "time") and can be analysed rigorously.
3. Every algorithm has *many* cost measures with different asymptotic behavious; in sorting, for instance, number of comparisons, swaps, and many more. Therefore, asking for "*the* complexity of the algorithm" is an oversimplification, and only meaningful under certain assumptions/conventions.
4. The analysis of cost measures can yield testable hypotheses, if it's more precise than Landau bounds. "Complexity" results are not testable.
5. "Complexity" of an algorithm can be rigorously defined in terms of cost measures, if one so desires. The other way around does not work.

For instance, an algorithm's "(time) complexity" is usually taken to mean the $\Theta$-class of dominant, additive cost measure that is defined by a function on basic operations. However, I consider this practice confusing and thus harmful (cf. item 1), and prefer to say "\[cost measure\] is in $\Theta(\\\_)$".
> 8 votes

# Answer
My approach is as following.

Computational complexity is an abstract notion having a precise mathematical definition and a field of a whole scientific research.

"Computational cost" is alternatively used for "computational complexity", though in my opinion I would not use the term "computational cost" in the formal meaning instead of "computational complexity".

The most significant difference between "complexity" and "cost" is that the "complexity" is precise mathematical measure measured using big-O notation, we usually say "space complexity" or "time complexity" where both terms "space" or "time" are abstract, i.e., by "space" we might mean RAM or HardDisk storage, while "time" might mean milliseconds, seconds, or even hours. "Cost", on the other hand, is real-life, physical, concrete measure. For example we say "it costs 2 Gigs" or "it costs 2 TB of disc space".

Let me support my point of by example. Suppose we have come up with two different algorithms solving the same problem and we have estimated exact number of operations for both algorithms, say, $n^2 + 100n$ and $0.2n^2$. We do not need to implement both algorithms in order to conclude that their complexity are equal and are $O(n^2)$. From point of view of computational complexity these algorithms have equal efficiency. However, to measure the cost of these algorithms we need to implement them, run on a computer, and measure how much time they take (in milliseconds, seconds, minutes...). This is cost and we'll obviously get different time measures for $n^2 + 100n$ and $0.2n^2$ algorithms. Thus comparing their costs we may choose a better algorithm for practical use.
> 2 votes

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


title: Finding median from given range

text:
# Question
Title: Finding median from given range
What is the most effective way of finding median from $N$ numbers within given range ? It is guaranted that $N \leq 10^{9}$.

The input consists of $L$ lines.

Each line consists either of:

a) `S X` , which means store number $X$, where $X \leq 10^{9}$.

or

b)`F X Y`, which means find median from stored numbers within range $(X,Y)$. where $1 \leq X,Y \leq 10^{9}$

For each `F X Y` ( median range request ) it should print the median from all stored numbers within range $(X, Y)$

Example:

Suppose the input:

```
S 20
S 10
S 22
S 30
S 25
F 21 30
S 5
S 7
S 9
F 5 20

```

Output:

```
   Median from range (21, 30) : 25
   Median from range (5, 20) : 9

```

Explanation:

The first median request for range (21, 30) satisfie 3 numbers: `22 25 30` where the median is `25`.

The second median request for range (5, 20) satisfie 5 numbers: `5, 7, 9, 10, 20` and we pick up the median which is `9`.

The mean is not guaranted to be close to median. The requests for storing `S` do not have to go consecutevly.

# Answer
It can be done in $O(L \log L)$ time, which is optimal by reduction from sorting.

Consider a Red-Black Tree $T$ (or any other self-balancing tree) where each node $v$ is augmented with $s(v)$, the number of nodes in the subtree rooted in $v$. Keeping such information updated between insertions is trivial.

In order to show that such structure supports median queries in $\log L$ time, it is sufficient to show that we can perform the following operations in $\log |T|$ time:

* Given $v \in T$, determine $\\#v$.
* Given $n \in \mathbb{N}$, find $v \in T$ such that $\\#v = n$.

To solve the first problem, initialize a variable $x := 0$ and then find $v$. Whenever in the search you are located at a node $w$, if you move right, it means that $v$ is higher than $w$ and each node in the left child of $w$. In such a case, we set $x := x + s(w.left) + 1$. When we reach $v$, we similarly set $x := x + (v.left) + 1$.

After that last update, it will hold $x = \\#v$, that is true because $v$ is the minimum of the tree $T\_L$ obtained starting from $T$ and cutting the left branch every time you moved to the right while searching $v$, and, conversely, the maximum of the analogous $T\_R$.

The second problem can be solved by a similar idea: initialize $x:=0$ to keep track of how many elements you "discarded" by going right, and then perform a dichotomic search.
> 1 votes

---
Tags: algorithms, data-structures, selection-problem
---


# Question
Title: Is a BST considered a data structure or abstract data type
and why?

It seem abstract in that it is and idea created and implemented with nodes arranged a certain way.

But it did not show up in the text here:

https://en.wikipedia.org/wiki/Abstract\_data\_type

Here:

https://en.wikipedia.org/wiki/Binary\_search\_tree

they are referred to as data structure b.c. other ADTs can be created from them.

In this train of thought, can I assume that SLLs and DLLs are data structures as well.

Is is not so black and white, perhaps more of a spectrum of classification?

# Answer
> 1 votes
A binary search tree is a data structure. The interface it supports (the list of operations you can perform on it and their semantics) is an abstract data type.

See https://en.wikipedia.org/wiki/Abstract\_data\_type for explanation of the difference between an ADT and a data structure.

---
Tags: data-structures, binary-trees, abstract-data-types
---


# Question
Title: Is it possible to obtain dynamic tree with two dimensions in big matrix
Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions).

In some of the coordinates of the matrix there are positive numbers and all other fields are zeroes (at most 100000 elements are with value different from 0). For each element we are keeping three values, the $x, y$ coordinate and the value of it.

How could we answer queries of type $q(i, j)$ to return the sum in the fields that are in the submatrix from $(0, 0) \text{ to } (i, j)$.

Is there way to create tree that will be able to answer such queries. Thanks in advance.

# Answer
> 2 votes
Yes. Use a persistent data structure. Build a tree data structure to answer queries of the form $q(i,0)$. Then, advance $j$, updating the persistent tree data structure as you do. This will build a data structure of size $k$ and let you answer queries in $O(\log k)$ time, where $k$ is the number of non-zero entries in the matrix.

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


# Question
Title: Behavior of non-deterministic Turing Machines after $t_i$ seconds
Suppose that I have a non-deterministic Turing Machine $M\_1$ and its clone $M\_2$. Given a string $x \in \Sigma^\*$, it is possible that after $t\_i$ seconds $M\_1$ accepts $x$ and $M\_2$ does not halt ? What happens if i run $M\_2$ $2t\_i$ seconds?

**My approach**

It is possible because the transition function $\delta\_N$ is a partial function and the machines do random guesses, but it can't be that a machine reject and the other accept. If i run $M\_2$ for $2\_i$ seconds, the outcomes may be different.

# Answer
> 1 votes
There are no seconds of execution, you might want to use steps instead.
Non-deterministic Turing Machine does not behave randomly at all, so two machines $\mathcal M\_1$ and $\mathcal M\_2$ (being copy) are identical, they do not in any random way pick the steps, so the simulation on the first one goes like on the second one. At any time after the same number of steps the tape content matches and the current state matches.

In sny transition there might be more than one rule, the NDTM accepts when one of the paths accepts, but these are executed in copied machines. This effectively may mean that the NDTM have "guessed" the next step (counting steps to the accepted path is the shortest possible one if such exist) but it will always be the same one for given configuration. Please note that if you imagine every step as producing copy of the machine with a different transition taken then these copies might differ.

Please read also the difference between non-determinism and randomness

---
Tags: turing-machines, nondeterminism
---


# Question
Title: Operating system maintains copy of page table for each process
I am quoting a paragraph in *Operating System Concepts* by Silberschatz, in paging chapter,

> In addition, the operating system must be aware that user processes operate in user space, and all logical addresses must be mapped to produce physical addresses. If a user makes a system call (to do I/O, for example) and provides an address as a parameter (a buffer, for instance), that address must be mapped to produce the correct physical address. The operating system maintains a copy of the page table for each process, just as it maintains a copy of the instruction counter and register contents. This copy is used to translate logical addresses to physical addresses whenever the operating system must map a logical address to a physical address manually. It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU.

I don't understand why OS would copy the page table, isn't it the one creating and maintaining it?
And as given further, why does it keep copy of instruction counter and register contents?

# Answer
> 4 votes
> why does it keep copy of instruction counter and register contents?

It's because of process scheduling.

Let's say a process comes in execution first time and executes some lines of instruction. The registers contain values as per the instructions executed till now. Now if the process switches from running state to waiting state (due to I/O or preemption) and then comes back to the running state, it must have the same register values for further execution. So OS stores a copy of each register in the program control block(PCB).

> I don't understand why OS would copy the page table, isn't it the one creating and maintaining it?

Again, if the process goes out of execution, OS must save the information regarding frames of memory allocated to the process.

---
Tags: operating-systems, paging
---