title: How does a computer work?

text:
# Question
Title: How does a computer work?
I have been a computer nerd for many many years. I can program in quite a few languages, and I can even build them. I sat down with a buddy the other day and asked how a computer actually takes electricity and does something with it, and we just couldnt figure it out, and Google wasn't much help either.

I mean, how does a computer take a constant flow of electricity and turn it into 1's and 0's and then actually do something with those 1's and 0's like turn a light on for 15 seconds?

I understand *gates* (AND, OR, NOR, NAND, NOT) and a little about *diodes*, *resistors* and *transistors*, but I figured this would be the perfect place to have it explained in true laymens terms!

Can anybody point me in the right direction or give me a brief explanation?

# Answer
This is a broad question that does not have an easy answer; it's a long way from electrons skittering along copper wires to rendering a website in Firefox. I will attempt to give you an overview from bottom to top and point you towards the right things to look up.

### Encoding Numbers

The basic motivation is to compute things, as in doing arithmetics¹. The first thing to look at is how to represent numbers. There have been many approaches, using decimal or ternary and I think even octal systems, but in the end, binary won out. Now we know we have to build devices that deal with two values -- let's call them $0$ and $1$.

Note that there are also multiple ways to encode numbers in binary. After you build up your first processor, you realise advantages of doing things in certain ways. Popular examples are the two-complement and IEEE floats. For starters, restrict yourself to plain natural numbers.

### Gates

Assume we use binary encoding. Think of how you learned adding in primary school and write down the same for binary numbers. As it turns out, the building blocks of Boolean algebra are already there for you; it is easy to build a basic adder (and other arithmetic functions) using logic gates.

How to build such gates is outside of the scope of computer science; eletrical engineering has provided multiple solution using e.g. tubes or transistors. Head over to Electrical Engineering Stack Exchange for questions on this.

### Clock and State

Not all gates are equally fast and not all parts of a computation have the same number of gates. Therefore, we have to take extra care that individual operations do not overtake each other. It has proven useful to use a global clock; the result of a given network of gates is the state of the output wires at the end of the cycle (which may change wildly while the gates cascade towards their individual final states).

That means that results of one cycle may have to be stored until the next cycle starts, e.g. if you wire up loops. There are a number of basic elements you can use to varying effect, all build up from gates; some are called flip-flops. Those are also used to build registers, elements that store numbers for as many clock cycles as needed.

### Architecture and Commands

Now you have a myriad of design choices to make. What arithmetic operations does your processor provide? What do your commands look like? It may be educational to look at the MIPS architecture whose early forms are easy compared to other designs. Have a look at the plans:

Original from http://ube.ege.edu.tr/~erciyes/CENG311

Essentially, it's fetching and and disassembling commands, a set of registers, an ALU and control. Commands encode which ALU operation to perform on which operands (by the number of the register they are held in), how to manipulate the program counter² or which register to load/store from/to memory³.

### Further Considerations

By now you have a working processor in the modern sense, assuming you figured out how to build a memory and a way to feed it commands. On its way to a modern machine, many choices have to be made. Here are some:

### Alternatives

The above is heavily influenced by how history turned out. In a different world with different minds, computers may work differently. In fact, there is a plenty of models of computation, some of which have advantages that make them useful as abstraction for real machines in many cases. There are also attempts to imitate the way our brains work, that is to enable neural computing, or more generally to exploit problem-solving and information-storing strategies observed in nature, most prominently DNA and quantum computing.

So maybe (hopefully?) the information above is all ancient history another 50 or 100 years from now.

---

1. All the fancy things we do with computers today are broken down into many small arithmetic tasks which the processor executes one by one.
2. If your model allows the program to manipulate control flow, this would be the memory address the processor gets the next instruction from. You can also conceive machines that only read a fixed set of instructions from, say, a tape. In fact, early implementations did that. No jumps meant no loops; a program was a completely unrolled/unfolded series of instructions depending on the data. Obviously, being able to use the same program for multiple input data is more powerful.
3. Assuming you have memory; your processor works fine without but can then only deal with so many values at once. Early computers did read in all their data from tapes and kept them in registers. There was no memory, let alone writable, persistent storage as we know it today.
> 49 votes

# Answer
The complete picture is fairly complicated. There are many layers built on top of one another that collectively implement high-level abstractions on top of electrical voltages. There is no simple explanation of how everything is put together, especially considering that computer hardware and software has evolved dramatically in the past fifty years.

If you're interested in seeing how everything is put together, you might want to check out *The Elements of Computing Systems*, a book that starts with NAND gates and progressively builds up a working implementation of Tetris on top of a compiler and operating system that you also build. Each piece of the computer is built on the previous one, which might help you see how everything works.
> 26 votes

# Answer
The podcast Security Now! did a series on how computers work, starting with base principles.

* 233 \- Let's Design a Computer (part 1)
* 235 \- Machine Language
* 237 \- Indirection: The Power of Pointers (not technically part of the series)
* 239 \- Stacks, Registers & Recursion
* 241 \- Hardware Interrupts
* 247 \- The “Multi”-verse
* 250 \- Operating Systems
* 252 \- RISCy Business
* 254 \- What We'll Do for Speed

The gaps in the numbers is because every other episode is a Listener Feedback episode so you may want to watch those too. Also between 241 and 247 they did a few episodes about SSL due to the breaking news at the time about countries compelling CA to give root certs to them.

Also EP. 248 is the "Portable Dog Killer" which does not kill dogs, but a sonic beam weapon that Steve made on his own as a child to help teach a neighbor dog not to run up to the fence line and try to attack people on the sidewalk.
> 9 votes

# Answer
A computer works by manipulating energy gradients (which we then interpret as 1's and 0's) in a **consistent**, **defined** way. It's the *consistency* which defines a computer, while it's the *definition* which separates the different processors.

Also, learn about how just two logic gates (OR, and AND) are sufficient building blocks to build up any general-purpose computer. See also, Danny Hillis and the Tinkertoy computer.
> 5 votes

# Answer
A computer is a large *synchronous logical system*, which means that

* it manipulates $0/1$ information in the form of electric signals using the rules of Boolean calculus,
* it operates with a (very fast) clock so that all signals are sampled at discrete moments to ensure coherence.

The $0/1$ information is represented by two electric voltages and the Boolean operations are implemented by means of transistors (forming digital circuits).

It has specialized circuits to retain information as long as the computer is powered (RAM, in huge amounts). It has specialized circuits to perform binary arithmetic (actually the bits are handled in groups - typically in multiples of 8 - that collectively represent an integer number). And it has specialized routing capabilities (busses) based on memory addresses, which are nothing but integers.

Last but not least, a modern computer has a program also stored in RAM, which is a list of instructions coded as integers, which is executed sequentially, typically fetching data from memory, performing some arithmetic and sending the results back to memory.

In your scenario, one could think of an implementation where the elapsed time is stored somewhere in RAM and the program instructs to

* fetch the elapsed time value,
* increment it with an adder,
* compare it to a predefined delay with a comparator,
* return to the starting program address in case of inequality (i.e. "loops"),
* otherwise set a specialized signal which goes to an external switch rather than RAM.

---

Note that all these elements nowadays achieve a high degree of sophistication, and every sentence in this very brief overview deserves several *books* of explanations.
> 4 votes

# Answer
There are several ways to do a delay function or convert the binary data to decimal data or signal strength. When you input value "15", the computer displays a bitmap image of the number 15 on the screen. This is actually the binary value, at the moment the binary code of your keyboard also sent to cpu. It will be parsing the data then turning the code to ALU (arithmetic logic unit) processing unit to convert it to a pulse to DAC chip. The analog signal is now being controlling the frequency (the frequency from khz to hz) of a flip-flop circuit. Now the frequency output will be directed to the RAM, and the cpu read RAM to match if the data is "1111". So that's 4 seconds.
> -1 votes

---
Tags: computer-architecture, education, reference-question
---


# Question
Title: Is selection in genetic algorithm considered to be a genetic operator?
It is listed as such in wiki, however my literature never refers to it as such. My gut tells me to follow papers and monographs on the matter, but my concern is that I will make an easily avoidable mistake, or that I simply misunderstood the text.

# Answer
> 3 votes
One of my first Google hits is a widely-cited article:

Eberhart, Russell C., and Yuhui Shi. "Comparison between genetic algorithms and particle swarm optimization." In International Conference on Evolutionary Programming, pp. 611-616. Springer, Berlin, Heidelberg, 1998.

The third paragraph of the article says:

> Regardless of the specific implementation, it is generally agreed that GAs utilize one form or another of three operators: selection, crossover, and mutation.

# Answer
> 1 votes
There's no authorized body to pronounce the truth on this sort of thing. Personally, I would say it absolutely is a genetic operator. Someone else might disagree. I don't thing either is objectively wrong or makes one look amateurish or silly.

---
Tags: genetic-algorithms
---


# Question
Title: Are Epsilon-NFAs a way to make designing NFAs easier?
It seems that their purpose is in making designing certain NFAs less onerous? Does this mean that no automata that are implemented have Epsilon-transitions, and that they are kind of a mathematical conceit we adopt for our own ease of design? I'm having a lot of trouble understanding what is "happening" when an Epsilon-transition occurs - is it a way of saying, "have the NFA now switch, automatically, to this next state"?

EDIT: I'm a CS student taking CS Theory for the very first time, so apologies if this question is very rudimentary. I'm a narrative person and I often understand abstract ideas through examples or by trying to understand the problems the ideas are engaging with. I ask very basic questions, but those questions help me hook into the ideas I'm studying.

# Answer
> 4 votes
Yes, $\epsilon$-transitions can make designing NFAs less onerous, in cases where you just need *any* NFA recognizing a particular language.

But no, that is not their only purpose. NFA can be used to directly model real-world system behavior, and indeed, in those models, $\epsilon$-transitions represent silent state changes: ones that may happen, but that do not happen in response to receiving any input.

For instance, the coffee machines where I work can be modeled as state machines, with the user's actions as inputs. When operating, and operated, as intended, they are deterministic, responding to each input by making the state change requested by that input every time. This is what makes them usable as machines. But neither users nor the machine always play by the script, and that is when $\epsilon$-transitions happen.

For instance, when the user does nothing for too long, the system will spontaneously revert to its initial state. This will be an $\epsilon$-transition, unless we regard doing nothing for too long as an input to the machine, which seems strange.

Another example: without network connectivity, the machine refuses to serve coffee; losing and regaining network connectivity may happen at any time and no user input is involved, so it will be modeled as $\epsilon$-transitions as well.

# Answer
> 4 votes
An epsilon-NFA is a mathematical formalization. Mathematics doesn't have a purpose, per se.

Why do we use this formalization? Sometimes, because it is convenient. Yes, it sometimes makes designing certain NFAs less onerous, and that's useful. So, yes, your suggested rationale/motivation is reasonable. It also makes some algorithms (e.g., Thompson's construction) simpler and easier to understand. It's also intellectually interesting to know what power epsilon-transitions add. There are multiple reasons why one might study this concept; different people might have different reasons for studying it at any point in time. See also Why is non-determinism useful concept?.

What is "happening" when we execute an epsilon-transition? Well, a NFA is not a physically implementable machine; it is an abstract concept. So it is hard to map it to physical, real-world intuitions. See also Why NFA is called Non-deterministic?.

---
Tags: finite-automata
---


# Question
Title: Simple discrete math problem: A and B in 3CNF
I need to write (A and B) in 3CNF, and for whatever reason, I can only come up with (A or B) in 3CNF (A OR B OR X) AND (NOT(X) OR A OR B). Any help is greatly appreciated!

# Answer
How about $(A \lor A \lor A) \land (B \lor B \lor B)$?

If you need three different variables in each clause, you can use

$$ (A \lor x\_1 \lor x\_2) \land (B \lor x\_1 \lor x\_2) \land \\ (\lnot x\_1 \lor y\_1 \lor z\_1) \land (\lnot x\_1 \lor y\_1 \lor \lnot z\_1) \land (\lnot x\_1 \lor \lnot y\_1 \lor z\_1) \land (\lnot x\_1 \lor \lnot y\_1 \lor \lnot z\_1) \land \\ (\lnot x\_2 \lor y\_2 \lor z\_2) \land (\lnot x\_2 \lor y\_2 \lor \lnot z\_2) \land (\lnot x\_2 \lor \lnot y\_2 \lor z\_2) \land (\lnot x\_2 \lor \lnot y\_2 \lor \lnot z\_2). $$
> 3 votes

---
Tags: logic, discrete-mathematics
---


# Question
Title: Merging sorted arrays and finding Big O bounds
Say we have $x$ amount of sorted arrays, each with $n$ elements, and we combine them one at a time. So merging the first two arrays would give us $2n$ in terms of cost, and $3n$ for the next array, all the way until $xn$ for the cost of merging. How would one go about finding the tightest possible Big-O bound for the cost of all the merges? I don't know how to go about this, I have tried writing an equation for the sequence, and that might be where I am going wrong. The sequence would look something like $2n+3n+4n \dots +kn = n(2+3+4+5+ \dots +k)$ and I'm not sure where to go next.

# Answer
**In case the order of the elements does not matter:**

I assume your arrays are not sorted and you don't care of the order of the elements when you merge them.

If you store your arrays as a linked list, then merging `list1` and `list2` takes $O(1)$ time: you just point `list1`'s tail to `list2`'s head or vice versa depending how you are going to merge. So for $x$ arrays it wil take $O(x)$ time.

If you initially store them as $x$ separate static arrays (by static I mean their size is fixed and the arrays do not grow) then at each step you will need to create a new array of larger size to combine two previous arrays by copying each element one-by-one. Thus, initially it will take $2n$ steps, then $3n$ an so on. Then the total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

If your array is dynamic, i.e., you can append one element to the end of the arrays in $O(1)$ time, then you just append all elements to the first array in $O(nx)$ time.

**In case the arrays are sorted and the order of the elements does matter:**

The underlying structure does not provide an advantage, whether it is a linked list or dynamic array. Again assume that elements are stored as $x$ separate static arrays. Then we merge two arrays like in the Merge sort algorithm. The total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

But you could use the same procedure exactly like in the Merge sort algorithm by pairwise merging arrays at each stage. This will take $O(nx\log\_2{x})$ time.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, arrays
---


title: Closure operator and set of fixpoint

text:
# Question
Title: Closure operator and set of fixpoint
In chapter 2.2 of

*Giacobazzi, Roberto; Ranzato, Francesco*, **Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements**, Inf. Comput. 145, No.2, 153-190 (1998). ZBL0921.68057.

it's said:

> An (upper) closure operator (or simply closure) on a poset $C$ is an operator $\rho:C \to C$ monotone, idempotent and extensive (i.e., $\forall x \in C . x \le \rho(x)$). We denote by $uco(C)$ the set of all closure operators on the poset $C$. **If $C$ is a complete lattice then each closure operator $uco(C)$ is uniquely determined by the set of its fixpoints, which is its image $\rho(C)$**

Where can I find a proof of the phrase in bold?

# Answer
> 4 votes
There is an intimate connection between closure operators and complete lattices.

Given a closure operator $C$ on a set $X$, we can construct a complete lattice $L(C)$ as follows:

* The points of the lattice are the fixpoints of $C$.
* The meet of the lattice is $A \wedge B = A \cap B$.
* The join of the lattice is $A \vee B = C(A \cup B)$.

Conversely, given a complete lattice $L$ of subsets of $X$, we can construct a closure operator $C:=C(L)$ on $X$ using the formula $$ C(A) = \bigcap \\{ B \in L : B \supseteq A \\}. $$

It turns out that these two operators are inverses: $C(L(C)) = C$ and $L(C(L)) = L$.

In particular, this shows that $C$ is determined by the set $L(C)$ of fixpoints, since $$ C(A) = \bigcap \\{B \in L(C) : B \supseteq A\\}. $$

(This information is taken from the sample chapter of M-solid varieties of algebras by Koppitz and Denecke.)

---
Tags: closure-properties, lattices
---


# Question
Title: What can't be done with a neural network
This reference from the german wikipedia article on neural networks states:

> There are also many other important problems that are so difficult that a neural network will be unable to learn them without memorizing the entire training set, such as:
>
> * Predicting random or pseudo-random numbers.
> * Factoring large integers.
> * Determining whether a large integer is prime or composite.
> * Decrypting anything encrypted by a good algorithm.

**Can someone explain, why this limitation should hold for all kinds of neural networks and for any advances in the future?**

**Are there any formal possibilities to prove that this problems cant be solved with a neural network?**

Lets look at the third note. There are many insights on the distribution of prime numbers and this paper shows, that the calculations for proving that an integer is a prime number, can be done in polynomial time (PRIMES is in P). So why is this problem "to difficult" to be solved by a neural network?

# Answer
This paper introduces a finite size neural network and proves that it can simulate a Turing Machine, meaning that this NN is Turing complete. Thus anything that may be computed using TMs can be computed by this type of NNs. You may want to read this too.
> 2 votes

---
Tags: complexity-theory, artificial-intelligence, neural-networks
---


# Question
Title: Is it possible to prove closure of decidable languages under union and intersection, using enumerators?
We can use multi-tape enumerators. *(Of course it is not valid to use turing machines albeit the fact that any enumerator has an equivalent TM)*

What we need is to prove that if $A$ and $B$ are decidable then $A\cup B$ and $A\cap B$ are also decidable.

Can it be done? If so, what is a possible approach?

# Answer
> 2 votes
Given a decidable language $L$ consider the following enumerator:

```
EnumL
 loop on strings x over 0 and 1 in canonical/lexicographic order
   if x in L then print x
 end
end

```

This procedure enumerates/emits all strings in $L$ in lexicographic order. So you can decide if $x \in L$ by running `EnumL` until it prints the first string of length $|x| + 1$. If it does print $x$ until that time then it means $x \in L$, otherwise $x \notin L$. Thus, using both enumerators `EnumA` and `EnumB` you can decide $x \in A\cup B$ and $x \in A\cap B$. In other words, if one of `EnumA` or `EnumB` eventually emits $x$ then $x \in A\cup B$, and if both `EnumA` and `EnumB` emit $x$ then $x \in A\cap B$.

# Answer
> 2 votes
Please be careful:

A language is *recursively enumerable* iff there exists an enumerator that lists its elements.

We cannot use an enumerator to handle decidable languages except if we require additional properties. A language is decidable iff either of the following

* there exists an enumerator that lists the strings in lexicographic order
* there exist enumerators \[in any order\] for both the language and its complement.

---
Tags: undecidability, closure-properties, enumeration
---


# Question
Title: Is there a formalization of the computational model for quantum computers?
There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, Hoare's communicating sequential processes, and of course the universal Turing machine, all of them formally defined.

I do understand that though there are possibly different ways of building quantum computers, the ways we build them today are Turing-complete and equivalent to the other models of computation. My question is: have anyone formalized a mathematical computation model for a quantum computer (such as the D-Wave)? (As the other models, I assume this could be used as a programming language.)

(I do understand that a possible answer would be "the quantum mechanics", but that's not exactly what I'm looking for...)

# Answer
> 8 votes
Just as Turing machines aren't widely used to model computation, so are quantum Turning machines not wildly used to model quantum computation. Instead Quantum circuits are more popular. Quantum circuits defined in the obvious way: reversible transformations on a quantum mechanical analog of an n-bit register.

# Answer
> 10 votes
Yes. The quantum Turing machine is a mathematical formalization of a computation model for a quantum computer.

See also https://en.wikipedia.org/wiki/Quantum\_computing#Developments and https://en.wikipedia.org/wiki/Quantum\_complexity\_theory and https://en.wikipedia.org/wiki/BQP.

# Answer
> 6 votes
Peter Sellinger has been working on programming languages for quantum computing for a long time now. He is not the only one working in that field, of course, but I believe his work is accessible and largely accepted enough to fit your bill.

What he essentially developed is a "typed lambda calculus for quantum computation". I believe the best place to start is in the chapter of the textbook *Semantic Techniques in Quantum Computation* (written with B. Valiron), available at http://www.mscs.dal.ca/~selinger/papers/qlambdabook.pdf. I believe the list of references in that chapter is quite authoritative, too.

If you're looking for a concrete formalization, have a look at the Quipper language, which is embedded in Haskell. The introductory paper as well as the devoted webpage are probably the best places to start.

If you're looking for a more general discussion / introduction to those topics, you can have a look at the video and the article *Programming the Quantum Future*.

---
Tags: computation-models, quantum-computing, mathematical-foundations
---


# Question
Title: How to prove that every regular language can be obtained by some FA?
I have seen this definition almost everywhere, but I don't know the underlying proof behind this definition.

# Answer
> 2 votes
These definitions are from Wikipedia

> In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using a regular expression...
>
> ...
>
> Alternatively, a regular language can be defined as a language recognized by a finite automaton.

You can define a regular language as a *set of strings accepted by some FA*. In this case **you don't have to prove anything** since a regular language **is recognized by a finite automaton by definition**.

But if you define a regular language as *a formal language that can be expressed using a regular expression* then **you can prove that it is accepted by some FA using** Thompson construction, i.e. prove the equivalence of regular expressions and finite automata.

---
Tags: complexity-theory, regular-languages, finite-automata
---


# Question
Title: Show that RE is closed against right-quotient
I have a problem that I have no idea how to approach. I've been looking at using mapping reductions, but I can't find a way to apply it.

> Assume some alphabet $\Sigma$ and two languages $A, B \subseteq \Sigma^\*$.
>
> Define the language $A / B = \\{x \in \Sigma^\* \mid xy \in A \text{ for some } y \in B \\}$.
>
> Prove that if both $A$ and $B$ are recursively enumerable then also $A / B$ is recursively enumerable.
>
> (The term recursively enumerable is also called semi-decidable and Turing recognizable).

# Answer
Recursively enumerable languages can equivalently be defined as languages of the following form:

$$ x \in L \longleftrightarrow \exists y R(x,y), $$ where $R$ is a computable relation.

Let $R\_A,R\_B$ be the relations demonstrating that $A,B$ are recursively enumerable. Then

$$ \begin{align\*} x \in A/B &\longleftrightarrow \exists y . y \in B \land xy \in A \\ &\longleftrightarrow \exists y,z,w. R\_B(y,z) \land R\_A(xy,w). \end{align\*} $$

You take it from here.
> 1 votes

# Answer
It is straight-forward to construct a semi-decider for $A / B$: given $x$, search for $y \in B$ so that $xy \in A$.

Since all three subcomputations, namely

* enumerate all $y$,
* check if $y \in B$, and
* check if $xy \in B$

are partially recursive, you'll have to *interleave* all these computations in a clever way. I'll leave you to figure out the details.

> Buzzwords to search for are *time sharing* and *dovetailing*.
> 1 votes

---
Tags: computability, closure-properties, semi-decidability
---


# Question
Title: What is more important in an algorithm, small runtime or small memory usage?
I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same type). The size on which are based the complexities is $n$.

* In the fist one, the server has to send only one object and the client has to perform $n$ operations.
* In the second one, the server has to send $\log n$ objects and the client has to perform $\log n$ operations.

What is the best algorithm ? Does it depend on the environment of execution ?

# Answer
> 3 votes
The best algorithm must certainly depend on the environment. What type of system is your client? What type of system is your server? What kind of transport system stands between them?

If, for example, your clients are Raspberry Pis then it is likely you want to reduce the amount of work you need to do on the client end - take the `log(n)` option.

If, your client is a Mars Rover you want to minimise the amount of data you need to send *and* minimise the computation required at the client. Perhaps use the `log(n)` option, perhaps not - depends on the cost of transporting the data and the computation cost at the other end.

If, however, your server is the LHC then use the `n` approach - you have probably the largest data bandwidth on the planet and the least amount of time to offload that data you've just collected.

# Answer
> 1 votes
First, let me point out that there is no obvious memory issue in your question, only bandwidth. Nowhere is it written that objects (supposed to be the same size and same transmission cost, which you should make precise) have to be stored or remembered. But they clearly have to be transmitted.

It all depends on the load and the computing/transmission power of server and clients, on whether they are homogeneous or heterogeneous, and on the size distribution of the communication.

You may well want to **mix the two protocols**, and choose which to use for each transmission task, based on size of the task, on current load, and currently available power of the server and client(s).

# Answer
> 0 votes
A direct answer is: try to find an algorithm with small runtime.

Small data storage is not so important because the physical storage equipment's got very cheap and great in amount.

Take care on accessibility of these storage devices. A lot of time gets lost for transport of data from the external storage to central main storage. All storage and load activities should work parallel.

Besides: why do you make a difference between n and log n? Mathematically they are only different numbers by value.

# Answer
> 0 votes
What you need to determine is not space and time, but cost. AND you may decide based on the cost that is relevant to you - if you pay for the server, but someone else pays for the clients, then you pick what is cheapest for the server.

---
Tags: algorithm-analysis, runtime-analysis, space-analysis
---


# Question
Title: Approximating maximal independent set with a minimal vertex cover approximation
The minimal vertex cover problem has a 2-approximation algorithm.

We can reduce the maximal independent set problem to the minimal vertex cover problem as shown here.

Does this mean that I can use the $2$-approximation for minimal vertex cover to get a $1/2$-approximation for maximal independent set?

My approach:

```
// is this a 1/2-approximation algorithm?
approxAlgForMaxIS(Graph G) {
    minVC = computeMinVC(G);
    maxIS = G.V - minVC;   // remove all vertices in the minVC from G
    return maxIS
}

```

# Answer
No, unfortunately this doesn't work. Denote by $\newcommand{\VC}{\mathrm{VC}}\VC$ the size of a minimum vertex cover and by $\newcommand{\IS}{\mathrm{IS}}\IS$ the size of a maximum independent set, so that $\VC+\IS=n$. The approximation algorithm for $\VC$ produces a vertex cover $C$ whose size satisfies $|C| \leq 2\VC$. The complement of $C$ is an independent set $I$ whose size satisfies $$ |I| = n-|C| \geq n-2\VC. $$ Unfortunately, $n-2\VC$ can be much smaller than $n-\VC$, and there's no constant lower bound on the ratio $$ \frac{n-2\VC}{n-\VC}. $$

As an example, let's see how the algorithm which picks a maximal matching fares on a graph consisting of a matching on $n$ vertices. The minimum vertex cover has size $n/2$, and so the maximum independent set has size $n/2$. The maximal matching algorithm picks all edges in the graph and then all vertices contained in them – in other words, it picks *all* vertices. It thus gives a vertex cover of size $n$, which corresponds to an independent set of size 0.

This difference between vertex cover and independent set is reflected in the fact that it is NP-hard to approximate independent set to within $n^{1-\epsilon}$, for any $\epsilon \> 0$.
> 3 votes

---
Tags: algorithms, graphs, algorithm-analysis, approximation
---


# Question
Title: Points at distance $k$ or less in 2D grid
How can we prove that the total number of mesh points k or fewer jumps away from an arbitrary point in a 2D mesh is: $2k^2 + 2k + 1$.

I tried making a $3 \times 3$ mesh.

```
     a --- b --- c
     |     |     |
     d --- e --- f
     |     |     |
     g --- h --- i

```

For point $e$, the number of points $k=1$ jump away is four: $b$, $d$, $f$, $h$. But, according to the formula, it should be $2\times1^2 + 2\times1 + 1=5$. I am stuck!

# Answer
> 2 votes
The distance between two points $(x\_1,y\_1),(x\_2,y\_2)$ on a 2D mesh is $|x\_1-x\_2|+|y\_1-y\_2|$. You can prove this as follows:

* Every horizontal edge changes the $x$ coordinate by one, hence we need at least $|x\_1-x\_2|$ horizontal edges. Similarly we need $|y\_1-y\_2|$ vertical edges. This shows that the distance is at least $|x\_1-x\_2| + |y\_1-y\_2|$.
* On the other hand, it's not hard to find a path taking exactly $|x\_1-x\_2| + |y\_1-y\_2|$ many edges (exercise).

Now say that the fixed point is $(0,0)$. You are interested in the number of points $(x,y)$ such that $$ |x| + |y| \leq k. $$ This is something you can solve on your own.

# Answer
> 3 votes
Read your question more carefully. The formula you give is for

> the total number of mesh points $k$ **or fewer** jumps away

(my emphasis). And there are indeed five points one jump or fewer away from $e$: $b$, $d$, $f$, $h$ and $e$ itself.

---
Tags: combinatorics
---


# Question
Title: Operating System: Performance of Demand Paging
I am reading Operating systems from the book "Operating System Concepts" by Peter Baer Galvin, 7th edition.

> **Performance of Demand Paging:**
>
> Let p be the probability of a page fault (0 $\leqslant$ p $\leqslant$1). We would expect p to be close to zero—that is, we would expect to have only a few page faults. The effective access time is then **effective access time = (1 - p) x ma + p x page fault time**.
>
> To compute the effective access time, we must know how much time is needed to service a page fault.
>
> **Example** If we take an average page-fault service time of 8 milliseconds and a memory-access time of 200 nanoseconds, then the effective access time in nanoseconds is
>
> effective access time = (1 - p) x (200) + p (8 milliseconds)
>
> = (1 - p) x 200 + p x 8.00(1000
>
> = 200 + 7,999,800 x p.

My doubt when there is a page table hit it we should multiply p by (ma + ma) because, we need one memory access to access page table from memory and one more memory access to access the actual page from memory. In my opinion formula should be **effective access time = (1 - p)x(ma+ma) + p x page fault time**.

Where ma is memory access time

Please let me where am I wrong?

# Answer
CPUs keep in special purpose caches recently addressed page table entries. Entries are usually named "TLB = Translation Lookaside Buffer"

We have 3 cases :

* The page is in TLBs and the access is allowed (no write in read-only areas, no user access in supervisor pages, etc...). The delay to access the TLBs is usually hidden through pipelining. The access time depends on whether data is in caches or not. Can be less than 1ns on current high performance CPUs.
* The page is not in TLBs. The CPU must find a way to update the TLBs. Some do it with simple hardware mechanisms, others use exceptions and let software do the work. In both cases, one or more memory accesses to pages tables is needed. 8ms is far too much for such operations which have a huge impact on CPU performance. This is not really "page faults"
* The page may be in the TLBs, or not, but there is a real "page fault", for example the memory accessed has been swapped to disk, or not yet initialized, or the applications has a bug... The operating system will need to do complex thing to correct that, loading memory and updating page tables, or killing the applications... 8ms seems a reasonable delay for some of these operations.
> 2 votes

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


# Question
Title: Girth of Undirected Graph with Positive Integer Weights
Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e.

$g(G) := \min\left\\{ n \in \mathbb{N} \mid \exists \text{ cycle }(e\_1, e\_2, \dots, e\_k) \text{ in $G$ satisfying } n = \sum\_{i = 1}^k w(e\_i) \right\\}$.

**GOAL.** Determine $g(G)$ algorithmically and as efficient as possible in terms of time complexity. Note that it's not necessary to find corresponding cycle, length is sufficient.

I present my thoughts on this problem as following. If the graph is unweight, i.e. $w(v) = 1$ for all $v \in V$, we may start a breadth-first search traversal keeping track of the depth of each vertex. Once we detect an edge which leads to an already visited vertex $v$, a cycle is found. The length of the cycle is the difference of the current depth and the depth of $v$. BFS from each vertex and taking minimum should do the job, time complexity is $\mathcal{O}(|V| \times (|V| + |E|))$.

How to deal with edge weights? It seems natural to modify Dijkstra, but I do not see how, because the cycle with least edges may be different from the cycle of minimum weight, the shortest cycle. Is there still a way to use Dijkstra in order to solve this problem?

Can we adapt an all-pairs shortest path algorithm? I would appreciate a solution based on Floyd-Warshall, because of it's simplicity (if there is no faster algorithm). One may assume the graph to be dense, i.e. $|E| = \mathcal{O}(|V|^2)$, so the above solution is $\mathcal{O}(|V|^3)$.

# Answer
> 2 votes
You can use both algorithms to solve this problem (Dijkstra's and Floyd-Warshall's) and you do not need to adapt them: you can simply use their output.

As suggested in D.W.'s answer, you can compute the minumum $d(v,v)$ over all $v \in V$. Each value $d(v,v)$ represents the length of the shortest way to get from a vertex $v$ back to the same vertex $v$; that is, the shortest cycle through $v$. Therefore, the minimum $d(v,v)$ over all vertices represents the shortest cycle in the entire graph $G$.

To gain more intuition, note that the shortest cycle in $G$ will go through some vertices $\\{v\_1, v\_2, ..., v\_k\\}$, and that $d(v\_1,v\_1) = d(v\_2,v\_2) = \\: ... \\: = d(v\_k,v\_k)$. You need to find the minimum $d(u, v)$ (where $u = v$) in the whole graph $G$. This information can be easily obtained by inspecting the diagonal of the output matrix of an all-pairs shortest-paths algorithm.

Observe that the above reasoning would not be valid if $G$ had negative edge weights, and you were looking for a simple cycle. This is because nothing prevents the algorithm from selecting the same edge twice.

Observe also that if the graph is a tree (i.e., it contains no cycles), then the girth can be considered to be infinity. This can be checked in a simple pre-processing step, using, for example, breadth-first search.

With respect to the running time, $|V|$ invocations to Dijkstra's algorithm will probably be faster - $O(|V|^2 \log |V|)$ - if the graph is sparse. If the graph is dense, Floyd-Warshall's algorithm is probably a better choice.

# Answer
> 3 votes
Use an all-pairs shortest-paths algorithm to find the distance from each vertex to each other vertex, call it $d(u,v)$. Now find the minimum value of $d(v,v)$ over all vertices $v$. That is the length of the shortest cycle.

Why does this work? Suppose the shortest cycle from $v$ to $v$ has length $\ell$. Obviously we will have $d(v,v) \le \ell$ (since we have a path from $v$ to $v$ of length $\ell$, the shortest such path is at most $\ell$). Conversely, we know there is a path of length $d(v,v)$ from $v$ to $v$; since it goes from $v$ to $v$, this is a cycle; so the length $\ell$ of the shortest cycle must satisfy $\ell \le d(v,v)$. We have proven both $d(v,v) \le \ell$ and $\ell \le d(v,v)$, so it follows that $\ell = d(v,v)$.

---
Tags: algorithms, graphs, graph-traversal, weighted-graphs
---


# Question
Title: STCON is NL complete - but why is the reduction in L?
I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity

I understand the reduction, but how is it logspace?

I understand each state is of $O(\log(n))$ space. What I don't understand is how I can create the graph in logspace.

I tried to do some kind of DFS, but remembering the states looks like it'd take $\log(n) * \log(n)$ because the longest path is $\log(n)$ and it costs $\log(n)$ to remember each one?

EDIT: to make sure, I do understand the why the language is in NL, but I don't understand how the reduction from lanuage L in NL to STCON is logspace.

# Answer
> 2 votes
You don't need to do DFS. Each branch on the nondeterministic TM corresponds to each possible path from $s$ to any node $v$ of length at most $n$. You also maintain the index of the vertex it is at which takes $O(\log{n})$ space. If at some step the NDTM has reached the node $t$ then you it halts with ACCEPT. If the NDTM has checked $n$ nodes and it has not reached the node $t$ then it REJECTs. So, if $t$ is reachable from $s$ then there is a path from $s$ to $t$ which would correspond to some branch on the NDTM. In this case the NDTM will halt with ACCEPT.

In simple words, each branch of computation needs to maintain a constant number of variables of size $\log n$: current node, counter for number nodes explored so far, etc. We don't care which nodes we have visited, the only thing we care about is the current node and the number of nodes we have visited in order to stop as soon as we visit $n$ nodes (all nodes).

In order to prove that STCON is NL-complete, given a string $w$ we need to convert it into STCON instance using log-space. Let $M$ be a log-space NDTM accepting $L$. We convert the configurations of computation of $M$ on $w$ into a directed graph. Each node corresponds to a single configuration and if there is a legal transition from a configuration $C\_{i}$ into a configuration $C\_j$ there is an edge between $C\_{i}$ and $C\_j$. The size of each configuration is $O(\log{|w|})$ since $M$ computes using $O(\log{|w|})$ space. Generating all possible configurations (nodes) and verifying that $C\_i$ yields $C\_j$, i.e., adding edge, take $O(\log{|w|})$ space.

Note also that we could generate all possible nodes/configurations of length $\log{|w|}$ by going through all possible strings of length $\log{|w|}$ and test if the generated string is a legal configuration. If it is legal then the TM writes it to its output tape. All this is done in $O(\log{|w|})$ space. Similarly you could generate all pairs $(C\_i, C\_j)$ and check if $C\_i$ yields $C\_j$. If $C\_i$ yields $C\_j$ then write it to the output tape as an edge of the output graph. This also takes $O(\log{|w|})$ space.

The key thing is that you don't need to worry about the time complexity whether it takes linear or exponential time. The output space isn't restricted to $O(\log{|w|})$ space either. Once you convert $w$ to an instance of STCON problem, STCON can decide if this instance belongs to $L\_{STCON}$.

---
Tags: complexity-theory, space-complexity, nondeterminism
---


title: Does DPDA accept all regular languages?

text:
# Question
Title: Does DPDA accept all regular languages?
A DPDA which accepts by empty stack cannot accept all Regular Languages? Is it true that the DPDA cannot accept all regular languages?

I am not able to understand this.As per my knowledge DPDA are more powerful than regular languages as they have finite automate and also the stack.So finite automate can handle all the regular languages.So why above statement is true?

# Answer
It is the property "accepting by empty stack" what makes the DPDA weaker. If a language $L$ is accepted by a DPDA by empty stack, then $L$ has the prefix property. The following language $L = \\{ b^n \mid n \geq 0\\}$ clearly does not have prefix property since if $b^k \in L$ then $b^m \in L$ as well for $m \< k$. So this language is not accepted by a DPDA by empty stack.

Assume that $w \in L$ and $wv \in L$ and $L$ does not have prefix property. Assume also that $L$ is accepted by some DPDA $M$ by empty stack. Since $w$ is accepted by $M$, there is a computation path from $(q\_0, w, S\_0)$ to $(q\_k, \epsilon, \epsilon)$. Since $M$ is deterministic, the only possible computation for input $wv$ is $(q\_0, w, S\_0) \Rightarrow^\* (q\_k, v, \epsilon)$. But $M$ has already had empty stack and so it cannot move further from $(q\_k, v, \epsilon)$ and hence does not accept $wv$.

---

**Definition**: A language $L$ has *prefix* *property* if $w \in L$ implies no proper prefix of $w$ is in $L$.
> 9 votes

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


# Question
Title: Subsequence of one string but not of others
Let $\Sigma$ be an alphabet, and let $x^+,x^-\_1,\dots,x^-\_n \in \Sigma^\*$ be strings over that alphabet. Call a string $s \in \Sigma^\*$ *good* if $s$ is a subsequence of $x^+$ but not a subsequence of any of $x^-\_1,\dots,x^-\_n$.

Given $x^+,x^-\_1,\dots,x^-\_n$, I am looking to find the shortest good string $s$. Is there a reasonable algorithm for this? I am interested in a practical algorithm, even if its worst-case running time is not great. In my domain, the strings $x^+,x^-\_1,\dots,x^-\_n$ might be fairly long but I expect there will exist a good string $s$ that is fairly short, in case that helps.

The case $n=1$ is handled by Shortest sub-sequence of one string, that's not a sub-sequence of another string, but I need to deal with the case $n\>1$.

# Answer
## Mistakes

First of all, in the comments I made a few mistakes: Both the original claim I made about interleaving, and the comment "correcting" it (now deleted) were wrong, and separately my claim that trying all possible interleavings must yield an optimal solution was also wrong (I give a simple counterexample below). Finally, my suggestion to set $x^+ = z\_j$ and iterate, or use beam search, is actually also not helpful: Whatever answer could be produced by doing this and applying Aryabhata's DP can never be better than using the original $x^+$, since all it does is reduce the size of the solution set from which the DP can pick. Sorry! Hopefully the improved version below contains no further problems...

I also noticed two mistakes in Aryabhata's DP as well. Fortunately they can both be easily repaired (see my comments on that post).

## A heuristic solution using random interleavings

If you don't need absolutely the shortest subsequence, you could use the fact that, if a string $s$ is a subsequence of some $x^-\_i$, then it is also a subsequence of every possible *interleaving* of all the strings $x^-\_i$. Turning this around, if $s$ is not a subsequence of some particular interleaving of all the strings $x^-\_i$, then it is not a subsequence of *any* individual $x^-\_i$.

So you could try many different ways of randomly interleaving the $n$ strings $x^−\_i$ into a single string, and for each such interleaving $y\_j$, look for the shortest subsequence $z\_j$ of $x^+$ that avoids being a subsequence of $y\_j$ using Aryabhata's nice DP algorithm for the two-string case, and pick whichever $z\_j$ is shortest over all interleavings you tried.

## Caveat: No guarantee of optimality even if we try all interleavings

Surprisingly (to me at least), even if you repeat the above procedure for all possible interleavings, you are not guaranteed to find the optimal solution: Consider the instance in which $x^+ = aaa$, $n=2$, and $x^-\_1 = x^-\_2 = a$. Then $aa$ is an optimal solution with length 2, but the shortest solution found by trying all interleavings of $x^-\_1$ and $x^-\_2$ is $aaa$, with length 3.
> 1 votes

---
Tags: algorithms, regular-languages, strings, substrings, subsequences
---


# Question
Title: Troubles understanding this Interval Scheduling question
***Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.***

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤ . . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs, the two algorithms are the same.) We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces a set of jobs whose size can be an arbitrarily small fraction of the optimal.) More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

**Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B with which j conflicts?**

# Answer
> 1 votes
You'll want to start by answering the question in the hint, and then make another argument to obtain the final result.

The hint is saying that for any job $j \in A$, there is a fixed upper bound on the number of intervals in $B$ with which $j$ overlaps. Think about what happens if $j$ intersects with three or more intervals in $B$. Would this be possible using the Shortest-Job-First algorithm?

Let the upper bound you obtain from the hint be $k$. Then, you can make the following argument (presented informally, as it is just a hint). Using our result above, we can state that in the worst case, we have each $j \in A$ overlapping with a subset of $k$ distinct jobs of $B$, where these subsets of $k$ jobs are pairwise disjoint. This gives you an upper bound on $|B|$ in terms of $|A|$.

Can you take it from here?

---
Tags: algorithms, greedy-algorithms, scheduling, process-scheduling, intervals
---


title: Big o notation help?

text:
# Question
Title: Big o notation help?
I'm learning about data structures and have been reading up on upper bounds. Most of the stuff I understand but my professor gave us a problem in class to solve on our own for fun. I'm not sure how to find the $O$ notation as a function of $N$ for this one.

```
for (i=1; i<=N; i++)
   for (j=1; j<=N; j+=i)
       x=i+j;

```

Also, does `j+=1` make things different?

# Answer
> 0 votes
You have one cycle in another cycle. In general that can be represented as

$$\sum\_{i=1}^n\Big(f(n)+\sum\_{j(i)} g(k)\Big)$$

Since former cycle contains nothing except another cycle, $f(n)\equiv0$.

So, you need to calculate $h\_i(n)\equiv\sum\_{j(i)} g(n)$ for every $i$. I have replaced $k$ with $n$ since it depends only on $n$. To do it try to understand how many iterations inner cycle will have.

If you are not successful, here is a hint:

> $h\_1(n)\equiv n,~h\_2(n)\equiv n/2,~h\_3(n)\equiv n/3...$

Once you will find an exact runtime, you want to convert it to big O. Googling that gave me an answer quick. Hope it helps.

Don't open following spoiler if you haven't understood what the function is

> Converting to big O.

---
Tags: algorithms, data-structures, asymptotics, upper-bound
---


# Question
Title: Shortest paths when edge weight depends on previous edge
I have a directed graph with non-negative weights on the edges. I can divide the nodes in two "classes", X (roughly 1700 nodes) and Y (~300). I want to collect all the shortest paths from x in X to y in Y.

The weight of the edges depend on the previous edge in the path I am currently on.

Testing the possible paths between x1 and y1, e4 has same attribute "B" as the preceding edge e3, so its weight will be reduced (I want to favour paths with same properties).

How do I actually find the shortest among the paths among x1 and y1 in this scenario?

# Answer
> 2 votes
Let your graph be $G=(V,E)$. Build a new graph $G'=(V',E')$, where each vertex in $G'$ corresponds to a pair $(u,v)$ of vertices in $G$. Add an edge $(u,v) \to (v,w)$ in $G'$ iff there is an edge $v \to w$ in $G$. The intended meaning of the vertex $(u,v)$ is that you are currently at vertex $v$ in $G$, and previously were at vertex $u$. Thus, you can now figure out what weight to put on the edge $(u,v) \to (v,w)$ -- namely, whatever weight you want to put on the edge $v \to w$ assuming you previously traversed the edge $u \to v$.

Let $X' = \\{(x,u) \in E : x \in X, u \in V\\}$ and $Y' = \\{(u,y) \in E : u \in V, y \in Y\\}$. Now, the find the shortest path in $G'$ from each vertex in $X'$ to each vertex in $Y'$, using an all-pairs shortest paths algorithm. From this you can infer the length of the shortest path in $G$ from some vertex in $X$ to some vertex in $Y$, while taking into account the fact that edges switch weights.

If you use the Floyd-Warshall algorithm, the running time will be $O(|V'|^3)$, which is at most $O(|V|^6)$. As an optimization, the vertex set $V'$ can be taken to be $V' = \\{(u,v) : u,v \in V, (u,v) \in E\\}$. Then the running time of Floyd-Warshall in $G'$ will be at most $O(|E|^3)$. Given that your original graph $G$ is fairly small, this might already be feasible without further optimizations.

If you want further optimizations, here's one more. You can add to $G'$ a special vertex $x^\*$ for each $x \in X$, with an edge $x^\* \to (x,u)$ in $G'$ for each $(x,u) \in E$ with the same weight as the edge $x \to u$ in $G$; and similarly add $y^\*$ for each $y \in Y$, with edge $(u,y) \to y^\*$ of weight 0. Now find the shortest path from each $x^\*$ to each $y^\*$. This can be done by applying Dijkstra's algorithm $|X|$ times, once for each $x \in X$, to find the distance from $x^\*$ to each other node in the graph. The total running time will be $O(|X| \cdot |E'| \log |V'|)$, which is $O(|X| \cdot |V| \cdot |E| \log |V|)$. You can also achieve running time $O(|Y| \cdot |V| \cdot |E| \log |V|)$ by searching backwards (e.g., reversing the graph). Given that you have $|Y| \approx 300$, $|V| \approx 2000$, and $|E| \le |V|^2 = 4000000$, this might complete rapidly.

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: Signed and Unsigned Loads in a 32-bit Registers
I have a question over this quote directly out of Computer Organization and Design, 5e:

> Signed versus unsigned applies to loads as well as to arithmetic. The function of a signed load is to copy the sign repeatedly to fill the rest of the register—called sign extension—but its purpose is to place a correct representation of the number within that register. Unsigned loads simply fill with 0s to the left of the data, since the number represented by the bit pattern is unsigned.
>
> **When loading a 32-bit word into a 32-bit register, the point is moot; signed and unsigned loads are identical.**

(Chapter 2.4, pg 76; Patterson and Hennessy). \[emphasis mine\]

I do not immediately grasp why signed values do not matter for a full 32-bit word in a 32-bit register. The authors do not go on to clarify exactly why this is. My best guess from the materials of the book is because registers are to be sign agnostic with regard to the data within them and how they are interpreted is up to the assembly code? This would make sense if it weren't for the lack of a signed `lw` operation for MIPS, the language chosen for the text.

Thank you for any clarification on this.

# Answer
> 2 votes
A $n$-bit bitstring can be interpreted semantically both as an unsigned integer in the range $0$ to $2^n-1$, and as a signed integer in the range $-2^{n-1}$ to $2^{n-1}-1$. There is always a way to assign an $n\_1$-bit bitstring to an $n\_2$-bit bitstring so that both have the same semantics, but the way to do that depends on whether the semantics is unsigned or signed. In the unsigned case, we use *zero extension*: we affix $n\_2-n\_1$ zeroes on the left. In the signed case, we use *zero extension*: we affix $n\_2-n\_1$ copies of the sign bit on the left.

As an example, consider $x=1111$, and suppose that we wish to assign it into an 8-bit bitstring. In the unsigned case, the value of $x$ is $15$, and the extension is $00001111$. In the signed case, the value of $x$ is $-1$, and the extension is $11111111$.

When $n\_2 = n\_1$, there is nothing to extend, so the signed and unsigned cases are the same. That's why the point is moot in such cases.

---
Tags: computer-architecture, operating-systems, arithmetic, memory-hardware
---


# Question
Title: Algorithm to estimate the probability that a "0 and 1 matrix" fills up following the bootstrap percolation rules
**Presentation of the model:** we consider the regular lattice created from $\mathbb{Z}^2$ (It's no more, no less a square lattice).

* At $t=0$, each site is said "active" independently with a probability $p$, "inactive" otherwise.
* At $t$, if a site is inactive, it becomes active if at least $2$ of its neighbours are active.

We call neighbour of $x$ each element of $V(x)=\\{y\in\mathbb{Z}^2, ||x-y||=1\\}$ (or, if I have a matrix M in python, a neighbour of $M\[i\]\[j\]$ is $M\[i\pm1\]\[j\]$ or $M\[i\]\[j\pm 1\]$).

---

**My problem:** I consider a $n\times n$ matrix filled with 0s and 1s, (0 = inactive ; 1 = active), and I want to estimate the probability $p\_c$ that a matrix, following the rules above, fills up (at $t\rightarrow \infty$, but this happen really fast in reality). The probability $p\_c$ depend on $n$. I want to test it for $n=2$ to $n=100$ at least.

**What I already have:** I have a program, `matrix_creation(n,p)` that creates a $n\times n$ matrix with the probability $p$ for each coefficient to be 1, and another, `test(M)`, to test if "M" fills up.

# Answer
> 1 votes
Here is a reasonably fast approach to estimate $p\_c$. We will perform $N$ different trials, count the number of successes $M$, and estimate the result as $M/N \pm 1/\sqrt{N}$ (better estimates are possible if $p\_c$ is close to 0 or to 1).

For each trial, you initialize an $N \times N$ matrix with the initial filling. You then go over the array, calculating the number of active neighbors of each non-filled point in the matrix, and whenever that number reaches 2, you put it in a stack. You then repeatedly pop elements from the stack, updating the matrix of active neighbors, and whenever that number reaches 2 for some non-filled point, you add it to the stack. When the stack is empty, the process is complete, and you can check whether all points have been activated.

There are many optimizations possible: for example, you can use an $(N+2)\times(N+2)$ matrix to help deal with border cases, you can keep track of the number of active points, and so on.

Using this naive approach, I managed to perform $10^6$ trials for $n = 100$, $p = 0.0535$ in about two minutes on my PC. The answer was $M/N \approx 0.5008$, so the critical probability is pretty close to $0.0535$.

---
Tags: algorithms, graphs, randomized-algorithms, cellular-automata
---


# Question
Title: What does $k$ mean in regular expressions?
From what I have learned in *Introduction to Automata Theory, Languages, and Computation*, regular expressions can be represented with $R^{(k)}\_{ij}$.

I understand that $i$ and $j$ represent the starting state and the closing state respectively. However, I am still trying to understand the purpose of $k$.

To put it simply, what does $k$ stand for in $R^{(k)}\_{ij}$?

Side note: Link to the book is here.

# Answer
$k$ means that if $w \in R^{k}\_{ij}$ then on reading $w$, FA starting from the state $i$ enters the state $j$ and never enters a state $t$ where $t \> k$ while reading input $w$. In the book, you learn from, $R^{k}\_{ij}$ is defined as the *set of all strings that transition the automaton $M$ from $q\_i$ to $q\_j$ without passing through any state higher than $q\_k$*.
> 4 votes

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


# Question
Title: Largest possible cost of a shortest path in which every edge's length is either -1, 0, or 1
I'm doing an online course in which I'm struggling with the following (multiple-choice) question:

> Suppose we run the FLoyd-Warshall algorithm on a directed graph $G =(V,E)$ in which every edge's length is either $-1,0,$ or $1$. Suppose further that $G$ is strongly connected, with at least one $u$-$v$ path for every pair $u,v$ of vertices. The graph $G$ may or may not have a negative-cost cycle. How large can the final entries $A\[i,j,n\]$ be, in absolute value? Choose the smallest number that is guaranteed to be a valid upper bound. (As usual, $n$ denotes $|V|$.) \[WARNING: for this question, make sure you refer to the implementation of the Floyd-Warshall algorithm given in lecture, rather than to some alternative source.\]
>
> 1. $+\infty$
> 2. $n^2$
> 3. $2^n$
> 4. $n-1$

I'm furthermore told that $n-1$ shouldn't be selected, with the hint "Experiment with graphs that have negative-cost cycles".

Here is the Floyd-Warshall algorithm as described in the lectures:

> Let $A$ be a 3-D array, indexed by $i,j,k$. Define the base cases: $$ A\[i,j,0\] = \begin{cases}0 & i = j \\ c\_{i,j} & (i,j)\in E \\ +\infty & \text{else}\end{cases}$$
>
> ```
> For k = 1 to n
>     For i = 1 to n
>         For j = 1 to n
>             A[i,j,k] = min(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1])
>
> ```
>
> **Correctness**: From optimal substructure and induction, as usual.
>
> **Running time**: $O(1)$ per sub-problem, $O(n^3)$ total.

In the course's nomenclature, $n$ denotes the total number of vertices in the graph, so $A(i, j, n)$ is the shortest path from node $i$ to $j$ which may use all $n$ nodes.

As I understand it, a shortest path between any two nodes has at most $n - 1$ edges, so if the maximum cost of an edge is 1, I would expect the maximum cost of a shortest path to be $n - 1$. I don't see how the presence of negative-cost cycles could change this?

# Answer
> 2 votes
> a shortest path between any two nodes has at most n - 1 edges

This is only true for simple paths *(paths with no repeat nodes)*. If there is a negative-cost cycle, you can take the cycle multiple times to get a shorter path.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Why $\operatorname{gap-A}[1.5a, 1.5b + 1/4]$ has an efficient solution?
> Let $0\<a \< b\<1/2$. Suppose that there's an efficient $a/b$-approximation for $A$, where $A$ is a maximization problem. Why does $\operatorname{gap-A}\[1.5a, 1.5b +1/4\]$ also has a polynomial solution?

We've learned in class that if $gap-A\[a,b\]$ has a polynomial solution then there's a $\frac{a}{b}$ approximation. That is,

$$\frac{a}{b} opt(x) \le val(y\_x) \le opt(x)$$

So let's assume by contradiction that $\operatorname{gap-A}\[1.5a, 1.5b +1/4\]$ is hard.
Then, there's no polynomial time $\frac{1.5a}{1.5b + 1/4} $-approximation algorithm.

$$\frac{1.5a}{1.5b + 1/4} = \frac{a}{b+1/6}$$

Then, $gap-A\[a,b+1/6\]$ is hard to decide, but that doesn't help with reaching a contradiction.

**EDIT:**
We define for a maximization problem $A$ the decision problem $\operatorname{gap-A}\[a,b\]$ as:

Let $Y$ to be the set of solutions for $x$.

for a given $x$, the algorithm needs to decide:

1. there's a $y\_x\in Y$ such that $y\_x \> b$.
2. for every $y\_x\in Y$: $y\_x \< a$

If $x$ is not in one of the above the result could be arbitrary.

# Answer
> 2 votes
Given an instance $x$ of $\mathsf{gap\text{-}A}(1.5a,1.5b+1/4)$, calculate $y\_x$ using the $a/b$ approximation algorithm, so that $$ \frac{a}{b} opt(x) \leq val(y\_x) \leq opt(x). $$ If $opt(x) \geq 1.5b+1/4$ then $$ val(y\_x) \geq \frac{a}{b} (1.5b+1/4) \> 1.5a. $$ Conversely, if $opt(x) \leq 1.5a$ then $$ val(y\_x) \leq 1.5a. $$ You take it from here.

---
Tags: complexity-theory, approximation
---


# Question
Title: $C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?
> $C\_1 \subseteq C\_2$ implies $C\_1^A\subseteq C\_2^A$?

I've given a caveat that one shouldn't make this implication blindly and it shall be justified.

I can think of examples such that $C\_1^A \subsetneq C\_2^A$ and examples such that $C\_1^A = C\_2^A$.

but could it be that $C\_2^A \subset C\_1^A$? I can't see how.

So what's the point of this caveat?

# Answer
A proof technique is (informally) *relativizing* if the results it generates also hold relative to an oracle. Not all proof techniques are relativizing. Perhaps the best known example is $\mathsf{IP}=\mathsf{PSPACE}$, which uses the technique of algebraization. Although $\mathsf{PSPACE} \subseteq \mathsf{IP}$, there is an oracle $O$ such that $\mathsf{PSPACE}^O \not\subseteq \mathsf{IP}^O$ (see this question on cstheory).
> 3 votes

---
Tags: complexity-theory
---


title: Tree with branching factor 1

text:
# Question
Title: Tree with branching factor 1
Something that has been bothering me for a while is the formula for the maximum amount of nodes of a tree with height d and branching factor of b.

$$(b^{d+1}-1)/(b-1)$$

This holds true for all positive integer values of b, including 0, with the exception of b=1.

If b = 1, we would be dividing by 0. Which, well, we all know is not a "legal mathematical move". However, if b = 1, the number of nodes would be equal to the height of the tree + 1.

I'm not sure exactly what my question is. I just feel like it's weird that a tree with branching factor 0 would have 0 nodes, a tree with branching factor 2 would have $$(b^{d+1}-1)/(b-1)$$ nodes , but calculating the number of nodes of a tree with branching factor 1 would be impossible using the same formula.

I don't know what I'm missing. Why isn't there a formula that calculates all nodes in a tree that includes branching factor 1 (or rather, why doesn't this formula include b = 1?)? Or does a tree need a branching factor that is anything else than 1 (but larger than -1?) to qualify as a tree? I'm a bit confused. Help is greatly appreciated.

(Not sure if I got all the facts right here. Please forgive me if I didn't)

# Answer
> 3 votes
The formula you state follows from summing a geometric series: $$ 1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}. $$ When $b=1$, the series sums to $d+1$, which is also the limit of the expression above as $b\to1$.

As you mention, the formula is only meaningful when $b \neq 1$, though the correct value can still be recovered by taking a limit. This is perhaps the simplest example of a curious phenomenon in combinatorics, that of the "field with one element". Consider the following two quantities:

1. The number of subsets of size $k$ of a set of size $n$. These are counted by binomial coefficients $\binom{n}{k}$.
2. The number of $k$-dimensional subspaces of an $n$-dimensional vector space over the finite field with $q$ elements. These are counted by Gaussian binomial coefficients $\binom{n}{k}\_q$, which are rational functions (ratios of two polynomials) in $q$.

The curious thing is that if we substitute $q=1$ in the expression for $\binom{n}{k}\_q$, we get back $\binom{n}{k}$ *in the limit*. (Just as in your case, when $q=1$ the denominator vanishes.) So a set is similar to a vector space over "the field with one element".

More generally, there are other formulas involving "$q$-analogs" (sets replaced with vector spaces over the field with $q$ elements) which degenerate to the correct values when taking the limit $q\to1$. There are some explanations for this phenomenon but it is still somewhat mysterious.

---
Tags: graphs, trees
---


# Question
Title: prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?
I tried doing this, but kept failing to prove. I know how to prove that the language is nonregular when n0(w) = n1(w). The following is the proof for n0(w) = n1(w) using pumping lemma:

```
Assume L is regular. Then, by the Pumping Lemma, there is a natural number m such
that any w ∈ L with |w| ≥ m can be factored as w = xyz with |xy| ≤ m and |y| > 0,
and xyi
z ∈ L, for i = 0, 1...
Pick w = 0^m 1^m.
Then, 0^m 1^m = xyz, where y = 0k, for k > 0.
By the Pumping Lemma, xz ∈ L.
But, n0(xz) does not equal n1(xz).
The assumption that L is regular thus is false.
Hence Proved

```

However, I don't know how to prove it for when number of 0 is not equal to number of 1.

# Answer
There are two easy proofs that I will let you work out on your own. The first uses the fact that regular languages are closed under complement, the other uses the Myhill–Nerode criterion.

You can also prove that this language is not regular using the pumping lemma, but the proof is a bit tricky. Let $p$ be the pumping length, and consider the word $w = 0^p1^{p!+p} \in L$. The pumping lemma gives us some decomposition $w = xyz$ with $y = 0^i$ for $1 \leq i \leq p$. Then $xy^{1+p!/i}z = 0^{p!+p} 1^{p!+p} \notin L$.
> 1 votes

---
Tags: formal-languages, regular-languages, context-free, pumping-lemma
---


# Question
Title: Regular Expression for {W | W contains an even number of As and an odd number of Bs, but doesn't contains AB}
While studying Automata at my University, I faced the following problem from SIPSER, M textbook:

> Consider D = { w | w contains an even number of as and an odd number of bs and doesn't contains the chain ab}. Draw an DFA with 5 states that recognizes D and a Regular Expression that generated D.

I tried doing the following DFA:

With the Regular Expression `b(bb)*(aa)*`

And that seemed quite right for me, but for chains that goes like `baab` it should be refused, but it isn't.

I couldn't find a way to fix it without adding another state to the DFA.

How can it be done?

# Answer
> 1 votes
Here's one possible solution:

(In fact, the words $b,bb,ba,baa,bab$ show that at least five states are needed, so this is the *unique* minimal DFA.)

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


# Question
Title: When LRU is NOT the optimal replacement policy
I've been googling this topic but still couldnt get a legit answer. So can someone explain with some examples that if we were to use cache memory instead of LRU we would have lower miss rate (better peformance). Or simply when LRU is not an optimal choise.

# Answer
Consider a program that plays a video in an endless loop (e.g. an electronic advertising billboard), assuming the RAM is constrained enough that the whole video can't fit at once.

The most recently used page of memory will contain the most recent section of the video, that *just* played. LRU would be the worst choice, because you're holding onto the parts that have already played, which are the parts that won't be needed for the longest time. They won't be needed again until all other pages are played first, and the video repeats. By definition, such a use case is hitting the *least* recently used pages, over and over.

The optimal page replacement policy in such a situation is one that either preempts the future pages (which is possible in this case because of the periodicity and simplicity of this usage profile) or one which permanently holds onto some parts of the video (doesn't matter which parts, as they're all played equally) and uses the rest of the space to cycle through the rest of the pages.
> 1 votes

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


# Question
Title: Why k- Vertex Cover is not in PTIME when it can be expressed in FO-logic
We can express property that graph has vertex cover of size at most k with first order formula:

$$\exists x\_1 \exists x\_2...\exists x\_k (\forall y \forall z (E(z,y) \ \rightarrow \ \bigvee\_{1 \leq i \leq k} y=x\_i \ \vee \ \bigvee\_{1 \leq i \leq k} z=x\_i))$$

But, there is also theorem (proven for example in Libkin's book Finite model theory) that for every given FO sentence and finite model A one can decide does:

$$A \models \varphi$$

in PTIME.

Why can't we use this for sentence expressing k-VC property, written above, and decide does any given graph has this property?

# Answer
Your argument shows that for each *fixed* $k$, the problem $k$-VC can be solved in polynomial time (indeed, the algorithm enumerates all sets of size $k$ and checks whether they are vertex covers, all of which can be accomplished in $O(n^{k+1})$ or so). However, the vertex cover problem is different – it accepts $k$ as an *input*. This version of the vertex cover problem cannot be expressed in first-order logic.
> 7 votes

---
Tags: complexity-theory, graphs, time-complexity, first-order-logic
---


# Question
Title: Construct this two-taped Turing Machine {(u#,v#):u,v E {a,b}* , |u| = 2|v|}
I am having troubles trying to create this two-taped Turing Machine, I understand how I would get it to accept 2 strings of equal length. But to move forwards, I dont know how I would check to see if |u| = 2|v|

# Answer
> 1 votes
One possible solution running in linear time:

1) Move head of the first tape to the right until you reach end of $u$ while copying each symbol of $u$ to the second tape. But first write a blank symbol on the second tape as the first symbol.

2) Read $v$ by two symbols and for each pair of symbol of $v$ erase one symbol of $u$ on the second tape (starting from the last symbol and moving backward).

3.1) If all symbols (of $u$) on the second tape has been erased then check if the first head has reached end of the string (of $v$). If "no" then REJECT else ACCEPT.

3.2) If the TM has reached end of the string of $v$ (on the first tape) then check if the second tape is empty. If "yes" then ACCEPT else REJECT.

---
Tags: turing-machines, finite-automata
---


# Question
Title: General approach to randomized algorithm for equality problem
Using randomized approach we can guarantee that the equality problem has O(1) complexity (in communication). With other definitions of of equality (not strictly equal), is there a general approach to design a randomized algorithm with bounded error? Or how to determine if there is no way such an algorithm can be designed?

# Answer
> 2 votes
Suppose that the inputs are $x,y \in \\{0,1\\}^n$.

Consider the following protocol:

* The parties decide on a random string $z \in \\{1,2\\}^n$.
* Alice sends Bob $\alpha = \sum\_{i=1}^n x\_i z\_i \pmod{3}$, and Bob sends Alice $\beta = \sum\_{i=1}^n y\_i z\_i \pmod{3}$.
* The parties compute $\gamma = \alpha - \beta \pmod{3}$.

Suppose that the Hamming distance between $x$ and $y$ is $d$. Then $\gamma$ is the sum of $d$ random values in $\\{1,2\\}$. Using linear algebra, we can calculate $$ \Pr\[\gamma = 0\] = \frac{1}{3} + \frac{2}{3} \left(-\frac{1}{2}\right)^d.$$ (You can also prove this formula by induction.)

In particular, when $d=0$ the probability is $1$, when $d=1$ the probability is $0$, and otherwise the probability is in the range $\[1/4,1/2\]$ (corresponding to $n=3$ and $n=2$, respectively).

The suggests a protocol of the following form:

1. The parties decide on $N$ random strings $z\_1,\ldots,z\_N \in \\{1,2\\}^n$.
2. Alice sends Bob $\alpha\_j = \sum\_{i=1}^n x\_i z\_{j,i} \pmod{3}$ and Bob sends Alice $\beta\_j = \sum\_{i=1}^n y\_i z\_{j,i} \pmod{3}$, for $1 \leq j \leq N$.
3. The parties compute $\gamma\_j = \alpha\_j - \beta\_j \pmod{3}$ for $1 \leq j \leq N$.
4. If all $\gamma\_j$ are zero or all are non-zero, output "Hamming distance is probably at most 1", otherwise output "Hamming distance is definitely more than 1".

As in the case of equality, this protocol has only one-sided error: whenever the algorithm outputs "Hamming distance is more than 1", it is always correct. It remains to determine the connection between $N$ and the error probability $\epsilon$. Let $p = \Pr\[\gamma = 0\]$. If $p \neq 0,1$, the probability that the algorithm outputs the incorrect answer is $$ p^N + (1-p)^N \leq (1/2)^N + (3/4)^N. $$ This shows that $\epsilon$ is exponentially small in $N$, and so in order to guarantee an error probability of $\epsilon \> 0$, it suffices to take $N = O(\log(1/\epsilon))$.

---
Tags: randomized-algorithms
---


# Question
Title: how to find upper bound and lower bound of quadratic equation
I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields same results. Anyhow now I am writing the upper and lower bound for that, the equation which I get is

$$20n^2+11n+1$$ I need to find the

$$c\_1n^2 \leq 20n^2+11n+1 \leq c\_2n^2$$

Here I am stuck and needs some assistance, I have gone through a lot of examples, books, and youtube videos, but no one has any method to solve it instead of assumption and different ways. Any help is much appreciated.

EDIT Graph for the equation

# Answer
> 1 votes
Since $n \geq 1$ (since $n$ is the input length), we have $$ 20n^2 \leq 20n^2 + 11n + 1 \leq (20+11+1)n^2 = 32n^2. $$ Put differently, for all $n \geq 1$, the function $f(n) = 20n^2 + 11n + 1$ is bounded from below by $20n^2$ and from above by $32n^2$. This shows that $f(n) = \Theta(n^2)$.

Note also that when $n$ is large, $f(n)$ gets very close to $20n^2$. Indeed, $$ 1 \leq \frac{f(n)}{20n^2} \leq 1 + O\left(\frac{1}{n}\right). $$

---
Tags: algorithm-analysis, asymptotics, lower-bounds, upper-bound
---


title: LTL to GBA versus LTL to BA

text:
# Question
Title: LTL to GBA versus LTL to BA
Let's assume that I have an LTL formula and I want to convert it to a Buchi automaton. For which fragment of LTL, GBA is more succinct and for which fragment BA has the same size as GBA.

# Answer
> 2 votes
There is no precise answer to this.

1. The smallest GBA for a given language is never larger than the smallest BA for a given language, simply by the fact that BAs are a special case of GBAs.
2. It is easy to construct a language for which smaller GBA exist. Example would be (in LTL) $\mathsf{GF}(a \wedge b) \wedge \mathsf{GF}(a \wedge \neg b) \wedge \mathsf{GF}(\neg a \wedge b) \wedge \mathsf{GF}(\neg a \wedge \neg b)$ - a four-state GBA does the trick, but the BA needs more states to encode waiting for the next event (out of $a \wedge b$, $\ldots$, $\neg a \wedge \neg b$) to happen. So whatever fragment of LTL you build, this formula will not be contained therein. But if you now take a disjunction of this property with $\mathsf{GF}(a)$ and then with $\mathsf{GF}(\neg a)$, then the smallest BA and GBA have the same size (one state). So you cannot give a precise syntactic representation of such a fragment (without making a containment check at least PSPACE-hard).
3. You can, of course, build an LTL fragment for which containment of the property in the fragment guarantees that the smallest GBA will not be larger than the smallest BA. You would get such a fragment, for example, by including the next-time operator as the only temporal operator in the fragment.
4. In practice, it doesn't matter anyway. Due to the many different optimizations in LTL-to-BA and LTL-to-GBA tools, you cannot predict very well whether they will compute BAs that are just as small as GBAs.

---
Tags: automata, model-checking, software-verification, linear-temporal-logic, buchi-automata
---


# Question
Title: TRNG by hamming distance of processor tics
I hardly remember on a lecture, where it was told, that the distance of the practical actual running-speed of a processor to the previous tic is used, to generated a true random entropy for seeding. But I cannot find any source for proving this memory right.

So my question arises: Is this a way to generate a true random seed and spawn so a trng?

# Answer
> 1 votes
You are talking about using the relative jitter of 2 timers to source entropy.

That is indeed an option for entropy generation.

However in terms of cryptographically secure RNGs (the reason you would go to such length to create randomness) this jitter can be influenced by the load on the processor and electrical noise. This provides a side channel to try and influence or predict the entropy used for the generator.

---
Tags: computer-architecture, randomness, random-number-generator
---


# Question
Title: What is correct time complexity of the substring generation algo
The naive algorithm for generating all unique substrings involves traversing all the string from `1..n`, thus takes $\mathcal{O}(n^2)$, but it also involves maintaining a list for all generated substring to check everytime for repetitions.

So the total time can't be $\mathcal{O}(n^2)$, since there is an added checking of uniqueness, which means that I have to maintain a list of all previous generated substrings.

So how is it correct that when it is said that the algorithm takes only $\mathcal{O}(n^2)$ time.

There is obviously an added cost at each substring generation.

The actual time complexity should be as pointed out by Raphael should be something like the following -:

$\mathcal{O}(n^2) + (\mathcal{O}(m^2) * \mathcal{O}(n)))$

where $m$ is the total number of substrings generated $n(n+1)/2$, and the time to compare 2 different strings is the smaller length between two strings, assuming the strings are being compared character by character.

Now if the above is correct then what I am confused about is should it be plus or a multiply with the comparision cost.

# Answer
> 3 votes
To be blunt, the Stack Overflow question and its answers illustrate why you want to ask about such things here.

1. The propsed algorithm clearly does not run in quadratic time.
2. Since the length $n$ of the original string is our input size, and the length of the longest possible result string, we can not assume that string comparisons run in constant time.
3. The bound you give is therefore also wrong, since you can not check in constant time if any string is in a list of size $L$.

Instead, the running time of the algorithm is more complicated and depends on several factors (new variable names).

* The length $N$ of the input string.
* The number $m$ of output strings. $m \in \Omega(n) \cap O(n^2)$.
* The total length $M$ of all output strings. $M \in \Omega(n^2) \cap O(n^3)$.

You should be able to derive rough bounds using standard approaches. Keep in mind to fix the dictionary implementation you use for the "list"! Using, say, tries you get lookup (and insertion) costs bounded by the length of the string at hand.

---
Tags: algorithm-analysis, runtime-analysis, strings, substrings
---


# Question
Title: Some questions on kernels and Reinforcement Learning
I've a test in a few days and I've a few issues with some of the subjects.

Let's start with kernels, basically I understood that a kernel needs to be positive semi-definite and symmetric in order to be valid. Is that enough? For example the following kernel, $\mathrm{kernel}(x,y) = 2 k(x,y)$ for some $k$ which is a valid kernel. Is that valid? My question is how can I distinguish between a valid kernel and an invalid kernel if I'm given a kernel in the test?

Reinforcement learning - Value iteration, upper bound confidence and Q-learning. I'm trying to figure out the major differences between them, Value Iteration is when we are familiar with the world, with the probabilities and such. And Q-learning is basically learning the world first. Where does upper bound confidence enter?

Thanks.

# Answer
> 3 votes
> Is that valid? My question is how can I distinguish between a valid kernel and a nonvalid kernel if I'm given a kernel in the test?

Yes, it will be a valid kernel for all practical purposes, because kernel functions measure the similarity of some points relative to other ones (that's why they are also called similarity functions). Making your kernel function twice as big doesn't change that.

The next quote is from Wikipedia:

*Although no single definition of a similarity measure exists, usually such measures are in some sense the inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. E.g., in the context of cluster analysis, Frey and Dueck suggest defining a similarity measure $s(x,y)=-\\|x-y\\|\_{2}^{2}$ where $\\|x-y\\|\_{2}^{2}$ is the squared Euclidean distance.*

As you can see, a kernel function *can be negative*, if that's convenient in a particular problem. I don't know any example of an asymmetric kernel function. See this question for more examples.

The answer to your question boils down to this: can you apply a particular kernel function to a particular method? So it depends on a problem to large extent.

> Where does upper bound confidence enter?

In general, Upper Confidence Bound (UCB) is a Bayesian Optimization method, that aims to deal with exploration-exploitation trade off in the multi-armed bandit problem. In this problem, there is an *unknown* function, which we can evaluate in any point, but each evaluation costs (direct penalty or opportunity cost), and the goal is to find its maximum using as few trials as possible. Basically, the trade off is this: you know the function in a finite set of points (of which some are good and some are bad), so you can try area around the current local maximum, hoping to improve it (*exploitation*), or you can try a completely new area of space, that can potentially be much better or much worse (*exploration*), or somewhere in between.

Just as a side note, Bayesian Optimization methods, UCB in particular, build a model of the target function using a Gaussian Process (GP) and at each step choose the most "promising" point based on their GP model.

In Reinforcement Learning, the same exploration-exploitation dilemma arises as well. When an agent chooses an action to make, it has a choice between low uncertainty actions with a known value (*exploitation*) and high uncertainty actions (*exploration*). Without proper exploration, an agent would always do the same actions and never actually learn.

In this setting, UCB is counting how many times each action $a$ has been selected, $N\_t(a)$, and maximizes the following expression:

$a\_t = \underset{a∈A}{\operatorname{argmax}} Q(a) + \sqrt \frac{2 log t}{N\_t(a)}$

where $Q(a)$ is an action-value function. If you compare this formula to the one used in Bayesian Optimization, you'll notice it's actually the same idea.

---
Tags: machine-learning, reinforcement-learning, kernel-functions
---


# Question
Title: Is linked list a preferable underlying basic DS for a collection mutable through an iterator
I need to implement a collection DS that exposes an iterator which can be used to iterate an underlying collection and possibly remove the current item. I can use either a vector (dynamic array) or a linked list as an underlying DS. I'm inclined toward toward linked list because of the easiness of operations. Is it a good decision? What other things I need to consider?

Thanks

# Answer
> 1 votes
Well, if you're looking for easiness of operations, I would recommend a vector. Vectors support a wide array of operations, providing a large number of top-level methods, and iterators namely std::iterator, reverse iterator, and a lot more. With these top-level functions and iterators however, comes the caveat of not being able to modify these to suit your needs. Consider all of this when making the choice.

# Answer
> 1 votes
Since deleting or inserting in the middle of a vector is a linear time operation, a linked list is the better choice. This assumes of course that you have reasonably large lists (i.e. they don't fit in cache) and that you frequently insert or delete items in the middle, compared to just iterating or changing the end of the list. If you have small lists or change them only infrequently, the smaller constants in the asymptotic runtime for operations on a vector could beat asymptotic improvements.

---
Tags: data-structures, arrays, linked-lists, iteration
---


title: Is n!=O(2^(n lg n))?

text:
# Question
Title: Is n!=O(2^(n lg n))?
By Stirling's Approximation $n! = \sqrt{2\*\pi\*n} * \[n/e\]^n * e^\alpha$

Therefore $T(n!) = O(n^n)$

$O(n^n) \neq O(2^{n \lg n})$

Is this correct? Is there another way to get this result if it is correct? Thanks.

# Answer
> 1 votes
Remember, big-O is essentially an *upper* bound so we do have $$ n! = O(n^n) $$ in the sense that there is a constant $c$ for which $n!\le c\\;n^n$ eventually. \[Note, by the way, that there's no function $T(\cdot)$ involved here.\]

Now let's see if $n!=O(2^{n\log n})$. We can argue this way (assuming the log is base-2): $$ 2^{n\log n} = 2^{(\log n) n} = \left(2^{\log n}\right)^n = n^n $$ so we can conclude that the two sets $O(n^n)$ and $O(2^{n\log n})$ are in fact equal.

---
Tags: asymptotics
---


# Question
Title: What determines the number of inputs and outputs when initialising weights in a convolutional neural network?
Following Deep MNIST for Experts tutorial on Tensorflow, I realize I don't understand where the choice of numbers comes from when initializing weights.

In the tutorial, they first show the below function for creating random weights.

```
def weight_variable(shape):
  initial = tf.truncated_normal(shape, stddev=0.1)
  return tf.Variable(initial)

```

However, the `shape` parameter has me confused when the tutorial shows the next line of code:

```
W_conv1 = weight_variable([5, 5, 1, 32])

```

The tutorial says the following:

> The first two dimensions are the patch size, the next is the number of input channels, and the last is the number of output channels.

I don't understand the significance of the last two values, `1` and `32`.

What decides what values you input there? And what do they affect?

When I'm designing my own neural network, could I put any value I like for the last two, or if I were to change them in a neural network would it 'break' the entire network?

# Answer
> 1 votes
The question is about basic principles of Convolutional Neural Networks, specifically how the layers are organized (it's best explained here, in fact I highly recommend to complete the whole CS231n course, it's amazing!).

> What decides what values you input there? and what do they affect?

```
W_conv1 = weight_variable([5, 5, 1, 32])

```

The input channel of the first convolutional layer is the depth of MNIST images. Since they are grayscale, there's only one channel. If you had colorful CIFAR-10 images, you'd use 3 channels (R, G, B).

The 5x5 filters in this layer (`32`) would be the the output of this layer and input to the next layer. Indeed, as you can see the next layer defines

```
W_conv2 = weight_variable([5, 5, 32, 64])

```

> When I'm designing my own neural network, could I put any value I like for the last two, or if I were to change them in a neural network would it 'break' the entire network?

Yes, you have freedom here, you only need to make input-output channels consistent. If you decide to use `48` filters instead `32`, you would write:

```
W_conv1 = weight_variable([5, 5, 1, 48])
b_conv1 = bias_variable([48])
...
W_conv2 = weight_variable([5, 5, 48, 64])
b_conv2 = bias_variable([64])

```

Like I said before, the first `1` is determined by your data. But you can change the filter size as well, from 5x5 to 3x3.

Note that if the number of channels doesn't match, the graph won't simply compile. You'll see an error even before the training starts, so don't be afraid to experiment.

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?
Let $\mathrm{LOG}\_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$.

Obviously, this class is a proper subset of the class of context-free languages. Which languages are in this class, and what (closure) properties does it have?

I have found this class in Harrison's Book:

>

I have searched a lot about iterated counter languages but I can't understand them well. I also I don't know whether this problem is what I am looking for or not.

I think if we have L1 and L2 in this class so we can have their union in this class by adding two lambda- transition.

And if we have a Pda A with logarithmic stack height , if we can construct an equivalent Pda B with the extra property that always clear all its stack symbols except the bottom-of-stack symble after every acceptance so we this class will be closed under Kleene- star

I will be grateful if anyone can explain me whether this class is closed under intersection and complement or not

I am still looking for just one non-regular-language that is in this class!!!

# Answer
> 4 votes
The class $LOG\_{CF}$ is in fact the class of regular languages $R$ (and thus have all of the regular languages closure properties).

$R\subseteq LOG\_{CF}$ is trivial, so we'll concern ourselves only with the the other direction.

Let $A$ be some PDA, and let $s(n)$ be the maximal stack size of $A$'s run on a length-$n$ word. First notice that if $s(n)=O(1)$, then $L(A)$ is regular (you can always encode a finite set of stack configurations into a NFA).

We will claim that if $s(n)=\omega(1)$, then $s(n)=\Theta(n)$, thus there can't be any PDA which is guaranteed to use non-constant sub-linear space.

We define *Automaton-Sub-Configuration* to be a tuple $(q,x)\in Q\times \Gamma^\*$ such that currently the automaton is in state $q$, and the top of his stack (the suffix of the stack word), is a word $x\in\Gamma^\*$.

Now if $s(n)=\omega(1)$, there has to be some automaton sub-configuration, $(q',x')$, for the such that:

$(q',x')$ can be reached unbounded number of times, and on every time it is reached, the stack size grows by at least one symbol.

Let $w\_0\in \Sigma^\*$ be a word such that the automaton would reach $(q',x')$, and let $w\_1$ be a word such that when reading $w\_1$ out of $(q',x')$, the automaton ends at $(q',x')$ with at least one additional symbol in the stack.

Finally, consider the word $w=w\_0\cdot w\_1^k$. Notice that the automaton stack size after reading $w$ is (at least) $k$, while $|w|=|w\_0|+k|w\_1|$, hence the stack size could be linear in the length of the word.

---

The conclusion is that for any PDA $A$, $s(n)=O(1)$ or $s(n)=\Theta(n)$.

# Answer
> 2 votes
) !

My answer result exactly is the same as above but I hope this answer be useful for the others and if there is something wrong with it, I understand it and correct it and learn it .

It wasn’t obvious for me that this class is equal to context free so after proving some of its properties I tried to find a language in this class then I realized that I can't find any non-regular language and this led me to following:

$LOG\_{CF}= R$ , which $R$ means class of regular languages.

Suppose that $\Sigma = \\{0,1\\}$

We claim that $LOG\_{CF}= R$. it follows $LOG\_{CF} - R= \emptyset$. Proof by contradiction: let $L\in LOG\_{CF}$. So there is a PDA like P that $L(P)=L$ and for all $w \in L $ P uses its stack's cells at most $log|w|.$ We know that every context free languages that its words contains only one alphabet are regular, so $\forall w \in L$ , $w$ would be an string including 0 and 1. Let $n\_0(w)$ and $n\_1(w)$ be respectively number of 0s and 1s. Since P at most uses $log|w|$ cells of its stack, $n\_0(w)$ and $n\_1(w)$ don’t have linear relationship. We can conclude using Parikh theorem that $L$ is not context free! If $L$ is not context free then there is no PDA like P. it means $L \notin LOG\_{CF}$ and that is the contradiction.

# Answer
> 2 votes
I'm afraid the accepted answer which claims that $LOG\_{CF}=REG$ is not correct.

In section 6 of this reference, Klaus Reinhardt gives a simple example of non-regular language that can be accepted by pushdown automata using $\sqrt{n}$ stack space.

This language is defined as the set of finite non-prefixes of the following infinite word:

$baba^2ba^3ba^4ba^5b...$

Additionally, in the same paper it is shown that for each function f(n) between $\log n$ and $n$, there is a context free language that can be accepted in pushdown space $f(n)$, but not in pushdown space $o(f(n))$.

Note that the paper is written in terms of height of parse-trees for context free grammars. But height $f(n)$ is equivalent to pushdown space $f(n)$.

---
Tags: complexity-theory, automata, pushdown-automata, space-complexity
---


# Question
Title: A slightly different version of the halting problem
I got stuck with a question and would like to have a little guidance for the solution.

I need to prove that the next problem is undecidable:

* Input - A program
* Problem - Does the number of possible inputs for which the program halts is larger than those for which the program won't halt?

I tried to build a reduction that (in case the input is even) halts for every even number, goes to an infinite loop for every odd and runs the program with the input. Or in case the input is odd does the opposite - but it only works if I am able to prove that the number of real odd numbers is equal to the real even numbers.

# Answer
I won't give you the solution - I think you're on the right track. However I will give a possible way of making this question precise:

Prove that this problem is undecidable:

* Input: A (code for a) Turing Machine $M$
* Output: $\texttt{Accept}$ if the number of inputs for which $M$ halts is a finite number $\leq n$
* $\texttt{Reject}$ otherwise.

Since there are an infinite number of inputs, if $M$ halts for a finite number of them, then it doesn't halt for an infinite number of them.

Of course, it's possible for a machine to halt on an infinite number of inputs, and not halt on an infinite number of inputs (say, halt on even numbers and not on odd numbers). In this case, a hypothetical machine for this problem would $\mathtt{Reject}$.

You might notice some similarity to the halting problem at this point.
> 2 votes

---
Tags: algorithms, complexity-theory, reductions, halting-problem
---