How to convert DFA to regular expression using arden's rule I generally use state removal method to convert DFA to regular expressions. But I want to try other methods like using algebraic methods and arden's rule.

How to solve a DFA with multiple final states using algebraic method?
I refered this link
https://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions and arrived at this solution which I think is wrong since a can be followed by only a or c not b.

I used state removal method and arrived at below regular expression which seems to be correct as the language won't contain ab.

Your equations are wrong; your solution works for the reversed arrows. You should be solving the following system:
$$
q_0 = (b+c)q_0 + aq_1 + \epsilon \\
q_1 = cq_0 + aq_1 + \epsilon
$$


Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent I've really been thinking about and working on this problem for a while, and I would appreciate if someone could offer any help towards the solution.

  Consider the following family of hash functions that map $w$-bit
  numbers to $l$-bit numbers (i.e. the range is $\{0,...,m-1\}$ where
   $m=2^l$):

  $\mathcal{H} = \{h_{A,b}|A\in \{0,1\}^{l\times w}, b \in
 \{0,1\}^{l\times 1}\}$, where $h_{A,b}(x) = Ax+b\mod 2$

  Show that $\mathcal{H}$ is $2$-wise independent but not $3$-wise
  independent ($\mathcal{H}$ is $k$-wise independent if for any $k$
  inputs $x_1,...,x_k$ and hash values $v_1,...,v_k$,
  $\Pr\limits_{h\in\mathcal{H}} \left( \bigwedge\limits_{1\le i\le k}
 h(x_i)=v_i \right)=m^{-k} $).

I'm first trying to show that $\mathcal{H}$ is $2$-wise independent. So consider any two inputs $x_1, x_2$ and hash values $v_1,v_2$. Then it's required that $\Pr \left( h(x_1)=v_1 \wedge h(x_2)=v_2 \right)=\frac{1}{m^2}$.

$$\Pr \left( h(x_1)=v_1 \wedge h(x_2)=v_2\right)$$

$$\Rightarrow \Pr\left( Ax_1+b = v_1 \mod 2\wedge Ax_2+b=v_2 \mod 2\right)$$

What about this equation shows that the probability is $\frac{1}{m^2}$? If we were trying to show $3$-wise independence, we would have:

$$\Pr\left( Ax_1+b = v_1 \mod 2 \wedge Ax_2+b=v_2 \mod 2 \wedge Ax_3+b=v_3 \mod 2\right)$$

Why is this not $\frac{1}{m^3}$?

I just don't know how to evaluate an expression like $\Pr\left( Ax_1+b = v_1 \mod 2 \wedge Ax_2+b=v_2 \mod 2 \wedge Ax_3+b=v_3 \mod 2\right)$. I've tried searching online for similar problems, but none seem to help with solving this one specifically.

Hint for showing 2-wise independence: Given $x_1,x_2$ and $v_1,v_2$, write the desired equations in a different way:
$$
b = v_1 - Ax_1, \\
A(x_2-x_1) = v_2 - v_1.
$$

Regarding 3-wise independence: I could be missing something, but it seems that the family is 3-wise independent.

Hint for refuting 4-wise independence: Take $x_3 = x_1 + x_2$ and $x_4 = 0$.


Can we test whether two vertices are connected in time linear in the number of nodes? Consider the problem:

  Given an undirected graph and two of its vertices, is there a path between them?

I often read that this problem can be solved in linear time in the number of vertices! I am not sure why this claim holds.

Can this really be done in linear time (not amortized) without preprocessing?

It is not possible to decide $s$-$t$ connectivity in $O(n)$, in the adjacency matrix model. In fact, here is an $\Omega(n^2)$ lower bound. Let $|S| = |T| = n/2$ be a partition of the vertex set, and choose some $s \in S$ and $t \in T$. Consider the graph in which $S$ and $T$ are both cliques. In this graph $t$ is not reachable from $s$. If we add any edge from $S$ to $T$, then $t$ is reachable from $s$. A simple adversary argument shows that any algorithm that decides where $t$ is reachable from $s$ has to potentially check all $|S| \cdot |T| = n^2/4$ potential edges: if it didn't query some edge $(x,y)$, then it wouldn't be able to distinguish the case in which there is no edge from $S$ to $T$ (and so $t$ is not reachable from $s$) from the case in which $(x,y)$ is the unique edge from $S$ to $T$ (and so $t$ is reachable from $s$).


pattern search with k-mismatch I have used Rabin Karp Rolling Hash for searching a pattern $P$ in a text $T$. Now I am allowing $k$-mismatches, but not able to do a faster implementation.

I tried modifying RK algorithm by splitting the pattern into few blocks, but that does not improve the speed.

I'm trying to use locality sensitive hashing, but not sure how could I calculate hash with sliding window manner. Any help would be appreciated. For my case, the length of $P$ is 50~75 and $T$ is 100~150.

Split into segments

One simple approach is to split $P$ into $k+1$ pieces, say $P = P_0 P_1 \cdots P_k$, as @j_random_hacker suggests.  You can make each of the $P_i$ be of approximately equal length, though this is not required.  Then, for each $i$, search for all instances of $P_i$ in $T$ (with no mismatches), and see if it can extend to an instance of $P$ with at most $k$ mismatches.  If there is a solution for your original problem, then this procedure will find it.

For non-degenerate cases, if every $|P_i|$ is large compared to $\log_{|\Sigma|} |T|$ and $P,T$ are more or less random, we can expect that there will be few "false matches" of a piece, and consequently  we can expect that the running time will be approximately $O(k \cdot |T|)$.  Thus this should be pretty fast in your specific situation.

This approach allows you to use any fast string-matching algorithm to search for instances of $P_i$ in $T$; e.g., you can use Rabin-Karp or any other existing algorithm -- this is nice because you can re-use existing well-tuned string matching libraries.  This approach might be not-too-difficult to implement and fairly efficient in practice.

Levenshtein automaton

You can build a NFA (nondeterministic finite-state automaton) to recognize instances of $P$ with at most $k$ mismatches.  In particular, the NFA recognizes all strings $S$ that end with something that matches $P$ with at most $k$ mismatches.  The NFA has $(k+1) \times |P|$ states: each state is of the form $(m,i)$, where $m$ counts the number of mismatches so far and $i$ counts the length of the prefix of $P$ that has been matched so far.

You can convert this NFA to a DFA.  Heuristically, I expect the size of the DFA to be pretty small, say $O(k \cdot |P|)$, though I don't know of any proof of this.  Next, you can run the DFA along the text $T$, to find the first place where there is a match, which takes $O(|T|)$ time.

This might be fast if $k$ is not too large.  If $k$ gets too large, it's possible the DFA will be enormous and the approach might fail.  This is probably most useful if you plan to re-use the same pattern $P$ with many different texts $T$, or if $T$ is far longer than $P$.  I wouldn't recommend it for your specific situation.

I have no proof that the resulting DFA will be small.  See also Levenshtein automata, which consider the far harder problem of building a DFA to recognize all strings $S$ that end with something that has edit distance $\le k$ to $P$ (i.e., they allow for at most $k$ mismatches, insertions, and/or deletions, in total).  The resulting DFA is much more complex, yet there are amazing algorithms to build the edit-distance DFA in running time that is linear in $|P|$ (but possibly exponential in $k$).  Your problem is considerably easier and will probably lead to DFA that are significantly smaller.


How to design xml schema for digital circuits? how can i design XML Schema for logical and digital circuits?

i cant find any help or manual for this work

for example i have a digital circuits with AND OR NOR ,... gates

now i want design xml and schema for that

thanks for help

soryy for bad english

A simple example.

Assume the following circuit in symbolic notation:

Cir = ((A OR B) AND (C OR D)) OR (NOT(D) AND F), where OR , AND, NOT etc can be realized with serial/parallel connections etc..

XML scheme proposition:

<circuit>
    <gate-or>
        <element>
            <gate-and>
                <element>
                    <gate-or>
                        <element>A</element>
                        <element>B</element>
                    </gate-or>
                </element>
                <element>
                    <gate-or>
                        <element>C</element>
                        <element>D</element>
                    </gate-or>
                </element>
            </gate-and>
        </element>
        <element>
            <gate-and>
                <element>
                    <gate-not>D</gate-not>
                </element>
                <element>F</element>
            </gate-and>
        </element>
    </gate-or>
</circuit>

This is an example xml-scheme where the root element is circuit and can have gates or elements as children and each gate (eg gate-or or gate-and) can have elements as children etc..

Of course this is very verbose , a yaml or json representation scheme would be lighter


Maximum number of inversions that can be removed by swapping two elements? I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in advance!

Question

Suppose we exchange elements $a[i]$ and $a[j]$, where $j > i$, which are originally out of order.

For example, $a = [2,8,3,7,1,5,6]$ and we exchange the second and sixth elements, we have $[2,5,3,7,1,8,6]$.

The array has now fewer inversions. What is the maximum number of inversions that can be removed if we exchange $a[i]$ and $a[j]$?

My proposed answer

Take an array and sort it in reverse order. The first element would have the most inversions. We switch it with the last element and the number of inversions decrease drastically.

The maximum number of inversions would be $j-i+n-2$.

My concern

Since the question doesn't say anything about me being allowed to change the order of the array, I don't know if my proposed answer is the one they were aiming for.

The question is indeed not completely clear, but they definitely wanted you to search the "worst possible" array $a$ (the one leading to the largest number of removed inversions). Otherwise there is nothing to do - just look at the array and calculate the number of inversions resulting from the swap.

What is somewhat less clear is whether they also wanted you to optimize over $i$ and $j$. Your answer, which doesn't assume that, is on the safe side.

One thing you haven't shown is that your example leads to the maximal number of inversions being removed. The argument is very simple, but it's still needed for completeness.


Interpretation of Turing's statement on universal computers I'm currently reading a book about artificial intelligence and i frequently come across the concept of universal computers, as it is essential to understand the book i would like to know the meaning of author's statement referring to Turning's paper of 1936:

  If a type of computer can perform a certain bare minimum set of operations, then it's  universal in the sense that given enough resources, it can do anything that any other computer can do.

Maybe the above statement is on its own very clear, but i have difficulties to understand. I'm afraid i interpret the concept in a wrong way.

Consider a simple calculator we were using in school, how can we provide it with enough resources so it can do anything that any graphical calculator nowadays can do? We if add components to the existing computer then it wouldn't be the same computer as it used to be. So my conclusion is the term enough resources doesn't mean any physical alterations.

To understand what Turing means here, you first need to understand what Turing means when he uses the word "computer". He is not talking about any particular machine, but about someone or something that 'computes', where 'computing' means to transform inputs into outputs according to some specification or function.

The key difference between the everyday using of 'computer' and Turing's is the following: a 'computer' such as a pocket calculator or mobile phone consists of not only a 'computer' a la Turing, but also has an interface to this computer. Roughly, we can see this interface as a component that translates device input (touch screens, keys, etc.) to strings of 0's and 1's and translates this binary code back to device output (e.g. screen displays). This means that all the 'computer' has to do is compute on strings of 0's and 1's and leaves how to get input or present the output to the interface.

Now for the actual statement. What Turing says is the following:

If a computer can perform a certain (relatively simple) set of operations, we call it universal.
An universal computer can do anything another computer can do, given enough resources.

Part 1 should be clear. The 'resources' in part 2 is not very clear, but we can think a bit about what it means. Since a computer is something that only works with transforming binary code, the 'resources' of a computer are 'whatever is needed to perform this transformation on binary code'. What exactly are resources then depends on the type of computer: a mobile phone will need battery power to perform computations, while an engineer might be able to perform the same computations with a piece of paper and a good cup of coffee. Both of them will also need time to perform the computation.

We can now take a look at your calculator example. First of all, Turing's statement is only applicable if the simple calculators operations make it a universal computer. While a calculator is likely not universal, let's assume that it is for the moment. Then the computer 'inside'  the pocket calculator can do everything the computer 'inside' the graphical calculator can do, even though the graphical calculator can display things the pocket calculator cannot.

What you should realize is that the difference in displays is a difference in interfaces of devices, not of their computers. The pocket calculator may not be able to show you a function plot on the display, but the display can certainly show the coordinates of all points on the plot.


Computational Complexity of 'Generic'/'Relaxed' Horn 3SAT Horn 3SAT are described as the 3SAT with at most one positive literal. And its in P. What about the complexity of relaxed case of 2-Horn 3SAT i.e.

Each clause is in CNF, has exactly 3 literals, with at most 2 positive literals.

Can someone please help with the reference.

Schaefer's dichotomy theorem gives you the answer. Apply it and see what you get, and let us know.

Looking at the modern formulation, in your case $\Gamma$ contains the three relations $\lnot x \lor \lnot y \lor \lnot z, x \lor \lnot y \lor \lnot z, x \lor y \lor \lnot z$. For each of these relations $R$, you have to go over the list of polymorphisms, and check whether one of them is a polymorphism of $R$. For example, to check whether the binary AND function is a polymorphism of $\lnot x \lor \lnot y \lor \lnot z$, you have to check whether
$$
(\lnot x_1 \lor \lnot y_1 \lor \lnot z_1) \land (\lnot x_2 \lor \lnot y_2 \lor \lnot z_2) \\ \Longrightarrow \lnot (x_1 \land x_2) \lor \lnot (y_1 \land y_2) \lor \lnot (z_1 \land z_2).
$$
If every $R \in \Gamma$ has one of the six polymorphisms, then your problem is in P. Otherwise, it's NP-complete.


Having trouble in understanding the definition of a clique My definition says

  A clique is a graph that has an edge connecting every pair of vertices

but as I understand, an edge connects only two vertices. Like $A-B$.

If we want to connect three vertices, we need at least two edges. For example, $A-B-C$.

I don't understand how an edge can connect every pair of vertices.

Recalling that a clique is a subset $C$ of vertices of an undirected graph such that the subgraph induced by $C$ is fully connected. That is, every two distinct  vertices in $C$ are connected by a distinct edge of the graph. This means different edges, not the same.
So, on a clique $C$ containing $k$ vertices $v_1, v_2,..,v_k$, there are $\frac{k(k-1)}2$ edges connecting them, that is the number of possible unordered pairs on $k$ elements.
Example

As you can see in the previous picture, this is a clique on four vertices $\{{1,2,3,4}\}$, so there is a different edge connecting every edge (i.e. $(1,2)$,$(1,3)$,$(1,4)$,$(2,3)$,$(2,4)$,$(3,4)$).
You can count them and see that there are exactly $6 = \frac{4\times 3}{2}$ edges.


Why using Hyper-threading can lead to performance degradation I have read it at various places like this, that Hyper-threading leads to performance degradation.
I am unable to get why or how hyper-threading leads to degradation.
Why it is so that even when Hyper-threading allows the OS to utilize free resources does the degradation happens.
Though benchmarks does indicate hyper-threading as the culprit but can someone explain me the reason for this.
Thanks

It would seem that the answer, as per usual, has something to do with caches. Since hyper-threads utilize the same L1 and L2 caches, one hyper-thread can trash another's caches. In the worst case the threads take turns trashing the other's cache and performance degrades as the caches are re-filled only to be trashed again.

Of course, this is likely very workload specific, which would explain why the problem is mostly seen on servers.

It is also worth noting that the answer depends in part on what you mean by "performance." For example, in real-time systems your performance metric is predictability instead of throughput, which hyper-threading negatively impacts by introducing unpredictable stalls.


CPU sending and recieve Data? I am looking for an answer regarding the CPU read and write. We know there are two clocks that are working in the computer system, one is the peripheral clock and the other is the CPU own clock on which its control systems are working. I am familiar with the clock domain crossing but I dont understand how the CPU read and write data working on different clocks.
For example the CPU sends the data to be written on the data bus and address on the address bus. Since the rest of the peripherals are working on their own clocks such as PCI or other standards, Now the CPU which is working on its own clock will execute the next instruction send the address again on the address bus and the data on the data bus to the same peripheral but data bits have still not been read by the peripheral so doesnt the data will be lost in this process or is there any mechanism of handling this situation ?

That's why buffers are used.

While the transfer is in progress the peripheral writes the data into a buffer and the cpu ignores it and just works on its own clock.

Then when the transfer to the buffer is complete the peripheral will issue an interrupt (or other toggle a transfer complete pin) and the cpu will read from the buffer and if applicable let the next transfer start.

The buffer used can be the RAM this is often referred to as Direct Memory Access. The peripheral is attached to the memory bus and can issue reads and writes to ram directly.


Is there a program to solve a metric TSP for 80 edges at optimum? i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum.

But when i'm finished, i'd like to check my solution but i don't know how. So i thought about using a computer-program to find the optimal solution to see, if my solution is within the 3/2-range.

i am not quite sure, if this is really possible or how long it might take. if it would take less than a month, i think, it would be worth a try.

It should be no problem to solve this instance with an integer linear programming based approach. You could try the online interface to the Concorde TSP solver.


How to find how many times an object's path crosses another? I have several hundred objects that will move in a fixed area throughout the day.  Frequently the objects will cross over another object's path, either at the same time (eg. a collision) or within a few seconds or minutes, the time window tolerance.  How can I determine how many times that happens throughout a fixed period of time, let's say in a day?

For example, to visualize it on a simple level, let's say I have 2 points, A & B, arranged in a north-south and east-west configuration:

         (A) - Loc 1

              |
              |

Loc 3---------------------- (B) Loc 4

              |
              |
            Loc 2

Object A moves only from Loc 1 to Loc 2 throughout a given period of time.  Likewise Object B only moves from Loc 3 to Loc 4 during that same period of time.  They cross paths at the center.  One could just calculate the speed of A and figure out when it hits the location of the path cross, and also do that with B.  Then simply determine when those cross point time windows are close.  However that logic breaks down when I have hundreds of objects, variable indirect paths, and changing speeds.

What I am given at the end of the day is the path of each object, timestamps along the path, stops and times.  Is there a straightforward way or algorithm to determine how many times one path crossed another during a time window tolerance?

This can be done by what I'd call "accelerated replay" (I'm making up this term).

Let's suppose the movement of each object is piecewise linear: each object moves in a straight line at a constant speed for a while, then changes direction and moves in a different direction at a different speed, etc.  So, object $i$'s path can be specified a sequence of times $t_{i,0},t_{i,1},\dots,t_{i,n}$ at which the object changes direction; between times $t_{i,j}$ to $t_{i,j+1}$, the object is moving in a straight line (with known endpoints) at a constant speed.  The algorithm can be generalized to allow each individual piece of the path to be curved or other shapes as well, but it's easiest to describe in this setting.

So, let's take the union of all of the times $t_{i,j}$ and sort them.  In this way, we get a set of "events", where each "event" corresponds to an object changing direction/speed.  Now, we're going to replay all of the object movements.  However, we're going to "fast forward" through all of the times that fall between two adjacent events.  In other words, we're going to iterate through the events in time order.

At a single step of the algorithm, we're going to be processing a particular event, say the event at time $t_{i,j}$ where object $i$ changes direction.  We know the line segment that each of the other objects are currently on; and we know the line segment that object $i$ will travel on after time $t_{i,j}$.  So, for each other object $i'$, compute the location where the lines for objects $i$ and $i'$ intersect, check the time when that will happen, and check whether that time is before the end time for both line segments; if so, you've found a cross-over.  Notice that finding the intersection point of two line segments can be done in constant time ($O(1)$ time).  Once you've done that, you've taken into account all cross-overs that can occur until the next event.  So, no need to continue simulating what happens in any future time, until the next event.  So, fast-forward to the next event, and then do the same thing for the next event.

The total running time will be $O(nm)$, where $n$ is the number of objects and $m$ is the total number of events.  Or, if you expect $q$ events per object (i.e., $q$ changes of direction), then the total running time will be $O(n^2q)$.  Since you have only a few hundred objects, that should be quite reasonable.

It's plausible to me that it might be possible to reduce this to something more like $O(nq \log n)$, using techniques from computational geometry (e.g., Shamos-Hoey etc.), if that were really necessary -- but I haven't tried to think about whether that's possible, as given the numbers you listed in your question, the algorithm above should be fine.

If you want to find "points of closest approach" instead of "crossovers", it's easy to adjust the above algorithm to do that.  Given two line segments, it is easy to find their point of closest approach in $O(1)$ time, so then you just apply the same ideas as before.  If you want to deal with curved trajectories, that is also possible; if you have two curved lines that are parts of a circle, it is also possible to find whether they intersect in $O(1)$ time using some trigonometry, so again you can generalize the above algorithm to handle that as well.

There are probably many pragmatic ways one could speed this up, e.g., by using quadtrees to separate the plane into multiple regions and map each part of the path to the region(s) it visits, and then only look for crossovers within each region.


Why is static-single assignment preferred over continuation passing style in many industry-used compilers? According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects using continuation-passing style (CPS) is a bit lacking in comparison.

I have this notion that CPS is preferred by compilers and interpreters that implement primarily functional languages -- particularly, Haskell and Scheme seem to have strong inclinations towards CPS style due to the restrictions on mutation or need for first-class continuation support (I would guess that Smalltalk would possibly need this as well). The major literature that I've encountered that uses CPS seems to be those that are primarily working on Scheme or are related to Scheme in some respect.

Is there any particular reason why SSA is used in industry besides momentum of adoption? SSA and CPS have a close relationship; that means that it would be easy to state either in terms of another, but perhaps the information representation would be less compact or less efficient for CPS.

I imagine many compiler implementers for typical imperative languages simply weren't that familiar with CPS and CPS-based compilation techniques. In the functional programming community both CPS and CPS-based compilation are very well-known techniques - the latter from Guy Steele's work. Nevertheless, even in the FP community, most compilers don't use CPS-based techniques for compilation unless the language itself supports control operators like call/cc.  Something more like Administrative Normal Form (ANF) (sometimes also referred to as Monadic Normal Form which is intimately related for reasons that will become clear) is used which has an even tighter relationship to SSA than CPS does.

If I remember correctly, administrative normal form gets its name from the fact that CPS-based compilation can lead to beta-redexes in the intermediate code that didn't correspond to anything in the source code. These were referred to as "administrative redexes". These could reduced at compile-time, but there was a good amount of research on performing a CPS transform that would output code without the administrative redexes in the first place. The goal then was to produce output in a normal form where all "administrative" redexes were reduced, and this was the origin of Administrative Normal Form. It didn't take long to realize there wasn't a whole lot of benefit to viewing this as a(n optimization of a) two-step process: CPS-transform, reduce administrative redexes. In particular, administrative normal form looks rather like monadic-style as practiced (by hand) most notably in Haskell. The CPS transform can be understood as a conversion to monadic-style where you just happen to be using the CPS monad (so there's really multiple ways to "convert" to monadic-style corresponding to different evaluation orders). In general, though, you could be using a quite different monad, and so conversion to monadic-style and thus administrative normal form isn't really related to CPS in particular.

Nevertheless, there were some benefits to CPS versus ANF. In particular, there were certain optimizations that you could do in CPS with just standard optimizations, such as beta reducing, that required (seemingly) ad-hoc rules for ANF. From the monadic perspective, these rules correspond to commuting conversions. The upshot is now there is a theory that can explain what rules should be added and why. A recent paper gives a (new and) pretty clear description of this (from a logical perspective) and its related work section serves as a brief but decent survey of and references into the literature on the topics I mention.

The problem with CPS is tied to one of its main benefits. CPS transforming allows you to implement control operators like call/cc, but this means every non-local function call in the CPS intermediate code has to be treated as potentially performing control effects. If your language includes control operators, then this is just as it should be (though even then most functions probably aren't doing any control shenanigans). If your language doesn't include control operators, then there are global invariants on the use of continuations that are not evident locally. This means there are optimizations that are unsound to perform on general CPS code that would be sound to perform on this particularly well-behaved use of CPS. One way this manifests is in the change in precision of data and control flow analyses. (CPS transforming helps in some ways, hurts in others, though the ways it helps are mostly due to duplication rather than the CPS aspect itself.)1 You could, of course, add rules and adjust analyses to compensate for this (i.e. to exploit the global invariants), but then you've partially defeated one of the major benefits of CPS-based compilation which is that many (seemingly) special-purpose, ad-hoc optimizations become special-cases of general-purpose optimization (particularly beta reduction).

Ultimately, unless your language has control operators, there is usually not much reason to use a CPS-based compilation scheme. Once you compensate for the issues I mentioned above, you've typically eliminated the benefits of CPS-based compilation and produced something equivalent to not using CPS. At that point, CPS is just making convoluted looking intermediate code for not much benefit. An argument for CPS-based compilation from 2007 addresses some of these issues and presents some other benefits using a different form of CPS conversion. The things that paper brings up are covered in part by the (2017) paper I mentioned before.

1 Doesn't the equivalence between SSA and CPS make this more or less impossible? No. One of the first things the paper introducing this equivalence states is that the equivalence does not work for arbitrary CPS code, but it does work for the output of a CPS transform (which they define) for a language without control operators.


Hadoop MapReduce Word Counting Example In an example of the application of MapReduce provided by University of Utah, it says that Map() function emits <"hello", 1> every time it sees hello where the reduce function counts the number of instances "hello" occurs

My question is if this is the case, why isn't reduce doing <"hello", {1,1,1,1,1,1,1,1,1,1,1,1...}>, where each 1 is an instance Map() emits a key,value pair? In the example it wrote something like <"hello", (3,5,2,7)>, what does it mean?

Also, why do you need MapReduce to do this? I can just use an linked list on my computer.

Thanks

[...] it says that Map() function emits <"hello", 1> every time it sees hello where the reduce function counts the number of instances "hello" occurs

Not quite: It appears the mapper reads each file, counts the number of times a word appears, and outputs a single (word, count) pair per file, rather than per occurrence of the word. The reduce step then sums these. ("hello", 1) indicates that "hello" appeared once in a given file, ("hello", 3) indicates three appearances in a file, etc.

In the example for the reduce step, it appears four files were mapped, and that "hello" appeared 3 times in the first, 5 in the second, etc.

  Also, why do you need MapReduce to do this?

Via wiki MapReduce is "for processing parallelizable problems across huge datasets using a large number of computers[.]" Meaning, if your task is to count the number of times "hello" appears in four small documents, you likely don't need MapReduce. But if your task is to count the appearances of all words that appear in a large set of documents, then the only way to accomplish this is a practically useful time may require distributing across multiple processors.


Probabilistic r-way cut set algorithm I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph.

In this generalized version, instead of finding a set of edges that would break the graph into two components, it would break it in r components.
The approach used for the 2-way cut-set is to contract edges until only two vertices remain, and treat the edges remaining as the cut-set $C$.

The question then is

  Explain how the randomized min-cut algorithm can be used to find minimum r-way cut-sets, and bound the probability that it succeeds in one iteration.

My idea is to instead of stopping when there are r vertices remaining, instead of 2. But I am unable to bound its success probability.
A possible approach would be to find the probability of contracting an edge $\in C$. To do so, I define $|C|=k$, and based on that, $d(v)\ge k-r+2$, $\forall v \in V$. Thus, $|E|\ge \frac{(k-r+2) \cdot (n)}{2}$. But i can't remove this $k$ from the equation latter...

Any ideas here?

Your idea of stopping when there are $r$ vertices remaining is the correct approach. Now let us see how to bound the success probability of contracting one arbitrary edge not in a fixed $r$ way cut-sets.

Denote the graph by $(V,E)$ with $n=|V|$ and $m=|E|$.

Lemma: Let $C$ be an $r$-way minimum cut. The probability that a randomly selected edge is not in $C$ is at least
$$\frac{(n-r+1)(n-r)}{n(n-1)}.$$

Proof:
Let us count the number of elements in the following sets.

$$\begin{align}
V^{r-1}&=\{Q: Q \subseteq V\text{ such that } |Q| = r-1\}\\
S&=\{(e, Q):  Q\in V^{r-1}, e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
S_{e}&=\{\phantom{(e,\,} Q\phantom{)}: Q\in V^{r-1}\phantom{, e\in E } \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
S_{Q}&=\{\phantom{(}e\phantom{,Q)}: \phantom{Q\in V^{r-1},\,} e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \}\\
\end{align}$$

$|V^{r-1}|=\binom{n}{r-1}.$
$|S_e|=\binom{n-2}{r-1}$ for all $e\in V$.

Fix an arbitrary $Q\in V^{r-1}$. If we removes all edges not in $S_Q$, i.e., all edges whose endpoints are in $Q$ and all edges between a vertex in $Q$ and a vertex not in $Q$, there will be $r-1$ connected components of single vertex and one or more connected components in the remaining vertices. That means the set of all edges not in $S_Q$ is an $r$-way cut. Since the minimize size of an $r$-way cut is $k$, the number of edges not in $S_Q$ is no less than $k$, i.e, $|S_Q|\le m-k.$

Since $S$ is the disjoint union of all $S_e$, $e\in E$ as well as the disjoint union of all $S_Q$, $Q\in V^{r-1}$,
$$\binom{n-2}{r-1}m \le (m-k)\binom n{r-1},$$
which means,
$$1-\frac k{m} \ge\frac{\binom{n-2}{r-1}}{\binom n{r-1}}=\frac{(n-r+1)(n-r)}{n(n-1)},$$
where the left side is exactly the probability that a randomly selected edge from $E$ is not in $C$, a set of $k$ edges. QED.

Now that we have the lemma above, we can proceed just as in the book to compute the probability that any given minimum $r$-way cut $C$ survives all $n − r$ random successive edge contractions.

Exercise. (One minute or less) Check that the lemma and its proof above  specialize to the arguments given in the book in the case of $r=2$.


Infinite union of recursive languages I'm trying to figure out how to prove or disprove the following statement:

  Infinite union of recursive languages is recursively enumerable.

I know how to prove that infinite union of regular languages is not recursive, but I can't figure out how to prove the statement above. Intuition is telling me that the statement is true, but I'm not sure. Does anybody know how would I go about it?

Any help is greatly appreciated.

Choose an arbitrary language $L$ that is not RE. Denote $L_w=\{w\}$ the language containing a single word $w$. Clearly, $L=\bigcup_{w\in L} L_w$ is a union of infinitely many regular and recursive languages.


Is converting an ambiguous grammar to an unambiguous grammar computable? Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).

I assume that question is about derivation, otherwise the outcome does not change, but please read Yuval's comment for further details.

No it is not computable in the domain of your choice. There are inherently ambigous grammars, which are subset of context-free grammars. For the subset without inherently ambigous ones it is computable.

I like to point to thesis about ambiguous grammars, which is consistent with what I wrote, contains the same proof as TCS topic.

Since the problem of finding out whether grammar is inherently ambiguous is undecidable then you cannot build halting Turing Machine for such task. And yes, if you could built one it would be decidable.


How powerful are DFA with recursive calls? A family of deterministic finite automata of degree $n$ over an alphabet $Σ$, with   $\bigcap Σ = ∅$, consists of a set $\mathcal{A} =\{(K_i,Σ∪\{1,\dots,n\},δ_i,s_i,F_i) : 1 ≤ i ≤ n\}$ of deterministic finite automata. We fix implicitly a subscript function over $\mathcal{A}$, so that we can refer to the “$i$-th automaton   $\mathcal{A}_i = (K_i, Σ ∪ \{1, \dots, n\}, δ_i, s_i, F_i)$ of $\mathcal{A}$.”

Such a family performs the following processing:

Given an input $w ∈ Σ^∗$, the automaton $\mathcal{A}_1$ starts processing the input as usual, following the transitions in $δ_1$, until it reaches a transition of the form $δ_1(q, i) = p$, with $i ∈ \{1, \dots, n\}$. It then gives control to the automaton $\mathcal{A}_i$. The automaton $\mathcal{A}_i$ processes the not yet consumed input until it reaches a final state. When such a state is reached, $\mathcal{A}_i$ terminates and gives control back to $\mathcal{A}_1$, which resumes its operation from state $p$. $\mathcal{A}_1$ accepts the input iff it is in a final state when the end of the input is reached.
More generally, any automaton $\mathcal{A}_i$ can “call” some other automaton $\mathcal{A}_j$, which happens whenever $\mathcal{A}_i$ performs a transition of the form $δ_i(q, j) = p$. When such a transition happens, $\mathcal{A}_i$ gives control to $\mathcal{A}_j$. When the operation of $\mathcal{A}_j$ reaches a final state, $\mathcal{A}_i$ takes the control back and resume its operation starting from state $p$.

Call the whole system a deterministic finite automaton with recursive calls. It is in fact a usual finite automaton, with the added functionality that some edges represent a call to a different automaton instead of the acceptance of one input symbol.

How to show any language accepted by a deterministic finite automaton with recursive calls is context-free?
Are all the languages accepted by deterministic finite automata with recursive calls deterministic context-free?

Recursion is implemented on a computer using a stack, and your case is no different. You can use a stack to emulate the "call-and-return" semantics of your DFA with recursive calls, and the results will be a DPDA.


For every two decidable languages There is a turing machine that decides if they are equal I was wondering if this is true. I already proved that it is true for regular languages and I assume it is similar in context free languages (correct me if I am wrong), but what about languages in R that are not context-free?

Many problems that are decidable for regular languages become undecidable for context-free languages.

Even the intuitively simple problem $L = \Sigma^*$ is undecidable for context-free $L$, where $\Sigma$ is the alphabet of the language. That of course means that equality for context-free language $L=K$ is undecidable too.


Equivalence of different automata I  have a question about the equivalence of different automata. I looked up the similiar questions but sadly none of them are exactly, what I need or am looking for.

I know some of these are equivalent ( or not ) but for which language class pairs does a real inclusion apply?

DFA = NFA ⊋ ? DPDA ≠ PDA ⊋ ? LBA = DTM = NTM

I want to know, if this is correct or not.

Hint:" C is the class of all languages accepted by a C-type machine" - If this is important.

I apologize, if my question isn't in a correct format, therefor forgive me, I am trying to settle in.

Linear-bounded automata accept the class of context-sensitive languages. In contrast, Turing machine (deterministic as well as nondeterministic) accept the class of recursive languages. Every context-sensitive language is recursive, but the converse doesn't hold. For example, the halting problem for nondeterministic Turing machines running in space $n^2$ is not context-sensitive by the nondeterministic space hierarchy theorem.


What would you call an algorithm that finds $R$ % of the time the optimal solution to an NP-hard problem? According to Wikipedia,

A $\rho$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $\rho$ times the value, $OPT$, of an optimum solution.

I am interested in a situation where we would like to measure the performance of $A$ by how often it finds the optimal solution. For example, the algorithm $A$ finds the optimal value $R$ % of the time and finds a strictly larger (or less) solution $100-R$ % of the time. What would such algorithm be called? Is this notion known in the literature?

The idea you mention is covered in complexity theory by probabilistic classes.

The computational model they refer to is the probabilistic Turing machine, i.e. a Turing machine equipped with an additional read only tape that at the beginning of the computation contains an infinite sequence of symbols, independently chosen at random with uniform probability from the machine alphabet. Or, equivalently, a Turing machine that can flip a fair coin and read the answer in constant time.

Observe that due to the way that our computational model works, two executions on the same instance may give two different answers; for instance, one could define a machine that flips a coin and returns YES on heads and NO on tails.

We are interested in both the asymptotic worst-case running time and the probability that the answer given is actually correct. In literature, a vast amount of different classes are analyzed, they differ depending on various constraints that they impose on the solver.

Perhaps the most interesting of such classes, both from a theoretical and practical point of view is $\mathcal{BPP}$, defined as the class of languages decidable in polynomial time by a probabilistic Turing machine that, whether the answer is YES or NO, is guaranteed to give a correct answer with probability at least $2/3$. Notably, it is an open problem whether or not $\mathcal{P} = \mathcal{BPP}$.

A full discussion of probabilistic complexity theory would be too lengthy for SE, although there are plenty of sources available in both electronic and dead-tree form.


Clarification about conclusion of $Θ(nlogn)$? Why the first part of formula is equal to $2 * 2^2 + ... +  2^{log(n)} = 2^2 + 2^3 +...+  2^{log(n)} = 2^3 +...+  2^{log(n)} =... +2^{log(n)}$
What is the logic behind ($2^{log n +1} - 2{log n}$)  ?
I don't understand why $2n.log - (2^{log (n+1)} - 2)=Θ(nlogn)$ ? (Please explain what is math logic bihind it)

In the first part where the summation $\sum_{i=1}^{\log n}i2^i$, you see that whole summation can be written as that chain of summations (if you sum them all up you'll end up getting the first form on the top). Then you use the summation of power two's formula, i.e. $\sum_{i=0}^{n}2^i= 2^{n+1}-1$.

In the first line $=2+2^2+...+2^{log n}$ the formula is missing a -1 so the result will be $2^{\log n +1}-2$, the second one is missing a 2 so it will be $2^{\log n+1}-2^2$ and so on.

You can write $2^{\log n +1}$ as $2*2^{\log n}$ which is equal to $2*n$. I think what confuses you is that you think they wrote $2^{\log (n+1)}$ where as it is $2^{\log n +1}$.

As for why the $2n*\log n - (2^{\log n +1} -2) \in \Theta(nlogn)$, since $2n\log n \in \Theta(nlogn)$ and $2^{\log n + 1} = 2*n$ thus it is $\Theta(n)$ and from the property of asyptotic notation we can conclude $\Theta(nlogn)-\Theta(n) \in \Theta(nlogn)$.


What is the use of finding minimum number of straight lines to cover a set of points? There is that popular problem [1] [2] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D.

Even though I have scanned many papers, none of them has a clear motivation for the problem.

What is the use of solving this problem? Is there a paper that explains this?

Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case.  Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation).

However, you can look at the papers

Approximation algorithms for hitting objects with straight lines (Hassin & Megiddo) and
On the complexity of locating linear facilities in the plane (Megiddo & Tamir).

They claim, e.g.

  The problem of hitting objects in the plane with a minimum number of straight lines has a military application.  In many cases when a bomber attempts to destroy
  targets on the ground, protected by anti-aircraft  missiles, it has to spend as little time as possible close to the targets. Thus, careful planning of an air raid on a multi-target site (for example, a cluster of fuel tanks) calls for a minimum number of times a bomber has to fly across the site. Moreover, each pass has to be carried out as fast as possible, hence for each dive into the site there exists a straight line (a "stick") along which targets are destroyed. Another application
  (in three dimensions) is in medicine where radiotherapy is administered
  by inserting a minimum number of radioactive needles into a certain area of the body so as to achieve a required level of radiation.

And also:

  For example, we may view the problems faced by a planner who has to locate r (linear) segments of a new railroad system so as to minimize the average cost to the users who have to reach the tracks from a number of different small communities. Thus, a straight line or a line segment is of natural importance in this context. Sometimes such problems are easier than those with point facilities. For example, it is much easier to find a line, so as to minimize the sum of distances to it from a set of given points, than to find a single point with the same objective.


Different decompositions of the string in the pumping lemma proof Let $s = a^pb^{2p}$, now which one of those decomposition is correct:

$x=a^k$, $y=a^l$, $z=a^{p-k-l}b^{2p}$, where $k+l \leq p$

$x=a^{p-k}$, $y=a^k$, $z=b^{2p}$, where $1\leq k \leq p$

$x=\epsilon$, $y=a$, $z=a^{p-1}b^{2p}$

or are they the same? I've read in multiple answers that we don't get to pick the decomposition, but I'm not sure how to understand this, because to me all of those decompositions are legitimate.

Here is the statement of the pumping lemma:

  If $L$ is a regular language then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) for all $i \geq 0$, $xy^iz \in L$.

Here is the contrapositive, which is how you usually apply the lemma:

  Suppose that $L$ is a language such that for every $p$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w = xyz$ satisfying $|xy| \leq p$ and $y \neq \epsilon$, there exists $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

When you apply the lemma to show that a language is not regular, you have to consider all possible decompositions satisfying $|xy| \leq p$ and $y \neq \epsilon$. For each of them you need to find an $i$ such that $xy^iz \notin L$.


Are neural networks dynamical systems? Dynamical systems are those whose evolution can be described by a rule, evolves with time and is deterministic. In this context can I say that Neural networks have a rule of evolution which is the activation function $f(\text{sum of product of weights and features})$ ?

Are neural networks

dynamical systems,
linear or nonlinear dynamical systems?

Can somebody please shed some light on this?

The type of neural networks you have in mind (where each neuron is a threshold function taking on $0$ or $1$ values), with $n$ neurons is a dynamical system with state space $\{0,1\}^n$. After every tick of the clock, the neural network is in some new state, defined by the current values of its neurons.

Because the state space is discrete, I don't think your second question makes sense here. Linear vs. non-linear are terms applied to continuous-time dynamical systems.


Text detection in computer vision I'm curious about the way text recognition works in machine learning(or more generally, the question of object vs not object) in computer vision.

How are systems trained when the not-object data set is so much greater in quantity and apparently lacks structure?

One approach is having the algorithm first searches for a text box and once it finds one applies character recognition. Thus the initial classification comes down to "text" or "not text". "Not text" doesn't have any particular structure though and in fact almost everything is "not text"...so how is this dealt with?

What would the "not text" training set be? Random images? Clearly you need negative examples.

Many research projects use something called "hard negative mining": instead of training on all of the positive instances (e.g., "text" or "object") and all of the negative instance (e.g., "not text" or "not object"), they train on all of the positive instances and a carefully chosen subset of the negative instances.  In particular, they omit many of the 'obvious' negative instances and try to bias towards choosing negative instances that are more difficult to handle correctly.  It's not clear to me whether this is truly necessary or beneficial with modern machine learning methods, but it is something you could try, if you don't want to use all of the negative instances.

Yes, to create negative instances, you would normally sample random patches of the image (at a random location), subject to the restriction that they not have too much overlap with the actual text/objects.

For learning more about how to recognize object vs objectness, read about "objectness" detection or saliency detection.  For learning more about detecting text, you might be interested in the stroke width transform and the segmentation step in OCR.


In a DAG, longest path where every vertex has degree at most 2 I have a directed acyclic graph (DAG).  How I can find the longest path using only vertices with degree at most 2?

Currently, I try this

def all_simple_paths(g):
  for path in all_paths(g):
      if len(path) > 2:
          center_path = path[1:-1]
          nodes_degree = g.degree(center_path).values()
          if max(nodes_degree) <= 2:
              return path

but that might output any path, rather than the longest path.

First, remove all vertices whose degree is greater than 2 (i.e., their degree was greater than 2 in the original graph).  The result is a smaller DAG.  This can be done in linear time.

Now, find the longest path in the resulting DAG.  This can be done in linear time, too; see https://en.wikipedia.org/wiki/Longest_path_problem.


What is an approximation oracle? I have seen the term "approximation oracle" in computer science papers, sometimes parameterized with the letters $\alpha$ and $\beta$. What is an approximation oracle? How are such oracles used? I am somewhat familiar with the idea of an "oracle machine" in complexity theory.

An approximation oracle for an optimization problem $X$ is an oracle which accepts an instance of $X$ and returns an approximate optimum. The parameters $\alpha,\beta$ quantify the quality of the approximation.

Approximation oracles are a formal way of stating results of the following form:

  Given a polynomial time $C$-approximation algorithm for $X$, there is a polynomial time $f(C)$-approximation algorithm for $Y$.

Formally, we give a polynomial time $f(C)$-approximation algorithm for $Y$ which uses a $C$-approximation oracle for $X$.


Recurrence $f(n+1)=2f(n)-f(n-1)$ with initial values $f(0)=0,f(1)=1$ How do I solve the following recurrence?
$$
f(0) = 0, \quad f ((1)) = 1, \quad f((n+1)) = 2*f(n) - f(n-1).
$$

The normal recipe for solving a recurrence of this form goes like this:

Determine the polynomial corresponding to the recurrence, in your case $x^2 - 2x + 1$.
Determine the roots of the polynomial, in your case $x = 1$ (double root).
The solution is a linear combination of $1^n$ and $n1^n$ (more generally, if the roots are $\lambda_1,\ldots,\lambda_r$ with multiplicities $m_1,\ldots,m_r$, then you get a linear combination of $\lambda_1,\ldots,n^{m_1-1} \lambda_1,\ldots,\lambda_r,\ldots,n^{m_r-1}\lambda_r$).
Find the coefficients using the initial conditions. In your case, the general solution is $A + Bn$. Since $f(0) = 0$, we have $A = 0$, and since $f(1) = 1$, we have $A + B = 1$, hence $B = 1$. Thus the solution is $0 + 1 \cdot n = n$.

Here are two more equivalent ways to solve this.
Matrices. Notice that
$$
\begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} =
\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix}.
$$
It follows that
$$
\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix} = \begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}.
$$
The characteristic polynomial of the matrix is
$$
\det \begin{pmatrix} t-2 & 1 \\ -1 & t \end{pmatrix} = (t-2)t+1 = (t-1)^2,
$$
hence there is a single eigenvalue with multiplicity $2$. To determine the Jordan form of this matrix, which we denote by $A$, notice that
$$
\begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix} - I = \begin{pmatrix} 1 & -1 \\ 1 & -1 \end{pmatrix}
$$
has rank $1$, and so the Jordan form of $A$ is
$$
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.
$$
The above shows that one eigenvector of $A$ is $v = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$. A generalized eigenvector of the matrix is a vector $u$ such $(A-I)u = w$, for example $u = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$. It follows that
$$
\begin{pmatrix} 2 & -1 \\ 1& 0 \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{-1} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}
\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix}.
$$
It follows that
$$
\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^n
\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix}
\begin{pmatrix} 1 \\ 0 \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}
\begin{pmatrix} 0 \\ 1 \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} n \\ 1 \end{pmatrix} =
\begin{pmatrix} n+1 \\ n \end{pmatrix}.
$$
In particular, $f(n) = n$.
Generating functions. Let $P(x) = \sum_{n=0}^\infty f(n) x^n$. Then
\begin{align}
P(x) &= x + \sum_{n=2}^\infty f(n) x^n \\&=
x + \sum_{n=2}^\infty [2f(n-1)-f(n-2)] x^n \\ &=
x + 2x\sum_{n=1}^\infty f(n) x^n - x^2 \sum_{n=0}^\infty f(n) x^n \\ &=
x + (2x-x^2) P(x).
\end{align}
It follows that
$$
P(x) = \frac{x}{1-2x+x^2} = \frac{x}{(1-x)^2} = x \sum_{n=0}^\infty \binom{n+1}{1} x^n = \sum_{n=0}^\infty n x^n.
$$
Therefore $f(n) = n$.


Getting started with Program Analysis I'm looking for resources on getting started with program analysis.

The only book I've found on the topic is the Nielson & Nielson book.

Other than that, it seems like there are only "compiler" books where "program analysis" would be a chapter, or something along those lines.

Do people know of any other resources?

Unfortunately there aren't many textbooks on the topic. I think the best way to learn program analysis today is to survey different courses that are available, play with a few implementations and then look at a few research papers for your specific needs. What follows is a very small sampling of what's out there. Since you specifically mentioned compiler-oriented analyses were easy to find, I will not cover such material below.

Web-based resources
These are articles that emphasise the use of static analysis outside a compilation context.

A Reverse Engineering Reddit discussion on program analysis has many useful links.
Mozilla Wiki on abstract interpretation.
Deploying Static Analysis, a Dr. Dobbs article by Flash Sheridan
A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World, Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, Dawson Engler  in Communications of the ACM.

University courses on program analysis

Anders Møller at Arhus University teaches a course that covers object-oriented and web technology.
Bor-Yuh Evan Chang at University of Colorado Boulder has a foundational course that involves an OCaml implementation and a graduate course.
Ben Hardekopf at the University of California Santa Barbara used to have a great set of assignments, but they are no longer available online. Some students who took his course seem to have made a Python implementation available.
Markus Müller-Olm has a graduate course on analysis of Android.
Reinhard Wilhelm at the University of Sarbruecken teaches a graduate course that covers static analysis applications such as timing analysis, cache behaviour prediction, and some shape analysis.
Sumit Gulwani from MSR taught a nice course on statically estimating resource consumption of programs (time/memory) at the Oregon Summer School on Programming Languages.
Koushik Sen at the University of California at Berkeley teaches a course that focuses on bug finding and whose topics cover concolic execution and software model checking.
Jeffrey Foster at the University of Maryland teaches a course that covers type systems, model checking, alias analysis and a lot of the other usual material.
Patrick Cousot spent a year at MIT and taught a comprehensive, foundational course on abstract interpretation. The assignments include an OCaml implementation which go from concrete collecting semantics to some algorithmically non-trivial ideas.
A graduate course on abstract interpretation taught by some leaders in the field is a good place to catch up on even more theory.
Patrick Cousot taught a short course on abstract interpretation at the Oregon Summer School on Programming Languages in 2009.

Tools to play with

I am not listing a lot of research tools here. There are many of those but I have tried to list a few that you can download and play with to understand the area better.

Interproc is a very educational tool to play with to learn about numerical static analysis.
The Apron Numeric Abstraction library if you are really into numeric analysis.
Slayer is a shape analysis tool from Microsoft Research.
jStar is an analyzer for Java that is based on separation logic.
Microsoft Research has numerous groups developing numerous tools, many of which are available for download or have web-demos. I cannot list everything here and suggest you play with them.

There is a lot more, but that's probably enough to keep you busy for a while.


How to find sum of maximum K elements in range in array Recently, I came up to the following problem:

Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for  given range $[l, r]$ we should find sum of the $k$ maximum elements over all $A_i$ such that $l \leq i \leq r$.

Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QN\log N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.

Is it possible to solve this problem in complexity better than $O(QN\log N)$

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.

Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.

With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(n\log n)$ preprocessing and $O(\log n)$ time per query.


Average number of full nodes in rooted m-ary tree I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e.,
$$ \mu_{n}^{(m)} = \frac{\# \text{full nodes in all $m$-ary trees having $n$ nodes} }{\# \text{nodes in all $m$-ary trees having $n$ nodes}}$$.

As to the denominator, according to this answer, it sholud be given by
$$n C_m^n = \binom{mn}{n} \frac{n}{(m-1)n + 1}$$
As to numerator, at the first glance, I tought that this answer would have provided a hint; but then I have realized that it is not the case because it gives how many trees have $n$ full nodes, but I need to know how many full nodes are in the set of all the $m$-ary trees having $n$ nodes.

Could someone help me to understand how to solve it and provide (if any) a usable formula for $\mu_{n}^{(m)}$?

Every $m$-ary tree is a node together with up to $m$ children, which are also $m$-ary trees. Let $T(x,y)$ be the generating function in which the coefficient of $x^ny^k$ is the number of $m$-ary trees with $n$ nodes and $k$ full nodes. Then
$$
T(x,y) = x(1 + T(x,y) + \cdots + T(x,y)^{m-1} + yT(x,y)^m).
$$
The generating function of the total number of $m$-ary trees is $A(x) = T(x,1)$, and the generating function of the total number of full nodes in $m$-ary trees is $B(x) = \frac{\partial}{\partial y} T(x,y)|_{y=1}$.

The generating function $A(x)$ satisfies the equation
$$
A(x) = x(1 + A(x) + \cdots + A(x)^m).
$$
The generating function $B(x)$ satisfies the equation
$$
B(x) = x(B(x) + 2A(x)B(x) + 3A(x)^2B(x) + \cdots + mA(x)^{m-1}B(x) + A(x)^m),
$$
and so
$$
B(x) = \frac{xA(x)^m}{1-x(1+2A(x)+3A(x)^2+\cdots+mA(x)^{m-1})}.
$$

You can try solving these equations.

For example, in the trivial case $m=1$, we have $A(x) = x(1 + A(x))$, and so
$$ A(x) = \frac{x}{1-x} = \sum_{n \geq 1} x^n. $$
It follows that
$$
B(x) = \frac{x\cdot \frac{x}{1-x}}{1-x} = \frac{x^2}{(1-x)^2} = \sum_{n \geq 1} (n-1)x^n.
$$
Therefore the average number of full nodes in $1$-ary trees with $n$ nodes is $\frac{n-1}{1} = n-1$.


Justifying a claim in the proof of the master theorem I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.

My argument is as follows:
Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$.
$$g(n)=\sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i)$$
Now by the definition of big O, we have that $\exists c\in\mathbb{R}, N'\in \mathbb{R    }$ such that $\forall n/b^j>N'$, we have that $$f(n/b^j)<c(n/b^j)^{\log_b{a}-\epsilon}$$
This implies that $\forall n>N'b^{\log_bn-1}$
$$g(n)=
\sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i)
\leq \sum_{i=0}^{\log_{b}(n)-1}a^ic(n/b^i)^{\log_b{a}-\epsilon}
\leq c\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}
$$
Which implies that $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$ with $M=c$ and $N=N'b^{\log_bn-1}$.
Have I found the correct $c$ and $N$ to prove this claim for the upper bound of $g(n)$ and is this proof valid? Thanks!

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the maximum value of $f(n)/n^{\log_b a - \epsilon}$ over all positive integers $n < N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq \max(M,C) n^{\log_b a - \epsilon}$ holds for all integer $n \geq 1$. Therefore
$$
g(n) = \sum_{j=0}^{\log_b n-1} a^j f(n/b^j) \leq \max(M,C) \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} = O\left( \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} \right).
$$


Show that recurrence is $O(\phi^{\log n}) I have a function whose time complexity is given by the following recurrence:

\begin{equation*}
    T(n) = \begin{cases}
               \mathcal{O}(1) & \text{for } n=0\\
               T(k)+T(k-1)+\mathcal{O}(1)  & \text{for } n=2k\\
               T(k)+\mathcal{O}(1) & \text{for } n=2k+1\\
           \end{cases}
\end{equation*}

and I have to prove that $$T(n)\in \mathcal{O}(\phi^{\log_2 n}),$$

where $\phi$ is the golden ratio, $(1 + \sqrt5)\over2$.

I think I could prove it by induction but, how would I go on about it if I didn't know that $T(n)\in \mathcal{O}(\phi^{\log_2 n})$ in the first place?

Your sequence (shifted by 1) is known as Stern's diatomic sequence, or the Stern–Brocot sequences. The usual recurrence is:
\begin{align}
&a(0)=0 \\ &a(1)=1 \\ &a(2n) = a(n) \\ &a(2n+1) = a(n) + a(n+1)
\end{align}
The recurrence suggests that the answer has something to do with binary representation, so one might be prompted to look at the maximal value of $a(n)$ among numbers of length $m$ in binary:
$$
1,2,3,5,8,13,\ldots
$$
This is the Fibonacci sequence. (One can check that the first maxima are attained at $(2^n-(-1)^n)/3$.)

From here, one immediately sees that the rate of growth is $O(\phi^{\log_2 n})$.

More can be said. For example, Coons and Tyler determined the best possible constant in front of $\phi^{\log_2 n}$ in their paper The maximal order of Stern's diatomic sequence.

You can find many more links in the OEIS entry A002487.


checking whether a language is turing recognizable After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept.

so for instance, if i take a simple language like:"L = {< M > | M ACCEPTS < M >}", then it should be a turing recognizable language since there can be a turing machine that halts and accepts strings in it, and for strings not in that language it doesn't halt or just skip them.

however, how can i build such a turing machine(i mean the pseudocode for it)?

i know it's quite a simple question, but i rose it out of curiosity so i could learn and from that to adapt to more complicated problems.

thank you very much for helping me

Let $U$ be a universal Turing machine.  Then running $U$ on the input $\langle M \rangle, x$ will produce the same output as running $M$ on the input $x$ -- that's what it means for $U$ to be a universal Turing machine.  Others have shown how to build a universal Turing machine.

Then, you can build a Turing machine to do what you want by using $U$: namely, on input $\langle M \rangle$, your Turing machine should run $U(\langle M \rangle, \langle M \rangle)$.  Or, to put it another way, your Turing machine should make a second copy of the input it receives on the input tape, then run $U$.  If you know how to build a Turing machine to copy a bit-string, and if you have a universal Turing machine $U$, you'll have a solution for your problem.

This might not sound very enlightening, but it's the easiest way to describe how you can do it.  Programming Turing machines is incredibly tedious and usually not enlightening: it's like programming in a particularly nasty and human-unfriendly programming languages.  Therefore, it's best avoided wherever possible.  In this case, my solution lets you take advantage of the fact that someone else has already figured out how to build a universal Turing machine.

You might be wonder how to do that.  Well, the basic idea is that you need to implement an interpreter for Turing machines.  Pick your favorite programming language, like Python; could you write a Python program to interpret a Turing machine, one step at a time?  I bet you could -- it's a simple matter of programming.  Now you just need to do that, but this time instead of writing a Python program, you need to write a Turing machine -- a nastier and messier task that's far more tedious, but not conceptually different.


Uniqueness of minimum spanning tree If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?

If $G$ is a tree, it has a unique MST whatever its weights are.  The weights could be unique, all the same, anything.


Value of constants in Big Theta notation In Big Theta notation used for defining the running time of an algorithm, are the constants $c_1$ and $c_2$ different for every value of $n$?

Definition:

$\qquad \displaystyle \Theta (g(n)) = \{ f(n): \exists\, c_1,c_2,n_0>0. \forall n \geq n_0.\ \ c_1g(n) \leq f(n) \leq c_2g(n) \}.$

No, the constants $c_1,c_2$ are the same for all values of $n$. If they could depend on $n$ then the definition would be meaningless since $\Theta(g(n))$ would contain all positive functions. Indeed, suppose $f,g$ are two positive functions. Then for all $n$, $$c_1g(n) \leq f(n) \leq c_2g(n) \text{ for } c_1 = c_2 = \frac{f(n)}{g(n)}.$$


Machine learning - PCA and KNN on rgb images are too slow I work with python and images of tables (taken from above). My aim is to take a photo of a random table and then find the most similar tables to it in my database. By most similar I mean tables of similar shape(square, rectangular, round, oval), texture, colour etc.

For now, I am just running a PCA and then a KNN on all the pixels of rgb images of tables to let my computer find the most similar ones among them. Obviously the k-nearest neighbours of a table image must be images with tables which are very similar to it. The images are common images of tables and are of 529x940 dimensions.

My final goal is to run this program with 2000 or even 4000 table images so I need a more efficient machine learning algorithm for my task than the PCA and the KNN.

Can you recommend me another more efficient machine learning algorithm for this task?
Is Support Vector Machine significantly or Histogram of Gradient better for this task?

One possible approach is to train a classifier that, given a table, outputs its shape; train a classifier that, given a table, outputs its texture; train a classifier that, given a table, outputs its colour; and so on for each of the feature values you care about.  Thus, given a table, you can compute a feature vector that has the value of each of these attributes.  You can then define a distance metric on these feature vectors (e.g., some kind of weighted L2 distance), which will let you measure how similar two tables are by comparing their feature vectors.

Once you've done this, there's a straightforward way to find the most similar tables.  Use the classifiers to find the feature vectors for all the tables.  Then, use k-nearest neighbors to find the k most similar images to each given image.  If the number of features is not too large, this should be efficient, as you are now doing k-NN in a low-dimensional space.  For instance, you can use k-d trees or other data structures for nearest neighbor search to speed up the search.  These data structures are a lot more efficient when the number of dimensions is small.

I expect this should be plenty efficient for your needs.  Handling 4000 table images should be no problem.

There are other possible approaches as well, but the above is the first thing I'd try.


Is showing two different derivations enough to prove that a CFG is ambiguous? I'm wondering, is showing two different ways to derive the same word enough proof to show that a context-free grammar is ambiguous?

For example:

O = start symbol
Non-terminal = {O}
Terminal = {r, s}
Productions =
     O -> r
     O -> Or
     O -> sOO
     O -> OOs
     O -> OsO

There are two different derivations for the word rsrrs:

O -> OOs -> OsOOs -> rsOOs -> rsrOs -> rsrrs
O -> OsO -> rsO -> rsOOs -> rsrOs -> rsrrs

As Rick says, this is very close. The key is to show that there are two different parse-trees for the same word in the grammar.

What you have is okay, but presenting it as a linear derivation isn't enough. For example, consider something similar to what you did, but slightly different:

$O \rightarrow OOs \rightarrow OsOOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

At face value, these are two different derivations. However, if you look closely, you see that they only differ in the order that we expand the different terminals of the same intermediate word. So this is NOT a valid proof that the grammar is ambiguous.

However, if we look at your original example using parse-trees, we can see that it still holds:

O
|
O--O--s
|  |
r  s--O--O
      |  r
      r

And the second tree:

O
|
O--s--O
|     |
r     O--O--s
      |  |
      r  r

This shows that these are actually different parses: we use a different production from the initial $O$ symbol, so we know that they are different.

An equivalent way to do this is to use the linear derivations like you do, but always put them in "left-derivative" form, where you only ever expand the left-most non-terminal. So your derivations would become:

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OsO \rightarrow rsO \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

In this case, there's a 1:1 correspondence between left-derivatives and parse trees, so if there are two distinct ones, you know the grammar is ambiguous.

For the "bad" example I gave, both derivations give the first parse tree, so it's not a valid proof that the grammar is ambiguous.


Rotations in a treap I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done.

Image 1

Image 2

Initially, node F is violating the heap invariant. Its priority is too small, and it needs to be moved up the treap. The only operation needed is a single rotation. If you are not already familiar, please read this Wikipedia entry. Here are some illustrative diagrams:

https://upload.wikimedia.org/wikipedia/commons/2/23/Tree_rotation.png
https://upload.wikimedia.org/wikipedia/commons/3/31/Tree_rotation_animation_250x250.gif

I've drawn snapshots of the rotation process below. In each diagram, I've marked where the rotation is about to happen with stars (e.g. *E:14*). The direction of rotation should be obvious: the goal is to get F up the tree! Notice that as long as F is violating the heap invariant, we're rotating the parent of F.

       G:3
      /   \
    B:6   K:8
   /   \     \
A:11   D:9   L:12
      /   \
    C:16  *E:14*
             \
             F:2

       G:3
      /   \
    B:6   K:8
   /   \     \
A:11  *D:9*  L:12
      /   \
    C:16  F:2
          /
        E:14

       G:3
      /   \
   *B:6*  K:8
   /   \     \
A:11   F:2   L:12
      /
    D:9
   /   \
 C:16  E:14

       *G:3*
       /   \
     F:2    K:8
     /        \
   B:6         L:12
  /   \
A:11   D:9
      /   \
    C:16  E:14

      F:2
     /   \
   B:6    G:3
  /   \     \
A:11   D:9   K:8
      /   \    \
    C:16  E:14  L:12

There are some really nice properties of rotations which make this work. Obviously rotations preserve the in-order traversal of the tree. But also notice that, whenever a subtree is detached/reattached during a rotation, there is never a priority inversion (i.e. you never attach a subtree as a child of a node with a larger priority).


Reduction from a further constrained problem If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard?

Generally, this is probably not the case. For example, the NP Hard TSP is just a further constrained version of the shortest path problem.

Specifically, I have the problem:

  Given a universe $\mathcal{U}$ and a family $\mathcal{S}$ of subsets of $\mathcal{U}$, select $k$ sets from $\mathcal{S}$  such that the sum of the number of repeated times that each element is covered is maximized.
  Number of repeats are defined as one less than the number of instances.

If the number of repeated times for each element has an upper bound at 1, this is equivalent the densest k-subgraph problem (edges are elements and nodes are sets),

  Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum number of edges.

Since the densest k-subgraph problem is strongly NP Hard, can I prove that my problem is also NP Hard?

Hint: An instance of densest $k$-subgraph can be viewed as an instance of your problem, in which sets are vertices and elements are edges.

More generally, to prove that a problem P is NP-hard given that a (seemingly) related problem Q is NP-hard, you need to come up with a polytime reduction from Q to P. If Q is strongly related to P, such a reduction could be easy to find.


What is a good approach to symbol identification/recognition given a path, instead of raster data Excuse any mistakes in my description as I'm new to ML. But I have an application that takes user input to generate paths/curves (All symbols are single paths) and I would then like to attempt identification. This seems, generally, to be a pretty well studied problem, and there is a lot of reference I can find.

However everything I've found so far starts with some sort of raster format, which makes sense given that often recognition comes in initially in that format. But given my particular set of constraints it seems that there may be additional useful data given that I have paths.

So my question is are there any good techniques for doing identification without first rasterizing my paths that may be well suited for my particular instance, or is rasterizing to a grid particularly well suited to the problem, and should I just raster and solve this problem more classically?

What you are looking for is called "on-line recognition". I have written my Bachelors thesis about this:

  Thoma, Martin. "On-line Recognition of Handwritten Mathematical Symbols." arXiv preprint arXiv:1511.09030 (2015).

And I've created the online service write-math.com as a part of it.

As a short introduction, you might be interested in my presentations.

  Are there any good techniques for doing identification without first rasterizing my paths that may be well suited for my particular instance?

Yes. You can on the one hand make it a fixed-length sequence, on the other hand you can use recurrent neural networks (I didn't try that in my bachelors thesis)

  Is rasterizing to a grid particularly well suited to the problem, and should I just raster and solve this problem more classically?

This works astonishingly well. I achieved better results with the rasterized version (in my master thesis which isn't published yet due to bureaucracy problems at my university) than with fixed-length sequence techniques. But I guess the way to go is to do both.


Is every undecidable language reducible to any other undecidable language? For the undecidable languages I have seen so far , I am able to give a reduction from one language to other . Is it the case that every undecidable language is reducible to every other undecidable language?

If not can you prove that there exists 2 undecidable languages A and B such that A is not reducible to B.

Note : I am not talking only about mappping reducibility . I am talking about reducibility in general .

There is no concept of "reducibility in general". You always have to specify the power of the reduction. For example, if you allow mapping reductions but with literally any function (not necessarily a computable function) performing the mapping, then any language is reducible to any non-trivial language (i.e., anything other than $\emptyset$ or $\Sigma^*$).

If you do limit the power of the reduction in any way, then there are always pairs of problems $X$ and $Y$ such that $X\not\leq Y$. For example, take any language $X$ that isn't decidable in whatever model of computation you're using to define your reductions. Under that model of reductions, $X\not\leq \{0\}$.

OK, but you asked about undecidable languages and $\{0\}$ isn't undecidable. So, let $H_0$ be the halting problem for the model of computation you're using for your reductions. Let $H_1$ be the halting problem for Turing machines that have an oracle for $H_0$ (if $H_0$ is decidable, this is just the ordinary Turing machine halting problem), and let $H_2$ be the halting problem for Turing machines that have an oracle for $H_1$. Essentially the same proof that the ordinary Turing machine halting problem is undecidable shows that $H_2\not\leq H_1$, and both of these languages are undecidable.

Actually, I don't think that last paragraph is quite right. In the case that your model of reductions is more powerful than Turing machines, you probably need to use the reduction model instead of Turing machines to define the pair of halting problems. I don't have time to fix this right now but I'll come back to it this evening (UK time).


Checking equality of integers: O(1) in C but O(log n) in Python 3? Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$.
def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

But consider what is happening under the surface. Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. In either case this scan is $O(b)$ where $b$ is the number of bits. Since integers have a constant size in bits in C, this is simply $O(1)$.
EDIT: C doesn't compare bit-by-bit see this answer
In Python 3 however, integers do not have fixed size and the scan remains $O(b)$ for the number of bits in the input, or $O(\log a)$ where $a$ is the value of the input in base 10.
So if you're analyzing code in Python, any time you compare two integers, you are embarking on a  surprisingly complex journey of $O(\log n)$ with respect to the base 10 value of either number.
For me this raises several questions:

Is this correct? I haven't seen anyone else claim that Python compares ints in log time.
In the context of conducting an interview, should you notice or care if a candidate calls this $O(1)$?
Should you notice or care about this distinction in the real world?

EDIT: It is easily verified (and intuitive) that Python cannot compare arbitrarily large ints in constant time. So a better way to ask question 1 above might be "What (if any) is the justification for calling this operation $O(1)$? Because it's pragmatic? Conventional? Implied by the RAM model?

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit.

Not quite. C ints are machine-word-sized and compared with a single machine instruction; Python ints are represented in base $2^{30}$ (see e.g. https://rushter.com/blog/python-integer-implementation/) and compared digit-by-digit in that base. So the relevant base of the logarithm is $2^{30}$.
If at least one of numbers can be bounded by $2^{30d}$ for any fixed $d$, the comparison is $O(1)$ (because the number of digits is compared first), and if they can't, other operations are likely of much more concern than equality comparison. So in practice I'd say it's very unlikely to matter and if it does you'll know (and would be using not ints but something like the GNU Multiple Precision Arithmetic Library in C as well).


Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning.
If you have a given an array such as A[1...n] of numeric values (can be positive, zero, and negative) how may you determine the subarray A[i...j] (1≤ i ≤ j ≤ n) where the sum of elements is maximum overall (subvectors). Regarding the brute force algorithm below, how do you go about analyzing its best case, worst case, and average-case time complexity in terms of a polynomial of n and the asymptotic notation of ɵ. How would you even show steps? Without building out the algorithm?
Thanks in advance.
// PSEUDOCODE
// BRUTE-FORCE-FIND-MAXIMUM-SUBARRAY(A)
n = A.length
max-sum = -∞
for l = 1 to n
    sum = 0
    for h = l to n
        sum = sum + A[h]
        if sum > max-sum
            max-sum = sum
            low = l
            high = h
return (low, high) # No, return of MAX-HIGH

Note: New to the forum, not sure if this is the correct exchange. But I am referring to and referencing problems from https://walkccc.me/CLRS/Chap04/4.1/.

Your algorithm goes over all pairs $(\ell,h)$ of indices such that $1 \leq \ell \leq h \leq n$, and for each of them, runs $\Theta(1)$ operations (the rest of the steps are insignificant from an asymptotic point of view). If there are $M$ such pairs, then the best case, worst case, average case complexity are all equal to $\Theta(M)$.


Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own I had an online round at a company where I was asked this question.
There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$.
Each item has three properties, weight, profit and type. There are only two types of objects.
Type 0 item can be selected independently own their own.
A type 1 item cannot the selected on its own and needs another item of type 1.

Note: The problem does not say if this means what we have to select at least two type 1 items to select any at all, or that all the type 1 items must be in pairs.

Constraints:

$N < 10^3$

$W < 10^5$

$\mathit{weight}, \mathit{profit} < 10^5$

This is obviously (?) related to the knapsack problem, as without the restriction on the type 1 objects, it would actually be the 0-1 knapsack problem. How do I go about doing this? Any help and general ideas are extremely appreciated.

I think this can be solved the same way that knapsack problem is solved using dynamic programming.
I present the problem for the case where type 1 items are to be selected in pairs, but the other case is solvable in a similar way.
Suppose the weights are $\{w_1, …, w_n\}$, the profits are $\{p_1, …, p_n\}$ and the types are $\{t_1, …, t_n\}$. Let's define, for $w\in [\![0, W]\!], i \in [\![1, n]\!], j\in\{0,1\}$, $K(w, i, j)$ representing the maximum profit using a knapsack of capacity $w$, using items $1, …, i$, with a parity of type 1 items equal to $j$.
We want to determine $K(W, n, 0)$. Using this definition, we can calculate $K(w, i, j)$ by distinguishing if we take or not the $i$-th item:
$K(w, i, j) = \max(K(w-w_i, i - 1, j \oplus t_i) + p_i, K(w, i - 1, j))$ (where $\oplus$ is the addition modulo 2)
With this formula, we can then compute $K(W, n, 0)$ in time complexity $O(nW)$.
In the case you just need to pick at least two items of type 1 if you want any, $K(w, i, j)$ could represent the maximum profit with $j\in \{0, 1,2\}$ representing respectively exactly zero type 1 item, exactly one type 1 item or at least 2 type 1 items.


Circuit of constant depth that takes three binary numbers and outputs two binaries? How can I construct -- or better to say what type of circuit can be like this -- a circuit that takes 3 binary numbers (a, b, c) and then calculates two binary numbers (d, e) in a way that a + b + c = d + e The circuit should be of constant depth and furthermore, a, b, c, d, and e are as follows;

a=a_n−1…a_0
b=b_n−1…b_0
c=c_n−1…c_0

d=d_n…d_0
e=e_n…e_0

A circuit which would satisfy this requirement is a carry-save adder.  I'm sure you can find a reference for the gate layout somewhere.


How to construct a NFA that the third symbol and the third from last symbol are same? Suppose the alphabet is {a,b}. I have tried coming up with NFA1: third symbol is a, and NFA2: third from last symbol is a. Then NFA3 and NFA4 similar but with symbol of b. Then I use intersection of NFA1, NFA2, and intersection of NFA3, NFA4, and add $\epsilon$ transition. But things seem to go wrong here. When doing the intersection of, say, NFA1, and NFA2, obviously the new NFA would not accept strings such as aba, aaa.

I have been trying different methods but still stuck here for hours. Any help of hint would be much appreciated!

Hint:

Here is a NFA that accepts exactly those strings whose first and last character are both $a$:

Can you modify and extend this to become a solution to your problem?


Comparing 2 video files I have a bunch of wmv files (~300), named the following way: video1.wmv -> videox.wmv. Some of these video files, are exact duplicates of one another (same format, same bitrate, same length, basically, they were copied and renamed, so the only thing that differs from them is their name). Is there any way to find out if two video files from this group are identical or not, so I would be able to filter out the duplicate ones?

Comparing their size is unfortunately out of the question, because I manually went through some of them, and because each of them is around the same length(even the non duplicate ones), some have identical sizes, but they are not identical per se.

If there is a possibility, I would prefer a method which could be implemented as a PHP script, but any other method of comparing them would be welcome.

Thanks!

A general algorithm is to compute the SHA256 hash of each file, then sort the hashes and look for duplicates.  After sorting any duplicates that may exist will be consecutive.  For all practical purposes, you can assume that two files will be identical if and only if their SHA256 hash is the same.

If you're asking how to do this from the command line or looking for a product recommendation, take a look at this:

https://unix.stackexchange.com/q/71176/9812
https://superuser.com/q/8223/93541
https://superuser.com/q/46690/93541


Sizeof function definition in a system Why sizeof(int) and sizeof(int *) takes different value in a system? I mean generally size of integer is 4 B, but size of integer pointer is 8 B. But why they cannot take same value, although their return type is same?

An integer is a value, whereas a pointer to an integer is a pointer, that is, a memory address. In most systems, all pointers have the same size, but the objects they point to can have different sizes. For example, in your systems pointers are 8 bytes long, whereas integers come in various sizes — possibly from 1 byte up to 8 bytes.

You might be misled by the specific quirky syntax of C, which allows declarations of the form

int a, *b;

This declares an integer a and a pointer b. This is just a confusing feature of C syntax.


Shuffling a collection too large for memory I have a set that is too large to hold in memory but I have a function that I can use to compute a value within the set given an index.  I'm curious if there's a standard way to shuffle this set, a pseudo-shuffle is acceptable and expected.

I imagine a function that is initialized with some parameters, including the size of the set to be shuffled, and that I can call repeatedly, getting unique and pseudo-random indexes each time that I can use to generate the corresponding value in my set.  I also imagine that this function is periodic and repeats after I've gone through all values once (so there's some mod relation).

This function need not be cryptographically secure but rather be easy to construct and hold in memory so that the next "random" value of the set may be generated.

Here's a concrete formulation of the problem. I want to iteratively generate "random" colors in the RGB spectrum without repeats. I don't want to create an array of 256^3 elements and shuffle them. I want a function that on each call provides an index in the range that I have not yet received, until I've exhausted the range.

How might you construct a function that satisfies the above?

Let $n$ denote the number of items in the set, and $f(i)$ denote the $i$th value.  Use format-preserving encryption to construct a random permutation $\sigma:\{1,\dots,n\} \to \{1,\dots,n\}$.  Define $g(i) = f(\sigma(i))$.  Then $g$ is a representation of a randomly shuffled version of your set, and specific items can be accessed very efficiently.

To address your concrete problem, you'd pick a random permutation on $\{0,1\}^{24}$, i.e., $\sigma : \{0,1\}^{24} \to \{0,1\}^{24}$.  This can be done using format-preserving encryption: format-preserving encryption will give you a block cipher $E:K \times \{0,1\}^{24} \to \{0,1\}^{24}$ such that if you pick a key $k \in K$ random, $E_k$ will be (indistinguishable from) a random permutation on $\{0,1\}^{24}$. Moreover, $E_k$ can be efficiently evaluated.  Then, if you want $m$ random RGB colors, you'd pick a random key $k$ and output the $m$ colors $E_k(0), E_k(1), \dots, E_k(m-1)$.

A reasonable way to build a 24-bit block cipher is to use a Feistel cipher on 24 bits: say, 4 rounds, where in the $i$th round you map the input $L||R$ to the output $R||(L \oplus f_k(R,i))$, where $L,R$ are each 12 bits long and $f_k$ is a PRF, say $f_k = AES_k(R||i)$, and $||$ denotes concatenation of bits.  You can adjust the number of rounds (fewer rounds is faster; more rounds gives higher amount of pseudorandomness; you probably want at least 3 rounds), and you can adjust the choice of $f$ (for instance, instead of a cryptographic-based construction, you could use any fast, non-cryptographic hash function).  This is the construction proposed in https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_a_Feistel_network.  I suggest referring to the Wikipedia link I shared above for an overview of standard constructions for format-preserving encryption.


Precise definition of term: *schema* Does the term schema, in the context of describing a structure, refer to the actual structure of the data, or the description of this structure? I.e. can I talk about the schema of an entity without a schema language?

For example, suppose I am writing documentation for some JSON API, that always returns a particular structure, say:

{
   "name" : "jeroen",
   "age" :  28
}

Can I say that the schema for the payload returned by this API includes required values for "name" and "age"? Or does the term exclusively refer to another document that formally describes this structure using a schema language of some sort? In that case, what is another appropriate term to refer to the recurring pattern in the structure?

The Github API, has a section titled schema: http://developer.github.com/v3/#schema. However, the word schema is not mentioned in the text itself, nor do they use any schema language. This would suggest that schema is just a general term for the structure/attributes of the output. Unless they consider english as a schema language, in which case the entire page is a schema. Hmmm.

In order to write the documentation of the structure of the JSON objects returned from your API you can follow two approaches:

describe the common attributes and of the objects returned by every function of your API; and then for each API function describe the specific attributes (their type, meaning, and example);
Many APIs that use JSON to exchange data are documented using this approach: e.g. Google APIs for various services, Facebook Graph API, Twitter API, ...
In this case I think it is not correct to use the term "schema".
or you can give a formal description of the output using a schema definition language like JSON-schema (designed by the IETF) and that plays the same role of the XML schema definition language for XML.
But I don't know if JSON-schema is an established standard (there is an active Google group, but I didn't find any "notable" example, ... ).
In this case you should provide a valid (json-)schema for the output of each function.

If you choose this approach, then you should say that name and age are two required properties of the (json-)schemas of the (json-)objects returned by the functions of your APIs (but obviously you should provide the full-schemas, too)


Analyzing time complexity of solution in tutorial Could someone explain time complexity of solution of in this tutorial?

I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$.

What I figured so far is, for computing $f(Y)$, we would require $O(\lvert Y\rvert)$ steps and for fixed set $X$ (such that $\lvert X\rvert=k$), we would have $2^{n-k}$ number of $Y$ sets that would contain set $X$. And there would be ${n \choose k}$ such $X$ sets.

So total steps should be $${n \choose k } {\sum_{r=0}^{n-k} {n-k \choose r} ({k+r})} \leq {n \choose k} n  2^{n-k}$$

But is this value tightly bounded by $3^k k$?

Let me focus on the following question:

  Is $3^nn$ a tight bound on $\binom{n}{k}n2^{n-k}$?

First, let us see that this is a valid bound. This follows from the binomial theorem:
$$
\sum_{k=0}^n \binom{n}{k} n 2^{n-k} = 3^nn.
$$

Since there are $n+1$ summands in the expression, we deduce that
$$
\max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} \ge \frac{3^nn}{n+1}.
$$
Using Stirling's formula, we find out that
$$
\max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} = \Theta(3^n\sqrt{n}).
$$
This is a tighter bound.