Binary search uneven split number of queries? For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/2, then number of queries is log with base 3/2. Why is this so? Would someone please help me get an intuitive understanding of why this works?

The number of queries in the question is assumed to mean the exact upper bound of the number of queries in the worst case. So, only the worst case is considered except in exercise 3. That is,  the wanted element will be in the "2/3" part after each query.

Suppose we have $3m$ ordered items currently. After a split by ratio 1/3:2/3, we will be left with $2m$ choices. So each query reduces the number of choices by a ratio of $3m:2m=3:2$.

After $k$ queries, the number of choices will be reduced by a ratio of $(3/2)^k$. In order to have only one choice left after $k$ queries, we should have $\frac{n}{(3/2)^k}\approx 1$, where $n$ is the number of original items. So the number of queries, $k$ is about $\log_{3/2}n$. That is the simple intuition.

Of course, the above reasoning is not rigorous since we could have $3m+1$ ordered items. The number of items left after one query will be $2m$ or $2m+1$ (depending on how we round the fractional item), which is approximately $(2/3)(3m+1)$.

Or we could have $3m+2$ ordered items. The number of items left after one query will be $2m+1$ or $2m+2$, which is still approximately $(2/3)(3m+2)$.

It turns out that the number of queries will be between $-3+\log_{3/2}n$ and $1+\log_{3/2}n$ for all $n>1$. So there is not much error to say the number of queries is log of $n$ with base 3/2.

Exercise 1. How many queries are needed if we binary search 26 items with splitting ratio $1/3:2/3$? ( Answer: 6 for floor, 7 for rounding or 8 for ceiling.)

Exercise 2. Write the approximate formula for the number of queries needed if we binary search $n$ items with splitting ratio $1:t$.

Exercise 3. Write the approximate formula for the number of queries needed in the best case if we binary search $n$ items with splitting ratio $1/3:2/3$.


Is the language TMs that accept finite languages Turing-recognizable? I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ).  But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a  general way for proving that a language is not recognizable like for undecidability  we try to reduce an undecidable problem to the current problem ?

If that method worked, semi-decidability would always imply decidability for infinite languages (note how you don't need any property of $L$ to make the proof work), which we know is not true.

Since your reasoning is sound, one of your assumptions has to be faulty. What you assume is, paraphrased:

  Assuming semi-decider $H$ for $L$, I can enumerate $L$ in lexicological order by using $H$.

You don't say how you do this, though, and we have already determined that you can not.

What you probably had in mind that we always get a recursive enumerator, and even a repetition-free one for infinite languages. Thus, it's the order that has to be impossible to achieve.

Intuitively, you can not reject $i$ as next output of the enumerator after only finite time.

Proving that $L$ is not semi-decidable works by reduction as well. See here for inspiration.

Hint:

   Reduce from $\overline{K}$, the complement of the Halting language.

Details:

   Define a computable mapping $\langle M \rangle \mapsto \langle M' \rangle$ so that $\langle M \rangle \in \overline{K}$ if and only if $\langle M' \rangle \in L$. For instance, define $M'$ by

 M'(y) :
   Simulate M(⟨M⟩) for y steps.
   if M halts
     accept y
   else
     reject y
 Note how $L(M') = \emptyset$ if $\langle M \rangle \in \overline{K}$, and
 $L(M') = \mathbb{N}_{\geq N}$ if $M$ halts after $N$ steps on its own code.


Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$
decreases by some positive number, how to prove the the MST is unchanged (still $T$) ?

It seems obvious by Kruskal's algorithm if the weight of all edges are different, if the weights are same, or some of them are same, how to prove it?

There is no necessarily a unique MST for a given G. So reducing an edge might trigger an MST finding algorithm to find a alternative MST. The question is if given MST remains an MST after the change.

Let's make some definitions:

$e$ is the edge we reduce its weight
$w(e)$ is the weight of the edge e
$w(T)$ is the weight of tree T (sum of all edges)

I will prove it by contradiction
Let's suppose that after decreasing the weight of of edge $e$ from $w(e)$ to $w'(e)$ T is no more a minimal spanning tree, and $T'$ is a minimal spanning tree.

First we consider the case where $e \in T'$

After the decrease of w(e)-> w'(e) the new graph is $G'$.
In $G'$ we have:

$w(T') < w(T)$ by assumption

$w'(e) + w(T' - {e}) < w'(e) + w(T-{e})$

$w(T'-{e}) < w(T-{e})$ and that is true both in G and G', since $\{T'-e\}$ and $\{T-{e}\}$ are same in both graphs

Then subsequently in $G$ we have
$w(T'-{e}) < w(T-{e})$

$w(e) + w(T'-{e}) < w(e)+ w(T-{e})$

$w(T') < w(T)$ which means that in G T is not a minimal spanning tree which is not true.

Now we consider the case where $e \notin T'$

Then in G' $w(T')< w(T)$ and by the same sequence

$w(T'-{e}) <  w(T-e)$ in both $G$ and $G'$

In $G$ we have consequently
$w(T'-{e}) + w(e) < w(T-{e}) + w(e)$ and if $T'' \equiv \{T'+e\}$ then

$w(T'') < w(T)$ which again contradicts the truth that T is MST in G.


Relation between semi decidable, undecidable and countable sets I know that

decidable problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings )
semidecidable problem: has counting algorithm and TM halts for member strings
countable problem: has only counting algorithm

Now I have come across undecidable language set which does not have membership algorithm (as semi decidable languages at least have TM which halts for member strings, which is not the case for undecidable problems), that is it does have TM that halt neither for member string nor for non member string.

I have doubt about the relationship between these language classes.

I know "decidable $\subset$ semi decidable $\subset$ countable".

Where does "undecidable" fit here?

Is it like this?:

(Match the color of text with that of the border. Region color is lighter shades of corresponding enclosed texts.)

Q. Is above diagram correct? Also I want to add "countable" to above. I feel, for finite alphabet languages, countable will be proper superset of "undecidable". Is it right?

PS: I feel, earlier I based my understanding of "undecidable" on incorrect definition given in this question. So I draw wrong diagram earlier. I believe its correct now.

Undecidable is simply the complement of decidable, as the name suggests: anything that is not decidable is undecidable. So the whole pink area of your diagram consists of undecidable languages.

All languages over finite alphabets are countable. For example, every string over alphabet $\{0,1\}$ is a natural number written in binary.1 Everything in your diagram is countable. We only ever consider finite alphabets; infinite alphabets aren't physically realizable because we can't store infinitely many distinguishable possibilities in a finite space.

1. A small problem is that $0$, $00$, $000$, etc. are all the number zero written in binary. So, instead, associate the binary string $xyz$ with the natural number $1xyz$ and now, every binary string represents a different natural number.


Is there a recommended process for designing CSGs (other than intuition)? I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the palindromic strings, but not easy per say for other combinations. But when asked to produce a CSG for Context-Sensitive language (not regular, not context-free), with restrictions on the terminals with respect to other terminals, it becomes difficult. I'm having trouble coming up with the production rules.

Is there some recommended process or method that people use to come up with the rules? Or do they just keep trying out example strings to "capture the essence" of them?

I would post an example, but this is for an assignment, so I can't give it away. In general I would just like to be better at coming up with the grammars.

The hint by Yuval in his comment is the right one. An approach to writing context-sensitive grammars is to design them like a machine. Send messages over the string. This is very close to writing a linear bounded automaton (or linear space Turing machine). In such a machine the reading/writing head scans over the tape while updating the string. This head (with the machine state) can be modelled by a production, like $ap\to qb$ for "in state $p$ while reading $a$, write $b$ and move left, changing state to $q$", where we assume the state is written to the right of the position of the head.

There are differences. The CSG is more flexible as one can insert letters in the middle of the string, and moreover there can be parallel processes going on at the same time. The latter can be a nuisance when arguing the approach is correct.

Lets see how the messages work in an example:
$L = \{ww\mid w\in\{a,b\}^*, |w|\ge 1 \}$, or squares.

Start with left and right sides of the string with the rule $S\to LR$. As markers and messengers cannot disappear in a CSG they must represent a letter in the final string. This letter can be $a$ or $b$ so we have two rules instead: $S\to L_aR_a\mid L_bR_b$. Now the left marker generates new letters and a messenger that becomes a copy at the other half of the string. $L_\sigma\to L_\sigma aM_a\mid L_\sigma bM_b$. Everywhere in these rules $\sigma,\tau$ may take the values $a,b$.
Messengers move over other letters: $M_\sigma\tau\to \tau M_\sigma$. At the beginning of the second half write the letter: $M_\sigma R_\tau \to R_\tau \sigma$.

We should end the derivation by removing the boundary markers $L_\sigma\to\sigma$, $R_\sigma\to \sigma$. We have a problem when the right marker is gone, while there is still a messenger under way. This can be solved by extra symchronization. However, no terminal string will be generated this way; the drivation is lost, so there is no real problem.

I tried a similar approach here  for the language $\{a^ib^jc^{ij} \mid i,j\ge 1\}$. Here a hint for squares (numbers) $\{a^{n^2} \mid n\ge 1\}$.  As you see, I practise a lot.

PS. I hope you mean a monotonic grammar rather than a "real" context-sensitive one. Those are harder, but there is a standard (boring) transformation.


Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation In this blog the author states that the following

  So we now have a rather poor estimate of the number of values in the
  dataset based on bit patterns. How can we improve on it? One
  straightforward idea is to use multiple independent hash functions. If
  each hash produces its own set of random outputs, we can record the
  longest observed sequence of leading 0s from each; at the end we can
  average our values for a more accurate estimate.

can be replace with

  A better approach is one known as stochastic averaging. Instead of
  using multiple hash functions, we use just a single hash function, but
  use part of its output to split values into one of many buckets.
  Supposing we want 1024 values, we can take the first 10 bits of the
  hash function as a bucket number, and use the remainder of the hash to
  count leading 0s

I am confused on his description of replacement, can someone help me understand what does take the "first 10 bits of the hash function as a bucket number" mean? And how is it a direct replacement of the hashing multiple times and take the average.

Thanks

Edit:

The author claims that given a random hashed set of element, by counting the highest consecutive k prefix bit that is 0, you can estimate the cardinality of the distinct set to be 2^k.

But using 2^k once might not be a good idea, so he suggest using multiple hashing to determine the average of 2^k. For example given n distinct n hash function. 2^k_approximate = (2^k_1 + 2^k_2 + .....2^k_n)/n

However he claims that multiple hash can be be replace by using the first 10 bit of a single hash function as a bucket number. Which I don't quite understand why that would be similar to the original multi hash average technique.

Let us start with the original approach. We compute the hash values of all input elements, and choose the minimal one $h$. If the leading bit is at position $k$, then we estimate that the number of distinct inputs in the output is roughly $2^k$.

The idea behind this is that we think of the minimal hash as a minimum of $N$ random strings, where $N$ is the number of distinct inputs. We expect the leading bit of such a minimum to be at position roughly $\log_2 N$.

When using $D$ different hash functions, the corresponding experiment is

  Choose $N$ random strings for each of $D$ many bins.

We then calculate the leading bit of the minimal string in each bin, and use this to estimate $N$.

Now suppose that we use the top $B$ bits to choose one of $2^B$ buckets, and compute the minimum value in each bucket. As before, this should be similar to the following experiment:

  Distribute $N$ random strings into $2^B$ bins at random.

As before, we then calculate leading bits and use them to estimate $N$, but since this step is identical to the corresponding step in the multiple hash method, we just concentrate on the first part of the experiment (putting random strings into bins).

We expect each bin to get roughly $N/2^B$ random strings, and so this experiment is very similar to the following one:

  Distribute $N/2^B$ random strings for each of $2^B$ many bins.

This is the same as the experiment for multiple hash functions, with $D = 2^B$ and $N$ reduced by a factor of $2^B$.

You might be put off by the difference in $N$. However, this difference disappears when we calculate the number of hash function evaluations. If we have a quota of $M$ hash function evaluations, then in the multiple hash case we can only use $M/D$ inputs, whereas in stochastic averaging we can use $M$ inputs.


Analysis quickselect: Median of Medians with duplicates in This Lecture Notes 1 (page 3), it is said concerning quickselect with median of medians:

  If there are repeated elements
  ...
  Alternatively, one has to refine the algorithm and the analysis
  (see CLR).

But in my copy of CLRS (2011), the authors assumed that the elements are distinct.

How would one refine the algorithm and the analysis?

(I'm aware that you can make elements distinct in O(n), but I'm interested in the alternative)

[1] - https://people.eecs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

A common refinement to quicksort could also be used with quickselect to deal with duplicates. Instead of partitioning into two buckets, do so into three. This new partition is called the "fat partition". It holds items that are equal to the current pivot. When there are no duplicates, this adds 2% overhead to the sort, according to the following paper.
See https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf
The paper discusses several memory layouts for partition, like whether to put the fat partition in the middle or the end of the invariant array or even split it and put part at the head and part at the tail, all to reduce the number of memory swaps.
The paper quantifies the huge benefits for some extreme edge cases, like when the data is a random set of ones and zeroes. In that case, their algorithm went from being four times slower than a benchmark Unix qsort to being twice as fast, an 8x speedup by the addition of a fat partition.


Theory behind regex implementations In a 2007 article, Russ Cox (at presents, he leads the development of the Go programming language at Google) argues that regex engines in languages like Java, Perl, PHP, Python, Ruby are built on a different theoretical framework from implementations like awk or sed. Cox claims a difference in performance between 60s and 20microseconds (the difference is an order of magnitude of millions!). Link to the article.
Is this issue still up-to-date? That is, is the theory behind these groups of implementations basically different?
Is there any real life scenario when a programmer would need to pick some Jurassic implementation like awk (due to its solid theoretical framework) because otherwise the task at hand could not be dealt with?

It isn't a matter of implementation. It's a matter of different approaches to parsing that unfortunately have similar names.
NFAs and DFAs (finite-state machines) can only recognize regular languages. Regular expressions are a way of specifying regular languages, and they can be compiled into efficient NFAs or DFAs that recognize the language. This is all taught in undergraduate CS courses.
The so-called "regexes" in Perl and its many imitators have a name that sounds like an abbreviation of "regular expression", and they syntactically resemble the regular expressions of sed and awk, but they are not regular expressions. They are really specifications of backtracking parsers. Backtracking parsers aren't limited to recognizing regular languages. (The name "regex" is Larry Wall's fault. He made a deliberate decision to not call them "regular expressions" because he knew that they weren't, but he should have invented an entirely different name.)
You don't need a Jurassic implementation of NFA/DFA based regular expression matching; modern maintained libraries are available for popular languages. But they lack many features of Perl-style regexes, and they don't offer much in exchange. They certainly have much better worst-case performance, but the pathological worst cases of backtracking parsers can be fixed by modifying the regexes, without losing the extra flexibility of backtracking.
The article by Cox is disingenuous. He evidently wants you to believe that the authors of regex libraries are ignorant of the theory of regular languages, and if they had just studied the standard undergraduate CS curriculum then they would have implemented their libraries in a different way and made them faster. That's false. It's impossible to implement Perl-style regexes that way, and he knows it. The popularity of Perl-style regexes is probably due in large part to their flexible feature set that goes far beyond what's available in any true regular expression library.


How to find a minimum cut of a network flow? I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph.

Could someone explain how to find the minimum cut of this graph? I THINK the minimum capacity is 4.

The minimum cut is a partition of the nodes into two groups.

Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $A$. The rest of the nodes (the unreachable ones) can be called $B$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $A$ to a node in $B$.


Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$ When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa.
I'm thinking that this equal to $P=NP$, but I saw a solution (an example) that I disagree with:
$M$ is a non-deterministic polynomial by time Turing machine that decide $SAT$, if all that paths   are rejected then $L(\overline{M})=\Sigma^*\in P$
Is it a valid solution, or as I'm thinking $L(M)\in NPC$ and $L(\overline{M})\in P \Leftrightarrow P=NP$

Let's imagine a Non Deterministic Turing Machine $M$ that decide $SAT$. If we tune this machine a bit, and add a transition on the initial state, for every letter read, that reject the entry. Let $M'$ be the new NTM. Then, $L(M') = L(M)$, since $u\in L(M) \Leftrightarrow \exists$ at least one computational path in $M$ to an accepting state (and the same thing for $M'$).
Now consider $\overline{M'}$. Since we added a rejecting transition which is possible for every entry in $M'$, that means that there is an accepting transition for every entry in $\overline{M'}$, so it means that $L(\overline{M'}) = \Sigma^* \in P$.
That does not necessarily imply that $P = NP$, the reason being that $L(\overline{M'}) \neq \overline{L(M')}$.
Generaly speaking, $L \in NPC \Leftrightarrow \overline{L} \in \text{co-}NPC$, but that is not the case if you consider a Turing Machine and its switched version.


why is discrete maths needed to understand algorithms? I am new to algorithms. I need to know is it necessary to study discrete maths to understand algorithms. If so, why? In particular, is it necessary for understanding algorithms or is it only necessary for making your own algorithms (when you need to prove algorithm correctness).

There are several angles to this question.

First, most algorithms work on discrete abstractions like graphs, trees, matrices, sequences. To understand what the algorithm does, you need some acquaintance with those. They are staple of discrete mathematics. To prove the algorithm works as claimed relies on said properties, and the proof is essentially doing discrete mathematics.

Second, to use algorithms successfully, you need to know how to map your real work problem to the above abstractions, that again means knowing their particularities.

Third, you usually will want to derive performance numbers, either to verify the algorithm works within given constraints (time, space), or to compare alternative approaches and evaluate tradeoffs. Again, a job for discrete mathematics.

Sure, you certainly can do a lot without going deeply into discrete mathematics (at least not openly), but it is a valuable toolbox.


Lower bound on number of (different) circuits of given size? For circuits with $n$ input bits, we know that, for any function $s$, there are at most $O(s(n)^{s(n)}) = O(2^{s(n) \log s(n)})$ circuits with size at most $s(n)$.

Say two circuits $C_1$ and $C_2$ are different if the function they compute is different, that is, there is an $n$-bit string $x$ such that $C_1(x) \neq C_2(x)$. The $O(s(n)^{s(n)})$ bound above is an upper bound on the number of circuits of a given size. Is there a known lower bound on the number of different circuits with size at most $s(n)$ for different values of $s(n)$ (e.g., $s(n) \in \mathsf{poly}(n)$, $s(n) \in n^{\textsf{polylog}(n)}$, or $s(n) = 2^{n^\varepsilon}$)?

Clearly such a bound must be strictly smaller than the $O(s(n)^{s(n)})$ bound since there are pairs of circuits with different structures (and even different number of gates) and which nevertheless compute the same function (i.e., they are not "different" as defined above)—but how smaller can it be?

Let $1000 \leq s \leq 2^n/n$.
Every function on $m$ bits can be computed by a circuit of size $O(2^m/m)$ (I believe that even the optimal constant is known). Choose a value of $m$ such that every function on $m$ bits can be computed by a circuit of size $s$, and furthermore $s = \Omega(2^m/m)$.
Since there are $2^{2^m} = s^{\Omega(s)}$ different functions on $m$ bits, we see that your upper bound is quite tight.


Calculate the number of distinct permutations of length n in the closure of a language I am studying a distance CS course, but there is no tutor available, so I would appreciate your help...

Consider the language $S = \{a, aa, ab\}$
How many distinct words of length $n$ will appear in $S^*$?

Is there a way to do this without having to "enumerate" $S^*$ until the answer is found?

The language $S^*$ is regular.  Therefore, it can be expressed by a DFA.  Now use Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038.


Floating point arithmetic I need to change x1 = 0.3 and x2 = -0.29 to a FP(floating point) number with one sign bit, a 4 bit mantissa, a 3 bit exponent. The results I got are:

x1: 0 001 0011

x2: 1 001 0010

I am also trying to calculate the number of significant digits of x1 and x2 and I have found 2 for each, but I am unsure of this result.

The question also requires me to find z = (FP)x1 + (FP)x2 and the number of significant digits of z. But I am not sure how to proceed with this part of the question. Therefore, any guidance on how I could proceed would be greatly appreciated.

Thank you very much!

Firstly, you need to decide if the floating point numbers you are working with are "normalized" or not.

Think about how binary numbers are represented in scientific notation.

Consider the number 100101.010101
The expression given above is not given in scientific notation, but what if we change that?
To re-write 100101.010101 in scientific notation, we move the binary point to the left until we have  $1.[\text{something}] * 2^{\text{some power}} $
For the specific example I gave, we have $(1.00101010101)_2*(2^5)_{10}$
Note that binary numbers written in scientific notation almost always begin as <one><dot><something>

As such, most computers today do not store the leading $1$. Normally, this leading $1$ would be the most significant bit of the mantissa. However, its existence is implied in normalized numbers. There is only one number whose binary scientific notation representation does not begin as "one-dot-something." That number, is zero. As such 1.0000[...] * 2 ^ [some large magnitude negative number] represents the number zero in many computer systems today.

You say that you want to represent $0.3$ as a floating point number.

First, I think it will help to represent $(1/2), (1/4), (1/8), (1/16),$ etc... in decimal form.

$(1/2) = 0.5$
$(1/4) = 0.25$
$(1/8) = 0.125$
$(1/16) = 0.0625$
$(1/32) = 0.03125$
$(1/64) = 0.015625$

Okay; $0.3 = 0.25 + 0.05$
$0.25 = (1/4)$. $0.05$ is the leftover remainder.

$0.05 = 0.03125 + 0.01875$
$0.03125 = (1/32)$.
$0.01875$  is the leftover remainder.

Okay; $0.3 = 0.25 + 0.03125 + 0.015625 + 0.00029296875$

We have $0.3 = (1/4) + (1/32) + (1/64) + 0.00029296875$
$(0.3)_{10} = (0.010011)_{2} + $ a remainder of $(0.00029296875)_{10}$

You said that you only wanted a 4 bit mantissa. I think our leftovers/remainder are small enough at this point.

Let's write the number in scientific notation.

$(0.3)_{10} = (1.0011)_{2} *(2^{2})_{10}  + $ a remainder of $(0.00029296875)_{10}$

I suppose we want the exponent in binary-format instead of decimal. We can do this:

$(0.3)_{10} \approx (1.0011)_{2} *(2)_{10}^{(100)_{2}}$

SIGN: POSITIVE
MANTISSA: 10011
EXPONENT: 100

You wanted a 4 bit mantissa, but I went out to 5 bits. We round the number to obtain that $0.3$ is represent-able as:

SIGN: POSITIVE
MANTISSA: 1001
EXPONENT: 100

A normalized float would omit the leading $1$ of the mantissa. However, simply explain in your homework, that it was not specified whether the float be normalized or non-normalized. Therefore, you chose to use non-normalized floating point numbers.

You asked about significant figures. There are many different definitions of "significant figure." All of these different definitions are about how many of the leftmost digits of the approximation are correct.

Imagine writing two numbers lined up on a sheet of paper

APROX: 0.00070384
EXACT: 0.00070392

Now, cover-up the rightmost digits with a blank sheet of paper

APROX: 0.0007
EXACT: 0.0007

They are both correct for the number 7. That's good. slide the topmost sheet of paper to the right

APROX: 0.00070
EXACT: 0.00070

They're still the same. That's 2 significant figures so far.

APROX: 0.000703
EXACT: 0.000703

Still the same up to 3 figures.

APROX: 0.0007038
EXACT: 0.0007039

Uh oh; 8 and 9 are different. So the exact value, and the approximation are the same up to 3 significant figures, but not 4 significant figures.

The above method does not work very well.

Note that 0.499999999999999999999999999999 is a very good approximation of 0.5 However, if you use the sliding paper method, then not a single digit matches, and so, the approximation is not correct to even 1 significant figure!

My procedure for calculating significant figures will be different from the sliding paper method. The procedure is as follows:

Put the exact value in scientific notation.
Put the approximate value almost in scientific notation. However, make sure the approximate number has same exponential term as the exact value. Maybe the approximation is not of the form X.XXX Maybe the approximate number looks like 0.0XXXX or XXX.X
Subtract the approximate from the exact, or vis versa.

The number of significant digits is the number of zeros on the left.
For example, 0.000XXX means 4 significant figures. 0.XXXXX means 1 significant figure.

To calculate teh number of significant figures, convert your floating-point number back into decimal:

SIGN: POSITIVE
MANTISSA: 1001
EXPONENT: 100

$(1.0011^{100})_{2} = (0.28125)_{10}$

Notice that the floating point approximation is not the same as the exact value of $0.3$
Just how different are they?

$3.0 *\text{some exponent} - 2.8125 *\text{the same exponent} = 0.1875$

The floating point approximation of 0.3 is correct to 1 significant figure.

Repeat the process for -0.29:
1. Calculate the floating point approximation.
2. Take the difference between the approximation and the exact value.
3. Count the number of leftward zeros in the difference.

$-0.29 = -(1/4 + 1/32 + 0.00875)$

Note that the remainder $0.00875$ is less than $(2^-6)$. Your mantissa is only 4 bits long, so we needn't worry about the remainder.

$-0.29 \approx -(1/4 + 1/32)$
$-0.29 \approx -0.28125$
$2.9 - 2.8125 = 0.0875$
The floating point approximation of 0.29 is correct to 2 significant figures.

The exact value of 0.3 + -0.29 is 0.01.

Compute the following:

(float approx of 0.3) + (float approx of -0.29) =
(2.8125) + -0.28125) =
0

Then compare the approximate value (0) to the exact value (0.1) for the number of significant figures of $z = float(x_1) + float(x_2)$

1.0 - 0.0 = 1.0

The result has zero significant figures of accuracy.

Note that your textbook's definition of significant figures is probably different than mine. In your homework, explain to your teacher what definition you used. The concept of significant figures is more important that the details. Knowing roughly how many digits of the approximation are correct is more important than knowing exactly how to compute the number of significant figures.


In which paper is written that you can transform one problem to another to show NP-completeness? For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard:
Post

I am searching for a scientific paper to cite where it is written, that this is a valid method.

Does anybody knows one?

If I may make an assumption, you want such a reference to be able to put it in one of your works, right ? I don't why you would wanna do that as if you have a problem A, reducting a NP Hard problem to problem A quite clearly shows that A is NP Hard. No one bothers proving it as it's such a straightforward and fundamental result. If you need to prove it for some reason you can do it in two lines. If you still want a reference for a reader to read about NP in general then just quote Arora and Barak's book on complexity theory.


Do dynamic/static languages associate types or classes to values or variables? In Practical Foundation of Programming Languages by Harper

  There have been many attempts by advocates of dynamic typing to
  distinguish dynamic from static languages. It is useful to consider
  the supposed distinctions from the present viewpoint.

  Dynamic languages associate types with values, whereas static languages associate
  types to variables. Dynamic languages associate classes, not types, to values by tagging them with identiﬁers such as num and
  fun. This form of classiﬁcation amounts to a use of recursive sum
  types within a statically typed language, and hence cannot be seen as
  a distinguishing feature of dynamic languages. Moreover, static
  languages assign types to expressions, not just variables. Because
  dynamic languages are just particular static languages (with a single
  type), the same can be said of dynamic languages.
  Dynamic languages check types at run-time, whereas static language check types at compile time. Dynamic languages are just as surely
  statically typed as static languages, albeit for a degenerate type
  system with only one type. As we have seen, dynamic languages do
  perform class checks at run-time, but so too do static languages that
  admit sum types. The difference is only the extent to which we must
  use classiﬁcation: always in a dynamic language, only as necessary in
  a static language.

What do the first two sentences in the first part try to say:

What do dynamic languages associate  with values: types or classes or both?
What is the significance of associating types or classes to values or variables? Do static languages associate types to variables but not to values? Do dynamic languages associate types or classes to variables besides values?

Thanks.

In those bullets, Harper is addressing common misconceptions about static versus dynamic typing. Each of those bullet points starts with a misconception, and then continues with Harper's clarification.

So, the first misconception is:

  Dynamic languages associate types with values, whereas static languages associate types to variables.

Harper disagrees, and instead says that dynamic languages associate classes to values. This comes from a type-theoretic perspective, where it is useful to reserve the notion of a "type" to a particular form of static classification of expressions. In the textbook, Harper defends this perspective by demonstrating that "dynamic types" and "static types" can coexist, and in this way, the two concepts are orthogonal. In particular, there is a special static type which Harper calls dyn, and values of type dyn are given a tag at runtime which identifies their class, i.e. their "dynamic type". (By the way, it's worth mentioning that this tagging mechanism is exactly how dynamic types are implemented in modern languages.) In dynamically typed languages, it is often the case that the static types do not carry very much information, for example all expressions might actually have the static type dyn.

The interest in "values versus variables" comes from the "dynamic versus static" perspective on types. If we associate "types" with values, then we can only determine their "type" at runtime. But if we associate types with variables, then we can determine the type of the variable statically. Harper is just trying to point out that there doesn't need to be an issue of "this versus that": dynamic types and static types do not lie on the same spectrum. Simply put, from the perspective of type theory, "dynamic types" are not types.

To sum up, if we take a type-theoretic perspective and make a distinction between types and classes, then we can make this statement: all languages associate types with both variables and values. In fact, we can make an even stronger statement, which is this: all languages associate types with expressions. Variables and values are just two different forms of expressions.


Description logics with decision problems within NP Is there any description logic where important decision problems (e.g. abox consistency or concept satisfiability) lie within NP with respect to their time complexity?

The well-researched family of $\mathcal{ALC}$-based logics might not work since even for $\mathcal{ALC}$, problems are PSpace-complete. Neither would the $\mathcal{EL}$ family since the problems are at least CoNP.

Some restriction thereof might work, though, although I couldn't find any so far.

Can see here https://www.w3.org/TR/owl2-profiles/#Computational_Properties  for OWL-EL, OWL-QL and OWL-RL


Efficient method for generating the smoothing function The smoothing function of a boolean function with respect to one of its variables is the disjunction of its cofactors. For example given a Boolean function F(a,b,c) the cofactors with respect to a are F(0,b,c) and F(1,b,c), the smoothing function with respect to a therefore is G(b,c) = F(0,b,c) + F(1,b,c).

Now, given a circuit for F, one simple method for creating the circuit for G is to make two copies of the circuit for F, hardwire the inputs for a as 0 and 1 in the two circuits respectively and then OR the outputs. However this will double the number of gates needed. If one needs to do this for several variables, then the size of the resulting circuit grows exponentially in the number of variables removed. What bothers me the most about this is that we are creating simpler functions (as judged by the number of variables and consequently the size of the truth table) with increasing number of gates. This leads me to think that maybe there is a well known way for creating a circuit for the smoothing function using fewer gates than in the original circuit.

For the purpose of this question, let us assume that the truth tables are too big to enumerate and the functions under consideration are not linear.

Suppose that we are substituting variable $x$.

You will have a lot of zeroes and ones in the circuit, so a simple simplification function should help a lot. Additionally a potentially large part of your circuit unrelated to $x$ might be duplicated, so I would suggest preventing its duplication in the first place.

First I would mark any inputs (including the constants $0$ and $1$) to the circuit that aren't $x$ as unrelated. Second, any gate that only has unrelated inputs is marked as unrelated itself. This is done repeatedly until the result is stable. Then, any unrelated subcircuit which has a related gate as parent is removed and replaced with a temporary variable (e.g. $t_1, t_2,$ etc) and it is for each temporary variable what circuit it corresponded to.

Then you should apply your smoothing function definition and minimize recursively using $S$, applying matching with priority from top to bottom:

$$\begin{align}
S(0) &= 0\\
S(1) &= 1\\
S(\neg 0) &= 1\\
S(\neg 1) &= 0\\
S(a + b) &= \begin{cases}
    1 & S(a) = 1 \vee S(b) = 1\\
    0 & S(a) = 0 \wedge S(b) = 0\\
    S(a) & S(b) = 0\\
    S(b) & S(a) = 0\\
    S(a) & S(a) = S(b)\\
    S(a) + S(b)&S(a) < S(b)\\
    S(b) + S(a)&\text{otherwise}
\end{cases}\\
S(a \cdot b) &=\begin{cases}
    1 & S(a) = 1 \wedge S(b) = 1\\
    0 & S(a) = 0 \vee S(b) = 0\\
    S(a) & S(b) = 1\\
    S(b) & S(a) = 1\\
    S(a) & S(a) = S(b)\\
    S(a) \cdot S(b)& S(a) < S(b)\\
    S(b) \cdot S(a)& \text{otherwise}\\
\end{cases}\\
S(\neg \neg a) &= S(a)\\
S(\neg a) &= \neg S(a)\\
S(a) &= a\end{align}$$

Note that all comparisons here are done simply on the symbolic formulas, with comparison done in any consistent order (such as an arbitrary lexicographic order). This minimization isn't very advanced, but runs very fast and fully eliminates any constants unless the entire circuit is constant. If your primitive gates aren't conjunction and disjunction you'll need a different minimization function, but I think the concept is clear.

After minimization is done you can add back the $t_1, t_2,$etc circuits and connect wherever they occur.

Practical algorithms aside, I don't believe that your intuition of the circuit becoming simpler is correct when truth tables are too large to be enumerated.

Let's do a napkin math calculation. Suppose you have 64 inputs and consider a 'reasonable' useful circuit any circuit with $\leq 10000$ binary gates, then there are $4\sum_{g=0}^{10000}\sum_{k=0}^{g} (64+k)^2$ possible circuits, assuming $4$ different gate types. That's approximately $2^{52}$ possible reasonably sized circuits.

There are $2^{2^{64}}$ possible truth tables. We haven't even scratched the surface of the surface of all possible circuits. There is plenty of space for combinations of reasonable circuits to blow up exponentially in size and I don't see reason to believe why they wouldn't - there's plenty of domain left to blow up into.


Finding common edges of two graphs Is there any algorithm that finds the common edges and vertices between two graphs? Its not a common subgraph problem though, the edges which are common between the two graphs may not be connected to each other, may be far apart. How to find all the common edges in the graph? Like finding the common subgraphs between two graphs such that none of the subgraphs are connected to each other. Like these two graphs, the black and the blue part are the uncommon part...

This appears to be the maximum subgraph isomorphism problem: given graphs $G,H$, you want to find the largest pairs of subgraphs $G',H'$ that are isomorphic (where $G'$ is a subgraph of $G$ and $H'$ is a subgraph of $H'$ and $G'$ is isomorphic to $H'$).  Then the edges of $G',H'$ are common to both $G$ and $H$.  Apparently, this problem has been applied in chemistry, which might be of interest to you given the diagram you showed.

In the comments you asked about the case $G$ and $H$ both have two common subgraphs which are not connected to each other.  The maximum subgraph isomorphism solution will automatically find those.  Nothing requires $G'$ or $H'$ to be connected.  Thus, in your case, the optimal solution will have $G'$ consist of two disconnected components, and $H'$ consisting of the same two components.  So, this problem already does what you want.

This problem is NP-hard for general graphs, so the general expectation is that there's not likely to be any efficient algorithm that can handle large, general graphs.  However, you have two aspects that offer room for hope.  First, it appears that your graphs are relatively small, so there might algorithms that are acceptable for graphs that are about the size of the examples in your diagram: even exponential-time algorithms might be practical.  Second, and more importantly, it looks like you aren't dealing with arbitrary graphs.  As Tom van der Zanden accurately explains:

  The graphs shown in the example are both trees and they appear to be models of molecules. While of course molecules (like benzene) can have cycles, depending on what molecules the OP is interested in the problem may not be NP-hard.

So, I suggest you search the research literature to see if there's been work done on the maximum subgraph isomorphism problem for trees.  There might be algorithms that have been described in the algorithms literature that you could use.


How to write all $r$-tuples with a certain property in a list I have the following question:

Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$.

I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with $x\in [a..b]$ and $y \in [c..d]$.

Now, I have a new list, let's call it list_1. It consists of elements indexed by the $(x,y)$.

For example, let a=3, b=4, c=7, d=8.

Then my programm produces list=[[3,7],[3,8],[4,7],[4,8]].

Now, my list_1 is [M_{3,7},M_{3,8},M_{4,7},M_{4,8}].

  I would like to have a new list, call it list_2, which has exactly the following entries.

  list_2 shall contain all $r$-tuples (for $r\in\{1,...,m\}$; $m$ is the size of list_1) with the form

  $(M_{i_1},...,M_{i_r})$, such that $i_j$ is an entry of list, that comes before $i_k$ for all $j<k$.

  For example, $i_j=[3,8]$ comes before $i_k=[4,7]$.

In our example, list_2 looks like this:

$(M_{3,7}),(M_{3,8}),(M_{4,7}),(M_{4,8}),
(M_{3,7},M_{3,8}),(M_{3,7},M_{4,7}),(M_{3,7},M_{4,8}),(M_{3,8},M_{4,7}),(M_{3,8},M_{4,8}),(M_{4,7},M_{4,8}),
(M_{3,7},M_{3,8},M_{4,7}),(M_{3,7},M_{3,8},M_{4,8}),(M_{3,7},M_{4,7},M_{4,8}),(M_{3,8},M_{4,7},M_{4,8}),(M_{3,7},M_{3,8},M_{4,7},M_{4,8})$.

I would like to have this in general for arbitrary natural numbers $a,b,c,d$ with $a \leq b$ and $c\leq d$.

I would be very grateful, if somebody was able to send me a pseudo-code.

Thanks for the help!

There are many ways to compute all $k$-tuples of elements in a given list $L$. One way is to use recursion and the analogue of Pascal's identity $$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. $$ We can interpret this identity as follows. Write $L=x, L'$, where $x$ is the first element and $L'$ is the rest of the list. A $k$-tuple of $L$ is either a $k$-tuple of $L'$, or $x$ along with a $k-1$-tuple of $L'$. I'll let you figure out how to turn this into a solution for your problem.

Using the same idea, you can also write a function that given $m$ outputs the $m$th $k$-tuple of $L$, in lexicographic order. You can even decode such a tuple back to its index in this order.

If you don't like recursion, you can also try an iterative approach. The idea is to start with the tuple $0,1,\ldots, k-1$, and keep incrementing the tuple. To increment the tuple, start by incrementing the last position. If it's now $n$, we backtrack and increment the previous position. If that one is now $n-1$, we backtrack once more, and so on. Eventually, unless we were at the last tuple, we well have incremented some position successfully, say to the value $m$. The following position (if any) we set to $m+1$, the one after it (if any) to $m+2$, and so on. I'll let you figure out how to implement this idea.

Both approaches can be implemented so that they produce the same, lexicographic, order. There are probably other, trickier approaches, that rely on applying an intricate sequence of transpositions on the list $0,1,\ldots, n-1$, but the ones I described are general approaches applicable in many other situations. For the more magical ones, check Knuth's new volumes-in-preparation of TAOCP.


A O(n) algorithm for a point set triangulation I'm currently stuck at the following task:

Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have pairwise different $y$-coordinates and are sorted in increasing order of them, i.e., $y(p_i) < y(p_j) $ if and only if $i < j$.
Develop an algorithm that computes a triangulation of $S$ and needs $O(n)$ runtime and memory.

I found out how to triangulate monotone polygons, which is pretty close to the task, but I don't know how to transfer this into a triangulation of point sets in case the monoton polygonial has a "notch".

I'd be thankful for any kind of help.

You can find one triangulation similar to finding the convex hull. On your conditions finding the convex hull can be solved in linear time.

In order to find the convex hull of a set of points in $R^2$ let's do two sweep lines, one from left to right to compute the upper-hull and another from right to left to find the lower-hull. In order to illustrate the algorithm better I will use pseudo from here.

I'll augment it to solve the triangulation problem. My comments start with #

Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# We can skip this since points are already sorted
Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

# Initialize T as empty list to store triangulation
Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from L and P[i] to T (the triangulation)
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from L and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

Remove the last point of each list (it's the same as the first point of the other list).
Concatenate L and U to obtain the convex hull of P.
Points in the result will be listed in counter-clockwise order.
# Triple of points in T will be the triangles


How to find degree of polynomial represented as a circuit? I know very little about arithmetic circuits, so maybe it is something well-known.

Given a small circuit consisted of $\{1,x,-,+,*\}$ defining one variable polynomial. Let be additionally known that degree of this polynomial does not exceed $d$ and all the coefficients are small. I wonder if exists a fast way to find actual degree of this polynomial?
Using FFT and some small field, one can do it in $O(d)$ time (regardless $polylog$ factors), but this time is sufficiently to reconstruct the the entire polynomial, so I hope computing degree only can be done more efficient.

If the coefficients are small, then for large $x$ the polynomial is roughly equal to $Cx^d$. If you plug in both $x$ and, say, $2x$, then the ratio should be roughly $2^d$. Given bounds on the coefficients and the degree, this method can be made rigorous.

Another idea uses difference sequences. For a polynomial $P(x) $, the polynomial $P(x+1) - P(x)$ has degree smaller by one,  the polynomial $P(x+2)-2P(x+1)+P(x) $ has degree smaller by two, and so on (in general, the coefficients are binomial coefficients with alternating signs). Using polynomial identity testing you can find the degree by binary search. This seems less efficient than your approach.


Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time.

Additionally, all of the coefficients of $A$ are in $\{-1, 0, 1\}$, but I couldn't find a way to use that.

The trivial case is if the (matrix $A$ of the) system is invertible, there is only one solution, it is easy to check whether all of them belong to $\{0,1\}$.

However, if you have infinitely many solutions, and $k$ free variable, I can't find a way to do better than check all the $2^k$ possibilities.

Do you know any algorithm to do so in polynomial time ?

I also tried to do a reduction from SAT (or some variant with n clauses and n variables in each clause, to show that it is NP complete), but because of the fact that we have $Ax = b$ and not $Ax \geq b$, I couldn't do that either.

Do you have a reduction to show that this problem is NP complete ?

1-IN-3SAT is the following problem: given a collection of 3-clauses (just like 3SAT), decide whether there is a truth assignment which satisfies exactly one literal in each clause. 1-IN-3SAT is known to be NP-complete, see for example here. You can reduce 1-IN-3SAT to your problem – I'll let you work out the details.


Amortised analysis of a simple loop and 3 operations I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$.

Operation OP(S,X[i]) has complexity O(log|S|) and operations push and pop has constant complexity O(1).

S <- Emptystack
for i=1 to n do
    while (S!=0) and OP(S,X[i]) do
        pop(S)
    od
    push(S,X[i])
od

I would like to proove it using potential function. It would be simple if there were just pop(S) and push(s):

Pot.function represents number of items in stack

  C^ PUSH = 1 + |S|+1 - |S| = 2

  C^ POP = 1 + |S|-1 - |S| = 0

So the complexity would be linear (O(2n)) = O(n). But I don't know how to compute amortized complexity of OP.

We can divide the running time into several parts:

Pushes.
Pops.
The first OP performed at every round.
Subsequent OPs performed at every round.

Note that every OP costs $O(\log n)$, that there are at most $n$ pops, and that each "subsequent OP" follows a pop. We conclude that the total running time of pushes and pops is $O(n)$, the total running time of first OPs is $O(n\log n)$ (since there are $n$ rounds), and the total running time of subsequent OPs is $O(n\log n)$ (since there are at most $n$ pops). In total, the running time is $O(n\log n)$.

If you want to use the potential method, try to use a potential of the form $|S| + \log(|S|!)$.


Each cycle in the graph, the edge with the minimum weight belongs to MST Let $G=(V,E)$ be a weighted undirected connected graph and $w: E \to \mathbb{R^{+}}$  a weight function so that there are no two edges that have the same weight, and $T$ is an MST of $G$ . Then in each cycle in the graph, the edge with the minimum weight belongs to $T$.
I either need to prove it in a positive way or give a counterexample.

Following is a simple counterexample: Take a complete graph on four vertices: ${u_{1},u_{2},u_{3},u_{4}}$, with edge weights $w(u_{1},u_{2}) = 1$, $w(u_{2},u_{3}) = 2$, $w(u_{1},u_{3}) = 4$, $w(u_{1},u_{4}) = 5$, $w(u_{2},u_{4}) = 3$, and $w(u_{3},u_{4}) = 6$. Here MST is composed of edges: $(u_{1},u_{2})$, $(u_{2},u_{3})$, and $(u_{2},u_{4})$ with total weight $6$. And, no edge of the cycle $(u_{1},u_{3},u_{4})$ is part of the MST.


Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut? I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something.

The analysis goes as follows:

Fix a min cut $(A,B)$.

Let $k$ = # of edges crossing $(A,B)$ , these edges will be called $F$

Let $S_{i}$ be the event that an edge of $F$ is contracted in iteration $i$.

For the first iteration,
$\Pr [S_i] = \frac{\text{# of crossing edges}}{\text{# of edges}}=\frac{k}{m}$,

where $k$ is the number of crossing edges, and $m$ is the total number of edges.

Here's where I get confused:

Observation: The degree of each vertex is at least k

Reason: Each vertex v defines a cut $\left( \{v\}, V - \{v\} \right)$

I don't really understand. The reason given for his observation doesn't make much sense to me. Why would the degree of each vertex be at least the number of edges crossing our min cut (A,B)?

You pretty much have the answer in front of you.

For any vertex $v$, the cut $\left(\left\{v\right\},V\setminus\left\{v\right\}\right)$ has $\text{deg}(v)$ crossing edges.

If there exists a vertex $v$ with degree $<k$, then its corresponding cut has less than $k$ crossing edges, contradicting the minimality of $(A,B)$.


Is there a random shuffle algorithm using only true /false? Is there a way to randomly shuffle an array using only a source of random boolean values?  SO to clarify, shuffle using true /false only, and not integers or decimals.

For this question, I'm specifically excluding an approach whereby the booleans are just arranged into an integer and then it's used in a Fisher-Yates shuffle. I'd be repeatedly shuffling approximately 30,000 items and have a ready source of random booleans.  I'd need to build up a very large integer for Fischer-Yates to avoid any form of bias in the shuffle.  Can this step be avoided and true /false used directly somehow?  I have the sense that some soft of bubble sort might do it, with the comparison determined randomly, but I can't quite flesh it out.

I'd be interested in any algorithm than wasn't ridiculous i.e. with a stupid time complexity of something like 2^O(n). This question builds upon some of the concepts of Best random permutation employing only one random number but isn't identical.

No, there is no algorithm that shuffles an array of length $n > 2$ using a bounded number of random Booleans. This is because given an algorithm that uses $m$ random bits (at most), each outcome has a probability of the form $A/2^m$, whereas we need each possible permutation to have probability $1/n!$.

When you're using Fisher–Yates shuffle in the form you describe you aren't getting a uniformly random permutation, though you are getting something very close. If you want to get a truly uniform random permutation then you need to use some form of rejection sampling.

Using bubble sort in the way you describe would likely be a disaster – it would likely result in a random permutation which is easy to distinguish from uniform. Don't do that. There are no tricks and shortcuts. If you want your random permutations to be faster at the cost of being slightly less uniform, you can reduce the precision involved in approximating random integers inside the Fisher–Yates shuffle. This will probably be much better than inventing your own algorithm.


How to express a structure of a 5-colorable graph in logic A graph can be expressed as an structure $G = <A,R>$ satisfying the axioms
$ \forall xy R(x,y) \rightarrow R(y,x)$ and $ \forall x \lnot R(x,x)$.

How to extend the structure and/or axioms to express a 5 colourable graph?

General ideas:

Require that each vertex ($\forall x \ldots$) satisfies at least one color predicate (Use $\lor$ among five color predicates).
Also require that no vertex ($\lnot\exists x \ldots$) has two distinct colors (you can enumerate all the ten distinct pairs: $\lnot({\sf red}(x)\land{\sf blue}(x))\land \lnot(\ldots)\land \cdots$).
For each color (repeat this axiom five times, once for each color), require that if $x$ has that color and $R(x,y)$ then $y$ has not that color (e.g. $\forall x y.\ {\sf red}(x)\land R(x,y) \implies \lnot{\sf red}(y)$).


Comparing coefficients of boolean functions Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the set of $i$ such that $a_i=1$ and $\bar{1}_a$ is the complement of $1_a$. How do you represent $c_a$ in terms of $p(a)$?

Is for all $b\in\{0,1\}^n$, $c_{b} = \sum_{a\in\{0,1\}^n}(-1)^{<b,a>}p(a)$?

Consider the function $P(x_1) = x_1$. Then $P(0) = 0$, $P(1) = 1$, and the polynomial representation is $x_1$, but your formula gives $c_0 = 1$ and $c_1 = -1$. However, if we define $\hat{P}(b) = 2^{-n} \sum_{a \in \{0,1\}^n} (-1)^{\langle a,b \rangle} P(a)$ then
$$ P(x) = \sum_{b \in \{0,1\}^n} \hat{P}(b) (-1)^{\langle x,b \rangle}. $$
This is known as the Fourier expansion of $P$. To relate this to your expansion, notice that
$$ (-1)^{\langle x,b \rangle} = \prod_{i\colon b_i=1} (-1)^{x_i} = \prod_{i\colon b_i=1} (1-2x_i). $$
It is now an exercise to relate the coefficients $\hat{P}(b)$ to the coefficients $c_b$ you are interested in.


Proving that the scramble of a regular language is context-free For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator $\operatorname {SCRAMBLE}$ such that
  $$\operatorname {SCRAMBLE}(w):=\{t\mid t\sim w\}, $$
  and for a language $A$,
  $$\operatorname {SCRAMBLE}(A):=\{t\mid t\sim w, \exists w\in A\}.$$
  Prove that: given an alphabet $\Sigma:=\{0,1\}$, for any regular language $L$, $\operatorname {SCRAMBLE}(L)$ is a context-free language.

I have tried to use the pumping lemma of regular language to show that it satisfies the pumping lemma of context-free language after the $\operatorname {SCRAMBLE}$ operation, but I failed to find the pumping substring of $\operatorname {SCRAMBLE}(L)$.
I have also tried PDA construction but to no avail. Can anyone help me with it? Any answer or hint will be appreciated. Thanks in advance.

First, two remarks. When $L = (01)^*$, we have $\newcommand{\scramble}{\mathrm{SCRAMBLE}}\scramble(L) \cap 0^*1^* = \{ 0^n 1^n : n \geq 0 \}$, and this shows that we can't expect $\scramble(L)$ to be regular.

Second, when $L=(012)^*$, we have $\scramble(L) \cap 0^*1^*2^* = \{ 0^n 1^n 2^n : n \geq 0 \}$. This shows that it's important that the alphabet have only two symbols.

Now for the proof. It is actually enough to assume that $L$ is context-free (and not necessarily regular). For a word $w$, let $p(w) = (\#_0(w),\#_1(w))$, and define $P(L) = \{ p(w) : w \in L \}$. Parikh's theorem states that $P(L)$ is a semilinear set, that is, a finite union of sets of the form
$$
x + \sum_{i=1}^m \mathbb{N} y_i,
$$
where $x,y_1,\ldots,y_m \in \mathbb{N}^2$. It is thus enough to show that for every linear set $S$, the language $L(S)$ of words $w$ such that $p(w)$ belongs to $S$ is context-free.

A pushdown automaton accepting $L(S)$ proceeds as follows. We will assume for simplicity that $x = (0,0)$; for general $x = (x_0,x_1)$, the PDA will ignore the first $x_0$ zeroes and $x_1$ ones, but will only accept if these actually appear.

When the PDA starts running, it guesses a mode $i \in \{1,\ldots,m\}$. When it reads $0$, it pushes it to the stack. Meanwhile, it keeps track of the number of $1$s it has read. Once it has read $(y_i)_1$ of them, it removes $(y_i)_0$ zeroes from the stack (pushing, if necessary, "negative" $0$s which will get cancelled later with actual $0$s). Then it guesses another mode $i \in \{1,\ldots,m\}$ (possibly the same one).

Upon reaching the end of input, the automaton verifies that it hasn't read any $1$s in its current phase, and that the stack is empty. This completes the construction. We leave it to the reader to prove that it actually works.


Concorde time efficiency What is the efficiency of Concorde TSP solver program. And is it have any weaknesses? I build my own exact solver and I want to compare it to Concorde. What would be the best way to do this?

In the paper "Evolving L-Systems as an intelligent design approach to find classes of difficult-to-solve Traveling Salesman Problem instances" by Farhan Ahammed and Pablo Moscato, the authors show how to build instances which causes Concorde to run in its worst-case time.

So, you may compare your solver with Concorde on instances generated that way, besides comparing on randomly generated instances and/or specific test-case instances.

Here is the paper's abstract:

  The technique of computationally analysing a program by searching for instances which causes the program to run in its worst-case time is examined. Concorde [2], the state-of-the-art Traveling Salesperson Problem (TSP) solver, is the program used to test our approach. We seed our evolutionary approach with a fractal instance of the TSP, defined by a Lindenmayer system at a fixed order. The evolutionary algorithm produced modifications to the L-System rules such that the instances of the modified L-System become increasingly much harder for Concorde to solve to optimality. In some cases, while still having the same size, the evolved instances required a computation time which was 30,000 times greater than what was needed to solve the original instance that seeded the search. The success of this case study shows the potential of Evolutionary Search to provide new test-case scenarios for algorithms and their software implementations.


Uniform random number generation from random bits I need to generate random number in a given interval using random bits. For example, If I want to generate a random number between 1 to 6, inclusive, I can concatenate three random bits which gives me a possible range of 000 to 111 (0 to 7), inclusive. My intuition says after concatenating 3 random bits, if the result falls between 000 and 101, inclusive, I can just return that number plus 1 (which essentially gives me a number between 1 and 6, inclusive). If I get 110 or 111 (6 or 7) after concatenating 3 random bits, I can retry again until I the number generated is in my desired range. How can I prove (or disprove) that the number I returned is indeed random?

First we need reduce our rand(from, to) function just to rand(n) = returns uniformly random number from [0, n); and later we will be able construct original function as rand(from, to) = rand(to - from) + to.

  $rand(n)=$

  Take $k$ random bits such where $n \le 2 ^ k$ (actually we can choose any $k$ that satisfy this condition, but in practice make sense to choose minimal among all possible $k$) and interpret this sequence as binary integer $r$.
  If $r < n$ return $r$ else go to step 1.

Now let's calculate probability that some number $r$ will be choosen:

Probability that algorithm will stop after one iteration is $\frac{n}{m}$, probability that we will reach 2nd iteration is $\frac{m-n}{m}$; more generally probability that algorithm will reach $step$ interation is $Pr(step) = (\frac{m-n}{m}) ^ {step - 1}$.
Probabilities that algorithm will return some $r$ on 1st iteration:

$
Pr(0) = \frac{1}{m}\\
Pr(1) = \frac{1}{m}\\
Pr(2) = \frac{1}{m}\\
...\\
Pr(n - 1) = \frac{1}{m}\\
$

Probabilities that algorithm will return some $r$ on 2nd iteration:

$
Pr(0) = \frac{m-n}{m}*\frac{1}{m}\\
Pr(1) = \frac{m-n}{m}*\frac{1}{m}\\
Pr(2) = \frac{m-n}{m}*\frac{1}{m}\\
...\\
Pr(n - 1) = \frac{m-n}{m}*\frac{1}{m}\\
$

Probabilities that algorithm will return some $r$ on $step$ iteration:

$
Pr(0) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
Pr(1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
Pr(2) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
...\\
Pr(n - 1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
$

And probability that some $r$ will be choosen (after any number of interations) will be the same regardless of $r$:

$
Pr(r) = \frac{1}{m} + \frac{m-n}{m}*\frac{1}{m} + ... + (\frac{m-n}{m}) ^ s*\frac{1}{m} + ... = \frac{1}{m}\sum\limits_{s=0}^\infty(\frac{m-n}{m}) ^ s = \frac{1}{m} \frac{1}{1 - \frac{m - n}{m}} = \frac{1}{m} \frac{m}{n} = \frac{1}{n}
$


What is the fastest algorithm for finding all shortest paths in a sparse graph? In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall which is $O(V^3)$ but very fast per iteration?

How about if the graph is weighted?

Since this is an unweighted graph, you could run a Breadth First Search (BFS) from every vertex $v$ in the graph. Each run of BFS gives you the shortest distances (and paths) from the starting vertex to every other vertex. Time complexity for one BFS is $O(V + E) = O(V)$ since $E = O(V)$ in your sparse graph. Running it $V$ times gives you a $O(V^2)$ time complexity.

For a weighted directed graph, the Johnson's algorithm as suggested by Yuval is the fastest for sparse graphs. It takes $O(V^2\log V + VE)$ which in your case turns out to be $O(V^2\log V)$. For a weighted undirected graph, you could either run Dijkstra's algorithm from each node, or replace each undirected edge with two opposite directed edges and run the Johnson's algorithm. Both these will give the same aysmptotic times as Johnson's algorithm above for your sparse case. Also note that the BFS approach I mention above works for both directed and undirected graphs.


Sliding Window Dictionary String Matching Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every pattern in $\Pi$ is contained in the substring $s[i:i+k]$.

Can this be solved in linear- or near-linear-time? It can of course be solved in quadratic time $O(|s| |\Pi| + \sum |\pi_i|)$ using KMP or Aho-Corasick plus post-processing.

The motivation for this problem is finding matches for a topic (represented by the set of patterns) in a text. In that context it actually makes sense to require the matches to be non-overlapping so I'm also interested in that case, but it might be easier to start with the relaxed version.

I would also be interested in generalizations of the problem that allow for approximate matches of some kind, eg, only requiring a threshold on the size of the subset of matching patterns, allowing matches within given edit distance, or something using hidden Markov models or general probabilistic graphical models. I would be surprised if any such generalization can be solved in subquadratic time though.

The set of all $k$-length strings that contain every pattern in $\Pi$ is regular; call it $L$.  (It is $(\Sigma^* \pi_1 \Sigma^* \cap \dots \cap \Sigma^* \pi_m \Sigma^*) \cap \Sigma^k$.)  From this, you can form a nondeterministic finite-state automaton (NFA) that recognizes $\Sigma^* L$.  Next, convert this to a DFA.  Finally, run the DFA across the input string $s$.  You can then obtain all locations in the string where the DFA is in an accepting state; each such location  is an index $i+k$ so that $s[i:i+k]$ matches all patterns in $\Pi$.

The running time will be linear in $|s|$ and the size of the DFA.  I expect the size of the DFA to be exponential in $\Pi$ and $k$, but independent of $|s|$.  So, if you only care about the dependence on $|s|$, this algorithm might meet your requirements.  If you additionally care about the dependence on $\Pi$ and/or $k$, I do not expect this will meet your requirements.


What is the Number of epochs with no improvement after which training will be stopped.? I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check that model is overfitted or not . What should be the number of epochs we will se that with no improvement after which training will be stopped . Should I see after 2, 3 or which number ?

The number of iterations with no improvement is a hyperparameter. Scikit-learn has a default value of 10 in the MLPClassifier but of course you can select one depending on your problem. You can also do a grid search over all your model's hyperparameters.
Another advice I would give is that you could first train the model experimentally for a lot of epochs. If you see it getting stuck for a lot of iterations and then increasing after a halt, then it's better to set a higher value. On the other hand if after a lot of time you don't see it improving you should set the max number of iterations with no improvement to a smaller value.


Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$? I have a book that proves the halting problem with this simple statement:

$$
A_\text{TM} \le_m  \text{HALTING} \le_m \text{HALTING}^\varepsilon
$$

It states that halting problem reduces to the language consisting of $\langle M, \omega \rangle$ for which a Turing machine $M$ accepts $\omega$ is undecidable.

What does this mean? What does the notation $\le_m$ indicate?

The symbol $\leq_m$ means many-one reducible, contrast to reductions such as turing reducible (denoted by $\leq_T$) and one-one reducible (denoted $\leq_1$).

A many-one reduction from $L$ to $L′$ (given an alphabet $\Sigma$) is a (computable) function $f:\Sigma^* \to \Sigma^*$ such that for every $w \in \Sigma^*$, we have that $w \in L$ if and only if $f(w) \in L′$.  The "many-one" means that we allow $f(w) = f(w′)$ (it does not have to be injective).  In your setting, it basically means that you can transform an input to $A_{TM}$ to $HALTING$ such that $A_{TM}$ accepts an input $w$ if and only if $HALTING$ accepts the transformed input $f(w)$.


Trying to detect recurring events at certain intervals, e.g. daily, weeekly, monthly, annually I don't have much experience with ML but am looking for some guidance on where I should start.

I have timestamp data mapped to a certain category, e.g. travel, food, groceries, etc.

Judging by some other posts and answers, would it be correct to break the data into these intervals (day, week, month, year) and then try to detect patterns across the intervals?  Are there any particular approaches or algorithms I should investigate first?  Thanks!

Given an event type and a sequence of times at which it has occurred, there are several ways to check whether it seems to recur periodically.

One simple approach is to look at the interarrival times (the time between each occurrence and the previous occurrence), and histogram those; if it is periodic, you'll see a sharp peak in the histogram.

Another approach is to use autocorrelation to detect periodicity.  See, e.g., https://en.wikipedia.org/wiki/Autocorrelation.  The Fourier transform can be useful here.


Estimating the time until we obtain five-in-a-row? Consider the following random process.  We have a $10\times 10$ grid.  At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker in that grid cell.  As soon as we have five contiguous markers in a line (in a row, column, or diagonal), we stop.

I'm given a grid containing some markers in some positions, and I'd like to estimate how long until the process stops if we start from that configuration (i.e., the number of additional time steps until five-in-a-line occurs).  I would be happy with any reasonable metric for that: e.g., the expected time until it stops, or the value $t$ such that there's a probability $0.5$ that the process will stop in $\le t$ time steps.  I'd be happy with an estimate of any such metric.

Is there any efficient algorithm to estimate this metric, given a configuration where some markers have already been placed?  I'm hoping for something faster than random simulation (repeatedly simulating the process and computing an estimate based upon the resulting empirical distribution).

Just for fun, I coded this up in Mathematica. I started with a $10 \times 10$ matrix initialized to all zeros. I then considered two processes throwing darts in the cells: (1)  a cell is chosen uniformly and independently at random from the set of all cells, and (2) a cell is chosen uniformly and independently at random from the set of all empty cells. When a  dart hits a cell, the value of that cell is set to $1$. A five-in-a-row can appear on a row, column, the diagonal, or on the antidiagonal.

For both processes, I ran $N = 20000$ simulations. Rounded up to the nearest integer, for process (1) we need $65$ dart throws on average to obtain a five-in-a-row. For process (2), the same number was $47$.

This is not exactly what you were asking for, but maybe you can at least compare the numbers you get with mine.


Default scan order in SCAN and LOOK disk scheduling algorithms I've been learning various disk scheduling algorithms in Operating systems. I wanted to know if there was any default scan order in SCAN, C-SCAN, LOOK and C-LOOK algorithms, like towards higher cylinders or lower cylinders ? Or are they OS-specific ?

There is no specific order. In SCAN, C-SCAN, LOOK and C-LOOK we have to start moving towards the closest cylinders as in SSTF or you can start moving towards a direction in which there are less number of requests and then move towards the other


Guessing the smallest unique positive integer Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the players made their moves, computer outputs a name of winner – who submitted the lowest unique number.

How do you think, what is the best strategy for this game?

There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. This gives equations which for three players have a closed form solution: you choose the integer $i$ with probability

$$ 0.839286 \cdot (0.543689)^{\textstyle i}$$

where 0.543689 is the solution of $x^3 + x^2 + x = 1$.

For $k$ players, if $k \geq 4$, the equations can still be derived, but they appear to have no closed form solution. However, in the optimal strategy the probability of playing a number larger than $k$ is very small, so an explicit nearly-optimal strategy can be found by solving the equations numerically.


Write Serialization for Cache Coherence in the presence of Store Buffers One of the requirements for a coherent memory system is write serialization - "two writes to address X by any two processors are observed in the same order by all processors". I am not sure how this condition would be met when the CPU cores have a store buffer into which stores are retired before updating the memory hierarchy.

Suppose Cores A and B both retire a store to address X (which is cached by both A and B), and these stores are now in the store buffers and are yet to update the cache. Now loads from address X on both cores A and B could retire after obtaining the load value from the store buffers ie loads from X on core A see value written by the store to X on core A, similarly, loads from X on core B see value written by the store to X on core B. Say now, the store to X from core A sends a read-upgrade message to core B. What happens next on core B? After coherence transactions have completed for A, the store to X on B updates the local cache. After the stores to X from A and B have completed the final value of X is the store by B.

Above, the order for values seen by A for X are write by A followed by the write to B. But this doesn't seem to be the order seen by B. So the question is how is write serialization enforced when store buffers are being used?

(This is based on my understand of the various material I have read and would appreciate it if anyone can point to sources that discuss these issues in detail)

From a coherence perspective, I think your example is coherent.  All processors believe that the write and read from A happened first, then the write and read from B happened later.

From a consistency standpoint you need to be more careful.  (Consistency is the global ordering of memory operations to different addresses.) The way consistency is handled in practice is that the store buffer sits before retirement, not after.  The store buffer acts as a little coherent cache for the speculative memory state.  A store instruction is not permitted to retire until its processor has acquired write ownership of the appropriate cache line.

The store buffer needs to be aware of all the coherence traffic reaching the cache.  If a speculative load gets its value from the store buffer, but the corresponding memory location is invalidated before the load retires, the load (and everything following it in the reorder-buffer) needs to be squashed and reexecuted.


Is there a non-brute force algorithm for Eulerization of graphs? Given some undirected, unweighted, connected, and potentially parallel-edged graph $G$, an Euler circuit may be constructed iff every vertex in $G$ has an even degree.

In graphs with two or more vertices of odd degree (there may only be multiples of two), one must "Eulerize" the graph, connecting the odd vertices with additional edges through other vertices if necessary.

The optimal case for Eulerization is with the construction of only $n/2$ edges, where $n$ is the number of odd degree vertices, but this can only be the case if each odd vertex has an adjacent partner, thus allowing us to connect both vertices with one edge and making them both even.

That being said, most graphs will require more than $n/2$ edges. As humans, we tend to Eulerize graphs by always choosing each pair of odd vertices that are adjacent to one another, and then using trial and error for the rest. However, this does not always work.

For instance, in the following graph, choosing to add an edge between the pair of adjacent odd vertices, $1\leftrightarrow 2$ and using $5$ edges to connect $3\leftrightarrow 4$ results in an Eulerization that costs $6$ edges. However, choosing to instead connect $1\leftrightarrow 4$ and $2\leftrightarrow 3$ yields an Eulerization that costs $5$ edges, even though it did not use the adjacent odd vertices to its advantage.

I know for sure that this problem is solvable, at least by brute force, because the number of pairs of odd vertices which should be connected with some number of edges is finite; specifically, there are $2^{n/2} \Gamma(\frac{n+1}{2})/\sqrt{\pi}$ (Mathematica said so) possible sets of pairs of odd vertices to connect. It's possible to go through each one, linking up each vertex to its partner (finding the shortest path between the two vertices in an undirected graph is probably a challenge within itself, which Wikipedia fails to give a time complexity for).

In the end, the whole deal probably runs in polynomial times exponential times factorial time, which is pretty nasty. I've done some basic research into whether there are algorithms which Eulerize paths, but can't seem to find any.

Mathematica code for graphic:

GraphPlot[
  {1 -> 2, 2 -> 5, 5 -> 3, 3 -> 6, 6 -> 3, 6 -> 7, 7 -> 6, 2 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 4, 4 -> 11, 11 -> 4, 11 -> 12, 12 -> 1, 1 -> 12},
  VertexRenderingFunction ->
    (If[#2 < 5,
        Text[Style[#2, Large], #1, Background -> Yellow], Null] &)]

Consider the Chinese Postman Problem on undirected graphs: Given an undirected graph $G$, find the shortest circuit of the graph that travels every edge atleast once. Now, if $G$ is Eulerian, then the Euler circuit is the shortest such circuit. If not, some edges will be traveled more than once. In other words, some edges will be duplicated, and the circuit will be Eulerian on the graph with these extra edges.

Now, for obtaining the shortest circuit, the edge duplication has to be minimized. This is the same as your problem. You need to find a new graph $H$ which has all the edges of $G$, and a few extra parallel edges - as few extra edges as possible - so that $H$ is Eulerian. Each extra edge in $H$ corresponds to the fact that its corresponding parallel edge in $G$ is visited again in a shortest complete circuit of $G$. In other words, the optimum (minimal) "eulerization" is equivalent to the Chinese Postman problem. For a better expressed explanation of this, refer to Section 4 (Chinese Postman Problem) and Definition 11 (Eulerization, Minimal Eulerization) of these notes. Fortunately, this is solvable in polynomial time for undirected graphs.

For the Chinese Postman problem, Wikipedia has one solution. I describe another algorithm from Steven Skiena's The Algorithm Design Manual [1]:

Find the shortest paths between each pair of odd-degree vertices in $G$: $O(n^3)$.
Finding the best set of shortest paths to add to $G$ reduces to identifying the minimum-weight perfect matching in a special graph $G' = (V', E')$. The vertices $V'$ of $G'$ correspond the odd-degree vertices of $G$, with the weight of the edge $(i, j) \in E'$ defined to be the length of the shortest path from $i$ to $j$ in $G$. Note that a matching is a set of pairwise non-adjacent edges. Thus, each edge in the matching connects two vertices, and no vertex is part of two matching (a matched vertex is matched with exactly one other vertex). A perfect matching is a matching where each vertex has been matched. Now, for each matching edge obtained, you can consider the two end vertices to be paired up. The constraint of "minimum-weight" when obtaining the matching ensures that the total weight of each edge in the matching is as small as possible. Since the weight of each edge is the distance between its end points in $G$, which in turn is the number of edges that need to be duplicated when the end points are paired up - this condition ensures that globally, the total number of edge duplication is minimized. Obtaining such a matching is described in [2], and is based on the Blossom algorithm. An efficient implementation is described by Kolmogorov [3] (preprint copy) with an implementation here. The implementation is an improvement over the ideas and review presented by Cook and Rohe in [4]. This can be done $O(n^3)$.
Once the matching is obtained, each odd vertex is paired with another odd vertex. This is the pairing that you want.

Thus, you can obtain the optimal "Eulerization" in time polynomial (cubic) in the number of odd-vertices. This is based on a paper by Edmonds and Johnson [2] which solves the Chinese postman problem.

References:

Steven S. Skiena. The Algorithm Design Manual. ISBN: 978-1-84800-069-8 e-ISBN: 978-1-84800-070-4 and DOI: 10.1007/978-1-84800-070-4
J. Edmonds and E. Johnson. Matching, Euler tours, and the Chinese postman.
Mathematical Programming, 5:88–124, 1973.
Vladimir Kolmogorov. Blossom V: A new implementation of a minimum cost perfect matching algorithm. In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
W. Cook and A. Rohe. Computing minimum-weight perfect matchings. INFORMS Journal on Computing, 11(2):138–148, February 1999.


Algorithm to find and add prime numbers How would one write code to find and add the prime numbers between 4 and 5 million? I need a code that can find all such numbers, and then add them together. I'm not too keen on computer science, so I wouldn't know even where to begin. (I'm a math major).

Any help is appreciated. Also any advice on how to compile and run the code would be helpful.

PS I know the answer is one of the following: 294185048443, 303141243820, 294095048847, 277319432363, 453190021165, or 210569014847.


Regular set of the "does not contain" kind Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses
$L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$?
Well, the part that states that w must end with 00 is easy and I (think I) managed to find the regular set for it. But I can't modify it so that w won't contain 11.
I didn't find many articles about this subject on the internet, and the ones I did didn't help me much in this "does not contain" kind of problem. So it'd help a lot if you guys could mention some articles on regular sets to me.

If a string doesn't contain $11$, then any $1$ is followed by $0$, unless it is the final $1$ in the string. Therefore you can break the string up into pieces of the forms $0,10,1$, the last one appearing only at the very end. This leads to the following regular expression for the set of binary strings excluding $11$:
$$ (0+10)^*(\epsilon+1). $$
If we furthermore want the string to end with $0$, then we have no terminal $1$. On the other hand, we also want to disallow the empty string. Altogether, we get
$$ (0+10)^+. $$
A similar case analysis leads to a regular expression for your language. Details left to you.


Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow? I stumbled across this question and answer (source):

  Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear
  time algorithm to determine whether the solution does indeed give a maximum flow.

  Answer: First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of
  each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|))
  and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting
  path would mean the solution is not a maximum flow.

Does this mean that the Ford-Fulkerson algorithm will reach max flow if given any valid flow as input, instead of initializing all edges to 0 at the start?

Yes. If the flow is not maximum, then there is an augmenting path. If there's an augmenting path, Ford-Fulkerson will find it (and continue to find them until the flow is maximum). Starting from a different initial flow does not change this.


Theorem Prover for complexity theoretic reductions Can complexity theoretic reductions that lead to proofs of say NP completeness be formalized using an existing theorem prover such as Coq?

If so, can you provide an outline of how to formalize a simple reduction argument? I’d also appreciate pointers to the literature.

This is certainly possible, and the language of higher order functions makes this quite nice. If you're doing a Turing/Cook reduction, you can basically just write a function that takes an oracle as a parameter.

For example, to show that Graph Coloring is NP-hard, you could write something like this (pardon my terrible Coq-like pseudocode)

Theorem reduction:
  (forall (k:Nat) (g:Graph), Decidable (Coloring g))
  -> (forall (f:BoolFormula), Decidable (Model f))

What gets tricky is proving that your reductions are polynomial-time. There are ways to do this, such as with a time-tracking monad. This example verifies the time complexity of a sorting algorithm, and gives some hints as to how to model this. Basically, for whatever operation you're counting as $O(1)$, you require that it be performed in the monad, as well as calls to your oracle. Then you write a proof of some polynomial bound on the number of operations performed in the monad (which can keep track of them by encapsulating state).


Inferring refinement types At work I’ve been tasked with inferring some type information about a dynamic language. I rewrite sequences of statements into nested let expressions, like so:

return x; Z            =>  x
var x; Z               =>  let x = undefined in Z
x = y; Z               =>  let x = y in Z
if x then T else F; Z  =>  if x then { T; Z } else { F; Z }

Since I’m starting from general type information and trying to deduce more specific types, the natural choice is refinement types. For example, the conditional operator returns a union of the types of its true and false branches. In simple cases, it works very well.

I ran into a snag, however, when trying to infer the type of the following:

function g(f) {
  var x;
  x = f(3);
  return f(x);
}

Which is rewritten to:

\f.
  let x = undefined in
    let x = f 3 in
      f x

HM would infer $\mathtt{f} : \mathtt{Int} \to \mathtt{Int}$ and consequently $\mathtt{g} : (\mathtt{Int} \to \mathtt{Int}) \to \mathtt{Int}$. The actual type I want to be able to infer is:

$$\mathtt{g} : \forall \tau_1 \tau_2. \:(\mathtt{Int} \to \tau_1 \land \tau_1 \to \tau_2) \to \tau_2$$

I’m already using functional dependencies to resolve the type of an overloaded + operator, so I figured it was a natural choice to use them to resolve the type of f within g. That is, the types of f in all its applications together uniquely determine the type of g. However, as it turns out, fundeps don’t lend themselves terribly well to variable numbers of source types.

Anyway, the interplay of polymorphism and refinement typing is problematic. So is there a better approach I’m missing? I’m currently digesting “Refinement Types for ML” and would appreciate more literature or other pointers.

You've stumbled on the fact that inference of static invariants for higher-order languages is quite difficult in practice, in addition to being undecidable in theory. I'm not sure what the definitive answer to your question is, but note several things:

Polymorphism and refinement types behave poorly together, as you have noted, in particular the notion of most general type is lost. A consequence of this is that analyses based on refinement types in the presence of polymorphism may need to chose between whole-program analysis (as opposed to compositional analysis) and the use of heuristics to decide which type you want to assign to your program.
There is a strong relationship between inferring refinement types and:

Computing the abstract interpretation of your program
Computing loop invariants in an imperative language.

With this in mind, here are a few disorganized references on the inference of refinement types. Note that there are many differing flavors of refinement types: I tend to be more interested in refinements of inductive datatypes, so this list may be skewed in that direction.

Start with the classics: Relational Abstract Interpretation of Higher-Order Functional Programs by Cousot & Cousot. This explains how to extend abstract interpretation to higher-order programs using relational semantics.
Liquid Types by Rhondon, Kawaguchi and Jhala. This is very evolved work, that combines HM and a type of predicate refinement to infer security annotations (array bound checks for instance) for ML style programs. The inference proceeds in 2 steps; the first is HM inference of type annotations, which guide the choice of refinements to perform.
I should probably also mention the work by Fournet, Swarmy, Chen, Strub... on $F^*$, an extension of $F^\#$ which seems similar to the liquid types approach, but with the goal of verifying cryptographic protocols and algorithms for distributed computing. I'm not sure how much published work there is on the inference of annotations in this case.
There is a nice paper by Chin and Khoo on inference of a specific kind of refinement types: types with size annotations.
The ATS programming language is a system which allows various refinements and provides facilities for writing programs with them. However the annotations may be arbitrarily complex (and thus undecidable) and therefore may require user interaction. I believe that there is a form of inference for these types, I'm not sure which article to recommend however.
Last, but not least The Cartesian Product Algorithm, by Ole Agesen. While not mentioning refinement types explicitly, this seems to be the work closest to solving the problem you seem to have. Don't be fooled by the mention of parametric polymorphism in the abstract: they look to infer concrete types, which are just tuples of possible atomic types. Emphasis is given on efficiency. I recommend reading this article first to see if it solves your problem.

Side note: type inference in the presence of intersection types can be very undecidable: in the simplest form, $\lambda$-terms with intersection type are exactly the strongly normalizing terms. Tread softly around them :)


How to represent OOP concepts in algorithms in a standard way? I have usually been using the Cormen algorithm format to teach some introductory courses in Programming. I mean something like this:

TreeSearch(k,n)
1. if x==NIL or k==x.key
2.     return x
3. if k<x.key
4.     return TreeSearch(k.left,n)
5. else return TreeSearch(k.right,n)

Actually I have not agree with a couple of lecturers in my institution that they insist to put the type of the variable that they are using in the algorithm. I mean, to do that, will it not be to make a bias toward the programming language and not to focus on the algorithm? For example what would happen if the student grab other programming language, like R or Python, that really do not care about the type of variable.

The other issue that I have is how to represent OOP algorithms in a nice algorithmic way. For example when I make a constructor should I put something like:

Class: car
Attributes: wheels
Constructor car()

or something like

Class: car
Function car()

also when I come to the part of inheritance, one of my colleages put the word super() to define inheritance in an algorithmic way, but again I think that is too Java-way to do this part. Usually they teach in that way because the practical part is made in Java, but again I think that the algorithm should be more freely, directly towards the logic, and not to an specific programming language.

Does anybody knows some standard to represent algorithms for OOP?

Generally there is no unified to present algorithms. Each researcher should use/introduce notation with which he is most comfortable with.

If you look at some algorithmic books writers have different approach to this manner.

For instance:

CLRS book gives no types for functions arguments
Tel's "Introduction to distributed algorithms" gives types
Sedgewick's "Algorithms" gives code in Java (which is not very good solution IMO)

On the other hand any object can be represented as tuple of base data types, eg binary tree can be presented as:

(5,(3,(1,NIL,NIL),(4,NIL,NIL)),(6, NIL, NIL))

Which might corresponds to

5
|\
3 6
|\
1 4

But the first notation is not very readable, so its easier to relate so such tuple as Node.

Additionally algorithms representation depends on field on which they are presented. If you assume that algorithm should be more or less translatable from pseudo code to actual code then you should introduce hints and notation to your algorithm presentation which allow this. But if that is not the case and you want to focus mainly on algorithm idea, or some other complexity value then, time then mathematical notation might become handy. In the end as previously stated it depends on needs.

If you look closely on various papers and books you can see that types of arguments are either obvious from context, or explained in algorithm description.

I suggest you to get familiar with $\LaTeX$ Algorithms module.