# Question
Title: Who converts binary/machine code to electrical signals and how?
I went through lots of blogs and posts but could not exactly figure out how the machine code is converted to electrical signals?

Any software program is compiled to machine code which is nothing but lots of 1s and 0s. 1 means high voltage e.g 5V and 0 means comparatively low voltage e.g. 0V or ground, what's the component which understands that okay I got 1(one) so I need to step up up the voltage to 5V and for 0(zero) I need to step down to lower voltage level and how it does that?

# Answer
In old computer you actually had a row of switches on the front panel that would allow entering 1s and 0s directly by hand in the registers of the machines. But this is no longer done.

You never have 1s and 0s, unless you ask the machine to print its internal information as a sequence of 1s and 0s. All information is already in the machine encoded as voltage, or magnetic orientation, or hole in a physical substrate, or some other physical form. Various devices can perform the translation between these form: magnetic heads, laser beams, electro-mechanical devices, electronic circuits,etc.

Some form are better adapted at memorizing or transmission by various means, while other (electrical signal notably) are better adapted at processing, usually by complex systems of logical gates (and, or, not, xor ...) and micro-memories (registers).

In general, binary/machine code is no longer entered by human beings, but produced by a program (usually a compiler) by the computer itself, or by another computer and then imported on some memory support or by network. However, human beings can ask to have it printed as 1s and 0s to check what the computer is using or producing. However this requires transforming the single bit 0 or 1 in the computer as a stream of bits to be interpreted by the printer as a request to print an actual drawing (on screen or paper) od the symbol representing a 0 or a 1.

It is hard to give more details without your being more specific regarding the source form and target form of the conversion. But it is most often from binary to binary, with a different physical representation.
> 6 votes

# Answer
The question is asking there must be something between the machine code and the electric signal in the computer. For example, a program written in C++ is compiled into machine code first, then it is converted into electrical signal so that the computer can really "execute" the program. As the computer does not understand the machine code, what is the component really change machine code to electronic signal?

Some answers mentioned the input process from keyboard, but that does not really answer the question. I think if anybody who can explain step by step the execution process of an .exe file on a Windows computer will be able to provide more valuable details.
> 4 votes

# Answer
**The CPU**

What is important to understand is that the CPU comes with a predefined instruction set that it can handle. For example, x86-64 CPUs have a defined set of instructions that they can operate on.

The CPU has a data bus and an address bus. The buses are only pins under the processor and they are connected to metallic lines that are directed towards the pins of the DIMM (Dual Inline Memory Module) or RAM which contains DRAM chips.

The CPU pins (under the CPU) are detailed here https://www.intel.com.br/content/dam/doc/datasheet/core-i5-600-i3-500-pentium-6000-datasheet-vol-1.pdf in the last chapter. Below is an image which shows the upper-left quadrant.

In the upper-left quadrant, you have some SA\_DQ pins which are the DDR3 data pins. These pins will be connected by the data bus to the data pins of the RAM memory module's pins. You have something similar for the address pins.

On the address pins is placed an address (0 or 1 on each line). This address will be decoded by the DIMM which will open a path to the DRAM memory cells containing the content at that address. A DRAM memory cell looks like below.

The DRAM cell consists of one transistor controlling the flow of charge and one capacitor containing the charge. Each DRAM cell is one bit of information. You could think of it as if the charge would flow from the capacitor to the CPU register and then the CPU would do operations on the register and then charge back some other capacitors. In reality, it is a bit more complex but you get the point.

For example, you could have the Intel syntax assembly instruction

```
mov rax, [0x1234]

```

This instruction will have an encoding in binary (stored as an array of charged/not charged capacitors). When the CPU fetches that instruction, it will place the address of the instruction on the address bus and expect RAM to answer with the instruction on the data bus. Then the CPU will decode the instruction. It will do basic operations on it to determine what it asks. Since the instruction tells the CPU to place the content of address 0x1234 in RAX then the CPU will place that address on the address bus and wait for RAM to answer with the content of that address. It will then charge/discharge the SRAM (Static RAM) cells of the register to now hold the new data. Static RAM is faster and more reliable then DRAM (Dynamic RAM). It uses six transistors instead of one and no capacitor. Registers are made of it (every bit of the register is one SRAM cell).

To understand better how the computer works, you should look at booting because a lot happens there.

**Booting**

CPUs have reset pins. The reset pins are used by the BIOS to initialize the CPU when you start the computer. The CPU is manufactured to put a certain address in its RIP register when you reset it (the reset vector). The RIP register is the instruction pointer. It contains the address of the next instruction to be fetched, decoded and executed. The CPU will thus execute its first instruction at the reset vector. It is the job of the motherboard to make sure that, at this address, is hardwired the BIOS's first instruction. The BIOS will thus be executed as the first program (software) of the computer. It will start sending instructions to the CPU and tell it to write some stuff in RAM like the ACPI tables.

The ACPI tables are located in predefined conventional locations in RAM that the OS will look for. The OS will then interpret these tables to determine what is plugged in the computer. Like what PCI slots there is, what USB controller and what IOAPIC.

Today most computers boot with UEFI. The BIOS will initialize everything and then jmp to the first instruction of the UEFI program. The UEFI program will set up long mode and paging then execute a UEFI app in a predefined directory on a FAT32 partition. The hardware/firmware manufacturer provides the UEFI program while the OS/software manufacturer provides the UEFI app that the UEFI program will launch. The hard-disk needs to be partitioned with GPT so that the UEFI program embedded in the motherboard can interpret the partitions and jmp to a UEFI app in a certain directory. The OS manufacturers often provide an ISO file which is basically an image of the hard-disk byte by byte. When you burn an ISO to disk, you simply use software to write that ISO byte by byte to the disk as an exact copy.

**USB**

I think that to understand computers better, you should look at how USB works because most of what happens comes from there (keyboard/mouse). Today, USB is controlled by an Intel's xHCI (https://www.intel.com/content/dam/www/public/us/en/documents/technical-specifications/extensible-host-controler-interface-usb-xhci.pdf). The xHCI is responsible to trigger interrupts when an event happens like when you press a keyboard key. At the hardware level, one (or some) pin of the xHCI is hardwired to the IOAPIC(s) of the processor. The IOAPIC is responsible to trigger an interrupt at the local APIC of one specific CPU core. The IOAPIC can be programmed to trigger certain local APICs depending on where the interrupt happened (what interrupt pin). The OS will determine what pin of the IOAPIC is connected to what by looking at the ACPI tables in RAM at boot. For example, it may find that the xHCI controller is connected to pin 12 of the IOAPIC. It will thus program that pin to fire a certain interrupt number in a specific local APIC.

The CPU has an IDT (interrupt descriptor table). The IDT is a table present in RAM which indicates some information to the processor on what to do with what interrupt number. For example, if the xHCI on pin 12 triggers an interrupt, the OS could decide to map it to interrupt number 10. The processor will thus look in its LIDT register, which stores the physical address of the IDT in RAM, and will jump to the handler of interrupt 10. The handler of interrupt 10 will do something depending on what was connected to this USB plug which has been determined at boot by querying this information from the xHCI.

For a keyboard keypress in hardware, the steps are the following:

1. The keyboard key is pressed.
2. The 5 volts provided by the USB port to the keyboard is used as the voltage to trigger a pin on the xHCI.
3. The xHCI then triggers a pin on the IOAPIC to interrupt the CPU.
4. The CPU looks in its LIDT register for the address of the IDT.
5. It fetches the information of the IDT from RAM (or from its cache most probably).
6. It jumps to the handler of the interrupt number that was programmed by the OS for that interrupt pin.
7. The handler uses a GetReport request to the HID USB device (https://wiki.osdev.org/USB\_Human\_Interface\_Devices) to gather the info on what happened.
8. The HID device responds with a serial packet containing the information.
9. The OS interprets that info and sends to the application, which currently has focus, a message stating that a key was pressed. For example, on Windows 10, every application running is polling a message queue in a loop. When a message arrives (in the form of an int or a macro in C/C++), the message is switched for several messages until the right message is found and then handled by the application. The minimal Windows 10 window application looks like below (in C++).

```
#include <windows.h>

LRESULT CALLBACK WindowProc(HWND hwnd, UINT uMsg, WPARAM wParam, LPARAM lParam){
    switch (uMsg)
    {
    case WM_DESTROY: //The user closed the application
        PostQuitMessage(0);
        return 0;

    case WM_PAINT: //Message sent when the window is painted at app launch
        {
            PAINTSTRUCT ps;
            HDC hdc = BeginPaint(hwnd, &ps);

            FillRect(hdc, &ps.rcPaint, (HBRUSH) (COLOR_WINDOW+1));

            EndPaint(hwnd, &ps);
        }
        return 0;
    }
    return DefWindowProc(hwnd, uMsg, wParam, lParam);
}

int WINAPI wWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, PWSTR pCmdLine, int nCmdShow){
    // Register the window class.
    const wchar_t CLASS_NAME[]  = L"Window";
    WNDCLASS wc = { };
    wc.lpfnWndProc   = WindowProc;
    wc.hInstance     = hInstance;
    wc.lpszClassName = CLASS_NAME;
    RegisterClass(&wc);

    // Create the window.
    HWND hwnd = CreateWindowEx(0, CLASS_NAME, L"Window", WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, CW_USEDEFAULT, CW_USEDEFAULT, CW_USEDEFAULT, NULL, NULL, hInstance, NULL);
    ShowWindow(hwnd, nCmdShow);

    // Run the message loop.
    MSG msg = { };
    while (GetMessage(&msg, NULL, 0, 0))
    {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }
    return 0;
}

```

Every application in any language will be translated to something similar after being compiled. It doesn't matter if it is C# or C++ it will use the same API provided by Microsoft to create the window and show controls like buttons. As you can see the application goes into an infinite loop until GetMessage() returns a certain value which tells the app to close (when you close the app). In the meantime, it is receiving messages probably from the USB keyboard/mouse that the interrupt handler will translate to a message and then place the message at the end of the message queue of the application which currently has focus. Even a console application is a window application. The window is the console and your application is just running in a background thread of the console application which itself has a message queue.

**Screen**

Where you get things wrong I think is when you look at an abstract screen and think it is all magical. In the end, it's the other way around. From boot time to shutdown of the computer, everything is just electrical signals in the computer. The screen is just a representation of what is happening in the computer that software/OS developers determined.

At the hardware level, the screen is often controlled today by a graphics card. Even one which is embedded in the CPU. The graphics card can be accessed using the PCI bus and certain memory mapped registers. Memory mapped registers are hardwired to pins on the graphics card. When you set the address bus to the addresses of memory mapped IO (MMIO), what you output on the data pins (data bus) will be written to the graphics card registers. This way, you can send commands to the different hardware or read data from the hardware connected to PCI. It works the same way for the IOAPIC and the xHCI USB controller.

Using these registers, you can set the address of the framebuffer (Video RAM). The graphics card often has memory within itself to store video data. It is pretty complex and often graphics cards are provided along with their drivers. For example, NVIDIA graphics cards are closed source and there have been attempts to support them on Linux with the Nouveau driver which have been a complete failure. In the end, NVIDIA provided graphics card drivers for Ubuntu Linux and maybe some other distributions (since a driver for Linux should work on Linux). I don't know about the specifics.

The framebuffer will be read at certain rates by the graphics card and the screen refreshed. VGA works similarly but outside the PCI bus. It has separate controllers which is even emulated with today's more recent hardware. The framebuffer works by writing to some addresses in RAM, but writes the data to Video RAM instead which is separate memory.

**Compilation**

When you write a program in C/C++ (high level languages). You use a lot of abstract human/machine interfaces like the screen, keyboard and mouse. What you write is simply encoded as ASCII/UTF-8 in the machine at all time and stored in a text file. A .c/.cpp file is just a text file with a different extension. The .c/.cpp file will be iterated by the compiler and translated to machine code following the convention that the CPU provides for instruction encoding. It will then be placed in a file with a certain extension and a certain conventional format. For example, on Windows 10 the .exe files are executables. These executables store the virtual addresses at which the code should be placed in memory so that the different execution paths reference each other properly. By execution paths I mean the different functions, ifs, loops etc. In assembly it takes the form of relative jmps to certain virtual addresses. For example, you could have the main function executed at first from virtual address 0x401000. Then the foo() function will be placed at virtual address 0x400000. When you call that function, the CPU will execute something like `jmp 0x400000` but it will be relative to the current position in the code (a short jump). In reality it will be more like `jmp -0x1000` as depicted in the bochs emulator. Again assembly is just an abstract representation of machine code which has a more direct relationship to it than C/C++. What I mean by that is that you can easily go from assembly to machine code while compiling C/C++ to machine code takes more steps.

Launching an executable on Windows has many steps which could look like the following in hardware:

1. The user presses a mouse button while having the file explorer opened and with the mouse on the executable's icon.
2. The xHCI receives an electrical signal and triggers its interrupt line to the IOAPIC.
3. The IOAPIC fires a certain interrupt number to the local APIC it was programmed to.
4. The local APIC checks the IDT for the address of the handler for that interrupt number.
5. The local APIC changes the RIP register to that address which makes the CPU jump to the handler.
6. The CPU keeps doing its fetch, decode and execute cycle as usual and executes the handler.
7. The handler will send a message to the message queue of the file explorer.
8. The file explorer will eventually handle that message which will prompt it to determine what what pressed (what file).
9. The file explorer will then launch that application using system calls. The kernel will load some parts of that file (or the whole file) to RAM. The kernel will use IO port registers of the DMA controller. The DMA controller will load the data from disk placing the data in RAM. Once done, the hardware (hard-disk) will fire an interrupt.
10. The OS will then know it's time to launch that application. The OS will interpret the .exe file which is now in RAM and set up the page tables and other structures for the new process taking place.
11. The OS will put that application in its processes queue and eventually, will make the CPU jump to the first instruction of that process.
12. The CPU will then be executing the new process instruction by instruction.
> 4 votes

# Answer
You don't "convert" a zero to low voltage: a zero *is* low voltage. Whenever a logic component is at low voltage, we call that state "zero". Likewise, when a component is at high voltage, we call that state "one". Zeroes and ones exist *only* as voltage levels.
> 2 votes

# Answer
There is nothing to convert, the moment you press a key your keyboard sends a signal containing the information about the pressed key (imagine a switch being turned on for the duration of the keypress, this is interpreted by a microchip), this information is already voltage and the cpu or other components work with that. So the only points where such a conversion is necessary are IO devices, if the device in question sends analog data this would be done by an AD Converter.

Maybe you are reffering to the state transion 1-\>0 or 0-\>1 itself ? Well, at the lowest level this is done with transistors, for example in NMOS logic you could build a NOR gate like this:

see NMOS, CMOS, MOSFET if you want to know more about it.
> 1 votes

# Answer
Your machine code is not "converted" into electrical signals at all. It is a set of electrical signals. The fact that you see numbers and letters on your screen is irrelevant, all of that data is simply the processing of very precisely arranged electrical signals under a strict set of rules.

See this answer on SuperUser for a more detailed answer
> 1 votes

# Answer
The text / code you are looking at on your display right now is a view of the underlying voltages residing on Memory ; therefore, if it’s not a voltage on memory, it’s never on screen.

Text/code is a view of voltages

To compile source code means cover underlying voltages to different voltages and view the resulted voltages as compiled code/text
> 1 votes

# Answer
I’m afraid you are looking at things from the wrong level. There’s a highest level that we usually look at here: Algorithm design. Next level: High level programming languages. Below that: Assembly languages and machine code. Below: Processors. Below that: Logic design. Building things from and/or/nand gates. Out Next level: Transistors. And that’s where actual electricity comes in; voltages, currents, capacitors etc.

Very few people know and very few people care about details as low as this.
> 1 votes

# Answer
Every thing you write on a text editor, first, it is stored in a memory (electric signals generated from the keybord) no matter in which code (ascii,...). From memory, those signals are fed into the computer monitor and you can see the source code you are typing. Then, you run your compiler (or assembler) that reads the source code in memory (electric signals) and converts it to machine code, storing those transformed electric signals in another region of the memory (electric signals again). When the cpu reads the machine code, what it sees are electric signals. There is no logic levels, so there is no need to convert logic level in voltage level.
> -1 votes

# Answer
Actually voltage signals work with themselves in voltage layer(involve cpu,memory,input,output,...) ,and we can see the meaning of voltages signals in binary codes or c code or other language at pc monitor.
> -1 votes

# Answer
Basically, it is the data bus between the processor and the RAM that does this conversion from logic state to real voltage that can be measured with an instrument like a scope and logic analyzer. Modern computers are difficult to design and verify because the frequency is so high, the voltages decreased to lower values such as 3.3 volt or 1.8 volt. Furthermore, the cache memory inside modern processors prevent to probe the data bus after the first reading. But there is no magic trick. Every features are clearly described by each processor companies. There is option to disable the cache, forcing the CPU to access the RAM chip every time data is needed. This is very useful for hardware diagnostic. It could also resolve complex multi core cache corruption problem.
> -1 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Fast algorithm for interpolating data from polar coordinates to cartesian coordinates
I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid:

That is, using the image above, for each node in the Cartesian grid I would interpolate a value from the closest existing nodes (red).

Currently, my approach is to generate a kd-tree for the original solution nodes, then use a nearest-neighbor search to obtain the three closest nodes. I then use barycentric interpolation to obtain a value from these three points. The problem, however, is that my polar grid is much finer along the radial direction than it is in the azimuthal direction, which means that my nearest-neighbor search almost always selects points from the same radial. This has the result of creating "striations" in my new solution, instead of smoothly interpolating along the azimuthal direction (i.e., the results look no different than if I had simply mapped the nearest point to the "interpolated" point).

Unfortunately, I don't know how to achieve a better sampling without sacrificing the kd-tree and losing a lot of the speed improvements. Am I being thick-headed and missing an obvious solution? Or does anyone know a better way to approach this problem?

# Answer
> 2 votes
I don't know if this has been studied by others. Speculating off the top of my head, let me outline two possible approaches.

## Applying standard rectangular methods to polar coordinates

Here's one way to adapt more familiar interpolation methods (that work with Cartesian coordinates) to your setting. Let's start by looking at bilinear interpolation.

Let $P$ be the point on the Cartesian grid whose value you want to compute, using interpolation. Find the smallest "rectangle" of four nodes that surround the point $P$. A "rectangle" in polar coordinates is just like a rectangle in a Cartesian grid, except with up/down replaced with "inward"/"outward" and right/right replaced with "clockwise"/"counterclockwise". For instance, here is an example of a "rectangle" in a polar-coordinate grid:

This gives you 4 nodes that surround $P$. Finally, use these 4 nodes to interpolate and form the value for $P$. For instance, you could do bilinear interpolation, in the same way we do bilinear interpolation on a Cartesian grid, but now working with polar coordinates / barycentric coordinates.

This also makes clear how to generalize to other interpolation schemes, such as bicubic interpolation.

## Ad-hoc method: supplement from adjacent radials

One possible approach you could try would be to pick the 3 closest nodes, then supplement them with a few other nodes from adjacent radials.

Let $P$ be your point. Start by picking the closest 3 nodes to $P$ (say). Then, supplement them. For instance, suppose all 3 nodes are on the radial $\theta$. Look at the radial just to the left of it, $\theta-\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$. Similarly, look at the radial just to the right of it, $\theta+\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$.

Now use those points to interpolate. You might use weighted least-squares regression to fit a linear (or bilinear/bicubic/etc.) model, where the nodes that are closer to $P$ receive a higher weight. If you experiment a bit with the number of points chosen, the type of model, and the weights, you might find a scheme that reduces the "striation" artifacts.

Maybe better schemes are known; I don't know. I'm not expert in this area.

# Answer
> 2 votes
I had the same problem when I was trying to simulate the Projection-Slice-Theorem.

A quick solution is to use generalized bivariate interpolations, e.g. from random sample points to rectangular grid (not specific to your problem , but will work, example in python here https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.griddata.html#scipy.interpolate.griddata.

For my problem which involved taking an FFT of a function sampled in cylindrical (rather polar) coordinates to transform to a Cartesian xy grid, there is a very efficient solution published by Averbuch, Donoho, Coifman and Elad in 2006: "Fast and Accurate Polar Fourier Transform". (https://elad.cs.technion.ac.il/software/ scroll down to Polar-FFT to get both paper and free code in Matlab).

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


# Question
Title: recurrence relation for this n queen problem algorithm . and the time complexity
I am not able to understand how to write a recurrence relation for this n queen problem algorithm down below. Recurrence relation is for n\*n board and the time complexity

```
Algorithm : nQueen(B) for the n queens problem
Input : 2-dimensional array B[]

Output: All solutions B[] satisfying the condition for the eight queens problem

1 for i ← 1, 2,..., n do
2      for j ← 1, 2,..., n do
3            B[i, j] ← 0 ; /* Initialize the board */
4      end
5 end

6 for i ← 1, 2,..., n do
7     B[i, 1] ← 1 ; /* Put the first queen at B(1, j) */
8     QueenSub(B, 2) ; /* Proceed to the second column */
9     B[i, 1] ← 0 ; /* Remove the first queen from B(1, j) */
10 end

Algorithm : Subroutine QueenSub(B,J)

Input : 2-dimensional array B[], the number i of column
 Output: Each B[] that satisfies the conditions of the eight queens problem

1   for I ← 1, 2,..., N do
2       c ← 0 ; /* The number of threatening queens */
3     for k = 1,...,J − 1 do
4        if i − (j − k) > 0 then /* Queens on the left upper diagonal? */
5            c ← c + B[ i − (j − k),k];
6        end
7        c ← c + B[i,k] ; /* Queens on the left of B(i, j)? */
8        if i + (j − k)) < 9 then /* Queens on the left lower diagonal? */
9           c ← c + B[i + (j − k), k];
10        end
11     end
12     if c = 0 then /* No queen threatening here */
13           B[i, j] ← 1 ; /* Put a queen at B(i, j) */
14           if i = n then /* The last column? */
15              output B[] ; /* This is a solution */
16           else
17             QueenSub(B,j + 1) ; /* Proceed to the next column */
18            end
19            B[i, j] ← 0 ; /* Remove the queen from B(i, j) */
20       end
21   end

```

:

# Answer
> 0 votes
Your algorithm basically does this:

```
for all positions in row 1
  for all positions in row 2 without conflict with row 1
    for all positions in row 3 without conflict with rows 1-2
      for all positions in row 4 without conflict with rows 1-3

```

etc. The time complexity is difficult, because it depends on the actual number of conflicts which is hard to estimate. An upper bound is O (n!), a lower bound is n(n-3)(n-6)(n-9) ... = (n/3)! * 3^(n/3), because each row can only produce 3 conflicts.

Your test whether a position is conflict free takes O(n) steps, which isn't necessary, so the time complexity is (number of conflict free positions) * n.

You have conflicts because of queens moving straight up, diagonally to the left, and diagonally to the right. Maintain three bit masks for the straight up lines, left diagonals, and right diagonals hitting row i. These bit masks are empty for the first row. Conflict free positions are those in none of the three masks. If you decide to put a queen into position j in row i, set bit #j in each mask, then shift the "left diagonal" mask one position to the left, and shift the "right diagonal mask" one position to the right. This saves a factor O(n) and should give a very small constant factor.

The time complexity of finding or counting all solutions seems to grow extremely fast. The time complexity of finding *one* solution seems to grow a lot slower, but still fast.

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


# Question
Title: Structural parametrization for weighted vertex cover
Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that **VWVC** ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(2^\ell n^c)$ time, where $n$ is the number of vertices and $c$ is a constant.

I tried to approach this by finding a tree and find VWVC there with polynomial time and then brute forcing the rest $\ell$ edges in $O(2^{\ell})$, unfortunately i found a counterexample very quickly. Also I attempted to somehow assign all edges a weight (maybe for $uv\in E$ set $w(uv)=w(u)+w(v)$) and compute the minimal spanning tree and do something with that but I couldn't show that this would yield optimal vertex cover either. I'm kinda lost. Any hints appreciated.

# Answer
Find the set $L$ containing the $\ell$ extra edges (actually, find any set $L$ of $\ell$ edges such that $G-L$ is a tree).

Let $C$ be an optimal solution. For each edge $(u,v)$ in $L$, guess whether $u \in C$. If you guess "yes", add $u$ to a set $X$, otherwise add $v$ to $X$. (Notice that it is possible for both $u$ and $v$ to be in $C$, but we do not need to explicitly consider this case).

Overall, there are at most $2^\ell$ distinct choices for the $\ell$ guesses. At least one set $X^\*$ among the guessed sets $X$ is a subset of $C$.

Given $X^\*$ you can find the minimum weighted vertex cover in poylnomial-time by considering $F=G-X^\*$. Since all the edges in $L$ have an endpoint in $X^\*$, $F$ is a forest. Then you can find a minimum weighted vertex cover $C\_i$ for each tree $T\_i$ in $F$. The set $\cup\_i C\_i$ is a minimum weighted vertex cover for $F$, and $X^\* \cup (\cup\_i C\_i)$ is the sought solution.

You could also directly find a minimum weighted vertex cover for $G-L$ with the constraints that the vertices in $X^\*$ are forced to be in the cover. This can be done, e.g., with a straightforward modification of the dynamic programming algorithm for trees. Another option is setting the weights of the vertices in $X^\*$ to $0$ (or to $\sum\_{v \in V}$) making them essentially "free" to select.

Since you don't actually know $X^\*$ you can run the above procedure on each guess $X$ and then select the cover of minimum weight.
> 1 votes

---
Tags: algorithms, graphs, parameterized-complexity, vertex-cover
---


title: What's beautiful in CS?

text:
# Question
Title: What's beautiful in CS?
I'm afraid this may be opinion-based and not apt here, but...

Mathematicians often talk about "mathematical beauty", i.e. Gauss' proof of the Fundamental Theorem of Algebra, Euler's Formula, etc.

What's beautiful in Computer Science? Things like the Church-Turing thesis or Curry-Howard correspondence are cool, but I'm not sure they are the same kind of "beauty" as mathematicians commonly prescribe.

Is it because CS is often an engineering field (despite its theories), and doesn't share the same notion of "beauty"?

# Answer
As others have said, this is very opinion based. What's the difference between "cool" and "beautiful"? I find the Curry-Howard isomorphism beautiful, you don't. Neither of us is wrong.

Ultimately, Computer Science is a science of compromise. Mathematics is concerned with what "is": logical facts, pure truth and knowledge. Computer Science is concerned with what can be computed, and thanks to undecidability, that's really not that much. There are uncountably many undecidable sets, but only countably many decidable ones.

So the mathematicians get to write beautiful pictures and draw beautiful diagrams about what is, in the abstract. And the computer scientists get to find the heuristics, the edge cases, the conservative approximations, and the impossibility results. In some sense, ours is a science of ugliness.

That said, everyone will find something beautiful in their field. In mine (Programming Languages), there's a whole category of paper called "Pearl" papers, where the design of something complex is made particularly simple or elegant by the programming language or technique used to create it. If you google "ICFP Functional Pearl" or "JFP Functional Pearl" you'll find a ton.
> 1 votes

---
Tags: theory
---


# Question
Title: Which of the following words is in the language of the grammar G?
This is taken from a practice quiz by my university.

I ruled out that aabbbaab is not part of the grammar:

S → aSb → aaSbb... This shows that I can't make this word because it would have to have atleast two b's at the end in order for me to add more letters

Then I tried to see if abbaabb can be derived from the grammar and I experienced the same thing:

S → aSb → aaSbb... This shows that I can't make a word with two b's at the end without having at least two a's in the beginning

Finally, I tried to do aabaabbb:

S → aSb → aaSbb → aaSSbb → aaSaSbbb... I decided it can't be this one because even if I make aaSa**S**bbb into ϵ, I still need to find a way to make aa**S**aSbbb into ba so I can derive the word. It doesn't seem like I can do that.

So by elimination I thought the correct answer was aabaabb but I was wrong.

Please show me how to work out whether a word can be derived from a grammar.

# Answer
This is what we have at our hand.

Now let us see what can be get from the second production in red.

From the production in Blue we have

And the parsing can be stopped using $S\rightarrow \epsilon$

So from the above two work outs we find that the $a$'s and $b$'s are properly nested. (and can be mapped to the problem of valid parenthesization )

That being said let us work the options out:

Alternatively, during the examination, it is hard to get this detailed thought in mind, so one can try to draw the parse tree for any one of the words, trying to do so, you shall get the intuition of the semantics of the language of the grammar.
> 2 votes

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


# Question
Title: what is the relationship between entropy and variance?
Consider a simple Bernoulli variable X

```
X = 1 with probability p
X = 0 with probability (1-p)

```

The variance is simply `p(1-p)`. The entropy is `-p*ln(p)-(1-p)*ln(1-p)` Both are measures of uncertainty. What is the advantage of entropy then?

Thanks!

# Answer
> 2 votes
They measure different things. Given the variance, you can solve for $p$ and compute the entropy, and vice versa, but they have different interpretations and different applications. You can learn a bit about the meaning and applications of these notions in the corresponding Wikipedia articles: https://en.wikipedia.org/wiki/Entropy\_(information\_theory), https://en.wikipedia.org/wiki/Variance.

Analogy: if we have a sphere, I could measure its radius, or I could measure its volume. They both reflect the size of the sphere, so you could as, what is the advantage of radius, or of volume? Answer: they measure different things, so depending on what you want to do, one or the other might be more useful.

---
Tags: probability-theory, information-theory
---


# Question
Title: What is the difference between a state machine and a database
I didn't study computer science as a degree, so whilst having studied computer science, there are still gaps in my knowledge. Everything I read about 'state' sounds like some form of 'data' but kept in memory as opposed to a database. This keeps leading me to the question: is a state machine not just a way of storing data, like a database.

There is probably a very obvious answer to this, but I can't seem to find anything about it when searching Google, which leads me to think I'm way off in my understanding somewhere. Any pointers (not the memory type) into some good reading would be super helpful. Thanks!

# Answer
> 3 votes
State machines and databases are quite different entities, and their usage (or *functionality*) is very different. In this answer, I'll just try to separate them with respect to the similarity you mention. This is by no means a comprehensive description of neither state machines nor databases.

The states of a state machine can indeed be thought of as representing data (although this is not always obvious, and sometimes state machines do not reveal what data they store in their states). However, the crucial element of a state machine is the *transitions* between the states, which represent the behaviour of the machine.

That is, a state machine *does* something. It *computes*. During its run (or runs, in nondeterministic models), it moves from state to state according to some predetermined set of rules, and possibly according to a given input, and this process is called a computation. At the end of the computation (if it's finite), you might receive an output, from which you can derive some information.

For example, a Turing machine receives an input and if it halts, tells you whether the input is accepted or rejected, from which you can formalize a decision problem. Similarly, an automaton does the same, but without external memory.

In contrast, a database merely stores data. How this storage is done, which operations are allowed on the data, and what their respective complexity is, are all interesting questions, and their answers depend on the type of database you use. However, databases do not *compute* anything by themselves, they just store the data, possibly efficiently.

---
Tags: data-structures, memory-management, databases
---


# Question
Title: Can someone tell a formal definition for this problem: k-disjoint triangle?
k-disjoint triangle "We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. "

The above definition is the best I could find online. Nowhere could I find an clear formal definition.

1. What does it mean to be vertex disjoint exactly?
2. How to prove k-disjoint vertex is NP hard?

# Answer
> 2 votes
Let's consider the case in which $H$ is a triangle; the general case is very similar.

A *triangle* in a graph $G$ is a set $\\{x,y,z\\}$ of three vertices of $G$ such that $G$ contains the edges $\\{x,y\\},\\{y,z\\},\\{z,x\\}$. Two triangles $T\_1,T\_2$ are *(vertext) disjoint* if they do not share a vertex: $T\_1 \cap T\_2 = \varnothing$. A graph contains $k$ disjoint triangles if it contains $k$ triangles $T\_1,\ldots,T\_k$ which are pairwise disjoint: $T\_i \cap T\_j = \varnothing$ for all $i \neq j$.

Your quote is taken from the paper Exact algorithms for finding $k$ disjoint triangles in an arbitrary graph by Fellows, Heggernes, Rosamond, Sloper, and Telle. Here is the last sentence of the first paragraph:

> On the other hand, the $K\_3$-packing problem, which is our main concern in this paper, is NP-hard \[HK78\].

The $K\_3$-packing problem asks, given a graph $G$ and an integer $k$, whether $G$ contains $k$ disjoint triangles. The reference \[HK78\], which can be found in the bibliography of the paper, presumably contains a proof that this problem is NP-complete.

# Answer
> 2 votes
Finding $k$ disjoint triangles in a graph means that you color $3k$ vertices with $k$ colors, $\chi\_i, 1 \leq i \leq k$ such that for each color $\chi\_i$, the graph $G\[X\_i\] \simeq K\_3$, where $X\_i$ are the three vertices that received color $\chi\_i$.

It simply means that you cannot use the same vertex in two different triangles.

This type of problem is often referred to as $K\_3$-packing or triangle-packing: You want to "pack" as many triangles as possible in a graph $G$.

The problem is NP-complete even if you are given a tri-partition of the graph, and this problem is called 3-dimensional matching, one of Karp's 21 NP-complete problems.

---
Tags: data-structures, parameterized-complexity
---


# Question
Title: Maximum integer in a sorted list which also is in an unsorted list
If I have a sorted list $A=\[a\_1, \dots, a\_n\]$ such that the integers $a\_1\leq a\_2\leq\dots\leq a\_n$, and an unsorted list $B=\[b\_1, \dots, b\_k\]$, which includes at least one integer also in $A$, can I then find the maximum integer in $A$ which also is in $B$ in $O(k\log n)$ time? If so, how?

# Answer
Are you familiar with binary search? If not, look that up. It has complexity $O(\log n)$ and will find you the index $i$ where you would insert $x$ into $A$ to maintain sorted order. From this you can instantly see whether $x$ already exists in $A$ by checking whether $A\[i\] = x$.

Then, do this for $b\_1, b\_2, \dots$, checking for each whether it is in $A$ in $O(\log n)$ time, and if yes, whether it is bigger than the current best found.

You do this $k$ times to find the biggest element that is in both $A$ and $B$ in $O(k \log n)$ time.

---

You can even be a bit smarter, like such:

```
lo = 1
best = A[1] - 1
for b in B:
    if b > best:
        i = binary_search(A, lo, n, b)
        if A[i] == b:
            best = b
            lo = i + 1

```

This doesn't change the worst case complexity but will avoid needless binary searches, and make the bounds on the binary searches that you do tighter.
> 4 votes

---
Tags: algorithms, algorithm-analysis, minmax-algorithm
---


# Question
Title: How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?
I am interested in the asymptotic bounds of the following recurrence:

$$T(n)= T(n - 1) + \frac{1}{n\log n}$$

with base case $T(1) = 1$. I'm having trouble while solving this recurrence. It seems much more tricky than I initially thought.

I've tried out by iterative method and since $\log(n!) = n\log n$, I've got $\frac{1}{n\log n}$.

At this point, I've got that the summation of $\frac{1}{i}$ is equal to $\Theta(\log n + O(1))$. So at the end, I've come up with this bound (by simplifying the two terms): $\Theta(\frac{1}{n})$.

I'm not so sure about this bound. What is a good way to approach this problem?

# Answer
> 3 votes
We have $$ T(n) = \sum\_{m=3}^n \frac{1}{m\log m} + T(2). $$ We can bound $$ \int\_3^{n+1} \frac{dx}{x\log x} \leq \sum\_{m=3}^n \frac{1}{m\log m} \leq \int\_2^n \frac{dx}{x\log x}. $$ Since $(\log\log x)' = \frac{1}{x\log x}$, this shows that $$ \log\log(n+1) - \log\log 3 \leq \sum\_{m=3}^n \frac{1}{m\log m} \leq \log\log n - \log\log 2, $$ and so $T(n) = \log\log n + \Theta(1)$.

# Answer
> 1 votes
First, this isn’t a recursion, it’s just a straightforward sum, adding 1 / (j log j) for j = 2 to n, plus 1 added.

Remember how the sum of 1/j is about log (n)? You are adding something similar, but smaller. Find an upper and lower bound for the sum from 2 to 2, from 3 to 4, from 5 to 8, from 9 to 16, from 17 to 32 etc. and use that to get T(2^k), and then it is easy.

I’d bet the result is about log log n. Take the derivative: (log log n)’ = log’ (log n) * (log n)’ = (1 / log n) * (1 / n). Just right. Now T(n) - T(n-1) would usually be closer to f’(n-1/2), so I’d say T(n) ≈ c + log(log(n-1/2)), picking c so that the error is small for large n.

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


# Question
Title: Minimal Spanning Tree vs Minimum Spanning Tree
I got confused about minimal and minimum in context of graph theory. Although, I have understanding that minimal means more than one minimum i.e. none qualifies as actual minimum so we say them minimal.

What exactly does minimal spanning tree mean? Also, what exactly does 'minimal edge' mean?

How do they differ from minimum spanning tree? How are 'minimal edge' different from minimum edge?

This doubt arose due to the statement:

S: There exists a minimum weight edge in G, which exists in every minimum spanning tree of G.

Can we say on using word 'minimum' it's implied that there is only one minimum weight edge. Besides, statement used "exists" which is singular.

# Answer
> 1 votes
A *minimum weight edge* is an edge whose weight is minimal among all edges. There can be more than one minimum weight edge. All minimum weight edges have the same weight.

Similarly, a *minimum spanning tree* is a spanning tree whose weight is minimal among all spanning trees. There can be more than one minimum spanning tree. All minimum spanning trees have the same weight.

In some cases, there is a distinction between *minimum* and *minimal*. For example, a *minimum vertex cover* is a vertex cover whose weight is minimal among all vertex covers. In contrast, a *minimal vertex cover* is a vertex cover, any proper subset of which isn't a vertex cover. Finding a minimal vertex cover is easy – start with the set of all vertices, and repeatedly remove a vertex as long as it is possible to do so while maintaining the property of covering all edges. In contrast, finding a minimum vertex cover is expected to be hard (the corresponding decision problem is NP-hard).

The same property of being minimal doesn't make much sense for edges and spanning trees. When people say *minimal edge* or *minimal spanning tree*, they probably mean *minimum (weight) edge* and *minimum spanning tree*.

---
Tags: graphs, minimum-spanning-tree
---


title: Asymptotics of harmonic series

text:
# Question
Title: Asymptotics of harmonic series
> Show that $$ 1 + \frac{1}{2} + \cdots + \frac{1}{n} = \Theta(\ln n) $$

How do I solve this problem?

I tried to to integrate it but I got a weird answer.

# Answer
> 1 votes
Notice that $\frac{1}{i}$ is monotonically decreasing. Then:

$$ \sum\_{i=1}^n \frac{1}{i} = 1 + \sum\_{i=2}^n \frac{1}{i} \< 1 + \int\_{x=1}^n \frac{1}{x} \\,\mathsf{d}x = 1 + \left\[ \ln x \right\]\_{x=1}^n = 1+ \ln n \in O(\log n). $$

Moreover, $$ \sum\_{i=1}^n \frac{1}{i} \> \sum\_{i=1}^{n-1} \frac{1}{i} \> \int\_{x=1}^{n} \frac{1}{x} \\,\mathsf{d}x = \left\[ \ln x \right\]\_{x=1}^{n} = \ln(n) \in \Omega(\log n). $$

---
Tags: asymptotics
---


title: How is the NP verifier polynomial?

text:
# Question
Title: How is the NP verifier polynomial?
If we start with the definition of L being in NP if "there exists a polynomial NTM that decides L" (where polynomial for an NTM means the length of the worst run as a function of the size/length of the input / the maximal tree depth)

There is a proof that L is in NP iff there exists a polynomial TM verifier for L. Regarding the "L is in NP" -\> "there exists a polynomial TM verifier for L" side: Let N be that NTM I fail to understand how given (w, R) where R is the encoding for an accepting run of N on w, we can verify this in polynomial time **in regards to w** (as this is how the time complexity for a Verifier is defined)

We can show R's length is polynomial in w, but how would we verify that it is a valid run for N in polynomial time? We need to verify every 2 consecutive configurations in R are valid, but since for NTM's the transition function maps to a set of (Q x Gamma x {L,R}) possibilities - I can't figure out how this is possible.

Update:

Let me clarify a little further. An obviously bad (non polynomial) solution would be to have the verifier initially write the whole encoding on N on its tape, and then "search through it" to see if a transition is valid. But since the encoding of N is certainly not necessarily polynomial in N, this doesn't work.

It seems the answer has to rely on having the "inner workings" of N "embedded" in the verifier therefore avoiding time complexity issue as we are avoiding time complexity issues by having things "embedded" - but I fail to see how that could then be used further. I see how this opens an avenue of possibility, but can't see it through. I'm assuming there is some low-level technical grunt work so that the right transitions can be "embedded" straight into the verifier.

# Answer
You run your NTM, and at any point where it could decide between n \> 1 actions, it picks an action k and writes k to a tape.

Now you build a TM. It’s identical to the NTM, except at every point where the NTM made a decision, your TM reads a number k from the NTMs successful run, and takes action #k. That’s it.
> 1 votes

# Answer
> We need to verify every 2 consecutive configurations in R are valid, but since for NTM's the transition function maps to a set of (Q x Gamma x {L,R}) possibilities - I can't figure out how this is possible.

The size of the set of possibilities $Q \times \Gamma\times \\{L,R\\}$ is constant. By definition, a NTM has a *constant* size set of states $Q$, a *constant* size alphabet $\Gamma$, and the size of the set $\\{L,R\\}$ is $2$. Besides, to verify that a transition is valid we do not need to consider all possible transistions, we only need to check that the single given transition is valid.
> 0 votes

---
Tags: time-complexity, nondeterminism
---


title: How 'Avalanche Effect' got its name?

text:
# Question
Title: How 'Avalanche Effect' got its name?
I wonder how or why `Avalanche Effect` got its name.

> Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (for example, flipping a single bit), the output changes significantly (e.g., half the output bits flip). (source: Wikipedia)

But I feel like this definition has nothing to do with its name. If I asked what is avalanche/snowball effect, I would probably think of something which starts small but exponentially grow out of control.

# Answer
> 3 votes
The term first described by Horst Feistel (1973)

> As the input moves through successive layers the pattern of 1's generated is amplified and results in an unpredictable avalanche.

It is rather very good naming. Consider a bit flip in the AES's input; It enters the first Sbox, then according to the design of the Sboxes of AES the output is different since they are invertible (actually they are also designed to have avalanche effect). Now say we have at least two different output bits, then the Sub-Bytes and MixColums will distribute the changes. Therefore in the first round, you will have 2 changes, in the next round you will have 4,.. and so on. As you can see the minimum change becomes larger and larger in each round. That is how an avalanche is working.

Note that we have $2^{10}$ changes in the last round for AES-128. Contradictory, no, since some changes will cancel each other and that part together with the key's action is unpredictable for our computing capabilities!

The blow picture was drawn by Feistel, which should tell the idea; One small change at the beginning and it is a big effect on the output.

---
Tags: terminology, hash, cryptography, hash-tables
---


# Question
Title: Is it possible to build regex-based-map with search asymptotically faster then hashmap?
From time to time I stumble across a problem of matching hashmap keys to a regular expression. In such situations I am forced to loop through all of map's elements and try to match every single key to the regex. With regex compiled to DST it should have complexity class of O(n * m) where n is number of elements in map and m is the length of the longest key in the map. Assuming m is reasonably small, we can assume it is O(n).

Above solution to this problem, although it is reasonably good, makes me think every time - is it possible to construct a data structure that would be faster (at least in theory) in searching all the keys that match the given regex. Probably it would not be linearly dependent on the number of the keys in the data structure. Is it possible? If it is possible - what would be the main idea reducing complexity?

# Answer
> 1 votes
One possible approach is to store the keys in a trie, convert the regex to a DFA (remove all useless states from it and optionally minimize it), and then use that to search the trie.

In particular, you can construct a recursive algorithm for traversing the trie. The root of the trie is associated with the start state of the DFA. For each edge out of the root, you look at the letter on that edge, advance the DFA to the appropriate state, and associate that state with the corresponding child. If it causes the DFA to reject, then you can prune exploration of that node in the trie. In this way, each node in the trie gets associated with a state of the DFA, you recursively explore the trie, pruning when you hit dead ends, and if you hit a leaf in the trie, if the DFA is in an accept state at that point, you have found a match.

However the running time to convert a regex to a DFA can take exponential time. Also this only works with language-theoretic regular expressions, not Perl- or POSIX-style regexps, which are more expressive and cannot be converted to a DFA. So, whether this will be attractive might depend on your application.

---
Tags: data-structures, regular-expressions
---


title: Basic exercises on decision trees

text:
# Question
Title: Basic exercises on decision trees
I am a pure math person doing some ML self-study and I am pretty lost.

I am trying to solve the following exercises on decision trees:

> Exercise 1. Consider the following training set where $X\_1,X\_2,X\_3,X\_4$ are the attributes and $Y$ is the class variable. $$ \begin{matrix} Y & X\_1 & X\_2 & X\_3 & X\_4 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ -1& 0 & 0 & 1 & 1 \\ -1& 0 & 0 & 0 & 0 \\ -1& 0 & 0 & 1 & 0 \\ -1& 1 & 0 & 0 & 0 \\ -1& 0 & 0 & 1 & 1 \\ \end{matrix} $$
>
> * Learn a decision tree using the ID3 algorithm.
> * Draw a decision tree having only 4 leaf nodes, 3 internal nodes and depth bounded by 2, that has 100% accuracy on the given dataset.

> Exercise 2. Let $x$ be a vector of $n$ Boolean variables ${X\_1,...,X\_n}$ and let $k$ be an integer less than $n$. Let $f\_k$ be a target concept which is a disjunction consisting of $k$ literals. State the size of the smallest possible consistent decision tree (namely a decision tree that correctly classifies all possible examples) for $f\_k$ in terms of $n$ and $k$ and describe its shape.

Now, I've done the first part of Exersice 1 as follows: first I noticed that $X\_2$ is pure and so I chose it as root; then I used Information Gain to find the nodes. The second question confuses me: my understanding was that ID3 already gives the smallest tree, so how am I supposed to make it smaller? Or if am I wrong can anybody help me clarify?

For the second problem, I really don't know where to start from, so any hint would be appreciated.

# Answer
> 2 votes
ID3 is a heuristic. It is not guaranteed to generate an optimal decision tree.

Here is an algorithm for Exercise 1:

* If $X\_3 = 1$, then answer $2X\_1-1$.
* If $X\_3 = 0$, then answer $2X\_4-1$.

For Exercise 2, suppose $f\_k = X\_1 \lor \cdots \lor X\_k$. An optimal decision tree simulates the following algorithm:

* If $X\_1 = 1$, output 1, else continue.
* If $X\_2 = 1$, output 1, else continue.
* ...
* If $X\_k = 1$, output 1, else output 0.

Indeed, every decision tree for $f\_k$ must query all of $X\_1,\ldots,X\_k$ in the worst case.

---
Tags: machine-learning, decision-tree
---


# Question
Title: Can the intersection two non-recursive sets be recursive? Prove it
I am still really new to compsci theory and some of the topics are really hard to understand. For this Problem I would think that say we have two sets A and B and they are both non-recursive. If we take A ∩ B we would get the the matching inputs and since they are both from non-recursive sets wouldn't the intersection also be non-recursive? or am I thinking about this the wrong way. Any help appreciated Thanks

# Answer
> 2 votes
Let $L$ be a non-recursive set. Let $L\_0 = \\{0 \cdot x \mid x \in L\\}$ and $L\_1 = \\{1 \cdot x \mid x \in L\\}$. Both $L\_0$ and $L\_1$ are non-recursive, but $L\_0 \cap L\_1 = \emptyset$ is recursive.

# Answer
> 0 votes
Short answer: there are such languages.

Take some language $L\notin RE\cup co-RE$ (look at the explanation at the end for why such a language exists). Then both $L$ and $\bar L$ are not recursive, and are not even recursively enumerable. But, its obvious that $\emptyset=L\cap \bar L$ **is** a recursive set.

**Claim: there is some $L\notin RE\cup co-RE$.**

**Proof:** Why would such $L$ exist? We will compare the sizes of $RE\cup co-RE$ and the set of all languages.

$RE$ contains only $\aleph\_0$ languages, since each language has to be recognized by some turing machine, and turing machines we can ultimately be encoded in text. More formally, we know that for any $A\in RE$ we must have some turing machine $T$ that recognizes it, and $\langle T \rangle\in\\{0,1\\}^{\mathbb{N}}$. But $|\\{0,1\\}^\mathbb{N}|=\aleph\_0$, and thus $|RE|\le\\#\text{TM}\le|\\{0,1\\}^{\mathbb{N}}|=\aleph\_0$. A similar argument can be done to show that also $|co-RE|=\aleph\_0$ and combining the two, we get $|RE\cup co-RE| = \aleph\_0$

Now, notice that the set of all languages, is precisely $P(\\{0,1\\}^{\mathbb{N}})$, and thus it has $2^{\aleph\_0}$ elements in it. Since $2^{\aleph\_0}\>\aleph\_0$, there must be some $L\in P(\\{0,1\\}^{\mathbb{N}})$ such that $L\notin RE\cup co-RE$, and thus we proved the claim.

---
Tags: turing-machines, computability
---


# Question
Title: Can anyone explain how look-up tables are used for optimal Rubik's cube solvers such as Thistlethwaite's or Kociemba?
I have implemented Thistlethwaite's algorithm however, it is far too slow as it is only using graph traversal over many Rubik's cube states. I am currently unsure of how look-up tables are implemented so any help on how I could do so would be greatly appreciated.

# Answer
> 1 votes
In case it's still relevant, the idea is to get indices based on cube states and store the distance (number of moves it takes) to reach the next group from the given state.

For example - G0-\>G1 only looks at edge orientations. This means, that if you only consider the orientation of an edge at a given position, there are 2^11 possible states (2 ways each of the 11 edges can be oriented, because the orientation of the 12th edge is "forced" in place by the other 11 edges, so the orientation can be assumed).

For G0-\>G1, it's easy to generate these indices because you can assign each edge position to a bit in a 11-bit integer, and convert it to decimal.

For a state which satisfies G1, the index would be 0 (00000000000) and for a state with all edges oriented badly, the index would be 2047 (11111111111) which gives unique index for each state from 0 to 2047.

Using this logic, run your IDDFS from a solved cube only using the available moves of the group until all permutations were visited. for G0-\>G1 it should be done in 7 depths.

---
Tags: graph-traversal
---


# Question
Title: Are most metaheuristic algorithms different metaphors for the same method?
Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to better compare algorithms?

# Answer
> 2 votes
# Comparing ideas

If you want to compare the ideas involved on the various metaheuristics, a good starting point for the comparison is to think of them as **Population based vs Trajectory based**. Population based metaheuristics works with the concept of create a solution that mix components of good solutions. Trajectory based metaheuristics works with the concept of creating a solution and iteratively do improving modifications(moves) on it. With the image below, you can visualize this dichotomy and other possibles parameters for comparison.

# Comparing performance

To compare performance, a common approach is to use **time to target**. Given a known solution and its objective value, how fast my metaheuristic achieve this value? This site provides a tool that helps in this task.

# Answer
> 1 votes
The new metaheuristics are pretty much genetic algorithms and local search in disguise. And this is actually a problem and hinders progress. There is a good write-up on this topic by Sörensen, Kenneth. "Metaheuristics—the metaphor exposed." International Transactions in Operational Research 22, no. 1 (2015): 3-18.

The argument is that the "new" metaheuristics are not, in fact, new. They just reheat and repackage concepts, ideas, operators, subroutines from classical metaheuristics under a new name. While among all those repackaged ideas there is some "truly innovative research of high quality", it is hard to filter them out from all the noise, and hard to ascribe credibility to those new ideas.

Also have a look at The Evolutionary Computation Bestiary.

---
Tags: optimization, heuristics, genetic-algorithms
---


# Question
Title: What is the meaning of phenotype could be represented by a number of different genotype
I found this sentence in multiple sources but I didnt understand

in one thesis

> With a neutral representation each phenotype could be represented by a number of different genotype

and in another thesis

> it may be possible for neural networks with functionally equivalent topologies to be represented by a number of different genotypes

And in another source

> the genotypical representation: 010 001 100 0000 1100 0000 0000 0000 0011 0100 0000 0000 However, the graph (phenotype) can also be represented by a number of different genotypes. E.g:

> 010 001 100 **0110** 1100 0000 **0011** 0000 0011 0100 0000 0000

> 010 001 100 0000 1100 0000 0000 0000 0011 0100 **1110 0100**

Up to my understanding the first phenotype is the representation of the graph, so why the second or third phenotypes are different representations. how did we come up with the bold genotypes

# Answer
> 0 votes
The same function can be described in several ways.

If you're familiar with finite automata, then you should know that the same regular language ("phenotype") can be represented by many different finite automata ("genotype").

The same holds in many other cases, unless you choose an encoding which guarantees that every function has a unique description. It is not clear whether this is even desirable. For example, the genetic code has some redundancy which causes the same DNA sequence to encode the same proteins.

---
Tags: genetic-algorithms
---


# Question
Title: How to reconcile the different definitions of asynchrony?
There are 3 definitions of asynchrony that I know of:

* In **event-based programming**, asynchrony refers to the execution of tasks in a non-sequential way, which may involve creating another thread. For example with AJAX, we can perform HTTP requests and handle their response in a new thread so that the program doesn't block to wait for results.
* In **communication**, a channel is asynchronous if both parties don't need to be present at the same time (e.g., emails), and synchronous if they do (e.g., telephone).
* In **distributed systems**, an asynchronous model is one where messages may take an arbitrary long time to transit. It implies that there is no way to know for sure if a node has crashed or it/the network is just being slow.

However I struggle to reconcile these 3 definitions. Is there a common denominator that I'm missing, or is the term *asynchrony* used in 3 completely different contexts?

Thank you for your help.

# Answer
The unifying definition is that one part of the system triggers an event in another part of the system, and the triggerer does not know when the event will take place.

To put it another way: in a synchronous system, you know when things (will) happen. In an asynchronous system, you don't know when things (will) happen.

In event-based programming, a thread creates another thread, and then it has no control over when the thread will do its job. For example, with AJAX, the new theard performs an HTTP request, and the original thread continues executing without knowing when the HTTP response comes back.

In communication over an asynchronous channel, the sender of a message does not know or care when the recipient will be available receive the message.

In an asynchronous distributed system, the sender of a message does not know when (or possibly even whether) the recipient will receive the message and potentially reply to it.
> 1 votes

---
Tags: distributed-systems, computer-networks, synchronization
---


# Question
Title: What is the "formula" for "any cipher can be deciphered by a quantum computer"?
There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.

P=NP BPP=NP in simple words means "any cipher can be deciphered by a classical computer". (Do I understand it correctly?)

So, what is the "formula" for "any cipher can be deciphered by a quantum computer"?

# Answer
> 1 votes
In general, if NP turns out to be the subset of any tractable class then that will be a black swan event for those who depend on cryptography as it exists today. $NP \subseteq BQP$ is one such example. But it need not be a fatal blow to use of cryptography. Quantum computers with a large number of qubits have yet to be built, and it is unknown whether they can be. So increasing key lengths may well put tractable decryption out of reach of the machines that can be built. And of course the polynomial exponent might turn out to be large enough to make polynomial-time "efficient" decryption infeasible in practice. E.g. an $O(n^{13})$ algorithm for SAT, while a beautiful thing to behold, probably isn't going to break use of cryptography.

---
Tags: complexity-theory, time-complexity, complexity-classes, quantum-computing, encryption
---


# Question
Title: Prove no DFA with four states can accept L={111}
Assume we have a language L={111}. Prove no DFA with four states can accept L.

Can’t a DFA with 4 states accept L?

# Answer
> 3 votes
This depends on your favorite definition for DFAs. If your definition allows the transition function to be undefined on some state-symbol pairs $(q, a)$ then your DFA in your comment does the trick. Otherwise, you would need a fifth state (a sink) that is not accepting and catches all missing transitions.

To show that there is no DFA with less than five states accepting $L = \\{111\\}$, we can check the Myhill-Nerode equivalence classes of $L$ which are

* $\[\varepsilon\]\_L = \\{\varepsilon\\}$,
* $\[1\]\_L = \\{1\\}$,
* $\[11\]\_L = \\{11\\}$,
* $\[111\]\_L = \\{111\\}$,
* $\[0\]\_L = \\{w \in \\{0, 1\\}^\ast \mid w \notin \\{\varepsilon, 1, 11, 111\\}\\}$.

(To show that these are indeed the five classes is left as exercise.)

The equivalence classes have a 1:1 correspondence to the unique minimal DFA of the latter definition (with transitions for all state-symbol pairs).

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


# Question
Title: Regular expression for the language $\{wtw^r \mid w, t \in\{0 \cup 1\}^+\}$
What is a regular expression for the language $C=\\{wtw^r \mid w, t \in \\{0 \cup 1\\}^+\\}$? Here $w^r$ is the reverse of $w$.

# Answer
> 1 votes
Let $wtw^R \in C$. This word can also be written as $xyx$ where $x \in \\{0,1\\}$ and $y \in \\{0,1\\}^+$ (pick $x$ as the first character of $w$, pick $y$ as $wtw^R$ except for the first and last characters). Conversely, any word of the form $xyx$ with $x \in \\{0,1\\}$ and $y \in \\{0,1\\}^+$ belongs to $C$ (simply pick $w=w^R=x$ and $t=y$).

It follows that a regular expression for your language is $(0(0|1)^+0) \mid (1(0|1)^+1)$ or, equivalently, $(0(0|1)(0|1)^\*0) \mid (1(0|1)(0|1)^\*1)$.

---
Tags: automata, regular-expressions
---


# Question
Title: Prove correctness of in-order tree traversal subroutine
I'm trying to prove that in-order tree traversal prints the keys in sorted order. It's shown here, but what I want is to prove correctness using ordinary induction.

> Claim: For any n-node subtree, the in-order-tree-walk subroutine prints the keys of the subtree rooted at node x in sorted order.

```
in-order-tree-walk(x)
  if(x!=NIL)
    in-order-tree-walk(x.left)
    print x.key
    in-order-tree-walk(x.right)

```

Above pseudo-code is taken from CLRS, and we're traversing the subtree rooted at node x.

> Proof.
> By ordinary induction. Let our induction hypothesis $P(n)$ be the claim itself. We need show $P(n)$ holds for all positive integers.
> Base case ($n=1$):
> In-order-tree-walk subroutine prints the single node's key and, since the both *left* and *right* pointers are *NIL*, terminates. Trivially, single key is already in sorted order.
> Inductive step:
> Suppose $P(n)$ holds for some $n \geq 1$. Prove $P(n+1)$. Let $T$ be subtree consisting of $n+1$ nodes. Let $T'$ be subtree formed by removing the largest element from $T$. $T'$ has $n$ elements. By induction hypothesis $P(n)$, *in-order-tree-walk(T')* prints keys of subtree rooted at *T'.root* in sorted order. By binary-search-tree property, largest element in the tree is placed on the rightmost node and it's the last node visited during the in-order-tree traversal. So, that rightmost node's key is printed after the keys of $T'$ is printed. Since it's the largest element in $T$, and keys of $T'$ in printed in sorted order, we can conclude that *in-order-tree-walk(T')* prints keys of $T$ in sorted order.
> By induction principle, we can conclude that $P(n)$ holds for all positive integers.

Can we show correctness using this induction proof?
Is any parts of the proof need to be revised?

I appreciate your efforts.

EDIT: Trees/subtrees in this post refer to binary search trees. Binary search tree property is preassumed.

# Answer
In your proof the largest element of binary search tree $T$ can in fact be the root of the tree. I did not check whether you took care of that.

If you want to use induction by a number of elements in the tree, I would advise you to take *strong induction*, that is the hypothesis assumes the algorithm works for *any* number less or equal to $n$. Then the hypothesis can be applied to both subtrees which must have less elements than the full tree.

Finaly you could use *structural induction*, that is induction using the inductive definition of the structures you consider. Here that is the notion of a binary tree: which is either empty, or a root and two subtrees. In practise this gives the same proof as strong induction, but you did not need to quantify the number of nodes.
> 1 votes

---
Tags: algorithms, induction, binary-search-trees
---


# Question
Title: A doubt on best media for a time capsule
So, I have some data to a time capsule project of mine. But the thing is, I need to know the best media on long-time scale to use as storage unity. The time range is 120 years. Now, I've been thinking about two medias: the average CD-ROM/DVD-ROM and a outdated Vinyl/LP. On the one hand the CD/DVD is a good one, due to its dimensions and information space, but the question remains about the difficulties to read a CD/DVD in 2141. A vinyl LP could be more simple.

So my question is: what is the best media for a time capsule?

# Answer
This is an interesting question that has a multidisciplinary application. Not only does this apply to computer science, but given the nature of preservation of that data over time also applies to archival science!

While DVDs and CD-ROMs generally have a high information density, they were never designed with longevity in mind. The average life-expectancy for either of the two is about 100-200 years, according to Council on Library and Information Resources. \[\]

This may sound like a long time, but your question regarding the ability to retrieve the information 120 years from now comes into play. A major factor in deciding if a media is archival or not is the ability for that information to be interpreted years later. Assuming there is still a method for retrieving data from CDs and DVDs 120 year from now depends on several factors:

1. How much information are you looking to store?
2. What are the storage conditions? --You said "time capsule," but does this mean the capsule will be hermetically sealed? Will it be purged of all moisture, oxygen, and other environmental contaminants that are known to degrade material integrity over time? Will the environment be replaced with an inert gas like nitrogen to provide a stable environment?
3. What is the tolerance for data loss/corruption? Is this going to be something that needs to have archival quality, e.g. zero-tolerance for loss? CDs and DVDs can experience some loss given their storage and handling over time. \[\]
4. You have already asked one of the most important questions regarding the ability to retrieve the information 120 years from now.

The last question is something that archivists have been asking for some time. In today's world where we are generating more data on a daily basis than we have since the beginning of time, we need to develop a solution that addresses the questions of *how much* information needs to be stored and for *how long* does it need to last?

A question still remains unanswered: does your time capsule have to have media that already exists, or is it a quandary into the realm of storage technologies that could be developed to store information for a long period of time?

If it has to be of media that already exists, there are a few options out there:

1. Microfilm: industry standard for data preservation. Film of particular types is guaranteed to last for ~500 years. \[\] In the application of computer science, you could quite feasibly encode some arbitrary data in binary dots/dashes onto a piece of microfilm and interpret the data via computer. The advantage here is twofold: binary is a numbering system that isn't going anywhere and all you just need something to view the microfilm. Any intermediate technology can change between now and the next 120 years (think scanners, other ways of reading data into a computer), but all you need is *a way to read visual data into a computer*. This is unlike CDs or DVDs that can only be read by a very specific device.
2. You already mentioned one of them: an LP. Specifically an LP made from copper, aluminum and gold like the ones on Voyager I and II.
3. Least romantic? Straight up paper. As long as it is well-kept and information density is not a concern, acid-free paper will stick around for 120+ years (think The Declaration of Independence).

Things to *stay away from*:

1. SSDs or anything based on flash memory. These all need a minimum trickle charge of voltage to hold onto all of their data. Over time, the electrons leak from the storage cells and the data becomes corrupted. \[\]

Some things have already been proposed for future storage:

1. Recording the information on a CD or DVD-like surface, or a small square, either of which would be made from glass. This would not involve the metallic substrate employed by laser-read media that is known to degrade over time. The method for recording the information would be etched in the media by laser in a similar bit pattern, while using etchings of varying depths could be used to increase the information density.
2. Using DNA to encode data. DNA is known to last for millennia as long as it is kept from UV light. It would also provide a method of storing information in base-4 -- given the fact that DNA uses the four base pairs G, C, T and A to store information -- versus base-2, which uses 0 and 1. This would effectively increase the information density in two domains: the space in which the data could be stored given the relatively small size of DNA and the numbering system used to store that data.
> 2 votes

---
Tags: memory-hardware, storage
---


# Question
Title: Number of substrings possible with even characters
Consider a string 'ABBAA'
Possible substrings with even number of characters are $4$
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even - ($0$)
Similarly 'BB' and 'BBAA' substrings.
So a total of $4$ substrings are possible.

If given string is 'AABCCBBCAA'
substrings possible are "AA" "BB" "AA" "CC" "BCCB" "CCBB" "CBBC" "CBBCAA" "AABCCB"

So total $9$ substrings are possible

Is there any pattern or sequence or algorithm to find this?

# Answer
> 4 votes
Assuming that your alphabet has constant size, you can solve your problem in linear time in the length of the input string.

Let $\Sigma = \\{a\_1, a\_2, \dots, a\_m\\}$ be your alphabet and $s = s\_1 s\_2 \dots s\_n$ be your input string. For $i=0, \dots, n$, and $j=1,\dots,m$ let $n\_j(i)$ be $0$ iff the number of occurrences of $a\_j$ in $s\_1 \dots s\_i$ is even and $1$ otherwise. Let $\eta(i) \in \\{0,1\\}^{m}$ be the vector $(\eta\_1(i), \dots, \eta\_m(i))$.

Consider any substring $s\_{hk} = s\_{h+1},s\_{h+2}, \dots, s\_k$ of $s$, where $0 \le h \< k \le n$. The number of occurrences of each $a\_j$ in $s\_{hk}$ is even if and only if $\eta(k)-\eta(h) = (0, \dots, 0)$, where the difference is taken modulo $2$, i.e., iff $\eta(k)=\eta(h)$.

Then your problem is equivalent to counting the number of unordered pairs of distinct indices $\\{h,k\\}$ for which $\eta(h)=\eta(k)$. This can be done as follows: given $x \in \\{0,1\\}^{m}$ let $\alpha(x)$ be the number of times of $x$ appears in $\eta(0), \dots, \eta(n)$, so that the number of unordered pairs $\\{h,k\\}$ for which $\eta(h) = \eta(k) = x$ is $\binom{\alpha(x)}{2} = \frac{\alpha(x) (\alpha(x)-1)}{2}$.

To find the find the overall number of substrings of interest it suffices to sum the above quantity over all choices of $x \in \\{0,1\\}^m$: $$ \sum\_{x \in \\{0,1\\}^m} \binom{\alpha(x)}{2} = \frac{1}{2} \sum\_{x \in \\{0,1\\}^m} \alpha(x) (\alpha(x)-1). $$

Since $m=O(1)$, all values of $\eta(i)$, for $i=0, \dots, n$ can be computed in $O(nm) = O(n)$ time. Moreover, all values of $\alpha(x)$ for $x \in \\{0,1\\}^m$ can also be found in $O(n m \log \min\\{n, 2^m\\}) = O(n)$ time by scanning $\eta(0), \dots, \eta(n)$ once and maintaining a counter for each $x$ (these counters can be stored in a dictionary with at most $\min\\{n,2^m\\}$ elements). Finally, the final sum can be computed using $O(\min\\{n, 2^m\\}) = O(1)$ arithmetic operations (as it only needs to extend to $x \in \\{0,1\\}$ for which $\alpha(x) \> 0$).

---

An example implementation due to @orlp of the above in Python using a binary integer as the vector $x$ and storing all $a(x)$ in a hashmap counter is as follows:

```
def num_even_substrings(s):
    a = {0: 1}
    x = 0
    for c in s:
        x ^= 1 << ord(c)
        a[x] = a.get(x, 0) + 1
    return sum(ax*(ax-1)//2 for ax in a.values())

```

---
Tags: algorithms, logic, combinatorics, strings, counting
---


# Question
Title: Is there a binary representation where the encoding distance grows with the arithmetic distance?
I need to binarily encode/decode small integers (around 10 bits), in such a way that the hamming distance of the encoded number grows monotonically with the (absolute value) arithmetic distance of the numbers.

Edit: the monotonicity doesn't needs to be absolute. There is probably a cost to pay breaking it, but the cost should be as low as possible. Is preferable to reduce the hamming distance at short scales, and if unavoidable, break it at larger scales.

For example:

The question is: **Is there already such an encoding (better if it has error correction)?**

I need to use it in python, so if there is already a python library to do the encode/decode, it would be perfect.

The "monotonically growing" requirement is a loose requirement. It is not strictly necessary. It just is convenient that the hamming distance reflects the arithmetic distance in some way.

The hamming distance can be replaced wit some other measure of encoding distance, like Jaccard distance.

The requirement is that close integers share most of their binary encoding, and still there is error correction.

# Answer
You can get some kind of tradeoff between unary and binary.

Start by choosing some integer $k$ and set $w=2^k-1$.

Then write $x$ as $x=r+w+w+\ldots+w$, where $r$ is the remainder of $x$ when divided by $w$. Let $\bar{a}$ denote the binary encoding of $a$. You can encode $x$ as $e(x) = \bar{r}\bar{w}\bar{w}\ldots\bar{w}$.

This encoding is of length $k\times x/w$ and you have $d\_{hamming}(x,y)$ which should be in the range from $\frac{1}{w}(|x-y|-1)$ to $\frac{k}{w}(|x-y|+1)$ (give or take some rounding errors on my part).

The smaller $k$ you choose, the better correspondence between Hamming distance and absolute difference, but the longer the encoding.

You can also use Gray code instead of binary to squeeze a bit more out of it.
> 2 votes

# Answer
Unary encoding meets all of your stated requirements, with $c=1$. This will work poorly for large integers, because the encoding grows very long, but for small integers, it is probably fine.
> 1 votes

# Answer
Here’s what you can try: Start with 0 encoded as all bits zero. To encode k+1, determine which is the highest bit you would set to change from k to k+1 in pure binary, and change only that bit. So the number of bits changing when you add 1 is at most 1.

Numbers 0 to 15 are 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.
> 1 votes

# Answer
Try gray code encoding. It is basically used already in many places and fits your needs.

A link to some python module to start with: link
> 1 votes

---
Tags: encoding-scheme, binary, numeral-representations
---


title: Dynamic programming for graph splitting

text:
# Question
Title: Dynamic programming for graph splitting
I have a directed graph which has edges between every vertices $i$ and $j$ such that $i \< j$ and the edge is from i-\>j and every vertex needs to be visited. I need to divide the graph into two parts such that the travel distance on both the parts i.e. sum of edge weights while traveling from the lowest index to the highest index in each of the group is minimum. For example there is a graph of 4 vertices where each edge weight is the following

* $w(1, 3) = 2$
* $w(1, 4) = 1$
* $w(3, 4) = 3$
* $w(1, 2) = 100$
* $w(2, 3) = 100$
* $w(2, 4) = 100$

The solution would be $\\{2\\}, \\{1, 3, 4\\}$. In the first group {2} doesn't have any vertex so no edges between any of the vertices in that group. In the second group we travel from 1-\>3 and 3-\>4 so the edges we travelled would be 2 + 3. Hence the ans would be 0 (from the first group) + (2+3) (from the second group). We start from the lowest index vertex and move to the highest index vertex as the edges are from lower index to higher index vertex.

The algorithm I came up was a brute force i.e. considering each combination and return the minimum of it i.e. to take one vertex in one group or include in other which leads to complexity $O(2^n)$.

I want to get the above problem to run in $O(n^2)$ solution. I did draw a decision tree for the above problem and can see nodes being overlapped i.e. $\\{1,2\\}, \\{3,4\\}$ and $\\{3,4\\}, \\{1,2\\}$ so I figured this is a dynamic programming problem but I am not able to define the states.

Edit - It can be done using a 1d dp array

# Answer
I don't have a dynamic programming solution but this problem can be efficiently reduced to a minimum weight max-flow problem.

Let $G$ denote your original graph. We will create an instance $(s,t,G')$ of the minimum weight max-flow problem as follows:

* Let $W$ denote the sum of all weights in $G$ plus one.
* For every vertex $u$ in $G$, we create two vertices $u\_{in}$ and $u\_{out}$ in $G'$ and add a directed edge from $u\_{in}$ to $u\_{out}$ with weight $-W$ and capacity $1$.
* For every directed edge $e=(u,v)$ in $G$, we add a directed edge from $u\_{out}$ to $v\_{in}$ in $G'$ with weight $w(e)$ and capacity $1$.
* We create a vertex $s'$ and we connect the source $s$ to $s'$ with a directed edge of weight $0$ and capacity $2$.
* We connect $s'$ to every "in" vertex with a directed edge of weight $0$ and capacity $1$. We connect every "out" vertex to the sink $t$ with a directed edge of weight $0$ and capacity $1$.

Let $n$ denote the number of vertices in $G$. Then the vertices in $G$ can be partitioned into two vertex-disjoint paths of total weight $k$ (which is what you want) if and only if there is a max-flow in $(s,t,G')$ with total weight $k-nW$. Moreover, this flow is the union of two paths in $G'$ (which are disjoint except at $s$, $s'$ and $t$) , from which you can easily retrieve the two vertex-disjoint paths in $G$.

Note that by changing the capacity of the $(s,s')$ edge from $2$ to whatever integer we like, we can generalize this approach to partitioning into arbitrary number of vertex disjoint paths with minimum total weight.
> 2 votes

---
Tags: algorithms, graphs, dynamic-programming
---


# Question
Title: Is it possible to wear-level a FAT32 file system?
Because SD cards use flash memory, they should requires wear leveling to avoid significantly shortening the life of the card. At the same time, my understanding is that they usually use a FAT32 file system.

My understanding of FAT32 is that there is a small "file system description" block at the beginning of the device, which is followed by the file allocation table (FAT) describing which files are stored where. However, because the FAT needs to be updated every time a file is moved/copied/appended/etc, then doesn't that mean the FAT gets written to many times more often than the rest of the card?

For example, if each erasable block of an SD card is 4 KB, and it uses a 32-bit address space, they each erasable block of the FAT contains 128 addresses, so the FAT should get erased and written ~128 times as often as the rest of the device. If this hypothetical device has an expected life span of \>100k cycles, then should it not wear out around 1k cycles if it spends the entire time formatted with a FAT32 file system?

And, if my current understanding is true, then wouldn't FAT32 be basically the worst possible way to format a flash memory device? Or is this a problem that all file systems have, so FAT32 isn't apreciably worse than anything else?

# Answer
The OS references blocks using a "logical block address". The SD card then maps this to a physical page of flash memory. With wear leveling, each time data in that block is changed, it will get mapped to a new physical page of flash memory. So, even though the OS is changing the same "logical block address" every time, this is causing different physical pages in flash to be erased and rewritten. This spreads out the "wear" across the entire flash device, lengthening its lifetime and avoiding the problem you mentioned. In other words, although the FAT32 is stored at the same "logical block address", it isn't stored on the same physical page of flash memory every time it is modified.

I'd expect that any commercial flash storage device you buy today will be using wear leveling, because of exactly the problem you mention if wear leveling isn't used. This problem is not specific to FAT32; it occurs with essentially all conventional filesystems.
> 6 votes

# Answer
When flash storage is exposed directly to the operating system, it's used with a file system specifically designed for flash, like JFFS2.

USB and SATA flash drives emulate Winchester hard drives, and do wear leveling in the firmware. The details are proprietary and specific to each drive, but it's probably broadly similar to the way JFFS2 works. A file system like FAT32 is layered on top of this. The FAT32 driver thinks it's writing the same sector over and over, but the firmware maps each write to a different block of flash memory.
> 3 votes

---
Tags: filesystems
---


# Question
Title: Probability of arising of simple graph in configuration model
I am studying a configuration model building $d$-regular graphs and reading the following article: The expansion of random regular graphs by David Ellis.

I am stuck on the following step:

> Each simple labelled $d$-regular graph on $n$ vertices has the same probability of arising. Indeed, it is easy to see that a simple d-regular graph on $\[n\]$ arises from precisely $(d!)^n$ of the matchings.

Where does this $(d!)^n$ come from?

# Answer
> 1 votes
Consider a simple $d$-regular graph. For each vertex, assign numbers from $1$ to $d$ to the edges adjacent to it. There are $(d!)^n$ ways to do so. Each such assignment corresponds to a particular perfect matching in the configuration model, and vice versa.

---
Tags: graphs, combinatorics, random-graphs
---


# Question
Title: Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?
In my analysis of algorithms class we were given the following recurrence relation:

\begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\ 2T\left(\displaystyle\frac{n-1}{2}\right), &n \ \mbox{is odd number}& \end{cases} \nonumber \\ T(1) &=& 1 \end{eqnarray}

I have proved by iteration (expand) that when $n = 2^k$ (always the even case), $T(n) = O(\log{n})$; when $n = 2^{k+1}-1$ (always the odd case), $T(n) = \Omega(n)$.

Is this actually possible? After looking at some other posts, I am thinking this is possibly because the $\Omega(n)$ obtained here is the lower bound runtime of the worst case scenario, and the $O(\log{n})$ is the upper bound runtime of the best case?

Am I confusing something? Or is there any other conclusion can be drawn from the result that $T(n) = O(\log{n})$ and $T(n) = \Omega(n)$ for the recurrence?

# Answer
Your recurrence satisfies neither $T(n) = O(\log n)$ nor $T(n) = \Omega(n)$.

What does hold is that there exists an infinite sequence of values $n\_k$ such that $T(n\_k) \leq C\log n\_k$, and another infinite sequence of values $m\_\ell$ such that $T(m\_\ell) \geq c m\_\ell$, where $C,c\>0$ are some constants.

The definitions of big O and big Omega require such inequalities to hold *for all large enough $n$*, rather than for infinitely many values.

---

A similar situation is that of *partial limits* and *limits superior and inferior*. Consider the sequence $\sin n$ (where the angle is measure in radians). For each $x \in \[-1,1\]$, we can find an infinite sequence $n\_k$ such that $\sin n\_k \to x$. These are the *partial limits* of the sequence. The limit superior of the sequence is $1$, and its limit inferior is $-1$.

Similarly, in your case, $\Theta(\log n)$ and $\Theta(n)$ are "partial asymptotic limits", in the sense that there is an infinite sequence $n\_k$ such that $An\_k \leq T(n\_k) \leq Bn\_k$ for some $A,B\>0$, and another infinite sequence $m\_\ell$ such that $C \log m\_\ell \leq T(m\_\ell) \leq D \log m\_\ell$ for some $C,D\>0$. The "asymptotic limit superior" is $O(n)$, since $T(n) = O(n)$ but $T(n)$ is not $O(f(n))$ for any $f(n) = o(n)$. Similarly, the "asymptotic limit inferior" is $\Omega(\log n)$, since $T(n) = \Omega(\log n)$ but $T(n)$ is not $\Omega(g(n))$ for any $g(n) = \omega(\log n)$.

(Showing that $T(n) = O(n)$ and that $T(n) = \Omega(\log n)$ requires an argument.)

---

A sequence such as $\sin n$ has no limit. Similarly, $T(n)$ has no "asymptotic limit", that is, there is no "nice" function $h(n)$ such that $T(n) = \Theta(h(n))$ (we can define "nice" in various ways, for example a logarithmico-exponential function, that is, a function which can be expressed using arithmetic operations, $\log$ an $\exp$).
> 0 votes

# Answer
You calculated “Big-Theta for n = power of two - 1”. That’s not a useful thing. Try calculating T(n) for n = (4^k - 1) / 3 and be surprised. (Write n down in binary first). Or n = 3 * (8^k - 1) / 7 where T(n) ≈ n^(2/3).

You found the values for a good case and for a bad case. You’ll have to prove they are lower and upper bound.
> 0 votes

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


# Question
Title: Turing machine - definition of program - naive question
In the paradigm of Turing machines what is considered a program? Can't find a definition anywhere. Is it a member of L(M)?

# Answer
The Turing machine itself is the program.

You can see this in universal Turing machines. A universal Turing machine accepts a description $\langle M \rangle$ of a Turing machine $M$ and an input $x$, and runs $M$ on $x$. Thus $M$ (or rather, $\langle M \rangle$) is the *code* or *program*, and $x$ is the *input* or *data*.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Efficient cardinality of set overlap relation
Assume that we have a set `S` of sets `s`.

Every pair `(s,s')` in `SxS` can be overlapping or not.

How can we efficiently compute the number of pairs `(s,s')` that are overlapping, i.e. that share at least one element?

Additional: actually each set `s` occurs a number of times (`S` is a multiset). I have tried to create a matrix `M` of `scipy.sparse.csr_matrix` that stores the subset partial order over `S`. Then I have tried to add the additional edges for overlaps through `M.T.dot(M)` to then later compute `f.dot(M).dot(f.T)`, where `f` gives the frequency for each `s`. Unfortunately `M.T.dot(M)` becomes too large, so if anything, we probably have to propagate the counts through the subset partial order one after the other.

Hints: it might seem apparent at first to just take the sum over the union of all elements in all `s` of their frequency squared to sum up the number of pairs sharing one particular element. However the problem is that this counts many pairs multiple times. For example `{a,b}` is counted for `a` and also for `b`. This is why it seems important to use the subset partial order.

Any ideas?

# Answer
> 2 votes
Consider the following problem. We are given $n$ sets $S\_1,\ldots,S\_n \subseteq \\{1,\ldots,\log n\\}$, and have to decide whether there are two disjoint sets among them. This problem is known as *Orthogonal Vectors* (OV), and it is conjectured that it cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon\>0$ (on a RAM machine). See for example Chen and Williams, An Equivalence Class for Orthogonal Vectors.

---
Tags: sets, mathematical-foundations, set-cover, partial-order
---