# Question
Title: Order list of lines to make them form a closed contour
I need to solve the following type of problem. I have a list of many connected lines forming a closed contour. These lines come as the output of a MarchingSquare algorithm. Consequently they are lines that have their start and end points on the sides of a grid. Furthermore, the lines never intersect except at the extreme points. But these lines are in random order and I would like to rearrange them in such a way that each line is in the list exactly before and after the two adjacent lines that start and end at the start and end point of the line in question. I tried a first "brutal" algorithm that works as follows, but obviously it's very slow: I start from any of the lines in question that I add to the new list. I pass through each of the other lines and evaluate the distance between the start and end point of this last line and my starting line. If I find that the distance is smaller than the tolerance I gave myself (for example 1e-10) I remove the line from the list I add the line to the new list. Then I iterate the procedure until I have emptied the initial list.

# Answer
1. Don't work with distances but with the indexes of the grid edges (assign distinct numbers to all sides, vertical or horizontal). In marching squares, every point is repeated on two neighboring cells, on their shared edge, and there is no more than one point per edge.
2. Generate all line segments and store their endpoints in a single hash map with the edge index for the key, but keep mutual links.
3. Starting from an endpoint, follow the link to the buddy, and from the buddy find the matching endpoint on the same edge.
4. Continue until you are back to the initial point, or hit a border of the domain (in this case restart the search from the initial point, to the other side).

The total search time will be roughly proportional to the number of segments.

Be careful to handle the special cases with endpoints close to a grid node. A Quick and dirty solution is to apply a small displacement to endpoints near a node.

E.g.: segments $9-8',8'-3,3-4,5-4,11'-5,13-11',\cdots$ (all upward), curve following $9-8'-3-4-5-11'-13-\cdots$,
> 0 votes

---
Tags: algorithms, graph-traversal
---


# Question
Title: What is currently the best theoretical book (or notes) about Convolutional Neural Networks?
I have a degree in maths and i am interested in learning about Convolutional Neural Networks from a mathematical/ theory point of view. Can someone point me towards some resource.

I already have a basic knowledge of Convolutional Neural Networks (and other Neural Networks)

# Answer
Can I suggest Deep Learning from Ian Goodfellow, Yoshua Bengio and Aaron Courvile. It has a whole chapter on Convolutional Neural Networks and the background to all Neural Networks. Furthermore the Bibliography has a list of key papers if you want to dig deeper or into recent developments.
> 1 votes

---
Tags: machine-learning
---


title: Is Python a context-free language?

text:
# Question
Title: Is Python a context-free language?
From Wikipedia: Off-side\_rule#Implementation, there is a statement:

> ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation when this changes, and thus the **lexical grammar is not context-free** – INDENT/DEDENT depend on the contextual information of previous indentation level.

I'm a bit confused. Some lexical grammars of Python is not context-free but INDENT/DEDENT themselves can be expressed in CFG. So lastly, Python is a context-free language or not?

# Answer
Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these languages use additional techniques to handle those structures. For example keep track of indentation levels, or tokenizer (scanners) may count number whitespaces and store that info in a table for later use. This is similar to something like trying to write a parser for the language $a^nb^{2n}c^n$, where you must keep track of value of $n$.

A simple example of adding additional power to a lexer is removing redundant whitespace symbols (space/tabs/newlines) or removing comments which has no meaning for the parser (parsing a CFL).

**As another example, roughly it can be described as following. Assume a grammar $a^nb^mc^k$ which is clearly CFG. You use BISON/YACC like tools to generate a parser for this grammar. Then you can introduce an additional rule like number of $a$s must be equal to the number of $c$ which makes the language non CF. So you just add extra logic (manually coding) to your parser to handle that rule by means of, say, annotated trees. Your original language is still context free but extra piece of code you added manually allows it to accept non CF subset of the original language.**

I don't think that such parsers are generated automatically by compiler tools (at least I don't know) and so that ("non context free") part must be coded manually.
> 19 votes

# Answer
Python is not a context free language. We can check any language context free or not using Odgens's lemma (In the theory of Formal languages).
> -1 votes

# Answer
It is not context free. I.e., it is illegal to call a function that isn't defined, and that can't be expressed by a context free grammar. Or just write `print(a)` at your nearest Python interpreter, it will inform you `a` isn't defined.
> -1 votes

# Answer
No, Python is not a context-free language. It is a programming language that follows a syntax defined by a context-sensitive grammar. Context-free languages are a subset of formal languages that can be described by context-free grammars, where the structure of the language is determined solely by the arrangement of its symbols, independent of any context or surrounding symbols. However, Python's syntax includes constructs like indentation and significant whitespace, which make it context-sensitive. These features affect the meaning and behavior of the code, and they depend on the context in which they are used.
> -4 votes

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


title: How does OSI model and TCP/IP work?

text:
# Question
Title: How does OSI model and TCP/IP work?
If I go into google browser and type in the name of a website, this is the application layer of the OSI. HTTP protocol is being used and is a request-response, so when exactly does my computer send the request to the server and when do I get the response?

I understand the encapsulation of data until it gets to the physical layer, is the HTTP request before then? If so how does it get across to the server? Thanks

# Answer
> 1 votes
**How does the internet works?**

I could answer this question in one sentence or we could be here for hours. But I want to keep things simple and easy to understand.

The internet is literally a mesh of wires spread around the world that connect different devices to each other. Even if you do not see a physical wire, you can imagine your smartphone connected to a WiFi router via a virtual wire that lets you talk to a Google server situated miles away from you.

When you want to send some data to a device that is connected to your personal device via the internet, you need to follow some rules. All the data transferred over the internet is binary data consist of 1s and 0s.

1. First of all, the application being used to send data needs to communicate with the hardware on the device to send the data over the internet. Also, the hardware of the device needs to communicate with the device that is actually transmitting the data over the internet like a WiFi router.
2. When you send a letter to a person, you label your letter with the address of the receiving person so that the letter gets delivered to the right person. Similarly, when you send some data over the internet, you need to know the address of the device that will receive it eventually.
3. When a network application is launched in a device like a web browser or a web server to transmit or receive the data, it will listen to the internet data on a port number like 8080. The sender needs to know about the port number of the receiver device so that the data is received by the correct application and not the one that may abuse it.

These port numbers are randomly assigned by the operating system but we can force the operating system to bind an application to a certain port number.

4. The device receiving the data would not be able to make sense of it unless it has prior knowledge of what it is looking at. The data could be an image, a song, a plain text message or an HTML document. Hence we need to tell the receiver about the data type so that it can interpret it correctly.

These four steps describe a communication model for data transmission on the internet. Each of these steps is defined by a protocol. Depending on the type of protocol, each of these steps formats the data accordingly so that the receiver can extract the data properly.

There might be more steps in a particular model depending on the use case of the data transmission. You can read about the OSI model which can be used by anyone to transmit data over the internet or Local Area Network (LAN).

If we inspect these steps carefully, they form a pipeline where data from one step is sent to the other step for further processing until it gets transmitted over the internet. However, the layer would be the most suitable word to describe each step and we will soon learn why.

$....$

# TCP/IP Communication Model

The Transmission Control Protocol (TCP) is the transport layer protocol in the communication model we saw earlier while Internet Protocol (IP) is the internet layer protocol.

These protocols together drive most of internet communication. At this very moment, your browser is using the TCP/IP model to load this webpage from a server. Hence, these together form the internet protocol suite.

In the above communication model (left side), the application layer gets the data from a source (like internal storage or RAM) and wraps some headers of a particular protocol like HTTP. This creates a data package of the HTTP protocol and can be read by an application that can understand it like a web browser.

This HTTP application data is sent to the transport layer. The transport layer wraps the package with TCP protocol headers along with the source and destination ports. The source port is the port of the application transmitted the data (like a web browser) and destination port is where the application running on the receiving side will receive it.

This TCP segment is received by the internet layer which wraps some IP protocol headers with source and destination IP addresses. The source IP address is the IP address of the sender device while the destination address is the IP address of the receiver device.

An IP address is a unique number allocated to a device on the internet. You can read more about IPV4 and IPV6 IP address formats. The IP address of a device can be known prior to the data transmission or can be resolved from a DNS server using the domain name contained in the HTTP header.

Once the segment is stamped with IP protocol, it becomes a network packet that is good enough to be transmitted over the internet. This is the last step of the virtual layers (processed by a computer program).

The last link layer is a physical layer on the device. This is a hardware part like the Network Interface Card (NIC) on your device which takes the packet and adds the source and destination MAC addresses to it.

The Media Access Control (MAC) address is the unique address of a hardware part provided by the equipment manufacturer. Using MAC addresses, communication between two devices becomes possible.

Once the packet is labeled with source and destination MAC addresses with some additional headers of a data transmission protocol (like Ethernet) it becomes a data frame, it can be sent to the internet communication device like a WiFi router or Satellite Dish that will take care of the transmission over the internet.

Once the data frame is received at the receiving end (right side of the diagram above), it will be peeled like an onion until the original data (the HTML document) is recovered.

The data is extracted successfully without any misinterpretation, one layer at a time, by looking at the protocol of that layer. Once the original data is extracted, it can be consumed by the correct application.

For example, if a server sends an HTML page using the HTTP protocol, a web browser is fully capable of understanding a package of an HTTP protocol and extracting the HTML page. This HTML document will then be rendered on the screen by the browser.

The HTTP protocol can also be used to transmit data other than HTML pages. The Content-Type header of the HTTP protocol is used by the application like a browser to understand the MIME type of the content.

If the receiver wishes to send the data back, it can use the source address of each layer provided by the sender to successfully send the data back in the same manner.

$...$

---
Tags: computer-networks
---


# Question
Title: On hardness of finding total dominating sets in triangle-free graphs
A *total dominating set* $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The *minimum total dominating set* of $G$ is a total dominating set of $G$ of minimum possible size. The *minimum total domination number* of $G$ is represented by $\gamma\_t(G)$.It is known that MTDS is $NP-complete$ for general graphs, bipartite graphs, chordal graphs, etc. \[**REFERENCE**: Henning, Michael A.. “A survey of selected recent results on total domination in graphs.” Discret. Math. 309 (2009): 32-63.\]

**Do we know anything about hardness of MTDS on *triangle-free* graphs of bounded degree?Or *triangle-free* graphs in general?** ( A graph is *triangle-free* if any three vertices does not form a triangle).

# Answer
The problem is indeed $\mathsf{NP}$-hard on bipartite graphs (which are triangle-tree) of degree at most $3$. See Theorem 6 of this paper.
> 3 votes

---
Tags: graphs, reference-request, np-hard, combinatorics
---


# Question
Title: Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it
Were *w* is any string composed over the alphabet $\Sigma = \\{0,1\\}$.

1. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the string before the 0 the second one for the 0 itself and the third for the rest of the string after the 0. This is what I came up with: $$ \begin{align} S &\rightarrow S\_{1}S\_{2}S\_{3} \\ S\_{1} &\rightarrow 0S\_{1}|1S\_{1}|\varepsilon \\ S\_{2} &\rightarrow 0 \\ S\_{3} &\rightarrow 0S\_{3}|1S\_{3}|\varepsilon \end{align} $$

But I'm not sure if the presence of the $\epsilon$ means that input strings such as $01$ or $10$ could be accepted, or if the $\epsilon$ at the end just ensure the recursion of the grammar.

2. For the second part I have no idea about a possible solution.

Any help would be most appreciated. Thanks in advance

# Answer
In your solution there is no guarantee that the words generated by $S\_1$ and $S\_2$ will have the same length. The trick is to generate both sides simultaneously: $$S \to 0S0 \mid0S1 \mid1S0 \mid1S1 \mid 0.$$

As for the second part, there are mechanical procedures to convert a CFG into a PDA.
> 0 votes

---
Tags: formal-languages, context-free, pushdown-automata, stacks, chomsky-hierarchy
---


# Question
Title: if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?
if by absurdly there is a 3/2-approximation algorithm for *INDIPENDENT SET* then does there exist a 3/2-approximation algorithm for *VERTEX COVER*? the implication should be true because independent is reduced to to *VERTEX COVER*, right?

# Answer
> 2 votes
Try to prove it. Don't just assume "it should be true"; write out the proof in detail. Specify the algorithm for finding a 3/2 approximation for Vertex Cover concretely. Provide a proof that its output is a 3/2 approximation.

If you try to do that, you should be able to answer your own question for yourself.

---
Tags: complexity-theory, reductions, approximation, vertex-cover
---


# Question
Title: Introduction to theoretical computer science for research mathematicians
> Are there any references on theoretical computer science aimed at people with a background in research mathematics?

For reference, I spend my time thinking about category theory and set theory most days. I've begun programming in haskell and it feels very intuitive now that I'm starting to get the whole 'type' syntax down, but reading through some stuff comparing haskell to other languages got me thinking about the foundations of programming, and now here I am.

Some light searching revealed that Knuth has a series considered a standard reference by many; I'm familiar with Knuth as a mathematician and fond of his work, so this seems promising. I've also heard that the computing handbook is widely considered a standard reference.

Are there any standard references I'm missing, or narrower ones geared towards set/category theorists? Research papers are certainly welcome, and any pointers are appreciated.

# Answer
You could look at semantics of programming languages textbooks that rely on category theory.

For instance: Check out the books advised \[here\]\[1\].

This is part of theoretical computer science. Dana Scott's work is particularly relevant. As is Lawvvere's later work, topos theoretic applications etc. \[1\]: https://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics
> 1 votes

---
Tags: reference-request
---


# Question
Title: NP-HARD optimization problem and instance correlation
If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?

# Answer
I assume in this answer that $A$ is NP-complete, since otherwise it is possible that $A$ is unsolvable, or that the output size is super polynomial in $n$.

Assuming $A$ is NP-complete, let $x$ be some instance, and let $s$ be the optimal output for $x$. Let $\mathcal{A}$ be an algorithm that solves $A$ in (possibly exponential) deterministic time. Let $\mathcal{A}^s\_x$ be the algorithm that given $x$ it outputs $s$, and otherwise it simulates $\mathcal{A}$.

Then this algorithm has linear running time in $|x|+|s|$ which is polynomial in $|x|$ (which is constant), an solves $A$ correctly in general.

Intuitively, when you fix an instance, then a solution already exists, and both the instance and the solution have constant size, we just do not know how the solution looks like, and hence, we don't know how the algorithm $\mathcal{A}\_x$ looks like, but it exists!
> 1 votes

---
Tags: complexity-theory, optimization, np-hard, polynomial-time, information-theory
---


title: NP-Complete Proof - Using CFLP

text:
# Question
Title: NP-Complete Proof - Using CFLP
I have formulated the below optimization problem.

\begin{align}\nonumber \hspace{-3mm}&\text{(P) minimize}\\!\sum\_{i}\\!\alpha\_{i}w\_{i}\\!+\\!\sum\_{i}\sum\_{j}\\!c\_{ij} p\_{ij}\\!\\ \text{s.t.} & \sum\_{i}\\! p\_{ij} = 1 , \forall(j) \in \mathcal{J}\\ & \sum\_{j} d\_j p\_{ij} \leq b\_i w\_{i} , \forall(i) \in \mathcal{I}\\ & p\_{ij} \in \\{0,1\\}, \forall(i) \in \mathcal{I},\forall(j) \in \mathcal{J}\\ & w\_{i} \in \\{0,1\\}, \forall(i) \in \mathcal{I}\\ & q\_{i} \in \\{0,1\\}, \forall(i) \in \mathcal{I} \end{align}

In $(P)$:

* $w\_i$ and $p\_{ij}$, and $q\_i$ are decision variable.
* $\alpha\_i,c\_{ij},\beta\_{i}$ are coefficients.

For the proof of being NP-complete, It is easy to show that problem in is NP. For the reduction part of the proof, I aimed to show that Capacitated Facility Location Problem is polynomially reducible to $(P)$.

The main obstacle (so as to prove the instance of CFLP can be solved as instance of our problem) here is that in order to remove the last term in objective function of $(P)$, we can set the decision variable $q\_i=0$, however, it yields that $w\_i$ should be $1$ for all $i$ (due to existence of third constraints). In CFLP notation, it means that all facilities should be open (which does not parse to me). Is there any alternative way to for the proof?

# Answer
Just set $\beta\_i = 0$ instead of $q\_i$.
> 2 votes

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


title: Associative memory addressing

text:
# Question
Title: Associative memory addressing
I would like to understand better how associative memory works.In associative memory we have the tag and the actual data being stored.The tag describes where the data came from but what does this mean exactly?

# Answer
Associative memory, also known as content-addressable memory is a memory that you access by supplying the tag rather than an address (using your terminology). For efficiency, the lookup is performed by specialized hardware.

It is useful for instance in paging systems, where you give a virtual page number and the memory manager quickly tells where it resides in RAM.

In software, this compares to a hash-map.
> 1 votes

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


# Question
Title: Are GPU's only a fraction of the cost of supercomputers?
According to wikipedia, the Frontier supercomputer is the largest supercomputer in the world, at 1 exaFLOPS, and cost 600 million USD.

I am quite surprised that the largest supercomputer only has 1 exaFLOPs, because of the following:

* The AMD Instinct MI250X has about 100 teraFLOPS, i.e. 0.1 petaFLOPS.
* Hence, if you stick about 10000 MI250X's together, you get 1 exaFLOPS.
* The price of an AMD Instinct MI250X is about 10k USD, so 10000 of them are about 100 million USD.
* This would suggest that the actual workhorse of the supercomputer is only 20% of its cost (since Frontier cost 600 million USD).

Maybe I did my calculation incorrectly, but if not then this surprises me. Why are the GPU's such a small fraction of the actual cost?

ps. Not sure which stackexchange to use for this if computer science is the wrong one.

# Answer
You have to remember that sticking a bunch of GPUs together does not linearly increase the performance. You can argue that yeah, if all the GPUs are running then instructions are being run, but to actually efficiently run useful operations on a bunch of GPUs is no easy task.

Some factors for scaling up GPUs:

* Communication: this is a big one. If you have a bunch of GPUs, how do you broadcast instructions to all of them, and put them all back together?
    + On this topic, you would need bridges or some sort of other hardware to communicate data. If you have to transfer large amounts of data across distances, you will lose time while you wait for data transfers.
* Benchmark for instructions: There's a bunch of literature (and scandals) about how chip companies purposefully devise very specific tests to boost their flop count in the disgust of their competitors. A big historical one has been CISC vs RISC processors.
* Architecture: Again, this has to do with linearity, but a supercomputer will have a very different design than your personal computer. A supercomputer will have specialized architecture and hardware just to make that 1 TF work, which will add to the cost. Also having a 1 of 1 will make the production cost more expensive than a mass produced item like an AMD graphics card.
> 2 votes

# Answer
Labor cost. 6x is an amazingly great work!

DoD kept awarding modular cellular designs on infinitely scalable FPGA arrays for many decades, and those projects have failed inevitably due to the lack of a distributed parallel model of computation. We just bunch whole bunch of von-Neumann cores to each other, than try to comprehend and scale that mess.

Building a new supercomputer is a manual architecture every single time.

Writing software for every new supercomputer is a manual labor every single time.

Nobody still has solved infinite scalability problem.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Exactly how many clocks does a Computer consists of and how do they synchronize with each other?
I am currently trying to understand how Computers are arranged and organized internally (so that I can learn Assembly Language) through an online book called The Art of Assembly by Randall Hyde. Irrespective of whether or not I'll learn Assembly, I'm finding it difficult to understand exactly how is everything synchronized in the Computer. I'm currently at **3.2 - System Timing** topic.

Below are my observations and the things I currently understand not only from the book but also from the things I learned through understanding computers in general.

Reading the book, I've came to understand that there are atleast 2 clocks in the whole system. One is the *System Clock* which makes one of the lines within the Control Bus go **HIGH** and **LOW** periodically. The CPU also has it's own *Internal Clock* which controls the operations which are done by the CPU. Now the Internal Clock should be in sync with the System Clock for the whole system to make sense which means the control line (which oscillates between low and high) should be connected to the CPU so that both the clock combine and act like a single clock. But then this happened:

*The above snippet is from the PDF version of the same book.*

I still didn't get confused after reading this. I perfectly understood that the Internal Clock just runs twice as fast as the System Clock which is fine. My confusion came when the Author mentioned the words "On a 5 MHz 8088/8086 CPU the memory access time..." and "On a 50 MHz 80486, the memory access time...". The question is, 'How can CPUs have their clocks running at certain frequencies when their Clock depends on the System Clock?'. 'Shouldn't their Internal Clock run at a certain multiple of the System Clock?'. I've also came across overclocking the CPU and stuff. 'Won't that make the Internal Clock of the CPU go out of Sync with the System Clock?'

Perhaps the main problem in understanding how everything is synchronized in Computer is the understanding of the word 'synchronized'. And also, 'How many clocks are there in the Computer as a whole?'. Because "Zafaria Kansa" says on the following link on Quora that there are 'Internal' and 'External' Clocks on the CPU: `https://www.quora.com/What-does-GHz-mean-How-does-it-relate-to-processor-speed` (I don't have enough reputation to post more than two links). Does she mean 'System Clock' when she said 'External Clock'? How does everything fit together?

# Answer
Modern processors tend to have more clocks than processors in the past, because that means when a part of the processor isn't used, it may be possible to switch off that part completely, including the clock, to save energy.

Clocks are often not synchronised, because synchronising and keeping them synchronised is expensive and complicated, and if you can make a part of the processor work correctly without synchronising its clock, that's overall cheaper.
> 3 votes

# Answer
So this is actually a very difficult question. It highly depends on the specific system used.

So first we have to clarify some naming issues:

> Reading the book, I've came to understand that there are atleast 2 clocks in the whole system. One is the System Clock which makes one of the lines within the Control Bus go HIGH and LOW periodically. The CPU also has it's own Internal Clock which controls the operations which are done by the CPU. Now the Internal Clock should be in sync with the System Clock for the whole system to make sense which means the control line (which oscillates between low and high) should be connected to the CPU so that both the clock combine and act like a single clock.

As you pointed out these clocks act as a "single" clock. So are these actually different clocks / clock domains? This highly depends on who you ask and with which requirements you look at it.

There are several relations, 2 clocks can be in with each other:

* The same clock. I will identify 2 clocks as the same clock if they have the same frequency, phase etc and are generated by the same clock source. For the designers of the system, these 2 clocks might be differnet becasue these have two separate wires etc. But with a higher perspecitve, they are the same.
* Synchronous clocks. Synchronous clocks must no be generated from the same clock sources but have a fixed phase / frequency relation to each other.
* Asynchronous clocks. The two clocks are generated by different sources that do no share a common reference and do not have a guaranteed fixed phase and frequency relation.
* In reality, even the same clock line will have different clock phases at different points on the wire, due to signal propagation delays. Clocks with the same frequency but unknown phases are called mesochronous.

So even inside a single microchip, the same clock can become mesochronous when routed to different locations with different distances. This is a real problem but I will ignore this in the further discussion.

So starting with the simplest case, there is only a single clock necessary for a computer system to operate. Although if it is used for your CPU, memory etc. and might have different names at specific points in the system, it stays the same clock.

Many simple microcontroller systems, especially small 8 bit controllers, only have a single clock. The CPU, RAM, and all the interfaces run on this clock. This is cheap and easy. And if the system is small enough you don't get severe problems by routing this clock to all places.

I've attached the clock tree of an STM32F4 microcontroller. This is still not a full "computer" like your PC, but looking at it, you can see, it's a mess. I won't go into much detail on how this works but we can observe some interesting things.

The squares on the left represent pyhsical Pins on the microcontroller's package and are used to get clocks in and out of the system. So we can see, that this specific microcontroller which is not bigger than a coin:

already has teh follwoing clock sources:

1. LSE OSC 32.768 kHz. An externally provided clock for real time clock applications
2. HSE OSC 4-26 MHz An externally provided clock which is used to derive most clocks in the system
3. I2S\_CKIN A special clock for the Audio part of the system. Audio application require specific frequencies due to precision reasons or weird sample rates like 44.1 kHz which are not easily dividable from other clocks
4. Ethernet PHY. Most Ethernet applications require a good 100 / 50 / 25 MHz clock
5. USB Phy. Clock for the USB system
6. LSI OSC. An internal 32.768 lHz osciallator
7. HSI OSC. An internal oscillator to provice 16 MHz

Compared to a whole PC, this system is rather small and easy. It is just this small single chip. But it already hass 7 different primary clock sources that "generate clocks out of the blue". Either externally provided, or internally generated.

Usually on-chip clock sources have the advantage of being cheap (no external stuff required) and being available very early on system start. But most ways of generating clocks on a chip are not very precise. Many of these clocks have high temperature drifts and large manufacturing spread. So if a precise clock is required, most chips require an external clock to be provided from e.g. a crystal oscillator that derives its output from the machanical oscillation of an actual crystal.

This is the reason why this chip e.g. has an internal 16 MHz oscillator but also provides a way to feed an external Oscillator. If precision is of secondary concern the internal one can be used to optimize for cost.

Looking further into this system, we can see, that the clock inputs are spread all over the place. I want to move your attention to the PLL blocks. A PLL (Phase Locked Loop) is essentially a fancy way to generate a clock signal dependent on a reference clock. And the fancy thing is, that the generated output clock can have a different frequency than the reference clock. I won't go into details on how this works. There's plenty of explaination on the net on this topic.

So a PLL is a way to generate new clocks based on a reference clock with a specific frequency / pahse relation compared to an reference clock. These PLLs are usally used internally of semiconductors to either achieve variable clocking and/or higher clock frequencies that otherwise would be difficult to route over a board.

Using PLLs and Clock dividers this system uses the input clocks for generating different clocks.

Essentially this system can use a single 16 MHz internal clock generator to provide a 168 MHz CPU clock (via an PLL), an 48 MHz clock for its USB module via another PLL, several lower clocks for its periphjeral modules, like UART, that are divided form the 168 MHz system clock.

As you can see, we only need one clock source to derive several mesochronous clocks from this via PLLs and clock dividers. This is a common practice most moder semiconductors use.

Going back to your question: Essentially there is only a single main clock source needed in a computer system. If different clock frequencies are needed to speed up several parts of the system, these clocks can be generated via PLLs from this base clock. If slower clocks are required, these can be easily divided.

However, different use cases require different clocks with different specification regarding precision and stability.

* All communication, that doesn't transmit the clock, requires somewhat precise clocking as the receiver has to either regenerate the clock from the received data or has its own clock that needs to be as close as possible to the one of the transmitter. This includes all wireless transmission. Most WiFi cards will have an onboard clock gerneration of the 2.4 GHz / 5 GHz clocks used for the modulation. But also other technologies like SATA, Ethernet, USB etc. do not share a common clock between receiver and transmitter and therefore precise generation and/or clock recovery is necessary.
* The DDR memory inside a PC is usually clocked at a different speed than the CPU and most importantly this is not as frequently changed as the CPU clock. Most likely the memory clock is derived via one of the described means from a common clock source as the CPU clock.
* Audio requires special clocks for the specific sample rates that are common. A 192 KHz sample clock is easier to be generated from a 12.288 MHz crystal than from a 8 MHz reference.
* PCIe (usually) uses a 100 MHz reference clock that is send to the cards so they can internally generate a higher clock frequency for PCIe based on this clock. It is generated by the root complex of the PCIe e.g. your CPU or chipset. Providing a reference clock ensures, that all connected devices can generate a clock that is very precise compared to each other but does not need to be absolutely precise.
* Digital video like HDMI, DVI etc. transmits a pixel clock in the cable.
* etc.

As you can see, there are easily several hundreds of differnet clocks in a modern computer system. However, in some cases these hundreds of clocks are only derived from a hand full of primary clock sources.

---

So far we only looked at how many clocks there are in a system. And we came to the conclusion: A ton... So how are these synchronized:

This highly depends on the relationship of the different clocks.

* If carefully designed synchronous clocks of the same frequency do not require any synchronization at all.
* A slower clock that trasnmits data to a faster clock with a fixed clock and phase ratio (derived from the same reference using a PLL) might also not need a synchronization, as the faster clock is capable of processing all data coming from the slower clock and the cahnges of the source clock domain are guaranteed not to violate the setup and hold requirements of the flip flops in the destination domain due to the fixed phase and frequency relationship.

Problems arise when the clocks are asynchronous or mesosynchronous. As you've pointed out, these can run "out of sync" with each other. So a special clock domain crossing mechanism needs to be installed. There are several ways of ensuring this. I recommend searching the net regarding clock domain crossing (CDC) and synchroinization. The short answer is: All clock domain crossings require the synchronization of the signals into the destination clock. This is usually done by using 2 or more Flip-Flops clocked by the destination clock to sample the input signals.

For one bit wide signals this is already sufficient. Of course you would have to ensure by design that the signal is held stable in the source domain for long enough so that the target domain is able to capture it. This is especially problematic going from faster to slower clocks.

However, if multiple signals e.g a data bus needs to cross a clock domain, the signals cannot be simply synchronized bit by bit, as differnet routing delays and flip flop manufacturing tolerances etc. can lead to wrong sampling of the value in the destination clock domain if sampled right at the change.

One way of circumventing this is to proved the data in the source clock domain and toggle a qualifier signal. The data is synchronized by a signle flip flop in the destination domain and the qualifier signal is synchronized by 2 or more flip flops in the destination. Therefore, it is ensured, that once the toggling qualifier signal is fully synchronized into the destination domain, the data is also synchronized. Data and qulaifier need to be stbale during this process. Either by a fixed timing or by providing a feedback signal from the destination to the source.

As you can see, clock domain crossing is

1. Complex
2. Requires time -\> Can actually severely impact performance and latencies
3. Is notoriously difficult to debug in anything goes wrong. Therefore, special care needs to be given when designing these crossings, so that they are functional.
> 3 votes

# Answer
The description is hopelessly outdated. For instance, "*the* Control Bus" ? I wouldn't even know what bus that would be. It's apparently not the "Internal Clock", so presumably "the Control Bus" is the external bus. Problem: modern CPU's don't have a single external bus. And it's not like each external bus has its own clock: modern high-speed parallel buses have a different clock *per data line* !

Yet another flawed assumption in your text there: that clock is in-band, not an extra pin. That would be too expensive, having one extra clock pin per data pin. Besides, that wouldn't work anyway. The reason to do clocking in-band is to eliminate the variation between pins.

As for the internal clock, a modern CPU may not even have a fixed number (!). Commonly, each core of a multi-core CPU can have its own clock, but an unneeded core may have its clock shut down to reduce energy consumption.

Of course, with those multiple cores, there has to be yet another bus to connect the cores on a CPU, and that too has a clock. This one can be especially funny: due to the limited speed of light, this clock can be both 0 and 1 at the same time, at different parts of the chip. Of course, half a clocktick later, it will be the other way around, so 1 and 0. The internal bus can have phase differences over its length.

You mention the 8086 and 80486. These are old chips. The increase in speed of modern CPU's is possible because of this added complexity. All those different clock domains prevent the fast parts from being slowed down by the rest of the system. Having 2 clocks, internal and external was just a first step, but today we can even use multiple clocks per bus.
> 0 votes

# Answer
If I am correct about your query then there are some of the links which I mentioned below that may help you to understand the procedure. But to make better understanding approach should not be how it is working the approach should be how it could possibly work.

Lets check with the first approach.

If you read some open documents of MCH you will see the PCI works on separate clock and FSB works on separate clock. Think of all the components working in the system works on different clock rate, the word synchronized doesnt mean that "If I say yes, at the same time you also say Yes", indeed it means things happenning at the rising edge of the clock. Now all the components such as circuits deal with busses like PCI, circuits deal with interrupt system and control unit itself has different clocks. One approach is in order to intercommunicate between the components the approach should be based on the handshaking signals. Lets suppose components X1 is the main component that deal with internal processing and component X2 is the component that deals with only ISA or I2C bus. Now data recieved by X2 should go to processing through X1, what handshaking signals required. The hypothetical approach is:-

1 X2 notification that he has the data to X1 2 X1 acknowledge and ask to share the data 3 X2 start sending the data by keeping another signal ON to tell the X1 that data is on the bus (Just like in RAM we have the concept of RAS and CAS signals) 4 Once the data is completed by X2 it sends complete signal 5. And X1 acknowledge

Second approach I read on the MP book for x86, based on my understanding.

There is separate clock generated circuit in the computer that sends the clock to the processor and to the system, This circuit is tunned by a variable for example 2Y is the clock frequency on which the computer processor work and processor and clock generator is designed in such a way that 2Y gives to the processor and processor is made aware that it receives the multiple of Y clock frequency like "2" in this case and the board designer (An important person) should know that Y is enough frequency for the operation of every component mentioned on the board, thats why when he send the board for selling in the Market he mentioned the list of specifications for the compatibility.

Third approach is my own idea where the system components have one controller and each controller has two clocks one that is running its part and the other for which it is communicating upstream with the single reference clock

Moreover if we study pentium structure there is one pin which is known as cache miss and also if you study X86 you will see one pin known as Data ready, such kind of implementation is done that if an environment comes where sync-synchronized (The idea of perfect matching) not be the option (Board designer person decision) then create the wait states until the data is reliably received.

Below are some links that might help you. Also search ***clock domain crossing protocols***

https://en.wikipedia.org/wiki/Clock\_synchronization http://paginas.fe.up.pt/~ee12248/Dissertation/wp-content/uploads/2015/03/PDI\_ee12248.pdf
> 0 votes

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


# Question
Title: Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?
Edit: Since this post is gaining traction, I feel the need to clarify that the purpose of this is to see if asymptotic and constant factor estimations calculated from high level code implementations of algorithms are reasonable approximations of the true version. **I am not trying to predict the speed of code when running**.

---

Suppose I have some sequence of code $C$ in a high level language (C++, Python, Java, etc.) which needs to be converted into machine code which we will call $M$. Obviously machine code varies from system to system, so assume we are on a fixed machine

Under a uniform cost model, we can say that every instruction of $M$ costs $1$ operation, so we can calculate the complexity of our code as some function of the input size of our problem $n$. Let an upper bound of this function be $f\_M(n)$.

Clearly, nobody writes in machine code, so we can *approximate* $f\_M(n)$ by counting operations of our high level language code $C$, which we can say $f\_C(n)$

Define $1$ operation of $C$ to be the following

```
1. Function Calls
2. Returning
3. Arithmetic Operators
4. Logical Operators
5. Comparisons
6. Pointer/Object dereferencing/Array indexing
7. Variable Assignment

```

This list is heuristic, and was given to me as a means of approximating by an engineer mentor, so if a better heuristic exists please let me know.

---

Questions: Given $f\_C(n)$, are we guaranteed any of the following, assuming the code is compiled in "good faith" (no additional logic added to insert unnecessary operations)

1. Does $f\_C(n)\in \mathcal{O}(g(n))$ imply $f\_M(n)\in \mathcal{O}(g(n))$?
2. Does there exist a constant factor such that $f\_M(n)\leq c\cdot f\_C(n)$? for sufficiently large $n$?

# Answer
> 6 votes
Yes, this is reasonable as a first cut approximation. As always, there are caveats.

A theoretical model is a model. It is used for making predictions, but models typically are not perfect, and there are some factors that they don't take into account.

I'm not sure what you mean by function calls, but some functions might take a very long time to execute, so a single function call might take a very long time, unless you are also careful to count all of the operations that are done by the function you are calling. So I will assume that you are also counting the time to execute the body of every function that is called, otherwise there is a major flaw.

This does not take into account the effect of memory hierarchy. For instance, random access memory lookups might be noticeably slower than sequential memory access, because of cache effects. This is not taken into account by the model you articulate -- partly because it is very challenging to model.

If you are concerned with practical running times, there are no guarantees. A single memory access could cause a page fault (e.g., if there is thrashing due to memory pressure) and loading data from disk, which a long time, compared to executing a single instruction.

# Answer
> 2 votes
The answer actually depends on the how many machine operations are utilized by an operation of the high-level language. If each operation of $C$ takes a constant machine operations, then the answer to your questions is *yes*.

However, you can design a high level language that implements a multiplication using addition. So multiplying two integers $2$ and $n$ with input size $\log(n)$ could actually take expoenential time $2^{\log n}$.

# Answer
> 2 votes
The whole story of complexity evaluations is that you count the operations that execute in *bounded* time (they also say in $O(1)$). Whether you consider a high-level language or concrete machine language, the costs need not be unit nor even constant (independent of the values of the arguments), this does not matter: as long as you don't involve operations that themselves have a dependency on $n$, the asymptotic complexities in any model are equivalent.

Now when you translate from one language to another, a single operation in one model translates to a bounded number of operations in the other. E.g. a multiply & add opcode that translates to one multiply and one add, no more. So when computing the overall complexity, if you collect the terms with the dominant asymptotic complexity, you get $\le c\_0f(n)$ in one case, and $\le c\_1f(n)$ in the other. The relation between $c\_0$ and $c\_1$ depends on the respective times of the elementary operations and the ratio of their counts across the translation. And we just don't care about this relation.

---

In practice, it is overkill to accurately count every operation, such as giving a weight to *call* or *return*. What you do is to select a representative operation (such as a comparison or a data move) *such that the number of other operations is of the same order*.

E.g. if you look at bubble sort, every time you perform a comparison, you perform zero (no swap) or three moves (swap), and no other operation (loop control) is performed more often.

---

The answer to 1 is true. In principle 2 is false, because all we know is

$$f\_M\le c\_M\cdot g(n)\land f\_C\le c\_C\cdot g(n).$$

But in reality, the ratio of the constants cannot be as large as one wants and the following bracketing will hold:

$$c\_0\cdot f\_M(n)\le f\_C(n)\le c\_1\cdot f\_M(n).$$

This reflects the fact that one operation corresponds to a bounded number in the translation.

# Answer
> 1 votes
One kind of high-level operations that may not translate to constant-time machgine code are memory management operations, such as alloc/free or new/delete.

There are allocators with constant-time operations for constrained conditions (e.g. fixed block allocators, the stack), but for a general allocator *some* operation is nonconstant (search for a free block, update free block set/list/X on deletion, compaction, etc.).

# Answer
> 1 votes
There is asymptotic behaviour, and there is real time measurements. Asymptotic behaviour tells you how the time that your algorithm takes will grow as your problem size grows, assuming operations take constant speed. Things like adding, subtracting, multiplying, dividing will take constant speed, if the operands have a fixed size. One trillion divisions will take a million times longer than a million divisions. On the other hand, I have a computer now with 8 cores running at about 3GHz each, and doing multiple operations per processor cycle. In 1984 I had a computer running at 8 MHz and taking multiple cycles for each operation. There is a huge speed difference, which isn't accounted for by asymptotic behaviour at all. So asymptotic behaviour isn't everything.

Now accessing memory is tricky, and your "constant factor" assumption falls apart. Some values are stored in registers and can be accessed super fast. Some values are in L1 cache and can be accessed very fast, then you have slower L2 cache, some machines have an even slower L3 cache, then comes slow RAM, then even slower memory that is handled by a different core, and then virtual memory which is an awful lot slower. And then you reach a limit where currently you cannot access more memory. Big-O assumes that your problem size can be large beyond any limit. And you can't have that on a real machine.

# Answer
> 0 votes
I think that the whole approach is flawed. Modern compilers and computers are way to complex for that.

What you should do: Implement the code, measure the speed with good benchmarking software for a large variety of input values.

Analyse the result with statistics software. You will see if the runtime is linear, quadratic, exponential (or something else) in the data.

---
Tags: complexity-theory, time-complexity, asymptotics, compilers
---


# Question
Title: Requirements to a CPU architecture to actually allow a C compiler to be built for it
I have this rather weird CPU architecture for which currently only an assembler exists. I won't go into too much details about this architecture as it is not publicly available. However, some quirks of it are:

* It can only address full 32 bit words in memory
* No shift operations
* No internal registers. It fully operates on the system memory for each access.
* No multiplication / division in hardware
* No indirect jumps
* No calls (subroutines with returns to the jumped of address) at all.

The question of writing a C compiler for this thing came up.

As far as I see, the first point of only being able to access full 32 bit words shouldn't be a problem because I could simply define a 'char' as 32 bits wide, which should be valid, weird but valid.

Missing multiplication / division / shift operations can be constructed from additions and subtractions. So this seems possible as well.

So this actually got me thinking: "What are the requirements to an architecture so that it is actually possible to write a C compiler for it?"

I'm an electrical engineer with a strong background on CPU architectures and C programming. However, I'm not too much into theoretical CS. So an easy formulated answer is highly appreciated (if possible).

# Answer
I cannot provide an authoritative answer, but, besides key arithmetic support missing, this machine is lacking a stack mechanism, which precludes the implementation of function calls. These can be emulated by inlining, to a very limited extent, but that cannot decently be called C anymore.

---

**Update:**

The missing arithmetic operations can be implemented with decent efficiency using addition, subtraction and bitwise masking. Even floating-point can be implemented.

As said in the comments below, indirect addressing can be used to implement a stack, and indirect jumps to labels can be emulated efficiently.

So the set of missing features is vanishing...
> 2 votes

---
Tags: computer-architecture, compilers, c
---


# Question
Title: Sympy does not recognise when two partial derivatives happen to be equal
I am trying to find the first and second-order partial derivatives of a function of four variables $S$ using pythons symbolic math package sympy.

The issue is that sympy does not automatically see that certain pairs of partial derivatives, **when evaluated at the same arguments**, are in fact equal, and so cancellations do not occur. For example: $$\frac{\partial S(x,y,u,v)}{\partial x}=\frac{\partial S(u,v,x,y)}{\partial u} \text{ when } x=u \text{ and } y=u.$$ You can see that in each case the functions are differentiated w.r.t their first arguments (x, u respectively) and that afterwards each partial derivative is evaluated at (x,y,x,y).

However, the code below returns `False`:

`sympy.diff(S(x, y, u, v), x).subs({u: x, v: y}) == sympy.diff(S(u, v, x, y), u).subs({u: x, v: y})`

Any help is appreciated!

# Answer
I think you should substitute before differentiating:

`sympy.diff(S(x, y, u, v).subs({u: x, v: y}), x) == sympy.diff(S(u, v, x, y).subs({u: x, v: y}), u)`
> 0 votes

---
Tags: python
---


# Question
Title: Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)
The following excerpt is from page 39 of the 4th edition of *'Introduction to Algorithms'* (emphasis added):

> 2.3.2 Analyzing divide-and-conquer algorithms
>
> \[...\]
>
> A recurrence for the running time of a divide-and-conquer algorithm falls out from the three steps of the basic method. As we did for insertion sort, let $T(n)$ be the worst-case running time on a problem of size $n$. If the problem size is small enough, say $n \leq n\_0$ for some constant $n\_0 \> 0$, the **straightforward solution** takes constant time, which we write as $\Theta(1)$.

(I was not able to find a Google Books preview of §2.3.2, but the 3rd edition version of the section can be found here.)

I'm a little confused as to what "straightforward solution" is referring to. I initially thought it was the base case, but can't be sure (why didn't the authors just use the term "base case"?).

My lecture slides also seem to think the authors are referring to the base case, but use the term "brute-force solution" in place of "straightforward solution". Here's the text from the relevant slide (emphasis added):

> $T(n)$ = running time on a problem of size $n$ If a problem is small enough (say, $n \leq c$ for some constant $c$), we have a base case. The **brute-force solution** takes constant time: $\Theta(1)$.

* What exactly are the terms *"straightforward solution"* and *"brute-force solution"* referring to?
* If they are referring to the base case, how can we be sure that the base case will take $\Theta(1)$ time? Is it possible for the base case to be non-trivial so that we spend a non-constant amount of time in it?

# Answer
> 0 votes
Yes, "straightforward solution" refers to the base case (and also "brute-force solution" on your slides). You need at least one base case (there could be more than one in some cases), otherwise recursion never ends and your recurrence equation is wrong. Now, the base case is often assumed to require $O(1)$ (constant time), since it is associate to a very small - actually a constant - number of elements (or objects, items etc). Think about a sorting algorithm designed using divide and conquer. Le $n$ be the size of the array in one recursive invocation. Two possible base cases may be $n=1$ (because if your array only includes one element, then it is already sorted) and $n=2$ (because for two elements one comparison is enough to establish the correct sorted order).

# Answer
> 0 votes
The *straightforward* solution is an easy but possibly inefficient solution, such as the one you can design for a small number of elements (e.g. sorting 1, 2 or 3 elements).

The *brute-force* solution is a particular case of straightforward solution, which tries all possibilities without caring for efficiency (for instance trying all permutations until you get an increasing sequence).

If these solutions are used to solve the cases $n\<n\_0$, then they indeed correspond to the base case of the recurrence. As $n\_0$ is a constant, the running time for $n\<n\_0$is perforce bounded, i.e. constant in the asymptotic sense.

E.g. real-world implementations of Quicksort often switch to StraightSelection or similar for $n\<10$ (say). But you may not conclude that the complexity is $O(n^2)$ because $n\<10$; the complexity is constant, bounded by $T\_{\text{StraightSelection}}(10)$.

---

One might think of cases such that we use divide & conquer down to some $n\_0$ that is a function of the initial $n$, then switch to a straightforward solution. In this case, the complexity associated to the straightforward solution would not be a constant, though it can still be the base case. But honestly, I have never met such a construction.

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


title: Simultaneous reachability of NFA states

text:
# Question
Title: Simultaneous reachability of NFA states
Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$.

I am interested for a given NFA to compute a $n \times n$ *simultaneous reachability matrix* $R$, such that $R\_{ij} = \[\exists x : \\{i, j\\} \subseteq S(x)\]$.

From NFA product construction of $F$ with itself and then checking the reachability from the starting state I can compute $R$ in $O(n^4 \cdot |\Sigma|)$ time. Is there a better algorithm?

# Answer
> 0 votes
The Floyd-Warshall algorithm is typically used for computing the transitive closure of a directed graph, which is similar to finding the simultaneous reachability matrix in an NFA.

The time complexity of the Floyd-Warshall algorithm is (^3⋅|Σ|), which is an improvement over the (^4⋅|Σ|) complexity of the NFA product construction approach.

---
Tags: time-complexity, finite-automata, nondeterminism
---


# Question
Title: Finding the mode of a continuous distribution
I need to find the empirical mode of a sample of numbers taken from a continuous distribution (i.e. floating-point data).

I can think of using an histogram, but choosing an appropriate bin size does not seem so easy. I could also count the values in a sliding Parzen window, but again, which window size ? I could also compare the local densities (width of the intervals containing M consecutive values). But which M ?

My question: do you know a classical procedure to estimate the mode in such a case ? Alternatively, is there a robust answer to the "sizes" question ?

# Answer
> 0 votes
I don't think the question is answerable without more context. If you observe a list of $n$ values $x\_i$, there are multiple distributions that are consistent with the observed values, each with different modes. You would need to define what you mean by "the empirical mode" in this context.

For a discrete r.v., we can ask for the maximum likelihood distribution (i.e., the distribution that assigns the highest possible likelihood to the observed values). For a continuous r.v., this is no longer meaningful. The distribution that gives the highest possible likelihood will be a discrete distribution that only takes non-zero probability at the values that appear in the sample, but this is almost certainly not what you are looking for.

My guess would be that, most likely, you have some prior on the possible distribution, and then a Bayesian analysis may be possible, but it's hard to know without knowing more specifics. A general approach to Bayesian analysis would be to model the (unknown) probability distribution as given by the pdf $f\_\theta(\cdot)$ where $\theta$ is an unknown function, with some prior $p(\theta)$ on the distribution of the unknown parameter $\theta$. Let $m$ denote the mode and $x=(x\_1,\dots,x\_n)$ the denote the finite sample. Then our Bayesian estimate for the mode is

$$\begin{align\*} \mathbb{E}\[m|x\] &= \int\_\theta m(f\_\theta) p(\theta|x) \\; d\theta\\ &= {\int\_\theta m(f\_\theta) f\_\theta(x\_1) \cdots f\_\theta(x\_n) p(\theta) \\; d\theta \over \int\_\theta f\_\theta(x\_1) \cdots f\_\theta(x\_n) p(\theta) \\; d\theta} \end{align\*}$$

where $m(f\_\theta)$ denotes the mode of the distribution with pdf $f\_\theta$. Whether you can compute (or approximate) those integrals depends on the parametrization of possible continuous distributions for the samples and the prior on the parameters $\theta$.

A crude approximation to this Bayesian estimate is to find $\theta^\*$ that maximizes the value of $f\_{\theta^\*}(x\_1) \cdots f\_{\theta^\*}(x\_n) p(\theta^\*)$, and then use $m(f\_{\theta^\*})$ as your estimate of the mode. If you have a uniform prior on $\theta$, this basically amounts to asking for the maximum likelihood distribution. Whether you can solve this optimization problem and thus compute this approximation again depends on your parametrization and prior.

---
Tags: algorithms, statistics
---


# Question
Title: Is there a data structure for lazy-loading time-series data?
I am writing a UI that needs to display a chat log, similar to Slack and Discord. In addition to being able to scroll and lazy-fetch additional pages in either direction, I need to be able to jump to a specific point in time and fetch the message records "around" it (a backend API problem, of course).

I need a "lazy range" data structure that can store "intervals" (each with bounds and an ordered list of items), respond to queries for "more before" or "more after" including items and some kind of indication of gaps, and insert new intervals (pages fetched from the backend), merging existing intervals when overlaps are detected and eliminating the gap indicator.

I have not been able to find an existing named data structure that handles this kind of access pattern. It seems similar to a range tree but has only a single level of interval nodes, and it is similar to an interval tree in that we want to detect bound overlaps/gaps, but then we want to merge overlaps. Does such a data structure already exist?

# Answer
> 1 votes
The binary search tree of @dw seems a good solution.

For something simpler, if the time density of messages is homogeneous, you can consider successive time intervals of a well-chosen fixed duration and associate to every interval the doubly-linked list of events that occurred, in chronological order. The intervals are stored in an array.

From the current event, you can move forward or backward, and switch to the next/previous interval easily. For random access, just find the relevant interval.

The duration should be such that a single interval roughly corresponds to the size of the scrolled area.

---

If your data structure is external (on disk), a B-tree indexed on the timestamp is appropriate.

# Answer
> 0 votes
I find it hard to understand your requirements, but I suspect a balanced binary search tree might meet your needs. I assume each record is associated with a timestamp, and you want to support queries like "find the record nearest time $t$", "find the 50 records immediately preceding time $t$", "find the $i$th record", and so on.

All of those can be handled in $O(\log n)$ time with a balanced binary search tree.

I am assuming here that each record represents a single chat message, and so has a single timestamp associated with it, and that a page is simply a window of consecutive records.

---
Tags: data-structures, intervals, abstract-data-types, range-query
---


# Question
Title: Given a GapP function can I assume there is an "optimal" function that solves it?
What I mean by this, is let $f \in GapP$, and let $k\_n =min\\{k|\forall x (s.t. |x|\<n):2^k \> |f(x)|\\}$ for every $n$, can I assume there is a nondetermenistic machine $M$ that on input $x$ does at most $k\_n$ coin tosses with results in $\\{0, 1\\}$, and that for every $x$: $f(x)=\\#(M(x)=1) - \\#(M(x)=0)$, where $\\#(M(x)=a)$ means the amount of passes of $M$ on input $x$ for which it returns $a$?

# Answer
> 0 votes
I don't have a complete answer, but it is actually easy to show that if it were true then we'd get $AWPP ⊂ BPP$, so I guess no we can't assume this. To prove this, let $L \in AWPP$, then there are $f \in GapP$ and $g \in FP$ s.t.: $x\in L =\> 2/3\<f(x)/g(1^{|x|})\<1$ and $x\notin L =\> 0 \<f(x)/g(1^{|x|})\<1/3$, but becasue of the assumption we know there is a machine $M$, that does at most $log (g(1^{|x|}))$ coin tosses and satisfies $f(x)=\\#(M(x)=1)-\\#(M(x)=0)$, so that means that $2\*Pr\[M(x)=1\]-1=f(x)/g(1^{|x|})$ and so that proves $L \in BPP$

---
Tags: complexity-theory
---


# Question
Title: Finding asymptotically tight upper bound of a recursion relation
> Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$

I tried to solve it by applying iteration: $$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{5^2})+\log^2(\frac{n}{5}))=\ldots=5^kT(\frac{n}{5^k})+\sum\_{i=0}^{k-1}5^i\log^2(\frac{n}{5^i})$$ Now letting $5^k=n$, we have that $k=\log\_5(n)$. Hence the last equality becomes: $$n\cdot T(1)+\sum\_{i=1}^{\log\_5(n)-1}5^i\log^2(\frac{n}{5^i})\stackrel{\*}{\leq} n\cdot T(1)+\log^2(n)\sum\_{i=0}^{\log\_5(n)-1}5^i=n+\log^2(n)\cdot\frac{5^{\log\_5(n))}-1}{4} =n+\frac{\log^2(n)(n-1)}{4}$$

Hence $T(n)=O(n\log^2(n))$. However, I'm not sure this is the correct answer. Is the bound I took in the step marked by $\*$ not tight enough? Any help would be appreciated.

# Answer
Your upper bound is not tight. Let $n=5^k$, as in you question. You can upper bound your summation by $$ \sum\_{i=1}^{k} 5^i \cdot \log^2 5^{k-i} \le 6 \sum\_{i=1}^{k} 5^i (k-i)^2 = 6 \cdot 5^{k} \sum\_{i=0}^{k-1} \frac{i^2}{5^i} = 5^k \cdot O(1), $$ where the last equality follows from the fact that the series converges to some positive constant. Indeed, by the ratio test: $$ \lim\_{i \to \infty} \frac{(i+1)^2}{5^{i+1}} \cdot \frac{5^i}{i^2} = \lim\_{i \to \infty} \frac{i^2+2i+1}{5 i^2} = \frac{1}{5}. $$

This shows that $T(n) = O(n)$, which is tight. To prove that formally you also need to show a lower bound of $\Omega(n)$, which is easy using similar calculations.

You can also easily get a tight upper bound by a direct application of the master theorem.
> 2 votes

# Answer
Given, $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ compare with $$T(n)=aT(\frac{n}{b})+n^k\log^p(n)$$(By master theorem) where $a\geq1,b\>1,k\geq 0$ and $p \in \mathbb{R}.$

Since $a\> b^k$, $T(n) =\Theta(n^{\log\_{b}a})$ which is $\Theta(n).$
> 1 votes

---
Tags: computability, asymptotics, runtime-analysis, recursion, upper-bound
---


# Question
Title: Minimal set of elements needed to satisfy property counts
I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain sufficient instances of specific orthographic properties (at least 5 2-syllable words, 3 closed syllables, etc.).

I've formalized the problem of generating these word lists as follows:

> Given:
>
> * $ A = \\{ p\_1, p\_2, \dots, p\_m\\}$, the set of all possible distinct properties
> * $\\{ w\_1, w\_2, \dots, w\_n\\}$, the set of all possible distinct words
> * $ P\_1, P\_2, \dots, P\_n\ $ corresponding property multisets, such that $P\_i$ is the multiset of the non-unique properties $\\{ p\ |\ p \in A\\} $ in word $w\_i$. Thus, if $P\_i$ contains $p\_j$ with multiplicity $k$, then $w\_i$ has $k$ instances of the property $p\_j$.
> * A requirements multiset $R = \\{ p\ |\ p \in A\\} $ of non-unique properties that must appear in the word list
>
> Determine the minimal set of unique words $S=\\{ w\_a,w\_b,\dots \\}$ with the property multisets $P\_S=\\{ P\_a,P\_b,\dots \\}$ such that if the requirements multiset $R$ contains $p\_i$ with multiplicity $k$, then the union of the solution words' property multisets $\bigcup P\_S$ contains $p\_i$ with multiplicity $\geq k$.

One example instance and solution to this problem would be as follows:

> Given:
>
> * $A={p\_1, p\_2, p\_3, p\_4}$
> * All possible words $w\_1, w\_2, w\_3$
> * Word property multisets $P\_1=\\{p\_1, p\_2, p\_2, p\_3\\}$, $P\_2=\\{p\_2, p\_3, p\_4\\}$, and $P\_3=\\{p\_1, p\_1, p\_1, p\_2\\}$
> * Requirements multiset $R=\\{p\_1, p\_1, p\_2, p\_2, p\_3, p\_4\\}$
>
> Solution:
>
> The set of words $\boxed{S=\\{w\_2, w\_3\\}}$, which happen to have the property multisets $P\_S=\\{P\_2, P\_3\\}=\\{\\{p\_2, p\_3, p\_4\\}, \\{p\_1, p\_1, p\_1, p\_2\\}\\}$.
>
> Note that $R$ contains $p\_1$ and $p\_2$ with multiplicity 2, and $p\_3$ and $p\_4$ with multiplicity 1. Also note that $\bigcup P\_S=\\{p\_1, p\_1, p\_1, p\_2, p\_2, p\_3, p\_4\\}$, and thus $P\_S$ always contains at least as many copies of any given property as $R$: $p\_1$ with multiplicity $3\geq 2$, $p\_2$ with multiplicity $2\geq2$, and $p\_3$ and $p\_4$ with multiplicity $1\geq1$. $P\_S$ therefore satisfies all property requirements in $R$, and thus $S$ represents a word list with all the required properties.
>
> Examining the other possible solutions, we determine that any solution set which satisfies all the property requirements in $R$ must contain at least $w\_2$ and $w\_3$, and thus $P\_S$ is minimal. It is therefore the true solution.

So far I've tried greedily sorting words by most properties satisfied (but found many counterexamples) and I'm currently working on a dynamic programming attempt. I've only taken one semester of algorithms though, and I feel like something similar to this problem would appear in a textbook. Any pointers on creating an algorithm or a reduction to some more common problem (constraint satisfaction?) would be greatly appreciated.

I think this problem is superficially similar to this assignment problem, but I'm not sure if the solution could be adapted. This is also my first post, so feel free to tell me to post this differently/somewhere else!

# Answer
> 1 votes
The problem is known as Multi-set Multi-cover problem. Since you are choosing a $P\_i$ at most once, you can use the dynamic programming based algorithm given in Section 5 of the paper.

---
Tags: algorithms, dynamic-programming, constraint-satisfaction, set-cover
---


title: What circuit depth is required to add?

text:
# Question
Title: What circuit depth is required to add?
If we suppose that we are given two numbers $a$ and $b$ to add, what circuit depth do we require to add them?

I'm wondering if $a$ and $b$ are $O(n)$, and thus the amount of bits required to store $a$ and $b$ are $O(\log\_2(n))$, how much time and/or space we must require to add them.

I'm interested in the general case. However, I am wondering if there is anything else to be said about the case of adding $a+2a+1$. It would be spectacular if we could do this addition in constant circuit depth.

# Answer
To add two $n$-bit numbers, you need a circuit of depth $\Omega(\lg n)$. Depth $O(\lg n)$ is also achievable, so the lower bound is tight.

There are many examples of such circuits; for instance, a carry lookahead adder has depth $O(\lg n)$ (and size $O(n)$). One can even achieve depth $\lg n + o(\lg n)$; for instance, a Krapchenko adder has depth $\lg n + O(\lg^{1/2} n)$ (and size $O(n)$).

This all assumes bounded fan-in gates, as usual. If you allow AND and OR gates with arbitrary fan-in, then you can achieve constant depth (depth 3, I think). See, e.g., https://en.wikipedia.org/wiki/AC0.
> 5 votes

# Answer
If unbounded fan-in is allowed, depth $1$ is sufficient.

See Page $11$ (Theorem $1.15$) and Page $12$ (Corollary $1.18$) of Herbert Vollmer's book on Circuit Complexity.
> 1 votes

# Answer
We assume that the logic gates are bounded to having two inputs (as opposed to unbounded fan-in gates, with which addition can be done in constant depth by implementing the Conjunctive Normal Form for each bit in the result of the addition). We also assume the standard binary encoding of numbers.

Note that the most significant bit of the result in addition depends on some computation involving at least $n-1$ bits (we need to check that all $n-1$ carries occur in this addition). Thus we need a circuit of depth $\Omega(\log n)$ just to compute some single bit valued function on these $n$ bits, since each time step or depth level in the circuit can only half the number of bits present in it compared to the level above it.
> 0 votes

---
Tags: circuits, binary-arithmetic
---


# Question
Title: When does Quicksort go from O(n log n) to O(n^2)?
Quicksort is O(n log n) average case, and O(n^2) worst case. The worst case occurs if one side of the pivot contains all of the elements and the other side contains none. However, I think the worst case would also occur if there is only one element on one side of the pivot each time and the rest on the other side. Is there a point, i.e. a factor of how unbalanced one side is compared to the other, where Quicksort goes from O(n^2) to O(n log n)?

# Answer
> 1 votes
> However, I think the worst case would also occur if there is only one element on one side of the pivot each time and the rest on the other side.

Yes, however..

> Is there a point, i.e. a factor of how unbalanced one side is compared to the other

When expressed as a factor, the point where it becomes quadratic is "only when completely unbalanced". Even if the partitions are 0.1% vs 99.9%, quicksort is still in $O(n \log n)$-land. What changes is how big $n$ needs to be before the scaling starts to look noticeably less than quadratic, but that point will come for some sufficiently large $n$, so in terms of big O nothing changes. Such cases can still be considered pathological in practice.

Recall the Akra-Bazzi method. Given some recursive definition of $T(x)$ of this form (with some restrictions that I won't repeat here):

$$T(x) = g(x) + \sum\_{i=1}^{k} a\_iT(b\_i x + h\_i(x)) $$

So $g(x) = x$, $k = 2$, $a\_i = 1$, and $b\_1$ and $b\_2$ represent the "split" between the two sides of the partition. Let's ignore $h\_i$ this time.

The Akra–Bazzi method ask us to find a $p$ such that $\sum\_{i=1}^{k} a\_ib\_i^p = 1 $, and since the b's add up to 1, $p = 1$.

Aside from $p$, the solution given by Akra-Bazzi does not depend on the specific values that the b's have. They're not in the formula:

$$T(x) \in \Theta(x^p (1 + \int\_1^x \frac{g(u)}{u^{p+1}}du)) $$

The solution here is always $T(x) \in \Theta(x \log x)$, unless one of the b's is 0 and the other is 1. Staring at this formula it is not obvious why it would break, but Akra-Bazzi requires the b's to be strictly between 0 and 1, excluding those endpoints.

# Answer
> 0 votes
There is no precise answer to this question. For a given $n$, the running time of Quicksort follows a statistical distribution with nonzero probabilities in $\[\Theta(n\log n),\Theta(n^2)\]$, but the exact distribution depends on the distribution of the input.

In the case of equiprobable permutations of the input numbers, the distribution remains concentrated around $\Theta(n\log n)$, and in the case of nearly sorted sequences, more around $\Theta(n^2)$, with a larger spread. But you could design distributions that result in intermediate expected complexities such as $\Theta(n^{3/2})$, if you wanted.

Last remarks: if you stick to input distributions such that all partitions are unevenly balanced but with a constant *ratio*, then the behavior is still $\Theta(n\log n)$, with an asymptotic constant that grows for ratios moving away from $\frac12$. For higher complexities, the partitions must get more imbalanced than proportionally.

---
Tags: algorithms, asymptotics, big-o-notation
---


# Question
Title: TMs can decide whether or not a string is a Palindrome, yet, the language called PALINDROMES is undecidable - why?
I came across this language, where M denotes a Turing Machine:

PALINDROMES $:= \\{M \mid M \text{ accepts strings which are palindromes}\\}.$ It is proven to undecidable.

And, I know one can construct a Turing Machine that decides for strings, if they are palindromes or not.

Further, a set A is decidable if and only if there exists a computable function $f(x) : Σ^\* \to \\{0, 1\\}$ such that for any input $x \in Σ^\*$, $f(x) = 1$ if $x$ is in $A$, and $f(x) = 0$ if $x$ is not in $A$.

In other words:

$$A \text{ is decidable } \Leftrightarrow \exists f(x) : Σ^\* \to \\{0, 1\\}\text{, where }f(x)\text{ is computable and}$$

$$f(x) = 1\text{ if }x \in A\ ,$$

$$f(x) = 0\text{ if }x \not\in A\ .$$

How come then, that the existence of a TM that decides whether or not a given string is a palindrome is not sufficient condition to say, that the language PALINDROMES decidable?

Basically, i try to make out the source of my confusion. Do I confuse the "language of palindromes" and "the language of Turing machines that accept palindromes"(PALINDROMES)?

# Answer
> 0 votes
Yes, you are right, you are confusing the two languages.

You know that, via "gödelization", you can associate to every Turing machine $M$ a number $\lceil M \rceil$ in bijective way (this can be done in multiple way, but you can fix one of this way, for example using a binary alphabet and fixing the rules coherently).

Consider the machine $M$ that recognize the set of palindromes: what can you say about its Gödel number $\lceil M \rceil$? Probably not much; for sure there is no reason for this number to be a palindrome in base 2.

The fact that the set PALINDROMES is not decidable, while the set of binary palindrome strings is, has this implication: there's no gödelization such that a Turing machine recognizes the set of binary palindrome if and only if its Gödel number is a palindrome.

Another example: the set of even number is recognizable, while the set of Turing machine that recognize all the even numbers is not: this implies that, for every gödelization, there are two Turing machine $M$ and $M'$ that recognize the set of even numbers such that $\lceil M \rceil$ is even and $\lceil M' \rceil$ is odd.

---
Tags: turing-machines, computability, undecidability, decidability
---


# Question
Title: fault-tolerant K-median problem on an undirected graph
We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$:

We are given a set of facilities $F\subseteq V$ and a set of demands (or clients) $D\subset V$ in a metric space. We can open at most $k$ facilities and then assign each client $j$ to the $r\_j \geq 1$ facility. Assigning demand $j$ to facility $i$ incurs an assignment cost of $d(i, j)$, where $d(i, j)$ is the shortest path between $i$ and $j$. Our goal is to minimize the sum of the assignment costs for all clients.

If $r\_j$ is uniform, e.g. $r\_j=3$ for all clients, each client should be connected to three facilities. Why the below algorithm does not solve the problem in polynomial time; let's assume $r\_j =3$.

1. Go through all the vertices in $F$
    * For each $v \in F$ Calculate the sum of the distance to all clients $D$
    * Store this sum value in a variable
2. Select the first vertext $v$ with minimum sum variable as the first facility to be opened
3. Select the second vertex $v'$ with minimum sum variable as the second facility to be opened
4. Select the third vertex $v''$ with minimum sum variable as the third facility to be opened
5. Connect all clients to facilities calculated in steps 2,3,4.

**Note**: This problem was considered in this article , and the authors provided an approximation algorithm for it. Hence, it should be a hard problem. They did not specifically mention the problem to be solved on the graph but mentioned that it should be on metric space. Moreover, they mention the existence of an approximation algorithm even in the uniform case of $r\_j$.

# Answer
> 1 votes
Let the set of client locations is $C = \\{c\_1,c\_2,c\_3\\}$ and the set of feasible facility locations is $F = \\{f\_1,\dotsc,f\_6\\}$. Let $k = 5$. Let the distance function be defined by $3 \times 6$ matrix $D$ such that $D\[i,j\]$ denotes the distance of client $i$ to facility $j$:

\begin{bmatrix} 1 & 1 & 2 & 1 & 3 & 3\\ 1 & 1 & 2 & 3 & 3 & 1\\ 1 & 1 & 2 & 3 & 1 & 3\\ \end{bmatrix}

Sum of distances for $f\_1$ is $3$, for $f\_2$ is $3$, for $f\_3$ is $6$, for $f\_4$ is $7$, for $f\_5$ is $7$, and for $f\_6$ is $7$.

Your algorithm chooses the facilities $f\_1$, $f\_2$, and $f\_3$. The total cost of the clients is $12$.

However, the optimal solution is $f\_1$, $f\_2$, $f\_4$, $f\_5$, and $f\_6$ with total cost $9$.

---
Tags: algorithms, graphs, optimization, approximation, clustering
---


# Question
Title: Isn't allocating a same size array for result considered to be space complexity O(n)?
It is related to this question: https://leetcode.com/problems/product-of-array-except-self/

And assuming we cannot alter the original array, but have to allocate a same size array to store the results, that is, if the input array is 200GB, we need to allocate a 200GB array. Input 800GB, allocate extra 800GB. Input 16TB, allocate 16TB. (suppose now or one day the RAM or virtual memory has that much capacity).

However, according to the problem description:

> Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

And some people putting down a solution also agree, essentially, allocating that extra array for the result doesn't count and it is space complexity O(1).

However, we do in practice have to allocate the 16GB, 800GB, 16TB, or whatever the input size is.

The question is, when doing this, is the space complexity O(1) or O(n)?

# Answer
It is normally assumed that the space for input *and* output is already allocated and neither do count in the estimation of the complexity. So you won't allocate an extra array.

This is logical, as you need the input and output storage anyway. What matters is additional resources that an algorithm would require.

---

A special case is given by MergeSort. Indeed, sorting algorithms are meant to be in-place, i.e. input and output coincide. This is why MergeSort is said to require $O(n)$ space.
> 2 votes

---
Tags: algorithms, space-complexity
---


# Question
Title: AVL tree with balance factor equal to depth
If you were to define an altered AVL tree where the balance factor (the difference between the height of the left and right subtree) of a node must be less than or equal to the depth of the node (in absolute value), would it be balanced (h is in O(log n))? How would you prove so?

# Answer
This is not a complete answer, but some ideas about it.

For convenience purposes, I will use the convention I talked about in the comments:

* the depth of a node $x$ is the number of **nodes** between the root of the tree and the node $x$. That means that the depth of the root is $1$ (and not $0$);
* the height of a tree is the maximal depth of one of its nodes.

For $h$ a positive integer, and $k$ a non-negative integer, denote $T\_{h,k}$ the set of binary trees $t$ such that for each internal node $N(l, r)$ of depth $p$, the balance factor is less than $p + k$, meaning: $$|h(l) - h(r)|\leqslant p + k$$

Denote $n\_{h, k}$ the **minimal** size of a tree of $T\_{h,k}$. It is somewhat clear that $n\_{h,k}$ is an increasing function in $h$ (if the height increases, so does the minimal size) and decreasing in $k$ (if we allow bigger balance factors, the tree is more unbalanced, and thus contains less nodes).

If $h \leqslant k + 1$, that means that there is no restriction on balance, and if that's the case, then $n\_{h,k} = h$.

In the general case, if $t\in T\_{h,k}$, then one of its children is in $T\_{h-1, k + 1}$ (the height decreases by one, and the balance factor increases by one, because the depth of all nodes in the child is increased by one in $t$). To minimize $n\_{h,k}$, the other child must be chosen of the minimal possible height, which is $h - 2 - k$. We get:

$$n\_{h,k} = 1 + n\_{h - 1, k + 1} + n\_{h - 2 - k, k + 1}$$

What you would like to know is if $n\_{h, 0}$ is exponential in $h$. Now I don't know how to solve this induction, but I made some tests in Python, because those values can be easily computed using dynamic programming.

The following curves show the values of $n\_{h,0}$ and $\log n\_{h,0}$ respectivelly. The first curve gives the impression that the growth is indeed exponential, however the second curve has a slower growth than a linear function, so that may not be the case. Still, any tree of size $\leqslant 3\times 10^{23}$ will have a height smaller than $1000$, so that could be considered balanced.
> 0 votes

# Answer
Trees you are asking for do not exist in general. Consider a tree with two nodes. Regardless of how you arrange them, one must be the root. Then absolute value of the balance factor of the root is $1$ but the root's depth is $0$.
> 0 votes

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


# Question
Title: Binary search calculating complexity big o
I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book :

```
Initially, the number of candidates is n; after the first call in a binary search, it is at
most n/2; after the second call, it is at most n/4; and so on.

```

What if n is a odd number ?

# Answer
Strictly speaking, $n$ reduces to at most $\left\lceil\frac n2\right\rceil$, which is $\frac n2$ or $\frac{n+1}2$, depending on the parity of $n$. So you are right. But this can only change the total number of subdivisions by one unit, so it remains essentially $O(\log(n))$.

E.g. $$27\to13\to6\to3\to1$$ vs. $$27\to14\to7\to4\to2\to1.$$

---

A common technique to handle cases with uneven partitions is to assume that $n$ is a power of $2$, so that all divisions are exact. Then for other $n$, you just notice that the number of partitions is intermediate between those for the bracketing powers of $2$. (E.g. $16\<27\<32$.)
> 0 votes

---
Tags: algorithms, recursion, big-o-notation
---


# Question
Title: How to find maximum number of edge-disjoint trails of length $k$ of a directed multi-graph $G=(V,E)$ between arbitrary start and end vertices?
How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices may be different for each trail, although they need not be different. (I'd like the output to be the paths themselves, and of course trivially the number of trails too).

This type of question has a lot of variations when some additional assumptions are added. Most of them involve adding a source and terminal vertex. However, I haven't seen any proper treatment of the case for an arbitrary $s,t$, even under a specific topology (e.g. $k$-connected, co-graph or bounds on the degree of a vertex, etc).

Assume that the problem is well-posed. If someone could help me get started towards a way to find such edge-disjoint paths of equal length, it would be helpful. Even if we need to make some assumptions on the topology of the graph, e.g. bounded degree, connected, etc., that's fine for now and I can find a way to generalize from those if needed.

# Answer
> 0 votes
This is not a complete solution. But the following reduction simplifies it.

The problem can be reduced to finding maximum number of edge disjoint paths of length $k$ between two vertices $s$ and $t$ in a directed graph. I am assuming that the given graph is unweighted. However, a similar reduction also works for weighted graphs.

*Reduction*: Given an instance graph $G = (V,E)$ for your problem. Add new vertices $s$ and $t$. Add $m$ multi directed edges from $s$ to every vertex in $V$ where $m = |E|$. Similarly, add $m$ multi directed edges from each vertex of $V$ to $t$. Then, for each edge $e = (u,v)$ in the graph, replace it with a new vertex $w\_e$, and edges $(u,w\_e)$ and $(w\_e,v)$. Let this new graph be $G' = (V',E')$.

*Claim:* For any set of $\ell$ edge-disjoint paths of length $k$ in directed multi-graph $G$ there exists $\ell$ edge-disjoint paths of length $2(k+2)$ in directed graph $G'$ and vive-versa.

The proof easily follows from the construction.

---

If you want the edge disjoint paths of length at most $k$, then there exists efficient algorithms: see this. The authors state that the problem can be solved in polynomial time using linear programming for unit edge lengths. I believe that a similar solution might also work for paths of length exactly $k$. There is a more recent paper on a similar problem.

---
Tags: graphs, graph-traversal, weighted-graphs, eulerian-paths
---


# Question
Title: Schaefer's dichotomy theorem and limits on the formula length
Schaefer's dichotomy theorem ensures than when a constraint satisfiability problem satisfies certain conditions, the problem is either in $\mathsf P$ or is $\mathsf{NP}$-hard.

Suppose the following problem:

> Given a monotone CNF $f(X)$ and a 2-CNF $g(X)$ such that $|g(X)|\le \log\_c^k |f(x)|$ (where $|f|$ stands for the amount of machine words used to encode $f$) decide if $f(X)\land g(X)$ is satisfiable.

$c\>1$ and $k$ are fixed (i.e. are not a part of the input). This problem is in $\mathsf{QP}$, but does Schaefer's dichotomy still apply to it or does the way the problem is formulated not satisfy the conditions in which the theorem applies?

# Answer
Schaefer's theorem is stated in many places, e.g., on Wikipedia. Can you define a set $S$ of relations so that your problem has the form specified in Schaefer's theorem? No, you cannot. Therefore, Schaefer's theorem does not apply. You will have to seek other tools to understand its complexity.
> 1 votes

---
Tags: complexity-theory, time-complexity, satisfiability, decision-problem
---


# Question
Title: DPDA for language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n$
How to construct DPDA for the following language $L=\\{a,b\\}^\* \setminus a^nb^n \setminus b^na^n $

$L\_1 = \\{a,b\\}^\* \setminus a^nb^n =\\{a^i b^j \\, | \\, i\>j\\}\\,\cup\\,\\{a^i b^j\ \ | \ i\<j\\}\\,\cup\\,(a+b)^\* b (a+b)^\* a (a+b)^\*$.

At this step I got stuck. What is next? How to express additional difference $b^na^n$?

# Answer
Given $L=(a+b)^\*- a^nb^n-b^na^n$ which could be written as $L=(a+b)^\*- (a^nb^n \cup b^na^n)=(a+b)^\* \bigcap (a^nb^n \cup b^na^n)^\complement= (a+b)^\* \bigcap \\{(a+b)^\*-(a^nb^n \cup b^na^n)\\}=(a+b)^\*\bigcap(\\{a^mb^n | m\neq n\\}\cup\\{b^ma^n | m\neq n\\}\cup a(a+b)^\*a\cup b(a+b)^\*b \cup (ab)^\*b \cup (ba) ^\*a) =\\{a^mb^n | m\neq n\\}\cup\\{b^ma^n | m\neq n\\}\cup a(a+b)^\*a\cup b(a+b)^\*b\cup (ab)^\*b \cup (ba) ^\*a,$

from here you could make $DPDA$ easily.
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: Defining 2 inductive propositions relying on each other in Coq
I'm pretty beginner in Coq. I want to formalize negative and positive occurrence of an atom in a proposition inside coq the definition is as down below:

I want to define this property as an *Inductive prop* so I use it with more ease in proving theorems (such as interpolation) but the problem is positively occurrence and negatively occurrence are defined with each other and I don't know how to do that.
I also thought of a Fixpoint function which returns `option bool` which false is equivalent to negative occurrence and true is equivalent to positive occurrence and None to no occurrence but it seems like a messy way to do it

# Answer
You can use mutually defined inductive types, using the `with` construct. Here is the standard simple example on how to do that:

```
Inductive even : nat -> Prop :=
  | evenO : even 0
  | evenS n : odd n -> even (S n)
with odd : nat -> Prop :=
  | oddS n : even n -> odd (S n).

```

Since you do not describe how you define your notion of formula or of occurrence of an atom, I'm not sure how exactly to make this idea fit your needs. I'll let you try and adapt it yourself.

Note that there are other ways to go about this than indexed inductive proposition. Your fixpoint idea seems like it can definitely work, and depending on the task might be better suited than the inductively defined solution. Also, instead of mutually defining the positive and negative occurrences, you can also define a single inductive proposition, say `occurrence_variance : occurrence -> formula -> bool -> Prop`, where `occurrence_variance o f true` means the occurrence `o` in `f` is a positive one, and `occurrence_variance o f false` in `f` is a negative one. This gives you the benefit of inductive definition for doing proofs by induction, but should cut down nicely on the duplication you'll get with the mutual approach.
> 2 votes

---
Tags: logic, proof-assistants, coq
---


# Question
Title: What is the closest theory to "The theory of code refactoring"?
We refactor code lots of times as developers. Metaphorically, our program space is an infinite-dimensional Rubik's cube. Things can be rearranged, preserving the code's action, so a "symmetry structure" is at play. You can do things in code that can be factored sort of like distributive law in a ring, but there are way more operations, so things are not that cut-and-dry.

If someone wanted to develop a next-generation IDE that is Refactoring-centered instead of having that as an auxillary feature added in later after centering things around an Editor and Debugger; then what theory should they study?

In other words what is the closest theory or topic in regards to the application of code refactoring? So the theory has to be taught but it also has to apply to real-world languages in a somewhat direct way, such as C++, Python, Java, etc.

Does such a theory exist already?

# Answer
> 5 votes
Basic code refactoring is not about symmetries but rather about *equivalences*. When code $C$ is transformed by refactoring to become code $C'$, we expect $C$ and $C'$ to "do the same thing". (This applies to simple forms of refactoring only.)

There are several notions of equivalence of code, such as:

* programs $P$ and $Q$ are equivalent when their mathematical meaning is the same
* programs $P$ and $Q$ are equivalent when they satisfy the same assertions in some program logics
* programs $P$ and $Q$ are equivalent when they cannot be distinguished in terms of their behavior

These slides might be helpful.

Anyhow, once a theory of equivalence is established, it can be used to make sure that code refactoring is done correctly, i.e., that no unintended changes in the code were made. People study this topic broadly, the slides linked to above should contain enough buzzwords for you to google around for more.

Of course, not all aspects of code refactoring are about program equivalence. In practice, one might make transformations that obviously change code (such as introducing a new method in a class definition). In such cases one would look at the topic of program transformation.

---
Tags: programming-languages, software-engineering, applied-theory
---


# Question
Title: How to reduce $k$-oriented problem to max flow problem?
Given an undirected graph $G$, how to reduce this problem :"Judge whether every edge of $G$ can be given a orientation such that for every vertex $v$ in $G$ has input-degree of at most $k$" to a max flow problem?

I tried the method in this link where input or output degree are the same because we can change all the orientation simultaneously. But the main distinction lies in "every vertex has at least output degrees" instead of "at most" and I havn't found how to modify this method.

Also post here: https://math.stackexchange.com/posts/4732656/

# Answer
A similar solution to the one given here works here as well. The following is the reduction (non-highlighted statements are directly taken from Steven's answer):

Given $G=(V,E)$, create a directed bipartite graph $H=(V+E, F)$ where there is an edge $(v,e) \in F$ iff $v \in V$ is an endpoint of $e \in E$. All these edges have capacity $1$.

Augment $H$ as follows: add two additional vertices $s$ and $t$; for each $v \in V$ add an edge $(s,v)$ **with capacity $k$**; for each $e \in E$ add the edge $(e, t)$ with capacity $1$.

Compute a maximum flow $\phi$ from $s$ to $t$ in the augmented version of $H$. Your problem admits a solution if and only **if the amount of flow $|\phi|$ is $|E|$. This ensures that all edges are oriented in the original graph.**
> 1 votes

---
Tags: algorithms, graphs, reductions, network-flow
---


# Question
Title: Is it an open problem if CDCL algorithms violate SETH?
Strong Exponential Time Hypothesis states that general SAT, where clauses are not limited in length, can't be solved in time $o(2^n)$. It's proven that DPLL algorithm requires $\Omega(2^n)$ time in the worst case.

CDCL algorithms, however, use more sophisticated approaches to SAT solving, primarily by using partial assignments and skipping the ones that obviously lead to unsatisfiability, such as setting all variables in a particular clause to make the clause equal to $0$.

In order to violate SETH it would suffice to show that 3-SAT is solvable in $o(\sqrt\[3\]{2^n})$ time. Is it known if CDCL in the worst case would require more time than this?

# Answer
No, it doesn't imply that there will be $\Omega(n)$ clauses of length $\le k$. Satisfiability of 100-CNF formulas (where all clauses have exactly 100 literals) is still NP-hard, even though there are 0 clauses of length $\le 99$.

Also, you have not accurately stated the strong exponential time hypothesis.
> 0 votes

---
Tags: time-complexity, runtime-analysis, satisfiability
---