# Question
Title: How do computers perform operations on numbers that are larger than 64 bits?
There are many reasons why numbers larger than 64 bits must be computed. For example, cryptographic algorithms usually have to perform operations on numbers that are 256 bits or even larger in some cases. However, the programming languages that I use can only handle at maximum, 64 bit integers, so how do computers perform operations on numbers that are larger than 64 bits in size and which programming languages support computation of these larger numbers?

# Answer
Larger precision numbers are simulated in software using arrays of fixed-width integers. The elements of these arrays are effectively super-sized digits, and are called *limbs*.

The size of a limb is chosen based on considerations such as what are the available types; what, if any, special operations does the target processor have for going beyond the widest type; and what is actually available in the implementation language.

Let's consider multiplication. If our 64 bit processor does not provide a 64 × 64 → 128 multiplication, we may have to choose a 32 bit limb for our integers, or at least treat our numbers that way for the purposes of multiplication. The basic idea is that we are restricted to inputs which are half the size of the widest type that can be the *result* of a multiplication. We then implement long multiplication.

The following diagram represents 64 × 64 → 128 bit unsigned multiplication of an operand `A` and `B`. The `U:V` notation shows a 64 bit value made up of an upper 32 bit half `U` and a lower 32 bit half `V`. The notation `AH` denotes the upper 32 bits of 64 bit operand `A`, and `AL` denotes the lower 32 bits. `x` is just the multiplication operator:

```
               AH : AL
          x    BH : BL
     -----------------
 P0:           AL x BL
 P1:      AH x BL
 P2:      AL x BH          <-- 64 bit inner products
 P3: AH x BH
     ------------------
    [ 128 bit product ]    <--- sum of inner products

```

This is just long multiplication in which four 32-bit limbs play the role of digits. All combinations of limbs from both operands are multiplied together, and then added together. Each inner product is shifted into the correct power position.

I have given the inner products names, so we can rewrite the addition like this, where 000 indicates 32 all-zero bits.

```
             P0H:P0L
         P1H:P1L:000
         P2H:P2L:000
     P3H:P3L:000:000
     ---------------
     ...........:P0L

```

If only 64 bit addition is available, adding the inner products together is tricky. The addition of two 64 bit numbers produces a 65 bit result. If we work in machine language, the processor may give us the 65th bit in the form of a carry flag, which can then be included in the next round of addition.

If we don't have access to the carry flag, we can infer it anyway. We simply add together the operands. Then if the result is smaller than either operand, we know that carry occurred: we must carry a 1 into the next addition. In C notation:

```
uint64_t A = get_operand_a();
uint64_t B = get_operand_b();
uint64_t SUM = A + B;
int carry = (SUM < A); // 1 if SUM < A, else 0.

```

In any case, we begin by working on the rightmost 64 bit column:

```
        [P0H:P0L]
     P1H[P1L:000]
     P2H[P2L:000]
 P3H:P3L[000:000]
 -------[-------]
 .......[XXX:P0L]

```

We begin by adding `P0H:P0L` and `P1L:000`. This could produce a carry which we call `C0`. We then add `P2L:000` to this partial result. It could carry again, so we call that `C1`. Then we deal with the left column:

```
[C0 + C1]P0H:P0L
[    P1H]P1L:000
[    P2H]P2L:000
[P3H:P3L]000:000
[-------]-------
[ZZZ:YYY]XXX:P0L

```

We add together the carry C0 + C1, which can be 0, 1 or 2, with `P1H`, `P2H` and `P3H:P3L`. This addition will not overflow, because 64 × 64 multiplication cannot overflow 128 bits.

Now 64 bit processors, like the x86-64 ones from Intel, often provide a way in the instruction set to to do 64 × 64 → 128 multiplication, right in the hardware. A special instruction might be provided whose output is a pair of registers. In that case, the problem is solved; we don't have to implement any of the above. We choose 64 bit limbs for our wider-precision numbers and take advantage of that multiplication instruction.

Some compilers for languages like C may provide access to a 128 bit type. If we are working with the GNU C compiler, we have an `__uint128_t` type. Using this may be advantageous since the compiler can map that to the available hardware support, so that when two 64 bit values that are cast to this type are multiplied together, the special instruction is used. A code example of this is attached below.

Suppose no 64 × 64 → 128 multiplication is available. And suppose we are implementing general purpose multi-precision integers that can go to "arbitrary" widths, limited only by memory: so-called *bignums*.

In that case, we will probably skip implementing the above 64 × 64 → 128 multiplication entirely. Our bignum integers will use 32 bit limbs, and multiplication will be implemented as a more general long multiplication of two multi-precision integers using a pair of nested loops. The 64 × 64 → 128 occurs as a special case in that algorithm, when both inputs have two limbs.

> The naive long multiplication is not the only choice of algoirthm for bignum integers. There is the Karatsuba algorithm which becomes advantageous when the numbers go beyond a certain size, because it has better asymptotic performance than the $O(n^2)$ of the naive long-multiplication's nested loop. In fact it achieves $O(n^{1.58})$. After Karatsuba, there are several other algorithms which get the asymptotic performance down, but require even larger numbers in order to yield an payoff).

Here is an example of using GCC on a 64 bit Intel platform to gain access to 64 × 64 → 128 multiplication:

```
#include <stdint.h> // for uint64_t, standard type from ISO C.

// __uint128_t is a GCC extension:
// Not found in all targets and configurations!

__uint128_t mul(uint64_t a, uint64_t b)
{
  return (__uint128_t) a * b;
}

```

Now, when we compile this with `gcc -O2 -S` (optimize at level 2, produce assembly code) we get:

```
mul:
        movq    %rsi, %rax
        mulq    %rdi
        ret

```

Just three instructions, including the `RET`! The quad-word multiplication instruction requires that one of the operands is in the `RAX` register, and so a `mov` is required to move it from `RSI` to `RAX`, since under the calling conventions being used, RSI is used for passing the first argument of a function. If RAX were used for passing the first argument, the move would not be required.

Thus `mulq %rdi` is multiplying `%rax` by `%rdi`; the `%rax` is implicit and understood and so doesn't appear in the assembly notation.

The output is produced in the register pair RDX:RAX. The calling convention is such that this is exactly how a 128 bit result is returned, and so there is nothing left to do but to return from the function.

If we are implementing bignum integers on 64 bit Intel, working in C, using the GNU C compiler, or any other one which provides such an extension, it behooves us to take advantage of this: we can choose 64 bit limbs for our numbers, and use the compiler-specific 128 bit type to handle the multiplication inner products.
> 9 votes

# Answer
in school you (probably) memorized the common operations (addition, subtraction, multiplication and division) for decimal 1 digit numbers.

Then you learned how to do operations on larger numbers using those memorized operations by doing the computation part by part for example long multiplication and long division.

A computer can do the same algorithms using "digits" of whatever word size they can use carrying over the overflow into the next digit.

More advanced algorithms exist that operate a bit faster but still operate on the same principle of the large numbers being sequences of 32-bit or 64-bit digits.
> 52 votes

# Answer
The x86 ISA, along with many (most?) other microprocessor architectures includes the instruction ADC (add with carry), among others, to support arbitrary-precision arithmetic. The basic idea is that instead of thinking of a number as a fixed 2, 4, 8-byte integer, you instead treat it as a variable-length "string" of 2, 4, or 8-byte integers (depending on the word size of the architecture) and combine multiple operations along this string using elementary school arithmetic.

However, note that the instruction merely provides a hardware boost to an operation which can easily be implemented in software using fixed-width arithmetic instructions. To see such a software implementation, take a look at the Java `BigInteger` source, which uses an array of `int` to hold the "string" of \[32-bit\] "digits".
> 11 votes

# Answer
The computer hardware provides facility of storing integers and doing basic arithmetic over them; generally this is limited to integers in a range (e.g. up to $2^{64}-1$). But larger integers can be supported via programs; below is one such method.

Using *Positional Numeral System* (e.g. the popular base-10 numeral system), any arbitrarily large integer can be represented as a sequence of *digits* in base $B$. So, such integers can be stored as an array of 32-bit integers, where each array-element is a digit in base $B=2^{32}$.

We already know how to represent integers using numeral-system with base $B=10$, and also how to perform basic arithmetic (add, subtract, multiply, divide etc) within this system. The algorithms for doing these operations are sometimes known as Schoolbook algorithms. We can apply (with some adjustments) these Schoolbook algorithms to any base $B$, and so can implement the same operations for our large integers in base $B$.

To apply these algorithms for any base $B$, we will need to understand them further and handle concerns like:

* what is the range of various intermediate values produced during these algorithms.
* what is the maximum carry produced by the iterative addition and multiplication.
* how to estimate the next quotient-digit in long-division.

(Of course, there can be alternate algorithms for doing these operations).

Some algorithm/implementation details can be found here (initial chapters), here (written by me) and here.
> 2 votes

# Answer
Decimal positional representation of numbers, called Indo-Arabic numeral system, was discovered about 20 centuries ago. It was sucessful because there is no limitation on the size of number that can be represented, and it allows fairly simple manipulations of number representations (i.e. algorithms) to realize elementary arithmetic operations.

It represents numbers as sequences of the ten distinct digits (numerical symbols) represented today as 0, 1, ... 9. Modern understanding shows that there is nothing essential about the number of distinct digits, which is called the base of the system, which is ten in this case. A similar system can be built with any number base, any number of distinct digits, as long as it is two or more. With two digits, i.e. base 2, you get the binary system commonly used in computers hardware (binary digits are called bits).

However, size limitations in computer hardware limit the size of bit sequences it can represent and manipulate simply to represent numbers and realize arithmetic operations. This is basically what this question is about.

The simple answer to this question is to come back to basics :

* chose a numeration base N
* define a set of N symbols that will be the digits. Any computer representation of the digits is ok, as long as you can identify and manipulate them.
* define a way to represent and manipulate sequences of symbols, that will be your representation of numbers.

Then you must also write routines that perform the fundamental arithmetic operations on your number thus represent$ed in base N (and possibly a few other utilities, such as I/O routine in some human readable representation). Then you can use your new numbering system.

Note that N can be arbitrary (but at leaen.wikipedia.org/wiki/Arabic\_numeralsst two), such as $2^{64}$, $3$, $16$ or $3^{72}-276$.

There rest is a matter of implementation choice, depending on what you want to do with your numbering system, and on what you want to optimize, such as speed of computation or size of number representation.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: Space complexity Matrix form of Fibonacci numbers
I read the following link.

That compute $F\_n$ in $O(\log n)$, but i can't find the space complexity of this matrix form of $F\_n$.

# Answer
> 2 votes
The algorithm uses a constant number of $2 \times 2$ matrices which contain Fibonacci numbers $F\_m$ for $m \leq n$, as well as a few indices ranging up to $n$.

This should be enough information to compute the space complexity of the algorithm, whether expressed in machine words or in bits.

As an aside, since $F\_n$ grows exponentially in $n$, it is misleading to count only the number of arithmetic operations, rather than the bit complexity of the computation.

---
Tags: algorithms
---


# Question
Title: Coming up with a loop invariant for the partition section Quicksort?
```
void partition(int a[], int L, int R) {
int i = L;
int pivot = a[R];
 for (int j = L; j < R; j++) {
     if (a[j] <= pivot) {
     swap(a[i], a[j]);
      i++;
     }
  }
swap(a[i], a[R]);
}

```

My code is above. My loop invariant is "At the beginning of the iteration, j is in the range of a\[L\] to a\[R-1\]". Is this correct? Or if it is not am I on the right track. Thank you.

# Answer
You're sort of on the right track in that you're trying to relate the *position* of array elements to their *value*, but your statement makes a serious error in directly comparing the value of an index, $j$, to the value of arbitrary data, $a\[L\]$ and $a\[R-1\]$.

I think you meant to say $L\leq j\leq R$ is a loop invariant. Observe that $L\leq i\leq j$ is as well, but neither are very interesting statements.

Remember, the motivation for identifying loop invariants is so that we can use them to verify that our code does what it's supposed to. Here, implementing the partition stage of Quicksort, our goal is to rearrange the elements of $a$ such that all the data to the left of the pivot will be less than or equal to the pivot, and all the data to the right of the pivot will be greater than or equal to the pivot.

One important loop invariant is $$\text{For all indices }k \text{ with } L\leq k\<i, \text{ we have } a\[k\]\leq\text{pivot}=a\[R\]$$ We can see this in your code:

```
    void partition(int a[], int L, int R) {
    int i = L;
    int pivot = a[R];
    //a[k]<=pivot for all k with L<=k<L=i (true since there are no such k)

     for (int j = L; j < R; j++) {
         //a[k]<=pivot for all k with L<=k<i (inductive hypothesis)

         if (a[j] <= pivot) {
             swap(a[i], a[j]);
             //we have now ensured a[i]<=pivot
             //it is an invariant that i<=j
             //so the elements a[L],...,a[i-1] are unchanged
             //thus a[k]<=pivot for all k with L<=k<i+1

             i++;
             //now a[k]<=pivot for all k with L<=k<i
         }
      }
    swap(a[i], a[R]);
    }

```

Another important loop invariant is $$\text{For all k such that } i\leq k\< j, \text{we have } a\[k\]\geq\text{pivot}=a\[R\]$$ Again we can see this looking at your code:

```
    void partition(int a[], int L, int R) {
    int i = L;
    int pivot = a[R];

    //a[k]>=pivot for all k with i=L<=k<L=j (true since there are no such k)
     for (int j = L; j < R; j++) {
         //a[k]>=pivot for all k with i<=k<j (inductive hypothesis)

         if (a[j] <= pivot) {
             //it is an invariant that i<=j. now either i<j or i=j
             //if i=j, then there are no k such that i<=k<j, so assume i<j
             //then i<=i<j, and consequently a[i]>=pivot

             swap(a[i], a[j]);
             //now a[j]>=pivot and a[i]<=pivot
             //the other elements are unchanged
             //so now a[k]>=pivot for k with i+1<=k<=j

             i++;
             //now a[k]>=pivot for k with i<=k<=j

         }
      }//after incrementing j by 1, now a[k]>=pivot for k with i<=k<j

    swap(a[i], a[R]);
    }

```
> 1 votes

# Answer
You don’t want “a loop invariant”. You want a loop variant that leads to something you want to prove. Think about what you want after the loop. You want a loop variant that leads bit by bit to your desired outcome.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Are there any programming languages that support state machines in their standard library?
State machines are a fundamental computer science concept and in many senarios they are the simplest way to implement a process or program. However, most programming languages don't support them natively. Is there a technical limitation to do it? And if not, are there any programming languages that do support state machines in their standard libraries?

# Answer
> 2 votes
A state machine is basically a loop around a `switch case` construct, which exists in pretty much almost every language I know in a form or another.

So I'm curious of the one languages you found out that do, according to your wording, implement state machines natively, since to me most of all do so.

# Answer
> 1 votes
All imperative code is a state machine. The current state is called the *program counter* or in high-level languages the *line number*.

It's possible to construct an explicit state machine so that the state corresponds to some variable in your code, and the transitions are specific blocks of code. You can write this yourself, but it's a reasonably common transformation as it allows you to interleave the execution of different pieces of code.

The feature which uses this transformation - the ability to interleave the execution of different pieces of code - is often called "coroutines". C++ coroutines are implemented this way. However, coroutines can also be implemented using stack switching, which does not construct a state machine. Lua coroutines are implemented this way - although since the stack in this case is part of the interpreter state, from the perspective of outside the interpreter you can see them as explicit state machines.

# Answer
> 1 votes
In a language with Proper Tail Calls, implementing a State Machine is trivial: each state is a subroutine, each transition is a subroutine call, choosing the transition is done using the programming language's builtin feature for conditions (e.g. `switch` in ECMAScript).

In an OO language (or any other language with dynamic ad-hoc polymorphism) with Proper Tail Calls, we can go one step further and make the message dispatch algorithm implement the choice of transition for us.

In a language with flexible syntax, we can typically get very close to a formal state machine syntax. In a language with programmable syntax, we can not just get close, we can make our syntax identical to a formal state machine syntax.

All of this can generally be done in a few lines of code, without the need of any special language features. It is generally preferred to make languages powerful enough that the programmer can provide their own abstractions, instead of the language designer having to provide the abstractions for the programmer. (This at least applies to general purpose languages. Domain-specific languages are a different beast. In DSLs, restricting the programmer's capabilities is often a good thing.)

Lots of languages actually provide *regex* as part of the language and/or the library. *Regex* are supersets of regular expressions, and can thus directly express State Machines operating on character strings.

# Answer
> 0 votes
Suppose that you have a (finite) list of Boolean values and that you would like to count the number of occurrences of `True`. This (infinite) state machine's state-transition function is

$$ f (x, u) := \begin{cases} x + 1 & \text{if } u = \texttt{True} \\ x &\text{if } u = \texttt{False} \end{cases} $$

Suppose further that the initial state is $x\_0 = 0$ and that the input sequence is

$$\[ \texttt{False}, \texttt{True}, \texttt{True}, \texttt{False}, \texttt{True} \]$$

Hence,

$$ 0 \xrightarrow{\texttt{False}} 0 \xrightarrow{\texttt{True}} 1 \xrightarrow{\texttt{True}} 2 \xrightarrow{\texttt{False}} 2 \xrightarrow{\texttt{True}} 3$$

In Haskell,

```
type State = Integer
type Input = Bool

-- initial state
x0 :: State
x0 = 0

-- state-transition function
f :: State -> Input -> State
f x True  = x + 1
f x False = x

-- sequence of inputs
us :: [ Input ]
us = [ False, True, True, False, True ]

-- compute sequence of states
xs :: [ State ]
xs = scanl f x0 us

```

After having loaded this Haskell script on GHCi,

```
λ> xs
[0,0,1,2,2,3]

```

However, if you only want the final state, use (left fold) function `foldl` instead of (cumulative left fold) function `scanl`, as follows.

```
λ> foldl f x0 us
3

```

---
Tags: finite-automata, programming-languages
---


# Question
Title: Semantics and implementation of side effects
From a practical point of view, how do functional languages with formally specified semantics (like ML) handle side effects like printing? I'm aware of things like the IO monad in Haskell but I'm interested in how the actual primitives are encoded and implemented. Thanks in advance.

# Answer
> 4 votes
Monads in Haskell serve two purposes.

A monad that is defined *within* Haskell is really a *simulation* of some computational effect in terms of pure (side-effect free) computation. After all, Haskell is a pure language.

The second use of monads in Haskell, as well as in programming language semantics, and many other languages, is to model *external* or *primitive* computational effects. Such effects cannot be defined within the language itself. They necessarily come from some external environment (hardware, operating system, virtual machine).

In Haskell the monad that gives access to external effects is `IO`. This is why the main program has the type `IO ()` – so that it can actually interact with the external world through computational effects.

Under the hood, the Haskell compiler compiles pure code, including user-defined monads, to machine code that behaves equivalently to the pure code (with respect to a formal semantics). But it takes special care of code of type `IO` by compiling things like `putStr` to actual system calls that trigger real I/O (I am over-simplifying a bit, but you get the point).

The ML-family of languages differ from Haskell because they do not separate so cleanly the pure & effectful computations. In such "impure" languages, *all* computations happen in a single `IO`-style monad that gives access to all external effects (I/O, mutable memory, exceptions) all the time. And the fact that this is the case is *not* recorded in types. Thus, an ML computation of type `int` would really be something like `IO Int` in Haskell.

Of course, the programmer is free to define their own monads in ML to simulate various computational effects, just like in Haskell, but this is a bit irrelevant here.

You ask how the effects are specified in the formal semantics. There are several ways of doing it (transition semantics, algebraic semantics, abstract interpretation), and I am not sure that describing them here would serve a purpose. Please ask for further references if you'd like to know the details.

The important thing to understand is the *relationship* between the formal semantics, which is the mathematical model of computational effects, and the actual implementation by the language compiler, which converts source code to machine code that triggers computational effects by using the available hardware, possibly via some system calls. We want the mathematical model and the compiled code to match, i.e., the compiler should be *correct* with respect to the formal semantics.

# Answer
> 3 votes
> From a practical point of view, how do functional languages with formally specified semantics (like ML) handle side effects like printing? I'm aware of things like the IO monad in Haskell but I'm interested in how the actual primitives are encoded and implemented.

It is strange to lump ML and Haskell together in this question. Unlike Haskell, ML is *not* a *functional language* in the sense that you seem to be using the term here.

ML handles side-effects in exactly the same way that C or Java or almost any mainstream programming language does: it doesn't. It ignores them.

This is in contrast to Haskell, where side-effects are not possible at all. There are no ways to express side-effects in the Haskell 2010 language and there are no ways to express side-effects using the Haskell 2010 standard library.

Okay. There is a big asterisk attached to that paragraph.

First off, there *are* actually functions like `System.IO.Unsafe.unsafePerformIO` which allow you to use unrestricted side-effects. Note, however, that this function is *explicitly* placed in the `System.IO.Unsafe` module, and also note that it is *not* part of the Haskell 2010 Specification. So, there is already a double warning sign around it: first, you have the fact that it is a non-portable *implementation-specific* extension to the standard, and then you have the word "unsafe" in the module name.

These functions are considered to be "escape hatches" for emergency use by very experienced programmers working on performance-sensitive core libraries, they are not considered to be part of the normal toolset of a Haskell programmer.

In other words, using these functions is considered to be outside the realm of Haskell; whenever you use them, you leave all the protections and guarantees of Haskell behind.

Secondly, of course, there is the `System.IO` module, which *is* part of Haskell 2010. This is how you can perform I/O (the most general form of side-effects) in Haskell. Except, technically, you are *not* performing I/O using the `System.IO` module. What you are doing is *describing* purely-functional *I/O Actions*, and returning these *Actions* to the runtime.

The runtime then contains an *impure* evaluator for those *Actions*. So, the trick that Haskell uses, is that the programmer *never* performs side-effects. The programmer only *describes* the side-effects to the runtime, and the runtime then performs those side-effects … but the runtime is not considered to be inside the realm of Haskell and therefore is not bound by the restrictions of Haskell.

*How* the runtime performs those side-effects is considered to be irrelevant. That is what programming, in the end, is all about: abstraction and reuse. As long as I get a description of how to use some "thing", I don't need to know how that "thing" works internally … in fact, ideally, it should be *impossible* for me to figure out how that "thing" works internally (IOW it should be impossible to break an abstraction boundary).

Now, of course, most Haskell implementations are open source, so we can just check. E.g. GHC implements the I/O runtime at least partially in C and calls out to the Operating System's I/O routines. (In fact, GHC contains multiple different implementations of the I/O subsystem for e.g. POSIX vs. Windows or single- vs. multi-threaded Runtime System.) Other Haskell implementations are allowed to implement I/O differently. For example, I am assuming that the (now defunct) Haskell.NET did not implement I/O in C but in C#; similarly, I am assuming that the (now defunct) Jaskell did not implement I/O in C but in Java. I assume GHCJS implements I/O in ECMAScript.

In short, most Haskell implementations view the graph of I/O Actions generated by the `IO` monad as instructions to some form of abstract machine … in other words, they view them as a language, and they deal with them the way you deal with any other language: you either compile it to a language you know how to interpret, or you interpret it directly.

---
Tags: programming-languages, functional-programming, semantics
---


# Question
Title: Floyd's Cycle detection algorithm | Determining the starting point of cycle
I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle\_detection#Tortoise\_and\_hare)

I can see how the algorithm detects cycle in O(n) time. However, I am unable to visualise the fact that once the tortoise and hare pointers meet for the first time, the start of the cycle can be determined by moving tortoise pointer back to start and then moving both tortoise and hare one step at a time. The point where they first meet is the start of the cycle.

Can someone help by providing an explanation, hopefully different from the one on wikipedia, as I am unable to understand/visualise it?

# Answer
> 0 votes
I found the answer on stackoverflow. Thanks if anyone was looking into this for me. And for those who like me wanted an explanation, please refer to: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list The chosen answer to the question, explains it!

# Answer
> 95 votes
You can refer to "Detecting start of a loop in singly linked list", here's an excerpt:

**Distance travelled by `slowPointer` before meeting** $= x+y$

**Distance travelled by `fastPointer` before meeting** $=(x + y + z) + y = x + 2y + z$

Since `fastPointer` travels with **double** the speed of `slowPointer`, and **time is constant** for both when both pointers reach the meeting point. So by using simple speed, time and distance relation (`slowPointer` traveled half the distance):

\begin{align\*} 2\*\operatorname{dist}(\text{slowPointer}) &= \operatorname{dist}(\text{fastPointer})\\ 2(x+y) &= x+2y+z\\ 2x+2y &= x+2y+z\\ x &= z \end{align\*}

Hence by moving `slowPointer` to start of linked list, and making both `slowPointer` and `fastPointer` to move one node at a time, **they both have same distance to cover**.

They will reach at the point where the loop starts in the linked list.

# Answer
> 59 votes
I have seen the accepted answer as proof elsewhere too. However, while its easy to grok, it is incorrect. What it proves is

$x = z$ (which is obviously wrong, and the diagram just makes it seem plausible due to the way it is sketched).

What you really want to prove is (using the same variables as described in the diagram in the accepted answer above):

$z = x\ mod\ (y + z)$

$(y + z)$ is the loop length, $L$

so, what we want to prove is:

$z = x\ mod\ L$

Or that z is congruent to x (modulo L)

Following proof makes more sense to me:

Meeting point, $M = x + y$

$2(x + y) = M + kL$, where $k$ is some constant. Basically, distance travelled by the fast pointer is $x + y$ plus some multiple of loop length, $L$

$x + y = kL$

$x = kL - y$

The above equation proves that $x$ is the same as some multiple of loop length, $L$ minus $y$. So, if the fast pointer starts at the meeting point, $M$ or at $x + y$, then it will end up at the start of the loop.

# Answer
> 2 votes
Say there are $l$ elements before the loop starts and $n$ elements in the loop. And $e\_l$ is the first element of the loop which is seen when we traverse the linked-list. When we will say "an element $x$ steps ahead of $e$", that will mean, we can reach that element taking $x$ steps from $e$.

Now, when Tr (tortoise) reaches $e\_l$, after $l$ iterations, say, Hr (Hare) is $x$ steps ahead of $e\_l$. Since Hr has taken total $2l$ steps by then ($l$ steps prior to the loop), so:

$x = l \bmod n$.

In each future iteration, Tr and Hr will progress by 1 and 2 steps respectively, and so each iteration will increase their "gap" by 1. So they will meet after $n-x$ further iterations, when their gap will become $x + (n-x) = n$. So, the meeting element $M$ will be $n-x$ steps ahead of $e\_l$. Now that means, stepping $x$ steps after $M$ will again bring us to $e\_l$. Our goal is to locate $e\_l$.

So, when we start with one reference Tr at $M$ and another reference Hr at the head of the linked-list, and progress both of them 1 step at a time, after $l$ iterations:

* Hr will be $l$ steps ahead of the head, which is $e\_l$.
* Tr will be $(l \bmod n)$ steps ahead of $M$, that is, $x$ steps ahead of $M$, which is $e\_l$.

Thus when they have met, we know it is $e\_l$.

See this article (written by me) for details. There you will find a slightly modified method to locate $e\_l$.

# Answer
> 1 votes
I try to draw function curves to see what happen when two pointers velocities are not 2:1，and verified the correctness of finding the start of cycle.

https://www.desmos.com/calculator/snqtvrmhn3

# Answer
> 0 votes
I also think the top answer is incomplete, and while some of the other explanation are also good, I have another version without MOD to show the same thing, which is perhaps easier for some people.

The same setup, consider $X\ge 0$ being the distance before the loop, $N \le \text{size of list}$ being the size of the loop (the quantity $y+z$ in the picture), and the meeting point be $Y$ in the Loop. At this point, notice that we have also made $X+Y \le N$.

Now, the slow pointer travels $X+Y+pN$, where $p$ is an arbitrary integer. Then fast pointer travelled $2(X+Y+pN)$.

Now, we **claim** that they meet at $Y$.

**Proof**:

If they meet at $Y$, it must be that the faster pointer travelled exactly $qN$ more than the slower pointer, where $q$ is an integer. Then we have: $$\text{distance difference = }2(X+Y+pN)-(X+Y+pN)=X+Y+pN$$. But we had $Y$ being an arbitrary meeting point in the loop, so we can choose simply $X+Y=N$, which holds as $X+Y \le N$.

Therefore, we have: $$ X+Y+pN=N+pN=(p+1)N = qN $$ which is true if $p+1=q$. Now, since both $p$ and $q$ are arbitrary integers, we can just choose the minimum so that $p=0,q=1$, which corresponds to: $$ \text{distance travelled by slow pointer}=X+Y+pN=X+Y $$ and $$ \text{distance travelled by fast pointer}=(X+Y+pN)+qN=X+Y + N $$ so the fast pointer, at the first time meeting the slow pointer, travelled exactly $N$ more.

# Answer
> 0 votes
Assume there are l steps to enter the loop, and the loop has length n. Using Floyd’s algorithm, tortoise and hare meet at the smallest m \>= 1 where $x\_m = x\_{2m}$. m steps are one or more complete cycles.

If we compare $x\_i$ and $x\_{i+m}$ then they are the same if and only if $x\_i$ is within the cycle, that is i \>= l. We set tortoise = $x\_0$ and hare = $x\_m$ and as long as they are not the same increase them both by one step, counting the steps. They are the same for the first time when the tortoise enters the cycle, and that is after i = l steps.

PS. To find n, iterate the hare from $x\_m$ until it reaches $x\_m$ again after n steps. You would do that at the same time as finding the steps until the cycle. If n \<= l then we find n at the same time or before l, otherwise at least we have done l steps of the search already.

PS. We know that n divides m. So if we haven’t found n after x steps where x \< m is the largest divisor of m, then n = m.

PS. Brent’s loop finding algorithm usually runs faster, determines the cycle length immediately, and often knows an element $x\_{m-l}$ shortly before entering the loop, makeing it faster to determine the number of steps until the loop.

```
Let t = h = start, m = 0
Repeat
    t = t -> next, h = h -> next -> next, m = m+1
Until t = h
Let t = start, i = 0, x = h
While t ≠ h
    t = t -> next, h = h-> next, i = i + 1
    If h = x and n unknown then n = i
l = i

```

# Answer
> -2 votes
The tortoise and the hare are two pointers that are initialized with the value of the "top" of the list. In each cycle of the loop, the hare increases by 2 incremental items, while the tortoise increases by one. If at any point, the hare equals the hare, a loop has been detected. If the hare equals the end, a loop is not found.

This post explains it better line-by-line:

https://www.thiscodeworks.com/floyd-s-cycle-detection-algorithm-aka-the-tortoise-and-the-hare-algorithms-logic-interesting/5e10a9b796432f6f7b798b29

---
Tags: algorithms, linked-lists
---


# Question
Title: DFA for {w|w contains a substring of length at most 5 that has at least three 1's}
I have thought about this problem, but cannot come up with a convincing answer since I think this problem has too many states too consider. The accepting states can be length 5 substring and 3 1's, length 5 substring and 4 1's, length 5 substring and 3 1's, length 4 substring and 3 1's, length 4 subtring and 4 1's, length 3 substring and 3 1's. However, I am not sure how to think about this question. Any help would be appreciated.

# Answer
> 1 votes
It seems you are on the right track. Keep the last five bits seen in the state of the automaton. In fact you can start with 00000 rather than the empty string (no letters read), because it's the same count. Then, reading a 1 you move to 00001, etcetera.

Then note that any state which has (at least) three 1's is accepting, and whatever happens next the string will be accepted. So all these states can be lumped in to one accept state.

Now if my count is right you need 17 states.

---
Tags: finite-automata
---


# Question
Title: What is difference between fetching, accessing and downloading in web?
I need more clarity about what is the main difference between fetching, accessing and downloading in web? which is differentiating these three words in web?

# Answer
**Accessing** a resource (a file or a device) basically refers to using it or performing any operation on it. For example, accessing a document stored on a cloud platform includes viewing as well editing the document (and any other operations that can be performed on it).

**Fetching** and **Downloading** basically mean the same: transfer a file from a remote device (for example, a server) to your own device. A slight difference between the two is that generally, downloading saves the file to your local storage while fetching doesn't necessarily do it. For example, online streaming is also a type of fetching but it doesn't save the video locally.

These are the general meanings of the above terms related to web. Meanings may be different in any specific context (like any specific application or programming language).
> 2 votes

---
Tags: computer-networks
---


# Question
Title: On a coloring that uses $2\cdot a\left( G \right)$ colors
Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say that $E$ can be partitioned to $F\_1 , ..., F\_a$. Then, color $V\_1$ is $2$ colors because its a forest. then, color $V\_2 \backslash V\_1$ in $2$ new colors because this is still a forest, and so on.

I agree that the amount of colors to be used will be $2\cdot a \left( G \right)$. What bothers me, is that each coloring of a single forest is proper when you look at the forest itself, but might not be proper once you look at the entire graph.

Let me give a partial example. Say we have $\left( u\_1 , u\_2 \right), \left( u\_2 , u\_3 \right), \left( u\_1 , u\_3 \right)$, and say $\left( u\_1 , u\_2 \right), \left( u\_2 , u\_3 \right) \in F\_1$ and that $\left( u\_1 , u\_3 \right) \in F\_2$. So $u\_1,u\_2,u\_3$ are spanned by $F\_1$. Hence, they will be colored in $2$ colors: $1$ and $2$. WLOG, $f\left( u\_1 \right) = 1$, $f\left( u\_2 \right) = 2$, $f\left( u\_3 \right) = 1$. Now as we approach $F\_2$, the vertices $u\_1,u\_2,u\_3 \notin V\_2 \backslash V\_1$. therefore their color will not be altered.

So, the coloring was proper when our world was $F\_1$. However, upon looking at the entire graph, our coloring is not proper, and that's what bothers me.

# Answer
The proof given in the linked post is wrong. Here is a correct proof, taken from Steven Butler's notes.

A forest of $k$ trees on $n$ vertices contains $n-k$ edges, and so its average degree is $\frac{2(n-k)}{n} \< 2$. Therefore, if a graph has arboricity $a(G)$, then its average degree is less than $2a(G)$. Consequently, a graph of arboricity $a(G)$ always contains a vertex of degree at most $2a(G) - 1$.

Given a graph $G$ of arboricity $a(G)$, we arrange its vertices in order $v\_1,\ldots,v\_n$ as follows. The first vertex $v\_1$ is an arbitrary vertex of degree at most $2a(G) - 1$. Now remove $v\_1$ from the graph. The resulting graph still has arboricity at most $a(G)$, so it ontains some vertex $v\_2$ of degree at most $2a(G) - 1$. Remove $v\_2$ from the graph, and repeat.

We have ordered the vertices in such a way that $v\_i$ has at most $2a(G) - 1$ neighbors in the subgraph of $G$ induced by the vertex set $\\{v\_i,\ldots,v\_n\\}$. This allows us to greedily color $G$ using $2a(G)$ colors: scanning the vertices in reverse order $v\_n,\ldots,v\_1$, each vertex $v\_i$ has at most $2a(G) - 1$ neighbors which have already been colored (since at this point, only the vertices $v\_{i+1},\ldots,v\_n$ have been colored), and so we can always color it using some color in $\[2a(G)\]$ without creating a monochromatic edge. After processing all vertices in this way, we obtain a valid coloring of the entire graph using at most $2a(G)$ colors.
> 3 votes

---
Tags: graphs, combinatorics, weighted-graphs, colorings
---


title: AVL Tree rotations

text:
# Question
Title: AVL Tree rotations
What size is the largest AVL tree for which an insertion could trigger a double rotation?

# Answer
The insertion of a single element to an AVL-tree might *cause unbalance at several nodes* on the path from the root to the leaf where the new element was placed.

The tree can then be *restored by a rotation at a single node* on the path: the *lowest node with unbalance*. After that rotation the height of the subtree at that node is again the height it had before insertion, so all balance-factors above that point are again what they used to be before insertion.

The rotation that fixes the tree might be a single rotation or a double rotation depending on the position of the subtree that is deepest, as seen from the node where the rotation is performed.

In the example below we will rotate at node 4 to restore the balance caused by the insertion of node 6. (This will be a single rotation, to the left.)
> 1 votes

---
Tags: data-structures, trees, databases, avl-trees
---


# Question
Title: Karatsube-Ofman runtime complexity computation
I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample.

Question: One can generalize the Karatsube-Ofman algorithm even further and divide the number to be squared into b parts with n / b places. However, one then has to perform 2b - 1 recursive squaring of numbers with n / b digits 2 plus O (n) overhead for various “simple” operations. Represent the running time Q b (n) of this method by a recursion equation and try to solve this recursion. Which asymptotic running time is achieved?

Solution: there exists $\alpha$ and $\beta$ such that:

with some estimates and the partial summation of the geometrical series follows:

My questions:

1: how did we convert the $(2b+1)Q\_b(\frac{n}{b}+\beta n)$ to the first line of the ?

2: did we use the sum since it's for all number $n\geq 2$?

3: in first line why did we multiply $\beta$ with $(2b-1)$?

4: why $\log\_b(n)-1$ above the sum ?

5: in third line how did we remove the sum?

6: in fourth line why did we use inequality ?

7: in fifth line how did it get converted ? from 3 and 4

# Answer
> 2 votes
The recurrence relation you give can be handled by the master theorem. Any proof of the master theorem will include similar steps (in more generality). A good proof of the master theorem should carefully explain all the steps in the proof.

Beware, though, that the master theorem includes three different cases, and you're interested in only one of them (case 1 in the numbering used by Wikipedia).

---
Tags: time-complexity, runtime-analysis, proof-techniques
---


# Question
Title: Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms
I stumbled upon some problem in my understanding of the complexity classes FPT and XP. According to Wikipedia (and the Book "Parameterized Algorithms") we know the following about the Vertex Cover and Vertex Coloring problem:

> A vertex cover of size $k$ in a graph of order $n$ can be found in time $O(2^{k}n)$, so this problem is in FPT.

> An example of a problem that is thought not to be in FPT is graph coloring parameterized by the number of colors. It is known that 3-coloring is NP-hard, and an algorithm for graph $k$-coloring in time $O(f(k)n^{O(1)})$ for $k=3$ would run in polynomial time in the size of the input. Thus, if graph coloring parameterized by the number of colors were in FPT, then $P = NP$.

According to this answer from a different question it is also true that Vertex coloring isn't even contained in $XP$ (unless $P = NP$).

> since $3$-coloring (which is NP-complete) would be solvable in $O(n^{f(3)})=O(n^c)$ time, thus rendering it polynomially solvable.

While each statement above makes perfect sense on its own the combination of all three seems odd to me, as we know that Vertex Cover is considered NP-complete just like Vertex Coloring is.

What I don't get is: As far as my understanding goes I could argue as above that for a fixed $k$ (say $k=3$) in a vertex cover instance we could achieve a linear runtime, namely $O(2^3n)=O(n)$. Which would show $P=NP$, just as it is argued in Vertex Coloring.

And again since $O(n^{f(3)})=O(n^c)$ it wouldn't even be in $XP$. Thus Vertex Cover should not be contained in $FPT$ or $XP$.

Since Vertex Cover clearly is in FPT: What am I getting wrong here?

# Answer
> 2 votes
What you are probably missing is that vertex coloring is hard already when $k=3$, i.e., the number of colors is not part of the input but fixed. In contrast, for vertex cover, the size of the cover $k$ is part of the input.

---
Tags: complexity-theory, time-complexity, polynomial-time, parameterized-complexity
---


# Question
Title: Domain of discourse vs First-order theory
In the question (Validity of predicate logic formulas) I see the following way of expressing:

"The predicate $P(x,y) \equiv \bigl\[ y \cdot x = 1 \bigr\]$, where the domain of discourse is $\mathbb{Q}$."

However, I am used to call this *domain of discourse* a *first-order theory*. For instance, I would have rewritten the above phrase as:

"The predicate $P(x,y) \equiv \bigl\[ y \cdot x = 1 \bigr\]$, where the first-order theory is $\mathcal{T}\_{\mathbb{Q}}$.", where $\mathcal{T}\_{\mathbb{Q}}$ denotes the theory of Linear Rational/Real Arithmetic (I call them like that, since, in the linear fragment, arithmetics for $\mathbb{Q}$ and $\mathbb{R}$ are equivalent).

Then, my question is: which is the difference between *domain of discurse* and *first-order theory*? Someone could say that if I am using a theory, then I am accepting all of its axioms, but the same happens with domain of discourse! That is, if I say the domain of discourse is $\mathbb{Q}$, then I am accepting all the axioms of the rationals, in the same way.

Does the difference come from the signature? Maybe the domain of discourse is not specifying whether the arithmetic is linear or no?

# Answer
> 1 votes
Unless I'm missing something, you're simply asking a different question than the previous questioner did.

The previous question is asking an abstract question about predicate logic, so all axioms are available. But the question could also have been expressed as a question about a specific theory, too. Asking "is $P$ a tautology where the domain of discourse is $\mathbb{N}$" is not the same question as "is $P$ a tautology in the theory of Peano arithmetic". In the former question, all axioms and theorems are available, and in the latter, you are restricting yourself to the first-order theory with addition and multiplication, plus induction.

The statement that $P\ne NP$ can be expressed as a formula in the domain of discourse $\mathbb{N}$, but not in any first-order theory.

---
Tags: logic, first-order-logic, smt-solvers, predicate-logic
---


# Question
Title: Cover 2 by n binary matrix with submatrices of minimum total size
This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the size of the submatrices (we consider the size of a matrix the product of its rows and columns) and we use no more than $L$ submatrices. For example, if $A$ is $$ 1 \quad 1 \quad 0 \quad 0 \quad 1 \quad 1\\ 0 \quad 1 \quad 1 \quad 0 \quad 0 \quad 0 $$ and $L = 2$, the optimal solution would be covering $A$ with 2 submatrices of sizes $2 \times 3$ and $1 \times 2$: $$ x \quad x \quad x \quad 0 \quad x \quad x\\ x \quad x \quad x \quad 0 \quad 0 \quad 0 $$ in this case the output of an algorithm solving this problem should be $8$ (the sum of the sizes of the submatrices: $2\cdot 3 + 1 \cdot 2$), and $2$ (which means that we used 2 submatrices).

I've come up with a partial solution using dynamic programming, but it is so long that I doubt it is correct. In summary, suppose that we start to analyze the input array from the first column until the $k$-th column. Let $C\_{OPT}(k)$ and $M\_{OPT}(k)$ be the optimal solutions at the $k$-th column. If $M\_{OPT} = L$ then we have two analyze whether the previous submatrix used covers the $(k-1)$-th column or not, and then observe how many 1s there are at the $k$-th column. Based on that, the recursive relationships between $C\_{OPT}(k)$ and $C\_{OPT}(k-1)$ can be written. However, I haven't figured out yet how to analyze the case where $M\_{OPT} \< L$.

Is my approach correct so far? Or is there a better way to solve this problem?

# Answer
> 1 votes
It looks like you are in the right direction.

In order to establish recurrence relations, we need more subproblems. The final solution is probably even longer than what you have done!

Let $A$ be the given binary array (the leftmost column of $A$ is the first column). For each pairs of numbers $(k, s)$, where $1\le k\le n$, $0\le s\le L$,

* Let $N(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that neither of $A\[0\]\[k\]$ and $A\[1\]\[k\]$ $A\[1\]\[k\]$ is covered.
* let $U(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A\[1\]\[k\]$ is not covered.
* let $L(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A\[0\]\[k\]$ is not covered.
* let $B\_1(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A\[0\]\[k\]$ and $A\[1\]\[k\]$ are covered by the same submatrix.
* let $B\_2(k, s)$ be the least cost to cover all $1$s in the input array up to the $k$-th column with no more than $s$ matrices such that $A\[0\]\[k\]$ and $A\[1\]\[k\]$ are covered by different submatrices.

When $k$ or $s$ is out of bounds, consider all costs defined above as infinity.

The differences among $N(k,s), U(k,s), L(k,s), B\_1(k,s)$ and $B\_2(k,s)$ are how the $k$-th column is covered.

The recurrence relations are

$$N(k, s) = \begin{cases} \infty &\mbox{if }A\[0\]\[k\]=1 \mbox{ or } A\[1\]\[k\]=1 \\ \min(N(k-1,s), U(k-1,s), L(k-1,s), B\_1(k-1,s), B\_2(k-1, s))&\mbox{otherwise} \end{cases}$$

$$U(k, s) = \begin{cases} \infty &\mbox{if }A\[1\]\[k\]=1 \\ 1 + \min(N(k-1,s-1), U(k-1,s), L(k-1,s-1), B\_1(k-1,s), B\_2(k, s-1))&\mbox{otherwise} \end{cases}$$

$$L(k, s) = \begin{cases} \infty &\mbox{if }A\[0\]\[k\]=1 \\ 1+\min(N(k-1,s-1), U(k-1,s-1), L(k-1,s), B\_1(k-1,s), B\_2(k, s-1))&\mbox{otherwise} \end{cases}$$

$$B\_1(k, s) = 2 + \min(N(k-1,s-2), U(k-1,s-1), L(k-1,s-1), B\_1(k-1,s), B\_2(k, s-2))$$

$$B\_2(k, s) = 2 + \min(N(k-1,s-1), U(k-1,s-1), L(k-1,s-1), B\_1(k-1,s-1), B\_2(k-1, s))$$

The initial values, $N(1,s)$, $U(1,s)$, $L(1,s)$, $B\_1(1,s)$, $B\_2(1,s)$ can be determined easily.

The final answer is $N(n+1, L)$.

---
Tags: algorithms, optimization, dynamic-programming, matrices
---


# Question
Title: Mathematical models of computation that capture more advanced OS and CPU design features
The universal Turing machine is the standard theoretical model of a stored-program computer. While in one sense as general as possible (Turing completeness), it doesn't *explicitly* contain many of the more advanced features of real-world/practical stored-program computers and their operating systems that have been developed since the 1950's. I am referring to basic features such as,

* the fact that there is an "operating system" at all that can control execution of other stored-programs.
* that there is a distinction between kernel and user mode, that the kernel mode can allocate and remove privileges to programs, and that this is hardcoded into the CPU,
* That programs can execute "system calls" and that this causes a switch to kernel mode and to the OS,
* the notion of "interactive programs", such as a shell with a command line where the input and output strings interact with some non-deterministic entity such as a human,
* multi-programming,
* the notion of CPU "interrupts" that can stop the execution of programs based on events,
* etc.

I know this is a general question, but I am wondering whether there are mathematical models of computation that capture more advanced features such as these. I'm hoping someone could point me in the right direction.

# Answer
Formal verification deals with checking that software and hardware systems are correct by defining mathematical models that capture the behaviour of such systems. This is a large and active area, spanning verification of (components of) real-world hardware, operating systems, software, communication and security protocols, etc. All of these are modeled mathematically, so if you look them up, you will see what people are doing (and they are doing a lot).

Perhaps one lesson to be learned is that mathematical modeling of real-world systems need not proceed by defining one monolithic mathematical model that aims to describe every aspect of a given system – even if we could do that, it would not be terribly useful. Instead, it is much more useful to develop *methods* and *techniques* for building mathematical models, and then have many, many models, each suited to whatever aspect of a system we wish to study.

I can mention two examples (and you can google "formally verified X" for more):

* CompCert \- a formally verified C compiler, a high-assurance compiler for almost all of the C language (ISO C99), generating efficient code for the PowerPC, ARM, RISC-V and x86 processors.
* Verve \- an operating system that is formally verified to be type safe

But yes, there's a whole industry of mathematical models for real-world hardware and software systems.
> 4 votes

# Answer
* The Computer Science answer is **yes**, the Turing machine can tick *all* the boxes of your list, except the last one.
* The fact is that the *functionality* of parallel architectures *can* be emulated on purely sequential architectures, albeit at a very slow speed. A real world example for this is simulating and debugging a CUDA program on a CPU.
* In practice, the **Finite State Machine** is the true computational model of any real computer system, i.e. a computer with **finite** memory. The finite state machine can model arbitrarily complex behaviour. Finite State Machines can model both software and hardware.
* In digital hardware design, the FSM+Datapath model is the commonly used abstraction of complex digita hardware. See Why did finite-state controller with datapath win? for a discussion on this.
* Privilege levels can be easily modeled using finite state machines.
* In the semiconductor industry, a C++ library called SystemC is often used for modelling System-On-Chips and digital electronic subsystems. SystemC supports many types of abstract models.
* TLM is a library in SystemC that stands for Transaction Level Models, and is widely used for early design state space exploration.
> 0 votes

---
Tags: turing-machines, reference-request, operating-systems, computation-models, cpu
---


# Question
Title: Do modern computers prevent instructions being executed by audio? If so, how?
Most know that early phones and modems, and still, fax machines, sent information through the use of tones. This got me thinking - could audio be a viable vector for executing instructions by a bad actor? (By this I mean the use of a carefully crafted audio file that when played could trick some part of the OS or underlying hardware to execute actual machine code)

I imagine there are means to prevent this (I hope), but I'm unable to find any specific documentation or examples of this being considered, nor any defenses being placed into software or hardware.

This is quite a theoretical question, mostly born out of curiosity, and something I was hoping to find a study on, with no luck.

# Answer
> 2 votes
It already exists and we can find the examples with CVE mpeg or CVE mp3, or searching some other formats. Three examples among the many;

> * CVE-2014-2299
> Buffer overflow in the mpeg\_read function in wiretap/mpeg.c in the MPEG parser in Wireshark 1.8.x before 1.8.13 and 1.10.x before 1.10.6 allows remote attackers to execute arbitrary code or cause a denial of service (application crash) via a large record in MPEG data. Publish Date : 2014-03-11 Last Update Date : 2016-06-02

> * CVE-2010-0480
> Multiple stack-based buffer overflows in the MPEG Layer-3 audio codecs in Microsoft Windows 2000 SP4, XP SP2 and SP3, Server 2003 SP2, Vista Gold, SP1, and SP2, and Server 2008 Gold and SP2 allow remote attackers to execute arbitrary code via a crafted AVI file, aka "MPEG Layer-3 Audio Decoder Stack Overflow Vulnerability."

> * CVE-2010-0818
> The MPEG-4 codec in the Windows Media codecs in Microsoft Windows XP SP2 and SP3, Server 2003 SP2, Vista SP1 and SP2, and Server 2008 Gold and SP2 does not properly handle crafted media content with MPEG-4 video encoding, which allows remote attackers to execute arbitrary code via a file in an unspecified "supported format," aka "MPEG-4 Codec Vulnerability."

# Answer
> 2 votes
Yes, it absolutely could, if the software that plays the audio has a vulnerability that allows that to happen.

I suggest learning about the nature of these vulnerabilities, to understand better how it can happen -- and then you will see that it can happen with any data, if the software that interprets the data has the right (wrong) sort of vulnerability. You might start by reading about buffer overrun vulnerabilities and code injection vulnerabilities.

Without a vulnerability, no, that won't happen.

# Answer
> 0 votes
I'm far from a expert hardware engineer but hardware like old phones transmit sound with a range of frequency that's translated by some oscillating circuit. It is dead hardware that doesn't do anything except transmit current that makes a small speaker vibrate at a specific frequency which create sound. It doesn't really execute instructions like a processor would.

Nowadays, you have complex microphones which capture sound. There are complex controllers in the microphones probably which execute instructions but not CPU ones.

For example, on x86-64, a USB microphone is polled by an xHC. The xHC polls the microphone until it has data. The xHC doesn't execute CPU instructions but it can write in RAM directly. This is definitely a vulnerability but is the kind of attack that would require having a combined control of the computer and to be in range of the microphone AND a vulnerability in the hardware controller (the xHC). The xHC does write in data but at the demand of software. Since it is DMA, if the xHC writes in RAM at some position where it shouldn't then, it is an attack vector. I have a hard time to understand why some sound vs other would trigger this kind of attack. I also doubt that there is such vulnerability in USB controllers.

The biggest threat is probably software. Software is audited a lot but is known to have lots of bugs and vulnerabilities. Software could overwrite some part of itself by triggering DMA writes for example. That could drastically change the behaviour of software and be an attack vector.

Don't get me wrong though. The question is "Do modern computers prevent instructions executed by audio? If so how?". The answer is they don't have to because audio isn't executing instructions. There is a lot of hardware in between and even this hardware is DMA so it doesn't execute instructions. It writes in RAM directly so this is the vulnerability not that "audio executes instructions".

---
Tags: reference-request, cpu, software-engineering, security
---


title: Time Complexity Sigma Notation

text:
# Question
Title: Time Complexity Sigma Notation
Consider the following pseudo-code:

```
counter = 0
for (k = 16; k > 0; k /= 2)
    for (j = 0; j < k; j++)
        counter++

```

I get that the time complexity is $O(n)$ when I examine the code, but I do have a question regarding the formal complexity analysis:

$$\begin{align} T(n) &= \sum\_{i=1}^{\lceil \log\_2 n \rceil} \sum\_{j=1}^{2^i - 1} c = c \cdot \sum\_{i=1}^{\lceil \log\_2 n \rceil} (2^i - 1) \\ T(n) &= c\left( 2 \left\[ 2^{\log\_2 n} -1 \right\] - \log\_2 n \right)\\ T(n) &= c\left( 2n - 2 - \log\_2 n \right)\\ T(n) &= \Theta(n) \end{align} $$

I understand outer loop must be $\log\_2(n)$ but why do we say the inner loop's upper bound is $2^i$?

# Answer
> why do we say the inner loop's upper bound is $2^i$?

The outer sum (sigma) is going backwards, so to speak. The first iteration of the sigma makes the inner summation from $j=1$ to $j=1$, whereas, in fact, it should be from $j=1$ to $j=16$ (in your case).

In each iteration of the outer loop, we are *doubling* the variable $k$ from the outer `for`-loop (recall that we terminate the sum after $\log n$ iterations). Since $k$ is doubled, the inner sum (sigma), which corresponds to the inner `for`-loop needs to go from $j=1$ to $2^i$ to reflect the doubling of $k$.
> 1 votes

---
Tags: complexity-theory, time-complexity, big-o-notation
---


# Question
Title: NP-Completeness of SAT with given hamming weight k
I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction.

**Input**: A propositional formula $\varphi$ and a number $k$.

**Output**: Yes if exists an valuation $\sigma$ that satisfies the formula $\varphi$ and the hamming weight of $\sigma$ is $k$ ( Exactly k propositional variables have the value 1 on the assigment $\sigma$). Otherwise, output is NO

# Answer
> 1 votes
There is a simple reduction from the Clique problem, i.e. given some (undirected, simple) graph $G = (V, E)$ and some number $k$ we are asked whether or not $G$ contains a clique of size at least $k$.

Now, introduce variables $x\_v$ for every vertex $v \in V$ and consider the formula $$\psi(G) = \bigwedge\_{v \in V} \bigwedge\_{w \in V} (x\_v \wedge x\_w \to \[Evw\]) $$ where $\[Evw\]$ is replaced by $1$ if $vw \in E$ and $0$ otherwise. Then some set $X \subseteq V$ is a clique if and only if setting precisely those variables corresponding to the vertices in $X$ to $1$ (and all others to $0$) yields a satisfying assignment for $\psi(G)$.

Let us prove this rigorously:

* Suppose that $X$ is a clique. Then for any distinct $v, w \in X$ the graph $G$ contains the edge $vw$, and hence $x\_v \wedge x\_w \to \[Evw\]$ evalutes to $1$. Also note that if at least one of $v$ and $w$ is not in $X$, then $x\_v \wedge x\_w \to \[Evw\]$ is trivially satisfied as the premise of the implication does not hold. Hence setting exactly the variables corresponding to the vertices in $X$ to $1$ satisfies $\psi(G)$.
* Suppose that $X$ is *not* a clique. Then there must exist distinct $v, w \in X$ such that $vw$ is not an edge in $G$ and hence, $x\_v \wedge x\_w \to \[Evw\]$ evaluates to $0$, yielding that setting precisely the variables corresponding to the vertices in $X$ to $1$ does not satisfy $\psi(G)$.

This immediately gives us the desired reduction by mapping Clique-instances $(G, k)$ to $(\psi(G), k)$. Clearly, computing $\psi(G)$ from $G$ can be done in polynomial time, and $\psi(G)$ has a satisfying assignment of weight $k$ if and only if $G$ has a clique of size $k$.

We conclude that your problem is $\mathsf{NP}$-complete.

---
Tags: complexity-theory, np-complete, reductions, decision-problem, propositional-logic
---


# Question
Title: Dividing a String According to the Pumping Lemma
I have some questions about how a string can be divided into pieces according to the pumping lemma. I am learning from Michael Sipser’s book Introduction to the Theory of Computation, 3rd Edition. He states the pumping lemma as follows.

> **Pumping lemma** If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:
>
> 1. for each $i≥0, xy^i z∈A$,
> 2. $|y|\>0$,
> 3. and $|xy|≤p$.

Sipser says that when $s$ is divided into $xyz$, either $x$ or $z$ may be $ε$, but not $y$ (condition 2).

He provides an example to show how the pumping lemma can be used to prove that the following language $B$ is not regular.

> Let $B=\\{0^n 1^n | ≥ 0\\}$.

It is a proof by contradiction. He assumes $B$ is regular and presents three cases to show that it is not. In each case he splits a string $s$ from $B$ into $xyz$ in a different way. He chooses $s$ to be the string $0^p1^p$. In one case, Sipser lets $y$ consist only of 0s. Here are my questions:

1. In this case, is it possible for $y$ to consist of $p$ 0s and for $x$ to be the empty string if $|xy|≤p$ (condition 3)?
2. If so, do you agree that a case can be presented where $s$ is divided into $xyz$ such that $x=ε,y=0^p,z=1^p$?
3. If so, do you agree that the string $xyyz$ contains more 0s than 1s?
4. If so, do you agree that the string $xyyz$ is not in B?

I would greatly appreciate if you could answer all the questions in a numbered list format.

# Answer
Here is the answer.

1. Yes.
2. Yes.
3. Yes.
4. Yes.
> 1 votes

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: A query regarding the paper/statement: P=BPP unless E has sub-exponential circuits
I was going thorough this paper: (*P=BPP unless E has sub-exponential circuits*: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf) and I am somewhat struggling with some basics from the paper that I quote below:

**Definition 1:** Let $m$ and $l$ be positive integers. Let $f:\\{{0,1}\\}^m→\\{{0,1}\\}^l$. $S(f)$, the worst-case circuit complexity of $f$, is the minimum number of gates for a circuit $C$ with $C(x)=f(x)$ for every $x∈\\{{0,1}\\}^m$.

**2.2 Hardness versus Randomness:** For this section only, we use $f,g,h$ to denote a Boolean function on strings of all lengths, and by $f\_n,g\_n,h\_n$ their segments on n-bit strings. Also, let $E=DTIME(2^{O(n)})$.

**Theorem 2:** If there is a Boolean function $f∈E$ with $S(f\_n )=2^{Ω(n)}$ then $P=BPP$.

**Query 1:** I am assuming the boolean function is given by its truth table of size $2^m.l$ with all possible entries. I am unclear what it means by this truth table (denoted by $f$) $f∈E/DTIME(2^{O(n)})$? How do you assign the truth table its runtime without having some circuit represent it? I am clear about the fact that $S(f)$ represents the size(i.e. the number of gates in) the smallest possible circuit that represents/calculates $f$.

**Query 2:** Can someone please explain and simplify the theorem ("if...then") part? I am clear about the complexity classes $P$ and $BPP$, but I am struggling with the condition?

# Answer
The function $f$ is a Boolean function. It maps an input of arbitrary length to a single bit. Its signature is $$f\colon \\{0,1\\}^\* \to \\{0,1\\}.$$ We denote its restriction to $n$-bit inputs by $f\_n$, whose signature is $$f\_n\colon \\{0,1\\}^n \to \\{0,1\\}.$$ For example, the parity function returns the parity of its inputs: $$ f(x\_1,\ldots,x\_m) = x\_1 \oplus \cdots \oplus x\_m, $$ where $m \geq 0$ is arbitrary. The restriction for inputs of length $n$ is $$ f\_n(x\_1,\ldots,x\_n) = x\_1 \oplus \cdots \oplus x\_n. $$ Here the input length is fixed.

The main theorem states that P=BPP if there is some function $f$ such that

1. There is a constant $C \> 0$ and a Turing machine computing $f$ which runs in time $C2^{Cn}$ on inputs of length $n$.
2. There is a constant $c \> 0$ such that for all $n$, any circuit computing $f\_n$ has size at least $c2^{cn}$.
> 1 votes

---
Tags: complexity-theory
---


title: What makes 'interrupt vectors' vectors?

text:
# Question
Title: What makes 'interrupt vectors' vectors?
I've recently been learning about interrupt vectors, partly from this Wikipedia page.

I've understood that different processors will have different types of interrupts, and the interrupt vector table stores the information about where code evaluation should move to when each type of interrupt occurs. As far as I'm aware I have understood this well, please let me know if there's something I'm missing.

What I don't understand is, why is this information referred to as a vector? To me it seems that we are storing the information of a pointer to a memory address for each type of interrupt, so I would more naturally call this an 'interrupt pointer table'.

I'm coming from a background in mathematical physics, so to me 'vector' generally refers to a physical quantity with magnitude and direction, or an element of a vector space (or both). Does the 'vector' part of the 'interrupt vector' have some interpretation as a vector in one of these two senses? I can see that you could imagine an arrow pointing to a certain memory address as a vector, but if you went with this reasoning then all pointers would be vectors.

# Answer
Vector has different meanings depending on the context. I would say that, in this case, the word vector is used because it enables "directing" the IRQs to the right handler. You could define vector to be the entry in the IVT that enables directing the IRQs. They are more like vectors of transmission or vectors that enable transmission rather than the vectors known in the physics world.

Also, I don't know about other types of processors but x86 family of processors refer to IVT when in Real Mode (emulated 16 bits mode) and IDT when in protected mode (32 bits) and in long mode (64 bits). IDT stands for interrupt descriptor table. This allows programmers of these modes to differentiate between the Real Mode table and the protected/long mode table.

I agree though that the use of descriptor instead of vector is better.
> 2 votes

---
Tags: terminology, assembly
---


# Question
Title: Prove that $\{xyz \mid zyx \in A \}$ is regular if $A$ is regular
Does the following work and is there anything possibly simpler?

Let $X = (Q, \Sigma, \delta, s, F)$ be a DFA for $A$. Intuitively, we want to "remember" (or guess) two states $p$ and $q$ such that $s \stackrel{z}{\longrightarrow^{\ast}} p \stackrel{y}{\longrightarrow^{\ast}} q \stackrel{x}{\longrightarrow^{\ast}} f$ where $f \in F$ is a valid "run" in $X$ (Also by $\stackrel{w}{\longrightarrow^\ast}$ I mean a transition over letters of $w$).

Consider $X' = \left( Q \times Q \times \left\\{ 0, 1, 2 \right\\}, \Sigma \cup \\{\varepsilon\\}, \delta', S, F' \right)$ where $S = \left\\{ (p, q, 0) \mid \text{$q$ is reachable from $p$} \right\\}$ and $F' = \left\\{ (p, p, 2) \mid p \in Q \right\\}$. The idea will be to break the automaton into 3 parts joined together by $\varepsilon$-transitions. The transition function is defined as follows: \begin{align\*} \delta'\left( (p, q, n), a \right) &= (p, \delta(q, a), n) \quad\forall\\, n \in \left\\{ 0, 1, 2 \right\\}, \\ \delta'\left( (p, f, 0), \varepsilon \right) &= (p, p, 1)\quad\text{where $f \in F$}, \\ \delta'\left( (p, q, 1), \varepsilon \right) &= (p, s, 2). \end{align\*} As is evident, we want to store the state $p$ in a \`\`memory'' throughout any run starting at $(p, q, 0)$. This way, if $s \stackrel{z}{\longrightarrow^{\ast}} p \stackrel{y}{\longrightarrow^{\ast}} q \stackrel{x}{\longrightarrow^{\ast}} f$ is a valid run in $X$, then we have the following valid run in $X'$ and vice versa: \begin{equation\*} (p, q, 0) \stackrel{x}{\longrightarrow^{\ast}} (p, f, 0) \stackrel{\varepsilon}{\longrightarrow} (p, p, 1) \stackrel{y}{\longrightarrow^{\ast}} (p, q, 1) \stackrel{\varepsilon}{\longrightarrow} (p, s, 2) \stackrel{z}{\longrightarrow^{\ast}} (p, p, 2). \end{equation\*}

# Answer
> 0 votes
You can basically follow the same reasoning without explicitly constructing the resulting finite automaton, using closure properties instead. That might save a lot of technical details. And it makes states $p,q$ explicit, rather than remembering them in states.

Given $X=(Q,Σ,δ,s,F)$ the DFA for $A$, now consider some derived automata that only change initial and final states. Let $X\_{pq}=(Q,Σ,δ,p,\\{q\\}) $ and $X\_{pF}=(Q,Σ,δ,p,F) $.

Then $L(X) = \bigcup\_{p,q\in Q} L(X\_{sp}){\cdot}L(X\_{pq}){\cdot}L(X\_{qF})$.

The language you are looking for equals $\bigcup\_{p,q\in Q} L(X\_{qF}){\cdot}L(X\_{pq}){\cdot}L(X\_{sp})$.

---
Tags: regular-languages, automata, closure-properties
---


# Question
Title: NFA has power to be in several states at once implies NFA has ability to guess about its input. How?
I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "NFA has ability to guess about its input". What is this trying to say? Can you explain with example using NFA rather than the one used by hopcroft book.

# Answer
> 2 votes
The ability to "guess" is an informal but often helpful analogy on the NFA's capability to solve problems with much fewer states than the equivalent DFA would. I will demonstrate with an example.

Let $L\_n = \\{ w \in \\{a, b\\}^\* : \text{the } n\text{th-last character of } w \text{ is } a\\}$.

For example, $L\_1$ is the language of strings with $a$ as the final character, $L\_2$ is the language of strings with $a$ as the second-from-last character, etc.

For every fixed $n$, $L\_n$ is regular and therefore a DFA accepts it. It is fairly simple to create these DFAs for small values of $n$: for example, when $n=2$ you only need four states: one for each possible sequence of two characters (the last two that were read, with the initial state also being served by the state $bb$). States representing $aa$ and $ab$ are accepting.

However, these automata grow very fast with $n$: you need $2^n$ states, to be exact, match $L\_n$ with DFA. Let's approach the problem with an NFA.

The NFA, instead of having to maintain a record of $n$ symbols all the time, can "guess", whenever it sees an $a$ symbol, that this $a$ is the $n$th to last symbol of the string. The NFA will look like this for $n=3$:

```
(q0, a OR b) -> q0
(q0, a) -> q1
(q1, a OR b) -> q2
(q2, a OR b) -> q_accept

```

The NFA will always be in the initial state $q\_0$, and when it encounters an $a$, it will also launch a "guess" at $q\_1$. If this $a$ indeed was the $n$th last character, this "guess" will be in the state $q\_{accept}$ after reading two more characters. Since the NFA is always in the state $q\_0$, each $a$ launches a similar guess and multiple "guesses" can occur in parallel, eg. if there are successive $a$ symbols in the string.

# Answer
> 0 votes
Here is an example: the language of all words over $\\{a,b,c\\}$ which *do not* contain all letters.

We can construct an NFA for this language by mimicking the regular expression $$ (a+b)^\* + (a+c)^\* + (b+c)^\*. $$ The NFA contains four states: an initial state $q\_0$ which leads, via $\epsilon$-transitions, to three other states, all accepting: one $q\_1$ with self-transitions labeled $a,b$, another $q\_2$ with self-transitions labeled $a,c$, and the final one $q\_3$ with self-transitions labeled $b,c$.

We can think of the NFA as "guessing" which of the letters is missing. If it guesses that $c$ is missing, then it transitions to the state $q\_1$; if it guesses that $b$ is missing, then it transitions to the state $q\_2$; and if it guesses that $a$ is missing, then it transitions to the state $q\_3$. In the remainder of its run, it verifies this guess. If it manages to scan the entire input without seeing the guessed missing letter, then the word is accepted.

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


# Question
Title: What is the runtime overhead and how many more states are needed for simulating a TM whose head may remain stationary by a standard TM?
The standard Turing Machine (TM) can only move left and right. When I simulate a TM whose head may remain stationary and I execute the stationary move, then I need to make two steps with the standard TM: go left and then right. So does this mean I need twice the amount of steps and I need twice the amount of states?

# Answer
Twice the amount of steps and twice the amount of states suffice for the simulation.

The sketch is as follows: replace every transition of the original TM that keeps the head still and changes the state to $q$ with two transitions: first move the head right and change the state to a new intermediate state $q'$, then whenever the state is $q'$ move the head left (without modifying the current tape symbol) and go to state $q$.

You can actually construct an equivalent TM that uses at most one more state and requires at most the same number of steps. The sketch is as follows: consider a transition of the original TM that keeps the head still. This transition writes $\alpha$ to the current tape cell and changes the state to $q$. Then you can find the next transition that will be executed by the machine, i.e., the transition performed when the current tape symbol is $\alpha$ and the current state is $q$. Suppose that the latter transition writes $\beta$ and moves to $q'$. If the transition also moves the head, then you can "shortcut" the first transition by directly writing $\beta$ and moving to $q'$.

If the second transition does not move the head, then the process can be repeated. Eventually (there are at most $|\Gamma| \cdot |Q|$ distinct transitions that can be applied, where $\Gamma$ is the tape alphabet) you either reach a transition that moves the head/halts the machine, or you discover that the machine must loop.

In the former case you can shortcut all involved transitions to the last one. In the latter case, you can add only a single (global) additional state to ensure that the machine runs forever while moving its head.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Find element with at least $\frac{n}{2}$ repeats in an array
I saw this question on my college "Design of Algorithms" exam but I could not solve it:

Given an array $A\[1..n\]$ of integers. find an element which is repeated at least $\frac{n}{2}$ times using **Divide and Conquer** algorithm in $O(n\log{n})$ if such element exists.

Correctness of the algorithm must be proven.

---

I wonder if there's any answer for it.

# Answer
Without sorting the array, you could use the following divide-and-conquer algorithm. For simplicity, I will suppose that one searches an element that appears strictly more than $\frac{n}{2}$ times, but it could also be done with the equality case.

```
Algorithm: Majority(A)
Input: array A[1...n]
Output: element x that appears > n/2 times if it exists, or false otherwise

If n = 1:
   return A[1]
Else:
   x1 := Majority(A[1...n/2])
   x2 := Majority(A[n/2+1...n])
   If x1 ≠ false and x1 appears > n/2 times in A:
      return x1
   If x2 ≠ false and x2 appears > n/2 times in A:
      return x2
   return false

```

The algorithm is correct, because if $x$ appears $\>\frac{n}{2}$ times in $A$, then $x$ appears $\>\frac{n}{4}$ times in at least one half of $A$.

The time complexity $C(n)$ verifies:

* $C(1) = \mathcal{O}(1)$;
* $C(n)$ is the sum of:
    + $2C(n/2)$: both recursive calls to `Majority`;
    + $\mathcal{O}(n)$: verification of $x\_1$ and $x\_2$ in $A$

So $C(n) = 2C(n/2) + \mathcal{O}(n) = \mathcal{O}(n\log n)$.
> 2 votes

# Answer
This is probably the simplest but not the optimal way to solve your problem.

Since you can use $O(n\log{n})$ time and your algorithm needs to use Divide and Conquer, you can solve the problem by:

```
1. Use Merge Sort to sort the array A
2. For i = 1...n/2
3.    If A[i] == A[n/2 + i] return A[i]

```

The first step works in $O(n\log{n})$ which is the worst case complexity for merge sort and the for loop works in $O(n)$ (i.e., $\frac{n}{2}$ comparisons) in the worst case, so the overall complexity is $O(n\log{n})$. Furthermore, if $A\[i\] == A\[\frac{n}{2} + i\]$, it is guaranteed that the elements in between are also equal to $A\[i\]$, because the array is sorted. If no such element has been found by the midpoint of the array, $A\[\frac{n}{2}\]$, no such number exists in the array since any other element appears at most $\frac{n}{2} - 1$ times.
> 0 votes

# Answer
Say I have 201 integers. You need to find one that occurs at least 101 times. Split the integers into 100 and 101 integers. To occur 101 times in total, your integer must occur 51 times in one of the two halves.

Now you turn this into an algorithm.
> 0 votes

---
Tags: algorithms, divide-and-conquer
---


# Question
Title: CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof
In Cormen et. al., *Introduction to Algorithms* (3rd ed.), I don't get a line in the proof of Lemma 26.1 which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| =|f|+|f'|$ (this is pp. 717-718).

My confusion: When arguing *flow-conservation* they use the definition of $f\uparrow f'$ in the first line to say that for each $u\in V\setminus\\{s,t\\}$

$$ \sum\_{v\in V} (f\uparrow f')(u,v) = \sum\_{v\in V} (f(u,v)+f'(u,v) - f'(v,u)), $$

where the augmented path is defined as

$$ (f\uparrow f')(u,v) = \begin{cases} f(u,v)+f'(u,v) - f'(v,u) & \text{if $(u,v)\in E$}, \\ 0 & \text{otherwise}. \end{cases} $$

Why can they ignore the 'otherwise' clause in the summation? I don't think the first clause evaluates to zero in all such cases. Do they use flow-conservation of $f$ and $f'$ in some way?

# Answer
**Note:** The notations and definitions used below are borrowed from the third edition of the book.

To answer this question, first, observe that if $(u,v) \notin E$, then by flow definition,

$$f(u,v) = f'(u,v) = (f \uparrow f')(u,v) = 0 \\, .$$

Furthermore, since $f'(v,u) \le c\_f(u,v) = f(u,v)$, it is obtained that $f'(v,u) = 0$. This simply implies that $\forall (u,v) \notin E$,

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) = 0 \\, .$$

Therefore, the definition of augmented flow can be generalized for all $(u,v) \in V \times V$ to be as follows:

$$ (f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) \\, .$$

The rest of the proof follows from this observation which, of course, is not explicitly explained in the text.

P.S. Please note that the formal definition of flow in the third edition of the book is significantly different from that in the second edition. In particular, in the second edition, there is a flow property named *skew symmetry* that requires $f(u,v) = - f(v,u), \forall u,v \in V$. This property has been removed in the third edition due to the assumptions that $(v,u) \notin E$ if $(u,v) \in E$ and $f(v,u) = 0$ if $(v,u) \notin E$. Because of this, the definitions of flow conservation in two editions are also different. Lots of such confusions, in fact, come from this change of definition that is presumably intended to simplify the proofs, but turned out being more perplexing. I personally would rather to stick to the second edition of the book for this particular chapter.
> 10 votes

# Answer
There is an errata in this printing, the corrected proof is found in the link below. Indeed, the correction requires you to consider subsets $V\_1=\\{v:(u,v)\in E\\}$ and $V\_2=\\{v:(v,u)\in E\\}$.

https://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf
> 3 votes

---
Tags: algorithms, network-flow
---


# Question
Title: Maximum number of teams that can be formed with given age such that the sum of their age is more than 18
An array of students age is given : $ A = \\{ A\_1,A\_2, ..., A\_n \\} $. Form maximum number of teams such that the sum of age for each team is more than 18. Note that each team consists of only 2 people.

I came across this question in an algorithm book without any answer.

**My attempt :**

Sort A in ascending order. Calculate the sum of biggest and smallest age from A. If the sum was more than 18 then these two should form a team, otherwise remove the smaller one from A. Continue this algorithm until we reach $|A| = 0$ or $|A| = 1$.

I believe this algorithm is the optimal answer but I don't know how to prove it.

# Answer
If you had an optimal solution not containing the oldest player, then we take any team and replace the older team member with the oldest player, and you would still have an optimal solution. So we know there is an optimal solution including the oldest player.

If oldest player and some player X together are not older than 18, then player X cannot be member of any team, so they can be removed without affecting the solution.

That done, if there is an optimal solution including the oldest player and some other player who is not the youngest player, you can replace the other player with the youngest player, and the solution is still optimal.

So you can find an optimal solution by: 1. Picking the oldest player X. 2. Removing all players Y where X + Y ≤ 18. 3. Having no team at all if X is the only player remaining. 4. Forming a team consisting of X and the youngest player, then putting the other players into teams in an optimal way.
> 1 votes

---
Tags: greedy-algorithms
---


title: Restriction in description logic

text:
# Question
Title: Restriction in description logic
> $Human ⊓ ¬Female ⊓ (∃married.Doctor) ⊓ (∀hasChild.(Doctor ⊔ Professor))$

Here, $∃married.Doctor$ means if there exists an individual who is married to Bob belongs to $Doctor$ concept.

But my confusion is what if I use $∀$ instead of $∃$ will this mean:

1. Bob is married to individuals all of them belongs to $Doctor$ concept or
2. Bob is married to all from $Doctor$ concept. (like FOL if I pick anyone from Doctor domain married to Bob)

# Answer
> 1 votes
Below is the usual definition of $\forall$ and $\exists$ in description logic:

> $\forall R.C=\\{x \in \Delta | \forall y, (x,y) \in R \to y \in C \\}$
> $\exists R.C=\\{x \in \Delta | \exists y, (x,y) \in R \land y \in C \\}$

So apparently in your case if you use $\forall$ instead of $\exists$ and assuming your Bob is a concept assertion of your above recursively constructed concept, then your interpretation 1 is the right one. Also note strictly speaking in DL Doctor as a concept name is not a domain, but a subset of the domain of a certain language of DL.

---
Tags: first-order-logic
---


# Question
Title: Polytime Mapping Reduction from Language A to Language A (identity)
How would I create a polytime mapping reduction to prove A ≤p A for any language A.

I was thinking to assume A is in P to start. For every : ∈ iff ()∈.

But I am not sure what to do from there, any advice? I don't get how to show that you can polytime reduce a function to itself, because if you assume A has a Turing machine and a polytime decider, a function that is a polytime mapper, then how do you show its equal to each other?

# Answer
> 1 votes
You need to construct a polytime function $f$ with the following property:

> For every $x$: $x \in A$ iff $f(x) \in A$.

You take it from here.

---
Tags: complexity-theory, reductions, discrete-mathematics, polynomial-time-reductions
---


# Question
Title: Reduction: Does polytime reduction imply Turing reduction?
I am unsure if given $A \leqslant\_p B$, does that imply that $A \leqslant\_T B$.

If we can polytime reduce $A$ to $B$, that would imply there is a decider for $A$ that runs in polynomial time which can be mapped to the decider for $B$, meaning we would halt on any input that is run on the decider for $B$.

# Answer
> 1 votes
I think you got yourself a bit confused. If $A \le\_p B$ there there is a polynomial-time computable function $f$ that maps **instances** (not deciders) of $A$ into **instances** of $B$ such that $x \in A \iff f(x) \in B$. This means that $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes instance of $B$.

Notice how this definition does not involve deciders halting. In fact $A$ and $B$ could even be languages for which no decider exists.

That said, if $A \le\_p B$ then $A \le\_T B$ since there exists a Turing machine with an oracle for $B$ that decides $A$. A possible Turing machine operates as follows on input $x$:

* It simulates a Turing machine that computes $y=f(x)$.
* It invokes the oracle for $B$ on $y$.
* If the oracle returns "yes", it accepts. Otherwise it reject.

Notice that we did not even need to use the hypothesis that $f$ can be computed *in polynomial time*.

---
Tags: computability, reductions, polynomial-time-reductions
---


# Question
Title: If two languages are polytime reducable, does that imply they are also turing reducable
Is it possible for a pair of languages where A ≤T B but not A ≤p B?

I am not sure if this could be the case since a turning reduction would imply we can use a decider for one language to decide another.

# Answer
Hint: take $A=\emptyset$ and some $B\in R\setminus P$ where $R$ is the set of all recursive languages.
> 0 votes

---
Tags: computability, reductions, polynomial-time-reductions
---


# Question
Title: Recursive decomposition if a sequence can be parsed in both directions
Given a sequence/string of values and an algorithm that can process said sequence in both directions and obtain the same result - does it follow that the problem can in fact be decomposed in a divide-and-conquer sort of manner?

The sum of a sequence of numbers can be computed sequentially both from left to right and from right to left - it also can be computed if we recursively compute the sum of the left/right halves of the sequence and apply the sum operator on the results of the subproblems. Would work for any associative operation (sum, mul, max, min, etc etc).

Even more, the argument can be made for parsing some languages - json/lisps can be parsed in both directions and all it takes is to find a good way to merge partial results.

Intuitively this should work - is there a theorem that proves this? Does it have a name?

# Answer
> 0 votes
http://research.nii.ac.jp/~hu/pub/popl09.pdf

I watched a talk by Guy Steele years ago which was nowhere to be found so I thought it's my imagination. Said talk was reuploaded and he mentions this implication and paper at https://youtu.be/dPK6t7echuA?t=3755 this timestamp

---
Tags: parallel-computing, divide-and-conquer
---


# Question
Title: Find nodes at k distance from given source node in an undirected cyclic graph if k<=1e9
I have encountered this problem many times. In an undirected graph, you need to get all the nodes/one node that is `k` distance away from the given source node (`src`). Given that the edge-weight is `1` for all the edges, the graph can have cycles.

**constraints:**

```
1<=N<=1e5
0 <= M <=N
1<=k<=1e9
1<=src<=N

```

where, N = total number of nodes M = total number of edges

Subproblem: There is only one cycle in the graph.

I tried to solve it using DFS and BFS with k breadth/depth, but that is not an efficient way to do it. How can we solve it efficiently considering the given constraints?

# Answer
> 0 votes
Do a regular BFS (for at most $k$ iterations, if you want to optimize it), and then loop through the vertices and take all of those that have $k$ distance.

---

This approach works in $O(|V|+|E\_k|)$ where $E\_k$ is the set of all edges in the subgraph formed by taking all nodes with distance at most $k$ from $s$ (it is also known as the ball with radius $k$ around $s$).

Its not hard to see that this is optimal and you cant really do better than that.

---
Tags: algorithms, graphs
---


# Question
Title: Regular expression for set of all strings containing no 3 consecutive 0s?
The answer is

$1^\*01^\*01^\*+1^\*(0+00+\in)1^\*$

If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice?

How do I understand what the regular expression is doing just like in this case here.

I think I can create DFA for this, but not sure if that would help me to create regular expression(I know there are posts to convert dfa to regular expression but I don't want that hassle).

# Answer
> 1 votes
If you don't want to go through a DFA (which would definitely be the easiest *systematic* way of doing this), you can approach it by viewing the language as strings of 2, 1 or 0 zeros interleaved by ones:

$$(00 +0 + \epsilon)(1(00 + 0 + \epsilon))^\*$$

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


# Question
Title: Algorithm to reduce a Circuit-SAT to NAND-SAT
I am trying to construct an algorithm to reduce OR, AND and NOT gates into NAND-SAT. Can someone give me a hint as to where to start?

# Answer
Rewrite each gate with its equivalent NAND construction.

https://en.wikipedia.org/wiki/NAND\_logic
> 1 votes

---
Tags: reductions, satisfiability, circuits, polynomial-time-reductions
---


# Question
Title: What does DFA that accepts at least 1 a or at least 1 b mean?
What are the language accepted by this DFA?

The truth table of OR-:

But I am unable to deduct what this dfa will accept? Say-: P=at least 1 a Q=at least 1 b

So DFA should accept both ab. Or in another case it could accept a and in another case it could accept b? Is this the interpretation?

# Answer
This will accept any word containing $a$ or $b$. There's a simpler way of describing the set of all words accepted by the FA, by the way. Can you see it?
> 0 votes

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


title: Average case complexity and Big-O

text:
# Question
Title: Average case complexity and Big-O
In this Wikipedia article on Average-case complexity there is the text:

> For example, many sorting algorithms which utilize randomness, such as Quicksort, have a worst-case running time of $O(n^2)$, but an average-case running time of $O(n \log(n))$, where n is the length of the input to be sorted.

My question is about the use of $O$ as our function for analyzing the average-case scenario. My understanding of $O$ is, essentially, $\leq$, which seems like an odd choice to use for average time, which could be much more tightly defined (perhaps like $\Theta$?).

Is Wikipedia correct to use $O$ here, and if so, why?

# Answer
Wikipedia use is correct. The notation $O(\cdot)$ denotes a set of function, in particular $O(f(n))$ contains all functions $g(n)$ for which there is a constant $c$ and a choice of $n\_0$ such that $g(n) \le c f(n)$ for all $n \ge n\_0$.

The average running time of an algorithm is some function of its input size $n$. Therefore it is perfectly correct to say that a function belongs to a set of functions.

Notice also that if $g(n) \in \Theta(f(n))$ then $g(n) \in O(f(n))$.
> 2 votes

---
Tags: time-complexity, average-case
---


# Question
Title: Why does floating point become less accurate as the powers of 2 increase?
https://fabiensanglard.net/floating\_point\_visually\_explained/

I was reading this article where the exponent and the mantissa are explained as the window and offset respectively. As the gap between powers of 2 increases, the granularity of the incremental steps that the offset offers will decrease. Is this an intentional design decision?

# Answer
Yes, almost certainly. We only have a fixed number of bits, so allowing the most significant bit to represent different powers of two dramatically increases the range of useful values we can represent.

And really, it's a logical behavior. If you're looking at a number in the trillions, who cares if you are off by .0000001? An error of that size has no meaningful impact in almost any real situation.

On the other hand, if you're looking at a number in the ten-thousanths, a gap of .0000001 is actually pretty substantial. We would want to be careful at that granularity to maintain exacting precision.
> 1 votes

---
Tags: floating-point
---


# Question
Title: Memory-efficient list of N unique integers from 0..N-1 with fast lookup
We want to represent a list of $n$ unique integers between $0$ and $n-1$ in a memory-efficient way. The only operation we need to support is looking up the $n\text{-th}$ element.

What are some of the most compact data structures that can do the lookup in $O(1)$ or $O(\log n)$?

---

Naive example: an array of $\log n$-bit integers. ($n \log{n} $ bits)

Intuitively it seems that we can do better. If we didn't have the fast lookup requirement, the data structure could simply be a permutation index ($ ⌈\log{n!}⌉ ≈ n \log{n} − 1.44n$ bits).

# Answer
> 1 votes
This is equivalent to storing a permutation of $n$ items in memory. There are in general, $n!$ ($n$ factorial) such permutations, and it is well known that $\log(n!)=\Theta(n\log(n))$. Hence, you will need **at least** $\Omega(n\log(n))$ bits to represent the permutations (which is what you get from the naive solution).

So without even the requirement about the lookup time, you are bound to have at least this much memory consumed - and sadly you cannot compress it further.

# Answer
> 0 votes
The naive solution may be n log n bits. But for the first number you have n choices; you have n-1 choices for the second number, n-2 choices for the third number etc. So log(n!) bits, rounded up to the next integer, would be a possibility.

In practice, if you want the lookup to be fast, looking up number k should locate a range of bits that represent some numbers around k, like numbers k-3 to k+5, and then there should be some fixed number of operations to extract number k.

For example: Given n, pick t depending on n, so that $n^t$ is only slightly less than a power of two, say $n^t \< 2^m$. We then arrange the numbers $x\_0$ to $x\_{n-1}$ in groups of t numbers, $x\_{k \cdot t}$ to $x\_{k \cdot t + (t-1)}$. Interpret these t numbers as digits of a t-digit base-n number with a value less than $2^m$. Store the bits for each of these numbers consecutively.

Given j, we let $j = t \cdot k + r$. We take bits number j to j+m-1, interpret them as an integer, write that integer in base n, and take the j-th base n digit as the result.

---
Tags: data-structures, data-compression, permutations
---