Converting IPV4 address into Binary So given an IP address it is converted into binary via calculating the binary of all different segments and then joining them.
For example, 12.32.18.01 converted into a binary it would amount to this number in decimal form 12*2^24 + 32*2^16 + 18*8 + 01
My question is why to go through all this trouble and calculation. Why not just get rid of the dots in the original Ip and then convert that integer into binary. So, for this example, the binary of the above example would amount to this integer in decimal 112 032 018 001. I mean what's the problem with second approach?

I am going to answer this question in two parts:
First,
Without reaching into the depths of communication, I want to mention that the data that humans do understand(such as this answer which I am typing) is classified under Layer 7 of the TCP/IP stack. This data gets converted into analog signals that travel over the wire, and any hosts connected to these wires translate these analog signals to electric signals. Electric signals have two states, 0 and 1, which we humans call binary format.
So any data on the wire would essentially be looked upon as a sequence of bits and bytes.

The IP address that you mention, is a component of the IP Protocol, and this protocol is used to carry packets end to end between two hosts on a network. So, the data would be added as a payload on top of an IP packet which contains a IP header. Any devices in between these two hosts which operate on Layer-3 of the TCP/IP stack(the network layer!) would use this header to process the packet. Similarly the end hosts would use this header to determine if the packet indeed was sent to them.
The IP protocol specifies the syntax and semantics of the IP Packet header, and as you might notice the size of the fields are fixed. Now any machine which is looking at a sequence of bits coming in (with the knowledge that it is receiving the IP header) can just read as many bytes as it wants to extract every field of the header. For example, given that the system knows where the IP header starts, the system could read the first 4 bits and understand that it would just read the version of IP packet.

Second,
The conversion that you mentioned, between binary and dotted decimal, is purely for representing data in human readable format(as the other answer mentions). Tools like Wireshark do this to show details of a packet(the internals of this are fascinating). So, you can choose whichever method to convert one form to the other, but the machines don't really need to do this at the level of the TCP/IP stack where it really matters.  The system doesn't really see it as a dotted decimal construct, but a data structure which consists of four 8 byte fields, (or two 16).

Hope this helps !


Given list of numbers find for each number in the list the next distinct number Given a sequence of numbers $l_1, \ldots, l_n$, I want to find for each index $i$ the next possible number to the right of $l_i$ (if any) that is different from $l_i$. What is the best time and space optimal solution to do this?

The numbers may be repeating and are in no particular order.

Here is pseudocode for an algorithm which outputs the entire answer array $a_1,\ldots,a_n$:

Set $\mathit{first} \gets 1$ (first index in the current run)
Set $\mathit{curr} \gets 1$ (index of the current element being scanned)
While $\mathit{curr} < n$:
   Set $\mathit{curr} \gets \mathit{curr} + 1$
   If $l_{\mathit{curr}} \neq l_{\mathit{first}}$:
     Set $a_{\mathit{first}},\ldots,a_{\mathit{curr}-1} \gets l_{\mathit{curr}}$
     Set $\mathit{first} \gets \mathit{curr}$
   End If
End While
Set $a_{first},\ldots,a_n \gets \bot$ (no different element to the right)

This algorithm uses linear time and $O(1)$ auxiliary space.


Bias or not when finding patterns using data mining techniques? I am currently following a course on Data Mining and i am very curious about the deeper underlying method. As far as i have learned so far data mining is about finding unknown patterns that can be useful and provide new knowledge about your data.

In data mining, is it okay to start from expectations (bias) as to which patterns could be present and actually do statistics to see if this is actually the case. Say if i have data for the typical example of survivors on the titanic. How would i start doing my analysis - that is: what types of questions would i be asking my self to begin with. Say if i would like to test whether the survival percentage was smaller for a male passenger, i could do some statistical analysis, and find out whether or not that would be the case. I could programme a decision tree and see what my data tells me. That would tell me HOW to use machine learning to analyse the data in order to be able to predict what chance of survival a new passenger x with specific 'properties' would have. What would the data mining perspective come into this process?

I am aware of different types of classifiers and how we can use them to check for patterns in order to do predictions, but how does one go from A (wanting to find patterns) to B (actually finding unknown patterns)) in data mining specifically?

Citing directly from the wiki page of data mining:
"Neither the data collection, data preparation, nor result interpretation and reporting is part of the data mining step, but do belong to the overall KDD process as additional steps." and "Data mining is the analysis step of the "knowledge discovery in databases" process, or KDD."

This indicates that the actual data mining part is the analysis using mathematics, statistics and machine learning tools. Well from here, how would i start finding patterns in a large data set. Would i start from what my prior tells my could be interesting and dig deeper to see whether there actually is an interesting pattern here - and if not, i can conclude that there isn't, which in itself is insightful - and then i can try finding other patterns.
OR do i make an algorithm that randomly tries to find correlations and patterns across different random combinations of attributes in my data, without me choosing ANY direction to look in?
Because one thing i have been taught is that when you work with REALLY large datasets, all sorts of patterns begin to emerge, and no matter where you look, you will find some sort of patterns. The art is to find USEFUL patterns, and patterns that actually provide some kind of insight into your data! As always correlation does not necessary imply causation, but that is for the analysis part, and i guess data mining is all about just finding the patterns - so how do we actually go about and do this.

I hope my question is possible to understand. I find it hard to formulate any better. If i were to boil it all down into one sentence, it would be: If i have a large dataset which i have cleaned and prepared, then from a data mining perspective what is the following thought-process I should use to find patterns in the data?

In data mining, is it okay to start from expectations (bias) as to which patterns could be present and actually do statistics to see if this is actually the case

Sure. This is called hypothesis testing.

  Say if i have data for the typical example of survivors on the titanic. How would i start doing my analysis - that is: what types of questions would i be asking my self to begin with

Exploratory data analysis, see http://github.com/MartinThoma/edapy as a tool.

  how does one go from A (wanting to find patterns) to B (actually finding unknown patterns)) in data mining specifically?

You have a classification problem... So, just train the classifier you want to use.

  If i have a large dataset which i have cleaned and prepared, then from a data mining perspective what is the following thought-process I should use to find patterns in the data?

This depends very much on the context. What I happen to do at the very beginning quite often:

Look at the general distribution of the data per single feature: min, max, mean, median, number of different values. If the number of different values is small, print a bar chart
Null values: why are they there? Can they be replaced by a reasonable other value?
Covariance

  What is the difference between ML and data mining?

Taken from
https://stats.stackexchange.com/a/29186/25741

  Data Mining is about using Statistics as well as other programming methods to find patterns hidden in the data so that you can explain some phenomenon. Data Mining builds intuition about what is really happening in some data and is still little more towards math than programming, but uses both.

  Machine Learning uses Data Mining techniques and other learning algorithms to build models of what is happening behind some data so that it can predict future outcomes. Math is the basis for many of the algorithms, but this is more towards programming.


Finding shortest paths in undirected graphs with possibly negative edge weights The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge weights (not by treating an undirected edge as two directed one which means that a single negative edge implies a negative cycle). However, no references are given in the book. Are you aware of any such algorithms?

Q. How can we find shortest paths in undirected (edge-weighted) graphs?
A. For positive edge weights, Dijkstra's algorithm does the job. We just build an EdgeWeightedDigraph corresponding to the given EdgeWeightedGraph (by adding two directed edges corresponding to each undirected edge, one in each direction) and then run Dijkstra's algorithm. If edge weights can be negative (emphasis added), efficient algorithms are available, but they are more complicated than the Bellman-Ford algorithm.

I contacted one of the authors (Kevin Wayne; thanks) of the textbook "Algorithms, 4th Edition" and got a hint:

  Try adding "t-joins" or "perfect matching" to your web searches.

Following this, I found the following two lecture notes:

Shortest Path Algorithms Luis Goddyn, Math 408: Using Edmonds' Minimum Weight Perfect Matching Algorithm to solve shortest path problems for undirected graph with negative-weight edges, provided that $(G, d)$ is conservatively weighted, that is, if $G$ has no negative weight directed circuits (circuits $C$ whose total weight $d(C)$ is negative), then Dijkstra’s algorithm stops with a shortest path tree $T$ rooted at $s$.

$T$-joins and Applications from CS 598CSC: Combinatorial Optimization uses the $T$-join techniques.


Is the balanced parentheses language inherently ambiguous? I have this grammar:

$S\rightarrow SS |S \rightarrow(S)|S\rightarrow\epsilon  $

Now this grammar generates the set of balanced parentheses. But this grammar is ambiguous. I am trying to find an unambiguous grammar for this language but all in vain. This has led me to believe that the language is inherently ambiguous. Am I true? If not please provide an unambiguous grammar for this language.

$$S \rightarrow (S)S$$
$$S \rightarrow \epsilon$$

Generalising this to other Dyck languages is left as an exercise.


Genetic algorithm does not always find the global optima and a higher mutation rate finds a better solution I wanted to make a tool which minimizes the interference between antennas.

Currently, the tool is very limited for prototyping reasons. It can only place an antenna every 1 meters. The available space that the antennas can be placed is 1 dimensional and is 15 meters wide.

The user can only decide how many antennas will be used (e.g. 3 antennas).

I decided to encode the setup as follows: a binary array where 1 represents an antenna and 0 is an empty space because it seemed straightforward. The length of the array is thus the available space to place those antennas (= 15 meters).

For example, here are all the antennas on the left: 11100 00000 00000 and here they are on the right: 00000 00000 00111.

My mutate function enforces that the offspring contains only 3 antennas. If it is not the case the mutate function will try again. Same thing for the crossover.

In this case, the total search space consists of 455 solutions since there are only 455 ways to place those antennas.

I benchmarked a little bit the algorithm and I got the following results:

If I use a 5% of the search space, thus a population of 7 with 4  generations (7 * 4 = 28) then I got a solution which is better than 96% of the 455 solutions.
If I use a population of 10% of the search space, thus a population of 9 with 5 generations (9 * 5 = 45) then I got a solution which is better than 98% of the 455 solutions
The higher the mutation rate the better the results. This one is very strange since the algorithm becomes more and more a random search. I thought that it should normally give worst results. The difference of the results is 1-2% better when using a mutation rate of e.g. 0.8 instead of 1 / n = 1 / 15 (where n is the length of the encoding).

Finally, I have two questions:

I got a good solution but never the best one, even by using 10% of the search space. Is this normal?

A higher mutation rate gives me better results? Is it because I am working with a toy problem? Or is my encoding bad?

I'll start with the second question because it's easier.  How could increasing the mutation rate improve the results?

Genetic algorithms can beat random searches when they converge on the right answer.  Similar to other machine learning algorithms, genetic algorithms have an "explore" phase and a "converge" phase.  If the algorithm doesn't run long enough (enough rounds) to enter the converge phase, then a higher mutation rate will likely give you better results.  The other culprit may be that the utility score of offspring may be independent of the utility score of the parents even though their parameters are very similar.  If this is the case (especially around "good" results) then convergence may be impossible and random search would outperform genetic algorithms.

The other question "Why didn't I ever find the best solution?" could also have a few explanations.  First, you could have just been unlucky - especially if you didn't run your experiment very many times.  Intuitively, a single run searching 10% of the space will have roughly a 10% chance of finding the best solution.  Second, it may be that all antenna configurations which are similar to an optimal solution have low scores.  This would make it less likely to produce the optimal solution genetically.


Why does the program counter increment before an instruction is completed? During the fetch, decode, execute cycle, the Program Counter (PC) increments after the operand is copied from the Memory Data Register (MDR), and then carries on with the processing of the instruction.

Why does the PC increment in the middle of the cycle rather than at the end?

My only guess would be that it relates to jump instructions being incremented but I cannot find any sources on this.

The exact details of when (or even how) to increment the program counter are implementation specific details. There are however a few considerations that come into play across most computers.

After sending out the PC address, there is (almost) always a delay waiting for memory to respond. Thus there's often not a lot going on. One possible use of this "dead" time to do something useful, like incrementing the PC.
The next instruction is going to need the incremented value of the PC before it can proceed. If the processor does this at the end of the instruction, then the PC increment becomes part of the critical path for the next instruction.

The thing is, once this becomes part of the programming model for a processor, it is difficult to change the outward semantics of the PC increment. Consider processors with a PC relative addressing mode. If the value retrieved were to change from incremented to non-incremented, almost all the code would break. Thus the decisions made for early versions of a CPU must be honored in later (pipelined/overlapped/multi-way executing/multi-threaded/etc) versions of that CPU family.

Finally, and while silly sounding, most important; People are just used to having processors work that way. Some really great gains would be needed in order to ignore this bit of orthodoxy.


How are system calls handled in a virtual machine? Quoting wikipedia, a system call is:

  In computing, a system call is how a program requests a service from
  an operating system's kernel. This may include hardware related
  services (e.g. accessing the hard disk), creating and executing new
  processes, and communicating with integral kernel services (like
  scheduling). System calls provide an essential interface between a
  process and the operating system.

In ordinary operating systems, when a system call is made the operating system enters kernel mode and performs the requested operation.

What happens to a system call made by a process in a virtual machine? Is it handled by the virtual machine only, or is it delegated to the outer kernel to be operated by the hardware-facing kernel?

There are 3 common strategies to handle this:
1. Hypervisor traps system calls from guest:  The hypervisor checks whether the privileged instruction(effectively system call) came from the guest OS itself, or from a user-space program within the guest OS. If it's the former case, then the hypervisor will actually forward the call to the hardware, although through the virtualization instructions. If it's the latter, the hypervisor will redirect the call to the guest OS, and then proceed.
2. Binary translation: Here the hypervisor checks the code from the guest OS in what are called as "basic blocks", scanning for privileged instructions. Wherever it finds them, it replaces them with calls to it's own procedures to system calls. It then proceeds to cache these blocks & eventually builds a whole set of such blocks.
3. Paravirtualization: Here the guest OS itself is modified so that instead of making calls to the hardware, it has APIs to invoke the hypervisor to get its hardware I/O done.

Source: Modern Operating Systems by Andrew Tanenbaum


Getting maximum number of pairs in a set I'm sorry if the title is unclear, I didn't know how to name this question.

I have a problem where I have an array of numbers with positive integer values. For a pair of these integers to be considered valid, they should follow the format a^2 + b^2 = x^2, where a and b are the integers, and x is any whole number.

What I need to do is to find the maximum number of pairs that can be used concurrently (for example, if I have numbers {3, 4, 4}, the answer would be 1, even though there are two valid pairs (3 and the first 4, as well as 3 and the second 4), because we can not use both of these pairs at the same time.

Can anyone point me in the right direction toward solving this problem without brute-forcing all the combinations?

Your problem is an instance of maximum matching, for which there exist efficient algorithms. The vertices in the graph are the entries of the list, and the edges correspond to allowable pairs.


Official Name for the “First” Programming Language Developed by Turing? As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions on how they operate. Is there any official or widely accepted name for this "first" mathematically defined programming language$^*$ $L$ that consists of a specification of a Turing Machine together with its transition function?  Clearly by definition this language is Turing complete and hence can simulate any other algorithmic programming language. For instance here would be how program of $L$:

//Some specification of the machine $M$'s states, initial state, final state, allowable tape symbols, blank tape symbol, etc.

<0, 0, 1, R, 2>   // If $M$ is in state 0 and sees a 0, then write 1, move right, and enter state 2

<2, 0, 0, R, 3>  // If $M$ is in state 2, sees a 0, then write 0, move right, and enter state 3

<2, 1, 0, L, 3>  // etc

*By first mathematically defined programming language, I'm ignoring for the moment innovations like automated loom printing or natural programming languages like DNA/RNA which are definitely algorithmic, and instead focusing on a particular strand of algorithmic specification that most closely matches what is commonly thought of as a programming language today. There are also other mathematically defined systems that were shown to be Turing equivalent around the same time as Turing, but none of these really caught on in terms of influence as Turing machines and their programming language did.

Turing machines are not programmable. Each Turing machine computes only one function. Hence they do not use any
programming language. What you see as a language is the description of
the machine itself, not of a program in some programming language. Thus the name "Turing machine" is the only appropriate terminology.

Now it turns out that there are devices that can emulate Turing
machines, such as a computer programmed to do such an emulation.  They
can use the description of a Turing machine to simulate its
computation. This is very similar to a hardware emulator that can
mimic the hardware of a computer from a formal description of the
circuits.

The abstract theoretical model of such an emulation, as then performed
by a Turing machine is called a Universal Turing machine. But
universal Turing machines are in no way specialized for that kind of
description. It is a much more general concept. The most general name for the input to a universal Turing machine could possibly be "Natural numbers".

However, in his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, Turing uses the kind of encoding you have in mind as input to be properly encoded for his universal computing machine.
He calls it "standard description", abbreviated as "S.D.".

But it is not the first Turing complete language, even ignoring earlier theoretical work such as done by people like Church and Gödel.

You view of history is missing an earlier invention, which is Charles Babbage's Analytical Engine. Lady Augusta Ada King, Countess of Lovelace, is considered the first programmer in history, though her computer, Babbage's engine, never worked in her lifetime. I do not know that the "assembly language" for the engine received a name. According to Wikipedia it would have been Turing complete.


What's the input to the decoder in a sequence to sequence autoencoder? What's the input to the decoder part of a sequence to sequence autoencoder? I've seen certain examples of such an autoencoder (using LSTM's more often than not) but am still unclear.

For example, here in this often-cited paper by Dai & Le ('Semi
Supervised Sequence Learning'), we have the following diagram:

What's the input to the decoder portion of the autoencoder here? In this example it's 'W-X-Y-Z.' But in general, is
it the same as the input to the encoder? Or is it using the output
from the previous timestep/LSTM cell as input?
Similarly, in another popular paper by Srivastava et. al
('Unsupervised Learning of Video Representations using LSTMs'), they
have the following diagram:

It seems they're using the reversed input from the encoder as input
here. However, there's a section as follows:

  The decoder can be of two kinds – conditional or unconditioned. A conditional decoder receives the last generated output frame as
  input, i.e., the dotted input in Fig. 2 is present. An unconditioned
  decoder does not receive that input.

In the unconditioned decoder, what input does the decoder receive?

I was wondering the same and just stumbled across a nice tutorial by Quoc V. Le. The following explanation deals with the conditional case since this seems to be the common case. My explanation is based on and the image is taken from chapter 5 Sequence output prediction with Recurrent Neural Networks.

Background

We only regard a decoder with a single cell RNN which has:

W input to hidden weights
U hidden to hidden weights (ignore that first weight is different here)
V hidden to label weight

$$
f(x) = Vh_T \\
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ h_t = \sigma ( U h_{t-1} + W x_t ) ~~~ \text{for} ~ t = T, \dots, 1 \\
~~~~~~~~~~ h_0 = \sigma ( W x_0 )
$$

Since we are doing sequence prediction, we are not only interested in the last output of the RNN but rather the output at every timestep. Therefore the conditional decoder is designed to predict each label based on the previous ones, mathematically it splits the conditional probability in the following way:

$$
p(y|x) = \prod_{i=1}^n p(y_{i} | y_{i-1}, \dots, y_{1}, x)
$$

Like often done in machine learning, you can transform the probability to a score/energy/whatever which consists of a more convenient summation:

$$
\log p(y|x) = \sum_{i=1}^n \log p(y_{i} | y_{i-1}, \dots, y_{1}, x)
$$

The maximization of that score over our data is the objective. That can be equivalently formulated by the minimization of $ - \sum_{(x,y) \in D} \log p(y|x) $ where $D$ is our training set.

To complete this thought: When this probability is approximated we are actually interested in the argument $\theta_{min}$ of the minimization of $ - \sum_{(x,y) \in D} \log f(y|x,\theta) $ where $f(y|x,\theta)$ is our function approximator, e.g. a RNN, and $\theta$ the vector containing all weights $U$, $W$ and $V$.

During Training

During training we have the ground truth at hand so we can feed the decoder (see image) with the respective previous label at each timestep. At the first timestep we use the output of the encoder. Easy peasy.

During Inference

Here we obviously do not have the ground truth so instead we use the output of the previous timestep. This however poses another problem, since to find the sequence of maximum probability, we would have to compute every possible sequence and its probability according to probability function defined above.

Now, apparently one "greedy" approach is, to just ignore the above probability model and take the argmax's of each timestep.

Another more faithful approach is Beam Search which just heuristically looks at a subset of probable sequences and picks the one with maximum probability of them.

Things to note:

Inference is stopped, when the End-Of-Sequence symbol (<EOS>) is returned (greedy: when a timestep's argmax is <EOS>, beam search: the currently regarded sequence leads to <EOS>)
Both inference methods do not gurantee retrieving the sequence with maximum probability
The output of $f(x,\theta)$ needs to be a probability distribution at each timestep, so the final activation of the RNN is usually a softmax $f(x) = softmax(Vh_T)$

Unconditioned Case

I'd say based on the above explanation and the paper you referenced, that the unconditioned case does only get input at the first timestep of the decoder and then just "works with" the propagation of the hidden states. So the second equation of the RNN equations changes to $h_t = \sigma ( U h_{t-1} )$.

Then the outputs at each step would not be conditioned on the previous timestep's output, but rather be unconditioned. This way the modelled probability would become

$$
p(y|x) = \prod_{i=1}^n p(y_{i} | x)
$$

and the greedy inference strategy would become valid.


p constant in pumping lemma for regular languages We have a language

$L = \{ a^{n^{2}}, n < 12\}$ We have to find minimum constant P for pumping lemma.

What does p represent here? I thought p in pumping lemma represent number of states , yet the right answer is $p >= 122$ , i would understand if it was $p <= 122$.

So for example it would be correct when $p = 155$. But how could we create such automat with 155 states?

The key here is that $L$ is a finite language.  Therefore it can be recognized by a DFA which has no cycles - in this case, a chain of 122 states, numbered 1 through 122, with transitions on $a$ from each state $i$ to state $i+1$ [except for a loop on $a$ from state 122 to itself], with states 1, 4, 9, ..., 121 being final.  For P=122, this automaton satisfies the Pumping Lemma - i.e all strings in $L$ of length at least P can be pumped - in a purely vacuous sense, because there are no strings in $L$ of length at least P.


Continue on: Prove that $BPP^{BPP} = BPP$ regarding the following post: Prove that $BPP^{BPP} = BPP$

Let $L\in BPP^{BPP}$, by definition $BPP^{BPP} =\bigcup_{O\in BPP}BPP^O $, therefore there exists a language $A\in BPP$ such that $L\in BPP^{A}$.
This means that there exists a $\mathsf{PTM} $ $M^{A}(x,r)$ such that $\mathbb{P}_{r}(M(x,r)\neq L(x))\leq \frac{1}{3}$, and $M^A$ runs in polinomial time.
In addition, since $A\in BPP_{[\frac{1}{3},\frac{2}{3}]} \subset BPP_{[2^{-n},1-2^{-n}]}$, there exists a $\mathsf{PTM} $ $M'(x,r)$ such that $\mathbb{P}_{r}(M'(x,r)\neq L(x))\leq 2^{-n}$, and $M'$ runs in polinomial time.
I defiened a $\mathsf{PTM}$ $N$, that on input $x$ does the following:
Simulate $M^A$ on $x$ and every time we need to do an orcale quarey $\alpha_i$, we would simulate $M'$ on  $\alpha_i$ and the answer to the query would be the answer of $M'$.
I understand why $N$ runs in polynomial time, but I was stuck in the probabilistic analysis.
This is what I have so far:
If $x\in L$ then $N$ answer correctly iff $M^A$ answer correctly and $M'$ answer correctly about every query, therefore I got:
$\mathbb{P}_{r}(N(x,r)= 1)= \mathbb{P}_{r}(M(x,r)= 1)\mathbb{P}_{r}(\forall i, M'(\alpha_i,r)$is correct$)\geq \frac{2}{3} \prod_{i}(1-\frac{1}{2^{|\alpha_i|}}) $
How can I prove from here that $\mathbb{P}_{r}(N(x,r)= 1) \geq \frac{2}{3}$?
Would appreciate your help:)

Your BPP algorithm makes polynomially many queries to the BPP oracle, and assuming that all these queries are answered correctly, has error probability at most $1/3$, say.
In order to simulate this algorithm without appealing to the oracle, we replace each oracle call with the BPP algorithm itself. By repeating the BPP algorithm polynomially many times, we can reduce the error probability of each oracle call to $2^{-n}$, say. The union bound then implies that all oracle calls are answered correctly with probability $1-o(1)$, and so the entire algorithm has error probability at most $1/3+o(1)$, which suffices to put the language in BPP.


Backward vs Forward Data-flow Analysis I understand how both forward and backward data-flow analysis work but in what situations would we use them? Why do we need to be able to do it in both ways? Do compilers of certain types perform one way more efficiently than the other?

You can do different analysis with forward and backward flow algorithms:

Forward-analysis can provide information about some code to "future" code -- along the normal path of execution. A good example is constant propagation where you provide the value of variables to code further down the line.

Backward-analysis can provide information about some future properties "back in time". A good example is dead code elimination where you can remove assignments to variables if they will never be read in the future.

Real compilers like gcc or llvm perform both kind of analysis and there are even optimizations that require both kind of analysis simultaneously:

Partial redundancy elimination is one of those forward- and backward-analysis requiring algorithms: It tries to move code to the latest-necesary, earliest-possible place.


Show that if $NP\subseteq BPP$ then also $NP=RP$ - considerations about solution Show that if $$NP ⊆ BPP$$ then $$NP = RP$$

  Solution: It is enough to show that if $NP ⊆ BPP$ then $3SAT∈ RP$.
  Let $A$ be a $BPP$ algorithm for $3SAT$. Given a formula $ϕ$ with n variables,
  we first run $A$ on $ϕ$. If $A$ rejects, we reject. Otherwise, we try to
  construct a satisfying assignment for $ϕ$ one variable at a time. That
  is, we try instantiating $x_1$ to $0$, and then use $A$ to decide if the
  resulting formula is satisfiable: if so, then we permanently set $x_1$ to
  $0$ and proceed with $x_2$; otherwise we set $x_1$ to $1$ and proceed with $x_2$.
  If we manage to construct a satisfying assignment we accept, otherwise
  we reject, and so on. If $ϕ$ is unsatisfiable, then we always reject. If
  $ϕ$ is satisfiable, then we construct a satisfying assignment and accept
  provided that the $n + 1$ invocations of $A$ that we make are all correct.
  We can ensure that this happens with high probability by replacing
  each invocation of $A$ with $O(\log n)$ independent ones and taking the
  majority answer

It is fine solution from https://people.eecs.berkeley.edu/~luca/cs278-04/notes/sol.pdf

My only question is: Why $O(\log n)$ ? After all, we can run it polynomially to make error probablity exponetially small.

It's true that we can run $A$ even more times, but $O(\log n)$ times suffices for us to obtain a certainty of $1 - 1/(100n)$ (say) for each $x_i$. Applying the union bound, we deduce that the algorithm finds a valid truth assignment with probability at least $1 - 1/100$.

If you run $A$ polynomially many times then you get an exponentially small error, which is not needed here.


What is meant by interrupts in the context of operating systems? I've decided to read Operating Systems Concepts by Silberschatz, Galvin Gagne (8th edition) over the summer. I've gotten to a topic that's confusing me - interrupts and their role as it relates to operating systems.

The text says that an operating system will begin a first process such as "init" and then wait for an "event" to occur and this event is usually signaled by an interrupt. The text also says that the interrupt can come from either the hardware or the software. How does this work, in a little more detail? Is the operating system driven by interrupts?

I am just looking for some big picture understanding.

When the OS runs a process such as "init", it would have sent signals to other sub-systems/device managers etc, like the memory, I/O devices, etc. The interrupt is just a way of telling the processor or the OS that it is ready, or it has new input, etc. So sometime during init, the OS is waiting for sub-systems to be ready, and an interrupt from these sub-systems would indicate exactly that. So that is what the "event" relates to.

In regard to hardware or software interrupts, hardware interrupts are those which come from the hardware. Eg. I/O devices like keyboard, etc. A hardware interrupt causes the processor to save its state and begin execution of interrupt handler. On the other hand, software interrupts are instructions in the instruction set, which causes the processor to change its privilege level from user-supervisor, also known as context-switch. These details will be covered later on in the text book.


Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL? Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL OR CFL?
The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence I am not sure whether its DCFL or CFL.

Can you provide an explanation that shows $L$ is either DCFL or CFL?

i dont know how to use math,i searched for the solution but didn't got any,my DPDA is shown in picture below.

Your PDA isn't deterministic, as it has moves for $q_0, \epsilon, a$ and $q_0, b, a$.


Complexity of finding the largest $m$ numbers in an array of size $n$ What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ time. Any comments regarding the proof itself, or the style (i.e. my ideas may be clear but the presentation not).

The original question:

  Given $n$ numbers, find the largest $m \leq n$ among them in time $o(n \log n)$. You may not assume anything else about $m$.

My answer:

Sort the first $m$ elements of the array. This takes $O(1)$ time, as this is totally dependent on $m$, not $n$.
Store them in a linked list (maintaining the sorted order). This also takes $O(1)$ time, for the same reason as above.
For every other element in the array, test if it is greater than the least element of the linked list. This takes $O(n)$ time as $n$ comparisons must be done.
If the number is in fact greater, then delete the first element of the linked list (the lowest one) and insert the new number in the location that would keep the list in sorted order. This takes $O(1)$ time because it is bounded by a constant ($m$) above as the list does not grow.
Therefore, the total complexity for the algorithm is $O(n)$.

I am aware that using a red-black tree as opposed to linked list is more efficient in constant terms (as the constant upper bound is $O(m\cdot \log_2(m))$ as opposed to $m$ and the problem of keeping a pointer to the lowest element of the tree (to facilitate the comparisons) is eminently doable, it just didn't occur to me at the time.

What is my proof missing? Is there a more standard way of presenting it (even if it is incorrect)?

Here is an $O(n)$ algorithm solving the problem.

Use the worst-case $O(n)$ selection algorithm to determine the $n-m+1$-th order statistics. Let $k$ be this number, which is the smallest of the $m$ largest numbers we are trying to determine.
Now partition the array around the pivot $k$ using the QuickSort partition function. This step takes $O(n)$ too.
Output the $m$ largest numbers: these are given by $k$ and all of the numbers in the upper subarray generated by partition in step 2.


Sampling from the uniform distribution Is there an efficient classical algorithm that generates samples from the uniform distribution (or a distribution that is close to the uniform distribution in total variation distance), over the set $\{0, 1\}^{n}$, for a fixed $n$?
We can easily express the uniform distribution in terms of a formula:
$Pr(X = x) = \frac{1}{N}$, for each $x \in \{0, 1\}^{n}$ and $N = 2^{n}$.
My guess is that any distribution that can be expressed in terms of an explicit formula can be efficiently sampled from, but I can't find a concrete proof.

Sure, just sample $n$ bits, concatenate them, and output the result.


An Exact Method for Solving Small Instances of XORSAT I have a couple of small instances for XORSAT for which I am to design and implement an exact method. However, there are a few catches. It is guaranteed that there always exists and answer but I need to find the one solution with the minimal (non-zero) number of TRUE variables.

As I understand, XORSAT can apparently be solved in polynomial time through the Gaussian Elimination method but I simply cannot apply the special conditions of this problem (the minimal number of TRUE variables) and I'm wondering if I could potentially get some help on that.

The instances of XORSAT that I have are not completely random, they all consist of a number of variables that if XOR'd together will always yield FALSE. I.e., all of the clauses are in the form of $x_1 \oplus x_2 \oplus ... \oplus x_i = 0$ which would translate into the equation $x_1 + x_2 + ... + x_i = 0\space(mod 2)$.

At first, I tried to apply a greedy method, taking the two most repeated variables in all of the clauses and forcing the value TRUE on them, then propagating their values through all of the clauses and repeating the same method on the remaining unsatisfied clauses but that was fundamentally flawed.

Any help is tremendously appreciated.

I'll assume all of the equations take the form $x_i + \cdots + x_j = 0$ (i.e., always 0 on the right-hand side).  Then, your problem is: given a boolean matrix $M$, find a $x$ such that $Mx=0$ (modulo 2) that minimizes the Hamming weight of $x$.

I think this is equivalent to the problem of finding the minimum-weight codeword of a linear code.  That problem is NP-hard, and hard to approximate.  The equivalence: we think of $M$ as the parity-check matrix of a linear code; then $x$ is a codeword iff $Mx=0$, so your goal is to find a minimum-weight codeword. I encourage you to check my reasoning here.

There is a brute-force algorithm that runs in $O({n \choose w})$ time, where $n$ is the number of boolean variables and $w$ is the weight of the solution.  Assume that $w$ is known (in practice we can search over increasing values for $w$, as there aren't too many possibilities for it).  Then, you simply enumerate all ways to choose a subset of $w$ of the variables to set to true and check whether any of them work.

I think there is a meet-in-the-middle algorithm that takes exponential time but is faster than enumerating all possibilities.  The algorithm takes $O({n/2 \choose w/2} \sqrt{w})$ time and space, which is significantly better than the brute-force algorithm.  We'll write $x=u+v$, where $u$ is zero in its right $n/2$ bits and $v$ is zero in its left $n/2$ bits.  Then $Mx=0$ is equivalent to $Mu=Mv$.  We'll optimistically hope that $u$ has weight $w/2$ and $v$ has weight $w/2$; as I argue later, this happens with good probability.  So, we enumerate all ${n/2 \choose w/2}$ values of $u$ and store $Mu$ in a hashtable.  Then, for each of the ${n/2 \choose w/2}$ possible values of $v$, we compute $Mv$ and look it up in the hashtable.  If we find a match $Mu=Mv$, we've found solution $x=u+v$.  What's the success probability of this algorithm?  It is ${n/2 \choose w/2}^2 / {n \choose w} \approx \sqrt{2/(\pi w)}$.  Thus, if we repeat the algorithm about $\sqrt{\pi w/2} = O(\sqrt{w})$ times, with a different split of the $n$ coordinates into two equal-size subsets, we expect to find one solution.  Check my reasoning here -- this is from memory, so I can't vouch for this.

I believe there are algorithms in the literature that improve upon this scheme.  See, e.g., A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511 by Canteaut and Chabaud.  I think there has been more recent work but I'm not up to speed on it.


Are NP problems lower bounded by exponential order of growth? My understanding of P. vs NP is quite limited. I can understand P refers to an algorithm with an upper bound (big O) with order of growth $n^c$ for some constant c and variable n. My question is, do NP problems have a hypothesized lower bound order of growth (big Omega) of $c^n$ for deterministic machines? I can't find this stated anywhere and I'm trying to understand if this is something that is assumed or not.
Thanks.

First of all, every problem in P is in NP, and so we need to change your question to involve NP-complete problems rather than just NP problems.
The Exponential Time Hypothesis states that 3SAT requires exponential time $c^m$ for some constant $c > 1$, where $m$ is the number of variables. The Strong Exponential Time Hypothesis states that $k$SAT requires exponential time $c_k^m$, where $c_k \to 2$.
However, your conjecture is unconditionally false. Consider the language $L$ consisting of all pairs $\langle x,y \rangle$ such that $x$ is a 3SAT instance on $m$ variables (in particular, $m \leq |x|$), and $y = 0^{|x|^{100}}$. The language $L$ is clearly NP-complete, but it can be solved in time $2^m \mathit{poly}(n) = 2^{n^{1/100}} \mathit{poly}(n)$, where $n$ is the input size.
The Exponential Time Hypothesis does imply that every NP-complete problem requires time $c^{n^\alpha}$, for some $c>1$ and $\alpha>0$. This kind of running time is sometimes called subexponential time, but unfortunately this expression has several different interpretations, depending on context.


Crossover operator in genetic algorithms in Neural Networks I am developing a neural network that is trained using a genetic algorithm.
The neural network is a multilayer perceptron using $\tanh$ as its activation function. Currently, the genotype of the neural network is by its weights. I used the method of making a connectivity matrix and linearizing it according to this paper: http://sci2s.ugr.es/keel/pdf/keel/articulo/NN-Garcia05.pdf

What is a good crossover method for this? I've tried uniform crossover but it is too disruptive as there is no improvement whatsoever. Single-point crossover is discouraged as I have read, so what should I use?

I don't think you should.

But, supposing the structure is the same in all individuals, you could take a random set of nodes from one, and the rest from the other, and just keep all out edges from nodes you selected.

Another alternative is taking a random set of edges from one, and the rest from the other.

A third alternative is to take the first $\ell$ layers from the first individual and the last $L-\ell$ layers from the second individual.

As you can see, there are very many approaches, and I don't think any of them will be satisfactory, but I hope you try and see for yourself.


Encircling randomly distributed points I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will allow me to find the radii for the circles that cover as many points as possible, subject to the constraints that:

the radii are bounded (maximum radius $r_{max}$)
circles cannot intersect/overlap.

My approach so far was to compute a rank 3 tensor. Start from a definition: a point is denied by a circle, if the circle, by taking another point, causes that the point cannot be covered by any of the remaining circles without violating the constraints. The size of tha tensor is $C \times P \times P$, where $C$ is the number of circles, and $P$ is the number of points. I initialize it with zeros. I then check whether if circle c takes point p, point p' is denied, which I signify in the tensor by setting the appropriate value to 1.  From this data I'm trying to deduce whether it's worth trying to encircle a point, e.g. if a point is denied by many points, it probably means that it's a distant, isolated point, or that denying point form a cluster. I didn't manage to find a way that would allow me to make general any statements though.

Any ideas how to extend my approach / any suggestions to do it differently would be most welcome!

Okay, I think I have the solution to this one. It exploits the constraint (no overlaps) and the fact, that even a complex, multiple overlap problem, can actully be seen as a bunch of pairwise confilcts - at the end of the day no two circles can overlap.

Here is how it goes:
Find all points that can be covered by by a given circle and sotre these. Find the furthest point distance and set the radius of the circle to be that distance.
Now we probably have some overlaps. Create a priority queue and enter all the overlaping circles into the queue. The index of the queue is:

(distance from the furthest point) - (distance from the second furthest point).

Then we descrease the radius of the circle with the highest index so that now it's the distance to the second furthest point. Delete the circle from the queue, update the index and re-enter the circle into the queue if it still overlaps with any of the remainging circles. Keep repeating untill there is no more overlap in the system.

The solution is optimal, since the price for retracting the radius is constant (leaving out one point) and the gain is variable (and maximized by teh use of a priority queue).


Pumping lemma for a finite language Possible Duplicate:
  Pumping lemma for simple finite regular languages

The pumping lemma says that for any regular language $L$, there exists a constant $p$ such that any word $w$ in $L$ with length at least $p$ can be split into three substrings, $w = xyz$, where the middle portion $y$ must not be empty, such that the words $xz, xyz, xyyz, xyyyz, \ldots$ constructed by repeating $y$ an arbitrary number of times (including zero times) are still in $L$.

Consider a regular Language which contains only one string - the alphabet $a$. ie, $L = \{a\}$.

Now, in this $L$, what would be the value of $p$, and possible values of $x$, $y$ , $z$?

I am confused to the boundary cases of the pumping lemma.

The short answer is that for any finite language $p$ is greater than the length of every string in the language - i.e. finite languages are a trivial case as it's true that every string longer than $p$ can be pumped.

Beyond the question you asked, understanding what the pumping length is can help with stuff that you might do later. A very brief sketch of the proof of the lemma is that given a regular language, there's some DFA that accepts it. We can can take $p$ to be the number of states in that DFA.

Then if there are no loops in the DFA, we have a finite language an every string has length strictly less than $p$ (it can't have passed through the same state twice), this is the case in the question.

If there are loops (i.e. the language is infinite) then there can be strings of length greater than $p$, but this means that they have to have repeated some states (by going around the loop), and that it has to have done this loop in the first $p$ characters (otherwise we have too many characters for the number of states). This loop is the $y$ section of the string, obviously we can go around the loop as much as we want (even zero times), and this is the pumping part.

Obviously this is quite informal, but you should be able to glean the essential parts that give the conditions of the pumping lemma.


Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm? Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number of nodes or vertices. The Dijkstra's algorithm has a complexity of O((|V| + |E|) * log(|V|)) where E is the number of edges. Compared to A star, the Dijkstra's does not rely on properties of any heuristic which makes them popular. But I am trying to understand the advantage of Dijkstra's over Grassfire. Are there practical reasons why this is the case? Or am I simply seeing more cases of Dijkstra's compared to Grassfire due to the application areas such as navigation that I am working on?

In grassfire the distances are constant. All of your neighbors have equal length. In a weighted graph, grassfire will fail.

Graphfire is actually based on a small modification of BFS.

The Dijsktra works on weighted graphs, too.

Note: If all costs are equal, Dijkstra = BFS

Know the difference, and use them according to your need.


Find multiple duplicates in $n$ size data set in linear time Problem:

  Given a vectors of size $n$ with integer data within $[1, n-1]$ range, find $if$ and $which$ numbers are multiple duplicates (numbers appearing more than once). The time complexity ought to be linear and space complexity constant (don't use any auxiliary data structure except the input vector and variables) and the input data set ought not to be modified.

I'm trying to solve this problem for at least one multiple duplicate (as a starting point, although I don't know if the solution to this case can be expanded to the general case of at least two multiple duplicates). Here's what I've done so far:

The $if$ part is relatively easy, taken we can be proven using the pigeonhole principle to show that there $will$ be at least a simple duplicate within the given data set.

The $which$ part, on the other hand, is what gives me headaches. Unlike  the missing number problem, we cannot simply Xor the numbers. Neither can we sum them up and subtract the sum from 1 to n-1, thus finding a simple duplicate. Can anyone suggest a good approach towards this problem?  You are not allowed to modify the input array.

This can't be done in constant space.

Let's think first about algorithms  that read the entire input array before producing any output.  Note that there are exponentially many possible outputs.  In particular, the output might include up to $n/2$ different numbers that are "multiple duplicates".  Thus, there are at least ${n-1 \choose n/2}$ different possible outputs, and ${n-1 \choose n/2}$ is $\Theta(2^n/\sqrt{n})$.  Now the state of the algorithm (the values of all variables, etc.) before producing output must uniquely determine the output, so that means there must be at least ${n-1 \choose n/2}$ possible states.  It requires $\lg {n-1 \choose n/2}$ bits to store that state.  It follows that any algorithm that reads all input before producing all output must use at least $\lg {n-1 \choose n/2}$ bits of space; and this is $\Theta(n)$.  So any such algorithm must use linear space.

What about algorithms that might produce output as they go?  It's still not possible in constant space; such algorithms still need linear space.  Consider an input where the first half of the array has no duplicates, and think about the intermediate state of the algorithm at that point.  That state must contain enough information to deduce the set of numbers in the first half of the input array (if two such input arrays that differ in their first half produce the same state at this point, then we can construct a way to fill in the second half so that the algorithm is wrong for at least one of those -- just pick a number that appears in the first half of one of those inputs but not the other, and make sure it appears exactly once in the second half).  It follows that there must be at least ${n-1 \choose n/2}$ possible states after reading the first half of the input array.  As before, it then follows that the algorithm needs $\Theta(n)$ bits of space.  So producing output as you go doesn't help -- it still can't be done in constant space.


Decimal to Fixed Point Conversion I am having trouble to get the intuition behind the following approach:
We take the fraction point (say: .642) and continuously multiply by 2,
taking whatever ends up right of the point as our next number (either 0 or 1) after the fixed point in the binary number. Then we take whatever is left after the decimal point and repeat.

Let $x$ be the real number you wish to convert. We will assume without loss of generality that $0 \le x < 1$. Form the Dedekind-completeness of the order on $\mathbb{R}$, it follows that $x$ can be (almost) uniquely written as

$$
x = \sum_{h=1}^{\infty} 2^{-h} \alpha_h
$$

where $a_h \in \{ 0, 1\}$ for all $h$. Now observe that:

$$
2x = \sum_{h=1}^{\infty} 2^{-h+1} \alpha_h = \alpha_1 +\sum_{h=1}^{\infty} 2^{-h} \alpha_{h+1}
$$

where the rightmost sum is nonnegative and less than $1$. Multiplying by $2$, therefore, allowed us to discover a single binary digit of $x$, namely $\alpha_1$. The same procedure can be iterated to yield as many digits as you wish.


Are the definitions of loop in CS and in programming (standard/common) identical? Are the definitions of loop in CS and in programming (standard/common) identical?
If not, what is the main difference / what are the main differences?

In Mathematics and computer science, looping is generally associated with either some repetitive work, or with accumulated summation (bitwise, or higher logic operations).
Looping is more of an abstract view of iteration, in, say, programming - where it is very specific and depends on the language and associated compiler with programming point of view.

Sidenote: it is also a convenient way of writing programs to have loops rather than call some functions multiple times which is not good practice.


Fine-grained versioning of entities in programming languages I have a question related to design, implementation of programming languages. I hope it fits here and apologize if it doesn't.
All or most programming languages version modules (aka packages, libraries, crates). All the entities in a module (types, functions, variables and other information) share the same version with the module. However usually only some parts of a module change between a version and the next.
When two different modules use different versions of the same third module, this creates an incompatibility.

Some programming languages (for instance C and C++) ignore the problem altogether. They don't care about the version but only about the name and signature of entities. They accept programs that may crash or misbehave when executed, if different pieces of such programs expected different versions of a same entity that changed.

Other programming languages (for instance Rust or Node.js) trait different versions of the same entity as two completely different entities. This avoid crashes, but introduces unnecessary incompatibilities between entities that did not change.

This can be a big problem for modules that define many different entities and that lots of other modules depend on, for instance the standard library of a programming language. Most programming languages use special tricks for their standard libraries: for instance they tie the standard library's version to the compiler version and require to recompile everything when the compiler version changes.
A better solution to this problem could be versioning every entity independently instead of whole modules. The GNU implementation of the standard library of C and C++ do this. I have seen some Rust crates do this too by importing their previous version and re-exposing all the symbols that didn't change. But these processes are very tedious and easy to get wrong, hence very few pieces of software adopt similar practices.
Do we know of any good way to version entities in a fine-grained way?
Has there been any research on this problem?
A practical example
If the problem I described isn't clear, let me explain it with a practical example.
A module "time 1.0.0" defines loads of entities related to time. Among many others, it defines these two types:
type UnixTime   = uint32_t; # seconds from 1970 Jan 1
type UnixTimeNS = uint32_t; # nanoseconds from 1970 Jan 1

After "time 1.0.0" is out, we realize that UnixTimeNS is too small: it needs to be an uint64_t. We change that type and release "time 2.0.0" since we did an incompatible API change. Nothing else changed in the whole "time" module besides that UnixTimeNS type.
Two other modules "logger" and "totp" depend on "time". The former was developed on "time 1.0.0", while the latter uses "time 2.0.0". They both only use time::UnixTime and nothing else. This type did not change between the two version. But the compiler can't know that and treats time_1.0.0::UnixTime and time_2.0.0::UnixTime as different, incompatible types. It's now very hard to use both "logger" and "totp".
Imagine if they make a similar change to the standard library of any existing language: it could result in a tremendous split between new and existing modules, something as catastrophic as the switch from Python 2 to Python 3. All for a very minor change that affects 0.1% of the existing code.
I developed a rust crate (https://github.com/BlueNebulaDev/rust-version-test) and a Node.js package (https://github.com/BlueNebulaDev/node-version-test/) to show this problem in action. The names used in these projects differ from the ones in the example described here, but the meaning is the same.

The Unison programming language is based around two simple fundamental ideas:

code is immutable
code is content-addressed

What does that mean? Code being immutable means just what it sounds like: since code is immutable, it will never change. You can only ever add new code to the system, but you can never change or remove existing code.
Code being content-addressed means that all addresses (references) are based on the content of the code, not any names. And computing the content address is invariant under α-conversion by using De Bruijn indices in the code database.
This has some interesting implications: since you only reference functions, types, modules, variables, etc. by their content address and the content address is based on a name-less representation, you can rename anything and everything to your heart's desire, and never break any code. Also, since all references are based on content, and content never changes (remember, code is immutable), code that works at one time, will always continue to work until all eternity.
This poses an interesting question, though: How do you fix bugs?
One part of the puzzle is how names are handled in Unison. I wrote above that Unison's code model is based on addresses, but that doesn't mean that there are no names at all. It would be very annoying to write code like
#1uekd4 = #lle0xy #5q17cp #h8i067

instead of
fullName = concat firstName lastName

and having to remember all the addresses.
Instead, Unison also stores a mapping of names to addresses in its code database. This is similar to how Unix filesystems work: in a Unix filesystem, a file has no name, it only has a file serial number. However, there are directories (which are also files) which map names to serial numbers (which could point to regular files or to another directory). Also, Git works in a similar fashion. There are blobs, which only have content, and there are trees which assign names to addresses (which could be blobs or trees).
If you want to fix a bug, then you create a new version of the buggy function which doesn't have the bug. But all existing code still references the old function! (Remember, all addressing is based on content, not names.) So, you have to update every function that references the old function. And you have to update every function that references a function that references the old function.
Obviously, this gets tedious really fast. This is where names come in. After updating the function (really creating a new function), you also update the name database (really creating a new database) with a version where the name now points to the new, fixed, function.
Unison will notice this update, and will automatically propagate this name change through all existing functions. So, it will automatically update all functions that reference the buggy function to now reference the fixed function, then it will update the functions which reference the functions it just updated, and so on.
Where "automatically propagate" can mean one of two things:

If the new function has the same type as the old one, Unison will automatically apply the update.
If the new function has an incompatible type, Unison will create a to-do list with all the places that need to be changed.

Once the change is made, regardless of whether it was done aumatically or it required manual intervention, this change is recorded in a patch and becomes part of the code database as well. So, anybody else who pulls in the changes will benefit from the fact that you already resolved the issue and they can pull in the patch as well.
Bringing this to your example: since the content of time::UnixTime hasn't changed, it still has the same address, and since code is immutable, it is guaranteed that this address will refer to this type for all eternity. And since both logger and totp only refer to it by its address, which will never change, they, too, will continue to work unchanged for all eternity.


The time complexity for finding the kth smallest number in a min-heap Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap?

I thought that we can remove the root element for k times and each time we apply heapify? So it should be $O(k \log n)$ but the answer is $O (k \log k)$. What did I do wrong?

There is an $O(k)$ algorithm [1].

[1] Frederickson, G. N. (1993). An optimal algorithm for selection in a min-heap. Information and Computation, 104(2), 197-214.


How does left-factoring prevent backtracking? I read that deterministic grammar helps in preventing backtracking.

Consider a grammar

$$A \rightarrow ab \mid ac \mid ad$$.

Here if input is "ad" then the compiler needs to check each of ab, ac .. and backtrack until it gets to last production.

To eliminate non determinism we modify the grammar as

$$A \rightarrow aB$$
$$B\rightarrow b\mid c\mid d$$

I don't understand how will this modified grammar prevent backtracking . If we again give the same input "ad" then in B production , it will again back track for b and c until it reaches d.

So how does left factoring actually solve this problem ?

Suppose the input is ab. In compiler terms you have two tokens a and b which are read in linear sequence. So, when you read a it is not clear which production rule to apply since you have three possible rules which begin with a: $A \rightarrow ab \mid ac \mid ad$. To choose the right production rule you need check all possible rules which is done by backtracking.

However, if you factor this grammar  then you have only one production rule which begins with a: $A \rightarrow aB$ which is the only single possible rule and thus there is no need in backtracking.

Nondeterminism, when parsing, can be resolved using lookahead technique, where left-factoring is one of the steps in order to transform the initial grammar into $LL(k)$-grammar.  For more details please read about $LL(k)$-parsers.


Is there a faster algorithm for my graph problem? I'm working on a tool that can analyze sizes of individual functions in a compiled binary. For each one it calculates how much space would be saved if the function was removed.

However, the current algorithm is quadratic in the number of functions and as such is quite slow. Is there a better one? The problem formulation follows.

Let $G=(V, E)$ be a directed graph with labeling $f\colon V\to\mathbb{N}$, and $R\subseteq V$ be a set of root vertices. Here, $V$ represents the functions in the binary. The graph edges represent the dependencies between the functions: $(u, v)\in E$ iff $u$ references $v$, thus forcing $v$ to be present in the binary. $f$ assigns to each function its size in bytes. Functions in $R$ (the main function in the executable or the set of exported functions in an .so) are the functions we want in the binary, the rest of them were pulled in directly or indirectly from $R$.

For a set of vertices $U\subseteq V$ and edges $F\subseteq E$, we define $r(U, F)$ as the set of vertices reachable from $U$ along the edged from $F$.

$$r(U, F)=\{v\in V\mid \exists r\in U. (r, v)\in F^*\}$$

We guarantee that $r(R, E)=V$, that is all vertices are reachable from $R$ in the original graph (not that it helps).

We define $s(U) = \sum_{u\in U} f(u)$ as the total size of all functions from $U$.

For each $u\in V$, let $E_u\subseteq E$ be the restriction of $E$ in which all edges adjacent to $u$ are removed. Then $r(R\setminus\{u\}, E_u)$ is the set of functions that will be present in the binary if we remove $u$. Note that other functions besides $u$ may disappear as they will no longer be reachable from $R$.

Our goal is to compute for each $u\in V$ the size of the binary after removing $u$, i.e. to compute $g\colon V\rightarrow\mathbb{N}$ at all points, where

$$g(u)=s(r(R\setminus\{u\}, E_u))$$

I can easily compute $g(u)$ in $O(|V|+|E|)$ with a simple depth-first-search. Computing the entire $g$ thus yields $O(|V|(|V| + |E|))$. Is there a faster algorithm?

In practice, just as you can calculate g (u) for one particular u quite quickly, you can calculate g (u) for all $u \in V$ in parallel, operating with bit vectors of $|V|$ bits instead of boolean values - this changes the number of operations only be a constant, but by a rather large constant. This is quite useful if you actually want the number of bytes saved for every u.

If you are only interested in one u, then you only want to know for each function: 1. Can it be reached from u? 2. Can it be reached from any function other than u? To decide that, just combine all the other functions in V into one single function which calls everything that any of these functions calls. You don't need to know all the individual call graphs, just what can be reached from any of the functions in V other than u.

Second comment: I thought that you wanted to know how many bytes are saved by removing one function. That took you O (|V| * (|V| + |U|) by calculating all g (u). Which looks quite bad and can be improved if you want to know the answer for one function. If you want to answer the question for all functions, then calculating all g (u) is fine. It still takes O (|V| * (|V| + |U|), but the work can be reused for every function.

That's a very common situation, where solving n problems can be done a lot quicker than n times solving one problem.


Travelling Salesman Problem with Memoization I coded a solution for the famous Travelling Salesman Problem but my code does not work properly, although it seems okay.

In a grid of size m x n, you are allowed to move only down/right, and
you need to go from the top-left corner to the bottom-right corner.
Each sell has a reward value. How much is the maximum reward you can
collect?

def travellingSalesman(m, n, rewards, memo={}):

  if m == 0 or n == 0:    return 0
  if (m, n) in memo:      return memo[(m, n)]
  if (n, m) in memo:      return memo[(n, m)]

  # Base case
  if m == 1 and n == 1:   return rewards[0][0]

  # maximum rewarding one of the grids m-1 x n - m x n-1 plus reward of the current cell
  memo[(m, n)] = max(travellingSalesman(m-1, n, rewards, memo), travellingSalesman(m, n-1, rewards, memo)) + rewards[m-1][n-1]

  return memo[(m, n)]

if __name__ == '__main__':
  print(travellingSalesman(m=3, n=3, rewards=[[0,4,2],
                                              [3,2,0],
                                              [4,1,0]]))

The function below returns 6, but it should return 8 with the path: 0-> 3 -> 4 -> 1 -> 0
Can you enlighten me about the problematic/missing part of this code? Thanks!

In the 3rd if statement your code assumes that the optimal solution when starting from coordinates $(m, n)$ is equal to the optimal solution when starting from coordinates $(n, m)$. This is clearly false in general.


What happens during the DFA reversal construction if the initial state is final? The steps in reversal of DFA are :-

Make final state as initial state. If there are more than 1 final state, then make a new start state with epsilon transitions to these states.
Change all initial states to final states
Reverse the direction of edges.

Now what if I have a state which is both initial and final ? Will it be initial or final state in the reversed dfa?

Yes.  It will be both initial and final in the reversed automaton.

(Separately: If you want the reversed automaton to be a DFA, you may have to be a bit careful about your construction for reversing a DFA, as DFAs are not allowed to contain epsilon transitions.)


Formal grammar with variables for consistent substitutions In a rewriting system, suppose the production rule S→xAyAz (or <S>:=xyz, in BNF), where S and A are nonterminal symbols and x, y, z are any string.

This rule produces the string xa1ya2z, where a1 and a2 are strings substituted by the nonterminal symbol A. The substitutions a1 and a2 may be equal or different strings.

But what if I want to a1 and a2 to be the same string; that is, if the nonterminal A be substituted by the same instance in both its occurrences in that production rule?

I used a kind of BNF I created informally for such purpose, with <v:A> instead of : a kind of "typed variable", whose type is a nonterminal symbol and the variable is the same substitution for all its occurrences. Thus, <S>:=x<v:A>y<v:A>z, and <v:A> is substituted for the same string in its both occurrences.

What is the name of such a grammar that uses variables for consistent substitution of a nonterminal? And there is a grammar formalism for it?

You've created an affix grammar, so named because they were created to deal with affixes (prefixes and suffixes) in natural languages.

Specifically, this is a type of affix grammar where the "affixes" (what you call typed variables) are defined by the same type of grammar rather than coming from a simpler (finite) grammar. This creates a two-level grammar, specifically a type known as a Van Wijngaarden grammar after its creator.

It turns out that this type of grammar is in fact Turing-complete, so non-trivial semantic properties of such grammars are undecidable by Rice's theorem. On the one hand this makes them extremely powerful; on the other hand, it makes them not as useful in practice, since you could use some other Turing-complete system instead.


How do I describe formally complexity of 2-sum problem algorithm? I have algorithm that finds if there are two elements in sorted array that have sum zero.

1.ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2.    l <- 1, r <- n
3.    while(l < r)
4.        while(l < r or A[l] + A[r] > 0)
5.            r--
6.        if(A[l] + A[r] = 0)
7.            return true
8.        l++
9.    return false

Intuitively I know that this algorithm is $O(n)$, but how do I deduct it using proof with summations like in CLRS book?

I've also saw How to develop an $O(N)$ algorithm solve the 2-sum problem?, but I didn't see any formal proof.

Consider this slightly modified algorithm where I've added an "operation counter" t. This will be incremented every time we do a comparison or assignment.

1. ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2.   l <- 1, r <- n
3.   t <- 3             // 2 for first two assignments and 1 for initial while check
4.   while(l < r)
5.     t++              // 1 for initial while check
6.     while(l < r or A[l] + A[r] > 0)
7.       t++            // 1 for decrementing r
8.       r--
9.       t++            // 1 for following while check
10.    t++              // 1 for if comparison
11.    if(A[l] + A[r] = 0)
12.      return true
13.    t++              // 1 for incrementing l
14.    l++
15.    t++              // 1 for following while check
16.  return false

This is a bit verbose, but it will work. Now we must simply prove that, at termination we have $t = O(n)$. We can do this inductively with a loop invariant.

Let's use the following loop invariant for the loop on line 4.

$$t = 3 + 4(l-1) + 2(n-r)$$

Base Case

Initially $t = 3$, $l = 1$, and $r = n$. Thus we have:

$$3 = 3 + 4(1 - 1) + 2(n - n) = 3$$

Inductive Case

Let $t'$, $l'$, and $r'$ be the values of $t$, $l$, and $r$ at the end of our previous iteration. At the end of our current iteration we have $l = l' + 1$, $r = r' - k$ for some $k$, and $t = t' + 4 + 2k$. Thus we have:

$$\begin{align*}
t & = t' + 4 + 2k\\
  & = 3 + 4(l' - 1) + 2(n - r') + 4 + 2k\\
  & = 3 + 4(l - 2) + 2(n - (r + k)) + 4 + 2k\\
  & = 3 + 4(l - 1) - 4 + 2(n - r) - 2k + 4 + 2k\\
  & = 3 + 4(l - 1) + 2(n - r) & \square
\end{align*}$$

Thus, we can conclude the loop invariant holds. At the end of the loop (in the worst case) we have $l = r \leq n$. We then have:
$$\begin{align*}
t & = 3 + 4(l - 1) + 2(n - r)\\
  & = 3 + 4l - 4 + 2n - 2l\\
  & = 2(n + l) - 1\\
  & \leq 2(n + n) - 1\\
  & = 4n - 1\\
  & = O(n) & \square
\end{align*}$$

Thus it is linear. There might be an easier way to do this, but this way makes sense to me pretty clearly.


How are boolean circuits used for solving P vs NP? In the paper https://web.stanford.edu/~gavish/documents/sipser-pvsnp.pdf , it is mentioned under the Status section that boolean circuits have been used to try and solve P vs NP. Can anyone explain to me in simple terms how boolean circuits are used for solving P vs NP?

First, let me start by explaining what Boolean circuits are. You are probably familiar with Boolean formulas — these are formulas of the sort $(a \land b) \lor (\lnot a \land \lnot b)$. We can represent each formula as a tree. In our example, the root of the tree will be labeled $\lor$, and its two children are the trees corresponding to $a \land b$ and $\lnot a \land \lnot b$. More generally, there are four types of nodes: nodes labeled $\lor$ or $\land$ have exactly two children, nodes labeled $\lnot$ have exactly one child, and the rest of the nodes are labeled by input variables. We can think of the edges as directed towards the root.

Boolean circuits generalize Boolean formulas by allowing arbitrary directed acyclic graphs instead of directed trees. In the example above, we can, for example, identify the two nodes labeled $a$ and the two nodes labeled $b$. Alternatively, we can identify Boolean circuits with straightline programs. These are programs which use the following instructions:

$x \gets y \lor z$.
$x \gets y \land z$.
$x \gets \lnot y$.

For example, the formula above corresponds to the straightline program

$x \gets a \land b$.
$y \gets \lnot a$.
$z \gets \lnot b$.
$w \gets y \land z$.
$o \gets x \lor w$.

The value of the formula is the value of the last assignment. Notice that every variable other than the inputs is used exactly once. Straightline programs with this constraint correspond to formulas. If we remove the constraint, the we get circuits.

The $\mathsf{P} \neq \mathsf{NP}$ conjecture can be stated equivalently as follows:

  SAT has no polynomial time algorithm.

It turns out that the following conjecture (known as $\mathsf{P/poly} \neq \mathsf{NP}$) implies $\mathsf{P} \neq \mathsf{NP}$:

  SAT has no polynomial size circuits.

What does this mean? We can encode CNFs as strings of bits (for example, encode them first in ASCII, and then unfold the ASCII into bits). Let $SAT_n$ be the collection of satisfiable CNFs of length $n$ bits. A circuit for $SAT_n$ is a circuit on $n$ inputs $x_1,\ldots,x_n$ which returns True if and only if $x_1\ldots x_n \in SAT_n$, i.e., the CNF corresponding to $x_1\ldots x_n$ is satisfiable. We say that a collection of circuits $C_1,C_2,\ldots$ solves SAT if $C_n$ is a circuit for $SAT_n$. The collection has polynomial size if there exists a polynomial $P(n)$ such that the size of $C_n$ is at most $P(n)$ (the size of a circuit is the number of nodes in its graphical representation).

Why does this imply that SAT has no polynomial time algorithms? The reason is (essentially) the Cook–Levin theorem. This theorem shows that if SAT has a polynomial time algorithm then it also has polynomial size circuits. There is nothing special about SAT here — this reduction works for every problem. The theorem shows how to encode the computation of a Turing machine running in polynomial time as a polynomial size circuit.

Unfortunately, we are very far from realizing this program. We only know how to show that polynomial size circuits cannot solve certain problems in the following circumstances:

When the circuit is shallow, that is, has small depth.
When the circuit doesn’t use $\lnot$ gates at all.
For non-explicit problems: by counting the number of polynomial size circuits (for any fixed polynomial), you can show that there must be some functions that they cannot compute.

There is some further progress which throws diagonalization into the mix, but that’s about it. It seems that this approach is stuck, and different lines of attack are required to solve this important problem.


Subtracting binaries using two's complement I am trying to subtract these two binary numbers:

$  1110
- 1011$

First I convert 1011 to two's complement by doing 1011 to 0100 and then adding 1 to get 0101. Then I add the first number to the converted two's complement number:

$1110$

$+$ $0101$

$-----$

$0011$

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 carry 1

carry 1 + 1 + 0 = 0

For a final answer of $0011$ which is 3 in decimal, however, the answer in my book says it should be 2 or 0010...?

Your book is wrong and what you are doing is correct.

1110 is 14 in decimal and 1011 is 11 in decimal. Hence the answer should be 3 i.e. 0011


How many rotations after AVL insertion and deletion Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?

How many rotations, does deletion from AVL require?

I've searched for these two questions with no luck so far.

The obvious resource, Wikipedia, I did not find  very helpful.

When inserting an element at most one (single or double) rotation is needed, at the lowest point where the tree is out of balance. After rotation the height of that subtree is the same as in the original subtree, so all nodes upwards are balanced.
See the answer by colleague Raphael to "Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?"

When deleting occurs, one is not always that lucky. Rotation does not necessarily restore the original tree height, so the tree has to be updated at other levels higher up in the tree. Worst case trees are those which are minimal AVL trees, meaning with no node can be removed without violating the AVL property. There you might have to rotate every level, thus a logarithmic number of times.


Analysis of Universal Hashing I was reading universal Hashing from Introduction to Algorithms by Cormen et al., and came across the following corollary regarding search, insert and delete functions on Universally Hashed tables:

  Corollary 11.4

  Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(n)$ to handle any sequence of $n$ Insert, Search, and Delete operations containing $O(m)$ Insert operations.

  Proof Since the number of insertions is $O(m)$, we have $n = O(m)$ and so $\alpha = O(1)$. The Insert and Delete operations take constant time and, by Theorem 11.3, the expected time for each Search operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of  $n$ operations is $O(n)$. Since each operation takes $\Omega(1)$ time, the $\Theta(n)$ bound follows. $\quad\blacksquare$

How is the author able to say that $n = O(m)$, in the first line of the proof?
Also, what does $n=O(m)$ mean? Because $n$ is a variable and $m$ is a constant, therefore the statement seems wrong.
Also, if $n=O(m)$ is true, then obviously $n=\Omega(m)$ is true, thus yielding $n=\Theta(m)$.

The statement of the corollary is extremely sloppy. Here is a correct statement and proof.

  Corollary 11.4

  Fix $c < 1$. Using universal hashing and collision resolution by chaining in an initially empty table with $m$ slots, it takes expected time $\Theta(N)$ to handle any sequence of $N$ Insert, Search, and Delete operations containing at most $cm$ Insert operations.

  Proof Since the number of insertions is at most $cm$, we have $n \leq cm$, where $n$ is the number of elements in the table, and so the load factor satisfies $\alpha \leq c$. The Insert and Delete operations take constant time and, by Theorem 11.3, the expected time for each Search operation is $O(1)$. By linearity of expectation, therefore, the expected time for the entire sequence of  $N$ operations is $O(N)$. Since each operation takes $\Omega(1)$ time, the $\Theta(N)$ bound follows. $\quad\blacksquare$

Roughly speaking, there are two problems with the book version:

The variable $n$ is used both for the number of elements in the table and for the number of operations.
The number of Insert operations should be $O(m)$, with a hidden constant bounded away from $1$.


Is the language given by a context-free grammar always context-free? Consider the language generated by the following grammar:

$S \to aSBb \mid \epsilon$

$B \to aB \mid bB \mid \epsilon$

Is the above language context-free?

The above language looks like $\{ w \in (a+b)^* : a^n w_1b w_2b ... w_nb \}$.

I tried using the pumping lemma to show that this language is not context-free, but I was unable to do so.

Hint: A language $L$ is context-free iff there exists a context-free grammar $G$ such that $L = L(G)$. (Some people take this as the definition of context-free languages.)


Center of a Cycle and Complete graph The center of a graph is the set of vertices with minimum eccentricity, so a $C_n$ have the minimum eccentricity equals to $n$ and a $K_n$ have the minimum eccentricity equals to $1$? Is valid that a center of a graph be the graph itself?

Let $G = (V, E)$ be a graph. If the eccentricity of each vertex $v \in V$ is $c$. Then the center of the graph is $V$, the set of all vertices of the graph $G$. Note that the center is the set $V$ of vertices not the graph $G$. In general the center of a graph $G = (V, E)$ is a subset of $V$.


Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.

Create pushdown automation for
{w: #a(w) >= 2#b(w)}; and simulate it for the word ababaaa

# means number

Does any one of you is fluent enought in automation to solve it?

General strategy:

What you want to do is every time you read an input symbol a, if the stack has a b on it delete the b, and if the stack is empty/has a's, add an a. Every time you read a b, if the stack is empty/has b's add bb, if the stack has one a, remove the a and add a b, and if the stack has two or more a's, delete two of them. You're in an accepting state as long as the stack has no b's on it.

You can implement this strategy if you use epsilon transitions and intermediate states in a fairly straightforward way.


What are the conditions for a NFA for its equivalent DFA to be maximal in size? We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in worst case gives us $2^S$ states, if our NFA had $S$ states.

My question is: what is determining the worst case scenario?

Here's a transcription of an algorithm in case of ambiguity:

Let $A = (Q,\Sigma,\delta,q_0,F)$ be a NFA. We construct a DFA $A' = (Q',\Sigma,\delta',q'_0,F')$ where

$Q' = \mathcal{P}(Q)$,
$F' = \{S \in Q' | F \cap S \neq \emptyset \}$,
$\delta'(S,a) =\bigcup_{s \in S} (\delta(s,a) \cup \hat \delta(s,\varepsilon))$, and
$q'_0 = \{q_0\} \cup \hat \delta(q_0, \varepsilon)$,

where $\hat\delta$ is the extended transition function of $A$.

The algorithm you refer to is called the Powerset Construction, and was first published by Michael Rabin and Dana Scott in 1959.

To answer your question as stated in the title, there is no maximal DFA for a regular language, since you can always take a DFA and add as many states as you want with transitions between them, but with no transitions between one of the original states and one of the new ones. Thus, the new states will not be reachable from the initial state $q_0$, so the language accepted by the automaton will not change (since $\hat\delta(q_0,w)$ will remain the same for all $w\in\Sigma^*$).

That said, it is clear that there can be no conditions on a NFA for its equivalent DFA to be maximal, since there is no unique equivalent DFA. In contrast, the minimal DFA is unique up to isomorphism.

A canonical example of a language accepted by a NFA with $n+1$ states with equivalent DFA of $2^n$ states is
$$L=\{w\in\{0,1\}^*:|w|\geq n\text{ and the \(n\)-th symbol from the last one is 1}\}.$$
A NFA for $L$ is $A=\langle Q,\{0,1\},\delta,q_0,\{q_{n+1}\}\rangle$, with $\delta(q_0,0)=\{q_0\}$, $\delta(q_0,1)=\{q_0,q_1\}$ and $\delta(q_i,0)=\delta(q_i,1)=\{q_{i+1}\}$ for $i\in\{1,\ldots,n\}$. The DFA resulting of applying the powerset construction to this NFA will have $2^n$ states, because you need to represent all $2^n$ words of length $n$ as suffixes of a word in $L$.


Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set? Given a set of 10 integers $A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is NOT divisible by any member of this set.

I understand the Inclusion-Exclusion principle can be used to solve this problem but I can't figure out how to implement it so that it works efficiently.

Note: When I say "efficient", I mean polynomial time, yet I am not entirely sure what qualifies as polynomial time is this case as both variables are fixed.

Let $\mathbf x$ be a random number in the range $1,\ldots,N$, and let $E_i$ denote the event that $\mathbf x$ is divisible by $a_i$. You are interested in the probability that none of the events $E_1,\ldots,E_m$ happen (in your case, $m = 10$). Using the inclusion-exclusion principle, this reduces to computing the probability of the events of the form $E_{i_1} \land \cdots \land E_{i_k}$, that is, $\mathbf x$ is divisible by all of $a_{i_1},\ldots,a_{i_k}$. Since a $\mathbf x$ is divisible by a bunch of numbers iff it is divisible by their LCM, it suffices to determine the probability that $\mathbf x$ is divisible by $a$.

Among $1,\ldots,N$, the numbers divisible by $a$ are
$$
a,2a,3a,\ldots,\lfloor N/a \rfloor a,
$$
in total $\lfloor N/a \rfloor$ numbers. Hence the probability that $\mathbf x$ is divisible by $a$ is exactly
$$
\frac{\lfloor N/a \rfloor}{N}.
$$


Approximation algorithm for the partition problem In the partition problem we want to partition a set $S$ of positive integers into two sets $S_{1}$ and $S_{2}$ such that the sum of the integers in the two sets is the same.

The optimization version of the problem is NP-Hard, in the following wikipedia page an 7/6 approximation algorithm is described. In that algorithm, we sort the original set $S$, traverse the new sorted set in descending order and send each element to the set $S_{i}, i\in\{1,2\}$ that has the minimum total sum at the given moment.

My question is, does the traversal have to be in descending order? If we do it in ascending, does anything change in the final approximation ratio?

Consider what happens if you have 1000 items of size 1, and 1 of size 1000.  Optimally, you would have 2 sets of size 1000, but if you followed the heuristic with items in ascending order, you will have one set of 500, and one of 1500, for a 3/2 approximation, worse than 7/6.


What is the name of this problem (the dual of the asymmetric k-center problem) I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse.

In this problem, the number of warehouses is fixed to $k$, and the goal is minimizing the maximum distance between any city to it's the nearest warehouse.

But, if we want to find a minimum number of centers to meet the demand of having maximum distance from any cities to it's nearest warehouses be fixed (less than) to $t$, what known problem is defined.

Actually, instead of minimizing the distance, I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?

It is not entirely clear to me where the warehouses are allowed to be placed. I will assume here that a warehouse can be placed in any city given by the input1.

instead of minimizing the distance [$t$], I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?

Observe that we may assume the maximum allowed distance $t=1$, because we can simply scale the input by a factor of $1/t$. This problem is known as the DISCRETE UNIT DISK COVER problem (DUDC).
DUDC is NP-hard. To see why, first note that the problem is equivalent to the dominating set problem on unit disk graphs.2 The dominating set problem is NP-hard for general graphs, but this does not imply that it remains hard for unit disk graphs in particular. However, the dominating set problem is known to be NP-hard on "grid graphs": unit disk graphs that have an embedding where all vertices lie on an integer grid with disks of radius $1/2$.3 Since all grid graphs are unit disk graphs, the dominating set problem is NP-hard for unit disk graphs, and hence DUDC is NP-hard.

1: Another option is that there is a finite number of fixed sites for warehouses, which are not necessarily inside a city. But this has the problem I discuss here as a special case, so my discussion here shows that both problems are in fact NP-hard.
2: Technically, we need to restrict ourselves to unit disk graphs for which we can compute an embedding in polynomial time, as this is not known to be possible for an arbitrary unit disk graph. Fortunately, this is possible for "grid graphs" (what helps is that these graphs are planar, unlike general unit disk graphs), so the construction works out fine.
3: See the paper Unit disk graphs by Clark, Colbourn and Johnson. They also note there exists an earlier proof for the hardness of the DUDC problem in the conference paper "S. Masuyama, T. Ibaraki and T. Hasegawa, The computational complexity of the M-center
problems in the plane" from 1981, but this paper appears to be accessible only for members of the Japanese institute that published the conference proceedings)


Doubt in derivation of a proof in Information Theory In my class we were trying to derive Shannon's Source Theorem, first by proving the equivalent form in a weaker version.

The question is: Consider a biased coin with probability of heads $p \geq \frac{1}{2}$.We want to transfer this information with the code of minimum expected length.

To prove this, we can construct a code such that for any $\epsilon $, for large $n$, there exists a code such that average code length is less than $(1+\delta)nH(p) $ and also the lower limit of the code length is $(1-\delta)nH(p) $

We tried to prove it by first getting the inequalities
$$ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} \leq 2^{nH(p)}$$
Both these inequalities are easy to derive. The problem comes with deriving the lower limit we try to prove that in an optimal code the length of the lower probability event is greater than equal to higher probability code, and then try to find the length of one of the events of higher probability an conclude by showing that since the lengths of events with lower probability is going to be more than this the expected length is more than  $(1-\delta)nH(p) $

Hence, since  $ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} $, one of the events containing $np $ heads will be of length greater than $log_{2}\frac{2^{nH(p)}}{n+1}$ . That is $ nH(p) -\log_{2}(n+1) $ . However to complete this part of the proof I need to prove the probability of all events with less than $np$ heads is a constant. Is it true for a binomial distribution that for an event with probability of success greater than $c$ where $c$ is some constant independent of $p$? By proving this we can prove that the expected length of the code is greater than $ c \times (nH(p) -\log_{2}(n+1)) $ which comes up to $(1-\delta)nH(p) $

For fixed $p$, the central limit theorem shows that
$$
\begin{align*}
\lim_{n\to\infty} \Pr[\mathrm{Bin}(n,p) \leq np] &= \lim_{n\to\infty} \Pr[\tfrac{1}{n}\mathrm{Bin}(n,p) \leq p] \\ &=
\Pr[N(p,\tfrac{p(1-p)}{n}) \leq p] \\ &= \frac{1}{2}.
\end{align*}
$$
In this particular case you can get quantitative bounds in several ways, for example using the Berry–Esseen theorem or large deviation theorems such as the Chernoff bound.


Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior I asked this question on Stack Overflow, but I have not obtained an actual answer to the question.

Tarjan's strongly connected components algorithm is stunningly beautiful, and inexpressible in a literal way in any programming language that I know of.

Allow me to refer to the pseudocode in the Wikipedia article. The problem is with the code that pops the strongly connected component we just found from the auxiliary stack:

// If v is a root node, pop the stack and generate an SCC
if (v.lowlink = v.index) then
  start a new strongly connected component
  repeat
    w := S.pop()
    w.onStack := false
    add w to current strongly connected component
  while (w != v)
  output the current strongly connected component
end if

The instruction w := S.pop() is unsafe, because, as far as the programming language's static semantics knows or cares, S could be empty. (Of course, a human programmer can easily tell that S will not be empty, because we are only popping S until we find v, which is initially contained in S.) Hence, a compiler for a memory safe language will emit code that

Checks whether S is empty.
Raises an exception if the stack is empty.
Pops and returns the stack's top element otherwise.

I am not too worried about the (negligible) performance impact of the useless test of emptiness. (Thus, “rewrite it in a memory-unsafe language” is not an answer.) However, I am concerned with the fact I cannot communicate an important invariant in a way that the compiler can treat as actionable information.

My questions are:

Am I overlooking some way in which I can communicate to the compiler the fact that S contains v?
If the answer to the first question is negative, is there a proof that I can't communicate this fact to the compiler?

EDIT: I am starting to suspect that the key to solving this conundrum is to use the same tricks I used to work around the lack of polymorphic recursion in SML without introducing redundant safety checks, but I need to properly write this down.

There will always be situations where we can see there is a complex invariant but the compiler cannot derive it.  Type systems are sound but not complete: not all invariants can be expressed in the type system.  So this isn't something specific to Tarjan's algorithm; it is a general fact of life when working in a type system -- sometimes the compiler will insert type checks that the programmer can tell won't be necessary, and similarly, as a programmer you might need to insert type checks that you can tell won't be necessary.


Proof of value discovery in complete graphs I have an assignment

There are n > 2 finite processors, two registers for each processor.
Register s_i is not readable by the processor p_i but any other processor can read it.
Register r_i is readable and writable by the processor p_i and any other processor can read it.

I have to solve the problem to let p_i discover the secret s_i value by reading r_i value. I don't have to (probably) come up with something super-scientific a somewhat simple proof will do just fine. I've been reading through various publications (leader election, complete graphs, uniform, etc) but wasn't able to find a point to start from.

If I understand correctly, a rough approach could be as follows.

Each processor $p_i$ can read $s_{i+1\ {\sf mod}\ n}$ and write its content to $r_i$.

Then each processor $p_i$ can read the wanted value by reading $r_{i-1\ {\sf mod}\ n}$.

The main issue of this naive algorithm is that some synchronization is needed between the two steps: $p_i$ must not read $r_{i-1\ {\sf mod}\ n}$ too soon, before it is written by $p_{i-1\ {\sf mod}\ n}$.