Oblivious RAM write protection I'm trying to understand how oblivious RAM works, specifically
path oblivious RAM. While I understand how this technique offers protection when reading data - multiple randomly distributed reads obfuscate the access pattern of the data actually requested - I can't tell how that helps protect against an attacker who is interested in the users write access.

Surely multiple randomly addressed writes would potentially overwrite critical data that is later required by the program. Similarly, while batching the writes would stop an attacker knowing exactly which addresses were written to at a given time, this would not stop them discovering which addresses were written to, nor the presence of those writes.

Surely multiple randomly addressed writes would potentially overwrite critical data...

Nope.  The oblivious RAM data structures take care to ensure that, when doing reads and writes at random locations, they don't mess up the data.  For instance, if doing an extra write, then they make sure to write the same value that was already there (except in encrypted form), so that it doesn't change what value is stored there.

  batching the writes would stop an attacker knowing exactly which addresses were written to at a given time

But the attacker would still know which set of addresses were written, which is leakage of partial information.  Oblivious RAM aims to eliminate even this partial leak.  So oblivious RAM achieves a stronger property than batching could ever provide.


Given a mechanical assembly as a graph, how to find an upper bound on number of assembly paths The rules are that you can only build from an existing part, so in the example below, B is the only option for the first move = A.

A mechanical assembly might be represented as follows:

  E
  |
  C
  |
A-B
  |
  D
  |
  F

Where the valid assembly paths when starting from A are:

A, B, C, E, D, F
A, B, C, D, E, F
A, B, C, D, F, E
A, B, D, F, C, E
A, B, D, C, F, E
A, B, D, C, E, F

This is a fairly simple example, but providing an upper bound for an arbitrary assembly is difficult since it's related to the "connectivity" of the parts.

n! would be an absolute upper bound I guess, but I'm hopping to find something a little better.

I've also looked at representing the graph with the parts (A, B, C, etc) as the edges and doing Kirchhoff's theorem, but that doesn't work for sparsely connected graphs like the example above.

Any information about the problem would help.  I'm not sure if there's a formal description of this type of problem or not.

Your question is quite open-ended, in that you have not specified how accurate the upper bound should be, nor how efficient the algorithm should be. There is certainly a trade-off between the run-time and the accuracy.

Ways to get an exact answer:

Naive brute force - I guess you know what this means (very slow)
Observe that it is easy to calculate the number of ways of the graph is a tree (start from the leaves, and when they join up, just count number of ways of joining the two branches

ie. #ways = #ways(branch A) * #ways(branch B) * {#nodes(branch A) + #nodes(branch B)} Choose #nodes(branch A)

Thus iterate over all possible trees, and sum up the number of ways of assembling the tree.

This method is faster than a naive brute force, but it is still brute forcing on all the trees

For an upper bound:

$n!$ - very quick but not accurate
Using the same observation as before (easy to calculate number of ways for a tree), you can use the quick method for all subtrees/leaves off the main component. Then join it all up.

For example, suppose the main component connected to the root has $a_0$ nodes, then you have two subtrees hanging off that main component with $a_1$ and $a_2$ nodes, each with $b_1$ and $b_2$ ways of assembling them respectively.

Then, letting $b_0$ = $a_0!$ (an upper bound on the main component), an upper bound on the whole graph is $b_0b_1b_2\frac{(a_0a_1a_2)!}{a_0!a_1!a_2!}$.

This method is very quick, but although it is a much better upper bound than $n!$, it can still be very far off the exact answer.
A refinement to either of the above methods can be made, by considering the earliest that a particular node can appear in the sequence. Basically, it is a way of counting such that, for example, since you know $B$ can never be the 1st in the sequence, and $C$ is 3rd or later, etc., you can count in such a way to avoid that possibility.

For example, in the above example, first consider that there are 2 ways of ordering $E$, $F$, in places 4-6, call this sequence $s_1$. Then there are 2 ways of ordering $C$, $D$ in places 3-6 (sequence $s_2$). So you can now merge the two sequences. Because the intersection of their possible places is 4-6, you know that in place 4-6, there is one element from $s_2$ and two elements from $s_1$. Thus, the number of ways of merging them is $\frac{3!}{2!1!}=3$, thus the merger of the two sequences results in a sequence with $2\times 2 \times 3=12$ ways, in a possible range of places ranked 3-6. After merging with a subsequence consisting of $B$ and a subsequence consisting of just $A$, you have an upper bound of $12$ ways of assembling it.
Further refinement may also be made by considering the latest a node can appear (eg. $C$ and $D$ cannot be in place 6. Thus, when merging sequences $s_1$ and $s_2$, an even better upper bound is $2\times 2 \times \frac{2!}{1!1!}=8$ ways.

There may be other ways I cannot think of. But each refinement will add complexity, and running time to your algorithm.

I am unsure if there exists an efficient algorithm for finding the exact answer (in $P$ time).


How undecidable is it whether a given Turing machine runs in polynomial time? The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at  cs.SE and cstheory.SE. However, what is different is a footnote, which highlights that proving both $\mathsf{R}$-hardness and $\mathsf{coR}$-hardness seems to be new:

  1The undecidability of PTime seems to be folklore, but non-semi-decidability seems to be new, even though semi-decidability is a natural property here.

But I want to ignore the question whether this observation is new. What interests me is what is known about the degree of undecidability of PTime. For example, is computation in the limit powerful enough to decide PTime? Are there better lower bounds than $\mathsf{R}\cup\mathsf{coR}$ for the difficulty of PTime?

Note: I denote the problem to decide "whether a given Turing machine runs in polynomial time" as PTime here. I know that this is incorrect, because PTime is a class of languages and not a class of Turing machines. However, I found this misuse of terminology convenient for this question.

The answer is $\bf 0''$ (and so in particular computation in the limit - which corresponds to $\le_T\bf 0'$ - is not enough). And this stronger result is also folklore (I was assigned it as an exercise way back when).

As an upper bound we just check quantifier complexity: $\Phi_e$ runs in polynomial time iff there exists some polynomial $p$ such that for every input $n$ we have $\Phi_e(n)[p(\vert n\vert)]\downarrow$ (that final clause only uses bounded quantifiers). So running in polynomial time is a $\Sigma^0_2$ property.

Now we just need to show optimality. We'll actually show a bit more: not just that the Turing degree is $\bf 0''$, but that the set is $\Sigma^0_2$-complete. Supposing $$A=\{x:\exists y\forall z\theta(x,y,z)\}$$ (with $\theta\in\Delta^0_0$) is any other $\Sigma^0_2$ set, we want to reduce $A$ to the set of programs running in polynomial time.

So fix an instance $i$. We'll say $m$ is $s$-bad for $i$ if $m<s$ and there is some $n<s$ such that $\neg\theta(i,m,n)$. Let $t_i(s)$ be the least $m$ which is not $s$-bad for $i$. Now we'll whip up a stupid program $\Phi_{e_i}$ as follows: on input $s$, $\Phi_{e_i}(s)$ runs for ${\vert s\vert}^{t_i(s)}$-many steps and then halts and outputs $0$. The point is that if $i\in A$ then $t_i(s)$ stabilizes and so $\Phi_{e_i}$ runs in polynomial time, and otherwise $\Phi_{e_i}$ does not run in polynomial time.

Now the map $\mu: i\mapsto e_i$ is computable, so we get a many-one reduction of $A$ to our set.

As a quick comment, note that we only used one property of polynomial time above: that there is no biggest polynomial time bound. This let us keep pushing up the runtime bit by bit (each time $t_i(s)$ goes up) while preserving the possibility of still running in polynomial time. By contrast, "halts within seven steps on all inputs" (say) is merely $\Pi^0_1$-complete. Basically, whenever we have a concrete resource-bounded complexity class with no "maximal bound," being in that class will be $\Sigma^0_2$-complete. In particular, this applies to NP, EXPTIME, PSPACE, ...


What is OUTER UNION and why is it partially compatible I am trying to understand how a OUTER UNION $∪^✳$ works, and why it is only partially compatible.

I am aware this operation was created to take union of tuples from two relations if the relation are not type compatible (which I understand).

Examples of this operation will be great!

There are two flavors of outer union: with and without NULLs. Google search readily exibits an example for NULLs version. The cleaner version of relational algebra desn't allow NULLs, and outer union is defined via De Morgan's law:

$ X \bigcup Y = \overline {\overline X \Join \overline Y} $

Date&Darwen call this operation $\blacktriangleleft OR \blacktriangleright$.

Given

R = [A B]
     1 2
     3 4

and

S = [B C]
     4 5
     6 7

both outer join variants agree that the result projected to common column B should be {2,4,6}. This is what is called inner union -- alternative way of generalizing standard relational algebra union operator. Now the problem is finding values of attributes A and C. Next, we match the values of the "middle column" with attributes A and C trying to leverage information in the relations R and S. In case of value B=2 we don't have matching value of C. Likewise, for B=6 we don't have matching value of A. Therefore, D&D $\blacktriangleleft OR \blacktriangleright$ operator fills the blanks in

[A B C]
 1 2
 3 4 5
   6 7

with all the values from corresponding domain, while the NULL version just blurts NULLs.


The math behind converting from any base to any base without going through base 10? I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org  but I'm still not sure if I have it right. I have the converting from a larger base to a smaller base down okay because it is simply take first digit multiply by base you want add next digit repeat. My problem comes when converting from a smaller base to a larger base. When doing this they talk about how you need to convert the larger base you want into the smaller base you have. An example would be going from base 4 to base 6 you need to convert the number 6 into base 4 getting 12. You then just do the same thing as you did when you were converting from large to small. The difficulty I have with this is it seems you need to know what one number is in the other base. So I would of needed to know what 6 is in base 4. This creates a big problem in my mind because then I would need a table. Does anyone know a way of doing this in a better fashion.

I thought a base conversion would help but I can't find any that work. And from the site I found it seems to allow you to convert from base to base without going through base 10 but you first need to know how to convert the first number from base to base. That makes it kinda pointless.

Commenters are saying I need to be able to convert a letter into a number. If so I already know that. That isn't my problem however.
My problem is in order to convert a big base to a small base I need to first convert the base number I have into the base number I want. In doing this I defeat the purpose because if I have the ability to convert these bases to other bases I've already solved my problem.

Edit: I have figured out how to convert from bases less than or equal to 10 into other bases less than or equal to 10. I can also go from a base greater than 10 to any base that is 10 or less. The problem starts when converting from a base greater than 10 to another base greater than 10. Or going from a base smaller than 10 to a base greater than 10. I don't need code I just need the basic math behind it that can be applied to code.

This seems a very basic question to me, so excuse me if I lecture you a bit. The most important point for you to learn here is that a number is not its digit representation. A number is an abstract mathematical object, whereas its digit representation is a concrete thing, namely a sequence of symbols on a paper (or a sequence of bits in compute memory, or a sequence of sounds which you make when you communicate a number). What is confusing you is the fact that you never see a number but always its digit representation. So you end up thinking that the number is the representation.
Therefore, the correct question to ask is not "how do I convert from one base to another" but rather "how do I find out which number is represented by a given string of digits" and "how do I find the digit representation of a given number".
So let us produce two functions in Python, one for converting a digit representation to a number, and another for doing the opposite. Note: when we run the function Python will of course print on the screen the number it got in base 10. But this does not mean that the computer is keeping numbers in base 10 (it isn't). It is irrelevant how the computer represents the numbers.
def toDigits(n, b):
    """Convert a positive number n to its digit representation in base b."""
    digits = []
    while n > 0:
        digits.insert(0, n % b)
        n  = n // b
    return digits

def fromDigits(digits, b):
    """Compute the number given by digits in base b."""
    n = 0
    for d in digits:
        n = b * n + d
    return n

Let us test these:
>>> toDigits(42, 2)
[1, 0, 1, 0, 1, 0]
>>> toDigits(42, 3)
[1, 1, 2, 0]
>>> fromDigits([1,1,2,0],3)
42

Armed with conversion functions, your problem is solved easily:
def convertBase(digits, b, c):
    """Convert the digits representation of a number from base b to base c."""
    return toDigits(fromDigits(digits, b), c)

A test:
>>> convertBase([1,1,2,0], 3, 2)
[1, 0, 1, 0, 1, 0]

Note: we did not pass through base 10 representation! We converted the base $b$ representation to the number, and then the number to base $c$. The number was not in any representation. (Actually it was, the computer had to represent it somehow, and it did represent it using electrical signals and funky stuff that happens in chips, but certainly those were not 0's and 1's.)


Basic queries for Object Detection using deep learning I have recently started working on the Object detection using deep learning.

I have understood the basic steps of object detection are:

Input Image -> Object proposals -> Feature Extraction -> Training.

I have successfully implemented my own code up to the Object Proposal extraction. Now I want to use deep learning here from that point. For the input to deep learning I have fixed number of object proposals (i.e. 800 proposals from one image) and I need a labeled data.
For example:
I have a one class dataset. 1) Aircraft,
Images number 1-90 are aircraft.
and the above number of images have 800 aircraft.
Q: Here, I want to ask that how can I make the labels for the dataset with this configuration of class? According to the tutorials and the Matlab implemented examples I have seen, they used the images and the training labels as the input to the CNN. As I have training images I want to know how can i make training labels.

The input to the CNN network will be proposals (just a cropped regions) around 500 proposals. I want the output is to be if any of the proposals is matched as aircraft then it will appear a bounding box on the big image that this is a aircraft.

Input image.

The input to your CNN is a small cropped image, and the output will be a prediction at the label (either "airplane" or "not-airplane").  The training set needs to contain example input-output pairs.  So, you need your training set to contain many small images (of the size of a single crop), with a label indicating whether it should be classified as "airplane" or "not-airplane".

How do you do that?  You take many large images where you know where the bounding box of the airplanes in each is.  For each large image, you crop it around an airplane and add that to the training set, labelled as "airplane".  You also crop it somewhere else (in a place not intersecting any of the airplane bounding boxes) and that to the training set, labelled as "not-airplane".  You can do the letter step many times, taking many different crops.  Repeat this for many large images.  Use the resulting training set to train your neural network.


How to efficiently code Dynamic Time Warping algorithm with a locality constrain? For given two lists $[s_1, s_2, ... s_n]$ and $[t_1, t_2, ..., t_m]$

I need to implement DTW algorithm with one extra constraint:

If $s_i$ is matched with $t_j$ then the next element $s_{i+1}$ has to be matched with some $t_{j+k}$ close enough to $t_j$ (i.e. $0 \le k \le W$ for some fixed window size $W$).

This constraint has to hold for each $s_i$.

1) Does there exist $O(nm)$ solution to such problem?

2) If an efficient algorithm does not exist, what would be a good practical solution?

(Note that locality constraint mentioned in the DTW link above is different from the constraint I need).

There is a $O(nmW)$-time algorithm using dynamic programming.  Let $A[i,j] = $ the cost of the best matching of $[s_1,\dots,s_i]$ to $[t_1,\dots,t_j]$ such that $s_i$ is matched to $t_j$.  Then

$$A[i,j] = \min\{c(s_i,t_j) + A[i-1,j-k] : k=0,1,\dots,W\}.$$

If you consider $W$ a constant, then you obtain a $O(nm)$-time algorithm.

I don't know if the factor of $W$ can be eliminated.

If $W$ is large, this can be improved to $O(nm \lg W)$ time.  The basic primitive we need is:

Given an array $B[1..m]$ and $W$, preprocess $B$ so that we can efficiently answer queries "compute $\min\{B[i],B[i+2],\dots,B[i+W-1]\}$".

Here's how to do that.  Assume first for simplicity that $W$ is a power of two.  You construct secondary arrays $M_2,M_4,M_8,\dots,M_W$ such that $M_w[i] = \min\{B[i],B[i+1],\dots,B[i+w-1]\}$.  You can build them up in $O(m \lg W)$ time, as each $M_{2w}$ can be constructed from $M_w$ in $O(m)$ time.  Thus if $W$ is a power of two you can answer subsequent queries in $O(1)$ time per query.

If $W$ isn't a power of two, you can still express the interval $i,i+1,i+2,\dots,i+W-1$ as the union of at most $\lg W$ intervals each of whose width is a power of two.  Thus, if $W$ isn't a power of 2, you can answer subsequent queries in $O(\lg W)$ time per query.

Finally, apply this to the original problem.  You apply this to each row of $A$, i.e., to $A[i,\cdot]$ for each $i$.  Then the recurrence can be computed using a single query, and it takes $O(\lg W)$ time instead of $O(W)$ time to compute the min.  You'll need to update the secondary arrays each time you update $A[i,j]$, but this takes only $O(\lg W)$ time per update to $A[i,j]$ (as there are only $\lg W$ secondary arrays to update).

In all, you obtain an algorithm whose running time is $O(nm \lg W)$ and with $O(nm \lg W)$ space usage.  (I suspect it's also possible to achieve $O(nm \lg W)$ time and $O(nm)$ space, if necessary, by only storing $M_w[i]$ for values of $i$ that are a multiple of $w$, at the cost of about a 2x increase in running time.)


Convert 24(decimal) to modified IEEE 754 floating point format? Here's what I have as the tweaked format I'm to use:

S EEE MMMM (excess 8 format)
s = sign bit, E = exponent bits, M = mantissa/fraction bits
Otherwise, it follows the IEEE 754 in principle.
The values:

(-1)^s x 0.0: e == 0, && m == 0

(-1)^s x 0.M x 2^-2: e == 0, && M != 0

(-1)^s x 1.N x 2^(e - 3): 0 < e < 7

(-1)^s x infinity: e == 7 && m == 0

NaN: e == 7 && m != 0

That's the formula I've been provided. I need to change 24(decimal) into a floating point binary value, but I continually end up with NaN. Am I doing something wrong?

It is technically a homework question, so if you don't want to provide an exact answer, I'd still be very appreciative if someone can tell me if I'm doing this right or wrong.

Since $e=111$ is saved for indicating NaN and  $\infty$, then the maximal number that can be represented with this 8bit-floating point structure is
$$ (-1)^0 \cdot (1.1111)_b \cdot 2^{6-3} = 15.5$$

Therefore, you cannot represent 24(Dec) using the above system.

However, the correct translation would be infinity rather than a NaN, that is, 24 should be represented as $0\ 111\ 0000 \equiv \infty$.


Algorithmic Composition: generative vs transformative algorith What's the difference between generative and transformative algorithms in relation to algorithmic composition of music?

As I understand the basic idea of the algorithms themselves, generative uses past candidate values (output becomes input) as progenitors (parents) for the next output, i.e. by combining them under certain conditions.

Transformative algorithms use environmental factors only to determine how to change the existing input.

However I've read that generative music as created by Brian Eno can use environmental factors and a single candidate input value, transforming it based on stored environmental factors.

I am struggling to understand what the difference is since there seems to be no universal agreement on what constitutes generative.

A generative algorithm tries to generate a new song out of nothing.

A transformative algorithm takes one song $s$ as input, and tries to produce a new song $s'$ by making some changes to $s$.


Turing, RAM, or Von Neumann --- which theory/model is the consensus? I am not a formal student for CS nor have I ever been, I just want to understand something simple about your field for general knowledge, in plea.
Turing, RAM, or Von Neumann --- which theory/model is consensually accepted to describe how "generally every computer works" (among computer scientists)?

It depends on the usage. For basic formal complexity theory, we usually work with Turing machines. However, RAMs and Von Neumann architectures are a better description for a real-world computer, so some may be more interested in them.
From my personal experience, TMs are the most popular in a CS degree, and in theory in general. I barely saw theoretical usages for RAM, and I never saw any Von Neumann architecture used in theory for computation, but I have seen models that describe a CPU in a specific course that covers that.


What to expect in a Computer Science and Mathematics course? I'm a high school student. I'm really into programming and mathematics and planning to study CS and mathematics when finished with high school.

I have a couple of questions concerning this issue:

Firstly, from maths point of view, what are the prerequisites and what subjects do I get in the first 2 years? I understood that Linear Algbera and Discrete mathematics are very important! So can you name an example of a maths textbook I may get?

Secondly, from a CS point of view, I already 'know' C#, F# and sometimes I play around with JS. Is it obligatory to learn ANOTHER language like python, java or c++? since knowing C# and F# already fulfils the 'need' of knowing different languages, F# with it's elegant functional-first programming paradigm and C# for imperative-first programming (technically, both F# and C# are multi-paradigm, which is awesome!)

To be more specific, I am into computer vision and ML. what textbooks do you think I may get in this area?

Firstly, from maths point of view, what are the prerequisites and what subjects do I get in the first 2 years? I understood that Linear Algebra and Discrete mathematics are very important! So can you name an example of a maths textbook I may get?

You want to select a textbook that "meets you where you're at" in terms of "mathematical maturity."  Selecting too basic of a textbook will bore you, but selecting one that is too advanced will allow you to progress only at a suboptimal rate.
If you don't already know stuff that's in a typical discrete math course, I would suggest looking at this thread on Math.SE.  My first Discrete Math course used Epp's book, but I found it somewhat basic.
If you already know some of what is covered in a typical discrete math course (e.g. elementary set theory, basic methods of proof, etc.--the stuff that would be covered in AoPS coursework), then I would highly recommend Graham, Knuth, and Patashnik's Concrete Mathematics.  It is literally the book on math with respect to computer science theory.  (If you learn everything in that book, I'd nearly guarantee you would know more math than 70-80% of CS students.)
However, graph theory and linear algebra are not covered in GKP's book.  For linear algebra, I don't really know of a "great" textbook.  For Graph Theory, I'd recommend looking at an algorithms textbook (CLRS's Introduction to Algorithms is really good), and perhaps going through this Coursera class and it's sequel.  I learned so much in that course.
Also, take a look at Project Euler; it gives some fun math-based challenges that build quite nicely on each other.  By solving those problems, I self-taught a ton of math from a very wide/eclectic basis.

Secondly, from a CS point of view, I already 'know' C#, F# and sometimes I play around with JS. Is it obligatory to learn ANOTHER language like python, java or c++? since knowing C# and F# already fulfils the 'need' of knowing different languages, F# with it's elegant functional-first programming paradigm and C# for imperative-first programming (technically, both F# and C# are multi-paradigm, which is awesome!)
To be more specific, I am into computer vision and ML. what textbooks do you think I may get in this area?

You'll probably be required to learn one of Java, C++, or Python depending on your school--most schools have a "favorite language" that they use by default in most of their classes.  This "favorite language" is typically one of those three.  (For example, University of Virginia uses Java as the language they assume all CS students know.)  If you're really into computer vision, you'll probably want to learn C++; it's speed is important in that field, or so I've heard.
I wouldn't worry too much about learning other languages; having a foundation in a procedural and a functional language is great, and if you're comfortable with OOP, you'll be fine.  When it comes time to use another language, you'll be able to pick it up really quickly with your background.


A regular expression for all strings that have exactly one double letter in them? Why is the answer (b + /\)(ab)*aa(ba)*(b + /\) + (a + /\)(ba)*bb(ab)*(a + /\)?  I'm confused and I request guidance

It took me a while to understand that your alphabet $\Sigma$ is $\{a,b\}$ and by /\ you meant the empty word $\epsilon$.

Your regular expression is the union of two sub-expression, namely:

(b + /\)(ab)*aa(ba)*(b + /\); and
(a + /\)(ba)*bb(ab)*(a + /\).

The first one (resp. second one) matches all the words that contain exactly one double letter, and that double letter is "a" (resp. "b"). Since the two sub-expression are similar (just swap "a" and "b"), I will only describe the first of the two.

A word $w$ that matches the first sub-expression contains exactly one occurrence of  "aa" and no occurrence of "bb", and can then be decomposed as
$$w = x \circ \, aa \, \circ y,$$
where "$\circ$" denotes concatenation and:

$x$,$y$ are strings that contain no double letters;
$x$ does not end with "a" (as otherwise you would have 3 consecutive "a"s in $w$).
$y$ does not start with "a".

We are then left with the task of finding a regular expression for $x$ and $y$.
Let's consider $y$ first.
Either $y = \epsilon$, or it must start with a $b$. Moreover, since no two characters in a row can be the same, $y$ is just an alternation of "b"s and "a"s. This can be expressed as $(ba)^*$ if $y$ has even length (i.e., if it ends with an $a$), and as $(ba)^*b$ if $y$ has odd length.

Therefore we can write the following regular expression for $y$: $(ba)^* + (ba)^*b$ and, by factorizing the common prefix, $(ba^*)(b+\epsilon)$.

The argument for $x$ is analogous, with the exception that $x$ is either $\epsilon$ or it must end with a "b". With a similar reasoning we get:
$x = (ab)^* + b(ab)^* = (b + \epsilon)(ab)^*$.

Substituting our regular expression for $x$ and $y$ back into the formula for $w$ we obtain:

$$
w = x \circ \, aa \, \circ y = \underbrace{(b + \epsilon)(ab)^*}_x \; aa \; \underbrace{(ba^*)(b+\epsilon)}_y .
$$.


What is the optimal way to perform GCD chain operation? Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices.
This problem is solved using dynamic programming.

Similarly

GCD chain operation is defined as:- Given a set of $n$ integers, what is the most efficient way to find the gcd of all the elements?

The cost is the number of GCD(x,y) invocations done by a binary GCD algorithm.

Basic attempt at solving the problem is:-
GCD$(a_1,a_2,a_3,a_4,\ldots a_n)$

{

$k=GCD(a_1,a_2)$.

if ($k=1$)

return 1;

else

return $GCD(k,a_3,a_4\ldots a_n)$;

}

In simple terms, it keeps finding the gcd of the smallest two among all the $n$ elements and then recurse, by replacing the two elements with their gcd which is at most the smallest element in the input.

Make suitable assumptions if necessary. For example you can assume that the integers are given in sorted order.

Assume GCD is computed using a binary GCD algorithm (other GCD algorithm is also fine)
aka

$GCD(a,b)= GCD(a-b,b)$

$GCD(2a,2b)=2GCD(a,b)$

and $GCD(a,2b)=GCD(a,b)$ (if $a$ is odd)

GCD(75,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 3

GCD(125,25)=GCD(100,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 4

GCD(179,25)= GCD(154,25)=GCD(77,25)=GCD(52,25)=GCD(26,25)=GCD(1,25)=1

Number of steps is 6

A heuristic strategy mentioned in the basic attempt above is not optimal for the following example

GCD(25,75,125,179,181,225)

= GCD(GCD(25,75),125,179,181,225) (3 steps)

=GCD(GCD(25,125),179,181,225) (4 steps)

=GCD(GCD(25,179),181,225) (6 steps)

=1

This required 13 invocations of GCD(x,y) function.

But the optimal strategy would be to see that 179 and 181 have gcd 1 and therefore the solution is 1, which requires computing only 1 bivariate gcd.

GCD(179,181)=GCD(179,2)=GCD(179,1)=1

which takes 3 invocations of GCD(x,y) only

I am not sure if there exists an optimal way to do it, or maybe it is NP hard to find a solution which makes the least number of GCD(x,y) calls.

You are saying that you will perform n-1 gcd operations, unless you find k numbers with a gcd of 1 by performing k-1 gcd operations.

Since you don't know which set of numbers has a gcd of 1, you can't pick a set with gcd 1. Your total time depends on the data you have.

You can try to process small numbers first, because the gcd of small numbers tends to be calculated quicker than the gcd of large numbers.

The optimal strategy will not always lead to the best outcome. I put a deck of cards on the table, face down, and ask you to pick the ace of hearts. Do you think "pick the ace of hearts" is the optimal strategy? No, it isn't a strategy that you can enforce since you don't know which one is the ace of hearts.


$\overline{SAT}$ vs. $UNSAT$, Is it the same? I know this question may look stupid, but still..
Is the meaning of both "have no satisfiable assignment"?

They are not precisely the same language. For instance, $\overline{SAT}$ has words that are not even formulas. $UNSAT$ on the other hand, has only formulas that are not satisfiable.
In terms of complexity measures - the two languages are equivalent, since we can check in polynomial time whether a given input word is a formula or not and therefore we have a poly-time reduction from $\overline{SAT}$ to $UNSAT$ and vice versa.


In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3? The paper is available here:
https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

The 1st paragraph of lemma 3's proof says

In other words,if event e is applicable to config C,and E is any config reachable from C without applying e,then e is applicable to E.

I can follow the whole proof except the above claim. In real,practical systems, the claim isn't necessarily true. Here is an example:

suppose process p has a code fragment like this:

open 2 udp sockets,f1 and f2,respectively,in nonblocking mode

s1: read a message m from f1，depending on m,do some local processing,then send a finite set of messages to other processes //m could be null

s2: read a message m' from f2，depending on m',do some local processing,then send a finite set of messages to other processes //m' could be null

The label s1 and s2 in the code are steps("In one atomic step, a process can attempt to receive a message, perform local computation on the basis of whether or not a messagewas delivered to it (and if so, which one), and send an arbitrary but finite set of messagesto other processe",quoted from the final paragraph of page 2 of the paper).

Use C and E to denote the system config when process p's program counter was pointing to s1 and s2,respectively. Obviously,E is reachable from C. Suppose another process q sent udp datagrams m1 and m2 to sockets f1 and f2,respectively,right before the system reached config C. Therefore,in config C,events (p,m1),(p,null) are both applicable.Suppose (p,null) was applied in config C,making the system reach config E.Obviously,event (p,m1) is not applicable in config E,because process p was unable to read socket f1 in config E.

Now we've seen (p,m1) was applicable in config C, config E was reachable from C, and along the path from C to E,(p,m1) was never applied, but (p,m1) was not applicable to E,violating the claim in lemma 3's 1st paragraph.

The crucial understanding here is the notion applicability of an event in some configuration versus the effect of applying the event to that configuration.
If an event e applies to configuration C, it follows that e applies to all C, where C is the set of all configurations reachable from C (all admissible extensions of C). This is a simple consequence of the model assumptions. If I can theoretically receive e now, and e can be delayed indefinitely, then I can apply e at any point in the future, perhaps having applied e', e'', and so on.
There is a myriad of conceivable scenarios where, in practice, either e will not be applied by the program (because the program counter has advanced beyond the point where this is possible, as per your example) or where the message in e will be rejected by the program because of some other condition (i.e. internal state that forbids the processing of e). An example of the latter is the receipt of phase 1a and 2a messages in Paxos: they may be silently discarded by an acceptor that has already promised a higher ballot number.
Now we come to the notion of effect, which was omitted from FLP. (One of the reasons that FLP is obscure.) Applying e in some configuration does not imply a measurable transition. A process p could conceivably pop a message from its receive queue and discard it immediately. FLP does not forbid this, provided p behaves deterministically at all times and does not rely on the notion of time. Perhaps, p has received some other message m', which has 'locked out' m, so to speak; ergo, the late delivery of m has no measurable effect on p. This is entirely possible.
The reasoning behind FLP is to only induce a contradiction. If applying e to any configuration in C results in a configuration in D, and if we can prove that D does not solely comprise univalent configurations, then we have shown that there is an ever-admissible schedule that spans bivalent states. Lemma 3 does not state that C and D are disjoint: some configurations in C may conceivably be in D. In the case where applying e to some state C' in C has no effect, then C' is in D by the assumption of the lemma.
In summary, applies simply means that an event may be delivered. It does not mean that it is acted upon in a transition-inducing way.


Why doesn't playing audio stop other tasks? If processors can only execute one thing at a time, how come I can play music continuously and still be able to run other tasks?

I understand the interrupt system, but isn't it needed that CPU continuously process audio for it to not sound jittery/laggy?

I am asking about the underlying implementation, is this question related to multi-threading? How does a 1-core, 1-threaded CPU be able to achieve this multitasking?

Since the CPU works in fixed clock cycles, nothing is really continuous, only seems so because the discretization is sensitive enough.

Suppose your CPU clock rate is $1\text{GHz}=10^9Hz$. If the CPU only devotes one in $t$ clock cycles to processing audio (and utilizes the remaining clock cycles for unrelated tasks) then you have a delay of $\approx t\cdot 10^{-9}s$ between every "audio processing tasks" preformed by the cpu (for simplicity, we assume the cpu preforms this processing using only one clock cycle).

Lets say we allow a delay of $10^{-5}s$ (humans hear frequencies in the range of 20Hz to 20Khz, so the human hearing will not be sensitive to such delay), then we need to require $t<10^4$, so the CPU can handle simultaneously $10^4$ more tasks while keeping a delay of $10^{-5}s$.


The difference between absurd reasoning and contraposal reasoning What is the difference between absurd reasoning and contraposal reasoning?
To show that a language is not regular

I've never heard those terms in the context of computer science.  When you mention "contraposal reasoning", I've never heard that term before, but I suspect that might be a reference to proving the contrapositive.  When you mention "absurd reasoning", I've never heard anyone use that specific phrase, but I suspect you might be referring to proof by contradiction, also known as reductio ab absurdum, which is Latin for reduction to absurdity.

These are general proof techniques. They're not specific to showing that a language is not regular.

General advice: I recommend that you try to avoid proof by contradiction.  It's a valid proof technique, but my experience is that it often leads beginners awry and causes them to make mistakes in the proof.  I recommend instead proving the contrapositive; it leads to more straightforward proofs where it is easier to avoid errors, and spot where you went wrong if you do make an error.


Average prefix code length of every 4-sized frequency vector is bounded at 2 I'm trying to show that for every frequency vector $(p_1, p_2, p_3, p_4)$ such that $\sum_{i=1}^4 p_i=1$, the average word length outputted by Huffman algorithm is bounded at 2: If $(w_1,w_2,w_3,w_4)$ is the outputted code, then $\sum_{i=1}^4 p_i |w_i| \le 2$.

I've tried looking at the tree that is generated by Huffman algorithm, but the thing is that several different tree structures match different 4-sized frequency vectors and I can't tell something general about all of them.

Also, is there a more general theorem for $k, n$ (here $k=4, n=2$)?

Hint: The code generated by Huffman's algorithm has the minimal average word length, and in particular is at least as good as any other code. Show that there is a "universal" code (of length $n=4$) whose average code length is exactly $2$ on any distribution.

The more general theorem states that the average word length for a code over an alphabet of size at most $2^a+b$ is at most $a + \frac{b}{2^a+b}$; to get the best bound for a specific $n$, write $n = 2^a+b$ with $a$ as large as possible. When $b=0$ there is even a universal code as in your particular case.


Termination of Z combinator with call-by-value I am trying to build my own λ-calculus interpreter. So far it supports both call-by-value and normal order.

I now want to try recursion via fixed points. The $Y$ combinator works with normal order, tested with the faculty function $$\text{fac} = \lambda f.\lambda n.\text{iszero}\,n\,1 (\text{mul}\,n\, (f(\text{pred}\,n)))\text{,}$$
and for example my interpreter yields $Y\,\text{fac}\,3 \stackrel{\text{NO}}{\rightarrow} 6$. (I'll write behaviourally equivalent Church numerals as decimal numbers)

As far as I know for call-by-value I will need the $Z$ combinator instead:

$$Z = \lambda f. (\lambda x. f (\lambda y. x x y)) (\lambda x. f (\lambda y. x x y))\text{,}$$

as $Y$ would cause an immediate infinite regression.

My problem is, I fail to understand how $Z\,\text{fac}\,0$ is supposed to terminate. It also does not terminate in my interpreter, but I want to understand it manually first.

After some steps call-by-value should arrive at:
$$Z\,\text{fac}\,0
\\=\lambda f. (\lambda x. f (\lambda y. x x y)) (\lambda x. f (\lambda y. x x y))\,\text{fac}\,0
\\\stackrel{\text{CBV}}{\rightarrow}(\lambda x. \text{fac} (\lambda y. x x y)) (\lambda x. \text{fac} (\lambda y. x x y))\, 0
\\\stackrel{\text{CBV}}{\rightarrow}\text{fac} (\lambda y. (\lambda x. \text{fac} (\lambda y'. x x y')) (\lambda x. \text{fac} (\lambda y. x x y')) y) \, 0
\\\stackrel{\text{CBV}}
{\rightarrow}\text{fac}\,F\,0\stackrel{\text{CBV}}{\rightarrow}\text{iszero}\,0\,1\,a\text{,}$$

where the omitted term

$$a=\text{mul}\,0\, (F\,(\text{pred}\,0))$$ contains

$$F=\lambda y.(\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\,y$$ again.

Now, $\text{iszero}\,0\stackrel{\text{CBV}}{\rightarrow}\lambda t.\lambda f.t$, s.t.

$$\text{iszero}\,0\,1\,a\stackrel{\text{CBV}}{\rightarrow}(\lambda t.\lambda f.t)\,1\,a\stackrel{\text{CBV}}{\rightarrow} (\lambda f. 1)\,a\text{.}$$

If our language had a branching construct that would ignore the $a$ branch we'd be done, but with call-by-value we have to evaluate $a$ to a value, i.e. an abstraction.

$a=\text{mul}\,0\, (F\,(\text{pred}\,0))$ and $\text{mul}\,0$ will be another abstraction so next I have to reduce $F\,(\text{pred}\,0)$.

$\text{pred}\,0\stackrel{\text{CBV}}{\rightarrow}0$, so we reduce $F\,0$.

$$F\,0 = (\lambda y.(\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\,y)\,0 \stackrel{\text{CBV}}{\rightarrow} (\lambda x.\text{fac}(\lambda y'.xxy'))(\lambda x.\text{fac}(\lambda y'.xxy'))\,0\stackrel{\text{CBV}}{\rightarrow}\text{fac}\,F\,0$$

And now we're back at square one. Am I doing something wrong?

I don't think you're doing the reduction wrong, but the problem isn't the Z combinator. The problem is $\text{iszero}$. Branching constructs in call-by-value cannot just take the direct terms for each branch as arguments like they can in call-by-name (or similar), because both branches will be evaluated regardless of the test. This clearly interacts poorly with recursion, but it's also undesirable in general.

Instead, branching constructs in call-by-value should take explicitly delayed arguments. So something like: $$\text{iszero}\ n\ (λ\_. 1) (λ\_. \text{mul}\ n\ (f\ (\text{pred}\ n))$$ this way the recursive evaluation can be avoided unless it is actually necessary. You could, of course, leave $\text{iszero}$ as is, always use it this way, and provide an extra argument yourself, but I think normally it would be defined to expect delayed arguments.


In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation? When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs.

I am confused about the definition of an $S_3$ graph.
I am aware that in some resources, $S_n$ means $K_{1,n}$, and in others $S_{n-1}$ means $K_{1,n}$.

However, in both cases, ($C_{n+4}$,$S_3$,claw,net)-free $\equiv$ UIG seems like a wrong notation.

If $S_3$ is $K_{1,3}$, then $S_3$ is also a claw graph. Thus, ($S_3$,claw)-free is a redundant notation.
On the other hand, if $S_3$ is $K_{1,2}$, then it is wrong because a path of length 3 is realizable as a unit interval graph.

If this notation is true, then can I also write UIG $\equiv$ ($C_{n+4}$,$S_3$,$K_{1,2}$,$P_2$,claw,net)-free?
If not, then is it correct to write that UIG $\equiv$ ($C_{n+4}$,claw,net)-free?

You can look up the small graphs that ISGCI uses to define classes. Specifically, $S_3$ is the following "sun" graph:

ISGCI defines sun graphs as

  a chordal graph on $2n$ nodes ($n\geq3$) whose vertex set can be partitioned into $W = \{w_1,\dots,w_n\}$ and $U = \{u_1, \dots,u_n\}$ such that $W$ is independent and $u_i$ is adjacent to $w_j$ iff $i=j$ or $i=j+1\pmod{n}$.

Implicitly, the subgraph induced by $U$ can be anything. Wolfram Mathworld also talks about "complete sun graphs", which is the special case where $U$ is a clique.


Is this simple problem NP-complete? Candy Allocation Problem: Suppose there are $n$ candies, each with a weight $w_i$ gram. There are $m$ kids, and each kid needs to eat at least $\omega$ grams of candies to be full. Candies cannot be cut into pieces. Is there a candy allocation algorithm such that at least $k$ kids can be full?

Is the above problem NP-complete? It has some similarity to knapsack, but not exactly the same. Can someone help me?

First, we prove that the decision version of the original problem is NP. Since an instance of an assignment can be verified within polynomial time, it's obviously NP.

Now, we try to prove the NP-hardness of the problem.
Well, I believe this problem can be reduced from the bin-packing problem.

The bin-packing problem says the following:
There are $n$ items each with a weight $w_i$ and $m$ bins. We want to put the items to bins. Each bin has a maximum weight limit $\omega$. The problem is to find a item assignment scheme so as to minimize the number of bins needed. Mathematically:
$$\textrm{minimize}~~~ z = \sum_{j=1}^m y_j$$
Subject to:
$$\sum_{i=1}^n w_i x_{i,j} \leq \omega y_j, \forall j \in \{1,2,\cdots,m\}$$
$$\sum_{j=1}^m x_{i,j} = 1, \forall i \in \{1,2,\cdots,n\}$$
$$y_j \in \{0,1\}, \forall j$$
$$x_{i,j} \in \{0,1\}, \forall i, \forall j$$
The problem is NP-hard, and its NP-hardness has already been proved. The decision version of this problem is NP-complete.

Note that in the candy allocation problem, we tend to maximize the number of kids that are completely full. Since the number of kids are the same, the problem is equivalent to minimizing the number of kids that are not full, while ensuring every candy is allocated. The problem is formalized as follow:
$$\textrm{minimize}~~~ \sum_{j=1}^m y_j$$
Subject to:
$$\sum_{i=1}^n x_{i,j}w_i \leq \omega y_j, \forall j \in \{1,\cdots,m\}$$
$$\sum_{j=1}^m x_{i,j}=1 ,\forall i \in \{1,\cdots,n\}$$
$$x_{i,j} \in \{0,1\}, \forall i, \forall j$$
$$y_j \in \{0,1\}, \forall j$$
where $y_j$ denotes if kid $j$ is hungry ("1" is hungry, "0" is full), and $x_{i,j}$ denotes if candy $i$ is allocated to kid $j$.

One can easily see that the problem is equivalently to the bin packing problem. Thus, candy allocation is NP-hard.

Since candy allocation is NP and NP-hard, it's NPC.

The definition of bin packing problem can also be found in https://en.wikipedia.org/wiki/Bin_packing_problem.


Constraint Satisfaction: maximizing total value with no overlaps Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value.

Out of all the bars available, we want to choose the set which maximizes the total value but with no overlap between the start points and end points of the bars. In the example above, the selected bars would be the following (in red):

What would be the best way to approach this problem computationally, for n number of bars being potentially large (several thousands) and [x,y] the possible bar positions being large as well?

I thought of a probabilistic approach, but are there deterministic approaches as well?

You are looking for a maximum weight independent set in an interval graph, which can be solved in linear time (by a deterministic algorithm). By the way, the same is true also for a superclass of interval graphs, namely chordal graphs.

One such algorithm is based on dynamic programming, you can see e.g., [1] for details and discussion.

[1] Hsiao, Ju Yuan, Chuan Yi Tang, and Ruay Shiung Chang. "An efficient algorithm for finding a maximum weight 2-independent set on interval graphs." Information Processing Letters 43.5 (1992): 229-235.


A monotonically nondecreasing function $ f(n) $ s.t $ f \in O(n^2) $ and $ f \notin o(n^2) $ but also $ f \in \Omega(n) $ and $ f \notin \omega(n) $ I am trying to look for an example of a monotonically non-decreasing function $ f(n) $ such that:
$ f(n) \in O(n^2) $ and $ f(n) \notin o(n^2) $ but also $ f(n) \in \Omega(n) $ and $ f(n) \notin \omega(n) $. The domain could also be all real numbers.
I considered different variations of piecewise functions, for example I considered the function $$ f(n)=
\begin{cases}
 n^{2-\frac{1}{n}} &\text{if}\, n =2k+1\\
 n^{1+\frac{1}{n}}&\text{if}\, n=2k\\
\end{cases} $$
which satisfies the growth rate conditions, but is clearly not monotonically non-decreasing.
I would be happy to hear your ideas, thank you.

I may be wrong, but it seems to me that the function defined by:
$f(n) = \left\{\begin{array}{rl}1 & \text{if }n=1\\2^{2^{\left\lfloor \log_2\log_2 n \right\rfloor+1}}&\text{otherwise}\end{array}\right.$
satisfy the conditions.
To explain why, the values taken by $f(n)$ will be $1, 4, 4, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 256, 256, …$
The idea is that when $n=2^{2^k}$, then $f(n) = 2^{2^{k+1}} = n^2$, and when $n=2^{2^k}-1$, then $f(n) = 2^{2^{k}} = n +1$. That way, you will guarantee the 5 conditions: $(O(n^2) \setminus o(n^2)) \cap (\Omega(n) \setminus \omega(n))$ and increasing.


Role of Term Constants in Simply Typed Lambda Calculus In the Wikipedia article on Simply Typed Lambda Calculus (among other places), there is a notion of a "term constant".  This is particularly notable in the production grammar given:

In this production grammar, the c is the term constant.  I am new to the simply typed variant of lambda calculus -- I do not understand what role this constant plays in the overall computations of STLC.  Can anyone give some examples of how the term constant is used and explain its general purpose?

As per Sam's request, I rephrase my comment as an answer.

Constants play an important role in λ-calculi (not just the simply typed variant).

They are often convenient: even though we can usually represent our target data using
$\lambda$-terms without constants this tends to be unwieldy. For example
integers
directly by some variant of an unary encoding, e.g. the Church encoding has $$\lambda g x. \underbrace{g ( g ( ... g ( g\ x ) .. ) ) }_{n}$$ as representation of $n$. That leads to cumbersome, unreadable terms. With constants we can  do arithmetic with 0,1,2,..., and +,−,∗,...
In a typed calculus, we need  constructors for types, and constants play this rule. E.g. 0,1,2,..., or +,−,∗,...
for the type of integers, true,false... or ∨,∧ for booleans etc.

Note that the STLC was born with constants : Church's original
formulation contains constants $N_{oo}$, $A_{ooo}$, $\Pi_{o(o\alpha)}$
as well as $\iota_{\alpha(o\alpha)}$, representing negation,
disjunction, universal quantification and the selection operator,
respectively.


#3-Coloring Problem for Tree with Some Pre-Colored Nodes I have a undirected tree and three colors to choose from. Some nodes are already colored; these nodes and their colors are given. What is an efficient algorithm to find the number of ways to color the rest of the nodes such that no two adjacent nodes are the same color?

Many problems on trees can be solved using dynamic programming. Let me explain how to solve a similar problem, independent set with fixed vertices. In this problem, you are given a tree $T$ and an independent subset $I$ of its nodes, and your task is to count all independent sets which contain $I$.

Arbitrarily root $T$ at some vertex $r \in T$. For every vertex $v \in T$, let $T_v$ be the subtree of $T$ rooted at $v$. For every $v \in T$, we will calculate two quantities:

$\alpha_v$ is the number of independent sets in $T_v$ containing $T_v \cap I$ and $v$.
$\beta_v$ is the number of independent sets in $T_v$ containing $T_v \cap I$ but not containing $v$.

We calculate these quantities recursively, as explained below, and output $\alpha_r + \beta_r$, which is the total number of independent sets in $T$ containing $I$.

The base case is when $v$ is a leaf. If $v \in I$ then $\alpha_v = 1$ and $\beta_v = 0$, and otherwise $\alpha_v = \beta_v = 1$.

Now suppose that $v$ is an internal node, say with children $v_1,\ldots,v_m$. If $v \in I$ then $\beta_v = 0$ and $\alpha_v = \prod_{i=1}^m \beta_{v_i}$, since an independent set containing $v$ cannot contain any of its children. If $v \notin I$ then it is still the case that $\alpha_v = \prod_{i=1}^m \beta_{v_i}$, and additionally $\beta_v = \prod_{i=1}^m (\alpha_{v_i} + \beta_{v_i})$, since we don't have any constraints on the $v_i$.

Now that the algorithm is laid out, you can check that it runs in linear time. Your problem can be solved in a similar fashion, also in linear time.


Given that f(n)>0 and constant c>0 Prove that f(n)+c = O(f(n)) or provide a counter-example if it's false Question:

Given that f(n)>0 and c>0

Prove that f(n)+c  =  O(f(n)) or  provide a counter-example if it's false.

My Effort to solve: \begin{eqnarray*}
f(n) + c \space  \leq \space d\cdot&f(n)\space for \space all\space n \geq n_0\space and \space d>0\\
\end{eqnarray*}
So i believe there can be found some large d that satisfies this equation, but i am not sure about it.

This is false. A counterexample is $f(n)=1/n$ and $c=1$.

If $f(n)+c=O(f(n))$, then there exists $n_0>0$ and $d>0$, for any $n>n_0$,  $f(n)+c\le df(n)$, or $1/n+1\le d/n$. But let $n=\max\{n_0+1,d\}$, the inequality fails obviously, a contradiction.

In fact, any $f(n)$ and $c$ such that $f(n)\to 0$ ($n\to\infty$) and $c>0$ are sufficient.


Euclidean algorithm and well define ness on the underlying set Euclidean algorithm is given below:

  gcd($a$,$b$):

    if $a=0$, return $b$

    otherwise, return gcd($b \bmod a$, $a$)

Let us first argue that the algorithm terminates. The reason is that each time the number is decreasing, and there is a well-ordering defined on the set from which number $a$ and $b$ are defined.

Question: What if the well-ordering is not defined on the set from which elements $a$ and $b$ are coming? In that case can we say that algorithm will take finite time? To me it appears no, but the reasoning is not clear to me.

We can think of the GCD algorithm as taking place inside a directed graph. The vertices of the graph are all pairs $(a,b)$, where $a,b \geq 0$. If $a \neq 0$, then there is an edge from $(a,b)$ to $(b \bmod a, a)$. The algorithm starts at some vertex $(a,b)$, follows the unique outgoing edges, until (hopefully) reaching a leaf $(0,b)$, at which point it outputs $b$.

We can consider a more general situation, in which we are given a directed graph in which every vertex has at most one outgoing edge, and a starting vertex. We start at that vertex, and follow the unique outgoing edges, stopping if we ever reach a leaf. In this generality, we cannot be certain that the process always terminates. In fact, if the graph contains a directed cycle and we start with a vertex on the cycle, the process will ever terminate!

Consider for example the graph on $1,2,3$ with edges $1\to 2$, $2 \to 3$, $3 \to
1$. On this graph, the iterative process will never terminate.

There is another reason for the process to not terminate: there might be an infinite directed path.  For example, consider the directed graph on the integers in which the edges are $a \to a+1$. This graph contains no cycles, but nevertheless the process does not terminate.

To show that the GCD algorithm always terminates, we define a potential function $\phi$ on the vertices by $\phi(a,b) = a$. If $(a,b) \to (b \bmod a,a)$ then
$$
\phi(b \bmod a,a) = b \bmod a < a = \phi(a,b).
$$
Therefore the potential decreases. Since the potential is always a natural number, and these are well-ordered, it cannot decrease forever, and therefore the algorithm necessarily terminates.

To finish, let me mention the Collatz conjecture. Consider the directed graph on the positive integers in which the edges are $2n \to n$ and $2n+1 \to 3n+2$ for all $n \geq 1$. The Collatz conjecture states that the process considered above always terminates, no matter what the starting vertex is. The conjecture is suspected to be true, but nobody knows how to prove it.


Are hardware specs relevant in software performance comparisons? I notice occasionally in blogs or articles comparing different languages, algorithms, etc. that the author will divulge info about the processor used in the testing. Is this meaningful?

Shouldn't the relative performance differences be hardware-agnostic? That is, if Language A executes in twice the time as Language B, shouldn't that roughly persist no matter the hardware?

Yes, hardware specs are relevant.  No, relative performance differences are not hardware-agnostic.

Suppose I find that editing a certain movie on my laptop takes twice as long as printing a certain Word document on my laptop.  Does this mean if I do those two tasks on my desktop computer, the movie editing task will also take twice as long as printing the Word document?  No, not necessarily.

Maybe my desktop computer has a great GPU (graphics card) but my laptop doesn't have a GPU.  The GPU can be expected to speed up the movie-editing task, but it won't speed up printing from Word.  So, on my desktop it's even possible that the movie-editing task might be faster than the printing task.

This is one reason why hardware specs are relevant.


Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively
account for at least three-fourths (3/4) of the edges in an arbitrary undirected
graph.

The algorithm I have come up with is a greedy algorithm that iterates through the graph choosing the node with the largest number of incident edges and then updating the adjacent vertices with their new incident edge count.

I am fairly confident this algorithm will work, however I am struggling with the proof that I will always account 3/4 of the edges.

What I have so far is that because the sum of the degrees of all the edges in the graph is equal to 2E then on average every node will contribute at least a degree of 2E/n to that summation.  2E/n x n/2 vertices provides me with just E. Is this correct or am I missing something?

I'm not sure your algorithm works. Here is an algorithm that does work: choose $\lceil V/2 \rceil$ random vertices. You can calculate that each edge is chosen with probability at least $3/4$, and so the expected number of chosen edges is at least $3/4$ of all edges.

This algorithm can be derandomized (made deterministic) using the method of conditional expectations. I suggest you read about the method and work the details out. You will get something very similar to the greedy algorithm you're suggesting, but I suspect there will be some subtle differences.


How can a universal Turing machine simulate "bigger" ones? I'm trying to find the answers of two questions about the Universal Turing machine.

How can the Universal Turing machine simulate a Turing machine if
the one that is being simulated has a bigger number of states?
How can the Universal Turing machine simulate a Turing machine if
the one that is being simulated has a bigger number of alphabet
characters?

Can anyone help me with these questions?

The answer to both subquestions is the same: by using the tape to store the necessary data. We can assume that the state set and alphabet of the machine to be simulated are subsets of the natural numbers ("State 1", "State 2", "State 3", etc.). Even with just two non-blank characters, the universal machine can represent all those integers as binary strings.

Note, though, that the universal machine has a fixed number of states, which makes computing the transition function a little tricky. What we'd like to do is write some instructions that implement a big switch statement of the form, "If the state is $s$ and the character under the head is $x$, then move to state $s'$, write character $x'$ and move the head in direction $d$." So – and I think this may be the root of your question – how do we calculate the transition function if we don't even have enough states in the universal machine to store the transition function's input?

One way is to store the transition function as a binary tree. Suppose all the simulated machine has $2^q$ states and $2^\ell$ tape symbols. Store the transition function as a binary tree of depth $q+\ell$  where, at the first $q$ levels, you go left or right according to whether the next bit of the simulated state is a one or a zero and the next $\ell$ levels are the same but for the successive bits of the simulated tape character. Now, your universal machine can walk backwards and forwards on its tape, checking the next bit of the state/character, remembering that bit in its own states, moving back to the tree, putting a marker at the correct node, and so on.

This gets somewhat easier if you let your universal machine have multiple tapes but then you still have to show that your multitape machine is equivalent to a single tape machine.


Uniformly sampling from cycles of a graph I was wondering if, given an arbitrary cycle basis (that's complete, e.g. every cycle in the graph can be expressed as the $\mathbb{Z}/2\mathbb{Z}$ sum of elements from the basis) of some graph $G$, is there some way of sampling all cycles uniformly? I'm not able to find papers on it, and I was wondering if anyone had any results on this.

Exponential-time algorithm

One (slow) approach is to rejection sampling.

Let $c_1,\dots,c_k$ be the cycle basis.  Then we obtain an isomorphism $\varphi : (\mathbb{Z}/2\mathbb{Z})^k \to \mathcal{E}$, where $\mathcal{E}$ is the set of Eulerian subgraphs of $G$, given by

$$\varphi(\alpha_1,\dots,\alpha_k) = \alpha_1 \cdot c_1 + \cdots + \alpha_k \cdot c_k.$$

This gives us a way to sample uniformly at random from the set of Eulerian subgraphs.

Note that the set $\mathcal{C}$ of simple cycles of $G$.  Note that every simple cycle is an Eulerian subgraph, i.e., $\mathcal{C} \subseteq \mathcal{S}$.  Thus, a simple procedure to sample uniformly at random from $\mathcal{C}$ is:

Sample uniformly at random from $\mathcal{E}$, to get a subgraph $e$.  (Namely, pick $\alpha_1,\dots,\alpha_k$ uniformly at random and set $e = \varphi(\alpha_1,\dots,\alpha_k)$.)
If $e$ is a simple cycle, output it.  Otherwise, go back to step 1.

This samples a simple cycle uniformly at random from the set of all simple cycles of $G$.

The (expected) running time is proportional to $|\mathcal{E}|/|\mathcal{C}|$.  It is known that $|\mathcal{E}|=2^{|V|+|E|-1}$ if $G$ is connected.  Thus, if $G$ has $C$ different cycles, this gives an algorithm whose running time is proportional to $2^{|V|+|E|-1}/C$.  Depending on the number of cycles in $G$, this might be extremely slow.

I don't know if there is a polynomial-time algorithm or not.

Counting the number of simple cycles

Counting the exact number of simple cycles in a graph is NP-hard, by reduction from the Hamiltonian cycle problem.  Jonathan Katz has some lecture notes that provide a proof.

I don't know whether it is hard to approximate the number of simple cycles in $G$. If it is, then this might imply hardness results for uniform sampling from among the set of simple cycles.

See also https://cstheory.stackexchange.com/q/20246/5038.


How to implement mutex on single processor (single core) system other than using spinlock How does one implement mutex on a single processor system without using spinlock mechanism. Mutex is to be implemented in user space (for any user level library like pthread lib for example).

It is impossible to implement a mutex completely in userspace unless you have special CPU instruction that could simulate a semaphore or a lock (some "test and increment if true" instruction). pthread in Linux goes through the kernel to implement the mutex.


Can you determine rotation/camera calibration from series of images separated by pure rotation I have a series of about 50 images, each separated by a small rotation and taken from the same camera. The images are feature-dense, and I can calculate a homography from image-to-image easily.

My question is, is there any way to determine the rotation matrix and/or intrinsic camera calibration parameters given just these images?

If the images are related by pure rotation, then the homography would give you the rotation matrix.  If the rotation is in-plane, then you would not be able to compute the intrinsics.


How can Karger's algorithm (and other randomized algorithms) be used in practice? Suppose I am given the following problem (the source is here):

  Disconnect two nodes in a graph by removing minimum number of edges.

I would apply Karger's min-cut algorithm. But how can I guarantee that I'll finally find the min-cut? Karger's algorithm is a randomized algorithm. If the probability of success is 1/p, I could run it p times to get the answer, right? Not necessarily! What if I am extremely unlucky, so I will never (or too much time will pass) get the answer?

Karger's algorithm is a randomized algorithm.  It has a small probability of error, but that probability can be made arbitrarily (exponentially) small simply by repeating the approach.

If we do one round of the algorithm, it has a probability of success of $p$.  If you repeat it $100/p$ times and take the best cut found in any of those iterations, then the probability of success is incredibly high: the algorithm fails only if all $100/p$ iterations fail, so the probability of failure is

$$(1-p)^{100/p} \approx e^{-100} < 2^{-128},$$

and the probability of success is larger than $1 - 2^{-128}$.  For Karger's algorithm, $p=1/{n \choose 2}$, so we repeat it $100 {n \choose 2}$ times, and we obtain a probability of success that is larger than $1 - 2^{-128}$.

For all engineering purposes this is equivalent to a guarantee of success.  For instance, the probability that a cosmic ray hits your computer and causes a bitflip error that causes the algorithm to produce the wrong result is far higher than $2^{-128}$, but we're apparently willing to accept that -- so we should be glad to accept Karger's algorithm too, as long as we repeat it enough times.

See the Wikipedia article for more explanation: https://en.wikipedia.org/wiki/Karger%27s_algorithm


Standard definition of Turing machine I have followed two famous book on "Automata and Formal Language Theory":

Micheal Sipser's book
Jeffrey Ullman and John Hopcroft's book

in both books, tuple level definition of Turing machine differs with each other. Although abstract level working are same but details are different. Why there is not any standard definition? Even some other books have explained the Turing machine in different way.

When we try to measure time complexity of same algorithm on these machines, exact time also differs. Why the authors/scientist have not agreed upon one standard definition?

There is no standard definition since it is uncommon to use the details of the definition of Turing machine. In contrast to other definitions in mathematics, Turing machines are complicated objects whose definition is unwieldy to use directly. Instead, we invoke the Church–Turing hypothesis and describe Turing machines by giving algorithms rather than listing tuples. At this point, the exact definition of Turing machine is unimportant.

A similar situation occurs in other cases, of which I will describe two: number systems and forcing.

Number systems, especially the real numbers, have several different constructions. If you look at books containing a construction of the real numbers, you are likely to see different constructions, in some cases vastly different ones (for example, Dedekind cuts versus Cauchy sequences). However, from the point of view of the user, all we care about is that the real numbers we construct satisfy the field axioms as well as being complete and Archimedean (the exact meaning of these terms is unimportant). We almost never get to use the actual underlying definitions.

Forcing is an important proof technique in set theory. Forcing can be defined in several different ways, the most popular being forcing relations and Boolean-valued models. (A less popular one is modal logic.) These methods are all equivalent, but the formal development can be somewhat different. All of these methods lead to the same proofs in set theory, but there is no "official" one. Which one you choose to present in a set theory textbook or course depends on your personal taste.

The exact definition of Turing machine does matter if you're interested in exact resource consumption, say, how many steps does it take to solve a certain problem. Since all reasonable definitions of Turing machines result in the same running times up to constant factors, and since we don't usually care about constant factors per se, the exact definition doesn't matter and yields the same results.

The same situation occurs when proving other theorems in which the Church–Turing hypothesis cannot be used. For example, when proving Cook's theorem that SAT is NP-complete, we really need to refer to the definition of Turing machine; but the construction will work for many different definitions, in much the same way. We pick one definition arbitrarily and stick to it, knowing that using any other variant will result in a slightly different yet still valid proof.


Space-efficient representation of potentially very large arbitrary-precision rationals? I'd like to know if there are good techniques for faithfully and (reasonably) representing rational numbers with forms similar to:

2/3
1/10
4 * 10 ^ 1,000,000,000,000

I know arbitrary precision rationals can be represented by pairs of arbitrary precision integers, and they can be normalized using gcd, so operations like equality testing are efficient. But trying to represent (3) this way would quickly exhaust memory.

(3) can be dealt with efficiently and faithfully with a scientific-notation-like representation, but this can't faithfully represent all rationals.

Is there a way to get the best of both worlds, i.e. be able to both faithfully represent all rational numbers, and deal with very large numbers efficiently?

Representing a rational number as ${a \over b} \times c^d$ where $a,b,c,d$ are integers can represent all three classes of numbers you mentioned efficiently.  You can do standard operations on numbers represented in this way, but some of those operations will be inefficient: for instance, $10^{10000000}+1$ will be inefficient.

For any representation you have in mind, there will be some rational numbers that can be specified concisely in English but that require a huge amount of memory to represent with that representation scheme, so there is no one answer that will handle everything efficiently -- the best you can do is probably to identify the classes of numbers you want to represent efficiently and then choosing a representation that handles those particular classes.


What is the time/space complexity of $n!$? Can $n!$ has polynomial space complexity? Given an integer $n$, calculate $n!=n\times(n-1)\times(n-2)\dotsc 3\times2\times1$.

What is the best time and space complexity of calculating $n!$?

P.S. I do not have any idea about this topic. I was using MATLAB and I needed to compute $200!$ but it said "Out of memory"!! That's why I am asking.

Stirling's formula shows that $\log m! = \Theta(m\log m)$. In terms of the length $n = |m|$, we get $|m!| = \Theta(n2^n)$, and so $m!$ cannot be bounded by a polynomial in $m$. A reasonable algorithm for calculating $m!$ exactly is using the formula $m! = m \cdot (m-1) \cdots 1$. This algorithm uses quasilinear time and linear space (in the output size). For estimating $m!$, you can use the asymptotic series extending Stirling's formula.

Since $m!$ grows very large, there is no real need to calculate $m!$, you can just store all relevant values in a table (a value is relevant if it can be stored as a machine integer, though if you use bignums then more values become relevant). You can find the values in such a table on the web.

Things become more interesting when you're after $\log m!$, since now a table would be too big. Fortunately, MATLAB can compute the $\Gamma$ function which satisfies $\Gamma(m+1) = m!$ (it is the unique log concave function with this property) and its logarithm $\ln \Gamma$ — use the functions gamma and gammaln.


Applying a multi qubit quantum gate to specific qubits A controlled not gate matrix looks like this:

$$\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}$$

That works great when you only have two qubits and you want to use the first qubit as the control, and the second qubit as the input to be flipped (or not).

Is there a method to convert this matrix to use for instance if you had 3 qubits, and wanted to use qubit 1 as the control and qubit 3 as the input that is possibly flipped?

Thinking about it logically, I can come up with this:

$$\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
\end{bmatrix}$$

Is there a better, more formal/generalized way to convert multi qubit gates to use any specified qubits, rather than the first $N$ in an $N$ qubit circuit?

Don't use the swap method, it's very inefficient. And the other person's answer is specific to the CNOT gate, and to be frank, over-complicates things.

Here's a very simple algorithm that solves your problem for every single case, not just the CNOT gate, for any arbitrary bits.

The algorithm:

let sys = matrix representing the current state of the system
let n = number of qubits being simulated
let lgm = logic gate matrix of size 2^n by 2^n
let f = our logic gate transformation function
for i = 0 to (2^n) - 1:
    lgm[column = i] = f(i)
sys = sys × lgg

In classical computers, there's something known as the "decoder". Let's say I have only 3 wires, effectively, 3 bits. But I want to control 8 wires. Can that be done? Yes, because 3 bits has 8 different possibilities: 000, 001, 010, 011, 100, 101, 110, 111. So we can assign each possibility to one of our 8 output wires. This is called "decoding".

If I pass in the number 101 and we have 3 bits, we know 101=5, so then I will be setting output wire 5 to a high voltage and the other 7 output wires will be 0, which we can represent like this: decode(101) = [0, 0, 0, 0, 0, 1, 0, 0].

In this algorithm, I mention the "transformation function" called "f". For classical computers, the transformation function is just taking in an input value and returning the "decoded" version of the output value. So if we have 3 bits, and the output is 4, then we will be returning [0, 0, 0, 0, 1, 0, 0, 0]. We then assign that as the column of our matrix for that value.

Let's think of "decoding" in terms of qubits. How can we decode the qubits |101>?

We know that for our qubit probability vectors, |0> is [1, 0] and |1> is [0, 1]. Decoding qubits can then be done what's called the Kronecker product.

So if we convert each bit to the probability vector equivalent and take the Kronecker product of all of them, we get...

|101> = |1> ⊗ |0> ⊗ |1> = [0, 1] ⊗ [1, 0] ⊗ [0, 1] = [0, 0, 0, 0, 0, 1, 0, 0]

This is how we'd want to decode qubits. This algorithm can be applied to qubits just the same using this.

Let's try this algorithm on a simpler problem.

Let's assume we have a system with only 2 qubits. If we want to apply the Hadamard gate to just 1 qubit, we can generate a logic gate for both qubits that only applies the Hadamard gate to a single qubit. Let's assume the single qubit we want to apply it to is our most significant qubit and the least significant will be unaffected.

We want a transformation function that for each of our possible inputs, produces the correct output. We have two qubits, this means there are four possible outputs.

f(|00>) = ?
f(|01>) = ?
f(|10>) = ?
f(|11>) = ?

We know the least significant qubit will be unaffected, so we can fill that in.

f(|00>) = ? ⊗ |0>
f(|01>) = ? ⊗ |1>
f(|10>) = ? ⊗ |0>
f(|11>) = ? ⊗ |1>

We also know what the Hadamard does to a qubit, such that:

H(|0>) = 1/sqrt(2)|0> + 1/sqrt(2)|1>
H(|1>) = 1/sqrt(2)|0> - 1/sqrt(2)|1>

So our transformation function is simply:

f(|00>) = (1/sqrt(2)|0> + 1/sqrt(2)|1>) ⊗ |0>
f(|01>) = (1/sqrt(2)|0> + 1/sqrt(2)|1>) ⊗ |1>
f(|10>) = (1/sqrt(2)|0> - 1/sqrt(2)|1>) ⊗ |0>
f(|11>) = (1/sqrt(2)|0> - 1/sqrt(2)|1>) ⊗ |1>

Expand this out to our normalized probability vector form...

f(|00>) = [ 1/sqrt(2), 1/sqrt(2) ] ⊗ [ 1, 0 ]
f(|01>) = [ 1/sqrt(2), 1/sqrt(2) ] ⊗ [ 0, 1 ]
f(|10>) = [ 1/sqrt(2), -1/sqrt(2) ] ⊗ [ 1, 0 ]
f(|11>) = [ 1/sqrt(2), -1/sqrt(2) ] ⊗ [ 0, 1 ]

Now let's actually solve this...

f(|00>) = [ 1/sqrt(2), 0, 1/sqrt(2), 0 ]
f(|01>) = [ 0, 1/sqrt(2), 0, 1/sqrt(2) ]
f(|10>) = [ 1/sqrt(2), 0, -1/sqrt(2), 0 ]
f(|11>) = [ 0, 1/sqrt(2), 0, -1/sqrt(2) ]

That's our transformation function.

Our  logic gate matrix, "lgm", is of size 2^n by 2^n where n = number of qubits being simulated, so in this case it's 2^2 by 2^2 or 4x4.
Our algorithm tells us that for each column i, set the column equal to f(i). We've defined our probability transformation function, so we can easily fill out these columns.

lgm =
    |00>       |01>        |10>        |11>
[ 1/sqrt(2),         0,  1/sqrt(2),          0 ]
[         0, 1/sqrt(2),          0,  1/sqrt(2) ]
[ 1/sqrt(2),         0, -1/sqrt(2),          0 ]
[         0, 1/sqrt(2),          0, -1/sqrt(2) ]

Now the final step in our algorithm is simply matrix-multiplying our matrix representing the entire quantum system, sys, by this logic gate, lgm.

And that does what we want. It will apply the hadamard gate only to the most qubit and leave the least significant qubit alone.
If you don't believe me, you can try it yourself and see that it works.

The reason this is so powerful is because it applies to any case.

Let's try this algorithm on your problem.

Imagine we have a 3 qubit system and we want to apply a CNOT gate to qubit[0] and qubit[2]. If you look up the CNOT matrix on Wikipedia, that matrix only applies to a 2-qubit system. A naive solution would be to append identity matrices to it using the Kronecker product to make it work on systems with three qubits. But this fails here: qubit[0] and qubit[2] are not adjacent, so simply appending identity matrices won't work.

We could swap qubit[0] with qubit[1], apply the CNOT gate, then swap them back. But that's slow. Instead, we could simply generate a non-adjacent CNOT gate for our problem using the algorithm above.

We first need to come up with a transformation function for each case.

f(|000>) = |0> ⊗ |0> ⊗ |0>
f(|001>) = |0> ⊗ |0> ⊗ |1>
f(|010>) = |0> ⊗ |1> ⊗ |0>
f(|011>) = |0> ⊗ |1> ⊗ |1>
f(|100>) = |1> ⊗ |0> ⊗ |1>
f(|101>) = |1> ⊗ |0> ⊗ |0>
f(|110>) = |1> ⊗ |1> ⊗ |1>
f(|111>) = |1> ⊗ |1> ⊗ |0>

If you understand the CNOT gate, you can understand why this is our function. Think of this like a truth table. Since our control qubit is the most significant qubit, qubit[2], only when that qubit is |1> will the least significant qubit, qubit[0], be negated.

Expand this out to our normalized probability vector form...

f(|000>) = [ 1, 0 ] ⊗ [ 1, 0 ] ⊗ [ 1, 0 ]
f(|001>) = [ 1, 0 ] ⊗ [ 1, 0 ] ⊗ [ 0, 1 ]
f(|010>) = [ 1, 0 ] ⊗ [ 0, 1 ] ⊗ [ 1, 0 ]
f(|011>) = [ 1, 0 ] ⊗ [ 0, 1 ] ⊗ [ 0, 1 ]
f(|100>) = [ 0, 1 ] ⊗ [ 1, 0 ] ⊗ [ 0, 1 ]
f(|101>) = [ 0, 1 ] ⊗ [ 1, 0 ] ⊗ [ 1, 0 ]
f(|110>) = [ 0, 1 ] ⊗ [ 0, 1 ] ⊗ [ 0, 1 ]
f(|111>) = [ 0, 1 ] ⊗ [ 0, 1 ] ⊗ [ 1, 0 ]

Now let's actually solve this...

f(|000>) = [ 1, 0, 0, 0, 0, 0, 0, 0 ]
f(|001>) = [ 0, 1, 0, 0, 0, 0, 0, 0 ]
f(|010>) = [ 0, 0, 1, 0, 0, 0, 0, 0 ]
f(|011>) = [ 0, 0, 0, 1, 0, 0, 0, 0 ]
f(|100>) = [ 0, 0, 0, 0, 0, 1, 0, 0 ]
f(|101>) = [ 0, 0, 0, 0, 1, 0, 0, 0 ]
f(|110>) = [ 0, 0, 0, 0, 0, 0, 0, 1 ]
f(|111>) = [ 0, 0, 0, 0, 0, 0, 1, 0 ]

Let's make these the columns of our lgm matrix.

lgm =
[ 1, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 1, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]
[ 0, 0, 0, 0, 1, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 1 ]
[ 0, 0, 0, 0, 0, 0, 1, 0 ]

Now if the matrix-multiply our entire system matrix, sys, by our logic gate matrix, lgm, our result will be the effect of applying the CNOT gate to qubit[2] and qubit[0] where qubit[2] is the control qubit.


Why time complexity of union-find is $O(lgN)$ with only "Union by Rank"? I'm studying time complexity of Union-Find data structure.

I saw time complexity of union and find function depends on some conditions.

without anything: $O(N)$
with Union by Rank: $O(\log N)$
with Path Compression: $O(\alpha(N))$ which is inverse Ackermann function.

I understood $O(N)$ because of skewed tree of disjoint set. But, I cannot understand $O(\log N)$. I looked on Wikipedia and Stack Overflow, but I couldn't find it. How can I prove second time complexity?

Firstly, here is the precise statement of the case 2 in OP's question.

  A sequence of m MAKE-SET, UNION, and FIND operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank in worst-case time $O(m\log_2 n)$.

In fact, it is trivial to see that the MAKE-SET and UNION operations run in $O(1)$ time. So the question is really about the time-complexity of the FIND operation.

Here are the properties of the disjoint-set forest you can prove.

Given any node $u$ that has been added to the set of union-find data structure, the ranks of the nodes in a path from $u$ to its root is strictly increasing.
A node $u$ which is root of a sub-tree with rank $r$ has at least $2^r$ nodes. (This fact can be proved by induction on $r$).
Every node has rank at most $\log_2 n$.

With properties 1 and 3, it should be easy to prove the desired time complexity.

The above explanation follows roughly the section 21.4 in Introduction To Algorithms, third edition by CLRS. Readers are encouraged to read the chapter 21 of that book.


Oven cooking queue problem: need help to determine its nature CS community!

I'm more of a practical programmer than a computer scientist, so I need your help to find a solution (or at least point me into the right direction) to an extremely practical problem related to cooking food in the oven.

Problem

I have N ovens and I have multiple various ingredients to cook in them.
Each ingredient has certain preparation (e.g. peel the potato, cut the meat, etc.) time and oven cooking time. At time 0 we start preparing ingredients and putting them into the oven to cook. I need an algorithm to find the most optimal arrangement for the queues of these N ovens, so that it takes minimum time to finish cooking all of the ingredients.

Additional note: each ingredient is cooked at specific temperature, so no 2 ingredients can be cooked simultaneously.

Example

2 ovens: O1, O2

7 ingredients:

A (PT 200, CT 400)

B (PT 180, CT 380)

C (PT 80, CT 240)

D (PT 60, CT 180)

E (PT 40, CT 120)

F (PT 20, CT 60)

G (PT 0, CT 20)

Where: PT - preparation time, minutes; CT - cooking time, minutes.

I solved it simply visually and found that optimal solution looks like this:

Time: action

0: put G in O1
20: take G from O1, put F in O1
40: put E in O2
80: take F from O1, put C in O1
160: put take E from O2, put D in O2
320: take C from O1, put A in O1
340: take D from O2, put B in O2
720, take A from O1, take B from O2 -- finished in 720 min!

Visually it looks like this:

Conclusion

In a search for an answer I found that problem cannot be solved by simply sorting ingredients in some order, as changing the timing on one of the ingredients can dramatically change the cooking order: sometimes ingredients need to wait for certain time, even though they are prepared and ready to be cooked -- the priority queue can change completely!

Question

Whoever sees any similarities with certain mathematical or CS problems (Knapsack? Packing?), please point me in the right direction. Or, preferably, point me to the solution, which surely must exist for such an obvious problem.

Thank you!

This problem is NP-hard: it is a more general version of Minimum Multiprocessor Scheduling. You should not expect efficient algorithms that compute the optimal solution in all cases.

The main difficulty is finding out what is the "best" oven in which to cook an ingredient. Once you know (in some way or the other) which ingredients should go in which oven, you can not go wrong by queueing them based on their preparation time.

So one way to compute the best solution is as follows: perform a cycle in which you try all possible assignments of $K$ ingredients to $N$ ovens, which is $N^K$ possibilities. For each of these possibilities, compute the solution based on queueing by preparation time in each oven. The best of all solutions you generate is the optimal solution. This of course will only be practical if $N$ is very small (like in your example) and $K$ is also small.


Closure properties of the class of inherently ambiguous CFLs is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are answered?

Reversal

The class of inherently ambiguous context-free languages is closed under reversal (exercise).

Intersection

The class of inherently ambiguous context-free languages is not closed under intersection. Indeed, take some inherently ambiguous context-free language $L$. Now take $L'$ to be a copy of $L$ which uses a different alphabet. Then $L \cap L' = \emptyset$.

Complementation

The class of inherently ambiguous context-free languages is not closed under complementation. Indeed, consider the Goldstine language
$$ G = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i \text{ for some } i \}. $$
This language is context-free and inherently ambiguous (see slides of Cyril Nicaud). Also,
$$
\overline{G} \cap \Sigma^* b = \{ aba^2\cdots a^p b : p \geq 1 \},
$$
which isn't even context-free.

Union

The class of inherently ambiguous context-free languages is not closed under union. Indeed, the following variant of the Goldstine language is probably also context-free and inherently ambiguous:
$$ G' = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i+1 \text{ for some } i \}. $$
However, $G \cup G' = (a^*b)^+$.

Iteration (Kleene star)

The class of inherently ambiguous context-free languages is not closed under Kleene star. Indeed, consider the following language:
$$
\Omega_3 = \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \}.
$$
Here $|u|_a$ is the number of $a$s in $u$. This language is context-free and inherently ambiguous (see the slides of Cyril Nicaud). However, $\Omega_3^* = \{a,b,c\}^*$.

Concatenation

The class of inherently ambiguous context-free languages is not closed under concatenation. Indeed, the following variants of $\Omega_3$ are probably also context-free and inherently ambiguous:
$$
\begin{align*}
\Omega'_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \text{ or } u = \epsilon \}, \\
\Omega''_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b+1 \text{ or } |u|_a \neq |u|_c+1 \text{ or } u = \epsilon \}.
\end{align*}
$$
However, $\Omega'_3 \Omega''_3 = \{a,b,c\}^*$.


Proving NP-completeness of a surveilled graph problem So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a function.

We can call this graph instance $\textit{consistent}$ if we can find a subset $B \subseteq V$ \ $A$ such that for any $u \in A$, $ g(u) = |N(u)\cap B|$ (in which $N(u)$ obviously denotes the neighbourhood of vertex $u$).

How would one go about proving that the problem of determining consistency of a graph $(V,E,A,g)$ is NP-complete? Would a reduction from SUBSET-SUM using slack variables of some type work?

Thanks!

Let $\langle \mathcal{S}, \mathcal{I} \rangle$ be an instance of exact cover. Here $\mathcal{I}$ is a set of items and $\mathcal{S} \subseteq 2^\mathcal{I}$ is a collection of subsets of $\mathcal{I}$.

The goal is to decide whether there is a subset $S$ of $\mathcal{S}$ such that every item in $\mathcal{I}$ belongs to exactly one set in $S$. This is a well-known NP-complete problem.

To reduce exact cover to your problem create a graph $G = (V, E, A, g)$ as follows:

$V = \mathcal{S} \cup \mathcal{I}$.
$E = \{ (u,v) \in \mathcal{S} \times \mathcal{I} \mid v \in u \}$.
$A = \mathcal{I}$
$\forall u \in a, g(u)=1$.

If $S$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$, then $B=S$ is a solution for your original problem since $S \cap \mathcal{I} = B \cap A = \emptyset$ and each item in $\mathcal{I}=A$ has exactly one neighbor in $S = B$.

On the other hand, a solution $B$ to your original problem is such that $B \cap A = B \cap \mathcal{I} = \emptyset$. Hence $B \subseteq \mathcal{S}$ and eacn item in $A = \mathcal{I}$ has exactly one neighbor in $B$. Therefore $B$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$.


Equivalence of machine $M$ in $BPP$ and $EXP$ Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists equivalent machine in $EXP$. I cannot see how the $EXP$-machine is equivalent.

If we run machine $A$ on $x$ it can accept a word $x$ with probability $0.5$. Now we can run our $EXP$-machine. It try every possible toin-cosses-result so it compute an average probability of accepting of $x$.
I don't see why it works equivalently- even if the $EXP$-machine has coin-toesses as input, it should be random in any way.

You are confused about the definition of when a language is in a class. You show that a language $L\subseteq \{0,1\}^\ast$ is in $P$, for example, by describing a Turing Machine with the following properties:

It is deterministic
It runs in polynomial time
It solves $L$

The classes $BPP$ and $EXP$ have similar definitions. The Complexity Zoo has a (very long) list of all the complexity classes.

The proof you cite works by following the definition of $EXP$ very closely: to show that $L\in EXP$, it describes a Turing Machine which (1) is deterministic, (2) runs in exponential time and (3) solves $L$. Showing this is relatively straightforward: it simulates the random machine for all possible random seeds, counts how many of those computations accept and how many reject, and then acts accordingly. This new algorithm satisfies the three properties above: we now know that there is a Turing Machine which is deterministic, runs in exponential time, and solves $L$. Now the proof is done. $\square$

The confusion may be that you do not need an equivalent machine (one that is also random, or that also sometimes errs, etc.), you only need to look closely at the definition of $EXP$ (which again, you can find in The Zoo), and then show that $L$ satisfies all the requirements. Also, $BPP$ is a class of languages, not of machines. Consider for example the complexity class $Sparse$, which consists of all languages that have a certain density, but which are not necessarily computable by any Turing Machine; the definition is not at all tied to the notion of computation.


Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$ Hope you had a fantastic christmas break :)
I am trying to find an algorithm in polynomial time that finds the shortest arithmetical expression (the one with the least amount of 1 symbols) to express any natural number, while only using the elements of $\Sigma=\{(,),1,+,\times\}$.
As an example there are multiple ways to express $6\in \mathbb{N}$. but we want the one with the least amount of 1 symbols.
1+1+1+1+1+1
(1+1)*(1+1+1)
(1+1)*1+1+1+1+1
Algorithm:
My current algorithm GetExpression(n) uses a recursive mechanism to get the expression for a number $n\in \mathbb{N}$.

if $n=1$ return "1"
trying to find a divider for n (for loop from i=2 to $\lceil \sqrt{n} \rceil$ with trying $n\mod i=0$)
if there is a divider return "(GetExpression(divider)$\times$GetExpression($\frac{n}{divider}$))"
if n is prime return "(1+GetExpresion(n-1))"

Runtime:
Due to the loop trying to find the divider going in $\mathcal{O}(n)$ and both options of recursive calls having $0<\alpha_1=\frac{n-1}{n}<1$ (in the prime case) and $0<\alpha_2+\alpha_3<1$ (in the non-prime case) we can use the master theorem to see, that our agorithm runs in $\mathcal{O}(n)$ (since we only make one of both options at a time we dont need to look for $\sum_{i=1}^3\alpha_i<1$ but only for $\alpha_1<1$ and $\sum_{i=2}^3\alpha_i<1$)
(actually we need to make a special case for $divider=2$ since there couldbe $\alpha_2+\alpha_3=\frac{1}{2}+\frac{2}{4}=1$ if $n=4$ but we don't care right now).
Correctness:
My problem is how to proof that this algorithm is correct. I was thinking about a induction but i have no glue how to build it.

You can't prove that your algorithm is correct because it isn't. First counter example is n = 46. If we don't bother writing 2 = 1+1 to make it more readable, your algorithm gives
46 = 2 * (1 + 2 * (1 + 2 * (1 + 2 * 2)))

which uses 13 1's.
A better solution is
46 = 1 + ((1 + 2) * ((1 + 2) * (1 + 2 * 2))

which uses only 12 1's.
The difference is bigger for n = 235 (difference 2), n = 649 (difference 3), n = 1,081 (difference = 4), n = 7,849 (difference = 5), n = 33,793 (difference = 6), n = 221,617 (difference = 8).


TM that accepts all strings is recognizable or not? Lets say we have the following language $L = \{\text{$M$ is a TM such that $M$ accepts all strings}\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct could anyone provide me with a proof?

My current reasoning is that since the set of all strings is infinite, the "recognizer" TM will never be able to test all strings thus never be able to accept a given TM.

Please give me your thoughts on this.

Your intuition is correct: your $L$ is unrecognizable. Here's a hint on how to proceed.

If we define $A_\text{TM}= \{(\langle M\rangle,w)\mid M \text{ accepts }w\}$, then it's known that its complement, $\overline{A_\text{TM}}$, is unreconizable so if we can construct a mapping reduction $\overline{A_\text{TM}}\le_M L$, then we'll have shown that $L$ is unrecognizable.

Define the mapping $f(\langle M\rangle, w)\rightarrow \langle N\rangle$ where the TM $N$ depends on $M$ and $w$ and is defined by

N(x) =
   run M on w for |x| moves
   if M hasn't accepted yet,
      accept

The key idea here is that if $M$ accepts $w$, then it will do so in $k$ moves, for some number $k$, so if $M$ accepts $w$, then $N$ will accept all and only those strings of length less than $k$, and so the language of $N$ will be $L(N) = \Sigma^{k-1}$. On the other hand, if $M$ doesn't accept $w$, then $N$ will accept all strings.

With this hint, you should be able to show that $(\langle M\rangle, w)\in \overline{A_\text{TM}}\Longleftrightarrow\langle N\rangle\in L$, which is the reduction we need.


Dijkstra's algorithm for undirected graphs with negative edges INPUT: "an undirected, weighted graph (negative weights allowed)"

Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work?
As far as i understood it only fails by directed graphs in case of negative edges.
Am i right ?

Think about a "triangle"(3-clique): an undirected graph $G(V,E)$ with three vertices $a,b,c$ and edges $(a,b),(b,c),(c,a)$. Assign cost $w_{a,b} = 1$, $w_{b,c} = -100$, $w_{c,a} = 100$. If we want to find the shortest path from $a$ to $b$, Dijikstra greedily chooses $b$ via edge $(a,b)$, which has cost one. However, the shortest path from $a$ to $b$ is $(a,c),(c,b)$, which has cost only 0.

In fact, the proof of the correctness of Dijikstra algorithm relies on the fact that all edges have non-negative weights such that the greedy algorithm always stays ahead.


Amount of information in scaled-down images Does an image that is scaled down lose more Information when
calculating averages of pixels rather than selecting single pixels?

One way to scale down an image is to replace 2x2 pixel blocks with the average of those four pixels, the other way is to just select the top-left pixel (or any other) instead.

Averaging is done by summation and integer division. We reduce the Problem to just scaling 2x2 images down to 1x1 images. For black and white images there are 16 possible images, 15 of those will be black and one will be white
thus the entropy of the scaled down image is 0.337 bits. For grayscale images with 5bits per pixel results
in 4.2524 bits, with 6bits per pixel we end up at 5.251 bits.

Does averaging really lose more information than just selecting top-left pixels?

I'm aware that you lose some information due to rounding but my calculations don't seem to converge so rounding wouldn't explain everything.

Averaging-and-truncation certainly loses more information. It is not because you are not preserving any specific pixel: it is because you are taking an even probability distribution and giving it a strong bias in one direction.

If I have understood you correctly, you have taken the 16 possible 2x2 images and transformed one of them to white and 15 of them to black. This 15:1 split is about as bad as you can get! It destroys information, and it is the reason why your results are so bad compared to the "take top left corner".

The nearer you get to an "8:8" split, the less information you will lose. So try averaging and rounding: what I think you call "taking the median". This will split 11:5, which is less bad. It is still not very good, because the 6 cases of "2 black, 2 white pixels" all have to be translated either to black or to white - that is why you can only get 11:5 rather than the ideal 8:8 between black and white outcomes. [It would be interesting to try "use the majority value if there is a majority value; if not, use the top left"].

If you try $3\times 3$ blocks then either a clear majority of pixels will be white or a clear majority of pixels will be black: a straight 256:256 split. This is the best possible outcome, and if you simulate it then you should find it leads to the least information loss.