# Question
Title: Lower bound of degree of polynomial approximating parity
Let $\text{MOD}\_2 : \\{0,1\\}^n \rightarrow \\{0,1\\}$ be a parity function where $$\text{MOD}\_2(x\_1,\dots,x\_n) = \sum\_i x\_i \bmod 2$$

It is known \[See e.g. Lemma 5 of this lecture note\] that any polynomial $f(x\_1,\dots,x\_n) \in \mathbb{R}\[x\_1,\dots,x\_n\]$ of degree at most $\sqrt{n}$ must disagree with $\text{MOD}\_2$ on at least a constant fraction of inputs.

> Is this true for a polynomial with degree $n^{0.5+\epsilon}$ for some small constant $\epsilon\>0$ ? How about a polynomial with degree $o(n)$?

# Answer
You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$).

Let $S = x\_1 + x\_2 + \dots + x\_n$. Note that $\text{MOD}\_2(x\_1, x\_2, \dots, x\_n)$ can be written as a single-variable function of $S$. By Lagrange interpolation, there exists a univariate polynomial of degree $O(\sqrt{n\log n})$ in $S$ (and hence in the $x\_i$s) that agrees with $\text{MOD}\_2$ on the interval $S \in \[(n-\sqrt{n\log n})/2, (n+\sqrt{n\log n})/2\]$. By the central limit theorem, this range of $S$ accounts for all but $o(1)$ of the $2^n$ inputs $(x\_1, x\_2, \dots, x\_n)$.
> 5 votes

---
Tags: complexity-theory, circuits, lower-bounds, polynomials
---


# Question
Title: why the big-oh of a linear function is n^2?
I know the ***definitions and differences*** of *big-theta, big-oh, and big-omega* in finding time complexity of algorithms. what I can't understand is that why the big-oh of a linear function cannot be O(n).

$0 \le an + b \le cn \Rightarrow c = a + \frac b {n\_0}$

so we could find a value for constant $c$. as a result, the big-oh of a linear function can also be $n$. am I right??

**Note:** I have read all the previous answers and questions in this commission and others. but I didn't understand. that's why asked a new question

# Answer
> 5 votes
A function does not have a *unique* big-oh. $O(f(n))$ denotes a *class* of functions that are big-oh of $f(n)$. Big-oh is used to give upper bounds.

For example, $f(n)=3n+5$ *is* $O(n)$, but it is *also* $O(n^2)$ *and also* $O(n^3)$ *and also* $O(2^{2^{2^n}})$. However, $f(n)$ is (in this example) *not* $O(\log n)$.

In set theory notation, we have $O(n)\subset O(n^2)$, i.e. any function that is $O(n)$ is also $O(n^2)$. However, if we had a function that is $O(n)$ and you gave $O(n^2)$ as an upper bound, that would not be incorrect, but it would be a *weaker* result than saying it is $O(n)$.

$\Omega$ works the other way around (i.e., it is used for lower bounds). A function that is $\Omega(n^2)$ is also $\Omega(n)$. $\Theta$ is used to give "tight" bounds: a function that is $\Theta(n^2)$ is neither $\Theta(n)$ nor $\Theta(n^3)$.

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Alternative definitions of ZPP and probabilistic Turing Machines
There are two ways to define a probabilistic Turing Machine:

1. A Turing Machine that can toss coins during its computation.
2. A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is the original input and $r$ is taken from a distribution of coin tosses.

For example, Arora and Barak give an "alternative definition" for $\mathrm{BPP}$:

> **Definition 7.4 (BPP, alternative definition)**
> $\mathrm{BPP}$ contains a language $L$ if there exists a polynomial-time TM $M$ and a polynomial $p\colon \mathbb{N}\to \mathbb{N}$ such that for every $x \in \\{ 0, 1 \\}^{∗}$, $\Pr\_{r \in \\{ 0,1 \\}^{p(|x|)}} \[M (x, r) = L(x)\]\geq 2 / 3 $.

My problem is formulating a similar alternative definition for $\mathrm{ZPP}$.

$\mathrm{ZPP}$ can be defined as the class of languages with a randomized algorithm that always outputs the correct answer, and for every input the expected running time of the algorithm is polynomial.

If we want a similar alternative definition for $\mathrm{ZPP}$, then $r$ should be an infinite stream because the algorithm may need to use any number of coin tosses before it finishes (with small probability).

Is there any problem with a Turing Machine that takes as a second input an infinite long stream?

# Answer
The definition works fine if you allow $r$ to be infinite, and require that $M(x,r)$ agrees with $L$ with probability $1$ when $r$ is distributed according to the coin toss measure on $\\{0,1\\}^{\mathbb{N}}$ (toss a fair coin an infinite number of times). In this setting, in order to get $\mathsf{ZPP}$, you need to require that the expected running time will be polynomial in $|x|$.

However, you don't really need an infinite number of coins to get $\mathsf{ZPP}$, and could do with an exponential amount of coins. Suppose $L\in\mathsf{ZPP}$, hence there exists a probabilistic Turing machine $M(x)$, such that for all $x\in\Sigma^\*$ it holds that $M(x)=L(x)$ and $\mathbb{E}\[T\_x\]\le |x|^c$, where $T\_x$ is the running time of $M$ on input $x$. You can now define an equivalent Turing machine $M'$ which is exponential in the worst case (rather than unbounded), and still satisfies the above conditions. Given input $x$, $M'$ simulates $M$ for $2^{|x|^c}$ steps, and if $M$ did not halt in this time, check "manually" if $x\in L$. This can be done by running a PSPACE machine for $L$ (which exists since $\mathsf{ZPP\subseteq PSPACE})$. You can now show that $M'$ is also polynomial in expectation (think about the appropriate choice of $c$ for this to work).
> 2 votes

---
Tags: complexity-theory, turing-machines, computation-models, randomized-algorithms
---


# Question
Title: What is the relation between word size and size of internal register of a processor?
Is there any difference between word size and size of internal register of CPU ,since "Word size" refers to the number of bits processed by a computer's CPU in one go ,so does this imply that word size is architecture dependent and ALU register's size is same as word size ?

# Answer
The term "word size" is defined in different ways by different sources, but almost everybody agrees that it is architecture dependent.

In the definition you quote: "number of bits processed by a computer's CPU in one go" it is not clear what "processed" refers to.

(Sorry about using ancient example, but I have not really looked at hardware specs for ages)

For example: The 486DX processor can add 32 bit integers for a 32-bit result (plus carry). It can multiply 32 bit integers for a 64-bit result. It can add or multiply 80-bit floating-point numbers for 80-bit results.

It has 32-bit integer registers and 80-bit floating-point registers. The 64-bit int multiplication stores in result in two registers.

I won't even start on the various physical and virtual memory address sizes.

The integer multiply instruction 32x32 -\> 64 is an oddity, most integer instructions can only process 32 bits.

Now, what is the word size?

It all depends on your definition.
> 2 votes

# Answer
One. Yes the size of one word is the size of a single register present in a register file.

Your memory storage may store the data in 4,8,16,32,64 bits of data, but they ultimately have to be loaded into a register before the CPU can use it for performing operations. Here MIPS reads the data from the memory in sets of the size which can be accomodated in a single register file.

e.g: If your register has 32 bits capacity and your memory stores the data in 8bit values, then MIPS will read 4 memory locations and fit it into a single register and this set is called as a "word" or "data word".

In short, one word is the data which can be fit into a single register in the register file of your computer.

Hope this helps!!
> 2 votes

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


# Question
Title: Why do derivation tree not make sense for context-sensitive grammars?
I don't understand the line in the paper "Mappings and Grammars on Trees" by William C. Rounds, the passage:

> Transformational theory, as developed by Chomsky \[7\] and many others, deals with the notion of phrase-structure grammar, and with certain mappings defined on derivation trees associated with the grammar. **Derivation trees do not make much sense for context-sensitive grammars, because they depend on the order of carrying out a derivation**. We will therefore assume that mappings are to be defined on context-free derivation trees.

Thank you.

# Answer
For context-free grammars, the order in which you execute rules does not matter. Formally, let

$\qquad \gamma = w\_1 A\_1 w\_2 \dots w\_{n-1} A\_{n-1} w\_n$

with $A\_i \in N$ and $w\_i \in T^\*$ for all $i$. Then, any order of applying rules $A\_i \to \alpha\_i$ yields the same sentential form. Thus, it makes sense to identify $\gamma$ with a level in a syntax tree -- the children of all the nodes (if any) are independent of each other.

For context-sensitive grammars, this is not true. Consider this grammar¹:

$\qquad\begin{align\*} S\ \ &\to AS \mid A \\ AS &\to a \\ SA &\to b \\ A\ \ \ &\to c \end{align\*}$

Observe how the set of applicable rules changes as soon as you start applying them! Therefore, while you can still imagine a tree structure here, the children are no longer independent.

Also, you'd have to connect *two* nodes from higher levels each node -- and arbitrarily many for general CSGs. Since any symbol may influence the picking of many rules, this will give you a DAG, but no tree.

---

1. As has been aptly noted by commentes chi and fade2black, this grammar is not context-sensitive in the strict sense of the definition. I find it clearer to illustrate the issue; but still, this is a clearly context-sensitive variant:

$\qquad\begin{align\*} S\ \ &\to AS \mid AB \\ AS &\to CC \\ SA &\to DD \\ A\ \ \ &\to c \\ B \ \ \ &\to d \\ C \ \ \ &\to a \\ D \ \ \ &\to b \end{align\*}$
> 3 votes

# Answer
Consider the CFG $$ S\to AB \qquad A \to a \qquad B \to b $$ Here, it does not matter if we consider the derivation $$ S \to AB \to aB \to ab $$ or $$ S \to AB \to Ab \to ab $$ The order of the expansion of the non terminals $A$ and $B$ is irrelevant. Because of that, we can represent this derivation as a tree, as if the non terminals $A,B$ were replaced in parallel.

This is not always the case for context sensitive grammars. $$ S \to AB \qquad AB \to aB \qquad aB \to ab $$ clearly admits only one derivation $S \to^\* ab$, and there we can not replace $B$ before $A$, since we can't rewrite the string in parallel ignoring the context of each non terminal, as we could for CFGs.
> 3 votes

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


# Question
Title: What does $\sigma(t_0, \ldots, t_{n-1}) \in \mathcal{T}_{\Sigma}^{0}$ in this paper mean?
The paper is "Mappings and Grammars on Trees" by William C. Rounds. There was a definition of ranked alphabet in page 3 and I can't understand the second part of the definition.

> Definition. A ranked alphabet is a pair $(\Sigma, r)$ where $\Sigma$ is finite, and $r: \Sigma \rightarrow \mathbb{N}$.
>
> We set $\Sigma\_n = r^{-1}\\{n\\}$
>
> Let $(\Sigma, r)$ be a ranked alphabet. The set $\mathcal{T}\_{\Sigma}^{0}$ (the constant $\Sigma$-terms) is the smallest set of strings such that:
>
> $\ldots$
>
> (b) if $t\_0, \ldots, t\_{n-1} \in T\_{\Sigma}^{0}$, and $\sigma \in \Sigma\_{n}$, then $\sigma(t\_0, \ldots, t\_{n-1}) \in \mathcal{T}\_{\Sigma}^{0}$

The $\sigma$ should be set of the alphabet which is ranked $n$, how can a set of alphabet become a function?

Thank you.

# Answer
You're over-thinking it. It just says that, if $t\_0$, ..., $t\_{n-1}$ are in $T^0\_\Sigma$ and $\sigma$ is a symbol in the alphabet $\Sigma\_n$, then the string consisting of $\sigma$, followed by $($, followed by... is in $T^0\_\Sigma$
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Is $O(n^{1/2})$ exponential? Is $O(n)$ better than $O(n^{1/2})$?
I was just going through some of the primality test algorithms. It seems that the regular one – loop up to square root of $n$ – has running time $O(n^{1/2})$.

Is $O(n^{1/2})$ exponential? And is exponential time better than polynomial always?

# Answer
A function that is $O(n^{1/2}) = O(\sqrt{n})$ is a polynomial, not an exponential, function of $n$. However, when analyzing the run-time of algorithms, we need to be clear about what $n$ actually is.

Here, $n$ is the (value of the) number whose primality is being tested. However, we measure the run-time of the algorithm in terms of the length of its input in bits. The number $n$ can be represented in $\log n$ bits, which means that the running time of $O(n^{1/2})$ is actually exponential in the length of the input.
> 6 votes

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


title: Why is CVAL a P-Complete problem?

text:
# Question
Title: Why is CVAL a P-Complete problem?
We've learned in class that CVAL is P-complete. CVAL is the language of all $\langle C,x\rangle$ where $C$ is a formula (a circuit which outputs $0$ or $1$) and $x$ is some input for $C$ such that $C(x) = 1$.

We've done this in the same fashion Michael Sipser does in this paper (accessed Jul 11, 2017).

The reduction itself is pretty much clear. What isn't clear to me is why we can make this reduction in $\mathcal O (\log n)$ space?

It's clear that every cell is dependent on some *constant* number of cells of the above row (= previous configuration). Yet, one would end up calculating recursively more and more cells, until reaching the very first configuration.

We did learn in class how to evaluate $f\_2 (f\_1(x))$ effectively, with $\log n$ space - You start with computing $f\_2$, and when in need, you "ask" $f\_1$ for some symbol. I don't see how to apply it in our case.

I'd be glad for clarificatoins

# Answer
> 4 votes
The reduction doesn't calculate the values of all cells. Rather, it outputs a circuit which calculates (recursively) the values of all cells. You can output the circuit using only logarithmic space, while evaluating it probably requires more space (unless L=P) since CVAL is P-complete.

---
Tags: complexity-theory, reductions, space-complexity
---


# Question
Title: Closure of regular languages under non-contiguous subsequence
Suppose there is a language $L$ on alphabet $Σ$. Now consider the language

$$ S(L) = \\{x : wxy ∈ L, w, y ∈ Σ^\*\\} ∪ \\{x : w ∈ L,\text{ and $x$ is a subsequence of $w$}\\}. $$

How to prove that if $L$ is regular then $S(L)$ is also regular?

For first part I think if there is a DFA that accepts $wxy$ then there is a DFA that accepts $x$. For second part I have no clue. Can anyone shed some light on this or can provide a formal proof for this?

# Answer
> 3 votes
Here are several ways of showing this:

1. Starting with a DFA/NFA for $L$, add $\epsilon$ transitions parallel to all other transitions.
2. Apply the regular substitution that maps $\sigma \in \Sigma$ to $\\{\sigma,\epsilon\\}$.
3. Starting with a regular expression for $L$, replace all copies of each $\sigma \in \Sigma^\*$ by $\epsilon + \sigma$.

# Answer
> 3 votes
Given a DFA $M$ for $L$ create a new NFA with $\epsilon$-moves $M'$ by adding a new transition $\delta(q\_i, \epsilon) = q\_j$ for each existing transition $\delta(q\_i,a) = q\_j$ for some symbol $a \in \Sigma$.

Now for example if $w = abaabab$ is accepted by $M$ and $u = aab$ is a subsequence of $w$, then $u$ can be written as $a \epsilon \epsilon ab \epsilon \epsilon$ which is accepted by $M'$ according to the new NFA rules.

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Variant of bipartite matching, with real capacities from source and to sink, all others unlimited
I've got a variant of bipartite graph matching and I can't find any literature about it.

We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real capacity edges from right vertices to sink (also summing to 1), and unlimited capacity edges between left and right. What is the fastest algorithm for max flow here?

To phrase it more colorfully, you have N types of dog food, totaling 1 kilogram; and N dogs, with each dog being able to eat a maximum quantity of food, but in total they can eat 1 kilogram. Not all dogs will eat all types of dog food, but they will eat up to their "capacity" of any combination of the types that they do like. How do you get the largest quantity of dog food fed to your dogs?

So far it looks like Edmonds-Karp is actually faster than push-relabel. I've been using the networkx python package implementation of both of these algorithms, but now I need to optimize for speed. I will be implementing a solution in C or Cython, but I'm concerned about the algorithm itself. It feels like there should be a specialized solution for this that works faster. Does anyone have any ideas?

# Answer
Looks like the answer I was looking for was something like Dinitz's algorithm with dynamic trees. There are some implementation optimizations that can be added since we know it's a bipartite graph.
> 0 votes

---
Tags: algorithms, graphs, network-flow, bipartite-matching
---


# Question
Title: General Number Field Sieve Big O Clarification
This paper states that the general number field sieve is of order:

$$L\approx\exp\left((64/9)^{1/3}\\,n^{1/3}\\,(\ln(n))^{2/3}\right)$$

However several sources (e.g. Wolfram) give it as:

$$O\left( \exp\left((64/9)^{1/3}\\,(\log n)^{1/3}\\,(\log\log n)^{2/3}\right) \right)$$

To my knowledge L-notation and big O notation are exactly the same, so is this paper incorrect, or am I missing something?

It also gives the binary length of the number being factored, $n$, as being converted from its decimal length via:

$$n=k\\,\ln(10)$$

I'm aware that if you can multiply by a constant factor then how the complexity is expressed doesn't matter (e.g. you can pick any log base so long as you're consistent), but since the correct way of doing this would be:

$$n = \lfloor k\\, \log\_2(10)\rfloor + 1$$

Is their stated conversion to $n$ acceptable?

# Answer
> 3 votes
There is a small difference between these two:

1. $L\approx\exp\left((64/9)^{1/3}\\,n^{1/3}\\,(\ln(n))^{2/3}\right)$. Here $n$ is a number of bits needed to represent given number $N$.
2. $O\left( \exp\left((64/9)^{1/3}\\,(\log N)^{1/3}\\,(\log\log N)^{2/3}\right) \right)$. Here the number $N$ itself is used in notation.

This is true since length of number grows logarithmically of the number itself. Just put $n$ instead of $\log N$ or vice versa and you see that they are equal.

In terms of big O notation constants are uninteresing, so, base of logarithm also is uninteresting. That's why it doesn't make sense whether you interpret number in decimal or binary or any other (except unary) system.

$n=k\\,\ln(10)$: here $\ln(10)$ is constant and we can get rid of it. Also, $k$ depends linearly on $n$, so $k = O(n)$.

$n = \lfloor k\\, \log\_2(10)\rfloor + 1$: and here both $\log\_2(10)$ and $+1$ are removed when written as big O: it still equals $O(n)$.

---
Tags: complexity-theory, asymptotics
---


title: Asserting Run Time From Big O Function

text:
# Question
Title: Asserting Run Time From Big O Function
Related to this, but I felt it was more appropriate to ask as a separate question:

The complexity of Shor's algorithm is of order

$$O\left(n^2\\,\log(n)\\,\log(\log(n))\right)$$

with $n$ the bit length of the number to be factored. This paper asserts that on a terahertz range quantum computer (i.e. $10^6$ instructions per second) a thousand digit decimal number will take 84 seconds to factorize. It makes this assertion based on taking $\log$ to be $\ln$. By changing the $\log$ base it's obviously possible to get quite different answers e.g. $\log\_2$ gives a result of 460 seconds.

My question is, is it at all meaningful/correct make such precise assertions as to run time based on this information?

# Answer
The base of logarithms is irrelevant in big-O notation, since $$\log\_b x = \frac{\log\_a x}{\log\_a b} = O(\log\_a x)\\,,$$ so $O(\log\_a x)$ and $O(\log\_b x)$ denote exactly the same class of functions.

The assertions made by the paper about how long a certain computer would take to solve some problem don't appear to be well founded. As a minor issue, doesn't "terahertz range computer" mean $10^{12}$ operations per second, not one million per second? But the major point is that $O(n^2\log n\log\log n)$ is not the same thing as $n^2\log n\log\log n$: it's merely a statement that, there's some constant $c$ such that, for large enough $n$, the number of computation steps is at most $cn^2\log n\log\log n$. In particular, it doesn't tell us what the value of $c$ is: it could be $10^{-100}$ or $10^{100}$ or anything else. Further, the analysis is never sufficiently precise to equate some number of "computation steps" with an actual number of machine instructions.

You simply cannot turn an asymptotic expression such as this into a running time in seconds without more information. One possible way to obtain the value of $c$ would be to time the actual execution of the program, but this isn't possible as we don't have any quantum computers that can run Shor's algorithm on $1000$-digit numbers. I don't see anything that would enable the authors of the paper to give precise wall-clock running times for a program on a computer that doesn't exist.

It appears that the authors are using $\ln$ to denote base-$2$ logarithms, since they say that a $k$-digit number equates to $k\ln10$ bits. A 1000-digit number is about 3300 bits and $$3300^2\log\_2 3300\log\_2\log\_2 3300\approx 451\times 10^6\\,,$$ so that's certainly not where the $84$-second claim comes from.

It seems, in fact, to come from interpreting $\ln$ as meaning the natural logarithm. Based on the incorrect claim that a $1000$-digit number has $1000\log\_e 10\approx 2300$ bits, we get $$2300^2\log\_e 2300\log\_e\log\_e2300\approx 84\times 10^6\\,.$$ This calculation is not meaningful in any way.
> 1 votes

# Answer
No. You can't predict the concrete running time based on an asymptotic expression for the running time, as asymptotic analysis ignores constant factors. You don't know whether the big-O notation hides a factor of 3 or 3 million.
> 1 votes

---
Tags: asymptotics, complexity-classes, quantum-computing
---


# Question
Title: Devising algorithm for an A.I. to solve the Wumpus game
## Background

I am currently coding an AI in C++ to solve a game called Hunt the Wumpus. You can try the game out here. My implementation of the game is based on a Graph template which I use to model the caves and the AI's "memory".

## Rules

* The start position for the player, the Wumpus and the hazards (pits or bats) is randomized, one of the 20 caves.
* You can move from cave to cave freely and each cave will warn you if it has dangerous neighbors.
* You can shoot one of your 5 arrows to a cave adjacent to yours. The arrow will fly randomly for up to three caves. If it comes in contact with you or the Wumpus, the arrow will kill it.
* When shoting an arrow, if it's a misfire, then the Wumpus wakes up and each turn it will move randomly.
* You die either when one of the following happens:
    + Falling into a pit
    + Walking into the Wumpus' cave (it devours you)
    + Losing all of your arrows
    + An arrow which you shot randomly flies back into your cave and kills you.

## AI Rules

* The AI marks each cave it visits as safe. If it enters a cave which has a threatful neighbor, it makrs the cave with TN (Threat Neighbor) and it marks each neighbor as a possible threat (PT).
* The AI has a "memory" which is a copy of the graph, but it is incomplete. The AI fills it as it travels through the graph.
* Based on the information stored in said memory, the AI decides to move or shoot.

## Problem

I'm having trouble with the algorithm that I'm trying to implement "to hunt the Wumpus". My algorithm searches for the non-dangerous caves, each turn analysing the current memory and deducing which caves are optimal to move.

I think my algorithm cannot solve this problem, since it might get stuck. This is because I instructed to back off when there is a TN flag and the algorithm will not be able to deduce if there are safe caves remaining within reach.

I read up this paper \[1\] which explains an approach to solving the problem but does not describe the algorithm in detail. The section I'm trying to base my algotrithm off is section 4.2 and following of \[1\].

## The algorithm

Suppose $G=(\lbrace v\_0,...,v\_{19}\rbrace, E)$ is the graph we are working on and let $N\_i = \lbrace u\in G: \lbrace u,v\_i\rbrace\in E\rbrace$ represent the neighborhood of vertex $v\_i$. Suppose $M$ is the graph which represents the A.I.'s memory. $M$ is constructed step by step, for each turn that passes, each vertex $m\_i\in M$ stores the following data: vertex number in $G$, indications (room is safe/dangerous, neighborhood has pit/bat/wumpus), and times A.I. has been here.

* For the first cave $v\_i$, $m\_0$ stores the information for this cave. Even if it is dangerous we have to move to a random neighbor in $N\_i$. We store the room number, the indications it gives in memory for future reference and mark this room as safe.
* When we enter the next room $v\_j$, if we didn't die we mark it as safe. We recieve the indications from the neighbors, store them in $m\_1$ and we decide what to do next.
    + If there were no threats coming from the neighbors, we move once again to a random neighbor in $N\_j$ except the previous one.
    + If there was a threat flag, then we only store the information of the room and backtrack to the last threatless room we were in.
* If we find the Wumpus-Is-Neighbor (W) flag in vertex $v\_k$ then we mark the neighbors $N\_k$ as possible hosts for the wumpus. Because there are no 4-cycles in the graph, once we hit with the W flag again in, say vertex $v\_l$, we will know certainly that the Wumpus is in $N\_l$.
* When we find the W flag again we will search inside $N\_k\cap N\_l$ for the only vertex inside
* Each turn when we move or shoot, the A.I. reads all of $M$ and adds flags, then we deduce information.
* Once the A.I. evaluates this, the A.I. decides to move or shoot. It will only shoot once we have found two instances of the W flag in two non-adjacent rooms.

As an example: Suppose that the A.I. walks into $v\_i$, $m\_i$ corresponding to $v\_i$ has a TN flag, and $v\_j\in N\_i$. Then $m\_j$ corresponding to $v\_j$ will have a PT flag.
Now suppose the A.I. arrives at $v\_k$, there is no TN flag in $m\_k$, and $v\_j\in N\_k$. This means that the PT flag in $m\_j$ is not true, and therefore $v\_j$ is a safe room.

## A more detailed example

* Step 1: The A.I. starts the game at $v\_i$. It stores information in $m\_0$, the $i$ index of $v\_i$, the flags from this room (either safe or non safe). Then it moves randomly as it cannot backtrack.
* Step 2: The A.I. walks into $u\in N\_i$, once again storing the information in $m\_1$. Suppose $u$ has a TN flag, then all of $v\in N(u)$ has a PT flag except for $v\_i$. The A.I. decides to backtrack to the previous cave (if it wasn't dangerous). Else, the A.I. has to choose to move randomly between $N(u)$.

For the following steps the A.I. covers all of the area it can reach and it deduces that there are safe rooms which it hasn't gone to.

Here I face one of the problems: I feel the A.I. isn't taking enough risks and therefore it might reach a stalemate where there are no more safe rooms to explore and it won't be able to deduce that there exist more of such rooms.

* Step $i$: Essentially the A.I. arrives at this room, records the information in a new vertex in $M$ and decides whether to explore this room's neighborhood or backtrack.

Another problem I have is that I am not sure whether the A.I. will reach the Wumpus' room.

Also when the A.I. at a room with bats, I'm not sure how to handle the $M$ graph, since what I'm doing is adding a $m\_i$ vertex one by one. I think that it shouldn't generate a problem, but I'm not sure.

---

1. Hunt the Wumpus: an Empirical Approach by Graeme Cole (2005)

# Answer
> 0 votes
If you have explored all edges out of all safe rooms, and you don't have enough information to identify the location of the Wumpus, then you can pick an unsafe room randomly and randomly explore an edge out of it. That prevents you from getting stuck if you've explored all safe rooms. (There are other possible strategies, but this is a simple one that's probably reasonable and easy to program.)

Rather than backtracking, I would suggest the following strategy: if the current room $r$ is not safe, pick a random safe room $r'$ that has an unexplored edge out of it, move from $r$ to $r'$, and then explore the unexplored edge out of $r'$. Since you've built up the graph in memory, you can easily find a path from $r$ to $r'$ (e.g., via BFS). In this way, you're not restricted to rooms $r'$ and paths that take the form of "backtracking", but you can go to anywhere known and reachable. In this way, if there is any safe place you can explore, the algorithm will explore that before trying anything unsafe.

In this way, you won't get stuck.

Bats should be straightforward to handle. Suppose the bat takes you to a room $r$ that you haven't previously been in. Then you add a new vertex for $r$ to the graph, that's disconnected from all other vertices.

Those simple tweaks should take care of all of the problems/concerns you listed in the question.

# Answer
> 1 votes
This game is mentioned in Peter Norvig's lovely textbook "Artificial Intelligence: A Modern Approach". A pdf can be found online quite easily.

Are you familiar with how to model this problem as a search problem?

The issue with the algorithm getting 'stuck' is a basic feature in search algorithms like depth first search and breadth first search, in that once the algorithm can not make any more legal moves it should return to an un-explored branch of the search space and explore that until it reaches a goal state.

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Convolutional Neural Network with constant kernels
I'm starting to learn about CNNs, and I have this question that I haven't been able to answer. Sorry if it is too basic.

I know that in a CNN, the network learns to extract relevant features of images in order to classify them. My question is: **if I just update the weights of the fully-connected layer and leave the kernels constant, will the network learn how to classify as well?**

(The kernels might be a Gaussian blur or a sharpenning, or whatever comes to mind).

# Answer
No, probably not -- unless you happen to get lucky and the kernel weights you started with just happen to be good ones. But if you choose the kernel weights randomly, your procedure will probably work very poorly.

You can always try it out yourself and see what happens.

That said, you might be thinking of "fine-tuning". In fine-tuning, we first train a model for some image recognition task, on some training set. This stage involves learning both the kernel weighted and fully-connected layer weights. Now, suppose we have a new task (hopefully similar to the original task, but a bit different) and a new training set. Then you can take the prior model, hold the kernel weights fixed, and try doing the learning procedure (backpropagation etc.) on the new training set, adjusting only the last few fully-connected layers. Sometimes this is highly effective: the kernels in the first few layers that are useful for one image classification task are often still useful for other image classification tasks. For instance, people sometimes take a good model trained on ImageNet for general objection recognition and then use it with fine-tuning to do some other similar but not identical image classification task. This potentially saves training time and requires less training data, and can sometimes work well.
> 2 votes

# Answer
A fully connected layer is able to classify images better than random. If you make the kernels constant and there is still information in the result, the network is essentially only a FCN operating on a preprocessed image. Of course it will learn how to classify the image. But it will certainly be worse than a similar network where the convolutional weights are learned.
> 3 votes

---
Tags: machine-learning, neural-networks, image-processing, clustering
---


# Question
Title: Can I use breadth-first search for topological sorting?
Can I use breadth-first search for topologicallly sort vertices and finding strongly connected components in a graph?

If yes, how can I do that? If not, why?

I tried with a simple acyclic graph of 3 vertices, gave the start and finish time as we do in DFS and then sorted them in non-increasing order. There was a conflict. The result was topologically sorted.

I find in all books that we use depth first search here. Is there any way that I can modify BFS so that I can topologically sort vertices?

# Answer
> 1 votes
BFS for topological sort seems possible to me.

All we need to add to the baseline BFS is a stack. The idea is that in BFS, nodes are traversed by levels relative to the starting node. When we get to the level where none of the nodes have un-visited children, we know that these nodes will be the first to put in topological ordering. Then we look at their immediate predecessors, and we know that they will be second to put in topological ordering. And we look at a level above, and so on.

Here is a pseudo-code snippet that does this on a subgraph reachable from the `start_node` (it'd be straightforward to extend it to the entire graph):

```
# Returns a list of nodes in topological-ordering.
def top_bfs(start_node):
    queue = [start_node]
    stack = []
    while not queue.empty():
        node = queue.dequeue()
        if not node.visited:
            node.visited = True
            stack.push(node)
            for c in node.children:
                queue.enqueue(c)
        else:
            # node's ordering should be lowered because previously visited.
            adjustedNode = stack.remove(node)
            stack.push(adjustedNode)

    stack.reverse()
    return stack

```

# Answer
> 0 votes
Yes, you can do **topological sorting** using **BFS**. Actually I remembered once my teacher told me that if the problem can be solved by **BFS**, never choose to solve it by **DFS**. Because the logic for **BFS** is simpler than **DFS**, most of the time you will always want a straightforward solution to a problem.

You need to start with nodes of which the **indegree is 0**, meaning no other nodes direct to them. Be sure to add these nodes to your result first.You can use a HashMap to map every node with its indegree, and a queue which is very commonly seen in BFS to assist your traversal. When you poll a node from the queue, the indegree of its neighbors need to be decreased by 1, this is like delete the node from the graph and delete the edge between the node and its neighbors. Every time you come across nodes with 0 indegree, offer them to the queue for checking their neighbors later and add them to the result.

```
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
  ArrayList<DirectedGraphNode> result = new ArrayList<>();
      if (graph == null || graph.size() == 0) {
        return result;
      }

  Map<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>();
  Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();

  //mapping node to its indegree to the HashMap, however these nodes
  //have to be directed to by one other node, nodes whose indegree == 0
  //would not be mapped.
  for (DirectedGraphNode DAGNode : graph){
      for (DirectedGraphNode nei : DAGNode.neighbors){
          if(indegree.containsKey(nei)){
              indegree.put(nei, indegree.get(nei) + 1);
          } else {
              indegree.put(nei, 1);
          }
      }
  }

//find all nodes with indegree == 0. They should be at starting positon in the result
  for (DirectedGraphNode GraphNode : graph) {
      if (!indegree.containsKey(GraphNode)){
          queue.offer(GraphNode);
          result.add(GraphNode);
      }
  }

//everytime we poll out a node from the queue, it means we delete it from the
//graph, we will minus its neighbors indegree by one, this is the same meaning
//as we delete the edge from the node to its neighbors.
  while (!queue.isEmpty()) {
      DirectedGraphNode temp = queue.poll();
      for (DirectedGraphNode neighbor : temp.neighbors){
          indegree.put(neighbor, indegree.get(neighbor) - 1);
          if (indegree.get(neighbor) == 0){
              result.add(neighbor);
              queue.offer(neighbor);
          }
      }
  }
  return result;
}

```

---
Tags: algorithms, graphs, sorting
---


# Question
Title: Estimating run time in the absence of knowledge
I’ve always wondered how to make a best guess in the absence of any knowledge.

Let’s say you have a computation running, and you don’t know when it will complete (just that it will). Can you make any estimate when it will be finished just based on the elapsed time without any further knowledge? For example after 10 minutes I cannot tell how much longer it will take, it might take 10 more minutes, or less, or a lot more. But after 4 hours I’m quite sure it will not finish in the next 10 minutes (that would be a big coincidence). So a guess might be "probably a few hours more". After 4 days I’d be quite certain that it will take a lot longer.

Can you somehow quantify this certainty / uncertainty?

# Answer
> 1 votes
No, you can't make any well-justified estimate, if you truly have *no* knowledge.

In practice, it's rarely that case that we have zero knowledge. Instead, we might have some idea what the distribution of total computation time will look like. That gives you a prior. In other words, before you start the computation, suppose I asked you for your guess at the probability distribution of what the total computation time will be. What probability distribution would you choose? The result is a prior.

If you have a prior, then you can compute an estimate for the remaining run time and quantify the uncertainty, using Bayesian analysis. Let $p(x)$ denote the prior probability that the total computation time is $x$; in other words, before you start running it and before you make any observation, $p(x)$ is your estimate of the probability that it will take $x$ seconds to terminate.

Now we make an observation, and we want to update our estimate of the probability. We observe that the computation has run for $y$ seconds without terminating yet. This implies that, whatever the true value of $x$ will turn out to be, it will be at least $y$. Using Bayes' theorem we obtain

$$\begin{align\*} p(x|y) &= {p(y|x) p(x) \over p(y)}\\ &= {p(y|x) p(x) \over \int\_0^\infty p(y|x) p(x) \\; dx} \end{align\*}$$

We notice that we're going to need to know the distribution $p(y|x)$. This helps us realize that the problem isn't well-stated yet: you haven't told us how you would decide when to make the observation.

Suppose that we decide in advance, before starting the computation, that we're going to wait $y\_0$ seconds and then check whether it has halted or not. Thus there are two possible outcomes of the observation: "already halted" (finished in $\le y\_0$ seconds) or "hasn't halted yet" (will take a total of $\>y\_0$ seconds to finish). Let's denote those by the outcomes "A" vs "H", so we'll say $y=A$ in the former and $y=H$ in the latter. Then we find that $p(y|x)$ has the following form: $p(A|x) = 1$ if $x \le y\_0$, else $p(A|x)=0$; and the reverse for $p(H|x)$. Plugging into the formulas above, we obtain

$$\begin{align\*} p(x|A) &= {p(A|x) p(x) \over \int\_0^{y\_0} p(x) \\; dx}\\ p(x|H) &= {p(H|x) p(x) \over \int\_{y\_0}^\infty p(x) \\; dx} \end{align\*}$$

When $x \le y\_0$, we have $p(x|H)=0$ (naturally). When $y\_0 \< x \< \infty$, we see that $p(x|H) = p(x)/q$, where $q = \int\_{y\_0}^\infty p(x) \\; dx$ is the prior probability that $x$ falls in the range $y\_0 \< x \< \infty$. Here $q$ is a constant that depends on the prior probability; you can think of it as a normalization constant to ensure that $p(x|H)$ is a probability distribution (it integrates to one).

This gives you the posterior distribution for $x$, after running the experiment (starting up the computation and after $y\_0$ seconds checking to see whether it has finished yet) and making the observation (that it hasn't finished yet). From the posterior distribution, you can make estimates for the total running time. For instance, one reasonable way to make an estimate is to compute the expected value of this posterior distribution. In this way we obtain

$$\mathbb{E}(x|H) = \int\_0^\infty x p(x|H) \\; dx = {\int\_{y\_0}^\infty x p(x) \\; dx \over \int\_{y\_0}^\infty p(x) \\; dx}.$$

You can also summarize the uncertainty in your estimate using a 95% credible interval.

As you can see, all of this machinery requires that we have a prior for the total running time. Selection of the prior isn't something math can give you; instead, it needs to reflect your domain knowledge and expectations. Probably you have *some* ideas for how likely it is that the computation will take a certain amount of time. For instance, maybe it's common for computations to take anywhere from 1ms to 1 day, but it's rare to run across computations that take (say) 10000 hours -- usually they'll either complete much earlier, or (occasionally) they'll take much longer, but 10000 hours is a lot less likely outcome than 1 hour. So, constructing a prior is the (subjective) process of quantifying that knowledge you already have. Alternatively, the choice of prior might be informed by data, if you collect a data set of how long other computations have taken to complete and use that to fit some kind of distribution to them.

Once you've chosen a prior, then you can use the mathematics shown above to estimate how long the running time will turn out to be, in a methodologically sound way.

# Answer
> 0 votes
What you are talking about is probably related to exponential distribution and Poisson processes.

> In probability theory and statistics, the exponential distribution (also known as negative exponential distribution) is the probability distribution that describes the time between events in a Poisson process, i.e. a process in which events occur continuously and independently at a constant average rate.

The key property of geometric and exponential distributions is memoryless.

> It is the continuous analogue of the geometric distribution, and it has the key property of being memoryless.

If we discretize time then the process will be similar to tossing a coin ( given probabilities for $Heads$ and $Tails$) and waiting until the first $Heads$. Memoryless property says that the probability of $Heads$ is the same after the first $Tails$, after 10 $Tails$, or after 1000 $Tails$ in a row.

In your statement you don't provide any information implying that the termination of process somehow depends on the elapsed time. So I assume that the process is memoryless.

The exponential distribution may be applied as following. Suppose that you run your computation anew every time it terminates. And suppose that the rate $\lambda$ is taken as the number of terminations per unit of time (you may guess this quantity or you may collect statistical data). For example if $\lambda$ is measured as *number of terminations per minute*, then the probability that the computation will terminate in $t$ minutes is equal to $1 − e^{−λt}$.

---
Tags: statistics
---


title: When are multiple CPU's needed?

text:
# Question
Title: When are multiple CPU's needed?
Forgive me if I'm asking something that should be obvious, my experience is with software development, not computer science. I've glanced at some articles on hyperthreading and parallel processing, but it seems like those implementations are primarily for consumer devices to persist multiple apps at the same time (listen to a music app while browsing the internet) but for non consumer implementations where there is only one primary process, like a VM exclusively used for tensorflow, would there be any benefit to the VM having additional CPU's? There may be other OS processes going on with the VM, but the only way to calculate tensorflow faster would be to use a different hardware, like a GPU or a TPU, right?

# Answer
As Wikipedia states,

> The improvement in performance gained by the use of a multi-core processor depends very much on the software algorithms used and their implementation. In particular, possible gains are limited by the fraction of the software that can run in parallel simultaneously on multiple cores; this effect is described by Amdahl's law. In the best case, so-called embarrassingly parallel problems may realize speedup factors near the number of cores, or even more if the problem is split up enough to fit within each core's cache(s), avoiding use of much slower main-system memory. Most applications, however, are not accelerated so much unless programmers invest a prohibitive amount of effort in re-factoring the whole problem.

Whether you'll see an improvement when running a particular software application depends upon how that software application is built, and whether it can make use of threads to parallelize computation. Some can; others can't.

I don't know what the situation is for Tensorflow, but my impression is that Tensorflow tries to use your GPU if possible, because the GPU is far faster than the CPU at the kinds of tasks Tensorflow is designed for. And, if Tensorflow is using your GPU, then there's little or no benefit to having a multiple-core CPU or multiple threads.

Parallelization *can* be useful for some tasks. For instance, some video processing applications are designed to make use of multiple cores, so even if you're running only one application (the video editor application), it still runs faster with multiple cores than with a single core. It's not just for running multiple applications at the same time.

See also https://superuser.com/q/153833/93541, https://superuser.com/q/2489/93541, https://superuser.com/q/453799/93541, and https://superuser.com/q/949030/93541 for more background.

Hyperthreading is best ignored until you understand the fundamentals of multi-core procoessors and multi-threaded applications.
> 4 votes

---
Tags: cpu
---


title: How 2d cellular automata rules works?

text:
# Question
Title: How 2d cellular automata rules works?
How 2D Cellular Automata rules sequences works? For example, in elementary cellular automata, when we look at the binary sequence of the rule number, we understand that first bit says if all neighbors are white, and the cell itself is white, the cell in next step is black or white ( depend on the value of the bit ).

But how should I analyze and interpret the binary sequence of rule number? How should I implement the 2D CA when I have the rule number, for example when we have rule number 22369621 with r = 2 ( 25 neighbors ) how can I understand the behavior of this 2D CA to implement that?

# Answer
> 3 votes
When we interpret CA rules in a canonical form bijective with the naturals, it's convienient to think in terms of a lookup table array indexed by a neighborhood into the next cell state, or rather a truthtable with a variable from each of the neighborhood cells.

This works when the number of states is a power of two. If not a power of two, you need to use a mixed-radix encoding to remain bijective with the naturals.

The choice of 22369621 as an example rule hints that you haven't fully grasped how many *potential* rules there are with a neighborhood of 25 binary state cells mapping into the next binary state center cell. I assume this rule was chosen because its length up to the most significant one is 25, which shows you might be thinking that it only requires 25 bits to fully encode any rule from this type.

However, 25 (2-state) neighbors -\> 1 (2-state) center cell requires in the worst case 2^25 bits, *not* 25.

Let's take a more simple example from the von Neumann neighboorhood: 5 (2-state) neighbors -\> 1 (2-state) center. This requires at most 32 (2^5) bits.

So now let's take a random number within 32 bits, such as 3427859663.

In binary this is 11001100010100001111110011001111. We can intrepret these 32 bits as the next cell lookup for each of the configurations those 5 cells in the neighborhood can be in:

```
  a        *
b c d -> * f *
  e        *

~a ~b ~c ~d ~e ->  f
~a ~b ~c ~d  e ->  f
~a ~b ~c  d ~e -> ~f
~a ~b ~c  d  e -> ~f
~a ~b  c ~d ~e ->  f
~a ~b  c ~d  e ->  f
~a ~b  c  d ~e -> ~f
~a ~b  c  d  e -> ~f
~a  b ~c ~d ~e -> ~f
~a  b ~c ~d  e ->  f
~a  b ~c  d ~e -> ~f
~a  b ~c  d  e ->  f
~a  b  c ~d ~e -> ~f
~a  b  c ~d  e -> ~f
~a  b  c  d ~e -> ~f
~a  b  c  d  e -> ~f
 a ~b ~c ~d ~e ->  f
 a ~b ~c ~d  e ->  f
 a ~b ~c  d ~e ->  f
 a ~b ~c  d  e ->  f
 a ~b  c ~d ~e ->  f
 a ~b  c ~d  e ->  f
 a ~b  c  d ~e -> ~f
 a ~b  c  d  e -> ~f
 a  b ~c ~d ~e ->  f
 a  b ~c ~d  e ->  f
 a  b ~c  d ~e -> ~f
 a  b ~c  d  e -> ~f
 a  b  c ~d ~e ->  f
 a  b  c ~d  e ->  f
 a  b  c  d ~e ->  f
 a  b  c  d  e ->  f

```

Besides the approach of luts for CA, there are other data structures (or canonical numberings) that tend to remove the redundancies found in the most relevant designed rules that utilize large neighborhoods and especially non-power-of-two states. A good resource for more information about these techniques can be found at the Golly webpage.

http://golly.sourceforge.net/Help/formats.html

Some techniques listed there are:

* Rule tables
* Rule trees (also known as n-ary decision diagrams)

---
Tags: cellular-automata
---


# Question
Title: Is $\Omega^\infty (g(n)$ a more general version of $\Omega(g(n))$?
In CLRS, one question defines $\Omega^\infty(g(n))$ such that: $$f(n) = \Omega^\infty (g(n)) \iff \exists c \in \mathbb{R}^+ : \text{for infinitely many integers } n, 0 \leq cg(n) \leq f(n) \ .$$

My question: What does it mean by "infinitely many integers"? Does it mean $\\{n : n \in \mathbb{Z}\\}$ or does it just mean some infinite subset of $\mathbb{Z}$ (say, for instance, every odd positive integer)?

If the latter is true, then why is $\Omega^\infty$ even useful? I'm struggling to find out what knowing the behaviour of $f(n)$ for some arbitrary infinite scattering of integers could possibly achieve.

If the former is true, why do we care about what a function $f(n)$ does for small $n$ (i.e. for $n \< n\_0$)? Isn't the whole point of asymptotics that we're looking for the behaviour of functions as they approach infinity?

Can someone give a bit of context to the definition of $\Omega ^\infty$, because at the moment, it just seems a very contrived definition.

# Answer
The phrase "for infinitely many integers" means "for an infinite set of integers". This strange definition is what you get when you negate little $o$. That is, for any two functions $f,g \geq 0$, either $f = o(g)$ or $f = \Omega^\infty(g)$. In some cases $f = \Omega^\infty(g)$ is enough to derive certain consequences, and so is a useful property.
> 3 votes

---
Tags: asymptotics
---


# Question
Title: Primal-dual schema in approximation algorithms
I was studying Set Cover via the Primal–Dual Schema on my own that I faced a problem in the following paragraph: Consider an LP-relaxation for an NP-hard problem. In general, the relaxation will not have an optimal solution that is integral(why?? when we relax an LP we can choose the variables from the interval of \[0,1\] so the solution must be integral!!!). Does this rule out a complementary slackness condition driven approach? Interestingly enough, the answer is ‘no’. It turns out that the algorithm can be driven by a suitable relaxation of these conditions!(what this paragraph tries to say, I don't get the concept of relaxation here, why we do it??) I apologize for my long question, I really appreciate if anybody can help me.

# Answer
You are asking many questions. I will only answer the first.

The answer to the first question is that in linear programming we cannot enforce the variables to be integers. Therefore the optimal solution could be *fractional*. Consider for example the vertex cover problem for a graph $G = (V,E)$:

$$ \begin{align\*} &\min \sum\_{v \in V} x\_v \\ s.t. \quad& x\_u + x\_v \geq 1 \text{ for all } (u,v) \in E \\ & x\_v \in \\{0,1\\} \end{align\*} $$

This is an integer program whose LP relaxation is

$$ \begin{align\*} &\min \sum\_{v \in V} x\_v \\ s.t. \quad& x\_u + x\_v \geq 1 \text{ for all } (u,v) \in E \\ & 0 \leq x\_v \leq 1 \end{align\*} $$

Now take the case of the triangle. The smallest vertex cover has size 2, but the optimal solution for the LP is $(1/2,1/2,1/2)$. As you can see, it isn't integral.
> 2 votes

---
Tags: algorithms, approximation, linear-programming
---


# Question
Title: Finding MST for connected graph with $|E|=|V|+87$
Given $G=(V,E)$ undirected, connected graph and weights given by $w:E \to \mathbb R$. We also know that $|E|=|V|+87$.

Find Minimum spanning tree of $G$.

---

Obviously we can use Prim in $O(|V| \cdot \log |V|)$.

But can we do better by using the fact that the graph is connected, and use the sets sizes? Like removing the lightest edge from each cycle and keeping the connectivity of the graph?

# Answer
> 3 votes
The "Cycle Property" helps (If you don't know it before, try to prove it first):

> Let $C$ be any cycle in $G$ and $e$ a heaviest (not necessarily unique) edge in $C$. Then there exists some MST which does not contain $e$.

You are encouraged to answer the following questions:

* How to identify a cycle and then a heaviest edge $e$ in it?
* What to do with the edge $e$?
* How many times should you apply the cycle property?
* When to stop?

Then analyze the time complexity.

# Answer
> 2 votes
Nice exercise. Here's a hint for you:

> How many edges will be in the spanning tree of $G$? How many edges will be omitted?

Spend some time thinking about that, and what its implications might be.

Then, if you're still stuck, here's one more hint:

> Often when thinking about MST problems, it helps to first solve the problem under the assumption that all edge weights are unique, so let's assume that. What characterizes the edges that are omitted?

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


title: Lower Bound for Sorted 2-Sum

text:
# Question
Title: Lower Bound for Sorted 2-Sum
> Given a sorted array of integers $x$ and a target value $t$, determine if there exists a pair $x\_i, x\_j \in x \wedge i \neq j$ such that $x\_i + x\_j = t$.

What is the lower bound for this problem?

---

I know for the generalized $k$-sum (unsorted) there is a lower bound of $\Omega(n^{\lceil \frac{k}{2}\rceil} )$. This would mean if the array were unsorted we could prove a lower bound of $\Omega(n)$. I would assume sorting it would give us some sort of extra information. I also haven't seen any lower bound claims of this problem so feel free to link a solution if one already exists.

It is relatively easy to show a lower bound of $\Omega(\log\_2 n)$ using an adversary:

1. Create $x$ such that every sum of each pairs of integers is unique (hint: Fibonacci Numbers).
2. We also have that the target $t$ is larger than all values so no values can be preemptively discarded (hint: add a reasonable constant to all values).

Now we have $\frac{n(n-1)}{2}$ possible target values. Using an optimal binary search of these target values it takes $\Omega(\log\_2 (n^2)) = \Omega(\log n)$. So it's easily lower bounded by $\log n$.

Although the algorithm can't necessarily perform an optimal binary search, because it takes at least $\Omega(n^2)$ to create all the unique sums of pairs. Unless it could figure out the median of all sums of pairs in less time than it takes to create them (another interesting question).

I would assume we can take advantage of this lack of knowledge in some way to establish a greater lower bound, possibly $\Omega(n)$. The standard algorithm to solve this takes $O(n)$ using two pointers. It does this because it's difficult to discard particular values without explicitly checking them. Any help would be greatly appreciated.

# Answer
Consider the following problem I'll call check-for-ones (where it is easy to show a lower bound of $\Omega(n)$): given a binary array of length $n$, check if there are any 1s in this array. We'll reduce this problem to the sorted-2-sum problem, thereby showing that sorted-2-sum also should require $\Omega(n)$ time.

We need to be a bit careful what we mean by "reduce" here; the standard notion of polytime reduction is useless, and even a linear-time reduction doesn't say much since we can solve both problems trivially in linear-time. Our reduction will have the following property: it will reduce an instance $y$ of our check-for-ones problem to an instance $x$ of the sorted-2-sum problem such that for any index $i$, we can compute $x\_i$ in time $O(1)$ given random access to $y$ (assuming that all word operations take $O(1)$ time).

Now, if you can solve sorted-2-sum in $O(t)$ time, you read in at most $O(t)$ values $x\_i$, and each $x\_i$ can be computed from associated $y\_j$ in $O(1)$ time, and therefore you can also solve check-for-ones in $O(t)$ time.

Here is the reduction. Let the array $x$ have length $2n$. When reading a value $x\_i$ proceed as follows:

* If $1 \leq i\leq n$, let $x\_i = -100(n+1-i)$
* If $n \< i \leq 2n$, let $x\_i = 100(i-n) + y\_{i-n}$

Now, the equation $x\_{j} + x\_{k} = 1$ has a solution iff there exists a $y\_{i} = 1$ (in particular, $(j,k)$ must be a pair of the form $(n-a, n+a-1)$).

An example might help as well, let $y$ be the following:

$$y = \\{0,0,1,0\\}$$

We then have that $x$ (if we were to have read $O(n)$ values) would be:

$$x = \\{-400, -300, -200, -100, 100, 200, 301, 400\\}$$

We can see how $x\_j + x\_k = 1 \Leftarrow \Rightarrow \exists y\_i =1 \in y$. In our case, $-300 + 301 = 1$ implies $y\_3 = 1$.
> 5 votes

---
Tags: lower-bounds
---


title: Understanding church numerals

text:
# Question
Title: Understanding church numerals
I am learning lambda calculus as my previous questions indicate . But in a different book , namely , The structure and interpretation of computer program I cam across the concept of "church numerals " and the stumbled upon the following link about church numerals :

https://www.cs.rice.edu/~javaplt/311/Readings/supplemental.pdf

It goes on stating the following in the first page :

The Church numerals that follow just have additional applications of the successor function:

$$\begin{align} C\_2 &= \lambda f . \lambda x . f(fx) \\ C\_3 &= \lambda f . \lambda x . f(f(fx))\\ C\_4 &= \lambda f . \lambda x . f(f(f(fx)))\\ &\vdots\\ C\_n &= \lambda f . \lambda x . f nx \end{align} $$

and then he mentions that had we been having a little more powerful language then we could define the following two functions : $$\begin{align} S &= \lambda r.\text{“ring the small bell (ding) and apply r”}\\ Z &= \lambda r.\text{“ring the big bell (dong)”} \end{align} $$ and then says that the application of

$C\_4$ to $S$ and $Z$ would yield "ding ding ding ding dong"

How to explain the above result without even knowing what "f" is ?

POST EDIT : After I got the first answer , I tried computing the sequence by the help of clue provided .

By applying step by step I will get (lambda r.ding r)^4 (lambda r.dong) = (lambda r.ding r)^4 dong .

Now each evaluation of (lambda r.ding r) leads to "ding r " .

So the overall evaluation becomes "ding ding ding ding r dong ".

Am I doing it right ?If yes then , how to account for omission of r in the expression?

P.S : For some trivia information , has there been any known application of this idea of church numerals to any field of mathematics ?

# Answer
Using your definition for Church Numerals and trying to see what's going on:

$$ \begin{align} 0 &= \lambda f. \lambda x. x \\ 1 &= \lambda f. \lambda x. f x\\ 2 &= \lambda f. \lambda x. f f x\\ 3 &= \lambda f. \lambda x. f f f x\\ &\vdots \end{align} $$

Now let's say have a function $g$ and some $a$, try to use $g$ and $a$ as arguments to $0$, that is:

$$ \begin{align} 0 ~ g ~ a &= (\lambda fx. x)~g~a\\ \quad &\rhd\_{1\beta} (\[g/f\] (\lambda x.x)) a = (\lambda x.x) a \\ \quad &\rhd\_{1\beta} \[a/x\]x = a \end{align} $$

So $g$ applied $0$ times to $a$ returns $a$.

Now try to do the same with $1$.

$$ \begin{align} 1 ~ g ~ a &= (\lambda fx. f~x)~g~a\\ \quad &\rhd\_{1\beta} (\[g/f\] (\lambda x.f~x)) a = (\lambda x.g~x) a \\ \quad &\rhd\_{1\beta} \[a/x\]g~x = g ~ a \end{align} $$

So $g$ applied $1$ time to $a$ is indeed $g(a)$.

Your problem is $4 ~ g ~ a$, where $g$ is $S$ and $a$ is $Z$.

$$ \begin{align} S &= \lambda r.\text{“ring the small bell (ding) and apply r”}\\ Z &= \lambda r .\text{“ring the big bell (dong)}” \end{align} $$

Doing $1 ~ S ~ Z$ we already know that evaluates to $S(Z)$. And that translates to **"print 'Ding' then apply $r$ "**, where $r$ just prints **'Dong'**. So it outputs **'Ding Dong'**.
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: What does it mean that HDLs "explicitly include the notion of time"?
I got onto the topic of HDLs (Hardware Description Languages) from a comment elsewhere on this site.

The Wikipedia article states, rather tantalizingly:

> One important difference between most programming languages and HDLs is that HDLs explicitly include the notion of time.

I tried to dig deeper in the article to better understand this statement, but I didn't get far.

One thing I did find was this great diagram of a flip flop, which certainly demonstrates the *need* to consider timing in hardware design. Rather than dealing with explicit on/off states, you are also dealing with high/low voltage *propagation.*

Naively, though, my immediate thought was, "Huh? *All* imperative languages include the notion of time. Only declarative or functional programming languages could be said to exclude the notion of time, and only by certain specific interpretations."

I think there *is* a valid point being made here, though, and I would very much like to better understand it. It's even stated to be an "important" difference. :)

---

So, again, **what does it mean that HDLs "explicitly include the notion of time"?** How does that distinguish them from programming languages in general from a CS standpoint?

# Answer
> 5 votes
Programming languages usually don't have a notion of time. They describe how things are sequenced, but usually they don't go further. When they do, that's relegated to the library part of the language, and it is to handle time computation or to handle real time measurement and delay.

HDL are used for two purposes: synthesis and simulation. For the first purpose, there is no more use of time than for a programming language. For the second purpose, time is inherently part of what is to be simulated. You need to know after which delay $Q$ will change after a change of $R$, and after which delay $\bar Q$ will do the same. The time here is thus not the real time, but a simulated one, which has no easy relationship with the real time during which the simulation will occurs.

Your circuit will be described in a VHDL-like syntax:

```
Q <= not (R or QBar) delay 1ns;
QBar <= not (S or Q) delay 1ns;

```

You can also write an oscillator, with no stable state:

```
Clock <= not Clock delay 5ns;

```

Time is thus present in the syntax of the language, and in its semantic as well (the language clearly states that $\bar Q$ will change 2ns of simulated time after $R$ does).

# Answer
> 2 votes
Imperative languages only implicitly have a notion of time. Primarily, demarcated by mutation of state, i.e. there's a before some variable was mutated and an after some variable was mutated. Declarative languages, as you say, don't have a notion of time *unless they explicitly model it.* There are a variety of ways of modeling time. Ptolemy II has a rather comprehensive framework and analysis, so I highly recommend looking at it and reading the book System Design, Modeling, and Simulation using Ptolemy II.

Hardware description languages (HDLs) are typically synchronous reactive (SR) languages like Lucid Synchrone, Esterel, and Sig. (Note, these are *not* HDLs but languages with a similar programming model.) The Dedalus language can be thought of as a synchronous reactive language, though that wasn't really the intent behind it. It nevertheless gives a concrete model of what's happening. Discrete functional reactive programming is a similar but distinct approach.

Another class of languages that are complementary is synchronous (or static) dataflow (SDF) languages such as StreamIt. The word "synchronous" here is being used in a different sense than in "synchronous reactive". Synchronous dataflow languages are probably better thought of as stream processing languages and they are widely used for signal processing tasks of various sorts. There are connections between these two models. A synchronous reactive program with no feedback corresponds to a homogeneous synchronous dataflow program. In a synchronous dataflow program, we have a bunch of stream processing functions where we know statically how many elements in each input stream each function consumes to produce a given number of elements in their output streams. If the rates are consistent — which can be statically checked — then it is possible to schedule the code so the inputs are always available and buffers with fixed, statically known sizes can be used. This model doesn't actually have a notion of time, but if the overall input streams represent regularly timed events, then the rates gain temporal significance.

The synchronous reactive model does have an explicit notion of time. In this model, there's a global (logical) clock. Every function is called on each tick. We can think of this as like the synchronous dataflow model except every stream processing function has a 1:1 rate. However, unlike the synchronous dataflow model, values can be absent and we can detect this. Another difference from the synchronous dataflow model in some synchronous reactive languages is that calculating a value at a particular time may (conceptually) require a fixed point calculation because the scheduling (within a tick) is data dependent. It's typically possible to do static checks to avoid this situation entirely.

Usually synchronous reactive systems allow different rates for different stream processing functions and this is what the absent values are typically used for. Conceptually, there's a "fastest" logical clock and every stream processing function is executed on every tick of that clock and running on a different (slower) clock means producing absent values for some ticks of the faster clock. To avoid needing to actually represent the absence/presence of values, static analyses can be done to make sure every stream processing function only attempts to read present values. Lucid Synchrone has a fairly sophisticated approach involving a type system and clock variables. It does also support explicitly reifying the absence/presence via its signal feature.

All the discussion above has used a logical notion of time. It's easy to go from there to a notion of real time by simply specifying a rate for the top-level fastest clock(s). However, the logical time model treats calculations as happening instantaneously. The execution time can be modeled by inserting delays into operations and/or using clocks running at different rates. However, while VHDL and Verilog do use a programming model similar to what I've described above, and they do provide annotations to specify timing, the latter are more descriptive than prescriptive. A functional simulation doesn't need them and the synthesizer ignores them (i.e. it assumes they accurately describe the chosen hardware). The annotations get used for timing simulations. In a functional simulation, the delays that need to exist for situations like your flip-flop to have a well-defined behavior are called delta delays and are conceptualized as "infinitesimal" time delays. In the SDF model, these delays would happen automatically. In a synchronous reactive model delays would need to be inserted (though will typically be embedded in primitives) and the delta delays correspond to ticks of the global logical clock. The notion of superdense time described in the Ptolemy II book in section 1.7.2 may also be a useful tool here.

So, in a hardware description language time enters in two distinct but correlated way. One is as an implicit part of the programming model and as a more logical notion. Another as explicit annotations to be used for timing simulation that can interact with the programming model. The latter can be coupled to the former by modeling the timing annotations as finite delays in terms of a sufficiently fine-grained logical clock. This requires delays be specified for everything (directly or indirectly) and is more computationally-intensive to model than the functional simulation (if for no other reason) because it's doing essentially the same thing at a finer grain. Sometimes the functional simulation is described as a Discrete Event (DE) simulation (another model of time described in the Ptolemy II book), but for synchronous sequential logic this more or less reduces to SDF or SR. (In general, in the DE model you can schedule an event to happen at any time in the future and simulation of it involves repeatedly processing the earliest unprocessed event in a priority queue. In \[synchronous\] sequential logic, events are being produced regularly and for a HDL "scheduling" something for the \[distant, i.e. more than a cycle away\] future would be explicitly modeled by, say, decrementing a counter until it reached 0.)

# Answer
> 1 votes
HDL's incorporate a notion of time in the following sense: they may allow you to talk about the current value of the circuit's state (e.g., registers) and the next value of its state. So, you might be able to write something

`next(v) := x XOR y`

where `x` represents the current value of `x` (in the current clock cycle) and `next(v)` represents what the value of `v` will be in the next clock cycle.

I'm not sure what the Wikipedia author meant when they said that most programming languages don't explicitly include a notion of time. Most programming languages don't have a `next()` operator, so perhaps that is what was meant.

---
Tags: programming-languages, real-time
---


title: Meaning of $NL$ Complexity Class

text:
# Question
Title: Meaning of $NL$ Complexity Class
I am aware of the complexity classes $P$, $NP$ and $L$. But I am not clear what $NL$ or Non-deterministic Log Space intuitively means. The part what I am unclear about is what is the meaning of Non-deterministic Space?

A Turing machine in a $L$ case would read an input, read/write on the work tape that is logarithmic in size, update its internal state, move the read write head on the work-tape and read head on the input tape. And at appropriate time it halts.

What does Non-determinism on work tape mean and how does the Turing Machine behave. I am totally lost on this one? An intuitive explanation would help.

# Answer
Nondeterminism is not about tape or space. It is just a computational model.

One way of thinking of how a nondeterministic TM works is parallel computation. Given an input $x$, a nondeterministic TM may start many parallel (branches of) computation and wait for answers. If all branches terminate then the whole computation terminates. In addition if at least one of them terminates with YES then the TM accepts the input. In particular a nondeterministic TM may run exponentially many branches at the same time. However a deterministic TM is not allowed to run more than one process (branch) at the same, so less powerful in terms of time. But in terms of decidability they are equivalent.

For example consider 3SAT problem with variables $x\_1, \dots, x\_n$. Then on nondeterministic TM we can check all $2^n$ settings of the variables at the same time, while on a deterministic TM we will have to check each settings one by one in sequence.

NOTE: unlike a deterministic TM a nondeterministic TM is a hypothetical abstract model which is not something we use in our everyday life.

**Definition of space complexity for nondeterministic Turing machines:**

> If $M$is a nondeterministic TM where all branches halt on all inputs then its space complexity is the maximum number of tape cells it scans on any branch of its computation.

In particular if a TM scans at most $O(log(n))$ working tape cells on **every** input of length $n$ then we say its space complexity is logarithmic. It also worth noting that requiring $O(log(n))$ space does not restrict running time. A TM may decide in exponential time but still use logarithmic space.

Typically, when dealing with *sublinear*, $log(n)$, space bounds we use Turing machines with two tapes: input read only tape, and working tape which contributes to space complexity.

Then formally $L = SPACE(log(n))$. $L$ is the class of languages that are decidable in logarithmic space on a deterministic TM. That means that a deterministic TM decides using no more than log space. If we switch from a deterministic TM to a nondeterministic TM then we have $NL = NSPACE(log(n))$, that is, the class of languages that are decidable in logarithmic space on a nondeterministic TM.

Thus, meaning, or more formally members, of $NL$ complexity class is all languages decidable:
1) on nondeterministic two tape TM
2) using at most $ O(log(n))$ space on work tape.

**Example**: the language of the problem deciding for a graph whether or not there is a simple path between nodes $s$ and $t$. This language is in $ NL$ class, but if it is in $L$ class is unknown.
> 7 votes

---
Tags: complexity-theory
---


# Question
Title: What should I read before tackling Michael Huth's Logic in Computer Science: Modelling and Reasoning about Systems?
I have to read **Logic in Computer Science: Modelling and Reasoning about Systems** by M. Huth and M. Ryan for a class next semester. However Amazon reviews say it's hard to read unless you're an advanced student and I'm very new to computer science. Is there any other book I may read before I approach this one that would make it easier to understand?

# Answer
From the Preface of the 2nd Edition:

> The book requires that students know the **basics of elementary arithmetic and naive set theoretic concepts and notation**. The core material of Chapter 1 (everything except Sections 1.4.3 to 1.6.2) is essential for all of the chapters that follow. Other than that, only Chapter 6 depends on Chapter 3 and a basic understanding of the static scoping rules covered in Chapter 2 – although one may easily cover Sections 6.1 and 6.2 without having done Chapter 3 at all.

Of course, having elementary prerequisites and being easy are two different things. I've only read the first two chapters as a way to self-teach some logic so I can't comment on the 'latter' material.

The cool thing is that you're only obligated to read the first chapter and then you can proceed to read most of the other chapters in whichever order suits you. If you want a free supporting material, there's the Stanford Logic MOOC and the Mathematics for Computer Science course from MIT.
> 3 votes

---
Tags: logic, books
---


# Question
Title: Is it possible to do Dependent Types in Typed Racket?
Is it possible to use Dependent Types in the existing Typed Racket implementation? (ie do they exist in it?)

Is it reasonably possible to implement a Dependent Types System using Typed Racket?

# Answer
> 5 votes
Dependent Types in Racket are being worked on by Andrew Kent at Indiana University.

There is a set of slides. There is a talk.

Of interest, this potentially also impacts Typed Clojure, which is strongly modeled on Typed Racket.

# Answer
> -1 votes
I think to "do dependent types" using contracts is already possible. Check https://docs.racket-lang.org/guide/contracts-struct.html and look for "Checking Properties of Data Structures".

You could argue, that this is rather simulating the effect, than having it as part of the language. However, somewhere you'll need to write the code, which tells the interpreter/compiler what those dependencies are and in Racket you can do that with contracts.

---
Tags: programming-languages, typing, type-checking, dependent-types, lisp
---


# Question
Title: What is the difference between caching, buffering and paging? Expecting a detailed answer on the OS level
I have been reading about caching and buffering it seems about the same to me can't get hold of the differences clearly and paging, for now the only difference I understand between paging and caching is that, pages store locations of data that are frequently accessed and so CPU can use the address to locate the data, whereas in caching the data itself is stored and wanting process directly acquires the data from the cache. I'm not sure if I'm entirely right which is why I posted the above question.

# Answer
Paging, caching, and buffering are too broad topics to cover in a single post. Briefly, they serve different purposes:

Operating systems use **paging** as a memory management scheme. A computer stores and retrieves data from secondary storage (usually HDD) for use in main memory (RAM). For example, virtual memory implementations use paging.

**Page caching**, on the other hand, is a part of the main memory (say RAM) where you store frequently accesses pages since retrieving from HDD slower than retrieving from the main memory. Please note, I am talking about only page caches. There is for example HDD caches, CPU caches, Web server caches. But all of them have the same goal: to speed up data access.

**Buffering** typically used for data transfer between OS or program and external devices, Input/Output (keyboard, printer, etc).

In some sense caches and buffers are somewhat similar, both for storing temporary data for read/write speedup. However, buffers are usually associated with a certain device (printer, keyboard, or even a particular file). Two different buffers are used for two different files, while raw data from both files may be stored in a single cache. Unlike caches buffers contain metainformation about files or devices. Buffers usually short-lived but caches may live as long as OS or program runs.

This is just very brief information. For further details you may Google and find tons of information on this subject. Or just get a good book on OS.
> 3 votes

---
Tags: operating-systems, cpu-cache, paging
---


# Question
Title: Balanced Binary Search Tree Two-Sum with Constraints
My question spawns from this question. The question is straightforward:

> Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value?

Now the constraints:

1. Constant additional space in regards to $n$, the size of the tree. By this I mean you can use a constant number of $O(\log n)$ bit words however you wish. Assume references to nodes also take $\log n$ bits to store.
2. Read-only access to the tree. No modifications are allowed. This prevents a threaded traversal.
3. A node `n` has the following attributes: `n.left`, `n.right`, `n.value`. This means we have no access to a node's parent. This prevents a successor and predecessor traversal.
4. The algorithm must run in worst-case linear time in regards to $n$, the size of the tree.

It's worth noting that if we remove any one of the four constraints, we can satisfy the the other three relatively easily.

---

My initial thought is that this is not possible. Simply because we can have no memory of where we are in the tree when traversing it.

We could however implement a successor and predecessor in-order traversal using binary searches to find successors and predecessors. This would take $O( n \log n)$.

Another thought was that we could use a non-deterministic algorithm. Possibly a Monte Carlo algorithm with repetition or a Las Vegas algorithm. This randomized algorithm could be used to do a random walk along one path, then have another path search for a compatible node based on the random walk's nodes. I'm not entirely sure if this would work, but these are just some thoughts.

If this is indeed not possible, as I am suspicious, I would also be interested in the following additional modification:

* The algorithm must run in average-case linear time.

# Answer
I don't know how to do this is in $O(n)$ time and $O(1)$ space, but I can show you how to do it in $O(n)$ time and $O(\lg \lg n)$ space. In particular, given any tree of depth $O(\lg n)$, I'll show how to do an in-order traversal in $O(n)$ time and $O(\lg \lg n)$ space. That will be enough to solve this problem.

# Warmup

Let me first establish some notation. At any point in the traversal, we'll currently be at some leaf node $x\_1$. Let $x\_1,x\_2,x\_3,\dots,x\_d$ be the nodes on the path from $x\_1$ to the root (so $x\_1$ is the leaf and $x\_d$ is the root of the tree), where $d$ denotes the depth of the tree. Note that since the tree has depth $O(\lg n)$, it follows that this sequence has length $O(\lg n)$.

For convenience, I'll assume that the tree is a complete binary tree, i.e., all leaves are at the same depth. This simplifies explanation of the main ideas. All of the techniques here generalize to an arbitrary binary tree, as long as its maximum depth is $O(\lg n)$.

An easy way to do a traversal would be to keep track of the entire sequence $x\_1,x\_2,x\_3,\dots,x\_d$. When you want to find the successor, you update the entire sequence. For instance, if $x\_1$ is the left child of $x\_2$, this involves updating just $x\_1$ to its right sibling. If $x\_1$ is the right child of $x\_2$ and $x\_2$ is the left child of $x\_3$, this involves updating $x\_1$ and $x\_2$. And so on. Notice that as we repeatedly compute the successor, the first parts of the sequence get updated more often: $x\_1$ changes every time, $x\_2$ changes half of the time, $x\_3$ changes $1/4$ of the time, and so on. This gives an $O(n)$ time traversal (since $1 + 1/2 + 1/4 + \cdots = O(1)$), but it requires $O(\lg n)$ space.

# The main attraction

Our improvement will be to store only part of that sequence: we'll store $x\_1,x\_2,x\_4,x\_8,\dots,x\_k$ (where $k=2^{\lfloor \lg d \rfloor}$). In other words, we're only storing the power-of-two-indexed elements of the path from the current leaf to the root. Since $d=O(\lg n)$, we're only storing $O(\lg \lg n)$ elements of the sequence.

When we want to find the successor, we might need to update one or more of these elements. As we repeatedly iterate compute successors, the early parts change more often: $x\_1$ always changes, $x\_2$ changes $1/2$ of the time, $x\_4$ changes $1/2^3$ of the time, $x\_8$ changes $1/2^7$ of the time, $x\_{16}$ changes $1/2^{15}$ of the time, and so on. How do we do the updates? To see if $x\_2$ needs to change, we go down from $x\_2$ to $x\_1$ to find the successor to $x\_1$. If $x\_2$ doesn't need to change, we're done. Otherwise, we go down from $x\_4$ to $x\_2$ to find the successor to $x\_2$ (at the same height as $x\_2$). And so on. When $x\_{2^i}$ changes, we go down from $x\_{2^{i+1}}$ to $x\_{2^i}$ to compute the successor to $x\_{2^i}$ at the same height, and this takes $2^i$ steps of computation since we have to traverse $2^i$ levels of the tree; this happens for a $1/2^{2^i-1}$ fraction of the successor operations. Taking all of that into account, the amortized amount of work we do per successor operation is

$$1 + {2 \over 2} + {4 \over 2^3} + {8 \over 2^7} + {16 \over 2^{15}} + \cdots = O(1).$$

This yields an in-order traversal that takes $O(n)$ time and $O(\lg \lg n)$ space.

# Bonus answer

As an extra bonus, I'll show how to do an in-order traversal in $O(n \lg^\* n)$ time and $O(\lg^\* n)$ space. $O(\lg^\* n)$ "might as well be constant" for all practical purposes, so maybe this is of interest.

The construction is a small modification of the scheme I gave above. Define $a\_1,a\_2,a\_3,\dots$ by $a\_1 = 1$ and $a\_{i+1} = 2^{a\_i}$. Now, instead of storing the whole sequence $x\_1,\dots,x\_d$, we'll store just the elements $x\_{a\_1},x\_{a\_2},x\_{a\_3},\dots,x\_{a\_\ell}$, where $\ell= \lg^\* d = \lg^\* (\lg n)$. Notice that $x\_{a\_i}$ changes for a $1/2^{a\_i-1}$ fraction of the successor operations, and when it does change, we do $a\_{i+1} - a\_i$ work. Therefore, the amortized time per successor operation is

$$T = \sum\_{i=1}^\ell {a\_{i+1} - a\_i \over 2^{a\_i-1}}.$$

With a bit of manipulation we can show

$$T \le \sum\_{i=1}^\ell {a\_{i+1} \over 2^{a\_i-1}} = \sum\_{i=1}^\ell {1 \over 2} = \ell/2 = O(\lg^\* (\lg n)) = O(\lg^\* n).$$

Therefore, a traversal of the entire tree can be done $O(n \lg^\* n)$ time, using $O(\lg^\* n)$ time.
> 5 votes

# Answer
This is an attempt to prove a lower bound of $\Omega(n \log n)$ for solving the problem using any comparison based algorithm under the first 3 constraints. (Feel free to point out flaws if you notice them)

There are two core concepts to the proof.

1. The algorithm must visit all non-root nodes.
2. Cost of visiting all non-root nodes is $\Omega(n \log n)$.

---

# Must Visit All Non-Root Nodes

### The Tree Structure

The adversary will maintain a perfect binary search tree. The approach will be similar to @jschnei's reduction here.

Let the tree be of size $n = 2^k - 1$.

We will index the nodes in ascending order about the root for convenience (e.g. $x\_0 = $root, $x\_{-\frac{n-1}{2}} = $min, $x\_{+\frac{n-1}{2}} = $max). We then have a simple way to define node values:

$$x\_i = i \cdot 2$$

For example, let's say we have a tree of size $n = 7$. It will look like the following:

### The Analysis

The adversary will establish the target value as $t = 1$. The adversary will accept queries of the following format:

$$x\_i + x\_j \text{ COMP } t \quad \text{ COMP }= \\{\<, =, \>\\}$$

The adversary will maintain a list of all nodes that have been queried so far. Until every node besides the root has been queried, it is undecided whether or not a pair of nodes will sum to $t = 1$ because if a node has not been checked we could either add $1$ to it and the problem would be satisfied or leave it as is and the problem would not be satisfied.

It is clear to see this will require visiting all nodes except the root, inevitably ending up in the problem not being satisfied. There is no need to visit the root if we have already checked all other pairs because the root is one value not a pair of values and thus it won't matter if it sums to $1$, the problem will still not be satisfied.

---

# Visiting All Non-Root Nodes Takes $\Omega( n \log n)$ Time

We can easily prove this by proving that visiting all leaf nodes takes $\Omega(n \log n)$ time.

Let's first note some things:

1. The algorithm has limited history. We can assume at any point the algorithm has memory of exactly $k$ nodes.
2. A node that has not been traversed yet can **not** be one of the $k$ nodes.
3. The algorithm can **not** traverse *up* the tree. It can however bounce back to any of the $k$ nodes it has previously stored.

At any rate, it is safe to assume we can always create a tree large enough where the $k$ nodes the algorithm has in memory becomes insignificant and the amortized cost of visiting a leaf node will always be $\Omega(\log n)$. Intuitively this makes sense but I'll try to give an informal proof below.

We will assume $k \ll \log\_2 n$. Then at any point in the traversal to a leaf node let's assume the $k$ memory cells contain a set of nodes $y \subset x$ along the path to the leaf. We will include the root node and leaf node in $y$ as an assumption, because if you weren't keeping track of the root you could easily be lost and the other assumption is that we're currently at a leaf. In order from leaf to root we have the $k$ memory cells as $\\{y\_1, y\_2, \dots y\_k\\}$. Let's also define $d(y\_i, y\_j)$ to be the positive difference in depth between two nodes. Then we have:

$$ k \in O(1) \implies \exists y\_{i-1}, y\_i \in y \text{ such that } d(y\_{i-1}, y\_i) = \Omega(\log n)$$

This is obvious because in the best case, the $k$ memory cells are evenly spread about the path to the leaf and then $d(y\_{i-1}, y\_i) = \frac{\log n}{k} = \Omega(\log n)$. In any other case, at least one of the stepwise pairs are spread greater than $\frac{\log n}{k}$.

We then have that for a pair $(y\_{i-1}, y\_i)$ on the path whose depth difference is proportional to $\log n$, getting to any leaf in the subtree rooted at $y\_{i-1}$'s sibling will clearly take $\Omega(\log n)$ time. We can extrapolate this for the new (if indeed new) dispersion of $i-1$ memory cells in this new subtree that there will be some instance of moving to a new subtree (whether it be within this subtree or outside) that will also take $\Omega(\log n)$ even if it is just some fraction of $\log n$. Therefore the total amortized cost of visiting each leaf node will be some proportion of $\log n$, also $\Omega(\log n)$. Thus visiting all leaf nodes will be some proportion of $n \log n$.

The implications of all this is that we must take $\Omega( n \log n)$ time to satisfy the first 3 constraints.
> 0 votes

---
Tags: binary-trees, binary-search-trees
---


# Question
Title: Is it possible to implement a WeakMap with primitive keys and weak values?
### Theory

Basically, I have a use-case where I would like to use primitives to store weak references to non-primitive values. If the value is no longer referenced anywhere else, then the entry should be GC'd from the WeakMap and checking the primitive key for an existing value would return false.

Is this possible to implement, and how so in a theoretical sense? If not, why isn't it possible to?

### Use-case

Since people seem to be confused about the use-case, it's pretty straight-forward. Essentially, consider a function, when given a primitive, generates a non-primitive deterministically using an expensive operation. I expect a fair amount of these generated non-primitives to be used at run-time, and a large percent of them to be re-used.

For the non-primitives that have a reference held onto them, they are used as keys in an operation that coerces them back into the primitive that was used to generate them (this step cannot be avoided, unfortunately), that then must be used to re-generate the non-primitive again.

It would be convenient to have a WeakMap to access the original non-primitive, if it has already been made, instead of using the expensive operation to generate a copy of it, but currently I don't see a way to achieve this.

# Answer
Okay. My confusion with this question is that I assumed that what you wanted is a weak value map, which it appears *is* what you want, and this can be implemented in a straightforward manner (at least as straightforward as a weak key map). I'm using (slightly modified) terminology from Designing Efficient and Safe Weak References in Eiffel with Parametric Types. The JavaScript WeakMap is indeed a weak key map, and, as you seem to understand and D.W. states, it makes no sense to have weak references to primitive values, and thus primitive values as keys in a weak key map.

As far as a weak value map, it's implemented basically the same as a weak key map. For example, for a mark-sweep GC, during the sweeping phase if the GC notices that a value in a weak value map is dead it removes all entries in the map referencing it. A weak key map is basically the same only it considers the keys. The Eiffel paper also talks about weak vectors and doubly weak maps where either the key or the value dying results in the entry being removed.

A weak reference primitive as described in the paper or as in e.g. Java's WeakReference would make this a straightforward exercise. You'd just wrap a `Dictionary<Key, WeakReference<Value>>` to clean out entries on access, say.
> 4 votes

# Answer
It would be pointless to have a primitive as the key in a Javascript WeakMap, as you can't/don't garbage-collect primitives, and a WeakMap is entirely about whether or not GC will garbage-collect the keys in the WeakMap. No purpose would be served by allowing the key to be a primitive.

See also https://softwareengineering.stackexchange.com/q/324345/34181.
> 1 votes

---
Tags: data-structures, programming-languages, efficiency, garbage-collection
---


# Question
Title: Proving the given language isn't context free using Pumping Lemma
i want to prove that the following Language isn't CF

$L=\\{a^kba^kba^k|k\in \mathbb{N}\\}$

Let $z=a^nba^nba^n$ be a String from $L$

$n$ is the pumping length and $|z|=3n+2 \> n$

and $z=uvwxy$ with $|vx|\geqslant 1$, $|vwx|\leqslant n$

but i'm not sure how to determine the correct substrings, how should i consider them ? I tried the ones below are thy correct ?

Case 1 : $u=a^n,\ uwx=ba^n,\ y=ba^n$

Case 2 : $u=a^{n-l},\ uwx=a^lb,\ y=a^nba^n$

Case 3 : $u=a^nb,\ uwx=a^nb,\ y=a^n$

Case 4 : $u=a^nba^{n-l},\ uwx=a^{l-k},\ y=a^kba^n$

Case 5 : $u=a^nb,\ uwx=a^n,\ y=ba^n$

# Answer
The pumping segments $v$ and $x$ can be anywhere in the string assuming they are at most $n$ apart, i.e., $|vwx|\le n$. Like you I get five possibilities, but I think you wrote some special cases rather than the general picture.

Inside one of the $a$-segments, for instance :

* the first $u=a^i$, $vwx=a^j$, $y=a^{n-i-j}ba^nba^n$ where $i+j\le n$ and $j\ge 1$. Or
* the second $u=a^nba^i$, $vwx=a^j$, $y=a^{n-i-j}ba^n$ where $i+j\le n$ and $j\ge 1$. Or
* the third $\dots$ .

Or overlapping with one of the $b$'s. Of course because of the lengths we cannot overlap with both $b$'s.

* First: $u=a^{n-i}$, $vwx=a^iba^j$, $y=a^{n-j}ba^n$ where $0\le i,j\le n$, $i+j\< n$ .
* Second $\dots$ .

**However** this does not solve the pumping problem. Note we repeat the strings $v,x$ when pumping. In these last cases we do not know how $v,x$ look. Do they contain the $b$? More cases.

A **shortcut** to the proof would be to make the following observation.

1. The pumping segments cannot contain $b$.

That leaves five cases for the position of $v$, $x$ in the three $a$-segments. Either deal with them or argue

2. Now that $v$, $x$ can only contain $a$'s we can pump either one or two of the three $a$-segments in $z$. That means after pumping they cannot all contain the same number of $a$'s
> 0 votes

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


# Question
Title: Complexity of determining whether three points are collinear from a set of points
Let $S \subseteq \mathbb{R}^2$ be a finite set of points. Do there exists three collinear points $p, q, r \in S$?

I wan't to know the complexity of this decision problem and present my approach as following.

**SOLUTIONS**. Let $n = |S|$. A naive brute-force takes time $\mathcal{O}(n^3)$. We can simply go through all triplets of points from $S$ and check for collinearity in time $\mathcal{O}(1)$.

I found additionally a $\mathcal{O}(n^2 \log{n})$ solution. For each $p(x\_p \mid y\_p) \in S$, we consider all points $q(x\_q \mid y\_q) \in S \setminus \\{ p \\}$ and compute the slope $m = \left|\frac{\Delta y}{\Delta x}\right| = \left| \frac{y\_p - y\_q}{x\_p - x\_q} \right|$ of the (unique) connecting line through $p$ and $q$. Resulting in a list of $n - 1$ slope values, we sort this list in time $\mathcal{O}(n \log {n})$ and use a linear search taking time $\mathcal{O}(n)$ for checking if two elements of the list are identical. If and only if this happens, three points of $S$ are collinear. Since we need time $\mathcal{O}(n \log {n})$ for each of these $n$ points, the whole thing runs in $\mathcal{O}(n^2 \log{n})$.

(Notice: We may assume the points of $S$ to be unique, because a simple preprocessing in time $\mathcal{O}(n \log {n})$ allows use to find duplicates. If $n \ge 3$ and there exists a duplicate, three points are obviously collinear.)

**LOWER BOUNDS**. A lower bound of $\Omega(n)$ is trivial. But we can do better. Let the set $X = \\{ x\_1, x\_2, \dots, x\_n \\} \subseteq \mathbb{R}\_+^n$ be an instance of the element distinctness problem (EDP). If is well-known, that EDP has a $\Omega(n \log {n})$ lower bound in many computational models (algebraic decision trees for instance). Define $S := \\{ (x\_1 \mid x\_1^2), (x\_2 \mid x\_2^2), \dots, (x\_n \mid x\_n^2) \\}$ and consider the following two cases.

Case 1: All elements of $X$ are distinct. Because the points of $S$ lie on the parabola $y = x^2$, there are no three collinear points.

Case 2: There are two indices $i, j \in \\{ 1, 2, \dots, n \\}$ with $i \neq j$ and $x\_i = x\_j$. Then, $x\_i^2 = x\_j^2$. If $n \ge 3$, select an arbitary value $x^\* \in X \setminus \\{ x\_i, x\_j \\}$. Hence, we found three collinear points: $(x^\* \mid (x^{\*})^2), (x\_i \mid x\_i^2)$ and $(x\_j \mid x\_j^2)$.

By reduction principle, our problems complexity is $\Omega(n \log {n})$. Can we do better or is this lower bound optimal? Is there an $\mathcal{O}(n \log {n})$ algorithm?

# Answer
There is an $O(n^2)$ algorithm for the more general problem of minimum area triangle, see for example these lecture notes. The problem itself (as well as minimum area triangle) is 3SUM-hard, as shown in a survey of King on 3SUM-hard problems, where the problem is known as 3-points-on-line.

See also this stackoverflow question, where I found the links given above.
> 5 votes

---
Tags: algorithms, time-complexity, computational-geometry, lower-bounds
---


# Question
Title: Multi objective optimization using genetic algorithm
I have an objective function `profit = income - expense` . I want to solve it using genetic/evolutionary algorithm (strength pareto SPEA2). Since the algorithm is multi-objective so can I consider the income maximization as one objective and expense minimization as second objective?. I am using SPEA2 matlab code from YARPIZ. I am not sure whether this approach of breaking objective function is technically correct. Secondly, please also throw some light on how to do both conflicting objective simultaneously. The code in link is written for minimization of objective functions, but I have to minimize one and maximize other objective.

# Answer
Just define profit as a variable and maximize porfit as your singular objective. In general the objective will depent on multiple variables indirectly and the variables will usually also depend on each other. If this is not the case there are probably much more effective solutions than genetic algorithms.
> 1 votes

---
Tags: optimization, genetic-algorithms, evolutionary-computing
---