# Question
Title: detecting a cycle in an undirected graph problem is in $RL$ complexity class
I need come up with an algorithm for detecting a cycle in an undirected graph where the algorithm is in $RL$. That is, the algorithm detects a cycle with a probability greater-equal to $\frac{1}{2}$ but it doesn't return true for a graph with no cycle (no false-positive).

In class, we've learned that $USTCONN$ (the problem of telling if there's a path from $s$ to $t$ in an unidrected graph) is in $RL$.

I thought about utilizing it for the current problem:

1. We choose $s,t$ in random s.t $t$ has at least $2$ edges and check if there's a path between them.
2. Then, in the same fashion, we check if there's a path between $s$ and $t$'s neighbors (If there are too many we may limit it to some constant, randomly, since we must use only logarithmic space)
3. If we found two different paths from $s$ to $u\_1,u\_2$ where the latter are $t$'s neighbors then there must be two different paths from $s$ to $t$ - Which is a cycle.
4. We repeat the above sufficiently many times (TBD)

I would like to know if that is the algorithm expected from me to come up with before I put efforts in proving that this algorithm is indeed in $RL$.

Thanks!

# Answer
> 2 votes
In fact USTCONN is in L (as shown by Reingold), and you can reduce your problem to USTCONN using non-backtracking walks. These are walks which are not allowed to backtrack, that is, after going from $x$ to $y$ we can't go immediately back to $x$ (but we could go back to $x$ via a different route). The graph contains a cycle iff there is a non-backtracking walk from some vertex to itself. You can formulate this problem as aan undirected connectivity problem, and solve it using the logspace algorithm for USTCONN. As a result, you can detect whether the graph contains a cycle in logspace.

---
Tags: complexity-theory, graphs, randomized-algorithms
---


# Question
Title: state of the art of subset, set containment and partial match queries
The subset query problem is defined as:
Given a list `D` of size `N` where the entries are subsets of a universe with `m` elements, create a datastructure that detects for every query-set `Q` if there exists a set `P` in `D` so that `Q`is a subset of `P`

I was wondering what are the best known algorithms to solve this problem. I couldn't find any recent publications, just this work from 2002: Subset Queries

There it is stated, that the subset query problem is equivalent to the set containment problem as well as the partial match problem.

Any help would be appreciated.

# Answer
I am not sure if this is "state of the art" but take a look at this paper Efficient subset and superset queries.
> 4 votes

---
Tags: algorithms, data-structures, matching
---


# Question
Title: Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?
Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is not $\mathcal{O}(1)$, it is $\mathcal{O}(\log s)$, where $s$ is weight of the path from initial vertex to current.

And this means that complexity is $\mathcal{O}(|V|^2\log s)$.

Am I missing something?

# Answer
***tl;dr*-** The idea that setting a value has $\mathcal{O}\left(\log{s}\right)$ complexity follows from a presumed model for numeric data where numbers require $\log{x}$ bits for representation. This isn't the case in most real-world implementations nor in general, so it isn't reflected in common descriptions of algorithm complexity.

However, the expression given in the question seems valid when the presumed data model is used. As such, I'd characterize this expression as implementation-specific; it's more precise when applicable, but it's only applicable when the relevant data model is used.

### Intro

It sounds like you're assuming a data model for numeric values where values start at $0$, then each bit expands the range, e.g. as in common binary notation. I'll assume that you handle floating-point extensions in a similar manner, e.g. $0.25$ in decimal is stored as `0.01` in the data model, while $\frac{1}{3}$ would require infinite bits to precisely represent.

In binary, we can distinguish $2^{n\_{\text{bits}}}$ of numbers given $n\_{\text{bits}}$ of storage. Further, this grows with $x$ as $x$ gets larger if we pin the data-zero to numeric-$0$. So, you could say that the complexity of a value $x$ is then $\log\_2\left(x\right)$, which is proportional to $\log\left(x\right)$.

The problem with this logic is that you're presuming a data model for numeric values that's **(1)** not usually true in implementation nor **(2)** logically optimal. I'll try to comment on **(3)** the general problem.

### (1) Not true in practice

In most common implementations of algorithms like this, primitive datatypes are used. Such datatypes store the same number of bits regardless of the numeric interpretation of their value.

In these cases (which is most cases), the complexity simply doesn't grow with the value of the weights.

### (2) Not true in the general case

If only (1) were the issue, it'd seem like an implementation thing, right? But $\log{\left(x\right)}$ isn't logically true either.

The core problem is that it presumes a numeric model where you start at zero and add bits to represent larger values. While that seems like a sensible approach, it's by no means fundamentally the only reasonable way to store data.

For a practical example, consider a system where weights might be a multiple of $\pi$. To store $\pi$ in the presumed data model, you'd need $$\log{\infty}=\infty$$ bits. That's obviously not possible. But, you can use algebraic logic (think Mathematica) with more abstract data types to bridge the gap.

### (3) The general problem

In general, the computer needs to do two things:

1. Keep expressions for total of path distance.
2. Be able to compare those expressions to determine if one's larger than the other.

Neither of these require that the numbers be stored in a format with $\mathcal{O}\left(\log{s}\right)$ complexity. For example, consider someone asking a StackExchange question like this:

> What's larger:
>
> 1. the distance from Washington DC to Maryland; *or*
> 2. the distance from Earth to the edge of the observable universe to the googolplexth power to the googolplexth power.

In answering this question, do you need $\log{\left(\left(\left\[{r}\_{\text{universe}}\right\]^{{10}^{\left({10}^{100}\right)}}\right)^{{10}^{\left({10}^{100}\right)}}\right)}$ of storage in your brain? Or, if they asked about volumes or something else that involves $\pi$, does your brain need infinite data storage?

The answer's obviously no; you have comparison methods that aren't based on the presumed model with $\log\_2\left(x\right)$ of storage needed. Likewise, a computer program shouldn't need to use that storage model, either.

### Conclusion

We don't attribute $\mathcal{O}\left(\log{s}\right)$ complexity to numeric data because that characterization follows from a model that's neither true in general nor used in practice.

If you do want to include that component in your complexity assessment of an algorithm, you'd need to qualify the complexity claim with the fact that you're considering a special case of the algorithm which uses the presumed data model.
> 3 votes

# Answer
Algorithms are usually analyzed under the *word RAM* model, in which basic operations on machine words cost $O(1)$. Machine words are defined as words of length $\log n$, where $n$ is the size of the input (in bits).

In the case of algorithms on weighted graphs, we could make the further assumption that weights are put in special registers for which "reasonable" arithmetic operations are $O(1)$. This assumption is made implicitly, without any mention of it, since the exact computation model isn't really needed when designing an algorithm, as long as you're not "cheating". It allows using floating point weights, for example.

The computation model serves two purposes:

* To explain what constitutes "cheating", that is, what is not allowed (or rather, what *is* allow).
* To allow proving lower bounds.

If we are not careful with the computation model, we could solve PSPACE-complete problems such as TQBF; see here.

One instantiation of the murky class of computation models for weighted graphs is allowing the weights to fit in a constant number of machine words; then we can just analyze the algorithm using the word RAM model. In this case, any weight encountered during Dijkstra's algorithm also fits in a constant number of machine words, since any such weight is the sum of at most $|V|-1$ weights. Therefore in the word RAM model, assignment (as well as addition) costs $O(1)$ rather than $O(\log s)$.
> 6 votes

---
Tags: complexity-theory, graphs, time-complexity, runtime-analysis
---


title: What have I done wrong in this C code

text:
# Question
Title: What have I done wrong in this C code
I tried to make a program printing out the contents of the file text.txt, but for some reason it only prints out the even letters. What have I done wrong?

# Answer
> 2 votes
This really should be in Stack Overflow for coding issues. Computer Science is, as I understand it, more for "big picture" CS stuff.

That being said, the problem is that you have `fgetc(fp)` twice - in the while() and inside { }, so the first one reads and throws away the character (no assignment to a variable) and the second one (inside { }) reads and prints.

---
Tags: programming-languages
---


# Question
Title: Difference between an a microcontroller and a system on a chip?
I pulled this right from Wikipedia to compare, staring with an SoC:

> A system on a chip or system on chip (SoC or SOC) is an integrated circuit (IC) that integrates all components of a computer or other electronic system into a single chip.

And to compare, here's the microcontroller:

> A microcontroller (sometimes abbreviated µC, uC or MCU) is a small computer on a single integrated circuit containing a processor core, memory, and programmable input/output peripherals.

What is the difference? If they are both small computers that integrate all components on a single integrated circuit, and are limited, why are they regarded as different concepts or terms? A microcontroller has everything an SoC has, so why are they claimed to be different?

To elaborate further, what draws any tangible line here on any noteworthy differences?

They both are in the area of embedded systems, but aside from minimal differences, they are both seemingly exact in almost every way.

# Answer
> 8 votes
The microcontroller definition is, at best, poorly worded. The distinction between an SoC and a microcontoller may be a bit fuzzy, but not that fuzzy. A microcontroller might be included as one element of an SoC, but it is not an SoC.

SoC means (approximately) "single chip solution." The SoC in a cell phone might have a 32-bit ARM processor running Linux (Android) and any apps that the user has installed. In addition it would have a GPU, the wireless transceiver and modem, the video and audio decoders for streaming video, GPS, controllers for the accelerometer, controllers for battery management, and who knows what else. There might be many microcontrollers in a SoC.

The "peripherals" included on the microcontroller itself are going to be a lot less specific. They are really registers for communicating with the *off-chip* devices (or at least off-module, if the microcontroller is embedded in an SoC) that you are controlling with the microcontroller. The peripherals might include some analog-to-digital or digital-to-analog converters, and/or a USB controller and/or I2C bus controller.

More often than not the microcontroller will be running a single program (no operating system, no apps), and that program will be stored in a read-only-memory (Flash). (Usually the flash memory *is* included in the same chip as the microprocessor.)

As an example. Here's the specs for the Microchip PIC16F77:

> This powerful (200 nanosecond instruction execution) yet easy-to-program (only 35 single word instructions) CMOS FLASH-based 8-bit microcontroller packs Microchip's powerful PIC® architecture into an 40- or 44-pin package and is upwards compatible with the PIC16C5X, PIC12CXXX and PIC16C7X devices. The PIC16F77 features 8 channels of 8-bit Analog-to-Digital (A/D) converter with 2 additional timers, 2 capture/compare/PWM functions and the synchronous serial port can be configured as either 3-wire Serial Peripheral Interface (SPI™) or the 2-wire Inter-Integrated Circuit (I²C™) bus and a Universal Asynchronous Receiver Transmitter (USART). All of these features make it ideal for more advanced level A/D applications in automotive, industrial, appliances and consumer applications.

It also has 14KB of flash to store the program and 368 *bytes* of RAM. (Yes you read that right, *bytes*.)

# Answer
> 2 votes
The differences are essentially non-technical. Microcontrolers date back to the 70's and the term is used for what provide more or less the same feature set as what was possible then, just higher end; you could consider SoC as the current incarnation of the same idea if there wasn't at least another difference. Microcontrolers are from CPU vendors who added commonly used pieces to their CPU, SoC comes from the ASIC world and were first designed for a specific product, then a specific line of products of the designer before being sold outside the designing organization. Both points make SoC more application specific than microcontrolers.

# Answer
> 2 votes
I will try to make it short. Let me put it this way: if you ask for the difference between a car, a truck and a bulldozer you will have the same kind of answers as for this question. They all have wheels, motor, pedals, you can drive them, etc... actually they follow the same concept. With terms like microcontroller, SoC, CPU, DSP and the like you are facing the same problem when looking for a definition, they are essentially the same but they are focused on different use cases.

A microcontroller is focused on control systems: they have (in general and relatively) a wide range of interfaces (SPI,I2C, a lot of GPIOs...), less computational power, no MMU... A CPU is a bit different: less interfaces, more raw power... A SoC is an encapsulation of one or more of these (CPUs, microcontrollers, DSPs, other accelerators) intended for applications with more requirements and have more complex and diverse hardware available on the same chip.

Needless to say that there exist bulldozers that are faster than some cars...

# Answer
> 1 votes
A microcontroller is simply a CPU with built-in RAM (not cache RAM) and ROM. It can execute code on startup without external RAM or ROM. The Intel 8042, which was the keyboard controller in the original IBM PC, is an example. It's a CPU but has an EEPROM as well. SD cards and USB devices often have microcontrollers (with programmable flash ROM).

A System-On-Chip is a chip that has a CPU plus supporting hardware that would typically fall in a "chipset" or "peripheral" category. RAM is not necessarily part of this but can be. Home routers are a good example where a MIPS CPU core is combined with switch hardware, or things like the Qualcomm Snapdragon which has multiple CPU cores along a lot of other hardware. One could argue that modern x86 CPUs are becoming more like SoCs with the integration of memory controllers, PCIe interfaces, and integrated graphics.

---
Tags: computer-architecture
---


# Question
Title: Examples for CFG that cannot be expressed by regular language
There are nice examples for context free grammars which cannot be expressed with regular language, for example the palindrome and a similar contrived example here, but they are very intuitively applicable for formal languages, e.g. checking for balanced nested parentheses and such.

Can you conceive an example that is pertinent to natural languages?

Part of the motivation to this question is that in one view, regular expressions are practically intractable when it comes to combining and scaling them to describe natural language phenomena; they don't compose as nicely as grammars. But at the same time I can't easily think of an *actual example* where regular expressions should not be enough for describing natural languages.

An example, therefore, for some natural language phenomena that cannot be modelled with regular language, would be very nice and interesting!

# Answer
Theoretically, you can nest sentences arbitrarily depth, by using subclauses and this excluded any finite state mechanism. The inventor of the phrase structure grammars himself looked at finite state languages, and compared them with the model of phrase structure grammars. The abstract of his paper *Finite State languages* reads:

> We find that no finite-state Markov-process \[...\] can serve as an English grammar \[...\]

The idea to use finite Markov processes, which came down to finite automata in Chomskys work, go back to ideas of Shannon (see his seminal work *A mathematical theory of communication*). If this caught your interest, you might also take a look at the two works *Three models for the description of language* and *Syntactic structures* by N. Chomsky, where he further discusses the adequacy of grammars and finite state processes for language description (or production thereof).

Later, these ideas, which originally came from linguistics and where therefore closely related to research on natural languages, where later adapted by computer scientists to describe programming languages. I refer to the seminal papers *Two families of languages related to ALGOL* by Ginsburg and Rice or *Revised Report on the Algorithmic Language Algol 60*, where the BNF was introduced, the first papers using this phrase structure (or nowadays context free) grammars to describe programming languages.

But on the other side, you seldom find "arbitrary" complex nested sentences, as, in general, the "cognitive" system could not handle them, or said differently this could be conceived as a finite state systems. I refer, for example, to the famous paper The magical number seven, plus or minus two by G. Miller, which states that for numbers the human brain can only store a finite number $7 \pm 2$ of digits. Similar restrictions might hold for language processing, see the textbook *The psychology of language* by T. Harley.
> 4 votes

# Answer
If no bracket language examples suffice, your quest is futile. Every context-free-language is a reduction of a bracket/parenthesis language. Reduction comprises

* homomorphism;
* intersection with a regular language.

This is the Chomsky-Schutzenberger (representation) theorem.
> 4 votes

---
Tags: context-free, formal-grammars, natural-language-processing
---


# Question
Title: Why is addition as fast as bit-wise operations in modern processors?
I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex operation that consists of at least one and possibly up to a dozen bit-wise operations, so I naturally thought it will be 3-4 times slower. I was surprised to see after a simple benchmark that addition is exactly as fast as any of the bit-wise operations(XOR, OR, AND etc). Can anyone shed light on this?

# Answer
Addition is fast because CPU designers have put in the circuitry needed to make it fast. It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers have judged it to be worth it. See https://en.wikipedia.org/wiki/Adder\_(electronics).

Both can be made fast enough to execute within a single CPU cycle. They're not equally fast -- addition requires more gates and more latency than a bitwise operation -- but it's fast enough that a processor can do it in one clock cycle. There is a per-instruction latency overhead for the instruction decoding and control logic, and the latency for that is significantly larger than the latency to do a bitwise operation, so the difference between the two gets swamped by that overhead. AProgrammer's answer and Paul92's answer explain those effects well.
> 110 votes

# Answer
There are several aspects.

* The relative cost of a bitwise operation and an addition. A naive adder will have a gate-depth which depend linearly of the width of the word. There are alternative approaches, more costly in terms of gates, which reduce the depth (IIRC the depth then depend logarithmically of the width of the word). Others have given references for such techniques, I'll just point out that difference is also less important than what it may seem just considering the cost of the operation because of the need of control logic which add delays.
* Then there is the fact that processors are usually clocked (I'm aware of some research or special purpose non clocked designs, but I'm not even sure that some are available commercially). That means that whatever the speed of an operation is, it will take at an integer multiple of the clock cycle.
* Finally there is the micro-architectural considerations: are you sure that you measure what you want? Nowadays, processors tend to be pipelined, multi-scalar, with out-of-order execution and whatever else. That means that they are able to execute several instructions at the same time, at various stage of completion. If you want to show by measurements that an operation takes more time that another, you have to take take those aspect in consideration as their goal is to hide those difference. You may very well have the same throughput for addition and bitwise operations when using independent data but a measure of the latency or introducing dependencies between the operations may show otherwise. And you have also to be sure that the bottleneck of your measure is in the execution, and not for instance in the memory accesses.
> 43 votes

# Answer
CPUs operate in cycles. At each cycle, something happens. Usually, an instruction takes more cycles to execute, but multiple instructions are executed at the same time, in different states.

For example, a simple processor might have 3 steps for each instruction: fetch, execute and store. At any time, 3 instructions are being processed: one is being fetched, one is being executed and one stores its results. This is called a pipeline and has in this example 3 stages. Modern processors have pipelines with over 15 stages. However, addition, as well as most of the arithmetic operations, are usually executed in one stage (I am speaking about the operation of adding 2 numbers by the ALU, not about the instruction itself - depending on the processor architecture, the instruction might require more cycles for fetching arguments from memory, performing conditionals, storing results to memory).

The duration of a cycle is determined by the longest critical path. Basically, it's the longest amount of time necessary for some stage of the pipline to complete. If you want to make the CPU faster, you need to optimize the critical path. If reducing the critical path per se is not possible, it can be split into 2 stages of the pipeline, and you are now able to clock your CPU at almost twice the frequency (assuming there is not another critical path that prevents you from doing this). But this comes with an overhead: you need to insert a register between the stages of the pipeline. Which means that you don't really gain 2x speed (the register needs time to store the data), and you have complicated the whole design.

There are already quite efficient methods for performing addition (e.g. carry lookahead adders) and addition is not a critical path for the processor speed, thus is makes no sense splitting it into multiple cycles.

Also, note that while it might seem complicated for you, in hardware things can be done in parallel very fast.
> 26 votes

# Answer
Processors are clocked, so even if some instructions can clearly be done faster than others, they may well take the same number of cycles.

You'll probably find that the circuitry required to transport data between registers and execution units is significantly more complicated than the adders.

Note that the simple MOV (register to register) instruction does even less computation than bitwise logic, yet both MOV and ADD usually take one cycle. If MOV could be made twice as fast, CPUs would be clocked twice as fast and the ADDs would be two cycles.
> 13 votes

# Answer
Addition is important enough to *not* have it wait for a carry bit to ripple through a 64-bit accumulator: the term for that is a carry-lookahead adder and they are basically part of 8-bit CPUs (and their ALUs) and upwards. Indeed, modern processors tend to need not much more execution time for a full multiplication either: carry-lookahead is actually a really old (and comparatively affordable) tool in a processor designer's toolbox.
> 12 votes

# Answer
I think you'd be hard pressed to find a processor that had addition taking more cycles than a bitwise operation. Partly because most processors must carry out at least one addition per instruction cycle simply to increment the program counter. Mere bitwise operations aren't all that useful.

(Instruction cycle, not clock cycle - e.g. the 6502 takes a minimum of two clock cycles per instruction due to being non-pipelined and not having an instruction cache)

The real concept you may be missing is that of the *critical path*: within a chip, the longest operation that may be performed within one cycle dictates, at the hardware level, how fast the chip may be clocked.

The exception to this is the (rarely used and hardly commercialised) asynchronous logic, which really does execute at different speeds depending on logic propagation time, device temperature etc.
> 10 votes

# Answer
At the gate level, you are correct that it takes more work to do addition, and thus takes longer. However, that cost is sufficiently trivial that doesn't matter.

Modern processors are clocked. You cannot do instructions at anything except multiples of this clock rate. If the clock rates were pushed higher, to maximize the speed of the bitwise operations, you would have to spend at least 2 cycles on addition. Much of this time would be spent waiting around because you didn't really need the full 2 cycles worth of time. You only needed 1.1 (or some number like that). Now your chip adds slower than everyone else on the market.

Worse, the mere act of adding or doing bitwise operations is only one tiny part of what is going on during a cycle. You have to be able to fetch/decode instructions within a cycle. You have to be able to do cache operations within a cycle. Lots of other things are going on on the same timescale as the simple addition or bitwise operation.

The solution, of course, is to develop a massively deep pipeline, breaking these tasks up into tiny parts that fit into the tiny cycle time defined by a bitwise operation. The Pentium 4 famously showed the limits of thinking in these deep pipeline terms. All sorts of issues arise. In particular branching gets notoriously difficult because you have to flush the pipeline once you have the data to figure out which branch to take.
> 9 votes

# Answer
Modern processors are clocked: Every operation takes some integral number of clock cycles. The designers of the processor determine the length of a clock cycle. There are two considerations there: One, the speed of the hardware, for example measured as the delay of a single NAND-gate. This depends on the technology used, and on tradeoffs like speed vs. power usage. It is independent of the processor design. Two, the designers decide that the length of a clock cycle equals n delays of a single NAND-gate, where n might be 10, or 30, or any other value.

This choice n limits how complex operations can be that can be processed in one cycle. There will be operations that can be done in 16 but not in 15 NAND delays. So chosing n = 16 means such an operation can be done in a cycle, choosing n = 15 means it can't be done.

The designers will chose n so that many important operations can be just about done in one, or maybe two or three cycles. n will be chosen locally optimal: If you replaced n with n-1, then most operations would be a bit faster, but some (those that really need the full n NAND delays) would be slower. If few operations would slow down, so that overall program execution is faster on average, then you would have picked n-1. You could also have picked n+1. That makes most operations a bit slower, but if you have many operations that can't be done within n delays but can be done within n+1 delays then it would make the processor overall faster.

Now your question: Add and subtract are so common operations that you want to be able to execute them in a single cycle. As a result, it doesn't matter that AND, OR etc. could execute faster: They still need that one cycle. Of course the unit "calculating" AND, OR etc has a lot of time to twiddle its thumbs, but that can't be helped.

Note that it's not just whether an operation can be done within n NAND-delays or not: An addition for example can be made faster by being a bit clever, still faster by being very clever, still a bit faster by investing extraordinary amounts of hardware, and at last a processor can have a mixture of very fast very expensive and a bit slower and cheaper circuits, so there is the possiblity to make one operation just about fast enough by spending more money on it.

Now you *could* make the clock speed so high / the cycle so short that only the simple bit operations execute in one cycle and everything else in two or more. That would most likely slow the processor down. For operations that take two cycles, there is usually overhead to move an incomplete instruction from one cycle to the next, so two cycles doesn't mean you have twice as much time for execution. So to do the addition in two cycles, you couldn't double the clock speed.
> 8 votes

# Answer
Let me correct a few things that were not mentioned that explicitely in your existing answers:

> I know that bitwise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel,

This is true. Labeling a CPU as "XX" bit usually (not always) means that most of its common structures (register widths, addressable RAM etc.) are XX bits in size (often "+/- 1" or somesuch). But in regards to your question, you can safely assume that a CPU with 32 bit or 64 bit will do any basic bit operation on 32 or 64 bits in constant time.

> so bitwise operations take only one clock cycle.

This conclusion is not necessarily the case. Especially CPUs with rich instruction sets (google CISC vs. RISC) can easily take more than one cycle for even simple commands. With interleaving, even simples commands might break down into fetch-exec-store with 3 clocks (as an example).

> However addtion is a complex operation

No, integer addition is a simple operation; subtraction as well. It is very easy to implement adders in full hardware, and they do their stuff as instantaneously as basic bit operations.

> that consists of at least one and possibly up to a dozen bitwise operations, so I naturally thought it will be 3-4 times slower.

It will take up 3-4 times as many transistors, but in comparison to the big picture that is neglectible.

> I was surprised to see after a simple benchmark that addition is exactly as fast as any of the bitwise operations(XOR, OR, AND etc). Can anyone shed light on this?

Yes: integer addition *is* a bitwise operation (with a few more bits than the others, but still). There is no need to do anything in stages, there is no need for complicated algorithms, clocks or anything else.

If you wish to add more bits than your CPU architecture, you will incur a penalty of having to do it in stages. But this is on another level of complexity (programming language level, not assembly/machine code level). This was a common problem in the past (or today on small embedded CPUs). For PCs etc., their 32 or 64 bits are sufficient for the most common data types for this to start to become a moot point.
> 6 votes

---
Tags: computer-architecture, arithmetic, circuits, cpu, digital-circuits
---


# Question
Title: Is rejecting in polynomial time required for language to be in P?
Language $L$ is in $\mathrm{P}$ if and only if there exists some Turing Machine $M$ such that for every word in $L$, $M$ either accepts or rejects it in polynomial time. Right?

But what if all we know about our language is that there exists TM $M'$ such that for every word in $L$, $M$ accepts it in polynomial time, but for words not in $L$ it might not halt at all, for example? Is existence of $M'$ enough to say that $L$ is in $\mathrm{P}$, and why/why not?

# Answer
Suppose you have a problem $A$, and a TM $M$ which accepts all the words $w \in A$ within a polynomial time bound $p(|w|)$, and diverge (or reject) otherwise.

Then, we can craft a new TM $N$, which on input $w$ performs the following:

* simulate $M$ with input $w$ for $p(|w|)$ steps;
* if $M$ accepts, we make $N$ accept as well
* otherwise we make $N$ reject

It is immediate to see that $N$ runs in polynomial time: simulating a step of $M$ requires polynomial time on the $M$ configuration (whose size remains polynomial during the whole simulation), and we only need a polynomial number of steps.

Further, $N$ decides $A$ by construction.

TL;DR: if we know we can only accept a word within a time bound $t$, we can set an alarm on $t$. When the alarm rings, if we have not accepted before, we know it's a reject.

Conclusion: your alternative definition of $P$ is equivalent to the regular one. I would argue that it is harder to work with in proofs, though.
> 8 votes

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


# Question
Title: Check whether an interval is contained in a union of intervals
Initial Problem:

> Given an interval $\[A, B\]$ and a set of intervals $S = \\{\[S\_{11}, S\_{12}\], \[S\_{21}, S\_{22}\], \[S\_{31}, S\_{32}\], \ldots, \[S\_{N1}, S\_{N2}\]\\}$ with $S\_{11}\leq S\_{21}\leq \cdots \leq S\_{N1}$ output True if and only if $\[A, B\]$ is completely contained in the union of all intervals in $S$, and False otherwise.

What is the best-time-complexity algorithm we can do this? Surely, there is a way to do this in $O(N)$ naively but is there any technique we could use to, say, lower the complexity down to $O(\log N)$ or anything better than $O(N)$?

# Answer
> 2 votes
The problem requires $\Omega(n)$ time. Consider the interval $\[A,B\] = \[0,N\]$ and an algorithm for the problem. Whenever the algorithm queries $\[S\_{i1},S\_{i2}\]$, it gets the answer $\[i-1,i\]$. If the algorithm queries all intervals, then it knows that they cover $\[A,B\]$. Otherwise, the algorithm cannot tell. Indeed, suppose that it doesn't query $\[S\_{i1},S\_{i2}\]$, and that all other intervals are of the indicated form. If $\[S\_{i1},S\_{i2}\] = \[i-1,i\]$ then they cover $\[A,B\]$, but if $\[S\_{i1},S\_{i2}\] = \[i-1/3,i-2/3\]$ then they don't. Note that both inputs are legal (satisfy the constraint $S\_{11} \leq S\_{21} \leq \cdots \leq S\_{n1}$).

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


title: Prove that $NP^{NP\cap co-NP} = NP$

text:
# Question
Title: Prove that $NP^{NP\cap co-NP} = NP$
> Let $A\in NP\cap co-NP$. Then, $NP^A = NP$.

At first, I thought: Easy, let $L\in NP^A$ s.t. $A\in NP\cap co-NP$. Let $M\_L$, an $NDTM$ to decide $L$ and $M\_A$, an $NDTM$ to decide $A$. Then, we could create a new $NDTM$, $M$ which acts the same as $M\_L$, but instead of calling the oracle, it *simulates* $M\_A$ on the oracle's input.

That is wrong as far as I understand; We can't simulate an $NDTM$ that way since $M\_A$ may have some computation paths which *rejects* and some which *accepts* and we wouldn't know how to act.

What should I do instead?

# Answer
> 4 votes
Since $A \in \mathsf{NP} \cap \mathsf{coNP}$, there is a witness both for $x \in A$ and for $x \notin A$. An NP machine which wishes to (non-deterministically) find out whether $x \in A$ or not can guess the answer ($x \in A$ or $x \notin A$) and then verify it using a witness.

---
Tags: time-complexity, complexity-classes
---


title: Formal definition on graph levels

text:
# Question
Title: Formal definition on graph levels
I'm looking for a formal definition of "graph levels" on a DAG. This example should illustrate what I mean by this.

The node 0 has no edges directed towards it, therefore this has level 0. Next is is 3 and 4 which will have level 1 and so on.

Level 0 : node 0

Level 1 : node 3, node 4

Level 2 : node 1, node 2

Level 3 : node 5

# Answer
A DAG (or poset) is *ranked* or *graded* if it is possible to assign nodes a rank function $r$ such that if $(x,y)$ is a directed edge, $r(y) = r(x)+1$. We usually choose $r$ so that $\min r = 0$. See for example the Wikipedia article on graded poset.
> 3 votes

# Answer
This is sometimes known as a level structure, and they come up in e.g., certain algorithmic applications.
> 2 votes

---
Tags: graphs, dag
---


# Question
Title: Code to count number of leaves of a tree?
I've just started learning C. Can anyone tell me whether my code is correct or not, if not what's the correct version? This is code for counting number of leaf nodes. Is this efficient one if this is correct?

```
void Count_leaf( Tree* head)
    {       static leaf = 0;
            if(head.left==NULL && head.right==NULL)
            leaf++;
            else
            {     Count_leaf(head.left);
                  Count_leaf(head.right);
            }
    }

```

# Answer
Using this recursive algorithm is indeed a correct way. But your code is wrong, and it could use some improvements.

First of all, you are using a pointer for `head` so you should use `->` instead of `.` to access the `left` and `right` element.

Then, using a `static` variable is not the cleanest way to store the result. You could use the recursion and simply return the result, like so:

```
int Count_leaf(Tree* head)
{
    if(head->left == NULL && head->right == NULL)
        return 1;
    else
        return Count_leaf(head->left) + Count_leaf(head->right);
}

```

Finally, you should check if the tree is empty before starting any counting. You can add a simple condition at the start of your fonction to do that:

```
if(head == NULL)
    return 0;

```

Here is the final program:

```
int Count_leaf(Tree* head)
{
    if(head == NULL)
        return 0;

    if(head->left == NULL && head->right == NULL)
        return 1;
    else
        return Count_leaf(head->left) + Count_leaf(head->right);
}

```
> 2 votes

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


# Question
Title: What counts as automatic program analysis?
I'm trying to understand the definition of program analysis on Wikipedia:

> Program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness.

What is the meaning of "automatic" here?

Are parsers static analysis tools, since they will throw an error if they encounter syntactically invalid code?

Is running a program an example of dynamic analysis, since it will provide me with an output (though I still have to interpret it myself)?

What if I explicitly throw a `this can't happen` exception when the program reaches an invalid state?

What about using a debugger to pause execution?

# Answer
> 5 votes
There is no sharp formal definition.

"Static" denotes "before running the program".

"Dynamic" denotes "while running the program".

"Automatic" stands for "without the intervention of the user". For instance, Hoare logic can be used to prove program properties, but (at least in its basic form) it requires user-provided invariants. Abstract interpretation, instead, often results in a totally automatic analysis. Type checking is usually regarded as automatic, since the type checker does not (usually) ask the user to provide hints about, e.g., *why* a given expression has the given type.

Parsing is static, but it's such a preliminary stage that probably most people wouldn't consider as program analysis at all. If a text file does not respect the syntactic rules, it is not part of the programming language (a language being a set of strings, after all!), hence it is not even a program, hence parsing is not *program* analysis. I would not be very interested in the syntax errors reported by `cc kitten.jpeg`, for instance.

Observing the program when it is being run is definitely a "dynamic" approach. Using a debugger, observing fired exceptions fall in this category.

# Answer
> 1 votes
The key part of the definition, which you have not focussed on, is "*analyzing* the *behavior* of computer programs".

* Analyzing suggests more than just running, it suggests performing some computation on, or, "examining (something) methodically and in detail, typically in order to explain and interpret it." (Oxford Dictionary).
* It is the behaviour of the program that is analyzed. The syntax is not part of the behaviour. The type structure, for example, is an abstraction of the behaviour of the program. The memory allocation behaviour is another aspect of the behaviour of the program. And so forth.

---
Tags: static-analysis
---


title: Number of Inner nodes in a B-Tree

text:
# Question
Title: Number of Inner nodes in a B-Tree
the question goes as follows: In a B-tree (d,2d) of height h, what is the minimal and maximal number of inner-nodes (excluding leaves)?

My idea:

**Minimal:** The root is 1, it has a minimum of 2 children, therefore we have 1 + 2, and then for any level below each node will have the minimum nodes allowed which is d. We get $1 + 2 + 2d + 2d^2 + ... + 2d^{h-1}$ including the leaves, therefore making $1 + \sum\_{i=1}^{h-2} 2d^i$ (note that the final index is $h-2$ since we dont count the leaves).

**Maximal:** Pretty similiar but each level will have $2d$ children, thus making $ 1 + 2d + (2d)^2 + .... + (2d)^{h}$ including the leaves, therefore making $ \sum\_{i=0}^{h-1} (2d)^i$.

However, the answer sheet goes $1 + \sum\_{i=1}^{h} (2d)^i$ for maximal and $1 + \sum\_{i=1}^{h} 2d^{i-1}$ for minimal.

I'll note that the height is defined as the numbers of edges from top-to-bottom, and for example; a tree of root only is of height 0. Tree of root + one set of children is of height 1.

Am I missing something or is there a mistake in our answer-sheet?

Thanks!

# Answer
Update: There was an error in the answer sheet, it turns out I was right.
> 0 votes

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


title: About Depth first search

text:
# Question
Title: About Depth first search
Graph

Is 1) A D F E G C B and; 2) A D F E G B C is one of deep-first transverse?

The code below is written in java and method1 and method2 is two different implementation.

```
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

/**
 * Created by raymond on 12/05/2017.
 */
class Node {
    public char ele;
    public ArrayList<Node> neighbors = new ArrayList<>();
    public boolean visited = false;

    public Node(char ele) {
        this.ele = ele;
    }
}

public class Test {
    private static HashMap<Character, Node> nodes = new HashMap<Character, Node>() {{
        put('A', new Node('A'));
        put('B', new Node('B'));
        put('C', new Node('C'));
        put('D', new Node('D'));
        put('E', new Node('E'));
        put('F', new Node('F'));
        put('G', new Node('G'));

    }};

    static void addNeighbors() {
        nodes.get('A').neighbors.add(nodes.get('B')); //A
        nodes.get('A').neighbors.add(nodes.get('D')); //A

        nodes.get('B').neighbors.add(nodes.get('A')); //B
        nodes.get('B').neighbors.add(nodes.get('C')); //B
        nodes.get('B').neighbors.add(nodes.get('E')); //B
        nodes.get('B').neighbors.add(nodes.get('G')); //B

        nodes.get('C').neighbors.add(nodes.get('B')); //C
        nodes.get('C').neighbors.add(nodes.get('D')); //C
        nodes.get('C').neighbors.add(nodes.get('F')); //C

        nodes.get('D').neighbors.add(nodes.get('A')); //D
        nodes.get('D').neighbors.add(nodes.get('C')); //D
        nodes.get('D').neighbors.add(nodes.get('F')); //D

        nodes.get('E').neighbors.add(nodes.get('B')); //E
        nodes.get('E').neighbors.add(nodes.get('F')); //E
        nodes.get('E').neighbors.add(nodes.get('G')); //E

        nodes.get('F').neighbors.add(nodes.get('C')); //F
        nodes.get('F').neighbors.add(nodes.get('D')); //F
        nodes.get('F').neighbors.add(nodes.get('E')); //F

        nodes.get('G').neighbors.add(nodes.get('B')); //G
        nodes.get('G').neighbors.add(nodes.get('E')); //G
    }

    static void method1() {
        Stack<Node> stack = new Stack<Node>();
        Node currentNode = nodes.get('A'); //Start node
        stack.push(currentNode);
        while (!stack.isEmpty()) {
            currentNode = stack.pop();
            currentNode.visited = true;
            for(int i = 0; i < currentNode.neighbors.size(); i++) {
                if(currentNode.neighbors.get(i).visited) continue;
                stack.push(currentNode.neighbors.get(i));
                currentNode.neighbors.get(i).visited = true;
            }
            System.out.print(currentNode.ele + " ");
        }
    }

    static void method2() {
        Stack<Node> stack = new Stack<Node>();
        Node currentNode = nodes.get('A'); //Start node
        stack.push(currentNode);

        while (!stack.isEmpty()) {
            currentNode = stack.pop();
            if(currentNode.visited) continue;

            for(int i = 0; i < currentNode.neighbors.size(); i++) {
                stack.push(currentNode.neighbors.get(i));
            }

            System.out.print(currentNode.ele + " ");
            currentNode.visited = true;
        }
    }

    public static void main(String... args) {
        addNeighbors();
        method1();
        System.out.println();
        for(Node n :nodes.values()) n.visited = false; //reset
        method2();
    }

}

```

1) Are method1 and method2 are also Depth first search?

2) What different between these methods?

3) For the method1 it just go through to G and the back to C B. The level of depth is only 5. But for the second method, it don't need to go back to C B and only one path. The level of depth is 7. Is method1 is also a DFS?

# Answer
Codebot basically the implementation of BFS(Breath First Search) and DFS(Depth First Search) are totally different. Let assume our graph in this format :-

```
     A
   /   \
  B     C
 /
D

```

So if you do BFS, your path traversal should be:-

```
 A->B->C->D

```

And for DFS, it should be:-

```
 A->B->D->C

```

Hope this clears your doubts.
> 0 votes

---
Tags: data-structures
---


title: Box representation in modern languages

text:
# Question
Title: Box representation in modern languages
I'm studying value representation in modern languages. The idea is that since in many situations the size of objects can be unknown, one can introduce a box representation of it. This box representation is just a block stored at the heap with a tag to identify it.

My questions is as follows: who deals with the size of the block? who decides the type of the tag? I'm pretty sure it is the runtime system who has to deal with it. But then what is done in compile time? How does a compiler represent objects at compile time?

# Answer
I'm not sure I completely understand your questions. Still:

> who deals with the size of the block?

If the compiler does not know the size, it can write the size at the very beginning the block, after (or before) the tag. Some convention must be established -- this is something that must be decided when designing the runtime system.

> who decides the type of the tag? I'm pretty sure it is the runtime system who has to deal with it.

If the type is known by the compiler, the compiler can emit code to put the right tag. Otherwise, the compiler must emit code which will compute the tag at runtime, e.g. fetching it from some other block, and store it at the start of the block.

> But then what is done in compile time? How does a compiler represent objects at compile time?

It does not have to. A compiler must emit target code which, at runtime, will deal with the tags.

Further, note that tags are not always needed. If the language is (statically) typed, the compiler might know the size and type of everything, hence there would be no need to store tags at runtime.
> 1 votes

---
Tags: compilers
---


# Question
Title: 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR
I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the question:

> In MAX-3-COLOR you are given a graph $G=(V,E)$ and your goal is to find a coloring of the vertices with only 3 colors $c: V \rightarrow \[3\]$ that maximizes the quality function $q(c)$ - The number of edges whose endpoint vertices are colored with different colors:
>
> $\sum\_{(i,j)\in E} (1\_{c(i) \neq c(j)})$
>
> Give a **probabilistic** $3/2$-approximation algorithm. (i.e $q(c)\geq 2/3 \cdot OPT$ with probability at least $1-\frac{1}{e^{k}}$ for any $k \in \mathbb{N}$

OK so up until now the textbook only talks about one probabilistic algorithm which fits the requirements - MAX-3-SAT. The textbook gives a probabilistic $8/7$ - approximation algorithm for it (for every literal, toss a fair coin and decide whether to set it to $True$ or $False$).

I also found several other sources which prove that the 3-COLOR is NP-Complete by reducing it to the 3-SAT problem. Thus I am pretty confident that MAX-3-SAT is the way to go.

According to this thread: 3 Colorability reduction to SAT I thought about doing the same thing:

> For every $x \in V$ create three literals: $x\_1, x\_2, x\_3 \in \\{{True, False}\\}$ where each literal denotes if said vertex $x$ is colored with color $i$.
>
> Then for every edge $e =(x,y)\in E$ create the following 3-CNF formula $\varphi$:
>
> $ \varphi\_e = (\urcorner x\_1 \vee \urcorner y\_1 \vee \urcorner y\_1) \wedge (\urcorner x\_2 \vee \urcorner y\_2 \vee \urcorner y\_2) \wedge (\urcorner x\_3 \vee \urcorner y\_3 \vee \urcorner y\_3) \wedge (x\_1 \vee x\_2 \vee x\_3)$
>
> And the final formula $\phi$ is:
>
> $\phi = \bigwedge\_{e \in E} \varphi\_e$

Every 3-CNF formula for an edge makes sure that the two endpoints are not of the same color and that one of them is either color 1, 2 or 3.

The thing is I don't see how this would help me. This gives me a MAX-3-SAT problem since I have a 3-CNF formula for every edge and one big 3-CNF formula for the whole graph. So technically I could use the same algorithm that was given in the textbook before

But wouldn't using the same probabilistic probabilistic $8/7$ - approximation algorithm for the MAX-3-SAT give the exact same approximation? whereas I wish to achieve a $3/2$- approximation

Thanks to anyone who helps!

# Answer
> 4 votes
If you simply uniformly at random (i.i.d) color each of the vertices of $V$ by each of the three possible colors, then for every edge $e\in E$, it's endpoint will be colored by different colors w.p. $\frac{2}{3}$, hence the expected quality of the random coloring is exactly $\frac{2|E|}{3}$. We know that the optimal quality is at most $q^\*\leq |E|$, hence this is a $\frac{3}{2}$ approximation.

# Answer
> 3 votes
Consider the greedy algorithm that loops through the vertices in arbitrary order and assigns each vertex $v$ the least popular color among its previously-colored neighbors. Each vertex $v$ gets a different color than at least $2/3$ of its neighbors, so the quality of the greedy coloring is at least $2|E|/3$. The optimal quality is trivially at most $|E|$, so the greedy coloring is *always* a $3/2$-approximation. (In particular, the greedy coloring is a $3/2$-approximation with probability at least $1-e^{-k}$ for any integer $k\in \mathbb{N}$.)

(You might object that this is not a probabilistic algorithm. Okay, whatever. In a preprocessing phase, generate a random permutation of the colors, and use this permutation to break ties in the greedy algorithm. Alternatively, flip 42 independent fair coins, and if they all come up heads, do ten jumping jacks and a lap around the football field before running the greedy algorithm.)

---
Tags: algorithms, approximation, probabilistic-algorithms, 3-sat
---


# Question
Title: Is the lambda calculus referentially transparent?
In an answer of this Reddit discussion somebody defines referential transparency (RT) as "a context $K\[ \]$ is RT if, for all $M$ and $N$ s.t. $M = N$, then $K\[M\] = K\[N\]$". Based on this definition, Lambda Calculus (LC) (and any other language with binding constructs) is non-RT.

For example, let $\Omega = (\lambda w.ww)(\lambda w.ww)$. In the expressions $(\lambda x.K\[x\]) \Omega$ and $(\lambda x.K\[\Omega\])\Omega$, we have $x = \Omega$, so given any RT context $K\[\]$ both expressions must evaluate to $\bot$. However, if we define $K\[\] = (\lambda x. \[\])(\lambda y.y)$, the first expression terminates while the second does not, proving that LC is non-RT.

Is this definition of RT wrong or LC is really a non-RT language?

# Answer
> 8 votes
Quoting the paper referenced in that thread, i.e. What is a Purely Functional Language by Amr Sabry:

> Finally, two informal definitions of purity: referential transparency and independence of order of evaluation, do not have universally agreed-upon definitions and are not considered any further. (See, however, the treatment of referential transparency by Søndergaard and Sestoft (1990).)

This refers to the paper Referential Transparency, Definiteness, and Unfoldability by Harald Søndergaard and Peter Sestoft.

So, first off, there is no "right" definition of referential transparency (especially of an entire language as opposed to a single context) to which to contrast to "wrong" definitions. Secondly, the devil is in the details, which is part of why there is no universally agreed-upon definition. Probably the main factor as alluded to by the original Reddit post is: what notion of equality should we use? Obviously using contextual equivalence would be an absurd choice for this purpose. It would make all contexts referentially transparent tautologically. Another factor is what is the domain of things we're considering plugging into the context: raw terms, $\alpha$-equivalence classes of terms, terms-in-context, closed terms? To extend referential transparency to a whole language further requires specifying what exactly the set of contexts is. Finally, often the term "referential transparency" refers (at least roughly) to what Søndergaard and Sestoft call "unfoldability". This is the ability to replace a variable with what it is bound to without changing meaning. For the pure untyped lambda calculus, this just means the full $\beta$ rule holds which is true for call-by-name but not call-by-value.

In their paper, Søndergaard and Sestoft essentially answer the above questions as follows (extrapolating to the untyped lambda calculus): equality is denotational equality with respect to a given semantics; the domain is raw terms (or perhaps $\alpha$-equivalence classes of terms, whichever the semantics operates over); contexts are as follows: $$\mathcal{K}\[\\\_\] ::= \\\_\mid (\mathcal{K}\[\\\_\]) E \mid E (\mathcal{K}\[\\\_\]) \mid \lambda x.(\mathcal{K}\[\\\_\])$$ where $x$ stands for any variable. At any rate, the upshot of these choices is that your example and psygnisfive's example fail to demonstrate a violation of referential transparency (in this sense) because the terms you are plugging in to the context are not denotationally equal in the first place. In fact, any compositional denotational semantics will guarantee that all contexts are referentially transparent in this sense. Indeed, the example from the paper of a non-referentially-transparent language also has a non-compositional denotational semantics which is "fixed" by making it compositional.

The issue with this definition for more elaborate languages, particularly languages with side-effects, is that we can almost always give a compositional semantics to a programming language. Certainly we can for the lambda calculus extended with mutable state, for example. This leads to the notion not having much bite. The lambda calculus with mutable state equipped with a compositional denotational semantics will be referentially transparent in the above sense because two expressions that have potentially different side-effects won't be considered equal in the first place.

---
Tags: lambda-calculus
---


# Question
Title: Draw a 5 × 5 grid graph. How many edges does the n × n grid graph have?
just confuse with this problem. What is n × n grid graph and how many edges it has?

# Answer
a quick google search shows a grid graph to be http://mathworld.wolfram.com/GridGraph.html

so given that a 5 x 5 grid graph would have 25 nodes we can calculate the number of edges using this formula

> A grid graph G\_(m,n) has mn nodes and (m-1)n+(n-1)m=2mn-m-n edges

(5-1)5+(5-1)5=2(5)(5)-5-5 = 50 - 10 = 40

the formula itself generalized to nxn is the answer for the second portion

> (n-1)n+(n-1)n=2nn-n-n = 2n^2-2n
> 1 votes

# Answer
The $a \times b$ grid graph has the vertex set $\[a\] \times \[b\]$, and edges of two types: horizontal edges $(i,j),(i+1,j)$ (of which there are $(a-1)b$) and vertical edges $(i,j),(i,j+1)$ (of which there are $a(b-1)$), for a total of $ab$ vertices and $(a-1)b+a(b-1)=2ab-a-b$ edges.
> 8 votes

# Answer
Start by counting the left edges and top edges, then add in the missing right and bottom edges.

For a $m \times n$ grid graph, there are $m \times n-1$ left edges (a left edge for each column at each row). Similarly, there are $m-1 \times n$ top edges. At this point, we are still missing the bottom edges for the last row, and the right edges for the last column. There are $n-1$ remaining right edges, and $m-1$ remaining bottom edges. Hence, the number of edges of an $m \times n$ grid graph is $|E\_{m \times n \text{ grid}}| = m(n-1) + (m-1)n = mn-m+mn-n = 2mn-m-n$.
> 1 votes

---
Tags: graphs, square-grid
---


# Question
Title: How do quantum computers find the global minimum?
If I understand correctly, quantum computers work by trying multiple methods of solving a problem simultaneously, using quantum superposition. However, if you try to "look" at a superposition-ed atom, you will find either one or the other-1 or 0. What I've heard is that this is random.

So, if you compute all these solutions, how do you know which is the best without "looking" at it? Wouldn't the result just be random, and you can only see the result of one answer? Now, I've heard that this can be solved by quantum annealing, but I don't really understand it. I'd like to know how this works in fairly layman-ish (It's a word) terms.

# Answer
Nope, that's not how quantum computing works. That's actually a common misconception. Sometimes people think that quantum computers work by trying all solutions in parallel and then selecting the best one, but that's not right -- that's not really how quantum computing works.

To learn more about how quantum computing works, I recommend you study Scott Aaronson's book *Quantum Computing since Democritus*, or his lecture notes on quantum computing.

Don't expect to find a one-sentence summary that is simultaneously enlightening and accurate. Quantum physics is highly counter-intuitive, so you shouldn't expect your existing intuition to necessarily help you understand how quantum computing works. Keep in mind that it's a bit unreasonable to expect an explanation in layman terms: quantum physics is tricky stuff, so your intuition from the everyday world doesn't really translate into a useful way of thinking about quantum computing.

You can also look at other questions on this site. See, e.g., Why and how is a quantum computer faster than a regular computer? and .
> 6 votes

# Answer
You can condition quantum operations on unmeasured values, without measuring them. These are called *controlled operations*, and every quantum algorithm uses them.

For example, a crucial step in Grover's algorithm is toggling the phase of the system only if all qubits are on. Doing so does not measure every qubit, or do an aggregate "is it all on?" measurement. The superposition survives.

A more concrete example: take a system in the |00\> state, hit the first qubit with a Hadamard gate so now we're in the |00\>+|10\> state, then hit the second qubit with a NOT controlled by the first qubit, so we go into the |00\>+|11\> state. Instead of destroying the superposition, the controlled operation helped us increase the amount of entanglement present.

However, don't think of controlled operations as magic beyond measurement. Controlled operations are *very very* similar to measurements. In fact, in some interpretations of quantum mechanics, measurements *are* controlled operations. It's just that controlled operations can have small controllable/reversible effects, but "measurement" implies dissipation into the environment and thus thermodynamic irreversibility.
> 3 votes

# Answer
If your question was about quantum algorithms and the paradigm of quantum computing, then there is a paper you might be interested in:

"A quantum algorithm for finding the minimum" by Durr and Hoyer https://arxiv.org/pdf/quant-ph/9607014.pdf

One pattern in quantum computing algorithms is yes, to set up the superposition of qubits as states in a register, operate on those (that is, gates operating on qubits that comprise the states), then take measurements.

The algorithm in the paper is a demonstration of the use of increasingly lowered thresholds and filtered initialized registers that are put through Grover's quantum number finding algorithm. Each iteration is followed by measurement of the first register and comparison to the threshold. The threshold is the minimum at some iteration and the total number of iterations is determined prior to the iterations to ensure success.
Using the algorithm on a list of numbers that have gaps in them, which could be a register holding pre-processed states, seems to need a larger register qubit width so the runtime complexity for input lists is larger than the usual quoted.

It looks like one of the main abilities of quantum computing will be or is combinatorial problems and what steps are needed to put the system into a certain state with high probability.

Note that if your question is hardware based, then the answer presumably depends upon the quantum computer implementation. There is a paper discussing sorting: "Sorting quantum systems efficiently" by Ionicioiu

If your question was instead about minimum of the amplitudes of all possible states at any given time (rather than the value of a state), then you'd probably be interested in the papers regarding error analysis in progress because that's an attempt to quantify the lowest probable state...

As a tangent, could consider that one of the goals is storing multiplicity of state. Atoms and molecules have rotational, vibrational, and electronic transitions and any such system needs a decent number of particles in the given state for good statistics and the system needs isolation of its parts. For example, using sound as a means to facilitate rotational transitions has as its challenge that being a pressure wave, it is quickly everywhere it can be when there is a medium to transport it. Using low frequency radiation has as its challenges the diffraction limit and near field effects... Lots of interesting research happening which may have different answers to your question.
> 3 votes

---
Tags: optimization, quantum-computing
---


# Question
Title: TF IDF Spark values are small after cosine similarity
I am creating a software that computes the cosine similarity between 2 strings.

I am using Spark as I have to use Java. I created a Bag of words model and computed the cosine similarity successfully.

Feeding the same sentences to the software and substituting the bag of words model with a TF-IDF the similarity between sentences took a hit. Some similar sentences became not similar.

Example

"a b c"

"a a b c d"

Cosine similarity using Bag of words is 0.871

Cosine similarity using TF-IDF is 0

Is this behavior correct or am I doing something wrong?

# Answer
> 1 votes
From the documentation:

> Since logarithm is used, if a term appears in all documents, its IDF value becomes 0.

So if you're only considering similarity between two strings, then you only have one document in your corpus, and either your TF value will be 0 (since the word doesn't appear in the document), or the IDF value will be 0 (since the word does appear in the document), thus all terms in TF-IDF will be 0.

If you just have two strings, then cosine similarity should be enough for you - IDF is attempting to weigh the relative importance of each word within the entire corpus (from an information theoretic perspective, it basically treats the word as appearing uniformly across the documents it appears in within the corpus - under that assumption, one can consider IDF to be a form of information gain; i.e., how many bits of information does having this term gain you, relative to selecting a document at random from within the whole corpus. If every document in the corpus has a term, then under that uniform model, providing that term in the query doesn't help you at all in narrowing down your selection).

---
Tags: algorithms, natural-language-processing
---


# Question
Title: Matrix chain multiplication and exponentiation
If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

* Free matrix variables of known dimensions
* Products of arbitrary subexpressions
* Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

---

**Edit:**

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A\_1 A\_2 \ldots A\_k)^n$, consider every cyclic permutation of the factors:

* $(A\_1 A\_2 \ldots A\_k)^n$
* $A\_1 (A\_2 \ldots A\_k A\_1)^{n-1} A\_2 \ldots A\_k$
* $A\_1 A\_2 (A\_3 \ldots A\_k A\_1 A\_2)^{n-1} A\_3 \ldots A\_k$
* ...
* $A\_1 A\_2 \ldots A\_{k-1} (A\_k A\_1 A\_2 \ldots A\_{k-1})^{n-1} A\_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.

---

**Edit:**

The idea outlined in my previous edit is still somewhat nonoptimal. The exponentiation by squaring algorithm actually evaluates expressions of the form $K A^n$ or $A^n K$, where $K$ isn't necessarily the identity matrix. But my algorithm doesn't consider the possibility of using the exponentiation by squaring algorithm with $K$ not equal to the identity matrix.

# Answer
> 3 votes
**Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided.**

The problem reduces to finding the most efficient ordering when considering the square of the product.

For example, when looking at e.g. $(ABC)^{50}$, we only need to optimally solve $(ABC)^2$ since this expands to $ABCABC$. No useful ordering information is added by concatenating $ABC$ again. The intuition here is that since the problem of optimal ordering can be solved bottom-up, higher orderings consisting of more elements using the same matrices are irrelevant.

Finding the best ordering of $ABCABC$ reduces to the Matrix Chain Multiplication problem. After finding an optimal ordering, apply exponentiation to the triplet (n-tuple generally) in the ordering.

As an e.g., if the optimal ordering for the square is $A(B(CA))BC$, the solution to the initial problem is $A(B(CA))^{49}BC$.

**In summary:**
1) The first step in solving $(A\_1 A\_2 \cdots A\_n)^m$ is to solve $(A\_1 A\_2 \cdots A\_n)^2$.
2) Solving $(A\_1 A\_2 \cdots A\_n)^2$ is best approached as an instance of the Matrix Chain Multiplication problem.
3) Using the n-tuple ordering $G$ from the solution in (2) will give us the solution to (1) as some flavor of $A\_1 \cdot A\_2 \cdot G^{m-1} \cdot A\_n$ (note that any other groupings from solving (2) should be applied as well).

**Informal proof**
Considering the simplest case using two matrices, $(AB)^n$, we note that $A$ and $B$ have dimension $X \times Y$ and $Y \times X$ respectively. Any product using $A$ and $B$ has one of the following dimensions:

$X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

We have either $X \< Y$ or $Y ≤ X$.

**Assumption 1a):** $X \< Y$
$AB$ has dimension $X \times X$, and this ordering is guaranteed to be optimal from a bottom-up approach. Any other configuration of $A$ and $B$ is either equally good, or worse. Thus, the problem is optimally solved as $(AB)^n$.

**Assumption 1b):** $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving $A$ and $B$. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

This concludes the proof, and we have only looked at the two orderings found in $ABAB$, the square problem.

Using more matrices, the argument is similar. Perhaps an inductive proof is possible? The general idea is that solving the MCM for the square will find the optimal size for the operations with all involved matrices considered.

**Case study:**

```
julia> a=rand(1000,2);
julia> b=rand(2,1000);
julia> c=rand(1000,100);
julia> d=rand(100,1000);
julia> e=rand(1000,1000);

julia> @time (a*b*c*d*e)^30;
  0.395549 seconds (26 allocations: 77.058 MB, 1.58% gc time)

# Here I use an MCM solver to find out the optimal ordering for the square problem
julia> Using MatrixChainMultiply
julia> matrixchainmultiply("SOLVE_SQUARED", a,b,c,d,e,a,b,c,d,e)
Operation: SOLVE_SQUARED(A...) = begin  # none, line 1:
    A[1] * (((((A[2] * A[3]) * (A[4] * (A[5] * A[6]))) * (A[7] * A[8])) * A[9]) * A[10])
  end
Cost: 6800800

# Use the ordering found, note that exponentiation is applied to the group of 5 elements
julia> @time a*(((((b*c)*(d*(e*a)))^29*(b*c))*d)*e);
  0.009990 seconds (21 allocations: 7.684 MB)

# I also tried using the MCM for solving the problem directly
julia> @time matrixchainmultiply([30 instances of a,b,c,d,e]);
  0.094490 seconds (4.02 k allocations: 9.073 MB)

```

# Answer
> -1 votes
If you want to calculate the product of n matrices $A\_1$ to $A\_n$ in the best possible time, you can easily calculate how many operations are needed to calculate the product of $A\_i$ to $A\_j$ for all 1 ≤ i ≤ j ≤ n in $O (n^3)$ steps.

---
Tags: optimization, dynamic-programming, linear-algebra
---


# Question
Title: Clarification regarding definition: Two way non deterministic finite state Automata
In two way non-deterministic finite state automata there is the concept of reject state.

Since an input is accepted if any one of the parallel branches in the Non Deterministic FSA reaches an accept state and the rest of the branches are then immaterial.

1. On a given Input even if one of the branches reaches the 'reject' state and the other reaches the accept state (after processing the last input symbol) what do we do ?
2. If one of the branch reaches the reject state before processing the complete input what do we do? Continue processing the other branches that might lead to accepting the input and terminate only the local branch? Or the input is rejected (similar to accept state)?

# Answer
> 1 votes
As you clearly state, an input is accepted, *by definition*, if one of the parallel branches accepts. This means that an input is accepted if and only if at least one of the parallel branches accepts. So if one brach accepts and another rejects, the input is accepted.

In non-deterministic automata, acceptance and rejection are *not* symmetric. An input is accepted iff there is *some* accepting computation path. An input is rejected iff *all* computation paths are rejecting.

---
Tags: automata
---


# Question
Title: how to interpret the coefficients of binary logistic regression?
I'm working on a kNN classifier to classify whether a text is written by a man or a woman on the basis of the most frequent words. However, a kNN doesn't show which features were the most important in the classification. I got the suggestion to fit a logistic regression on my training data and labels to see which words were the most important in the classification task.

Now I have a list of the top 20 positive words and coefficients and top 20 words with negative coefficients. I do not know how to interpret these. I can see that the logistic regression has the classes F and M (don't know which one is 0 and which is 1), but is it possible to argue that the positive coefficients belong to the F class and the negative belong to the M class?

# Answer
> 3 votes
I don't have the rep to comment, but the answer to your question is "sort of." It would take me too long to answer this question completely and with the proper care, so i will point you to a good resource http://www.appstate.edu/~whiteheadjc/service/logit/intro.htm

There is a section midway through on interpreting your regression coefficients. In your specific case (as I imagine all of your independent variables only take on positive values), your interpretation is fine. If $b\_1$ is the slope coefficient of an indicator variable for some word, then a 1 unit change in $b\_1$ (i.e. if the word corresponding to $b\_1$ is seen) corresponds to an $\exp{(b\_{1})}$ change in the log odds of your model (e.g. the probability of the person being a boy is $\exp{(b\_{1})}$ more likely). Hope this helps

---
Tags: machine-learning, classification, statistics
---


# Question
Title: Beginnings of multiptogramming and compilations for it
I want to know how the first programs to be able to execute more than one programs within a common time span were like . I went through the history of the topic and it seemed like Strachey was the first one to work on multi-programming . Hence , i thought of reading his paper "Time sharing in large and fast computers"

Where can I find this paper ?

Is it so that in multi- programming , two addresses are stored in a memory location and the program counter is sequentially switched between the values in the two locations and after the execution of instructions the value in the corresponding register is incremented ? So basically for a language to support multi-programming the keyword or function ,it should use to create concurrent programs or to make two programs run in parallel , should translate to a machine code having conditional jump instructions .

For example , a version of AlGol 60 , used "cobegin" and "coend" keywords to mean the parallel execution of two streams of instructions as follow :

Cobegin :

process 1 Begin :..... End

process 2 begin .......End

Coend

So , is it so that cobegin and coend translate to a machine code which stores the addresses of the machine codes obtained from translation of process1 and process 2 to two different registers , and use jump instruction to sequentially switch between the present values in the registers which are incremented as the programs get executed .

P.S : It would also be of great help , if someone can point towards a link where the code for the OS used by Burrough's written in ALGOL60 is available provided such a link exists .

# Answer
The early multiprogramming systems ran two or three programs simultaneously in a single computer. They did so by partitioning the memory amongst

* operating system
* one user-program
* another user-program
* ...

The user programs shared a single copy of the operating system, which provided input/output and other services through system calls, which switched the processor into a special privileged mode that can access the external hardware. Programs had to be relocatable - able to run wherever in the memory they happened to end up.

Many advances were made in the Ferranti Atlas hardware and operating system:

* virtual memory - both mapping and one-level store;
* memory-addressed hardware;
* three-level processing hierarchy: interrupt, supervisor, and user;
* SPOOLing - buffering of slow input/output devices.

Time-sharing - time-division multiplexing of processor and sometimes of computer memory - dragged behind, and proved difficult to make a success of.

Multi-tasking within a single programming model is different and developed almost orthogonally.
> 1 votes

# Answer
Multiple program execution on a single-core CPU, whether time sharing (which I generally understand to mean multiple users each seeing the computer as their own), multitasking (multiple distinct programs running for one user) or multiprogramming (multiple threads of execution inside a single program like the cobegin/coend you mention) is generally handled by having multiple threads of execution - each with its own stack, program code area (possibly shared & reentrant, but not necessarily), data area, program counter, etc.

Essentially, under either OS (time sharing, multitasking) or program control, the CPU is switched around between multiple executing processes as needed. The switching can be time based (e.g., every 1/60 of second or more or less frequently depending on the CPU and OS), interrupt driven or cooperative (programs designed to run for a short amount of time and go to sleep/hand off to the supervisor for the next process to run).

There are some other ways of doing things - multi-core CPUs can truly execute multiple tasks as the same time, 1 per CPU but often with shared memory & I/O; and massively parallel systems may really have methods where small groups of instructions (or even individual instructions) are applied to multiple CPUs at the same time, with each operating on a different chunk of memory, but typical multitasking is in some ways not much more complex than CPU being interrupted for peripheral I/O.

In the case of the cobegin/coend example, I assume that two separate processes (again, could be OS control or program control depending on the OS capabilities) are spawned and the main program simply waits until all processes have been reported as completed.
> 0 votes

---
Tags: multi-tasking
---


# Question
Title: Distribution of beans in jars to k members
Here is the problem. We have N jars. Each jar can have any number of beans. These beans have to be distributed among C children. The resulting distribution should serve two goals Now

* the number of beans that each child gets must be the same (+/- 1 when total number of beans is not a multiple of C)
* each child to get all the beans from minimum number of distinct jars. Why? It is possible that beans in a jar may be contaminated. We want as few children to get infected as possible. E.g. if we have two jars with N beans each and two children, each child gets N beans. we would want child one to get N beans from jar 1 and child two to get beans from jar 2. As opposed to a solution, wherein child 1 gets half beans from jar 1 and half beans from jar 2. In former solution, if jar 1 is contaminated, only child 1 is infected. In latter solution, both children are infected.

So if

```
C = 5
beans = {B0:12, B1:12, B2:12, B3:12, B4:12} // Jar:<Bean-Count>

```

Distribution should be

```
{C1:{B0:12}, C1:{B1:12}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

```

Because each child has beans from exactly one jar. Following distribution will be less preferred

```
{C0:{B0:6, B1:6}, C1:{B0:6, B1:6}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

```

What will be the algorithm for achieving the distribution strategy with above goals in mind?

# Answer
If this is a practical problem, it can be solved using integer linear programming (ILP).

We'll introduce three kinds of integer variables:

* $x\_{i,j}$ counts the number of beans from jar $i$ that are given to child $j$.
* $y\_{i,j}$ is 1 if child $j$ gets any beans from jar $i$, or 0 otherwise.
* $z\_i$ is the number of children who get at least one bean from jar $i$.

Then we'll add some constraints to enforce the requirements in the question:

* $\lfloor B/C \rfloor \le \sum\_i x\_{i,j} \le \lceil B/C \rceil$ where $B$ is the total number of beans across all the jars. This ensures that each child receives the same number of beans.
* $0 \le x\_{i,j} \le B\_i y\_{i,j}$, where $B\_i$ is the number of beans in jar $i$, and $0 \le y\_{i,j} \le x\_{i,j}$. This ensures that $x\_{i,j}$ and $y\_{i,j}$ are consistent with each other.
* $\sum\_j x\_{i,j} \le B\_i$. This ensures that you don't give out more beans from jar $i$ than are available.
* $z\_i = \sum\_j y\_{i,j}$.

Finally, the objective function is the average of the $z\_i$'s, i.e., $\frac{1}{N} \sum\_i z\_i$. We feed this to an integer linear programming solver and ask it to minimize the objective function, subject to the constraints above.

The worst-case running time of ILP solvers is exponential time, but in practice they are sometimes much more efficient than you might think. If you have $N,C \< 50$, I suspect this might be efficient enough to work in practice. The only way to find out for sure is to try it.
> 1 votes

---
Tags: algorithms, heuristics
---


title: Pseudocode for graph chase algorithm

text:
# Question
Title: Pseudocode for graph chase algorithm
Input: undirected graph $G$, starting node $j$ for Justin Bieber (JB), and starting nodes for 4 fans $f\_1, f\_2, f\_3, f\_4$.

This problem has turns: for every turn, JB can either stay at his current node or move 1 node adjacent. Fans are working together and follow the same rules, but can share the same node. The fans are trying to occupy the same node as JB, and if any one of them achieves this, JB loses (Yes, you are on Justin's side for this problem!).

If both JB and his fans always have knowledge of the locations of everyone else, decide if it's possible for JB to avoid his fans indefinitely, no matter what his fans' strategies are. Your pseudo-code algorithm must be bound by a polynom in graph size $n+m = |V|+|E|$

---

This was a tricky, original problem from our algorithms class I'm really interested in. I was thinking that one way JB could avoid all the fans was if the graph was laid out in a way so that he and all his fans would go in a cycle forever, with JB at the front. But we weren't given the strategies for the fans though, so I'm just assuming they move in whatever direction that brings them closer to JB's location (but could there be a more complicated strategy they use, like box him in somehow?) I'm thinking for the pseudo code it should somehow decide whether JB and his fans can make such a cycle, but any help would be greatly appreciated.

# Answer
Hint: What's the size of the state space?

The state of the world at any point is determined by \_____. Therefore, there are \____ many possible states.

Fill in the blanks, then think about how to use those facts to help you devise an algorithm.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is this "cycle" condition sufficient for unique minimum spanning tree?
Given a connected, undirected, weighted graph $G$, the condition

> The maximum-weight edge in any cycle of $G$ is unique.

is *not necessary* for $G$ to have a unique minimum spanning tree (MST).

However, is this condition *sufficient* for $G$ to have a unique MST?

# Answer
***Answer My Own Question*** by attempting to prove that the condition above is sufficient for a graph $G$ to have a unique MST. ***I am asking for reviews.*** Thanks in advance.

First, for each cycle, the unique heaviest edge in it must be not in any MST. Consider the remaining graph $G'$, obtained by keeping removing the unique heaviest edges in cycles from $G$. All MSTs are part of $G'$. If we can show that $G'$ is a spanning tree, then $G'$ is the unique MST of $G$.

$G'$ is connected because each edge removed belongs to a cycle when it was removed.
$G'$ is acyclic because we are keeping breaking cycles. Thus, $G'$ is a spanning tree.
> 2 votes

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


# Question
Title: Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?
Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that $$\forall s\_1,s\_2 \\; \exists i \in \\{1,\cdots,n^c\\} \\; f\_i(s\_1)\neq f\_i(s\_2),$$ Where two strings $s\_1,s\_2$ have length $2^n$ and $\forall i\in\\{1,\cdots,n^c\\}, \\; f\_i(s\_j)\leq n^d, \\; j\in \\{1,2\\}$?

It seems a little similar to hash functions but since we don't have any restrictions (e.g. having uniform distribution or being oneway) our hands are open to define whatever we like.

I think *it's not possible*. Because we have $2^{2^n}$ strings of size $2^n$ and transformring them into polynomial size strings means we have put many strings in a single string. But when I make an example this comes to my mind that maybe by defining a good design for each function we can recognize the difference by probability one.

One example can be:

For $c=3$ and $d=1$,

$f\_1$: it takes string of length $2^n$ and transforms it to $mod\\, n$.

$f\_2$: it takes string of length $2^n$. (suppose we have divided $2^{2^n}$ strings into $\frac{2^{2^n}}{n}$ collections) If the input belongs to $i$th collection, $f\_2$ transforms it to $i$.

$f\_3$: it takes string of length $2^n$ and transforms it to the number which shows its $1$s number.

The probability that for two strings $s\_1$ and $s\_2$, these three maps $f\_1, f\_2,f\_3$ be the same would be $$\frac{1}{n}\times \frac{1}{n} \times \frac{1}{2^{2n}}$$ That is negligible.

So my question is that *can we ever understand the difference of two long strings with probability $1$ using polynomial size strings*?

# Answer
> 2 votes
There is no sequence of functions $f\_1,...,f\_{n^c}:\\{0,1\\}^{2^n}\rightarrow\\{0,1\\}^{n^d}$, such that for all $s\_1\neq s\_2\in\\{0,1\\}^{2^n}$ $\exists i\in\\{1,...,n^c\\} : f\_1(s\_1)\neq f\_i(s\_2)$.

Examine the function $F:\\{0,1\\}^{2^n}\rightarrow \prod\limits\_{i=1}^{n^c}\\{0,1\\}^{n^d}$ defined by $F(s)=\left(f\_1(s),f\_2(s),...,f\_{n^c}(s)\right)$.

The domain of $F$ is of cardinality $2^{2^n}$, while its range is of cardinality $\left(2^{n^d}\right)^{n^c}=2^{n^{c+d}}$. Since for large enough $n$ it holds that $2^{2^n}\>2^{n^{c+d}}$, $F$ is not one to one, and thus the condition is not satisfied.

---
Tags: probability-theory, hash, hashing
---


# Question
Title: Hit/Miss in a 2-way set associative cache with offset
"In a 2-way set associative cache of 4 blocks containing 4 words each, which one of these addresses will return a hit when being read? The blocks to be retained in the cache are decided by LRU."

4 word / block means that the offset = 2 bits.

2-way means 4 blocks / 2 = 2 sets. The index then needs 1 bit.

And thus the tag is 3 bits, since we're dealing with 6 bits adresses.

What I'm not too sure about is the hit/miss part. In such a case, do we need to have an exact match for the Index, the Tag **and** the Offset to get a hit?

Or is a hit encountered as soon as the Index and the Tag match?

If it is the latter then what role plays the offset in such a situation?

# Answer
> 2 votes
No, you don't need to have a match for the offset. When you 'miss' some address (= when its not in the cache) , the whole block is copied from the memory to the cache. i.e for address $001111$ , we will copy the 4 word block: $001100$ , $001101$ , $001110$, $001111$ to the cache. Therefore, for example, in line 4 you get a 'hit', not a miss.

So a hit is encountered as soon as the Index and the Tag match. The offset tells you which word from the block you want to read, as there are 4, and you want only 1. for example, for $001111$ it will skip the first 3 words and read the fourth.

EDIT: if I remember correctly, in a 2-way you need 3 offset bits and not 2. 1 bit is 'block offset' so you know in which block of the 2 has your word (because there are 2 blocks with same tag and index).

---
Tags: cpu-cache
---


# Question
Title: Is this “cut condition" sufficient for unique minimum spanning tree?
Given a connected, undirected, weighted graph $G$, the following "cut condition"

> For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.

is *not necessary* for $G$ to have a unique minimum spanning tree.

However, is this "cut condition" *sufficient* for $G$ to have a unique MST?

---

Related post: Is this "cycle condition" sufficient for unique minimum spanning tree?

# Answer
> 2 votes
*Answer my own question*: The answer is from here.

For every cut of $G$, the unique light edge crossing the cut must be part of every MST of $G$. Consider the set $T$ of edges, containing the unique light edge crossing each cut $C$ of $G$. Then, we know that $T$ is a subset of every MST.

Now we can show that $T$ must be equal to every MST.

Because there is exactly one edge of $T$ crossing every cut of $G$, the graph $(V, T)$ must have exactly one connected component: if there were two unconnected components $V\_1$ and $V − V\_1$, then the cut $(V\_1, V − V\_1)$ would not be crossed by any edge of $T$, which contradicts the definition of $T$. In addition, $T$ cannot contain any cycles: the heaviest edge on a cycle in $T$ cannot be the unique lightest edge in any cut. Then $T$ itself must be a spanning tree of $G$. Because $T$ is a subset of all minimum spanning trees of $G$, it must be the unique MST of $G$, as any additional edge added to $T$ would form a cycle, making it no longer be a tree.

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


# Question
Title: Time complexity of $T(n) = nT(n-1) + n^2$
This time complexity comes from $N$-queen problem. There are many threads talking about the time complexity to be $O(n!)$ but I cannot figure out how we get it. Here is the progress I have so far:

$$ \begin{align} T(n) & = n T(n-1) + n^2\\ & = n(n-1)T(n-2) + n(n-1)^2 + n^2\\ & \vdots\\ & = n! + n! + n(n-1) \dots 2^2 + n(n-1) \dots 4\*3^2 + \dots + n(n-1)^2 + n^2 \end{align} $$

RHS and LHS divided by $n!$

$$ \frac{T(n)}{n!} = 2 + \frac{2}{1!} + \frac{3}{2!} + \dots + \frac{n-2}{(n-3)!} + \frac{n-1}{(n-2)!} + \frac{n}{(n-1)!} $$

From comments in GeeksForGeeks the RHS converges to a constant. Can anyone please explain why the RHS converges to a constant?

# Answer
The RHS does converge, you can prove it using the Ratio test which says

> for series of non-zero numbers $\sum a\_n$ with $$\rho = \lim\_{n \to\infty}\frac{|a\_{n+1}|}{|a\_n|}$$ for $\rho$ finite or infinite follows that
>
> $\rho\<1$ series converges absolutely
>
> $\rho\> 1$ series diverges
>
> $\rho=1$ inconclusive

In OP's case the ratio $$\rho=\frac{(n+1)(n-1)!}{n(n!)} =\frac{(n+1)(n-1)!}{n^2(n-1)!}$$

$$\lim\_{n \to \infty}\rho=0$$ Therefore the series converges.
> 3 votes

# Answer
We can compute the limit explicitly: $$ 1 + \sum\_{n=0}^\infty \frac{n+1}{n!} = 1 + \sum\_{n=0}^\infty \frac{1}{n!} + \sum\_{n=1}^\infty \frac{1}{(n-1)!} = 2e + 1. $$
> 4 votes

# Answer
**(skip to Part II)**

You might find it easier to think about it this way.

First think of the definition of $n!$

$n! = n(n-1)!$

where $1! = 1$

The ! "operator" is just a notation convenience, it might as well have been written as $R(n)$

$R(n) = nR(n-1)$

where $R(1) = 1$

The idea so far is that $n! = R(n)$

Then think of the definition of $T(n)$ and how it relates to $R(n)$ (or $n!$)

$T(n) = nT(n-1) + n^2$

$T(n) \> nR(n-1) + n^2 = n! + n^2$

$T(n)$ is greater than $R(n)$ because of the $n^2$ term on every iteration. With this you have already proved that $T(n)$ is at least $O(n!)$

This doesn't proof $T(n)$ is $O(n!)$ as you might need a bigger function.

**Part II**

By the definition of big-O we're now interested in proving there exists constants $c$ and $k$ such that $T(n) \leq cn!$ for $n \geq k$.

$T(n)/n! \leq c$

expanding $T(n)$ you'll find

$T(n)/n! = (nT(n-1) + n^2)/n! = nT\_{n-1} / n! + n^2/n! = T\_{n-1}/(n-1)! + n^2/n!$

You can expand that a couple more times to realise $T\_n/n! = T\_{n-k}/(n-k)! + \sum\_{i=0}^{k-1}{(n-i)^2/(n-i)!}$

With $k = n - 1$ and defining $T\_1 = 1$ as the base case:

$T\_n/n! = 1 + \sum\_{i=0}^{n-2} {(n-1)^2/(n-1)!}$

The summation term converges (in each "iteration" it grows less and less), that guarantees that if we find a $c$ for a given $k$, then it will also work for all $n \geq k$. To find $c$, just substitute $n$ on the above equation for any value you'd like $k$ to have.
> -1 votes

---
Tags: recurrence-relation
---


title: Question on digital DE-MULTIPLEXER!

text:
# Question
Title: Question on digital DE-MULTIPLEXER!
How does a demultiplexer ignore/discard/block the non-required outputs? A demultiplexer channels the input to one of the outputs, but there are several outputs. When one output is selected (depending on the state of the select line(s)) then rest of the outputs are 0/low (am I right?). Now, if the input is 0/low then the selected and non-selected outputs all becomes 0/low. How does the demultiplexer perceive the final result in such a case??

Please explain in details (with reference to 1:2 demux if possible). Thank You!

# Answer
> 1 votes
It's just AND gates. So, assuming $in$ is the input, $sel$ is your selector bit, and $out\_1$ and $out\_2$ are your two possible outputs, you would get:

$out\_1 = in \land \lnot sel$

$out\_2 = in \land sel$

The idea is that, if $in$ is $0$, out must always be $0$. If $in$ is $1$, then we have to output it to the proper gate. If you had a larger demux, you would simply have more selector bits. So, for a demux with 16 outputs, we would need 4 selector bits: $sel1$, $sel2$, $sel4$, and $sel8$. Output 10 would thus be a 5-input `AND` gate:

$out\_{10} = in \land (sel\_8 \land \lnot sel\_4 \land sel\_2 \land \lnot sel\_1)$

The other outputs would be blocked because they would have different combinations of $sel1$, $sel2$, $sel4$, and $sel8$ `AND`ed into their outputs.

---
Tags: circuits
---


# Question
Title: Finding a trapdoor function for the 3-partition problem
I am working on a cryptography project. Let's say I want to build a public key cryptosystem using the 3-partition problem, which is NP-Complete, as a basis (just like RSA uses integer factorization).

Now, I am having trouble coming up with a trapdoor function that helps me enconde it. Let's say I have $T=\\{t\_{1}, t\_{2},...,t\_{3n}\\}$ and a solution $S=\\{S\_{1}, S\_{2}, ..., S\_{n}\\}$, where every $S\_{i}$ contains 3 elements of $T$ and $\sum\_{k=1}^{3} S\_{ik} = \sum\_{k=1}^{3} S\_{jk}=x$.

Now, let's assume the user creates $T$ and $S$, and of course also knows $x$. He can use either $x$ or $S$, or both, as a private key, and send $T$ and the public key for enconding.

I want to find a "function" that in one way requires finding $S$ or $x$ from $T$, and the other way can be done only with $T$. That is, given a plaintext $p$, $f(p, T)=c$ and $g(c, S)=p$ (I don't know if $f$ and $g$ have to be inverse of each other necessarily).

The cryptisystem does not have to be super-secure or have no flaws, I'm just looking for a function/encoding that does this in whatever way. For example, the MH knapsack cryptosystem uses some kind of alternate way to write the subset sum problem as a sum like $V=a\_1x\_1,..., a\_nx\_n$.

Thanks for reading.

# Answer
As Yuval says, it's an open question whether one can build a public-key cryptosystem whose security is based on the assumption that $\textsf{P} \ne \textsf{NP}$. There is no known public-key cryptosystem with that property, though many cryptographers have tried to find one. So, you're trying to solve a problem that is likely to be extremely hard to solve.

Part of the challenge is that NP-complete problems are generally hard, but that's not enough for cryptography. Public-key cryptography also requires that there be a "trapdoor" that makes them easy. So, you'll need to find a way to encode a secret trapdoor in the 3-partition instance that makes it easy to solve the 3-partition problem if you know the trapdoor -- but where you can prove that the existence of the trapdoor doesn't make the problem any easier for people who don't know the trapdoor. It's not clear how to do that. There are ways to embed a trapdoor, but then they require choosing 3-partition instances with a particular structure/format, and then solving those special instances might be easy (might be doable in polynomial time).

You might be interested in knapsack cryptography (see the knapsack tag on Crypto.SE), Impagliazzo's five worlds, this question on Crypto.SE, and Impagliazzo and Rudich's black-box separation between one-way functions and key exchange, which provides some kind of evidence that it's likely not going to be easy to do what you want (e.g., there's no black-box way to convert a NP-complete problem to a public-key encryption algorithm).
> 2 votes

---
Tags: complexity-theory, cryptography, encryption
---